鲭兜的博客


努力に胜る天才无し


机器学习笔记(第二周)

1、Multivariate Linear Regression 多变量线性回归

适用于多个输入量或者多个特征量的情况。

Notation 记号说明

1、使用$X$的下标来表示这是第几个特征量,$x_1,x_2,x_3,\cdots,x_n$。
2、n = number of features $n$表示特征量的数目。
3、$x^{(i)}$ = input(features) of $i^{th}$ training example 表示第$i$个训练样本的输入特征值,是一个$n$维列向量,上标其实就是训练集的一个索引。
4、$x_j^{(i)}$ = value of feature $j$ in $i^{th}$ training example 表示第$i$个训练样本的第$j$个特征量的值。根据图形显然,这表示的是一个$m$行$n$列矩阵的第$i$行第$j$列的数(输入特征值形成一个矩阵,预测值形成一个列向量)。

1-1、假设函数

之前单变量的假设函数显然已经不适用了,我们可以类比得到
$h_{\theta}(x)={\theta}_0+{\theta}_1x_1+{\theta}_2x_2+\cdots+{\theta}_nx_n$

1-2、简化假设函数

为了标记的简便,不妨假设$x_0=1$,这样就允许我们对假设函数使用矩阵操作加速运算。
那么就有,对于每一个训练样本,$x_0^{(i)}=1,i\in[1,m]$。
不妨理解为我们定义了一个额外的第0个特征量。
所以现在的特征向量$X$可以表示为
$X=
\begin{bmatrix}
x_0 \\\
x_1 \\\
x_2 \\\
. \\\
. \\\
x_n
\end{bmatrix}
\in R^{n+1}
$
$X$是一个$n+1$维向量。
同样,我们可以把所有参数聚合在一起表示为
${\theta}=
\begin{bmatrix}
{\theta}_0 \\\
{\theta}_1 \\\
{\theta}_2 \\\
. \\\
. \\\
{\theta}_n
\end{bmatrix}
\in R^{n+1}
$
同样${\theta}$也是一个n+1维向量。
那么简化假设函数为$h_{\theta}(x)={\theta}_0x_0+{\theta}_1x_1+{\theta}_2x_2+\cdots+{\theta}_nx_n \\ =\displaystyle\sum_{i=0}^n{\theta}_ix_i \\ ={\theta}^TX$
这就是多特征量情况下的假设形式。

1-3、Gradient Descent for Multiple Variables 多变量下的梯度下降

对于多元线性回归,不妨不要将参数想成n+1个单独的参数,而是想成一个n+1维的向量(即不妨认为只是一个参数)。
代价函数
$J({\theta})=J({\theta}_0,{\theta}_1,\cdots,{\theta}_n)=\frac{1}{2m}\displaystyle\sum_{i=1}^m{(h_{\theta}(x^{(i)})-y^{(i)})}^2$
同样的,不要将$J$函数想成一个关于n+1个自变量的函数,而是一个自变量是一个n+1维向量的函数,即只有一个参数。
Gradient Descent 梯度下降算法
Repeat{
  ${\theta}_j:={\theta}_j-{\alpha}\dfrac{\partial}{\partial{\theta}_j}J({\theta}_0,\cdots,{\theta}_n)$
}
simultaneously update for every $j=0,\cdots,n$
将$J$函数的偏导数求出来,函数就变成下面的式子
Repeat{
  ${\theta}_j:={\theta}_j-{\alpha}\dfrac{1}{m}\displaystyle\sum_{i=1}^m(h_{\theta}(x^{(i)})-y^{(i)})x_j^{(i)}$
}
simultaneously update for every $j=0,\cdots,n$
这样就得到了多元线性回归的梯度下降算法,也很显然的可以看出解决多元的梯度下降是解决单元的一般形式($x_0^{(i)}=1$),这两种算法其实是一回事。

1-4、Gradient Descent in Practice 梯度下降运算中的实用技巧

1-4-1、Feature Scaling 特征缩放

