Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!mcgill-vision!bloom-beacon!snorkelwacker!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!haven!udel!rochester!fulk
From: fulk@cs.rochester.edu (Mark Fulk)
Newsgroups: comp.ai.neural-nets
Subject: Re: Computational Learning (intro needed)
Keywords: Reference for Book
Message-ID: <1990Feb9.025932.26006@cs.rochester.edu>
Date: 9 Feb 90 02:59:32 GMT
References: <689@h.cs.wvu.wvnet.edu> <2937@bingvaxu.cc.binghamton.edu> <1990Feb8.033651.18574@Neon.Stanford.EDU> <1546@ariel.unm.edu>
Reply-To: fulk@cs.rochester.edu (Mark Fulk)
Organization: University of Rochester Computer Science Department
Lines: 103

In article <1546@ariel.unm.edu> bill@wayback.unm.edu (william horne) writes:
>What come to be know as Computational Learning Theory is actually an
>offshoot of work by Valient.  In fact, the Computational Learning Theory
>(COLT) Conferences, are centered around Valient's approach to learning.
>An introductory reference is:
>
>Valient, L.G., "A Theory of the Learnable", Comm. of the ACM, v27, n11
>	pp. 1134-1142.
>

I am a person doing computational learning theory who work does NOT
derive from Valiant's.  In fact, I started in the field before he did.
I am definitely a member of the COLT crowd, having published and presented
at COLT, and being this year's conference chair.

Computational learning theory includes any research into the mathematics
of learning machines.  Most research derives it inspiration from the work
of E. Mark Gold and Raymond Solomonoff, in the late 60's.  Gold's seminal
paper is entitled "Language identification in the limit", and appeared
in Information and Control in 1967.

The field now includes the following strands:

Recursion-theoretic (mainly what I do), which foreswears (for the time
being, not permanently) considerations of efficiency.  Our hope is to
cast light on what might EVENTUALLY be a vigorous field of feasible
learning theory.  Our claim is that the recursion-theoretic setting,
by deliberately ignoring issues such as run-time, permits easier
examination of other issues which are at least as important.  It seems
to me that the most important issues involve the sorts of data used
by a learning machine, and the criteria for its success.

Concrete, (which I've done a bit of) which tries to find efficient mechanisms
for learning specific classes of functions or sets.  For example, how
efficiently can one learn a regular language from positive and negative
examples?  Gold proved that finding the smallest DFA to fit some data
is NP-complete, but I don't think that really answers the question
(even assuming NP != P).

Probabilistic concrete: Given some sort of random source of data, one
is interested in algorithms that probably succeed, at least in
supplying a good approximation.  For example, learn a convex set in
the plane from examples chosen randomly from the set according to the
uniform distribution on the plane restricted to the set.  (Easy: draw
a bunch of examples, form the convex hull).  This kind of learning is
often called "probably approximately correct" (pac) learning.

Valiant-style, or "distribution-independent" pac learning: One must
give an algorithm that, given ANY random source of data about a problem
it is supposed to work on, probably produces an approximately correct
answer, where the approximation is measured with the same distribution
used to produce the data.

There are also questions of learning things other than programs, for example
first-order formulae, and of very powerful kinds of data (f.o. formulae
in restricted languages are quite popular again).

Obviously I'm raving on about a favorite subject.  For more information,
consult the proceedings of the First and Second Workshop on Computational
Learning Theory, published by Morgan-Kaufman.  The literature appears
mainly in Information and Computation (formerly Information and Control),
with some articles in Journal of the ACM and Theoretical Computer Science,
as well as Journal of Computer and System Sciences.  The East German
journal EIK (Elektronische Informatik und Kybernetik) is a good source
for some of the work of people in Eastern Europe.  For a REAL introduction
to the subject, including a chance to talk to real originators like Valiant,
Manuel Blum, John Case, and Rusins Freivalds,...

   COME TO ROCHESTER AUGUST 6-8, 1990!!

COLT '90, the Third Workshop on Computational Learning Theory, will be
held in Stouffer's Rochester Plaza Hotel, Rochester, New York, on those
dates.  Reception the evening of Aug. 5 (Sunday).  Send me your address,
and I'll make sure you get registration materials (email fine, I'll email
you a form).  Expect the forms towards the end of May or early June.

EVEN BETTER: SUBMIT A PAPER.

I'll post the call for papers after this article.  We are very interested
in papers that carry out mathematical analyses of neural net learning.
We are even more interested in papers that expose fresh insights into
the nature of or criteria for learning.  If you think the old stuff is
foolish, and you have the right idea to replace it, and you can write
a good mathematical paper, SUBMIT IT!  We (the program committee, I'm
just a member) might even agree!!  Just, please, do not subject us to
pure complaints with no constructive suggestions, and do not send papers
of the "I tried it twice, and it worked both times (well sort of the first
time, but the second time REALLY)" sort.

Oh, and don't send anything to me.  John Case is the program committee
chair, and has things set up to receive papers at the University of
Delaware.  Send them there; for addresses, read the call for papers.

Incidentally, the Special Interest Groups in Automata and Computability
Theory (SIGACT), and in Artificial Intelligence (SIGART), of the
Association for Computing Machinery (ACM) are sponsors of COLT '90.

Mark Fulk
fulk@cs.rochester.edu
...!uunet!rochester!fulk
Computer Science Department
University of Rochester
Rochester, NY 14627