人工智能機器學習課件

第六章機器學習概述幾種機器學習第一頁，共100頁。第一頁，共100頁。第六章機器學習概述幾種機器學習第二頁，共100頁。第二頁，共100頁。機器學習—概述參考書本書展示了機器學習中的核心算法和理論，并闡明了算法的過行過程。書中主要涵蓋了目前機器學習中各種最實用的理論和算法，包括概念學習、決策樹、神經網絡、貝葉斯學習、基于實例的學習、遺傳算法、規則學習、基于解釋的學習和增強學習等。對每一個主題，作者不僅進行了十分詳盡和直觀的解釋，還給出了實用的算法流程。本書被卡內基梅隆等許多大學作為機器學習課程的教材。第三頁，共100頁。第三頁，共100頁。機器學習—概述什么是機器學習？Simon（1983）：學習就是系統中的變化，這種變化使系統比以前更有效地去做同樣的工作。Minsky(1985)：學習是在我們頭腦中（心里內部）進行有用的變化。學習是一種具有多側面的現象。學習的過程有：獲取新的陳述性知識、通過教育或實踐發展機械技能和認知能力、將新知識組織成為通用化和有效的表達形式、借助觀察和實驗發現新的事實和新的理論。第四頁，共100頁。第四頁，共100頁。機器學習—概述基本形式：知識獲取和技能求精知識獲?。簩W習的本質就是獲取新的知識。包括物理系統和行為的描述和建模，構造客觀現實的表示?！R獲取通過實踐逐漸改造機制和認知技能。例：騎自行車。這些技能包括意識的或機制的協調。這種改進又是通過反復實踐和從失敗的行為中糾正偏差來進行的?！寄芮缶谖屙?，共100頁。第五頁，共100頁。機器學習—概述基本形式知識獲取的本質可能是一個自覺的過程，其結果是產生新的符號知識結構和智力模型。而技能求精則是下意識地借助于反復地實踐來實現的。本章只涉及學習的知識獲取問題。第六頁，共100頁。第六頁，共100頁。機器學習—概述為什么要研究機器學習？人工智能主要是為了研究人的智能，模仿其機理將其應用于工程的科學。在這個過程中必然會問道：“人類怎樣做才能獲取這種特殊技能（或知識）？”。.......….第七頁，共100頁。第七頁，共100頁。機器學習—概述為什么要研究機器學習？

.......….當前人工智能研究的主要障礙和發展方向之一就是機器學習。包括學習的計算理論和構造學習系統?，F在的人工智能系統還完全沒有或僅有很有限的學習能力。系統中的知識由人工編程送入系統，知識中的錯誤也不能自動改正。也就是說，現有的大多數人工智能是演繹的、沒有歸納推理，因而不能自動獲取和生成知識。.......….第八頁，共100頁。第八頁，共100頁。機器學習—概述為什么要研究機器學習？

………..未來的計算機將有自動獲取知識的能力，它們直接由書本學習，通過與人談話學習，通過觀察學習。它們通過實踐自我完善，克服人的存儲少、效率低、注意力分散、難以傳送所獲取得知識等局限性。一臺計算機獲取的知識很容易復制給任何其它機器。第九頁，共100頁。第九頁，共100頁。機器學習—概述實現的困難：

預測難：學習后知識庫發生了什么變化，系統功能的變化的預測。

歸納推理：現有的歸納推理只保證假，不保證真。演繹推理保真。而且，歸納的結論是無限多的，其中相當多是假的，給生成的知識帶來不可靠性。

機器目前很難觀察什么重要、什么有意義。第十頁，共100頁。第十頁，共100頁。機器學習—

概述機器學習模型學習是建立理論、形成假設和進行歸納推理的過程。整個過程包括：信息的存儲、知識的處理兩部分環境學習環節知識庫

執行環節對環境所提供的信息進行處理，以便改善知識庫中的顯式知識。第十一頁，共100頁。第十一頁，共100頁。機器學習—概述發展歷史神經系統模型和決策理論的研究50年代開始。其特點是對開始與無初始結構和面向作業知識的通用學習系統感興趣。包括構造多種具有隨機或部分隨機的初始結構的基于神經模型的機器。這些系統一般稱為神經網絡或自組織系統。由于當時計算機技術狀態，多停留在理論和硬件上。這些元件類似于神經元，他們實現簡單的邏輯功能?！谑?，共100頁。第十二頁，共100頁。機器學習—概述發展歷史

神經系統模型和決策理論的研究………1965年左右，神經網絡經驗模式導致了模式識別這一新學科以及機器學習的決策理論方法。這種方法中學習就是從給定的一組經過選擇的例子中獲得判斷函數，有線性的、多項式的、或相關的形式。當時，Samuel(1059-1963)的跳棋程序是最著名的成功的學習系統之一。達到了跳棋大師的水平。第十三頁，共100頁。第十三頁，共100頁。機器學習—概述符號概念獲取的研究60年代中期提出的基于符號表示的概念學習系統研究。這類學習過程通過分析一些概念的正例和反例構造出這些概念的符號表示。表示的形式一般是邏輯表達式、決策樹、產生式規則或語義網絡。代表有Winston的ARCH。第十四頁，共100頁。第十四頁，共100頁。機器學習—概述基于知識的學習系統的研究70年代中期注重基于知識的學習系統研究。人們不再局限于構造概念學習系統和獲取上下文知識，同時也結合了問題求解中的學習、概念聚類、類比推理及機器發現的工作。一些成熟的方法開始用于輔助構造專家系統，并不斷地開發新的學習方法，使機器學習達到一個新的時期。這時期的工作特點主要有三個方面：第十五頁，共100頁。第十五頁，共100頁。機器學習—概述基于知識的學習系統的研究基于知識的方法：著重強調應用面向任務的知識和指導學習過程的約束。從早先的無知識學習系統的失敗中吸取的教訓就是：為獲取新的知識，系統必須事先具備大量的初始知識。開發各種各樣的學習方法，除了早先從例子中學習外，各種有關的學習策略相繼出現，如示教學習,觀察和發現學習。同時也出現了如類比學習和基于解釋的學習等方法。

結合生成和選擇學習任務的能力：應用啟發式知識于學習任務的生成和選擇，包括提出收集數據的方式、選擇要獲取的概念與控制系統的注意力等。

第十六頁，共100頁。第十六頁，共100頁。機器學習—概述聯接學習和符號學習的深入研究

第四時期開始于八十年代后期，聯接學習和符號學習的深入研究導致機器學習領域的極大繁榮。首先，神經網絡的研究重新迅速崛起，并在聲音識別、圖象處理等諸多領域得到很大成功。從事研究的學者，發現了用隱含層神經元來計算和學習非線性函數的方法，克服了早期神經元模型的局限性。計算機硬件技術的高速發展也為開發大規模和高性能的人工神經網絡掃清了障礙，使得基于人工神經網絡的聯接學習從低谷走出，發展迅猛，并向傳統的基于符號的學習提出了挑戰。第十七頁，共100頁。第十七頁，共100頁。機器學習—概述聯接學習和符號學習的深入研究

同時，符號學習已經歷了三十多年的發展歷程，各種方法日臻完善，出現了應用技術蓬勃發展的景象。最突出的成就有分析學習（特別是解釋學習）的發展,遺傳算法的成功和加強學習方法的廣泛應用。特別是近幾年來，隨著計算機網絡的發展，基于計算機網絡的各種自適應、具有學習功能的軟件系統的研制和開發都將機器學習的研究推向新的高度，網絡環境已成為人工智能和機器學習的重要試驗床。第十八頁，共100頁。第十八頁，共100頁。機器學習—概述機器學習進入新階段的重要表現：（近十年）

機器學習已成為新的邊緣科學并在高校形成一門課程。它綜合應用心理學、生物學和神經生理學以及數學、自動化和計算機科學形成機器學習理論基礎。第十九頁，共100頁。第十九頁，共100頁。機器學習—概述機器學習進入新階段的重要表現：（近十年）結合各種學習方法，取長補短的多種形式的集成學習系統的研究正在興起。特別是連接學習，符號學習的耦合可以更好地解決連續性信號處理中知識與技能的獲取與求精問題而受到重視。第二十頁，共100頁。第二十頁，共100頁。機器學習—概述機器學習進入新階段的重要表現：（近十年）機器學習與人工智能各種基礎問題的統一性觀點正在形成。例如：學習與問題求解結合進行，知識表達便于學習的觀點產生了通用智能系統SOAR的組塊學習。類比學習與問題求解結合的基于案例學習已成為經驗學習的重要方向。

第二十一頁，共100頁。第二十一頁，共100頁。機器學習—概述機器學習進入新階段的重要表現：（近十年）各種學習方法的應用范圍不斷擴大，一部分已形成商品。歸納學習的知識獲取工具已在診斷分類性專家系統中廣泛應用。連接學習在聲圖文識別中占優勢。分析學習用于設計綜合性專家系統。遺傳算法與強化學習在工程控制中有較好的應用前景。與符號系統耦合的神經網絡連接學習將在企業的智能管理與智能機器人運動規劃中發揮作用。第二十二頁，共100頁。第二十二頁，共100頁。機器學習—概述機器學習進入新階段的重要表現：（近十年）與機器學習有關的學術活動空前活躍。國際上除每年一次的機器學習研究會外，還有計算機學習理論會議及遺傳算法會議。

第二十三頁，共100頁。第二十三頁，共100頁。機器學習—

概述分類（由低到高）通過歸納總結學習（自學習）通過書本資料學習（獨立研究）通過實際事例學習（啟發式學習）通過提問學習（注入式學習）通過機械記憶學習（死記硬背式）高

低第二十四頁，共100頁。第二十四頁，共100頁。機器學習—

概述分類：(按學習策略分類)機械式學習和直接輸入新知識（記憶學習） 學習者不需要進行任何推理或知識轉換，將知識直接裝進機器中。根據示教學習（傳授學習、指點學習） 從老師或其它有結構的事物獲取知識。要求學習者將輸入語言的知識轉換成它本身的內部表示形式。并把新的信息和它原有的知識有機地結合為一體。第二十五頁，共100頁。第二十五頁，共100頁。機器學習—

概述通過類推學習（演繹學習） 學習者找出現有知識中所要產生的新概念或技能十分類似的部分。將它們轉換或擴大成適合新情況的形式，從而取得新的事實或技能。從例子中學習（歸納學習） 給學習者提供某一概念的一組正例和反例，學習者歸納出一個總的概念描述，是它適合于所有的正例且排除所有的反例。（目前研究較多的一種方法）第二十六頁，共100頁。第二十六頁，共100頁。機器學習—

