漫话匹配学习(Learning to match) 与Q&A

李航在2012年的一年共做了四篇关于匹配学习的报告,大致内容一致。
2012. 07 mmds_2012 @Stanford University
Large Scale Machine Learning for Query Document Matching in Web Search
2012.08 sigir2012_tutorial
Beyond Bag of Words Machine Learning for Query-Document Matching in Web Search
2012.08 yssnlp_2012
Learning to Match for Natural Language Processing and Information Retrieval
2012.11 MLA @Tsinghua
Learning to Match
匹配学习的动机是什么?
主要是为了解决Query – Document相关度匹配问题。
因为很多相同的Search意图的人会输入很多各式各样的Query表示形式。
从微软搜索引擎Bing的Search log中可以看到有很多实例性问题,如:
查询“Distance between Sun and Earth
• “how far” earth sun                               • distance from earth to the sun
• “how far” sun                                        • distance from sun to the earth
• “how far” sun earth                               • distance from the earth to the sun
• distance from sun to earth                   • average distance earth sun
• average distance from earth to sun     • average distance from
• how far away is the sun from earth      • how far away is the sun from the earth
• how far earth from sun • how far earth is from the sun

口语化及非法的语法结构错误

查询“Youtube
• yutube                       • ytube
• youtubo                     • youtube om
• youtube                     • youtub com
• youtub                       • you tube
• you tube videos         • www youtube
• yotube                       • ww youtube com
• utube videos             • u tube com
• u tube • outube
拼写错误
在一个检索系统中,为解决以上问题,匹配任务就构成塔级结构:(语义等级自下至上提高)

Term[词]级:作为语言的最小单元,匹配任务:拼写纠错检查;
例,检查NY、youtube这样的单词是否拼错。
Phrase[短语]级:Term[词]构成Phrase[短语],匹配任务:Term组合;
例,hot dog词在一起时就要考虑搭配到一起,是否为热狗面包。
Word Sense[词义]级:匹配任务:同义词替换、缩写展开等操作;
例,口语化的utube(youtube)及以首字母缩写词NY(New York)。
Topic[主题]级:提取短语的主题词,进行相内容关扩展;
例,提到Micosoft Office时就应该能扩展到PowerPoint,Word, Excel..等。
Structure[结构]级:匹配任务:规范化句子结构。
例,How far is sun from earth这样的句子结构可以转变为:distance between sun and earth.

英文系统中Term都是一个个单词,对于中文的检索系统来说,Term是切词之后的词。
为实现这样的匹配任务就要从客户服务两端同时进行预处理工作,文本理解:
客户端,输入一个Query。比如用户输入:
michael Jordan berkele


Query的理解过程如下:
1). 拼写检查:发现berkeley拼错;
2). 短语识别:[michael Jordan] Berkeley;
3). 相似查询:michael I. Jordan Michael jordan;
4). 主题标识:识别与berkely相关的michael jordan是机器学习届的大牛,不是篮球明星jordan
5). 结构识别:标注中心短语就是michael jordan。
服务器端,存储一些Document,比如抽取michael jordan主页中的一段内容:
Michael Jordan is Professor in the Department of Electrical Engineering

Document的理解过程如下:
1). 短语识别:[Michael Jordan] is [Professor] in the [Department] of [Electrical Engineering];
2). 关键短语:把[Michael Jordan]、[Professor]和[Electrical Engineering]标为关键短语;
3). 主题识别:识别Michael Jordan的主领域为machine learning;
4). 标题结构:中心短语为Michael Jordan。
有了这样的预处理工作,那么Online Matching的Basic idea应该是:

匹配过程就可以在不同的级别中进行。
匹配工作涉及到的内容包括:IR技术、查询扩展、伪相关反馈、LSI、LDA及目前遇到的新问题:大数据和新机器学习技术。
关于匹配和排序。在Search中,是一个先Matching再Ranking的顺序。匹配与排序任务的功能、模型与挑战如下:

[参考1]: Large Scale Machine Learning for Query Document Matching in Web Search

