序言
线性最小二乘法，作为统计学与数据科学中的基石之一，自其诞生以来便在科学研究、工程技术、经济预测等众多领域展现出了强大的应用价值。这一方法的核心思想在于，通过最小化误差的平方和来寻找数据的最佳函数匹配，即找到一个线性模型，使得该模型预测值与观测值之间的差的平方和最小。
简而言之，它提供了一种量化并优化模型预测准确性的有效手段，使得我们能够基于有限的数据点，构建出最能反映数据内在规律的线性关系。
线性最小二乘实例（Linear Least Squares）
- 要解决问题
- 假设，我们希望找到最小化公式1的 x \boldsymbol{x} x值： f ( x ) = 1 2 ∥ A x − b ∥ 2 2 —公式1 f(\boldsymbol{x})=\frac{1}{2}\left\|\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b}\right\|_2^{2}\quad\textbf{\footnotesize{---公式1}} f(x)=21∥Ax−b∥22—公式1
- 专门线性代数算法能够高效地解决这个问题；但是，我们也可以探索如何使用基于梯度的优化算法来解决这个问题，这可以作为这些技术是如何工作的一个简单的例子。
- 基于梯度的优化算法
- 首先，我们计算梯度： ∇ x f ( x ) = A T ( A x − b ) = A T A x − A T b —公式2 \nabla_xf(\boldsymbol{x})=\boldsymbol{A}^T(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b})=\boldsymbol{A}^T \boldsymbol{A} \boldsymbol{x}-\boldsymbol{A}^T \boldsymbol{b}\quad\textbf{\footnotesize{---公式2}} ∇xf(x)=AT(Ax−b)=ATAx−ATb—公式2
- 然后，我们可以采用小的步长，按照这个梯度下降。见算法1中的详细信息。
- 牛顿法二次近似算法
- 我们也可以使用牛顿法解决这个问题。因为在这个情况下真正的函数是二次的，牛顿法所用的二次近似是精确的，该算法会在一步后收敛到全局最小点。
- 现在假设我们希望最小化同样的函数，但受 x ⊤ x ≤ 1 \boldsymbol{x}^\top\boldsymbol{x}\leq 1 x⊤x≤1的约束。
- 要做到这一点，我们引入 Lagrange \text{Lagrange} Lagrange： L ( x , λ ) = f ( x ) + λ ( x ⊤ x − 1 ) —公式3 L(\boldsymbol{x},\lambda)=f(\boldsymbol{x})+\lambda(\boldsymbol{x}^\top\boldsymbol{x}-1)\quad\textbf{\footnotesize{---公式3}} L(x,λ)=f(x)+λ(x⊤x−1)—公式3
- 现在，我们解决以下问题： min x max λ , λ ≥ 0 L ( x , λ ) —公式4 \min\limits_x\max\limits_{\lambda,\lambda\ge0}L(\boldsymbol{x},\lambda)\quad\textbf{\footnotesize{---公式4}} xminλ,λ≥0maxL(x,λ)—公式4
- 可以用 Moore-Penrose \text{Moore-Penrose} Moore-Penrose伪逆： x = A + b \boldsymbol{x}=\boldsymbol{A}^+\boldsymbol{b} x=A+b找到无约束最小二乘问题的最小范数解。
- 如果这一点是可行的，那么这也是约束问题的解。否则，我们必须找到约束是活跃的解。
- 关于 x \boldsymbol{x} x对 Lagrangian \text{Lagrangian} Lagrangian微分，我们得到方程： A ⊤ A x − A ⊤ b + 2 λ x = 0 —公式5 \boldsymbol{A}^\top\boldsymbol{Ax}-\boldsymbol{A}^\top\boldsymbol{b}+2\lambda\boldsymbol{x}=0\quad\textbf{\footnotesize{---公式5}} A⊤Ax−A⊤b+2λx=0—公式5
- 这就告诉我们，该解的形式将会是： x = ( A ⊤ A + 2 λ I ) − 1 A ⊤ b —公式6 \boldsymbol{x}=(\boldsymbol{A}^\top\boldsymbol{A}+2\lambda\boldsymbol{I})^{-1}\boldsymbol{A}^\top\boldsymbol{b}\quad\textbf{\footnotesize{---公式6}} x=(A⊤A+2λI)−1A⊤b—公式6
- λ \lambda λ的选择必须使结果服从约束。我们可以关于 λ \lambda λ进行梯度上升找到这个值。
- 为了做到这一点，观察： ∂ ∂ λ L ( x , λ ) = x ⊤ x − 1 —公式7 \frac{\partial}{\partial\lambda}L(\boldsymbol{x},\lambda)=\boldsymbol{x}^\top\boldsymbol{x}-1\quad\textbf{\footnotesize{---公式7}} ∂λ∂L(x,λ)=x⊤x−1—公式7
- 当 x \boldsymbol{x} x的范数超过 1 1 1时，该导数是正的，所以为了跟随导数上坡并相对 λ \lambda λ增加 Lagrangian \text{Lagrangian} Lagrangian，我们需要增加 λ \lambda λ。
- 因为 x ⊤ x \boldsymbol{x}^\top\boldsymbol{x} x⊤x的惩罚系数增加了，求解关于 x \boldsymbol{x} x的线性方程现在将得到具有较小范数的解。
- 求解线性方程和调整 λ \lambda λ的过程一直持续到 x \boldsymbol{x} x具有正确的范数并且关于 λ \lambda λ的导数是 0 0 0。
算法1
从任意点 x \boldsymbol{x} x开始，使用梯度下降关于 x \boldsymbol{x} x最小化 f ( x ) = 1 2 ∥ A x − b ∥ 2 2 f(\boldsymbol{x})=\frac{1}{2}\left\|\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b}\right\|_2^{2} f(x)=21∥Ax−b∥22的算法
伪代码
将步长（ ϵ \epsilon ϵ）和容差（ δ \delta δ）设为小的正数。
w h i l e \bold{while} while ∥ A ⊤ A x − A ⊤ b ∥ 2 > δ \Vert\boldsymbol{A}^\top\boldsymbol{Ax}-\boldsymbol{A}^\top\boldsymbol{b}\Vert_2>\delta ∥A⊤Ax−A⊤b∥2>δ d o \bold{do} do
x ← x − ϵ ( A ⊤ A x − A ⊤ b ) \quad\boldsymbol{x} \leftarrow \boldsymbol{x}-\epsilon(\boldsymbol{A}^\top\boldsymbol{Ax}-\boldsymbol{A}^\top\boldsymbol{b}) x←x−ϵ(A⊤Ax−A⊤b)
e n d \bold{end} end w h i l e \bold{while} while
总结
- 线性最小二乘法不仅因其数学上的简洁性而广受欢迎，更因其实用性和鲁棒性成为了数据分析和模型拟合的首选工具之一。
- 在面对复杂多变的现实问题时，该方法通过最小化误差平方和的方式，有效平衡了模型复杂度与拟合精度之间的关系，从而帮助我们从海量数据中提取出有价值的信息和规律。无论是线性回归模型的构建，还是参数估计的精确求解，线性最小二乘法都展现出了其不可替代的重要作用。
- 随着大数据时代的到来，线性最小二乘法的应用将更加广泛而深入，为科学研究和社会进步提供更加坚实的数据支撑。
往期重要内容回顾
应用数学与机器学习基础 - 数值计算篇