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