1、目錄,第一章緒論 第二章知識表示 第三章搜索技術(shù) 第四章推理技術(shù) 第五章機(jī)器學(xué)習(xí) 第六章專家系統(tǒng) 第七章自動規(guī)劃系統(tǒng) 第八章 自然語言理解 第九章 智能控制 第十章 人工智能程序設(shè)計,5.1 機(jī)器學(xué)習(xí)概述,學(xué)習(xí)的基本概念 學(xué)習(xí)是人類具有的一種重要的智能行為。 西蒙的觀點：學(xué)習(xí)就是系統(tǒng)在不斷重復(fù)的工作中對本身能力的增強或者改進(jìn)，使得系統(tǒng)在下一次執(zhí)行同樣任務(wù)或類似任務(wù)時，會比現(xiàn)在做得更好或效率更高。 1959年 Samuel 下棋程序，具有學(xué)習(xí)能力。4年后程序戰(zhàn)勝了設(shè)計者，又3年后戰(zhàn)勝了美國一個冠軍。,5.1 機(jī)器學(xué)習(xí)概述,機(jī)器學(xué)習(xí)的定義 機(jī)器學(xué)習(xí)是研究如何使用機(jī)器來模擬人類學(xué)習(xí)活動的一門學(xué)科。稍

2、為嚴(yán)格的提法是：機(jī)器學(xué)習(xí)是一門研究機(jī)器獲取新知識和新技能，并識別現(xiàn)有知識的學(xué)問。,5.1 機(jī)器學(xué)習(xí)概述,機(jī)器學(xué)習(xí)的發(fā)展 機(jī)器學(xué)習(xí)是人工智能應(yīng)用研究較為重要的分支，它的發(fā)展過程大體上可分為4個時期： （1）第一階段是在50年代中葉到60年代中葉，屬于熱烈時期。在這個時期，所研究的是“沒有知識”的學(xué)習(xí)，即“無知”學(xué)習(xí)；其研究目標(biāo)是各類自組織系統(tǒng)和自適應(yīng)系統(tǒng)；指導(dǎo)本階段研究的理論基礎(chǔ)是早在40年代就開始研究的神經(jīng)網(wǎng)絡(luò)模型。,5.1 機(jī)器學(xué)習(xí)概述,（2）第二階段在60年代中葉至70年代中葉，被稱為機(jī)器學(xué)習(xí)的冷靜時期。本階段的研究目標(biāo)是模擬人類的概念學(xué)習(xí)過程，并采用邏輯結(jié)構(gòu)或圖結(jié)構(gòu)作為機(jī)器內(nèi)部描述。 （

3、3）第三階段從70年代中葉至80年代中葉，稱為復(fù)興時期。在這個時期，人們從學(xué)習(xí)單個概念擴(kuò)展到學(xué)習(xí)多個概念，探索不同的學(xué)習(xí)策略和各種學(xué)習(xí)方法。本階段已開始把學(xué)習(xí)系統(tǒng)與各種應(yīng)用結(jié)合起來。 （4）機(jī)器學(xué)習(xí)的最新階段始于1986年。一方面，由于神經(jīng)網(wǎng)絡(luò)研究的重新興起，另一方面，對實驗研究和應(yīng)用研究得到前所未有的重視。,5.1 機(jī)器學(xué)習(xí)概述,機(jī)器學(xué)習(xí)研究與應(yīng)用的發(fā)展趨勢 （1） 從有教師指導(dǎo)的歸納學(xué)習(xí)向無教師指導(dǎo)的發(fā)現(xiàn)學(xué)習(xí)轉(zhuǎn)變。以數(shù)據(jù)挖掘為核心技術(shù)的發(fā)現(xiàn)學(xué)習(xí)成為最有價值的機(jī)器學(xué)習(xí)技術(shù)。 （2） 從面向確定性環(huán)境的觀察學(xué)習(xí)到面向不確定性環(huán)境的統(tǒng)計學(xué)習(xí)轉(zhuǎn)變。概率理論和統(tǒng)計分析處理不確定問題。 （3） 從缺乏

4、堅實理論的經(jīng)驗性學(xué)習(xí)到具有嚴(yán)密數(shù)學(xué)基礎(chǔ)的學(xué)習(xí)理論轉(zhuǎn)變。粗糙集和統(tǒng)計學(xué)習(xí)理論。,5.2 機(jī)器學(xué)習(xí)的主要策略和基本結(jié)構(gòu),機(jī)器學(xué)習(xí)的主要策略 學(xué)習(xí)過程與推理過程是緊密相連的，按照學(xué)習(xí)中使用推理的多少，機(jī)器學(xué)習(xí)所采用的策略大體上可分為4種：機(jī)械學(xué)習(xí)、示教學(xué)習(xí)、類比學(xué)習(xí)和示例學(xué)習(xí)。學(xué)習(xí)中所用的推理越多，系統(tǒng)的能力越強。 （1）機(jī)械學(xué)習(xí)就是記憶，是最簡單的學(xué)習(xí)策略。這種學(xué)習(xí)策略不需要任何推理過程。 （2）比機(jī)械學(xué)習(xí)更復(fù)雜一點的學(xué)習(xí)是示教學(xué)習(xí)策略。系統(tǒng)在接受外部知識時需要一點推理，翻譯和轉(zhuǎn)化工作。,5.2 機(jī)器學(xué)習(xí)的主要策略和基本結(jié)構(gòu),（3）類比學(xué)習(xí)系統(tǒng)只能得到完成類似任務(wù)的有關(guān)因此，他比上述兩種學(xué)習(xí)策略需

