能否用一句話描述下究竟什麼叫「最優化」 問題? | 知乎問答精選

 

A-A+

能否用一句話描述下究竟什麼叫「最優化」 問題?

2018年02月04日 知乎問答精選 暫無評論 閱讀 2 ℃ 次

【王小龍的回答(152票)】:

最優化,就是:

1. 構造一個合適的目標函數,使得這個目標函數取到極值的解就是你所要求的東西;

2. 找到一個能讓這個目標函數取到極值的解的方法

下面通過兩個例子進行解釋。

一、圖像去噪

假設你手頭有一張照片《沙塵暴下依然堅持工作的攝像師》:

你打算讓計算機幫你去個噪,把圖像變清晰。你對計算機說:你打算讓計算機幫你去個噪,把圖像變清晰。你對計算機說:

你看,計算機的回復往往是「你丫能不能說機話!」這是因為計算機是無法進行抽像思維的,它不懂重建、去噪、清晰這些複雜的概念,它唯一會的東西就是加減乘除這樣的基本運算,你只能使用正確的計算機語句讓它去執行對應的基本運算,因此就需要首先把去噪問題轉化成一個數學問題,一個函數的求解問題。比如可以試著這樣想,去噪,就是要把圖像變平滑,於是你對計算機說:給爺來張圖片,無比光滑。計算機的回答是:你看,計算機的回復往往是「你丫能不能說機話!」這是因為計算機是無法進行抽像思維的,它不懂重建、去噪、清晰這些複雜的概念,它唯一會的東西就是加減乘除這樣的基本運算,你只能使用正確的計算機語句讓它去執行對應的基本運算,因此就需要首先把去噪問題轉化成一個數學問題,一個函數的求解問題。比如可以試著這樣想,去噪,就是要把圖像變平滑,於是你對計算機說:給爺來張圖片,無比光滑。計算機的回答是:

真的是好光滑,但是且慢!攝像師哪去了?你是想光滑圖像,但是也需要保留圖像中的有用細節。這就說明你設計的目標不合理。一個好的去噪的目標,應該兼顧兩個要求:與原始圖像盡量接近,並且盡量光滑。一個合適的目標可以是:尋找一幅圖像A,讓下面這個目標函數J最小:真的是好光滑,但是且慢!攝像師哪去了?你是想光滑圖像,但是也需要保留圖像中的有用細節。這就說明你設計的目標不合理。一個好的去噪的目標,應該兼顧兩個要求:與原始圖像盡量接近,並且盡量光滑。一個合適的目標可以是:尋找一幅圖像A,讓下面這個目標函數J最小:

J(A) = (A與原始圖像盡量接近) + r * (A盡量平滑)

我們要尋找的,就是能讓目標函數J最小的圖像A,能夠兼顧相似和平滑兩個要求。因子r用來權衡二者的重要程度。當r取0時,我們得到的最優目標圖像就是原始圖像自己!因為我們的目標只是相似,而原始圖像自己和自己最像,但是這樣就沒有任何平滑效果;當r取無窮大的時候,為了讓整個目標函數J不至於無窮大,我們必須保證A無比平滑,這樣就得到上面那張過度平滑,與原始圖像毫不相似的無意義圖片。因此,為了兼顧兩個目標,我們需要把r的值取得不大不小。

有了一個合適的目標函數,下面就需要構造一種獲得它的極小值的算法。在圖像去噪領域有一大堆算法:卷積去噪、中值去噪、雙邊濾波、偏微分方程、小波去噪、隨機場去噪......它們的作用或多或少都是相同的——求上面那個混合目標函數的最小值。計算機運算獲得的去噪圖像是:

從這個成功去噪的例子中我們可以看出:合理的目標函數是最優化第一個需要精心考慮的問題,需要直覺和理性;而如何求解目標函數,則是一個數學算法問題。二者都是數學家們和工程師們大顯身手的地方。從這個成功去噪的例子中我們可以看出:合理的目標函數是最優化第一個需要精心考慮的問題,需要直覺和理性;而如何求解目標函數,則是一個數學算法問題。二者都是數學家們和工程師們大顯身手的地方。

二、機器學習

題主困惑機器學習和最優化之間為什麼聯繫緊密,是因為對機器學習這個領域不太瞭解,實際上研究最優化方法最多的人都在這個領域。機器學習的目的,就是為了讓計算機代替人來發現數據之間隱藏的關係。

之所以要使用計算機,是因為數據量太大,遠遠超過人腦的處理能力。比如我們需要從一堆人臉圖片裡給每個人標上正確的名字,一幅32像素見方的人臉圖像有1024顆像素點,你能想像出一百萬張這樣的照片和1萬個人名字之間的關係是什麼樣嗎。再比如給你1萬個患者的DNA序列,每個患者的序列由百萬級的鹼基對構成,你能找到這些天文數字量級的序列和是否患某種疾病之間的聯繫嗎?

答案是不能!所以研究者退而求其次,建立很多學習模型,這些模型輸入是一個樣本的數據(頭像圖片、一個人的DNA序列),輸出是樣本的標籤(人名、是否患病)。模型裡有大量可以調整的參數,這些參數通過訓練,能夠學習到數據和標籤之間人類無法直接理解的、複雜的關係。科學家期望當模型訓練完成後,再拿來一個樣本,餵給這個訓練好的機器,它能夠吐出一個標籤,這個標籤恰好就是樣本對應的那個正確的標籤。

目前人們已經研究出一大堆學習模型:神經網絡、支持向量機、AdaBoost、隨機森林、隱馬爾科夫鏈、卷積神經網絡等等。它們的結構差異很大,但是共同點都是擁有一大堆參數,就等著你餵給它數據供它學習。這些模型的學習也需要一個目標函數:讓模型的分類錯誤率盡量小。為了達到目的,模型的訓練往往首先給參數賦上隨機初值,然後用各種下降法來尋找能讓分類錯誤率更小的參數設置,梯度下降、牛頓法、共軛梯度法和Levenberg—Marquard法都是常見的方法。

隨著研究的深入,問題也越來越多,比如下降法往往只能保證找到目標函數的局部最小值,找不到全局最小值,怎麼辦呢?答案是不一味下降、也適當爬爬山,說不定能跳出小水溝(局部極小值)找到真正的深井(全局極小值),這種算法叫模擬退火。也可以增大搜索範圍,讓一群螞蟻(蟻群算法)或者鳥兒(粒子群算法)一齊搜索,或者讓參數巧妙地隨機改變(遺傳算法)。

那麼多模型,到底該選哪個?研究者又發現了一個定理「天下沒有免費的午餐」定理,意思是沒有一個模型能一直比其他模型好,對於不同類型的數據,必須要通過實驗才能發現哪種學習模型更適合。機器學習領域也就成了學界灌水嚴重的領域之一——換模型、調參數就能發文章哎。

下面說到了調參數,問題又來了,到底是參數多了好還是少了好?參數少了模型太笨學不到數據內的複雜關係,參數多了模型太精明又可能會把數據中的隨機噪聲當作某種關係進行認真學習(過擬合)。最後大家一致認為,確定模型的複雜度時,要保證模型能力足夠強,能夠學會數據之間的關係,能力又不能太強,以至於耍小聰明亂學習。這種選擇模型的思想被稱為奧卡姆剃刀:選擇有能力的模型中最簡單的那個。此外,訓練模型的目標並不是為了使訓練樣本能夠被盡量正確分類,更需要對未知新樣本有好的分類效果,這樣模型才有實用價值,這種能力被稱為泛化能力。除了奧卡姆剃刀原理外,訓練時引入隨機性的模型比確定的模型(比如BP神經網絡)具有更好的泛化能力。

模型的更新也是問題。如果引入了新數據,全部模型都需要重新訓練是一筆很大的開銷,在線學習模型採用來一個樣本學一點的模式,能夠不斷自我更新;半監督學習利用少量帶標籤的樣本訓練一個原始模型,然後利用大量無標籤數據再學習。

咱們來看看一些經典的學習模型能做成啥樣。首先隨便畫點散點圖,紅色和白色是兩類不同的數據,分類器需要對整個空間做分割,讓平均分類錯誤率盡量小。你可以先想想如果讓你來分要如何劃分。

首先是神經網絡,使用了6個神經元把空間分成了奇怪的形狀:

如果神經元數目變成10個,學到的模式將會十分怪異,說明模型過於複雜了:如果神經元數目變成10個,學到的模式將會十分怪異,說明模型過於複雜了:

下面是支持向量機的分類結果,這是這幾十年機器學習最重要的成果之一,它的發明是基於結構最小化準則,通俗地講就是把目標函數設為:下面是支持向量機的分類結果,這是這幾十年機器學習最重要的成果之一,它的發明是基於結構最小化準則,通俗地講就是把目標函數設為:

J=模型分類正確率 + r * 模型複雜度

使得模型能夠自動選擇分類效果好,並且盡量簡單的參數。

接下來是隨機樹,它把空間劃分為一系列矩形區域(葉子),所有的葉子區域由一顆樹形結構從根節點不斷劃分而成,隨機的意思是樹的生長每次劃分第一維還是第二維是隨機的:

支持向量機對於小樣本數據和非線性結構數據的分類有十分優秀的表現:

