Catálogo de publicaciones - libros

We consider probabilistic predictions using graphical models and describe a newly developed method, fully conditional Venn predictor (FCVP). FCVP can provide upper and lower bounds for the conditional probability associated with each predicted label. Empirical results confirm that FCVP can give well-calibrated predictions in online learning mode. Experimental results also show the prediction performance of FCVP is good in both the online and the offline learning setting without making any additional assumptions, apart from i.i.d.

Recommendation Systems are tools designed to help users to find items within a given domain, according to their own preferences expressed by means of a user profile. A general model for recommendation systems based on probabilistic graphical models is proposed in this paper. It is designed to deal with hierarchical domains, where the items can be grouped in a hierarchy, each item being only contained in another, more general item. The model makes decisions about which items in the hierarchy are more useful for the user, and carries out the necessary computations in a very efficient way.

We propose an algorithm for learning the Markov boundary of a random variable from data without having to learn a complete Bayesian network. The algorithm is correct under the faithfulness assumption, scalable and data efficient. The last two properties are important because we aim to apply the algorithm to identify the minimal set of random variables that is relevant for probabilistic classification in databases with many random variables but few instances. We report experiments with synthetic and real databases with 37, 441 and 139352 random variables showing that the algorithm performs satisfactorily.

The learning of probabilistic classification models can be approached from either a generative or a discriminative point of view. Generative methods attempt to maximize the unconditional log-likelihood, while the aim of discriminative methods is to maximize the conditional log-likelihood. In the case of Bayesian network classifiers, the parameters of the model are usually learned by generative methods rather than discriminative ones. However, some numerical approaches to the discriminative learning of Bayesian network classifiers have recently appeared. This paper presents a new statistical approach to the discriminative learning of these classifiers by means of an adaptation of the TM algorithm [1]. In addition, we test the TM algorithm with different Bayesian classification models, providing empirical evidence of the performance of this method.

The dominant approach for learning Bayesian networks from data is based on the use of a scoring metric, that evaluates the fitness of any given candidate network to the data, and a search procedure, that explores the space of possible solutions. The most used method inside this family is (iterated) hill climbing, because its good trade-off between CPU requirements, accuracy of the obtained model, and ease of implemetation. In this paper we focus on the searh space of dags and in the use of hill climbing as search engine. Our proposal consists in the reduction of the candidate dags or neighbors to be explored at each iteration, making the method more efficient on CPU time, but without decreasing the quality of the model discovered. Thus, initially the parent set for each variable is not restricted and so all the neighbors are explored, but during this exploration we take advantage of locally consistent metrics properties and remove some nodes from the set of candidate parents, constraining in this way the process for subsequent iterations. We show the benefits of our proposal by carrying out several experiments in three different domains.

In this paper we explore the use of several types of structural restrictions within algorithms for learning Bayesian networks. These restrictions may codify expert knowledge in a given domain, in such a way that a Bayesian network representing this domain should satisfy them. Our objective is to study whether the algorithms for automatically learning Bayesian networks from data can benefit from this prior knowledge to get better results. We formally define three types of restrictions: existence of arcs and/or edges, absence of arcs and/or edges, and ordering restrictions, and also study their interactions and how they can be managed within Bayesian network learning algorithms based on the score+search paradigm. Then we particularize our study to the classical local search algorithm with the operators of arc addition, arc removal and arc reversal, and carry out experiments using this algorithm on several data sets.

A type of problem domains known as models poses difficulty for common learning methods, which are based on the single-link lookahead search. To learn this type of domain models, a method called the multiple-link lookahead search is needed. An improved result can be obtained by incorporating model complexity into a scoring metric to explicitly trade off model accuracy for complexity and vice versa during selection of the best model among candidates at each learning step. Previous studies found the complexity formulae for full PI models (the simplest type of PI models) and for atomic PI models (PI models without submodels). This study presents the complexity formula for non-atomic PI models, which are more complex than full or atomic PI models, yet more general. Together with the previous results, this study completes the major theoretical work for the new learning algorithm that combines complexity and accuracy.

We consider the general problem of optimal stochastic control of a dedicated-platform that processes one primary function or task (target-task). The dedicated-platform has two modes of action at each period of time: it can attempt to process the target-task at the given period of time, or suspend the target-task for later completion. We formulate the optimal trade-off between the processing cost and the latency in completion of the target-task as a Partially Observable Markov Decision Process (POMDP). By reformulating this POMDP as a Markovian search problem, we prove that the optimal control policies are threshold in nature. Threshold policies are computationally efficient and inexpensive to implement in real time systems. Numerical results demonstrate the effectiveness of these threshold based operating algorithms as compared to non-optimal heuristic algorithms.

We describe , an approximate probabilistic contingent planner based on , a probabilistic contingent planner that operates by converting the planning problem to a stochastic satisfiability () problem and solving that problem instead [1]. The values of some of the variables in an instance are probabilistically determined; considers the most likely instantiations of these variables (the most probable situations facing the agent) and attempts to construct an approximation of the optimal plan that succeeds under those circumstances, improving that plan as time permits. Given more time, less likely instantiations/situations are considered and the plan is revised as necessary. In some cases, a plan constructed to address a relatively low percentage of possible situations will succeed for situations not explicitly considered as well, and may return an optimal or near-optimal plan. This means that can sometimes find optimal plans faster than . And the anytime quality of means that suboptimal plans could be efficiently derived in larger time-critical domains in which might not have sufficient time to calculate the optimal plan. We describe some preliminary experimental results and suggest further work needed to bring closer to attacking real-world problems.

In this article, we consider the computational aspects of deciding whether a conditional independence statement is implied by a list of conditional independence statements using the implication related to the method of structural imsets. We present two methods which have the interesting complementary properties that one method performs well to prove that is implied by , while the other performs well to prove that is not implied by . However, both methods do not perform well the opposite. This gives rise to a parallel algorithm in which both methods race against each other in order to determine effectively whether is or is not implied.

Some empirical evidence is provided that suggest this racing algorithms method performs a lot better than an existing method based on so-called skeletal characterization of the respective implication. Furthermore, the method is able to handle more than five variables.