References of "Hammer, Peter L"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailLogical Analysis of Data: Classification with justification
Boros, Endre; Crama, Yves ULg; Hammer, Peter L. 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: 69 (5 ULg)
Full Text
See detailBoolean Functions: Theory, Algorithms, and Applications
Crama, Yves ULg; Hammer, Peter L.

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: 694 (18 ULg)
Full Text
See detailBoolean Models and Methods in Mathematics, Computer Science, and Engineering
Crama, Yves ULg; Hammer, Peter L.

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: 114 (17 ULg)
Full Text
Peer Reviewed
See detailConsensus algorithms for the generation of all maximal bicliques
Alexe, Gabriela; Alexe, Sorin; Crama, Yves ULg 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: 90 (6 ULg)
Full Text
Peer Reviewed
See detailPseudo-Boolean optimization
Crama, Yves ULg; Hammer, Peter L.

in Resende, M.G.C.; Pardalos, P.M. (Eds.) Handbook of Applied Optimization (2002)

This article briefly surveys some fundamental results regarding pseudo-Boolean functions.

Detailed reference viewed: 12 (1 ULg)
Peer Reviewed
See detailBoolean normal forms, shellability and reliability computations
Boros, Endre; Crama, Yves ULg; Ekin, Oya et al

in SIAM Journal on Discrete Mathematics (2000), 13

Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal ... [more ▼]

Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete. [less ▲]

Detailed reference viewed: 17 (1 ULg)
Full Text
Peer Reviewed
See detailVariable and term removal from Boolean formulae
Crama, Yves ULg; Ekin, Oya; Hammer, Peter L.

in Discrete Applied Mathematics (1997), 75

Given a Boolean formula in disjunctive normal form, the variable deletion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF ... [more ▼]

Given a Boolean formula in disjunctive normal form, the variable deletion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF satisfying some prescribed property. Similar problems can be defined with respect to the fixation of variables or the deletion of terms in a DNF. In this paper, we investigate the complexity of such problems for a broad class of DNF properties. [less ▲]

Detailed reference viewed: 19 (3 ULg)