月度归档:2011年04月

52NLP微博-当真李逵遇到假李逵

  晚上无意间发现了新浪微博上有个52nlp的帐号:

  52nlp微博

  有点吃惊,虽然52nlp不是我的注册商标,任何人都有权利在新浪微博上注册,但是说成是我的,就有问题了。我没有在新浪微博上以52nlp的名义注册任何微博帐号,虽然前段时间在Twitter和腾讯微博上注册了52nlp的帐号,计划尝试玩一下微博,但是到目前为止还没有公开过,主要原因大概是自己认为做好52nlp这个博客就够了,其他都是浮云!同样,到目前为止,我没有加入任何自然语言处理的群,甚至也没有因为喜爱水木NLP版而去注册一个水木的帐号。
  但是,当我看到这个微博的时候,有点坐不住了,第一感觉就是“真李逵遇到假李逵”,没办法,别人已经注册了52nlp,我也没话说,但是请不要借用这个“52nlp”的旗号就行了。同样,为了遏制谣言,我刚刚注册了一个新浪微博帐号:http://weibo.com/2104931705,并且写下了我的第一条微博:

  52nlpcn:52NLP微博-当真李逵遇到假李逵!http://t.cn/hdjv3u

  如果你喜欢这里的52nlp,并且拥有新浪微博帐号,欢迎转发这条微博,非常感谢!

立委科普:问答系统的前生今世

李维老师的文章看起来就是过瘾,这篇文章也是刚刚在科学网上看到的,还有下一篇,感兴趣的读者可以继续关注。前段时间IBM超级计算机沃森(Watson)刚刚出了一把风头,也让关注自然语言处理的读者更关注起自动问答系统了,李维老师的这篇博文无疑让我们对于问答系统的前世今生又有了一次深刻的了解,所以厚着脸皮,以下继续全文转载自李维老师的博文:立委科普:问答系统的前生今世

上周信笔涂鸦写了个不伦不类的科普(【立委科普:从产业角度说说NLP这个行当】),写完自我感觉尚可,于是毛遂自荐要求加精:“自顶一哈:不用谦虚,这个应该加精。也不枉我费了大半天的时辰。” 本来是玩笑话,没成想科网的编辑MM在两小时内就真地加精上首页了。前几周还在抱怨,怕被编辑打入另册,正琢磨献花还是金币以求青睐,没想到这么快就峰回路转,春暖花开。响鼓不用重敲,原来还是要发奋码字才行,花言巧语的不行。得,一鼓作气,再码两篇。

言归正传,第一篇先介绍一下问答系统(Question Answering system)的来龙去脉。第二篇专事讲解问答系统中的三大难题 What,How 与 Why。

一 前生

传统的问答系统是人工智能(AI: Artificial Intelligence)领域的一个应用,通常局限于一个非常狭窄专门的领域,基本上是由人工编制的知识库加上一个自然语言接口而成。由于领域狭窄,词汇总量很有限,其语言和语用的歧义问题可以得到有效的控制。问题是可以预测的,甚至是封闭的集合,合成相应的答案自然有律可循。著名的项目有上个世纪60 年代研制的LUNAR系统,专事回答有关阿波罗登月返回的月球岩石样本的地质分析问题。SHRDLE 是另一个基于人工智能的专家系统,模拟的是机器人在玩具积木世界中的操作,机器人可以回答这个玩具世界的几何状态的问题,并听从语言指令进行合法操作。这些早期的AI探索看上去很精巧,揭示了一个有如科学幻想的童话世界,启发人的想象力和好奇心,但是本质上这些都是局限于实验室的玩具系统(toy systems),完全没有实用的可能和产业价值。随着作为领域的人工智能之路越走越窄(部分专家系统虽然达到了实用,基于常识和知识推理的系统则举步维艰),寄生其上的问答系统也基本无疾而终。倒是有一些机器与人的对话交互系统 (chatterbots)一路发展下来至今,成为孩子们的网上玩具(我的女儿就很喜欢上网找机器人对话,有时故意问一些刁钻古怪的问题,程序应答对路的时候,就夸奖它一句,但更多的时候是看着机器人出丑而哈哈大笑。不过,我个人相信这个路子还大有潜力可挖,把语言学与心理学知识交融,应该可以编制出质量不错的机器人心理治疗师。其实在当今的高节奏高竞争的时代,很多人面对压力需要舒缓,很多时候只是需要一个忠实的倾听者,这样的系统可以帮助满足这个社会需求。要紧的是要消除使用者 “对牛弹琴”的先入为主的偏见,或者设法巧妙隐瞒机器人的身份,使得对话可以敞开心扉。扯远了,打住。)
继续阅读

