# Given an output space for a Neural Net, what is the minimum input space for training and prediction?

As far as I can tell, a neural net computes an arbitrary function from an input set $X$ to an output set $Y$ through the magic of back propagation (i.e. it computes $f: X \rightarrow Y$).

Suppose we have a known task, with a given input space and output space. Also, we have successfully trained a neural net to predict the function with 99% accuracy. Take a subset of the input space $Z \subset X$. What is the minimum size of $Z$ such that the neural net, when given $Z$ as an input space, correctly predicts the restricted function $f_Z : Z \rightarrow Y$? We assume that $|Y| < |Z| < |X|$.

There is another similar problem which is that we want to predict the same restricted function, but we train on the smaller set $Z$. Put simply, again suppose we have a trained a neural net on a large input set $X$, that successfully computes $f$ with 99% accuracy. I now want to collect less data as the input and train the neural net on a smaller subset of information, $Z \subset X$. I want the NN to compute the restricted function $f_Z$, ie the same function as $f$, with the same codomain, but a restricted domain $Z$.

What is the smallest input subset I can use for these two problems? Is it a function of the size of $Y$ or $X$? Is there, perhaps, a metric of the complexity of $f$, call it $Comp(f)$. Could $Z$ be bounded by a function of $Comp(f)$?

• "Is it a function of the size of Y and/or X?" -- Yes, but almost certainly not a practically computable function. Is this a theoretical question or are you coming from an actual application? Commented Jun 5, 2018 at 20:36
• It's not really clear what you're asking for, as what you've described is effectively asking for generalization error. Commented Jun 5, 2018 at 21:58
• It seems impossible to say anything in general. You could have a binary classification task with a single relevant, but arbitrarily high-quality feature. Or you could have no relevant features. Or all features could be relevant. Or you could know that the problem is structured in a particular way, in which case you can get by using a smaller, specialized network (compare a CNN and FFN on MNIST to see what I mean).
– Sycorax
Commented Jun 6, 2018 at 15:36

## 1 Answer

There is no answer to the problem:

• If you keep the same features: reducing the samples could lead to an improvement in accuracy by removing noise and outliers, a loss of accuracy if you remove good unique observations, or no change.
• If you keep the same samples: reducing the features could lead to an improvement in accuracy by removing irrelevant features, a loss of accuracy by removing important features, or no change.

In general, giving more good unique observations to the network and relevant features will reduce the bias.