概述類比學習 演繹學習與歸納學習的組合。匹配不同論域的描述、確定公共的結構。以此作為類比映射的基礎。尋找公共子結構是歸納推理，而實現類比映射是演繹推理?；诮忉尩膶W習

學生根據教師提供的目標概念、該概念的一個例子、領域理論及可操作準則，首先構造一個解釋來說明為什么該例子滿足目標概念，然后將解釋推廣為目標概念的一個滿足可操作準則的充分條件。第二十七頁，共100頁。第二十七頁，共100頁。機器學習—

概述分類：(按綜合分類)機器學習近幾年來發展很快，無論是符號學習還是聯接學習都派生出了許多分支和新的方法，研究領域不斷擴大，使得不少機器學習方法很難用加以歸類。綜合分類方式則在對機器學習方法進行分類時，綜合考慮各種學習方法出現的歷史淵源、知識表示、推理策略、結果評估的相似性、研究人員交流的相對集中性以及應用領域等諸因素。綜合分類方式將機器學習方法區分為以下六類：第二十八頁，共100頁。第二十八頁，共100頁。機器學習—

概述按綜合分類經驗性歸納學習(empiricalinductivelearning)。經驗性歸納學習采用一些數據密集的經驗方法（例如，版本空間法、ID3法，定律發現方法）對例子進行歸納學習。其例子和學習結果一般都采用屬性、謂詞、關系等符號表示。它相當于基于學習策略分類中的歸納學習，但扣除聯接學習、遺傳算法、加強學習的部分。第二十九頁，共100頁。第二十九頁，共100頁。機器學習—

概述按綜合分類經驗性歸納學習--決策樹構造法ID3。如果學習的任務是對一個大的例子集作分類概念的歸納定義，而這些例子又都是用一些無結構的屬性值對來表示，則可以采用示例學習方法的一個變種──決策樹學習，其代表性的算法是昆蘭（，1986）提出的ID3。第三十頁，共100頁。第三十頁，共100頁。機器學習—

概述按綜合分類決策樹構造法--ID3。ID3的輸入是描述各種已知類別實例的列表。例子由預先定義的屬性值對來表示。歸納推理產生的結果不是以往討論的那種合取表達式，而是一棵決策樹（也稱判別樹，并可轉而表示為決策規則的一個集合），用它可正確地區分所有給定例子的類屬。第三十一頁，共100頁。第三十一頁，共100頁。機器學習—

概述按綜合分類決策樹構造法--ID3。樹中的每一非葉節點對應一個需測試的屬性，每個分叉就是該屬性可能的取值；樹的葉節點則指示一個例子事物的類別。

ID3的顯著優點是歸納學習花費的時間和所給任務的困難度（取決于例子個數，用來描述對象的屬性數，所學習概念的復雜度即決策樹的節點數等）僅成線性增長關系。當然，ID3只能處理用屬性-值對表示的例子。第三十二頁，共100頁。第三十二頁，共100頁。機器學習—

概述按綜合分類分析學習（analyticlearning）。分析學習方法是從一個或少數幾個實例出發，運用領域知識進行分析。其主要特征為：

☆推理策略主要是演繹，而非歸納；

☆使用過去的問題求解經驗（實例）指導新的問題求解，或產生能更有效地運用領域知識的搜索控制規則。

分析學習的目標是改善系統的性能，而不是新的概念描述。分析學習包括應用解釋學習、演繹學習、多級結構組塊以及宏操作學習等技術。第三十三頁，共100頁。第三十三頁，共100頁。機器學習—

概述按綜合分類類比學習。它相當于基于學習策略分類中的類比學習。目前，在這一類型的學習中比較引人注目的研究是通過與過去經歷的具體事例作類比來學習，稱為基于范例的學習(case_basedlearning)，或簡稱范例學習。

基于范例的推理（Case-BasedRessoning,CBR）是指利用過去經歷的典型事例（稱為范例）求解或理解當前問題。第三十四頁，共100頁。第三十四頁，共100頁。機器學習—

概述按綜合分類基于范例的推理。這種推理形式在現實生活中非常常見。例如，有經驗的建筑設計師在設計新的建筑結構時，往往會回想起以往類似的例子。在烹飪、日?；顒影才偶捌渌S多方面都存在類似情況，即處理問題時不是從頭開始考慮各種細節及其關系，而是依據過去典型的事例，做適當調整以處理當前問題。因而基于范例推理又被稱為"即時推理"（instantreasoning），特別適合于知識缺乏或知識太復雜而經驗又相對豐富、穩定的領域。第三十五頁，共100頁。第三十五頁，共100頁。機器學習—

概述按綜合分類基于范例的推理是一種類比推理方式。與一般的類比推理相比,基于范例推理有以下兩個特點：

1)作為過去經驗的范例一般有比較固定的表示結構，通常用框架形式表示；

2)欲求解的問題與范例中的問題同屬于一個領域，且一般是同性質的，即是兩類同性質問題的類比。第三十六頁，共100頁。第三十六頁，共100頁。機器學習—

概述基于范例的推理不僅是一種有效的推理方法，也可用于建立一種很好的機器學習方法--基于范例的學習（CaseBasedLearning，CBL），其學習能力主要表現在：

1)通過記憶和調整老問題的解，使得新問題的求解不必從頭做起，因而推理更有效率。

2)通過記憶更多的正、反范例，使得系統的推理能力更強。

3)通過對范例庫中同類范例的歸納，可抽象出更一般、有用的結論。第三十七頁，共100頁。第三十七頁，共100頁。機器學習—

概述按綜合分類遺傳算法（geneticalgorithm,GA）。是一種基于進化論優勝劣汰、適者生存的物種遺傳思想的搜索算法。遺傳算法模擬生物繁殖的突變、交換和達爾文的自然選擇（在每一生態環境中適者生存）。它把問題可能的解編碼為一個向量，稱為個體，向量的每一個元素稱為基因，并利用目標函數（相應于自然選擇標準）對群體（個體的集合）中的每一個個體進行評價，根據評價值（適應度）對個體進行選擇、交換(基因重組)、變異(突變)等遺傳操作，從而得到新的群體。第三十八頁，共100頁。第三十八頁，共100頁。機器學習—

概述按綜合分類遺傳算法（geneticalgorithm,GA）。美國密執根大學的霍勒德（）于70年代初提出并創立了遺傳算法。在霍勒德的GA算法中采用二進制串來表示個體?？紤]到物種的進化或淘汰取決于它們在自然界中的適應程度，GA算法為每一個體計算一個適應值或評價值，以反映其好壞程度。第三十九頁，共100頁。第三十九頁，共100頁。機器學習—

概述按綜合分類遺傳算法（geneticalgorithm,GA）因而，個體的適應值越高，就有更大的可能生存和再生，即它的表示特征有更大的可能出現在下一代中。遺傳操作“交換”旨在通過交換兩個個體的子串來實現進化；遺傳操作“突變”則隨機地改變串中的某一（些）位的值，以期產生新的遺傳物質或再現已在進化過程中失去的遺傳物質?；衾盏绿岢龅倪z傳算法也稱為簡單遺傳算法（SGA），是一種基本的遺傳算法。第四十頁，共100頁。第四十頁，共100頁。機器學習—

概述按綜合分類簡單遺傳算法（simple

geneticalgorithm,SGA）

SGA以0、1組成的串表示問題域中待進化的個體（初始解）。利用遺傳操作──交換和突變，SGA從當前個體的集合──群體的各串中產生下一代群體。這一過程循環進行，直到滿足了結束條件（如循環了指定次，或群體性能不再改進）。SGA的處理過程如下：第四十一頁，共100頁。第四十一頁，共100頁。機器學習—

概述按綜合分類簡單遺傳算法（simple

geneticalgorithm,SGA）

begin

1.選擇適當表示，生成初始群體；

2.評估群體；

3.While未達到要求的目標do

begin

1.選擇作為下一代群體的各個體；

2.執行交換和突變操作；

3.評估群體；

end

end第四十二頁，共100頁。第四十二頁，共100頁。機器學習—

概述按綜合分類簡單遺傳算法（simple

geneticalgorithm,SGA）因此，對于一個SGA算法來說主要涉及以下內容：

·編碼和初始群體生成；

·群體的評價；

·個體的選擇；

·交換；

·突變；第四十三頁，共100頁。第四十三頁，共100頁。機器學習—

概述按綜合分類遺傳算法（geneticalgorithm）。遺傳算法適用于非常復雜和困難的環境，比如，帶有大量噪聲和無關數據、事物不斷更新、問題目標不能明顯和精確地定義，以及通過很長的執行過程才能確定當前行為的價值等。遺傳算法作為一種解決復雜問題的嶄新的有效優化方法，近年來得到了廣泛的實際應用，同時也滲透到人工智能、機器學習、模式識別、圖像處理、軟件技術等計算機學科領域。GA在機器學習領域中的一個典型應用就是利用GA技術作為規則發現方法應用于分類系統。第四十四頁，共100頁。第四十四頁，共100頁。機器學習—

概述按綜合分類聯接學習。典型的聯接模型實現為人工神經網絡，其由稱為神經元的一些簡單計算單元以及單元間的加權聯接組成。第四十五頁，共100頁。第四十五頁，共100頁。機器學習—

概述按綜合分類加強學習（reinforcementlearning）。加強學習的特點是通過與環境的試探性（trialanderror）交互來確定和優化動作的選擇，以實現所謂的序列決策任務。在這種任務中，學習機制通過選擇并執行動作，導致系統狀態的變化，并有可能得到某種強化信號（立即回報），從而實現與環境的交互。強化信號就是對系統行為的一種標量化的獎懲。系統學習的目標是尋找一個合適的動作選擇策略，即在任一給定的狀態下選擇哪種動作的方法，使產生的動作序列可獲得某種最優的結果（如累計立即回報最大）。第四十六頁，共100頁。第四十六頁，共100頁。機器學習—

概述研究目的希望得到通用的算法研究了解學習知識的模型、認知模型解決實際問題的知識庫域系統，達到工程目標研究特點不可預測性第四十七頁，共100頁。第四十七頁，共100頁。第六章機器學習概述幾種機器學習第四十八頁，共100頁。第四十八頁，共100頁。第六章機器學習概述幾種機器學習機械式學習指導式學習示例學習決策樹學習遺傳算法第四十九頁，共100頁。第四十九頁，共100頁。機械式學習概述是一種最簡單的機器學習系統。外界以一種推理機可直接使用的知識表示形式提供信息，學習系統無需作任何處理。它所要做的是記住所有的信息，考察系統已解決的問題，記住問題和結論。模型：

