入门人工智能·机器学习篇·信息论（AIML03）

文章内容参考《PATTERN RECOGNITION & MACHINE LEARNING》作者：CHRISTOPHER M.BISHOP 文章作者联系邮箱：[email protected]

Preview (Chapter 1):

• 作者叨叨一下人工智能
• 以例子入门了解机器学习：多项式曲线拟合
• 概率论
• 模型选择
• 高维诅咒$\quad \leftarrow$←
• 决策论$\quad \leftarrow$←
• 信息论$\quad \leftarrow$←

---

1 高维诅咒

维数之咒所指的问题是，当维度增加时，空间的体积增加得非常之快（以指数增加），以致于可用的数据变得稀疏。这种稀疏性会造成统计意义上的一些困难，这是因为为了获得一个统计上可靠的结果，支持结果所需的数据量往往随着维度的增加而成倍增长。此外，组织和搜索数据通常依赖于检测具有相似属性的对象的区域，然而，在高维数据中，所有对象在许多方面看起来都是稀疏和不相似的，这使得在数据处理的过程中无法使用通用的数据处理方法。

在之前的曲线拟合中，当M=3时，产生的系数将达到$D^3$D3.

从几何方面理解：
一个半径$r=1$r=1的球形在D维空间下的体积为：
$V_D(r)=K_Dr^D$VD​(r)=KD​rD
$\frac{V_D(1)-V_D(1-\epsilon)}{ V_D(1)} = 1-(1-\epsilon)$VD​(1)VD​(1)−VD​(1−ϵ)​=1−(1−ϵ)
对于较大的D，上式趋近于1，即使对较小的$\epsilon$ϵ。所以，在高维空间中，大部分的体积是集中在表面。（是不是有点难理解）。

怎么解决高维诅咒的问题？

• 对于真实数据，空间区域的有效维度较低，所以可以使用一些算法（PCA，SVD）进行对数据的降维。
• 对于真实数据，通常会表现出一些平滑性，所以可以在局部利用插值技术。

2 决策论

推论阶段：
决定是从$p(t|x)$p(t∣x)还是$p(x,t)$p(x,t)进行预测变量和数据的结合。
决策阶段：
利用不同的决策算法找出最优的预测值。

最小错分率：

红色加绿色和蓝色区域就是错分类的区域，我们的目的是让这些错分类区域围成的面积最小从而选出最优的$x$x值。

最小损失期望：

举一个例子：如下图，得癌症被判断为癌症的人损失是0，被判为正常的损失是1000，没有得癌症被判断为癌症的损失为1，判为正常损失是0，所以可以得到如下矩阵。

所以其损失期望为：
$E(L)=\sum_k\sum_j \int_{R_j}L_{kj}p(x,C_k)dx$E(L)=k∑​j∑​∫Rj​​Lkj​p(x,Ck​)dx
所以区域$R_j$Rj​可以选择为让$E(L)=\sum_kL_{kj}p(C_k|X)$E(L)=∑k​Lkj​p(Ck​∣X)最小化。

拒绝选项：

3 信息论

熵（Entropy）衡量系统复杂度的一个指标。在编码、统计、机器学习领域是一个重要的指标。
$H(x)=-\sum_xp(x)log_2p(x)$H(x)=−x∑​p(x)log2​p(x)
举个例子，X有8种状态，最少需要多少比特才能传送X？
$H(x)=-8\times\frac{1}{8}log_2\frac{1}{8}=3bits$H(x)=−8×81​log2​81​=3bits
或者我们传送一串铭文abcdefgh，文中出现的对应字母的概率是：

熵是度量系统复杂性的一个指标：

系统数据差别不大时，熵会很大。

---

差分熵

推广到连续型随机变量的熵。高斯分布具有最大的差分熵。$H(x)=\frac{1}{2}(1+ln(2\pi \sigma^2))$H(x)=21​(1+ln(2πσ2)).（证明方法：对高斯分布积分，利用其均值和方差带入即可证明）

---

条件熵

条件熵 $H(Y|X)$H(Y∣X) 表示在已知随机变量 $X$X 的条件下随机变量 $Y$Y 的不确定性。条件熵 $H(Y|X)$H(Y∣X) 定义为 $X$X 给定条件下 $Y$Y 的条件概率分布的熵对 $X$X 的数学期望，条件熵 $H(Y|X)$H(Y∣X) 相当于联合熵 $H(X,Y)$H(X,Y) 减去单独的熵 $H(X)$H(X)，即

---

相对熵 $(Relative entropy)$(Relativeentropy)，也称KL散度 $(Kullback–Leibler divergence)$(Kullback–Leiblerdivergence)

相对熵$（relative entropy）$（relativeentropy），又被称为$Kullback-Leibler$Kullback−Leibler散度$（Kullback-Leibler divergence）$（Kullback−Leiblerdivergence）或信息散度$（information divergence）$（informationdivergence），是两个概率分布间差异的非对称性度量 。在在信息理论中，相对熵等价于两个概率分布的信息熵$（Shannon entropy）$（Shannonentropy）的差值。
设$p(x)、q(x)$p(x)、q(x)是离散随机变量 $X$X 中取值的两个概率分布，则 $p$p 对 $q$q 的相对熵是：

