TCS-TR-A-08-34

Date: Wed Jan 16 04:27:08 2008

Title: On the Limits of Learning with Computational Models

Authors: Shane Legg, Jan Poland, and Thomas Zeugmann

Contact:

First name: Thomas
Last name: Zeugmann
Address: Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan
Email: thomas@ist.hokudai.ac.jp

Abstract. This paper provides a short discussion concerning the state of the art in Bayesian learning theory with an emphasis on performance guarantees. In the second part of the paper, we outline some negative results indicating that there is no hope for a general learning algorithm that is computable and implementable, but powerful enough to learn any computable data.