算法 - AI中的向量计算思维导图模板_ProcessOn思维导图、流程图

向量运算

相关用途

简化索引

计算归一化，提高准确性

定义

范数是一个函数，记作∥⋅∥，它将一个向量（或矩阵、函数）映射为一个非负实数，表示其“大小”或“长度”。

形式上，设 V是一个向量空间，一个函数称为范数

重要三个性质

正定性： ∥x∥ ≥ 0

齐次性：∥αx∥ = ∣α∣ ⋅ ∥x∥ ∥αx∥=∣α∣⋅∥x∥，对任意标量α∈R

三角不等式： ∥x+y∥ ≤ ∥x∥ + ∥y∥

常见的范数类型

1. 向量范数（Vector Norms）

设 x = (x1, x2, …, xn) xi∈Rn 是一个向量。

L¹ 范数（1-范数，曼哈顿范数）

||x||₁ = |x₁| + |x₂| + ... + |xn|

意义：表示向量各个分量绝对值的和，常用于稀疏性建模（如Lasso回归）。

L² 范数（2-范数，欧几里得范数）

意义：表示向量从原点出发的欧几里得距离，也是我们常说的“模长”。

用途：

有旋转不变性 (Rotation Invariance)；计算涉及平方和开方；

在优化问题中通常能产生光滑的解；

是主成分分析 (PCA)、支持向量机 (SVM)、机器学习正则化 (Ridge 回归) 等的基础

L∞ 范数（无穷范数）

意义：表示向量中绝对值最大的那个分量，常用于最大误差分析。

几何上表示所有坐标方向投影中最大的那个长度

Lp 范数（p-范数）

意义：

Lp 范数是 L¹、L²、L∞ 的一般化形式。

p 越大，越强调大分量的贡献。

p 值越小（特别是 p=1），范数对向量中较小元素（包括零）越敏感，越容易产生稀疏解。

2. 矩阵范数（Matrix Norms）

设A∈Rm×n 是一个矩阵。

Frobenius 范数（弗罗贝尼乌斯范数）

意义：将矩阵看作一个向量，计算其 L² 范数。

用途：常用于矩阵逼近、图像处理等。

谱范数（Spectral Norm）

意义：表示矩阵对向量长度的最大拉伸倍数，常用于稳定性分析。

(A) 是矩阵 A 的最大奇异值。

3. 函数范数

函数范数是泛函分析中的核心概念，它将向量范数的思想推广到了函数空间（由函数构成的线性空间）上

基本意义

用于衡量函数的“大小”或“强度”。它在分析微分方程、逼近理论、数值分析、信号处理、优化等领域至关重要。

函数范数 (Function Norm)：定义在函数空间X上的一个实值函数 || · || : X → [0, ∞)，满足以下公理（与向量范数公理类似）：

基本性质，类似向量

非负性 (Non-negativity)：对所有 f ∈ X, ||f|| ≥ 0。

确定性 (Definiteness / Point-separating)： ||f|| = 0 当且仅当 f = 0 (在函数空间中，“0”通常指几乎处处为零的函数，特别是在Lᵖ空间中)。

齐次性 (Homogeneity / Absolute scalability)：对所有标量 α 和 f ∈ X, ||αf|| = |α| · ||f||。

三角不等式 (Triangle Inequality / Subadditivity)：对所有 f, g ∈ X, ||f + g|| ≤ ||f|| + ||g||。

(有时还要求相容性，特别是当空间有乘法结构时，但基本定义只需要以上四条)。

向量索引方案

以下介绍的索引算法都与索引构建和数值查询优化息息相关

在 Fassi, Mulvis, PG, ES 等各类数据库中都有广泛应用。

通常向量维度 D 很高，数据条数 N 很大，所以为了高效召回，引入索引算法优化。

通常步骤

索引文件的构建 Build

索引文件使用初始数据前训练 Pretrain

索引添加 Add

索引的查询 Search

brute-force,

对于每个查询向量，计算它与数据库中所有向量的距离（L2 或内积），然后返回距离最小的 k 个。

算法分析

构建时间 (build_time): O(1)。只是将向量添加到数组末尾，常数时间。

搜索时间 (query_time): O(n * d)。n 是数据库大小，d 是向量维度。必须计算 n 次 d 维度的距离。

如果 N=10000, D=128

最原始的暴力计算则有 O(N * D) = 10000 * 128

内存占用 (memory): O(n * d)。存储所有原始向量。

精度

100% 精确。返回的是真实的最近邻。

Inverted File System, 简称IVF.

使得查询 query vector 只在相关感兴趣的子空间进行，不关注全空间，所有对子空间倒排序

背景

如果 N=10000, D=1280

所有向量计算的时候相互都需要在 D 个维度上进行计算

整个样本 N 查询时间和计算太消耗资源

设计 (倒排文件)

训练 (Training): 使用 k-means 聚类算法在训练数据上训练一个码本 (codebook)。码本包含 nlist 个聚类中心 C（centroids）。

