你印象中的線性規(guī)劃是什么樣的?先在二維平面上畫圖再找最優(yōu)解?
但畢竟是學(xué)理論嘛,大家或多或少都會(huì)覺得枯燥晦澀。那么為何不試試更加直觀、好玩的學(xué)習(xí)方式呢?例如這樣:
這是一位國外博主發(fā)布的機(jī)器學(xué)習(xí) 3D 教程,用可視化的方法展示如何在線性規(guī)劃問題中逐步逼近最優(yōu)解。
這篇帖子僅在一天之內(nèi)就在 Reddit 上收獲了接近 200 點(diǎn)的熱度:
還收到了很多網(wǎng)友的好評(píng):
我喜歡對(duì)數(shù)學(xué)問題高度可視化的描述,太棒了!
是什么內(nèi)容這么優(yōu)質(zhì)?不妨看看他到底做了什么工作。
線性規(guī)劃也可以一目了然
關(guān)于線性規(guī)劃問題大家應(yīng)該都不陌生。
在一組線性方程或不等式的約束下,求某一線性目標(biāo)函數(shù)極值的問題就是線性規(guī)劃問題。
而它的其中一個(gè)解法,就是上文中動(dòng)圖展示的單純形法,還曾被評(píng)為 20 世紀(jì)最偉大的算法之一。在生產(chǎn)計(jì)劃,日程管理,交通運(yùn)輸,農(nóng)業(yè)等諸多領(lǐng)域都有廣泛的應(yīng)用。
接下來我們以一個(gè)生產(chǎn)計(jì)劃為例子做講解:
假如你現(xiàn)在是老板,經(jīng)營一家貨運(yùn)公司,一共有兩種貨車。
第一種貨車跑一趟需要兩天,燒 4 桶油,可以創(chuàng)造 1000 的利潤。
第二種跑一趟要 15 天,燒 8 桶油,但是可以創(chuàng)造 5000 的利潤。
那如果你手上有 500 桶油,應(yīng)該怎么配比兩種貨車的貨運(yùn)次數(shù)才能在一年內(nèi)獲得最大利潤呢?
這就是一個(gè)簡(jiǎn)單的線性規(guī)劃問題。
這樣的約束條件看起來并沒有什么感覺,但是放在空間中就不一樣了。
類似于許多平面把完整空間分割出一塊多面體:
分割出的多面體(粉色部分)為可行域或者可行多面體。它包含了所有符合約束條件的點(diǎn)。
線性規(guī)劃的目的,簡(jiǎn)單來說就是在可行多面體上找到一個(gè)點(diǎn),來滿足預(yù)期。比如前面例子中的獲得最大利潤。
那應(yīng)該怎么找呢?博主對(duì)比了兩種辦法。
第一種是單純形法。
由于約束函數(shù)和目標(biāo)函數(shù)都是線性的,所以最優(yōu)解必然存在于可行多面體的頂點(diǎn)。
所以尋找最優(yōu)解的過程就可以描述為:沿著在可行多面體的棱上沿著目標(biāo)函數(shù)值增加的方向搜索頂點(diǎn)。
聽起來不明所以吧?但是用圖形解釋就清楚多了:
但是這個(gè)方法只能用于求解線性規(guī)劃的問題。對(duì)于非線性規(guī)劃就無能為力了。
而第二種內(nèi)點(diǎn)法,在更廣泛的凸集優(yōu)化問題中都可以應(yīng)用。
它和單純形法不同的地方在于,內(nèi)點(diǎn)法是通過增加一個(gè)懲罰函數(shù) P (x) 來不斷地調(diào)整路徑:
在逐漸靠近可行多面體邊界時(shí),懲罰函數(shù)會(huì)取越來越小的值。
內(nèi)點(diǎn)法直觀來看是這樣的:
它不再沿著可行多面體的棱進(jìn)行迭代,而是直接從內(nèi)部開始,逐漸逼近最優(yōu)解。是不是一目了然了?
相比于純數(shù)學(xué)或者算法的推演,可視化的形式明顯更容易讓人印象深刻。
更多的可視化教程
除了這篇 3D 教程之外,該博主還在另一個(gè)介紹凸優(yōu)化的 KKT 條件和內(nèi)點(diǎn)法的視頻中,可視化了內(nèi)點(diǎn)法是如何通過牛頓迭代逐漸得到最優(yōu)解的:
視頻中 x (t) 每經(jīng)過一個(gè)黃色的圓框代表進(jìn)行一次牛頓迭代,左下方的圖像代表 x (t) 在不斷地迭代下趨近于最優(yōu)解。同樣,也比視頻上方的一長(zhǎng)串公式容易理解多了。
用這樣的形式去呈現(xiàn)復(fù)雜的內(nèi)容不禁讓網(wǎng)友聯(lián)想到了另一位可視化視頻博主:
好內(nèi)容!還看到了 3blue1brown 的影子,動(dòng)畫也很清晰。
在博主的回復(fù)中,也能看到他受到另一個(gè)數(shù)學(xué)可視化博主 3blue1brown 的啟發(fā)。
后者也同樣輸出了很多數(shù)學(xué)可視化的相關(guān)視頻,如果有興趣可以多多了解。
參考鏈接:
https://www.reddit.com/r/MachineLearning/comments/qtx8hn/d_back_to_basics_linear_programming/
廣告聲明:文內(nèi)含有的對(duì)外跳轉(zhuǎn)鏈接(包括不限于超鏈接、二維碼、口令等形式),用于傳遞更多信息,節(jié)省甄選時(shí)間,結(jié)果僅供參考,IT之家所有文章均包含本聲明。