【正文】 值。 2022/2/15 《人工智能》 66 強化學習的原理 強化學習把學習看作試探過程，基本過程如圖所示。 ? 1989年 Watkins提出了 Q學習，也把強化學習的三條主線扭在了一起。 ? 強化學習的發(fā)展階段（ 70 年代 ~ ） ? 1972年， Klopf把試錯學習和時序差分結合在一起。 1969年， Minsky因在人工智能方面的貢獻而獲得計算機圖靈獎。同年， Farley和 Clark也在計算上對它進行了研究。 ? 動物的試錯學習，包含兩個含義：選擇和聯(lián)系，對應計算上的搜索和記憶。 1911年 Thorndike提出了效果律（ Law of Effect）：一定情景下讓動物感到舒服的行為，就會與此情景增強聯(lián)系（強化），當此情景再現(xiàn)時，動物的這種行為也更易再現(xiàn)；相反，讓動物感覺不舒服的行為，會減弱與情景的聯(lián)系，此情景再現(xiàn)時，此行為將很難再現(xiàn)。 我們特指這種學習技術為強化學習技術。 如果將強化學習作為一類問題，目前的學習技術大致可分成兩類： ? 其一是搜索智能系統(tǒng)的行為空間，以發(fā)現(xiàn)系統(tǒng)最優(yōu)的行為。 強化學習不同于連接主義學習中的監(jiān)督學習，主要表現(xiàn)在教師信號上，強化學習中由環(huán)境提供的強化信號是對產生動作的好壞作一種評價 (通常為標量信號 ) ，而不是告訴強化學習系統(tǒng)如何去產生正確的動作。而在連接主義學習中，把學習算法分為非監(jiān)督學習 (unsupervised learning) 、監(jiān)督學習 (supervised learning) 和強化學習三種。 圖 EBG問題 2022/2/15 《人工智能》 62 強化學習 強化學習 (reinforcement learningRL，又稱再勵學習，評價學習 ) 在智能控制機器人及分析預測等領域有許多應用。 2022/2/15 《人工智能》 61 EBG求解問題的形式描述 : 給定： (1) 目標概念描述 TC； (2) 訓練實例 TE； (3) 領域知識 DT； (4) 操作準則 OC。 1986年米切爾（ Mitchell）等人為基于解釋的學習提出了一個統(tǒng)一的算法 EBG，該算法建立了基于解釋的概括過程，并運用知識的邏輯表示和演繹推理進行問題求解。 (2) 對例子的結構進行概括性解釋。 2022/2/15 《人工智能》 59 解釋學習 基于解釋的學習： ? 一種從單個觀察中抽象出通用規(guī)則的方法 ? 目標是下次可以快速地解決類似的問題 ? 通過保存結果和避免從零開始解決問題來提高速度 ? 更進一步 EBL從觀察到規(guī)則 解釋學習 (ExplanationBased Learning, 簡稱 EBL)是一種分析學習方法，在領域知識指導下 , 通過對單個問題求解實例的分析 , 構造出求解過程的因果解釋結構 , 并獲取控制知識 ,以便用于指導以后求解類似問題。 把新范例加入到范例庫中， 需要對它建立有效的索引，這樣以后才能對之作出有效的回憶。修改和精化源范例庫 , 其中包括泛化和抽象等過程。這是學習也是知識獲取。 (9) 范例保存 : 新問題得到了解決，則形成了一個可能用于將來情形與之相似的問題。 (7) 范例修補 : 有些類似于類比轉換，區(qū)別在于修補過程的輸入是解方案和一個失敗報告，而且也許還包含一個解釋，然后修改這個解以排除失敗的因素。有時對成功也同樣做出解釋。需要根據它們之間的不同對復用的求解方案進行調整。 (5) 類比轉換 : 轉換源范例中同目標范例相關的信息，以便應用于目標范例的求解過程中。該標準定義得好，會使得檢索出的范例十分有用，否則將會嚴重影響后面的過程。一般講，范例匹配不是精確的，只能是部分匹配或近似匹配。 (3) 范例檢索 ：利用檢索信息從源范例庫中檢索并選擇潛在可用的源范例。對于那些數量達到成千上萬、而且十分復雜的范例 , 組織和索引問題尤其重要。 2022/2/15 《人工智能》 56 范例學習的主要問題（ 1） (1) 范例表示 ：基于范例推理方法的效率和范例表示緊密相關。 2022/2/15 《人工智能》 55 范例的索引 建立范例索引有三個原則： ① 索引與具體領域有關 。 有了結果內容 ， CBR在給出建議解時有能給出曾經成功地工作的范例 ， 同時也能利用失敗的范例來避免可能會發(fā)生的問題 。 它可能是對問題的簡單解答 ， 也可能是得出解答的推導過程 。 2022/2/15 《人工智能》 53 基于范例學習的一般過程 新問題 新范例 檢索 歷史范例 范例庫 復用 保存 修正范例 修正 解答范例 確認解 建議解 2022/2/15 《人工智能》 54 范例的內容 (1) 問題或情景描述： 是對要求解的問題或要理解的情景的描述 ， 一般要包括這些內容：當范例發(fā)生時推理器的目標 ， 完成該目標所要涉及的任務 ， 周圍世界或環(huán)境與可能解決方案相關的所有特征 。因此在 CBR中，學習的主要任務是對案例庫的豐富和優(yōu)化。 如在法律中的判例 ，基于范例推理能很好發(fā)揮作用 。 ? 過去求解成功或失敗的經歷可以指導當前求解時該怎樣走向成功或避開失敗 ， 這樣可以改善求解的質量 。 2022/2/15 《人工智能》 50 范例推理基本流程 提出解決方案 確認解決方案 以前案例 新案例 學過的 案例 取回案例 新案例 解決的案例 修改 案例 一般知識 提取 使用 修改 保留 問題 2022/2/15 《人工智能》 51 ? 基于范例推理中知識表示是以范例為基礎 ， 范例的獲取比規(guī)則獲取要容易 ， 大大簡化知識獲取 。 在基于范例推理中，把當前所面臨的問題或情況稱為目標范例 (target case)，而把記憶的問題或情況稱為源范例 (base case)。 2022/2/15 《人工智能》 49 基于范例的推理 人們?yōu)榱私鉀Q一個新問題，先是進行回憶，從記憶中找到一個與新問題相似的范例，然后把該范例中的有關信息和知識復用到新問題的求解之中。 ? 范例可以是各式各樣的，可有不同的形狀和粒度，可涵蓋或大或小的時間片，可帶有問題的解答或動作執(zhí)行后的效應。 2022/2/15 《人工智能》 48 基于范例的學習 范例（ case）： “范例是一段帶有上下文信息的知識，該知識表達了推理機在達到其目標的過程中能起關鍵作用的經驗”。 (4) 對類推得到的新問題的知識進行校驗。 (2) 對輸入的兩組條件，根據其描述，按某種相似性的定義尋找兩者可類比的對應關系。所以類比學習既有歸納過程，又有演繹過程。 2022/2/15 《人工智能》 47 類比學習 類比學習是基于類比推理的。 (3) 建立對應映射 在 S與 T的相似情況之間建立相似元素的對應關系，并建立起相應的映射。 類比推理過程如下： (1) 回憶與聯(lián)想 遇到新情況或新問題時，首先通過回憶與聯(lián)想在 S中找出與當前情況相似的情況，這些情況是過去已經處理過的，有現(xiàn)成的解決方法及相關的知識。 2022/2/15 《人工智能》 45 類比推理和類比學習 類比推理 類比推理是由新情況與已知情況在某些方面的相似來推出它們在其它相關方面的相似。 類比學習 (learning by analogy)就是通過類比，即通過相似事物加以比較所進行的一種學習。當然，一般情況下在歐氏空間中通常采用神經網絡來構造分類器。 （ 2）決策樹方法同樣可用于連續(xù)取值的特征量。其中，路徑的非葉結點部分構成了規(guī)則的條件部分（ IF部分），葉結點給出了規(guī)則的結論（ THEN部分）。 2022/2/15 《人工智能》 43 討論 （ 1）根據決策樹可以得出若干條規(guī)則。 葉結點的類別 設分類問題為 C類的分類問題。 上述合并條件中，△ i(n)代表了由于合并所導致的不純凈度的損失。 2022/2/15 《人工智能》 42 決策樹修剪（ 3） ( ) ( ) ( ) ( )ny nnynnnN Ni n i n i n i nNN??? ? ? ?????()i n A??（ 3）兄弟葉結點合并的條件為 其中， ny及 nn為兄弟葉結點， n為其父結點。對于新形成的決策樹，可以重復上述兄弟結點的合并過程，直到最后得到一棵決策樹，其中任意兩個兄弟葉結點都不再滿足合并的條件。如果可以合并，則對這些兄弟結點進行合并，并將其父結點設為葉結點。這樣構造的決策樹，其葉結點均為不可再進一步劃分的結點。其基本思路是，首先使決策樹得到充分生長，然后再通過修剪降低決策樹的復雜度，從而保證決策樹的泛化能力。決策樹的優(yōu)化準則為：使該準則函數取得最小值。 方法 4：采用如下的性能準則函數： 其中 size 代表決策樹的復雜度， i(n)為結點 n 的非純凈度。采用該方法同樣不需要將樣本集合分為訓練集及測試集。在決策樹的訓練過程中，對于任意一個結點 n，如果 Nn/NA，則確定結點n為葉結點。決策樹直接采用全體樣本集合構建。在決策樹的訓練過程中，對于任意一個結點 n，如果該結點的最優(yōu)劃分（即最優(yōu)問題對該結點的樣本集合所作的劃分）所導致的純凈度的提高小于 A，則將該結點定為葉結點。根據學習曲線，選擇在測試集上性能最佳的決策樹為最終的決策樹。每展開一層子結點，并將其設為葉結點，就得到一棵決策樹，然后采用測試集對所得決策樹的分類性能進行統(tǒng)計。將樣本集合分為訓練集與測試集。具體方法為：在結點還可以進一步劃分的時候，可根據預先設定的準則停止對其劃分，并將其設置為葉結點。此時決策樹的復雜度偏低。葉結點的不純凈度過高，對訓練樣本的正確分類能力過低稱為欠學習（此時，決策樹不能夠充分提取樣本集合中蘊涵的有關樣本真實分布的信息。此時決策樹的復雜度偏高。并不絕對追求葉結點的純凈度。這一現(xiàn)象稱為過度擬合 (指決策數對訓練樣本過度擬合，從而背離了樣本的真實分布 )。因此，該集合并不能完全描述樣本 (即特征向量 )真實分布。該集合中的樣本是隨機的。這樣構造的決策樹，其葉結點均為不可再進一步劃分的結點。此時結點 n可以進一步劃分。此時結點 n不可進一步劃分。此時結點 n不可進一步劃分。 2022/2/15 《人工智能》 35 葉結點的確定問題 決策樹結點劃分的原則是使其子結點盡可能純凈（指兩個子結點的平均純凈度最高）。 由于特征的數量是有限的，每個特征的可能取值也是有限的，所以所有可能提出的問題是可以枚舉的。 結點 n的最佳選擇問題：使△ i(n)取得最大值。 2022/2/15 《人工智能》 32 最佳提問的選擇（ 3） ( | )21( ) ( | ) l og jc pnjji n p n ????? ?( | )jnjnNpnN? ?（ 8）結點 n非純凈度的定義 其中， i(n)為結點 n的非純凈度， Nn 為結點 n對應的樣本的數量， Njn為結點 n中屬于 ?j的樣本的數量，C為類別的個數。復雜度小的分類器通常具有較好的泛化能力。 （ 6）根據上述準則（純凈度準則）構建決策樹，可以保證決策樹的復雜度較?。ńY點數量少、深度?。?。 2022/2/15 《人工智能》 31 最佳提問的選擇（ 2） （ 4）當如上得到的某一個子結點足夠純凈時，就可以確定該結點為葉結點，并給出其類別。同樣，根據結點 N的提問，可以將DN進一步劃分為兩個部分 DNy及 DNn（其中， DNy為回答YES的樣本， DNn為回答 NO的樣本），并得到與之相對應的兩個子結點。我們希望選擇一個這樣問題進行提問：使得 Dy及 Dn盡可能純凈。 （ 2）根結點的構建：根結點對應于訓練樣本集 D。每一個葉結點給出最終的分類。 2022/2/15 《人工智能》 29 決策樹的構建 ? 已知訓練樣本集，構造決策樹需要解決以下幾個問題（考慮 Binary Decision Trees）： （ 1）最佳提問的選擇：應該先對哪一個屬性提出問題？應該按什么樣的順序提出問題？ 每一個問題都是一個 YES/NO問題。然后重復整個過程，用每個分枝節(jié)點關聯(lián)的訓練樣例來選取在該點被測試的最佳屬性。分類能力最好的屬性被選作樹的根節(jié)點的測試。 ? 構造過程是從“哪一個屬性將在樹的根節(jié)點被測試”這個問題開始。 ? ID3是一種自頂向下增長樹的貪婪算法，在每個節(jié)點選取能最好分類樣例的屬性。 該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間 。 2022/2/15 《人工智能》 27 決策