UIUC《文本检索与搜索引擎》课程学习笔记(一)—— 自然语言处理概述

UIUC《文本检索与搜索引擎》课程学习笔记(一)—— 自然语言处理概述

Contents

前言

这系列笔记是记录Coursera上伊利诺伊大学厄巴纳香槟分校翟成祥教授(Prof. Chengxiang Zhai)所开设课程“Text Retrieval and Search Engines”课程内容的。该课程没有直接给出文档版的讲义,所以笔记内容多数是自己结合课程视频与课前导学问题所写。由于水平有限,文中难免会有不准确的地方,在此诚挚欢迎大家指出,共同交流完善。

引导问题(Guiding Questions)

Develop your answers to the following guiding questions while watching the video lectures throughout the week.

  • What does a computer have to do in order to understand a natural language sentence?
  • What is ambiguity?
  • Why is natural language processing (NLP) difficult for computers?
  • What is bag-of-words representation? Why do modern search engines use this simple representation of text?
  • What are the two modes of text information access? Which mode does a web search engine such as Google support?
  • When is browsing more useful than querying to help a user find relevant information?
  • Why is a text retrieval task defined as a ranking task?
  • What is a retrieval model?
  • What are the two assumptions made by the Probability Ranking Principle?
  • What is the Vector Space Retrieval Model? How does it work?
  • How do we define the dimensions of the Vector Space Model? What does “bag of words” representation mean?
  • What does the retrieval function intuitively capture when we instantiate a vector space model with bag of words representation and bit representation for documents and queries?

关键概念(Key Phrases and Concepts)

Keep your eyes open for the following key terms or phrases as you complete the readings and interact with the lectures. These topics will help you better understand the content in this module.

  • Part of speech tagging, syntactic analysis, semantic analysis, and ambiguity
  • “Bag of words” representation
  • Push, pull, querying, browsing
  • Probability ranking principle
  • Relevance
  • Vector space model
  • Dot product
  • Bag of words representation
  • Bit vector representation

额外阅读材料(Additional Readings and Resources)

The following readings are optional:

  • N. J. Belkin and W. B. Croft. 1992. Information filtering and information retrieval: Two sides of the same coin? Commun. ACM 35, 12 (Dec. 1992), 29-38.
  • C. Zhai and S. Massung. Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining, ACM Book Series, Morgan & Claypool Publishers, 2016. Chapters 1-6.

一、自然语言内容分析(Natural Language Content Analysis)

1.句法歧义(Syntactical Ambiguities)

我们先来看一句话: A dog is chasing a boy on the playground. 机器该如何解析这句话呢?

首先,我们需要分析出句子的成分,这样就提取出其中的主语、谓语、宾语、形容词等。这就是词法分析(lexical analysis)或者说词性标注(speech tagging)

之后,我们需要分析句子的结构(Structures),找出合理的结构来套用这些单词的组合。这就是语法分析(Syntactic analysis)。

但是目前为止,仍然无法理解句子的意思,那么就进入了下一步:语义分析(semantic analysis)。我们可能会实例化其中的Dog类和Boy类,以及Playground类,然后使用Chasing方法。这样就完成了一次基本的理解。

更进一步,看到这个句子的我们,可能会有一些推理(inference)。比如,推断出被狗追的男孩可能会觉得害怕;比如这句话可能是在提醒狗的主人把狗牵回来。这是因为我们有庞大的知识库。这些都是基于具体语境做出的推断(出于什么目的而说出这句话),也就是使用实用分析(pragmatic analysis)。但是对于计算机而言,想实现这一步却是非常复杂的。

 

所有的这些,都是因为自然语言并非专为电脑设计的,而是为人类交流设计的。由于人类可以通过推理解决一些显而易见的“大家都知道的东西”,所以它保留了大量的含糊之处,以此提高我们的沟通效率。但这也导致了使用计算机进行自然语言处理时会出现一些问题。

一个最经典的例子就是“A man saw a woman with a telescope”,这里的问题在于,是男人用望远镜看一个女人,还是一个男人看到一个拿着望远镜的女人呢?

2.文本检索中的自然语言处理(NLP for Text Retrieval)

我们需要在很多领域都用到文本检索,这意味着,文本检索必须是普适、健壮、高效的。

对于大多数搜索任务而言,“词包”(bag of words)是一种很有效的方法。

很多文本检索技术可以自然地定位/解决NLP问题。

尽管如此,在面对更加复杂的搜索任务时,我们需要更加深入的NLP方法。

二、文本访问(Text Access)

