機(jī)器學(xué)習(xí)課件

第六章

機(jī)器學(xué)習(xí)7/4/20231第六章機(jī)器學(xué)習(xí)主要內(nèi)容：機(jī)器學(xué)習(xí)概述歸納學(xué)習(xí)例如學(xué)習(xí)基于決策樹的歸納學(xué)習(xí)方法ID3類比學(xué)習(xí)基于范例的學(xué)習(xí)解釋學(xué)習(xí)支持向量機(jī)7/4/20232學(xué)習(xí)經(jīng)典定義：利用經(jīng)驗(yàn)改善系統(tǒng)自身的性能[T.Mitchell,Book97]隨著該領(lǐng)域的開展，主要做智能數(shù)據(jù)分析典型任務(wù)：預(yù)測(cè)例如：天氣預(yù)報(bào)7/4/20233機(jī)器學(xué)習(xí)〔續(xù)〕數(shù)據(jù)挖掘數(shù)據(jù)庫(kù)機(jī)器學(xué)習(xí)數(shù)據(jù)分析技術(shù)數(shù)據(jù)管理技術(shù)7/4/20234美國(guó)航空航天局JPL實(shí)驗(yàn)室的科學(xué)家在?Science?〔2001年9月〕上撰文指出：機(jī)器學(xué)習(xí)對(duì)科學(xué)研究的整個(gè)過(guò)程正起到越來(lái)越大的支持作用，……，該領(lǐng)域在今后的假設(shè)干年內(nèi)將取得穩(wěn)定而快速的開展重要性生物信息學(xué)計(jì)算金融學(xué)分子生物學(xué)行星地質(zhì)學(xué)……工業(yè)過(guò)程控制機(jī)器人……遙感信息處理信息平安機(jī)器學(xué)習(xí)7/4/20235重要性：例子—網(wǎng)絡(luò)平安入侵檢測(cè)：是否是入侵？是何種入侵？如何檢測(cè)？歷史數(shù)據(jù)：以往的正常訪問模式及其表現(xiàn)、以往的入侵模式及其表現(xiàn)……對(duì)當(dāng)前訪問模式分類這是一個(gè)典型的預(yù)測(cè)型機(jī)器學(xué)習(xí)問題常用技術(shù)：神經(jīng)網(wǎng)絡(luò)決策樹支持向量機(jī)k近鄰序列分析聚類…………7/4/20236重要性：例子—生物信息學(xué)常用技術(shù)：神經(jīng)網(wǎng)絡(luò)支持向量機(jī)隱馬爾可夫模型k近鄰決策樹序列分析聚類…………7/4/20237重要性〔續(xù)〕機(jī)器學(xué)習(xí)在過(guò)去十年中開展極為迅速，今后會(huì)快速穩(wěn)定地開展、對(duì)科學(xué)做出更大奉獻(xiàn)的領(lǐng)域[E.Mjolsness&D.DesCoste,Science01]人工智能中最活潑、應(yīng)用潛力最明顯的領(lǐng)域〔之一〕[T.G.Dietterich,AIMag97]美國(guó)、歐洲各國(guó)都投入了大量人力物力大型公司如波音、微軟、通用電器等都有研究課題已有一些研究成果進(jìn)入產(chǎn)品7/4/20238機(jī)器學(xué)習(xí)角色的轉(zhuǎn)變?nèi)绻覀兿胱龀鲋匾姆瞰I(xiàn)，首先需要把握住該領(lǐng)域開展的脈搏機(jī)器學(xué)習(xí)現(xiàn)在似乎已經(jīng)開展到一個(gè)新階段機(jī)器學(xué)習(xí)起源于人工智能對(duì)人類學(xué)習(xí)能力的追求，上一階段的研究幾乎完全局限在人工智能這一領(lǐng)域中〔學(xué)習(xí)本身是目的〕而現(xiàn)在，機(jī)器學(xué)習(xí)已經(jīng)開始進(jìn)入了計(jì)算機(jī)科學(xué)的不同領(lǐng)域，甚至其他學(xué)科，成為一種支持技術(shù)、效勞技術(shù)〔學(xué)習(xí)本身是手段〕7/4/20239挑戰(zhàn)問題(1)：泛化能力共性問題：幾乎所有的領(lǐng)域，都希望越準(zhǔn)越好提高泛化能力是永遠(yuǎn)的追求目前泛化能力最強(qiáng)的技術(shù)：支持向量機(jī)〔SVM〕產(chǎn)生途徑：理論->實(shí)踐集成學(xué)習(xí)〔ensemblelearning〕產(chǎn)生途徑：實(shí)踐->理論7/4/202310挑戰(zhàn)問題(1)：泛化能力〔續(xù)〕第一個(gè)挑戰(zhàn)問題：今后10年能否更“準(zhǔn)〞？如果能，會(huì)從哪兒來(lái)？7/4/202311挑戰(zhàn)問題(2)：速度共性問題：幾乎所有的領(lǐng)域，都希望越快越好加快速度也是永遠(yuǎn)的追求“訓(xùn)練速度〞vs.“測(cè)試速度訓(xùn)練速度快的往往測(cè)試速度慢：k近鄰測(cè)試速度快的往往訓(xùn)練速度慢：神經(jīng)網(wǎng)絡(luò)7/4/202312挑戰(zhàn)問題(2)：速度〔續(xù)〕第二個(gè)挑戰(zhàn)問題：今后10年能否更“快〞？能做到“訓(xùn)練快〞、“測(cè)試也快〞嗎？如果能，如何做？7/4/202313挑戰(zhàn)問題(3)：可理解性共性問題：絕大多數(shù)領(lǐng)域都希望有“可理解性〞例子：醫(yī)療診斷地震預(yù)測(cè)目前強(qiáng)大的技術(shù)幾乎都是〔或根本上是〕“黑盒子〞神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、集成學(xué)習(xí)“黑盒子〞能滿足需要嗎？7/4/202314挑戰(zhàn)問題(3)：可理解性〔續(xù)〕第三個(gè)挑戰(zhàn)問題：今后10年能否產(chǎn)生“白盒子〞？是和“黑盒子〞完全不同的東西，還是從“黑盒子〞變出來(lái)？7/4/202315挑戰(zhàn)問題(4)：數(shù)據(jù)利用能力傳統(tǒng)的機(jī)器學(xué)習(xí)技術(shù)—>對(duì)有標(biāo)記數(shù)據(jù)進(jìn)行學(xué)習(xí)“標(biāo)記〞——>事件所對(duì)應(yīng)的結(jié)果共性問題：隨著數(shù)據(jù)收集能力飛速提高、Internet的出現(xiàn)，在大多數(shù)領(lǐng)域中都可以很容易地獲得大量未標(biāo)記數(shù)據(jù)例子：醫(yī)學(xué)圖象分析垃圾郵件過(guò)濾沒有標(biāo)記的數(shù)據(jù)是沒用的嗎？7/4/202316挑戰(zhàn)問題(4)：數(shù)據(jù)利用能力〔續(xù)〕共性問題：在絕大多數(shù)領(lǐng)域中都會(huì)遇到“壞〞數(shù)據(jù)，有時(shí)甚至只有“壞〞數(shù)據(jù)例子：海軍艦隊(duì)Web“壞〞數(shù)據(jù)——>大量噪音、屬性缺失、不一致、……傳統(tǒng)的“壞〞數(shù)據(jù)處理方式—>“扔掉〞“壞〞數(shù)據(jù)一點(diǎn)用也沒有嗎？7/4/202317第四個(gè)挑戰(zhàn)問題：今后10年能否“數(shù)據(jù)通吃〞？如何“吃〞？挑戰(zhàn)問題(4)：數(shù)據(jù)利用能力〔續(xù)〕7/4/202318挑戰(zhàn)問題(5)：代價(jià)敏感目前的機(jī)器學(xué)習(xí)技術(shù)—>降低錯(cuò)誤率“錯(cuò)誤〞是沒有區(qū)別的嗎？把“好〞當(dāng)成“壞〞把“壞〞當(dāng)成“好〞共性問題：大多數(shù)領(lǐng)域中的錯(cuò)誤代價(jià)都不一樣例子：入侵檢測(cè)癌癥診斷一樣嗎？7/4/202319第五個(gè)挑戰(zhàn)問題：今后10年能否“趨利避害〞？在到達(dá)較低的總錯(cuò)誤率的根底上，如何“趨〞、如何“避〞？挑戰(zhàn)問題(5)：代價(jià)敏感〔續(xù)〕7/4/202320挑戰(zhàn)問題：……More……在任何一個(gè)挑戰(zhàn)問題上取得突破性進(jìn)展，都可能成為對(duì)機(jī)器學(xué)習(xí)的重要奉獻(xiàn)7/4/2023216.1機(jī)器學(xué)習(xí)概述學(xué)習(xí)可能只是一個(gè)簡(jiǎn)單的聯(lián)想過(guò)程，給定了特定的輸入，就會(huì)產(chǎn)生特定的輸出。如：狗命令“坐〞行為“坐〞7/4/202322學(xué)習(xí)的成功是多種多樣的：學(xué)習(xí)識(shí)別客戶的購(gòu)置模式以便能檢測(cè)出信用卡欺詐行為，對(duì)客戶進(jìn)行扼要描述以便能對(duì)市場(chǎng)推廣活動(dòng)進(jìn)行定位，對(duì)網(wǎng)上內(nèi)容進(jìn)行分類并按用戶興趣自動(dòng)導(dǎo)入數(shù)據(jù)，貸款申請(qǐng)人的信用打分，燃?xì)鉁u輪的故障診斷等。7/4/2023236.1.1簡(jiǎn)單的學(xué)習(xí)模型

