chapter3.tex

% !Mode:: "TeX:UTF-8"
% !TEX encoding = UTF-8 Unicode

%----------------------------------------------------------------------------------------
% 机器翻译：基础与模型
% Machine Translation: Foundations and Models
%
% Copyright 2020
% 肖桐(xiaotong@mail.neu.edu.cn) 朱靖波 (zhujingbo@mail.neu.edu.cn)
%----------------------------------------------------------------------------------------

%----------------------------------------------------------------------------------------
%    CONFIGURATIONS
%----------------------------------------------------------------------------------------

\renewcommand\figurename{图}%将figure改为图
\renewcommand\tablename{表}%将figure改为图

%----------------------------------------------------------------------------------------
%	CHAPTER 3
%----------------------------------------------------------------------------------------
\chapter{词法分析和语法分析基础} \label{chapter_3}

\parinterval 机器翻译并非是一个孤立的系统，它依赖于很多模块，并且需要多个学科知识的融合。其中就会用到许多自然语言处理工具来对不同语言的文字进行分析。因此，在正式开始介绍机器翻译的内容之前，本章会对相关的词法分析和语法分析知识进行概述，包括：分词、命名实体识别、短语结构句法分析。它们都是自然语言处理中的经典问题，而且在机器翻译中被广泛使用。本章会重点介绍这些任务的定义和求解问题的思路。其中也会使用到统计建模方法，因此本章也可以被看作是第二章内容的延伸。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{问题概述}

\parinterval 很多时候机器翻译系统被看作是孤立的“黑盒”系统（图\ref{fig:3.1-1}(a)）。将一段文本作为输入送入机器翻译系统之后，系统输出翻译好的译文。但是真实的机器翻译系统非常复杂，因为系统看到的输入和输出实际上只是一些符号串，这些符号并没有任何意义，因此需要进一步对这些符号串进行处理才能更好的使用它们。比如，需要定义翻译中最基本的单元是什么？符号串是否具有结构信息？如何用数学工具刻画这些基本单元和结构？

%----------------------------------------------
\begin{figure}[htp]
    \centering
 	\subfigure[\small{机器翻译系统被看作一个黑盒}] {\input{./Chapter3/Figures/figure-mt-system-as-a-black-box}  }
 	\subfigure[\small{机器翻译系统 = 前/后处理 + 核心引擎}] {\input{./Chapter3/Figures/figure-mt=language-analysis+translation-engine}}
	\caption{机器翻译系统的结构}
    \label{fig:3.1-1}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:3.1-1}(b)展示了一个机器翻译系统的输入和输出形式。可以看到，输入的中文词串“猫喜欢吃鱼”被加工成一个新的结构（图\ref{fig:3.1-2}）。直觉上，这个结构有些奇怪，因为上面多了很多新的符号，而且还有一些线将不同符号进行连接。实际上这就是一种常见的句法表示\ \dash \ 短语结构树。生成这样的结构会涉及两方面问题：

\begin{itemize}
\vspace{0.5em}
\item {\small\sffamily\bfseries{分词}}\index{分词}（ Word Segmentation）\index{Word Segmentation}：这个过程会把词串进行切分，切割成最小的具有完整功能的单元\ \dash\ {\small\sffamily\bfseries{单词}}\index{单词}（Word\index{单词}）。因为只有知道了什么是单词，机器翻译系统才能完成对句子的表示、分析和生成。
\vspace{0.5em}
\item {\small\sffamily\bfseries{句法分析}}\index{句法分析}（Parsing）\index{Parsing}：这个过程会对分词的结果进行进一步分析。比如，可以对句子进行浅层分析，得到句子中实体的信息（如人名、地名等）。也可以对句子进行更深层次的分析，得到完整的句法结构，类似于图\ref{fig:3.1-2}中的结果。这种结构可以被看作是对句子的进一步抽象，被称为短语结构树，比如，NP+VP就可以表示由名词短语（Noun Phrase，NP）和动词短语（Verb Phrase，VP）构成的主谓结构。利用这些信息，机器翻译可以更加准确地对句子的结构进行分析和生成。
\vspace{0.5em}
\end{itemize}

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-analysis-of-sentence-participle&syntactic}
\caption{汉语句子“猫喜欢吃鱼”的分析结果（分词和句法分析）}
\label{fig:3.1-2}
\end{figure}
%-------------------------------------------

\parinterval 类似地，机器翻译输出的结果也可以包含同样的信息。甚至系统输出英语译文之后，还有一个额外的步骤来把部分英语单词的大小写恢复出来，比如，句首单词的首字母要大写。

\parinterval 一般来说，在送入机器翻译系统前需要对文字序列进行处理和加工，这个过程被称为{\small\sffamily\bfseries{预处理}}\index{预处理}（Pre-processing）\index{Pre-processing}。类似地，在机器翻译模型输出译文后进行的处理被称作{\small\sffamily\bfseries{后处理}}\index{后处理}（Post-processing）\index{Post-processing}。这两个过程对机器翻译性能影响很大，比如，对于神经机器翻译系统来说，不同的分词策略可能会造成翻译性能的天差地别。

\parinterval 值得注意的是，有些观点认为，对于机器翻译来说，不论是分词还是句法分析，并不要求符合人的认知和语言学约束。换句话说，机器翻译所使用的“单词”和“结构”本身并不是为了符合人类的解释，它们更直接目的是为了进行翻译。从系统开发的角度，有时候即使使用一些与人类的语言习惯有差别的处理，仍然会带来性能的提升，比如在神经机器翻译中，在传统分词的基础上进一步使用{\small\sffamily\bfseries{双字节编码}}\index{双字节编码}（Byte Pair Encoding，BPE）\index{Byte Pair Encoding}子词切分\upcite{DBLP:conf/acl/SennrichHB16a}会使得机器翻译性能大幅提高。当然，自然语言处理中语言学信息的使用一直是学界关注的焦点。甚至关于语言学结构对机器翻译是否有作用这个问题也有一些不同的观点。但是不能否认的是，无论是语言学的知识，还是计算机自己学习到的知识，对机器翻译都是有价值的。在后续章节会看到，这两种类型的知识对机器翻译帮助很大。

\parinterval 剩下的问题是如何进行句子的切分和结构的分析。思路有很多，一种常用的方法是对问题进行概率化，用统计模型来描述问题并求解之。比如，一个句子切分的好坏，并不是非零即一的判断，而是要估计出这种切分的可能性大小，最终选择可能性最大的结果进行输出。这也是一种典型的用统计建模的方式来描述自然语言处理问题的方法。

\parinterval 本章将会对上述问题及求解问题的方法进行介绍。并将统计建模应用到中文分词、命名实体识别和短语结构句法分析等任务中。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{中文分词}

\parinterval 对于机器翻译系统而言，输入的是已经切分好的单词序列，而不是原始的字符串（图\ref{fig:3.2-1}）。比如，对于一个中文句子，单词之间是没有间隔的，因此需要把一个个的单词切分出来，这样机器翻译系统可以区分不同的翻译单元。甚至，可以对语言学上的单词进行进一步切分，得到词片段序列（比如：中国人$\to$中国/人）。广义上，可以把上述过程看作是一种分词过程，即：将一个输入的自然语言字符串切割成单元序列，每个{\small\sffamily\bfseries{单元}}\index{单元}（Token）\index{Token}都对应可以处理的最小单位。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-a-simple-pre-processing-process}
\caption{一个简单的预处理流程}
\label{fig:3.2-1}
\end{figure}
%-------------------------------------------

\parinterval 分词得到的单元序列既可以是语言学上的词序列，也可以是根据其他方式定义的基本处理单元。在本章中，把分词得到的一个个单元称为单词或词，尽管这些单元可以不是语言学上的完整单词，而这个过程也被称作{\small\sffamily\bfseries{词法分析}}\index{词法分析}（Lexical Analysis）\index{Lexical Analysis}。除了汉语，词法分析在日语、泰语等单词之间无明确分割符的语言中有着广泛的应用，芬兰语、维吾尔语等一些形态学十分丰富的语言也需要使用词法分析来解决复杂的词尾、词缀变化等形态学变化。

\parinterval 在机器翻译中，分词系统的好坏往往会决定译文的质量。分词的目的是定义系统处理的基本单元，那么什么叫做“词” 呢？关于词的定义有很多，比如：

\vspace{0.5em}
\begin{definition} 词

\vspace{0.5em}
语言里最小的可以独立运用的单位。
\begin{flushright}——《新华字典》\end{flushright}

单词，含有语义内容或语用内容，且能被单独念出来的的最小单位。
\begin{flushright}——维基百科\end{flushright}

语句中具有完整概念，能独立自由运用的基本单位。
\begin{flushright}——《国语辞典》\end{flushright}
\end{definition}


\parinterval 从语言学的角度来看，人们普遍认为词是可以单独运用的、包含意义的基本单位。这样可以使用有限的词组合出无限的句子，这也正体现出自然语言的奇妙之处。不过，机器翻译并不仅仅局限于语言学定义的单词。比如，神经机器翻译中广泛使用的BPE子词切分方法，可以被理解为将词的一部分切分出来，将得到的词片段送给机器翻译系统使用。比如，对如下英语字符串，可以得到切分结果：

\vspace{0.8em}

\noindent
\begin{tabular}{l l l}
Interesting \; $\to$ \; Interest/ing & selection $\to$ \;se/lect/ion & procession $\to$ \; pro/cess/ion  \\
Interested $\to$ \; Interest/ed & selecting $\to$ \; se/lect/ing & processing $\to$ \; pro/cess/ing \\
Interests $\to$ \; Interest/s & selected $\to$ \; se/lect/ed & processed $\to$ \; pro/cess/ed
\end{tabular}

\vspace{0.8em}

