【正文】 對數(shù)據(jù)項集 X ? I ，稱 T 包含 X 當(dāng)且僅當(dāng) X ? T 對任一項集 X ? I ，在事務(wù)集 D中的 支持度 定義為 X在該事務(wù)集中出現(xiàn)的相對頻度，即： %100}|{),s up( ??? D TXTDX2022/2/15 《人工智能》 96 關(guān)聯(lián)規(guī)則 具有形式： X=Y 這里 X ? I , Y ? I ，且 X∩Y =Φ, X 稱為規(guī)則的條件 , Y 稱為規(guī)則的結(jié)果。例如，在所有購買激光打印機(jī)的人中，半年后有 80%的人再購買新硒鼓， 20%的人用舊硒鼓裝碳粉。關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫中隱藏的關(guān)聯(lián)網(wǎng)。 可視化方法 可視化（ visualization）就是把數(shù)據(jù)、信息和知識轉(zhuǎn)化為可視的表示形式的過程。 范例推理是直接使用過去的經(jīng)驗或解法來求解給定的問題。 統(tǒng)計方法 統(tǒng)計方法是從事物的外在數(shù)量上的表現(xiàn)去推斷該事物可能的規(guī)律性。 主要是對上述數(shù)據(jù)進(jìn)行再加工，包括消除“噪聲”或去掉無用的數(shù)據(jù)，彌補(bǔ)遺漏數(shù)據(jù)，說明時間序列信息和已知的變化等。 (4) 可被人理解： 知識發(fā)現(xiàn)的一個目標(biāo)就是將數(shù)據(jù)庫中隱含的模式以容易被人理解的形式表現(xiàn)出來，從而幫助人們更好地了解數(shù)據(jù)庫中所包含的信息。數(shù)據(jù)庫知識發(fā)現(xiàn) (knowledge discovery and database, 簡稱 KDD)技術(shù)就是在這種背景下應(yīng)運而生的，我們把 KDD簡稱為知識發(fā)現(xiàn)。其中通過構(gòu)造 e(s)函數(shù)，即可以保證在一次學(xué)習(xí)循環(huán)中值函數(shù)正確更新。所謂一步 TD 算法，是指 Agent 獲得的瞬時報酬值僅回退一步，也就是說只是修改了相鄰狀態(tài)的估計值。 MC算法基于平均化取樣回報來解決強(qiáng)化學(xué)習(xí)問題，它將解決的問題分解成幕 ( episode) 。因此在 s狀態(tài)下的值函數(shù)要考慮不同學(xué)習(xí)循環(huán)中所有返回函數(shù)的數(shù)學(xué)期望。記 R(s, a, s’)為系統(tǒng)在狀態(tài) s采用 a動作使環(huán)境狀態(tài)轉(zhuǎn)移到 s’獲得的瞬時獎賞值，簡記為 Rass’；記 P(s, a, s’)為系統(tǒng)在狀態(tài) s采用 a動作使環(huán)境狀態(tài)轉(zhuǎn)移到 s’的概率，簡記為 Pass’ 。 Agent 的任務(wù)就是學(xué)習(xí)控制策略 π: S →A ，能夠最大化期望獎賞值的總和。 ? 1992年， Tesauro用強(qiáng)化學(xué)習(xí)成功了應(yīng)用到西洋雙陸棋中，稱為TDGammon 。所以， 1954年， Minsky在他的博士論文中實現(xiàn)了計算上的試錯學(xué)習(xí)。 2022/2/15 《人工智能》 63 強(qiáng)化學(xué)習(xí)通常包括兩個方面的含義： ① 一方面是將強(qiáng)化學(xué)習(xí)作為一類問題； ② 另一方面是指解決這類問題的一種技術(shù)。下圖表示 EBG問題。 在決定選取范例的哪些信息進(jìn)行保留時，一般要考慮以下幾點：和問題有關(guān)的特征描述；問題的求解結(jié)果；以及解答為什么成功或失敗的原因及解釋?；诮忉尩乃饕彩且环N重要的方法。因此，它要求有一個相似度的評價標(biāo)準(zhǔn)。 數(shù)據(jù)庫中的索引是通用的 ， 目的僅僅是追求索引能對數(shù)據(jù)集合進(jìn)行平衡的劃分從而使得檢索速度最快；而范例索引則要考慮是否有利于將來的范例檢索 ， 它決定了針對某個具體的問題哪些范例被復(fù)用； ② 索引應(yīng)該有一定的抽象或泛化程度 ， 這樣才能靈活處理以后可能遇到的各種情景 ， 太具體則不能滿足更多的情況； ③ 索引應(yīng)該有一定的具體性 ， 這樣才能在以后被容易地識別出來 ， 太抽象則各個范例之間的差別將被消除 。 在 CBR中，大多數(shù)學(xué)習(xí)是通過如下兩種方式體現(xiàn)的：一個是新范例的積累，推理系統(tǒng)的范例對問題的覆蓋越多，其功能越強(qiáng)；另一個是設(shè)計覆蓋了成功事例也覆蓋了失敗事例的推理要比只設(shè)計成功情況的推理系統(tǒng)要好，索引的重新賦值，調(diào)節(jié)索引可使得范例能在更合適的時機(jī)被回憶。粗略地說，基于范例推理就是由目標(biāo)范例的提示而獲得記憶中的源范例，并由源范例來指導(dǎo)目標(biāo)范例求解的一種策略。驗證正確的知識存入知識庫中，而暫時還無法驗證的知識只能作為參考性知識，置于數(shù)據(jù)庫中。 (4) 轉(zhuǎn)換 在上一步建立的映射下，把 S中的有關(guān)知識引到 T中來，從而建立起求解當(dāng)前問題的方法或者學(xué)習(xí)到關(guān)于 T的新知識。 2022/2/15 《人工智能》 44 類比學(xué)習(xí) 類比 (analogy)是一種很有用的和有效的推理方法，它能夠清晰簡潔地描述對象間的相似性；也是人類認(rèn)識世界的一種重要方法。對于葉結(jié)點 n，如果在該結(jié)點對應(yīng)的樣本中，屬于第 i 類的樣本數(shù)量最多，則判該葉結(jié)點為第 i類。在對所有可以合并的兄弟葉結(jié)點進(jìn)行合并后，可以形成一棵新的決策樹。該準(zhǔn)則函數(shù)表達(dá)出了過度擬合與欠學(xué)習(xí)之間的相互關(guān)系。采用該方法不需要將樣本集合分為訓(xùn)練集及測試集。 2022/2/15 《人工智能》 38 確定葉結(jié)點的基本方法（ 1） 方法 1：采用測試集的方法。絕對追求葉結(jié)點的純凈度導(dǎo)致過度擬合。這種葉結(jié)點的確定方法是否可行？ ? 答案：決策樹是根據(jù)訓(xùn)練樣本的集合構(gòu)成的。對于任意一個結(jié)點 n，可以出現(xiàn)以下三種情況： （ 1）結(jié)點 n中的樣本屬于同一類，即結(jié)點 n絕對純凈。這一原則稱為 Occam’s razor。 （ 3）中間結(jié)點的構(gòu)造：對于每一個中間結(jié)點（結(jié)點 N），都有一個與之對應(yīng)的子集 DN。這形成了對合格決策樹的貪婪搜索，也就是算法從不回溯重新考慮以前的選擇。這種方法是 ID3算法 (Quinlan 1986)和后繼的 (Quinlan 1993)的基礎(chǔ) 。 ? 目標(biāo)函數(shù)具有離散的輸出值：決策樹給每個實例賦予一個布爾型的分類。 2022/2/15 《人工智能》 23 決策樹表示法 ? 決策樹通過把實例從根節(jié)點排列 (sort)到某個葉子節(jié)點來分類實例，葉子節(jié)點即為實例所屬的分類。 2022/2/15 《人工智能》 22 歸納學(xué)習(xí)示例 決策樹學(xué)習(xí) 決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。 歸納學(xué)習(xí)系統(tǒng)的模型如圖所示。 （ 2） 歸納推理 是應(yīng)用歸納方法，從足夠多的具體事例中歸納出一般性知識，提取事物的一般規(guī)律；它是一種從個別到一般的推理。在機(jī)械學(xué)習(xí)中我們只記憶計算的輸入輸出，忽略了計算過程，這樣就把計算問題化簡成存取問題。 ③連接學(xué)習(xí)：人工神經(jīng)網(wǎng)絡(luò)學(xué)習(xí) ④遺傳學(xué)習(xí) ： 模擬自然界遺傳與變異機(jī)制 2022/2/15 《人工智能》 13 機(jī)械學(xué)習(xí) 機(jī)械學(xué)習(xí)的模式 機(jī)械學(xué)習(xí)是最簡單的機(jī)器學(xué)習(xí)方法。每一個學(xué)習(xí)系統(tǒng)都要求具有某些知識理解環(huán)境提供的信息，分析比較，做出假設(shè)，檢驗并修改這些假設(shè)。 (2) 知識庫是影響學(xué)習(xí)系統(tǒng)設(shè)計的第二個因素。 2022/2/15 《人工智能》 10 機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu) ? 環(huán) 境是指系統(tǒng)外部信息的來源，它可以是系統(tǒng)的工作對象，也可以包括工作對象和外界條件。 機(jī)器學(xué)習(xí)的最新階段始于 1986年。 本階段的研究目標(biāo)是模擬人類的概念學(xué)習(xí)過程，并采用邏輯結(jié)構(gòu)或圖結(jié)構(gòu)作為機(jī)器內(nèi)部描述。 更為嚴(yán)格的提法是：機(jī)器學(xué)習(xí)是一門研究機(jī)器獲取新知識和新技能，并識別現(xiàn)有知識的學(xué)問。 學(xué)習(xí)的很多過程都是由改進(jìn)所學(xué)的技能組成。 ? 學(xué)習(xí)是技能的獲取。 機(jī)器學(xué)習(xí)是繼專家系統(tǒng)之后人工智能應(yīng)用的又一重要研究領(lǐng)域。學(xué)習(xí)的基本機(jī)制是把一種情況下成功的表現(xiàn)行為轉(zhuǎn)移到另一種類似的新情況中。 ? 西蒙的觀點：學(xué)習(xí)就是系統(tǒng)在不斷重復(fù)的工作中對本身能力的增強(qiáng)或者改進(jìn)，使得系統(tǒng)在下一次執(zhí)行同樣任務(wù)或類似任務(wù)時，會比現(xiàn)在做得更好或效率更高。我們的意思是，此人已經(jīng)掌握了有關(guān)物理學(xué)的基本概念，并且理解其含義，同時還懂得這些概念之間以及它們與物理世界之間的關(guān)系。人類的學(xué)習(xí)一般表現(xiàn)為這兩種活動的結(jié)合。 在這個時期，所研究的是 “ 沒有知識 ” 的學(xué)習(xí)，即 “ 無知 ”學(xué)習(xí)；其研究目標(biāo)是各類自組織系統(tǒng)和自適應(yīng)系統(tǒng)；指導(dǎo)本階段研究的理論基礎(chǔ)是早在 40年代就開始研究的神經(jīng)網(wǎng)絡(luò)模型。1984年 ,《 機(jī)器學(xué)習(xí) 》 雜志問世。 ? 1995年，在加拿大召開了第一屆知識發(fā)現(xiàn)和數(shù)據(jù)挖掘國際學(xué)術(shù)會議。 ? 執(zhí)行單元處理系統(tǒng)所面臨的現(xiàn)實問題，即應(yīng)用知識庫中的知識求解問題。 ? 容易修改知識庫。 ④類比學(xué)習(xí)：應(yīng)用類似任務(wù)的知識求解當(dāng)前問題。 (X1,X2,…, Xn) (Y1,Y2,…, Yn) f ((X1,X2,…, Xn),(Y1,Y2,…, Yn)) 存儲 2022/2/15 《人工智能》 14 數(shù)據(jù)化簡 Lenat,Hayes Roth，和 Klahr等人于 1979年關(guān)于機(jī)械學(xué)習(xí)提出一種有趣的觀點。 2022/2/15 《人工智能》 16 歸納學(xué)習(xí) 歸納學(xué)習(xí)是目前研究得最多的學(xué)習(xí)方法，其學(xué)習(xí)目的是為了獲得新的概念、構(gòu)造新的規(guī)則或發(fā)現(xiàn)新的理論。 (3) 背景知識，用于定義有關(guān)觀察陳述、候選歸納斷言以及任何相關(guān)問題領(lǐng)域知識、假設(shè)和約束，其中包括能夠刻畫所求歸納斷言的性質(zhì)的優(yōu)先準(zhǔn)則。 觀察發(fā)現(xiàn)學(xué)習(xí) 觀察發(fā)現(xiàn)學(xué)習(xí)又稱為描述性概括，其目標(biāo)是確定一個定律或理論的一般性描述，刻畫觀察集，指定某類對象的性質(zhì)。決策樹學(xué)習(xí)算法有很多，比如 ID、 ASSISTANT等等。 樣本集：一批水果，知道其特征向量及類別 問 題：一個新的水果，觀測到了其特征向量，將其分類 2022/2/15 《人工智能》 24 2022/2/15 《人工智能》 25 通常決策樹代表實例屬性值約束的合取 (conjunction)的析取式 (disjunction)。 2022/2/15 《人工智能》 27 決策樹學(xué)習(xí)的常見問題 ? 確定決策樹增長的深度，避免過度擬合； ? 處理連續(xù)值的屬性； ? 選擇一個適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)； ? 處理屬性值不完整的訓(xùn)練數(shù)據(jù)； ? 處理不同代價的屬性； ? 提高計算效率。分類能力最好的屬性被選作樹的根節(jié)點的測試。 （ 2）根結(jié)點的構(gòu)建：根結(jié)點對應(yīng)于訓(xùn)練樣本集 D。 （ 6）根據(jù)上述準(zhǔn)則（純凈度準(zhǔn)則）構(gòu)建決策樹，可以保證決策樹的復(fù)雜度較?。ńY(jié)點數(shù)量少、深度?。?。 由于特征的數(shù)量是有限的，每個特征的可能取值也是有限的，所以所有可能提出的問題是可以枚舉的。此時結(jié)點 n可以進(jìn)一步劃分。這一現(xiàn)象稱為過度擬合 (指決策數(shù)對訓(xùn)練樣本過度擬合，從而背離了樣本的真實分布 )。此時決策樹的復(fù)雜度偏低。根據(jù)學(xué)習(xí)曲線，選擇在測試集上性能最佳的決策樹為最終的決策樹。采用該方法同樣不需要將樣本集合分為訓(xùn)練集及測試集。這樣構(gòu)造的決策樹，其葉結(jié)點均為不可再進(jìn)一步劃分的結(jié)點。 上述合并條件中，△ i(n)代表了由于合并所導(dǎo)致的不純凈度的損失。 （ 2）決策樹方法同樣可用于連續(xù)取值的特征量。 類比推理過程如下： (1) 回憶與聯(lián)想 遇到新情況或新問題時，首先通過回憶與聯(lián)想在 S中找出與當(dāng)前情況相似的情況，這些情況是過去已經(jīng)處理過的，有現(xiàn)成的解決方法及相關(guān)的知識。 (2) 對輸入的兩組條件，根據(jù)其描述，按某種相似性的定義尋找兩者可類比的對應(yīng)關(guān)系。 2022/2/15 《人工智能》 49 基于范例的推理 人們?yōu)榱私鉀Q一個新問題，先是進(jìn)行回憶，從記憶中找到一個與新問題相似的范例，然后把該范例中的有關(guān)信息和知識復(fù)用到新問題的求解之中。 如在法律中的判例 ，基于范例推理能很好發(fā)揮作用 。 有了結(jié)果內(nèi)容 ， CBR在給出建議解時有能給出曾經(jīng)成功地工作的范例 ， 同時也能利用失敗的范例來避免可能會發(fā)生的問題 。 (3) 范例檢索 ：利用檢索信息從源范例庫中檢索并選擇潛在可用的源范例。需要根據(jù)它們之間的不同對復(fù)用的求解方案進(jìn)行調(diào)整。這是學(xué)習(xí)也是知識獲取。 (2) 對例子的結(jié)構(gòu)進(jìn)行概括性解釋。而在連接主義學(xué)習(xí)中，把學(xué)習(xí)算法分為非監(jiān)督學(xué)習(xí) (unsupervised learning) 、監(jiān)督學(xué)習(xí) (supervised learning) 和強(qiáng)化學(xué)習(xí)三種。 1911年 Thorndike提出了效果律（ Law of Effect）：一定情景下讓動物感到舒服的行為，就會與此情景增強(qiáng)聯(lián)系（強(qiáng)化），當(dāng)此情景再現(xiàn)時，動物的這種行為也更易再現(xiàn)；相反，讓動物感覺不舒服的行為，會減弱與情景的聯(lián)系，此情景再現(xiàn)時，此行為將很難再現(xiàn)。 ? 強(qiáng)化學(xué)習(xí)的發(fā)展階段（ 70 年代 ~ ） ? 1972年， Klopf把試錯學(xué)習(xí)和時序差分結(jié)合在一起。 強(qiáng)化學(xué)習(xí)的結(jié)構(gòu) Agent 環(huán)境 狀態(tài) s 獎賞 r 動作 a 2022/2/15 《人工智能》 67 強(qiáng)化學(xué)習(xí)模型由以下部分組成： 強(qiáng)化學(xué)習(xí)模型 ? 一個離散的狀態(tài)集 S ={ s0 , s1 , s2 , ?, sn }； ? 動作集 A={ a0 , a1 , a2 , ?, an} ； ? 一個強(qiáng)化值集 r ∈ R； ? agent 和環(huán)境交互的狀態(tài) — 動作序列 (si,ai) → ri，表示 agent 在狀態(tài) si 下執(zhí)行動