5、要更多的推理。 （4）采用示例學(xué)習(xí)策略的計算機(jī)系統(tǒng)，事先完全沒有完成任務(wù)的任何規(guī)律性的信息，因此需要推理是最多的。,5.2 機(jī)器學(xué)習(xí)的主要策略和基本結(jié)構(gòu),機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu) 環(huán)境向系統(tǒng)的學(xué)習(xí)部分提供某些信息，學(xué)習(xí)部分利用這些信息修改知識庫，以增進(jìn)系統(tǒng)執(zhí)行部分完成任務(wù)的效能，執(zhí)行部分根據(jù)知識庫完成任務(wù)，同時把獲得的信息反饋給學(xué)習(xí)部分。在具體的應(yīng)用中，環(huán)境，知識庫和執(zhí)行部分決定了具體的工作內(nèi)容，學(xué)習(xí)部分所需要解決的問題完全由上述3部分確定。,環(huán)境,學(xué)習(xí),知識庫,執(zhí)行,5.2 機(jī)器學(xué)習(xí)的主要策略和基本結(jié)構(gòu),影響學(xué)習(xí)系統(tǒng)設(shè)計的重要因素 （1）影響學(xué)習(xí)系統(tǒng)設(shè)計的最重要的因素是環(huán)境向系統(tǒng)提供的信息。整

6、個過程要遵循“取之精華，棄之糟粕”的原則，同時謹(jǐn)記“實踐是檢驗真理的唯一標(biāo)準(zhǔn)”。 （2）知識庫是影響學(xué)習(xí)系統(tǒng)設(shè)計的第二個因素。知識的表示有多種形式，在選擇表示方式時要兼顧以下4個方面： 表達(dá)能力強。所選擇的表示方式能很容易地表達(dá)有關(guān)的知識。 易于推理。為了使學(xué)習(xí)系統(tǒng)的計算代價比較低，希望知識表示方式能使推理較為容易。,5.2 機(jī)器學(xué)習(xí)的主要策略和基本結(jié)構(gòu),容易修改知識庫。學(xué)習(xí)系統(tǒng)的本質(zhì)要求它不斷地修改自己的知識庫，當(dāng)推廣得出一般執(zhí)行規(guī)則后，要加到知識庫中。 知識表示易于擴(kuò)展。 學(xué)習(xí)系統(tǒng)不能在全然沒有任何知識的情況下憑空獲取知識，每一個學(xué)習(xí)系統(tǒng)都要求具有某些知識理解環(huán)境提供的信息，分析比較，做出

7、假設(shè)，檢驗并修改這些假設(shè)。因此，更確切地說，學(xué)習(xí)系統(tǒng)是對現(xiàn)有知識的擴(kuò)展和改進(jìn)。,5.3 常見的幾種學(xué)習(xí)方法,5.3.1 機(jī)械學(xué)習(xí) 1. 機(jī)械學(xué)習(xí)的模式 機(jī)械學(xué)習(xí)是最簡單的機(jī)器學(xué)習(xí)方法。機(jī)械學(xué)習(xí)就是記憶，即把新的知識存儲起來，供需要時檢索調(diào)用，而不需要計算和推理。機(jī)械學(xué)習(xí)又是最基本的學(xué)習(xí)過程。任何學(xué)習(xí)系統(tǒng)都必須記住它們獲取的知識。在機(jī)械學(xué)習(xí)系統(tǒng)中，知識的獲取是以較為穩(wěn)定和直接的方式進(jìn)行的，不需要系統(tǒng)進(jìn)行過多的加工。,5.3 常見的幾種學(xué)習(xí)方法,5.3.1 機(jī)械學(xué)習(xí) 2. 數(shù)據(jù)化簡 Lenat,Hayes Roth，和Klahr等人于1979年關(guān)于機(jī)械學(xué)習(xí)提出一種有趣的觀點。他們指出，可以把機(jī)械學(xué)

8、習(xí)看成是數(shù)據(jù)化簡分級中的第一級。數(shù)據(jù)化簡與計算機(jī)語言編譯類似；其目的是把原始信息變成可執(zhí)行的信息。在機(jī)械學(xué)習(xí)中我們只記憶計算的輸入輸出，忽略了計算過程，這樣就把計算問題化簡成存取問題。,5.3 常見的幾種學(xué)習(xí)方法,5.3.1 機(jī)械學(xué)習(xí),存儲,計算,推導(dǎo),歸納,算法與理論,機(jī)械記憶,搜索規(guī)則,5.3 常見的幾種學(xué)習(xí)方法,5.3.1 機(jī)械學(xué)習(xí) 3. 主要問題 對于機(jī)械學(xué)習(xí)，需要注意3個重要的問題：存儲組織，穩(wěn)定性和存儲與計算之間的權(quán)衡。 （1）存儲組織信息：采用適當(dāng)?shù)拇鎯Ψ绞?，使檢索速度盡可能地快，是機(jī)械學(xué)習(xí)中的重要問題。 （2）環(huán)境的穩(wěn)定性與存儲信息的適用性問題：機(jī)械學(xué)習(xí)系統(tǒng)必須保證所保存的信息

