这一篇是query transformation and refinement，讲述了一下几点
- stopping and stemming
- spell checking and suggestions
- query expansion
- relevance feedback
- context and personalization
1. stopping and stemming revisited
- stopping即stopwords相关的工作，
- stemming主要是涉及单词多态，找到单词的原始态，甚至是同义词match的问题
这个大家都了解的比较多，不赘述
2. spell checking and suggestions
这二者是用户最常见的query变化的形式了，二者的方法比较类似，区别在于前者的原始query是wrong的或者un populoar的，SE会猜测是不是输入错误了，只给出一个候选，而后者是在用户输入任何queyr的时候，给出top k的候选，协助用户输入的同时给出建议。
形式如下
checking：
suggestion：
二者的方法比较相通，可以概述如下
普通文本最basic的方法是使用拼写字典，计算拼错的word和字典中的word的编辑距离
编辑距离：
- insertion
- deletion
- substitution
- transposition
计算拼错的word和字典中的word的距离计算量很大（要有一定的候选），有一些手段，包括一些近似的方法
- word A和B的start letter必须相同
- 相同或者类似的长度
- 发音类似，等（在英语中应用）
得到候选之后就是ranking所有的corrections
- 典型的有按照降序排列
- 对于搜索引擎，通常只需要best one
需要noisy channel model这个framework来ranking，在language model中，word w的概率分布为p(w)，用word occurrence即可。noisy channel为P(e|w)即persion想写w，却写成了e的概率，该概率成为error model，编辑距离长的概率更小，使用的时候对于编辑距离一样的e，概率可以假设相同，而rank的时候使用的是P(w|e)，做一个贝叶斯变化即可=P(e|w)*P(w)/P(e)，p(e)不变，等价于，P(e|w)*P(w)，这个是上下文无关的rank
考虑到上下文有关的，可以考虑二元的贡献，即前一个word的因素，word的language可以使用一个混合的概率模型，即为lamda P(w) + (1-lamda)P(w|wp) wp为previous word，在p(w)相同的情况下，P(w|wp) 利用上下文来判断选择谁
spell checking的流程
- 切词
- 使用词典和query log等资源寻找候选corrections
- 使用noisy channel model选择最好的correction
- 迭代上述的过程，知道找不到更好的correction（注意假如迭代多了会转义）
实验表明，query log的language model是correction accuracy中最重要的部分，error model比较次要，但是假如没有使用qurey log（只使用doc集合）的话，error model更加重要，好的实践是query log + application的dictionary，构建noisy channel model query expansion
3. query expansion
通常用于
- 搜索的时候会利用query的同义扩展或者相关的query来增加召回
- 用户交互界面的半自动化query提示，即suggestion
query expansion技术通常基于word或者term的共现（co-occurrence），集合可以是整个文档集合，query的机会，或者是搜索结果中的排名靠前的一些docs，著名的有pseudo-relevance feedback后续会提到，term association measure在expanseion中非常重要，有以下一些度量
- Dice's coefficient = 2*Nab/(Na + Nb) (rank等价于) Nab/(Na + Nb)
- 互信息mutual information = log(P(a,b)/(P(a)P(b)))，而P(a,) = na/N，因此上式等价于 log(N*Nab/(Na*Nb))等价于Nab/(Na*Nb)
- 混信息的期望expected mutual information = P(a,b) *log(P(a,b)/(P(a)P(b))) 等价于 Nab*log(N*Nab/(Na*Nb))
- 皮尔逊系数 pearson's chi-squared(x2) measure =(Nab - N * Na/N * Nb/N)^2 / (N * Na/N * Nb/N)
其中2和4偏向于低频的terms
4. relevance feedback
rf是基于query session的，而不是基于历史数据的，即点击数据可能用不上
rf是基于retrieval model相关的假设的，如假设搜索的前几条结果靠谱，从中抽取相关的term来扩展query，进一步去retriveal
事实证明suggestions要比是使用rf要好，目前也更加流行，因此不铺开说了
5.context and personalization
why:起初多数搜索引擎的特点是一个query的返回结果是相同的，不管是谁提交的query，为什么提交，在哪里提交，抑或在同一个session中其他的query是什么样的。然而事实上，我们在提交query的时候，是处在某上下文中的，而这些上下文，不仅影响检索到哪些文档，还影响到如何ranking。而上下文信息往往很难捕捉，或者不能一直保证效果。
1. personalization
user model和user profile
user model和user profile被研究用来代表用户的insterests，以便将搜索个性化。例如：同时搜索“rose”，对花感兴趣的人和对电影感兴趣的人所得到的结果理应是不同的。
然而这种思想有下面的问题。
- user model的准确度问题。构造user model往往基于用户看过的文档，访问过的web页面，email信息，以及桌面文档等等。然后从中提取term，进行tf，idf之类的计算，最终获取一个term的权重列表。
- 然而，在这些文档中，一方面用户感兴趣的只是文档其中某一部分，并非文档的全部，另一方面，这些文档仅仅代表了用户的一部分兴趣，而不是全部， 即从文档中抽取的兴趣和用户的真实兴趣的match程度是不确定的
predefined category
还有的方法询问user的兴趣，然后把user划入预定义的类别
- 这个方法的弊端在于，喜欢鲜花的人，也可能去询问一个和电影相关的query
- 因此事先将user划入类别也是不好的，query粒度的category仿佛更好，然而这还不如输入更加确定的query来的方便，如输入rose titanic，而不是输入rose的时候再选择category是film
隐私问题
人们现在越来越关注自己的隐私，建立user profile现在的利弊还不是很清楚（Google+也带来了诟病）
2. context information
- 利用query log和点击数据来改进搜索，这里的context包括session中的previous searches以及实现挖掘的similar search session（利用统计）
- local search，从query中识别出location相关的信息，然后和对应的location相关的文档match上，流程通常如下
- 对web pages预处理，识别出其中的地理位置
- 人工添加的location 元数据
- 文本解析，识别出地名
- 识别出query中隐含的地理位置，可以通过query中包含的location，或者设备的ip，等。可以通过分析query log，发现包含location的query是非常多的，15%左右，（在中国这个比例更高）。
- 结合locatioin信息进行rankking
总结，最有效的是利用past interactions，即query log和session history，而对于location相关的，可以进一步使用local search，而这些工作的目的是对不是specific的query进行expansion，使得更加specific，已达到context和personalization的效果
No comments:
Post a Comment