🤖 machine learning

Estimation, Prediction, and Assortment Optimization for Markov Chain Choice Models with Panel Data

이 논문은 패널 데이터를 활용한 마르코프 체인 선택 모델을 위한 새로운 프레임워크를 소개하며, 이는 매개변수 추정을 위한 우수한 EM 알고리즘을 개발하기 위해 부분 순서 선호 정보를 활용하는 동시에, 개인화된 선택 예측 및 어소트먼트 최적화의 계산 복잡도를 규명한다.

원저자: Yalcin Akcay, Gerardo Berbeglia, Young-San Lin

게시일 2026-07-14

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yalcin Akcay, Gerardo Berbeglia, Young-San Lin

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 사람들이 실제로 무엇을 좋아하는지 알아내려는 탐정이라고 상상해 보세요. 옛날의 탐정들은 레스토랑의 거대한 영수증 더미를 살펴보곤 했습니다. 그들은 모든 주문이 마치 동전 던지기처럼 새롭고 독립적인 추측이라고 가정했습니다. 만약 누군가 스시를 주문하고, 그다음에 피자를, 그다음에는 버거를 주문했다면, 기존의 수학 방식은 이 세 가지 선택을 서로 연결되지 않은 세 개의 별개 사건으로 취급했습니다.

하지만 여기 반전이 있습니다. 사람들은 동전이 아닙니다. 만약 한 고객이 매운 참치 롤을 주문하고, 나중에 다시 매운 참치 롤을 주문했다면, 그것은 하나의 단서가 됩니다! 이는 그들이 정말로 매운 참치를 좋아한다는 것을 암시합니다. 이 논문은 이러한 "영수증"(저자들이 패널 데이터라고 부르는 것)을 보는 새로운 방법을 제시합니다. 즉, 영수증을 무작위로 쌓인 종이 더미가 아니라, 각 특정 고객을 위한 연결된 이야기로 취급하는 것입니다.

새로운 탐정 도구: 마르코프 체인 (Markov Chain)

저자들은 마르코프 체인(MC) 선택 모델이라는 특정 수학 도구를 제안합니다. 이 모델을 "선호도 지도"라고 생각해보세요. 단순히 "나는 스시를 좋아해"라고 말하는 대신, 이 모델은 여정을 그려냅니다. 이 모델은 다음과 같이 묻습니다: "만약 내가 현재 스시에 대해 생각하고 있다면, 다음에 무엇을 생각할 가능성이 높은가? 사시미로 넘어갈 것인가, 아니면 포기하고 탄산음료를 주문할 것인가?"

이 논문의 큰 발견은, 고객의 이력(패널 데이터)이 있을 때 이 "여정" 지도를 훨씬 더 정확하게 그릴 수 있다는 점입니다. 저자들은 시뮬레이션(컴퓨터 실험)을 실행하고, 5,000명의 스시 선호도가 담긴 실제 데이터셋을 통해 그들의 방법을 테스트했습니다. 그 결과, 고객의 이력을 사용하여 지도를 업데이트함으로써 그들의 새로운 알고리즘(Cus와 Hyb)이 기존 방식보다 사람들이 다음에 무엇을 살지 예측하는 데 훨씬 더 뛰어나다는 것을 발견했습니다.

기존 방식의 오류

이 논문은 단일 고객의 과거 주문 사이의 연결성을 무시해도 된다는 생각에 명시적으로 반박합니다.

"독립성"의 신화: 저자들은 만약 모든 주문을 완전히 새롭고 무작위적인 사건으로 취급한다면(전통적인 방식), 선호도의 "부분적 순서(partial ordering)"를 놓치게 된다는 것을 보여줍니다. 이는 마치 어떤 사람이 본 영화들의 목록을 볼 때, 그가 모든 속편을 순서대로 봤다는 사실을 깨닫지 못한 채 단순히 무작위로 본 영화 리스트만 보고 그 사람의 인생 영화를 맞추려는 것과 같습니다.
MNL의 함정: 매우 대중적이고 더 단순한 모델인 다항 로짓(Multinomial Logit, MNL) 모델이 있습니다. 이 논문은 이 특정 모델의 경우, 고객의 이력을 살펴보는 것이 전체 영수증 더미를 보는 것보다 일반적인 인구의 선호도를 파악하는 데 도움이 되지 않는다는 것을 증명합니다. 하지만 그들이 사용하는 마르코프 체인 모델의 경우에는 이력이 엄청난 차이를 만들어냅니다. 이는 "어떤 종류의 수수께끼냐에 따라 단서를 순서대로 보는 것이 도움이 되기도 하고, 그렇지 않기도 하다"는 말과 같습니다.

