Online Rule Learning via Weighted Model Counting

Frédéric Koriche 1
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Online multiplicative weight-update learning algorithms, such asWinnow, have proven to behave remarkably for learning simple disjunctions with few relevant attributes. The aim of this paper is to extend theWinnow algorithm to more expressive concepts characterized by DNF formulas with few relevant rules. For such problems, the convergence of Winnow is still fast, since the number of mistakes increases only linearly with the number of attributes. Yet, the learner is confronted with an important computational barrier: during any prediction, it must evaluate the weighted sum of an exponential number of rules. To circumvent this issue, we convert the prediction problem into a Weighted Model Counting problem. The resulting algorithm, SharpNow, is an exact simulation ofWinnow equipped with backtracking, caching, and decomposition techniques. Experiments on static and drifting problems demonstrate the performance of the algorithm in terms of accuracy and speed.
Type de document :
Communication dans un congrès
ECAI'08: Eighteenth European Conference on Artificial Intelligence, Patras, Greece, pp.5-9, 2008, 〈http://www.ece.upatras.gr/ecai2008/〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00315916
Contributeur : Frédéric Koriche <>
Soumis le : dimanche 15 mars 2009 - 02:15:06
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 12:18:30

Fichier

ECAI08-Article-FV.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00315916, version 2

Collections

Citation

Frédéric Koriche. Online Rule Learning via Weighted Model Counting. ECAI'08: Eighteenth European Conference on Artificial Intelligence, Patras, Greece, pp.5-9, 2008, 〈http://www.ece.upatras.gr/ecai2008/〉. 〈lirmm-00315916v2〉

Partager

Métriques

Consultations de la notice

125

Téléchargements de fichiers

210