《機器學習》PPT課件.ppt

《《機器學習》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《機器學習》PPT課件.ppt（89頁珍藏版）》請在裝配圖網上搜索。

1、第六章 機器學習 6.1 機器學習概念6.2 示例學習6.2.1示例學習的兩個空間模型6.3 基于解釋的學習6.4基于案例的推理6.5 加強學習 6.1 機器學習的概念6.1.1 機器學習的發(fā)展歷史1.神經元模型研究階段這個時期主要技術是神經元模型以及基于該模型的決策論和控制論;機器學習方法通過監(jiān)督（有教師指導的）學習來實現(xiàn)神經元間連接權的自適應調整，產生線性的模式分類和聯(lián)想記憶能力。具有代表性的工作有FRosenblaft的感知機（1958年）；NRashevsky數學生物物理學（1948年）；WSMcCullouch與WPitts的模式擬神經元的理論（1943年）;RMFriedberg對

2、生物進化過程的模似等。 v2符號概念獲取研究階段60年代初期，機器學習的研究進入了第二階段，在這個階段，心理學和人類學習的模似占有主導地位，其特點是使用符號而不是數值表示來研究學習問題，其目標是用學習來表達高級知識的符號描述。在這一觀點的影響下，主要技術是概念獲取和各種模式識別系統(tǒng)的應用；研究人員一方面深入探討學習的簡單概念，另一方面則把大量的領域知識并入學習系統(tǒng)，以便它們發(fā)現(xiàn)高深的概念。這個階段代表性的工作是溫斯頓（Winston，1975）的基于示例歸納的結構化概念學習系統(tǒng)。 v3基于知識的各種學習系統(tǒng)研究階段機器學習發(fā)展的第三個階段始于70年代中期，這個階段不再局限于構造概念學習系統(tǒng)和獲

3、取上下文知識，結合了問題求解中的學習、概念聚類、類比推理及機器發(fā)現(xiàn)的工作。相應的有關學習方法相繼推出，比如示例學習、示教學習、 觀察和發(fā)現(xiàn)學習、類比學習、基于解釋的學習。工作特點強調應用面向任務的知識和指導學習過程的約束，應用啟發(fā)式知識于學習任務的生成和選擇，包括提出收集數據的方式、選擇要獲取的概念、控制系統(tǒng)的注意力等。 v4聯(lián)結學習和符號學習共同發(fā)展階段80年代后期以來，形成了聯(lián)結學習和符號學習共同發(fā)展的局的第四個階段。在這個時期，發(fā)現(xiàn)了用隱單元來計算和學習非線性函數的方法，從而克服了早期神經元模型的局限性，同時，由于計算機硬件的迅速發(fā)展，使得神經網絡的物理實現(xiàn)變成可能，在聲間識別、圖像處理

4、等領域，神經網絡取得了很大的成功。在這個進期，符號學習伴隨人工智能的進展也日益成熟，應用領域不斷擴大，最杰出的工作有分析學習（特別是解釋學習）、遺傳算法、決策樹歸納等?，F(xiàn)在基于計算機網絡的各種自適應、具有學習功能的軟件系統(tǒng)的研制和開發(fā),將機器學習的研究推向新的高度。 6.1.2什么是機器學習什么是機器學習，到今仍沒有嚴格定義，不同學派對機器學習有不同的定義 準確、完整地給出機器學習的定義很困難，綜合上述三種觀點可以得出，學習是對某一個特定目標的知識獲取的智能過程，系統(tǒng)的內部表現(xiàn)為新知識結構的建立和改進，外部表現(xiàn)為系統(tǒng)性能的改善，變得更快、更精確、更健全。 v一個機器學習系統(tǒng)應具有以下特點：v1

5、.具有適當的學習環(huán)境v學習系統(tǒng)中環(huán)境并非指通常的物理條件，而是指學習系統(tǒng)進行學習時所必需的信息來源。v2.具有一定的學習能力v一個好的學習方法和一定的學習能力是取得理想的學習效果的重要手段。所以，學習系統(tǒng)應模擬人的學習過程，使系統(tǒng)通過與環(huán)境反復多次相互作用，逐步學到有關知識，并且要使系統(tǒng)在學習過程中通過實踐驗證、評價所學知識的正確性。v3.能用所學的知識解決問題v學習的目的在于應用，學習系統(tǒng)能把學到的信息用于對未來的估計、分類、決策和控制。 v4.能提高系統(tǒng)的性能v提高系統(tǒng)的性能是學習系統(tǒng)最終目標。通過學習，系統(tǒng)隨之增長知識，提高解決問題的能力，使之能完成原來不能完成的任務，或者比原來做得更好

6、。v學習系統(tǒng)至少應有環(huán)境、知識庫、學習環(huán)節(jié)和執(zhí)行環(huán)節(jié)四個基本部分。一種典型的機器學習系統(tǒng)（迪特里奇（Dietterich）學習模型）如圖6-1所示。環(huán)境向系統(tǒng)的學習部件提供某些信息，學習環(huán)節(jié)利用這些信息修改知識庫，增進執(zhí)行部件的效能；執(zhí)行環(huán)節(jié)根據知識庫完成任務，同時把獲得的信息反饋給學習部件。下面介紹其主要組成部分的功能。 1.環(huán)境v系統(tǒng)中的環(huán)境包括工作對象和外界條件。比如在醫(yī)療系統(tǒng)中，環(huán)境就是病人當前的癥狀，物化檢驗的報告和病歷等信息；在模式識別中，環(huán)境就是待識別的圖形或影物；在控制系統(tǒng)中，環(huán)境就是受控的設備或生產流程。v環(huán)境提供給系統(tǒng)的信息水平和質量對于學習系統(tǒng)有很大的影響。信息的水平是指

