Bengxy

聊一聊Query的拼写纠错

搜索系列

字数统计: 1.1k阅读时长: 4 min
2017/08/01 Share

背景

在搜索引擎中,用户输入的检索词(Query)通常会出现拼写错误。如果直接对错误的Query做匹配,通常不会得到用户想要的结果。

因此,首先需要对用户的Query进行纠错,获得用户最大概率想搜的Query。

taobao

baidu

要解决这个问题,一个简单的做法是根据同音词去匹配相似的、并且有含义的词组。

但是这种方法存在一定的局限性,比如在遇到英文单词匹配,或者是同音的词语很多时,算法都不能很好的work。

因此,我们需要一个能解决复杂场景下拼写纠错的算法。

主要Task

在中文搜索引擎的拼写纠错任务中,其实有这么几个主要的task:

  • 中文同音字纠错
  • 中文相似字纠错(针对五笔、移动端笔画、手写输入法等)
  • 中文拼音的推导
  • 英文推导

其中中文拼音和英文之间又有一些歧义需要推断和处理。像long这个单词可以表示龙(中文拼音),又能表示长(英语)。在上下文不同的时候,代表不同的意思。比如当用户检索的Query是konglong,那这里就应该推断为中文搜索恐龙

Model

其实如果熟悉Machine Learning同学很容易就会想到,这种利用上下文关系推测对应文本概率的问题,是很典型的Language Model问题。

比如要对以下的Query做纠错:

儿童简直 wanju

淘宝搜

其实本质是一个寻找最优状态序列问题

Query分割

首先Query会经过分词器,分割成最基本的语义单元,对于中文(汉字、拼音)会以‘字’为单位,英文以word为单位。

候选Query生成

接着便可以开始我们的候选Query生成

首选是对每个word生成候选集

  • word为中文
    • 根据拼音、笔画相似这两种先验知识,生成候选中文
    • 根据历史的session log抓取错误形式作为补充
      • (比如用户在极短的时间内发起两次查询,很有可能是第一次输入错误导致的)
  • word为英文,则主要根据编辑距离
    • 当然还可以加上键盘布局的先验知识(比如yu和hu的编辑距离比yu和qu的更近,因为在键盘上,y和h更近)
  • word为拼音串
    • 通常的做法是根据历史的log,获取中文拼音的切分位置

候选Query排序(寻找最优序列)

寻找最优序列的方法很多,最主要的是基于两种思路

  • 概率估计(MLE)
  • 神经网络 Seq2Seq

概率估计(MLE)

我们的候选query其实是

最后一个公式表示:候选结果C出现的概率 乘上 C被错写为Q的概率。

其中序列C出现的概率又可以表示为其中每个单词出现概率的叠加(这里指的是第i个单词出现后,i+1位置单词出现的概率)

C被错写为Q的概率可以写成

到这一步,概率推导的模型雏形就出来了。

接下来,用N-gram语言模型(n-1 马尔科夫模型)即可求解

神经网络 Seq2Seq

对于RNN神经网络,能更加方便的处理长序列,可以通过端到端的方式,直接生成正确的候选集。

我们知道N-gram考虑前面n-1阶信息,通常我们取n=2或n=3,再大的话,计算开销就很高了。

而神经网络可以自动学习到长序列的前后关联,相比N-gram的$ p(ci) = p(c{i-n},…,c{i-1}) $ ,神经网络可以做到$ p(c_i) = p(c_0,…,c{i-1}) $

而具体的实现就是经典的Seq2Seq模型了

我们以一个汉字为单位,英文以一个word为单位,走一遍Seq2Seq神经网络。就能完成训练。

模型中,我们的训练的正样本可以通过Session Log获得。

Reference

  • Kukich, Karen. 1992. Techniques for automatically correcting words in text. ACM Computing Surveys 24(4):377-437.
  • Sutskever, Ilya, Oriol Vinyals, and Quoc V. Le. “Sequence to sequence learning with neural networks.” Advances in neural information processing systems. 2014.
CATALOG
  1. 1. 背景
  2. 2. 主要Task
  3. 3. Model
    1. 3.1. Query分割
    2. 3.2. 候选Query生成
    3. 3.3. 候选Query排序(寻找最优序列)
      1. 3.3.1. 概率估计(MLE)
      2. 3.3.2. 神经网络 Seq2Seq
  4. 4. Reference