稀松字典学习

✍ dations ◷ 2025-07-24 04:15:44 #机器学习

稀松字典学习是一种表征学习方法,其目的在于找出一组基本元素让输入讯号映射到这组基本元素时具有稀松表达式。我们称这些基本元素为“原子”,这些原子的组合则为“字典”。字典里的“原子“并不需要满足正交这一特性,且往往它们会是过完备的生成集合。过多的原子除了可以让我们在叙述一个讯号的时候可以由很多种表达式,同时也提升了整个表达式的稀松性,让我们可以以较简单的表达式来诠释讯号。

稀松字典学习最主要应用在压缩感知及讯号还原上。在压缩感知上,当你的讯号具有稀松或者接近稀松特质时,那么只需要对讯号进行几次的随机取样就可以把高维度的讯号描述出来。但在现实世界中,并不是全部讯号都具有稀松这一特性,所以我们需要把找出这些讯号的稀松表达式,转换方式有很多种,根据不同的讯号有不同的转换方式。当高维度的讯号转换至稀松讯号是,那么就可以透过少次数的线性取样,并利用一些还原算法如:基追踪(Basis Pursuit)、CoSaMP、正交匹配追踪(Orthogonal Matching Pursuit)等方法来对讯号进行还原。

在这整个过程中,关键在于如何找到一个转换方式把讯号转换到具有稀松表达式的域内,也就是如何建立一个字典,让讯号投影在这个字典上时具有稀松表达式。而稀松字典学习就是利用学习的方式帮我们找出这个转换方法,即稀松字典。稀松字典学习的兴起是基于在讯号处理中,如何使用较少的元素来叙述一个讯号。在这之前,普遍上大家还是使用傅立叶转换(Fourier Transform)及小波转换(Wavelet Transform)。不过在某一些情境下,使用透过字典学习得到的字典来进行转换,能有效的提高讯号的稀松性。高稀松性意味着讯号的可压缩性越高,因此稀松字典学习也被应用在资料分解、压缩和分析。

假设输入讯号集合 X = , x i R d {\displaystyle X=,x_{i}\in \mathbb {R} ^{d}} ,我们希望找到一个字典 D R d × n : D = {\displaystyle \mathbf {D} \in \mathbb {R} ^{d\times n}:D=} 和一个表达式 R = , r i R n {\displaystyle R=,r_{i}\in \mathbb {R} ^{n}} ,让 X D R F 2 {\displaystyle \|X-\mathbf {D} R\|_{F}^{2}} 最小化,且其表达式 r i {\displaystyle r_{i}} 足够稀松。

这个问题可以被视为是下面这个最佳化问题:

argmin D C , r i R n i = 1 K x i D r i 2 2 + λ r i 0 {\displaystyle {\underset {\mathbf {D} \in {\mathcal {C}},r_{i}\in \mathbb {R} ^{n}}{\text{argmin}}}\sum _{i=1}^{K}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{0}} ,而

C { D R d × n : d i 2 1 i = 1 , . . . , n } {\displaystyle {\mathcal {C}}\equiv \{\mathbb {D} \in \mathbb {R} ^{d\times n}:\|d_{i}\|_{2}\leq 1\,\,\forall i=1,...,n\}} λ > 0 {\displaystyle \lambda >0}

这里需要 C {\displaystyle {\mathcal {C}}} 来限制 D {\displaystyle \mathbf {D} } 的原子不会因 r i {\displaystyle r_{i}} 的值非常小而变得无穷大。 λ {\displaystyle \lambda } 这里则是控制稀松性, λ {\displaystyle \lambda } 越大,稀松性越大, λ {\displaystyle \lambda } 越小,稀松性越小,但稀松性越大代表还原的误差也会越大, λ {\displaystyle \lambda } 的取值常常伴随着稀松性与还原误差之间的取舍。

当n<d,上述定义的稀松字典 D {\displaystyle \mathbf {D} } 被称为低完备(undercomplete);当n>d,稀松字典 D {\displaystyle \mathbf {D} } 则被称为过完备(overcomplete)。

低完备字典会让输入讯号投影到低维度空间,类似于降维(dimension reduction)、主要成分分析。在投影到低完备的字典时,如何选择重要的子空间(subspace)是非常重要的,选择对的子空间能够让讯号最大程度的被保留下来。使用低完备字典进行降维这个方法可以应用在资料分析或分类上。

过完备的字典由于由较多的“原子”组成,因此一般上拥有较丰富的表达式。此外,过完备的特性能让讯号投影在到过完备字典时拥有稀松的特性。而透过学习得到的字典,即透过稀松字典学习而来的字典能让讯号在投影过来之后拥有更加稀松的表达式。

在问题定义有提到,在找寻一个可以让讯号投影至该空间并具有稀松特质的字典其实就是一种最佳化问题。这最佳化问题与稀松编码以及字典相关,目前大部分算法都是迭代式的相继更新字典以及其表达式。

最佳方向法是其中一个最早被提出用来解决稀松字典学习的方法。最佳方向法的核心理念是下面的最小化问题,在下面的最小化问题中,它的表达式只有固定数量的非零数值。

min D , R { X D R F 2 } s.t. i r i 0 T {\displaystyle \min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{s.t.}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T}

