Hope is a dangerous thing, but I have it.


【基础方法】Gradient Descent(梯度下降)

这段时间不是很忙,也看到Andrew Ng在Coursera上的machine learning开课了,就顺带着看看。第一周和第二周讲的都是比较简单的问题,主要就是介绍了Cost Function以及最小化的几个方法。我这里要说的就是其中的一种:Gradient desxcent(梯度下降)。
  梯度下降这个概念对很多人来说都不是很熟悉了,我之前看过关于HOG(方向梯度直方图)的一篇论文,再看梯度下降就有种熟悉感。

梯度下降的思想

在介绍梯度下降之前我们先引入一个Cost function(代价函数):
$$J(\theta_0,\theta_1,...,\theta_n)=\frac{1}{2m}\sum_{i=1}^{m}(h(x^i)-y^i)^2$$
  $\theta_t$是$x^t$对应的系数,$m$是样本总数,其中$h(x^i)$是第$i$个变量预测的结果,计算公式定义如下:
$$h(x^i)=\theta_0+\theta_1x_1+...+\theta_nx_n$$
  我们的目的就是最小化$J(\theta_0,\theta_1,...,\theta_n)$的值,这是一个有关于$\theta_0,\theta_1,...,\theta_n$的函数。这也是梯度下降想要求得的目标。
  假想我们站在一个山上(当然根据这个题目,这个山可能是多维的,但是不管),我们想要到达海拔最高的地,所以我们的选择是像更矮的地方迈出一步,然后一步一步走到最低点。这也就是梯度下降的思想,根据一定的策略减少$J$的值,然后达到最低点。因为$J(\theta_0,\theta_1,...,\theta_n)$是和$\theta_0,\theta_1,...,\theta_n$有关的函数,所以我们可以通过修改$\theta_0,\theta_1,...,\theta_n$的值来修改$J(\theta_0,\theta_1,...,\theta_n)$的大小。我们以前常用的一种方法就是通过求导来得到最小值所在的位置,梯度下降也是通过求导来逐步修改$\theta_0,\theta_1,...,\theta_n$的值。具体公式如下:
$$$$\begin{matrix}
\left\{
\begin{aligned}
\theta_0:=\theta_0-\alpha\frac{1}{2m}\sum_{i=1}^{m}(h(x^i)-y^i)\\
\theta_n:=\theta_n-\alpha\frac{1}{2m}\sum_{i=1}^{m}(h(x^i)-y^i)x^i_n\\
\end{aligned}
\right.
\end{matrix}$$$$
  

  其中$\alpha$是学习效率,即我们每次的步子究竟是要迈多大。太小了就会走的很慢,太大了容易一步迈过了最小值,可能离最小值越来越远。通常,我们函数在越靠近最小值时下降越平缓,所以没有必要手动的修改(可以设置为$...0.001,...,0.01,...,0.1,...,1...$)。所以我们每次迭代就是根据不同的$\theta$来计算,再根据不同的计算结果修改$\theta$,至于迭代结束的条件,可以设置两次大小相差不超过$10^{-3}$,或者预先设置好迭代次数。
  但是这也带来了一个问题,因为我们身在山中,只知道这个点是我们目前走到的局部最低点,而并不知道是不是想要的全局海拔最低的地方,所以相对应的,梯度下降也是只能得到局部最小值,而不能得到全局最小值。

matlab代码

虽然作业分了单个变量和多个变量,但是因为是用Matlab进行矩阵运算,所以写起来没有多大差别。

梯度下降

function [theta, J_history] = gradientDescent(X, y, theta, alpha, num_iters)
%GRADIENTDESCENT Performs gradient descent to learn theta
%   theta = GRADIENTDESCENT(X, y, theta, alpha, num_iters) updates theta by 
%   taking num_iters gradient steps with learning rate alpha

% Initialize some useful values
m = length(y); % number of training examples
J_history = zeros(num_iters, 1);

for iter = 1:num_iters

    % ====================== YOUR CODE HERE ======================
    % Instructions: Perform a single gradient step on the parameter vector
    %               theta. 
    %
    % Hint: While debugging, it can be useful to print out the values
    %       of the cost function (computeCost) and gradient here.
    %
    h=X*theta;
    theta=theta-alpha/m*((h-y)'*X)';

    % ============================================================

    % Save the cost J in every iteration    
    J_history(iter) = computeCost(X, y, theta);

end
end

计算代价函数

function J = computeCost(X, y, theta)
%COMPUTECOST Compute cost for linear regression
%   J = COMPUTECOST(X, y, theta) computes the cost of using theta as the
%   parameter for linear regression to fit the data points in X and y

% Initialize some useful values
m = length(y); % number of training examples

% You need to return the following variables correctly 
J = 0;

% ====================== YOUR CODE HERE ======================
% Instructions: Compute the cost of a particular choice of theta
%               You should set J to the cost.
h=X*theta;
J=1/2/m*(h-y)'*(h-y);

% =========================================================================

end

特征一般化

function [X_norm, mu, sigma] = featureNormalize(X)
%FEATURENORMALIZE Normalizes the features in X 
%   FEATURENORMALIZE(X) returns a normalized version of X where
%   the mean value of each feature is 0 and the standard deviation
%   is 1. This is often a good preprocessing step to do when
%   working with learning algorithms.

% You need to set these values correctly
X_norm = X;

% ====================== YOUR CODE HERE ======================
% Instructions: First, for each feature dimension, compute the mean
%               of the feature and subtract it from the dataset,
%               storing the mean value in mu. Next, compute the 
%               standard deviation of each feature and divide
%               each feature by it's standard deviation, storing
%               the standard deviation in sigma. 
%
%               Note that X is a matrix where each column is a 
%               feature and each row is an example. You need 
%               to perform the normalization separately for 
%               each feature. 
%
% Hint: You might find the 'mean' and 'std' functions useful.
%       

mun=mean(X);
sigma=std(X);
[m,~]=size(X);
for i=1:m
    X_norm(i,:)=(X(i,:)-mun)./sigma;
end
mu=mun;
% ============================================================

end

作业及代码放在github了。