信息測度和熵

08-16

信息測度和熵

來自專欄 Eureka機器學習讀書筆記12 人贊了文章

專欄文章匯總

文章結構如下：

0：信息量

1：熵的定義

2：聯合熵和條件熵

3：相對熵和互信息

4：交叉熵

5：微分熵

6：相對熵和互信息（連續）

0：信息量

信息是不是可以量化？

起碼直覺上而言是可以的，不然怎麼可能我們覺得有些人說的廢話特別多，「沒什麼信息量」，有些人一語中的，一句話就傳達了很大的信息量。

為什麼有的信息量大有的信息量小？

有些事情本來不是很確定，例如明天股票是漲還是跌。如果你告訴我明天NBA決賽開始了，這兩者似乎沒啥關係啊，所以你的信息對明天股票是漲是跌帶來的信息量很少。但是假如NBA決賽一開始，大家都不關注股票了沒人坐莊股票有99%的概率會跌，那你這句話信息量就很大，因為本來不確定的事情變得十分確定。而有些事情本來就很確定了，例如太陽從東邊升起，你再告訴我一百遍太陽從東邊升起，你的話還是絲毫沒有信息量的，因為這事情不能更確定了。所以說信息量的大小跟事情不確定性的變化有關。

不確定性的變化跟什麼有關呢？

一，跟事情的可能結果的數量有關；二，跟概率有關。

先說一。例如我們討論太陽從哪升起。本來就只有一個結果，我們早就知道，那麼無論誰傳遞任何信息都是沒有信息量的。當可能結果數量比較大時，我們得到的新信息才有潛力擁有大信息量。

二，單看可能結果數量不夠，還要看初始的概率分布。例如一開始我就知道小明在電影院的有15*15個座位的A廳看電影。小明可以坐的位置有225個，可能結果數量算多了。可是假如我們一開始就知道小明坐在第一排的最左邊的可能是99%，坐其它位置的可能性微乎其微，那麼在大多數情況下，你再告訴我小明的什麼信息也沒有多大用，因為我們幾乎確定小明坐第一排的最左邊了。

怎麼衡量不確定性的變化的大小呢？怎麼定義呢？

這個問題不好回答，但是假設我們已經知道這個量已經存在了，不妨就叫做信息量，那麼你覺得信息量起碼該滿足些什麼特點呢？

一，起碼不是個負數吧，不然說句話還偷走信息呢~

二，起碼信息量和信息量之間可以相加吧！假如你告訴我的第一句話的信息量是3，在第一句話的基礎上又告訴我一句話，額外信息量是4，那麼兩句話信息量加起來應該等於7吧！難道還能是5是9？

三，剛剛已經提過，信息量跟概率有關係，但我們應該會覺得，信息量是連續依賴於概率的吧！就是說，某一個概率變化了0.0000001，那麼這個信息量不應該變化很大。

四，剛剛也提過，信息量大小跟可能結果數量有關。假如每一個可能的結果出現的概率一樣，那麼對於可能結果數量多的那個事件，新信息有更大的潛力具有更大的信息量，因為初始狀態下不確定性更大。

那有什麼函數能滿足上面四個條件呢？負的對數函數，也就是$-log(x)$！底數取大於1的數保證這個函數是非負的就行。前面再隨便乘個正常數也行。

a. 為什麼不是正的？因為假如是正的，由於$x$是小於等於1的數，$log(x)$就小於等於0了。第一個特點滿足。

b. 咱們再來驗證一下其他特點。三是最容易的。假如$x$是一個概率，那麼$log(x)$是連續依賴於$x$的。

c. 四呢？假如有$n$個可能結果，那麼出現任意一個的概率是$1/n$，而$-log(x)$是$n$的增函數，沒問題。

d。最後驗證二。由於$-log(xy) = -log(x) -log(y)$，所以也是對的。學數學的同學注意，這裡的$y$可以是給定$x$的條件概率，當然也可以獨立於$x$。

ok，所以我們知道一個事件的信息量就是這個事件發生的概率的負對數。

最後終於能回到信息熵。信息熵是跟所有可能性有關係的。每個可能事件的發生都有個概率。信息熵就是平均而言發生一個事件我們得到的信息量大小。所以數學上，信息熵其實是信息量的期望。

再說一次：信息量度量的是一個具體事件發生了所帶來的信息，而熵則是在結果出來之前對可能產生的信息量的期望——考慮該隨機變數的所有可能取值，即所有可能發生事件所帶來的信息量的期望。

上文轉自：信息熵是什麼？

1：熵的定義

假設離散隨機變數 $X$ ，它的p.m.f是 $p(x)=Pr(X=x)$ 。我們定義 $X$ 的熵 $H(X)$ 是：

$H(X)=-sum_{xin mathcal{X}}p(x)log~p(x),quad 其中：0log0=0$

引理： $H(x)geqslant0$

證明 $0le H(X)le log,n$ ，即均勻分布熵最大。

利用拉格朗日乘子法證明：

$H(X)=?left(p(1)log,p(1)+p(2)log,p(2)+?+p(n)log,p(n) ight)$

$s.t,,p(1)+p(2)+?+p(n)=1$

由拉格朗日計算可以可到： $p(1)=p(2)=?=p(n)=1/n$ ， $H(X)$ 得到極值為 $log,n$ 。

2：聯合熵和條件熵

定義（聯合熵）： $H(X,Y)=-sum_{xin mathcal{X}}sum_{yin mathcal{Y}}p(x,y)log,p(x,y)=-E(log~p(x,y))$

定義（條件熵）：假如 $(X,Y)sim p(x,y)$ ，則條件熵是：

$H(Y|X)=sum_{xin mathcal{X}}p(x)H(Y|X=x)=-sum_{xin mathcal{X}}p(x)sum_{yin mathcal{Y}}p(y|x)log,p(y|x)=-sum_{xin mathcal{X}}sum_{yin mathcal{Y}}p(x,y)log,(y|x)$

定理（鏈式規則）： $H(X,Y)=H(X)+H(Y|X)$

證明：

$egin{align*}H(X,Y)&=-sum_{x,y}p(x,y)log,p(x,y) \&=-sum_{x,y}p(x,y)log,(p(y|x)p(x)) \&=-sum_{x,y}p(x,y)log,p(y|x)-sum_{x,y}p(x,y)log,p(x) \&=H(Y|X)-sum_{x}log,p(x)sum_{y}p(x,y) \&=H(Y|X)-sum_{x}log,p(x)p(x) \&=H(Y|X)+H(X) end{align*}$

推廣： $H(X,Y|Z)=H(X|Z)+H(Y|X,Z)$

注意：熵只依賴於隨機變數的分布，與隨機變數取值無關。

3：相對熵和互信息

定義（相對熵或Kullback–Leibler(KL) divergence）：KL散度是兩個隨機變數的概率質量函數 $p(x)$ 和 $q(x)$ 的距離，公式如下：

$D(pparallel q)=sum_{x in mathcal{X}} p(x)logfrac{p(x)}{q(x)}=E_{p}(logfrac{p(x)}{q(x)})$

其中： $0logfrac{0}{q(x)}=0,0logfrac{0}{0}=0,p(x)logfrac{p(x)}{0}=infty$ ，且 $D(pparallel q) eq D(qparallel p)$

定義（互信息）：假設隨即變數 $X$ 和 $Y$ 的p.m.f是 $p(x,y)$ ，邊際p.m.f分別是 $p(x)$ 和 $p(y)$ 。則互信息 $I(X,Y)$ 是：