\parinterval 词法分析的重要性在自然语言处理领域已经有共识。如果切分的颗粒度很大，获得单词的歧义通常比较小，比如“中华人民共和国”整体作为一个单词不存在歧义，而如果单独的一个单词“国”，可能会代表“中国”、“美国”等不同的国家，存在歧义。但是随着切分颗粒度的增大，特定单词出现的频次也随之降低，低频词容易和噪音混淆，系统很难对其进行学习。因此，处理这些问题并开发适合翻译任务的分词系统是机器翻译的第一步。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{基于词典的分词方法}

\parinterval 计算机并不能像人类一样在概念上理解“词”，因此需要使用其他方式让计算机“学会”如何分词。一个最简单的方法就是给定一个词典，在这个词典中出现的汉字组合就是所定义的“词”。也就是说，可以通过一个词典定义一个标准，符合这个标准定义的字符串都是合法的“词”。

\parinterval 在使用基于词典的分词方法时，只需预先加载词典到计算机中，扫描输入句子，查询其中的每个词串是否出现在词典中。如图\ref{fig:3.2-2}所示，有一个包含六个词的词典，给定输入句子“确实现在物价很高”后，分词系统自左至右遍历输入句子的每个字，发现词串“确实”在词典中出现，说明“确实”是一个“词”。之后，重复这个过程。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-example-of-word-segmentation-based-on-dictionary}
\caption{基于词典进行分词的实例}
\label{fig:3.2-2}
\end{figure}
%-------------------------------------------

\parinterval 但是，基于词典的分词方法很“硬”。这是因为自然语言非常灵活，经常出现歧义。图\ref{fig:3.2-3}就给出了上面例子中的交叉型歧义，从词典中查看，“ 实现”和“现在”都是合法的单词，但是在句子中二者有重叠，因此词典无法告诉系统哪个结果是正确的。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-cross-type-word-segmentation-ambiguity}
\caption{交叉型分词歧义}
\label{fig:3.2-3}
\end{figure}
%-------------------------------------------

\parinterval 类似的例子在生活中也很常见。再比如“答辩结束的和尚未答辩的同学都请留在教室”一句中，正常的分词结果是“答辩/结束/的/和/尚未/答辩/的/同学/都/请/留在/教室”，但是由于“尚未”、“和尚”都是常见词汇，使用基于词典的分词方法在这时很容易出现切分错误。

\parinterval 基于词典的分词方法是典型的基于规则的方法，完全依赖于人工给定的词典。在遇到歧义时，需要人工定义消除歧义的规则，比如，可以自左向右扫描每次匹配最长的单词，这是一种简单的启发式消歧策略。图\ref{fig:3.2-2}中的例子实际上就是使用这种策略得到的分词结果。但是，启发式的消岐方法仍然需要人工设计启发式规则，而且启发式规则也不能处理所有的情况。所以说简单的基于词典的方法还不能很好的解决分词问题。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{基于统计的分词方法}

\parinterval 既然基于词典的方法有很多问题，那么就需要一种更为有效的方法。在上文中提到，想要搭建一个分词系统，需要让计算机知道什么是“词”，那么可不可以给出已经切分好的分词数据，让计算机在这些数据中学习到规律呢？答案是肯定的，利用“数据”来让计算机明白“词”的定义，让计算机直接在数据中学到知识，这就是一个典型的基于统计建模的学习过程。

%----------------------------------------------------------------------------------------
%    NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------

\subsubsection{1. 统计模型的学习与推断}

\parinterval 统计分词也是一种典型的数据驱动方法。这种方法将已经经过分词的数据“喂”给系统，这个数据也被称作{\small\sffamily\bfseries{标注数据}}\index{标注数据}（Annotated Data）\index{Annotated Data}。在获得标注数据后，系统自动学习一个统计模型来描述分词的过程，而这个模型会把分词的“知识”作为参数保存在模型中。当送入一个新的需要分词的句子时，可以利用学习到的模型对可能的分词结果进行概率化的描述，最终选择概率最大的结果作为输出。这个方法就是基于统计的分词方法，其与{\chaptertwo}介绍的统计语言建模方法本质上是一样的。具体来说，可以分为两个步骤：

\begin{itemize}
\vspace{0.5em}
\item {\small\sffamily\bfseries{训练}}。利用标注数据，对统计模型的参数进行学习。
\vspace{0.5em}
\item {\small\sffamily\bfseries{预测}}。利用学习到的模型和参数，对新的句子进行切分。这个过程也可以被看作是利用学习到的模型在新的数据上进行推断。
\vspace{0.5em}
\end{itemize}

\parinterval 图\ref{fig:3.2-4}给出了一个基于统计建模的汉语分词实例。左侧是标注数据，其中每个句子是已经经过人工标注的分词结果（单词用斜杠分开）。之后，建立一个统计模型，记为$\funp{P}(\cdot)$。模型通过在标注数据上的学习来对问题进行描述，即学习$\funp{P}(\cdot)$。最后，对于新的未分词的句子，使用模型$\funp{P}(\cdot)$对每个可能的切分方式进行概率估计，之后选择概率最高的切分结果输出。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-word-segmentation-based-on-statistics}
\caption{基于统计的自动分词流程}
\label{fig:3.2-4}
\end{figure}
%-------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------

\subsubsection{2. 全概率分词方法}

\parinterval 上述过程的核心在于从标注数据中学习一种对分词现象的统计描述，即句子的分词结果概率$\funp{P}(\cdot)$。如何让计算机利用分好词的数据学习到分词知识呢？本书的{\chaptertwo}曾介绍如何对单词概率进行统计建模，而对分词现象的统计描述就是在单词概率的基础上，基于独立性假设获取的\footnote{即假定所有词的出现都是相互独立的。}。虽然独立性假设并不能完美描述分词过程中单词之间的关系，但是它大大化简了分词问题的复杂度。

\parinterval 如图\ref{fig:3.2-5}所示，可以利用大量人工标注好的分词数据，通过统计学习方法获得一个统计模型$\funp{P}(\cdot)$，给定任意分词结果$W = w_1w_2 \ldots w_m$，都能通过$\funp{P}(W)=\funp{P}(w_1) \cdot \funp{P}(w_2) \cdot \ldots \cdot \funp{P}(w_m)
$计算这种切分的概率值。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-examples-of-chinese-word-segmentation-based-on-1-gram-model}
\caption{基于1-gram语言模型的中文分词实例}
\label{fig:3.2-5}
\end{figure}
%-------------------------------------------

\parinterval 以“确实现在数据很多”这个实例来说，如果把这句话按照“确实/现在/数据/很/多”这样的方式进行切分，这个句子切分的概率$\funp{P}$(确实/现在/数据/很/多) 可以通过每个词出现概率相乘的方式进行计算。
\begin{eqnarray}
&\funp&{P}\textrm{(确实/现在/数据/很/多)} \nonumber \\
& = &\funp{P}\textrm{(确实)} \cdot \funp{P}\textrm{(现在)} \cdot \funp{P}\textrm{(数据)} \cdot \funp{P}\textrm{(很)} \cdot \funp{P}\textrm{(多)}
\label{eq:3.2-1}
\end{eqnarray}

\parinterval 经过充分训练的统计模型$\funp{P}(\cdot)$就是我们所说的分词模型。对于输入的新句子$S$，通过这个模型找到最佳的分词结果输出。假设输入句子$S$是“确实现在数据很多”，可以通过列举获得不同切分方式的概率，其中概率最高的切分方式，就是系统的目标输出。

\parinterval 这种分词方法也被称作基于1-gram语言模型的分词，或全概率分词\upcite{刘挺1998最大概率分词问题及其解法,丁洁2010基于最大概率分词算法的中文分词方法研究}。全概率分词最大的优点在于方法简单、效率高，因此被广泛应用在工业界系统里。它本质上就是一个1-gram语言模型，因此可以直接复用$n$-gram语言模型的训练方法和未登录词处理方法。与传统$n$-gram语言模型稍有不同的是，分词的预测过程需要找到一个在给定字符串所有可能切分中1-gram语言模型得分最高的切分。因此，可以使用{\chaptertwo}中所描述的搜索算法实现这个预测过程，也可以使用动态规划方法\upcite{bellman1966dynamic}快速找到最优切分结果。由于本节的重点是介绍中文分词的基础方法和统计建模思想，因此不会对相关搜索算法进行进一步介绍，有兴趣的读者可以参考{\chaptertwo}和本章\ref{sec3:summary}节的相关文献做进一步深入研究。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{命名实体识别}

\parinterval 在人类使用语言的过程中，单词往往不是独立出现的。很多时候，多个单词会组合成一个更大的单元来表达特定的意思。其中，最典型的代表是{\small\sffamily\bfseries{命名实体}}\index{命名实体}（Named Entity）\index{Named Entity}。通常，命名实体是指名词性的专用短语，例如公司名称、品牌名称、产品名称等专有名词和行业术语。准确地识别出这些命名实体，是提高机器翻译质量的关键。比如，在翻译技术文献时，往往需要对术语进行识别并进行准确翻译，因此引入{\small\sffamily\bfseries{命名实体识别}}\index{命名实体识别}（Named Entity Recognition）\index{Named Entity Recognition} 可以帮助系统对特定术语进行更加细致的处理。

\parinterval 从句法分析的角度来说，命名实体识别是一种浅层句法分析任务。它在分词的基础上，进一步对句子浅层结构进行识别，包括词性标注、组块识别在内的很多任务都可以被看作是浅层句法分析的内容。本节会以命名实体识别为例，对基于序列标注的浅层句法分析方法进行介绍。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{序列标注任务}

\parinterval 命名实体识别是一种典型的{\small\sffamily\bfseries{序列标注}}\index{序列标注}（Sequence Labeling\index{Sequence Labeling}）任务，对于一个输入序列，它会生成一个相同长度的输出序列。输入序列的每一个位置，都有一个与之对应的输出，输出的内容是这个位置所对应的标签（或者类别）。比如，对于命名实体识别，每个位置的标签可以被看作是一种命名实体“开始”和“结束”的标志，而命名实体识别的目标就是得到这种“开始”和“结束”标注的序列。不仅如此，分词、词性标注、组块识别等也都可以被看作是序列标注任务。

