Entropy，Gini ，Information gain

2021-09-10 本文已影响0人 shudaxu

Entropy

信息量：值域 $[0,+{\inf} ]$
$\mathbb I(x) = -log(p(x))$
发生概率越小，信息量越大。
不确定性越高，信息量越大。
信息熵：值域 $[0,+{\inf} ]$ ,更确切为： $[0,log(n)]$ ， $n$ 为类别数量：
$H(X) = -\sum_i p(x_i)log(p(x_i))$
Skewed Probability Distribution (unsurprising): Low entropy.
Balanced Probability Distribution (surprising): High entropy.
即衡量不确定性的大小
不确定性越高，数据越不纯，越混乱，信息熵越大。（比如二分类中概率p=0.5，entropy最大）
确定性越高，数据纯度越大，信息熵越小。（比如二分类中概率p=0.01，entropy很小）
在二分类中，信息熵值域 $[0,1]$ ，即 $- 0.5 *log_2 \frac 1 2 - 0.5 *log_2 \frac 1 2 = 1$
在N分类中，信息熵值域 $[0, - log_2 \frac 1 n]$ ，最大为所有类别概率相等时 $-n* \frac 1 n log_2 \frac 1 n= -log_2 \frac 1 n = log_2 n$ （最混乱）

GINI impurity

Gini impurity可以理解为熵模型的一阶泰勒展开。所以也叫GINI不纯度。越“纯”即越确定，gini数值越小。这点与entropy是一致的。
$Gini(X) = \sum_i^k p(x_i)(1-p(x_i)) = 1 - \sum_i^k p(x_i)^2$
$H(X) = - \sum_i^k p(x_i) log(p(x_i))$ 对其中log的部分在 $x_0=1$ 处做一阶段泰勒展开：
$log(x) = log(x_0) + log'(x_0) (x - x_0)$ 【一阶展开】
带入 $x_0=1$ 即可得到 $log(x) = x - 1$ 【带入数据点】
得到 $Gini(X)=- \sum_i^k p(x_i) (p(x_i) - 1)$
$= \sum_i^k p(x_i)- \sum_i^k p(x_i)^2$
$= 1 - \sum_i^k p(x_i)^2$ 【概率sum to 1】

1、Gini在决策树中的运用：
决策树会选择gini最小的划分。（即划分后节点得到最大的确定性【纯度】）

Gini Index（Coefficient）

注意，gini 系数与gini 不纯度是不一样的概念。

1、Gini Index与AUC的关系：特定情况下Gini=2AUC-1
gini：measure how often a randomly chosen element from the set would be incorrectly labeled。
https://blog.csdn.net/u012735708/article/details/86002858
2、Gini Index与KS的关系：
https://blog.csdn.net/buptdavid/article/details/84308900

"单一"变量Entropy

研究单一变量。下述p，q等概率分布（密度函数），描述的都是对同一个变量 $x$ 的密度，譬如 $p(x_i),q(x_i)$ 对应的是同一个 $x_i$ ，这里单一是带引号的，因为多个变量编码组成的变量，也可以算作“单一”变量，譬如32位整数可以当作32个2维0，1变量编码组成的“单一”变量。

