2
$\begingroup$

I come from a pure math background and am not very familiar with machine learning. So, I'll start with an example to compensate for my confused grasp of the terminology.

Let's say we have a function $f:X \to Y$, and we want to develop a neural network to compute this function. For instance, $X$ could be $\{0, 1, ... 255\}^N$ for some large $N$, and $Y$ could be $\{0, 1\}$, if we wanted to build a network that performs a binary classification on images of $N$ pixels. We have some algorithm which adjusts, maybe stochastically or maybe deterministically, the weights and parameters of our network, creating a sequence of networks which should converge to $f$.

What theorems exist to guarantee that we do indeed converge to $f$, or even that a network exists to represent $f$? If we don't want to make assumptions about $f$, we would need some theorem establishing that given any function $f$, and any initial network, the sequence of networks generated by the learning algorithm will converge to $f$.

I'm not just interested in neural nets, though. Are there textbooks on machine learning which cover this sort of thing in depth? What keywords should I be looking out for?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 1. Computational learning theory and machine learning (practice) have a very small intersection. There are very few if any results of the type you describe about neutral networks. 2. For computational learning theory have a look at Kearns and Vazirani's book. 3. For machine learning pick a standard textbook, e.g. Bishop's or Murphy's. $\endgroup$
    – Kaveh
    Jun 12, 2016 at 18:42
  • $\begingroup$ @Kaveh Well, I know for neural nets there is at least this theorem. $\endgroup$
    – Jack M
    Jun 12, 2016 at 19:02
  • $\begingroup$ See Aryeh's answer below. There are three strands: 1. Computational learning theory which is part of theoretical computer science. It is mathematically rigorous and cares about computational complexity of learning algorithms but the results are for general distributions and almost everything interesting in practice is shown to be hard to learn under general distributions. 2. Statistics which typically ignores the computation complexity aspects of learning algorithms. $\endgroup$
    – Kaveh
    Jun 12, 2016 at 19:16
  • $\begingroup$ 3. Machine learning which cares only about distributions in practice which are hard to model rigorously. They seldom have mathematical theorems showing efficiency of algorithms or convergence because their algorithms often only work on those specific practical distributions which are hard to model mathematically and prove theorems about. Algorithms are typically compared based on how they well perform on benchmarks, e.g. a new break through algorithm might perform 5% better than the best previous algorithms but no rigorous theorem is given why it performs better. $\endgroup$
    – Kaveh
    Jun 12, 2016 at 19:19

2 Answers 2

Reset to default
4
$\begingroup$

I recommend Neural Network Learning: Theoretical Foundations by Anthony and Bartlett. You'll find exhaustive answers to your questions there. Very briefly, theoretical learning problems tend to separate very cleanly into two orthogonal components: statistical and computational. Thus, a universal learner unconstrained by computational issues could construct the smallest Turing machine (or MATLAB program) consistent with the input data; such a learner would be near-optimal statistically in a well-defined sense.

Nobody studies such learners (beyond intro-class homework problems) because they are computationally infeasible (actually uncomputable, in my example). When computational constraints enter the picture, it becomes much more nuanced: often times, what is the obvious course of action for the statistician is dismissed out of hand as infeasible by the algorithmist.

In any case, the Anthony+Bartlett book seems like the perfect introduction for a mathematically inclined beginner.

Improve this answer
$\endgroup$
5
  • $\begingroup$ AFAIU, statisticians do study the statistical perspective. By "nobody" I guess you mean "no computer scientist". $\endgroup$
    – Kaveh
    Jun 12, 2016 at 19:28
  • $\begingroup$ I think modern statisticians are very much aware of computational issues. $\endgroup$
    – Aryeh
    Jun 12, 2016 at 19:42
  • $\begingroup$ I am not saying they are not :) I am not an expert on this but don't statisticians still study these problems without the computational complexity restrictions? That is at least my impression based on discussions I have had with ML people at our department. $\endgroup$
    – Kaveh
    Jun 12, 2016 at 19:45
  • $\begingroup$ I'm also not an expert but I think it would be difficult to get a paper into, say, Ann. Stat., that was using an infeasible learning method. What's more reasonable is the use of oracles: call a black box to minimize some reasonable sample-dependent function. But JMLR publishes such papers also. $\endgroup$
    – Aryeh
    Jun 12, 2016 at 20:00
  • $\begingroup$ Anthony and Bartlett seems like exactly the kind of book I was looking for. $\endgroup$
    – Jack M
    Jun 13, 2016 at 9:09
2
$\begingroup$

I can also recommend Computational Learning Theory by Kearns and Vazirani.

The book is general, not assuming any specific underlying structure to the learning algorithm like a neural net, instead it considers more generally algorithms for approximating functions based on sample training data.

The book seems very theoretical and rigorous, with proofs of NP-hardness and such results, Vapnik-Chervonenkis dimension, and a cute chapter on a theorem they call a formalized version of Occam's razor, which states (very) roughly that if a data sample is drawn from a probability distribution P, then the simplest (in a Kolmogorov-y sense) function consistent with that sample will have the best predictive power for future data drawn according to P.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.