转载

ITQ迭代量化方法解析

一.问题来源

来源于换关键字，从LSH转换为hash检索，这要感谢李某。

二.解析

笔者认为关键思想是数据降维后使用矩阵旋转优化，其他和LSH一样的。

2.1 PCA降维

先对原始空间的数据集 X ∈ R n × d 用PCA进行降维处理，设经过PCA降维后的数据集为 V ∈ R n × c ，该问题就可以转化为将该数据集中的数据点映射到一个二进制超立方体的顶点上，使得对应的量化误差最小，从而而已得到对应该数据集优良的二进制编码。

对于PCA降维部分，不做详解。设 v ∈ R c 为原特征空间中某一数据点经过PCA降维后的表示形式，对应在超立方体中的顶点用 s g n ( v ) ∈ { − 1 , 1 } c 来表示，要使量化误差最小，即 v ∈ R c 与 s g n ( v ) ∈ { − 1 , 1 } c 的欧式距离最小，即 m i n | | s g n ，对于所有的数据点进行二进制编码后用B表示，PCA降维后 V = X × W ，对整个数据集为 m i n | | B − V | | 2 。由于对矩阵进行旋转可以降低量化误差。

2.2 ITQ优化求解

对投影后的矩阵V进行随机旋转后，量化误差降低至0.93，对于找到的最优的旋转矩阵，量化误差降低至0.88(矩阵与正交矩阵相乘实际上就是对矩阵做旋转)。基于这样一个事实，考虑将投影后的数据集V进行旋转变换， m i n | | B − V | | 2 便变换为 m i n | | B − V R | | 2 ，R为旋转矩阵。整个问题域就变成了 m i n | | B − V R | | 2 的优化问题，即找出最优的旋转矩阵R和与之对应的编码B。该式的优化可以采用交替跌倒的求解方法：先生成随机矩阵并对其进行SVD分解得到对应的正交矩阵作为R的初始值，然后固定R求B， B = s g n ( V × D ) （注意这里截距 b = 0 ,因为在原空间已对数据中心化，非常重要）,B求出来再通过对 B × V 进行SVD更新R，交替迭代若干次即可，文中选用的是50次。