當拿到一筆資料準備玩統計，往往會想要做線性迴歸(Linear Regression)，找出一個模型(mathematical model)來解釋變數間的關係，一般都是使用平方距離，但是如果我們採用絕對值距離呢?? 而剛好在工業工程(Industrial Engineering)，作業研究(Operation Research) 領域，發展成熟的線性規劃(Linear Programming) 恰好可以來解決，是一個跨領域的應用 !! 已經存在有許多商業或open source 軟體，如: Gurobi，Cplex ，Xpress，Mosek，SCIP 可以輕易求解大型的線性規劃問題。而不僅如此也可以利用整數規劃(Integer Programming)來做特徵選擇 (Feature Selection)，甚至可以偵測離群值(Detect Outlier) !! 本文只介紹最小絕對值和，關於 Feature Selection , Detect Outlier
可以參考 Mixed-Integer Linear Programming Robust Regression with Feature Selection , Oleksii Omelchenko , 2010 的論文。
[Data Fitting Problem]
給定$n$筆實數型訓練資料 (training data) $\{(x^{k},y^{k})\}^{n}_{k=1} = \mathcal{D} , x^{k} =(x^{k}_1,x^{k}_2, ... , x^{k}_{p})\in \mathbb{R}^{p}$ , $y^{k} \in \mathbb{R}$ ，
我們目標是想要找到一個函數 $f_{\mathcal{D}} : \mathbb{R}^p \rightarrow \mathbb{R}$ 使得 $\forall x \in \mathbb{R}^{p} , f_{\mathcal{D}}(x) \approx y$ ，
精確來說:
$$ \text{Find } f_{\mathcal{D}} \text{ such that } f_{\mathcal{D}}(x)\approx \left\{ \begin{array}{lll} y^k & \text{ if } (x,y) = (x^{k},y^{k}) \in \mathcal{D} & \text{fit training data} & (F1) \\ y^{test} & \text{if } (x,y) = (x^{test},y^{test}) \not\in \mathcal{D} & \text{fit test data} & (F2) \\ \end{array}\right.$$
[概念補充]
1.在 Simple Regression 的假設為 $y$ 可以有混了雜訊(noise)，視為隨機變數，而 $x$ 沒有雜訊(即真實的 input)，而構造 $f_{\mathcal{D}}$ 有點就是把 $y$ 雜訊給濾掉，得到$ f_{\mathcal{D}}(x)$ (真實的 $y$)
2.$\{y^{k}- f_{\mathcal{D}}(x^{k})\}$ 我們稱之為殘差(residual)，來研究雜訊跟隨機性，有一門統計學領域稱之為殘差分析(residual analysis)特別是時間序列(time series)會需要使用 !!
3.如果連 $x$ 都有雜訊視為隨機變數，則需要參考統計學的 errors-in-variables models
其中構造 $f_{\mathcal{D}}$ 的方法論，只能含有 training data $\mathcal{D}$資訊，不能含有 test data 資訊
4.若只滿足(F1) 是經典的 Data Fitting Problem，本文也只探討盡量滿足(F1)
5.若也要滿足(F2) 是機器學習(machine learning)重要的目的，即 $f_{\mathcal{D}}$ 有預測的功能
6.而如果$f_{\mathcal{D}}$ 太過於滿足(F1)，而不滿足(F2) 我們稱之為 overfitting ，一般來說要使用一種技術叫做 regularization來改善。
[Linear Regression Review]
線性迴歸的意思代表 $f(x) = \sum^{p}_{j=1} \beta_{j} \phi_j(x_j)$，$\phi_j : \mathbb{R} \rightarrow \mathbb{R}$
$\{ \phi_j \}$為給定的 basis functions，可視為把初始資料作轉換!!
最常見的是 $\forall j , \phi_j(t) = t$ 即 $f(x) = \sum^{p}_{j=1} \beta_{j} x_j$
其中 $\beta = (\beta_1,\beta_2,...\beta_p) \in \mathbb{R}^{p}$ 代表模型參數 (model parameter) ，意義代表每個特徵(feature) $x_j$ 對 $y$ 的影響(單位權重)
[概念澄清I]
即使$\phi_{j}$是非線性函數(nonlinear)，我們也是稱為線性迴歸，因為在最小平方法，還是求解 Normal Equation 即線性系統 $A^{T}Ax = A^{T}b$，非線性迴歸指的是 $\beta_j$ 不是只有一次項。
[概念澄清II]
以統計學的術語 $\beta$ 可視為母體未知參數(unknown parameter)，而需要找估計量(Estimator) $\bar{\beta} = \bar{\beta}(\mathcal{D})$ 是個隨機變數。利用$\bar{\beta}$去估計 $\beta$ ，
竟量滿足不偏性(unbiasedness) $\displaystyle{E[\bar{\beta}] = \beta} $
滿足一致性(consistency)$\displaystyle{ \lim_{n \rightarrow \infty } Var[\bar{\beta}] = 0} $。
這類的統計分析比較精密，但需要假設母體分布的長相與求解最大概似估計(Maximum Likelihood Estimation)。而使用給定目標式最佳化調參數的方法比較單純不需要統計學假設。
[額外議題]
線性迴歸需要注意共線性(Multicollinearity)等議題 !!
[Linear Regression with absolute $|\cdot|$]
我們想要求解這兩種最佳化問題
(M1) $$\underset{\beta \in \mathbb{R}^{p}}{\text{min}} \sum^{n}_{k=1}\left|y^k - \sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j})\right| $$
(M2) $$\underset{\beta \in \mathbb{R}^{p}}{\text{min}} \underset{k=1,2,..n}{\text{max}} \left|y^k - \sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j})\right| $$
[Linear Programming]
可以把(M1) 寫成線性規劃模式 (RM1) !!
$$ \left\{\begin{array}{l}\text{ min } \sum^{n}_{k=1}z_k \\ \text{subject to : }\\\forall k =1,2,3,....n \quad y^k -\sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j}) \leq z_k \\ \forall k =1,2,3,....n \quad \sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j}) - y^k \leq z_k \\\forall k =1,2,3,....n \quad z_k \geq 0 \\ \end{array}\right. $$
可以把(M2) 寫成線性規劃模式 (RM2) !!
$$ \left\{\begin{array}{l}\text{ min } z \\ \text{subject to : }\\\forall k =1,2,3,....n \quad y^k -\sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j}) \leq z \\ \forall k =1,2,3,....n \quad \sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j}) - y^k \leq z \\ z \geq 0 \\ \end{array}\right. $$
[解線性規劃的演算法]
當我們把問題 formulate 成標準的線性規劃
$\left\{ \begin{array}{c} \text{min } cx \\ \text{subject to : } \\ Ax=b \\ x\geq 0 \\ \end{array}\right.$
我們可以使用以下眾多的演算法來求解線性規劃
[Direct Method]
Primal Simplex Method，Dual Simplex Method，Primal-Dual Direct method
[Iterative Method]
Khachian's Epllisoid Algorithm , Karmarkar's Projective Algorithm , Log Barrier Method , Primal-Dual Interior Point Method , Augmented Lagrangian method
而目前求解軟體(Solver) 比較具有競爭力的演算法是 Dual Simplex Method，Log Barrier Method , Primal-Dual Interior Point Method
註 : Primal-Dual Interior Point Method，Augmented Lagrangian method 可以拿來解非線性規劃問題。
可以參考 Mixed-Integer Linear Programming Robust Regression with Feature Selection , Oleksii Omelchenko , 2010 的論文。
[Data Fitting Problem]
給定$n$筆實數型訓練資料 (training data) $\{(x^{k},y^{k})\}^{n}_{k=1} = \mathcal{D} , x^{k} =(x^{k}_1,x^{k}_2, ... , x^{k}_{p})\in \mathbb{R}^{p}$ , $y^{k} \in \mathbb{R}$ ，
我們目標是想要找到一個函數 $f_{\mathcal{D}} : \mathbb{R}^p \rightarrow \mathbb{R}$ 使得 $\forall x \in \mathbb{R}^{p} , f_{\mathcal{D}}(x) \approx y$ ，
精確來說:
$$ \text{Find } f_{\mathcal{D}} \text{ such that } f_{\mathcal{D}}(x)\approx \left\{ \begin{array}{lll} y^k & \text{ if } (x,y) = (x^{k},y^{k}) \in \mathcal{D} & \text{fit training data} & (F1) \\ y^{test} & \text{if } (x,y) = (x^{test},y^{test}) \not\in \mathcal{D} & \text{fit test data} & (F2) \\ \end{array}\right.$$
[概念補充]
1.在 Simple Regression 的假設為 $y$ 可以有混了雜訊(noise)，視為隨機變數，而 $x$ 沒有雜訊(即真實的 input)，而構造 $f_{\mathcal{D}}$ 有點就是把 $y$ 雜訊給濾掉，得到$ f_{\mathcal{D}}(x)$ (真實的 $y$)
2.$\{y^{k}- f_{\mathcal{D}}(x^{k})\}$ 我們稱之為殘差(residual)，來研究雜訊跟隨機性，有一門統計學領域稱之為殘差分析(residual analysis)特別是時間序列(time series)會需要使用 !!
3.如果連 $x$ 都有雜訊視為隨機變數，則需要參考統計學的 errors-in-variables models
其中構造 $f_{\mathcal{D}}$ 的方法論，只能含有 training data $\mathcal{D}$資訊，不能含有 test data 資訊
4.若只滿足(F1) 是經典的 Data Fitting Problem，本文也只探討盡量滿足(F1)
5.若也要滿足(F2) 是機器學習(machine learning)重要的目的，即 $f_{\mathcal{D}}$ 有預測的功能
6.而如果$f_{\mathcal{D}}$ 太過於滿足(F1)，而不滿足(F2) 我們稱之為 overfitting ，一般來說要使用一種技術叫做 regularization來改善。
[Linear Regression Review]
線性迴歸的意思代表 $f(x) = \sum^{p}_{j=1} \beta_{j} \phi_j(x_j)$，$\phi_j : \mathbb{R} \rightarrow \mathbb{R}$
$\{ \phi_j \}$為給定的 basis functions，可視為把初始資料作轉換!!
最常見的是 $\forall j , \phi_j(t) = t$ 即 $f(x) = \sum^{p}_{j=1} \beta_{j} x_j$
其中 $\beta = (\beta_1,\beta_2,...\beta_p) \in \mathbb{R}^{p}$ 代表模型參數 (model parameter) ，意義代表每個特徵(feature) $x_j$ 對 $y$ 的影響(單位權重)
[概念澄清I]
即使$\phi_{j}$是非線性函數(nonlinear)，我們也是稱為線性迴歸，因為在最小平方法，還是求解 Normal Equation 即線性系統 $A^{T}Ax = A^{T}b$，非線性迴歸指的是 $\beta_j$ 不是只有一次項。
[概念澄清II]
以統計學的術語 $\beta$ 可視為母體未知參數(unknown parameter)，而需要找估計量(Estimator) $\bar{\beta} = \bar{\beta}(\mathcal{D})$ 是個隨機變數。利用$\bar{\beta}$去估計 $\beta$ ，
竟量滿足不偏性(unbiasedness) $\displaystyle{E[\bar{\beta}] = \beta} $
滿足一致性(consistency)$\displaystyle{ \lim_{n \rightarrow \infty } Var[\bar{\beta}] = 0} $。
這類的統計分析比較精密，但需要假設母體分布的長相與求解最大概似估計(Maximum Likelihood Estimation)。而使用給定目標式最佳化調參數的方法比較單純不需要統計學假設。
[額外議題]
線性迴歸需要注意共線性(Multicollinearity)等議題 !!
[Linear Regression with absolute $|\cdot|$]
我們想要求解這兩種最佳化問題
(M1) $$\underset{\beta \in \mathbb{R}^{p}}{\text{min}} \sum^{n}_{k=1}\left|y^k - \sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j})\right| $$
(M2) $$\underset{\beta \in \mathbb{R}^{p}}{\text{min}} \underset{k=1,2,..n}{\text{max}} \left|y^k - \sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j})\right| $$
[Linear Programming]
可以把(M1) 寫成線性規劃模式 (RM1) !!
$$ \left\{\begin{array}{l}\text{ min } \sum^{n}_{k=1}z_k \\ \text{subject to : }\\\forall k =1,2,3,....n \quad y^k -\sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j}) \leq z_k \\ \forall k =1,2,3,....n \quad \sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j}) - y^k \leq z_k \\\forall k =1,2,3,....n \quad z_k \geq 0 \\ \end{array}\right. $$
$$ \left\{\begin{array}{l}\text{ min } z \\ \text{subject to : }\\\forall k =1,2,3,....n \quad y^k -\sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j}) \leq z \\ \forall k =1,2,3,....n \quad \sum^{p}_{j=1}\beta_{j}\phi(x^{k}_{j}) - y^k \leq z \\ z \geq 0 \\ \end{array}\right. $$
[解線性規劃的演算法]
當我們把問題 formulate 成標準的線性規劃
$\left\{ \begin{array}{c} \text{min } cx \\ \text{subject to : } \\ Ax=b \\ x\geq 0 \\ \end{array}\right.$
我們可以使用以下眾多的演算法來求解線性規劃
[Direct Method]
Primal Simplex Method，Dual Simplex Method，Primal-Dual Direct method
[Iterative Method]
Khachian's Epllisoid Algorithm , Karmarkar's Projective Algorithm , Log Barrier Method , Primal-Dual Interior Point Method , Augmented Lagrangian method
而目前求解軟體(Solver) 比較具有競爭力的演算法是 Dual Simplex Method，Log Barrier Method , Primal-Dual Interior Point Method
註 : Primal-Dual Interior Point Method，Augmented Lagrangian method 可以拿來解非線性規劃問題。
[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~]
by Plus & Minus 2017.08
留言
張貼留言