精品国产亚洲AV天,久久夜色欧美精品

machine_learning.jpg

上一次分享給出決策樹(shù)劃分幾種算法，如下。

信息增益
$Gain(D,C) = Ent(D) - Ent(D|C) = Ent(D) - \sum_{i=1}^n \frac{N(D_i)}{N} Ent(D_i)$
信息增益率
$Gain(D,C) = Ent(D) - Ent(D|C) = Ent(D) - \sum_{i=1}^n \frac{N(D_i)}{N} Ent(D_i)$

但是為什么這樣按特征對(duì)數(shù)據(jù)劃分就可以達(dá)到分類(lèi)或回歸的效果呢? 今天我們就嘗試來(lái)回答這個(gè)問(wèn)題。
我們對(duì)數(shù)據(jù)了解程度決定了我們是否可以對(duì)數(shù)據(jù)進(jìn)行分類(lèi)和預(yù)測(cè)。數(shù)據(jù)對(duì)于我們是一些信息，在決策樹(shù)我們是通過(guò)一些列方法讓我們更了解這些數(shù)據(jù)，也就是數(shù)據(jù)提供給我們更多信息。

所以我們通過(guò)對(duì)數(shù)據(jù)某個(gè)特征對(duì)數(shù)據(jù)進(jìn)行劃分來(lái)不斷了解數(shù)據(jù)，我們同過(guò)了解數(shù)據(jù)特征，更加了解數(shù)據(jù)。我們可以根據(jù)特征對(duì)數(shù)據(jù)進(jìn)行劃分，降低我們對(duì)數(shù)據(jù)不確定性。數(shù)據(jù)的不確定性是通過(guò)信息熵可以衡量。降低數(shù)據(jù)信息熵就等同于降低數(shù)據(jù)不確定性。那么我們將要盡快了解數(shù)據(jù)，就要找到可以讓信息熵下降最快的特征作為我們劃分?jǐn)?shù)據(jù)的依據(jù)。

今天我們會(huì)首先介紹信息熵，接下來(lái)介紹在給定條件(就是已知什么條件下）數(shù)據(jù)下的條件熵。衡量連個(gè)對(duì)同一個(gè)數(shù)據(jù)不同概率分布之間的距離(差異性)的交叉熵。這些都是為證明互信息的公式?；バ畔⒕褪切畔⒃鲆?，也就是我們今天主要分享的內(nèi)容。

entropy_venn.png

圖中很直觀表示了互信息 $I(X,Y)$ 和條件熵 $H(X|Y$ 以及聯(lián)合熵 $H(X,Y)$ 他們之間關(guān)系。

信息熵

熵概念最早是在物理熱力學(xué)中提出概念后來(lái)也被在統(tǒng)計(jì)學(xué)中使用，表示提出了信息熵的概念，用以度量信息的不確定性。以及信息熵關(guān)系。我們先說(shuō)介紹一下事件，什么是事件呢?例如太陽(yáng)從東方升起就是一個(gè)事件、老板告訴你升職了也是一個(gè)事件。這些事件發(fā)生都是有一定概率的，例如太陽(yáng)升起的概率是 100%，而老板告訴你升職卻是一個(gè)小概率事件。然后這些事件也是帶有一定信息量，如果你告訴朋友太陽(yáng)會(huì)從東方升起，朋友會(huì)感覺(jué)你無(wú)聊，沒(méi)話找話。因?yàn)檫@個(gè)這個(gè)事件對(duì)于他的信息量幾乎為 0。

然后用概率表示事件發(fā)生可能性，我們用熵來(lái)衡量信息量大小。通過(guò)上面例子我們已經(jīng)了解到信息熵越大則概率越小，概率為 1 時(shí)信息熵為 0。好現(xiàn)在我們先給出熵計(jì)算公式，然后再給出合理解釋為什么熵公式長(zhǎng)成這個(gè)樣子
$H(p) = -\sum_{i=1}^N p_i \log p_i$
計(jì)算均勻分布信息熵
$p_i = \frac{1}{N} \, i \in \{1,2,\dots,N\}$
$H(p) = - \sum_{i=1}^N \frac{1}{N} \log \frac{1}{N} = \log \frac{1}{N}$

條件熵

之前已經(jīng)學(xué)習(xí)過(guò)條件概率， $P(Y|X)$ 就是在 X 事件發(fā)生前提下，發(fā)生 Y 事件的概率。那么什么是條件熵呢?這里用 $H(Y|X)$ 來(lái)表示在 X 發(fā)生前提下，Y 的信息熵的值，
$\begin{aligned} H(Y|X) = H(Y,X) - H(X) \\ =- \sum_{x,y}p(x,y)\log p(x,y) - \left(- \sum_{x}p(x) \log p(x)\right) \\ =- \sum_{x,y}p(x,y)\log p(x,y) + \sum_{x}p(x) \log p(x) \\ = - \sum_{x,y}p(x,y)\log p(x,y) + \sum_x \left( \sum_y p(x,y) \log p(x) \right) \\ = - \sum_{x,y}p(x,y)\log p(x,y) - \left( - \sum_{x,y} p(x,y) \log p(x) \right)\\ = - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)}\\ = - \sum_{x,y} p(x,y) \log p(y|x) \end{aligned} \tag{1}$
通過(guò)推導(dǎo)我們得出 $H(Y|X) = -\sum_{x,y} p(x,y) \log p(y|x)$ ,這里我們可能會(huì)感覺(jué)有點(diǎn)不舒服就是，如果根據(jù)信息熵定義應(yīng)該是 $H(Y|X) = - \sum_{x,y} p(y|x) \log p(y|x)$

