• 從一個案例開始

• 動態(tài)規(guī)劃

Hi, 你好。我是茶桁,。

咱們之前的課程就給大家講了什么是人工智能,，也說了每個人的定義都不太一樣。關于人工智能的不同觀點和方法,，其實是一個很復雜的領域,，我們無法用一個或者兩個概念確定什么是人工智能，無法具體化,。

我也是要給大家講兩個重要的概念,，要成為一個良好的AI工作者，需要了解兩個概念,，一個是什么是優(yōu)化問題,，第二個呢就是什么是繼續(xù)學習。

這一節(jié)開始,，我們要開始進入機器學習的入門,，這一部分只是機器學習的初級部分，我將其分成了三個部分,，分別是：

1. 如何衡量向量的相似性（metric for tensor)

2. k-means算法進行聚類

3. 線性回歸與梯度下降

但是整體課程的排程并不是嚴格按照這三個部分來排的,，所以大家能看到，我本篇課程的標題也并不是「如何衡量向量的相似性（metric for tensor)」,。以上三個部分僅僅是我們當前這一部分會講到的內容,，但是也是拆散了放入課程中的。

從一個案例開始

那這節(jié)課最初,，讓我們從一個實際案例來引入,，開始我們的深度學習初級之旅。

那要給大家講的第一個問題,，我們叫做optimization, 也叫做優(yōu)化問題,。那這里，我們拿一個實際的項目來,。

我們所在的城市,，可能很多人會經常看到運鈔車,。這個運鈔車其實也是銀行花錢雇的,，運鈔車其實也不是銀行的。

每次要使用運鈔車的時候是需需要花錢,，還比較貴,。這樣就會帶來一個結果，專門有人來策劃運鈔車的運行路徑,。為什么要策劃計劃運鈔車的運行路徑呢,？因為如果我們有一臺ATM機,，ATM機滿了，那么面對的一個問題就是別人存不進去錢了,，

另外很重要一點是,，如果一個ATM機滿了而且沒有把錢取出來，那這個錢就相當于是浪費了,。加入一個ATM機能存一百萬,，那晚拿出來一天、兩天,，對銀行來說損失就比較大,。

還有一種情況就是這個ATM機空了，那客戶去取錢的時候也取不到錢,，也就起不到ATM機的作用,。而銀行對ATM機所在地的房租也就相當于白費了。

試想一下,，如果同時有兩張卡,，一張農行卡，一張工行的卡,，在農行準備想取錢的時候取不出來,，就到工行去取了。而每次農行都取不出來,，那之后就用工行用的多了,。

在這樣的情況下, 一個城市有很多個點, 就需要有很多個運鈔車。

比方說在城市中有很多個ATM機的站點,，現(xiàn)在我們有k個運鈔車,。

我們要策劃一條線路，這個線路要使得所有的車,，每個車每個點只走一遍,，還要回到他出發(fā)的地方，而且這k個車運行的時間加起來是最小的,。

那怎么樣計劃出這樣一條路徑呢,？就這是一個非常典型的優(yōu)化問題。對于此類的問題其實還有很多很相似的,。

比如對于一家公司而言,，手里的錢是有限的。如何把這些金額分配到不同的項目組中,；

另外一個比方就是,，對于一個公司來說如何選取合理的倉庫的存貨點,，還有哪些倉庫放哪些商品,，能夠讓運輸?shù)能囕v花的時間最少,，能快速的去把這貨物運輸?shù)讲煌牡胤剑贿@種物流問題是我最喜歡的問題之一,。

或者我們制造一部手機,，我們能花的錢就這么多，那怎么樣能夠在我們可以花的這個金額的范圍內,，如何選取最合理的元器件成本,，讓我們的手機達到最大的利潤；

有很多約束條件,，很多約束我們做決策的東西,，總量不能大于多少。比方電的成本,，水的成本等等,，都要滿足一定的關系才可以。這種東西我們就把它叫做約束條件,。

要解決在約束條件下達成目標的這個問題,，我們就把它叫做優(yōu)化問題。

