7
$\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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
5
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jan 31, 2011 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 ♦
    Commented Jan 31, 2011 at 1:02
1
$\begingroup$

A decision tree is a simple function essentially. According to the simple function approximation lemma, decision tree is universal approximator. See http://mathonline.wikidot.com/the-simple-function-approximation-theorem for more details on simple function approximation lemma.

Improve this answer
$\endgroup$

Your Answer

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

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