Search

Multidimensional fuzzy sets (MFS) is a new extension of fuzzy sets on which the membership values of an element in the universe of discourse are increasingly ordered vectors on the set of real numbers in the interval [ 0 , 1 ]. This paper aims to investigate fuzzy negations on the set of increasingly ordered vectors on [ 0 , 1 ] , i.e. on L ∞ ([ 0 , 1 ]) , MFN in short, with respect to some partial order. In this paper we study partial orders, giving special attention to admissible orders on L n ([ 0 , 1 ]) and L ∞ ([ 0 , 1 ]). In addition, we study the possibility of existence of strong multidimensional fuzzy negations and some properties and methods to construct such operators. In particular, we define the ordinal sums of n-dimensional negations and ordinal sums of multidimensional fuzzy negations on a multidimensional product order. A multi-attribute group decision making algorithm is presented. [ABSTRACT FROM AUTHOR]

In this paper, we study structures such as distributive lattices, distributive semilattices, and median graphs from an algorithmic point of view. Such structures are very useful in classification and phylogeny for representing lineage relationships for example. A distributive lattice can be considered as a median graph while a distributive ∨-semilattice can be considered as a median graph provided that some conditions holding on triple of elements are satisfied. Starting from a lattice structure with different representations, we study the problem of building a median graph from such structures. We make precise and propose algorithms for checking how a lattice can be distributive and can be a median graph. Then, we adapt the problem to semilattices as a lattice where the bottom element is removed is a ∨-semilattice. We also state the problem in terms of Formal Concept Analysis and the representation of a lattice as a formal context, i.e., a binary table. Moreover, we also propose as input a system of implications such as the Duquenne-Guigues basis of a lattice, and we study how to compute such a basis for a distributive semilattice. In the paper, we provide algorithms and examples which illustrate the difficulties related to these different classification tasks. In particular, the minimality of the output lattices is a condition which is hard to ensure and which cannot be always achieved. [ABSTRACT FROM AUTHOR]

Shadowed sets, as a three-way approximation of fuzzy sets, employ two thresholds (α , β) to maintain the essence of fuzzy sets with reduced computing complexity and simpler semantic interpretation by allowing quantification of numeric membership grades into three parts: core, total exclusion, and complete uncertainty. An essential issue in inducing shadowed sets is determining the thresholds (α , β) and maintaining the consistency in fuzziness. However, it is found that the existing interval shadowed sets (ISS) have a significant fuzziness loss. In addition, the algorithm used to obtain the threshold pairs in ISS need to be further optimized. To this end, a novel method to induce interval shadowed sets based on a new objective function is proposed in this paper. Firstly, the shortcomings of the objective function and fuzziness loss of ISS are analyzed. Then, a new objective function is given, and interval shadowed sets with less fuzziness loss are induced based on this objective function. Afterwards, a fast algorithm is developed to obtain interval shadowed sets quickly. Finally, the rationality and validity of the proposed method are verified by experimental results. [ABSTRACT FROM AUTHOR]

Three-way concept analysis is a research hotspot. Inspired by multi-scale information system, some scholars put forward and researched multi-granularity formal context. Most of the existing algorithms for constructing three-way concept lattice take care of the static formal contexts and can not deal with the multi-granularity formal context. To address this problem, this paper primarily focuses on a constructing approach to object-induced three-way concept (OE-concept) lattices for multi-granularity formal contexts. Firstly, transformation relationships between OE-concepts based on different granularities are researched. Secondly, the mutual transformation between OE-concept lattices under different granularities is proposed via these relationships, and then corresponding algorithms are proposed. Finally, several groups of datasets are selected from UCI for comparative experiments. Experimental results exhibit that our algorithms are more effective and advantageous than the latest construction algorithms. [ABSTRACT FROM AUTHOR]

Pattern mining is one of the most studied fields in data mining. Being mostly motivated by practitioners, pattern mining algorithms are often based on heuristics and are lacking suitable formalization. In this paper, we are revisiting pattern mining, and especially itemset mining, which allows one to analyze binary datasets in searching for interesting and meaningful itemsets and respective association rules. We introduce a concise representation –the closure structure– based on closed itemsets and their minimum generators (called "passkeys") for capturing the intrinsic content of a dataset. The closure structure allows one to understand the content of the dataset in terms of closed sets and equivalence classes of itemsets. We discuss theoretical properties of passkeys which are concise representatives of closed itemsets. We propose a formalization of the closure structure and passkeys in terms of Formal Concept Analysis, which is well adapted to studying such elements. Besides theoretical results, we present the GDPM algorithm for enumerating passkeys and discovering the closure structure. GDPM is rather unique as it returns a characterization of a dataset content in terms of complexity levels, highlighting the diversity and the distribution of the itemsets. Finally, some experiments show how the GDPM algorithm and the closure structure can be practically used. [ABSTRACT FROM AUTHOR]

Efficiently discovering causal relations from data and representing them in a way that facilitates their use is an important problem in science that has received much attention. In this paper, we propose an adaptation of the Formal Concept Analysis formalism to the problem of discovering and representing causal relations. We show that Formal Concept Analysis structures and algorithms are well-suited to this problem. [ABSTRACT FROM AUTHOR]

