乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

對應的圖像形象表達如下:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

對應的圖像形象表達如下:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

對應的圖像形象表達如下:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:Hessian等價於梯度的Jacobian矩陣。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

對應的圖像形象表達如下:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:Hessian等價於梯度的Jacobian矩陣。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

這些知識是前置知識,下面都要用到,記住兩個特殊矩陣指的是什麼?然後偏導數是什麼?

4函數導數為零的二三事

注意:為了便於理解,下面將詳細分析導數為0在低維的情況,而在高維情況下都是類似的。下面先介紹一些概念:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

對應的圖像形象表達如下:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:Hessian等價於梯度的Jacobian矩陣。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

這些知識是前置知識,下面都要用到,記住兩個特殊矩陣指的是什麼?然後偏導數是什麼?

4函數導數為零的二三事

注意:為了便於理解,下面將詳細分析導數為0在低維的情況,而在高維情況下都是類似的。下面先介紹一些概念:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

以上都是在一元函數中的定義,如下圖所示,而二維或以上可簡單推之:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

對應的圖像形象表達如下:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:Hessian等價於梯度的Jacobian矩陣。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

這些知識是前置知識,下面都要用到,記住兩個特殊矩陣指的是什麼?然後偏導數是什麼?

4函數導數為零的二三事

注意:為了便於理解,下面將詳細分析導數為0在低維的情況,而在高維情況下都是類似的。下面先介紹一些概念:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

以上都是在一元函數中的定義,如下圖所示,而二維或以上可簡單推之:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

鞍點 (saddle point): 目標函數在此點上的梯度(一階導數)值為 0, 但從改點出發的一個方向是函數的極大值點,而在另一個方向是函數的極小值點。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

對應的圖像形象表達如下:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:Hessian等價於梯度的Jacobian矩陣。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

這些知識是前置知識,下面都要用到,記住兩個特殊矩陣指的是什麼?然後偏導數是什麼?

4函數導數為零的二三事

注意:為了便於理解,下面將詳細分析導數為0在低維的情況,而在高維情況下都是類似的。下面先介紹一些概念:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

以上都是在一元函數中的定義,如下圖所示,而二維或以上可簡單推之:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

鞍點 (saddle point): 目標函數在此點上的梯度(一階導數)值為 0, 但從改點出發的一個方向是函數的極大值點,而在另一個方向是函數的極小值點。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

對應的圖像形象表達如下:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:Hessian等價於梯度的Jacobian矩陣。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

這些知識是前置知識,下面都要用到,記住兩個特殊矩陣指的是什麼?然後偏導數是什麼?

4函數導數為零的二三事

注意:為了便於理解,下面將詳細分析導數為0在低維的情況,而在高維情況下都是類似的。下面先介紹一些概念:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

以上都是在一元函數中的定義,如下圖所示,而二維或以上可簡單推之:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

鞍點 (saddle point): 目標函數在此點上的梯度(一階導數)值為 0, 但從改點出發的一個方向是函數的極大值點,而在另一個方向是函數的極小值點。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

對應的圖像形象表達如下:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:Hessian等價於梯度的Jacobian矩陣。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

這些知識是前置知識,下面都要用到,記住兩個特殊矩陣指的是什麼?然後偏導數是什麼?

4函數導數為零的二三事

注意:為了便於理解,下面將詳細分析導數為0在低維的情況,而在高維情況下都是類似的。下面先介紹一些概念:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

以上都是在一元函數中的定義,如下圖所示,而二維或以上可簡單推之:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

鞍點 (saddle point): 目標函數在此點上的梯度(一階導數)值為 0, 但從改點出發的一個方向是函數的極大值點,而在另一個方向是函數的極小值點。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上圖列出臨界點的類型。在一維情況下,三種臨界點的示例。臨界點是斜率為零的點。這樣的點可以是 局部極小點(local minimum),其值低於相鄰點; 局部極大點(local maximum),其值高於相鄰點; 或鞍點,同時存在更高和更低的相鄰點

使 f(x)取得絕對的最小值(相對所有其他值)的點是 全局最小點(globalminimum)。函數可能有一個全局最小點或存在多個全局最小點,還可能存在不是全局最優的局部極小點。

