타로, 비터비, LLM의 공통점: 하나의 의미를 선택하는 알고리즘

Habr에 게재된 이 글은 타로 카드 해석을 여러 후보 중에서 가장 일관성 있는 의미 경로를 선택하는 문제로 모델링할 수 있음을 탐구하며, 이를 비터비(Viterbi) 알고리즘이나 빔 서치(beam search)와 같은 알고리즘에 유비한다. 저자는 카드가 맥락(context)과 고유 의미(native meaning)를 여러 가능한 해석의 집합으로 매핑하는 함수 역할을 한다는 아이디어에서 출발하지만, 탐색의 단위가 단일 해석이 아니라 전체 의미 경로(semantic path)여야 한다고 주장한다. 다섯 가지 상태(정체, 재고, 자원, 행동, 전환)와 세 장의 카드(행맨, 마법사, 전차)를 사용한 구체적인 예시는, 탐욕적(greedy) 접근법이 비터비의 전역 최적(global optimum)에 비해 차선의 경로를 선택함을 보여준다. 이 형식적 모델은 조건부 비균질 마르코프 체인(conditional inhomogeneous Markov chain)으로, 비터비 디코딩은 O(n*S^2) 시간 안에 정확한 최대 경로를 찾아낸다. 그러나 점수가 전체 이력이나 자유 텍스트에 의존하게 되면 최적 부분 구조(optimal substructure)가 성립하지 않게 되며, 이 경우 근사적 방법으로 빔 서치가 사용되고, 다양성 빔 서치(diverse beam search)도 함께 논의된다. 이 글은 비터비, 빔 서치, 다양성 빔, A*, MCTS(몬테카를로 트리 탐색), LLM(대규모 언어 모델) 재랭킹(reranking)을 비교하며, 더 일반적인 형식화로서 팩터 그래프(factor graph)와 선형 체인 조건부 무작위장(linear-chain CRF, Conditional Random Field)을 언급한다. 또한 실제 의미들이 이산적인 상태에 딱 들어맞지 않을 수 있다는 점을 지적하며, 이를 위해 의미 임베딩 벡터(semantic embedding vector)와 LLM 재랭킹을 활용할 수 있다고 제안하고, 이러한 예시를 AI 지원 타로 실천에 관한 연구로 발전시킬 수 있는 방향들을 제시한다.