9、適應(yīng)于外界環(huán)境變化的需要，這也就是所謂的信息適用性問題。 （3）存儲與計算之間的權(quán)衡：對于機(jī)械學(xué)習(xí)來說很重要的一點是它不能降低系統(tǒng)的效率。,5.3 常見的幾種學(xué)習(xí)方法,5.3.2 基于解釋的學(xué)習(xí) 解釋學(xué)習(xí)（explanation 最初是由美國Illinois 大學(xué)的DeJong 于1983 年提出來的。在經(jīng)驗學(xué)習(xí)的基礎(chǔ)上，運用領(lǐng)域知識對單個例子的問題求解作出解釋，這是一種關(guān)于知識間因果關(guān)系的推理分析，可產(chǎn)生一般的控制策略。 解釋學(xué)習(xí)根據(jù)任務(wù)所在領(lǐng)域知識和正在學(xué)習(xí)的概念知識，對當(dāng)前實例進(jìn)行分析和求解，得出一個表征求解過程的因果解釋樹，以獲取新的知識。在獲取新的知識過程中，通過對屬性、表征現(xiàn)象和內(nèi)

10、在關(guān)系等進(jìn)行解釋而學(xué)習(xí)到新的知識。,5.3 常見的幾種學(xué)習(xí)方法,5.3.2 基于解釋的學(xué)習(xí) 解釋學(xué)習(xí)一般包括下列3個步驟： （1） 利用基于解釋的方法對訓(xùn)練例子進(jìn)行分析與解釋。 （2） 對例子的結(jié)構(gòu)進(jìn)行概括性解釋。 （3） 從解釋結(jié)構(gòu)中識別出訓(xùn)練例子的特性，獲取一般控制知識。 1986年Mitchell，Keller 和 Kedar-Cabelli等人為基于解釋的學(xué)習(xí)提出了一個統(tǒng)一的算法EBG(Explanation-Based Generalization)，該算法建立了基于解釋的概括過程，并運用知識的邏輯表示和演繹推理進(jìn)行問題求解。,5.3 常見的幾種學(xué)習(xí)方法,5.3.2 基于解釋的學(xué)習(xí),

11、操作規(guī)則,目標(biāo)概念,訓(xùn)練實例,新規(guī)則,領(lǐng)域知識,5.3 常見的幾種學(xué)習(xí)方法,5.3.2 基于解釋的學(xué)習(xí) EBG求解問題的形式可描述于下: 給定： (1) 目標(biāo)概念描述TC； (2) 訓(xùn)練實例TE； (3) 領(lǐng)域知識DT； (4) 操作準(zhǔn)則OC。 求解：訓(xùn)練實例的一般化概括，使之滿足： (1) 目標(biāo)概念的充分概括描述TC； (2) 操作準(zhǔn)則OC。,5.3 常見的幾種學(xué)習(xí)方法,5.3.2 基于解釋的學(xué)習(xí) 其中，領(lǐng)域知識DT是相關(guān)領(lǐng)域的實施和規(guī)則，在學(xué)習(xí)系統(tǒng)中作為背景知識，用于證明訓(xùn)練實例TE為什么可以作為目標(biāo)概念的一個實例，從而形成相應(yīng)的解釋。訓(xùn)練實例TE是為學(xué)習(xí)系統(tǒng)提供一個例子，在學(xué)習(xí)過程中起著

12、重要的作用，它應(yīng)能充分地說明目標(biāo)概念TC。操作規(guī)則OC用于指導(dǎo)學(xué)習(xí)系統(tǒng)對目標(biāo)概念進(jìn)行取舍，使得通過學(xué)習(xí)產(chǎn)生的關(guān)于目標(biāo)概念TC的一般性描述成為可用的一般性知識。 基于解釋的學(xué)習(xí)從本質(zhì)上說屬于演繹學(xué)習(xí)，它是根據(jù)給定的領(lǐng)域知識，進(jìn)行保真的演繹推理，存儲有用結(jié)論，經(jīng)過知識的求精和編輯，產(chǎn)生適合以后求解類似問題的控制知識。,5.3 常見的幾種學(xué)習(xí)方法,5.3.3 基于事例的學(xué)習(xí) 當(dāng)無法建立好的模型時，可通過記錄事例進(jìn)行學(xué)習(xí)。 采用基于事例的學(xué)習(xí)：首先，任何時候都可以應(yīng)用相容啟發(fā)方法，把某個預(yù)先觀察過的事物的特性賦予一個從未見過的新事物；其次，學(xué)會如何用于k維樹結(jié)構(gòu)迅速找到特征空間內(nèi)的最近鄰物體。 相容啟

13、發(fā)：無論何時要猜測某事物的特性，除了提供一套參考事例外不知道其他情況；通過測量其他事物的已知特性，找到最相近的事例，該事例的特性特性是已知的。作為猜測：所求未知特性是與最相似事例的已知特性一樣的。,5.3 常見的幾種學(xué)習(xí)方法,5.3.3 基于概念的學(xué)習(xí) 歸納學(xué)習(xí)的定義 （1）歸納（induction）是人類拓展認(rèn)識能力的重要方法，是一種從個別到一般的，從部分到整體的推理行為。 （2）歸納推理是應(yīng)用歸納方法，從足夠多的具體事例中歸納出一般性知識，提取事物的一般規(guī)律；它是一種從個別到一般的推理。 （3）歸納學(xué)習(xí)（induction learning）是應(yīng)用歸納推理進(jìn)行學(xué)習(xí)的一種方法。 從應(yīng)用角度看

