編者按：其實(shí)『降維』的思想貫穿各個(gè)學(xué)科、各行各業(yè)。僅從傳統(tǒng)機(jī)器學(xué)習(xí)、深度學(xué)習(xí)和運(yùn)籌學(xué)數(shù)學(xué)規(guī)劃的角度，淺談我心中『降維』這個(gè)概念。

作者 留德華叫獸 美國(guó)Clemson應(yīng)用數(shù)學(xué)|運(yùn)籌學(xué)碩士、博士候選人，德國(guó)海德堡大學(xué)數(shù)學(xué)|組合優(yōu)化博士，博士研究方向?yàn)殡x散優(yōu)化在計(jì)算機(jī)視覺的交叉應(yīng)用。讀博期間于意大利博洛尼亞大學(xué)和法國(guó)巴黎綜合理工訪問10個(gè)月，意大利IBM Cplex實(shí)習(xí)半年。學(xué)術(shù)不精，轉(zhuǎn)而致力于科普，讀博期間創(chuàng)辦運(yùn)籌OR帷幄（運(yùn)籌學(xué)|數(shù)據(jù)科學(xué)|人工智能社區(qū)）以及DIY飛躍計(jì)劃（全球1000+海外碩博留學(xué)咨詢師）倆個(gè)知乎機(jī)構(gòu)號(hào)|微信公眾號(hào)|頭條號(hào)|社區(qū)，并邀請(qǐng)學(xué)界|業(yè)界大佬聯(lián)合舉辦了10+知乎 Live?，F(xiàn)于德國(guó)某汽車集團(tuán)無人駕駛部門機(jī)器學(xué)習(xí)組，擔(dān)任計(jì)算機(jī)視覺研發(fā)工程師。

所謂降維，即把高緯度的數(shù)據(jù)“濃縮”到低維度，但最大化保留其主要的信息使得模型更高效，但盡量減少精度上的影響。

而在運(yùn)籌學(xué)數(shù)學(xué)規(guī)劃領(lǐng)域，另一個(gè)名詞可能更為人熟知：分解（Decomposition）。

本質(zhì)是一個(gè)（帶約束的）優(yōu)化問題

其中優(yōu)化的目標(biāo)方程是：最大化數(shù)據(jù)壓縮比

約束條件可以是：丟失的"精度" <= 10%

或者是：壓縮后依舊能被某模型識(shí)別出某某信息

拿人工智能最火的計(jì)算機(jī)視覺領(lǐng)域舉例，現(xiàn)在智能手機(jī)拍的圖片輕松就能上一千萬像素分辨率，每個(gè)像素又有3個(gè)channel（RGB），精確建立圖數(shù)學(xué)模型(Graph Model)一張圖片就有至少三千萬變量（維度）。

下面就以五個(gè)例子淺談一下『降維』。

1

-? 傳統(tǒng)的圖像壓縮? -

便是一種降維的理念，即降低分辨率但盡量不失真。

例如下圖：最左邊是原圖，最右邊僅保留5%的像素，但卻依然保證了圖片的主要輪廓和色彩。

用到了包括經(jīng)典的PCA（主成分分析法）在內(nèi)的各種算法[1]

2
-? 超像素（聚類）-

超像素最直觀的解釋，便是把一些具有相似特性的像素“聚合”起來，形成一個(gè)更具有代表性的大“元素”。

而這個(gè)新的元素，將作為其他圖像處理算法的基本單位，即Graph中的node一來大大降低了維度；二來可以剔除一些異常像素點(diǎn)。至于根據(jù)什么特性把一個(gè)個(gè)像素點(diǎn)聚集起來，可以是顏色、紋理、類別等。

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

因此，超像素也是一種降維。

如何把一張圖片『降維』成超像素，聚類算法是常用的一種方法。我的一篇paper用到了基于圖(Graph)的整數(shù)規(guī)劃模型，不僅可以生成超像素， 還能同時(shí)對(duì)圖片進(jìn)行去噪。

因此，該模型可以用于帶噪聲圖片的『降維』，如下圖：

