稀疏表示_稀疏表示分类 - CSDN
精华内容
参与话题
  • 稀疏表示(Sparse representation)原理理解

    万次阅读 多人点赞 2019-03-21 16:21:41
    最近他很想了解我最近在搞的东西,在此,就发一片博客来简单说明一下自己最近研究的稀疏表示算法。因为本人能力有限,我会尽自己最大的努力将稀疏表示算法讲的清楚简单。此外,博客中避免不了会有一些差错,希望各位...

    谨以此文献给我最好的朋友

    我有一个十分好学的朋友,一起度过了三年的大学时光(大二认识的),最终他选择了工作,我继续读书。最近他很想了解我最近在搞的东西,在此,就发一片博客来简单说明一下自己最近研究的稀疏表示算法。因为本人能力有限,我会尽自己最大的努力将稀疏表示算法讲的清楚简单。此外,博客中避免不了会有一些差错,希望各位大佬理解。

    正文

    稀疏表示(Sparse Representation)也叫作稀疏编码(Sparse Coding),就是用字典中元素的线性组合去表示测试样本。

    我们现在考虑图片分类问题,如下:

    图片分类

    现在给定一个任务,在字典中找出10张图片,用这10张图片的一个线性组合去尽可能的表示测试样本,如果是你的话,你会怎么选,你会选10张桌子图片去表示 一张狗的图片吗?不会的,你会选10张狗的图片竟可能的描述测试样本。这也就是稀疏表示的过程。表示,就是用字典中的元素(就是字典中的样本)的线性组合尽可能的描述(还原)测试样本。稀疏表示要用尽可能少的字典中的元素去描述测试样本。为什么要稀疏呢?为什么选用的字典中的样本要尽可能少呢?你可以想象对于一个狗的图片,我用大量的字典中桌子的的样本,东补补西凑凑,只要桌子的样本够多,我也是可以用大量桌子图片的线性组合去表示狗这张图片的。所以对字典中选取的样本的数量要求尽可能的少。

    然后,我们的任务就是怎么将这个想法,用数学的公式表示出来,然后用计算机编程实现。

    对应的数学表示

    在图片分类的问题上,通常把一个两维图像,展成一个一维的向量(一般说向量,是列向量),来方便后边的操作。如何将一个二维图像展成一个一维向量呢,很简单,就是以列展开,第一列下边接上第二列,第二列下边接上第三列.....

    完整之后就是这样一个情况:

    转化为向量

    下面我将详细的解释这图途中每一个字母的含义

    Y_{i} 表示的是第i个测试样本(就是上个图中左侧的狗这个测试样本),上边我们提到我们已经将二维图像展成了一个一维图像,在这里Y_{i} 为N*1的向量,N表示样本的维度。

    D表示的是字典(就是上一个图中的字典),这里对字典中的每一个二维图像也展成了一个向量。D是一个N*M的矩阵,N表示样本的维度,所有的样本的维度都是相同的,用图像处理可以很简单的做到。M表示字典中训练样本的个数。

    注意这个图中D=[\varphi _{1}^{^{T}};\varphi _{2}^{^{T}};...;\varphi _{n}^{^{T}}] 的表述是不准确的,实际上应该是D=[\varphi _{1},\varphi _{2},...,\varphi _{n},] ,其中\varphi _{i} 表示的是第i类训练样本的训练集,n表示类别总共n类。假设i个类别中训练样本的个数用p_{i} 表示,那么可以得到n类样本总的样本个数为\sum _{1}^{n} p_{i}=M

    X_{i} 就是对应第i个测试样本的稀疏系数。

    下面我将讲明这个公式代表的具体意思(很重要),

    Y_{i}=D\times X_{i}

    我们把D矩阵写成行向量的形式,上个公式就变成了

    Y_{i}=[d_{1},d_{2},...,d_{M}]\times X_{i}

    注意这里的d_{i} 与上边提到的\varphi _{i} 所表示的意思是不一样的,d_{i} 是一个N*1的向量,表示字典中第i个元素(训练样本),而\varphi _{i} 表示的是一个N*p_{i} 的矩阵,表示的是字典中第i个训练样本的总体。

    我们再把X_{i} 展开,

    Y_{i}=[d_{1},d_{2},...,d_{M}]\times [x_{1};x_{2};...x_{M}]

    [x_{1};x_{2};...x_{M}] 表示列向量,我们继续变换

    Y_{i}=x_{1}\times d_{1}+x_{2}\times d_{2}+...+x_{n}\times d_{n}

    这个公式的含义是什么呢?你可以想仔细想想,是不是很兴奋,他代表这用的d1,d2...等训练样本去表示测试样本,这不就是我们在开头提出的问题吗?选10张照片去表示狗。

    现在稀疏表示,表示已经出来了,稀疏怎么办呢,很好办,我们约束系数X_{i}  是稀疏的,具体的约束就是X_{i} 中非零项的个数不能超过10,用数学公式表示就是 ||X_{i}||_{0}<T, 这个叫做0范数,就是要求X_{i} 中非零项的个数不能超过T。

    最后还有一个问题怎么描述 误差呢,因为 

    Y_{i}=x_{1}\times d_{1}+x_{2}\times d_{2}+...+x_{n}\times d_{n}

    要做到严格的相等太难了,实际中是存在误差的,如何描述这个误差呢?

    是不是已经想到办法了

    (Y_{i}-x_{1}\times d_{1}+x_{2}\times d_{2}+...+x_{n}\times d_{n})^{2}

    最终上边所提的到的表示的问题,最终就转化成了如下公式:

    \arg \min ||Y_{i}-D\times X_{i}||_{2}^{2} \quad s.t. ||X_{i}||_{0}<T

    arg min这个单词下边应该有一个X_{i} (CSDN的公式编辑器中没有找到如何编写),表示在s.t.的约束下,使得上个公式最小的X_{i} 的值。

    如何求解这个问题,我们就直接用现成的算法就好,我一般用OMP算法,具体见https://blog.csdn.net/scucj/article/details/7467955

    最后最后的问题来了?怎么分类呢??先想几分钟,其实很简单

    那就是用字典中每一个类别对应的训练样本乘以与之对应的稀疏系数中的分量。

    我们上边提到

    Y_{i}=[d_{1},d_{2},...,d_{M}]\times [x_{1};x_{2};...x_{M}]

    现在我不这么划分了,我将D字典不按照样本数量划分了,我按照样本类别划分。

    Y_{i}=[D_{1},D_{2},...,D_{n}]\times [\alpha _{1};\alpha _{2};...\alpha _{n}]

    Di表示字典D中第i个类别中所有的样本,\alpha _{i} 表示Di 在系数X中对应的分量。

    最终||Y_{i}-D_{i}\times \alpha _{i}||_{2} 表示用字典D中的第i类去重建测试样本 Y_{i} 的误差。我们将误差最小的类别最为Y_{i} 的预测类别。

    具体的流程请见:

    SRC具体流程

     

     

    至此本片文章结束。

    但是我的朋友要求我要理论+实践,理论部分讲完了,实践部分,你们自己写吧。我觉得我讲的已经十分清楚了,这么清楚的一片博客,一个认真阅读的读者,应该可以自己写出代码来了吧

    (来自朋友的一顿毒打)

    所以,我还写了代码(真香),用稀疏表示来进行人脸识别(人脸分类)的。(脸好疼)

    这是结果

    用稀疏表示人脸分类的结果

    code:code

     

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

    万次阅读 多人点赞 2018-11-23 15:04:22
    1.什么是稀疏表示:  假设我们用一个M*N的矩阵表示数据集X,每一行代表一个样本,每一列代表样本的一个属性,一般而言,该矩阵是稠密的,即大多数元素不为0。 稀疏表示的含义是,寻找一个系数矩阵A(K*N)以及一...

    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

    展开全文
  • 稀疏表示(Sparse Representations)

    千次阅读 2019-03-28 17:00:27
    1.什么是稀疏表示: 用较少的基本信号的线性组合来表达大部分或者全部的原始信号。 其中,这些基本信号被称作原子,是从过完备字典中选出来的;而过完备字典则是由个数超过信号维数的原子聚集而来的。可见,任一信号...

    1.什么是稀疏表示:

    用较少的基本信号的线性组合来表达大部分或者全部的原始信号。

    其中,这些基本信号被称作原子,是从过完备字典中选出来的;而过完备字典则是由个数超过信号维数的原子聚集而来的。可见,任一信号在不同的原子组下有不同的稀疏表示。

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

    image

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

    表达为优化问题的话,字典学习的最简单形式为:
    字典学习表达式
    其中xi为第i个样本,B为字典矩阵,αi为xi的稀疏表示,λ为大于0参数。 

    寻找少量重要的系数来表示原始信号的技术被称作Sparse Coding(稀疏编码或稀疏分解);

    •从任意一个字典中为原始信号寻找最稀疏的表示常用的方法分类两类:

    ①贪婪算法,比如匹配追踪(MP)、正交匹配追踪(OMP)、弱匹配追踪(WMP)、阈值方法等;

    ②松弛算法,比如迭代加权最小二乘(Iterative-Reweighed-Least-Squares,IRLS)、基追踪(BP)等。

    其中,贪婪算法的特点是速度快,精度相对较低;松弛算法是精度高,但速度慢。

    穷举法——NP难:

    假设 的非零项数目为L(sparse level),先令L=1,字典里的每一个原子(列向量)尝试一遍,看是否满足终止条件,共有K种组合。如果没有满足,再令L=2,再次尝试,共有K(K-1)/2种组合。还没有满足条件的,则令L=3……组合的数目呈指数增长,于是遇到了NP难问题。

    贪婪算法——Matching Pursuit

    第一步,找到最接近X的原子,等效于 向量上仅取一个非零项,求出最接近的原子,保留下来;

    第二步,计算误差是否满足要求,如果满足,算法停止,否则,计算出残差信号,和第一步类似,找到最接近残差向量的原子,保留下来;

    第三步,调整已选向量的系数,使得 最接近X,重复第二步。

    松弛算法——Basis Pursuit,将L0问题转化为L1问题,解决的方法有很多,比如内点法、迭代收缩法等。事实上,它可以化成一个线性规划的问题,用MATLAB很容易解。

          上式中第一个累加项说明了字典学习的第一个目标是字典矩阵与稀疏表示的线性组合尽可能的还原样本;第二个累加项说明了αi应该尽可能的稀疏。之所以用L1范式是因为L1范式正则化更容易获得稀疏解。具体原因参看该书11.4章或移步机器学习中的范数规则化之(一)L0、L1与L2范数。字典学习便是学习出满足上述最优化问题的字典B以及样本的稀疏表示A(A{α1,α2,…,αi})。L1正则化常用于稀疏,可以获得稀疏解。如下图表示,L1正则化交点在轴上,所得的解一般只是在某个轴上有实数,另外的轴为0,从而最终得到稀疏解。

    2.字典学习:

            寻找字典的过程称为字典学习。字典学习的一个假设是字典对于指定信号具有稀疏表示。因此,选择字典的原则就是能够稀疏地表达信号。

    两种方法来设计字典:

    •从已知的变换基中选取,比如 DCT 、小波基等,这种方法很通用,但是不能自适应于信号。

    学习字典,即通过训练和学习大量的与目标数据相似的数据来获得。这里,我们介绍一种叫K-SVD的方法

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

    技术分享

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

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

    稀疏表达有两点好处:
    1) 省空间;
    2) 奥卡姆剃刀说:如果两个模型的解释力相同,选择较简洁的那个。稀疏表达就符合这一点。

    How to find the dictionary D?——K-SVD

    假设现在有原始信号矩阵 , 该矩阵的每一行表示一个信号或者一张图片, D 矩阵是字典矩阵,右下方是 稀疏解矩阵S,红色的点表示非零项。

    image

    Step 1: Initialize. 在 矩阵中随机挑选一些行向量(一些原图),填满矩阵 D,并归一化每一列。

    Step 2: Sparse Coding. 用松弛或者贪婪法进行稀疏编码,使得

    image

    得到稀疏表示 构成稀疏矩阵S的第i行。

    What are sparse representations/approximations good for?

    稀疏性是DFT、WT和SVD分解得以广泛利用的原因之一,这些变换的目的都是为了反映信号的确定性结构,并用紧凑的或稀疏的表示来表征这些结构;

    稀疏表示的思想为模式分类方法建立了基础,比如SVM和RVM,其中稀疏性直接与估计函数(estimator)的学习能力有关。

    稀疏表示解决的问题主要集中在:

    图像去噪(Denoise),代表性paper:Image Denoise Via Sparse and Redundant Representations Over Learned Dictionaries(Elad M. and Aharon M. IEEE Trans. on Image Processing,Dec,2006);Image Sequence Denoising Via Sparse and Redundant Representations(Protter M. and Elad M.IEEE Trans. on Image Processing,Jan,2009);

    超分辨率重建(Super-Resolution OR Scale-Up),代表性paper:Image Super-Resolution via Sparse Representation(Jianchao Yang, John Wright, Thomas Huang, and Yi Ma,IEEE Transactions on Image Processing, Nov,2010),A Shrinkage Learning Approach for Single Image Super-Resolution with Overcomplete Representations( A. Adler, Y. Hel-Or, and M. Elad,ECCV,Sep,2010);

    另外还有inpaintting,deblurring,compression等等..更多应用参考Elad M的书。

    image

    image

     

     

     

     

    转自:https://www.cnblogs.com/yifdu25/p/8128028.html

    展开全文
  • 稀疏表示去噪的理解

    万次阅读 多人点赞 2018-04-16 15:31:41
    1、 对稀疏表示的理解稀疏信号定义为:若信号仅有限非零采样点,而其他采样点均为零(或接近于零),则称信号是稀疏的。但是自然图像信号中,可以稀疏表示的情况是极少的,因为尽管有的地方值很小,但是并不为零,...

    1、  对稀疏表示的理解

    稀疏信号定义为:若信号仅有限非零采样点,而其他采样点均为零(或接近于零),则称信号是稀疏的。

    但是自然图像信号中,可以稀疏表示的情况是极少的,因为尽管有的地方值很小,但是并不为零,因此另一种概念“可压缩的”就被提出来,其定义是:如果在不丢失全部(大部分)信息的前提下,信号经过任何变换后是稀疏的,也就是说信号再某个变换域是稀疏的,那么可以称之为可压缩信号,自然图像信号多数是可压缩信号。

    利用可压缩信号的概念,那么大多数自然信号可以由有限个特征线性表达:

    这里,是用来表达信号的特征原子,是稀疏编码。

    如上图所示,D是训练好的过完备字典,通过稀疏编码,可以得到稀疏向量x,在重建过程中,利用字典D和稀疏向量x相乘,就可以用对应的第3,7,14个原子来线性表示原图像,稀疏向量x中不为0的个数是有限的,因此其表示是稀疏的。

    稀疏表示在实现中的细节问题:

    a.        在稀疏表示的过程中,图像首先被向量化,然后再用有限个原子向量稀疏表示,最后再把重构的图像reshape为二维图像

    b.        字典的原子个数是自定义的,但是为了构造过完备的字典,要求字典是一个矮矩阵,即行数小于列数,字典的行数,即每个原子的维数是图像patch的行数乘以列数,即patch的像素数。

    c.        对于全局的稀疏表示来说,字典在训练的时候,使用时训练样本是从观测图像中分割出来的一个一个的patch,所有的patch训练一个字典,用于训练字典的patch也是经过向量化以后,作为列向量,构成训练样本的矩阵

    d.         为什么要分块?

    我觉得是因为字典的原子是向量化的,其维数是图像块的行列积,而一幅图像的行列积是很大的,因此原子用分块的patch来表示,可以大大降低字典原子的维数,此外,用重叠的patch,有利于训练集的丰满,这样训练出来的字典才更加的准确。


    稀疏表示能够去噪的原因:可以认为含噪(观测)图像是由无噪(原始)图像和噪声合成的图像,而观测图像被认为是可稀疏的,即可以通过有限个原子来表示,而噪声是随机的不可稀疏的,即不可以通过有限个原子表示,因此通过观测图像去提取图像的系数成分,再用这些稀疏成分来重构图像,在这个过程中,噪声被处理为观测图像和重构图像之间的残差,在重构过程中残差被丢弃,从而达到去噪的效果。

    稀疏表示又称为稀疏编码,这个过程可以被视为特征提取的过程,可以看作把目标信号投影到一组非正交的基构成的空间中,而在每个基上投影的系数,就是稀疏编码。这组非正交的基向量中,每一个基向量被称为一个原子,这些原子(列向量)可以构成一个超完备的字典。

    那么,为什么要使用过完备的字典,或者说要在非正交的空间进行投影呢?

    对于一组正交基而言,它们可以准确而唯一地表示空间中的任何向量,而且这些向量间没有冗余(因为正交),正式因为严格的正交限制,因此正交基的展开简单,但是稀疏性不够理想,因为严格正交的基往往只能表示图像的某一个特征而不能够同时表示其他特征,因此正交基的稀疏性不及非正交基(过完备字典)。

     

    2、  稀疏表示模型

    稀疏表示的模型有3种,分别是:

    1)        利用拉格朗日乘子将两个约束条件合为一个不等式:

    2)        固定稀疏系数的个数,优化最小误差:

    3)        固定最小误差,优化稀疏系数个数:

    3、  常见的稀疏表示方法

    稀疏表示可以分为两个步骤:稀疏编码和字典学习

    1)        稀疏编码:在进行稀疏编码的时候,字典D是固定的

    在进行优化的时候,0范数的优化是一个NP难题,稀疏编码主要分为了3中主流的算法:

    a.        针对0范数的贪婪算法:MP(匹配追踪)算法,OMP(正交匹配追踪)算法,梯度追踪算法,此外还有ROMP(正则化正交匹配追踪)算法,Stage-wise OMP算法等。

    这些贪婪算法通过每次迭代时选择一个局部最优解来逐步逼近原始信号,MP算法运算量相对于BP算法计算量减少,但是容易陷入局部最优解,而后来提出的OMP算法在MP 的基础上,将选中的原子经Gram-Schmidt正交化处理后,然后再将原始信号在正交化的原子构成的子空间中投影,OMP可以得到全局最优解并且收敛速度比MP更快。

    b.        凸松弛法:BP(基追踪)算法,GPSR(梯度投影稀疏重构)

    这些凸松弛算法是针对范数最小提出的线性规划最优算法,这种算法需要的观测信号数量最少,但是计算量大

    c.        组合算法:就是将粒子群算法等结合到贪婪算法或者凸松弛算法中

    这种算法组合要求信号的采样支持通过分组测试快速重建,它的复杂度低,但是收敛性还没有得到证明

    2)        字典学习:传统的小波变换,曲波变换,DCT变换等,都是使用的固定的正交字典,这种字典和图像本身的统计特性没有关联,因此其表示的稀疏性往往得不到保证,而学习的字典是提取的数据特征是依赖于原始数据的统计特征的,因此在表示的时候,其稀疏性远远优于固定字典

    常见的字典学习的方法有MOD(最优方向)算法,K-SVD算法,Online算法,最大后验概率算法等。



    展开全文
  • 稀疏表示

    千次阅读 2018-12-28 20:34:00
     信号的稀疏表示并不是新的东西。我们很早就一直在利用这一特性。例如,最简单的JPEG图像压缩算法。原始的图像信号经过DCT变换之后,只有极少数元素是非零的,而大部分元素都等于零或者说接近于零。这就是信号的...
  • 稀疏表示分类(SRC)

    千次阅读 2018-03-27 11:20:34
    转载 2015年11月07日 10:51:57标签:压缩感知...基于超完备字典的信号稀疏分解是一种新的信号表示理论,其采用超完备的冗余函数系统代替传统的正交基函数,为信号自适应的稀疏扩展提供了极大的灵活性。稀疏分解可以...
  • 字典学习/稀疏表示学习笔记

    万次阅读 多人点赞 2016-02-24 16:10:58
    首先向大家安利一下南大周志华老师写的《机器学习》这本书...这两天看了一下该书关于稀疏表示的部分(第11章),将核心知识点总结归纳一下,以免遗忘。若有错误,望大家赐教。1.提出问题:什么是稀疏表示 假设我们用
  • 稀疏表示与压缩感知

    万次阅读 2016-04-07 16:21:13
    最近在看机器学习时,看到一章关于稀疏学习的,之前有了解过稀疏表示与压缩感知,但是两者之间的差异并不是很清楚,今天就总结一下吧 稀疏表示  稀疏域模型(Sparse-Land Model)即信号的稀疏表示,它意欲用尽可能...
  • 信号的稀疏表示

    万次阅读 2017-07-01 20:11:19
    本文是博主对网上一些资料的整理学习,会附上相关原文地址,一部分内容来自百度百科。 原文地址: https://wenku.baidu.com/view/185d325b4a7302768f993905.html
  • 深度学习系列(四):什么是稀疏编码

    万次阅读 多人点赞 2015-12-23 21:48:21
    上节使用简单方法阐述了自编码问题与简单...在这之前先看看稀疏表示。 从一个简单的例子说起,相信大多数人学过线性代数或者矩阵论之类的课程吧,再线性代数中,最初始的时候就会学到关于如何判断一大堆向量线性的相关
  • ML之FE:数据处理—特征工程之稀疏特征的简介、如何处理、案例应用之详细攻略 目录 稀疏特征的简介 ...信号稀疏表示的目的就是在给定的超完备字典中用尽可能少的原子来表示信号,可以获得信...
  • 稀疏表示与字典学习

    万次阅读 2017-04-21 22:20:41
    稀疏表示与分类Sparse representation 二压缩感知Compressed sensing 三字典学习及应用Dictionary learning一、稀疏表示与分类(Sparse representation) 二、压缩感知(Compressed sensing)如果信号在某一个...
  • 稀疏表示和字典学习的简单理解

    千次阅读 2019-02-20 16:28:51
    稀疏表示和字典学习的简单理解特征分类稀疏表示字典学习 特征分类 相关特征:对当前有用的属性 冗余特征:所包含的信息有时能从其他特征中推演出来。如若某个冗余特征恰好对应了学习任务所需“中间概念”,有时可以...
  • 文章来源 Jia K, Chan T H, Ma Y. Robust and practical face recognition via structured sparsity[J]. Computer Vision–ECCV 2012, 2012: 331-344.Highlight 作为一种 sparse representation based ...
  • 稀疏表示分类器

    千次阅读 2015-10-28 11:35:52
    稀疏表示可作为基础理论用于构建稀疏表示分类器[14](Sparse Representation Classifier, SRC)。SRC 假定当测试样本所在类的训练样本数足够多时,测试样本可由这些训练样本进行线性表示,而其它类的样本对重构该测试...
  • 稀疏表示学习

    万次阅读 2017-04-25 21:22:42
    1.提出问题:什么是稀疏表示 假设我们用一个M*N的矩阵表示数据集X,每一行代表一个样本,每一列代表样本的一个属性,一般而言,该矩阵是稠密的,即大多数元素不为0。 稀疏表示的含义是,寻找一个系数矩阵A(K*N...
  • 稀疏表示:寻找一个系数矩阵A(K*N)以及一个字典矩阵B(M*K),使得B*A尽可能的还原X,且A尽可能的稀疏。A便是X的稀疏表示。 书上原文为(将一个大矩阵变成两个小矩阵,而达到压缩)字典学习 :“为普通稠密表达的...
  • 在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。...三元组表示法按照压缩存储的概念,只存储稀疏矩阵的非零元素。因此,除了存储非零元的值之外,还必须同时记录下它所在的行和列的位置(i,j)。反之,
  • 近十几年来,稀疏(sparsity)已经成为信号处理及其应用领域中处于第一位的概念之一。近来,研究人员又致力于过完备(overcomplete)信号表示的研究。这种表示不同于许多传统的表示。因为它能提供一个广阔范围的生成...
  • 如何判断一个图是稀疏的还是稠密的  最近涉及了一些图的算法,发现用途蛮广,比如:物流配送... 决定我们采用邻接矩阵还是采用邻接表来表示图,需要判断一个图是稀疏图还是稠密图。邻接矩阵和邻接表表示图所需的存
1 2 3 4 5 ... 20
收藏数 79,321
精华内容 31,728
关键字:

稀疏表示