正交匹配追踪算法(OMP)简介与详解
介绍匹配追踪算法MP、正交匹配算法OMP。附带sklearn代码
秒懂
匹配追踪算法(MP)
为了了解OMP我们先从MP开始说起。
匹配追踪最早是时频分析的分析工具,目的是要将一已知讯号拆解成由许多被称作为原子讯号的加权总和,而且企图找到与原来讯号最接近的解。
在机器学习领域,我们可以将它抽象为 X ω = Y X\omega=Y Xω=Y,其中 X X X是我们已知的向量, Y Y Y是我们要去拟合或者称为追踪的向量, MP算法的目的就是找到公式中的 ω \omega ω。MP算法采用逐步迭代的方式,每一步寻找到 X X X中与 Y Y Y内积最大的向量,将其从 Y Y Y中剔除(相减)得到 Y ′ Y' Y′(被称为残差),这样一步步迭代下去就能找到较优的近似解。
举个例子,我想要使用 x 1 = ( − 1 , 1 ) x_1=(-1,1) x1=(−1,1)和 x 2 = ( 1 , 0 ) x_2=(1,0) x2=(1,0)两个向量来拟合向量 y = ( 1 , 1 ) y=(1,1) y=(1,1),如果让我们口算,我们可以很容易地计算出 1 x 1 + 2 x 2 = y 1x_1+2x_2=y 1x1+2x2=y,那么使用MP算法呢?
-
第一步迭代:
计算 x 1 x_1 x1和 x 2 x_2 x2与 y y y的内积 m 1 = < x 1 , y > = 0 m_1=<x_1,y>=0 m1=<x1,y>=0, m 2 = < x 2 , y > = 1 m_2=<x_2,y>=1 m2=<x2,y>=1
比较绝对值发现 x 2 x_2 x2对 y y y的影响更大,因此 y ′ = y − m 2 x 2 = ( 0 , 1 ) y'=y-m_2x_2=(0,1) y′=y−m2x2=(0,1),记录 ω = ( _ , 1 ) \omega=(\_,1) ω=(_,1)。 -
第二步迭代:
计算 x 1 x_1 x1和 x 2 x_2 x2与 y ′ y' y′的内积 m 1 = < x 1 , y ′ > = 1 m_1=<x_1,y'>=1 m1=<x1,y′>=1, m 2 = < x 2 , y ′ > = 0 m_2=<x_2,y'>=0 m2=<x2,y′>=0
比较绝对值发现 x 1 x_1 x1对 y ′ y' y′的影响更大,因此 y ′ ′ = y ′ − m 1 x 1 = ( 1 , 0 ) y''=y'-m_1x_1=(1,0) y′′=y′−m1x1=(1,0),记录 ω = ( 1 , 1 ) \omega=(1,1) ω=(1,1)。 -
第三步迭代:
计算 x 1 x_1 x1和 x 2 x_2 x2与 y ′ y' y′的内积 m 1 = < x 1 , y ′ ′ > = − 1 m_1=<x_1,y''>=-1 m1=<x1,y′′>=−1, m 2 = < x 2 , y ′ ′ > = 1 m_2=<x_2,y''>=1 m2=<x2,y′′>=1
比较绝对值发现 x 1 x_1 x1与 x 2 x_2 x2对 y ′ y' y′的影响一样大,因此随便选一个 y ′ ′ ′ = y ′ ′ − m 2 x 2 = ( 0 , 0 ) y'''=y''-m_2x_2=(0,0) y′′′=y′′−m2x2=(0,0),记录 ω = ( 1 , 2 ) \omega=(1,2) ω=(1,2),得到正确答案。
but!如果随机选选到了 x 1 x_1 x1怎么办,这就可能导致出现迭代时间变长、收敛速度变慢甚至死循环等问题。于是引出正交匹配追踪算法。
正交匹配追踪算法
正交匹配追踪算法是匹配追踪算法的升级版,每一步迭代时保证剔除后的
Y
′
Y'
Y′与被剔除的向量正交,这样之后的迭代就不需要再计算已经剔除掉的向量,极大地减少了时间开销。
例如在上一节的问题中,使用
x
1
=
(
−
1
,
1
)
x_1=(-1,1)
x1=(−1,1)和
x
2
=
(
1
,
0
)
x_2=(1,0)
x2=(1,0)两个向量来拟合向量
y
=
(
1
,
1
)
y=(1,1)
y=(1,1)
-
第一步迭代:
计算 x 1 x_1 x1和 x 2 x_2 x2与 y y y的内积 m 1 = < x 1 , y > = 0 m_1=<x_1,y>=0 m1=<x1,y>=0, m 2 = < x 2 , y > = 1 m_2=<x_2,y>=1 m2=<x2,y>=1
比较绝对值发现 x 2 x_2 x2对 y y y的影响更大,因此 y ′ = y − k 1 x 2 = ( 1 − k 1 , 1 ) s . t . y ′ ⊥ x 2 y'=y-k_1x_2=(1-k_1,1)\,\,s.t. \,\,y'\perp x_2 y′=y−k1x2=(1−k1,1)s.t.y′⊥x2,解得 k 1 = 2 , y ′ = ( − 1 , 1 ) k_1=2, y'=(-1,1) k1=2,y′=(−1,1),记录 ω = ( _ , 2 ) \omega=(\_,2) ω=(_,2)。 -
第二步迭代:
由于正交性,不需要再考虑 x 2 x_2 x2,因此 y ′ ′ = y ′ − k 2 x 1 = ( − 1 − k 2 , 1 − k 2 ) s . t . y ′ ⊥ x 1 ∧ y ′ ⊥ x 2 y''=y'-k_2x_1=(-1-k_2,1-k_2)\,\,s.t. \,\,y'\perp x_1 \wedge y'\perp x_2 y′′=y′−k2x1=(−1−k2,1−k2)s.t.y′⊥x1∧y′⊥x2,解得 k 2 = 1 k_2=1 k2=1记录 ω = ( 1 , 1 ) \omega=(1,1) ω=(1,1),得到正确答案。
正交匹配追踪算法的优势可见一斑。
详解
算法流程
简单介绍已经说清楚了,即通过
X
ω
=
Y
X\omega=Y
Xω=Y中已知的
X
X
X和
Y
Y
Y来求出
ω
\omega
ω,我们将其拆开来写
ω
1
x
1
+
ω
2
x
2
+
.
.
.
+
ω
n
x
n
=
y
\omega_1x_1+\omega_2x_2 + ...+\omega_nx_n=y
ω1x1+ω2x2+...+ωnxn=y
- 第一步计算每个向量 x x x与 y y y的内积,挑选出绝对值最大的设为 x i x_i xi,令 y ′ = y − ω i x i y'=y-\omega_ix_i y′=y−ωixi, ω i \omega_i ωi满足 y ′ ⊥ x i y'\perp x_i y′⊥xi,将 y y y替换成 y ′ y' y′(即令 y = y ′ y=y' y=y′)。
- 随后,计算除 x i x_i xi之外每个向量 x x x与 y y y的内积,挑选出绝对值最大的设为 x j x_j xj,令 y ′ = y − ω j x j y'=y-\omega_jx_j y′=y−ωjxj, ω j \omega_j ωj满足 y ′ ⊥ x j ∧ y ′ ⊥ x i y'\perp x_j\wedge y'\perp x_i y′⊥xj∧y′⊥xi,将 y y y替换成 y ′ y' y′。
- 重复步骤2,值得注意的是,这里的政教关系需要用施密特正交化方法来计算。
- 求出的 ω \omega ω就是OMP算法的解。
代码实现
废话不多说,直接上sklearn
from sklearn import linear_model
def data_generate():
# 这里随机生成了一些数据
a = [[i + 1, i - 2, i + 4, i - 3] for i in range(5)]
a.extend([[i - 1, i - 2, i, i] for i in range(5)])
b = [sum(i) * 2 + 1 for i in a]
# b = [[i + random.randint(-10, 10) for _ in range(1)] for i in range(5)]
# b.extend([[i + random.randint(-10, 10) for _ in range(1)] for i in range(10, 15)])
return a, b
if __name__ == "__main__":
x, y = data_generate()
reg = linear_model.OrthogonalMatchingPursuit()
# 可以和下面这一行的标准线性回归做一个对比
# reg = linear_model.LinearRegression()
reg.fit(x, y)
for i, j in zip(x, y):
print(i, j)
print('---------------')
# 懒得再构造数据了,使用训练集预测一遍,效果。。。一般,主要是因为数据量太少了。
# 当数据量增加时,OMP可以超过标准线性回归的效果
print(reg.predict(x))
print(reg.score(x, y))
算法优劣
通过上文中的介绍可以发现
OMP算法相较于MP算法收敛快,效率高。
作为压缩感知领域的算法,可以应用在回归问题上,效果还不错。
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)