Redian新闻
>
如何度量数据的稀疏程度?

如何度量数据的稀疏程度?

科技

©PaperWeekly 原创 · 作者 | 苏剑林

单位 | 追一科技

研究方向 | NLP、神经网络


在机器学习中,我们经常会谈到稀疏性,比如我们经常说注意力矩阵通常是很稀疏的。然而,不知道大家发现没有,我们似乎从没有给出过度量稀疏程度的标准方法。也就是说,以往我们关于稀疏性的讨论,仅仅是直观层面的感觉,并没有过定量分析。那么问题来了,稀疏性的度量有标准方法了吗?
经过搜索,笔者发现确实是有一些可用的指标,比如 、熵等,但由于关注视角的不同,在稀疏性度量方面并没有标准答案。本文简单记录一下笔者的结果。



基本结果
狭义上来讲,“稀疏”就是指数据中有大量的零,所以最简单的稀疏性指标就是统计零的比例。但如果仅仅是这样的话,注意力矩阵就谈不上稀疏了,因为softmax出来的结果一定是正数。所以,有必要推广稀疏的概念。一个朴素的想法是统计绝对值不超过 的元素比例,但这个 怎么确定呢?
1 相比于 0.0001 很大,但是相比 10000 又很小,所以大和小的概念不是绝对的。直观来想,稀疏的向量存在很多接近于零的数,那么它的绝对值的平均肯定会比较小,又因为大和小的概念是相对的,我们不妨将这个平均值跟最大值做除法,以获得相对结果,所以一个看上去比较合理的指标是

其中 是需要评估稀疏性的向量(下面都假设 并非全等向量,即至少有两个不同的元素),指标越小的向量越稀疏。不过,尽管这个指标有一定的合理性,但它却不够“光滑”,主要是 这个操作极易受到异常值的影响,不能很好地反应数据统计特性。



光滑齐次
于是,我们按照《寻求一个光滑的最大值函数》[1] 的思路,将 换成它的光滑近似。 标准的光滑近似是
然而,如果这里用 替代 ,并不能起到较好的改进效果。一是因为有 的放大作用, 同样容易受到异常值的影响,二是因为 没有正齐次性,反而不美(所有 乘以正数 ,稀疏性应该不改变)。在《寻求一个光滑的最大值函数》[1] 中我们也给出了一个 的具备正齐次性的光滑近似,它正好是 范数():

再次观察式(1),我们可以发现它的分子正好是 ,所以综合上面的结果,我们得到了度量稀疏性的一个指标为
如果只是固定维度的向量比较,那么 可以略掉。常见的是取 ,那么就得到稀疏性度量的 指标。



理想性质

在《“熵”不起:从熵、最大熵原理到最大熵模型(一)》[2] 介绍“熵”的概念时,我们发现可以通过几条熵应当具备的理想性质来把熵的数学形式确定下来。那么稀疏性可否效仿这一点呢?

论文《Comparing Measures of Sparsity》[3] 做了这方面的尝试,它提出稀疏性度量 应该具备以下几点理想性质(不失一般性,这里假设 是非负向量,如果不是的话,逐项取绝对值即可):
D1、,其中 。这点性质说的是如果总和不变,那么越均匀越不稀疏。
D2其中 。这点容易理解,就是指稀疏是一个相对的性质,所有元素乘以一个相同的倍数,不改变相对大小,也就不改变稀疏性。
D3其中 。这点也容易理解,全体元素加上一个正数,那么全体都更加远离了零,稀疏性自然要降低。
D4、,这里的 指两个向量拼接。这点也不难理解,就是单纯的数据复制不改变稀疏性。
P1、任意给定 存在 ,使得对于任意 ,都有 。这条性质想表达的是当某个元素足够大的时候,整个向量的稀疏性就由它主导了。
P2、这个就很朴素了,给向量添加零,应该导致稀疏性增加。
原论文对稀疏性的各种常用指标做了推导,发现只有一个名为 “Gini 指数”的指标同时满足以上 6 点性质(但这个 Gini 指数比较复杂,这里就不介绍了)。不过需要提醒的是,读原论文的读者需要仔细留意一下推导过程,因为笔者发现它证明 不满足 D3 的证明是错的,事实上 是满足 D3 的,至于其他推导笔者也没有细看,读者需要自行甄别正误。



参考证明
对于本文的两个指标,指标(1)同时满足除 D1 外的另外 5 点性质(如果 D1 的 改为 ,那么也满足),这些性质的判断是比较平凡的,这里不详细讨论了,请读者自行完成。

至于指标(4),可以证明它同时满足除 D4 外的另外 5 点性质,其中 D3、P1 的证明稍微复杂一些,这里给出它们的参考证明。

为了证明 D3,只需要证明
关于 是单调递增的。两边取对数,得到
我们只需要证明 。直接求导得到
等价于

这由幂均值不等式 [4] 直接可得。

P1 的证明思路是类似的,只需要证明当 足够大的时候,
关于 是单调递减的。两边取对数,得到
我们只需要证明 。直接求导得到

等价于
只要各 并非全零,那么当 足够大时,总可以使得上式对 恒成立。



完美指标
尽管指标(4)不满足 D4,但我们将它简单修改为

后,它是满足 D4 的,并且也可以检验它也满足 P2,至于其他几点性质并不涉及到维度 n 的改变,因此跟指标(4)一样也满足。也就是说, 是同时满足 6 点性质的“完美指标”!
由幂均值不等式 [4] 可知 所以 此外,由于
所以 。综上,
时,有

