统计学习方法:决策树

由于时间关系我没有实现决策树的剪枝与CART算法.

原理

熵

熵度量了不确定性,具体参考书中给出例子进行理解. $$\begin{aligned} H(x) = -\sum_{i=1}^{n}p_i\log{p_i} \end{aligned}$$

条件熵

既然熵度量了不确定性,引用条件概率后,可以得到条件熵,即给定条件下的不确定性.

注意: 公式第二行对应实际计算的情况,因为分类问题中$Y$的类别必然大于1.

$$\begin{aligned} H(Y|X)&=\sum_{i=1}^{n}{P(X=x_i)}H(Y|X=x_i)\\ &=\sum_{i=1}^{n}\left[{P(X=x_i)}\sum_{j=1}^{k}\left[P(Y=y_j|X=x_i)\log{P(Y=y_j|X=x_i)}\right]\right] \end{aligned}$$

信息增益

在极大似然估计中的得到的熵与条件熵称为经验熵与经验条件熵.将经验熵减去经验条件熵即可表示得知到$X$后对分类$Y$的不确定性减少的程度,也就是信息增益.一般地$H(Y)-H(Y|X)$被称为互信息,决策树中的信息增益等价于最大化特征与标签的互信息,只不过这里的概率都是统计出来的,结合到深度学习中还是有很大用武之地的,我个人觉得比如可以用互信息做度量代替attention机制选择特征的激活概率,当然互信息的估计没有attention那么方便.

$$\begin{aligned} g(D, A)=H(D)-H(D|A) \end{aligned}$$

实现过程

实现过程中我还是依据朴素贝叶斯的思路,先统计出多项式分布的概率再逐一求熵与条件熵.这样做比较麻烦,我其实是为了制作$P(Y=y_j|X=x_i)$的概率分布动画...对于条件概率分布差距越大的特征表明他的熵越小,那么信息增益就越大.

这里我还踩了个小坑,朴素贝叶斯的条件概率是$P(X|Y)$,这里的条件概率是$P(Y|X)$...由于时间关系也没有实现高斯分布的条件概率计算,如果需要可以参考我在朴素贝叶斯的实现.

后面考虑了下,这种概率方法的编程模型还是先弄个distribution类,然后继承各种分布,输入数据后可以计算概率分布函数和熵.这样后续实现会比较方便.

简单的做法是直接把算熵和条件熵就好了.可以看ID3的实现.