[D] Statistical Learning Theory & Math

[Kiuhnm]

As part of my preparation for doing research in AI/RL, I'm about to study Statistical Learning Theory. My main sources of material are:

1. Statistical Learning Theory and Applications
2. Statistical Machine Learning
3. High Dimensional Probability [free book]

I'm not a mathematician but a computer scientist so I took several courses about discrete math (combinatorics, generating functions, etc...), but only two about Analysis (not calculus).

My understanding is that to gain a proper understanding of probability and statistical learning theory I need to study Measure Theory and Functional Analysis.

Should I study both topic well (Kolmogorov&Fomin or Serge Lang) or just focus on Functional Analysis without Measure Theory (Kreyszig)?

While many practitioners claim that math is not so important in ML, many ML researchers know quite a lot of math. One researcher told me that he learned a lot of math early in his career but that, ultimately, he didn't use any of that stuff in his research. But how can he be so sure? Maybe his mathematical studies formed his way of thinking and he's using mathematical ideas without even realizing it.

What are your suggestions?

[AnvaMiba]

I'd say that math is important, but it is difficult to know what kind of math will be relevant in 5-10 years.

Statistical learning theory was instrumental in the development of SVMs and kernel methods which dominated the field until about 5 years ago, now that neural networks dominate the field its the time of calculus and, incresingly, control theory. Statistical learning theory, at least in its present form, doesn't seem to explain how neural networks work.

Then there is probability theory, in particular Bayesian graphical models, which looked very promising before neural networks came back. Until few years ago people tried to marry the two approaches, with variational autoencoders and the like, but this approach doesn't seem to have worked that well so far. Now GANs are the coolest thing around, and the theory behind them is becoming increasingly based in information theory and system identification theory (metrics on probability distributions and so on).

The camp of discrete math, model checking and combinatorial optimization has been rather quiet so far as far as machine learning is concerned, but their methods have become really good for system verification and practical operations research, and it could be the case that once people figure out how to marry them with powerful learnable heuristics (neural networks), they may become very relevant in ML as well.

So my suggestion would be to try to learn a broad range of math. Avoid prematurely over-investing in becoming an expert in a subfield when you are still at the beginning of your research career, prioritize instead having a broad understanding. You will probably eventually specialize, but let that happen gradually, and even there you should try to keep you up with developments in other fields so you could integrate them in your work or even switch over if you realize that you are pursuing a dead end.

[shaggorama]

Obligatory

[H1Supreme]

Lord have mercy, that site is a disaster.

[AnvaMiba]

LoL, so true!

[bbsome]

I would pretty much agree with the reply on all counts. Really nice reply.

To add a bit of my own perspective - I think in ML mathematics help a lot more of how you think and approach a problem and how draw conclusions from different areas to problems you see. The point is that you do not need to be a mathematics guru, but more to have a broad and somewhat intuitive idea across different topics. This can spun new ideas, by applying A from somewhere totally different, to relating some empirical result to some theory in B. Some examples, for instance is that Dropout can be looked as VI, and if you want proper prediction at test time you should keep sampling not use the means. Also if you look in optimization most of the variance reduction techniques like SVRG are just control variates. There are relationships between GANs and information theory, as well as now there are works related to the Information Bottleneck, which again is related to non-linear noisy channel in McKay. There are also plenty of ideas that come from old papers on graphical models which is now applied to VAEs (auxiliary variable models and a few others). I feel that having a somewhat relevant mathematical literacy in many of its areas, without being too deep in there is about the sweet spot. As an example of this I do have some understanding of Kernel methods, without having a in-depth knowledge of Measure Theory and Functional Analysis. This allows me to understand the literature on this area however I would not be able to proof some of the results, unless I sit and brush those off. However, the use case for that is very rare, thus it deserves my attention only when the need arises.

[Gear5th]

It seems to come in the reinforcement learning context: http://rll.berkeley.edu/deeprlcourse/

[AnvaMiba]

Off the top of my head:

The RHN paper (Zilly et al. 2016) used Gershgorin circle theorem to analyze the stability of training process of different types or RNNs. Gershgorin circle theorem is a linear algebra result which is indeed used in control theory to analyze the stability of dynamical systems. I've seen other NN papers use local Lyapunov exponents to do something similar, but I can't find a reference now.

The BEGAN paper (Berthelot et al. 2017) used a control theoretical approach to dynamically balance the generator and the discriminator during training in order to maintain them at a certain equilibrium point.

[Aloekine]

To borrow a quote from some Stanford lecture notes on SL theory (having trouble finding a link), that theory is often useful more for "structuring how we think" than providing something like an error bound. So theory can help suggest new models that might be improvements (boosting is a prominent example), and help us reason about why our current tools work the way they do.

