Skip to main content
main-content

Über dieses Buch

This book constitutes the proceedings of the 12th International Conference on Modeling Decisions for Artificial Intelligence, MDAI 2015, held in Skövde, Sweden, in September 2015. The 18 revised full papers presented were carefully reviewed and selected from 38 submissions. They discuss theory and tools for modeling decisions, as well as applications that encompass decision making processes and information fusion techniques.

Inhaltsverzeichnis

Frontmatter

Invited Paper

Frontmatter

Classifying Large Graphs with Differential Privacy

Abstract
We consider classification of graphs using graph kernels under differential privacy. We develop differentially private mechanisms for two well-known graph kernels, the random walk kernel and the graphlet kernel. We use the Laplace mechanism with restricted sensitivity to release private versions of the feature vector representations of these kernels. Further, we develop a new sampling algorithm for approximate computation of the graphlet kernel on large graphs with guarantees on sample complexity, and show that the method improves both privacy and computation speed. We also observe that the number of samples needed to obtain good accuracy in practice is much lower than the bound. Finally, we perform an extensive empirical evaluation examining the trade-off between privacy and accuracy and show that our private method is able to retain good accuracy in several classification tasks.
Fredrik D. Johansson, Otto Frost, Carl Retzner, Devdatt Dubhashi

Aggregation Operators and Decision Making

Frontmatter

Extremal Completions of Triangular Norms Known on a Subregion of the Unit Interval

Abstract
The strongest and the weakest t-norms that coincide with the given t-norm on a subregion of the unit interval are discussed. The question whether such a t-norm can be obtained as a limit of the sequence of continuous t-norms that coincide with the original t-norm on the given subregion is investigated.
Andrea Mesiarová-Zemánková

The Notion of Pre-aggregation Function

Abstract
In this work we consider directional monotone functions and use this idea to introduce the notion of pre-aggregation function. In particular, we propose an example of such functions inspired on Choquet integrals.
Giancarlo Lucca, José Antonio Sanz, Graçaliz Pereira Dimuro, Benjamín Bedregal, Radko Mesiar, Anna Kolesárová, Humberto Bustince

Weighted Quasi-Arithmetic Mean on Two-Dimensional Regions and Their Applications

Abstract
This paper discusses a decision maker’s attitude regarding risks, for example risk neutral, risk averse and risk loving in micro-economics by the convexity and concavity of utility functions. Weighted quasi-arithmetic means on two-dimensional regions are introduced, and some conditions on utility functions are discussed to characterize the decision maker’s attitude. Risk premiums on two-dimensional regions are given and demonstrated. Some approaches to construct two-dimensional utilities from one-dimensional ones are given, and a lot of examples of weighted quasi-arithmetic means are shown.
Yuji Yoshida

A Comparison of the GAI Model and the Choquet Integral w.r.t. a k-ary Capacity

Abstract
This paper proposes a comparison between a GAI model and the Choquet integral w.r.t. a k-ary capacity. We show that these two models are much closer than one would expect. Based on this comparison, we show a new result on the GAI models: any 2-additive GAI model can be rewritten in such a way that all utility terms in the GAI decomposition are non-negative and monotone. This is very important in practice since it allows reducing the number of monotonicity constraints to be enforced in the elicitation process, from an exponential number (of the number of attributes) to a quadratic number.
Christophe Labreuche, Michel Grabisch

Estimating Unknown Values in Reciprocal Intuitionistic Preference Relations via Asymmetric Fuzzy Preference Relations

Abstract
Intuitionistic preference relations are becoming increasingly important in the field of group decision making since they present a flexible and simple way to the experts to provide their preference relations, while at the same time allowing them to accommodate a certain degree of hesitation inherent to all decision making processes. In this contribution, we prove the mathematical equivalence between the set of asymmetric fuzzy preference relations and the set of reciprocal intuitionistic fuzzy preference relations. This result is exploited to tackle the presence of incomplete reciprocal intuitionistic fuzzy preference relation in decision making by developing a consistency driven estimation procedure via the corresponding equivalent incomplete asymmetric fuzzy preference relation.
Francisco Chiclana, Raquel Ureña, Hamido Fujita, Enrique Herrera-Viedma

Handling Risk Attitudes for Preference Learning and Intelligent Decision Support

Abstract
Intelligent decision support should allow integrating human knowledge with efficient algorithms for making interpretable and useful recommendations on real world decision problems. Attitudes and preferences articulate and come together under a decision process that should be explicitly modeled for understanding and solving the inherent conflict of decision making. Here, risk attitudes are represented by means of fuzzy-linguistic structures, and an interactive methodology is proposed for learning preferences from a group of decision makers (DMs). The methodology is built on a multi-criteria framework allowing imprecise observations/measurements, where DMs reveal their attitudes in linguistic form and receive from the system their associated type, characterized by a preference order of the alternatives, together with the amount of consensus and dissention existing among the group. Following on the system’s feedback, DMs can negotiate on a common attitude while searching for a satisfactory decision.
Camilo Franco, Jens Leth Hougaard, Kurt Nielsen

Representation of Ordinal Preferences over Infinite Products

Abstract
In many decision processes data aggregation is required. In many models the need arises to aggregate data of varying dimension while aggregation operators are considered for a fixed number of arguments. In many contexts inputs to be aggregated are of a qualitative nature. This paper analyzes the evaluation of sequences of ordinal input and of variable length. We consider various axioms against which different ranking methods can be compared.
Marta Cardin

Clustering and Similarity

Frontmatter

Spherical k-Means++ Clustering

Abstract
k-means clustering (KM) algorithm, also called hard c-means clustering (HCM) algorithm, is a very powerful clustering algorithm [1, 2], but it has a serious problem of strong initial value dependence. To decrease the dependence, Arthur and Vassilvitskii proposed an algorithm of k-means++ clustering (KM++) algorithm on 2007 [3]. By the way, there are many case that each object is allocated on an unit sphere, e.g. text clustering. Dhillon and Modha proposed the primitive spherical k-means clustering algorithm to classify such objects on 2007 [4] and Honik, Kober, and Buchta proposed new spherical k-means clustering (SKM) algorithm on 2012 [5]. However, both of the algorithms also have the same problem of initial value dependence as KM. Therefore, the paper discuss the following points: (1) the dissimilarity of SKM is extended to satisfy the triangle inequality, and (2) spherical k-means++ clustering (SKM++) algorithm which works well for the problem is proposed. The paper shows that the effectiveness of SKM++ is theoretically guaranteed.
Yasunori Endo, Sadaaki Miyamoto

On Possibilistic Clustering Methods Based on Shannon/Tsallis-Entropy for Spherical Data and Categorical Multivariate Data

Abstract
In this paper, four possibilistic clustering methods are proposed. First, we propose two possibilistic clustering methods for spherical data — one based on Shannon entropy, and the other on Tsallis entropy. These methods are derived by subtracting the cosine correlation between an object and a cluster center from 1, to obtain the object-cluster dissimilarity. These methods are derived from the proposed spherical data methods by considering analogies between the spherical and categorical multivariate fuzzy clustering methods, in which the fuzzy methods’ object-cluster similarity calculation is modified to accommodate the proposed possibilistic methods. The validity of the proposed methods is verified through numerical examples.
Yuchi Kanzawa

A Unified Theory of Fuzzy c-Means Clustering Models with Improved Partition

Abstract
This paper attempts to unify the theory of a certain class of modified variants and another class of manipulated versions of the fuzzy c-means algorithm. Starting from the objective function of the so-called fuzzy c-means algorithm with generalized improved partition (GIFP-FCM), and defining its rewarding term in a more flexible way, we obtain a unified algorithm that can model all algorithm variants in question including the wide family of suppressed and generalized suppressed FCM. Numerical tests were carried out to provide a comparison of the modeled algorithms in terms of accuracy and cluster size insensitivity. The suppression of the probabilistic fuzzy partition obtained at high values of the fuzzy exponent m proved the most effective.
László Szilágyi

Data Mining and Data Privacy

Frontmatter

Effective MVU via Central Prototypes and Kernel Ridge Regression

Abstract
Maximum variance unfolding (MVU) is one of the most prominent manifold learning techniques for nonlinear dimensionality reduction. Despite its effectiveness it has proven to be considerably slow on large data sets, for which fast extensions have been developed. In this paper we present a novel algorithm which combines classical MVU and multi-output kernel ridge regression (KRR). The proposed method, called Selective MVU, is based on a three-step procedure. First, a subset of distinguished points indicated as central prototypes is selected. Then, MVU is applied to find the prototypes embedding in the low-dimensional space. Finally, KRR is used to reconstruct the projections of the remaining samples. Preliminary results on benchmark data sets highlight the usefulness of Selective MVU which exhibits promising performances in terms of quality of the data embedding compared to renowned MVU variants and other state-of-the-art nonlinear methods.
Carlotta Orsenigo

Cooperative Multi-agent Learning in a Large Dynamic Environment

Abstract
In this work, we are addressing the problem of cooperative multi-agent learning for distributed decision making in non stationary environments. Our principal focus is to improve learning by exchanging information between local neighbors (agents) and to ensure the adaption to the new environmental form without ignoring knowledge already acquired. First, a distributed dynamic correlation matrix based on multi-Q learning method, presented in [1], is evaluated. To overcome the shortcomings of this method, a new multi-agent reinforcement learning approach and a new cooperative action selection strategy are developed. Several simulation tests are conducted using a cooperative foraging task with a single moving target and show the efficiency of the proposed methods in the case of large, unknown and temporary dynamic environments.
Wiem Zemzem, Moncef Tagina

Optimized and Parallel Query Processing in Similarity-Based Databases

Abstract
We present a novel method of query execution in similarity-based databases which adopts techniques commonly used in traditional programming language compilers. Our method is based on decomposition of relational algebra operators into a small set of simple operations which are subject of further optimizations. It shows up that with a small set of optimizations rules our system itself is able to infer efficient algorithms for data processing. Furthermore, operations we propose are compatible with the map/reduce approach to data processing, and thus, allows for implicitly parallel or distributed data processing.
Petr Krajča

An Evaluation of Edge Modification Techniques for Privacy-Preserving on Graphs

Abstract
Noise is added by privacy-preserving methods or anonymization processes to prevent adversaries from re-identifying users in anonymous networks. The noise introduced by the anonymization steps may also affect the data, reducing its utility for subsequent data mining processes. Graph modification approaches are one of the most used and well-known methods to protect the privacy of the data. These methods converts the data by edges or vertices modifications before releasing the perturbed data. In this paper we want to analyse the edge modification techniques found in the literature covering this topic, and then empirically evaluate the information loss introduced by each of these methods. We want to point out how these methods affect the main properties and characteristics of the network, since it will help us to choose the best one to achieve a desired privacy level while preserving data utility.
Jordi Casas-Roma

Co-utile Collaborative Anonymization of Microdata

Abstract
In surveys collecting individual data (microdata), each respondent is usually required to report values for a set of attributes. If some of these attributes contain sensitive information, the respondent must trust the collector not to make any inappropriate use of the data and, in case any data are to be publicly released, to properly anonymize them to avoid disclosing sensitive information. If the respondent does not trust the data collector, she may report inaccurately or report nothing at all. The reduce the need for trust, local anonymization is an alternative whereby each respondent anonymizes her data prior to sending them to the data collector. However, local anonymization by each respondent without seeing other respondents’ data makes it hard to find a good trade-off minimizing information loss and disclosure risk. We propose a distributed anonymization approach where users collaborate to attain an appropriate level of disclosure protection (and, thus, of information loss). Under our scheme, the final anonymized data are only as accurate as the information released by each respondent; hence, no trust needs to be assumed towards the data collector or any other respondent. Further, if respondents are interested in forming an accurate data set, the proposed collaborative anonymization protocols are self-enforcing and co-utile.
Jordi Soria-Comas, Josep Domingo-Ferrer

Generalization-Based k-Anonymization

Abstract
Microaggregation is an anonymization technique consisting on partitioning the data into clusters no smaller than k elements and then replacing the whole cluster by its prototypical representant. Most of microaggregation techniques work on numerical attributes. However, many data sets are described by heterogeneous types of data, i.e., numerical and categorical attributes. In this paper we propose a new microaggregation method for achieving a compliant k-anonymous masked file for categorical microdata based on generalization. The goal is to build a generalized description satisfied by at least k domain objects and to replace these domain objects by the description. The way to construct that generalization is similar that the one used in growing decision trees. Records that cannot be generalized satisfactorily are discarded, therefore some information is lost. In the experiments we performed we prove that the new approach gives good results.
Eva Armengol, Vicenç Torra

Logics

Frontmatter

The Complexity of 3-Valued Łukasiewicz Rules

Abstract
It is known that determining the satisfiability of n-valued Łukasiewicz rules is NP-complete for \(n \ge 4\), as well as that it can be solved in time linear in the length of the formula in the Boolean case (when \(n=2\)). However, the complexity for \(n=3\) is an open problem. In this paper we formally prove that the satisfiability problem for 3-valued Łukasiewicz rules is NP-complete. Moreover, we also prove that when the consequent of the rule has at most one element, the problem is polynomially solvable.
Miquel Bofill, Felip Manyà, Amanda Vidal, Mateu Villaret

Information Theory for Subjective Logic

Abstract
Uncertainty plays an important role in decision making. People try to avoid risks introduced by uncertainty. Probability theory can model these risks, and information theory can measure these risks. Another type of uncertainty is ambiguity; where people are not aware of the probabilities. People also attempt to avoid ambiguity. Subjective logic can model ambiguity-based uncertainty using opinions. We look at extensions of information theory to measure the uncertainty of opinions.
Tim Muller, Dongxia Wang, Audun Jøsang

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise