La complexité de l'apprentissage exact des réseaux de préférences conditionnelles acycliques à partir d'exemples échangés

Résumé

L'apprentissage des préférences des utilisateurs, représentées par exemple par des réseaux de préférences conditionnelles (CP-nets), est devenu une question centrale dans la recherche en IA. Des études récentes examinent l'apprentissage des CP-nets à partir d'exemples choisis aléatoirement ou à partir de requêtes d'appartenance et d'équivalence. Pour évaluer l'optimalité des algorithmes d'apprentissage et pour mieux comprendre la structure combinatoire des classes de CP-nets, il est utile de calculer certains paramètres de complexité de l'information de la théorie de l'apprentissage. Cet article se concentre sur le cas fréquemment étudié de l'apprentissage exact à partir d'exemples dits de permutation, qui expriment des préférences entre des objets qui ne diffèrent que par un seul attribut. Il présente des limites ou des valeurs exactes de certains paramètres de complexité de l'information bien étudiés, à savoir la dimension VC, la dimension d'enseignement et la dimension d'enseignement récursif, pour des classes de CP-nets acycliques. Nous fournissons également des algorithmes qui apprennent exactement des CP-nets arborescents et acycliques généraux à partir de requêtes d'adhésion. En utilisant nos résultats sur les paramètres de complexité, nous prouvons que nos algorithmes, ainsi qu'un autre algorithme d'apprentissage par requête pour les CP-nets acycliques présenté dans la littérature, sont quasi-optimaux.