學(xué)習(xí)系統(tǒng)的根本結(jié)構(gòu)如下圖。環(huán)境學(xué)習(xí)知識(shí)庫(kù)執(zhí)行環(huán)境向系統(tǒng)的學(xué)習(xí)局部提供某些信息，學(xué)習(xí)局部利用這些信息修改知識(shí)庫(kù)，以增進(jìn)系統(tǒng)執(zhí)行局部完成任務(wù)的效能，執(zhí)行局部根據(jù)知識(shí)庫(kù)完成任務(wù)，同時(shí)把獲得的信息反響給學(xué)習(xí)局部。在具體的應(yīng)用中，環(huán)境、知識(shí)庫(kù)和執(zhí)行局部決定了具體的工作內(nèi)容，學(xué)習(xí)局部所需要解決的問題完全由上述三局部確定。7/4/202324影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的最重要的因素是環(huán)境向系統(tǒng)提供的信息。知識(shí)庫(kù)里存放的是指導(dǎo)執(zhí)行局部動(dòng)作的一般原那么，但環(huán)境向?qū)W習(xí)系統(tǒng)提供的信息卻是各種各樣的。如果信息的質(zhì)量比較高，與一般原那么的差異比較小，那么學(xué)習(xí)局部就比較容易處理。如果向?qū)W習(xí)系統(tǒng)提供的是雜亂無(wú)章的指導(dǎo)執(zhí)行具體動(dòng)作的具體信息，那么學(xué)習(xí)系統(tǒng)需要在獲得足夠數(shù)據(jù)之后，刪除不必要的細(xì)節(jié)，進(jìn)行總結(jié)推廣，形成指導(dǎo)動(dòng)作的一般原那么，放入知識(shí)庫(kù)。這樣，學(xué)習(xí)局部的任務(wù)就比較繁重，設(shè)計(jì)起來(lái)也較為困難。7/4/202325學(xué)習(xí)系統(tǒng)所進(jìn)行的推理并不完全是可靠的，它總結(jié)出來(lái)的規(guī)那么可能正確，也可能不正確，這要通過(guò)執(zhí)行效果加以檢驗(yàn)。正確的規(guī)那么能使系統(tǒng)的效能提高，應(yīng)予保存；不正確的規(guī)那么應(yīng)予修改或從數(shù)據(jù)庫(kù)中刪除。知識(shí)庫(kù)是影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的第二個(gè)因素。知識(shí)表示有多種形式，如特征向量、一階邏輯、產(chǎn)生式規(guī)那么、語(yǔ)義網(wǎng)絡(luò)框架等。選擇表示方式時(shí)要兼顧以下4個(gè)方面：7/4/202326(1)表達(dá)能力強(qiáng)。例如，如果研究的是一些孤立的木塊，那么可選用特征向量表示方式。用(<顏色>，<形狀>，<體積>)這種形式的向量表示木塊。用一階邏輯公式描述木塊之間的相互關(guān)系，如用公式表示一個(gè)紅色的木塊在一個(gè)綠色的木塊上面。7/4/202327(2)易于推理。如，在推理過(guò)程中經(jīng)常會(huì)遇到判別兩種表示方式是否等價(jià)的問題。在特征向量表示方式中，解決這個(gè)問題比較容易；在一階邏輯表示方式中，解決這個(gè)問題要花費(fèi)較高的計(jì)算代價(jià)。因?yàn)閷W(xué)習(xí)系統(tǒng)通常要在大量的描述中查找，很高的計(jì)算代價(jià)會(huì)嚴(yán)重影響查找的范圍。因此如果只研究孤立的木塊而不考慮相互的位置，那么應(yīng)該使用特征向量表示。7/4/202328(3)容易修改知識(shí)庫(kù)學(xué)習(xí)系統(tǒng)的本質(zhì)要求它不斷地修改自己的知識(shí)庫(kù)，當(dāng)推廣得出一般執(zhí)行規(guī)那么后，要加到知識(shí)庫(kù)中去。當(dāng)發(fā)現(xiàn)某些規(guī)那么不適用時(shí)要將其刪除。因此學(xué)習(xí)系統(tǒng)的知識(shí)表示，一般都采用明確、統(tǒng)一的方式，如特征向量、產(chǎn)生式規(guī)那么等，以利于知識(shí)庫(kù)的修改。新增加的知識(shí)可能與知識(shí)庫(kù)中原有的知識(shí)相矛盾，因此有必要對(duì)整個(gè)知識(shí)庫(kù)作全面調(diào)整。刪除某一知識(shí)也可能使許多其他知識(shí)失效，因此需要進(jìn)一步作全面檢查。7/4/202329(4)知識(shí)表示易于擴(kuò)展隨著系統(tǒng)學(xué)習(xí)能力的提高，單一的知識(shí)表示己經(jīng)不能滿足需要；一個(gè)系統(tǒng)可能同時(shí)使用幾種知識(shí)表示方式。有時(shí)還要求系統(tǒng)自己能夠構(gòu)造出新的表示方式，以適應(yīng)外界信息不斷變化的需要。因此要求系統(tǒng)包含如何構(gòu)造表示方式的元級(jí)描述?，F(xiàn)在，人們把這種元級(jí)知識(shí)也看成是知識(shí)庫(kù)的一局部。這種元級(jí)知識(shí)使學(xué)習(xí)系統(tǒng)的能力得到極大提高，使其能夠?qū)W會(huì)更加復(fù)雜的東西，不斷地?cái)U(kuò)大它的知識(shí)領(lǐng)域和執(zhí)行能力。7/4/202330學(xué)習(xí)系統(tǒng)不能在全然沒有任何知識(shí)的情況下憑空獲取知識(shí)，每一個(gè)學(xué)習(xí)系統(tǒng)都要求具有某些知識(shí)以理解環(huán)境提供的信息，分析比較，作出假設(shè)，檢驗(yàn)并修改這些假設(shè)。因此，學(xué)習(xí)系統(tǒng)是對(duì)現(xiàn)有知識(shí)的擴(kuò)展和改進(jìn)。7/4/2023316.1.2什么是機(jī)器學(xué)習(xí)學(xué)習(xí)是系統(tǒng)在不斷重復(fù)的工作中對(duì)本身能力的增強(qiáng)或者改進(jìn)，使得系統(tǒng)在下一次執(zhí)行同樣任務(wù)或類似任務(wù)時(shí)，比現(xiàn)在做得更好或效率更高。例子：機(jī)器學(xué)習(xí)是一門研究機(jī)器獲取新知識(shí)和新技能，并識(shí)別現(xiàn)有知識(shí)的人工智能分支。1959年Samuel設(shè)計(jì)了一個(gè)下棋程序，這個(gè)程序具有學(xué)習(xí)能力，它可以在不斷的對(duì)弈中改善自己的棋藝。4年后，這個(gè)程序戰(zhàn)勝了設(shè)計(jì)者本人。又過(guò)了3年，這個(gè)程序戰(zhàn)勝了美國(guó)一個(gè)保持8年之久的常勝不敗的冠軍。這個(gè)程序向人們展示了機(jī)器學(xué)習(xí)的能力。7/4/202332開展分四階段：(1)在20世紀(jì)50年代中葉到60年代中葉，屬于熱烈時(shí)期。在這個(gè)時(shí)期，所研究的是“沒有知識(shí)〞的學(xué)習(xí)，即“無(wú)知〞學(xué)習(xí)；其研究目標(biāo)是各類自組織系統(tǒng)和自適應(yīng)系統(tǒng)；其主要研究方法是不斷修改系統(tǒng)的控制參數(shù)以改進(jìn)系統(tǒng)的執(zhí)行能力，不涉及與具體任務(wù)有關(guān)的知識(shí)。指導(dǎo)本階段研究的理論根底是早在20世紀(jì)40年代就開始研究的神經(jīng)網(wǎng)絡(luò)模型。這個(gè)階段的研究導(dǎo)致了“模式識(shí)別〞的誕生，同時(shí)形成了兩種機(jī)器學(xué)習(xí)方法——判別函數(shù)法和進(jìn)化學(xué)習(xí)。Samuel的下棋程序就是使用判別函數(shù)法的典型例子。6.1.3機(jī)器學(xué)習(xí)研究概況7/4/202333(2)在20世紀(jì)60年代中葉至70年代中葉，被稱為冷靜時(shí)期。本階段的研究目標(biāo)是模擬人類的概念學(xué)習(xí)過(guò)程，并采用邏輯結(jié)構(gòu)或圖結(jié)構(gòu)作為機(jī)器內(nèi)部描述。機(jī)器能夠采用符號(hào)來(lái)描述概念(符號(hào)概念獲取)，并提出關(guān)于學(xué)習(xí)概念的各種假設(shè)。本階段的代表性工作神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)機(jī)因理論缺陷未能到達(dá)預(yù)期效果而轉(zhuǎn)入低潮。Winston的結(jié)構(gòu)學(xué)習(xí)系統(tǒng)和HayesRoth等人的基于邏輯的歸納學(xué)習(xí)系統(tǒng)。7/4/202334(3)從20世紀(jì)70年代中葉至80年代中葉，稱為復(fù)興時(shí)期。在這個(gè)時(shí)期，人們從學(xué)習(xí)單個(gè)概念擴(kuò)展到學(xué)習(xí)多個(gè)概念，探索不同的學(xué)習(xí)策略和各種學(xué)習(xí)方法。機(jī)器的學(xué)習(xí)過(guò)程一般都建立在大規(guī)模的知識(shí)庫(kù)上，實(shí)現(xiàn)知識(shí)強(qiáng)化學(xué)習(xí)。本階段開始把學(xué)習(xí)系統(tǒng)與各種應(yīng)用結(jié)合起來(lái)，促進(jìn)了機(jī)器學(xué)習(xí)的開展。在出現(xiàn)第一個(gè)專家學(xué)習(xí)系統(tǒng)之后，例如歸約學(xué)習(xí)系統(tǒng)成為研究的主流，自動(dòng)知識(shí)獲取成為機(jī)器學(xué)習(xí)的應(yīng)用研究目標(biāo)。1980年，在CMU召開了第一屆機(jī)器學(xué)習(xí)國(guó)際研討會(huì)。此后，機(jī)器歸納學(xué)習(xí)進(jìn)入應(yīng)用。1986年，雜志MachineLearning創(chuàng)刊。7/4/202335(4)機(jī)器學(xué)習(xí)的最新階段始于1986年。在這一時(shí)期，符號(hào)學(xué)習(xí)由“無(wú)知〞學(xué)習(xí)轉(zhuǎn)向有專門領(lǐng)域知識(shí)的增長(zhǎng)型學(xué)習(xí)，因而出現(xiàn)了有一定知識(shí)背景的分析學(xué)習(xí)。神經(jīng)網(wǎng)絡(luò)中的反向傳播算法獲得應(yīng)用?；谏锇l(fā)育進(jìn)化論的進(jìn)化學(xué)習(xí)系統(tǒng)和遺傳算法，因吸取了歸納學(xué)習(xí)與連接機(jī)制學(xué)習(xí)的長(zhǎng)處而受到重視?；谛袨橹髁x的強(qiáng)化學(xué)習(xí)系統(tǒng)因開展新算法和應(yīng)用連接機(jī)制學(xué)習(xí)遺傳算法的新成就而顯示出新的生命力。數(shù)據(jù)挖掘研究的蓬勃開展。7/4/202336它綜合應(yīng)用心理學(xué)、生物學(xué)和神經(jīng)生理學(xué)以及數(shù)學(xué)、自動(dòng)化和計(jì)算機(jī)科學(xué)形成機(jī)器學(xué)習(xí)的理論根底。結(jié)合各種學(xué)習(xí)方法的多種形式的集成學(xué)習(xí)系統(tǒng)研究正在興起。機(jī)器學(xué)習(xí)與人工智能各種根底問題的統(tǒng)一性觀點(diǎn)正在形成。各種學(xué)習(xí)方法的應(yīng)用范圍不斷擴(kuò)大，一局部已形成商品。數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)技術(shù)在生物醫(yī)學(xué)、金融管理、商業(yè)銷售等領(lǐng)域得到成功應(yīng)用。ML進(jìn)入新階段表現(xiàn)在：7/4/202337機(jī)器學(xué)習(xí)的研究概況學(xué)習(xí)過(guò)程與推理過(guò)程是緊密相連的，機(jī)器學(xué)習(xí)所采用的策略可分為：機(jī)械學(xué)習(xí)示教學(xué)習(xí)類比學(xué)習(xí)例如學(xué)習(xí)學(xué)習(xí)中所用的推理越多，系統(tǒng)的能力就越強(qiáng)。