立委科普:从产业角度说说NLP这个行当

“NLP is not magic, but the results you can get sometimes seem almost magical.”

这篇文章是前几天在科学网李维老师的博客上看到的,写得很棒,没有在NLP产业摸爬滚打几十年,是写不出的,这里全文转载,原文见科学网博客, 以下转载自李维老师的博文:立委科普:从产业角度说说NLP这个行当

前面一篇博文的本意,是想借题发挥,从工业运用的角度说说 NLP(Natural Language Processing:自然语言处理)这个行当。不好意思,我算是这个行当在工业界的老古董了(学界不算,学界有的是NLP师爷和大牛)。跟我同期学习这行的同门学长们有小20位,由于这个行当不能在工业界形成规模,他们无一例外都在不同时期改行了,我几乎是幸存在工业界的仅有的化石级元老,赶上了工业应用的末班车。我运气比较好,1986年硕士毕业不久就兼职中关村搞机器翻译的开发,1997年博士快结束又赶上了dot康泡沫的美国大跃进,技术资金源源不断。就是在泡沫破灭后的萧条年代,我也一直对这一行抱有信心,但是从来没有像现在这样信心满满。我的预计,今后20年是 NLP 大显神威的时机,NLP 技术支撑的包括搜索在内的各类信息系统是真正的朝阳产业。(卖瓜的说瓜甜,据说连饶教授这样的大牛都不免。所以读者诸君为免在下误导,可在此打个折扣。)

NLP 技术的工业可行性我认为已经完全被证明了(很多人也许还没有意识到)。证明的实例表现在我们解决了三个信息搜索的难题:1 是解决了搜索 how 的难题;2 是解决了搜索 why 的难题;3 是解决了对客户反馈情报及其动机的抽提(譬如客户对一个产品的好恶)。前两个问题是问答搜索业界公认的最难类型的题目,第三个题目涉及的是语言现象中较难把握的主观性言语(subjective language),并非NLP通常面对的对象(objective language,事实描述的客观性言语),因此成为语言处理最难的课题之一(叫 sentiment extraction)。从问答系统角度来看,回答who/when/where等实体(entity)事实(factoid)的问题比较简单,技术相对成熟,最突出的表现就是IBM的问答系统赢得美国家喻户晓的电视智力竞赛Jeopardy的冠军,电脑打败了人脑,见 COMPUTER CRUSHES HUMAN 'JEOPARDY!' CHAMPS)。这是因为 JEOPARDY! 的大多数问题是属于实体事实类的问题。具体细节就不谈了,以后有机会再论。总之,这三大公认的难题在过去五年中被我们一个一个解决,标志了作为实用技术的 NLP 已经过了需要证明自己的阶段。

很长一段时间,我们在学界测量一个系统,使用的是两个指标:1 查准率(precision:准确性, 即抓到的有多大比例是抓对了的);2 查全率(recall:覆盖面,即所有该抓到的有多大比例真地抓到了)。Precision 和 recall 的定义如下:

Precision 查准率 = correct 查对数 / (correct 查对数 + spurious 查错数)
Recall 查全率 = correct 查对数 / (correct 查对数 + missing 查漏数)