1.文本访问的两种方式“拉”与“推”(Two Modes of Text Access: Pull vs. Push)

  • 对于Pull Mode而言,一般是搜索引擎
    – 用户主动
    – 关于广告的需求(即临时起意的需求,典故为:对于一则广告感兴趣,然后去搜索与它相关的信息)
  • 对于Push Mode而言,一般是推荐系统
    – 系统主动
    – 稳定的需求或者系统对用户的兴趣有足够的了解(例如用户经常在一个浏览器浏览新闻,那么浏览器就知道用户的新闻偏好)

2. Pull模式的两种方法:询问与浏览(Pull Mode: Querying vs. Browsing)

  • 询问(querying)
    – 用户进行(关键词)询问
    – 系统返回相关文档
    – 在用户知道需要使用什么关键词的时候表现很好

  • 浏览(browsing)
    – 用户通过文档结构中的路径,被引导至相关信息处(最常见的是论文引用)
    – 在用户不知道该用什么关键词,或者不能方便地进入一个询问时,能够表现很好

我们以寻路和信息搜索问题来理解:

  • 寻路:知道目的地的地址吗?
    -知道:乘坐出租车直接到达
    -不知道:四处转转,或者乘坐出租到附近的地方然后步行
  • 信息搜索:准确知道你想找的是什么吗?
    -知道:使用正确的关键词来询问,进而直接找到所需信息
    -不知道:直接浏览信息空间或者从一个粗糙的询问出发,然后浏览

三、文本检索问题(Text Retrieval Problem)

1.什么是文本检索(What is Text Retrieval)

  • 对象是已有的文本文档集
  • 用户通过询问来表达信息需求
  • 搜索引擎系统返回相关文档给用户
  • 经常被称作“信息检索”(IR),但是IR的范围实际上更广
  • 在工业界也被称作“搜索技术”(Search Technology)

2.文本检索与数据库检索(Text Retrieval vs. Database Retrieval)

  • 信息
    -无结构/自由的文本 vs. 结构化数据
    -模棱两可 vs. 准确定义 的语法
  • 询问
    -模棱两可 vs. 准确定义 的语法
  • 答案
    -相关文档 vs. 匹配记录
  • TR是一个企业级的问题
    不能从数学上证明一个方法比另一个方法好
    -需要依赖于企业级的用户

 

3.文本检索的形式表述(Formal Formulation of TR):

  • 词汇(Vocabulary):​\( V=\left\{ w_1,w_2,…,w_N \right\} \)​of language.
  • 询问(Query):​\( q=q_1,…,q_n \)​其中​\( q_i \space\epsilon V \)
  • 文档(Document):​\( d_i=d_{i1},…,d_{im_i} \)​其中​\( d_{ij}\space\epsilon V \)
  • 容器(Collection):​\( C=\left \{ d_1,…,d_M \right \} \)
  • 相关文档集(Set of relevant documents):​\( R(q) \subseteq C \)
    -是未知的,与用户相关的
    -询问是一次“命中”R(q)的文档
  • 任务(Task):计算R'(q),即R(q)的一个近似