機(jī)械學(xué)習(xí)就是記憶。這種學(xué)習(xí)策略不需要任何推理過(guò)程。外界輸入知識(shí)的表示方式與系統(tǒng)內(nèi)部的表示方式完全一致，不需要任何處理與轉(zhuǎn)換。7/4/202338雖然機(jī)械學(xué)習(xí)在方法上看來(lái)很簡(jiǎn)單，但由于計(jì)算機(jī)的存儲(chǔ)容量相當(dāng)大，檢索速度又相當(dāng)快，而且記憶精確、無(wú)絲毫誤差，所以也能產(chǎn)生人們難以預(yù)料的效果。Samuel的下棋程序就是采用了這種機(jī)械記憶策略。為了評(píng)價(jià)棋局的優(yōu)劣，他給每一個(gè)棋局都打了分，對(duì)自己有利的分?jǐn)?shù)高，不利的分?jǐn)?shù)低，走棋時(shí)盡量選擇使自己分?jǐn)?shù)高的棋局。這個(gè)程序可記住53000多個(gè)棋局及其分值，并能在對(duì)弈中不斷地修改這些分值以提高自己的水平，這對(duì)于人來(lái)說(shuō)是無(wú)論如何也辦不到的。7/4/202339機(jī)械學(xué)習(xí)示教學(xué)習(xí)類比學(xué)習(xí)例如學(xué)習(xí)

示教學(xué)習(xí)策略:對(duì)于使用示教學(xué)習(xí)策略的系統(tǒng)來(lái)說(shuō)，外界輸入知識(shí)的表達(dá)方式與內(nèi)部表達(dá)方式不完全一致，系統(tǒng)在接受外部知識(shí)時(shí)需要一點(diǎn)推理、翻譯和轉(zhuǎn)化工作。MYCIN，DENDRAL等專家系統(tǒng)在獲取知識(shí)上都采用這種學(xué)習(xí)策略。類比學(xué)習(xí)系統(tǒng)只能得到完成類似任務(wù)的有關(guān)知識(shí)，因此，學(xué)習(xí)系統(tǒng)必須能夠發(fā)現(xiàn)當(dāng)前任務(wù)與任務(wù)的相似點(diǎn)，由此制定出完成當(dāng)前任務(wù)的方案，因此，它比上述兩種學(xué)習(xí)策略需要更多的推理。7/4/202340采用例如學(xué)習(xí)策略的計(jì)算機(jī)系統(tǒng)，事先完全沒有完成任務(wù)的任何規(guī)律性的信息，所得到的只是一些具體的工作例子及工作經(jīng)驗(yàn)。系統(tǒng)需要對(duì)這些例子及經(jīng)驗(yàn)進(jìn)行分析、總結(jié)和推廣，得到完成任務(wù)的一般性規(guī)律，并在進(jìn)一步的工作中驗(yàn)證或修改這些規(guī)律，因此需要的推理是幾種策略中最多的此外，還有基于解釋的學(xué)習(xí)、強(qiáng)化學(xué)習(xí)和基于神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)等。機(jī)械學(xué)習(xí)示教學(xué)習(xí)類比學(xué)習(xí)例如學(xué)習(xí)

7/4/202341歸納學(xué)習(xí)歸納學(xué)習(xí)人類智能的重要表達(dá)；機(jī)器學(xué)習(xí)的核心技術(shù)之一；從提供的例如中抽象出結(jié)論的知識(shí)獲取過(guò)程。依據(jù)：具體的例如；目標(biāo)：一般性推論；能解釋例如；預(yù)見新事實(shí)。例如一般性推論新的事實(shí)歸納演繹7/4/2023421.歸納學(xué)習(xí)的模式和規(guī)那么一般的歸納推理結(jié)論只是保假的。從相同的實(shí)例集合中，可以提出不同的理論來(lái)解釋它，應(yīng)按某一標(biāo)準(zhǔn)選取最好的作為學(xué)習(xí)結(jié)果。人類知識(shí)的增長(zhǎng)主要得益于歸納學(xué)習(xí)方法。雖然歸納得出的新知識(shí)不像演繹推理結(jié)論那樣可靠，但存在很強(qiáng)的可證偽性，對(duì)于認(rèn)識(shí)的開展和完善具有重要的啟發(fā)意義。歸納學(xué)習(xí)(inductionlearning)是應(yīng)用歸納推理進(jìn)行學(xué)習(xí)的一種方法。根據(jù)歸納學(xué)習(xí)有無(wú)教師指導(dǎo)，可把它分為例如學(xué)習(xí)和觀察與發(fā)現(xiàn)學(xué)習(xí)。前者屬于有師學(xué)習(xí)，后者屬于無(wú)師學(xué)習(xí)。7/4/202343(1)歸納學(xué)習(xí)的模式給定：①觀察陳述F，用以表示有關(guān)某些對(duì)象、狀態(tài)、過(guò)程等的特定知識(shí)；②假定的初始?xì)w納斷言(可能為空)；③背景知識(shí)，用于定義有關(guān)觀察陳述、候選歸納斷言以及任何相關(guān)問題領(lǐng)域知識(shí)、假設(shè)和約束，其中包括能夠刻畫所求歸納斷言的性質(zhì)的優(yōu)先準(zhǔn)那么。求：歸納斷言H，能重言蘊(yùn)涵或弱蘊(yùn)涵觀察陳述，并滿足背景知識(shí)。7/4/202344假設(shè)H永真蘊(yùn)涵事實(shí)F，說(shuō)明F是H的邏輯推理，那么有：H∣>F(讀作H特殊化為F)或F∣<H(讀作F一般化為H)這里，從H推導(dǎo)到F是演繹推理，因此是保真的；而從事實(shí)F推導(dǎo)出假設(shè)H是歸納推理，因此不是保真的，而是保假的。7/4/202345歸納學(xué)習(xí)系統(tǒng)的模型如下圖。實(shí)驗(yàn)規(guī)劃過(guò)程通過(guò)對(duì)實(shí)例空間的搜索完成實(shí)例選擇，并將這些選中的活潑實(shí)例提交給解釋過(guò)程。解釋過(guò)程對(duì)實(shí)例加以適當(dāng)轉(zhuǎn)換，把活潑實(shí)例變換為規(guī)那么空間中的特定概念，以引導(dǎo)規(guī)那么空間的搜索。歸納學(xué)習(xí)系統(tǒng)模型

實(shí)例空間規(guī)則空間規(guī)劃過(guò)程解釋過(guò)程7/4/202346(2)歸納概括規(guī)那么歸納推理過(guò)程中，要引用如下歸納規(guī)那么：選擇性概括規(guī)那么構(gòu)造性概括規(guī)那么令D1,D2分別為歸納前后的知識(shí)描述，那么歸納是D1=>D2。如果D2中所有描述根本單元(如謂詞子句的謂詞)都是D1中的，只是對(duì)D1中根本單元有所取舍，或改變連接關(guān)系，那么就是選擇性概括。如果D2中有新的描述根本單元(如反映D1各單元間的某種關(guān)系的新單元)，那么就稱之為構(gòu)造性概括。7/4/2023472.歸納學(xué)習(xí)方法(1)例如學(xué)習(xí)例如學(xué)習(xí)(learningfromexamples)，它是通過(guò)環(huán)境中假設(shè)干與某概念有關(guān)的例子，經(jīng)歸納得出一般性概念的一種學(xué)習(xí)方法。外部環(huán)境提供的是一組例子(正例和反例)，它們是一組特殊的知識(shí)，每一個(gè)例子表達(dá)了僅適用于該例子的知識(shí)。例如學(xué)習(xí)就是要從這些特殊知識(shí)中歸納出適用于更大范圍的一般性知識(shí)，以覆蓋所有的正例并排除所有反例。如，如果用一批動(dòng)物作為例如，并且告訴學(xué)習(xí)系統(tǒng)哪一個(gè)動(dòng)物是“馬〞，哪一個(gè)動(dòng)物不是。當(dāng)例如足夠多時(shí)，學(xué)習(xí)系統(tǒng)就能概括出關(guān)于“馬〞的概念模型，使自己能夠識(shí)別馬，并且能將馬與其他動(dòng)物區(qū)別開來(lái)。歸納學(xué)習(xí)的方法7/4/202348(2)觀察發(fā)現(xiàn)學(xué)習(xí)觀察發(fā)現(xiàn)學(xué)習(xí)(learningfromobservationanddiscovery)，其目標(biāo)是確定一個(gè)定律或理論的一般性描述，刻畫觀察集，指定某類對(duì)象的性質(zhì)。觀察發(fā)現(xiàn)學(xué)習(xí)分為概念聚類機(jī)器發(fā)現(xiàn)前者用于對(duì)事例進(jìn)行聚類，形成概念描述；后者用于發(fā)現(xiàn)規(guī)律，產(chǎn)生定律或規(guī)那么。1〕概念聚類——根本思想是把事例按照一定的方式和準(zhǔn)那么分組，如劃分為不同的類或不同的層次等，使不同的組代表不同的概念，并且對(duì)每一個(gè)組進(jìn)行特征概括，得到一個(gè)概念的語(yǔ)義符號(hào)描述。如，對(duì)如下事例：7/4/202349喜鵲、麻雀、布谷鳥、烏鴉、雞、鴨、鵝……可根據(jù)它們是否家養(yǎng)分為如下兩類：鳥={喜鵲，麻雀，布谷鳥，烏鴉……}家禽={雞，鴨，鵝，…}這里，“鳥〞和“家禽〞就是由分類得到的新概念，而且根據(jù)相應(yīng)動(dòng)物的特征還可得知：“鳥有羽毛、有翅膀、會(huì)飛、會(huì)叫、野生〞“家禽有羽毛、有翅膀、不會(huì)飛、會(huì)叫、家養(yǎng)〞如果把它們的共同特性抽取出來(lái)，就可進(jìn)一步形成“鳥類〞的概念。7/4/2023502〕機(jī)器發(fā)現(xiàn)機(jī)器發(fā)現(xiàn)是指從觀察事例或經(jīng)驗(yàn)數(shù)據(jù)中歸納出規(guī)律或規(guī)那么的學(xué)習(xí)方法。可分為：經(jīng)驗(yàn)發(fā)現(xiàn)知識(shí)發(fā)現(xiàn)前者是指從經(jīng)驗(yàn)數(shù)據(jù)中發(fā)現(xiàn)規(guī)律和定律，后者是指從已觀察的事例中發(fā)現(xiàn)新的知識(shí)。7/4/202351例如學(xué)習(xí)和ID3教學(xué)目的：掌握例如學(xué)習(xí)的根本策略；理解構(gòu)造決策樹法ID3；主要內(nèi)容：例如學(xué)習(xí)的根本概念3種例如學(xué)習(xí)策略：①逐步泛化的學(xué)習(xí)策略；②逐步特化的學(xué)習(xí)策略；③雙向?qū)W習(xí)策略；基于決策樹的歸納學(xué)習(xí)方法ID37/4/202352教學(xué)要求：掌握主要內(nèi)容：理解例子空間和假設(shè)空間的概念及其關(guān)系；理解泛化和特化的概念以及與搜索的關(guān)系；掌握例如學(xué)習(xí)的三種根本策略。例如學(xué)習(xí)7/4/202353例如學(xué)習(xí)任務(wù)：從一系列例如出發(fā)：正例；反例；生成一個(gè)反映這些例如本質(zhì)的定義〔概念描述〕：覆蓋所有的正例，而不包含任何反例；可用來(lái)指導(dǎo)對(duì)新例子的分類識(shí)別；例如概念描述解描述例如學(xué)習(xí)7/4/2023541、概念描述的搜索和獲取例子空間和假設(shè)空間例子空間：所有可能的正例、反例構(gòu)成的空間；假設(shè)空間〔概念空間〕：所有可能的假設(shè)〔概念描述〕構(gòu)成的空間；假設(shè)空間中每一假設(shè)都對(duì)應(yīng)于例子空間中一個(gè)子集子集中的例子均是該假設(shè)的例子；假設(shè)空間例子空間假設(shè)A假設(shè)B例子1例子n...例如學(xué)習(xí)7/4/2023551、概念描述的搜索和獲取假設(shè)的泛化和特化：D1對(duì)應(yīng)例子集是D2對(duì)應(yīng)例子集的子集；D2比D1泛化；D1比D2特化；假設(shè)空間中假設(shè)間的泛化關(guān)系：反對(duì)稱：