由于自然语言的歧义(和诡异),要想编制一套两项指标综合水平(术语叫 F-score)都很高的系统非常不容易。这跟打假也差不多,宁肯错杀一千,也不放过一个的蒋中正野蛮政策保证的是查全率;而宁肯放过一千,也不错杀一个的西方文明世界的准则保证的是查准率。要想兼顾二者,做到打得准也打得全,那是很难的。于是我们挖煤工人有时不得不叹气,面对汪洋大海的语言自觉渺小,吾生也有涯,口水没有涯,殆矣,觉得没什么指望了,疑惑红旗到底可以打得多久?

但是,事实是,自然语言系统能否实用,很多时候并不是决定于上述两个学界公认的指标。在信息爆炸的时代,在面对海量数据的时候,还有一个更重要的指标决定着一个系统在现实世界的成败。这个指标就是系统的吞吐量(through-put),系统可以不可以真正地 scale-up。由于电脑业的飞速发展,硬件成本的下降,由于并行分布式运算技术的成熟,吞吐量在现实中的瓶颈主要是经济上的羁绊,而不是技术意义上的难关。运行一个 farm 的 servers,只要有财力维护,能耐的工程师完全可以做到。其结果是革命性的。这种革命性成功的最突出的表现就是 Google 和 Facebook 等公司的做大。

在处理海量数据的问题解决以后,查准率和查全率变得相对不重要了。换句话说,即便不是最优秀的系统,只有平平的查准率(譬如70%,抓100个,只有70个抓对了),平平的查全率(譬如50%,两个只能抓到一个),只要可以scale up,一样可以做出优秀的实用系统来,创造应用程式的奇迹。为什么?根本原因在于两个因素:一是爆炸时代的信息冗余度;二是人类信息消化的有限度。查全率的不足可以用增加所处理的数据量来弥补,这一点比较好理解。既然有价值的信息,有统计意义的信息,不可能是“孤本”,它一定是被许多人以许多不同的说法重复着,那么查全率不高的系统总会抓住它也就没有疑问了。从信息消费者的角度,一个信息被抓住一万次,与被抓住一千次,是没有区别的,信息还是那个信息,只要准确就成。问题是一个查准率不理想的系统怎么可以取信于用户呢?如果是70%的系统,100条抓到的信息就有30条是错的,这岂不是鱼龙混杂,让人无法辨别,这样的系统还有什么价值?沿着这个思路,别说70%,就是高达90%的系统也还是错误随处可见。这样的视点忽略了实际系统中的信息筛选(sampling)与整合(fusion)的环节,因此夸大了系统的个案错误对最终结果的负面影响。实际上,典型的情景是,面对海量信息源,信息搜索者的几乎任何请求,都会有数不清的潜在答案。由于信息消费者是人,不是神,吃的是五谷杂粮,用的是一目最多十行的双眼,靠的是总比电脑慢三万拍的人脑,即便有一个完美无误的理想系统能够把所有结果,不分巨细都提供给他,他也无福消受,simply overwhelmed,就好比再超人的皇帝也无法应对360后宫720殿一样。因此,一个实用系统必须要做筛选整合,把统计上最有意义的结果呈现出来。这个筛选整合的过程可以保证最终结果的质量远远高于系统的个案质量。

总之,size matters,多了就不一样了。那天跟镜子提到这个在黑暗与半明半暗中摸索了几十年悟出来的体会,镜兄气定神闲地说:“那自然,大数定理决定的”。好像一切都在他的预料之中!!

信息的关键载体之一是语言。只要有语言,就需要NLP,你说说NLP该不该有光明的前景?

Quote:
NLP is not magic, but the results you can get sometimes seem almost magical.
(“NLP 不是魔术,但是,其结果有时几乎就是魔术一般神奇。”)

引自:http://www.confidencenow.com/nlp-seduction.htm

相关博文:【据说,神奇的NLP可以增强你的性吸引力,增加你的信心和幽会成功率】
http://bbs.sciencenet.cn/home.php?mod=space&uid=362400&do=blog&id=434774

中文机器翻译沙龙第六次活动报名

本次活动由北大翻译协会与中文机器翻译沙龙联合举办。地址在北京大学理科楼,活动主题为计算机辅助翻译工具的评测, 欢迎对机器翻译、计算机辅助翻译感兴趣的人员报名,也欢迎专家、资深人士预约发言。

