逻辑回归的向量化实现样例

From Ufldl

Jump to: navigation, search
 
Line 1: Line 1:
我们想用批量梯度上升法对logistic回归分析模型进行训练,其模型如下:
我们想用批量梯度上升法对logistic回归分析模型进行训练,其模型如下:
-
<math>h_{\theta }\left( x\right) =\dfrac {1} {1+exp\left( -\theta ^{T}x\right) }</math>
+
:<math>\begin{align}
 +
h_\theta(x) = \frac{1}{1+\exp(-\theta^Tx)},
 +
\end{align}</math>
让我们遵从公开课程视频与CS229教学讲义的符号规范,设 <math>\textstyle x_0=1</math>,于是<math>x\in R^{n+1}</math> ,<math>\theta \in R^{n+1}</math>, <math>\textstyle \theta_0</math> 为截距。假设我们有m个训练样本{(<math>x^\left( 1\right) </math>,<math>y^\left( 1\right)</math> ) ,...,(<math>x^\left( m\right)</math> ,<math>y^\left( m\right)</math> )},而批量梯度上升法的更新法则是:<math>\theta :=\theta +\alpha \nabla _{\theta }l\left( \theta \right) </math> ,这里的 <math>l\left( \theta \right) </math> 是对数似然函数,<math>\nabla _{\theta }l\left( \theta \right) </math> 是其导函数。
让我们遵从公开课程视频与CS229教学讲义的符号规范,设 <math>\textstyle x_0=1</math>,于是<math>x\in R^{n+1}</math> ,<math>\theta \in R^{n+1}</math>, <math>\textstyle \theta_0</math> 为截距。假设我们有m个训练样本{(<math>x^\left( 1\right) </math>,<math>y^\left( 1\right)</math> ) ,...,(<math>x^\left( m\right)</math> ,<math>y^\left( m\right)</math> )},而批量梯度上升法的更新法则是:<math>\theta :=\theta +\alpha \nabla _{\theta }l\left( \theta \right) </math> ,这里的 <math>l\left( \theta \right) </math> 是对数似然函数,<math>\nabla _{\theta }l\left( \theta \right) </math> 是其导函数。
Line 9: Line 11:
于是,我们需要如下计算梯度:
于是,我们需要如下计算梯度:
-
<math>\nabla _{\theta }l\left( \theta \right) =\sum _{i=1}^{m}\left( y^{\left( i\right) }-h_{\theta }\left( x^{\left( i\right) }\right) \right) x_{j}^{\left( i\right) }</math>
+
:<math>\begin{align}
 +
\nabla_\theta \ell(\theta) = \sum_{i=1}^m \left(y^{(i)} - h_\theta(x^{(i)}) \right) x^{(i)}_j.
 +
\end{align}</math>
 +
 
 +
我们用Matlab/Octave风格变量x表示输入数据构成的样本矩阵,x(:,i)代表第 i个训练样本<math>x^{\left( i\right) }</math>,x(j,i)就代表<math>x_{j}^{\left( i\right) }</math>(译者注:第i个训练样本向量的第j个元素)。同样,用Matlab/Octave风格变量y表示由训练样本集合的全体类别标号所构成的行向量,则该向量的第i个元素y(i)就代表上式中的<math>y^{\left(i\right) }\in \left\{ 0,1\right\} </math>。(注意这里跟公开课程视频及CS229的符号规范不同,矩阵x按列而不是按行存放输入训练样本,同样,<math>y\in R^{1\times m}</math>是行向量而不是列向量。)
-
我们用Matlab/Octave风格变量x表示输入数据构成的样本矩阵,x(:,i)代表第 i个训练样本<math>x^{\left( i\right) }</math>,x(j,i)就代表<math>x_{j}^{\left( i\right) }</math>(译者注:第i个训练样本向量的第j个元素)。同样,用Matlab/Octave风格变量y表示由训练样本集合的全体标号所构成的向量,则变量y(i) 就代表该向量中的每个元素,即上式中的<math>y^{\left( 1\right) }\in \left\{ 0,1\right\} </math>(注意这里跟公开课程视频及CS229的符号规范不同,矩阵x按列而不是按行存放输入训练样本,同样,<math>y\in R^{1\times m}</math>是行向量而不是列向量。)
 
以下是梯度运算代码的一种实现,非常恐怖,速度极慢:
以下是梯度运算代码的一种实现,非常恐怖,速度极慢:
-
  % 代码1
+
<syntaxhighlight lang="matlab">
-
  grad = zeros(n+1,1);
+
% 代码1
-
  for i=1:m,
