周志华西瓜书《机器学习》习题提示——第10章_周志华机器学习考试题

习题提示

10.1：
决策树分类的边界是折线【西瓜书图4.11】，且形成凸形，而$k$近邻分类通常边界不清晰甚至没有边界。

10.2：
本题以$err$表示【西瓜书(10.2)】中的$P(err)$，贝叶斯最优分类器：$c^{\ast }=\underset{c}{\mathrm{argmax}}P(c|\mathbf{x})$，则有：
P ( c ∗ ∣ x ) ⩾ P ( c ∣ x ) e r r ∗ = 1 − P ( c ∗ ∣ x ) e r r = 1 − P ( c ∣ x )

$$\begin{align} P(c^*|\boldsymbol{x})\geqslant P(c|\boldsymbol{x}) \tag{1}\\ err*=1-P(c^*|\boldsymbol{x}) \tag{2}\\ err=1-P(c|\boldsymbol{x}) \tag{3} \end{align}$$ P(c∗∣x)⩾P(c∣x)err∗=1−P(c∗∣x)err=1−P(c∣x)​(1)(2)(3)​

由式(2)(3)有：
e r r = 1 − P ( c ∣ x ) ⩾ 1 − P ( c ∗ ∣ x ) = e r r ∗

$$\begin{align} err=1-P(c|\boldsymbol{x})\geqslant 1-P(c^*|\boldsymbol{x})=err^* \tag{4} \end{align}$$ err=1−P(c∣x)⩾1−P(c∗∣x)=err∗​(4)​
即【西瓜书(10.40)】左侧不等式得证.
$$\begin{array}{rl}err& \backsimeq 1-\sum _{c\in \mathcal{Y}}{P(c|\mathbf{x})}^2\text{（由【西瓜书(10.2)】第二行）}\\ & =1-{P(c^{\ast }|\mathbf{x})}^2-\sum _{c\ne c^{\ast }}{P(c|\mathbf{x})}^2\\ & =(1-P(c^{\ast }|\mathbf{x}))(1+P(c^{\ast }|\mathbf{x}))-\sum _{c\ne c^{\ast }}{P(c|\mathbf{x})}^2\\ & =er{r}^{\ast }(2-er{r}^{\ast })-\sum _{c\ne c^{\ast }}{P(c|\mathbf{x})}^2\end{array}\text{\hspace{1em}(5)}$$

这里我们作点数学知识准备：将不等式$a^2+b^2⩾2ab$推广到一般情形：
∵   P i 2 + P j 2 ⩾ 2 P i P j ∴   ∑ i ∑ j ( P i 2 + P j 2 ) ⩾ 2 ∑ i ∑ j P i P j ∴   n ∑ i P i 2 ⩾ ∑ i ∑ j P i P j = ( ∑ i P i ) 2

$$\begin{align} &\because\ P_i^2+P_j^2\geqslant 2P_iP_j\notag\\ &\therefore\ \sum_i\sum_j(P_i^2+P_j^2)\geqslant 2\sum_i\sum_jP_iP_j\notag\\ &\therefore\ n\sum_iP_i^2\geqslant \sum_i\sum_jP_iP_j=(\sum_iP_i)^2 \tag{6} \end{align}$$ ​∵ Pi2​+Pj2​⩾2Pi​Pj​∴ i∑​j∑​(Pi2​+Pj2​)⩾2i∑​j∑​Pi​Pj​∴ ni∑​Pi2​⩾i∑​j∑​Pi​Pj​=(i∑​Pi​)2​(6)​

在式(6)中，令：$P_i=P(c|\mathbf{x})$，（$c\in \mathcal{Y},c\ne c^{\ast }$）故$n=|\mathcal{Y}|-1$。
式(5)的第2项应用(6)有：
( ∣ Y ∣ − 1 ) ∑ c ≠ c ∗ P ( c ∣ x ) 2 ⩾ ( ∑ c ≠ c ∗ P ( c ∣ x ) ) 2

$$\begin{align} (|\mathcal{Y}|-1)\sum_{c\neq c^*}P(c|\boldsymbol{x})^2\geqslant (\sum_{c\neq c^*}P(c|\boldsymbol{x}))^2 \tag{7} \end{align}$$ (∣Y∣−1)c=c∗∑​P(c∣x)2⩾(c=c∗∑​P(c∣x))2​(7)​
由式(7)(5)整理即【西瓜书(10.40)】右侧不等式得证。

10.3：
参见8、协方差矩阵的特征值中的式 (D10)的证明。

10.4：
参见8、协方差矩阵的特征值中的式 (D11)的讨论。

注：10.3与10.4这两题都是讨论“中心化”问题。 “中心化”实际上是作平移，将坐标原点平移到“中心点”，这样，数据集就关于原点“对称”（物理质心），再求方差就简化了。

10.5：
投影变换公式是基于正交矩阵（即【西瓜书(10.15)】中$s.t.{\mathbf{W}}^{\mathrm{T}}\mathbf{W}=\mathbf{I}$）推导的，故当使用正交投影矩阵时，估值会更准确。 而非正交是现实问题的普遍现象，因此，采用非正交的方式的优势是适应范围广，缺点是损失了一定的合理性。

10.6：
这是一个实践题，理论依据参见10.6 图像压缩（图像坐标x压缩成了坐标z么？错！）。

10.7：
核化线性降维与流形学习从整体上看都是非线性变换，而且都是以线性变换为基础。 流形学习基于欧氏空间的“连续拼接”，当局部具有线性不变性，则为LLE算法， 核化线性降维是基于核空间中进行线性变换，对应于PCA降维有KPCA算法。优点就是利用线性变换使问题得到了极大简化，缺点就是寻找适合的“核”及“局部”没有通用的方法。

10.8：
短路：近邻范围指定过大时，距离很远的点，被误认为近邻；断路：近邻范围指定过小时，没有点的区域被误认为与其它区域不存在连接。处理方法是寻找一个度量“影响”的连续函数，变“局部视野”为“全局视野”，例如，【西瓜书图10.7】采用测地线距离以及【西瓜书(10.35)】采用影响概率。

10.9：
从LLE算法可知，它是对数据集 { x i } i = 1 m \{\boldsymbol{x}_i\}_{i=1}^m {xi​}i=1m​进行“批量”转换为 { z i } i = 1 m \{\boldsymbol{z}_i\}_{i=1}^m {zi​}i=1m​，但产生的点具有一一对应关系。 即对于$i$，点${\mathbf{x}}_i$对应于点${\mathbf{z}}_i$。

设新样本为${\mathbf{x}}_0$，找到其$k$近邻点及下标集$Q_0$，由【西瓜书(10.28)】计算出$w_{0j},(j\in Q_0)$，则得到${\mathbf{x}}_0$的近似点：
x ^ 0 = ∑ j ∈ Q 0 w 0 j x j

$$\begin{align} \hat{\boldsymbol{x}}_0=\sum_{j\in Q_0}w_{0j}\boldsymbol{x}_j \tag{8} \end{align}$$ x^0​=j∈Q0​∑​w0j​xj​​(8)​
该近似点对应到低维空间中：
$$\begin{array}{r}{\hat{\mathbf{z}}}_0=\sum _{j\in Q_0}{w}_{0j}{\mathbf{z}}_j\end{array}\text{\hspace{1em}(9)}$$
则可将${\hat{\mathbf{z}}}_0$作为新样本${\mathbf{x}}_0$的降维结果。

10.10：
参见10.10 度量学习（将欧氏距离推广成马氏距离）中将欧氏距离推广成马氏距离的讨论。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：周志华西瓜书《机器学习》习题提示——第9章
下一篇：11.1 子集搜索与评价（流水贪心，贪心法的优缺点）