Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (II)

IJCAI-95 Contents Vol 2

Proceedings of the Fourteenth International

Joint Conference on Artificial Intelligence

Montreal, Quebec, Canada August 20-25,1995

CONTENTS

LEARNING 1

Oversearching and Layered Search in Empirical Learning 

 R QuinLan and R M Cameron-Jones  1019

Lookahead and Pathology in Decision Tree Induction

Sreerama Murthy and Steven Salzberg  1025

LEARNING 2

On Biases in Estimating Multi-Valued Attributes 

Igor kononenko 1034

Flexibly Exploiting Prior Knowledge in Empirical Learning

Julio Ortega and Doug Fisher  1041

LEARNING 3

Using Decision Trees for Conference Resolution

Joseph F McCarthy and' Wendy G Lehnerr  1050

Intermediate Decision Trees  

Laurence B Holder  1056

LEARNING 4

Constructing Nominal X of-N Attributes

 Zijian Zheng  1064

Oblivious Decision Trees Graphs and Top Down Pruning 

Ron Kohavi and (hia-Hsin Li  1071

REINFORCEMENT AND MARKOV MODELS 1

Probabilistic Robot Navigation in Partially Observable Environments

Reid Simmons and Sven Koenig  1080

Approximating Optimal Policies for Partially Observable Stochastic Domains

Ronald Parr and Stuart Russell  1088

REINFORCEMENT AND MARKOV MODELS 2

Process-Oriented Planning and Average-Reward Opumalirv  

Craig Boutilier and Martin L Puterman  1096

Exploiting Structure in Policy Construction   

Craig Boutdier Richard Dearden, and Moises Goldszmidt  1104

REINFORCEMENT AND MARKOV MODELS 3

A Reinforcement Learning Approach to Job-shop Scheduling

Wei Zhang and Thomas G Dietierich  1114

Decomposition Techniques for Planning in Stochastic Domains

Thomas Dean and Shieu-Hong I in  1121

STATISTICAL LEARNING 1

Dependency Relationship Based Decision Combination in Multiple Classifier Systems

Hee-Joong Kang and Jin H Kim  1130

A Studv of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selectio

 Ron Kohavi 115

STATISTICAL LEARNING 2

Local learning in probabilistic networks with

hidden variables   Stuart Russell John Binder Daphne Roller and Keiji Kanazawa  1146

Extending Classical Planning to Real-World Execution with Machine Learning

Gerald Dejong and SiOtt Bennett  1153

PAC LEARNING

The Complexity of Theory Revision

Russell Grrtner 1162

Practical PAC Learning

Dale Schuurmans and Russell Graner  1169

LEARNING 5

Learning to Reason The Non Monotonic Case

Dan Roth  1178

Generating and Solving Imperfect Information Games

Daphne Roller and Aur Pfeffer  1185

INDUCTIVE LOGIC PROGRAMMING

Covering vs Divide and-Conquer for Top-Down Induction of Logic Programs

 Hennk Bostrum  1194

AILP Abductive Inductive Logic Programming

 Hilde Ade and Marc Denecker  1201

LEARNING 6

Building Theories into Instantiation  

Alan M Frisch and C David Page Jr  1210

Learning One More Thing

Sebastian Thrun and Tom M Mitchell

INSTANCE BASED

Rule Induction and Instance-Based Learning A Unified Approach 

Pedro Domingos  1226

Muluresolution Instance-Based Learning  

 Kan Deng and Andrew W Moore

NATURAL LANGUAGE DISCOURSE 1

Generating Information-Sharing Subdialogues in Expert-User Consultation  

Jennifer Chu-Carroll and Sandra Carberry  1233

Generating Discourse across Several User Models Maximizing Belief while Avoiding Boredom and Overload Ingrid

 Zukerman and Richard McConachy  1261

DISCOURSE 2

The Use of Knowledge Preconditions in Language Processing

Karen E Lochbaum  1262

Integrating Gncean and Attcntional Constraints 

Rebecca J Passonneau  1267

PRESENTATION GENERATION

Generating Explanatory Captions for Information Graphics  

Vibhu 0 Mittal Steven Roth Johanna D Moore Joe Mattis and Giuseppe Caremm  1276

Ubiquitous Talker Spoken Language Interaction with Real World Objects  

 Katashi Nagao and Jun Rckimoto  1284

TENSE AND ASPECT

Dynamic Semantics for Tense and Aspect 

Mark Sttedman

Selecting Tense Aspect and Connecting Words In Language Generation

Bonnie J Dorr and Terry Gaasterland  1292

DICTIONARY CONSTRUCTION

Automatic Thesaurus Construction based on Grammatical Relations  

Tokunaga Tahenobu Iwayama Makoto and Tanaka Hozumi  1308

CRYSTAL Inducing a Conceptual Dictionary

Stephen Sodrrland, David Fisher Jonathan Aselttm and 'Wendy Lehnert  1314

STATISTICAL APPROACHES

Hierarchical Bayesian Clustering for Automatic Text Classification

Makoto Iwayama and Takenobu Tokunaga  1322

Stochastic Inversion Transduction Grammars with Application to Segmentation, Bracketing, and Alignment of Parallel Corpora 

Dekat Wu  1328

UNDERSTANDING 1

Improving Heuristic Based Temporal Analysis of Narratives wLth Aspect Determination 

Fel Song and Robin Cohen  1338

Semantic Inference in Natural Language Validating a Tractable Approach

Marc Vilaln  1346

UNDERSTANDING 2

Anaphors PPs and disambiguation process for conceptual analysis 

Saliha Azzam  1354

Discourse as a Knowledge Resource for Sentence Disambiguation

Tetsttya Nasukawa and Naohiko Uramoto  1360

UNDERSTANDING 3

A WordNei-based Algorithm for Word Sense Disambiguation

Xiaobtn Li Stan Szpakowicz, and Stan Matwin  1368

Analogy in the Large  

 Kenneth B Haast  1376

MACHINE TRANSLATION

Unification-Based Glossing 

Vasiletos  Hatzivasstloglou and Kevin Knight  1217

Filling Knowledge Gaps in a Broad Coverage Machine Translation System

Kevin Knight Ishwar Chander Matthew Haines Vasiletos Hatzivassiloglou Eduard Hovy, Masayo Jida Steve K Luk Richard Whitney, and Kenjt Yamada 1390

APPLICATIONS

A Support Tool for Writing Multilingual Instructions 

Cicile Paris Keith Vander Linden Markus Fischer Anthony Hartley, Lyn Pembenon Richard  Power and  Doma Scott  1398

Dialogue actions for natural language interfaces 

Arne Jonsson  1406

PARSING AND GENERATION

An Efficient Algorithm for Surface Generation 

Chruster Samuelsson  1414

 A Dependency-based Method for Evaluating Broad-Coverage Parsers  

 Dekang Lin 1420

FORMAL METHODS

 

Efficient Parametenzablc lype Expansion for Typed Feature Formalisms

Hans-Ulrtcb Krteger and Ulrtch Schdfer 1428

Integration oi Syntactic, Semantic and Contextual Information in Processing Grammatically III Formed Inputs

Osamu Imatcht and Yuji Matsumoto 1435

NONMONOTONIC REASONING

NON NONMONOTONIC REASONING 1

On the Relation between Argumentation and Non Monotonic Coherence Based Entailment  Claudette Cayrol 1443

How to infer from inconsistent beliefs without revising'

Salem Benferhat  Didier Dubois and Henn Prade 1449

NON NONMONOTONIC REASONING 2

On Decision Theoretic Foundations for Defaults  

Ronen I Brafman and Ntr Friedman 1458

Allowed Arguments  

 Michael Morreau 1466

NON NONMONOTONIC REASONING 3

On Specificity in Default Logic  

Jussi Rmtaneri 1474

Specificity and Inheritance in Default Reasoning 

Sek-Mah Ian and faded Pearl 1480

NON NONMONOTONIC REASONING 4

Syntactic Conditional C losures lor Defeasible Reasoning 

 James P Delgrande 1488

Sound and Efficient Non-monotonic Inference Hector  

Geffner Jimena Liopis and Gisela Mendez 1495

NON NONMONOTONIC REASONING 5

ComputingCircumscriptionRevisitedPreliminaryReport  

Andrzcj Pamck Doberty WttoldLukaszewicz,andSzalas   1502

Constrained and rational default logics

Artur Mikttmk and Mtroslaw Iruszczynsh

1509

NON NONMONOTONIC REASONING 6

On Bimodal Nonmonotonic Logics and Their Unimodal and Nonmodal Equivalents

Alexander Bochman 1518

Cancelling and Overshadowing Two Types of Defeasibdity in Defeasible Deontic Logic

Leendert W N van der Torre and Yao-Hua Jan 1525

BELEF REVISION 1

Belief revision, revised 

Daniel Lehmann 1534

Iterated Theory Base Change A Computational Modei

Mary-Anne Williams 1541

BELIEF REVISION 2

Generalized Update Belief Change in Dynamic Settings

Craig Boutiher 1550

Relating Belief Revision and Circumscription

Paolo Liberatore and Marco Schaerf 1557

PLANNING UNCERTAINTY

Planning under uncertainty Some key issues

Gregg Collins and Louue Pryor 1567

SOLUTION QUALITY

Optimizing Decision Quality with Contract Algorithms 

Shlomo Zilberstein 1576

Expected Solution Quality

John Brntna Mark Drummond and Keith Swanson 1583

ALGORITHMS

A Critical Look at Critics in HTN Planning

Kutluhan trol Jama Hendler Dana S Nau and Reiko Tsuneto 1592

Planning with Abstraction Hierarchies can be Exponentially Less Effici

Chnster Backstrom and Peter Jonswn 1599

SEARCH 1

Planning with Primary Effects Experiments and Analysis

Fugene Fink and Qiang Yan 1606

Scope and Abstraction Two Criteria for Localized Planning

Amy L Lansky and Lise C Getoor 1612

SEARCH 2

Comparison of Methods for Improving Search Efficiency in a Partial-Order Planner

Raghavan Snntvasan and Adele t Houv

1620

Admissible Pruning Strategies based on plan minimality for Plan Space Planning

Subbarao Kambhampati

1627

Fast Planning Through Planning Graph Analysis 

 Avrim L Blum and Merrick L Furst  1636

Planning with Sharable Resource Constraints 

 Philippe Laborie and Malik Ghailab  1643

REAL TIME SEARCH

The Focussed D" Algorithm for Real-Time Replannig 

Anthony Stentz  1662

Real-Time Search in Non-Deterministic Domains 

Sven Koenig and Reid G Simmons  1660

APPLICATIONS AND EVALUATION 1

AI Planning Versus Manufacturing-Operation Planning A Case Study  

Dana S Nau Satyandra A Gupta and William C Regit  1670

Hierarchical Plan Merging with Application to Process Planning  

Bntanik and M Marrfat  1677

APPLICATIONS AND EVALUATION 2

Planning Executing Sensing and Replanning for Information Gathering 

Crajg A Knoblock  1686

Abstraction by Interchange a biliry in Resource Allocation 

Berthe Y Choueiry, Bot Faltmgs and Ramer Weigel  1694

PLAN RECOGNITION

A Sound and Fast Goal Recognizer 

Neat Lesh and Oren Etzwm  1704

Recovering Problem-Solving Activities from Query Messages 

Yoshihtko Hayashi  1711

QUALITATIVE REASONING AND DIAGNOSIS

DIAGNOSIS 1

A Formal Framework for Representing Diagnosis Strategies in Model-Based Diagnosis Systems 

Wolfgang Nejdl Peter Frohlich and Michael Schroeder  1721

No Faults in Structure—How to Diagnose Hidden Interactions 

 Claudia Bottcher  1728

Trading off the costs of inference vs probing in diagnosis 

Johan de Kleer and Olivier Raiman  1736

Diagnosing tree-decomposable circuits 

Yousn El Fattah and Rtna Dechtcr  1742

MODELLING 1

Generating Causal Networks for Mobile Multi-Agent Systems with Qualitative Regions 

Korchi Kurumatam  1750

Case-based Modeling with Qualitative Indices 

Bradley Richards Boi Fairings and Peter Duxbury-Smith  1757

MODELLING 2

Using a Domain Theory to Guide Automated Modeling of Complex Physical Phenomena 

Sui-ky Ringo Ling  1766

Modeling Time in Hybrid Systems How Fast Is Instantaneous

Yumi Iwasaki Adam Farquhar Vijay Saraswat Daniel Bobrou and \ meet Gupta  1773

SIMULATION 1

Reasoning about Fluid Motion I Finding Structures 

Kenneth Yip  1782

Hisstory-based Interpretation of Finite Element Simulations of Seismic Wave Fields

Ulrieh junker and Bertrand Braunschweig  1789

SIMULATION 2

Scaling up Self-Explanatory Simulators Polynomial time Compilation

Kenneth D Forbus and Brian Falkenhamer  1798

Numerical Interval Simulation Combined Qualitative and Quantitative Simulation to Bound Behaviors of Non-Monotonic Systems

 Marcos Vescovi Adam Farquhar and Yumi Iwasaki  1806

MONITORING

Device Representation and Reasoning with Affective Relations 

James M Crawford Daniel L Dvorak Diane f Litman, Anil K Muhra and Peter F Patel-Schneider  1814

Determining the Loci of Anomalies Using Minimal Causal Models  

Richard f Doyle  1821

REASONING ABOUT FUNCTION

FBRL A Function and Behavior Representation Language

 Munchiko Sasajima Yoshinobu Kitamura, Mitsuru Ikeda and Ruchiro Mizoguchi  1830

A Theory of Mapping from Structure to Function Applied to Engineering Thermodynamics 

John O Everttt  1837

REASONING UNDER UNCERTAINTY

PROBABILITY AND ENTROPY

Minimum Cross-En cropy Reasoning A Statistical Justification 

Manfred Jaeger  1847

Representation Dependence in Probabilistic Inference 

 Joseph Y Halpern and Daphne Roller  1863

IMPRECISE PROBABILITIES

Models and Algorithms for Probabilistic and Bayesian Logic 

Pierre Hansen Brigitte Jaumard  Guy-Blaise  Douanya Nguetse and Marcus Poggi de Aragao  1862

Ignorant Influence Diagrams 

Marco Ramom  1869

BAYES NETS

The BAT mobile Towards a Bayesian Automated Taxi 

Jeff Forbes lim Huang ketjt harmzawa and Smart Russell  1878

Adaptive Provision of Evaluation Oriented lnformation Tasks and Techniques

Anthony Jameson Ralph Schafer Joep Simom and Thomas Wets  1886

BELIEF FUNCTIONS

The Canonical Decomposition of a Weighted Belief 

 Philippe Smets  1896

On the Representation of Nonmoniomc Relations in the Theory of Evidence 

 Ronald R yager  1902

MULTIPLE VALUED LOGIC

The Rationality and Decidability of Fuzzy Implication  

Cheng Xiaochun Jiang Yunfer and Liu Xuhua  1910

Possibihstic Temporal Reasoning based on Fuzzy Temporal Constraints 

Lluis Godo and Lluls Vila  1916

DECISION THEORY

Possibility Theory as a Basis for Qualitative Decision Theory  

Dtdter Dubois and Henri Prade  1924

TEMPORAL REASONING 1

Reasoning about Noisy Sensors in the Situation Calculus 

 Fahiem Bacchus Joseph Y Halpern and Hector f Levesque  1933

A Logic for Acting Sensing and Planning 

Paolo Traversa and Luca Spalazzs  1941

TEMPORAL REASONING 2

Reasoning about Action and Change Using Dijkstras Semantics for Programming Languages Preliminary Report

Witold Lukaszewicz and Ewa Madahnska Bugaj  1950

The Logic of Dynamic Systems 

Michael  Thiedscher  1956

TEMPORAL REASONING 3

Dependent Fluents 

 Enrico Giunchiglia and  ladimir Lifschitz  18964

A simple Formalization of Actions Using Circumscription 

G.Neelakantan Kartha and Vladimir Lifichitz  1970

TEMPORAL REASONING 4

A Causal Theory of Ramifications and Qualifications 

 Norman McCain and Hudson Turner  1978

Embracing Causality in Specifying the Indirect Effects of Actions 

Fangzhen Lin  1985

TEMPORAL REASONING 5

Computing Ramifications by Post processing 

Michael Thielscher  1904

How to Progress a Database 11 The STRIPS Connection 

Fangzhen Lin and Ray Reiter  2001

TEMPORAL REASONING 6

Towards Action Prediction Using a Mental-Level Model  

Ronen I Brafman and Moshe Tennenholtz  2010

Reasoning about actions Non-deterministic effects Constraints and Qualification  

Chitta Baral  2017

PANELS

Systematic Versus Stochastic Constraint Satisfaction  

Eugene C Freuder (Chair) Rina Dechter Matthew L Ginsberg Bart Selman and Edward Tsang  2027

VERY Large Knowledge bases—Architecture vs Engineering

Jame  Hendler (Chair) Jaime Carbonell Douglas Lenat Riichtro Mizogueht Paul Rosenbloom  2033

A Philosophical Encounter 

Aaron Sloman  2037

What has Al in Common with Philosophy 

John McCarthy  2041

VIDEOS

Description Logic in Practice A CLASSIC Application

 Deborah L McGumness and Lort Alpenti Resnick ATOT Bell Laboratories and Charles Isbell MITAI Lab  2045

Revealing Collection Structure through Information Access Interfaces 

Marti A Hearst and Jan 0 Pederson Xerox Palo Alto Research Center  2047

Advances of the DBLearn System for Knowledge Discover; in Large Databases 

Jiawei Han Yongjian Fu and Simon Tang Simon Eraser University  2049

IRV Learning to Integrate Visual Information Across Camera Movements

 Peter N Prokopowicz, University of Chicago and Paul R Cooper Northwestern University  2051

WIP From Multimedia to Intellimedia

Elisabeth Andre Wolfgang Finkler Wtnfried Graf Karin Harbusch Jochen Heinsohn Anne Kilger Bern hard Nebel Hans-Jurgen Profitlich Thomas Rist Wolfgang Wahlster (Authors of the WlP System) Andreas Butz (Video Producer) Anthony Jameson (Speaker) German Research Center for Artificial Intelligence (DFKI)  2053

Computer-aided Creative Mechanism Design 

Boi Faltings and Run Sun, Swiss Federal Institute of Technology  2055

Learning University Mathematics  

Edmund Furse University of Glamorgan  2067

PeopIeFinder a Multimodal Multimedia Communications Tool for Interconnecting Office Staff

Innes A Ferguson and James D Davlouros  2069

 Situated Verbal Interaction in Virtual Design and Assembly

Yong Cao Bernhard Jung and Ipke Wachsmuth University of Bielefeld  2061

Multiple Perspective Interactive Video

Arun Katkere Don huramura Sated Moezzi Patrick Kelly Deborah Swanberg Kojr Wakimoto Edward Hunter Li-Cbeng Tai Shankar Chatterjee and Ramesh Jam University of California San Diego  2063

GRASPER A Permissive Planning  Robot 

 Scott Bennett SRA Corporation and Gerald Dejong University of Illinois  2065

SRICAT Sky Image Cataloging and Analysis Tool 

Usama M Fayyad JPL California Institute of Technology  2067

MUSE (Multidimtnsional User Oriented Synthetic Environment}—A New Approach to the Human-Computer Interface Using Precognitive Models of

 Perception Creve Maples and Craig Peterson  2069

Sandia National Labs A Case Based Approach to Knowledge Navigation 

kristian J Hammond and Robin Burke University of Chicago and Steven L Lytinen Depaul University  2071

Modeling Interactive Agents in ALIVE   

Pattie Maes Brute Blumberg Treivr Darrell Alex Pent land and Alan Wexelblat MIT Media Laboratory  2073

DISCLAIMER: Please note that IJCAI Organization is the sole copyright owner of all materials published in the Proceedings of its conferences. All rights are reserved. No part of any IJCAI conference Proceedings may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher, which is also the IJCAI Organization. Contact information for obtaining written permission can be found here.