Information Theory basics in Machine Learning（機器學習中的資訊理論必備基礎）

本篇notes介紹資訊理論的一些必備基本知識,資訊理論的知識在機器學習特徵篩選,距離度量學習演算法(ITML),還有知名的決策樹演算法抑或神經網路損失函數的構造中都發揮著非常重要的作用,在不久前kaggle比賽中選手甚至通過資訊理論的知識快速擬合線上label並且在短短時間中霸佔PB榜單的第一名的有趣的情況。

第一部分:前綴編碼和Huffman樹(由此引出資訊理論的知識)。

Huffman編碼是一種最優的前綴編碼，而構造Huffman編碼可以根據Huffman樹進行完成(具體的細節參考數據結構中Huffman樹部分).Huffman編碼傳達的一個重要建模思想是:不確定性越大(某事發生的概率越小),編碼的長度就越長;不確定性越小(某事發生的概率越大),那麼編碼的長度就越短.而這類比到我們做機器學習問題中,就是我們對預測的結果越確定,那麼我們損失函數值就越小;越不確定,我們的損失函數值就越大.所以轉換到機器學習問題對應的優化函數中就是：最小化不確定性.

不確定性的概念剛好與資訊理論中的entropy相對應,所以接下來的部分著重介紹entropy.

第二部分:資訊理論的基礎知識(離散情況,連續情況)

這一節介紹資訊理論的很多基本的定義,分成離散情況和連續情況介紹.

離散情況:包括熵,聯合熵,條件熵,互信息,相對熵(KL divergence);之後介紹關於這些基本定義的一些性質,包括 ①.KL 距離的非負性; ②互信息的非負性; ③互信息,條件熵,熵三者之間的關係圖.

連續情況:這一部分和離散情況下很類似,就是把離散情況下的累加形式換成了這邊的積分形式,介紹的流程還是類似的,先是介紹微分下的熵,聯合熵,條件熵以及KL距離的定義.在微分部分由三個非常重要的性質, ①. 對一個分布進行平移並不改變微分熵; ②對一個分布乘以一個正半定矩陣A,變換後的熵為原來的熵+ln|A|; ③. 對於獨立的隨機變數,聯合概率的熵為兩個獨立變數的熵的和.

當然一般在模式識別機器學習之類的課程中一旦擴展到連續的情況下就不得不介紹高斯部分的相關內容了,而此處一個最大的結論就是: 在所有擁有相同的均值和相同的協方差的分布中(同時要求熵存在),多元高斯分布擁有最大的熵.(在證明的過程中還涉及到了交叉熵的概念)

第三部分：資訊理論在機器學習模式識別領域的一些應用

上述提到的資訊理論的基本知識在機器學習模式識別這塊的應用包含:特徵選取(一些其他的關於特徵選取的經典介紹可以參考:https://zhuanlan.zhihu.com/p/27829646);決策樹的節點的split過程;最大熵模型;神經網路的交叉熵損失函數等等.

文章鏈接：https://cs.nju.edu.cn/wujx/paper/IT.pdf

ppt鏈接：https://pan.baidu.com/s/1mhIw7oc

推薦閱讀：