Search Engine basics

一、搜索引擎的发展历史

搜索引擎最早并不是 Web 搜索引擎。从 1990 年代初开始出现各种原始信息搜索工具：

  • Archie、Veronica、Gopher：早期网络文件/菜单搜索工具，不是真正的网页搜索。
  • 1993 年左右出现最早的 Web 搜索尝试，比如 Wanderer、ALIWeb。
  • 1994–1997 年出现了大量搜索引擎（Excite、Lycos、Yahoo、AltaVista、Ask Jeeves 等）。
  • 1998 年 Google 的出现标志着现代搜索引擎时代的开端，它用链接分析（PageRank）等新方法推进了相关排序技术。

这一段历史说明：搜索引擎从简单索引工具逐步发展成复杂的系统，从单纯文本匹配走向结合统计与链接结构的排序逻辑。

二、什么是搜索引擎

搜索引擎是一个计算机程序，其目的是：

帮助用户查找存储在某个系统（如 Web 或企业网络）中的信息。

这里的 “信息” 可以是网页、文档、图片、视频，只要用户能查到。

搜索引擎包括集中式（Web 这样的大规模）和专用的企业/个人搜索系统。

三、搜索引擎的主要组成部分

一个典型的搜索引擎包含如下核心组件：

  1. 用户（User）

用户通过查询界面提交搜索请求，用户行为（搜索历史、点击行为）会影响个性化排序。

  1. 爬虫 / Spider / Crawler

自动遍历 Web 页面、抓取网页内容、提取链接，为索引构建做准备。 工作的核心是递归抓取 URL、解析 HTML、发现新链接。

  1. 索引器（Indexer）

把爬取到的文本转换为可检索的数据结构（例如倒排索引），包括词表处理、停用词过滤、词干提取等。

  1. 索引结构（Indexes）

如倒排索引（term → 文档列表）和其他辅助索引（URL、anchor text、元数据等），用于快速查找匹配内容。

  1. 广告索引（Ad Indexes）

专门存储广告内容及其关键词匹配结构，这是搜索引擎商业变现的重要部分。

  1. 查询处理器（Query Processor）

处理用户输入的查询，进行分词、符号处理、语义扩展，然后查索引并返回结果。

以上组件共同协作，使得搜索引擎能够高效地从海量信息中返回匹配结果。

四、Web 和搜索引擎的挑战

搜索引擎面对 Web 时有几个关键难点：

  • Web 是开放且无序的分布式系统：没有中心结构，内容动态生成；
  • 数据异构：文本、图片、视频等多种形式；
  • Web 规模巨大：文档数量呈指数级增长；
  • 质量问题：页面可能包含错误信息、SEO 干扰、垃圾内容。

因此除了简单抓取和索引，搜索引擎还需要大量策略来提升效率与质量。

五、用户对搜索的需求

PPT 中提出：用户需求是多样的，通常可以分为几类：

  • 信息型（Informational）：想了解某个主题；
  • 导航型（Navigational）：想访问特定网站；
  • 事务型（Transactional）：想完成某个操作（下载、购物等）。

理解用户意图对排名与界面设计非常重要。

六、查询处理的智能化趋势

现代搜索不再是简单匹配词项，还会：

  • 识别查询语言；
  • 过滤停用词；
  • 推断查询意图（个性化、地理位置、历史偏好）；
  • 用上下文信息改善返回结果。

这些处理提高了相关性和用户体验。

七、搜索结果不是孤立的

搜索返回的并不只是文档链接，而是“整体结果”，可能包括：

  • 新闻摘要；
  • 地图信息；
  • 图片、视频；
  • 相关主题推荐等。

这说明现代搜索重视用户全方位信息需求，而不是简单匹配关键词。

八、搜索引擎作为产业

搜索引擎不是单纯技术，它是一个产业：

  • 收入主要来自广告，例如付费搜索竞价广告；
  • 公司如 Google、Bing、百度 都有巨量商业规模；
  • 搜索引擎技术和广告生态紧密耦合。

PPT 展示了搜索引擎行业收入规模及竞争分布，说明它不仅是学术课题，也是商业核心。

九、Google 在搜索行业的地位

课件特别引用了 Google 的历史与市场地位，说明它：

  • 在 Web 搜索领域占主导；
  • 索引规模最大；
  • 维护全球最大 Web 数据库。

同时由于其市场规模，也引发监管和公平竞争问题。

Web Serving Basics

这节课主要讲了 Web 的基本特征与趋势，为什么搜索引擎设计需要考虑规模、动态性、多样性以及网络结构等复杂属性。 Web 已经从几十年前的小规模、静态集合发展成一个极其庞大、动态生成、海量数据的分布式系统，这些特性决定了搜索系统必须采用分布式抓取、索引、存储与检索的架构。

全球互联网发展的趋势：全球数十亿用户连接网络，移动流量占比超过一半，在线视频和社交媒体增长极快，每分钟上传到 YouTube 的视频达到数百小时级别，全球数据量以指数级增长，达到以 Zettabyte 为单位的规模。这些统计说明 Web 不再是少量静态页面，而是一个巨大、不断膨胀的实时内容生态。

从不同维度讨论如何“衡量 Web”：通过网站的数量、域名分布、网页语言多样性、不同内容类型（文本、图片、视频、音频、二进制文件等）的比例、以及页面的变化速率等指标来描述 Web 的复杂性。数量级上讲，Web 含有数十亿网站和数万亿唯一 URL，如果完全存储一份快照需要数百 PB 级别存储，这已经远超传统单机级能处理的规模。

Web 的动态性和测量难度：Web 页面不断被创建、删除、更新，这让对 Web 的统计变得很难长期有效；不同的抓取方式可能导致不同的样本特性，这些都对搜索引擎的抓取策略和索引设计提出挑战。虽然完整意义上描述整个 Web 几乎不可能，但通过大规模抓取和统计仍然可以捕捉到一些代表性趋势。

一些 Web 的基本事实统计：全球网站分布、不同顶级域（.com、.de 等）的数量比例、网页内容语言的多样性、以及 Webgraph 的基本属性。这一部分虽然数据本身会随着时间更新，但核心思想是：Web 是一个极其巨大的、异质的、动态变化的网络系统，它的规模和结构特性必须成为搜索引擎设计的基本前提。

一句话总结这节课：Web 已经不是简单的静态页面集合，而是一个规模巨大、结构复杂、实时演化的网络，由此决定了搜索引擎必须用分布式架构、图结构分析、动态索引和高效数据处理技术来应对 Web 的本质特点。

Search Engine Evaluation

Crawler → Indexer → Query Processor → Ranking → Results

评价不是看界面，而是用指标和实验方法衡量系统返回结果的质量和排序表现。指标既要反映查准性、查全性，又要考虑结果的位置及用户体验。

搜索引擎评估的核心是：对于一个查询，系统返回一串排序结果，你需要判断哪些是“相关”（relevant），哪些是“不相关”。不同指标从不同角度把这个结果串的表现量化出来，让你能比较不同模型或不同版本的效果。

质量评估指标

最基础的衡量是 Precision（查准率） 和 Recall（查全率）。

  • Precision = TP / (TP + FP)，即被检索出的相关文档占所有检出的比例。
  • Recall = TP / (TP + FN)，即被检索出的相关文档占所有相关文档的比例。 这里 TP 是检索到的相关文档数，FP 是检索到的非相关文档数，FN 是未检索到的相关文档数。 两者反映不同侧重点：Precision 强调结果干净、少噪声；Recall 强调覆盖全面。

F-Measure（F-score）

Precision 和 Recall 有权衡关系。F-score 是它们的调和平均数，通过对两者取加权调和平均反映综合表现。 F₁（默认 β = 1）是最常用的形式，强调 Precision 和 Recall 同等重要。数学上它是：

\(F_1 = 2 × \frac{Precision × Recall}{Precision + Recall}\)

它在检索评估中常用于在同一个数值上综合反映查准与查全。

平均 Precision 与 MAP（Mean Average Precision）

对于一个查询，你可以计算每个相关文档在结果列表中出现时对应位置的 Precision，然后求平均，这就是一个查询的 Average Precision（平均精度）。 对一组查询集计算平均，就得到 Mean Average Precision（MAP）。MAP 是 IR 研究中常用的指标，代表系统在多个查询上的整体表现，强调的是相关结果越全文提取得好越高。

\(MAP = \frac{\sum_{q=1}^{Q} AP(q)}{Q}\)

DCG / NDCG（折损累计增益与归一化）

现实检索更关注 位置排位：把相关结果排在前面更重要。为此引入了 Discounted Cumulative Gain（DCG）。它用每个结果的相关性得分除以一个与位置相关的衰减因子（通常是 log₂(rank+1)），把越靠前的结果权重更高。

如果用相关性等级（如 0 = 不相关, 1 = 有点相关, 2 = 很相关 等）：

\(DCG_p = \sum_{i=1}^{k} \frac{rel_i}{\log_2(i+1)}\)

这样能量化排序的质量。为了能比较不同查询，使用 Normalized DCG（NDCG）：把 DCG 除以理想排序（IDCG）的 DCG，得到一个 0~1 的标准值。NDCG 越大说明系统排序越好。

评估实验与用户反馈

课件里还提到评估方法不只是指标：要结合真实用户行为和实验。搜索引擎常用 人工标注的测试集合（relevance judgments）来评测，因为系统内部日志里的点击数据可能有位置偏差（比如用户更容易点前面结果）并不能直接代表相关性。

另外大公司（如 Google）会组织 Search Quality Raters（人工评估团队）使用统一标准对查询结果打分，再把这些统计数据用于优化模型。阿布测试（A/B Testing）也是常用方法：对比两个版本在真实用户流量下的点击/满意度差异，从而评估改动效果。

评价指标的意义与应用

  • Precision / Recall 强调查准查全，但只关注二值相关性，不看排序。
  • F-score 综合考量查准查全，适合单一数值比较。
  • MAP 更适合研究和学术评估，在多个查询上综合比较性能。
  • DCG / NDCG 考虑位置影响，更接近用户体验评价。
  • 用户点击和 A/B Testing 则是工程层面评估，反映真实用户行为，但需注意噪声和偏见。

Web Crawling

Web Crawling 是搜索引擎、搜索系统的第一步，就是 系统地遍历 Web、抓取网页内容和结构。

Web Crawling 是搜索引擎系统的第一步，也是整个搜索系统的“数据入口”。搜索引擎不可能在用户查询时才去实时访问整个互联网，因此必须提前把网页抓取下来、解析并建立索引。爬虫（crawler、spider、bot）的任务就是系统性地遍历 Web，把页面内容和链接结构收集起来，为后续倒排索引和排序算法提供原始数据。

从结构上看，Web 可以被视为一个巨大的有向图：每个网页是一个节点，超链接是边。爬虫的本质就是对这个图进行遍历。遍历的起点是一组种子 URL（seed URLs），爬虫从这些页面开始抓取，解析出页面中的链接，再把新发现的链接加入待抓取队列，循环进行。这一过程不断扩展覆盖范围，因此常被称为“frontier 扩展”。

为了管理抓取顺序，系统会维护一个 URL frontier（待抓取队列）。这个队列不仅是简单的先进先出，还会根据策略进行优先级调度。例如，新闻站点更新频繁，应该高频抓取；而博物馆介绍页面多年不变，可以低频抓取。老师在课上强调过一个重要思想：爬虫不仅要“抓得多”，还要“抓得聪明”。盲目遍历会浪费资源。

爬虫必须遵守 robots.txt 规则。robots.txt 文件放在网站根目录，用于声明哪些路径允许抓取、哪些不允许。一个规范的搜索引擎必须先读取 robots.txt 再决定抓取范围。这体现了所谓的“politeness policy”（礼貌抓取策略）。除此之外，还要控制抓取频率，避免短时间内向同一服务器发送过多请求，否则可能被视为攻击。

现实中的 Web 规模极其庞大，因此单机爬虫是不可能完成任务的。大型搜索引擎采用分布式架构，多台机器并行抓取，每台机器负责不同域名或不同 URL 范围。抓取过程中还必须处理网络错误、服务器超时、重复页面、死链接等问题。这使得 Web Crawling 不只是算法问题，更是大规模工程系统问题。

老师特别讲到“重复抓取”和“动态网页”的问题。很多网站内容相同或高度相似，如果不做去重，索引会膨胀并浪费存储。动态页面还可能在每次访问时生成不同参数的 URL，形成“爬虫陷阱（crawl trap）”，导致爬虫陷入无限扩展。因此爬虫系统必须有去重机制（如记录已访问 URL 或利用哈希技术）以及策略限制。

在课堂中老师强调了一个关键点：爬虫不是为了抓“所有页面”，而是为了抓“有价值页面”。真正重要的是高质量页面和高链接权重页面。Web 具有明显的幂律结构（少数页面有大量入链），因此可以通过链接结构优先抓取重要节点。

与 Web Scraping 不同，Web Crawling 面向的是整个 Web 生态，是系统级行为；Scraping 通常针对特定站点、特定目标数据。搜索引擎爬虫必须保持长期运行，不断刷新内容，因为 Web 是动态变化的。

总结来说，Web Crawling 是搜索引擎的基础设施层。它解决的问题是：如何在一个规模巨大、动态变化、分布式且结构复杂的网络中，高效、合法、稳定地获取尽可能多的有价值网页。没有高质量的爬虫，就没有后续的索引、排序和检索。

Deduplication

在大规模爬取的过程中，会出现两个问题：

1）Exact Duplicate（完全重复）

  • 多个 URL 可能指向相同内容（例如镜像网站、同样内容不同参数）。
  • 如果不处理，会浪费存储和索引资源。

2）Near-Duplicate（近似重复）

  • 页面内容几乎一样但有细微改动（比如广告变动、时间戳变化）。
  • 对搜索引擎来说，保留这些重复内容对用户体验没价值。

Deduplication 的核心目标

识别并剔除重复或近重复的网页，节省存储和计算成本，同时提升搜索结果的质量。

