[AUTH1=Scholkopf_B ( 69%, 31%)]
[AUTH2=Darwiche_A ( 72%, 28%)]

A method is described which like the kernel trick in support vector machines SVMs lets us generalize distance based algorithms to operate in feature spaces usually nonlinearly related to the input space This is done by identifying a class of kernels which can be represented as norm based distances in Hilbert spaces It turns out that common kernel algorithms such as SVMs and kernel PCA are actually really distance based algorithms and can be run with that class of kernels too As well as providing a useful new insight into how these algorithms work the present work can form the basis for conceiving new algorithms

This paper presents a comprehensive approach for model based diagnosis which includes proposals for characterizing and computing preferred diagnoses assuming that the system description is augmented with a system structure a directed graph explicating the interconnections between system components Specifically we first introduce the notion of a consequence which is a syntactically unconstrained propositional sentence that characterizes all consistency based diagnoses and show that standard characterizations of diagnoses such as minimal conflicts correspond to syntactic variations on a consequence Second we propose a new syntactic variation on the consequence known as negation normal form NNF and discuss its merits compared to standard variations Third we introduce a basic algorithm for computing consequences in NNF given a structured system description We show that if the system structure does not contain cycles then there is always a linear size consequence in NNF which can be computed in linear time For arbitrary system structures we show a precise connection between the complexity of computing consequences and the topology of the underlying system structure Finally we present an algorithm that enumerates the preferred diagnoses characterized by a consequence The algorithm is shown to take linear time in the size of the consequence if the preference criterion satisfies some general conditions

[AUTH1=Dietterich_T ( 66%, 34%)]
[AUTH2=Thrun_S ( 52%, 48%)]

Many researchers have explored methods for hierarchical reinforcement learning RL with temporal abstractions in which abstract actions are defined that can perform many primitive actions before terminating However little is known about learning with state abstractions in which aspects of the state space are ignored In previous work we developed the MAXQ method for hierarchical RL In this paper we define five conditions under which state abstraction can be combined with the MAXQ value function decomposition We prove that the MAXQ Q learning algorithm converges under these conditions and show experimentally that state abstraction is important for the successful application of MAXQ Q learning

We present a Monte Carlo algorithm for learning to act optimally in partially observable Markov decision processes POMDPs Our approach uses importance sampling for representing beliefs and Monte Carlo approximation for belief revision Reinforcement learning value iteration is employed to learn value functions over belief functions and a sample based version of nearest neighbor is used to generalize across states Our approach departs from previous work in the POMDP field in that it can handle real valued state spaces Initial empirical results suggest that our approach may work well in practical applications

[AUTH1=Hauskrecht_M ( 70%, 30%)]
[AUTH2=Resnik_P ( 82%, 18%)]

Partially observable Markov decision processes POMDPs provide an elegant mathematical framework for modeling complex decision and planning problems in stochastic domains in which states of the system are observable only indirectly via a set of imperfect or noisy observations The modeling advantage of POMDPs however comes at a price exact methods for solving them are computationally very expensive and thus applicable in practice only to very simple problems We focus on efficient approximation heuristic methods that attempt to alleviate the computational problem and trade off accuracy for speed We have two objectives here First we survey various approximation methods analyze their properties and relations and provide some new insights into their differences Second we present a number of new approximation methods and novel refinements of existing techniques The theoretical results are supported by experiments on a problem from the agent navigation domain

This article presents a measure of semantic similarity in an IS A taxonomy based on the notion of shared information content Experimental evaluation against a benchmark set of human similarity judgments demonstrates that the measure performs better than the traditional edge counting approach The article presents algorithms that take advantage of taxonomic similarity in resolving syntactic and semantic ambiguity along with experimental results demonstrating their effectiveness

[AUTH1=Halpern_J ( 74%, 26%)]
[AUTH2=Adelson_E ( 72%, 28%)]

Causal models defined in terms of a collection of equations as defined by Pearl are axiomatized here Axiomatizations are provided for three successively more general classes of causal models 1 the class of recursive theories those without feedback 2 the class of theories where the solutions to the equations are unique 3 arbitrary theories where the equations may not have solutions and if they do they are not necessarily unique It is shown that to reason about causality in the most general third class we must extend the language used by Galles and Pearl In addition the complexity of the decision procedures is characterized for all the languages and classes of models considered

The classical approaches to lightness perception involve normalization by a image statistics e g dividing or subtracting out the mean luminance Low level operations such as lateral inhibition can implement such normalization locally However we have devised stimuli that dramatically demonstrate the inadequacy of these traditional models The new illusions indicate the importance of mid level visual processes that utilize information about contours junctions and regions We propose that the visual system estimates optical atmosphere at each point in a scene and propagates lightness constraints within regions defined by atmospheric boundaries Lightness constancy can be considered as a statistical estimation problem where the statistics are gathered within an adaptive window that prevents the mixture of samples from different lighting conditions