\parinterval 通常来说，序列标注任务中首先需要定义标注策略，即使用什么样的格式来对序列进行标注。为了便于描述，这里假设输入序列为一个个单词\footnote{广义上，序列标注任务并不限制输入序列的形式，比如，字符、单词、多个单词构成的词组都可以作为序列标注的输入单元。}。常用的标注策略有：

\begin{itemize}
\vspace{0.5em}
\item {\small\sffamily\bfseries{BIO格式}}（Beginning-inside-outside）。以命名实体识别为例，B代表一个命名实体的开始，I表示一个命名实体的其它部分，O表示一个非命名实体单元。
\vspace{0.5em}
\item {\small\sffamily\bfseries{BIOES格式}}。与BIO格式相比，多出了标签E（End）和S（Single）。仍然以命名实体识别为例，E和S分别用于标注一个命名实体的结束位置和仅含一个单词的命名实体。
\vspace{0.5em}
\end{itemize}

\parinterval 图\ref{fig:3.3-1}给出了不同标注格式所对应的标注结果。可以看出文本序列中的非命名实体直接被标注为“O”，而命名实体的标注则被分为了两部分：位置和命名实体类别，图中的“B”、“I”、“E”等标注出了位置信息，而“CIT”和“CNT”则标注出了命名实体类别（“CIT”表示城市，“CNT”表示国家）。可以看到，命名实体的识别结果可以通过BIO、BIOES这类序列标注结果归纳出来：例如在BIOES格式中，标签“B-CNT”后面的标签只会是“I-CNT”或“E-CNT”，而不会是其他的标签。同时，在命名实体识别任务中涉及到实体边界的确定，而“BIO”或“BIOES”的标注格式本身就暗含着边界问题：在“BIO”格式下，实体左边界只能在“B”的左侧，右边界只能在“B”或“I”的右侧；在“BIOES”格式下，实体左边界只能在“B”或“S”的左侧，右边界只能在“E”和“S”的右侧。

%----------------------------------------------
\begin{figure}[htp]
    \centering
 	\subfigure[\small{BIO格式标注命名实体}] {\input{./Chapter3/Figures/figure-labeling-named-entities-in-bio-format} }
 	\subfigure[\small{BIOES格式标注命名实体}] {\input{./Chapter3/Figures/figure-labeling-named-entities-in-bioes-format}}
	\caption{BIO和BIOES格式对比}
    \label{fig:3.3-1}
\end{figure}
%-------------------------------------------

\parinterval 需要注意的是，虽然图\ref{fig:3.3-1}中的命名实体识别以单词为基本单位进行标注，但真实系统中也可以在字序列上进行命名实体识别，其方法与基于词序列的命名实体识别是一样的。因此，这里仍然以基于词序列的方法为例进行介绍。

\parinterval 对于像命名实体识别这样的任务，早期的方法主要是基于词典和规则的方法。这些方法依赖于人工构造的识别规则，通过字符串匹配的方式识别出文本中的命名实体\upcite{1995University,krupka1998isoquest,DBLP:conf/muc/BlackRM98}。严格意义上来说，那时命名实体识别还并没有被看作是一种序列标注问题。

\parinterval 序列标注这个概念更多的是出现在基于统计建模的方法中。许多统计机器学习方法都被成功应用用于命名实体识别任务，例如{\small\sffamily\bfseries{隐马尔可夫模型}}\index{隐马尔可夫模型}（Hidden Markov Model，HMM）\index{Hidden Markov Model}\upcite{1996Hidden}、{\small\sffamily\bfseries{条件随机场}}\index{条件随机场}（Conditional Random Fields，CRFs）\index{Conditional Random Fields}\upcite{lafferty2001conditional}、{\small\sffamily\bfseries{最大熵}}\index{最大熵}（Maximum Entropy，ME）\index{Maximum Entropy}模型\upcite{kapur1989maximum}和{\small\sffamily\bfseries{支持向量机}}\index{支持向量机}（Support Vector Machine，SVM）\index{Support Vector Machine}\upcite{1998Support}等。此外，近些年深度学习的兴起也给命名实体识别带来了新的思路\upcite{2011Natural}。而命名实体识别也成为了验证机器学习方法有效性的重要任务之一。本节将对序列标注中几类基础的方法进行介绍。其中会涉及概率图模型、统计分类模型等方法。特别是统计分类的概念，在后续章节中也会被使用到。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{基于特征的统计学习} \label{sec3:feature}

\parinterval 基于特征的统计学习是解决序列标注的有效方法之一。这种方法中，系统研发人员通过定义不同的特征来完成对问题的描述，之后利用统计模型完成对这些特征的某种融合，并得到最终的预测结果。

\parinterval 在开始介绍序列标注模型之前，先来看一下统计学习所涉及的重要概念\ \dash \ {\small\sffamily\bfseries{特征}}\index{特征}（Feature）\index{Feature}。简单来说，特征是指能够反映事物在某方面表现或行为的一种属性，如现实生活中小鸟的羽毛颜色、喙的形状、翼展长度等就是小鸟的特征；命名实体识别任务中的每个词的词根、词性和上下文组合也可以被看做是识别出命名实体可以采用的特征。

\parinterval 从统计建模的角度看，特征的形式可以非常灵活。比如，可以分为连续型特征和离散型特征，前者通常用于表示取值蕴含数值大小关系的信息，如人的身高和体重，后者通常用于表示取值不蕴含数值大小关系的信息，如人的性别。正是由于这种灵活性，系统开发者可以通过定义多样的特征来从多个不同的角度对目标问题进行建模。而这种设计特征的过程也被称作{\small\sffamily\bfseries{特征工程}}\index{特征工程}（Feature Engineering）\index{Feature Engineering}。

\parinterval 设计更好的特征也成为了很多机器学习方法的关键。通常有两个因素需要进行考虑：

\begin{itemize}
\vspace{0.5em}
\item {\small\sffamily\bfseries{样本在这些特征上的差异度}}，即特征对于样本的区分能力。比如，可以考虑优先选择样本特征值方差较大即区分能力强的特征\footnote{方差如果很小，意味着样本在这个特征上基本上没有差异，那么这个特征对于样本的区分并没有什么用。}；
\vspace{0.5em}
\item {\small\sffamily\bfseries{特征与任务目标的相关性}}。优先选择相关性高的特征。
\vspace{0.5em}
\end{itemize}

\parinterval 回到命名实体识别任务上来。对于输入的每个单词，可以将其表示为一个单词和对应的{\small\sffamily\bfseries{词特征}}\index{词特征}（Word Feature）\index{Word Feature}的组合，记作$<w, f>$。通过这样的表示，就可以将原始的单词序列转换为词特征序列。命名实体识别中的特征可以分为两大类，一种是单词对应各个标签的特征，另一种是标签之间组合的特征。常用的特征包括词根、词缀、词性或者标签的固定搭配等。表\ref{tab:3.3-1}展示了命名实体识别任务中一些典型的特征。

\begin{table}[htp]{
\begin{center}
\caption{命名实体识别中常用的特征}
{
\begin{tabular}{c|c|c}
特征名 & 示例文本 & 释义 \\
\hline
\rule{0pt}{10pt} LocSuffix & 沈阳\underline{市} & 地名后缀 \\
\rule{0pt}{10pt} FourDigitYear & \underline{2020} & 四位数年份 \\
\rule{0pt}{10pt} OtherDigit & \underline{202020} & 其他数字 \\
\rule{0pt}{10pt} NamePrefix & \underline{张}三 & 姓名前缀 \\
\rule{0pt}{10pt} ShortName & \underline{东大}成立120周年 & 缩略词 \\
\end{tabular}
\label{tab:3.3-1}
}
\end{center}
}\end{table}

\parinterval 在相当长的一段时期内，基于特征工程的方法都是自然语言处理领域的主流范式。虽然深度学习技术的进步使得系统研发人员可以逐步摆脱繁重的特征设计工作，但是很多传统的模型和方法在今天仍然被广泛使用。比如，在当今最先进的序列标注模型中\upcite{lample2016neural}，条件随机场模型仍然是一个主要部件，本节即将对其进行介绍。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{基于概率图模型的方法}

\parinterval {\small\sffamily\bfseries{概率图模型}}\index{概率图模型}（Probabilistic Graphical Model）\index{Probabilistic Graphical Model}是使用图表示变量及变量间概率依赖关系的方法。在概率图模型中，可以根据可观测变量推测出未知变量的条件概率分布等信息。如果把序列标注任务中的输入序列看作观测变量，而把输出序列看作需要预测的未知变量，那么就可以把概率图模型应用于命名实体识别等序列标注任务。

%----------------------------------------------------------------------------------------
%    NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------

\subsubsection{1. 隐马尔可夫模型}

\parinterval 隐马尔可夫模型是一种经典的序列模型\upcite{Baum1966Statistical,baum1970maximization,1996Hidden}。它在语音识别、自然语言处理的很多领域得到了广泛的应用。隐马尔可夫模型的本质就是概率化的马尔可夫过程，这个过程隐含着状态间转移和可见状态生成的概率。

\parinterval 这里用一个简单的“抛硬币”游戏来对这些概念进行说明：假设有三枚质地不同的硬币$A$、$B$、$C$，已知这三个硬币抛出正面的概率分别为0.3、0.5、0.7，在游戏中，游戏发起者在上述三枚硬币中选择一枚硬币上抛，每枚硬币被挑选到的概率可能会受上次被挑选的硬币的影响，且每枚硬币正面向上的概率都各不相同。不停的重复挑选硬币、上抛硬币的过程，会得到一串硬币的正反序列，例如：抛硬币6次，得到：正正反反正反。游戏挑战者根据硬币的正反序列，猜测每次选择的究竟是哪一枚硬币。

