References of "Ibaraki, Toshihide"
     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)
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 detailHitting or avoiding balls in Euclidean space
Crama, Yves ULg; Ibaraki, Toshihide

in Annals of Operations Research (1997), 69

We investigate the algorithmic complexity of several geometric problems of the following type: given a "feasible" box and a collection of balls in Euclidean space, find a feasible point which is covered ... [more ▼]

We investigate the algorithmic complexity of several geometric problems of the following type: given a "feasible" box and a collection of balls in Euclidean space, find a feasible point which is covered by as few or, respectively, by as many balls as possible. We establish that all these problems are NP-hard in their most general version. We derive tight lower and upper bounds on the complexity of their one-dimensional versions. Finally, we show that all these problems can be solved in polynomial time when the dimension of the space is fixed. [less ▲]

Detailed reference viewed: 16 (1 ULg)
Full Text
Peer Reviewed
See detailCause-effect relationships and partially defined Boolean functions
Crama, Yves ULg; Ibaraki, Toshihide

in Annals of Operations Research (1988), 16

This paper investigates the use of Boolean techniques in a systematic study of cause-effect relationships. The model uses partially defined Boolean functions. Procedures are provided to extrapolate from ... [more ▼]

This paper investigates the use of Boolean techniques in a systematic study of cause-effect relationships. The model uses partially defined Boolean functions. Procedures are provided to extrapolate from limited observations, concise and meaningful theories to explain the effect under study, and to prevent (or provoke) its occurrence [less ▲]

Detailed reference viewed: 22 (2 ULg)