1、機器學習For 2012級計算機應用技術研究生主講 李鶴喜機器學習概述簡介1、概述 機器學習是近20多年興起的一門多領域交叉學科，涉及概率論、統計學、逼近論、凸分析、算法復雜度理論等多門學科。機器學習理論主要是設計和分析一些讓計算機可以自動“學習”的算法。機器學習算法是一類從數據中自動分析獲得規律，并利用規律對未知數據進行預測的算法。因為學習算法中涉及了大量的統計學理論，機器學習與統計推斷學聯系尤為密切，也被稱為統計學習理論。算法設計方面，機器學習理論關注可以實現的，行之有效的學習算法。很多推論問題屬于無程序可循難度，所以部分的機器學習研究是開發容易處理的近似算法。機器學習概述機器學習應用2、

2、機器學習的應用機器學習已經有了十分廣泛的應用，例如：數據挖掘、計算機視覺、汽車自動駕駛、語音和手寫識別、自然語言處理、生物特征識別、搜索引擎、醫學診斷、檢測信用卡欺詐、證券市場分析、DNA序列測序、戰略游戲和機器人運用機器學習概述機器學習的發展歷史4、機器學習的發展歷史機器學習的研究基本上經歷了以下幾個發展時期通用的學習系統研究，基于符號表示的概念學習系統研究，基于知識的各種學習系統研究，聯接學習和符號學習的深入研究。（1）通用學習系統的研究 這一時期從50年代中葉開始，幾乎和人工智能學科的誕生同步。當時，人工智能的研究著重于符號表示和啟發式方法的研究，而機器學習卻致力于構造一個沒有或者只有很

3、少初始知識的通用系統，這種系統所應用的主要技術有神經元模型、決策論和控制論。 鑒于當時計算機技術的限制，研究主要停留在理論探索和構造專用的實驗硬件系統。這種系統以神經元模型為基礎，只帶有隨機的或部分隨機的初始結構，然后給它一組刺激，一個反饋源和修改自身組織的足夠自由度，使系統有可能自適應地趨向最優化組織。這種系統的代表是稱為感知器的神經網絡。 機器學習概述機器學習的發展歷史（1）通用學習系統的研究 這種系統的代表是稱為感知器的神經網絡。系統的學習主要靠神經元在傳遞信號的過程中，所反映的概率上的漸進變化來實現。同時也有人開發了應用符號邏輯來模擬神經元系統的工作，如McCulloch 和 Pitt

4、s用離散決策元件模擬神經元的理論。相關的工作包括進化過程的仿真，即通過隨機演變和自然選擇來創造智能系統，如Friedberg的進化過程模擬系統。這方面的研究引出了二個副產品:形成了人工智能的一個新分支模式識別，并創立了學習的決策論方法。這個方法的學習含義是從給定的例子集中，獲取一個線性的、多項式的或相關的識別函數。 機器學習概述機器學習的發展歷史（1）通用學習系統的研究 神經元模型的研究未取得實質性進展，并在60年代末走入低谷。作為對照，一種最簡單、最原始的學習方法-機械學習，又稱為死記式學習，卻取得了顯著的成功。該方法通過記憶和評價外部環境提供的信息來達到學習的目的。采用該方法的代表性成果是

5、塞繆爾(A.L.Samuel)于50年代末設計的跳棋程序，隨著使用次數的增加，該程序會積累性記憶有價值的信息，可以很快達到大師級水平。正是機械學習的成功激勵了研究者們繼續進行機器學習的探索性研究。 機器學習概述機器學習的發展歷史（2）基于符號表示的概念學習系統研究 人們研究了從例子中學習結構化概念的各種不同方法。也有部分研究者構造了面向任務的專用系統，這些系統旨在獲取特定問題求解任務中的上下文知識，代表性工作有亨特和哈蘭德(Hunt & C.I.Hovland)的CLS和巴查納(B.G.Buchanan)等的META-DENDRAL，后者可以自動生成規則來解釋DENDRAL系統中所用的質譜數據

6、。這個時期機器學習的研究者已意識到應用知識來指導學習的重要性，并且開始將領域知識編入學習系統，如META-DENDRAL和里南(D.B.Lenat，1976)的AM等。 機器學習概述機器學習的發展歷史（3）基于知識的學習系統研究這時期的工作特點主要有三個方面:1)基于知識的方法:著重強調應用面向任務的知識和指導學習過程的約束。從早先的無知識學習系統的失敗中吸取的教訓就是:為獲取新的知識，系統必須事先具備大量的初始知識。2)開發各種各樣的學習方法，除了早先從例子中學習外，各種有關的學習策略相繼出現，如示教學習, 觀察和發現學習。同時也出現了如類比學習和基于解釋的學習等方法。3)結合生成和選擇學習

7、任務的能力:應用啟發式知識于學習任務的生成和選擇，包括提出收集數據的方式、選擇要獲取的概念與控制系統的注意力等。 機器學習概述機器學習的發展歷史（4）聯接學習和符號學習的深入研究 與此同時，符號學習已經歷了三十多年的發展歷程，各種方法日臻完善，出現了應用技術蓬勃發展的景象。最突出的成就有分析學習(特別是解釋學習)的發展, 遺傳算法的成功，和加強學習方法的廣泛應用。特別是近幾年來，隨著計算機網絡的發展，基于計算機網絡的各種自適應、具有學習功能的軟件系統的研制和開發都將機器學習的研究推向新的高度，網絡環境已成為人工智能和機器學習的重要試驗床。 一、機器學習概述機器學習的發展歷史一、機器學習概述三個