传统 Hash（如 MD5）的问题

  • MD5 是加密式哈希：输入只要一丁点变化，输出 hash 完全不同。
  • 这种哈希适合检测绝对一样的内容，但不能反映“内容近似”。

举例：两个只差一个空格的文本，其 MD5 完全不同，但内容几乎相同 —— 传统 hash 检不出来。

真实世界要关注“相似度”

为了处理 near-duplicates，需要一种 hashing 方法让：

  • 输入内容小改动 → hash 只小幅改变；
  • 输入内容大改动 → hash 猛烈改变。

这类 hash 称为 局部敏感哈希（Locality Sensitive Hashing, LSH）。

SimHash（特征降维+相似指纹）

SimHash 是一种 LSH 算法，非常适合在大规模爬虫/搜索场景下做去重。

它的核心思想：

  1. 提取特征（词、shingle 等）；
  2. 用普通 hash 把每个特征映射到 bit 向量；
  3. 对所有特征的 bit 向量按权重累加（出现 +1，没出现 -1）；
  4. 最终把累加结果按符号转成固定长度二进制 fingerprint。

结果：

  • 内容非常相似的文档 → fingerprint 很接近（海明距离小）；
  • 内容差异很大的文档 → fingerprint 差异大。

海明距离（Hamming Distance） = 两个二进制串不同位置的个数 它是 SimHash 判断相似度的衡量标准。

为什么 SimHash 好用？

  • 它使得“相似”在 hash 输出空间中变得可度量；
  • 与传统 hash 相比，小改动不会导致 hash 大变；
  • 便于在大规模网页库中快速判断近重复；
  • 可结合排序/索引优化避免 O(n²) 全比较。

大规模去重的优化思路（在课程图示中体现）

  • SimHash 输出固定长度（二进制） fingerprint；
  • 对所有 fingerprint 排序；
  • 通过邻近比较或“小窗口滑动检查”来找可能相似对；
  • 结合 bit 旋转/分块等技术可以提高命中率而非全对比

这种 approach 比一对一计算每个文档相似度要高效得多。

核心目标：在海量网页中快速识别 near-duplicate 文档，避免重复内容被索引和存储，从而提升检索效率和质量。

Information Retrieval

如果在考试中问了什么是IR，一个单词概括就是Similarity

把“搜索”从工程问题上升到数学建模问题。

信息检索（IR）的本质是：在一个巨大的文档集合里，找到对用户查询最“相关”的文档。过去所谓的信息检索，其实只是“文档检索”——系统给你一堆链接，你自己去读。现在的 RAG 和向量数据库，本质上还是 IR，只是把“相关性计算”做得更精细，再由模型生成答案。

真正的关键问题只有三个：文档如何表示？查询如何表示？相关性如何计算？

第一种模型：Boolean Model（布尔模型）。布尔模型是最原始的做法。文档里有这个词就匹配，没有就不匹配。AND/OR/NOT 是刚性的逻辑，没有“部分匹配”的概念，也无法表达“更相关”。它解决的是“是否满足条件”，不是“谁更好”。

第二种模型：Vector Space Model向量空间模型。向量空间模型是真正的转折点。1. 文档怎么表示？把整个词汇表当成一个高维坐标系，每个词是一个维度，每篇文档是一个向量。某个词出现几次，就在那个轴上有多大的值。2. 查询也被表示成同样的向量。 3. 怎么判断相关？ Dot Product和Cosine Similarity于是检索问题变成几何问题：哪个文档向量和查询向量夹角最小？cos(θ) 最大的，就是最相关的。这就是现代 embedding 检索的数学原型。

权重（weight）其实就是词频（TF）。词出现越多，那个维度的分量越大，向量越往那个方向偏。后面再配合 IDF 才形成完整的 TF-IDF，但这节课已经建立了核心直觉：词频就是重要性。

TF-IDF 是一种衡量某个词在某篇文档中“重要程度”的权重。

\(w_{ij} = tf_{ij} \cdot idf_j\)， TF（Term Frequency），这个词在该文档中出现了多少次；IDF（Inverse Document Frequency）：这个词在整个语料库中“稀有程度”。公式：

\(idf_j = \log \frac{N}{df_j}\)

如果向量变成二进制（出现=1，不出现=0），相关性就可以用 Hamming distance 来算；如果用实数向量，就用 dot product 或 cosine。无论哪种形式，本质都是在计算“距离”或“相似度”。距离小，相似度高；距离大，相似度低。相似度和距离是对偶关系。

常见相似度算法：

不考虑位置：

  • Cosine similarity：把文档或查询表示成向量（比如 TF-IDF 向量），然后计算两个向量之间的夹角。
  • Jaccard：衡量两个“集合”的重叠程度，交集/并集

考虑位置：

  • Edit distance：衡量把字符串 A 变成字符串 B 需要多少次“编辑操作”
  • N-gram sequence：连续的 N 个词（或字符）组成的序列
  • Hamming(bit-difference) distance

倒排索引的作用是让搜索变成对索引的快速查找，而不是对全文扫描。搜索发生在 index 上，ranking 发生在取出的候选集合上。用户点击行为又会反过来作为 relevance feedback 修正模型。这是搜索引擎不断优化排序的基础思想。

embedding 和向量数据库：现代 RAG 并没有推翻传统 IR，而是把向量表示从“词频向量”升级成“语义向量”。查询变成 embedding，文档也变成 embedding，然后做向量相似度搜索。原理没有变，只是表示方式更聪明。

Text Processing

  1. 文本分类的核心任务 (Text Classification)

文本分类是指将文档（或文本片段）分配到一个或多个预定义类别的过程。讲义中提到了几个典型应用场景：

  • 垃圾邮件过滤 (Spam Filtering)： 区分垃圾邮件（Spam）和非垃圾邮件（Ham）。
  • 语言识别 (Language Identification)： 自动判断文本所属的语言。
  • 主题分类 (Topic Classification)： 例如将新闻分为政治、体育、科技等。
  1. 核心算法与模型

讲义介绍了多种用于文本分类的模型，涵盖了从传统统计方法到深度学习的内容：

  • 朴素贝叶斯 (Naive Bayes)： * 这是文本分类中最经典的基准算法。
    • 基于贝叶斯定理，假设特征（单词）之间相互独立。
    • 提到了 Paul Graham 的垃圾邮件过滤实验。
  • 神经网络 (Neural Networks)： * 强调了神经网络是目前最强大的监督学习架构之一。
    • 特别提到了使用 交叉熵损失函数 (Cross-Entropy Loss) 来训练分类器。
  • Rocchio 分类法：
    • 利用质心 (Centroids) 来定义每个类别的区域。
    • 通过计算新文档到各个类别质心的距离来进行分类，涉及到了 Voronoi 图 (Voronoi Regions) 的概念。
  • 支持向量机 (SVM)：
    • 旨在寻找能够最大化类别间距的超平面 (Hyperplane)。
  1. 关键工具与案例
  • SpamAssassin： 讲义引用了 Apache SpamAssassin 作为一个真实的工业级垃圾邮件过滤案例。
  • 特征提取： 讨论了如何将文本转换为机器可以理解的向量形式（如词袋模型、TF-IDF 等，尽管部分细节在图片中，但这是文本处理的通用背景）。

4. 分类过程的逻辑

  • 训练 (Training)： 使用带有标签的文档集来学习分类模型。
  • 测试/评估 (Evaluation)： 在未见过的测试数据上验证模型的准确性。
  • 决策边界： 讲义通过视觉化的图片展示了不同算法如何划分特征空间，例如线性划分与非线性划分的区别。

Inverted Index

核心主题：倒排索引。它是搜索引擎最核心的数据结构，也是后面所有检索模型（包括 RAG、向量数据库）能够工作的基础。

倒排索引本质是一个 Key–Value 结构。Key 是用户可能搜索的词（term），Value 是包含该词的文档列表（postings list）。和传统书本的索引类似，只不过方向是反过来的：传统是“一本书 → 很多词”，倒排索引是“一个词 → 很多文档”。因此叫 Inverted Index。

搜索引擎之所以快，不是因为“实时扫描网页”，而是因为提前构建好了倒排索引。当用户输入一个词，比如 “banana”，系统做的事情是：在排序好的词典里用二分查找迅速找到这个词，然后直接取出对应的文档列表，再进行排序输出。查找复杂度是 O(log n)，而不是遍历所有网页。

倒排索引的构建过程包括：分词、大小写统一、去除停用词（the, a, of 等）、词干提取（run / running → run）、统计词频。每个词不仅存储出现在哪些文档，还可以存储出现次数（Term Frequency）和位置（Position）。位置索引可以支持短语查询，比如 “computer architecture” 必须按顺序出现。

排序时使用 TF-IDF 思想。TF（Term Frequency）表示词在文档中出现的次数，出现越多越重要。DF（Document Frequency）表示该词出现在多少个文档中。如果一个词出现在几乎所有文档里（如 the），说明它区分能力弱。于是使用 IDF = log(N / df) 来惩罚高频词。最终权重是 TF × IDF。这个模型后来发展成 BM25，是工业界真正使用的改进版本。

当查询包含多个词时，比如 “Brutus AND Caesar NOT Calpurnia”，系统会分别取出每个词的 postings list，然后做集合运算。核心操作是合并有序列表。最基础做法是线性 merge，时间复杂度 O(n)。为了优化，倒排列表中可以加入 Skip Pointers（跳跃指针），允许在合并时跳过大片不匹配区域，从而加速 AND 查询。

短语查询可以通过三种方式实现：基于位置索引做精确匹配、建立 biword 索引（把常见词对当作一个 term）、或使用 n-gram 索引。实际搜索系统会根据用户查询日志，把高频短语单独建索引以提高效率。

老师特别强调：倒排索引的价值极高。它是搜索引擎最核心资产之一。美国司法部曾考虑要求 Google 分享其索引，因为建立一个高质量、规模巨大的倒排索引需要多年积累。

总结来说，这节课的核心理解是：搜索不是扫描网页，而是在预构建的倒排索引上做集合运算和排序。倒排索引负责“找候选文档”，TF-IDF/BM25 负责“排序”，两者结合才构成完整的信息检索系统。

Video Search Engines

这节课一开始老师讲的是 Agent 世界的快速变化。Cloud/OpenCloud、PicoCloud、在 10 美元硬件上跑 agent、Android 手机跑 agent、Meta 眼镜接入 agent 等等，这些例子本质上是在说明：Agent 已经不再是实验室概念，而是可以运行在边缘设备上的系统。Agent 不仅仅做文本问答，而是可以调 API、操作应用、执行循环调用工具（tool loop），直到满足用户高层目标。老师强调，很多 orchestration 逻辑已经可以由模型自己写出来，人类不再手动写复杂 agent 框架。这背后的核心结构是：大模型（pretrain + fine-tune + RLHF）只是中枢，大量能力来自外部工具调用与循环执行。

随后老师强调一个非常重要的观点：AI 生成能力（video、3D、音频）正在冲击传统内容创作行业，但这些系统“仍然不理解世界”。它们只是基于概率生成 token。生成的视频、动画可能看起来逼真，但在物理一致性、逻辑一致性上会出现严重错误。这和信息检索里的“幻觉”问题是同源的：模型生成的是高概率输出，不是事实。

课堂后半部分进入真正的技术主题：Video Search Engine。

老师用 YouTube 作为案例说明视频检索系统的整体架构。

首先是系统架构层面。一个视频平台至少包含：

  • Load Balancer（负载均衡）：分发用户请求。
  • Web Server / Application Server：处理业务逻辑。
  • Media Storage：原始视频存储。
  • Transcoding Server：转码成不同分辨率和格式。
  • CDN（Content Delivery Network）：在全球边缘节点缓存视频，减少延迟。
  • Metadata Storage：保存视频标题、描述、标签等文本信息。
  • User Database：保存用户观看历史与偏好。

上传视频是“push”模型：内容创作者主动上传，系统无需爬虫。和 Web crawling 不同，视频平台通常不需要主动去外部抓视频，而是用户提交。

当用户搜索时，真正被搜索的并不是“原始视频帧”，而是 metadata。标题、标签、描述、字幕文本等构成了可索引文本。也就是说，视频搜索的核心仍然是文本倒排索引，只不过索引对象从网页变成视频条目。

视频检索的核心流程和普通 IR 非常类似：

  1. 用户输入查询词。
  2. 系统在 metadata 的 inverted index 中查找匹配视频。
  3. 得到候选视频集合。
  4. 进行排序（ranking）。
  5. 返回排序后的视频列表。

排序信号包括：

  • 观看次数
  • 点赞数
  • 用户互动率
  • 上传时间（新视频通常加权）
  • 视频长度（短视频更易传播）
  • 用户历史兴趣（推荐系统信号）

这本质上是经典 IR + 推荐系统融合。

视频检索和文本检索的区别在于：视频有多模态特征。

除了标题和标签，还可能包含：

  • 自动生成字幕（Speech-to-Text）
  • OCR（视频中的文字识别）
  • 画面内容识别（对象检测）
  • 音频情绪识别
  • 视觉 embedding

但当前大规模视频搜索仍然严重依赖文本代理（metadata proxy），而不是直接索引视频内容本身。

视频平台中的附加技术：

Closed Caption（可开关字幕） Open Caption（烧录进视频，无法关闭） Speech Recognition（自动语音转文本） OCR（视频内文字识别） Transcoding（多码率适配不同设备）

这些技术本质上都是为了增强“可检索性”和“可访问性”。

一个非常重要的延伸是：信息检索正在向信息生成转变。

过去：搜索 → 返回文档 现在：搜索 + 聚合 + 生成 → 返回摘要或新内容 未来：生成全新视频（例如自动拼接多个视频片段做 summary montage）

老师举的例子是：假设搜索“kite flying”，系统不仅返回视频列表，还可以自动从前 100 个视频中抽取最精彩 3 秒，拼成一个总结视频。这就是从 IR 走向 IG（Information Generation）。

视频搜索引擎本质仍然是倒排索引 + 排序系统，只是对象从网页变成视频，多模态技术增强可检索性，而未来趋势是从信息检索走向信息生成。

Querying

