Online multiple kernel similarity learning for visual search

A Multilayer Framework for Online Metric Learning

Online metric learning (OML) has been widely applied in classification and retrieval. It can automatically learn a suitable metric from data by restricting similar instances to be separated from dissimilar instances with a given margin. However, the existing OML algorithms have limited performance in real-world classifications, especially, when data distributions are complex. To this end, this article proposes a multilayer framework for OML to capture the nonlinear similarities among instances. Different from the traditional OML, which can only learn one metric space, the proposed multilayer OML (MLOML) takes an OML algorithm as a metric layer and learns multiple hierarchical metric spaces, where each metric layer follows a nonlinear layer for the complicated data distribution. Moreover, the forward propagation (FP) strategy and backward propagation (BP) strategy are employed to train the hierarchical metric layers. To build a metric layer of the proposed MLOML, a new Mahalanobis-based OML (MOML) algorithm is presented based on the passive-aggressive strategy and one-pass triplet construction strategy. Furthermore, in a progressively and nonlinearly learning way, MLOML has a stronger learning ability than traditional OML in the case of limited available training data. To make the learning process more explainable and theoretically guaranteed, theoretical analysis is provided. The proposed MLOML enjoys several nice properties, indeed learns a metric progressively, and performs better on the benchmark datasets. Extensive experiments with different settings have been conducted to verify these properties of the proposed MLOML.

One-Class Classification Using ℓp-Norm Multiple Kernel Fisher Null Approach

We address the one-class classification (OCC) problem and advocate a one-class MKL (multiple kernel learning) approach for this purpose. To this aim, based on the Fisher null-space OCC principle, we present a multiple kernel learning algorithm where an ℓ_p-norm regularisation (p ≥ 1) is considered for kernel weight learning. We cast the proposed one-class MKL problem as a min-max saddle point Lagrangian optimisation task and propose an efficient approach to optimise it. An extension of the proposed approach is also considered where several related one-class MKL tasks are learned concurrently by constraining them to share common weights for kernels. An extensive evaluation of the proposed MKL approach on a range of data sets from different application domains confirms its merits against the baseline and several other algorithms.

Low-rank robust online distance/similarity learning based on the rescaled hinge loss

An important challenge in metric learning is scalability to both size and dimension of input data. Online metric learning algorithms are proposed to address this challenge. Existing methods are commonly based on Passive/Aggressive (PA) approach. Hence, they can rapidly process large volumes of data with an adaptive learning rate. However, these algorithms are based on the Hinge loss and so are not robust against outliers and label noise. We address the challenges by formulating the online Distance/Similarity learning problem with the robust Rescaled Hinge loss function. The proposed model is rather general and can be applied to any PA-based online Distance/Similarity algorithm. To achieve scalability to data dimension, we propose low-rank online Distance/Similarity methods that learn a rectangular projection matrix instead of a full Mahalanobis matrix. The low-rank approaches not only reduce the computational cost but also keep the discrimination power of the learned metrics. Also, current online methods usually assume training triplets or pairwise constraints exist in advance. However, this assumption does not hold, and generating triplets using available batch sampling methods is both time and space consuming. We address this issue by developing an efficient, yet effective robust one-pass triplet construction algorithm. We conduct several experiments on datasets from various applications. The results confirm that the proposed methods significantly outperform state-of-the-art online metric learning methods in the presence of label noise and outliers by a large margin.

Semisupervised Laplace-Regularized Multimodality Metric Learning

Distance metric learning, which aims at learning an appropriate metric from data automatically, plays a crucial role in the fields of pattern recognition and information retrieval. A tremendous amount of work has been devoted to metric learning in recent years, but much of the work is basically designed for training a linear and global metric with labeled samples. When data are represented with multimodal and high-dimensional features and only limited supervision information is available, these approaches are inevitably confronted with a series of critical problems: 1) naive concatenation of feature vectors can cause the curse of dimensionality in learning metrics and 2) ignorance of utilizing massive unlabeled data may lead to overfitting. To mitigate this deficiency, we develop a semisupervised Laplace-regularized multimodal metric-learning method in this work, which explores a joint formulation of multiple metrics as well as weights for learning appropriate distances: 1) it learns a global optimal distance metric on each feature space and 2) it searches the optimal combination weights of multiple features. Experimental results demonstrate both the effectiveness and efficiency of our method on retrieval and classification tasks.

Efficient Unsupervised Dimension Reduction for Streaming Multiview Data

