毕业生知识库

1. 针对流式数据的哈希函数学习问题，本文提出了一种基于数据素描(data sketching)的在线哈希学习方法。实际检索系统中数据通常以流式的形式出现。然而，大多数现有的哈希方法都假设训练数据是事先给定且不会发生变化的，因此很难有效地处理实际问题中的流式数据。本文通过数据素描方法在线地为流式数据维护一个很小的素描，然后基于该素描进行哈希函数学习。为了保持哈希学习过程中数据的零均值特性，本文还提出了一种新的零均值素描方法，并从理论上证明了该素描方法能够保持数据中哈希学习所需要的主要特性。

 

2. 针对分布式数据的哈希函数学习问题，本文提出了一种分布式哈希方法。我们引入了一种基于最小化量化误差的集中式哈希学习模型，并基于该模型设计了一套分布式哈希学习框架。通过引入一致性约束，本文对集中式哈希模型进行形式上的分解，并通过ADMM算法对分解后的模型进行分布式求解。实验证明该求解方法能很快地收敛到一个较好的解。本文提出的分布式算法没有对网络做任何假设，因此可以适用于任意网络拓扑结构。另外，在整个训练的过程中各个计算节点间只需要交换一些中间变量而无需交换训练数据，因此本文方法的通信代价非常小。

 

3. 为了解决基于矩阵特征值分解的哈希方法中长编码噪声大、性能低的问题，本文提出了基于集成学习的哈希方法。该方法仅通过信息量最大的若干个特征向量生成短的哈希编码，然后将多段短编码串联成长编码。为了保证各段短编码间的多样性，本文借鉴了两种著名的集成学习方法，即Bagging算法和随机子空间算法，分别在样本空间和特征空间中随机采样，得到BPCAH和RPCAH两种哈希方法。本文将提出的方法和著名的LSH算法进行类比，并从理论上证明了基于本文方法生成的哈希编码性能会随着编码长度的增加而增强。

 

4. 为了加速三维重建中的图像匹配过程，本文提出一种层级哈希算法。本文将图像匹配问题抽象成搜索问题，通过哈希方法将图像的特征点从欧式空间映射到汉明空间，然后在汉明空间中进行快速匹配。本文提出的层级哈希算法通过多表哈希查找、哈希重投影以及快速哈希排序三层结构来实现由粗到细的搜索过程。本文详细分析对比了层级哈希算法和其它匹配方法的时间复杂度。在精度相当的情况下，层级哈希算法的匹配速度可以达到目前三维重建中最常用的$Kd$-tree方法的10倍以上。

1. We propose a novel online hashing method to address the hashing learning problem for streaming data. The proposed method is innovated from the idea of data sketching, and allows a dramatic reduction in computation and storage overhead. In real world applications, the data often comes in a streaming fashion, but most of existing hashing methods are batch based models. Our approach maintains a small size sketch for the streaming data online, and learns hashing functions on the sketch rather than the whole dataset. To overcome the mean-varying problem in online hash function learning, we propose a new algorithm to sketch the zero-meaned stream data online. We theoretically prove that the obtained sketch can preserve most of the useful information in data for hashing function learning.

 

2. We propose a novel distributed hashing method for data which is distributed across different nodes in a network. We introduce a centralized hashing model within the framework of minimizing quantization distortion. We then cast this centralized hashing model as a set of decentralized subproblems with consensus constraints and solve them with ADMM algorithm. Experiments demonstrate that our method can fast converge to a local optimum. Since we make no assumption about the network, the proposed distributed algorithm can adapt to arbitrary network topology. Besides, since there is no exchange of training data across the nodes in the learning process, the communication cost of our method is very small.

 

3. For the eigendecomposition based hashing methods, the information caught by different eigenvectors is unbalanced, which causes that longer hashing codes are often noisy with inferior performance. We propose ensemble learning based hashing methods to address this problem. Our methods use only the top eigenvectors to generate a piece of short but strong code and repeat this process several times, then we concatenate many pieces of short codes into one piece of long code. In order to guarantee the diversity among different pieces of short codes, we adopt the bagging and random subspace strategy to sample in the data and feature space respectively, leading to two hashing algorithms BPCAH and RPCAH. We compare the proposed methods with the famous LSH algorithm, and theoretically prove that longer codes tend to yield better performance than the shorter ones under the ensemble learning strategy.

 

4. We propose a cascade hashing structure to speed up the image matching process for 3D reconstruction. We find that the image matching problem can be essentially converted into a nearest neighbor search problem, and use hashing method to map the image descriptors from Euclidean space to Hamming space. The proposed cascade hashing is a coarse to fine strategy with three steps, i.e., multi-table hashing lookup, hashing remapping and hashing based top $k$ ranking. We compare the time complexity of our cascade hashing with other well-known matching methods. It is easy for our method to realize 10 times or more acceleration than $Kd$-tree based image matching with comparable accuracy.