Linear Regression with Multiple Variables——Normal Equation

对于线性回归问题，用梯度下降法求解参数需要选择α，并且需要多步迭代才能收敛到全局最小值，而用正规方程法可以一次性求解参数。Andrew Ng在视频中直接给出了正规方程求解参数的计算结果

θ = (X^{T} X)^{- 1} X^{T} y

本篇文章给出了一种可能的推导方法。

一、矩阵运算预备知识

1.1 矩阵转置

\begin{aligned} (A + B)^{T} & = A^{T} + B^{T} \\ (A B)^{T} & = B^{T} A^{T} \end{aligned}

1.2 矩阵求偏导

\frac{d (X^{T} A)}{d (X)} = \frac{d (A^{T} X)}{d (X)} = A

\frac{d (X^{T} A X)}{d (X)} = 2 A X

二、推导过程

对于训练样本集，有

\begin{aligned} h_{θ} (x^{(1)}) & = θ_{0} x_{0}^{(1)} + θ_{1} x_{1}^{(1)} + \dots \dots + θ_{n} x_{n}^{(1)} \\ h_{θ} (x^{(2)}) & = θ_{0} x_{0}^{(2)} + θ_{1} x_{1}^{(2)} + \dots \dots + θ_{n} x_{n}^{(2)} \\ \dots \dots \\ h_{θ} (x^{(m)}) & = θ_{0} x_{0}^{(m)} + θ_{1} x_{1}^{(m)} + \dots \dots + θ_{n} x_{n}^{(m)} \end{aligned}

用向量形式表示，得到

\begin{aligned} {[\begin{matrix} h_{θ} (x^{(1)}) \\ h_{θ} (x^{(2)}) \\ ⋮ \\ h_{θ} (x^{(m)}) \end{matrix}]}_{m \times 1} = {[\begin{array}{cccc} x_{0}^{(1)} & x_{1}^{(1)} & \dots & x_{n}^{(1)} \\ x_{0}^{(2)} & x_{1}^{(2)} & \dots & x_{n}^{(2)} \\ ⋮ & ⋮ & \dots & ⋮ \\ x_{0}^{(m)} & x_{1}^{(m)} & \dots & x_{n}^{(m)} \end{array}]}_{m \times (n + 1)} \times {[\begin{matrix} θ_{0} \\ θ_{1} \\ ⋮ \\ θ_{n} \end{matrix}]}_{(n + 1) \times 1} \end{aligned}

即

h_{θ} (x) = X θ

代价函数

J (θ)

可写为

\begin{aligned} J (θ) & = \frac{1}{2 m} \sum_{i = 1}^{m} {(h_{θ} (x^{(i)}) - y^{(i)})}^{2} \\ = \frac{1}{2 m} (X θ - y)^{T} (X θ - y) \\ = \frac{1}{2 m} (θ^{T} X^{T} X θ - 2 θ^{T} X^{T} y + y^{T} y) \end{aligned}

最小化代价函数，即需

\frac{\partial}{\partial θ} J (θ) = 0

根据矩阵求偏导规则，得到

\frac{1}{2 m} \times [2 (X^{T} X) θ - 2 X^{T} y] = 0

解得

θ = (X^{T} X)^{- 1} X^{T} y

三、梯度下降法和正规方程法的对比

【Machine Learning, Coursera】机器学习Week2 Normal Equation
对于线性回归问题，用梯度下降法求解参数需要选择α，并且需要多步迭代才能收敛到全局最小值，而用正规方程法可以一次性求解参数，自然也不必画 $J (θ)$ 曲线图了。此外，如果使用正规方程法，还不需要归一化特征变量。显然，在某些情况下，正规方程法效率更高。

那么，梯度下降法和正规方程法该如何取舍？

首先，要看n的大小。正规方程法需要进行矩阵逆运算，而实现逆矩阵计算所需的计算量大约是矩阵维度的三次方。当n非常大时，逆运算会消耗大量时间。具体来说，当n在10000以上时，就会考虑优先使用梯度下降法。
其次，要看具体的问题。梯度下降法的应用范围更广，在非回归问题中，梯度下降法也可用于求解参数。

【Machine Learning, Coursera】机器学习Week2 Normal Equation