相對(duì)熵

相對(duì)熵，又稱互熵、交叉熵，鑒別信息，Kullback 熵或則 Kullback_Leible 散度。我們假設(shè)有 $p(x)$ 和 $q(x)$ 分別是 X 中取值的兩個(gè)概率分布，則 p 相對(duì)于 q 的相對(duì)熵為

$D(p||q) = \sum_x p(x) \log \frac{p(x)}{q(x)} = E_{p(x)} \log \frac{p(x)}{q(x)}$

在 p 概率分布上求 $\log \frac{p(x)}{q(x)}$ 的期望。那么相對(duì)熵也就是可以衡量?jī)蓚€(gè)概率分布 $p(x)$ 和 $q(x)$ 之間的距離。我們知道KL散度可以用于進(jìn)行分類(lèi)問(wèn)題。

互信息

上面介紹相對(duì)熵就是為了介紹互信息，兩個(gè)隨機(jī)變量 X,Y 的互信息，定義為 X,Y 的聯(lián)合分布和獨(dú)立分布乘積的相對(duì)熵。
$I(X,Y) = D(P(X,Y) || P(X)P(Y))$
$I(X,Y) = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x),p(y)}$
如果兩個(gè)隨機(jī)變量 $p(x)$ 和 $p(y)$ 是相互獨(dú)立那么，就是 $\frac{p(x,y)}{p(x),p(y)} = 1$ 也就是 $I(X,Y) = 0$ 如果兩個(gè)隨機(jī)變量的互信息為 0 就是說(shuō)明兩個(gè)隨機(jī)變量是相互獨(dú)立，反之就是大于 0。

有了互信息我們想證明一件事
$\begin{aligned} H(Y) - I(X,Y) = - \sum_y p(y) \log p(y) - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} \\ = -\sum_y \left( \sum_x p(x,y) \right)\log p(y) - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} \\ - \sum_{x,y} p(x,y) \log p(y) - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)}\\ - \sum_{x,y} p(x,y) \log \frac{p(y)p(x,y)}{p(x)p(y)}\\ - \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)} \\ H(Y|X) \end{aligned} \tag{2}$