利用信息，消除歧义 – 吴军博士对于搜索本质的解释定性

本文内容来自于一次吴军博士的讲座整理

用信息熵衡量搜索

香农在信息论中提出信息熵的概念，统摄这个议题

语言的出现是为了人类之间的通信，任何一种语言都是一种编码的方式，这也是语言模型中直接抽象 encoder $\rightarrow$ decoder 的来源，自然语言处理问题等价成通信的解码问题

一本五十万字的中文书平均有多少信息量？

• 常用汉字大约有7000，假如每个字等概率，那么大约要用13个bit表示一个汉字（实际上汉字的使用是不平均的）

• 考虑到实际每个汉字使用不平均，前10%的汉字占文本的95%以上

  • 不考虑上下文相关性，每个汉字独立概率，那么每个汉字信息熵大约8-9个bit

  • 考虑上下文相关性，每个汉字信息熵约5bit左右

    传统理论上一个汉字包含的信息少于5bits，大部分网上均称汉字的信息熵大于6，甚至达到11

故一本50w字中文书，信息量大约是250wbit

这里讲的250wbit是个平均数，同样长度的数，所含的信息可以差很多

编码压缩存储

• 用好用的压缩算法压一下，整本书可存成一个320KB的文件
• 若直接用两字节编码存储这书，大约要1MB大小，是压缩文件的3倍

这两个数量的差距，在信息论中称作 冗余度（redundancy)

重复内容越多，信息量就越小，冗余度就大

不同语言的冗余度差别很大，汉语在所有语言中冗余度是相对小的，这与人们普遍的认识“汉语是最简洁的语言”是一致的

定量分析

从10亿数据中找出10个文档，需要27bit的信息

$10亿=2^{30}$， $10=2^3$，30-3=27

其中query本身能提供20bits的信息，这就是搜素中最重要的内容

• 每个查询串，一般3-5个字符，平均4个，4*5bits/字=20bits
• 所以查询命中信息（hit proximity）最重要，占20bits

还需要7bits

• 文本质量度量（pagerank）
• 大众的知识（查询重写、点击模型）
• 个性化

西瓜和芝麻

抓住主要部分，钻在小的芝麻粒做得再好也只是"芝麻"，这里的西瓜就是20bits的内容，即查询文字

信息的来源：

• QRW – query rewrite transform提供20bits的信息，占70%的信息量（hits）
• 客户端收集的log数据（点击行为模型），提供3.4bits信息，对相关性排序贡献在40%以上（现阶段更高）
• QRW的重构，根据上下文相关性提供2~3bits的信息（关联性）
• 搜索偏好的设定（个性化）
• 隐含信息，把可能的结果作为QRW进行查询

QRW功能示例

当今地球上五十个最值得去的地方

• 当今，表明结果网页有时效性要求。时间较晚的网页会被排序加权，提供全局属性
• 上下文无关冗余词：个，最，去，的
• 上下文相关冗余词：当今。提供全局属性后，其在匹配时可作为非必留
• 同义词替换
  • 地球：世界
  • 五十：50
  • 地方：地域，地区（得分不高，不适合是合适的同义词替换）
• 世界上 五十 值得 地方

技术的两个支柱

有信息–数据的重要性

• 索引量要尽可能大

• 内容尽可能全

  • 本来信息就不够，还丢掉些就更难做好
  • 不需要多余小歘歘

• 过滤掉噪音：作弊

用好信息–模型的重要性

• 保证将效果接近最佳
  • 所有信息一起用
• 好的模型一定是简约的
• 模型里的每一部分原理都讲得清

排序所需的信息

与查询无关的部分

可分为link-related 和content-related

• 完整的网页（内容、title、body、anchor等

• Pagerank（很像专业内的reference）

  • 原始算法未回应时效性方面的关注
  • 因作弊被污染数据的纠正
    • 今天对网页质量的衡量是全方位的，商业度同样考量，如一些八卦网站pagerank可能很高，但内容权威度很低

• 访问量（popularity分层的依据）