这个结果可以回答关于稀疏化的一些问题。比如为什么 L1 正则有利于稀疏化?因为 L1 出现在上式的分子中,它越小越稀疏。为什么 L2 正则不利于稀疏化?因为 L2 出现在上式的分母中,它越小越不稀疏。如果要更准确地实现稀疏,应该以 为正则项,它既最小化 L1,又最大化 L2,直接优化稀疏指标。



熵的联系
现在回到注意力矩阵上,它的特点是每一行对应一个概率分布,即自动满足 。最确定的概率分布是 one hot 分布,此时它也最稀疏;最不确定的分布是均匀分布,很显然此时它也最不稀疏。从这两个极端可以猜测,概率分布的稀疏性与不确定性有一定的关联。
我们知道,概率分布的不确定性一般用(香侬)熵来度量:
而此时指标(13)则变为 ,它是 范数的衍生物。既然稀疏性与不确定性可能有一定的关联,那么是否意味着熵与 范数存在一定程度的相关性呢?
确实如此。事实上,基于 范数我们可以构造出 Rényi 熵 [5]
可以证明 ,即 时正好对应于经典的香侬熵,而当 时就是一般的 Rényi 熵(有些场景 Rényi 熵也特指 时的情形)。每种 Rényi 熵都可以作为不确定性的某种度量,它们的值域都是 ,都是在 one hot 分布取的最小值、在均匀分布取得最大值。从这个意义上来说,所有的 Rényi 熵在一定程度上都是等价的,这就解释了熵与 范数的关联。
值得一提的是, 时的 Rényi 熵往往对数值计算更加友好,这是因为 然是一个正的、有界的结果, 运算不用担心 问题,而且只需要对最后的结果做一次 ;相反标准的香侬熵,需要对每个 都算 ,计算量增加而且还要特别 一下以防 的出现。



文章小结

本文系统整理了一下关于稀疏性的度量问题,并且讨论了它与 L1、L2、熵等概念的联系。


参考文献

[1] https://kexue.fm/archives/3290

[2] https://kexue.fm/archives/3534

[3] https://arxiv.org/abs/0811.4706

[4] https://en.wikipedia.org/wiki/Generalized_mean

[5] https://en.wikipedia.org/wiki/Rényi_entropy


更多阅读



#投 稿 通 道#

 让你的文字被更多人看到 



如何才能让更多的优质内容以更短路径到达读者群体,缩短读者寻找优质内容的成本呢?答案就是:你不认识的人。


总有一些你不认识的人,知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁,促使不同背景、不同方向的学者和学术灵感相互碰撞,迸发出更多的可能性。 


PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是最新论文解读,也可以是学术热点剖析科研心得竞赛经验讲解等。我们的目的只有一个,让知识真正流动起来。


📝 稿件基本要求:

• 文章确系个人原创作品,未曾在公开渠道发表,如为其他平台已发表或待发表的文章,请明确标注 

• 稿件建议以 markdown 格式撰写,文中配图以附件形式发送,要求图片清晰,无版权问题

• PaperWeekly 尊重原作者署名权,并将为每篇被采纳的原创首发稿件,提供业内具有竞争力稿酬,具体依据文章阅读量和文章质量阶梯制结算


📬 投稿通道:

• 投稿邮箱:[email protected] 

• 来稿请备注即时联系方式(微信),以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信(pwbot02)快速投稿,备注:姓名-投稿


△长按添加PaperWeekly小编



🔍


现在,在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧


·
·

微信扫码关注该文公众号作者

戳这里提交新闻线索和高质量文章给我们。
相关阅读
【宏观市场】如何看待财政与经济增长数据的背离?—评2023年1-2月财政数据一个人可以废物到什么程度?独家 | B站考虑全面取消播放量数据的显示前哨速览:扎克伯格锐评Vision Pro,铜矿未来会成为新的稀缺资源上海传奇“21所”的稀缺AP高中,10年低调不内卷,却成批培养康奈尔伯克利等名校生一句话的信息量能大到什么程度?亲身体验|日本最牛之一的“精密体检”医院,到底能高端到什么程度?说日本,看日本!完成数千万元级别A+轮融资,「云科安信」希望以动态、多维的视角帮客户度量安全风险丨早起看早期一土学校有夏校啦|炎热程度10%,体验程度1000000%知乎瞎扯|一句话的信息量可以大到什么程度?Rhino到底难道什么程度?孩子申请国际学校,要做哪些准备?英语要到什么程度?2023年三八节清晨漫步后院有感今日神图 | 梦话能离谱到什么程度?38节,如何拒绝诱惑?OpenAI推出ChatGPT企业版:用户有权决定对话数据和API数据的去留丨最前线美国发达到了什么程度?答案大跌眼镜!RTC 体验优化的“极值”度量与应用人要如何度过这一生,学学如何不沉重地活了日本寡闻“三八节”【外汇商品】如何度量交易拥挤度?赔偿N+3!OPPO终止芯片研发,低估了芯片烧钱的程度?没有这套OSM全国地图数据,你的ArcGIS彻底废了!(附矢量数据下载)中国现在,铀矿缺到什么程度?​ICLR 2023 | 用于类别不平衡图表示学习的统一数据模型稀疏性让别人舒服的程度,决定着你成功的程度AAAI 2023 | 面向低质量数据的时空预测知乎瞎扯|人可以后知后觉到什么程度?仅用67位患者的CT数据的影像组学研究如何发表在顶刊欧放?Zilliz星爵:向量数据库,开创AI原生数据基础软件时代 | GGV OMEGA访谈录斯坦福最新研究警告:别太迷信大模型涌现能力,那是度量选择的结果不用望眼镜也能看见今夜一颗耀眼的行星知乎故事|人在医院能无知到何种程度?挖到宝!会玩"国际象棋"的娃,是未来的稀缺品
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。