優(yōu)化問題就是,，我們可能會有不少的函數(shù),，這些函數(shù)去限定了之間的一種關系，也就是函數(shù)之間可能會有一些約束條件,。比如圖中的g_i(x),。

假設我們要造很多倉庫，倉庫加起來所花費的成本是什么樣的, 花費的人力是什么樣的,。

最后要優(yōu)化出來一個最小值就是我們的最小花費,，或者所需要最少的時間。這種問題其實廣泛存在于我們各個地方,。

你點外賣每天在地圖上做一個地圖的規(guī)劃,，公司里做一筆投資，其實都是使用了類似這樣的東西,。

動態(tài)規(guī)劃

我們要解決優(yōu)化問題,，其實有比較多的方法，今天來介紹最著名的一種,，也是可以說是最重要的一種,，動態(tài)規(guī)劃的思想。

動態(tài)規(guī)劃是一個什么樣的情況,？以這個問題引入一下,。

想象一下有這么一個工廠，這個工廠是賣木頭的,，長度是一米的木頭賣一塊錢,，長度2米的賣5塊錢,。

那么所以除非拿了一個一米的木頭，否則不會有一個人像傻子一樣說：把這個兩米的木頭截成兩段,。

圖中我們可以看到,，3米的就賣8塊等等，到后面10米的賣30,，11米的賣33,。

那么現(xiàn)在你拿到了一個長度為8的一個木頭，那你想想這個8米的木頭是該直接賣,，還是它切分掉去賣,。切分掉去賣的話，如果用1和7,，加起來就是18塊錢,，
2和6加起來就22塊錢了，比8是不是就多了,？

給你任意的一個長度n,，然后我們要得出來這個n到底該怎么切分能夠使得價格最大。怎么樣能夠讓賣出去的價格最大,。

思考一下咱們怎么解決這個問題,。計算機有一個很很簡單的方法，就是計算機有一個非常好的優(yōu)點就是它可以做窮舉,。你可以讓他去找什么,，讓他把所有東西全部都運行一遍就可以了。這是計算機的一個好處,。

我們來思考一下咱們怎么樣能夠解決這個問題呢,？

我們現(xiàn)在輸入了一個長度是n的一個木頭。它可以變成n和0,，就是不切分,。可以變成1和n-1, 變成2和n-2,。一直截斷到多少呢,？可以變成n-n/2。

(0,n),(1, n-1),(2, n-2)...(n-n/2, n-n/2)

在這個情況下, 它分成1和n-1, n-1也面臨了類似的問題,。n-1是你直接返回n-1呢, 還是變成(1, n-2),，變成(2, n-3)。對于2,，其實也有也會面臨這樣一個問題,，是返回2呢，還是(2-1, 2-1),。如果我們要遍歷的話,，遍歷的就應該是一個樹,。把這個樹里面所有情況都找一遍，然后返回那個最大值就可以了,。

我們可以把所有的情況循環(huán)一遍，那我們現(xiàn)在來實現(xiàn)一下,，你會發(fā)現(xiàn)其實一點也不難,。

讓我們來先定義一下所有的價格：

我們要知道它的每一個商品直接的價錢，就是complete,，我們來定義一個complete_price,

complete_price = { i+1: p for i, p in enumerate(prices)}print(complete_price[9])---24

那如果這個時候是30,，就會出問題。

遇到這種問題的時候不要非要去判斷這個在不在里邊,可以直接用detaultdict, 它是是一個帶有默認值的Dictionary,，如果這個值不存在的話,，給它賦予一個默認值。

from collections import defaultdictcomplete_price = defaultdict(int)for i, p in enumerate(prices): complete_price[i+1] = pprint(complete_price[9])print(complete_price[30])

這個時候如果是30, 它就有一個結果了?，F(xiàn)在有了這樣的一個基礎數(shù)據,，我們假如要寫一個revenue,revenue就是營收，輸入長度是n,。

現(xiàn)在做一個很簡單的方法：

candidates等于價錢完全不切割是多少錢,。然后我們寫一個for循環(huán)：

for i in range(1, n):    pass

接下來我們做個拆分，拆分左邊就等于i, right就等于n-i:

這個時候整體的價格就等于complete_price[left], 再加完整的右邊, complete_price[right],。

total_r = complete_price[left] + complete_price[right]

這里其實是有問題的, 如果我們在這里假設n現(xiàn)在是100, 假設運行到i是50, 那么complete_price[50] 其實是一個沒有值的, 值是0,。

就是數(shù)據里沒有50的長度的價格，所以這個左邊和右邊其實是需要變成一個遞歸問題,。

現(xiàn)在寫法寫的稍微巧妙一些,，這個就是我們剛才所說的遍歷一遍，把所有的情況給拿出來,找到最大的返回出來,。目前為止這個方法完整的代碼如下：

def r(n):    candidates = [complete_price[n]]    for i in range(1, n):        left = i        right = n-i        total_r = r(left) + r(right)        candidates.append(total_r)    return max(candidates)

這個時候我們來調用一下：

這個22是怎么來的呢? 我們來看一下上面這段代碼, 首先8進方法之后,， 第2行告訴我們8完全不切割的話是多少，并賦值給candidates,。

緊接著把它變成了1和7,，2和6，3和5,，4和4這樣的問題,。

假如到6的時候，又會去求一下這個6,。右邊是要變成6,，那么6最大應該是多少。

這個代碼其實可以寫成更加Python化的方式,，我先寫一遍上面的,，是希望能讓大家知道這個代碼是怎么來的,，現(xiàn)在讓我們來用Python的方式來解決：

# 優(yōu)化為Python向def r(n):    return max([complete_price[n]] + [r(i) + r(n-i) for i in range(1, n)])print(r(8))---22

也就是，以上方法里定義的內容,，完全可以壓縮成一句話解決,。你們可以仔細的研究一下這兩段的相同點和差別。

現(xiàn)在的問題就是我們缺了一個記錄他中間分割步驟的內容,，這個也簡單,，我們稍微改變一下代碼，將return改為賦值,，然后給他加一個分割方法：

其中我們添加了(n, 0), 還有(i,n-i),。

然后我們還要給他加上最優(yōu)值：

optimal_price, split = max(candidates)

如果這其中你要是看不出邏輯過程，那你需要一些更多的練習,。好好的再去回去看看我之前寫的AI秘籍中的Python基礎教程篇,。

對于熟練的Python的工程師來說，應該熟悉這種方式才對,。第一次咱們實現(xiàn)的方法,，其實是C和Java的一種方法。如果是Python的話,，你需要熟悉Python,，直接會寫成這個樣子。

我們定義了一個candidates, 后面將風格方式定義進去并賦值給它,。

然后我們使用optimal_price來接收它的最優(yōu)價格,。

接著，我們添加一個solution變量,，solution是n的時候就找到了它的分割過程,。

最后，我們還是將最優(yōu)價格給返回出去,。

return optimal_price

來看一下solution[8]

我們如果在這里debug一下這個solution,，運行完之后solution如下：

是8的情況下變成6和2，現(xiàn)在就要看一下6的時候怎么切分,？6的時候變成6和0,。

好，現(xiàn)在我們來看一個更復雜的問題,，我們將它變成33, 33你會發(fā)現(xiàn)他運行的時間很久,。剛剛我們運行8，或者我們重新運行9的時候,，速度都還可以,，很快就能得到結果。但是運行33的時候就會非常的緩慢。知道這是為什么嗎,？

在這段代碼中,，現(xiàn)在有一個n，n接下來會拆分成了n-1個問題,，其實是要進行n-1個循環(huán),。那每個n-1的循環(huán)里面又有兩個調用了這個運算。所以在整個計算的次數(shù)的復雜性,，對于一個n來說,，它整個的運行時間應該是：2 * (n-1) * 2 * (n-2) * ... = 2^n * n!，就等于2的n次方再乘上n的階乘,。

這樣的話，結果就是它的運行時間會非常非常的久,。那我們就需要對代碼進行優(yōu)化了,。

如果現(xiàn)在仔細分析一下的話，會發(fā)現(xiàn)之所以運行的慢,，問題在于很多重復的值其實被重復運算了,。同樣是n-3這個事，不僅在n-1向下分支中會計算一次,，在其他的分支也會再計算很多次,。有很多的值是被重復運算了。

為了解決重復運算的問題,，我們可以做一個非常簡單的方法,。既然很多計算是重復的，那我定義一個變量去記錄這些曾經計算過的,，再遇到的時候就不要去計算不就完了：

cache = {}def r(n):    if n in cache: return cache[n]    ...    cache[n]  = optimal_price    return optimal_priceprint(r(33))---99

如果n在cache里面, 直接return cache[n], 如果它不在里邊的話就往下繼續(xù)運行,，每次求完解的之后，我們讓cache[n]等于optimal_price,。這樣就簡單多了,。

我們最后求了一下33，瞬間就得到了99的答案,。

這個cache其實是很簡單的一個東西,，但是它其實是很重要的一種思想。在一九二幾年,、三幾年的時候,，當時有一個數(shù)學家叫Richard Bellman。Bellman發(fā)現(xiàn)在整個數(shù)學計算中有相當?shù)囊活悊栴},，都牽扯到了一個相似的問題：over-lapping sub-problem,，就是子問題的重復。

Bellman就提出來了一種方法，他就說我們解決這種問題其實有一個很簡單的方法,，用一張表格,，不斷地記錄不斷地查表，就是不斷地寫表查表,。

就把值和結果都一一對應的寫入表中,，我們發(fā)現(xiàn)問題的時候，在這個表里面重新查一遍,，看一下有沒有這個值,，存不存在。

當時Bellman把這種方法叫做Dynamic,，不斷地,、持續(xù)地、變化的,、動態(tài)的,。programming在我們現(xiàn)在意思是編程，在一九二幾,、一九三幾年的時候,，是指把東西寫到表格里以及從表格里面拿出來。

那為什么后來演化成編程的意思,，因為早些時候,，馮諾伊曼當年制作的那個機器寫的是紙帶，就是給你一個一個的紙帶,，這個紙帶每一行會打八個洞,，就是當時馮諾伊曼最早的計算機。這8個洞里邊有一些是透光的,，有一些是不透光的,，其實就是一條一條計算機命令。

這其實也是一個寫表讀表的過程,，后來programming就有了編程的意思,。但是Bellman當年提出來的這個意思，Dandep programming就是不斷地寫表和查表,。它針對的是所有一切有這個over-lapping sub-problem的問題,，都可以用這種簡單的方法，可以大幅度的減少計算性,。

在很多地方學動態(tài)規(guī)劃的時候,，很多書上教動態(tài)規(guī)劃的時候往往是直接給一個解法。不知道您有沒有看過那些算法的書,，在動態(tài)規(guī)劃里往往會有一個表,，這個表格很重要,。

如果不用動態(tài)規(guī)劃的話，這個問題也是能解決的,。世界上幾乎所有的這種優(yōu)化問題不用動態(tài)規(guī)劃都是可以解決的,。但是理論上是要給你一個運算能力無限強，存儲空間無限大的計算設備,。

顯然不太可能,，所以我們就需要這樣寫到一個表格里邊，記一個記錄表格,。這個就是我們動態(tài)規(guī)劃的核心思想,。

關于「動態(tài)規(guī)劃的詳解」之后有機會我去專門寫個算法的相關課程，在這里就把動態(tài)規(guī)劃的核心思想給大家介紹了,。

我們現(xiàn)在來繼續(xù)看代碼,，剛才我們算了一下33這個值，得到了99,。但現(xiàn)在我們知道了能賣多少錢,，但是我們還不知道到底怎么個拆分法。

要拆分的話我們就要把這個solution給它parse一下,，再繼續(xù)定義一個方法：