在機器學習領域,還有很多重要問題被不斷討論,優秀的模型也不斷在湧現。這個領域的開山模型是神經元,由其組成的多層神經網絡由於訓練速度慢、分類效果不佳,在支持向量機出現後很快就失去了熱度。大家卯著勁研究怎麼面對訓練樣本不足的窘境,PCA和核方法大行其道,前者致力於減少數據維數,後者致力於從低維數據中學習高維結構。但是近幾年隨著卷積神經網絡的流行,神經網絡又煥發出了第二春,研究者發現只要樣本量足夠大(百萬級甚至億級樣本量),網絡參數足夠多(百萬級參數),加上巧妙的防過擬合技術,利用現代並行計算帶來的強大計算能力,神經網絡能夠學得和人類的判別能力一樣好。機器學習領域發展了幾十年,似乎又回到了出發的地方。

【周開拓的回答(10票)】:

謝邀,但是我本科最優化這門課掛了。。

所以算是工作後自學成才。其實這個東西挺好理解的:

更新:機器學習為什麼要學習最優化呢?

因為機器學習其實本質是機器進化,通過算法的方式進化出最適應需求(最優化函數)的「模式」。進化的過程和算法就是最優化的核心研究課題,所以剛好這個數學工具能為機器學習提供很好的幫助。

--------------------------

嚴格定義是對某個定義域為Q,值域為某個有序集R(一般研究R=實數的情形)的函數f,求x屬於Q使得f(x)最小(大)。

這樣的問題就是最優化問題。

這個東西和機器學習有什麼關係呢?機器學習中Q一般是一個函數構成的空間,比如希爾伯特空間。

然後比如你要學習出一個函數,函數q你希望輸入是128*128的圖像像素矩陣,輸出是判斷圖像是否代表一個美女。

然後你要制定一個標準,這個標準可以衡量q這個函數的質量,比如q輸出和實際情況相比的誤差什麼的,不展開討論,總之這個標準可以定義為一個函數,叫做v。v(q)越大,函數質量越高,越接近你想要的結果

那麼從數學上,你這個問題就轉變成了在Q這個空間內尋找v(q)的最大值這個最優化問題。

當然世紀上,因為Q這個空間的結構可能非常扯淡,因而這個問題基本不可能有解析解。所以要用數值方法:

如各種解析搜索方法:梯度下降、牛頓

隨機搜索方法:蟻群、進化、退火

還有就是設法取一個Q的性質比較好的子集。比如所有從128*128的圖像像素矩陣到0/1這個函數空間性質太差了。那麼比如說:

限定使用決策樹?

限定使用SVM

限定使用logistic

限定使用神經網絡

不定時更新。

【王希的回答(3票)】:

少花錢多幹事

【楊延生的回答(7票)】:

在機器學習領域有個普遍的觀點:所有機器學習的問題最後都轉換為了最優化問題。

擬合一些數據點,你可以選擇

擬合,你也可以選擇

擬合,你甚至可以選擇更高維的曲線擬合,那麼選擇哪個? -- 最優化問題

兩堆數據點,你想在中間畫一條直線,將其分開,實際上這樣的直線很多,選擇哪一個?最優化問題。

任何一個機器學習問題,我們提一個模型來描述問題很簡單,所有可能的模型組成了假設空間。

那麼機器學習最後都轉化到 在假設空間中找到最優解。 求最優解的策略很多,選擇經驗風險最小化或結構風險最小化,最後都還是最優化問題。

當然機器學習的內容肯定不止於此,數據、模型、算法都有很多內容值得探索。

【知乎用戶的回答(2票)】:

一句話有點難,一小段倒是可以。通俗一點來說,就是

1,要完成一件事情;

2,完成這件事情有多重選擇;

3,有一個或若干個指標來衡量這件事情的完成;

4,做這件事情可能有一些約束。

於是你要做的事情就是,在約束條件下,根據衡量指標,在所有可能的選擇中,篩選出使得指標最優的一個或多個可能。

下面舉些例子。

比如,

1,從家出發去某一地方;

2,方式:步行,公交,打的/自駕,地鐵;

3,指標:時間最短,或者行程最短;(對於步行,兩者一致。對於打的,距離最短路徑未必時間最少)

4,除地鐵外,其他方式你必須按照街道距離來。再比如你不能飛。

因為趕時間,且不能飛,所以你在所有可能的地面及地下交通方式中,通過比較,選擇了那個時間最短的交通方式。

以被提到的圖像去噪為例。圖像去噪就是在現有的觀察下,恢復出滿足一下幾點要求的去噪圖像:1)恢復結果視覺觀感更好;2)不能偏離觀察太遠(比如把cameraman恢復成了lena)。

比如在白噪聲情況下,這樣一個問題就變成了帶正則的最小二乘問題。正則項式因為圖像和噪聲在它下面有著完全不同的性質,最小二乘項是為了保證不偏離觀察太遠,而他們之間有個權重在衡量。

教科書中涉及到過的去噪算法大致都可以寫成以上的形式。區別是有些形式好解,可以直接給出答案,有些則需要迭代算法進行求解,而如何迭代求解,便是數值計算/優化算法所研究的東西。

