19
$\begingroup$

My goal is to solve the following problem, which I have described by its input and output:

Input:

A directed acyclic graph $G$ with $m$ nodes, $n$ sources, and $1$ sink ($m > n \geq 1$).

Output:

The VC-dimension (or an approximation of it) for the neural network with topology $G$.

More specifics:

  • Each node in $G$ is a sigmoid neuron. The topology is fixed, but the weights on the edges can be varied by the learning algorithm.
  • The learning algorithm is fixed (say backward-propagation).
  • The $n$ source nodes are the input neurons and can only take strings from $\{-1,1\}^n$ as input.
  • The sink node is the output unit. It outputs a real value from $[-1,1]$ that we round up to $1$ or down to $-1$ if it is more than a certain fixed threshold $\delta$ away from $0$.

The naive approach is simply to try to break more and more points, by attempting to train the network on them. However, this sort of simulation approach is not efficient.

Question

Is there an efficient way (i.e. in $\mathsf{P}$ when changed to the decision-problem: is VC-dimension less than input parameter $k$?) to compute this function? If not, are there hardness results?

Is there a works-well-in-practice way to compute or approximate this function? If it is an approximation, are there any guarantees on its accuracy?

Notes

I asked a similar question on stats.SE but it generated no interest.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It might make the question more self-contained if you could make the transfer function more explicit. I.e specify the actual formulas for how the information propagates. $\endgroup$
    – Suresh
    Apr 25, 2012 at 15:48

1 Answer 1

Reset to default
9
$\begingroup$

If you are willing to constrain the problem further by letting the network be layered, then Tom Mitchell's "Machine Learning" gives an upper bound of ( $2ds \log(es)$) (section 7.4.4) where $s$ is the number of internal nodes (which must be higher than 2), $d$ is the VC dimension of the individual nodes, and $e$ is the base of the natural logarithm. If you're after a bound on the number of training examples then this information should be enough.

It's not strictly an answer to your question, but it might help you on the way. The result is due to Baum and Haussler (1989).

Improve this answer
$\endgroup$

Your Answer

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

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