Supervised Learning: Linear Regression gaunthan Posted on Nov 24 2017 ? Machine Learning ? ? Supervised Learning ? ## Supervised Learning **监督学习**(Supervised Learning)是机器学习中的一种。监督意味着样本是有人工标注的,我们希望通过学习探知已标注样本中的某种规律,从而可以较为准确地预测未知(即未标注)样本的标注信息。监督学习是有目的的学习。 监督学习解决的问题分为两类: - **回归**(Regression):预测值是“连续”的。例如房价这样的连续量。严格上来说,房价并不是真的连续。因此“连续”是指取值是无法穷尽的。 - **分类**(Classification):预测值是离散的。例如对交通工具进行分类,样本会被分类到“陆地交通工具”、“水域交通工具”、“航空交通工具”类别之一。可以用不同的整数代表这些类别,这使得输出值是有限的、离散的值。 ## Linear Regression ### Introduction **线性回归**(Linear Regression)是解决回归问题的一种方法——它假设样本之间存在某种“线性”关系。线性回归试图找到一条直线,它能够较好地拟合数据,表示数据之间的某种线性关系。 假设我们获得了某些城市的总人口数量以及对应的赢利。我们可以在二维坐标系中描绘样本,如下图所示(每个红色X表示一个样本):  我们需要对不在样本集中的城市进行预测。假设城市A拥有人口20万人口,我们希望知道它的总赢利。首先,从图中我们直观地“感觉出“样本中存在线性关系。因此,我们可以通过拟合一条直线,对我们的未知样本进行预测。  从上图可以得知城市A的赢利大约为19万。 ### Model Definition 我们知道,平面内有无数条直线。该如何确定我们想要的是哪一条直线呢?这就涉及到我们的学习目标。在此之前,先看看我们的预测模型是如何定义的。 #### One variable 对于单个输入变量来说,我们的预测模型可以表示为: $$h_\theta(x) = \theta_0 x_0 + \theta_1 x_1,其中x_0 = 1$$ 在中学课本中平面内的直线通常用$y = ax + b$表示,为了方便推广,我们统一用$\theta_j(j>=0)$来表示a和b这样的参数。 #### Multiple variable 我们知道,影响房价的可能不单单是面积、还有房间的数量、附近地铁站的数量等等因素。在实际应用中,**特征**(feature, 即输入变量的属性)往往不只一个。我们可以将上式推广到具有n个特征的情况,以获得更一般的模型定义。 假设输入变量x的维度为n,则我们的预测模型定义为: $$h_\theta(x) = \theta^T x, 其中 \theta = \begin{pmatrix}\theta_0 \\ \theta_1 \\ \theta_2 \\ \vdots \\ \theta_n \end{pmatrix}, x = \begin{pmatrix} x_0 \\ x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}, x_0 = 1$$ 注意这是一个**向量化**(vectorilized)的模型定义。这意味着在用Matlab/Octave实现模型时,不需要编写显式地循环来累加特征和参数的乘积,可以直接定义向量后,按照公式定义,进行向量操作即可。向量化的实现不仅使得我们的代码更简洁明了,同时因为矩阵操作是高度优化的,我们能够获得更高的运行效率。 ### Learning Object **学习问题**(Learning Problem)由三个指标描述: - T(Task):学习任务,即我们希望学习系统完成的事情。 - P(Performance measure):性能度量,即我们对学习系统工作好坏的度量。 - E(Experience):经验,学习系统需要从样本数据中习得的“一般”规律。 以预测房价为例,我们可以这样形式化地定义它: - T:给定房子的数据(如房屋面积),预测它的价格。 - P:预测的价格跟实际价格的偏差,即误差。 - E:从样本数据中习得的规律,例如房子的面积与价格存在线性关系。 T显然是预测模型的输出结果;P则是所有训练样本的预测结果与真实结果的累积误差。E则是在样本数据中观察到的规律(即模型的参数)。 学习过程可以形式化定义为如下最优式: $$\begin{matrix} arg \ min \\ \theta \end{matrix} J(\theta) ={1\over2m}\sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2$$ 它的含义是:求参数集$\theta$,使得$J(\theta)$最小。$J(\theta)$也称为**损失函数**(lost function),**误差**(error),**代价函数**(cost function)等。这种求最小累积平方误差的方法被称为**最小二乘法**(Least square method)。 其中,$x^{(i)}$表示第i个样本的特征,它是一个n维向量;$y^{(i)}$表示第i个样本的标注值,$h_{\theta}(x^{(i)})$表示第i个样本的预测值。在这里,通过最小化样本的累积平方误差,我们便能够习得一组参数,它表示的模型能够使得每个样本的预测值尽量接近它的真实值。因此,当输入未知变量时,我们希望模型的预测值也能够尽量接近真实值。 ### Learning Algorithm **学习算法**(Learning Algorithm)是实现学习过程的方法。线性回归有两种学习算法。通常来说,当特征数比较少时(一般是低于100, 000),使用normal quation效率更高;当特征数很多时,normal equation中的矩阵操作速度过慢,此时使用gradient descent更为适合。 #### Gradient Descent **梯度下降**(Gradient descent)是一种常见的学习算法。它通过逐次**同时**(simultaneously)更新参数,使参数往函数梯度下降的方向(即导数的负方向)移动,最终到达一个极小点。当且仅当只存在一个极小点时,梯度下降才可以保证找到最小点。 如何确定梯度下降已经到达了极小点呢?方法有很多,但为了效率考虑,一般是迭代一定次数后就认为它已经收敛。也可以检查$\theta$的值是否还发生较大的变化。  *(Image from [here](http://blog.datumbox.com/tuning-the-learning-rate-in-gradient-descent/).)* 上图展示了从不同的起始点(即不同的参数初始化值)运行梯度下降,最终可能会收敛于不同的极小点,即局部最优点(optimal)。然而,如果我们的代价函数是**碗状的**(bow-shaped),则正确配置了学习率的梯度下降可以保证收敛到最小点:  *(Image from [here](https://cn.mathworks.com/matlabcentral/fileexchange/35389-gradient-descent-visualization).)* ##### Batch 函数$J(\theta)$对于参数$\theta_j$的梯度(gradient)为: $$ \frac{\partial J(\theta)}{\partial \theta_j} = {1 \over m} \sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)}) x^{(i)}_j$$ 参数$\theta_j$的更新公式为: $$ \theta_j = \theta_j - \alpha{1 \over m} \sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)}) x^{(i)}_j$$ 可以写出如下所示向量化的更新公式: $$ \theta = \theta - \alpha{1 \over m} \sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)}) x^{(i)}$$ 注意梯度乘上了一个因子$\alpha$,它被称为**学习率**(Learning rate),用来控制梯度的大小。形象地来说就是在函数图像上的迈步长度。学习率小,下降速度慢;学习率大,下降速度快。在合理的取值范围内,学习率越大,梯度下降收敛的速度越快。如下图所示:  当学习率过大时,可能会导致跨步越过极小点,导致算法无法收敛:  *(Image from [here](https://www.linkedin.com/pulse/gradient-descent-simple-words-parth-jha).)* ##### Stochastic 上面那种一次更新遍历全部样本的梯度下降称为**批量梯度下降**(Batch Gradient Descent)。这种更新方式在样本数非常多的时候运行速度会急剧下降,而且当数据量过大无法一次性装入内存时,算法无法运行。 为此人们提出了梯度下降的另一种实现——**随机梯度下降**(Stochastic Gradient Descent),这种情况下一次更新只使用一个样本:  随机梯度下降不保证每次迭代会求得更小的$J(\theta)$,它的下降路径可能非常崎岖,但最终也会收敛到极小点。 ##### Mini-Batch 梯度下降还有另一种变种,称为**小批量梯度下降**(Mini-Batch Gradient Descent)。顾名思义,小批量梯度下降的一次更新操作不单单使用一个样本,而是使用$b$个样本。这个数量的设置因具体平台和环境会有所不同。  如果代码实现是向量化的,则相比于随机梯度下降,小批量梯度下降往往运行得更快——一次更新使用多个样本,而这多个样本可以借助并行机制更快地计算出结果。 #### Normal Equation 线性回归的代价函数通常是凸函数,这意味着极值点(极小点)唯一。因此可以令代价函数的一阶导数等于0,直接求极小点(最小点)。这种方法就是normal equation。由于推导和化简过程比较复杂,这里省略。感兴趣的读者请自行查阅。下面是参数的计算公式: $$ \theta = (X^T X)^{-1}X^T{\vec y}$$ #### Comparison Gradient Descent| Normal Equation --|-- Need to choose alpha| No need to choose alpha Needs many iterations| No need to iterate O ($kn^2$), k = num of iterations| O ($n^3$), need to calculate inverse of $X^TX$ Works well when n is large| Slow if n is very large ### Implement 可以使用Matlab/Octave实现本文讲述的所有模型和算法。 样本数据X应是一个mxn维的矩阵,每行代表一个样本;y应是mx1的向量,每行代表一个样本的真实值。theta是(n+1)x1维的向量,代表参数。由于添加了$x_0$,在使用X前,需要在第一列前插入值全为1的mx1维向量。 #### Model ```matlab h = X * theta ``` 由于Matlab/Octave中数组下标从1开始,因此h(1)代表第1个样本的预测值。 #### Lost ```matalb J = 1 / (2*m) * sum((X * theta - y) .^ 2); ``` #### Gradient Descent ```matlab function [theta, J_history] = gradientDescentMulti(X, y, theta, alpha, num_iters) m = length(y); % number of training examples J_history = zeros(num_iters, 1); for iter = 1:num_iters theta = theta - alpha * (1/m) * X' * (X * theta - y); % Save the cost J in every iteration J_history(iter) = computeCostMulti(X, y, theta); end end ``` 一般会保留每次迭代时的模型代价,以此观察随着迭代次数的增加,$J(\theta)$是否如预期般递减,使得我们能够提前发现算法是否运行异常:  #### Normal Equation ```matlab theta = pinv(X' * X) * X' * y; ``` 由于`X' * X`不一定可逆,因此在实现时往往使用**矩阵伪逆**(pseudo)。伪逆可以通过`pinv`函数计算。 ## Best Practice ### Feature Preprocessing 通常特征之间存在很大的取值范围差异。例如影响房价的房子面积,和房间数量。如果前者的单位比较小,则前者往往是后者的千倍或万倍。当特征之间存在这种情况时,梯度下降的计算过程会变得缓慢,甚至可能会遇到数值计算问题。 通常在运行梯度下降前,对特征进行预处理,使其具备零均值(zero mean)和单位标准差(unit variance)是一种好习惯,这不仅能避免数值计算问题,而且也使得梯度下降等算法的解搜索过程更加快速:  #### Feature Scaling 可以将特征的值除以它的最大值,使其取值在0附近。如特征F取值在[0,20],则将其除以20。 #### Mean Normalization 可以使用下面公式处理特征,使其拥有zero mean,同时缩小取值范围: $$ x := {x - \mu \over \sigma}$$ 其中,$\mu$为x的均值,$\sigma$为标准差。也有一种方式是将分母改为除以最大值减去最小值的差。在Matlab/Octave中均值和标准差可以分别通过函数`mean()`和`std()`求得。 ### Improve Features 我们可以通过添加新特征,或将累赘的多个特征合并为一个特征等手段改进模型的表现。模型的好坏和特征的选取息息相关。大多数情况下特征都是很难人工选取的。这时候可以使用**特征选择**(Feature selection)方法: - 向前选择法:添加新特征时,判断添加后模型的表现是否有所改进。若是,才添加此特征。 - 向后剔除法:评估现有参数,若去掉其后,模型的表现有所改进,则将其去除。 ### Polynomial Regression 有时候数据之间存在的不是简单的线性关系。对于非线性问题,可以通过增加多项式项拟合一条曲线,以获得更好的拟合效果。但这种情况下,要注意**过拟合**(Overfitting)问题。 ### Learning Rate α 学习率α的选取是让梯度下降工作地又快又好的要点,可以通过设置一组α值: $$ ..., 0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1, ...$$ 然后绘制不同α值下$J(\theta)$与迭代次数的函数图,获得最适合的α值。 ### Automatic Convergence Test 可以通过判断每次迭代后,$J(\theta)$的减少量来决定梯度下降是否收敛。例如,当减少量小于$10^{-3}$时认为结果收敛。然而在实际应用中,很难决定这个阈值。 赏 Wechat Pay Alipay Regression Techniques That You Should Know Coursera Machine Learning: submit problem solving