Daniel S. Weld

AAAI Conference 2022 Conference Paper

A Search Engine for Discovery of Scientific Challenges and Directions

• Dan Lahav
• Jon Saad Falcon
• Bailey Kuehl
• Sophie Johnson
• Sravanthi Parasa
• Noam Shomron
• Duen Horng Chau
• Diyi Yang

Keeping track of scientific challenges, advances and emerging directions is a fundamental part of research. However, researchers face a flood of papers that hinders discovery of important knowledge. In biomedicine, this directly impacts human lives. To address this problem, we present a novel task of extraction and search of scientific challenges and directions, to facilitate rapid knowledge discovery. We construct and release an expert-annotated corpus of texts sampled from full-length papers, labeled with novel semantic categories that generalize across many types of challenges and directions. We focus on a large corpus of interdisciplinary work relating to the COVID-19 pandemic, ranging from biomedicine to areas such as AI and economics. We apply a model trained on our data to identify challenges and directions across the corpus and build a dedicated search engine. In experiments with 19 researchers and clinicians using our system, we outperform a popular scientific search engine in assisting knowledge discovery. Finally, we show that models trained on our resource generalize to the wider biomedical domain and to AI papers, highlighting its broad utility. We make our data, model and search engine publicly available.

AAAI Conference 2021 Conference Paper

Is the Most Accurate AI the Best Teammate? Optimizing AI for Teamwork

• Gagan Bansal
• Besmira Nushi
• Ece Kamar
• Eric Horvitz
• Daniel S. Weld

AI practitioners typically strive to develop the most accurate systems, making an implicit assumption that the AI system will function autonomously. However, in practice, AI systems often are used to provide advice to people in domains ranging from criminal justice and finance to healthcare. In such AI-advised decision making, humans and machines form a team, where the human is responsible for making final decisions. But is the most accurate AI the best teammate? We argue “not necessarily” — predictable performance may be worth a slight sacrifice in AI accuracy. Instead, we argue that AI systems should be trained in a human-centered manner, directly optimized for team performance. We study this proposal for a specific type of human-AI teaming, where the human overseer chooses to either accept the AI recommendation or solve the task themselves. To optimize the team performance for this setting we maximize the team’s expected utility, expressed in terms of the quality of the final decision, cost of verifying, and individual accuracies of people and machines. Our experiments with linear and non-linear models on real-world, high-stakes datasets show that the most accuracy AI may not lead to highest team performance and show the benefit of modeling teamwork during training through improvements in expected team utility across datasets, considering parameters such as human skill and the cost of mistakes. We discuss the shortcoming of current optimization approaches beyond well-studied loss functions such as log-loss, and encourage future work on AI optimization problems motivated by human-AI collaboration.

AAAI Conference 2019 Conference Paper

Updates in Human-AI Teams: Understanding and Addressing the Performance/Compatibility Tradeoff

• Gagan Bansal
• Besmira Nushi
• Ece Kamar
• Daniel S. Weld
• Walter S. Lasecki
• Eric Horvitz

AI systems are being deployed to support human decision making in high-stakes domains such as healthcare and criminal justice. In many cases, the human and AI form a team, in which the human makes decisions after reviewing the AI’s inferences. A successful partnership requires that the human develops insights into the performance of the AI system, including its failures. We study the influence of updates to an AI system in this setting. While updates can increase the AI’s predictive performance, they may also lead to behavioral changes that are at odds with the user’s prior experiences and confidence in the AI’s inferences. We show that updates that increase AI performance may actually hurt team performance. We introduce the notion of the compatibility of an AI update with prior user experience and present methods for studying the role of compatibility in human-AI teams. Empirical results on three high-stakes classification tasks show that current machine learning algorithms do not produce compatible updates. We propose a re-training objective to improve the compatibility of an update by penalizing new errors. The objective offers full leverage of the performance/compatibility tradeoff across different datasets, enabling more compatible yet accurate updates.

AAMAS Conference 2016 Conference Paper

Optimal Testing for Crowd Workers

• Jonathan Bragg
• NONE-REMOVE Mausam
• Daniel S. Weld

Requesters on crowdsourcing platforms, such as Amazon Mechanical Turk, routinely insert gold questions to verify that a worker is diligent and is providing high-quality answers. However, there is no clear understanding of when and how many gold questions to insert. Typically, requesters mix a flat 10–30% of gold questions into the task stream of every worker. This static policy is arbitrary and wastes valuable budget — the exact percentage is often chosen with little experimentation, and, more importantly, it does not adapt to individual workers, the current mixture of spamming vs. diligent workers, or the number of tasks workers perform before quitting. We formulate the problem of balancing between (1) testing workers to determine their accuracy and (2) actually getting work performed as a partially-observable Markov decision process (POMDP) and apply reinforcement learning to dynamically calculate the best policy. Evaluations on both synthetic data and with real Mechanical Turk workers show that our agent learns adaptive testing policies that produce up to 111% more reward than the non-adaptive policies used by most requesters. Furthermore, our method is fully automated, easy to apply, and runs mostly out of the box.

AIJ Journal 2013 Journal Article

POMDP-based control of workflows for crowdsourcing

• Peng Dai
• Christopher H. Lin
• Mausam
• Daniel S. Weld

