Reflection in machine learning

Basic research project, 1999-2001, Ministry of Science and Technology, Republic Of Slovenia

[I stand corrected] Summary: The project will formally define useful kinds of computational reflection (using a model of a program within the program itself) by analyzing the capabilities of existing systems and comparing them with properties of reflective formal systems, given by classical recursion theorems and later generalizations. Effects of introducing reflection into systems for machine learning will be analyzed and an optimal kind of reflection will be experimentally built into a chosen system for machine learning, developed within the research unit.

Team -- Background -- State of the art -- References

Reflection conferences: '96 abstracts and '99 CfP

The basic goal of this reserch project is to determine the range and effectiveness of ways of using reflection in systems for machine learning. The initial and basic theoretical part will attempt to use known results about reflective formal systems such as the recursion theorems, and use any results obtained within the current project Formal self-reference in artificial intelligence. The central theme of this project, formalizing reflective progressions of reflective theories, can be partly described in terms of learning as a very abstract, idealized situation of a difficult type of learning (cf. [Lathrop]), namely inducing finite descriptions of infinite sets of axioms, generated by a certain transfinite iteration.

Assuming that the effort to formally define reflective learning indicates sufficently important advances beyond current systems of machine learning, the next goal will be to implement such advances in some local system for machine learning, developed within the research unit.

T i m e t a b l e

1999
- review and analysis of reflection capabilities in existing computational systems (for machine learning);
- comparison with properties of reflexive formal systems (eg. variants and generalizations of the recursion theorems);
- design and formal description of additional capabilities for reflection in machine learning.

2000
- determining efficient kinds of reflection, depending on the type of machine learning;
- designing a reflective improvement of a chosen local system for machine learning,
- estimating the cost of introducing reflection (execution speed, possible reprogramming).

2001
- implementing a reflexive extension for the chosen system and evaluating the result;
- possible review of previous phase(s), depending on the result.

P r o j e c t    t e a m

Members of the Department of Intelligent Systems, Jozef Stefan Institute, Ljubljana: and former/associate members:


The background of this research is the increasing appearance and role of mechanisms of reflection in computational systems (of artificial intelligence) and their introduction into systems for machine learning. The attribute 'reflective' typically denotes a program which includes and uses a representation of itself, eg. for explaining its decisions or improving its performance (eg. detecting (some) loops, simplification). Reflective programs are usually interpreted, which allows the program to access its own code, and in addition the trace of its interpretation and the very intepreter which runs the program. These additional possibilities suggest a more general conception of computational or behavioral reflection as the ability of a program to 'change, even at run-time, its own code and the semantics and implementation of its programming language' [Malenfant & Demers]; this conception of reflection also covers compiled programs [Friedman et al].

Current uses of reflection in machine learning i.e. the programs for machine learning which are called reflective by their authors, actually tend to instantiate a fairly simple meta-level architecture. Such an architecture has a clear hierarchical structure, without any real reflective loops [Steyaert] i.e. reflective [Steyaert] or introspective [Smith] overlap. If a system contains its own representation, the content of this representation has to be compatible with its inclusion in the system; that is, the representation must not »reflect« facts about the system which are invalidated by its very presence in it [Smith]. A simple example of such overlap, without its possible conflicts but, on the contrary, a harmonius one, building the foundation for a formal structure, is the double use of diagonalization in building the self-reference of Gödel's sentence: the representation of diagonalization involves formulas which »already« contain that representation [Bojadziev].

Reflection as self-application is a classical theoretical concept in computer science, present from the very beginning in Turing's reflective machines [Webb], but it has recently also established itself as a practical technique in the main programnming paradigms (logic, functional and object programming). Standard examples are:

Many such systems/languages are being developed eg. in the Yonezawa laboratory of Tokyo University.

In Slovenia, the first research project concerned with computational reflection, Formal self-reference in artificial intelligence, currently runs in the Department for intelligent systems at the Jozef Stefan institute, Ljubljana [Gams et al]. There is some similarity between this research and the one described here, but there are significant differences in most respects, mainly in scope (the research described here is much more specific), application area (here, it is machine learning only) and target formalism (here, it is programming-oriented). An early forerunner of the present research is the work done in the Department on meta-level architectures of expert systems [Lavrac & Vassilev 89].

The problem, targeted by the this research, is the basic problem of the way and usefulness of using reflection in a system for machine learning, beyond the current, mainly meta-level structures. Solving this problem would open the way for introducing some appropriate form of reflection into existing Departmental systems for machine learning, such as LINUS, which learns non-recursive definitions of relations [Lavrac, Dzeroski & Grobelnik]. Since introducing reflection into existing systems brings with it a certain processing cost (run-time, memory, possible reprogramming), this reflection overhead will have to be justified by a cost/benefit analysis or experimental estimate.

The novelty of the present research consists in its orientation beyond the common meta-level solutions, which tend to reduce to simple command procedures or, at the opposite end, shift the problem to the meta-level (learning how to learn [Schmidhuber]).

An interesting phenomenon of human learning and cognition in general, which would appear to be at least partially connected with the capacity for reflection, is the experience of sudden insight, click of comprehension (Brown), the A h a-Erlebniss, in which we realize what the solution to a problem is, or understand what we have been trying to learn. There are as yet no computational treatments of this aspect of learning, and this research will not explicitly target it, but it may provide at least some partial insight into sudden insight.

State of the art

