机器学习概论机器学习概论 (9).pdf

《机器学习概论机器学习概论 (9).pdf》由会员分享，可在线阅读，更多相关《机器学习概论机器学习概论 (9).pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1The final topic:Introduction to Machine Learning overview introduction to machine learning:overview2Overview Basic concepts Machine learning approaches 2019/6/102I.Basic Concepts introduction to machine learning:overview4Whats machine learning？2019/6/103introduction to machine learning:overview5Wha

2、ts machine learning?Learning=improving with experience at some taskT（Task）P（Performance）E（Experience）introduction to machine learning:overview7A generic system System1x2xNx1y2yMy12,.,Kh hh()12,.,Nx xx=x()12,.,Kh hh=h()12,.,Ky yy=yInput Variables:Hidden Variables:Output Variables:Control Parameterse,

3、d2019/6/104II.Machine learning approachesintroduction to machine learning:overview9The branches of machine learningSupervised LearningUnsupervised LearningSemi-supervised LearningTransfer Learning2019/6/105SupervisedUnsupervisedInstances for learning(X,Y)pair,usually with human involvementX only,usu

4、ally without humaninvolvementGoal of learningLearning relation between X and YLearning structure of XMeasure of successLoss functionNo ApplicationPrediction:X=input,Y=outputAnalysis:X=inputintroduction to machine learning:unsupervised learning10Supervised and Unsupervised LearningSupervisedUnsupervi

5、sedInstances for learning(X,Y)pair,usually with human involvementX only,usually without humaninvolvementGoal of learningLearning relation between X and YLearning structure of XMeasure of successLoss functionNo ApplicationPrediction:X=input,Y=outputAnalysis:X=inputintroduction to machine learning:uns

6、upervised learning11Supervised and Unsupervised Learning2019/6/106SupervisedUnsupervisedInstances for learning(X,Y)pair,usually with human involvementX only,usually without humaninvolvementGoal of learningLearning relation between X and YLearning structure of XMeasure of successLoss functionNo Appli

7、cationPrediction:X=input,Y=outputAnalysis:X=inputintroduction to machine learning:unsupervised learning12Supervised and Unsupervised Learningintroduction to machine learning:overview13SupervisedUnsupervisedInstances for learning(X,Y)pair,usually with human involvementX only,usually without humaninvo

8、lvementGoal of learningLearning relation between X and YLearning structureof XMeasure of successLoss functionNo ApplicationPrediction:X=input,Y=outputAnalysis:X=inputSupervised and Unsupervised Learning2019/6/107II.Machine learning approaches(part I)Supervised Learningintroduction to machine learnin