时间:2011年4月23日(周六)下午14:00-17:00

报名截止日期:4月21日(周四)

地点:北京大学理科楼

费用:无

主讲人:北京大学外国语学院翻译硕士教育中心 王华树

题目: 计算机辅助翻译工具的评测

报名请回复邮箱cmt.salon@gmail.com

北京大学语言信息工程系:www.pkucat.com

北大译坛:http://bbs.pkucat.com/

中文机器翻译的豆瓣小组是http://www.douban.com/group/304684/

中文机器翻译沙龙第五次活动小结

本次沙龙活动于3月27在清华科技园的泰为公司会议室举行。共有二十四人参加,包括来自泰为、百度、金山、高德、老虎宝典、索爱、Novell、ifeng等公司的人士,以及来自清华、中科院计算所、自动化所、北师大等高校的研究生。另外还有来自东北师大的研究生参加,这是首次有外地的沙龙参与者。

首先由国家知识产权局的王进先生介绍了他在机器翻译领域的研究成果----原型系统和句法分析。王进先生首先介绍了范畴语法,然后基于范畴语法的扩展建立了原型系统。他提出“突破句法范畴,定义语义范畴体系”以及“突破语言结构,定义范畴跳转规则”。然后给出了句法分析的例子,并演示了其构建的翻译系统。王进先生随后就大家感兴趣的问题与大家进行了交流。非常遗憾的是,限于时间关系,未能与王先生展开深入讨论。

然后来自中国科技技术信息研究所的宋培彦博士介绍了HNC(概念层次网络)的理论。我国中文信息处理的三大流派之一的HNC理论,是由中科院声学所的黄曾阳先生所提出的。“虽然世界上有6000多种语言,但概念空间基本稳定,而且互通,这是翻译的基础。” “HNC是对大脑的语言功能进行模拟。”HNC又具体到概念基元空间(HNC1):词汇及语义网络;句类空间(HNC2):句子;语境单元空间(HNC3):句群;语境空间(HNC4):篇章。HNC正在进行的天翼计划——机器翻译,“先理解,后翻译”,不要统计意义上的“硬译”,不要语法形式上的符号转换,直面理解。这些无疑对目前机器翻译的研究具有参考意义。宋博士的介绍深入浅出,使得大多数未接触过HNC的沙龙成员对其有了大概的认知。随后宋博士介绍了其在回指模糊消解方面所做的研究。随后大家就HNC目前的研究和发展状况进行了讨论,宋博士提出了HNC应该走向“通俗化”、“实例化”、“国际化”。

请求捐赠短信,为短信语料库的创建出一份力

大家好:

我们是来自新加坡国立大学计算机学院的研究人员。我们在6年前收集过英文短信,之后发布了10,000条英文短信的语料库,供研究人员免费使用。

目前我们重新启动了短信收集项目,扩展已有的英文短信,同时还为了创建中文短信库。该项目通过了新加坡国立大学学术委员会的审查。目前我们收集到 15,111条中文短信,语料库已经发布。详情见http://wing.comp.nus.edu.sg:8080/SMSCorpus/

短信属于隐私数据,收集十分不易。目前在学术领域,公开的短信数据库非常稀少。我们发这个帖子的目的,是让更多的人了解我们的工作,宣传我们的语料库,更重要地是希望你能够帮助语料库的创建。

