在达尔文的进化论中，自然界物种间和同物种个体间，因为生存竞争而优胜劣汰。但随着人们对自然界的不断观察和研究，发现自然界不只存在竞争，而且存在利他合作，对达尔文进化论进行了补充和发展，形成了新达尔文学说。在自然界中，同一物种和不同物种的种群之间，都存在竞争和共生关系，并且合作比竞争更为普遍。
1990年，Daniel Hillis受Hamilton启发，创造性地将自然界中捕食者－被捕食者的协同进化现象（predator-prey coevolution）引入进化算法，提出了协同进化算法(CEA,co-evolutionary algorithm)，并将之用于求解排序网络优化问题，取得了良好的效果。
在Hillis提出协同遗传算法中，存在两个种群，一个种群是候选解，一个种群是测试集，每次只选取少数具有高难度的测试对个体进行评估，两个种群互相评价，共同进化，类似于自然界中捕食者与被捕食者的相互促进的关系，形成协同进化。该算法不仅可以避免陷入局部最优，而且大幅度提升了计算效率。
Paredis在Hillis基础上，加入了个体全生命周期适应值评估机制（LTFE，life-time fitness evaluation），从而能够引入多种个体学习机制（LTL，life-time learning），包括Back-Propagation等学习机制，形成了更强大的协同进化算法，并将之用于优化分类神经网络和求解约束优化问题。
与一般的个体评估机制不同的是，全生命周期适应值评估机制不是单纯的使用适应值函数评估，而是尽量将复杂的问题分成小问题，每次评估一个子问题，并且是两个群体互相评估。这样既减小了评估代价，并且总是优先解决当前较难的子问题；同时，种群也不易陷入局部最优，保持了较好的多样性。特别是在求解约束优化问题时，将约束条件作为一个种群，使用全生命周期适应值评估机制后，搜索效率提升明显，具有更强的搜索可行解的能力。
八月底的时候，找工作的事情就提到了最重要的等级上了。我写了份简历，自己觉得还可以，写完简历上QQ。结果意外在群里看到余子玉吼了一声，知道可以找他帮忙内推百度。刚开始，我都不知道有内推这回事，经过余子玉同志用心良苦的教育，我才意识到这是一个很好的机会。又经过他的诲人不倦的艰苦教育，我认识到写简历是个技术含量很高的活。修改好简历，拜托他师兄帮忙内推了百度。
到了9月29日，百度来了电话面试。面了大概二十多分钟，针对简历问了项目经历，每个项目怎么做的，问得很细。然后还问了项目中最难的地方是什么，怎么克服的。然后还问了有没有多线程经验等。大概就问了这些，三十多分钟就过去。电话面试是针对内推的人进行的一轮筛选，表现比较好的进入面试阶段，表现还可以的参加笔试，不适合的就淘汰了。
电话面试过后，国庆就一直呆在实验室准备面试的事情。10月9日上午百度就打来电话，约我下周一下午面试，问我是当面面试还是电话面试，刚开始我怕麻烦想电话面试，但想一想当面面试更有诚意些，就约好当面面试了。接下来就是买火车票，准备money。没想到的是，火车票这么难买，居然都没有火车票了，只好打电话让我哥帮忙买黄牛票。结果第一个黄牛也跑票了，说好了的票没有了，又只得找第二个黄牛，买了一张超级慢的K186，要二十多个小时。小曼帮忙收拾好东西，准备了两本书，带上了她的笔记本。上了火车，路上看看书，晚上用小曼的小本本看看文档。
周一上午十点半终于到了北京，坐319到了余子玉那里，吃完中饭在他宿舍休息了一会儿。下午三点半就打的到了普天大厦，四点钟上楼到了前台，前台MM给贴了一张Baidu Friend，然后在会议室等。等的时候，发现百度真如传说中一样，无论帅哥还是MM，都是捧着一个笔记本到处走。
Read more…
柯林斯（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年吴军对最大熵模型进行了进一步改进，提出了层次训练算法。下一篇将详细介绍这一算法。
UDS-SJTU 联合实验室（德国萨尔州大学和上海交通大学的联合实验室）邀请我做一场语言技术的演讲。我简要介绍了我们如何基于已有的服务和数据上面构建Totuba研究平台。 成为一个AI研究者真是令人兴奋：这需要感谢Linked Open Data Initiative 将巨大的机器可以处理的数据公开在网络上了；还有一些相似让复杂的文本处理成为可能的网络服务，例如OpenCalais，一个抽取文本的主题的网络服务。 简单的说，这些意味着我们能够复用这些工具和数据为Totuba快速构建一个原型，而这样的工作在数年以前还是令人望而却步的昂贵。
我认为在研究或者商业应用中都应当鼓励复用，这能够给我们带来好处。下面是我的演讲PPT:语义网研究平台的一个快速原型 。
下面简要介绍一下其他人的演讲内容。
Hans Uszkoreit教授展示了混合机器翻译，结合了统计机器翻译和基于规则机器翻译这两种最好的机器翻译算法。统计系统在封闭领域中是较好的机器翻译算法，如果在开放领域则是基于规则的系统更好。混合机器翻译算法的主要思想是，将基于规则翻译的短语替换成统计机器翻译的短语。Uszkoreit教授还展示了EuroMatrix项目，一个针对欧洲语言的翻译竞赛。
徐飞玉则介绍了如何使用“种子”从文本中抽取信息，种子(例如ElBaradei, Nobel prize, peace, 2005) 能够帮助找到相似的信息。她展示了选择正确的种子的重要性，以及负面种子(例如nominated, Noble Prize)能够改进准确率(但是召回率有所下降)。
Read more…
原文链接：http://www.intelligententerprise.com/blog/archives/2009/06/summer_reading.html
夏天缓慢的节奏让我们可以通过阅读度过平静的一天。你的阅读计划是什么呢？我的阅读计划包括各种论文和对信息搜索、情感分析和可视化的长期工作。在我的列表上的都是技术性的和入门级的（也不能算容易），任何从事分析工作并有潜在兴趣的人都可以阅读。我已经记录下来而且计划进行深入阅读。TechWeb读者可能会觉得它们至少值得阅读一下。
Read more…
最新评论