人工智能10學(xué)習(xí)課件

第10章學(xué)習(xí)第10章學(xué)習(xí)1Supervisedlearning監(jiān)督學(xué)習(xí)Supervisedlearning監(jiān)督學(xué)習(xí)2Supervisedlearning正規(guī)的參數(shù)表示

分類回歸Supervisedlearning正規(guī)的參數(shù)表示

分類回3Classification（分類）WearegivenasetofNobservations{(xi,yi)}i=1..NNeedtomapx∈Xtoalabely∈YExamples:

Classification（分類）Wearegive4DecisionTrees

決策樹教材Section18.3

DecisionTrees

決策樹教材Section185學(xué)習(xí)決策樹Problem:基于以下屬性決定是否在一家餐館等座位:

1.Alternate（別的選擇）:isthereanalternativerestaurantnearby?

2.Bar:isthereacomfortablebarareatowaitin?

3.Fri/Sat:istodayFridayorSaturday?

4.Hungry:arewehungry?

5.Patrons（顧客）:numberofpeopleintherestaurant(None,Some,Full)

6.Price:pricerange($,$$,$$$)

7.Raining:isitrainingoutside?

8.Reservation（預(yù)約）:havewemadeareservation?

9.Type:kindofrestaurant(French,Italian,Thai,Burger)

10.WaitEstimate:estimatedwaitingtime(0-10,10-30,30-60,>60)學(xué)習(xí)決策樹Problem:基于以下屬性決定是否在一家餐館等6Attribute-basedrepresentations以下是12個(gè)基于這10個(gè)屬性描述的例子，屬性值是布爾、離散和連續(xù)的E.g.,situationswhereIwill/won'twaitforatable:Classification（分類）ofexamplesispositive(T)ornegative(F)Attribute-basedrepresentation7Decisiontrees一個(gè)可能的假設(shè)表示

E.g.,hereisthe“true”treefordecidingwhethertowait:

Decisiontrees一個(gè)可能的假設(shè)表示

E.g.,8DecisionTreeLearningDecisionTreeLearning9Expressiveness（表達(dá)能力）決策樹能夠表達(dá)關(guān)于輸入屬性的任何函數(shù)

E.g.,forBooleanfunctions,truthtablerow→pathtoleaf（函數(shù)真值表的每行對(duì)應(yīng)于樹中的一條路徑）:

Trivially,thereisaconsistentdecisiontreeforanytrainingsetwithonepathtoleafforeachexample(unlessfnondeterministicinx)butitprobablywon‘tgeneralizetonewexamples

需要找到一顆更緊湊的決策樹Expressiveness（表達(dá)能力）決策樹能夠表達(dá)關(guān)于輸10Decisiontreelearning目標(biāo):找到一顆小的決策樹來滿足訓(xùn)練樣本Idea:(遞歸地)選擇最佳屬性作為（子）樹的根

Decisiontreelearning目標(biāo):找到一顆11ChoosinganattributeIdea:一個(gè)好的屬性選擇將樣本分割成理想的子集，例如“allpositive”or“allnegative“Patrons?isabetterchoiceChoosinganattributeIdea:一個(gè)好12Usinginformationtheory（信息論）algorithm落實(shí)DTL算法中Choose-Attribute函數(shù)的實(shí)施InformationContent信息量(Entropy熵):

對(duì)于一個(gè)包含p個(gè)正例和n個(gè)反例的訓(xùn)練集：

