这几天看了几篇感兴趣的SIGIR 2011的论文，包括信息抽取、页面分析、检索模型、索引等方面，以下是阅读笔记。

From One Tree to a Forest: a Unified Solution for Structured Web Data Extraction

这篇文章解决的问题是网站垂直信息的抽取，这个方向实际中遇到的问题是，抽取过程很难自动化：如何从抽取一个网站，到自动化抽取一个领域，再到方法本身与领域无关；如果用人工配模板的方式，费时费力还不讨好，因为网站一旦改版就前功尽弃。目前实用的方法通常是用程序模拟人工配模板，用一些方法自动统计出目标数据的DOM path，但仍会遭遇改版的问题，而且准确率比人工方式低一些。

这篇文章绕开了DOM path的问题，利用语义、视觉等更不易改变的特征来表征一个数据区域，并充分利用同站点同类页面的统计信息，方法较为通用，与领域无关；并且只需要对一个领域标注一个站点，就可以自动抽取该领域的其他站点的数据。这篇文章假定待抽取的数据都在文本节点中，因此将抽取过程变成了一个对文本节点进行分类的过程。

• 特征：内容特征——token集合，token数量，字符数量，字符类型，数据字符串在不同页面间的重复度；上下文特征——前置文本，前缀和后缀。
• 学习过程：属性级别——对内容特征和上下文特征分别训练出一个分类器，预测值为这两个分类器各自预测值的最大值；属性间级别——不同属性之间的相对距离表示成为一个矩阵，假定同一领域的属性之间的相对距离关系比较稳定，利用矩阵的相似来选择最合适的属性预测。
• 预测阶段：首先在页面级别，对每个数据段（即文本节点）利用内容特征和上下文特征，计算其属于各个属性类别的可能性；然后在页面间级别，对不同页面的相同的数据段利用DOM path和上下文特征进行对齐，对于对齐的数据段，将它在各个页面的预测值进行平均，作为属性级别预测值；最后，利用属性间的位置关系矩阵与训练集该矩阵的相似度，结合属性级别的预测值，对数据段的类别进行ranking。

该文章显示，其效果好于google的Stacked Skews Model的效果；并且，利用页面间统计后，效果有明显提升。该文章的方法领域无关，将机器学习、多页面统计很好地结合起来，不受网站改版影响，我认为比较promising。

Using Cross Terms to Enhance Probabilistic Information Retrieval

在信息检索中，当query中含有多个term时，如何根据term之间的邻近关系赋权，是一个比较麻烦的问题。在我们的直觉中，一个term的存在通常会对邻近term的含义产生一定的影响，本文提出用kernel函数来量化这种影响力，两个term的kernel函数曲线的交点，对应了一个虚拟term: cross-term。cross-term与一般的term一样，也有对应的tf、idf等，只不过在计算tf、idf时，cross-term的一次出现不是对应数值1，而是对应(0,1)之间的某个连续值，这个值等于两邻近term的kernel函数曲线交点的取值。在ranking计算权值时，使用cross-term的方式与一般term一样，然后将一般term权值与cross-term的权值进行加权叠加。

论文最后有一个数据，相关文档与不相关文档的Average Cross Term Freq in Docs的差距非常显著，而传统的tf、term间最小距离、平均距离等，差距都不太显著，也许这就是利用cross-term ranking效果比较好的原因。如果要使用本文的方法，可以验证一下这个数据。

A Boosting Approach to Improving Pseudo-Relevance Feedback

Pseudo-Relevance feedback是一种ranking算法中的著名技术，利用检索中返回的文档的统计信息，进行query expansion并计算扩展出的term的权值，在此基础上进行第二次ranking。这种方法可以整体改善ranking的效果，但不太健壮，在增强某些查询效果的同时容易伤害另一些查询的效果。本文即是为了解决这一问题。

Pseudo-Relevance feedback的不同策略体现在两方面，一是对不同的反馈文档的权重的计算，二是对扩展出的不同term的权重的计算。本文的算法致力于第一方面，即利用机器学习算法调整策略，将46个原子的反馈文档权重计算策略综合起来，得到各个反馈文档的一个综合权值，利用这个综合权值来计算扩展term的权值。

本文直接将优化目标定义为，在各个query上使用feedback后的总相关性损失最小化。训练过程使用boost算法：如果上一轮迭代中某些query上的相关性损失较大，则调高这些query的权重，寻找使调整权重之后的总的相关性损失最小的原子反馈算法，最后将不同的原子反馈算法进行加权综合。由于不同的原子反馈算法具有互补性，因此可以使得总的策略比单独的原子策略更加健壮。本文使用forward stagewise additive modeling算法来增量地选取原子反馈算法并赋予权重。最后实验显示，得到的模型在增强效果的同时又更加健壮。

DOM Based Content Extraction via Text Density

本文在网页DOM树的的基础上，基于文本密度来抽取主要内容，它基于网页正文抽取方向的一个很传统的假设：正文一般文本较长、tag较少、链接较少，因此比较适合抽取新闻、博客等页面。本文的公式非常简单，一个节点的文本密度等于其子树的字符串长度除以子树的节点数，然后又考虑了链接数量，得到一个复杂一些的复合的文本密度；由于正文中往往也夹杂着一些琐碎文本，边框中可能也有一些大段的文本，因此一般需要采取办法平滑一下，本文使用一种相当简单的技术来达到平滑的效果，即DensitySum——一个节点的DensitySum等于其子节点的文本密度（或复合文本密度）的和。最后的阈值设定算法是这样的：首先找到整个页面DensitySum最大的tag，从该tag到body节点路径上的最小的DensitySum作为阈值T，DensitySum大于T的节点都作为主要内容提取。

该文的方法与“Cetr - content extraction via tag ratios”这篇文章的方法比较像，不过后者不是基于DOM树而是直接从源代码提取内容。

A Site Oriented Method for Segmenting Web Pages

与提取网页的公用模板不同，划分网页是将网页分成几个非嵌套的部分，目标是尽量与人对网页的直观划分一致。该文对同站点的网页取样，利用节点级别的统计信息来构建SOM树（Site Object Model），最后得到的SOM树的叶节点即对应了对网页的划分；利用一些启发式的办法来净化SOM树，算法比较直白。最后利用该算法对4个站点的网页进行划分，并用在检索中，使检索效果得到改进。

Inverted Indexes for Phrases and Strings

现代搜索引擎通常使用词粒度的倒排表进行检索，因此难以支持任意字符串的检索。本文基于后缀树来组织倒排表，可以支持文档的任意子串的检索，令人欣慰的是空间占用并不大，其倒排节点数小于2n，n为所有文档的总长度。本文同时了利用一些启发式的办法来压缩索引的空间，将索引大小控制在大约文档数据大小的5倍。个人认为这种技术适用于一些短文本的检索，而对长的文档来说并不需要支持任意粒度的子串的检索。

An Optimized Algorithm Towards Efficient Approximate String Searches

基于倒排表索引进行近似查询也是一个麻烦的事情，比如，如何快速查找与query编辑距离小于k的字符串呢？基于q-gram索引，可以近似完成这个任务，基于这个结论：如果两字符串s1,s2的编辑距离为k，那么它们至少有t个公共的q-gram，其中t = max(|s1|,|s2|) - q + 1 - qk。因此，对于查询Q来说，查找与它的编辑距离小于k的字符串，就是查找在Q的grams的倒排表中，出现至少t次的字符串。本文是对归并算法的一个优化，没有仔细看。

A Novel Hybrid Index Structure for Efficient Text Retrieval

为了缩短检索时的归并时间，可以预先计算好term pair索引。但使用预计算的term pair索引，使需要读取的倒排链表成平方增加。本文介绍了一个技巧，对term pair (t1, t2)来说，在同一个倒排拉链中既存储pair的链表，也存储t1,t2的链表，这样可大大减小读取的倒排链表数量，代价是读取的同一个倒排链表会增长，也就是用更多的顺序磁盘读取为代价，减少随机读取，从而带来性能的提升。

Towards Effective Short Text Deep Classification

短文本分类的主要问题是特征稀疏，因此通常需要扩展特征。本文扩展特征的方法是explicit semantic analysis，即短文本通过与wikipedia的m篇文章比较相似度，将短文本表示m维的向量，相似度用tf,idf度量；将类别看作虚拟文档，也用同样的方法来表示。然后，利用求向量夹角余弦的办法，找出最有可能的k个类别。之后再用SVM分类器在k个分类中找出最可能的分类。