机器学习(二十九) 稀疏表示与字典学习(LASSO算法、KSVD算法、奇异值分解)
29.1 稀疏表示
特征选择考虑的问题是特征具有"稀疏性"，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列，模型的训练过程仅需在较小的矩阵上进行，学习任务的难度会有所降低，涉及的计算和存储开销会减少，学得模型的可解释性也会提高，因为模型所建立的"输入-输出"关系会更清晰。
现在考虑另一种稀疏性：D所对应的矩阵中存在很多零元素，但这些零元素并不是以整列、整行形式存在的。例如在文档分类任务中，通常将每个文档看作一个样本，也就是说，数据集矩阵的每行是一个文档，每列是一个字(词)，每个元素是某字(词)在此文档中出现的频率或次数。那么，这个矩阵有多少列呢？以汉语为例，即便仅考虑《现代汉语常用字表》中的汉字，此矩阵也有3500多列。然而，相当多的字是不出现在这个文档中的，所以矩阵的每一行都有大量的零元素。
当样本具有这样的稀疏表达形式时，对学习任务来说会有不少好处，例如线性支持向量机之所以能在文本数据上有很好的性能，正是由于文本数据在使用上述的字频表示后具有高度的稀疏性，使大多数问题变得线性可分。同时，稀疏样本并不会造成存储上的巨大负担，因为稀疏矩阵已有很多高效的存储方法。
29.2 字典学习
为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，通常称为"字典学习"(dictionary learning)，"稀疏编码"(sparse coding)。"字典学习"侧重于学得字典的过程，"稀疏编码"侧重于对样本进行稀疏表达的过程，两者通常是在同一个优化求解过程中完成。
29.2.1 优化目标
给定数据集{x1, x2, ..., xm}，字典学习最简单的优化方式为
<字典学习优化目标>
其中，样本xi∈Rd，B∈R(d×k)为字典矩阵，k为字典的词汇量(通常由用户指定)，ai∈Rk是样本xi的稀疏表示。第一项是希望Bai能很好地重构xi，第二项是希望ai尽量稀疏。
受LASSO的启发，可采用变量交替优化的策略进行求解：
第一步，先固定字典矩阵B，若将<字典学习优化目标>表达式按分量展开，可参照LASSO的解法求解如下表达式，为每个样本xi找到相应的ai：
min(ai) ||xi - Bai||^2 + λ||ai||1
令Bai=x'i 是对xi的重构，则 ||xi - Bai||^2 = Σ(j=1,d)(xij - x'ij)^2
即 最小化各维度重构误差的平方和。
||ai||1 = Σ(l=1,k)|ail|
通过L1正则化约束 ai 的稀疏性，促使尽可能多的 ail 为零。
<字典学习优化目标>按分量展开的表达式对应于LASSO回归的标准形式：
min(β) ||y-Xβ||^2 + λ||β||1
y↔xi (目标向量，相当于每个"样本"的目标值yj对应xi的每一个字xij)
X↔B (样本集合↔字典设计矩阵，相当于字典B的每个字对应X的一个"样本"，具有k个特征)
β↔ai (待求系数向量↔xi的稀疏表示）
29.2.2 LASSO解法求解样本的稀疏表示
如下通过具体实例演示先固定字典矩阵B，采用LASSO解法求解字典学习中样本的稀疏表示：
实例数据设置：
样本：xi = [2, 3]ᵀ
字典矩阵：B =
样本 xi 稀疏表示：ai = [a1, a2, a3]ᵀ
正则化系数：λ = 0.5
代入 min(ai) ||xi - Bai||^2 + λ||ai||1 得：
min(a1,a2,a3) (2-a1-a3)^2 + (3-a2-a3)^2 + 0.5(|a1|+|a2|+|a3|)
步骤1. 固定a2, a3，优化 a1
即 min(a1) (2-a1-a3)^2 + 0.5|a1|
对 a1 求导并等于0，得
-2(2−a1−a3)+0.5⋅sign(a1)=0
-2(2−a3)+2a1+0.5⋅sign(a1)=0
根据LASSO求解法的理论，a1解为：=SoftThreshold(2−a3, 0.25)
步骤2. 固定a1, a3，优化 a2
即 min(a2) (3-a2-a3)^2 + 0.5|a2|
同理，a2解为：=SoftThreshold(3−a3, 0.25)
步骤3. 固定a1, a2，优化 a3
即 min(a3) (2-a1-a3)^2 + (3-a2-a3)^2 + 0.5|a3|
对 a3 求导并等于0，得
2(a1+a2)−10+4a3+0.5⋅sign(a3)=0
a3解为：=SoftThreshold[ (10-2(a1+a2))/4, 0.5/4] = SoftThreshold(2.5-0.5(a1+a2), 0.125)
LASSO 闭式解：
SoftThreshold(z,γ) = z-γ if z>γ
SoftThreshold(z,γ) = 0 if |z|≤γ
SoftThreshold(z,γ) = z+γ if z<-γ
初始化 a1=a2=a3=0，分别代入a1, a2, a3的解，根据LASSO闭式解进行求解并依次迭代，可得
最终收敛得到稀疏表示：ai=[a1, a2, a3]=[0, 0.5, 2]ᵀ
正则化项：0.5(∣0∣+∣0.5∣+∣2.0∣)=0.5×2.5=1.25
重构验证：
B1ai = 1⋅0+0⋅0.5+1⋅2.0=2.0 (第一维)
B2ai = 0⋅0+1⋅0.5+1⋅2.0=2.5 (第二维，与原始 xi=[2,3]ᵀ存在误差，因正则化约束)
以上过程完整体现了LASSO的求解逻辑：每一步优化某个样本稀疏表示的单个分量，利用LASSO闭式解处理重构误差与L1正则化项，通过迭代更新直至所有分量收敛，最终得到满足重构误差与稀疏性之间平衡的最优稀疏表示ai。
29.2.3 KSVD解法逐列更新字典矩阵
第二步，以 ai 为初值更新字典矩阵B，此时可将<字典学习优化目标>表达式写为
min(B) (||X - BA||F)^2
其中X=(x1, x2, ..., xm)∈R(d×m)，A=(a1, a2, ..., am)∈R(k×m)
<备注：R(行数×列数)，即X中的样本xi、A中的稀疏表示ai 均对应列向量>。
‖·‖F 是矩阵的Frobenius范数
<矩阵的Frobenius范数记为||A||F，是衡量矩阵整体大小的一种重要范数 :
||A||F = √Σ(i=1,m)Σ(j=1,n)|aij|^2
若将矩阵视为在欧几里得空间中被展平的长向量，其Frobenius范数等价于此长向量的L2范数。
可通过Python求得矩阵A的Frobenius范数 : frobenius_norm = np.linalg.norm(A, 'fro')
Frobenius范数尤其在量子力学中有广泛应用。
>
此表达式有多种求解方法，常用的有基于逐列更新策略的KSVD[Aharon et al.,2006]：
令bi表示字典矩阵B的第i列，ai表示稀疏矩阵A的第i行 <注意 : biai得到的是d×m矩阵 (秩1矩阵)>
min(B) ||X - BA||F^2 = min(bi) ||X - Σ(j=1,k)bjaj||F^2
= min(bi) ||(X - Σ(j≠i)bjaj) - biai||F^2
= min(bi) ||Ei - biai||F^2 <Ei固定表达式>
在更新字典矩阵B的第i列时，其他各列都是固定的，因此Ei是固定的，所以最小化<Ei固定表达式> 求解 bi 原则上只需对 Ei 进行奇异值分解 -- 取得最大奇异值所对应的正交向量。
29.2.4 奇异值分解(SVD)求解字典矩阵B第i列
如下通过具体实例演示采用 KSVD 解法，并通过奇异值分解(SVD) 求解字典矩阵B第i列的过程 :
1. 设定初始参数与数据：
. 样本维度：d=3 (每个样本xi∈R³)
. 字典词汇量：k=2 (字典矩阵B∈R³ˣ²)
. 样本数量：m=2 (样本矩阵X∈R³ˣ²)
. 目标：更新字典矩阵B的第1列，固定第2列
初始化字典矩阵 B⁰ (d×k) =
[[1, 0],
[0, 1],
[0, 0]]
#b₁ #b₂
根据第一步得到稀疏矩阵 A⁰ (k×m) =
[[2, 0], # a₁
[0, 3]] # a₂
样本矩阵 X 近似 B⁰ @ A⁰ =
[[2, 0],
[0, 3],
[0, 0]]
2. 计算 Ei = X - Σ(j≠i)bjaj
= X - b₂·a₂ = [[2,0],[0,3],[0,0]] - [[0,0],[0,3],[0,0]] = [[2,0],[0,0],[0,0]] (3×2矩阵)
3. 对 Ei 进行奇异值分解 (SVD) :
Ei = UΣVᵀ
U (d×d) : 左奇异向量矩阵，列向量正交；
Σ (d×m) : 奇异值对角矩阵，主对角线元素 σ1≥σ2≥⋯≥0；
V (m×m) : 右奇异向量矩阵，列向量正交。
奇异值 σi 是 EiᵀEi 和 EiEiᵀ 的特征值的平方根。
计算 EiᵀEi =
[[4, 0],
[0, 0]]
特征值：λ₁=4 (对应特征向量 v₁=[1,0]ᵀ)，λ₂=0 (对应特征向量 v₂=[0,1]ᵀ)
奇异值：σ1=√4=2，σ2=0
右奇异向量矩阵：V = [[1,0],[0,1]] (m×m)
计算 EiEiᵀ =
[[4, 0, 0],
[0, 0, 0],
[0, 0, 0]]
特征值：λ₁=4 (对应特征向量 u₁=[1,0,0]ᵀ)，λ₂=λ₃=0 (对应特征向量 u₂=[0,1,0]ᵀ、u₃=[0,0,1]ᵀ)
奇异值：σ1=√4=2，σ2=0，σ3=0
左奇异向量矩阵：U = [[1,0,0],[0,1,0],[0,0,1]] (d×d)
奇异值矩阵 Σ 的维度必须与 Ei 匹配 (3×2矩阵) : Σ =
[[σ1, 0],
[0, σ2],
[0, 0]] = [[2, 0],[0,0],[0,0]]
bi (d×1)、ai (1×m)，biai是秩1矩阵。根据矩阵低秩近似理论，Frobenius范数下，优化目标 min(bi) ||Ei - biai||F^2 其秩1矩阵 biai 最佳近似 由Ei的SVD前1项给出，即：
秩1矩阵 biai 最佳近似为 : σ1u1v1ᵀ
σ1是最大奇异值λ*
u1 (d×1) : U的第1列 (最大左奇异向量)
v1 (m×1) : V的第1列 (最大右奇异向量)
此时：bi=σ1u1, ai=v1ᵀ 或 bi=u1, ai=σ1v1ᵀ
若需强调 bi 的缩放，可选择 bi=σ1u1；若需保持 ai 的原始方向，可选择 ai=σ1v1ᵀ。
迭代执行上述两步，最终可求得字典矩阵B和每个样本xi的稀疏表示αi。
在上述字典学习过程中，用户能通过设置词汇量k的大小控制字典的规模，从而影响样本的稀疏程度。
原文地址：https://blog.csdn.net/FluxMelodySun/article/details/159733109
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！