|
The computational complexity of learning from binary examples is
investigated for linear threshold neurons. We introduce
combinatorial measures that create classes of infinitely many
learning problems with sample restrictions. We analyze how the
complexity of these problems depends on the values for the measures.
The results are established as dichotomy theorems showing that each
problem is either NP-complete or solvable in polynomial time.
In particular, we consider consistency and maximum consistency
problems for neurons with binary weights, and maximum consistency
problems for neurons with arbitrary weights. We determine for each
problem class the dividing line between the NP-complete and
polynomial-time solvable problems. Moreover, all efficiently
solvable problems are shown to have constructive algorithms that
require no more than linear time on a random access machine model.
Similar dichotomies are exhibited for neurons with bounded
threshold.
The results demonstrate on the one hand that the consideration of
sample constraints can lead to the discovery of new efficient
algorithms for non-trivial learning problems. On the other hand,
hard learning problems may remain intractable even for severely
restricted samples.
|
