PRML第一章习题答案
Chapter 1. Introduction
目录- Chapter 1. Introduction
- 习题简述
- 习题详解
- Exercise 1.1
- Exercise 1.2
- Exercise 1.4
- Exercise 1.15
- Exercise 1.16
- Exercise 1.19
- Exercise 1.20
- Exercise 1.21
- Exercise 1.22
- Exercise 1.24
- Exercise 1.27
- Exercise 1.28
- Exercise 1.29
- Exercise 1.31
- Exercise 1.32
- Exercise 1.33
更新日志（截至20210618）
- 20210618：添加习题 1.2-1.4 的简述，习题 1.1-1.2，1.4，1.14-1.15 的详解
- 20210614：添加习题 1.22，1.24，1.28-1.29 的详解
- 20210503：添加习题简述和习题 1.19-1.21，1.27，1.31-1.33 的详解
- 20210127：首次提交，含习题 1.31 的详解
习题简述
- 多项式回归
- 1.1：多项式回归的最小二乘解
- 1.2：带二范数正则的多项式回归的最小二乘解
- 1.3：全概率公式计算实例与最大后验概率计算实例
- 1.4：随机变量的函数的极大似然估计一般不等于随机变量极大似然估计的函数
- 1.15-1.16：多项式回归的有效参数量
- 概率论
- 1.5：方差等于二阶矩减去一阶矩的平方
- 1.6：独立随机变量间的协方差为零
- 1.7：单变量高斯的归一化常数
- 1.8：单变量高斯的均值和方差
- 1.9：高斯分布的众数
- 1.10：独立随机变量的和的方差等于方差的和
- 1.11：单变量高斯的极大似然估计
- 1.12：独立高斯变量间的二阶交叉矩
- 1.13：如果知道真实的均值，则样本标准差为标准差的无偏估计，否则为有偏估计
- 1.14：任意方阵可以表示为一个对称矩阵和一个反对称矩阵的和
- 1.17：gamma 函数是阶乘的连续延拓
- 高维高斯分布的行为
- 1.18：高维球的体积
- 1.19：高维球的体积在空间中的占比随着维度的增大而急剧缩小
- 1.20：高维高斯的概率质量集中在一个“薄球壳”上
- 决策论（分类问题）
- 1.21：二分类问题分类误差的一个上界
- 1.22：若分类损失为错分类计数，则期望上等同于最小化分类的错误率
- 1.23：基于一般错分类 loss 矩阵的分类优化准则
- 1.24：若分类概率超过某个阈值 \(\lambda \in(0,1]\) 时才接受该分类结果，则拒绝概率为 \(1-\lambda\)
- 1.25-1.26：平方损失下回归问题的最优解为条件期望
- 1.27：回归问题损失函数为 \(p\)-范数时的最优解
- 信息论
- 1.28：熵必为对数形式
- 1.29：类别分布的熵有上界
- 1.30：高斯分布间的 KL 散度
- 1.31：联合熵小于等于熵的和，当随机变量独立时取等号
- 1.32：随机变量经线性变换的熵
- 1.33：若两个离散随机变量的条件熵 \(\text{H}[y|x]\) 为零，则在 \(p(x)\) 的支撑集上，一个 \(x\) 唯一确定一个 \(y\)。
- 1.34：给定均值和方差的最大熵估计是高斯分布
- 1.35：计算高斯分布的熵
- 1.36：二次可微函数的凸性等价于海森矩阵正定
- 1.37：联合熵等于熵加上条件熵
- 1.38：凸组合的函数值小于等于函数值的凸组合
- 1.39：给定分布律实例，计算熵，条件熵，互信息
- 1.40：算数平均大于等于几何平均
- 1.41：互信息等于熵减去条件熵
习题详解
Exercise 1.1
Hint.
记 \(\phi(x)=[x^0,\dots,x^M]^T,\mathbf{x}=[x_1,\dots,x_N]^T,\Phi=\phi(\mathbf{x})\in\mathbb{R}^{N\times M},\mathbf{t}=[t_1,\dots,t_N]^T,\mathbf{w}=[w_1,\dots,w_M]^T\)，则多项式回归的目标函数可以写成 \(\frac{1}{2}\|\Phi \mathbf{w}-\mathbf{t}\|^2_2\)，对 \(\mathbf{w}\) 求导并令导数为零可得 \(\Phi^T\Phi\mathbf{w}=\Phi^T\mathbf{t}\)，其中 \((\Phi^T\Phi)_{ij}=\sum^N_{n=1}x_n^{i+j}\)。
Exercise 1.2
Hint.
在上题的基础上，带二范数正则的多项式回归的目标函数可以写成 \(\frac{1}{2}\|\Phi \mathbf{w}-\mathbf{t}\|^2_2+\frac{\lambda}{2}\|\mathbf{w}\|^2_2\)，对 \(\mathbf{w}\) 求导并令导数为零可得 \((\Phi^T\Phi+\lambda I)\mathbf{w}=\Phi^T\mathbf{t}\)，其中 \((\Phi^T\Phi+\lambda I)_{ij}=\lambda\delta_{ij}+\sum^N_{n=1}x_n^{i+j}\)。
Exercise 1.4
Hint.
记 \(g:\mathbb{R}^n\to\mathbb{R}^n,x=g(y)\)，则有 \(p_y(y)=p_x(g(y))|J|\)，其中 \(J=\frac{\partial g}{\partial y}\) 记
一般地，\(p_x(g(\widehat{y}))\leq p_x(\widehat{x})\)。当 \(g\) 是可逆仿射变换时，即 \(x=g(y)=Ay+b\)，\(|g'(y)|=|A|\) 为非零常数，两个优化问题等价，有 \(\widehat{x}=A\widehat{y}+b\)。
Comment.
仅当 \(g\) 为 \(\mathbb{R}^n\) 上的可逆函数时，才有变换前后的概率密度函数间的对应关系 \(p_y(y)=p_x(g(y))|J|\)。
Exercise 1.15
Hint.
记多项式的 \(m\) 次项为 \(\prod^D_{i=1}x_i^{n_i}\)，满足 \(\sum^D_{i=1}n_i=m,n_i\geq 0\)，即求不定整数方程解的个数，根据相关结论得 \(m\) 次项的系数为 \(n(D,m)=C^{D-1}_{D+m-1}\)。
Comment.
本解法给出了题目提示思路外的一种不需要归纳法的直接解法。
Exercise 1.16
Solution.
总参数量即 \(N(D,M)=\sum^M_{m=1}C^{D-1}_{D+m-1}\)，用归纳法证明 \(N(D,M)=C^D_{D+M}\)。当 \(M=0\) 时，显然成立。假设对某个 \(M\) 成立，考虑 \(M+1\)，
其中最后一个等号用到了组合恒等式 \(C^m_n+C^{m-1}_n=C^m_{n+1}\)。
下面用 Stirling 公式估计其关于 \(D\) 和 \(M\) 的阶数。
由 Stirling 公式得 \(n!\simeq (2\pi)^{1/2}e^{-n}n^{n+1/2}\)，故
若 \(D\gg M\)，则 \(\left(1+\frac{M}{D}\right)^D\to e^M,(D^{-1}+M^{-1})^{1/2}\to M^{-1/2},\left(1+\frac{D}{M}\right)^M=D^M(D^{-1}+M^{-1})^M\)，固定 \(M\)，则前述项关于 \(D\) 以 \(M\) 次幂的速度增长。由于 \(D,M\) 的位置关系是对称的，因此当 \(D \ll M\) 时也有类似的结论。由此可见，多项式系数的个数关于原始特征维度 \(D\) 大约是多项式规模增长的，因此多项式回归不适合高维问题。
Exercise 1.19
Solution.
\(D\) 维单位球的体积为 \(\frac{2\pi^{D/2}}{D\Gamma(D/2)}\)，容纳其的最小立方体的体积为 \(2^D\)，单位球的体积占比为 \(\frac{2\pi^{D/2}}{D2^D\Gamma(D/2)}=\frac{2\pi^{D/2}}{D2^{D-1}\Gamma(D/2)}\)。由于 gamma 函数没有解析式，采用其 Stirling 估计，\(\Gamma(x+1)\simeq (2\pi)^{1/2}e^{-x}x^{x+1/2}\)。故
第二个等号是因为当 \(D\to\infty\)，第一项趋于常数，类似于 \(\underset{n\to\infty}{\lim}(1+\frac{1}{n})^n\)，第二项阶数为 \(o(D^{-1/2})\)，即高维球的体积占比以维度的平方根的倒数的速度趋于零。
另一方面，立方体中心到任一顶点的距离为 \(D^{1/2}\)，而单位球的半径为 \(1\)，比例为 \(D^{-1/2}\)，亦以维度的平方根的倒数的速度趋于零。
Comment.
本题刻画了高维单位球在容纳其最小的立方体中的体积占比随维度增大趋于零的速度。
Exercise 1.20
Solution.
半径为 \(r\) 的 \(D\) 维球的体积为 \(\frac{S_D}{D}r^D\)，其中 \(S_D\) 为 \(D\) 维单位球的表面积。则高维球的体积微元为 \(S_D r^{D-1}\,\text{d}r\)，故计算高斯积分时，将直角坐标转为极坐标，并对角度积分后得到概率密度随半径 \(r\) 的分布 \(p(r)=\frac{S_D r^{D-1}}{(2\pi\sigma^2)^{D/2}}\exp\left(-\frac{r^2}{2\sigma^2}\right)\propto r^{D-1}\exp\left(-\frac{r^2}{2\sigma^2}\right)=f(r)\)。对 \(f(r)\) 求导有
分析可知 \(f\) 有唯一的极大值点（同时为最大值点）\(\widehat{r}=\sigma(D-1)^{1/2}\)。下面考虑最大值点附近的情况，
\[\begin{aligned} \frac{f(\widehat{r}+\epsilon)}{f(\widehat{r})} &=\left(\frac{\widehat{r}+\epsilon}{\widehat{r}}\right)^{D-1}\exp\left(-\frac{2\epsilon\widehat{r}+\epsilon^2}{2\sigma^2}\right)\\ &=\left(1+\frac{\epsilon}{\sigma(D-1)^{1/2}}\right)^{D-1}\exp\left(-\frac{\epsilon(D-1)^{1/2}}{\sigma}\right)\exp\left(-\frac{\epsilon^2}{2\sigma^2}\right)\\ &=\exp\left((D-1)\ln(1+\frac{\epsilon}{\sigma(D-1)^{1/2}})-\frac{\epsilon(D-1)^{1/2}}{\sigma}\right)\exp\left(-\frac{\epsilon^2}{2\sigma^2}\right)\\ &=\exp\left((D-1)(\ln(1+t)-t)\right)\exp\left(-\frac{\epsilon^2}{2\sigma^2}\right)\quad(t=\frac{\epsilon}{\sigma(D-1)^{1/2}})\\ &=\exp\left((D-1)(-\frac{t^2}{2}+o(t^3))\right)\exp\left(-\frac{\epsilon^2}{2\sigma^2}\right)\\ &=\exp\left(-\frac{\epsilon^2}{2\sigma^2}\right)\exp\left(o(t)\right)\exp\left(-\frac{\epsilon^2}{2\sigma^2}\right)\\ &=\exp\left(-\frac{\epsilon^2}{\sigma^2}+o(t)\right) \end{aligned} \]上述推导说明，在概率质量最大的球面附近，概率质量随着对最优半径的远离指数衰减，从一个侧面说明概率质量集中在半径为 \(\widehat{r}\) 的球壳上。
以上结论适用于各向同性的高斯，即协方差矩阵为算术矩阵，若协方差矩阵为一般矩阵时，总可以通过坐标变换将其变为各向同性的高斯，所以坐标变换回去就可以得到，高维高斯的概率质量集中在一个椭球壳上。
Comment.
Exercise 1.21
Solution.
\[\begin{aligned} p(\text{mistake}) &=\int_{\mathcal{R}_1}p(x,\mathcal{C}_2)\,\text{d}x+\int_{\mathcal{R}_2}p(x,\mathcal{C}_1)\,\text{d}x\\ &=\int_{\mathcal{R}_1}p(\mathcal{C}_2|x)p(x)\,\text{d}x+\int_{\mathcal{R}_2}p(\mathcal{C}_1|x)p(x)\,\text{d}x\\ &\leq\int_{\mathcal{R}_1}\sqrt{p(\mathcal{C}_2|x)p(\mathcal{C}_1|x)}p(x)\,\text{d}x+\int_{\mathcal{R}_2}\sqrt{p(\mathcal{C}_1|x)p(\mathcal{C}_2|x)}p(x)\,\text{d}x\\ &=\int\sqrt{p(\mathcal{C}_1|x)p(x)p(\mathcal{C}_2|x)p(x)}\,\text{d}x\\ &=\int\sqrt{p(\mathcal{C}_1,x)p(\mathcal{C}_2,x)}\,\text{d}x\\ \end{aligned} \]不等号处用到了决策条件
\[\begin{cases} &p(\mathcal{C}_2|x)\leq p(\mathcal{C}_1|x),x\in\mathcal{R}_1\\ &p(\mathcal{C}_1|x)\leq p(\mathcal{C}_2|x),x\in\mathcal{R}_2 \end{cases} \]Comment.
本题给出了二分类问题分类误差的一个上界。
Exercise 1.22
Solution.
\[\begin{aligned} \mathbb{E}[L] &=\sum_k\sum_j\int_{\mathcal{R}_j}L_{kj}p(x,\mathcal{C}_k)\,\text{d}x\\ &=\sum_k\sum_jL_{kj}p(x\in\mathcal{R}_j,\mathcal{C}_k)\\ &=\underset{p(x,\mathcal{C}_k)}{\mathbb{E}}[L_{kj}\mathbf{1}_{[x\in\mathcal{C}_j,\mathcal{C}_k]}]\\ &=\underset{p(x,\mathcal{C}_k)}{\mathbb{E}}[(1-\delta_{kj})\mathbf{1}_{[x\in\mathcal{R}_j,\mathcal{C}_k]}]\quad(L_{kj}=1-\delta_{kj})\\ &=1-\underset{p(x,\mathcal{C}_k)}{\mathbb{E}}[\mathbf{1}_{[x\in\mathcal{R}_k,\mathcal{C}_k]}]\\ &=1-p(\text{correct})\\ &=p(\text{misclassification}) \end{aligned} \]故当 \(L_{kj}=1-\delta_{kj}\)，优化目标为最小化错分类率。
\[\begin{aligned} \mathbb{E}[L] &=1-\underset{p(x,\mathcal{C}_k)}{\mathbb{E}}[\mathbf{1}_{[x\in\mathcal{R}_k,\mathcal{C}_k]}]\\ &=\underset{p(x)}{\mathbb{E}}[1-\underset{p(\mathcal{C}_k|x)}{\mathbb{E}}[\mathbf{1}_{[x\in\mathcal{R}_k,\mathcal{C}_k]}]]\\ &=\underset{p(x)}{\mathbb{E}}[1-p(\mathcal{C}_k|x)]] \end{aligned} \]故对于单个样本 \(x\)，其优化目标为最大化后验概率 \(p(\mathcal{C}_k|x)\)。
Exercise 1.24
Hint.
单个样本的损失为 \(\ell(x|j)=\underset{p(\mathcal{C}_k|x)}{\mathbb{E}}[L_{kj}\mathbf{1}_{[x\in\mathcal{C}_j,\mathcal{C}_k]}]\)，若损失函数的最小值大于给定阈值，即 \(\min_j\ell(x|j)>\lambda\)，则拒绝分类。若 \(L_{kj}=1-\delta_{kj}\)，\(\ell(x|j)=1-p(\mathcal{C}_j|x)\)，当 \(\max_j p(\mathcal{C}_j|x)< 1-\lambda\) 时，拒绝分类，即仅在置信度较高时才做出分类。
Exercise 1.27
Solution.
\(\mathcal{L}=\mathbb{E}[L_q]=\mathbb{E}[\|y(x)-t\|_q^q]\)，当 \(q=1\)，有
其中 \(t\in\mathbb{R}^M\)，\(t^{(m)}\) 为 \(t\) 的第 \(m\) 个元素。令 \(\delta\mathcal{L}=0\)，有 \(\underset{t^{(m)}|x}{\mathbb{E}}\left[\mathbf{1}_{\{y^{(m)}\geq t^{(m)}\}}\right]=\underset{t^{(m)}|x}{\mathbb{E}}\left[\mathbf{1}_{\{y^{(m)}< t^{(m)}\}}\right]=\frac{1}{2}\)，故 \(y^*\) 的每个维度为条件中位数。
当 \(q\in(0,1)\)，有
\[\begin{aligned} \mathcal{L} &=\underset{x}{\mathbb{E}}\,\underset{t|x}{\mathbb{E}}[\|y-t\|_q^q\mathbf{1}_{\{t|x=y\}}+\|y-t\|^q_q\mathbf{1}_{\{t|x\neq y\}}]\\ &=\underset{x}{\mathbb{E}}\,\underset{t|x}{\mathbb{E}}[\|y-t\|^q_q\mathbf{1}_{\{t|x\neq y\}}]\\ &\to \underset{x}{\mathbb{E}}\,\underset{t|x}{\mathbb{E}}[\mathbf{1}_{\{t|x\neq y\}}]\quad(q\to 0)\\ &=1-\underset{x}{\mathbb{E}}\,\underset{t|x}{\mathbb{E}}[\mathbf{1}_{\{t|x= y\}}]\\ &=1-\underset{x}{\mathbb{E}}[p(y|x)] \end{aligned} \]欲最小化 \(\mathcal{L}\)，只需令 \(y^*=\arg\max_t p(t|x)\)，即 \(y^*\) 为条件众数。
Comment.
\(q\) 取其他值的时候，最优解是什么？
Exercise 1.28
Hint.
\(h(p(x)p(y))=h(p(x))+h(p(y))\)，记 \(a=p(x),b=p(y)\)，则有 \(h(ab)=h(a)+h(b),a,b\in[0,1]\)，即得到关于 \(h\) 的函数方程，可猜测 \(h\) 为对数函数，下面予以证明。
Solution.
假设 \(h\) 可导，两边微分得 \(h'(ab)(b\,\text{d}a + a\,\text{d}b)=h'(a)\,\text{d}a+h'(b)\,\text{d}b\)，比较两边得
\[\begin{aligned} h'(a)&=h'(ab)b\\ h'(b)&=h'(ab)a \end{aligned} \]上式两边同乘 \(a\)，下式两边同乘 \(b\) 得 \(h'(a)a=h'(b)b\)，由 \(a,b\) 的任意性，\(h'(a)a=C\)，分两种情况考虑，
- 若 \(C=0\)，则 \(h'(a)=0\)，则 \(h\equiv\text{const.}\)，由 \(h(ab)=h(a)+h(b)\) 可知，\(h\equiv 0\)，即得到了一个平凡解，但该解关于自变量并非严格单调，舍弃。
- 若 \(C\neq 0\)，对于 \(a\neq 0\)，有 \(h'(a)=Ca^{-1}\)，故 \(h(a)=C\ln a + C'\)，由 \(h(ab)=h(a)+h(b)\) 可知，\(C'=0\)，故 \(h(a)=C\ln a\)，但 \(h\) 在 \(a=0\) 处无定义。
综上，\(h(p(x))\propto \ln p(x),p(x)>0\)。
Comment.
本解答假设 \(h\) 可导进行证明，实际上只需假设 \(h\) 连续，可证明 \(h(a^{n/m})=(n/m)h(a),m,n\in\mathbb{Z}^+\)，即 \(h(a^q)=qh(a),q\in\mathbb{Q}^+\)，假设 \(a\in(0,1)\)，记 \(b=a^q\)，即 \(h(b)=h(a)\log_a b=\frac{h(a)}{\ln a}\ln b\)。\(\forall\,b\in(0,1)\)，记 \(r=\log_a b\in\mathbb{R}^+\)，由于 \(\mathbb{Q}^+\) 在 \(\mathbb{R}^+\) 稠密，故存在有理数 \(q\) 任意逼近 \(r\)，由 \(h\) 的连续性，\(\forall\,b\in(0,1),h(b)=\frac{h(a)}{\ln a}\ln b\)，该解可以延拓到 \(b=1\) 上，即 \(\forall\,b\in(0,1],h(b)=\frac{h(a)}{\ln a}\ln b\propto \ln b\)。
Exercise 1.29
Solution.
\[\begin{aligned} \text{H}[x] &=-\underset{x}{\mathbb{E}}[\ln p(x)]\\ &=\int_{p(x)>0}p(x)\ln p(x)^{-1}\,\text{d}x\\ &\leq \int_{p(x)>0}\ln \{p(x)p(x)^{-1}\}\,\text{d}x\\ &=\int_{p(x)>0}\text{d}x\\ &<\infty \end{aligned} \]若概率密度函数 \(p(x)\) 的支撑集具有有限测度，则最大熵分布在支撑集上为均匀分布。若 \(x\) 为类别变量，类别数为 \(M\)，则 \(\text{H}[x]\leq \ln M\)。若 \(x\) 为区间 \([a, b]\) 上的分布，则有 \(\text{H}[x]\leq \ln(b-a)\)。
Comment.
本题证明了在分布的支撑集具有有限测度的前提下，最大熵分布在支撑集上为均匀分布，推广了类别分布上的结论。
Exercise 1.31
Hint.
\({\rm H}[x]+{\rm H}[y]-{\rm H}[x,y]={\rm H}[x]-{\rm H}[x|y]={\rm I}[x, y]\geq 0\)
Exercise 1.32
Hint.
\(q(y)=p(x)\left|\frac{\partial x}{\partial y}\right|=p(x)|A|^{-1}\)
Solution.
\[\begin{aligned} \text{H}[y] &=-\int q(y) \ln q(y)\,\text{d}y\\ &=-\int q(y) \ln p(x)|A|^{-1}\,\text{d}|A|x\\ &=-\int q(y)|A| \ln p(x)|A|^{-1}\,\text{d}x\\ &=-\int p(x) \ln p(x)|A|^{-1}\,\text{d}x\\ &=-\int p(x) \ln p(x)\,\text{d}x-\int p(x) \ln |A|^{-1}\,\text{d}x\\ &=\text{H}[x]+\ln |A| \end{aligned} \]Comment.
经可逆线性变换得到的随机变量的熵与原随机变量的熵相差一个常数。如果不加限制，如矩限制，直接做最大熵优化，可能是在增大 \(|A|\)，但是并没有从本质上改变分布（相差一个可逆变换）。
Exercise 1.33
Solution.
\[\begin{aligned} \text{H}[y|x] &=-\sum_i\sum_j p(x_i,y_j)\ln p(y_j|x_i)\\ &=-\sum_i\sum_j p(y_j|x_i)p(x_i)\ln p(y_j|x_i)\\ &=0 \end{aligned} \]由于 \(p(x_i)>0\)，所以 \(p(y_j|x_i)=0\) 或者 \(p(y_j|x_i)=1\)，若 \(p(y_j|x_i)>0\)，则 \(p(y_j|x_i)=1\)。由于 \(x,y\) 均为离散变量，故存在函数 \(f\) 使得 \(y=f(x)\)。进一步地，\(p(y_j)=\underset{x}{\mathbb{E}}[p(y_j|x)]>0\)，由此得到 \(y\) 的支撑集由 \(x\) 的支撑集通过函数关系确定，即 \(y\) 相对于 \(x\) 在概率意义上没有增加新的信息，亦是 \(\text{H}[y|x]=0\) 的实际含义。
Comment.
离散随机变量的假设对于导出本题结论至关重要，若两者均为连续随机变量，则有
则有 \(\mu(\{y\,|\,p(x)>0,p(y|x)\in(0,1)\})=0\)，\(p(y|x)\neq 1\) 的地方为零测集。等价地，\(\mu(\{y\,|\,p(x)>0,p(y|x)=1\})=1\)，即 \(y\) 和 \(x\) 之间以概率 1 存在函数关系。