Teorema da inexistência de almoço grátis

No folclore matemático e no folclore científico, o teorema da inexistência de almoço grátis (no free lunch em inglês ou NFL) (às vezes pluralizado) de David Wolpert e William Macready, alude ao ditado "não existe almoço grátis", ou seja, não existe nenhum atalho fácil para o sucesso. Ele apareceu em 1997 no "No Free Lunch Theorems for Optimization (Teoremas da Inexistência de Almoço Gratis para Otimização)".[1] Wolpert já havia derivado teoremas de almoço grátis inexistente para o aprendizado de máquina (inferência estatística).

Em 2005, Wolpert e Macready indicaram que o primeiro teorema em seu artigo "afirma que quaisquer dois algoritmos de otimização são equivalentes quando seu desempenho é calculado em média entre todos os problemas possíveis".[2]

O teorema da inexistência de almoço grátis (NFL) é uma consequência fácil de enunciar e compreender dos teoremas que Wolpert e Macready realmente comprovaram. Ele é objetivamente mais fraco do que os teoremas comprovados e, portanto, não os encapsula. Vários pesquisadores ampliaram substancialmente o trabalho de Wolpert e Macready. Em termos de como o teorema NFL é usado no contexto da área de pesquisa, o teorema da inexistência de almoço grátis em busca e otimização é um campo dedicado à análise matemática de dados para identidade estatística, particularmente busca[3] e otimização.[1]

Exemplo

Imagine um universo de brinquedos que existe por exatamente dois dias e em cada dia contém exatamente um objeto: um quadrado ou um triângulo. O universo tem exatamente quatro histórias possíveis:

  1. (quadrado, triângulo): o universo contém um quadrado no primeiro dia e um triângulo no segundo dia
  2. (quadrado, quadrado)
  3. (triângulo, triângulo)
  4. (triângulo, quadrado)

Qualquer estratégia de previsão que seja bem-sucedida para a segunda história, prevendo um quadrado no dia 2 se houver um quadrado no dia 1, falhará na primeira história e vice-versa. Se todas as histórias forem igualmente prováveis, qualquer estratégia de previsão terá a mesma pontuação, com a mesma taxa de precisão de 0,5.[4]

Origem

Wolpert e Macready apresentam dois teoremas NFL intimamente relacionados ao teorema folclórico. Em seu artigo, eles afirmam:  "Chamamos os resultados associados de teoremas da NFL porque eles demonstram que se um algoritmo tem um bom desempenho em uma determinada classe de problemas, ele necessariamente paga por isso com um desempenho degradado no conjunto de todos os problemas restantes." O primeiro teorema levanta a hipótese de funções objetivas que não mudam enquanto otimização está em progresso e o segundo levanta a hipótese de funções objetivas que poderiam mudar.[1]

Teorema — Para quaisquer algoritmos a1 e a2, no passo de iteração m onde denota o conjunto ordenado de tamanho dos valores de custo associados aos valores de entrada , é a função que está sendo otimizada e é a probabilidade condicional de obter uma dada sequência de valores de custo a partir do algoritmo executado vezes na função .

O teorema pode ser formulado de forma equivalente da seguinte forma:

Teorema — Dado um conjunto finito e um conjunto finito de números reais, suponha que seja escolhido aleatoriamente de acordo com a distribuição uniforme no conjunto de todas as funções possíveis de a . Para o problema de otimização de sobre o conjunto , nenhum algoritmo tem melhor desempenho do que a busca cega.

Aqui, a busca cega significa que em cada etapa do algoritmo, o elemento é escolhido aleatoriamente com distrbuição de probabilidade uniforme a partir dos elementos de que não foram escolhidos anteriormente.

Em essência, isso diz que, quando todas as funções f são igualmente prováveis, a probabilidade de observar uma sequência arbitrária de valores m durante a otimização não depende do algoritmo. Na estrutura analítica de Wolpert e Macready, o desempenho é uma função da sequência de valores observados (e não, por exemplo, do tempo de relógio de parede), portanto, segue-se facilmente que todos os algoritmos têm um desempenho identicamente distribuído quando funções objetivo são desenhadas uniformemente ao acaso, e também que todos os algoritmos têm desempenho médio idêntico. Mas o desempenho médio idêntico de todos os algoritmos não implica o primeiro teorema e, portanto, o teorema folclórico não é equivalente ao teorema original.

