Quais são as implicações do teorema "No Free Lunch" para aprendizado de máquina?

O teorema do No Free Lunch (NFL) afirma (consulte o artigo Coevolutionary Free Lunchches de David H. Wolpert e William G. Macready)

quaisquer dois algoritmos são equivalentes quando o desempenho é medido em todos os possíveis problemas

O teorema "No Free Lunch" é realmente verdadeiro? O que isso realmente significa? Um bom exemplo (no contexto de ML) ilustrando essa afirmação seria bom.

Vi alguns algoritmos que se comportam muito mal e tenho dificuldade em acreditar que eles realmente seguem o teorema mencionado acima, por isso estou tentando entender se minha interpretação desse teorema está correta ou não. Ou é apenas outro teorema ornamental como o teorema da aproximação universal de Cybenko?

Essa é uma reação muito comum após o primeiro encontro com os teoremas do No Free Lunch (NFLs). O aprendizado de máquina é especialmente pouco intuitivo, porque contraria tudo o que é discutido na comunidade de ML. Dito isto, o teorema é verdadeiro, mas o que isso significa está aberto a algum debate.

Para reafirmar o teorema das pessoas que não o conhecem, o teorema da NFL para aprendizado de máquina é realmente um caso especial do teorema da NFL para busca e otimização locais . A versão de pesquisa local é mais fácil de entender. O teorema faz a seguinte afirmação um tanto radical:

Média de todos os possíveis problemas de otimização, a qualidade média da solução encontrada por qualquer algoritmo de pesquisa local que você escolher usar é exatamente a mesma que a qualidade média da solução de um algoritmo local de "pesquisa" que apenas gera possíveis soluções, amostrando uniformemente aleatoriamente a partir do espaço de todas as soluções.

Outra formulação, quando as pessoas querem uma reação ainda mais forte, é dizer que, se você deseja encontrar a melhor solução para um problema, é tão bom tentar coisas que parecem estar tornando sua solução iterativamente pior quanto tentar coisas que parece estar tornando sua solução iterativamente melhor. Em média, ambas as abordagens são igualmente boas.

Ok, então por que isso é verdade? Bem, a chave está nos detalhes. Wolpert às vezes descreveu o teorema como uma especialização do trabalho de Hume sobre o problema da indução . A afirmação básica do problema da indução é: não temos base lógica para supor que o futuro será como o passado. Logicamente, não há razão para que as leis da física não possam mudar radicalmente amanhã. De uma perspectiva puramente lógica , é totalmente razoável que o futuro possa ser diferente do passado de várias maneiras. O problema de Hume é que, em geral, o futuro é como o passado de várias maneiras. Ele tentou formular um argumento filosófico (lógico) de que isso precisava ser assim, mas basicamente falhou.

Os teoremas do No Free Lunch dizem a mesma coisa. Se você não sabe como é o seu espaço de pesquisa, se refina iterativamente sua ideia de como é uma boa solução, em resposta às observações feitas anteriormente sobre como são as boas soluções (por exemplo, aprendendo com dados), então é tão provável que a operação que você faz ajude quanto doa. É por isso que a parte "calculada a média de todos os possíveis problemas de otimização" é fundamental. Para qualquer problema de otimização em que a subida é uma boa estratégia após$k$movimentos, podemos fazer um que seja idêntico, exceto que o k-ésimo movimento de escalada leva a uma solução terrível. A prova real é mais sutil que isso, mas essa é a ideia básica.

Um breve resumo leigo pode ser:

Um algoritmo de aprendizado de máquina só pode ser feito para funcionar melhor em alguns tipos de problemas, sendo feito para funcionar pior em outro tipo de problema.

Então, o que isso significa em um sentido prático? Isso significa que você precisa ter alguma razão a priori para pensar que seu algoritmo será eficaz em um problema específico . Exatamente como uma boa razão é objeto de intenso debate na comunidade de ML. Isso está intimamente relacionado à troca de viés / variância .

Algumas respostas comuns são:

• Quando você olha para um novo problema de otimização, embora possa ter algum tipo aleatório de estrutura, os problemas que realmente encontramos no mundo real são muito mais regulares e certos temas comuns estão presentes, como o fato de mover " morro acima "(minimizar erros) iterativamente tende a levar a boas soluções. Basicamente, essa escola de pensamento diz que a NFL é um teorema ornamental: a maioria dos algoritmos de ML funciona melhor no "tipo de problemas que vemos na vida real", trabalhando pior no "tipo de problemas que não vemos na vida real".
• Quando você olha para um novo problema de otimização em [insira seu domínio de aplicativo favorito], embora possa ter qualquer tipo aleatório de estrutura, os problemas tendem a se parecer com [o que você pensa], o que torna [seu algoritmo favorito] muito mais eficaz do que adivinhação aleatória.
• Os próprios Wolpert e McCready publicaram um resultado interessante, mostrando que, na verdade, existem processos de otimização especializados, baseados na co-evolução, que são consistentemente melhores do que a adivinhação aleatória.

Independentemente disso, é indiscutível que alguns algoritmos são melhores que outros, em certos subdomínios (podemos ver isso empiricamente). A NFL nos diz que para ser melhor lá, eles precisam ser piores em outro lugar. A questão a ser debatida é se o "outro lugar" é um problema real ou puramente artificial.