Crowdsourcing, outsourcing of tasks to a crowd of unknown people (“workers”) in an open call, is rapidly rising in popularity. It is already being heavily used by numerous employers (“requesters”) for solving a wide variety of tasks, such as audio transcription, content screening, and labeling training data for machine learning. However, quality control of such tasks continues to be a key challenge because of the high variability in worker quality. In this paper we show the value of decision-theoretic techniques for the problem of optimizing workflows used in crowdsourcing. In particular, we design AI agents that use Bayesian network learning and inference in combination with Partially-Observable Markov Decision Processes (POMDPs) for obtaining excellent cost-quality tradeoffs. We use these techniques for three distinct crowdsourcing scenarios: (1) control of voting to answer a binary-choice question, (2) control of an iterative improvement workflow, and (3) control of switching between alternate workflows for a task. In each scenario, we design a Bayes net model that relates worker competency, task difficulty and worker response quality. We also design a POMDP for each task, whose solution provides the dynamic control policy. We demonstrate the usefulness of our models and agents in live experiments on Amazon Mechanical Turk. We consistently achieve superior quality results than non-adaptive controllers, while incurring equal or less cost.

UAI Conference 2012 Conference Paper

A Theory of Goal-Oriented MDPs with Dead Ends

• Andrey Kolobov
• Mausam
• Daniel S. Weld

Stochastic Shortest Path (SSP) MDPs is a problem class widely studied in AI, especially in probabilistic planning. They describe a wide range of scenarios but make the restrictive assumption that the goal is reachable from any state, i.e., that dead-end states do not exist.Because of this, SSPs are unable to model various scenarios that may have catastrophic events (e.g., an airplane possibly crashing if it flies into a storm). Even though MDP algorithms have been used for solving problems with dead ends, a principled theory of SSP extensions that would allow dead ends, including theoretically sound algorithms for solving such MDPs, has been lacking. In this paper, we propose three new MDP classes that admit dead ends under increasingly weaker assumptions. We present Value Iteration-based as well as the more efficient heuristic search algorithms for optimally solving each class, and explore theoretical relationships between these classes. We also conduct a preliminary empirical study comparing the performance of our algorithms on different MDP classes, especially on scenarios with unavoidable dead ends.

UAI Conference 2012 Conference Paper

Crowdsourcing Control: Moving Beyond Multiple Choice

• Christopher H. Lin
• Mausam
• Daniel S. Weld

To ensure quality results from crowdsourced tasks, requesters often aggregate worker responses and use one of a plethora of strategies to infer the correct answer from the set of noisy responses. However, all current models assume prior knowledge of all possible outcomes of the task. While not an unreasonable assumption for tasks that can be posited as multiple-choice questions (e.g. n-ary classification), we observe that many tasks do not naturally fit this paradigm, but instead demand a free-response formulation where the outcome space is of infinite size (e.g. audio transcription). We model such tasks with a novel probabilistic graphical model, and design and implement LazySusan, a decision-theoretic controller that dynamically requests responses as necessary in order to infer answers to these tasks. We also design an EM algorithm to jointly learn the parameters of our model while inferring the correct answers to multiple tasks at a time. Live experiments on Amazon Mechanical Turk demonstrate the superiority of LazySusan at solving SAT Math questions, eliminating 83.2% of the error and achieving greater net utility compared to the state-ofthe-art strategy, majority-voting. We also show in live experiments that our EM algorithm outperforms majority-voting on a visualization task that we design.

AIJ Journal 2012 Journal Article

Discovering hidden structure in factored MDPs

• Andrey Kolobov
• Mausam
• Daniel S. Weld

Markov Decision Processes (MDPs) describe a wide variety of planning scenarios ranging from military operations planning to controlling a Mars rover. However, todayʼs solution techniques scale poorly, limiting MDPsʼ practical applicability. In this work, we propose algorithms that automatically discover and exploit the hidden structure of factored MDPs. Doing so helps solve MDPs faster and with less memory than state-of-the-art techniques. Our algorithms discover two complementary state abstractions — basis functions and nogoods. A basis function is a conjunction of literals; if the conjunction holds true in a state, this guarantees the existence of at least one trajectory to the goal. Conversely, a nogood is a conjunction whose presence implies the non-existence of any such trajectory, meaning the state is a dead end. We compute basis functions by regressing goal descriptions through a determinized version of the MDP. Nogoods are constructed with a novel machine learning algorithm that uses basis functions as training data. Our state abstractions can be leveraged in several ways. We describe three diverse approaches — GOTH, a heuristic function for use in heuristic search algorithms such as RTDP; ReTrASE, an MDP solver that performs modified Bellman backups on basis functions instead of states; and SixthSense, a method to quickly detect dead-end states. In essence, our work integrates ideas from deterministic planning and basis function-based approximation, leading to methods that outperform existing approaches by a wide margin.

ICAPS Conference 2012 Conference Paper

Reverse Iterative Deepening for Finite-Horizon MDPs with Large Branching Factors

• Andrey Kolobov
• Peng Dai 0001
• Mausam
• Daniel S. Weld

In contrast to previous competitions, where the problems were goal-based, the 2011 International Probabilistic Planning Competition (IPPC-2011) emphasized finite-horizon reward maximization problems with large branching factors. These MDPs modeled more realistic planning scenarios and presented challenges to the previous state-of-the-art planners (e. g. , those from IPPC-2008), which were primarily based on domain determinization - a technique more suited to goal-oriented MDPs with small branching factors. Moreover, large branching factors render the existing implementations of RTDP- and LAO-style algorithms inefficient as well. In this paper we present GLUTTON, our planner at IPPC-2011 that performed well on these challenging MDPs. The main algorithm used by GLUTTON is LR2TDP, an LRTDP-based optimal algorithm for finite-horizon problems centered around the novel idea of reverse iterative deepening. We detail LR2TDP itself as well as a series of optimizations included in GLUTTON that help LR2TDP achieve competitive performance on difficult problems with large branching factors -- subsampling the transition function, separating out natural dynamics, caching transition function samples, and others. Experiments show that GLUTTON and PROST, the IPPC-2011 winner, have complementary strengths, with GLUTTON demonstrating superior performance on problems with few high-reward terminal states.

ICAPS Conference 2011 Conference Paper

Heuristic Search for Generalized Stochastic Shortest Path MDPs

• Andrey Kolobov
• Mausam
• Daniel S. Weld
• Hector Geffner

Research in efficient methods for solving infinite-horizon MDPs has so far concentrated primarily on discounted MDPs and the more general stochastic shortest path problems (SSPs). These are MDPs with 1) an optimal value function V* that is the unique solution of Bellman equation and 2) optimal policies that are the greedy policies w. r. t. V*. This paper's main contribution is the description of a new class of MDPs, that have well-defined optimal solutions that do not comply with either 1 or 2 above. We call our new class Generalized Stochastic Shortest Path (GSSP) problems. GSSP allows more general reward structure than SSP and subsumes several established MDP types including SSP, positive-bounded, negative, and discounted-reward models. While existing efficient heuristic search algorithms like LAO* and LRTDP are not guaranteed to converge to the optimal value function for GSSPs, we present a new heuristic-search-based family of algorithms, FRET (Find, Revise, Eliminate Traps). A preliminary empirical evaluation shows that FRET solves GSSPs much more efficiently than Value Iteration.

IJCAI Conference 2011 Conference Paper

Towards Scalable MDP Algorithms

• Andrey Kolobov
• Mausam
• Daniel S. Weld

The scalability of algorithms for solving Markov Decision Processes (MDPs) has been a limiting factor for MDPs as a modeling tool. This dissertation develops theoretical and empirical techniques for solving larger MDPs than was possible before, and aims to demonstrate the achieved progress by applying these new algorithms to a real-world problem.

AIJ Journal 2010 Journal Article

Automatically generating personalized user interfaces with Supple

• Krzysztof Z. Gajos
• Daniel S. Weld
• Jacob O. Wobbrock

Today's computer–human interfaces are typically designed with the assumption that they are going to be used by an able-bodied person, who is using a typical set of input and output devices, who has typical perceptual and cognitive abilities, and who is sitting in a stable, warm environment. Any deviation from these assumptions may drastically hamper the person's effectiveness—not because of any inherent barrier to interaction, but because of a mismatch between the person's effective abilities and the assumptions underlying the interface design. We argue that automatic personalized interface generation is a feasible and scalable solution to this challenge. We present our Supple system, which can automatically generate interfaces adapted to a person's devices, tasks, preferences, and abilities. In this paper we formally define interface generation as an optimization problem and demonstrate that, despite a large solution space (of up to 1017 possible interfaces), the problem is computationally feasible. In fact, for a particular class of cost functions, Supple produces exact solutions in under a second for most cases, and in a little over a minute in the worst case encountered, thus enabling run-time generation of user interfaces. We further show how several different design criteria can be expressed in the cost function, enabling different kinds of personalization. We also demonstrate how this approach enables extensive user- and system-initiated run-time adaptations to the interfaces after they have been generated. Supple is not intended to replace human user interface designers—instead, it offers alternative user interfaces for those people whose devices, tasks, preferences, and abilities are not sufficiently addressed by the hand-crafted designs. Indeed, the results of our study show that, compared to manufacturers' defaults, interfaces automatically generated by Supple significantly improve speed, accuracy and satisfaction of people with motor impairments.

ICAPS Conference 2010 Conference Paper

Classical Planning in MDP Heuristics: with a Little Help from Generalization

• Andrey Kolobov
• Mausam
• Daniel S. Weld

Computing a good policy in stochastic uncertain environments with unknown dynamics and reward model parameters is a challenging task. In a number of domains, ranging from space robotics to epilepsy management, it may be possible to have an initial training period when suboptimal performance is permitted. For such problems it is important to be able to identify when this training period is complete, and the computed policy can be used with high confidence in its future performance. A simple principled criteria for identifying when training has completed is when the error bounds on the value estimates of the current policy are sufficiently small that the optimal policy is fixed, with high probability. We present an upper bound on the amount of training data required to identify the optimal policy as a function of the unknown separation gap between the optimal and the next-best policy values. We illustrate with several small problems that by estimating this gap in an online manner, the number of training samples to provably reach optimality can be significantly lower than predicted offline using a Probably Approximately Correct framework that requires an input epsilon parameter.

AIJ Journal 2010 Journal Article

Panlingual lexical translation via probabilistic inference

• Mausam
• Stephen Soderland
• Oren Etzioni
• Daniel S. Weld
• Kobi Reiter
• Michael Skinner
• Marcus Sammer
• Jeff Bilmes

This paper introduces a novel approach to the task of lexical translation between languages for which no translation dictionaries are available. We build a massive translation graph, automatically constructed from over 630 machine-readable dictionaries and Wiktionaries. In this graph each node denotes a word in some language and each edge ( v i, v j ) denotes a word sense shared by v i and v j. Our current graph contains over 10, 000, 000 nodes and expresses more than 60, 000, 000 pairwise translations. The composition of multiple translation dictionaries leads to a transitive inference problem: if word A translates to word B which in turn translates to word C, what is the probability that C is a translation of A? The paper describes a series of probabilistic inference algorithms that solve this problem at varying precision and recall levels. All algorithms enable us to quantify our confidence in a translation derived from the graph, and thus trade precision for recall. We compile the results of our best inference algorithm to yield PanDictionary, a novel multilingual dictionary. PanDictionary contains more than four times as many translations as in the largest Wiktionary at precision 0. 90 and over 200, 000, 000 pairwise translations in over 200, 000 language pairs at precision 0. 8.

