《機(jī)器學(xué)習(xí)》PPT課件.ppt

第六章 機(jī)器學(xué)習(xí) 6.1 機(jī)器學(xué)習(xí)概念6.2 示例學(xué)習(xí)6.2.1示例學(xué)習(xí)的兩個(gè)空間模型6.3 基于解釋的學(xué)習(xí)6.4基于案例的推理6.5 加強(qiáng)學(xué)習(xí) 6.1 機(jī)器學(xué)習(xí)的概念6.1.1 機(jī)器學(xué)習(xí)的發(fā)展歷史1.神經(jīng)元模型研究階段這個(gè)時(shí)期主要技術(shù)是神經(jīng)元模型以及基于該模型的決策論和控制論;機(jī)器學(xué)習(xí)方法通過(guò)監(jiān)督（有教師指導(dǎo)的）學(xué)習(xí)來(lái)實(shí)現(xiàn)神經(jīng)元間連接權(quán)的自適應(yīng)調(diào)整，產(chǎn)生線(xiàn)性的模式分類(lèi)和聯(lián)想記憶能力。具有代表性的工作有FRosenblaft的感知機(jī)（1958年）；NRashevsky數(shù)學(xué)生物物理學(xué)（1948年）；WSMcCullouch與WPitts的模式擬神經(jīng)元的理論（1943年）;RMFriedberg對(duì)生物進(jìn)化過(guò)程的模似等。 v2符號(hào)概念獲取研究階段60年代初期，機(jī)器學(xué)習(xí)的研究進(jìn)入了第二階段，在這個(gè)階段，心理學(xué)和人類(lèi)學(xué)習(xí)的模似占有主導(dǎo)地位，其特點(diǎn)是使用符號(hào)而不是數(shù)值表示來(lái)研究學(xué)習(xí)問(wèn)題，其目標(biāo)是用學(xué)習(xí)來(lái)表達(dá)高級(jí)知識(shí)的符號(hào)描述。在這一觀(guān)點(diǎn)的影響下，主要技術(shù)是概念獲取和各種模式識(shí)別系統(tǒng)的應(yīng)用；研究人員一方面深入探討學(xué)習(xí)的簡(jiǎn)單概念，另一方面則把大量的領(lǐng)域知識(shí)并入學(xué)習(xí)系統(tǒng)，以便它們發(fā)現(xiàn)高深的概念。這個(gè)階段代表性的工作是溫斯頓（Winston，1975）的基于示例歸納的結(jié)構(gòu)化概念學(xué)習(xí)系統(tǒng)。 v3基于知識(shí)的各種學(xué)習(xí)系統(tǒng)研究階段機(jī)器學(xué)習(xí)發(fā)展的第三個(gè)階段始于70年代中期，這個(gè)階段不再局限于構(gòu)造概念學(xué)習(xí)系統(tǒng)和獲取上下文知識(shí)，結(jié)合了問(wèn)題求解中的學(xué)習(xí)、概念聚類(lèi)、類(lèi)比推理及機(jī)器發(fā)現(xiàn)的工作。相應(yīng)的有關(guān)學(xué)習(xí)方法相繼推出，比如示例學(xué)習(xí)、示教學(xué)習(xí)、 觀(guān)察和發(fā)現(xiàn)學(xué)習(xí)、類(lèi)比學(xué)習(xí)、基于解釋的學(xué)習(xí)。工作特點(diǎn)強(qiáng)調(diào)應(yīng)用面向任務(wù)的知識(shí)和指導(dǎo)學(xué)習(xí)過(guò)程的約束，應(yīng)用啟發(fā)式知識(shí)于學(xué)習(xí)任務(wù)的生成和選擇，包括提出收集數(shù)據(jù)的方式、選擇要獲取的概念、控制系統(tǒng)的注意力等。 v4聯(lián)結(jié)學(xué)習(xí)和符號(hào)學(xué)習(xí)共同發(fā)展階段80年代后期以來(lái)，形成了聯(lián)結(jié)學(xué)習(xí)和符號(hào)學(xué)習(xí)共同發(fā)展的局的第四個(gè)階段。在這個(gè)時(shí)期，發(fā)現(xiàn)了用隱單元來(lái)計(jì)算和學(xué)習(xí)非線(xiàn)性函數(shù)的方法，從而克服了早期神經(jīng)元模型的局限性，同時(shí)，由于計(jì)算機(jī)硬件的迅速發(fā)展，使得神經(jīng)網(wǎng)絡(luò)的物理實(shí)現(xiàn)變成可能，在聲間識(shí)別、圖像處理等領(lǐng)域，神經(jīng)網(wǎng)絡(luò)取得了很大的成功。在這個(gè)進(jìn)期，符號(hào)學(xué)習(xí)伴隨人工智能的進(jìn)展也日益成熟，應(yīng)用領(lǐng)域不斷擴(kuò)大，最杰出的工作有分析學(xué)習(xí)（特別是解釋學(xué)習(xí)）、遺傳算法、決策樹(shù)歸納等。現(xiàn)在基于計(jì)算機(jī)網(wǎng)絡(luò)的各種自適應(yīng)、具有學(xué)習(xí)功能的軟件系統(tǒng)的研制和開(kāi)發(fā),將機(jī)器學(xué)習(xí)的研究推向新的高度。 6.1.2什么是機(jī)器學(xué)習(xí)什么是機(jī)器學(xué)習(xí)，到今仍沒(méi)有嚴(yán)格定義，不同學(xué)派對(duì)機(jī)器學(xué)習(xí)有不同的定義 準(zhǔn)確、完整地給出機(jī)器學(xué)習(xí)的定義很困難，綜合上述三種觀(guān)點(diǎn)可以得出，學(xué)習(xí)是對(duì)某一個(gè)特定目標(biāo)的知識(shí)獲取的智能過(guò)程，系統(tǒng)的內(nèi)部表現(xiàn)為新知識(shí)結(jié)構(gòu)的建立和改進(jìn)，外部表現(xiàn)為系統(tǒng)性能的改善，變得更快、更精確、更健全。 v一個(gè)機(jī)器學(xué)習(xí)系統(tǒng)應(yīng)具有以下特點(diǎn)：v1.具有適當(dāng)?shù)膶W(xué)習(xí)環(huán)境v學(xué)習(xí)系統(tǒng)中環(huán)境并非指通常的物理?xiàng)l件，而是指學(xué)習(xí)系統(tǒng)進(jìn)行學(xué)習(xí)時(shí)所必需的信息來(lái)源。v2.具有一定的學(xué)習(xí)能力v一個(gè)好的學(xué)習(xí)方法和一定的學(xué)習(xí)能力是取得理想的學(xué)習(xí)效果的重要手段。所以，學(xué)習(xí)系統(tǒng)應(yīng)模擬人的學(xué)習(xí)過(guò)程，使系統(tǒng)通過(guò)與環(huán)境反復(fù)多次相互作用，逐步學(xué)到有關(guān)知識(shí)，并且要使系統(tǒng)在學(xué)習(xí)過(guò)程中通過(guò)實(shí)踐驗(yàn)證、評(píng)價(jià)所學(xué)知識(shí)的正確性。v3.能用所學(xué)的知識(shí)解決問(wèn)題v學(xué)習(xí)的目的在于應(yīng)用，學(xué)習(xí)系統(tǒng)能把學(xué)到的信息用于對(duì)未來(lái)的估計(jì)、分類(lèi)、決策和控制。 v4.能提高系統(tǒng)的性能v提高系統(tǒng)的性能是學(xué)習(xí)系統(tǒng)最終目標(biāo)。通過(guò)學(xué)習(xí)，系統(tǒng)隨之增長(zhǎng)知識(shí)，提高解決問(wèn)題的能力，使之能完成原來(lái)不能完成的任務(wù)，或者比原來(lái)做得更好。v學(xué)習(xí)系統(tǒng)至少應(yīng)有環(huán)境、知識(shí)庫(kù)、學(xué)習(xí)環(huán)節(jié)和執(zhí)行環(huán)節(jié)四個(gè)基本部分。一種典型的機(jī)器學(xué)習(xí)系統(tǒng)（迪特里奇（Dietterich）學(xué)習(xí)模型）如圖6-1所示。環(huán)境向系統(tǒng)的學(xué)習(xí)部件提供某些信息，學(xué)習(xí)環(huán)節(jié)利用這些信息修改知識(shí)庫(kù)，增進(jìn)執(zhí)行部件的效能；執(zhí)行環(huán)節(jié)根據(jù)知識(shí)庫(kù)完成任務(wù)，同時(shí)把獲得的信息反饋給學(xué)習(xí)部件。下面介紹其主要組成部分的功能。 1.環(huán)境v系統(tǒng)中的環(huán)境包括工作對(duì)象和外界條件。比如在醫(yī)療系統(tǒng)中，環(huán)境就是病人當(dāng)前的癥狀，物化檢驗(yàn)的報(bào)告和病歷等信息；在模式識(shí)別中，環(huán)境就是待識(shí)別的圖形或影物；在控制系統(tǒng)中，環(huán)境就是受控的設(shè)備或生產(chǎn)流程。v環(huán)境提供給系統(tǒng)的信息水平和質(zhì)量對(duì)于學(xué)習(xí)系統(tǒng)有很大的影響。信息的水平是指信息的一般性程度，也就是適用范圍的廣泛性，高水平的信息往往比較抽象，適用面更廣泛。v信息的質(zhì)量指信息的正確性、信息選擇的適宜性和信息組織的合理性。信息質(zhì)量對(duì)學(xué)習(xí)難度有明顯的影響。 2.學(xué)習(xí)環(huán)節(jié)v學(xué)習(xí)環(huán)節(jié)是系統(tǒng)的學(xué)習(xí)機(jī)構(gòu)，是學(xué)習(xí)系統(tǒng)的核心。它通過(guò)對(duì)環(huán)境的搜索取得外部信息，然后經(jīng)分析、綜合、類(lèi)比、推理等思維過(guò)程獲得知識(shí)，并將這些知識(shí)送入知識(shí)庫(kù)，供執(zhí)行環(huán)節(jié)使用。v事實(shí)上，由于環(huán)境提供的信息水平與執(zhí)行環(huán)節(jié)所需的信息水平之間往往有差距，學(xué)習(xí)環(huán)節(jié)的任務(wù)就是解決這個(gè)水平差距問(wèn)題。如果環(huán)境提供較高水平的信息，學(xué)習(xí)環(huán)節(jié)就去就去補(bǔ)充遺漏的細(xì)節(jié)，以便執(zhí)行環(huán)節(jié)能用于具體情況。如果環(huán)境提供較具體的低水平信息，即在特殊情況執(zhí)行任務(wù)的實(shí)例，學(xué)習(xí)環(huán)節(jié)就要上此歸納規(guī)則，以便系統(tǒng)能完成更為一般的任務(wù)。 3.知識(shí)庫(kù)v學(xué)習(xí)系統(tǒng)設(shè)計(jì)的另一個(gè)重要問(wèn)題就是知識(shí)庫(kù)的形成設(shè)計(jì)以及其內(nèi)容。學(xué)習(xí)系統(tǒng)實(shí)質(zhì)上就是對(duì)原有知識(shí)的擴(kuò)充和完善。 4.執(zhí)行環(huán)節(jié)v執(zhí)行環(huán)節(jié)實(shí)際上是由執(zhí)行環(huán)節(jié)和評(píng)價(jià)兩部分組成，執(zhí)行環(huán)節(jié)用于處理系統(tǒng)面臨的現(xiàn)實(shí)問(wèn)題，比如定理證明、智能控制、自然語(yǔ)言處理、機(jī)器人行動(dòng)規(guī)劃等；評(píng)價(jià)環(huán)節(jié)用來(lái)驗(yàn)證、評(píng)價(jià)執(zhí)行環(huán)節(jié)執(zhí)行的效果，比如結(jié)果的正確性等。評(píng)價(jià)環(huán)節(jié)的處理方法有兩種，一種是把評(píng)價(jià)時(shí)所需的性能指標(biāo)直接建立在系統(tǒng)中，由系統(tǒng)對(duì)執(zhí)行環(huán)節(jié)所做出的結(jié)論進(jìn)行評(píng)價(jià)；另一種是由人類(lèi)協(xié)助完成評(píng)價(jià)工作。v另外，從執(zhí)行環(huán)節(jié)到學(xué)習(xí)環(huán)節(jié)心須要有反饋信息。這們，學(xué)習(xí)環(huán)節(jié)就可以根據(jù)反饋信息決定是否要從環(huán)境中獲取進(jìn)一步的信息進(jìn)行再學(xué)習(xí)，以便修改、完善知識(shí)庫(kù)中的知識(shí)。 6.1.3機(jī)器學(xué)習(xí)分類(lèi)v當(dāng)前國(guó)際上流行的機(jī)器學(xué)習(xí)分類(lèi)方法主要有四種：按應(yīng)用領(lǐng)域分類(lèi)：主要的應(yīng)用領(lǐng)域有專(zhuān)家系統(tǒng)、認(rèn)知模擬、規(guī)劃和問(wèn)題求解、數(shù)據(jù)挖掘、網(wǎng)絡(luò)信息服務(wù)、圖象識(shí)別、故障診斷、自然語(yǔ)言理解、機(jī)器人和博弈等。v按獲取的知識(shí)的表示分類(lèi)：有形式邏輯表達(dá)式、形式文法、代數(shù)表達(dá)式參數(shù)、圖和網(wǎng)絡(luò)、框架和模式、計(jì)算機(jī)程序和其它的過(guò)程編碼、產(chǎn)生式規(guī)則、決策樹(shù)、框架、神經(jīng)網(wǎng)絡(luò)等；v按推理策略分類(lèi)：如演繹推理和歸納推理。v按學(xué)習(xí)系統(tǒng)性綜合分類(lèi)的方法：考慮了事物的歷史淵源、知識(shí)表示、推理策略和應(yīng)用領(lǐng)域等因素，是對(duì)前面三種分類(lèi)方法的綜合。 （一）基于推理策略的分類(lèi)v一個(gè)學(xué)習(xí)過(guò)程實(shí)質(zhì)上是學(xué)習(xí)系統(tǒng)把環(huán)境所提供的信息轉(zhuǎn)換成新的形式，以便存儲(chǔ)和使用。這種信息的轉(zhuǎn)換就是種推理，而推理的性質(zhì)確定了學(xué)習(xí)策略的類(lèi)型。在學(xué)習(xí)過(guò)程中，學(xué)生所使用的推理越少，他對(duì)教師的依賴(lài)就越大，因而教師的負(fù)擔(dān)就越重，反過(guò)來(lái)，學(xué)生使用的推理越多，教師的負(fù)擔(dān)就越輕。顯然，基于推理策略分類(lèi)方法可以按學(xué)生使用推理的多少和難易程度進(jìn)行。下面分別進(jìn)行討論。 v1.機(jī)械學(xué)習(xí)（Rote Learning）v機(jī)械學(xué)習(xí)是最簡(jiǎn)單的學(xué)習(xí)方法，它亦被稱(chēng)為記憶學(xué)習(xí)或死記硬背式學(xué)習(xí)。這種學(xué)習(xí)方法不需要推理，而是由教師向系統(tǒng)提供被記憶的信息，學(xué)習(xí)者無(wú)需任何推理或其它的知識(shí)轉(zhuǎn)換，直接吸取環(huán)境所提供的信息，并用這些信息指導(dǎo)系統(tǒng)行為。v 機(jī)械學(xué)習(xí)是記憶，它僅保存新的知識(shí)以便使用。這里是個(gè)檢索問(wèn)題，而不是重復(fù)計(jì)算、推理或查詢(xún)。機(jī)械學(xué)習(xí)可以認(rèn)為是基本的學(xué)習(xí)方式，它本身并不能實(shí)現(xiàn)智能學(xué)習(xí)，但是它是其他學(xué)習(xí)系統(tǒng)所固有重要組成部分。在機(jī)械學(xué)習(xí)系統(tǒng)中，知識(shí)已經(jīng)以某種方式獲取，并且是一種直接可使用的形式。所有學(xué)習(xí)系統(tǒng)都是建立在機(jī)械學(xué)習(xí)的基礎(chǔ)之上，即對(duì)知識(shí)庫(kù)中的知識(shí)進(jìn)行存儲(chǔ)、維護(hù)和檢索。 v2. 示教學(xué)習(xí)（Learning from Instruction or Learning by being told）v示教學(xué)習(xí)中，教師以某種形式（教導(dǎo)和建議）提出和組織知識(shí)，以使學(xué)生擁有的知識(shí)可以不斷地增加。學(xué)生把知識(shí)轉(zhuǎn)換成內(nèi)部可使用的表示形式，并將新的知識(shí)和原有知識(shí)有機(jī)地結(jié)合為一體；示教系統(tǒng)中，由外部給系統(tǒng)提供抽象的、一般化的信息，學(xué)習(xí)系統(tǒng)經(jīng)過(guò)選擇和改造，把新的信息與系統(tǒng)原有的知識(shí)融為一體。由于外部提供的信息過(guò)于抽象，它的水平高于執(zhí)行時(shí)所用信息的水平，因此學(xué)習(xí)環(huán)節(jié)要把把較高水平的知識(shí)轉(zhuǎn)換為較低水平的知識(shí)，這種轉(zhuǎn)換稱(chēng)為實(shí)用化。 v研究示教學(xué)習(xí)的途徑主要有兩種。一是在開(kāi)發(fā)系統(tǒng)時(shí)接收抽象的、高級(jí)的信息，并將它變換成規(guī)則，以便批指導(dǎo)執(zhí)行部分。二是開(kāi)發(fā)完善的工具，比如知識(shí)庫(kù)的編輯和調(diào)試輔助程序，使得專(zhuān)家們可以很方便地將專(zhuān)門(mén)知識(shí)轉(zhuǎn)換成詳細(xì)的規(guī)則。 v3. 演繹學(xué)習(xí)（Deductive Learning）v這種學(xué)習(xí)方法是一種常規(guī)的邏輯推理方法。其推理的過(guò)程通常從公理出發(fā)，經(jīng)過(guò)邏輯變換，推導(dǎo)出結(jié)論。演繹學(xué)習(xí)包括知識(shí)改造、知識(shí)編譯、生成宏操作、保持等價(jià)操作和其他的一些保真變換。 v4. 解釋學(xué)習(xí)(Explanation-based Learning)v解釋學(xué)習(xí)利用問(wèn)題求解的示例，依賴(lài)領(lǐng)域知識(shí)構(gòu)造出求解過(guò)程的因果解釋結(jié)構(gòu)，并獲取控制知識(shí)，為以后類(lèi)似問(wèn)題求解提供指導(dǎo)。v解釋學(xué)習(xí)過(guò)程可分成兩個(gè)步驟：v首先產(chǎn)生解釋結(jié)構(gòu)：輸入實(shí)例后，系統(tǒng)首先對(duì)問(wèn)題進(jìn)行求解。 v再用解釋結(jié)構(gòu)對(duì)得到的解釋結(jié)構(gòu)和事例進(jìn)行概括：概括通常采取的方法是將常量轉(zhuǎn)換成變量，且去掉某些不重要的信息，僅僅保留求解時(shí)所必需的那些關(guān)鍵信息，經(jīng)過(guò)一定的方式進(jìn)行組合形成產(chǎn)生式規(guī)則，從而獲得概括性的控制知識(shí)。 v5. 類(lèi)比學(xué)習(xí)（Learning by Analogy）v類(lèi)比學(xué)習(xí)利用二個(gè)不同領(lǐng)域（源域、目標(biāo)域）中的知識(shí)相似性，通過(guò)類(lèi)比，從源域的知識(shí)（包括相似的特征和其它性質(zhì)）推導(dǎo)出目標(biāo)域的相應(yīng)知識(shí)。例如：未開(kāi)過(guò)貨車(chē)的司機(jī)有開(kāi)小車(chē)的知識(shí)就可完成開(kāi)貨車(chē)的任務(wù)；v類(lèi)比學(xué)習(xí)是演繹和歸納學(xué)習(xí)的組合。它對(duì)不同論域的描述進(jìn)行匹配，確定公共的子結(jié)構(gòu)，以此作為類(lèi)比映射。尋找公共子結(jié)構(gòu)是歸納推理，而實(shí)現(xiàn)類(lèi)比映射是演繹推理。 v6. 歸納學(xué)習(xí)（Inductive learning）v歸納學(xué)習(xí)由教師或環(huán)境提供某概念的一些實(shí)例或反例，學(xué)生通過(guò)歸納推理得出該概念的一般描述。歸納學(xué)習(xí)可分為示例學(xué)習(xí)和觀(guān)察與發(fā)現(xiàn)學(xué)習(xí)。v示例學(xué)習(xí)（Learning from Examples ）v示例學(xué)習(xí)也稱(chēng)為概念獲?。–oncept Acquisition）。是由教師提供給系統(tǒng)某種概念的正例集合反例集合，學(xué)習(xí)通過(guò)歸納推理產(chǎn)生覆蓋所有正例并排除所有反例的該概念的一般描述。這些正例是由已知概念的教師或者是學(xué)生做實(shí)驗(yàn)時(shí)從系統(tǒng)中得到的反饋信息而提供的。 v觀(guān)察與發(fā)現(xiàn)學(xué)習(xí)（Learning from Observation and Discovery）v觀(guān)察與發(fā)現(xiàn)學(xué)習(xí)是由環(huán)境提供一組觀(guān)察事例，學(xué)生構(gòu)造一個(gè)一般的概念描述（即理論）來(lái)覆蓋所有或大多數(shù)事例。這是一種無(wú)導(dǎo)師學(xué)習(xí)。這類(lèi)學(xué)習(xí)又分為觀(guān)察學(xué)習(xí)與機(jī)器發(fā)現(xiàn)兩類(lèi)。 v（1）觀(guān)察學(xué)習(xí) 觀(guān)察學(xué)習(xí)是學(xué)生將已知事例進(jìn)行分類(lèi)，同時(shí)產(chǎn)生每一類(lèi)的一般概念描述。觀(guān)察學(xué)習(xí)又可根據(jù)是否漸近（incremental）方式而分為va概念聚類(lèi) b概念形成 v(2)機(jī)器發(fā)現(xiàn)（Machine Discovery）v學(xué)生從觀(guān)察的事例或經(jīng)驗(yàn)數(shù)據(jù)中進(jìn)行歸納產(chǎn)生規(guī)律或規(guī)則，這就是機(jī)器發(fā)現(xiàn)。機(jī)器發(fā)現(xiàn)是觀(guān)察與發(fā)現(xiàn)學(xué)習(xí)的最困難、最富有創(chuàng)造性的一種學(xué)習(xí)形式。機(jī)器發(fā)現(xiàn)包括有經(jīng)驗(yàn)發(fā)現(xiàn)和知識(shí)發(fā)現(xiàn)兩種類(lèi)型。 （二）基于系統(tǒng)綜合性的分類(lèi)v基于系統(tǒng)性分類(lèi)，機(jī)器學(xué)習(xí)可分為四種類(lèi)型，即：歸納學(xué)習(xí)、分析學(xué)習(xí)、聯(lián)接學(xué)習(xí)、遺傳算法與分類(lèi)系統(tǒng)。 v1分析學(xué)習(xí)（Analytie Learning）分析學(xué)習(xí)是針對(duì)幾個(gè)實(shí)際例子，應(yīng)用領(lǐng)域知識(shí)進(jìn)分析來(lái)學(xué)習(xí)。 v2聯(lián)結(jié)學(xué)習(xí)(connection based learning)聯(lián)結(jié)學(xué)習(xí)的目標(biāo)是區(qū)分輸入模式的等價(jià)類(lèi)。一個(gè)聯(lián)結(jié)模型是由一些類(lèi)似神經(jīng)元的簡(jiǎn)單單元帶權(quán)互邊而組成的網(wǎng)絡(luò)。 v3遺傳算法（Genetic Algorithm）遺傳算法似生物繁殖的突變（互換、倒位、點(diǎn)突變等）和達(dá)爾文的自然選擇（在每一生態(tài)環(huán)境中適者生存）。 v4.加強(qiáng)學(xué)習(xí)（reinforcement learning）加強(qiáng)學(xué)習(xí)的學(xué)習(xí)目標(biāo)是尋找一個(gè)合適的動(dòng)作選擇策略，使產(chǎn)生的動(dòng)作序列可獲得某種最優(yōu)的結(jié)果（如累計(jì)立即回報(bào)最大）。基本方法是通過(guò)與環(huán)境的試探性（trial and error）交互來(lái)確定和優(yōu)化動(dòng)作的選擇。 6.2示例學(xué)習(xí)v示例學(xué)習(xí)屬于歸納學(xué)習(xí)，是目前機(jī)器學(xué)習(xí)方法中最成熟的方法之一。示例學(xué)習(xí)要求環(huán)境能夠從一些特殊的實(shí)例（這些實(shí)例事先由教師劃分為正例和反例兩類(lèi)），并由這些實(shí)例進(jìn)行歸納推理，導(dǎo)出一般性的規(guī)則。 v6.2.1示例學(xué)習(xí)的兩個(gè)空間模型v示例學(xué)習(xí)的模型如圖6-2所示。例子空間是所有可能的正、反例構(gòu)成的空間；假設(shè)空間（又稱(chēng)概念空間）是所有可能的概念描述（稱(chēng)為假設(shè)）構(gòu)成的空間。v 假設(shè)空間中的每一假設(shè)都對(duì)應(yīng)于例子空間中的一個(gè)子集，使得該子集中的例子均是該假設(shè)的例子。 v在圖6-2中，除描繪從例子學(xué)習(xí)的實(shí)例空間規(guī)則空間外，還描繪了解釋實(shí)例和實(shí)驗(yàn)規(guī)劃過(guò)程。v在這個(gè)模型中，首先由示教者給實(shí)例空間提供一些初始示教例子，然后程序?qū)κ窘汤舆M(jìn)行解釋。由于示教例子的形式往往不同于規(guī)則形式，所以有必要對(duì)例子進(jìn)行解釋。往后再利用被解釋的示教例子支搜索規(guī)則空間。一般情況下不能一次就從規(guī)則空間中搜索到要求的規(guī)則，因此還要尋找一些新的示教例子，這個(gè)過(guò)程就是選擇例子。此過(guò)程如此循環(huán)，直到搜索到要求的規(guī)則。 v（一）實(shí)例空間v考慮撲克牌中“同花”概念的問(wèn)題，同花是五張同一花色所組成的手牌。在這個(gè)學(xué)習(xí)問(wèn)題中，實(shí)例空間是五張牌的全部各手牌的集合。我們可以把這個(gè)空間中單個(gè)的點(diǎn)表示為一組五個(gè)有序?qū)Γ热纾簐 （2，梅花），（3，梅花），（5，梅花），（J，梅花），（K，梅花）v每一有序?qū)χ该饕粡埮频狞c(diǎn)數(shù)和花色。整個(gè)實(shí)例空間是所有這樣的五張牌集合的空間。高質(zhì)量的示教例子是無(wú)二義性的，它可以為規(guī)則空間的搜索提供可靠的指導(dǎo)。低質(zhì)量的示教例子會(huì)引起互相矛盾的解釋?zhuān)浣Y(jié)果僅為規(guī)則空間的搜索提供試探性的指導(dǎo)。示教例子排列次序也會(huì)影響學(xué)習(xí)的質(zhì)量。 v一般情況下認(rèn)為實(shí)例是同時(shí)提供的，也可以主動(dòng)地選擇另外一些附加的實(shí)例，以便修正假設(shè)，這種方法稱(chēng)為補(bǔ)充學(xué)習(xí)。還有的程序直接搜索實(shí)例空間，這種方法稱(chēng)主動(dòng)選擇例子。 v（二）規(guī)則空間v定義規(guī)則空間的目的是指定表示規(guī)則的操作符和術(shù)語(yǔ)。所謂規(guī)則空間是用指定的描述語(yǔ)言可以表示的所有規(guī)則(概念假設(shè))的集合。對(duì)規(guī)則空間有三個(gè)方面的要求，即規(guī)則的表示形式應(yīng)適應(yīng)歸納推理，規(guī)則的表示與實(shí)例的表示一致，規(guī)則空間應(yīng)包含要求的規(guī)則。 v三）解釋例子v解釋示教例子的基本目的是提取指導(dǎo)規(guī)則空間搜索有用的信息。通常是把示數(shù)例子轉(zhuǎn)換成易于進(jìn)行符號(hào)歸納的形式。不過(guò)，這種轉(zhuǎn)換也許是困難的，尤其是在感性的學(xué)習(xí)中。 v (四）實(shí)驗(yàn)規(guī)則v一旦學(xué)習(xí)環(huán)節(jié)根據(jù)示教例子搜索規(guī)則空間，并產(chǎn)生可能合理的假設(shè)規(guī)則集合H后，程序就可能需要收集更多的訓(xùn)練實(shí)例加以測(cè)試和修改集合H。當(dāng)實(shí)例空間和規(guī)則空間是以不相同的方法表示時(shí)，就需要判斷訓(xùn)練哪些實(shí)例和怎樣才能獲得它們，這是一個(gè)復(fù)雜的過(guò)程。比如，假定一個(gè)遺傳學(xué)習(xí)程序要想發(fā)現(xiàn)DNA的哪一部分是最重要的，為了測(cè)試幾個(gè)高級(jí)假設(shè)（即假設(shè)的規(guī)則）要安排復(fù)雜的試驗(yàn)。這些試驗(yàn)合成DNA的特殊成分，并把它插入到適當(dāng)?shù)募?xì)菌細(xì)胞中，以觀(guān)察細(xì)胞的最后動(dòng)作。 v搜索規(guī)則空間的方法有：特化搜索既從最泛化的假設(shè)（概念描述）出發(fā)，每次取用一個(gè)新的例子，就產(chǎn)生一些特化的描述，直到將初始最泛化的假設(shè)特化為解描述。泛化搜索即從最特化的假設(shè)（相應(yīng)于例子空間中的一個(gè)例子）開(kāi)始，每次取用一個(gè)新的例子時(shí)，就產(chǎn)生一些泛化的描述，直到產(chǎn)生出足夠泛化的解描述。大多數(shù)示例學(xué)習(xí)方法都采用這二種方法或這二個(gè)方法的結(jié)合。下面介紹搜索規(guī)則空間的幾種方法。這些方法都具有一個(gè)假設(shè)規(guī)則的集合H，不同的僅僅是對(duì)H的改進(jìn)，以便得到要求的規(guī)則。 v（1）變型空間法（version-space methold）v變型空間法是TMMitchell于1977年提出的一種數(shù)據(jù)驅(qū)動(dòng)型的學(xué)習(xí)方法。v該方法以整個(gè)規(guī)則空間為初始的假設(shè)規(guī)則集合H。依據(jù)示教例子中的信息，系統(tǒng)對(duì)集合H進(jìn)行一般化或特殊化處理，逐步縮小集合H。最后使得H收斂到只含有要求的規(guī)則。由于被搜索的空間H逐漸縮小，故稱(chēng)為變型空間法。 v 1規(guī)則空間的結(jié)構(gòu)v在規(guī)則空間中，表示規(guī)則的點(diǎn)與點(diǎn)之間存在著一種由一般到特殊的偏序關(guān)系。我們定義為覆蓋，例如，color(X,Y)覆蓋color(ball,Z)，于是又覆蓋color(ball,red)。v作為一個(gè)簡(jiǎn)單的例子，考慮有這樣一些屬性和值的對(duì)象域：v Sizes=large,smallv Colors=red,white,bluev Shapes=ball,brick,cubev這些對(duì)象可以用謂詞obj(Sizes,Color,Shapes)來(lái)表示。用變量替換常量這個(gè)泛化操作定義 v如圖6-3的空間。 v圖6-3表示了一個(gè)規(guī)則空間偏序關(guān)系的一部分。我們可以把歸納學(xué)習(xí)看成是對(duì)同所有訓(xùn)練實(shí)例相一致的概念空間的搜索。在搜索規(guī)則空間時(shí)，使用一個(gè)可能合理的假設(shè)規(guī)則的集合H，是規(guī)則空間的子集，從圖6-4可知，H中最一般的元素構(gòu)成的子集為G，H中最特殊的元素構(gòu)成的子集為S。在規(guī)則空間中，H是以G為上確界和以S為下確界的一段。因此，可以用G和要來(lái)表示集合H。 v2修選刪除算法v Mitchell的學(xué)習(xí)算法稱(chēng)為候選刪除算法。在這種算法中，把尚未被數(shù)據(jù)排除的假設(shè)稱(chēng)為可能假設(shè)，把所有可能假設(shè)構(gòu)成的集合H稱(chēng)為變型空間。v 算法一開(kāi)始，變型空間H包含所有的概念隨著向程序提供示教正例后，程序就從變v型空間中刪除候選概念。當(dāng)變型空間僅包含有一個(gè)候選概念時(shí)，就找到了所要求的概念。v該算法分為四個(gè)步驟： (1)把H初始化為整個(gè)規(guī)則空間。這時(shí)G僅包含空描述。S包含所有最特殊的概念。v實(shí)際上，為避免S集合過(guò)大，算法把S初化為僅包含第一個(gè)示教正例。（2）接受一個(gè)新的示教例子。如果這個(gè)例子是正例，則從G中刪除不包含新例的概念，然后修改S為由新正例和S原有元素同歸納出最特殊化的泛化。這個(gè)過(guò)程稱(chēng)為對(duì)集合S的修改過(guò)程。如果這個(gè)例子是反例，則從S中刪去包含新例的概念，再對(duì)G作盡量小的特殊化，使之不包含新例。這個(gè)過(guò)程稱(chēng)為集合G的修改過(guò)程。（3）重復(fù)步驟，直到G=S，且使這兩個(gè)集合都只含有一個(gè)元素為止。（4）輸出H中的概念（即輸出G或S）。 v3方法討論v變型空間法還存在有一些弱點(diǎn)，需要加以改進(jìn)。該方法的主要缺點(diǎn)是：v（1）抗干擾能力差v （2）無(wú)法發(fā)現(xiàn)析取概念 2.改進(jìn)假設(shè)法v改進(jìn)假設(shè)法（hypothesis-rfinement methold）也是一種數(shù)據(jù)驅(qū)動(dòng)方法。這種方法表示規(guī)則和實(shí)例的形式不統(tǒng)一。程序根據(jù)例子選擇一種操作，用該操作去改進(jìn)假設(shè)規(guī)則集H中的規(guī)則。 v3.產(chǎn)生與測(cè)試法v產(chǎn)生與測(cè)試法（generate and test）是一種模型驅(qū)動(dòng)方法（model-driven methold）。這種方法針對(duì)示教例子反復(fù)產(chǎn)生和測(cè)試假設(shè)的規(guī)則。在產(chǎn)生假設(shè)規(guī)則時(shí)，使用基于模型的知識(shí)，以便只產(chǎn)生可能合理的假設(shè)。 v4.方案示例法v方案示例法（schema instantiation）也是一種模型驅(qū)動(dòng)方法。該方法使用規(guī)則方案的集合來(lái)約束可能合理的規(guī)則的形式，其中最符合示教例子的規(guī)則方案被認(rèn)為是最合理的規(guī)則。數(shù)據(jù)驅(qū)動(dòng)方法的優(yōu)點(diǎn)是可以逐步接受示教例子，以漸近方式學(xué)習(xí)，特別是變型空間法，它很容易修改集合H，不要求程序回溯就可以考慮新的實(shí)例。而模型驅(qū)動(dòng)方法難以逐步學(xué)習(xí)，它是通過(guò)檢查全部實(shí)例來(lái)測(cè)試假設(shè)。在使用新假設(shè)時(shí)，它必須回溯或重新搜索規(guī)則空間。因?yàn)樵瓉?lái)對(duì)假設(shè)的測(cè)試已不適用于新實(shí)例加入后的情況。 6.2.2示例學(xué)習(xí)的一個(gè)變種決策樹(shù)學(xué)習(xí)算法 v 1 決策樹(shù)v決策樹(shù)歸納算法主要是通過(guò)一組輸入輸出樣本構(gòu)建決策樹(shù)的有指導(dǎo)學(xué)習(xí)方法。一個(gè)典型的決策樹(shù)學(xué)習(xí)系統(tǒng)采用的確是自頂向下的方法，在部分搜索空間中搜索解決方案。它可以確保求出一個(gè)簡(jiǎn)單的決策樹(shù)，但未必是最簡(jiǎn)單的。v決策樹(shù)一個(gè)屬性節(jié)點(diǎn)的輸出分枝和該節(jié)點(diǎn)的所有可能的檢驗(yàn)結(jié)果相對(duì)應(yīng)。圖6-6給出了有兩個(gè)輸出屬性X和Y的樣本分類(lèi)的一個(gè)簡(jiǎn)單決策樹(shù)。所有屬性值X和Y=B的樣本屬于類(lèi)2。不論屬性Y的值是多少，值X1的樣本都屬于類(lèi)1。對(duì)于樹(shù)中的非葉節(jié)點(diǎn)，可以沿著分枝繼續(xù)分區(qū)樣本，每一個(gè)子節(jié)點(diǎn)得到它相應(yīng)的樣本子集。 v生成決策樹(shù)的一個(gè)著名的算法是Quinlan的ID3算法，它有一個(gè)改進(jìn)版本叫C4.5。vID3算法從樹(shù)的根節(jié)點(diǎn)處的所有訓(xùn)練樣本開(kāi)始，選取一個(gè)屬性來(lái)分區(qū)這些樣本。對(duì)屬性的每一個(gè)值產(chǎn)生一個(gè)分枝。分枝屬性值的相應(yīng)樣本子集被移到新生成的子節(jié)點(diǎn)上。 v自頂向下的決策樹(shù)的生成算法的關(guān)鍵性決策是對(duì)節(jié)點(diǎn)屬性值的選擇。ID3和C4.5算法的屬性選擇的基礎(chǔ)是基于節(jié)點(diǎn)所含的信息熵最小化。ID3的屬性選擇是根據(jù)一個(gè)假設(shè)，即：決策樹(shù)的復(fù)雜度和所給屬性值表達(dá)的信息量是密切相關(guān)的?；谛畔⒄摰姆椒?，對(duì)一個(gè)樣本進(jìn)行分類(lèi)時(shí)所做檢驗(yàn)的數(shù)量最小，要選擇的分類(lèi)屬性是可以給出最高信息增益的屬性，即信息熵最小化的屬性。ID3的擴(kuò)展是C4.5算法，C4.5算法把分類(lèi)屬性擴(kuò)展到數(shù)字屬性。 v2 C4.5算法：生成一個(gè)決策樹(shù)vC4.5算法最重要的部分是由一組訓(xùn)練樣本生成一個(gè)初始決策樹(shù)的過(guò)程。該算法生成一個(gè)決策樹(shù)形式的分類(lèi)器，決策樹(shù)節(jié)點(diǎn)具有兩種類(lèi)型的結(jié)構(gòu)：一個(gè)葉節(jié)點(diǎn)，表示一個(gè)類(lèi)，一個(gè)決策點(diǎn)，它指定要在單個(gè)屬性值上進(jìn)行的檢驗(yàn)，對(duì)檢驗(yàn)的每個(gè)可能輸出有一個(gè)分枝和子樹(shù)。 v決策樹(shù)可以用來(lái)對(duì)一個(gè)新鮮樣本進(jìn)行分類(lèi)，這種分類(lèi)從該樹(shù)的根節(jié)點(diǎn)開(kāi)始，然后移動(dòng)樣本直至達(dá)葉節(jié)點(diǎn)。在每個(gè)非葉決策點(diǎn)處，確定該節(jié)點(diǎn)的屬性檢驗(yàn)結(jié)果，把注意力轉(zhuǎn)移到所選擇子樹(shù)的根節(jié)點(diǎn)上。例如，圖6-7a中的決策樹(shù)的分類(lèi)模型問(wèn)題，待分類(lèi)的樣本如圖6-7b所示，然后，該算法將生成一條通過(guò)節(jié)點(diǎn)A，C，F(xiàn)（葉節(jié)點(diǎn)）的路徑直到得出最終分類(lèi)決策，即類(lèi)2為止。 v 圖6-7 基于決策樹(shù)模型的一個(gè)新樣本的分類(lèi) v C4.5算法的構(gòu)架是基于享特的CLS方法，其通過(guò)一組訓(xùn)練樣本T構(gòu)造一個(gè)決策樹(shù)。我們用 C1，C2，CK來(lái)表示這些類(lèi)。集合T所含的內(nèi)容信息有3種可能性：v 1T包含一個(gè)或更多的樣本，它們?nèi)繉儆趩蝹€(gè)的類(lèi)Cj。那么T的決策樹(shù)是由類(lèi)C1標(biāo)識(shí)的一個(gè)葉節(jié)點(diǎn)。v 2T不包含樣本。決策樹(shù)也是一個(gè)葉，但和該葉關(guān)聯(lián)的類(lèi)由不同于T的信息決定，如T中的絕大多數(shù)類(lèi)。C4.5算法以在所給節(jié)點(diǎn)的雙親上出現(xiàn)最頻繁的類(lèi)作為準(zhǔn)則。v 3T包含屬于不同類(lèi)的樣本。這種情況下，是把T精化成朝向一個(gè)單類(lèi)樣本集的樣本子集。根據(jù)某一個(gè)屬性，選擇具有一個(gè)或更多互斥的輸出 O1，O2，On 的合適檢驗(yàn)。T被分區(qū)成子集T1，T2，Tn，其中Ti包括T中所選擇的檢驗(yàn)的輸出是Oi的所有樣本。T的決策樹(shù)包括標(biāo)識(shí)檢驗(yàn)的一個(gè)決策點(diǎn)和每個(gè)可能輸出的一個(gè)分枝（圖6-7a中的決策樹(shù)的節(jié)點(diǎn)A，B和C是這種類(lèi)型節(jié)點(diǎn)的例子）。 6.3 基于解釋的學(xué)習(xí)v基于解釋的學(xué)習(xí)是八十年代中期興起的新型機(jī)器學(xué)習(xí)方法，是分析學(xué)習(xí)的主要方式，與基于大量訓(xùn)練例作歸納推理的數(shù)據(jù)密集型學(xué)習(xí)方法不同，基于解釋的學(xué)習(xí)是知識(shí)密集型的，可克服歸納學(xué)習(xí)因缺乏領(lǐng)域知識(shí)的引導(dǎo)而面臨的問(wèn)題?；诮忉尩膶W(xué)習(xí)通過(guò)應(yīng)用領(lǐng)域理論（領(lǐng)域知識(shí)）對(duì)單一事例所作的分析，構(gòu)造出求解過(guò)程的因果解釋結(jié)構(gòu)，并獲取控制知識(shí)，用于指導(dǎo)以后求解類(lèi)似的問(wèn)題。 v一、基于解釋學(xué)習(xí)的工作原理v 基于解釋學(xué)習(xí)也是屬于通過(guò)實(shí)例學(xué)習(xí)的方法，與通過(guò)實(shí)例學(xué)習(xí)的方法與眾不同之處在于學(xué)習(xí)系統(tǒng)除了實(shí)例之外，還需要具備有關(guān)領(lǐng)域的知識(shí)，并且能夠根據(jù)這些知識(shí)對(duì)實(shí)例進(jìn)行分析，從而構(gòu)成解釋?zhuān)a(chǎn)生規(guī)則。 v 1986年Mitchell等人提出了基于解釋學(xué)習(xí)的系統(tǒng)工作步驟：v 1產(chǎn)生解釋v系統(tǒng)得到實(shí)例后首先進(jìn)行問(wèn)題求解，由目標(biāo)反向推理，從領(lǐng)域知識(shí)庫(kù)存中尋找有關(guān)規(guī)則，使基后件與目標(biāo)匹配。找到這樣的規(guī)則后，就把目標(biāo)作為后件，該規(guī)則作為前件，并記錄這一因果關(guān)系。然后以規(guī)則的前件作為子目標(biāo)，進(jìn)一步反復(fù)分解。如此反復(fù)沿著因果鏈進(jìn)行，直到求解結(jié)束。一旦得到解，便證明了該例的目標(biāo)是可滿(mǎn)足的由此也得到證明的因果解釋結(jié)構(gòu)。v v2對(duì)解釋結(jié)構(gòu)的概括v對(duì)所得到的解釋結(jié)構(gòu)以及事件進(jìn)行概括，是采用將常量轉(zhuǎn)換為變量，去掉一些不重要的信息，僅保留求解所心需的那些關(guān)鍵信息，再由組合形成產(chǎn)生式規(guī)則，從而獲得概括性的控制信息。vMitchell等人綜合了以前各種基于解釋的概括方法，提出了一個(gè)般化，獨(dú)立具體領(lǐng)域的基于解釋的學(xué)習(xí)方法基于解釋的概括（EXPlanation-Bosed Generalization，簡(jiǎn)稱(chēng)EBG） v 給定：v 目標(biāo)概念：對(duì)于所學(xué)概念的一個(gè)初始描述（其尚不滿(mǎn)足可操作準(zhǔn)則）；v 訓(xùn)練例子：目標(biāo)概念的一個(gè)正例；v 領(lǐng)域理論：解釋訓(xùn)練例子為何是目標(biāo)概念正例時(shí)可用的規(guī)則和事實(shí)集合；v 可操作準(zhǔn)則：學(xué)到的知識(shí)（對(duì)于目標(biāo)概念的解釋?zhuān)┧枳駨牡谋硎拘问?，以使這些知識(shí)能用于問(wèn)題求解活動(dòng)。 v 獲?。簐對(duì)于目標(biāo)概念的一個(gè)特化描述，其是訓(xùn)練例子的泛化，且滿(mǎn)足可操作準(zhǔn)則。v基于解釋的概括過(guò)程有二個(gè)階段：v (1) 解釋?zhuān)菏褂妙I(lǐng)域理論建立一個(gè)證明訓(xùn)練例子滿(mǎn)足目標(biāo)概念定義（初始描述）的解釋結(jié)構(gòu)；該結(jié)構(gòu)可表示為一顆證明推理樹(shù)，又稱(chēng)解釋樹(shù)，其每個(gè)分枝的葉節(jié)點(diǎn)上的表達(dá)式都必須滿(mǎn)足可操作準(zhǔn)則。v (2) 泛化：通過(guò)將解釋結(jié)構(gòu)中的常量變換為變量（實(shí)現(xiàn)對(duì)于訓(xùn)練例子的泛化），獲得對(duì)于目標(biāo)概念的一個(gè)特化描述，使其滿(mǎn)足可操作準(zhǔn)則：v * 基于解釋結(jié)構(gòu)對(duì)目標(biāo)概念進(jìn)行回歸(regressing)， v * 對(duì)回歸所得的表達(dá)式（相應(yīng)于解釋結(jié)構(gòu)中的葉節(jié)點(diǎn)）加以合取 6.3.2基于解釋學(xué)習(xí)的方法的舉例 v1問(wèn)題的邏輯描述v2. 產(chǎn)生解釋結(jié)構(gòu) v3. 概括 6.4基于案例的推理v基于案例的推理（case-based reasoning，CBR）同人類(lèi)的日常推理活動(dòng)十分接近，它來(lái)自于人類(lèi)的認(rèn)知心理活動(dòng)不同于傳統(tǒng)的基于知識(shí)系統(tǒng)，CBR系統(tǒng)所信賴(lài)的知識(shí)主要是系統(tǒng)所存儲(chǔ)的相關(guān)領(lǐng)域中以前解決問(wèn)題的具體記錄。 v1.CBR系統(tǒng)的特點(diǎn)v羅杰沙克（Roger Schank）是CBR研究的開(kāi)創(chuàng)者，沙克（Schank）指出，CBR方法研究的原始動(dòng)機(jī)，主要來(lái)源于對(duì)人類(lèi)推理活動(dòng)中“回憶”的重要地位的認(rèn)識(shí) v傳統(tǒng)的基于知識(shí)系統(tǒng)（主要指知識(shí)表示采用產(chǎn)生式規(guī)則或框架架或語(yǔ)義網(wǎng)絡(luò)的專(zhuān)家系統(tǒng)，ES）存在一定的困難，如：v知識(shí)獲取的瓶頸問(wèn)題v知識(shí)庫(kù)維護(hù)的困難v推理鏈不能太長(zhǎng)v固定的求解范圍 vCBR方法在以下方面對(duì)基于規(guī)則的系統(tǒng)做出了改進(jìn)：v以下討論都假定非CBR知識(shí)系統(tǒng)的知識(shí)表示都采用產(chǎn)生式規(guī)則。1.知識(shí)獲取2.知識(shí)庫(kù)維護(hù)3.解決問(wèn)題的范圍5.解質(zhì)量4.求解過(guò)程 v2.CBR系統(tǒng)的體系結(jié)構(gòu)v一個(gè)CBR推理和學(xué)習(xí)過(guò)程可以分解為下面四個(gè)步驟：vstep1.從案例庫(kù)中檢索出與新案例最相似的案例或案例集；vstep2.把step1獲得的案例（或案例集）中的信息和知識(shí)復(fù)用到新問(wèn)題上；vstep3.修正所建議的解答；vstep4.把該次獲得的經(jīng)驗(yàn)保存起來(lái)，以備將來(lái)來(lái)使用。 6.4.3學(xué)習(xí)方法v基于案例的推理通過(guò)下面幾種方法來(lái)完成它的大部分學(xué)習(xí)：v新案例的積累。保存成功的和失敗的新案例。 v建立、修改和撤消指向案例的索引路徑，完善索引機(jī)制。 v歸納學(xué)習(xí)。 vCBR方法的實(shí)現(xiàn)一般包含下面幾個(gè)主要步聚：案例表示，索引和存儲(chǔ)，檢索，適應(yīng)修改，評(píng)估和學(xué)習(xí)等。v(1)案例表示v基于案例的推理系統(tǒng)利用案例記錄以前的問(wèn)題求解的情況，應(yīng)該包括與問(wèn)題的解答有關(guān)的一切重要信息。v從問(wèn)題求解角度來(lái)看，案例應(yīng)包含對(duì)問(wèn)題整體情況的描述，還應(yīng)包含對(duì)問(wèn)題的解或解決方法的描述。所以案例可被表成一個(gè)有序?qū)Γ骸?v（2）索引v案例庫(kù)的索引（indexing）的目標(biāo)是提供一種案例庫(kù)的搜索機(jī)制，使得在將來(lái)的檢索中能夠快速找出符合需要的案例或案例集。v一個(gè)案例的索引就是這個(gè)案例的重要關(guān)鍵字的集合，這些關(guān)鍵字可以將這個(gè)案例同其他案例區(qū)分開(kāi)來(lái) v索引問(wèn)題的主要任務(wù)包括：選擇什么類(lèi)型的索引、如何定義索引詞匯表、如何構(gòu)建索引的搜索空間等。 v(3)案例檢索v檢索任務(wù)開(kāi)始于一個(gè)描述待求問(wèn)題的新案例，利用案例庫(kù)索引機(jī)制，根據(jù)相似性度量方法，在某種相似性程度閾值下，從案例庫(kù)中找出一組與新案例匹配較好的舊案例，并從中選擇出一個(gè)最佳的案例。v檢索任務(wù)的子任務(wù)包括：特性鑒別（indentify feature），初始匹配（initially match），搜(search)和選擇(select)。 v(4)相似性度量v相似性度量（similarity measure）在CBR系統(tǒng)中十分重要，合適的度量方法可以迅速、準(zhǔn)確地找到所需要的案例。vCBR系統(tǒng)的相似性度量方法主要使用基于距離（基于計(jì)算）的方法，考慮到具體應(yīng)用環(huán)境的特點(diǎn)擴(kuò)展了的相似性度量方法和最近鄰法（NNh,the nearest neighbor method）。 v(5)適應(yīng)性修改v適應(yīng)性修改可以被簡(jiǎn)單地理解為把解決文案的一部分用其他的內(nèi)容替換，或者修改整個(gè)解決方案。適應(yīng)性修改可以有幾種形式苛以直接向解決方案中插入一些新內(nèi)容，也呆以從解決方案中刪除一些內(nèi)容，可以替換解決方案的某一部分內(nèi)容，也可以將某一部分內(nèi)容改造。但是，要使CBR系統(tǒng)得到足夠的適應(yīng)性修改知識(shí)(Adaptation knowledge)是一件十分困難的任務(wù)。 v科洛德（Kolodner）提出了十種適應(yīng)性修改的方法。v .重新例化v .參數(shù)調(diào)整v .局部搜索v詢(xún)問(wèn)/查詢(xún)記憶（v .特殊化搜索v .基于案例的替換v .常識(shí)轉(zhuǎn)化v .模型制導(dǎo)的修改補(bǔ)v .特定目的的修改和修補(bǔ) v .推導(dǎo)重放上述的1至6屬替換方法，7和8屬于轉(zhuǎn)化方法 v(6)評(píng)估和學(xué)習(xí)v評(píng)估任務(wù)需要在現(xiàn)實(shí)環(huán)境中應(yīng)用該案例解答的結(jié)果，可以通過(guò)詢(xún)問(wèn)專(zhuān)家或在現(xiàn)實(shí)世界中具體執(zhí)行任務(wù)來(lái)實(shí)現(xiàn)。這通常是CBR系統(tǒng)外部的一個(gè)步驟。根據(jù)應(yīng)用的類(lèi)型，評(píng)估結(jié)果可能需要一段時(shí)間。當(dāng)某案例的評(píng)估結(jié)果沒(méi)有得出時(shí)，該案例應(yīng)標(biāo)記為未評(píng)估案例。v學(xué)習(xí)過(guò)程把新案例中有意義的部分保存到系統(tǒng)的知識(shí)庫(kù)中。它包括從案例中選擇哪種信息進(jìn)行保存，以什么形式保存，為新案例建立哪些索引，如何建立這些索引，如何存儲(chǔ)新案例等等。 v 4. 結(jié)論v基于案例的推理是人工智能領(lǐng)域中較新出現(xiàn)的一種重要的基于知識(shí)的問(wèn)題求解和學(xué)習(xí)方法。作為一種基于經(jīng)驗(yàn)的問(wèn)題求解技術(shù)，基于案例的推理（CBR）可以理解為修改舊的解決方案滿(mǎn)足新的需要；使用舊案例解釋新情況、評(píng)價(jià)新方案、構(gòu)造新問(wèn)題的解答。學(xué)習(xí)是CBR推理行為的副產(chǎn)品，它獲得過(guò)去的經(jīng)驗(yàn)并在以后的推理中能夠回憶起來(lái)，這樣它的推理能力和效率都能得到提高。v基于案例的推理系統(tǒng)的推理質(zhì)量取決它具有的經(jīng)驗(yàn)，即在那些舊經(jīng)驗(yàn)的基礎(chǔ)上理解新情況的能力、修改的能力、以及評(píng)價(jià)和改錯(cuò)的能力。基于案例的推理程序的主要過(guò)程是案例存儲(chǔ)、檢索、修改及審查。 6.5加強(qiáng)學(xué)習(xí)v加強(qiáng)學(xué)習(xí)是一種以環(huán)境反饋?zhàn)鳛檩斎氲摹⑻厥獾?、適應(yīng)環(huán)境的機(jī)器學(xué)習(xí)方法。所謂加強(qiáng)學(xué)習(xí)是指從環(huán)境狀態(tài)到行為映射的學(xué)習(xí)，以使系統(tǒng)行為從環(huán)境中獲得的累積獎(jiǎng)賞值最大。 v加強(qiáng)學(xué)習(xí)通常包括兩個(gè)方面的含義：一方面是將加強(qiáng)學(xué)習(xí)作為一類(lèi)問(wèn)題；另一方面是指解決這類(lèi)問(wèn)題的一種技術(shù)。v加強(qiáng)學(xué)習(xí)（reinforcement learning）又稱(chēng)再勵(lì)學(xué)習(xí)或評(píng)價(jià)學(xué)習(xí)，是一種重要的機(jī)器學(xué)習(xí)方法，在智能控制機(jī)器人及分析預(yù)測(cè)等領(lǐng)域有許多應(yīng)用。 6.5.1加強(qiáng)學(xué)習(xí)基本方法v在加強(qiáng)學(xué)習(xí)技術(shù)中首先對(duì)隨機(jī)的、離散狀態(tài)、離散時(shí)間這一類(lèi)問(wèn)題進(jìn)行數(shù)學(xué)建模。在實(shí)際應(yīng)用中，最常采用的是馬爾可夫模型。表2中給出最常用的幾種馬氏模型。 v表2 常用的幾種馬氏模型 是否智能系統(tǒng)行為控制環(huán)境狀態(tài)轉(zhuǎn)移？ 馬氏模型 否 是 否 馬爾可夫鏈 馬氏決策過(guò)程 是否環(huán)境為部 分可感知？ 是 隱馬爾可夫模型 部分感知馬氏決策過(guò)程 v下面給出馬氏決策過(guò)程（Markov Decision Process，MDP）建模的形式化定義：v馬氏決策過(guò)程 由四元組定義。包含一個(gè)環(huán)境狀態(tài)集S，系統(tǒng)行為集合A，獎(jiǎng)賞函數(shù)R：SA和狀態(tài)轉(zhuǎn)移函數(shù)P：SAPD（S）。記R（s，a，s）為系統(tǒng)在狀態(tài)s采用a動(dòng)作使環(huán)境狀態(tài)轉(zhuǎn)移到s獲得的瞬時(shí)獎(jiǎng)賞值；記P（s，a，s）為系統(tǒng)在狀態(tài)s采用a動(dòng)作使環(huán)境狀態(tài)轉(zhuǎn)移到s的概率。 v馬氏決策過(guò)程的本質(zhì)是：當(dāng)前狀態(tài)向下一狀態(tài)轉(zhuǎn)移的概率和獎(jiǎng)賞值只取決于當(dāng)前狀態(tài)和選擇的動(dòng)作，而與歷史狀態(tài)和歷史動(dòng)作無(wú)關(guān)。因此在已知狀態(tài)轉(zhuǎn)移概率函數(shù)P和獎(jiǎng)賞函數(shù)R的()環(huán)境模型知識(shí)下，可以采用動(dòng)態(tài)規(guī)劃技術(shù)求解最優(yōu)策略。而加強(qiáng)學(xué)習(xí)著重研究在P函數(shù)和R函數(shù)未知的情況下，系統(tǒng)如何學(xué)習(xí)最優(yōu)行為策略。加強(qiáng)學(xué)習(xí)可以簡(jiǎn)化為圖6-13的結(jié)構(gòu)。 v圖6-13 加強(qiáng)學(xué)習(xí)結(jié)構(gòu) 6.5.2加強(qiáng)學(xué)習(xí)技術(shù)目前主要研究方向v 1部分感知馬氏決策過(guò)程中的強(qiáng)化學(xué)習(xí)v在實(shí)際的問(wèn)題中，系統(tǒng)往往無(wú)法完全感知環(huán)境狀態(tài)信息。即使環(huán)境屬于馬爾可夫型，但由于感知的不全面，對(duì)于狀態(tài)之間的差異也無(wú)法區(qū)別。因此部分感知問(wèn)題屬于非馬爾可夫型環(huán)境。在部分感知問(wèn)題中，如果不對(duì)強(qiáng)化學(xué)習(xí)算法進(jìn)行任何處理就加以應(yīng)用的話(huà)，學(xué)習(xí)算法將無(wú)法收斂。v在部分感知模型中，不僅考慮動(dòng)作的不確定性，同時(shí)也考慮狀態(tài)的不確定性。這種環(huán)境描述更接近現(xiàn)實(shí)世界，因此應(yīng)用面比馬氏決策模型更廣。解決部分感知問(wèn)題的基本思路是將部分感知環(huán)境轉(zhuǎn)換為馬氏決策模型描述，即假設(shè)存在部分可觀(guān)測(cè)（或不可觀(guān)測(cè)）的隱狀態(tài)集S滿(mǎn)足馬爾可夫?qū)傩浴?v2加強(qiáng)學(xué)習(xí)中的函數(shù)估計(jì)v對(duì)于大規(guī)模MDP或連續(xù)空間MDP問(wèn)題中，加強(qiáng)學(xué)習(xí)不可能遍歷所有狀態(tài)。因此要求加強(qiáng)學(xué)習(xí)的值函數(shù)具有一定泛化能力。加強(qiáng)學(xué)習(xí)中的映射關(guān)系包括：SA、SR、SAR、SAS等等。加強(qiáng)學(xué)習(xí)中的函數(shù)估計(jì)本質(zhì)就是用參數(shù)化的函數(shù)逼近這些映射。 v3分層加強(qiáng)學(xué)習(xí)v經(jīng)典馬氏決策過(guò)程模型只考慮了決策的順序性而忽略決策的時(shí)間性。基于馬氏決策過(guò)程的加強(qiáng)學(xué)習(xí)都假設(shè)動(dòng)作在單個(gè)時(shí)間步完成，因而無(wú)法處理需要在多個(gè)時(shí)間步完成的動(dòng)作。為解決此問(wèn)題，引入半馬氏決策過(guò)程（SMDP，Semi-MDP）模型。在SMDP模型中，每個(gè)行為動(dòng)作的時(shí)間間隔作為變量（整數(shù)或?qū)崝?shù)），并進(jìn)一步可以細(xì)分為連續(xù)時(shí)間-離散事件SMDP和離散時(shí)間SMDP兩種模型。在后者中，行為決策只在單位時(shí)間片的正整數(shù)倍做出，較前者模型簡(jiǎn)單。 v4 多agent加強(qiáng)學(xué)習(xí)v多agent加強(qiáng)學(xué)習(xí)是加強(qiáng)學(xué)習(xí)研究中非常重要的研究方向之一。在多agent系統(tǒng)中，環(huán)境在多個(gè)agent的聯(lián)合動(dòng)作下進(jìn)行狀態(tài)的遷移。對(duì)于單個(gè)agent來(lái)講，由于其只能確定自身agent的行為動(dòng)作，因此體現(xiàn)出一種行為動(dòng)作上的“部分感知”，從而產(chǎn)生出另一種形式的非標(biāo)準(zhǔn)馬爾可夫環(huán)境。多agent加強(qiáng)學(xué)習(xí)機(jī)制被廣泛應(yīng)用到各個(gè)領(lǐng)域，例如游戲、郵件路由選擇、電梯群控系統(tǒng)以及機(jī)器人設(shè)計(jì)等等。 6.5.3結(jié)論v本部分綜述了加強(qiáng)學(xué)習(xí)技術(shù)基本原理和目前主要研究方向。盡管在過(guò)去的二十年中，加強(qiáng)學(xué)習(xí)技術(shù)研究取得了突破性進(jìn)展，但目前仍然存在許多有待解決的問(wèn)題。在今后的若干年中，以下方面也將成為強(qiáng)化學(xué)習(xí)研究的重要研究?jī)?nèi)容。 1.加強(qiáng)學(xué)習(xí)與其他學(xué)習(xí)技術(shù)相結(jié)合的研究 v眾所周知，加強(qiáng)學(xué)習(xí)的一個(gè)主要缺點(diǎn)是收斂慢。其根本原因在于學(xué)習(xí)過(guò)程僅僅從經(jīng)驗(yàn)獲得的獎(jiǎng)賞中進(jìn)行策略的改進(jìn)，而忽略了大量其他有用的領(lǐng)域信息。因此，如何結(jié)合其他機(jī)器學(xué)習(xí)技術(shù)，如神經(jīng)網(wǎng)絡(luò)、符號(hào)學(xué)習(xí)等技術(shù)，來(lái)幫助系統(tǒng)加快學(xué)習(xí)速度是強(qiáng)化學(xué)習(xí)研究和應(yīng)用的重要方向。目前，結(jié)合技術(shù)研究的主要難點(diǎn)在于：如何從理論上證明和保證學(xué)習(xí)算法的收斂性。 v2.非馬氏決策過(guò)程中的新型加強(qiáng)學(xué)習(xí)算法研究 v經(jīng)典的馬氏決策模型是相當(dāng)簡(jiǎn)單的，除了部分感知、連續(xù)狀態(tài)、半馬氏決策過(guò)程等模型外，在實(shí)際應(yīng)用中還存在大量更加復(fù)雜的模型。例如，在圖象的馬爾可夫隨機(jī)場(chǎng)模型中，狀態(tài)的遷移是由歷史多個(gè)相鄰狀態(tài)決定。因此，在更復(fù)雜馬氏決策模型中發(fā)展有效的加強(qiáng)學(xué)習(xí)算法也將是未來(lái)重要的研究方向之一。 v3.加強(qiáng)學(xué)習(xí)應(yīng)用研究v目前，加強(qiáng)學(xué)習(xí)的應(yīng)用主要可以分為四類(lèi)：制造過(guò)程控制、各種任務(wù)調(diào)度、機(jī)器人設(shè)計(jì)和游戲。另外，加強(qiáng)學(xué)習(xí)在學(xué)習(xí)分類(lèi)器（Learning Classifier System）中的應(yīng)用也逐漸成為研究的熱點(diǎn)。從當(dāng)前看來(lái)，加強(qiáng)學(xué)習(xí)的應(yīng)用逐步向一些新的機(jī)器學(xué)習(xí)任務(wù)上拓展，如Web Log Mining、Web Crawling、Classification等等。因此，如何在新應(yīng)用上快速、有效地部署和應(yīng)用加強(qiáng)學(xué)習(xí)技術(shù)也是放在研究人員面前的挑戰(zhàn)之一。