Make sure features are on a similar scale.
不妨假设有个多元线性回归问题,如果你能确保所有特征量都处在一个相近的范围,即确保不同特征的取值在相近的范围内,这样梯度下降算法就能更快地收敛。
如果特征量的取值范围相差很大($x_1$的取值范围远远大于$x_2$),那么轮廓图里面(不妨想象成只有两个参数${$\theta}_1$和${\theta}_2$)的椭圆将会又细又长。如果你用这种代价函数来运行梯度下降的话,收敛速度会很慢并且可能来回波动。
特征缩放可以有效的解决这个问题。分析原因,之所以收敛速度变慢,是因为特征量的取值范围相差很大。那么不妨人为的将特征值的取值范围规划到一个固定的范围,轮廓图近似接近圆,那么收敛速度将会大大加快。
Get every feature into approximately a $-1\le x_i\le+1$ range.
更一般的,我们通常将特征的取值约束到-1到+1的范围内。当然-1,+1这两个数并不是很重要,主要是保证所有特征值的取值范围相差不大即可(当然首先得考虑$x_0=1$,那么其他特征量最好都在1的附近取值)。不仅范围大不好,范围太小也不行,比如[-0.0001,+0.0001]相对于[-1,+1]来说也不是可行的范围,那就要考虑特征缩放了。
除了将特征量除以最大值以外,我们还可以用到Mean Normalization 均值归一化的方法。
Replace $x_i$ with $x_i-{\mu}_i$ to make features have approximately zero mean (Do not apply to $x_0=1$).
用$x_i-{\mu}_i$ 来替换$x_i$, 通过这样做让特征值具有为0的平均值,可以将所有特征值变化到[-0.5,+0.5]之间(可能会大于,但是基本保持接近)。
一般的,特征缩放可以参照下面的公式
$x_i\leftarrow\dfrac{x_i-{\mu}_i}{s_i}$
${\mu}_i$ is the average of all the values for feature ($i$) 表示在训练集中特征$x_i$的平均值。
$s_i$ is the range of values (max - min), or the standard deviation表示该特征值的范围(最大值减去最小值),也可以将$s_i$设置为该特征值的标准差。
只要将特征转换为相似的范围就都是可以的,特征缩放其实不需要那么精确,只是为了能让梯度下降算法运行的快一点。

1-4-2、Learning Rate 学习率 $\alpha$

Making sure gradient descent is working correctly.
在梯度下降算法运行时,绘出代价函数的值,即绘出代价函数随迭代步数增加的变化曲线。
$J(\theta)$ should decrease after every iteration.
Debugging gradient descent: Make a plot with number of iterations on the x-axis. Now plot the cost function, J(θ) over the number of iterations of gradient descent. If J(θ) ever increases, then you probably need to decrease α.
如果梯度下降算法运行正常,那么每一步迭代后,代价函数的值都应该下降
如果代价函数(近似)保持一个值,没有继续下降,那么可能说明梯度下降基本已经收敛了。曲线可以帮助你判断梯度下降算法是否已经收敛。
Automatic convergence test: Declare convergence if J(θ) decreases by less than E in one iteration, where E is some small value such as $10^{−3}$. However in practice it’s difficult to choose this threshold value.
也可以进行Automatic convergence test 自动收敛测试:Declare convergence if $J(\theta)$ decreases by less than $10^{-3}$ in one iteration 但是这个阈值是很难确定的。
Choose learning rate correctly.
时刻查看这条曲线也可以提前警告你,如果梯度下降没有正常运行。
总结的说的话,如果在曲线中出现了增长,那么梯度下降就没有正常运行,而且一般都是因为学习率太大(排除代码错误),只要减小学习率即可。
For sufficiently small $\alpha$, $J(\theta)$ should decrease on every iteration. 除非它已经收敛了。
But if $\alpha$ is too small, gradient descent can be slow to converge.
Summary
if $\alpha$ is too small: slow convergence
if $\alpha$ is too large: $J(\theta)$ may not decrease on every iteration; may not converge
To choose $\alpha$, try
$\dots$, 0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1, $\dots$

1-5、Features and Polynomial Regression 特征选择与多项式回归

1-5-1、特征选择

