2 Basic information retrieval
2.1 Boolean retrieval
PPT课件下载链接：
Examples information retrieval problem
Building an inverted index
Processing Boolean queries
The extended Boolean model
2.1.1 Examples information retrieval problem
A example of boolean retrieval
Suppose you wanted to determine which plays of Shakespeare contain the words Brutus AND Caesar AND NOT Calpurnia
One way to do that is to start at the beginning and to read through all the text, commonly referred to as grepping through text, after the Unix command grep
The size of Shakespeare’s Collected Works is a bit under one million words of text in total
Realistic Challenge
But for many purposes, you do need more
To process large document collections quickly
To allow more flexible matching operations. It is impractical to perform the query Romans NEAR Countrymen with grep (Unix command)
To allow ranked retrieval. In many cases you want the best answer to an information need among many documents that contain certain words
Binary term-document incidence matrix
The way to avoid linearly scanning the texts for each query is to index the INDEX documents in advance
Shakespeare used about 32,000 different words
The index is a binary term-document incidence matrix(二值的项文档发生矩阵)
Terms are the indexed units, which are usually words. But they are combination of words sometime( Hong Kong) .
We can look at the matrix rows or columns, we can have a vector for each term, which shows the documents it appears in, or a vector for each document
Formally, we take the transpose of the matrix to be able to get the terms as column vectors
The procession of boolean retrieval
To answer the query “Brutus AND Caesar AND NOT Calpurnia”, we can take the vectors for Brutus, Caesar and Calpurnia, and then do a bitwise AND:
110100 AND 110111 AND 101111 = 100100
The answers for this query are thus “Anthony and Cleopatra” and “Hamlet”
The definition of boolean retrieval
The Boolean retrieval model is a model for information retrieval in which we can pose any query which is in the form of a Boolean expression of terms, that is, in which terms are combined with the operators AND, OR, and NOT. Such queries effectively view each document as a set of words.
布尔检索模型是一种可以利用布尔表达式表示查询要求和进行检索的信息检索模型。其中，查询关键词可以使用AND、OR和NOT操作符连接起来构成布尔表达式，这种查询将每篇文档都看成是一个词语集合
Realistic Challenge
Let us now consider a more realistic scenario
A document collection about 6 GB in size
1 million documents
Documents might be individual memos or chapters of a book
Each document is about 1000 words long (2–3 book pages)
Assume an average of 6 bytes per word including spaces and punctuation
Nearly 500000 distinct terms in these documents
A system to address the ad hoc retrieval (即席检索) which need fast information access
We now cannot build a term-document matrix in this way !
A 500K × 1M matrix has half-a-trillion 0’s and 1’s – too many to fit in a computer’s memory
The crucial observation is that the matrix is extremely sparse, that is, it has few non-zero entries
Because each document is 1000 words long, the matrix has no more than one billion 1’s, so a minimum of 99.8% of the cells are zero
A much better representation is to record only the things that do occur, that is, the 1 positions
This idea is inverted index !
The name is actually redundant
Nevertheless, inverted index, or sometimes inverted file, has become the standard term in information retrieval
2.1.2 Building an inverted index
The major steps to build the inverted index
Collect the documents to be indexed
Tokenize the text, turning each document into a list of tokens
Do linguistic preprocessing, producing a list of normalized tokens, which are the indexing terms
Index the documents that each term occurs in by creating an inverted index, consisting of a dictionary and postings
The data structure of inverted index
Multiple occurrences of the same term from the same document are then merged
The dictionary also records some statistics, such as the number of documents which contain each term (the document frequency, which is here also the length of each postings list). This information is not vital for a basic Boolean search engine, but it allows us to improve the efficiency of system
The dictionary is commonly kept in memory, while postings lists are normally kept on disk
Fixed length array
Singly linked lists
Variable length arrays
A hybrid scheme with a linked list of fixed length arrays for each term
Perhaps compressed
Singly linked lists allow cheap insertion of documents into postings lists
Variable length arrays win in space requirements by avoiding the overhead for pointers and in time requirements, because their use of contiguous memory increases speed. Extra pointers can in practice be encoded into the lists as offsets
If updates are relatively infrequent, variable length arrays will be more compact and faster to traverse
Some definitions
Term: Often are words
Dictionary( vocabulary, lexicon): A set of terms
Postings list( inverted list ):For each term, we have a list that records which documents the term occurs in, and often the positions in the document——conventionally called a posting. The dictionary has been sorted alphabetically and each postings list is sorted by document ID
Postings: All the postings lists taken together
2.1.3 Processing Boolean queries
A example
Consider processing the simple conjunctive query:
Brutus AND Calpurnia
Procession:
Locate Brutus in the Dictionary. Retrieve its postings
Locate Calpurnia in the Dictionary. Retrieve its postings
Intersect the two postings lists
The intersection operation of postings lists
The intersection operation is the crucial one, also called by merge algorithm
Query optimization
We can extend the intersection operation to process more complicated queries, but query optimization is necessary
A major element of this for Boolean queries is the order in which postings lists are accessed
The standard heuristic is to process terms in order of increasing document frequency, which justifies keeping the frequency of terms in the dictionary
We can temporarily store the answers for intermediate expressions in a complex expression
The Advantage of Boolean Retrieval
1）与用户思维习惯相一致
可以通过布尔逻辑符“AND”、“OR”和“NOT”将用户的提问翻译成系统可接受的形式，即布尔检索式可以表达与用户思维习惯相一致的查询要求
这是布尔检索的一个突出优点
2）简单易行
布尔检索系统实际上是通过对若干个文献集合（文献集D或D的子集）的并、交、补运算来回答用户提问。这种运算上的简单易行是布尔检索系统的又一突出优点
3）易于缩检和扩检
用布尔检索进行操作的某些系统允许用户通过使用一个有结构的字典来缩小或扩大检索
所谓有结构的字典是指对任何一个给定的标引词都存储了与之相关的更一般的（上位）或更精确（下位）的关键词的词典，这些词形成一种树的数据结构
下位标引词被包含在更一般的上位关键词中，同时它还可以继续细分成更精确的关键词
4）检索输出完全依赖于布尔查询与文档中文献的匹配情况，很难控制输出量的大小，检索结果可能是很多的文献，也可能是很少的文献
检索结果不能按任何意义上对于用户的重要性排序输出，从而检索出的文献对用户来讲都一样重要。其中这也是布尔检索的根本特性，它采用了要么命中要么不命中的检索策略，而其他一些检索方法则采用区间数值表达的计算方法，能够得到很多介于命中和不命中之间的文档，此时只能通过相关度排序来实现结果输出，否则没法使用
5）对于文献描述与布尔查询中的标引词没有一种加权的方法，以凡在文献描述或布尔查询中出现的词在检索时都呈现出相同的重要性
布尔查询表示有一个很不合理的现象，例如，关于“OR”查询（A OR B OR … OR Z）对于包含有一个在查询中出现标引词的文献与包含有几个在查询中出现的标引词的文献被认为是一样重要的。另一方面，对于“AND”查询（A AND B AND … AND Z），则包含n－1个在查询中的标引词的文献描述所代表的文献与没有包含在查询中的标引词的文献描述所代表的文献被认为一样无用
2.1.4 The extended Boolean model
为了克服上述缺陷，人们考虑了建立新型理论的可能性。事实上，这种性质的工作已经获得了丰硕的成果，如代数检索理论（文档向量空间模型），概率检索理论等，这两种理论已经可以控制输出量的大小和对检索输出进行排序。同时与已有的科学技术水平达到了一定程度的接近
除此以外，还有模糊检索理论，它是用模糊数学方法来处理布尔查询的，但是理论复杂，所以实施难度较大
早在60年代，人们就已经考虑了对布尔检索理论本身进行改进、推广的尝试
相继有许多人提出了一些可以排序输出的布尔检索策略，并应用于实验系统，真正有意义的工作是Waller和Kraft在1979年进行的，他们提出了加权布尔检索模型应遵循的基本原则
接着，Bookstein、Buell和Kraft分别在1980、1981年做了更进一步的工作，他们事实上已经提出了一些有意义的加权布尔检索模型
1983年，Salton将向量检索模型与布尔检索模型融为一体，提出了一种所谓扩展布尔检索模型。上述工作使得在理论上不够完善的传统布尔检索理论出现了新的生机
Ranked retrieval models
Contrasts with boolean retrieval, ranked retrieval models such as the vector space model allows users to largely use free text queries, that is, just typing one or more words rather than using a precise language with operators for building up query expressions, and the system decides which documents best satisfy the query
But boolean retrieval is still a important search option provided by large commercial information providers
Salton Model
Salton模型的出发点是用向量方法来讨论布尔检索
先从最简单的情况谈起。设文档集D中各文档仅由两个标引词t1和t2标引，并且在各文档表示中t1和t2允许赋予权值，其权值范围为[0，1]，这个值需要标引来确定
则文档集中各文档均可由t1和t2所确定的二维平面上的点来表示
点A（0，1）与文档表示中t1权为零，t2权为1的所有文档相对应
点B（1，0）与文档表示中t1权为l，t2权为零的所有文档相对应
点C（1，1）与文档表示中t1和t2权都为l的所有文档相对应
而对于更一般的情况，即文档表示中t1权为d1，t2权为d2的文档，可以用在正方形AOBC内部的某一个点D（d1，d2）来表示
显然0<=|DO|<=√2，为了使相关程度控制在0与l之间，可以对上述距离公式稍作修改，将相似程度定义为：
对于由tl和t2构成的查询q=t1 AND t2，在图中只有C点所代表的文档才是最理想的文档
对于D点所代表的文档，仍然可以按照一个合理的步骤来设计它们与查询q的相关程度。因为C点代表着理想的命中文档，所以当D点与C点越接近时，D点所代表的文档关于查询q的相关程度就越大，即D与C间的距离可以作为衡量一篇文档与查询q的相关程度的一个尺度
上述两个相似度计算公式是Salton对传统布尔检索模型进行扩展的最初结果，下表总结了扩展布尔检索模型与传统布尔检索模型的区别:
从表中可以看出，扩展布尔检索比传统布尔检索对文档和查询之间的关系考虑得更周密，更细致：
对查询t1 OR t2的处理，传统布尔检索对只被一个标引词（t1或t2）标引的文档与被两个标引词都标引的文档做出相同的处理结果，即都作为命中文档，而扩展布尔检索对这两种文档则做出不同的处理结果，前者的相似值为1／√2，小于后者的相似值1
对查询t1 AND t2的处理，传统布尔检索对只被其中一个标引词标引的文档和两个标引词都不标引的文档做出相同的处理结果，即都作为不命中文档，而扩展布尔检索则对这两种不同的文档给予区别，前者的相似值为1－1／√2，大于后者的相似值0
只被一个标引词标引的文档，扩展布尔检索在处理它们与查询t1 OR t2和t1 AND t2时，也给予区别，前者的相似值为l／√2，大于后者的相似值1—1／√2
查询的步骤：
得到查询词语及其布尔逻辑关系
对所有文档，将查询词语作为维度，以前面所示公式计算在这个维度坐标上，不同文档的相似度值
按序输出最终结果
Question
现有：
D={d1 , d2 , d3 , d4}
T={t1 , t2 , t3 , t4}
D中各个文档的向量表示分别为：
d1={0.8 , 0.6 , 0.2 , 0}
d2={0.7 , 0.1 , 0.8 , 0}
d3={0 , 0.5 , 0.7 , 0.8}
d4={0.7 , 0 , 0.8 , 0.9}
查询：( t1 AND t2 ) OR t3
计算扩展布尔检索结果
现在进一步考虑当查询标引词推广到n个的情形
设文档标引词及查询标引词的集合为{t1，t2，…，tn}，文档集中某一文献的向量表示为：
d=(d1,d2,…,dn)
其中di表示第i个标引词ti的当前文档权值，0<=di<=1
2.1.5 关于文档的标引
文档标引（index）
它是指通过对文档的分析，产生出一种计算机能够处理的文档表示形式，如一组词语集合，必要的时候还需给这些词语一定的重要性权值
并非索引，只是索引中的标识（Tokenization）部分，然而也并非纯粹的标识，因为很多情况下，还要给出权值
以数学方式表示标引，设D为文档集合，表示为：
D={d1,d2,…,dm}
T为标引词集合，表示为：
T={t1,t2,…,tn}
D中第i篇文档经过标引后其特征为：
di={di1,di2,…,din}(1<=i<=m)
在标引中，可以将不同标引词在文档中的权重值设为不同的数值，按照这种方式，可以将标引分为二值标引和加权标引
在二值标引中，dij的值只有0和1这两种数值，如：
dij=0，第i篇文档未标上第j个标引词
dij=1，第i篇文档标上了第j个标引词
在标引时，如果按标引词反映文档主题内容的程度，设计一个权值附加给该标引词，标引词反映文档主题内容的程度越高，权值越大，反之越小，则这样的标引被称为加权标引
加权标引的取值范围则可以是一个闭区间[0,1]，所以它是一种多值标引，即假定了标引词与文档的相关性是多值的。已有充分的证据表明，加权标引比二值标引具有更高的检索效益
Zipf定律
在标引时，是不是需要标引所有的词语？
一篇文档中不同词的使用有什么特点，它们在文档中出现的频率有没有一定的规律，其表现形式应是怎样？
Zipf定律说明了这个问题
Zipf收集了大量的统计材料，他发现自然语言词汇的分布服从一个简单的定律，他在《人类行为与最小力气法则》中称这一定律为“省力法则（Principle of Least Effort）”，即将某一篇较长的文档（约5000字以上）中每个词出现的频率按照递减顺序排列起来（高频词在前，低频词在后），并用自然数给这些词编上等级序号，频次最高的是1级，其次是2级等等，这样一直到D级
该法则也被称为二八原则，或者帕累托分布
该定律有效的揭示了不同词语对于表达主题的重要性贡献上具有不同的作用
如果用f表示词在文档中出现的频次，用r表示词的等级序号，则有：
fr＝C（C为常数）
如果建立f与r的坐标系，用横坐标表示词的等级序号r，纵坐标表示频次f，就得到双曲线的一支
Zipf定律在许多领域都得到了验证
许文霞在1986年的《齐普夫定律与中文词频分布机理》中也验证了中文文档中的词频分布符合Zipf定律
今天的网络语言仍然表现出明显的这项特点
Luhn思想
Luhn在Zipf定律的基础上，作了许多文档内容的自动分析工作，提出了自动抽词的思想
即一篇文档中一个词出现的频率是这个词的重要性的有效测度依据
一个句子中具有给定该重要性测度的词的相关状态，成为该句子重要性的有效测度
也可以按照数学方式来说明这一问题，设Q＝{q1,q2,…,qn}是查询d的标引词集合，ri和σi分别表示相关文档集合R和不相关文档集合I中包含qi作为标引词的文献个数
定义查询标引词qi的精确度为：
ri/(ri+σi)
词精确度同词的权值一样，不是词的固有性质，它是针对一个特定查询而言的
对于不同的查询可以有不同的词精确度。当查询给定时，词的精确度反映了一个词作为标引词的标引效率
词的精确度越高，用其作为标引词的标引效率越高；词的精确度越低，用其作为标引用的标引效率越低
上述思想可以以下面的假设来表示：
设qi和qj（1<=i,j<=m）表示两个不同的查询标引词
ri、σi分别表示相关文档集合R和不相关文档集合I中包含qi作为标引词的文档个数
rj和σj分别表示相关文档集合R和不相关文档集合I中包含qj作为标引词的文档个数
如果qi的文档频率大于（含等于）qj的文档频率（即ri+σi>=rj+σj），则可假设qj的词精确度大于qi的词精确度，即：
ri/(ri+σi)<= rj/(rj+σj)
按照上述思路，将词的出现频率按等级排列，以一定的标准排除高频词与低频词，剩下的就是最能代表文档主题内容的词
其具体步骤如下：
给定n篇文档组成的一个集合，计算第k个词在第i篇文档中发生的频率fik
决定该词在整个文档集上的发生频率：fk=Σfik（1<=i<=n）
按照fk的大小将词降序排列，确定一个上截止阈值，并去掉fk大于上截止阈值的那些词。同样确定一个下截止阈值，并去掉fk小于下截止阈值的那些词
剩余的中频词用于文档的标引
词分辨力与词频的关系
这里Luhn在分析词频的基础上提出了词分辨力（resolution power）的概念。他设想在文档中每个词都具有一定的分辨力，所谓词分辨力，就是帮助人或机器区分不同文档的能力
他还发现频率太高的词（高频词）分辨力很低，有些甚至于接近零。因为它们一般都是—些只起语法作用而无实际内容的功能词，如介词和连词等，或是一些很泛指的词。它们既然不能给文档本身增添什么实际内容，也就起不到区分不同文档的作用
频率过低的词（低频词、罕用词）在文档中很少出现，不能依*它们来区分不同文献，所以分辨力一般很低
中频词的分辨力较强，称为有效词（Significant term），它是可供文档用的标引词
现在许多自动标引的工作都是在Luhn的思想影响下进行的，Luhn本人也用这些想法设计了一种自动编制文摘的方法，他这一开创性的工作引起了一些情报科学家和计算机应用专家的极大注意
他的文摘自动编制思想是：
利用计算机程序，通过对词出现情况的统计分析
选取包含有所确认的特征项的句子，将其再连贯起来自动建立文摘。也就是对文档中各句子的语义进行数值测度研究，将各句子按照测度大小排列，最高的排列被包含在实际抽取的文摘中
但是也有许多证据表明，Luhn的原始自动抽词思想在实际检索时是粗糙的
因为高频词的去舍会降低查全率，因为高频词用于文档标引会检索出大量的相关文档
相反，低频词的去舍会降低查准率
另外，最基本的问题是对于标引词的绝对频率（fik和fk）易于受到文档长度的影响
关于阈值的确定，Luhn是用试错的方法来确定上下截止界。显然，如果截止界定得不合适就可能出现两种情况：或者是许多与文档主题无关的词被包括进来，或者是忽略了许多有用的词，或者两方面兼而有之
由于Luhn早期工作存在的问题，后来的研究者提出了许多补救的办法
标引词的权重选择
这里讨论的主要是自动权重方法
由于一篇文档的词可以分为“特征词”和“非特征词”两大类
特征词就是能反映文档的主题内容的词
非特征词就是不能反映文档主题内容的词，只是为了语法或写作风格上的需要才出现
自动标引的实质就是通过对文档的自动分析，根据词在文档中出现的特点，选择一部分特征词作为标引词
逆文档频率加权标引
设fik为第k个词在第i篇文档中的发生次数，称为词发生频率（frequency of occurrence）
fk为包含第k个词的文档总数，称为词的文档频率（document frequency），则：
fk=Σbik(1<=i<=n)
其中的bik可以表示为：
bik=1(fik>=1) bik=0(fik=0)
词发生频率只对文档集合中某一确定的文档才有意义，而词的文档频率则是对整个文档集合而言的
在一个文档集合中，非特征词的文档频率一般较高，例如一些反映句子语法结构的词，几乎在所有的文档中都出现，而特征词的文档频率一般较低
例如“信息检索”一词只在一些主题内容与信息检索有关的文档中才出现
在一篇特定的文档中，特征词的发生频率越高，说明它与该文档的主题相关的程度越高。所以在标引中，人们总希望所选择的标引词在某些特定的文档中发生频率较高，而在整个文档集合中出现的频率较低
在设计词权时，权的大小应与标引词的发生频率一致，与标引词的文档频率成反比。依据这一思想，可用如下方法设计词权：
wik=fik/fk
在逆文档词频率加权标引中，由于fik的确定较为繁杂，所以在实际中往往只根据词的文档频率设计词的权值，即如果词语qi的文档频率大于词语qj的文档频率，则wi<=wj，这是前文Luhn思想的体现
由此说明假设给定固定的词发生频率fik，标引词的权值随文档频率fk的增大而减小，随fk的减小而增大
标引词的权重与标引词的文档频率存在相逆关系，故称这种标引权重设置方法为逆文档频率加权标引（inverse document frequency）
[此贴子已经被作者于2010-12-14 08:49:51编辑过]
加好友 
发短信
管理员
Post By：2008/3/8 10:32:04 [只看该作者]