+
grad = zeros(n+1,1);
-
    h = sigmoid(theta'*x(:,i));
+
for i=1:m,
-
    temp = y(i) - h;  
+
  h = sigmoid(theta'*x(:,i));
-
    for j=1:n+1,
+
  temp = y(i) - h;  
-
      grad(j) = grad(j) + temp * x(j,i);  
+
  for j=1:n+1,
-
    end;
+
    grad(j) = grad(j) + temp * x(j,i);  
-
  end;
+
  end;
 +
end;
 +
</syntaxhighlight>
 +
 
嵌套的for循环语句使这段代码的运行非常缓慢。以下是更典型的实现方式,它对算法进行部分向量化,带来更优的执行效率:
嵌套的for循环语句使这段代码的运行非常缓慢。以下是更典型的实现方式,它对算法进行部分向量化,带来更优的执行效率:
-
  % 代码2
+
<syntaxhighlight lang="matlab">
-
  grad = zeros(n+1,1);
+
% 代码2
-
    for i=1:m,
+
grad = zeros(n+1,1);
-
      grad = grad + (y(i) - sigmoid(theta'*x(:,i)))* x(:,i);
+
for i=1:m,
-
  end;
+
  grad = grad + (y(i) - sigmoid(theta'*x(:,i)))* x(:,i);
 +
end;
 +
</syntaxhighlight>
 +
 
但是,或许可以向量化得更彻底些。如果去除for循环,我们就可以显著地改善代码执行效率。特别的,假定b是一个列向量,A是一个矩阵,我们用以下两种方式来计算A*b:
但是,或许可以向量化得更彻底些。如果去除for循环,我们就可以显著地改善代码执行效率。特别的,假定b是一个列向量,A是一个矩阵,我们用以下两种方式来计算A*b:
-
  % 矩阵-向量乘法运算的低效代码
+
<syntaxhighlight lang="matlab">
-
  grad = zeros(n+1,1);
+
% 矩阵-向量乘法运算的低效代码
-
  for i=1:m,
+
grad = zeros(n+1,1);
-
    grad = grad + b(i) * A(:,i);  % 通常写法为A(:,i)*b(i)
+
for i=1:m,
-
  end;
+
  grad = grad + b(i) * A(:,i);  % 通常写法为A(:,i)*b(i)
-
+
end;
-
  % 矩阵-向量乘法运算的高效代码
+
 
-
  grad = A*b;
+
% 矩阵-向量乘法运算的高效代码
 +
grad = A*b;
 +
</syntaxhighlight>
 +
 
我们看到,代码2是用了低效的for循环语句执行梯度上升(译者注:原文是下降)运算,将b(i)看成(y(i) - sigmoid(theta'*x(:,i))),A看成x,我们就可以使用以下高效率的代码:
我们看到,代码2是用了低效的for循环语句执行梯度上升(译者注:原文是下降)运算,将b(i)看成(y(i) - sigmoid(theta'*x(:,i))),A看成x,我们就可以使用以下高效率的代码:
-
  % 代码3
+
<syntaxhighlight lang="matlab">
-
  grad = x * (y- sigmoid(theta'*x));
+
% 代码3
 +
grad = x * (y- sigmoid(theta'*x));
 +
</syntaxhighlight>
 +
 
这里我们假定Matlab/Octave的sigmoid(z)函数接受一个向量形式的输入z,依次对输入向量的每个元素施行sigmoid函数,最后返回运算结果,因此sigmoid(z)的输出结果是一个与z有相同维度的向量。
这里我们假定Matlab/Octave的sigmoid(z)函数接受一个向量形式的输入z,依次对输入向量的每个元素施行sigmoid函数,最后返回运算结果,因此sigmoid(z)的输出结果是一个与z有相同维度的向量。
Line 54: Line 71:
想采用向量化实现并非易事,通常需要周密的思考。但当你熟练掌握向量化操作后,你会发现,这里面有固定的设计模式(对应少量的向量化技巧),可以灵活运用到很多不同的代码片段中。
想采用向量化实现并非易事,通常需要周密的思考。但当你熟练掌握向量化操作后,你会发现,这里面有固定的设计模式(对应少量的向量化技巧),可以灵活运用到很多不同的代码片段中。
 +
 +
 +
==中英文对照==
 +
 +
:逻辑回归 Logistic Regression
 +
:批量梯度上升法 batch gradient ascent
 +
:截距 intercept term
 +
:对数似然函数 the log likelihood
 +
:导函数 derivative
 +
:梯度 gradient
 +
 +
 +
==中文译者==
 +
 +
林锋(xlfg@yeah.net),谭晓阳(x.tan@nuaa.edu.cn),邓亚峰(dengyafeng@gmail.com)
 +
 +
 +
{{矢量化编程实现}}
 +
 +
 +
{{Languages|Logistic_Regression_Vectorization_Example|English}}

Latest revision as of 08:31, 8 April 2013

Personal tools