Thursday, April 26, 2018

Machine Learning Discussion(二):Kullback–Leibler divergence

Machine Learning Discussion(二):Kullback–Leibler divergence

2017/05/25

Kullback–Leibler divergence [1] 與 Jensen–Shannon divergence [2] 是 GAN 的基礎 [3], [4]。Wasserstein GAN 則是 GAN 在理論與實作的改良 [5]-[7]。到底 Wasserstein GAN 有多精彩,在 [8] 有詳細的中文說明。

關於 Kullback–Leibler divergence,我搜尋了網路上的資料 [9],並貼在 FB 的社團裡,引來一些精彩的討論 [11]。

-----

[11]

Wasserstein GAN,我想才是真正的 GAN。GAN 的概念不難,理論很難。Kullback–Leibler divergence 應該算是第一道門檻,先過再說吧(講給自己聽)! ----- 我們感興趣的是熵和交叉熵的差,我們把這個差異叫做KL散度(Kullback–Leibler divergence),所以 對 的KL散度定義為: 關於KL散度需要知道的是 ...

-----

討論一

David Tung: 離散版的KL-divergence, D(p||q) = \sum p log(p/q) KL-divergence 可以從消息理論的觀點了解,但首先你要知道 divergence 和 distance (metric) 不一樣

distance (metric) 有三個特性
1. self-reflexive: d(x,y) = 0, iff, x = y
2. symmetry: d(x,y) = d(y,x)
3. triangularity: d(x,z) <= d(x,y)+d(y,z)

D(p||q) 的 2, 3 特性都fail, 所以是 divergence. 你也許會問這樣 D(p||q) 有什麼用? 但是他卻是機率和消息理論很關鍵的運算。

D(p||q)>=0, 且只有p=q 時 D(p||q)=0,是它最重要的特性,這可以很簡單從Jensen's inequality證明。所以它是某種機率分佈間差異的指標。它和消息理論的相容性很好。 比如 cross-entropy, C(p, q) = -\sum p log(q) 也可以由 KL-divergence 了解:

C(p, q) = -\sum p log(q) = -\sum p log(p) + \sum p log(p/q)=H(p)+D(p||q), 其中 H(p) = -\sum p log(p) 是 p分佈的entropy. 這樣我們可以很簡單的解釋為什麼 C(p, q)是 cost function, 因為給定分佈 p, C(p, q)= H(p)+D(p||q)>=H(p), 且只有p=q時C(p, q)是最小值。

我們還可以了解更多, Deep learning 第六章說如果 cross-entropy用來學習分佈, 也就是 H(p) 是變動的, 我們要加 p 的regulation, 否則 training 會一直下降 H(p), 而不是讓 q 逼近 p。這在消息理論的關係式下很明顯。

Wasserstein distance 明顯符合 metric 特性 1,2 但是 3 可能不好證明(但既然被稱為distance, 3一定是成立的), 且和消息理論完全不相容。

郭宗賢:很精彩的推論, 麻煩也多描述一下 H(P) 

David Tung:離散H(p) >= 0 很明顯, 因為 pj <= 1,log pj <= 0. 但連續的H(p)可能小於0, 比如 uniform(0, 0.1), p 的值在(0,0.1)下等於10, log 10 > 0, 所以 H(p) < 0。 

郭宗賢:感謝, 這了解,。。不過, 主要是想請教 H(p) 的直觀意義... 

David Tung:喔,H(p) 的直觀意義的瞭解,就是用"最少可以用多少位元(bits)去表示這個機率分佈"為了理解這個觀念,先用離散分佈和以二為基底的log 去思考(不同基底的log所產生的entropy會產生一個不一樣的差異,但是同樣log之間的大部份(所有?) 關係不變。)

假設一個銅板,正反面各二分之一機率,H(p)=1, 也就是一位元去代表它,很明顯可以用1代表正面0代表反面(或相反)。就像entropy所預期的,一位元。沒有更有效率的表示方法。

一個100%單一事件的機率(已經是確定也可說非機率)H(p)=0。大家都知道的事,就沒有information了。

其他更複雜的分佈 entropy 也有同樣的意義。聽說過Huffman coding 嗎,Huffman coding 需要的位元數就是entropy(或為了避開無限問題比entropy大一些。)。

一開始消息理論的消息觀念和一般人理解的不太一樣(好像完全相反)所以直觀有時候就能走這麼遠,直正要理解消息理論還是要看一下標準教科書的數學推導。 順便提一下林宏毅教授的教學方式,林教授有很多訴諸直觀的解釋,這對第一次學習的人很好,很快捉住大綱,但是有時直覺就只能走這麼遠。沒有養成瞭解背後原理的習慣,有時候就只能到此止步,有空再說。

-----

討論二

郭宗賢:針對 GAN training 的問題, 除了W-GAN, 還有LS GAN (Least square GAN), 還有今年初Open-AI 的W-GAN Improved (W-GAN 需要 weight clipping, .) 

David Tung:我知道還有很多divergence,可能有也會有很多distance (現在或未來)。但是以WGAN 為例,improved WGAN只是variation, 要知道原理當然要去看前面的paper(甚至更早的研究). 我前面的引用是要強調該論文的範例1, 用一個很生動的角度去看幾種divergencec和W-distance的不同,了解這個不同,你自己也可以創造不同的divergence或distance. 

David Tung:我在adaptive filter的經驗,這種大量的generalizations, variations, fast algorithms, fast convergences, 大部分是沒有太大意義的, 時尚一過就不見了。最後真正有被使用的就是LMS algorithm 一個。即時一開始真的忽略一個重要改善,只要基礎清楚,這都是overnight 可以pickup 的。XDDD, 說的有點澎風。

-----

討論三:

David Tung:Wasserstein distance 似乎只有在這個學習完全一樣的分佈的問題,才有意義。

比如一個uniform分佈,旁邊有一個奇型怪狀的分佈,我們可以算出它和uniform分佈的W距離,假設為d。我們可以再找另一個同樣的uniform分佈,讓它的mean離開原uniform分佈的mean d 距離,這樣兩個uniform分佈的W距離也是d。

我們這時候説原uniform分佈和奇型分佈的"距離"和兩個uniform分佈的"距離"一様。很多時候這種一樣是沒有意義的。剛好兩個分佈要收斂成同一分佈,這才有意義。

-----

References

[1] Kullback–Leibler divergence - Wikipedia
https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence

[2] Jensen–Shannon divergence - Wikipedia
https://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence

[3] 2014_Generative adversarial nets

[4] 2016_NIPS 2016 Tutorial, Generative Adversarial Networks

[5] 2017_Towards principled methods for training generative adversarial networks

[6] 2017_Wasserstein GAN

[7] 2017_ Improved training of Wasserstein GANs

[8] 令人拍案叫绝的Wasserstein GAN - 知乎专栏
https://zhuanlan.zhihu.com/p/25071913

[9] 聊不來,聊的來 -初探資訊理論 « CK's Blog
http://kuanchen-blog.logdown.com/posts/333763

[10] Visual Information Theory -- colah's blog
http://colah.github.io/posts/2015-09-Visual-Information/

[11] https://www.facebook.com/groups/Taiwan.AI.Group/permalink/1837933429862423/

[12] KL Divergence - YouTube
https://www.youtube.com/watch?v=aSuuByj8T6Y&t=455s

[13] A Short Introduction to Entropy, Cross-Entropy and KL-Divergence - YouTube
https://www.youtube.com/watch?v=ErfnhcEV1O8&app=desktop

No comments: