Enseignement optimal sans collusion

Résumé

Les modèles formels d'apprentissage des enseignants doivent respecter certains critères pour éviter la collusion. La notion la plus communément admise d'absence de collusion a été proposée par Goldman et Mathias (1996), et divers modèles d'enseignement obéissant à leur critère ont été étudiés. Pour chaque modèle M et chaque classe de concepts C, un paramètre M-TD(C) se réfère à la dimension d'enseignement de la classe de concepts C dans le modèle M, défini comme étant le nombre d'exemples nécessaires pour enseigner un concept, dans le pire des cas sur tous les concepts de C. Cet article présente un nouveau modèle d'enseignement, appelé enseignement sans collision, ainsi que le paramètre correspondant NCTD(C). L'enseignement sans conflit est prouvé optimal au sens fort, c'est-à-dire que, pour toute classe de concepts C et tout modèle M obéissant au critère d'absence de collusion de Goldman et Mathias, on obtient NCTD(C) ≤ M-TD(C). Nous étudions également une notion correspondante NCTD+ pour le cas de l'apprentissage à partir de données positives seulement, établissons des bornes utiles sur NCTD et NCTD+, et discutons des relations de ces paramètres avec la dimension VC et la compression d'échantillon. Outre la formulation d'un modèle optimal d'apprentissage sans collusion, nos principaux résultats portent sur la complexité informatique de la décision de savoir si NCTD+(C) = k (ou NCTD(C) = k) pour des C et k donnés. Nous montrons que certains de ces problèmes de décision sont équivalents à la question de l'existence de certains appariements contraints dans les graphes bipartis. Nos résultats de dureté NP pour ces derniers sont d'un intérêt indépendant dans l'étude des appariements contraints de graphes.