We present a bound on the generalisation error of linear classifiers in terms of a refined margin quantity on the training set. The result is obtained in a PAC- Bayesian framework and is based on geometrical arguments in the space of linear classifiers. The new bound constitutes an exponential improvement of the so far tightest margin bound by Shawe-Taylor et al. [8] and scales logarithmically in the inverse margin. Even in the case of less training examples than input dimensions sufficiently large margins lead to non-trivial bound values and - plexity term. Furthermore, the classical margin is too coarse a measure for the essential quantity that controls the generalisation error: the volume ratio between the whole hypothesis space and the subset of consistent hypotheses.

Low-dimensional representations are key to solving problems in high(cid:173) level vision, such as face compression and recognition. Factorial coding strategies for reducing the redundancy present in natural images on the basis of their second-order statistics have been successful in account(cid:173) ing for both psychophysical and neurophysiological properties of early vision. Class-specific representations are presumably formed later, at the higher-level stages of cortical processing. Here we show that when retinotopic factorial codes are derived for ensembles of natural objects, such as human faces, not only redundancy, but also dimensionality is re(cid:173) duced. We also show that objects are built from parts in a non-Gaussian fashion which allows these local-feature codes to have dimensionalities that are substantially lower than the respective Nyquist sampling rates.

We propose the following general method for scaling learning algorithms to arbitrarily large data sets. Consider the model Mii learned by the algorithm using ni examples in step i (ii (nl, ...,nm)), and the model Moo that would be learned using in(cid:173) finite examples. Upper-bound the loss L(Mii' M oo) between them as a function of ii, and then minimize the algorithm's time com(cid:173) plexity f(ii) subject to the constraint that L(Moo, Mii) be at most f with probability at most 8. We apply this method to the EM algorithm for mixtures of Gaussians. Preliminary experiments on a series of large data sets provide evidence of the potential of this approach.

We develop an intuitive geometric framework for support vector regression (SVR). By examining when (cid:15)-tubes exist, we show that SVR can be regarded as a classi(cid:12)cation problem in the dual space. Hard and soft (cid:15)-tubes are constructed by separating the convex or reduced convex hulls respectively of the training data with the response variable shifted up and down by (cid:15). A novel SVR model is proposed based on choosing the max-margin plane between the two shifted datasets. In the proposed approach the e(cid:11)ects of the choices of all parameters become clear geometrically.

Principal component analysis (PCA) is a commonly applied technique for dimensionality reduction. PCA implicitly minimizes a squared loss function, which may be inappropriate for data that is not real-valued, such as binary-valued data. This paper draws on ideas from the Exponen- tial family, Generalized linear models, and Bregman distances, to give a generalization of PCA to loss functions that we argue are better suited to other data types. We describe algorithms for minimizing the loss func- tions, and give examples on simulated data.

We propose a method for the fast estimation of hyperparameters in large networks, based on the linear response relation in the cav(cid:173) ity method, and an empirical measurement of the Green's func(cid:173) tion. Simulation results show that it is efficient and precise, when compared with cross-validation and other techniques which require matrix inversion.

Factor analysis and principal components analysis can be used to model linear relationships between observed variables and linearly map high-dimensional data to a lower-dimensional hidden space. In factor analysis, the observations are modeled as a linear com(cid:173) bination of normally distributed hidden variables. We describe a nonlinear generalization of factor analysis, called "product analy(cid:173) sis", that models the observed variables as a linear combination of products of normally distributed hidden variables. Just as fac(cid:173) tor analysis can be viewed as unsupervised linear regression on unobserved, normally distributed hidden variables, product anal(cid:173) ysis can be viewed as unsupervised linear regression on products of unobserved, normally distributed hidden variables. The map(cid:173) ping between the data and the hidden space is nonlinear, so we use an approximate variational technique for inference and learn(cid:173) ing.

This paper describes a clustering algorithm for vector quantizers using a "stochastic association model". It offers a new simple and powerful soft- max adaptation rule. The adaptation process is the same as the on-line K-means clustering method except for adding random fluctuation in the distortion error evaluation process. Simulation results demonstrate that the new algorithm can achieve efficient adaptation as high as the "neural gas" algorithm, which is reported as one of the most efficient clustering methods. It is a key to add uncorrelated random fluctuation in the simi- larity evaluation process for each reference vector.

In this paper we introduce a new sparseness inducing prior which does not involve any (hy- per)parameters that need to be adjusted or estimated. Although other applications are possi- ble, we focus here on supervised learning problems: regression and classification. Experi- ments with several publicly available benchmark data sets show that the proposed approach yields state-of-the-art performance. In particular, our method outperforms support vector machines and performs competitively with the best alternative techniques, both in terms of error rates and sparseness, although it involves no tuning or adjusting of sparseness- controlling hyper-parameters.

We give results about the learnability and required complexity of logical formulae to solve classification problems. These results are obtained by linking propositional logic with kernel machines. In particular we show that decision trees and disjunctive normal forms (DNF) can be repre- sented by the help of a special kernel, linking regularized risk to separa- tion margin. Subsequently we derive a number of lower bounds on the required complexity of logic formulae using properties of algorithms for generation of linear estimators, such as perceptron and maximal percep- tron learning.