speech and language processing读书
ch5词性标注
词性标注能够提供关于单词和其邻近成分的大量有用信息。它可以区分标记集的主有代词和人称代词；能告诉我们关于单词的发音信息；能用来在信息检索中帮助分割词干；帮助我们进行词义排歧。
目前用到的算法有手写规则（基于规则的标注），统计方法（隐马尔可夫模型标注HMM和最大熵标注）,基于转化的标注和基于记忆的标注等。
5.1英语词的分类
词类分为两个大类：封闭类（比如介词，成员相对固定）和开放类。封闭类又称为虚词，通常很短，出现频率高，在语法中表示结构关系。
名词，动词，形容词，副词为四大开放类。
名词是具有以下能力的词：与限定词（一个，他的）同时出现；可以受主有代词的修饰；大多数名词都可以以复数形式出现。
动词表示大多数行为和过程的词。
形容词包括很多描写性质或质量的单词。
副词可以看成是要修饰某种东西的词。
不同语言的封闭类差别很大，英语中重要的封闭类有：介词，限定词，代词，连接词，助动词，小品词，数词
5.2英语的标注集
包含87个标记的标记集Brown语料库；除此之外常用的两个标注集：penn treebank标记集和CLAWS
5.3词类标注
POS标注的问题就是消解歧义，在一定的上下文中选择恰如其分的标记，所以词性标注是排歧的一个重要方面。
大多数的标注算法可以归纳为两类：一类是基于规则的标注算法，一类是概率或者随机标注算法
5.4基于规则的词性标注
在标注算法的第一阶段，每一个单词都要通过双层的词表转录机，然后该单词所有可能的词类都返回到他的条目上。然后把大量的约束规则应用于输入的句子中以便消除那些不正确的词类。
5.5基于隐马尔可夫链的词类标注
把隐马尔可夫模型应用于词类标注是贝叶斯推理的一种特殊情况。
词类标注一般可以作为一个序列分类问题来处理。
词性标注可以看作是给单词序列指派一个词性标注序列。在贝叶斯推理中，我们首先考虑所有可能的类的序列，从中选出最可能的标记序列。
HMM标注算法有两个假设，为了简化计算：1.单词出现的概率只与它本身的词类标记有关；2.标记出现的概率只与他前面一个标记有关，也就是我们前面说的二元语法。
马尔可夫链适合用于能够看到实际条件的事件，但是不适合做词类标注，隐马尔可夫模型就可以
viterbi算法是HMM最常见的解码算法，解码就是确定哪一个变量序列是隐藏在某个观察序列下的源变量。viterbi算法实际上就是经典的动态规划算法的标准应用。viterbi算法一个稍微简化的表达就是：取一个单独的HMM和所观察到的单词序列o作为输入，返回概率最大的状态/标记序列q以及他们的概率作为输出。
在实际应用时，HMM算法是忽略上下文信息的，现在大多数的HMM标注算法使用的历史信息多一些，不是二元语法而是三元语法。这样会造成一个数据稀疏问题，据此问题可以使用删除插值法。
这里可以区分HMM算法和EM算法。HMM算法使用手工标注数据进行训练，EM算法是自动学习的。
5.6基于转换的标注
Transformation-based learning ,TBL是基于规则的，他最终指出，什么样的标记会指派给什么样的单词，但是它的规则是从数据中自己推导出来的，他是有指导的，需要一个预先标记过的训练语料库。
TBL的标注规则就是对语料库先使用比较粗糙的规则来标注，这些规则也就是在大多数场合都能使用的规则，然后再选择较为特殊的规则来修改原来的某些标记。
TBL算法主要包含三个阶段：1.首先把每一个单词标上最可能的标记；2.检查每一个可能的转换，并且选择那个能够最大程度的改善标注的转换；3.根据这个规则对数据进行重新标注。后面两个阶段重复进行，直到达到某一个标准。
5.7评测和错误分析
将语料库分为测试集和训练集，这样在测试时测试集的容量再大也无法反映数据的全貌，所以最好的方法是用全部的数据进行测试和训练，这时所用到的方法就是交叉验证，交叉验证是不断的随机分测试机和验集。
评价准确率的好坏时由于标记集和任务的不同，标记的使用情况可以根据下界的底线（baseline）和上界的顶线（ceiling）来比较。顶线就是看人来进行这项任务所达到的程度。语义消歧的标准底线是对每一个歧义单词选择一元语法最可能的标记，最大频率底线是给每一个单词指派在训练集上最经常出现的类别标记。
5.8词类标注中的高级专题
5.8.1实际问题：标记的不确定性与词例还原
遇到标注的不确定问题，有些标注器允许多重标注。通常有三种方式处理不确定性：1.采用某种方式只以一个标记来代替不确定的标记；2.在测试时，只要给出其中一个正确的标记就算标记正确，训练时，才用某种方式只用多个标记中的一个作为他的标记；3。把不确定的标记作为一个单独的复杂标记来处理。
大多数的标记算法都假定标记已经应用过词例还原了
5.8.2未知词
我们讨论的所有算法都要求有一步词典，词典列出词已经所有可能的标注。但是再大的词典也不可能将所有的可能的词都包含进去。所以我们需要某种方法来猜测未知词的标记。
最简单的思想是认为每种未知词都是有歧义的且每种可能的标注的概率是一样的。稍微复杂一点的思想是在未知词的概率分布上是与只出现一次的词的概率分布是一样的；他们的相似之处在于他们最可能的词性是名词，其实是动词。最强的未知词算法是使用了单词的形态信。
5.9高级专题：拼写中的噪声信道模型
一般来说噪声信道模型是更正单词拼写错误的一种使用最广的算法。
噪声信道模型可以从直觉上解释为：一个正确拼写的单词通过噪声信道的信道时被扭曲了，我们要通过信道模型来处理这个错拼的单词。噪声信道模型告诉我们，是有一个真正被隐藏起来的单词w，并且有一个噪声信道把这个单词改变为了某种可能拼错的表层形式。
对于真词拼写错误我们把更正这样的错误叫做上下文有关的拼写更正错误。
ch6隐马尔可夫模型与最大熵模型
HMM与MEMM两者都是序列分类器，他是给序列中的某个单元指派类别或者标号的模型。如果认为有限状态转录机是非概率序列分类器，那么HMM与MEMM就是使用概率的序列分类器。
6.1马尔可夫链
马尔可夫链是加权自动机的一个特殊情况，其中输入序列唯一的确定了自动机将要通过的输入序列唯一的确定了自动机将要通过的状态。更想象的描述，马尔可夫链可以看作是概率图模型。一阶马尔可夫链认为一个特定状态的概率只与他前面的一个状态有关。
6.2隐马尔可夫模型
隐马尔可夫模型使得我们有可能涉及被观察到的事件，又涉及隐藏事件。
一阶隐马尔可夫模型有两个假设，一个是特定状态只与他前面一个状态有关；一个是一个输出观察的概率只与该观察的状态有关而与其他任何状态任何观察都无关。
如果任何两个状态之间都有一个非零的概率，那么这样的HMM称为全联通HMM或者遍历HMM
6.3似然度的计算：向前算法
向前算法有效的代替了呈指数增长的极为复杂的算法，是一种动态规划算法，当得到观察序列的概率时，使用一个表来存储中间值。
6.4解码：viterbi算法
解码就是确定哪一个变量序列是隐藏在后面的某个观察序列的来源的工作
HMM最常见的解码算法就是viterbi算法，他是一种动态规划算法，使用动态规划网格，与最小编辑距离算法很相似。
6.5HMM的训练：向前-向后算法
训练HMM的标准算法是向前-向后算法，这是期望最大化算法的一种特殊情形。它帮助我们训练转移概率和发射概率。
6.6最大熵模型：背景
最大熵模型是一种多元回归模型，是非序列分类工具。它属于指数分类器或对数分类器
6.6.1线性回归
在统计学中，把某些输入特征映射到某个输出值时，输出是实数值，就使用“回归”，输出是离散值(即类删离散集合中的某个值)，就使用“分类” 用于预测的因素称为特征，使用多个特征的线性回归称为多元线性回归，训练回归模型基于代价函数的。
6.6.2逻辑回归
在回归模型中，使用线性函数来估计概率的分对数，而不是估计概率，这样的回归称为逻辑回归。
6.6.3逻辑回归(分类)
分类也称为推论是说给定一个特定的观察，确定其属于两个类别的哪一个，也称为二元分类问题。超平面是用于分开两个类别的平面。
6.6.4高级专题：逻辑回归(训练)
在线性回归中，训练就是选择合适的权值，使得训练集上的代价函数最小。 在逻辑回归中，使用条件最大似然度估计来估计权值，这个问题属于凸优化问题。凸优化问题常用算法有准牛顿法，梯度上升法， 共轭梯度法，迭代定标算法
6.7 最大熵模型(MEMM)
最大熵模型是对数线性方法家庭中的一员，主要用与分类。 对数线性模型也应用于汉语的词类标注中。
前面我们假设的特征都是实值的，而在nlp中通常使用2值属性的，指示函数就是如果一个特征取值为0和1。
当使用MaxEnt在进行分类时，他会将这个类别上的概率分布给我们。如果我们想要进行硬分类并选择最佳的类别，我们需要选择具有最大概率的类别。因此最大熵模型是逻辑回归中的分类的泛化。
以上我们描述的都是单独的二元特征。而现实中我们常会建立更复杂的特征来表示一个单词的多个特性的组合。想支持向量机等机器学习模型就可以自动的模拟特征之间的相互关系，但最大熵模型中任何一种复杂的特征都必须通过手工定义。想要成功的使用最大熵模型关键在于设计恰当的设计特征与特征之间的组合。
训练最大熵模型的一个重要问题是对于权值进行平滑，称为正则化。正则化的目的是惩罚那些大的权值。
为什么多元逻辑回归要叫最大熵，直觉上来讲：所谓最大熵就是不断的通过增加特征的方法来建立分布，每一个特征就是一个指示函数。对于每一个特征在总的分布中增加一个约束，所以我们要选择与这些约束一致的最大熵分布，而多元逻辑回归的指数模型也能够找到最大熵分布。
6.8 最大熵马尔可夫模型
最大熵马尔可夫模型是基本的最大熵模型分类起的扩充，它能够把一个类别指派给一个序列中的每一个成分。最大熵模型把voterbi算法与最大熵模型紧密结合起来。
我们曾经说HMM是一个生成模型，而MEMM是分辨模型，因为模型通过训练可以在各种可能的标记序列中进行分辨。另一点于HMM的不同是，MEMM可以使用观察到的任何有用的特征作为条件。
而与HMM一致的事，MEMM同样可以使用viterbi算法进行解码。
