Skip to Main content Skip to Navigation
Conference papers

Robust $k$-DNF Learning via Inductive Belief Merging

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
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

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 : Friday, October 4, 2019 - 1:07:26 PM

File

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

Identifiers

Collections

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⟩

Share

Metrics

Record views

123

Files downloads

61