Multiview learning has received substantial attention over the past decade due to its powerful capacity in integrating various types of information. Conventional unsupervised multiview dimension reduction (UMDR) methods are usually conducted in an offline manner and may fail in many real-world applications, where data arrive sequentially and the data distribution changes periodically. Moreover, satisfying the requirements of high memory consumption and expensive retraining of the time cost in large-scale scenarios are difficult. To remedy these drawbacks, we propose an online UMDR (OUMDR) framework. OUMDR aims to seek a low-dimensional and informative consensus representation for streaming multiview data. View-specific weights are also learned in this article to reflect the contributions of different views to the final consensus presentation. A specific model called OUMDR-E is developed by introducing the exclusive group LASSO (EG-LASSO) to explore the intraview and interview correlations. Then, we develop an efficient iterative algorithm with limited memory and time cost requirements for optimization, where the convergence of each update is theoretically guaranteed. We evaluate the proposed approach in video-based expression recognition applications. The experimental results demonstrate the superiority of our approach in terms of both effectiveness and efficiency.

Large-Scale Local Online Similarity/Distance Learning Framework Based on Passive/Aggressive

Similarity/distance measures play a key role in many machine learning, pattern recognition, and data mining algorithms, which leads to the emergence of the metric learning field. Many metric learning algorithms learn a global distance function from data that satisfies the constraints of the problem. However, in many real-world datasets, where the discrimination power of features varies in the different regions of input space, a global metric is often unable to capture the complexity of the task. To address this challenge, local metric learning methods are proposed which learn multiple metrics across the different regions of the input space. Some advantages of these methods include high flexibility and learning a nonlinear mapping, but they typically achieve at the expense of higher time requirements and overfitting problems. To overcome these challenges, this research presents an online multiple metric learning framework. Each metric in the proposed framework is composed of a global and a local component learned simultaneously. Adding a global component to a local metric efficiently reduces the problem of overfitting. The proposed framework is also scalable with both sample size and the dimension of input data. To the best of our knowledge, this is the first local online similarity/distance learning framework based on Passive/Aggressive (PA). In addition, for scalability with the dimension of input data, Dual Random Projection (DRP) is extended for local online learning in the present work. It enables our methods to run efficiently on high-dimensional datasets while maintaining their predictive performance. The proposed framework provides a straightforward local extension to any global online similarity/distance learning algorithm based on PA. Experimental results on some challenging datasets from machine vision community confirm that the extended methods considerably enhance the performance of the related global ones without increasing the time complexity.

Absent Multiple Kernel Learning Algorithms

Multiple kernel learning (MKL) has been intensively studied during the past decade. It optimally combines the multiple channels of each sample to improve classification performance. However, existing MKL algorithms cannot effectively handle the situation where some channels of the samples are missing, which is not uncommon in practical applications. This paper proposes three absent MKL (AMKL) algorithms to address this issue. Different from existing approaches where missing channels are first imputed and then a standard MKL algorithm is deployed on the imputed data, our algorithms directly classify each sample based on its observed channels, without performing imputation. Specifically, we define a margin for each sample in its own relevant space, a space corresponding to the observed channels of that sample. The proposed AMKL algorithms then maximize the minimum of all sample-based margins, and this leads to a difficult optimization problem. We first provide two two-step iterative algorithms to approximately solve this problem. After that, we show that this problem can be reformulated as a convex one by applying the representer theorem. This makes it readily be solved via existing convex optimization packages. In addition, we provide a generalization error bound to justify the proposed AMKL algorithms from a theoretical perspective. Extensive experiments are conducted on nine UCI and six MKL benchmark datasets to compare the proposed algorithms with existing imputation-based methods. As demonstrated, our algorithms achieve superior performance and the improvement is more significant with the increase of missing ratio.

Large-Scale Multi-modal Distance Metric Learning with Application to Content-Based Information Retrieval and Image Classification

Metric learning algorithms aim to make the conceptually related data items closer and keep dissimilar ones at a distance. The most common approach for metric learning on the Mahalanobis method. Despite its success, this method is limited to find a linear projection and also suffer from scalability respecting both the dimensionality and the size of input data. To address these problems, this paper presents a new scalable metric learning algorithm for multi-modal data. Our method learns an optimal metric for any feature set of the multi-modal data in an online fashion. We also combine the learned metrics with a novel Passive/Aggressive (PA)-based algorithm which results in a higher convergence rate compared to the state-of-the-art methods. To address scalability with respect to dimensionality, Dual Random Projection (DRP) is adopted in this paper. The present method is evaluated on some challenging machine vision datasets for image classification and Content-Based Information Retrieval (CBIR) tasks. The experimental results confirm that the proposed method significantly surpasses other state-of-the-art metric learning methods in most of these datasets in terms of both accuracy and efficiency.

SVRG-MKL: A Fast and Scalable Multiple Kernel Learning Solution for Features Combination in Multi-Class Classification Problems

In this paper, we present a novel strategy to combine a set of compact descriptors to leverage an associated recognition task. We formulate the problem from a multiple kernel learning (MKL) perspective and solve it following a stochastic variance reduced gradient (SVRG) approach to address its scalability, currently an open issue. MKL models are ideal candidates to jointly learn the optimal combination of features along with its associated predictor. However, they are unable to scale beyond a dozen thousand of samples due to high computational and memory requirements, which severely limits their applicability. We propose SVRG-MKL, an MKL solution with inherent scalability properties that can optimally combine multiple descriptors involving millions of samples. Our solution takes place directly in the primal to avoid Gram matrices computation and memory allocation, whereas the optimization is performed with a proposed algorithm of linear complexity and hence computationally efficient. Our proposition builds upon recent progress in SVRG with the distinction that each kernel is treated differently during optimization, which results in a faster convergence than applying off-the-shelf SVRG into MKL. Extensive experimental validation conducted on several benchmarking data sets confirms a higher accuracy and a significant speedup of our solution. Our technique can be extended to other MKL problems, including visual search and transfer learning, as well as other formulations, such as group-sensitive (GMKL) and localized MKL (LMKL) in convex settings.

Discriminative Fisher Embedding Dictionary Learning Algorithm for Object Recognition

Both interclass variances and intraclass similarities are crucial for improving the classification performance of discriminative dictionary learning (DDL) algorithms. However, existing DDL methods often ignore the combination between the interclass and intraclass properties of dictionary atoms and coding coefficients. To address this problem, in this paper, we propose a discriminative Fisher embedding dictionary learning (DFEDL) algorithm that simultaneously establishes Fisher embedding models on learned atoms and coefficients. Specifically, we first construct a discriminative Fisher atom embedding model by exploring the Fisher criterion of the atoms, which encourages the atoms of the same class to reconstruct the corresponding training samples as much as possible. At the same time, a discriminative Fisher coefficient embedding model is formulated by imposing the Fisher criterion on the profiles (row vectors of the coding coefficient matrix) and coding coefficients, which forces the coding coefficient matrix to become a block-diagonal matrix. Since the profiles can indicate which training samples are represented by the corresponding atoms, the proposed two discriminative Fisher embedding models can alternatively and interactively promote the discriminative capabilities of the learned dictionary and coding coefficients. The extensive experimental results demonstrate that the proposed DFEDL algorithm achieves superior performance in comparison with some state-of-the-art dictionary learning algorithms on both hand-crafted and deep learning-based features.

An Interpretable Deep Architecture for Similarity Learning Built Upon Hierarchical Concepts

In general, development of adequately complex mathematical models, such as deep neural networks, can be an effective way to improve the accuracy of learning models. However, this is achieved at the cost of reduced post-hoc model interpretability, because what is learned by the model can become less intelligible and tractable to humans as the model complexity increases. In this paper, we target a similarity learning task in the context of image retrieval, with a focus on the model interpretability issue. An effective similarity neural network (SNN) is proposed to offer not only to seek robust retrieval performance but also to achieve satisfactory post-hoc interpretability. The network is designed by linking the neuron architecture with the organization of a concept tree and by formulating neuron operations to pass similarity information between concepts. Various ways of understanding and visualizing what is learned by the SNN neurons are proposed. We also exhaustively evaluate the proposed approach using a number of relevant datasets against a number of state-of-the-art approaches to demonstrate the effectiveness of the proposed network. Our results show that the proposed approach can offer superior performance when compared against state-of-the-art approaches. Neuron visualization results are demonstrated to support the understanding of the trained neurons.

Online Asymmetric Metric Learning With Multi-Layer Similarity Aggregation for Cross-Modal Retrieval

Cross-modal retrieval has attracted intensive attention in recent years, where a substantial yet challenging problem is how to measure the similarity between heterogeneous data modalities. Despite using modality-specific representation learning techniques, most existing shallow or deep models treat different modalities equally and neglect the intrinsic modality heterogeneity and information imbalance among images and texts. In this paper, we propose an online similarity function learning framework to learn the metric that can well reflect the cross-modal semantic relation. Considering that multiple CNN feature layers naturally represent visual information from low-level visual patterns to high-level semantic abstraction, we propose a new asymmetric image-text similarity formulation which aggregates the layer-wise visual-textual similarities parameterized by different bilinear parameter matrices. To effectively learn the aggregated similarity function, we develop three different similarity combination strategies, i.e., average kernel, multiple kernel learning, and layer gating. The former two kernel-based strategies assign uniform weights on different layers to all data pairs; the latter works on the original feature representation and assigns instance-aware weights on different layers to different data pairs, and they are all learned by preserving the bi-directional relative similarity expressed by a large number of cross-modal training triplets. The experiments conducted on three public datasets well demonstrate the effectiveness of our methods.

