Teoria da aprendizagem computacional

A teoria da aprendizagem computacional é um sub-campo da inteligência artificial e teoria da computação que busca construir modelos formais de projeto e analise de agentes de aprendizado baseados em máquinas de estado. Alguns modelos famosos propostos são o Provavelmente Aproximadamente Correto^[1], o AIXI^[2], Máquinas de Gödel^[3], Indução Universal de Solomonoff^[4] e Identificação de Linguagem no Limite^[5]. Diferente da teoria do aprendizado estatístico, que busca projetar e entender ferramentas que extraem padrões estatísticos nos dados pelo método indutivo, a teoria da aprendizagem computacional tem maior foco em entender os limites computacionais de qualquer agente inferencial, como representações simbólico numéricas, complexidade computacional e decidibilidade. Trabalhos mais recentes no campo tem explorado o projeto de agentes que atuam no processo de aprendizado, como meta-aprendizes ou aprendizado por reforço.

Introdução

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 $E$ em respeito a uma classe de tarefa $T$ e medida de performance $P$ , se sua performance nas tarefas em $T$ , medidas por $P$ , melhora com a experiência $E$ .

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 $T$ 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, $\{{\text{bom}},{\text{ruim}}\}\in {\mathcal {K}}$ . 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 $E$ 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 $P$ 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 é $NP$ -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 $P$ e $NP$ ^[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 $P$ apresentar uma sequência de strings $s\in S$ derivadas da gramática $G$ , a um aprendiz $A$ , de forma que $A$ pare com uma representação da gramática ${\hat {G}}$ que descreve $s$ em sua fita. Desta forma, é dito que $A$ aprendeu $G$ , se após apresentado a um número finito de strings em $S$ , $A$ consegue parar com precisamente a representação de $G$ 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 $G$ . 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.

Ver também

Referências

↑ Kearns, Michael J. (1994). An introduction to computational learning theory. Umesh Virkumar Vazirani. Cambridge, Mass.: MIT Press. OCLC 47009798
↑ Hutter, Marcus (2005). Universal artificial intelligence : sequential decisions based on algorithmic probability. Berlin: Springer. OCLC 184898003
↑ Schmidhuber, Jürgen (2007). Goertzel, Ben; Pennachin, Cassio, eds. «Gödel Machines: Fully Self-referential Optimal Universal Self-improvers». Berlin, Heidelberg: Springer Berlin Heidelberg (em inglês): 199–226. ISBN 978-3-540-23733-4. doi:10.1007/978-3-540-68677-4_7. Consultado em 29 de julho de 2022
↑ Solomonoff, R. J. (1 de março de 1964). «A formal theory of inductive inference. Part I». Information and Control (em inglês) (1): 1–22. ISSN 0019-9958. doi:10.1016/S0019-9958(64)90223-2. Consultado em 29 de julho de 2022
↑ ^a ^b Gold, E Mark (maio de 1967). «Language identification in the limit». Information and Control (em inglês) (5): 447–474. doi:10.1016/S0019-9958(67)91165-5. Consultado em 29 de julho de 2022
↑ ^a ^b Mohri, Mehryar (2012). Foundations of machine learning. Afshin Rostamizadeh, Ameet Talwalkar. Cambridge, MA: MIT Press. OCLC 809846149
↑ Mitchell, Tom M. (1997). Machine Learning. New York: [s.n.] OCLC 36417892
↑ ^a ^b Sipser, Michael (2007). Introdução à teoria da computação. Ruy José Guerra Barretto de Queiroz, Newton José Vieira. São Paulo: Thomson Learning. OCLC 246908272
↑ Valiant, L. G. (5 de novembro de 1984). «A theory of the learnable». Communications of the ACM (em inglês) (11): 1134–1142. ISSN 0001-0782. doi:10.1145/1968.1972. Consultado em 2 de agosto de 2022

[1] Kearns, Michael J. (1994). An introduction to computational learning theory. Umesh Virkumar Vazirani. Cambridge, Mass.: MIT Press. OCLC 47009798

[2] Hutter, Marcus (2005). Universal artificial intelligence : sequential decisions based on algorithmic probability. Berlin: Springer. OCLC 184898003

[3] Schmidhuber, Jürgen (2007). Goertzel, Ben; Pennachin, Cassio, eds. «Gödel Machines: Fully Self-referential Optimal Universal Self-improvers». Berlin, Heidelberg: Springer Berlin Heidelberg (em inglês): 199–226. ISBN 978-3-540-23733-4. doi:10.1007/978-3-540-68677-4_7. Consultado em 29 de julho de 2022

[4] Solomonoff, R. J. (1 de março de 1964). «A formal theory of inductive inference. Part I». Information and Control (em inglês) (1): 1–22. ISSN 0019-9958. doi:10.1016/S0019-9958(64)90223-2. Consultado em 29 de julho de 2022

[:0-5] Gold, E Mark (maio de 1967). «Language identification in the limit». Information and Control (em inglês) (5): 447–474. doi:10.1016/S0019-9958(67)91165-5. Consultado em 29 de julho de 2022

[:1-6] Mohri, Mehryar (2012). Foundations of machine learning. Afshin Rostamizadeh, Ameet Talwalkar. Cambridge, MA: MIT Press. OCLC 809846149

[7] Mitchell, Tom M. (1997). Machine Learning. New York: [s.n.] OCLC 36417892

[:2-8] Sipser, Michael (2007). Introdução à teoria da computação. Ruy José Guerra Barretto de Queiroz, Newton José Vieira. São Paulo: Thomson Learning. OCLC 246908272

[9] Valiant, L. G. (5 de novembro de 1984). «A theory of the learnable». Communications of the ACM (em inglês) (11): 1134–1142. ISSN 0001-0782. doi:10.1145/1968.1972. Consultado em 2 de agosto de 2022

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]