【正文】 賞值為 : 其中 ∈ [0,1] 為折扣因子。這和生理學(xué)中的條件反射原理是接近的。包含一個(gè)環(huán)境狀態(tài)集 S，系統(tǒng)行為集合 A，獎(jiǎng)賞函數(shù) R： S A→ ? 和狀態(tài)轉(zhuǎn)移函數(shù) P：S A→PD(S) 。 而強(qiáng)化學(xué)習(xí)著重研究在 P函數(shù)和 R函數(shù)未知的情況下，系統(tǒng)如何學(xué)習(xí)最優(yōu)行為策略。 1132211 ????? ?????? tttttt RrrrrrR ??? ?? ?? ??????????????a sassasstttttsVRPassssVrEssREsV)(),(}|)({}|{)( 11???????? 由于環(huán)境是不確定的，系統(tǒng)在某個(gè)策略 π指導(dǎo)下的每一次學(xué)習(xí)循環(huán)中所得到的 Rt有可能是不同的。 ? ?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ù)。 如部分有關(guān)狀態(tài)序列、動作行為集以及同環(huán)境交互產(chǎn)生的獎(jiǎng)賞值的信息。 對 s 的值函數(shù)的更新有兩種方法： (1) first visit MC 將回報(bào)賦予第一次訪問的 s； (2) every visit MC 將每次訪問 s 到 t 的回報(bào)平均后賦予 s。 最簡單的算法為一步 TD 算法，即 TD (0) 算法，是一種自適應(yīng)的策略迭代算法。 TD (?)算法的收斂速度有很大程度上的提高。 2022/2/15 《人工智能》 77 stst + 1rt + 1st + 2λ rt + 1st + 3λ2rt + 2? ?st + TλT 1rt + T 那么值函數(shù)迭代為： ? ? ? ? ? ?t t t tV s V s R V s? ?? ? ?????2022/2/15 《人工智能》 78 由于強(qiáng)化學(xué)習(xí)算法中值函數(shù)的更新是在每一學(xué)習(xí)步進(jìn)行的，為使學(xué)習(xí)算法能在一次學(xué)習(xí)循環(huán)中值函數(shù)滿足上式迭代，設(shè)計(jì) TD(λ)算法如右邊所示。 Watkins 定義 Q函數(shù)為在狀態(tài) st下執(zhí)行動作 at ， 且此后按最優(yōu)動作序列執(zhí)行時(shí)的折扣累計(jì)強(qiáng)化值，即： Q函數(shù)的迭代公式為： (其中 ??[0,1]為學(xué)習(xí)因子 ) ? ?AaasQrasQ tattt ??? ? |),(m a x),( 1?? ?),(),(max),(),( 1 tttattttt asQasQrasQasQ ???? ???2022/2/15 《人工智能》 80 算法在初始過程中初始化每個(gè) Q(s,a)值，然后根據(jù)貪心策略選擇最大的 Q值，再通過迭代式得到實(shí)際迭代值，當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時(shí)此次迭代過程結(jié)束，再繼續(xù)從初始狀態(tài)進(jìn)行迭代，直至學(xué)習(xí)過程結(jié)束。 機(jī)器學(xué)習(xí)能夠通過對數(shù)據(jù)及其關(guān)系的分析，提取出隱含在海量數(shù)據(jù)中的知識。 ? 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ù)集中辨識出有效的、新穎的、潛在有用的、并可被理解的模式的高級處理過程。 (3) 潛在有用： 提取出的模式應(yīng)該是有意義的，這可以通過某些函數(shù)的值來衡量。 如：“成績優(yōu)良 ={80,81,82,83,84,85,86,87,88,89}”不是模式；而“ IF 成績 ≥80 and 成績＜ 90 THEN 成績優(yōu)良”可稱為一個(gè)模式。 數(shù)據(jù)預(yù)處理。 。 2022/2/15 《人工智能》 88 知識發(fā)現(xiàn)的方法 知識發(fā)現(xiàn)的方法有統(tǒng)計(jì)方法、機(jī)器學(xué)習(xí)、神經(jīng)計(jì)算和可視化方法等。 (4) 粗糙集 2022/2/15 《人工智能》 89 機(jī)器學(xué)習(xí)方法 可能用于知識發(fā)現(xiàn)的機(jī)器學(xué)習(xí)方法有： (1) 規(guī)則歸納。 (3) 范例推理。 (5) 科學(xué)發(fā)現(xiàn)。 2022/2/15 《人工智能》 90 神經(jīng)網(wǎng)絡(luò)方法 人工神經(jīng)網(wǎng)絡(luò)建立在可以自學(xué)習(xí)的數(shù)學(xué)模型的基礎(chǔ)之上，它可以對大量復(fù)雜的數(shù)據(jù)進(jìn)行分析，并可以完成對人腦或其他計(jì)算機(jī)來說極為復(fù)雜的模式抽取及趨勢分析。 定義： 數(shù)據(jù)挖掘 (Data miningDM ) 是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中提取隱含在其中的、人們事先不知道的但又是潛在有用的信息和知識的過程。 2022/2/15 《人工智能》 92 數(shù)據(jù)挖掘的類型 數(shù)據(jù)挖掘按其功能劃分主要包括以下幾類 ： ①關(guān)聯(lián)分析 若兩個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的取值重復(fù)出現(xiàn)且概率很高時(shí)，它就存在著某種關(guān)聯(lián)，可以建立起這些數(shù)據(jù)項(xiàng)的關(guān)聯(lián)規(guī)則。 2022/2/15 《人工智能》 93 ③ 聚類 數(shù)據(jù)庫中的數(shù)據(jù)可分為一系列有意義的子集，或稱為類。這里強(qiáng)調(diào)時(shí)間序列的影響。偏差檢測的基本方法是尋找觀測結(jié)果與參照之間的差別。挖掘關(guān)聯(lián)規(guī)則的問題描述如下 : 令 I= {i1, i2, ?, im }是所有項(xiàng)目（數(shù)據(jù)項(xiàng)）集， D是全體事務(wù)的集合（數(shù)據(jù)庫），事務(wù) T 是 I 的一個(gè)子集 T ?I ，每個(gè)事務(wù)由唯一的標(biāo)志 TID標(biāo)識。即： %100),s up ( ),s up (%100}|{ }|{),( ????? ???? DX DYXTXT TYXTDYXc on f2022/2/15 《人工智。其意義是：一個(gè)事務(wù)中某些項(xiàng)的出現(xiàn) , 可推導(dǎo)出另一些項(xiàng)在同一事務(wù)中也出現(xiàn)。 2022/2/15 《人工智能》 95 關(guān)聯(lián)規(guī)則挖掘 關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)之間存在的潛在關(guān)系的規(guī)則 ，形式為 ： A1∧ A2∧ . . . ∧ Am = B1∧ B2∧ … ∧ Bn 其中 ， A i、 Bj是數(shù)據(jù)庫中 的數(shù)據(jù)項(xiàng) 。 2022/2/15 《人工智能》 94 ⑤ 偏差檢測 數(shù)據(jù)庫中的數(shù)據(jù)常有一些異常記錄，從數(shù)據(jù)庫中檢測出這些偏差很有意義。聚類增強(qiáng)了人們對客觀現(xiàn)實(shí)的認(rèn)識，即通過聚類建立宏觀概念。在大型數(shù)據(jù)庫中，這種關(guān)聯(lián)規(guī)則是很多的，一般用“支持度”和“可信度”兩個(gè)閾值來淘汰那些無用的關(guān)聯(lián)規(guī)則。嚴(yán)格地講，知識發(fā)現(xiàn)是從數(shù)據(jù)庫中發(fā)現(xiàn)知識的全部過程，而數(shù)據(jù)挖掘則是此全部過程的一個(gè)特定的、關(guān)鍵步驟。可視化數(shù)據(jù)分析技術(shù)拓寬了傳統(tǒng)的圖表功能，使用戶對數(shù)據(jù)的剖析更清楚。 (6) 遺傳算法。 (4) 貝葉斯信念網(wǎng)絡(luò)。 (2) 決策樹。與統(tǒng)計(jì)學(xué)有關(guān)的知識發(fā)現(xiàn)方法有： (1) 傳統(tǒng)方法 常見的統(tǒng)計(jì)方法有回歸分析、判別分析、聚類分析等。 知識評價(jià)。 數(shù)據(jù)降維和轉(zhuǎn)換 所謂降維指在考慮了數(shù)據(jù)的不變表示的情況下 , 減少變量的實(shí)際數(shù)目。 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ù) 挖掘 解釋 評價(jià) 2022/2/15 《人工智能》 87 數(shù)據(jù)選擇。 2022/2/15 《人工智能》 85 (5) 模式： 對于集合 F中的數(shù)據(jù)，可以用語言 L以表達(dá)式 E描述其中某些數(shù)據(jù)的特性。 (2) 新穎： 經(jīng)過知識發(fā)現(xiàn)提取出的模式 E必須是新穎的。 2022/2/15 《人工智能》 82 知識發(fā)現(xiàn)的發(fā)展和定義 知識發(fā)現(xiàn)最早是于 1989年 8月在第 11屆國際人工智能聯(lián)合會議的專題討論會上提出。 數(shù)據(jù)庫系統(tǒng)雖然提供了對數(shù)據(jù)的管理和分析處理，但無法從中尋找和發(fā)現(xiàn)某些規(guī)律和模式。 2022/2/15 《人工智能》 79 Q學(xué)習(xí)算法 Q 學(xué)習(xí)算法是由 Watkins 在 1989 年提出的一種無模型強(qiáng)化學(xué)習(xí)算法 。因此，我們考慮：能否在值函數(shù)更新中，不僅僅依賴當(dāng)前狀態(tài)的瞬時(shí)獎(jiǎng)賞值，也可以利用下一狀態(tài)的瞬時(shí)獎(jiǎng)賞值，一直到終結(jié)狀態(tài)？ 為此，構(gòu)造一個(gè)新的 λ返回函數(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)。 TD (0) 算法如式： ? ?)()()()( 11 ttttt sVsVrsVsV ???? ?? ?? 與 MC算法相比 ，上式中用回報(bào)的估計(jì)值 rt+1+?V(st+1)代替了實(shí)際回報(bào)值 Rt?？刂七^程采用貪心搜索策略。當(dāng)環(huán)境狀態(tài)為終止?fàn)顟B(tài)時(shí)，將得到積累回報(bào)賦予開始狀態(tài) s 的值函數(shù) V。 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í)算法等。因此在 π策略下，系統(tǒng)在 s狀態(tài)下的值函數(shù)由下式定義，其反映了如果系統(tǒng)遵循 π策略，所能獲得的期望的累計(jì)獎(jiǎng)賞折扣和。但由于在選擇行為策略過程中，要考慮到環(huán)境模型的不確定性和目標(biāo)的長遠(yuǎn)性，因此在策略和瞬時(shí)獎(jiǎng)賞之間構(gòu)造值函數(shù)（即狀態(tài)的效用函數(shù)），用于策略的選擇。 2022/2/15 《人工智能》 69 馬氏決策過程的本質(zhì)是：當(dāng)前狀態(tài)向下一狀態(tài)轉(zhuǎn)移的概率和獎(jiǎng)賞值只取決于當(dāng)前狀態(tài)和選擇的動作，而與歷史狀態(tài)和歷史動作無關(guān)。下面首先給出馬氏決策過程的形式化定義。 ???????022110iii rrrr ??? ?2022/2/15 《人工智能》 68 強(qiáng)化學(xué)習(xí)技術(shù)的 基本原理 是：如果系統(tǒng)某個(gè)動作導(dǎo)致環(huán)境正的獎(jiǎng)賞，那么系統(tǒng)以后產(chǎn)生這個(gè)動作的趨勢便會加強(qiáng)。 強(qiáng)化學(xué)習(xí)的結(jié)構(gòu) Agent 環(huán)境 狀態(tài) s 獎(jiǎng)賞 r 動作 a 2022/2/15 《人工智能》 67 強(qiáng)化學(xué)習(xí)模型由以下部分組成： 強(qiáng)化學(xué)習(xí)模型 ? 一個(gè)離散的狀態(tài)集 S ={ s0 , s1 , s2 , ?, sn }； ? 動作集 A={ a0 , a1 , a2 , ?, an} ； ? 一個(gè)強(qiáng)化值集 r ∈ R； ? agent 和環(huán)境交互的狀態(tài) — 動作序列 (si,ai) → ri，表示 agent 在狀態(tài) si 下執(zhí)行動作 ai 獲得的立即獎(jiǎng)賞值 ri。 2022/2/15 《人工智能》 66 強(qiáng)化學(xué)習(xí)的原理