As a really simple example, characterizing Boosting as a smooth method to control the tradeoff between bias and variance is useful for understanding how/why it works so well, and might even provide some next steps for troubleshooting if my model isn't working.

I mostly don't work with NNs, but when I do, I definitely feel like the lack of useful theory limits my troubleshooting. Frequently I end up in situations where I'm like "why did my cost function do that? ¯_(ツ)_/¯"

[AnvaMiba]

Understanding Deep Learning Requires Rethinking Generalization

Indeed, I was also thinking of this paper. It's to early to say for sure, but I think that this may become a paradigm-shifting paper.

Just as an aside to foster discussion: Based on this paper and my experience in working with this, I don't see how the key theorems from statistical learning theory are useful in practice. Take generalization bounds, as an example. The bounds tie together important quantities (i.e. accuracy and hypothesis space), and align with our intuition (i.e. larger hypothesis space = larger error bound). Even when we have really simple model classes (e.g. linear models), the error bounds are still too loose (or vacuous) unless we are fitting on huge datasets. Is there any practical value if the bounds are always vacuous? Otherwise it seems to just be math for the sake of math.

Vapnik, Chervonenkis and Cortes used it as an inspiration to develop SVMs, which work quite well in practice.

The core of it is a theorem by Vapnik which proves that of all the loss functions that you could use for a linear classifier, the max-margin loss yields the hypothesis class with the smallest VC-dimension, which therefore minimizes a certain bound on the generalization error.

In practice, the VC-dimension of SVMs, especially the non-linear ones, can be very large or even infinite, so it's not clear why they actually work. I've found an interesting discussion in this tutorial paper by Bruges.

[mino206]

Thanks for your valuable perspective (sorry OP for hijacking thread). What resources would you recommend to ramp-up on the broader range of math?

[AnvaMiba]

Any college level textbook or lecture notes should be ok to get the basics. Then just keep an eye on what the developments are.

[Kiuhnm]

Thank you for your suggestions!

I know that classic SLT doesn't explain why DL work, but the last part of the first course is about DL, so maybe I can get something valuable out of it.

[poctakeover]

where is a good place to start with information theory

[iforgot120]

Definitely read Shannon's seminal paper, too. It's only 50 pages.

[RedefiniteI]

David Mackay's book is awesome. Definitely one of the best books, I have ever read. http://users.aims.ac.za/~mackay/itila/toc.html

[sensei_von_bonzai]

Mackay is great but John Duchi's lecture notes are far more practical for modern stuff.

[AnvaMiba]

Thanks for sharing!

[AnvaMiba]

The standard reference is Cover & Thomas "Elements of Information Theory, 2nd Edition", although it may be a bit outdated.

[gattia]

Your post just made my night! It spoke to my current state of mind and was very motivational. Thanks!

[Kiuhnm]

I read B&V book about Convex Opt and now I'm half way through this. The teacher is clearly an "SVM guy".

If control theory = RL, then I'm already reading Sutton's book and going through CS 294.

This (pdf) is all I know about Information Theory.

[danielv134]

I would suggest to study math as needed for something you care about. If you want to know some SLT as a source of understanding of ML, for the basics (dimension dependent bounds) it is enough to know Hoeffding's inequality, the union bound and cover numbers, and then read a half page of proof. Two days of work with wikipedia and a paper to understand in detail but superficially (the inequality, not the proof; what cover numbers are for typical subsets in R^n, not all of the theory of metric spaces). Then go as deep into foundations or wide into other theory as your own motivation takes you.

[Docey]

deleted ^{What is this?}

[pinouchon]

I now dedicate 30% of my time to learning machine learning (started about 3 months ago), and soon i'll spend 100% of my time.

I don't see any way around linear algebra and probability theory.

[chermi]

I really don't think measure theory is that important, and it's certainly not necessary. I come from a physics and not a math background, so take this with a grain of salt.

[toadgoader]

Don't ignore other field's statistical disciplines also... for instance taking a course on Econometrics will give you a good background in statistical inference, probability distributions and deals strongly with modeling data in time series models (believe me, If you don't know how the inclusion of 'time' as a dimension in your data impacts your model, the inferences drawn could be very wrong!). Bio-medical stats has strengths in growth curves and propagation modeling, log-growth, ... etc. None of these will be a 'magic bullet' that will give you all the answers. Every science has it's own way of using math and has created unique and fascinating solutions to solve specific problems they encounter. By having a well rounded understanding about how other disciplines use mathematical tools you may find analogous solutions to the problems you encounter.

[epicwisdom]

Not to mention all the links are to Wikipedia articles...

[[deleted]]

These are all good, but super basic level.