A teoria da aprendizagem computacional busca construir e extrapolar modelos baseados em máquinas de estado que são capazes de "aprender" a desempenhar alguma tarefa em um dado ambiente sob dadas condições[6]. Entender esses aspectos de modo formal nos permite entender os limites e apresentar garantias quanto a capacidade de agentes aprendizes. Uma definição formal para o conceito de máquinas aprendizes é dado em Mitchell[7].
Definição: Um programa de computador é dito aprender da experiência em respeito a uma classe de tarefa e medida de performance , se sua performance nas tarefas em , medidas por , melhora com a experiência .
Podemos exemplificar esse conceito com um problema simples de classificação de vinhos, queremos que o agente aprendiz consiga classificar vinhos em bons e ruins, dado a descrição das propriedades químicas do vinho. A tarefa aqui então é nomeada classificação, pois queremos atribuir uma classe ao vinho. Para que o agente aprenda por indução, devemos então prover pares de exemplos de descrições químicas do vinho, junto a classes quanto a qualidade do mesmo, . Assumindo que nada mude quanto ao processo de produção dos vinhos e sua qualidade (hipótese da independência e normalidade), o agente pode usar dessa experiência para aprender a classificar novos vinhos, assim, diminuindo ao longo do tempo a sua imprecisão ao classificar novos vinhos. Para medir essa imprecisão a acurácia seria uma métrica aplicável. Logo, dizemos que o agente "aprende" se a acurácia ao classificar novos vinhos fica cada vez mais alta ao longo do tempo.
Definindo o que é o aprendizado agora devemos entender quando ele é possível de ser realizado por um programa de computador e quando o mesmo é tratável, isto é, se o custo de memória e o tempo de processamento desse programa são viáveis para o contexto que ele será aplicado, i.e, são descritos por uma função polinomial da entrada. Embora o exemplo ilustrado seja bem conhecido, o método empírico indutivo, e tenhamos vários programas de computador conhecido para resolver em tempo polinomial, como a regressão logística, ainda há uma ampla gama de tarefas as quais não havia formalização sobre sua solução.
Suponhamos agora que queremos classificar sentenças 3-SAT em satisfazíveis ou não satisfazíveis, isto é, passamos um conjunto de experiências ao aprendiz com formulas 3-SAT e para uma nova formula 3-SAT queremos que ele classifique se ela é ou não satisfazível. Sabemos que o problema 3-SAT é -completo[8], logo se existir tal agente ou ele não aprende polinomialmente e é indesejável como agente aprendiz, ou ele aprende polinomialmente e provaria a equivalência entre as classes e [8]. Entretanto, acredita-se que tal agente não exista[6].
Modelos Teóricos de Aprendizado Universal
Alguns modelos foram propostos como forma de criar máquinas aprendizes que tenham resultados ótimos para os contextos que foram desenhados. Embora a descrição de tais máquinas possa ser abstrata ou envolver computações não-decidíveis, a análise e aproximação desses agentes nos permite construir algoritmos quase-ótimos viáveis.
Identificação de Linguagem no Limite
Um dos primeiros modelos a introduzir o conceito de "aprendibilidade" (do inglês, learnability) para o contexto teórico-computacional foi o modelo de identificação de linguagem no limite. Este modelo consiste em um professor apresentar uma sequência de strings derivadas da gramática , a um aprendiz , de forma que pare com uma representação da gramática que descreve em sua fita. Desta forma, é dito que aprendeu , se após apresentado a um número finito de strings em , consegue parar com precisamente a representação de em sua fita[5].
Embora a definição acima nos permita formalizar o conceito de "aprender" para máquinas de estado de forma ampla, ela não nos dá perspectivas sobre a aplicabilidade do agente, pois, nem sempre é possível obter gramáticas precisas para representar fenômenos que sofrem de ruído e embora o aprendiz seja decidível, podemos estar lidando com problemas intratáveis, i.e., o aprendiz necessitar de uma quantidade imensas de exemplos para chegar em . Valiant (1984) propõem então um modelo que suaviza a ideia de aprender[9], em que a gramática não precisa ser precisamente a original, pois se tolera um erro máximo entre as sequências geradas pelas duas gramáticas e também define garantias quanto a convergência do aprendizado, isto é, não excede a classe polinomial.
Modelos Práticos para Aprendizado de Gramáticas Formais
Muitos modelos foram propostos para a identificação the padrões algorítmicos em gramáticas, como RNNs, LTSMs, Transformers e demais redes com recorrências, entretanto diversos experimentos apresentaram um limite a quais classes gramáticas esses modelos são capazes de reconhecer. Máquinas Recorrentes de Memória Estendida foram propostas como uma abordagem para que tais redes recorrentes fossem capazes de reconhecer gramáticas de maior hierarquia do que apenas as gramáticas regulares.
Classes de linguagem formal e sua correspondência com arquiteturas de redes neurais.
Para isso, adicionalmente a estrutura recorrente, um dispositivo de memória é incorporado a recorrência para que ele simule operações de acesso, como incrementar (contador), empilhar (pilha), deslizar (fita), e consequentemente aprenda a reconhecer linguagens de sua respectiva hierarquia de forma mais eficiente.
