Colin Campbell

NeurIPS Conference 2009 Conference Paper

Analysis of SVM with Indefinite Kernels

• Yiming Ying
• Colin Campbell
• Mark Girolami

The recent introduction of indefinite SVM by Luss and dAspremont [15] has effectively demonstrated SVM classification with a non-positive semi-definite kernel (indefinite kernel). This paper studies the properties of the objective function introduced there. In particular, we show that the objective function is continuously differentiable and its gradient can be explicitly computed. Indeed, we further show that its gradient is Lipschitz continuous. The main idea behind our analysis is that the objective function is smoothed by the penalty term, in its saddle (min-max) representation, measuring the distance between the indefinite kernel matrix and the proxy positive semi-definite one. Our elementary result greatly facilitates the application of gradient-based algorithms. Based on our analysis, we further develop Nesterovs smooth optimization approach [16, 17] for indefinite SVM which has an optimal convergence rate for smooth problems. Experiments on various benchmark datasets validate our analysis and demonstrate the efficiency of our proposed algorithms.

NeurIPS Conference 2009 Conference Paper

Sparse Metric Learning via Smooth Optimization

• Yiming Ying
• Kaizhu Huang
• Colin Campbell

In this paper we study the problem of learning a low-dimensional (sparse) distance matrix. We propose a novel metric learning model which can simultaneously conduct dimension reduction and learn a distance matrix. The sparse representation involves a mixed-norm regularization which is non-convex. We then show that it can be equivalently formulated as a convex saddle (min-max) problem. From this saddle representation, we develop an efficient smooth optimization approach for sparse metric learning although the learning model is based on a non-differential loss function. This smooth optimization approach has an optimal convergence rate of $O(1 /\ell^2)$ for smooth problems where $\ell$ is the iteration number. Finally, we run experiments to validate the effectiveness and efficiency of our sparse metric learning model on various datasets.

JMLR Journal 2001 Journal Article

Bayes Point Machines (Kernel Machines Section)

• Ralf Herbrich
• Thore Graepel
• Colin Campbell

Kernel-classifiers comprise a powerful class of non-linear decision functions for binary classification. The support vector machine is an example of a learning algorithm for kernel classifiers that singles out the consistent classifier with the largest margin, i.e. minimal real-valued output on the training sample, within the set of consistent hypotheses, the so-called version space. We suggest the Bayes point machine as a well-founded improvement which approximates the Bayes-optimal decision by the centre of mass of version space. We present two algorithms to stochastically approximate the centre of mass of version space: a billiard sampling algorithm and a sampling algorithm based on the well known perceptron algorithm. It is shown how both algorithms can be extended to allow for soft-boundaries in order to admit training errors. Experimentally, we find that - for the zero training error case - Bayes point machines consistently outperform support vector machines on both surrogate data and real-world benchmark data sets. In the soft-boundary/soft-margin case, the improvement over support vector machines is shown to be reduced. Finally, we demonstrate that the real-valued output of single Bayes points on novel test points is a valid confidence measure and leads to a steady decrease in generalisation error when used as a rejection criterion.

NeurIPS Conference 2000 Conference Paper

A Linear Programming Approach to Novelty Detection

• Colin Campbell
• Kristin Bennett

Novelty detection involves modeling the normal behaviour of a sys(cid: 173) tem hence enabling detection of any divergence from normality. It has potential applications in many areas such as detection of ma(cid: 173) chine damage or highlighting abnormal features in medical data. One approach is to build a hypothesis estimating the support of the normal data i. e. constructing a function which is positive in the region where the data is located and negative elsewhere. Recently kernel methods have been proposed for estimating the support of a distribution and they have performed well in practice - training involves solution of a quadratic programming problem. In this pa(cid: 173) per we propose a simpler kernel method for estimating the support based on linear programming. The method is easy to implement and can learn large datasets rapidly. We demonstrate the method on medical and fault detection datasets. 1

ICML Conference 2000 Conference Paper

Query Learning with Large Margin Classifiers

• Colin Campbell
• Nello Cristianini
• Alexander J. Smola

NeurIPS Conference 1998 Conference Paper

Dynamically Adapting Kernels in Support Vector Machines

• Nello Cristianini
• Colin Campbell
• John Shawe-Taylor

The kernel-parameter is one of the few tunable parameters in Sup(cid: 173) port Vector machines, controlling the complexity of the resulting hypothesis. Its choice amounts to model selection and its value is usually found by means of a validation set. We present an algo(cid: 173) rithm which can automatically perform model selection with little additional computational cost and with no need of a validation set. In this procedure model selection and learning are not separate, but kernels are dynamically adjusted during the learning process to find the kernel parameter which provides the best possible upper bound on the generalisation error. Theoretical results motivating the approach and experimental results confirming its validity are presented.

ICML Conference 1998 Conference Paper

The Kernel-Adatron Algorithm: A Fast and Simple Learning Procedure for Support Vector Machines

• Thilo-Thomas Frieß
• Nello Cristianini
• Colin Campbell