• 信息含量（informative measurement去重）

  • 负向例子：如过短的新闻

• 时效性

和查询相关的部分

• 命中：hits
• 点击：click information
• 关键词之间的关联性（proximity）
  • 距离
  • 其它语义相关性
    • 同义词
    • 语法关联性没有语义关联性重要，语义：信息直接对应
• 查询重写
• 商业和作弊信息
• 隐含信息
  • 高考（年代），地点
  • 查询类型（人物，专有名词，问题）
  • 同义词扩展等
• 关联性本质是上下文信息有助于降低不确定性
• 汉字查询词：上下文相关提供的信息约莫占2-3bits

个性化信息

• 浏览器设置和搜索偏好的设置
• 地点
• 用户画像
  • 搜索历史：search history,query hints
  • 喜好站点
• 订阅信息
• 前面几次搜索
• 前几次点击的表现

个性化是否是良药

• 累死了产品经理，但效果甚微

• 两个人在不同维度权重不同（维度由产品决定），但差异性（距离）过小，不足以累计起足够有意义的信息

  • 例如有6个维度

    • A $\begin{bmatrix} 0.3 &0.2 &0.15 &0.05 &0.2 &0.1 \end{bmatrix}$

    • B $\begin{bmatrix} 0.2 &0.4 &0.05 &0.2 &0.05 &0.1 \end{bmatrix}$

    • 大众平均 $\begin{bmatrix} 0.25 &0.3 &0.1 &0.125 &0.125 &0.1 \end{bmatrix}$

    • 两者之间的KL-divergence

      • A对B： 0.154 bits
      • B对A：0.152 bits
      • 对大众更小：A：0.102，B：0.081

• 需要比较多的信息才起作用，累计道1bits的信息

• 成本上也要考量，是否要每个人建立一个click model，要做，但不是首要的目标任务

排序的一勺烩

• 信息是原料，排序函数ranking function是菜谱
• 把每种信息看成一种变量，多种信息组合搜索空间巨大
• 难点就在信息的组合
  • 借鉴统计模型的思想
    • 符合所有可靠的统计数据
    • 满足所有的边际分布
    • 尽可能平滑
  • 方法论：机器做 Jump Start，专家做经验公式
• 理想情况下各种信息是正交的，现实却是：
  • 大多信息不是统计独立的
  • 一些信息完全被其它信息覆盖
• 面对现状，对影响力较小的信息，需定期review和删除

召回不是问题，但准确率不高时

• 内容作弊
• 没有找到关键词
  • 我们需帮用户补上（隐含的信息）
• 信息整合的不好 – 模型不好
  • N种Feature，如何构造scoring function G$\begin{pmatrix} x1,&x2,&…,&xn \end{pmatrix}$
  • 新闻：时效性和质量的平衡
  • 内容质量和相关性的平衡，等等
  • 如果一个scoring/ranking的架构不能适应算法，改架构而不是改算法
    • 点击模型放到最前面
    • QRW的预计算（保证先于很多的过滤）
  • 架构（模型）上要避免同一个原始Feature多次使用

应对作弊的方法

笨办法：在网页上做文章

• 检测无效跳转页面
• 检查javascript等
• 减少hard code排序算法

聪明办法：在链接上做文章（背后皆有利益驱动）

• 链接批发商检测
• 惩罚购买链接的目的地
• 过期域名检测

垃圾的本质

• 噪音的引入且产生正反馈
• Anti spam（反作弊）的核心是加入信息，降低不确定性
  • 简单的分类器不足够
  • 如有1/2的spam，至少需要一个bit的信息
  • Naive Bayesian Classifier，准确率差不多有90%

点击模型&客户端的竞争

• 对相关性的贡献在40%以上
  • 举例，20条信息，等概率的话，信息熵5.7bits
  • 若点击率分别是1/2，1/4，1/8，信息熵变成2.3bits
  • 改进了3.4bits，在查询所需的额外7个bits中，相当于提升了3.4/7=50%的效率
