Symbolic or Functional Grounding

As I presented in my introduction to this thesis, the symbol grounding problem is the problem encountered when trying to relate the symbols in a physical symbol system to objects in the system's environment. S. Harnad [22] presents this as the inability of current agents to acquire an intrinsic meaning for the features they encounter in their environment, opposing this intrinsic meaning to the extrinsic meaning a human assigns to the components of the system he is observing or building. His formulation of the symbol grounding problem, focussed on meaning, is in fact inspired from the attack, focussed on intentionality, led by Searle [53] against computer intelligence and more precisely understanding in his well known Chinese room argument. With this argument, Searle intends to demonstrate that digital computers lack the causal power to do anything but produce a formally predefined next stage in a programmed calculation. He then concludes by saying that: formal symbol manipulations have no intentionality, they are meaningless; they aren't even symbol manipulations, since the symbols don't symbolize anything. In the linguistic jargon, they have only syntax but no semantics. This part of the doubts of Searle regarding artificial intelligence appear to be relevant since the production of meaning in symbol systems seems out of reach for the current approaches to AI. I would suggest that actually, the determinism that Searle reproaches to computers is not a true limitation. The fact that it appears as such is related to the idea that programs can always be simply interpreted by an observer. When this is not the case, formally predefined next stages in a calculation can induce very interesting (and unpredictable) behaviors in a program. I will now suggest a view of meaning independent of the (anthropologically flavored) intentionality of Searle which could allow further investigation into artificial intelligence.

Solving Grounding

The search for a solution to the symbol grounding problem has followed one main direction, namely that grounded systems need a tight relation with their environment and that this relation must be established by the sensory-motor equipment of an agent. A lot of research has thus gone into the study of perception in situated symbol systems, both from a top-down and from a bottom-up perspective, as described by Ziemke in [72].

To this end, the cognitivist approach embodied by classical AI attempts to devise high level input systems responsible for mapping perception into internal representations in a way that is coherent with this representation. Its recent methodology developed in the context of the symbol grounding problem generally consists in the extraction of perceptual features or invariants that can be related to atomic components of the internal representation. These components are then used to form the first ``grounded'' layer in the agent's representation of the world and from which the whole world model is constructed. In the attempt to ground representations of these components to categories of objects in the world, the cognitivist approach also often distinguishes between a symbolic and subsymbolic level of representation. Perceptions are then analyzed on a subsymbolic level, typically implemented with a connectionist method, to bring forth perceptual categorization at the symbolic level. Ziemke [72] classifies the main proposals for symbol grounding in this framework into Harnad's proposal of iconic representations [22] and Regier's perceptually grounded semantics [48] to which I would add the work of L. Barsalou on perceptual symbol systems [3].

The new AI (bottom-up) approach to symbol grounding, on the other hand, is not only focussed on the agent's perception, but on its active qualities. Following Maturana and Varela's autopoietic theory [39], agents are characterized by their embodied situatedeness, emphasizing the fact that an agent experiences the world through its active participation in it, called experiential enaction. The enactive cognitive science that follows from this theory [63] gives the theoretical framework for bottom-up grounding. In fact, since bottom-up methodology boasts the absence of representation [7] and the internal structure of the agent built here is grown from perception, these agents should be immediately grounded in their environments. In practice, new AI is behavior based in that agents are usually equipped with some elementary behaviors that are designed by the scientist and then these behaviors are allowed to interact and combine to form more complex behavioral patterns. It is these behaviors and their combination mechanisms that need now to be grounded and this proves to be of comparable difficulty to the initial symbol/representation grounding. One approach that has been used to this aim is the evolution of all behaviors from perceptions by using a dynamically generated (evolved) connectionist architecture to control an agent [33,11]. I believe this method can generate grounded agents because the internal functionality of such systems is evolved in conjunction with the problem domain and this is the fundamental point that I want to make in the following sections, unfortunately, the approach suffers from the size of the space of solutions that must be explored by the evolution mechanism.

Locating Meaning

The three components partaking in the grounding problem are the environment, the agent and the sensory-motor equipment linking an agent to its environment. In the various AI techniques described previously, the environment has played the role of problem domain with the assumption that in this domain, objects or object categories have an intrinsic meaning. Since the human ability of reasoning appears to be based on the acquisition of this meaning in the environment, attempts to transfer this meaning in a similar way to symbol systems have recently been focussed on the agent-environment interface. The various designs of agent control mechanisms that are supposed to accommodate this meaning have of course remained the main active area of the field of artificial intelligence, but generally with a distinct emphasis, boosted by new AI and the statement of the symbol grounding problem, on the action/perception properties of agents, since it is their only access to the world.