D2比D1泛化、且D1比D2泛化，那么D1=D2；可傳遞：D3比D2泛化、且D2比D1泛化，那么D3比D1泛化；假設(shè)空間假設(shè)D1假設(shè)D2例子空間D2例子集D1例子集假設(shè)空間假設(shè)D1假設(shè)D2例如學(xué)習(xí)7/4/2023561、概念描述的搜索和獲取例1：病態(tài)細(xì)胞的分類識(shí)別〔找到病態(tài)細(xì)胞的概念〕每個(gè)細(xì)胞由2個(gè)細(xì)胞體組成；每個(gè)細(xì)胞體具有3個(gè)屬性──胞核數(shù)(1-2)，尾巴數(shù)(1-2)及染色狀〔淺或深〕；細(xì)胞P1,P2,P3有病狀X；N1,N2是正常細(xì)胞；P1+P2+N1-P3+N2-例如學(xué)習(xí)7/4/2023571、概念描述的搜索和獲取例1：病態(tài)細(xì)胞的分類識(shí)別細(xì)胞體——3元組〔核數(shù)、尾數(shù)、染色狀〕；細(xì)胞——2個(gè)細(xì)胞體3元組組成的集合；細(xì)胞P1表示為{(2,2,深)(1,1,淺)}例子空間由P1,P2,P3,N1,N2組成；P1,P2,P3為正例；N1,N2為反例；P1+P2+N1-P3+N2-學(xué)習(xí)任務(wù)從例子空間中歸納出有病狀X的細(xì)胞概念描述

例如學(xué)習(xí)7/4/2023581、概念描述的搜索和獲取例1：病態(tài)細(xì)胞的分類識(shí)別假設(shè)空間表示為假設(shè)的集合；假設(shè)不必給每個(gè)特性〔屬性〕都指明應(yīng)取值：假設(shè)a：{(2,?,?)(?,1,深)}，表示：如果：細(xì)胞中一個(gè)細(xì)胞體有2個(gè)胞核；另一個(gè)有1個(gè)尾巴，且染色是深的；那么：該細(xì)胞有病癥X。“?〞指相應(yīng)的屬性對(duì)病細(xì)胞的判斷是無(wú)關(guān)緊要；a例如學(xué)習(xí)7/4/2023591、概念描述的搜索和獲取例1：病態(tài)細(xì)胞的分類識(shí)別假設(shè)空間表示為假設(shè)的集合；假設(shè)不必給每個(gè)特性〔屬性〕都指明應(yīng)取值：假設(shè)a：{(2,?,?)(?,1,深)}假設(shè)b：{(2,?,?)(?,?,深)}覆蓋更多的例子ab特

化泛

化假設(shè)b比假設(shè)a泛化假設(shè)a比假設(shè)b特化例如學(xué)習(xí)7/4/202360完全的假設(shè)空間底層假設(shè)⑴最特化〔具體〕的概念描述；⑵所有特性都給定特性值；⑶對(duì)應(yīng)于例子空間中的一個(gè)例子；頂層假設(shè)⑴最泛化的概念描述；⑵不指定任何具體的特性值；⑶表示為{(???)，(???)}；特化范化例如學(xué)習(xí)7/4/2023611、概念描述的搜索和獲取例如學(xué)習(xí)的過(guò)程〔T.Mitchell,1982〕：在假設(shè)空間中搜索的過(guò)程。學(xué)習(xí)過(guò)程中假設(shè)空間可以動(dòng)態(tài)擴(kuò)展；假設(shè)空間假設(shè)D1假設(shè)D2例子空間D2例子集D1例子集獲取、修正指導(dǎo)、預(yù)測(cè)例如學(xué)習(xí)7/4/2023621、概念描述的搜索和獲取假設(shè)空間中的搜索方法①特化搜索從最泛化的假設(shè)〔概念描述〕出發(fā)；每次取用一個(gè)新的例子，產(chǎn)生一些特化的描述；直到產(chǎn)生出足夠特化的解描述；②泛化搜索從最特化的假設(shè)〔例子空間中的一個(gè)正例〕開始；每次取用一個(gè)新的例子，產(chǎn)生一些泛化的描述；直到產(chǎn)生出足夠泛化的解描述。例如學(xué)習(xí)7/4/2023631、概念描述的搜索和獲取假設(shè)空間中的搜索方法①特化搜索②泛化搜索大多數(shù)例如學(xué)習(xí)方法都采用這二種方法或這二個(gè)方法的結(jié)合。任何的例如學(xué)習(xí)的過(guò)程都可以看成假設(shè)空間中的搜索過(guò)程，不同的搜索方式對(duì)應(yīng)于不同的學(xué)習(xí)策略：①逐步泛化的學(xué)習(xí)策略——自底向上的泛化搜索；②逐步特化的學(xué)習(xí)策略——自頂向下的特化搜索；③雙向?qū)W習(xí)策略——雙向搜索。例如學(xué)習(xí)7/4/2023642、逐步泛化的學(xué)習(xí)策略采用寬度優(yōu)先、自底向上的泛化搜索方式；根本策略：⑴從第一個(gè)正例出發(fā)，作為初始假設(shè)；⑵遇見正例就泛化某些假設(shè)以保證假設(shè)的完全描述性〔覆蓋所有正例〕；⑶遇見反例那么刪去某些假設(shè)以保證假設(shè)的一致描述性〔不覆蓋所有反例〕；直至得到一個(gè)既完全又一致的解描述(假設(shè))為止；解描述作為學(xué)習(xí)系統(tǒng)獲得的新知識(shí)，滿足給定例子集的概念定義。例如學(xué)習(xí)7/4/2023652、逐步泛化的學(xué)習(xí)策略采用寬度優(yōu)先、自底向上的泛化搜索方式：⑴將正例P1作為初始假設(shè)H1初始假設(shè)H1是最特化的假設(shè)；只覆蓋了一個(gè)正例P1；P1+P2+N1-P3+N2-寬度優(yōu)先自底向上例如學(xué)習(xí)7/4/2023662、逐步泛化的學(xué)習(xí)策略采用寬度優(yōu)先、自底向上的搜索方式：⑵取出下一個(gè)正例P2由于初始假設(shè)H1不能覆蓋P2；建立比H1泛化的假設(shè),使之能同時(shí)覆蓋H1和P2；初始假設(shè)H1P2+相同特性(2,?,?)相同特性(1,?,?)假設(shè)H2相同特性(?,1,淺)相同特性(?,2,深)假設(shè)H3例如學(xué)習(xí)7/4/2023672、逐步泛化的學(xué)習(xí)策略采用寬度優(yōu)先、自底向上的搜索方式：⑵取出下一個(gè)正例P2正例P2指導(dǎo)系統(tǒng)生成泛化的假設(shè)H2和H3；采用“最低限度的泛化〞的原那么新的假設(shè)剛好覆蓋現(xiàn)有的“假設(shè)/例子〞，如，H2和H3剛好覆蓋H1/P2；初始假設(shè)H1P2+假設(shè)H2假設(shè)H3例如學(xué)習(xí)7/4/2023682、逐步泛化的學(xué)習(xí)策略采用寬度優(yōu)先、自底向上的搜索方式：⑶取出下一個(gè)反例N1反例用來(lái)刪除過(guò)于泛化的假設(shè)；假設(shè)H2覆蓋了反例N1；假設(shè)H2是過(guò)于泛化的假設(shè)，應(yīng)該剪去；初始假設(shè)H1假設(shè)H2假設(shè)H3反例N1-細(xì)胞體1(2,?,?)細(xì)胞體2(1,?,?)例如學(xué)習(xí)7/4/2023692、逐步泛化的學(xué)習(xí)策略采用寬度優(yōu)先、自底向上的搜索方式：⑷取出下一個(gè)正例P3由于假設(shè)H3不能覆蓋P3；建立比H3泛化的假設(shè),使之能同時(shí)覆蓋H3和P3；初始假設(shè)H1假設(shè)H3P3+相同特性(?,2,?)相同特性(?,1,?)假設(shè)H4例如學(xué)習(xí)7/4/2023702、逐步泛化的學(xué)習(xí)策略采用寬度優(yōu)先、自底向上的搜索方式：⑷取出下一個(gè)正例P3由于假設(shè)H3不能覆蓋P3；建立比H3泛化的假設(shè),使之能同時(shí)覆蓋H3和P3初始假設(shè)H1假設(shè)H3P3+相同特性(?,?,淺)相同特性(?,?,深)假設(shè)H4假設(shè)H5例如學(xué)習(xí)7/4/2023712、逐步泛化的學(xué)習(xí)策略采用寬度優(yōu)先、自底向上的搜索方式：⑸取出下一個(gè)反例N2反例用來(lái)刪除過(guò)于泛化的假設(shè)；假設(shè)H4覆蓋了反例N2；假設(shè)H4是過(guò)于泛化的假設(shè)，應(yīng)該剪去；假設(shè)H5不覆蓋反例N1，N2。細(xì)胞體1(?,2,?)細(xì)胞體2(?,1,?)初始假設(shè)H1假設(shè)H3假設(shè)H4假設(shè)H5N2-反例N1-例如學(xué)習(xí)7/4/202372P1+P2+N1-P3+N2-初始假設(shè)H1假設(shè)H2假設(shè)H3例如學(xué)習(xí)7/4/202373P1+P2+N1-P3+N2-假設(shè)H5假設(shè)H3假設(shè)H4初始假設(shè)H1假設(shè)H5足夠泛化的解描述例如學(xué)習(xí)7/4/2023742、逐步泛化的學(xué)習(xí)策略符號(hào)說(shuō)明：H：當(dāng)前的假設(shè)集，初始值為{第一個(gè)觀察的正例}；N：已觀察到的反例集，初始值為空集{}；i：觀察的下一個(gè)例子；算法描述：IFi是正例THEN{⑴對(duì)每一個(gè)不覆蓋i的假設(shè)h∈H,用能覆蓋i和h〔假設(shè)/例子〕，且泛化程度又最低的假設(shè)〔可以有多個(gè)〕代替h；⑵移去H中能覆蓋已往觀察到的反例n∈N的假設(shè)(以保證一致性)；}ELSE//i是反例{⑴把i參加到反例集N；⑵移去H中能覆蓋i的假設(shè)；}例如學(xué)習(xí)7/4/2023751、概念描述的搜索和獲取例如學(xué)習(xí)的過(guò)程〔T.Mitchell,1982〕：在假設(shè)空間中搜索的過(guò)程。假設(shè)空間中的搜索方法①泛化搜索從最特化的假設(shè)〔例子空間中的一個(gè)正例〕開始；每次取用一個(gè)新的例子，產(chǎn)生一些泛化的描述；直到產(chǎn)生出足夠泛化的解描述。②特化搜索從最泛化的假設(shè)〔概念描述〕出發(fā)；每次取用一個(gè)新的例子，產(chǎn)生一些特化的描述；直到產(chǎn)生出足夠特化的解描述；例如學(xué)習(xí)7/4/2023763、逐步特化的學(xué)習(xí)策略“泛化策略〞：采用寬度優(yōu)先、自底向上的搜索方式；“特化策略〞：采用寬度優(yōu)先、自頂向下的搜索方式；【相同點(diǎn)】新例子的參加會(huì)導(dǎo)致新假設(shè)的增加和已存在假設(shè)的刪除；P1+N1-N2-P2+例如學(xué)習(xí)7/4/2023773、逐步特化的學(xué)習(xí)策略正例和反例所起的作用與泛化策略相反：反例——生成一些特化假設(shè)；*采用保守的原那么——最低限度的特化：-新的假設(shè)在覆蓋已有正例的同時(shí)只是剛好能排斥反例；正例——剪裁過(guò)于特化的假設(shè)。7/4/2023783、逐步特化的學(xué)習(xí)策略采用寬度優(yōu)先、自頂向下的搜索方式；⑴最泛化的假設(shè)H1={(?,?,?),(?,?,?)}細(xì)胞簡(jiǎn)化成2個(gè)細(xì)胞體,不附有任何的屬性；⑵取出第一個(gè)正例P1H1正確地覆蓋了正例P1，不必修改；正例P1將放入正例集，備用；初始假設(shè)H1P1+例如學(xué)習(xí)7/4/2023793、逐步特化的學(xué)習(xí)策略采用寬度優(yōu)先、自頂向下的搜索方式；⑶取出下一個(gè)反例N1初始假設(shè)H1過(guò)于泛化,覆蓋了這個(gè)反例N1；假設(shè)H1必須特化，至少得到特化假設(shè)H2、H3；假設(shè)H2、H3排斥反例N1；系統(tǒng)是依靠反例來(lái)生成一些特化假設(shè)；“最低限度的特化〞保守的原那么：特化的假設(shè)在覆蓋已有正例的同時(shí)只是剛好能排斥反例。N1-初始假設(shè)H1假設(shè)H2假設(shè)H3P1+覆蓋正例P1例如學(xué)習(xí)7/4/2023803、逐步特化的學(xué)習(xí)策略采用寬度優(yōu)先、自頂向下的搜索方式；⑷取出下一個(gè)反例N2假設(shè)H2、H3過(guò)于泛化,覆蓋了這個(gè)反例N2；假設(shè)H2、H3必須特化；初始假設(shè)H1假設(shè)H2假設(shè)H3P1+-N2假設(shè)H4假設(shè)H5例如學(xué)習(xí)7/4/2023813、逐步特化的學(xué)習(xí)策略采用寬度優(yōu)先、自頂向下的搜索方式；⑸取出下一個(gè)正例P2正例P2排斥了假設(shè)H4；初始假設(shè)H1假設(shè)H2假設(shè)H3假設(shè)H4假設(shè)H5P2+假設(shè)H5是最后得到的概念描述——解描述例如學(xué)習(xí)7/4/2023823、逐步特化的學(xué)習(xí)策略符號(hào)說(shuō)明：H：當(dāng)前的假設(shè)集，初始值為{最泛化的假設(shè)}；P：已觀察到的正例集，初始值為空集{}；i：觀察的下一個(gè)例子；算法描述：IFi是反例THEN{⑴對(duì)每一個(gè)覆蓋i的假設(shè)h∈H,用可被h覆蓋但排斥i，且特化程度最低的假設(shè)代替h；⑵移去H中不覆蓋已往觀察到的正例p∈P的假設(shè)；}ELSE//i是正例{⑴把i參加到正例集P；⑵移去H中所有不覆蓋i的假設(shè)；}例如學(xué)習(xí)7/4/202383泛化策略：采用自底向上的搜索假設(shè)空間的方式；從第一個(gè)正例表示的最特化的假設(shè)開始；系統(tǒng)依靠正例生成泛化的假設(shè)；反例用來(lái)剪裁過(guò)于泛化的假設(shè)；解描述——泛化程度最低；特化策略：采用自頂向下的搜索假設(shè)空間的方式；從最泛化的假設(shè)開始；系統(tǒng)依靠反例生成特化的假設(shè)；正例用來(lái)剪裁過(guò)于特化的假設(shè)；解描述——特化程度最低；如果給出充分多的例子,那么二者的結(jié)果就可能會(huì)是相同的概念描述。

