David Mcallester

Evidence for Invariants in Local Search (2003)

In recent work we showed that planning problems can be efficiently solved by general propositional satisfiability algorithms (Kautz and Selman 1996). A key issue in this approach is the development...

David Mcallester, Bart Selman, Henry Kautz

It is well known that the performance of a stochastic local search procedure depends upon the setting of its noise parameter, and that the optimal setting varies with the problem distribution. It is...

Concentration Inequalities for the Missing Mass and for Histogram Rule Error (2002)

David Mcallester, Luis Ortiz

This paper gives distribution-free concentration inequalities for the missing mass and the error rate of histogram rules. Negative association methods can be used to reduce these concentration...

ATTac-2001: A Learning, Autonomous Bidding Agent (2002)

Peter Stone, Robert E. Schapire, Janos A. Csirik, Michael L. Littman, David Mcallester

Auctions are becoming an increasingly popular method for transacting business, especially over the Internet. This paper presents a general approach to building autonomous bidding agents to bid in...

Observations on Cognitive Judgments (2002)

ATT-CMUnited-2000: Third Place Finisher in the Robocup-2000 Simulator League (2002)

It is obvious to anyone familiar with the rules of the game of chess that a king on an empty board can reach every square. It is true, but not obvious, that a knight can reach every square. Why is...

Patrick Riley, Peter Stone, David Mcallester, Manuela Veloso

Introduction The ATT-CMUnited-2000 simulator team nished in third place at Robocup2000. It was one of only three teams to nish ahead of the previous year's champion, CMUnited-99. In controlled...

Modeling Auction Price Uncertainty Using Boosting-based Conditional Density Estimation (2002)

Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman

In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...

Machine Learning: Proceedings of the Nineteenth International Conference, 2002. Modeling Auction Price Uncertainty (2002)

Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman

In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...

Machine Learning: Proceedings of the Nineteenth International Conference, 2002. Modeling Auction Price Uncertainty (2002)

Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman

In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...

Relating Probabilistic Grammars and Automata (2002)

Steven Abney, David Mcallester, Fernando Pereira

Both probabilistic context-free grammars (PCFGs) and shift-reduce probabilistic pushdown automata (PPDAs) have been used for language modeling and maximum likelihood parsing. We investigate the...

ATTac-2001: A Learning, Autonomous Bidding Agent (2002)

Peter Stone, Robert E. Schapire, Michael L. Littman, David Mcallester

This paper presents a general approach to building autonomous bidding agents to bid in multiple simultaneous auctions for interacting goods. The core of our approach is learning a model of the...

Modeling Auction Price Uncertainty Using Boosting-based Conditional Density Estimation (2002)

Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman

In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...

Logical Algorithms (2002)

Ganzinger,Harald, McAllester,David

It is widely accepted that many algorithms can be concisely and clearly expressed as logical inference rules. However, logic programming has been inappropriate for the study of the running time of...

Logical Algorithms (2002)

Ganzinger, Harald, McAllester, David, Stuckey, Peter J.

It is widely accepted that many algorithms can be concisely and clearly expressed as logical inference rules. However, logic programming has been inappropriate for the study of the running time of...

Learning Theory and Language Modeling (2001)

On the Complexity Analysis of Static Analyses (2001)

Here we consider some of our recent work on Good-Tuing estimators in the larger context of learning theory and language modeling. The Good-turing estimators have played a significant role in natural...

An Indexed Model of Recursive Types for Foundational Proof-Carrying Code (2001)

. This paper argues that for many algorithms, and static analysis

An Architecture for Action Selection in Robotic Soccer (2001)

The proofs of "traditional" proof carrying code (PCC) are type-specialized in the sense that they require axioms about a specific type system. In contrast, the proofs of foundational PCC explicitly...

Peter Stone, David Mcallester

CMUnited-99 was the 1999 RoboCup robotic soccer simulator league champion. In the RoboCup-2000 competition, CMUnited-99 was entered again and despite being publicly available for the entire year, it...

Learning Theory and Language Modeling (2001)

A Statistical Mechanics Approach to Large Deviation Theorems (2001)

Here we consider some of our recent work on Good-Tuing estimators in the

David Mcallester, Att Shannon Labrotories

Chernoff bounds and related large deviation bounds have a wide variety of applications in statistics and learning theory. This paper proves that for any real-valued random variable X the probability...

Inference Using Formal Logics (2001)

The Horn Mu-calculus (2001)

Introduction Logic is fundamental to a variety of disciplines. Logic provides insight into the nature of mathematics and human mathematical reasoning. Logic provides insight into the syntax and...

Witold Charatonik, David Mcallester, Damian Niwinski, Andreas Podelski, Igor Walukiewicz

The Horn µ-calculus is a logic programming language allowing arbitrary nesting of least and greatest fixed points. The Horn µ-programs can naturally expresses safety and liveness properties for...

A new meta-complexity theorem for bottom-up logic programs (2001)

Ganzinger,Harald, McAllester,David

Nontrivial meta-complexity theorems, proved once for a programming language as a whole, facilitate the presentation and analysis of particular algorithms. This paper gives a new meta-complexity...

A new meta-complexity theorem for bottom-up logic programs (2001)

Ganzinger, Harald, McAllester, David, Goré, Rajeev, Leitsch, Alexander, Nipkow, Tobias

Nontrivial meta-complexity theorems, proved once for a programming language as a whole, facilitate the presentation and analysis of particular algorithms. This paper gives a new meta-complexity...

Keeping the Ball from CMUnited-99 (2000)

David Mcallester, Peter Stone

. This paper presents preliminary results achieved during our current development of a team for simulated robotic soccer in the RoboCup soccer server [2]. We have constructed a team that plays a...

An Architecture for Action Selection in Robotic Soccer (2000)

Peter Stone, David Mcallester

CMUnited-99 was the 1999 RoboCup robotic soccer simulator league champion. In the RoboCup-2000 competition, CMUnited-99 was entered again and despite being publicly available for the entire year, it...

Nonexpressibility of Fairness and Signaling (2000)

David Mcallester, Prakash Panangaden, Vasant Shanbhogue

In this paper we establish new expressiveness results for indeterminate dataflow primitives. We consider split primitives with three differing fairness assumptions and show that they are strictly...

Hardening Soft Information Sources (2000)

William W. Cohen, Henry Kautz, David Mcallester

The web contains a large quantity of unstructured information. In many cases, it is possible to heuristically extract structured information, but the resulting databases are "soft": they contain...

Polynomial-time Computation via Local Inference Relations (2000)

Robert Givan, David Mcallester

We consider the concept of a local set of inference rules. A local rule set can be automatically transformed into a rule set for which bottom-up evaluation terminates in polynomial time. The...

Polynomial-time Computation via Local Inference Relations (2000)

Givan, Robert, McAllester, David

We consider the concept of a local set of inference rules. A local rule set can be automatically transformed into a rule set for which bottom-up evaluation terminates in polynomial time. The...

Generalization Bounds for Decision Trees (2000)

Computable Shell Decomposition Bounds (2000)

We derive a new bound on the error rate for decision trees. The bound depends both on the structure of the tree and the specific sample (not just the size of the sample). This bound is tighter than...

John Langford, David Mcallester

Haussler, Kearns, Seung and Tishby introduced the notion of a shell decomposition of the union bound as a means of understanding certain empirical phenomena in learning curves such as phase...

On the Convergence Rate of Good-Turing Estimators (2000)

Computable Shell Decomposition Bounds (2000)

Good-Turing adjustments of word frequencies are an important tool in natural language modeling. In particular, for any sample of words, there is a set of words not occuring in that sample. The total...

John Langford, David Mcallester

Haussler, Kearns, Seung and Tishby introduced the notion of a shell decomposition of the union bound as a means of understanding certain empirical phenomena in learning curves such as phase...

Istituto Per La Ricerca Scientifica E Tecnologica (2000)

Roberto Sebastiani, David Mcallester

Traditional results in modal logics state that, if a formula ' is satisfiable in K (K-satisfiable), then it has a Kripke model M s.t. jjM jj 2 j'j , jjM jj being the number of states of M and j'j the...

Hardening Soft Information Sources (2000)

William Cohen, Henry Kautz, David Mcallester

The web contains a large quantity of unstructured information. In many cases, it is possible to heuristically extract structured information, but the resulting databases are "soft": they contain...

Boosting with Multi-Way Branching in Decision Trees (2000)

Boosting using Branching Programs (2000)

It is known that decision tree learning can be viewed as a form of boosting. However, existing boosting theorems for decision tree learning allow only binary-branching trees and the generalization to...

On the Convergence Rate of Good-Turing Estimators (2000)

It is known that decision tree learning can be viewed as a form of boosting. Given a weak learning hypothesis one can show that the training error of a decision tree declines as jT j Gammafi where jT...

Policy Gradient Methods for Reinforcement Learning with Function Approximation (2000)

Good-Turing adjustments of word frequencies are an important tool in natural language modeling. In particular, for any sample of words, there is a set of words not occuring in that sample. The total...

Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour

Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically...

Policy Gradient Methods for Reinforcement Learning with Function Approximation (2000)

Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour

Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically intractable.

Unknown (2000)

Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour

Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically intractable.

New upper bounds for satisfiability in modal logics -- the case-study of modal K (2000)

Roberto Sebastiani, David Mcallester

Traditional results in modal logics state that, if a formula ' is satisfiable in K (K-satisfiable), then it has a Kripke model M s.t. jjM jj 2 j'j , jjM jj being the number of states of M and j'j the...

Boosting with Multi-Way Branching in Decision Trees (1999)

It is known that decision tree learning can be viewed as a form of boosting. However, existing boosting theorems for decision tree learning allow only binary-branching trees and the generalization to...

Truth Maintenance (1999)

Effective Bayesian Inference for Stochastic Programs (1999)

General purpose truth maintenance systems have received considerable attention in the past few years. This paper discusses the functionality of truth maintenance systems and compares various existing...

Daphne Koller, David Mcallester, Avi Pfeffer

In this paper, we propose a stochastic version of a general purpose functional programming language as a method of modeling stochastic processes. The language contains random choices, conditional...

Generalization Bounds for Decision Trees (1999)

On the Complexity Analysis of Static Analyses (1999)

We derive a new bound on the error rate for decision trees. The bounds depends both on the structure of the tree and the specific sample (not just the size of the sample). This bound is tighter than...

Bellman Equations for Stochastic Programs (1999)

. This paper argues that for many algorithms, and static analysis algorithms in particular, bottom-up logic program presentations are clearer and simpler to analyze, for both correctness and...

Policy Gradient Methods for Reinforcement Learning with Function Approximation (1999)

. This paper gives a model-checking style algorithm for verifying the decision-theoretic utility of a hand-written robot controller. The paper presents a simple Turing-complete programming language...

Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour

Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically...

ATT Labs -- Research, 180 Park Avenue, Florham Park, NJ 07932 (1999)

Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour

Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically...

Policy Gradient Methods for (1999)

Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour

Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically intractable.

Computational Challenges in Propositional Reasoning and Search (1999)

Bart Selman, Henry Kautz, David Mcallester

The past several years have seen much progress in the area of propositional reasoning and satisfiability testing. There is a growing consensus by researchers on the key technical challenges that need...

Tarskian Set Constraints (1999)

Robert Givan, David Mcallester, Carl Witty, Dexter Kozen

We investigate set constraints over set expressions with Tarskian functional and relational operations. Unlike the Herbrand constructor symbols used in recent set constraint formalisms, the meaning...

Boosting with Multi-Way Branching in Decision Trees (1999)

Relating Probabilistic Grammars and Automata (1999)

It is known that decision tree learning can be viewed as a form of boosting. However, existing boosting theorems for decision tree learning allow only binary-branching trees and the generalization to...

Steven Abney, David Mcallester, Fernando Pereira

Both probabilistic context-free grammars (PCFGs) and shift-reduce probabilistic pushdown automata (PPDAs) have been used for language modeling and maximum likelihood parsing. We investigate the...

Bart Selman, Henry Kautz, (1999)

Bart Selman, Henry Kautz, David Mcallester

The past several years have seen much progress in the area of propositional reasoning and satisfiability testing. There is a growing consensus by researchers on the key technical challenges that need...

Evidence for Invariants in Local Search (1999)

David Mcallester, Bart Selman, Henry Kautz

It is well known that the performance of a stochastic local search procedure depends upon the setting of its noise parameter, and that the optimal setting varies with the problem distribution. It is...

