Qual é o teorema do almoço grátis?

7

Eu tenho lido sobre o Teorema Sem Almoço Gratuito, mas não consigo entender direito do que se trata. Ouvi esse teorema descrito em outro lugar como a alegação de que "não existe um otimizador universal de propósito geral". Por outro lado, o artigo da Wikipedia fala sobre 'soluções candidatas' que são "avaliadas uma a uma" - se considerarmos apenas algoritmos de uma forma específica, essa é uma afirmação muito mais limitada.

Alguém pode explicar o que esse teorema realmente afirma?

Casebash
fonte
Você leu o artigo inteiro, em particular a declaração formal e as interpretações ?
Raphael
fyi P ≠ NP pode ser considerado relacionado ao thm. um contraponto a esse teorema é que algoritmos de ML definitivamente diferentes têm desempenho diferente em dados do mundo real e são otimizáveis.
vzn

Respostas:

10

O teorema do No Free Lunch (NFL) foi estabelecido para desmascarar reivindicações do formulário:

Minha estratégia de otimização X é sempre a melhor.

Em particular, tais alegações surgiram na área de algoritmos genéticos / evolutivos.

A afirmação é, grosso modo: toda estratégia de otimização tem um desempenho ruim em muitos problemas. Portanto, não pode haver sempre a melhor estratégia e sua afirmação sobre X está errada.

Rafael
fonte
11
Por curiosidade, como é que isso se chama "sem almoço grátis"? Sua explicação faz sentido, mas não consigo ver o que isso faz com o almoço (nom).
StackExchange What The Heck
3
@yochannah Já ouviu a frase "Não existe almoço grátis" ? Para mim, nesse contexto, significa que um algoritmo pode ter algumas situações melhores, mas nem tudo melhor. Veja também o artigo da Wikipedia sobre o teorema , com sua própria analogia / explicação.
Tim S.
4
@yochannah Você pode pensar que o bom vendedor apenas quer convidá-lo para almoçar, mas sempre há um problema.
Raphael
3

Até onde eu entendo, essa teoria visa métodos de otimização global como algoritmos genéticos, redes neurais, recozimento simulado e assim por diante ...

A principal alegação é que, se considerarmos todas as possíveis instâncias de problemas de um determinado problema, esses métodos são tão bons quanto qualquer outro otimizador que considere a mesma quantidade de soluções candidatas, inclusive a Random Walk, por exemplo.

Os otimizadores de uso geral provavelmente funcionarão bem em muitas instâncias de problemas populares / da vida real, mas elas não representam bem todo o espaço de possíveis instâncias de problemas.

Ron Teller
fonte