資訊理論與機器學習有著怎樣的關係?

01-02

如題。

資訊理論與機器學習同為涉及計算機科學和應用數學等學科的分支領域，這兩門交叉學科在起源和應用上有很多相似之處。資訊理論的理論體系相對成熟一些。機器學習這些年比較受歡迎，理論和應用的擴充發展速度遠遠更快且看不到飽和的趨勢。兩個方向互有交叉，但主要還是機器學習中借用資訊理論的方法以此拓展理論研究和應用場景，比較典型的就是借鑒信息理論創造和改進學習演算法（主要是分類問題），甚至衍生出了一個新方向，信息理論學習，詳細介紹和研究近況可以看這裡：Information Theoretic Learning (ITL) research

以上結論，以下具體說明。

機器學習可以根據數學原理分為兩種，一種基於經驗公式（錯誤率、邊界、代價、風險、實用性、分類邊緣），還有一種則是基於信息理論。

資訊理論中的一些度量也可以作為學習演算法的度量。Watanabe也提出過「學習就是一個熵減的過程」，學習的過程也就是使信息的不確定度下降的過程。Bayesian理論也紮根於信息和優化的概念中。比起傳統的經驗公式為基礎的機器學習，以信息理論為基礎的機器學習也擁有無可比擬的優勢。當少數類的樣本數量接近0時，Bayesian分類器對少數類的分類趨向於完全的錯誤。而以互信息為學習準則的分類器則能夠保護少數類，並根據各類樣本數量比例自動平衡錯誤型和拒絕型。

有目標隨機變數 $T$ 和預測結果隨機變數 $Y$

這些度量中，互信息可以用來衡量相似性，而條件熵、交叉熵和相對熵可以用來度量相異性。如果一個變數 $T$ 在統計意義上提供真實值（也就是說 $[pleft( t ight) = left( {{p_1}, ldots ,{p_m}} ight)]$ 其中總體率 $[{p_i}(i = 1, ldots ,m)]$ 已知），那麼它的熵 $H(T)$ 就是學習的基線，也就是說出現這種情況 $[I(T,Y) = H(T;Y) = H(Y;T) = H(Y) = H(T)]$ 或這種情況 $[KL(T,Y) = KL(Y,T) = H(Y|T) = H(Y|T) = 0]$ 時我們就可以說，我們就說這種方法達到了基線 $H(T)$

對於這些量的關係如下：

我們記E,Rej,A,CR分別表示錯誤率，拒絕率，正確率和正確識別率。那麼有 $[CR + E + {mathop{ m Re} olimits} j = 1]$ 和 $[A = CR/(CR + E)]$ ，這時有如下關係

這裡的 $[left{ {{y_k}} ight} = left{ {{t_k}} ight}]$ 表示每個對應標籤樣本之間都相等。對於有限的數據集來說，這種形式用來表示分布和度量，用 $leftrightarrow$ 表示對於等價關係的雙向連接，用 $ightarrow$ 表示單向連接。

準確分類的必要條件是所有信息度量都達到了基線 $H(T)$
當所有信息度量都達到了基線 $H(T)$ ，也不能充分說明這是準確分類
單向連接的不同位置解釋了充分條件為什麼存在以及充分條件是什麼

當然當遇到其他問題的時候我們還可以擴展到其他信息度量，比如聚類、特徵選擇/提取等。當我們從相似度（或者也能轉變成相似度的相異度）著手來考慮機器學習/模式識別的過程的時候，有一個重要的定理用以描述它們的關係：一般來說，在經驗定義的相似度量和信息度量之間，不存在一對一的對應關係（這個結論由錯誤和熵的學習邊界的研究給出）。

所以，由信息度量的優化並不能保證獲得經驗方法完成的優化效果。

但是，也有不少研究者猜想，在機器學習中，所有學習目標的computational representation都是可以用熵函數的優化來描述或者解釋的。這個猜想給了我們很好的一個研究著力的方向。

上面的概述有點太宏大了，那麼最後看一個大白話的實例：

以互信息作為學習準則。例如以應用信息增益（歸一化的互信息）構造最簡結構決策樹就是其中一種應用。這種基於信息理論為學習準則的原理就是將無序（標籤、特徵）數據轉變為有序數據，以信息熵差值作為測量尺度來評價轉換效果。

現在的研究有關於怎樣設計目標函數，怎樣處理其中互信息、經驗熵的計算，互信息與分類器傳統性能指標的關係……

唔，坑開的有點大，還有具體實例也暫時沒想到怎麼表述，另外除了常用的幾個，應用較多的如Renyi entropy也沒提到，等有空了再來慢慢填坑吧，覺得我寫的不好的或者等不及的可以自己看看列出的參考文獻。

References

[1] Hu, Bao-Gang. "Information Theory and Its Relation to Machine Learning."Proceedings of the 2015 Chinese Intelligent Automation Conference. Springer Berlin Heidelberg, 2015.

[2] MacKay, David JC. Information theory, inference and learning algorithms. Cambridge university press, 2003.

[3] Principe, Jose C., Dongxin Xu, and John Fisher. "Information theoretic learning." Unsupervised adaptive filtering 1 (2000): 265-319.

David MacKay說「information theory and machine learning are the two sides of the same coin」。

想詳細了解information theory和machine learning關係的同學可以看一下David MacKay的《information theory，inference and learning algorithms》。

這本書挺不錯的，提供了另外一個看待機器學習的角度。說遠一點，其實機器學習和深度學習里的encoder decoder模型（autoencoder、機器翻譯里seq2seq、圖像分割里的fcn等等）就是一個通信系統，對應到通信系統里就是編碼、解碼。

感覺資訊理論是基石，通信原理、機器學習是建造在資訊理論上的房子（學通信專業的同學估計心有戚戚焉）。

機器學習從資訊理論中汲取了很多的營養，比如BP演算法最早是用來求編碼的，熵被用於很多演算法的cost方程。

機器學習可以用資訊理論理解和解釋，例如聚類其實就是信息壓縮，topic model都是信息編碼等等。這樣就可以用資訊理論的評價指標和公式體系了。

對搞機器學習的人來說，資訊理論是內功，可以大大提升對機器學習問題的理解。在處理具體問題時也會更深刻和準確。

決策樹中可以用熵來選擇特徵

請學習鍾義信先生的相關書籍，推薦信息科學原理。