7、信息的一般性程度，也就是適用范圍的廣泛性，高水平的信息往往比較抽象，適用面更廣泛。v信息的質量指信息的正確性、信息選擇的適宜性和信息組織的合理性。信息質量對學習難度有明顯的影響。 2.學習環(huán)節(jié)v學習環(huán)節(jié)是系統(tǒng)的學習機構，是學習系統(tǒng)的核心。它通過對環(huán)境的搜索取得外部信息，然后經分析、綜合、類比、推理等思維過程獲得知識，并將這些知識送入知識庫，供執(zhí)行環(huán)節(jié)使用。v事實上，由于環(huán)境提供的信息水平與執(zhí)行環(huán)節(jié)所需的信息水平之間往往有差距，學習環(huán)節(jié)的任務就是解決這個水平差距問題。如果環(huán)境提供較高水平的信息，學習環(huán)節(jié)就去就去補充遺漏的細節(jié)，以便執(zhí)行環(huán)節(jié)能用于具體情況。如果環(huán)境提供較具體的低水平信息，即在特殊情

8、況執(zhí)行任務的實例，學習環(huán)節(jié)就要上此歸納規(guī)則，以便系統(tǒng)能完成更為一般的任務。 3.知識庫v學習系統(tǒng)設計的另一個重要問題就是知識庫的形成設計以及其內容。學習系統(tǒng)實質上就是對原有知識的擴充和完善。 4.執(zhí)行環(huán)節(jié)v執(zhí)行環(huán)節(jié)實際上是由執(zhí)行環(huán)節(jié)和評價兩部分組成，執(zhí)行環(huán)節(jié)用于處理系統(tǒng)面臨的現(xiàn)實問題，比如定理證明、智能控制、自然語言處理、機器人行動規(guī)劃等；評價環(huán)節(jié)用來驗證、評價執(zhí)行環(huán)節(jié)執(zhí)行的效果，比如結果的正確性等。評價環(huán)節(jié)的處理方法有兩種，一種是把評價時所需的性能指標直接建立在系統(tǒng)中，由系統(tǒng)對執(zhí)行環(huán)節(jié)所做出的結論進行評價；另一種是由人類協(xié)助完成評價工作。v另外，從執(zhí)行環(huán)節(jié)到學習環(huán)節(jié)心須要有反饋信息。這們，學

9、習環(huán)節(jié)就可以根據反饋信息決定是否要從環(huán)境中獲取進一步的信息進行再學習，以便修改、完善知識庫中的知識。 6.1.3機器學習分類v當前國際上流行的機器學習分類方法主要有四種：按應用領域分類：主要的應用領域有專家系統(tǒng)、認知模擬、規(guī)劃和問題求解、數據挖掘、網絡信息服務、圖象識別、故障診斷、自然語言理解、機器人和博弈等。v按獲取的知識的表示分類：有形式邏輯表達式、形式文法、代數表達式參數、圖和網絡、框架和模式、計算機程序和其它的過程編碼、產生式規(guī)則、決策樹、框架、神經網絡等；v按推理策略分類：如演繹推理和歸納推理。v按學習系統(tǒng)性綜合分類的方法：考慮了事物的歷史淵源、知識表示、推理策略和應用領域等因素，是

10、對前面三種分類方法的綜合。 （一）基于推理策略的分類v一個學習過程實質上是學習系統(tǒng)把環(huán)境所提供的信息轉換成新的形式，以便存儲和使用。這種信息的轉換就是種推理，而推理的性質確定了學習策略的類型。在學習過程中，學生所使用的推理越少，他對教師的依賴就越大，因而教師的負擔就越重，反過來，學生使用的推理越多，教師的負擔就越輕。顯然，基于推理策略分類方法可以按學生使用推理的多少和難易程度進行。下面分別進行討論。 v1.機械學習（Rote Learning）v機械學習是最簡單的學習方法，它亦被稱為記憶學習或死記硬背式學習。這種學習方法不需要推理，而是由教師向系統(tǒng)提供被記憶的信息，學習者無需任何推理或其它的知

11、識轉換，直接吸取環(huán)境所提供的信息，并用這些信息指導系統(tǒng)行為。v 機械學習是記憶，它僅保存新的知識以便使用。這里是個檢索問題，而不是重復計算、推理或查詢。機械學習可以認為是基本的學習方式，它本身并不能實現(xiàn)智能學習，但是它是其他學習系統(tǒng)所固有重要組成部分。在機械學習系統(tǒng)中，知識已經以某種方式獲取，并且是一種直接可使用的形式。所有學習系統(tǒng)都是建立在機械學習的基礎之上，即對知識庫中的知識進行存儲、維護和檢索。 v2. 示教學習（Learning from Instruction or Learning by being told）v示教學習中，教師以某種形式（教導和建議）提出和組織知識，以使學生擁有的

