挖坑不填兽

主成分分析 主成分分析（principal components analysis）是一类非常常见的算法，广泛应用于各种需要信息压缩的场景。虽然《深度学习》一书称之为“简单的机器学习算法”，但是PCA通常可以通过确定的数值算法实现。 概略来说，PCA是找到一个映射算法，将高维空间的样本集合在尽量不损失信息的前提下，映射到更低的维度，从N维空间映射到M维空间，可以表示为一个 $M*N$的矩阵。PCA的目的就是通过分析样本集合，解出这个映射矩阵。 这个求解过程主要有这样几个步骤： 将样本集合表达为$样本数特征数$（$AF$）的矩阵 将这个矩阵规范化，使后续步骤中我们可以得到一个对角线为1的协方差矩阵，这需要先得到无偏的标准差： 我们先求得样本集的均值向量，均值向量的每个维度都是所有样本在该特征维度的值的平均 用样本集减去这个均值向量，得到一组中心化的数据$B$ 对这个集合求平方，然后求和，再除以$A-1$得到无偏方差 开方得到无偏标准差(Unbiased standard deviation)即样本标准差(Samples standard deviation) 。 为了避免样本标准差的某个维度为0，导致后续计算出错，可以给它加上一个极小的正数作为补偿。 用B矩阵除以标准差 得到规范化的矩阵X之后，我们计算 $X^TX$ 将得到的矩阵除以$A-1$，得到$F*F$的协方差矩阵 求解协方差矩阵的奇异值矩阵$S$和右奇异值$VT$向量矩阵，按从奇异值大到小，取对应的前M个向量，组成PCA转换矩阵 使用这个矩阵，对样本做矩阵乘法时，得到的就是降维后的结果向量。 实现 我最初做PCA算法的动机，来自于将 4096 维度的 ollama 嵌入向量降维到 2000 维以下——我的目标是256，那么在这个计算过程中，如果假设样本集数量为一万，计算过程中就会涉及好几次千万级的浮点数乘法。为了加速计算过程，使之可以优化到足以放到 PostgreSQL 内部使用，我使用AI框架 ggml 实现了一个 PCA 方法。 GGML 是一个 C 库，它支持 CUDA、MPX 等硬件加速方案，可以快速处理大规模的矩阵算法。 GGML 的tensor类型支持最多4个张量维度，PCA仅涉及矩阵和向量计算，只需要用到最多两位维度。所以这里仅使用GGML TENSOR的前两个维度。 在前述步骤中，基础的矩阵算法如乘法，加法等都有对应的 GGML... [Read More]

C/C++ 混合编程 这几天踩了一些坑，做个笔记。 两种语言，两个编译器 十多年前，我曾经是个职业的 CPP 程序员，但是那个时候我用 VC，这是一个高度自动化的 CPP 开发环境，它自动的做了太多的工作，以至于我甚至没有注意到自己的很多问题。 理论上，CPP是C的超集，使用 CPP 编译器可以自动的兼容 C 代码。这也导致了有时候我们其实不太注意自己到底在写C还是CPP。甚至很多构建工具允许我们用 CPP 编译器直接编译C 代码。 这在很多项目中是好的功能，不过我还是决定在 tensor dancer 项目中厘清这个问题，让混合编程的过程放到明面上来。 Meson 在默认情况下，使用 C 编译器编译 .c 文件，用 CPP 编译器编译 .cpp 文件。因为前面的理由，我没有将 c 编译器指定为 c++。 这样就暴露出一个问题，如果我在一个 c 程序中 include 一个CPP 头文件，它会递推到相关的 CPP 代码，这就会引发语法错误或符号找不到这样的错误。应对的方式是，定义一个 .h 文件 ，其中仅包含引用符合C标准的导出定义，例如dancer.h的内容是： [Read More]

环境和依赖 我准备围绕几个基础的算法工具，编写一系列算法，最终形成一个高阶的算法库，并提供相关的 PostgreSQL 插件。 这个系列，我们主要依赖三个第三方库，线性代数计算库BLAS、LAPACK和GGML。 BLAS 全称 Basic Linear Algebra Subprograms ，底层基于 Fortran 代码，是众多线性代数库的基石。 LAPACK 全称Linear Algebra PACKage，基于 BLAS 库开发，提供了一些矩阵计算算法实现，例如SDV分解。 我的日常工作在一台 M3 芯片的 Apple MacBook 笔记本上完成，因此这里也主要围绕 MacOS 展开，兼顾 Linux。不过我手头没有 Navida 显卡，也没有 CUDA 的运行环境，这方面的东西无法实验。 开发工具 BLAS 和 LAPACK 本身有系统内置的版本，但是实验来看，连编时会找不到头文件，好在它们也有 homebrew 版本，可以直接安装。但是ggml 要程序员自己编译。因此我们还是从开发工具的准备开始。 首先，我们需要安装 Apple 的开发工具集，这个不多介绍，Apple Store上现在可以直接下载xcode……嗯我大概是这个世界上少数在apple store上花过45块钱买xcode的苹果用户了。现在xcode是个免费软件。 说个好笑的，xcode和 xcode-commandline 的库搜索路径不一样，我也是在编译 llama.cpp... [Read More]

在 PG 中支持矩阵乘法 Tensor Dancer 项目核心目标之一，是在 PostgreSQL 中提供张量计算能力。这里我们从一个最简单的需求开始：支持矩阵乘法，使我们可以对 pgvector 的向量使用 PCA 矩阵降维。 关键代码 将一个n维向量V降到m维，可以简单的理解为用一个 n*m的矩阵 T 乘以 n 的转置， $$ 这是一个非常基本的线性代数算法，在 BLAS 库中提供了通用的矩阵乘法。我们可以简单的调用这个函数。 int mul_matrix_vector_f32(struct Matrix *matrix, float *vector, float *result) { cblas_sgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans, (int) matrix->rows, 1, (int) matrix->columns, 1.0, (float *) matrix->data, (int) matrix->columns, vector, 1, 0.0, result,... [Read More]

一次不成功的 pull request 昨天，我向 pgvector 提交的一个降维算法被拒绝了 Submit a simple vector dimensionality reduction function 。 这个结果对我来说，并不意外。顶多算是略有遗憾。我习惯使用ollama ，而ollama的embedding接口返回的是4096维度，远大于PGVector索引支持的最大维度2000。关于这个问题，我第一个想法是修改PGVector的维度限制，不过这个issue很快被拒绝了 Increased max dimensions for index from 2000 to 4096 。原因也很简单，PGVector这个限制其实来自PostgreSQL，PG的索引页最大为8K，所以PGVector的索引维度最大不能超过2000。 在此之后，我就开始尝试实现一个实用的降维算法。 一般来说，PCA（主成分分析）总是被首先推荐的，这玩意儿甚至是花书的一个重要示例。但是我并没有将 PCA 作为首选。这是因为： PCA 基于样本空间进行降维，但是我希望首先有一个不依赖预备知识，可以直接对任意向量进行降维操作的算法。 当然，完全零知识的前提下是无法有效降维的，我希望的是首先找到一个足够简单，但是对 ollama 的嵌入向量有效的压缩算法，可以将这些 4096 维的向量压缩到 256甚至更低的维度，但是仍然可以足够有效的用于 RAG 应用。如果能做到第一步，再继续尝试对其它类似的embedding向量构造算法。这样我就可以无状态的使用它。 PGVector并不是一个很大的项目，我希望我的降维算法也足够简单，可以不依赖很重的外部资源，使用朴素的c语言实现。而PCA需要计算协方差和特征值或奇异值矩阵，这需要引入LAPACK和BLAS库，或者自己写出相关的算法。 因此，我尝试了一些朴素的，甚至可以说是非常朴素的算法。例如对m维降到n维的，直接用 n/m 划分原向量，再对每一组取平均值（我称之为norm 或 integral reduce）。再比如先算出相邻维度的差分，然后找到前n-1个最大的差分，以此为边界将原向量分割为n份，再求平均值——我称之为diff reduce——这多少有点儿像PCA，没办法，对一个向量（1xN矩阵），实在没办法求特征值，我看到的同行的实现，都是加入了一些白噪声维度再计算PCA，而这比我期待的还是重了一些。 我的意思是，关于PG的浮点数计算，我有很多有野心的想法，但是目前我希望写出一个足够小的函数，可以让PGVector社区毫无压力的接受它。所以我重点实验了一下几种不需要样本数据集，不需要引入额外维度，不需要ggml，也不需要lapack之类的算法库支持的微型算法。 很意外，效果最好的，居然是最简单的按固定区间分组求平均值的算法——我称之为... [Read More]