|
Said the person to the computer: I demand an explanation Jerry DeJong
You ask a computer a question, and it gives you an answer. Can you trust it? Only if it provides a reasonable explanation for its conclusion. This is at the heart of explanation-based learning. Jerry DeJong has been doing explanation-based learning for the past two decades, on a quest to make machine learning more responsive to prior knowledge. Explanation-based learning is a branch of machine learning in which prior knowledge is integrated into the process of forming new concepts. Machine learning is a subfield of artificial intelligence (AI), in which a computer "learns" by extracting rules and patterns from large data sets. Over the years, machine learning has evolved from a logic framework to a statistical framework. DeJong believes that a combination of these approaches is necessary for a machine to act intelligently. There's logic . . . In a logic framework, you give the computer a description of the world, and it will use logical inference to deduce likely answers based on the knowledge you gave it before. But this system is very brittle: It might go nuts if you ask for something it hasn't seen before. "It was generally accepted that what AI systems were missing was the huge encyclopedic knowledge base that people have," said DeJong. "If you ask a person to name things that could be found in a professor's office, they could do it. A desk, a stapler, some books. A computer wouldn't know any of this, even if it knew what each item was individually." It turns out that logic is inappropriate for presenting knowledge about the world. This one example of what is known as the Qualification Problem, a phenomenon known to philosophers for hundreds of years. Put another way, if you are using logic to describe the world, almost everything you suppose will be incorrect. For example, birds fly. Well, not all birds fly, some, like penguins, don't. What if they sort of fly, like a chicken? What about a bird with a broken wing? Or what about a bird whose feet are cast in cement? The boundary between whether a bird flies or does not is a fuzzy one in some cases. "No matter how many exceptions we can write down-outlandish or not-we will never get all of them," said DeJong. "The problem is that with the statement 'birds fly,' we haven't captured our knowledge about what it really means for birds to fly. No matter how carefully we word things, we will never converge to a representation with which we can say: Okay, now we've got it. We cannot yet reach the level of understanding of a person." Clearly, logic alone is not going to cut it. "Logic is very extreme in its interpretation of symbols," he continued. "When you write an expression, it's either true or not. Cars move. This is true. For all x, if x is a car, then it moves. Buried things cannot move. For all y, if y is buried, then it cannot move. This is also true. The implication, however, is that you cannot bury a car. The sets of things that are buried and the things that are cars are disjoint. The conclusion is derived from reasonable statements, but it cannot be believed. The premise is okay. The rule of inference is okay. If you believe x and y, then you must conclude that cars cannot be buried, which is not reasonable." And then there's statistics . . . Statistics, or statistical inference, on the other hand, is optimization. It is concerned with what is likely to be true or false. If you know that 90 percent of basketball players are taller than football players, and person A is a basketball player and person B is a football player, logic will demand that you be certain that A is taller than B. That's the brittleness of logic. Person A probably is taller than B, but not necessarily, and unlike logic, statistics would allow this exception. "The statistical framework seeks a solution to an optimization problem rather than a satisfiability problem," said DeJong. "The world is more likely like this than like that, and it's the same with the conclusions. Some parts of the world are extreme-the light switch is either on or off-but most of the world isn't like that. Most of the world's knowledge is a statistical distribution rather than a proposition of what is known to be true." The problem with the statistical framework, however, is expressiveness-what kinds of things you can say. Statistically you can say that birds can fly, but this notion cannot be applied to an individual bird. "It's been very difficult until recently to translate statements about classes of things into statements about the members of those classes," said DeJong. "It's trivial to do that in logic. For example, John has red hair. I found this hair that came from John. It must be red." The best of both worlds DeJong's solution to the limitations of the logic approach and the statistical approach is to combine them by annotating more expressive formalisms to some of the attributes of statistics. Using probabilities and distributions, the obvious thing to do would be to come up with a representation language with some characteristics of logic and many of statistics. However, that doesn't work very well. Instead, DeJong proposes to reinterpret the semantics of logic to have a statistical rather than a logical framework. "When most people say that birds fly," DeJong explained, "they don't really mean that. What they mean is that most birds fly. There is an implied confidence that birds fly. In my framework, when you say birds fly, it is a correct statement. I'm trying to resist the notion that insists on having some kind of probability measure on that statement. This leads to a different kind of logical inference that is more similar to logic than statistics, but it ends up with characteristics of approximability, which is the missing part of logic. Instead of simply merging logic and statistics, I am staying with logic but changing the semantics, which includes the underlying meaning of these statements and that introduces a rather different notion of what inference means." DeJong is working out a theory of interference in this new, non-standard logic framework. This theory is explanation-based learning. DeJong is looking at additional information sources in a machine-learning system that adds interaction with prior knowledge to the training examples. An explanation-based learning system will insist on a reason for believing the assigned labels of a machine-learning system. "Instead of picking one output or another," he said, "it will try to understand the structure of the inputs and what parts contributed to its output or assessment. We would also like to give some prior knowledge to the system so that it prefers reasonable rules over silly rules, even if it doesn't fit the data as well. It's a bit like medical training. If a medical student had to learn to be a doctor strictly by observing examples, it would take forever. Instead, that student can take advantage of everything already known from other doctors. DeJong is currently applying his explanation-based learning algorithms for handwritten Chinese character identification. Another application domain is in compiler software-a compiler that gets better at compiling. He is focusing his efforts on areas in which current machine learning falls apart. "We are not so much trying to get it right, but we are trying to make progress. We are qualitatively incorporating different kinds of evidence (the statistical training set) with analytic evidence (believing something because you can make a good story out of it). We want both a good story and reasonable accuracy. If we can get both, then we have a good chance of doing well on unseen examples, even without having tested it on thousands of examples. In cases when standard statistical techniques fall short, this is often exactly what's needed." "We need to take advantage of the storehouse of understanding that humankind has amassed over the century," DeJong concluded. "We should only use learning to fill in what we don't already know." Written by Judy Tolliver, July 5, 2006
|
|