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 :

Keywords : Inductive inference, Theory of Complexity, Query Learning
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
  1. The Teacher is assumed to be the Prover
  2. The Learner  is assumed to be the Verifier
  3. V-to-P messages are membership and equivalence queries
  4. 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 ...
  1. What is the input string if we consider IPS as  a learning process ?
  2. What kind of information must the Prover give to the Verifier ?
  3. 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.


[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.