在这里, F {\displaystyle F} 为弗罗贝尼乌斯范数(Frobenius norm)。在整个算法过程中,MOD使用匹配追纵(Matching Pursuit)来取得讯号的稀松编码,随即计算 D = X R + {\displaystyle \mathbf {D} =XR^{+}} 的解析解(analytic solution),这里的 R + {\displaystyle R^{+}} 指的是摩尔-彭若斯广义逆(Moore-Penrose pseudoinverse)。随后这个更新后的 D {\displaystyle \mathbf {D} } 会在再标准化(renormalized)以达到我们的约束条件。这时,新的稀松编码也会同时计算得到。这个过程会一直重复直到稀松字典 D {\displaystyle \mathbf {D} } 以及稀松编码 R {\displaystyle R} 收敛为止。

相关链接参考:K-SVD

K-SVD 主要是以奇异值分解为核心来更新稀松字典的“原子”。它会让输入讯号 x i {\displaystyle x_{i}} 以不超过 T 0 {\displaystyle T_{0}} 的元素以线性组合的方式表示,整个过程与MOD类似:

min D , R { X D R F 2 } s.t. i r i 0 T 0 {\displaystyle \min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{s.t.}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T_{0}}

整个算法的过程在,一、先固定字典,找出满足上述条件相对应的 R {\displaystyle R} (可以使用匹配追踪)。然后固定 R {\displaystyle R} ,利用下面的式子迭代式的更新字典。

X D R F 2 = | X i = 1 K d i x T i | F 2 = E k d k x T k F 2 {\displaystyle \|X-\mathbf {D} R\|_{F}^{2}=\left|X-\sum _{i=1}^{K}d_{i}x_{T}^{i}\right|_{F}^{2}=\|E_{k}-d_{k}x_{T}^{k}\|_{F}^{2}}

整个字典学习的架构,其实就是对我们的输入讯号进行线性分解,分解到字典里的少数“原子”,并具有稀松特性。而这些“原子”是由本身的讯号产生,或学习得出来的。稀松字典学习可以应用在影像或者是影片处理。这个技术也常常被应用在分类问题上,我们可以针对不同的分类来对字典进行设计,透过输入讯号映射到字典的稀松表达式,我们可以较容易的把该讯号进行有效的分类。

此外,字典学习还有一个性质,那就是在噪声去除上非常有效。这时因为字典在学习时会找出输入讯号相似的特性,这时候具有意义的讯号会被学习到字典,而不具意义的讯号则会被排除在字典之外。那么,当输入讯号映射到字典时,由于字典不含有噪声的“原子”,所以该讯号在还原回来时不会有噪声。

相关

  • 温带季风温带季风气候是一种分布于亚欧大陆东部的气候类型。温带季风气候分布于亚欧大陆的温带东部,具体在秦岭淮河以北、大兴安岭——阴山——贺兰山以东以南、日本关东以北,包括华北
  • 洁癖洁癖(英语:Mysophobia,也称verminophobia、germophobia、germaphobia、bacillophobia或bacteriophobia)是强迫症的一种,即把正常卫生范围内的事物认为是肮脏的,感到焦虑,强迫性地清
  • 痤疮丙酸杆菌痤疮丙酸杆菌(学名:Propionibacterium acnes)是和皮肤疾病粉刺息息相关,是一种生长相对缓慢的典型革兰氏阳性菌,杆状,兼性厌氧。它会引起慢性睑炎以及眼内炎,特别是后者还需要眼科
  • 西惠特尔-洛斯涅托斯西惠提尔-洛斯涅托斯(英语:West Whittier-Los Nietos)是位于美国加利福尼亚州洛杉矶县的一个人口普查指定地区。西惠提尔-洛斯涅托斯的座标为33°58′34″N 118°04′08″W / 3
  • 鼻唇沟鼻唇沟(Nasolabial fold、Smile line、Laugh line),通常被称为法令纹,是位于鼻子和嘴两侧的皮肤褶,分开了上嘴唇和脸颊。这是由致密的纤维组织、提上唇肌的纤维、起于鼻唇沟筋膜
  • 2010年马来西亚羽毛球黄金大奖赛2010年马来西亚羽毛球黄金大奖赛为第2届马来西亚羽毛球黄金大奖赛,是2010年世界羽联大奖赛的其中一站。本届赛事于2010年7月6日至7月11日在马来西亚新山举行,并获得YONEX-SUNR
  • 异硫氰酸烯丙酯异硫氰酸烯丙酯 (Allyl isothiocyanate, AITC) 是一种有机硫化合物,其化学式为CH2CHCH2NCS。异硫氰酸烯丙酯是一种无色的油脂,芥菜,萝卜,辣根,芥末的刺激性味道都是来自于此化合
  • 香叶醇香叶醇(英语:Geraniol,又称牻牛儿醇)是一个非环单萜醇类化合物。它是玫瑰油、马丁香油和香茅油等香精油的主要成分之一,也少量存在于天竺葵和柠檬中。常温下为无色至黄色的油状液
  • 劳伦斯·布朗劳伦斯·布朗(英语:Lawrence D. Brown,1940年12月16日-),美国统计学家,宾夕法尼亚大学沃顿商学院教授。布朗毕业于加州理工学院、康奈尔大学,1964后获博士学位。此后曾历任加州大学
  • 刘锡瑛刘锡瑛(1894年-1966年),河北滦县人,中国教育家、电机专家,九三学社中央委员会常务委员。曾任天津大学副校长、校长,第一至四届天津市政协副主席,第二至四届全国政协委员。