|
本文是「小孩都看得懂」系列的第八篇，本系列的特點(diǎn)是極少公式，沒有代碼，只有圖畫，只有故事。內(nèi)容不長(zhǎng)，碎片時(shí)間完全可以看完，但我背后付出的心血卻不少。喜歡就好！
本文被以下三份資料所啟發(fā)，純純的致敬！
這次還拿馬賽克隊(duì)的哈登來(lái)舉例 。 1 主題：物理概念的熵 熵（entropy）是物理中的一個(gè)概念。如下圖，水有三種狀態(tài)：固態(tài)、液態(tài)和氣態(tài)，分別以冰、水和水蒸氣的形式存在。 它們具有不同的熵值：
現(xiàn)在你大體有個(gè)感覺，越不穩(wěn)定的東西具有的熵值越大。 世界處處充滿不確定性，從不確定到確定肯定是得到了額外的信息。從計(jì)算機(jī)專業(yè)術(shù)語(yǔ)來(lái)講，比特（BIT, Binary Digit）是衡量信息的單位。 講到這里小孩可能聽不懂了，那么就先不嚴(yán)謹(jǐn)?shù)恼J(rèn)為，比特可用 0 或 1 代表，而 傳遞 1 比特信息 = 將不確定性減半 2 主題：等概率事件的信息量 從物理切換到體育，假設(shè)馬賽克隊(duì)的哈登每次進(jìn)攻，50% 機(jī)會(huì)投籃，50% 的機(jī)會(huì)灌籃，如下圖所示。 如果我預(yù)測(cè)他會(huì)投籃，或他會(huì)灌籃 => 我都把兩種情況減少到了一種情況， => 我將不確定性減半 => 我發(fā)出 1 比特的信息 計(jì)算公式 log2(2) = log2(1/50%) = 1 咦？信息（1 比特）和概率（50%）聯(lián)系起來(lái)了。 類比一下：
3 主題：不等概率事件的信息量 等概率發(fā)生的事件理解起來(lái)容易，那如果哈登每次進(jìn)攻，75% 機(jī)會(huì)投籃，25% 的機(jī)會(huì)灌籃呢？如下圖所示。 這時(shí)我們可以把它等價(jià)想象成有四個(gè)事件，3 個(gè)投籃事件和 1 個(gè)灌籃事件。 那么
如果平均來(lái)看， 75%×0.42 + 25%×2 = 0.81 我發(fā)出的信息量是 0.81 比特。 4 主題：熵 = 平均信息量 現(xiàn)在我們可以歸納一下，對(duì)于有 p 概率發(fā)生的事件，預(yù)測(cè)該事件發(fā)生等價(jià)于發(fā)出 log2(1/p) 比特信息，因?yàn)?nbsp;log2(1/x) = - log2(x)，我們可以將信息量寫成 信息量 = - log2(p) 考慮到所有事件，平均信息量的公式為（期望公式） 平均信息量 = -∑i pi×log2(pi) 平均信息量就是信息論中的熵！用符號(hào) H(p) 表示（粗體 p 代表 p1, p2, ..., pn），因此我們有 H(p) = -∑i pi×log2(pi) 5 主題：等概率事件編碼 某天我在客戶那邊做項(xiàng)目，看不了 NBA 直播，只能通過在美國(guó)的朋友小明發(fā)短信直播，他會(huì)告訴我哈登每次進(jìn)攻的手段：三分、上籃、灌籃、兩分。 但是小明用二進(jìn)制密碼和我交流，我收到的短信是下面這樣子的： 0 1 0 0 1 0 0 0 為了理解短信的真實(shí)含義，我需要一個(gè)解碼表，如下： 這樣，我就可以把小明傳的密碼分段，然后將每段密碼在解碼表中找到對(duì)應(yīng)的動(dòng)作，因此 01001000 就解碼成上籃三分灌籃三分。 假設(shè)哈登兩分、三分、上籃、灌籃這四個(gè)動(dòng)作是等概率發(fā)生，那面我們可以給編碼長(zhǎng)度（橫軸）和動(dòng)作頻率（縱軸）做一個(gè)可視化，如下圖。 圖中彩色面積之和就表示每次短信說(shuō)一個(gè)動(dòng)作所需要的密碼的期望長(zhǎng)度，顯然在這種情況下，期望長(zhǎng)度為 2 比特。 6 主題：不等概率事件編碼 如果哈登進(jìn)攻手段（兩分、三分、上籃、灌籃）不是等概率發(fā)生呢？我們知道哈登最喜歡投三分（1/2 時(shí)間），再就是上籃（1/4 時(shí)間），而投兩分（1/8 時(shí)間）和上籃（1/8 時(shí)間）比較少。 每個(gè)動(dòng)作我們還是用長(zhǎng)度為 2 的密碼編碼時(shí)，那么最后得到的期望長(zhǎng)度還是 2 比特，如下圖所示。 你要知道從小明美國(guó)從發(fā)短信很貴啊，按編碼長(zhǎng)度收錢的，他可以做的更好一點(diǎn)么（即編碼更短一些）？先看下圖。 現(xiàn)在每次短信的期望密碼長(zhǎng)度變成了 1.75 比特，好過 2 比特。 其實(shí)我們做法很簡(jiǎn)單，就
因此上面上籃三分灌籃三分的編碼為 10 0 111 100。 問題來(lái)了，當(dāng)解碼的時(shí)候，我怎么把這一串編碼拆分為對(duì)應(yīng)到每個(gè)動(dòng)作的一個(gè)個(gè)編碼呢？如果每個(gè)動(dòng)作的編碼長(zhǎng)度都一樣，我那還可以等分，但現(xiàn)在每個(gè)每個(gè)動(dòng)作的編碼長(zhǎng)度都不一樣。 別問，問就是下節(jié)告訴你（盡管不情愿）！ 7 主題：信息論 正式了解一下編碼：
每次只要加 1 比特，編碼種數(shù)就翻倍。如下圖。 如果每個(gè)編碼長(zhǎng)度相等，那么一串編碼就有唯一的解碼方式。比如 01101110 就可以解碼成 01-10-11-10，簡(jiǎn)單。 如果每個(gè)編碼長(zhǎng)度不相等，那么一串編碼可以用同解碼方法，比如 01101110 可以解碼成以下兩種（其實(shí)有很多種）
這樣不就亂套了，必須采取限制，有個(gè)規(guī)則叫 prefix codes，就是任何編碼都不能是其他編碼的前綴。舉例
從上圖可知
這就是代價(jià)，這需要權(quán)衡，當(dāng)你對(duì)一個(gè)動(dòng)作用了短編碼，你就需要對(duì)其他動(dòng)作用個(gè)長(zhǎng)編碼。 下圖就是一種編碼，而且是最優(yōu)編碼（這個(gè)就不證明了，需要用到拉格朗日算子，目測(cè)沒有小孩可以懂）。 這樣我們就給每一個(gè)進(jìn)攻動(dòng)作一個(gè)密碼：
用上面一串密碼來(lái)編碼不會(huì)有任何歧義了。 8 主題：復(fù)習(xí)一下熵 現(xiàn)在我們知道最優(yōu)編碼長(zhǎng)度就是熵（通常上面一節(jié)解釋，希望現(xiàn)在可以秒懂熵的公式）。 無(wú)論怎么修改編碼，如果一個(gè)隨機(jī)事件的概率定下來(lái)了，那么用于交流該事件用的平均編碼長(zhǎng)度不會(huì)低于基于該事件分布的熵。
實(shí)際上，如果這些可能性中，每件事發(fā)生的概率相對(duì)集中，那么所需要的平均編碼長(zhǎng)度就更短，而如果概率相對(duì)分散，那么需要的平均編碼長(zhǎng)度就更長(zhǎng)。均勻分布需要的平均編碼長(zhǎng)度最長(zhǎng)。 9 主題：交叉熵 小明通過研究哈登的歷史進(jìn)攻動(dòng)作發(fā)生頻率（三分 1/2，上籃 1/4，灌籃和兩分 1/8），做了一套編碼（定義為哈登編碼），每次傳遞一次信息只用 1.75 比特。 現(xiàn)在我又想讓小明告訴我威少的下一個(gè)進(jìn)攻動(dòng)作，還可以用哈登編碼來(lái)傳遞信息嗎？威少的歷史進(jìn)攻動(dòng)作發(fā)生頻率如下：
下圖對(duì)比一下哈登和威少的進(jìn)攻動(dòng)作頻率圖。 這樣，如果用哈登編碼來(lái)發(fā)送威少動(dòng)作分布的信息，得到信息平均編碼長(zhǎng)度就叫做交叉熵。 反過來(lái)，如果用威少編碼來(lái)發(fā)送哈登動(dòng)作分布的信息，得到信息平均編碼長(zhǎng)度就也叫做交叉熵。 正規(guī)定義：使用專門為另一個(gè)分布制作的密碼表來(lái)發(fā)送某個(gè)分布中事件的信息，此時(shí)信息的平均編碼長(zhǎng)度定義為交叉熵（cross-entropy）。 把哈登動(dòng)作分布稱為 p 分布，把威少動(dòng)作分布稱為 q 分布，那么 p 分布對(duì) q 分布的交叉熵公式如下 而 q 分布對(duì) p 分布的交叉熵公式如下（把 p 和 q 位置反過來(lái)） 熵和交叉熵的總結(jié)在下圖。 根據(jù)上面公式計(jì)算各種熵和交叉熵，得到
我們發(fā)現(xiàn)兩個(gè)規(guī)律：
Hq(p) ≠ Hp(q) 熵比交叉熵要小，那兩者之間的差距是什么？看下節(jié)。 10 主題：KL 散度 Kullback-Leibler 散度（KL 散度）是熵與交叉熵之間的差值。稱之為散度而不是距離是因?yàn)榫嚯x是對(duì)稱的，而散度可以是不對(duì)稱的。 回到我們的場(chǎng)景，把哈登動(dòng)作分布稱為 p 分布，把威少動(dòng)作分布稱為 q 分布，那么 p 分布對(duì) q 分布的 KL 散度定義為 而 q 分布對(duì) p 分布的 KL 散度定義為 上面 log2(q(x)/p(x)) 或 log2(p(x)/q(x)) 實(shí)際上是描述編碼每個(gè)進(jìn)攻動(dòng)作時(shí)兩種不同的編碼之間的長(zhǎng)度差異。 分布 p 和 q 差別越大，那么之間的 KL 散度 KLq(p) 和 KLp(q) 也就越大。 總結(jié) 最后看看湖人隊(duì)的麥基，他進(jìn)攻手段只有灌籃，如下圖所示。 我不需要做什么預(yù)測(cè)（不需要發(fā)出任何信息），因此麥基 100% 會(huì)灌籃，根據(jù)公式我們有 H(p) = - 0×log20 - 1×log21 = 0 我們知道 log21 = 0，而且需要定義 log20 = 0。 如果某件事本身越不確定，而當(dāng)你知道發(fā)生了什么時(shí)，你得到的信息也就越多。 交叉熵，即使用針對(duì)另一分布制作的密碼表對(duì)某個(gè)分布內(nèi)的事件進(jìn)行通訊時(shí)的長(zhǎng)度，其組成分為兩部分：
數(shù)學(xué)表達(dá)式如下： 交叉熵p(q) = 熵(q) + 散度p(q) 交叉熵q(p) = 熵(p) + 散度q(p) 最后提一下機(jī)器學(xué)習(xí)用的熵公式里面的對(duì)數(shù)都是以 e 為底，即 ln()，它和以 2 為底的對(duì)數(shù)只差一個(gè)大于零的常數(shù)項(xiàng)，我們有 ln(x) = log2(x) / log2e = c×log2(x) 因此在做極值問題時(shí)，不會(huì)對(duì)結(jié)果有什么影響。 |
|
|
來(lái)自： LibraryPKU > 《Math》
