Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Logical Analysis of Data: Classification with justification ; Crama, Yves ; et al in Annals of Operations Research (2011), 188 Learning from examples is a frequently arising challenge, with a large number of algorithms proposed in the classification, data mining and machine learning literature. The evaluation of the quality of ... [more ▼] Learning from examples is a frequently arising challenge, with a large number of algorithms proposed in the classification, data mining and machine learning literature. The evaluation of the quality of such algorithms is frequently carried out ex post, on an experimental basis: their performance is measured either by cross validation on benchmark data sets, or by clinical trials. Few of these approaches evaluate the learning process ex ante, on its own merits. In this paper, we dis- cuss a property of rule-based classifiers which we call "justifiability", and which focuses on the type of information extracted from the given training set in order to classify new observations. We investigate some interesting mathematical properties of justifiable classifiers. In partic- ular, we establish the existence of justifiable classifiers, and we show that several well-known learning approaches, such as decision trees or nearest neighbor based methods, automatically provide justifiable clas- sifiers. We also identify maximal subsets of observations which must be classified in the same way by every justifiable classifier. Finally, we illustrate by a numerical example that using classifiers based on "most justifiable" rules does not seem to lead to over fitting, even though it involves an element of optimization. [less ▲] Detailed reference viewed: 60 (5 ULg)Boolean Functions: Theory, Algorithms, and Applications Crama, Yves ; Book published by Cambridge University Press (2011) This monograph provides the first comprehensive presentation of the theoretical, algorithmic and applied aspects of Boolean functions, i.e., {0,1}-valued functions of a finite number of {0,1}-valued ... [more ▼] This monograph provides the first comprehensive presentation of the theoretical, algorithmic and applied aspects of Boolean functions, i.e., {0,1}-valued functions of a finite number of {0,1}-valued variables. The book focuses on algebraic representations of Boolean functions, especially normal form representations. It presents the fundamental elements of the theory (Boolean equations and satisfiability problems, prime implicants and associated representations, dualization, etc.), an in-depth study of special classes of Boolean functions (quadratic, Horn, shellable, regular, threshold, read-once, etc.), and two fruitful generalizations of the concept of Boolean functions (partially defined and pseudo-Boolean functions). It features a rich bibliography of about one thousand items. Prominent among the disciplines in which Boolean methods play a significant role are propositional logic, combinatorics, graph and hypergraph theory, complexity theory, integer programming, combinatorial optimization, game theory, reliability theory, electrical and computer engineering, artificial intelligence, etc. The book contains applications of Boolean functions in all these areas. [less ▲] Detailed reference viewed: 664 (18 ULg)Boolean Models and Methods in Mathematics, Computer Science, and Engineering Crama, Yves ; Book published by Cambridge University Press (2010) This collection of papers proposes in-depth presentations of a variety of advanced topics related to Boolean functions and expressions. The chapters are written by some of the most prominent experts in ... [more ▼] This collection of papers proposes in-depth presentations of a variety of advanced topics related to Boolean functions and expressions. The chapters are written by some of the most prominent experts in their respective fields, and cover topics ranging from algebra and propositional logic to learning theory, cryptography, computational complexity, electrical engineering, and reliability theory. Beyond the diversity of the questions raised and investigated in different chapters, a remarkable feature of the collection is the common thread created by the fundamental language, concepts, models and tools provided by Boolean theory. Many readers will certainly be surprised to discover countless links between seemingly remote topics discussed in various chapters of the book. They will hopefully be able to draw on such connections to further their understanding of their own scientific discipline and to explore new avenues for research. [less ▲] Detailed reference viewed: 106 (17 ULg)Consensus algorithms for the generation of all maximal bicliques ; ; Crama, Yves et al in Discrete Applied Mathematics (2004), 145(1 Sp. Iss. SI), 11-21 We describe a new algorithm for generating all maximal bicliques (i.e. complete bipartite. not necessarily induced subgraphs) of a graph. The algorithm is inspired by, and is quite similar to. the ... [more ▼] We describe a new algorithm for generating all maximal bicliques (i.e. complete bipartite. not necessarily induced subgraphs) of a graph. The algorithm is inspired by, and is quite similar to. the consensus method used in propositional logic. We show that some variants of the algorithm are totally polynomial, and even incrementally polynomial. The total complexity of the most efficient variant of the algorithms presented here is polynomial in the input size. and only linear in the output size. Computational experiments demonstrate its high efficiency on randomly generated graphs with up to 2000 vertices and 20,000 edges. (C) 2003 Elsevier B.V. All rights reserved. [less ▲] Detailed reference viewed: 85 (6 ULg) |
||