检索技术及向量数据库

基础索引

数据库索引难点:

常见索引优化策略:

其他业务场景需求:

距离检索之天真办法: 额外辅助索引 idx_bit_count = bit_count(x)

字符串匹配算法 / string matching

Q: needle in haystack 是如何实现的?

哲思: 失败是成功之母, 从不匹配中尽可能抽取有用的信息

Python: 短文本 Boyer–Moore–Horspool (BM简化版), 长文本 Two-Way

https://github.com/python/cpython/blob/main/Objects/stringlib/fastsearch.h

字符串匹配自动机

检索: 针对海量的haystack文本构建有效的索引结构, 从而快速框定小样本目标数据

文本搜索

information retrieval / search / full-text search / …

备忘

文本搜索需求

词包模型

bag of words / BoW

文档 = {词: 频数}

再弱化一点: 词集? 文档 = {词}

倒排索引 / inverted index

检索过程: 输入预处理 -> 查找倒排索引 -> 求交 -> 后处理 -> 评分排序

搜索场景分词诉求

分词 / parser / tokenizer / cut / …

带入数据分布先验做数据压缩

构建索引时分词: 细粒度拆分, 冗余分词, 提召回. 缺点: 倒排索引数据量膨胀. 极端情况: n-gram 分词. 搜索时视情况可选择不同的分词器保精度. Q: 为什么会掉精度? 检索时输入文本也应冗余分词么?

n-gram index

场景: IDE搜索

https://dev.mysql.com/doc/refman/5.7/en/fulltext-search-ngram.html

https://www.elastic.co/guide/en/elasticsearch/reference/current/analysis-ngram-tokenizer.html

编辑距离检索

场景: 拼写纠错, 搜索召回, “你是不是要搜索…”

naive approach

长度n单词, 字表k

Levenshtein_automaton: 给定词表构建, 找出所有编辑距离m内的有效词.

一般针对给定词典做, 任意文本编辑距离, 先分词拆解处理

TODO DEMO TIME

排序评分 / TF-IDF / BM25

语言模型视角解读 / The query likelihood model

其他的排序规则混合: 文档的属性, 如重要性, PageRank指标, …

ES分词插件

IK分词器: https://github.com/medcl/elasticsearch-analysis-ik

官方插件: https://www.elastic.co/guide/en/elasticsearch/plugins/current/analysis-smartcn.html

搜索质量严重依赖于分词及相似度计算指标, 很多搜不出来, 可惜现在没有例行评估优化

向量计算视角的全文检索

文档的TF矩阵, IDF向量

输入检索词 -> 独热向量Q

numpy.argmax(Q * TF @ IDF)

也可以把IDF向量提前分解到TF矩阵上, 记作TF-IDF矩阵

解释:

DEMO TIME

词向量

词嵌入 / Embedding

词包模型:

词向量:

词向量的学习, 本质上基于邻近词共现概率的学习 (两词向量内积 ~ 共现概率)

主题向量

LSA (latent semantic analysis): 文档TF-IDF矩阵SVD分解 (W=USVt-> 左特征向量 (词主题向量) + 特征值 (主题权重) + 右特征向量 (主题在语料的分布)

主题 = 认为出现一个词的时候, 在说一个主题的概率较大; 或者反过来说, 一个词被多大的可能纳入描述某个主题的文章中

文档分类(主题)标注 -> 指定Vt -> 习得词对于分类的贡献概率

LSA矩阵维度: 词表 x 主题

主题向量 VS 词向量

都可以认为式无监督的学习方法 / 自编码

文档的向量化表达

词向量: 缺点, 词向量习得后固定, 与上下文无关 深度学习: 超越邻近词视距, 更复杂的交互结构, 词向量上下文/全文深度相关

回顾BERT:

词向量 -> 模型计算 -> 文档向量 -> 分类输出层

相似的文档, 表征的文档向量应相似, 因此可直接检索文档向量做语义搜索

gensim / fasttext

传统NLP艺能工具

gensim.models.LsiModel / gensim.word2vec

fasttext:

哈希 / 特征向量 / LSH

hash: chopped meat mixed with potatoes and browned

哈希: 接受不固定的输入, 输出定长的字节, 以期捕获输入的某种特征

CHF (cryptographic hash function)

LSH (locality-sensitive hashing)

文本 / SimHash / 主要针对长文本, 解决网页抓取去重问题

我们业务上更需要针对短文本的编辑距离不敏感的simhash, 短文本编辑距离检索聚类

图像 / perceptual hashing / pHash / 相似图像检索

LSH”曲解”为机器学习的表征函数

距离检索手段

低维: 空间索引, GIS, 地图临近搜索, L1/L2度量

高维: 向量检索

树索引检索

R-Tree 针对低维空间

R=rectangle. 每个节点是一个空间闭包 (pos_min, pos_max), 从而可以范围索引确定 构建索引目标: 用最少的纸盒把房间中的点包住, 且尽可能的留白 和B-Tree结构类似

针对高维空间是否仍然有效 ??? 过于稀疏, 筛选性低

KD-Tree / k-dimensional binary tree

复习决策树 / decision-tree 生成手段, 每个维度当作一个特征分量, 从筛选性(方差)最高的分量开始切

图结构检索

Q: 不同于地图寻路, 如何定位开始检索的节点?

量化手段

也可以理解为一种LSH

主要是为了确保量化前后计算的评分(这里严谨点, 不说度量)不发生较大变化, 因此需要先确定评分函数后针对性的量化

对比模型参数压缩/量化: 模型压缩需要考虑矩阵计算便利性, 以及点乘结果的尽可能少扰动

faiss

https://github.com/facebookresearch/faiss/wiki

CODE HERE

首先不要瞧不起暴力/线性索引, 通过指令并行, mmap减少内存, 小场景还是可以满足诉求的, 参考目前搜索词推荐

milvus

https://milvus.io/docs

底层基于faiss, 类似lucene和elasticsearch, 工具包还是单独数据库的区别

向量数据库

LLM风口后飞上天后的突然带火的热词

https://www.infoq.cn/article/saw52ys9ymut3c2zb9wp

本质上还是侧重高维向量数据快速检索问题

实现手段:

ES/PostgreSQL+插件, 你也可以说它是向量数据库

Reference

HOME