機器/深度學習中的參數優化原理初探

機器/深度學習中的參數優化原理初探

1. 最小二乘估計法

0x1：最小二乘估計的發展曆史

最小二乘法(Least Squares Method,簡記為LSE)是一個比較古老的方法，源于天文學和測地學上的應用需要。

在早期數理統計方法的發展中，這兩門科學起了很大的作用。丹麥統計學家霍爾把它們稱為“數理統計學的母親”。此後近三百年來，它廣泛應用于科學實驗與工程技術中。美國統計史學家斯蒂格勒( S. M. Stigler)指出, 最小二乘方法是19世紀數理統計學的壓倒一切的主題。1815年時,這方法已成為法國、意大利和普魯士在天文和測地學中的标準工具,到1825年時已在英國普遍使用。

追溯到1801年，意大利天文學家朱賽普·皮亞齊發現了第一顆小行星谷神星。經過40天的跟蹤觀測後，由于谷神星運作至太陽背後，使得皮亞齊失去了谷神星的位置。随後全世界的科學家利用皮亞齊的觀測資料開始尋找谷神星，但是根據大多數人計算的結果來尋找谷神星都沒有結果。時年24歲的高斯也計算了谷神星的軌道。奧地利天文學家海因裡希·奧爾伯斯根據高斯計算出來的軌道重新發現了谷神星。高斯于其1809年的著作《關于繞日行星運動的理論》中。在此書中聲稱他自1799年以來就使用最小二乘方法,由此爆發了一場與勒讓德的優先權之争。

近代學者經過對原始文獻的研究,認為兩人可能是獨立發明了這個方法,但首先見于書面形式的，以勒讓德為早。然而,現今教科書和著作中,多把這個發明權歸功于高斯。其原因,除了高斯有更大的名氣外,主要可能是因為其正态誤差理論對這個方法的重要意義。

勒讓德在其著作中,對最小二乘方法的優點有所闡述。然而,缺少誤差分析。我們不知道,使用這個方法引起的誤差如何,就需建立一種誤差分析理論。

高斯于1823年在誤差e1 ,… , en獨立同分布的假定下,證明了最小二乘方法的一個最優性質: 在所有無偏的線性估計類中,最小二乘方法是其中方差最小的！

在德國10馬克的鈔票上有高斯像，并配了一條正态曲線。在高斯衆多偉大的數學成就中挑選了這一條,亦可見這一成就對世界文明的影響。

現行的最小二乘法是勒讓德( A. M. Legendre)于1805年在其著作《計算慧星軌道的新方法》中提出的。它的主要思想就是選擇未知參數，使得理論值與觀測值之差的平方和達到最小：

我們現在看來會覺得這個方法似乎平淡無奇,甚至是理所當然的。這正說明了創造性思維之可貴和不易。從一些數學大家未能在這個問題上有所突破,可以看出當時這個問題之困難。歐拉、拉普拉斯在許多很困難的數學問題上有偉大的建樹,但在這個問題上未能成功。

在高斯發表其1809年著作之前，約在1780年左右,拉普拉斯已發現了機率論中的“中心極限定理”。

根據這個定理，大量獨立的随機變量之和,若每個變量在和中起的作用都比較小，則和的分布必接近于正态。

測量誤差正具有這種性質。一般地說,随機(而非系統)的測量誤差，是出自大量不顯著的來源的疊加。是以，中心極限定理給誤差的正态性提供了一種合理的理論解釋。這一點對高斯理論的圓滿化很有意義,因為高斯原來的假定(平均數天然合理)總難免給人一種不自然的感覺。

耐人尋味的是,無論是中心極限定理的發明者拉普拉斯,還是早就了解這一結果的高斯,都沒有從這個結果的啟示中去考察誤差分布問題。對前者而言,可能是出于思維定勢的束縛,這對拉普拉斯來說可算不幸,他是以失掉了把這個重要分布冠以自己名字的機會(正态分布這個形式最早是狄莫弗( De Moiv re) 1733年在研究二項機率的近似計算時得出的。以後也有其他學者使用過,但都沒有被冠以他們的名字。高斯之是以獲得這一殊榮,無疑是因為他把正态分布與誤差理論聯系了起來) 。

可以說,沒有高斯的正态誤差理論配合, 最小二乘方法的意義和重要性可能還不到其現今所具有的十分之一。最小二乘方法方法與高斯誤差理論的結合,是數理統計史上最重大的成就之一,其影響直到今日也尚未過時！

0x2：從一個日常的例子來看最小二乘估計的思想

1. 求平均數 - 數學直覺

來看一個生活中的例子。比如說，有五把尺子：

用它們來分别測量一線段的長度，得到的數值分别為（顔色指不同的尺子）：

這5次測量本質上就是代表了5次實驗觀測得到的觀測樣本。這種現象在實際的工程項目中是十分常見的，甚至可以說是百分百出現的，即樣本噪音或樣本偏差問題。

之是以出現不同的值可能因為：

• 不同廠家的尺子的生産精度不同
• 尺子材質不同，熱脹冷縮不一樣
• 測量的時候心情起伏不定
• ....

這種情況下，一個直覺的解決思路是：取平均值來作為線段的長度。

這種解決思路是最符合”直覺“的，但是有人可能會提出質疑：

• 這樣做有道理嗎？
• 用調和平均數行不行？
• 用中位數行不行？
• 用幾何平均數行不行？

