%% Last updated on October 28, 2013.
@article { maua2013ai,
abstract = {Influence diagrams are intuitive and concise representations of structured decision problems. When the problem is non-Markovian, an optimal strategy can be exponentially large in the size of the diagram. We can avoid the inherent intractability by constraining the size of admissible strategies, giving rise to limited memory influence diagrams. A valuable question is then how small do strategies need to be to enable efficient optimal planning. Arguably, the smallest strategies one can conceive simply prescribe an action for each time step, without considering past decisions or observations. Previous work has shown that finding such optimal strategies even for polytree-shaped diagrams with ternary variables and a single value node is NP-hard, but the case of binary variables was left open. In this paper we address such a case, by first noting that optimal strategies can be obtained in polynomial time for polytree-shaped diagrams with binary variables and a single value node. We then show that the same problem is NP-hard if the diagram has multiple value nodes. These two results close the fixed-parameter complexity analysis of optimal strategy selection in influence diagrams parametrized by the shape of the diagram, the number of value nodes and the maximum variable cardinality.},
title = {On the complexity of solving polytree-shaped limited memory influence diagrams with binary variables},
journal = {Artificial Intelligence},
author = {Mau\'a, Denis Deratani and de Campos, Cassio Polpo and Zaffalon, Marco},
year = {2013},
volume = {205},
number = "0",
pages {30--38},
issn = {0004-3702},
doi = {10.1016/j.artint.2013.10.002},
url = {http://ipg.idsia.ch/preprints/maua2013b.pdf}
}
@phdthesis { maua2013,
abstract = {Many solutions to problems in machine learning and artificial intelligence involve solving a combinatorial optimization problem over discrete variables whose functional dependence is conveniently represented by a graph. This thesis addresses three types of these combinatorial optimization problems, namely, the maximum a posteriori inference in discrete probabilistic graphical models, the selection of optimal strategies for limited memory influence diagrams, and the computation of upper and lower probability bounds in credal networks. These three problems arise out of seemingly very different situations, and one might believe that they share no more than the graph-based specification of their inputs or the underlying probabilistic treatment of uncertainty. However, correspondences among instances of these problems have long been noticed in the literature. For instance, the computation of probability bounds in credal networks can be reduced either to the problem of maximum a posteriori inference in graphical models, or to the selection of optimal strategies in limited memory influence diagrams. Conversely, both the maximum a posteriori inference and the strategy selection problems can be reduced to the computation of a probability bound in a credal network. These reductions suggest that much insight can be gained by carrying out a joint study of the practical and theoretical computational complexity of these three problems. This thesis describes algorithms and complexity results for these three classes of problems. In particular, we develop a new anytime algorithm for the maximum a posteriori problem. Not only the algorithm is of practical relevance, as we show that it compares favorably against a state-of-the-art method, but it is the base of the proof of polynomial-time approximability of the two other problems. We characterize the tractability of the strategy selection problem according to the input parameters, and we show that the strategy selection problem can be solved in polynomial time in singly connected diagrams over binary variables and univariate utility functions, and that relaxing any of these assumptions makes the problem NP-hard to solve or even approximate within any bound. We also investigate the theoretical complexity of computing upper and lower probability bounds in credal networks. We show that the complexity of the problem depends on the irrelevance concept adopted, but is in general NP-hard even in polytree-shaped networks, and even in trees if we assume strong independence. We also show that there is a particular type of inference that can be solved in polynomial time in imprecise hidden Markov models, whether we assume epistemic irrelevance or strong independence.}
title = {Algorithms and Complexity Results for Discrete Probabilistic Reasoning Tasks},
author = {Mau\'a, Denis Deratani},
year = {2013},
institution = {Universit\`a della Svizzera italiana},
url = {http://doc.rero.ch/record/203103?ln=en}
}
@inproceedings { antonucci2013ijcai,
abstract = {We present a novel approach for multilabel classification based on an ensemble of Bayesian networks. The class variables are connected by a tree; each model of the ensemble uses a different class as root of the tree. We assume the features to be conditionally independent given the classes, thus generalizing the naive Bayes assumption to the multiclass case. This assumption allows us to optimally identify the correlations between classes and features; such correlations are moreover shared across all models of the ensemble. Inferences are drawn from the ensemble via logarithmic opinion pooling. To minimize Hamming loss, we compute the marginal probability of the classes by running standard inference on each Bayesian network in the ensemble, and then pooling the inferences. To instead minimize the subset 0/1 loss, we pool the joint distributions of each model and cast the problem as a MAP inference in the corresponding graphical model. Experiments show that the approach is competitive with state-of-the-art methods for multilabel classification.},
title = {An Ensemble of {B}ayesian Networks for Multilabel Classification},
booktitle = {Proceedings of the 23rd International Joint Conference on Artificial Intelligence ({IJCAI})},
author = {Alessandro Antonucci and Giorgio Corani and Denis Deratani Mau\'a and Sandra Gabaglio},
url = {http://ijcai.org/papers13/Papers/IJCAI13-184.pdf},
pages = {1220--1225},
year = {2013}
}
@inproceedings{ maua2013uai,
abstract = {Credal networks are graph-based statistical models whose parameters take values in a set, instead of being sharply specified as in traditional statistical models (e.g.,~Bayesian networks). The computational complexity of inferences on such models depends on the irrelevance/independence concept adopted. In this paper, we study inferential complexity under the concepts of epistemic irrelevance and strong independence. We show that inferences under strong independence are NP-hard even in trees with ternary variables. We prove that under epistemic irrelevance the polynomial time complexity of inferences in credal trees is not likely to extend to more general models (e.g.~singly connected networks). These results clearly distinguish networks that admit efficient inferences and those where inferences are most likely hard, and settle several open questions regarding computational complexity.},
author = {Denis Deratani Mau\'a and Cassio Polpo de Campos and Alessio Benavoli and Alessandro Antonucci},
title = {On the Complexity of Strong and Epistemic Credal Networks},
booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence ({UAI})},
keywords = {creal networks, probabilistic graphical models, complexity theory, bayesian networks, imprecise probabilities},
year = {2013},
%url = {http://ipg.idsia.ch/preprints/maua2013a.pdf},
url = {http://arxiv.org/pdf/1309.6845},
pages = {391--400}
}
@inproceedings{ maua2012uai,
Abstract = {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.},
Author = {Denis Deratani Mau\'a and Cassio Polpo de Campos and Marco Zaffalon},
Booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence (UAI)},
Keywords = {decision networks,influence diagrams,combinatorial optimization,bayesian networks},
Pages = {604--613},
Title = {The Complexity of Approximately Solving Influence Diagrams},
Url = {http://www.auai.org/uai2012/papers/166.pdf},
Year = {2012}
}
@inproceedings{ maua2012icml,
Abstract = {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.},
Author = {Denis Deratani Mau\'a and Cassio Polpo de Campos},
Booktitle = {Proceedings of the 28th International Conference on Machine Learning (ICML)},
Keywords = {probability theory,map inference, discrete inference,combinatorial optimization,bayesian networks},
Title = {Anytime Marginal MAP Inference},
pages = {1471--1478}
Url = {http://icml.cc/2012/papers/728.pdf},
Year = {2012}
}
@article{ zaffalon2012ijar,
author = "Marco Zaffalon and Giorgio Corani and Denis Deratani Mau\'a",
abstract = "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.",
title = "Evaluating credal classifiers by utility-discounted predictive accuracy",
journal = "International Journal of Approximate Reasoning",
volume = "53",
number = "8",
pages = "1282--1301",
year = "2012",
issn = "0888-613X",
doi = "10.1016/j.ijar.2012.06.022",
url = "http://www.sciencedirect.com/science/article/pii/S0888613X12000989?v=s5"
}
@article{ maua2012ijar,
author = "Denis Deratani Mau\'a and Cassio Polpo de Campos and Marco Zaffalon",
abstract = "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.",
title = "Updating Credal Networks is Approximable in Polynomial Time",
journal = "International Journal of Approximate Reasoning",
volume = "53",
number = "8",
pages = "1183--1199",
year = "2012",
issn = "0888-613X",
doi = "10.1016/j.ijar.2012.06.014",
url = "http://www.sciencedirect.com/science/article/pii/S0888613X12000904?v=s5"
}
@article{ maua2012jair,
Abstract = {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.},
Author = {Denis Deratani Mau\'a and Cassio Polpo de Campos and Marcos Zaffalon},
Journal = {Journal of Artificial Intelligence Research},
Keywords = {decision making, influence diagrams},
Pages = {97--140},
Title = {Solving Limited Memory Influence Diagrams},
Url = {http://www.jair.org/media/3625/live-3625-6282-jair.pdf},
Volume = {44},
Year = {2012}
}
@incollection{ maua2011nips,
Abstract = {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.},
Author = {Denis Deratani Mau\'a and Cassio Polpo de Campos},
Booktitle = {Advances in Neural Information Processing Systems 24},
Editor = {J. Shawe-Taylor and R.S. Zemel and P. Bartlett and F.C.N. Pereira and K.Q. Weinberger},
Keywords = {influence diagrams},
Pages = {603--611},
Title = {Solving Decision Problems with Limited Information},
Url = {http://books.nips.cc/papers/files/nips24/NIPS2011_0422.pdf},
Year = {2011}
}
@inproceedings{ maua2011isipta,
Abstract = {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.},
Address = {Innsbruck, Austria},
Author = {Denis Deratani Mau\'a and Cassio Polpo de Campos and Marco Zaffalon},
Booktitle = {ISIPTA '11: Proceedings of the Seventh International Symposium on Imprecise Probability: Theories and Applications},
Editor = {Coolen, F. and de Cooman, Gert and Fetz, T. and Oberguggenberger, M.},
Keywords = {approximation scheme,credal networks,probabilistic graphical models,valuation algebra},
Pages = {277--286},
Publisher = {SIPTA},
Title = {A Fully Polynomial Time Approximation Scheme for Updating Credal Networks of Bounded Treewidth and Number of Variable States},
Url = {http://leo.ugr.es/sipta/isipta11/proceedings/papers/s035.pdf},
Year = {2011}
}
@inproceedings{ zaffalon2011isipta,
Abstract = {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.},
Address = {Innsbruck, Austria},
Author = {Marco Zaffalon and Giorgio Corani and Denis Deratani Mau\'a},
Booktitle = {ISIPTA '11: Proceedings of the Seventh International Symposium on Imprecise Probability: Theories and Applications},
Editor = {Coolen, F. and de Cooman, Gert and Fetz, T. and Oberguggenberger, M.},
Keywords = {credal classification,credal classifiers,discounted accuracy,empirical,evaluation,indeterminacy,risk-aversion,utility},
Pages = {401--410},
Publisher = {SIPTA},
Title = {Utility-Based Accuracy Measures to Empirically Evaluate Credal Classifiers},
Url = {http://leo.ugr.es/sipta/isipta11/proceedings/papers/s016.pdf},
Year = {2011}
}
@techreport{ maua2011arxiv,
Abstract = {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.},
Archiveprefix = {arXiv},
Author = {Denis Deratani Mau\'a and Cassio Polpo de Campos and Marco Zaffalon},
Eprint = {1109.1754},
Institution = {IDSIA},
Journal = {ArXiv e-prints},
Keywords = {influence diagrams},
Month = sep,
Title = {Solving Limited Memory Influence Diagrams},
Url = {http://arxiv.org/pdf/1109.1754v2},
Year = {2011}
}
@phdthesis{ maua2009masterthesis,
Abstract = {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.},
Author = {Denis Deratani Mau\'a},
Keywords = {artificial intelligence,computational learning,machine learning,master dissertation,sentiment classification,text categorization,text processing},
School = {Universidade de S\~{a}o Paulo},
Title = {Topic models on the automatic classification of user reviews},
Type = {masterthesis},
Url = {http://www.idsia.ch/~deratani/Publications/mestrado.pdf},
Year = {2009}
}
@inproceedings{ maua2008wiva,
Abstract = {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.},
Address = {Campinas},
Author = {Denis Deratani Mau\'a and Fabio Gagliardi Cozman},
Booktitle = {Workshop on Information Visualization and Analysis in Social Networks (WIVA)},
Keywords = {classification,markov networks,social networks,trust management,trust managment},
Pages = {10},
Title = {Using Social Data to Predict Trust on Web Communities : A Case Study with the Epinions.com Website},
Url = {http://www.poli.usp.br/p/fabio.cozman/Publications/Article/maua-cozman-wiva2008.pdf},
Year = {2008}
}
@inproceedings{ maua2009enia,
Abstract = {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 supervisedmethod that converts raw text into an appropriate represen- tation, 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.},
Address = {Bento Gon\c{c}alves, Brazil},
Author = {Denis Deratani Mau\'a and Fabio Gagliardi Cozman},
Booktitle = {Encontro Nacional de Intelig\^{e}ncia Artificial},
Keywords = {markov logic,text categorization},
Title = {Representing and Classifying User Reviews},
Url = {http://www.ime.usp.br/~logprob/articles/maua-ENIA2009.pdf},
Year = {2009}
}
@inproceedings{ maua2008wtdia,
Abstract = {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.},
Address = {Salvador, Brazil},
Author = {Denis Deratani Mau\'a and Fabio Gagliardi Cozman},
Booktitle = {IV Workshop on MSc Dissertation and PhD Thesis in Artificial Intelligence (WTDIA)},
Keywords = {knowledge discovery,markov logic,trust management},
Title = {Managing Trust in Virtual Communities with {M}arkov Logic},
Url = {http://www.poli.usp.br/p/fabio.cozman/Publications/Article/maua-cozman-wtdia2008.pdf},
Year = {2008}
}