黄耀鹏，统计硕士，喜欢历史八卦
博客：http://yphuang.github.io/
1.梯度下降算法的理解
我们在求解最优化问题的时候，需要最小化或最大化某一个目标函数。如线性回归中，就需要最小化残差平方和。
某一向量的平方和函数可定义如下：
def sum_of_squares(v):
"""computes the sum of squared elements in v"""
return sum(v_i ** 2 for v_i in v)
梯度定义
若f(x,y,z)在点P0(x0,y0,z0)存在对所有自变量的偏导数，则称向量(fx(P0),fy(P0),fz(P0))为函数ff在点P0的梯度,记为：
由于某一方向上ll的方向导数公式可以写成
其中，θ为梯度向量gradf(P0)与ll方向上的单位向量l0的夹角。
从而，当f可微时，ff在P0的梯度方向是ff的值增长最快的方向。
梯度下降算法的直观理解
由于梯度方向是使得函数值下降最快的方向,从而快速求解到目标函数最小值的一种途径就是：
随机选择一个起点，计算梯度；
朝着负梯度（即使得该点目标函数值下降最快的方向）移动一小步；
重新计算新的位置的梯度，继续朝梯度方向移动一小步
如此循环，直到目标函数值的变化达到某一阈值或者最大迭代次数。
梯度下降算法的局限性
以求解目标函数最小化为例，梯度下降算法可能存在一下几种情况：
当目标函数存在全局最小值时，这种方法可以快速的找到最优解；
当目标函数存在多个局部最小值时，可能会陷入局部最优解。因此需要从多个随机的起点开始解的搜索。
当目标函数不存在最小值点，则可能陷入无限循环。因此，有必要设置最大迭代次数。
2.梯度的估计
梯度的精确计算，需要对目标函数求偏导。
这里，对于一元函数的梯度计算，我们可以采用如下函数进行估计：
from __future__ import division
def difference_quotient(f,x,h):
return (f(x h)-f(x))/h
其中，h→0
对于多元函数，我们可以如下定义梯度估计函数：
# 先定义偏导估计函数
def partial_difference_quotient(f,v,i,h):
"""compute the i-th partial difference quotient of f at v"""
w = [v_j (h if j==i else 0)
for j,v_j in enumerate(v)]
return (f(w)-f(v))/h
# 再定义梯度估计函数
def estimate_gradient(f,v,h=0.00001):
return [partial_difference_quotient(f,v,i,h)
for i,_ in enumerate(v)]
3.梯度的使用
这里，先通过一个简单的例子测算梯度下降算法是否有效。
假设我们要求解的目标函数是：Minf(X)=XTX,其中，XX为一个三维的向量。则其梯度为2X,不难计算出其最小值点为[0,0,0]
下面，通过梯度下降法来求解。
### 定义步长函数
def step(v,direction,step_size):
"""move step_size in the direction from v"""
return [v_i step_size * direction_i
for v_i,direction_i in zip(v,direction)]
### 定义梯度
def sum_of_squares_gradient(v):
return [2 * v_i for v_i in v]
import random
### 选择一个随机的起点
v = [random.randint(-10,10) for i in range(3)]
### 定义向量距离
#######################
#### 减法定义
def vector_substract(v,w):
"""substracts coresponding elements"""
return [v_i - w_i
for v_i,w_i in zip(v,w)]
### 向量的点乘
def dot(v,w):
return sum(v_i * w_i
for v_i,w_i in zip(v,w))
### 向量的平房和
def sum_of_squares(v):
"""v_1*v_1 v_2*v_2 ... v_n*v_n"""
return dot(v,v)
### 向量的距离
##### method 1:
def distance(v,w):
""""""
return sum_of_squares(vector_substract(v,w))
### 进行迭代计算
tolerance = 0.000000001
max_iter = 1000000
iter = 1
while True:
gradient = sum_of_squares_gradient(v)
next_v = step(v,gradient,-0.01)
if (distance(next_v,v)
注册
登录