• 如果$p(x)$p(x),$q(x)$q(x)分布相同，则相对熵为0。
• 相对熵不具备对称性，即$KL(p||q)$KL(p∣∣q)不等于$KL(q||p)$KL(q∣∣p)。
• $D_{KL}(p||q)\geq0$DKL​(p∣∣q)≥0证明：利用jensen不等式。
  
  
  $\sum q(x)=1$∑q(x)=1
  所以最后$D_{KL}(p||q)>=0$DKL​(p∣∣q)>=0。
  $D_{KL}(p||q)=\displaystyle\sum_{x}p(x)log\frac{p(x)}{q(x)}=E_{p(x)}log\frac{p(x)}{q(x)}$DKL​(p∣∣q)=x∑​p(x)logq(x)p(x)​=Ep(x)​logq(x)p(x)​
  相对熵可以用来衡量两个概率分布之间的差异，上面公式的意义就是求 $p$p 与 $q$q 之间的对数差在 $p$p 上的期望值。

---

交叉熵 (Cross Entropy)

参考https://www.cnblogs.com/kyrieng/p/8694705.html

$H(p,q)=\displaystyle\sum _{x}p(x)log\frac{1}{q(x)}$H(p,q)=x∑​p(x)logq(x)1​

交叉熵可以用来计算学习模型分布与训练分布之间的差异。交叉熵广泛用于逻辑回归的Sigmoid和Softmax函数中作为损失函数使用。

现在有关于样本集的两个概率分布 $p(x)$p(x) 和 $q(x)$q(x)，其中 $p(x)$p(x) 为真实分布， $q(x)$q(x) 非真实分布。如果用真实分布 $p(x)$p(x) 来衡量识别别一个样本所需要编码长度的期望（平均编码长度）为:
$H(p) =\displaystyle\sum_{x}p(x)log\frac{1}{p(x)}$H(p)=x∑​p(x)logp(x)1​
如果使用非真实分布 $q(x)$q(x) 来表示来自真实分布 $p(x)$p(x) 的平均编码长度，则是：
$H(p,q)=\displaystyle\sum _{x}p(x)log\frac{1}{q(x)}$H(p,q)=x∑​p(x)logq(x)1​
因为用 $q(x)$q(x) 来编码的样本来自于分布 $q(x)$q(x) ，所以 $H(p,q)$H(p,q) 中的概率是 $p(x)$p(x)。此时就将 $H(p,q)$H(p,q) 称之为交叉熵。
$D_{KL}(p||q)=H(p,q)-H(p)$DKL​(p∣∣q)=H(p,q)−H(p)
当用非真实分布 $q(x)$q(x) 得到的熵比真实分布 $p(x)$p(x) 得到的熵多的部分就是相对熵。并且当 $H(p)$H(p) 为常量时（注：在机器学习中，训练数据分布是固定的），最小化相对熵 $D_{KL}(p||q)$DKL​(p∣∣q) 等价于最小化交叉熵 $H(p,q)$H(p,q) 也等价于最大化似然估计。

---

互信息

参考https://blog.****.net/pipisorry/article/details/51695283

如果$(X, Y) \sim p(x, y), X, Y$(X,Y)∼p(x,y),X,Y之间的互信息 $I(X; Y)$I(X;Y)定义为:
$I(X,Y)=\sum_x\sum_yp(x,y)log\frac{p(x,y)}{p(x)p(y)}$I(X,Y)=x∑​y∑​p(x,y)logp(x)p(y)p(x,y)​
其实互信息是更广泛相对熵的特殊情况。如果变量不是独立的,那么我们可以通过考察联合概率分布与边缘概率分布乘积之间的 Kullback-Leibler 散度来判断它们是否“接近”于相互独立。此时, Kullback-Leibler 散度为：
$I(x,y)=KL(p(x,y)||p(x)p(y))=-\int\int p(x,y)ln(\frac{p(x,y)}{p(x)p(y)})dxdy$I(x,y)=KL(p(x,y)∣∣p(x)p(y))=−∫∫p(x,y)ln(p(x)p(y)p(x,y)​)dxdy
这被称为变量 $x$x 和变量 $y$y 之间的互信息( mutual information )。根据 Kullback-Leibler 散度的性质,我们看到 I[x, y] ≥ 0 ,当且仅当 x 和 y 相互独立时等号成立。
使用概率的加和规则和乘积规则,我们看到互信息和条件熵之间的关系为:
$I(x,y)=H(x)-H(x|y)=H(y)-H(y|x)$I(x,y)=H(x)−H(x∣y)=H(y)−H(y∣x)
可以把互信息看成由于知道 y 值而造成的 x 的不确定性的减小(反之亦然)（即Y的值透露了多少关于X 的信息量）。

---

下节预告：

概率分布！（入门人工智能必修的基础数学知识，跟着老王慢慢学，下节见～～～）