1. 背景
1.1 搜索检索问题
在互联网中，用户越来越多的依赖通过搜索关键词来获得想要的相关内容，如何快速准确为用户提供相应的结果成为一个重要的课题
用户的搜索行为通常可以简化为从一个数据集合中查询一个子集的过程，举个栗子：首先限制数据集合为英文集合（主要是英文分词比较好办，中文等一些语言还需要设计到分词的算法），然后从这些英文集合中搜索一些英文文档，将问题简化一下就是计算“查询的英文文档”和全部的“英文数据集合”中各个文档的相关性
接下来我们用更加具体化的方式来说明一下这个问题，首先我们有一个文档数据集合\(D\)，用户的搜索语句为\(q=w_1,w_2,...,w_n\),其中\(w_i\)代表具体的单词，接下来我们期望给用户返回一个数据\(D\)的子集 \(D^*\)，对于任何一个 \(d \in D^*\)，最大化概率 \[P(d|q,D)\] 上面的思想是通过引入概率和统计的方式计算出具体的数值，同时还有一些基于向量的方案来优化检索的过程
1.2 Ad-Hoc检索算法
在介绍TF—IDF算法之前我们先来探讨一些已有的模型，首先是如同上面提出的基于统计的最直接的方法，这种方法受欢迎并有效，比如（Berger & Lafferty, 1999)提出检索时结合用户的偏好概率框架从而提高查询结果的匹配度的。该模型假设用户有一个确定需求信息\(G\)，而这个需求信息可以近似的由一系列的单词组合\(q\)代表，通过近似的将\(G\)转换为\(q\)并将贝叶斯公式带入公式（1）中，在给定语句\(q\)的情况下返回合适的文档情景中该模型能够得到比较好的结果。
利用基于向量的模型来处理检索问题也能够获得好的结果，(Berry, Dumais & OíBrien, 1994)提出通过LSI（潜在语义检索）矩阵来处理查询检索，本质上，该算法是创建了一个降维过的向量空间来获得文档的\(n\)维空间表达式。当查询的发生的时候通过计算查询向量和文档集合中的其他文档向量的余弦相似度，然后返回那些相似度比较大的文档。文章作者的实验结果显示该算法在查询检索中性能非常好，甚至能够应用在夸语言的文档查询检索(Littman & Keim 1997)。如果某些条件得到满足（在特定的场景下），他们认为LSI能够扩展应用到2种语言以上。
我们接下来我们要详细的测试的算法是词频逆词频（TF-IDF），这种基于权重的模式可以认为是统计方式的一种，尽管事实上他的结果是确定的。词频逆词频是一个相当古老的权重模式，简单有效的特点使得他在众多方法中更加受欢迎（Salton & Buckley, 1988），在本文中我们通过the LDCís United Nations Parallel Text Corpus.英语文档集合来测试TF-IDF算法，探究该算法的优缺点作为未来算法的一个起点
2. TF-IDF概述
现在我们来看一下TF-IDF的结构和实现。首先我们将介绍算法的数学背景，并检查其相对于每个变量的行为。 然后提供实现的算法。
2.1 数学框架
在进行之前，我们将对TF-IDF进行快速非正式的解释。本质上，TF-IDF通过确定特定文档中的单词的相对频率与该单词在整个文档语料库中的反比例相比较起作用。 直观地，该计算确定给定单词在特定文档中的相关性。 在一个单一或一小组文件中不常见的单词往往比普通单词（如冠词和介词）具有更高的TF-IDF值。不同的情景下实现的TF-IDF有一些微小不同的地方，但是总体上计算的方式如下。给定一个稳定集合\(D\)，一个单词 \(w\) 和一个文档 \(d \in D\),我们计算\[\mathcal{W}_d=f_{w,d}*log(\frac{|D|}{f_{w,D}})\]其中 \(f_{w,d}\) 等于词 \(w\) 在文档 \(d\) 中出现的次数，\(|D|\)是文档全集的大小, \(f_{w,D}\) 是词 \(w\) 在全集中出现的次数(Salton & Buckley, 1988, Berger, et al, 2000)。根据\(f_{w,d}\)，\(|D|\)和\(f_{w,D}\)，每个单词都会出现不同的情况，这些正是我们接下来主要测试的地方。 假设\(|D|\thicksim f_{w,d}\),即语料库的大小大接近于\(w\)在集合\(D\)的频率，对于一些非常小的常数\(c\)，满足\(1 < log(\frac{|D|}{f_{w,D}}) < c\), 那么\(w\)将会比\(f_{w,d}\)小但是仍然是正的,这意味着\(w\)在整个语料库中比较常见，但在整个\(D\)句中仍然保持一定的重要性，例如TF-IDF在《新约》中的测试“Jesus”，就会是这种情况，与我们更加相关的例子在联合国文档的语料中“united”的结果可以预期到也是这种情况。对于非常常见的词语也是如此，例如冠词，代词和介词，它们本身在查询中没有任何相关的含义（除非用户明确要求含有这样的常用单词的文档）。 因此，这样的常用词得到非常低的TF-IDF分数，使得它们在搜索中基本上可以忽略不计。 最后，我们假设\(f_{w,d}\)非常大，\(f_{w,D}\)很小，那么\(log(\frac{|D|}{f_{w,D}})\)将会变得相当大，所以\(w_d\)同样会很大，这个使我们感兴趣的情况，因为具有高\(w_d\)的词意味着\(w\)是\(d\)中的重要词，而在\(D\)中不常见。这个词被认为具有很大的有辨识力的,所以当查询包含单词\(w\)，返回的高\(w_d\)文档\(d\)很大可能满足用户。
2.2 为TF-IDF编码
TF-IDF的代码很简单，给定一个由单词\(w_i\)集合组合成的查询\(q\)，对每个文档\(d\in D\)，计算每个单词\(w_i\)的\(w_{i,d}\)。最简单的方法是通过遍历文档集合并求和\(f_{w,d}\)和\(f_{w,D}\)。一旦完成，我们可以很容易地根据前面提到的数学框架计算\(w_{i,d}\)。 一旦找到所有\(w_{i,d}\)，我们返回一个包含满足最大化以下等式文档 \(d\) 的集合\(D^*\)：\[\sum_i{w_{i,d}}（3）\]无论是用户还是系统都可以预先设定查询返回的文档集合\(D^*\)的任意大小，并根据等式（3）以递减的顺序返回文档。 这是实现TF-IDF的传统方法。 我们将在后面的部分讨论该算法的扩展，以及根据我们自己的结果分析TF-IDF。
3. 实验
3.1 数据搜集和规则化
我们从《 LDC‘s United Nations Parallel Text Corpus》语料集合上搜集了1400文件，对TF-IDF进行测试，这些文件是从联合国1988年数据库的大量文件中任意收集的。这些文件是用SGML文本格式编码的，为了测试TF-IDF的鲁棒性，我们决定留下格式化标签导致的嘈杂的数据，并且强制区分大小写加大噪声。由于某些限制，我们不得不将用于执行信息检索的查询数量限制为86。我们根据计算公式3来计算这些查询的TF-IDF值，然后返回最大化（3）公式的前100个文档，这些文档根据权重的大小依次递减排序，为了对比我们的结果，我们同时测试暴力的方法（更加的朴素）