例如學(xué)習(xí)7/4/2023844、雙向?qū)W習(xí)策略結(jié)合“泛化策略〞和“特化策略〞,同時(shí)從2個(gè)方向搜索假設(shè)空間。版本空間法(VersionSpace〕假設(shè)集S——泛化搜索的假設(shè)空間；遇見一個(gè)新的正例時(shí)，如未被Ｓ集包含，那么在該集中進(jìn)行泛化搜索；假設(shè)集G——特化搜索的假設(shè)空間；一個(gè)新的反例產(chǎn)生時(shí)，如被Ｇ集包含，那么在該集中進(jìn)行特化搜索;例如學(xué)習(xí)7/4/202385完全的假設(shè)空間假設(shè)集SS不能覆蓋新的正例i那么在S中進(jìn)行泛化搜索假設(shè)集GG能覆蓋新的反例i，那么在G中進(jìn)行特化搜索特化搜索范化搜索當(dāng)S、G合一時(shí)，雙向?qū)W習(xí)結(jié)束例如學(xué)習(xí)7/4/2023864、雙向?qū)W習(xí)策略結(jié)合“泛化策略〞和“特化策略〞,同時(shí)從2個(gè)方向搜索假設(shè)空間。版本空間法(VersionSpace〕假設(shè)集S——泛化搜索的假設(shè)空間；期望獲取的最終解描述下界；假設(shè)集G——特化搜索的假設(shè)空間；期望獲取的最終解描述上界；例如學(xué)習(xí)7/4/2023874、雙向?qū)W習(xí)策略版本空間法(VersionSpace〕優(yōu)點(diǎn)：⑴系統(tǒng)不必保存正例〔特化策略〕和反例〔泛化策略〕：S蘊(yùn)涵了已取用的所有正例，刪除G中過(guò)于特化的假設(shè)；G蘊(yùn)涵了對(duì)所有已取用反例的排斥，刪除S中過(guò)于泛化的假設(shè)。⑵系統(tǒng)知道何時(shí)推理任務(wù)完成；當(dāng)S、G合一時(shí)，雙向?qū)W習(xí)結(jié)束；“泛化〞和“特化〞策略只能搜索完所有例如；例如學(xué)習(xí)7/4/202388輸入第一個(gè)正例P

