Lecture
Thinking beings are capable of exhibiting very complex forms of behavior, possessing a consciousness whose mechanisms we understand only very dimly. Consider, for example, how you plan a route for a trip across town in order to get a mass of errands done. In a poorly lit room you manage to make out the edges of objects and avoid bumping into them. You can concentrate on a conversation with one person at a noisy party where many people are talking at once. Not one of these tasks has a clear algorithmic solution. Route planning belongs to the class of NP-complete problems. Moving about in the dark implies making decisions on the basis of incomplete and fuzzy visual information. Picking out one person's speech from a multitude of conversations requires the ability to catch useful information amid noise and to filter the desired messages out of the general cacophony.
These and similar problems attract the attention of researchers in the field of artificial intelligence, who strive to improve our understanding of the human mind. In particular, intelligent systems are being created that imitate certain aspects of human behavior. Erman, Lark, and Hayes-Roth pointed out that "intelligent systems differ from traditional ones in a number of respects (not all of them mandatory):
Realizing even one of these requirements in a system is already no simple task. It is harder still to build an intelligent system for use in certain specific application areas, for example, in medical diagnosis and airline flight scheduling: such systems must, at a minimum, do no harm, and artificial intelligence knows practically nothing about common sense.
The successes of enthusiasts in this field have been somewhat exaggerated; nevertheless, artificial intelligence has yielded quite a few good practical ideas, in particular knowledge representation, the concept of the blackboard, and expert systems. This chapter examines approaches to creating an intelligent system for deciphering cryptograms based on the blackboard method, which models the human way of solving the problem to a sufficient degree. As we shall see, the methods of object-oriented design work very well in this area.
11.1. Analysis
Defining the boundaries of the problem domain
As stated in the sidebar, we intend to take up cryptanalysis - the process of transforming enciphered text into ordinary text. In the general case the process of decipherment is extremely complex and yields to even the most powerful scientific methods only with difficulty. There exists, for example, the DES encryption standard (Data Encryption Standard, a private-key encryption algorithm that uses numerous substitutions and permutations), which apparently is free of weak spots and is resistant to all known methods of breaking it. But our problem is considerably simpler, since we will limit ourselves to ciphers with a single substitution.
As a first step in the analysis, try to solve (honestly now, without looking ahead!) the following cryptogram, writing down each of your steps:
Q AZWS DSSC KAS DXZNN DASNN
Hint: the letter w corresponds to the letter v of the original text. Trying all possible variants makes no sense at all. Assuming that the alphabet contains 26 uppercase English letters, we get 26! (about 4.03x1026) possible combinations. Consequently, we must look for another method of solution, for example, using knowledge about the structure of words and sentences and making plausible assumptions. As soon as we exhaust the obvious solutions, we will make the most likely assumption and press on further. If it turns out that the assumption leads to a contradiction or into a dead end, we will go back and make another attempt.
| Requirements for the cryptanalysis system
Cryptography "studies methods of concealing data from outsiders". Cryptographic algorithms transform messages (the original text) into enciphered text (a cryptogram) and back again. One of the most widely used cryptographic algorithms (going back to the times of ancient Rome) is substitution. Each letter in the alphabet of the original text is replaced by another letter. For example, one may cyclically shift all the letters of the alphabet: the letter A is replaced by B, B by C, and Z by A. Then the following original text: CLOS is an object-oriented programming language turns into the cryptogram: DMPT jt bo pckfdu-psjfoufe qsphsbnnjoh mbohvbhf More often the replacement is made in a less trivial way. For example, A is replaced by G, B by J and so on. Consider the following cryptogram: PDG TBCER CQ TCK AL S NGELCH QZBBR SBAJG Hint: the letter C in this cryptogram corresponds to the letter O of the original text. The assumption that a substitution algorithm was used to encipher the text simplifies the problem substantially, since in the general case the process of decipherment will not be nearly so trivial. In the process of decipherment one has to use the method of trial and error, making an assumption about a substitution and considering its consequences. It is convenient, for example, to begin the decipherment with the assumption that the one- and two-letter words in the cryptogram correspond to the most commonly used words of the English language (I, a, or, it, in, of, on). By substituting these conjectured letters into other words, we can guess at the probable value of other letters. For example, if a three-letter word begins with the letter O, then it may be one of the words one, our, off. A knowledge of phonetics and grammar can also aid decipherment. For example, two identical letters occurring in a row can with very low probability mean qq. The presence of the letter g at the end of a word makes it possible to conjecture the presence of the suffix ing. At a still higher level of abstraction it is logical to assume that the word combination it is is more likely than if is. One must also take the structure of the sentence into account: nouns and verbs. If it turns out that a sentence has a verb but no noun associated with it, then the assumptions made earlier must be rejected and the search begun anew. Sometimes one has to backtrack, if an assumption that has been made comes into conflict with other assumptions. For example, we allowed that some two-letter word corresponds to the combination or, which subsequently led to a contradiction. In this case we must go back and try to use another variant for deciphering this word, for example, on. The requirements for our system: given a cryptogram, on the assumption that a simple substitution was used, find that substitution and (most importantly) recover the original text. |
Here is our solution, step by step:
1. Using the hint, let us replace w with v.
Q AZVS DSSC KAS DXZNN DASNN
2. The first word, consisting of a single letter, is probably A or I; let us assume that it is A:
A AZVS DSEC KAS DXZNN DASNN
3. The third word must contain vowel sounds, and it is likely that these are double letters. They cannot be UU or II, nor AA (the letter A has already been used). Let us try the variant EE.
A AZVE DEEC KAE DXZNN DAENN
4. The fourth word consists of three letters and ends in E, which looks very much like the word THE.
A HZVE DEEC THE DXZNN DHENN
5. The second word needs a vowel, and here only I, O, U will do (the letter A has already been used). Only the variant with the letter I gives a meaningful word.
A HIVE DEEC THE DXINN DHENN
6. One can find several four-letter words with the doubled letter E (DEER, BEER, SEEN). Grammar requires the third word to be a verb, so let us settle on SEEN.
A HIVE SEEN THE SXINN SHENN
7. The resulting sentence has no meaning, since a hive (HIVE) cannot have seen (SEEN) anything, which means that somewhere along the way we made a mistake. It appears that the choice of the vowel in the second word was wrong, and we have to go back, canceling the very first assumption - the first word must be I. Repeating all our other reasoning practically unchanged, we get:
I HAVE SEEN THE SXANN SHENN
8. Let us look at the last two words. The doubled letter S at the end does not give a meaningful value and has moreover already been used earlier, whereas LL does give a meaningful word.
I HAVE SEEN THE SXALL SHELL
9. From grammatical considerations it is obvious that the remaining word is an adjective. Analyzing the pattern S?ALL, we find SMALL.
I HAVE SEEN THE SMALL SHELL
Thus the solution has been found. Analyzing the solution process, we can make three observations:
The approach set out above is known as the blackboard method. It was first proposed by Newell in 1962, and was later used by Reddy and Erman in the Hearsay and Hearsay II speech recognition projects. The effectiveness of the method was confirmed, and it was used in other areas as well, including signal interpretation, three-dimensional modeling of molecular structures, pattern recognition, and planning. The method has shown good results in representing descriptive knowledge; it is more efficient in terms of memory and time compared with other approaches.
The blackboard is quite suitable for the role of a development environment (see Chapter 9). Let us now try to capture the architecture of this method in the form of a system of classes and mechanisms for their interaction.
The architecture of the blackboard metaphor
To explain the blackboard model, Englemore and Morgan used the following analogy with a group of people assembling the pieces of a jigsaw puzzle into the required picture:
Imagine a room with a large board, next to which stands a group of people holding pieces of a picture in their hands. The process is begun by volunteers, who place on the board the most "likely" pieces of the picture (let us suppose that they stick to the board). Next, each member of the group looks at the pieces remaining in his hands and decides whether there are any that fit the ones already on the board. Whoever finds a match walks up to the board and sticks on his piece. As a result, piece after piece takes its proper place. It does not matter in the process that one of the participants may have more pieces than another. The whole picture will be fully assembled without any exchange of information between the members of the group. Each participant activates himself and knows when he needs to join in the process. No order of approaching the board is established in advance. The joint behavior is regulated only by the information on the board. Watching the process demonstrates that it is sequential (one piece per approach) and opportunistic (when an opportunity arises, a piece is put in place). This differs substantially from strict systematicity, for example, from proceeding from the upper left corner and trying every piece in turn.
From Figure 11-1 it is clear that the method rests on three elements: the blackboard, a collection of knowledge sources, and a controller that manages these sources. Note that the following definition corresponds directly to the principles of the object approach. According to Nii: "The blackboard is needed in order to store data about the progress and state of the problem being solved, data that are used and produced by the knowledge sources. The blackboard contains objects from the solution space. These objects are grouped hierarchically by levels of analysis and, together with their attributes, form the vocabulary of the solution space".
Englemore and Morgan make this more precise: "the knowledge about the problem domain needed to solve the problem is divided among several independent sources. Each knowledge source tries to offer information useful for solving the problem. The current information from each source is placed on the blackboard and modified in accordance with the content of the knowledge. Knowledge sources are represented in the form of procedures, sets of rules, or logical inferences" [10].
Figure 11-1. The blackboard.
Knowledge sources depend on the problem domain. In speech recognition systems we may be interested in agents that supply knowledge about phonemes, words, and sentences. In pattern recognition systems they may be information about elementary structures of an image, such as junctions of lines and regions of uniform density, and, at a higher level of abstraction, objects belonging to a particular scene (houses, roads, fields, automobiles, and people).
In the general case, knowledge sources correspond to the hierarchical structure of the objects placed on the blackboard. Moreover, each source uses objects of one level of the hierarchy as input data, and as output it generates or modifies objects at another level. For example, in a speech recognition system the knowledge source about words watches the stream of phonemes (a low level of abstraction) in order to detect a word (a higher level of abstraction). The knowledge source about sentences may conjecture that a verb is needed here (a high level of abstraction) and check this conjecture by going through the list of possible words (a low level of abstraction).
These two approaches to searching for a solution are called, respectively, forward and backward chaining of reasoning. Forward chaining of reasoning makes it possible to pass from more particular assumptions to more general ones, while backward chaining, starting from some hypothesis, makes it possible to check that hypothesis by comparing it with known premises. This is why we characterized the control of the blackboard as opportunistic: depending on the circumstances, knowledge sources may activate either forward or backward chains of reasoning.
Knowledge sources, as a rule, consist of two components: a precondition and an action. A precondition is a state of the blackboard that is of "interest" to a particular knowledge source (potentially capable of activating it). For example, in pattern recognition a precondition might be the presence of a straight line (which may signify a road). The satisfaction of the preconditions causes the knowledge source to focus attention on a particular region of the blackboard, and then to bring into play the appropriate rules or procedural knowledge.
Under these conditions the order of activation is of no importance: if a knowledge source discovers data useful for solving the problem, it signals this to the blackboard controller; figuratively speaking, it raises its hand, showing that it wishes to do something useful. Of the several sources making such a gesture, the controller invokes the one that seems to it the most promising.
Analysis of the knowledge sources
Let us now return to the problem at hand and consider the knowledge sources useful for solving it. In building most knowledge-based applications it is best to sit down next to an expert in the problem domain and record the heuristics he uses. In our case we will have to try to decipher a certain number of cryptograms and note the features of the process of searching for solutions.
Proceeding in this way, we have identified thirteen knowledge sources relevant to our problem:
| ® Prefixes | The most commonly used beginnings of words (for example, re, anti, un). |
| ® Suffixes | The most commonly used endings of words (ly, ing, es, ed). |
| ® Consonants | Letters that are not vowels. |
| ® Directly known substitutions | Substitutions known to us a priori, before solving the problem. |
| ® Double letters | The letters most often doubled (tt, ll, ss). |
| ® Letter frequency | The probability of letters appearing in a text. |
| ® Legal strings | Permissible and impermissible combinations of letters (for example, qu and zg). |
| ® Pattern matching | Words matching a pattern. |
| ® Sentence structure | Grammar, including knowledge about noun and verb phrases. |
| ® Small words | One-, two-, three-, and four-letter words. |
| ® Solved | Whether a solution has been found or we have reached a dead end. |
| ® Vowels | Letters that are not consonants. |
| ® Word structure | The placement of vowels and the typical structure of nouns, verbs, adjectives, adverbs, prepositions, conjunctions, and so on. |
Proceeding from the object-oriented approach, all of these knowledge sources are potential candidates for the role of classes, on the basis of which objects are created that possess state (knowledge), behavior (the knowledge source about suffixes can react to a word with a characteristic ending), and identity (knowledge about small words is independent of the ability to match against a pattern).
The knowledge sources listed can be organized into a hierarchy. In particular, there are groups of knowledge sources about sentences, about words, about groups of letters, and about individual letters. Such a hierarchy corresponds to the objects on the blackboard: sentences, words, parts of words, and letters.
Comments