Este artigo é que minha recontagem gratuita de Aprendizagem pode ser indecidível, Shai Ben-David, et al.

Recentemente, em Habré, o artigo Machine learning enfrentou um problema matemático não resolvido , que é uma tradução do artigo de Shay Ben-David no artigo da Nature News com o mesmo nome. No entanto, devido à natureza do tópico e à brevidade da revisão original, permaneceu completamente incompreensível para mim o que estava no artigo. Conhecendo Shai Ben-David, como autor do excelente livro "Entendendo o aprendizado de máquina: da teoria aos algoritmos", fiquei interessado neste tópico, me familiarizei com este trabalho e tentei delinear os principais pontos aqui.

Devo dizer imediatamente que o artigo é bastante complicado e, talvez, tenha perdido alguns pontos importantes, mas minha revisão será mais completa do que a que já está em Habré.

Algumas palavras sobre a aprendizagem do PAC em geral

A primeira coisa que me confundiu em uma revisão da Nature News foi que o problema de aprendizagem em si foi apresentado como algo completamente novo. De fato, esse é um problema longo e relativamente bem estudado.

Existe uma teoria da aprendizagem provavelmente quase correta (provavelmente uma aprendizagem aproximadamente correta, PAC ).

Essa teoria remonta aos anos 80 do século passado. No entanto, ele não fornece nenhum indicador mensurável que reflita a capacidade de aprendizado de um algoritmo. Mas essa resposta é dada pela teoria do aprendizado estatístico ( teoria do VC ) já desenvolvida por V. Vapnik e A. Chervonenkis. Esta teoria é baseada em um indicador numérico da dimensão VC. A dimensão VC é uma estimativa combinatória do tamanho máximo de dados que o algoritmo pode dividir em duas partes de todas as maneiras possíveis.

O principal teorema da teoria da CV, em uma das formulações possíveis, prova o fato de que, se a dimensão VC do algoritmo for finita, ela será treinada pelo PAC. Além disso, a dimensão VC é um indicador de quão rapidamente, com o aumento do tamanho da amostra empírica, o valor do risco empírico converge para o valor do risco médio.

Assim, o problema do aprendizado de máquina dos algoritmos de aprendizado de máquina per se é relativamente bem estudado e possui uma base matemática rigorosa.

Qual é, então, o assunto de um artigo na Nature?

Os autores escrevem que o problema com a teoria do PAC, baseada em várias dimensões da dimensão, é que ela não é universal.

Os autores dão um exemplo interessante de um problema cuja declaração em si é projetada para que o sucesso não possa ser formulado como aprendizado do PAC. Os autores escrevem:

Imagine que temos um site na Internet no qual exibimos anúncios. Defina X como o conjunto de todos os visitantes em potencial deste site. A publicidade é selecionada em um determinado pool de publicidade. Condicionalmente, suponha que cada anúncio do pool seja direcionado a alguma categoria de usuários: anúncios de esportes para fãs de esportes etc. A tarefa é colocar exatamente o tipo de publicidade mais relevante para os visitantes do site .

O problema aqui é que não sabemos realmente quem visitará o site no futuro. Para resumir, a declaração desse problema pode ser descrita da seguinte maneira:

Tendo um conjunto de recursos $$$F$sobre o conjunto $$$X$encontre essa função $$$F_ {best}$para que sua métrica sobre a distribuição desconhecida $$$P$foi máximo. Além disso, é necessário encontrar essa função com base em um conjunto limitado de quantidades independentes distribuídas de forma idêntica $$$P$

Treinamento EMX

Shai Ben-David e seus colegas introduzem um novo conceito - E stimating the M a X imum (aprendizado EMX), que apenas fornece critérios de aprendizado para esses problemas de maximização:

Para conjunto de recursos $$$F$conjuntos de entrada $$$X$e distribuição desconhecida $$$P$para qualquer número $$$d = d (\ epsilon, \ delta)$função $$$G (s)$é $$$(\ epsilon, \ delta)$-EMX-treinado se para qualquer distribuição $$$P$:

$$

$$Pr_ {S \ sim P ^ d} [\ mathbb {E} _P (G (S)) \ leq \ sup_ {h \ em F} \ mathbb {E} (h) - \ epsilon] \ leq \ delta$$

Essa definição de aprendizado é, sem dúvida, mais geral que o conceito de PAC.

Então, onde está o continuum e o "problema não resolvido da matemática"?

Os autores provam o seguinte teorema:
Rotatividade da EMX $$$F$a respeito $$$P$independente do sistema de axiomas Zermelo - Frenkel com o axioma de escolha (a seguir denominado ZFC).

Em outras palavras, usando axiomas matemáticos padrão, não podemos, no caso geral, provar a possibilidade de encontrar uma solução para o problema de aprendizado do EMX ou provar a impossibilidade de encontrar essa solução.

Os autores também mostram que, para o caso geral de aprendizado EMX, não há análogo da dimensão VC (ou qualquer outra dimensão) que seria finito no caso da mensurabilidade EMX e vice-versa, a aprendizabilidade EMX seguiria sua finitude. Mais rigorosamente, eles o formulam da seguinte maneira:

Existe uma constante $$$c$que se assumirmos a consistência do ZFC, essa propriedade não existe $$$A (X, Y)$isso para alguns$$ $ inline $ m, M> c $ inline $ para qualquer $$$X$e conjunto de recursos $$$F$seria realizado:

• Se $$$A (X, Y)$verdade então $$$(1/3, 1/3)$complexidade do aprendizado EMX $$$F$não excede M;
• Se $$$A (X, Y)$falso então $$$(1/3, 1/3)$complexidade do aprendizado EMX $$$F$pelo menos m;

Pelo contrário, isso é verdade para, por exemplo, a dimensão VC, pois para $$$A (X, Y)$igual $$$VC \ leq d$será essencialmente uma formulação do principal teorema da teoria da VC.

Conclusão

A mensagem do trabalho está, de fato, pouco relacionada às questões práticas do aprendizado de máquina, ou mesmo às questões teóricas da teoria do aprendizado estatístico. Pareceu-me que existem dois pensamentos principais no trabalho:

• Uma bela conexão entre o aprendizado EMX e os teoremas de Gödel;
• A impossibilidade fundamental de criar uma caracterização universal do aprendizado (como a dimensão VC) para a classe geral de problemas de aprendizado de máquina.

Ao mesmo tempo, eu pessoalmente não gosto do título "O aprendizado de máquina encontrou um problema matemático não resolvido", usado na tradução de uma revisão deste artigo . Na minha opinião, este é um clickbait absoluto, além disso, simplesmente não corresponde à realidade. O trabalho original não significa que alguém tenha encontrado alguma coisa. O aprendizado de máquina e a teoria do PAC funcionaram e continuam a funcionar. É apontado que a teoria do PAC não pode ser generalizada para algumas afirmações particulares do problema de aprendizado de máquina, são encontradas conexões interessantes com os teoremas de Gödel, mas nenhuma palavra sobre algum problema não resolvido que o aprendizado de máquina encontrou.