现在,我们先考虑Query Refinement的问题,也就是如何去做一个客户端的查询优化。
Query Refinement的目标:通过对ill-fromed search query的 重组变形操作 来提高查询结果的相关度。
典型的任务有:Spelling error correction, word splitting, word merging, phrase segmentation, word stemming和acronym expansion.
一般来说,这些优化任务是串级结构完成的,计算所程学祺团队几个任务整合到一个CRF-QF模型中来完成。训练的数据来源是商业搜索引擎Bing的query log数据
[参考2]: A Unified and Discriminative Model for Query Refinement

针对当前Q&A的特点为:
1). 中文知识问答系统;2).结构化数据存储;3).缺乏query log数据
语言学角度建立的一个初级模型,首先可考虑的查询优化任务为:
0). 同义词扩展; 1). 查询词纠错; 2). 中文机构简称扩展.
0). 同义词扩展
{作曲, 曲作者, 谱曲}
{作词, 作词者, 填词}
1. 查询词纠错
查询词纠错主要是为了反向推测用户输入,在确定查询信息出错时,给出纠错推荐词。
一个查询语句有多种输入方式,常见的方式有:键盘输入、语音识别、OCR识别、电子扫描等。我们仅考虑基于拼音的键盘输入方式
也正是因为拼音输入法学习成本低、思维干扰少、普及广等因素,造成用户输入的中文查询信息两大特点:
a). 可能是别字或冗余字,但不会是错字符,即必是汉字编码字符集中的单字;
b). 错误信息最多的是同音别字错误,而多字漏字情况多事由于不小心输入错误。
Sogou实验室提供的部分查询日志可证实这一点[4]。因此,主要应解决以下问题:
1.1. 同音别字问题
错误输入如:[药名]的身高是多少?姚明
[理想]是哪个电视台主持人?李湘
建立基于拼音的同音词典进行纠错推荐;

1.2. 短语级多字漏字别字问题
错误输入如:[中科院自动所]在哪里?自动化所
从大数据库中匹配短语级相似字符串的算法中,通过2-gram倒排索引是一种易于实现,能够快速、准确、低耗的从海量级短语集中剔除掉海量无关的数据项,然后引入广义编辑距离概念进行再次过滤,得到匹配度比较高的相似短语。
以GB2312字符集为例,GB2312共收录了6763个汉字。根据汉字的区位码,选取适当的Hash函数把GB2312字符映射到一维空间中。
按照一个字符占用4个字节计算,那么建立一个Unigram单字索引结构(除去地址列表)占用空间26.42KB,一个2-gram索引结构占用空间174.5MB。
例如:索引的文本中只有两个短语句(或词):

中文字符串匹配与复制
字符串复制

那么拆分得到的Bigram项和地址列表:

注:<0,0,0>表示<文件号, 段号, 偏移量>, 对于2-gram索引,偏移量也可忽略而减少存储空间。
当用户输入待匹配句子 字符串匹配。 获得各个Bigram项的一、二级索引下标并提取各Bigram项的地址列表:

这样就从地址列表中提取出了相关项,然后根据编辑距离的概念进行过滤。
[参考3]相似字符串匹配过滤算法研究
Lucene中默认采用的CJK切词包就是通过2-gram建立的索引结构。

1.3. 基于拼音的编辑距离
同音别字其实是基于拼音编辑距离为0的一种特例。
中文拼音与英文的不同在于,中文有标准的音节:汉语普通话中的无调音节(不做音调区分)共有400个音节。一个汉字音节,包括声母23个、韵母24个和整体音节16个:
声母:b p m f d t n l g k h j q x zh ch sh r z c s y w
韵母:a o e i u v ai ei ui ao ou iu ie ve er an en in un vn ang eng ing ong
整体认读音节:zhi chi shi ri zi ci si ye yi yin ying wu yu yue yun yuan
那么把拼音串简单地看作广义的英文字母串,则替换、插入或者删除一个字母后,所得结果不一定是合法的拼音串。因此应从音节的角度来分析拼音串的差别。
这样的话,一个出错的拼音串总可以分解为:声母变化和韵母变化。给出一个现有音节,很容易枚举出所有与它编辑距离为n的音节。
错误输入如:[姚敏]的身高是多少?yaomin à yaoming? 姚明
语言学中讲,有9对发音相似的声母对和韵母对是最容易发生替换错误的,包括:/l/和/n/、/z/和/zh/、/c/和/ch/等声母对,/in/和/ing/、/en/和/eng/等韵母对。
例如:/li/和/ni/的编辑距离是1 ,/li/和/pi/的编辑距离也是1。但是这2 组音节的差异从发音机理角度来看,/li/与/ni/更加近似。类似的例子还如:音节/lin/与/ling/的差异较小,而/lin/和/lan/的差异较大。
那么在没有大量语料库进行统计的情况下,仅由语言学知识可知,这些音节之间的相似匹配度更高。
[参考4]基于拼音索引的中文模糊匹配算法