(x1,…,x2)(y1,…,y2)[(x1,…,x2),(y1,…,y2)]

輸入模式執行輸出值數據對（已解決問題結果）函數是一種基于記憶和檢索的辦法，因此儲存器的組織問題將影響檢索的效率。f存儲第五十頁，共100頁。第五十頁，共100頁。指導式學習概述通過和用戶的相互對話，把用戶的一般性意見或指示具體化；或協助用戶補充和修改原有的知識庫。該方法既避免系統自己分析、歸納和發現知識的困難，又無需提供知識的領域專家了解系統內部表示和組織知識的實際細節。是目前智能系統中采用較多的方法之一。第五十一頁，共100頁。第五十一頁，共100頁。指導式學習模型輸入推理機輸出知識庫征詢解釋加工歸并評價專家用戶第五十二頁，共100頁。第五十二頁，共100頁。指導式學習步驟征詢：請求并接受專家的指導。解釋：消化吸收成內部表示（系統規定的形式）。加工：轉換成推理機可直接使用的形式。歸并：歸并到知識庫中，主要檢查冗余性、一致性和完整性。評價：對執行結果進行評價。第五十三頁，共100頁。第五十三頁，共100頁。示例學習概述50年代興起的示例學習是歸納學習的一種。目前示例學習在某些系統中的應用已成為機器學習走向實踐的先導。環境提供給系統一些特殊的示例，這些示例事先由施教者劃分為正例和反例。示例學習系統由此進行歸納推理得到一般規則。環境提供給學習環節的正例和反例是低水平的信息，這是特殊情況下執行環節的行為。學習環節歸納出的規則是高水平的信息，可以在一般情況下用這些規則指導執行環節的工作。第五十四頁，共100頁。第五十四頁，共100頁。示例學習示例學習的學習模型驗證搜索解釋形成規則實驗計劃示例空間規則空間第五十五頁，共100頁。第五十五頁，共100頁。示例學習示例學習的學習模型1）示例空間：所有可能對系統進行訓練的示例集合。2）搜索：從示例空間中搜索出所需的示例。3）解釋：從所選的示例中抽象出信息，提供給規則空間。4）形成規則：從解釋處接收示例，抽取所需信息，將它們歸納成一般性規則。5）規則空間：存放已形成的規則。6）實驗計劃：一旦規則假設形成，系統就要選擇更多的示例來驗證和精練它們，甚至修正它們，以形成正確的知識。第五十六頁，共100頁。第五十六頁，共100頁。示例學習示例學習的兩個空間模型例子空間規則空間選擇例子解釋例子第五十七頁，共100頁。第五十七頁，共100頁。示例學習－兩個空間模型描述例子空間的描述語言可以描述所有例子；規則空間的可以描述所有規則。例如：紙牌，同花5張正例：{(2,c),(3,c),(5,c),(J,c),(A,c)},其中c，草花club規則：描述一手牌的全部謂詞表達式的集合。符號：SUIT(花色)，RANK（點數）常量：A,2,3,…,10.J,Q,K,clubs(草花),diamonds(方塊),hearts（紅桃）,spades(黑桃)合取連接詞∧，存在量詞所以有規則：對c1,c2,c3,c4,c5SUIT(c1,x)∧SUIT(c2,x)∧SUIT(c3,x)∧SUIT(c4,x)∧SUIT(c5,x)第五十八頁，共100頁。第五十八頁，共100頁。示例學習－兩個空間模型例子空間示教例子的質量。不能有錯，同時提供正例和反例，逐步分批有選擇地送入。選擇的條件：最有力地劃分規則空間；證實肯定假設規則的集合；否定否定假設規則的集合。搜索方法。第五十九頁，共100頁。第五十九頁，共100頁。示例學習－兩個空間模型規則空間最根本，真正學習的部分。定義：一套符號來規定表示規則的算符、術語，所有的描述都在其中。歸納方法：從特殊到一般的推理（P.221）常量化為變量。例，從幾個正例中找到共性的部分改成變量。去掉條件。同上例。去掉牌點數這個條件增加選擇（析?。?。例人臉牌。從RANK(c1,J),RANK(c2,K)推出還有RANK(c3,Q)曲線擬合。幾組值，解方程或用最小二乘法擬合成一條曲線或曲面。第六十頁，共100頁。第六十頁，共100頁。示例學習－兩個空間模型（規則空間）不管是去掉還是增加，都是擴大范圍。把已有的知識總結歸納推廣。但是要小心。越快越強的方法越容易出錯。原因是歸納推理方法是保假不保真。實際上沒有很嚴格的具體方法。因此，用歸納方法的過程就是搜索過程。找到包含在少數例子中的正確信息。歸納出錯就要回溯。要經常檢驗，用新例子去否定歸納出的錯誤規則。即解釋例子和選擇例子的反復，反復于例子空間和規則空間之間。第六十一頁，共100頁。第六十一頁，共100頁。示例學習－兩個空間模型（規則空間）對規則空間的要求表示要適應于歸納。如：有謂詞才可以增減；有狀態空間才能擬合。不同的歸納方法要求不同的規則表示方法。如果規則空間描述的語言的表達能力較弱，可以使用的歸納方法就比較少，規則空間的搜索反謂就比較小，搜索就比較容易。但解決的問題就較少。因此，設計是在規則空間表達能力與規則空間搜索難度之間進行權衡。表示和例子的一致。如相差很大，解釋例子和選擇例子的過程就很復雜。引入新術語（規則空間）。當表示語言不能描述學習過程中產生的新狀態時，要產生新的術語。第六十二頁，共100頁。第六十二頁，共100頁。示例學習－例有兩組數據組別發色眼睛1金藍紅藍金藍金灰2金黑黑藍黑藍黑灰金黑通過學習,得到描述規則1.[發色=金色∨紅色]∧[眼睛=藍色∨灰色]2.[發色=黑色]∨[眼睛=黑色]第六十三頁，共100頁。第六十三頁，共100頁。示例學習－例有兩組數據（決策樹學習）組別身高發色眼睛+矮金藍高紅藍高金藍-高金棕矮黑藍高黑藍高黑棕矮金棕第六十四頁，共100頁。第六十四頁，共100頁。決策樹學習決策樹(DecisionTree)

