오늘 당신은 점심으로 왠지 돈가스가 당깁니다. 회사 근처, 이미 가 본 적당한 맛집을 다시 가는 게 좋을까요, 아니면 평점이 높지만 가보지 못한 새로운 식당을 도전해 봐야 할까요? 모험과 안전 사이, 여러분의 고민을 단번에 해결해 줄 연구가 6월 1일 발표됐습니다. 50년 전 물리학자 리처드 파인먼이 음식 메뉴 선택을 위해 쓴 공식을 해독한 연구죠. 과학동아가 파인먼의 수학 해법을 따라 돈가스 맛집을 찾아봤습니다.
파인먼의 도움으로 돈가스 맛집을 찾아라
와자작. 한 입 베어물자 튀김옷이 바스러지면서 육즙이 입안 가득 배어 나옵니다. 바삭한 식감과 고기 감칠맛의 적절한 조화에 짜릿한 쾌감을 느끼며 미소를 짓습니다. 이 식당은 장효빈 기자가 찾은 광화문의 한 돈가스 맛집 ‘무○돈까스’입니다.
6월 24일, 장효빈 기자와 김태희 기자는 이창욱 편집장으로부터 카드를 받았습니다. 돈가스를 사랑하는 돈가스사이언스, 아니 과학동아 편집부를 위해 최고의 돈가스 맛집을 찾아내라는 임무를 받았죠. 두 기자에게 주어진 기간은 단 5일, 탐색 범위는 광화문 일대. 두 기자 사이에서 조용하고도 치열한 경쟁이 시작됐습니다. 바로 5일간 편집장 카드로 더 행복한 점심시간을 보내는 것입니다. 장 기자는 자신 있었습니다. 식당 선택의 비법을 손에 넣었기 때문입니다. 미국의 물리학자 리처드 파인먼이 약 50년 전 식당에서 점심을 먹다가 쓴 노트, ‘식당 난제(Restaurant Dilemma)’죠.
1970년대의 어느 날, 파인먼은 친구 랠프 레이턴과 점심을 먹다가 미국 캘리포니아의 단골 태국 음식점에 갔습니다. 파인먼은 레이턴이 늘시키던 생강 닭고기를 주문할지 새로운 음식을 시도할지 고민하는 모습을 보고 메모지를 꺼내 수학식을 써 내려갔습니다. 레이튼이 보관하다 후세에 남긴 이 메모는 2004년 미국의 물리학자 마이클 고틀리브에 의해 의미가 해석됐지만, 최적의 해법이 맞는지는 그동안 입증되지 않았습니다. 그런데 6월 1일, 톰 그리피스 미국 프린스턴대 컴퓨터학과 교수가 이끈 국제 공동연구팀이 파인먼의 메모가 식당 난제를 푸는 최적의 해법임을 증명하는 연구 결과를 국제학술지 ‘미국국립과학원회보(PNAS)’에 발표했습니다. doi: 10.1073/pnas.2509612123
결혼부터 맛집까지 해결하는 최적-정지 이론
기자는 논문을 들여다보며 파인먼의 해법을 독차지하기로 결심했습니다. 파인먼의 해법은 ‘최적-정지 이론’을 기반으로 합니다. 최적-정지 이론은 가장 유리한 결과를 얻기 위해 차례대로 주어지는 선택지를 언제까지 탐색하고, 언제 탐색을 멈춰야 할지 결정하는 수학 이론입니다.
“탐색을 지속한다는 건 더 좋은 선택이 남아 있을 것 같다는 믿음이 있을 때죠.” 6월 25일 서울대에서 만난 이다빈 수리과학부 교수는 최적-정지 이론과 파인먼 해법에 관한 해설을 이렇게 시작했습니다.
“예를 들면 ‘소개팅을 10번 한다고 했을 때, 몇 번째에 만난 사람이 가장 나와 성향이 잘 맞을 확률이 높을까?’ ‘몇 번째부터 소개팅을 멈추고 한 사람을 길게 만나 보는 게 좋을까?’ 같은 문제입니다. 주식 투자를 할 때도 언제까지 다양한 주식 종목에 투자를 하다가 정착하는 게 좋을지 고민할 때 적용할 수 있어요.”
파인먼 해법은 위에서 예로 든 일반적인 최적-정지 이론과 다른 3가지 전제 조건이 있습니다. 우선 모든 식당의 점수는 0~1점 사이에 분포돼 있고, 모든 점수가 균일하게 분포돼 있다고 가정합니다. 식당 한 곳을 고를 때 0.3점일 확률, 0.7점일 확률, 0.9점일 확률이 모두 같다는 뜻입니다. 그리고 한번 다녀온 식당은 다시 선택할 수 있습니다. 마지막으로 파인먼 해법의 목표는 최고의 식당 하나만 찾는 게 아니라는 점입니다. 매일매일 먹는 점심 메뉴의 만족도를 최대로 만드는 게 목표죠. 때문에 여러 날 동안 다녀온 식당 점수의 총합이 높아야 합니다.
이 전제 조건을 따라가면, 맛집 선택 과정에서 일어난 총 손실(이 집 돈가스 맛없네….) 대비 이득(어? 여기 맛있잖아?)이 커야 한다는 결론이 나옵니다. 연구팀은 n일 동안 탐색을 시도하거나 탐색을 멈출 때 각각 얻을 수 있는 기대값을 계산하고 비교해 봤습니다. 기댓값은 특정한 확률의 사건을 무한히 반복했을 때 평균적으로 얻을 수 있는 수치를 의미합니다. 예를 들어 마지막 날 새로운 식당을 찾을 때 평균 이상의 식당이 나올 확률은 50%이므로 기대값은 0.5점입니다. 그런데 마지막 날이 되기 전 이미 0.7점짜리 식당을 다녀왔고 이 식당을 다시 방문한다면 얻을 수 있는 점수 역시 0.7점이죠. 0.5점 기대값의 새로운 식당을 찾는 것보다 0.7점 식당을 다시 가는 게 훨씬 이득이라는 겁니다.
새로운 곳을 갈지 아는 맛집을 갈지 정하는 기준 기대값인 ‘임계값’은 내게 남은 날짜에 따라 달라집니다. 연구팀이 임계값을 n일로 일반화했더니 이라는 공식이 하나 도출됐습니다. 9일 동안 식당을 고른다고 가정하고, n에 9를 대입하면, 0.75가 됩니다. 선택 기간이 9일 남았을 때, 0.75점 이상인 식당이 나오면 탐색을 멈추고 그 식당만 가는 것이, 0.75점 미만이면 탐색을 더 하는 게 이득이라는 뜻입니다. 남은 일수인 n이 줄어들수록 임계값은 낮아져 하루 남았을 때(n=1) 임계값은 0.5가 됩니다. 0.5점 이상인 식당이 나왔으면 그 식당만 가라는 뜻이니, 기간이 적게 남을수록 기존 맛집을 다시 가야 한다는 결론이 나옵니다. 연구팀이 도출한 임계값은 놀랍게도 파인먼의 메모지에 쓰인 식과 같았습니다. 파인먼의 해법은 최적의 공식이 맞았던 셈이죠.
두 기자의 돈가스 대결, 결과는?
이 교수의 도움으로 파인먼의 비법을 얻은 장 기자는 돈가스 승부에 바로 이 공식을 활용하기로 마음먹었습니다. 파인먼 해법의 임계값을 넘는 순간 바로 식당을 그만 탐색하고 가던 식당을 또 가는 겁니다. 안타깝게도 파인먼 해법을 못 얻은 김 기자는 그만의 방법에 도전했습니다. 평소 맛집을 찾는 방법을 활용해 최대한 다양한 식당들을 5일 동안 다녀온 겁니다.
장 기자가 처음으로 방문한 ‘O 돈가스’는 튀김옷이 눅눅하지 않고, 고기가 적절히 잘 입혀졌습니다. 그러나 튀김옷이 너무 얇은 점이 아쉬워서 0.62점을 줬습니다. 공식에 4일을 대입하면 기준 점수(임계값)가 0.67점이 되기 때문에, 더 탐색을 해 보기로 했죠. 두 번째로 방문한 ‘H 돈가스’는 튀김옷이 아주 바삭해서 식감이 만족스러웠지만, 너무 두꺼운 튀김옷 때문에 기름이 많아 느끼해 직전 식당과 똑같은 점수 0.62점을 줬습니다. 3일이 남은 시점, 임계값은 0.63점이기 때문에 아직도 점수 미달입니다.
무○돈까스에 방문한 3일 차, 장 기자는 꿈에 그리던 돈가스를 만났습니다. 바삭한 튀김옷과 적절히 새 나오는 육즙, 그리고 느끼함을 잡아줄, 톡 쏘는 소스. 장 기자는 박수를 치며 0.89점을 줬습니다. 이틀이 남은 시점, 기준 점수인 0.59점을 훌쩍 뛰어넘었기 때문에 마지막 이틀은 무○돈까스를 연달아 다시 반복했습니다. 두 번의 0.62점, 그리고 3번의 0.89점. 총 점수는 3.91점이었습니다.
반대로 탐색을 최대화한 김 기자는 첫날부터 비교적 만족스러운 식당을 찾았습니다. ‘A 돈가스’는 돈가스 육즙과 씹는 맛이 일품이었고, 소스도 다양했습니다. 다만 식을수록 고기가 퍽퍽해지는 점이 아쉬워 0.8점을 줬습니다. 이틀차에 방문한 ‘J 돈가스’는 아주 부드러운 고기에 다양한 소스, 적절한 밑간에 감탄했습니다. 김 기자는 0.88점을 줬습니다. 셋째 날에 방문한 ‘M 돈가스’는 퍽퍽한 고기 탓에 육즙을 느낄 수 없어 0.57점을 줬습니다. 네 번째 시도 때 튀김옷이 바삭하고 육즙이 환상적인 돈가스를 찾아 무려 0.9점을 줬습니다(그는 현재 과학동아 팀원들에게 이곳을 꼭 방문해 보라 권하고 있죠). 마지막 날 0.65점을 주면서, 총합 점수는 3.8점이었습니다. 파인먼 해법을 손에 얻은 장 기자의 승리였죠.
두 기자의 돈가스 대결
파인먼 해법을 현실적으로 풀어내다
파인먼의 해법을 실제로 검증할 수 있었던 실험이었습니다. 다만 두 기자의 점수 차는 0.11점에 불과했습니다. 이 교수와 함께 실험 과정과 결과를 분석해 봤습니다. 이 교수는 “세 가지 원인 때문에 돈가스 승부에 변수가 있었다”고 설명했습니다. 파인먼 해법으로도 풀 수 없던 변수가 있었죠.
첫째, 두 기자의 입맛이 달라 각각 매긴 점수의 표준화가 이루어지지 않았을 가능성이 있습니다. 두 기자는 똑같은 기준을 토대로 돈가스 맛의 점수를 매겼지만, 각 기준의 ‘선’이 달랐습니다. 쉽게 말해 장 기자가 더 깐깐히 식당을 평가했을 가능성이 있다는 거죠.
두 번째, 식사 기회 수인 n이 5로 적기도 합니다. 이 교수는 “파인먼 해법은 초반에 탐색해 좋은 선택지를 찾고, 그동안 탐색한 곳 중 좋은 선택지를 고르고 누리는 게 핵심인데, 5일은 탐색에 허비한 시간을 만회하기 부족하다”고 설명했습니다. “기간이 늘어나면 탐색한 식당 중 맛있는 곳에 다시 방문할 기회 역시 많아져 평균 만족도가 높아질 수 있습니다.” 따라서 편집장이 30일 동안 돈가스를 사 먹도록 카드를 줬다면, 장 기자가 더 큰 점수차로(물론 그전에 돈가스에 질렸겠지만요) 이겼을 겁니다.
마지막으로, 파인먼 해법의 전제 조건과 달리 광화문의 식당 별점 분포는 균등하지 않았습니다. 두 기자는 모두 인공지능(AI), 지도앱의 별점과 후기로 식당 후보를 추렸습니다. 이들은 이미 어느 정도 높은 점수일 확률이 높은 식당들입니다. 그리고 식당들 간의 점수가 비슷할 가능성이 높죠.
분포가 달라지면 선택도 달라져야 할까요? 논문에서 연구팀은 파인먼의 해법을 균등 분포가 아닌 세 가지 조건에 적용해 봤습니다. 첫 번째는 낮은 점수가 많고 높은 점수가 거의 없는 분포, 두 번째는 중간 점수가 많지만 아주 높은 점수가 나올 확률이 미미하게 존재하는 분포, 그리고 세 번째는 유독 특정 점수(주로 80점)가 나올 확률이 높은 분포였습니다.
연구팀은 각 분포에 해당하는 그래프 공식에 파인먼의 조건을 반영해 계산해 봤습니다. 그 결과, 균등 분포에서 계산한 파인먼 해법과 다른 임계값이 도출됐습니다. 첫 번째와 두 번째 분포는 임계값이 균등 분포에 비해 더 높았습니다. 확률이 낮더라도 예상한 범위를 뛰어넘는 뛰어난 식당이 나올 가능성이 존재하기 때문이죠. 이 교수는 “상방(상승할 여력)이 높은 구조이기에 고만고만한 식당이 아닌, 엄청 맛있는 식당이 나올 수 있는 기대감에 공격적인 선택이 가능하다”고 설명했습니다. 이때 100점에 가까운, 아주 높은 점수가 나올 확률이 존재하는 두 번째 분포에서 특히 더 많은 탐색을 시도하는 게 이득이었죠.
특정 점수에 분포가 쏠려 있는 세 번째 분포에서는 반대로 다른 분포에 비해 임계값이 낮았습니다. 예를 들어 0.8점 식당을 찾았다면, 해당 분포가 0.8점에 쏠려 있을 가능성이 높아 추가로 탐색을 해도 0.8점과 유사한 점수일 가능성이 높기에 탐색을 빠르게 멈추는 게 이득입니다. 과학동아가 시도한 맛집의 후보군은 점수가 높은 식당일 확률이 높다는 점에서 세 번째 분포와 닮았습니다.
파인먼 공식, 현실에서 어떻게 사용할까?
❷ 임계값을 뛰어넘기 전까지는 계속 다른 메뉴를 도전한다.
❸ 임계값을 뛰어넘는 점수가 나오면, 같은 메뉴(케이크)를 계속 먹는 게 20일간의 음식 만족도를 가장 높이는 방법이다.
※ 케이크를 매일 먹으면 질리겠지만, 이러한 한계까지 파인먼 해법이 고려하지는 않는다.
맛집 탐방을 넘어 알고리즘 개발까지
이번 연구팀의 논문은 파인먼의 해법이 효율적이라는 사실을 알아낸 데 그치지 않습니다. 연구팀은 파인먼의 해법이 사람의 행동 본능과도 관련이 있을지 간단한 실험을 진행했습니다. 실험 참가자 2520명을 대상으로 7일, 14일, 28일 동안 가상의 도시에서 식당을 선택하는 실험을 진행했습니다. 파인먼 해법과 선택 양상이 동일하지는 않았지만, 실제로 이들은 초반에는 탐색을 다양하게 하다가, 후반으로 갈수록 이미 간 식당에 정착하는 경향을 보였습니다. 인간은 고도의 수학 계산을 하지 않고, 감으로도 이익을 최대화하기 위한 선택을 했고, 그 전략이 파인먼 해법과 유사했습니다.
연구팀이 파고든 파인먼 해법, 그리고 파인먼 해법을 포함하는 최적-정지 이론은 점심 메뉴를 고를 때만 유용한 게 아닙니다. 이 교수는 대표적인 사례로 “유튜브의 콘텐츠 시스템이 최적-정지 이론을 따른다”고 설명했습니다. “유튜브 추천 시스템은 사용자의 취향을 모를 때는 최대한 다양한 영상을 추천하다가, 사용자의 만족도에 대한 정보가 많이 쌓인 뒤로는 점점 이미 본 영상과 비슷한 영상을 추천해 주죠. 유튜브 시스템뿐 아니라 다양한 플랫폼의 추천 알고리즘 원리에 활용될 수 있어요.”
최적-정지 이론은 강화학습의 근간이 되기도 합니다. “알파고가 바둑을 둘 때 이런 수도 두고 저런 수도 두다가 반복적인 피드백을 반영해, 결국 가장 좋은 수를 고르는 것도 최적-정지 이론이 반영된 예입니다. AI를 학습시킬 때도 같은 아이디어를 사용하죠.”
수학 난제를 푸는 AI를 개발할 때도 마찬가지입니다. 수학 난제 풀이에는 대수학과 조합론 등 다양한 분야를 아우르는 탐색과 추론이 필요합니다. 어디까지 탐색이 필요할지, 어떤 풀이 전략이 가장 최적화된 방식일지 찾을 때도 최적-정지 이론이 반영되죠. “AI 모델의 추론 규모가 점점 커지고, 해결이 필요한 문제는 점점 고도화되고 있기 때문에 최적-정지 이론 역시 고도화가 필요합니다.”
파인먼 해법을 따라 식사해 보니, 개인적으로는 무언가를 선택하는 데 있어서 명확한 기준이 마련돼 있다는 사실에 편안함을 느꼈습니다. 임계값을 넘는 점수의 식당을 찾은 날에는 앞으로 맛 없는 돈가스를 먹을 위험을 감수하지 않아도 된다는 생각에 안심하기도 했죠. 한편, 맛집을 찾아나설 때 얻는 호기심, 그리고 미래를 알 수 없을 때 느끼는 적당한 긴장감을 느낄 수 없었습니다. 여행과 모험만이 지닌 묘미가 사라진 기분이랄까요. 수학 이론을 적용한 편리함에, 수학이 한정지을 수 없는 인간만의 실패의 영역이 적당히 더해졌을 때 진정한 선택의 ‘만족도’가 높아짐을 알려준 실험이었습니다.