初始化S={P}初始化G={最泛化的假設(shè)}例如i沒有考察例如i為正例保存G中覆蓋i的假設(shè)S中不覆蓋i的假設(shè)泛化，并且泛化的假設(shè)能被G所蘊(yùn)涵刪除S中蘊(yùn)涵其他假設(shè)的假設(shè)是保存S中不覆蓋i的假設(shè)G中覆蓋i的假設(shè)特化，并且特化的假設(shè)能蘊(yùn)涵S中相應(yīng)假設(shè)刪除G中被其他假設(shè)蘊(yùn)涵的假設(shè)否版本空間法(VersionSpace〕蘊(yùn)涵其他假設(shè)的假設(shè)泛化程度并非最低的假設(shè)〔最低泛化的原那么〕被其他假設(shè)蘊(yùn)涵的假設(shè)特化程度并非最低的假設(shè)〔最低特化的原那么〕7/4/202389P1+P2+N1-P3+N2-S1G1輸入第一個(gè)正例P1

7/4/202390P2+S1G1正例P2

保存G中覆蓋i的假設(shè)S中不覆蓋i的假設(shè)泛化，并且泛化的假設(shè)能被G所蘊(yùn)涵刪除S中蘊(yùn)涵其他假設(shè)的假設(shè)S2G27/4/202391反例N1

S2G2N1保存S中不覆蓋i的假設(shè)G中覆蓋i的假設(shè)特化，并且特化的假設(shè)能蘊(yùn)涵S中相應(yīng)假設(shè)刪除G中可以被其他假設(shè)蘊(yùn)含的假設(shè)G3S3S3和G3中的假設(shè)構(gòu)成了滿足正、反例的概念描述進(jìn)一步的“泛化〞、“特化〞搜索只能在S3和G3之間進(jìn)行例如足夠多時(shí)，S3和G3就會(huì)合而為一7/4/2023926.3基于決策樹的歸納學(xué)習(xí)方法教學(xué)要求：理解主要內(nèi)容：掌握決策樹的概念；理解決策樹的構(gòu)造方法。7/4/202393決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；任務(wù)：從大的已經(jīng)分類的例子集，歸納分類概念；例子表示為一組“屬性-值〞；每一個(gè)例子用相同的一組屬性來(lái)表示；每一個(gè)屬性又有自身的屬性值集；6.3基于決策樹的歸納學(xué)習(xí)方法7/4/202394編號(hào)屬性分類天氣溫度濕度風(fēng)況1晴熱大無(wú)N2晴熱大有N3多云熱大無(wú)P4雨中大無(wú)P5雨冷正常無(wú)P6雨冷正常有N7多云冷正常有P8晴中大無(wú)N9晴冷正常無(wú)P10雨中正常無(wú)P11晴中正常有P12多云中大有P13多云熱正常無(wú)P14雨中大有N7/4/202395決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；任務(wù)：從大的已經(jīng)分類的例子集，歸納分類概念；例子表示為一組“屬性-值〞；每一個(gè)例子用相同的一組屬性來(lái)表示；每一個(gè)屬性又有自身的屬性值集；ID3算法，昆蘭〔，1986〕；輸入：⑴描述類別例子的列表；⑵例子由預(yù)先定義的“屬性-值〞對(duì)來(lái)表示；結(jié)果：決策樹——可以正確地區(qū)分所有給定例子的類別；數(shù)學(xué)根底使用信息論指導(dǎo)決策樹構(gòu)造，提高決策樹的工作效率6.3基于決策樹的歸納學(xué)習(xí)方法7/4/202396決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；預(yù)先定義一組屬性及其可取值：高度{高，矮}；發(fā)色{黑色,紅色，金色}；眼睛{蘭色，棕色}；人分為兩類：“＋〞“－〞高度發(fā)色眼睛類別

─────────────────

矮黑色蘭色－

高黑色蘭色－

矮金色蘭色＋

高金色棕色－

高黑色棕色－

矮金色棕色－

高金色蘭色＋

高紅色蘭色＋6.3基于決策樹的歸納學(xué)習(xí)方法7/4/202397決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；選取“發(fā)色〞為樹的根節(jié)點(diǎn)：3個(gè)屬性值——3個(gè)對(duì)象子集發(fā)色黑色紅色金色｛矮、黑色、藍(lán)色:－｝｛高、黑色、藍(lán)色:－｝｛高、黑色、棕色:－｝｛高、紅色、藍(lán)色:＋｝｛矮、金色、藍(lán)色:＋｝｛高、金色、棕色:－｝｛高、金色、藍(lán)色:＋｝｛矮、金色、棕色:－｝6.3基于決策樹的歸納學(xué)習(xí)方法7/4/202398決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；按屬性“眼睛〞劃分“金色〞分支：2個(gè)屬性值——2個(gè)對(duì)象子集發(fā)色黑色紅色金色｛矮、黑色、藍(lán)色:－｝｛高、黑色、藍(lán)色:－｝｛高、黑色、棕色:－｝｛高、紅色、藍(lán)色:＋｝｛矮、金色、藍(lán)色:＋｝｛高、金色、棕色:－｝｛高、金色、藍(lán)色:＋｝｛矮、金色、棕色:－｝｛矮、金色、藍(lán)色:＋｝｛高、金色、藍(lán)色:＋｝｛高、金色、棕色:－｝｛矮、金色、棕色:－｝眼睛藍(lán)色棕色二級(jí)決策樹

所有葉節(jié)點(diǎn)的對(duì)象子集只含同一類對(duì)象6.3基于決策樹的歸納學(xué)習(xí)方法7/4/202399決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；發(fā)色黑色紅色金色｛矮、黑色、藍(lán)色:－｝｛高、黑色、藍(lán)色:－｝｛高、黑色、棕色:－｝｛高、紅色、藍(lán)色:＋｝｛矮、金色、藍(lán)色:＋｝｛高、金色、藍(lán)色:＋｝｛高、金色、棕色:－｝｛矮、金色、棕色:－｝眼睛藍(lán)色棕色二級(jí)決策樹

非葉節(jié)點(diǎn)對(duì)應(yīng)一個(gè)需測(cè)試的屬性

每個(gè)分叉就是該屬性可能的取值

葉節(jié)點(diǎn)指示同類例子的集合

6.3基于決策樹的歸納學(xué)習(xí)方法7/4/2023100決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；發(fā)色黑色紅色金色｛矮、黑色、藍(lán)色:－｝｛高、黑色、藍(lán)色:－｝｛高、黑色、棕色:－｝｛高、紅色、藍(lán)色:＋｝｛矮、金色、藍(lán)色:＋｝｛高、金色、藍(lán)色:＋｝｛高、金色、棕色:－｝｛矮、金色、棕色:－｝二級(jí)決策樹生成

＋＋－－眼睛棕色藍(lán)色6.3基于決策樹的歸納學(xué)習(xí)方法葉節(jié)點(diǎn)指示同類例子的集合

可以用相應(yīng)的類別名〔本例中的“+〞和“-〞〕取代各葉節(jié)點(diǎn)7/4/2023101決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；發(fā)色黑色紅色金色｛高、金色、藍(lán)色｝對(duì)象所屬類的判別＋＋－－眼睛棕色藍(lán)色只測(cè)試了兩個(gè)屬性＋6.3基于決策樹的歸納學(xué)習(xí)方法7/4/2023102決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；預(yù)先定義一組屬性及其可取值：高度{高，矮}；發(fā)色{黑色,紅色，金色}；眼睛{蘭色，棕色}；人分為兩類：“＋〞“－〞高度發(fā)色眼睛類別

─────────────────

矮黑色蘭色－

高黑色蘭色－

矮金色蘭色＋

高金色棕色－

高黑色棕色－

矮金色棕色－

高金色蘭色＋

高紅色蘭色＋6.3基于決策樹的歸納學(xué)習(xí)方法高度眼睛頭發(fā)7/4/2023103決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；高度高矮＋－－眼睛棕色藍(lán)色頭發(fā)黑色紅色金色＋眼睛棕色藍(lán)色－頭發(fā)－黑色紅色＋｛高、金色、藍(lán)色｝對(duì)象所屬類的判別測(cè)試了3個(gè)屬性＋6.3基于決策樹的歸納學(xué)習(xí)方法7/4/20231046.3基于決策樹的歸納學(xué)習(xí)方法面臨的問題：如何選擇屬性，使生成的決策樹最小的？ID3算法采用了香農(nóng)〔Shannon〕信息論：目標(biāo)：使分類時(shí)平均的測(cè)試次數(shù)最??；給定的例子集C：M(C)：從C判別一個(gè)對(duì)象的類屬所要求的總的期望信息量；人分類問題：M(C)=-P+log2P+-P-log2P-“+〞類消息的概率P+；“-〞類消息的概率P-；對(duì)于上述例子，C集有８?jìng)€(gè)例子，3個(gè)為“+〞，5為"-"，那么

M(C)=-〔3/8〕log2〔3/8〕-〔5/8〕log2〔5/8〕=0.954bits概率近似地表示為相對(duì)頻率P+=3/8高度發(fā)色眼睛類別

─────────────────

矮黑色蘭色－

高黑色蘭色－

矮金色蘭色＋

高金色棕色－

高黑色棕色－

矮金色棕色－

高金色蘭色＋

高紅色蘭色＋7/4/2023105A為構(gòu)造C的決策樹時(shí)下一個(gè)可能選取的屬性；{A1,A2,..,An}為屬性A的值且是互斥的；屬性A將集合C劃分為假設(shè)n個(gè)子集合；{C1，C2，...，Cn}M(Ci)是子集Ci判別一個(gè)對(duì)象的類屬所要求的總的期望信息量；B(C,A)：屬性A構(gòu)造決策樹后需要的期望信息量：∑(集合C中A值為Ai的概率P(Ai))*M(Ci)屬性AA1A2AnC1C2CnM(C1)M(C2)M(Cn)P(A1)P(A2)P(An)6.3基于決策樹的歸納學(xué)習(xí)方法7/4/2023106決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；M(C)＝∑(-Pilog2Pi)C判別一個(gè)對(duì)象的類屬所要求的總的期望信息量；M(Ci)Ci判別一個(gè)對(duì)象的類屬所要求的總的期望信息量；B(C,A)＝∑(C中A值為Ai的概率P(Ai))*M(Ci)

C按屬性A構(gòu)造決策樹后需要的期望信息量；M(C)-B(C,A)越大說(shuō)明測(cè)試這個(gè)屬性A所能傳遞的信息量越大；判別的速度也就越快；選擇M(C)-B(C,A)最大的屬性A生成決策樹；6.3基于決策樹的歸納學(xué)習(xí)方法7/4/20231076.3基于決策樹的歸納學(xué)習(xí)方法面臨的問題：如何選擇屬性，使生成的決策樹最小的？ID3算法采用了香農(nóng)〔Shannon〕信息論：目標(biāo)：使分類時(shí)平均的測(cè)試次數(shù)最??；給定的例子集C：M(C)：從C判別一個(gè)對(duì)象的類屬所要求的總的期望信息量；人分類問題：M(C)=-P+log2P+-P-log2P-“+〞類消息的概率P+；“-〞類消息的概率P-；對(duì)于上述例子，C集有８?jìng)€(gè)例子，3個(gè)為“+〞，5為"-"，那么

M(C)=-〔3/8〕log2〔3/8〕-〔5/8〕log2〔5/8〕=0.954bits概率近似地表示為相對(duì)頻率P+=3/8高度發(fā)色眼睛類別

─────────────────

矮黑色蘭色－

高黑色蘭色－

矮金色蘭色＋

高金色棕色－

高黑色棕色－

矮金色棕色－

高金色蘭色＋

高紅色蘭色＋7/4/20231086.3基于決策樹的歸納學(xué)習(xí)方法決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；選取“高度〞為樹的根節(jié)點(diǎn)：2個(gè)屬性值——2個(gè)對(duì)象子集高度高矮{高，金，棕：－}{高，紅，藍(lán)：＋}{高，黑，藍(lán)：－}{高，金，藍(lán)：＋}{高，黑，棕：－}

｛矮、金、藍(lán):＋｝｛矮、黑、棕:－｝｛矮、金、棕:－｝“高〞的分支的所需期望信息量為：M(C高)

-〔2/5〕log2〔2/5〕-〔3/5〕log2〔3/5〕=0.971bitsP+

=2/5P-=3/5“矮〞的分支的所需期望信息量為：M(C矮)

-〔1/3〕log2〔1/3〕-〔2/3〕log2〔2/3〕=0.918bitsP+

=1/3P-

=2/3C以屬性“高度〞作劃分后進(jìn)一步判別所需的期望信息量為：

B(C,“高度〞)=5/8×M(C高)+3/8×M(C矮)=0.951P(高)

=5/8P(矮)

=3/8M(C高)M(C矮)7/4/20231096.2.2決策樹構(gòu)造法以屬性“高度〞作劃分后進(jìn)一步判別所需的期望信息量為：

B(C,"高度")=5/8×0.971+3/8×0.918=0.951bits測(cè)試這屬性“高度〞傳遞的信息為：

M(C)-B(C,"高度")=0.954-0.951=0.003bits對(duì)于上述例子，C集有８?jìng)€(gè)例子，3個(gè)為“+〞，5為"-"，那么

M(C)=-〔3/8〕log2〔3/8〕-〔5/8〕log2〔5/8〕=0.954bits屬性“頭發(fā)〞作為根節(jié)點(diǎn)構(gòu)造決策樹7/4/2023110發(fā)色黑色紅色金色｛矮、黑色、藍(lán)色:－｝｛高、黑色、藍(lán)色:－｝｛高、黑色、棕色:－｝｛高、紅色、藍(lán)色:＋｝｛矮、金色、藍(lán)色:＋｝｛高、金色、棕色:－｝｛高、金色、藍(lán)色:＋｝｛矮、金色、棕色:－｝-1×log21

