Pruning Deductions in Expert Systems

Question

In a rule system, or any reasoning system that deduces facts via forward-chaining inference rules, how would you prune "unnecessary" branches? I'm not sure what the formal terminology is, but I'm just trying to understand how people can limit their train-of-thought when reasoning over problems, whereas all semantic reasoners I've seen appear unable to do this.

For example, in John McCarthy's paper An Example for Natural Language Understanding and the AI Problems It Raises, he describes potential problems in getting a program to intelligently answer questions about a news article in the New York Times. In section 4, "The Need For Nonmonotonic Reasoning", he discusses the use of Occam's Razer to restrict the inclusion of facts when reasoning about the story. The sample story he uses is one about robbers who victimize a furniture store owner.

If a program were asked to form a "minimal completion" of the story in predicate calculus, it might need to include facts not directly mentioned in the original story. However, it would also need some way of knowing when to limit its chain of deduction, so as not to include irrelevant details. For example, it might want to include the exact number of police involved in the case, which the article omits, but it won't want to include the fact that each police officer has a mother.

Answer 1

What problem is solving by pruning?

At least concerning specific ML algorithms, Decision Trees, MARS, and Neural Network, pruning is performed on an initially over-fit model (a model that fits the training data so nearly that it is incapable to generalize accurately predict new instances). In each case, pruning involves removing marginal nodes (DT, NN) or terms in the regression equation (MARS) one by one.

Second, why is pruning necessary/desirable?

Pruning works from "the bottom up" that is the model is constructed from the top down, so tuning the model (to achieve the same benefit as pruning) eliminates not just one or more decision nodes but also includes the child nodes that (like trimming a tree closer to the trunk). So eliminating a marginal node might also eliminate one or more strong nodes subordinate to that marginal node--but the modeler would never know that because his/her tuning eliminated further node creation at that marginal node. Pruning works from the other direction--from the most subordinate (lowest-level) child nodes upward in the direction of the root node.