一種描述概念空間的有效的歸納推理辦法?；跊Q策樹的學習方法可以進行不相關的多概念學習，具有簡單快捷的優勢，已經在各個領域取得廣泛應用。第六十五頁，共100頁。第六十五頁，共100頁。決策樹學習（概述）決策樹學習是以實例為基礎的歸納學習。從一類無序、無規則的事物（概念）中推理出決策樹表示的分類規則。概念分類學習算法：來源于Hunt,Marin和Stone于1966年研制的CLS學習系統，用于學習單個概念。1979年,J.R.Quinlan給出ID3算法，并在1983年和1986年對ID3進行了總結和簡化，使其成為決策樹學習算法的典型。Schlimmer和Fisher于1986年對ID3進行改造，在每個可能的決策樹節點創建緩沖區，使決策樹可以遞增式生成，得到ID4算法。1988年，Utgoff在ID4基礎上提出了ID5學習算法，進一步提高了效率。1993年，Quinlan進一步發展了ID3算法，改進成C4.5算法。另一類決策樹算法為CART，與C4.5不同的是，CART的決策樹由二元邏輯問題生成，每個樹節點只有兩個分枝，分別包括學習實例的正例與反例。其基本思想是以信息熵為度量構造一棵熵值下降最快的樹，到葉子節點處的熵值為零，此時每個葉節點中的實例都屬于同一類。第六十六頁，共100頁。第六十六頁，共100頁。決策樹學習（概述）隨著決策樹學習算法的廣泛應用，包括C4.5和CART的各種算法得到進一步改進。當前比較引人注目的有斜超平面分割的多變決策樹(Multi-VarianceDecisionTree，MDT)算法，將遺傳算法、神經元網絡和C4.5相結合的GA-NN-C4.5算法，SVM決策樹算法。這些改進算法旨在結合各種方案的優勢，取得更合理的分類效果，總結出更通用的規則。第六十七頁，共100頁。第六十七頁，共100頁。決策樹學習（概述）決策樹學習采用的是自頂向下的遞歸方法。決策樹的每一層節點依照某一屬性值向下分為子節點，待分類的實例在每一節點處與該節點相關的屬性值進行比較，根據不同的比較結果向相應的子節點擴展，這一過程在到達決策樹的葉節點時結束，此時得到結論。從根節點到葉節點的每一條路經都對應著一條合理的規則，規則間各個部分（各個層的條件）的關系是合取關系。整個決策樹就對應著一組析取的規則。決策樹學習算法的最大優點是，它可以自學習。在學習的過程中，不需要使用者了解過多背景知識，只需要對訓練例子進行較好的標注，就能夠進行學習。如果在應用中發現不符合規則的實例，程序會詢問用戶該實例的正確分類，從而生成新的分枝和葉子，并添加到樹中。第六十八頁，共100頁。第六十八頁，共100頁。決策樹學習（決策樹）樹是由節點和分枝組成的層次數據結構。節點用于存貯信息或知識，分枝用于連接各個節點。樹是圖的一個特例，圖是更一般的數學結構，如貝葉斯網絡。

決策樹是描述分類過程的一種數據結構，從上端的根節點開始，各種分類原則被引用進來，并依這些分類原則將根節點的數據集劃分為子集，這一劃分過程直到某種約束條件滿足而結束。

根結點個子大可能是松鼠可能是老鼠可能是大象在水里會吱吱叫鼻子長脖子長個子小不會吱吱叫鼻子短脖子短可能是長頸鹿在陸地上可能是犀?？赡苁呛玉R第六十九頁，共100頁。第六十九頁，共100頁。決策樹學習（決策樹）可以看到，一個決策樹的內部結點包含學習的實例，每層分枝代表了實例的一個屬性的可能取值，葉節點是最終劃分成的類。如果判定是二元的，那么構造的將是一棵二叉樹，在樹中每回答一個問題就降到樹的下一層，這類樹一般稱為CART（ClassificationAndRegressionTree）。判定結構可以機械的轉變成產生式規則?？梢酝ㄟ^對結構進行廣度優先搜索，并在每個節點生成“IF…THEN”規則來實現。如圖6-13的決策樹可以轉換成下規則：