8、密切相關的概念人工智能、模式識別、機器學習是三個密切相關的概念人工智能目的是給機器賦予人類的智能，讓機器能夠像人類那樣思考、判斷和推理。當然，目前的人工智能沒有發展到很高級的程度，這種智能與人類的大腦相比還是處于非常幼稚的階段，但目前我們可以讓計算機掌握一定的知識，更加智能化的幫助我們實現簡單或復雜的活動。人工智能更關注的是符號信息與知識的推理，模式識別更關注感知信息處理，而機器學習是介于模式識別和人工智能之間，注重于模式識別中的學習問題。我變聰明了我學會認識鳥了！一、機器學習概述三個密切相關的概念人工智能、模式識別、機器學習是三個密切相關的感念，機器學習通俗的說就是讓機器自己去學習，然后通過

9、學習到的知識來指導進一步的判斷。舉個最簡單的例子，我們訓練機器人識別鳥，我們用一堆的鳥的樣本數據來讓計算機進行運算，樣本數據可以是有類標簽的，并設計懲罰函數，通過不斷的迭代，機器就學會了怎樣進行區分鳥和其它動物，使得懲罰最小，然后用學習到的分類規則進行預測等活動。一、機器學習概述三個密切相關的概念人工智能、模式識別、機器學習是三個密切相關的感念模式識別模式識別偏重于對信號、圖像、語音、文字、指紋等非直觀數據的自動辨識處理，如語音識別、人臉識別、指紋識別、工件識別等，通過提取出相關的特征，利用這些特征和機器學習算法來進行搜尋我們想要找的目標，注重的是結果。我認得：這是一只鳥人工智能、模式識別、機

10、器學習三者之間的關系人工智能模式識別機器學習人工智能提供智能處理架構、概念和推理方法機器學習提供自動學習的理論與方法是實現智能化的技術模式識別是機器學習、人工智能的運用實踐一、機器學習概述三個密切相關的概念一、機器學習概述機器學習的基本架構5、機器學習的基本架構一個典型的機器學習架構由學習環境、學習算法、知識庫和實踐執行四部分組成。環境學習部分（學習算法）知識庫（知識表示）訓練數據知識累積待辨識數據執行部分（識別）輸出結果反饋評估一、機器學習概述機器學習的典型算法機器學習的典型算法1、k-NN最近鄰居法*2、貝葉斯學習法*3、決策樹學習法*4、神經網絡學習法*5、支持向量機學習法*6、關聯規則

11、學習法7、集成學習法*8、聚類分析學習法*9、強化學習法10、事例推理學習法23 對輸入樣本 x, 從訓練樣本中找到與x距離最近的K個最近樣本，以它們最可能的類標簽來分類x。xk=1k=6 二 、K-NN最近鄰分類算法紅點類別1綠點類別2黑點待分類輸入1 、K-NN算法的相似度量 K-NN算法需要計算樣本之間的度量函數，最常見的有歐氏距離、 Minkowski距離、馬氏距離、manhattan距離等。1、歐氏距離測試樣本已知訓練集數據點1 、K-NN算法的相似度量3、馬氏距離 Mahalanobis這里是方差矩陣，是原型樣本均值。采用馬氏距離相當用方差的倒數來進行加權，相當于使決策界從方差較大

12、的一方朝方差較小一方移動。 割草機制造商想把某一個城市家庭分為需要買割草機和不需要買割草機的兩類家庭，在這個城市隨機抽取12有割草機的家庭和12個沒有割草機的家庭， 設樣本屬性有兩個x=x1,x2T x1表示家庭收入，x2表示擁有草地面積其數據如表2-1所示。0表示無，1表示有2 、K-NN算法的實例觀測點收入（x1）草地面積（x2）有/無16018.41285.516.81364.821.61461.520.8158723.616110.119.21710817.61882.822.41969201109320.8111512211281201表 2-1購買割草機的樣本數據集2 、K-NN算

13、法的實例2 、K-NN算法的實例k134579111318錯分率333333333333171750表2-2 不同K值對測試集的誤分率隨機取數據集中18個樣本為訓練樣本，6個為測試樣本，其中6,7,12,14,19,20為測試樣本。K取較小的值，對局部特征敏感，k取較大的值，相當取多個數據點的平均值，濾掉波動，比較穩定，當K=18，取極端值完全忽略樣本的屬性，錯分率取決正/負樣本比例。通過上面的實例可以歸納k-NN算法步驟如下：步驟1、將訓練樣本按相似度similarity閾值正確分類；2、依距離測度公式計算x 與 D1、D2 、Dj 之相似度sim。得到Sim(Item, D1)、Sim(I

14、tem, D2) 、Sim(Item, Dj)。3.將Sim(Item, D1)、Sim(Item, D2) 、Sim(Item, Dj)排序，若是超過相似度門檻t則放入鄰居案例集合NN。4.自鄰居案例集合NN中取出前k名，依多數決，得到Item可能類別。2 、K-NN算法的步驟32K-NN的關鍵問題距離度量最常用方法: euclidean更好的距離度量: normalize each variable by standard deviation離散數據：Hamming distanceK的選擇Increasing k reduces variance, increases bias高維空間的

