http://qs1969.pair.com?node_id=393077


in reply to Finding Patterns

I think there are two very different things you *might* be talking about here: "given a pattern, and some data, how do we find that pattern in the data", or "given some data, how do we find interesting patterns in it".

The first is ludicrously easy compared to the second, but has two areas of difficulty. One is how we represent the pattern - the language of regular expressions is our canonical example of "a way to represent patterns" over character streams. Different domains tend to give different languages, whether it is the type of data that is different (ie not a character stream), or the type of pattern; indeed, you could argue that the symbology of mathematics is the canonical "pattern language" for numbers (or even go further and argue that mathematics itself is "the study of patterns").

The second difficulty with the first question is finding matches for the pattern in a particular dataset. What is difficult here is entirely dependent on the type of pattern you are looking for: to some extent the language of regular expressions only bothers to provide mechanisms for expressing patterns we actually know how to check for. If you want to know more about how to match regular expressions, you might find it easier to look at the source code for PCRE than at perl's own regular expression engine.

The second question, "how do we find patterns without specifying in advance what patterns to look for" is very different, and as far as I know we don't have any real answer for that at the moment other than to point a human at the data.

I can identify two specific difficulties here, though I'm sure there are more: how do we decide (or specify) what patterns would qualify as "interesting", and how do we avoid restricting what types of pattern we are capable of discovering.

To me, these skills - spotting a new pattern, and taking advantage of it - are the essence of intelligence. It is far more efficient to remember a rule that applies to everything than to remember individually for each thing that the rule applies to it, and looking at it that way makes clear that "finding a pattern in the data" is very similar to "finding a way to compress the data". However, not all "ways to compress the data" necessarily represent "interesting patterns", and that brings us back to the nub; in particular, neural nets aren't very helpful in this respect - you may well be able to design a neural net that will once trained be very good at compressing data, but it won't be able to tell you what it's doing, nor will you be able to determine it from analysis of the system, in a way which has any chance of being expressible as an "interesting pattern".

Some of these areas are touched on in Fluid Concepts and Creative Analogies, but I need to track down some of the original papers discussed there to find some of the more interesting bits. In particular, I read there that for 'Seek Whence', Marsha Meredith developed a language for expressing the patterns of a particular class of integer sequences in such a way as to preserve the types of things that humans would choose to express; for example a sequence like:

1 1 1 2 1 2 2 3 1 2 3 3 4 1 2 3 4 4 5 ...
would tend to be viewed by a human as "a series of ladders of increasing height from 1 to n, with the penultimate entry duplicated"; most formal pattern languages would be capable of expressing this pattern, but would probably not express it like that - they'd probably split each ladder into two ranges, and might have to add a special-case for the start to cope with the "degenerate" first ladder with no "penultimate entry".

Finding better ways to express patterns is definitely a step in the right direction, and I suspect that it is only when we've gone further in extending and unifying "how to express a pattern" that we'll be able to improve our ability to reason about patterns themselves, and maybe that is the route that will let us work out how to do the rest.

However, within that book (which I've not finished), I've not yet seen any attempt to tackle the second problem: how to avoid restricting the type of pattern we can find. I don't know how to get there from here - we somehow need to be able to invent a new concept, determine whether it is a useful one, and if so add it to its dictionary/network of concepts to take advantage of in the future. Humans manage to do this remarkably well, bootstrapping from (essentially) nothing at all

Hugo