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)$?

  • 1
    $\begingroup$ "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? $\endgroup$
    – kbrose
    Commented Jun 5, 2018 at 20:36
  • $\begingroup$ It's not really clear what you're asking for, as what you've described is effectively asking for generalization error. $\endgroup$
    – Alex R.
    Commented Jun 5, 2018 at 21:58
  • 1
    $\begingroup$ 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). $\endgroup$
    – Sycorax
    Commented Jun 6, 2018 at 15:36

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.