14、，歸納學(xué)習(xí)可分為概念學(xué)習(xí)、概念聚集和啟發(fā)學(xué)習(xí)三種。,5.3 常見的幾種學(xué)習(xí)方法,5.3.3 基于概念的學(xué)習(xí) 概念學(xué)習(xí)研究的路線： （1）基于工程方法的概念學(xué)習(xí)，它從可能的學(xué)習(xí)機(jī)理出發(fā)，試圖試驗并確定概念學(xué)習(xí)的工程方法。 （2）基于認(rèn)知建模的概念學(xué)習(xí)，開發(fā)出人類概念學(xué)習(xí)的計算理論。 概念學(xué)習(xí)的任務(wù)：構(gòu)造類型定義、分類程序（分類）,5.3 常見的幾種學(xué)習(xí)方法,5.3.5 基于類比的學(xué)習(xí) 1. 類比推理和類比學(xué)習(xí)形式 類比推理是由新情況與已知情況在某些方面的相似來推出它們在其它相關(guān)方面的相似。顯然，類比推理是在兩個相似域之間進(jìn)行的：類比推理的目的是從源域中選出與當(dāng)前問題最近似的問題及其求解方法以求解

15、決當(dāng)前的問題，或者建立起目標(biāo)域中已有命題間的聯(lián)系，形成新知識。,5.3 常見的幾種學(xué)習(xí)方法,5.3.5 基于類比的學(xué)習(xí) 類比推理過程如下： (1) 回憶與聯(lián)想 遇到新情況或新問題時，首先通過回憶與聯(lián)想在S中找出與當(dāng)前情況相似的情況，這些情況是過去已經(jīng)處理過的，有現(xiàn)成的解決方法及相關(guān)的知識。 (2) 選擇 從找出的相似情況中選出與當(dāng)前情況最相似的情況及其有關(guān)知識。,5.3 常見的幾種學(xué)習(xí)方法,5.3.5 基于類比的學(xué)習(xí) (3) 建立對應(yīng)映射 在S與T的相似情況之間建立相似元素的對應(yīng)關(guān)系，并建立起相應(yīng)的映射。 (4) 轉(zhuǎn)換 在上一步建立的映射下，把S中的有關(guān)知識引到T中來，從而建立起求解當(dāng)前問題的

16、方法或者學(xué)習(xí)到關(guān)于T的新知識。,5.3 常見的幾種學(xué)習(xí)方法,5.3.5 基于類比的學(xué)習(xí) 2. 類比學(xué)習(xí)過程與研究類型 類比學(xué)習(xí)主要包括如下四個過程： (1) 輸入一組已知條件（已解決問題）和一組未完全確定的條件（新問題）。 (2) 對輸入的兩組條件，根據(jù)其描述，按某種相似性的定義尋找兩者可類比的對應(yīng)關(guān)系。,5.3 常見的幾種學(xué)習(xí)方法,5.3.5 基于類比的學(xué)習(xí) 2. 類比學(xué)習(xí)過程與研究類型 (3) 按相似變換的方法，將已有問題的概念、特性、方法、關(guān)系等映射到新問題上，以獲得待求解新問題所需的新知識。 (4) 對類推得到的新問題的知識進(jìn)行校驗。驗證正確的知識存入知識庫中，而暫時還無法驗證的知識只

17、能作為參考性知識，置于數(shù)據(jù)庫中。,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 1. 決策樹的概念 決策樹算法起源于概念學(xué)習(xí)系統(tǒng)(CLS: Concept Learning System)，是一種有指導(dǎo)的學(xué)習(xí)方法。決策樹分類算法以其易于提取顯示規(guī)則、計算量相對較小、具有較高的分類準(zhǔn)確率等優(yōu)點被統(tǒng)計學(xué)界接受并獲得了信賴，并很快被廣泛應(yīng)用于許多領(lǐng)域。決策樹技術(shù)在許多數(shù)據(jù)挖掘系統(tǒng)應(yīng)用中得到研究者和軟件公司的極大關(guān)注。 許多數(shù)據(jù)挖掘產(chǎn)品中都采用了決策樹算法，例如：SAS公司的SAS Enterprise Miner；IBM公司的Intelligent Miner；Solution公司的

18、Clementine；微軟的SQL Server。,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 最為典型的決策樹學(xué)習(xí)算法是由J.Ross Quinlan1979年提出的ID3算法。ID3（Iterative Dichotomiser，迭代的二分器)算法是一種基于信息熵的決策樹算法，以Shannon的信息論為依據(jù)。 ID3改進(jìn)、優(yōu)化： C4.5算法：1993年，Quinlan出版了專著機(jī)器學(xué)習(xí)規(guī)劃對C4.5算法進(jìn)行詳細(xì)描述。 CART(Classification and Regression Tree)算法：描述了二叉決策樹的產(chǎn)生，可對連續(xù)型因變量進(jìn)行處理。,5.3 常見的幾

19、種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 決策樹（又稱判定樹 decision tree)是一種樹結(jié)構(gòu)，其節(jié)點分為兩類：一類是內(nèi)節(jié)點，另一類是葉節(jié)點。 內(nèi)節(jié)點：一般用一個屬性名來標(biāo)記，代表對該屬性的測試。與內(nèi)節(jié)點連接的邊表示對該屬性測試的輸出。 葉節(jié)點：每個葉節(jié)點表示分類結(jié)果，一般用類標(biāo)號屬性值來標(biāo)記。,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí),Male?,grade,grade,class1,class2,class3,class2,yes,no,60,60,60,60,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 如何構(gòu)造一顆具有較高分類準(zhǔn)確率的決策