Usinginformationtheory（信息論）a13Informationgain（信息增益）任何屬性A都可以根據(jù)屬性A的值將訓(xùn)練集E劃分為幾個(gè)子集E1,…,Ev，其中A可以有v個(gè)不同的值從屬性A測(cè)試中得到的信息增益(IG)是原始的信息需求和新的信息需求之間的差異:ChoosetheattributewiththelargestIGInformationgain（信息增益）任何屬性A都可以14信息增益對(duì)于訓(xùn)練集,p=n=6,I(6/12,6/12)=1bit考慮屬性PatronsandType(andotherstoo):PatronshasthehighestIGofallattributesandsoischosenbytheDTLalgorithmastheroot信息增益對(duì)于訓(xùn)練集,p=n=6,I(6/12,15Examplecontd.Decisiontreelearnedfromthe12examples:明顯比前面那顆“true”tree要簡(jiǎn)單得多Examplecontd.Decisiontreele16性能評(píng)估Howdoweknowthath≈f?

1.Usetheoremsofcomputational/statisticallearningtheory

2.Tryhonanewtestset（測(cè)試集）ofexamples

(usesamedistributionoverexamplespaceastrainingset)Learningcurve（學(xué)習(xí)曲線）=%correctontestsetasafunctionoftraining

性能評(píng)估Howdoweknowthath≈f17評(píng)論基于決策樹的分類Advantages:

易于構(gòu)造

在分類位置記錄時(shí)速度快

對(duì)于“小號(hào)”樹易于解釋

在簡(jiǎn)單數(shù)據(jù)集上分類精度相當(dāng)于其他分類算法

Example:C4.5

Simpledepth-firstconstruction.

UsesInformationGain評(píng)論基于決策樹的分類Advantages:

易于構(gòu)造

在分類18Knearestneighborclassifier

最近鄰模型教材Section20.4Linearpredictions線性預(yù)測(cè)

Knearestneighborclassifier

19LearningFrameworkLearningFramework20FocusofthispartBinaryclassification(e.g.,predictingspamornotspam):Regression(e.g.,predictinghousingprice):

FocusofthispartBinaryclass21ClassificationClassification

=learningfromdatawithfinitediscretelabels.DominantprobleminMachineLearning

ClassificationClassification

=22線性分類器Binaryclassificationcanbeviewedasthetaskof

separatingclassesinfeaturespace（特征空間）:

線性分類器Binaryclassificationcan23RoadmapRoadmap24線性分類器 h(x)=sign(wTx+b)需要尋找合適的w(direction)和

b(location)of分界線Wanttominimizetheexpectedzero/oneloss（損失）forclassifierh:X→Y,whichis

h(x)=sign(wTx+b)

理想情況下，完全分割線性分類器 h(x)=sign(wTx+b)25線性分類器→損失最小化理想情況下我們想找到一個(gè)分類器

h(x)=sign(wTx+b)來最小化0/1lossUnfortunately,thisisahardproblem..替換的損失函數(shù):

線性分類器→損失最小化理想情況下我們想找到一個(gè)分類器

h(x26LearningasOptimizationLearningasOptimization27LeastSquaresClassification

最小二乘分類Leastsquareslossfunction:目標(biāo):

學(xué)習(xí)一個(gè)分類器h(x)=sign(wTx+b)來使最小二乘損失最小

LeastSquaresClassification

最28最小二乘分類解決方案最小二乘分類解決方案29W解決方案W解決方案30通用的線性分類通用的線性分類31Regression（回歸）Regression

=learningfromcontinuouslylabeleddata.（連續(xù)的標(biāo)簽數(shù)據(jù)）

Regression（回歸）Regression

=lea32線性回歸線性回歸33一般的

線性/多項(xiàng)式

回歸一般的線性/多項(xiàng)式回歸34模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合35模型復(fù)雜度及過擬合欠擬合高偏離模型復(fù)雜度及過擬合欠擬合36模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合37模型復(fù)雜度及過擬合過擬合高方差模型復(fù)雜度及過擬合過擬合38模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合39模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合40PredictionErrors預(yù)測(cè)誤差Trainingerrors(apparenterrors)—訓(xùn)練誤差

ErrorscommittedonthetrainingsetTesterrors—測(cè)試誤差

ErrorscommittedonthetestsetGeneralizationerrors—泛化誤差

Expectederrorofamodeloverrandomselectionofrecordsfromsamedistribution（未知記錄上的期望誤差）PredictionErrors預(yù)測(cè)誤差Training41模型復(fù)雜度及過擬合欠擬合:whenmodelistoosimple,bothtrainingandtesterrorsarelarge過擬合:whenmodelistoocomplex,trainingerrorissmallbuttesterrorislarge

模型復(fù)雜度及過擬合欠擬合:whenmodelisto42IncorporatingModelComplexity基本原理:Ockham’sRazor奧卡姆剃刀原則

Giventwomodelsofsimilargeneralizationerrors,one

shouldpreferthesimplermodeloverthemorecomplexmodel

Acomplexmodelhasagreaterchanceofbeingfitted

accidentallybyerrorsindata復(fù)雜的模型在擬合上更容易受錯(cuò)誤數(shù)據(jù)誤導(dǎo)

因此在評(píng)估一個(gè)模型時(shí)需要考慮其模型復(fù)雜度IncorporatingModelComplexity43Regularization（規(guī)范化）直觀的:smallvaluesforparameters

“Simpler”hypothesis

Lesspronetooverfitting

Regularization（規(guī)范化）直觀的:small44RegularizationRegularization45L-2andL-1regularizationL-2:easytooptimize,closedformsolutionL-1:sparsity

L-2andL-1regularizationL-2:46Morethantwoclasses?Morethantwoclasses?47MorethantwoclassesMorethantwoclasses48評(píng)論最小二乘分類不是分類問題最好的辦法But

易于訓(xùn)練,closedformsolution（閉式解）

可以與很多經(jīng)典的學(xué)習(xí)原理相結(jié)合

評(píng)論最小二乘分類不是分類問題最好的辦法49Cross-validation（交叉驗(yàn)證）基本思想:如果一個(gè)模型有一些過擬合（對(duì)訓(xùn)練數(shù)據(jù)敏感），那么這個(gè)模型是不穩(wěn)定的。也就是說移除部分?jǐn)?shù)據(jù)會(huì)顯著地改變擬合結(jié)果。因此我們先取出部分?jǐn)?shù)據(jù)，在剩余數(shù)據(jù)中做擬合，然后在取出的數(shù)據(jù)中做測(cè)試Cross-validation（交叉驗(yàn)證）基本思想:如果50Cross-validationCross-validation51Cross-validationCross-validation52Cross-validationCross-validation53Cross-validationCross-validation54LearningFrameworkLearningFramework55Model/parameterlearningparadigmChooseamodelclass