当选择了合适的特征之后,可以得到不同的学习算法。
不妨以房价预测为例,假设你有两个特征,分别是房子临街的宽度和垂直宽度。当然你可以采用多元线性回归模型,将房子临街的宽度和垂直宽度作为两个特征量。但是,不一定非要直接使用给出的数据作为特征,也可以根据已有的特征量创造出新的特征。根据实际情况,房价应该和房屋占地面积有直接的关系。那么不妨将房子临街宽度乘以垂直宽度得到房屋占地面积,以此作为特征量而使用单元线性回归模型。相比较而言,我认为第二种模型更加符合实际。
特征选取取决于你从什么角度去审视一个特定的问题,而不是直接使用问题已知的参数。有时候,通过定义一个新的特征,你会得到一个更好的模型。

1-5-2、Polynomial Regression 多项式回归

不妨假设有一个回归问题,需要使用三次函数进行拟合,三次函数写作$h_{\theta}(x)={\theta}_0+{\theta}_1x+{\theta}_2x^2+{\theta}_3x^3$。
我们还没有学习过非线性回归问题的解决方法,我们可以将这个问题转化为多元线性回归。
$h_{\theta}(x)={\theta}_0+{\theta}_1x+{\theta}_2x^2+{\theta}_3x^3 \\ ={\theta}_0+{\theta}_1(size)+{\theta}_2{(size)}^2+{\theta}_3(size)^3 \\ x_1=(size) \\ x_2=(size)^2 \\ x_3=(size)^3$
我们将每个$(size)^i$都作为一个特征量$x_i$,通过之前的预计算和将高次幂化简为特征量,将一个三次函数拟合模型转化为了多元线性回归模型。
但是出现了另一个问题,这样选择特征量的话,特征量的归一化就是必要的。
我认为,多项式回归可以使用在许多非线性函数模型中,主要是看使用者是否拥有丰富的函数库,比如$h_{\theta}(x)={\theta}_0+{\theta}_1x^1+{\theta}_2x^2+\cdots+{\theta}_nx^n+{\theta}_{n+1}\sqrt{x}$。
在某些回归问题中,二次函数模型是不合适的,因为二次函数模型可能前面拟合的很好,但是之后会出现一个下降的趋势,这与大部分实际情况是不相符的。很显然的,我们考虑使用一个三次函数模型来重新拟合。但是别忘了,加上一个平方根函数的,也是可以的(这就需要多次模型调优),比如$h_{\theta}(x)={\theta}_0+{\theta}_1(size)+{\theta}_2\sqrt{(size)}$。

2、Normal Equation 正规方程

对于某些线性回归问题,用正规方程求解参数${\theta}$的最优值更好更快。

2-1、比较

梯度下降:为了最小化代价函数$J({\theta})$我们使用的迭代算法,需要经过很多步,通过多次迭代来收敛到全局最小值。
Normal Equation: Method to solve for ${\theta}$ analytically.
正规方程提供一种求解$\theta$的解析解法,可以一步求解$\theta$的最优值。

2-2、直观理解

假设有一个代价函数$J(\theta)=a{\theta}^2+b\theta+c,\theta\in R$
为了得到代价函数的最小值,我们一般采用求导的方法,将导数置为0,这样就可以求得使得$J(\theta)$最小的$\theta$值。
前面讨论的是$\theta$是实数的情况,接着我们转而讨论它是一个n+1维的参数向量。
$J({\theta}_0,{\theta}_1,…,{\theta}_n)=\dfrac{1}{2m}\displaystyle\sum_{i=1}^m(h_{\theta}(x^{(i)})-y^{(i)})^2,\theta\in R^{n+1}$
事实上微积分给出了一种数值方法,对每个参数$\theta_i$求$J$的偏导数,然后把他们都置为0,并且求出所有的$\theta_i$值,这样也可以得到答案。
$\dfrac{\partial}{\partial{\theta}_j}J(\theta)=\dots=0$ for every $j$
solve for ${\theta_0},{\theta}_1,\dots,{\theta}_n$

2-3、简单计算