15、可區分性差For high-dimensional space, problem that the nearest neighbor may not be very close at all!大數據量時計算開銷大Must make a pass through the data for each classification. This can be prohibitive for large data sets.Indexing the data can help; for example KD trees3 、貝葉斯學習算法3.1概述 貝葉斯學習算法是一種依據統計學原理的學習方法，更確切地

16、說它是一類利用概率統計知識進行分類的算法。在許多場合，樸素貝葉斯(Naive Bayes，NB)分類算法可以與決策樹和神經網絡分類算法相媲美，該算法能運用到大型數據庫中，且方法簡單、分類準確率高、速度快。貝葉斯學習的特點：貝葉斯推理提供了一種概率手段，基于如下的假定：待考察的量遵循某概率分布，且可根據這些概率及已觀察到的數據進行推理，以作出最優的決策。貝葉斯推理為衡量多個假設的置信度提供了定量的方法。貝葉斯推理為直接操作概率的學習算法提供了基礎，也為其他算法的分析提供了理論框架。3 、貝葉斯學習算法3.2 一些與貝葉斯學習有關的預備知識確定事件：概念是確定的，發生也是確定的；隨機事件：概念是確

17、定的，發生是不確定的；模糊事件：概念本身就不確定。1、隨機變量隨機變量：隨機事件的數量表示；離散隨機變量：取值為離散的隨機變量 ；連續隨機變量：取值為連續的隨機變量 ；3.2 一些預備知識2、頻率和概率頻率：試驗在相同的條件下重復N次，其中M次事件A發生，則A發生的頻率為： fN(A) = M / N概率：當N很大時，頻率會趨向一個穩定值，稱為A的概率：3.2 一些預備知識3、聯合概率和條件概率聯合概率：設A，B是兩個隨機事件，A和B同時發生的概率稱為聯合概率，記為：P(A, B)；條件概率：在B事件發生的條件下，A事件發生的概率稱為條件概率，記為：P(A|B)； 乘法定理：P(A|B) =

18、P(A, B) / P(B)。 P(A, B)= P(A|B) P(B)。 3.2 一些預備知識4、概率密度函數概率分布函數：設X為連續型隨機變量，定義分布函數；F(x) = P(Xx)；概率密度函數：給定X是隨機變量，如果存在一個非負函數f(x)，使得對任意實數a,b(ab)有 P（aXb) = f(x)dx, （積分下限是a,上限是b) ，則稱f(x)為X的概率密度函數3.2 一些預備知識概率密度函數f(x)3.2 一些預備知識條件概率P（A|B)： 設A、B是兩個隨機事件，則有：P（A)-事件A的先驗概率（prior probability）P(A|B)-事件A的后驗概率（ poster

19、ior probability）5、事件概率的貝葉斯定理3.2 一些預備知識條件概率P（A|B)： 設A、B是兩個隨機事件，則有：P（A)-事件A的先驗概率（prior probability）P(A|B)-事件A的后驗概率（ posterior probability）6、事件概率的貝葉斯定理 P(ci) 先驗概率P(x) 是x的先驗概率P(ci|x)后驗概率3.3 基于貝葉斯決策的分類器 給定一個n類（c1,c2,cn)，用一個特征向量x表示未知樣本，生成n個條件概率P(ci|x),也稱為后驗概率，則根據貝葉斯定理有先驗概率P(ci) P(ci)代表還沒有訓練數據前，ci擁有的初始概率。P

