Computational Learning Theory at NUS

Computational Learning Theory concerns the mathematical analysis of algorithms that either adapt to their environments, or try to model parts of them. The work of our group at NUS ranges from study of detailed theoretical models of concrete applied problems to study of basic questions about more abstract problems.

The members of the group are Sanjay Jain, Lee Wee Sun and Frank Stephan.

 Research Topics

• Complexity of Approximate Planning.
  Planning for partially observable Markov decision processes (POMDP) is known to be intractable in the worst case. In this project, we study subclasses of POMDP planning problems and factors that make some of them easier to solve.
• Learning and hypothesis spaces.
  This area deals with the interplay of learnability and expressiveness of the hypothesis space used by the learner. Building on previous results of Angluin, Lange and Zeugmann, it is investigated how the learnability depends on the question whether the hypothesis space is chosen by the learner itself or prescribed by another authority and what requirements of regularity are requested from the hypothesis space. Another question studied is how important padding is in iterative learning and what happens if padding is almost ruled out by imposing a one-one class-preserving hypothesis space.
• Learning from Negative Counterexamples.
  We study a model of learning where the learner in addition to getting positive data is also told about negative counterexamples to its conjectures. Among several results, we show the surprising result that the class of all recursively enumerable sets is learnable in Bc¹ model of learning, when negative counterexamples are available.
  We also considered the effect of negative counterexamples in iterative learning, and it shows surprising contrasts to results when normal non-iterative learning is considered; for example, negative counterexamples help more than informant for iterative learning.
• Non U-Shaped Learning.
  This project is motivated from the observation that humans and animals tend to forget and relearn skills and behaviours in their life. So the question is whether such a behaviour would increase the ability to learn in general or whether it is only a sign of imperfectness of the real world. The question was rephrased in the mathematical well-defined setting of inductive inference and there it was investigated for the two learning criteria of behavioural correct and explanatory learning whether the additional constraints of decisiveness and non U-shapedness are restrictive. Here a learner is decisive iff it never returns (semantically) to an abandoned hypothesis; it is non U-shaped iff it never abandons a correct one and hence never has the need to return to an abandoned correct hypothesis. It turned out that decisiveness is restrictive for all major learning criteria while non U-shapedness is only restrictive for behaviourally correct learning. Many related questions are studied.
• Applications of Kolmogorov Complexity.
  Kolmogorov complexity is a field where the complexity of strings or numbers is measured in terms of the shortest computer program to generate this number. It is studied how to apply this theory to the fields of recursion theory, model theory and learning theory. For example the minimum description lengths principle in many learning algorithms comes directly from the research in this field. Furthermore, Kolmogorov complexity was used by Khoussainov, Semukhin and Stephan to solve some problem open since 25 years in the field of recursive model theory.

Publications

Some recent publications related to above research topics are:

• Learning Languages from Positive Data and a Limited Number of Short Counterexamples. Sanjay Jain and Efim Kinber. In Theoretical Computer Science, 2007.
• Some Natural Conditions on Incremental Learning. Sanjay Jain, Steffen Lange and Sandra Zilles. In Information and Computation, 2007.
• What Makes Some POMDP Problems Easy to Approximate? David Hsu, Wee Sun Lee and Nan Rong. In Neural Information Processing Systems, 2007.
• Results on memory-limited U-shaped learning. Lorenzo Carlucci, John Case, Sanjay Jain and Frank Stephan.  In Information and Computation, 2007.
• Applications of Kolmogorov Complexity to Computable Model Theory. Bakhadyr Khoussainov, Pavel Semukhin and Frank Stephan.  In The Journal of Symbolic Logic, 2007.

More publications can be found in the group members' home pages.

Mail comments about this page