¿Qué estaba pasando antes de aprender PAC?

Estoy investigando el aprendizaje PAC (teoría del aprendizaje computacional) como un principiante sin conocimientos previos de aprendizaje automático / IA. Estoy investigando el modelo principalmente desde un punto de vista histórico.

Para esto, lo más importante son, por supuesto, los resultados basados ​​en el modelo. Hay suficientes documentos por ahí que documentan estos resultados. Pero también quiero escribir algo sobre lo que estaba sucediendo antes del aprendizaje de PAC, como esbozar el contexto histórico hasta donde Valiant llegó con la noción del modelo PAC.

No hay documentos / encuestas que he encontrado hasta ahora documentan esto, y como alguien sin un conocimiento real del aprendizaje automático, es difícil descubrirlo. Por lo tanto, hago esta pregunta suave aquí, porque creo que hay suficientes expertos que pueden ayudarme con esto. Las referencias son muy apreciadas.

Cuando pueda investigar y estudiar lo que estaba sucediendo antes de PAC, podría apreciar mejor por qué el mundo académico está tan entusiasmado con el modelo PAC, ¡que también es algo interesante de documentar en mi trabajo histórico!

Las referencias son muy apreciadas.

Se espera que un autor aborde la cuestión del contexto y la relevancia de sus resultados al comienzo de su publicación. Acabo de leer la introducción de "L. Valiant. Una teoría de lo que se puede aprender. Comunicaciones de la ACM, 27, 1984." de nuevo, y descubrí que Valiant efectivamente cubrió su pregunta.

El documento original de Valiant está disponible gratuitamente y no es demasiado difícil de leer. (Excepto la sección 7, que solo prueba que el autor también puede abordar problemas matemáticos desafiantes, pero no contribuye mucho al contenido real del artículo). Leer al menos su introducción será más gratificante que leer mi respuesta demasiado larga a esto pregunta, así que sugiero probarlo realmente.

El resto de esta respuesta trata de citar algunos pasajes de la introducción que deberían indicar si leer esta introducción podría responder la pregunta sobre el contexto histórico. Sin embargo, tenga en cuenta que un autor tiene la prerrogativa natural de ser parcial con respecto a tales preguntas.

... tal sistema sería, al menos, un muy buen comienzo. Primero, cuando uno examina los ejemplos más famosos de sistemas que incorporan conocimiento preprogramado, a saber, sistemas expertos como DENDRAL y MYCIN , esencialmente no se usa ninguna notación lógica más allá del cálculo proposicional.

Esta es información interesante para el contexto, porque el cálculo proposicional es significativamente más débil que el cálculo predicativo o los diversos sistemas de teoría de tipos que a veces se usan en la actualidad. (Aunque es bastante extraño, Prolog (1972) y ML (1973) fueron, entre otros, pensados ​​como metalenguajes para "tales" sistemas expertos, y parecen ir más allá de la simple lógica proposicional hasta donde puedo ver. Además, el modelo relacional ( 1969) para la gestión de bases de datos se afirma que se basa en la lógica de predicados).

Quizás el principal descubrimiento técnico contenido en el documento es que con esta noción probabilística de aprendizaje, el aprendizaje altamente convergente es posible para clases enteras de funciones booleanas. Esto parece distinguir este enfoque de otros más tradicionales en los que el aprendizaje se ve como un proceso de "inducir" alguna regla general de la información que es insuficiente para hacer una deducción confiable.

Estoy totalmente de acuerdo aquí. Es importante poder explicar cómo su solución puede resolver un problema determinado, y en qué sentido es una solución. De lo contrario, terminará con los teoremas de "almuerzo libre" que no le permiten distinguir una implementación con errores de una heurística dudosa de una implementación correcta de una heurística adecuada.

En resumen, este artículo intenta explorar los límites de lo que se puede aprender según lo permitido por la complejidad algorítmica. Los resultados se distinguen del diverso cuerpo de trabajo previo sobre el aprendizaje porque intentan conciliar las tres propiedades ((1) - (3)) mencionadas anteriormente. El rigor más cercano a nuestro enfoque es la literatura de inferencia inductiva [...]. Existe una gran cantidad de trabajo sobre reconocimiento y clasificación de patrones, utilizando herramientas estadísticas y otras [...]. El aprendizaje, en varios sentidos menos formales, se ha estudiado ampliamente como una rama de la inteligencia artificial.

Las propiedades ((1) - (3)) fueron que (1) "las máquinas pueden aprender clases enteramente caracterizables de conceptos" que son (2) "apropiados y no triviales para el conocimiento de propósito general" y (3) "la computación el proceso requiere solo un número factible (es decir, polinomial) de pasos ".

La identificación del idioma en el límite es el primer intento conocido de capturar la noción de capacidad de aprendizaje. Fue introducido por Gold en 1967 y es un modelo de inferencia inductiva que se refiere al aprendizaje de clases de idiomas.