20、(ci)常被稱為ci的先驗概率(prior probability) ，它反映了我們所擁有的關于ci是正確分類機會的背景知識,它應該是獨立于樣本的。 如果沒有這一先驗知識，那么可以簡單地將每一候選類別賦予相同的先驗概率。不過通常我們可以用樣例中屬于ci的樣例數|ci|比上總樣例數|D|來近似，即3.3 基于貝葉斯決策的分類器似然函數P(x|cj)（likehood)似然函數是指當已知類別為ci的條件下，看到樣本x(特征向量）出現的概率。 若設x = 則P(x|ci)= P(a1,a2am| ci)3.3 基于貝葉斯決策的分類器后驗概率P(ci |x) 即給定數據樣本x時ci成立的概率,而這正是

21、我們所感興趣的。 P(ci|x )被稱為ci的后驗概率（posterior probability），因為它反映了在看到數據樣本x后cj成立的置信度 對于一個決策判斷，我們取后驗概率為最大的作為正確的分類，即：3.3 基于貝葉斯決策的分類器假設在某地區切片細胞中正常（c1）和異常（c2）兩類的先驗概率分別為p(c1)=0.9, p(c2)=0.1。現有一待識別細胞呈現出狀態 x(測量值），由其類條件概率密度分布曲線查的p(x|c1)=0.2, p(x|c2)=0.4,試對細胞x進行分類。3.3 基于貝葉斯決策的分類器一個基于貝葉斯決策的實例 利用貝葉斯公式，分別計算出狀態為x時c1與c2的后驗

22、概率3.3 基于貝葉斯決策的分類器后驗概率由下式決定而上式分母是x的概率，由全概率公式有正常細胞C1的后驗概率為：異常細胞C2的后驗概率為：由于c1的后驗概率C2的后驗概率：3.4 貝葉斯學習算法簡介貝葉斯學習算法與機器學習相關的兩個原因：貝葉斯學習算法能夠計算顯示的假設概率，比如樸素貝葉斯分類貝葉斯方法為理解多數學習算法提供了一種有效的手段，而這些算法不一定直接操縱概率數據，比如Find-S候選消除算法神經網絡學習：選擇使誤差平方和最小化的神經網絡推導出另一種誤差函數：交叉熵分析了決策樹的歸納偏置考察了最小描述長度原則貝葉斯學習方法的特性觀察到的每個訓練樣例可以增量地降低或升高某假設的估計概

23、率。而其他算法會在某個假設與任一樣例不一致時完全去掉該假設先驗知識可以與觀察數據一起決定假設的最終概率，先驗知識的形式是：1）每個候選假設的先驗概率；2）每個可能假設在可觀察數據上的概率分布貝葉斯方法可允許假設做出不確定性的預測新的實例分類可由多個假設一起做出預測，用它們的概率來加權即使在貝葉斯方法計算復雜度較高時，它們仍可作為一個最優的決策標準衡量其他方法貝葉斯方法的難度難度之一：需要概率的初始知識，當概率預先未知時，可以基于背景知識、預先準備好的數據以及基準分布的假定來估計這些概率難度之二：一般情況下，確定貝葉斯最優假設的計算代價比較大（在某些特定情形下，這種計算代價可以大大降低）。貝葉斯

24、法則機器學習的任務：在給定訓練數據D時，確定假設空間（hypotheses）H=h1,h2,中的最佳假設。最佳假設：一種方法是把它定義為在給定數據D以及H中不同假設的先驗概率的有關知識下的最可能假設。貝葉斯理論提供了一種計算假設概率的方法，基于假設的先驗概率、給定假設下觀察到不同數據的概率以及觀察到的數據本身。先驗概率和后驗概率用P(h)表示在沒有訓練數據前假設h擁有的初始概率。P(h)被稱為h的先驗概率。先驗概率反映了關于h是一正確假設的機會的背景知識如果沒有這一先驗知識，可以簡單地將每一候選假設賦予相同的先驗概率類似地，P(D)表示訓練數據D的先驗概率，P(D|h)表示假設h成立時D的概率

25、機器學習中，我們關心的是P(h|D)，即給定D時h的成立的概率，稱為h的后驗概率貝葉斯公式貝葉斯公式提供了從先驗概率P(h)、P(D)和P(D|h)計算后驗概率P(h|D)的方法P(h|D)隨著P(h)和P(D|h)的增長而增長，隨著P(D)的增長而減少，即如果D獨立于h時被觀察到的可能性越大，那么D對h的支持度越小極大后驗假設學習器在候選假設集合H中尋找給定數據D時可能性最大的假設h，h被稱為極大后驗假設（MAP）確定MAP的方法是用貝葉斯公式計算每個候選假設的后驗概率，計算式如下最后一步，去掉了P(D)，因為它是不依賴于h的常量極大似然假設在某些情況下，可假定H中每個假設有相同的先驗概率，

26、這樣式子可以進一步簡化，只需考慮P(D|h)來尋找極大可能假設。P(D|h)常被稱為給定h時數據D的似然度，而使P(D|h)最大的假設被稱為極大似然假設假設空間H可擴展為任意的互斥命題集合，只要這些命題的概率之和為1實例：一個醫療診斷問題（1）有兩個可選的假設：h1=病人有癌癥、h2=病人無癌癥，假設H=h1,h2可用數據D 來自化驗結果：d1為正+和d2為負-, D=d1,d2有先驗知識：在所有人口中，患病率是P(h1)=0.008，則無病率P(h2)=0.992對確實有病的患者的化驗準確率為98%，對確實無病的患者的化驗準確率為97%總結如下P(h1)=0.008, P(h2)=0.992

27、P(d1|h1)=0.98, P(d2|h1)=0.02P(d1|h2)=0.03, P(d2|h2)=0.97問題：假定有一個新病人，化驗結果為正，是否應將病人斷定為有癌癥？求后驗概率P(h1|d1)和P(h2|d1)利用貝葉斯后驗概率公式計算后驗假設概率：hMAP=h2(無癌癥） 取最大后驗概率有：P(h1|d1) =P(d1|h1)P(h1)=0.98*0.008=0.00784P(h2|d1)=P(d1|h2)P(h2)=0.03*0.992=0.02976實例：一個醫療診斷問題（2）舉例：一個醫療診斷問題（2） 貝葉斯推理的結果很大程度上依賴于先驗概率，另外不是完全接受或拒絕假設，只

28、是在觀察到較多的數據后增大或減小了假設的可能性。確切的后驗概率可將上面的結果除以P(d1)得到，對于無癌癥的假設h2有貝葉斯法則和概念學習貝葉斯法則為計算給定訓練數據下任一假設的后驗概率提供了原則性方法，因此可以直接將其作為一個基本的學習方法：計算每個假設的概率，再輸出其中概率最大的。這個方法稱為Brute-Force貝葉斯概念學習算法。將上面方法與概念學習算法比較，可以看到：在特定條件下，它們學習得到相同的假設，不同的是概念學習方法不明確計算概率，而且效率更高。Brute-Force貝葉斯概念學習概念學習問題：有限假設空間H定義在實例空間X上，任務是學習某個目標概念c（concept)。Br

29、ute-Force MAP學習算法對于H中每個假設h，計算后驗概率輸出有最高后驗概率的假設上面算法需要較大計算量，因為它要計算每個假設的后驗概率，對于大的假設空間顯得不切實際，但是它提供了一個標準以判斷其他概念學習算法的性能。特定情況下的MAP假設假定樣例集X=x1,x2,訓練數據D=d1,d2,dn是無噪聲的，即di=c(xi)目標概念c包含在假設空間H中每個假設的概率相同求得由于所有假設的概率之和是1，因此由于訓練數據無噪聲，那么給定假設h時，與h一致的D的概率為1，不一致的概率為0，因此|H|表示假設的個數特定情況下的MAP假設（2）考慮Brute-Force MAP算法的第一步h與D不

30、一致，h與D一致，VSH,D是關于D的變型空間（Version Space）（即與訓練集D一致的假設集）|VSH,D|是H中與D一致假設的數量。特定情況下的MAP假設（3）P(D)的推導P(D)假設的概率演化情況如圖所示，初始時所有假設具有相同的概率，當訓練數據逐步出現后，不一致假設的概率變為0，而整個概率的和為1，它們均勻分布到剩余的一致假設中。每個一致的假設都是MAP假設。特定情況下的MAP假設（3）假設hP(h)a)每個假設賦予均勻的先驗概率假設hP(h|D1)b)訓練數據增長到D1假設hP(h|D1,D2)c)訓練數據增長到D1,D2極大似然和最小誤差平方假設前面分析表明：某些學習算法