O segundo teorema estabelece um resultado NFL semelhante, mas "mais sutil", para funções objetivas que variam com o tempo.[1]

Motivação

Os teoremas NFL não foram explicitamente motivados pela questão do que pode ser inferido (no caso do NFL para aprendizado de máquina) ou encontrado (no caso do NFL para busca) quando o "ambiente é aleatório uniforme". Em vez disso, a aleatoriedade uniforme foi usada como ferramenta para comparar o número de ambientes nos quais o algoritmo A supera o algoritmo B com o número de ambientes nos quais B supera A. O NFL nos diz (apropriadamente ponderado) que há tantos ambientes em ambos os conjuntos.

Isso se aplica a muitas definições do que exatamente é um "ambiente". Em particular, existem tantas distribuições anteriores (apropriadamente ponderadas) nas quais o algoritmo de aprendizagem A supera B (em média) quanto o contrário.[carece de fontes?] Esta afirmação sobre conjuntos de priores é o que é mais importante sobre o teorema, não o fato de que quaisquer dois algoritmos têm o mesmo desempenho para a distribuição prioritária única e específica que atribui probabilidade igual a todos os ambientes.

Embora a NFL seja importante para entender a limitação fundamental de um conjunto de problemas, ela não afirma nada sobre cada instância específica de um problema que pode surgir na prática. Ou seja, a NFL declara o que está contido em suas declarações matemáticas e nada mais é do que isso. Por exemplo, ela se aplica às situações em que o algoritmo é fixado a priori e um problema de pior caso para o algoritmo fixado é escolhido a posteriori. Portanto, se temos um "bom" problema na prática ou se podemos escolher um "bom" algoritmo de aprendizado para uma determinada instância específica do problema, a NFL não menciona nenhuma limitação sobre essa instância específica do problema. Embora a NFL possa parecer contraditória com os resultados de outros artigos que sugerem a generalização de algoritmos de aprendizado ou heurísticas de busca, é importante entender a diferença entre a lógica matemática exata da NFL e sua interpretação intuitiva.

Implicações

Para ilustrar uma das implicações contra-intuitivas do teorema, suponha que consertemos dois algoritmos de aprendizado supervisionado, C e D. Em seguida, amostramos uma função-alvo f para produzir um conjunto de pares de entrada-saída, d. A questão é como devemos escolher entre treinar C ou D em d, a fim de fazer previsões sobre qual saída estaria associada a um ponto fora de d.

É comum em quase toda a ciência e estatística responder a essa pergunta – escolher entre C e D – executando validação cruzada em d com esses dois algoritmos. Em outras palavras, para decidir se generalizamos a partir de d com C ou D ', vemos qual deles apresenta o melhor desempenho fora da amostra quando testado dentro de d.

Como C e D são fixos, esse uso da validação cruzada para escolher entre eles é, em si, um algoritmo, ou seja, uma maneira de generalizar a partir de um conjunto de dados arbitrário. Chame esse algoritmo "A". (Pode-se argumentar que A é um modelo simplificado do próprio método científico.)

Também poderíamos usar a anti-validação cruzada para fazer nossa escolha. Em outras palavras, poderíamos escolher entre C e D com base em qual apresenta o pior desempenho fora da amostra dentro de d. Novamente, como C e D são fixos, esse uso da anti-validação cruzada é, em si, um algoritmo. Chame esse algoritmo "B".

O teorema NFL nos diz (em termos gerais) que B deve vencer A em tantas funções-alvo (e conjuntos de dados associados d) quanto A vence B. Nesse sentido muito específico, o método científico perderá para o método "anti" científico com a mesma facilidade com que vence.[5]

