2020機器學(xué)習(xí)數(shù)學(xué)公式

機器學(xué)習(xí)數(shù)學(xué)公式??錄內(nèi)容提要序前?主要符號表第1第2章模型評估與選擇第3章線性模型第4章決策樹第5章神經(jīng)?絡(luò)第6章?持向量機第7章?葉斯分類器第8章集成學(xué)習(xí)第9章聚類第10章降維與度量學(xué)習(xí)第11章特征選擇與稀疏學(xué)習(xí)第12章計算學(xué)習(xí)理論第13第14第15第16主要符號表主要符號表標量向量變量集矩陣單位陣樣本空間或狀態(tài)空間概率分布數(shù)據(jù)樣本（數(shù)據(jù)集）假設(shè)空間假設(shè)集學(xué)習(xí)算法?向量列向量向量或矩陣轉(zhuǎn)置集合集合中元素個數(shù)范數(shù), 缺省時為L范數(shù)概率質(zhì)量函數(shù),條件概率質(zhì)量函數(shù)概率密度函數(shù),條件概率密度函數(shù)函數(shù))對在分布下的數(shù)學(xué)期望;意義明確時將省略和(或).上確界指?函數(shù),在為真和假時分別取值為1,0符號函數(shù), 在時分別取值為第第1章 緒論式(1.1)參?式(1.2)式(1.2）①③④⑤③ ⑤顯然成?解析① ②：② ③：?先要知道此時我們假設(shè)是任何能將樣本映射到{0,1}函數(shù).存在不??個時，服從均勻分布，即每個出現(xiàn)的概率相等.例如樣本空間只有兩個樣本時，.那么所有可能的真實?標函數(shù)如下：?共個可能的真實?標函數(shù).所以此時通過算法學(xué)習(xí)出來的模型對每個樣本?論預(yù)測值為0還是1，都必然有?半的之預(yù)測值相等.例如，現(xiàn)在學(xué)出來的模型對 的預(yù)測值為1，即，那么有且只有和與的預(yù)測值相等，也就是有且只有?半的與它預(yù)測值相等，所以.值得?提的是，在這?我們假設(shè)真實的?標函數(shù)服從均勻分布但是實際情形并?如此，通常我們只認為能?度擬合已有樣本數(shù)據(jù)的函數(shù)才是真實?標函數(shù)，例如，現(xiàn)在已有的樣本數(shù)據(jù)為，那么此時才是我們認為的真實?標函數(shù)，由于沒有收集到或者壓根不存在這類樣本，所以都不算是真實?標函數(shù).這也就是“??書”式(1.3)下?的第段中“騎???”的例?所想表達的內(nèi)容.第第2章 模型評估與選擇式(2.20）解析在解釋 式之前，需要先弄清楚 曲線的具體繪制過程.下?我們就舉個例?，按照“??書”圖2.4下?給出的繪制?法來講解?曲線的具體繪制過程.假設(shè)我們已經(jīng)訓(xùn)練得到?個學(xué)習(xí)器，現(xiàn)在?該學(xué)習(xí)器來對8個測試樣本（4個正例，4個反例，即）進?預(yù)測，預(yù)測結(jié)為：此處?表?樣本，以和坐標作出區(qū)分其中，和分別表?樣本為正例和為反例，數(shù)字表?學(xué)習(xí)器測該樣本為正例的概率，例如對于反例來說，當前學(xué)習(xí)器預(yù)測它是正例的概率為.上?給出的預(yù)測結(jié)果已經(jīng)按照預(yù)測值從?到?排序根據(jù)“??書”上給出的繪制?法，?先需要對所有測試樣本按照學(xué)習(xí)器給出的預(yù)測結(jié)果進?排序，接著將分類閾值設(shè)為?個不可能取到的最?值.顯然，此時所有樣本預(yù)測為正例的概率都?定?于分類閾值，那么預(yù)測為正例的樣本個數(shù)為0，相應(yīng)的真正例率和假正例率也為0，所以我們可以在坐標處標記?個點.接下來需要把分類閾值從?到?依次設(shè)為每個樣本的預(yù)測值，也就是依次設(shè)為0.77,0.62,,0.33,0.23,0.15，然后分別計算真正例率和假正例率，再在相應(yīng)坐標上標記點，最后再將各個點?直線連接,即可得到 曲線.需要注意的是，在統(tǒng)計預(yù)測結(jié)果時，預(yù)測值等于分類閾值的樣本也被算作預(yù)測為正例.例如，當分類閾值為 時，測試樣本 被預(yù)測為正例，由于它的真實標記也是正例，所以此時 是?個真正例.為了便于繪圖，我們將軸（假正例率軸）的“步?”定，軸（真正例率軸）的“步?”定.根據(jù)真正例率和假正例率的定義可知，每次變動分類閾值時，若新增個假正例，那么相應(yīng)的軸坐標也就增加；若新增個真正例，那么相應(yīng)的軸坐標也就增加.按照以上講述的繪制流程，最終我們可以繪制出如圖2-1所?的 曲線.圖2-1 ROC曲線?意注： 表?紅?線段； 表?藍?線段； 表?綠?線段在這?，為了能在解析式(2.21)時復(fù)?此圖，我們沒有寫上具體的數(shù)值，轉(zhuǎn)??其數(shù)學(xué)符號代替.其中綠?線段表?在分類閾值變動的過程中只新增了真正例，紅?線段表?只新增了假正例，藍?線段表?既新增了真正例也新增了假正例.根據(jù)值的定義可知，此時的值其實就是所有紅?線段和藍?線段與軸圍成的?積之和.觀察圖2-1可知，紅?線段與軸圍成的圖形恒為矩形，藍?線段與軸圍成的圖形恒為梯形.由于梯形?積式既能算梯形?積，也能算矩形?積，所以?論是紅?線段還是藍?線段，其與軸圍成的?積都能?梯形公式來計算：其中，為“?”，為“上底”， 為“下底”.那么對所有紅?線段和藍?線段與軸圍成的?積進?求和，則有此即 .式(2.21)解析按照我們上述對式(2.20)的解析思路，可以看作是所有綠?段和藍?線段與軸圍成的?積之和，但從式(2.21)中很難?眼看出其?積的具體計算?式，因此我們進?恒等變形如下：在變動分類閾值的過程當中，如果有新增真正例，那么圖2-1就會相應(yīng)地增加?條綠?線段或藍?線段，所以上式中的可以看作在累加所有綠?和藍?線段，相應(yīng)地，后?的內(nèi)容便是在求綠線段或者藍?線段與軸圍成的?積，即：與式(2.20)中的求解思路相同，不論是綠?線段還是藍?線段，其與軸圍成的圖形?積都可以?梯形公式來進?計算，所以上式表?依舊是?個梯形的?積公式.其中即梯形的“?”，中括號內(nèi)便是“上底+下底”，下?我們來分別推導(dǎo)?下“上底”（較短的底）和“下底”（較?的底）.由于在繪制 曲線的過程中，每新增?個假正例時坐標也就增?個步?，所以對于“上底”，也就是綠?或者藍?線段的下端點到軸的距離，?度就等于乘以預(yù)測值?于 的假正例的個數(shù)，即?對于“下底”，?度就等于 乘以預(yù)測值?于等的假正例的個數(shù)，即式(2.27)解析截?2018年12?“??書”第1版第30次印刷，式(2.27)應(yīng)當勘誤為具體推導(dǎo)過程如下：由“??書”中的上下?可知，對 進?假設(shè)檢驗，等價于本章附注中所述的對進?假設(shè)檢驗，所以在“??書”中求解最?錯誤率等價于在附注中求解事件最?發(fā)?頻率.附注可知所以將上式中的 等價替換為可得式(2.41)①②③④⑤⑥⑦① 再加?，屬于簡單的恒等變形④ ⑤：同①②?樣，減再加?個，屬于簡單的恒等變形⑤ ⑥：同②③?將最后?項利?期望的運算性質(zhì)進?展開解析② ③：?先將中括號內(nèi)的式?展開，有然后根據(jù)期望的運算性質(zhì)可將上式化為③ ④：再次利?期望的運算性質(zhì)將第3步得到的式?的最后?展開，有?先計算展開后得到的第1項，有由于是常量，所以由期望的運算性質(zhì)：（其中均為常量）可得由式(2.37)可知，所以接著計算展開后得到的第?項由于噪聲和?關(guān)，所以和 是兩個相互獨?的隨機變量.根據(jù)期望的運算性質(zhì)（其中 和為相互獨?的隨變量）可得所以⑥ 和均為常量，根據(jù)期望的運算性質(zhì)，有⑥中第2項同理有⑥中的最后?項由于此時假定噪聲的期望為零，即，所以附注附注?項分布參數(shù)的檢驗[1]設(shè)某事件發(fā)?的概率為.做次獨?試驗，每次觀察該件是否發(fā)?，以記該事件發(fā)?的次數(shù)，則服從?項分布，現(xiàn)根據(jù)檢驗如下假設(shè)：由?項分布本?的特性可知：越?， 取到較?值的概率越?.因此，對于上述假設(shè)，?個直觀上合理的檢驗為:當 時接受 ,否則就拒絕其中， 表?事件最?發(fā)?次數(shù).此檢驗對應(yīng)的功效函數(shù)為由于“越?， 取到較?值的概率越?”可以等價表?為：是關(guān)于的減函數(shù)，所以是關(guān)于的增函數(shù)，那么當 時，即的上確界.?根據(jù)參考?獻[1]中5.1.3的定義1.2可知，檢驗?平默認取最?可能的?平，所以在給定檢驗?平時，可以通過如下?程解得滿?檢驗?平的整數(shù)：更為嚴格的數(shù)學(xué)證明參?參考?獻[1]中第?章習(xí)題7顯然，當時有對于此?程，通常不?定正好解得?個使得?程成?的整數(shù) ，較常?的情況是存在這樣?個使得;此時，只能取 或者.若取 ，則相當于升?了檢驗?平；若取則相當于降低了檢驗?平.具體如何取舍需要結(jié)合實際情況，但是通常為了減?犯第?類錯誤的概率，會傾向于令取下?考慮如何求解.易證是關(guān)于 的減函數(shù)，再結(jié)合上述于的兩個不等式易推得參考參考?獻陳希孺.概率論與數(shù)理統(tǒng)計[M].合肥：中國科學(xué)技術(shù)?學(xué)出版社,2009.第第3章 線性模型式(3.5)解析已知，所以式(3.6)解析已知，所以式(3.7)解析令式(3.5)等于0，有由于令式(3.6)等于0可得 ，?因為 且，則，代?上式可得將 和代?上式，即可得式(3.7)：如果要想?Python來實現(xiàn)上式的話，上式中的求和運算只能?循環(huán)來實現(xiàn).但是如果能將上式向量化，也就是轉(zhuǎn)換成矩陣（即向量）運算的話，我們就可以利?諸如NumPy這種專門加速矩陣運算的類庫來進?編寫.下?我們就嘗試將上式進?向量化.將代?分?可得?因為 且，則有若令，為去均值后的；，為去值后的，代?上式可得、 、、 均為 ?1列的列向量式(3.10)解析將展開可得對 求導(dǎo)可得矩陣微分式 ,式(3.27）解析將式(3.26)代?式(3.25)可得其中 ， ，代?上式可得由于=0或1，則兩式綜合可得由于此式仍為極?似然估計的似然函數(shù)，所以最?化似然函數(shù)等價于最?化似然函數(shù)的相反數(shù)，即在似然函數(shù)前添加負號即可得式(3.27).值得?提的是，若將式(3.26)改寫為，再代?式(3.25)可得顯然，此種?式更易推導(dǎo)出式(3.27).式(3.30)解析此式可以進?向量化.令，代?上式得式(3.32)解析式(3.37)解析由式(3.36)，可定義拉格朗?函數(shù)為對 求偏導(dǎo)可得.這是由于、令上式等于0即可得由于我們想要求解的只有，?拉格朗?乘?具體取值多少都?所謂，因此可以任意設(shè)定來配合我們求解.注意到如果我們令，那么上式即可改寫為將其代?即可解得式(3.38)參?式(3.37)式(3.39)參?式(3.37)式(3.43)解析由式(3.40)、式(3.41)、式(3.42)可得：式(3.44)解析此式是式(3.35)的推?形式，證明如下.設(shè)，其中為?1列的列向量，則所以式(3.44)可變形為對?式(3.35)易知，上式即式(3.35)的推?形式.式(3.45)解析同式(3.35)，此處也固定式(3.44)的分?為1，那么式(3.44)此時等價于如下優(yōu)化問題根據(jù)拉格朗?乘?法，可定義上述優(yōu)化問題的拉格朗?函數(shù)根據(jù)矩陣微分式 對上式關(guān)于 求偏導(dǎo)可得.這是由于且令上式等于即可得第第4章 決策樹式(4.1)解析下?證明.已知集合 的信息熵的定義為其中，表?樣本類別總數(shù)， 表?第類樣本所占的?例，有.若令，那么信息熵就可以作?個元實值函數(shù)，即其中 .下?考慮求該多元函數(shù)的最值.?先我們先來求最?值，如果不考慮約束 ?僅考慮，則對 求最?值等價如下最?化問題：顯然，在 時，此問題為凸優(yōu)化問題.對于凸優(yōu)化問題來說，使其拉格朗?函數(shù)的?階偏導(dǎo)數(shù)等于0的點即最優(yōu)解.根據(jù)拉格朗?乘?法可知，該優(yōu)化問題的拉格朗?函數(shù)為其中，為拉格朗?乘?.對分別關(guān)于求?階偏導(dǎo)數(shù)，并令偏導(dǎo)數(shù)等于0可得;;...;.整理?下可得由以上兩個?程可以解得?因為 還需滿?約束，顯然 ，所以是滿?所有約束的最優(yōu)解，即當前最?化問題的最?值點，同時也是的最?值點.將代?中可得所以在滿?約束 時的最?值為.下?求最?值.如果不考慮約束?僅考慮 ，可以看作個互不相關(guān)的?元函數(shù)的和，即其中，.那么當分別取到其最?值時，也就取到了最?值.所以接下來考慮別求各?的最?值，由于的義域和函數(shù)表達式均相同，所以只需求出的最?值也就求出了的最?值.下?考慮求的最?值，?先對關(guān)求?階和?階導(dǎo)數(shù)，有顯然，當 時 恒?于0，所以是?個在其定義域范圍內(nèi)開?向下的凹函數(shù)，那么其最?值必然在邊界取.別取和，代?可得計算信息熵時約定：若 ，則所以，的最?值為0，同理可得的最?值也都為0，即的最?值為0.但是，此時僅考慮約束 ，?未考慮.若考慮約束，那么 的最?值定?于等于0.如果令某個 ，那么根據(jù)約束可知，將其代?可得所以?定是在滿?約束和 的條件下的最?值點，時取到最?值0.綜上可知，當 取到最?值時：此時樣本集合純度最低；當取到最?值時：，此時樣本集合純度最?.式(4.2)解析此為信息增益的定義式.在信息論中信息增益也稱為互信息（本章附注①），表?已知?個隨機變量的信息后另?個隨機變量的不確定性減少的程度.所以此式可以理解為的取值后，樣本類別這個隨機變量的不確定性減?的程度.若根據(jù)某個的信息增益越?，則說明在知道其取值后樣本集的不確定性減?的程度越?，即“??書”上所說的“純度提升”越?.式(4.6）解析此為數(shù)據(jù)集中屬性的基尼指數(shù)的定義，表?在屬性的取值已知的條件下，數(shù)據(jù)集按照屬性的所有可能取值劃分后的純度.不過在構(gòu)造CART決策樹時并不會嚴格按照此式來選擇最優(yōu)劃分屬性，主要是因為CART決策樹是?棵?叉樹，如果?上?的式去選出最優(yōu)劃分屬性，?法進?步選出最優(yōu)劃分屬性的最優(yōu)劃分點.常?的CART決策樹的構(gòu)造算法如下：考慮每個屬性的每個可能取值，將數(shù)據(jù)集分為 和兩部分來計算基尼指數(shù)，即選擇基尼指數(shù)最?的屬性及其對應(yīng)取值作為最優(yōu)劃分屬性和最優(yōu)劃分點；重復(fù)以上兩步，直?滿?停?條件.下?以“??書”中表4.2中??數(shù)據(jù)集2.0為例來構(gòu)造決策樹，其中第?個最優(yōu)劃分屬性和最優(yōu)劃分點的計算過程如下：以屬性“?澤”為例，它有3個可能的取值：{?綠}，{烏?}，{淺?}?該屬性的屬性值是否等于“?綠”對數(shù)據(jù)集進?劃分，則可得到2個?集，分別記為?綠),(?澤?綠).?集包含編號共6個樣例，其中正例占，反例占；?包含編號共11個樣例，其中正例占，反例占，根據(jù)式(4.5)可計算出?“?澤=?綠”劃分之得到基尼指數(shù)為( ,?澤=?綠)類似地，可以計算出不同屬性取不同值的基尼指數(shù)如下：Gini_index(,?澤=烏?)=0.456Gini_index(,?澤=淺?)=0.426Gini_index(,根蒂=蜷縮)Gini_index( ,根蒂=稍蜷)=0.496Gini_index( ,根蒂=硬挺)=0.439Gini_index( ,敲聲=濁響)=0.450Gini_index( ,敲聲=沉悶)=0.494Gini_index( ,敲聲=清脆)=0.439Gini_index( ,紋理=清晰)=0.286Gini_index( ,紋理=稍稀)=0.437Gini_index( ,紋理=模糊)=0.403Gini_index( ,臍部=凹陷)=0.415Gini_index( ,臍部=稍凹)=0.497Gini_index( ,臍部=平坦)=0.362Gini_index( ,觸感=硬挺)=0.494Gini_index( ,觸感=軟粘)=特別地，對于屬性“觸感”，由于它的可取值個數(shù)為2，所以其實只需計算其中?個取值的基尼指數(shù)即可.根據(jù)上?的計算結(jié)果可知，Gini_index( ,紋理=清晰)=0.286最?，所以選擇屬性“紋理”為最優(yōu)劃分屬性并?成根節(jié)點，接著以“紋理=清晰”為最優(yōu)劃分點?成(紋理清晰)(紋理清晰)兩個?節(jié)點，對兩個?節(jié)點分別重復(fù)上述步驟繼續(xù)?成下?層?節(jié)點，直?滿?停?條件.以上便是決策樹的構(gòu)建過程，從構(gòu)建過程可決策樹最終構(gòu)造出來的是?棵?叉樹除了決策樹能處理分類問題以外，回歸樹還可以處理回歸問題，附注②中給出了回歸樹構(gòu)造算法.式(4.7)解析此式所表達的思想很簡單，就是以每兩個相鄰取值的中點作為劃分點.下?以“??書”中表4.3中??數(shù)據(jù)集3.0為例來說明此式的?法.對于“密度”這個連續(xù)屬性，已觀測到的可能取值為{0.243,0.245,0.343,0.360,0.403,0.437,0.481,0.556,0.593,0.608,0.634,0.639,0.657,0.666,0.697,0.719,0.774}共個值，根據(jù)式(4.7)可知，此時依次取1到16，那么“密度”這個屬性的候選劃分點集合為式(4.8)解析此式是式(4.2)?于離散化后的連續(xù)屬性的版本，其中由式(4.7)計算得來，表?屬性的取值分別?于等于和?于候選劃點時的情形，即當時有，當時有.附注附注①互信息[1]在解釋互信息之前，需要先解釋?下什么是條件熵.條件熵表?是在已知?個隨機變量的條件下，另?個隨機變量的不確定性.具體地，假設(shè)有隨機變量 和，且它們服從以下聯(lián)合概率分布那么在已知 的條件下，隨機變量 的條件熵為其中，.互信息定義為信息熵和條件熵的差，它表?的是已知?個隨機變量的信息后使得另?個隨機變量不確定性減少的程度.具體地，假設(shè)有隨機變量 和，那么在已知的信息后，的不確定性減少的程度為此即互信息的數(shù)學(xué)定義.②CART回歸樹[1]假設(shè)給定數(shù)據(jù)集其中為維特征向量，是連續(xù)型隨機變量.這是?個標準的回歸問題的數(shù)據(jù)集,若把每個屬性視為坐標空間中的?個坐標軸，則個屬性就構(gòu)成了?個維的特征空間，?每個維特征向量就對應(yīng)了維的特征空間中的?個數(shù)據(jù)點.CART回歸樹的?標是將特征空間劃分成若?個?空間，每個?空間都有?個固定的輸出值，也就是凡是落在同?個?空間內(nèi)的數(shù)據(jù)點，它們所對應(yīng)的輸出值恒相等，且都為該?空間的輸出值.那么如何劃分出若?個?空間呢？這?采??種啟發(fā)式的?法.任意選擇?個下性最優(yōu)劃分點：其中，，和分別為集合和中的樣本 對應(yīng)的輸出值的均值，即點將特征空間劃分為兩個?空間，接著對每個?空間重復(fù)上述步驟，直?滿?停?條件.這樣就?成了?棵回歸樹，假設(shè)最終將特征空間劃分為 個?空間，那么回歸樹的模型式可以表?為同理，其中的表?的也是集合中的樣本對應(yīng)的輸出值的均值.此式直觀上的理解就是，對于?個給定的樣本，?先判斷其屬于哪個?空間，然后將其所屬的?空間對應(yīng)的輸出值作為該樣本的預(yù)測值.參考參考?獻[1] 李航.統(tǒng)計學(xué)習(xí)?法[M].北京：清華?學(xué)出版社,2012.第第5章 神經(jīng)?絡(luò)式(5.2)解析此式是感知機學(xué)習(xí)算法中的參數(shù)更新式，下?依次給出感知機模型、學(xué)習(xí)策略和學(xué)習(xí)算法的具體介紹[1].感知機模型已知感知機由兩層神經(jīng)元組成，故感知機模型的式可表?為其中， ，為樣本的特征向量，是感知機模型的輸?；是感知機模型的參數(shù)， ，為權(quán)重，為閾值.假定為階躍函數(shù)，么感知機模型的式可進?步表?為?代表階躍函數(shù)由于維空間中的超平??程為所以此時感知機模型式中的可以看作是維空間中的?個超平?，將維空間劃分為和兩個?空間，落在前?個?空間的樣本對應(yīng)的模型輸出值為1，落在后?個?空間的本對應(yīng)的模型輸出值為0，如此便實現(xiàn)了分類功能.感知機學(xué)習(xí)策略給定?個線性可分的數(shù)據(jù)集（參?本章附注），感知機的學(xué)習(xí)?標是求得能對數(shù)據(jù)集中的正負樣本完全正確劃分的分離超平?假設(shè)此時誤分類樣本集合為，對任意?個誤分類樣本來說，當時，模型輸出值為，樣本真實標為；反之，當時，模型輸出值為，樣本真實標為.綜合兩種情形可知，以下式恒成?：所以，給定數(shù)據(jù)集，其損失函數(shù)可以定義為顯然，此損失函數(shù)是?負的.如果沒有誤分類點，則損失函數(shù)值為?且，誤分類點越少，誤分類點離超平?越近，損失函數(shù)值就越?.因此，給定數(shù)據(jù)集，損失函數(shù)是關(guān)于的連續(xù)可導(dǎo)函數(shù).感知機學(xué)習(xí)算法感知機模型的學(xué)習(xí)問題可以轉(zhuǎn)化為求解損失函數(shù)的最優(yōu)化問具體地，給定數(shù)據(jù)集其中，求參數(shù)，使其為極?化損失函數(shù)的解：其中 為誤分類樣本集合.若將閾值看作?個固定輸?為的“啞節(jié)點”，即那么可化簡為其中.根據(jù)該式，可將要求解的極?化問題進?步簡化為假設(shè)誤分類樣本集合 固定，那么可以求得損失函數(shù)的梯度感知機的學(xué)習(xí)算法具體采?的是隨機梯度下降法，即在極?化過程中，不是?次使 中所有誤分類點的梯度下降，?是?次隨機選取?個誤分類點并使其梯度下降.所以權(quán)重 的更新式為相應(yīng)地，中的某個分量 的更新式即式(5.2).式(5.10)參?式(5.12)式(5.12)解析因為?所以式(5.13）因?所以式(5.14)因?所以式(5.15)參?式(5.13)式(5.20)解析Boltzmann機（RestrictedBoltzmannMachine，簡稱RBM）本質(zhì)上是?個引?了隱變量的?向圖模型，其能量可理解為其中，表?圖的能量，表?圖中邊的能量，表?圖中結(jié)點的能量.邊能量由兩連接結(jié)點的值及其權(quán)重的乘積確定，即；結(jié)點能量由結(jié)點的值及其閾值的乘積確定，即.圖中邊的能量為所有邊能量之和為圖中結(jié)點的能量為所有結(jié)點能量之和故狀態(tài)向量所對應(yīng)的Boltzmann機能量式(5.22)解析受限Boltzmann機僅保留顯層與隱層之間的連接.顯層狀態(tài)向量，隱層狀態(tài)向量.顯層狀態(tài)向量的變量僅與隱層狀態(tài)向量有關(guān)，所以給定隱層狀態(tài)向量，有相互獨?.式(5.23）解析由式(5.22)的解析同理可得，給定顯層狀態(tài)向量，有相互獨?.式(5.24）解析由式(5.20)可推導(dǎo)出受限Boltzmann機的能量函數(shù)其中再由式(5.21)可知，RBM的聯(lián)合概率分布其中為規(guī)范化因?給定含 個獨?同分布數(shù)據(jù)的數(shù)據(jù)集，記.學(xué)習(xí)RBM的策略是求出參數(shù)的值，使得如下對數(shù)似然函數(shù)最?化：具體地，采?梯度上升法來求解參數(shù)，因此考慮求對數(shù)似然函數(shù)的梯度.對于 中的任意?個樣本 ，其對應(yīng)似然函數(shù),對求導(dǎo)有.由于,,故.包含三個參數(shù)，在這?我們僅以 中的任意?個分量 為例進?詳細推導(dǎo).?先將上式中的替換為 可得根據(jù)式(5.23)可知同理可推得將以上兩式代回 中可得觀察此式可知，通過枚舉所有可能的來計算的復(fù)雜度太?，因此可以考慮求其近似值來簡化計算.具體地，RBM通常采?的是“??書”上所說的“對?散度”（ContrastiveDivergence，簡稱CD）算法.CD算法的核?思想是：?步?為（通常設(shè)為1）的CD函數(shù)讀者可參閱“?果提”發(fā)布于CSDN的?章《受限玻爾茲曼機（RBM）學(xué)習(xí)筆記（六）對?散度算法》近似代替對于 來說，即?近似代替令 ，表?參數(shù)為的RBM?絡(luò)，則的具體算法如圖5-1所?.輸?：步?；數(shù)據(jù)集；參數(shù)為的RBM?絡(luò)RBM.過程：1：初始化2：for do3： 4： for do5： 6： 7： end for8： for do9： 10： end for11：end for輸出：圖5-1 CD算法圖5-1中函表?在給定的條件下，從中采樣?成，同理，函數(shù)表?在給定條件下，從中采樣?成.由于兩個函數(shù)的算法可以互相類?推得，因此僅給出函數(shù)的具體算法，如圖5-2所?.綜上可知，式(5.24)其實就是帶有學(xué)習(xí)率的的?種形式化表?.輸?：顯層狀態(tài)向量；參數(shù)為的 RBM.過程：1:for do2: 隨機?成3:4:endfor輸出：輸出：圖5-2 算法附注附注數(shù)據(jù)集的線性可分[1]給定?個數(shù)據(jù)集其中.如果存在某個超平?能將數(shù)據(jù)集中的正樣本和負樣本完全正確地劃分到超平?兩側(cè)，即對所有的樣本 有，對所有的樣本 有，則稱數(shù)據(jù)集線性可分，否則稱數(shù)據(jù)集線性不可分.參考參考?獻李航.統(tǒng)計學(xué)習(xí)?法[M].北京：清華?學(xué)出版社,2012.第第6章 ?持向量機式(6.9)解析式(6.8)可作如下展開：對 和分別求偏導(dǎo)數(shù)并分別令其等于0和0，有值得?提的是，上述求解過程遵循的是“??書”附錄B中式(B.7)左側(cè)的那段話：“在推導(dǎo)對偶問題時，常通過將拉格朗?函數(shù)對求導(dǎo)并令導(dǎo)數(shù)為0，來獲得對偶函數(shù)的表達形式.”那么這段話背后的緣由是什么呢？在這?我們認為有兩種說法可以進?解釋：對于強對偶性成?的優(yōu)化問題，其主問題的最優(yōu)解?定滿本章附注給出的KKT條件，?KKT條件中的條件(1)就要求最優(yōu)解能使得拉格朗?函數(shù)關(guān)于的?階導(dǎo)數(shù)等于0；證明參?參考?獻[1]的5.5節(jié)對于任意優(yōu)化問題，若拉格朗?函數(shù)是關(guān)于的凸函數(shù)，那么此時對關(guān)于求導(dǎo)并令導(dǎo)數(shù)等于0解出來的點?定是最?值點.根據(jù)對偶函數(shù)的定義，將最?值點代回即可得到偶函數(shù).顯然，對于SVM來說，從以上任意?種說法都能解釋得通.式(6.10)參?式(6.9)式(6.11）s.t. ,解析將式(6.9)和式(6.10)代?式(6.8)即可將中的和消去，考慮式(6.10)的約束，就得到了式(6.6)的對偶問題：由于 ，所以上式最后?項可化為0，于是得,所以式(6.13)參?式(6.9)中給出的第1點理由式(6.35）s.t.,解析令顯然 .且當時有當時有綜上可得式(6.37）參?式(6.9)式(6.38）參?式(6.10)式(6.39)解析式(6.36)關(guān)于求偏導(dǎo)并令其等于0可得式(6.40）s.t. ,解析將式(6.37)(6.39)代?式(6.36)可以得到式(6.35)的對偶問題，有,所以.?因為，，，消去 可得等價約束條件式(6.41)參?式(6.13)式(6.52）解析將式(6.45)的約束條件全部恒等變形為?于等于0的形式可得由于以上四個約束條件的拉格朗?乘?分別為，由本章附注可知，以上四個約束條件可相應(yīng)轉(zhuǎn)化為KKT條件?由式(6.49)和式(6.50)有所以上述KKT條件可以進?步變形為?因為樣本只可能處在間隔帶的某?側(cè)，即約束條件和不可能同時成?，所和中?少有?個為0，即.在此基礎(chǔ)上再進?步分析可知，如果，則根據(jù)約可知此時.同理，如果，則根據(jù)約束可知此時.所以和中也是?少有?個為0，即.將整合進上述KKT條件中即可得到式(6.52).式(6.60)類似于第3章的式(3.35)式(6.62）類似于第3章的式(3.34)式(6.63)類似于第3章的式(3.33)式(6.65）解析由表?定理可知，此時?分類KLDA最終求得的投影直線?程總可以寫成如下形式：?因為直線?程的固定形式為所以將代?可得.由于的計算結(jié)果為標量，?標量的轉(zhuǎn)置等于其本?，所以即式(6.66)解析為了詳細地說明此式的計算原理，下??先舉例說明，然后再在例?的基礎(chǔ)上延展出其?般形式.假設(shè)此時僅有4個樣本，其中第1和第3個樣本的標記為0，第2和第4個樣本的標記為1，那么此時有;;所以,根據(jù)此結(jié)果易得的?般形式為式(6.67)參?式(6.66)的解析式(6.70）解析此式是將式(6.65)代?式(6.60)后推得?來的，下?給出詳細地推導(dǎo)過程.?先將式(6.65)代?式(6.60)的分?可得,其中.將其代?上式可得.由于為標量，所以其轉(zhuǎn)置等于本?，即.將其代?上式可得.設(shè)，同時結(jié)合式(6.66)的解析可得的?般形式，上式可以化簡為以上便是式(6.70)分?部分的推導(dǎo)，下?繼續(xù)推導(dǎo)式(6.70)的分?部分.將式(6.65)代?式(6.60)的分?可得：其中由于且所以再將此式代回可得其中，第1項第2項同理，有第3項將上述三項的化簡結(jié)果代回再將此式代回可得附注附注KKT條件[2]考慮?般的約束優(yōu)化問題其中，?變量 .設(shè)具有連續(xù)的?階偏導(dǎo)數(shù)，是優(yōu)化問題的局部可?解.若該優(yōu)化問題滿?任意?個約束限制條件（constraintqualificationsorregularityconditions），則?定存在，使得：參?維基百科??“Karush-kuhn-tuckerconditions”(1)(2)(5);其中為拉格朗?函數(shù)以上5條即KKT條件，嚴格數(shù)學(xué)證明參?參考?獻[2]的4.2.1?節(jié).參考參考?獻王書寧.凸優(yōu)化[M].北京：清華?學(xué)出版社,2013.王燕軍.最優(yōu)化基礎(chǔ)理論與?法[M].上海：復(fù)旦?學(xué)出版社2011.第第7章 ?葉斯分類器式(7.5)解析由式(7.1)和式(7.4)可得? ，則此即式(7.5).式(7.6）將式(7.5)代?式(7.3)即可推得此式式(7.12）參?式(7.13)式(7.13）解析根據(jù)式(7.11)和式(7.10)可知參數(shù)求解式為由“??書”上下?可知，此時假設(shè)概率密度函數(shù)，其等價于假設(shè)其中，表?的維數(shù)，為對稱正定協(xié)?差矩陣，表?的?列式.將其代?參數(shù)求解式可得.假設(shè)此時數(shù)據(jù)集中的樣本個數(shù)為，即，則上式可以改寫為.為了便于分別求解和，在這?我們根據(jù)式和 將上式中的最后?項作如下恒等變形：.所以.觀察上式可知，由于此時和 ?樣均為正定矩陣，所以當時，上式最后?項為正定?次型.根據(jù)正定?次型的性質(zhì)知，此時上式最后?項的取值僅與相關(guān)，并有當且僅當時，上式最后?項取最?值0，此時可以解得將求解出來的代回參數(shù)求解式可得新的參數(shù)求解式，有,此時的參數(shù)求解式是僅與 相關(guān)的函數(shù).為了求解，在這?我們不加證明地給出?個引理：設(shè) 為階定矩陣， 為實數(shù)，則對所有階正定矩陣 有具體證明可搜索張偉平“多元正態(tài)分布參數(shù)的估計和數(shù)據(jù)的清潔與變換”課件當且僅當 時等號成?.根據(jù)此引理可知，當且僅當時，上述參數(shù)求解式中后?的式?到最?值，那么此時的 即我們想要求解的.式(7.19)解析從?葉斯估計（參?本章附注①）的?度來說，拉普拉斯修正等價于先驗概率為Dirichlet分布（參?本章附注③）的后驗期望值估計.為了接下來的敘述?便，我們重新定義?下相關(guān)數(shù)學(xué)符號.設(shè)有包含 個獨?同分布樣本的訓(xùn)練集，中可能的類別數(shù)為，其類別的具體取值范圍為.若令隨機變量 表?樣本屬的類別，且 取到每個值的概率分別為，那么顯然服從參數(shù)為分布（參?附注②），其概率量函數(shù)為其中就是式(7.9)所要求解的，下?我們??葉斯估計中的后驗期望值估計來估計.根據(jù)?葉斯估計的原理可知，在進?參數(shù)估計之前，需要先主觀預(yù)設(shè)?個先驗概率，通常為了?便計算后驗概率，我們會?似然函數(shù)的共軛先驗作為我們的先驗概率.顯然，此時的似然函數(shù)是?個基于Categorical分布的似然函數(shù)，?Categorical分布的共軛先驗為Dirichlet分布，所以只需要預(yù)設(shè)先驗概率為Dirichlet分布，然后使?后驗期望值估計就能估計.讀者可搜索“共軛先驗”（conjugateprior）和“共軛先驗分布”（conjugatepriordistribution）以了解更多具體地，記中樣本類別取值為的樣本個數(shù)為，則似然函數(shù)可展開為則有后驗概率假設(shè)此時先驗概率是參數(shù)為的Dirichlet分布，則可寫為將其代?可得此時若設(shè)，則根據(jù)Dirichlet分布的定義可知將此結(jié)論代?可得綜上可知，對于服從Categorical分布的來說，假設(shè)其先驗概率是參數(shù)為的Dirichlet分布時，得到的后驗概率是參數(shù)為的Dirichlet分布，通常我們稱這種先驗概率分布和后形式相同的這對分布為共軛分布.在推得后驗概率的具體形式后，根據(jù)后驗期望值估計可得的估計值為顯然，式(7.9)是當時推得的具體結(jié)果，此時等價于我們主觀預(yù)設(shè)的先驗概率服從均勻分布，此即拉普拉斯修正.理，當我們調(diào)整的取值后，即可推得其他數(shù)據(jù)平滑的公式.式(7.20)參?式(7.19)式(7.24）參?式(7.19)式(7.25）參?式(7.20)式(7.27)解析在這?補充?下同?結(jié)構(gòu)和順序結(jié)構(gòu)的推導(dǎo).同?結(jié)構(gòu)：在給定?節(jié)點 的條件下 獨?，有順序結(jié)構(gòu)：在給定節(jié)點的條件下 獨?，有式(7.34)EM算法這?節(jié)建議以李航《統(tǒng)計學(xué)習(xí)?法》為主，“??書”為輔進?學(xué)習(xí)附注附注①?葉斯估計[1]?葉斯學(xué)派視?下的?類點估計法稱為?葉斯估計，常?的?葉斯估計有最?后驗估計（MaximumAPosterioriEstimation，簡稱MAP）、后驗中位數(shù)估計和后驗期望值估計這3種參數(shù)估計?法，下?給出這3種?法的具體定義.設(shè)總體的概率質(zhì)量函數(shù)（若總體的分布為連續(xù)型時則改為概率密度函數(shù)，此處以離散型為例）為，從該總體中抽取出的個獨同分布的樣本構(gòu)成樣本集，則根據(jù)?葉斯式可得在給定樣本集的條件下為其中為似然函數(shù)，由于樣本集中的樣本是獨?同分布的，所以似然函數(shù)可以進?步展開，有根據(jù)?葉斯學(xué)派的觀點，此條件概率代表了我們在已知樣本集后對產(chǎn)?的新的認識，它綜合了我們對主觀預(yù)設(shè)的先驗概率樣本集帶來的信息，通常稱其為的后驗概率.?葉斯學(xué)派認為，在得到以后，對參數(shù)的任何統(tǒng)計推斷，都只能基于.?于具體如何去使?它，可以結(jié)合某種準則?起去進?，統(tǒng)計學(xué)家也有?定的?由度.對于點估計來說，求使得到最?值的作為的估計稱為最?后驗估計，求的中位數(shù)作為的估計稱為后驗中位數(shù)估計，求的期望值（均值作為的估計稱為后驗期望值估計.②Categorical分布Categorical分布?稱為?義伯努利分布，是將伯努利分布中的隨機變量可取值個數(shù)由兩個泛化為多個得到的分布.具體地，設(shè)離散型隨機變量 共有種可能的取值，且 取到每個值的概率分別為，則稱隨機變服從參數(shù)為的Categorical分布，其概率質(zhì)量函數(shù)為其中是指?函數(shù)，若為真則取值1，否則取值0.③Dirichlet分布類似于Categorical分布是伯努利分布的泛化形式，Dirichlet分布是Beta分布的泛化形式.對于?個維隨機變，中 滿?，若服從參數(shù)為的Dirichlet分布，則其概率密度函數(shù)為其中 為Gamma函數(shù)，當時，Dirichlet分布等價于均勻分布.參考參考?獻[1] 陳希孺.概率論與數(shù)理統(tǒng)計[M].合肥：中國科學(xué)技術(shù)?學(xué)出版社,2009.第第8章 集成學(xué)習(xí)式(8.1)解析是編號為的基分類器預(yù)測的標記，是的真實標記，它們間不?致的概率記為.式(8.2)“??書”中將符號函數(shù)寫為sign解析當把分類為1時，有，否則.各個基分類的分類結(jié)果求和之后數(shù)字的正、負或0，代表投票法產(chǎn)?的結(jié)果，即“少數(shù)服從多數(shù)”.符號函將正數(shù)變成1，負數(shù)變成 ，0仍然是0，所以是由投票法產(chǎn)?的分類結(jié)果.式(8.3)解析即 服從?項分布由于基分類器相互獨?，假設(shè)隨機變量 為個基分類器分類正的次數(shù)，因此，設(shè)為每?個分類器分類正確的次數(shù)，則，有證明過程如下：.根據(jù)Hoeffding不等式知令 得式(8.4)解析此式是集成學(xué)習(xí)的加性模型.加性模型不采?梯度下降的思想，?是每次更新求解?個理論上最優(yōu)的 和 參?式(8.18)和式(8.11)式(8.5)解析由式(8.4)知?由式(8.11)可知由 函數(shù)的單調(diào)性可知，該分類器的權(quán)重只與分類器的錯誤率負相關(guān)(即錯誤率越?，權(quán)重越低)，指數(shù)損失函數(shù)的意義如下.先考慮指數(shù)損失函數(shù)的含義.為真實函數(shù)，對于樣本說，只能取 和 ，?是?個實數(shù).當?shù)姆柵c?致時，，因此有，且越?指數(shù)損失函數(shù)越?.這很合理，因為此時越?意味著分類器本?對預(yù)測結(jié)果的信?越?損失應(yīng)該越?；若在零附近，雖然預(yù)測正確，但表?分類器本對預(yù)測結(jié)果信?很?，損失應(yīng)該較?.當?shù)姆柵c不?致時，，因此，且越?指數(shù)損失函數(shù)越?.此時越?意味著分類器本?對預(yù)測結(jié)果的信?越?，但預(yù)測結(jié)果是損失應(yīng)該越?；若在零附近，雖然預(yù)測錯誤，但表?分類器本?對預(yù)測結(jié)果信?很?，雖然錯了，損失應(yīng)該較?.接下來考慮符號的含義. 為概率分布，可簡單理解為在數(shù)據(jù)集中進?隨機抽樣時每個樣本被取到的概率；為經(jīng)典的期望.此表?在概率分布上的期望，可理解為對數(shù)據(jù)集以概率分布進?加權(quán)后的期望.即式(8.6)解析由式(8.5)中對于符號的解釋可知因此式(8.7）解析令式(8.6)等于0，移項并分離，即可得到式(8.7).式(8.8）①③函數(shù)即“??書”中的sign函數(shù)解析① ②顯然成?；② ③利?了 函數(shù)的定義:表?使得函數(shù))取得最?值的的值，展開則為②.式(8.9)與式(8.1)?致，表?分類錯誤的概率式(8.10）指數(shù)損失函數(shù)對 求偏導(dǎo)，以得到使得損失函數(shù)取最?值時 的值式(8.11)解析令式(8.10)等于0移項即得到的該式.此時 的取值使得該基分類經(jīng) 加權(quán)后的損失函數(shù)最?.式(8.12)解析將代?式(8.5)即可，因為理想的可以糾的全部錯誤，所以這?指定其權(quán)重系數(shù)為1.如果權(quán)重系數(shù) 是常數(shù)的話，對后續(xù)結(jié)果也沒有影響.式(8.13)解析由 的?階泰勒展開得因為與取值都為1或 ，所以，故有式(8.14)①②③④解析理想的是使得的指數(shù)損失函數(shù)取得最?值時的，該式將此轉(zhuǎn)化成某個期望的最?值.②③是因是個常數(shù)，與?關(guān).③④是因也與?關(guān)，所以可以引?.式(8.16)解析?先解釋下符號的含義.注意在本章中有兩個符號 和，其中 表?數(shù)據(jù)集，? 表?數(shù)據(jù)集的樣本分布，即在數(shù)據(jù)集上進?次隨機采樣時，樣本被抽到的概率是.表?在概率分布上的期望，可以簡單地理解為，對數(shù)據(jù)及 以概率加權(quán)之后的期望，因此有故可得由式(8.15)可知所以有式(8.17)當時，，；當時，，式(8.18）解析由式(8.16)和式(8.17)有式(8.19）Boosting算法根據(jù)調(diào)整后的樣本訓(xùn)練下?個基分類器.此為“重賦權(quán)法”的樣本分布的調(diào)整式式(8.20)解析表?對個基學(xué)習(xí)器分別判斷結(jié)果是否與?致，的取值?般是和.如果基學(xué)習(xí)器結(jié)果與?致，則；如果樣本不在訓(xùn)練集內(nèi)，則.綜合起來看，就是對包外的數(shù)據(jù)，?“投票法”選擇包外估計的結(jié)果，即1或.式(8.21）由式(8.20)知，是對包外的估計.該式表?估計錯誤的個數(shù)除以總的個數(shù)，得到泛化誤差的包外估計式(8.22）此為對基分類器的結(jié)果進?簡單的平均式(8.23）此為對基分類器的結(jié)果進?加權(quán)平均式(8.24）即當某?個類別的基分類器的結(jié)果之和?于所有結(jié)果之和的時，選擇該類別為最終結(jié)果式(8.25）若類別的基分類器的結(jié)果之和在所有類別中最?，則選擇類別為最終結(jié)果式(8.26)此式與式(8.25)的不同在于，在基分類器前?乘上?個權(quán)重系數(shù)，滿? 且式(8.27）此為個體學(xué)習(xí)器結(jié)果與預(yù)測結(jié)果的差值的平?，即個體學(xué)習(xí)器的“分歧”式(8.28）此為對各個個體學(xué)習(xí)器的“分歧”加權(quán)平均的結(jié)果，即集成的“分歧”式(8.29）此為個體學(xué)習(xí)器與真實值之間差值的平?，即個體學(xué)習(xí)器的平?誤差式(8.30)此為集成與真實值之間差值的平?，即集成的平?誤差式(8.31)解析由式(8.28)知?因為所以式(8.32)解析表?個體學(xué)習(xí)器在全樣本上的“分歧”，表?集成在全樣本上的“分歧”.根據(jù)式(8.31)將拆成誤差的形式即有本式.式(8.33)此為個體學(xué)習(xí)器在全樣本上的泛化誤差式(8.34）此為個體學(xué)習(xí)器在全樣本上的分歧式(8.35）此為集成在全樣本上的泛化誤差式(8.36）表?個體學(xué)習(xí)器泛化誤差的加權(quán)均值，表?個體學(xué)習(xí)器分歧項的加權(quán)均值，該式稱為“誤差-分歧分解”第第9章 聚類式(9.5)解析給定兩個集合和，則Jaccard系數(shù)定義為Jaccard系數(shù)可以?來描述兩個集合的相似程度.推論：假設(shè)全集共有個元素，且 ， ，則每?個元素的位置共有4種情況元素同時在集合和中，這樣的元素個數(shù)記為;元素出現(xiàn)在集合中，但沒有出現(xiàn)在集合 中，這樣的元素個記為;元素沒有出現(xiàn)在集合中，但出現(xiàn)在集合 中，這樣的元素個記為;元素既沒有出現(xiàn)在集合中，也沒有出現(xiàn)在集合 中，這樣的素個數(shù)記為 .根據(jù)Jaccard系數(shù)的定義，此時的Jaccard系數(shù)聚類屬于?監(jiān)督學(xué)習(xí).我們并不知道聚類后樣本所屬類別的類別標記所代表的意義，即便參考模型的類別標記意義是已知的，也?法知道聚類后的類別標記與參考模型的類別標記的對應(yīng)關(guān)系.此外，聚類的類別總數(shù)與參考模型的類別總數(shù)還可能不同.因此?法只?單個樣本衡量聚類性能的好壞.外部指標的基本思想就是以參考模型的類別劃分為參照.如果某?個樣本對中的兩個樣本在聚類結(jié)果中同屬于?個類，在參考模型中也同屬于?個類，或者這兩個樣本在聚類結(jié)果中不同屬于?個類，在參考模型中也不同屬于?個類，那么對于這兩個樣本，這是?個好的聚類結(jié)果.?般地，樣本對中的兩個樣本共存在4種情況：在聚類結(jié)果中屬于同?個類，在參考模型中也屬于同?個類;在聚類結(jié)果中屬于同?個類，但在參考模型中不屬于同?個類;在聚類結(jié)果中不屬于同?個類，但在參考模型中屬于同?個類;在聚類結(jié)果中不屬于同?個類，在參考模型中也不屬于同?個類.以上4種情況對應(yīng)“??書”中的式(9.1)(9.4).假設(shè)集合中存放著兩個樣本都同屬于聚類結(jié)果的同?個類的樣本對，即，集合 中存放著兩個樣本都同屬于參考模型的同?個類的樣本對，即，那么根據(jù)Jaccard系數(shù)的定義有也可直接將“??書”中的式(9.1)(9.4)的四種情況類?推論，即，，，所以式(9.6)解析式中和為提出的兩個?對稱指標，其中代表兩樣本在聚類結(jié)果和參考模型中均屬于同?類的樣本對的數(shù)量，代表兩個樣本在聚類結(jié)果中屬于同?類的樣本對的數(shù)量， 代表兩個樣本在參考模型中屬于同?類的樣本對的數(shù)量.這兩個?對稱指標均可理解為樣本對中的兩個樣本在聚類結(jié)果和參考模型中均屬于同?類的概率.由于指標的?對稱性，這兩個往往不相等，因此Fowlkes和Mallows提出利??何平均數(shù)將這兩個?對稱指標轉(zhuǎn)化為?個對稱指標，即FM指數(shù).式(9.7)解析Rand指數(shù)定義如下：其中表?聚類結(jié)果為同?類別且參考模型給出的劃分也屬于統(tǒng)?類別的樣本對的個數(shù)。表?聚類結(jié)果不屬于同?類別且參考模型也劃分到同?類別的樣本對的個數(shù)。分?是所有樣本的總對數(shù)，因此 可以簡單理解為聚類結(jié)果與參考模型的?致性。式(9.8）解析此為簇內(nèi)距離的定義.為 組合數(shù)量的倒數(shù)為這些組合的距離和.?者相乘即平均距離.式(9.33）解析根據(jù)式(9.28)有?根據(jù)式(9.32)，由，有為了避免混淆，重寫式(9.32)如下這?2個求和號的求和變量由式(9.32)的變量改為，是為了免和中的變量混淆,其中，對于，有對于 ，有由矩陣求導(dǎo)的法則 可得因此有式(9.34)解析由式(9.30)，有代?式(9.33)，有因此式(9.35）解析根據(jù)式(9.28)可知?根據(jù)式(9.32)，需令.考慮等號左側(cè)，有其中矩陣微分式：將此式代回 中可得?由式(9.30)可知 ，所以上式可進?步化簡為令上式等于0可得移項推導(dǎo)有此即式(9.35).式(9.38)解析式(9.37)兩邊同時乘以 可得兩邊對所有混合成分求和可得由 有因此?由式(9.30)可知 ，所以上式可進?步化簡為此即式(9.38).第第10章 降維與度量學(xué)習(xí)式(10.1)解析表?和同屬類的概率，對所有可能的類別和，則得到和同屬相同類別的概率，因此表?不同類別的概率.式(10.2)①②③④⑤解析① ②來源于前提假設(shè)“假設(shè)樣本獨?同分布，且對?正數(shù)距離范圍內(nèi)總能找到?個訓(xùn)練樣本”最?的組成和維數(shù)相同的向量，則.② ③是因為 ，則 的?個分量，所以.③ ④是平?差式展開.④ ⑤是因.式(10.3)解析式(10.4）解析?先根據(jù)式(10.3)有對于第?項，根據(jù)矩陣跡的定義， .對于第?項，于求和號內(nèi)元素和?關(guān)，因此.對于第三項，有中?化

是利?了“??書”上的前提條件，即將降維后的樣本被式(10.5）參?式(10.4)式(10.6）解析其中“??書”中假設(shè)降維后的樣本被中?化式(10.10)解析由式(10.3)可得由式(10.6)和式(10.9)可得由式(10.4)和式(10.8)可得由式(10.5)和式(10.7)可得綜合可得式(10.14)解析已知，則constconstconstconst式(10.17)解析由式(10.15)可知，主成分分析的優(yōu)化?標為其中，為單位矩陣.對于帶矩陣約束的優(yōu)化問題，其優(yōu)化?標的拉格朗?函數(shù)為讀者可搜索Lagrangianoptimizationwithmatrixconstrains了解更多其中，為拉格朗?乘?矩陣，其維度恒等于約束條件的維度，且其中的每個元素均為未知的拉格朗?乘?；為矩陣的內(nèi)積.若此時僅考慮約束，則拉格朗?乘?矩陣此時為對?新的拉格朗?乘?矩陣為，則新的拉朗?函數(shù)為讀者可搜索Frobeniusinnerproduct了解更多對拉格朗?函數(shù)關(guān)于 求導(dǎo)可得矩陣微分式：令 可得將 和展開可得顯然，此式為矩陣特征值和特征向量的定義式，其中和 分別表?矩陣的特征值和單位特征向量.由于以上是僅考慮約束所求得的結(jié)果，? 還需滿?約束.觀的定義可知，是?個實對稱矩陣，實對稱矩陣的不同特征值所應(yīng)的特征向量之間相互正交，同?特征值的不同特征向量可以通過施密特正交化使其變得正交，所以通過上式求得的可以同時滿?約束和.根據(jù)拉格朗?乘?法的原理可知，此時求得的結(jié)果僅是最優(yōu)解的必要條件，?且有個相互正交的單位特征向量，所以還需要個特征向量?找出個能使得?標函數(shù)最優(yōu)值的特征向量作為最優(yōu)解.將代??標函數(shù)可得顯然，此時只需要令和 分別為矩陣的前個最?的特征值和單位特征向量就能使得?標函數(shù)達到最優(yōu)值.式(10.24)解析已知，類?可以構(gòu)造，所以式(10.21)可變換為?由式(10.22)可知其中，,所以式(10.21)可以進?步變換為此時的?標是求出 ，等價于求出滿?上式的.顯然，此時滿?的?定滿?上式，所以問題轉(zhuǎn)化為了求解滿?令，那么上式可化為即式(10.24)，其中矩陣 的第?第列的元素.式(10.28)解析由“??書”中上下?可知，式(10.28)是如下優(yōu)化問題的解：s.t.若令，則上述優(yōu)化問題的?標函數(shù)可以進?如下恒等變形其中，?如下恒等變形：

.同理，約束條件也可以進其中為?1列的單位向量.因此，上述優(yōu)化問題可以重寫為顯然，此問題為帶約束的優(yōu)化問題，因此可以考慮使?拉格朗?乘?法來進?求解.由拉格朗?乘?法可得此優(yōu)化問題的拉格朗?函數(shù)對拉格朗?函數(shù)關(guān)于 求偏導(dǎo)并令其等于0有矩陣微分式：若可逆，則?因為，則上式兩邊同時左乘可得即將其代回 即可解得設(shè)矩陣第?第列的元素為 ，則即式(10.28).顯然，若可逆，此優(yōu)化問題即凸優(yōu)化問題，且此時?拉格朗?乘?法求得的 為全局最優(yōu)解.式(10.31)約束條件是為了得到標準化（標準正交空間）的低維數(shù)據(jù)解析其中.第第11章 特征選擇與稀疏學(xué)習(xí)式(11.1)解析此為信息增益的定義式.對于數(shù)據(jù)集和屬性?集，假設(shè)根據(jù)的取值將分為了個?集，那么信息增益的定義為劃之前數(shù)據(jù)集的信息熵和劃分之后每個?數(shù)據(jù)集的信息熵的差.熵?來衡量?個系統(tǒng)的混亂程度，因此劃分前和劃分后熵的差越?，表?劃分越有效，劃分帶來的“信息增益”越?.式(11.2)解析此為信息熵的定義式.其中所占的?例.可以看出，樣本越純，即?，其最?值為0.或表? 中第類樣時，越此處約定式(11.5)解析該式為線性回歸的優(yōu)化?標式表?樣本的真實值，?表其預(yù)測值，這?使?預(yù)測值和真實值差的平?衡量預(yù)測值偏離真實值的程度.式(11.6)解析該式為加?了正規(guī)化項的優(yōu)化?標，也叫“嶺回歸”.?來調(diào)節(jié)差項和正規(guī)化項的相對重要性.引?正規(guī)化項的?的是降低因的分量過太?導(dǎo)致過擬合的?險.式(11.7)解析該式將式(11.6)中的正規(guī)化項替換成了正規(guī)化項.關(guān)于和兩個正規(guī)化項的區(qū)別，“??書”圖11.2給出了很形象的解釋.具結(jié)合范數(shù)優(yōu)化的模型參數(shù)分量更偏向于取0，因此更容易取得稀疏解.式(11.10)解析?先注意優(yōu)化?標式和式(11.7)LASSO回歸的聯(lián)系和區(qū)別，本式中的對應(yīng)到式(11.7)的，即我們優(yōu)化的?標.再解釋下什么是條件：根據(jù)維基百科的定義，它是?個?“連續(xù)”更強的光滑性條件.直覺上，利普希茨連續(xù)函數(shù)限制了函數(shù)改變的速度，符合利普希茨條件的函數(shù)的斜率，必?于?個稱為利普希茨常數(shù)的實數(shù)（該常數(shù)依函數(shù)?定）.注意這?存在?個筆誤，根據(jù)維基百科的定義，式(11.9)應(yīng)該寫成移項得由于上式對所有的和 都成?，由導(dǎo)數(shù)的定義，上式可以看成是的?階導(dǎo)數(shù)恒不?于,即.接下來推導(dǎo)式(11.10).由泰勒式可知， 附近的通過?階泰展開可近似為其中 .式(11.11)解析此式很容易理解.因為范數(shù)的最?值為0，因此當時，有恒成?，同理等.反復(fù)迭代能夠使的值不斷下降.式(11.12）解析式(11.11)的優(yōu)化?標為，?式(11.8)優(yōu)化的函數(shù)為.由泰勒展開式，有. 的更由式(11.12)決定.參?式(11.10)式(11.13）解析這?將式(11.12)的優(yōu)化步驟拆分成了兩步.?先設(shè)并計算，然后再求解式(11.13)，得到的結(jié)果是?致的.式(11.14)解析設(shè)優(yōu)化函數(shù)這個式?表明優(yōu)化可以被拆解成優(yōu)化的各個分量的形式，對分量，其優(yōu)化函數(shù)求導(dǎo)得其中對于的特殊情況，由于在點處不光滑，所以其不可導(dǎo)，需單獨討論.令有此式的解即優(yōu)化?標的極值點，因為等式兩端均含有未知變量，故分情況討論.當時：假設(shè) ，則 ，那么有與假設(shè)?盾.假設(shè) ，則 ，那么有和假設(shè)相符合下?來檢驗是否是函數(shù) 的最?值點.當 時有在定義域內(nèi)連續(xù)可導(dǎo)，則的?階導(dǎo)數(shù)由于利普希茨常數(shù)恒?于0，因此 是函數(shù)的最?值.當 時：假設(shè) ，則 ，那么有與假設(shè)?盾.假設(shè) ，則 ，那么有與假設(shè)符，由上述?階導(dǎo)數(shù)恒?于0可知，是 的最?值.當時：假設(shè) ，則 ，那么有與假設(shè)?盾.假設(shè) ，則 ，那么有與假設(shè)?盾.當 時有.當 時，由上述推導(dǎo)可知的最?值在 處取得.因為因此當 時， 不會是函數(shù)的最?值.當 時，對于任何有因此 是的最?值點.綜上所述，式(11.14)成?.式(11.15)解析此式即希望樣本的稀疏表?通過字典重構(gòu)后和樣本的原始表?盡量相似，如果滿?這個條件，那么稀疏表?是?較好的.后?的1范數(shù)項是為了使更加稀疏.式(11.16)解析為了優(yōu)化式(11.15)，我們采?類似EM算法的變量交替優(yōu)化：?固定變量 ，則式(11.15)求解的是 個樣本相加的最?值.這是由于式?沒有樣本之間的交互，即“??書”中所述形式，因此可以對每個變量做分別的優(yōu)化求出 ，求解?法?式(11.13)和式(11.14).式(11.17)解析這是優(yōu)化式(11.15)的第?步，固定住，此時式(11.15)的第?項為?個常數(shù)，優(yōu)化式(11.15)即優(yōu),其寫成矩陣相乘的形式為，將 范數(shù)擴展到Frobenius數(shù)即得優(yōu)化?標為.式(11.18)解析這個式難點在于推導(dǎo).?致的思路是會?成和矩陣同樣維度的矩陣，這個矩陣對應(yīng)位置的元素是中對應(yīng)位置元素的?個分量，這樣的分量矩陣?共個，把所有分量矩陣加起來得到了最終結(jié)果.推導(dǎo)過程如下：求和可得：將矩陣 分解成矩陣列帶來?個好處，即和式(11.16)的原理相同，矩陣列與列之間?關(guān)，因此可以分別優(yōu)化各個列，即將轉(zhuǎn)化成了，得到第三?的等之后，再利??中介紹的KSVD算法求解即可.第第12章 計算學(xué)習(xí)理論式(12.1)解析此式為泛化誤差的定義式.所謂泛化誤差，是指當樣本從真實樣本分布中采樣后其預(yù)測值不等于真實值的概率.在現(xiàn)實世界中，我們很難獲得樣本分布，?實際獲得的數(shù)據(jù)集可以看作從樣本分布中獨?同分布采樣得到的.在“??書”中，我們稱實際獲得的據(jù)集為樣例集(也叫觀測集、樣本集，注意與花體的區(qū)別).式(12.2)解析此式為經(jīng)驗誤差的定義式.所謂經(jīng)驗誤差，是指觀測集中的樣的預(yù)測值和真實值的期望誤差.式(12.3)解析假設(shè)我們有兩個模型和，將它們同時作?于樣本上，那么們的“不合”度定義為這兩個模型預(yù)測值不相同的概率.此為Jensen不等式式(12.4)解析此式可以做很直觀的理解.?如在?維空間，凸函數(shù)可以想象成開?向上的拋物線.假設(shè)拋物線上有兩個點 ，那么表?兩個點的均值的縱坐標，?表?的是兩個點縱坐標的均值.因為兩點的均值落在拋物線的凹處，所以均值的縱坐標會??些.式(12.5)此為Hoeffding不等式解析對于獨?隨機變量 來說，它們的觀測值的均值總是和它們的期望 的均值相近.此式從概率的?度對這個結(jié)論進?了描述：事件“觀測值的均值和期望的均值之間的差值不?于”發(fā)?的概率不?于.可以看出，當觀測到的變越多，觀測值的均值越逼近期望的均值.式(12.7)此為McDiarmid不等式解析?先解釋此式的前提條件此條件表?當函數(shù)的某個輸?由 變?yōu)楹?，其函?shù)值變化的上確界 仍不?于.所謂上確界sup可以理解成變化的極限最?值，可能被取到也可能被?限逼近.McDiarmid不等式指出，當此條件被滿?時，函數(shù)值和其期望值也相近.從概率的度描述，即事件“函數(shù)值和其期望之間的差值不?于”發(fā)?的概率不?于.可以看出，當每次變量改動帶來函數(shù)值改動的上限越?，函數(shù)值和其期望越相近.式(12.9）解析此式中表?算法在?觀測集訓(xùn)練后輸出的假設(shè)函數(shù)的化誤差辨識的定義指出，如不?于的概率，那么稱學(xué)習(xí)算法能從假設(shè)空間 中辨識概念類.泛化誤差?式(12.1)式(12.10)①②③式(12.10)(12.14)是為了回答“??書”中的問題：到底需要多少樣例才能學(xué)得?標概念的有效近似？只要訓(xùn)練集的規(guī)模能使學(xué)習(xí)算法以概率找到?標假設(shè)的近似即可.式(12.10)(12.14)?數(shù)學(xué)式對這個回答進?抽象解析①是因和是對?事件.① ②是因為泛化誤差定義[?式(12.1)].由于我們假定了泛化誤，因此有，即② ③.式(12.11)解析先解釋什么是與“表現(xiàn)?致”.“??書”12.2節(jié)開頭闡述了這樣的概念：如將中所有樣本按與真實標記?致的?式完全分們則稱問題對學(xué)習(xí)算法是?致的,即為真.因為每個事件是獨?的，所以上式可以寫成.根據(jù)對?事件的定義，有，?根據(jù)式(12.10)，有式(12.12）解析?先解釋為什么“我們事先并不知道學(xué)習(xí)算法會輸出中的哪個假設(shè)”.這是因為?些學(xué)習(xí)算法對??個觀察集的輸出結(jié)果是?確定的.感知機就是個典型的例?：訓(xùn)練樣本的順序也會影響感知機學(xué)習(xí)到的假設(shè)參數(shù)的值.泛化誤差?于且經(jīng)驗誤差為0的假設(shè)(即在訓(xùn)練集上表現(xiàn)完美的假設(shè))出現(xiàn)的概率可以表?為.根據(jù)式(12.11)，每?個這樣的假設(shè)都滿?設(shè)這樣的假設(shè)的數(shù)量為.因為每個假設(shè)滿?且.是互斥的，因此總的概率就是這些互斥事件和，即參?式(12.11)接下來要證明，即證明，其中， 是正整數(shù).證明如下.當 時，該式顯然成?.當時，因為左式和右式的值域均?于0，所以可以左右兩邊同時取對數(shù)；?因為對數(shù)函數(shù)是單調(diào)遞函數(shù)，所以即證明，即證明.這個式?很容易證明：設(shè)，其中，則有，即 時取極?值0，因此有，即成?.式(12.13)解析回到我們要回答的問題：到底需要多少樣例才能學(xué)得?有效近似？只要訓(xùn)練集的規(guī)模能使學(xué)習(xí)算法以概率找到?標假似即可.根據(jù)式(12.12)，學(xué)習(xí)算法?成的假設(shè)?于?似的概率為，因此學(xué)習(xí)算法?成的設(shè)落在?標假設(shè)的近似的概率為，我們希望這個概率?少是 ，因此有.式(12.14）解析這個式?告訴我們，若假設(shè)空間 是可學(xué)習(xí)的，輸出假設(shè)的泛化誤差隨樣本數(shù)?增??收斂到0，收斂速率為.這也是我在機器學(xué)習(xí)中的?個共識，即可供模型訓(xùn)練的觀測集樣本數(shù)量越多，機器學(xué)習(xí)模型的泛化性能越好.式(12.15)參?式(12.5)式(12.16）參?式(12.5)式(12.17）參?式(12.6)式(12.18）解析令，則 ，由式(12.17)有將 代?即此式得證.此式進?步闡明了當觀測集樣本數(shù)量?夠?的時候，的經(jīng)驗誤差是其泛化誤差很好的近似.式(12.19)令表?假設(shè)空間 中的假設(shè)，有這?步很好理解：存在?個假設(shè)使得的概率可以表?為對假設(shè)空間內(nèi)所有的假設(shè) )使這事件成?的“或”事件.因，?，所以最后??的不等式成?.由式(12.17)有因此其對?事件的概率令，則 ，代?上式中即有其中前置條件 可以省略.式(12.20)解析此式是“不可知可學(xué)習(xí)”的定義式.不可知是指當?不算法所能?成的假設(shè)空間?.可學(xué)習(xí)是指如果中泛化誤差最?的假設(shè)是，且這個假設(shè)的泛化誤差滿?其與?標概念的泛化誤差的差值不?于的概率不?于.我們稱這樣的假設(shè)空間是不可知可學(xué)習(xí)的.式(12.21）解析此式是增?函數(shù)的定義式.增?函數(shù)表?假設(shè)空間 對 個本所能賦予標簽的最?可能的結(jié)果數(shù).?如對于有2個樣本的?分類問題，?共有4種可能的標簽組合：.如果假設(shè)空間能賦予這2個樣本2種標簽組合，則.顯然，對樣本所能賦予標簽的可能結(jié)果數(shù)越多，的表?能?就越強.增可以?來反映假設(shè)空間的復(fù)雜度.式(12.22）解析截?2018年12?“??書”第1版第30次印刷，式(12.22)的前提假設(shè)應(yīng)當勘誤為“對假設(shè)空間，，，存在”.詳細證明可參?“??書”及本書側(cè)欄的原論?.原論?標題為“Ontheuniformconvergenceofrelativefrequencieseventstotheirprobabilities”[1]式(12.23）解析此式是VC維的定義式.VC維的定義是能被打散的最??例集的??.“??書”中例12.1和例12.2給出了形象的例?.注意，VC維的定義式上的底數(shù)2表?這個問題是?分類的問題.如果是分類的問題，那么定義式中底數(shù)需要變?yōu)?式(12.24)解析?先解釋“??書”中數(shù)學(xué)歸納法的起始條件“時，定理成?”.當時，由VC維的定義式可，否則可以取到1.?因為為整數(shù)，所以，式(12.24)右側(cè)為，因此不等式成?.當時，因為?個樣本最多只能有兩個類別，所以，不等式右側(cè)為，因此不等式成?.接下來解釋歸納過程.這?采?的歸納?法是假設(shè)式(12.24)對和成?，推導(dǎo)出其對也成?.證明過程中引?觀測集和觀測集，其中? 多?個樣本 ，它們對應(yīng)的假設(shè)空間可以表?為：如果 對 的分類結(jié)果為 或 ，那么任何出現(xiàn)在中的串都會在中出現(xiàn)?次或者兩次.這?舉個例?就很容易理解了，假設(shè)，則有其中串在中出現(xiàn)了兩次：，?中的其他串在中均只出現(xiàn)了?次.這?的原因是每個樣本是?分類的，所以多出的樣本 要么取，要么取，要么都取（?少兩個假設(shè)對 做出了不?致的判斷）.記號表?在中出現(xiàn)了兩次的組成的集合，此時由于表?限制在樣本集 上的假設(shè)空間 的表達能?（即所有假設(shè)對樣本集 所能賦予的標記種類數(shù)），樣本集 的??為 根據(jù)增?函數(shù)的定義，假設(shè)空間 對包含個樣本的集合所能賦予的最?標記種類數(shù)為，因此.?根據(jù)數(shù)學(xué)歸納法的前提假設(shè)，有由記號的定義可知 ，?由于和均為整數(shù)，因此，由于樣本集的??為 ，根據(jù)增?函數(shù)的概念，有.假設(shè)表?能被 打的集合.根據(jù)的定義， 必對元素 給定了不?致的判定，因必能被打散，由前提假設(shè)的VC維為，因的VC維最?為 ，綜上有因此其中，最后?步依據(jù)組合式.具體推導(dǎo)如下：式(12.25)參?式(12.24)式(12.26）參?式(12.24)式(12.27）參?式(12.24)式(12.28）解析①②③⑤⑥① ②和③④均因為 ;④ ⑤是由于?項式定理令得⑤ ⑥的不等式即需證明 ，因為，根據(jù)e的定義，有.注意“?書”中?的是，但是由于的定義是?個極限，所以可?.式(12.29)請注意某些印次的“??書”中漏印的絕對值符號解析將式(12.28)代?式(12.22)得令 可解得代?式(12.22)，則定理得證.此式?VC維表?泛化界.可以看出，泛化誤差界只與樣本數(shù)量 關(guān)，收斂速率為??書”上簡化為).式(12.30）解析此式是經(jīng)驗?險最?化的定義式，從假設(shè)空間中找出能使經(jīng)驗?險最?的假設(shè).式(12.31）解析?先回憶可學(xué)習(xí)的概念，?定義12.2，?可知/不可知學(xué)習(xí)之間的區(qū)別僅僅在于概念類是否包含于假設(shè)空間 中.令結(jié)合這兩個標記的轉(zhuǎn)換，由推論12.1可知,?少以 的概率成?.寫成概率的形式有即 ，因此且 成?.再令由式(12.29)可知同理，且成?.由和均成?可知,事件和件同時成?的概率即因此再由和的定義可知，表?假設(shè)空間中經(jīng)驗誤差最?的假設(shè)，表?泛化誤差最?的假設(shè).將這兩個假設(shè)共?作?于樣本集，有，因此上式可以簡化為根據(jù)式(12.32)和式(12.34)，可以求出 為關(guān)于的多項式.根據(jù)定理12.2和定理12.5可得到結(jié)論任何VC維有限的假設(shè)空間 都是（不可知可學(xué)習(xí)的.式(12.32)參?式(12.31)式(12.34）參?式(12.31)式(12.36）①②③解析這?解釋① ②的推導(dǎo).因為前提假設(shè)是?分類問題，即，因此.具體來說，假如或，有；反之，假如或，有.式(12.37)解析由式(12.36)可知，經(jīng)驗誤差 和呈反?的關(guān)系，此假設(shè)空間中能使經(jīng)驗誤差最?的假設(shè)即是使最?的.上確界 這個概念的解釋?式(12.7)的解析式(12.38）解析由于 是隨機變量，因此此式可以理解為求解和隨機?成的標簽(即)最契合的假設(shè).當和完全?致時，它們的內(nèi)積最?式(12.39）解析此式可以?來衡量假設(shè)空間 的表達能?，對變量求期望可以解為當變量包含所有可能的結(jié)果時，假設(shè)空間 中最契合的假設(shè)和變量的平均契合程度.因為前提假設(shè)是?分類的問題，因此?共有種，這些不同的構(gòu)成了數(shù)據(jù)集的“對分”.?個假設(shè)空間的表達能?越強，假設(shè)空間中就越有可能對于每?種都存在?個使得和?常接近甚?相同，對所有可能的取望即可衡量假設(shè)空間的整體表達能?，這就是這個式?的含義.參?“??書”12.4節(jié)式(12.40）解析對?式(12.39)，這?使?函數(shù)空間代替假設(shè)空間、函數(shù)代.這很容易理解，因為可以看作作?在數(shù)據(jù)上的?個映射，通過這個映射可以得到標簽.注意前提假設(shè)實值函數(shù)空間，即函數(shù)將樣本 映射到了實數(shù)空間，此時所有的將是個標量，即.式(12.41)解析這?所要求的是 關(guān)于分布的Rademacher復(fù)雜度，因此從 中出不同的樣本，計算這些樣本對應(yīng)的Rademacher復(fù)雜度的期望.式(12.42）解析?先令記號即表?函數(shù)作為假設(shè)下的經(jīng)驗誤差，表?經(jīng)驗誤差和泛化誤差的上確界.再令 為只與有?個?例(樣本)不同的訓(xùn)練集不妨設(shè)和為不同的?例，那么有①②④⑤① ②是因為上確界的差不?于差的上確界，③④是由于 只有 不相同，④ ⑤是因為前提假，即.同理有綜上?式有將看作式(12.7)中的函數(shù)則有注意區(qū)別式(12.7)中的和定義?的令 可以求得 ，所以由逆事件的概率定義得此即式(12.44)的結(jié)論下?來估計的上界,有①②③④⑤⑥⑦⑧Jesen不等式參?式(12.4)① ②是在外?套了?個對服從分布的?例集 求期望.因為，?采樣出來的 和相互獨?，因此有.② ③的不等式基于上確界函數(shù) 是凸函數(shù)，根據(jù)Jesen不等式，有其中是的簡寫形式.④ ⑤引?對Rademacher隨機變量的期望，由于函數(shù)值空間是標量，? 也是標量，即，且 總可以以相同概率取到這個值，因此可以引??不影響最終結(jié)果.⑤⑥是因為上確界的和不?于和的上確界.同時，因只含有變量，所以可以去掉；因為第?項中只含有變量，所以可以去掉.⑥ ⑦利?了的對稱性（即 的分布和完全?致）去除第?中的負號.?因為和 均是從 中獨?同分布采樣得到的數(shù)據(jù)，因此可以將第?項中的替換成，將 替換成.最后根據(jù)式(12.41)可得，式(12.42)得證.式(12.43)參?式(12.42)式(12.44）參?式(12.42)式(12.45）參?式(12.42)式(12.46）參?式(12.42)式(12.52）本式的證明?較煩瑣.同“??書”上所?，參?MehryarMohri等?的書籍FoundationsofMachineLearning(即本章參考?獻[2])式(12.53）解析根據(jù)式(12.28)有.根據(jù)式(12.52)，有，因此 ，再根據(jù)式(12.47)即得證.式(12.57)①②解析根據(jù)三?不等式，令，，代?即有①的不等關(guān)系，由表?移除中第個樣本，表?替換中第個樣本，那么和的變動均為?個本，根據(jù)式(12.57)，有，因此.式(12.58）證明過程?較煩瑣，參?本章參考?獻[2]式(12.59）證明過程?較煩瑣，參?本章參考?獻[2]式(12.60）將 代?式(12.58)即得證定理12.9若學(xué)習(xí)算法是ERM且是穩(wěn)定的，則假設(shè)空間 可學(xué)習(xí).解析?先明確?個概念，ERM表?算法滿?經(jīng)驗?險最?化(EmpiricalRiskMinimization).由于算法滿?經(jīng)驗誤差最?化，則可令表?假設(shè)空間中具有最?泛化損失的假設(shè)，即再令將 代? 可以解得 ，由Hoeffding不等式，有參?式(12.6)其中 ， ，代?可得根據(jù)逆事件的概率可得即?中?少以 的概率成?.由可以求解出即 .由和式(12.31)中介紹的相同的?法，可以推導(dǎo)出?因為 為與相關(guān)的多項式的值，根據(jù)定理、定理12.5，可得到結(jié)論：是（不可知可學(xué)習(xí)的.參考參考?獻VLADIMIRVN,AOntheUniformConvergenceofRelativeFrequenciesofEventstoTheirProbabilities[M]//MeasuresofComplexity.Berlin:SprinMOH