31、即使沒有顯示地使用貝葉斯規則，或以某種形式計算概率，但它們輸出的結果符合貝葉斯原理，是一個MAP假設。通過簡單的貝葉斯分析，可以表明在特定前提下，任一學習算法如果使輸出的假設預測和訓練數據之間的誤差平方和最小化，它將輸出一極大似然假設。上面結論的意義是，對于許多神經網絡和曲線擬合的方法，如果它們試圖在訓練數據上使誤差平方和最小化，此結論提供了基于貝葉斯的理論依據。極大似然和最小誤差平方假設（2）問題框架：學習器L工作在實例空間X和假設空間H上，H中的假設為X上定義的某種實數值函數。L面臨的問題是學習一個從H中抽取出的未知目標函數f，給定m個訓練樣例的集合，每個樣例的目標值被某隨機噪聲干擾，此隨

32、機噪聲服從正態分布更精確地講，每個訓練樣例是序偶，di=f(xi)+ei，ei是代表噪聲的隨機變量，假定ei的值是獨立抽取的，并且它們的分布服從0均值的正態分布學習器的任務是在所有假設有相等的先驗概率前提下，輸出極大似然假設（即MAP假設）極大似然和最小誤差平方假設（3）用一個簡單情況，即線性函數來說明問題。如圖所示，實線表示線性目標函數f，實點表示有噪聲的訓練樣例集，虛線對應有最小平方訓練誤差的假設hML，即極大似然假設。對于e這樣的連續變量上的概率，使用概率密度表示概率分布，它在所有值上的積分為1，用小寫的p表示。有限概率P有時又稱為概率質量概率密度函數：exy學習某實值函數目標函數 f

33、對應實線，訓練樣例為真實目標+噪聲ei,虛線是使誤差平方之和最小的線性函數。di = f (xi)+ ei極大似然和最小誤差平方假設（3）極大似然和最小誤差平方假設（4）假定有一固定的訓練實例集合，因此只考慮相應的目標值序列D=，這里di=f(xi)+ei。假定訓練樣例是相互獨立的，給定h時，可將P(D|h)寫成各p(di|h)的積如果誤差ei服從0均值和未知方差2的正態分布，那么每個di服從均值為f(xi)，方差不變的正態分布。因此，p(di|h)可寫為方差2、均值f(xi)的正態分布使用正態分布公式并將相應的參數代入，由于概率di的表達式是在h為目標函數f的正確描述條件下的，所以替換=f(

34、xi)=h(xi)極大似然和最小誤差平方假設（5） 上式說明了極大似然假設等價于使訓練值和假設預測值之間的誤差的平方和最小的那個假設。 這個結論的前提是：訓練值等于真實目標值加上隨機噪聲，其中隨機噪聲從一個均值為0的正態分布中獨立抽取。采用正態分布的合理性數學計算的簡潔性對許多物理系統的噪聲都有良好的近似中心極限定律顯示，足夠多的獨立同分布隨機變量的和服從正態分布由許多獨立同分布的因素的和所生成的噪聲將成為正態分布（當然，現實中不同的分量對噪聲的貢獻也許不是同分布的）使誤差平方最小化的方法經常被用于神經網絡、曲線擬合及其他許多實函數逼近的算法中上面的分析只考慮了訓練樣例的目標值中的噪聲，而沒有

