Teoria da aprendizagem algorítmica
 |
A teoria da aprendizagem algorítmica é um arcabouço matemático para a análise de problemas e algoritmos na área de aprendizagem de máquina. Alguns termos sinônimos são teoria da aprendizagem formal e inferência indutiva algorítmica. A teoria da aprendizagem algorítmica é diferente da teoria da aprendizagem estatística no sentido de que a primeira não faz uso de pressupostos ou análises estatísticas. Ambas as teorias são voltadas para a aprendizagem de máquina e podem, portanto, serem vistas como ramos da teoria da aprendizagem computacional.
Características distintivas
[editar | editar código-fonte]Diferente da teoria da aprendizagem estatística, a teoria de aprendizagem algorítmica não toma os dados como amostrar randômicas, i.e, pontos de dados isolados uns dos outros. Isto faz com que a teoria seja apropriada para domínios onde as observações são (relativamente) livre de ruídos, mas não aleatórias, tal como a aprendizagem de linguagens[1] e descobertas científicas automatizadas.[2][3]
O conceito fundamental da teoria de aprendizagem algorítmica é a aprendizagem no limite: quando o número de pontos de dados cresce, um algoritmo de aprendizagem deve convergir para uma hipótese correta em "toda" sequência possível e consistente de dados no espaço do problema. Essa é uma versão não-probabilística da consistência estatística, que também prediz a convergência para um modelo correto no limite, mas permite que o aprendiz falhe em sequência de dados com medida de probabilidade 0 (zero).
A teoria de aprendizagem algorítmica também investiga o poder de aprendizado de máquinas de Turing. Outras frameworks consideram uma classe de algoritmos de aprendizagem bem mais restrita que as máquinas de Turing, como a de aprendizes que computam hipóteses mais rapidamente, tempo polinomial por exemplo. Um exemplo de framework como essa é a aprendizagem provável-aproximadamente correta.
Aprendizagem no limite
[editar | editar código-fonte]O conceito foi introduzido no artigo seminal de E. Mark Gold, chamado Language identification in the limit.[4] O objetivo da identificação de linguagens é permitir que uma máquina rodando um programa seja capaz de desenvolver outro programa onde qualquer sequencia dada pode ser testada para se determinar se é gramaticalmente válida ou não. A linguagem a ser aprendida não pode ser a língua inglesa ou qualquer outra linguagem natural - na verdade, a definição de "gramaticalmente" não pode ser nada conhecido pelo testador.
No modelo de aprendizagem de Gold, o testador fornece uma sentença de exemplo a cada passo, e o aprendiz responde com uma hipótese, que é uma sugestão de programa de computador para se determinar a correção gramatical. É necessário que todas as sentenças possíveis do testador (gramaticalmente válidas ou não) eventualmente apareçam na lista, mesmo sem uma ordem particular. É requerido do aprendiz que cada passo a hipótese deve ser correta para todas as sentenças até o momento.[carece de fontes]
Um aprendiz particular é dito hábil a "aprender uma linguagem no limite" se há um certo número de passos após o qual sua hipótese não muda.[carece de fontes] Neste ponto, ele (o aprendiz) de fato aprendeu a linguagem, pois toda sentença possível aparece em algum lugar na sequência de entrada (passado ou futuro), então a hipótese é correta para toda sentença. Não é exigido do aprendiz que se diga quando a hipótese correta foi alcançada, tudo que é pedido é que ela seja verdade.
Gold mostrou que qualquer linguagem definida por um programa de uma Máquina de Turing pode ser aprendida no limite por outra máquina Turing completa usando enumeração.[necessário esclarecer] Isso é feito pelo aprendiz ao se testar todos os possíveis 'programas de Máquinas de Turing' da vez até que um seja um identificado como correto até o momento - isto forma a hipótese para o passo atual. Eventualmente, o programa correto será encontrado, depois que a hipótese nunca mais mudar (mas, note que o aprendiz não sabe que a mesma não irá mais mudar).
Gold também mostrou que se o aprendiz recebe apenas exemplos positivos (i.e, apenas sentenças gramaticalmente válidas aparecem na entrada, sem sentenças inválidas), então a linguagem só pode ser garantidamente aprendida no limite se exite apenas um conjunto finito de possíveis sentenças na linguagem (isso é possível, por exemplo, se as sentenças possuírem um tamanho limitado e conhecido).[necessário esclarecer]
A identificação de linguagens no limite é um modelo altamente abstrato. Ele não permite limites de tempo de execução ou de memória (informática) computacional que podem ocorrer na prática, e o método da enumeração pode falhar se há erros na entrada. Contudo, a estrutura é bem poderosa, pois se essas condições restritas forem alcançadas, será possível a aprendizagem de qualquer programa conhecidamente computável. Isso se deve ao fato de que programas de Máquinas de Turing poderem ser escritos para imitar qualquer programa em qualquer linguagem de programação convencional.
Outros critérios de identificação
[editar | editar código-fonte]Teóricos da aprendizagem têm investigado outros critérios de aprendizado,[1] como os seguintes
- Eficiência: minimizando o número de pontos de dados requeridos antes da convergência a uma hipótese correta.
- Mudança de ideia: minimizando o número de trocas de hipóteses que ocorrem antes da convergência.[5]
Os limites das mudanças de ideias estão fortemente relacionados com os limites de erro que são estudados na teoria da aprendizagem estatística.[6] Kevin Kelly sugeriu que minimizar as mudanças de ideias está intimamente relacionado a escolher a hipótese mais simples no sentido da Navalha de Occam.[7]
Ver também
[editar | editar código-fonte]Referências
- ↑ a b Jain, S. et al (1999): Systems That Learn, 2nd ed. Cambridge, MA: MIT Press.
- ↑ Langley, P.; Simon, H.; Bradshaw, G. & Zytkow, J. (1987), Scientific Discovery: Computational Explorations of the Creative Processes, MIT Press, Cambridge
- ↑ Schulte, O. (2009), Simultaneous Discovery of Conservation Laws and Hidden Particles With Smith Matrix Decomposition, in Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), pp. 1481-1487
- ↑ Gold, E. Mark (1967), Language Identification in the Limit (PDF), 10, Information and Control, pp. 447–474 The original paper. Arquivado em 25 de janeiro de 2009, no Wayback Machine.
- ↑ Luo, W. & Schulte, O. (2005), Mind Change Efficient Learning, in Peter Auer & Ron Meir, ed., Proceedings of the Conference on Learning Theory (COLT), pp. 398-412
- ↑ Jain, S. and Sharma, A. (1999), On a generalized notion of mistake bounds, Proceedings of the Conference on Learning Theory (COLT), pp.249-256.
- ↑ Kevin T. Kelly (2007), Ockham’s Razor, Empirical Complexity, and Truth-finding Efficiency, Theoretical Computer Science, 383: 270-289.
Ligações externas
[editar | editar código-fonte]- Learning Theory in Computer Science.
- The Stanford Encyclopaedia of Philosophy provides a highly accessible introduction to key concepts in algorithmic learning theory, especially as they apply to the philosophical problems of inductive inference.