UA SIE545 优化理论基础0 优化建模3 线性回归的参数估计问题

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

考虑一元线性回归问题，假设数据集为$\{(x_i,y_i),i=1,\cdots ,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)|,\forall i \\ ⟺ \\ \underset{{\beta }_0,{\beta }_1}{\min }u \\ s.t.u\ge [y_i-({\beta }_0+{\beta }_1{x}_i)],\forall i \\ u\le -[y_i-({\beta }_0+{\beta }_1{x}_i)],\forall 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 线性回归的参数估计问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。