Conditional measure estimation is a fundamental problem in statistics. Specific instances of this problem include classification, regression and conditional density estimation. This paper formulates a general approach for nonparametric, incremental, closed-form Bayesian estimation of conditional measures that relies on a model structure defined on a sequence of covers. This is an important development, particularly for the problem of conditional density estimation, where although non-parameteric kernel-based approaches that currently dominate generally perform well, a fast, tractable, incremental, Bayesian approach has been lacking. This construction used in this paper employs a random walk in a set of contexts.

We introduce a temporal model for reasoning on disjunctive metric constraints on intervals and time points in temporal contexts. This temporal model is composed of a labeled temporal algebra and its reasoning algorithms. The labeled temporal algebra defines labeled disjunctive metric point-based constraints, where each disjunct in each input disjunctive constraint is univocally associated to a label. Reasoning algorithms manage labeled constraints, associated label lists, and sets of mutually inconsistent disjuncts. These algorithms guarantee consistency and obtain a minimal network. Additionally, constraints can be organized in a hierarchy of alternative temporal contexts. Therefore, we can reason on context-dependent disjunctive metric constraints on intervals and points. Moreover, the model is able to represent non-binary constraints, such that logical dependencies on disjuncts in constraints can be handled. The computational cost of reasoning algorithms is exponential in accordance with the underlying problem complexity, although some improvements are proposed.

In many combinatorial problems one may need to model the diversity or similarity of assignments in a solution. For example, one may wish to maximise or minimise the number of distinct values in a solution. To formulate problems of this type, we can use soft variants of the well known AllDifferent and AllEqual constraints. We present a taxonomy of six soft global constraints, generated by combining the two latter ones and the two standard cost functions, which are either maximised or minimised. We characterise the complexity of achieving arc and bounds consistency on these constraints, resolving those cases for which NP-hardness was neither proven nor disproven. In particular, we explore in depth the constraint ensuring that at least k pairs of variables have a common value. We show that achieving arc consistency is NP-hard, however achieving bounds consistency can be done in polynomial time through dynamic programming. Moreover, we show that the maximum number of pairs of equal variables can be approximated by a factor 1/2 with a linear time greedy algorithm. Finally, we provide a fixed parameter tractable algorithm with respect to the number of values appearing in more than two distinct domains. Interestingly, this taxonomy shows that enforcing equality is harder than enforcing difference.

We prove that it is NP-hard for a coalition of two manipulators to compute how to manipulate the Borda voting rule. This resolves one of the last open problems in the computational complexity of manipulating common voting rules. Because of this NP-hardness, we treat computing a manipulation as an approximation problem where we try to minimize the number of manipulators. Based on ideas from bin packing and multiprocessor scheduling, we propose two new approximation methods to compute manipulations of the Borda rule. Experiments show that these methods significantly outperform the previous best known %existing approximation method. We are able to find optimal manipulations in almost all the randomly generated elections tested. Our results suggest that, whilst computing a manipulation of the Borda rule by a coalition is NP-hard, computational complexity may provide only a weak barrier against manipulation in practice.

We describe a general approach to optimization which we term `Squeaky Wheel' Optimization (SWO). In SWO, a greedy algorithm is used to construct a solution which is then analyzed to find the trouble spots, i.e., those elements, that, if improved, are likely to improve the objective function score. The results of the analysis are used to generate new priorities that determine the order in which the greedy algorithm constructs the next solution. This Construct/Analyze/Prioritize cycle continues until some limit is reached, or an acceptable solution is found. SWO can be viewed as operating on two search spaces: solutions and prioritizations. Successive solutions are only indirectly related, via the re-prioritization that results from analyzing the prior solution. Similarly, successive prioritizations are generated by constructing and analyzing solutions. This `coupled search' has some interesting properties, which we discuss. We report encouraging experimental results on two domains, scheduling problems that arise in fiber-optic cable manufacturing, and graph coloring problems. The fact that these domains are very different supports our claim that SWO is a general technique for optimization.

