Some Learning Systems are Deterministic Interactive Proof
Systems
José M. Sempere
Departamento de Sistemas
Informáticos y Computación
Universidad Politécnica
de Valencia
Valencia 46070 (Spain)
Tel : + 34 6 387 73 53
Fax : +34 6 387 73 59
email : jsempere@dsic.upv.es
Keywords : Inductive inference, Theory of Complexity,
Query Learning
Abstract
Inductive Inference [6]
is a learning paradigm in which examples (and counterexamples) are provided
to the learner in order to communicate any concept to be learned.
Under inductive inference paradigm, if the space to represent
the concepts is considered a formal grammar class and the examples and
counterexamples are considered labelled strings, then the framework is
named Grammatical Inference. A lot of methods have been proposed
to learn different language classes. A good review of the general concepts
and methods in this framework can be seen in [2]
while a good viewing of the most significant theoretical
results for inference of recursively enumerable languages can be seen in
[5].
An Interactive Proof System (IPS), as stated
in [3]
consists of two Turing machines (P) and (V) and a set of tapes to
communicate them. P (the prover) is a computationally
unlimited deterministic Turing machine while V (the verifier)
is a polynomial-time deterministic one. P and V take turns to be
active. Every time one of them is active then can write and read,
change its state and send any message to the other machine. The acceptance
criterion is defined through the final states of V. When V has stopped
its computation (i.e. no more V-movements are carried out) the
acceptation or rejection of the input string is considered. In such a model
the number of messages interchanged between P and V and the length of them
is polynomially bounded. It is well know that this model defines
a complexity class (DIP) which has been proved equivalent to NP.
If a random device is introduced into the model, then a new complexity
class is defined (IP) and it is equivalent to PSPACE.
A Minimally Adequate Teacher (MAT)
as defined by Angluin in [1]
is a learning system in which the Teacher can answer
two different kind of queries : membership and equivalence. In the last
case, for answer NO it provides a counterexample for the symmetric difference
between the target concept and the learner hypothesis. There
are different succes criteria for this model (i.e. exact identification
in the Limit , PAC identification, . . .). We consider here polynomial
exact identification. That is, the learner, after making a polynomial
number of queries and proposing a polynomial number of hypotheses,
exactly identifies the target concept proposed by the Teacher. Some language
classes as the regular languages can be learned under the
MAT protocol.
In this work, a technique is presented to relate MAT
learning systems with IPS devices.
Main theorem : Every language which can be learned in
polynomial time with a MAT protocol can be accepted by a IPS.
Outline of the proof
We can define an IPS based
on a MAT protocol in the following way
-
The Teacher is assumed to be the Prover
-
The Learner is assumed to be the Verifier
-
V-to-P messages are membership and equivalence queries
-
P-to-V messages are YES/NO answer plus counterexamples
Every time, an input string
is supplied to the IPS, the Prover and the Verifier simulate the
behaviour of the Teacher and the Learner during the learning process. If
the input string belongs to the learned language then it can be proved
in polynomial time.
Learning while proving
Interactive Proof Systems establishes a protocol for learning
concepts in a similar way as MAT protocol. So, P-to-V messages
can be considered as the information that a Teacher gives to
the Learner during a learning process, and V-to-P messages
as the questions that the Learner makes to the Teacher. Anyway, there
are some questions which start to arise if this system is considered
for learning ...
-
What is the input string if we consider IPS as
a learning process ?
-
What kind of information must the Prover give to the Verifier
?
-
Which additional knowledge does the Verifier need ?
The answer to these questions will define IPS as
learning processes. The next step to be considered will be
the study of the classes of proofs which can be learned under a reasonable
learning system. In the present work some of these aspects will be discussed.
References
[1] Angluin, D. Learning Regular Sets from Queries
and Counterexamples. Information and Computation 75, pp 87-106. 1987.
[2] Angluin, D., Smith C. Inductive Inference : Theory
and Methods. Computing Surveys, Vol 15. No. 3, pp 237-269. 1983.
[3] Bovet, D. Crescenzi, P. Introduction to the Theory
of Complexity. Prentice Hall. 1994.
[4] Gold, M.E. Language Identification in the Limit.
Information and Control 10, pp 447-474. 1967
[5] Osherson, D., Stob, M. and Weinstein, S. Systems
That Learn. The MIT Press. 1986.
[6] Solomonoff, R.J. A Formal Theory of Inductive Inference.
(Part I and II). Information and Control 7, pp 1-22, pp 224-254. 1964.