O que estava acontecendo antes do aprendizado do PAC

Estou investigando a aprendizagem do PAC (teoria da aprendizagem computacional) como iniciante, sem nenhum conhecimento prévio de aprendizado de máquina / IA. Estou investigando o modelo principalmente de um ponto de vista histórico.

Para isso, as coisas mais importantes são, obviamente, os resultados baseados no modelo. Existem documentos suficientes por aí que documentam esses resultados. Mas também quero escrever algo sobre o que estava acontecendo antes do aprendizado do PAC, para esboçar o contexto histórico até onde Valiant veio com a noção do modelo do PAC.

Nenhum artigo / pesquisa que encontrei até agora documenta isso e, como alguém sem nenhum conhecimento real de aprendizado de máquina, é difícil descobrir isso. Estou, portanto, fazendo esta pergunta suave aqui, porque acredito que há especialistas suficientes que podem me ajudar com isso. As referências são muito apreciadas.

Quando eu posso pesquisar e estudar o que estava acontecendo antes do PAC, posso entender melhor por que o mundo acadêmico está tão entusiasmado com o modelo do PAC, que também é algo interessante para documentar em meu trabalho histórico!

As referências são muito apreciadas.

Um autor deve abordar a questão do contexto e da relevância de seus resultados no início de sua publicação. Acabei de ler a introdução de "L. Valiant. Uma teoria do que pode ser aprendido. Comunicações da ACM, 27, 1984". novamente, e descobriu que Valiant realmente cobriu bem sua pergunta.

O artigo original da Valiant está disponível gratuitamente e não é muito difícil de ler. (Exceto a seção 7, que prova apenas que o autor também pode enfrentar problemas matemáticos desafiadores, mas não contribui muito para o conteúdo real do artigo.) Ler pelo menos sua introdução será mais gratificante do que ler minha resposta excessivamente longa a isso pergunta, então eu sugiro realmente tentar.

O restante desta resposta tenta citar algumas passagens da introdução que devem indicar se a leitura dessa introdução pode responder à pergunta sobre o contexto histórico. Observe, no entanto, que um autor tem a prerrogativa natural de ser tendenciosa em relação a essas questões.

... esse sistema seria, pelo menos, um começo muito bom. Primeiro, quando examinamos os exemplos mais famosos de sistemas que incorporam conhecimento pré-programado, ou seja, sistemas especialistas como DENDRAL e MYCIN , essencialmente nenhuma notação lógica além do cálculo proposicional é usada.

Esta é uma informação interessante para o contexto, porque o cálculo proposicional é significativamente mais fraco que o cálculo preditivo ou os vários sistemas da teoria dos tipos, às vezes usados ​​hoje. (Por mais estranho que pareça, Prolog (1972) e ML (1973) eram, entre outros, pretendidos como meta-linguagens para "tais" sistemas especialistas, e parecem ir além da lógica proposicional simples, tanto quanto posso ver. Além disso, o modelo relacional ( 1969) para o gerenciamento de banco de dados é reivindicada com base na lógica de predicado.)

Talvez a principal descoberta técnica contida no artigo seja que, com essa noção probabilística de aprendizado, é possível obter um aprendizado altamente convergente para classes inteiras de funções booleanas. Isso parece distinguir essa abordagem das mais tradicionais, onde o aprendizado é visto como um processo de "induzir" alguma regra geral de informações insuficientes para que uma dedução confiável seja feita.

Eu concordo plenamente aqui. É importante ser capaz de explicar como sua solução é capaz de resolver um determinado problema e, em que sentido, é uma solução. Caso contrário, você acabará com os teoremas do "almoço grátis", que não permitem distinguir uma implementação incorreta de uma heurística duvidosa da implementação correta de uma heurística apropriada.

Em resumo, este artigo tenta explorar os limites do que é aprendível, conforme permitido pela complexidade algorítmica. Os resultados são distinguíveis do corpo diversificado de trabalhos anteriores sobre aprendizado, porque eles tentam conciliar as três propriedades ((1) - (3)) mencionadas anteriormente. O mais rigoroso de nossa abordagem é a literatura de inferência indutiva [...]. Há um grande corpo de trabalho sobre reconhecimento e classificação de padrões, usando ferramentas estatísticas e outras [...]. O aprendizado, em vários sentidos menos formais, tem sido amplamente estudado como um ramo da inteligência artificial.

As propriedades ((1) - (3)) eram que (1) "as máquinas podem aprender classes de conceitos caracterizáveis ​​inteiras" que são (2) "apropriadas e não triviais para o conhecimento de uso geral" e (3) "a computação processo requer apenas um número possível de etapas (isto é, polinomial) ".

A identificação do idioma no limite é a primeira tentativa conhecida de capturar a noção de aprendibilidade. Foi introduzido por Gold em 1967 e é um modelo de inferência indutiva que diz respeito à aprendizagem de classes de idiomas.