【正文】 方式能使推理較為容易。學習系統(tǒng)的本質(zhì)要求它不斷地修改自己的知識庫，當推廣得出一般執(zhí)行規(guī)則后，要加到知識庫中。每一個學習系統(tǒng)都要求具有某些知識理解環(huán)境提供的信息，分析比較，做出假設(shè)，檢驗并修改這些假設(shè)。 2022/2/15 《人工智能》 12 機器學習的分類 ? 按學習方法分類（溫斯頓在 1977年提出的分類方法） ①機械式學習：機械學習就是記憶。 ③示例學習：通過工作例子學習。 ⑤解釋學習：根據(jù)領(lǐng)域知識對當前實例分析和求解。 ③連接學習：人工神經(jīng)網(wǎng)絡(luò)學習 ④遺傳學習 ： 模擬自然界遺傳與變異機制 2022/2/15 《人工智能》 13 機械學習 機械學習的模式 機械學習是最簡單的機器學習方法。機械學習又是最基本的學習過程。在機械學習系統(tǒng)中，知識的獲取是以較為穩(wěn)定和直接的方式進行的，不需要系統(tǒng)進行過多的加工。他們指出，可以把機械學習看成是數(shù)據(jù)化簡分級中的第一級。在機械學習中我們只記憶計算的輸入輸出，忽略了計算過程，這樣就把計算問題化簡成存取問題。 （ 1）存儲組織信息：采用適當?shù)拇鎯Ψ绞剑箼z索速度盡可能地快，是機械學習中的重要問題。 （ 3）存儲與計算之間的權(quán)衡：對于機械學習來說很重要的一點是它不能降低系統(tǒng)的效率。這種方法對領(lǐng)域理論沒有要求，甚至可以沒有領(lǐng)域理論，但其需要大量的訓練例子，而且歸納性能受到描述語言、概念類型、信噪比、實例空間分布、 歸納模式等的影響。 （ 2） 歸納推理 是應(yīng)用歸納方法，從足夠多的具體事例中歸納出一般性知識，提取事物的一般規(guī)律；它是一種從個別到一般的推理。根據(jù)歸納學習有無教師指導，可把它分為示例學習和觀察與發(fā)現(xiàn)學習。 2022/2/15 《人工智能》 17 歸納學習的模式和規(guī)則 歸納學習的模式 給定： (1) 觀察陳述（事實） F，用以表示有關(guān)某些對象、狀態(tài)、過程等的特定知識； (2) 假定的初始歸納斷言（可能為空），是關(guān)于目標的泛化項或泛化描述。 求：歸納斷言（假設(shè)） H，能重言蘊涵或弱蘊涵觀察陳述，并滿足背景知識。 歸納學習系統(tǒng)的模型如圖所示。即： CTX∧ S→ K = CTX→ K (2) 放松條件： 一個事例的原因可能不止一條，當出現(xiàn)新的原因時，應(yīng)該把新的原因包含進去。在這種學習方法中，外部環(huán)境提供的是一組例子（正例和反例），示例學習就是要從這些特殊知識中歸納出適用于更大范圍的一般性知識，以覆蓋所有的正例并排除所有反例。觀察發(fā)現(xiàn)學習可分為觀察學習與機器發(fā)現(xiàn)兩種。 2022/2/15 《人工智能》 22 歸納學習示例 決策樹學習 決策樹學習是應(yīng)用最廣的歸納推理算法之一。在這種方法中學習到的函數(shù)被表示為一顆決策樹。 決策樹學習方法對噪聲數(shù)據(jù)有很好的健壯性且能夠?qū)W習析取表達式。這些決策樹學習方法搜索一個完整表示的假設(shè)空間，從而避免了受限假設(shè)空間的不足。 2022/2/15 《人工智能》 23 決策樹表示法 ? 決策樹通過把實例從根節(jié)點排列 (sort)到某個葉子節(jié)點來分類實例，葉子節(jié)點即為實例所屬的分類。 ? 分類實例的方法是從這顆樹的根節(jié)點開始，測試這個節(jié)點指定的屬性，然后按照給定實例的該屬性值對應(yīng)的樹枝向下移動。 例子：在一個水果的分類問題中，采用的特征向量為： {顏色 ,尺寸 ,形狀 ,味道 }，其中：顏色取值為 {紅 ,綠 ,黃 }，尺寸取值為 {大 ,中 ,小 }，味道取值為 {甜 ,酸 }，形狀取值為 {圓 ,細 }。從樹根到樹葉的每一條路徑對應(yīng)一組屬性測試的合取，樹本身對應(yīng)這些合取的析取。 ? 目標函數(shù)具有離散的輸出值：決策樹給每個實例賦予一個布爾型的分類。 ? 可能需要析取的描述：決策樹很自然地代表了析取表達式。 ? 訓練數(shù)據(jù)可以包含缺少屬性值的實例：決策樹甚至可以再有未知屬性值的訓練樣例中使用。 2022/2/15 《人工智能》 28 ID3算法 ? 大多數(shù)已開發(fā)的決策樹學習算法是一種核心算法 （ CLS算法 ） 的變體 。這種方法是 ID3算法 (Quinlan 1986)和后繼的 (Quinlan 1993)的基礎(chǔ) 。繼續(xù)這個過程指導這棵樹能完美分類訓練樣例，或所有的屬性都已被使用過。為了回答這個問題，使用統(tǒng)計測試來確定每一個實例屬性單獨分類訓練樣例的能力。然后為根節(jié)點屬性的每個可能值產(chǎn)生一個分枝，并把訓練樣例排列到適當?shù)姆种Γㄒ簿褪?，樣例的該屬性值對?yīng)的分枝）之下。這形成了對合格決策樹的貪婪搜索，也就是算法從不回溯重新考慮以前的選擇。 （ 2）葉結(jié)點的確定：什么時候可以結(jié)束提問，并判定模式的類別？ （ 3）決策樹修剪：如果決策樹過大，應(yīng)該如何修剪決策樹，以保證其泛化能力？ 2022/2/15 《人工智能》 30 最佳提問的選擇（ 1） （ 1）決策樹中的每一個結(jié)點（葉結(jié)點除外）對應(yīng)于一個提問。決策樹的構(gòu)建從根結(jié)點開始。通過選擇針對某一屬性的一個問題進行提問，可以根據(jù)對該問題的回答，將訓練樣本集 D分類兩個部分： Dy及 Dn （其中， Dy為回答YES的樣本， Dn為回答 NO的樣本） ，并建立與之相對應(yīng)的兩個子結(jié)點。 （ 3）中間結(jié)點的構(gòu)造：對于每一個中間結(jié)點（結(jié)點 N），都有一個與之對應(yīng)的子集 DN。我們希望根據(jù)結(jié)點 N提出的問題，能夠使DNy及 DNn盡可能純凈。 （ 5）當決策樹中的每一條路徑都對應(yīng)于一個葉結(jié)點時，學習過程結(jié)束，決策樹構(gòu)建完畢。 （ 7）在對訓練集分類能力相近的條件下，復(fù)雜度小的決策樹（分類器）優(yōu)于復(fù)雜度大的決策樹（分類器）。這一原則稱為 Occam’s razor。 2022/2/15 《人工智能》 33 最佳提問的選擇（ 4） ( ) ( ) ( ) ( )ny nnynnnN Ni n i n i n i nNN??? ? ? ????? 其中， ny為結(jié)點 n的 YES子結(jié)點， nn 為 NO子結(jié)點， Nny為 YES子結(jié)點對應(yīng)的樣本的數(shù)量， Nnn為 NO子結(jié)點對應(yīng)的樣本的數(shù)量。 （ 9）結(jié)點 n最佳問題的選擇： 對于結(jié)點 n，通過提出并回答某個問題，可以得到如下的純凈度的提高（不純凈度的降低）： 2022/2/15 《人工智能》 34 最佳提問的選擇（ 5） （ 10）結(jié)點 n最佳問題的選擇范圍： 需要枚舉出所有可以提出的問題，從中選出有效的問題，并在這些有效的問題中選擇一個最佳的問題。 所提問題通常限制為針對某個特征提出的簡單問題，問題的形式如前面的二叉數(shù)所示。對于任意一個結(jié)點 n，可以出現(xiàn)以下三種情況： （ 1）結(jié)點 n中的樣本屬于同一類，即結(jié)點 n絕對純凈。 （ 2）結(jié)點 n中的樣本不屬于同一類，但是不存在任何一個劃分（即提出一個問題并根據(jù)該問題對結(jié)點 n的樣本進行劃分）可以使其子結(jié)點的平均純凈度高于結(jié)點 n。 （ 3）可以提出一個問題對結(jié)點 n進行劃分，從而使結(jié)點 n的子結(jié)點具有更高的純凈度。 2022/2/15 《人工智能》 36 葉結(jié)點的確定問題 ? 問題：在構(gòu)建決策樹的過程中，確定葉節(jié)點的一個策略是：對于每一個可以進一步劃分的結(jié)點都進行劃分，直到得到一個不可劃分的子結(jié)點，并將該子結(jié)點定為葉結(jié)點。這種葉結(jié)點的確定方法是否可行？ ? 答案：決策樹是根據(jù)訓練樣本的集合構(gòu)成的。不同的隨機實驗會得到不同的樣本集合。當葉結(jié)點按上述方法確定時，所得決策樹雖然對訓練樣本集合給出了最優(yōu)的分類，但是卻背離了樣本的真實分布，因此削弱了對未來新樣本的分類能力。 2022/2/15 《人工智能》 37 葉結(jié)點確定的基本思路 （ 1）并不絕追求對訓練樣本的正確劃分。絕對追求葉結(jié)點的純凈度導致過度擬合。 （ 2）要適度保證葉結(jié)點的純凈度，適度保證對訓練樣本的正確分類能力。欠學習同樣不能保證對未來新樣本的正確分類能力）。 （ 3）因此，在決策樹的構(gòu)建過程中，需要在過度擬合與欠學習之間尋求合理的平衡，即尋求復(fù)雜度適中的決策樹。 2022/2/15 《人工智能》 38 確定葉結(jié)點的基本方法（ 1） 方法 1：采用測試集的方法。根據(jù)訓練集構(gòu)建決策樹，決策樹中的結(jié)點逐層展開。重復(fù)上述過程，可以得到?jīng)Q策樹在測試集上的學習曲線。 方法 2：在決策樹開始訓練以前，首先設(shè)定一個閾值 A。采用該方法不需要將樣本集合分為訓練集及測試集。 2022/2/15 《人工智能》 39 確定葉結(jié)點的基本方法（ 2） ()n le a f n o d e ssiz e i n???? ?方法 3：在決策樹開始訓練以前，首先設(shè)定一個閾值 A。其中， Nn為結(jié)點 n對應(yīng)的樣本的數(shù)量， N 為全體樣本的數(shù)量。決策樹直接采用全體樣本集合構(gòu)建。該準則函數(shù)表達出了過度擬合與欠學習之間的相互關(guān)系。 2022/2/15 《人工智能》 40 決策樹修剪（ 1） 決策樹的修剪是決策樹學習的另外一種有效的方法。具體方法如下： （ 1）決策樹的構(gòu)建：在決策樹的構(gòu)建過程中，對于每一個可以進一步劃分的結(jié)點都進行劃分，直到得到一個不可進一步劃分的子結(jié)點，并將該子結(jié)點定為葉結(jié)點。 2022/2/15 《人工智能》 41 決策樹修剪（ 2） （ 2）在上述決策樹構(gòu)建完畢后，從葉結(jié)點一層開始，考察兄弟葉結(jié)點是否可以合并。在對所有可以合并的兄弟葉結(jié)點進行合并后，可以形成一棵新的決策樹。這棵決策樹，就是我們最終選擇的決策樹。 Nn 為父結(jié)點中樣本的數(shù)量， Nny及 Nnn 為兩個子結(jié)點中樣本的數(shù)量。 A為閾值，在修剪過程開始前預(yù)先設(shè)定。對于葉結(jié)點 n，如果在該結(jié)點對應(yīng)的樣本中，屬于第 i 類的樣本數(shù)量最多，則判該葉結(jié)點為第 i類。一條從根結(jié)點到葉結(jié)點的路途對應(yīng)于一條 IFTHEN規(guī)則。 例子： IF COLOR=RED AND SIZE=MEDIUM THEN IT IS AN APPLE 用途：知識的獲取。當特征向量空間為歐氏空間時，同樣可以采用決策樹方法來構(gòu)造分類器。 2022/2/15 《人工智能》 44 類比學習 類比 (analogy)是一種很有用的和有效的推理方法，它能夠清晰簡潔地描述對象間的相似性；也是人類認識世界的一種重要方法。 例如，當人們遇到一個新問題需要進行處理，但又不具備處理這個問題的知識時，通常采用的辦法就是回憶一下過去處理過的類似問題，找出一個與目前情況最接近的處理方法來處理當前問題。顯然，類比推理是在兩個相似域之間進行的：類比推理的目的是從源域中選出與當前問題最近似的問題及其求解方法以求解決當前的問題，或者建立起目標域中已有命題間的聯(lián)系，形成新知識。 2022/2/15 《人工智能》 46 (2) 選擇 從找出的相似情況中選出與當前情況最相似的情況及其有關(guān)知識。 (4) 轉(zhuǎn)換 在上一步建立的映射下，把 S中的有關(guān)知識引到 T中來，從而建立起求解當前問題的方法或者學習到關(guān)于 T的新知識。類比學習的過程主要分為兩步：首先歸納找出源問題和目標問題的公共性質(zhì)，然后再演繹推出從源問題到目標問題的映射，得出目標問題的新的性質(zhì)。 類比學習的主要過程可描述如下： (1) 輸入一組已知條件（已解決問題）和一組未完全確定的條件（新問題）。 (3) 按相似變換的方法，將已有問題的概念、特性、方法、關(guān)系等映射到新問題上，以獲得待求解新問題所需的新知識。驗證正確的知識存入知識庫中，而暫時還無法驗證的知識只能作為參考性知識，置于數(shù)據(jù)庫中。具體來說，一個范例應(yīng)具有如下特性： ? 范例表示了與某個上下文有關(guān)的具體知識，這種知識具有可操作性。 ? 范例記錄了有用的經(jīng)驗，這種經(jīng)驗?zāi)軒椭评頇C在未來更容易地達到目標，或提醒推理機失敗發(fā)生的可能性有多大等等。這種推理就是 基于范例的推理 (CaseBased Reasoning, CBR)，也簡稱為范例推理。粗略地說，基于范例推理就是由目標范例的提示而獲得記憶中的源范例，并由源范例來指導目標范例求解的一種策略。 ? 對過去的求解結(jié)果進行復(fù)用 ， 而不是再次從頭推導 ， 可以提高對新問題的求解效率 。 ? 對于那些目前沒有或根本不存在的問題 ， 可以通過計算推導來解決的問題 。 范例推理的特點 2022/2/15 《人工智能》 52 基于范例的學習 基于范例的推理系統(tǒng)經(jīng)過不斷的積累經(jīng)驗（案例），同時合適地對其進行索引，系統(tǒng)的推理效率和問題求解能力會隨之增加。 在 CBR中，大多數(shù)學習是通過如下兩種方式體現(xiàn)的：一個是新范例的積累，推理系統(tǒng)的范例對問題的覆蓋越多，其功能越強；另一個是設(shè)計覆蓋了成功事例也覆蓋了失敗事例的推理要比只設(shè)計成功情況的推理系統(tǒng)要好，索引的重新賦值，調(diào)節(jié)索引可使得范例能在更合適的時機被回憶。 (2) 解