Image Representation for Fast Query and Its Applications

在许多识别问题中，最基本的过程是输入和数据集之间的匹配。这个过程可以描述为高维向量空间中的最近邻问题。如果每个数据驻留在高维空间中，则最近邻搜索变得非常困难，这取决于维数。例如，著名的kd树对于高维向量空间中的搜索问题是无用的。本文首先比较了常用的搜索算法，包括暴力搜索法、kd树和局部敏感哈希算法。我们表明，LSH可以是非常有效的，虽然它只能给出近似解。为了在高维向量空间中实现快速查询，降低目标数据集的维数和/或减小目标数据集的大小是非常重要的。LSH可以看作是减少数据集的方法之一。基于这些初步的结果，我们首先提出了一个基于高斯混合模型和PCA（主成分分析）的图像查询系统。然后，我们表明，如果分布的数据集可以描述为“集群”，快速查询可以成为可能。当数据集由多个类组成时，为每个输入向量识别合适的类是快速可靠搜索的关键。为此，我们必须从例子中学习分类器。由于我们不能期望分类器100%准确，因此希望获得产生多个假设的分类器。在我们的报告中，我们描述了一种方法来扩展DAG-SVM，使多个假设。

In many recognition problems, basic procedure is the matching between the input and the data set. This procedure can be characterized as the nearest neighbor problem in high dimensional vector space. If each data resides in the high-dimensional space, nearest neighbor search is getting very difficult depending the dimensionality. For example, well-known kd-tree is useless for the search problem in high dimensional vector space. In this report, we first compare the search algorithms, including brute-force method, kd-tree and LSH(locality sensitivity hashing). We show, LSH can be very effective, although it can give only the approximation solution. To realize fast query in high-dimensional vector space, it is important to reduce the dimensionality and/or to reduce the size of the target data set. LSH can be seen as one of the method to reduce the data set to examine.Based on these preliminary results, we first propose an image query system based on the Gaussian mixture model and PCA(principle component analysis). Then, we show if the distribution of the data set can be described as the "clusters", fast query can be made possible. If data set is made up of several clusters, recognizing the appropriate cluster for each input vector is the key to the fast and reliable search. For that purpose, we have to learn classifiers from examples. Since we cannot expect the classifier 100% accurate, it is desirable to obtain classifiers which give rise to multiple hypotheses. In our report, we describe a method to extend DAG-SVM to make multiple hypotheses.