基于优化的乘积量化的在线学习算法研究

发布时间：2021-03-06 00:54

　　随着计算机的快速发展以及互联网的迅速普及,信息在互联网上爆发式增长,文本、图像、音频、视频等的发展导致表达数据需要更高的维度。为了更快速地对用户做出反应,如何在短时间内快速地在海量的数据库内进行匹配搜索并进行反馈,成为目前巨大的挑战。基于此背景下,近似最近邻（ANN）相关的算法被相继提出。其中,基于量化的搜索技术由于搜索性能高,表达能力强,占用内存空间小等优点取得了巨大的成功。但是,大多数现有的量化方法都是基于批次的模型,不适合处理流式数据,且现有的在线乘积量化模型没有对空间分解进行优化。为了解决上述问题,本文提出了一种在线优化的乘积量化（Online OPQ）模型。该模型可以动态更新量化码本和旋转矩阵,在模型更新阶段对空间分解进行优化,降低了量化误差,提高了搜索性能。由于在线OPQ本质上是一个在线模型,故在更新过程中只需用到新数据而不需要历史数据。在参数初始化阶段,采用优化的乘积量化（OPQ）算法,对码书、旋转矩阵以及计数器进行初始化,在后续参数更新过程中,当学习新数据时,在线OPQ会先将数据旋转到最优空间上,随后利用Kmeans算法的计算过程对码书进行更新,更新后便可以得到相邻的两... 

【文章来源】：电子科技大学四川省 211工程院校 985工程院校 教育部直属院校

【文章页数】：64 页

【学位级别】：硕士

【部分图文】：

k-d树特征空间划分对于一般低维的情况下，k-d树在近似最近邻上搜索较为高效

电子科技大学硕士学位论文10言，用二进制表示的话只需要4bits即可。即通过将整个空间划分为16份以后，原始空间上的每个数据都可以用4bits大小的存储空间表示，而原始的若干个数据点，在进行矢量量化后，可以仅存储16个中心点的向量以及每个数据点的索引即可，大大减小了存储空间。图2-1矢量量化空间中心点根据这样划分的子空间中每个子空间均有若干个数据，便可以计算每个子空间的中心点，在图中用黑色圆圈标注，中心点的坐标可以用对应子空间的数据点的期望得到。则在量化空间中，对于任意一个原始数据，都可以用中心点代替原数据，但显然，中心点毕竟不是原始数据，在计算任意两点之间的距离时，如果只用中心点代替进行计算的话，会存在一定误差。但同样的，这样量化的优点是可以只保存中心点的坐标以及子空间的编号，而不用保存所有的数据点。那么无论有多大的数据集，均可以用这16个中心点的坐标以及4bits的索引代替，这样便大大减少了存储空间，在计算任意两个数据点之间的距离的时候，可以通过预先计算任意两个中心点之间的距离来生成一个查询表，随后在计算距离的时候可以通过查询该表快速的获得结果。计算中心点的方法便是利用K-means聚类得到。但是在海量数据的情况下，原始数据与量化后中心点之间仍然存在一些距离，这样的距离便是损失误差，即量化后的数据与真实数据之间的差距。矢量量化便是以优化损失误差为目标函数所提出的量化方法。矢量量化的目标函数为：

电子科技大学硕士学位论文12min1",1#,…,1$?H!IJ1(!)KH#&,2.3. I∈S=S"×S#×…×S,(2-2)其中，C为M个子码书S",…,S,的笛卡尔乘积。同样的，1()为编码函数，表示将数据量化到相应的中心点上，并返回中心点的索引值。I()为解码函数，即将中心点的索引值作为输入，返回对应子空间上中心点的具体向量。上式目标函数将原始数据的子向量和相应子码书中心点之间的损失。而该式的解决方法为：对原始数据x，按照预先规定的M，将数据切分成维数相等的子向量，随后对每个子空间上做K-means后得到M个子码书，根据编码函数和解码函数，可以计算出原始数据对应的中心点。M个子码书保存了M个空间上的中心点，原始数据对应的中心点可以用索引表示。同样的，假设每个子空间上聚类为k个中心点，则可以用log#Lbits表示k个索引，在大大减少了存储空间的基础上，与矢量量化相比，乘积量化通过子码书之间的笛卡尔乘积，可以得到L,个中心点，大大减小了量化误差损失。图2-2矢量量化子空间聚类为了方便理解乘积量化的定义式，现将利用码书将定义式进行改写：min1,4%?‖!-SW-‖#-∈!(2-3)


本文编号：3066157