Logistic Regression Vectorization Example

From Ufldl

Jump to: navigation, search
Line 46: Line 46:
</syntaxhighlight>
</syntaxhighlight>
-
However, it turns out to be possible to even further vectorize this.  In Matlab/Octave,
+
However, it turns out to be possible to even further vectorize this.  If we can get rid of the for-loop, we can significantly speed up the implementation.  In particular, suppose <tt>b</tt> is a column vector, and <tt>A</tt> is a matrix.  Consider the following ways of computing <tt>A * b</tt>:
-
it is possible to get rid of for-loops, and doing so will speed up the algorithm.  In
+
<syntaxhighlight lang="matlab">
-
particular, we can implement the following:  
+
% Slow implementation of matrix-vector multiply
 +
grad = zeros(n+1,1);
 +
for i=1:m,
 +
  grad = grad + b(i) * A(:,i);  % more commonly written A(:,i)*b(i)
 +
end;
 +
 
 +
% Fast implementation of matrix-vector multiple
 +
grad = A*b
 +
</syntaxhighlight>
 +
 
 +
We recognize that Implementation 2 of our gradient descent calculation above is using the slow version with a for-loop, with
 +
<tt>b(i)</tt> playing the role of <tt>(y(i) - sigmoid(theta'*x(:,i)))</tt>.  We can derive a fast implementation as follows:  
<syntaxhighlight lang="matlab">
<syntaxhighlight lang="matlab">
% Implementation 3
% Implementation 3
Line 55: Line 66:
Here, we assume that the Matlab/Octave <tt>sigmoid(z)</tt> takes as input a vector <tt>z</tt>, applies the sigmoid function component-wise to the input, and returns the result.  The output of <tt>sigmoid(z)</tt> is therefore itself also a vector, of the same dimension as the input <tt>z</tt>  
Here, we assume that the Matlab/Octave <tt>sigmoid(z)</tt> takes as input a vector <tt>z</tt>, applies the sigmoid function component-wise to the input, and returns the result.  The output of <tt>sigmoid(z)</tt> is therefore itself also a vector, of the same dimension as the input <tt>z</tt>  
-
When the training set is large, this final implementation takes the greatest advantage of Matlab/Octave's highly optimized numerical linear algebra libraries to carry out the matrix-vector operations, and so this is far more efficient than the earlier implementations.
+
When the training set is large, this final implementation takes the greatest advantage of Matlab/Octave's highly optimized numerical linear algebra libraries to carry out the matrix-vector operations, and so this is far more efficient than the earlier implementations
 +
 
 +
Coming up with vectorized implementations isn't always easy, and sometimes requires careful thought.  But as you gain familiarity with vectorized operations, you'll find that there are design patterns (i.e., a small number of ways of vectorizing) that apply to many different pieces of code.

Revision as of 01:38, 27 February 2011

Personal tools