将所有特征数据(要加上$x_0$)放到一个矩阵$X$,是一个$m*(n+1)$矩阵
将所有输出值放到一个向量$y$中,是一个m维列向量
那么要求的$\theta =(X^TX)^{-1}X^Ty$就是使得$J(\theta)$取到最小值的参数。
$x^{(i)}=
\begin{bmatrix}
x_0^{(i)} \\\
x_1^{(i)} \\\
x_2^{(i)} \\\
. \\\
. \\\
. \\\
x_n^{(i)} \\\
\end{bmatrix}
\in R^{n+1}
$
$X=
\begin{bmatrix}
{x^{(1)}}^T \\\
{x^{(2)}}^T \\\
. \\\
. \\\
. \\\
{x^{(m)}}^T
\end{bmatrix}
$
$Y=
\begin{bmatrix}
y^{(1)} \\\
y^{(2)} \\\
. \\\
. \\\
. \\\
y^{(m)}
\end{bmatrix}
$
$(X^TX)^{-1}$ is inverse of matrix $X^TX$.
Octave命令:

1
pinv (X'*X)*X'*y

在Octave中,$X’$表示$X$的转置,pinv()表示求解矩阵的逆矩阵。
注意:如果你使用的是正规方程法求解代价函数的最小值,那么就不需要使用均值归一化的方法来缩放特征,但是梯度下降算法可能需要。

2-4、推导过程

不妨假设$Rss=\displaystyle\sum_{i=1}^m(h_{\theta}(x^{(i)})-y^{(i)})^2=(h(X)-Y)^T(h(X)-Y)$
而假设函数$h(X)=X\theta$
所以$Rss=(X\theta-Y)^T(X\theta-Y)$
根据微积分和凸函数可知,当导数$\dfrac{\partial Rss}{\partial\theta}$时,$Rss$取到最小值
所以$\dfrac{\partial Rss}{\partial\theta}=2X^T(X\theta-Y)=0$
所以$X^TX\theta=X^TY$
所以$\theta=(X^TX)^{-1}X^TY$

2-5、梯度下降和正规方程的优劣

梯度下降
缺点一:Need to choose $\alpha$ 需要选择学习率,需要运行多次尝试不同的学习率,然后找到效果最好的那个
缺点二:Need many iterations 需要更多次的迭代,因为一些细节计算可能会很慢
优点一:Works well even when $n$ is large 梯度下降算法在有很多特征量的情况下也能运行地相当好
正规方程
缺点一:Need to compute $(X^TX)^{-1}$, slow if $n$ is very large 为了求解参数$\theta$需要求解这一项,实现逆矩阵计算所需要的计算量是矩阵维度的三次方,即$o(n^3)$
优点一:No need to choose $\alpha$ 不需要选择学习速率
优点二:Don’t need to iterate 不需要迭代操作,不需要画出运行曲线来检查收敛性或者其他额外的步骤
Summary
无法加载图片
如果$n$很大的话($n\ge10000$),使用梯度下降算法更加好;但如果$n$很小,那么正规方程算法可以更快地求解

2-6、Normal Equation Noninvertibility 正规方程的不可逆性

问题:如果$(X^TX)$是不可逆的怎么办?即$(X^TX)$没有逆矩阵?即$(X^TX)$是奇异矩阵?
首先$(X^TX)$不可逆的情况很少发生。
在Octave中,有两个函数可以求解逆矩阵,一个是inv(),另一个是pinv()。在计算过程中有所区别,一个是所谓的伪逆,另一个被称为逆。使用pinv()函数一定可以求解$\theta$,即便矩阵$(X^TX)$是不可逆的。inv()引入了先进的数值计算概念。
如果矩阵$(X^TX)$是不可逆的,通常有两种最常见的原因。
Redundant features(linearly dependent)
存在多余的特征,比如以平方英尺来计算房子面积的特征量和以平方米来计算房子面积的特征量,满足$x_1=(3.28)^2x_2$,那么参考线性代数的知识很显然这个矩阵一定是不可逆的,因为存在两个列向量之间是相关的。
Too many features $m\le n$
存在大量的特征值,比如尝试在10个训练样本中找到满足101个参数的值。
删除一些特征是一种方法。
但是并不是不可能在小数据样本中得到大量参数值,但是不能使用正规方程,我们一般使用正则化的线性代数方法。
Summary
如果你真的遇到矩阵$(X^TX)$是不可逆矩阵,首先看看特征值中是否存在一些多余的特征(线性相关的),可以删除重复特征而只保留其中的一个。然后,检查是否有过多的特征,如果特征数量实在是过多,那么删除部分特征或者使用正则化的方法就可以了。