12、知識可以不斷地增加。學生把知識轉換成內部可使用的表示形式，并將新的知識和原有知識有機地結合為一體；示教系統(tǒng)中，由外部給系統(tǒng)提供抽象的、一般化的信息，學習系統(tǒng)經過選擇和改造，把新的信息與系統(tǒng)原有的知識融為一體。由于外部提供的信息過于抽象，它的水平高于執(zhí)行時所用信息的水平，因此學習環(huán)節(jié)要把把較高水平的知識轉換為較低水平的知識，這種轉換稱為實用化。 v研究示教學習的途徑主要有兩種。一是在開發(fā)系統(tǒng)時接收抽象的、高級的信息，并將它變換成規(guī)則，以便批指導執(zhí)行部分。二是開發(fā)完善的工具，比如知識庫的編輯和調試輔助程序，使得專家們可以很方便地將專門知識轉換成詳細的規(guī)則。 v3. 演繹學習（Deductive L

13、earning）v這種學習方法是一種常規(guī)的邏輯推理方法。其推理的過程通常從公理出發(fā)，經過邏輯變換，推導出結論。演繹學習包括知識改造、知識編譯、生成宏操作、保持等價操作和其他的一些保真變換。 v4. 解釋學習(Explanation-based Learning)v解釋學習利用問題求解的示例，依賴領域知識構造出求解過程的因果解釋結構，并獲取控制知識，為以后類似問題求解提供指導。v解釋學習過程可分成兩個步驟：v首先產生解釋結構：輸入實例后，系統(tǒng)首先對問題進行求解。 v再用解釋結構對得到的解釋結構和事例進行概括：概括通常采取的方法是將常量轉換成變量，且去掉某些不重要的信息，僅僅保留求解時所必需的那些

14、關鍵信息，經過一定的方式進行組合形成產生式規(guī)則，從而獲得概括性的控制知識。 v5. 類比學習（Learning by Analogy）v類比學習利用二個不同領域（源域、目標域）中的知識相似性，通過類比，從源域的知識（包括相似的特征和其它性質）推導出目標域的相應知識。例如：未開過貨車的司機有開小車的知識就可完成開貨車的任務；v類比學習是演繹和歸納學習的組合。它對不同論域的描述進行匹配，確定公共的子結構，以此作為類比映射。尋找公共子結構是歸納推理，而實現(xiàn)類比映射是演繹推理。 v6. 歸納學習（Inductive learning）v歸納學習由教師或環(huán)境提供某概念的一些實例或反例，學生通過歸納推理得

15、出該概念的一般描述。歸納學習可分為示例學習和觀察與發(fā)現(xiàn)學習。v示例學習（Learning from Examples ）v示例學習也稱為概念獲?。–oncept Acquisition）。是由教師提供給系統(tǒng)某種概念的正例集合反例集合，學習通過歸納推理產生覆蓋所有正例并排除所有反例的該概念的一般描述。這些正例是由已知概念的教師或者是學生做實驗時從系統(tǒng)中得到的反饋信息而提供的。 v觀察與發(fā)現(xiàn)學習（Learning from Observation and Discovery）v觀察與發(fā)現(xiàn)學習是由環(huán)境提供一組觀察事例，學生構造一個一般的概念描述（即理論）來覆蓋所有或大多數事例。這是一種無導師學習。這

16、類學習又分為觀察學習與機器發(fā)現(xiàn)兩類。 v（1）觀察學習 觀察學習是學生將已知事例進行分類，同時產生每一類的一般概念描述。觀察學習又可根據是否漸近（incremental）方式而分為va概念聚類 b概念形成 v(2)機器發(fā)現(xiàn)（Machine Discovery）v學生從觀察的事例或經驗數據中進行歸納產生規(guī)律或規(guī)則，這就是機器發(fā)現(xiàn)。機器發(fā)現(xiàn)是觀察與發(fā)現(xiàn)學習的最困難、最富有創(chuàng)造性的一種學習形式。機器發(fā)現(xiàn)包括有經驗發(fā)現(xiàn)和知識發(fā)現(xiàn)兩種類型。 （二）基于系統(tǒng)綜合性的分類v基于系統(tǒng)性分類，機器學習可分為四種類型，即：歸納學習、分析學習、聯(lián)接學習、遺傳算法與分類系統(tǒng)。 v1分析學習（Analytie Lear

17、ning）分析學習是針對幾個實際例子，應用領域知識進分析來學習。 v2聯(lián)結學習(connection based learning)聯(lián)結學習的目標是區(qū)分輸入模式的等價類。一個聯(lián)結模型是由一些類似神經元的簡單單元帶權互邊而組成的網絡。 v3遺傳算法（Genetic Algorithm）遺傳算法似生物繁殖的突變（互換、倒位、點突變等）和達爾文的自然選擇（在每一生態(tài)環(huán)境中適者生存）。 v4.加強學習（reinforcement learning）加強學習的學習目標是尋找一個合適的動作選擇策略，使產生的動作序列可獲得某種最優(yōu)的結果（如累計立即回報最大）?；痉椒ㄊ峭ㄟ^與環(huán)境的試探性（trial and

18、 error）交互來確定和優(yōu)化動作的選擇。 6.2示例學習v示例學習屬于歸納學習，是目前機器學習方法中最成熟的方法之一。示例學習要求環(huán)境能夠從一些特殊的實例（這些實例事先由教師劃分為正例和反例兩類），并由這些實例進行歸納推理，導出一般性的規(guī)則。 v6.2.1示例學習的兩個空間模型v示例學習的模型如圖6-2所示。例子空間是所有可能的正、反例構成的空間；假設空間（又稱概念空間）是所有可能的概念描述（稱為假設）構成的空間。v 假設空間中的每一假設都對應于例子空間中的一個子集，使得該子集中的例子均是該假設的例子。 v在圖6-2中，除描繪從例子學習的實例空間規(guī)則空間外，還描繪了解釋實例和實驗規(guī)劃過程。v

