Why is a simple regression problem so hard for an MLP to learn?

Question

Consider a very simple problem, which is to find the maximum value out of a list of 5 numbers between 0 and 1. This is obviously trivial, but serves as a good example for a real-world problem I'm facing.

One could attempt to train an MLP to solve this problem using randomly generated input data. The following code is an example in Keras/Tensorflow. It generates 1000000 random examples (A large number, so we can reduce overfitting as a factor). It also applies some simple techniques like LR decay and early stopping to optimize training.

import tensorflow as tf

# Create a dataset where the y value is the largest of 5 random x values.
x = tf.random.uniform(shape=(1000000, 5), minval=0.0, maxval=1.0)
y = tf.reduce_max(x, axis=-1)

dataset = tf.data.Dataset.from_tensor_slices(
    (x, y)
).shuffle(1000000).batch(1024).prefetch(1)

# See the post for discussion of hyperparameter optimization
units = 400
depth = 5
initial_learning_rate = 0.001

model = tf.keras.models.Sequential()

for i in range(depth):
    model.add(tf.keras.layers.Dense(units, activation="relu"))
model.add(tf.keras.layers.Dense(1))

model.compile(
    optimizer=tf.keras.optimizers.Adam(initial_learning_rate),
    loss=tf.keras.losses.MeanAbsolutePercentageError(),
)

stopping_callback = tf.keras.callbacks.EarlyStopping(monitor="loss", patience=5)

reduce_lr_callback = tf.keras.callbacks.ReduceLROnPlateau(monitor="loss", factor=0.75, patience=2)

model.fit(dataset, epochs=1000)

The metric we care about is the mean absolute percentage error. When we run the code, the model trains successfully. But very importantly, the loss does not ever go below ~0.2 with these hyperparameters.

0.2% error sounds pretty good, but it's actually unacceptable for my use case. I need much more precision, as in practice the model is used in a situation where any errors are magnified.

At this point, you may want to suggest hyperparameter tuning, but I assure you I have done an extensive amount of hyperparameter tuning on this and similar problems.

The model is clearly underfitting, and it is possible to decrease the error by increasing the number of parameters in the network. Empirically, I've noticed that increasing the number of parameters (and number of examples) by an order of magnitude can reduce the error by a similar order of magnitude.

However, intuitively this just feels wrong. It is not practical to have a network with millions, or even tens of millions of parameters, just to regress such a simple function. It feels like there should be an architecture that can learn a simple function much more efficiently, but I have not been able to find any reference to such an alternative architecture.

Again, of course this particular example is trivial, but hopefully you can imagine a real-world analogue where an unknown (more complex, but similar) function is expressed by a similar dataset. And in such a real-world example, the unacceptable error still persists (and is much more pronounced, for reasons that I don't fully understand).

Does anyone have any idea what's going on here? Am I missing something? How can I improve the performance to a place that would be acceptable?

Answer 1

An interesting problem. This network has only 933 trainable parameters, and obtains MeanAbsolutePercentageError of 0.01 - 0.04. It is based on a softmax activation, to choose which item from the input to choose.

n, dim, validation_split = 100000, 5, 0.1
X = tf.random.uniform(shape=(n, dim), minval=0.0, maxval=1.0)
y = tf.reduce_max(X, axis=-1)

initial_learning_rate = 0.003
act, units, depth = 'relu', 16, 3

inp = tf.keras.layers.Input(dim)
x = inp

for _ in range(depth):
    x = tf.keras.layers.Dense(units, activation=act)(x)
    x = tf.keras.layers.BatchNormalization()(x)

x = tf.keras.layers.Dense(int((dim * units)**0.5), activation="elu")(x)
x = tf.keras.layers.BatchNormalization()(x)

x = tf.keras.layers.Dense(dim, activation="softmax")(x)

# Skip this step to make categorical predictions
x = tf.reduce_sum(inp * x, axis=-1, keepdims=True)

model = tf.keras.models.Model(inp, x)
model.summary()

is_categorical = model.output.shape[1] == dim

model.compile(
    optimizer=tf.keras.optimizers.Adam(initial_learning_rate),
    loss=tf.keras.losses.CategoricalCrossentropy() if is_categorical else
         tf.keras.losses.MeanAbsolutePercentageError(),
    metrics=[tf.keras.metrics.CategoricalAccuracy()] if is_categorical else []
)

stopping_callback = tf.keras.callbacks.EarlyStopping(monitor="val_loss", patience=10, restore_best_weights=True)
reduce_lr_callback = tf.keras.callbacks.ReduceLROnPlateau(monitor="loss", factor=0.1**0.5, patience=5,
                                                          verbose=1, min_lr=1e-4)

target = tf.cast(X == y[:,None], tf.float32) if is_categorical else y

h = model.fit(X, target, verbose=1,
              batch_size=1024, epochs=10000, validation_split=validation_split,
              callbacks=[stopping_callback, reduce_lr_callback])

n_val = int(n * validation_split)
print([model.evaluate(X[:n_val],  target[:n_val]),
       model.evaluate(X[-n_val:], target[-n_val:])])

An alternative formulation outputs just the softmax activation, this obtains an accuracy of 98 - 99%. Granted, it isn't 100% accurate.

Summary of the model with just one output:

__________________________________________________________________________________________________
Layer (type)                    Output Shape         Param #     Connected to                     
==================================================================================================
input_273 (InputLayer)          [(None, 5)]          0                                            
__________________________________________________________________________________________________
dense_868 (Dense)               (None, 16)           96          input_273[0][0]                  
__________________________________________________________________________________________________
batch_normalization_577 (BatchN (None, 16)           64          dense_868[0][0]                  
__________________________________________________________________________________________________
dense_869 (Dense)               (None, 16)           272         batch_normalization_577[0][0]    
__________________________________________________________________________________________________
batch_normalization_578 (BatchN (None, 16)           64          dense_869[0][0]                  
__________________________________________________________________________________________________
dense_870 (Dense)               (None, 16)           272         batch_normalization_578[0][0]    
__________________________________________________________________________________________________
batch_normalization_579 (BatchN (None, 16)           64          dense_870[0][0]                  
__________________________________________________________________________________________________
dense_871 (Dense)               (None, 8)            136         batch_normalization_579[0][0]    
__________________________________________________________________________________________________
batch_normalization_580 (BatchN (None, 8)            32          dense_871[0][0]                  
__________________________________________________________________________________________________
dense_872 (Dense)               (None, 5)            45          batch_normalization_580[0][0]    
__________________________________________________________________________________________________
tf_op_layer_mul_251 (TensorFlow [(None, 5)]          0           input_273[0][0]                  
                                                                 dense_872[0][0]                  
__________________________________________________________________________________________________
tf_op_layer_Sum_329 (TensorFlow [(None, 1)]          0           tf_op_layer_mul_251[0][0]        
==================================================================================================
Total params: 1,045
Trainable params: 933
Non-trainable params: 112
__________________________________________________________________________________________________

I don't know what kind your original problem is, but maybe you could do some feature-engineering by supplying the min/max/median directly to the network. Then the network wouldn't need to learn to approximate those functions.

Answer 2

Assuming the $N$ numbers are different, a function that combines sums, products and the hard step function for solving the maximum may look like this.

$$ max(x_1,x_2,...,x_N) = \sum_{i=1}^N x_i \prod_{j=1,j\neq i}^N sign(x_i-x_j) $$

$sign(z)$ is $1$ for $z>0$ and $0$ for $z<0$.