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

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

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

DecisionTrees

決策樹教材Section18.3

學(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)Attribute-basedrepresentations以下是12個(gè)基于這10個(gè)屬性描述的例子，屬性值是布爾、離散和連續(xù)的E.g.,situationswhereIwill/won'twaitforatable:Classification（分類）ofexamplesispositive(T)ornegative(F)Decisiontrees一個(gè)可能的假設(shè)表示

E.g.,hereisthe“true”treefordecidingwhethertowait:

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

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

Trivially,thereisaconsistentdecisiontreeforanytrainingsetwithonepathtoleafforeachexample(unlessfnondeterministicinx)butitprobablywon‘tgeneralizetonewexamples

需要找到一顆更緊湊的決策樹Decisiontreelearning目標(biāo):找到一顆小的決策樹來滿足訓(xùn)練樣本Idea:(遞歸地)選擇最佳屬性作為（子）樹的根

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

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

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

1.Usetheoremsofcomputational/statisticallearningtheory

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

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

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

易于構(gòu)造

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

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

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

Example:C4.5

Simpledepth-firstconstruction.

UsesInformationGainKnearestneighborclassifier

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

LearningFrameworkFocusofthispartBinaryclassification(e.g.,predictingspamornotspam):Regression(e.g.,predictinghousingprice):

ClassificationClassification

=learningfromdatawithfinitediscretelabels.DominantprobleminMachineLearning

線性分類器Binaryclassificationcanbeviewedasthetaskof

separatingclassesinfeaturespace（特征空間）:

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

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

h(x)=sign(wTx+b)

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

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

LearningasOptimizationLeastSquaresClassification

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

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

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

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

線性回歸一般的

線性/多項(xiàng)式

回歸模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合欠擬合高偏離模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合過擬合高方差模型復(fù)雜度及過擬合模型復(fù)雜度及過擬合PredictionErrors預(yù)測(cè)誤差Trainingerrors(apparenterrors)—訓(xùn)練誤差

ErrorscommittedonthetrainingsetTesterrors—測(cè)試誤差

ErrorscommittedonthetestsetGeneralizationerrors—泛化誤差

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

IncorporatingModelComplexity基本原理:Ockham’sRazor奧卡姆剃刀原則

Giventwomodelsofsimilargeneralizationerrors,one

shouldpreferthesimplermodeloverthemorecomplexmodel

Acomplexmodelhasagreaterchanceofbeingfitted

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

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

“Simpler”hypothesis

Lesspronetooverfitting

RegularizationL-2andL-1regularizationL-2:easytooptimize,closedformsolutionL-1:sparsity

Morethantwoclasses?Morethantwoclasses評(píng)論最小二乘分類不是分類問題最好的辦法But

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

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

Cross-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-validationCross-validationCross-validationCross-validationLearningFrameworkModel/parameterlearningparadigmChooseamodelclass

NB,kNN,decisiontree,loss/regularizationcombinationModelsel