Milvus 核心设计 （4） ---- metric及index原理详解与示例(2)

目录

背景

Binary Embedding

定义与特点

常见算法

应用场景

距离丈量的方式

Jaccard

Hamming

代码实现

Index

BIN_FLAT

BIN_IVF_FLAT

Sparse embeddings

定义

应用场景

优点

实现方式

距离丈量方式

IP

Index

SPARSE_INVERTED_INDEX

应用场景

优势

SPARSE_WAND

工作原理

性能特点

应用场景

小结

背景

接着上面的Milvus metric 及index 继续写下剩余的两种方式。这样对于 vector db 的metric 及index 你将全面理解并学会使用。因为当你看完 Chroma 源码，再看Milvus 时，某些时候总会产生共鸣，虽然两个都是很优秀的开源vector db，来自不同的设计团队，但是你总能感受到来自底层 design 的共鸣。比如对于 HNSW 算法，设置M，efConstruction，ef 都是不变的旋律。或许高手忘掉所有招式，只重其意，不看其形，那就能自创门派了。

Binary Embedding

顾名思义，就是二进制嵌入，说直白点就是只有 0 与 1 的编码。这里不是指计算机底层硬件表示，无论如何目前都是0 与 1 的存储，是指上层应用转换为了一组0 与 1 的 向量存储。

简单来说，二进制嵌入是嵌入技术中的一种，它主要将高维数据转换为低维的二进制向量表示。这种表示方法具有存储效率高、计算速度快等优点，因此在许多领域，如信息检索、推荐系统、图像识别等中得到了广泛应用。以下是对Binary embeddings的详细解释：

定义与特点

• 定义：Binary embeddings是指将原始数据（如文本、图像等）通过某种算法转换成固定长度的二进制向量（即只包含0和1的向量）的过程。
• 特点：
  • 高效存储：二进制向量比浮点数向量占用更少的存储空间，有利于大规模数据的存储和处理。
  • 快速计算：二进制向量的计算（如汉明距离计算）通常比浮点数向量的计算更快，有利于提升算法的效率。
  • 简化模型：二进制嵌入可以简化机器学习模型的复杂度，使得模型更加易于理解和实现。

常见算法

• Locality-Sensitive Hashing (LSH)：是一种基于哈希的算法，通过设计一种哈希函数，使得相似的输入数据经过哈希后得到的哈希值也相似。LSH常用于大规模数据的近似最近邻搜索。
• Iterative Quantization (ITQ)：是一种通过迭代优化过程将浮点数向量转换为二进制向量的算法。ITQ旨在最小化转换后的二进制向量与原始浮点数向量之间的欧氏距离。
• HashNet：是一种基于深度学习的二进制嵌入算法，通过训练神经网络来学习从原始数据到二进制向量的映射关系。HashNet可以捕获数据中的复杂结构，并生成高质量的二进制嵌入。

应用场景

• 信息检索：在搜索引擎中，可以将查询和文档都转换为二进制向量，然后通过计算向量之间的相似度（如汉明距离）来快速找到与查询相关的文档。
• 推荐系统：在推荐系统中，可以将用户和物品表示为二进制向量，并通过计算用户向量和物品向量之间的相似度来推荐用户可能感兴趣的物品。
• 图像识别：在图像识别领域，可以将图像特征转换为二进制向量，并通过比较向量之间的相似度来进行图像

所以实际上前面介绍的 float embedding 可以转换为 binary embedding。看下 milvus 怎么丈量其距离。

距离丈量的方式

Jaccard

定义
Jaccard距离（Jaccard Distance）或Jaccard相似系数（Jaccard Similarity Coefficient）是一种度量两个集合之间相似性或差异性的方法。它定义为两个集合交集的大小除以两个集合并集的大小。

表达式
假设有两个集合A和B，Jaccard相似系数J(A,B)的表达式为：
[ J(A,B) = \frac{|A \cap B|}{|A \cup B|} ]
其中，(|A \cap B|)表示集合A和集合B的交集的大小，(|A \cup B|)表示集合A和集合B的并集的大小。

Jaccard距离则是通过1减去Jaccard相似系数来计算的，即：
[ \text{Jaccard Distance} = 1 - J(A,B) ]