Many supposedly reflective systems for machine learning actually have a more or less non-reflective, merely meta-level architecture. For example, the supposedly reflective shell AUTOGNOSTIC [Stroulia & Goel], presented in more detail at the Autognostic project page, is actually a meta-system, a normal shell, operating on other systems, so that both its name (AUTOgnostic) and the characterization of its activity (reflective learning) are badly chosen; the same applies to the special case of this shell called REFLECS. Much the same can be said about the series of  "self- reflective" sistems, documented in the AI laboratory of the University of Michigan, eg. THEO [Mitchell et al]. Systems, sketched in the literature, frequently tend to remain at the gestural level, providing "new approaches" without coming nearer or actually reaching a solution.

Current theoretical knowledge about reflective machine learning is also rather limited, much more than the knowledge about reflective computational systems in general. There are efforts to establish a unified formal framework for reflection, usually within a system of logic, but there are far less formal results/theorems within such a system, or at least attempts to apply classical formal results about reflection to a theory of reflective machine learning, eg. Kleene's recursion theorems [Case]. Interestingly enough, there are already results about the hardest learning problem, namely learning what cannot be learned, since it does not exist (the decision function) [Lathrop].

In the complementary area of computational teaching, there are some initial proposals of reflective systems which would take into account the human reflection of the learner, by building and using a (reflective) model of her [Morales]. In general, there are more analyses of the role of reflection in learning and of ways to use and encourage it in the humanistic literature [Flake].

Re f e r e n c e s

Assumpcao, J. et al, Bootstrapping the Object Oriented Operating System Merlin: Just Add Reflection, in Zimmerman, C. (ed.), Advances in Object-Oriented Metalevel Architectures and Reflection, CRC Press, 1996

Bojadziev, D., Reconstructing diagonalization(s), Yearbook of the Kurt Gödel Society 1989, pp.74-77, Wien 1990

Case, J., Infinitary Self Reference in Learning Theory, Journal of Experimental and Theoretical Artificial Intelligence, 6 (1994), 3-16.

Flake, J., Reflections on Reflective Learning in a Computer Environment, Dept. of Educational Theory and Practice report, Florida State University

Friedman, D.et al, Dynamically Extensible Computational Reflection, DARPA/NCF research project

Gams, M. (principal researcher), Bojadziev, D, et al, Formal self-reference in artificial intelligence, basic research project, Ministry of Science and Technology, J2-7643, 1996-98, approved extension to 1999-2001

Gams, M. et al, EMA - An Intelligent Employment Agent, Proc. 4. Th World Congress on Expert Systems, Mexico, pp. 57-64, 1998.

Hölzle, U., Ungar, D., A Third-Generation Self Implementation, Proc. ACM OOPSLA `94 Conference, Portland, Oregon, 1994

Kiczales, G. et al, The Art of the Metaobject Protocol, MIT Press, 1991

Lathrop, R., On the learnability of the uncomputable, in Saitta, L. (ed.), Proc. 13.th International Conference on Machine Learning, pp. 302-309, Bari 1996, Italy, Morgan Kaufman, San Francisco

Lavrac, N., Vassilev, H., Meta-level architecture of a 2.nd generation knowledge acquisition system, 4.th European Working Session on Learning EWSL 89, Montpellier 1989; London: Pitman, pp. 99-109.

Lavrac, N., Dzeroski, S., Grobelnik, M., Learning nonrecursive definitions of relations with LINUS., Proc. Fifth European Working Session on Learning, 265-281. Springer, Berlin, 1991.

Lunau, C.P., Papers on Reflection in Object-Oriented Languages

Maes, P., Nardi, D. (ed..), Meta-Level Architectures and Reflection., North Holland 1988

Malenfant, J., Demers, F., Tutorial on Behavioral Reflection and its Implementation, Proc. Reflection '96

Mitchell, T.M.et al, Theo: A framework for self-improving systems, in K. VanLehn (ed.), Architectures for Intelligence, pp. 325-355, Lawrence-Erlbaum Associates, Hillsdale, N.J., 1991.

Morales, R., Modelling user reflection, PhD proposal, Dept. of AI, Univ. of Edinburgh

Proceedings of OOPSLA'93 Workshop on Object-Oriented Reflection and Metalevel Architectures, Washington, D.C., September 1993

Rivard, F., Smalltalk: a Reflective Language, Proc. Reflection '96

Sanchis, L., Reflexive structures, Springer 1988, and Recursive functionals, Springer 1992

Schmidhuber, J., On learning how to learn learning strategies, Technical report FKI-198-94, 1995 [ps]

Smith, B. Varieties of Self-reference, in J. Halpern (ed.), Theoretical Aspects of Reasoning about Knowledge, Proc. of 1986 Conference, Morgan Kaufmann Publishers, 1986

Sobel, J.M., Friedman, D.P., An Introduction to Reflection-Oriented Programming, Computer Science Department, Indiana University

Steyaert, P., Computational Reflection and Open Systems, in: Open Design of Object-Oriented Languages, A Foundation for Specialisable Reflective Language Frameworks, PhD Thesis, Vrije Universiteit Brussel, 1994

Stroulia, E., Goel, A., A Model-Based Approach to Reflective Learning. , Proc. 1994 European Conference on Machine Learning, Catania, Italy, April 1994, pp. 287-306..

Webb, J., Mechanism, Mentalism and Metamathematics - An Essay on Finitism, D. Reidel Publ. Co. 1980

Yonezawa, A., Smith, B. (ed)., Reflection and Meta-level Architectures, Proc. Int. Worskhop on New Models for Software Architecture, Tokyo 1992

Gunter Grieser, Dimitar Kazakov