AT

AAAI Conference 1999 Conference Paper

A Simple, Fast, and Effective Rule Learner

• William W. Cohen
• Yoram Singer
• AT
• T Labs - Research

Wedescribe SLIPPER~ a newrule learner that generates rulesets by repeatedly boosting a simple, greedy, rule-builder. Likethe rulesets built byother rule learners, the ensembleof rules created by SLIPPER is compact and comprehensible. This is madepossible by imposingappropriate constraints on the rule-builder, andby use of a recently-proposedgeneralization of Adaboostcalled confidence-ratedboosting. In spite of its relative simplicity, SLIPPER is highly scalable, andan effective learner. Experimentally, SLIPPER scales no worse than O(nlog n), wheren is the numberof examples, and on a set of 32 benchmark problems, SLIPPER achieves lower error rates than RIPPER 20 times, and lowererror rates than C4. 5rules22times.

AAAI Conference 1999 Conference Paper

AI & the World Wide WebRecognizing Structure in Web Pages Using Similarity Queries

• William W. Cohen
• AT
• T Labs - Research

Wepresent general-purpose methodsfor recognizing certain types of structure in HTML documents. The methodsare implementedusing WHIRL, a "soft" logic that incorporates a notion of textual similarity developed in the information retrieval community. In an experimental evaluation on 82 Web pages, the structure ranked first byour methodis "meaningful"--i. e. , a structure that wasused in a hand-coded"wrapper", or extraction program, for the page--nearly 70%of the time. This improveson a value of 50%obtained by an earlier method. With appropriate backgroundinformation, the structure-recognition methodswedescribe can also be used to learn a wrapper from examples, or for maintaining a wrapper as a Web page changes format. In these settings, the top-rankedstructure is meaningfulnearly 85%of the time.

AAAI Conference 1999 Conference Paper

Control Knowledge in Planning: Benefits and Tradeoffs

• Yi-Cheng Huang
• Bart Selman
• Cornell University; Henry Kautz
• AT
• T Labs - Research

Recent newplanning paradigms, such as Graphplan and Satplan, have been shownto outperform moretraditional domain-independentplanners. Aninteresting aspect of these planners is that they do not incorporate domainspecific control knowledge, but instead rely on efficient graph-basedor propositional representations and advancedsearch techniques. Analternative approach has been proposed in the TLPlansystem. TLPlanis an exampleof a powerful planner incorporating declarative control specified in temporal logic formulas. Weshowhowthese control rules can be parsed into Satplan. Ourempirical results showup to an order of magnitudespeed up. Wealso provide a detailed comparison with TLPlan, and showhowthe search strategies in TLPlanlead to efficient plans in terms of the numberof actions but with little or no parallelism. The Satplan and Graphplan formalisms on the other hand do find highly parallel plans, but are less effective in sequential domains. Ourresults enhanceour understandingof the various tradeoffs in planning technology, and extend earlier workon control knowledgein the Satplan frameworkby Ernst et a/. (1997) and Kautz and Selman(1998).

AAAI Conference 1999 Conference Paper

State-Space Planning by Integer Optimization

• Henry Kautz
• T Shannon Labs; Joachim P. Walser
• AT
• T Shannon Labs
• i2 Technologies

This paper describes ILP-PLAN, a framework for solving AI planning problems represented as integer linear programs. ILP-PLAN extends the planning as satisfiability framework to handle plans with resources, action costs, and complex objective functions. We show that challenging planning problems can be effectively solved using both traditional branchand-bound IP solvers and efficient new integer local search algorithms. ILP-PLAN can find better quality solutions for a set of hard benchmark logistics planning problems than had been found by any earlier system.

IJCAI Conference 1995 Conference Paper

Stochastic Search and Phase Transitions: AI Meets Physics

• Bart Selrnan
• AT
• T Bell Laboratories