\parinterval 在上面的例子中，每次挑选并上抛硬币后得到的“正面”或“反面”即为“可见状态”，再次挑选并上抛硬币会获得新的“可见状态”，这个过程即为“状态的转移”，经过6次反复挑选上抛后得到的硬币正反序列叫做可见状态序列，由每个回合的可见状态构成。此外，在这个游戏中还暗含着一个会对最终“可见状态序列”产生影响的“隐含状态序列”\ \dash \ 每次挑选的硬币形成的序列，例如$CBABCA$。

\parinterval 实际上，隐马尔科夫模型在处理序列问题时的关键依据是两个至关重要的概率关系，并且这两个概率关系也始终贯穿于“抛硬币”的游戏中。一方面，隐马尔可夫模型用{\small\sffamily\bfseries{发射概率}}\index{发射概率}（Emission Probability）\index{Emission Probability}来描述隐含状态和可见状态之间存在的输出概率（即$A$、$B$、$C$抛出正面的输出概率为0.3、0.5、0.7），同样的，隐马尔可夫模型还会描述系统隐含状态的{\small\sffamily\bfseries{转移概率}}\index{转移概率}（Transition Probability）\index{Transition Probability}，在这个例子中，$A$的下一个状态是$A$、$B$、$C$的概率都是1/3，$B$、$C$的下一个状态是$A$、$B$、$C$的转移概率也同样是1/3。图\ref{fig:3.3-2}展示了在“抛硬币”游戏中的转移概率和发射概率，它们都可以被看做是条件概率矩阵。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-transition-prob-and-launch-prob-in-coin-toss-game}
\caption{“抛硬币”游戏中的转移概率和发射概率}
\label{fig:3.3-2}
\end{figure}
%-------------------------------------------

\parinterval 由于隐含状态序列之间存在转移概率，并且隐马尔可夫模型中隐含状态和可见状态之间存在着发射概率，因此根据可见状态的转移猜测隐含状态序列并非无迹可循。图\ref{fig:3.3-3}描述了如何使用隐马尔可夫模型来根据“抛硬币”结果推测挑选的硬币序列。可见，通过隐含状态之间的联系（绿色方框及它们之间的连线）可以对有序的状态进行描述，进而得到隐含状态序列所对应的可见状态序列（红色圆圈）。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-example-of-hmm-in-coin-toss}
\caption{抛硬币的隐马尔可夫模型实例}
\label{fig:3.3-3}
\end{figure}
%-------------------------------------------

\parinterval 从统计建模的角度看，上述过程本质上是在描述隐含状态和可见状态出现的联合概率。这里，用$\seq{x}=(x_1,...,x_m)$表示可见状态序列，用$\seq{y}=(y_1,...,y_m)$表示隐含状态序列。（一阶）隐马尔可夫模型假设：

\begin{itemize}
\vspace{0.5em}
\item 当前位置的隐含状态仅与前一个位置的隐含状态相关，即$y_i$仅与$y_{i-1}$相关；
\vspace{0.5em}
\item 当前位置的可见状态仅与当前位置的隐含状态相关，即$x_i$仅与$y_i$相关。
\vspace{0.5em}
\end{itemize}

于是，联合概率$\funp{P}(\seq{x},\seq{y})$可以被定义为：
\begin{eqnarray}
\funp{P}(\seq{x},\seq{y}) & = & \funp{P}(\seq{x}|\seq{y})\funp{P}(\seq{y}) \nonumber \\
                                                   & = & \funp{P}(x_1,...,x_m|y_1,...,y_m) \funp{P}(y_1,...,y_m) \nonumber \\
                                                   & = & \prod_{i=1}^{m} \funp{P}(x_i|x_1,...,x_{i-1},y_1,...,y_m) \prod_{i=1}^{m} \funp{P}(y_i | y_{i-1}) \nonumber \\
                                                   & = & \prod_{i=1}^{m} \funp{P}(x_i|y_i) \prod_{i=1}^{m} \funp{P}(y_i | y_{i-1}) \nonumber \\
                                                   & = & \prod_{i=1}^{m} \funp{P}(x_i|y_i) \funp{P}(y_i | y_{i-1})  \label{eq:joint-prob-xy}
\end{eqnarray}

\noindent 这里，$y_{0}$表示一个虚拟的隐含状态。这样，可以定义$\funp{P}(y_1|y_{0}) \equiv \funp{P}(y_1)$，它表示起始隐含状态出现的概率。隐马尔可夫模型的假设也大大化简了问题，因此可以通过式\eqref{eq:joint-prob-xy}很容易地计算隐含状态序列和可见状态序列出现的概率。值得注意的是，发射概率和转移概率都可以被看作是描述序列生成过程的“特征”。但是，这些“特征”并不是随意定义的，而是符合问题的概率解释。而这种基于事件发生的逻辑所定义的概率生成式模型，通常可以被看作是一种{\small\sffamily\bfseries{生成式模型}}\index{生成式模型}（Generative Model）\index{Generative Model}。

\parinterval 一般来说，隐马尔可夫模型中包含下面三个问题：

\begin{itemize}
\vspace{0.5em}
\item {\small\sffamily\bfseries{隐含状态序列的概率计算}}，即给定模型（转移概率和发射概率），根据可见状态序列（抛硬币的结果）计算在该模型下得到这个结果的概率，这个问题的求解需要用到前后向算法\upcite{baum1970maximization}。
\vspace{0.5em}
\item {\small\sffamily\bfseries{参数学习}}，即给定硬币种类（隐含状态数量），根据多个可见状态序列（抛硬币的结果）估计模型的参数（转移概率），这个问题的求解需要用到EM算法\upcite{1977Maximum}。
\vspace{0.5em}
\item {\small\sffamily\bfseries{解码}}，即给定模型（转移概率和发射概率）和可见状态序列（抛硬币的结果），根据可见状态序列，计算最可能出现的隐含状态序列，这个问题的求解需要用到基于动态规划的方法，通常也被称作{\small\sffamily\bfseries{维特比算法}}\index{维特比算法}（Viterbi Algorithm）\index{Viterbi Algorithm}\upcite{1967Error}。
\vspace{0.5em}
\end{itemize}

\parinterval 隐马尔可夫模型处理序列标注问题的基本思路是：

\begin{itemize}
\vspace{0.5em}
\item 第一步：根据可见状态序列（输入序列）和其对应的隐含状态序列（标记序列）样本，估算模型的转移概率和发射概率；
\vspace{0.5em}
\item 第二步：对于给定的可见状态序列，预测概率最大的隐含状态序列，比如，根据输入的词序列预测最有可能的命名实体标记序列
\vspace{0.5em}
\end{itemize}

\parinterval 一种简单的办法是使用相对频次估计得到转移概率和发射概率估计值。令$x_i$表示第$i$个位置的可见状态，$y_i$表示第$i$个位置的隐含状态，$\funp{P}(y_i|y_{i-1})$表示第$i-1$个位置到第$i$个位置的状态转移概率，$\funp{P}(x_i|y_{i}) $表示第$i$个位置的发射概率，于是有：
\begin{eqnarray}
\funp{P}(y_i|y_{i-1}) &=& \frac{{c}(y_{i-1},y_i)}{{c}(y_{i-1})}
\label{eq:3.3-1}\\
\funp{P}(x_i|y_{i}) &=& \frac{{c}(x_i,y_i)}{{c}(y_i)}
\label{eq:3.3-2}
\end{eqnarray}

\noindent 其中，${c}(\cdot)$统计训练集中某种现象出现的次数。

\parinterval 在获得转移概率和发射概率的基础上，对于一个句子进行命名实体识别可以被描述为：在观测序列$\seq{x}$（可见状态，即输入的词序列）的条件下，最大化标签序列$\seq{y}$（隐含状态，即标记序列）的概率，即：
\begin{eqnarray}
\hat{\seq{y}} &=& \arg\max_{\seq{y}}\funp{P}(\seq{y}|\seq{x})
\label{eq:3.3-3}
\end{eqnarray}

\parinterval 根据贝叶斯定理，该概率被分解为$\funp{P}(\seq{y}|\seq{x})=\frac{\funp{P}(\seq{x},\seq{y})}{\funp{P}(\seq{x})}$，其中$\funp{P}(\seq{x})$是固定概率，因为$\seq{x}$在这个过程中是确定的不变量。因此只需考虑如何求解分子，即将求条件概率$\funp{P}(\seq{y}|\seq{x})$的问题转化为求联合概率$\funp{P}(\seq{y},\seq{x})$的问题：
\begin{eqnarray}
\hat{\seq{y}} &=& \arg\max_{\seq{y}}\funp{P}(\seq{x},\seq{y}) \label{eq:markov-sequence-argmax}
\label{eq:3.3-4}
\end{eqnarray}

\parinterval 将式\eqref{eq:joint-prob-xy}带入式\eqref{eq:markov-sequence-argmax}可以得到最终计算公式，如下：
\begin{eqnarray}
\hat{\seq{y}} &=& \arg\max_{\seq{y}}\prod_{i=1}^{m}\funp{P}(x_i|y_i)\funp{P}(y_i|y_{i-1})
\label{eq:3.3-5}
\end{eqnarray}

\parinterval 图\ref{fig:3.3-4}展示了基于隐马尔可夫模型的命名实体识别模型。实际上，这种描述序列生成的过程也可以被应用于机器翻译，在第五章还将看到隐马尔可夫模型在翻译建模中的应用。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-ner-based-on-hmm}
\caption{基于隐马尔可夫模型的命名实体识别}
\label{fig:3.3-4}
\end{figure}
%-------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------

\subsubsection{2. 条件随机场}