2. 用最小二乘估計的思路來解這個問題

首先，把測試得到的值畫在笛卡爾坐标系中，分别記作

 ：

其次，把要猜測的線段長度的真實值用平行于橫軸的直線來表示（因為是猜測的，是以用虛線來畫），記作

每個點都向

 做垂線，垂線的長度就是

 ，也可以了解為測量值和真實值之間的誤差：

因為誤差是長度，取絕對值計算計算比較複雜，是以設計者用平方來代表誤差：

誤差的平方和就是（

 代表誤差）：

下面的動圖表示了

在不斷變化下，誤差的變化情況。

自然，誤差的平方和

 在不斷變化的。

法國數學家，阿德裡安-馬裡·勒讓德提出了一個劃時代的定理：讓總的誤差的平方最小的

 就是真值。這是基于，如果誤差是随機的，應該圍繞真值上下波動。

勒讓德的想法變成代數式就是：

這是一個二次函數，對其求導，導數為0的時候取得最小值：

化簡得：

可以看到正好是算術平均數。這個巧合在1元1次方程中是剛好成立的，也就是說，算數平均是最小二乘估計的一個特例。

3. 最小二乘估計法

最小二乘估計法包含兩個基本的元素：

1. 利用平方作為評價名額。要注意的是，深度學習中的平方損失函數隻是一個名額，即用平方的方式進行損失函數的評估，不要和最小二乘法混淆。
2. 利用求導極值的方式，直接得到全局最優值。這點是最小二乘估計和梯度下降這種疊代算法最大的差別。      

筆者插入：這裡需要注意的是，導數為0并不是得到極值的充要條件，隻是一個必要條件，對于多元高階方程組，通過求導極值并不能保證得到最優值。

0x3：最小二乘估計的适用範圍

最小二乘估計是一個通用的未知參數最優化方案，它可以對任何的模型進行參數優化。

從曆史的角度來說，最小二乘估計的出現是因為當時回歸模組化的出現以及對回歸模型進行參數估計的需求。

是以我們先花一些時間，來讨論下回歸模型。

0. 回歸模型

回歸模型來源于當時科學和工程領域一個很基本的問題，數學模組化。模組化的思想在處理統計資料分析的每一個學科中都很有用。

例如，假設給定一個随機變量集，要完成的任務是：找到可能存在于這些變量之間的關系，如果這種關系存在的話。

作為函數逼近的一種特殊形式，回歸的典型方案如下：

1. 選擇随機變量中的一個變量作為關注變量，這一随機變量被稱為依賴變量，或者響應變量（response）
2. 剩下的随機變量稱為獨立變量，或者回歸量（regressor）。它們的作用是用來解釋或者預測響應的統計行為。
3. 響應對回歸量的依賴還包括一個附加的誤差項，用來說明在對依賴程度公式化時候的不确定性。誤差項稱為期望誤差（expectational error）或解釋誤差（explanational error）      

上述這樣的模型稱為回歸模型（regression model）。

回歸模型有很多種類，例如我們熟知的線性回歸模型就是其中一種：

1. Linear Regression線性回歸
2. Logistic Regression邏輯回歸
3. Polynomial Regression多項式回歸
4. Stepwise Regression逐漸回歸
5. Ridge Regression嶺回歸
6. Lasso Regression套索回歸
7. ElasticNet回歸       

在對具體問題模組化的時候，要選取哪種模型呢？這個問題似乎沒有最佳答案，需要具體問題具體分析，結合專家知識，領域經驗來標明最适合的模型。例如我們在量化交易中第一步要做的事情是設計一個符合股市曆史波動的回歸模型，而公式的形式各家量化交易公司都不一樣，這裡面考驗的就是對股市交易的本質了解了。

我們通過一個簡單例子來讨論這個問題，比如溫度與冰淇淋的銷量（一個自變量、一個因變量）：

1. 線性回歸估計

可以假設這種線性關系為：

上圖的

 分别為：

總誤差的平方為：

不同的

 會導緻不同的

 ，根據多元微積分的知識求偏導：

這個時候

 取最小值。對于

 而言，上述方程組為線性方程組，用之前的資料解出來：

也就是這根直線：

2. 非線性回歸估計

同一個問題，還可以假設（這其實就是數學模組化過程）：

在這個假設下，可以根據最小二乘法（求導極值），算出

 ，得到下面這根紅色的二次曲線：

3. 任意模型的最小二乘估計

同一組資料，選擇不同的

 ，通過最小二乘法可以得到不一樣的拟合曲線

0x4：最小二乘法和矩陣投影的關系 - 最小二乘估計的的幾何解釋

從矩陣投影的角度來看最小二乘，最小二乘法的本質是最小化系數矩陣所張成的向量空間到觀測向量的歐式誤差距離。

我們從幾何的角度來幫助我們了解其中的概念含義。

1. 線性方程組的幾何意義

為了從幾何的角度解釋最小二乘法，我們先回顧一下，線性方程組的幾何意義。線性方程組可以從行和列兩個角度看。 

舉例，看如下簡單的線性方程組：

1）從行的角度看

線性方程組的解就是直線a和直線b的交點，這一點應該誰都知道，如下圖所示：

從圖上很容易可以看出該線性方程組的解為x1=1，x2=2

從行的角度看，線性方程組的每一行都代表空間中的幾何圖形（二維時是直線，三維時是平面，高維時是高維空間中的一個”平面“），線性方程組的解就是這些圖形的交點or交線or交面。 

