Nina Gierasimczuk, Believing in Formal Learning Theory
Abstract:
This talk brings together two types of learning.
The first kind, getting to know about facts, is formalized and
analyzed in the domain of belief revision and the diverse frameworks
of epistemic
and doxastic logics. The main aim here is to formalize the elementary dynamics
of knowledge and epistemic attitudes towards incoming information. The second
kind, learning as a process, is studied within the framework of formal learning
theory. In this framework a general concept (language, grammar, theory) gets
to be identified by an agent on the basis of some elementary data (sentences,
results of experiments) over a long period of time. The learning agent
is allowed
to change his mind on the way, and the process is successful if it results in
convergence to an appropriate hypothesis. In a sense this kind of learning is
built on top of the first kind, it consists of an iteration of simple
gettingtoknow
events.
In this talk we propose a way to use the framework of learning theory
to evaluate beliefrevision policies. On the inductive inference side,
we
are interested in the paradigm of language learning. As possible
concepts that are inferred we
take sets of atomic propositions. Therefore, receiving new data corresponds to
getting to know about facts. On the side of belief revision we follow
the lines of
dynamic epistemic logic (see van Benthem, 2007). Hence, we interpret current
beliefs of the agent (hypothesis) as the content of those possible
worlds that he
considers most plausible. The revision does not only result in the change of the
current hypothesis, but can also induce modification of the agent’s plausibility
order. We are mainly concerned with identifiability in the limit
(Gold, 1967). In the
first part we restrict ourselves to learning from sound and complete streams of
positive data. We show that learning methods based on belief revision via conditioning (update) and lexicographic revision are universal, i.e.,
provided certain
prior conditions, those methods are as powerful as identification in the limit.
Those prior conditions, the agent’s prior dispositions for belief
revision, play a
crucial role here. We show that in some cases, these priors cannot be modeled
using standard beliefrevision models (as based on wellfounded preorders), but
only using generalized models (as simple preorders). Furthermore, we draw conclusions about the existence of tension between conservatism and learning power
by showing that the very popular, most ‘conservative’ beliefrevision
methods fail to be universal. Then we turn
to the case of learning from both positive and negative data. Here, along with
information about facts the agent receives negative data about things that do
not hold of the actual world. We again assume these streams to be truthful and
we draw conclusions about iterated belief revision governed by such streams.
This enriched framework allows us to consider the occurrence of erroneous information. Provided that errors occur finitely often and are always eventually
corrected we show that the lexicographic revision method is still reliable, but
more conservative methods fail.
Our results can be interpreted as showing that applying certain types of
rules in certain contexts can be analyzed in terms of whether they can be relied
upon in the ‘quest for the truth’ (the analysis of inductive inference
in terms of
reliability has been for the first time provided by Kelly, 1996). In
our framework
we can naturally treat the procedural aspect of iterated belief
revision, address
some intermediate stages of such iterations and relate them to the ultimate
success of a beliefrevision policy.
The results presented in this talk come from a joint work with Alexandru
Baltag and Sonja Smets.
References
van Benthem, J. (2007). Dynamic logic for belief revision. Journal of Applied
NonClassical Logics, 2:129–155.
Gold, E. (1967). Language identification in the limit. Information and Control,
10:447–474.
Kelly, K. (1996). The Logic of Reliable Inquiry. Oxford University
Press, Oxford.