\parinterval 隐马尔可夫模型有一个很强的假设：一个隐含状态出现的概率仅由上一个隐含状态决定。这个假设也会带来一些问题，举个例子：在某个隐马尔可夫模型中，隐含状态集合为\{$A, B, C, D$\}，可见状态集合为\{$T, F$\}，其中隐含状态$A$可能的后继隐含状态集合为\{$A, B$\}，隐含状态$B$可能的后继隐含状态集合为\{$A, B, C, D$\}，于是有：
\begin{eqnarray}
\funp{P}(A|A)+\funp{P}(A|B) & = & 1 \label{eq:3.3-6} \\
\funp{P}(A|B)+\funp{P}(B|B)+\funp{P}(C|B)+\funp{P}(D|B) & = & 1 \label{eq:3.3-7}
\end{eqnarray}

\noindent 其中，$\funp{P}(b|a)$表示由状态$a$转移到状态$b$的概率，由于式\eqref{eq:3.3-6}中的分式数量少于式\eqref{eq:3.3-7}，这就导致在统计中获得的$\funp{P}(A|A)$、$\funp{P}(A|B)$的值很可能会比$\funp{P}(A|B)$、$\funp{P}(B|B)$、$\funp{P}(C|B)$、$\funp{P}(D|B)$要大。

\parinterval 图\ref{fig:3.3-5}展示了一个具体的例子，有一个可见状态序列$T F F T$，假设初始隐含状态是$A$，图中线上的概率值是对应的转移概率与发射概率的乘积，比如图中隐含状态$A$开始，下一个隐含状态是$A$且可见状态是$F$的概率是0.45，下一个隐含状态是$B$且可见状态是$F$的概率是0.55。图中可以看出，由于有较大的值，当可见状态序列为$T F F T$时，隐马尔可夫计算出的最有可能的隐含状态序列为$A A A A$。但是如果对训练集进行统计可能会发现，当可见序列为$T F F T$ 时，对应的隐含状态是$A A A A$的概率可能是比较大的，但也可能是比较小的。这个例子中出现预测偏差的主要原因是：由于比其他状态转移概率要大得多，隐含状态的预测一直停留在状态$A$。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-example-of-hmm}
\caption{隐马尔可夫实例}
\label{fig:3.3-5}
\end{figure}
%-------------------------------------------

\parinterval 上述现象也被称作{\small\sffamily\bfseries{标注偏置}}\index{标注偏置}（Label Bias）\index{Label Bias}。条件随机场模型在隐马尔可夫模型的基础上，解决了这个问题\upcite{lafferty2001conditional}。在条件随机场模型中，以全局范围的统计归一化代替了隐马尔可夫模型中的局部归一化。除此之外，条件随机场模型中并非使用概率计算而是特征函数的方式对可见状态序列$\seq{x}$对应的隐含状态序列$\seq{y}$的概率进行计算。

\parinterval 条件随机场中一般有若干个特征函数，都是经过设计的、能够反映序列规律的一些二元函数\footnote{二元函数的函数值一般非1即0}，并且每个特征函数都有其对应的权重$\lambda$。特征函数一般由两部分组成：能够反映隐含状态序列之间转移规则的转移特征$t(y_{i-1},y_i,\seq{x},i)$和状态特征$s(y_i,\seq{x},i)$。其中$y_i$和$y_{i-1}$分别是位置$i$和前一个位置的隐含状态，$\seq{x}$则是可见状态序列。转移特征$t(y_{i-1},y_i,\seq{x},i)$反映了两个相邻的隐含状态之间的转换关系，而状态特征$s(y_i,\seq{x},i)$则反映了第$i$个可见状态应该对应什么样的隐含状态，这两部分共同组成了一个特征函数$F(y_{i-1},y_i,\seq{x},i)$，即
\begin{eqnarray}
F(y_{i-1},y_i,\seq{x},i) & = & t(y_{i-1},y_i,\seq{x},i)+s(y_i,\seq{x},i)
\label{eq:3.3-8}
\end{eqnarray}
	
\parinterval 实际上，基于特征函数的方法更像是对隐含状态序列的一种打分：根据人为设计的模板（特征函数），测试隐含状态之间的转换以及隐含状态与可见状态之间的对应关系是否符合这种模板。在处理序列问题时，假设可见状态序列$\seq{x}$的长度和待预测隐含状态序列$\seq{y}$的长度均为$m$，且共设计了$k$个特征函数，则有：
\begin{eqnarray}
\funp{P}(\seq{y}|\seq{x}) & = & \frac{1}{Z(\seq{x})}\exp(\sum_{i=1}^m\sum_{j=1}^{k}\lambda_{j}F_{j}(y_{i-1},y_i,\seq{x},i))
\label{eq:3.3-9}
\end{eqnarray}

\parinterval 公式\eqref{eq:3.3-9}中的$Z(x)$即为上面提到的实现全局统计归一化的归一化因子，其计算方式为：
\begin{eqnarray}
Z(\seq{x})&=&\sum_{\seq{y}}\exp(\sum_{i=1}^m\sum_{j=1}^k\lambda_{j}F_{j}(y_{i-1},y_i,\seq{x},i))
\label{eq:3.3-10}
\end{eqnarray}

\parinterval 由公式\eqref{eq:3.3-10}可以看出，归一化因子的求解依赖于整个可见状态序列和每个位置的隐含状态，因此条件随机场模型中的归一化是一种全局范围的归一化方式。图\ref{fig:3.3-6}为条件随机场模型处理序列问题的示意图。

%----------------------------------------------
\begin{figure}[htp]
\centering
\input{./Chapter3/Figures/figure-crf-to-deal-with-sequence-problems}
\caption{条件随机场模型处理序列问题}
\label{fig:3.3-6}
\end{figure}
%-------------------------------------------

\parinterval 虽然，式\eqref{eq:3.3-9}和式\eqref{eq:3.3-10}的表述相较于隐马尔可夫模型更加复杂，但是其实现有非常高效的方式。比如，可以使用动态规划方法完成整个条件随机场模型的计算\upcite{lafferty2001conditional}。

\parinterval 条件随机场模型处理命名实体识别任务时，可见状态序列对应着文本内容，隐含状态序列对应着待预测的标签。对于命名实体识别任务，需要单独设计若干适合命名实体识别任务的特征函数。例如在使用BIOES标准标注命名实体识别任务时，标签“B-ORG”\footnote{ORG表示机构实体}后面的标签必然是“I-ORG”或是“E-ORG”，而不可能是“O”，针对此规则可以设计相应特征函数。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{基于分类器的方法}

\parinterval 基于概率图的模型将序列表示为有向图或无向图，如图\ref{fig:3.3-7}(a)、(b)所示。这种方法增加了建模的复杂度。既然要得到每个位置的类别输出，另一种更加直接的方法是使用分类器对每个位置进行独立预测。分类器是机器学习中广泛使用的方法，它可以根据输入自动地对类别进行预测。如图\ref{fig:3.3-7}(c)所示，对于序列标注任务，分类器把每一个位置所对应的所有特征看作是输入，而把这个位置对应的标签看作输出。从这个角度说，隐马尔可夫模型等方法实际上也是在进行一种“分类”操作，只不过这些方法考虑了不同位置输出（或隐含状态）之间的依赖。

\parinterval 值得注意的是分类模型可以被应用于序列标注之外的很多任务，在后面的章节中还会看到，机器翻译中的很多模块也借鉴了统计分类的思想。其中使用到的基础数学模型和特征定义形式，与这里提到的分类器本质上是一样的。

%----------------------------------------------
\begin{figure}[htp]
\centering
\begin{tabular}{l l l}
\subfigure[\small{HMM处理序列标注}]{\input{./Chapter3/Figures/figure-process-sequence-labeling-by-hmm}} & \subfigure[\small{CRF处理序列标注}]{\input{./Chapter3/Figures/figure-process-sequence-labeling-by-crf}} & \subfigure[\small{分类模型处理序列标注}]{\input{./Chapter3/Figures/figure-process-sequence-labeling-by-classfication}}
\end{tabular}
\caption{HMM、CRF、分类算法三种方法对比}
\label{fig:3.3-7}
\end{figure}
%-------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------

\subsubsection{1. 分类任务与分类器}

\parinterval 无论在日常生活中还是在研究工作中，都会遇到各种各样的分类问题，例如挑选西瓜时需要区分“好瓜”和“坏瓜”、编辑看到一篇新闻稿件时要对稿件进行分门别类。事实上，在机器学习中，对“分类任务”的定义会更宽泛而并不拘泥于“类别”的概念，在对样本进行预测时，只要预测标签集合是有限的且预测标签是离散的，就可认定其为分类任务。

\parinterval 具体来说，分类任务目标是训练一个可以根据输入数据预测离散标签的{\small\sffamily\bfseries{分类器}}\index{分类器}（Classifier\index{Classifier}），也可称为分类模型。在有监督的分类任务中\footnote{与之相对应的，还有无监督、半监督分类任务，不过这些内容不是本书讨论的重点。读者可以参看参考文献\upcite{周志华2016机器学习,李航2019统计学习方法}对相关概念进行了解。}，训练数据集合通常由形似$({\mathbi{x}}^{[i]},y^{[i]})$的带标注数据构成，${\mathbi{x}}^{[i]}=(x^{[i]}_1,\ldots,x^{[i]}_k)$作为分类器的输入数据（通常被称作一个训练样本），其中$x^{[i]}_j$表示样本$\mathbi{x}^{[i]}$的第$j$个特征；$y^{[i]}$作为输入数据对应的{\small\sffamily\bfseries{标签}}\index{标签}（Label）\index{Label}，反映了输入数据对应的“类别”。若标签集合大小为$n$，则分类任务的本质是通过对训练数据集合的学习，建立一个从$k$ 维样本空间到$n$维标签空间的映射关系。更确切地说，分类任务的最终目标是学习一个条件概率分布$\funp{P}(y|{\mathbi{x}})$，这样对于输入${\mathbi{x}}$可以找到概率最大的$y$作为分类结果输出。