35、考慮實例屬性值的噪聲貝葉斯最優分類器（1）前面我們討論的問題是：給定訓練數據，最可能的假設是什么？另一個相關的更有意義的問題是：給定訓練數據，對新實例的最可能的分類是什么？顯然，第二個問題的解決可以將第一個問題的結果（MAP）應用到新實例上得到，還存在更好的算法貝葉斯最優分類器（2）例子考慮一個包含三個假設h1, h2, h3的假設空間。假定已知訓練數據時三個假設的后驗概率分別是P(h1|D)=0.4, P(h2|D)=0.3, P(h3|D)=0.3，因此h1為MAP假設。若一新實例x被h1分類為正，被h2和h3分類為反計算所有假設，x為正例的概率為0.4，為反例的概率為0.6因此，這時最可

36、能的分類與MAP假設生成的分類不同貝葉斯最優分類器（3）一般而言，新實例的最可能分類可通過合并所有假設的預測得到，用后驗概率來加權。如果新實例的可能分類可取某集合V中的任一值vj，那么概率P(vj|D)表示新實例分類為vj的概率新實例的最優分類為使P(vj|D)最大的vj值，貝葉斯最優分類器為：貝葉斯最優分類器（4）例子已知：新實例的可能分類集合為V=+, -P(h1|D)=0.4, P(-|h1)=0, P(+|h1)=1P(h2|D)=0.3, P(-|h2)=1, P(+|h2)=0P(h3|D)=0.3, P(-|h3)=1, P(+|h2)=0因此： 貝葉斯最優分類器（5）貝葉斯最優

37、分類器在給定可用數據、假設空間及這些假設的先驗概率下使新實例被正確分類的可能性達到最大貝葉斯最優分類器的一個屬性：它所做的分類可以對應于H中不存在的假設使用前面式子來分類X中的每個實例，按此定義的實例標注不一定對應于H中的任一單個假設h對實例的標注將貝葉斯分類器看成是不同于假設空間H的另一空間H，在其上應用貝葉斯公式。H有效地包含了一組假設，它能在H中多個假設的線性組合所作的預言中進行比較Gibbs算法貝葉斯最優分類器能從給定訓練數據中獲得最好的性能，但算法的開銷很大一個替代的、非最優的方法是Gibbs算法，定義如下：按照H上的后驗概率分布，從H中隨機選擇假設h使用h來預言下一個實例x的分類在

38、一定條件下，Gibbs算法的誤分類率的期望值最多為貝葉斯最優分類器的兩倍。確切地講，期望值是在隨機抽取的目標概念上作出的，抽取過程按照學習器假定的先驗概率對概念學習問題的一個啟示：如果學習器假定H上有均勻的先驗概率，而且如果目標概念實際上也按該分布抽取，那么當前變型空間中隨機抽取的假設對下一實例分類的期望誤差最多為貝葉斯分類器的兩倍。樸素貝葉斯分類器 樸素貝葉斯分類器（Nave Bayes Classifier)是貝葉斯學習方法中實用性很高的一種分類器，其核心思想是假設樣本的每個特征與其他特征都不相關。盡管這些特征有時相互依賴或者有些特征由其他特征決定，然而樸素貝葉斯分類器認為這些屬性在概率分

39、布上獨立的。樸素貝葉斯分類器在有監督學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中，樸素貝葉斯分類器對很多復雜的現實情形中仍能夠取得相當好的效果。樸素貝葉斯分類器應用的學習任務：每個實例x可由屬性值的合取描述，而目標函數f(x)從某有限集合V中取值貝葉斯方法的新實例分類目標是在給定描述實例的屬性值下，得到最可能的目標值vMAP使用貝葉斯公式變化上式樸素貝葉斯分類器（2）基于訓練數據估計式子中的兩個數據項的值估計P(vj)很容易：計算每個目標值vj出現在訓練數據中的頻率估計P(a1,.an|vj)遇到數據稀疏問題，除非有一個非常大的訓練數據集，否則無法獲得可靠的估計樸素貝葉斯分類器引入

40、一個簡單的假定避免數據稀疏問題：在給定目標值時，屬性值之間相互條件獨立，即樸素貝葉斯分類器（3）樸素貝葉斯分類器的定義：從訓練數據中估計不同P(ai|vj)項的數量比要估計P(a1,.,an|vj)項所需的量小得多只要條件獨立性得到滿足，樸素貝葉斯分類vNB等于MAP分類，否則是近似樸素貝葉斯分類器與其他已介紹的學習方法的一個區別：沒有明確地搜索可能假設空間的過程（假設的形成不需要搜索，只是簡單地計算訓練樣例中不同數據組合的出現頻率）DayOutlookTemperatureHumiditywindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStro

41、ngNoD3OvercastHotHighweakYesD4RainMildHighweakYesD5RainCoolNormalweakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYes考慮周六上午是否適合玩網球的概念學習，設天氣有4個屬性Di=Outlook，Temperature， Humidity，wind目標概念PlayTennis的訓練樣例集D=D1,D2,D14樸素貝葉斯分類器-實例DayOutlookTemperatureHumiditywindPlayTennisD8SunnyMildHighWeakNoD9Sun

42、nyCoolNormalWeakYesD10RainMildNormalweakYesD11SunnyMildNormalStrongYesD12OvercastRainHighStrongYesD13OvercastHotNormalweakYesD14RainMildHighStrongNo目標概念PlayTennis的訓練樣例（續）樸素貝葉斯分類器-實例樸素貝葉斯分類器（4）問題：根據表中提供的目標概念PlayTennis的14個訓練樣例，給新實例D15=，請分類D15屬于: PlayTennis=Yes 或 PlayTennis=No 按樸素貝葉斯公式: 這里類別V=Yes, No=樸

43、素貝葉斯分類器（4）根據上表可以計算出上式需要的概率值P(v1)=P(yes)=9/14=0.64P(v2)=P(no)=5/14=0.36P(a1|v1)=P(Sunny|yes) =2/9=0.22P(a1|v2)=P(Sunny|no) =3/5=0.60P(a2|v1)=P(Cool|yes) =3/9=0.33P(a2|v2)=P(Cool|no) =1/5=0.20P(a3|v1)=P(High|yes) =3/9=0.33P(a3|v2)=P(High|no) =4/5=0.80P(a4|v1)=P(strong|yes) =3/9=0.33P(a4|v2)=P(strong|n

44、o) =3/5=0.60樸素貝葉斯分類器（4）求vNBP(v1|D15)=P(Yes|Sunny,Cool,High,Strong) =P(Yes)P(Sunny|yes)P(Cool|yes)P(High|yes)P(Strong|yes) =0.64*0.22*0.33*0.33*0.33 =0.0051P(v2|D15)=P(No|Sunny,Cool,High,Strong) =P(No)P(sunny|no)P(cool|no)P(high|no)P(strong|no) = 0.36*0.60*0.20*0.80*0.60 =0.0207樸素貝葉斯分類器-概率估算估計概率前面通過在

45、全部事件基礎上觀察某事件出現的比例來估計概率，即P估計=nc/n當樣本很小時，采用平滑技術，m-估計p是將要確定的概率的先驗估計，而m是一稱為等效樣本大小的常量在缺少其他信息時，選擇p的一種典型的方法是均勻概率，比如某屬性有k個可能值，那么p=1/km被稱為等效樣本大小的原因是：P估計式子可被解釋為將n個實際的觀察擴大，加上m個按p分布的虛擬樣本樸素貝葉斯分類器學習分類文本利用樸素貝葉斯分類器可以進行文本自動過濾，比如我感興趣的電子新聞稿討論機器學習的萬維網頁這里描述一個基于樸素貝葉斯分類器的文本分類的通用算法，它是目前所知的文本分類的最有效方法之一問題框架：實例空間X包含了所有的文本文檔，給

46、定某未知目標函數f (x)的一組訓練樣例，f(x)的值來自某有限集合V（作為示例，此處令V=like, dislike）舉例：學習分類文本（2）應用樸素貝葉斯分類器的兩個主要設計問題：怎樣將任意文檔表示為屬性值的形式如何估計樸素貝葉斯分類器所需的概率表示文檔的方法給定一個文本文檔，對每個單詞的位置定義一個屬性，該屬性的值為在此位置上找到的英文單詞假定我們共有1000個訓練文檔，其中700個分類為dislike，300個分類為like，現在要對下面的新文檔進行分類：This is an example document for the naive Bayes classifier. This d

47、ocument contains only one paragraph, or two sentences.舉例：學習分類文本（3） 注意此處貝葉斯分類器隱含的獨立性假設并不成立。通常，某個位置上出現某個單詞的概率與前后位置上出現的單詞是相關的 雖然此處獨立性假設不精確，但別無選擇，否則要計算的概率項極為龐大。 另外實踐中，樸素貝葉斯學習器在許多文本分類問題中性能非常好。按樸素貝葉斯計算式有舉例：學習分類文本（4）需要估計概率項P(vj)和P(ai=wk|vj)。前一項可基于每一類在訓練數據中的比例很容易得到，P（like) =0.3, P(dislike)=0.7,后一項的概率計算量相當大，

48、假如有20000單詞，則有2（兩類）19（位置屬性） 20000=96萬！再引入一個假定以減少需要估計的概率項的數量：假定單詞wk出現的概率獨立于單詞所在的位置，即P(ai=wk|vj)=P(wk|vj)作此假定的一個主要優點在于：使可用于估計每個所需概率的樣例數增加了，因此增加了估計的可靠程度舉例：學習分類文本（4）采納m-估計方法，即有統一的先驗概率并且m等于詞匯表的大小，因此詞匯表單詞總數n為不同單詞位置的總數假設統一的先驗概率故有：所以 m*p=1Wk出現在文本中的次數用于學習和分類文本的樸素貝葉斯算法Learn_Naive_Bayes_Text( Examples, V )Examp