4.如何计算R'(q)

  • 策略1:文档选取(Document selection)
    -R'(q)={d∈C|f(d,q)=1},其中f(d,q)∈{0,1}是一个指示函数或者二类型分类器
    -系统必须决定一个文档到底是否相关/无关(绝对地确定
  • 策略2:文档排名(Document ranking)
    -R'(q)={d∈C|f(d,q)>θ},其中f(d,q)∈R是一个相关度测度函数;θ是一个由用户设定的分界线
    -系统仅仅需要决定一个文档是不是比另一个文档更相关(相对地相关性

5.文档选择时的问题(Problems of Document Selection)

  • 分类器并不是那么精确
    -“过约束(Over-constrained)”询问 -> 没有任何相关文档可以返回
    -“欠约束(Under-constrained)”询问 -> 返回过多的结果
    -很难找到一个合适的平衡点来均衡两种情况
  • 即使结果是准确的,但所有相关文档的相关程度是不同的(相关度问题)
    -需要给出优先级
  • 因此,一般而言文档排名比文档选择策略更受欢迎

6.排序策略的一些理论基础(Theoretical Justification for Ranking)

  • 可能性排名原理(Probability Ranking Principle):返回一个按相关可能性降序排名之后的文档名单,在如下两个前提下,排序策略才会有效果:
    -不同文档之间的效果是独立的(也就是说文档之间不相关,不会产生联合效果)
    -一个用户会按照一定的顺序浏览结果
  • 那么,这两个前提成立吗?

7.总结

  • 文本检索是一个企业级的问题
    -需要由用户来判断哪个算法更好
  • 文档排名一般而言更受欢迎
    -帮助用户优先检查一部分搜索结果
    -避免了决定文档是否绝对相关的困难(用户帮助决定排名名单的分界线)
  • 主要挑战:设计一个有效的排名函数f(q,d)=?

四、文本检索算法概览(Overview of Text Retrieval Methods)

1.如何设计一个排名函数(How to design a ranking function)

  • 询问:\( q=q_1,…,q_m \)​,其中​\( q_i∈V \)
  • 文档:​\( d=d_1,…,d_n \)​,其中​\( d_i∈V \)
  • 排名函数:f(q,d)∈R
  • 一个良好的排名函数应该能够把相关的文档排在不相关文档的前面
  • 关键挑战:如何量化文档d与询问q之间的相关程度
  • 检索模式=相关程度的表达(给定关于相关程度的可计算的定义)

2.各种检索模式(Many Different Retrieval Models)

  • 基于相似程度的模式:f(q,d)=相似度(q,d)
    -向量空间模式
  • 概率模式:f(q,d)=p(R=1|d,q),其中R∈{0,1}
    -传统的概率模式
    -语言模式
    -随机性偏离的模式(Divergence-from-randomness model)
  • 概率推论模式:f(q,d)=p(d->q)
  • 公理模式:f(q,d)必须满足一系列的约束条件
  • 这些不同的模式应该会带来相同的排名函数使用相同的变量

3.当今检索模式的一般思想(Common Ideas in State of the Art Retrieval Models)

当今的文本检索模式比较流行的思想是使用“词包”。将询问划分为不同的单词,然后在每一个文档中按照如下方式进行计算:

  • 问题中的某个单词,在文档d中出现了多少次?
    这个步骤的指标也被称为关键词频(Term Frequency, TF)
    //我个人觉得这里用frequency不是特别准确,因为它统计的是次数而不是频率
  • 文档d有多长?
    文档越长,那么出现关键词的次数自然会多
  • 在所有文档集中,我们能多经常看见包含某个特定词的文档?
    这个不招租的指标也被称为文档频率(Document Frequency,DF)

4.哪一个模式效果最好?(Which Model Works the Best)

  • 当经过优化之后,下列模式能够具有同等的表现:
    -Pivoted length normalization
    -BM25
    -Query likehood
    -PL2
  • BM25最流行

5.总结

  • 要设计排名函数,需要预先定义出可计算的相关度
  • 很多模式的表现都很优秀,没有一个特别突出的
  • 排名函数的状态一般而言依赖于:
    -词包
    -关键词频与文档频率
    -文档长度

五、向量空间模式(Vector Space Model,VSM)

1.VSM是一个框架

  • 将一个文档/询问用关键词向量表示出来
    -关键词:基本的概念,例如,单词或者短语
    -每一个关键词定义出一个维度
    -N个关键词定义出一个N维空间
    -询问向量:​\( q=\left\{ x_1,…,x_N \right\},x_i∈ \Re \)​是询问的关键词权重
    -文档向量:\( d=\left\{ y_1,…,y_N \right\},y_i∈ \Re \)​是文档的关键词权重
  • 相关程度(q,d)∝相似度(q,d)=f(q,d)

2.VSM还未明确给出的(What VSM Doesn’t Say)

  • 如何定义/选取“基本概念”
    -概念之间需要相互正交(无关)
  • 如何在空间中放置这些文档和询问(如何确定关键词权重)
    -询问中的关键词权重表明了关键词的重要性
    -文档中的关键词权重表明了文档的关键词特征
  • 如何定义询问向量与文档向量之间的“相似度”

3.向量表征:位向量(Bit Vector)

上一小节我们明确了需要将询问和文档投影在向量空间,那么该如何表征向量呢?这里的一种方法是位向量法,当一个单词Wi出现的时候,对应位置1,若没出现过,置0.

4.相似度实例:点积(Dot Product)

将向量表征出来之后,就可以考虑进行比较了,这里定义询问与文档之间的点积为​\( Sim(q,d)=\sum_{i=1}^Nx_iy_i \)

5.这样的简单版VSM有效吗?

我们来看下面这个例子:

在这个例子里,出现了多个相似度为3的文档,但是其中的关键词可能不一样,在我们看来,应该是D4文档更相关。也就是说,我们的算法还需要改善。

6.总结

  • VSM实例:维度,向量表征,相似度
  • 简单版VSM
    -维度=单词
    -向量=0-1位向量(单词出现/没出现)
    -相似度=点积
    -f(q,d)=询问q与文档q关于不同单词匹配的个数

 

Tags:


Leave a Reply

Your email address will not be published.

*
*
*

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert