CISC 805: Theory of Machine Learning

Catalog Description:
Mathematically circumscribes the absolute boundaries of what algorithms can do about learning grammars for languages and programs for functions. Proves results in the recursion-theoretic theory of machine learning. Provides interpretations of results regarding human language learning and philosophy of science.

Goals:
The student should learn the principal results and proof techniques in recursion-theoretic learning theory.

Contents:
It is possible to circumscribe mathematically the absolute boundaries of what discrete computing machines can do by way of learning grammars for languages and programs for functions. Background mathematical tools from recursive function theory are provided. Important results in the recursion-theoretic theory of machine learning are presented and proven. Interpretations of some of these results regarding human language learning and philosophy of science and indications of directions for future work are also given.

Reference:
D. Osherson, M. Stob, and S. Weinstein, Systems That Learn: An Introduction to Learning Theory for Cognitive and Computer Scientists, MIT Press, Cambridge, MA, 1986.

Helpful Knowledge:
Either CISC 601 or at least one course in which the student was required to prove theorems and familiarity with at least one general model of computation, for example, the Turing machine model.