20、樹？ 關(guān)鍵：如何確定當(dāng)前要以哪個屬性作為測試屬性？ 1948 年Shannon 提出并發(fā)展了信息論，研究以數(shù)學(xué)的方法度量并研究信息。通過通信后對信源中各種符號出現(xiàn)的不確定程度的消除來度量信息量的大小。 （1）自信息量 設(shè)系統(tǒng)S中有多個可能發(fā)生的事件：a1,a2,an， 事件ai發(fā)生的概率為p(ai), i=1,2,n，p(ai) 0,1 p(ai)越大，事件ai不確定程度越低，反之，則越高。,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 用-log p(ai)表示事件ai的不確定程度，稱為ai的自信息量I(ai) I(ai)=- -log p(ai) /log以2為底 （2）信

21、息熵（entropy） 如果將S看作一個信源， a1,a2,an看成信源S發(fā)出的n種類型的信息，則信源S的不確定性可以用平均自信息量來度量，記為H(S)，定義：,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 2. 決策樹的學(xué)習(xí) 決策樹學(xué)習(xí)的過程是從空樹開始，從訓(xùn)練集中不斷選擇測試屬性，逐步創(chuàng)建決策樹的過程。 設(shè)X為訓(xùn)練集，分為m類，第i類中的訓(xùn)練實例集合記為Ci ，i=1,2,m，那么X中任意一個實例屬于類Ci的概率估計值為： p(Ci)=|Ci|/|X| 其中|X|表示集合X中的元素個數(shù)。 訓(xùn)練集X關(guān)于類簇C=C1, C2, , Cm的分類不確定性可用西面信息熵來度量：,5.

22、3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 在C已知的情況下（訓(xùn)練集中已確定），H(X,C)簡寫為H(X)。 構(gòu)造決策樹的目的：將訓(xùn)練集X的不確定程度H(X)降至最低。從而可以對未知數(shù)據(jù)（X集以外的數(shù)據(jù)）進(jìn)行分類預(yù)測。 構(gòu)造決策樹的過程是從空樹開始不斷添加節(jié)點的過程，關(guān)鍵是選擇測試屬性，使得構(gòu)造起來的“半”決策樹最大限度減低訓(xùn)練集X的信息熵H(X)。,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí),5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 設(shè)A=a1, a2, , ar為候選的測試屬性，那么屬性A對X形成一個劃分a1, a2, , ar，其中ai

23、表示X中在屬性A上取值為ai的實例集合，i=1, 2, , r。 現(xiàn)對任意i1, 2, , r，考慮類ai。令 則 形成ai的一個劃分， 于是類ai關(guān)于類簇 的分類不確定性程度為：,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 其中， 表示類ai中任意一個實例屬于 的概率， 令 稱E(A)為由屬性A劃分成子集的信息熵。,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 當(dāng)選擇A作為測試屬性時，導(dǎo)致訓(xùn)練集X的信息熵的壓縮量為 H(X, C)-E(A) 該壓縮量成為信息增益（information gain），記為gain(A) gain(A)=H(X, C)-E(A)

24、 構(gòu)造決策樹時，選擇當(dāng)前具有最大信息增益的屬性作為當(dāng)前節(jié)點的測試屬性，這使得X的信息熵下降最快，構(gòu)造的決策樹高度也相對較低。,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 示例： （1）創(chuàng)建根節(jié)點 先計算gain(color)。 inflated為類標(biāo)號屬性，對X的劃分為 C=T, F=1,2,3,4,5,7,8,10, 3,6,9=C1, C2 其中 C1 =1,2,3,4,5,7,8,10=T C2 =3,6,9=F,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) H(X,C)=-p(C1)logp(C1)- p(C2)logp(C2),5.3 常見的幾種學(xué)習(xí)

25、方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 屬性color對X形成的劃分為 1, 2, 3, 4, 5, 6, 7, 8, 9, 10=YELLOW, PURPLE 其中 YELLOW=1, 2, 3, 4, 5, 6, PURPLE= 7, 8, 9, 10 于是 = YELLOW C1= 1,2,3,4,5,6 1,2,4,5,7,8,10 =1, 2, 4, 5 = YELLOW C2= 1,2,3,4,5,6 3,6,9 =3, 6,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) = PURPLE C1= 7,8,9,10 1,2,4,5,7,8,10 =7,8,10 = P

26、URPLE C2= 7,8,9,10 3,6,9 =9,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 這樣 gain(color)=H(X,C)-E(color)=0.88-0.88=0 同樣的方法，可得 gain(size)=0 gain(act)=0.88 gain(age)=0.28 act具有最高信息增益，選為根節(jié)點。,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí),act,DIP,STRETCH,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) （2）創(chuàng)建子節(jié)點 左邊的表類標(biāo)號屬性 均為T，故創(chuàng)建葉節(jié)點。 右邊的表，作為新 數(shù)據(jù)集，依據(jù)步驟（

27、1）， 計算信息增益，選擇測試屬性， 構(gòu)造內(nèi)節(jié)點，直到得到一顆完整 的決策樹。,act,T,age,F,T,DIP,STRECH,ADULT,CHILD,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 決策樹剪枝 噪聲數(shù)據(jù)和獨立（異常)點造成產(chǎn)生的分枝異常， 過少的實例失去了統(tǒng)計意義，分枝不具代表性。 剪枝：減少異常分枝出現(xiàn)。 先剪枝技術(shù)：提前終止決策樹的“生長” 后剪枝技術(shù)：對創(chuàng)建完畢的決策樹進(jìn)行剪枝，剪去“畸形發(fā)展”的分枝。,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 3. 從決策樹提取分類規(guī)則 決策樹：分類規(guī)則集 act=STRETCHinflated=T

28、 act=DIPage=CHILD inflated=F act=DIPage=ADULT inflated=T,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 4. 決策樹學(xué)習(xí)適用的問題 實例是由“屬性-值”對表示的 目標(biāo)函數(shù)具有離散的輸出值（如布爾型） 需要析取得描述（決策樹本身代表析取表達(dá)式） 訓(xùn)練數(shù)據(jù)可以包含錯誤 訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實例,5.3 常見的幾種學(xué)習(xí)方法,5.3.6 基于決策樹的歸納學(xué)習(xí) 5. 決策樹學(xué)習(xí)的問題 過度擬合（運用剪枝技術(shù)） 連續(xù)值屬性（連續(xù)值域分割為離散區(qū)間集合） 屬性選擇度量（信息增益偏袒具有較多值的屬性）,5.3 常見的幾種學(xué)習(xí)方法,

29、5.3.7 強化學(xué)習(xí) 1. 強化學(xué)習(xí)的概念 強化學(xué)習(xí)（reinforcement learning）：智能系統(tǒng)從環(huán)境到行為映射的學(xué)習(xí)，以使獎勵信號（強化信號）函數(shù)值最大。 連接主義的學(xué)習(xí)分類： 監(jiān)督學(xué)習(xí)（supervised learning) 無監(jiān)督學(xué)習(xí)（unsupervised learning） 強化學(xué)習(xí),5.3 常見的幾種學(xué)習(xí)方法,5.3.7 強化學(xué)習(xí) 強化學(xué)習(xí)中由環(huán)境提供的強化信號對智能體（Agent）產(chǎn)生動作的好壞做一種評價，而不是直接告訴智能體要做什么或者要采取哪個動作,而是智能體通過看哪個動作得到了最多的獎勵來自己發(fā)現(xiàn)。智能體的動作的影響不只是立即得到的獎勵，而且還影響接下來的

30、動作和最終的獎勵。 試錯搜索(trial-and-error search)和延期強化(delayed reinforcement)這兩個特性是強化學(xué)習(xí)中兩個最重要的特性。,5.3 常見的幾種學(xué)習(xí)方法,5.3.7 強化學(xué)習(xí) 2. 強化學(xué)習(xí)的基本模型和原理 強化學(xué)習(xí)技術(shù)是從控制理論、統(tǒng)計學(xué)、心理學(xué)等相關(guān)學(xué)科發(fā)展而來，最早可以追溯到巴甫洛夫的條件反射實驗。但直到上世紀(jì)八十年代末、九十年代初強化學(xué)習(xí)技術(shù)才在人工智能、機(jī)器學(xué)習(xí)和自動控制等領(lǐng)域中得到廣泛研究和應(yīng)用，并被認(rèn)為是設(shè)計智能系統(tǒng)的核心技術(shù)之一。特別是隨著強化學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)研究取得突破性進(jìn)展后，對強化學(xué)習(xí)的研究和應(yīng)用日益開展起來，成為目前機(jī)器學(xué)習(xí)

31、領(lǐng)域的研究熱點之一。,5.3 常見的幾種學(xué)習(xí)方法,5.3.7 強化學(xué)習(xí) 基本模型：,Agent,環(huán)境,狀態(tài) s,獎勵 r,動作 a,5.3 常見的幾種學(xué)習(xí)方法,5.3.7 強化學(xué)習(xí) 強化學(xué)習(xí)系統(tǒng)接受環(huán)境狀態(tài)的輸入s，根據(jù)內(nèi)部的推理機(jī)制，系統(tǒng)輸出相應(yīng)的行為動作a。環(huán)境在系統(tǒng)動作作用a 下，變遷到新的狀態(tài)s。系統(tǒng)接受環(huán)境新狀態(tài)的輸入，同時得到環(huán)境對于系統(tǒng)的瞬時獎懲反饋r。對于強化學(xué)習(xí)系統(tǒng)來講，其目標(biāo)是學(xué)一個行為策略：SA，使系統(tǒng)選擇的動作能夠獲得環(huán)境獎勵的累計值最大。 在學(xué)習(xí)過程中，強化學(xué)習(xí)技術(shù)的基本原理是：如果系統(tǒng)某個動作導(dǎo)致環(huán)境正的獎勵，那么系統(tǒng)以后產(chǎn)生這個動作的趨勢便會加強。反之系統(tǒng)產(chǎn)生這個

32、動作的趨勢便減弱。這 和生理學(xué)中的條件反射原理是接近的。,5.3 常見的幾種學(xué)習(xí)方法,5.3.7 強化學(xué)習(xí) 3. 強化學(xué)習(xí)分類 強化學(xué)習(xí)算法可劃分為兩類：一類算法是先進(jìn)行模型的學(xué)習(xí)，再根據(jù)模型知識推導(dǎo)最優(yōu)策略，這類算法被稱為模型相關(guān)算法(Model-based)；另一類算法是直接計算最優(yōu)策略，這類算法被稱為模型無關(guān)算法(Model-free)。 模型相關(guān)的強化學(xué)習(xí)算法包括時序差分算法(TD)、Sarsa算法和Dyna算法等。 模型無關(guān)的強化學(xué)習(xí)算法包括蒙特卡羅算法(Monte Carlo)、Q學(xué)習(xí)算法和R學(xué)習(xí)算法等。,5.3 常見的幾種學(xué)習(xí)方法,5.3.7 強化學(xué)習(xí) 4. 強化學(xué)習(xí)的應(yīng)用 （1

33、） 在游戲比賽中應(yīng)用 Samuel 在跳棋游戲中 應(yīng)用了時序差分的思想。 （2）在控制系統(tǒng)中應(yīng)用 倒立擺控制 過程控制,5.3 常見的幾種學(xué)習(xí)方法,5.3.7 強化學(xué)習(xí) （3） 在機(jī)器人中應(yīng)用 機(jī)器人導(dǎo)航系統(tǒng) 機(jī)器人協(xié)調(diào)動作 機(jī)器人路徑規(guī)劃,機(jī)器人足球比賽中的2 vs.1問題,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 1. 生理神經(jīng)元的結(jié)構(gòu)與功能 （1）生理神經(jīng)元的結(jié)構(gòu) 神經(jīng)元指神經(jīng)細(xì)胞, 它是生物神經(jīng)系統(tǒng)的最基本 的單元。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 神經(jīng)元由細(xì)胞體、樹突和軸突組成。細(xì)胞體是神經(jīng)元的主體,由細(xì)胞核、細(xì)胞質(zhì)和細(xì)胞膜三部分構(gòu)成

34、.從細(xì)胞體向外延伸出許多突起,其中大部分突起呈樹狀,稱為樹突.樹突起感受作用,接受來自其他神經(jīng)元的傳遞信號. 由細(xì)胞體伸出的一條最長的突起,用來傳出細(xì)胞體產(chǎn)生的輸出信號,稱之為軸突;軸突末端形成許多細(xì)的分枝,叫做神經(jīng)末梢;每一條神經(jīng)末梢可以與其他神經(jīng)元形成功能性接觸,該接觸部位稱為突觸。所謂功能性接觸是指并非永久性接觸,它是神經(jīng)元之間信息傳遞的奧秘之處。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 一個神經(jīng)元把來自不同樹突的興奮性或抑制性輸入信號(突觸后膜電位)累加求和的過程，稱為整合?？紤]到輸入信號的影響要持續(xù)一段時間(毫秒級),因此,神經(jīng)元的整合功能是一種時空整合。當(dāng)神經(jīng)

35、元的時空整合產(chǎn)生的膜電位超過閾值電位時,神經(jīng)元處于興奮狀態(tài),產(chǎn)生興奮性電脈沖,并經(jīng)軸突輸出;否則,無電脈沖產(chǎn)生,處于抑制狀態(tài)。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 神經(jīng)元由細(xì)胞體、樹突和軸突組成。細(xì)胞體是神經(jīng)元的主體,由細(xì)胞核、細(xì)胞質(zhì)和細(xì)胞膜三部分構(gòu)成.從細(xì)胞體向外延伸出許多突起,其中大部分突起呈樹狀,稱為樹突.樹突起感受作用,接受來自其他神經(jīng)元的傳遞信號. 由細(xì)胞體伸出的一條最長的突起,用來傳出細(xì)胞體產(chǎn)生的輸出信號,稱之為軸突;軸突末端形成許多細(xì)的分枝,叫做神經(jīng)末梢;每一條神經(jīng)末梢可以與其他神經(jīng)元形成功能性接觸,該接觸部位稱為突觸。所謂功能性接觸是指并非永久性接觸,

36、它是神經(jīng)元之間信息傳遞的奧秘之處。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 （1）生理神經(jīng)元的功能 人腦有極大量的神經(jīng)元（約為1010 1012個）,每個神經(jīng)元又約有103 104個突觸，神經(jīng)元通過突觸經(jīng)過復(fù)雜的互連而成的一種高度復(fù)雜、非線性、并行處理的信息處理系統(tǒng)。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 與計算機(jī)相比 數(shù)量：神經(jīng)元1010 1012 個； 目前世界上最快的富士通 “京”計算機(jī),由68544個8核處理器所組成，總核數(shù)達(dá)548,352個 。 速度：單個神經(jīng)元的反應(yīng)速度是在毫秒級； 計算機(jī)邏輯門反應(yīng)時間在10-9S。,5.4 基于神經(jīng)網(wǎng)

37、絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 與計算機(jī)相比 連接：每個神經(jīng)元可與幾千個其他神經(jīng)元連接（總連接數(shù)61013）； 計算機(jī) 幾百個機(jī)架，通過交換機(jī)與I/O節(jié)點連接 能耗：神經(jīng)元每一運算約10-16J/S； 計算機(jī)每一運算10-6J/S， “京”計算機(jī)9,890千瓦電源。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 2. 人工神經(jīng)網(wǎng)絡(luò)的組成與數(shù)學(xué)描述 （1）人工神經(jīng)網(wǎng)絡(luò)的組成,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 它是一個多輸入單輸出的非線性閾值器件。其中 x1，x2，xn表示神經(jīng)元的n個輸入信號量； w1，w2，wn表示對應(yīng)輸入的權(quán)值,它表示各

