课程主页：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)}$差