Querying 这一部分主要讲的是搜索引擎如何处理查询、如何改进查询结果，以及如何评价一个搜索引擎的好坏。老师首先强调，查询不仅仅是用户输入几个关键词然后返回结果这么简单，它背后涉及排序机制、用户行为反馈、查询扩展以及评估指标等多个层面。

在传统查询模型中，搜索引擎基于关键词匹配进行检索，早期主要使用布尔查询语言，例如 AND、OR、NOT 这样的逻辑运算符来精确控制查询条件。用户可以指定必须包含某些词、排除某些词。这种方式强调精确匹配，属于经典信息检索方法。后来发展为基于 tf-idf 的向量空间模型，通过计算词频和逆文档频率来衡量文档与查询之间的相关性，从而进行排序。

接着老师讲到了 Query Expansion 和 Relevance Feedback。现代搜索引擎会根据用户的点击行为来改进排序。例如，当你搜索一个问题时，页面上会出现 “People also ask” 或 “Related searches”。如果大量用户在搜索某个词后点击某些相关问题，搜索引擎就会记录这种行为，在未来提高这些结果的排名。这种机制叫做 Relevance Feedback，即用户点击行为作为相关性信号反向优化排序系统。点击行为可以被理解为一种隐式反馈，如果 90% 的用户点击某个结果而不是当前第一名结果，说明排序可能需要调整。

老师还讲到了 Related Search 的概念。例如你搜索 rock bands，系统会推荐 metal、emo、punk 等相关类别。这些并不是你明确输入的查询，而是基于用户群体行为产生的查询扩展。这属于查询重构（Query Reformulation）的一种方式，可以帮助用户发现自己没有想到的相关信息。

另一个重要概念是 Standing Query。Standing Query 是指持续查询机制，也就是当用户设置一个长期关注的关键词时，系统会自动监控新内容并推送给用户。例如 Google Alerts，当有新的网页或新闻匹配你的关键词时，系统会自动发邮件通知。这种机制体现了 Push 和 Pull 的区别。Pull 是用户主动搜索，Push 是系统主动推送。这实际上是一种持续性的查询匹配和分类过程。

在查询评估方面，老师重点讲了 Mean Reciprocal Rank（MRR）。这是评价搜索引擎性能的重要指标。具体做法是：对于每个查询，找到正确答案出现的位置 rank，然后计算 1/rank。多个查询的结果取平均值，就是该搜索引擎的 MRR。这个指标的意义在于，正确答案越靠前，1/rank 越大，平均值越高。如果正确答案根本没有出现在结果中，则可以视为 rank 为无穷大，对应的倒数为 0。这样 MRR 就能够惩罚那些没有正确答案或把正确答案排在很后面的搜索引擎。老师强调，在实际应用中不会只用 3 个查询测试，而是会用几百甚至几千个查询来获得稳定评估结果。

老师还提到 Custom Search Engines，例如 Google Scholar、Google Books 或专门的专利搜索系统。这些系统看起来和普通搜索引擎类似，但它们的索引范围不同，只针对特定领域进行搜索。这说明查询系统可以针对不同数据集进行定制。

在现代搜索环境中，查询不再仅仅基于关键词匹配，而是进入了语义检索阶段。老师举例说明视频搜索系统如何通过 embedding 技术将视频帧映射到向量空间中，从而实现语义搜索。embedding 的核心思想是将具有相似语义的内容映射到向量空间中相近的位置，使搜索从“词匹配”升级为“语义匹配”。这意味着查询可以是文本、图片甚至视频片段，多模态搜索成为可能。

总体来说，Querying 这一部分围绕四个核心思想展开：第一是传统关键词与布尔查询模型；第二是用户行为驱动的查询扩展与相关反馈；第三是搜索引擎性能评估方法，尤其是 MRR；第四是现代基于向量和 embedding 的语义查询。查询系统从简单的字符串匹配逐渐演变为结合统计模型、用户行为数据以及深度学习技术的复杂系统，其目标始终是将最相关的结果尽可能排在最前面。

Search engine advertising

Search Engine Advertising 本质上是一个实时竞价系统。当用户在搜索引擎中输入一个查询词时，系统不仅会返回自然排序结果，还会触发一次广告拍卖。所有购买了该关键词的商家都会自动进入这场拍卖。搜索引擎不会简单地按照谁出价最高来排序，而是通过一个综合排名公式来决定广告位置，这个公式是广告出价（Bid）乘以质量分（Quality Score）。老师强调，排名不是单纯拼钱，而是拼“出价 × 质量”。即使某个商家出价较低，只要质量分高，仍然可以排在前面。

质量分是搜索引擎内部计算出来的一个指标，主要依据广告历史表现，例如过去的点击率（CTR）、用户互动情况、页面质量和相关性等。老师提到，这些数值是搜索引擎根据历史数据估计出来的，比如广告过去被点击了多少次，用户是否真正对内容感兴趣。因此，一个广告如果经常被点击，说明用户认为它有价值，质量分就会提高，从而在未来的竞价中更有优势。

广告位置与点击率之间存在明显差异。排名第一通常能获得最多点击，老师举例说明排名第一大约可以获得 42% 的点击率。这意味着广告主会非常重视排名位置，因为更靠前的位置直接带来更多流量和潜在收益。因此广告竞价本质上是一种商业博弈，企业不断调整出价和策略，以获得更优展示位置。

老师还讲到广告营销活动（Ad Campaign）的概念。企业可以同时运行多个广告项目，为不同关键词设置不同出价，并进行 A/B 测试来优化效果。广告主会不断测试不同关键词、文案和预算组合，以观察哪种组合带来更高点击率和转化率。这种系统化的广告管理方式在商业中被称为营销活动（Marketing Campaign）。

在讲广告机制之前，老师回顾了早期的 SEO（搜索引擎优化）历史。过去曾经存在“关键词堆砌”（Keyword Stuffing）等作弊行为，即在网页源码中反复隐藏关键词以提高排名。但现在搜索引擎算法已经足够成熟，会惩罚这种行为，因此黑帽 SEO 基本失效。如今如果想稳定排在搜索顶部，付费广告成为更加直接有效的方式。

老师还提到一个新的趋势叫做 Generative Engine Optimization（GEO）。随着生成式 AI 的发展，未来不仅要优化网页以适应传统搜索引擎，还要优化内容以便被生成式 AI 系统引用。这意味着广告与内容优化的对象正在从“传统搜索引擎”扩展到“生成式搜索引擎”。

最后，老师强调这个广告系统的商业逻辑：企业之间通过竞价竞争流量，而搜索引擎平台无论排名如何都会盈利。这种机制使搜索引擎成为一个拍卖平台，广告排序既反映市场竞争，也反映用户行为数据。

总体而言，Search Engine Advertising 是一个结合实时拍卖机制、用户行为反馈和质量评估体系的复杂系统。其核心在于出价与质量分的乘积决定广告排名，而点击率与历史表现又反过来影响质量分，从而形成一个动态循环的商业优化过程。

期中复习

The Web

核心本质

  • Web 是一个 有向图 (directed graph)
  • 页面 = nodes
  • 超链接 = edges

\(G=(V,E)\)

特征

  • 非结构化 / 半结构化
  • 动态内容
  • 大规模
  • 频繁更新

IR 角度重要点

  • link structure ≠ relevance
  • 规模极大 → 必须 index
  • 需要 crawling

Web Crawling

定义

自动抓取网页内容。

两种遍历方式

BFS（Queue）

  • 广度优先
  • 更 topical
  • 早期质量高

DFS（Stack）

  • 深度优先
  • 容易跑偏

数据结构

  • Queue → FIFO
  • Stack → LIFO

现代挑战

  • JavaScript 渲染
  • 动态内容
  • anti-bot
  • robots.txt

Indexes（尤其 Inverted Index）

核心问题

没有 index：

\(O(N) \text{ scan every document}\)

不可扩展。

Inverted Index 结构

\(term \rightarrow [doc_1, doc_2, ...]\)

查询流程

  1. 分词
  2. 查 posting list
  3. 交集 / 合并
  4. 排序

时间复杂度

\(O(\log N) \text{ 或近似常数级}\)

Search Engines

架构

Crawler → Indexer → Query Processor → Ranking → Results

核心目标

  • Relevance
  • Speed
  • Scalability

关键区别

Retrieval ≠ Ranking

Ranking

为什么重要？

  • 用户 top-down 扫描
  • 只看前几条

经典公式

DCG：

\(DCG = \sum_{i=1}^{n} \frac{rel_i}{\log_2(i+1)}\)

MRR：

\(MRR = \frac{1}{Q} \sum \frac{1}{rank_i}\)

设计思想

  • penalize lower ranks
  • diminishing returns

Hashing

定义

将 key 映射到固定大小空间。

\(h(key) \rightarrow index\)

用途

  • term lookup
  • O(1) access

冲突处理

  • chaining
  • open addressing

IR 中

  • dictionary → hash table

Classifying

定义

将文档分配到类别。

常见算法

Rocchio

\(\vec{c} = \frac{1}{|D_c|} \sum_{d \in D_c} \vec{d}\)

centroid-based

kNN

  • 选 k 个最近邻
  • majority vote

NN

  • 最近一个

几何视角

  • 向量空间
  • 点 / cluster / centroid

SIMILARITY

定义

衡量两个对象“相似程度”。

Cosine Similarity

\(\cos(\theta) = \frac{\vec{d} \cdot \vec{q}}{||d|| \, ||q||}\)

Jaccard

\(J(A,B) = \frac{|A \cap B|}{|A \cup B|}\)

Edit Distance

\(\text{min operations to transform}\)

Binary Similarity

  • TP, FP, FN, TN

SimHash

\(HammingDistance(h_1, h_2) \le k\)

Speeding Up Processing

四个维度

数据结构

  • inverted index
  • trie
  • B-tree

计算

  • distributed computing
  • MapReduce
  • GPU

磁盘

  • compression
  • deduplication

带宽

  • CDN
  • caching
  • parallel fetching

Searching

两种类型

Database Search

  • structured
  • exact
  • SQL

Web Search

  • unstructured
  • natural language
  • ranked

MapReduce

前半部分讲AI从retrieval走向generation，本质是从“查已有内容”变成“按需生成内容”，例如音乐机器人可以实时根据输入生成和声，体现出生成式AI的个性化和实时性，同时引入synthetic data概念，即用符合真实分布的“假数据”训练模型来解决数据枯竭问题，并指出AI生态已经变成调用模型和API的工程问题而不是从零训练；同时老师批判性地讨论了现实影响，包括内容创作者被挤压、公司强制使用AI导致技术债、以及AI与权力和政治的关系。

MapReduce 是 Google 在 2004 年提出的并行处理算法，公开版本叫 Hadoop。两者在概念上做的是同一件事：大规模并行处理数据。

MapReduce 不只是两个步骤，完整流程更接近：

Map → Combine → Shuffle → Reduce

其中 Combine 有时可选，但 Shuffle 是核心步骤。

MapReduce、GFS、Bigtable 三件套

Google 早期的大规模基础设施由三部分组成：

GFS：Google File System 一个分布式文件系统，把数据分散存储在很多机器上，但对工程师来说像一个统一文件系统。

MapReduce 大规模并行计算框架，让工程师写 map 和 reduce 函数，系统自动把任务分发到很多机器上执行。

Bigtable Google 的大规模分布式数据库，用来存储搜索索引、Google Docs、YouTube、新闻缓存等数据。 Bigtable 不只是二维表，还可以有时间维度，用于保存不同时间版本的数据。

为什么 MapReduce 重要：Google 搜索变快

早期 Google 搜索一度变慢，因为网页规模越来越大，传统方式无法快速处理。MapReduce 和 GFS 让 Google 可以把巨大索引拆到大量机器上并行处理，从而让搜索重新变得很快。

搜索 “Anthropic” 的例子说明：用户感觉是一瞬间得到结果，但背后可能是海量服务器同时搜索、排序、聚合结果。

并行计算：SIMD vs MIMD

两类并行：

​ SIMD：Single Instruction, Multiple Data 同一个操作应用到很多数据上，比如对一张图像的不同区域做同样处理，或对很多温度数据求和。MapReduce 更接近这种思想，比较容易自动并行化。

​ MIMD：Multiple Instruction, Multiple Data 不同任务、不同操作之间存在依赖关系，比如图像处理 pipeline、神经网络计算图、自动驾驶系统等。 TensorFlow 的计算图：某些节点可以并行，某些必须等待前置结果。

MapReduce 的直觉例子：全球温度求平均

10 亿条温度记录求平均：

传统做法：一台机器循环累加 10 亿个数，再除以 10 亿，可能很慢。

MapReduce 做法：

  1. 把 10 亿条数据切成很多片，比如 10 片、100 片、1000 片；
  2. 每台机器对自己的片段求局部和，这是 Map；
  3. 把局部结果发送到 reducer；
  4. reducer 把这些局部和加起来，再求平均。

机器越多，速度越快。老师强调这就是 MapReduce 的巨大价值：通过横向扩展机器数，获得数量级的加速。

MapReduce 的编程来源：函数式编程

MapReduce 名字来自函数式编程里的 map 和 reduce。

比如 Python 中：

  • map(function, data)：把一个函数应用到列表中每个元素；
  • reduce(function, data)：把一组值合并成一个值，比如求和。

他举了摄氏度转华氏度的例子，也讲到 lambda 匿名函数、高阶函数、Lisp、Scheme、JavaScript、Haskell 等函数式编程背景。

Yarn 与容错

MapReduce 初期版本的容错能力不完善。如果某台机器失败，系统可能一直等它返回结果。

后来 Hadoop 生态中出现 YARN: Yet Another Resource Negotiator，相当于 MapReduce 2.0，负责资源管理、任务调度、失败重试等。这样系统能自动发现某个节点失败，并把任务重新分配到其他机器。

Knowledge Graphs

Graph：最通用的数据结构

图由节点和边组成。

1
node -- edge -- node

