CMU 11642 的课程笔记大纲。涉及了很多算法，详细见具体的链接，代码就不贴了。欢迎讨论，欢迎指正～

Jamie 搜索引擎这门课，还是很有收获的，课上除了一些基本概念和算法外还有很多最新研究，涵盖内容非常广，绝对不止一本书。据 Jamie 讲，在 yahoo 等公司搜索部门的学生回来说现在做的工作感觉就是当年做的作业，是否有夸张不知道，然而大家可以感受下。已经过了选课阶段，就当给下一届想选的小盆友一点 workload 信息吧：

reading notes。每周有大量的 reading，可能是教材也可能是论文。注意 reading notes 的成绩是 binary 的，1 or 0，不要以为在 blackboard 上看到自己是 80 分就以为有了0.8，80分＝0分！
homework。五次作业完成一个完善的 search engine，语言是 java，大概三四十个类，每次都是在上一次的基础上进一步改进，所以除了最后一次作业外，你做的每一次作业的 performance 都将深深的影响下一次。如果你发现你的运行时间比 Callen 给的时间要长很多，请务必进行优化。作业不难，通常是让你实现各种算法，常用的以及某些论文中的，然而评分很严，很多 corner case 要注意。
每次作业完成都有一篇 report，需要做很多实验(四五十个至少吧，不写脚本的话感觉可以从天黑做到天亮)，并做“深刻”总结，之所以说“深刻”是因为有时候我绞尽脑汁写的东西得到的评语是 shallow。一把心酸泪。一般来说一天写算法再一天过全部的 test case，最后做实验写 report。
exam。期中期末两次考试，上过 text analytics 的人都知道，Callen 的一贯风格，考试广度优先，题量大，靠本能，你腾出时间来思考你就输了，给分低。

但是说了这么多不要怕！！就算考试成绩再低你的最后分数也会很好看！！

关于能不能 hold 住，这么说吧我上学期还选了 Machine learning(11601A)，Distributed Systems(95702)，以及 Data Structures for Application Programmers(08722)，感觉 4 门课老实说大课只能 focus 一到两门，如果各位还要刷题找工作，还是建议 P/F 或者是 audit 一门。

然后回到正题，高度总结下，这门课就讲了两个问题，一个是如何准确匹配查询与文档，一个是如何快速返回检索结果，就是 效果 vs 效率 的一个权衡。下面的总结梳理了这门课的重点，其中会涉及很多具体算法，然而这只是简单的提纲，不能把公式/算法都列出来，具体的可以看下面的链接或者看书/讲义。透露一点：多数的算法项目里你都需要去实现，而不需要实现的算法，Jamie 也不会轻易放过你，所以你们觉得会在哪里出现呢？😁

文档表示

源文档到索引的过程：
Raw data –(Format Parser)–> Canonical format –(Lexical Analyzer)–> Index terms –(Index data structures)–> Indexer

元描述(Meta-descriptions)
```
- Fields (author, title, inlink, url)
```

关键词、受控词汇(controlled vocabulary)

scheme 由识别文档主题的规则、指定词库、索引术语、分配索引的规则四部分组成
- 优点
    § 召回率高
    § 支持浏览和搜索
    § 在医学、法律、专利方面比较流行
- 不足
    § 人工标注创建和维护的成本很高
    § 人工标注可能不一致
    § 检索受限制

自动文档表示(Free-text or full-text index terms)

一般用词袋(Bag of Words)，文档由该文档中出现的词的集合所表示
○ 优点
    § 简单、有效
○ 缺点
    § 无法从词袋表示恢复原文档
    § 忽略了词之间和句法关系以及篇章结构的信息

