Research On Online Learning Algorithm Based On Optimized Product Quantization

With the rapid development of computers and the popularization of the Internet,information has exploded on the Internet.The development of information has led to the need for higher dimensions of expression data.In order to react to users more quickly,how to quickly perform matching search and feedback in a massive database in a short time has become a huge challenge at present.Based on this background,some algorithms about approximate nearest neighbor(ANN)have been proposed successively.Among those algorithms,quantization-based technology has achieved great success due to its high search performance,strong expression ability,and small memory space.However,most of the existing quantization methods are batch-based models,which are not suitable for processing streaming data,and the existing online product quantization model do not optimize the space decomposition.In order to solve the above problems,this paper proposes an online optimized product quantization(Online OPQ)model.The model can dynamically update the quantized codebook and rotation matrix,and optimize the space decomposition during the model update stage,which can reduce the quantization error and improve the search performance.Because the online OPQ is essentially an online model,only new data is needed during the update process without historical data.In the parameter initialization stage,an optimized product quantization(OPQ)algorithm is used to initialize the codebook,rotation matrix,and counter.During the updating of parameters,when learning new data,the online OPQ will first rotate the data to the optimal space.In the following,the code books are updated by the calculation process of the K-means algorithm.Then the codebooks of two adjacent batches can be obtained.In order to ensure the optimality of space,this paper proposes to introduce a correction matrix to the rotation matrix.The correction matrix is used to track the change of the center points.In order to ensure the orthogonality of the rotation matrix,the correction matrix also needs to be an orthogonal matrix.The process of solving the correction matrix is exactly the Orthogonal Procrustes problem.By solving this problem,the orthogonality of the correction matrix can be guaranteed.In addition,in order to measure the difference between the online OPQ model and the traditional OPQ codebook,a loss error boundary is theoretically derived.In this paper,a series of comparative experiments are performed with the baseline models on the public datasets.The experimental results show that compared with the baseline models,the performance of online OPQ on approximate nearest neighbor search is more effective.With more subspaces are decomposed,the expressiveness of the codebooks is much stronger and the quantization performance is much better.By tracking the change of center points,this method can optimize the decomposition space which can reduce the quantization error and further improve the search performance.