\parinterval 与概率图模型一样，分类模型中也依赖特征定义。其定义形式与\ref{sec3:feature}节的描述一致，这里不再赘述。分类任务一般根据类别数量分为二分类任务和多分类任务，二分类任务是最经典的分类任务，只需要对输出进行非零即一的预测。多分类任务则可以有多种处理手段，比如，可以将其“拆解”为多个二分类任务求解，或者直接让模型输出多个类别中的一个。在命名实体识别中，往往会使用多类别分类模型。比如，在BIO标注下，有三个类别（B、I和O）。一般来说，类别数量越大分类的难度也越大。比如，BIOES标注包含5个类别，因此使用同样的分类器，它要比BIO标注下的分类问题难度大。此外，更多的类别有助于准确的刻画目标问题。因此在实践中需要在类别数量和分类难度之间找到一种平衡。

\parinterval 在机器翻译和语言建模中也会遇到类似的问题，比如，生成单词的过程可以被看做是一个分类问题，类别数量就是词表的大小。显然，词表越大可以覆盖更多的单词和更多种类的单词形态学变化，但是过大的词表里会包含很多低频词，其计算复杂度会显著增加。然而，过小的词表又无法包含足够多的单词。因此，在设计这类系统的时候对词表大小的选择（类别数量的选择）是十分重要的，往往要通过大量的实验得到最优的设置。

%----------------------------------------------------------------------------------------
%    NEW SUBSUB-SECTION
%----------------------------------------------------------------------------------------

\subsubsection{2. 经典的分类模型}

\parinterval 经过多年的发展，研究者提出了很多分类模型。由于篇幅所限，本书无法一一列举这些模型，这里仅列出了部分经典的模型。关于分类模型更全面的介绍可以参考相关文献\upcite{harrington2013机器学习实战,李航2019统计学习方法}。

\begin{itemize}
\vspace{0.5em}
\item{\small\sffamily\bfseries{$K$-近邻分类算法}} 。$K$-近邻分类算法通过计算不同特征值之间的距离进行分类，这种方法适用于可以提取到数值型特征\footnote{即可以用数值大小对某方面特征进行衡量。}的分类问题。该方法的基本思想为：将提取到的特征分别作为坐标轴，建立一个$k$维坐标系（对应特征数量为$k$的情况），此时每个样本都将成为该$k$维空间的一个点，将未知样本与已知类别样本的空间距离作为分类依据进行分类，比如，考虑与输入样本最近的$K$个样本的类别进行分类。
\vspace{0.5em}
\item {\small\sffamily\bfseries{支持向量机}}。支持向量机是一种二分类模型，其思想是通过线性超平面将不同输入划分为正例和负例，并使线性超平面与不同输入的距离都达到最大。与$K$-近邻分类算法类似，支持向量机也适用于可以提取到数值型特征的分类问题。
\vspace{0.5em}
\item {\small\sffamily\bfseries{最大熵模型}}。最大熵模型是根据最大熵原理提出的一种分类模型，其基本思想是：以在训练数据集中学习到的经验知识作为一种“约束”，并在符合约束的前提下，在若干合理的条件概率分布中选择“使条件熵最大”的模型。
\vspace{0.5em}
\item {\small\sffamily\bfseries{决策树分类算法}}。决策树分类算法是一种基于实例的归纳学习方法：将样本中某些决定性特征作为决策树的节点，根据特征表现进行对样本划分，最终根节点到每个叶子节点均形成一条分类的路径规则。这种分类方法适用于可以提取到离散型特征\footnote{即特征值是离散的。}的分类问题。
\vspace{0.5em}
\item {\small\sffamily\bfseries{朴素贝叶斯分类算法}}。朴素贝叶斯算法是以贝叶斯定理为基础并且假设特征之间相互独立的方法，以特征之间相互独立作为前提假设，学习从输入到输出的联合概率分布，并以后验概率最大的输出作为最终类别。
\vspace{0.5em}
\end{itemize}

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{句法分析}

\parinterval 前面已经介绍了什么叫做“词”以及如何对分词问题进行统计建模。同时，也介绍了如何对多个单词构成的命名实体进行识别。无论是分词还是命名实体识别都是句子浅层信息的一种表示。对于一个自然语言句子来说，它更深层次的结构信息可以通过更完整的句法结构来描述，而句法信息也是机器翻译和自然语言处理其他任务中常用的知识之一。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{句法树}

\parinterval {\small\sffamily\bfseries{句法}}\index{句法}（Syntax）\index{Syntax}是研究句子的每个组成部分和它们之间的组合方式。一般来说，句法和语言是相关的，比如，英文是主谓宾结构，而日语是主宾谓结构，因此不同的语言也会有不同的句法描述方式。自然语言处理领域最常用的两种句法分析形式是{\small\sffamily\bfseries{短语结构句法分析}}\index{短语结构句法分析}（Phrase Structure Parsing）\index{Phrase Structure Parsing}和{\small\sffamily\bfseries{依存句法分析}}\index{依存句法分析}（Dependency Parsing）\index{Dependency Parsing}。图\ref{fig:3.4-1}展示了这两种的句法表示形式的实例。其中，左侧是短语结构树，它描述的是短语的结构功能，比如“吃”是动词（记为VV），“鱼”是名词（记为NN），“吃/鱼”组成动词短语，这个短语再与“喜欢”这一动词组成新的动词短语。短语结构树的每个子树都是一个句法功能单元，比如，子树VP(VV(吃) NN(鱼))就表示了“吃/鱼”这个动词短语的结构，其中子树根节点VP是句法功能标记。短语结构树利用嵌套的方式描述了语言学的功能，短语结构树中，每个词都有词性(或词类)，不同的词或者短语可以组成名动结构、动宾结构等语言学短语结构，短语结构句法分析一般也被称为{\small\sffamily\bfseries{成分句法分析}}\index{成分句法分析}（Constituency Parsing）或{\small\sffamily\bfseries{完全句法分析}}\index{完全句法分析}（Full Parsing）\index{Full Parsing}。

\parinterval 图\ref{fig:3.4-1}右侧展示的是另一种句法结构，被称作依存句法树。依存句法树表示了句子中单词和单词之间的依存关系。比如，从这个例子可以了解，“猫”依赖“喜欢”，“吃”依赖“喜欢”，“鱼”依赖“吃”。

%----------------------------------------------
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure-phrase-structure-tree-and-dependency-tree}
    \caption{短语结构树(左)和依存树(右)}
    \label{fig:3.4-1}
\end{figure}
%---------------------------

\parinterval 短语结构树和依存句法树的结构和功能有很大不同。短语结构树的叶子节点是单词，中间节点是词性或者短语句法标记。在短语结构句法分析中，通常把单词称作{\small\sffamily\bfseries{终结符}}\index{终结符}（Terminal）\index{Terminal}，把词性称为{\small\sffamily\bfseries{预终结符}}\index{预终结符}（Pre-terminal）\index{Pre-terminal}，而把其他句法标记称为{\small\sffamily\bfseries{非终结符}}\index{非终结符}（Non-terminal）\index{Non-terminal}。依存句法树没有预终结符和非终结符，所有的节点都是句子里的单词，通过不同节点间的连线表示句子中各个单词之间的依存关系。每个依存关系实际上都是有方向的，头和尾分别指向“接受”和“发出”依存关系的词。依存关系也可以进行分类，例如，图\ref{fig:3.4-1}中的对每个依存关系的类型都有一个标记，这也被称作是有标记的依存句法分析。如果不生成这些标记，这样的句法分析被称作无标记的依存句法分析。

\parinterval 虽然短语结构树和依存树的句法表现形式有很大不同，但是它们在某些条件下能相互转化。比如，可以使用启发性规则将短语结构树自动转化为依存树。从应用的角度，依存句法分析由于形式更加简单，而且直接建模词语之间的依赖，因此在自然语言处理领域中受到很多关注。在机器翻译中，无论是哪种句法树结构，都已经被证明会对机器翻译系统产生帮助。特别是短语结构树，在机器翻译中的应用历史更长，研究更为深入，因此本节将会以短语结构句法分析为例介绍句法分析的相关概念。

\parinterval 而句法分析到底是什么呢？简单的理解，句法分析就是在小学语文课程中学习的句子成分的分析，以及对句子中各个成分内部、外部关系的判断。更规范一些的定义，可以参照百度百科和维基百科关于句法分析的解释。

%-------------------------------------------
\begin{definition} 句法分析

句法分析就是指对句子中的词语语法功能进行分析。
\begin{flushright}——百度百科\end{flushright}

在自然语言或者计算机语言中，句法分析是利用形式化的文法规则对一个符号串进行分析的过程。
\begin{flushright}——维基百科（译文）\end{flushright}
\end{definition}
%-------------------------------------------

\parinterval 上面的定义中，句法分析包含三个重要的概念：

\begin{itemize}
\vspace{0.5em}
\item 形式化的文法：描述语言结构的定义，由文法规则组成。
\vspace{0.5em}
\item 符号串：在本节中，符号串就是指词串，由前面提到的分词系统生成。
\vspace{0.5em}
\item 分析：使用形式文法对符号串进行分析的具体方法，在这里指实现分析的计算机算法。
\vspace{0.5em}
\end{itemize}

\parinterval 以上三点是实现一个句法分析器的要素，本节的后半部分会对相关的概念和技术方法进行介绍。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{上下文无关文法}

\parinterval 句法树是对句子的一种抽象，这种树形结构表达了一种对句子结构的归纳过程，比如，从树的叶子开始，把每一个树节点看作一次抽象，最终形成一个根节点。那这个过程如何用计算机来实现呢？这就需要使用到形式文法。

\parinterval 形式文法是分析自然语言的一种重要工具。根据乔姆斯基的定义\upcite{chomsky1957syntactic}，形式文法分为四种类型：无限制文法（0型文法）、上下文有关文法（1型文法）、上下文无关文法（2型文法）和正规文法（3型文法）。不同类型的文法有不同的应用，比如，正规文法可以用来描述有限状态自动机，因此也会被使用在语言模型等系统中。对于短语结构句法分析问题，常用的是{\small\sffamily\bfseries{上下文无关文法}}\index{上下文无关文法}（Context-free Grammar）\index{Context-free Grammar}。上下文无关文法的具体形式如下：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 上下文无关文法