[AUTH1=Tennenholtz_M ( 66%, 34%)]
[AUTH2=Carey_M ( 71%, 29%)]

Much work in AI deals with the selection of proper actions in a given known or unknown environment However the way to select a proper action when facing other agents is quite unclear Most work in AI adopts classical game theoretic equilibrium analysis to predict agent behavior in such settings This approach however does not provide us with any guarantee for the agent In this paper we introduce competitive safety analysis This approach bridges the gap between the desired normative AI approach where a strategy should be selected in order to guarantee a desired payoff and equilibrium analysis We show that a safety level strategy is able to guarantee the value obtained in a Nash equilibrium in several classical computer science settings Then we discuss the concept of competitive safety strategies and illustrate its use in a decentralized load balancing setting typical to network problems In particular we show that when we have many agents it is possible to guarantee an expected payoff which is a factor of 8 9 of the payoff obtained in a Nash equilibrium Our discussion of competitive safety analysis for decentralized load balancing is further developed to deal with many communication links and arbitrary speeds Finally we discuss the extension of the above concepts to Bayesian games and illustrate their use in a basic auctions setup

An abstract model of concurrency control algorithms is presented The model facilitates implementation independent descriptions of various algorithms allowing them to be specified in terms of the information that they require the conditions under which blocking or restarts are called for and the manner in which requests are processed The model also facilitates comparisons of the relative storage and CPU overheads of various algorithms based on their descriptions Results are given for single site versions of two phase locking basic timestamp ordering and serial validation Extensions which will allow comparisons of multiple version and distributed algorithms are discussed as well

[AUTH1=Ginsberg_M ( 77%, 23%)]
[AUTH2=Agrawal_R ( 60%, 40%)]

This paper investigates the problems arising in the construction of a program to play the game of contract bridge These problems include both the difficulty of solving the game s perfect information variant and techniques needed to address the fact that bridge is not in fact a perfect information game GIB the program being described involves five separate technical advances partition search the practical application of Monte Carlo techniques to realistic problems a focus on achievable sets to solve problems inherent in the Monte Carlo approach an extension of alpha beta pruning from total orders to arbitrary distributive lattices and the use of squeaky wheel optimization to find approximately optimal solutions to cardplay problems GIB is currently believed to be of approximately expert caliber and is currently the strongest computer bridge program in the world

The explosive progress in networking storage and processor technologies is resulting in an unprecedented amount of digitization of information In concert with this dramatic increase in digital data concerns about the privacy of personal information have emerged globally The concerns over massive collection of data are naturally extending to analytic tools applied to data Data mining with its promise to efficiently discover valuable non obvious information from large databases is particularly vulnerable to misuse The challenge for the database community is to design information systems that protect the privacy and ownership of individual data without impeding information flow One way of preserving privacy of individual data values is to perturb them Since the primary task in data mining is the development of models about aggregated data we explore if we can develop accurate models without access to precise information in individual data records We consider the concrete case of building a decision tree classifier from perturbed data While it is not possible to accurately estimate original values in individual data records we describe a reconstruction procedure to accurately estimate the distribution of original data values By using these reconstructed distributions we are able to build classifiers whose accuracy is comparable to the accuracy of classifiers built with the original data We also discuss how to discover association rules over privacy preserved data Inspired by the privacy tenet of the Hippocratic Oath we argue that future database systems must include responsibility for the privacy of data they manage as a founding tenet We enunciate the key principles for such Hippocratic database systems distilled from the principles behind current privacy legislations and guidelines We identify the technical challenges and problems in designing Hippocratic databases and also outline some solution approaches

[AUTH1=Kambhampati_S ( 66%, 34%)]
[AUTH2=Lomet_D ( 65%, 35%)]

This paper reviews the connections between Graphplan s planning graph and the dynamic constraint satisfaction problem and motivates the need for adapting CSP search techniques to the Graphplan algorithm It then describes how explanation based learning dependency directed backtracking dynamic variable ordering forward checking sticky values and random restart search strategies can be adapted to Graphplan Empirical results are provided to demonstrate that these augmentations improve Graphplan s performance significantly up to 1000x speedups on several benchmark problems Special attention is paid to the explanation based learning and dependency directed backtracking techniques as they are empirically found to be most useful in improving the performance of Graphplan

A new algorithm is presented for avoiding system deadlocks Because its performance has little dependence on the number of lockable resources it is particularly well suited to use in data base systems which may have millions of individually lockable records A further advantage is that both exclusive and shared locking are accommodated The algorithm is presented in some detail and its performance and functional characteristics discussed