Robust $k$-DNF Learning via Inductive Belief Merging - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2003

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.
Fichier principal
Vignette du fichier
Robust_k-DNF_Learning_via_Inductive_Belief_Merging.pdf (230.34 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00269706 , version 1 (04-10-2019)

Identifiers

Cite

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⟩
91 View
56 Download

Altmetric

Share

More