Methods for large-scale machine learning and computer vision

With the advance of the Internet and information technology, nowadays people can easily collect and store tremendous amounts of data such as images and videos. Developing machine learning and computer vision to analysis and learn from the gigantic data sets is an interesting yet challenging problem. Inspired by the trend, this thesis focus on developing large-scale machine learning and computer vision techniques for the purpose of handling various kinds of problems on gigantic data sets. This thesis will investigate the problem of developing machine learning algorithms for large-scale databases. The basic idea of this thesis is to leverage the learning and analysis process by only using a small subset of data. We propose different approaches to learn and generalize the knowledge from the subset to the whole data set. A key application domain of the proposed work is efficient similarity search in large databases of images. A second application of the proposed work is performing clustering on large-scale multi-view data. A third application of the proposed work is real-time visual tracking for computer-assisted surgery.;With respect to the problem of image classification, we employ the technique of sub-selection to reduce the computational cost of the optimization process. We consider the classification models based on sparse representation or collaborative representation. The proposed method can handle misalignment, occlusion and big noises with lower computational cost. It is motivated by the sub-selection technique, which uses partial observations to efficiently approximate the original high dimensional problems. In practical applications, the performance of classification can be affected by problems like misalignment, occlusion and big noises. To deal with these problems, we propose a robust sub-representation method, which can effectively handle these problems with an efficient scheme. While its performance guarantee was theoretically proved, numerous experiments on practical applications have further demonstrated that the proposed method can lead to significant performance improvement in terms of speed and accuracy.;With respect to the problem of improving the efficiency of similarity search, this thesis contribute a novel method for hashing a large number of images. While many researchers have worked on the topic of how to find good hash function for this task, the thesis will propose a new approach to address efficiency. In particular, the training step of many existing hash methods relies on computing the Principle Components Analysis (PCA). However, performing PCA on large dataset is time-consuming. The thesis will prove that, under some conditions, the PCA can be computed by using only a small part of the data. With the theoretical guarantee, one can accelerate the training process of hashing without loss much of accuracy. This result greatly improve the efficiency of the state-of-the-art hash methods.;With respect to the problem of clustering on large-scale multi-view data, the thesis contribute a novel method for graph-based clustering. A graph offers an attractive way of representing data and discovering the essential information such as the neighborhood structure. However, both of the graph construction process and graph-based learning techniques become computationally prohibitive at a large scale. To overcome these bottlenecks, we present a novel graph construction approach, called Salient Graphs, which enjoys linear space and time complexities and can thus be constructed over gigantic databases efficiently. Based on the Salient Graph, we implement an efficient graph-cut algorithm, which iteratively search consensus between multiple views and perform clustering. This results in an accurate and fast algorithm for multi-view data clustering.;With respect to the problem of visual tracking, the thesis contribute a novel method for instrument tracking in retinal microsurgery. The instrument tracking is a key task in robot-assist surgical system. In this kind of system, data is collected and processing in real-time. Therefore, a tracking algorithm need to find good balance between accuracy and efficiency. The thesis proposed a novel visual tracker based on online learning. The proposed algorithm is able to run in video frame-rate while achieving the state-of-the-art accuracy.Thorough experimental evaluation on a variety of datasets will demonstrate state-of-the-art performance for the proposed contributions of the thesis.