NB,kNN,decisiontree,loss/regularizationcombinationModelselection

CrossvalidationTraining

OptimizationTesting

Model/parameterlearningparad56SummarySupervisedlearning

(1)Classification

Na?veBayesmodel

Decisiontree

Leastsquaresclassification

(2)Regression

Leastsquaresregression

SummarySupervisedlearning

(1)57課后思考題試證明對(duì)于不含沖突數(shù)據(jù)（即特征向量完全相同但標(biāo)記不同）的訓(xùn)練集，必存在與訓(xùn)練集一致（即訓(xùn)練誤差為0）的決策樹。

課后思考題試證明對(duì)于不含沖突數(shù)據(jù)（即特征向量完全相同但標(biāo)記不58第10章學(xué)習(xí)第10章學(xué)習(xí)59Supervisedlearning監(jiān)督學(xué)習(xí)Supervisedlearning監(jiān)督學(xué)習(xí)60Supervisedlearning正規(guī)的參數(shù)表示

分類回歸Supervisedlearning正規(guī)的參數(shù)表示

分類回61Classification（分類）WearegivenasetofNobservations{(xi,yi)}i=1..NNeedtomapx∈Xtoalabely∈YExamples:

Classification（分類）Wearegive62DecisionTrees

決策樹教材Section18.3

DecisionTrees

決策樹教材Section1863學(xué)習(xí)決策樹Problem:基于以下屬性決定是否在一家餐館等座位:

1.Alternate（別的選擇）:isthereanalternativerestaurantnearby?