Time series clustering with a dissimilarity matrix based on tail dependence coefficients estimated by copula functions has been proposed in 2011 by De Luca and Zuccolotto, who used a two-step procedure allowing to resort to the k -means algorithm. The possibility to carry out hierarchical clustering directly on the dissimilarity matrix is still an open issue and the main concerns are relative to the meaning of the most common linkage methods in the context of tail dependence. In this paper, in a multivariate copula approach, we propose a linkage method based on the tail dependence coefficients between the clusters that are agglomerated at each iteration of the hierarchical clustering algorithms. [ABSTRACT FROM AUTHOR]

Bayesian network (BN) structure learning from complete data has been extensively studied in the literature. However, fewer theoretical results are available for incomplete data, and most are related to the Expectation-Maximisation (EM) algorithm. Balov [1] proposed an alternative approach called Node-Average Likelihood (NAL) that is competitive with EM but computationally more efficient; and he proved its consistency and model identifiability for discrete BNs. In this paper, we give general sufficient conditions for the consistency of NAL; and we prove consistency and identifiability for conditional Gaussian BNs, which include discrete and Gaussian BNs as special cases. Furthermore, we confirm our results and the results in Balov [1] with an independent simulation study. Hence we show that NAL has a much wider applicability than originally implied in Balov [1] , and that it is competitive with EM for conditional Gaussian BNs as well. [ABSTRACT FROM AUTHOR]

Dynamic Bayesian networks have been well explored in the literature as discrete-time models: however, their continuous-time extensions have seen comparatively little attention. In this paper, we propose the first implementation of a constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence. Furthermore, we analyze and discuss the computational complexity of the best and worst cases for the proposed algorithm. Finally, we validate its performance using synthetic data, and we discuss its strengths and limitations comparing it with the score-based structure learning algorithm from Nodelman et al. [23]. We find the latter to be more accurate in learning networks with binary variables, while our constraint-based approach is more accurate with variables assuming more than two values. Numerical experiments confirm that score-based and constraint-based algorithms are comparable in terms of computation time. [ABSTRACT FROM AUTHOR]

Kernel weighted fuzzy local information c-means clustering (KWFLICM) is of great significance in the field of fuzzy clustering. Nevertheless, it is sensitive to high noise or outliers. Aiming at the shortcoming of KWFLICM algorithm, this paper proposes a novel fuzzy local information c-means clustering algorithm utilizing total Bregman divergence driven by polynomial kernel function (TKWFLICM). Firstly, total Bregman divergence (TBD) is kernelized by global polynomial kernel function to solve the problem of kernel-based distance metric without rotation-invariance. Secondly, TBD with polynomial kernel metric is modified by local neighborhood information of current pixel to further enhance the ability to suppress the noise in image. In the end, the modified TBD with polynomial kernel is introduced into the objective function of KWFLICM, and then a novel robust fuzzy clustering with high robustness is obtained. Experimental results show that the proposed algorithm performs better than existing state-of-the-art KWFLICM algorithm, and the kernelized TBD can also be utilized in fuzzy clustering-related algorithms, which will enhance the anti-noise robustness of these algorithms. [ABSTRACT FROM AUTHOR]

Argumentative agents in AI are inspired by how humans reason by exchange of arguments. Given the same set of arguments possibly attacking one another (Dung's AA framework) these agents are bound to accept the same subset of those arguments (aka extension) unless they reason by different argumentation semantics. However humans may not be so predictable, and in this paper we assume that this is because any real agent's reasoning is inevitably influenced by her own preferences over the arguments. Though such preferences are usually unobservable, their effects on the agent's reasoning cannot be washed out. Hence by reconstructing her reasoning process, we might uncover her hidden preferences, which then allow us to predict what else the agent must accept. Concretely we formalize and develop algorithms for such problems as uncovering the hidden argument preference relation of an agent from her expressed opinion, by which we mean a subset of arguments or attacks she accepted from a given AA framework; and uncovering the collective preferences of a group from a dataset of individual opinions. A major challenge we addressed in this endeavor is to deal with "answer sets" of argument preference relations which are generally exponential or even infinite. So we start by developing a compact representation for such answer sets called preference states. Preference revelation tasks are then structured as derivations of preference states from data, and reasoning prediction tasks are reduced to manipulations of derived preference states without enumerating the underlying (possibly infinite) answer sets. We also apply the presented results to two non-trivial problems: learning preferences over rules in structured argumentation with priorities – an open problem so far; and analyzing public polls in apparently deeper ways than existing social argumentation frameworks allow. [ABSTRACT FROM AUTHOR]

Aiming at the difficult problems of dealing with mass linguistic information in uncertain environment, this paper mainly focuses on a linguistic reasoning algorithm based on property-oriented linguistic concept lattice by combining concept lattice and neural network. Specifically, we present a property-oriented linguistic concept lattice to express linguistic information between concepts based on linguistic term set. Furthermore, we are devoted to the study of rule extraction of fuzzy linguistic formal decision context by constructing property-oriented linguistic decision concepts. In order to obtain more decision knowledge from known linguistic rules, an extension method of linguistic decision rules is developed, which takes advantage of the dominance relation between similar rules on the premise of consistent property-oriented linguistic decision rules. In addition, we construct a multiple multidimensional linguistic reasoning model for predicting uncertain decision information. Moreover, we input a multiple multidimensional linguistic reasoning model with property-oriented linguistic decision information into neural network to obtain unknown decision results, which can not only improve the accuracy of inference results but also reduce the loss of linguistic information. Finally, some experiments are conducted to demonstrate the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

In three-way concept analysis, changing (decreasing or increasing) attribute-granularity levels is needed to seek desirable information. Reconstructing three-way concept lattices often requires huge computation and long elapsed time when attribute-granularity levels are changed. To avoid this problem, a good strategy is indirectly renewing three-way concept lattices. Our paper studies how to renew object-induced three-way concept lattices involving decreasing attribute-granularity levels. Firstly, we analyze changes of object-induced three-way concept lattices when attribute-granularity levels are decreased. To classify changes of object-induced three-way concepts, we classify these concepts into six categories, derive sufficient and necessary conditions of identifying these categories, and investigate their properties. To explore changes of covering relations among object-induced three-way concepts, we classify covering relations into three categories, and identify them by finding which are the destructors of deleted object-induced three-way concepts before the decrease, and analyzing which are children concepts of object-induced three-way concepts as destructors after the decrease. Secondly, by using the above analysis results, we put forward a novel algorithm called OEL-Collapse to renew object-induced three-way concept lattices when attribute-granularity levels are decreased. Finally, experiments are conducted to illustrate the efficiency of the OEL-Collapse algorithm. [ABSTRACT FROM AUTHOR]

Independence relations in general include exponentially many statements of independence, that is, exponential in the number of variables involved. These relations are typically characterised however, by a small set of such statements and an associated set of derivation rules. While various computational problems on independence relations can be solved by manipulating these smaller sets without the need to explicitly generate the full relation, existing algorithms for constructing these sets are associated with often prohibitively high running times. In this paper, we introduce a lattice structure for organising sets of independence statements and show that current algorithms are rendered computationally less demanding by exploiting new insights in the structural properties of independence gained from this lattice organisation. By means of a range of experimental results, we subsequently demonstrate that through the lattice organisation indeed a substantial gain in efficiency is achieved for fast-closure computation of semi-graphoid independence relations in practice. [ABSTRACT FROM AUTHOR]

Credal networks generalize Bayesian networks to allow for imprecision in probability values. This paper reviews the main results on credal networks under strong independence, as there has been significant progress in the literature during the last decade or so. We focus on computational aspects, summarizing the main algorithms and complexity results for inference and decision making. We address the question "What is really known about strong extensions of credal networks?" by looking at theoretical results and by presenting a short summary of real applications. [ABSTRACT FROM AUTHOR]

The paper proposes a method of damage detection in elastic materials, which is based on analyzing the time-dependent (dynamic) response of the material excited by an acoustic signal. A case study is presented consisting of experimental measurements and their mathematical analysis. The decisive parameters (wave speed and damping coefficient) of a mathematical model of the acoustic wave are calibrated by comparing the measurement data with the numerically evaluated exact solution predicted by the mathematical model. The calibration is done both deterministically by minimizing the square error over time and stochastically by a Bayesian approach, implemented through the Metropolis-Hastings algorithm. The resulting posterior distribution of the parameters can be used to construct a Bayesian test for damage. [ABSTRACT FROM AUTHOR]

This paper presents an axiomatic framework for influence diagram computation, which allows reasoning with partially ordered values of utility. We show how an algorithm based on sequential variable elimination can be used to compute the set of maximal values of expected utility (up to an equivalence relation). Formalisms subsumed by the framework include decision making under uncertainty based on multi-objective utility, or on interval-valued utilities, as well as a more qualitative decision theory based on order of magnitude probabilities and utilities. Consequently, we also introduce the order of magnitude influence diagram to model and solve partially specified sequential decision problems when only qualitative (or imprecise) information is available. [ABSTRACT FROM AUTHOR]

Rule reduction is one of the focuses of numerous researches on belief-rule-based system, in some cases, too many redundant rules may be a concern to the rule-based system. Though rule reduction methods have been widely used in the belief-rule-based system, extended belief-rule-based system, which is an expansion of belief-rule-based system, still lacks methods to reduce and train rules in the extended belief rule base (EBRB). To this end, this paper proposes an EBRB reduction and training method. Based on the density-based spatial clustering applications with noise (DBSCAN) algorithm, a new EBRB reduction method is proposed, where all the rules in the EBRB will be visited and rules within the distance of the fusion threshold will be fused. Moreover, the EBRB training method using parameter learning, which uses a set of training data to train the parameters of EBRB, is also proposed to improve the accuracy of the EBRB system. Two case studies of regression and classification are used to illustrate the feasibility and efficiency of the proposed EBRB reduction and training method. Comparison results show that the proposed method can effectively downsize the EBRB and increase the accuracy of EBRB system. [ABSTRACT FROM AUTHOR]

Community detection is a hot research in complex network analysis. Detecting community structure in networks is crucial for insight into the internal connections within networks. A variety of algorithms have previously been proposed, while few of them can efficiently apply to large-scale networks due to unacceptable running time and intractable parameter tuning. To tackle the above issues, this paper proposes an adaptive granulation algorithm for community detection based on improved label propagation (Gr-ILP), which granulates a network hierarchically with the improved label propagation strategy. For a given network, first, an improved label propagation strategy (ILP) is adopted to gather similar nodes into non-overlapping collections which consist of nodes with high similarity. Second, each collection detected in first step is granulated into a super node, and the edges between two collections are granulated into a super edge. After this granulation processing, a super-network that is coarser and smaller than the original one is formed. Then, the above two steps are repeated iteratively until it stops forming new collections in the first step. Due to the adoption of an adaptive strategy, the proposed Gr-ILP algorithm granulates the network to a certain layer which saves much time when processing large-scale networks. Finally, Gr-ILP assigns unallocated and isolated nodes to the appropriate community. The proposed algorithm requires neither any priori information of communities nor adjustment of any parameters and still can obtained satisfactory community structure adaptively. Gr-ILP tends to preserve small-scale communities by limiting the growth of node collections. Moreover, because of the sharp decline in network size by the granulation process, the algorithm consumes less time and is suitable for large-scale networks. Experimental results on eight real-world network datasets of different types and sizes demonstrate the effectiveness and efficiency of our algorithm, compared with several other baseline algorithms. [ABSTRACT FROM AUTHOR]

Dismantling allows for the removal of elements from a poset, or in our case lattice, without disturbing the remaining structure. In this paper we have extended the notion of dismantling by single elements to the dismantling by intervals in a lattice. We utilize theory from Formal Concept Analysis (FCA) to show that lattices dismantled by intervals correspond to closed subrelations in the respective formal context, and that there exists a unique core with respect to dismantling by intervals. Furthermore, we show that dismantling intervals can be identified directly in the formal context utilizing a characterization via arrow relations and provide an algorithm to compute all dismantling intervals. [ABSTRACT FROM AUTHOR]

Abstract: This paper considers the problem of ordering arc-reversal operations and breaking ties in cost measures when eliminating variables in Lazy AR Propagation (LPAR). In particular, the paper presents the BreakTies algorithm for breaking ties in cost measures when selecting the next arc to reverse in a variable elimination operation. BreakTies is based upon using a sequence of cost measures instead of randomly selecting an arc to reverse when multiple arcs share the same cost. The paper reports on an experimental evaluation of LPAR for belief update in Bayesian networks considering six sequences of five cost measures for breaking ties using BreakTies. The experimental results show that using BreakTies to select the next arc to reverse in a variable elimination operation can improve performance of LPAR. [Copyright &y& Elsevier]

Abstract: In this paper, by adopting a coherence-based probabilistic approach to default reasoning, we focus the study on the logical operation of quasi conjunction and the Goodman–Nguyen inclusion relation for conditional events. We recall that quasi conjunction is a basic notion for defining consistency of conditional knowledge bases. By deepening some results given in a previous paper we show that, given any finite family of conditional events and any nonempty subset of , the family p-entails the quasi conjunction ; then, given any conditional event , we analyze the equivalence between p-entailment of from and p-entailment of from , where is some nonempty subset of We also illustrate some alternative theorems related with p-consistency and p-entailment. Finally, we deepen the study of the connections between the notions of p-entailment and inclusion relation by introducing for a pair the (possibly empty) class of the subsets of such that implies . We show that the class satisfies many properties; in particular is additive and has a greatest element which can be determined by applying a suitable algorithm. [Copyright &y& Elsevier]

Abstract: The variable precision rough set model and graded rough set model are 2 important extended rough set models. This paper aims to make a comparative study of the 2 models. Rough set regions, primitive notions, are proposed first for the 2 models, which classify the universe more precisely. Then, both of their logical meanings related to quantitative indexes and their basic structure are investigated, and their precise descriptions are obtained as well. Furthermore, in the graded rough set model, macroscopic and microscopic algorithms are proposed and analyzed to calculate rough set regions; then, the conclusion is drawn that macroscopic and microscopic algorithms have advantages in time and space complexities, respectively, and a medical example is provided to illustrate the rough set regions and the 2 algorithms. In addition, 3 new properties of the 2 models are investigated, which are the results of extending the classical rough set model, i.e. the relationships between approximations and the basic set, the power actions of approximation operators, and the modifications of approximation operator actions on set operations. Finally, the classical rough set model is used to obtain many corresponding results, and moreover, the relationship and transformation between the 2 models is investigated. The study results of this paper have extended and enriched rough set theory from both operator-oriented and set-oriented points of view. [Copyright &y& Elsevier]

Abstract Neighborhood rough sets are widely used as an effective tool to deal with numerical data. However, most of the existing neighborhood granulation models cannot well describe the neighborhoods of category-mixed samples when they are used to characterize the classification ability of a subset of attributes. In this paper, we propose a new neighborhood rough set model called k -nearest neighborhood rough sets. This model combines the advantages of both δ -neighborhood and k -nearest neighbor, and has a better ability to deal with this type of heterogeneous data than the existing models. We employ an iterative strategy to define rough approximations of a decision and discuss their monotonicity. Furthermore, an attribute reduction algorithm based on this model is designed. Experimental analysis shows that the proposed algorithm has better performance than some existing algorithms, especially the δ -neighborhood rough set model and k -nearest neighbor rough set model. [ABSTRACT FROM AUTHOR]

Abstract The study of properties of gradual evaluation methods in argumentation has received increasing attention in recent years, with studies devoted to various classes of frameworks/ methods leading to conceptually similar but formally distinct properties in different contexts. In this paper we provide a novel systematic analysis for this research landscape by making three main contributions. First, we identify groups of conceptually related properties in the literature, which can be regarded as based on common patterns and, using these patterns, we evidence that many further novel properties can be considered. Then, we provide a simplifying and unifying perspective for these groups of properties by showing that they are all implied by novel parametric principles of (either strict or non-strict) balance and monotonicity. Finally, we show that (instances of) these principles (and thus the group, literature and novel properties that they imply) are satisfied by several quantitative argumentation formalisms in the literature, thus confirming the principles' general validity and utility to support a compact, yet comprehensive, analysis of properties of gradual argumentation. [ABSTRACT FROM AUTHOR]

Abstract Markov Decision Processes (mdp s) are commonly used to solve sequential decision problems. A less restrictive model is the Bounded-parameter mdp (bmdp) that allows: (i) the transition function to be expressed in terms of probability intervals and (ii) reasoning about a robust solution, i.e., the best solution under the worst model. In this paper, we propose the Robust Topological Policy Iteration (rtpi) algorithm which is a new policy iteration algorithm for infinite horizon bmdp s based on a partition of the state space. The empirical results show that the more structured the domain, the better is the performance of rtpi. [ABSTRACT FROM AUTHOR]

Abstract Fuzzy objective relation systems are an important class of datasets that are generalizations of many types of decision tables. This paper proposes an approach, based on relation systems and fuzzy sets, to reduce data redundancy in fuzzy objective relation systems. We study lower and upper approximation reductions of a relation system for a given fuzzy set. As a generalization of such reductions, we consider lower and upper approximation reductions of fuzzy objective relation systems and give their corresponding reduction algorithms using methods based on the discernibility matrix. We note that the usual positive region reduction for a decision table can be considered a special case of our lower approximation reduction. Finally, we provide two examples from the UCI datasets to verify our theoretical results. These results can help in the decision making analysis of fuzzy objective relation systems. [ABSTRACT FROM AUTHOR]

Abstract Active learning is a man-machine interaction scenario in which the machine acquires information actively from the expert. Cost-sensitive active learning balances the misclassification cost with the teacher cost paid for label queries. Inspired by granular computing (GrC) and three-way decision (3WD), this paper presents a new algorithm called cost-sensitive active learning through density clustering under a label uniform distribution model (CADU). CADU iteratively divides the universe, queries labels, and classifies instances until each label is queried or predicted. The density clustering technique is used to divide the universe into blocks. A label uniform distribution model is built to calculate the expected label distribution of each block. According to the teacher and misclassification cost settings, an optimization function is designed to determine the number of labels to be queried. Comparison study with 10 state-of-the-art algorithms are undertaken on 12 public datasets. Results show that CADU outperforms others in terms of average cost. [ABSTRACT FROM AUTHOR]

Abstract Coherent lower previsions are general probabilistic models allowing incompletely specified probability distributions. However, for complete description of a coherent lower prevision – even on finite underlying sample spaces – an infinite number of assessments is needed in general. Therefore, they are often only described approximately by some less general models, such as coherent lower probabilities or in terms of some other finite set of constraints. The magnitude of error induced by the approximations has often been neglected in the literature, despite the fact that it can be significant, with substantial impact on consequent decisions. An apparent reason is that no widely used general method for estimating the error seems to be available at the moment. This paper provides a practically applicable method that allows calculating an upper bound for the maximal error induced by approximating a coherent lower probability with its values on a finite set of gambles. An algorithm is also provided with an estimation of its computational complexity. [ABSTRACT FROM AUTHOR]

Abstract In covering-based rough sets, many basic issues are related to minimal and maximal descriptions. For a covering approximation space with a large cardinal, it would be tedious and complicated to use set representations to solve the issues about minimal and maximal descriptions. Therefore it is necessary to study matrix representations by which calculations will become algorithmic and can be easily implemented by computers. In this paper, we use matrix approaches to investigate some issues about minimal and maximal descriptions in covering-based rough sets. Firstly, several new matrices and matrix operations are defined by which one can compute the minimal description and the approximation operator about the minimal description. Inspired by this result, a matrix method is presented to judge whether a covering is unary. Secondly, the maximal description and the approximation operator about the maximal description are also computed by these new matrices and matrix operations. Finally, based on the above results, we propose a matrix method to efficiently compute reductions of coverings. Moreover, we propose two types of reducts of covering information systems via minimal and maximal descriptions respectively, and we use matrix approaches to compute them. In a word, these results show an interesting view to investigate the combination between matrices and covering-based rough sets. [ABSTRACT FROM AUTHOR]

Abstract An essential step in data mining and machine learning is selecting a useful feature subset from the high-dimensional feature space. Many existing feature selection algorithms only consider precision, but do not consider error types and test cost. In this paper, we use the ℓ 2 , 1 -norm to propose a cost-sensitive embedded feature selection algorithm that minimizes the total cost rather than maximizing accuracy. The algorithm is a cost-sensitive feature selection algorithm with joint ℓ 2 , 1 -norm minimization of the loss function with misclassification costs. The ℓ 2 , 1 -norm based loss function with misclassification costs is robust to outliers. We also add an orthogonal constraint term to guarantee that each selected feature is independent. The proposed algorithm simultaneously takes into account both test costs and misclassification costs. Finally, an iterative updating algorithm is provided using the objective function that makes cost-sensitive feature selection more efficient. The cost-sensitive feature selection algorithm is more realistic than existing feature selection algorithms. Extensive experimental results on publicly available datasets demonstrate that the proposed algorithm is effective, can select a low-cost subset and achieve better performance than other feature selection algorithms in real-world applications. [ABSTRACT FROM AUTHOR]

Abstract The benefits of automating design cycles for Bayesian inference-based algorithms are becoming increasingly recognized by the machine learning community. As a result, interest in probabilistic programming frameworks has much increased over the past few years. This paper explores a specific probabilistic programming paradigm, namely message passing in Forney-style factor graphs (FFGs), in the context of automated design of efficient Bayesian signal processing algorithms. To this end, we developed "ForneyLab" 2 as a Julia toolbox for message passing-based inference in FFGs. We show by example how ForneyLab enables automatic derivation of Bayesian signal processing algorithms, including algorithms for parameter estimation and model comparison. Crucially, due to the modular makeup of the FFG framework, both the model specification and inference methods are readily extensible in ForneyLab. In order to test this framework, we compared variational message passing as implemented by ForneyLab with automatic differentiation variational inference (ADVI) and Monte Carlo methods as implemented by state-of-the-art tools "Edward" and "Stan". In terms of performance, extensibility and stability issues, ForneyLab appears to enjoy an edge relative to its competitors for automated inference in state-space models. [ABSTRACT FROM AUTHOR]

Abstract Robust regression analysis is a stable method to fit a given dataset especially when the data set includes outliers. It has been developed with various approaches due to its practical usefulness and insensitivity to outliers. In this paper, we propose a new hybrid algorithm based on several robust methods combined with F (fuzzy)-transform to compare its performances with several robust methods. Some M -estimators such as L 1 , L 1 − L 2 and Fair have been used as existing robust methods. L 2 , which is very sensitive to outliers, also has been used for comparison. Additionally, the Orthogonal distance regression (ODR) is introduced to enhance the deficiency of basic distance of error. To find the estimated parameters which minimize the objective functions, the Genetic Algorithm (GA) is used as an optimization algorithm. The performances are measured in R M S E , M A D and M A P E to compare their accuracies. Three examples are provided and the results show that the proposed hybrid methods are much more superior to existing robust methods such as L 1 , L 1 − L 2 and Fair. [ABSTRACT FROM AUTHOR]

Abstract In the research spectrum of rough set, the task of attribute reduction is obtaining a minimal attribute subset that preserves certain properties of the original data. Cost-sensitive attribute reduction aims at minimizing various types of costs. Approximate attribute reduction allows decision makers to leverage the advantages of knowledge discovery and their own preferences. This paper proposes the cost-sensitive approximate attribute reduction problem under both qualitative and quantitative criteria. The qualitative criterion refers to the indiscernibility, while the quantitative criterion refers to the approximate parameter ε and the cost. We present a framework based on three-way decisions and discernibility matrix to handle this new problem. First, a quality function for attribute subsets is designed with the interpretation of a hierarchical granular structure. Second, a fitness function is designed for cost performance index by investigating attribute significance. Third, three-way decision theory is applied to partition the attributes into three groups based on the fitness function and a threshold pair (α , β). Finally, deletion-based and addition-based cost-sensitive approximate reduction algorithms are designed under this framework. Experimental results indicate that our algorithms outperform the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Abstract: This paper derives a particle filter algorithm within the Dempster–Shafer framework. Particle filtering is a well-established Bayesian Monte Carlo technique for estimating the current state of a hidden Markov process using a fixed number of samples. When dealing with incomplete information or qualitative assessments of uncertainty, however, Dempster–Shafer models with their explicit representation of ignorance often turn out to be more appropriate than Bayesian models. The contribution of this paper is twofold. First, the Dempster–Shafer formalism is applied to the problem of maintaining a belief distribution over the state space of a hidden Markov process by deriving the corresponding recursive update equations, which turn out to be a strict generalization of Bayesian filtering. Second, it is shown how the solution of these equations can be efficiently approximated via particle filtering based on importance sampling, which makes the Dempster–Shafer approach tractable even for large state spaces. The performance of the resulting algorithm is compared to exact evidential as well as Bayesian inference. [Copyright &y& Elsevier]

In this paper we propose a scalable importance sampling algorithm for computing Gaussian mixture posteriors in conditional linear Gaussian Bayesian networks. Our contribution is based on using a stochastic gradient ascent procedure taking as input a stream of importance sampling weights, so that a mixture of Gaussians is dynamically updated with no need to store the full sample. The algorithm has been designed following a Map/Reduce approach and is therefore scalable with respect to computing resources. The implementation of the proposed algorithm is available as part of the AMIDST open-source toolbox for scalable probabilistic machine learning ( http://www.amidsttoolbox.com ). [ABSTRACT FROM AUTHOR]

In covering rough set theory, the basic problem is the calculation of lower and upper approximations for subsets of a covering approximation space. For a covering approximation space with a large cardinal, using definitions to calculate approximations would be tedious and complicated. So it is important to investigate matrix methods by which calculations will become algorithmic and can be easily implemented by computers. Since the covering in a covering approximation space can be represented by a Boolean matrix, every covering rough approximation operator must be closely related to this matrix. In this paper, we investigated 32 pairs of neighborhood-based dual lower and upper approximation operators and successfully obtained all the matrix representations of them. Some examples were presented in the manuscript to illustrate how to use matrix methods to compute lower and upper approximations and examples were also given to solve the inverse problem, i.e., finding all the subsets whose lower or upper approximation is a given subset. [ABSTRACT FROM AUTHOR]

Abstract: In the literature several authors describe methods to construct simplified models of networks. These methods are motivated by the need to gain insight into the main properties of medium sized or large networks. The present paper contributes to this research by setting focus on weighted networks, the geographical component of networks and introducing a class of functions to model how the weights propagate from one level of abstraction to the next. Hierarchies of network models can be constructed from reordering of the adjacency matrix of the network; this is how “hypernodes” are derived in the present paper. The hypernode algorithm is explored and it is shown how it can be formulated to handle weighted networks. Weighted networks enable handling the uncertainty or the strength of the components which make up the network. The hypernode algorithm can be run in an iterative manner so that a hierarchy of simplified models of the network can be derived. Some case studies demonstrate the hypernode algorithm. In the first case the algorithm is compared with a similar implementation described in the literature. In the second case an airline dataset is analysed. This study shows that when networks are embedded in the geographical space hypernodes may relate to clusters in the spatial domain. The selection of the visual variables to illustrate the strength of the edges and nodes in a weighted network is discussed. [Copyright &y& Elsevier]

Abstract: This paper presents a hybrid method for identification of Pareto-optimal fuzzy classifiers (FCs). In contrast to many existing methods, the initial population for multiobjective evolutionary algorithms (MOEAs) is neither created randomly nor a priori knowledge is required. Instead, it is created by the proposed two-step initialization method. First, a decision tree (DT) created by C4.5 algorithm is transformed into an FC. Therefore, relevant variables are selected and initial partition of input space is performed. Then, the rest of the population is created by randomly replacing some parameters of the initial FC, such that, the initial population is widely spread. That improves the convergence of MOEAs into the correct Pareto front. The initial population is optimized by NSGA-II algorithm and a set of Pareto-optimal FCs representing the trade-off between accuracy and interpretability is obtained. The method does not require any a priori knowledge of the number of fuzzy sets, distribution of fuzzy sets or the number of relevant variables. They are all determined by it. Performance of the obtained FCs is validated by six benchmark data sets from the literature. The obtained results are compared to a recently published paper [H. Ishibuchi, Y. Nojima, Analysis of interpretability-accuracy tradeoff of fuzzy systems by multiobjective fuzzy genetics-based machine learning, International Journal of Approximate Reasoning 44 (1) (2007) 4–31] and the benefits of our method are clearly shown. [Copyright &y& Elsevier]

Abstract: This paper presents a family of algorithms for approximate inference in credal networks (that is, models based on directed acyclic graphs and set-valued probabilities) that contain only binary variables. Such networks can represent incomplete or vague beliefs, lack of data, and disagreements among experts; they can also encode models based on belief functions and possibilistic measures. All algorithms for approximate inference in this paper rely on exact inferences in credal networks based on polytrees with binary variables, as these inferences have polynomial complexity. We are inspired by approximate algorithms for Bayesian networks; thus the Loopy 2U algorithm resembles Loopy Belief Propagation, while the Iterated Partial Evaluation and Structured Variational 2U algorithms are, respectively, based on Localized Partial Evaluation and variational techniques. [Copyright &y& Elsevier]

Abstract: In this paper we introduce a new dynamic importance sampling propagation algorithm for Bayesian networks. Importance sampling is based on using an auxiliary sampling distribution from which a set of configurations of the variables in the network is drawn, and the performance of the algorithm depends on the variance of the weights associated with the simulated configurations. The basic idea of dynamic importance sampling is to use the simulation of a configuration to modify the sampling distribution in order to improve its quality and so reducing the variance of the future weights. The paper shows that this can be achieved with a low computational effort. The experiments carried out show that the final results can be very good even in the case that the initial sampling distribution is far away from the optimum. [Copyright &y& Elsevier]

Analogy-based classifiers, first proposed in 2007, have been applied with success to Boolean, nominal and numerical data. They rely on an extrapolation mechanism that exploits analogical proportions, which are statements of the form " a is to b as c is to d ". There are usually a great number of triplets (a , b , c) in the data set that lead to a prediction for the class of d. The paper shows that, using a preprocessing step for assessing the "competence" of pairs, it is possible to drastically diminish the number of triplets used for the prediction, with an obvious computational benefit, while preserving, and sometimes improving the accuracy of the results. [ABSTRACT FROM AUTHOR]

The paper addresses a classical problem of computing approximate max–min inverse fuzzy relation. It is an NP-complete problem for which no polynomial time algorithm is known till this date. The paper employs a heuristic function to reduce the search space for finding the solution of the problem. The time-complexity of the proposed algorithm is O(n3), compared to O(kn), which is required for an exhaustive search in the real space of [0,1] at k regular intervals of interval length (1/k). [Copyright &y& Elsevier]

We introduce three different approaches for decision making under uncertainty if (I) there is only partial (both cardinally and ordinally scaled) information on an agent's preferences and (II) the uncertainty about the states of nature is described by a credal set (or some other imprecise probabilistic model). Particularly, situation (I) is modeled by a pair of binary relations, one specifying the partial rank order of the alternatives and the other modeling partial information on the strength of preference. Our first approach relies on decision criteria constructing complete rankings of the available acts that are based on generalized expectation intervals. Subsequently, we introduce different concepts of global admissibility that construct partial orders between the available acts by comparing them all simultaneously. Finally, we define criteria induced by suitable binary relations on the set of acts and, therefore, can be understood as concepts of local admissibility. For certain criteria, we provide linear programming based algorithms for checking optimality/admissibility of acts. Additionally, the paper includes a discussion of a prototypical situation by means of a toy example. [ABSTRACT FROM AUTHOR]

The design of effective bandit algorithms to learn the optimal price is a task of extraordinary importance in all the settings in which the demand curve is not a priori known and the estimation process takes a long time, as customary, e.g., in e-commerce scenarios. In particular, the adoption of effective pricing algorithms may allow companies to increase their profits dramatically. In this paper, we exploit the structure of the pricing problem in online scenarios to improve the performance of state-of-the-art general-purpose bandit algorithms. More specifically, we make use of the monotonicity of the customer demand curve, which suggests the same behavior of the conversion rates, and we exploit the fact that, in many scenarios, companies have a priori information about the order of magnitude of the conversion rate. We design techniques—applicable in principle to any bandit algorithm—capable of exploiting these two properties, and we apply them to Upper Confidence Bound policies both in stationary and nonstationary environments. We show that algorithms exploiting these two properties may significantly outperform state-of-the-art bandit policies in most of the configurations and we also show that the improvement increases as the number of arms increases. In particular, simulations based on real-world data show that our algorithms may increase the profit by 300% or more when compared to the performance achieved by state-of-the-art bandit algorithms. Furthermore, we formally prove that the empirical improvement provided by our algorithms can be achieved without incurring any cost in terms of theoretical guarantees. Indeed, our algorithms present the same asymptotic worst-case regret bounds of the bandit algorithms previously known in the state of the art. [ABSTRACT FROM AUTHOR]

The paper studies the problem of actively learning from instances characterized by imprecise features or imprecise class labels, where by actively learning we understand the possibility to query the precise value of imprecisely specified data. We differ from classical active learning by the fact that in the later, data are either fully precise or completely missing, while in our case they can be partially specified. Such situations can appear when sensor errors are important to encode, or when experts have only specified a subset of possible labels when tagging data. We provide a general active learning technique that can be applied in principle to any model. It is inspired from racing algorithms, in which several models are competing against each others. The main idea of our method is to identify the query that will be the most helpful in identifying the winning model in the competition. After discussing and formalizing the general ideas of our approach, we illustrate it by studying the particular case of binary SVM in the case of interval valued features and set-valued labels. The experimental results indicate that, in comparison to other baselines, racing algorithms provide a faster reduction of the uncertainty in the learning process, especially in the case of imprecise features. [ABSTRACT FROM AUTHOR]

This paper presents decision analysis networks (DANs) as a new type of probabilistic graphical model. Like influence diagrams (IDs), DANs are much more compact and easier to build than decision trees and can represent conditional independencies. In fact, for every ID there is an equivalent symmetric DAN, but DANs can also represent asymmetric problems involving partial orderings of the decisions (order asymmetry), restrictions between the values of the variables (domain asymmetry), and conditional observability (information asymmetry). Symmetric DANs can be evaluated with the same algorithms as IDs. Every asymmetric DAN can be evaluated by converting it into an equivalent decision tree or, much more efficiently, by decomposing it into a tree of symmetric DANs. Given that DANs can solve symmetric problems as easily and as efficiently as IDs, and are more appropriate for asymmetric problems—which include virtually all real-world problems—DANs might replace IDs as the standard type of probabilistic graphical model for decision support and decision analysis. We also argue that DANs compare favorably with other formalisms proposed for asymmetric decision problems. In practice, DANs can be built and evaluated with OpenMarkov, a Java open-source package for probabilistic graphical models. [ABSTRACT FROM AUTHOR]

One of the challenges presented by Boolean matrix factorization consists in what became known as the ability to deal with noise in data. In this paper, we critically examine existing considerations regarding noise, reported results regarding various algorithms' ability to deal with noise, and approaches used to evaluate this ability. We argue that the current understanding is underdeveloped in several respects and, in particular, that the present way to assess the ability to handle noise in data is deficient. We provide a new, quantitative way to assess this ability. Our method is based on a common-sense definition of robustness requiring that the factorizations computed from data should not be affected much by varying the noise in the data. We present an experimental evaluation of several algorithms, and compare the results to the observations available in the literature. The experiments reveal important properties of these algorithms as regards handling noise. In addition to providing methodological justification of some properties claimed in the literature without proper justification, they reveal properties which were not reported as well as properties which counter certain claims made in the literature. Importantly, our approach reveals a line separating robust-to-noise from sensitive-to-noise algorithms, which has not been revealed by the previous approaches. We conclude by outlining open problems to which the present considerations and experiments lead. [ABSTRACT FROM AUTHOR]

Discrete statistical models supported on labeled event trees can be specified using so-called interpolating polynomials which are generalizations of generating functions. These admit a nested representation which is a notion formalized in this paper. A new algorithm exploits the primary decomposition of monomial ideals associated with an interpolating polynomial to quickly compute all nested representations of that polynomial. It hereby determines an important subclass of all trees representing the same statistical model. To illustrate this method we analyze the full polynomial equivalence class of a staged tree representing the best fitting model inferred from a real-world dataset. [ABSTRACT FROM AUTHOR]

While decision trees are a popular formal and quantitative method for determining an optimal decision from a finite set of choices, for all but very simple problems they are computationally intractable. For this reason, Influence Diagrams (IDs) have been used as a more compact and efficient alternative. However, most algorithmic solutions assume that all chance variables are discrete, whereas in practice many are continuous. For such ‘Hybrid’ IDs (HIDs) the current-state-of-the-art algorithms suffer from various limitations on the kinds of inference that can be performed. This paper presents a novel method that overcomes a number of these limitations. The method solves a HID by transforming it to a Hybrid Bayesian Network (HBN) and carrying out inference on this HBN using Dynamic Discretization (DD). It generates a simplified decision tree from the propagated HBN to compute and present the optimal decisions under different decision scenarios. To provide satisfactory performance the method uses ‘inconsistent evidence’ to model functional and structural asymmetry. By using the entire marginal probability distribution of the continuous utility and chance nodes, rather than expected values alone, our method also enhances decision analysis by offering the possibility to consider additional statistics other than expected utility, such as measures of risk. We illustrate our method by using the oil wildcatter example and its variations with continuous nodes. We also use a financial score to combine risk and return measures, for illustration. [ABSTRACT FROM AUTHOR]