A Unified Framework for Regularization Networks and Support Vector Machines

Regularization Networks and Support Vector Machines are techniques for solving certain problems of learning from examples -- in particular the regression problem of approximating a multivariate function from sparse data. We present both formulations in a unified framework, namely in the context of Vapnik's theory of statistical learning which provides a general foundation for the learning problem, combining functional analysis and statistics.

Support Vector Machines: Training and Applications

The Support Vector Machine (SVM) is a new and very promising classification technique developed by Vapnik and his group at AT&T Bell Labs. This new learning algorithm can be seen as an alternative training technique for Polynomial, Radial Basis Function and Multi-Layer Perceptron classifiers. An interesting property of this approach is that it is an approximate implementation of the Structural Risk Minimization (SRM) induction principle. The derivation of Support Vector Machines, its relationship with SRM, and its geometrical insight, are discussed in this paper. Training a SVM is equivalent to solve a quadratic programming problem with linear and box constraints in a number of variables equal to the number of data points. When the number of data points exceeds few thousands the problem is very challenging, because the quadratic form is completely dense, so the memory needed to store the problem grows with the square of the number of data points. Therefore, training problems arising in some real applications with large data sets are impossible to load into memory, and cannot be solved using standard non-linear constrained optimization algorithms. We present a decomposition algorithm that can be used to train SVM's over large data sets. The main idea behind the decomposition is the iterative solution of sub-problems and the evaluation of, and also establish the stopping criteria for the algorithm. We present previous approaches, as well as results and important details of our implementation of the algorithm using a second-order variant of the Reduced Gradient Method as the solver of the sub-problems. As an application of SVM's, we present preliminary results we obtained applying SVM to the problem of detecting frontal human faces in real images.

A Note on Support Vector Machines Degeneracy

When training Support Vector Machines (SVMs) over non-separable data sets, one sets the threshold $b$ using any dual cost coefficient that is strictly between the bounds of $0$ and $C$. We show that there exist SVM training problems with dual optimal solutions with all coefficients at bounds, but that all such problems are degenerate in the sense that the "optimal separating hyperplane" is given by ${f w} = {f 0}$, and the resulting (degenerate) SVM will classify all future points identically (to the class that supplies more training data). We also derive necessary and sufficient conditions on the input data for this to occur. Finally, we show that an SVM training problem can always be made degenerate by the addition of a single data point belonging to a certain unboundedspolyhedron, which we characterize in terms of its extreme points and rays.

Exploring Bit-Difference for Approximate KNN Search in High-dimensional Databases

In this paper, we develop a novel index structure to support efficient approximate k-nearest neighbor (KNN) query in high-dimensional databases. In high-dimensional spaces, the computational cost of the distance (e.g., Euclidean distance) between two points contributes a dominant portion of the overall query response time for memory processing. To reduce the distance computation, we first propose a structure (BID) using BIt-Difference to answer approximate KNN query. The BID employs one bit to represent each feature vector of point and the number of bit-difference is used to prune the further points. To facilitate real dataset which is typically skewed, we enhance the BID mechanism with clustering, cluster adapted bitcoder and dimensional weight, named the BID⁺. Extensive experiments are conducted to show that our proposed method yields significant performance advantages over the existing index structures on both real life and synthetic high-dimensional datasets.

Aitchison Geometry for Probability and Likelihood as a new approach to mathematical statistics

The Aitchison vector space structure for the simplex is generalized to a Hilbert space structure A2(P) for distributions and likelihoods on arbitrary spaces. Central notations of statistics, such as Information or Likelihood, can be identified in the algebraical structure of A2(P) and their corresponding notions in compositional data analysis, such as Aitchison distance or centered log ratio transform. In this way very elaborated aspects of mathematical statistics can be understood easily in the light of a simple vector space structure and of compositional data analysis. E.g. combination of statistical information such as Bayesian updating, combination of likelihood and robust M-estimation functions are simple additions/ perturbations in A2(Pprior). Weighting observations corresponds to a weighted addition of the corresponding evidence. Likelihood based statistics for general exponential families turns out to have a particularly easy interpretation in terms of A2(P). Regular exponential families form finite dimensional linear subspaces of A2(P) and they correspond to finite dimensional subspaces formed by their posterior in the dual information space A2(Pprior). The Aitchison norm can identified with mean Fisher information. The closing constant itself is identified with a generalization of the cummulant function and shown to be Kullback Leiblers directed information. Fisher information is the local geometry of the manifold induced by the A2(P) derivative of the Kullback Leibler information and the space A2(P) can therefore be seen as the tangential geometry of statistical inference at the distribution P. The discussion of A2(P) valued random variables, such as estimation functions or likelihoods, give a further interpretation of Fisher information as the expected squared norm of evidence and a scale free understanding of unbiased reasoning

Using zappers in Common Learning Spaces (Windows XP)

This resource is now obsolete and has been replaced by http://www.edshare.soton.ac.uk/5920/ This PowerPoint is an animated step-by-step guide that shows tutors how to use zappers in a teaching session. It covers starting the PC, distributing the zappers, plugging in the receiver, starting the software, running the presentation and managing voting, saving data at the end and collecting the handsets. It takes around 5 minutes to view.

Lecture notes pdf

Lecture notes in PDF

Lecture notes

Lecture notes in LaTex

Vector Fields

Exercises and solutions about vector fields. Diagrams for the questions are all together in the support.zip file, as .eps files

Vector Calculus

Exercises and solutions about vector calculus

Vector functions and curves

Exercises and solutions about vector functions and curves.

Uffington White Horse vector art files

Vector graphic files for the Uffington White Horse in PDF, AI (Adobe Illustrator EPS) and SVG formats. I manually traced these from a photo using Xara Xtreme.

Large Scale Structure of Metric Spaces

How the mathematical concept of Coarse Geometries is useful to analysing the Web

University Logo in Vector and Raster

This is a selection of University of Southampton Logos in both vector (svg) and raster (png) formats. These are suitable for use on the web or in small documents and posters. You can open the SVG files using inkscape (http://inkscape.org/download/?lang=en) and edit them directly. The University logo should not be modified and attention should be paid to the branding guidelines found here: http://www.edshare.soton.ac.uk/10481 You must always leave a space the width of an capital O in Southampton on all 4 edges of the logo. The negative space makes it appear more prominently on the page.

University Logo in Vector and Raster (Smoother Version)

These are a range of logos created in the same way as Mr Patrick McSweeny http://www.edshare.soton.ac.uk/11157. The logo has been extracted from PDF documents and is smoother and accurate to the original logo design. Many thanks to to McSweeny for publishing the logo, in SVG originally, I struggled to find it anywhere else. Files are in Inkscape SVG, PDF and PNG. From Mr Patrick McSweeney: This is a selection of University of Southampton Logos in both vector (svg) and raster (png) formats. These are suitable for use on the web or in small documents and posters. You can open the SVG files using inkscape (http://inkscape.org/download/?lang=en) and edit them directly. The University logo should not be modified and attention should be paid to the branding guidelines found here: http://www.edshare.soton.ac.uk/10481 You must always leave a space the width of an capital O in Southampton on all 4 edges of the logo. The negative space makes it appear more prominently on the page.