Support vector machine learning algorithm and transduction (Q1584173)

In many problems of pattern recognition and regression analysis a program must be capable of learning from known examples (represented by feature vectors with corresponding labels) and extrapolating to predict a new unknown (unlabeled) example. Various techniques have been developed over the years to enable programs to perform this function including discriminant analysis, neural networks, genetic algorithms and support vector machine. Learning machines based on the theory of machine learning often perform well in a wide range of applications without requiring any parametric statistical assumptions about the source of data (unlike traditional statistical techniques); the only assumption made is the i.i. d. assumption (the examples are generated from the same probability distribution independently of each other). One of the recent algorithms developed under this assumption is Support Vector Machine (SVM), where mathematical optimization techniques are used for labelling new examples. It can be used for solving extremely high- dimensional problems which are infeasible for the previously known learning machines. This paper first reviews the basic ideas of support vector machine and demonstrates the use of the kernel technique that allows high-dimensional problems to be solved. It then shows that the same kernel technique can be applied to classical algorithms such as Ridge Regression. A typical drawback of the techniques such as SVM is that they do not provide any measure of confidence in the predicted label output by the program. A user of such data labelling technique just hopes that the accuracy of the results from previous analyses using benchmark data sets is representative of the results to be obtained from the analysis of future data sets. In the final part of the paper a transductive learning algorithm that also allows to compute confidence levels is presented. This is based on practical approximations to universal measures of confidence that are given by algorithmic information theory.