Implementation document

Time complexity analysis

Time complexity analysis isn't very interesting in neural networks, which are notoriously slow, as they require a lot of calculations for a large amount of data.

The speed can be somewhat augmented by using matrices; however, in the naive case, they aren't that fast either:

        for row in range(len(matrix1)):
            for col in range(len(matrix2[0])):
                sum = 0
                # i is column depth
                for i in range(len(matrix1[row])):
                    a = matrix1[row][i]
                    b = matrix2[col][i]
                    sum += a*b
                result[row][col] = sum

We can see, that matrix multiplication is O(n³) in the naive case as the multiplication is done for every row of the 1. matrix, we must access every column of the 2. matrix, as well as each cell in the first matrix. The procedure can be theoretically improved with Strassen algoritm, which however rarely works significantly better in the real world. In reality, the optimization is done on hardware level using, fast languages and a cache.

Another linear alegbra procedure, which is often needed (and is sort the lackey of the matrix multiplication) is transposing, where a new matrix is created, where the columns of the old matrix are turned into rows in the new one. This procedure takes naively O(n²), but again, can be heavily optimized on hardware level.

In this project I decided to focus on the functionality of the network, and so far I have only implemented matrix multiplication (and half of the motivation was to refresh my memory on its functionality). I have used a mixture of python lists and numpy arrays in the code.

I use the following operations provided by numpy:

• Matrix multiplication
• Transposing
• Summing the elements on a specific row in a matrix
• Calculating the shape of a matrix
• Matrix addition/substraction
• Doing the operation e^x on each cell x on a matrix
• Calculating the Euclidean distance between vectors
• Generating a matrix with random initial values

Comparing run times with pytorch

You can run the comparison file yourself. It is called pytorch_vs_neurose.py. In the tests I built the same neural network using both neurose and pytorch, and compared the running time with different batch sizes. The neural network is almost the same as in the linear regressione example: it as an input layer of size 1, a hidden layer of size 5, and an output layer of size 1. The tests are run without an activation function, and then by applying Sigmoid on the hidden and output layers. 'Training cycle' refers to a the combination reset parameters + forward pass + calculating loss + backpropagating weights and biases + update weights, i.e. one epoch.

We can see that unsuprisingly, neurose was slower than pytorch (even though I left matrix multiplication to numpy). Except for one batch size, Pytorch is faster than Neurose: with the batch size of 1 Neurose is actually faster than Pytorch. The bigger the batch, the bigger the difference gets. Surprisingly, using an activation function didn't have as big an effect on neurose as it does on pytorch. This is probably due to some optimization in numpy, as the most demanding operation of the sigmoid function is np.exp.

Using batch size of 1
----------------------------------
without any activation
    training cycle with neurose took in average 0.0001057744026184082 seconds
    training cycle with torch took in average 0.00014873409271240235 seconds
    difference: -4.295969009399415e-05 seconds
with sigmoid as activation function
    training cycle with neurose took in average 0.0001366419792175293 seconds
    training cycle with torch took in average 0.00021657896041870118 seconds
    difference: -0.00011080455780029298 seconds
    with neurose, using an activation made the process 29.182463653781156% slower
    with torch, using an activation made the process 45.614873139735444% slower
----------------------------------

Using batch size of 10
----------------------------------
without any activation
    training cycle with neurose took in average 0.00017309951782226563 seconds
    training cycle with torch took in average 0.00015230178833007811 seconds
    difference: 2.079772949218752e-05 seconds
with sigmoid as activation function
    training cycle with neurose took in average 0.00023024225234985352 seconds
    training cycle with torch took in average 0.00017643117904663085 seconds
    difference: -3.3316612243652183e-06 seconds
    with neurose, using an activation made the process 33.01149260638649% slower
    with torch, using an activation made the process 15.843143393863498% slower
----------------------------------

Using batch size of 100
----------------------------------
without any activation
    training cycle with neurose took in average 0.0008359627723693848 seconds
    training cycle with torch took in average 0.00016092872619628907 seconds
    difference: 0.0006750340461730958 seconds
with sigmoid as activation function
    training cycle with neurose took in average 0.0008628993034362793 seconds
    training cycle with torch took in average 0.00020394325256347656 seconds
    difference: 0.0006320195198059082 seconds
    with neurose, using an activation made the process 3.2222165815527677% slower
    with torch, using an activation made the process 26.728929870930262% slower
----------------------------------

Using batch size of 1000
----------------------------------
without any activation
    training cycle with neurose took in average 0.007394265651702881 seconds
    training cycle with torch took in average 0.00025064849853515626 seconds
    difference: 0.007143617153167725 seconds
with sigmoid as activation function
    training cycle with neurose took in average 0.007814988613128663 seconds
    training cycle with torch took in average 0.0004698009490966797 seconds
    difference: 0.006924464702606201 seconds
    with neurose, using an activation made the process 5.689854560863533% slower
    with torch, using an activation made the process 87.43417648312179% slower
----------------------------------

Using batch size of 10000
----------------------------------
without any activation
    training cycle with neurose took in average 0.10261127758026123 seconds
    training cycle with torch took in average 0.0014822888374328613 seconds
    difference: 0.10112898874282837 seconds
with sigmoid as activation function
    training cycle with neurose took in average 0.10001712560653686 seconds
    training cycle with torch took in average 0.0026449556350708007 seconds
    difference: 0.09996632194519042 seconds
    with neurose, using an activation made the process -2.5281353423314075% slower
    with torch, using an activation made the process 78.43726325643338% slower
----------------------------------

The differences between the two seem small now, but with bigger networks they have a big effect.