Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!usc!samsung!aplcen!haven!udel!princeton!phoenix!eliot From: eliot@phoenix.Princeton.EDU (Eliot Handelman) Newsgroups: comp.ai Subject: Some Sequence Prediction Work (Long) Re: pattern recognition Keywords: patterns Message-ID: <11883@phoenix.Princeton.EDU> Date: 2 Dec 89 22:32:08 GMT References: <2850@ucrmath.UCR.EDU> Reply-To: eliot@phoenix.Princeton.EDU (Eliot Handelman) Organization: Princeton University, NJ Lines: 269 In article <2850@ucrmath.UCR.EDU> xcax12@ucrmath.UCR.EDU () writes: ; I am having a problem with pattern recognition. I am trying to ;write a program that will recognize patterns that are inputted, outputting ;the next couple of logical repetitions. I'm hoping it will work something ;like this: ; ;(defun pattern_rec (x) ; ( <<< CODE HERE >>> )) ;pattern_rec ; ;(pattern_rec '(a b a c a d a e)) ;(a b a c a d a e a f) ; ; ;I have everything figured out except for the 'CODE HERE' part. :-) ; ;If anyone can give me a bit of help, just even a push in the right direction, ;I would be greatly appreciative. I will be monitoring this group, so either ;post or send mail. Thanks. Two years ago I posed a similar question, and got a large number of pointers to research and the literature. I've appended some of them below. John McCarthy also wrote to express his skepticism of sequence-predicting approaches to AI. I've included his whole article, because there are probably many others interested in this. Saul Kripke, in "Wittgenstein on Rules and Private Language" makes an attack on the idea that there is "a" solution to a given sequence as follows: "... an intelligence tester may suppose that there is only one possible continuation to the sequence 2,4,6,8,..., mathematical and philosophical sophisticates know that an indefinite number of rules (even rules stated in terms of mathematical functions as conventional as ordinary polynomials) are compatible with any such finite initial segment. So if the tester urges me to respond, after 2,4,6,8,..., with *the* unique appropriate next number, the proper response is that no such unique number exists, nor is there any unique (rule determined) infinite sequence that continues the given one." (page 18) For example, one could argue that the "rule" determined by Kripke's sequence is "really": n(1) = 2; n(i + 1) = n(i + 2) IF i < 5; n(i + 1) = 57 IF i >= 5. Applying this rule, the "real" sequence is 2,4,6,8,57,57,57, .... Refuting this is not as simple as it looks. One could say that the solution is "inelegant," but what's the criteria of elegance? That the rule can be couched in as few clauses as possible? That's the argument of the "simplicicists," see, eg, Elliott Sober, "Simplicity," Oxford, 1975. My own interest in this has to do with music but there things are even more complex. I ought to have a paper forthcoming that may explain this remark. Here are some of the replies: ---- Date: Thu, 29 Oct 87 17:43:15 PST From: Tom Dietterich You might find the article Discovering Patterns in Sequences of Events by myself and Ryzsard Michalski (Artificial Intelligence, Vol 25, No. 2 187-232) to be relevant. We were looking at sequence prediction, and we cite all of the other work we could find. (A revised version of the article can be found in Michalski's edited collection Machine Learning: An Artificial Intelligence Approach, Vol II). ------ From: robin burke You might look at some of Holfstadter's work in analogies. Example: "Fluid Concepts and Creative Analogies" FARG Document 87-1, University of Michigan. ------- Date: Fri, 30 Oct 87 14:11:04 EST From: Carl H. Smith The Russians have done a lot of work on the extrapolation problem. This problem is one of predicting the next value of a function after seeing some initial segment of its graph. You can find a description of results in the area, along with formal definitions and pointers to the literature in Inductive inference: theory and methods by Angluin & Smith, Computing Surveys, 1983. ---- Date: Fri, 30 Oct 87 20:53:13 pst From: peregrine.com!dmi (Dean Inada) Well, data compression algorithms are essentialy pattern predictors. In particular, Lempel-Ziv compression can make good use of the pattern of your example. JACM, Vol. 29, No. 4, pg. 943 gives a good review of this. The Computer Recreations column of Scientific American Vol. 254, No. 3 March 1986 describes some other aproaches to pattern prediction, based on explicit models of the pattern generator. ----- Date: Sat, 31 Oct 87 22:01:04 cst From: uiucdcs!osiris.cso.uiuc.edu!goldfain (Mark Goldfain) A lot of work was done on this at UIUC a while back. The main program I remember that did this sort of work was called SPARC. I bet you could get a lot of paper references and perhaps some code from Intelligent Systems Group Department of Computer Science University of Illinois at Urbana-Champaign 1304 West Springfield Urbana, IL. 61801 The best contacts would be Ryzard Michalski or Kaihu Chen. If I'm not mistaken an email address that should work is: michalsk@aisund.uiuc.edu (If you have arpa/internet access). - Mark Goldfain ---- Date: Mon, 2 Nov 87 08:09:30 est From: John Grefenstette You might like to read: "Learning to predict by the method of temporal differences", by Rich Sutton, TR87-509.1, Computer and Intelligent Systems Lab, GTE Labs, 40 Sylvan Road, Waltham, MA 02254. ---- From: philabs.Philips.Com!raca (Rich Caruana) To: mind.UUCP!eliot Try HaYong Zhou's dissertation from Vanderbilt University, Nashville. ---- Date: Mon, 2 Nov 87 10:21 EDT From: RELAY.CS.NET!PTW%UTRC%untech.utc.com A. K. Dewdney has an interesting article in his "Computer Recreations" column in the Novemeber 1985 issue of Scientific American that seems applicable to your problem. Dewdney describes using the Genetic Algorithm to evolve a finite state table that can predict the next input signal based on previous inputs. The Genetic Algorithm is a machine learning technique that operates by simulating evolution through natural selection. Its not just a half-backed scheme though - it has a rigorous theoretical basis thanks to John Holland from U. of Michigan. Anyway, Dewdney used the GA to predict the next expected (binary) input. The state transition table that the GA produces to accomplish the prediction might constitute the "pattern of inference" you are looking for. ---- Subject: Re: Prediction-producing Algorithms Date: Wed, 04 Nov 87 16:53:33 -0800 There are several papers in the field of automatic program synthesis that ought to be right up your alley. For instance [BieSmi79] gives a simple yet interesting algorithm designed to generate an output from a single input as easily as possible---meaning it takes advantage of patterns inherent in the input. A good paper to start your search with. If you're really interested in studying pattern generation, there are PhD theses written on systems that generate programs from sample input-output examples. These systems both rely on pattern induction, but involve a lot of reading. I'll give you the references for those as well: [BieSmi79] Alan W Biermann and Douglas R Smith A Production Rule Mechanism for Generating LISP Code IEEE Transactions on Systems, Man, and Cybernetics volume SMC-9 #5 pages 260-276 [Bigger76] Ted J Biggerstaff C2: A "Super Compiler" Approach to Automatic Programming Ph D Dissertation, Dept of Computer Science University of Washington, Seattle, WA Jan 76 [Summer75] Phillip D Summers Program Construction from Examples Ph D Dissertation, Yale University, New Haven, CT Dec 75 ---- Date: 30 Oct 87 0950 PST From: John McCarthy Eliot Handelman'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. Brought to you by Super Global Mega Corp .com