O teorema só se aplica se a função-alvo for escolhida a partir de uma distribuição uniforme de todas as funções possíveis. Se este não for o caso, e certas funções-alvo tiverem maior probabilidade de serem escolhidas do que outras, então A pode ter um desempenho geral melhor do que B. A contribuição do NFL é que ela nos diz que escolher um algoritmo apropriado requer fazer suposições sobre os tipos de funções-alvo para as quais o algoritmo está sendo usado. Sem suposições, nenhum "meta-algoritmo", como o método científico, tem um desempenho melhor do que a escolha aleatória.

Enquanto alguns estudiosos argumentam que o NFL transmite alguns insights importantes, outros argumentam que a NFL é de pouca relevância para a pesquisa de aprendizado de máquina.[6] Se a navalha de Occam estiver correta, por exemplo, se sequências de menor complexidade de Kolmogorov forem mais prováveis do que sequências de maior complexidade, então (como é observado na vida real) alguns algoritmos, como a validação cruzada, têm melhor desempenho em média em problemas práticos (quando comparados com a escolha aleatória ou com a antivalidação cruzada).

No entanto, existem grandes desafios formais no uso de argumentos baseados na complexidade de Kolmogorov para estabelecer propriedades do mundo real, uma vez que ela é incomputável e indefinida até uma constante aditiva arbitrária. Em parte em reconhecimento a esses desafios, argumentou-se recentemente que existem maneiras de contornar os teoremas de "nenhum almoço grátis" sem invocar máquinas de Turing, usando "meta-indução".[7][8] Além disso, a complexidade de Kolmogorov de modelos de aprendizado de máquina pode ser limitada superiormente por meio de compressões de sua rotulagem de dados, e é possível produzir limites de generalização entre domínios não vazios por meio da complexidade de Kolmogorov.

Referências

  1. ↑ a b c d Wolpert, D. H.; Macready, W. G. (1997). «No Free Lunch Theorems for Optimization». IEEE Transactions on Evolutionary Computation. 1: 67–82. CiteSeerX 10.1.1.138.6606Acessível livremente. doi:10.1109/4235.585893 
  2. ↑ Wolpert, D.H.; Macready, W.G. (dezembro de 2005). «Coevolutionary Free Lunches». IEEE Transactions on Evolutionary Computation (em inglês). 9 (6): 721–735. Bibcode:2005ITEC....9..721W. ISSN 1089-778X. doi:10.1109/TEVC.2005.856205  |hdl-access= requer |hdl= (ajuda)
  3. ↑ Wolpert, D. H.; Macready, W. G. (1995). «No Free Lunch Theorems for Search». Santa Fe Institute. Technical Report SFI-TR-95-02-010 
  4. ↑ Forster, Malcolm R. (1999). «How do Simple Rules 'Fit to Reality' in a Complex World?». Minds and Machines. 9 (4): 543–564. doi:10.1023/A:1008304819398 
  5. ↑ Wolpert, David H. (dezembro de 2013). «Ubiquity symposium: Evolutionary computation and the processes of life: what the no free lunch theorems really mean: how to improve search algorithms». Ubiquity (em inglês). 2013 (December): 1–15. ISSN 1530-2180. doi:10.1145/2555235.2555237 
  6. ↑ Whitley, Darrell; Watson, Jean Paul (2005). Burke, Edmund K.; Kendall, Graham, eds. Complexity Theory and the No Free Lunch Theorem (em inglês). Boston, MA: Springer US. pp. 317–339. ISBN 978-0-387-23460-1. doi:10.1007/0-387-28356-0_11 
  7. ↑ Schurz, G. (2019). Hume's Problem Solved: The Optimality of Meta-Induction. [S.l.]: MIT Press 
  8. ↑ Wolpert, D. H. (2023). «The Implications of the No-Free-Lunch Theorems for Meta-induction». Journal for General Philosophy of Science. 54 (3): 421–432. arXiv:2103.11956Acessível livremente. doi:10.1007/s10838-022-09609-2 

Ligações externas

Este artigo é emitido por Wikipédia. O texto é licenciado sob Creative Commons Attribution-Share Alike 4.0. Termos adicionais podem ser aplicados aos arquivos de mídia.