在機器學習和深度學習的背景下,我們要優化的函數可能含有許多不是最優的局部極小點,或者還有很多處於非常平坦的區域內的鞍點。

尤其是當輸入是多維的時候,所有這些都將使優化變得困難。因此,我們通常尋找使 非常小的點,但這在任何形式意義下並不一定是最小。方向導數和梯度方向導數和梯度

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

推薦閱讀時間:8~15min

主要內容(下劃線部分):

1、計算複雜性與NP問題

2、上溢和下溢

3、導數,偏導數及兩個特殊矩陣

4、函數導數為零的二三事

5、方向導數和梯度

6、梯度有什麼用

7、梯度下降法

8、牛頓法

1計算複雜性與NP問題

算法的複雜性:現實中大多數問題都是離散的數據集,為了反映統計規律,有時數據量很大,而且多數目標函數都不能簡單地求得解析解。而為了記錄在解決問題的算法的性能或者說好壞,就引入了算法的複雜性。

算法理論被認為是解決各類現實問題的方法論。而衡量算法理論的計算複雜度可分為:時間複雜度和空間複雜度,這是對算法執行所需要的兩類資源——時間和空間的估算。其中,算法的時間複雜度是一個函數,它定性描述了該算法的運行時間,空間複雜度是對一個算法在運行過程中臨時佔用存儲空間大小的量度

另為,一般的,衡量問題是否可解的重要指標是:該問題能否在多項式時間內求解,還是隻能在指數時間內求解?在各類算法理論中,通常使用多項式時間算法即可解決的問題看作是易解問題,需要指數時間算法解決的問題看作是難解問題。

指數時間算法的計算時間隨著問題規模的增長而呈指數化上升,這類問題雖然有解,但並不適用於大規模問題。所以當前算法研究的一個重要任務就是將指數時間算法變換為多項式時間算法。

確定性和非確定性 :除了問題規模與運算時間的比較,衡量一個算法還需要考慮確定性和非確定性的概念。

先說說自動機:是有限狀態機(FSM)的數學模型。實際上是指一種基於狀態變化進行迭代的算法。也就是在給定輸入和狀態時,自動機的狀態會發生改變的模型。在算法領域常把這類算法看作一個機器,比較知名的有圖靈機、玻爾茲曼機、支持向量機等。或者,在日常生活中的自動售賣機就是一種有限狀態機。

確定性:所謂確定性,是指針對各種自動機模型,根據當時的狀態和輸入,若自動機的狀態轉移是唯一確定的,則稱具有確定性;

非確定性:若在某一時刻自動機有多個狀態可供選擇,並嘗試執行每個可選擇的狀態,則稱具有不確定性。

換個說法就是:確定性是程序每次運行時產生下一步的結果是唯一的,因此返回的結果也是唯一的;非確定性是程序在每個運行時執行的路徑是並行且隨機的,所有路徑都可能返回結果,也可能只有部分返回結果,也可能不返回結果,但是隻要有一個路徑返回結果,那麼算法就結束。

NP問題:簡單的說,存在多項式時間的算法的一類問題,稱之為P類問題;在多項式時間內可由非確定機解決的一類問題,稱之為NP問題。另外,很多人相信P類問題是NP問題的一個子集,但既沒有人證明出有某個問題屬於NP但不屬於P,也沒有人證明所有NP問題都能在多項式時間內有解,如圖:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

P類問題:就是能夠以多項式時間的確定性算法來對問題進行判定或求解,實現它的算法在每個運行狀態都是唯一的,最終一定能夠確定一個唯一的結果——最優的結果。

NP問題:是指可以用多項式時間的非確定性算法來判定或求解,即這類問題求解的算法大多是非確定性的,但時間複雜度有可能是多項式級別的。

對於上面的知識,我們只要瞭解知道他們的概念就好了,機器學習中多數算法都是針對NP問題(包括NP完全問題)的。

2上溢和下溢

下溢:當接近零的數被四捨五入為零時發生下溢。許多函數會在其參數為零而不是一個很小的正數時才會表現出質的不同。例如,我們通常要避免被零除。

