- 《机器学习》习题参考
- 叶翰嘉 詹德川
- 2880字
- 2025-03-13 17:51:07
1.4 矩阵、优化和概率分布
习题1.6 教材附录A中介绍了矩阵的性质.随机矩阵（stochastic matrix）和双随机矩阵（doubly stochastic matrix）在机器学习中经常出现，常用于运筹学、经济学、交通运输等不同领域中[6].其定义如下：
定义1.1（随机矩阵）
设矩阵X∈ℝd×d是非负矩阵，第i行第j列元素为xij.如果X满足
矩阵每行和为1.
则称矩阵X为随机矩阵（stochastic matrix）.如果X还满足
矩阵每列和为1.
则称矩阵X为双随机矩阵.
对于双随机矩阵X∈ℝd×d，回答以下问题：
1.定义矩阵X的统计量
试证明：H（X）≤dlogd.
2.矩阵谱半径（spectral radius）的定义为特征值取模后的最大值：
请证明X的谱半径ρ（X）=1，且1是X的特征值.
证明过程中可基于Perron-Frobenius定理.
定理1.1（Perron-Frobenius定理）
对于非负矩阵X有
解答
1.证明 考虑到函数f（x）=-xlogx是凹函数，即对于t∈[0，1]满足f（tx1+（1-t）x2）≥tf（x1）+（1-t）f（x2），由Jensen不等式（教材式（12.4）），有
为了使用Jensen不等式，在第一个等式中引入了d2因子，使求和过程中权重之和为1.最后的等式应用了双随机矩阵X的性质
□
习题注释 本小题考查Jensen不等式的应用.Jensen不等式在机器学习的很多定理中出现，用于针对凸函数或凹函数的结果进行放缩，需要熟练掌握.矩阵统计量H的定义与信息熵（information entropy）一致，在第4章决策树习题4.2中将证明类似的性质.
本小题的证明过程是从夹逼的思路入手，通过证明左右均为1从而推导出谱半径为1.
2.证明 由关于非负矩阵的广义Perron-Frobenius定理可知，对于非负矩阵X有
因为X是双随机矩阵，因此有ρ（X）=1.同时注意到X·1=1·1，因此1是X的特征值.□
1表示取值全为1的向量.
习题1.7 矩阵范数将向量范数的定义推广至ℝm×n空间.和向量的Lp范数类似，矩阵的Lp范数也与矩阵中各分量的信息密切相关.令aij是矩阵A∈ℝm×n的第i行第j列的分量，则
1）p=1时，
2）p=2时，此时定义的范数又称为Frobenius范数（简称F范数，参考教材附录A.1），记作
在讨论矩阵范数时，也关注其自相容性.
定义1.2（自相容性）
如果对于可乘的有限维矩阵A和B，‖AB‖≤|A‖‖B‖成立，则称矩阵范数 · 是自相容的‖.‖
请回答以下问题：
1.对于任意的正交矩阵U∈ℝm×m，V∈ℝn×n，证明
2.一般的矩阵范数并不具有自相容性，定义矩阵范数
，证明其不是自相容的矩阵范数.
3.证明矩阵的F范数是自相容的.
解答
1.证明
其中式（1.14）到式（1.15）的变换利用了正交矩阵的性质，即VV⊥=In，UU⊥=Im，其中In和Im分别为大小为n×n与m×m的单位矩阵.而式（1.16）中等号成立的原因是利用了矩阵的迹的性质，即tr（AB）=tr（BA）.□
2.证明 令
则有
考虑该范数，此时‖AB‖=2，‖A‖|B‖=1，不满足自相容条件.因此矩阵范数
不是自相容的矩阵范数.□
3.要证明矩阵的F范数是自相容的，首先证明Cauchy不等式.
定理1.2（ Cauchy不等式）
设a，b∈ℝn，则有
当且仅当a与b线性相关时，取等号.
证明 设a，b∈ℝn，下面分两种情况讨论.
如果a，b线性相关，则存在k∈ℝ，满足a=kb，将结果代入式（1.21），得到
如果a，b线性无关，则定义v∈ℝn，满足
，因此v与b正交.将a的范数平方展开，由于v与b正交，有
类似勾股定理.
考虑范数非负性，有
基于向量的Cauchy不等式，下面证明矩阵的F范数是自相容的.
证明 设A∈ℝm×n，B∈ℝn×p，则
在线性无关情况下证明Cauchy不等式时，用到的技巧是Gram-Schmidt正交化，将其应用到列满秩矩阵中，就得到了矩阵的QR分解，这一技巧也被广泛地应用于以最小二乘为目标函数的线性回归（linear regression）问题求解中.
其中不等号利用了上述Cauchy不等式的结论.□
除此以外，矩阵的自相容性也可通过如下方式证明.
证明
其中第二个等号利用了矩阵迹的定义.要证明上述结论，则只需证明
注意到（A⊥A）和（BB⊥）都是对称半正定矩阵.因此，它们可以被对角化，表示为
其中U，V是正交矩阵，且ΣA，ΣB是具有对应矩阵（A⊥A）和（BB⊥）非负特征值的对角矩阵.再次使用矩阵迹的定义，可以将式（1.27）的左式改写为
具有非负对角值的对角矩阵D应当具有以下性质：
1）在任何D的正交变换下，得到的矩阵都具有非负对角值.
性质2的证明可以通过对矩阵迹的计算公式进行展开得到，其中tr（MD）的每一项均包含在tr（M）·tr（D）中.
2）如果M是具有非负对角值的方阵，则tr（MD）≤tr（M）·tr（D）.综合以上两个性质，可知
习题注释 易证Cauchy不等式可以推广到矩阵形式.利用类似的方式，本题中Cauchy不等式可推广到如下矩阵的形式（首先定义矩阵Frobenius内积）.
定理1.3（矩阵Frobenius内积）
设A，B∈ℝm×n，其Frobenius内积定义为
Frobenius内积是对矩阵逐分量相乘再求和，因此满足内积的定义.类似于向量内积，矩阵内积也可以表示矩阵和矩阵之间的夹角.
定理1.4（矩阵范数的Cauchy不等式）
设A，B∈ℝm×n，则有
其中|〈A，B〉|是Frobenius内积.当且仅当A和B线性相关时，等号成立.
习题1.8 对于矩阵A∈ℝm×d，rank（A）表示矩阵A的秩.请问rank（A⊥A）与rank（AA⊥），rank（A），rank（A⊥）以及d，m之间有何关系？
解答
矩阵的秩之间的关系为
证明 根据矩阵的秩的定义，可知rank（A）=rank（A⊥）.构造两个线性方程组：
利用矩阵乘法的结合律，可以得到A（A⊥x）=0.所以A⊥x=0的解均为AA⊥x=0的解.将式（1.35）两边同时左乘x⊥，可得
AA⊥x=0的解均为A⊥x=0的解.因此，AA⊥x=0和A⊥x=0具有相同的解空间，rank（AA⊥）=rank（A⊥）.同理，可以证明rank（A⊥A）=rank（A），再结合rank（A）=rank（A⊥），式（1.33）得证.此外，由于rank（A）≤min（m，d），因此rank（A⊥A）≤min（m，d）.□
本题矩阵的性质在习题10.3对主成分分析（PCA）的讨论中有进一步应用.
习题1.9 教材附录C介绍了常见的概率分布.给定随机变量X的概率密度函数如下：
1.请计算随机变量X的累积分布函数（Cumulative Distribution Function，CDF）FX（x）.
2.随机变量Y定义为Y=1/X，求随机变量Y对应的概率密度函数fY（y）.
3.试证明，对于非负随机变量Z，如下两种计算期望的公式是等价的：
同时，请分别利用上述两种期望公式计算随机变量X和Y的期望，并验证该结论.
解答
1.随机变量X的累积分布函数FX（x）定义为
依式（1.40）可得
2.根据式（1.40），有下式成立：
从本题的分析可以看出，即使已知随机变量之间的映射关系，其概率密度分布并不具备相同的映射关系，而需要通过累积分布函数进行推导.
对两边求导，可得
依据本小题的结论，求解概率密度函数时可考虑借助累积分布函数，再进行求导.
因此，随机变量Y对应的概率密度函数fY（y）为
3.证明
易见式（1.38）和式（1.39）等价.□
由上述结论可知，
使用式（1.39）计算E[Y]：
由于式（1.46）第二项涉及了lny在y为∞时的取值，因此E[Y]不存在.
习题注释 概率密度函数的估计是机器学习后续内容中构造概率模型（probabilistic model）的重要一环.本题中对期望性质的证明技巧也可以辅助推导马尔可夫不等式（Markov Inequality），在机器学习理论推导中有广泛应用[7].对于第3小题的结论，请读者自行验证。
习题1.10 设向量x服从均值为0，协方差为Σ的正态分布，即x～N（0，Σ），给定半正定矩阵M，定义
，试证明
‖x‖M定义了在度量M下的一种范数，本题证明了随机变量在该空间中范数的上界.
证明 首先对
进行变换，通过矩阵迹的性质，得到
因此有
由于
是凹函数，式（1.48）利用了Jensen不等式.□
x⊥Mx=tr（x⊥Mx）成立是因为x⊥Mx是标量，与自身的迹相等.再进一步利用tr（AB）=tr（BA）的性质进行变换.