2）從列的角度看

從列的角度看時，先把上面的線性方程組寫成矩陣的形式

再把上式拆開，寫成下面這個樣子

表示向量 a1 的 x1 倍加上向量 a2 的 x2 倍等于向量 b 。這種角度就是從列向量的角度看線性方程組。該方程的解已經從行的角度看出來了，為x1=1，x2=2，于是我們把向量a1,a2,b畫到下面這張圖上：

向量 a1 的1倍加上向量 a2 的2倍剛好等于向量 b，而倍數1和2,就是我們的解 x1 和 x2

從列的角度看線性方程組Ax=b的解，就是為系數矩陣A裡的每一列都尋找一個合适的倍數，使每一列乘上這個倍數後再相加剛好等于向量b，這個倍數就是解。本質上就是找到A裡的列向量的一個線性組合使之等于b。

2. 最小二乘法就是解一個無解的線性方程組

這個topic是一個筆者認為非常重要意義的概念。

在機器/深度學習或者統計學任務中，我們基本上不可能找到一個100%

matched的model來對目标問題域進行模組化（我們沒有上帝視角），也即真實實體模型是非常難擷取的，像愛因斯坦質能方程那種跨世紀的發現在大多數的業務場景中都難以得到。是以，統計學家和機器學習工作者隻能退而求其次，尋找一個“大緻能拟合（盡可能拟合）”的模型來描述目标問題域。尋找這個大緻拟合的模型的方法之一就是最小二乘法。

我們從一個最簡單的例子開始，已知平面上有3個點(1,2)，(0,2)，(2,3)  

我們想用一條直線去拟合它。如上所述，我們沒有上帝視角，是以我們并不知道真實實體模型的函數形式。

我們隻能尋找一個大緻能拟合的模型，這個過程筆者相信大家都經曆過，例如在深度學習中編寫網絡結構的代碼（DNN/LSTM/CNN層等），通過建立高斯模型的假設進行異常發現。

回到這個簡單的線性例子，我們現在設這條直線的方程為 y=kx+b 。我們希望這條直線可以同時通過這三個點（100%拟合），也就是這條直線的參數要滿足:

從圖中直覺的看，沒有一條直線可以同時過這三個點，是以這個方程是無解的。怎麼解一個無解的方程組呢？

為了表述友善，我們換一下符号，用x1表示k，用x2表示b。即：

寫成矩陣形式：

從列的角度看：

一但化成列的形式，我們就很自然想到把向量a1，a2，b 畫到圖上:

要找到解，就要找到a1，a2的一個線性組合，使得組合後的向量剛好等于b。可惜的是，根據向量相加的原理，任何的a1和a2線性組合，隻可能出現在a1,a2所在的平面S上（這個平面S就是a1和a2組成的向量空間），但是向量b不在平面S上，如下圖。不可能找到解：

找不到完美的解，就隻能找到一個最接近的解。是以現在問題轉換為了哪個解是最接近的解。

我們的思路是在平面S上找一個最接近向量b的向量來代替向量b，記這個替代品向量為P。是以現在問題又轉換為了如何評價最接近向量b。

根據向量相關性的内積定理，和向量b相關性最高的向量就是過向量b的終點做平面S 的垂線（也就是做投影），垂足就是代替向量P（最接近向量b的向量）的終點。

P與b之間的誤差：e=b−P

原來的方程為Ax=b是無解的，我們用P代替b後，P在a1a2所在的平面上，是以現在方程Ax̂ =P就有解了。

但是這個解和目标真實值之間存在誤差，誤差為：

此時，誤差向量e一定是垂直于平面S的，也就是要垂直于a1和a2。垂直在數學上是有明确公式表示的。也就是e∙a1=0，e∙a2=0，用矩陣表示出來就是

，即：

綜合上面公式得：

，化簡一下就是

，是以最佳的近似解就是

這樣，按公式解出的解出了最近似的解為(1/2,11/6)。 

從列的角度，我們就可以用a1和a2的線性組合來表示P，下圖所示

那麼最優的直線的斜率和截距就是我們解出的k=1/2，b=11/6=1.8333。如下圖

0x5：最小二乘估計和最大似然估計的關系 - 從機率統計的角度來看

最小二乘估計的基本假設是：

這個假設真的合理嗎？數學王子高斯（1777－1855）也像我們一樣心存懷疑。

高斯換了一個思考架構，通過機率統計的思維架構來思考。

讓我們回到最初測量線段長度的問題。高斯想，通過測量得到了這些值：

每次的測量值

 都和線段長度的真值

 之間存在一個誤差：

根據大數定理，誤差本身也屬于非系統随機變量，是以這些誤差最終會形成一個機率分布，隻是現在不知道誤差的機率分布是什麼。假設機率密度函數為：

假設一個誤差的聯合機率，把所有的測量資料整合起來：

把

 作為變量的時候，上面就是似然函數了。關于極大似然估計的讨論，可以參閱我的另一篇blog。

 的圖像可能是這樣的：

根據極大似然估計的思想，L(x)的極大似然估計最應該是下面這點：

從最優化的角度來看，當下面這個式子成立時，取得最大值：

筆者插入：極大似然估計得到的極大似然點也我們用求導極值求最優點，在數學公式上是一緻的，讀者在看到這裡的時候有沒有體會到一種極緻的美感。