"하이브리드" 탐정

저자들은 또한 Hyb라는 "하이브리드" 탐정 도구를 만들었습니다. 현실 세계에서 고객의 이력은 때때로 엉망일 수 있습니다. 예를 들어, 어떤 고객이 버거를 주문했다가, 그다음엔 샐러드를, 그다음엔 다시 버거를 주문하는 식으로 완벽한 논리적 선(순환 구조)을 이루지 못할 수도 있습니다.

Cus 알고리형은 엄격합니다. 고객의 이력이 완벽하고 논리적인 선의 형태를 띨 때만 작동합니다.
Hyb 알고리즘은 유연합니다. 이 알고리즘은 이력 중 엉망이고 비선형적인 부분은 "독립적인" 데이터 포인트로 취급하는 동시에, 깔끔하고 논리적인 부분은 연결된 이야기로 유지합니다. 이를 통해 모델이 혼란에 빠지지 않고 모든 데이터를 사용할 수 있게 해줍니다.

얼마나 잘 작동했는가?

저자들은 단순히 추측한 것이 아니라 측정했습니다.

설정: 그들은 합성 데이터(가상의 고객)를 사용하여 2,000개의 서로 다른 테스트 시나리오를 만들었으며, 또한 5,000명의 개인을 포함한 스시 데이터셋에서도 테스트했습니다.
결과: 시뮬레이션에서 새로운 방식들(Cus 및 Hyb)은 일관되게 기존 방식들을 앞질렀습니다.
- 데이터가 적었을 때(고객 100명뿐일 때), 새로운 방식들이 사람들이 무엇을 살지 예측하는 데 훨씬 더 뛰어났습니다.
- 고객 수가 2,000명으로 늘어남에 따라, 새로운 방식들은 특히 특정 고객의 선택을 예측하는 데 있어 기존 방식들을 계속해서 능가했습니다.
- 수익 측면에서, 새로운 방식들은 소매업자들이 어떤 품목을 전시할지 결정하는 데 도움을 주었습니다. 예를 들어, 스시 테스트에서 새로운 모델들은 많은 경우에서 가능한 최대 수익의 거의 **100%**에 달하는 성과를 거둔 반면, 기존 모델들은 뒤처졌습니다.

핵심 요약

이 논문은 만약 당신이 사람들이 무언가를 선택하는 방식을 이해하고 싶다면, 단순히 "무엇을"(제품) 보는 것이 아니라 "이야기"(이력)를 보아야 한다고 제안합니다. 고객의 과거 선택을 무작위적인 사건이 아닌 연결된 여정으로 취급함으로써, 훨씬 더 정교한 선호도 지도를 구축할 수 있습니다. 저자들은 이러한 접근 방식이 마르코프 체인 모델을 사용할 때 가장 효과적이라는 것을 발견했으며, 이를 통해 엉망인 영수증 더미를 고객이 다음에 무엇을 원할지에 대한 명확하고 개인화된 가이드로 바꿀 수 있었습니다.

기술 요약: 패널 데이터를 활용한 마르코프 체인 선택 모델의 추정, 예측 및 구색 최적화

문제 정의

전통적인 구색 계획(assortment planning)은 과거의 거래가 무작위 효용 모델(random utility model, RUM)로부터 독립적이고 동일하게 분포된(i.i.d.) 표본이라는 가정하에 선택 모델에 의존합니다. 이 프레임워크는 개별 고객 간의 거래 상관관계를 무시하고 무조건적 선택 확률을 활용합니다. 그러나 패널 데이터(상세한 개인별 거래 이력)의 가용성은 이러한 독립성 가정에 도전 과제를 제기합니다.

본 논문은 마르코프 체인(Markov Chain, MC) 선택 모델의 맥락에서 패널 데이터를 사용하여 세 가지 핵심 문제를 다룹니다:

파라미터 추정: 거래를 독립적인 것으로 취급하는 대신, 고객 특유의 과거 거래 정보(부분 순서 선호도)를 통합하여 MC 파라미터를 어떻게 추정할 것인가?
조건부 선택 예측: 특정 고객의 과거 거래 이력을 조건으로 하여, 해당 고객이 주어진 오퍼 세트에서 특정 제품을 선택할 확률을 어떻게 계산할 것인가?
구색 최적화: 특정 고객의 이력을 고려했을 때, 기대 수익을 극대화하기 위해 해당 고객에게 제공할 최적의 제품 세트를 어떻게 결정할 것인가(조건부 구색 최적화)?

저자들은 패널 데이터를 활용하는 것이 MNL(다항 로짓) 모델 및 전통적인 추정 방식과 비교했을 때 MC 모델의 모집단 수준 추정 성능을 개선하는지 조사합니다.

방법론

이론적 프레임워크

저자들은 **부분 순서 선호 정보(partial-ordering preference information)**를 사용하여 문제를 공식화합니다. 고객의 거래 이력 $D_c$ 는 관찰된 선택으로부터 파생된 쌍별 선호도를 나타내는 유향 비순환 그래프(Directed Acyclic Graph, DAG)로 표현됩니다.

조건부 확률: 세트 $S$ 에서 선택 $j$ 를 할 확률은 축소 선형 확장(reduced linear extensions)(관찰된 DAG와 일치하는 엄격한 순위)을 사용하여 도출됩니다.
MC vs. MNL: 본 논문은 MC와 MNL 사이의 이론적 격차를 확립합니다. MNL 하에서는 모집단 선택 확률이 알려져 있다면 패널 데이터가 파라미터 식별력을 높이는 데 기여하지 못합니다. 반면, MC의 경우, 고객 수준의 정보는 특히 관찰된 구색 세트가 제한적인 상황에서 파라미터 식별력을 크게 향상시킵니다.

알고리즘: 기대-최대화(Expectation-Maximization, EM)

본 논문의 주요 기여는 패널 데이터를 사용하여 MC 파라미터( $\lambda$ : 초기 상태, $\rho$ : 전이 확률)를 추정하기 위한 새로운 EM 알고리즘을 개발하는 것입니다.

Algorithm Cus (고객 특화형):
- 가정: 각 고객의 거래 세트는 적어도 하나 이상의 엄격한 선호 리스트(사이클 없음)와 일치합니다.
- 메커니즘: 이 알고리즘은 고객의 기저에 깔린 엄격한 선호(축소 선형 확장 $\sigma$ 로 표현됨)와 초기 상태를 잠재 변수로 취급합니다.
- E-단계(E-Step): 관찰된 DAG와 현재 파라미터 추정치를 조건으로 하여 잠재 변수(초기 상태 지표 및 전이 횟수)의 기댓값을 계산합니다. 이는 축소 선형 확산과 일치하는 랜덤 워크(random walks)의 확률을 계산하는 과정을 포함합니다.
- M-단계(M-Step): 기대 완전 데이터 로그 가능도(expected complete-data log-likelihood)를 최대화하여 파라미터 $\lambda$ 와 $\rho$ 를 업데이트하며, 이는 기대 횟수에 기반한 폐쇄형 해(closed-form solutions)를 가집니다.
Algorithm Hyb (하이브리드형):
- 동기: 실제 데이터에는 DAG를 위반하는 순환적 선호나 불일치하는 거래가 포함될 수 있습니다.
- 메커니즘: Hyb는 Cus 알고리즘(DAG와 일치하는 거래용)과 전통적인 EM 알고리즘(독립적인 거래용)을 결합합니다.
- 유연성: "위반"하는 거래(사이클을 유발하는 거래)를 단순히 버리는 대신, 전통적인 가능도 구성 요소의 독립적 관측치로 취st하여 무조건적 모집단 분포에 대한 정보를 포착하면서도 일관된 이력에 대한 DAG 구조를 활용할 수 있게 합니다.

계산 복잡도

본 논문은 조건부 선택 예측 및 구색 최적화에 대한 난해도(hardness) 결과를 제시합니다. 전통적인 MC 하의 구색 최적화는 다항 시간 내에 해결 가능하지만, 조건부 버전(CAO 및 TCAO)은 계산적으로 까다로운 것으로 나타났습니다. 그러나 저자들은 일반적인 RUM에 비해 계산 부담을 줄여주는 MC 하의 조건부 선택 확률에 대한 폐쇄형 표현식을 제공합니다.

주요 기여

