publications
Last updated on January, 2013
outline
journal articles
by year: 2012
- maua2012ijar
-
Updating Credal Networks is Approximable in Polynomial Time
D. D. Maua, C. P. de Campos and M. Zaffalon
International Journal of Approximate Reasoning, 53 (8). pp. 1183-1199 (2012)
Credal networks relax the precise probability requirement of Bayesian networks, enabling a richer representation of uncertainty in the form of closed convex sets of probability measures. The increase in expressiveness comes at the expense of higher computational costs. In this paper, we present a new variable elimination algorithm for exactly computing posterior inferences in extensively specified credal networks, which is empirically shown to outperform a state-of-the-art algorithm. The algorithm is then turned into a provably good approximation scheme, that is, a procedure that for any input is guaranteed to return a solution not worse than the optimum by a given factor. Remarkably, we show that when the networks have bounded treewidth and bounded number of states per variable the approximation algorithm runs in time polynomial in the input size and in the inverse of the error factor, thus being the first known fully polynomial-time approximation scheme for inference in credal networks.
- zaffalon2012ijar
-
Evaluating Credal Classifiers By Utility-Discounted Predictive Accuracy
M. Zaffalon, G. Corani and D. D. Maua
International Journal of Approximate Reasoning, 53 (8). pp. 1282-1301 (2012)
Predictions made by imprecise-probability models are often indeterminate (that is, set-valued). Measuring the quality of an indeterminate prediction by a single number is important to fairly compare different models, but a principled approach to this problem is currently missing. In this paper we derive, from a set of assumptions, a metric to evaluate the predictions of credal classifiers. These are supervised learning models that issue set-valued predictions. The metric turns out to be made of an objective component, and another that is related to the decision-maker’s degree of risk aversion to the variability of predictions. We discuss when the measure can be rendered independent of such a degree, and provide insights as to how the comparison of classifiers based on the new measure changes with the number of predictions to be made. Finally, we make extensive empirical tests of credal, as well as precise, classifiers by using the new metric. This shows the practical usefulness of the metric, while yielding a first insightful and extensive comparison of credal classifiers.
- maua2012jair
-
Solving Limited Memory Decision Diagrams
D. D. Maua, C. P. de Campos and M. Zaffalon
Journal of Artificial Intelligence Research, 44. pp. 97-140 (2012)
We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and 10^64 solutions. We show that these problems are NP-hard even if the underlying graph structure of the problem has low treewidth and the variables take on a bounded number of states, and that they admit no provably good approximation if variables can take on an arbitrary number of states.
conference articles
by year: 2012 2011 2009 2008
- maua2012icml
-
The Complexity of Approximately Solving
Influence Diagrams
D. D. Maua, C. P. de Campos and M. Zaffalon
UAI 2012: Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence. pp. 604-613 (2012)
Influence diagrams allow for intuitive and yet precise description of complex situations involving decision making under uncertainty. Unfortunately, most of the problems described by influence diagrams are hard to solve. In this paper we discuss the complexity of approximately solving influence diagrams. We do not assume no-forgetting or regularity, which makes the class of problems we address very broad. Remarkably, we show that when both the treewidth and the cardinality of the variables are bounded the problem admits a fully polynomial-time approximation scheme.
- maua2012icml
-
Anytime Marginal MAP Inference
D. D. Maua and C. P. de Campos
ICML 2012: Proceedings of the 29th International Conference on Machine Learning. (2012)
This paper presents a new anytime algorithm for the marginal MAP problem in graphical models. The algorithm is described in detail, its complexity and convergence rate are studied, and relations to previous theoretical results for the problem are discussed. It is shown that the algorithm runs in polynomial-time if the underlying graph of the model has bounded tree-width, and that it provides guarantees to the lower and upper bounds obtained within a fixed amount of computational resources. Experiments with both real and synthetic generated models highlight its main characteristics and show that it compares favorably against Park and Darwiche's systematic search, particularly in the case of problems with many MAP variables and moderate tree-width.
- maua2011nips
-
Solving Decision Problems with Limited Information
D. D. Maua and C. P. de Campos
NIPS 2011: Advances in Neural Information Processing Systems 24. pp. 603-611 (2011)
We present a new algorithm for exactly solving decision-making problems represented as an influence diagram. We do not require the usual assumptions of no forgetting and regularity, which allows us to solve problems with limited information. The algorithm, which implements a sophisticated variable elimination procedure, is empirically shown to outperform a state-of-the-art algorithm in randomly generated problems of up to 150 variables and 10^64 strategies.
- maua2011isipta
-
A Fully Polynomial Time Approximation Scheme for Updating Credal Networks of Bounded Treewidth and Number of Variable States
D. D. Maua, C. P. de Campos and M. Zaffalon
ISIPTA '11: Proceedings of the Seventh International Symposium on Imprecise Probability: Theories and Applications. pp. 277-286 (2011)
Credal networks lift the precise probability assumption of Bayesian networks, enabling a richer representation of uncertainty in the form of closed convex sets of probability measures. The increase in expressiveness comes at the expense of higher computational costs. In this paper we present a new algorithm which is an extension of the well-known variable elimination algorithm for computing posterior inferences in extensively specified credal networks. The algorithm efficiency is empirically shown to outperform a state-of-the-art algorithm. We then provide the first fully polynomial time approximation scheme for inference in credal networks with bounded treewidth and number of states per variable.
- zaffalon2011isipta
-
Utility-Based Accuracy Measures to Empirically Evaluate Credal Classifiers
M. Zaffalon, G. Corani and D. D. Maua
ISIPTA '11: Proceedings of the Seventh International Symposium on Imprecise Probability: Theories and Applications. pp. 401-410 (2011)
Predictions made by imprecise-probability models are often indeterminate (that is, set-valued). Measuring the quality of an indeterminate prediction by a single number is important to fairly compare different models, but a principled approach to this problem is currently missing. In this paper we derive a measure to evaluate the predictions of credal classifiers from a set of assumptions. The measure turns out to be made of an objective component, and another that is related to the decision-maker's degree of risk-aversion. We discuss when the measure can be rendered independent of such a degree, and provide insights as to how the comparison of classifiers based on the new measure change with the number of predictions to be made. Finally, we empirically study the behavior of the proposed measure.
- maua2009enia
-
Representing and Classifying User Reviews
D. D. Maua and F. G. Cozman
ENIA '09: Encontro Nacional de Inteligencia Artificial. (2009)
A large number of user reviews in the internet contains valuable information on services and products; for this reason, there is interest in automatically understanding such reviews. Sentiment Classification labels documents according to the feelings they express; instead of classifying a document into topics (sports, economics, etc), one attempts to tag the document according to overall feelings. Compared to the accuracy of traditional text categorization methods, sentiment classifiers have shown poor performance. We argue that such bad results are due to an improper representation of reviews. We describe a weakly supervised method that converts raw text into an appropriate representation, and show how techniques from information retrieval can acquire labeled data and process data using Markov logic. We report results on sentence classification and rating prediction that support our claims.
- maua2008wiva
-
Using Social Data to Predict Trust on Web Communities: A Case Study with the Epinions.com Website
D. D. Maua and F. G. Cozman
WIVA '08: Workshop on Information Visualization and Analysis in Social Networks. (2008)
In this paper we analyze the performance of state-of-the-art machine learning techniques in trust prediction. We use two propositionalization methods together with the Naive and Tree-Augmented Naive Bayesian Classifiers, and the C4.5 algorithm. We compare those results with classifiers defined through Markov Logic, using data fromthe Epinions.comwebsite, a well-known product review community. The experiments show that predicting trust relationships is a difficult task, in which Markov Logic models outperform other methods in accuracy but are able to recover only a relatively small fraction of the existing relationships in the dataset.
- maua2008wtdia
-
Managing Trust in Virtual Communities with Markov Logic
D. D. Maua and F. G. Cozman
WTDIA '08: IV Workshop on MSc Dissertation and PhD Thesis in Artificial Intelligence. (2008)
This paper describes advances in the development of a trust management system for web-based virtual communities. We review current research on computational trust and report on a proposal for trust management with Markov Logic, a recently developed probabilistic logic language that aims at unifying statistical relational procedures. This work addresses two complex questions: how to learn trust metrics for a group of interacting agents upon amachine learning perspective, and how to use pairwise trust metrics structured as a trust network to compute personalized trust metrics.
theses
- maua2009masterthesis
-
Topic models on the automatic classification of user reviews
D. D. Maua
Master thesis. Universidade de Sao Paulo. (2009)
[pdf] (in Portuguese)
There is a large number of user reviews on the internet with valuable information on services, products, politics and trends. There is both scientific and economic interest in the automatic understanding of such data. Sentiment classification is concerned with automatic extraction of opinions expressed in user reviews. Unlike standard text categorization tasks that deal with the classification of documents into subjects such as sports, economics and tourism, sentiment classification attempts to tag documents with respect to the feelings they express. Compared to the accuracy of standard methods, sentiment classifiers have shown poor performance. One possible cause of such a poor performance is the lack of adequate representations that lead to opinion discrimination in a concise and machine-readable form. Topic Models are statistical models concerned with the extraction of semantic information hidden in the large number of data available in text collections. They represent a document as a mixture of topics, probability distributions over words that represent a semantic concept. According to Topic Model representation, words can be substituted by topics able to represent concisely its meaning. Indeed, Topic Models perform a data dimensionality reduction that can improve the performance of text classification and information retrieval techniques. In sentiment classification, they can provide the necessary representation by extracting topics that represent the general feelings expressed in text. This work presents a study of the use of Topic Models for representing and classifying user reviews with respect to their feelings. In particular, the Latent Dirichlet Allocation (LDA) model and four extensions (two of them developed by the author) are evaluated on the task of aspect-based sentiment classification. The extensions to the LDA model enables us to investigate the effects of the incorporation of additional information such as context, aspect rating and multiple aspect rating into the original model.
technical reports
- maua2011arxiv
-
Solving Limited Memory Influence Diagrams
D. D. Maua, C. P. de Campos and M. Zaffalon
ArXiv e-prints. arXiv:1109.1754v2 [cs.AI] (2011)
We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and 10^64 solutions. We show that the problem is NP-hard even if the underlying graph structure of the problem has small treewidth and the variables take on a bounded number of states, but that a fully polynomial time approximation scheme exists for these cases. Moreover, we show that the bound on the number of states is a necessary condition for any efficient approximation scheme.