2.Bar:isthereacomfortablebarareatowaitin?

3.Fri/Sat:istodayFridayorSaturday?

4.Hungry:arewehungry?

5.Patrons（顧客）:numberofpeopleintherestaurant(None,Some,Full)

6.Price:pricerange($,$$,$$$)

7.Raining:isitrainingoutside?

8.Reservation（預(yù)約）:havewemadeareservation?

9.Type:kindofrestaurant(French,Italian,Thai,Burger)

10.WaitEstimate:estimatedwaitingtime(0-10,10-30,30-60,>60)學(xué)習(xí)決策樹Problem:基于以下屬性決定是否在一家餐館等64Attribute-basedrepresentations以下是12個(gè)基于這10個(gè)屬性描述的例子，屬性值是布爾、離散和連續(xù)的E.g.,situationswhereIwill/won'twaitforatable:Classification（分類）ofexamplesispositive(T)ornegative(F)Attribute-basedrepresentation65Decisiontrees一個(gè)可能的假設(shè)表示

E.g.,hereisthe“true”treefordecidingwhethertowait:

Decisiontrees一個(gè)可能的假設(shè)表示

E.g.,66DecisionTreeLearningDecisionTreeLearning67Expressiveness（表達(dá)能力）決策樹能夠表達(dá)關(guān)于輸入屬性的任何函數(shù)

E.g.,forBooleanfunctions,truthtablerow→pathtoleaf（函數(shù)真值表的每行對(duì)應(yīng)于樹中的一條路徑）:

Trivially,thereisaconsistentdecisiontreeforanytrainingsetwithonepathtoleafforeachexample(unlessfnondeterministicinx)butitprobablywon‘tgeneralizetonewexamples

需要找到一顆更緊湊的決策樹Expressiveness（表達(dá)能力）決策樹能夠表達(dá)關(guān)于輸68Decisiontreelearning目標(biāo):找到一顆小的決策樹來滿足訓(xùn)練樣本Idea:(遞歸地)選擇最佳屬性作為（子）樹的根

Decisiontreelearning目標(biāo):找到一顆69ChoosinganattributeIdea:一個(gè)好的屬性選擇將樣本分割成理想的子集，例如“allpositive”or“allnegative“Patrons?isabetterchoiceChoosinganattributeIdea:一個(gè)好70Usinginformationtheory（信息論）algorithm落實(shí)DTL算法中Choose-Attribute函數(shù)的實(shí)施InformationContent信息量(Entropy熵):

對(duì)于一個(gè)包含p個(gè)正例和n個(gè)反例的訓(xùn)練集：