希望大家能够捐赠一些自己的短信!为短信研究贡献自己的一份力量!捐赠短信的详细方法见项目主页(http://wing.comp.nus.edu.sg:8080/SMSCorpus/)的短信捐赠页面。在存入数据库前,我们会对收集到的短信做相应的处理,保护捐献者的隐私。

感谢大家!

ME for Machine Translation

利用周末时间细读了Och和Ney在02年ACL上发表的一篇关于Machine Translation的文章,做个笔记。

Discriminative training and maximum entropy models for statistical macine translation

1. ME 模型是在噪声信道模型的基础上改进而来的。

2. Source-Channel Model 被称为“Fundamental Equation of Statistical MT”,即,机器翻译的基本方程式。

3. 噪声信道模型存在的几个问题:

(1)噪声信道模型中,当翻译模型和语言模型只有在语料上的实际值等于理论值的时候,翻译结果才能达到最优;如果有一种更好的能将LM和TM进行结合的方法,那么翻译效果会有很大的提升。

(2)噪声信道模型不能通过直接扩展可对MT产生帮助性作用的特征和信息来扩展统计MT 系统。

(3)噪声信道模型的翻译模型具有可对称性特点。p(f|e)与p(e|f)在模型中可产生相当的作用,都可以与语言模型一起在信道模型中产生作用。虽然在噪声信道理论框架中难以对这种现象进行分析解释,不过产生的翻译效果却极具有可比性。在实际的统计翻译中,可以通过比较其作用好坏,按需选择来使用。

ME Translation Model

由于噪声信道模型能够融入的信息较为有限,Och 等人提出了采用ME 来进行统计翻译的方法,这主要是由于ME 具有可将多种信息进行有效结合从而为翻译提供支撑的特点。ME 方法是对噪声信道模型的改进。在该理论中,可以将N个信息同时考虑在MT 的过程之中,每一个信息被视为一个特征(或者叫做特征函数function),每个特征对应一个参数a,翻译概率的计算就跟这些特征函数和参数有关。(详细计算公式见论文第3页)

实际上,噪声信道模型的MT方法是包含在ME 方法框架之内的,当特征1:

h1(e,f) = log p (e)

特征2:

h2(e,f) = log p (f|e)

并取参数a1=a2=1的时候,ME 表现出来的框架其实就是噪声信道。

Alignment Model and Maximum Approximation

另外,在翻译的过程中还有一个很重要的因子------对齐。不管是噪声信道还是ME,在翻译过程中都需要计算源语言到目标语言的对齐,这个贯彻翻译概率计算过程的始末。

Och等在当年的系统中采用的是Alignment Templates的方法。即,只有源语言短语、目标语言短语的短语表,i.e.,短语表。

Training (a参数的训练)

文中采用的是GIS 算法(Darroch and Ratcliff,1972)。

CFP: The 7th Young Researchers' Roundtable on Spoken Dialogue Systems

Second Call for Papers and Participation
The 7th Young Researchers' Roundtable on Spoken Dialogue Systems
(YRRSDS 2011)
www.yrrsds.org

The Young Researchers' Roundtable on Spoken Dialog Systems (YRRSDS) is an annual workshop designed for graduate students, post-docs and junior researchers working in research related to spoken dialogue systems in both academia and industry. The YRRSDS provides an open forum where participants can discuss their research interests, current work and future plans. Previous workshops have been co-located with SIGdial or InterSpeech, and YRRSDS 2010 was recently held in Japan. YRRSDS 2011 will be hosted by the Oregon Health & Science University in Portland, OR, USA, and will be directly before SIGdial and ACL 2011.

The workshop has three main goals:
* to offer an interdisciplinary forum for creative thinking about current issues in spoken dialogue systems research
* to provide young researchers with career advice from senior researchers and professionals from both academic and industrial backgrounds
* to develop a stronger international network of young researchers working in the field

Submission Information:
We invite any researcher who is at a relatively early stage of their career (e.g students, post- docs, or junior researchers in industry) to submit a 2-page position paper. This should include their past, present and future work, a short bio and topic suggestions for the workshop. Acceptance is on a first-come, first-served basis and the number of participants is generally capped at 50. Poster presentation by all participants is expected. However, posters need only present current work and are not necessarily from a published paper. Further format and outline information are provided at yrrsds.org under Submissions.
Please submit via the EasyChair system:
https://www.easychair.org/conferences/?conf=yrrsds2011
If you experience any problems with submission please contact the organizers at:
yrrsds2011 at gmail.com

Important Dates:
Submissions deadline: April 22, 2011
Author notification: May 9, 2011
Camera ready deadline: May 20, 2011

YRRSDS'11 will feature:
* a senior researcher panel (both academia and industry)
* a demo and poster session (Best Poster Award!)
* a special session on Embodied Conversational Agents
* two Roundtable discussion and presentation sessions

Some Topics of Interest (more complete list at yrrsds.org)
* Models of dialogue: Statistical, Symbolic and Hybrid dialogue modeling
* The Spoken Dialogue Challenge: SDS evaluation
* Psycholinguistic influences of dialogue system design
* Dialogue system development beyond ''toy'' research domains
* The importance of establishing social relations with the user in automated dialogues
* Interacting with virtual and robotic agents
* Semantics and Pragmatics of dialogue systems
* Context and spoken dialogue systems
* Building truly incremental spoken dialogue systems
* Dialogue data collection, sharing data sets and formats for statistical models
* Understanding industry development cycles, requirements, and future application
domains for dialogue systems

We thank our Sponsors:

* Microsoft Research
* AT&T Research
* LG
* BioSpeech
* Nuance
* IBM Research

YRRSDS 2011 is endorsed by:

* SIGDIAL
* ISCA and ISCA SAC
* ACL
* Dialogs on Dialogs

Organizing Committee

William Y. Wang, Columbia University, USA
Khan Md. Anwarus Salam, The University of Electro-Communications, Japan
Sungjin Lee, Pohang University of Science and Technology, Korea
Lina Maria Rojas Barahona, LORIA, France
Hamid R. Chinaei, Laval University, Canada
Ethan Selfridge, Oregon Health & Science University, USA

理解EM算法

EM(Expectation-Maximization)算法在机器学习和自然语言处理应用非常广泛,典型的像是聚类算法K-means和高斯混合模型以及HMM(Hidden Markov Model)。笔者觉得讲EM算法最好的就是斯坦福大学Andrew Ng机器学习课的讲课笔记和视频。本文总结性的给出普遍的EM算法的推导和证明,希望能够帮助接触过EM算法但对它不是很明白的人更好地理解这一算法。

EM算法的目标是找出有隐性变量的概率模型的最大可能性解,它分为两个过程E-stepM-stepE-step通过最初假设或上一步得出的模型参数得到后验概率,M-step重新算出模型的参数,重复这个过程直到目标函数值收敛。我们设观察到的变量所组成的向量为[image],所有的隐性变量所组成的向量为[image],模型的参数为[image](一个或多个参数)。在聚类的情况下,[image]是潜在的类,而[image]就是需要分类的数据。我们的目标就是找出模型的参数[image]使得[image]出现的可能性最大,也就是使下面的对数可能性最大化:

[image]

注:这里仿照Andrew Ng 的用法使用[image]而不是[image],因为[image]是模型的参数而不是随机变量。关于为什么要用EM算法而不是不直接通过[image]得出[image],是因为这样可能会出现严重的overfitting (这里不详细说明,请参看Pattern Recognition and Machine Learning一书9.2.1)

假设[image][image]上一个概率分布,所以[image]

[image]

最后一步是根据Jensen不等式[image]如果[image]是凹函数,在这个式子中就是对数函数。[image]就是[image][image]就是[image] [image]是严格的 凹函数的时候,[image]中等号成立的条件是[image]是常数,也就是说在这个特定的式子中[image],满足这个条件加上之前的[image][image]其实就是后验概率[image](参看http://www.stanford.edu/class/cs229/materials.html Lecture notes: The EM Algorithm)。这就是EM算法中E-step的由来。

M-step一般来说就是个就是二次规划的问题,通过[image]得出[image]。这里也就不再赘述。

EM算法其实就是coordinate ascent E-step是将[image]视为常数,选择一个概率分布[image]使得目标函数[image]最大化, M-step就是保持[image]不变,选择[image]使得目标函数[image]最大化,因为每一步的目标函数都比前一步的值大,所以只要目标函数存在最大值,EM算法就会收敛。这个过程用图像表示就是:

E-step找到跟[image](黑色弧线)交于[image][image](蓝色弧线),M-step得到[image]取最大值时的[image],这样下去直到收敛。(此图源于Andrew)