向量数据库技术鉴赏观看记录

发表于 2023-07-01 更新于 2024-04-21 分类于视频笔记 Disqus：本文字数： 1.6k

前言

配合 Ele 实验室的下列视频食用：

和多媒体数据处理课的实验相关密切（联系拓展到了四个实验中的三个），所以做一个记录。

我们可以将几乎所有的事物转化为数个值的组合来进行区别和描述。例如，一个狗={毛发长短，毛发颜色，体格大小，温顺程度……}，于是就可以用向量来表述一个东西。

向量一定程度的推理关系：如果“关系”作为向量的一环，那么我们会发现“警察与小偷”和“猫和老鼠”之间关系的相似性。

向量的应用：

图片领域：描述特征。实现“以图搜图”功能，参考计算机视觉实验和多媒体数据处理实验3（多媒体实验3：基于 BOF 进行相似图片搜索）
文本向量化：描述一个句子中有多少个x关键词，见上述多媒体数据处理实验3。相似文本内容查找。利于理解文本的实际内容，AI相关。
- 将相似对话输入给 chatGPT，极大提高输出效果。

问题：传统数据库不适合存储处理向量（在一些云计算的例子中，甚至只提供存储字符串类型）。

传统数据库：通过查询语句进行精准搜索

向量数据库：查询库中与查询向量最相似的向量转化为 KNN 问题，具有一定的模糊性。

距离的定义：欧几里得距离、余弦相似度、海明距离等……

近似最近邻 ANN：通常来说，试图提高速度的行为基本上都会带来准确率的下降。例如 Kmeans 中将一个点放入了错误的类中，算法得到的往往是近似的 KNN（参考 LSH 中的结果部分）。

局部敏感哈希算法 LSH：关于欧几里得距离的 LSH，见多媒体实验4：LSH局部敏感哈希
- 采用海明距离的LSH
  - 哈希函数：随机一个有正反的超平面。判断点是在正面还是反面，记为0/1。
  - 对两个点点被哈希得到的 01 串计算海明距离
  - 把 01 串进行分段，只要有一个段一致就候选的策略，提高分到同一个桶的概率。

内存开销问题：一个 128 维，每维一个浮点数（32 bit，4 byte）的向量需要占用 512 字节空间

用代表点代表类中的所有向量：有损压缩

量化：向量根据码本转化为代表点
- 使用码本记录代表点，记录码本索引值代替记录向量真实值
- 如果我们使用一个字节存储码本索引，最多可以记录 256 个代表点，此后的每个向量只需要一个字节即可表示。
维度灾难问题：每一个维度都会拉远点与代表点的距离，高维非常分散。要保证好的效果，就需要大量聚类，码本开销就十分巨大。
乘积量化PQ：用低维子向量拼接代替高维直接量化，缓解维度灾难问题
- 例如 128 维向量被分割为8 个 16 维向量分别量化，得到结果再拼接。每个子向量有自己的码本。
- 高维结果实际上是低维量化结果的笛卡尔积，所以叫 PQ。
- 从指数增长变成了加法增长。
- 主要减少了内存开销，但是一定程度地提高了速度（ $O(n+k\log k \log\log n)$ ）,与之相比，暴力搜索的时间复杂度是 $O(kn)$ 。
其他降维方法：主成分分析PCA，见多媒体实验2：PCA主成分分析

内存相比于速度和准确度，只能被开发者感知，因此有的时候我们愿意牺牲内存提高ANN的准确性与速度

导航小世界NSW

分层小世界HNSW：

本质是对查询的一种跳表化。

小世界算法：没有压缩 + 维护复杂的图结构 = 内存爆炸

向量数据库依然是数据库，和传统数据库产品一样有许多方面需要考虑：访问接口、访问控制、备份、多节点、容错、机器的监控与追踪……