当前位置：网站首页>Chapter 4 决策树和随机森林

Chapter 4 决策树和随机森林

2022-07-27 02:19:00 【桑之未落0208】

1 信息熵

1.1 熵

1 信息熵

1.1 熵

熵可以理解成概率分布的不确定性的期望值。这个值越大，表示该概率分布不确定性越大。它为我们人类提供的“信息”就越小，我们越难利用这个概率分布做出一个正确的判断。即概率越大越确定，熵就越小。

表达式： $H(X)=-\sum_{x}^{}p(x)logp(x)$

1.2 联合熵

(X,Y)所包含的熵

表达式： $H(X,Y)=-\sum_{x,y}^{}p(x,y)logp(x,y)$

1.3 条件熵

(X,Y)所包含的熵，减去X单独发生包含的熵，即在X发生的前提下，Y发生“新”带来的熵。

表达式： H(Y|X) 或者 H(X,Y)-H(X)

推导：

$H(X,Y)-H(X)=-\sum_{x,y}^{}p(x,y)log p(x,y)+\sum_{x}^{}p(x)logp(x)=-\sum_{x,y}^{}p(x,y)log p(x,y)+\sum_{x}^{}(\sum_{y}^{}p(x,y))log(x)=-\sum_{x,y}^{}p(x,y)log p(x,y)+-\sum_{x,y}^{}p(x,y)log p(x)=-\sum_{x,y}^{}p(x,y)log \frac{p(x,y)}{p(x)}=-\sum_{x,y}^{}p(x,y)log p(y|x)=-\sum_{x}^{}\sum_{y}^{}p(x)p(y|x)logp(y|x)=-\sum_{x}^{}p(x)\sum_{y}^{}p(y|x)logp(y|x)=\sum_{x}^{}p(x)H(Y|X=x)=H(Y|X)$

1.4 相对熵

相对熵又称互熵、交叉熵、鉴别信息、Kullback熵、Kullback-Leible散度等等。

设p(x)、q(x)是X中取值的两个概率分布，则对p对q的相对熵是

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

$pln\frac{p}{q}=p(lnp-lnq)=plnp-plnq=-(-plnp+plnq)=-(H(p)+lnq^{p})=-H(p)-lnq^{p}$

ps:相对熵可以度量两个随机变量的“距离”,想要使得相对熵最小， H(p) 是固定的，所以要使得 $lnq^{p}$ 最大。写成样本为 $\prod_{i=1}^{m}q_{i}^{p_{i}}$ ,求其最大值，即为求最大似然估计。

1.5 互信息

两个随机变量X,Y的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。

也可以看作H(Y)和H(Y|X)的差值。

表达式：
$I(X,Y)=D(P(X,Y)||P(X)P(Y))=\sum_{x,y}^{}log\frac{p(x,y)}{p(x)p(y)}$

或： I(X,Y)=H(Y)-H(Y|X)

或： I(X,Y)=H(X)+H(Y)-H(X,Y)

度量联合分布和独立分布乘积的“距离”；若X,Y相互独立，那么互信息就为0。

第二个公式推导：
$H(Y)-H(Y|X)=-\sum_{y}^{}p(y)logp(y)+\sum_{x,y}^{}p(x,y)logp(y|x)=-\sum_{y}^{}(\sum_{x}^{}p(x,y))logp(y)+\sum_{x,y}^{}p(x,y))log\frac{p(x,y)}{p(x)}=-\sum_{x,y}^{}p(x,y)logp(y)+\sum_{x,y}^{}p(x,y))log\frac{p(x,y)}{p(x)}=\sum_{x,y}^{}p(x,y)log\frac{p(x,y)}{p(x)p(y)}=I(X,Y)$

第三个公式推导：

$H(X)+H(Y)-H(X,Y)=-\sum_{x}^{}p(x)log(x)-\sum_{y}^{}p(y)log(y)+\sum_{x,y}^{}p(x,y)log(x,y)=-\sum_{x}^{}(\sum_{y}^{}p(x,y))logp(x)-\sum_{y}^{}(\sum_{x}^{}p(x,y))logp(y)+\sum_{x,y}^{}p(x,y)log(x,y)=-\sum_{x,y}^{}p(x,y)logp(x)-\sum_{x,y}^{}p(x,y)logp(y)+\sum_{x,y}^{}p(x,y)log(x,y)=\sum_{x,y}^{}p(x,y)(logp(x,y)-logp(x)-logp(y))=\sum_{x,y}^{}p(x,y)log\frac{p(x,y)}{p(x)p(y)}$