如果最小二乘法是對的，那麼

 時應該取得最大值，即：

現在可以來解這個微分方程了。最終得到：

可以看到，這就是一個正态分布，并且這還是一個充要條件：

也就是說，如果誤差的分布是正态分布，那麼最小二乘法得到的就是極大似然的值。

接下來問題來了，那麼誤差的分布是正态分布嗎？

如果誤差是由于随機的、無數的、獨立的、多個因素造成的，比如之前提到的：

• ......

那麼根據中心極限定理，誤差的分布就應該是正态分布。

Relevant Link: 

https://www.zhihu.com/question/20447622
https://blog.csdn.net/Macer3/article/details/48394239 
https://www.zhihu.com/question/37031188
https://www.zhihu.com/question/20447622
https://blog.csdn.net/Macer3/article/details/48394239
https://www.zhihu.com/question/37031188
      

2. 維納濾波器 - 一種負回報自動控制系統

0x1：維納的生平簡略

諾伯特·維納（Norbert Wiener，1894年11月26日－1964年3月18日），生于美國密蘇裡州哥倫比亞，美國應用數學家，在電子工程方面貢獻良多。他是随機過程和噪聲信号處理的先驅，又提出“控制論”一詞。

他主要在哥廷根和劍橋，研究布朗運動、傅裡葉變換、調和分析、狄利克雷問題和Tauber型定理（Abelian and tauberian theorems）等。1929年維納指導當時在貝爾電話公司學習的博士生李郁榮研制了李-維納網絡，獲得美國專利。1935年維納應國立清華大學校長梅贻琦和數學系主任熊慶來之聘，到清華大學講學，主講傅立葉變換，聽講者包括華羅庚、段學複等。維納曾推薦華羅庚和徐賢修合寫的論文發表在麻省理工學院的《數學實體學報》（上）

二戰時，他在槍炮控制方面工作，引發了他對通訊理論和回報的興趣，著《控制論：或關于在動物和機器中控制和通信的科學》一書，促成了控制論的誕生。

http://www.ee.cityu.edu.hk/~gchen/pdf/Wiener_S.pdf      

維納的個人履曆實在令人望而生畏，他真的将各種領域的知識融合在了一起。同時，他創造了自動控制理論，深刻地影響了機器/深度學習的發展曆程。神經元模型以及GD梯度下降的發明也是基于自動控制理論基礎上創立的。

筆者思考：

自動負回報控制理論，從另一個角度讨論了一個資訊處理系統如何達到穩态（即找到最優參數）。

筆者任務其核心思想是：比起一次接受所有曆史狀态資訊，通過最小二乘估計得到最優參數。資訊系統其實可以将時間序列切片，通過隻擷取一個有限時間段内的資訊，對通過濾波器後的資訊誤差進行評估，進而對系統本身進行負回報調節，這種方式最終可以讓系統趨向于穩态。

這也是GD（梯度下降）思想的核心之一，當然，GD本身還解決了對高維多元随機變量求極值的計算複雜度問題，GD本身是易于通過計算機實作的。

0x2：數字濾波器的基本概念以及它和機器學習算法的關系

數字濾波器是數字信号進行中使用得罪廣泛的一種線性系統環節，是數字信号處理的重要基礎。

數字濾波器的本質是将一組輸入的數字序列通過一定的運算後轉變為另一組輸出的數字序列。

1. 濾波器的定義

實作濾波處理的運算電路、或裝置稱為濾波器。

2. 濾波的定義

對輸入信号通過一定的處理得到輸出信号，這個處理通常是濾除輸入信号的某些頻率成分；保留信号中某些頻率範圍内的有用信号成分。是以把這種處理的過程稱為濾波。

筆者思考：CNN卷積網絡的訓練過程展現了非常明顯的濾波過程，CNN網絡在訓練樣本資料的過程中，會自動地保留樣本資料中和target有關的“關鍵性像素區域”，例如小貓識别任務中，CNN會保留圖像樣本中各種姿勢的貓，而對背景這些“備援資訊”會逐漸通過權重調整過濾掉，從某種程度上來說，這就是一種濾波過程。

3. 自适應濾波器結構 - 一種包含負回報的神經元模型

幾乎是以的機器學習算法的參數優化（訓練）過程都包含負回報，算法通過在訓練中不斷根據本輪疊代的預測結果和目标結果之間的差距來動态調整自己的負回報，進而逐漸将權值參數調整到”盡量完美“的狀态（即拟合）。

下圖是一個未知動态系統的流程方框圖，由包含元素

的輸入向量所刺激，其中 i 是刺激（激勵）應用于系統時的瞬時時間，作為時間序列的索引。

作為對刺激的相應，系統産生一個輸出 y(i) 作為相應。是以，次系統的外部行為由下述資料集描述：

從數字信号的時空特性角度來看，刺激向量 x(i) 能夠以兩種根本不同的方式出現，一種是空間的，另一種是空間的：

1. x(i) 的 M 個元素代表空間中的不同點，輸入向量 x(i) 的維數 M 稱為輸入空間的維數，或簡稱輸入維數。在這種情況下我們稱 x(i) 為資料的瞬像（snapshot）
2. x(i) 的 M 個元素代表在時間上均勻分布的某個刺激，的現在和（M-1）個過去的值組成的集合。即它是時域累計刺激。      

我們現在面對的問題是如何通過建立一個簡單線性神經元來設計未知動态系統的一個多輸入-單輸出模型（即濾波器模型）。