Stacked generalization is a general method of using a high-level model to combine lower-level models to achieve greater predictive accuracy. In this paper we address two crucial issues which have been considered to be a `black art' in classification tasks ever since the introduction of stacked generalization in 1992 by Wolpert: the type of generalizer that is suitable to derive the higher-level model, and the kind of attributes that should be used as its input. We find that best results are obtained when the higher-level model combines the confidence (and not just the predictions) of the lower-level ones. We demonstrate the effectiveness of stacked generalization for combining three different types of learning algorithms for classification tasks. We also compare the performance of stacked generalization with majority vote and published results of arcing and bagging.

Without these assumptions the sequences of operations that achieve the goals depend on the initial state and the outcomes of nondeterministic changes in the system. This setting raises the questions of how to represent the plans and how to perform plan search. The answers are quite dierent from those in the simpler classical framework. In this paper, we approach conditional planning from a new viewpoint that is motivated by the use of satisability algorithms in classical planning. Translating conditional planning to formulae in the propositional logic is not feasible because of inherent computational limitations. Instead, we translate conditional planning to quantied Boolean formulae. We discuss three formalizations of conditional planning as quantied Boolean formulae, and present experimental results obtained with a theorem-prover. Plans consist of operators that make a set of facts true whenever their preconditions are fullled. The most basic { and the most common in earlier research { form of plans is sequence of operators that are executed unconditionally in the specied order. Plans of this form are sucient only if the world where a plan is carried out is completely predictable and known, and the execution of the plan always starts in the same state. When not all changes in the world can be predicted or not all facts aecting plan execution are known in advance, the structure of plans has to be more general. If the task is to move object A, that is in room 1 or in room 2, to a trash can, the operations that achieve the goal depend on the initial location of A. There is no single sequence of operations that achieves the goal in both cases.

Journal of Arti ial In telligen e Resear h 10 (1999) 243-270 Submitted 10/98; published 5/99 Learning to Order Things William W. Cohen w ohen resear h.a tt. Here w e onsider the problem of learning ho w to order instan es giv en feedba k in the form of preferen e judgmen ts, i.e., statemen ts to the ee t that one instan e should b e rank ed ahead of another. W e outline a t w o-stage approa h in whi h one rst learns b y on v en tional means a binary pr efer en e fun tion indi ating whether it is advisable to rank one instan e b efore another. Here w e onsider an online algorithm for learning preferen e fun tions that is based on F reund and S hapire's \Hedge " algorithm. In the se ond stage, new instan es are ordered so as to maximize agreemen t with the learned preferen e fun - tion. W e sho w that the problem of nding the ordering that agrees b est with a learned preferen e fun tion is NP-omplete. Nev ertheless, w e des rib e simple greedy algorithms that are guaran teed to nd a go o d appro ximation. Finally, w e sho w ho w metasear h an b e form ulated as an ordering problem, and presen t exp erimen tal results on learning a om-bination of \sear h exp erts," ea h of whi h is a domain-sp e i query expansion strategy for a w eb sear h engine. Ho w ev er, there are man y appli ations in whi h it is desirable to order rather than lassify instan es. Su h orderings ould b e onstru ted based on a learned probabilisti lassier or regression mo del and in fa t often are. F or instan e, it is ommon pra ti e in information retriev al to rank do umen ts a ording to their probabilit y of relev an e to a query, as estimated b y a learned lassier for the on ept \relev an t do umen t." An adv an tage of learning orderings dire tly is that preferen e judgmen ts an b e m u h easier to obtain than the lab els required for lassi ation learning. F or instan e, in the email appli ation men tioned ab o v e, one approa h migh t b e to rank messages a ording to their estimated probabilit y of mem b ership in the lass of \urgen t" messages, or b y some n umeri al estimate of urgen y obtained b y regression. Supp ose, ho w ev er, that a user is presen ted with an ordered list of email messages, and ele ts to read the third message rst. Giv en this ele tion, it is not ne essarily the ase that message three is urgen t, nor is there suÆ ien t information to estimate an y n umeri al urgen y measures.

This paper offers an approach to extensible knowledge representation and reasoning for a family of formalisms known as Description Logics. The approach is based on the notion of adding new concept constructors, and includes a heuristic methodology for specifying the desired extensions, as well as a modularized software architecture that supports implementing extensions. The architecture detailed here falls in the normalize-compared paradigm, and supports both intentional reasoning (subsumption) involving concepts, and extensional reasoning involving individuals after incremental updates to the knowledge base. The resulting approach can be used to extend the reasoner with specialized notions that are motivated by specific problems or application areas, such as reasoning about dates, plans, etc. In addition, it provides an opportunity to implement constructors that are not currently yet sufficiently well understood theoretically, but are needed in practice. Also, for constructors that are provably hard to reason with (e.g., ones whose presence would lead to undecidability), it allows the implementation of incomplete reasoners where the incompleteness is tailored to be acceptable for the application at hand.

We describe a variational approximation method for efficient inference in large-scale probabilistic models. Variational methods are deterministic procedures that provide approximations to marginal and conditional probabilities of interest. They provide alternatives to approximate inference methods based on stochastic sampling or search. We describe a variational approach to the problem of diagnostic inference in the `Quick Medical Reference' (QMR) network. The QMR network is a large-scale probabilistic graphical model built on statistical and expert knowledge. Exact probabilistic inference is infeasible in this model for all but a small set of cases. We evaluate our variational inference algorithm on a large set of diagnostic test cases, comparing the algorithm to a state-of-the-art stochastic sampling method.