Enseignement basé sur les préférences

Résumé

Nous introduisons un nouveau modèle d'enseignement appelé "enseignement basé sur les préférences" et un paramètre de complexité correspondant - la dimension d'enseignement basée sur les préférences (PBTD) - représentant le nombre le plus défavorable d'exemples nécessaires pour enseigner un concept dans une classe de concepts donnée. Bien que la PBTD coïncide avec la dimension d'enseignement récursif (RTD) bien connue sur les classes finies, elle est radicalement différente sur les classes infinies : la RTD devient déjà infinie pour les classes infinies triviales (telles que les demi-intervalles) alors que la PBTD s'évalue à des valeurs raisonnablement petites pour une large collection de classes infinies, y compris les classes constituées d'ensembles dits fermés par rapport à un opérateur de fermeture donné, y compris diverses classes liées aux ensembles linéaires sur N0 (dont la RTD a été étudiée assez récemment) et y compris la classe des demi-espaces euclidiens. En plus de présenter ces résultats concrets, nous fournissons au lecteur un cadre théorique (de type combinatoire) qui permet de dériver des bornes sur la RDTB.