南京大学2019年秋高级机器学习期末考试

从最近重构性或最大可分性对PCA的目标函数进行推导，假设输入数据为X，每行为一个样例，投影矩阵为W。最近重构性通过最小化样本与重构点之间的距离来优化目标函数，而最大可分性则通过最大化样本在投影空间中的方差来优化目标函数。PCA是一种降维技术，通过正交变换将高维数据映射到低维空间，减少特征数量的同时保留数据的大部分信息。特征脸（eigenface）是一种利用PCA进行降维的应用，能够输出多张特征脸用于后续任务，降维体现在主成分的数量减少。马氏距离是一种重要的距离度量，其表达形式为√((x−μ)T M−1 (x−μ))，其中M为马氏距离矩阵，通常为单位矩阵时，马氏距离等于欧氏距离。Relief算法属于过滤式特征选择方法，其主要特点包括：过滤式选择直接过滤原始数据，与后续学习器无关；包裹式选择将学习器的性能作为特征子集的评价准则；嵌入式选择将特征选择与学习器训练过程融为一体。L1正则化在回归

1. 从最近重构性或者最大可分性对PCA的目标函数推导（假设输入数据为X， 每一行为一个样例，投影矩阵为W）

答：

• 最近重构性 ：

• 最大可分性 ：

主成分析（PCA）在人脸数据集中的重要应用是特征脸（eigenface）。该方法能够生成多张特征脸结果，并应用于后续分析任务。特征脸如何辅助实现降维操作？维度的降低体现在哪些方面？

答：

https://wenku.baidu.com/view/f6a03269492fb4daa58da0116c175f0e7dd11915.html

3. 马氏距离是一种具有重要地位的距离度量指标，设马氏距离的度量矩阵为M，请推导其表达式。其中矩阵M需要满足对称性和正定性。对比而言，马氏距离相较于欧氏距离具有如下优势：首先，它考虑了数据的协方差结构，能够更好地反映数据间的实际相似性；其次，马氏距离在高维空间中表现出较好的稳健性，避免了维度灾难带来的影响。

答：

M为单位阵的时候，马氏距离等于欧式距离。

4. Relief算法归类于哪一类特征选择方法？对比三种特征选择方法的主要区别。

答： Relief算法属于过滤式特征选择方法。

采用特征筛选机制，先从原始数据中去除不符合条件的数据，然后利用筛选出的特征进行模型训练。其中，特征筛选过程与后续的学习器设计保持独立性。

包裹式选择方法：该方法主要依据其性能作为特征子集的评价标准，以确保选择的最优性。

嵌入式选择采用特征嵌入方式，将特征选择过程与学习器训练过程融为一体。在同一个优化框架下，特征选择与模型训练同步进行，最终实现特征的自动优化。在学习器训练过程中，自动完成特征选择任务。

5. 如何利用L1正则化方法在回归问题中获得最优解的稀疏性？参数λ对模型稀疏性的影响程度如何？（例如，可绘制相关图表进行分析）

答：

当\lambda增加时，解趋于稀疏。即使\lambda的值很小，惩罚项的值也不会显著，但仍会导致过拟合现象。随着\lambda的逐渐增大，过拟合现象的程度逐渐减弱。当\lambda超过某个临界值时，欠拟合现象就会出现，这是因为惩罚项变得过于庞大，导致失去了过多的特征，甚至一些重要的特征也被遗弃。

6. 图半监督学习可采用\frac{1}{2}\sum^{m}_{i = 1}\sum^{m}_{j = 1}{W_{ij}(f(x_i)-f(x_j))}^2的形式对模型施加约束，其中W为样本亲和矩阵，可简化为f^T(D-W)f。D的具体表达式是什么，其含义是什么？

答： D=diag(d_1,d_2,d_3,...,d_m)，其中d_i=\sum^{m}_{j=1}W_{ij},即d_i为W中第i行或i列元素之和（W对称)

7. PAC可学习的定义是什么，列举几种常用的假设空间。