IF“個子大”THENIF“脖子短”THENIF“鼻子長”THEN可能是大象形式化表示成第七十頁，共100頁。第七十頁，共100頁。決策樹學習（決策樹）構造一棵決策樹要解決四個問題：收集待分類的數據，這些數據的所有屬性應該是完全標注的。設計分類原則，即數據的哪些屬性可以被用來分類，以及如何將該屬性量化。分類原則的選擇，即在眾多分類準則中，每一步選擇哪一準則使最終的樹更令人滿意。設計分類停止條件，實際應用中數據的屬性很多，真正有分類意義的屬性往往是有限幾個，因此在必要的時候應該停止數據集分裂：該節點包含的數據太少不足以分裂，繼續分裂數據集對樹生成的目標(例如ID3中的熵下降準則)沒有貢獻，樹的深度過大不宜再分。通用的決策樹分裂目標是整棵樹的熵總量最小，每一步分裂時，選擇使熵減小最大的準則，這種方案使最具有分類潛力的準則最先被提取出來第七十一頁，共100頁。第七十一頁，共100頁。決策樹學習（性質）證據由屬性值對表示證據由固定的的屬性和其值表示，如屬性（溫度），值（熱）最簡單的學習情況時每個屬性擁有少量的不相關的值。目標函數有離散輸出值決策樹分配一個二值的樹，很容易擴展成為多于兩個的輸出值。需要不相關的描述決策樹原則上是表述不相關的表示容忍訓練數據的錯誤對訓練樣本和表述樣本的屬性值的錯誤都有較強的魯棒性。訓練數據可以缺少值可以采用缺少屬性值的樣本學習。（不是所有樣本都有）第七十二頁，共100頁。第七十二頁，共100頁。決策樹學習（應用）根據病情對病人分類根據起因對故障分類根據付款信用情況對貸款申請者分類這些都是將輸入樣本分類成可能離散集

分類問題第七十三頁，共100頁。第七十三頁，共100頁。決策樹學習（學習）Shannon信息熵自信息量設信源X發出ai的概率p(ai)，在收到符號ai之前，收信者對ai的不確定性定義為ai的自信息量I(ai)。I(ai)=-logp(ai)。信息熵自信息量只能反映符號的不確定性，而信息熵用來度量整個信源整體的不確定性，定義為：

其中，r為信源X發出的所有可能的符號類型。信息熵反應了信源每發出一個符號所提供的平均信息量。條件熵設信源為X，收信者收到信息Y，用條件熵H(X|Y)來描述收信者在收到Y后對X的不確定性估計。設X的符號ai，Y的符號bj，p(ai|bj)為當Y為bj時，X為ai的概率，則有：平均互信息量用平均互信息量來表示信號Y所能提供的關于X的信息量的大小，用I(X,Y)表示：

第七十四頁，共100頁。第七十四頁，共100頁。決策樹學習（學習）設學習的實例集為其中Si為學習實例，T實例集大小。對于有指導的學習，任一個Si具有明確標定的類別，向量表示該實例的特性，即Si的信息為，如果一個觀測值具有屬性則應該劃歸為類，應該有下面的規則總結出來式中Xi為事件所具有的第i個屬性。這里的屬性和類具有廣泛的意義。第七十五頁，共100頁。第七十五頁，共100頁?；谶z傳算法的機器學習應用簡單遺傳算法（simple

geneticalgorithm,SGA）一個SGA算法來說主要涉及以下內容：

·編碼和初始群體生成；

·群體的評價；

·個體的選擇；

·交換；

·突變；

第七十六頁，共100頁。第七十六頁，共100頁?；谶z傳算法的機器學習應用1.編碼和初始群體的生成

GA的工作基礎是選擇適當的方法表示個體和問題的解（作為進化的個體）。SGA要求個體均以0、1組成的串來表示，且所有個體串都是等長的。實際上，可以任意指定有限元素組成的串來表示個體，而不影響GA的基本算法。對于同一問題，可以有不同的編碼表示方法。由于遺傳操作直接作用于所表示的串上，因而不同的表示方法對SGA的效率和結果都會有影響。

第七十七頁，共100頁。第七十七頁，共100頁?；谶z傳算法的機器學習應用1.編碼和初始群體的生成

從原理上講，任何取值為整數（或其它有限可枚舉的值）的變量，均可用有限長度的0、1串來表示，而任何取值為連續實數的變量也均可用有限長度的0、1串來近似表示。因此，對任何一個變量，均可在一定程度上用0、1串來表示（編碼），而當問題的解涉及多個變量時，則可用各變量對應串的拼接（形成一個長串）來表示相應解。

一般可用隨機方法來產生初始群體，當然最好能考慮各個體的代表性和分布概率。

第七十八頁，共100頁。第七十八頁，共100頁?；谶z傳算法的機器學習應用2.群體的評價

對群體中各個體的適應性評價常需直接利用待優化問題的目標函數。這一目標函數也可稱為適應函數，個體選擇（或再生）過程正是基于這一函數來評價當前群體中各個體的再生概率。

第七十九頁，共100頁。第七十九頁，共100頁?；谶z傳算法的機器學習應用3.個體的選擇

