# Robust $k$-DNF Learning via Inductive Belief Merging

1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A central issue in logical concept induction is the prospect of inconsistency. This problem may arise due to noise in the training data, or because the target concept does not fit the underlying concept class. In this paper, we introduce the paradigm of inductive belief merging which handles this issue within a uniform framework. The key idea is to base learning on a belief merging operator that selects the concepts which are as close as possible to the set of training examples. From a computational perspective, we apply this paradigm to robust k-DNF learning. To this end, we develop a greedy algorithm which approximates the optimal concepts to within a logarithmic factor. The time complexity of the algorithm is polynomial in the size of k. Moreover, the method bidirectional and returns one maximally specific concept and one maximally general concept. We present experimental results showing the effectiveness of our algorithm on both nominal and numerical datasets.
Document type :
Conference papers
Domain :

Cited literature [21 references]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269706
Contributor : Christine Carvalho de Matos <>
Submitted on : Friday, October 4, 2019 - 12:04:19 PM
Last modification on : Monday, January 11, 2021 - 5:24:09 PM

### File

Robust_k-DNF_Learning_via_Indu...
Files produced by the author(s)

### Citation

Frédéric Koriche, Joël Quinqueton. Robust $k$-DNF Learning via Inductive Belief Merging. ECML: European Conference on Machine Learning, Sep 2003, Dubrovnik, Croatia. pp.229-240, ⟨10.1007/978-3-540-39857-8_22⟩. ⟨lirmm-00269706⟩

Record views