19、在這個模型中，首先由示教者給實例空間提供一些初始示教例子，然后程序對示教例子進行解釋。由于示教例子的形式往往不同于規(guī)則形式，所以有必要對例子進行解釋。往后再利用被解釋的示教例子支搜索規(guī)則空間。一般情況下不能一次就從規(guī)則空間中搜索到要求的規(guī)則，因此還要尋找一些新的示教例子，這個過程就是選擇例子。此過程如此循環(huán)，直到搜索到要求的規(guī)則。 v（一）實例空間v考慮撲克牌中“同花”概念的問題，同花是五張同一花色所組成的手牌。在這個學習問題中，實例空間是五張牌的全部各手牌的集合。我們可以把這個空間中單個的點表示為一組五個有序對，比如：v （2，梅花），（3，梅花），（5，梅花），（J，梅花），（K，梅花）v

20、每一有序對指明一張牌的點數和花色。整個實例空間是所有這樣的五張牌集合的空間。高質量的示教例子是無二義性的，它可以為規(guī)則空間的搜索提供可靠的指導。低質量的示教例子會引起互相矛盾的解釋，其結果僅為規(guī)則空間的搜索提供試探性的指導。示教例子排列次序也會影響學習的質量。 v一般情況下認為實例是同時提供的，也可以主動地選擇另外一些附加的實例，以便修正假設，這種方法稱為補充學習。還有的程序直接搜索實例空間，這種方法稱主動選擇例子。 v（二）規(guī)則空間v定義規(guī)則空間的目的是指定表示規(guī)則的操作符和術語。所謂規(guī)則空間是用指定的描述語言可以表示的所有規(guī)則(概念假設)的集合。對規(guī)則空間有三個方面的要求，即規(guī)則的表示形式