$I(X,Y)=sum_{xin mathcal{X}}sum_{yin mathcal{Y}}p(x,y)logfrac{p(x,y)}{p(x)p(y)}=D(p(x,y)parallel p(x)p(y)$

定理（互信息和熵的關係）：

$egin{align*}I(X,Y)&=I(Y,X) \I(X,X)&=H(X) \I(X,Y)&=H(X)-H(X|Y)=H(Y)-H(Y|X) \I(X,Y)&=H(X)+H(Y)-H(X,Y)end{align*}$

因此互信息就是在了解了其中一個 $Y$ 的前提下，對消除另一個 $X$ 不確定性所提供的信息量，也可稱為信息增益。

上面一堆概念，估計比較暈，用下面這個圖很容易明白他們的關係。左邊的橢圓代表 $H(X),$ 右邊的橢圓代表 $H(Y),$ 中間重合的部分就是我們的互信息或者信息增益 $I(X,Y),$ 左邊的橢圓去掉重合部分就是 $H(X|Y),$ 右邊的橢圓去掉重合部分就是 $H(Y|X)。$ 兩個橢圓的並就是 $H(X,Y)。$

定義（條件互信息）：在給定 $Z$ 後，隨機變數 $X$ 和 $Y$ 的互信息是：

$I(X,Y|Z)=H(X|Z)-H(X|Y,Z)$

定義（條件相對熵）： $Dleft(p(y|x)parallel q(y|x) ight)=sum_{xin mathcal{X}}sum_{yin mathcal{Y}}p(y|x)logfrac{p(y|x)}{q(y|x)}$

定理： $p(x),q(x),xin mathcal{X}$ 是兩個p.m.f，則 $D(pparallel q)geqslant 0$ 當且僅當 $p(x)=q(x)$ 時，等號成立。

推論：對於任意的 $X,Y$ ， $I(X,Y)geqslant 0$ ，當且僅當 $X$ 和 $Y$ 獨立時等號成立。

引理：一組非負序列 $sum a_{i}$ 和 $sum b_{i}$ 是收斂的：

1. $sum a_{i}logfrac{b_{i}}{a_{i}}+sum(a_{i}-b_{i})leqslant 0$ 或者 $sum a_{i}logfrac{a_{i}}{b_{i}}+sum(b_{i}-a_{i})geqslant 0$ （兩組正的序列KL距離定義）

2. 如果 $sum a_{i}geqslant sum b_{i}$ ，則 $sum a_{i}logfrac{b_{i}}{a_{i}}leqslant 0$ ，當且僅當 $a_{i}=b_{i}$ 時，等號成立。

3. 如果 $a_{i}leqslant 1$ 且 $b_{i}leqslant 1$ 對所有的 $i$ 都成立，則 $2sum a_{i}logfrac{a_{i}}{b_{i}}geqslant sum a_{i}(a_{i}-b_{i})^{2}$

引理：令非負序列 $sum a_{i}$ 和 $sum b_{i}$ 是收斂的。則 $sum a_{i}logfrac{a_{i}}{b_{i}}geqslant (sum a_{i})logfrac{sum a_{i}}{sum {b_{i}}}$ ，當且僅當 $frac{a_{i}}{b_{i}}=constant$ 時等號成立。

引理： $H(X)leqslant logleft |mathcal{X} ight |$ ，其中 $left |mathcal{X} ight |$ 表示集合 $X$ 元素的個數，當且僅當 $X$ 有均勻分布時等號成立。【均勻分布時熵最大，即不確定性最大】

引理（Condition reduces entropy）： $H(X|Y)leqslant H(X)$ ，當且僅當 $Xperp Y$ （獨立）時等號成立。：交叉熵

由KL散度可以得到： $D(pparallel q)=sum_{x in mathcal{X}} p(x)logfrac{p(x)}{q(x)}=-sum_{x in mathcal{X}} p(x)log,q(x)+sum_{x in mathcal{X}} p(x)log,p(x)$ 。而KL散度的前半部分 $-sum_{x in mathcal{X}} p(x)log,q(x)$ 就是交叉熵。

若 $p(x)$ 是數據的真實概率分布， $q(x)$ 是由數據計算得到的概率分布。機器學習的目的就是希望 $q(x)$ 儘可能地逼近甚至等於 $p(x)$ ，從而使得KL散度接近最小值0。由於真實的概率分布是固定的，KL散度公式的後半部分 $sum_{x in mathcal{X}} p(x)log,p(x)$ 就成了一個常數。那麼KL散度達到最小值的時候，也意味著交叉熵達到了最小值。對 $q(x)$ 的優化就等效於求交叉熵的最小值。

5：微分熵

定義： $X$ 是連續的， $H(X)=-int _{S}f_{X}(x)log,f_{X}(x)dx$ (存在)，其中 $S$ 是隨機變數的支撐。此時熵不一定是大於0。

定義（聯合熵）：一組隨機變數 $X_{1},X_{2},...,X_{n}$ 的 p.d.f 是 $f(x_{1},...,x_{n})$ ，則聯合熵是：

$H(x_{1},..,x_{n})=-int f(x_{1},...,x_{n})log~f(x_{1},...,x_{n})dx_{1}cdots dx_{n}$

定義（條件熵）：對於隨機變數 $X$ 和 $Y$ ，條件熵是：

$H(X|Y)=-int f(x,y)log~f(x|y)dxdy$

6：相對熵和互信息（連續）

定義（相對熵或Kullback–Leibler(KL) divergence）：兩個連續隨機變數 $f(x)$ 和 $g(x)$ ，KL散度為：

$D(fparallel g)=sum_{x in mathcal{X}} f(x)logfrac{f(x)}{g(x)}=E_{f}(logfrac{f(x)}{g(x)})$

注意：假如 $f$ 的支撐包含在 $g$ 的支撐上，則 $D(fparallel g)$ 是有限的。

定義（互信息）：兩個隨機變數 $X$ 和 $Y$ p.d.f 是 $p(x,y)$ ，邊際 p.d.f 分別為 $p(x)$ 和 $p(y)$ 。則互信息 $I(X,Y)$ 是：

$egin{align*}I(X,Y)&=int p(x,y)logfrac{p(x,y)}{p(x)p(y)}dxdy \I(X,Y)&=H(X)-H(X|Y)=H(Y)-H(Y|X)=D(f(x,y)parallel f(x)f(y)) end{align*}$

定理： $D(fparallel g)geqslant 0$ ，當且僅當 $f$ 與 $g$ 幾乎處處相等時等號成立。

推論：

1. 對於任何 $X,Y$ ，有 $I(X,Y)geqslant 0$ ，當且僅當 $X$ 和 $Y$ 獨立時等號成立。

2. $H(X|Y)leqslant H(X)$ ，當且僅當 $X$ 和 $Y$ 獨立時等號成立。

定理（微分熵的鏈式規則）： $H(X_{1},X_{2},...,X_{n})=sum_{i=1}^{n}H(X_{i}|X_{1},...,X_{i-1})$

推論： $H(X_{1},...,X_{n})leqslant sum_{i=1}^{n}H(X_{i})$

定理： $H(alpha X + C)=H(X)+log,left |alpha ight |,, alpha eq 0quad Rightarrow quad A$ 是非奇異矩陣， $H(AX)=H(X)+log~left |det(A) ight |$

定理：假設 $Xin mathbb{R}^{n}$ 均值是0，方差是 $Sigma=E,XX$ ，則 $H(X)leqslant frac{1}{2}log~left((2pi)^{n}|Sigma| ight)+frac{n}{2}$ ，當且僅當 $Xsim N(0,Sigma)$ 時等號成立。（當一階矩和二階矩給定時，高斯分布的熵最大）