稀松字典学习

✍ dations ◷ 2025-04-03 10:44: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}}

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

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

相关

  • 大动脉弹性动脉(elastic artery)为一种动脉,其中膜(英语:tunica media)含有大量胶原蛋白及弹性蛋白的血管。该血管具有一定的弹性,以承受脉搏的张力。弹性动脉的弹性及伸缩性造成了韦德克
  • 吉林2019冠状病毒病吉林省疫情,介绍在2019冠状病毒病疫情中,在中华人民共和国吉林省发生的情况。截至2020年3月25日24时,吉林省全省有确诊病例95例,其中境外输入1例,治愈出院92例,死亡
  • 1057年重要事件及趋势重要人物
  • 广州城广州城(原广东省城,旧南海县、番禺县)曾共有多座城门。宋代重修了子城(即中城),增筑东、西两城,史称“宋三城”,分布着16个城门。行春门连通中城和东城,而朝天门则连通中城和西城。明
  • 教育学系本系所是指专门研究教育领域的相关学系。就读此科系的学生大部分都是师范体系,将来毕业后准备成为教师的学生。也有部分的教育学系是提供已经任教已久的资深教师进修,或者是提
  • 赣剧赣剧是江西的主要剧种,其前身为古代四大声腔之一的“弋阳腔”。《珍珠记》、《张三借靴》是其代表性剧目。《还魂记》则是根据汤显祖同名原著改译。而赣剧皮黄腔的《雪夜访普
  • 雅克·马里顿雅克·马里顿又译雅克·马里丹或雅克·马里旦(法文:Jacques Maritain,1882年11月18日 – 1973年4月28日)是法国天主教哲学家。在新教的家庭出身,他一直奉行不可知论,后来在1906年
  • 十六进制编辑器十六进制编辑器(也称为二进制文件编辑器)是一种计算机程序,它可以用较为友好的界面用来编辑二进制文件。计算机的存储与处理皆为二进制,因此为了能用一个显示的字符表示整数个二
  • 征服者-313战斗机征服者-313战斗机(波斯语:قاهر-۳۱۳,又有“Ghaher-313”、“Qaher-313”、“Q-313”、“F-313”多种称呼与译名)是伊朗空军的一款研制中的单座隐身战斗机,于2013年2月1日首
  • 弗兰西丝·康罗伊弗兰西丝·康罗伊(英语:Frances Conroy,1953年11月13日-)出生于美国佐治亚州沃尔顿县门罗,美国女演员。1953年,康罗伊出生于美国佐治亚州沃尔顿县门罗 (佐治亚州),父亲是一个企业高