1.1.9. Orthogonal Matching Pursuit (OMP)

一、简介

这是sklearn对OMP的所有描述，对我来说，显得有些晦涩难懂。事实上，想要很好的理解这部分内容，我们需要一定的基础和相应的数学功底。

OMP本质上，涉及到了字典学习和稀疏表示这一领域。我也是在复习了西瓜书上相关部分的内容和结合了之前关于线性模型求解的数学推导与优化后，才堪堪理解。

这里我先给出一篇我学习这部分内容时，看得一篇文章，这位大佬做了很多、很详细的数学上的讲解，虽然我看不太懂，但我大受震撼。

二、结合多种算法理解OMP

在这里，我们暂时先抛弃各种算法之间的优劣和针对不同数据的泛化性能的区别，仅讨论模型的数学属性和之间的相似性。

2.1梯度下降体系和最小角回归体系（铺垫1）

求解线性回归的模型当中，最核心的思想是逼近。有两种广为人知的

1. 梯度下降
2. 坐标下降（前向梯度）

在我的理解中，坐标下降和前向梯度十分相似，但我还没弄清楚它们之间具体的关系

事实上，他们的思想都是不断的选择不同特征的线性组合，最后向目标逼近。即，将目标表示为不同特征的线性组合加上残差的形式。
$y=\hat{y}+\epsilon ={\omega }_0{x}_0+{\omega }_1{x}_1+{\omega }_2{x}_2+...+{\omega }_n{x}_n$

只不过，在梯度下降中，我们选择的梯度，都是所有特征之间的线性组合；而在坐标下降（前向梯度）中，我们一次只选择一个维度（特征），并在该维度上下降。

这两种算法在面对大量数据集时性能都会显著降低（梯度下降每一次求解梯度都要进行大量的计算，坐标下降每一次只能在一个维度上下降）。于是，我们有了第一种优化方式那就是减少迭代次数。（当然不是简单的提高学习率啦）

1. 最速下降 to 共轭梯度下降
2. 前向选择 to 最小角回归LARs

先说最速下降：在梯度下降中，我们每一步的步长是学习率决定的。但是为了减少迭代次数（防止函数在同一方向或相近方向上走好多步），我们选择在当前梯度方向上一次走到底（也就是该方向上的偏导为0），从而一步到位。这样的走法，决定了每次下降的方向和上一次都是正交的。

补：写到后面才发现，坐标选择（前向梯度）本身就具有正交属性，不过它的正交属性是和最速下降相类似的

对最速下降近一步优化：在最速下降中，我们只能保证“每次下降的方向和上一次都是正交的”，因此放眼全局，我们仍然会在相同方向上走很多步。所以，我们通过一定的数学手段，让每一次的下降方向和之前所有的下降方向都正交，那么，对于n维函数（n个特征），我们只需要n步就能解决问题。

同理，前向选择也类似：前向选择每次选择一个维度做投影并计算残差，然后再对下一个维度做投影，这样，n步也能解决问题。（1.前向选择是根据最小残差选择维度的，即每一步让当前残差最小「贪心」；2.前向选择很粗暴，误差很大，但这不是我们改在这里讨论的问题；3.这里在不同维度上投影，说明每一步的迭代方向也是正交的）

最后是LARs 最小角回归：最小角回归是前向选择和前向梯度的优化，它既在每步走到底（这里的底不是偏导为0，而是遇到一个和到残差的角度相等的其他维度（角平分线）），也做了不同维度间的线性组合，所以该算法十分优秀。

2.2字典学习和稀疏表示（铺垫2）

显然，如何对特征进行线性组合是梯度下降体系和最小角回归体系最大的区别。于是，我们想有一种方法，能对特征之间进行一种独特的线性组合。

这种线性组合：

• 不能像梯度一样那么难计算
• 不能像坐标一样那么简单（单个维度）
• 它的组合不能太草率（想LARs一样等权重的组合）

于是我们想到了字典学习和稀疏表示。我们选择通过用一种学习算法同时优化出一个“字典”和一种“表达方式”使得每一个目标能用字典里的单词表示（因为是稀疏字典，所以每个单词是较少的特征的线性组合；这种由稀疏“单词”构成的表达叫做稀疏表达）
[该算法不在这里展示了，有兴趣的同学可以参考一下西瓜书的第11章]

2.3MP and OMP

于是根据算法学成的“成熟的”字典，我们将字典中的每个词视为一个维度（新特征），并在这些特征上进行坐标下降（前向梯度），这就是所谓的Matching Pursuit匹配追踪！！！

这样是不是很好理解了。

相应的，OMP正交匹配追踪就是利用和“前向选择”和“共轭梯度下降”的思想对MP进行优化。我们不满足上一步与下一步之间的“局部正交”属性，我们希望算法具有“全局正交”的属性。这就是OMP存在的目的。

最后

以上就是羞涩小蝴蝶为你收集整理的1.1.9. Orthogonal Matching Pursuit (OMP)（正交匹配追踪）1.1.9. Orthogonal Matching Pursuit (OMP)的全部内容，希望文章能够帮你解决1.1.9. Orthogonal Matching Pursuit (OMP)（正交匹配追踪）1.1.9. Orthogonal Matching Pursuit (OMP)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。