上溢(overflow):當大量級的數被近似為 或者 時發生上溢。進一步的運算通常將這些無限值變為非數字。

為什麼會下溢或者上溢:數字計算機上實現連續數學的基本困難是我們需要通過有限數量的位模式來表示無限多的實數,這意味著我們在計算機中表示實數時幾乎都會引入一些近似誤差。在許多情況下,這僅僅是舍入誤差。如果在理論上可行的算法沒有被設計為最小化舍入誤差的累積,可能會在實踐中失效,也就是可能產生下溢或者上溢

一個例子:必須對上溢和下溢進行數值穩定的一個例子是softmax 函數。softmax 函數經常用於預測與Multinoulli分佈相關聯的概率,定義為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

當式中的都是很小的負數時,就會發生下溢,這意味著上面函數的分母會變成0,導致結果是未定的;同理,當式中的是很大的正數時,就會發生上溢導致結果是未定的。

這個概念是比較重要的,我們需要了解清除!

3導數和偏導數

導數: 當函數定義域和取值都在實數域中的時候,導數可以表示函數曲線上的切線斜率。 當然除了切線的斜率,導數還表示函數在該點的變化率。或者從物理意義來說,就是瞬時變化率。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上面是一維導數的定義式,其中涉及極限的知識,簡單來說極限就是“無限靠近而永遠不能到達”,當然,高中初中就學過導數,這個也可以用之前斜率的角度去理解,多維的話也就是在此之上的推廣。

將上面的公式轉化為下面圖像為:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:在一元函數中,只有一個自變量變動,也就是說只存在一個方向的變化率,這也就是為什麼一元函數沒有偏導數的原因。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

對應的圖像形象表達如下:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

注意:Hessian等價於梯度的Jacobian矩陣。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

這些知識是前置知識,下面都要用到,記住兩個特殊矩陣指的是什麼?然後偏導數是什麼?

4函數導數為零的二三事

注意:為了便於理解,下面將詳細分析導數為0在低維的情況,而在高維情況下都是類似的。下面先介紹一些概念:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

以上都是在一元函數中的定義,如下圖所示,而二維或以上可簡單推之:

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

鞍點 (saddle point): 目標函數在此點上的梯度(一階導數)值為 0, 但從改點出發的一個方向是函數的極大值點,而在另一個方向是函數的極小值點。

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上圖列出臨界點的類型。在一維情況下,三種臨界點的示例。臨界點是斜率為零的點。這樣的點可以是 局部極小點(local minimum),其值低於相鄰點; 局部極大點(local maximum),其值高於相鄰點; 或鞍點,同時存在更高和更低的相鄰點

使 f(x)取得絕對的最小值(相對所有其他值)的點是 全局最小點(globalminimum)。函數可能有一個全局最小點或存在多個全局最小點,還可能存在不是全局最優的局部極小點。

在機器學習和深度學習的背景下,我們要優化的函數可能含有許多不是最優的局部極小點,或者還有很多處於非常平坦的區域內的鞍點。

尤其是當輸入是多維的時候,所有這些都將使優化變得困難。因此,我們通常尋找使 非常小的點,但這在任何形式意義下並不一定是最小。方向導數和梯度方向導數和梯度

乾貨|掌握機器學習數學基礎之優化「1」(重點知識)

上圖展示了近似最小化,當存在多個局部極小點或者平坦區域時,優化算法可能無法找到全局最小點,在機器學習和深度學習中,即使找到的解不是真正最小的,但只要它們對應於代價函數顯著低的值,我們通常就能接受這樣的解。

這些知識點都是基本知識,不做過多解釋,低維的我們理解了,高維的就類推就行了,比如高維也臨界點也有局部最優或者鞍點的情況。但在深度學習中優化算法比如SGD往往可以避免鞍點,然後使得其效果不錯,這也是深度學習為什麼可行的一個原因吧。

End.

運行人員:中國統計網小編(微信號:itongjilove)

微博ID:中國統計網

中國統計網,是國內最早的大數據學習網站,公眾號:中國統計網

//www.itongji.cn

相關推薦

推薦中...