一元线性回归-梯度下降法
在高数中，我们求解一个函数的最小值时，最常用的方法就是求出它的导数为0的那个点，进而判断这个点是否能够取最小值。但是，在实际很多情况，我们很难求解出使函数的导数为0的方程，这个时候就可以使用梯度下降。我们知道对于一个函数沿着梯度的那个方向是下降是最快的。例如为了选取一个θ使J(θ)最小，我们可以先随机选择θ一个初始值，然后不断的修改θ以减小J(θ)，直到θ的值不再改变。对于梯度下降法，可以表示为：
θj=θj−α*∂J(θ)/∂θj
即不断地向梯度的那个方向（减小最快的方向）更新θ，最终使得J(θ)最小。其中α称为学习速率（learning rate），取值太小会导致迭代过慢，取值太大可能错过最值点。
假设我们有一堆数据集，这些数据集用散点图的方式，可以用一元线性回归方程表示，那么我们表示成如下公式
数据集为
image.png
假设我们建立模型 y=h(x)=θ0+θ1x
那么我们的预期是让通过对两个参数θ0和θ1的调整，将y的实际值和模型输出预测值的偏移量尽量的小，于是有
image.png
θ0和θ1两个参数的变化我们用J（θ0，θ1）表示
image.png
如何求出J（θ0，θ1）的最小值，这里就引入了梯度下降算法。主要思想是，J（θ0，θ1）好比是层峦叠嶂的群山，任意指定一个θ0和θ1，好比你在群山中的任意一个点，如何下山，一般都会瞭望四周，选择当前下山最陡的方向向下走。于是你又从A到达B，在B点，同样的情景，你将会选择下一步何去何从，同样的，选择当前最陡的路径向下走去。
如此周而复始，终将到达一个相对低，局部最优的位置。
如何将这一思想落实在数学上，是机器学习的基础。
首先先复习一下几个基本概念。
1.导数和微分
image.png
导数的定义如下
image.png
导数反映的是函数y=f(x)在某一点处沿x轴正方向的变化率。也就是在x轴上某一点处，如果f’(x)>0，说明f(x)的函数值在x点沿x轴正方向是趋于增加的；如果f’(x)<0，说明f(x)的函数值在x点沿x轴正方向是趋于减少的。
偏导数的定义
image.png
偏导数的定义和导数类似，都是当自变量的变化量趋于0时，函数值的变化量与自变量变化量比值的极限。直观地说，偏导数也就是函数在某一点上沿坐标轴正方向的的变化。区别在于导数为一元变量，偏导数为多元变量。
方向导数的定义
image.png
即：某一点在某一趋近方向上的导数值。 通俗的解释是： 我们不仅要知道函数在坐标轴正方向上的变化率（即偏导数），而且还要设法求得函数在其他特定方向上的变化率。而方向导数就是函数在其他特定方向上的变化率。
梯度的定义如下
image.png
梯度的提出只为回答一个问题：
函数在变量空间的某一点处，沿着哪一个方向有最大的变化率？ 函数在某一点的梯度是这样一个向量，它的方向与取得最大方向导数的方向一致，而它的模为方向导数的最大值。
这里注意三点：
1）梯度是一个向量，即有方向有大小；
2）梯度的方向是最大方向导数的方向；
3）梯度的值是最大方向导数的值。
既然在变量空间的某一点处，函数沿梯度方向具有最大的变化率，那么在优化目标函数的时候，自然是沿着负梯度方向去减小函数值，以此达到我们的优化目标。
如何沿着负梯度方向减小函数值呢？既然梯度是偏导数的集合，如下
image.png
同时梯度和偏导数都是向量，那么参考向量运算法则，我们在每个变量轴上减小对应变量值即可，梯度下降法可以描述如下：
这就是梯度下降法的数据原理。
参考http://blog.csdn.net/walilk/article/details/50978864
为什么从函数的梯度方向下降可以得到函数的最小值
梯度下降法，基于这样的观察：如果实值函数F(x)在点a 处可微且有定义，那么函数 F(x)在a点沿着梯度相反的方向−▽F(a)−▽F(a)下降最快。
因而，如果
b=a−α▽F(a)
b=a−α▽F(a)
那么F(b)≤F(a)F(b)≤F(a)。
考虑如下序列x0,x1,x2,...x0,x1,x2,...使得
xn+1=xn−α▽F(xn)
xn+1=xn−α▽F(xn)
因此可以得到： F(x0)≥F(x1)≥F(x2)≥...F(x0)≥F(x1)≥F(x2)≥... 如果顺利的话序列最终可以收敛到期望的极值。
注意：梯度下降得到的结果可能是局部最优值。如果F(x)F(x)是凸函数，则可以保证梯度下降得到的是全局最优值。
批量梯度下降法的算法
批梯度下降法（batch gradient descent）的算法描述如下：
对每一个j重复以下过程直到收敛 {
image.png
}
其中假设训练样本数有m个，每个样本用zi可以表示为(xi,yi)。可以看出，使用批梯度下降法每一次更新θj都需要遍历训练样本中的所有样本。
批量梯度下降法代码
#coding=utf-8
##
#Calculate the hypothesis h = X * theta
#Calculate the loss = h - y and maybe the squared cost (loss^2)/2m
#Calculate the gradient = X' * loss / m
#Update the parameters theta = theta - alpha * gradient
###
import numpy as np
from numpy import *
import random
def loadDataSet(filename):
numFeat = len(open(filename).readline().split(','))-1
datMat = []; labelMat = []
fr = open(filename)
for line in fr.readlines():
lineArr = []
curLine = line.strip().split(',')
for i in range(numFeat):
lineArr.append(float(curLine[i]))
datMat.append(lineArr)
labelMat.append(float(curLine[-1]))
return datMat,labelMat
#x为自变量训练集，y为自变量对应的因变量训练集；theta为待求解的权重值，需要事先进行初始化；alpha是学习率；m为样本总数；maxIterations为最大迭代次数；
def batchGradientDescent(x, y, theta, alpha, m, maxIterations):
xTrains = x.transpose() #x 转置
for i in range(0, maxIterations):
hypothesis = np.dot(x, theta) #矩阵乘法，https://migege.com/post/matrix-multiplication-in-numpy 计算f(x(k))
loss = hypothesis - y
#print(loss)
#print(m)
#print(type(loss))
# avg cost per example (the 2 in 2*m doesn't really matter here.
# But to be consistent with the gradient, I include it)
cost = np.sum(loss ** 2) / (2 * m)
print("Iteration %d | Cost: %f" % (i, cost))
# avg gradient per example
gradient = np.dot(xTrains, loss) / m ##梯度
#print("gradinet is ",gradient)
# update
theta = theta - alpha * gradient #x(k+1)
#print("theta is ",theta)
return theta
xArr,yArr = loadDataSet('gmvusers3.csv')
xArr1 = asarray(xArr)
yArr1 = asarray(yArr)
#print("xArr is ",asarray(xArr))
#print("yArr is ",asarray(yArr))
#print(asarray(xArr).dtype)
#print(asarray(yArr).dtype)
m, n = np.shape(xArr1)
print("m %d | n %d" %(m,n))
numIterations= 10000
alpha = 0.00000001
theta = [1,1] #Return a new array of given shape and type, filled with ones. 初始值。
theta = batchGradientDescent(xArr1, yArr1, theta, alpha, m, numIterations)
print(theta)
####
# gen 100 points with a bias of 25 and 10 variance as a bit of noise
#x, y = genData(100, 25, 10)
#print(x)
#print(y)
#print(x.dtype)
#print(y.dtype)
#m, n = np.shape(x)
#numIterations= 100000
#alpha = 0.0001
#theta = np.ones(n)
#theta = batchGradientDescent(x, y, theta, alpha, m, numIterations)
#print(theta)
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(yArr1,'go')
xCopy = xArr1.copy()
xCopy.sort(0)
yHat=xCopy*theta
ax.plot(xCopy[:,1],yHat)
plt.show()
print(yArr1)
print(yHat)
print(corrcoef(yHat.T,yArr1)) ???
'''
其他深度学习好的文章http://sebastianruder.com/optimizing-gradient-descent/
'''
学习速率的注意条件
参数α为初始学习速率，代表着梯度下降的速率，需要选择一个合适的参数。
在学习速率为固定值的时候，这个参数不能太小，否则学习的步数太多，程序的速度很慢，你可能需要很长一段时间才能收敛；但是也不能选的太大，
否则，你可能会发现，或许一开始J很快就接近收敛了，但是步长太大，之后并没有收敛，而是出了点状况。你会发现，代价函数的值不但迟迟不收敛，
反而可能会越来越发散，以至于结果变得糟糕起来，甚至会导致直接跨过谷底到达另一端，这就是所谓的“步子太大，迈过山谷”。至于这个参数如何选择，
需要有一定的经验，不过可以提前多选几个值做一下试验，比如用0.001，发现太慢，用0.1，发现过一段时间会发散，0.01既不太慢也不会发散，那就选择这个参数。
或者我们可以根据梯度下降每一步的实际情况动态调整学习速率，使用可变的学习速率，这就是上式的由来。我们设定一个初始的学习速率，这个学习速率也不能太大，
否则一开始就会发散，当然也不能太小，否则速度太慢。在优化的过程中，学习速率应该逐步减小，越接近“山谷”的时候，迈的“步伐”应该越小。我们每走一步，
数据分布与直线的误差越小，而这时梯度也会减小，那么步伐也就应当相应的减小，这就是初始学习速率乘上代价函数负梯度的原因。本实例中，经过我的试验，学习
速率选择为0.0001比较合适。
值得说明的是，在进行梯度下降的时候，我们应当尽量使用限定迭代次数的循环，而不是用判断是否收敛的循环。原因很简单，一旦出现你的结果是发散的，限定
迭代次数的循环可以使你的程序很快停止下来，而因为你的结果永远不会收敛，所以，如果你用while进行判断是否收敛的话，你将很有可能陷入死循环，因为你的
结果永远不可能收敛。这里我把迭代步数设为100步。
https://blog.ailemon.me/2017/02/10/machine-learningregression-statistic-model/
特征量标准化
如果我们能够将输入各个特征变量统一在相同范围内，则会加速梯度下降的效果。这是应为 θ 在小范围内将会下降的很快，在大范围内将会下降的很慢.
为了避免无谓的计算，理想状态下，我们最好能将输入变量限定在−1 ≤ x(i) ≤ 1或者−0.5 ≤ x(i) ≤ 0.5。由于目的只是为了将梯度下降效果优化，只需将各个输入X统一在一个较小的范围内即可。
一般选用两种方法：
- Feature scaling. X(i) 除以最大值和最小值的差,让X(i)在绝对值区间1之间.
- Mean normalization，公式为:xi:=xi−μisi ； μi 为 feature (i) 的均值 and si 为值的范围 (max - min), or si 为标准差。
除了批梯度下降法之外，还有一种算法称为——随机梯度下降法（stochastic gradient descent，SGD）。算法描述如下：
image.png
每一次更新只使用了一个训练样本，但更新了m次。
批梯度下降法每更新一步都需要遍历所有的样本数据，如果样本数m很大的话，就会非常的耗时；而对于随机梯度下降，每一遇到一个样本数据，就可以马上更新。通常情况下，使用随机梯度下降法的速度会比批梯度下降法快很多。因此，当样本数很大的时候，我们通常都选择使用随机梯度下降法。
参考
http://www.wengweitao.com/ti-du-xia-jiang-fa.html
另外梯度下降极容易受到异常值的影响，使用前最好删掉异常值。
