【数值计算1】线性回归问题的几种解法

• 0 引言
• 1 最小二乘法
• • 1.1最小二乘法推导
  • 1.2 拓展：基于最小二乘法的非线性回归
  • 1.3 递归最小二乘法

线性回归问题在不同的背景下有不同的表述，

• 机器学习
  给定一组输入 D = { ( x 1 , y 1 ) , ⋯   , ( x m , y m ) } D={(x_1,y_1),cdots,(x_m,y_m)} D={(x1​,y1​),⋯,(xm​,ym​)}，其中 x i = [ x i 1 , ⋯   , x i n ] T x_i=left[x_i^1,cdots,x_i^nright]^T xi​=[xi1​,⋯,xin​]T是一个 n n n维列向量，线性回归问题是求出损失函数最小的 θ theta θ
  m i n J ( θ ) = m i n ∑ i = 1 m ( y i − x i T θ ) 2 minJ(theta)=minsum_{i=1}^{m}(y_i-x_i^Ttheta)^2 minJ(θ)=mini=1∑m​(yi​−xiT​θ)2
  主要有梯度下降法
• 数值计算
  在数值计算方法中，求参数 θ theta θ的过程称为数据拟合或曲线拟合，常用的算法维最小二乘法。

首先介绍线性回归问题的解法中，实施起来最简单的最小二乘法。

误差平方和为
J ( θ ) = ∑ i = 1 m ( x i T θ − y i ) 2 = ( X θ − Y ) T ( X θ − Y ) J(theta ) = sumlimits_{i = 1}^m {{{({x_i}^Ttheta - {y_i})}^2}} = {(Xtheta - Y)^T}(Xtheta - Y) J(θ)=i=1∑m​(xi​Tθ−yi​)2=(Xθ−Y)T(Xθ−Y)

其中 X = [ x 1 ⋯ x m ] T X = left[ {x_1} cdots {x_m} right]^T X=[x1​⋯xm​]T, Y = [ y 1 ⋯ y m ] T Y = left[ {y_1} cdots {y_m} right]^T Y=[y1​⋯ym​]T。令 ∂ ∂ θ J ( θ ) = 0 {partial over {partial theta }}J(theta ) = 0 ∂θ∂​J(θ)=0，已知

J ( θ ) = θ T X T X θ − θ T X T Y − Y T X θ − Y T Y J(theta)=theta^TX^TXtheta-theta^TX^TY-Y^TXtheta-Y^TY J(θ)=θTXTXθ−θTXTY−YTXθ−YTY， ∂ x T A x ∂ x = ( A + A T ) x frac{partial x^TAx}{partial x}=(A+A^T)x ∂x∂xTAx​=(A+AT)x， ∂ x T A y ∂ x = A y frac{partial x^TAy}{partial x}=Ay ∂x∂xTAy​=Ay， ∂ y T A x ∂ x = A T y frac{partial y^TAx}{partial x}=A^Ty ∂x∂yTAx​=ATy。

则
∂ J ( θ ) ∂ θ = 2 X T X θ − 2 X T Y = 0 frac{partial J(theta)}{partial theta}=2X^TXtheta-2X^TY=0 ∂θ∂J(θ)​=2XTXθ−2XTY=0

因此
θ ^ = ( X T X ) − 1 X T Y hat theta=(X^TX)^{-1}X^TY θ^=(XTX)−1XTY

例题：有一组数据

用最小二乘法求出拟合这组数据的曲线，提示：抛物线，MATLAB代码为

clear all
clc
t = [0:0.1:13]';
x = [1,3,5,6,7,8,9,10]';
y = [10,5,2,1,1,2,3,4]';
X = [ones(length(x),1),x,x.^2];
theta = inv(X'*X)*X'*y
figure
plot(x,y,'ro')
hold on
plot(t,[ones(length(t),1),t,t.^2]*theta,'k--')
legend('数据点','拟合曲线')

当数据随时间增加时，数据增加需要重新进行最小二乘计算 ( X T X ) − 1 X T Y (X^TX)^{-1}X^TY (XTX)−1XTY，递推最小二乘可以降低计算量，根据前 k k k时刻的估计值 θ k ^ hat {theta_k} θk​^​和第 k + 1 k+1 k+1时刻新的数据 ( x k + 1 , y k + 1 ) (x_{k+1},y_{k+1}) (xk+1​,yk+1​)，得到第 k + 1 k+1 k+1时刻的估计值 θ k + 1 ^ hat {theta_{k+1}} θk+1​^​，满足

θ k ^ = ( X k T X k ) − 1 X k T Y k θ k + 1 ^ = ( X k + 1 T X k + 1 ) − 1 X k + 1 T Y k + 1 hat {theta_k}=(X_k^TX_k)^{-1}X_k^TY_k \ hat {theta_{k+1}}=(X_{k+1}^TX_{k+1})^{-1}X_{k+1}^TY_{k+1} θk​^​=(XkT​Xk​)−1XkT​Yk​θk+1​^​=(Xk+1T​Xk+1​)−1Xk+1T​Yk+1​

具体公式为：

推导过程待补充