Induction and AI

What's the next entry in this list?

$$ \text{B123A, A231B, B312A, A123B, } \ldots $$

If you feel very strongly that the next string should be $\text{B231A}$, then this is because you've recognized a pattern, even though this is most likely the first time you've seen this sequence. Once you've found the pattern, you then used it to predict the next string in the sequence.

Like many, I believe that this ability to recognize patterns is the hallmark of intelligence. In fact, most of the other abilities commonly associated with intelligence such as learning, planning, analogical reasoning, and so on, can be seen as either directly connected to or dependent upon our capacity for pattern recognition.

Pattern recognition and computation are intimately related to each other.

Computation is the process that takes a program $p$ as input and then mechanically generates a potentially infinite output sequence $x_1 x_2 \ldots$. Thus, if you can express unambiguously how to do a task, then computation will perform the exact task you've described. The Church-Turing thesis proposes that these mechanical processes are precisely those computable by a Turing machine (or any formalism that is equivalent to it, such as lambda calculus).

Pattern recognition can be regarded as the inverse process: given an input sequence $x_1 x_2 \ldots$ it finds a program $p$ (or a set of programs) that would mechanically compute said sequence. In other words,

$$ \text{PatternRecognition}(x) = \text{Computation}^{-1}(x). $$

In this sense, a pattern is a program. Programs are the most general way of specifying describing formal relationships of the parts within a whole. They encompass symmetries (and hence, the physical laws), arithmetic sequences, fractals, even the geometrical patterns within your carpet.

There's a connection between the aforementioned processes and logic. Logicians identify two distinct reasoning methods: deduction and induction.

Deduction is the method which yields inevitable conclusions based on given premises and rules. The archetypal example is that if you know “all humans are mortal” (premise) and “Socrates is a human” (premise), then you can unequivocally conclude that “Socrates is mortal” (necessary conclusion) through the use of a categorical syllogism (rule).

Induction: This method produces general hypotheses (rules & premises for instance) derived from specific observations. An example is observing that the sun has risen every day in recorded history and thus concluding that the sun will rise every day (a general rule, but not an absolute certainty). Another example would be to observe that “Socrates is mortal” and then conclude that this is because “all humans are mortal” and “Socrates is a human”, although the credence attributed to this hypothesis is arguably quite low given the anecdotal data.

(Logicians sometimes acknowledge other forms of reasoning, for instance abduction. I won't explore them separately here, as I believe they're subsumed by deduction and induction for our discussion.)

If we identify rules and premises with the information contained in a program, computation appears to correspond to a type of deduction restricted to processes that can be carried out through mechanical means. Induction, on the other hand, can be regarded as a process that finds rules and premises from conclusions. This suggests the following parallels:

$$ \begin{array}{ccc} \text{Logic} & & \text{Computer Science} \\ \text{Deduction} &\longleftrightarrow & \text{Computation} \\ \text{Induction} &\longleftrightarrow & \text{PatternRecognition?} \end{array} $$

That is, if we limit ourselves to processes that can be executed through mechanical means, deduction becomes computation. Would it be right to say that pattern recognition is just induction restricted to mechanical processes?

We've pointed out the connection to logic. Now we dig a bit deeper.

So far I've talked about computation and pattern recognition as processes, but I didn't specify what kind of processes they are. Answering this question will reveal that they are fundamentally different in nature.

The concept of computation, wherein a program is interpreted and executed, is intriguingly a program in its own right, i.e. it can be described with a finite amount of information, in spite of its universality. This profound insight is a cornerstone of computer science: Alan Turing proved that specific programs, now known as Universal Turing Machines (UTMs), are capable of running any given program. We're all familiar with them: they are today's programming language interpreters.

Given this understanding, one might wonder about the nature of the pattern recognition process. Since it is the converse of computation, can it be defined as a program too? In other words, can the core mechanisms of intelligence be encapsulated in a finite set of rules? Is there a fixed rule set capable of transforming any set of observations into a program that replicates them?