搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 西安老实人报 > 机器学习基础(一)——稀疏表示

机器学习基础(一)——稀疏表示

西安老实人报 2020-07-01

机器学习基础(一)稀疏表示





(一)什么是稀疏表示



什么是稀疏表示?

首先我们来一个官方的说法:

任意一个信号都可以在一个过完备字典上稀疏线性表出。这样,一个信号被分解为有限个信号的线形组合的形式我们称之为稀疏表示。表达为公式为:


y = Dα  s.t.||α||0 < σ


当然,就这样给出一个定理和公式大家都肯定难以接受,接下来听我慢慢解释。

我们先从整体入手,理解这句话,然后在逐个的解释每个字眼的含义。


首先我们说到中国古典四大名著之一的《红楼梦》,全篇120回,一共用了731,017个汉字。新华字典是我们每个人小学都人手必备的工具书,共收录了11,200个汉字,虽然二者字数相差了将近70倍,但我们每个人都知道,《红楼梦》中出现的每一个汉字都能从《新华字典》里找到,并且如果大家仔细想想的话,《红楼梦》一定没有用完一本《新华字典》中收录的每一个汉字,综上我们可以说:一套《红楼梦》中所有的汉字都能在《新华字典》中找到,并且《新华字典》中一定有《红楼梦》没用到的汉字

机器学习基础(一)——稀疏表示

乍一听是不是挺有哲理?基于这个例子我们把“能在**找到”翻译成线性表示,把“一定有没用过的字”翻译成稀疏,这样的话是不是对我们文章开始所提到的定义有一点理解了?别急,我们再看一个例子。

你有没有思考一个问题,你如何认出你的朋友?

机器学习基础(一)——稀疏表示

你怎么能从人群中认出你最好的朋友,你怎么能在很多年不见之后一眼就认出你的年轻时候的朋友?这时候有的朋友可能会说啦,“因为他下巴这有颗痣”,“因为他鼻子特别大”,“因为他秃啦”,等等。


这些都对,我们可总结一下,我们只需要记住特定的几个专属于朋友的特征就能认出你的朋友,因为一张脸上有无数的东西可以记住,用掉书袋的话说,脸是连续的,有无数个特征,但你只需要记住很少的特征你就能认出你的朋友。那么这样的问题我们同样用上面的话总结一下:只需要从脸上找到有限个标志特征就能识别出一个人。同样的我们将“识别出人”看作是线形表出,“有限个”说成稀疏,这也是我们一开始提到的那句话一种理解。


这一次我们加深一步,我们将上一句话换个说法:人脸在面部特征识别的空间中是稀疏的。说白了也是同一个意思,面部特征识别空间就是我要认出一个人,也就是说我想认出一个人只需要有限个特征,而这有限个特征相较于拥有无限特征的脸来说,是稀疏的。


这样将第一个例子扩张,也就变成了:任意一本中文书在《新华字典》的收录汉字空间中是稀疏的。然后我们自然推广(高中数学知识),假设存在这样一个信号的字典,它也像《新华字典》一样收录了各种基本信号,那么我们也能说:任意一个信号都是这个信号字典中基本信号组合而成,并且任意一个信号不会用到其中的每一个基信号。抑或是:信号在信号字典的特征空间内是稀疏的。这就是本文一开始提到的定义的通俗理解。


好了,通过上面的解释相信所有人都对稀疏表示大体有了一个理解,现在我门开始理解定义中的一个关键字眼,“过完备”,什么是过完备呢,这就要用到一点线性代数中的知识。


我们知道在三维坐标系中任意三个互不相关的向量就可以表示出空间中所有的向量,表达为公式为:


x = ax1+bx2+cx3


其中x1,x2,x3表示任意三个互不相关的向量,并且我们知道任意四个,五个,六个向量也有同样的定理,但任意两个不行。为什么呢,因为向量的数量一定要大于等于空间的维数,即任意n维空间中,n个互不相关的向量就可以表示n维空间中所有的向量。

