首页 > 其他分享 >ch11 特征选择与稀疏学习

ch11 特征选择与稀疏学习

时间:2024-06-21 20:55:19浏览次数:29  
标签:ch11 frac min 特征选择 nabla 稀疏 子集 lambda

子集选择与评价

缓解维度灾难的另一种重要方法是进行特征筛选,同时它也能降低学习任务的难度,只留下关键特征。

对当前学习任务有用的属性称为“相关特征”,而对当前学习任务没有用的属性称为“无关特征”,包含信息能被其他特征表示的属性称为“冗余特征”。

如果想要从原始特征集中选择出一个子集,那么就是一个特征选择问题。特征选择通常包含以下两个环节

  • 子集搜索:搜索最优特征子集
    暴力搜索会遇见组合爆炸问题,所以需要一些启发式方法,如贪心法(前向、后向、双向)

  • 子集评价:评价特征子集的好坏
    评价指标有很多,如信息增益、信息增益比、基尼指数、方差、相关系数等

常见的特征选择方法有:过滤法、包裹法、嵌入法

过滤法

先对数据集进行特征选择,再用特征子集训练模型,特征选择过程与学习过程无关

著名的算法有:Relief、Relief-F

Relief 设计了一个相关统计量用于度量特征的重要性

相关统计量:对于每一个样本点\(x_i\),寻找与其最近邻的样本点\(x_{i,nh}\)(同类)和\(x_{i,nm}\)(异类),于是我们可以定义如下的相关统计量

\[\delta^j = \sum_{i=1}^m - \text{diff}(x_{i,j}, x_{i,nh,j})^2 + \text{diff}(x_{i,j}, x_{i,nm,j})^2 \]

那么最终得到的一个统计量向量越大,说明子集选择的越好,分类性能越强

包裹法

直接利用学习器的性能来评价特征子集的好坏,通常效果更好,但计算开销也更大

著名的算法有:LVW 框架,在特征选择的过程中使用了随机算法

嵌入法

将特征选择过程与学习过程融为一体,直接在学习器上进行特征选择

著名的算法有: L1 正则化、L2 正则化

对于线性回归算法,我们通常认为有这样一条直线可以拟合数据

\[Y = XW \]

当\(X\)不可逆时,我们使用最小二乘法,即

\[\min \| Y - XW \|_2^2 \]

\[W = (X^T X)^{-1} X^T Y \]

当\(X\)列不满秩时,即\(X^T X\)不可逆,即样本特征多于样本数,此时我们可以使用正则化

\[\min \| Y - XW \|_2^2 + \lambda \| W \|_2^2 \]

\[W = (X^T X + \lambda I)^{-1} X^T Y \]

保证了\(X^T X + \lambda I\)可逆,从而解决了多重共线性问题

这是一种罚函数法,即在目标函数中加入了一个罚函数,使得优化问题变得更加复杂

最直观的罚函数是 L0 范数,即非零元素的个数,但是 L0 范数是一个非凸函数,所以我们通常使用 L1 范数,L1 通常能获得稀疏解,即有些特征的权重为 0

img

因此可以说,L1 正则化是一种特征选择方法

L1 正则化的求解方法

可以使用近端梯度下降法(Proximal Gradient Descent),对于优化目标

\[\min_x f(x) + \lambda \| x \|_1 \]

如果满足 Lipschitz 连续梯度条件,即

\[\exist L > 0, \quad \| \nabla f(x) - \nabla f(y) \|_2 \leq L \| x - y \|_2, \quad \forall x, y \]

那么在\(x_k\)处对目标函数进行二阶泰勒展开,有

\[f(x) \approx f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{L}{2} \| x - x_k \|_2^2 \\ = \frac{L}{2} \| x - (x_k - \frac{1}{L} \nabla f(x_k)) \|_2^2 + \text{const} \]

? 那么我们可以得到

\[x_{k+1} = \arg \min_x \frac{L}{2} \| x - (x_k - \frac{1}{L} \nabla f(x_k)) \|_2^2 \\ \Rightarrow x_{k+1} = x_k - \frac{1}{L} \nabla f(x_k) \]

最小值可以通过如上的迭代方式求解,即梯度下降法是对 二次拟合函数的近似

那么应用到 L1 正则化的问题上,我们可以得到

\[x_{k+1} = \arg \min_x f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{L}{2} \| x - x_k \|_2^2 + \lambda \| x \|_1 \\ \Rightarrow x_{k+1} = \arg \min_x \frac{L}{2} \| x - (x_k - \frac{1}{L} \nabla f(x_k)) \|_2^2 + \lambda \| x \|_1 \]