也就是說,在圖像處理、機器學習以及其他很多領域中,很多實際問題最終都轉化為「在一定限制條件下,根據評判標準,在所有可能中,選擇出合適的一個或者幾個可行方案」,這一過程便是優化。(好像一句話說粗來了。。。)

「最」之所以加粗斜體下劃線,是因為很多情況下這個最合適是找不到噠。比如壓縮感知的原始模型最小化0范數,是非凸組合優化,稍微上點規模的問題(1萬維,5%稀疏度),全世界所有電腦加起來有生之年也是算不到最優解滴。

【花京華的回答(1票)】:

比如想從廣州去杭州,怎樣最快又最經濟(目標函數)?你有很多種方法,可以坐火車,飛機,汽車(很多種解,而且可以對這些解進行組合),但總是有個組合最讓你滿意(最優解),最符合你的期望。怎麼去求解這個最優解,由此產生的一系列方法。

【zwcao的回答(4票)】:

用更少的話獲取更多的贊

【良良的回答(1票)】:

這個吃得飽,這個花錢少,這個方法屌~

【jianfengyao的回答(1票)】:

求一個函數的最小值的問題

【Louder的回答(0票)】:

一句話的話,我覺得最優化就是」找到全局最優解「。

至於機器學習,在最優化中的運用中就是」幫助人類找到全局最優解「。

【趙鵬鵬的回答(0票)】:

老師曾講過,多約束條件下沒有最優解。

所以,私以為,只有接近「最優解」的解

這也是在課堂上學到的對我生活有指導意義的一句話

至於「最優解」,在各種約束條件下,花費最小的成本,不僅是經濟成本,還包括時間成本,機會成本等,能達到目的解就是「最優解」。

個人愚見。運籌學正在追趕老師的節奏。

【yipan的回答(0票)】:

在相對中的一種運動,被人為的結構,通過對比結構,認知其普適性。(你想要的答案?)

【阿學的回答(0票)】:

函數定義中,最具生命力的解值和.

【知乎用戶的回答(0票)】:

手機碼字貢獻答案。

一句話答案:

在一定約束下,求解可使得目標函數取得期望極值的輸入(可能是參數,也可能是決策方法等等)的問題。

這類問題在我們的控制領域經常遇到。不過為了讓小白也可以理解這個問題,我們就不討論控制領域的問題了,而是以最簡單的問題舉例。

例題,給你100m長的欄杆,讓你在廣闊的草原上圈地,被欄杆閉合圈起來的區域將屬於你,用於放牧。

解釋:

任何最優化問題,都要先有個目標,就是你要最優化什麼東西。這個目標要非常準確地表述出來,成為目標函數。

這裡,我們分析,放牧顯然是要求所圈區域面積越大越好。這就是我們的目標。目標函數為區域面積。同時,我們期望的極值是極大值,而不是極小指。

顯然,我們有一個約束,就是圍欄的長度不能超過100m。而不是無約束的任意求取。因為在資源無限的情況下,優化就沒什麼必要了。

現在,解決上面的問題,就是一個簡單的最優化問題了。

所以,剛才的例題即為:

在一定約束下(欄杆長度100m),求解可使得目標函數(區域面積)取得期望極值(極大值)的輸入(圍欄設計方案)的問題。

題目簡單,給出答案,方案為以100m為周長的圓即可。證明略。

最後介紹下我瞭解到實驗室其他小夥伴研究的最優化問題:物流的路徑規劃,以實現成本和時間的最優;傳感器的佈置問題,以實現最大目標區域的覆蓋率;容錯算法設計,以實現系統的誤警率、漏警率最低等等……

其實最後一個問題,就是我研究的坑……

手機碼字,晚上排下版……

【有勇有萌兔的回答(0票)】:

最高票已經很好回答了什麼叫「最優化」 問題。。。我回答一下「為什麼學習機器學習必須要看最優化的書」。。。

1. 機器學習目的是學一個函數f

2. 方法是構造一類函數

3. 然後挑出最好的一個

第二個問題是建模的問題,第三個問題是最優化。解決一個機器學習的問題,要做的就是解決這兩個問題。這就是最優化問題和機器學習的關係。

【知乎用戶的回答(0票)】:

hhhh?g?q?a

【步千山踏萬里雪的回答(0票)】:

max收益=f(min投入)

【仄仄仄平平的回答(0票)】:

最優化就是系統問題結構化 程序問題目的化 物理問題數學化 感性問題理性化 複雜形式簡單化 能不廢話就堅決不廢話 要一句話給說清楚 沒說完就不打標點這種慵懶 傲人的氣質。

標籤:-數學 -數學建模 -機器學習 -運籌學 -最優化


相關資源:





給我留言