A Brief Introduction into Machine Learning

1 A Brief Introduction into Machine LearningGunnar R atschFriedrich Miescher Laboratory of the Max Planck Society,Spemannstra e 37, 72076 T ubingen, raetsch1 IntroductionThe Machine Learning field evolved from the broad field ofArtificial Intelligence,which aims to mimic intelligent abilities of humans by machines. In the field ofMa-chine Learningone considers the important question of how to make machines ableto learn . Learning in this context is understood asinductive inference, where oneobservesexamplesthat represent incomplete information about some statistical phe-nomenon . Inunsupervisedlearning one typically tries to uncover hidden regularities( clusters) or to detect anomalies in the data (for instance some unusual machinefunction or a network intrusion). Insupervised Learning , there is alabelassociatedwith each example.

2 It is supposed to be the answer to a question about the example. Ifthe label is discrete, then the task is calledclassification problem otherwise, for real-valued labels we speak of aregression problem. Based on these examples (includingthe labels), one is particularly interested topredictthe answer for other cases beforethey are explicitly observed. Hence, Learning is not only a question of rememberingbut also ofgeneralization to unseen Supervised ClassificationAn important task in Machine Learning isclassification, also referred to as patternrecognition, where one attempts to build algorithms capable of automatically con-structing methods for distinguishing between different exemplars, based on their dif-ferentiating [1985] described a pattern as the opposite of chaos; it is an entity,vaguely defined, that could be given a name.

3 Examples of patterns are human faces,text documents, handwritten letters or digits, EEG signals, and the DNA sequences thatmay cause a certain disease. More formally, the goal of a (supervised) classificationtask is to find a functional mapping between the input dataX, describing the inputpattern, to a class labelY( 1or+1), such thatY=f(X). The construction ofthe mapping is based on so-calledtraining datasupplied to the classification aim is to accurately predict the correct label on unseen pattern (also: example ) is described by itsfeatures. These are the characteris-tics of the examples for a given problem. For instance, in a face recognition task somefeatures could be the color of the eyes or the distance between the eyes. Thus, the input1to a pattern recognition task can be viewed as a two-dimensional matrix, whose axesare the examples and the classification tasks are often divided into several sub-tasks:1.

4 Data collection and Feature selection and/or feature collection and representation are mostly problem-specific. Therefore it is difficultto give general statements about this step of the process. In broad terms, one shouldtry to find invariant features, that describe the differences in classes as best as selection and feature reduction attempt to reduce the dimensionality ( number of features) for the remaining steps of the task. Finally, the classificationphase of the process finds the actual mapping between patterns and labels (or targets).In many applications the second step is not essential or is implicitly performed in thethird Classification AlgorithmsAlthough Machine Learning is a relatively young field of research, there exist morelearning algorithms than I can mention in this Introduction . I chose to describe sixmethods that I am frequently using when solving data analysis tasks (usually classifi-cation).

5 The first four methods are traditional techniques that have been widely usedin the past and work reasonably well when analyzing low dimensional data sets withnot too few labeled training examples. In the second part I will briefly outline twomethods (Support Vector Machines & Boosting) that have received a lot of attention inthe Machine Learning community recently. They are able to solve high-dimensionalproblems with very few examples ( fifty) quite accurately and also work efficientlywhen examples are abundant (for instance several hundred thousands of examples). Traditional Techniquesk-Nearest Neighbor ClassificationArguably the simplest method is thek-NearestNeighborclassifier [Cover and Hart, 1967]. Here thekpoints of the training dataclosest to the test point are found, and a label is given to the test point by a majorityvote between thekpoints.