When considering a human agent, the assumption made is that there exists some form of meaning that he can acquire to relate objects and events in the environment either independently or in relation to himself. This meaning, whether intrinsically preexistent in the world or co-constructed by his embodied situatedeness in the world then serves him to reason about the environment and solve problems within it. If we are to build artificial agents that can acquire a similar form of meaning in order to make decisions, I believe the fundamental sense in which meaning must be understood is, following a functionalist approach, as the causal role of elements in their environment. In this sense, meaning becomes an intrinsic property of these elements in the environment, or globally, in the agent-environment system.

In the AI techniques described previously, it appears that attempts to ground agents in their environment are focussed on the means of transferring external meaning into an agent's internal mechanisms. The emphasis is put on the internal mechanism an agent is fitted with to accommodate this meaning and, more recently, on the transduction apparatus interfacing an agent with his environment. I believe this approach is too intent on ``hooking'' environment elements to agent internal symbols. Even in the case of enaction approaches, eventually excluding the previously cited evolutionary connectionist techniques, the intent lies in connecting sensory information to internal processes, while these processes are partially predefined and their dynamics not well understood. These methods give the impression that what is attempted is a token-token identification between world tokens and agent tokens. But within the functionalist theory of mind, this form of identification has been shown not to hold the essence of mental characterizations. What should be deemed most important in an agent is the functional role of its internal components and since I have considered meaning in terms of the causal role of elements in the environment, meaning in this sense also preexists in an agent, expressed in terms of the functional role of its internal components. From this perspective, agents own an intrinsic meaning for the symbols of their internal representation, which is given as the functional role those symbols play for their own internal dynamics. Thus a situated agent is always grounded in its environment through its interaction with it, but the current techniques of implementing agents fail to provide these agents with the proper internal structure for a coherent functional integration of these agents in their environment. In other words, the intrinsic meaning an agent possesses cannot be correctly related with that of the environment and fails to reach the higher levels of integration that are visible in living creatures.

  

Figure 3.1: The functional structure in an agent.

If one looks at the current architecture of an agent 3.1, one usually sees some sort of functional structure linking components together and conveying information from sensors to effectors. Without adaptation, this structure is fixed and the dynamics of the agent will remain identical, whatever happens in the environment. With learning, the component links are usually malleable, being strengthened or weakened under the effect of external events, but the potential dynamics remain limited to what the implementer has imposed as his semantics for learning. Using evolutionary techniques, the components can then also be rearranged so as to adapt to the environment what functionality was given to the agent. The general trend of these methods is clearly to allow an increasingly functional grounding of an agent in its environment, but the missing element of the study is an analysis of the types of functionalities that can be provided to an agent in its components. These components are usually chosen because they express a function that is deemed important for the problem the agent will be faced with, but the question of what is important for the agent itself is rarely, if ever, investigated. In an somewhat excessive manner of speaking, where are the qualia^3.1 components of these agents? And without delving into abstract considerations such as those presented by Nagel in his article ``What is it like to be a bat?'' [43], the question of what it is like to be a digital agent surely requires of us a better understanding, without conceit for science, of the properties of the languages used to implement agent architectures.

Languages, Information and Dynamics

The definition of algorithms given by Turing has brought the abstract conception of machine or computer to science and served to build the current computers. With the study of universal Turing machines, the understanding of what machines can and cannot compute has also been understood and used, but the relation between program and data has always been problematic and while one universal Turing machine can theoretically compute what any other can, the information (under the form of symbol strings) that has to be provided to different universal machines for solving the same problem is also different. In fact, while it is at the heart of all of today's concerns, the simple notion of information has no unique definition in computer science.

At the center of this problem lies the difficult program versus data relation that has recently been studied in the field of information theory with various definitions of the information content of an object, an overview of which can be found in [50]. The most appropriate definition, that I will use here, is called the algorithmic information content or Kolmogorov-Chaitin complexity of an object. But it is worthy to note that information problems are not restricted to computer science, but were originally adressed by Shannon in the context of telecommunication [54] and also have implications that reach into biology [2] or physics [5,36].

Algorithmic Information

The definition of algorithmic information takes into account both structures and dynamics by using descriptions and description languages. When we need to measure the complexity of an object, a description of the object is considered, intuitively, when this description can be short, the complexity of the object is to be considered to be small and when this description is necessarily long, the object is complex. The typical example of this is when one is presented with two pictures as in 3.2. The first consists in an alternating distribution of gray and white bars and the second in a sequence gray and white bars whose positions must each be specified independently. The first figure can be easily described by giving the description of a gray and white bar and specifying its repetition, for the other illustration, each start and end position must be included in the description.

  

Figure 3.2: Two patterns to be described.

Algorithmic information theory [8,9] formalizes this understanding by measuring the information content of binary string descriptions (any string description can be written as a binary string) and applying the language of algorithms (Turing machines) to these strings. The algorithmic information of a description is the shortest description of an object that can be made using algorithms and strings. Formally, let s be a string that describes an object. There exists a family of Turing machines $\{T_i\}$ that when applied to strings $\{u_i\}$ will generate the string s, i.e. T_i(u_i)=s for each i. Since the machines T_i can be written as strings t_i. One can form the strings $d_i = t_i \oplus u_i$ by concatenation and these strings are descriptions of the original object that are equivalent to s since they can be used to reconstruct s. The algorithmic information of the object is the length of the shortest string in the set $\{d_i\}$, written K(s). Note that in the concatenation operation, a constant length delimiter must be used to distinguish algorithm part and string part. For a complete easy formal presentation of this theory, see [56].