1.4 推荐词排序
在句级上下文关系中,分析词与词之间的相互依存关系,进行排序推荐。
如 <姚明, 身高>,<李湘, 主持人> 等。
相关统计库:1,Sogou实验室提供Web域的1840W词对及相应词频;
2,计算大脑抽取的结构化三元组节点关联信息。

2. 中文机构简称扩展问题
与机构名类似的是中国地名,但中国地名虽然用词分散,却很少有缩略叫法。在<中华人民共和国地名录>收录了从高原盆地到桥梁电站共10万多个地名。
令人苦恼的是,很少有人称呼机构名的全称,缩略语最为常见,如:“发改委”,“北医三院”,还有一些奇怪的缩略简称如:“人影办” 为 “人工影响天气办公室”的简称。
[参考5]漫话中文自动分词和语义识别

那么对于中文机构名,需要解决的是简称与全称的匹配问题。
2.1 采用BMBoyer-Moore)算法查找子字符串
例,输入:中移动,可以匹配到 “中国移动有限责任公司”。
但,虽然很好的查询到了包含子字符串的机构名,却没法很好解决简称与全称的匹配问题。
例,输入:中石化
BM算法会匹配到:“中国实话齐鲁石化有限公司”,而不是 “中国石油化工有限公司”。
2.2 另一种方式就是:制定规则生成方法
机构名的结构:根据1999年12月8日国家工商行政管理局令第93号公布的《企业名称登记管理实施办法》, 企业名称一般由行政区划字号行业组织形式依次组成, 因此公司名可结构化地描述为【所属地】+【固有名称】+【行业性质】+【组织形式】,如“中国移动有限责任公司”;其他的机构名如清华大学等大学名称,也可归为以上结构。可见机构名的构成是有一定的规则的。
如:“北京”,“中国”等 属于区域类;
“石油”,“化工”等 属于行业类;
“有限公司”,“大学”等 属于组织结构类;
不属于以上关键词 即固有词 属于未知类。
而标识一个公司的关键部分在于固有词。那么对于一个机构全称可以通过分词工具划分出确定的区域类、行业类、组织结构类,剩下部分就为未知类。
a). 机构名的全称规则
全称规则描述形式:
Rule 0: <RegionName> <Unknown> <IndustryType> <OrgType>
Rule 1: <Region Name> <IndustryType> <OrgType>
Rule 2: <Unknown> <OrgType>

大约生成20多种相应规则,大部分机构名可归为其中的一种规则。
例,“北京斗牛士贸易公司”分词后为“北京/RegionName 斗牛士/Unknown 贸易/IndustryType公司/OrgType”
b). 机构名的简称规则:
制定一个词的属性有以下5类,Full, Null, LeftCC(n), RightCC(n), GetCC(i,j,…)。
简称规则描述形式:
AbbRule 0: Rule 0 <RegionName> + <Unknown>
AbbRule 1: Rule 0 <Unknown> + <IndustryType>
AbbRule 2: Rule 1 <RegionName>.LeftCC(1) + < IndustryType >
AbbRule 3: Rule 2  <Unknown>

以AbbRule 2: Rule 1为例:“中国移动有限责任公司” “中移动”
通过这种制定规则对数据库进行词条扩展。
[参考6]基于中文机构名简称的检索方法研究

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>