機器之心轉載
來源： 北京大學前沿計算研究中心
作者：許逸倫
本文是第八屆國際表徵學習會議 (ICLR 2020) 入選口頭展示論文 (oral)《基於計算約束下的有用信息的信息論 (A Theory of Usable Information Under Computational Constraint）》的解讀。該論文由北京大學 2016 級圖靈班本科生許逸倫，斯坦福博士生 Shengjia Zhao, Jiaming Song, Russell Stewart，和斯坦福大學助理教授 Stefano Ermon 合作完成。在審稿階段中，該論文獲「滿分」接收。
- Arxiv Link: https://arxiv.org/abs/2002.10689
- Openreview Link: https://openreview.net/forum?id=r1eBeyHFDH
背景
香農互信息（Mutual Information）是一套影響深遠的理論，並且在機器學習中的表示學習（Representation Learning）、信息最大化（Informax）、對比預測性編碼（Contrastive Predictive Coding）與特徵性選擇；和結構學習（Structure Learning）中的貝葉斯網絡的構建，均有廣泛應用。但香農信息論沒有考慮很重要的計算約束方面的問題，並假設了我們有無窮的計算能力。為了突出這個問題，我們考慮以下這個密碼學中的例子。
在我們的例子中，有一個帶標註的明文數據集，同時有一個相對應的 RSA 加密後的秘文數據集。如果 RSA 的公鑰已知，那麼由於 RSA 是雙射的，根據互信息在雙射下的不變性，明文與秘文應該與其標註有著相同的互信息，如下圖所示：
為了更直觀地理解其中的不合理性，我們用相應的圖片分別表示明文和秘文，如下圖所示，加密後的圖片看起來就像隨機採樣產生的噪聲圖片。
但是對於人類（或機器學習算法）來說，根據明文去預測標註顯然比根據秘文去預測更容易。因此我們認為，在人類看來，明文與標註有著更大的互信息，但這與香農互信息矛盾。這個矛盾背後的原因正是因為香農互信息假設了觀測者有無窮的計算能力，從而忽視了什麼是對於觀測者來說的有用信息。
另一個例子是，由香農互信息的數據處理不等式（data processing inequality）我們知道，神經網絡的深層表示（CNN feature）與標註的互信息應少於原始輸入與標註的互信息。但是在簡單的分類器看來，深層表示與標註的互信息更大。
因此，香農互信息對無窮計算能力的假設與對基於觀測者的有用信息的忽視帶來了許多反直覺的例子。
除此之外，本文還證明了現有的對香農互信息的變分估計量（NWJ, MINE, CPC）或者有較大的方差，或者有較大的估計誤差，比如 NJW 估計量的誤差可以到互信息量的指數級別。
V-信息：一種新的信息論框架
基於以上提到的香農信息論的缺點，本文利用變分（variational）的思想提出了一種顯示地考慮計算約束的信息量，並稱之為 V(ariational)-information。
首先，我們定義一個大集合
這個集合包含所有把一個隨機變量 X 的具體取值映射到另一個隨機變量的取值域上的概率測度 P(Y)。
什麼是計算約束呢？首先見下面我們對條件 V-熵（conditional V-entropy）的定義（其中我們省去了不重要的預測族（predictive family）的定義，它本質上是加了些正則條件，感興趣的小夥伴可以看下原 paper）：
定義（條件 V-熵）：X, Y 是兩個取值在 X, Y 的隨機變量，V ⊆ Ω 是一個預測族，則條件 V-熵的定義為：
計算約束體現在觀測者被限制為 V ⊆ Ω，即取全集 Ω 的一個子集合 V。由於 V ⊆ Ω，因此定義中的 f[x] 是一個概率測度，f[x](y) 是該概率測度（如概率密度函數）在 y 處的取值。
直觀地來看，條件 V-熵是在觀測到額外信息 X 的情況下，僅利用函數族 V 中的函數，去預測 Y 可以取到的期望下最小的負對數似然（negative log-likelihood）。同理定義 V-熵，也就是沒有觀測到額外信息（用 ∅ 表示）的情況下，利用 V 中的函數去預測 Y 可以取到的期望下最小的負對數似然。
下面我們展示，通過取不同的函數族 V，許多對不確定性的度量（如方差、平均絕對離差、熵）是 V-熵的特例：
接著類似於香農互信息的定義，我們利用 V-熵來定義 V-信息：
定義（V-信息）：X, Y 是兩個取值在 X, Y 的隨機變量，V ⊆ Ω 是一個預測族，則 V-信息的定義為：
即從 X 到 Y 的 V-信息是 Y 的 V-熵在有考慮額外信息 X 的情況下的減少量。我們也證明了決定係數、香農互信息均為 V-信息在取不同函數族 V 下的特例。我們還證明了 V-信息的一些性質，比如單調性（取更大的函數族 V，V-信息也隨之增大），非負性與獨立性（X, Y 獨立則 V-信息為 0）。
此外我們展示，通過顯示地考慮計算約束，在 V-信息的框架下，計算可以增加 V-信息，即增加對觀測者而言的有用信息：
同時，注意到 V-信息是非對稱的，它可以很自然地用到一些因果發現或者密碼學（如 one-way function）的場景中。
對 V-信息的估計
不同於香農互信息，在對函數族 V 的一些假設下，本文證明了 V-信息在有限樣本上的估計誤差是有 PAC 界的：
這個 PAC 界啟發我們將 V-信息用於一些使用香農互信息的結構學習的算法中。我們發現這些之前在有限樣本上沒有保證的算法，遷移到 V-信息下就有了保證。比如 Chow-Liu 算法就是一例：
本文通過實驗驗證了新的基於 V-信息的算法構建 Chow-Liu Tree 的效果，優於利用現存最好的互信息估計量的 Chow-Liu 算法。
更多的實驗
我們也將 V-信息用到了其他結構學習的任務中，如基因網絡重建（下左圖）和因果推斷（下右圖）。
注意到與一些非參數化的估計量（如 KSG, Partitioning 等）相比，我們的方法在低維基因網絡的重建中取得了更好的效果。同時我們的方法在因果推斷的實驗中正確地重建了時序序列。在確定性的時序軌跡（deterministic dynamics）下，香農互信息是無法重建時序序列的。
最後，我們將 V-信息應用到公平表示（fairness）上。若 V_A, V_B 是兩個不同的函數族，我們發現實現 V_A-信息最小化的公平表示不一定能泛化到 V_B-信息最小化。這一發現挑戰了許多現有文獻的結果。
總結
本文提出並探索了一種新的信息框架 V-信息。V-信息包含了許多現有的概念，並且有許多機器學習領域喜歡的性質，比如對信息處理不等式的違背與非對稱性。V-信息可以被有保證地估計好，且在結構學習中有著優異的表現。