机器学习基础(一)——稀疏表示

那么我们将信号的长度n看作这个信号空间的维数,那么至少n个互不相关的信号才能表示这个空间内所有信号。


但是当n足够大时,我们很难保证互不相关(学过高等代数的更好理解),那么我们就只能增大信号数量,要多大呢?不多,只需要足够大,数学有时候就是这么感性,只需要m个信号,当m足够大时就能表示所有的信号了,数学符号表示为m>>n,那么这个过完备的意思就是字典中信号的个数要远远大于信号的长度。


其实过完备和稀疏是相辅相成的,只有m足够大,才能实现只用极少的原子表示一个信号。


最后我们来解释公式(1)。


其中y就表示任意信号,D表示过完备字典,α表示系数矩阵,Dα就是二者的点乘,s.t.表示subject to的缩写,我们所说的稀疏就是α中非零系数的数量很少,即绝大部分α中的系数都为0,如何用数学公式约束呢?就是||α||0 < σ,其中小于符号前一部分是α的第0范数,所谓范数就是距离的一种,现实中的A到B的距离就是第二范数,α的第0范数指的是α中非零元数的数量,整体来说就是α中非零元素的数量之和小于一个约定好的数σ。


好了到这里,稀疏表示的基本原理已经讲完了,相信大家对于稀疏表示都有了自己的理解,但同时也相信很多人也有这样的疑问,稀疏表示有什么用呢?



(二)稀疏表示的应用

假设一条数据长度为1024的信号占用的储存空间为1 kb,在计算机内部会表示成大小为1024×1的矩阵,我们可以将其改写成32×32大小的信号矩阵。那么我们要传输这样的一个信号就需要1 kb的流量。

机器学习基础(一)——稀疏表示

但由于信号的稀疏性质,我们可以将其表达为一个储存在本地的字典D,大小为32×64,和一个稀疏向量α,大小为64×32,因为稀疏表示的性质我们知道向量α中绝大部分位置上的数值为0,根据经验超过90%位置的数值为0,计算64×32×0.1=204.8,因此我们知道一般矩阵α中不会有超过205个有效值。


所以我们记录每个值所在的位置,占用205个数据空间。因此现在我们如果需要传输这个长度为1024的信号,仅需要传输205×2大小的矩阵,消耗流量仅0.4 kb。

接收方在接受到这个矩阵后按特定的方式重构系数矩阵,再与储存在本地的字典做内积就得到了原始的长度为1024的信号,整个过程节省的数据传输流量为60%。怎么样,是不是AMAZING!


需要注意的是,这只是一个很简单很粗浅的例子,实际情况比这复杂很多,但这已经足够表示稀疏在数据存储传输中的作用。


再一个例子,本文前面提到的,我们可以通过少量的特征识别出特定的人,因为特征具有特殊性,每个人的特征不相同。因此我们可以采用字典学习的方法(如果大家感兴趣的话我会在后面介绍)从每个人的面部图片学习到特征,并组成字典D,因为每个人的特征都不相同,因此我们再将人脸与每个特征字典比对时就可以通过特征的重合程度判断该图片中的人脸属于谁,这是人脸识别中的一种办法,基于稀疏理论的人脸识别,Sparse Representation Classification (SRC)的基础理论。


实际上,稀疏理论是从人体上最初发现的,英国学者发现人的视觉识别系统就是以稀疏的方式处理图像的,随后他于1996年将这个研究成果发表在了《nature》上,这才打开了稀疏理论的大门。如今,稀疏理论作为一种具有较强数学逻辑性的机器学习方法,已经广泛运用于图像处理,人脸识别,信号处理等多个学科门类中。




end


撰稿人:周三斤

审稿:小D

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《机器学习基础(一)——稀疏表示》的版权归原作者「西安老实人报」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注西安老实人报微信公众号

西安老实人报微信公众号:gh_12dadc9cee00

西安老实人报

手机扫描上方二维码即可关注西安老实人报微信公众号

西安老实人报最新文章

精品公众号随机推荐