The Nature of Statistical Learning Theory

What Hacker News says

1. d_burfootJul 2023
   Hi Bob, thanks for the kind words and for sharing with HN. For TinyML, you need to go in almost the opposite direction of what my book suggests, since the model complexity limits are so strict! I think MDL should be very helpful, but make sure you understand the danger of "manual overfitting" that I described in the book. I would also encourage you to read Vapnik's book the Nature of Statistical Learning Theory, which shows the relation b/t MDL and VC theory. Feel free to reach out to me at firstname dot lastname at gmail.com, I'm always happy to chat about these ideas.
   Show morethread
2. wnewmanAug 2019
   Both proof and explanation seem to be important. Two experiences with explanation made a particular impression on me.

   First I found it hard to get much out of a Real Analysis course when I was a grad student. Only partly because of lack of explanations, admittedly. Probably even more of a problem was another kind of cultural mismatch between physical scientist me and the math prof that taught the course. My interest was mostly that I was actually doing path integral Monte Carlo calculations (for my Chemistry thesis) and wanted to make sure I understood the fundamentals. The prof, like many (most?) mathematicians seemed to be more interested in investigating ingeniously weird boundary cases. So the course didn't seem to teach me much about the gotchas that might come up in actual statistics or numerical analysis, and instead more about the ingenuity of mathematicians in constructing absurdly farfetched abuses of e.g. the axiom of choice. But besides that cultural mismatch, lack of an explanatory framework sure didn't help. Thus, I was very happy decades later when I ran across Terence Tao's book on measure theory (available as a free manuscript online), which had a lot of the same kind of material with quite a good framework of motivation and explanation wrapped around its proofs.

   I also like Vapnik's _The Nature of Statistical Learning Theory_ which as I understand it is highly parallel to a much longer proof-heavy version of most of the same material. I much preferred this book to the approach in my undergraduate course in statistics. Again, the difference wasn't only lack of explanations (also, e.g., not enough enough grounding in proof or plausibly provable propositions, and too narrowly based in a frequentist worldview assumed without any explicit justification), but the lack of explanatory framework sure didn't help, so later I welcomed Vapnik's explanations of his approach. I have never been motivated to read the proof-heavy parallel book by Vapnik, but I do find it reassuring that it exists in case I ever work with problems that were weird enough to start raising red flags about breaking the comfortable assumptions in my informal understanding of the statistics.

   Show morethread
3. lliiffeeFeb 2009
   If you happen to be much better at math than programming, starting with the theory could be much easier. This survey is the best introduction I have found. The alternative being to read Vapnik's "The Nature of Statistical Learning Theory", which is more longer and much more "Russian".

   Andrew Ng's notes are an excellent (non-theory) introduction to general machine learning.

   http://www.stanford.edu/class/cs229/materials.html

   Show morethread
4. DavidSJMay 2022
   With over-parameterized neural networks, the problem essentially becomes convex and even linear [1], and in many contexts provably converges to a global minimum [2], [3].

   The question then becomes: why does this generalize [4], given that the classical theory of Vapnik and others [5] becomes vacuous, no longer guaranteeing lack of over-fitting?

   This is less well understood, although there is recent theoretical work here too.

   [1] Lee et al (2019). Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent. https://proceedings.neurips.cc/paper/2019/hash/0d1a9651497a3...

   [2] Allen-Zhu et al (2019). A convergence theory for deep learning via over-parameterization. https://proceedings.mlr.press/v97/allen-zhu19a.html

   [3] Du et al (2019). Gradient Descent Finds Global Minima of Deep Neural Networks. http://proceedings.mlr.press/v97/du19c.html

   [4] Zhang et al (2016). Understanding deep learning requires rethinking generalization.

   [5] Vapnik (1999). The nature of statistical learning theory. https://arxiv.org/abs/1611.03530

   Show morethread
5. graycatApr 2017
   That rock you mention is where I work on my startup -- with money in mind.

   My main reason to do applied math is to apply it, to business, the money making kind.

   Yes you have told me about Vapnik before, but the rest I see, e.g., deep learning, smells like tweaks on Breiman's CART. I have a lot of respect for Breiman, maybe more for his fellow student Neveu as they were at Berkeley under Loeve.

   I have a tough time taking Silicon Valley seriously on anything serious about machine learning -- new words for statistical model building and estimation but done with much more data.

   In

   Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning Data: Mining, Inference, and Prediction, Second Edition, Springer, 2008.

   I find mention of Vapnik, mostly for separating hyperplanes, and references

   Vapnik, V. (1996). The Nature of Statistical Learning Theory, Springer, New York.

   Vapnik, V. (1998). Statistical Learning Theory, Wiley, New York.

   Looking at Hastie, et al., which seems relatively elementary, I wouldn't expect to find much on the Kuhn-Tucker conditions or Glivenko Cantelli.

   In

   Kevin P. Murphy, Machine Learning: A Probabilistic Perspective, ISBN 978-0-262-01802-9, MIT Press, 2012.

   I saw no mention of Vapnik.

   In

   Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning From Theory to Algorithms, 2014.

   I see

   Vapnik, V. (1992), Principles of risk minimization for learning theory, in J. E. Moody, S. J. Hanson & R. P. Lippmann, eds, `Advances in Neural Information Processing Systems 4', Morgan Kaufmann, pp. 831{838.

   Vapnik, V. (1995), The Nature of Statistical Learning Theory, Springer.

   Vapnik, V. N. (1982), Estimation of Dependences Based on Empirical Data, Springer- Verlag.

   Vapnik, V. N. (1998), Statistical Learning Theory, Wiley.

   Vapnik, V. N. & Chervonenkis, A. Y. (1971), `On the uniform convergence of relative frequencies of events to their probabilities', Theory of Probability and its applications XVI(2), 264{280.

   Vapnik, V. N. & Chervonenkis, A. Y. (1974), Theory of pattern recognition, Nauka, Moscow. (In Russian).

   Okay, that may be a first-cut list of what to read on Vapnik.

   Gee, machine learning and not from Silicon Valley -- the second part is a step up! Not from Pittsburgh either -- two steps up!

   Probabilistic and from Russia? More steps up!

   For more steps up, maybe some French or Japanese could contribute?

   For such things, I could take Bertsekas at MIT seriously.

   I'm deep into my startup; there I've done my applied math derivations and written the code.

   It is true that I have some suspicions that some old techniques tweaked a little and maybe some newer techniques might increase accuracy some, but I'm leaving that on the back burner for now, avoiding premature optimization.

   But I'll index this post and not forget about Vapnik.

   Show morethread
6. mrdrozdovNov 2015
   Thanks for the heads up.

   I found 38k citations for The Nature of Statistical Learning Theory: https://scholar.google.com/scholar?cluster=86085598803682809...

   And 25k for Statistical Learning Theory: https://scholar.google.com/scholar?cluster=86748554971781655...

   My initial estimation of 10k was from a CiteSeer list that I didn't realize was limited to only documents in the CiteSeer database: http://citeseer.ist.psu.edu/stats/articles

   Show morethread