38、信號源神經(jīng)元與該神經(jīng)元的連接強度； 表示神經(jīng)元的輸入總和,它相應(yīng)于生物神經(jīng)細(xì)胞的膜電位,稱為激活函數(shù)；y為神經(jīng)元的輸出；表示神經(jīng)元的閾值。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 （2）數(shù)學(xué)描述 神經(jīng)元輸出 f稱為激發(fā)函數(shù)（active function）或作用函數(shù)，它決定神經(jīng)元的輸出。該輸出為1或0，取決于其輸入之和大于或小于內(nèi)部閾值。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 激發(fā)函數(shù)一般具有非線性特性，常用有三種： 閾值型 1, xi0 f(xi)=U(xi)= 0, xi0 分段線性飽和型 Sigmoid型 最常用,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),

39、5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性,f(x),0,x,f(x),0,x,f(x),0,x,閾值型,分段線性飽和型,Sigmoid型,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 3. 人工神經(jīng)網(wǎng)絡(luò)的分類 如果將多個神經(jīng)元按某 種的拓?fù)浣Y(jié)構(gòu)連接起來， 就構(gòu)成了神經(jīng)網(wǎng)絡(luò)。 根據(jù)連接的拓?fù)浣Y(jié)構(gòu)， 神經(jīng)網(wǎng)絡(luò)可分為四大類： 分層前向網(wǎng)絡(luò)、 反饋前向網(wǎng)絡(luò)、 互連前向網(wǎng)絡(luò)、 廣泛互連網(wǎng)絡(luò)。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 （1）分層前向網(wǎng)絡(luò) 分層前向網(wǎng)絡(luò)如上圖(a)所示。這種網(wǎng)絡(luò)的結(jié)構(gòu)特征是，網(wǎng)絡(luò)由若干層神經(jīng)元組成，一般有輸入層、中間層（又稱隱層，可有一層或多層）

40、和輸出層，各層順序連接；且信息嚴(yán)格地按照從輸入層進(jìn)，經(jīng)過中間層，從輸出層出的方向流動。 （2）反饋前向網(wǎng)絡(luò) 反饋前向網(wǎng)絡(luò)如上圖(b)所示。它也是一種分層前向網(wǎng)絡(luò)，但它的輸出層到輸入層具有反饋連接。反饋的結(jié)果形成封閉環(huán)路，具有反饋的單元也稱為隱單元，其輸出稱為內(nèi)部輸出。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 （3）互連前向網(wǎng)絡(luò) 互連前向網(wǎng)絡(luò)如上圖(c)所示。它也是一種分層前向網(wǎng)絡(luò)，但它的同層神經(jīng)元之間有相互連接。同一層內(nèi)單元的相互連接使它們之間有彼此牽制作用。 （4）廣泛互連網(wǎng)絡(luò) 所謂廣泛互連是指網(wǎng)絡(luò)中任意兩個神經(jīng)元之間都可以或可能是可達(dá)的，即存在連接路徑，廣泛互連網(wǎng)絡(luò)如

41、圖上圖(d)所示。著名的Hopfield網(wǎng)絡(luò)、波爾茨曼機(jī)模型結(jié)構(gòu)均屬此類。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 4. 人工神經(jīng)網(wǎng)絡(luò)的功能 具體來講，神經(jīng)網(wǎng)絡(luò)至少可以實現(xiàn)如下功能： 數(shù)學(xué)上的映射逼近 通過一組映射樣本(x1，y1)(x2，y2)，(xn，yn)，網(wǎng)絡(luò)以自組織方式尋找輸入與輸出之間的映射關(guān)系：yi=f(xi)。識別和分類可以抽象為這一過程。 數(shù)據(jù)聚類 通過自組織方式對所選輸入模式聚類。多目標(biāo)跟蹤 聯(lián)想記憶 實現(xiàn)模式完善、恢復(fù)，相關(guān)模式的相互回憶等。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 3. 人工神經(jīng)網(wǎng)絡(luò)的功能 優(yōu)化計算和組合優(yōu)化問

42、題求解 利用神經(jīng)網(wǎng)絡(luò)的漸進(jìn)穩(wěn)定態(tài)，特別是反饋網(wǎng)絡(luò)的穩(wěn)定平衡態(tài)，進(jìn)行優(yōu)化計算或求解組合優(yōu)化問題的近似最優(yōu)解。 模式分類 現(xiàn)有的大多數(shù)神經(jīng)網(wǎng)絡(luò)模型都有這種分類能力。 概率密度函數(shù)的估計 根據(jù)給定的概率密度函數(shù)，通過自組織網(wǎng)絡(luò)來響應(yīng)在空間Rn中服從這一概率分布的一組向量樣本X1，X2，Xk。,5.4 基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),5.4.1 神經(jīng)網(wǎng)絡(luò)的組成與特性 4. 人工神經(jīng)網(wǎng)絡(luò)的工作過程 神經(jīng)網(wǎng)絡(luò)的工作過程主要由兩階段組成：第一個階段是學(xué)習(xí)期，此時各計算單元狀態(tài)不變，各連接權(quán)值通過學(xué)習(xí)樣本可修改；第一個階段是工作期，此時各連接權(quán)值固定，計算單元的狀態(tài)變化，以求達(dá)到穩(wěn)定狀態(tài)。 學(xué)習(xí)(亦稱訓(xùn)練)是神經(jīng)網(wǎng)絡(luò)的最重要特征之一。神經(jīng)網(wǎng)絡(luò)能夠通過學(xué)習(xí),改