【正文】 常檢驗，用新例子去否定歸納出的錯誤規(guī)則。 ? ?實例學(xué)習(xí) － 兩個空間模型 （規(guī)則空間） ? 對規(guī)則空間的要求 ? 表示應(yīng)適應(yīng)于歸納。不同的歸納方法要求不同的規(guī)則表示方法。但解決的問題就較少。 ? 表示和例子的一致。 ? 引入新術(shù)語（規(guī)則空間）。 實例學(xué)習(xí) － 兩個空間模型 （規(guī)則空間） ? 搜索規(guī)則空間的方法 最終的目的是為了搜索，先建立一個假設(shè)空間，在其中進(jìn)行搜索。 ? 變形空間法 Versionspace：數(shù)據(jù)驅(qū)動 ? 改進(jìn)假設(shè)法 Hypothesisrefinement：數(shù)據(jù)驅(qū)動 ? 產(chǎn)生與測試 Generate and Test：模型驅(qū)動 ? 方案示例法 Schema Instantiation：模型驅(qū)動 ? 選擇例子。 實例學(xué)習(xí) ? 實例學(xué)習(xí)的分類 ? 按搜索方法分類： 變形空間法；改進(jìn)假設(shè)法；產(chǎn)生與測試法；方案示例法 ? 按論域分類： ? 數(shù)字表示：多用于電子工程、系統(tǒng)理論和模式分析 知識：多項式、矩陣； 系統(tǒng)：自適應(yīng)系統(tǒng)； 任務(wù)：模式分類、自適應(yīng)控制、濾波等。 知識：符號的特征向量、一階謂詞、產(chǎn)生式規(guī)則、 框架、語義網(wǎng)絡(luò)； 實例學(xué)習(xí) － 實例學(xué)習(xí)的分類 ?按任務(wù)復(fù)雜程度分類： ?學(xué)習(xí)單個概念：最基本的 ?學(xué)習(xí)多個概念：歸納出多個相互獨立的概念 ?學(xué)習(xí)執(zhí)行多步任務(wù)： 一個操作序列去完成任務(wù)，即執(zhí)行環(huán)節(jié)對任務(wù)要規(guī)劃。 學(xué)習(xí)單個概念就是給系統(tǒng)一個概念的若干正例合反例 ， 系統(tǒng)由此歸納出表示這個概念的謂詞公式 。 覆蓋全部正例 ， 不覆蓋 全部反例 。 依據(jù)示教例子中的信息 ， 對集合 H進(jìn)行一般化或特殊化處理 。 變形空間圖 實例學(xué)習(xí) －學(xué)習(xí)單個概念 （變形空間法） ? 搜索：使用一個可能合理的假設(shè)規(guī)則的集合 H， H是規(guī)則空間的子集 ， 是規(guī)則空間中間的一段 。 （ H是上界 G和下界 S之間的一段 。 ? 具體方法：消除候選元素法 。學(xué)習(xí)結(jié)束時找到的應(yīng)是充分必要條件。搜索的過程是在例子的引導(dǎo)下，數(shù)據(jù)驅(qū)動。 正例去掉 G中不符合的概念，然后修改 S ,歸納出最特殊的結(jié)果 ,盡量少改 S。解決方法：例子一組一組地給。 實例學(xué)習(xí) －學(xué)習(xí)單個概念 ? 改進(jìn)假設(shè)方法 ? 也是數(shù)據(jù)驅(qū)動的方法。然后根據(jù)示教例子用啟發(fā)式方法選擇這些操作。變量的選樣，對例子的提供很敏感 實例學(xué)習(xí) －學(xué)習(xí)單個概念 ? 產(chǎn)生與測試方法 ? 模型驅(qū)動的方法 。即使例子中有干擾，就選覆蓋大多數(shù)例子的規(guī)則即可。同時，因為修剪所以不完備，不一定能找到全部合格的概念。 實例學(xué)習(xí) －學(xué)習(xí)單個概念 ? 方案示例方法 ? 模型驅(qū)動的方法 。 如：圖像 、 語音 、 自然語言理解 。有的規(guī)則不能被現(xiàn)有的方案覆蓋。 實例學(xué)習(xí) ? 學(xué)習(xí)多個概念 ? 單個規(guī)則：可存在規(guī)則將空間一分為二 ? 規(guī)則集合有相交，主要問題是重疊部分。如下棋，積分。 ? 獎罰分配問題 ? 透明度 第六章 機器學(xué)習(xí) ? 概述 ? 實例學(xué)習(xí) ? 基于解釋的學(xué)習(xí) ? 決策樹學(xué)習(xí) ? 神經(jīng)網(wǎng)絡(luò)學(xué)習(xí) 第六章 機器學(xué)習(xí) ? 概述 ? 實例學(xué)習(xí) ? 基于解釋的學(xué)習(xí) ? 決策樹學(xué)習(xí) ? 神經(jīng)網(wǎng)絡(luò)學(xué)習(xí) 基于解釋的學(xué)習(xí) ? ExplanationBased Learning(EBL).也是由實例學(xué)習(xí)。 ? 基于解釋的學(xué)習(xí)，不考慮很多實例，采用演繹推理，少用歸納。 ? 利用單個問題的求解例子，依領(lǐng)域知識對實例進(jìn)行詳細(xì)分析，構(gòu)造求解過程的因果解釋結(jié)構(gòu)，并獲取控制知識，然后對解釋進(jìn)行推廣得到一般性描述，以便用于指導(dǎo)以后求解類似問題。 參考書： 《 高級人工智能 》 史忠植，科學(xué)出版社 基于解釋的學(xué)習(xí) (簡介 ) ? 歷史 : ? 起源于經(jīng)驗學(xué)習(xí)， 50年代末出現(xiàn)用符號來標(biāo)記存儲結(jié)構(gòu)模型的方法（神經(jīng)模型）。如同圍棋、象棋大師腦中的棋譜。開始將chunk作為對人類行為進(jìn)行模擬的模型基礎(chǔ)。 ? 最終是 1983年，美國 Illinois大學(xué)的 Dejong提出了基于解釋的學(xué)習(xí)。 ? 1986又進(jìn)一步提出了明確的定義。 基于解釋的學(xué)習(xí) (簡介 ) ? 解釋： ? 專家系統(tǒng)是給用戶看的，所以，推理過程要說明 ? 搜索過程記錄下來，以便對錯誤決策進(jìn)行追蹤，發(fā)現(xiàn)知識庫和概念的錯誤。 方法：預(yù)制文本法；執(zhí)行追蹤法；策略解釋法。因此要考慮可操作性和一般性。 ? 可操作：如果一個概念描述能有效的用于識別相應(yīng)概念的例子。 ? 可操作滿足：可用性。 效用性。 概念描述空間 D1 不可操作 D2 可操作 例子空間 概念空間 C1 I3 I2 I1 解釋學(xué)習(xí)的空間描述 外延 集合 內(nèi)涵 屬性 基于解釋的學(xué)習(xí) (簡介 ) 解釋空間的描述 ? 概念空間：某個學(xué)習(xí)程序能描述的所有概念的集合，其中每一點對應(yīng)例子空間的唯一的一個子集合。 但概念空間的一個點可以對應(yīng)概念描述空間的多個點。 對應(yīng)同一概念的兩個描述稱為同義詞。例： D1是搜索的開始結(jié)點， D2是解結(jié)點，解釋是空間的變換，而可操作性是搜索結(jié)束的標(biāo)準(zhǔn)。 EXL 概念描述 的轉(zhuǎn)換 KB PS 結(jié)果是否 可操作 D1 D2 N Y 解釋學(xué)習(xí)的框架 基于解釋的學(xué)習(xí) (簡介 ) 解釋學(xué)習(xí)的模型 ? 執(zhí)行系統(tǒng)： PS ? 學(xué)習(xí)系統(tǒng)： EXL ? 領(lǐng)域知識庫： KB(不同描述間轉(zhuǎn)換的集合 ) 系統(tǒng)工作過程 ? EXL輸入概念 C1的描述 D1（一般是不可操作的） ? 根據(jù) KB中的知識，對其進(jìn)行不同的轉(zhuǎn)換（搜索） ? PS對每個轉(zhuǎn)換結(jié)果進(jìn)行測試，直至轉(zhuǎn)換結(jié)果是 PS可以接受的描述 D2（可操作的）時，學(xué)習(xí)結(jié)束，輸出 D2 基于解釋的學(xué)習(xí) (簡介 ) ? 一般框架： ? 給定：領(lǐng)域知識、目標(biāo)概念、訓(xùn)練實例和操作性準(zhǔn)則。 ? 訓(xùn)練實例：為了解釋學(xué)習(xí)提供的一個例子，解釋學(xué)習(xí)正是從該例出發(fā)，通過運用領(lǐng)域知識進(jìn)行證明，最終推廣出目標(biāo)概念的描述。 ? 找出：滿足操作性準(zhǔn)則的關(guān)于概念的充分條件 基于解釋的學(xué)習(xí) (簡介 ) ? 步驟： ? 產(chǎn)生解釋，求解問題。反復(fù)進(jìn)行直到求解結(jié)束。并獲得了構(gòu)成動作序列，作為解釋結(jié)構(gòu)。 ? 也可以，自頂向下的遍歷證明樹結(jié)構(gòu)。 ? 對得到的解釋結(jié)構(gòu)以及事件進(jìn)行概括。 ? 描述：用邏輯的表示方法 ， 語義清晰 例：見書 ? 產(chǎn)生解釋結(jié)構(gòu)：從目標(biāo)開始反向推理 （ 從上到下 ） 。 ? 略去解釋結(jié)構(gòu)的中間部件 。 解釋學(xué)習(xí)例題 學(xué)習(xí)的目標(biāo)：一個物體 x可以安全的放置在另一個物體 y的上面 ” 。Fragile(y)→Safe tostack(x, y)、 Lighter(x, y)→Safe tostack(x, y) 乘法計算 、 比較計算 Volume(p, v)ΛDensity(p, d)ΛProduct(v, d, w)→Weight(p, w) Weight(p1, w1)ΛWeight(p 2, w2)ΛSmaller(w 1, w2)→Lighter(p 1, p2) Safetostack(obj1, obj2) Lighter(obj1, obj2) Weight(obj1, ) Weight(obj2, 5) Smaller(, 5) Isa(obj2, table) Volume(obj1, 1) Density(obj1, ) Product(1, , ) 1）由 Safetostack(obj1, obj2)，尋找其條件（前件）。 Fragile(y)，所以選擇 Lighter(x, y)。 2）繼續(xù)尋找其前件，由比較計算公式可知 Lighter(obj1, obj2)的前件（條件）為Weight(p1, w1)Λ Weight(p2, w2)Λ Smaller(w1, w2)。 3）在繼續(xù)分別尋找各個元素的前件。直到全部結(jié)點都是葉子結(jié)點，便得到了解的解釋結(jié)構(gòu)樹。 開發(fā)了 PRODIGY學(xué)習(xí)系統(tǒng) ? 克服了 EBG（ 解釋和概括交替進(jìn)行 ） 的過分一般化的缺點 。 ? 目標(biāo)概念學(xué)習(xí) :成功 (preference)、 失敗 (rejection)、 唯一的選擇(selection)、 目標(biāo)互相制約 (restricted) 分析問題求解軌跡 ， 解釋為何滿足該概念 有解：成功；無解：失??；選擇唯一：唯一； 依賴于別的目標(biāo)：互相制約 ? 得到的結(jié)果就是相應(yīng)種類 （ 成功 、 無解 、 唯一 、 制約 ） 的規(guī)則 基于解釋的學(xué)習(xí) (方法 2) ? 具體方法（體系結(jié)構(gòu)圖） ? 解釋過程：就是詳細(xì)的說明過程 。 解釋每一步 ， 從領(lǐng)域庫中選擇與所給例子一致的規(guī)則 ， 生成一個結(jié)點 。 ? 學(xué)習(xí)控制規(guī)則：四種目標(biāo)概念 ， 有四種固定的控制規(guī)則模式 。 領(lǐng)域規(guī)則 ， 特別是問題求解器的推理規(guī)則實際上已經(jīng)進(jìn)行了概括化處理 。 基于解釋的學(xué)習(xí) (方法 3) 由外部指導(dǎo)學(xué)習(xí)控制 chunk方法 ? 1987年斯坦福大學(xué)與密西根大學(xué)教授提出 。 ? 體系結(jié)構(gòu)圖 ? 外部指導(dǎo) ? 直接的指令式：由專家指定一個算子求解 。 然后再請求專家勸告 （ 一個直觀簡單問題 ） 。 ? 以專家指定的算子或求解簡單問題所得出的結(jié)算子作為結(jié)論動作 ， 至此生成產(chǎn)生式規(guī)則 。 ? 可操作性標(biāo)準(zhǔn)： “ 概念描述應(yīng)該表示為描述訓(xùn)練例的那些謂詞或其它領(lǐng)域理論中挑選出來的易于估值的謂詞 ” ； “ 如果一個概念能有效的用于識別相應(yīng)的概念的例子，則它是可操作的 ” ? PRODIGY ? SOAR系統(tǒng) ? MRSEBG系統(tǒng) ? METALEX系統(tǒng) 可操作性對于基于解釋的學(xué)習(xí)系統(tǒng)是至關(guān)重要的 。 盡管在這方面國內(nèi)外的研究人員一直在尋找有效的處理方法 ， 但多數(shù)只是處于理論研究階段 ， 應(yīng)用于實際系統(tǒng)中的尚未達(dá)到令人滿意的程度 ?；跊Q策樹的學(xué)習(xí)方法可以進(jìn)行不相關(guān)的多概念學(xué)習(xí)，具有簡單快捷的優(yōu)勢，已經(jīng)在各個領(lǐng)域取得廣泛應(yīng)用。 ? 從一類無序、無規(guī)則的事物（概念）中推理出決策樹表示的分類規(guī)則。 ? 1979年 , . Quinlan 給出 ID3算法，并在 1983年和 1986年對 ID3 進(jìn)行了總結(jié)和簡化，使其成為決策樹學(xué)習(xí)算法的典型。 ? 1988年， Utgoff 在 ID4基礎(chǔ)上提出了 ID5學(xué)習(xí)算法，進(jìn)一步提高了效率。 ? 另一類決策樹算法為 CART，與 ， CART的決策樹由二元邏輯問題生成，每個樹節(jié)點只有兩個分枝，分別包括學(xué)習(xí)實例的正例與反例。 決策樹學(xué)習(xí) （概述） ? 隨著決策樹學(xué)習(xí)算法的廣泛應(yīng)用，包括 和 CART的各種算法得到進(jìn)一步改進(jìn)。 ? 這些改進(jìn)算法旨在結(jié)合各種方案的優(yōu)勢，取得更合理的分類效果，總結(jié)出更通用的規(guī)則。 ? 決策樹的每一層節(jié)點依照某一屬性值向下分為子節(jié)點，待分類的實例在每一節(jié)點處與該節(jié)點相關(guān)的屬性值進(jìn)行比較，根據(jù)不同的比較結(jié)果向相應(yīng)的子節(jié)點擴展，這一過程在到達(dá)決策樹的葉節(jié)點時結(jié)束，此時得到結(jié)論。整個決策樹就對應(yīng)著一組析取的規(guī)則。在學(xué)習(xí)的過程中，不需要使用者了解過多背景知識，只需要對訓(xùn)練例子進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。 決策樹學(xué)習(xí) （決策樹） ? 樹是由節(jié)點和分枝組成的層次數(shù)據(jù)結(jié)構(gòu)。樹是圖的一個特例，圖是更一般的數(shù)學(xué)結(jié)構(gòu)，如貝葉斯網(wǎng)絡(luò)。 根結(jié)點 個子大 可能是松鼠 可能是老鼠 可能是大象 在水里 會吱吱叫 鼻子長 脖子長 個子小 不會吱吱叫 鼻子短 脖子短 可能是長頸鹿 在陸地上 可能是犀牛 可能是河馬 決策樹學(xué)習(xí) （決策樹） ? 可以看到，一個決策樹的內(nèi)部結(jié)點包含學(xué)習(xí)的實例，每層