JMC@SAIL.STANFORD.EDU (John McCarthy) (10/30/87)
Eliot Handleman's request for information on prediction has inspired me to inflict the following considerations on the community. Roofs and Boxes Many people have proposed sequence extrapolation as a prototype AI problem. The idea is that a person's life is a sequence of sensory stimuli, and that science consists of inventing ways of predicting the future of this sequence. To this end many sequence extrapolating programs have been written starting with those that predict sequences of integers by taking differences and determining the co-efficients of a polynomial. It has always seemed to me that starting this way distorts the heuristic character of both common sense and science. Both of them think about permanent aspects of the world and use the sequence of sense data only to design and confirm hypotheses about these permanent aspects. The following sequence problem seems to me to typify the break between hypotheses about the world and sequence extrapolation. The ball bouncing in the rectilinear world - roofs and boxes Suppose there is a rectangular two dimensional room. In this room are a number of objects having the form of rectangles. A ball moves in the room with constant velocity but bounces with angle of incidence equal to angle of reflection whenever it hits a wall or an object. The observer cannot see the objects or the walls. All he sees is the x-co-ordinate of the ball at integer times but only when the ball is visible from the front of the room. This provides him with a sequence of numbers which he can try to extrapolate. Until the ball bounces off something or goes under something, linear extrapolation works. Suppose first that the observer knows that he is dealing with this kind of ball-in-room problem and only doesn't know the locations of the objects and the walls. After he has observed the situation for a while he will have partial information about the objects and their locations. For example, he may note that he has never been in a certain part of the room so there may be unknown objects there. Also he may have three sides of a certain rectangle but may not know the fourth side, because he has never bounced of that side yet. He may extrapolate that he won't have the opportunity of bouncing off that side for a long time. Alternatively we may suppose that the observer doesn't initially know about balls bouncing off rectangles but only knows the sequence and must infer this using a general sequence extrapolation mechanism. Our view is that this observer, whether human or machine, can make progress only by guessing the underlying model. At first he may imagine a one dimensional bouncing model, but this will be refuted the first time the ball doesn't bounce at an x-co-ordinate where it has previously bounced. Indeed he has to keep open the possibility that the room is really 3 or more dimensional or that more general objects than rectangles exist. We can elaborate the problem by supposing that when the ball bounces off the front wall, the experimenter can put a paddle at an angle and determine the angly of bounce so as to cause the ball to enter regions where more information is wanted. Assuming the rectangles having edges parallel to the axes makes the problem easier in an obvious sense but more difficult in the sense that there is less interaction between the observable x-co-ordinate and the unobservable y-co-ordinate. It would be interesting to determine the condition on the x-path that distinguishes 2-dimensional from 3-dimensional worlds, if there is one. Unless we assume that the room has some limited size, there need be no distinction. Thus we must make the never-fully-verified assumption that some of the repetititions in sequences of bounces are because the ball hit the front or back wall and bounced again off the same surfaces rather than similar surfaces further back. A tougher problem arises when the observer doesn't get the sequence of x-coordinates but only 1 or 0 according to whether the ball is visible or invisible. I am skeptical that an AI program fundamentally based on the idea of sequence extrapolation is the right idea. Donald Michie suggested that the "domain experts" for this kind of problem of inferring a mechanism that produces a sequence are cryptanalysts.