具體可以參考我寫的這篇知乎回答

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

3

-? 深度學(xué)習(xí)卷積神經(jīng)網(wǎng)絡(luò)? -

接觸過深度學(xué)習(xí)的小伙伴，有了以上的基礎(chǔ)，相信就不難理解。深度卷積神經(jīng)網(wǎng)絡(luò)（CNN）中，其實(shí)也有很多『降維』操作。例如：卷積、池化，甚至CNN模型本身。

/ 卷積 /

如下圖，當(dāng)stride=2, padding=0時(shí)，一個(gè)8x7的矩陣被『降維』到了3x3。

/?池化 /

如下圖，把一個(gè)4x4的矩陣『降維』到了2x2。

CNN一頓操作猛如虎，把一張圖片“降維”成了四個(gè)Class。如下圖：

這里我把“降維”打了引號(hào)，因?yàn)镃NN其實(shí)已經(jīng)通過數(shù)學(xué)模型做出了“降維”以外的『決策』|『分類』。

4

-? 大規(guī)模數(shù)學(xué)規(guī)劃模型的『降維』 -

畢竟碩士博士都是運(yùn)籌學(xué)出身，免不了嘮叨一下運(yùn)籌學(xué)中的『降維』。它（或者叫“分解”）也貫穿于求解大規(guī)模數(shù)學(xué)規(guī)劃問題的各類方法中。例如：割平面方法便是因?yàn)樵瓎栴}過于龐大（約束條件太多），因此先降低約束條件的維度。求解一個(gè)更小的問題，小問題求得解之后再去判斷是否滿足原問題，如不滿足則再加入約束繼續(xù)求解。

與之相仿的，還有列生成法、Benders分解法等等。其實(shí)就是化繁為簡(jiǎn)的思想，然而精粹之處在于運(yùn)籌學(xué)的這些『降維』方法與原問題是等價(jià)的，即絲毫不犧牲精度。

這就是數(shù)學(xué)的奇妙之處！

5

-? 運(yùn)籌學(xué)『降維』之實(shí)際應(yīng)用? -

一個(gè)非常直觀的運(yùn)籌學(xué)應(yīng)用：外賣派單和配送系統(tǒng)。

在外賣平臺(tái)，一個(gè)典型的場(chǎng)景：消費(fèi)者下單，外賣系統(tǒng)通過運(yùn)籌學(xué)算法給外賣員派單，一個(gè)外賣員接了多個(gè)單子，系統(tǒng)實(shí)時(shí)規(guī)劃取餐和送餐的路徑。

這些實(shí)際場(chǎng)景運(yùn)用到了多種運(yùn)籌學(xué)模型的算法，例如匹配模型、車輛路徑規(guī)劃模型等。

例如當(dāng)一個(gè)騎手有5個(gè)訂單、10個(gè)任務(wù)點(diǎn)的時(shí)候，就存在11萬多條可能的配送順序。而在高峰期的時(shí)候，騎手往往背負(fù)的不止5單，甚至有時(shí)候一個(gè)騎手會(huì)同時(shí)接到十幾單，這時(shí)候可行的取送順序就變成了一個(gè)天文數(shù)字。

盡管運(yùn)籌優(yōu)化模型大可不必窮舉以上所有的可能性，但是，當(dāng)一個(gè)城市騎手和訂單數(shù)量到達(dá)一定規(guī)模的時(shí)候，還是會(huì)因?yàn)檎麛?shù)規(guī)劃的“指數(shù)爆炸”，不得不用到『降維』。

最簡(jiǎn)單的操作，即把一個(gè)城市『分解』成幾片區(qū)域，限定該區(qū)域的訂單只配送給該區(qū)域的騎手。雖然這樣可能無法達(dá)到整個(gè)城市的全局最優(yōu)，但是卻大大降低了運(yùn)籌學(xué)模型的算法復(fù)雜度。

這里的『降維』方法，與原問題是不等價(jià)的，只能達(dá)到各個(gè)區(qū)域的局部最優(yōu)解。