我們看一下left和right,，將分割分別傳進來,，那如果left和right是0的話,，比如10， 寫成(10, 0),， 其實意思就是10就不用切分了,，直接返回left和right就可以了。

那如果說它里邊不是0,，假如說是37,，切分17和20，我們就要知道17該怎么分,，20該怎么分,。所以就返回:

return parse_solution(left, cut_solution) + parse_solution(right, cut_solution)

最后我們看到了18的切分結果，就被切分成[10, 6, 2],。

具體的切割過程也可以獲得,。

在Python里邊呢這個是一個非常非常經典的動態(tài)規(guī)劃問題。經過一個比較簡單的方法,，把重復問題給解決了,。

再跟大家普及一個知識，在Python里面有一個好處就是它把很多常見的功能其實都已經想到,，做了切分了,。

比方說Python自帶的庫里面就有一個functools, 它有一個lru_cache，就是least recent used, 最近最少使用。

我們如果在直接寫一個cache,，它會存在一個問題,。當n特別大的時候，那么cache的size也會變得特別的大,。這個時候我們就需要一種機制,，來讓cache保留最需要保留的東西，保留那些最重要的東西,，不要把所有的信息全部弄進去,。

這個lru_cache幫我們實現(xiàn)了這個功能,它會把最近最少使用過的這些值刪去, cache的這個size會保持在一個比較固定的范圍內。

這個函數(shù)是一個裝飾器,，小伙伴們是否還記得我在Python課程中介紹過裝飾器以及其使用,？

我們來使用一下這個裝飾器:

這里定義了一下maxsize等于2的10次方，就是最多可以存2的10次方個值,。

那這里和我們方法里的這一段內容其實是一摸一樣：

if n in cache: return cache[n]...cache[n] = optimal_price

當我們調用這個函數(shù)的時候, 如果函數(shù)的參數(shù)曾經被計算過,，那么就直接返回這個值。如果沒有被計算過,，就計算一遍,，再把這個值寫下來。

那我們使用了這個裝飾器之后,，我們對cache的使用的這兩句代碼就可以刪掉了,。

lru_cache的作用都懂了吧？以后遇到一個程序很慢的時候,，就可以用它來做優(yōu)化,。

那其實今天這節(jié)課程把這個函數(shù)看懂，幾乎所有的動態(tài)規(guī)劃的問題的主體思路就都懂了,。因為所有的動態(tài)規(guī)劃的問題都包含了以下幾個問題：

1. 識別子問題 sub-problems dividing

2. 識別子問題中的重疊特點 over-lapping sub-problem

3. 存儲子問題的答案 cache sub-solutions

4. 合并問題答案 combine solutions

5. 解析答案 parse solutions

這是所有的動態(tài)規(guī)劃的特點,，當你發(fā)現(xiàn)一個問題可以被分解成子問題，而且子問題有重復的時候,，就可以用這種方法去優(yōu)化它,。

以后大家面試，大概率會遇到這種問題,。只要按照這個方法來思考的話問題基本上就不大了,。

但是動態(tài)規(guī)劃其實也是有一個極限，曾經有一段時間人們以為動態(tài)規(guī)劃可以解決很多問題,，幾乎可以解決所有常見的問題,。但是后來人們發(fā)現(xiàn)，當限制條件特別多,，或者問題已經復雜到非常難的去識別此問題了,?？赡芩前俗訂栴}的關系，但是因為這個問題太復雜了,，所以我們沒辦法去把它分割出來,，我們沒有辦法去識別它。

動態(tài)規(guī)劃是一種思維方法,，一種思維類型,。比方計算機里面的圖論問題，并不是只能把它變成圖論問題,，不用圖論完全可以解決,，但是不太好弄。

所以,，動態(tài)規(guī)劃其實也有它的局限性,，人們?yōu)榱私鉀Q更多問題就提出了更多的方法，其中一種方法就叫做機器學習,。

好,，我們下節(jié)課，就好好的來講講機器學習,。本節(jié)課的最后,，我將之前咱們寫的那段代碼完整版貼在這里：