Recently, in an interview I got this question:
Design a convnet that sorts numbers. Operators are ReLU, Conv, and Pooling. E.g. input: 5, 3, 6, 2; output: 2, 3, 5, 6
I am not sure how can you sort a list of numbers using CNN. I know it is possible using RNN. Is it even possible?
I have a solution however I use a densely connected layer at the output to simplify the reshaping. If you can manipulate the sizes of this model such that you have 4 output parameters this should work as well.
from __future__ import print_function
import keras
from keras.datasets import mnist
from keras.models import Sequential
from keras.layers import Dense, Dropout, Flatten
from keras.layers import Conv1D, MaxPooling1D, Reshape
from keras.callbacks import ModelCheckpoint
from keras.models import model_from_json
from keras import backend as K
We will generate some random lists containing integers between [0,49], we will take a random permutation of the list and then take the first 4 values. We will then set our targets $y$ as the sorted rows of $x$.
import numpy as np
n = 100000
x_train = np.zeros((n,4))
for i in range(n):
x_train[i,:] = np.random.permutation(50)[0:4]
x_train = x_train.reshape(n, 4, 1)
y_train = np.sort(x_train, axis=1).reshape(n, 4,)
n = 1000
x_test = np.zeros((n,4))
for i in range(n):
x_test[i,:] = np.random.permutation(50)[0:4]
x_test = x_test.reshape(n, 4, 1)
y_test = np.sort(x_test, axis=1).reshape(n, 4,)
print(x_test[0][0].T)
print(y_test[0])
[ 44. 36. 13. 0.]
[ 0. 13. 36. 44.]
I tried different combinations of parameters. This worked out not bad.
input_shape = (4,1)
model = Sequential()
model.add(Conv1D(32, kernel_size=(2),
activation='relu',
input_shape=input_shape,
padding='same'))
model.add(Conv1D(64, (2), activation='relu', padding='same'))
model.add(MaxPooling1D(pool_size=(2)))
model.add(Reshape((64,2)))
model.add(Conv1D(32, (2), activation='relu', padding='same'))
model.add(MaxPooling1D(pool_size=(2)))
model.add(Flatten())
model.add(Dense(4))
model.compile(loss=keras.losses.mean_squared_error,
optimizer=keras.optimizers.Adadelta(),
metrics=['accuracy'])
epochs = 10
batch_size = 128
# Fit the model weights.
history = model.fit(x_train, y_train,
batch_size=batch_size,
epochs=epochs,
verbose=1,
validation_data=(x_test, y_test))
Epoch 10/10
100000/100000 [==============================] - 6s 56us/step - loss: 0.9061 - acc: 0.9973 - val_loss: 0.5302 - val_acc: 0.9950
So for a new list of values, I get the predicted output. Then I determine which value in the original list is closest to each of these and replace them. I could have just rounded the predicted values, however this caused so +/-1 errors due to rounding the wrong way.
test_list = [1,45,3,18]
pred = model.predict(np.asarray(test_list).reshape(1,4,1))
print(test_list)
print(pred)
print([np.asarray(test_list).reshape(4,)[np.abs(np.asarray(test_list).reshape(4,) - i).argmin()] for i in list(pred[0])])
[1, 45, 3, 18]
[[ 0.87599814 3.43058085 17.36335754 45.21624374]]
[1, 3, 18, 45]
And for the sequence you suggested as a test case
test_list = [5,3,6,2]
pred = model.predict(np.asarray(test_list).reshape(1,4,1))
print(test_list)
print(pred)
print([np.asarray(test_list).reshape(4,)[np.abs(np.asarray(test_list).reshape(4,) - i).argmin()] for i in list(pred[0])])
[5, 3, 6, 2]
[[ 1.85080266 2.95598722 4.92955017 5.88561296]]
[2, 3, 5, 6]
It's possible to encode a version of Bubble Sort by hand, that can be shown to correctly sort numbers.
Bubble Sort proceeds by flipping adjacent elements of the array which are inverted. For example,
3 2 1
x
2 3 1
x
2 1 3
x
1 2 3
This can be implemented with a double for loop
for i in 0..n {
for j in i+1..n {
if arr[i] > arr[j] {
arr[i], arr[j] = arr[j], arr[i];
}
}
}
To begin, we will design a swap layer which can swap adjacent elements to correct their order.
Let $X_i$ be the input vector encoded as floats. The swap layer $Y_i$ has the same size as the input. All equations are written with $0$ based indexing.
$$ Y_i = \begin{cases} min(X_i, X_{i+1}) & \text{if $i$ is even} \\ max(X_i, X_{i-1}) & \text{if $i$ is odd} \\ \end{cases} $$
The odd case needs a stride 2 max pool followed by transposed convolution that pads a zero on the left.
3 2 1 5
\| \|
=> 3 5 (Max Pool)
=> 0 3 0 5 (Padding)
The even case is just a stride 2 min pool (explained later) followed by a transposed convolution layer that pads the input with 0 on the right,
3 2 1 5
|/ |/
=> 2 1 (Min Pool)
=> 2 0 1 0 (Zero padding)
The two pools are then summed to produce a swap layer. Summing can be done with a simple 1x1 conv layer with stride 1.
0 3 0 5
+ 2 0 1 0
-------
= 2 3 1 5
The overall structure of a swap layer looks like this,
Input --> MinPool -- Zero pad-- + --> Swapped
| |
|----> MaxPool -- Zero pad --|
Notice the swap layer works locally in a 1x2 receptive field. To allow bubble sort like movement across fields, the next swap layer has be shifted by 1 position, thus inverting the odd-even rule above.
2 3 1 5 -> 0 3 0 5 (Max)
-> 2 0 1 0 (Min)
-------
2 3 1 5
Following up with a non-offset swap layer again completes the example,
2 1 3 5 -> 1 0 3 0 (Min)
-> 0 2 0 5 (Max)
-------
1 2 3 5
Stacking enough swap layers would eventually sort the array since each pair of swap layers will fix at least one inversion and there are at most $^{n}C_2$ inversions.
The min pool can be implemented with 2 1x1 convolution layers with linear activations and 1 max pool in between since,
$$min(a, b) = -max(-a, -b)$$
ReLU activations can't pass negative numbers but you can use ReLU if you assume that a large positive number has been added to the inputs to make them all positive and then subtracted out at the output.
Thus, sorting can be done with $O(n^2)$ layers with $n$ neurons each.
