【正文】 作 ai 獲得的立即獎賞值 ri。下面首先給出馬氏決策過程的形式化定義。但由于在選擇行為策略過程中，要考慮到環(huán)境模型的不確定性和目標(biāo)的長遠(yuǎn)性，因此在策略和瞬時獎賞之間構(gòu)造值函數(shù)（即狀態(tài)的效用函數(shù)），用于策略的選擇。 2022/2/15 《人工智能》 72 強(qiáng)化學(xué)習(xí)算法 到目前為止，研究者們提出了很多強(qiáng)化學(xué)習(xí)算法，近年來對強(qiáng)化學(xué)習(xí)算法的研究已由算法本身逐漸轉(zhuǎn)向研究經(jīng)典算法在各種復(fù)雜環(huán)境中的應(yīng)用，較有影響的強(qiáng)化學(xué)習(xí)算法有 TD 算法， Q 學(xué)習(xí)算法， Sarsa算法，Dyan 算法， R 學(xué)習(xí)算法， H 學(xué)習(xí)等，還有一些改進(jìn)算法，如滯后更新多步 Q學(xué)習(xí)算法等?？刂七^程采用貪心搜索策略。因此，我們考慮：能否在值函數(shù)更新中，不僅僅依賴當(dāng)前狀態(tài)的瞬時獎賞值，也可以利用下一狀態(tài)的瞬時獎賞值，一直到終結(jié)狀態(tài)？ 為此，構(gòu)造一個新的 λ返回函數(shù) Rt′： 211 2 3 Tt t t t t TR r r r r? ? ? ?? ? ? ?? ? ? ? ? ? 其中假定系統(tǒng)在此次學(xué)習(xí)循環(huán)中第 T步后進(jìn)入終結(jié)狀態(tài)。 數(shù)據(jù)庫系統(tǒng)雖然提供了對數(shù)據(jù)的管理和分析處理，但無法從中尋找和發(fā)現(xiàn)某些規(guī)律和模式。 (2) 新穎： 經(jīng)過知識發(fā)現(xiàn)提取出的模式 E必須是新穎的。 2022/2/15 《人工智能》 86 知識發(fā)現(xiàn)的處理過程 Knowledge 原始數(shù)據(jù) 目標(biāo)數(shù)據(jù) 整理后數(shù)據(jù) 變換后數(shù)據(jù) 模式 /模型 知識 數(shù)據(jù) 選擇 數(shù)據(jù) 預(yù)處理 降維 / 轉(zhuǎn)換 數(shù)據(jù) 挖掘 解釋 評價 2022/2/15 《人工智能》 87 數(shù)據(jù)選擇。 知識評價。 (2) 決策樹。 (6) 遺傳算法。嚴(yán)格地講，知識發(fā)現(xiàn)是從數(shù)據(jù)庫中發(fā)現(xiàn)知識的全部過程，而數(shù)據(jù)挖掘則是此全部過程的一個特定的、關(guān)鍵步驟。聚類增強(qiáng)了人們對客觀現(xiàn)實的認(rèn)識，即通過聚類建立宏觀概念。 2022/2/15 《人工智能》 95 關(guān)聯(lián)規(guī)則挖掘 關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫中數(shù)據(jù)項之間存在的潛在關(guān)系的規(guī)則 ，形式為 ： A1∧ A2∧ . . . ∧ Am = B1∧ B2∧ … ∧ Bn 其中 ， A i、 Bj是數(shù)據(jù)庫中 的數(shù)據(jù)項 。即： %100),s up ( ),s up (%100}|{ }|{),( ????? ???? DX DYXTXT TYXTDYXc on f2022/2/15 《人工智。偏差檢測的基本方法是尋找觀測結(jié)果與參照之間的差別。 2022/2/15 《人工智能》 93 ③ 聚類 數(shù)據(jù)庫中的數(shù)據(jù)可分為一系列有意義的子集，或稱為類。 定義： 數(shù)據(jù)挖掘 (Data miningDM ) 是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中提取隱含在其中的、人們事先不知道的但又是潛在有用的信息和知識的過程。 (5) 科學(xué)發(fā)現(xiàn)。 (4) 粗糙集 2022/2/15 《人工智能》 89 機(jī)器學(xué)習(xí)方法 可能用于知識發(fā)現(xiàn)的機(jī)器學(xué)習(xí)方法有： (1) 規(guī)則歸納。 。 如：“成績優(yōu)良 ={80,81,82,83,84,85,86,87,88,89}”不是模式；而“ IF 成績 ≥80 and 成績＜ 90 THEN 成績優(yōu)良”可稱為一個模式。 ? 1960s: Data collection, database creation, IMS and work DBMS. ? 1970s: Relational data model, relational DBMS implementation. ? 1980s: RDBMS, advanced data models (extendedrelational, OO, deductive, etc.) and applicationoriented DBMS (spatial, scientific, engineering, etc). ? 1990s: Data mining and data warehousing, multimedia databases, and Web technology. 2022/2/15 《人工智能》 83 ? 1989 IJCAI Workshop on KDD ? Knowledge Discovery in Databases (G. PiatetskyShapiro and W. Frawley, eds., 1991) ? 19911994 Workshops on KDD ? Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. PiatetskyShapiro, P. Smyth, and R. Uthurusamy, eds., 1996) ? 19951998 AAAI Int. Conf. on KDD and DM (KDD’9598) ? Journal of Data Mining and Knowledge Discovery (1997) ? 1998 ACM SIGKDD ? 1999 SIGKDD’99 Conf. Important dates of data mining 2022/2/15 《人工智能》 84 定義： KDD是從大量數(shù)據(jù)集中辨識出有效的、新穎的、潛在有用的、并可被理解的模式的高級處理過程。 Watkins 定義 Q函數(shù)為在狀態(tài) st下執(zhí)行動作 at ， 且此后按最優(yōu)動作序列執(zhí)行時的折扣累計強(qiáng)化值，即： Q函數(shù)的迭代公式為： (其中 ??[0,1]為學(xué)習(xí)因子 ) ? ?AaasQrasQ tattt ??? ? |),(m a x),( 1?? ?),(),(max),(),( 1 tttattttt asQasQrasQasQ ???? ???2022/2/15 《人工智能》 80 算法在初始過程中初始化每個 Q(s,a)值，然后根據(jù)貪心策略選擇最大的 Q值，再通過迭代式得到實際迭代值，當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時此次迭代過程結(jié)束，再繼續(xù)從初始狀態(tài)進(jìn)行迭代，直至學(xué)習(xí)過程結(jié)束。 TD (?)算法的收斂速度有很大程度上的提高。 對 s 的值函數(shù)的更新有兩種方法： (1) first visit MC 將回報賦予第一次訪問的 s； (2) every visit MC 將每次訪問 s 到 t 的回報平均后賦予 s。 ? ?11()()( ) m a x ( ) ,m a x ( )t t t ta A saass ssa A ssV s E r V s s s a aP R V s????????????? ? ? ?????? ??? 由于強(qiáng)化學(xué)習(xí)中， P函數(shù)和 R函數(shù)未知，系統(tǒng)無法直接求解上面的值函數(shù)。 而強(qiáng)化學(xué)習(xí)著重研究在 P函數(shù)和 R函數(shù)未知的情況下，系統(tǒng)如何學(xué)習(xí)最優(yōu)行為策略。這和生理學(xué)中的條件反射原理是接近的。選擇的動作不僅影響立即強(qiáng)化值而且還影響下一時刻的狀態(tài)及最終強(qiáng)化值。 1969年， Minsky因在人工智能方面的貢獻(xiàn)而獲得計算機(jī)圖靈獎。 我們特指這種學(xué)習(xí)技術(shù)為強(qiáng)化學(xué)習(xí)技術(shù)。 圖 EBG問題 2022/2/15 《人工智能》 62 強(qiáng)化學(xué)習(xí) 強(qiáng)化學(xué)習(xí) (reinforcement learningRL，又稱再勵學(xué)習(xí)，評價學(xué)習(xí) ) 在智能控制機(jī)器人及分析預(yù)測等領(lǐng)域有許多應(yīng)用。 2022/2/15 《人工智能》 59 解釋學(xué)習(xí) 基于解釋的學(xué)習(xí)： ? 一種從單個觀察中抽象出通用規(guī)則的方法 ? 目標(biāo)是下次可以快速地解決類似的問題 ? 通過保存結(jié)果和避免從零開始解決問題來提高速度 ? 更進(jìn)一步 EBL從觀察到規(guī)則 解釋學(xué)習(xí) (ExplanationBased Learning, 簡稱 EBL)是一種分析學(xué)習(xí)方法，在領(lǐng)域知識指導(dǎo)下 , 通過對單個問題求解實例的分析 , 構(gòu)造出求解過程的因果解釋結(jié)構(gòu) , 并獲取控制知識 ,以便用于指導(dǎo)以后求解類似問題。 (9) 范例保存 : 新問題得到了解決，則形成了一個可能用于將來情形與之相似的問題。 (5) 類比轉(zhuǎn)換 : 轉(zhuǎn)換源范例中同目標(biāo)范例相關(guān)的信息，以便應(yīng)用于目標(biāo)范例的求解過程中。對于那些數(shù)量達(dá)到成千上萬、而且十分復(fù)雜的范例 , 組織和索引問題尤其重要。 它可能是對問題的簡單解答 ， 也可能是得出解答的推導(dǎo)過程 。 ? 過去求解成功或失敗的經(jīng)歷可以指導(dǎo)當(dāng)前求解時該怎樣走向成功或避開失敗 ， 這樣可以改善求解的質(zhì)量 。 ? 范例可以是各式各樣的，可有不同的形狀和粒度，可涵蓋或大或小的時間片，可帶有問題的解答或動作執(zhí)行后的效應(yīng)。所以類比學(xué)習(xí)既有歸納過程，又有演繹過程。 2022/2/15 《人工智能》 45 類比推理和類比學(xué)習(xí) 類比推理 類比推理是由新情況與已知情況在某些方面的相似來推出它們在其它相關(guān)方面的相似。其中，路徑的非葉結(jié)點(diǎn)部分構(gòu)成了規(guī)則的條件部分（ IF部分），葉結(jié)點(diǎn)給出了規(guī)則的結(jié)論（ THEN部分）。 2022/2/15 《人工智能》 42 決策樹修剪（ 3） ( ) ( ) ( ) ( )ny nnynnnN Ni n i n i n i nNN??? ? ? ?????()i n A??（ 3）兄弟葉結(jié)點(diǎn)合并的條件為 其中， ny及 nn為兄弟葉結(jié)點(diǎn)， n為其父結(jié)點(diǎn)。其基本思路是，首先使決策樹得到充分生長，然后再通過修剪降低決策樹的復(fù)雜度，從而保證決策樹的泛化能力。在決策樹的訓(xùn)練過程中，對于任意一個結(jié)點(diǎn) n，如果 Nn/NA，則確定結(jié)點(diǎn)n為葉結(jié)點(diǎn)。每展開一層子結(jié)點(diǎn)，并將其設(shè)為葉結(jié)點(diǎn)，就得到一棵決策樹，然后采用測試集對所得決策樹的分類性能進(jìn)行統(tǒng)計。葉結(jié)點(diǎn)的不純凈度過高，對訓(xùn)練樣本的正確分類能力過低稱為欠學(xué)習(xí)（此時，決策樹不能夠充分提取樣本集合中蘊(yùn)涵的有關(guān)樣本真實分布的信息。因此，該集合并不能完全描述樣本 (即特征向量 )真實分布。此時結(jié)點(diǎn) n不可進(jìn)一步劃分。 結(jié)點(diǎn) n的最佳選擇問題：使△ i(n)取得最大值。 2022/2/15 《人工智能》 31 最佳提問的選擇（ 2） （ 4）當(dāng)如上得到的某一個子結(jié)點(diǎn)足夠純凈時，就可以確定該結(jié)點(diǎn)為葉結(jié)點(diǎn)，并給出其類別。每一個葉結(jié)點(diǎn)給出最終的分類。 ? 構(gòu)造過程是從“哪一個屬性將在樹的根節(jié)點(diǎn)被測試”這個問題開始。 ? 訓(xùn)練數(shù)據(jù)可以包含錯誤：決策樹學(xué)習(xí)對錯誤有很好的健壯性，無論是訓(xùn)練樣例所屬的分類錯誤，還是描述這些樣例的屬性值錯誤。然后這個過程再以新節(jié)點(diǎn)為根的子樹上重復(fù)。學(xué)習(xí)得到的決策樹也能再被表示為多個 ifthen規(guī)則，以提高可讀性。 CTX1→ K = (CTX1∨ CTX2)→K 2022/2/15 《人工智能》 20 (3) 沿概念樹上溯： 設(shè) L是一結(jié)構(gòu)性描述項， S代表所有條件中的 L值在概念分層樹上最近的共同祖先，則： KSLC T XKiLC T XKbLC T XKaLC T X????????????????????][][][][?(4) 形成閉合區(qū)域： 設(shè) L是一個具有顯性關(guān)系的描述項， a,b是它的特殊值，則： KbaLCT XKbLCT X KaLCT X ?????????? ??? ])..[(][ ][(5) 將常量轉(zhuǎn)化成變量： KxIFxBFxAFKZIFZBFZAF ??????? ),(),(),(),(),(),( ??2022/2/15 《人工智能》 21 歸納學(xué)習(xí)方法 示例學(xué)習(xí) 示例學(xué)習(xí)（ learning from examples）又稱為實例學(xué)習(xí)，它是通過環(huán)境中若干與某概念有關(guān)的例子，經(jīng)歸納得出一般性概念的一種學(xué)習(xí)方法。前者屬于有師學(xué)習(xí)，后者屬于無師學(xué)習(xí)。 （ 2）環(huán)境的穩(wěn)定性與存儲信息的適用性問題：機(jī)械學(xué)習(xí)系統(tǒng)必須保證所保存的信息適應(yīng)于外界環(huán)境變化的需要，這也就是所謂的信息適用性問題。任何學(xué)習(xí)系統(tǒng)都必須記住它們獲取的知識。 ②指導(dǎo)式學(xué)習(xí)：采用示教式學(xué)習(xí)策略，也稱為示教學(xué)習(xí)。 ? 易于推理。 ? 知識庫用于存放由學(xué)習(xí)環(huán)節(jié)所得到的知識。 2022/2/15 《人工智能》 9 機(jī)器學(xué)習(xí)、知識發(fā)現(xiàn)與數(shù)據(jù)挖掘 ? 知識發(fā)現(xiàn) (Knowledge Discovering in Database)與數(shù)據(jù)挖掘 (Data Mining)是人工智能、機(jī)器學(xué)習(xí) (Machine Learning)與數(shù)據(jù)庫技術(shù)相結(jié)合的產(chǎn)物。 在這個時期，人們從學(xué)習(xí)單個概念擴(kuò)展到學(xué)習(xí)多個概念，探索不同的學(xué)