编者按：其实『降维』的思想贯穿各个学科、各行各业。仅从传统机器学习、深度学习和运筹学数学规划的角度，浅谈我心中『降维』这个概念。

作者 留德华叫兽 美国Clemson应用数学|运筹学硕士、博士候选人，德国海德堡大学数学|组合优化博士，博士研究方向为离散优化在计算机视觉的交叉应用。读博期间于意大利博洛尼亚大学和法国巴黎综合理工访问10个月，意大利IBM Cplex实习半年。学术不精，转而致力于科普，读博期间创办运筹OR帷幄（运筹学|数据科学|人工智能社区）以及DIY飞跃计划（全球1000+海外硕博留学咨询师）俩个知乎机构号|微信公众号|头条号|社区，并邀请学界|业界大佬联合举办了10+知乎 Live。现于德国某汽车集团无人驾驶部门机器学习组，担任计算机视觉研发工程师。

所谓降维，即把高纬度的数据“浓缩”到低维度，但最大化保留其主要的信息使得模型更高效，但尽量减少精度上的影响。

而在运筹学数学规划领域，另一个名词可能更为人熟知：分解（Decomposition）。

本质是一个（带约束的）优化问题

其中优化的目标方程是：最大化数据压缩比

约束条件可以是：丢失的"精度" <= 10%

或者是：压缩后依旧能被某模型识别出某某信息

拿人工智能最火的计算机视觉领域举例，现在智能手机拍的图片轻松就能上一千万像素分辨率，每个像素又有3个channel（RGB），精确建立图数学模型(Graph Model)一张图片就有至少三千万变量（维度）。

下面就以五个例子浅谈一下『降维』。

1

-  传统的图像压缩  -

便是一种降维的理念，即降低分辨率但尽量不失真。

例如下图：最左边是原图，最右边仅保留5%的像素，但却依然保证了图片的主要轮廓和色彩。

用到了包括经典的PCA（主成分分析法）在内的各种算法[1]

2
-  超像素（聚类）-

超像素最直观的解释，便是把一些具有相似特性的像素“聚合”起来，形成一个更具有代表性的大“元素”。

而这个新的元素，将作为其他图像处理算法的基本单位，即Graph中的node一来大大降低了维度；二来可以剔除一些异常像素点。至于根据什么特性把一个个像素点聚集起来，可以是颜色、纹理、类别等。

看下图大家就能一瞥一二：

因此，超像素也是一种降维。

如何把一张图片『降维』成超像素，聚类算法是常用的一种方法。我的一篇paper用到了基于图(Graph)的整数规划模型，不仅可以生成超像素， 还能同时对图片进行去噪。

因此，该模型可以用于带噪声图片的『降维』，如下图：

具体可以参考我写的这篇知乎回答

https://www.zhihu.com/question/27623988/answer/371772624

3

-  深度学习卷积神经网络  -

接触过深度学习的小伙伴，有了以上的基础，相信就不难理解。深度卷积神经网络（CNN）中，其实也有很多『降维』操作。例如：卷积、池化，甚至CNN模型本身。

/ 卷积 /

如下图，当stride=2, padding=0时，一个8x7的矩阵被『降维』到了3x3。

/ 池化 /

如下图，把一个4x4的矩阵『降维』到了2x2。

CNN一顿操作猛如虎，把一张图片“降维”成了四个Class。如下图：

这里我把“降维”打了引号，因为CNN其实已经通过数学模型做出了“降维”以外的『决策』|『分类』。

4

-  大规模数学规划模型的『降维』 -

毕竟硕士博士都是运筹学出身，免不了唠叨一下运筹学中的『降维』。它（或者叫“分解”）也贯穿于求解大规模数学规划问题的各类方法中。例如：割平面方法便是因为原问题过于庞大（约束条件太多），因此先降低约束条件的维度。求解一个更小的问题，小问题求得解之后再去判断是否满足原问题，如不满足则再加入约束继续求解。

与之相仿的，还有列生成法、Benders分解法等等。其实就是化繁为简的思想，然而精粹之处在于运筹学的这些『降维』方法与原问题是等价的，即丝毫不牺牲精度。

这就是数学的奇妙之处！

5

-  运筹学『降维』之实际应用  -

一个非常直观的运筹学应用：外卖派单和配送系统。

在外卖平台，一个典型的场景：消费者下单，外卖系统通过运筹学算法给外卖员派单，一个外卖员接了多个单子，系统实时规划取餐和送餐的路径。

这些实际场景运用到了多种运筹学模型的算法，例如匹配模型、车辆路径规划模型等。

例如当一个骑手有5个订单、10个任务点的时候，就存在11万多条可能的配送顺序。而在高峰期的时候，骑手往往背负的不止5单，甚至有时候一个骑手会同时接到十几单，这时候可行的取送顺序就变成了一个天文数字。

尽管运筹优化模型大可不必穷举以上所有的可能性，但是，当一个城市骑手和订单数量到达一定规模的时候，还是会因为整数规划的“指数爆炸”，不得不用到『降维』。

最简单的操作，即把一个城市『分解』成几片区域，限定该区域的订单只配送给该区域的骑手。虽然这样可能无法达到整个城市的全局最优，但是却大大降低了运筹学模型的算法复杂度。

这里的『降维』方法，与原问题是不等价的，只能达到各个区域的局部最优解。