49、les為一組文本文檔以及它們的目標值。V為所有可能目標值的集合。此函數作用是學習概率項P(wk|vj)和P(vj)。收集Examples中所有的單詞、標點符號以及其他記號Vocabulary在Examples中任意文本文檔中出現的所有單詞及記號的集合計算所需要的概率項P(vj)和P(wk|vj)對V中每個目標值vjdocsjExamples中目標值為vj的文檔子集P(vj)|docsj| / |Examples|Textj將docsj中所有成員連接起來建立的單個文檔n在Textj中不同單詞位置的總數對Vocabulary中每個單詞wknk單詞wk出現在Textj中的次數P(wk|vj)(nk+

50、1) / (n+|Vocabulary|)用于學習和分類文本的樸素貝葉斯算法（2）Classify_Naive_Bayes_Text( Doc )對文檔Doc返回其估計的目標值，ai代表在Doc中的第i個位置上出現的單詞positions在Doc中的所有單詞位置，它包含能在Vocabulary中找到的記號返回vNB，利用前面學習獲得的P(wk|vj),代入上式得實驗結果Joachims將此算法用于新聞組文章的分類每一篇文章的分類是該文章所屬的新聞組名稱20個新聞組，每個新聞組有1000篇文章，共2萬個文檔2/3作為訓練樣例，1/3進行性能測量詞匯表不包含最常用詞（比如the、of）和罕見詞（數

51、據集中出現次數少于3）Lang用此算法學習目標概念“我感興趣的新聞組文章”NewsWeeder系統，讓用戶閱讀新聞組文章并為其評分，然后使用這些評分的文章作為訓練樣例，來預測后續文章哪些是用戶感興趣的每天向用戶展示前10%的自動評分文章，它建立的文章序列中包含的用戶感興趣的文章比通常高34倍貝葉斯信念網樸素貝葉斯分類器假定各個屬性取值在給定目標值v下是條件獨立的，從而化簡了最優貝葉斯分類的計算復雜度。但在多數情況下，這一條件獨立假定過于嚴厲了。貝葉斯信念網描述的是一組變量所遵從的概率分布，它通過一組條件概率來指定一組條件獨立性假設貝葉斯信念網中可表述變量的一個子集上的條件獨立性假定，因此，貝葉

52、斯信念網提供了一種中間的方法，它比樸素貝葉斯分類器的限制更少，又比在所有變量中計算條件依賴更可行。貝葉斯信念網（2）貝葉斯信念網描述了一組變量上的概率分布考慮一任意的隨機變量集合Y1.Yn，其中每個Yi可取的值集合為V(Yi)變量集合Y的聯合空間為叉乘V(Y1). V(Yn)在此聯合空間上的概率分布稱為聯合概率分布，聯合概率分布指定了元組的每個可能的變量約束的概率貝葉斯信念網則對一組變量描述了聯合概率分布條件獨立性精確定義條件獨立性令X, Y和Z為3個離散值隨機變量，當給定Z值時X服從的概率分布獨立于Y的值，稱X在給定Z時條件獨立于Y，即上式通常簡寫成P(X|Y,Z)=P(X|Z)擴展到變量集

53、合下面等式成立時，稱變量集合X1.Xl在給定變量集合Z1.Zn時條件獨立于變量集合Y1.Ym條件獨立性與樸素貝葉斯分類器的之間的關系貝葉斯信念網的表示貝葉斯信念網（簡稱貝葉斯網）表示一組變量的聯合概率分布一般地說，貝葉斯網表示聯合概率分布的方法是指定一組條件獨立性假定（有向無環圖）以及一組局部條件概率集合如下圖示，聯合空間中每個變量在貝葉斯網中表示為一個節點，每個變量需要兩種類型的信息網絡弧表示斷言“此變量在給定其直接前驅時條件獨立于其非后繼”每個變量有一個條件概率表，描述了該變量在給定其立即前驅（父節點）時的概率分布StormBusTourGroupLightingCampfireThund

54、erForestFireS,BS,BS,BS,BC0.2C0.8Campfire由事件S-Storm 、 B-BusTourGroup、 L-Lighting、 C-Campfire 、T-Thunder、 F-ForestFire組成的貝葉斯網，其中C的父節點為S、B，條件概率CPT表如下貝葉斯信念網的表示貝葉斯信念網的表示實例命題S- Smoker吸煙者命題CCoal Miner 是煤礦工人命題LLung Cancer 他患肺癌命題EEmphysema 他患肺氣腫SLEC節點代表一個證據有向弧代表一個規則假設表達了節點間的因果關系弧的起點父節點Parent 如S是L、E的父節點弧的終點后代節點 E是 S、C的后代節點 用一個無環DAG有向圖來表示因果關系網貝葉斯信念網的表示貝葉斯網絡就是在因果關系網上加入連接強度的因果關系。ABC如果A是B的父節點，通過概率因果關系，很顯然P(B|A)就是連接強度，即由A推出B的可能性有多大。如果B不止一個父節點，如還有父節點C，則對B的推演應該用聯合概率P（B|AC）來描述。P（B|A)P（B|C)就是在因果關系網上加入連接強度的因果關系。貝葉斯信念網的表示所有指定的概率和無環圖構成一個貝葉斯網