기술 요약: 이커머스 마케팅 캠페인을 위한 제약 조건이 있는 사용자-아이템 할당

문제 정의: 오토 타겟팅(Auto-Targeting)

본 논문은 이커머스 마케팅에서 발생하는 조합 할당 문제인 오토 타겟팅을 다룹니다. 아이템 선택과 사용자 할당을 분리하거나 미리 정의된 캠페인 구조를 가정하는 기존 방식과 달리, 본 연구는 이 문제를 결합 최적화(joint optimization) 작업으로 정식화합니다. 목표는 다음과 같은 조건을 만족하도록 사용자 집합과 아이템 집합을 $K$개의 서로소인 캠페인(그룹)으로 동시에 분할하는 것입니다:

1. 응집도(Cohesion): 각 캠페인은 할당된 사용자와 아이템 사이의 총 내부 그룹 친밀도(within-group affinity)를 극대화합니다.
2. 상호 배타성(Disjointness): 모든 사용자와 아이템은 최대 하나의 캠페인에만 포함됩니다.
3. 제약 조건(Constraints): 각 캠페인은 고정된 수의 아이템($I$)과 특정 범위 내의 사용자 수($\tau_{min} \le |U_k| \le \tau_{max}$)를 포함해야 합니다.

사용자와 아이템 사이의 친밀도는 (클릭이나 구매와 같은 과거 상호작용으로부터 학습된) 공유 임베딩 공간으로부터 도출되며, 여기서 근접성은 상호 간의 관심을 나타냅니다. 목적 함수는 모든 캠페인에 걸친 친밀도의 합을 극대화하는 것을 목표로 합니다:
$$\max_{\{I_k, U_k\}_{k=1}^K} \sum_{k=1}^K \sum_{i \in I_k} \sum_{u \in U_k} \text{affinity}(i, u)$$

이 공식은 지수적으로 증가하는 탐색 공간과 결합된 제약 조건들로 인해 계산적으로 매우 까다로우며, 대규모 데이터셋에 대해 정확한 해를 찾는 것을 불가능하게 만듭니다.

방법론

저자들은 시뮬레이티드 어닐링(Simulated Annealing, SA)을 베이스라인으로 하여, 이 문제를 해결하기 위한 세 가지 상호 보완적인 휴리스틱 전략을 제안합니다:

1. 제약 조건이 있는 스펙트럴 바이클러스터링 (Constrained Spectral Biclustering)

이 접근 방식은 스펙트럴 코-클러스터링(spectral co-clustering)을 변형하여 사용자-아이템 친밀도 행렬 내의 밀집된 영역을 식별합니다.

• 오버샘플링(Oversampling): 다양한 후보 풀을 확보하기 위해 처음에 $k' = \alpha k$ 개의 바이클러스터를 계산합니다 ($\alpha \ge 2$).
• 프루닝(Pruning): 크기 제약 조건을 충족하기 위해 후보를 제거합니다. 최대 크기에 도달할 때까지 바이클러스터 내의 평균 친밀도를 기준으로 아이템과 사용자를 순차적으로 제거합니다.
• 선택(Selection): 남은 후보들을 밀도(평균 친밀도)에 따라 순위를 매기고, 상위 $k$개의 중복되지 않는 바이클러스터를 최종 캠페인으로 선택합니다.

2. 멀티 암드 밴딧 (Multi-Armed Bandit, MAB) 최적화

이 방법은 캠페인을 밴딧 프레임워크에서의 "팔(arm)"로 취급하며, 착취(exploitation, 엔티티를 높은 친밀도를 가진 캠방에 할당)와 탐색(exploration) 사이의 균형을 맞춥니다.

• 결합된 보상(Coupled Rewards): 보상은 내생적입니다. 특정 엔티티의 캠페인에 대한 친밀도는 해당 캠페인의 현재 구성에 따라 달라집니다.
• 전략: 저자들은 두 가지 탐색 보너스를 구현합니다:
  • UCB1: 친밀도 점수에 신뢰 구간(confidence bound)을 더합니다.
  • 톰슨 샘플링(Thompson Sampling): 캠페인이 더 많은 할당을 받을수록 줄어드는 가우시안 노이즈를 사용하여 점수를 섭동(perturb)시킵니다.
• 메커니즘: 알고리즘은 변화하는 캠페인 구성에 적응하기 위해 지수 감쇠를 사용하는 롤링 윈도우 통계량을 사용하여 사용자 및 아이템 할당 단계를 교대로 수행합니다.

3. 그리디 로컬 서치 (Greedy Local Search)

이 전략은 용량 제약이 있는 그리디 절차를 수행한 후 정교화 과정을 거칩니다.

• 그리디 할당: 엔티티들은 잠재적 이득이 높은 순서대로 처리되며, 최대 점수 개선을 기준으로 캠페인에 할당됩니다.
• 쌍 교환(Pairwise Swaps): 로컬 서치 단계에서는 서로 다른 캠페인 간의 엔티티 교환을 평가하여 지역 최적해(local optima)를 탈출합니다. 만약 교환이 실행 가능성을 유지하면서 목적 함수를 개선한다면 실행됩니다.
• 반복: 이 과정은 정해진 반복 횟수 동안 사용자 업데이트와 아이템 업데이트를 교대로 수행합니다.

