Trying to Remove for-Loops from Python code, Performing Operations with a Look-up Table On Matrices
<p>I feel like this is a similar problem to the one I asked before, but I can't figure it out. How can I convert these two lines of code into one line with no for-loop?</p>

<pre><code>for i in xrange(X.shape[0]):
  dW[:,y[i]] -= X[i]
</code></pre>

<p>In English, every row in matrix X should be subtracted from a corresponding column in matrix dW given by the vector y.</p>

<p>I should mention dW is DXC and X is NXD, so the transpose of X does not have the same shape as W, otherwise I could re-order the the rows of X, and take the transpose directly. However, it is possible for the columns in dW to have multiple corresponding rows which need to be subtracted.</p>

<p>I feel like I do not have a firm grasp of how indexing in python is supposed to work, which makes it difficult to remove unnecessary for-loops, or even to know what for-loops are possible to remove. </p>

<p><strong>Approach #1</strong> Here's a one-liner vectorized approach with <code>matrix-multiplication</code> using <a href="http://docs.scipy.org/doc/numpy/reference/generated/numpy.dot.html" rel="nofollow"><code>np.dot</code></a> and <a href="http://docs.scipy.org/doc/numpy/user/basics.broadcasting.html" rel="nofollow"><code>NumPy broadcasting</code></a> -</p>

<pre><code>dWout -= (np.arange(dW.shape[1])[:,None] == y).dot(X).T
</code></pre>

<p><strong>Explanation :</strong> Take a small example to understand what's going on -</p>

<p>Inputs :</p>

<pre><code>In [259]: X
Out[259]: 
array([[ 0.80195208,  0.40566743,  0.62585574,  0.53571781],
       [ 0.56643339,  0.4635662 ,  0.4290103 ,  0.14457036],
       [ 0.31823491,  0.12329964,  0.41682841,  0.09544716]])

In [260]: y
Out[260]: array([1, 2, 2])
</code></pre>

<p>First off, we create the 2D mask of <code>y</code> indices spread across the length of dW's second axis.</p>

<p>Let <code>dW</code> be a <code>4 x 5</code> shaped array. So, the mask would be :</p>

<pre><code>In [261]: mask = (np.arange(dW.shape[1])[:,None] == y)

In [262]: mask
Out[262]: 
array([[False, False, False],
       [ True, False, False],
       [False,  True,  True],
       [False, False, False],
       [False, False, False]], dtype=bool)
</code></pre>

<p>This is using <a href="http://docs.scipy.org/doc/numpy/user/basics.broadcasting.html" rel="nofollow"><code>NumPy broadcasting</code></a> here to create a <code>2D</code> mask.</p>

<p>Next up, we use matrix-multiplication to sum-aggregate the same indices from <code>y</code> -</p>

<pre><code>In [264]: mask.dot(X)
Out[264]: 
array([[ 0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.80195208,  0.40566743,  0.62585574,  0.53571781],
       [ 0.8846683 ,  0.58686584,  0.84583872,  0.24001752],
       [ 0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.        ]])
</code></pre>

<p>Thus, corresponding to the third row of the mask that has <code>True</code> values at second and third columns, we would sum up the second and third rows from <code>X</code> with that matrix-multiplication. This would be put as the third row in the multiplication output.</p>

<p>Since, in the original loopy code we are updating <code>dW</code> across columns, we need to transpose the multiplication result and then update.</p>

<hr>

<p><strong>Approach #2</strong> Here's another vectorized way, though not a one-liner using <a href="http://docs.scipy.org/doc/numpy/reference/generated/numpy.ufunc.at.html" rel="nofollow"><code>np.add.reduceat</code></a> -</p>

<pre><code>sidx = y.argsort()
unq,shift_idx = np.unique(y[sidx],return_index=True)
dWout[:,unq] -= np.add.reduceat(X[sidx],shift_idx,axis=0).T
</code></pre>

python numpy matrix indexing vectorization