Post

搜索算法相关联想

Posted Updated
By 10 min read

搜索引擎的难题

  • Google早已成为全球最成功的互联网搜索引擎，但这个当前的搜索引擎巨无霸却不是最早的互联网搜索引擎，在Google出现之前，曾出现过许多通用或专业领域搜索引擎。Google最终能击败所有竞争对手，很大程度上是因为它解决了困扰前辈们的最大难题：对搜索结果按重要性排序。而解决这个问题的算法就是PageRank。毫不夸张的说，是PageRank算法成就了Google今天的低位。要理解为什么解决这个难题如此重要，我们先来看一下搜索引擎的核心框架。

搜索引擎的核心框架

  • 虽然搜索引擎已经发展了很多年，但是其核心却没有太大变化。从本质上说，搜索引擎是一个资料检索系统，搜索引擎拥有一个资料库（具体到这里就是互联网页面），用户提交一个检索条件（例如关键词），搜索引擎返回符合查询条件的资料列表。理论上检索条件可以非常复杂，为了简单起见，我们不妨设检索条件是一至多个以空格分隔的词，而其表达的语义是同时含有这些词的资料（等价于布尔代数的逻辑与）。例如，提交“美食 攻略”，意思就是“给我既含有‘美食’又含有‘攻略’词语的页面”，
  • 当然，实际上现在的搜索引擎都是有分词机制的，例如如果以“美食的攻略”为关键词，搜索引擎会自动将其分解为“美食 的 攻略”三个词，而“的”作为停止词（Stop Word）会被过滤掉。关于分词及词权评价算法（如TF-IDF算法）是一个很大的话题，这里就不展开讨论了，为了简单此处可以将搜索引擎想象为一个只会机械匹配词语的检索系统。
  • 这样看来，建立一个搜索引擎的核心问题就是两个：1、建立资料库；2、建立一种数据结构，可以根据关键词找到含有这个词的页面。
  • 第一个问题一般是通过一种叫爬虫（Spider）的特殊程序实现的（当然，专业领域搜索引擎例如某个学术会议的论文检索系统可能直接从数据库建立资料库），简单来说，爬虫就是从一个页面出发（例如新浪首页），通过HTTP协议通信获取这个页面的所有内容，把这个页面url和内容记录下来（记录到资料库），然后分析页面中的链接，再去分别获取这些链接链向页面的内容，记录到资料库后再分析这个页面的链接……重复这个过程，就可以将整个互联网的页面全部获取下来（当然这是理想情况，要求整个Web是一个强连通（Strongly Connected），并且所有页面的robots协议允许爬虫抓取页面，为了简单，我们仍然假设Web是一个强连通图，且不考虑robots协议）。抽象来看，可以将资料库看做一个巨大的key-value结构，key是页面url，value是页面内容。
  • 第二个问题是通过一种叫倒排索引（inverted index）的数据结构实现的，抽象来说倒排索引也是一组key-value结构，key是关键词，value是一个页面编号集合（假设资料库中每个页面有唯一编号），表示这些页面含有这个关键词。本文不详细讨论倒排索引的建立方法。
  • 有了上面的分析，就可以简要说明搜索引擎的核心动作了：搜索引擎获取“美食 攻略”查询条件，将其分为“美食”和“攻略”两个词。然后分别从倒排索引中找到“美食”所对应的集合，假设是{1， 3， 6， 8， 11， 15}；“攻略”对应的集合是{1， 6， 10， 11， 12， 17， 20， 22}，将两个集合做交运算（intersection），结果是{1， 6， 11}。最后，从资料库中找出1、6、11对应的页面返回给用户就可以了。

    思路二：

  • 排序时候，引入神经网络，代替pagerank
    1. 对比学习，
      • 对比学习在解决什么问题？
      • 如何学习representation
      • 解决数据稀疏的问题
      • 如何更好的利用没有label的数据
        • 未打标的数据远远多于打标的数据，不用简直太浪费了，但是要打标又是一个耗时耗力耗钱的事儿
      • 有监督学习的缺点：
    1. Attention 机制，实际上就是找到序列的重要程度，利用q和k矩阵作为加权的权重，变化v。(input 都是x，self attention，此时表示搜索的query和内容当作一个输入序列)

      在推荐系统领域

  • 几个基本步骤，推荐系统的主要四个阶段（召回、粗排、精排、重排）
阶段特点
召回从海量物品中快速找回一部分重要物品
粗排进行粗略排序，保证一定精准度并减少物品数量
精排精准地对物品进行个性化排序
重排改进用户体验
划分类型描述特点作用
传统划分   
召回根据用户部分特征，从海量的物品库里，快速找回一小部分用户潜在感兴趣的物品。速度快。 
排序可以融入较多特征，使用复杂模型，来精准地做个性化推荐。结果精准。 
精细划分   
召回（多路召回）根据用户部分特征，从海量的物品库里，快速找回一小部分用户潜在感兴趣的物品。  
粗排（可用可不用，根据场景选择）通过少量用户和物品特征，简单模型，对召回的结果进行个粗略的排序，保证一定精准的前提下，进一步减少选取的物品数量。 防止用户召回环节返回的物品数量过多，影响排序环节效率。
精排（重要）可以使用任何特征和复杂模型，尽量精准地对物品进行个性化排序。  
重排改进用户体验，可以采用各种技术及业务策略（技术产品策略主导），比如去已读、去重、打散、多样性保证、固定类型物品插入等等。技术产品策略主导。 

Reference

Generative AI, Artificial Intelligence
Algorithm
This post is licensed under CC BY 4.0 by the author.