6 This method is highly intuitive and attains given itssimplicity remarkably low classification errors, but it is computationally expensiveand requires a large memory to store the training Discriminant Analysiscomputes a hyperplane in the input space that min-imizes the within-class variance and maximizes the between class distance [Fisher,1936]. It can be efficiently computed in the linear case even with large data sets. How-ever, often a linear separation is not sufficient. Nonlinear extensions by using kernelsexist [Mika et al., 2003], however, making it difficult to apply it to problems with largetraining TreesAnother intuitive class of classification algorithms aredecision algorithms solve the classification problem by repeatedly partitioning the in-2put space, so as to build a tree whose nodesare as pure as possible (that is, they containpoints of a single class).

7 Classification of anew test point is achieved by moving from topto bottom along the branches of the tree, start-ing from the root node, until a terminal node isreached. Decision trees are simple yet effec-tive classification schemes for small computational complexity scales unfa-vorably with the number of dimensions of thedata. Large datasets tend to result in compli-cated trees, which in turn require a large mem-Figure 1:An example a decision tree (Figuretaken from Yom-Tov [2004]).ory for storage. The implementation by Quinlan [1992] is frequently used andcan be downloaded Networksare perhaps one of the most commonly used approaches to clas-sification. Neural networks (suggested first by Tur-ing [1992]) are a computational model inspired bythe connectivity of neurons in animate nervous sys-tems.

8 A further boost to their popularity came with theproof that they can approximate any function mappingvia the Universal Approximation Theorem [Haykin,1999].A simple scheme for a neural network isshown in Figure 2. Each circle denotes a computa-tional element referred to as aneuron, which computesa weighted sum of its inputs, and possibly performs anonlinear function on this sum. If certain classes ofnonlinear functions are used, the function computedby the network can approximate any function (specif-Figure 2:A schematic diagram of aneural network. Each circle in thehidden and output layer is a compu-tational element known as a neuron.(Figure taken from Yom-Tov [2004])ically a mapping from the training patterns to the training targets), provided enoughneurons exist in the network and enough training examples are Large Margin AlgorithmsMachine Learning rests upon the theoretical foundation ofStatistical Learning Theory[ Vapnik, 1995] which provides conditions and guarantees for good generalizationof Learning algorithms.

9 Within the last decade,large margin classification techniqueshave emerged as a practical result of the theory of generalization. Roughly speaking,the margin is the distance of the example to the separation boundary and a large mar-gin classifier generates decision boundaries with large margins to almost all trainingexamples. The two most widely studied classes of large margin classifiers areSupportVector Machines(SVMs) [Boser et al., 1992, Cortes and Vapnik, 1995] andBoosting[Valiant, 1984, Schapire, 1992]:Support Vector Machineswork by mapping the training data into a feature spaceby the aid of a so-called kernel function and then separating the data using alargemargin hyperplane(cf. Algorithm 1). Intuitively, the kernel computes a similarity3between two given examples. Most commonly used kernel functions areRBF kernelsk(x,x ) = exp( x x 2 2)andpolynomial kernelsk(x,x ) = (x x ) SVM finds a large margin separation between the training examples and pre-viously unseen examples will often be close to the training examples.

10 Hence, the largemargin then ensures that these examples are correctly classified as well, , the deci-sion rulegeneralizes. For so-calledpositive definitekernels, the optimization problemcan be solved efficiently and SVMs have an interpretation as a hyperplane separationin a high dimensional feature space [Vapnik, 1995, M uller et al., 2001, Sch olkopf andSmola, 2002]. Support Vector Machines have been used on million dimensional datasets and in other cases with more than a million examples [Mangasarian and Musi-cant, 2001]. Research papers and implementations can be downloaded from the kernelmachines web- 1 The Support Vector Machine with regularization labeled sequences(x1,y1),..,(xm,ym)(x Xandy { 1,+1}) and akernelk, the SVM computes a functionf(s) =m i=1 ik(xi,x) +b,where the coefficients iandbare found by solving the optimization problemminimize mi,j=1 i jk(si,sj) +C mi=1 isubject toyif(xi) 1 iBoostingThe basic idea of boosting andensemble Learning algorithmsin general isto iteratively combine relatively simplebase hypotheses sometimes calledrules ofthumb for the final prediction.