统计机器学习的基础知识

Basic of Statistical Learning Theory1The Statistical Learning FrameworkBefore we start learning,we need3things–domain set,label set and training data.Domain set is an arbitrary set X,a set of objects that we may wish to ually,these domain points will be represented by a vector of features.We also refer to domain points as instances and to X as instance bel set is a two-element set in pattern recognition,usually{0,1}or{−1,1}.Let Y denote our set of possible labels.Training data S=((x1,y1)...(x m,y m))is afinite sequence of pairs in X×Y,namely a sequence of labeled domain points.This is the input that the learner has access to and are often called training example,referred to S sometimes.A process of learning can be completed with the3inputs above,resulting in an output,a prediction rule h:X→Y.This function is also called a predictor or a classifier,used to predict the label of new domain ually use notaion A(S)to denote the classifier that a learning algorithm A, returns upon receiving the training sequence S.Training data is very important.We suppose the instances are generated by some probability dis-tribtution.Probability distribtution over X is denoted by D.Learner know nothing about this dis-tribtution,because this may be any arbitrary probability distribution,though there exists a suitable labeling fucntion f:X→Y,which is the target we want.Each pair in the training data S is generated byfirst sampling a point x i according to D and then labeled by f.Pay attention that learner can only learn the world through analyzing the training data.In other words,the learner is blind to the distribution and the labeling function,which can be treated as a white paper with a pen.Assume now we have get a learned labeling function,we are not confident because we don’t know if it is effective.The measurement of its effectiveness is called the error of a classifier.Error is not right,namely,it means the classifier does not predict correctly.More precisely,the error of h is the probability to draw a random instance x,according to the distribtution D,such that h(x)does not equal f(x).Mathematically,we define the error of a prediction rule,h:X→Y,to beL D,f(h)≜P x∼D[h(x)=f(x)]≜D({x:h(x)=f(x)})The subsecript(D,f)means the error is measured with respect to the probability distribtution D and the correct labeling function ually L stands for error,the loss of the learner.Recall loss function L,it is a non-negative function that measures disagreement between its argu-ments.When we have an estimator function f,we use a loss function to measure how well the estimator agrees with data.If we have paired data(x,y),the loss of the estimator is L(f(x),y). Risk R(f,P)is the expected risk for data drawn from distribtution PR(f,P)=E(x,y)∼P[L(f(x),y)]The empirical risk is the average loss of an estimator for afinite set of data drawn from P:R N(f)=1NN∑i=1L(f(x i),y i)The idea of risk minimization is not only measure the performance of an estimator by its risk,but to actually search for the estimator that minimizes risk over distribtution P.f∗=arg minf∈FR(f,P)Naturally,f ∗gives the best expected performance for loss L over the distribtution of any estimator in F .Because we do not know distribtution P we instead minimize empirical risk over a training dataset drawn from Pf †=arg min f ∈FR N (f )This general learning technique is called empirical risk minimization.Under stationarity and other regularity conditions,empirical risk minimizers converge.To prevent overfitting,the risk is often regularized to penalize complex hypotheses,which is called regulationf †=arg min f ∈F[R N (f )+cρ(f )]We have just said the ERM rule might lead to overfitting,which requires us more research.Is there a guarantee that ERM does not overfit in some circumstances?We can apply ERM rule in a restricted search space.Learner should be chose in advance in a set of functions called hypothesis class which is denoted by H .Each h ∈H is a function mapping from X to Y .For a certain H ,and certain training sample S ,the ERM H learner applies the ERM rule in choosing a predictor h ∈H .2PAC LearningThe output will be probably approximately correct if the ERM rule is applied to a sufficiently large traning sample whose size is independent of the underlying distribtution or labeling function,this is PAC learning.More precisely,a hypothesis class H is PAC learnable if there exist a fucntion m H :(0,1)2→N and a learning algorithm with the following property:For every ϵ,δ∈(0,1),for every distribtution D over X ,and for every labeling function f :X →{0,1},if the realizable assumption holds with respect to H ,D ,f ,then when running the learning algorithm on m ≥m H (ϵ,δ)i.i.d.examples generated by D and labeled by f ,the algorithm returns a hypothesis h such that,with probability of at least 1−δ(over the choice of the examples),L (D ,f )(h )≤ϵ.PAC learning includes 2approximation parameters.One is accuracy parameter ϵ,determining how far the output classifier can be from the optimal one,the other is a confidence parameter δindicating how likely the classifier is to meet that accuracy requirement.Since the training set is randomly generated,different training set may give different information,certain training set might give in-effective information.Few training set can cover all the aspects,so the accuracy parameter ϵbears some missing aspects.In our previous example m H :(0,1)2→N ,how many examples are required to guarantee a probably approximately correct solution,namely,how could we find a hypothesis class which is easy enough to learn.We need a quantity to measure its complexity.For finite hypothesis class,if m H (ϵ,δ)≤[log(|H|/δ)ϵ]3Regularization and Cross ValidationA typical way to choose model is regularization,a realization of structure risk minimization,adding a regularizer or penalty term to ERM.Regularizer is a monotonic increasing function of complexity,the more complex model is,the larger regularizer is.For example,regularizer could be a norm of model parameter vector.Mathematically,regularization has the follwing formmin f ∈F 1N N ∑i =1L (y i ,f (x i ))+λJ (f )Regularizer could be different forms.In regression problem,the loss function is squared loss,regu-larizer can be the L 2norm of parameter vector.L (w )=1N N ∑i =1[f (x i ;w )−y i ]2+λ2||w ||2||w||stands for the L2norm of parameter vector.Regularization is satisfied with Occam’s razor.In all the possible models,the one which is the simplest andfit the known data well is the best.Another common way of choosing model is cross validation.If we have enough data sets,a simple way to choose is split these sets in three parts–training set,validation set and test set.But,usually the quantity of sets is not enough,we can use the data over and over again.4Generalization AbilityThe generalization ability is the prediction ability of learner,the most important property of learner, always tested by measuring its uncertainty.This evaluation is based on testing data,so it might be unreliable.Let’sfirst introduce generalization error∫R exp(ˆf)=E P[L(Y,ˆf(X))]=L(y,ˆf(x))P(x,y)d x d yX×YBy researching its upper bound we can analyse its generalization ability.The upper bound of gener-alization error,a function of hypothesis space,is closer to0when the volume of samples is ually,generalization error is as decreasing as training error.5Generative Approach and Discriminative ApproachSupervised learning is studying a model,predcting an output according to its inputP(Y|X)which is divided into generative approach and discriminative approach,the learned model is called generative model and discriminative model repectively.Generative model gets united probability dstribution P(X|Y)by learning data,applying which it learned to predict,including naive Bayes and hidden Markov model.This method has good convergent ability and is applicable to hidden variables.Discriminative approach gets conditional probability dstribution P(X|Y)by learning data directly, including SVM.This method is more precise and much simpler.6Classification ProblemClassification is a core problem in supervised learning when output variable Y has discrete val-ues,while input variable X can be discrete or continuous.A classifier is expected in classification problem,making predictions.Solving classification problem including studying and classifying.In the process of studying,a classifier is generated via training data.In the process classfying,the generated classifier can do its work.The performace of a classifier is measured by accuracy,which is the ratio of correct predictions and total samples.Many statistical learning approach can be used to solve this problem,including naive Bayes and Logistic regression.In bank service,a customer classifier can be constructed to categorize customers by their loan risk.In network security,a log data classifier can inspect illegal invading.In image processing,a classifier can tell if there exiting human face.In hand writing recognition,a classifier can read hand writing nunmbers.7TaggingTagging is also a supervised learning,always treated as a generalized classification problem or an easier form of structure prediction problem.The output of tagging is a state sequence,while theinput is an observation sequence.In learning process,a training data set is givenT={(x1,y1),(x2,y3),···,(x N,y N)}here x i=(x(1)i,x(2)i,···,x(n)i )T is the input.y i=(y(1)i,y(2)i,···,y(n)i)T is the output,n is thelength of the sequence.A model is constructed by a conditional probability distribtutionP(Y(1),Y(2),···,Y(n)|X(1),X(2),···,X(n))Tagging problem is widely used in information extracting and natural language processing.For example,part of speech tagging in natural language processing is a typical tagging problem.Given a sentence composed by words,we need to tag the part of speech for every word.8Regression ProblemRegression is another important problem in supervised learning,predicting the relationship between the input and the output,particularly when the input is variant with output.A mapping function between the input and output is the regression model.In other words,regression is the same as curvefitting,choose a proper function curve tofit the known data and prediction the unknowns. Regression includes learning and prediction.First given a training dataT={(x1,y1),(x2,y2),···,(x N,y N)}x i∈R is input and y∈R is output.A model,function Y=f(X),is constructed based on training data.For new input x N+1,the prediction system gives an output y N+1accordingly.There is single regression and multivariable regression or linear regression and nonlinear regression. Squared loss function is widely used in regression in which there is a famous solution called least squares.Many problems in reality are similar to regression.For example,regression can be applied to busi-ness area,predicting market trending,managing product quality and analysing stock risk.Let us know a little about stock price prediction,suppose we know the price of one company’s stoke price in the past,say,every past day and any information which might perturb the price.The aim is to construct a model based on these information to predict the price of its stock in the following time point,which can be treated as regression.The information affecting stock price is the input variable and the price is output.The known price and past information are training data of the regression.9ConclusionStatistical machine learning is constructing of probability model by analysis of data and predic-tion,which including supervised,non-supervised,semi-supervised learning and reinforced learning. Three important factors in learning are model,strategy and algorithm.Supervised learning is based onfinite training data and a postulation of i.i.d.,applying certain evaluation rule,choosing a best model from hypothesis space,making reasonable prediction in given evaluation rule.。