过程：
    1. 符号化(Tokenization):识别词的边界
    2. 停用词(Stop Words)
        过滤不具有内容信息的词，停用词表依赖于具体文档集及具体应用
        ○ 优点
            §  停用词并不能提高检索效果
            §  大幅减少索引大小
            §  缩短检索时间
        ○ 不足
            § 难以满足某些特殊的 query(to be or not to be)
    3. 词语形态规范化(Normalization)
        规范化词语的形态信息: 时态，数量，如 company & companies, sell & sold
    4. 词根(Stemming)
        处理词缀信息
        ○ 优点
            § 更准确地表示文档
            § 匹配更广泛的查询
        ○ 不足
            § Stemming 的结果可能不是词语
             § 不相关的词可能具有相同的 stem
    5. 词形还原(Lemmatization)
        将词语变为其语法原型(syntactic stem)，使用一般规则与例外处理，处理过程要考虑词性的不同
        ○ 优点
            § 更准确地表示文档
            § 匹配更广泛的查询

    大部分互联网搜索引擎并不使用 stemming/lemmatization
        § 文档集很大
        § 不太考虑召回率
        § Stemming 结果并不完美
    大部分互联网搜索引擎使用停用词表，Jammie Callen 课上好像说现在不怎么用？

Search Engines笔记 - Document Representations
NLP 笔记 - Words, morphology, and lexicons

文档索引

目的在于提高检索效率

索引词项的统计特性

- Heaps定律：对词项数目的估计
- Zipf定律：对词项的分布建模

索引分类

- Term dictionary
- Inverted lists
    § 重点。常用的有 frequency inverted lists 和 positional inverted lists。
    § 可看做连标数组，每个链表的表头包含关键词，其后序单元则包括所有包括这个关键词的文档标号，以及一些其他信息，如该词的频率和位置等
- Attributes
- Fields masks
- Forward Index
- ...

索引对象

通常采用 word 构建索引
词组怎么办？
    - 事前处理 precoordinate(只有一个 inverted list)，合并可能的词组，interest rate -> interest_rate
    - 事后处理 postcoordinate(有多个 inverted lists)，查询的时候加上 #NEAR/1。interest rate -> #NEAR/1(interest rate)

索引算法

- 单机版
    - BSBI(Block sort-based indexing)
    - SPIMI(Single-pass in-memory indexing)
- 分布式索引
    - 技术：sharding, replication, MapReduce
    - 优化：分层索引
- 索引压缩
    - Delta Gap
    - Variable Byte Encoding