9、g:overview15Supervised learningLearning ModulePrediction Modulennyyyxxx!2121?1+ny)|(XYPKnowledge1+nxY is simpleX is complex2019/6/108introduction to machine learning:overview16A1.Decision treelData effectively modeled via decision splits on attributesX3Y5-1+1-1noyesyesnoXY35+1-1-1introduction to mac

10、hine learning:overview17Decision tree:use concepts/rules to represent hypothesisIntuitional,easy to get the explanation of the data by the learned hypothesisBut what if we cannot find the obvious rules for the observed data?Using statistical approachesUsing statistical approaches2019/6/109introducti

11、on to machine learning:overview18A2.Bayesian LearningCondition Resulte.g.pneumonia lung cancer?Hard to tell directlyReversed thinking (Result Causal)e.g.How many lung cancer patients have suffered from pneumonia?introduction to machine learning:overview19Bayesian LearningBayes theoremUse prior proba

12、bility to inference posterior probabilityMax A Posterior,MAP,hMAP，极大后验假设Generally we want the most probable hypothesis given the training dataMaximum Likelihood,ML,hML,极大似然假设The smart man always learns the most from experiences if he knows p(h)ML vs.LSE(Least Square Error)Nave Bayes,NB,朴素贝叶斯Independ

13、ent assumptionNB vs.MAPMinimum description length,MDL,最小描述长度Tradeoff:hypothesis complexity vs.errors by hMDL vs.MAP)()()|()|(DPhPhDPDhP=2019/6/1010introduction to machine learning:overview20A3.HMMWhat if the observed data is indirect evidence?hidden state existsProperty 1：Markov assumptionp(Xi|Xi-1X

14、1)=p(Xi|Xi-1)Property 2：time invariance assumptionp(Xi+1|Xi)=p(Xj+1|Xj)，for any i,jProperty 3：independent observation assumptionp(O1,.,OT|X1,.,XT)=p(Ot|Xt)oTo1otot-1ot+1ABAAABBBBintroduction to machine learning:overview21HMM basic Problem1 EstimationEstimation problem:Compute the probability of a gi

15、ven observation sequence p(|)Define forward variable,backward variableDynamic programming forward algorithm,O(N2T)111.()()tttijjoiNji a baa+=NiTiOP1)()|(aoTo1otot-1ot+1x1xt+1xTxtxt-12019/6/1011introduction to machine learning:overview22HMM basic Problem2 DecodingGiven an observation sequence,compute

16、 the most likely hidden statesequenceDynamic programming Viterbi algorithm,O(N2T)）（1)(max)(1+=+tjoijtitbaijdd）（1)(maxarg)(1+=+tjoijtitbaijdy),.,.(max)(1111.11ttttxxtojxooxxPjt=-doTo1otot-1ot+1x1xt-1xtxt+1xTintroduction to machine learning:overview23What weve learned from HMMHMMSSSKKKSKSKAAAABBBWe us

17、e the special structure of this model to do a lot of neat math and solve problems that are otherwise not solvable.2019/6/1012A4.Kernel methods and Non-linear SVMintroduction to machine learning:overview24Maximize the marginDefine:the margin of a linear classifier as the width that the boundary could

18、 be increased by before hitting a data pointMaximize the marginNon-separable Caseintroduction to machine learning:overview25Minimizing training error2019/6/1013Non-linear SVMintroduction to machine learning:overview26Input space feature spaceNon-linear in low dim.linear Hyperplane in higher mon kern

19、elsSoftwareLIBSVM http:/www.csie.ntu.edu.tw/cjlin/libsvmSVMlighthttp:/svmlight.joachims.orgintroduction to machine learning:overview27Previous learning approachesEstimate the characteristics(e.g.distribution)Make an assumption to the modelFind the optimal parameter Is there a learning approach that

20、is NOT“model assumption+parameter estimation”?But sometimes,we know nothing before learning2019/6/1014introduction to machine learning:overview28A5.k-Nearest Neighbor(KNN)1-Nearest Neighbor3-Nearest NeighborP1P2P3P4P5P6P7P8PnP1P2P3P4P5P6P7P8PnlThinking is reminding,making analogiesl One takes the be

21、havior of ones company“近朱者赤，近墨者黑”introduction to machine learning:overview29KNNMain assumptionAn effective distance metric existsNonparametricConceptually simple,yet can model any functionlMemory costlCPU costlFeature selection problemlIrrelevant features have negative impact on the distance metricl

22、Sensitive to representation2019/6/1015More on efficiency KD-Tree(Construction)We will keep around one additional piece of information at each node:The(tight)bounds of the points at or below this node.introduction to machine learning:overview30Each time a new closest node is found,we can update the d

23、istance bounds.More on efficiency KD-Tree(Query)introduction to machine learning:overview312019/6/1016Using the distance bounds and the bounds of the data below each node,we can prune parts of the tree that could NOT include the nearest neighbor.introduction to machine learning:overview32More on eff

24、iciency KD-Tree(Query)introduction to machine learning:overview33A memory based learner:4 factors1.A distance metricEuclidian/Scaled Euclidian/2.How many nearby neighbors to look at?1,k or all3.A weighting function(optional)wi=exp(-D(xi,query)2/Kw2)4.How to fit with the local points?Nearest neighbor

25、,orVoting among K neighbors,orThe weighted average of the outputs predict=wiyi/wi2019/6/1017II.Machine learning approaches(part II)Unsupervised Learningintroduction to machine learning:overview35Unsupervised learningLearning ModulePrediction Modulenxxx!21?1+nx)(XPKnowledgeX is complexBuild a model o

26、r find useful representations of the input that can be used for decision making,predicting future inputs,efficiently communicating the inputs to another machine,etcFind patterns(discover the structure)in the data above and beyond what would be considered pure unstructured noise.2019/6/1018What are g

27、ood clusters?introduction to machine learning:overview36The intra-cluster distance is smallThe inter-cluster distance is largeintroduction to machine learning:overview37Update the cluster means012345678910012345678910Update the cluster meansAssign each objects to most similar centerA6.K-Means0123456

28、78910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerreassignreassignDo loopUntil no change2019/6/1019introduction to machine learning:overview38012345678910012345678910Total Cost=200123456789100123456789K=20

29、12345678910012345678910Assign each object to nearest medoidsRandomly select a non-medoid object,OrandomCompute total cost012345678910012345678910Cost=26Not swapSwapping O and OrandomIf quality is improved.Do loopUntil no change012345678910012345678910A7.K-Medoids10Arbitrary choose k object as initial medoidsintroduction to machine learning:overview39124567893A8.Hierarchical Clustering(Agglomerative)