languages

[Jerry Feldman]

  Some months ago, I suggested a benchmark task of learning finite state
languages from examples. It was noted that the task is provably feasible
from lexicographically ordered examples and provably intractable from
arbitrary presentations. Two recent theoretical results show that the case
of arbitrary presentation is not even approximately solvable in any reason-
able way. The papers are by Kearns and Valiant (STOC 89) and by Pitt and
Warmuth ( U. Illinois TR ENG-89-1718 ).

  The proofs rely on very unnatural examples, like exactly one crafted
perverse string. Thus one should not be discouraged from seeking solutions
to more reasonable cases, but should be very careful about the claims made.

  We are currently working on a task which is both easier and much harder
than the original abstract one. The goal is to have a system learn a tiny
fragment of natural language describing simple 2D pictures from examples
of sentence-picture pairs. The system is supposed to work on presentations
in any natural language, but our initial work is more constrained. If
people are interested, we could send or post more details.

Jerry F.