UA SIE545 優化理論基礎0 優化建模3 線性回歸的參數估計問題

• OLS
• Least Absolute Deviation (LAD)
• Least Max Deviation (LMD)
• Least Weighted Deviation

考慮一元線性回歸問題，假設數據集為$\{(x_i,y_i),i=1,?,n\}$，假設被解釋變量為$y$，解釋變量為$x$，并且二者是線性關系：
$$y={\beta }_0+{\beta }_{1}x$$

OLS

考慮最小二乘法，優化問題可以寫成
$$\min \sum _{i=1}^n(y_i?({\beta }_0+{\beta }_1{x}_i){)}^2$$

決策變量是系數${\beta }_0$與${\beta }_1$，目標函數是二次函數。由此是可以看出優化與統計的區別的，優化研究的是最優${\beta }_0,{\beta }_1$的存在性，以及最優性條件、穩定性以及數值解法；統計在此基礎上研究在數據具有一定隨機性時，最優的${\beta }_0,{\beta }_1$具有怎么樣的統計性質（無偏、有效、漸近分布等）以及怎樣基于這些性質做統計推斷（假設檢驗、區間估計）。

Least Absolute Deviation (LAD)

考慮最小一乘法，
$$\min \sum _{i=1}^n|y_i?({\beta }_0+{\beta }_1{x}_i)|$$

目標函數不可導，我們可以用一些技巧來重構這個優化問題：定義$u_i=|y_i?({\beta }_0+{\beta }_1{x}_i)|$，則這個優化問題等價于
$$\begin{gathered} \min \sum _{i=1}^n{u}_i \\ s.t.u_i=|y_i?({\beta }_0+{\beta }_1{x}_i)| \end{gathered}$$

可以將這個優化問題等價地寫成：
$$\begin{gathered} \min \sum _{i=1}^n{u}_i \\ s.t.u_i\ge |y_i?({\beta }_0+{\beta }_1{x}_i)| \end{gathered}$$

注意到$u_i\ge 0$，目標函數是最小化$u_i$的和，因此$u_i$必定傾向于取等。這個結果可以進一步化簡為
$$\begin{gathered} \min \sum _{i=1}^n{u}_i \\ s.t.u_i\ge [y_i?({\beta }_0+{\beta }_1{x}_i)] \\ {u}_i\le ?[y_i?({\beta }_0+{\beta }_1{x}_i)] \end{gathered}$$

這就是一個典型的線性規劃問題。

Least Max Deviation (LMD)

LMD的優化問題為
$$\underset{{\beta }_0,{\beta }_1}{\min }\underset{i}{\max }|y_i?({\beta }_0+{\beta }_1{x}_i)|$$

用LAD的思路，定義$u={\max }_i|y_i?({\beta }_0+{\beta }_1{x}_i)|$，則優化問題可以等價變形為：
$$\begin{gathered} \underset{{\beta }_0,{\beta }_1}{\min }u \\ s.t.u=\underset{i}{\max }|y_i?({\beta }_0+{\beta }_1{x}_i)| \end{gathered}$$

現在放松等式約束，
$$\begin{gathered} \underset{{\beta }_0,{\beta }_1}{\min }u \\ s.t.u\ge \underset{i}{\max }|y_i?({\beta }_0+{\beta }_1{x}_i)| \\ ? \\ \underset{{\beta }_0,{\beta }_1}{\min }u \\ s.t.u\ge |y_i?({\beta }_0+{\beta }_1{x}_i)|,?i \\ ? \\ \underset{{\beta }_0,{\beta }_1}{\min }u \\ s.t.u\ge [y_i?({\beta }_0+{\beta }_1{x}_i)],?i \\ u\le ?[y_i?({\beta }_0+{\beta }_1{x}_i)],?i \end{gathered}$$

Least Weighted Deviation

這種情形類似于UA MATH574提到的監督學習unequal cost的情況，因為$y_i?({\beta }_0+{\beta }_1{x}_i)$的符號是有含義的，大于0表示低估；小于0表示高估。有時低估和高估的cost不一樣，可以分別定義為$w^{+},w^{?}$，則最優化可以寫成：
$$\min w^{+}\sum _{i=1}^n\max \{0,y_i?({\beta }_0+{\beta }_1{x}_i)\}+w^{?}\sum _{i=1}^n\max \{0,?y_i+({\beta }_0+{\beta }_1{x}_i)\}$$

這個最優化問題也可以重寫成線性規劃：定義$u_i^{+}=\max \{0,y_i?({\beta }_0+{\beta }_1{x}_i)\},u_i^{?}=\max \{0,?y_i+({\beta }_0+{\beta }_1{x}_i)\}$，把這兩個作為決策變量，可以把等式約束放松為
$$\begin{gathered} u_i^{+}\ge \max \{0,y_i?({\beta }_0+{\beta }_1{x}_i)\} \\ {u}_i^{?}\ge \max \{0,?y_i+({\beta }_0+{\beta }_1{x}_i)\} \end{gathered}$$

進而
$$\begin{gathered} u_i^{+}\ge 0,u_i^{+}\ge y_i?({\beta }_0+{\beta }_1{x}_i) \\ {u}_i^{?}\ge 0,u_i^{?}\ge ?y_i+({\beta }_0+{\beta }_1{x}_i) \end{gathered}$$

因此上面的優化問題可以表示為線性規劃：

$$\begin{gathered} \min w^{+}\sum _{i=1}^n{u}_i^{+}+w^{?}\sum _{i=1}^n{u}_i^{?} \\ s.t.u_i^{+}\ge 0,u_i^{+}\ge y_i?({\beta }_0+{\beta }_1{x}_i) \\ {u}_i^{?}\ge 0,u_i^{?}\ge ?y_i+({\beta }_0+{\beta }_1{x}_i) \end{gathered}$$

總結

以上是生活随笔為你收集整理的UA SIE545 优化理论基础0 优化建模3 线性回归的参数估计问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。