Low-rank analysis-synthesis dictionary learning with adaptively ordinal locality

Analysis dictionary learning (ADL) has been successfully applied to a variety of learning systems. However, the ordinal locality of analysis dictionary has rarely been explored in constructing discriminative terms. In this paper, a discriminative low-rank analysis-synthesis dictionary learning (LR-ASDL) algorithm with the adaptively ordinal locality is proposed for object classification. Specifically, we first explicitly introduce the relations between the analysis atoms and profiles (i.e., row vectors of the coefficients matrix). That is, the similarity between two profiles depends on that between the corresponding analysis atoms. Moreover, an adaptively ordinal locality preserving(AOLP) term is constructed by simultaneously exploiting the profiles and analysis atoms, which can be learned in a supervised way. In this way, the neighborhood correlations between analysis atoms and the high-order ranking information of each analysis atom's neighbors can be simultaneously preserved in the learning process. Particularly, this helps to uncover the intrinsic underlying data factors and inherit the geometry structure information of training samples. Furthermore, the low-rank model is imposed on the synthesis atoms to further facilitate the learned dictionaries to be more discriminative. Extensive experimental results on eight databases demonstrate that the LR-ASDL algorithm clearly outperforms some analysis and synthesis dictionary learning algorithms using deep and hand-crafted features.

Early Expression Detection via Online Multi-Instance Learning With Nonlinear Extension

Video-based facial expression recognition has received substantial attention over the past decade, while early expression detection (EED) is still a relatively new and challenging problem. The goal of EED is to identify an expression as quickly as possible after the expression starts and before it ends. This timely ability has many potential applications, ranging from human-computer interaction to security. The max-margin early event detector (MMED) is a well-known ranking model for early event detection. It can achieve competitive EED performance but suffers from several critical limitations: 1) MMED lacks flexibility in extracting useful information for segment comparison, which leads to poor performance in exploring the ranking relation between segment pairs; 2) the training process is slow due to the large number of constraints, and the memory requirement is also usually hard to satisfy; and 3) MMED is linear in nature, and hence may not be appropriate for data in a nonlinear feature space. To overcome these limitations, we propose an online multi-instance learning (MIL) framework for EED. In particular, the MIL technique is first introduced to generalize MMED, resulting in the proposed MIL-based EED (MIED), which is more general and flexible than MMED, since various instance construction and combination strategies can be adopted. To accelerate the training process, we reformulate MIED in the online setting and develop online multi-instance learning framework for EED (OMIED). To further exploit the nonlinear structure of the data distribution, we incorporate the kernel methods in OMIED, which results in the proposed online kernel multi-instance learning for early expression detection. Experiments on two popular and one challenging video-based expression data sets demonstrate both the efficiency and effectiveness of the proposed methods.

Online Feature Transformation Learning for Cross-Domain Object Category Recognition

In this paper, we introduce a new research problem termed online feature transformation learning in the context of multiclass object category recognition. The learning of a feature transformation is viewed as learning a global similarity metric function in an online manner. We first consider the problem of online learning a feature transformation matrix expressed in the original feature space and propose an online passive aggressive feature transformation algorithm. Then these original features are mapped to kernel space and an online single kernel feature transformation (OSKFT) algorithm is developed to learn a nonlinear feature transformation. Based on the OSKFT and the existing Hedge algorithm, a novel online multiple kernel feature transformation algorithm is also proposed, which can further improve the performance of online feature transformation learning in large-scale application. The classifier is trained with k nearest neighbor algorithm together with the learned similarity metric function. Finally, we experimentally examined the effect of setting different parameter values in the proposed algorithms and evaluate the model performance on several multiclass object recognition data sets. The experimental results demonstrate the validity and good performance of our methods on cross-domain and multiclass object recognition application.

Online Nonlinear AUC Maximization for Imbalanced Data Sets

