Leslie Valiant propose ce cadre théorique de « l’apprenabilité » dans son article « A theory of the learnable ».

Cette reformulation du cadre d’apprentissage proposé par Vapnik permet notamment d’évaluer la difficulté d’un problème dans le contexte l’apprentissage supervisé. Il a permis d’introduire la notion d’apprenabilité d’un concept à partir d’instances du concept, autrement dit d’une série d’observations. L’approche PAC (Probablement Approximativement Correct) consiste à introduire un aléa sur l’observation des instances et à formuler des résultats en termes de majoration du nombre d’instances nécessaires pour approcher le concept avec une certaine précision fixée et une probabilité également fixée. Ce cadre formel a donné naissance à ce que l’on appelle la computational learning theory.