图非常通用，因为它可以表示很多结构：

  • array；
  • tree；
  • database schema；
  • social network；
  • web pages；
  • recommendation system；
  • playlists；
  • movie database；
  • dependency graph；
  • dataflow graph；
  • knowledge graph。

例如：

IMDb 可以看成图：

1
2
3
Movie → directed by → Director
Movie → acted in by → Actor
Actor → married to → Actor

Wikipedia 也可以看成图：

1
Page → links to → Page

Spotify playlist 也可以看成图：

1
2
3
User → listens to → Song
Song → appears in → Playlist
Playlist → created by → User

推荐系统也可以看成图：

1
2
User → bought → Product
Product → frequently bought with → Product

图数据库 Graph Database

普通关系型数据库用表存储数据。 图数据库直接用节点和边存储数据。

典型例子是 Neo4j。

图数据库适合表示关系复杂的数据，例如：

  • 社交网络；
  • 推荐系统；
  • 金融交易；
  • 欺诈检测；
  • 供应链；
  • 电影人物关系；
  • 知识网络；
  • 路径查询。

但注意：图数据库不一定是知识图谱。

图数据库只是存图； 知识图谱要求图里的节点和边具有明确语义。

Knowledge Graph 知识图谱

知识图谱是一种特殊的图。

它不仅有节点和边，还要表达 meaning 语义 / knowledge 知识。

普通图：

1
A -- connected to -- B

知识图谱：

1
2
3
Elvis Presley -- born in -- Tupelo, Mississippi
Tupelo -- located in -- Mississippi
Mississippi -- part of -- United States

知识图谱的节点通常是实体：

  • 人；
  • 地点；
  • 作品；
  • 公司；
  • 概念；
  • 事件；
  • 学科

边表示有意义的关系：

  • born in；
  • located in；
  • created by；
  • part of；
  • caused by

知识图谱的目标是让机器不仅“存储数据”，而且能理解实体之间的语义关系。

Knowledge Graph 为什么重要

知识图谱比纯机器学习更“干净”的地方在于：

每个节点和每条边都可以由人类专家确认。 因此它可以非常高质量。

机器学习依赖大量训练数据，数据可能有：

  • 偏差；
  • 缺失；
  • 错误；
  • 噪声；
  • 幻觉；
  • 不可解释性。

知识图谱则可以更精确：

1
2
3
Picasso -- painted -- Guernica
Guernica -- style -- Cubism
Cubism -- art movement -- Modern Art

这些关系可以被验证。

问题是： 人工构建知识图谱很慢，难以扩展。 现在 LLM 可以快速从文本中抽取实体和关系，但也可能 hallucinate，所以需要人工审核或验证机制。

Taxonomy 分类法

Taxonomy 指分类体系。

它的核心是：把世界上的东西分门别类。

例子：

1
2
3
4
5
6
7
Vehicle
├── Car
│   ├── Sedan
│   ├── SUV
│   └── Sports Car
├── Truck
└── Motorcycle

周期表也是一种 taxonomy，因为它把化学元素按性质分类。

Taxonomy 的价值是帮助人理解世界。 科学本质上经常依赖分类：先知道有哪些类别，再研究类别之间的规律。

Ontology 本体论

Ontology 比 taxonomy 更强。

Taxonomy 主要是分类；Ontology 不仅有分类，还定义实体、属性、关系和规则。

例如：

1
2
3
4
5
Car is a Vehicle
ElectricCar is a Car
TeslaModel3 is an ElectricCar
Car has part Wheel
Person owns Car

Ontology 关注的是：

  • 什么东西存在；
  • 它们属于什么类别；
  • 它们有什么属性；
  • 它们之间有什么关系；
  • 哪些规则可以推理出新知识。

可以理解为： ontology = 带语义和规则的知识结构。

Knowledge Base 与 Rule

知识图谱可以和规则系统结合，形成 knowledge base。

规则通常是：

1
IF condition THEN conclusion

例如：

1
2
IF many people carry umbrellas
THEN it is probably raining

或者：

1
2
3
IF X is a dog
AND dog is a mammal
THEN X is a mammal

这些规则可以被 inference engine 推理引擎 使用。

推理引擎会根据已有事实和规则推出新事实。

例如已有：

1
2
Snoopy is a dog
Dog is a mammal

推出：

1
Snoopy is a mammal

这就是知识图谱和传统 AI / expert system 的联系。

Syntax vs Semantics

这节课强调一个重要区别：

Syntax 语法 / 结构

只看形式和结构，不真正理解含义。

例如传统关键词搜索：

1
chemistry

系统只是匹配包含这个词的文档。

Semantics 语义

理解词、实体、关系背后的含义。

例如知识图谱知道：

1
2
3
Chemistry -- studies -- Matter
Organic Chemistry -- subclass of -- Chemistry
Benzene -- compound in -- Organic Chemistry

这比单纯关键词匹配更接近“理解”。

Embedding 也能捕捉一定语义，因为相似含义的词会在向量空间中靠近。 但 embedding 本身仍然是向量，不是显式知识。知识图谱则把语义关系明确写出来。

RAG、Graph RAG 与 Knowledge Graph

传统 RAG 通常是：

  1. 文档切 chunk；
  2. chunk 转 embedding；
  3. 用户问题转 embedding；
  4. 找相似 chunk；
  5. 把 chunk 放进 prompt；
  6. LLM 生成答案。

这叫 Vector RAG。

但 Vector RAG 有局限：

  • 只靠相似度；
  • 不一定理解实体关系；
  • 跨文档推理弱；
  • 容易漏掉结构信息；
  • 对复杂关系问题不够好。

因此出现 Graph RAG。

Graph RAG 会使用知识图谱作为检索结构：

1
Question → entity extraction → graph traversal → retrieve related facts → LLM answer

例如问：

1
Impressionist art in Europe 有哪些重要人物和作品？

系统可以在艺术知识图谱里找到：

1
2
3
4
5
6
7
Impressionism
→ painters
→ artworks
→ countries
→ periods
→ influences
→ related movements

然后再生成答案。

Graph RAG 的优势是能利用显式关系，而不只是向量相似度。

Hybrid RAG

现代 RAG 不一定只用一种检索方式，可以混合：

  • vector search；
  • graph search；
  • BM25；
  • TF-IDF；
  • SQL query；
  • HTML parsing；
  • metadata filtering；
  • knowledge graph traversal。

这叫 hybrid RAG。

原因是：不同数据结构适合回答不同问题。

例如：

问题类型 更适合的方法
找语义相近文本 Vector search
找关键词精确匹配 BM25 / TF-IDF
查结构化数据 SQL
查实体关系 Knowledge Graph
查网页结构 HTML parsing
复杂问答 Hybrid RAG

所以未来的 RAG 更像一个多工具系统，而不是单纯 embedding search。

Snippets

Snippet 指搜索引擎结果页中，标题和链接下面显示的一小段内容。

它的作用是帮助用户判断：

  • 这个页面是不是我想要的？
  • 它是否回答我的问题？
  • 我要不要点击进去？

传统 snippet 通常来自网页正文中和查询词相关的一段文字，但现代 snippet 可以更丰富。

Snippet 会随着查询变化

同一个网页，面对不同搜索 query，Google 可能给出不同的 snippet。 比如某个 Cleveland Clinic 页面，用户搜 “what cholesterol levels mean” 时，Google 展示的是一段 FAQ/说明式内容；但搜另一个相关问题时，展示的 snippet 可能完全不同。

这说明 snippet 不是固定写死的，而是 query-time 生成 的：搜索时根据用户查询、网页内容、页面结构等动态决定展示哪一段。

Snippet 本质上是自动摘要问题

snippet 被归到 automatic summarization 自动摘要。传统摘要有两类：

Extractive summary：从原文里挑句子或片段出来组成摘要。 Abstractive summary：重新生成一句新的摘要，不一定完全来自原文。

搜索引擎 snippet 更接近 extractive summary，因为它通常从网页中抽取包含 query 关键词、上下文合适的文本片段。

Featured Snippet 是 Google 为了在搜索结果页直接回答问题而设计的特殊摘要，通常出现在普通结果上方。它一般来自排名靠前的页面，并用简洁格式回答 query。如果网页想更容易成为 Featured Snippet，可以做一些页面优化，例如：用清晰的问题标题、紧接着给出简洁答案、使用 1–2 句话定义、用表格或列表组织信息、避免过度第一人称表达。

PAA 是 Google 搜索结果中的 “People Also Ask” 模块。 它会列出与当前查询相关的问题，点开后展示简短答案，并可能继续扩展出更多问题。 PAA 增长很快，而且它和 Featured Snippet 类似，也是直接在搜索结果页回答用户问题的一种机制。

Rich Snippets 是普通 snippet 的增强版。网页开发者可以在页面中嵌入 structured data（结构化数据），让 Google 更容易识别页面里的实体和属性，从而在搜索结果中展示评分、价格、地址、营业时间、事件时间、人物信息等。例如餐厅结果可能显示地址、评分、营业时间；电影页面可能显示导演、演员、评分、简介等。

结构化数据技术

技术 作用
schema.org 定义实体和属性词汇，比如 Movie、Person、Event、Review
Microdata 在 HTML 标签中加 itemscope、itemtype、itemprop
RDFa / Microformats 其他结构化标记方式
JSON-LD 现在很常见的结构化数据格式

PageRank

PageRank：Google 早期用来衡量网页“重要性”的链接分析算法。它的核心问题可以概括成一句话：谁链接了你？链接你的人本身有多重要？

搜索引擎不只是要找到相关网页，还要决定：哪个结果排第一？哪个排第二？哪个排第三？

1. 从论文引用到网页链接

PPT 一开始先讲 bibliometrics（文献计量学），也就是通过论文之间的引用关系来衡量论文、作者、期刊的影响力。

比如：

  • 一篇论文被很多论文引用，通常说明它有影响力。
  • 两篇论文如果引用了很多相同文献，说明它们主题可能相近，这叫 bibliographic coupling。
  • 一个期刊的论文平均被引用次数高，就可能有较高的 impact factor。

PageRank 的思想和这个很像： 网页之间的链接可以看作某种“投票”或“引用”。

但 PPT 也提醒：网页链接不完全等于学术引用。论文引用通常比较正式、有同行评审背景；网页链接可能只是导航、广告、门户页入口，甚至不一定代表认可。

2. PageRank 的直觉

PageRank 的基本想法是：

一个网页重要，不只是因为很多网页链接到它，还因为链接到它的网页本身也重要。

也就是说：

  • 普通网页给你一个链接，有价值；
  • 权威网页给你一个链接，更有价值；
  • 如果一个网页链接出去很多个页面，它给每个页面分到的“投票权”就会变少。

所以 PageRank 不是简单数入链数量，而是看 链接质量 + 链接来源的权重分配。

3. 简化版 PageRank 公式

PPT 给出的初始公式是：

1
PR(u) = Σ PR(v) / |out(v)|

意思是：

  • PR(u)：页面 u 的 PageRank；
  • in(u)：所有指向 u 的页面集合；
  • PR(v)：某个指向 u 的页面 v 的 PageRank；
  • out(v)：页面 v 链出去的总数。

通俗说就是：

页面 u 的分数 = 所有指向 u 的页面，把自己的分数平均分给外链后，u 收到的总和。

比如某个页面 v 有 4 个外链，那么它只会把自己 PageRank 的 1/4 传给每个被链接页面。

4. 迭代计算

PageRank 不是一次算出来的，而是反复迭代。

PPT 的简化算法步骤是：

  1. 初始时，每个网页分配相同 PageRank，比如总共有 5 个网页，每个网页初始是 1/5。
  2. 下一轮，每个网页把自己的 PageRank 平均分给它链接出去的页面。
  3. 每个页面把收到的分数加起来，得到新 PageRank。
  4. 重复很多轮，直到数值稳定。

这就是为什么 PageRank 可以处理整个 Web 这种巨大图结构：它不需要一次性“直接求解”，而是通过不断更新逐步收敛。

5. 为什么需要完整公式：damping factor

简化版有问题。比如有些网页没有外链，或者一些网页形成小循环，PageRank 可能会卡在某些页面里。

所以完整 PageRank 加入了 damping factor（阻尼因子），通常记作 d，经典值是 0.85。

完整思想是：

1
PR(A) = (1 - d) + d * Σ PR(Ti) / C(Ti)

这里：

  • d 通常是 0.85；
  • (1 - d) 表示即使没人链接你，你也有一点基础分；
  • 后半部分表示从其他链接页面传来的分数；
  • C(Ti) 是页面 Ti 的外链数量。

这个公式背后的直觉是 random surfer model（随机冲浪者模型）：

一个用户在网页间随机点击链接，但有一定概率会不再沿着链接走，而是随机跳到其他页面。 d = 0.85 就表示大约 85% 的时候继续点链接，15% 的时候随机跳转。

6. 收敛问题

PPT 专门讲了 PageRank 的收敛。

关键点是：

  • 迭代次数不会随着网页数量简单线性增加；
  • 实验中，即使有上亿链接，也可以在几十轮左右收敛；
  • damping factor 太高，收敛会慢；
  • damping factor 太低，PageRank 区分度会变弱；
  • 没有 damping factor 时，一些图结构可能导致数值卡住或震荡。

所以 damping factor 的作用不仅是模拟用户行为，也让算法更稳定。

7. 链接结构如何影响 PageRank

不同网站结构会让 PageRank 分布不同。

几个重要结论：

首页通常 PageRank 高。 如果网站是层级结构，很多页面指回首页，首页会集中获得较高 PageRank。

外部链接很重要。 如果外部网站链接到你的网站，尤其链接到首页，你的网站整体 PageRank 会提高。

内部链接会重新分配 PageRank。 站内页面之间如何互相链接，会影响 PageRank 在网站内部的流动。

链接出去会分走 PageRank。 如果页面有很多外链，它会把自己的 PageRank 分散出去。PPT 里提到，增加内部链接可以减少 PageRank 完全流向外部站点。

完全互链不一定更好。 如果所有页面都互相链接，PageRank 可能会变得平均，无法突出重要页面。

