018 從實例中學習

Post date: 2013/3/18 上午 11:09:15

7 本章中我們將說明能夠從自身經歷中努力學習,從而改進自身行為的代理人

學習

學習的形式

任何代理人的元件均可藉由從資料學習來加以改進。藉以產生代理人元件的改進及技術,取決於四個主要因素:

● 哪個部分是要被改進的。

● 哪個事前知識是代理人已具備的。

● 用於資料及元件表示方法為何。

● 能獲得什麼樣的回饋(feedback)來加以學習。

要學習的元件

第 2 章描述了數種代理人設計。這些代理人的組成元件包括:

1. 一個從目前狀態的條件到行動的直接對應。

2. 一個從知覺序列中推斷世界的相關屬性的方法。

3. 世界發展方式,以及代理人可採取的可能行動而導致的結果之資訊。

4. 對世界狀態的期許度之效用(utility)資訊。

5. 做這些行動的期許度之行為-價值(action-value)資訊。

6. 目標(goal)是描述一群狀態的類別使得代理人能達到最大效用。

表示法與事前知識

因式表示法

歸納式學習(inductive learning)

分析式

演繹式學習

反饋學習

有三個類型的回饋決定了學習的三個主要類型:

無監督學習

代理人從輸入學習模式,即使沒有提供明確反饋。群集是最一般的無監督學習任務:偵測輸入例子中的潛在有用群集。

強化學習

代理人從一連串的強化─回報或懲罰─來學習。

受監督學習

代理人觀察一些輸入輸出對的例子,並學習由輸入對應到輸出的函數。

受監督的學習

受監督學習的任務是如此:

給定一個N例子輸出輸入對的訓練集合

(x1,y1),(x2,y2),...(xN,yN)

其中每個 yj 是由個未知函數 y=f(x) 所產生。

找出近似於真實函數 f 的函數h。

這裡 x 和 y 可以是任意值,他們不必為數字。函數 h 是一個假設。學習是在可能假設之空間中搜尋

會表現良好的一個假設,即使新的例子是不在訓練集合內。為了測量假設的精確度,我們給假設一

個對於例子的測試集,其異於訓練集。我們稱假設可良好推廣,指若他正確預測新例子中的y值。

分類

回歸(regression)

假設空間

一致