这个问题不存在交叉项,因此可以使用坐标轴下降法(Coordinate Descent)求解,即

\[x_i^{(k+1)} = \arg \min_{x_i} \frac{L}{2} (x_i - z_i^{k})^2 + \lambda |x_i| \]

求导数,令导数为 0,即可得到

\[x_i^{(k+1)} = \begin{cases} z_i^{(k)} - \frac{\lambda}{L}, & z_i^{(k)} > \frac{\lambda}{L} \\ 0, & |z_i^{(k)}| \leq \frac{\lambda}{L} \\ z_i^{(k)} + \frac{\lambda}{L}, & z_i^{(k)} < -\frac{\lambda}{L} \end{cases} \]

L1 正则化的求解方法

标签:ch11,frac,min,特征选择,nabla,稀疏,子集,lambda
From: https://www.cnblogs.com/Blackteaxx/p/18261316

相关文章

  • 基于蝗虫优化的KNN分类特征选择算法的matlab仿真
    1.程序功能描述      基于蝗虫优化的KNN分类特征选择算法。使用蝗虫优化算法,选择最佳的特征,进行KNN分类,从而提高KNN分类的精度。 2.测试软件版本以及运行结果展示MATLAB2022a版本运行   3.核心程序[idx1,~,idx2]=dividerand(rows,0.8,0,0.2);Ptrain......
  • 基于稀疏矩阵方法的剪枝压缩模型方案总结
    1.简介1.1目的在过去的一段时间里,对基于剪枝的模型压缩的算法进行了一系列的实现和实验,特别有引入的稀疏矩阵的方法实现了对模型大小的压缩,以及在部分环节中实现了模型前向算法的加速效果,但是总体上模型加速效果不理想。所以本文档针对这些实验结果进行分析和总结。1.2范围......
  • Python俄罗斯方块可操纵卷积分类 | 稀疏辨识算法 | 微分方程神经求解器
    ......
  • 【SAR图像变换检测】双字典交叉稀疏表示SAR图像变化检测(像素个数 误差率)【含Matlab源
    ......
  • SoftMax 的困境:在稀疏性和多模态之间左右为难
    SoftMax是现代机器学习算法中无处不在的组成部分。它将输入向量映射到概率单纯形,并通过将概率质量集中在较大的条目上,来重新加权输入。然而,作为Argmax函数的平滑近似,SoftMax将大量的概率质量分配给其他剩余的条目,导致可解释性差和噪声。虽然稀疏性可以通过一系列SoftMa......
  • colmap大场景稀疏重建记录:部分照片畸变导致sfm生成的稀疏点云扭曲
    一、问题如题,要进行一个大场景的3DGS重建,数据集来自于某工地现场(大约3000张照片),数据集拍摄于同一个相机,按照国际惯例,3DGS需要输入一个稀疏点云,所以首先利用colmap进行稀疏重建。进行特征提取,特征匹配(colmap官网建议1000-10000张图的特征匹配使用vocabtree),稀疏重建以后,发现场......
  • 通过强化学习彻底改变大型数据集特征选择
    文章目录一、说明二、强化学习:特征选择的马尔可夫决策问题三、用于使用强化学习进行特征选择的python库3.1.数据预处理3.2.安装和导入FSRLearning库四、结论和参考文献一、说明  了解强化学习如何改变机器学习模型的特征选择。通过实际示例和专用的Python......
  • 高度向稀疏的毫米波成像方法
    分析:高度向稀疏的采样数据是整行缺失的,每一列上都缺失了大量数据,这可能造成高度向的混叠现象,但是每一行上是没有缺失数据的,这说明方位向应该是不会出现混叠现象。考虑到上述现象,对于三维成像,可不可以先实现距离-方位向的二维成像,而后再实现高度向的聚焦,进而实现三维成像。想......
  • 基于对比稀疏扰动技术的时间序列解释框架 ContraLSP
    开篇近日,由阿里云计算平台大数据基础工程技术团队主导,与南京大学、宾夕法尼亚州立大学、清华大学等高校合作,解释时间序列预测模型的论文《ExplainingTimeSeriesviaContrastiveandLocallySparsePerturbations》被机器学习领域顶会ICLR2024接收。该论文提出了一种创新的基......
  • 基于稀疏辅助信号平滑的心电信号降噪方法(Matlab R2021B)
    基于形态成分分析理论(MCA)的稀疏辅助信号分解方法是由信号的形态多样性来分解信号中添加性的混合信号成分,它最早被应用在图像处理领域,后来被引入到一维信号的处理中。在基于MCA稀疏辅助的信号分析模型中,总变差方法TV是其中一个原型,稀疏辅助平滑方法结合并统一了传统的LTI低通滤......