베이스라인: 순차적 시뮬레이티드 어닐링 (Sequential Simulated Annealing)

저자들은 시뮬레이티드 어닐링(SA)을 베이스라인으로 사용합니다. 전체 문제를 $K$개의 순차적인 하위 문제로 분해합니다. 각 캠페인에 대해, SA는 최적의 바이클러스터를 근사하기 위해 온도 제어 수락 확률을 사용하는 확률적 로컬 서치(추가, 제거, 교환 연산 사용)를 수행합니다.

주요 기여

1. 오토 타겟팅의 정식화: 본 논문은 기존 방식들이 일반적으로 한쪽의 할당을 고정하는 것과 달리, 캠페인 구조와 사용자-아이템 할당을 동시에 추론하는 새로운 결합 최적화 문제를 정의했습니다.
2. 알고리즘 적응: 저자들은 결합된 환경에서의 상호 배타적 커버리지 및 용량 제한을 처리하기 위해 세 가지 뚜렷한 접근 방식(제약 조건이 있는 스펙트럴 바이클러스터링, 그리디 로컬 서치, 멀티 암드 밴딧)을 적응시켰습니다.
3. 포괄적인 평가: 제안된 방법들은 세 가지 서로 다른 데이터 소스에 대해 평가되었습니다:
   • 합성 데이터(Synthetic Data): 알려진 그라운드 트루스 구조를 가진 통제된 환경.
   • 공개 벤치마크: Amazon Reviews 데이터셋 (Baby Products, Musical Instruments).
   • 독점 데이터: 대규모 상업용 데이터셋 (IKEA, Interior Design).

결과 및 성능

평가는 유틸리티(Utility) (총 친밀도), 품질(Quality) (평균 친밀도), 리프트(Lift) (무작위 할당 대비 개선도), 그리고 지니 계수(Gini Coefficient) (사용자 간 유틸리티 분포)를 포함한 지표를 활용합니다.

• 솔루션 품질: 제약 조건이 있는 스펙트럴 바이클러스링은 모든 데이터셋에서 리프트, 품질 및 공정성(가장 낮은 지니 계수) 측면에서 일관되게 가장 높은 점수를 기록했습니다. 이는 구조가 노이즈가 많거나 겹쳐져 있는 경우에도 일관된 고친밀도 영역을 복구하는 데 특히 효과적입니다.
• 확장성 vs 품질 트레이드오프:
  • 바이클러스터링은 작은 데이터셋에서는 매우 효율적이지만, 친밀도 행렬이 커짐에 따라 계산 비용이 급증합니다 (예: IKEA에서 Interior Design으로 갈 때 실행 시간이 1.2분에서 66.2분으로 증가).
  • 밴딧 기반 방법(UCB1 및 톰슨 샘플링)은 매우 큰 규모의 데이터셋에서 경쟁력 있는 성능을 유지하면서도 훨씬 낮은 실행 시간을 제공하는 확장 가능한 대안이 됩니다.
  • 그리디 로컬 서치는 반복적인 로컬 서치 단계로 인해 일반적으로 밴딧 방법보다 느립니다.
• 베이스라인 성능: 시뮬레이티드 어닐링은 솔루션 품질 면에서 제안된 방법들보다 현저히 떨어지며 가장 높은 계산 비용을 발생시킵니다 (종종 몇 시간이 소요됨). 저자들은 이를 고차원 조합 공간에서 단일 엔티티 이동을 통해 의미 있는 진전을 이루기가 어렵기 때문이라고 설명합니다.

의의 및 주장

본 논문은 사용자-아이템의 결합 구조를 명시적으로 모델링하는 것이 효과적인 캠페인 설계를 위해 필수적이라고 주장합니다. 결과는 다음을 시사합니다:

• 결합 최적화의 우월성: 아이템 선택을 사용자 할당으로부터 분리하면 결합 최적화를 통해서만 나타나는 그룹들을 놓치게 됩니다.
• 잠재적 의도 포착: 질적 분석(예: Musical Instruments 데이터셋)에 따르면, 바이클러스터링은 표면적인 분류 체계보다는 잠재적인 사용자 의도(예: 색소폰 관리 용품 그룹화)에 부합하는 캠핑을 복구합니다.
• 노이즈에 대한 강건성: 바이클러스터링은 클러스터 분산과 노이즈가 증가하더라도 강건하며, 친밀도 신호가 일부 쌍에 집중되어 있고 개별 사용자에게는 분산되어 있는 경우 개별 엔티티 신호에 의존하는 방법들보다 뛰어난 성능을 보입니다.
• 실질적인 트레이드오프: 바이클러스터링이 가장 높은 품질을 제공하지만, 실행 시간이 주요 제약인 매우 대규모의 상업적 배포 환경에서는 밴딧 기반 방법이 실행 가능한 확장 가능한 대안이 될 수 있습니다.

저자들은 자신들의 프레임워크가 타겟팅의 관련성과 효율성을 개선하지만, 행동 데이터로부터 학습된 임베딩에 의존하므로 사용자 타겟팅에서의 기존 불균형을 강화하지 않기 위한 투명성과 공정성 고려가 필요하다고 결론짓습니다.