4 ms·
You are correct. This is Cover's Theorem. "A complex pattern-classification problem, cast in a high-dimensional space nonlinearly, is more likely to be linear
by jo_ 12y ago
You are correct. This is Cover's Theorem.
"A complex pattern-classification problem, cast in a high-dimensional space nonlinearly, is more likely to be linearly separable than in a low-dimensional space, provided that the space is not densely populated." - Cover, Geometrical and Statistical properties of systems of linear inequalities with applications in pattern recognition., 1965
- mturmon 12y agoThis is a well-known observation, but it's not at all the issue I was trying to get at, and which the existence proof of the OP raised. From the last paragraph of the paper by George Cybenko referenced in the OP: "While the approximating properties we have described are quite powerful, we have focused only on existence. The important questions that remain to be answered deal with ... how many terms in the summation (or equivalently, how many neural nodes) are required to yield an approximation of a given quality? [...] We suspect quite strongly that the overwhelming majority of approximation problems will require astronomical numbers of terms. This feeling is based on the curse of dimensionality that plagues multidimensional approximation theory and statistics." [I'm highly familiar with both the paper by Cybenko, and the paper by Tom Cover on linear separability that is the source of the Wikipedia quote pasted above, having gone through them carefully as part of my PhD. Andrew Barron, mentioned above, was Tom Cover's student, and the work Andrew did can be viewed as another approach to this problem.]
- jo_ 12y agoI misunderstood intentions. I just wanted to chime in with the name of theorem I thought you were describing. I like knowing the names of theorems, and I had a hard time finding this name when I first looked for it.