這個神經元模型是在一個算法的影響下運作的，此算法控制對神經元的突觸權值的必要調整，同時記住以下要點：

1. 此算法從任意設定的一個神經元突觸權值開始。這意味着模組化者不需要對目标問題域有先驗知識。
2. 為相應系統行為的統計變化，突觸權值的調整是建立在連續的基礎之上的，即把時間加進算法中，權值的調整是連續進行的。
3. 調整突觸權值的計算在長度為一個采樣周期的時間段内完成。      

這樣描述的神經元模型稱為“自适應濾波器（adaptive filter）”，而其中負責進行調整的算法理論就是LMS（最小均方算法），LMS我們放到下一個章節來展開讨論，我們這裡先關注濾波器系統本身。

雖然是在作為系統辨識（system identification）的任務背景下給出的描述，但自适應濾波器的特征還是有很廣泛的應用。

下圖是一個自适應濾波器的示意圖，它的運作由兩個連續過程組成：

1. 過濾過程（濾波過程），涉及兩個信号計算
　　1）一個輸入，記為 y(i)，它被産生以響應刺激向量 x(i) 的 M 個元素，即 x1(i),x2(i),.....,xM(i)
　　2）一個誤差信号，記為 e(i)，它是通過比較輸出 y(i) 和未知目标系統（要模型的實際實體系統）的相應輸出 d(i) 而獲得的。從效果上講，d(i) 可作為一個期望響應信号（desired response）或者目标（target）信号。
2. 自适應過程，包括根據誤差 e(i) 對神經元突觸權值的自動調整。      

這兩個共同運作過程的組合構成了一個圍繞神經元運作的回報環（feedback loop）。

上述的這兩個連續過程的産生原理如下：

因為神經元是線性的，輸出 y(i) 為局部誘導域：

。

神經元的輸出 y(i) 要和未知系統在時刻 i 的相應輸出 d(i) 作比較，通常 y(i) 與 d(i) 不等，是以它們的比較結果得到了誤差信号：

誤差信号 e(i) 用來對神經元突觸權值的調整進行控制的方式，是由用于導出自适應濾波算法的代價函數決定的。

這個問題與無限制最優化問題密切相關，無限制最優化不僅可以用線上性自适應濾波器上，還可以應用在一般的神經網絡上。

為了下一章節讨論LMS作準備，我們這裡先讨論下自适應濾波算法中的無限制最優化問題。

0x3：無限制最優化

考慮代價函數

，它是一個對未知權值（參數）向量 w， 連續可微（continuously differentiable）的函數。

函數

将 w 映射為單個實數，它是一種度量，用來選擇自适應濾波算法的權值（參數）向量 w，以使得模型以最優方式運作。

這樣，代價函數就成功地将一個學習問題轉換為了最優化問題。

我們想找到一個最優解

滿足條件：

也就是說，需要解決一個無限制的最優化問題，即：

選擇适當的權值向量 w 最小化代價函數

最優性的必要條件（注意不是充要條件）是：

這裡

是梯度算子（gradient operator）。權值向量的梯度為0，代表了已經優化到了極值，至少是局部極值。

同時

是代價函數的梯度向量（gradient vector）：

一類特别适合自适應濾波器設計的無限制最優化算法是以局部疊代下降（iterative descent）思想為基礎的：

從一個初始估計值 w(0) 開始，産生一系列權值向量 w(1),w(2),...，使得代價函數

在算法的每次疊代中都要下降，即

我們希望算法最終收斂到最優解

，但是這裡也僅僅是希望，因為局部疊代下降并不能保證一定收斂到全局最優解。

下面我們來讨論幾種以疊代下降思想的基本形式或變種形式的無限制最優化方法。

1. 最速下降法

在最速下降法中，對權值向量 w 的連續調整是在醉宿下降的方法進行的，即它是與梯度向量

方向相反的，記為：

是以，最速下降法一般表示為：

，這裡

是一個正常數，稱為步長（stepsize）或學習速率（learning-rate parameter）。g(n) 是在 w(n) 處的梯度向量值。

為了證明最速下降法的公式滿足

，我們用 w(n) 附近的一階泰勒級數展開來逼近

上式對小的

是适用的，将

代入上式得：

上式表明，對正的學習率參數

，代價函數每次疊代都必定是下降的，除非權值向量 w(n) 的梯度已經等于0（達到局部最優極值）。但這裡提供的推導是近似的，隻有當學習率足夠小時才是正确的（泰勒分解成立）。

最速下降法收斂到最優解

的速度是很慢的。此外，學習率參數

對收斂行為有重要影響：

1. 當 η 很小時：算法的瞬時相應是平緩的（overdamped），這是由于 w(n) 的軌迹是 w 平面的一個光滑曲線，如下圖 a）
2. 當 η 很大時：算法的瞬時相應是劇烈的（underdamped），這是由于 w(n) 的軌迹是鋸齒（振蕩）形的，如下圖 b）
3. 當 η 超過某一臨界值時，算法是不穩定的（即不收斂）
      

2. 牛頓法（Newton's method）

牛頓法的基本思想是：最小化代價函數

在目前點 w(n) 周圍的二次近似值；最小化在算法的每次疊代中都要進行。

具體來說，就是利用代價函數在點 w(n) 周圍的二次泰勒級數展開式，我們得到：

式中，g(n) 是代價函數

