基于语义关联的中文查询纠错框架
基于语义关联的中文查询纠错框架
本文作者：内部搜索平台部推荐中心组长，2009年加入腾讯，从事搜索相关工作，包括社区问答，网页搜索，音乐、视频、应用宝等项目，方向涉及query理解，文本相关性、智能问答等。目前从事天天快报、新闻客户端等资讯个性化，包括用户兴趣、推荐策略、工程架构等。
搜索引擎中, 一个好的纠错系统能够将用户输入查询词进行纠错提示, 或者将正确结果直接展示给用户，提高了搜索引擎的智能化。和传统文本纠错相比, 搜索引擎的纠错具有几个难点. 一是搜索引擎的query很短, 由几个独立的key words组成（Chen et al ,2007);二是用户输入比较随意, 错误串的比例高达10-15%(Cucerzan and Brill, 2004). 第三，在移动设备上，由于屏幕小，存在大量手写和语音输入，使得用户写错的比例更加严峻。
查询纠错主要是基于web和query logs作为语料训练模型来推断用户输入是否错误进行纠错. 还可以通过分析用户的sessions和点击行为，结合点击doc的特征信息，分析出用户的改写行为，挖掘一批置信度较高的纠错对。以上两种方法都有一个前提, 搜索引擎必须要有超大规模的web语料、搜索logs和用户点击数据，数据规模的大小直接决定了纠错系统的好坏，例如session数据足够大，离线挖掘出的纠错对就可以覆盖很高的错误比例。而这些大规模的数据只有若干几个商业搜索引擎才能得到，小的垂直业务数据规模非常小。
对于垂直搜索引擎,尤其是比较小的垂直apps,如何进行查询纠错,文献中基本没有探讨过. 普遍做法是,使用商业搜索引擎中网页搜索训练的纠错模型直接作用在垂直引擎中。但是在我们调研过程中, 发现不同的垂直业务, 用户的检索目的是不一样的，从而导致纠错的也不是通用的.例如,用户输入”消星星”, 在音乐业务中, 应该纠错成一首歌曲——”小星星”; 而在游戏app分发平台上就应该纠成一个游戏app——”消灭星星”。
文献研究传统文本纠错包含两种类型, 一种是“单词”错误的纠错类型, 另外一种是“词条搭配”的错误类型. 早期的纠错一般是第一种,使用编辑距离进行相近查找（Eg, Kucich, 1992; Kernighan et al., 1990; Brill and Moore, 2000; Toutanova and Moore, 2002)。第二种错误类型，通过探测query中词条的上下文搭配来判定是否存在错误，使用噪音信道和语言模型作为纠错的主要方法(Eg. Church et al., 2007)。例如, "peace" and "piece"在上下文"a _ of cake"中只能用"piece"。英文中也有将二者结合训练模型进行预测，进行单词字符的纠错（Eg. Noura et al.,2014）。从方法论上, 又分为基于词典和基于模型两种纠错模型. 前者通过离线建立或者挖掘好的词典，进行查找，判定是否需要进行纠错。后者是近些年研究的热点, 在大规模web语料和query logs的基础上, 使用噪音信道，语言模型，排序模型，分类模型等进行纠错（Eg, Cucerzan and Brill 2004; Ahmad and Kondrak, 2005; Li et al., 2006; Whitelaw et al., 2009）。
最近的研究文献中提出了一些纠错框架。一种是使用排序的方法, 对候选结果计算多个维度特征得分, 通过排序公式计算最终得分，取top N或者得分超过一定阈值进行展示（Eg, Jianfeng Gao, 2010）。另一种是将问题转化分类问题, 标注一些正负实例，正例是出正确纠错结果,负例是不出结果或者出错误的结果，离线训练一个二分类模型，在线进行预测（Eg, Alexey Baytin 2013）。
通过用户行为挖掘潜在的纠错对, 也是近些年的研究热点. Liyun ru 2013在文献中进行了概括，首先根据用户cookie和时间序列将连续搜索行为划分成若干session；然后依据 search和click的行为特征从session中挖掘尽量多pair作为候选结果；最后结合doc和query等特征对候选结果进行排序, 得到精度较高的纠错对。
和英文纠错相比，中文纠错面临的问题更为严峻. 首先，中文term之间没有分隔符，不能使用term本身进行错误识别，必须依赖于上下文。其次，中文的输入法类型较多，除了拼音还有五笔等字形输入法，再加上无线设备屏幕和键盘都很小，手写设备和语音输入都很频繁，使得错误类型更多。例如，“泡沬”和“泡沫”，“沬”、“沫”字形上相近，自身都是正确的汉字，必须依赖上下文。
几乎所有文献讨论的基本都是基于网页搜索的查询纠错, 很少有文献对垂直搜索的查询纠错进行讨论，本文详细阐述了垂直搜索和网页搜索的差异, 并提出了一个基于垂直搜索的纠错框架DCQC.
垂直搜索特点
垂直搜索和大网页搜索存在比较大的差异, 从四个方面进行阐述. 首先网页搜索意图较为发散, 用户需求多样性，例如“导航”“天气”“股票”“视频”等; 而垂直业务中用户意图是明确的, 比如在音乐app中搜索，用户就是查找”歌曲””歌手”“专辑”“mv”等；在视频app中查找”电影””电视剧”“综艺节目”等。其次是数据量, 网页搜索需要索引几乎所有的web网页(千亿级别), 而垂直业务只需要索引特定领域内的所有数据即可, 例如音乐领域只有百万级别歌曲。第三，用户的搜索和点击logs在量上也没有可比性，网页搜索每天会产生上亿的query logs，并且会有专门的团队进行去噪；而垂直apps，query logs噪音很大，甚至一些apps中的search和click的记录都不完善，可用性很差。第四，网页搜索的商业搜索引擎很少，例如google，baidu，bing等，有专业团队进行用户行为分析，研究查询纠错算法；而垂直apps有上百万，有很多都有搜索的需求，并且开发团队较小，没有精力开发查询纠错系统。
垂直apps爆发式的增长，也反映了互联网的发展从pc向无线客户端的转移，一套针对垂直业务的通用纠错框架迫在眉睫。
基于垂直搜索的纠错框架DCQC和网页搜索进行对比，垂直apps可使用的数据量小，噪音大，并且不同app都有自身的特殊需求，纠错结果差异很大，需要量身定制。我们提出一套针对垂直业务的通用纠错框架——DCQC（Domain Common Query Correction)，由召回层和决策层两层组成，可以方便扩展到任何领域，搭建一套满足业务自身需求的纠错系统。
召回层由一个或多个独立的集群组成，每个集群管理一个领域数据。优势在于一个领域的所有垂直apps可以共享数据，不同领域下的垂直apps所使用数据不交叉，保证了不同领域下纠错需求多样性。索引模块类似网页搜索的索引模块，使用倒排索引形式，建立汉字和拼音两个维度下的多种倒排。检索模块从汉字和拼音两个维度进行查找，对候选结果进行粗排序，保留一定数量的结果进入策略模块。不同领域集群，除了数据不一致，其他都是通用的，可以任意扩展。
Figure 1 DCQC框架
决策层是精计算阶段，对召回层传上来的结果进行特征计算，使用多种模型进行预测，业务还可以插入自身需求的策略代码，对结果做到个性化。
路由模块：可以根据业务需求指导召回哪些领域集群的数据，一般情况下一个垂直app只召回本领域集群的数据，但也有一些业务横跨好几个领域，例如一个娱乐app，需要music和video两个领域数据，业务可以进行简单的配置完成这个功能。
特征计算：包括五个维度的特征。一是用户特征，包括地域、年龄等，例如广东人容易将拼音‘f’写成‘h’，所以这些特征可以更好的计算转移概率。二是拼音特征，由于拼音输入法流行，大部分错误都是拼音错误，包括全拼，简拼，模糊音，声母编辑距离、韵母编辑距离等。三是字形，包括笔顺，五笔等，例如“自己”错误写成“自已”。四是数据资源权威度，包括领域内资源的热度和检索频次等，例如，音乐app中歌曲的播放次数。五是以上基础特征的统计和排名信息等。
在线预测：这个模块包括一些基础模型和预测模型，基础模型包括语言模型，关联模型等。预测模型有排序模型，分类模型等。文章中使用了svm分类模型，对结果进行二分类，并且根据用户的log反馈，进行自学习。
语义关联在垂直app和web页面中，资源数据之间不是孤立的，而是存在着某种联系。我们先看一些例子，音乐app中，歌手“吴俊余”演唱过歌曲“17岁的雨季”，这两个数据资源就是一种“演唱”关系；在视频app中， 电视台“湖南卫视”制作了一档娱乐节目“变形计”，这两个数据资源是一种“制作”关系。同样的道理，音乐业务中还存在，歌手“演唱”歌曲， 歌手“发行”专辑，专辑“包含”歌曲等；在视频业务中，导演“拍摄”电影，演员“出演”电影，演员“出演”娱乐节目，导演“拍摄”电视剧等；在小说业务中，作者“创作”小说，小说“包含”主人公等。
定义1：资源数据——在垂直业务中，数据会分为若干的分类，每个类别中可以单独表述完整意义的词条。例如，音乐业务中，歌曲、歌手、专辑、mv、歌词这些类别覆盖的数据都是资源数据。
定义2：数据关联——如果两个资源数据存在着某种关系，则这两个资源数据就存在数据关联。
定义3：关联热度——两个关联资源共同被作用的频次。例如，两个被共同点击的次数，或者在web中出现在同一段话中的频次等。
关联挖掘
在实际项目中，关联数据一般从两个方面进行建设。首先，垂直业务自身数据之间存在大量的关联，垂直业务中的一条记录包含若干字段，那么这条记录中的任何两个字段之间都有关联关系。这些数据是关联数据的主要组成部分，也是垂直业务的自身优势。
其次，是从web页面中进行挖掘，传统的知识图谱是由三元组（spo）组成，关联挖掘最大的差异是，只需要挖掘存在一定关系的两个数据，不需要记录非常明确的关系。大致流程如下：一是对句子进行句法分析，从句法树中查找主语（s）、谓语（p）、宾语（o）三个部分，选取主语（s）和宾语（o）作为候选关联数据；其次是结合垂直数据和query logs对候选进行统计，筛选频度较高的放入关联数据集合。
关联纠错在分析query logs中，发现一个有意思的现象：很多查询串往往包含两个或多个资源片段，并且这些query错误比例很高。分析原因应该是用户输入多个片段是为了得到一条明确的结果，而不愿意拿到一个结果列表；而错误比例较高应该是用户记忆比较模糊，希望使用两个或多个资源片段的关联关系得到明确的结果。但是如果其中一个片段或者多个片段存在错误，则结果会非常差，因为这些片段自身可能都代表一个正确的资源。例如，视频app中query“变形记 湖南卫视”，包含两个资源片段，电影“变形记”，电视台“湖南卫视”，两个资源都是正确的，而这两个资源没有任何关系，这种情况可能存在错误，用户真正想要的是“湖南卫视”的一档娱乐节目“变形计”，正确纠错形式应该是“变形记 湖南卫视”->“变形计 湖南卫视”。音乐app中更多例子如下：
关联纠错就是使用数据之间的关联关系，对用户输入的多个资源片段判定是否存在错误，继而进行纠错处理。因为每一个资源片段可能都是正确的资源，纠错的目的是寻找多个片段的是否存在语义关联，所以这种纠错是一种新的纠错类型。我们将整个过程分为三个步骤：
第一步，片段切分。将整个query切分成一些可以独立表达的语义片段，切分过程中尽量保证资源的完整性。
第二步，片段之间计算是否存在关联关系。如果存在关联关系则退出，否则对每个片段查找候选结果。算法使用噪音信道模型，从看到的query output(O)，推测正确的候选 input(i),取得分最高的若干最为候选。
第三步，将每个片段的候选结果进行拼接，拼接后可能有多个串， 使用关联关系计算得分，返回得分最高的一个作为纠错结果。算法表述如下，假设一个query拆分成两个片段S1和S2对应的纠错串<S1,{S11,S12}>和<S2,{S21,S22, S23}>算任意两两组合得分，其中u(si)、u(sj)分别代表S1和S2基于噪音信道模型计算的得分，f(si,sj)表示si和sj在关联数据中的热度，f(si)、f(sj)分别代表si和sj自身的热度。取得分最高的1组作为最终结果。
数据集合我们选取一个垂直app——QQ music来验证我们的算法，qq music是腾讯公司推出的中文最大的网络音乐平台，每天约6000w左右的搜索量。从一个月的query logs中，随机抽取3w条query，分别抓取baidu网页搜索纠错结果和自身纠错结果， 取两个纠错结果的并集共3.1k，进行人工标注，其中有200条存在关联纠错，作为实验的数据集合。抓取baidu网页搜索的纠错结果，主要是为了对比垂直纠错框架和网页搜索纠错效果进行对比，而baidu是中文网页搜索中最权威的。人工测评在3.1k数据集合上和网页纠错对比，召回提高了28.5%，F1提高了0.26。在200条存在关联纠错的集合上，我们的方法召回提高42.4%，F1提高了0.39.说明我们的垂直通用纠错框架（DCQC）和关联纠错算法能够明显胜出网页搜索的纠错结果,也证明了垂直业务需要搭建自身纠错系统的必要性。
Webpage vs domain （ALL data set）
Semantic Association Correction （small data set）
线上用户点击对线上流量进行随机切分三分，每一份代表一种纠错算法，使用用户的真实点击数据进行对比。为了排除排序位置的影响，只取第一条结果的点击数据进行分析。实验证明，和原始query相比，网页纠错后用户点击率提高2%，我们的框架能够提高8.4%， 效果更为明显。
未来展望由于互联网向无线客户端转移，垂直业务越来越多，所以垂直搜索的纠错很有必要性。在分析了和网页搜索的差异，本文提出了针对垂直业务的通用纠错系统框架DCQC，实现了工程开发，具有良好的通用性和扩展性，成功应用在腾讯公司的音乐，视频等垂直业务中。提出了新的纠错类型——关联纠错，利用垂直业务中资源数据的关联关系，进行多片段的错误判定和纠错处理。实验表明DCQC和关联纠错都可以取得很好的效果。
实际项目中也发现一些问题，发现垂直apps中用户不是查找某一个明确的资源，而是为了查找某一类型的结果，是一些语义搜索，这种情况下，容易产生过纠现象。如何在垂直搜索中引入一些网页的数据，以及如何更好地开放给更多的小开发者，是我们下一步要做的工作。
ReferencesChen, Q., Li, M., and Zhou, M. 2007. Improving query spelling correction using web search results.In EMNLP-CoNLL, pp. 181-189.
Cucerzan, S., and Brill, E. 2004. Spelling correction as an iterative process that exploits the collective knowledge of web users. In EMNLP, pp. 293-300.
Kucich, K. 1992. Techniques for automatically correcting words in text. ACM Computing Surveys,24(4):377-439.Kernighan, M. D., Church, K. W., and Gale, W. A.1990. A spelling correction program based on a noisy channel model. In COLING, pp. 205-210.
Brill, E., and Moore, R. C. 2000. An improved error model for noisy channel spelling correction. In ACL,pp. 286-293.
Toutanova, K., and Moore, R. 2002. Pronunciation modeling for improved spelling correction. In ACL,pp. 144-151.
Church, K., Hard, T., and Gao, J. 2007. Compressing trigram language models with Golomb coding. In EMNLP-CoNLL, pp. 199-207.
Noura Farra, Nadi Tomeh†, Alla Rozovskaya, Nizar Habash. 2014. Generalized Character-Level Spelling Error Correction. In ACL.pp.161-167
Cucerzan, S., and Brill, E. 2004. Spelling correction as an iterative process that exploits the collective knowledge of web users. In EMNLP, pp. 293-300.
Ahmad, F., and Kondrak, G. 2005. Learning a spelling error model from search query logs. In HLTEMNLP,pp. 955-962.Li, M., Zhu, M., Zhang, Y., and Zhou, M. 2006. Exploring distributional similarity based models for query spelling correction. In ACL, pp. 1025-1032.
Whitelaw, C., Hutchinson, B., Chung, G. Y., and Ellis, G. 2009. Using the web for language independent spellchecking and autocorrection. In EMNLP, pp.890-899.
Jianfeng Gao,Xiaolong Li,Daniel Micol. 2010. A Large Scale Ranker-Based Systemor Search Query Spelling Correction. Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 358–366.
Alexey Baytin Irina Galinskaya Marina Panina Pavel Serdyukov. Speller Performance Prediction for Query Autocorrection. CIKM’13, Oct. 27–Nov. 1, 2013, San Francisco, CA, USA.
Liyun RU, Canhui WANG, Yingying WU, Shaoping MA. Search Query Correction based on User Intent Analysis. Journal of Computational Information Systems 9: 6 (2013) 2157–2166.
Xiaodong Liu, Fei Cheng, Yanyan Luo, Kevin Duh and Yuji Matsumoto. A Hybrid Chinese Spelling Correction Using Language Model and Statistical Machine Translation with Reranking. Proceedings of the Seventh SIGHAN Workshop on Chinese Language Processing (SIGHAN-7), pages 54–58.