IJCAI Conference 2009 Conference Paper

• Andrey Kolobov
• Mausam
• Daniel S. Weld

Past approaches for solving MDPs have several weaknesses: 1) Decision-theoretic computation over the state space can yield optimal results but scales poorly. 2) Value-function approximation typically requires human-specified basis functions and has not been shown successful on nominal (“discrete”) domains such as those in the ICAPS planning competitions. 3) Replanning by applying a classical planner to a determinized domain model can generate approximate policies for very large problems but has trouble handling probabilistic subtlety [Little and Thiebaux, 2007]. This paper presents RETRASE, a novel MDP solver, which combines decision theory, function approximation and classical planning in a new way. RETRASE uses classical planning to create basis functions for value-function approximation and applies expected-utility analysis to this compact space. Our algorithm is memory-efficient and fast (due to its compact, approximate representation), returns high-quality solutions (due to the decisiontheoretic framework) and does not require additional knowledge from domain engineers (since we apply classical planning to automatically construct the basis functions). Experiments demonstrate that RETRASE outperforms winners from the past three probabilistic-planning competitions on many hard problems.

IJCAI Conference 2009 Conference Paper

• Peng Dai
• Mausam
• Daniel S. Weld

Recent progress on external-memory MDP solvers, in particular PEMVI [Dai et al. , 2008], has enabled optimal solutions to large probabilistic planning problems. However, PEMVI requires a human to manually partition the MDP before the planning algorithm can be applied — putting an added burden on the domain designer and detracting from the vision of automated planning. This paper presents a novel partitioning scheme, which automatically subdivides the state space into blocks that respect the memory constraints. Our algorithm first applies static domain analysis to identify candidates for partitioning, and then uses heuristic search to generate a ‘good’ partition. We evaluate the usefulness of our method in the context of PEMVI across many benchmark domains, showing that it can successfully solve extremely large problems in each domain. We also compare the performance of automatic partitioning with previously reported results using human-designed partitions. Experiments show that our algorithm generates significantly superior partitions, which speed MDP solving and also yield vast memory savings.

ICAPS Conference 2009 Conference Paper

Focused Topological Value Iteration

• Peng Dai 0001
• Mausam
• Daniel S. Weld

Topological value iteration (TVI) is an effective algorithm for solving Markov decision processes (MDPs) optimally, which 1) divides an MDP into strongly-connected components, and 2) solves these components sequentially. Yet, TVI’s usefulness tends to degrade if an MDP has large components, because the cost of the division process isn’t offset by gains during solution. This paper presents a new algorithm to solve MDPs optimally, focused topological value iteration (FTVI). FTVI addresses TVI’s limitations by restricting its attention to connected components that are relevant for solving the MDP. Specifically, FTVI uses a small amount of heuristic search to eliminate provably sub-optimal actions; this pruning allows FTVI to find smaller connected components, thus running faster. We demonstrate that our new algorithm outperforms TVI by an order of magnitude, averaged across several domains. Surprisingly, FTVI also significantly outperforms popular ‘heuristically-informed’ MDP algorithms such as LAO*, LRTDP, and BRTDP in many domains, sometimes by as much as two orders of magnitude. Finally, we characterize the type of domains where FTVI excels — suggesting a way to an informed choice of solver.

AAAI Conference 2008 Conference Paper

Intelligence in Wikipedia

• Daniel S. Weld
• Eytan Adar
• James Fogarty
• Kayur Patel

The Intelligence in Wikipedia project at the University of Washington is combining self-supervised information extraction (IE) techniques with a mixed initiative interface designed to encourage communal content creation (CCC). Since IE and CCC are each powerful ways to produce large amounts of structured information, they have been studied extensively — but only in isolation. By combining the two methods in a virtuous feedback cycle, we aim for substantial synergy. While previous papers have described the details of individual aspects of our endeavor [25, 26, 24, 13], this report provides an overview of the project’s progress and vision.

IJCAI Conference 2007 Conference Paper

• Mausam Mausam
• Piergiorgio Bertoli
• Daniel S. Weld

Markov Decision Processes are a powerful framework for planning under uncertainty, but current algorithms have difficulties scaling to large problems. We present a novel probabilistic planner based on the notion of hybridizing two algorithms. In particular, we hybridize GPT, an exact MDP solver, with MBP, a planner that plans using a qualitative (non-deterministic) model of uncertainty. Whereas exact MDP solvers produce optimal solutions, qualitative planners sacrifice optimality to achieve speed and high scalability. Our hybridized planner, HybPlan, is able to obtain the best of both techniques --- speed, quality and scalability. Moreover, HybPlan has excellent anytime properties and makes effective use of available time and memory.

ICAPS Conference 2007 Conference Paper

Evaluating Temporal Planning Domains

• William Cushing
• Daniel S. Weld
• Subbarao Kambhampati
• Mausam
• Kartik Talamadupula

The last eight years have seen dramatic progress in temporal planning as highlighted by the temporal track in the last three International Planning Competitions (IPC). However, our recent work, (Cushing et al. 2007), showed that most of the competition winning planners are only complete for very restricted forms of temporal planning languages that are in a sense indistinguishable from STRIPS. In this paper we consider the impact of those results on the design of benchmark temporal planning domains, and by extension, the temporal planning competition. We start by setting out to verify our speculation that the competition domains are temporally simple. This turns out to be tricky, and we develop a set of increasingly powerful analytic methods for domain analysis. Our analysis establishes that the benchmark domains are indeed inherently sequential (i. e., do not require concurrency). We suggest some real-world domains with required concurrency, and use a compilation argument to show that these are harder in the sense that they correspond to longer sequential plans. We conclude with the argument that temporal planners should be evaluated on both inherently sequential domains as well as those requiring concurrency.

ICAPS Conference 2006 Conference Paper

Challenges for Temporal Planning with Uncertain Durations

• Mausam
• Daniel S. Weld

We investigate the problem of temporal planning with concurrent actions having stochastic durations, especially in the context of extended-state-space based planners. The problem is challenging because stochastic durations lead to an explosion in the space of possible decision-epochs, which exacerbates the familiar challenge of growth in executable action combinations caused by concurrency.

ICAPS Conference 2005 Conference Paper

Concurrent Probabilistic Temporal Planning

• Mausam
• Daniel S. Weld

Probabilistic planning problems are often modeled as Markov decision processes (MDPs), which assume that a single unit-length action is executed per decision epoch. However, in the real world it is common to execute several actions in parallel. This paper presents efficient methods for solving probabilistic planning problems with concurrent, durative actions. We extend Concurrent MDPs, MDPs which allow multiple instantaneous actions to be executed simultaneously, by adding explicit action durations. We present two novel admissible heuristics and one inadmissible heuristic to speed up the convergence. We also develop a novel notion of hybridizing an optimal and an approximate algorithm to yield a hybrid algorithm, which quickly generates high-quality policies. Experiments show that all our heuristics speedup the policy construction significantly. Furthermore, our approximate hybrid algorithm runs up to two orders of magnitude faster than other methods, while producing policies close to optimal.

AIJ Journal 2005 Journal Article

Unsupervised named-entity extraction from the Web: An experimental study

• Oren Etzioni
• Michael Cafarella
• Doug Downey
• Ana-Maria Popescu
• Tal Shaked
• Stephen Soderland
• Daniel S. Weld
• Alexander Yates

The KnowItAll system aims to automate the tedious process of extracting large collections of facts (e. g. , names of scientists or politicians) from the Web in an unsupervised, domain-independent, and scalable manner. The paper presents an overview of KnowItAll's novel architecture and design principles, emphasizing its distinctive ability to extract information without any hand-labeled training examples. In its first major run, KnowItAll extracted over 50, 000 class instances, but suggested a challenge: How can we improve KnowItAll's recall and extraction rate without sacrificing precision? This paper presents three distinct ways to address this challenge and evaluates their performance. Pattern Learning learns domain-specific extraction rules, which enable additional extractions. Subclass Extraction automatically identifies sub-classes in order to boost recall (e. g. , “chemist” and “biologist” are identified as sub-classes of “scientist”). List Extraction locates lists of class instances, learns a “wrapper” for each list, and extracts elements of each list. Since each method bootstraps from KnowItAll's domain-independent methods, the methods also obviate hand-labeled training examples. The paper reports on experiments, focused on building lists of named entities, that measure the relative efficacy of each method and demonstrate their synergy. In concert, our methods gave KnowItAll a 4-fold to 8-fold increase in recall at precision of 0. 90, and discovered over 10, 000 cities missing from the Tipster Gazetteer.

AAAI Conference 2004 Conference Paper

Methods for Domain-Independent Information Extraction from the Web: An Experimental Comparison

• Oren Etzioni
• Doug Downey
• Tal Shaked
• Daniel S. Weld

Our KNOWITALL system aims to automate the tedious process of extracting large collections of facts (e.g., names of scientists or politicians) from the Web in an autonomous, domain-independent, and scalable manner. In its first major run, KNOWITALL extracted over 50,000 facts with high precision, but suggested a challenge: How can we improve KNOWITALL’s recall and extraction rate without sacrificing precision? This paper presents three distinct ways to address this challenge and evaluates their performance. Rule Learning learns domain-specific extraction rules. Subclass Extraction automatically identifies sub-classes in order to boost recall. List Extraction locates lists of class instances, learns a “wrapper” for each list, and extracts elements of each list. Since each method bootstraps from KNOWITALL’s domain-independent methods, no hand-labeled training examples are required. Experiments show the relative coverage of each method and demonstrate their synergy. In concert, our methods gave KNOWITALL a 4-fold to 19-fold increase in recall, while maintaining high precision, and discovered 10,300 cities missing from the Tipster Gazetteer.

AAAI Conference 2004 Conference Paper

Solving Concurrent Markov Decision Processes

• Mausam
• Daniel S. Weld

Typically, Markov decision problems (MDPs) assume a single action is executed per decision epoch, but in the real world one may frequently execute certain actions in parallel. This paper explores concurrent MDPs, MDPs which allow multiple non-conflicting actions to be executed simultaneously, and presents two new algorithms. Our first approach exploits two provably sound pruning rules, and thus guarantees solution optimality. Our second technique is a fast, sampling-based algorithm, which produces close-to-optimal solutions extremely quickly. Experiments show that our approaches outperform the existing algorithms producing up to two orders of magnitude speedup.

IJCAI Conference 2003 Conference Paper

Automatically Personalizing User Interfaces

• Daniel S. Weld
• Corin Anderson
• Pedro Domingos
• Oren Etzioni
• Krzysztof Gajos
• Tessa Lau
• Steve Wolfinan

Todays computer interfaces are one-size-fits-all. Users with little programming experience have very limited opportunities to customize an interface to their task and work habits. Furthermore, the overhead induced by generic interfaces will be proportionately greater on small form-factor PDAs, embedded applications and wearable devices. Automatic personalization may greatly enhance user productivity, but it requires advances in customization (explicit, user-initiated change) and adaptation (interface-initiated change in response to routine user behavior). In order to improve customization, we must make it easier for users to direct these changes. In order to improve adaptation, we must better predict user behavior and navigate the inherent tension between the dynamism of automatic adaptation and the stability required in order for the user to predict the computers behavior and maintain control. This paper surveys a decade's work on customization and adaptation at the University of Washington, distilling the lessons we have learned.

KER Journal 2001 Journal Article

Combining linear programming and satisfiability solving for resource planning

• STEVEN A. WOLFMAN
• Daniel S. Weld

Compilation to Boolean satisfiability has become a powerful paradigm for solving artificial intelligence problems. However, domains that require metric reasoning cannot be compiled efficiently to satisfiability even if they would otherwise benefit from compilation. We address this problem by combining techniques from the artificial intelligence and operations research communities. In particular, we introduce the LCNF (Linear Conjunctive Normal Form) representation that combines propositional logic with metric constraints. We present LPSAT (Linear Programming plus SATisfiability), an engine that solves LCNF problems by interleaving calls to an incremental Simplex algorithm with systematic satisfaction methods. We explore several techniques for enhancing LPSAT's efficiency and expressive power by adjusting the interaction between the satisfiability and linear programming components of LPSAT. Next, we describe a compiler that converts metric resource planning problems into LCNF for processing by LPSAT. Finally, the experimental section of the paper explores several optimisations to LPSAT, including learning from constraint failure and randomised cutoffs.

AIJ Journal 2000 Journal Article

Intelligent Internet systems

• Alon Y. Levy
• Daniel S. Weld

ICML Conference 2000 Conference Paper

Version Space Algebra and its Application to Programming by Demonstration

• Tessa Lau
• Pedro M. Domingos
• Daniel S. Weld

IJCAI Conference 1999 Conference Paper

Temporal Planning with Mutual Exclusion Reasoning

• David E. Smith
• Daniel S. Weld

Many planning domains require a richer notion of time in which actions can overlap and have different durations. The key to fast performance in classical planners (e. g. , Graphplan, IPP, and Blackbox) has been the use of a disjunctive representation with powerful mutual exclusion reasoning. This paper presents T G P, a new algorithm for temporal planning. TGP operates by incrementally expanding a compact planning graph representation that handles actions of differing duration. The key to TGP performance is tight mutual exclusion reasoning which is based on an expressive language for bounding mutexes and includes mutexes between actions and propositions. Our experiments demonstrate that mutual exclusion reasoning remains valuable in a rich temporal setting.

IJCAI Conference 1999 Conference Paper

The LPSAT Engine & its Application to Resource Planning

• Steven A
• Wolfinan
• Daniel S. Weld

Compilation to boolean satisfiability has become a powerful paradigm for solving AI problems. However, domains that require metric reasoning cannot be compiled efficiently to SAT even if they would otherwise benefit from compilation. We address this problem by introducing the LCNF representation which combines propositional logic with metric constraints. We present LPSAT, an engine which solves LCNF problems by interleaving calls to an incremental simplex algorithm with systematic satisfaction methods. We describe a compiler which converts metric resource planning problems into LCNF for processing by LPSAT. The experimental section of the paper explores several optimizations to LPSAT, including learning from constraint failure and randomized cutoffs.

ICAPS Conference 1998 Conference Paper

Conditional Effects in Graphplan

• Corin R. Anderson
• David E. Smith 0001
• Daniel S. Weld

Graphplanhas attracted considerable interest because of its extremelyhigh performance, but the algorithm’s inability to handle action representations moreexpressive than STRIPSis a major limitation. In particular, extending Graphplanto handle conditional effects is a surprisingly subtle enterprise. In this paper, we describe the space of possible alternatives, and then concentrate on one particular approach we call factored expansion. Factored expansion splits an action with conditional effects into several newactions called components, one for each conditional effect. Because these action components are not independent, factored expansion complicates both the mutual exclusion and backwardchaining phases of Graphplan. As compensation, factored expansion often produces dramatically smaller domainmodels than does the more obvious full-expansion into exclusive STRIPSactions. Wepresent experimental results showingthat factored expansion dominatesfull expansion on large problems.

AAAI Conference 1998 Conference Paper

Extending Graphplan to Handle Uncertainty & Sensing Actions

• Daniel S. Weld

If an agent does not have completeinformation about the world-state, it must reason about alternative possible states of the world and consider whether any of its actions can reduce the uncertainty. Agents controlled by a contingent planner seek to generate a robust plan, that accounts for and handles all eventualities, in advance of execution. Thus a contingent plan mayinclude sensing actions which gather information that is later used to select between different plan branches. Unfortunately, previous contingent planners suffered defects such as confusedsemantics, incompleteness, and inefficiency. In this paper wedescribe SGP, a descendant of Graphplan that solves contingent planning problems. SGPdistinguishes between actions that sense the value of an unknown proposition from those that change its value. SGPdoes not suffer from the forms of incompleteness displayed by CNLP and Cassandra. Furthermore, SGP is relatively fast.

IJCAI Conference 1997 Conference Paper

Automatic SAT-Compilation of Planning Problems

• Michael D. Ernst
• Todd D. Millstein
• Daniel S. Weld

AIJ Journal 1997 Journal Article

Sound and efficient closed-world reasoning for planning

• Oren Etzioni
• Keith Golden
• Daniel S. Weld

Closed-world inference—an essential component of many planning algorithms—is the process of determining that a logical sentence is false based on its absence from a knowledge base, or the inability to derive it. We describe a novel method for closed-world inference and update over the first-order theories of action used by planning algorithms such as nonlin, tweak and ucpop. We show the method to be sound and efficient, but incomplete. In our experiments, closed-world inference consistently averaged about 2 milliseconds while updates averaged approximately 1. 2 milliseconds. Furthermore, we demonstrate that incompleteness is nonproblematic in practice, since our mechanism makes over 99% of the desired inferences. We incorporated our method into the xii planner, which supports our Internet Softbot (software robot). The technique cut the number of actions executed by the Softbot by a factor of one hundred, and resulted in a corresponding speedup to xii.

AAAI Conference 1996 Conference Paper

Declarative Camera Control for Automatic Cinematography

• David B. Christianson
• Li-Wei He
• Daniel S. Weld

Animations generated by interactive 3D computer graphics applications are typically portrayed either from a particular character’ s point of view or from a small set of strategically-placed viewpoints. By ignoring camera placement, such applications fail to realize important storytelling capabilities that have been explored by cinematographers for many years. In this paper, we describe several of the principles of cinematography and show how they can be formalized into a declarative language, called the Declarutive Camera Control Language (DCCL). We describe the application of DCCL within the context of a simple interactive video game and argue that DCCL represents cinematic knowledge at the same level of abstraction as expert directors by encoding 16 idioms from a film textbook. These idioms produce compelling animations, as demonstrated on the accompanying videotape.

ICAPS Conference 1996 Conference Paper

Least-Commitment Action Selection

• Marc T. Friedman
• Daniel S. Weld

The principle of least commitment was embraced early in planning research. Hierarchical task networks (HTNs) reason about high-level tasks without committing to specific low-level steps. Partial-order planning arose from a complementary desire to avoid unnecessary ordering commitments. But most of today’s partial-order planning algorithms commit to a single producing step when supporting an open condition -- even when multiple alternatives exist. Each possibility results in a different child plan, and therefore a branch in the search tree. If the various choices have common features, computation may be duplicated unnecessarily on the various branches. The FABIAN planner attempts to avoid such waste. FABIAN separates the decision to add a step from the choice of which step to add. FABIAN supports an open condition by adding an abstract action to the plan representing the disjunction of possible new supporting steps; only later does it refine this choice to a particular concrete action. We show that this abstraction can lead to exponential savings, and argue that in the worst case FABIAN never explores more than a slightly larger space of plans than does a traditional planner such as SNLP.

ICAPS Conference 1996 Invited Paper

Planning-Based Control of Software Agents

• Daniel S. Weld

The exponential growth of the Internet has produced a labyrinth of databases and services. Almost any type of information is available somewhere, but most users can’t find it, and even experts waste untold time searching for appropriate information sources. Many researchers argue that software agents will remedy the situation by acting as personal assistants and automatically accessing multiple sources, integrating informa-tion, and acting on the user’s behalf. Indeed, this vision is so widely accepted (at least in the AI community) that I won’t dwell on it further. Instead, I’ll describe some of the software robots we've built at the University of Washington, explain why I think planning is a crucial technology for their control, summarize the lessons we've learned by their construction, and suggest directions for future work in the area. Note that this paper is not intended to he a comprehensive survey of important softbot projects -- there are far too many interesting systems for me to describe them all. I focus on University of Washington projects, because I am most familiar with this body of work and because the Washington softbots have emphasized planning-based control.

AIJ Journal 1995 Journal Article

An algorithm for probabilistic planning

• Nicholas Kushmerick
• Steve Hanks
• Daniel S. Weld

We define the probabilistic planning problem in terms of a probability distribution over initial world states, a boolean combination of propositions representing the goal, a probability threshold, and actions whose effects depend on the execution-time state of the world and on random chance. Adopting a probabilistic model complicates the definition of plan success: instead of demanding a plan that provably achieves the goal, we seek plans whose probability of success exceeds the threshold. In this paper, we present buridan, an implemented least-commitment planner that solves problems of this form. We prove that the algorithm is both sound and complete. We then explore buridan's efficiency by contrasting four algorithms for plan evaluation, using a combination of analytic methods and empirical experiments. We also describe the interplay between generating plans and evaluating them, and discuss the role of search control in probabilistic planning.

UAI Conference 1994 Conference Paper

A Probablistic Model of Action for Least-Commitment Planning with Information Gathering

• Denise Draper
• Steve Hanks
• Daniel S. Weld

AIJ Journal 1994 Journal Article

Partial-order planning

• Anthony Barrett
• Daniel S. Weld

Although most people believe that planners that delay step-ordering decisions as long as possible are more efficient than those that manipulate totally ordered sequences of actions, this intuition has received little formal justification or empirical validation. In this paper we do both, characterizing the types of domains that offer performance differentiation and the features that distinguish the relative overhead of three planning algorithms. As expected, the partial-order (nonlinear) planner often has an advantage when confronted with problems in which the specific order of the plan steps is critical. We argue that the observed performance differences are best understood with an extension of Korf's taxonomy of subgoal collections. Each planner quickly solved problems whose subgoals were independent or trivially serializable, but problems with laboriously serializable or nonserializable subgoals were intractable for all planners. Since different plan representations induce distinct search spaces, the subgoals for a given problem may be trivially serializable for one planner, laboriously serializable for another, and nonserializable for a third. We contend that the partial-order representation yields superior performance because it more frequently results in trivial serializability.