在點 w(n) 處的處的 M x 1 梯度向量。矩陣 H(n) 是

在 w(n) 的 m 行 m 列 Hessian矩陣。

的Hessian矩陣定義為：

上式需要代價函數

關于 w 的元素二階可微。

對式

中

進行微分并求極值得：

，我們最小化了改變量

解上式有關

的方程得到：

整合上面公式得：

一般來說，牛頓法收斂得很快，而且不會出現最速下降法有時會出現的鋸齒形情況。但是，應用牛頓法時， Hessian矩陣必須對每個 n 都是正定矩陣。

遺憾的是，一般不能保證在算法的每次疊代中 H(n) 都是正定矩陣。

假如 Hessian矩陣 H(n) 不正定，對牛頓法進行修正就有必要。在很多時候，牛頓法的最主要局限在于其計算複雜度。

3. Gauss-Newton法

為了處理牛頓法的計算複雜度過大，而不對其收斂行為做太嚴重的讓步，可以使用Gauss-Newton法。為了應用這一方法，我們采用表示為誤差平方和的代價函數，令：

誤差信号 e(i) 是可調權值向量 w 的函數。給定操作點 w(n)，通過引入下面新的項來線性化 e(i) 對 w 的依賴性：

用矩陣記号可以寫成等價的形式：

其中，e(n) 是誤差向量

J(n) 是 e(n) 的 n x m  Jacobi 矩陣：

Jacobi 矩陣 J(n) 是 m x n 梯度矩陣

的轉置，這裡：

現在更新後的權值向量 w(n+1) 定義為：

将

将以上表達式對 w 求微分并設結果為零，得到：

綜合上式，可得：

上式描述了 Gauss-Newton方法的純粹形式。

不想牛頓法必須知道代價函數

的 Hessian矩陣，Gauss-Newton法隻需要知道誤差向量 e(n) 的 Jacobi矩陣。

但是，為了使 Gauss-Newton 疊代可計算，矩陣乘積

必須是非奇異的。

4. GD（梯度下降法）

用負梯度作搜尋方向，即令

，是一種自然的選擇。這種方法被稱為梯度方法或梯度下降方法。

停止準則通常取為

，其中

是小正數。

注意：梯度下降是最速下降在歐式範數下的特殊情況。

Relevant Link:

https://www.zhihu.com/question/267021131       

3. LMS（最小均方）算法簡介

我們從最小二乘估計器引入最小二乘濾波器，這樣可以很自然地進入對LMS的讨論中。最小二乘濾波器和最小二乘估計器雖然隻有幾字之差，但是其整個優化運算過程是不一樣的。最小二乘濾波器引入了自适應回報的思想。

0x1：最小二乘估計器 - 維納濾波器的一種特定形式

我們在前面的章節中讨論了最小二乘估計器，它利用極小化（求導極值）的傳統放來從環境的觀測模型中找到最小二乘解。

從這個小節開始，我們将最小二乘估計器放到一個維納濾波器的架構中進行讨論，我們稱之為最小二乘濾波器（least-squares filter）。我們接下來利用 Gauss-Newton法來重新推導這個濾波器公式。

1. 最小二乘濾波器的誤差向量

我們定義如下誤差向量：

其中 d(n) 是 n x 1 的期望響應向量：

X(n) 是 n x M 的資料矩陣：

誤差向量 e(n) 對 w(n) 取微分得到梯度矩陣：

相應的，e(n) 的 Jacobi矩陣是：

因為誤差向量對權值向量 w(n) 已經是線性的，Gauss-Newton法在一次疊代後收斂，将上式綜合後代入

可得：

項

被看作是資料矩陣 X(n) 的僞逆，即：

是以，上式可寫為：

讀者注意！！

這個公式和我們在文章之前推導的最小二乘的幾何意義得到的公式是一緻的。通俗地說：

Gauss-Newton（以及其他疊代算法）的每一次疊代，本質上就是在這個 n 的時域内，進行最小二乘估計，并根據得到的本次最優解對權值向量進行更新。

這個公式表示了下面所陳述的一個簡便途徑：

權值向量 w(n+1) 求解定義在持續時間 n 的一個觀察區間上的線性最小二乘問題，是如下兩項的乘積：僞逆

和期望的響應向量 d(n)

2. 周遊環境下線性最小二乘濾波器的極限形式

我們已經知道了，LMS算法在一次疊代中（時間 n 時域區間），本質上是在進行最小二乘估計。接下來繼續思考，如果這個過程無限進行下去會得到什麼呢？即 n 趨近于無窮。

令

表示線性最小二乘濾波器關于觀測數 n 的極限形式，允許 n 趨于無窮。

基于公式

得到：

現在假設輸入向量 x(i) 和相應的期望響應 d(i) 來自于聯合周遊。我們可以用時間均值來代替總體均值。

輸入向量 x(i) 的相關矩陣（correlation matrix）的總體平均形式是：

并且，相應地，輸入向量 x(i) 和期望響應 d(i) 之間的互相關系（cross-correlation vector）的總體平均形式是：

，其中 E 表示期望算子。

進而，在周遊假設下，有：

和

綜上，可将式：

改寫為：

權值向量

稱為線性最優濾波問題的維納解。

是以，我們可以做以下的陳述：對一個周遊過程，當觀察樣本數趨于無窮時，線性最小二乘濾波器漸進趨于維納濾波器。

3. 維納濾波器的局限性