应用场景
Jaccard相似系数和距离广泛应用于多模态数据处理、文本挖掘、生物信息学等领域。在多模态数据处理中，它可以帮助度量两个不同类型数据之间的相似性，实现数据融合和挖掘。在文本挖掘中，它可以用于计算两个文档集合之间的相似度。

特点

• 只能应用于有限的样本集。
• 对集合中元素的顺序不敏感。
• 适用于二元数据或布尔数据。

主要是用在集合比较上面。

Hamming

定义
Hamming距离（Hamming Distance）是一种用于度量两个等长字符串（或等长向量）之间差异性的方法。它定义为两个字符串对应位置上不同字符的个数。

计算方式
对于两个等长字符串（或等长向量）a和b，Hamming距离的计算方式为：比较字符串（或向量）的每一位是否相同，若不同则Hamming距离加1，直到比较完所有位。

表达式
假设有两个等长字符串a和b，Hamming距离d(a,b)的表达式可以表示为：
[ d(a,b) = \sum_{i=1}^{n} \text{XOR}(a_i, b_i) ]
其中，n是字符串（或向量）的长度，(\text{XOR}(a_i, b_i))表示a和b在第i位上的异或运算结果（0或1）。

应用场景
Hamming距离广泛应用于信息传输、数据压缩、密码学等领域。在信息传输中，它可以用来检测数据传输过程中的错误。在数据压缩中，它可以用来评估压缩算法的效果。在密码学中，它可以用来评估加密算法的强度。

特点：

• 适用于等长字符串（或等长向量）。
• 对字符串（或向量）中元素的顺序敏感。
• 适用于二进制数据或可以转换为二进制表示的数据。

Jaccard和Hamming是两种不同但互补的度量方法，Jaccard更侧重于集合之间的相似性或差异性度量，而Hamming则更侧重于等长字符串（或等长向量）之间的差异性度量。

代码实现

FieldSchema(name='binary_embedding', dtype=DataType.BINARY_VECTOR, description='binary_embedding vector values', dim=dim)

# 定义索引参数
index_params = {
    'metric_type': 'BIN_FLAT',
    'index_type': 'Jaccard'
}

# 在embedding字段上创建索引
collection.create_index(field_name='embedding', index_params=index_params)

Index

BIN_FLAT

BIN_FLAT是Milvus中针对二进制embedding的一种简单的索引类型。它类似于FLAT索引，但没有进行任何形式的压缩或优化，直接存储了所有的二进制向量。

它没有进行任何压缩，它可以保证搜索的精确性，但可能会占用较多的存储空间，并且查询速度相对较慢，尤其是在处理大规模数据集时。

适用于对准确率要求极高且数据集规模相对较小的场景。

BIN_IVF_FLAT

BIN_IVF_FLAT是Milvus中针对二进制embedding的一种基于IVF（Inverted File）的索引类型。它将向量数据划分为多个聚类（cluster），并为每个聚类构建Flat索引。在搜索时，首先找到与目标向量最相似的聚类，然后在该聚类内部进行进一步的搜索。其实和 vector embedding 在 IVF_FLAT上的处理类似。

相比于BIN_FLAT，BIN_IVF_FLAT通过聚类的方式显著降低了查询时间，特别是在处理大规模数据集时。然而，它可能会牺牲一定的准确率，因为搜索结果被限制在了最相似的聚类内部。

适用于需要快速查询且可以接受一定准确率损失的大规模二进制embedding数据集。

Sparse embeddings

稀疏嵌入是机器学习和深度学习领域中的一个重要概念，特别是在处理大规模数据集和复杂模型时。先简单介绍下concept。

定义

Sparse embeddings是指向量中大部分元素为零，只有少数元素非零的嵌入表示。这种表示方式在利用矩阵运算上具有显著的优势，因为它可以大幅减少所需的计算量，并行计算粒度会提高。

应用场景

Sparse embeddings在多个领域都有广泛的应用，包括但不限于：

1. 自然语言处理（NLP）：在NLP任务中，如文本分类、情感分析、问答系统等，词嵌入（word embeddings）是常用的技术。对于大规模词汇表，使用稀疏嵌入可以减少模型的参数量和计算复杂度。

2. 推荐系统：在推荐系统中，用户和物品的嵌入表示是核心。由于用户和物品的数量可能非常庞大，使用稀疏嵌入可以有效地降低存储和计算成本。

3. 搜索系统：在搜索引擎中，文档和查询的嵌入表示对于提高检索效率至关重要。稀疏嵌入可以通过构建倒排索引等方式，实现高效的检索。

优点

1. 存储效率高：由于大部分元素为零，稀疏嵌入可以大幅减少存储空间的占用。

2. 计算速度快：在进行矩阵运算等操作时，稀疏嵌入可以减少不必要的计算，从而提高计算速度。

3. 可扩展性强：稀疏嵌入能够处理大规模数据集，适用于需要处理海量数据的场景。

实现方式

Sparse embeddings的实现方式多种多样，但核心思想是通过某种方式生成稀疏的向量表示。以下是一些常见的实现方式：

1. 哈希技巧：通过哈希函数将高维空间中的点映射到低维的稀疏空间中。这种方法简单易行，但可能会存在哈希冲突的问题。

2. 稀疏编码：利用稀疏编码算法（如LASSO、稀疏自编码器等）生成稀疏的嵌入表示。这种方法能够保留数据的重要特征，同时去除冗余信息。

3. 预训练模型：利用预训练模型（如BERT、GPT等）生成词嵌入或句子嵌入，并通过某种方式（如剪枝、量化等）将其转换为稀疏嵌入。这种方法能够充分利用预训练模型的优势，同时降低存储和计算成本。

距离丈量方式

IP

就是向量积，前面介绍 vector db 时已经详细介绍过了。原理也很简单，存储结构也定了matrix在sparse matrix 上运算特别合适。

Index

SPARSE_INVERTED_INDEX

• 稀疏倒排索引是一种针对稀疏向量的索引结构，它主要用于加速在稀疏向量空间中的搜索过程。
• 在这种索引中，每个维度都维护一个向量列表，这些向量在该维度上具有非零值。当进行搜索时，系统会遍历查询向量的每个维度，并计算在这些维度中具有非零值的向量的分数。

应用场景

• SPARSE_INVERTED_INDEX 特别适用于处理那些维度数量远大于非零元素数量的稀疏数据集。
• 在文本处理、推荐系统、搜索引擎等领域中，由于数据通常具有高度的稀疏性，因此 SPARSE_INVERTED_INDEX 得到了广泛的应用。

优势

• 提高了在稀疏向量空间中的搜索效率。
• 减少了不必要的计算，因为系统只关注那些非零值所在的维度。

SPARSE_WAND

• eak-AND 算法优化的稀疏索引）是在 SPARSE_INVERTED_INDEX 的基础上进行的一种优化算法。
• 它利用 Weak-AND 算法在搜索过程中来进一步降低全 IP（内积）距离评估的数量，从而提高搜索速度。

工作原理

• 在搜索过程中，SPARSE_WAND 会首先根据某种策略（如基于向量的稀疏性）对候选向量进行筛选。
• 然后，它会对筛选后的向量进行更精细的评估，以确定最终的搜索结果。

性能特点

• SPARSE_WAND 在速度方面通常优于其他方法，特别是在处理大规模稀疏数据集时。
• 然而，其性能可能会随着向量密度的增加而迅速恶化。为了解决这个问题，可以引入非零 drop_ratio_search 参数来显著提升性能同时只产生最小的精度损失。

应用场景

• SPARSE_WAND 特别适用于对搜索速度有较高要求且数据集较为稀疏的场景。

小结

实际上用的最多的还是 floating embedding，因为无论是LLM，图片，audio 还是  video，我们常用的做法一般都是embedding后进行归一化操作，归一化后的结果必然是 floating，只是说在有的地方这个floating是有机会转为 binary 进行计算的，在还有的case就是他确实可以用稀疏matrix 来完成。所以无论如何，场景决定了代码的选择。

floating embedding 不明白的 看上一篇文章

Milvus 核心设计 （3） ---- metric及index原理详解与示例(1)-CSDN博客