text:
# Information Compression by Multiple Alignment, Unification and Search as a Unifying Principle in Computing and Cognition11footnote 1In Artificial Intelligence Review 19(3), 193–230, 2003.

## 1 Introduction

This article presents the idea that information compression by multiple alignment, unification and search (ICMAUS) may serve as a unifying principle in artificial computing and natural cognition. In this context, multiple alignment has a meaning that is similar to its meaning in bio-informatics (with important differences), unification means a simple merging of patterns or parts of patterns that match each other, and search means searching for alignments yielding relatively large compression, pruning the search space using heuristic techniques or other forms of constraint.

There is now a fairly large body of evidence in support of this conjecture, described in Wolff \[2000, 1999b, 1999a\] and earlier sources cited there. This article presents an overview of these ideas, with examples from the SP61 computer model. The aim of this paper is to explain the ICMAUS concepts in outline and to illustrate their wide scope. A full evaluation of the concepts is outside the scope of this paper although a few remarks on that subject are made in Section 9. Another paper is planned to evaluate the concepts in relation to alternative theories and empirical data.

The emphasis in previous writings about the ICMAUS concepts has been on the ‘computing’ aspects of the proposals, whereas this article puts weight on the multi-disciplinary nature of the proposals and the cognitive science dimension.

## 2 Background

### 2.1 Cognitive economy

From the writings of William of Ockham in the 14th century and Ernst Mach in the 19th century, a principle of parsimony has been recognised as relevant to an understanding of thinking, perception and the workings of brains and nervous systems. Other writings in this tradition include Zipf , Attneave , Oldfield , von Békésy , Barlow  and many other publications over a long period), Watanabe , Garner , Wolff . Nice reviews of some of the issues and many other pointers to related research are provided by Chater .

In case these ideas seem a little obscure, consider the phenomenon of recognition. Recognising someone as ‘the same’ from one instant to another or from one occasion to another is essentially a process of merging (and thus compressing) many individual percepts into a single concept. If we wish to treat a given person as a single person, it would be very inconvenient if we did not merge our many perceptions of that person in that way.

In terms of biology, there is every reason to believe that natural selection would have favoured brains and nervous systems with an ability to economise on the storage and transmission of information.222Different rules may apply to the genetic code itself. DNA is such an economical means of storing information that there may be relatively little selection pressure in favour of economy. And replication of genes may on occasion yield advantages in terms of physiological functions. Perhaps more importantly, a key function of neural tissue is the inductive prediction of the future from the past and it is known that there is an intimate connection between information compression (IC) and this kind of inductive inference \[Solomonoff, 1964, Chater, 1996, 1999\].

### 2.2 Models of language learning and Minimum Length Encoding

The ideas to be described grew more immediately out of a programme of research developing the MK10 and SNPR computer models of first language learning by children \[see Wolff, 1988, 1982, and earlier papers cited there\]. A key idea emerging from this research was that many aspects of language learning could be understood in terms of IC or, more precisely, principles of Minimum Length Encoding (MLE)333MLE is an umbrella term for Minimum Message Length encoding (MML) and Minimum Description Length encoding (MDL). pioneered by Solomonoff , Wallace and Boulton , Rissanen  and others \[see Li and Vitányi, 1997\].

The key idea in MLE is that, in grammar induction and related kinds of processing, one should seek to minimise $`(G+E)`$, where $`G`$ is the size (in bits) of the ‘grammar’ (or comparable structure) under development and $`E`$ is the size (in bits) of the raw data when it has been encoded in terms of the grammar. This principle guards against the induction of trivially small grammars (where a very small $`G`$ is offset by a relatively large $`E`$) and over-large grammars (where $`E`$ may be small444If the grammar is very poor it may not even achieve a small $`E`$. but this is offset by a relatively large $`G`$).555The goal of minimising $`G`$ and $`E`$ for a grammar echoes the way science does or should aim for theories with a favourable combination of simplicity and descriptive or explanatory power.

Amongst other things, this idea provides a handle on how it is that a child, apparently without the need for correction by a teacher, negative samples or grading of samples (as postulated by Gold, 1967), can distinguish ‘correct’ generalisations from ‘incorrect’ ones despite the fact that, by definition, both kinds of generalisation have zero frequency in the child’s experience \[Wolff, 1988, 1982\].

### 2.3 Seeing connections

The first hint (in my mind) that IC by pattern matching, unification and search might provide a unifying framework for biological and artificial kinds of computation arose from the following train of thought:

* A prominent feature of the MK10 and SNPR models of language learning is a process of IC by finding patterns that match each other and then merging (‘unifying’) multiple instances to make one.666Provided they are larger than a certain minimum, patterns that match each other represent ‘redundancy’ in information. Hence, redundancy can be reduced (and information can be compressed) by unifying matching patterns. This is the basis of all the simpler standard techniques for information compression. These models also incorporate a process of searching amongst alternative possible unifications to find those that are relatively good in terms of compression.
* Pattern matching and search are prominent in systems like Prolog, designed originally for theorem proving. And ‘unification’ in the sense of this article (the merging of matching patterns) is a prominent part of ‘unification’ as it is understood in Prolog and other systems for logical deduction.

These and other reflections on the nature of information processing led to the first conjectural proposal that ‘computing’ in some deep sense might be understood as IC by the matching and unification of patterns \[Wolff, 1990\].777Solomonoff  had already observed that the great majority of problems in science and mathematics may be seen as either ‘machine inversion’ problems or ‘time limited optimisation’ problems, and that both kinds of problems can be solved by inductive inference using MLE principles. Although this is not a proposal that ‘computing’ itself might be understood as IC, the observation does provide some support for that hypothesis. Given the prominence of IC in diverse aspects of human cognition, perception and neural functioning, it is natural to suppose that IC may provide a unifying principle for both artificial computing and the processing of information in brains and nervous systems \[Wolff, 1993\].

The aim of subsequent research has been to refine and develop these first embryonic ideas, attempting to answer the many questions and issues that arose. A key insight has been that the explanatory scope of the concepts could be greatly increased by replacing ‘pattern matching’ within the framework by the more specific concept of ‘multiple alignment’ (similar to the concept of multiple alignment in bio-informatics but different in important ways, as will be described).

### 2.4 Related research

Since the ICMAUS concepts are an attempt to integrate ideas across a wide area, they naturally relate to a large volume of published research. As noted above, this article aims to present the ideas and illustrate their wide scope, with the evaluation of the proposals in relation to existing research largely deferred to another paper.

In general terms, this research may be seen as a contribution to Newell’s  quest for ‘unified theories of cognition’, alongside Soar (e.g., Laird et al. , Young and Lewis ), ACT-R \[e.g., Anderson and Lebiere, 1998\] and other attempts to integrate concepts in cognition. Like these other models, the ICMAUS framework aims to avoid the pitfalls of ‘micro’ theories for narrow domains by developing concepts with broad scope whilst striving for overall simplicity.

The main differences between the ICMAUS proposals and others are:

* The emphasis on IC as a unifying principle.
* The multiple alignment concept as it has been developed in this research.
* The intended scope of the proposals beyond human cognitive psychology to concepts in computing, mathematics and logic.

## 3 The ICMAUS Framework and the SP Models

The ICMAUS framework is founded on principles of Minimum Length Encoding mentioned above. The framework is intended as an abstract model of any natural or artificial system for computing or cognition.

In broad terms, the framework is an incremental process not unlike the well-known and widely-used LZ algorithms for IC (PkZip, WinZip etc). The system is intended to receive raw (or New) data from the environment, to compress those data as much as possible and store them in a steadily growing repository of Old information. Compression of New is achieved by matching New against itself and against patterns already stored in Old, unifying those parts that match (thus achieving the effect of recognition) and storing the parts that do not match (which may be seen as an element of learning).

The main differences between the ICMAUS framework and the LZ algorithms are the provision of mechanisms to achieve a relatively thorough search of the space of alternative unifications, the ability to find good partial matches between patterns, and the ability to create multiple alignments of the kind that will be described.

### 3.1 Information can be compressed and redundant at the same time

Paradoxical as it may seem, the idea that the workings of computers and brains may be founded on IC is not in conflict with the uses of redundancy in information to reduce errors or speed up processing.

It is widely accepted that databases should minimise redundancy, as far as practicable. If, for example, the name, address etc of a given person appears two or more times in a database, then updating of the information becomes more complicated than if there is only a single record, and there are risks of introducing inconsistencies. Likewise, as we noted earlier, it would be very inconvenient if, each time we encountered a given person, we made a new mental record of that person without any integration with previous records. The process of recognising people and other entities may be seen to be largely a process of compressing information \[Watanabe, 1972\].

However, it is standard practice to keep backup copies of databases and other computer information to guard against catastrophic loss of that information. And multiple copies of databases may speed up processing (e.g., mirror copies of web sites). Likewise, it seems very unlikely that evolution would have endowed us with a cognitive system that allows us to keep only one mental copy of our hard-won knowledge. It seems very likely that we will have multiple copies of our knowledge to protect us against the risk of losing it. And those copies may also have a role in speeding up processing.

In general, the ICMAUS proposals are entirely compatible with the idea that computers and brains may keep multiple (redundant) copies of stored knowledge.

### 3.2 Representation of knowledge

Within the ICMAUS framework, all kinds of information and knowledge are to be expressed as arrays or patterns of atomic symbols in one or more dimensions.888In work to date, the focus has been on one-dimensional patterns but it is envisaged that, at some stage, the concepts will be generalised to patterns in two or more dimensions. A one-dimensional array of symbols can, of course, be described as a ‘sequence’ or ‘string’. However, the term pattern will normally be favoured as a reminder that the framework is intended eventually to accommodate higher-dimensional arrays. The system may also store alignments amongst those patterns.

The main motivation for adopting this very simple, uniform format for knowledge (echoing the adoption of production systems in Soar) has been to facilitate the manipulation and integration of diverse kinds of information within a uniform processing environment. It is evident that all kinds of ‘raw’ information (speech, music, pictures, diagrams etc) can be stored as arrays of atomic symbols (e.g., ‘0’ and ‘1’) in one or more dimensions. An important aim of the research has been to see whether or how, within a single framework, this very simple format would support other kinds of representation such as grammars, trees, class hierarchies and so on, without the need for specialised processing for different kinds of representation. A selection of examples is shown below.

Another motivation for adopting a simple, uniform format for all kinds of knowledge, with uniform mechanisms for processing knowledge, is that such a scheme is more likely to be compatible with mechanisms in neural tissue than a more heterogeneous system.999Although there is clearly diversity in the organisation and functioning of different parts of the brain and nervous system, it seems likely that there is also an underlying uniformity about the way information is organised and processed in neural tissue. It is this hypothesised underlying uniformity that is the focus of interest in this research. This is considered briefly in Section 3.7, below.

Within each pattern, each symbol is merely a ‘mark’ that can be matched in a yes/no manner with other symbols—it has no ‘hidden’ meaning. Thus, for example, arithmetic symbols like ‘+’ or ‘$`\times `$’ may be used in ICMAUS patterns but they would not have their normal meanings (‘add’ and ‘multiply’). Any meaning that may attach to a given symbol is to be derived from its context of other symbols and not via some extrinsic process of interpretation.101010The principle that symbols should have no hidden meanings has been slightly bent in current models. In the SP61 model, a distinction has been made, within each pattern, between ‘identification’ symbols that identify the pattern and ‘contents’ symbols that represent the substance of the pattern. This distinction may be regarded as part of the mechanism by which the system manages its knowledge. As such, it is rather different from meanings associated with symbols like ‘+’ or ‘$`\times `$’ which are part of the knowledge itself.

The ‘granularity’ of symbols in the ICMAUS framework is undefined. Symbols may be used to represent very fine-grained details of a body of information (e.g., binary digits) or they may be used to represent relatively large chunks of information.

Although concepts from mathematics, logic or related disciplines such as theoretical linguistics cannot be used directly in ICMAUS representations, it is anticipated that such constructs may be modelled within the ICMAUS framework (as described in Section 5, below). Even such seemingly basic constructs as ‘variable’ or ‘negation’ are excluded from the ICMAUS framework. But it is possible to model these constructs within the framework, as we shall see.

### 3.3 Multiple alignment

In bio-informatics, a ‘multiple alignment’ is an arrangement of two or more symbol sequences, one above the other, so that, by judicious stretching of sequences where appropriate, symbols that match each other from one sequence to another are arranged in vertical columns. A ‘good’ alignment is one with a relatively large number of matching symbols. This kind of analysis, applied to sequences of DNA bases or amino acid residues, can be helpful in elucidating the structure, function or evolution of the corresponding molecules.

In the ICMAUS scheme, this idea has been adapted in the following ways:

* One of the patterns is designated ‘New’ and the others are ‘Old’.
* A ‘good’ alignment is one which allows the New pattern to be encoded economically in terms of the Old patterns, as will be explained.
* By contrast with multiple alignments in bio-informatics, any one pattern may appear two or more times in one alignment. As will be explained (Section 5.1.1), this is not the same as allowing two or more copies of a pattern to appear within an alignment.

These points are illustrated and further explained in the examples presented throughout the article.

### 3.4 The SP61 computer model

The ICMAUS framework is partially realised in the SP61 computer model, described most fully in Wolff . Source code for the model has now been released under the terms of the GNU General Public License and may be obtained (with the executable code) from www.informatics.bangor.ac.uk/$``$gerry/sp\_summary.html.

The model does not attempt any learning: it is designed to process a New pattern and to compress it, as far as possible, in terms of previously-stored Old patterns, forming multiple alignments in the course of this processing. All the alignments shown in this article are output from the SP61 model.

With regard to the application of MLE principles in the SP61 model, the size of $`G`$ does not vary because the model is not attempting any learning. This means that the process of seeking to minimise $`(G+E)`$ can be reduced to a process of seeking to minimise $`E`$.

At the core of the SP61 model is a process for finding full matches between patterns or good partial matches Wolff . The process is a refined version of dynamic programming \[see, for example, Sankoff and Kruskall, 1983\] with advantages compared with standard methods: it can process patterns of arbitrary length without excessive demands for memory, it can find two or more alternative alignments for any given set of patterns, and the thoroughness of searching can be controlled by parameters.

Within the SP61 model, the matching process is applied repeatedly so that the system can build up the two or more ‘levels’ of each multiple alignment in a pairwise manner. An outline of the model is presented in Figure 1. In this description, ‘unification’ of an alignment means collapsing each column of matching symbols into a single symbol so that the whole alignment can be treated as a simple sequence of symbols.

In operation 1.2 in Figure 2 each alignment is evaluated in terms of IC. From each alignment, a ‘code’ can be derived as explained in Section 4.2, below. This code is a compressed representation of the New pattern in the alignment. The ‘compression score’ for an alignment is $`N_rN_e`$, where $`N_r`$ is the number of bits needed to express the New pattern in its ‘raw’, unencoded state, and $`N_e`$ is the number of bits needed to express the encoded form of the New pattern.

Adjustments are also made to allow for ‘gaps’ in alignments—sequences of one or more unmatched symbols. Alignments with many gaps or large ones have lower scores than alignments with gaps that are few and small. Details of how alignments are scored are given in Wolff .

#### 3.4.1 Computational complexity

Notwithstanding the astronomically large search spaces that are the rule for most multiple alignments, the heuristic techniques used in the SP61 model mean that its computational complexity is within acceptable polynomial limits. In a serial processing environment, the time complexity is estimated to be O$`(log_2n\times nm)`$ where $`n`$ is the length of the pattern in New (in bits) and $`m`$ is the sum of the lengths of the patterns in Old (in bits). In a parallel processing environment, it is estimated that the time complexity would be O$`(log_2n\times n)`$, depending on how well the parallelism is applied. The space complexity in both types of processing environment is estimated to be O$`(m)`$.

### 3.5 The SP70 computer model

SP70 is a successor to the SP61 model designed to achieve unsupervised inductive learning by adding New patterns (or parts of them) to Old, creating appropriate ‘codes’ (as described below), and sifting out ‘good’ patterns from ‘bad’ ones (in accordance with MLE principles). This model is able to abstract plausible grammars from appropriate data but more work is needed to realise the full potential of the model in this area.

Incidentally, the method of scoring alignments in SP70 does not require the adjustment for gaps required in SP61 (described in Section 3.4, above). This is because SP70 responds to gaps by creating new patterns, each with its own code symbols, and adding these patterns to Old. The newly-created code symbols can be used for scoring alignments containing gaps.

An outline of the model is given in Section 8.1. A relatively full description of the current version may be found in \[Wolff, 2002c\].

### 3.6 Information compression and probabilities

There is an intimate connection between IC and concepts of frequency, probability and probabilistic inference \[Solomonoff, 1964, 1986, 1997, Chater, 1996, 1999\]. Compression techniques like Huffman coding and Shannon-Fano-Elias coding \[see, for example, Cover and Thomas, 1991\] are founded on concepts of probability. And estimates of absolute and relative probability may be derived from measures of compression.

Thus the ICMAUS framework, as an expression of IC, is fundamentally probabilistic. For this reason, it can support probabilistic inferences of various kinds, as outlined in Section 7, below.

Each pattern in Old is assigned a frequency of occurrence in some domain and, from these values, SP61 can calculate an absolute probability for each alignment, relative probabilities for sets of alternative alignments and probabilities for inferences that may be drawn from alignments.111111In SP70, the frequencies of patterns are derived from the learning process. The methods of calculation are described in Wolff \[1999b\].121212In brief, the absolute probability of any alignment is calculated as $`p=2^L`$, where $`L`$ is the length, in bits, of the code derived from the alignment as outlined in Section 4.2. For any given set of $`n`$ alternative alignments, $`a_1\mathrm{}a_n`$, where each alignment provides a match for a given set of symbols from New, the relative probability of the $`j`$th alignment may be calculated as $`r_j=p_j/_1^np_i`$. Probabilities of patterns and symbols within alignments may be derived from these relative probabilities.

### 3.7 Symbolic and connectionist processing

Although the framework has a symbolic flavour and is currently implemented as an ordinary software model, the framework is intended to express abstractions at a higher level than the distinction between symbolic and connectionist models.

It seems possible that the framework could be realised using connectionist mechanisms. Each pattern could perhaps be realised as a Hebbian ‘cell assembly’ while each symbol might be realised either as a single nerve cell or as a small cell assembly. Detailed discussion of these possibilities is outside the scope of the present article. Current thinking in this area is described in Wolff \[2002b\].

## 4 Natural Language Processing

Figure 3 shows how the sentence ‘s i x o f t h e m d o’ (that is presented to the system as New) can be aligned with patterns (in Old) representing grammatical structures.131313The grammatical patterns in Old are intended to represent knowledge that has been accumulated by the system as a result of learning. In SP70, the system builds these kinds of patterns for itself. But because SP61 does not attempt learning, the patterns are simply given to the system at the start of processing. By convention in this research, New is always shown in the top row of each alignment with patterns from Old in the rows underneath. The order of the rows below the top row is entirely arbitrary and has no special significance.141414This example and others in this article have been deliberately chosen to be relatively simple. This is partly for the sake of clarity in exposition and partly because complex alignments can be difficult to display within the confines of the printed page. As already indicated (Section 3.4.1), the computational complexity of the model is acceptable. The model readily produces more complex alignments where appropriate. Relatively elaborate examples of multiple alignment may be found in Wolff .

In the alignment, most of the patterns representing grammatical structures are similar to rules in a context-free phrase-structure grammar (CF-PSG). For example, the pattern ‘S NP #NP V #V #S’ expresses the idea that a (simple) sentence is composed of a noun phrase followed by a verb. In a CF-PSG, this would be expressed by a rule like ‘S $``$ NP V’. The main differences between the two representations are that the patterns do not contain rewrite arrows and that each structure is normally referenced by an initial symbol (e.g., ‘NP’) and a termination symbol (e.g., ‘#NP’).

In the pattern ‘S NP #NP V #V #S’, each pair of symbols ‘NP #NP’ and ‘V #V’ functions as a ‘variable’ that can receive an appropriate value, as shown in the alignment in Figure 3.

### 4.1 Discontinuous syntactic agreements

If we ignore row 8, the alignment in Figure 3 maps fairly directly onto the kind of parsing one would obtain with a CF-PSG. That kind of parsing expresses the division of the sentence into ‘chunks’ of structure such as phrases and words but it does not show the kind of dependency or ‘agreement’ that exists between the number of the subject (singular or plural) and the number of the verb. This kind of agreement is ‘discontinuous’ in the sense that it can bridge arbitrarily large amounts of intervening structure.

This aspect of the structure of natural languages has, for several years, been handled quite well by various grammatical systems including Transformational Grammar, Definite Clause Grammars \[Pereira and Warren, 1980\], FAPR \[described in Gazdar and Mellish, 1989\] and others.

Figure 3 illustrates an alternative way in which syntactic agreements may be expressed which is, as far as I can ascertain, significantly different from any existing system. The agreement between the plural subject (‘s i x’) and the plural verb (‘d o’) is expressed in row 8 of the alignment in a relatively simple and direct manner with the pattern ‘S PL NP Np Q Vp #S ’. The symbols ‘S’ and ‘#S’ serve to tie this pattern into the main sentence pattern; ‘PL’ at the beginning marks the sentence as plural (and has a use which is described shortly); the symbols ‘Np’ and ‘Vp’ express the connection between the plural noun at the beginning of the sentence and the verb at the end; and the symbol ‘Q’ is needed to show that the ‘Np’ in this plural pattern refers to the noun before the qualifying phrase, not the plural noun (‘t h e m’) within that phrase.

More elaborate examples of this kind of parsing by multiple alignment may be found in Wolff , including one example that shows overlapping patterns of number dependency and gender dependency in French, and another showing the interesting pattern of interlocking dependencies in English auxiliary verbs.

### 4.2 Encoding of New in terms of patterns in Old

Each of the Old patterns in Figure 3 contains symbols that may be used as an identifier or ‘code’ for the pattern. For example, the pattern ‘N PL 0 t h e m #N’ may be coded using the symbols ‘N PL 0 #N’. These code symbols provide the means of expressing New in a relatively succinct form in terms of the Old patterns in the alignment.

Looking at the alignment, one might think that relatively large numbers of code symbols would be needed to encode the whole sentence. But many of the code symbols (e.g., ‘N’ and ‘#N’) merely serve to tie patterns together within the alignment and do not need to be included in the encoding of the sentence. In an example like the one shown in Figure 3, a code for the sentence may be constructed by selecting the symbols in the alignment that are not matched to any other symbol. In this example, the code created in this way is ‘PL 1 2 Np 0 2’. As we shall see (next), this code can be used to reconstruct the original sentence.

### 4.3 Production of language

An interesting feature of the ICMAUS framework (and the SP61 model) is that, without any modification, it can support the production of language as well as the parsing of language. This can be done by replacing the sentence in New with an encoding of the sentence as just described. With this substitution, the best alignment found by SP61 is shown in Figure 4.

If this alignment is unified, and if we ignore the code symbols in the unified pattern, we obtain the words of the original sentence in their correct order. In effect, the system achieves the apparent paradox of ‘decompression by compression’. A relatively full discussion of this point and how the apparent paradox is resolved may be found in Wolff .

Notice how the inclusion of the single symbol ‘PL’ in the encoding of the sentence eliminates the need to include the two symbols ‘Np’ and ‘Vp’. This is how patterns like the one shown in row 8 of the two alignments can contribute to IC.

### 4.4 Ambiguity

It should be emphasised that SP61 normally forms several alternative alignments for a given set of patterns, each one with its own compression score. Amongst these alternatives are many that look, intuitively, wrong. Almost always, the one with the highest score (as in Figure 3) is also the one which is, intuitively, fully correct or most nearly correct. Where there is syntactic ambiguity, SP61 will normally deliver two (or more) alignments with relatively high scores.

### 4.5 Integration of syntax and semantics

The way in which the ICMAUS framework might support the integration of syntax and semantics has not yet been examined in any detail. However, as was noted above, the very simple format for knowledge that has been adopted was chosen deliberately with the aim of facilitating the representation of diverse kinds of knowledge and their integration.

Examples presented below show how the framework can support aspects of non-syntactic knowledge such as class hierarchies with inheritance of attributes (Section 6.2) and polythetic categories (Section 6.3).

## 5 Computing, Mathematics and Logic

Up until the 1940s, ‘computing’ was something done almost exclusively by people. In those days, it would have seemed entirely natural to find common ground between the psychological processes involved in computation and other aspects of human cognition. Indeed, a consideration of the elements of human computation provided part of the inspiration for Alan Turing’s brilliantly-conceived ‘Universal Turing Machine’. And of course George Boole regarded mathematical theories of logic and probability as being founded on “Laws of Thought”. The ICMAUS proposals may be seen as an extension of these lines of thinking.

In general, the ICMAUS framework is probabilistic (Section 3.6). Given appropriate input, it is capable of finding good partial matches between patterns (illustrated in Section 6, below) and it is typically able to find two or more alternative alignments for any given set of patterns in New and Old. But constraints may be applied or the focus may be narrowed to consider only those alignments in which each symbol in New has been matched to at least one symbol in Old or to consider only the ‘best’ alignment for any given set of patterns. With these kinds of constraint, the system may be used to model ‘exact’ forms of calculation and reasoning.

### 5.1 Modelling a Universal Turing Machine and Post Canonical System

For about 60 years, the concept of a ‘Universal Turing Machine’ (UTM), and equivalent models such as the ‘Post Canonical System’ (PCS), have provided an abstract definition of the concept of ‘computing’. These models have been very successful but have little to say about things like learning, fuzzy pattern recognition, probabilistic reasoning and other topics in cognitive science and artificial intelligence. A motivation for developing the ICMAUS framework is to see whether or how it may be possible to plug this gap.

In Wolff \[1999b\], I have argued that the operation of a PCS may be interpreted within the ICMAUS framework. Since any UTM can be modelled by a PCS \[see Minsky, 1967\], we may also argue that the UTM can be modelled within the ICMAUS framework.

#### 5.1.1 Example: a PCS for the generation of unary numbers

A PCS comprises an alphabet of symbols, one or more ‘primitive assertions’ or ‘axioms’, and one or more ‘productions’. Figure 5 shows a PCS for the generation of unary numbers (where 0 = 0, 1 = 01, 2 = 011, 3 = 0111, and so on). Such a system can be run ‘forwards’ to create unary numbers or ‘backwards’ to recognise unary numbers.

This example can be modelled in the ICMAUS framework if we represent the axiom with the pattern ‘X a 0 #X’ and the production with the pattern ‘X b X #X 1 #X’. The symbols ‘X’ and ‘#X’ at the beginning and end of each pattern are code symbols needed to tie the patterns together in an alignment. The symbols ‘a’ and ‘b’ are code symbols needed for the scoring system in SP61. In the second of these two patterns, the pair of contiguous symbols ‘X #X’ may be read as “any number” and the whole pattern may be read as “a number comprises any number followed by ‘1”’. As in our example of parsing by multiple alignment (Section 4), a pair of contiguous symbols like ‘X #X’ can imitate the effect of a variable.

Figure 6 (a) shows the best alignment found by SP61 with the unary number ‘0 1 1 1 1’ in New and patterns for the axiom and the production in Old. The alignment confirms that the number conforms to the rules of unary arithmetic and thus, in effect, recognises the number as a unary number. Figure 6 (b) shows one of many alternative alignments produced by SP61 with ‘0’ in New and the same patterns in Old. Ignoring the ‘service’ symbols, the alignment contains the same symbols as before, in the same order. In effect, the system has produced the unary number ‘0 1 1 1 1’.

Notice that, in each of the two alignments shown in Figure 6, the pattern ‘X b X #X 1 #X’ appears several times. As was indicated in Section 3.3, there is an important difference between two or more appearances of a pattern in one alignment and two or more copies of a pattern in one alignment. In the first case, any one symbol in one appearance should not be matched with the corresponding symbol in another appearance-because this means matching the given symbol with itself. In the latter case, no such restrictions apply.151515A New pattern may be a copy of an Old pattern but, in general, Old should not contain multiple copies of any pattern.

#### 5.1.2 Simplicity and power

The main difference between the ICMAUS framework and earlier models is in the provision of a capability for finding good partial matches between patterns and the ability to build multiple alignments.

Although the ICMAUS framework is not as simple as the UTM or PCS models, it seems that the added complexity is more than offset by an increase in descriptive or explanatory power, particularly in areas of interest within cognitive science and artificial intelligence.

### 5.2 Mathematics and logic

This subsection presents three examples to illustrate the way in which the ICMAUS framework may be used to model concepts in mathematics and logic. Much fuller discussion and more examples may be found in Wolff \[2002a\].

#### 5.2.1 Adding two numbers

The four patterns shown in Figure 7 define a function that, in computer science jargon, is known as a ‘half adder’. In each row of the figure, the two digits between ‘A’ and ‘S’ are two one-bit numbers, the digit following the ‘S’ is the sum of those two numbers and the digit following the ‘C’ is the ‘carry out’ bit.

Figure 8 shows the best alignment found by SP61 with ‘A 0 1 S C’ in New and the patterns from Figure 7 in Old. In effect, the pattern in New is a request to add the digits ‘0’ and ‘1’. The result of the computation is the two unmatched digits in the alignment, ‘1’ for the sum and ‘0’ for the carry out bit. This is, of course, the correct result for the addition of ‘0’ and ‘1’.

In order to progress beyond the addition of two one-bit numbers, it is necessary to be able to combine functions so that the output of one function becomes the input of another. In order to add numbers containing two or more bits, the set of patterns shown in Figure 7 needs to be augmented so that it becomes a ‘full adder’ in which there is a ‘carry in’ bit as well as a carry out bit, and the ICMAUS framework needs to be applied recursively. This is explained, with an example from SP61, in Wolff \[2002a\].

The way in which the output of one function can become the input of another is shown next in the domain of logic.

#### 5.2.2 Combining logical functions

The first four patterns in Figure 9 define the XOR logical function: the first two digits in each pattern are the digits to be processed and the digit between ‘A’ and ‘#A’ is the result.161616The function is the same as the half adder but without the carry out bit.

The next two patterns in the figure define the NOT logical function: the first digit in each pattern is the input and the last digit is the output. The last pattern in the figure serves to combine the two functions so that the output of the XOR function can become the input to the NOT function.

Figure 10 shows the best alignment found by SP61 with the pattern ‘NOTXOR 0 1 A #NX’ in New and the patterns from Figure 9 in Old. As can be seen in the alignment, the result of the XOR computation (‘1’) appears between the ‘A’ and ‘#A’ columns in the middle of the alignment and this becomes the input to the NOT function. The overall result (‘0’) is shown between the ‘R’ and ‘#R’ columns in the alignment.

This example is not as general as conventional functions (where there is no need to match the name of the output area of one function with the input area of another) but it does, nevertheless, demonstrate how, within the ICMAUS framework, information can be passed from one function to another. It is anticipated that, when SP70 is more fully developed, it will allow greater generality in this area.

#### 5.2.3 Syllogistic reasoning

Consider the following text-book example of a modus ponens syllogism:

1. All humans are mortal.
2. Socrates is human.
3. Therefore, Socrates is mortal.

In logical notation, this may be expressed as:

1. $`x:human(x)mortal(x)`$.
2. $`human(Socrates)`$.
3. $`mortal(Socrates)`$.

In the ICMAUS framework, the first of these propositions may be expressed with the pattern ‘X #X human true $``$ mortal true’. In the manner of Skolemization, the variable ‘X #X’ in the pattern represents anything at all and may thus be seen to be universally quantified. The scope of the variable may be seen to embrace the entire pattern, without the need for it to be repeated. In keeping with the earlier remarks about “no hidden meanings” (Section 3.2), the symbol ‘$``$’ in the ICMAUS pattern serves simply as a separator between ‘human true’ and ‘mortal true’.

If this pattern is included (with other patterns) in Old and if New contains the pattern ‘Socrates human true $``$’ (corresponding to ‘human(Socrates)’ and, in effect, a request to discover what that proposition implies), SP61 finds one alignment (shown in Figure 11) that encodes all the symbols in New. After unification, this alignment may be read as a statement that because it is true that Socrates is human it is also true that Socrates is mortal.

## 6 Pattern Recognition and Best-Match Information Retrieval

The dynamic programming built into the SP61 model means that it can find good partial matches between a New pattern and one or more stored patterns. It can thus mimic the kind of ‘fuzzy’ pattern recognition and best-match information retrieval that is such a prominent feature of human perception and cognition (Section 6.1, next). The ability to form multiple alignments allows the modelling of class hierarchies with inheritance of attributes (Section 6.2) and the modelling of polythetic categories (Section 6.3).

### 6.1 Fuzzy matching

Figure 12 shows how the system can achieve fuzzy recognition of words. The figure shows, in descending order of their compression scores, the best five alignments found by SP61 with the misspelled word ‘i m f o r m t i x o n’ in New and a selection of correctly-spelled words in Old. Notice how the system can accommodate errors of omission, commission and substitution.171717Given that the last four alignments shown in Figure 12 each have 6 matching pairs of symbols, one might expect them all to have the same compression score. The reason their scores are different is that the compression score takes account of unmatched symbols (‘gaps’) in the alignments. Alignments with many gaps or large gaps have lower scores than those with gaps that are few and small.

Of course, this kind of pattern recognition is done quite well by systems for spelling checking and correction. What is different about the ICMAUS framework is the range of its capabilities (illustrated in this article), well beyond what can be achieved with any spelling checker. Another difference-not illustrated in this example-is that the SP61 model can bridge arbitrarily large gaps between matching sections, unlike any ordinary spelling checker.

If the kinds of capabilities already demonstrated can be generalised to the processing of patterns in two dimensions, they should prove useful in such tasks as visual pattern recognition and scene analysis where it often happens that patterns and objects are partially obscured, one behind another.

### 6.2 Class hierarchies and inheritance of attributes

Apart from allowing fuzzy recognition or retrieval of patterns, the ICMAUS framework allows recognition to occur through two or more levels of abstraction. Figure 13 shows a simple example where symbols for ‘sustains\_life’, ‘long’ and ‘crusty’ serve to identify an object as being a ‘baguette’ which, as such, is a form of ‘bread’, which is a form of ‘food’.181818Compared with the previous alignments in this article, the alignment shown in Figure 13 is rotated by $`90^o`$, with New in the left-most column and patterns from Old in the columns to the right. This arrangement allows the alignment to be fitted more easily on to the printed page. As a baguette, the object is ‘white’ as well as being ‘long’ and ‘crusty’. As bread, it is made of ‘flour’, ‘yeast’ and ‘water’. And as food, it is ‘organic’ (derived from living things) and contains ‘fat’, ‘protein’ and ‘carbohydrate’. The proportions of these substances (‘small’, ‘medium’, ‘large’) are recorded at the level of bread.

In the jargon of object-oriented design, the patterns for ‘food’, ‘bread’ and ‘baguette’ represent ‘classes’ of entity that are arranged in a ‘hierarchy‘ (with ’food’ at the top in this case and ‘baguette’ at the bottom). And ‘attributes’ at each level (e.g., ‘white’, ‘made of flour’, ‘contains protein’ etc) are ‘inherited’ by all the lower levels.

#### 6.2.1 Class hierarchies and inheritance of attributes in human cognition

Collins and Quillian  suggested that these principles operate in human perception and cognition, and their experimental results seemed to support the proposal. However, later experimental work cast doubt on the validity of those early results \[see, for example, Barsalou, 1992, p. 178 ff.\].

A full discussion of this issue is not possible here. Class hierarchies with inheritance of attributes are such powerful ideas that it seems unlikely that our brains would not exploit them. It is hard to believe, that, for every person we know, we keep a complete record of all their human attributes. It seems much more likely that knowing that someone is a person allows us to infer most of their attributes from our general knowledge of people.

Bearing in mind the high levels of parallel processing that operate in the brain, and bearing in mind the probability that our mental knowledge is compressed and redundant at the same time (Section 3.1), it is very difficult to draw sound conclusions from reaction times and similar experimental measurements.

### 6.3 Polythetic classes

People not only have an ability to recognise things despite errors of omission, commission and substitution (as in the example in Section 6.1) but it seems that many of our concepts express a ‘family resemblance’ or are ‘polythetic’, meaning that no single attribute need appear in all members of the class. Although, in a naïf view of the nature of concepts, this aspect of ‘natural’ categories may be puzzling, it can actually be modelled very simply by the use of re-write rules. For example, the following five rules: ‘1 $``$ 2 3’; ‘2 $``$ A’; ‘2 $``$ B’; ‘3 $``$ C’; and ‘3 $``$ D’, define the polythetic class ‘AC’, ‘AD’, ‘BC’, ‘BD’. Notice that none of the attributes ‘A’, ‘B’, ‘C’ or ‘D’ appear in all members of the class.

Given that these kinds of re-write rules can be modelled in the ICMAUS framework (as we saw in Section 4), it is clear that the framework can accommodate this aspect of human thinking.

## 7 Probabilistic reasoning

There is now a vast literature relating to probabilistic reasoning: standard parametric and non-parametric statistics; ad hoc uncertainty measures in early expert systems; Bayesian statistics; Bayesian/belief/causal networks; Markov networks; Self-Organising Feature Maps; fuzzy set theory and ‘soft computing’; the Dempster-Shaffer theory; abductive reasoning; reasoning with default values and nonmonotonic reasoning; autoepistemic logic, defeasible logic, probabilistic, possibilistic and other kinds of logic designed to accommodate uncertainty; MLE; algorithmic probability and algorithmic complexity theory; truth maintenance systems; decision analysis; utility theory; and so on.

No attempt can be made here to compare the ICMAUS proposals with these many alternatives. This section merely presents some examples suggesting how the framework can support probabilistic reasoning.

The example shown in Figure 13 illustrates the way in which inferences may be drawn from the kinds of multiple alignment formed by SP61. As in the examples shown in Figure 8, Figure 10 and Figure 11, the columns of any alignment that are not aligned with any of the symbols in New may be seen to be inferences that may be drawn from the alignment. Thus, in Figure 13, we can infer that the object that has been recognised contains fat, protein and carbohydrate, that it is made of flour, yeast and water, and so on.

### 7.1 Probabilistic ‘deduction’ and abduction

Inheritance of attributes, as just described, may be seen as a kind of ‘deduction’: knowing the class or classes to which an object belongs allows us to deduce attributes that have not been directly observed. Quote marks are used because this kind of inference lacks the formal properties of classical kinds of deduction. And these inferences are probabilistic because they do not need to be constrained in the kinds of ways indicated in Section 3.6.

Figure 14 shows a simple example of this kind of deduction. New (in the left column) records the fact that ‘Tibbs’ is a ‘mammal’ and the pattern in the third column describes the attributes of mammals. The alignment allows us to infer that “If Tibbs is a mammal, it is likely that he or she is warm blooded, furry and so on”.

An attractive feature of the ICMAUS framework is that it is just as easy to make ‘backwards’ abductive inferences as the kind of ‘forwards’ inference just shown. Figure 15 shows the two best alignments found by SP61 with ‘Tibbs warm\_blooded’ in New and the same patterns in Old as were used for Figure 14. From these alignments, we may conclude that, as a warm blooded creature, Tibbs might be either a bird or a mammal.

In the example shown in Figure 14, there is only one alignment that matches all the symbols in New. So the relative probability of the alignment (and inferences that may be drawn from the alignment) is 1.0. In the second example, where there are two alignments that match all the symbols in New, the relative probabilities calculated by SP61 are 0.59 (for Figure 15 (a)) and 0.41 (for Figure 15 (b)). Notice that these two values sum to 1.0 because, in the ‘closed world’ of information supplied to the system, birds and mammals are the only kinds of warm-blooded animal.191919In this case, it seems also to be true of the ‘real’ world that birds and mammals are the only warm-blooded kinds of creature. But, like any cognitive system (natural or artificial), there is no guarantee that stored knowledge will be an accurate reflection of the real world.

### 7.2 Chains of inference and other compound inferences

Figure 13 shows how the system can support inferences through two or more levels. Similar ‘chains’ of inference can be modelled if Old contains patterns representing ‘if … then’ associations like ‘smoke fire’, ‘night day’, ‘black\_clouds rain’ etc.

A very simple whodunit example is shown in Figure 16 (a) where New (in the left column) records an association between a ‘suspect’ and a particular ‘motive’, whilst Old contains, inter alia, a pattern (in the second column) recording an association between the ‘motive’ and the ‘crime’, a pattern (in the third column) recording the fact that the crime was committed at a particular place (‘scene1’) and at a particular time (‘time1’), and a pattern (in the fourth column) recording the fact that the suspect was in the same place at the same time. The entire alignment may be seen as a chain of inference suggesting that the suspect may have committed the crime.

Figure 16 (b) shows a similar example of ‘means-ends analysis’: finding a (not very good) railway route from London to Edinburgh.

Readers will notice that, in these examples and others in this article, the order of symbols in each pattern is critical. If, in the second column of Figure 16 (a), the order of ‘crime’ and ‘motive’ had been reversed, then the system would not have been able to complete the alignment. The links in Figure 16 (b) are directional: the pattern ’Manchester York’ means there is a train from Manchester to York but leaves unspecified whether or not there is a train in the other direction.

Bi-directional links could, of course, be supplied explicitly. However, the redundancy in that solution can be avoided if we adopt an arbitrary order for symbols in all the patterns (e.g., alpha-numeric) and avoid clashes between symbols by tying them into a ‘framework’ pattern like the one shown in the third column of Figure 17. Each symbol (other than the symbols used in the framework) has its own slot in the framework so that it does not interfere with other symbols.202020It should be clear that bi-directional railway journeys could be accommodated in a similar way.

In this second whodunit scenario, New records the fact that the ‘accused’ was seen with ‘matches’ near ‘the\_barn’ and that ‘smoke’ was seen at about the same time. The patterns from Old that have been tied into the alignment include ones showing:

* The fact that the barn was destroyed (column 2).
* The well-known association between smoke and fire (column 4).
* That the accused had petrol (column 5).
* The association between fire, matches and petrol (column 6).
* The fact that fire destroys things (column 7).

It should be clear from the examples in this section that, in general, the ICMAUS framework can accommodate arbitrary networks and trees represented by sets of patterns. It may thus be used in other applications where these kinds of representation are appropriate.

### 7.3 Nonmonotonic reasoning and default values

It has been recognised for some time that, by contrast with classical logic, everyday human reasoning allows us to modify conclusions in the light of new information. We may, for example, infer that Tweety can fly because Tweety is a bird but revise this conclusion if we subsequently learn that Tweety is a penguin \[see, for example, Ginsberg, 1994, Antoniou, 1997\]. The ICMAUS framework provides a means of modelling this kind of ‘nonmonotonic’ or ‘defeasible’ style of reasoning.212121Owing to over-exposure in the literature, Tweety is suffering from nervous exhaustion and will, accordingly, be replaced in the following example by a loaf of bread!

In the example illustrated in Figure 13, the colour of a baguette was given unambiguously as ‘white’. Instead of specifying the colour directly in this way, we can replace the symbol ‘white’ with a pair of symbols ‘colour #colour’ (functioning as a variable for the colour for the loaf, unspecified as yet) and add a new pattern to Old, ‘standard baguette colour white #colour #baguette #standard’, that says, in effect, that the default value for the colour of a standard baguette is ‘white’. In addition, we may add the pattern ‘special baguette colour brown #colour #baguette rustic #special’ to Old that says, in effect, that there is a special ‘rustic’ subclass of baguette where the colour is ‘brown’.

Figure 18 shows the three best alignments formed by SP61 with the same symbols in New as before and with modifications to Old as described (and, for the sake of simplicity, without the details of fat, protein and carbohydrate).

From the first of these alignments, we may infer merely that the unknown object is a baguette and that its colour is unspecified. From the second alignment (that contains the first alignment), we may infer that the colour of the baguette could be ‘white’. And from the third alignment (which also contains the first alignment), we may infer that that the colour could be ‘brown’.

For these alignments, SP61 calculates probabilities of the inferences that may be drawn from the alignments. In this example, the calculated relative probability that the unknown object is a ‘baguette’ is 1.0, and the values for ‘white’ and ‘brown’ are 0.55 and 0.45, respectively.

If we now add the symbol ‘rustic’ to the symbols in New, only one alignment is formed that encodes all the symbols in New. This is shown in Figure 19. Notice how, with this additional information, the default colour for a baguette is overridden and we learn that, as a ‘rustic’ baguette, the colour of the loaf is ‘brown’. And because there is only one alignment that encodes all the symbols in New, the relative probability of ‘brown’ is 1.0.

These examples illustrate the way in which inferences made by the system may be modified in the light of new information, in the manner of nonmonotonic reasoning.

### 7.4 Other kinds of probabilistic inference

Apart from the kinds of probabilistic reasoning described above, the ICMAUS framework lends itself to at least two other forms of inference where probabilities have a role:

* Geometric Analogy Problems. Given the translation of geometric forms into the kind of one-dimensional patterns currently required for SP61, it is possible to solve geometric analogy problems of the form ‘A is to B as C is to ?’, with a choice of four possibilities for ‘?’. In essence, these kinds of problems can be understood as a search for good partial matches between patterns.
* Explaining Away ‘Explain Away’. If we receive a phone call at work to say our burglar alarm has gone off, we are likely to assume there has a been a break in. However, if, at about the same time, we hear on the radio that there has been an earthquake, and if we know that the burglar alarm is sensitive to earthquakes, then we will probably assume that the earthquake is the explanation of why the alarm went off \[Pearl, 1988\]. This kind of ‘explaining away’ can be modelled by SP61 in a manner that is somewhat similar to the example of nonmonotonic reasoning, above. As with the previous example, the addition of new information (learning that an earthquake has occurred in this example) can change radically what kind of alignment of patterns achieves the most compression of the information in New.

Details of these examples may be found in Wolff \[1999b\].

## 8 Unsupervised Inductive Learning

As was noted earlier, this entire programme of research is based on earlier work on unsupervised inductive learning of language (Section 2), and the overall ICMAUS framework is designed to accommodate learning (Section 3). Most of the work to date has concentrated on areas other than learning but, as we noted in Section 3.5, the SP70 model has now been developed as a successor to SP61, designed as a full realisation of the ICMAUS framework, including unsupervised inductive learning. This section outlines how the SP70 model works. A relatively full description of the current version of SP70 is presented in Wolff \[2002c\].

Imagine a new-born child listening to other people talking, either to the child directly or to each other. If ICMAUS principles apply, then each ‘New’ portion of speech will be encoded as far as possible in terms of what is already stored. In accordance with empiricist thinking about language learning, we shall suppose that, initially, the child has no knowledge of language patterns. Thus each New portion of speech cannot be encoded in terms of anything else and is simply stored ‘as is’. After a time, however, as the child’s brain gradually accumulates a collection of these speech patterns, new possibilities for economical encoding begin to appear.

Let us suppose that (the spoken equivalent of) ‘i t s b e d t i m e n o w’ is already stored. Then, at some point, the child may hear something like ‘i t s p l a y t i m e n o w’. Looking for matching patterns, the child finds an alignment like the one shown at the top of Figure 20. By adding ‘code’ symbols at appropriate points, the child may convert the alignment into a fragment of ‘grammar’, something like the patterns shown in the bottom part of the figure. If patterns are stored in the brain as Hebbian cell assemblies, it is not too hard to imagine additional cells being added to each assembly to serve as identifiers or codes for the assembly.

Even at this early stage, the system has identified two discrete words and, in accordance with the principles of distributional linguistics, it has even recognised an embryonic grammatical class of ‘qualifying’ words: ‘play’, ‘bed’.

Notwithstanding nativist thinking about the nature of first language learning, there is now increasing recognition that distributional techniques can provide useful insights \[Redington and Chater, 1998, Redington et al., 1998\]. Demonstrations include my MK10 model of the learning of speech segmentation \[Wolff, 1975, 1977, 1980\] and my SNPR model of syntax learning \[Wolff, 1982, 1988, Langley and Stromsten, 2000\].

### 8.1 Features of SP70

This subsection indicates briefly some aspects of how the SP70 model works.

#### 8.1.1 Sifting and sorting

Many of the alignments found by SP70 are not be as ‘tidy’ as the example shown in Figure 20. It does not always happen that words or classes of words are picked out as cleanly as in the example. How can the system learn ‘clean’ grammatical structures in the face of the inevitable messiness in the matching of linguistic patterns?

A related question is how children can learn ‘correct’ grammars despite the fact that the language that they hear is often corrupted in various ways. That learning systems of the kind we have been discussing can cope with ‘dirty data’ has been demonstrated already with the SNPR model of syntax learning.

The SNPR model can succeed in the face of dirty data because it is constantly searching for relatively large, relatively frequent patterns. Since ‘errors’ in the raw data are, by their nature, relatively rare, they are sifted out and discarded in favour of the ‘good’ patterns in the data.

SP70 incorporates a process for ‘sifting and sorting’ through the patterns that have been derived from multiple alignments. This process compiles a set of alternative grammars, each one with a score based on MLE principles. The focus of interest is normally the best grammar produced by the program or the top two or three.

It is anticipated that, in future versions of the model, this sifting and sorting process will be applied at regular intervals as the system assimilates New information from its environment. At each stage, the store of Old pattern will be purged of all the patterns that are not part of the best grammar found by the system. In this way, the system may, in an incremental manner, build a store of Old patterns that are ‘good’ in terms of MLE principles.

#### 8.1.2 Building hierarchical structures

The toy example shown in Figure 20 suggests how structures may be created at one level of abstraction above the raw data. Although SP70 can abstract plausible grammars from appropriate data, a weakness of the current version is that it is not good at finding levels of abstraction that are intermediate between the highest and lowest levels.

It is anticipated that this problem can be overcome by a reorganisation of the SP70 model. Incidentally, although the SNPR model lacks the generality of the ICMAUS framework, it does have the capability to discover structure at multiple levels of abstraction.

#### 8.1.3 Generalization of grammatical rules and correction of overgeneralizations

Another important feature of the SNPR model is the way it can generalise grammatical rules and then correct over-generalisations despite the fact that, by definition, all kinds of generalisations, correct and incorrect, have zero frequency in the corpus from which the grammar is induced. This is achieved in a totally ‘unsupervised’ way: without correction by a ‘teacher’, without the provision of ‘negative’ examples, and without any kind of ‘grading’ of the material from which the system learns \[Gold, 1967\].

MLE principles appear to provide the key to distinguishing between ‘correct’ and ‘incorrect’ generalisations without external error correction: correct generalisations increase the compression that can be achieved while incorrect generalisations do the opposite.

SP70 already has an ability to make generalisations and to discriminate ‘good’ ones from ‘bad’ ones but further work is needed in this area.

### 8.2 Unsupervised inductive learning of semantic structures

The ICMAUS framework has been developed with the intention that it should be widely applicable, not confined narrowly to the syntax of natural language or some other circumscribed domain. One of the motivations for aiming for this kind of generality is that it should facilitate the learning of semantic knowledge structures and the integration of syntax with semantics.

Figure 21 is intended to suggest how the kinds of class hierarchy considered in Section 6.2 may be learned. The alignment at the top of the figure is intended to suggest how the features that are shared by swans and robins may be identified. These shared features (‘wings feathers beak flies warm\_blooded’) may be abstracted into a higher-level pattern describing the class ‘bird’ (‘%bd wings feathers beak flies warm\_blooded #bd’) and then the two original patterns may be reduced to ‘%sw swan %bd #bd long\_neck #sw’ and ‘%rb robin %bd #bd red\_breast #rb’.

As with the learning of syntactic structures, it is anticipated that, when SP70 is more fully developed, this kind of thing will be done recursively so that arbitrarily deep hierarchical structures may be built up. At some stage, there will be a need to integrate this kind of learning with the learning of syntactic structures to achieve the kind of knowledge that can serve the process of understanding language and the process of producing language from meanings.

## 9 Comparative Evaluation

Although there is no space in this article to evaluate the ICMAUS framework properly in relation to alternative systems, a few remarks are offered here about how the ICMAUS system compares with Hidden Markov Models (HMMs) and Bayesian networks.

HMMs have been popular for applications like speech recognition but “A major limitation \[for speech\] is the assumption that successive observations (frames of speech) are independent, and therefore the probability of a sequence of observations $`P(O,O_2\mathrm{}O_T)`$ can be written as a product of probabilities of individual observations …” \[Rabiner, 1989, p. 284\]. Also, “… the Markov assumption itself, i.e., that the probability of being in a given state at time $`t`$ only depends on the state at time $`t1`$, is clearly inappropriate for speech sounds.” (ibid.).

These limitations of HMMs, which are true for kinds of knowledge other than speech, do not apply to the ICMAUS framework. Dependencies amongst observations are expressed in the ICMAUS framework by the use of patterns and, as we saw in Section 4.1, these dependencies can bridge arbitrary amounts of intervening structure.

With appropriate design, HMMs have a memory for past events. But the same is true of the ICMAUS framework. In SP70, the repository of Old patterns is the cumulative memory of all the New patterns that have been received to date.

Bayesian networks have some attractive features for probabilistic reasoning and related applications \[see Pearl, 1988\] but they lack the flexibility of the ICMAUS framework for representing diverse kinds of knowledge. They are, for example, not well suited to representing the syntax of natural languages. By contrast, the ICMAUS framework provides a powerful means of handling such structures, including the subtle structure of interlocking dependencies in English auxiliary verbs \[Wolff, 2000\].

With regard to probabilities, each node in a Bayesian network must contain a table of transition probabilities and these can be quite complicated. By contrast, the ICMAUS framework stores all statistical information quite simply by attaching a frequency value to each stored pattern. This frequency information is used to calculate probabilities of particular contingencies as or when they are required.

## 10 Conclusion

This has been a relatively brief outline of the possibilities offered by the ICMAUS framework in understanding issues in cognitive science, artificial intelligence, and beyond. Despite the essential simplicity of the framework, it yields useful insights across a wide area.

A substantial programme of research has been needed to bring the ideas to their present stage of development. Now that they are relatively mature, I hope that other researchers will explore the several areas of application of the framework, will evaluate the framework and develop it further. As was noted earlier, the executable code and the source code for the SP61 model is now available and may be obtained from www.informatics.bangor.ac.uk/$``$gerry/sp\_summary.html.

## Acknowledgements

I am very grateful for extensive and constructive comments on earlier drafts of this article that I have received from Dr Emmanuel Pothos of the Department of Psychology, University of Edinburgh and Professor Richard Young of the Department of Psychology, University of Hertfordshire. I am also very grateful to Mr John Hornsby and Dr Chris Whitaker of the School of Informatics, University of Wales Bangor, for advice on mathematical issues. The article has also benefited from constructive comments and suggestions by an anonymous reviewer.

This article, with revision and expansion, is based on “Information compression by multiple alignment, unification and search as a framework for ‘intelligent’ computing” presented at the International ICSC Congress on Computational Intelligence: Methods & Applications (CIMA 2001, June 2001, Bangor) and “Information compression by multiple alignment, unification and search as a model of non-conscious intelligence” presented at the Symposium on Nonconscious Intelligence: from Natural to Artificial (AISB’01 Convention, March 2001, York).


format: text

text:
# Heavy Ions at LHC: Theoretical Issues

## 1 Introduction

The ALICE detector at LHC will be the next generation facility for exploring the features of hot nuclear matter. The goal is to learn more about the universe as it existed a few microseconds after the big bang. A very hot and dense phase of partons was present at these times. Later, a phase transition occurred during which hadronic matter as we know it today was formed. In the laboratory we try to create conditions that are similar to those in the early universe by colliding ultrarelativistic heavy ions, e.g. at the RHIC facility and — in a few years from now — at the LHC. The hope is to create a deconfined quark gluon plasma (QGP) for a few fm/$`c`$ and to study its properties. Fig. 1 shows our knowledge about QCD in the plane of temperature $`T`$ and baryon chemical potential $`\mu _B`$ with points that were tested in heavy ion experiments so far. Also the region covered by the LHC, which lies at small baryon chemical potential but at temperatures well above the phase transition temperature of $`T_c170`$ MeV  is shown.

The theoretical knowledge about the QCD phase transition so far is mainly coming from lattice QCD (see e.g.  for a review). It is possible to simulate the behavior of QCD along the $`T`$-axis for $`\mu _B=0`$. It is found that the scaled energy density $`ϵ/T^4`$ steeply increases at $`T_c`$. Since

$$ϵ=g_{\text{DOF}}\frac{\pi ^2}{30}T^4,$$
(1)
this can be understood by the rapidly rising number of degrees of freedom $`g_{\text{DOF}}`$ when the confined partons are liberated. Lattice QCD also shows that the deconfinement phase transition occurs together with a restoration of the spontaneously broken chiral symmetry. Recently calculations at finite $`\mu _B`$ became available . They predict a critical point on the phase transition line that is shown in Fig. 1.

## 2 Signatures of the phase transition

If a quark gluon plasma is created in a collision of two large nuclei, it eventually has to hadronize again. The detectors in our experiments can only measure the hadronic debris from this collision. A direct observation of the plasma is not possible. There has been a long discussion over the past 25 years what the possible signatures of a phase transition from a quark gluon plasma might be. We give a short (and probably incomplete) list of some of the more popular ideas:

* Indirect measurements of thermodynamical quantities like the latent heat of the phase transition.
* The enhanced production of strange particles.
* Modifications of hadron properties, like the mass and width of the $`\rho `$ meson, through the presence of hot nuclear matter.
* The detection of thermal photon or dilepton radiation from a thermalized QGP.
* The suppression of quarkonia like the $`J/\mathrm{\Psi }`$.
* The energy loss of fast partons in a QGP, the so called jet quenching.
* Fluctuations in net charge or baryon number.
* Collective vacuum excitations like the disoriented chiral condensate (DCC).

In the following we discuss some of these ideas.

### 2.1 Latent heat

One of the simplest approaches one can think of is to measure quantities that are thermodynamically related to the phase transition, like the latent heat. A very interesting observation has been made regarding the slope of hadron spectra. Hadron spectra at low transverse momenta — below several GeV/$`c`$, can be described phenomenologically by a blast wave fit . This assumes a thermalized spectrum with an effective temperature $`T`$. The spectrum is additionally boosted by a collective radial flow. The data collected for kaons at different energies seem to indicate that a plateau in the temperature was reached at SPS energies, while at higher RHIC energies the temperature is again rising. This could be interpreted as latent heat that is used to free the additional partonic degrees of freedom.

### 2.2 Strangeness enhancement

One of the classical signatures of the QGP is strangeness enhancement . Since the strangeness content of the colliding nuclei in the initial state is nearly negligible, all strange particles in the final state have to be generated in the collision. In purely hadronic matter, e.g. kaons and $`\mathrm{\Lambda }`$s have to be produced through hadronic channels. In a quark gluon plasma, $`s\overline{s}`$ pairs will be created. This is enhanced by the relatively small strange quark mass $`m_s<T_{\text{QGP}}`$ in the chirally restored phase. The strange quarks will then hadronize into strange hadrons and lead to higher yields compared to the hadronic scenario. This can already be seen at the CERN SPS .

### 2.3 $`J/\mathrm{\Psi }`$ suppression

It was argued by Matsui and Satz , that the disappearance of quarkonia states is a signal for the QGP. Lattice calculations show that the heavy quark potential is effectively screened in a plasma above $`T_c`$, so that $`c\overline{c}`$ bound states are melting . It is then unlikely that the $`c\overline{c}`$ will find together at hadronization. Instead, they will mostly end up in open charm states. However, already at RHIC energies charm quarks could be so abundant, that spontaneous recombination of $`c\overline{c}`$ pairs could occur if $`c`$ quarks thermalize in the medium . That would alter the suppression scenario and could even lead to a $`J/\mathrm{\Psi }`$ enhancement.

### 2.4 Jet quenching

Fast partons produced in hard QCD interactions between the two colliding nuclei have to travel through the hot and dense medium surrounding them. It was proposed very early by Bjorken , that these partons lose energy by interactions with the medium, see Fig. 2. This ”jet quenching” was studied in a series of theoretical papers over the last 10 years . The main process is the induced radiation of gluon bremsstrahlung by interactions with the hot nuclear matter. This results in a suppression of hadron production at $`P_T>2`$ GeV. Furthermore, since for strong energy loss the emission of high-$`P_T`$ hadrons is dominated by surface emission, the correlated backside jet nearly vanishes. This was confirmed at RHIC . Fig. 3 shows the nuclear suppression factor $`R_{AA}`$ for pions which is defined as the particle yield in Au+Au collisions normalized by the yield in $`p+p`$ collisions scaled by the number of binary nucleon-nucleon collisions. If a heavy ion collision were just a superposition of individual nucleon-nucleon collisions, $`R_{AA}`$ would be 1. In recent $`d+`$Au control experiments, where no QGP is expected to be produced, indeed, no suppression in the hadron yield and back-to-back correlations similar to $`p+p`$ collisions were found .

Theoretically, the effect of energy loss for hadron spectra can be described by medium modifications in the fragmentation function of a parton $`a`$ into hadron $`h`$ . This modification approximately corresponds to a rescaling of the variable $`z`$

$$D_{ah}(z,Q^2)\stackrel{~}{D}_{ah}(z,Q^2)D_{ah}(\frac{z}{1\mathrm{\Delta }E/E},Q^2).$$
(2)
Theory predicts that the energy loss is quadratically dependent on the length of the medium due to the so-called non-abelian Landau-Pomeranchuk-Migdal interference effect .

## 3 Surprising RHIC results

Besides the search for standard QGP signatures and the confirmation of long standing theoretical expectations, experimental results from RHIC have provided many surprises. In this section we want to discuss the anomalous baryon enhancement and the elliptic flow pattern found at RHIC.

It was widely assumed that hadron production at RHIC for $`P_T>2`$ GeV can be described by perturbative QCD. This seemed to work well for pions if all known nuclear corrections, like shadowing and energy loss, are taken into account. On the other hand, protons and antiprotons deviate from this behavior. In a scenario with partonic energy loss, the suppression of $`p`$ and $`\overline{p}`$ should be the same as for pions. Furthermore, pQCD would predict a ratio $`p/\pi ^0<0.2`$. RHIC results show that the $`p/\pi ^0`$ ratio is about 1 between 1.5 and 4.5 GeV/$`c`$, and that there is nearly no nuclear suppression in the yield of protons in this transverse momentum region . A similar behavior was found in the strangeness sector for $`\mathrm{\Lambda }`$s and kaons .

An important quantity that can be measured in heavy ion collisions is the azimuthal anisotropy. At nonzero impact parameter $`b>0`$, the overlap zone of the two nuclei is not spherically symmetric. The initial anisotropy translates into an anisotropy of the final hadron spectra. This can be quantified by an expansion of the spectrum into harmonics

$$\frac{dN}{2\pi P_TdP_Td\varphi }=\frac{dN}{2\pi P_TdP_T}\left(1+v_1(P_T)\mathrm{cos}\varphi +2v_2(P_T)\mathrm{cos}2\varphi +\mathrm{}\right).$$
(3)
The coefficient $`v_2`$ describes the elliptic anisotropy in the spectrum. $`v_2`$ has been measured in RHIC experiments and shows a surprising dependence on the hadron species. As a function of $`P_T`$ it rises and saturates above 2 GeV/$`c`$. The value of saturation is always larger for baryons compared to mesons . It is believed that at these and higher values of $`P_T`$ the mechanism for translating the initial anisotropy into a final one is again partonic energy loss. Partons going into a direction where the interaction zone is less extended will suffer less energy loss. However, this mechanism should be blind to the hadron species.

The results above suggest that the range of validity for leading twist perturbative QCD calculations only starts at higher transverse momentum. Instead, the baryon enhancement and the azimuthal flow pattern can be understood in a simple picture of parton recombination . In pQCD hadronization happens through fragmentation. A single parton with momentum $`p`$ splits into gluons and $`q\overline{q}`$ pairs that eventually form hadrons. One of these hadrons is then measured and has momentum $`P=zp`$, ($`z<1`$). The hadron spectrum is given by

$$E\frac{dN_h}{d^3P}=\underset{a}{}\underset{0}{\overset{1}{}}\frac{dz}{z^2}D_{ah}(z)E_p\frac{dN_a}{d^3p}$$
(4)
where $`dN_a/d^3p`$ is the spectrum of partons $`a`$ and $`p=P/z`$ is the parton momentum.

On the other hand, if phase space is already densely populated with partons, these can simply recombine to give mesons $`M`$ and baryons $`B`$

$$q\overline{q}M,qqqB,\overline{q}\overline{q}\overline{q}\overline{B}.$$
(5)
In this case, the momenta of the valence partons add up. Quantitatively this can be formulated in a coalescence formalism using hadron wave functions $`\varphi _h`$ in light cone coordinates . For a meson $`M`$ the spectrum can be written as

$$E\frac{dN_M}{d^3P}=C_M\underset{\mathrm{\Sigma }}{}𝑑\sigma \frac{Pu(\sigma )}{(2\pi )^3}\underset{0}{\overset{1}{}}𝑑xw_q(\sigma ;xP^+)\left|\varphi _M(x)\right|^2w_{\overline{q}}(\sigma ;(1x)P^+)$$
(6)
where $`C_M`$ is a degeneracy factor, $`w_q`$ and $`w_{\overline{q}}`$ are the phase space distributions of the recombining quark and antiquark respectively, $`x`$ is the momentum fraction of the quark in light cone coordinates and $`\mathrm{\Sigma }`$ is the hadronization hypersurface in Minkowski space.

It can be shown that recombination is always more effective than fragmentation for an exponential parton spectrum, but fragmentation will dominate at high $`P_T`$ for a parton spectrum in power law form. Furthermore, for an exponential parton spectrum $`w=e^{P^+/T}`$, we have

$$w_q(xP^+)w_{\overline{q}}((1x)P^+)=e^{P^+/T}$$
(7)
in the case of a meson $`M`$ and analogously

$$w_q(x_1P^+)w_q(x_2P^+)w_q((1x_1x_2)P^+)=e^{P^+/T}$$
(8)
in the case of a baryon $`B`$. $`P^+`$ here always denotes the large component of the hadron momentum on the light cone. Hence recombination naturally provides a ratio $`B/M1`$. We should add that the description of recombination given above is only valid if $`P^+`$ is much larger than $`\mathrm{\Lambda }_{\text{QCD}}`$ and the masses of the hadrons.

Fig. 4 shows the result of a calculation for charged hadrons at RHIC using recombination from a thermalized phase of constituent quarks with a temperature $`T=175`$ MeV and an average radial flow velocity $`v_T=0.55c`$ and fragmentation in a leading order pQCD calculation including energy loss. One can clearly see the two different domains of hadron production. Only above $`P_T=5`$ GeV/$`c`$ is leading twist pQCD a good description for hadron production. Below that recombination is important. Data on the $`p/\pi ^0`$ ratio in this momentum range are well reproduced by this calculation.

For the recombination of partons, one can derive a simple scaling law that connects the azimuthal anisotropy $`v_2`$ for partons $`p`$ and hadrons $`h`$

$$v_2^h(P_T)=nv_2^p(P_T/n)$$
(9)
where $`n=2`$ for mesons and $`n=3`$ for baryons. This scaling law which was recently confirmed by the STAR and PHENIX collaborations , can be considered as a new “ smoking gun” for the creation of a quark gluon plasma. The scaling law visualizes the anisotropic flow in the parton phase before hadronization.

## 4 What’s different at LHC?

At LHC lead nuclei will collide with a center of mass energy $`\sqrt{s}=5.5`$ TeV. This leads to a much higher initial energy density. Higher energy density and increased lifetime will make initial state effects less important, but will also enhance the role of the QGP phase over final state hadronic interactions. On the other hand, probes with very high transverse momentum, up to 100 GeV/$`c`$, will be available and it might be possible to measure jets . Also heavy $`c`$ and $`b`$ quarks are plentiful probes at this energy.

### 4.1 Saturation physics

The relevance of saturation of the nuclear wave function  has already been discussed at lower energies. It is clear that LHC will be the ideal testing ground for saturation physics. The basic idea is that the gluon distribution in a QCD bound state cannot continuously grow fast at small Bjorken $`x`$ without violating unitarity. At some point, gluon fusion will balance the growth. The scale at which the probability of gluon interactions in the nucleus wave function becomes of the order of one determines the saturation scale $`Q_s`$

$$\frac{xG_A(x,Q_s^2)}{\pi R_A^2}\frac{\alpha _s(Q_s^2)}{Q_s^2}1.$$
(10)
From this equation one obtains the scaling with the nuclear size $`Q_s^2A^{1/3}x^{0.5}`$. Starting from these assumptions various phenomenological consequences have been derived  for QCD at large $`\sqrt{s}`$. See e.g.  for an overview.

Saturation has also to be taken into account, when one of the fundamental questions is addressed: What are the particle multiplicities we can expect at LHC? This is very important for the detector design. Estimates have been given in  using perturbative QCD and saturation.

### 4.2 Jet quenching at the LHC

It is expected that the effect of jet quenching at LHC is even larger than at RHIC due to the higher energy density in the medium. Estimates depending on the produced particle multiplicity show that quenching factors of 10–30 can occur for pions at $`P_T=10`$ GeV . Nevertheless, hard QCD will be an important part of the heavy ion program at LHC. It might be possible to measure jets directly, as it is done in $`p+\overline{p}`$ and $`e^++e^{}`$ collisions. That eliminates the uncertainty coming from fragmentation functions in theoretical calculations and could be a valuable contribution to our understanding of energy loss in the medium .

### 4.3 Recombination at the LHC

The large nuclear suppression factor raises the question whether “soft” thermal physics will push its limits to even higher $`P_T`$ at LHC. Preliminary studies with recombination from a thermalized parton phase confirm this. Figs. 5,6 shows an estimate of $`\pi ^0`$ and $`p`$ spectra at LHC taking into account recombination and fragmentation . The energy loss used is in accordance with the estimates of Gyulassy and Vitev  and for the thermal parton phase a temperature $`T=175`$ MeV and radial flow $`v_T=0.75c`$ are assumed. The crossover between the recombination domain and the pQCD domain is shifted to 6 GeV/$`c`$ (from 4 GeV/$`c`$ at RHIC ) for pions and to 8 GeV/$`c`$ (from 6 GeV/$`c`$ at RHIC) for protons. Correspondingly the $`p/\pi ^0`$ ratio at LHC is also shifted to higher $`P_T`$, see Fig. 7.

### 4.4 Measurements of medium properties

Once partonic energy loss is established, one would like to measure properties of the QGP by using hard QCD probes. One sort of precision measurements could be photon-tagged jets or hadrons. For this one considers the back-to-back production of a parton and a photon, e.g. $`q+gq+\gamma `$ as shown in Fig. 8. Due to the weakness of electromagnetic interactions, the photon can leave the medium unaffected, while the outgoing parton will suffer from final state interactions. By momentum conservation the transverse momentum of the photon is equal to the initial momentum of the outgoing parton directly after the production. But the parton will suffer from energy loss before it can hadronize. By tagging a reference photon and looking at hadrons or jets at the opposite side, precision measurements of energy loss will be possible . The same measurement can be done with back-to-back production of a parton and a virtual photon, which then decays into a lepton pair .

Another promising idea is to measure induced photon radiation from fast partons interacting with the medium . It is characteristic for the Born cross sections for these processes, e.g.

$$q(\text{jet})+\overline{q}(\text{medium})g+\gamma \text{or}q(\text{jet})+g(\text{medium})q+\gamma ,$$
(11)
— see Fig. 9 — that they peak in forward and backward directions (in the center of mass frame). That means that the three-momentum of the photon is very close to one of the two initial momenta. If one restricts the measurement of the photon to large transverse momentum, say $`P_T>4`$ GeV/$`c`$, then the momentum of the photon will be that of the fast parton. This jet-photon conversion mechanism is another opportunity to measure the momentum of a fast parton in the plasma. This time the photon emission will take place while this parton is traveling through the plasma and, in order to obtain the photon rate, one has to integrate over the path of the parton. Therefore this measurement is sensitive to the evolution of density and temperature of the medium. It has been estimated that photons from this conversion mechanism are shining quite brightly at RHIC and LHC compared to other photon sources, cf. Fig. 10. Again, similar measurements are possible with dileptons instead of photons .

## 5 Summary

We have discussed several key issues of heavy ion physics. While we might already discover the quark gluon plasma at RHIC, it will be at LHC that we can systematically study its properties by making use of the the plentiful hard probes. Some important questions have to be addressed.

* How does gluon saturation work at small $`x`$?
* How exactly are fragmentation functions modified in the medium?
* How does the energy loss depend on the energy density?
* Are heavy quarks thermalized?
* What is the role of nuclear higher twist effects?

The LHC will be the ideal machine to provide answers.