- 索引优化
    - Skip lists，考虑 operators(如 #NEAR,#WINDOW,#SYN,Boolean AND，调整指针) 以及 Top-Docs(截取部分 top docs)
    - 一个 term 多个 inverted list，比如一份不存位置信息，一份存，对于不需要位置信息的 operator，就用前一个索引
- 动态索引
    - 周期性索引重构
    - 辅助索引

数据结构

- 一般采用 B-Tree(B+ tree, B* tree)，易于扩展，用于完全匹配(exact-match lookup)，范围寻找(range lookup)，前缀寻找（prefix lookup）
- 哈希表，不易于扩展，用于完全匹配(exact-match lookup)

Search Engines笔记 - Index Construction

查询处理

TAAT(Term-at-a-time)

每处理完一个 inverted list，部分更新文档分数，再处理下一个。
- 优点：高效，易于理解
- 缺点：可能爆内存，因此很少用在 large-scale systems

DAAT(Document-at-a-time)

每处理一篇文档，就算出 complete score，再处理下一篇文档。
- 优点：易于进行内存管理，可以进行 query evaluation 的优化，常用在大规模的系统
- 缺点：效率没有 TAAT 高

TAAT/DAAT hybrids

平衡 Efficiency 和 memory control
Eg. block-based TAAT(compute TAAT over blocks of document ids)

Search Engines笔记 - Query Processing

信息检索模型

基本思想

如果一篇文档与一个查询相似，那么该文档与查询相关

相似性

- 字符串匹配
- 相似的词汇
- 相同的语义

检索模型

- 完全匹配模型／布尔模型(Boolean Model)
    - Unranked boolean model，只有匹配不匹配，没有分数。
    - Ranked boolean model，为文档计算特定分数。
    ○ 优点
        § 简单，效率高
        § 可预测，可解释，对查询严格掌控
    ○ 缺点
        § 一般用户难以构造布尔查询
        § 严格匹配，导致过少或过多的检索结果
        § 很难在 Precision 和 Recall 间得到平衡
    尽管布尔模型不再用作主流文档检索模型，但其思想常用于实现高级(综合)检索功能

- 最佳匹配模型(Best-Match Model)
    衡量一篇文档与 information need 的匹配程度，与完全匹配模型（匹配／不匹配）相比更注重用户体验，不管有没有匹配都会返回文档结果。有很多种方法，但说到底公式其实都和 tf-idf 的公式相似。
    1. 向量空间 Vector space retrieval model(VSM)
        - 思想: 文档与查询都是高维空间中的一个向量
        - 向量空间表示
            - 文档是词语组成的向量
            - 词语是文档组成的向量
            - 查询是词语组成的向量
        - 相似性
            - 用内积衡量
                ○ 缺点
                    § 长文档由于更可能包含匹配词语，因而更可能相关
                    § 然而，如果两篇文档具有同样的相似值，用户更倾向于短文档，短文档更聚焦在用户信息需求上
                    § 相似性计算中应该考虑文档长度(进行规范化)
            - 用夹角来衡量
                - 考虑 tf, idf, doclen
                - tf: 词语出现的频率
                - idf: 区别不同词语的重要性
                - doclen: 对文档长度进行补偿
            - 其他相似性度量
                - Minkowski metric(dissimilarity)
                - Euclidian distance(dissimilarity)
                - Jacquard measure
                - Dice's coefficient
        ○ 优点
            § 简单有效
        ○ 缺点
            § 过于灵活，自己设置 term weight，确定相似度度量方法，自己设置怎么支持 query-independent weights
    2. 概率理论 Probabilistic retrieval model(BM25)
        - RSJ weight * tf weight * user weight
        ○ 优点
            § 有很强的概率理论支持
            § 在新的环境中参数可以被调整
            § 在大量的 evaluation 中都非常有效
        ○ 缺点
            § 经验调整参数
    3. 统计语言模型 Statistical language model(query likelihood)
        生成两个模型，一个文档的语言模型，一个查询的语言模型，有两种方案来对文档进行排序，
        - query likelihood
            加上 Jelinek-Mercer Smoothing 和 Bayesian Smoothing With Dirichlet Priors
        - KL divergence
    4. 推理网络 Inference networks(Indri)
        - document + smoothing parameter(α,β) -> language model(θ) -> language model vocabulary(r)

Document Priors

与 query 无关的用来评估文档价值的 estimates(query independent)，主要有 spam score, PageRank, length of url 等，与上面的算法结合可以综合评估网页的分数。

Search Engines笔记 - Exact-match retrieval
Search Engines笔记 - Best-Match

个性化

基本逻辑：

- Representation: 描述用户的兴趣/偏好
- Learning: 从数据中学习兴趣/偏好
- Ranking: 在检索算法中使用兴趣/偏好

主要方法：

- 基于话题
    - 根据用户的长期检索历史对用户建模，得到的用户模型是在类别标签上的一个概率分布
    - 对排序列表进行 rerank，top n 的文档是两个分数的组合:
        - 原始文档分数
        - 文档类别和用户兴趣类别的匹配分数
- 长期 vs 短期
    将用户信息分为长期信息、短期信息、长期＋短期信息三组信息，每个特征都分别从这三组信息中分别提取出来，然后训练分类器
- 典型 vs 非典型信息需求
    - 根据用户长期检索历史创建 user profile
    - 判断非典型信息需求
        - 衡量 profile 和 session 的 divergence
          - 从用户历史记录里得到的每个 session feature 的 divergence
          - session 和 historical vocabularies 的 cosine 距离
          - session 和 historical topic categories 的 cosine 距离
    - 提取特征，训练分类器

Search Engines笔记 - Personalization

多样性

一个 query 可能表达了不同的信息需求，相关性模型可能带来的结果是大多文档只能满足同一个信息需求，我们希望检索到的文档是多样性的，能够覆盖到大多数的需求，满足更多用户。

算法

- Implicit Methods
    query intent 隐含在文档排名中，假设相似的文档涵盖了相似的 intent
    - Maximum Marginal Relevance (MMR)
        - 基于相似度，对文档重排序。
        - 重排序的标准是选择与 query 相似度高的，但和之前已经选出来的文档的相似度低的文档
    - Learning to Rank
        - 相当于 MMR 的有监督版本
        - 和 ListMLE 相同，写下 likelihood function，计算 MLE..
- Explicit Methods
    明确定义了 query intent，对文档重新排序，以便覆盖所有的 query intent
    - xQuAD
        选择涵盖多个 intents 的文档，给需要覆盖的 intents 赋予较高的权重
    - PM-2
        然后选择一个覆盖这个 intent 的文档，如果这个文档能覆盖其它 intents，那么给它加分

评价指标
```
- Precision-IA@k
- α-NDCG
```

Search Engines笔记 - Diversity

联合搜索

对一个 query，我们可以放到合适的多个垂直数据库里检索，然后合并结果呈现给用户。

Resource representation(资源表达)

- 获取每个数据库的信息
- 通常用 query-based sampling 方法

Resource selection(资源选择)

对资源进行排序，对每个查询选择少量资源进行检索
- 无监督算法
    看作资源排序的问题，估计 P(ri|q)
    - content-based methods
        - Bag-of-words method
            - 对各个资源下 query 和 resource 的相似度 S(q,c) 来对资源进行排序
            - 将一个资源看作一个大的词袋
            - E.g. CORI
            - query 和 resource 的相似度，这并不是我们的初衷
        - Sample documents method
            - 对每个资源采样然后合并得到一个 centralized index，记录每个文档来自哪个 resource
            - E.g. ReDDE
            - 高的召回率和准确率，通常来说效果都大于等于 CORI，尤其是数据库大小分布是 skewed 时
    - query-based methods
        对 query，搜索各个资源下的 query log，找出 match 的 query，然后求当前 query 和历史 query 的相似度 S(q,qpast)，对资源进行排序
- 监督算法
    给定一个查询，选择一个或更多的 verticals
    将问题定义为一个 “one-vs-all” 的分类任务
        - 对每个 vertical 都训练一个分类器
        - 对 “no vertical” (web only) 也训练一个分类器
        - 选择一个/多个具有最高置信度(confidence score)的分类器

Result-merging(结果合并)

即对来自不同搜索引擎／数据库对结果进行 merge，产生最终展现给用户的 ranking list。
用所有的 sampled documents 创建一个 index，从选定的资源里检索文档，对每个文档计算 sim (q, d)，同时根据数据库情况计算每个文档的 authority score，最后分数就是 score(d) = f ( sim (q, d), authority (d) )
- Semi-Supervised method
    - 对每个文档我们有两个分数，Sample index (resource neutral) score，Resource i (resource-specific) score
    - 学习 f (resource-specific) = resource-neutral

思路可以用于大规模分布式搜索引擎

Search Engines笔记 - Federated Search
Search Engines笔记 - ReDDE Algorithm for Resource Selection

Web 检索

Web 检索 = 文档检索 + 针对 Web 检索的新技术

Web 页面采集
爬虫：快速有效地收集尽可能多的有用 Web 页面，包括页面之间的链接结构

- Web 爬虫需要具备的特性
    - 健壮 robustness, 避免 spider traps
    - 友好 politeness, 遵守 web server 的采集协议
    - 分布式 distributed, 多台机器分布式采集
    - 可扩展 scalable, 爬虫架构方便扩展
    - 性能与效率，有效利用系统资源
    - 质量 quality, 倾向于采集有用的页面
    - 新颖 freshness, 获取网页的最新版本
    - 可扩充 Extensible, 能够处理新数据类型、新的采集协议等
- Web 页面爬取策略
    - 深度优先
    - 广度优先
    - 实际应用中以广度优先为主，深度优先为辅
- 难点
    - 暗网的采集，只有向数据库提交查询才形成的 Web 页面
    - Web 2.0 内容，脚本语言等生成的动态内容
    - 多媒体内容

Web 页面排序
页面排序值 = 页面内容相关度 +/* 页面重要性

Web 链接分析

- 理论基础：Web 页面之间的超链关系非常重要，一条从页面 A 指向页面 B 的链接表明
       - A 与 B 相关
       - A 推荐/引用/投票/赞成 B
- 经典算法
    - PageRank
   - Topic-Sensitive PageRank(TSPR)
   - T-Fresh
   - HITS - Hypertext Induced Topic Selection

基于学习的网页排序

Learning to Rank 主要包括三个类别
- Pointwise
    - 训练数据是一个文档类别或分数
    - Accurate score ≠ accurate ranking
    - 忽略文档的位置信息
- Pairwise
    - 训练数据是文档对的一个偏好(一对文档选哪个)
    - Accurate preference ≠ accurate ranking
     - 忽略文档的位置信息
- Listwise
    - 训练数据是文档的排名
    - 难以直接优化 ranking metrics
主流算法有
    - RankSVM
    - RankNet
    - ListNet
Learning to Rank 工具包
    - RankLib
    - people.cs.umass.edu/~vdang/ranklib.html
评价指标
    - WTA(Winners take all)
    - MRR(Mean Reciprocal Rank)
    - MAP(Mean Average Precision)
    - NDCG(Normalized Discounted Cumulative Gain)
    - RC(Rank Correlation)

Search Engines笔记 - Authority Metrics
聚类-小土刀
 爬虫总结(一)– 爬虫基础 & python实现
 爬虫总结(二)– scrapy
爬虫总结(三)– cloud scrapy
爬虫总结(四)– 分布式爬虫
 爬虫总结(五)– 其他技巧
 爬虫总结–汇总贴

伪相关反馈

Pseudo Relevance Feedback 自动产生更好的 query。基本逻辑 是把原始查询当做分类器，用它来给部分数据打标签，得到 top-ranked documents，然后用 labeled data 来产生更优的 classifier。基本过程：

用原始 query 检索文档
取结果的前 N 篇文档作为训练集，这些文档相关度可能不高，然而我们的目的是学习 vocabulary pattern。
应用 relevance feedback algorithm 选取 term 和 term weight
组成新的 query 来检索文档
- Query expansion 平均能使 MAP 提高 20%
- 但同时也有可能让 1/3 的用户感到 annoy

所以通常来说，query expansion 会用在召回率很重要的场景，或者 average performance 很重要的场景，比如 legal retrieval, TREC, research paper 等。

Search Engines笔记 - Pseudo Relevance Feedback

信息检索评价

评价检索模型或搜索引擎的性能
主要考虑搜索质量 vs 搜索效率，这里主要谈搜索质量

评测数据集

一般人工构建
构成
    - 文档集合(documents)
    - 信息需求(information needs)及查询集(queries)
    - 相关性判断(relevance judgements)
已有评测集
    - TREC
        § trec.nist.gov
        § 最具影响力
        § 多种信息检索任务，侧重于英文
    - NTCIR
        § research.nii.ac.jp/ntcir/
    - CLEF
        § www.clef-campaign.org

评价指标

衡量检索结果与标准答案的一致性
- 对 Unranked Retrieval(非排序检索)的评价
    - Precision and Recall
    - P@n
    - F-Measure
    - Average Results(Micro, Macro)
- 对 Ranked Retrieval(排序结果)的评价
    考虑相关文档在检索结果中的排序位置，考虑在不同 recall levels 的 precision 值
    - AP and MAP
    - MRR (Mean Reciprocal Rank)
    - NDCG (Normalized Discounted Cumulative Gain)
    - RBP (Rank-Biased Precision)

评价方法

- Cranfield Methodology
    1. 获得文档(documents)集合
    2. 获得信息需求(information needs)集合
    3. 获得相关性判断(relevance judgments)
    4. 计算(Measure)各种方法找到相关文档的效果
    5. 比较(Compare)各个方法的有效性

- 动态环境下的评价(Interleaved)
 主要用 Interleaved testing 方法。通常输入是两个排序列表，分别由不同方法产生，输出是一个排序列表，由输入的所有文档重新排序产生。
    - Balanced interleaving
        第一次决定从哪个方法开始，然后交替把文档加入 interleaved ranking，如果遇到了已经评估过的文档，就直接 counter++，但是不把文档加进 interleaved ranking 里。
    - Team-draft interleaving
        每一轮都随机产生先取哪种方法，如果有重复，跳过，取下一个。

一般来说，我们更多的会使用 Cranfield，因为
    § Cranfield 更成熟，已经使用了很多年而且易于理解
    § Cranfield 支持大量的 metrics，能提供更多关于 ranking behavior 的信息
    § Cranfield 几乎在所有场景下都使用，而 Interleaving 需要有 query traffic
    § 尽管如此，interleaving 仍然是一个很有用的工具，在 Inexpensive, adaptive, sensitive to small differences 的情景下效果较好

Search Engines笔记 - Evaluating Search Effectiveness

搜索日志

最重要的是两个问题

How to represent users

1. 从日志中得到 (user,query) pairs
2. 为用户创建 pseudo documents
        - 标题: user id
        - 内容: 每条 query 的前 10 篇文档对应的 Yahoo! 分类目录
3. 计算相似度
        e.g. JS divergence, cosine

Segmenting search logs into sessions

- 把 search log 划分为一个个基于信息需求的 dialogue，实际就是用户发出初始查询，搜索引擎给出结果，用户不满意，重新修改查询语句再次搜索，然后得到新的结果，不断循环知道解决问题/放弃检索，这期间的行为就构成了 dialogue
- 划分可以考虑的因素：时间、相同的 term、编辑距离、相同点击、文档类别、分类器等等

Search Engines笔记 - Search logs

搜索引擎优化(SEO)

提高网站或网页在搜索引擎中可见度(排名)的过程

基本思想

- 基于各类搜索引擎的工作原理(采集、索引、排序等)，对网站进行相关的优化的调整，提高网站在搜索引擎中的排名
- 白帽：合理优化，不牺牲用户体验
- 黑帽：不正当优化，牺牲用户体验
    § 重复、隐藏文字、链接工厂、桥页、跳页

影响排名的因素

- 内部因素
    § URL 中出现关键词
    § 网页 Title 中出现关键词
    § 常规内容中出现关键词
    § 在页面的最后一段中出现关键词
    § <Head> 标签 比如 h1, h2 中出现关键词
    § 站内的链接中出现关键词
    § 导向相关内容的导出链接
    § 导出链接中出现关键词
    § 图片文件名中出现关键词
    § Alt 标签中出现关键词
    § comment 中出现关键词
    § 合理的频率更新内容
    § 内容对搜索引擎的展示位置
    § 网站结构循环 PR, 而非散发 PR
    § 关键词进行适当的修饰(加粗、斜体等)
- 外部因素
    § 大量的导入链接
    § 从高 PR 值的网页获得导入链接
    § 从相关内容网站获得导入链接
    § 导入链接指向的网页有具体内容
    § 锚文字中有关键词
    § 锚文字周围有相关词
    § 锚文字存在于文章或句子中
    § 导入链接的时间长度，一般导入链接的存在时间有3-6个月
    § 单向链接的价值高于交换链接
    § 导入链接的页面的导出链接小于 100 个，流出链接越少越好
    § 链接来自不同 IP
    § 合理的导入链接增长频率

SEO 操作

- 站外 SEO
    § 网站外部链接优化、网站的链接见识、网站的外部数据分析等
    § 交换、购买链接，提交网址到分类目录等
- 站内 SEO
    § 网站结构的设计、网站代码优化和内部链接优化、网站内容的优化、网站用户体验优化等

建议：丰富网站关键词、主题集中、友好的网页结构、避免重复、有规律的更新等

聚类-小土刀