MC 패널 데이터 연구의 개시: 저자들이 아는 바로는, 마르코프 체인 모델 하에서 패널 데이터를 통한 선택 모델링을 연구한 최초의 프레임워크입니다.
새로운 EM 알고리즘: 부분 순서 기반의 고객 선호 정보를 통합하는 Cus 및 Hyb 알고리즘을 제안했습니다. 이 알고리즘들은 전통적인 MC 추정 방식(S¸im¸sek and Topaloglu, 2018) 및 MNL 기반의 부분 순서 벤치마크(Jagabathula and Vulcano, 2018)보다 우수한 성능을 보입니다.
이론적 식별 격차: MNL 파라미터는 (충분한 구색 데이터가 주어지면) 거래를 특정 고객과 연결하지 않고도 식별될 수 있는 반면, MC 파라미터는 특히 관찰된 구색 데이터가 제한적인 시나리오에서 패널 데이터로부터 큰 이득을 얻는다는 점을 입증했습니다.
계산적 지형: MC 및 MNL 하에서의 조건부 선택 예측 및 구색 최적화에 대한 계산적 난해함과 트랙터빌리티(tractability)를 명확히 하여, 추정 프레임워크를 보완했습니다.

실험 결과

저자들은 합성 데이터셋과 스시 선호도 데이터(5,000명)에서 유도된 준합성 데이터셋을 통해 방법론을 평가했습니다.

성능 지표: 예측 정확도를 위해 Soft RMSE를 사용하였고, 의사결정 성능을 위해 수익 비율(Revenue Ratios)을 사용했습니다.
합성 데이터:
- 제안된 Cus-MC 및 Hyb-MC 모델은 특히 고객 수가 증가함에 따라 전통적인 MC 추정, MNL, 그리고 LC-MNL(잠재 클래스 MNL) 변형 모델보다 일관되게 우수한 성능을 보였습니다.
- 이러한 개선은 실제 분포가 더 적은 수의 선호 리스트에 집중되어 있을 때(예: 10개의 리스트를 가진 Rank List 또는 높은 집중도를 가진 Mallows 분포) 더욱 두드러졌습니다.
- 패널 데이터의 통합은 MNL 추정보다 MC 추정에서 더 큰 개선 폭을 보였으며, 특히 데이터 크기가 작을 때 그러했습니다.
스시 데이터:
- MC 기반 모델이 MNL 기반 모델보다 수익 비율과 예측 정확도 면에서 일반적으로 우수했습니다.
- Hyb-MC와 Cus-MC는 대부분의 시나리오에서 최적에 가까운 기대 수익을 달ach했습니다.
- "Top 5" 절단 시나리오에서 데이터 크기가 커질수록 조건부 수익 성능이 저하되는 예외 상황이 관찰되었는데, 이는 제한된 거래 깊이(관찰된 상위 선택지가 적음)가 패널 데이터만으로 복잡한 MC 구조를 적합시키는 능력을 제한할 수 있음을 시사합니다.

의의 및 주장

본 논문은 고객 수준의 정보가 MNL 추정보다 마르코프 체인 추정에 더 가치 있다고 주장합니다. 개별 거래 이력의 상관관계를 체계적으로 활용함으로써, 제안된 프레임워크는 예측 정확도와 구색 최적화 성능을 모두 향상시킵니다.

저자들은 다음과 같은 점을 언급하며 본 연구의 기초적 역할을 강조합니다:

이 프레임워크는 전통적인 독립 거래 모델과 상관관계가 있는 고객 행동의 현실 사이의 간극을 메웁니다.
Hyb 알고리즘은 선호도가 순환적일 수 있는 실제 데이터셋에 대한 실용적인 휴리스틱을 제공하여, 엄격한 DAG 기반 휴리스틱에 의해 버려질 수 있는 정보를 유지할 수 있게 합니다.
향-후 연구로는 순환적 선호가 존재하는 실제 데이터에 대한 알고리즘 테스트와 다른 종류의 무작위 효용 모델(RUM)로의 프레임워크 확장이 포함됩니다.

논문은 합성 결과가 강력함에도 불구하고, 순환적 선호에 대한 실제 검증(특히 실제 데이터에서의 검증)이 여전히 필요한 미래 방향임을 인정하며 신중한 태도를 유지합니다. 모든 맥락에서 모든 모델보다 보편적으로 우월하다고 주장하는 것이 아니라, 제안된 방법론이 뚜렷한 이점을 제공하는 특정 조건(MC 모델, 제한된 구색, 패널 데이터 가용성)을 강조하고 있습니다.