21、應適應歸納推理，規(guī)則的表示與實例的表示一致，規(guī)則空間應包含要求的規(guī)則。 v三）解釋例子v解釋示教例子的基本目的是提取指導規(guī)則空間搜索有用的信息。通常是把示數例子轉換成易于進行符號歸納的形式。不過，這種轉換也許是困難的，尤其是在感性的學習中。 v (四）實驗規(guī)則v一旦學習環(huán)節(jié)根據示教例子搜索規(guī)則空間，并產生可能合理的假設規(guī)則集合H后，程序就可能需要收集更多的訓練實例加以測試和修改集合H。當實例空間和規(guī)則空間是以不相同的方法表示時，就需要判斷訓練哪些實例和怎樣才能獲得它們，這是一個復雜的過程。比如，假定一個遺傳學習程序要想發(fā)現(xiàn)DNA的哪一部分是最重要的，為了測試幾個高級假設（即假設的規(guī)則）要安排復

22、雜的試驗。這些試驗合成DNA的特殊成分，并把它插入到適當的細菌細胞中，以觀察細胞的最后動作。 v搜索規(guī)則空間的方法有：特化搜索既從最泛化的假設（概念描述）出發(fā)，每次取用一個新的例子，就產生一些特化的描述，直到將初始最泛化的假設特化為解描述。泛化搜索即從最特化的假設（相應于例子空間中的一個例子）開始，每次取用一個新的例子時，就產生一些泛化的描述，直到產生出足夠泛化的解描述。大多數示例學習方法都采用這二種方法或這二個方法的結合。下面介紹搜索規(guī)則空間的幾種方法。這些方法都具有一個假設規(guī)則的集合H，不同的僅僅是對H的改進，以便得到要求的規(guī)則。 v（1）變型空間法（version-space metho

23、ld）v變型空間法是TMMitchell于1977年提出的一種數據驅動型的學習方法。v該方法以整個規(guī)則空間為初始的假設規(guī)則集合H。依據示教例子中的信息，系統(tǒng)對集合H進行一般化或特殊化處理，逐步縮小集合H。最后使得H收斂到只含有要求的規(guī)則。由于被搜索的空間H逐漸縮小，故稱為變型空間法。 v 1規(guī)則空間的結構v在規(guī)則空間中，表示規(guī)則的點與點之間存在著一種由一般到特殊的偏序關系。我們定義為覆蓋，例如，color(X,Y)覆蓋color(ball,Z)，于是又覆蓋color(ball,red)。v作為一個簡單的例子，考慮有這樣一些屬性和值的對象域：v Sizes=large,smallv Colors

24、=red,white,bluev Shapes=ball,brick,cubev這些對象可以用謂詞obj(Sizes,Color,Shapes)來表示。用變量替換常量這個泛化操作定義 v如圖6-3的空間。 v圖6-3表示了一個規(guī)則空間偏序關系的一部分。我們可以把歸納學習看成是對同所有訓練實例相一致的概念空間的搜索。在搜索規(guī)則空間時，使用一個可能合理的假設規(guī)則的集合H，是規(guī)則空間的子集，從圖6-4可知，H中最一般的元素構成的子集為G，H中最特殊的元素構成的子集為S。在規(guī)則空間中，H是以G為上確界和以S為下確界的一段。因此，可以用G和要來表示集合H。 v2修選刪除算法v Mitchell的學習算法

25、稱為候選刪除算法。在這種算法中，把尚未被數據排除的假設稱為可能假設，把所有可能假設構成的集合H稱為變型空間。v 算法一開始，變型空間H包含所有的概念隨著向程序提供示教正例后，程序就從變v型空間中刪除候選概念。當變型空間僅包含有一個候選概念時，就找到了所要求的概念。v該算法分為四個步驟： (1)把H初始化為整個規(guī)則空間。這時G僅包含空描述。S包含所有最特殊的概念。v實際上，為避免S集合過大，算法把S初化為僅包含第一個示教正例。（2）接受一個新的示教例子。如果這個例子是正例，則從G中刪除不包含新例的概念，然后修改S為由新正例和S原有元素同歸納出最特殊化的泛化。這個過程稱為對集合S的修改過程。如果這

26、個例子是反例，則從S中刪去包含新例的概念，再對G作盡量小的特殊化，使之不包含新例。這個過程稱為集合G的修改過程。（3）重復步驟，直到G=S，且使這兩個集合都只含有一個元素為止。（4）輸出H中的概念（即輸出G或S）。 v3方法討論v變型空間法還存在有一些弱點，需要加以改進。該方法的主要缺點是：v（1）抗干擾能力差v （2）無法發(fā)現(xiàn)析取概念 2.改進假設法v改進假設法（hypothesis-rfinement methold）也是一種數據驅動方法。這種方法表示規(guī)則和實例的形式不統(tǒng)一。程序根據例子選擇一種操作，用該操作去改進假設規(guī)則集H中的規(guī)則。 v3.產生與測試法v產生與測試法（generate

27、and test）是一種模型驅動方法（model-driven methold）。這種方法針對示教例子反復產生和測試假設的規(guī)則。在產生假設規(guī)則時，使用基于模型的知識，以便只產生可能合理的假設。 v4.方案示例法v方案示例法（schema instantiation）也是一種模型驅動方法。該方法使用規(guī)則方案的集合來約束可能合理的規(guī)則的形式，其中最符合示教例子的規(guī)則方案被認為是最合理的規(guī)則。數據驅動方法的優(yōu)點是可以逐步接受示教例子，以漸近方式學習，特別是變型空間法，它很容易修改集合H，不要求程序回溯就可以考慮新的實例。而模型驅動方法難以逐步學習，它是通過檢查全部實例來測試假設。在使用新假設時，它必

28、須回溯或重新搜索規(guī)則空間。因為原來對假設的測試已不適用于新實例加入后的情況。 6.2.2示例學習的一個變種決策樹學習算法 v 1 決策樹v決策樹歸納算法主要是通過一組輸入輸出樣本構建決策樹的有指導學習方法。一個典型的決策樹學習系統(tǒng)采用的確是自頂向下的方法，在部分搜索空間中搜索解決方案。它可以確保求出一個簡單的決策樹，但未必是最簡單的。v決策樹一個屬性節(jié)點的輸出分枝和該節(jié)點的所有可能的檢驗結果相對應。圖6-6給出了有兩個輸出屬性X和Y的樣本分類的一個簡單決策樹。所有屬性值X和Y=B的樣本屬于類2。不論屬性Y的值是多少，值X1的樣本都屬于類1。對于樹中的非葉節(jié)點，可以沿著分枝繼續(xù)分區(qū)樣本，每一個子

29、節(jié)點得到它相應的樣本子集。 v生成決策樹的一個著名的算法是Quinlan的ID3算法，它有一個改進版本叫C4.5。vID3算法從樹的根節(jié)點處的所有訓練樣本開始，選取一個屬性來分區(qū)這些樣本。對屬性的每一個值產生一個分枝。分枝屬性值的相應樣本子集被移到新生成的子節(jié)點上。 v自頂向下的決策樹的生成算法的關鍵性決策是對節(jié)點屬性值的選擇。ID3和C4.5算法的屬性選擇的基礎是基于節(jié)點所含的信息熵最小化。ID3的屬性選擇是根據一個假設，即：決策樹的復雜度和所給屬性值表達的信息量是密切相關的?；谛畔⒄摰姆椒ǎ瑢σ粋€樣本進行分類時所做檢驗的數量最小，要選擇的分類屬性是可以給出最高信息增益的屬性，即信息熵最小

30、化的屬性。ID3的擴展是C4.5算法，C4.5算法把分類屬性擴展到數字屬性。 v2 C4.5算法：生成一個決策樹vC4.5算法最重要的部分是由一組訓練樣本生成一個初始決策樹的過程。該算法生成一個決策樹形式的分類器，決策樹節(jié)點具有兩種類型的結構：一個葉節(jié)點，表示一個類，一個決策點，它指定要在單個屬性值上進行的檢驗，對檢驗的每個可能輸出有一個分枝和子樹。 v決策樹可以用來對一個新鮮樣本進行分類，這種分類從該樹的根節(jié)點開始，然后移動樣本直至達葉節(jié)點。在每個非葉決策點處，確定該節(jié)點的屬性檢驗結果，把注意力轉移到所選擇子樹的根節(jié)點上。例如，圖6-7a中的決策樹的分類模型問題，待分類的樣本如圖6-7b所示

31、，然后，該算法將生成一條通過節(jié)點A，C，F(xiàn)（葉節(jié)點）的路徑直到得出最終分類決策，即類2為止。 v 圖6-7 基于決策樹模型的一個新樣本的分類 v C4.5算法的構架是基于享特的CLS方法，其通過一組訓練樣本T構造一個決策樹。我們用 C1，C2，CK來表示這些類。集合T所含的內容信息有3種可能性：v 1T包含一個或更多的樣本，它們全部屬于單個的類Cj。那么T的決策樹是由類C1標識的一個葉節(jié)點。v 2T不包含樣本。決策樹也是一個葉，但和該葉關聯(lián)的類由不同于T的信息決定，如T中的絕大多數類。C4.5算法以在所給節(jié)點的雙親上出現(xiàn)最頻繁的類作為準則。v 3T包含屬于不同類的樣本。這種情況下，是把T精化成

32、朝向一個單類樣本集的樣本子集。根據某一個屬性，選擇具有一個或更多互斥的輸出 O1，O2，On 的合適檢驗。T被分區(qū)成子集T1，T2，Tn，其中Ti包括T中所選擇的檢驗的輸出是Oi的所有樣本。T的決策樹包括標識檢驗的一個決策點和每個可能輸出的一個分枝（圖6-7a中的決策樹的節(jié)點A，B和C是這種類型節(jié)點的例子）。 6.3 基于解釋的學習v基于解釋的學習是八十年代中期興起的新型機器學習方法，是分析學習的主要方式，與基于大量訓練例作歸納推理的數據密集型學習方法不同，基于解釋的學習是知識密集型的，可克服歸納學習因缺乏領域知識的引導而面臨的問題?；诮忉尩膶W習通過應用領域理論（領域知識）對單一事例所作的分

33、析，構造出求解過程的因果解釋結構，并獲取控制知識，用于指導以后求解類似的問題。 v一、基于解釋學習的工作原理v 基于解釋學習也是屬于通過實例學習的方法，與通過實例學習的方法與眾不同之處在于學習系統(tǒng)除了實例之外，還需要具備有關領域的知識，并且能夠根據這些知識對實例進行分析，從而構成解釋，產生規(guī)則。 v 1986年Mitchell等人提出了基于解釋學習的系統(tǒng)工作步驟：v 1產生解釋v系統(tǒng)得到實例后首先進行問題求解，由目標反向推理，從領域知識庫存中尋找有關規(guī)則，使基后件與目標匹配。找到這樣的規(guī)則后，就把目標作為后件，該規(guī)則作為前件，并記錄這一因果關系。然后以規(guī)則的前件作為子目標，進一步反復分解。如此

34、反復沿著因果鏈進行，直到求解結束。一旦得到解，便證明了該例的目標是可滿足的由此也得到證明的因果解釋結構。v v2對解釋結構的概括v對所得到的解釋結構以及事件進行概括，是采用將常量轉換為變量，去掉一些不重要的信息，僅保留求解所心需的那些關鍵信息，再由組合形成產生式規(guī)則，從而獲得概括性的控制信息。vMitchell等人綜合了以前各種基于解釋的概括方法，提出了一個般化，獨立具體領域的基于解釋的學習方法基于解釋的概括（EXPlanation-Bosed Generalization，簡稱EBG） v 給定：v 目標概念：對于所學概念的一個初始描述（其尚不滿足可操作準則）；v 訓練例子：目標概念的一個正

35、例；v 領域理論：解釋訓練例子為何是目標概念正例時可用的規(guī)則和事實集合；v 可操作準則：學到的知識（對于目標概念的解釋）所需遵從的表示形式，以使這些知識能用于問題求解活動。 v 獲取：v對于目標概念的一個特化描述，其是訓練例子的泛化，且滿足可操作準則。v基于解釋的概括過程有二個階段：v (1) 解釋：使用領域理論建立一個證明訓練例子滿足目標概念定義（初始描述）的解釋結構；該結構可表示為一顆證明推理樹，又稱解釋樹，其每個分枝的葉節(jié)點上的表達式都必須滿足可操作準則。v (2) 泛化：通過將解釋結構中的常量變換為變量（實現(xiàn)對于訓練例子的泛化），獲得對于目標概念的一個特化描述，使其滿足可操作準則：v

36、* 基于解釋結構對目標概念進行回歸(regressing)， v * 對回歸所得的表達式（相應于解釋結構中的葉節(jié)點）加以合取 6.3.2基于解釋學習的方法的舉例 v1問題的邏輯描述v2. 產生解釋結構 v3. 概括 6.4基于案例的推理v基于案例的推理（case-based reasoning，CBR）同人類的日常推理活動十分接近，它來自于人類的認知心理活動不同于傳統(tǒng)的基于知識系統(tǒng)，CBR系統(tǒng)所信賴的知識主要是系統(tǒng)所存儲的相關領域中以前解決問題的具體記錄。 v1.CBR系統(tǒng)的特點v羅杰沙克（Roger Schank）是CBR研究的開創(chuàng)者，沙克（Schank）指出，CBR方法研究的原始動機，主要

37、來源于對人類推理活動中“回憶”的重要地位的認識 v傳統(tǒng)的基于知識系統(tǒng)（主要指知識表示采用產生式規(guī)則或框架架或語義網絡的專家系統(tǒng)，ES）存在一定的困難，如：v知識獲取的瓶頸問題v知識庫維護的困難v推理鏈不能太長v固定的求解范圍 vCBR方法在以下方面對基于規(guī)則的系統(tǒng)做出了改進：v以下討論都假定非CBR知識系統(tǒng)的知識表示都采用產生式規(guī)則。1.知識獲取2.知識庫維護3.解決問題的范圍5.解質量4.求解過程 v2.CBR系統(tǒng)的體系結構v一個CBR推理和學習過程可以分解為下面四個步驟：vstep1.從案例庫中檢索出與新案例最相似的案例或案例集；vstep2.把step1獲得的案例（或案例集）中的信息和知

38、識復用到新問題上；vstep3.修正所建議的解答；vstep4.把該次獲得的經驗保存起來，以備將來來使用。 6.4.3學習方法v基于案例的推理通過下面幾種方法來完成它的大部分學習：v新案例的積累。保存成功的和失敗的新案例。 v建立、修改和撤消指向案例的索引路徑，完善索引機制。 v歸納學習。 vCBR方法的實現(xiàn)一般包含下面幾個主要步聚：案例表示，索引和存儲，檢索，適應修改，評估和學習等。v(1)案例表示v基于案例的推理系統(tǒng)利用案例記錄以前的問題求解的情況，應該包括與問題的解答有關的一切重要信息。v從問題求解角度來看，案例應包含對問題整體情況的描述，還應包含對問題的解或解決方法的描述。所以案例可被

39、表成一個有序對：。 v（2）索引v案例庫的索引（indexing）的目標是提供一種案例庫的搜索機制，使得在將來的檢索中能夠快速找出符合需要的案例或案例集。v一個案例的索引就是這個案例的重要關鍵字的集合，這些關鍵字可以將這個案例同其他案例區(qū)分開來 v索引問題的主要任務包括：選擇什么類型的索引、如何定義索引詞匯表、如何構建索引的搜索空間等。 v(3)案例檢索v檢索任務開始于一個描述待求問題的新案例，利用案例庫索引機制，根據相似性度量方法，在某種相似性程度閾值下，從案例庫中找出一組與新案例匹配較好的舊案例，并從中選擇出一個最佳的案例。v檢索任務的子任務包括：特性鑒別（indentify featur

40、e），初始匹配（initially match），搜(search)和選擇(select)。 v(4)相似性度量v相似性度量（similarity measure）在CBR系統(tǒng)中十分重要，合適的度量方法可以迅速、準確地找到所需要的案例。vCBR系統(tǒng)的相似性度量方法主要使用基于距離（基于計算）的方法，考慮到具體應用環(huán)境的特點擴展了的相似性度量方法和最近鄰法（NNh,the nearest neighbor method）。 v(5)適應性修改v適應性修改可以被簡單地理解為把解決文案的一部分用其他的內容替換，或者修改整個解決方案。適應性修改可以有幾種形式苛以直接向解決方案中插入一些新內容，也呆以從

41、解決方案中刪除一些內容，可以替換解決方案的某一部分內容，也可以將某一部分內容改造。但是，要使CBR系統(tǒng)得到足夠的適應性修改知識(Adaptation knowledge)是一件十分困難的任務。 v科洛德（Kolodner）提出了十種適應性修改的方法。v .重新例化v .參數調整v .局部搜索v詢問/查詢記憶（v .特殊化搜索v .基于案例的替換v .常識轉化v .模型制導的修改補v .特定目的的修改和修補 v .推導重放上述的1至6屬替換方法，7和8屬于轉化方法 v(6)評估和學習v評估任務需要在現(xiàn)實環(huán)境中應用該案例解答的結果，可以通過詢問專家或在現(xiàn)實世界中具體執(zhí)行任務來實現(xiàn)。這通常是CBR系

42、統(tǒng)外部的一個步驟。根據應用的類型，評估結果可能需要一段時間。當某案例的評估結果沒有得出時，該案例應標記為未評估案例。v學習過程把新案例中有意義的部分保存到系統(tǒng)的知識庫中。它包括從案例中選擇哪種信息進行保存，以什么形式保存，為新案例建立哪些索引，如何建立這些索引，如何存儲新案例等等。 v 4. 結論v基于案例的推理是人工智能領域中較新出現(xiàn)的一種重要的基于知識的問題求解和學習方法。作為一種基于經驗的問題求解技術，基于案例的推理（CBR）可以理解為修改舊的解決方案滿足新的需要；使用舊案例解釋新情況、評價新方案、構造新問題的解答。學習是CBR推理行為的副產品，它獲得過去的經驗并在以后的推理中能夠回憶起

43、來，這樣它的推理能力和效率都能得到提高。v基于案例的推理系統(tǒng)的推理質量取決它具有的經驗，即在那些舊經驗的基礎上理解新情況的能力、修改的能力、以及評價和改錯的能力?；诎咐耐评沓绦虻闹饕^程是案例存儲、檢索、修改及審查。 6.5加強學習v加強學習是一種以環(huán)境反饋作為輸入的、特殊的、適應環(huán)境的機器學習方法。所謂加強學習是指從環(huán)境狀態(tài)到行為映射的學習，以使系統(tǒng)行為從環(huán)境中獲得的累積獎賞值最大。 v加強學習通常包括兩個方面的含義：一方面是將加強學習作為一類問題；另一方面是指解決這類問題的一種技術。v加強學習（reinforcement learning）又稱再勵學習或評價學習，是一種重要的機器學習方

44、法，在智能控制機器人及分析預測等領域有許多應用。 6.5.1加強學習基本方法v在加強學習技術中首先對隨機的、離散狀態(tài)、離散時間這一類問題進行數學建模。在實際應用中，最常采用的是馬爾可夫模型。表2中給出最常用的幾種馬氏模型。 v表2 常用的幾種馬氏模型 是否智能系統(tǒng)行為控制環(huán)境狀態(tài)轉移？ 馬氏模型 否 是 否 馬爾可夫鏈 馬氏決策過程 是否環(huán)境為部 分可感知？ 是 隱馬爾可夫模型 部分感知馬氏決策過程 v下面給出馬氏決策過程（Markov Decision Process，MDP）建模的形式化定義：v馬氏決策過程 由四元組定義。包含一個環(huán)境狀態(tài)集S，系統(tǒng)行為集合A，獎賞函數R：SA和狀態(tài)轉移函數

45、P：SAPD（S）。記R（s，a，s）為系統(tǒng)在狀態(tài)s采用a動作使環(huán)境狀態(tài)轉移到s獲得的瞬時獎賞值；記P（s，a，s）為系統(tǒng)在狀態(tài)s采用a動作使環(huán)境狀態(tài)轉移到s的概率。 v馬氏決策過程的本質是：當前狀態(tài)向下一狀態(tài)轉移的概率和獎賞值只取決于當前狀態(tài)和選擇的動作，而與歷史狀態(tài)和歷史動作無關。因此在已知狀態(tài)轉移概率函數P和獎賞函數R的()環(huán)境模型知識下，可以采用動態(tài)規(guī)劃技術求解最優(yōu)策略。而加強學習著重研究在P函數和R函數未知的情況下，系統(tǒng)如何學習最優(yōu)行為策略。加強學習可以簡化為圖6-13的結構。 v圖6-13 加強學習結構 6.5.2加強學習技術目前主要研究方向v 1部分感知馬氏決策過程中的強化學習v

46、在實際的問題中，系統(tǒng)往往無法完全感知環(huán)境狀態(tài)信息。即使環(huán)境屬于馬爾可夫型，但由于感知的不全面，對于狀態(tài)之間的差異也無法區(qū)別。因此部分感知問題屬于非馬爾可夫型環(huán)境。在部分感知問題中，如果不對強化學習算法進行任何處理就加以應用的話，學習算法將無法收斂。v在部分感知模型中，不僅考慮動作的不確定性，同時也考慮狀態(tài)的不確定性。這種環(huán)境描述更接近現(xiàn)實世界，因此應用面比馬氏決策模型更廣。解決部分感知問題的基本思路是將部分感知環(huán)境轉換為馬氏決策模型描述，即假設存在部分可觀測（或不可觀測）的隱狀態(tài)集S滿足馬爾可夫屬性。 v2加強學習中的函數估計v對于大規(guī)模MDP或連續(xù)空間MDP問題中，加強學習不可能遍歷所有狀態(tài)

47、。因此要求加強學習的值函數具有一定泛化能力。加強學習中的映射關系包括：SA、SR、SAR、SAS等等。加強學習中的函數估計本質就是用參數化的函數逼近這些映射。 v3分層加強學習v經典馬氏決策過程模型只考慮了決策的順序性而忽略決策的時間性?；隈R氏決策過程的加強學習都假設動作在單個時間步完成，因而無法處理需要在多個時間步完成的動作。為解決此問題，引入半馬氏決策過程（SMDP，Semi-MDP）模型。在SMDP模型中，每個行為動作的時間間隔作為變量（整數或實數），并進一步可以細分為連續(xù)時間-離散事件SMDP和離散時間SMDP兩種模型。在后者中，行為決策只在單位時間片的正整數倍做出，較前者模型簡單。

48、 v4 多agent加強學習v多agent加強學習是加強學習研究中非常重要的研究方向之一。在多agent系統(tǒng)中，環(huán)境在多個agent的聯(lián)合動作下進行狀態(tài)的遷移。對于單個agent來講，由于其只能確定自身agent的行為動作，因此體現(xiàn)出一種行為動作上的“部分感知”，從而產生出另一種形式的非標準馬爾可夫環(huán)境。多agent加強學習機制被廣泛應用到各個領域，例如游戲、郵件路由選擇、電梯群控系統(tǒng)以及機器人設計等等。 6.5.3結論v本部分綜述了加強學習技術基本原理和目前主要研究方向。盡管在過去的二十年中，加強學習技術研究取得了突破性進展，但目前仍然存在許多有待解決的問題。在今后的若干年中，以下方面也將成

49、為強化學習研究的重要研究內容。 1.加強學習與其他學習技術相結合的研究 v眾所周知，加強學習的一個主要缺點是收斂慢。其根本原因在于學習過程僅僅從經驗獲得的獎賞中進行策略的改進，而忽略了大量其他有用的領域信息。因此，如何結合其他機器學習技術，如神經網絡、符號學習等技術，來幫助系統(tǒng)加快學習速度是強化學習研究和應用的重要方向。目前，結合技術研究的主要難點在于：如何從理論上證明和保證學習算法的收斂性。 v2.非馬氏決策過程中的新型加強學習算法研究 v經典的馬氏決策模型是相當簡單的，除了部分感知、連續(xù)狀態(tài)、半馬氏決策過程等模型外，在實際應用中還存在大量更加復雜的模型。例如，在圖象的馬爾可夫隨機場模型中，狀態(tài)的遷移是由歷史多個相鄰狀態(tài)決定。因此，在更復雜馬氏決策模型中發(fā)展有效的加強學習算法也將是未來重要的研究方向之一。 v3.加強學習應用研究v目前，加強學習的應用主要可以分為四類：制造過程控制、各種任務調度、機器人設計和游戲。另外，加強學習在學習分類器（Learning Classifier System）中的應用也逐漸成為研究的熱點。從當前看來，加強學習的應用逐步向一些新的機器學習任務上拓展，如Web Log Mining、Web Crawling、Classification等等。因此，如何在新應用上快速、有效地部署和應用加強學習技術也是放在研究人員面前的挑戰(zhàn)之一。