Entropy，Gini ，Information gain

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用信息增益率。

Jensen's inequality

Refer：
Entropy,Gini,
https://zhuanlan.zhihu.com/p/74930310
and mutual information
[https://en.wikipedia.org/wiki/Mutual_information#Relation_to_conditional_and_joint_entropy]

Taylor Expansion of Entropy
https://www.programmersought.com/article/85613955092/

互信息，图示，类似概率
https://www.zhihu.com/question/39436574

DKL，Information Gain
https://blog.csdn.net/tiandiwoxin92/article/details/78244739

最后编辑于：2021.09.17 14:49:13

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 205,386评论 6赞 479
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,939评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,851评论 0赞 341
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,953评论 1赞 278
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,971评论 5赞 369
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,784评论 1赞 283
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,126评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,765评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,148评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,744评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,858评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,479评论 4赞 322
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,080评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,053评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,278评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,245评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,590评论 2赞 343