John Case's COLT Page
John Case's COLT Page (to be updated soon)
N.B. This page has not been updated for too long.
Click
HERE for my NSF Nugget on UShaped Learning. Versions of
corresponding papers (as well as other papers) coming soon.
ALSO,
HERE is a link to a complete, uptodate (as of March 2009)
list of my publications, including those on COLT.
Consider the problem of finding
a rule for generating a sequence of numbers such as
9, 61, 52, 63, 94, 46, 18, 1, 121, 441, ... .
Here is a rule for this sequence.
First compute the squares of successive integers
beginning with 3, but, then, to generate the sequence,
use, in place of these squares, the
squares each with its decimal
digits written down in reverse order (ignoring any lead zeros).
N.B. This rule can be written as a formal algorithm
(or computer program).
The problem of finding such rules
gets harder as the sequences to generate get more complicated
than the one above. Can the rule finding itself be done by some computer
program? Interestingly, it is mathematically proven that
there can be no computer program which can eventually
find (synonym: learn) these (algorithmic)
rules for all sequences which have such rules!
Here is a different problem. Given pictures of animals
each (correctly) labeled as being or not being a picture of a bird, eventually
find/learn
an (algorithmic) rule for deciding, of each of those (past, present, and
future) pictures, whether or
not it depicts a bird. People seemingly solve this
problem in childhood as well as many
other problems of learning (subconscious) rules
to predict membership in concepts (such as
the concept of bird). Many cognitive scientists
seek to model all of
cognition (including concept learning) by computer program.
It is, then,
an interesting, very
hard problem to write a computer program which can
learn (algorithmic) rules
to predict membership in all the concepts that people can .
It's so hard we don't know how to do it yet, and we don't know how to
to prove it can't be done.
Computational Learning Theory (COLT) is
a branch of
theoretical
computer science which mathematically studies the power of computer
programs to learn (algorithmic) rules for predicting things such as
membership in a concept or, as in the first example above, rules for
how to generate a sequence.
Besides the intrinsic scientific and philosophical interest,
the expected primary applications of COLT are to construction of
intelligent technology, especially technology which learns, and to cognitive
psychology, including understanding
human language acquisition (brief postscript bibliography available)
and
scientific inductive inference (brief postscript bibliography available).
COLT seeks to provide a conceptual, mathematical
infrastructure for these applied and basic areas.
I am especially interested in learning
models which can be explored with tools from mathematical
logic
such as
recursive function theory and
arguments and have contributed in
this area for a number of years and through a number of
Ph.D. students
and
other coworkers. Some of their home pages can be accessed by clicking on
their names below. For links to some
COLT and Machine Learning researchers, research groups, etc.,
click just below.
For the SLIDES (condensed onto one page of postscript)
of my guest lecture on COLT in the introductory undergraduate
UD Cognitive Science course
CGSC270,
Click Here.
The empirical machine learning work of
C. Sammut with others
on teaching an autopilot to fly a flight simulator
and the seminal theory paper on learning processcontrol,
M. Kummer and
M. Ott,
``Learning Branches and Closed Recursive Games,''
Proceedings of the
Ninth Annual Conference in Computational Learning Theory,
Desenzano del Garda, Italy,
June, 1996,
each partly inspired our theory paper on learning processcontrol cited
below.
In turn
I am also interested in using theorems in Computational Learning Theory to
suggest feasible approaches for applied Machine Learning problems
(including processcontrol problems).
Re Machine Learning, see also
the two papers below on Concept Drift and Learning from Context.
For my other work on feasible computation and program size see:
and, more generally:
I am also interested in characterizations of computational learning theoretic
scenarios with an eye to
providing useful insights and aiding machine learning practice. For example,
I'm interested in characterizations regarding hypothesis spaces employed (click
here
for a paper reference
below dealing with characterizations regarding the control structures
employed in hypothesis spaces  click
here
for more on control structures in general). Referenced below are also
papers featuring characterizations of langauge learning in both
noisefree data
cases, in
noisy data
cases, and in
computable noisy data
cases.
I've recently been working directly on empirical machine learning problems
(applied to
bioinformatics).
REPRESENTATIVE PUBLICATIONS:

Machine Inductive Inference
and Language Identification (with C. Lynes),
Automata, Languages and Programming, 9th Colloquium,
Aarhus, Denmark, July 1982, in volume 140 of
Lecture Notes in Computer Science,
SpringerVerlag, Berlin, 1982.

Comparison of Identification Criteria for Machine Inductive
Inference (with C. Smith),
Theoretical Computer
Science, 25 (1983), 193220.

Learning Machines, Language Learning and Concept Acquisition
(edited by W. Demopoulos and
A. Marras), Ablex Publishing Co., 1986.

Strong Separation of Learning Classes
(with K. Chen and
S. Jain),
Journal of Experimental and Theoretical Artificial Intelligence,
4 (1992), 281293.

On Learning Limiting Programs
(with
S. Jain
and
A. Sharma),
International Journal of Foundations of Computer Science, 3
(1992), 93115.

Refinements of Inductive Inference by Popperian and
Reliable Machines
(with
S. Jain
and S. Ngo Manguelle),
Kybernetika, 330
(1994), 2352.

Infinitary Self Reference in Learning Theory,
Journal of Experimental and
Theoretical Artificial
Intelligence, 6 (1994), 316.

Learning with Higher Order Additional Information
(with
G. Baliga),
in K. Jantke and S. Arikawa, editors,
Algorithmic Learning Theory,
Reinhardsbrunn Castle, Germany, pages 6475 in volume 872 of
Lecture
Notes in Artificial Intelligence, Springer Verlag, Berlin, 1994.

Vacillatory Learning of Nearly Minimal Size Grammars
(with
S. Jain
and
A. Sharma),
Journal of Computer and System Sciences, 49 (1994),
189207.

Machine Learning of Higher Order Programs
(with
G. Baliga,
S. Jain and M. Suraj),
Journal of Symbolic Logic, 59 (1994), 486500.

Complexity Issues for Vacillatory Function Identification
(with
S. Jain
and
A. Sharma),
Information and
Computation, 116 (1995), 174192.

Language Learning With Some Negative Information
(with
G. Baliga
and
S. Jain),
Journal of Computer and Systems Science, 51,
(1995), 273285.

Anomalous Learning Helps Succinctness
(with
S. Jain
and
A. Sharma),
Theoretical Computer
Science, 164 (1996), 1328.

NotSoNearlyMinimalSize Program Inference
(with
S. Jain
and M. Suraj),
in K. Jantke and S. Lange, editors,
Algorithmic Learning for KnowledgeBased Systems,
pages 7796, in volume 961 of Lecture
Notes in Artificial Intelligence, Springer Verlag, Berlin, 1995.
Click for expanded, corrected journal submission version with new title.

Machine Induction Without Revolutionary Changes in Hypothesis Size
(with
S. Jain
and
A. Sharma), Information and Computation, 128 (1996), 7386.

Learnability: Admissible, CoFinite and Hypersimple Sets
(with
G. Baliga),
Journal of Computer and Systems Science, 53
(1996), 2632.

Learning Recursive Functions From Approximations
(with
S. Kaufmann,
E. Kinber, and
M. Kummer),
Journal of Computer and Systems Science,
Special Issue for EuroCOLT'95, 55 (1997), 183196.

Vacillatory and BC Learning on Noisy Data
(with
S. Jain and
F. Stephan),
Theoretical Computer
Science, Special Issue for ALT'96, accepted 1997.

The Synthesis of Language Learners
(with
G. Baliga and
S. Jain), Information and Computation, 152 (1999), 1643
(and mentioned
above).

On the Classification of Computable Languages
(with
E. Kinber,
A. Sharma, and
F. Stephan), Proceedings of the
Fourteenth
Symposium on Theoretical Aspects of Computer Science (STACS'97),
Hansestadt Lübeck, Germany, February 27  March 1, 1997.

Control Structures in Hypothesis Spaces:
The Influence on Learning
(with
S. Jain, and
M. Suraj),
expansion of the version in
Proceedings of the
Third European Conference on Computational
Learning Theory (EuroCOLT'97), Jerusalem, Israel, March 1719, 1997
(and mentioned
above; journal version accepted by
Theoretical Computer Science, 2000).

Incremental Concept Learning for Bounded Data Mining
(with S. Jain,
S. Lange,
and T. Zeugmann),
Information and Computation, 152 (1999), 74110.

Synthesizing NoiseTolerant Language Learners
(with
S. Jain and
A. Sharma),
in M. Li and A. Maruoka, editors,
Proceedings of the
Eighth International Workshop on Algorithmic Learning Theory,
Sendai, Japan, pages 228243 in volume 1316 of
Lecture
Notes in Artificial Intelligence, Springer Verlag, Berlin, 1997
(and mentioned
above; journal version to appear, Theoretical Computer
Science (Special Issue for ALT'97), 1998).

Learning To Win ProcessControl Games Watching GameMasters
(with
M. Ott,
A. Sharma, and
F. Stephan),
Proceedings of the
Ninth International Workshop on Algorithmic Learning Theory,
Otzenhausen, Germany, 1998
(and mentioned
above;
journal version to appear, Information and Computation).

Predictive Learning Models for Concept Drift
(with
S. Jain,
S. Kaufmann,
A. Sharma, and
F. Stephan),
Proceedings of the
Ninth International Workshop on Algorithmic Learning Theory,
Otzenhausen, Germany, 1998
(journal version accepted 1999 for the associated Special Issue of
Theoretical Computer Science and mentioned
above).

Robust Learning Aided by Context
(with
S. Jain,
M. Ott,
A. Sharma, and
F. Stephan),
Journal of Computer and System Sciences, Special Issue for COLT'98,
152 (2000), 234257 (and mentioned
above).

Synthesizing Learners Tolerating Computable Noisy Data
(with
S. Jain),
Proceedings of the
Ninth International Workshop on Algorithmic Learning Theory,
Otzenhausen, Germany, 1998
(and mentioned
above; journal version to appear, Journal of Computer and System
Sciences).

Costs of General Purpose Learning
(with K. Chen and
S. Jain),
Proceedings of the Sixteenth
Symposium on Theoretical Aspects of Computer Science (STACS'99),
Trier, Germany, pages 424433 in volume 1563,
Lecture Notes in Computer Science, Springer, Berlin, 1999
(journal version to appear, Theoretical Computer
Science).

Maximal Machine Learnable Classes
(with M. Fulk),
Journal of Computer and System Sciences, 58 (1999), 211214.

The Power of Vacillation in Language Learning,
SIAM Journal on Computing, 28 (1999), 19411969.

Inductive Inference of
 vs.
Definitions
for Computable Functions
(with M. Suraj),
abstract in
Proceedings of the International Conference on Mathematical Logic,
held in Novosibirsk, Russia, August 1015, 1999. Click
here for the slides.

When Unlearning Helps
(with
G. Baliga,
W. Merkle, and
F. Stephan), expansion of a similarly entitled paper in
Proceedings of the 27th International Colloquium on Automata,
Languages and Programming (ICALP'00), Geneva, Switzerland,
pages 844855 in volume 1853,
Lecture Notes in Computer Science, Springer, Berlin, 2000.

Robust Learning  Rich and Poor
(with
S. Jain,
F. Stephan, and
R. Wiehagen),
Proceedings of the Fourteenth Annual Conference on Computational Learning
Theory (COLT'01) and The Fifth European Conference on Computational Learning
Theory (EuroCOLT'01),
to be held in Amsterdam, The Netherlands, July, 2001, to
appear, 2001.

On Learning To Coordinate:
Random Bits Help, Insightful Normal Forms, and
Competency Isomorphisms
(with
S. Jain, Franco Montagna,
Giulia Simi, and
A. Sorbi), conference submission 2003.

Generality's Price:
Inescapable Deficiencies in MachineLearned Programs
(with
KJ. Chen,
S. Jain,
W. Merkle), and
J. Royer),
conference submission 2003.
March 29, 2013
John Case