雖然，當樣本量趨近于無窮時，線性最小二乘濾波器趨近于維納濾波器，但是設計維納濾波器需要二階統計量的知識：

1）輸入向量 x(n) 的相關矩陣

2）x(n) 與期望響應 d(n) 的互相關向量

但是，在實際的情況下，這些資訊都是未知的，是以維納濾波器隻是一個理論上的最優濾波器。

在實際工程實踐中，我們可以利用線性自适應濾波器（linear adaptive filter）來處理未知的環境，自适應在這裡的含義就是濾波器能夠調整自己的自由參數來響應環境的統計變化。在連續的時間基礎上做這類調整的一個流行的算法就是最小均方算法（LMS）。

接下來，我們進入對LMS的讨論。

0x2： LMS（Least mean square）一種線性自适應濾波算法

LMS最小均方算法是第一個解決如預測和信道均等化等問題的線性自适應濾波算法。

值得注意的是，LSM算法自身不僅可以作為自适應濾波應用機器，它還可以作為其他自适應濾波算法的評價準則，這裡面的原因包括：

1. 從計算複雜度來說，對于可調參數而言 LMS算法的複雜度是線性的，這使得算法是計算高效的（computationlly efficient）的，而算法從性能上來說依然是有效的。
2. 算法可以簡單地用代碼來實作，因而是容易建立的。
3. 對于外部擾動來說，算法是魯棒的，LMS算法是模型獨立的。對任何模型，LMS都可以不辱使命，通過每次疊代的局部最優盡可能地去靠近全局最優。      

對工程來說，上述性能都是非常重要的。之是以強調說工程，是因為其實LMS并不是理論上最優的算法，但是卻是最實際工程有效的。

因為在實際情況中，我們很難獲得全局最優解，甚至說都無法完整按照最速下降的思想進行最優方向的梯度下降，原因大緻如下：

1. 神經網絡的目标函數多數是非凸函數，不一定有全局最優解
2. 多元函數偏導為0并非是局部極值
3. 解析式法運算複雜，多元函數通過解析式方法求解極值不是一件容易的事
4. 在一個 n 時域區間内，梯度并不是保持不變的，最速下降要求同時考慮所有方向上的梯度，這樣得到的梯度矩陣不一定是正定，可逆的。      

但是LMS擁有計算簡單、魯棒性等優點，使得LMS在之後的深度學習/BP理論的發展中被不斷繼承和發揚光大。

0x3：LMS算法公式

最小均方（least mean square，LMS）算法的建立是基于極小化代價函數的瞬時值。注意！是瞬時值。

代價函數為：

這裡 e(n) 是 n 時刻的瞬時誤差信号。

對權值向量 w 求微分得到：

和在最小二乘濾波器上一樣，LMS算法運作在一個線性神經元上，可以把誤差信号表示為：

是以，

綜上公式得：

，代價函數對 w(n) 的導數。

上式作為梯度向量的一種瞬時估計（instantaneous estimate），可以記為：

最後，将上式梯度的瞬時估計公式，帶入最速下降法作為最速下降法的梯度向量，可以得到LMS的算法公式：

這裡值得注意的是：

學習率參數

的倒數可以作為度量LMS算法的記憶（memory）：

給

賦的值越小，LMS算法将記憶的過去的資料就越多。是以，

值小的話，LMS算法執行得更精确，但算法的收斂速度慢

1. LMS用權重向量的瞬時估計代替實時變化

在LMS的公式中，我們用

代替

來強調這樣一個事實：

利用最速下降法可以得到一個權值向量，而LMS算法産生該權值向量的一個瞬時估計。是以，利用LMS算法時我們犧牲掉最速下降法的一個明顯特征。

在最速下降法中，對一個給定的

，權值向量

在權值空間中遵循一個明确定義的軌迹。對比之下，在LMS算法中，權值向量

則跟蹤一個随機的軌迹。

由于這個原因，LMS算法有時也被稱為”随機梯度算法“。當LMS算法的疊代次數趨于無窮時，

在維納解

周圍随機行走（布朗運動）。

一個重要的事實是，與最速下降法不同，LMS算法不需要知道環境的統計特征。從實際的角度來看，LMS的這一特征是非常重要的。

0x4：LMS算法的信号流圖表示

我們可以把LMS算法中的權值向量演變過程表示如下：

這裡，I 是機關矩陣。通過運用LMS算法，我們認識到：

是機關時間延遲算子（unit-time delay operator），意味着存儲。

我們利用信号流圖來表示LMS算法，這圖揭示了LMS算法是随機回報系統的一個執行個體。回報的出現對LMS算法的收斂行為有重要影響。

0x5：用馬爾科夫模型來描述LMS算法和維納濾波器的偏差

為了給LMS算法提供一種統計分析，我們利用下式定義的權值誤差向量（weight-error vector）更加友善。

其中，

是最優維納解，

是相應的由LMS算法計算的權值向量的估計。

是以，利用術語

，假設其為一個狀态（state），可以将式重寫為緊湊形式：

這裡，我們有

右邊的噪音項為

，其中，

是由維納濾波器産生的估計誤差。

1. LMS算法的馬爾科夫模型的特征

1. 模型的更新狀态（updated state），由向量

定義，依賴于老的狀态

，其自依賴性由轉移矩陣（transition matrix） A(n) 定義。