選擇操作是對自然界“適者生存”的模擬。評價值（目標函數值）較大的個體有較高的概率生存，即在下一代群體中再次出現。

一種常用的選擇方法是按比例選擇，即若個體i的適應值（目標函數值）是fi，則個體i在下一代群體中復制（再生）的子代個數在群體中的比例將為：

fi/∑fi

。

其中，∑fi是指所有個體適應值之和。

第八十頁，共100頁。第八十頁，共100頁?；谶z傳算法的機器學習應用3.個體的選擇

若當前群體與下一代群體的個數均維持在n，則每一個體i在下一代群體中出現的個數將是：

n*fi/∑fi=fi/f,

其中f=∑fi/n是群體評價的平均值。fi/f的值不一定是一個整數。為了確定個體在下一代中的確切個數，可將fi/f的小數部分視為產生個體的概率。如，若fi/f為2.7，則個體i有70％的可能再生2+1=3個，而有30％的可能只再生2個。

第八十一頁，共100頁。第八十一頁，共100頁?；谶z傳算法的機器學習應用3.個體的選擇

SGA采用稱為旋轉盤（roulettewheel）的方法來產生各個體的再生數。方法是：

每一個體均對應于旋轉盤中的一個以園點為中心的扇形區域，區域角度為2π*fi/∑fi

，因而，各個體的區域角度之和等于2π。然后隨機產生一個0到2π的值，根據該值所對應的區域，再生一個對應個體，直到產生的個體個數達到所需的數目，從而生成下一代的原始群體。這個群體還需進一步應用交換和突變操作。

第八十二頁，共100頁。第八十二頁，共100頁?；谶z傳算法的機器學習應用4.交換

交換是GA中最主要的遺傳操作，其工作于選擇過程結束后產生的下一代群體。交換操作應用于從這一群體中隨機選擇的一系列個體對（串對）。

SGA采用的是單點交換。設串長為L，交換操作將隨機選擇一個交換點（對應于從1到L-1的某個位置序號），緊接著兩串交換點右邊的子串互換，從而產生了兩個新串。

第八十三頁，共100頁。第八十三頁，共100頁?；谶z傳算法的機器學習應用4.交換

例如，設Ａ1，Ａ2為要交換的串，交換點被隨機選擇為7（串長為10）。

Ａ1＝1000011111

Ａ2＝1111111011

交換得新串Ａ1'，Ａ2'：

Ａ1'＝1000011011

Ａ2'＝1111111111

當然，并非所有選中的串對都會發生交換。這些串對發生交換的概率是Pc。Pc為事先指定的0－1之間的值，稱為交換率。第八十四頁，共100頁。第八十四頁，共100頁?；谶z傳算法的機器學習應用5.突變

另一種遺傳操作是突變，它一般在交換后進行。突變操作的對象是個體（即串），旨在改變串中的某些位的值，即由0變為1，或由1變為0。并非所有位都能發生變化，每一位發生變化的概率是Pm。Pm為事先指定的0－1之間的某個值，稱為突變率。串中每一位的突變是獨立的，即某一位是否發生突變并不影響其它位的變化。突變的作用是引進新的遺傳物質或恢復已失去的遺傳物質。例如，若群體的各串中每一位的值均為0，此時無論如何交換都不能產生有1的位，只有通過突變。第八十五頁，共100頁。第八十五頁，共100頁?；谶z傳算法的機器學習應用5.突變

下面舉一例子來說明遺傳算法的一個進化循環。設每一串的長度為10，共有4個串組成第一代群體（POP1），目標函數（適應函數）為各位值之和，因而函數值為0－10。

POP1中四個串的適應值分別為：3，6，6，9，所以再生的比例個數為：0.5，1，1，1.5。若最后實際的再生個數為0，1，1，2，則產生選擇后的群體POP2。下一步對POP2中各串配對，隨機選擇串1和串4為一對，串2和串3為另一對。第八十六頁，共100頁。第八十六頁，共100頁?；谶z傳算法的機器學習應用5.突變

群體POP1

串適應值

0000011100

3

1000011111

6

0110101011

6

1111111011

9

群體POP2（選擇后）

串適應值

1000011111

6

0110101011

6

1111111011

9

1111111011

9

第八十七頁，共100頁。第八十七頁，共100頁?；谶z傳算法的機器學習應用5.突變

設交換率為0.5，即只有一對串發生交換，如串1和串4。若交換點隨機選在位置7，因而交換后產生群體POP3。設突變率為0.05，即在POP3的40個位中，共有2個位發生突變，不妨設突變發生在串2的第6位和串4的第1位，從而產生群體POP4。注意，僅群體POP4代表新一代的群體（上一代為POP1），POP2和POP3只是一些進化中的中間群體。第八十八頁，共100頁。第八十八頁，共100頁?；谶z傳算法的機器學習應用5.突變

群體POP3（交換后）

串適應值

1000011011

5

0110101011

6

1111111011

9

1111111111

10

群體POP4（突變后）

串適應值

1000011011

5

0110111011

7

1111111011

9

0111111111

9第八十九頁，共100頁。第八十九頁，共100頁?；谶z傳算法的機器學習應用5.突變

在SGA算法中，一般采用的群體大小為30到200，交換率為0.5到1，突變率為0.001