This is a very interesting perspective on neural networks, is it novel? I've never seen a geometric interpretation of NNs.
In particular this:
> (Apparently determining if knots are trivial is NP. This doesn’t bode well for neural networks.)
Is there any theoretical research on obstructions to NN learning? Not that it would change much the practice (for instance, MLE learning of gaussian mixtures is NP-hard, but everybody does it anyway), but it could shed some light on the geometry of the "hard" instances.
EDIT: for example, to get a sense of how ill-conditioned is deep NN learning, a recent paper [1] shows that if we feed to an object classifying NN an image with crafted but unnoticeable perturbations the predictions change completely.
There is large body of work from the mid 1980s and early 1990s that addresses the question of hardness, sensitivity and robustness from various statistical physics/computer science collaborations. Of course, it is still ongoing, but that was a big period. The basic thrust of this program is to take methods from statistical mechanics and use them calculate not just worst case complexity, but also average case, best case, and everything in between. It is hard to think of a reference to end all references, but as far as books go you might want to check out: http://www.amazon.com/The-Nature-Computation-Cristopher-Moor.... For an article that briefly addresses some results related to kSAT there is: http://www.cs.cornell.edu/selman/papers/pdf/99.nature.phase.....
I have seen Riemann geometry applied to neural networks. Basically the state space is curved, so you can speed up learning if take the curvature into account when sampling in the space of possible neural nets. (you want to explore the hypothesis space evenly)
Information geometry for Neural networks, 1998, Daniel Wagenaar:-
I think the author has confused NP with NP-hard (or NP-complete). Indeed, it is extremely unlikely that the unknottedness problem is NP-complete, as it is already in NP ∩ co-NP (assuming the generalized Riemann hypothesis). Furthermore, we know that the problem of computing many knot invariants is "only" BQP-complete, so it's possible that unknottedness is in BQP (i.e., efficiently solvable by quantum computers), though I don't know the expert opinion on this.
Indeed I read that as NP-complete. That's very interesting, do you have any references on it?
Even if knots are ruled out, there might be hard topological decision problems that can be reduced to linear separability under homeomorphism, maybe in higher dimension.
I think machine learning boils down to 2 fundamental issues:
1) Having a model class that is powerful enough to represent the data.
and
2) Being able to find a "good enough" optimal solution over that model class.
In principle over-fitting can be addressed through the choice of the particular optimization criteria in (2).
Neural networks are used because they are powerful enough to represent many data sets of interest and because there exist good algorithms for finding LOCAL optima.
Unfortunately they are complex non-linear, non-convex functions and hence finding a global optimum is most likely NP-hard.
We are left then with the heuristic of hoping that the local optima we are able to find are "close enough" to the global optimum to meet our needs.
This seems to work reasonably well for certain types of problems, like image classification, where the underlying data possess a certain simplicity or "smoothness", but less well for other problems, like logic problems where good and bad solutions may not be "near by" in any sense that the local optimization algorithms are able to discover.
In particular this:
> (Apparently determining if knots are trivial is NP. This doesn’t bode well for neural networks.)
Is there any theoretical research on obstructions to NN learning? Not that it would change much the practice (for instance, MLE learning of gaussian mixtures is NP-hard, but everybody does it anyway), but it could shed some light on the geometry of the "hard" instances.
EDIT: for example, to get a sense of how ill-conditioned is deep NN learning, a recent paper [1] shows that if we feed to an object classifying NN an image with crafted but unnoticeable perturbations the predictions change completely.
[1] http://arxiv.org/abs/1312.6199