terça-feira, 22 de janeiro de 2019

Aprendizagem de máquina leva matemáticos a um problema insolúvel*

Alfred Eisenstaedt/ LIFE Picture Coll./Getty

por Davide Castelvecchi

Uma equipe de pesquisadores esbarrou em uma questão que é matematicamente irrespondível porque está ligada a paradoxos lógicos descobertos pelo matemático austríaco Kurt Gödel, nos anos 1930, que não podem ser resolvidos usando a matemática padrão.

Os matemáticos, que estavam trabalhando em um problema de aprendizagem de máquina, mostram que a questão da "capacidade de aprendizado" - se um algoritmo pode extrair um padrão de dados limitados - está ligada a um paradoxo conhecido como a hipótese do contínuo. Gödel mostrou que a afirmação não pode ser comprovada como verdadeira ou falsa usando linguagem matemática padrão. O último resultado apareceu no dia 7 de janeiro no Nature Machine Intelligence[1].

"Para nós, foi uma surpresa", diz Amir Yehudayoff, do Instituto de Tecnologia Technion-Israel, em Haifa, co-autor do artigo. Ele diz que, embora haja um número de questões matemáticas técnicas que são conhecidas como "indecidíveis", ele não esperava que esse fenômeno aparecesse em um problema relativamente simples no aprendizado de máquina.

John Tucker, um cientista da computação na Universidade de Swansea, no Reino Unido, diz que o artigo é "um resultado pesado nos limites do nosso conhecimento", com implicações fundamentais para a matemática e o aprendizado de máquina.

Nem todos os conjuntos são iguais

Os pesquisadores geralmente definem a capacidade de aprendizado em termos de se um algoritmo pode generalizar seu conhecimento. O algoritmo recebe a resposta para uma pergunta "sim ou não" - como "Essa imagem mostra um gato?" - para um número limitado de objetos e, em seguida, precisa adivinhar a resposta para novos objetos.

Yehudayoff e seus colaboradores chegaram a seu resultado enquanto investigavam a conexão entre capacidade de aprendizado e "compressão", que envolve encontrar uma maneira de resumir as características salientes de um grande conjunto de dados em um conjunto menor de dados. Os autores descobriram que a capacidade da informação de ser comprimida eficientemente se resume a uma questão na teoria de conjuntos - coleções matemáticas de objetos, como os conjuntos nos diagramas de Venn. Em particular, refere-se aos diferentes tamanhos de conjuntos contendo infinitamente muitos objetos.

Georg Cantor, o fundador da teoria dos conjuntos, demonstrou na década de 1870 que nem todos os conjuntos infinitos são criados iguais: em particular, o conjunto de números inteiros é "menor" que o conjunto de todos os números reais, também conhecido como continuum. (Os números reais incluem os números irracionais, bem como os racionais e inteiros.) Cantor também sugeriu que não pode haver conjuntos de tamanho intermediário - isto é, maiores que os inteiros, mas menores que o contínuo. Mas ele não foi capaz de provar essa hipótese contínua, nem muitos matemáticos e lógicos que o seguiram.

Seus esforços foram em vão. Um resultado de 1940 de Gödel (que foi completado na década de 1960 pelo matemático americano Paul Cohen) mostrou que a hipótese do contínuo não pode ser provada nem verdadeira nem falsa a partir dos axiomas padrões - as afirmações tomadas como verdadeiras - da teoria dos conjuntos, que são comumente tomados como base para toda a matemática.

O trabalho de Gödel e Cohen sobre a hipótese do continuum implica que podem existir universos matemáticos paralelos que são compatíveis com a matemática padrão - um em que a hipótese do contínuo é adicionada aos axiomas padrão e, portanto, declarada como verdadeira e outra na qual é declarada falso.

Limbo da capacidade de aprendizado

No último artigo, Yehudayoff e seus colaboradores definem a capacidade de aprendizado como a habilidade de fazer previsões sobre um grande conjunto de dados por amostragem de um pequeno número de pontos de dados. O link com o problema do Cantor é que existem infinitas maneiras de escolher o conjunto menor, mas o tamanho desse infinito é desconhecido.

Os autores mostram que, se a hipótese do contínuo é verdadeira, uma amostra pequena é suficiente para fazer a extrapolação. Mas se for falso, nenhuma amostra finita pode ser suficiente. Dessa forma, eles mostram que o problema da capacidade de aprender é equivalente à hipótese do contínuo. Portanto, o problema da capacidade de aprendizado também está em um estado de limbo que só pode ser resolvido escolhendo o universo axiomático.

O resultado também ajuda a dar uma compreensão mais ampla da capacidade de aprendizado, diz Yehudayoff. “Essa conexão entre compressão e generalização é realmente fundamental se você quiser entender o aprendizado.”

Pesquisadores descobriram uma série de problemas "indecidíveis", diz Peter O'Hearn, cientista da computação da University College London. Em particular, seguindo o trabalho de Gödel, Alan Turing - que foi um dos fundadores da teoria dos algoritmos - encontrou uma classe de questões que nenhum programa de computador pode ter a garantia de responder em qualquer número finito de passos.

Mas a indecidibilidade nos resultados mais recentes é "de um tipo raro", e muito mais surpreendente, O’Hearn acrescenta: aponta para o que Gödel descobriu ser uma incompletude intrínseca em qualquer linguagem matemática. As descobertas provavelmente serão importantes para a teoria do aprendizado de máquina, acrescenta ele, embora “não tenha certeza se terá muito impacto na prática”.

Referência
[1]. Ben-David, S., Hrubeš, P., Moran, S., Shpilka, A. & Yehudayoff, A. (2019). Nature Machine Inteligence 1, 44–48 (2019).

=============================
Artigo publicado na Nature, vol 565, pag 277, em 08 de janeiro de 2019.

Nenhum comentário:

Postar um comentário