Question

1. 设随机变量 $ MathJax-Element-75 $ 的概率分布为 $ MathJax-Element-68 $ ，熵为： $ MathJax-Element-69 $ 。

   可以证明： $ MathJax-Element-70 $ ，其中 $ MathJax-Element-71 $ 为 $ MathJax-Element-75 $ 的取值的个数。

   当且仅当 $ MathJax-Element-75 $ 的分布为均匀分布时有 $ MathJax-Element-74 $ 。即 $ MathJax-Element-254 $ 时熵最大。

1.1 最大熵原理

1. 最大熵Max Entropy原理：学习概率模型时，在所有可能的概率模型（即概率分布）中，熵最大的模型是最好的模型。

   • 通常还有其他已知条件来确定概率模型的集合，因此最大熵原理为：在满足已知条件的情况下，选取熵最大的模型。
   • 在满足已知条件前提下，如果没有更多的信息，则那些不确定部分都是“等可能的”。而等可能性 通过熵最大化来刻画。

2. 最大熵原理选取熵最大的模型，而决策树的划分目标选取熵最小的划分。原因在于：

   • 最大熵原理认为在满足已知条件之后，选择不确定性最大（即：不确定的部分是等可能的）的模型。也就是不应该再施加任何额外的约束。

     因此这是一个求最大不确定性的过程，所以选择熵最大的模型。

   • 决策树的划分目标是为了通过不断的划分从而不断的降低实例所属的类的不确定性，最终给实例一个合适的分类。因此这是一个不确定性不断减小的过程，所以选取熵最小的划分。

1.2 期望的约束

1. 一种常见的约束为期望的约束： $ MathJax-Element-283 $ ，其中 $ MathJax-Element-295 $ 代表随机变量 $ MathJax-Element-75 $ 的某个函数（其结果是另一个随机变量）。

   • 其物理意义为：随机变量 $ MathJax-Element-997 $ 的期望是一个常数。
   • 示例：当 $ MathJax-Element-82 $ 时，约束条件为： $ MathJax-Element-376 $ ，即随机变量 $ MathJax-Element-75 $ 的期望为常数。

2. 如果有多个这样的约束条件：

   $ \mathbb E[f_1(X)]=\sum_XP(X)f_1(X)=\tau_1\\ \vdots\\ \mathbb E[f_k(X)]=\sum_XP(X)f_k(X)=\tau_k $

   则需要求解约束最优化问题：

   $ \max_{P(X)} -\sum_X P(X)\log P(X)\\ s.t. \sum_XP(X)=1,0\le P\le 1\\ \mathbb E[f_1(X)]=\sum_XP(X)f_1(X)=\tau_1\\ \vdots\\ \mathbb E[f_k(X)]=\sum_XP(X)f_k(X)=\tau_k $

3. 给出拉格朗日函数：

   $ L(P)= -\sum_X P(X)\log P(X)+\lambda_0\left(\sum_XP(X)-1\right)+\lambda_1\left(\sum_XP(X)f_1(X)-\tau_1\right)\\ +\cdots+\lambda_k\left(\sum_XP(X)f_k(X)-\tau_k\right) $

   可以求得：

   $ P(X)=\frac 1Z\exp\left(-\sum_{i=1}^k\lambda_if_i(X)\right),\quad Z=\sum_X\exp\left(-\sum_{i=1}^k\lambda_if_i(X)\right) $

   • 将 $ MathJax-Element-91 $ 代入 ，有：

     $ \mathbb E[f_1(X)]=\sum_X\frac {f_1(X)}{Z}\exp\left(-\sum_{i=1}^k\lambda_if_i(X)\right)=\tau_1\\ \vdots\\ \mathbb E[f_k(X)]=\sum_X\frac {f_k(X)}{Z}\exp\left(-\sum_{i=1}^k\lambda_if_i(X)\right)=\tau_k $

     则可以求解出各个 $ MathJax-Element-81 $ 。

   • 该式子并没有解析解，而且数值求解也相当困难。

4. 当只有一个约束 $ MathJax-Element-82 $ 时，表示约束了变量的期望，即 $ MathJax-Element-84 $ 。此时有：

   $ P(X)=\frac{\exp(-\lambda X)}{\sum_X\exp(-\lambda X)} $

   代入 $ MathJax-Element-84 $ ，解得： $ MathJax-Element-464 $ 。

   即：约束了随机变量期望的分布为指数分布。

5. 当有两个约束 $ MathJax-Element-489 $ 时，表示约束了变量的期望和方差。即：

   $ \sum_X P(X)X=\tau_1,\quad\sum_X P(X) X^2=\tau_2 $

   此时有：

   $ P(X)=\frac{\exp(-\lambda_1 X-\lambda_2 X)}{\sum_X\exp(-\lambda_1 X-\lambda_2 X)} $

   代入约束可以解得：

   $ P(X)=\sqrt{\frac {1}{2\pi(\tau_2-\tau_1^2)}}\exp\left(-\frac{(X-\tau_1)^2}{2(\tau_2-\tau_1^2)}\right) $

   它是均值为 $ MathJax-Element-85 $ ，方差为 $ MathJax-Element-86 $ 的正态分布。即：约束了随机变量期望、方差的分布为正态分布。