字典学习_字典学习 算法 - CSDN
精华内容
参与话题
  • 字典学习/稀疏表示学习笔记

    万次阅读 多人点赞 2016-02-24 16:10:58
    首先向大家安利一下南大周志华老师写的《机器学习》这本书,作为一个对此一窍不通的人看了都觉得很有意思,受益匪浅。语言平实却又干货十足,比某些故弄玄虚泛泛而谈的其它国内教材高到不知哪里去了。 最近看的...

    首先向大家安利一下南大周志华老师写的《机器学习》这本书,作为一个对此一窍不通的人看了都觉得很有意思,受益匪浅。语言平实却又干货十足,比某些故弄玄虚泛泛而谈的其它国内教材高到不知哪里去了。
    机器学习 book
    最近看的论文涉及到稀疏表示,正好这本书有讲到。这两天看了一下该书关于稀疏表示的部分(第11章),将核心知识点总结归纳一下,以免遗忘。若有错误,望大家赐教。

    1.提出问题:什么是稀疏表示
    假设我们用一个M*N的矩阵表示数据集X,每一行代表一个样本,每一列代表样本的一个属性,一般而言,该矩阵是稠密的,即大多数元素不为0。
    稀疏表示的含义是,寻找一个系数矩阵A(K*N)以及一个字典矩阵B(M*K),使得B*A尽可能的还原X,且A尽可能的稀疏。A便是X的稀疏表示。
    书上原文为

    “为普通稠密表达的样本找到合适的字典,将样本转化为合适的稀疏表达形式,从而使学习任务得以简化,模型复杂度得以降低,通常称为‘字典学习’(dictionary learning),亦称‘稀疏编码’(sparse coding)”块内容

    表达为优化问题的话,字典学习的最简单形式为:
    字典学习表达式
    其中xi为第i个样本,B为字典矩阵,aphai为xi的稀疏表示,lambda为大于0参数。
    上式中第一个累加项说明了字典学习的第一个目标是字典矩阵与稀疏表示的线性组合尽可能的还原样本;第二个累加项说明了alphai应该尽可能的稀疏。之所以用L1范式是因为L1范式正则化更容易获得稀疏解。具体原因参看该书11.4章或移步机器学习中的范数规则化之(一)L0、L1与L2范数。字典学习便是学习出满足上述最优化问题的字典B以及样本的稀疏表示A(A{alpha1,alpha2,…,alphai})。

    2.字典学习求解
    求解上述最优化问题的总体策略是,对字典B以及样本稀疏表示alphai交替迭代优化。即先初始化字典B,1.固定字典B对alphai进行优化。2.固定A对字典B进行优化。重复上述两步,求得最终B以及X的稀疏表示A。
    其中第一步可采用与LASSO正则化相似的方法(如Proximal Gradient Desent法)进行求解,第二步可采用KSVD方法进行求解。具体步骤参看该书11.5章节内容或search the internet,因为我也不是很懂·····

    展开全文
  • 稀疏表示以及字典学习

    万次阅读 多人点赞 2018-11-23 15:04:22
     稀疏表示的含义是,寻找一个系数矩阵A(K*N)以及一个字典矩阵B(M*K),使得B*A尽可能的还原X,且A尽可能的稀疏。A便是X的稀疏表示。  南大周志华老师写的《机器学习》这本书上原文:“为普通稠密表...

    1.什么是稀疏表示:

                假设我们用一个M*N的矩阵表示数据集X,每一行代表一个样本,每一列代表样本的一个属性,一般而言,该矩阵是稠密的,即大多数元素不为0。 稀疏表示的含义是,寻找一个系数矩阵A(K*N)以及一个字典矩阵B(M*K),使得B*A尽可能的还原X,且A尽可能的稀疏。A便是X的稀疏表示。

            南大周志华老师写的《机器学习》这本书上原文:“为普通稠密表达的样本找到合适的字典,将样本转化为合适的稀疏表达形式,从而使学习任务得以简化,模型复杂度得以降低,通常称为‘字典学习’(dictionary learning),亦称‘稀疏编码’(sparse coding)”块内容。

            表达为优化问题的话,字典学习的最简单形式为: 


     
    其中xi为第i个样本,B为字典矩阵,aphai为xi的稀疏表示,lambda为大于0参数。 

          上式中第一个累加项说明了字典学习的第一个目标是字典矩阵与稀疏表示的线性组合尽可能的还原样本;第二个累加项说明了alphai应该尽可能的稀疏。之所以用L1范式是因为L1范式正则化更容易获得稀疏解。具体原因参看该书11.4章或移步机器学习中的范数规则化之(一)L0、L1与L2范数。字典学习便是学习出满足上述最优化问题的字典B以及样本的稀疏表示A(A{alpha1,alpha2,…,alphai})。

    2.字典学习:

           该算法理论包含两个阶段:字典构建阶段(Dictionary Generate)和利用字典(稀疏的)表示样本阶段(Sparse coding with a precomputed dictionary)。这两个阶段(如下图)的每个阶段都有许多不同算法可供选择,每种算法的诞生时间都不一样,以至于稀疏字典学习的理论提出者已变得不可考。笔者尝试找了Wikipedia和Google Scolar都无法找到这一系列理论的最早发起人。

    技术分享

    出处:http://www.mamicode.com/info-detail-1568956.html

            字典学习的第一个好处——它实质上是对于庞大数据集的一种降维表示。第二,正如同字是句子最质朴的特征一样,字典学习总是尝试学习蕴藏在样本背后最质朴的特征(假如样本最质朴的特征就是样本最好的特征).稀疏表示的本质:用尽可能少的资源表示尽可能多的知识,这种表示还能带来一个附加的好处,即计算速度快我们希望字典里的字可以尽能的少,但是却可以尽可能的表示最多的句子。这样的字典最容易满足稀疏条件。也就是说,这个“字典”是这个“稀疏”私人订制的。

    第二部分 稀疏字典学习的Python实现

    用Python实现稀疏字典学习需要三个前提条件

    1.安装NumPy

    2.安装SciPy

    3.安装Python机器学习工具包sklearn

    为了避免过于麻烦的安装,这里我干脆建议诸位读者安装Python的商业发行版Anaconda,内含python集成开发环境和数百个常用的python支持包。具体安装过程和使用细节参见我的博客附录D Python接口大法。

    样例一:图片的稀疏字典学习

    这段代码来源于Python的Dictionary Learning的官方文献教材,主要用途是教会用户通过字典学习对图片进行滤波处理。

    step1:首先是各种工具包的导入和测试样例的导入

    from time import time
    
    import matplotlib.pyplot as plt
    import numpy as np
    import scipy as sp
    
    from sklearn.decomposition import MiniBatchDictionaryLearning
    from sklearn.feature_extraction.image import extract_patches_2d
    from sklearn.feature_extraction.image import reconstruct_from_patches_2d
    from sklearn.utils.testing import SkipTest
    from sklearn.utils.fixes import sp_version
    
    if sp_version < (0, 12):
        raise SkipTest("Skipping because SciPy version earlier than 0.12.0 and "
                       "thus does not include the scipy.misc.face() image.")
    try:
        from scipy import misc
        face = misc.face(gray=True)
    except AttributeError:
        # Old versions of scipy have face in the top level package
        face = sp.face(gray=True)
    

    第1行:导入time模块,用于测算一些步骤的时间消耗

    第3~5行:导入Python科学计算的基本需求模块,主要包括NumPy(矩阵计算模块)、SciPy(科学计算模块)和matplotlib.pyplot模块(画图)。有了这三个模块,Python俨然已是基础版的Matlab。

    第7~11行:导入稀疏字典学习所需要的函数,下面分行解释

    第7行:导入MiniBatchDictionaryLearning,MiniBatch是字典学习的一种方法,这种方法专门应用于大数据情况下字典学习。当数据量非常大时,严格对待每一个样本就会消耗大量的时间,而MiniBatch通过降低计算精度来换取时间利益,但是仍然能够通过大量的数据学到合理的词典。换言之,普通的DictionaryLearning做的是精品店,量少而精,但是价格高。MiniBatchDictionaryLearning做的是批发市场,量大不精,薄利多销。

    第8行:导入碎片提取函数extract_patches_2d。调用该函数将一张图片切割为一个一个的patch。如果一张图片相当于一篇文章的话,那么该函数的目标就是把文章中的每个句子都找到,这样才方便提取蕴藏在每个句子中的字。图片和patch的关系如下图所示:

    技术分享

    整张头像的照片是个图片,通过对图片的分割可以将图片分割为一个一个的小块,也就是一个个Pitch。如果对pitch仍然不了解,只好请你看这个:http://blog.csdn.net/zouxy09/article/details/8775488

    第9行:导入图片复原函数reconstruct_from_patches_2d,它可以通过patch复原一整张图片。

    第10行:导入测试工具nose下的异常抛出函数SkipTest

    第11行:导入SciPy版本检测函数sp_version用于检测版本高低,版本低于0.12的SciPy没有我们需要的样本测试用例

    第13~15行:检测SciPy版本,如果版本太低就抛出一个异常。程序运行结束

    第16~21行:尝试打开样本测试用例,如果打不开就抛出一个异常。

    step2:通过测试样例计算字典V

    # Convert from uint8 representation with values between 0 and 255 to
    # a floating point representation with values between 0 and 1.
    face = face / 255.0
    
    # downsample for higher speed
    face = face[::2, ::2] + face[1::2, ::2] + face[::2, 1::2] + face[1::2, 1::2]
    face = face / 4.0
    height, width = face.shape
    
    # Distort the right half of the image
    print(‘Distorting image...‘)
    distorted = face.copy()
    distorted[:, width // 2:] += 0.075 * np.random.randn(height, width // 2)
    
    # Extract all reference patches from the left half of the image
    print(‘Extracting reference patches...‘)
    t0 = time()
    patch_size = (7, 7)
    data = extract_patches_2d(distorted[:, :width // 2], patch_size)
    data = data.reshape(data.shape[0], -1)
    data -= np.mean(data, axis=0)
    data /= np.std(data, axis=0)
    print(‘done in %.2fs.‘ % (time() - t0))
    print(‘Learning the dictionary...‘)
    t0 = time()
    dico = MiniBatchDictionaryLearning(n_components=100, alpha=1, n_iter=500)
    V = dico.fit(data).components_
    dt = time() - t0
    print(‘done in %.2fs.‘ % dt)
    
    plt.figure(figsize=(4.2, 4))
    for i, comp in enumerate(V[:100]):
        plt.subplot(10, 10, i + 1)
        plt.imshow(comp.reshape(patch_size), cmap=plt.cm.gray_r,
                   interpolation=‘nearest‘)
        plt.xticks(())
        plt.yticks(())
    plt.suptitle(‘Dictionary learned from face patches\n‘ +
                 ‘Train time %.1fs on %d patches‘ % (dt, len(data)),
                 fontsize=16)
    plt.subplots_adjust(0.08, 0.02, 0.92, 0.85, 0.08, 0.23)#left, right, bottom, top, wspace, hspace

    第3行:读入的face大小在0~255之间,所以通过除以255将face的大小映射到0~1上去

    第6~7行:对图形进行采样,把图片的长和宽各缩小一般。记住array矩阵的访问方式      array[起始点:终结点(不包括):步长]

    第8行:图片的长宽大小

    第12行:将face的内容复制给distorted,这里不用等号因为等号在python中其实是地址的引用。

    第13行:对照片的右半部分加上噪声,之所以左半部分不加是因为教材想要产生一个对比的效果

    第17行:开始计时,并保存在t0中

    第18行:tuple格式的pitch大小

    第19行:对图片的左半部分(未加噪声的部分)提取pitch

    第20行:用reshape函数对data(94500,7,7)进行整形,reshape中如果某一位是-1,则这一维会根据(元素个数/已指明的维度)来计算这里经过整形后data变成(94500,49)

    第21~22行:每一行的data减去均值除以方差,这是zscore标准化的方法

    第26行:初始化MiniBatchDictionaryLearning类,并按照初始参数初始化类的属性

    第27行:调用fit方法对传入的样本集data进行字典提取,components_返回该类fit方法的运算结果,也就是我们想要的字典V

    第31~41行:画出V中的字典,下面逐行解释

    第31行:figsize方法指明图片的大小,4.2英寸宽,4英寸高。其中一英寸的定义是80个像素点

    第32行:循环画出100个字典V中的字

    第41行:6个参数与注释后的6个属性对应

    运行程序,查看输出结果:

    技术分享

     

    step3:画出标准图像和真正的噪声,方便同之后字典学习学到的噪声相比较

    def show_with_diff(image, reference, title):
        """Helper function to display denoising"""
        plt.figure(figsize=(5, 3.3))
        plt.subplot(1, 2, 1)
        plt.title(‘Image‘)
        plt.imshow(image, vmin=0, vmax=1, cmap=plt.cm.gray,
                   interpolation=‘nearest‘)
        plt.xticks(())
        plt.yticks(())
        plt.subplot(1, 2, 2)
        difference = image - reference
    
        plt.title(‘Difference (norm: %.2f)‘ % np.sqrt(np.sum(difference ** 2)))
        plt.imshow(difference, vmin=-0.5, vmax=0.5, cmap=plt.cm.PuOr,
                   interpolation=‘nearest‘)
        plt.xticks(())
        plt.yticks(())
        plt.suptitle(title, size=16)
        plt.subplots_adjust(0.02, 0.02, 0.98, 0.79, 0.02, 0.2)
    
    show_with_diff(distorted, face, ‘Distorted image‘)

    程序输出如下图所示:

    技术分享

     

    step4:测试不同的字典学习方法和参数对字典学习的影响

    print(‘Extracting noisy patches... ‘)
    t0 = time()
    data = extract_patches_2d(distorted[:, width // 2:], patch_size)
    data = data.reshape(data.shape[0], -1)
    intercept = np.mean(data, axis=0)
    data -= intercept
    print(‘done in %.2fs.‘ % (time() - t0))
    
    transform_algorithms = [
        (‘Orthogonal Matching Pursuit\n1 atom‘, ‘omp‘,
         {‘transform_n_nonzero_coefs‘: 1}),
        (‘Orthogonal Matching Pursuit\n2 atoms‘, ‘omp‘,
         {‘transform_n_nonzero_coefs‘: 2}),
        (‘Least-angle regression\n5 atoms‘, ‘lars‘,
         {‘transform_n_nonzero_coefs‘: 5}),
        (‘Thresholding\n alpha=0.1‘, ‘threshold‘, {‘transform_alpha‘: .1})]
    
    reconstructions = {}
    for title, transform_algorithm, kwargs in transform_algorithms:
        print(title + ‘...‘)
        reconstructions[title] = face.copy()
        t0 = time()
        dico.set_params(transform_algorithm=transform_algorithm, **kwargs)
        code = dico.transform(data)
        patches = np.dot(code, V)
    
        patches += intercept
        patches = patches.reshape(len(data), *patch_size)
        if transform_algorithm == ‘threshold‘:
            patches -= patches.min()
            patches /= patches.max()
        reconstructions[title][:, width // 2:] = reconstruct_from_patches_2d(
            patches, (height, width // 2))
        dt = time() - t0
        print(‘done in %.2fs.‘ % dt)
        show_with_diff(reconstructions[title], face,
                       title + ‘ (time: %.1fs)‘ % dt)
    
    plt.show()

    第3行:提取照片中被污染过的右半部进行字典学习。

    第10~16行:四中不同的字典表示策略

    第23行:通过set_params对第二阶段的参数进行设置

    第24行:transform根据set_params对设完参数的模型进行字典表示,表示结果放在code中。code总共有100列,每一列对应着V中的一个字典元素,所谓稀疏性就是code中每一行的大部分元素都是0,这样就可以用尽可能少的字典元素表示回去。

    第25行:code矩阵乘V得到复原后的矩阵patches

    第28行:将patches从(94500,49)变回(94500,7,7)

    第32行:通过reconstruct_from_patches_2d函数将patches重新拼接回图片

    该程序输出为四中不同转换算法下的降噪效果:

     技术分享技术分享

    技术分享技术分享

     

    第二部分代码出处:

    http://www.mamicode.com/info-detail-1568956.html

    展开全文
  • ML笔记:字典学习1(Dictionary Learning)

    千次阅读 多人点赞 2019-11-08 13:00:38
    二、字典学习以及稀疏表示的概要 2.1、我们为什么需要字典学习? 2.2、我们为什么需要稀疏表示? 三、下一节 参考文献 一、预备知识 稀疏向量:假设向量中的元素绝大部分为零元素,则称该向量是稀疏的。 稀疏...

    目录

    一、预备知识

    二、字典学习以及稀疏表示的概要

    2.1、我们为什么需要字典学习?

    2.2、我们为什么需要稀疏表示?

    三、下一节

    参考文献


    一、预备知识

    稀疏向量:假设向量X=\left \{ x_{1},x_{2},...x_{n} \right \}中的元素绝大部分为零元素,则称该向量是稀疏的。

    稀疏表示:将原始信号表示为在适当选取的一组过完备基(字典D=\left [ d_{1},d_{2},...d_{p}] \right)上的稀疏线性组合即信号的稀疏表示,其中 d_{1},d_{2},...d_{p}  为字典中的原子。过完备基的意思是其中的原子数大大的超过原始信号的维数

    在表达式中:X=D\alphaX称为原始信号,D为字典,\alphaX的稀疏表示。其实该表达式中间的=是理想化的情况,一般只是用D\alpha逼近原始信号X。这就类似于用神经网络或者卷积神经网络等深度学习的网络去模拟任意函数。只不过,在神经网络中,求的是权值的最最优值,而此处求得是在字典下的最优解\alpha。因此,类似的求解\alpha的过程变成了最优化D\alpha和原始信号D\alpha的过程。即信号的稀疏表示问题转化为求解稀疏正则优化问题。

    二、字典学习以及稀疏表示的概要

    字典学习(Dictionary Learning)和稀疏表示(Sparse Representation)在学术界的正式称谓应该是稀疏字典学习(Sparse Dictionary Learning)。该算法理论包含两个阶段:字典构建阶段(Dictionary Generate)和利用字典(稀疏的)表示样本阶段(Sparse coding with a precomputed dictionary)。这两个阶段(如下图)的每个阶段都有许多不同算法可供选择,每种算法的诞生时间都不一样,以至于稀疏字典学习的理论提出者已变得不可考。笔者尝试找了Wikipedia和Google Scolar都无法找到这一系列理论的最早发起人。

    这里有两个问题是必须要预先解释清楚:

    2.1、我们为什么需要字典学习?

    回答这个问题实际上就是要回答“稀疏字典学习 ”中的字典是怎么来的。做一个比喻,句子是人类社会最神奇的东西,人类社会的一切知识无论是已经发现的还是没有发现的都必然要通过句子来表示出来(从某种意义上讲,公式也是句子)。这样说来,人类懂得的知识可要算是极为浩繁的。有人统计过人类每天新产生的知识可以装满一个2T(2048G)大小的硬盘。但无论有多少句子需要被书写,对于一个句子来说它最本质的特征是什么呢?毫无疑问,是一个个构成这个句子的单词(对英语来说)或字(对汉语来说)。所以我们可以很傲娇的这样认为,无论人类的知识有多么浩繁,也无论人类的科技有多么发达,一本长不过20厘米,宽不过15厘米,厚不过4厘米的新华字典或牛津字典足以表达人类从古至今乃至未来的所有知识,那些知识只不过是字典中字的排列组合罢了!直到这里,我相信相当一部分读者或许在心中已经明白了字典学习的第一个好处——它实质上是对于庞大数据集的一种降维表示。第二,正如同字是句子最质朴的特征一样,字典学习总是尝试学习蕴藏在样本背后最质朴的特征(假如样本最质朴的特征就是样本最好的特征),这两条原因同时也是这两年深度学习之风日盛的情况下字典学习也开始随之升温的原因。题外话:现代神经科学表明,哺乳动物大脑的初级视觉皮层干就事情就是图像的字典表示。

    2.2、我们为什么需要稀疏表示?

    回答这个问题毫无疑问就是要回答“稀疏字典学习”中稀疏两字的来历。不妨再举一个例子。相信大部分人都有这样一种感觉,当我们在解涉及到新的知识点的数学题时总有一种累心(累脑)的感觉。但是当我们通过艰苦卓绝的训练将新的知识点牢牢掌握时,再解决与这个知识点相关的问题时就不觉得很累了。这是为什么呢?意大利罗马大学的Fabio Babiloni教授曾经做过一项实验,他们让新飞行员驾驶一架飞机并采集了他们驾驶状态下的脑电,同时又让老飞行员驾驶飞机并也采集了他们驾驶状态下的脑电。如下图所示:

    随后Fabio教授计算出了两类飞行员的大脑的活跃状态,如下图:

    左图是新飞行员(不熟练的飞行员)的大脑。图中黄色的部分,是被认为活跃的脑区。右图是老飞行员(熟练的飞行员)的大脑,黄色区域相比左边的图有明显的减少。换言之,针对某一特定任务(这里是飞行),熟练者的大脑可以调动尽可能少的脑区消耗尽可能少的能量进行同样有效的计算(所以熟悉知识点的你,大脑不会再容易觉得累了),并且由于调动的脑区很少,大脑计算速度也会变快,这就是我们称熟练者为熟练者的原理所在。站在我们所要理解的稀疏字典学习的角度上来讲就是大脑学会了知识的稀疏表示

    ML笔记:字典学习2(Dictionary Learning)稀疏表示的本质:用尽可能少的资源表示尽可能多的知识,这种表示还能带来一个附加的好处,即计算速度快。

    在懂得“字典”和“稀疏”各自的那点事儿以后,我们还要再讲讲稀疏和字典共同的那点儿事。或许在大脑中“字典”和“稀疏”是两个不怎么想干的阶段,毕竟“字典”涉及初级视觉皮层,而“稀疏”涉及前额叶皮层。但是在计算机中,“字典”和“稀疏”却是一堆孪生兄弟。在学习样本字典之初的时候,稀疏条件就已经被加入了。我们希望字典里的字可以尽能的少,但是却可以尽可能的表示最多的句子。这样的字典最容易满足稀疏条件。也就是说,这个“字典”是这个“稀疏”私人订制的。

    三、下一节

    参考文献

    最后感谢作者:

    1. https://www.cnblogs.com/endlesscoding/p/10090866.html
    2. https://blog.csdn.net/tiaxia1/article/details/80264228
    3. https://blog.csdn.net/txwh0820/article/details/46392293
    展开全文
  • 机器学习(十三)k-svd字典学习

    万次阅读 多人点赞 2016-03-26 12:31:27
    给定训练数据Y,Y的每一列表示一个样本,我们的目标是求解字典D的每一列(原子)。K-svd算法,个人感觉跟k-means差不多,是k-means的一种扩展,字典D的每一列就相当于k-means的聚类中心。其实球面k-means也是一种特殊...

    k-svd字典学习

    原文地址:http://blog.csdn.net/hjimce/article/details/50810129

    作者:hjimce

    一、字典学习

    字典学习也可简单称之为稀疏编码,字典学习偏向于学习字典D。从矩阵分解角度,看字典学习过程:给定样本数据集Y,Y的每一列表示一个样本;字典学习的目标是把Y矩阵分解成D、X矩阵:


    同时满足约束条件:X尽可能稀疏,同时D的每一列是一个归一化向量。

    D称之为字典,D的每一列称之为原子;X称之为编码矢量、特征、系数矩阵;字典学习可以有三种目标函数形式

    (1)第一种形式:


    这种形式因为L0难以求解,所以很多时候用L1正则项替代近似。

    (2)第二种形式:


    ε是重构误差所允许的最大值。

    (3)第三种形式:

     

    L是一个常数,稀疏度约束参数,上面三种形式相互等价。

    因为目标函数中存在两个未知变量D、X,K-svd是字典学习的一种经典算法,其求解方法跟lasso差不多,固定其中一个,然后更新另外一个变量,交替迭代更新。

    如果D的列数少于Y的行数,就相当于欠完备字典,类似于PCA降维;如果D的列数大于Y的行数,称之为超完备字典;如果刚好等于,那么就称之为完备字典。

    二、k-svd字典学习算法概述

    给定训练数据Y,Y的每一列表示一个样本,我们的目标是求解字典D的每一列(原子)。K-svd算法,个人感觉跟k-means差不多,是k-means的一种扩展,字典D的每一列就相当于k-means的聚类中心。其实球面k-means也是一种特殊的稀疏编码(具体可参考文献《Learning Feature Representations with K-means》),只不过k-means的编码矩阵X是一个高度稀疏的矩阵,X的每一列就只有一个非零的元素,对应于该样本所归属的聚类中心;而稀疏编码X的每一列允许有几个非零元素。

    1、随机初始化字典D(类似k-means一样初始化)

    从样本集Y中随机挑选k个样本,作为D的原子;并且初始化编码矩阵X为0矩阵。

    2、固定字典,求取每个样本的稀疏编码

    编码过程采用如下公式:


    ε是重构误差所允许的最大值。

    假设我们的单个样本是向量y,为了简单起见我们就假设原子只有这4个,也就是字典D=[α1、α2、α3、α4],且D是已经知道的;我们的目标是计算y的编码x,使得x尽量的稀疏。

    (1)首先从α1、α2、α3、α4中找出与向量y最近的那个向量,也就是分别计算点乘:

    α1*y、α2*y、α3*y、α4*y

    然后求取最大值对应的原子α。

    (2)假设α2*y最大,那么我们就用α2,作为我们的第一个原子,然后我们的初次编码向量就为:

    x1=(0,b,0,0)

    b是一个未知参数。

    (3)求解系数b:

    y-b*α2=0

    方程只有一个未知参数b,是一个高度超静定方程,求解最小二乘问题。

    (4)然后我们用x1与α2相乘重构出数据,然后计算残差向量:

    y’=y-b*α2

    如果残差向量y’满足重构误差阈值范围ε,那么就结束,否则就进入下一步;

    (5)计算剩余的字典α1、α3、α4与残差向量y’的最近的向量,也就是计算

    α1*y’、α3*y’、α4*y’

    然后求取最大值对应的向量α,假设α3*y’为最大值,那么就令新的编码向量为:

    x2=(0,b,c,0)

    b、c是未知参数。

    (6)求解系数b、c,于是我们可以列出方程:

    y-b*α2-c*α3=0

    方程中有两个未知参数b、c,我们可以进行求解最小二乘方程,求得b、c。

    (7)更新残差向量y’:

    y’=y-b*α2-c*α3

    如果y’的模长满足阈值范围,那么就结束,否则就继续循环,就这样一直循环下去。

    3、逐列更新字典、并更新对应的非零编码

    通过上面那一步,我们已经知道样本的编码。接着我们的目标是更新字典、同时还要更新编码。K-svd采用逐列更新的方法更新字典,就是当更新第k列原子的时候,其它的原子固定不变。假设我们当前要更新第k个原子αk,令编码矩阵X对应的第k行为xk,则目标函数为:


    上面的方程,我们需要注意的是xk不是把X一整行都拿出来更新(因为xk中有的是零、有的是非零元素,如果全部抽取出来,那么后面计算的时候xk就不再保持以前的稀疏性了),所以我们只能抽取出非零的元素形成新的非零向量,然后Ek只保留xk对应的非零元素项。

    上面的方程,我们可能可以通过求解最小二乘的方法,求解αk,不过这样有存在一个问题,我们求解的αk不是一个单位向量,因此我们需要采用svd分解,才能得到单位向量αk。进过svd分解后,我们以最大奇异值所对应的正交单位向量,作为新的αk,同时我们还需要把系数编码xk中的非零元素也给更新了(根据svd分解)。

    然后算法就在1和2之间一直迭代更新,直到收敛。

    #更新字典第k列,<span style="font-family: Arial, Helvetica, sans-serif;">phi为字典,y为样本集、sparse为上面稀疏编码矩阵X</span>
    def dict_update(phi, matrix_y, matrix_sparse, k):
        indexes = np.where(matrix_sparse[k, :] != 0)[0]#取出稀疏编码中,第k行不为0的列的索引
        phi_temp = phi
        sparse_temp = matrix_sparse
    
        if len(indexes) > 0:
            phi_temp[:, k][:] = 0#把即将更新的字典的第k列先给设置为0
    
            matrix_e_k = matrix_y[:, indexes] - phi_temp.dot(sparse_temp[:, indexes])#取出样本数据中,字典第k列有贡献的值,并求Ek
            u, s, v = svds(np.atleast_2d(matrix_e_k), 1)
    
            phi_temp[:, k] = u[:, 0]
            sparse_temp[k, indexes] = np.asarray(v)[0] * s[0]
        return phi_temp, sparse_temp

    参考文献:

    1、《Learning Feature Representations with K-means》

    2、Restauration parcimonieuse d'unsignal multidimensionnel :algorithme K-SVD

    **********作者:hjimce     联系qq:1393852684    原创文章,转载请保留原文地址、作者信息******************

    展开全文
  • k-svd字典学习

    万次阅读 2016-07-24 15:59:32
    k-svd字典学习 原文地址:http://blog.csdn.net/hjimce/article/details/50810129 作者:hjimce 一、字典学习 字典学习也可简单称之为稀疏编码,字典学习偏向于学习字典D。从矩阵分解角度,看字典学习...
  • 字典学习PPT和源码

    2020-07-29 14:21:46
    图解《字典学习》代码实现和PPT资源,包括KSVD,OMP。有详细列子
  • 图解《字典学习

    千次阅读 2019-01-06 14:49:09
     PPT&amp;代码链接 csdn:https://download.csdn.net/download/u012037852/10899017 github:https://github.com/longfeizhou2016/Dictionary-learning
  • 图像分类的字典学习方法概述

    万次阅读 2014-11-30 12:09:50
    图像分类的字典学习方法概述 1 字典学习(dictionary learning) 旨在从原始数据中找到一组特殊的稀疏信号,在机器视觉中称为视觉单词(visual words),这一组稀疏元素能够足够线性表示所有的原始信号。字典学习...
  • 字典学习

    千次阅读 2019-02-27 19:44:13
    字典学习 及 稀疏表示 字典学习详解
  • 基于字典学习的图像去噪研究与实践

    千次阅读 多人点赞 2020-04-17 03:06:55
    今天我们就以机器学习中的字典学习(Dictionary Learning)为例,来展示其在图像去噪方面的应用。文中代码采用Python写成,其中使用了Scikit-learn包中提供的API,读者可以从【2】中获得演示用的完整代码(Jupyter ...
  • 近几年深度学习声名鹊起,一个又一个AI领域被深度学习攻破,然而现在大部分深度学习所采用的算法都是有监督学习的方法;稀疏自编码、受限玻尔兹曼机等无监督学习方法也随之渐渐的被人们所忽视。然而有监督学习需要...
  • 稀疏表示与字典学习

    千次阅读 2019-02-23 20:11:12
    参考: 1.稀疏表示:https://www.cnblogs.com/yifdu25/p/8128028.html 2.K-SVD : https://blog.csdn.net/chlele0105/article/details/16886795 3.OMP : https://www.cnblogs.com/yifdu25/p/8385204.html ...
  • 文章目录一、理解K-SVD字典学习二、K-SVD字典学习算法概述2.1、随机初始化字典D2.2、固定字典,求取每个样本的稀疏编码2.3、逐列更新字典、并更新对应的非零编码 一、理解K-SVD字典学习 字典学习也可简单称之为稀疏...
  • 贪婪深度字典学习

    2018-11-25 15:43:18
    贪婪深度字典学习 原文地址:http://blog.csdn.net/hjimce/article/details/50876891 作者:hjimce 一、相关理论 近几年深度学习声名鹊起,一个又一个AI领域被深度学习攻破,然而现在大部分深度学习所采用的算法都...
  • 字典学习与稀疏表示

    千次阅读 2018-11-22 17:06:36
    &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;...假设我们用一个M*N的矩阵表示数据集X,每一行代表一个...稀疏表示的含义是,寻找一个系数矩阵A(K*N)以及一个字典矩阵B(M*K),使得B*A尽可能的还原X,且...
  • 注:字典学习也是一种数据降维的方法,这里我用到SVD的知识,对SVD不太理解的地方,可以看看这篇博客:《SVD(奇异值分解)小结 》。 1、字典学习思想 字典学习的思想应该源来实际生活中的字典的概念。字典是前辈们...
  • 监督型字典学习

    千次阅读 多人点赞 2014-04-11 16:43:41
    另一种是通过机器学习来从样本中获取字典,这种字典表现为一种显性矩阵,explicit matrix,而算法是用来适应矩阵的,比如PCA,GPCA,MOD,K-SVD等等,这种字典的好处在于比前一种灵活,表现也好,
1 2 3 4 5 ... 20
收藏数 183,296
精华内容 73,318
关键字:

字典学习