=0-1×log21

=0以屬性“頭發(fā)〞作劃分后進(jìn)一步判別所需的期望信息量為：

B(C,“頭發(fā)〞)=3/8×0+1/8×0+4/8×1=0.5bits-1/2×log21/2

-1/2×log21/2

=1測(cè)試這屬性“頭發(fā)〞傳遞的信息為：

M(C)-B(C,"頭發(fā)")=0.954-0.5=0.454bits6.3基于決策樹的歸納學(xué)習(xí)方法M(C黑)M(C紅)M(C金)P(黑)

=3/8P(紅)

=1/8P(黑)

=4/8M(C黑)=0M(C紅)=0M(C金)=17/4/2023111決策樹構(gòu)造法測(cè)試這屬性“高度〞傳遞的信息為：

M(C)-B(C,"高度")=0.954-0.951=0.003bits測(cè)試這屬性“頭發(fā)〞傳遞的信息為：

M(C)-B(C,"頭發(fā)")=0.954-0.5=0.454bits測(cè)試這屬性“眼睛〞傳遞的信息為：

M(C)-B(C,"眼睛")=0.347bits對(duì)于上述例子，C集有８?jìng)€(gè)例子，3個(gè)為“+〞，5為"-"，那么

M(C)=-〔3/8〕log2〔3/8〕-〔5/8〕log2〔5/8〕=0.954bits高度發(fā)色眼睛類別

─────────────────

矮黑色蘭色－

高黑色蘭色－

矮金色蘭色＋

高金色棕色－

高黑色棕色－

矮金色棕色－

高金色蘭色＋

高紅色蘭色＋7/4/2023112決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；發(fā)色黑色紅色金色＋－6.3基于決策樹的歸納學(xué)習(xí)方法｛矮、金色、藍(lán)色:＋｝｛高、金色、棕色:－｝｛高、金色、藍(lán)色:＋｝｛矮、金色、棕色:－｝7/4/2023113｛矮、金色、藍(lán)色:＋｝｛高、金色、棕色:－｝｛高、金色、藍(lán)色:＋｝｛矮、金色、棕色:－｝C1集有4個(gè)例子，2個(gè)為“+〞，2為“-〞，那么

M(C1)=-〔2/4〕log2〔2/4〕-〔2/4〕log2〔2/4〕=1bits＋－眼睛棕色藍(lán)色-1×log21

=0-1×log21

=0M(C藍(lán))=0M(C棕)=0P(藍(lán))

=1/2P(棕)

=1/2以屬性“眼睛〞作劃分后進(jìn)一步判別所需的期望信息量為：

B(C1,“眼睛〞)=1/2×0+1/2×0=0bits測(cè)試這屬性“眼睛〞傳遞的信息為：