交叉熵：值域 $[H(p),+{\inf} ]$
$H(p,q) = -\sum_i p(x_i)log(q(x_i))$
当且仅当 $p=q$ 时最小，此时 $H(p,q) = H(p)$
衡量两个事件不确定性的关联性，完全一致时，取得最小值。
PS：
注意，实际在我们优化模型的时候，理论最小交叉熵是0，如果特征可以直接编码单条样本，则data本身没有不确定性，(！！！其实，其交叉熵计算的维度是单条样本，单条样本上，用empirical distribution来表示 $p(x)$ ，真实的类别概率为1，另一个概率为0。！！！）。而理论上界是全体概率作为估计的熵（如果模型logloss高于这个上界，说明还不如统计估计。譬如，如果正样本率5%，那么统计值的交叉熵logloss为 $H(p,q) = -0.05*log(0.05) - 0.95*log(0.95) = 0.19$ ，这个loss值可以视作baseline）
KL散度， $D_{KL}$ ，相对熵：值域 $[0,+{\inf} ]$
$D_{KL}(p,q) = H(p,q) - H(p)$ （交叉熵 - 熵）
$= -\sum_i p(x_i)log(q(x_i)) + \sum_i p(x_i)log(p(x_i))$
$=\sum_i p(x_i)log(\frac {p(x_i)}{q(x_i)})$
当且仅当 $p=q$ 时最小取得0，此时 $H(p,q) = H(p)$
注意：Dkl虽然非负，但是由于其不对称性，严格意义无法作为距离指标。（距离指标需要满足对称，非负，三角不等式，例如cosine距离即非严格measure）
关于KL散度的值域，由Gibbs' inequality
证明如下：
https://en.wikipedia.org/wiki/Gibbs'_inequality

多变量 entropy，information gain

这里Y，X对应的是不同的变量（事件），条件熵，联合熵基本也对应条件概率，联合概率

条件熵：值域 $[0,H(Y)]$
已知X情况下，Y的熵的期望。
$H(Y|X) = \sum_i p(x_i)H(Y|X=x_i)$
$= - \sum_i p(x_i) \sum_j p(y_j| x_i) log(p(y_j|x_i))$
$= - \sum_i \sum_j p(y_j , x_i) log(p(y_j|x_i))$ 【双重求和，外层 $i$ 确定时， $p(x_i)$ 为常数，可以直接移入内层sum。然后贝叶斯即可】
即当已知X的情况下，Y的不确定性为多少。如果X与Y无关，此时取得最大值 $H(Y|X) = H(Y)$ 。当条件熵等于0时，意味着已知X就能确定Y，即不存在不确定性。

联合熵：值域 $[0,H(X) + H(Y)]$
$H(X,Y) = H(X|Y) + H(Y) = H(Y|X) + H(X)$
$= -\sum_{i} \sum_{j} p(y_j , x_i) log(p(y_j, x_i))$
当两变量无关时，等于两者各自熵的和。
信息增益：值域 $[0,H(Y)]$
$IG(Y,X) = H(Y) - H(Y|X)$ ，即：熵 - 条件熵
$= - \sum_j p(y_j) log(p(y_j)) + \sum_i \sum_j p(x_i,y_j)log(p(y_j|x_i))$
$= - \sum_i \sum_j p(x_i, y_j) log(p(y_j)) + \sum_i \sum_j p(x_i,y_j)log(p(y_j|x_i))$ 【加入sum，反边缘化x变量】
$= \sum_i \sum_j p(x_i, y_j) log(\frac {p(y_j| x_i)}{p(y_j)})$ 【sum项合并】
$= \sum_i \sum_j p(x_i, y_j) log(\frac {p(y_j, x_i)}{p(y_j)p(x_i)})$ 【贝叶斯】
$=D_{KL}(p(x,y) ||p(x)p(y))$ 【反向还原为KL离散度】
即：信息增益可以解释为x，y联合分布（真实分布 $p(x,y)$ ）与假设x，y互相独立 $p(x)p(y)$ 的情况下的KL散度: $D_{KL}(p(x,y) ||p(x)p(y))$
代表在某种条件下，信息熵的减少（混乱程度的减少）
往往前者原始熵是固定的，所以最大化信息增益时，即在最小化条件熵。
即，在条件X下划分的数据Y，其熵最小（数据纯度大，譬如都是1或都是0）
所以当 $H(Y|X) = 0$ 时，取得最大值，即消除不确定性
互信息（数值上与information gain 相同）
$MI(X;Y) =H(X,Y) - H(Y|X) - H(X|Y)= H(Y) - H(Y|X) = H(X) - H(X|Y)$
在数值上与信息增益是相同的。只是说互信息中两变量的地位是相同的。而信息增益逻辑上是知道后者以后，前者不确定性的减少。
信息增益率
$Ratio(Y,X) = \frac {H(Y) - H(Y|X)} {H(X)}$
ID3用信息增益，ID4.5用信息增益率。