构建 (Building): 对于数据库中的 N 个向量 x，计算它到所有 centroids 的距离，将其分配到距离最近的 centroid 倒排列表 (inverted list) 中。

搜索算法

粗量化 (Coarse Quantizer): 对于查询向量 q，计算它到所有聚类中心 centroids 的距离。

选择倒排列表 (Probe Lists): 在一共 nlist 个倒排列表里，选择距离 q 最近的 C。

其中（nprobe << nlist << N）

精细搜索 (Fine Search): 只在这 nprobe 个对应的倒排列表中进行穷举搜索（在这些子集上做 brute force）。合并结果，返回全局 k-NN。

算法复杂度分析

构建时间

主要是聚类时间，迭代 T 次O(T*N*D*C) + 构建时间 O(N*D)

搜索时间

选择倒排列表 O(D*nlist) * 平均倒排索引中向量计算 O(D*N/nlist)

内存占用

可以只多存聚类中心 O(N*D + C*D) 在内存中，便于在相关空间取倒排计算。

Product Quantizer, 简称PQ.

矢量量化方法，即vector quantization，其具体定义为: 将向量空间的点用一个有限子集来进行编码的过程。

常见的聚类算法，都是一种矢量量化方法。而在 ANN 搜索问题中，向量量化方法又以乘积量化(PQ, Product Quantization)最为典型。

索引算法

设有 N 个 D=128 维的向量需要索引，考虑引入参数 M，C 来对向量分段，和使用 Clustering 来计算分段向量空间的簇心。

在 Pretrain 的时候，如有 M=4 向量将被分成4段，在 C=256 时所有N向量做4次聚类，计算每段的256个簇心。

簇心应该是 M=4, C=256 的矩阵 centers.shape = (4, 256, 32)，然后可以Assign各个向量

然后 Add 把原来的 N 维的向量映射到 M 个数字，然后对于每一段向量 D=128 维的向量就变成了一个由 M=4 个ID组成的向量

比如的库里的某个向量被量化成了 [124, 56, 132, 222]， vectors.shape = (N, 4)

最后 Search 的时候，先把128维也分成 M 段向量，然后计算每一段向量与之前预训练好的簇心 C=256 的距离，得到一个4*256 的表

4组和256个簇心的距离，query.shape = (256, 4)

查表得到查询向量第一段子向量与其ID为124的簇心的距离，然后再查表得到查询向量第二段子向量与其ID为56的簇心的距离。。。最后就可以得到四个距离d1、d2、d3、d4，查询向量跟库里向量的距离d = d1+d2+d3+d4。

算法复杂度分析

搜索时间

优化计算向量次数是分段*子空间中簇心 O(M * C * N/nlist) 次，则固定为 4 * 256 次小分段向量的计算

对于 N 个向量，只要执行 4N 次子向量簇心距离的查表，不需要计算

潜在问题

PQ优化了向量距离计算的过程，但是假如库里面的向量特别多，依然逃不了一个遍历整个库 N 个向量的过程

倒排乘积量化，简称IVFPQ

IVF with PQ (IndexIVFPQ): 设计结合 IVF 和 PQ 这是最常用、最具代表性的索引之一。

设计算法

对库里所有向量做KMeans Clustering，构建簇心个数 C (centroids) 的聚类

IVF (Inverted File System) 找到距离 q 最近的 nprobe 个 centroids。

PQ (Product Quantization): 核心压缩技术。将 d 维向量划分为 M 个 D/M 维的子向量。

一个向量 x 被量化成一个由 M 个索引（0-255）组成的 PQ 编码 (code)。

在计算查询向量和一个簇底下的向量的距离的时候，所有向量都会被转化成与簇心的残差，提高准确性

对残差进行 PQ 编码（通常效果比直接对原始向量做 PQ 好）。查询时也计算查询点到 centroid 的残差 q - centroid。

索引算法

找到距离 q 最近的 nprobe 个 centroids。

计算查询残差: 对每个选中的 centroid，计算 q_residual = q - centroid。

非对称距离计算 (ADC - Asymmetric Distance Computation): 这是 PQ 搜索的关键优化。不重构数据库向量。

对于目标倒排列表中的每个 PQ 编码（代表一个数据库向量 y 的残差），计算 q_residual 到 y 的 PQ 近似距离：

将 q_residual 划分为 m 个子向量。

对每个子空间 s，预计算 q_residual 的第 s 个子向量到该子码本所有 k (256) 个中心点的距离，得到一个大小为 (m, k) 的距离表 (lookup table, LUT)。

数据库向量 y 的 PQ 编码指定了它在每个子空间选择的中心点索引 idx_s。

近似距离 = sum_{s=0}^{m-1} LUT_s[idx_s]。

在选定的 nprobe 个倒排列表中执行上述 ADC 计算，找出 k-NN。

算法复杂度分析

构建时间

非常高。包括训练 IVF 的 k-means、训练 PQ 的 m 子空间中 PQ 子码本

搜索时间

IVF的时间 O(D*C) + 计算相关类nprobe个的q_residualO(d * nprobe) + PQ乘积向量化时间 O(m * nprobe * (n / nlist) )

场景

nprobe: 越大，搜索的列表越多，精度越高，越慢。

m: PQ 子空间数。m 越大，量化越精细，精度越高，存储和计算量略增。

ks: PQ 子码本大小（固定为 256）。量化误差主要来源。

大规模高维向量搜索的主力军。在内存消耗、搜索速度和精度之间提供了极佳的平衡。十亿级向量搜索的常见选择。

可导航小世界图，简称HNSW

设计

构建一个多层图结构。底层（层0）包含所有数据点。上层是下层的稀疏采样。

每层是一个 NSW (Navigable Small World) 图：具有“小世界”属性（平均路径短）和“可导航性”（邻居指向空间上更远的点，便于长跳）。邻居通过启发式算法（如选择距离近且能显著增加覆盖的点）连接。

构建过程：随机分配新点到一个最大层 L。从最高层开始，贪心搜索找到该层最近邻，将其作为入口点。然后逐层向下，在每一层贪心搜索找到近邻，并将该点连接到该层找到的一定数量的最近邻（不超过 M 个）。

搜索算法

从最高层的入口点开始（通常只有一个）。

贪心搜索：在当前层，从当前点出发，不断移动到其邻居中距离查询点 q 更近的点，直到无法再更近（局部最小）。

下钻：移动到下一层（更低一层），以上一层找到的局部最小点作为该层的起始点，重复贪心搜索。

重复步骤 2-3，直到达到最底层（层0）。在最底层进行贪心搜索，找到局部最小点及其邻近点作为候选。

维护一个动态候选列表（通常用优先队列），最终返回列表中距离 q 最近的 k 个点。搜索时通常设置 efSearch 参数限制候选集大小。

适用场景

精度非常高，通常优于 IVF 和 PQ 类方法（尤其在小 k 时）。

精度由 efSearch 控制，efSearch 越大，搜索越彻底，精度越高，越慢。

需要超高精度和超低延迟（毫秒级）的搜索场景，尤其是中小规模数据集（百万级）。对内存消耗相对不敏感。

构建时间长是其缺点。常作为 IVF 系统的第二级精排。

数学重要分支介

代数

线性代数

向量空间

向量运算

线性相关性

线性变换

特征值与特征向量

基与维数

矩阵理论

矩阵运算

矩阵分解

特征值与特征向量

行列式

抽象代数

群论

群的定义与性质

子群与陪集

同态与同构

循环群与置换群

环论

环的定义与性质

理想与商环

多项式环

整环与域

数论

初等数论

整除与素数

同余理论

费马小定理

欧拉定理

解析数论

黎曼ζ函数

素数分布

模形式

狄利克雷级数

几何

欧几里得几何

平面几何

三角形性质

圆的性质

相似与全等

勾股定理

立体几何

多面体

球体与圆柱

体积与表面积

空间向量

非欧几何

欧几里得空间的特点是满足平行公设（即两条平行线永不相交），而非欧几里得空间则不满足这一公设。主要分为两类：

双曲几何

平行公设

双曲三角形

庞加莱圆盘模型

测地线

椭圆几何

球面几何

椭圆三角形

黎曼几何

曲率

1. 黎曼几何（Riemannian Geometry，正曲率空间）

例子：球面（如地球表面）。

特点：

三角形内角和 > 180°。

平行线最终会相交（如经线在极点相交）。

应用：

广义相对论（时空弯曲）。

计算机图形学（曲面建模）。

2. 双曲几何（Hyperbolic Geometry，负曲率空间）

例子：马鞍形曲面。

特点：

三角形内角和 < 180°。

平行线可以无限远离。

应用：

网络科学（某些社交网络结构）。

计算机视觉（非平面图像分析）。

分析

微积分

微分学

导数与微分

极值与最值

泰勒展开

中值定理

积分学

不定积分

定积分

重积分

曲线与曲面积分

实分析

测度论

勒贝格测度

可测函数

积分理论

收敛定理

泛函分析

巴拿赫空间

希尔伯特空间

线性算子

谱理论

概率与统计

概率论

基础概率

概率空间

条件概率

独立性

随机变量

随机过程

马尔可夫链

泊松过程

布朗运动

鞅论

统计学

描述统计

数据可视化

集中趋势

离散程度

分布形态

推断统计

参数估计

假设检验

回归分析

数据工具

梳理运营方案的思维导图及流程图工具

processon

随手记录运营想法的工具

印象笔记

编辑活动宣传文案的工具

秀米

录屏工具

GifCam

图片处理工具

光影魔术手

图形设计工具

创客贴

二维码生成器

草料二维码

数据分析

行业资讯

了解互联网行业趋势和报告的工具

艾瑞网

了解互联网行业新闻资讯

36氪

调研用户的问卷调查工具

问卷星

麦客表单

用户行为分析工具

神策数据

诸葛io

研究关键词搜索趋势及用户画像的工具

百度指数

了解追踪竞品数据的工具

酷传

素材收集

收集图片素材

昵图网

花瓣网

站酷

新闻素材收集

微博

好奇心日报