• 今天所有搜索引擎，对常见的查询，结果都不差，差异在于不常见的查询。提高这些搜索查询质量实际靠的是大量的数据
• 数据成为决定好坏的第一要素，算法倒在其次了
  • 网页本身的数据(完备，新)
  • 用户点击的数据，点击模型统计数量足够，这种根据点击决定的排名就很准确有效。点击模型贡献了搜索排序至少60%~80%的权重
    • 市占率较小的引擎甚至在这些查询由热变冷之前，还没凑齐那么多数据，因此点击模型就非常不准确
    • 搜索行业就形成了一种马太效应：后进场的公司也不会坐以待毙，采取办法快速获取数据，收购流量（如微软收购雅虎，其搜索量由原来google的10%陡然提升至20%~30%，点击模型排名准确了许多）
    • 还有更激进的办法，如toolbar，浏览器甚至输入法来收集用户点击行为
    • 若一家公司能在浏览器市占率高，即使搜索量小，也能快速改进长尾搜索的质量
    • 搜索质量的竞争就变成了浏览器或其它客户端软件市占率的竞争

爬虫的挑战

现在互联网非常庞大，商业网络爬虫需要成千上万个服务器，通过高速网络连接起来

如google在2013年时整个索引大约有1万亿个网页。即使最新最频繁的基础索引也有100亿个网页，假如下载一个网页要1秒钟，那么下载这100亿网页需317年，下载1万亿网页要3.2w年，是人类有文字记载历史的6倍时间

现在很多网页是用一些脚本语言生成的，页面分析很复杂，要模拟浏览器运行一个网页，才能得到里面隐含的URL，所以要做浏览器内核的工程师来写网络爬虫的解析程序

V8引擎和Chrome应该就是网络爬虫的副产物

神经网络的代际趣闻

人工神经网络和人脑没半毛钱关系，本质上是一种有向图。但它使用了一个新名词：神经元。让人感觉很神秘，且会联想到仿生学或认知科学等一辈子都难搞懂的东西

神经网络的规模决定了它能做多大事情，因为节点之间是连接的，复杂度随着网络规模扩大呈指数级上升

• 经历了几次技术名词被玩坏：神经网络$\longrightarrow$连接主义$\longrightarrow$深度学习
• 这一代根据网络非常深的特点，起名深度学习
  • 相较于往代运气很好，云计算的兴起使得使用成千上万台计算机成为了可能

总结

• 过去几十年智能产品质量的根本：信息
• 信息量的提升是这些产品（机器翻译，语音识别，搜索，NLP）进步的根本
• 如果没有提供新的信息，不要指望搜索质量有任何提高
  • 如导出式特征，是没有贡献额外信息的，同一个信息用多遍没有用
• 两个支柱
  • 有信息（数据的重要性），常被忽视
  • 用好信息（模型的重要性）

赠语

• 忘掉自己的专长
  • 不要做铁锤人，一锤在手，满眼都是钉。解决问题有很多办法，很多办法比你手上的简单，简单才是美！
  • 考虑产品是怎样的，不是我最容易做成什么样
• 在产品方案选择上，关注每一个细节，但在过程中要建立信息秩序
• 在工程方案选择上，集中精力解决95%的问题，不浪费精力在5%的问题上，不要低估简单方法的有效性
  • 完成比完美重要，经常来说可以提早很多时间将变化提供给用户，且带来质的提高，雪中送炭；
  • 暂时放弃的20%的收益，对用户而言通常是锦上添花
  • 坚持选择简单方案另一个原因，是容易解释每一步和方法背后的道理，便于出问题时查错，且容易找到今后改进的目标
• 用数据说话，再有sense的人也会犯错。Never get any conclusion without data
• 提高自己的境界
  • 之前苹果的东西为什么做那么好
  • 境界高了，才知道关键技术在哪里
    • ipod的关键技术，google的关键技术
• 最好的指引也是不要去做什么（可少犯很多错误），节省很多可能做无用功的时间
• 所有产品最终都是要盈利的