一个上下文无关文法可以被视为一个系统$G=<N,\varSigma,R,S>$，其中

\begin{itemize}
\vspace{0.5em}
\item $N$为一个非终结符集合；
\vspace{0.5em}
\item $\varSigma$ 为一个终结符集合；
\vspace{0.5em}
\item $R$为一个规则（产生式）集合，每条规则 $r \in R$的形式为$X \to Y_1Y_2...Y_n$，其中$X \in N$, $Y_i \in N \cup \varSigma$；
\vspace{0.5em}
\item $S$为一个起始符号集合且$S \subseteq N$。
\vspace{0.5em}
\end{itemize}
\end{definition}
%-------------------------------------------

\parinterval 举例说明，假设有上下文无关文法$G=<N,\varSigma,R,S>$，可以用它描述一个简单汉语句法结构。其中非终结符集合为不同的汉语句法标记
\begin{eqnarray}
N&=&\{\textrm{NN},\textrm{VV},\textrm{NP},\textrm{VP},\textrm{IP}\} \nonumber
\label{eq:3.4-1}
\end{eqnarray}

\noindent 这里，\textrm{NN}代表名词，\textrm{VV}代表动词，\textrm{NP}代表名词短语，\textrm{VP}代表动词短语，\textrm{IP}代表单句。进一步，把终结符集合定义为
\begin{eqnarray}
\varSigma &=& \{\text{猫,喜欢,吃,鱼}\} \nonumber
\label{eq:3.4-2}
\end{eqnarray}

再定义起始符集合为
\begin{eqnarray}
S&=&\{\textrm{IP}\} \nonumber
\label{eq:3.4-3}
\end{eqnarray}

\parinterval 最后，文法的规则集定义图\ref{fig:3.4-2}所示（其中$r_i$为规则的编号）。这个文法蕴含了不同“层次”的句法信息。比如，规则$r_1$、$r_2$、$r_3$和$r_4$表达了词性对单词的抽象；规则$r_6$、$r_7$和$r_8$是表达了短语结构的抽象，其中，规则$r_8$描述了汉语中名词短语(主语)+动词短语(谓语)的结构。在实际应用中，像$r_8$这样的规则可以覆盖很大的片段（试想一下一个包含50个词的主谓结构的句子，可以使用$r_8$进行描述）。

%----------------------------------------------
\begin{figure}[htp]
    \centering
 \input{./Chapter3/Figures/figure-rules-of-grammar}
 \caption{一个示例文法的规则集}
     \label{fig:3.4-2}
 \end{figure}
%---------------------------

\parinterval 上下文无关文法的规则是一种{\small\sffamily\bfseries{产生式规则}}\index{产生式规则}（Production Rule）\index{Production Rule}，形如$\alpha \to \beta $，它表示把规则左端的非终结符$\alpha$替换为规则右端的符号序列$\beta$。 通常，$\alpha$被称作规则的{\small\sffamily\bfseries{左部}}\index{左部}（Left-hand Side）\index{Left-hand Side}，$\beta$被称作规则的{\small\sffamily\bfseries{右部}}\index{右部}（Right-hand Side）\index{Right-hand Side}。使用右部$\beta$ 替换左部$\alpha$ 的过程也被称作规则的使用，而这个过程的逆过程称为规约。规则的使用可以如下定义：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 上下文无关文法规则的使用

一个符号序列$u$可以通过使用规则$r$替换其中的某个非终结符，并得到符号序列$v$，于是$v$是在$u$上使用$r$的结果，记为$u \overset{r}{\Rightarrow} v$：
\begin{center}
\input{./Chapter3/Figures/figure-usage-of-regulation}
\end{center}
\end{definition}
%-------------------------------------------

\parinterval 给定起始非终结符，可以不断地使用规则，最终生成一个终结符串，这个过程也被称为{\small\sffamily\bfseries{推导}}\index{推导}（Derivation）\index{Derivation}。形式化的定义为：

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 推导

给定一个文法$G=<N,\varSigma,R,S>$，对于一个字符串序列$s_0,s_1,...,s_n$和规则序列$r_1,r_2,...,r_n$，满足

\vspace{-0.5em}
\begin{displaymath}
s_0 \overset{r_1}{\Rightarrow} s_1 \overset{r_2}{\Rightarrow} s_2 \overset{r_3}{\Rightarrow} ... \overset{r_{n}}{\Rightarrow} s_n
\end{displaymath}

且
\begin{itemize}
\vspace{0.5em}
\item $\forall i \in [0,n], s_i \in (N\cup\varSigma)^*$ \hspace{3.5em} $\lhd$ $s_i$为合法的字符串
\vspace{0.5em}
\item $\forall j \in [1,n], r_j \in R$ \hspace{6.3em} $\lhd$ $r_j$为$G$的规则
\vspace{0.5em}
\item $s_0 \in S$ \hspace{10.9em} $\lhd$ $s_0$为起始非终结符
\vspace{0.5em}
\item $s_n \in \varSigma^{*}$ \hspace{10.4em} $\lhd$ $s_n$为终结符序列
\vspace{0.5em}
\end{itemize}

\vspace{0.8em}
则$s_0 \overset{r_1}{\Rightarrow} s_1 \overset{r_2}{\Rightarrow} s_2 \overset{r_3}{\Rightarrow} ... \overset{r_{n}}{\Rightarrow} s_n$为一个推导
\end{definition}
%-------------------------------------------

\parinterval 比如，使用前面的示例文法，可以对“猫/喜欢/吃/鱼”进行分析，并形成句法分析树（图\ref{fig:3.4-3}）。从起始非终结符IP开始，使用唯一拥有IP作为左部的规则$r_8$推导出NP和VP，之后依次使用规则$r_5$、$r_1$、$r_7$、$r_2$、$r_6$、$r_3$、$r_4$，得到了完整的句法树。

\parinterval 通常，可以把推导简记为$d=r_1 \circ r_2 \circ ... \circ r_n$，其中$ \circ $表示规则的组合。显然，$d$也对应了树形结构，也就是句法分析结果。从这个角度看，推导就是描述句法分析树的一种方式。此外，规则的推导也把规则的使用过程与生成的字符串对应起来。一个推导所生成的字符串，也被称作文法所产生的一个{\small\sffamily\bfseries{句子}}\index{句子}（Sentence）\index{Sentence}。而一个文法所能生成的所有句子的集合是这个文法所对应的{\small\sffamily\bfseries{语言}}\index{语言}（Language）\index{Language}。

%-------------------------------------------
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure-example-of-derivation}
	\caption{上下文无关文法推导实例}
    \label{fig:3.4-3}
\end{figure}
%-------------------------------------------

\parinterval 但是，句子和规则的推导并不是一一对应的。同一个句子，往往有很多推导的方式，这种现象被称为{\small\sffamily\bfseries{歧义}}\index{歧义}（Ambiguity）\index{Ambiguity}。甚至同一棵句法树，也可以对应不同的推导，图\ref{fig:3.4-4} 给出同一棵句法树所对应的两种不同的规则推导。

%-------------------------------------------
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure-two-different-derivation-of-regulation}
\setlength{\abovecaptionskip}{-0.5em}
	\caption{同一棵句法树对应的不同规则推导}
    \label{fig:3.4-4}
\end{figure}
%-------------------------------------------

\parinterval 显然，规则顺序的不同会导致句法树的推导这一确定的过程变得不确定，因此，需要进行{\small\sffamily\bfseries{消歧}}\index{消歧}（Disambiguation）\index{Disambiguation}。这里，可以使用启发式方法：要求规则使用都服从最左优先原则，这样得到的推导被称为{\small\sffamily\bfseries{最左优先推导}}\index{最左优先推导}（Left-most Derivation）\index{Left-most Derivation}。图\ref{fig:3.4-4}中的推导1 就是符合最左优先原则的推导。

\parinterval 这样，对于一个上下文无关文法，每一棵句法树都有唯一的最左推导与之对应。于是，句法分析可以被描述为：对于一个句子找到能够生成它的最佳推导，这个推导所对应的句法树就是这个句子的句法分析结果。

\parinterval 不过问题又回来了，怎样才能知道什么样的推导或者句法树是“最佳”的呢？如图\ref{fig:3.4-5}所示，对于语言学专家，他们可以很确定地分辨出哪些句法树是正确的，哪些句法树是错误。甚至普通人也可以通过一些课本中学到的知识产生一些模糊的判断。而计算机如何进行判别呢？沿着前面介绍的统计建模的思想，计算机可以得出不同句法树出现的概率，进而选择概率最高的句法树作为输出，而这正是统计句法分析所做的事情。

%-------------------------------------------
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure-perspectives-of-expert-ordinary-and-syntactic-parser}
	\caption{如何选择最佳的句法分析结果 - 专家、普通人和句法分析器的视角}
    \label{fig:3.4-5}
\end{figure}
%-------------------------------------------

\parinterval 在统计句法分析中，需要对每个推导进行统计建模，于是定义一个模型$\funp{P}( \cdot )$，对于任意的推导$d$，都可以用$\funp{P}(d)$计算出推导$d$的概率。这样，给定一个输入句子，我们可以对所有可能的推导用$\funp{P}(d)$计算其概率值，并选择概率最大的结果作为句法分析的结果输出（图\ref{fig:3.4-6}）。

%-------------------------------------------
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure-probability-values-corresponding-to-different-derivations}
	\caption{不同推导（句法树）对应的概率值}
    \label{fig:3.4-6}
\end{figure}
%-------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{规则和推导的概率}