人为制造 link farm 是错误方式。 PPT 后面举例说，建立大量垃圾页面只为了给目标页面增加链接，虽然可能暂时提高某页 PageRank，但搜索引擎会把这种结构视为 spam。

8. 提高 PageRank 的建议

  • 增加真正有价值的外部入链。
  • 如果必须链接到外部网站，要意识到 PageRank 会被分出去。
  • 网站内部结构要清晰，不要让所有页面随便乱连。
  • 对重要页面，可以通过站内链接让更多 PageRank 流向它。
  • 使用 sitemap，帮助搜索引擎发现更多页面。
  • 不要用 link farm 或垃圾链接作弊。

9. PageRank 不是 Google 排名的全部

PageRank 只是 Google 搜索排名的众多信号之一。

它衡量的是链接层面的“重要性”，但搜索排名还要考虑：

  • 页面内容是否和查询相关；
  • anchor text；
  • 页面质量；
  • 用户体验；
  • 搜索意图；
  • 反作弊机制；
  • 其他大量 ranking signals。

所以不能简单理解为：PageRank 高，搜索排名就一定高。 更准确地说，PageRank 是 Google 早期搜索成功的关键技术之一，但现代搜索排名已经远比单一 PageRank 复杂。

总结

PageRank 把网页链接看成投票，但不是所有票都一样重要；来自重要网页的链接更值钱，而一个网页的投票权会被它的外链数量分摊。通过不断迭代，算法最终得到每个网页的相对重要性。

Query Processing

1. 搜索引擎收到 query 后要做什么

PPT 开头把搜索引擎的任务分成两步：

第一步是 快速找到包含查询词的候选文档。 这主要依赖倒排索引，也就是通过 query terms 找到对应 posting lists。

第二步是 判断用户真正想要什么，并给出尽可能准确的结果。 用户输入的 query 往往很短、很模糊，比如 “jaguar” 可能是动物、汽车品牌，也可能是球队，所以现代搜索不能只做关键词匹配。

这份 PPT 前半部分讲 如何加速倒排索引检索和 top-k 排名，后半部分讲 Google 查询处理如何从关键词匹配发展到语义理解。

2. 加速检索：不要一开始就算所有文档

理论上，只要文档包含 query 中任意一个词，它都可以成为候选文档。但现实中网页数量太大，如果每个候选文档都算完整 cosine score，成本太高。

所以课件介绍了一系列 heuristic，也就是工程上的加速策略。

3. 策略一：只优先考虑高 idf 的词

比如 query 是：catcher in the rye

其中 catcher 和 rye 比较有区分度，而 in、the 太常见。 PPT 的策略是：只先累计高 idf 词的 cosine score。

直觉是： 常见词的 posting list 很长，处理成本高，但对排名贡献很小；高 idf 词更能区分文档，所以优先处理它们更划算。

4. 策略二：多词查询时只考虑包含多个 query terms 的文档

对于多词 query，理论上包含一个 query term 的文档都可以入选。但实际中，可以只对包含多个 query terms 的文档计算分数。

例如 4 个 query terms 中，要求文档至少包含 3 个。这相当于对 query 加了一个 soft conjunction（软 AND）：不是必须包含所有词，但至少要包含大部分关键词。

这样能明显减少候选文档数量。

5. 策略三：Champion Lists

champion list，也叫 fancy list 或 top docs list。做法是：

对词典中的每个 term，提前保存该 term 对应 posting list 中 tf-idf 分数最高的 r 个文档。

查询时，不扫描完整 posting list，而是优先只看 query terms 的 champion lists，然后从这些文档中选 top-k。

它的核心思想是：提前把每个词最有代表性的文档存起来，查询时少算很多低可能性的文档。

缺点是 r 要在建索引时决定。如果 r 太小，可能漏掉好结果；如果太大，节省不明显。

6. 策略四：引入 Authority Measure

前面的方法主要考虑 relevance，也就是文档和 query 的相关性。但搜索结果还应该考虑 authority，也就是文档本身的权威性或质量。

PPT 里把每个文档赋予一个 query-independent quality score：g(d)

它和具体 query 无关，表示文档本身的“好坏”。

authority signals 可以包括：

  • Wikipedia 这类权威网站；
  • 高 PageRank 页面；
  • 被精心编辑的内容；
  • 有大量好评的文档；
  • 高质量新闻文章；
  • 被大量引用的论文或网页。

7. 相关性和权威性合并

PPT 给了一个简单的组合公式：net-score(q, d) = g(d) + cosine(q, d)

也就是说，一个文档最终得分由两部分组成：

最终分数 = 文档权威性 + 与 query 的相关性

其中 cosine score 衡量 relevance，g(d) 衡量 authority。

实际搜索引擎可能会用更复杂的线性组合或机器学习排序模型，但这个公式表达了基本思想： 搜索结果不能只相关，还要可信、有质量。

8. 策略五：按 authority 重排倒排列表

传统倒排索引的 posting list 通常按 docID 排序，这样方便合并列表。 但 PPT 提出一种优化：把 posting list 按 g(d)，也就是 authority score 排序。

这样最权威的文档会排在 posting list 前面。 查询时可以更早看到高质量候选文档，更快找到 top-k。

这不会改变 posting list 合并的基本逻辑，但可以让系统更早集中处理高价值文档。

9. 策略六：High / Low Lists

还有一种方法是： 对每个 term 维护两个 posting lists：

  • high list：高质量或高分文档；
  • low list：其他文档。

查询时先遍历 high lists。 如果已经找到超过 K 个好结果，就直接选 top K 并停止；如果不够，再去 low lists 里补。

这也是一种分层检索思想： 先查最可能进入前几名的文档，没必要一开始扫描全部。

10. 从关键词匹配到现代 Query Processing

后半部分讲 Google 查询处理的演进。

早期搜索主要流程是：

  1. parse query；
  2. 把词转成 wordID；
  3. 找到包含这些 wordID 的 barrels / posting lists；
  4. 扫描文档列表；
  5. 用 PageRank 和文本相关性计算排名；
  6. 返回 top-k。

但现代搜索已经不只是 keyword matching，而是包含更多语义处理：

  • 理解 query 的主题和意图；
  • 识别 query 中的实体；
  • 判断 query 是导航型、信息型、交易型还是本地搜索；
  • 结合用户位置、设备、历史行为；
  • 生成 SERP features，比如知识图谱、图片、People Also Ask、featured snippets 等。

11. Term-based vs Entity-based Meaning

PPT 用 “red stoplight” 和 “stoplight red” 的例子说明：

如果只是 term-based search，系统可能把 red 和 stoplight 当成两个独立词。 但 entity-based search 会理解： “red stoplight” 指的是一个具体概念或实体，而不是两个词的简单组合。

这就是现代搜索和传统倒排索引的区别：它不只是匹配词，还要理解词组合起来的意义。

12. Knowledge Graph 的作用

Google Knowledge Graph 用来识别和存储实体及其关系。

比如 query：

1
ceo vw

Google 不只是匹配 ceo 和 vw 两个词，而是识别：

  • vw 是 Volkswagen；
  • ceo 是一种角色/关系；
  • 用户想找 Volkswagen 的 CEO。

另一个例子是：

1
founder adidas

系统会识别 Adidas 和 founder 之间的实体关系，然后返回 Adolf Dassler。

所以 Knowledge Graph 让搜索引擎从“字符串匹配”转向“实体和关系理解”。

13. RankBrain

PPT 最后讲 RankBrain，它是 Google 用于查询理解的机器学习系统，尤其擅长处理以前没见过的新 query。

它的作用包括：

  • 把关键词映射到概念；
  • 根据上下文理解实体；
  • 处理长尾 query 或新 query；
  • 学习词与词、实体与实体之间的关系；
  • 结合用户交互信号判断结果是否有用。

PPT 里还提到 RankBrain 会利用 UX signals，例如：

  • 用户是否点击某个结果；
  • dwell time，也就是用户点进去后停留多久；
  • bounce rate；
  • pogo-sticking，也就是用户点进去马上返回搜索结果再点别的结果。

这些信号可以帮助系统判断结果是否真的满足用户需求。

总结

查询处理不是简单地“找包含关键词的网页”。搜索引擎要先用倒排索引和各种 heuristic 快速缩小候选集，再结合相关性、权威性、PageRank、实体识别、Knowledge Graph、RankBrain 和用户反馈来生成最终搜索结果。

Question Answering

1. IR 和 QA 的区别

传统 Information Retrieval（信息检索） 的目标是：用户输入 query，系统返回相关文档。

但 Question Answering（问答） 的目标更进一步：用户用自然语言提出问题，系统直接给出答案。

比如用户问：Who was the prime minister of Australia during the Great Depression?

传统搜索可能返回一堆网页；QA 系统希望直接回答：James Scullin

PPT 强调，现代搜索已经不只是 document retrieval，而是逐渐转向 answer search：结合信息检索、知识图谱、自然语言处理、查询历史、位置、用户行为等信息，直接生成或抽取答案。

2. 为什么 QA 很重要

PPT 举了 Ask.com query log 的例子，里面有大量自然语言问题，例如：

1
2
3
4
5
6
how much should I weigh
what does my name mean
how to get pregnant
where can I find pictures of hairstyles
who is the richest man in the world
what is true love

大约 10–20% 的 query log 都是这种问题形式。这说明用户并不总是输入关键词，而是经常直接问完整问题。

所以搜索引擎必须能理解：

  • 问题在问什么；
  • 答案类型是什么；
  • 哪些网页或知识库可能包含答案；
  • 如何从候选文本中抽取最可信答案。

3. 有些问题很容易，有些很难

有些问题很容易回答，比如：how tall is mount everest

Google 可以直接显示高度，因为这是明确的事实型问题，答案存在于知识库或高可信来源中。

但有些问题很难，比如：Who is Michael Jordan?

这个问题有歧义。Michael Jordan 可能是篮球运动员，也可能是机器学习领域的学者。QA 系统必须做 entity disambiguation（实体消歧）。

还有些问题需要推理，例如：What is the distance between the largest city in California and the largest city in Nevada?

系统不能只查一句话答案。它需要先知道：

  • California 最大城市是 Los Angeles；
  • Nevada 最大城市是 Las Vegas；
  • 再计算两者距离。

这属于多步推理。

还有些问题甚至没有可用数据，比如某年欧洲大学授予多少数学 PhD。这种情况下系统可能找不到答案，或者结果不可靠。

4. 早期 Google QA 方法

Google 早期处理问答的方式比较简单：

  1. 把问题当成字符串去网页里搜索；
  2. 如果某个网页里出现了完全相同或很相似的问题，比如 FAQ 页面；
  3. 返回该网页中紧跟问题后面的句子作为答案。

这种方法在 FAQ 场景下很好用，但缺点是明显的： 如果问题没有以原句形式出现在网页里，系统就很难回答。

后来系统变复杂，开始结合：

  • Knowledge Graph；
  • N-grams；
  • WordNet；
  • NLP techniques。

5. 为什么需要 NLP

PPT 用一个例子说明只靠关键词会出错：

问题：When was Wendy's founded?

候选段落中可能出现：Wendy's Moonan ...

系统如果只看到 Wendy's 和 founded，可能误以为答案是 “20th century”。但这里的 Wendy’s 是人名，不是快餐品牌 Wendy’s。

所以 QA 必须理解：

  • 实体是什么；
  • 词之间是什么关系；
  • 问题中的 predicate 和 argument 是什么；
  • 候选答案是否真的回答了问题。

另一个例子是：When was Microsoft established?

正确答案可能来自不完全包含 query term 的句子：

1
Microsoft Corp was founded in the US in 1975, incorporated in 1981, and established in the UK in 1982.

系统要区分 founded、incorporated、established 这些词的语义关系，并判断问题具体问的是哪种 established。

6. 四类常见 QA 产品思路

PPT 总结了几种问答系统路线：

Siri 类方法： 把问题映射到已知实体和结构化数据库，比如天气、地图、餐厅、日历、联系人。

Ask.com 类方法： 判断问题类型，然后利用搜索引擎 snippet 找答案。

IBM Watson 类方法： 结合结构化数据库、非结构化文本、候选答案评分等多种方法。

Google Knowledge Graph 类方法： 使用实体—关系图谱，基于图中的实体和关系直接推理答案。

7. Siri 的知识驱动方法

Siri 的流程大致是：

  1. 语音识别，把用户语音转文字；
  2. 语言模型理解用户意图；
  3. 抽取 query 中的实体，例如日期、地点、人物、餐厅、时间；
  4. 把语义结构映射到具体资源，比如 Yelp、OpenTable、Wolfram Alpha、Google、Bing；
  5. 得到答案后转成自然语言，再用语音读出来。

PPT 还强调了上下文的重要性：

用户说：Book a table at Il Fornaio at 7:00 with my mom.

之后又说：Also send her an email reminder.

系统要知道：

  • her 指的是 my mom；
  • 7:00 多半是晚上 7 点；
  • Il Fornaio 是餐厅；
  • 这是一个订餐任务，不只是普通搜索。

8. IBM Watson 的候选答案评分

Watson 的核心不是只找一个答案，而是生成很多 candidate answers，然后给每个候选答案打分。

评分可以来自几十个特征，例如：

  • 逻辑匹配；
  • 文本中的证据；
  • 地理关系；
  • 时间关系；
  • 实体类型是否匹配；
  • 外部知识库支持；
  • 分类关系。

比如问题问 “15th hotel in Japan”，候选答案必须是 hotel，并且地点要在 Japan。如果问题问某人的出生时间，候选答案应该是 date，而不是 person。

9. QA 系统的三阶段架构

PPT 把 QA 系统分成三个主要阶段：

第一阶段：Question Processing

系统要理解问题：

  • 判断问题类型：who、what、when、where、how many；
  • 识别重要实体；
  • 判断答案类型；
  • 生成适合发给搜索引擎的 query。

例如：

问题词 可能答案类型
Who Person / Organization
When Date / Year
Where Location
How many Number

第二阶段：Passage Retrieval

系统不是直接搜索整篇文档，而是找可能包含答案的 passage，也就是短文本片段。

它会：

  • 把问题转换成多个 query；
  • 用搜索引擎召回 snippet 或文档；
  • 按答案类型过滤；
  • 根据关键词重叠、实体匹配、n-gram overlap 等特征排序 passage。

第三阶段：Answer Processing

系统从 passage 中抽取候选答案，并排序。

比如问题问 “Who”，系统会优先找人名或组织名；问题问 “When”，系统会优先找日期或年份；问题问 “How many”，系统会找数字表达。

最后根据文本证据、类型匹配、外部知识库等信息选出最佳答案。

10. 问题分类和答案类型

PPT 中有一个 question taxonomy，说明问题可以细分得非常多。

例如：

  • Location → country、city、province、continent；
  • Number → speed、degree、dimension、rate、duration、percentage、count；
  • Human → individual、group；
  • Organization；
  • Product；
  • Currency；
  • Language；
  • Animal；
  • Game。

分类越细，系统越容易判断“应该找什么类型的答案”。 例如问：What 20th century poet wrote Howl?

系统应该找的是一个 poet/person，而不是任意名词。

11. QA 需要的 NLP 能力

PPT 总结了一些 QA 系统常用 NLP 技术：

  • POS tagging：识别名词、动词、形容词等词性；
  • Named Entity Recognition：识别人名、地点、组织、时间、金额等实体；
  • Semantic relations：识别实体之间的语义关系；
  • WordNet / dictionaries / thesauri：用于同义词、上下位词、语义扩展；
  • Coreference resolution：判断代词指向谁；
  • Information extraction：从句子中抽取实体和关系，构建知识图谱。

例如 “John was born in Liverpool, to Julia and Alfred Lennon.”

系统可以抽取出：

1
2
3
John Lennon — birthplace → Liverpool
John Lennon — childOf → Julia Lennon
John Lennon — childOf → Alfred Lennon

这就是从自然语言构建知识图谱的过程。

12. Keyword Expansion

为了提高召回率，系统会扩展关键词。

PPT 提到三类扩展：

Morphological variants：词形变化 例如 invented → inventor → inventions

Lexical variants：近义词 例如 killer → assassin，far → distance

Semantic variants：语义相关词 例如 like → prefer

这样可以避免因为表达方式不同而漏掉答案。

13. BERT 在 QA 中的作用 BERT 是 Bidirectional Encoder Representations from Transformers，由 Google 在 2018 年开源，后来被用于 Google 搜索中理解更复杂的自然语言。

BERT 的特点是 双向理解上下文。它不是只从左到右读句子，而是同时利用词前后的上下文判断含义。

例如：

1
The man went to the bank to deposit money.

和

1
The man sat on the river bank.

两个 bank 意思不同，BERT 可以利用上下文区分。

在 QA 中，BERT 可以把问题和段落一起输入，然后预测段落中哪一段文本最可能是答案。 PPT 例子中：

Input Question:

1
Where do water droplets collide with ice crystals to form precipitation?

Input Paragraph 中包含：

1
... within a cloud ...

BERT 输出答案：

1
within a cloud

这说明现代 QA 不只是靠规则和关键词，而是可以直接学习“问题—段落—答案 span”之间的关系。

总结

Question Answering 是从“找文档”到“直接找答案”的升级。它需要先理解问题类型和实体，再检索可能包含答案的 passage，最后用 NLP、知识图谱、候选答案评分或 BERT 等模型抽取并排序答案。

Autocorrect, auto Complete

1. 为什么搜索引擎需要自动纠错

Google / Bing 的例子：用户输入拼错的词时，搜索引擎会自动提示或直接改成更可能的查询。

拼写错误非常常见，尤其在手机输入中更明显。不同研究给出的拼写错误率不同，例如网页 query、无退格重输、手机输入等场景下都存在明显错误率。因此，对于搜索引擎来说，纠错不是附加功能，而是信息检索体验的重要组成部分。

2. 常见拼写错误原因

PPT 把 misspelling 的原因分成几类：

原因 错误例子 正确形式
typing quickly exxit exit
keyboard adjacency impotant important
inconsistent rules concieve conceive
ambiguous word breaking silver light silverlight
new words kinnect kinect

这里有个重要点：有些“错误”不是传统意义上的拼错，而是新词、品牌名、合成词、空格切分错误，系统必须结合上下文和用户行为判断。

3. 两个核心任务：检测错误 + 生成纠正

第一是 Spelling Error Detection：判断一个词是不是错了。 最简单方法是查词典：不在词典里，就可能是错误。但这不总可靠，因为新词、人名、品牌名可能也不在词典里。

第二是 Spelling Error Correction：如果错了，找出正确词。 这一步更难，因为系统要从很多候选词里选最可能的那个。

通常会结合两类信息：

  1. Edit distance（编辑距离）：候选词和错误词有多接近。
  2. N-gram / probability（语言概率）：候选词在真实文本或查询日志中有多常见。

4. 三类拼写错误

Non-word errors：拼出来的词根本不是合法词。 例如：

1
graf → giraffe

这种相对容易，因为词典能发现 graf 不存在。

Typographical errors：打字错误，但结果可能仍是合法词。 例如：

1
three → there

这更难，因为 there 本身也是合法词。

Cognitive errors：认知或同音词错误。 例如：

1
2
3
piece → peace
too → two
your → you're

这种必须靠上下文判断，单看词本身无法确定。

5. Non-word 错误怎么纠正

对 non-word error，基本流程是：

  1. 发现该词不在 dictionary 里；
  2. 从 dictionary 中找出和它“很像”的候选词；
  3. 用 edit distance 衡量相似度；
  4. 再用概率模型选择最可能的候选。

例如用户输入 acress，系统可以找到多个编辑距离为 1 的候选词：

1
2
3
4
5
6
actress
cress
caress
access
across
acres

然后根据频率或上下文判断哪个最可能。

6. 为什么上下文很重要

有些错误必须结合上下文。例如：

1
flew form Heathrow to LAX

这里 form 是合法词，但在上下文中应该是：

1
flew from Heathrow to LAX

再比如：

1
Power cord

和

1
Video card

系统要知道 cord 和 card 在不同语境下都可能正确。

还有些词读音相近，比如用户写了一个同音错误，系统需要用类似 Soundex 的算法找发音相近的候选。

7. Noisy Channel Model

Noisy Channel Model（噪声信道模型）的思想是：

用户本来想输入一个正确词，但在输入过程中经过“噪声信道”，发生了插入、删除、替换、转置等错误，最终变成了错误词。

所以纠错任务可以反过来理解：

给定用户输入的错误词，找出最可能的原始正确词。

形式上就是在候选词中选择概率最高的那个：

1
argmax P(correct word | observed typo)

实际中会同时考虑：

  • 这个正确词本身有多常见；
  • 它变成当前错误词的概率有多大；
  • 当前上下文是否支持这个词。

8. 基础拼写纠错算法

基本算法是：

  1. 建一个 dictionary，并能快速检索；
  2. 用户提交 query 后，对每个不在词典里的词查找可能编辑；
  3. 考虑插入、删除、替换、转置等操作；
  4. 大多数错误在 edit distance 1 内，几乎所有错误在 edit distance 2 内；
  5. 对候选词计算概率；
  6. 选概率最高的候选作为纠正。

更精细的版本会先生成所有编辑距离小于等于 K 的字符串，然后和词典取交集，最后按 n-gram 频率或上下文概率排序。

9. Dictionary 和 Trie 的作用

为了快速找到可能纠正，PPT 提到需要一个适合 prefix matching（前缀匹配） 的数据结构，常见的是 trie（前缀树）。

Trie 很适合自动补全：

用户输入一个前缀，比如：

1
comp

系统可以沿着 trie 找到所有以 comp 开头的词，例如：

1
2
3
4
computer
company
compare
complete

然后根据频率、个性化、上下文等因素排序。

这也是 autocomplete 的基础。

10. N-gram 在纠错中的作用

N-gram 是一种概率语言模型，用来估计词序列出现的可能性。 比如系统可以比较：

1
2
3
serve as the independent
serve as the index
serve as the indicater

哪一个短语在大规模语料中更常见，就更可能是正确表达。

N-gram 的优势是简单、可扩展，能在大语料上高效统计。Google 曾发布过大规模 n-gram 数据，包含海量 tokens 和多阶 n-grams。

在拼写纠错里，n-gram 可以帮助判断 上下文中哪个候选词更自然。

11. Edit Distance / Levenshtein Distance

PPT 重点讲了 edit distance（编辑距离），也叫 Levenshtein distance。

它表示把一个字符串变成另一个字符串所需的最少编辑操作数。

常见操作包括：

  • insertion：插入字符；
  • deletion：删除字符；
  • substitution：替换字符。

例如从 sitten 变成 sitting，需要替换和插入等操作。 系统会用动态规划计算最小编辑距离，而不是暴力枚举所有路径。

编辑距离越小，两个词越可能互为拼写错误和纠正候选。

12. Weighted Edit Distance

普通 edit distance 默认每种错误代价一样，但现实不是这样。

PPT 最后讲 weighted edit distance：不同编辑操作应该有不同权重。

例如：

  • 键盘上相邻字母更容易打错；
  • 某些字母组合更常混淆；
  • e 和 i 的错误可能比 q 和 z 更常见；
  • 某些语言里特定拼写规则更容易出错。

所以系统可以用 confusion matrix（混淆矩阵） 统计哪些字符更容易被误打成哪些字符，再给这些错误更低的代价。

这样比普通 edit distance 更贴近真实用户输入行为。

总结

自动纠错/补全不是简单查词典，而是结合词典、编辑距离、上下文、n-gram 概率、用户输入习惯和候选词排序，推断用户最可能想输入什么。

Clustering and classification

1. Clustering 是什么

Clustering（聚类）就是把一堆对象自动分成若干组，让同一组里的对象彼此相似，不同组之间尽量不相似。

在 IR 里，对象通常是文档。比如一批计算机科学文档，系统可能自动聚成：

1
2
3
4
5
NLP
AI
Graphics
Theory
Architecture

聚类属于 unsupervised learning（无监督学习），因为一开始没有人工给定类别标签，系统只根据文档之间的相似度自己找结构。

搜索引擎里的 “related searches”、早期 Yahoo 分类目录、Yippy 搜索结果聚类，都可以看作聚类思想的应用。

2. 好的聚类是什么样

PPT 提到好的聚类要满足两个核心标准：

intra-class similarity 高：同一个 cluster 内部文档相似。 inter-class similarity 低：不同 cluster 之间文档差异大。

此外，一个好的聚类算法还应该：

  • 数据增加时结果不要剧烈变化；
  • 对小的描述错误不敏感；
  • 不依赖输入文档的顺序；
  • 避免产生太大或太小的“无意义 cluster”。

比如如果所有文档都被放到一个大类里，那就没有帮助；如果每篇文档都单独成类，也没太大意义。

3. Clustering 和 Classification 的区别

这份 PPT 反复强调两者区别。

Clustering：先不知道类别。 系统根据相似度自己发现文档之间的结构。

Classification：类别已经定义好。 系统拿到一个新文档，要判断它属于哪个已有类别。

所以：

任务 是否有预定义类别 学习类型
Clustering 没有 无监督学习
Classification 有 监督学习

例如，如果系统已经知道类别是 Algorithms、AI、Databases、Operating Systems，并且有标注好的训练文档，那么给新论文分类就是 classification。

4. 文档如何表示：向量空间

聚类和分类都需要先把文档表示成向量。

常见做法是用词项权重，比如 tf-idf，形成一个高维向量，然后就可以用相似度或距离来比较文档。

PPT 里常见的度量包括：

1
2
3
4
Cosine similarity
Euclidean distance
Manhattan distance / L1 norm
Minkowski distance

在文本处理中，最常用的是 cosine similarity，因为文档长度差异很大，余弦相似度更关注方向，而不是绝对长度。

5. Hard clustering vs Soft clustering

Hard clustering：每个文档只能属于一个 cluster。 这更简单，也更常见。

Soft clustering：一个文档可以属于多个 cluster。 这在实际搜索中很合理。比如一篇关于 Los Angeles 的新闻，可能同时属于：

1
2
3
local news
national news
politics

商品也一样，一双运动鞋可以同时属于 sports apparel 和 shoes。

6. K-means 聚类

它属于 partitioning based algorithm：先指定要分成 K 个 cluster，然后把 N 个点分到 K 类里。

基本流程是：

  1. 随机选择 K 个初始中心点，叫 centroids。
  2. 把每个文档分配给离它最近的 centroid。
  3. 对每个 cluster 重新计算 centroid。
  4. 重复第 2、3 步，直到 centroid 不再变化，或达到最大迭代次数。

centroid 就是 cluster 中所有向量的平均值：

1
centroid = cluster 内所有文档向量的平均

K-means 的特点是：

  • 简单、快；
  • 通常前几轮就会收敛很多；
  • 结果依赖初始 centroid；
  • 必须提前指定 K；
  • 不保证找到全局最优，只是 greedy algorithm。

同一组点可以被分成 2 类、4 类、6 类，说明 K 的选择会极大影响聚类结果。

7. 层次聚类 Hierarchical Clustering

第二类是 hierarchical clustering（层次聚类）。 它不是直接给出一个固定 K，而是生成一个层级结构，常用 dendrogram（树状图） 展示。

主要有两种方法：

Agglomerative clustering，自底向上。 一开始每个文档都是一个 cluster，然后不断合并最相似的两个 cluster，直到只剩一个大 cluster，或剩下 K 个 cluster。

Divisive clustering，自顶向下。 一开始所有文档在一个大 cluster 中，然后不断把 cluster 拆分成更小部分，直到每个文档单独成类，或达到目标 K。

PPT 里更强调 HAC，也就是 hierarchical agglomerative clustering。它适合产生层级浏览结果，比如搜索结果分组、目录结构等。

8. Rocchio Algorithm

Rocchio algorithm最早用于 relevance feedback，也可以用于分类。

Rocchio 的基本思想是：如果我们知道哪些文档 relevant，哪些 non-relevant，就可以计算两个 centroid：

