Learning from Positive and Unlabeled Examples

Abstract : In many machine learning settings, labeled examples are difficult to collect while unlabeled data are abundant. Also, for some binary classification problems, positive examples, that is examples of the target class, are available. Can these additional data be used to improve accuracy of supervised learning algorithms? We investigate in this paper the design of learning algorithms from positive and unlabeled data only. Many machine learning and data mining algorithms, such as decision tree induction algorithms and naive Bayes algorithms, only use examples in order to evaluate statistical queries (SQ-like algorithms). Kearns designed the Statistical Query learning model in order to describe these algorithms. Here, we design an algorithm scheme which transforms any SQ-like algorithm into an algorithm based on positive statistical queries (estimates for probabilities over the set of positive instances) and instance statistical queries (estimates for probabilities over the instance space). We prove that any class learnable in the Statistical Query learning model is learnable from positive statistical queries and instance statistical queries only if a lower bound on the weight of any target concept $f$ can be estimated in polynomial time. Then, we design a decision tree induction algorithm POSC4.5, based on C4.5, that uses only positive and unlabeled examples and we give experimental results for this algorithm. The case of imbalanced classes in the sense that one of the two classes (say the positive class) is heavily underrepresented compared to the other class remains open. This problem is challenging because it is encountered in many real-world applications.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2005, 348 (1), pp.70-83
Liste complète des métadonnées

https://hal.inria.fr/inria-00536692
Contributeur : Rémi Gilleron <>
Soumis le : mardi 16 novembre 2010 - 17:31:42
Dernière modification le : jeudi 18 janvier 2018 - 02:01:00
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:06:56

Fichiers

onlypos02.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536692, version 1

Collections

Citation

François Denis, Rémi Gilleron, Fabien Letouzey. Learning from Positive and Unlabeled Examples. Theoretical Computer Science, Elsevier, 2005, 348 (1), pp.70-83. 〈inria-00536692〉

Partager

Métriques

Consultations de la notice

326

Téléchargements de fichiers

307