\parinterval 对句法树进行概率化，首先要对使用的规则进行概率化。为了达到这个目的，可以使用{\small\sffamily\bfseries{概率上下文无关文法}}\index{概率上下文无关文法}（Probabilistic Context-free Grammar）\index{Probabilistic Context-free Grammar}，它是上下文无关文法的一种扩展。

%-------------------------------------------
\vspace{0.5em}
\begin{definition} 概率上下文无关文法

一个概率上下文无关文法可以被视为一个系统$G=<N,\varSigma,R,S>$，其中
\begin{itemize}
\vspace{0.5em}
\item $N$为一个非终结符集合；
\vspace{0.5em}
\item $\varSigma$为一个终结符集合；
\vspace{0.5em}
\item $R$为一个规则（产生式）集合，每条规则 $r \in R$的形式为$p:X \to Y_1Y_2...Y_n$，其中$X \in N$, $Y_i \in N \cup \varSigma$，每个$r$都对应一个概率$p$，表示其生成的可能性；
\vspace{0.5em}
\item $S$为一个起始符号集合且$S \subseteq N$。
\vspace{0.5em}
\end{itemize}
\end{definition}
%-------------------------------------------

\parinterval 概率上下文无关文法与传统上下文无关文法的区别在于，每条规则都会有一个概率，描述规则生成的可能性。具体来说，规则$\funp{P}(\alpha \to \beta)$的概率可以被定义为：
\begin{eqnarray}
\funp{P}(\alpha \to \beta)&=&\funp{P}(\beta | \alpha)
\label{eq:3.4-4}
\end{eqnarray}

\noindent 即，在给定规则左部的情况下生成规则右部的可能性。进一步，在上下文无关文法中，每条规则之间的使用都是相互独立的 \footnote{如果是上下文有关文法，规则会形如 $a\alpha b\to a\beta b$，这时$\alpha \to \beta $的过程会依赖上下文$a$和$b$}，因此可以把$\funp{P}(d)$分解为规则概率的乘积：
\begin{eqnarray}
\funp{P}(d) & = & \funp{P}(r_1 \cdot r_2 \cdot ... \cdot r_n) \nonumber \\
& = & \funp{P}(r_1) \cdot \funp{P}(r_2) \cdots \funp{P}(r_n)
\label{eq:3.4-5}
\end{eqnarray}

\parinterval 这个模型可以很好的解释词串的生成过程。比如，对于规则集
\begin{eqnarray}
r_3: & &\textrm{VV} \to \text{吃}\nonumber \\
r_4: & & \textrm{NN} \to \text{鱼}\nonumber \\
r_6: & & \textrm{VP} \to \textrm{VV}\ \textrm{NN} \nonumber
\label{eq:3.4-6}
\end{eqnarray}

\parinterval 可以得到 $d_1=r_3 \cdot r_4 \cdot r_6$的概率为
\begin{eqnarray}
\funp{P}(d_1) & = &\funp{P}(r_3) \cdot \funp{P}(r_4) \cdot \funp{P}(r_6)\nonumber  \\
& = & \funp{P}(\textrm{VV} \to \text{吃}) \cdot \funp{P}(\textrm{NN} \to \text{鱼}) \cdot \funp{P}(\textrm{VP} \to \textrm{VV NN})
\label{eq:3.4-7}
\end{eqnarray}

\parinterval 这也对应了词串“吃/鱼”的生成过程。首先，从起始非终结符VP开始，使用规则$r_6$生成两个非终结符VV和NN；进一步，分别使用规则$r_3$和$r_4$将“VV”和“NN”进一步推导，生成单词“吃”和“鱼”。整个过程的概率等于三条规则概率的乘积。

\parinterval 新的问题又来了，如何得到规则的概率呢？这里仍然可以从数据中学习文法规则的概率。假设有人工标注的数据，它包含很多人工标注句法树的句法，称之为{\small\sffamily\bfseries{树库}}\index{树库}（Treebank）\index{Treebank}。然后，对于规则$\textrm{r}:\alpha \to \beta$可以使用基于频次的方法：
\begin{eqnarray}
\funp{P}(r)  &=& \frac{\text{规则$r$在树库中出现的次数}}{\alpha \text{在树库中出现的次数}}
\label{eq:3.4-8}
\end{eqnarray}

\parinterval 图\ref{fig:3.4-7}展示了通过这种方法计算规则概率的过程。与词法分析类似，可以统计树库中规则左部和右部同时出现的次数，除以规则左部出现的全部次数，所得的结果就是所求规则的概率。这种方法也是典型的相对频次估计。但是如果规则左部和右部同时出现的次数为0时是否代表这个规则概率是0呢？遇到这种情况，可以使用平滑方法对概率进行平滑处理，具体思路可参考{\chaptertwo}的相关内容。

%-------------------------------------------
\begin{figure}[htp]
   \centering
\input{./Chapter3/Figures/figure-evaluation-of-probability-for-grammar}
	\caption{上下文无关文法规则概率估计}
    \label{fig:3.4-7}
\end{figure}
%-------------------------------------------

\parinterval 图\ref{fig:3.4-8}展示了基于统计的句法分析的流程。首先，通过树库上的统计，获得各个规则的概率，这样就得到了一个上下文无关句法分析模型$\funp{P}( \cdot )$。对于任意句法分析结果$d=r_1 \circ r_2 \circ ... \circ r_n$，都能通过如下公式计算其概率值：

\begin{equation}
\funp{P}(d)= \prod_{i=1}^{n}\funp{P}(r_i)
\end{equation}

\parinterval 在获取统计分析模型后，就可以使用模型对任意句子进行分析，计算每个句法分析树的概率，并输出概率最高的树作为句法分析的结果。

%-------------------------------------------
\begin{figure}[htp]
    \centering
\input{./Chapter3/Figures/figure-process-of-statistical-syntax-analysis}
	\caption{统计句法分析的流程}
    \label{fig:3.4-8}
\end{figure}
%-------------------------------------------


%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\sectionnewpage
\section{小结及拓展阅读} \label{sec3:summary}

\parinterval 本章将统计建模的思想应用到三个自然语言处理任务中，包括：中文分词、命名实体识别、短语结构句法分析。它们和机器翻译有着紧密的联系，往往作为机器翻译系统输入和输出的数据加工方法。可以发现：经过适当的假设和化简，统计模型可以很好的描述复杂的自然语言处理问题。这种建模手段也会在后续章节的内容中被广泛使用。

\parinterval 由于本章重点介绍如何用统计方法对自然语言处理任务进行建模，因此并没有对具体的问题展开深入讨论。有几方面内容，读者可以继续关注：

\begin{itemize}
\vspace{0.5em}
\item 在建模方面，本章描述了基于1-gram语言模型的分词、基于上下文无关文法的句法分析等，它们都是基于人工先验知识进行模型设计的思路。也就是，问题所表达的现象被“一步一步”生成出来。这是一种典型的生成式建模思想，它把要解决的问题看作一些观测结果的隐含变量（比如，句子是观测结果，分词结果是隐含在背后的变量），之后通过对隐含变量生成观测结果的过程进行建模，以达到对问题进行数学描述的目的。这类模型一般需要依赖一些独立性假设，假设的合理性对最终的性能有较大影响。相对于生成式模型，另一类方法是{\small\sffamily\bfseries{判别式模型}}\index{判别式模型}（Discriminative Model）\index{Discriminative Model}。本章序列标注内容中提到一些模型就是判别式模型，如条件随机场\upcite{lafferty2001conditional}。它直接描述了从隐含变量生成观测结果的过程，这样对问题的建模更加直接，同时这类模型可以更加灵活的引入不同的特征。判别式模型在自然语言处理中也有广泛应用\upcite{ng2002discriminative,manning2008introduction,berger1996maximum,mitchell1996m,DBLP:conf/acl/OchN02}。 在本书的第七章也会使用到判别式模型。
\vspace{0.5em}
\item 事实上，本章并没有对分词、句法分析中的预测问题进行深入介绍。比如，如何找到概率最大的分词结果？这个问题的解决可以直接借鉴{\chaptertwo}中介绍的搜索方法：对于基于$n$-­gram 语言模型的分词方法，可以使用动态规划方法\upcite{huang2008coling}进行搜索；在不满足动态规划的使用条件时，可以考虑使用更加复杂的搜索策略，并配合一定的剪枝方法找到最终的分词结果。实际上，无论是基于$n$-gram 语言模型的分词还是简单的上下文无关文法都有高效的推断方法。比如，$n$-gram语言模型可以被视为概率有限状态自动机，因此可以直接使用成熟的自动机工具\upcite{mohri2008speech}。对于更复杂的句法分析问题，可以考虑使用移进- 规约方法来解决预测问题\upcite{aho1972theory}。
\vspace{0.5em}
\item 从自然语言处理的角度来看，词法分析和语法分析中的很多问题都是序列标注问题，例如本章介绍的分词和命名实体识别。此外序列标注还可以被扩展到词性标注\upcite{brants-2000-tnt}、组块识别\upcite{tsuruoka-tsujii-2005-chunk}、关键词抽取\upcite{li-etal-2003-news-oriented}、词义角色标注\upcite{chomsky1993lectures}等任务，本章着重介绍了传统的方法，前沿方法大多与深度学习相结合，感兴趣的读者可以自行了解，其中比较有代表性的使用双向长短时记忆网络对序列进行建模，之后于不同模型进行融合得到最终的结果，例如，与条件随机场相结合的模型（BiLSTM-CRF）\upcite{2015Bidirectional}、与卷积神经网络相结合的模型（BiLSTM-CNNs）\upcite{chiu2016named}、与简单的Softmax结构相结合的模型\upcite{vzukov2018named}等。此外，对于序列标注任务，模型性能很大程度上依赖对输入序列的表示能力，因此基于预训练语言模型的方法也非常流行\upcite{Li2020A}，如：BERT\upcite{devlin2019bert}、GPT\upcite{radford2018improving}、XLM\upcite{conneau2019unsupervised}等。
\vspace{0.5em}
\end{itemize}