8. 概率模型中生成式模型和判别式模型的区别？

答： 简单来说，生成式模型通过建模联合概率分布来捕捉变量之间的相互关系，而判别式模型则通过建模条件概率分布来预测结果变量与输入变量之间的关系。

9. 马尔科夫链的性质？求HMM联合分布的表达式。

答：
P(y_i|y_{i-1},y_{i-2},...,y_{1})=P(y_i|y_{i-1})
P(x_i|y_{i},y_{i-1},y_{i-2},...,y_{1})=P(x_i|y_{i})
P(x_1,...,x_n,y_1,...,y_n)=P(y_1)P(x_1|y_1)\sum^{n}_{i=2}P(y_i|y_{i-1})P(x_i|y_i)

10. Sarsa算法和Q-Learning算法在迭代过程中的区别是什么。

答：

*Sarsa是一种基于策略的算法，在选择动作时采用\epsilon贪心策略。

• Q-Learning是一种基于价值的算法，在动作选择时采用确定性策略。

基于Bellman最优等式，证明策略选择的动作被改变为当前最优动作，从而改进策略。以γ折扣奖赏为例，该方法展示了如何通过动态规划方法实现最优策略的求解。

答：
V^{\pi}(x)\leq V^{\pi{}'}(x)

[推导]： \begin{aligned} V^{\pi}(x)&\leq Q^{\pi}(x,\pi{}'(x))\ \\ &=\sum_{x{}'\in X}P_{x\rightarrow x{}'}^{\pi{}'(x)}(R_{x\rightarrow x{}'}^{\pi{}'(x)}+\gamma V^{\pi}(x{}'))\ \\ &\leq \sum_{x{}'\in X}P_{x\rightarrow x{}'}^{\pi{}'(x)}(R_{x\rightarrow x{}'}^{\pi{}'(x)}+\gamma Q^{\pi}(x{}',\pi{}'(x{}')))\ \\ &=\sum_{x{}'\in X}P_{x\rightarrow x{}'}^{\pi{}'(x)}(R_{x\rightarrow x{}'}^{\pi{}'(x)}+\gamma \sum_{x{}'\in X}P_{x{}'\rightarrow x{}'}^{\pi{}'(x{}')}(R_{x{}'\rightarrow x{}'}^{\pi{}'(x{}')}+\gamma V^{\pi}(x{}')))\ \\ &=\sum_{x{}'\in X}P_{x\rightarrow x{}'}^{\pi{}'(x)}(R_{x\rightarrow x{}'}^{\pi{}'(x)}+\gamma V^{\pi{}'}(x{}'))\ \\ &=V^{\pi{}'}(x) \end{aligned} 其中，使用了动作改变条件 Q^{\pi}(x,\pi{}'(x))\geq V^{\pi}(x) 以及状态-动作值函数 Q^{\pi}(x{}',\pi{}'(x{}'))=\sum_{x{}'\in X}P_{x{}'\rightarrow x{}'}^{\pi{}'(x{}')}(R_{x{}'\rightarrow x{}'}^{\pi{}'(x{}')}+\gamma V^{\pi}(x{}')) 于是，当前状态的最优值函数为

V^{\ast}(x)=V^{\pi{}'}(x)\geq V^{\pi}(x)

阐述基于"自顶向下"或"自底向上"方法生成一条规则的过程，如何防止每次仅选择一条"最优"文字而导致的局部最优解。

自顶向下方法：自顶向下方法是一种逐步细化的过程。为训练集中的每个属性的所有取值生成一个候选词项，采用特定的评估指标对每个候选词项进行评估，如准确率（或基尼系数、信息熵增益等）。根据候选词项的准确率、覆盖样本的数量以及属性的优先级进行选择。然后，从尚未被选中的属性中添加新的候选词项，并重复上述过程，直至所有候选词项的准确率达到100%。最终，被选中的候选词项组合形成一条规则。可以采用集束搜索（beam search）策略，每次保留若干最优候选规则。