np.add.at indexing with array

Question

I'm working on cs231n and I'm having a difficult time understanding how this indexing works. Given that

x = [[0,4,1], [3,2,4]]
dW = np.zeros(5,6)
dout = [[[  1.19034710e-01  -4.65005990e-01   8.93743168e-01  -9.78047129e-01
            -8.88672957e-01  -4.66605091e-01]
         [ -1.38617461e-03  -2.64569728e-01  -3.83712733e-01  -2.61360826e-01
            8.07072009e-01  -5.47607277e-01]
         [ -3.97087458e-01  -4.25187949e-02   2.57931759e-01   7.49565950e-01
           1.37707667e+00   1.77392240e+00]]

       [[ -1.20692745e+00  -8.28111550e-01   6.53041092e-01  -2.31247762e+00
         -1.72370321e+00   2.44308033e+00]
        [ -1.45191870e+00  -3.49328154e-01   6.15445782e-01  -2.84190582e-01
           4.85997687e-02   4.81590106e-01]
        [ -1.14828583e+00  -9.69055406e-01  -1.00773809e+00   3.63553835e-01
          -1.28078363e+00  -2.54448436e+00]]]

The operation they do is

np.add.at(dW, x, dout)

x is a two dimensional array. How does indexing work here? I went through np.ufunc.at documentation but they have simple examples with 1d array and constant:

np.add.at(a, [0, 1, 2, 2], 1)

Answer 1

In [226]: x = [[0,4,1], [3,2,4]]
     ...: dW = np.zeros((5,6),int)

In [227]: np.add.at(dW,x,1)
In [228]: dW
Out[228]: 
array([[0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 1, 0],
       [0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0, 0]])

With this x there aren't any duplicate entries, so add.at is the same as using += indexing. Equivalently we can read the changed values with:

In [229]: dW[x[0], x[1]]
Out[229]: array([1, 1, 1])

The indices work the same either way, including broadcasting:

In [234]: dW[...]=0
In [235]: np.add.at(dW,[[[1],[2]],[2,4,4]],1)
In [236]: dW
Out[236]: 
array([[0, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 2, 0],
       [0, 0, 1, 0, 2, 0],
       [0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0]])

possible values

The values have to be broadcastable, with respect to the indexes:

In [112]: np.add.at(dW,[[[1],[2]],[2,4,4]],np.ones((2,3)))
...
In [114]: np.add.at(dW,[[[1],[2]],[2,4,4]],np.ones((2,3)).ravel())
...
ValueError: array is not broadcastable to correct shape
In [115]: np.add.at(dW,[[[1],[2]],[2,4,4]],[1,2,3])

In [117]: np.add.at(dW,[[[1],[2]],[2,4,4]],[[1],[2]])

In [118]: dW
Out[118]: 
array([[ 0,  0,  0,  0,  0,  0],
       [ 0,  0,  3,  0,  9,  0],
       [ 0,  0,  4,  0, 11,  0],
       [ 0,  0,  0,  0,  0,  0],
       [ 0,  0,  0,  0,  0,  0]])

In this case the indices define a (2,3) shape, so (2,3),(3,), (2,1), and scalar values work. (6,) does not.

In this case, add.at is mapping a (2,3) array onto a (2,2) subarray of dW.

Answer 2

recently I also have a hard time to understand this line of code. Hope what I got can help you, correct me if I am wrong.

The three arrays in this line of code is following:

x , whose shape is (N,T)
dW,  ---(V,D)
dout ---(N,T,D)

Then we come to the line code we want to figure out what happens

np.add.at(dW, x, dout)

If you dont want to know the thinking procedure. The above code is equivalent to :

for row in range(N):
   for col in range(T):
      dW[ x[row,col]  , :] += dout[row,col, :]

---

This is the thinking procedure:

Refering to this doc

https://docs.scipy.org/doc/numpy-1.13.0/reference/generated/numpy.ufunc.at.html

We know that the x is the index array. So the key is to understand dW[x]. This is the concept of indexing an array(dW) using another array(x). If you are not familiar with this concept, can check out this link

https://docs.scipy.org/doc/numpy-1.13.0/user/basics.indexing.html

Generally speaking, what is returned when index arrays are used is an array with the same shape as the index array, but with the type and values of the array being indexed.

dW[x] will give us an array whose shape is (N,T,D), the (N,T) part comes from x, and the (D) comes from dW (V,D). Note here, every element of x is inside the range of [0, v).

Let's take some number as concrete example

x:    np.array([[0,0],[0,0]]) ---- (2,2) N=2, T=2
dW:   np.array([[0,0],[2,2]]) ---- (2,2) V=2, D=2
dout: np.arange(1,9).reshape(2,2,2)  ----(2,2,2) N=2, T=2, D=2

dW[x] should be [ [[0 0] #this comes from the dW's firt row
                  [0 0]]

                  [[0 0]
                   [0 0]] ]

dW[x] add dout means that add the elemnet item(here, this some trick, later will explian)

np.add.at(dW, x, dout) gives 
 [ [16 20]
   [ 2  2] ]

Why? The procedure is:

It add [1,2] to the first row of dW, which is [0,0].

Why first row? Because the x[0,0] = 0, indicating the first row of dW, dW[0] = dW[0,:] = the first row.

Then it add [3,4] to the first row of dW[0,0]. [3,4]=dout[0,1,:]. [0,0] again, comes from the dW, x[0,1] = 0, still the first row of dW[0].

Then it add [5,6] to the first row of dW.

Then it add [7,8] to the first row of dW.

So the result is [1+3+5+7, 2+4+6+8] = [16,20]. Because we do not touch the second row of dW. The dW's second row remains unchanged.

The trick is that we will only count the origin row once, can think that there is no buffer, and every step plays in the original place.