1
2
relevant documents 的中心
non-relevant documents 的中心

然后构造一个更好的查询向量，让它靠近相关文档，远离不相关文档。

简化公式是：

1
q_opt = relevant centroid - non-relevant centroid

更直观地说：

把 query 往相关文档方向拉，把它从不相关文档方向推开。

在分类里，Rocchio 会为每个类别建立 centroid。新文档来了以后，看它离哪个类别 centroid 最近，就分到哪个类别。

它的优点是简单、速度快；缺点是边界通常是线性的，遇到复杂形状的数据时效果有限。

9. Rocchio 的几何解释

PPT 用很多 2D 图说明 Rocchio。

假设圆圈是 relevant documents，叉号是 non-relevant documents：

  1. 先算 relevant 的 centroid。
  2. 再算 non-relevant 的 centroid。
  3. 用两者差向量调整 query。
  4. 得到一个更能区分相关/不相关文档的方向。

PPT 中还强调，Rocchio 的边界不是圆，而通常是 hyperplane（超平面）。 这意味着 Rocchio 更像一个线性分类器。

10. Classification 的问题定义

分类任务可以形式化为：

给定：

1
2
一个实例 x
一组类别 C = {c1, c2, ..., cn}

目标是找到一个函数：

1
c(x) ∈ C

也就是判断 x 属于哪个类别。这个函数就叫 classifier。

在向量空间里，学习分类器等价于学习一些边界，把不同类别的区域分开。

11. K-Nearest Neighbor, KNN

KNN（K-nearest neighbor）：KNN 的想法很直接：

给定一个新文档 d：

  1. 在训练集中找到离它最近的 K 个已标注文档；
  2. 看这 K 个邻居中哪个类别出现最多；
  3. 把 d 分到这个多数类别。

比如 K=6 时，如果 5 个邻居是 red 类，1 个是 green 类，那么新点就分到 red 类。

KNN 的特点：

  • 没有真正的训练步骤，只需要存储训练数据；
  • 因此也叫 memory-based learning、case-based learning、lazy learning；
  • 可以处理非线性边界；
  • 通常比 Rocchio 更灵活；
  • 但预测时要计算与很多训练样本的距离，可能较慢。

12. K 的选择

K 的选择很重要。如果 K 太小，比如 K=1，模型容易受噪声影响。如果 K 太大，邻居可能包含其他类别的点，边界会变得过于平滑。

通常：

  • K 取奇数可以避免二分类平票；
  • K 可以通过 validation set 或 cross-validation 选择；
  • 常见经验范围是 3 到 10。

13. Voronoi Diagram 和 1-NN

当 K=1 时，KNN 变成 1-nearest neighbor。 每个训练点会定义空间中的一个区域：区域内所有点都离这个训练点最近。

这些区域形成 Voronoi diagram。 PPT 中展示了平面被切成很多多边形区域，每个区域对应一个最近邻点。

这也说明 KNN 是一个 非线性分类器，因为它的决策边界可以非常复杂；而 Rocchio 更偏线性分类器。

总结

Clustering 是无监督地发现文档群组，Classification 是有监督地把新文档分到已有类别。

重点算法可以这样记：

方法 类型 核心思想
K-means 聚类 选 K 个中心，不断分配点并更新中心
Hierarchical clustering 聚类 自底向上合并或自顶向下拆分，形成树状结构
Rocchio 分类 / relevance feedback 用类别 centroid 或相关/不相关 centroid 做线性判断
KNN 分类 看最近 K 个已标注邻居，多数投票决定类别

一句话概括： 聚类是在没有标签时自动找结构；分类是在有标签时学习边界，并把新文档放到合适类别中。

Recommendation system

1. 推荐系统要解决什么问题

推荐系统的目标是回答：

“你还可能想知道、想看、想买、想听什么？”

课件先讲了一个背景：互联网商品和内容极其丰富，用户不可能逐个浏览，所以系统需要帮助用户发现新东西。理论上，推荐系统应该增加多样性，帮助长尾内容被发现；但实际中，很多算法会偏向已经流行的东西，因为过去销量、评分、点击越多，越容易被继续推荐。

2. 两类推荐系统

PPT 把推荐系统分成两大类。

Content-based filtering（基于内容的推荐）：

看物品本身的特征，然后推荐和用户过去喜欢的物品相似的东西。例如用户喜欢某个意大利餐厅，那么系统可能推荐另一个意大利餐厅。音乐推荐里，如果用户喜欢某些 “acoustic guitar”“female vocal”“slow tempo” 的歌，系统就推荐具有类似音乐属性的歌。

Collaborative filtering（协同过滤）：

看用户之间的行为相似性，利用“相似用户喜欢什么”来推荐。例如 Alice 和 Bob 都喜欢很多相同餐厅，那么 Alice 喜欢但 Bob 没试过的餐厅，就可能推荐给 Bob。

现实中的商业系统通常是 hybrid systems（混合推荐），会同时使用内容特征和协同过滤。

3. Utility Matrix：推荐系统的核心数据结构

很重要的概念是 utility matrix（效用矩阵）。

矩阵的：

  • 行表示用户；
  • 列表示物品；
  • 单元格表示用户对物品的偏好。

例如餐厅推荐里，行是 Alice、Bob、Cindy 等用户，列是不同餐厅，格子里可能是：

1
2
3
4
Yes / No
1 / -1
评分 1-5
空白 unknown

空白很重要： 它不是 0，而是 unknown，表示系统不知道用户是否喜欢这个物品。

推荐系统的核心任务就是： 根据已知格子，预测未知格子的值。

比如 Bob 没评价过 Il Fornaio，但 Alice、Dave、Estie 的评价和 Bob 很相似，那么系统可能预测 Bob 也会喜欢 Il Fornaio。

4. 最简单的方法：推荐最热门物品

Algorithm 0：直接推荐最受欢迎的餐厅，例如正评价最多、负评价最少的。

这个方法简单，但会忽略：

  • 用户自己的口味；
  • 相似用户的判断；
  • 小众兴趣；
  • 新物品。

所以它通常只能作为 baseline，不是真正个性化推荐。

5. 基于内容的推荐 Content-Based Filtering

基于内容的推荐会为每个物品建立 item profile，也就是物品特征向量。

例如电影可以用演员作为特征：

Movie Actor A Actor B Actor C
Movie 1 1 0 0
Movie 2 0 1 0

如果用户看过 5 部电影，其中 2 部有 Actor A，3 部有 Actor B，那么用户画像可以是这些物品画像的平均：

1
2
Actor A weight = 2/5 = 0.4
Actor B weight = 3/5 = 0.6

之后系统拿用户画像和新电影画像做相似度计算，比如用 cosine similarity。如果相似度高，就推荐。

6. Content-based 方法的优点

  • 不需要其他用户的数据；
  • 可以服务口味很独特的用户；
  • 可以推荐新的、不流行的物品；
  • 没有 first-rater problem，因为只要物品有内容特征，即使没人评价过也能推荐；
  • 可以解释推荐原因，例如“因为你喜欢某演员/某类型”。

7. Content-based 方法的缺点

缺点也很明显：

  • 合适的特征不一定容易找，例如图片、音乐、复杂文本内容；
  • 容易过度专业化，只推荐和用户过去喜欢的东西非常相似的内容；
  • 不容易利用其他用户的质量判断；
  • 对新用户有 cold-start problem，因为新用户没有历史行为，用户画像难以建立。

简单说： 基于内容的方法懂物品特征，但不太懂群体智慧。

8. 协同过滤 Collaborative Filtering

协同过滤的核心假设是：

如果 A 和 B 在很多事情上的看法相似，那么 A 喜欢的其他东西，B 也可能喜欢。

PPT 里先讲 user-user collaborative filtering，也就是找相似用户。

流程是：

  1. 用 utility matrix 表示用户评分；
  2. 计算用户之间的相似度；
  3. 找到与目标用户最相似的一批用户；
  4. 看这些相似用户喜欢但目标用户还没评价过的物品；
  5. 预测目标用户是否会喜欢。

9. 用户相似度：Jaccard、Cosine、Centered Cosine

Jaccard similarity：

只看两个用户共同评价过哪些物品，不太关心评分值。问题是它会忽略评分高低。

例如 A 和 B 都看过 Harry Potter 和 Star Wars，但一个给高分、一个给低分，Jaccard 仍可能觉得他们相似。

Cosine similarity：

把用户评分当成向量，计算夹角相似度。它会考虑评分值，比 Jaccard 更细。

但普通 cosine 有个问题：如果把未知评分当成 0，会让用户之间看起来比实际更远，因为 0 其实代表 unknown，不代表 dislike。

Centered cosine / Pearson correlation：

先减去用户自己的平均评分，再计算相似度。这样可以处理“有人天生给分高，有人天生给分低”的问题。

比如 Alice 平均打分很高，Bob 平均打分很低，直接比较原始分数可能不公平；中心化后，系统比较的是他们相对于自己平均值的偏好。

10. Item-item collaborative filtering

除了 user-user，PPT 还讲了 item-item collaborative filtering。

它不问“谁和我像”，而是问：

这个物品和哪些物品相似？

例如很多用户都同时喜欢 Movie 1 和 Movie 3，那么 Movie 1 和 Movie 3 就相似。 如果用户喜欢 Movie 3，而没看过 Movie 1，就可以推荐 Movie 1。

预测某用户对物品 i 的评分时，可以看：

  • 用户已经评分过的物品；
  • 这些物品和目标物品 i 的相似度；
  • 用相似度加权平均得到预测评分。

PPT 中的例子里，目标是估计 user 5 对 movie 1 的评分。系统找到与 movie 1 最相似的 movie 3 和 movie 6，然后用它们的相似度和用户对它们的评分加权，得到预测值约为 2.6。

11. Item-item vs User-user

理论上，user-user 和 item-item 是对偶的： 一个看用户相似，一个看物品相似。

但实践中，item-item 往往表现更好，原因是：

  • 物品通常比用户更稳定；
  • 用户兴趣会变，状态更多样；
  • 物品可以稳定归入类型、风格、主题；
  • 物品相似性通常比用户相似性更可靠。

例如一部电影的类型、演员、受众相对稳定；但用户今天想看喜剧，明天可能想看纪录片。

总结

推荐系统通过 utility matrix 记录用户—物品偏好，然后预测未知偏好。

主要方法可以这样记：

方法 看什么 优点 缺点
热门推荐 全局流行度 简单 不个性化
Content-based 物品特征 可解释、能推新物品 容易推荐太窄
User-user CF 相似用户 利用群体智慧 用户相似度不稳定
Item-item CF 相似物品 实践中常更稳定 依赖足够行为数据

一句话概括： 基于内容推荐“和你喜欢的东西相似的东西”，协同过滤推荐“和你相似的人喜欢的东西”，而现代系统通常把两者结合起来。

Assorted topics part A

1. IR 一直在演化

信息检索领域一直在变化。 除了传统的网页搜索、倒排索引、PageRank、query processing，现在还有很多新数据、新算法，以及来自机器学习、NLP、数据库、视觉模型等领域的交叉技术。

所以这份 PPT 是一个“快速扫盲式”介绍，每个主题都只讲一点，方便以后继续深入。

2. 图像理解与图像搜索

Image understanding and search。

核心例子是 ImageNet：一个大规模人工标注图片数据库。 它可以用来训练机器学习模型，比如 CNN、Vision Transformer 等，让系统理解图片内容。

这和 IR 的关系是：搜索不再只处理文本，也要能处理图片。 比如用户搜“一只坐在草地上的狗”，系统需要理解图片中有什么对象、场景和关系。

3. 代码搜索 Code Search

例子是 GitHub 的代码搜索和 GitHub Copilot。 代码搜索不同于普通文本搜索，因为代码有语法结构、变量名、函数调用、依赖关系等信息。

普通关键词搜索只能找字符串，而更好的代码搜索要理解：

1
2
3
4
函数做什么
代码结构是什么
变量之间如何关联
用户想找实现方式还是 API 用法

Copilot 则进一步从搜索走向生成：不仅帮你找代码，还能根据上下文生成代码。

4. Location-Based Search / Proximity Search

LBS / PS，也就是基于位置的搜索或邻近搜索。

它的核心是： 搜索引擎不仅看 query 本身，还看 query 发出的位置。

比如用户搜：

1
coffee shop

系统会优先返回附近咖啡店，而不是全世界最著名的咖啡店。

但位置搜索有隐私风险。如果系统能根据搜索或服务请求精确推断用户位置，就可能被用于 tracking。

5. Vector DB 和相似度搜索

Similarity search using vector DBs。

传统搜索主要靠关键词匹配；向量数据库会把文本、图片、代码、音频等数据转成向量 embedding，然后用向量相似度搜索，比如 cosine similarity。

直观来说：

1
2
语义相近的内容 → 向量空间中距离近
语义不相关的内容 → 向量空间中距离远

例如用户搜：

1
how to fix a leaking pipe

即使文档没有完全出现这些词，只要语义接近，也可能被搜到。

PPT 还提到，向量数据库可以作为生成式工具的 “infinite memory”，也就是给大模型提供长期外部知识库，支持 semantic search engine。

6. LDA 和 Topic Modeling

LDA 是一种主题建模方法，用来判断文档可能属于哪些主题。

例如一篇文章中频繁出现：

1
2
3
4
neural network
training
model
gradient

系统可能判断它的主题是 machine learning。

如果出现：

1
2
3
4
election
vote
senate
policy

主题可能是 politics。

LDA 的作用是： 从大量文档中自动发现潜在主题结构。

这和前面学过的 clustering 有点像，但 LDA 通常允许一篇文档混合多个主题。

7. ANN 和 Faiss

ANN，Approximate Nearest Neighbor，近似最近邻搜索。

在向量数据库中，如果有几亿个向量，精确找最近邻会很慢。 ANN 的思想是：不一定找绝对精确的最近向量，而是用更快的方法找到“足够接近”的结果。

Faiss 是一个常见的 ANN 工具库。

这在现代 IR 和 RAG 系统中特别重要，因为语义搜索常常需要在海量 embedding 中快速找相似内容。