In this definition, one uses Turing machines (programs) operating on input strings (data) to measure the information content of the objects under consideration. In practice, other types of description languages may be used to define equivalent information measures and it has been shown that for any given description language $\Delta$, there exists a fixed constant $k_{_\Delta}$ such that for any string s, $K(s) \leq K_{\Delta}(s) + k_{_\Delta}$. This indicates that whatever the description language, the information of objects is of the same order as their algorithmic information and is interpreted as an optimality property for this information measure.

Expressivity

The interesting point in this theory is the optimality interpretation given to the previous result. I think that this is characteristic of the difference that exists between theory and practice, for when two measures differ by ``at most'' a constant term, in theory the measures are equivalent, but in practice such a constant term may make a big difference. Consider the following situation: who hasn't smiled when he heard the anecdote of Von Neumann almost firing his assistants for wasting time in developing a higher level language than assembly on the IAS computer. The importance of expressivity in programming languages today is evident, and most courses on programming emphasize the choice of the right language for the right problem. The fact that any program can be written in assembly language is theoretically interesting, but in practice useless when one must implement a specific ``complex'' program on a computer.

Admitting this intuition implies that the constant provided by the algorithmic information theorem is actually large enough in some cases that in practice the choice of language does have a role when implementing distinct problem solving algorithms. And, returning to the main discussion, in particular when an artificial agent architecture is implemented. Additionally, this theory gives a hint at what could be the functional features that one is looking for when an agent must be designed for a specific environment.

Understanding as Information Compression

With the intrinsic meaning in an agent defined as the functional roles of its various components (ie. the potential for self en environment transformation they define), the environment elements that will most firmly be grounded in an agent should be those that are closest to the agent's internal representation dynamics. The measure of this proximity can easily be seen as the algorithmic information of the description of the external events or elements in the agent's internal representational language. In this language, the objects in the environment of an agent and the dynamics in the environment can be described by using symbols and their functional role. For each environment object or property, there exists a large number of different equivalent descriptions in the agent language, each owning a distinct meaning and the search for the most efficient description in terms of algorithmic information can be seen as the process of understanding for an agent.

If this hypothesis is accepted, a new approach to implementing agents is to search for a representational language that gives the shortest possible descriptions for the agent's environment perceptions. If this approach is pushed further, one might even attempt to provide agents with mechanisms for the compression of perceived information, so as to allow the agent to form sub-architectures that are specialized languages that deal with certain perceptions and act as information compression components in the agent that could parallel the process of understanding. Furthermore, a study of the dynamics that algorithms are naturally adapted to express can be made with experimentation on test cases. Of course, since the description languages instantiated by various agent algorithms have distinct properties and none can be universally efficient, the goal must be to find algorithms that can be applied to specific problem domains encountered in practice. This last sentence can be summed up by the statement that generalization is impossible in general, but that the problems encountered in practice can be generalized over.

Classification

A first step that I consider essential would be to make a classification of the known algorithms with respect to their informational properties. By classifying the known algorithms, an easier introduction to the very wide number of different methods used in the field could be accessed by young researchers. By providing categories of algorithms, the problem domains addressed by artificial intelligence would also be clarified. To that aim, I propose a benchmarking methodology, based on a collection of test case experiments used to evaluate the characteristic features of algorithms. Such benchmarking experiments can be devised based on the tests already used by many of the schools of AI, such as ``Santa Fe Trail'' experiments used in artificial life or obstacle avoidance problems used in mobile robotics. I give an example of this type of experimentation in the application part of this work by studying the use of classifier systems both in the representation perspective and the dynamic perspective provided by EMud environments.

Theoretical Approaches

In further refinements, the theoretical approach of formalizing the expressivity properties of algorithms seen as Turing machines could be pursued. Here, difficulties arise mainly from the lack of mathematical tools suited to practical expressivity notions and the criteria for determining what problem domains are relevant to artificial intelligence problems when working on abstract machines. A first course of action that I have used is to apply non-standard analysis techniques to Turing machines. By using non-standard analysis, one can make an additional distinction in element sets, dividing them into the class of standard elements and non-standard elements. Intuitively, this distinction separates elements that can be constructed in practice from elements that have a theoretical existence, but cannot be produced. When the set of Turing machines is considered, the standard Turing machines are those that can be realized as computers and the non-standard ones are those that can serve in proofs for example, but could never be constructed in practice. Using such a distinction allows some basic problems to be understood, such as the fact that the famous halting problem does not exist for standard Turing machines, but some non-trivial results still need to be demonstrated in this theory.