高维度——现代应用数学的核心挑战
novakon2016/07/29软件综合 IP:广东
所谓维度,指的是一个系统中自由变量的个数。高维(high-dimensional)问题是指系统中变量个数很多,以至于传统方法无法直接求解的问题。高维问题是现代应用数学、统计学、机器学习等领域中的核心挑战。可以说,目前前沿的学术报告中,十个有八九个和高维问题相关。

高维问题在不同的领域中可以有不同的表述方式。使用逼近论的语言可以表述如下。

假设我们需要逼近一个定义在\(d\)维欧式空间的有界子集上的函数,假设该函数有\(k\)阶光滑性,可以理解为该函数存在可积的\(k\)阶偏导数。假设采样点数量为\(n\),则此时最优的逼近速度为\(O(n^{-k/d})\)。这里最优的意义是对于任意的逼近方法,都存在一个满足上述条件的函数,使得逼近误差的阶不低于\(O(n^{-k/d})\)。

这个结果说明,当函数的光滑性固定的时候,如果维数增加,收敛速度会呈指数速度变慢。用一个不太确切的比方,对于\(d\)维的问题,如果要达到和1维问题相当的精度,需要的采样点个数为\(n^d\)。在实际中,这是令人难以接受的。我们称这个问题为维度灾难(curse of dimensionality)。

在当今世界中,随着传感、计算、储存等技术的发展,高维度问题比比皆是。在工程上,传统制造过程能够控制或测量的变量很少,但是在现代生产过程中,装有成百上千个传感器(sensor)的生产线比比皆是;在生物学上,随着基因检测技术的发展,我们已经能够在较低成本下实现全基因组的检测,由此观测到数以十万记的变量;在互联网上,大量不同来源的信息组成了一张巨大的社交网络,甚至可以将全世界所有的人联系在一起。

总的来说,高维度带来了前所未有的复杂性,其主要的挑战包括:如果有效的建模、如何有效的采样和分析、如何设计高效的算法。

下面简单介绍一下目前处理高维度问题的主要方法。

1)增加光滑性

从上面逼近的例子可以看出,最终的收敛速度取决于光滑性和维度的比值。所以,如果假设函数的光滑性可以随着维度的增长而增长,我们仍然可以期待一个不太差的收敛速度。换句话说,如果问题的维度非常高,我们必须假定目标函数非常光滑。在机器学习中,支持向量机(support vector machine)和神经网络(neural network)是利用光滑函数的典型例子;相反决策树(decision tree)则是不那么光滑的分类器。在应用数学中稀疏网格(sparse grids)是增加光滑性的典型方法,它考虑具有各向异性(anisotropic)光滑性的函数构成的空间。

2)特征提取

特征提取的主要思想是利用奇异值分解(SVD)。如果一个大矩阵主要的变异性(variation)可以被其少数几个较大的奇异值解释,我们就可以将一个高维问题化为一个维度不那么高的问题。当然,大矩阵的奇异值分解本身也是极为困难的事,实际中可能采用诸如贪婪法等近似方法。在应用数学中一个常见的方法为缩减基法(reduced basis method)。在统计中主成分分析(PCA)和因子分析(factor analysis)等方法是传统的,也是现在仍然广泛使用的方法。例如,深度学习(deep learning)中的限制的玻尔兹曼机(restricted Boltzmann machine)的构造就使用了主成分分析的原理。

3)稀疏性

稀疏性是指一种内生性(endogenous)的结构,在这个结构中绝大部分变量的取值都为0。一个简单的比方是:尽管世界上有70亿人,但是绝大多数人对我造成的直接影响等于0。压缩感知(compressive sensing)是应用数学中非常有名的方法。在统计学中相应的问题称为变量选择(variable selection),历史很长方法也很多。除了探讨自变量对因变量有无影响这一种稀疏模式以外,另一种常见的稀疏模式是考虑图上的稀疏性。另外在非线性问题中也可以类似的定义稀疏结构,神经网络和深度学习是利用非线性稀疏结构的典型例子。

高维问题从正式提出到现在已有近三十年的历史。总的来说,该领域已经取得了非常大的发展。然而由于实际问题越来越复杂,同时新的计算技术也在不断的涌现,所以需要研究的问题依然很多。另外,如果讲我上面提到的所有方法的理论与实践都掌握得比较好,在工业界应该可以找到一份高薪的工作(滑稽)
本帖转自超理论坛,原作者是小当。XXXXXXXXXXXXXXXXXub/XXXXXXXXp/2803

[修改于 7年9个月前 - 2016/07/29 11:52:43]

来自:计算机科学 / 软件综合
2
已屏蔽 原因:{{ notice.reason }}已屏蔽
{{notice.noticeContent}}
~~空空如也
Cirno
7年9个月前 IP:美国
823668
周末写PCA
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
hackerboygn
7年9个月前 IP:湖北
824065
对维度还没直观认识的同学,可以看看科教片《维度:数学漫步》(Dimensions: A Walk Through Mathematics【2008】,XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX/Dim_regarder_ZH_XXXXXm),有中文字幕。虽然CG在今天看来只值5毛,还有尴尬的拟音,但毫不影响你与高维度的第一次完美邂逅。
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

所属专业
所属分类
上级专业
同级专业
novakon
学者 机友 笔友
文章
1256
回复
8385
学术分
16
2008/03/29注册,2年2个月前活动

已走,勿送

主体类型:个人
所属领域:无
认证方式:手机号
IP归属地:未同步
文件下载
加载中...
{{errorInfo}}
{{downloadWarning}}
你在 {{downloadTime}} 下载过当前文件。
文件名称:{{resource.defaultFile.name}}
下载次数:{{resource.hits}}
上传用户:{{uploader.username}}
所需积分:{{costScores}},{{holdScores}}下载当前附件免费{{description}}
积分不足,去充值
文件已丢失

当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}
视频暂不能访问,请登录试试
仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。
音频暂不能访问,请登录试试
支持的图片格式:jpg, jpeg, png
插入公式
评论控制
加载中...
文号:{{pid}}
投诉或举报
加载中...
{{tip}}
请选择违规类型:
{{reason.type}}

空空如也

加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
收藏
取消收藏
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
管理提醒
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}