Classifying binary imbalanced streaming data is a significant task in both machine learning and data mining. Previously, online area under the receiver operating characteristic (ROC) curve (AUC) maximization has been proposed to seek a linear classifier. However, it is not well suited for handling nonlinearity and heterogeneity of the data. In this paper, we propose the kernelized online imbalanced learning (KOIL) algorithm, which produces a nonlinear classifier for the data by maximizing the AUC score while minimizing a functional regularizer. We address four major challenges that arise from our approach. First, to control the number of support vectors without sacrificing the model performance, we introduce two buffers with fixed budgets to capture the global information on the decision boundary by storing the corresponding learned support vectors. Second, to restrict the fluctuation of the learned decision function and achieve smooth updating, we confine the influence on a new support vector to its -nearest opposite support vectors. Third, to avoid information loss, we propose an effective compensation scheme after the replacement is conducted when either buffer is full. With such a compensation scheme, the performance of the learned model is comparable to the one learned with infinite budgets. Fourth, to determine good kernels for data similarity representation, we exploit the multiple kernel learning framework to automatically learn a set of kernels. Extensive experiments on both synthetic and real-world benchmark data sets demonstrate the efficacy of our proposed approach.

Sparse Passive-Aggressive Learning for Bounded Online Kernel Methods

One critical deficiency of traditional online kernel learning methods is their unbounded and growing number of support vectors in the online learning process, making them inefficient and non-scalable for large-scale applications. Recent studies on scalable online kernel learning have attempted to overcome this shortcoming, e.g., by imposing a constant budget on the number of support vectors. Although they attempt to bound the number of support vectors at each online learning iteration, most of them fail to bound the number of support vectors for the final output hypothesis, which is often obtained by averaging the series of hypotheses over all the iterations. In this article, we propose a novel framework for bounded online kernel methods, named “Sparse Passive-Aggressive (SPA)” learning, which is able to yield a final output kernel-based hypothesis with a bounded number of support vectors. Unlike the common budget maintenance strategy used by many existing budget online kernel learning approaches, the idea of our approach is to attain the bounded number of support vectors using an efficient stochastic sampling strategy that samples an incoming training example as a new support vector with a probability proportional to its loss suffered. We theoretically prove that SPA achieves an optimal mistake bound in expectation, and we empirically show that it outperforms various budget online kernel learning algorithms. Finally, in addition to general online kernel learning tasks, we also apply SPA to derive bounded online multiple-kernel learning algorithms, which can significantly improve the scalability of traditional Online Multiple-Kernel Classification (OMKC) algorithms while achieving satisfactory learning accuracy as compared with the existing unbounded OMKC algorithms.

Sparse Online Learning of Image Similarity

Learning image similarity plays a critical role in real-world multimedia information retrieval applications, especially in Content-Based Image Retrieval (CBIR) tasks, in which an accurate retrieval of visually similar objects largely relies on an effective image similarity function. Crafting a good similarity function is very challenging because visual contents of images are often represented as feature vectors in high-dimensional spaces, for example, via bag-of-words (BoW) representations, and traditional rigid similarity functions, for example, cosine similarity, are often suboptimal for CBIR tasks. In this article, we address this fundamental problem, that is, learning to optimize image similarity with sparse and high-dimensional representations from large-scale training data, and propose a novel scheme of Sparse Online Learning of Image Similarity (SOLIS). In contrast to many existing image-similarity learning algorithms that are designed to work with low-dimensional data, SOLIS is able to learn image similarity from large-scale image data in sparse and high-dimensional spaces. Our encouraging results showed that the proposed new technique achieves highly competitive accuracy as compared to the state-of-the-art approaches but enjoys significant advantages in computational efficiency, model sparsity, and retrieval scalability, making it more practical for real-world multimedia retrieval applications.

Soft Confidence-Weighted Learning

Online learning plays an important role in many big data mining problems because of its high efficiency and scalability. In the literature, many online learning algorithms using gradient information have been applied to solve online classification problems. Recently, more effective second-order algorithms have been proposed, where the correlation between the features is utilized to improve the learning efficiency. Among them, Confidence-Weighted (CW) learning algorithms are very effective, which assume that the classification model is drawn from a Gaussian distribution, which enables the model to be effectively updated with the second-order information of the data stream. Despite being studied actively, these CW algorithms cannot handle nonseparable datasets and noisy datasets very well. In this article, we propose a family of Soft Confidence-Weighted (SCW) learning algorithms for both binary classification and multiclass classification tasks, which is the first family of online classification algorithms that enjoys four salient properties simultaneously: (1) large margin training, (2) confidence weighting, (3) capability to handle nonseparable data, and (4) adaptive margin. Our experimental results show that the proposed SCW algorithms significantly outperform the original CW algorithm. When comparing with a variety of state-of-the-art algorithms (including AROW, NAROW, and NHERD), we found that SCW in general achieves better or at least comparable predictive performance, but enjoys considerably better efficiency advantage (i.e., using a smaller number of updates and lower time cost). To facilitate future research, we release all the datasets and source code to the public at http://libol.stevenhoi.org/.