6
$\begingroup$

I have an applied machine-learning and statistics background, and when I read the Universal approximation theorem, which (in the context of the learning theory of ANNs - Artificial Neural Networks) states (Wikipedia):

"the standard multilayer feed-forward network with a single hidden layer that contains finite number of hidden neurons, and with arbitrary activation function are universal approximators on a compact subset of $R^n$. "

I wondered if there are any similar results (in terms of approximation power) for other types of learners (e.g. decision trees, boosting methods, SVMs, etc.).

This leads me to a second but related question: Is this a topic that is formally studied in TCS? If so, are there any good texts for somebody with an applied background?

Thanks

$\endgroup$
  • $\begingroup$ Did mean for "ANN" to stand for "Acyclic Neural Network" or something? From my understanding, "ANN" often stands for "Approximate Nearest Neighbor," so this title might be confusing. $\endgroup$ – Lev Reyzin Jan 30 '11 at 23:59
  • $\begingroup$ @Lev: I think it stands for Artificial Neural Network. $\endgroup$ – M.S. Dousti Jan 31 '11 at 0:42
  • 1
    $\begingroup$ oh I see - that abbreviates to ANN too. Shows how much I know... $\endgroup$ – Lev Reyzin Jan 31 '11 at 0:58
4
$\begingroup$

Let me attempt to partly answer the learning part, or to at least address some connections. In learning (distributional issues aside), we usually want our algorithms to be able to not only approximate the target function (from a class) with a hypothesis, but also to be able find such a hypothesis (efficiently). So, even though a certain class can universally approximate a given target, we are not done.

I am not an expert in neural networks, but training a neural network is not easy. We have algorithms for training a neural network, like backpropogation, but they won't always converge, or converge quickly enough, to meet the PAC learning criteria. Boosting, on the other hand says (roughly) how to turn a weak "approximator" into a strong one, but it in some sense assumes the difficulty away but giving the learner access to the weak approximator.

$\endgroup$
  • $\begingroup$ Thanks @Lev! This is very helpful. I'll look into PAC more carefully. Are there any other mathematical frameworks besides PAC that are used to study the tractability and approximation power of learners? Is PAC the de-facto learning theory? $\endgroup$ – Amelio Vazquez-Reina Jan 31 '11 at 0:21
  • 1
    $\begingroup$ In some sense approximation doesn't fit so well into the PAC model because of ideas like boosting. Once you can do (bounded) better than half, you can do arbitrarily well. So when people talk about approximation in learning, they talk about approximating other types of things -- like the size of the best consistent hypothesis. But, yes, when people say "learnable" they usually mean "PAC learnable." There are, of course, many other models of learning: learning with membership and equivalence, online learning, reinforcement learning, active learning & more. Each has its own conditions, etc. $\endgroup$ – Lev Reyzin Jan 31 '11 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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