No Free Lunch Theorem (NFLT)
“공짜 점심은 없다”.
Literally (말 그대로), “공짜 점심은 없는 것 (No free lunch)” 을 통해 “머신러닝의 최적화 (or No general models)”와의 연관성을 바로 연상시키기는 어렵다고 생각한다. “공짜 점심” 과 “Machine Learning, Optimization”이 대체 무슨 연관성이 있는 걸까? 그래서 과연, 무슨 말을 하고 싶은 걸까?
심지어 Kevin P. Murphy의 「Machine Learning : A probabilistic Perspective (Chap.1.4.9)」 에서도 언급되어 있는데, 이해하지 못하고 그냥 지나치기에는 뭔가 찜찜했고 그래서 더 이해하고 싶다는 생각이 들었다.
☾ Table of contents
☺︎ What NFLT exactly means : NFLT는 무엇일까?
☺︎ An origin of “No Free Lunch Theorem (NFLT)” : NFLT의 기원/배경은?
☻ Reference
☺︎ What NFLT exactly means
우선은 David Wolpert와 William Macready가 1997년 발표한 「No Free Lunch Theorems for optimization」 이라는 논문에 실린 것으로
We have dubbed the associated results “No Free Lunch” theorems because they demonstrate that if an algorithm perfoms well on a certian class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems.
즉, 간단히 말해 특정 문제 혹은 데이터 셋에 맞게 잘 만들어지고, 짜여지고, 그리고 최적화된 “알고리즘, 해결책, 방법 등”은 다른 문제 혹은 데이터 셋에서는 맞지 않는 다는 것을 수학적으로 증명한 정리이다. 따라서 “공짜 점심은 없다”라는 말처럼 우리는 “점심값을 지불을 해야한다”라고 해석 할 수 있을 것이다. 여기서 “점심값”이라는 것은 우리가 풀고자하는 문제에 대한 값이라고 해석 할 수 있을 것 같다.
즉, 노력이든 시간이든 열정이든 혹은 정말 말 그대로 “알고리즘, 해결책, 방법 등”을 위한 비용을 지불 해야만 한다는 것이 아닐까?
그럼, Kevin P. Murphy에서 언급한 내용을 확인해보자 [1].
(한글판, 영문판에 있는 문구를 그대로 인용하였다. 한글판은 개인소장용으로 직접 구매하였다.)
[영문판]
All models are wrong, but some models are useful. — George Box (Box and Draper 1987) Much of machine learning is concerned with devising different models, and different algorithms to fit them. We can use methods such as cross validation to empirically choose the best method for our particular problem. However, there is no universally best model — this is sometimes called the no free lunch theorem (Wolpert 1996). The reason for this is that a set of assumptions that works well in one domain may work poorly in another. As a consequence of the no free lunch theorem, we need to develop many different types of models, to cover the wide variety of data that occurs in the real world. And for each model, there may be many different algorithms we can use to train the model, which make different speed-accuracy-complexity tradeoffs. It is this combination of data, models and algorithms that we will be studying in the subsequent chapters.
모든 모형은 잘못됐지만 일부 모형은 유용하다. — George Box (Box and Draper 1987)
머신 러닝의 대부분은 새로운 모형을 창안하고, 그것들을 적합하게 다루기 위한 알고리즘을 만드는 것과 관련돼 있다. 특정 문제에 대한 최적의 기법을 실험적으로 선택하기 위해 교차 검증과 같은 방법을 사용할 수 있다. 하지만 모든 문제에 최적인 단 하나의 최고 모형은 없다. 이것은 공짜 점심은 없다는 이론으로 불린다 (Wolpert 1996). 이것은 하나의 영역에서 잘 작동하는 가정이 다른 영역에서 잘못 작동하는 경우가 있기 때문이다. 공짜 점심이 없다는 이론의 결과로, 실제 세계에서 발생하는 다양한 데이터를 다루기 위해서 여러 형태의 모형을 개발해야 한다. 그리고 각 모형에 대해서 훈련을 위해 사용할 수 있는 여러가지 알고리즘이 있다. 이런 알고리즘은 서로 다른 속도-정확도-복잡도 트레이드오프를 갖고 있다. 앞으로 이런 데이터와 모형, 알고리즘의 조합을 공부 할 것이다.
그리고 이러한 아래 말하는 바와 같이, 이러한 NFLT는 Machine learning 그리고 Optimization에서 많이 거론되지만, 여전히 이해하는게 어려울 수 도 있다.
The No Free Lunch Theorem is often thrown around in the field of optimization and machine learning, often with little understanding of what it means or implies. The theorem states that all optimization algorithms perform equally well when their performance is averaged across all possible problems [2].
Okay, 여기까지는 어디서나 찾을 수 있는 부분이라고 생각한다.
하지만 여전히 “공짜 점심”과 “머신러닝”과의 연관성에 대하여 100% 이해가 되지 않았다.
이건 TMI이지만, 공부를 하다보면 항상 혹은 종종 ‘Why?’ 라는 부분에서 막힐 때가 있다. (그래서 내가 Physics를 좋아하지만, 다가가기 무척 어려운 학문이라고 생각한다)
마음은 급해서 이 책을 다 끝내야만 하는데, 이 것 하나때문에 진도도 못나가고 굉장히 답답하지만 그래도 반드시 이해가 수반되어야만 넘어갈 수 있을 것 같은 고집 아닌 고집을 부릴때가 있다.
물론, 우리는 이해할 부분이 많고, ‘이게 뭐라고?’ 할 수도 있지만, 그래도 뭔가 이해하면 더 깊게 생각할 수 있고, 또 오래 기억 할 수도 있어서 조금 고집을 부리는 것 같다.
☺︎ An origin of “No Free Lunch Theorem (NFLT)”
There’s no free lunch is an American axiom that is well known in economic circles, though its origins seem to be in literature. We will look at the meaning of the admonition there’s no free lunch, where it came from and some examples of its use in sentences.
The phrase there’s no free lunch means you don’t get something for nothing, or anything one receives for free will be paid for in another way. The term comes from a practice in the nineteenth century in the United States, whereby taverns provided a free lunch to drinkers. Obviously, by affording a thrifty lunch of perhaps boiled eggs and peanuts, the bartenders kept paying patrons in their establishments longer, quaffing profitable alcoholic beverages. The term there’s no free lunch was first used in 1942 by Paul Mallon, an American political journalist. It was made more popular when the author Robert Heinlein used it in his 1966 novel The Moon is a Harsh Mistress, and then more popular still when it was used by the economist Milton Friedman as the title of his book, There’s No Such Thing as a Free Lunch. Some say that the term there’s no free lunch originated with New Yorker Fiorello La Guardia, elected mayor of New York in 1933, when he said “È finita la cuccagna!” This was in regards to the corruption and graft that he intended to clean up. In reality, this phrase is more correctly translated as “the party’s over!” The term there’s no free lunch is often rendered as there’s no such thing as a free lunch, there ain’t no such thing as a free lunch or the acronyms TANSTAAFL, TINSTAAFL, and TNSTAAFL [3,4].
즉, you don’t get something for nothing, or anything one receives for free will be paid for in another way. 당신은 아무것도 얻지 못하거나 무료로받는 것은 다른 방식으로 지불한다라는 의미로 볼 수 있다.
그래서 “최적화된 알고리즘”과의 연관성에 대하여 내가 해석 한 바로는
모든 문제에 적용 가능한 “공짜 알고리즘, 해결책, 방법 등”은 없다. 따라서 우리가 풀고자 하는 문제에 대한 정의, 데이터, 여러 상황에 따라서 그에 맞는 최적화된 “알고리즘, 해결책, 방법 등”을 모색해야 한다. 라고 생각한다.
추가로 글을 읽다가 No free lunch의 기원에 대해서 생각한 바를 적으면, 19세기 어떤 음료를 마시든 free lunch가 제공되었지만 그 후 경제성장 및 여러가지 상황이 발생하면서 이러한 제공이 그만두게 되면서 No free lunch라는 말이 나왔다는 것이다. 즉, 어떤 음료 = 어떤 문제 든 free lunch = solution, algorithm, answer이 될 수 없다 (No)이다. 이는 처음에 언급되었듯, 특정 문제 혹은 데이터 셋에 맞게 잘 만들어지고, 짜여지고, 그리고 최적화된 “알고리즘, 해결책, 방법 등”은 다른 문제 혹은 데이터 셋에서는 맞지 않는 다는 것을 수학적으로 증명한 정리이다. 라고 해석 할 수 있을 것이다 (050722 update by SS)
그래도 뭔가 블로그 글을 작성하면서 NFLT에 대한 이해도가 높아진 것 같아서 재밌었다.
내가 이해한 것들을 누군가와 함께 나누고, 누군가가 이해하는데 조금이나마 도움이 되었음 좋겠다.
나 또한 누군가에게 도움을 받았으니 말이다 :)
☻ Reference
- https://www.amazon.com/Machine-Learning-Probabilistic-Perspective-Computation/dp/0262018020
- https://machinelearningmastery.com/no-free-lunch-theorem-for-machine-learning/
- https://grammarist.com/phrase/theres-no-free-lunch/
- https://en.wikipedia.org/wiki/There_ain%27t_no_such_thing_as_a_free_lunch
- https://towardsdatascience.com/what-no-free-lunch-really-means-in-machine-learning-85493215625d