2. 在時間 n 上狀态的演化被内部所産生的噪音 f(n) 所擾動，這一噪聲扮演者”驅動力“的角色。

下圖給出了表示這一模型的向量值信号流圖。标志為

的分支表示模型的記憶，

作為機關時間延遲算子，由下式定義：

和上面的原始形式相比，這個圖中用緊湊形式重點強調了LMS算法中的回報過程。

需要注意的是！

上面的信号流圖以及相應的方程提供了在國小習率參數

的假設下LMS算法的收斂性分析的架構。

下面我們開始讨論國小習率

以及實作這一目标的兩個基礎知識：朗之萬方程和Kushner直接平均法。

https://www.cnblogs.com/xingshansi/p/6603263.html      

4. LMS算法收斂的基礎知識

0x1：朗之萬方程 - 布朗運動的特點

考慮穩定性和收斂性，我們可以說LMS算法（對足夠小的

）從未達到完美的穩定或者收斂條件。

而且，在大量的疊代時間步 n 之後，算法達到”僞平衡“條件，這從定性上講，可由算法圍繞着維納解執行布朗運動來描述。

這一類統計行為可通過非平衡熱力學的朗之萬方程（Langevin equation）來很好地解釋。

由 v(t) 定義品質為 m 的宏觀粒子陷入粘滞鈴的速度。假設粒子足夠小以使其由熱起伏而來的速度被視為重要的（即小粒子的運動可以由熱力學定律描述，因為品質較大的物體主要由牛頓力學和流體力學定律所描述）。

然後，由均分人力學原理（equipartition law of thermodynamics），粒子的平均能量由下式定義：

其中

是Boltzmann常數，T為絕對溫度（absolute temperature）。粘滞鈴中分子作用于粒子的總驅動由兩部分組成：

1. 根據Stoke定律（Stoke's lay）的等于- av(t) 的阻尼力（damping force），其中 a 是摩擦系數

2. 漲落力（fluctuating force）

，其性質是平均指定的。

粒子的運動方程在缺少外部驅動時由下式給定：

兩邊同除以 m，我們得：

是每機關品質漲落力（fluctuating force per unit mass）

因為它依賴于組成粒子的極為大量的原子數量，是以它是一個統計驅動力，它處于不規則運動狀态。

公式

被稱為朗之萬方程（Langevin equation），

被稱為朗之萬力（Langevin force）。

朗之萬方程描述了在粘滞鈴中所有時間下粒子的運動（如果其初始條件是指定），它是描述非平衡熱力學的第一個數學公式。

在後面的章節中，我們會證明LMS算法的一個變換版本具有和朗之萬方程的離散時間版本相同的數學形式。但是在證明之前，需要先讨論一個基礎知識。

0x2：Kushner直接平均法

的馬爾科夫模型是非線性随機差分方程（nonlinerar stochastic difference equation）。

這一方程是非線性的原因是因為：

1. 轉移矩陣 A(n) 依賴于輸入向量 x(n) 的外積

。是以，權值誤差向量

對于 x(n) 的依賴性和疊加原理相沖突，而這一原則是線性的需要。

2. 而且，方程是随機的是因為訓練樣本

是從随機環境中取得的。

基于這2個原因，我們發現對LMS算法作嚴格的統計分析是困難的任務。

然後，在滿足一定的條件下，LMS算法的統計分析能夠通過将Kushner直接平均法（kushner direct-averaging method）應用于上式的模型進而顯著地簡化。

1. 對Kushner直接平均法的正規陳述

考慮由馬爾科夫模型所描述的随機學習系統：

其中，對一些輸入向量 x(n) ，我們有

而且附加噪聲 f(n) 是由學習率參數

線性拉伸的。有

1. 學習率參數

是充分小的。

2. 附加噪聲 f(n) 本質上獨立于狀态

，修正馬爾科夫模型的狀态演化由下式來描述：

上式确定矩陣

是修正馬爾科夫模型的轉移矩陣，我們用

來表示修正馬爾科夫模型的狀态，用來強調這一模型随時間的演化僅在微笑的學習率參數

的有限情況下等同于原始馬爾科夫小莫名。

上述的讨論可以充分說明：

小的時候，LMS算法具有長記憶（long memory）。是以，更新狀态

的演化可以通過時間一步一步追蹤所有的路徑直到初始條件

2. 當

小的時候，可以在

的展開式序列中忽略二階和高階項。

3. 最後，在上式修正馬爾科夫模型中，通過調用周遊性原理，此時總體平均可以被時間平均所替。

0x3：國小習率參數下統計LMS學習理論

我們已經有了Kushner直接平均法，現在可以建立LMS算法的統計分析原則了。我們做三個合理的假設：

假設一：學習率參數

是小的

從實際角度，

的小的選擇也是有意義的。特别是，當

小時，LMS算法對于外部擾動是魯棒的

假設二：維納濾波器産生的估計誤差

是白噪

假設三：輸入向量 x(n) 和期望響應 d(n) 是聯合高斯分布

由實體現象産生的随機過程頻繁地出現使得高斯模型是适當的。

更重要的是，朗之萬力

對于LMS算法的非平衡行為負責，它證明了自身在大量的足夠多的疊代次數 n 的時候，算法在最優維納解的周圍進行布朗運動（Brownian motion）。當然，前提是基于學習率參數

的情況下。

http://chem.xmu.edu.cn/teach/chemistry-net-teaching/wuhua/chapter3/part12/12-1.html