Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Locally monotone Boolean and pseudo-Boolean functions Couceiro, Miguel ; Marichal, Jean-Luc ; Waldhauser, Tamás in Discrete Applied Mathematics (2012), 160(12), 1651-1660 We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on ... [more ▼] We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on tuples which differ in less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions. Local monotonicities are shown to be tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions are shown to have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classification of p-locally monotone functions, as well as of functions having p-permutable derivatives, in terms of certain forbidden "sections", i.e., functions which can be obtained by substituting constants for variables. This description is made explicit in the special case when p=2. [less ▲] Detailed reference viewed: 100 (3 UL)Symmetric approximations of pseudo-Boolean functions with applications to influence indexes Marichal, Jean-Luc ; Mathonet, Pierre in Applied Mathematics Letters (2012), 25(8), 1121-1126 We introduce an index for measuring the influence of the $k$th smallest variable on a pseudo-Boolean function. This index is defined from a weighted least squares approximation of the function by linear ... [more ▼] We introduce an index for measuring the influence of the $k$th smallest variable on a pseudo-Boolean function. This index is defined from a weighted least squares approximation of the function by linear combinations of order statistic functions. We give explicit expressions for both the index and the approximation and discuss some properties of the index. Finally, we show that this index subsumes the concept of system signature in engineering reliability and that of cardinality index in decision making. [less ▲] Detailed reference viewed: 73 (4 UL)Reliability of systems with dependent components based on lattice polynomial description ; Marichal, Jean-Luc in Stochastic Models (2012), 28(1), 167-184 Reliability of a system is considered where the components' random lifetimes may be dependent. The structure of the system is described by an associated "lattice polynomial" function. Based on that ... [more ▼] Reliability of a system is considered where the components' random lifetimes may be dependent. The structure of the system is described by an associated "lattice polynomial" function. Based on that descriptor, general framework formulas are developed and used to obtain direct results for the cases where a) the lifetimes are "Bayes-dependent", that is, their interdependence is due to external factors (in particular, where the factor is the "preliminary phase" duration) and b) where the lifetimes' dependence is implied by upper or lower bounds on lifetimes of components in some subsets of the system. (The bounds may be imposed externally based, say, on the connections environment.) Several special cases are investigated in detail. [less ▲] Detailed reference viewed: 96 (6 UL)Hierarchies of local monotonicities and lattice derivatives for Boolean and pseudo-Boolean functions Couceiro, Miguel ; Marichal, Jean-Luc ; Waldhauser, Tamás in Miller, D. Michael; Gaudet, Vincent C. (Eds.) 42nd IEEE International Symposium on Multiple-Valued Logic, ISMVL 2012, Victoria, BC, Canada, May 14-16, 2012 (2012) In this paper we report recent results in [1] concerning local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if each ... [more ▼] In this paper we report recent results in [1] concerning local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if each of its partial derivatives keeps the same sign on tuples which differ on less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions. Local monotonicities are tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classification of p-locally monotone functions, as well as of functions having p-permutable derivatives, in terms of certain forbidden “sections”, i.e., functions which can be obtained by substituting variables for constants. This description is made explicit in the special case when p=2. [less ▲] Detailed reference viewed: 98 (3 UL)Using Choquet integral in Machine Learning: what can MCDA bring? ; ; et al in DA2PL' 2012 - from Multiple Criteria Decision Aid to Preference Learning (2012) In this paper we discuss the Choquet integral model in the realm of Preference Learning, and point out advantages of learning simultaneously partial utility functions and capacities rather than ... [more ▼] In this paper we discuss the Choquet integral model in the realm of Preference Learning, and point out advantages of learning simultaneously partial utility functions and capacities rather than sequentially, i.e., first utility functions and then capacities or vice-versa. Moreover, we present possible interpretations of the Choquet integral model in Preference Learning based on Shapley values and interaction indices. [less ▲] Detailed reference viewed: 158 (0 UL)Polynomial functions over bounded distributive lattices Couceiro, Miguel ; Marichal, Jean-Luc in Journal of Multiple-Valued Logic & Soft Computing (2012), 18(3-4), 247-256 Let $L$ be a bounded distributive lattice. We give several characterizations of those $L^n \to L$ mappings that are polynomial functions, i.e., functions which can be obtained from projections and ... [more ▼] Let $L$ be a bounded distributive lattice. We give several characterizations of those $L^n \to L$ mappings that are polynomial functions, i.e., functions which can be obtained from projections and constant functions using binary joins and meets. Moreover, we discuss the disjunctive normal form representations of these polynomial functions. [less ▲] Detailed reference viewed: 67 (12 UL)Quasi-Lovász extensions and their symmetric counterparts Couceiro, Miguel ; Marichal, Jean-Luc in Greco, S.; Bouchon-Meunier, B.; Coletti, G. (Eds.) et al Advances on Computational Intelligence, Part IV, 14th Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems, IPMU 2012, Catania, Italy, July 9-13, 2012, Proceedings, Part IV (2012) We introduce the concept of quasi-Lov\'asz extension as being a mapping $f\colon I^n\to\R$ defined over a nonempty real interval $I$ containing the origin, and which can be factorized as $f(x_1,\ldots,x_n ... [more ▼] We introduce the concept of quasi-Lov\'asz extension as being a mapping $f\colon I^n\to\R$ defined over a nonempty real interval $I$ containing the origin, and which can be factorized as $f(x_1,\ldots,x_n)=L(\varphi(x_1),\ldots,\varphi(x_n))$, where $L$ is the Lov\'asz extension of a pseudo-Boolean function $\psi\colon\{0,1\}^n\to\R$ (i.e., the function $L\colon\R^n\to\R$ whose restriction to each simplex of the standard triangulation of $[0,1]^n$ is the unique affine function which agrees with $\psi$ at the vertices of this simplex) and $\varphi\colon I\to\R$ is a nondecreasing function vanishing at the origin. These functions appear naturally within the scope of decision making under uncertainty since they subsume overall preference functionals associated with discrete Choquet integrals whose variables are transformed by a given utility function. To axiomatize the class of quasi-Lov\'asz extensions, we propose generalizations of properties used to characterize the Lov\'asz extensions, including a comonotonic version of modularity and a natural relaxation of homogeneity. A variant of the latter property enables us to axiomatize also the class of symmetric quasi-Lov\'asz extensions, which are compositions of symmetric Lov\'asz extensions with $1$-place nondecreasing odd functions. [less ▲] Detailed reference viewed: 82 (0 UL)Axiomatizations of quasi-Lovász extensions of pseudo-Boolean functions Couceiro, Miguel ; Marichal, Jean-Luc in Aequationes Mathematicae (2011), 82(3), 213-231 We introduce the concept of quasi-Lov\'asz extension as being a mapping $f\colon I^n\to\R$ defined on a nonempty real interval $I$ containing the origin and which can be factorized as $f(x_1,\ldots,x_n)=L ... [more ▼] We introduce the concept of quasi-Lov\'asz extension as being a mapping $f\colon I^n\to\R$ defined on a nonempty real interval $I$ containing the origin and which can be factorized as $f(x_1,\ldots,x_n)=L(\varphi(x_1),\ldots,\varphi(x_n))$, where $L$ is the Lov\'asz extension of a pseudo-Boolean function $\psi\colon\{0,1\}^n\to\R$ (i.e., the function $L\colon\R^n\to\R$ whose restriction to each simplex of the standard triangulation of $[0,1]^n$ is the unique affine function which agrees with $\psi$ at the vertices of this simplex) and $\varphi\colon I\to\R$ is a nondecreasing function vanishing at the origin. These functions appear naturally within the scope of decision making under uncertainty since they subsume overall preference functionals associated with discrete Choquet integrals whose variables are transformed by a given utility function. To axiomatize the class of quasi-Lov\'asz extensions, we propose generalizations of properties used to characterize the Lov\'asz extensions, including a comonotonic version of modularity and a natural relaxation of homogeneity. A variant of the latter property enables us to axiomatize also the class of symmetric quasi-Lov\'asz extensions, which are compositions of symmetric Lov\'asz extensions with $1$-place nondecreasing odd functions. [less ▲] Detailed reference viewed: 87 (2 UL)Influence and interaction indexes in cooperative games: a unified least squares approach Marichal, Jean-Luc ; Mathonet, Pierre Scientific Conference (2011, November 10) The classical Banzhaf power and interaction indexes used in cooperative game theory appear naturally as leading coefficients in the standard least squares approximation of the game under consideration by ... [more ▼] The classical Banzhaf power and interaction indexes used in cooperative game theory appear naturally as leading coefficients in the standard least squares approximation of the game under consideration by a set function of a specified degree. We observe that this still holds true if we consider approximations by set functions depending on specified variables. We show that the Banzhaf influence index can also be obtained from this new approximation problem. Considering certain weighted versions of this approximation, we also introduce a class of weighted Banzhaf influence indexes and analyze their most important properties. [less ▲] Detailed reference viewed: 32 (3 UL)On signature-based expressions of system reliability Marichal, Jean-Luc ; Mathonet, Pierre ; Waldhauser, Tamás in Journal of Multivariate Analysis (2011), 102(10), 1410-1416 The concept of signature was introduced by Samaniego for systems whose components have i.i.d. lifetimes. This concept proved to be useful in the analysis of theoretical behaviors of systems. In particular ... [more ▼] The concept of signature was introduced by Samaniego for systems whose components have i.i.d. lifetimes. This concept proved to be useful in the analysis of theoretical behaviors of systems. In particular, it provides an interesting signature-based representation of the system reliability in terms of reliabilities of k-out-of-n systems. In the non-i.i.d. case, we show that, at any time, this representation still holds true for every coherent system if and only if the component states are exchangeable. We also discuss conditions for obtaining an alternative representation of the system reliability in which the signature is replaced by its non-i.i.d. extension. Finally, we discuss conditions for the system reliability to have both representations. [less ▲] Detailed reference viewed: 100 (13 UL)Axiomatizations of Lovász extensions of pseudo-Boolean functions Couceiro, Miguel ; Marichal, Jean-Luc in Fuzzy Sets & Systems (2011), 181(1), 28-38 Three important properties in aggregation theory are investigated, namely horizontal min-additivity, horizontal max-additivity, and comonotonic additivity, which are defined by certain relaxations of the ... [more ▼] Three important properties in aggregation theory are investigated, namely horizontal min-additivity, horizontal max-additivity, and comonotonic additivity, which are defined by certain relaxations of the Cauchy functional equation in several variables. We show that these properties are equivalent and we completely describe the functions characterized by them. By adding some regularity conditions, these functions coincide with the Lovász extensions vanishing at the origin, which subsume the discrete Choquet integrals. We also propose a simultaneous generalization of horizontal min-additivity and horizontal max-additivity, called horizontal median-additivity, and we describe the corresponding function class. Additional conditions then reduce this class to that of symmetric Lovász extensions, which includes the discrete symmetric Choquet integrals. [less ▲] Detailed reference viewed: 94 (2 UL)A description of n-ary semigroups polynomial-derived from integral domains Marichal, Jean-Luc ; Mathonet, Pierre in Semigroup Forum (2011), 83(2), 241-249 We provide a complete classification of the n-ary semigroup structures defined by polynomial functions over infinite commutative integral domains with identity, thus generalizing Glazek and Gleichgewicht ... [more ▼] We provide a complete classification of the n-ary semigroup structures defined by polynomial functions over infinite commutative integral domains with identity, thus generalizing Glazek and Gleichgewicht's classification of the corresponding ternary semigroups. [less ▲] Detailed reference viewed: 108 (14 UL)Extensions of system signature and Barlow-Proschan importance index to dependent lifetimes Marichal, Jean-Luc ; Mathonet, Pierre Presentation (2011, September 07) Detailed reference viewed: 29 (2 UL)Signatures, decompositions of reliability, and approximation problems Marichal, Jean-Luc ; Mathonet, Pierre ; Waldhauser, Tamás Presentation (2011, September 07) Detailed reference viewed: 34 (0 UL)Measuring the interactions among variables of functions over the unit hypercube Marichal, Jean-Luc ; Mathonet, Pierre in Journal of Mathematical Analysis & Applications (2011), 380(1), 105-116 By considering a least squares approximation of a given square integrable function $f\colon[0,1]^n\to\R$ by a multilinear polynomial of a specified degree, we define an index which measures the overall ... [more ▼] By considering a least squares approximation of a given square integrable function $f\colon[0,1]^n\to\R$ by a multilinear polynomial of a specified degree, we define an index which measures the overall interaction among variables of $f$. This definition extends the concept of Banzhaf interaction index introduced in cooperative game theory. Our approach is partly inspired from multilinear regression analysis, where interactions among the independent variables are taken into consideration. We show that this interaction index has appealing properties which naturally generalize the properties of the Banzhaf interaction index. In particular, we interpret this index as an expected value of the difference quotients of $f$ or, under certain natural conditions on $f$, as an expected value of the derivatives of $f$. These interpretations show a strong analogy between the introduced interaction index and the overall importance index defined by Grabisch and Labreuche [7]. Finally, we discuss a few applications of the interaction index. [less ▲] Detailed reference viewed: 83 (3 UL)Agents in the shadow (cooperative games with non-cooperating players) Waldhauser, Tamás ; Couceiro, Miguel ; Marichal, Jean-Luc Scientific Conference (2011, July 19) The aim of this talk is to report on recent investigations about lattice derivatives of Boolean and pseudo-Boolean functions and their interpretations in game theory. The partial lattice derivatives of a ... [more ▼] The aim of this talk is to report on recent investigations about lattice derivatives of Boolean and pseudo-Boolean functions and their interpretations in game theory. The partial lattice derivatives of a (pseudo-) Boolean function are analogues of the classical partial derivatives, with the difference operation replaced by the minimum or the maximum operation. We focus on commutation properties of these lattice differential operators and relate them to local monotonicity properties. The least and greatest functions that can be obtained from a given function f, by forming lattice derivatives with respect to all variables, are called the lower and the upper shadows of f, respectively. It turns out that the lower and upper shadows of f coincide with the alpha- and beta-effectivity functions of the cooperative game corresponding to f. Thus a function f has a unique shadow if and only if the two effectivity functions coincide, which is equivalent to the fact that certain two-player zero-sum games associated with (the cooperative game corresponding to) f are strictly determined. We formulate a conjecture about Boolean functions (i.e., simple games) with a unique shadow, and present proofs in some special cases as well as results of computer experiments that support our conjecture. [less ▲] Detailed reference viewed: 108 (0 UL)An algorithm for producing median formulas for Boolean functions Couceiro, Miguel ; Lehtonen, Erkko ; Marichal, Jean-Luc et al in Proc. of the Reed Muller 2011 Workshop (2011, July) We review various normal form representations of Boolean functions and outline a comparative study between them, which shows that the median normal form system provides representations that are more ... [more ▼] We review various normal form representations of Boolean functions and outline a comparative study between them, which shows that the median normal form system provides representations that are more efficient than the classical DNF, CNF and Reed–Muller (polynomial) normal form representations. We present an algorithm for producing median normal form representations of Boolean functions. [less ▲] Detailed reference viewed: 147 (3 UL)Weighted Banzhaf power and interaction indexes through weighted approximations of games Marichal, Jean-Luc ; Mathonet, Pierre in European Journal of Operational Research (2011), 211(2), 352-358 The Banzhaf power index was introduced in cooperative game theory to measure the real power of players in a game. The Banzhaf interaction index was then proposed to measure the interaction degree inside ... [more ▼] The Banzhaf power index was introduced in cooperative game theory to measure the real power of players in a game. The Banzhaf interaction index was then proposed to measure the interaction degree inside coalitions of players. It was shown that the power and interaction indexes can be obtained as solutions of a standard least squares approximation problem for pseudo-Boolean functions. Considering certain weighted versions of this approximation problem, we define a class of weighted interaction indexes that generalize the Banzhaf interaction index. We show that these indexes define a subclass of the family of probabilistic interaction indexes and study their most important properties. Finally, we give an interpretation of the Banzhaf and Shapley interaction indexes as centers of mass of this subclass of interaction indexes. [less ▲] Detailed reference viewed: 84 (3 UL)Classification of associative multivariate polynomial functions Marichal, Jean-Luc ; Mathonet, Pierre Scientific Conference (2011, June) Detailed reference viewed: 42 (3 UL)Extensions of system signatures to dependent lifetimes: Explicit expressions and interpretations Marichal, Jean-Luc ; Mathonet, Pierre in Journal of Multivariate Analysis (2011), 102(5), 931-936 The concept of system signature was introduced by Samaniego for systems whose components have i.i.d. lifetimes. We consider its extension to the continuous dependent case and give an explicit expression ... [more ▼] The concept of system signature was introduced by Samaniego for systems whose components have i.i.d. lifetimes. We consider its extension to the continuous dependent case and give an explicit expression for this extension as a difference of weighted means of the structure function values. We then derive a formula for the computation of the coefficients of these weighted means in the special case of independent continuous lifetimes. Finally, we interpret this extended concept of signature through a natural least squares approximation problem. [less ▲] Detailed reference viewed: 71 (2 UL) |
||