前面分析了 線性最小二乘 的解法
YcoFlegs：[數值計算] 資料拟合——線性最小二乘法zhuanlan.zhihu.com
現在來看另一個問題：非線性最小二乘法
1. 定義
首先是如何定義這裡這個“非線性”。為什麼前面用多項式拟合就是線性了？
對于多項式拟合，每個資料樣本，誤差為：
，可以看到此處誤差（希望絕對值縮小到0的那個函數）和
的關系是線性的，是以這個最小二乘問題被稱為
線性最小二乘。雖然
與x的關系是非線性的，最終的優化函數為
也是非線性的。
那麼
非線性最小二乘就很容易了解了，誤差函數r和參數b的關系是非線性的就行了。
2. 例子——發射器位置
在一片區域裡
，存在10個接收器，分别位于
，和一個無線電發射器，位置
未知。這些接收器可以測量離發射器的距離，但存在誤差。
Credit to http://iacs-courses.seas.harvard.edu/courses/am205/schedule/
此時，單個接收器資料對應的誤差是
。
很容易證明非線性關系，即
。
3. 求導
和線性最小二乘一樣，優化的目标函數為
。其中，前面的
系數隻是為了友善後面推導的書寫，
m是樣本點的數量。
其中
n是待優化參數的次元，
是r對b的雅可比矩陣。
b最優的條件就是
如果r與b是線性關系，那麼
就是正規方程組（參考上一篇文章“線性最小二乘”），可以直接求解。證明的話隻需要把
拆開。
此處因為r(b)的非線性，隻能疊代求解這個優化問題。
4. 優化
4.1 牛頓法
先考慮一個簡單的情況來引入牛頓法。
- 在 一進制函數 ，求一個x使得f(x)=0。假如我們先猜這個根是 ，距離真實的根的距離是
python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 。使用泰勒展開python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 。忽略高階項，可以得到python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 。是以python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 ，如此循環。python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 - 對于 多元函數 ，形式完全類似： 。對于over-constrained system，
python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 ，python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 ，參考 https://zhuanlan.zhihu.com/p/83269117，可以用僞逆python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 求逆。python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法
4.2 牛頓法在非線性最小二乘中的使用
上面Section3提到，希望求根的函數F(b)為
有必要在這裡停下來理一下notation。注意此處：
- r是誤差函數，尺寸為 ，m是樣本點的個數
python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 - 是誤差函數對b的雅可比矩陣，尺寸為
python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 ，n是b的次元，是待優化參數的個數python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 - φ是目标函數，尺寸為
python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 - F是φ的導數，是待求根的函數，尺寸為
python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 - 是F對b的雅可比矩陣，尺寸為
python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法
是以為了得到
還得繼續求一次導：
其中
是Eq.4的第i列的轉置和r(b)列向量的點積。
下一步就是用Section4.1這個公式來疊代：
4.3 高斯牛頓法的推導 Gauss-Newton Method
Eq.6中的二階導求解通常很麻煩，而且随着優化的進行，誤差函數r(b)的值也在減小，是以決定忽略Eq.6的第二項求和：
把Eq.6 Eq.10代入到Eq.8裡，得到最終的疊代公式：
觀察下正規方程組的公式
可以發現，和上面的Eq.11形式上有很多相近之處。實際上高斯牛頓法實際上等價于在每個疊代步驟求解
。這種線性化非線性函數的思路在科學運算裡很常見。
4.4 如何優雅地計算雅可比矩陣
- 對于 簡單問題 ，比如上面Section2的 ，可以手推求導。
python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 - 但對于 複雜的函數 ，或者沒有closed-form的黑盒函數，可以考慮有限差分+autograd
autograd: Efficiently computes derivatives of numpy codegithub.com
4.5 高斯牛頓法小結
特點是：
- 使用牛頓法求解
python 最小二乘回歸 高斯核_[數值計算] 資料拟合——非線性最小二乘法 - 忽略二階項
缺點：
實際應用中收斂不穩定
4.6 高斯牛頓法的變種——Levenberg–Marquardt法
更新公式：
其中
，diag此處的意思是把除了對角線的元素直接歸零，然後用heuristic選擇
。
從形式上LM法比GM法隻是多了一個正則項。
5. 回到求發射器位置的例子
這裡用Python的scipy.optimize.root作為求解器
https://github.com/chr1shr/am205_examples/blob/master/1_data_fitting/nonlinlsq.pygithub.com
sol
Credit to http://iacs-courses.seas.harvard.edu/courses/am205/schedule/
紅色的點是b_init，紅色的×是最終收斂的解，而黑色的×是真實的位置。
一圈一圈的是
的等高線圖，而求解器想要找
的點。可以看到，此處的等高線圖不是規則形狀，也說明了這是一個非線性最小二乘的問題。
PS: 如果是線性最小二乘（
）的話，2D情況下（n=2）的輪廓圖會長這個樣子：
Credit to http://iacs-courses.seas.harvard.edu/courses/am205/schedule/
更高階的情況下是hyperellipses。