M(C1)-B(C1,“眼睛")=1-0=1bits7/4/2023114｛矮、金色、藍(lán)色:＋｝｛高、金色、棕色:－｝｛高、金色、藍(lán)色:＋｝｛矮、金色、棕色:－｝C1集有4個(gè)例子，2個(gè)為“+〞，2為“-〞，那么

M(C1)=-〔2/4〕log2〔2/4〕-〔2/4〕log2〔2/4〕=1bits高度矮高-1/2×log21/2-1/2×log21/2

=1M(C矮)=1M(C高)=1以屬性“高度〞作劃分后進(jìn)一步判別所需的期望信息量為：

B(C1,“高度〞)=1/2×1+1/2×1=1bits｛矮、金色、藍(lán)色:＋｝｛矮、金色、棕色:－｝｛高、金色、棕色:－｝｛高、金色、藍(lán)色:＋｝-1/2×log21/2-1/2×log21/2

=1P(矮)

=1/2P(高)

=1/2測(cè)試這屬性“高度〞傳遞的信息為：

M(C1)-B(C1,“高度")=1-1=0bits7/4/2023115｛矮、金色、藍(lán)色:＋｝｛高、金色、棕色:－｝｛高、金色、藍(lán)色:＋｝｛矮、金色、棕色:－｝決策樹學(xué)習(xí)——?dú)w納學(xué)習(xí)方法的一個(gè)變種；發(fā)色黑色紅色金色＋＋－－眼睛棕色藍(lán)色6.3基于決策樹的歸納學(xué)習(xí)方法測(cè)試這屬性“高度〞傳遞的信息為：

M(C1)-B(C1,“高度")=1-1=0bits測(cè)試這屬性“眼睛〞傳遞的信息為：

M(C1)-B(C1,“眼睛")=1-0=1bits7/4/2023116編號(hào)屬性分類天氣溫度濕度風(fēng)況1晴熱大無(wú)N2晴熱大有N3多云熱大無(wú)P4雨中大無(wú)P5雨冷正常無(wú)P6雨冷正常有N7多云冷正常有P8晴中大無(wú)N9晴冷正常無(wú)P10雨中正常無(wú)P11晴中正常有P12多云中大有P13多云熱正常無(wú)P14雨中大有N作業(yè)：構(gòu)造天氣狀況的決策樹要求：只要求寫出按不同狀況的根節(jié)點(diǎn)值的算式，不要求計(jì)算結(jié)果7/4/20231176.4類比學(xué)習(xí)類比學(xué)習(xí)(learningbyanalogy)就是通過(guò)類比，即通過(guò)對(duì)相似事物加以比較所進(jìn)行的一種學(xué)習(xí)。

許多創(chuàng)造和發(fā)現(xiàn)就是通過(guò)類比學(xué)習(xí)獲得的。如，盧瑟福將原子結(jié)構(gòu)和太陽(yáng)系進(jìn)行類比，發(fā)現(xiàn)了原子結(jié)構(gòu)；水管中的水壓計(jì)算公式和電路中電壓計(jì)算公式相似等等。7/4/20231181.類比推理和類比學(xué)習(xí)形式類比推理是由新情況與情況在某些方面的相似來(lái)推出它們?cè)谄渌嚓P(guān)方面的相似。類比推理是在兩個(gè)相似域之間進(jìn)行的：一個(gè)是已經(jīng)認(rèn)識(shí)的域，它包括過(guò)去曾經(jīng)解決過(guò)且與當(dāng)前問題類似的問題以及相關(guān)知識(shí)，稱為源域，記為S；另一個(gè)是當(dāng)前尚未完全認(rèn)識(shí)的域，它是待解決的新問題，稱為目標(biāo)域，記為T；類比推理的目的是從S中選出與當(dāng)前問題最近似的問題及其求解方法以求解決當(dāng)前的問題，或者建立起目標(biāo)域中已有命題間的聯(lián)系，形成新知識(shí)。7/4/2023119設(shè)用S1與T1分別表示S與T中的某一情況，且S1與T1相似；再假設(shè)S2與S1相關(guān)，那么由類比推理可推出T中的T2，且T2與S2相似。其推理過(guò)程如下：(1)回憶與聯(lián)想當(dāng)遇到新情況或新問題時(shí)，首先通過(guò)回憶與聯(lián)想在S中找出與當(dāng)前情況相似的情況，這些情況是過(guò)去已經(jīng)處理過(guò)的，有現(xiàn)成的解決方法及相關(guān)的知識(shí)。找出的相似情況可能不只一個(gè)，可依其相似度從高至低進(jìn)行排序。7/4/2023120(2)選擇從找出的相似情況中選出與當(dāng)前情況最相似的情況及其有關(guān)知識(shí)。在選擇時(shí)，相似度越高越好，這有利于提高推理的可靠性。(3)建立對(duì)應(yīng)關(guān)系在S與T的相似情況之間建立相似元素的對(duì)應(yīng)關(guān)系，并建立起相應(yīng)的映射。(4)轉(zhuǎn)換在上一步建立的映射下，把S中的有關(guān)知識(shí)引到T中來(lái)，從而建立起求解當(dāng)前問題的方法或者學(xué)習(xí)到關(guān)于T的新知識(shí)。7/4/2023121在以上每一步中都有一些具體的問題需要解決。下面對(duì)類比學(xué)習(xí)的形式加以說(shuō)明：設(shè)有兩個(gè)具有相同或相似性質(zhì)的論域：源域S和目標(biāo)域T，S中的元素a和T中的元素b具有相似的性質(zhì)P，即P(a)≌P(b)，a還具有性質(zhì)Q，即Q(a)。根據(jù)類比，b也具有性質(zhì)Q。即：P(a)∧Q(a),P(a)├Q(b)其中，符號(hào)├表示類比推理。7/4/2023122類比學(xué)習(xí)采用類比推理，步驟：(1)找出源域與目標(biāo)域的相似性質(zhì)P，找出源域中另一個(gè)性質(zhì)Q和性質(zhì)P對(duì)元素a的關(guān)系：P(a)→Q(a)。(2)在源域中推廣P和Q的關(guān)系為一般關(guān)系，即對(duì)于所有的變量x來(lái)說(shuō)，存在P(x)→Q(x)。(3)從源域和目標(biāo)域映射關(guān)系，得到目標(biāo)域的新性質(zhì)，即對(duì)于目標(biāo)域的所有變量x來(lái)說(shuō)，存在P(x)→Q(x)。(4)利用假言推理：P(b),P(x)→Q(x)├Q(b)最后得出b具有性質(zhì)Ｑ。7/4/2023123從上述步驟可見，類比學(xué)習(xí)實(shí)際上是演繹學(xué)習(xí)和歸納學(xué)習(xí)的組合。步驟(2)是一個(gè)歸納過(guò)程，即從個(gè)別現(xiàn)象推斷出一般規(guī)律；而步驟(4)那么是一個(gè)演繹過(guò)程，即從一般規(guī)律找出個(gè)別現(xiàn)象。7/4/20231242.類比學(xué)習(xí)過(guò)程與研究類型類比學(xué)習(xí)包括：(1)輸入一組條件(已解決問題)和一組未完全確定的條件(新問題)。(2)對(duì)輸入的兩組條件，根據(jù)其描述，按某種相似性的定義尋找兩者可類比的對(duì)應(yīng)關(guān)系。(3)根據(jù)相似變換的方法，將已有問題的概念、特性、方法、關(guān)系等映射到新問題上，以獲得待求解新問題所需的新知識(shí)。(4)對(duì)類推得到的新問題的知識(shí)進(jìn)行校驗(yàn)。驗(yàn)證正確的知識(shí)存入知識(shí)庫(kù)中，而暫時(shí)還無(wú)法驗(yàn)證的知識(shí)只能作為參考性知識(shí)，置于數(shù)據(jù)庫(kù)中。7/4/2023125類比學(xué)習(xí)的研究分兩類：(1)問題求解型。當(dāng)求解一個(gè)新問題時(shí)，總是首先回憶一下以前是否求解過(guò)類似的問題，假設(shè)是，那么可以此為根據(jù)，通過(guò)對(duì)先前的求解過(guò)程加以適當(dāng)修改，使之滿足新問題的解。(2)預(yù)測(cè)推定型。它又分為兩種方式。一種是傳統(tǒng)的類比法，用來(lái)推斷一個(gè)不完全確定的事物可能還具有的其他屬性。設(shè)X，Y為兩個(gè)事物，Pi屬性(i=l，2，….，n)，那么有以下關(guān)系：另一種是因果關(guān)系型的類比，其根本問題是：因果關(guān)系S1:A→B，給定事物Ａ與Ａ’相似，那么可能有與B相似的事物B’滿足因果關(guān)系：A’→B’。7/4/2023126進(jìn)行類比的關(guān)鍵是相似性判斷，而其前提是配對(duì)，兩者結(jié)合起來(lái)就是匹配。實(shí)現(xiàn)匹配有多種形式，常用的有以下幾種：(1)等價(jià)匹配：要求兩個(gè)匹配對(duì)象之間具有完全相同的特性數(shù)據(jù)；(2)選擇匹配：在匹配對(duì)象中選擇重要特性進(jìn)行匹配；(3)規(guī)那么匹配：假設(shè)兩個(gè)規(guī)那么的結(jié)論局部匹配，且其前提局部也匹配，那么兩規(guī)那么匹配；(4)啟發(fā)式匹配：根據(jù)一定背景知識(shí)，對(duì)對(duì)象的特征進(jìn)行提取，然后通過(guò)一般化操作使兩個(gè)對(duì)象在更高、更抽象的層次上相同。7/4/20231276.5基于范例的推理基于范例的推理〔case-basedreasoning，CBR〕同人類的日常推理活動(dòng)十分接近，它來(lái)自于人類的認(rèn)知心理活動(dòng)。不同于傳統(tǒng)的基于知識(shí)系統(tǒng)，CBR系統(tǒng)所信賴的知識(shí)主要是系統(tǒng)所存儲(chǔ)的相關(guān)領(lǐng)域中以前解決問題的具體記錄。7/4/20231281.CBR系統(tǒng)的特點(diǎn)羅杰·沙克〔RogerSchank〕是CBR研究的開創(chuàng)者，沙克〔Schank〕指出，CBR方法研究的原始動(dòng)機(jī)，主要來(lái)源于對(duì)人類推理活動(dòng)中“回憶〞的重要地位的認(rèn)識(shí)傳統(tǒng)的基于知識(shí)系統(tǒng)〔主要指知識(shí)表示采用產(chǎn)生式規(guī)那么或框架架或語(yǔ)義網(wǎng)絡(luò)的專家系統(tǒng)，ES〕存在一定的困難，如：知識(shí)獲取的瓶頸問題知識(shí)庫(kù)維護(hù)的困難推理鏈不能太長(zhǎng)固定的求解范圍7/4/2023129CBR方法在以下方面對(duì)基于規(guī)那么的系統(tǒng)做出了改進(jìn)：以下討論都假定非CBR知識(shí)系統(tǒng)的知識(shí)表示都采用產(chǎn)生式規(guī)那么。1.知識(shí)獲取2.知識(shí)庫(kù)維護(hù)3.解決問題的范圍4.解質(zhì)量5.求解過(guò)程7/4/20231302.CBR系統(tǒng)的體系結(jié)構(gòu)一個(gè)CBR推理和學(xué)習(xí)過(guò)程可以分解為下面四個(gè)步驟：step1.從案例庫(kù)中檢索出與新案例最相似的案例或案例集；step2.把step1獲得的案例〔或案例集〕中的信息和知識(shí)復(fù)用到新問題上；step3.修正所建議的解答；step4.把該次獲得的經(jīng)驗(yàn)保存起來(lái)，以備將來(lái)來(lái)使用。7/4/2023131CBR的學(xué)習(xí)方法基于范例的推理通過(guò)下面幾種方法來(lái)完成它的大局部學(xué)習(xí)：新范例的積累。保存成功的和失敗的新范例。建立、修改和撤消指向范例的索引路徑，完善索引機(jī)制。歸納學(xué)習(xí)。7/4/2023132CBR方法的實(shí)現(xiàn)一般包含下面幾個(gè)主要步聚：案例表示，索引和存儲(chǔ)，檢索，適應(yīng)修改，評(píng)估和學(xué)習(xí)等。(1)案例表示基于案例的推理系統(tǒng)利用案例記錄以前的問題求解的情況，應(yīng)該包括與問題的解答有關(guān)的一切重要信息。從問題求解角度來(lái)看，案例應(yīng)包含對(duì)問題整體情況的描述，還應(yīng)包含對(duì)問題的解或解決方法的描述。所以案例可被表成一個(gè)有序?qū)Γ?lt;問題描述，解描述>。

7/4/2023133〔2〕索引案例庫(kù)的索引〔indexing〕的目標(biāo)是提供一種案例庫(kù)的搜索機(jī)制，使得在將來(lái)的檢索中能夠快速找出符合需要的案例或案例集。一個(gè)案例的索引就是這個(gè)案例的重要關(guān)鍵字的集合，這些關(guān)鍵字可以將這個(gè)案例同其他案例區(qū)分開來(lái)。索引問題的主要任務(wù)包括：選擇什么類型的索引、如何定義索引詞匯表、如何構(gòu)建索引的搜索空間等。7/4/2023134(3)案例檢索檢索任務(wù)開始于一個(gè)描述待求問題的新案例，利用案例庫(kù)索引機(jī)制，根據(jù)相似性度量方法，在某種相似性程度閾值下，從案例庫(kù)中找出一組與新案例匹配較好的舊案例，并從中選擇出一個(gè)最正確的案例。檢索任務(wù)的子任務(wù)包括：特性鑒別〔indentifyfeature〕，初始匹配〔initiallymatch〕，搜(search)和選擇(select)。7/4/2023135(4)相似性度量相似性度量〔similaritymeasure〕在CBR系統(tǒng)中十分重要，適宜的度量方法可以迅速、準(zhǔn)確地找到所需要的案例。CBR系統(tǒng)的相似性度量方法主要使用基于距離〔基于計(jì)算〕的方法，考慮到具體應(yīng)用環(huán)境的特點(diǎn)擴(kuò)展了的相似性度量方法和最近鄰法〔NNh,thenearestneighbormethod〕。7/4/2023136(5)適應(yīng)性修改適應(yīng)性修改可以被簡(jiǎn)單地理解為把解決文案的一局部用其他的內(nèi)容替換，或者修改整個(gè)解決方案。適應(yīng)性修改可以有幾種形式苛以直接向解決方案中插入一些新內(nèi)容，也呆以從解決方案中刪除一些內(nèi)容，可以替換解決方案的某一局部?jī)?nèi)容，也可以將某一局部?jī)?nèi)容改造。但是，要使CBR系統(tǒng)得到足夠的適應(yīng)性修改知識(shí)(Adaptationknowledge)是一件十分困難的任務(wù)。7/4/2023137科洛德〔Kolodner〕提出了十種適應(yīng)性修改的方法。.重新例化.參數(shù)調(diào)整.局部搜索詢問/查詢記憶.特殊化搜索.基于案例的替換.常識(shí)轉(zhuǎn)化.模型制導(dǎo)的修改補(bǔ).特定目的的修改和修補(bǔ).推導(dǎo)重放上述的1至6屬替換方法，7和8屬于轉(zhuǎn)化方法7/4/2023138(6)評(píng)估和學(xué)習(xí)評(píng)估任務(wù)需要在現(xiàn)實(shí)環(huán)境中應(yīng)用該案例解答的結(jié)果，可以通過(guò)詢問專家或在現(xiàn)實(shí)世界中具體執(zhí)行任務(wù)來(lái)實(shí)現(xiàn)。這通常是CBR系統(tǒng)外部的一個(gè)步驟。根據(jù)應(yīng)用的類型，評(píng)估結(jié)果可能需要一段時(shí)間。當(dāng)某案例的評(píng)估結(jié)果沒有得出時(shí)，該案例應(yīng)標(biāo)記為未評(píng)估案例。學(xué)習(xí)過(guò)程把新案例中有意義的局部保存到系統(tǒng)的知識(shí)庫(kù)中。它包括從案例中選擇哪種信息進(jìn)行保存，以什么形式保存，為新案例建立哪些索引，如何建立這些索引，如何存儲(chǔ)新案例等等。7/4/20231394.結(jié)論基于案例的推理是人工智能領(lǐng)域中較新出現(xiàn)的一種重要的基于知識(shí)的問題求解和學(xué)習(xí)方法。作為一種基于經(jīng)驗(yàn)的問題求解技術(shù)，基于案例的推理〔CBR〕可以理解為修改舊的解決方案滿足新的需要；使用舊案例解釋新情況、評(píng)價(jià)新方案、構(gòu)造新問題的解答。學(xué)習(xí)是CBR推理行為的副產(chǎn)品，它獲得過(guò)去的經(jīng)驗(yàn)并在以后的推理中能夠回憶起來(lái)，這樣它的推理能力和效率都能得到提高?；诎咐耐评硐到y(tǒng)的推理質(zhì)量取決它具有的經(jīng)驗(yàn)，即在那些舊經(jīng)驗(yàn)的根底上理解新情況的能力、修改的能力、以及評(píng)價(jià)和改錯(cuò)的能力?；诎咐耐评沓绦虻闹饕^(guò)程是案例存儲(chǔ)、檢索、修改及審查。7/4/20231406.6解釋學(xué)習(xí)歸納學(xué)習(xí)基于訓(xùn)練數(shù)據(jù)中的規(guī)律來(lái)泛化：分析一組正例的共性，鑒別與反例的差異；概念描述：概括所有正例〔完全性〕；排除任何反例〔一致性〕；基于相似性的學(xué)習(xí)：依據(jù)——訓(xùn)練數(shù)據(jù)的相似性；⑴問題域背景知識(shí)約束作用有限；⑵大量正、反例增加歸納學(xué)習(xí)過(guò)程的計(jì)算復(fù)雜度；數(shù)據(jù)密集型學(xué)習(xí)方法7/4/20231416.6解釋學(xué)習(xí)基于解釋的學(xué)習(xí)〔Explanation-BasedLearning〕20世紀(jì)80年代中期興起的新型機(jī)器學(xué)習(xí)方法；根本方法：⑴應(yīng)用領(lǐng)域知識(shí)建立對(duì)1個(gè)訓(xùn)練實(shí)例的解釋；⑵訓(xùn)練實(shí)例的解釋泛化為目標(biāo)概念不是泛化訓(xùn)練實(shí)例主要內(nèi)容：6.6.2基于解釋的泛化Explanation-BasedGeneralization，EBG；Mitchelletal.1986；基于解釋的學(xué)習(xí)〔EBL〕的典型方法；逆向演繹推理7/4/20231426.6.2基于解釋的泛化〔EBG〕EBG