EE263 Lecture 7 Regularized least-squares and Gauss-Newton method

课程主页:https://see.stanford.edu/Course/EE263

这次回顾第七讲,这一讲结束最小二乘应用的内容,然后介绍了正规化最小二乘法和牛顿高斯法。

Growing sets of regressors

考虑一族最小二乘问题,对于$p=1, \ldots, n​$

(其中$a_{1}, \dots, a_{p}$被称为回归量)

  • 用$a_{1}, \dots, a_{p}​$的线性组合近似$y​$
  • 将$y$投影到$\operatorname{span}\left\{a_{1}, \dots, a_{p}\right\}$
  • 利用$a_{1}, \dots, a_{p}$对$y$做回归
  • 随着$p$增加,回归效果变好,所以最优残差减少

$p\le n​$的解由下式给出

其中

  • $A_{p}=\left[a_{1} \cdots a_{p}\right] \in \mathbb{R}^{m \times p}$是$A$的前$p$列
  • $A_p=Q_p R_p$是$A_p$的$QR$分解
  • $R_{p} \in \mathbb{R}^{p \times p}$是$R$的$p\times p$主子式
  • $Q_{p}=\left[q_{1} \cdots q_{p}\right]$是$Q$的前$p$列

实际效果如下:

最小二乘系统识别

我们测量未知系统的输入$u(t)$和输出$y(t)$,$t=0, \ldots, N$:

系统识别问题:根据I/O数据$u,y$,找到合理的系统模型。

假设$u,y$是标量,对I/O数据使用$n​$步延迟的滑动平均模

其中$h_{0}, \ldots, h_{n} \in \mathbb{R}$。

可以将模型写成矩阵形式:

模型的预测误差为

最小二乘识别:选择模型(即$h$)来最小化预测误差$| e|$。

模型阶数选择

继续之前的问题。

现在有一个问题,模型阶数$n​$如何选择?显然$n​$越大,建立模型的预测误差就越小,实际中可以作出阶数$n​$和相对误差的图:

从上图中不难看出,最合适的选择是$n=10​$。

交叉验证

交叉验证是在不用来建立模型的数据上评估预测结果:

从上图中仍然可以看出,最合适的选择是$n=10$。当$n$太大时,在验证数据上的相对误差很大,这就产生了模型过拟合的问题,所以实际中选择适中的$n$。

Growing sets of measurements

这部分考虑“流”的形式的最小二乘问题:

其中$a_i^T​$是$A​$的行($a_i \in \mathbb R^n​$)

  • $x \in \mathbb R^n$是某些需要估计的向量

  • 每对$a_i,y_i$为一个测量值

  • 该问题的解显然为

  • 考虑$a_i,y_i$为序列,即$m$随着时间增加的问题

递归最小二乘

对于上述问题,我们可以递归计算

  • 初始化$P(0)=0 \in \mathbb{R}^{n \times n}, q(0)=0 \in \mathbb{R}^{n}$

  • 对$m=0,1, \ldots, $

  • 如果$P(m)​$可逆,我们有

  • 注意到$P(m)$可逆等价于$a_{1}, \dots, a_{m}$张成$\mathbb R^n$(所以,一旦$P(m)$不可逆,那么后面的$P(m)$将会一直不可逆)

递归最小二乘的快速更新

我们需要计算

而这可以利用如下公式(rank one update formula)快速更新:

这里要求$P=P^T$以及$P$和$P+aa^T$都可逆。

  • 这给出了在$O(n^2)$时间内由$P(m)^{-1}$计算$P(m+1)^{-1}$的方法
  • 从$P(m+1)$计算$P(m+1)^{-1}$的标准方法需要的时间复杂度是$O\left(n^{3}\right)$

Verification of rank one update formula

公式验证:

Lecture 7 Regularized least-squares and Gauss-Newton method

多目标的最小二乘

在许多问题中我们有两个(或更多)的目标

  • 我们希望$J_{1}=|A x-y|^{2}$很小
  • 同时也希望$J_{2}=|F x-g|^{2}$很小

($x \in \mathbb{R}^{n}$可逆)

  • 通常目标函数是竞争关系
  • 我们在使其中一个变小的同时,另一个会变大

常见的例子:$F=I,g=0$;即我们希望$|A x-y|$和$|x|$同时比较小。

对可行的目标对作图

对每个$x$,作出图像$\left(J_{2}, J_{1}\right)​$:

注意$x \in \mathbb {R}^{n}$,但该图像是$\mathbb R^2$的;图中$x^{(i)}$代表的实际上是$\left(J_{2}\left(x^{(i)}\right), J_{1}\left(x^{(i)}\right)\right)$

  • 阴影部分为可以取到的$(J_2, J_1)​$
  • 无阴影部分为无法取到的$(J_2, J_1)$
  • 区域边界被称为最佳权衡曲线
  • 权衡曲线对应的$x$被称为Pareto Optimality(关于目标函数$|A x-y|^{2},|F x-g|^{2}$)

图中的三个例子:$x^{(1)}, x^{(2)}, x^{(3)}$

  • $x^{(3)}​$在$J_1,J_2​$上都比$x^{(2)}​$差
  • $x^{(1)}$在$J_2$上比$x^{(2)}$好,在$J_1$上比$x^{(2)}$差

本文标题:EE263 Lecture 7 Regularized least-squares and Gauss-Newton method

文章作者:Doraemonzzz

发布时间:2019年05月30日 - 18:12:00

最后更新:2019年05月30日 - 18:18:52

原始链接:http://doraemonzzz.com/2019/05/30/EE263 Lecture 7 Regularized least-squares and Gauss-Newton method/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。