线性回归——梯度下降 VS 正规方程

2018-7-25
线性回归问题： $y^i=\theta_0+\theta_1x_1^i+\theta_2 x_2^i+... \theta_mx_m^i=y^i=\theta ^TX^i$
线性回归问题有一种数学推导的求解方法：
残差平方和： $min \quad Q(\theta)=(Y-X\theta)^T(Y-X\theta)$
$\Longrightarrow \theta=(X^TX)^{-1}X^T Y$
其中，各参数含义：
$Y=[y^1,y^2,...,y^n]^T;$
$\theta=[\theta_0,\theta_1,...,\theta_m]^T;$
$X \in R^{n\times (m+1)}$

这种方法得到的计算式 $\theta=(X^TX)^{-1}X^T Y$，被称为正规方程（Normal Equation)。
对于线性回归问题，还有另外一种解法，称为梯度下降法，了解过机器学习的同学，想必对这种方法不陌生，此处不再详细介绍。本文主要关注梯度下降法和直接正规方程求解法在线性回归问题上的比较：
数据：n 个训练样本，m维特征。
1. 梯度下降法（Gradient Descent)

• 需要选择学习率$\alpha$;

• 需要多次迭代过程；

• 当m较大时表现较好。

2. 正规方程法（Normal Equation)

• 无需选择学习率$\alpha$;

• 无需迭代；

• 需要计算$(X^TX)^{-1} ,（[m+1] \times [m+1]$维) ;

• 当m很大时计算量很大，会很慢：计算机计算矩阵逆的复杂度为$O(n^3)$。

总结来说：当特征维数m较小时（100~10000），选择使用正规返程计算能够得到更为准确的参数；当特征维数m很大时（>>10000)，应该选择梯度下降法，这样计算速度会比正规方程快一些。
Dr. Ng在网课上讲到，当m大于10000时，他就会考虑用梯度下降法来计算。

吴恩达机器学习链接：http://study.163.com/course/courseLearn.htm?courseId=1004570029#/learn/video?lessonId=1050515796&courseId=1004570029
（顺便说一句，这个不是Stanford的那个机器学习课，是近期网易推出的Dr.Ng 主讲的机器学习入门课，课程内容很基础。但由于是特意录制的网课，所以PPT会比之前Stanford的那个清晰一些。）