動機
推論引擎應用事先提供的規則,學習系統則用例子調整表示方式或參數。這個區分有用,卻不是絕對分界:學到的決策樹可以成為規則系統,神經網絡也可為另一個推理程序提供特徵。兩者共同的限制是,預測只能使用表示方式保留下來的資訊。
例如訊息分類器只記錄某些字詞是否出現,便可學它們與類別的關聯,卻不能區分映到同一向量的兩句話。若語序改變意思,詞袋在最優化之前已丟掉必要資訊;再努力擬合也無法憑空重建。因此,表示方式與學習規則要一起分析。
本節從明確模型推導兩個基本更新,並分析決策樹的一個分割準則。保證範圍刻意清楚:感知器界需要正間隔,梯度是局部導數而不是全域最優化保證,訓練樣本熵減少也不是未來準確率保證。
定義
定義 3.1.1
(標記例子與線性分數)
二元標記例子為 ,其中特徵 ,標記 。線性分數為 。要含偏置,可把輸入擴為 ,並給最後一維獨立權重。下文範數與間隔條件都要套用於擴充後向量。零分數的預測慣例要說明;本節在 時視作錯誤或邊界違反而更新。
概念視角結構
特徵映射產生等價類
固定確定性特徵映射 ,任何形如 的預測器,都對相同特徵向量給相同輸出。因此 把輸入分成不可區分的類。如果任務要求同一類內兩項有不同標記,任何 都不能同時正確。這是表示方式的限制,與採哪個最優化器無關。例如 「dog bites person」 與 「person bites dog」 的字數向量相同,施事與受事卻互換,所以只看字數的預測器必須同樣對待它們。
詞數可對某些分類任務提供有用證據,同時丟掉句法。更完整的語言系統須指定斷詞、歧義、組合結構及評估任務,不能只因向量維度大便說已處理這些問題。
定義 3.1.2
(感知器更新)
感知器由 開始;遇違反例子便作 ,否則不變。該例子的帶號分數增加 ,因為 。但別的例子分數可能下降,故一次修正不表示錯誤總數單調減少。
定義 3.1.3
(平方損失、梯度步與單隱層網絡)
對可微模型 及實數目標 ,平方損失為 。梯度下降以指定步長 作 。單隱層、純量線性輸出的網絡寫成:
假設激活函數 在當前值可微。其他輸出激活及損失會給不同導數。Sigmoid 為 ,其導數為 。整流線性函數在零不可微,算法須另訂次梯度等處理約定,不能悄悄把普通導數公式用到不可微點。
定義 3.1.4
(熵、條件熵與資訊增益)
有限樣本中,均勻抽取一個訓練項目的類別記為 。若類別比例為 ,以 bit 為單位的經驗熵是:
約定 ,與連續延伸一致。屬性 把樣本分為值 的子組,比例為 。條件熵為 ,資訊增益為父熵減條件熵。決策樹可貪婪地挑最大增益,但仍需停止、同分及剪枝規則。
定理/命題
定理 3.1.5
(正間隔下的感知器錯誤界)
假設所有出現例子滿足 ,且存在同一單位向量 ,令每個例子皆有 。由零開始、在 時更新的感知器,不論呈現次序,至多更新 次。此界數更新次數,不數兩次錯誤之間可能出現的正確分類例子。
命題 3.1.6
(指定網絡的反向傳播)
對上述可微純量輸出網絡及 ,設 。在當前參數下,
若損失是批次平均,先平均各例子的導數,再同時更新參數。
兩個結果回答不同問題。第一個在強幾何假設下保證有限進展;第二個計算指定函數的準確局部敏感度,沒有聲稱損失曲面凸,也沒有聲稱反覆更新會到最佳參數。
命題 3.1.7
(資訊增益非負)
對一個非空標記樣本按屬性 分割,條件熵滿足 ,所以資訊增益 至少為零。
證明思路
證明
(對齊線性增長,範數只按平方根增長)
只按真正發生的更新編號, 表示更新 次後權重。每次與分隔向量的內積至少增加 ,所以 。另一方面,在需更新的例子上:
歸納得 。由 Cauchy–Schwarz 及 ,有 。若 ,除以 再平方即得界;零更新情況直接成立。有限可分樣本若循環呈現,最終必有一整輪沒有更新,否則無窮多個有錯輪次會違反有限更新界。
證明透視
兩個增長界缺一不可
共同分隔方向令對齊程度隨錯誤次數線性增長,只在非正帶號分數時更新則令範數至多以平方根速度增長。大量更新時兩者矛盾,因而終止。沒有共同正間隔,第一條界便消失;不是只在違反時更新,範數展開的交叉項便未必非正。所以不能把此證明原封不動套到任意梯度更新或互相矛盾的標記。
證明
(逐組參數的鏈式法則)
反向傳播先由 開始。輸出對 的導數為 、對 為一,立即得到輸出層導數。由 到輸出的路徑,鏈式法則依次乘 、、 及輸入 ;偏置的最後導數則為一。反向模式微分的意義,是重用共同的下游敏感度,避免每個參數都重算整條複合函數。
可微損失在非零梯度處滿足 (),所以充分小正步長會局部降低損失;這不保證任意固定步長安全,也不保證泛化。
證明
(熵函數的凹性)
在 凹,端點按連續延伸。父組類別比例向量是子組向量的加權平均,逐座標套凹性再相加,得 ,所以真正同一樣本分割的資訊增益非負。
此論證沒有說關聯在母體中穩定;獨特識別碼能令每個子組純粹,卻只是記住樣本。
數據不可分時,感知器的迴圈永遠完成不了一輪無錯誤的遍歷。
自然延伸的下一個問題
若不存在分離向量會怎樣?
數據不可分時,感知器的迴圈永遠完成不了一輪無錯誤的遍歷。
此上界假設存在間隔。若沒有任何 使每個帶號分數都滿足 ,迴圈便不會結束,因為一輪沒有更新的完整遍歷本身就給出這樣的 。例如 取兩次,標記分別為 和 , 會由 變成 ,再變回 ,如此重複。別的規則能否仍找到好的分類器是另一個問題,本定理並未回答。
例題詳解
例題 3.1.8
(含偏置感知器的追蹤)
擴充例子為 與 。零權重先被第一例觸發,成為 。第二例的分數為 ,帶號分數為 ,故不更新。原來一維輸入的邊界是 。取單位分隔向量 ,兩間隔為 ,所以可取 ,得至多五次更新。這是上界,不是聲稱實際要五次。
例題 3.1.9
(完整指定的一步神經更新)
輸入 ,一個 sigmoid 隱單元,參數 ,目標 ,步長 。有 ,激活導數為 。對 的梯度依次為 。同時更新得到 。新隱輸入為 ,輸出約 ,損失由 降至約 。重新前向計算可核對導數符號及意義。
例題 3.1.10
(資訊增益可能偏好記憶)
八項數據有四正四負,父熵為一 bit。屬性 A 產生兩個同樣大小子組,類別數為 及 ;各熵約為 ,所以增益約 。若用識別碼分成八個單項子組,增益達一 bit,卻未必能處理新識別碼,因為沒有相應分支。訓練增益要與表示方式、正則化及未見數據評估一起解讀。
常見錯誤
反例模式
線性特徵不能表示 XOR
令 為正類, 為負類。若仿射分數 能嚴格分隔,相加兩正例不等式給 ,相加兩負例卻給 ,矛盾。加入特徵 即可分隔,因它的符號正是標記。此處找不到線性分隔,不是感知器步長太小的證據。
常見錯誤
(在同一次梯度步中混用新舊參數)
一次梯度步的所有導數必須在同一組舊參數計算。若先改 ,再用新值計算 ,便定義了另一算法,結果也不再是所述損失的梯度步。在單一隱單元的例子中, 用的是舊的 ,而不是更新後的 。
常見錯誤
(把零資訊增益讀成無關)
對 XOR 表 ,單獨按 或 分割,每個子組都恰有每種標記各一行,所以兩個增益都是零;但兩個屬性合起來完全決定標記。零增益只表示這一次單獨分割沒有改變標記比例。
常見錯誤
(把學到的關聯當作規則、把分數當作概率)
專家系統也不只有推論引擎。知識獲取須找出領域規則、適用條件與例外;解釋須指出哪些規則被觸發;維護須處理衝突及過時知識。學到的關聯不自動是邏輯有效蘊涵。神經分數若沒有合適模型、目標及校準檢查,也不能直接當可靠概率。分類錯誤率、訓練損失及信心是不同量。
總結
學習結合表示方式、目標或更新規則,以及樣本假設。正間隔給感知器錯誤界;鏈式法則給神經梯度,卻不提供全域最優或泛化定理;資訊增益衡量樣本標記減少,可以獎勵記憶。更改最優化器之前,先檢查特徵能否分清任務要求區分的情況。
練習
練習 3.1.11
(由零開始,循環呈現 及 ,在帶號分數非正時以感知器規則更新。求首兩次更新、具正間隔的單位分隔向量,以及定理的更新界。)
核心
解答(3)
- 1
進行首兩次更新
在 時第一例的帶號分數為 ,所以 。第二例有 ,帶號分數為零,也更新:。再循環一輪,帶號分數為正(皆為 ),不再更新。
- 2
選取分隔向量並讀出間隔
關鍵一步
取 ,兩個帶號間隔都是 ,所以 ,且 。
依據: 定理需要一個固定單位向量,使每個帶號分數至少為 。
- 3
套用上界
。實際發生兩次更新,所以此順序及零分數約定恰達上界。
練習 3.1.12
(把上述神經例題的目標改為 ,重新計算梯度,給出步長 的同時更新,並解釋輸出偏置改變的方向。)
核心
解答(3)
- 1
重算前向值與誤差
前向值仍為 、、,但現在 。
- 2
以舊參數計算梯度
、、、。
依據: 所有導數都使用舊的 。
- 3
作同時更新
步長 給出 、、、。 為正,表示增大輸出偏置會局部增大損失;減去梯度便降低偏置,使輸出朝目標零移動。
練習 3.1.13
(某父樣本有六個正例、兩個負例;一個二元屬性把它分成類別數同為 的兩組。求資訊增益,並說明為何子組不純卻增益為零。)
基礎
解答(2)
- 1
計算各個熵
父組與兩個子組的正類比例都是 ,所以三個熵都等於 bit。
- 2
計算加權子熵與增益
兩個子組權重各為二分之一,加權子熵為 bit,與父熵相同,所以增益為零。分割可以重排記錄而不改變標記比例。零增益不表示標記本身確定,也不表示此屬性永遠不能與其他屬性聯合發揮作用。
練習 3.1.14
(證明確定性特徵映射的不可區分性,並應用到上述語序互換的兩個句子;再提出一個明確的新增特徵來區分兩者,但不要聲稱它解決一般語言理解。)
綜合證明
解答(3)
- 1
利用 是特徵向量的函數
設 為確定性特徵映射, 為任何函數,並假設 。
- 2
比較輸出
關鍵一步
對兩邊用同一函數 ,得 。若任務要求 與 有相反標記,預測器至少在其中一項出錯。
- 3
應用到句子並加入特徵
兩個句子的字數特徵相同,所以任何只依這些特徵的預測器都不能區分它們。特徵「是否出現有序相鄰詞 dog-bites」在指定斷詞下,於第一句為一、於第二句為零,因此能區分這一對。否定、改述、長距依賴及歧義文法仍是獨立問題;新增特徵沒有一般語義完備的保證。
依據: 兩個句子的字數向量相同。
∎