柯林斯（Collins）是Marcus的高徒，现在在MIT任教。Collins在2003发表于《Computational Linguistics》上的论文《Head-Driven Statistical Models for Natural Language Parsing》中提出了三个头驱动统计模型，其实就是其1999年的博士论文的精简版。该模型在当时是性能最好的句法分析模型。
柯林斯的头驱动统计模型，本质上属于基于历史模型，论文中该模型用于句法分析。句法分析的输入是词性标注过的句子，输出则是具有句法结构标注的句子，其结构可用句法树来表示。句法树有很多种，根据算法不同有不同的选择。句法树的构建过程就是一个决策序列，决策序列与句法树是一一对应的。句法分析的文法模型，总体来说有概率上下文无关模型（PCFG）、词汇概率上下文无关模型（Lexicalized PCFG，以下简称L-PCFG）、基于规则模型，应用得最广泛的是概率上下文无关模型。PCFG模型简单有效，但其独立性假设忽略了很多可以利用的信息，性能上不及L-PCFG模型，而柯林斯正是在L－PCFG模型基础上改进，利用了更多信息，提出了用于句法分析的头驱动统计模型，因此准确率达到了当时最高峰，但实现就比PCFG复杂了许多。
其第一个模型中，修改了L－PCFG的独立性假设，将规则概率的计算公式简化为一个个小的句法标注符概率的乘积，这个步骤不仅复杂度得到降低，而且大大缓解了数据稀疏问题。其后，又在模型中加入了距离信息，使得该模型的性能一举超越其他模型。
柯林斯在这时并没有满足，而是继续在第一个模型基础上，加入了补语分类信息，形成了第二个模型。在很多时候，补语的结构容易被错误标注，这都是由于补语结构没有另外的标注符号，导致统计模型中不能区分，从而导致误标注。柯林斯对语料库进行了改造，加入了新的标注符号，区分补语结构，并在规则概率计算公式中加入对补语结构概率的计算。该模型能够区分补语结构，从而降低了误标注率，性能进一步提升。
Read more…
计算机可能善于计算，但是能否知道感觉呢？博客和社交网络的上升，带动了挖掘个人观点的牛市，包括评论、打分、推荐和其他的在线形式。对于计算机科学家来说，急速增长的数据打开了一扇收集网友感受的大门。
一个名叫“情感分析”的新兴领域逐渐成形，这是计算机世界的一个尚未开发的前沿：将各种人类情感转化成实实在在的数据。
这不仅仅是一个网络开发演习，对于许多企业来说，在线观点更像虚拟货币，能够造就或者毁灭一个产品。
现在，在对产品如潮水般涌来的网络批评或赞扬中，许多公司处理不及，陷入漩涡中。随着情感分析工具的形成，它们不但能够改善企业的生命线，还能够给在线搜索带来转变。
几家情感分析公司正试图满足企业们的对在线言论的商业兴趣。“社会化媒体曾经被认为只是25岁顾问眼中的可爱项目” 旧金山的Scout Labs副总裁Margaret Francis说道，“现在顶极执行官都已经认识到，对于商业智能来说，这是一个不可思议的富矿。”
风险投资青睐的Scout Labs公司，由CNet创始人Halsey Minor创建，最近介绍了一种订阅服务，能够帮助客户监测博客、新闻、论坛和社会化网络网站，以识别对产品、服务或新闻主题的言论动态。在五月早些时候，StubHub票务公司使用Scout Labs的监测工具，监测到一场因雨延迟的Yankees对Red Sox比赛所带来的突然上升的负面博客情绪。
Read more…
纽约时报前不久对自动情感分析进行了报道（这篇报道将在下一个帖子中翻译，敬请期待），一家公司对这个领域的比喻很有趣：
“情感分析工具就像是煤矿中的金丝雀”， StubHub的客户总监John Whelan说。
我对自动情感分析的立场是：它目前还是一个不够好用的工具，至少还需要许多年才能挖掘出它的全部能力。
我并不整体否定情感分析——显然70% 的准确率比0%要好，但是我注意到一些公司对自动情感分析的可靠性具有错误的观念。打个比方，如果一只鸟，有30％的几率会误报瓦斯的危险水平，你愿意跟随这只鸟下到煤矿里去吗？我肯定不愿意。
问题是，大部分情感分析算法依赖于我们是使用简单的句子表达对一个产品或服务的情感。如果就如识别 “I love BestBuy” 或者 “I hate the iPhone” 那样简单，那么我们就可以建一个关键词数据库，情感分析就可以达到100% 的准确率了。很可惜，任何一种语言都不会那么简单。 Read more…
上次的文章中讲到吴军在IIS的基础上进一步提出了层次训练算法，其核心思想是利用特征的层次化关系，避免了重复计算，从而把最大熵模型的训练效率提高了几百上千倍。
最大熵模型的训练的计算量主要来自三个部分：模型参数、特征期望值和归一化因子。模型参数的个数等于特征的个数，可以用IIS中的办法计算出来，计算量相比特征期望值和归一化因子算是少的，因此主要的计算量集中在后两者。层次训练算法中计算模型参数的方法与GIS和IIS是一样的，主要改进特征期望值和归一化因子的计算方法。
最大熵模型中的特征有很多，有些特征具有层次化关系，例如在3-gram模型中，符合一个三元特征的元组通常会符合一个二元特征，因此符合二元特征的元组集合包含三元特征的元组集合，两者具有层次关系，以此类推，二元特征又跟一元特征具有层次关系。因此，在计算归一化因子的时候，能够将式子划分成对一元特征、二元特征和三元特征的累加值的和，这样具有同样前向条件的二元元组和三元元组只需计算一次，以后就都能使用二元特征和三元特征的累加值，只需计算一元特征的累加值，计算量大为下降。同样，在计算特征期望值的时候，由于符合一元特征的元组集合包含二元和三元特征的，可以将求一元特征期望值的式子划分成一元、二元、三元三个部分，其中二元和三元的部分，只需计算一次，以后具有同样的前向条件的三元元组就不需要计算了，以此类推，二元特征期望值和三元特征期望值，也可以简化。
但是，有些模型的特征并不具有层次关系，吴军提出一个通用的层次化特征的办法，这样对于一些诸如主题特征、句法特征、符号特征等无层次的特征的计算也能够进行简化。在此基础上，吴军还进一步简化了归一化因子的计算，将最大熵模型转化ARPA格式，同时对常用的归一化因子和特征期望值进行缓存，计算时间进一步减少。
以上三篇文章对最大熵模型的训练算法，做了基本介绍，下一篇将讲讲最大熵模型与最大似然概率的关系。
上次的文章中讲到最大熵模型最难的部分是训练，因为训练中的数据量巨大，导致计算量巨大。Darroch & Raticliff在1972年提出了GIS算法来求解。GIS算法是一种通用的求解线性等式约束对数线性规划问题的算法，其核心思想是利用拉格朗日算子，将线性等式约束对数线性规划问题转化为对数线性规划问题，然后使用求偏导数法将对数线性规划问题转化为迭代求解问题，最后使用梯度递减法求得最优解。GIS算法的效率不高，收敛速度慢，而且不稳定，容易越界。
鉴于这些缺陷，最大熵模型并未被广泛使用，但Adwait Ratnaparkhi在1994年的A Maximum Entropy Model for Parsing 论文中成功的使用了最大熵模型进行句法分析。1997年Della Pietra & Lafferty提出了IIS算法，对GIS进行了改进。IIS算法的前两步与GIS相同，再将线性等式约束对数线性规划问题转化为迭代求解问题后，使用最大似然概率法将问题再次转化为求最大下界问题，然后使用求偏导数法求得迭代步长，循环迭代得到最优解。Adam Berger对IIS算法进行了十分清晰的解释。
虽然经过了两次改进，最大熵模型的计算量仍然十分巨大，在2001年吴军对最大熵模型进行了进一步改进，提出了层次训练算法。下一篇将详细介绍这一算法。
原文链接：http://www.intelligententerprise.com/blog/archives/2009/06/summer_reading.html
夏天缓慢的节奏让我们可以通过阅读度过平静的一天。你的阅读计划是什么呢？我的阅读计划包括各种论文和对信息搜索、情感分析和可视化的长期工作。在我的列表上的都是技术性的和入门级的（也不能算容易），任何从事分析工作并有潜在兴趣的人都可以阅读。我已经记录下来而且计划进行深入阅读。TechWeb读者可能会觉得它们至少值得阅读一下。
Read more…
对于自然语言处理中的各种模型来说，最大熵模型是一种在形式上最简单，但是在实现上却最复杂的模型。最大熵模型就是在满足已知条件的情况下，求得使熵最大的概率模型。说起来很简单，实际上要求得这个熵最大的概率模型，计算量十分巨大，因此需要仔细设计细节。
最大熵模型最大的难点来源于特征的选取和参数估计。其中特征选取的需要很多次迭代，在迭代的过程中逐步对参数进行估计。在最大熵模型参数的计算中，因为将特征视为已知，因此需要对已知情况进行计算，而这种计算就是最大似然概率估计算法的特长。
最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不复杂，大致可以概括为以下几个步骤：
Read more…
在自然语言处理中，常常需要对语音识别、分词、词义标注、词性标注、句法分析等进行解空间搜索。解空间搜索的效率和准确性，一般理解是一个矛盾的命题。要得到最优的解就需要遍历整个搜索空间，效率就会有所下降。然而，却有些巧妙的算法能够提高效率同时，不损失准确性。下面将介绍两种常用的搜索算法：Viterbi、A*。
- Viterbi算法在自然语言处理中运用广泛。其核心思想是：针对输入序列，构造一个Viterbi矩阵，行为候选解序列，列为输入序列（N+2，加入了伪开始与结束列）。对每一个候选解根据当前时刻的前向概率和一些条件概率，计算具有最大迁移概率的取值并记录前一个时刻的取值，如此循环直到结束。回溯概率最大的候选解即可得到最优解的输出序列。Viterbi算法能够得到最优解，是基于动态规划恒定的假设：如果最佳路径经过状态Qi，那么这个最佳路径一定包含Qi之前的最佳路径。因此Viterbi算法并不能用于所有可能的语言模型，例如对于三元语法模型就不适用。其伪代码如下：
Function Viterbi(state-graph,input T)
state-number = Number of states(state-graph)
Create path probability matrix viterbi[state-number+2,T+2]
viterbi[0,0] = 1.0
for t = 0:T
for s = 0:state-number
for s-next = each symbol from s specified by state-graph
new-score = viterbi[s,t]*P(s,s-next,t)
if(viterbi[s-next,t+1] == 0 || newscore > viterbi[s-next,t+1])
then
viterbi[s-next,t+1] = new-score
back-pointer[s-next,t+1] = s
backtrace from maxium probability state in the final column of viterbi[] and return path
- A*算法是搜索格子和树空间的最佳优先搜索算法。其核心思想是：维持一个优先队列，每次从队列中取得分数最高的候选解进行扩展操作后得到新的候选解并进行评分，将其加入优先队列，如此循环直到找到一个完整解。其中评分函数的设计是一个难点，还没有解决。A*算法允许使用任何语言模型。其伪代码如下：
Function AStar(input T)
prior-queque = null
s = pop(prior-queue)
if( s contain EOS mark)
output s and exit
for w of candidate next symboles based T
create new candidate solution s+w
new-score = g(s+w)+h*(s+w)
if(end of T)
set EOS mark for s+w
insert s+w into prior-queue with new-score
Read more…
最新评论