机器学习-周志华】学习笔记-第十一章_机器学习 周志华第十一章

记录第一遍没看懂的
记录觉得有用的
其他章节：
        第一章
        第三章
        第五章
        第六章
        第七章
        第八章
        第九章
        第十章
        十一章
        十二章
        十三章
        十四章
        十五章
        十六章

特征选择

        特征选择是一个重要的"数据预处理" 过程，其一可以大为减轻维数灾难问题，二是可以降低学习任务的难度。
        第一个环节是“子集搜索”，可以逐渐增加相关特征(“前向”搜索)；可以从完整的特征集合开始，每次尝试去掉一个无关特征（"后向"搜索 ）；还可将前向与后向搜索结合起来，每一轮逐渐增加选定相关特征(这些特征在后续轮中将确定不会被去除)、同时减少无关特（“双向” 搜索）。
        第二个环节是“子集评价”，通过公式计算信息增益

        过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关
        包裹式特征选择直接把最终将要使用的学习器的性能作为特征于集的评价准则，这样性能更好但计算开销也大。
        嵌入式选择是在学习器训练过程中自动地进行了特征选择。L₁范数正则化公式为：

        使用L₁范数的好处可以通过下面的图来理解：使用范数就是为了找到一个点使得w极小，公式中${\sum }_{i=1}^m(y_i-w^T{x}_i{)}^2$其实是关于$w$的平方项，也就是一个抛物面；也就是最终w得到的点是抛物面与菱形/圆圈的交点上，可以看出，用L₁可能得到w₂项为0的点，相当于起到降维的效果。

        $L_1$问题求解，首先假设条件(11.9)：$f(x)$和他旁边的点的梯度相差不是很大，也就是$f(x)$不是太陡，没有突变点；也因此可以使用泰勒展开式。然而，由于正则项的存在，所以没有解析解，因此采用每次都朝梯度下降的方向走的方法。相当于把(11.13)当成一个标量式了，每次只求其中一个分量

        解(11.14)的具体过程如下：
$$\begin{gathered} x_{k+1}^i=arg\underset{x}{m}in\frac{L}{2}(x^i-z^i{)}^2+\lambda |x^i| \\ 平方项展开：\frac{L}{2}{x}^2-Lzx+\frac{L}{2}{z}^2+\lambda |x| \\ x>0:\frac{L}{2}{x}^2+(\lambda -Lz)x+\frac{L}{2}{z}^2\Rightarrow x^{\ast }=\frac{zL-\lambda }{L} \\ x<0:\frac{L}{2}{x}^2+(-\lambda -Lz)x+\frac{L}{2}{z}^2\Rightarrow x^{\ast }=\frac{zL+\lambda }{L} \end{gathered}$$

稀疏学习

        前面的情况都是，没有用的都是整列整列的，但实际情况时，没有用的都是分散在数据矩阵中。这样的样本的好处是：1.处理文本数据的性能较好，使大多数问题变得线性可分；2.存储高效。
        因此，本节的目的就是希望样本能够“恰当”的稀疏，让他在某些算法上有比较好的表现。那么首先需要先学习出一个“字典”，然后进行“稀疏编码”。

        采用用变量交替优化的策略来求解，首先固定$B$，利用近端梯度下降法求解${\alpha }_i$；然后固定${\alpha }_i$，利用KSVD策略求解。

        奈奎斯特采样定理：令采样频率达到模拟信号最高频率的两倍，则采样后的数字信号就保留了模拟信号的全部信息；那么假定有长度为$x$的离散信号 ，不妨假定我们以远小于奈奎斯特来样定理要求的采样率进行采样，得到长度为$n$的采样后信号$y$，即$y=\Phi x$，但由于这是一个欠定方程，因此难以求出数值解；所以假设$x=\Psi s$，那么$y=\Phi \Psi s$；如果$s$具有稀疏性,那么公式中$A=\Phi \Psi$可以类似于字典，能将信号转换为稀疏表示。
        压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。