ICAPS Conference 1994 Conference Paper

Probabilistic Planning with Information Gathering and Contingent Execution

• Denise Draper
• Steve Hanks
• Daniel S. Weld

Most AI representations and algorithms for plan generation have not included the concept of informationproducing actions (also called diagnostics, or tests, in the decision making literature). Wepresent planning representation and algorithm that models information-producing actions and constructs plans that exploit the information produced by those actions. Weextend the BURIDAN (Knshmerick et al. 1994) probabilistic planning algorithm, adapting the action representation to modelthe behavior of imperfect sensors, and combineit with a frameworkfor contingent action that extends the CNLP algorithm (Peot and Smith1992) for conditioned execution. The result, C-BURIDAN, is an implemented planner that builds plans with probabilistic information-producingactions and contingent execution. algorithm (Peot and Smith 1992). C-BURIDAN takes as input a probability distribution over initial world states, a goal expression, a set of action descriptions, and a probability threshold, and produces a contingent plan that makes the goal expression true with a Iprobability no less than the threshold.

AIJ Journal 1993 Journal Article

Representations of commonsense knowledge

• Daniel S. Weld

AIJ Journal 1992 Journal Article

Reasoning about model accuracy

• Daniel S. Weld

Although computers are widely used to simulate complex physical systems, crafting the underlying models that enable computer analysis remains a difficult job with only a small number of computer tools for support. Our goal is to mechanize this process by building an automated model management system that evaluates simplifying assumptions and selects appropriate perspectives. In this paper we present our initial results: a framework for dynamically changing model accuracy based on model sensitivity analysis. We show how to perform model sensitivity analysis efficiently when one model is a fitting approximation of the other. Finally, we discuss two implementations of our technique in programs that perform • • query-directed simplification by adding bounding abstractions, and • • discrepancy-driven refinement. Our programs use a mixture of qualitative and quantitative techniques with both symbolic and numeric computations.

AAAI Conference 1990 Conference Paper

Approximation Reformulations

• Daniel S. Weld

Although computers are widely used to simulate complex physical systems, crafting the underlying models that enable computer analysis remains difficult. When a model is created for one task, it is often impossible to reuse the model for another purpose because each task requires a different set of simplifying assumptions. By representing modeling assumptions explicitly as approximation reformulations, we have developed qualitative techniques for switching between models. We assume that automated reasoning proceeds in three phases: 1) model selection, 2) quantitative analysis using the model, and 3) validation that the assumptions underlying the model were appropriate for the task at hand. If validation discovers a serious discrepancy between predicted and observed behavior, a new model must be chosen. We present a domain independent method for performing this model shift when the models are related by an approximation reformulation and describe a Common Lisp implementation of the theory.

AIJ Journal 1990 Journal Article

Exaggeration

• Daniel S. Weld

Exaggeration is a technique for solving comparative analysis problems by considering extreme perturbations to a system. For example, exaggeration answers the question “What happens to the output temperature of a heat exchanger if fluid flow rate increases? ” by simulating the behavior of an exchanger with infinite flow rate. Exaggeration is implemented as a sequence of three phases: transform, simulate, and scale. The transform phase takes a comparative analysis problem and generates the description of an exaggerated system. The simulate phase predicts the behavior of the transformed system. Finally, the scale phase compares the original and exaggerated behaviors to answer the original comparative analysis question. This paper explains the theoretical basis of exaggeration, describes an implementation that has solved over fifty problems, and compares exaggeration with the differential qualitative (DQ) analysis approach to comparative analysis.

AIJ Journal 1989 Journal Article

The psychology of everyday things

• Daniel S. Weld

AIJ Journal 1988 Journal Article

Comparative analysis

• Daniel S. Weld

Comparative analysis is the problem of predicting how a system will react to perturbations in its parameters, and why. For example, comparative analysis could be asked to explain why the period of an oscillating spring/block system would increase if the mass of the block were larger. This paper formalizes the problem of comparative analysis and presents a technique, differential quantitative (DQ) analysis, which solves the task, providing explanations suitable for use by design systems, automated diagnosis, intelligent tutoring systems, and explanation-based generalization. DQ analysis uses inference rules to deduce qualitative information about the relative change of system parameters. Multiple perspectives are used to represent relative change values over intervals of time. Differential analysis has been implemented, tested on a dozen examples, and proven sound. Unfortunately, the technique is incomplete; it always terminates, but does not always return an answer.

AAAI Conference 1988 Conference Paper

Exaggeration

• Daniel S. Weld

AIJ Journal 1988 Journal Article

Women, fire, and dangerous things

• Daniel S. Weld

AIJ Journal 1986 Journal Article

The use of aggregation in causal simulation

• Daniel S. Weld

Aggregation is an abstraction technique for dynamically creating new descriptions of a system's behavior. Aggregation works by detecting repeating cycles of processes and creating a continuous process description of the cycle's behavior. Since this behavioral abstraction results in a continuous process, the powerful transition analysis technique may be applied to determine the system's final state. This paper reports on a program which uses aggregation to perform causal simulation in the domain of molecular genetics. A detailed analysis of aggregation indicates the requirements and limitations of the technique as well as problems for future research.

IJCAI Conference 1985 Conference Paper

Combining Discrete and Continuous Process Models

• Daniel S. Weld