Usinginformationtheory（信息論）a71Informationgain（信息增益）任何屬性A都可以根據(jù)屬性A的值將訓(xùn)練集E劃分為幾個(gè)子集E1,…,Ev，其中A可以有v個(gè)不同的值從屬性A測(cè)試中得到的信息增益(IG)是原始的信息需求和新的信息需求之間的差異:ChoosetheattributewiththelargestIGInformationgain（信息增益）任何屬性A都可以72信息增益對(duì)于訓(xùn)練集,p=n=6,I(6/12,6/12)=1bit考慮屬性PatronsandType(andotherstoo):PatronshasthehighestIGofallattributesandsoischosenbytheDTLalgorithmastheroot信息增益對(duì)于訓(xùn)練集,p=n=6,I(6/12,73Examplecontd.Decisiontreelearnedfromthe12examples:明顯比前面那顆“true”tree要簡(jiǎn)單得多Examplecontd.Decisiontreele74性能評(píng)估Howdoweknowthath≈f?

1.Usetheoremsofcomputational/statisticallearningtheory

2.Tryhonanewtestset（測(cè)試集）ofexamples

(usesamedistributionoverexamplespaceastrainingset)Learningcurve（學(xué)習(xí)曲線）=%correctontestsetasafunctionoftraining

性能評(píng)估Howdoweknowthath≈f75評(píng)論基于決策樹的分類Advantages:

易于構(gòu)造

在分類位置記錄時(shí)速度快

對(duì)于“小號(hào)”樹易于解釋

在簡(jiǎn)單數(shù)據(jù)集上分類精度相當(dāng)于其他分類算法

Example:C4.5

Simpledepth-firstconstruction.

UsesInformationGain評(píng)論基于決策樹的分類Advantages:

易于構(gòu)造

在分類76Knearestneighborclassifier

最近鄰模型教材Section20.4Linearpredictions線性預(yù)測(cè)

Knearestneighborclassifier

77LearningFrameworkLearningFramework78FocusofthispartBinaryclassification(e.g.,predictingspamornotspam):Regression(e.g.,predictinghousingprice):

FocusofthispartBinaryclass79ClassificationClassification

=learningfromdatawithfinitediscretelabels.DominantprobleminMachineLearning

ClassificationClassification

=80線性分類器Binaryclassificationcanbeviewedasthetaskof

separatingclassesinfeaturespace（特征空間）:

線性分類器Binaryclassificationcan81RoadmapRoadmap82線性分類器 h(x)=sign(wTx+b)需要尋找合適的w(direction)和

b(location)of分界線Wanttominimizetheexpectedzero/oneloss（損失）forclassifierh:X→Y,whichis

h(x)=sign(wTx+b)

理想情況下，完全分割線性分類器 h(x)=sign(wTx+b)83線性分類器→損失最小化理想情況下我們想找到一個(gè)分類器

h(x)=sign(wTx+b)來最小化0/1lossUnfortunately,thisisahardproblem..替換的損失函數(shù):

線性分類器→損失最小化理想情況下我們想找到一個(gè)分類器

h(x84LearningasOptimizationLearningasOptimization85LeastSquaresClassification

最小二乘分類Leastsquareslossfunction:目標(biāo):

學(xué)習(xí)一個(gè)分類器h(x)=sign(wTx+b)來使最小二乘損失最小

LeastSquaresClassification

最86最小二乘分類解決方案最小二乘分類解決方案87W解決方案W解決方案88通用的線性分類通用的線性分類89Regression（回歸）Regression

=learningfromcontinuouslylabeleddata.（連續(xù)的標(biāo)簽數(shù)據(jù)）

Regression（回歸）Regression

=lea90線性回歸線性回歸91一般的

線性/多項(xiàng)式

回歸一般的線性/多項(xiàng)式回歸92模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合93模型復(fù)雜度及過擬合欠擬合高偏離模型復(fù)雜度及過擬合欠擬合94模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合95模型復(fù)雜度及過擬合過擬合高方差模型復(fù)雜度及過擬合過擬合96模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合97模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合98PredictionErrors預(yù)測(cè)誤差Trainingerrors(apparenterrors)—訓(xùn)練誤差

ErrorscommittedonthetrainingsetTesterrors—測(cè)試誤差

ErrorscommittedonthetestsetGeneralizationerrors—泛化誤差

Expectederrorofamodeloverrandomselectionofrecordsfromsamedistribution（未知記錄上的期望誤差）PredictionErrors預(yù)測(cè)誤差Training99模型復(fù)雜度及過擬合欠擬合:whenmodelistoosimple,bothtrainingandtesterrorsarelarge過擬合:whenmodelistoocomplex,trainingerrorissmallbuttesterrorislarge

模型復(fù)雜度及過擬合欠擬合:whenmodelisto100IncorporatingModelComplexity基本原理:Ockham’sRazor奧卡姆剃刀原則

Giventwomodelsofsimilargeneralizationerrors,one

shouldpreferthesimplermodeloverthemorecomplexmodel

Acomplexmodelhasagreaterchanceofbeingfitted

accidentallybyerrorsindata復(fù)雜的模型在擬合上更容易受錯(cuò)誤數(shù)據(jù)誤導(dǎo)

因此在評(píng)估