8. Task-specific Fine-tuning

Fine-tuning 是把一个通用模型进一步训练成适合某个具体任务的模型。

比如一个通用语言模型可以被 fine-tune 成：

1
2
3
4
专门生成科研论文摘要
专门做法律问答
专门做医疗文本分类
专门写某种风格的代码

GPT-2 被 fine-tune 生成 scientific paper abstracts，Unsloth 等用于 LLM fine-tuning 的工具。

核心思想是：基础模型有通用能力，fine-tuning 让它更适合特定领域或任务。**

9. Task-specific Embedding

普通 embedding 只是把文本转成向量，但不同任务需要不同的语义重点。

例如同一句话，在不同任务中可能需要不同表示：

1
2
3
4
做情感分析：关注情绪
做主题分类：关注主题
做问答检索：关注是否能回答问题
做代码搜索：关注功能意图

Task-specific embedding 的思想是： 根据任务需求生成更合适的向量表示。

这样一个系统可以更好地支持多种 NLP 或 IR 任务。

Assorted topics part B

1. IR 领域继续快速变化

这部分继续看一些 “cutting edge” 技术和工业实现，包括：

1
2
3
4
5
6
7
retrieval
recommendations
knowledge extraction
LLM + memory
agent systems
vector search
AR / maps

核心观点是：信息检索 IR 是变化最快的领域之一，因为现代社会几乎所有系统都依赖信息获取、组织和推荐。

2. LLM + External Memory

外部记忆增强 LLM。

普通 LLM 本身是一个通用文本引擎，不一定掌握某个企业、数据库或领域的最新知识。 所以现在常见做法是：

1
LLM + 外部数据库 / 知识库 / 向量库 / 图数据库

例如：

  • 用自然语言查询 Neo4j 图数据库，而不是手写 Cypher；
  • 让 LLM 生成 SQL 查询数据库；
  • 用 external KB 帮助模型完成推理任务；
  • Retrieval Transformer 用外部 memory，让核心模型可以更小。

这其实就是后来很多 RAG 系统的思路： 模型负责理解和生成，外部知识库负责存储事实和领域知识。

3. Autonomous Task-Achieving：自主完成任务的 Agent

agent-based architecture。

传统聊天是用户一步步问，模型一步步答。 而 agent 的目标是：用户只给一个任务，系统自己拆成子任务并执行。

例如用户说：

1
帮我研究某个市场，整理竞争对手，生成报告

Agent 系统可能自动做：

1
搜索资料 → 提取信息 → 比较公司 → 写报告 → 检查遗漏

PPT 提到 AutoGPT 和 generative agents。前者试图让 LLM 自动规划和执行任务；后者则用 LLM 模拟人的行为和记忆，构造“生成式代理”。

4. LLM + Tasks + Memory = 新型“计算机系统”

1
2
传统计算机 = processor + code + data
LLM 系统 = LLM + tasks + DB / memory

也就是说，LLM 可以看作“处理器”，prompt / task templates 类似“程序”，数据库或向量库类似“内存”。

PPT 提到：

  • BabyAGI：尝试让系统自动生成任务、执行任务、再生成新任务；
  • LangChain：把 prompts、tools、retrieval、memory 串成任务流程；
  • OPL stack：OpenAI + Pinecone + LangChain；
  • SudoLang：一种面向 LLM 任务编排的语言风格。

第 6 页截图展示了 Pinecone meetup，主题是用 OpenAI + Pinecone 构建 AI apps，说明这种 stack 当时已经进入开发者生态。

5. NER：命名实体识别

Named Entity Recognition。

NER 的任务是：从文本、图像、视频、音频中识别出实体，比如：

1
2
3
4
5
6
7
person
place
organization
product
date
event
thing

例如句子：

1
Barack Obama was born in Hawaii.

NER 应该识别：

1
2
Barack Obama → Person
Hawaii → Location

PPT 提到可以用 BERT 做 NER。 在 IR 中，NER 很重要，因为搜索引擎和问答系统需要知道 query 或文档里提到的到底是人、地点、公司还是事件。

6. BERTopic：基于 BERT 的主题建模

Topic Modeling，尤其是 BERTopic。

之前 Misc_1 讲过 LDA。这里的 BERTopic 是更现代的主题建模方法，它使用 BERT embedding 表示文本语义，然后聚类出主题。

它比传统 LDA 更适合处理语义相近但词面不同的文本。例如：

1
2
3
car
automobile
vehicle

这些词表面不同，但 embedding 会把它们放得更近。

7. Knowledge Graph Construction

知识图谱构建。

知识图谱用结构化三元组表示知识：

1
(subject, predicate, object)

例如：

1
2
(Paris, capitalOf, France)
(Apple, foundedBy, Steve Jobs)

KG 是很好的知识表示方式，因为结构清晰、方便查询和推理。现在可以用 LLM 从非结构化文本中抽取实体和关系，自动构建知识图谱。

这和前面 QA、Knowledge Graph、NER 课程内容是连在一起的： NER 识别实体，关系抽取识别实体之间关系，KG 把它们组织起来。

8. Recommendation Engines：工业推荐系统

TikTok / ByteDance 的 Monolith 推荐系统，以及 Twitter “For You” timeline 和 Lyft 推荐系统。

第 12 页图展示了 Twitter 推荐 “For You” timeline 的流程，大致包括：

1
2
3
4
5
candidate sourcing
global filtering
scoring & ranking
filtering for diversity
mixing ads / who to follow / tweets

第 13 页还列出 Twitter 的 5 个阶段：

1
2
3
4
5
1. Candidate Sourcing：从海量 tweets 里召回候选
2. Global Filtering：过滤到大约 1500 candidates
3. Scoring & Ranking：用神经网络排序
4. Filtering：保证作者和内容多样性
5. Mixing：混入广告、关注推荐等模块

这说明现实中的推荐系统不是一个简单公式，而是一个多阶段 pipeline： 先粗召回，再过滤，再精排，再做多样性和业务规则混合。

9. 更多聚类方法

之前主课讲了 K-means。这里列出一些更现代或常用的方法：

1
2
3
t-SNE
HDBSCAN
UMAP

它们常用于高维数据可视化、聚类和结构发现。

简单理解：

  • t-SNE：适合把高维数据降到 2D/3D 可视化；
  • UMAP：也用于降维，速度快，常用于 embedding 可视化；
  • HDBSCAN：密度聚类方法，不需要像 K-means 那样固定 K，能发现不规则形状 cluster。

10. Search 的其他方向

Creative Commons search：搜索可复用授权内容，比如图片、音频。 Manifold search：用流形学习做相似搜索。 Graph-based nearest neighbor search：在图上做最近邻搜索，而不是只在普通度量空间中查找。 Redis vector search：用 Redis 做 AI-driven vector search。 Discord search：Discord 用倒排索引搜索海量消息。

核心是：搜索的对象和底层结构越来越多样，已经不只是网页文本和普通倒排索引。

11. NeRF、AR、Location-Based Search

传统 LBS 返回的是：

1
2
3
4
地址
地图
附近地点
路线

而新的地图搜索可能返回 immersive views（沉浸式视图）。 这些视图可以通过融合大量照片、航拍图和 3D 渲染技术生成。

PPT 提到 NeRF，也提到 3D Gaussian Splatting。 意思是：未来的位置搜索不仅是“给你一个地点”，而是可能直接给你一个可交互、沉浸式的 3D 场景。

Assorted topics part C

1. Transformer 和 Attention

开头重点是：

1
A Transformer computes self-attention.

也就是：Transformer 的核心机制是 self-attention（自注意力）。

自注意力让模型在处理一句话时，能判断每个词应该关注其他哪些词。例如：

1
The animal didn't cross the street because it was too tired.

模型要知道 it 指的是 animal，不是 street。 Transformer 就是通过 attention 机制捕捉这种上下文关系。

PPT 还提到 Transformer 不只用于语言模型，也能扩展到其他领域，比如：

1
2
3
Vision Transformer, ViT
time-series prediction
music generation

也就是说，Transformer 已经从 NLP 扩展成一种通用建模架构。

2. LLM 训练数据格式：JSONL

一种常见训练数据格式：JSONL / JSON Lines。

JSONL 的特点是：每一行都是一个独立 JSON 对象。 例如 instruction tuning 数据可能长这样：

1
2
{"instruction": "Explain PageRank", "response": "PageRank is..."}
{"instruction": "Summarize this article", "response": "..."}

PPT 用 Databricks Dolly 15k 作为例子，说明 LLM 微调数据常以这种格式组织。

3. Context 和 Attention 的二次复杂度瓶颈

讲 context length 的问题：

LLM 很依赖上下文，但普通 Transformer 的 attention 计算有一个问题： 随着上下文长度增加，计算成本通常按平方增长，也就是所谓：

1
quadratic bottleneck

所以长上下文很贵、很慢。

一些解决方向：

1
2
3
4
5
6
Hyena
Mamba
Jamba
Hymba
long convolution
mixed architecture

这些方法试图在不完全依赖标准 attention 的情况下，更高效地捕捉长距离依赖。

NVIDIA 的 Hymba它是一种面向小模型的 mixed architecture，用来更高效捕捉上下文。

4. Fine-tuning：让模型适应特定领域

通用 LLM 虽然能力强，但不一定适合专业领域，比如：

1
2
3
4
5
medicine
law
finance
scientific writing
enterprise documents

Fine-tuning 的作用是： 把通用模型进一步训练成某个领域或某个任务更擅长的模型。

PPT 还提到 ReFT 以及一个 fine-tuning 技术综述。 核心意思是：fine-tuning 是增强 LLM 的一种主要方式，但现在方法很多，不只是传统全参数微调，还包括各种参数高效微调和表示微调。

5. RAG：用外部知识增强模型

Retrieval-Augmented Generation**。

RAG 的思想是：

1
2
LLM 本身负责理解和生成
外部知识库负责提供事实和上下文

外部知识库可以是：

1
2
3
4
vector DB
knowledge graph
relational DB
document store

当用户提问时，系统先检索相关资料，再把资料放进 prompt 让 LLM 回答。

PPT 还提到 Hybrid RAG： 把多种检索方式结合起来，比如向量数据库 + 知识图谱。

但 PPT 也强调 RAG 有问题，例如：

  • context mismatch：检索到的内容和问题不完全匹配；
  • chunking 错误：文档切块不合理，导致关键信息被切断；
  • vector DB 规模变大后准确性可能下降；
  • 复杂文档，如表格、PDF、账单，很难直接转成适合 LLM 的上下文。

EyeLevel / GroundX 的截图说明，有公司专门把复杂文档处理成 “LLM-ready data”。

6. HyDE：RAG 的增强版本

第 11 页提到 HyDE，PPT 里称它类似 “RAG++”。

HyDE 的大意是： 面对一个 query，先让模型生成一个“假想答案”或“假想文档”，再用这个生成内容去检索真实文档。

这样做的原因是：原始 query 可能太短、太模糊，而生成出来的假想文档语义更丰富，更容易匹配到相关资料。

7. GenAI：生成式 AI 不只是 GPT

第 12 页讲 Generative AI。

PPT 说生成式模型不只有 GPT，还有：

1
2
3
4
5
6
GANs
VAEs
diffusion models
radiance modeling
point-cloud modeling
music pattern modeling

生成对象也不只是文本，还包括：

1
2
3
4
5
6
7
8
images
audio
video
3D
molecules
architecture plans
circuit layouts
business cards

所以 GenAI 的核心是： 模型学习数据分布，然后生成新的、类似但不完全相同的内容。

8. LLM 的新方向

包括：

硬件优化：更适合大模型训练和推理的芯片与系统。

非 Transformer 架构： 例如 SSM、Mamba、Hyena、Jamba、Hymba，以及 diffusion-based LLM。

位置编码改进： 比如 RoPE，用来帮助模型理解 token 的顺序和相对位置。

SLM，小语言模型： 不是所有任务都需要超大模型，小模型更便宜、更容易本地运行。

VLM / multimodal LLM： 模型同时处理文本、图像、音频、视频。

bit-crushed weights： 把权重量化到很低精度，比如 -1/+1 或 -1/0/+1，让模型更小、更快。

agentic approaches： 结合 reasoning、tool use、MoE、CoT、ToT、GoT 等，让模型像 agent 一样完成任务。

local running： 在本地设备上运行 LLM，减少云端依赖。

visual dataflow environments： 比如 ComfyUI、LangFlow，用可视化方式搭建 AI 应用流程。

standards： 如 DSPy、A2A、MCP 等，说明 LLM 应用生态正在逐渐工程化、标准化。

9. LLM Apps

很多新应用不是自己从零训练模型，而是基于 LLM 构建功能，例如：

1
2
3
4
5
6
finance assistant
research assistant
document QA
NotebookLM-style apps
enterprise knowledge assistant
code assistant

FinGPT、BloombergGPT、NotebookLM、Databricks 的 GenAI app 架构等。

核心观点是： LLM 正在成为应用开发的基础组件。

10. LLMOps

把 LLM demo 做出来不难，但真正上线需要工程化流程，包括：

1
2
3
4
5
6
7
8
9
10
11
prompt management
evaluation
retrieval quality monitoring
latency optimization
cost control
guardrails
logging
model/version management
A/B testing
data privacy
deployment

这就是 LLMOps： 把 LLM 应用可靠、安全、可维护地放到生产环境。

它类似传统 MLOps，但多了 prompt、RAG、工具调用、模型输出评估等新问题。

11. Agentic IR / AIR

最后一页讲 Agentic IR，也就是 Agent 化的信息检索。

传统 IR 是：

1
用户输入 query → 系统返回结果

Agentic IR 可能变成：

1
用户表达目标 → agent 理解任务 → 自动搜索 → 调用工具 → 验证信息 → 综合答案 → 继续迭代

也就是说，未来的信息检索可能不只是“找资料”，而是一个能主动完成信息任务的 agent。

PPT 最后举了类似：

1
OpenAI phone + Samsung glasses

这种未来设备形态，暗示 IR 可能会进入随身、持续、语义化、agent 化的阶段。