Henry Kautz, David McAllester, and Bart Selman (1999)

Encoding Plans in Propositional Logic (1999)

Stochastic search has recently been shown to be successful for solving large boolean satisfiability problems. However, systematic methods tend to be more effective in problem domains with a large...

Object Conversion is Type-Preserving (1999)

In recent work we showed that planning problems can be efficiently solved by general propositional satisfiability algorithms (Kautz and Selman 1996). A key issue in this approach is the development...

New upper bounds for satisfiability in modal logics -- the case-study of modal K (1999)

Closure conversion is a program transformation widely used in modern compilers. For a variety of reasons it is desirable that compilation preserve types. We consider a closure conversion mapping e to...

Roberto Sebastiani, David Mcallester

Traditional results in modal logics state that, if a formula ' is satisfiable in K (K-satisfiable), then it has a Kripke model M s.t. jjM jj 2 j'j , jjM jj being the number of states of M and j'j the...

Effective Bayesian Inference for Stochastic Programs (1999)

Daphne Koller, David Mcallester, Avi Pfeffer

In this paper, we propose a stochastic version of a general purpose functional programming language as a method of modeling stochastic processes. The language contains random choices, conditional...

Boolean Classes, (1998)

McAllester,David, Zabih,Ramin

Object-oriented programming languages all involve the notions of class and object. The authors extend the notion of class so that any Boolean combination of classes is also a class. Boolean classes...

Taxonomic Syntax for First Order Inference. (1998)

McAllester, David, Given, Bob

Most knowledge representation languages are based on classes and taxonomic relationships between classes. Taxonomic hierarchies without defaults or exceptions are semantically equivalent to a...

Natural Language Syntax and First Order Inference. (1998)

McAllester, David, Givan, Robert

First order inference can be made more efficient by using non-standard syntax for first order logic. This paper shows how a fragment of English syntax under Montague semantics provides the foundation...

Automatic Recognition of Tractability in Inference Relations. (1998)

McAllester, David

A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations. The procedure can automatically recognize the tractability of the inference...

Natural Language Based Inference Procedures Applied to Schubert's Steamroller. (1998)

Givan, Robert, McAllester, David, Shalaby, Sameer

We have previously argued that the syntactic structure of natural language can be exploited to construct powerful polynomial time inference procedures. This paper supports the earlier arguments by...

Systematic Nonlinear Planning. (1998)

McAllester, David, Rosenblitt, David

This paper presents a simple, sound, complete, and systematic algorithm for domain independent STRIPS planning. Simplicity is achieved by starting with a ground procedure and then applying a general,...

Lifting Transformations. (1998)

McAllester, David, Siskind, Jeffrey

Lifting is a well known technique in resolution theorem proving, logic programming, and term rewriting. In this paper we formulate lifting as an efficiency-motivated program transformation applicable...

Observations on Cognitive Judgments. (1998)

McAllester, David

It is obvious to anyone familiar with the rules of the game of chess that a king on an empty board can reach every square. It is true, but not obvious, that a knight can reach every square. Why is...

Grammar Rewriting. (1998)

McAllester, David

We present a term rewriting procedure based on congruence closure that can be used with arbitrary equational theories. This procedure is motivated by the pragmatic need to prove equations in...

Tractable Inference Relations. (1998)

Givan, Robert, McAllester, David

We consider the concept of local sets of inference rules. Locality is a syntactic condition on rule sets which guarantees that the inference relation defined by those rules is polynomial time...

Proceedings of ECAI-96 Workshop: Empirical AI (1998)

Toby Walsh (editor, James Crawford, Paul Cohen, Ian Gent, David Mcallester, Steve Muggleton, ...

inference patterns reversed-engineered from previously successful expert systems are not a productivity tool [2]. These isolated MIP experiments must be explored. If they prove to be a general...

The Horn Mu-calculus (1998)

Witold Charatonik, David Mcallester, Damian Niwinski, Andreas Podelski, Igor Walukiewicz

The Horn -calculus is a logic programming language allowing arbitrary nesting of least and greatest fixed points. The Horn -programs can naturally expresses safety and liveness properties for...

Encoding Plans in Propositional Logic (1998)