奧坎刺刀(Ockham's razor)

可實現的(realizable)

學習決策樹

決策樹歸納(Decision tree induction)

決策樹的表現

一個決策樹表示之函數是以輸入為屬性值向量,回傳一個「決策」─單一輸出值。輸入及

輸出的值可以是離散或連續。現在我們將關注的問題是,其輸入為離散值且輸出正好有兩個可能值;

這是布林分類,每個例子輸入都會被歸類為真(正例)或偽(反例)。

一個決策樹藉由執行一個測試序列得到他的決策。樹中的每個內部節點對應於輸入屬性之一 Ai

其值的測試,而每個從結點的分支被標記上屬性的可能值 Ai = vik。在樹的每個葉節點指定了由函數

所要被回傳的值。決策樹的表示方法看起來對人而言是很自然的;

舉個例子,我們將建立一個決策樹判斷是否要在餐館等座位。這裡的目的是學習對於目標謂詞 WillWait 的定義。

首先我們列出屬性,其將會被視為輸入的一部分:

1. Alternate(改變):附近是否有另一家合適的餐館。

2. Bar(酒吧):該餐館中供顧客等候的酒吧區是否舒適。

3. Fri/Sat(週五/週六):若是周五或週六,則為真。

4. Hungry(飢餓):我們是否飢餓。

5. Patrons(顧客):該餐館中有多少顧客[值為 None(沒人)、Some(一些) 或 Full(滿座)]。

6. Price(價格):餐館的價格範圍($,$$,$$$)。

7. Raining(下雨):外面是否再下雨。

8. Reservation(預約):我們是否預約過。

9. Type(類型):餐館的種類(法式、義大利式、泰式或漢堡店)。

10. WaitEstimate(估計等候時間):餐館主人估計的等候時間(0~10 分鐘,10~30,30~60,>60)。

注意每個變數有個可能值的小集合,例如WaitEstimate(估計等候時間)的值,不是一個整數,而是四

個離散值的其中之一,0~10、10~30、30~60、>60。我們中的一人,SR,斯圖爾特‧羅素,本書的第一作者針對這種情況

採取的決策樹如圖 18.2 所示。注意這棵樹忽略 Price 和 Type 這兩個屬性。

實力是從樹的根結點開始處理的,並沿著適當的分支到達業節點。例如,Patrons = Full 而且

WaitEstimate = 0~10 的實例會被分類為正例(即「是」,我們要等座位)。

圖18.2

決定是否要等座位的決策樹

決策樹的表達能力

布林決策樹邏輯地等同於推斷,其目標屬性為真若且為若輸入屬性,滿足於其中之一的路徑導向一個

帶有真實質的葉節點。江浙以命題邏輯寫出,我們得到

Goal <=> (Path1 v path2 v ...)

其中每個路徑(path)是需依照路徑的測試屬性值的連接。因此,整個表示是等價於選言標準型(習題 7.19 ),

其表示在命題邏輯中任何函數可被表示為一個決策樹。舉個例子,再圖 18.2 最右邊的路徑是

Path = (Patrons = Full ^ WaitEstimate = 0~10)

某些函數無法被簡潔地表示。例如,大多數函數,其回傳值若且為若多於一半以上的輸入為真,需要指數型大的決策樹。

從實例中歸納決策樹

一個包含一對(x,y)布林決策樹的例子,其中 x 是輸入屬性的向量值,且 y 是單一布林輸出值。

找出最小的一致樹是很難處理的問題,沒有辦法很有效率地搜尋超過2平方2^n的樹。利用某些簡單啟發式,

我們可以找出好的近似解:一個小的(並非最小)一致樹。DECISION-TREE-LEARNING 演算法採用貪婪各個擊破戰略:

總是先測試最重要屬性。

以下是對於這些地回問題要考慮的四種情況:

1. 如果所有剩餘的都是正例(或都是反例),那麼我們已經完成。我們可以回答Yes或No。

2. 如果存在一些正例和一些反例,那麼就要選擇能分割他們的最佳屬性。

3. 若沒有留下實例,它意味著對於屬性值的合併沒有實例可被觀察,並且我們退回由所有實例的

複數分類計算的預設值,其中用來建構節點的親代。這些是沿著變數 parent_examples。

4. 如果沒有留下任何屬性,而留下正及負實例兩者,這表示這些實例正好有相同敘述但不同分類。

這是會發生的,因為有錯誤或雜訊於資料中,因為域是非確定性的,或因為我們無法觀察實例

中可區分的屬性。我們可以做最好的是回傳剩餘實例的多元化分類。

圖18.4 透過屬性測試劃分實例。在每個節點處我們顯示出剩下的正(淺色方格)與負(深色方格)實例。

(a) 根據 Type 劃分並不能更好地區分正例和反例。(b) 根據 Patrons 屬性劃分則可以很好地分離正例和反例。

以 Patrons 分割後,Hungry 是第二個相當好的測試屬性

學習曲線

快樂圖(happy graphs)

圖 18.5 決策樹學習演算法。函數 IMPORTANCE敘述於 18.3.4節。函數 PLURALITY-VALUE 在實例集合

之中選擇最一般的輸出值,隨機地打破僵局

圖 18.6

從12 實例訓練歸納出的決策樹

選擇屬性測試

在決策樹學習中使用貪婪搜尋是為了近乎最小化最終樹的深度而設計的。挑選屬性就是提供實例的精確分類。

一個完整屬性將實例區分為集合,其中每個全為正或全為負,並且都將會是樹的葉節點。

Patrons 屬性並不完美,但還不錯。一個一點也沒用的屬性,諸如 Type ,使得分割後的實例集合仍具有和原始集合相同比例的正例和反例。

熵(Entropy)

資訊增益

歸納和過適配

過適配(overfitting)

對於決策樹,有個稱之為決策樹修剪(decision tree pruning)的技術來對抗過適配。修剪之所以

有用是因為消除了那些非明確相關之節點。若測試似乎不相干──在資料中指偵測到雜訊──

則我們排除測試並以葉節點將它做替換。重複這個流程,考量每個只有後裔之葉節點的測試,直到每個都被修剪或被接受。

利用統計的顯著性測試(significance test)來偵測一個節點是正在測試一個不相關屬性。

顯著性測驗從假設無淺在的模式(也就是所謂的虛無假設,null hpothesis)開始。然後分析實際的資料,計算它們

偏離無模式的程度。如果偏離程度從統計來看是不太可能存在的(通常意味著 5%的機率或更低),那麼這被認為是

在資料中存在顯著模式的好證據。這些機率是由隨機取樣中,期望見到的偏離量之標準分布計算而來的。

早期停止(early stopping)

生成然後修剪(generate-and-then-prune)

擴展決策樹的適用性

為了將決策樹歸納推廣到各種問題上,我們必須先討論一些待解的難題。

● 資料不完整:

在很多領域中,不見得我們能知道每個實例的所有屬性值。這些值可能沒有被記錄下來,或是獲取的代價太昂貴。

這邊就冒出兩個問題:其一,給定一個完整的決策樹,他該如何對缺少一個測試屬性的實例進行分類?

其二,當某些實例具有未知的屬性值時,該如何修改資訊增益公式?這些問題在習題18.11中可以找到。

● 多值屬性:

當某屬性有多個可能值時,資訊增益量不適合衡量屬性的有用與否。因為在極端情況下,屬性像是 ExactTime 對於

每個實例有不同的值,其中表示每個實例的子集都是獨一無二的分類,單元素的集合,然後選擇該屬性可得到最高的

資訊增益量。但首先選擇這個劃分是不可能產生最佳樹。一種解決方案是採用增益率(gain ratio)(習題18.10)。另一個

可能性是允許布林測試的形式 A = vk,也就是對一個屬性挑選可能值之一,留下在樹之中後續可能被測試的剩餘值。

● 連續的和整數值的輸入屬性:

諸如 Height 和 Weight 這樣具有連續的或整數值特性的屬性,是一個什麼值都有可能的無限集合。決策樹學習演算法

與其產生無限多的分支,不如有代表性地尋找資訊增益最高的點,即分割點(split point)。例如,給定樹中的某個節點,

其中在 Weight > 160 的測試結果獲得最多資訊。有效的方法可以尋找好的分割點:從排序屬性的值開始,且然後只考量

介於兩個在順序經過排序的實例之分割點,其中有不同的分類,直到持續追蹤所有正負實例於分割點每一邊。分割是在

真實世界中決策樹學習應用裡最昂貴的部分。

● 連續值的輸出屬性:

若嘗試預測出數字化輸出值,像是公寓的價格,那麼我們需要一棵回歸樹(regression tree)而不是分類樹。回歸樹在每個

葉節點都是線性函數,代表一些數子集的屬性,而不是一個單一值。例如,兩間寢室公寓的分支必定以平方米、寢室的

數量和鄰居平均收入的線性函數為結束。學習演算法必須選擇何時停止分割,並且透過屬性開始應用線性回歸。

評估與選擇最佳假設

我們希望最佳適配未來資料的假設。欲精確陳述,我們需要定義「未來資料」和「最佳」。

平穩性假設

堅持交叉驗證(holdout cross-validation)

k 次交叉驗證

逐一交叉驗證(leave-one-out cross-validation,LOOCV)

偷看

驗證集

模型選擇:複雜度 VS. 適配度

在圖 18.1 我們證明了較高階多項式可較適配訓練資料,但太過高階則會過適配,並且在資料驗證表現較差。

選擇多項式的階數是一個模型選擇問題的實例。你可想到的任務,尋找最佳的假設兩個任務:模型選擇定義

了假設空間並且最佳化找出在該空間中最佳假設。

包裝

由錯誤率到損耗

目前為止我們已嘗試將錯誤率最小化。這是明顯地比最大化錯誤率較佳,但她不是全貌。考慮

一個將電子郵件歸類為垃圾與非垃圾郵件的問題。比起將垃圾郵件歸類為非垃圾郵件(會引起短暫的怒火),

將非垃圾郵件歸類為垃圾郵件較糟糕(因此會有遺失重要訊息的潛在性)。

產生耗損

嘈雜

小規模學習

規則化

在18.4.1節,我們看到如何以模型大小的交叉驗證做模型選擇。一個另外的方法是搜尋假設,

其中直接最小化經驗損失與假設的複雜度的加權總和,我們將看到總成本:

Cost(h) = EmpLoss(h) + 齉打Complexity(h)

^h*= argmin H集合h Cost(h)

規則化(regularization)

特徵選擇

最小描述長度

學習的理論

學習中主要未回答的問題如下:如何可以確定我們的學習演算法已產生一假設,其將預測先前未見的輸入的正確值?

我們將會從學習是需要多少實例這個問題開始。

計算學習理論,其身處人工智慧、統計和理論計算機科學的交集。基礎原理是,任何嚴重錯誤的假設將幾乎必然在

很高機率下,於少量實例檢驗後被「抓出」,因為他將做出不正確的預測。於是,任何與足夠大的訓練實例集一致

的假設都不太可能有嚴重錯誤:也就是說,它必然是可能近似正確(probably approximately correct)。任何學習演算法

回傳假設,其中可能近似地正確被稱為 PAC 學習演算法,我們可以使用這方法來提供邊界於不同的學習演算法之效能。

錯誤率

近似正確(approximately correct)

樣本複雜度(sample complexity)

PAC 學習實例:決策表學習

圖 18.10

餐館問題的決策表

我們現在展示如何應用 PAC 學習於新的假設空間:決策表。它包含了一連串的測試,每個測試都是文字(literal)的連言。

如果某個實例描述的測試成功時,那麼決策表將指定回傳數值。如果測試失敗,則繼續進行表中下一個測試。決策表

與決策樹相仿,但是決策表的整體結構比較簡單。他們只在一個方向分歧。相反,單一項目的測試就比較複雜。

圖 18.10 為決策表如何表示下述的假設:

WillWait <=> (Patrons = Some) v (Patrons = Full ^ Fri / Sat)

線性模型的回歸與分類

線性函數

單變量線性回歸

權重

線性回歸

梯度下降

步級大小(step size)

學習率(learning rate)

批次梯度下降

隨機梯度下降(Stochastic gradient descent)

多變量線性回歸

我們可以容易地延伸到多變量線性回歸問題,其中每個實例 xj 是 n 元素向量。

資料矩陣

利用單變量線性回歸下,我們不需要擔心過適配。但利用高維度空間中的多變量線性回歸時,

有可能會這樣,就是實際無關的某一維度會意外地似乎是有用,而導致過適配。

稀疏模型

硬臨界的線性分類器

線性函數可能是用做分類以及回歸。

決策邊界

線性分離器

線性可分

臨界函數

感知器學習法則

訓練曲線

邏輯回歸的線性分類

我們已經看到線性函數的輸出透過臨界函數建立線性分類器,但硬性的臨界導致一些問題:假設

hw(x)非可微分的且事實上他的輸入和權重是不連續函數,這將導致以感知器法則學習是不可預知的冒險。

邏輯回歸

連鎖率

人工類神經網路

神經元

類神經網路

連接主義

並列分佈處理

神經計算

計算神經學

類神經網路結構

類神經網路是由節點或稱單元構成的,他們透過有向連結連接再一起。從單元

j 到單元 i 的連結作用是把激勵 aj 從 j 傳播到 i 。每條連結還有一個數值的權值 wi,j 與之相關聯,

他決定了連接的強度和符號。

感知器

S型感知器

前饋網路

迴圈網路

隱藏單元

單層前饋類神經網路(感知器)

如果網路的所有輸入直接連接到輸出,就稱為單層類神經網路,或稱感知器網路。

感知器學習法則

邏輯回歸

多數函數

多層前饋類神經網路

(McCulloch 和 Pitts,1943) 深知單一臨界單元不會解決他們所有的問題。

非線性回歸

在多層網路學習

首先讓我們省略一個由多層網路引起的輕微複雜:當網路具有多重輸出時,學習問題間的交互影響。

逆向傳播

逆向傳播過程可以歸納如下:

● 利用觀測到的誤差值,計算輸出單元的過程值。

● 從輸出層開始,對網路中的每一層重複下面的步驟,直到到達最早的隱層:

─ 向前面的層逆向傳播過程值。

─ 更新兩層之間的權值。

詳細的演算法如圖 18.24 所示

圖18.24 多層網路中的逆向傳播學習演算法

類神經網路學習效果很好,雖然不如決策樹學習那麼快。一開始的資料就是從一顆簡單決策樹產生的。

對類神經網路結構進行學習

過擬合

窺視

交叉驗證

最佳腦損傷

涵蓋

無參數模型

線性回歸和類神經網路使用訓練資料來估計參數 w 形成的一固定集合。

參數化模型

無參數模型是一個無法以參數的有界集合為特徵。

例如,若每個假設以他們本身所有的訓練實例產生簡單的保留,並且使用他們所有的來預測下一個實例。

基於實例的學習

基於記憶的學習最簡單的方法是查表

最近鄰模型

我們可用些微的變化來改進查表:給定一個查詢 xq,從 k 實例找出最接近 xq的。這稱為 k 最近鄰查詢。

明考斯基距離(Minkowski distance)

尤拉距離(Euclidean distance)

曼哈頓距離(Manhattan distance)

漢明距離(Hamming distance)

歸一化

馬氏距離(Mahalanobis distance)

維度的詛咒(the curse of dimensionality)

以 k-d 樹找出最近鄰

對於資料具有任意維度的平衡二元樹若為 k 維樹時,稱為 k-d 樹。

局部性敏感雜湊

雜湊表具有比二元樹提供較快搜尋的潛力。但我們能如何地用雜湊表找出最近鄰,當雜湊碼依賴

於精確比對?雜湊碼隨機地分佈值於箱子之間,但我們要將接近點組合在同一個箱子裡,我們需要

局部性敏感雜湊(locality-sensitive hash,LSH)。

在大的真實世界問題,像是從 1300 萬筆網路映像的資料集合使用 512 個維度找出近鄰(Torralba 等人,2008),

區域性敏感雜湊需要從 1300 萬之中僅驗證數千筆映像來找出最近鄰,透過窮舉或 k-d 樹方法達到千倍加速。

無參數回歸

現在我們來看無參數方法來回歸而不是分類。

k 最近鄰回歸(圖18.28(b))加強連點。

局部權重回歸(圖18.28(d))給出最近鄰的優點

核心

支持向量機

http://sls.weco.net/blog/hornacik/01-jan-2009/12026

支持向量機或SVM架構是目前「現成」受監督學習中最流行的方法:若你不具備任何關於這領域

事前專門知識,則SVM是個首先嘗試最佳方法。讓SVM有吸引力的3個特徵:

1. SVM 建構最大邊界分離器──與實例點具有最大可能距離的決策邊界。這讓他們良好地推廣。

2. SVM 建立一個線性分格超平面,但他們有能力嵌入資料於較高維度空間,利用所謂的核心技巧。

通常資料在原始輸入空間並非線性地可分,在較高維度空間輕易地可分。高維度限性分離器

在原始空間實際上是非線性的。 這意味假設空間是透過使用嚴格線性表示方法被大大地擴展。

3. SVM 是個無參數化方法──他們保留訓練實例和能夠需要儲存他們全部。在另一方面,實際上

他們通常僅有實例數目的一小部分而結束訓練──有時儘可能小到維度的數目的常數倍。 因此

SVM 合併無參數和參數模型的優點:它們具有表示複雜函數的彈性,但他們抵抗過適配。

最大邊界分離器

邊界

二次規劃

支持向量

核心函數

Mercer定理

多項式核心

核心技巧

軟邊界

核心化

集體學習

目前我們已經看過了從假設空間得到單一假設作為預測的學習方式。而集體學習(ensemble learning)

的想法是從假設空間中選出一整個假設集合,或稱為集體(ensemble),並把他們的預測組合再一起。

例如,交叉驗證之中我們可能產生20個不同決策樹,並且讓他們投票表決一個新實例的最佳分類。

增進演算法(boosting)

加權訓練集(weighted training set)

弱學習演算法(weak learning algorithm)

決策樁(decision stump)

貝氏學習(Bayesian learning)

線上學習

目前為止,本章我們所完成的每件事是依賴於假設資料是獨立且相同分佈(i.i.d.)。另一方面,有個合理的假設:

如果將來承擔沒有相似的過去,則要如何預測任何事?在另一方面,這是一個太強的假設:稀有的是輸入已所有捕捉資訊,

其中令未來真實地獨立於過去。

隨機化權重多數演算法:

1. 初始化權重的集合{w1,...,wk}全部為1。

2. 從專家接收到預測{y1,...,yk}。

3. 隨機地選擇專家 k*,以他的權重比例: P(k) = wk / (加總 k'Wk')

4. 預測yk*。

5. 接收正確的解答 y。

6. 對於每位專家 k 其中 yk /= y,更新 wk<-Bwk。

在此B是一個數字, 0 <B <1 ,告訴專家對於每個錯誤有多少的處罰。

不後悔學習(因為隨著試驗的次數增加,關於每次試驗的平均趨近於0)。

實際的機器學習

案例分析:手寫數字辨識

識別手寫體數字是許多應用中的一個重要問題,這些應用包括根據郵遞區號進行的郵件自動分揀、

帳單和納稅申報單的自動讀取以及掌上型電腦的資料登錄等。這個領域取得了飛速的進展,部分

是由於更好的學習演算法,部分是由於更優良的訓練集。美國國家科學技術學會(NIST)建立了一個包含

60,000 個經過標註的數字的資料庫,每個數字的影像大小為 20 * 20 = 400 個像素,每個像素使用 8 bit 灰度值。

3最近鄰分離器

單隱層類神經網路

專用類神經網路

改進型類神經網路

支持向量機

虛擬支持向量機

形狀匹配

人類

案例分析:詞意和房價

在教科書中我們需要處理簡單、玩具資料來得到概念跨越:一個小的資料集,通常是 2 維。但是

在實際機器學習的應用,資料通常是龐大、多維度且混亂的。

圖18.37表示個典型真實世界實例,比較於詞義分類的任務的 5 個學習演算法(給出個句子像是「The bank folded」,

將「bank」自分類為「money-bank」或「river-bank」

總結

本章所關心的內容是從實例中歸納出確定性的學習函數。要點如下:

● 學習有許多種形式,在於執行元件的本質、那些元件有待改進、以及可用的回饋。

● 若存在的回饋提供了正確的解答給實例輸入,則學習問題被稱作為受監督學習。這任務是學習

函數 y = h(x)。學習離散值函數被稱為分類;而學習連續函數則被稱為回歸

● 歸納學習包含找尋一個與實例相符的假設。奧坎剃刀原則建議選擇最簡單的一致假設。這件任

務的難度取決於所選的表示方法。

決策樹能夠表示所有布林函數。資訊增益啟發式提供一個有效方法來找到一棵簡單的、一致的

決策樹。

● 可以用學習曲線來衡量學習演算法的效能,該曲線將以訓練集大小的函數表示測試集上的預測

準確度。

● 當有多個模型可以選擇,交叉驗證可用來選擇較一般為佳的模型。

● 有時並非所有錯誤都相同。耗損函數告訴我們每個錯誤是如何,目標是在後來透過驗證集來最

小化耗損。

計算學習理論分析了歸納學習的樣本複雜度和計算複雜度。而在假設語言的表示能力與學習的

難易程度之間必須取得折衷。

線性回歸是被廣泛使用的模型。線性回歸的最佳參數可由梯度下降搜尋或透過精確計算來找到。

● 線性分類帶有硬臨界──也稱為感知器──可藉由簡單權重更新法則來符合線性可分資料。

在其他情況,該法則不會收斂。

邏輯回歸以邏輯函數所定義的軟臨界取代了感知器的硬臨界。梯度下降即使在線性地可分雜訊

資料下運作良好。

類神經網路以線性臨界單元的網路表示個複雜的非線性函數。給定足夠單元 termMultilayer 前饋

類神經可表示任何函數。逆向傳播演算法實作了一個在參數空間上最小化輸出誤差的梯度下降方法。

無參數模型使用所有資料執行每個預測,而非試著以少量參數先加總所有資料。實力包含最近鄰

局部權重回歸

支持向量機最大邊界找出線性分離器來加強分類器的一般效能。核心方法意暗示轉移輸入資料

為高維度空間,其中可能存在線性可分,即使原始資料是非線性可分。

● 例如增進演算法之類的集體學習方法之效能往往比單一學習方法要高。於線上學習我們可統合

專家的意見來趨近最好的專家表現,即使當分佈資料是不斷變化。