무작위 샘플링은 정말 무작위인가 — Next-POI 추천의 네거티브 샘플링 (WWW'24)

연구의 계보 — KCC'22의 남은 질문에서 WWW'24까지

밀도 0.02–0.04%의 체크인 데이터에서 '미방문 POI를 모두 0으로 재구성하는' 관행이 남긴 질문이 이 연구의 출발점이다.

현대자동차 산학과제에서 SAE-NAD 기반 개인화 POI 추천을 구현하고 KCC 2022에 발표하면서 남은 질문이 하나 있었다. 체크인 행렬의 밀도는 0.02–0.04% 수준이고, 이 데이터로 오토인코더 계열 모델을 학습하면 사용자가 방문하지 않은 모든 POI가 0으로 재구성되도록 학습된다. 그 결과 모델은 인기 POI 쪽으로 쏠린다. 그렇다면 미방문 POI 가운데 무엇을 진짜 negative로 봐야 하는가.

이 질문을 예비 연구로 먼저 검증했다. ASK 2023(제1저자, 우수논문상)에서는 무작위 샘플링으로 사전 학습한 별도 모델이 미방문 POI에 점수를 부여하고, 점수 2–4분위(hard negative 후보)의 샘플링 확률을 각각 5/10/15%씩 높이고, 10km보다 먼 POI는 제외하고, 워밍업(NYC K = 30 epoch, TKY 50 epoch) 이후부터 hard negative 학습을 시작하는 구조를 제안했다. STAN 기준 recall@5가 무작위 샘플링 대비 NYC +16.4%, TKY +7.8%였고, 워밍업을 제거하면 각각 −12.2%, −11.5%로 떨어졌으며, hard negative와 easy negative의 차이는 +7.2%였다.

WWW'24 논문은 이 예비 결과를 (i) 무작위 샘플링이 EN 샘플링으로 퇴화한다는 관찰의 정식화, (ii) 사전 학습 모델이 아니라 학습 중인 모델을 그대로 쓰는 동적 샘플러, (iii) 지리 거리를 확률 가중이 아니라 DoP라는 하나의 점수로 통합하는 설계로 확장한 것이다.

1. 문제 — Next-POI 추천에서 negative는 어떻게 쓰이는가

모델은 매 시점 '가지 않은 장소' 몇 개를 골라 배우는데, 무엇을 고르는지는 지금까지 설계의 대상이 아니었다.

LBSN(Brightkite, Foursquare 등)에서 사용자는 방문한 장소를 체크인으로 남긴다. 사용자의 POI 체크인 시퀀스는 방문한 POI의 시간 순서와 체크인 시점을 담고 있고, next-POI 추천은 이 시퀀스로 학습한 모델이 사용자의 체크인 패턴을 추론해 다음에 방문할 POI를 찾아낼 수 있다는 직관에 기반한다. 시퀀스로부터 선호를 학습하는 RNN·LSTM·Transformer 계열이 주로 쓰인다.

딥러닝 기반 next-POI 추천 시스템은 체크인 시퀀스의 모든 시점에서 positive/negative POI를 정해 모델을 학습한다. 그 시점에 실제로 체크인한 POI 하나가 positive이고, 체크인하지 않은 나머지가 negative다. 문제는 어떤 시점에 사용자가 가지 않은 POI가 수천에서 수만 개라는 점이다. 그중 무엇을 negative로 고를지에 설계의 여지가 크고, 이 선택은 추천 정확도에 크게 영향을 미친다. OTT·이커머스 같은 도메인에서는 이 문제로 광범위한 연구가 있었지만, next-POI 도메인의 기존 접근은 대부분 미방문 POI를 단순 무작위로 뽑는 데 그쳤다.

기존 SOTA 모델이 쓰는 샘플링

negative는 다 같은 negative가 아니다

논문은 negative POI를 그 시점에 체크인할 확률에 따라 세 그룹으로 나눈다.

• hard negative (HN) — 그 시점에 방문할 가능성이 높았으나 가지 않은 POI. 사용자가 그 시점에 선호하는 특성을 갖고 있어 모델이 positive와 구분하기 어렵다.
• easy negative (EN) — 그 시점에 방문할 가능성이 매우 낮은 POI. positive와 쉽게 구분된다.
• 그 외 — 두 그룹 어디에도 속하지 않는 POI.

무작위 샘플링(RN)은 HN과 EN을 구분하지 않고 뽑는다. 이 논문의 주장은 positive에 대응하는 negative로 EN 대신 HN을 뽑는 편(HN 샘플링)이 next-POI 추천 정확도 향상에 더 효과적이라는 것이다. HN 샘플링을 하면 모델은 사용자가 더 선호하는 POI의 특성을 정밀하게 포착하도록 학습되고, 그 결과 positive의 순위가 사용자의 다른 어떤 HN보다 높게 — 즉 올바르게 — 예측된다.

2. 관찰 1 — 무작위 negative의 95%는 easy negative였다

학습이 진행되면 낮은 점수를 받는 POI가 계속 늘어나므로, 무작위 추출은 사실상 EN 추출이 된다.

기존 모델은 negative POI가 낮은 선호 점수를 갖도록 학습된다. 학습이 진행될수록(epoch가 늘수록) 더 많은 미방문 POI가 negative로 샘플링되므로, 모델이 낮은 점수를 주는 POI — 즉 EN으로 간주되는 POI — 의 수가 점진적으로 늘어난다. 따라서 기존 연구의 RN 샘플링은 학습이 진행되면 EN 샘플링과 유사하게 동작한다는 것이 논문의 주장이다.

실험 설계

• 실세계 데이터셋 NYC·TKY 사용.
• 각 사용자의 시퀀스 매 시점에서, 그 시점에 체크인하지 않았고 사용자와 지리적으로 가까운 POI M = 2,000개를 선택(GeoSAN의 방식을 따름).
• 학습 중인 추천 모델로 이 M개에 대한 선호 점수를 0–1로 예측.
• 총 70 epoch 동안 이 과정을 반복하고, 모든 user-POI 쌍을 점수 기준 다섯 구간(0.0–0.2, 0.2–0.4, …, 0.8–1.0)으로 분류.
• 모델은 GeoSAN(그림 1)과 CatDM(부록 C.1) — 둘 다 next-POI 추천의 SOTA.

결과

0.0–0.2 구간은 EN, 0.8–1.0 구간은 HN으로 볼 수 있다. 학습 중반부(epoch 30)부터 두 데이터셋 모두 95% 이상의 쌍이 0.0–0.2 구간에 속했다(CatDM은 80% 이상). 이 시점 이후 사용자에게 negative POI를 무작위로 뽑으면 그것이 EN일 가능성이 매우 높다. 즉 학습이 진행되면서 RN 샘플링으로 학습한 모델은 실질적으로 EN 샘플링으로 학습한 모델과 같아진다.

이 관찰은 부수적으로 Step 1 설계의 근거도 준다. HN(0.8–1.0 구간)은 학습 중 전체 negative의 3% 이하에 불과하므로, 이 적은 수를 정밀하게 골라내는 별도의 절차가 필요하다.

2. 관찰 2 — EN으로 배운 모델은 정답을 중위권에 둔다

EN의 순위는 그 시점 전체 negative 중 최하위다. 'EN보다만 높게' 학습된 positive의 순위는 중간에서 멈춘다.

EN 샘플링을 쓰면 모델은 positive의 순위를 EN보다 높게 예측하도록 학습된다. 그런데 EN의 순위는 그 시점 사용자의 전체 negative 중 최하위에 있다. 따라서 EN보다만 높게 예측되도록 학습된 positive의 순위는 전체의 중간쯤에 놓일 가능성이 높다. 즉 positive보다 높은 순위를 받는 negative POI가 여전히 많이 남아 있고, 이는 모델이 잘못된 방향으로 학습되고 있다는 뜻이다.

실험 설계

• 모델은 GeoSAN. 매 시점 전체 미방문 POI 중 예측 선호 점수 상위 10개를 negative로 쓴 모델을 GeoSAN-HN, 하위 10개를 쓴 모델을 GeoSAN-EN이라 한다.
• 학습된 각 모델로, 사용자가 시퀀스에서 마지막으로 체크인한 POI(ground truth, GT)와 그 시점 전체 negative POI의 선호 점수를 예측.
• 모든 POI를 점수 내림차순으로 정렬한 뒤 GT POI를 순위 구간 다섯 개(상위 0–20%, …, 80–100%)로 분류.

결과

NYC에서 GeoSAN-HN의 예측 순위 기준 GT POI의 70% 이상이 상위 0–20% 구간에 속했다. 대부분의 GT POI 순위가 전체 POI 중 최상위로 올바르게 예측된 것이다. 반면 GeoSAN-EN에서는 약 30%만 상위 0–20% 구간에 속했고, 남은 약 70%의 GT POI 순위는 중간 혹은 그 아래로 잘못 예측되었다. 이는 추천 정확도 저하로 이어질 수 있다.

두 관찰이 이끄는 결론

• 무작위 샘플링은 실질적으로 EN 샘플링이고, EN 샘플링은 HN 샘플링보다 정확도 향상에 불리하다 → HN 샘플링 기반의 학습 기법이 필요하다.
• HN은 학습 중 전체 negative의 3% 이하에 불과하므로, 이 적은 수를 정밀하게 골라내는 방법이 필요하다.
• next-POI 도메인에서는 잠재 공간의 거리뿐 아니라 지리적 거리도 함께 고려해야 한다.

3. 제안 방법 — Degree of Positiveness (DoP)

'모델이 갈 것 같다고 예측했고, 실제로도 가까웠던' 미방문 POI를 hard negative로 정의한다.

사용자 u가 시점 t에 POI v를 체크인할 법했던 정도를 DoP로 정의하고, 다음 두 요인이 이를 결정한다.

• c(u, v, t) — 시점 (t−1)까지의 u의 체크인 시퀀스를 전제로, POI v가 u가 선호하는 특성을 갖는 정도.
• d(u, v, t) — 시점 t에서 사용자 u와 POI v 사이의 지리적 거리.

u가 시점 t에 체크인한 positive POI는 그 시점 u에게 DoP가 가장 높은 POI로 볼 수 있다. 이 관점에서 시점 t의 HN POI는 체크인하지 않았지만 DoP가 positive에 근접할 만큼 높은 POI로 규정된다. 기존 연구를 따라, 시점 t 이전에 u가 이미 체크인한 POI는 t의 negative에서 제외한다.

두 요인의 우선순위 — 세 전략 중 (i)을 채택

HN을 찾을 때 두 요인 사이에 우선순위를 주는 방식은 세 가지가 가능하다. (i) c를 d보다 우선, (ii) d를 c보다 우선, (iii) 둘에 동등한 우선순위. 논문은 (i)을 채택한다. 즉 Step 1에서는 c만으로 HN 후보를 정하고, Step 2에서는 c와 d로 함께 조정된 세밀한 선호 점수로 HN을 샘플링한다. 이 전략에서 얻은 HN이 다른 두 전략에 비해 학습 초·중반에 모델을 더 높은 정확도로 수렴시킨다는 것을 4장에서 실증한다.

수식

• 식 (1) c(u, v̄, t) = Q_u,(t−1)(v̄) — Q_u,(t−1)은 u의 (t−1)까지 체크인 시퀀스로 학습된(즉 지금 학습 중인) next-POI 추천 모델, Q_u,(t−1)(v̄)는 그 모델이 예측한 선호 점수로 0 ≤ Q ≤ 1.
• 식 (2) C_u,t(m) = { v̄ | rank(c(u, v̄, t)) ≤ m }, v̄ ∈ V̄_{u,t} — HN 후보 집합.
• 식 (3) d(u, v̄, t) = Haversine(v_u,t, v̄), v̄ ∈ C_u,t(m) — 위·경도로 두 지점 간 최단 거리를 구하는 Haversine 공식. 학습 시에는 그 시점 positive POI v_u,t의 위치를 사용자 위치로 삼는다.
• 식 (4) DoP(u, v̄, t) = (1 − d(u, v̄, t)) · c(u, v̄, t)
• 식 (5) H_u,t(n) = { v̄ | rank(DoP(u, v̄, t)) ≤ n }
• 식 (6) L_u,t = −( log Q_u,(t−1)(v_u,t) + Σ_{v̄ ∈ H_u,t(n)} log(1 − Q_u,(t−1)(v̄)) )

DoP는 c가 커지거나 d가 작아질수록 커지는, 두 요인으로 조정된 세밀한 선호 점수다. 식 (4)에 쓰인 곱셈 결합은 추천 시스템 연구에서 널리 쓰여 온 방식이다.

3.2 Step 1 — 선호 특성으로 POI를 필터링

HN은 학습 중 3% 이하에 불과하므로, HN이 될 가능성이 낮은 POI를 먼저 걸러낸다.

일반 추천 도메인에서 HN 아이템은 잠재 특성 공간에서 positive 아이템에 매우 가까이 위치한 아이템을 뜻한다. next-POI 추천에서도 negative POI가 사용자의 이전 체크인 시퀀스에 비추어 선호 특성을 적게 가질수록, 잠재 공간에서 positive POI로부터 멀어질 가능성이 크다. 즉 선호 특성이 높은 POI는 positive 근처에, 낮은 POI는 멀리 위치한다. 따라서 선호 특성이 낮은 POI는 HN이 되기 어렵고(모델이 positive보다 훨씬 낮은 점수를 줄 것이므로), 이들을 후보에서 먼저 걸러내는 것이 Step 1이다.

c(u, v̄, t)는 식 (1)처럼 학습 중인 모델 Q_u,(t−1)의 예측 선호 점수로 정의한다. 여기서 c를 구하는 모델로는 체크인 시퀀스에서 사용자의 체크인 패턴을 추론할 수 있는 기존 모델 어떤 것이든(GeoSAN, STAN 등) 쓸 수 있다 — 즉 제안 기법은 model-agnostic하다.

그다음 시점 t의 negative POI를 c의 내림차순으로 정렬하고 하위 POI를 걸러내, 남은 상위 m개를 HN 후보 집합 C_u,t(m)으로 삼는다(식 2).

왜 V̄를 M개 무작위 추출로 구성하는가

C_u,t(m)이 늘 동일한 상위 m개 POI로 고정되는 것을 막기 위해, V̄_{u,t}를 시점 t의 전체 negative POI에서 무작위로 뽑은 M개(예: M = 2,000)로 구성한다. 이는 다른 도메인의 HN 샘플링 선행 연구를 따른 것이다.

예시 (그림 3, m = 3)

시점 t₁에 사용자 u가 체크인한 POI v_a가 positive다. 체크인하지 않은 POI v_b~v_g 중 모델 Q_u,t₀이 예측한 선호 점수가 가장 높은 상위 3개가 HN 후보가 된다.

즉 C_u,t₁(3) = {v_b, v_d, v_e}이고, n = 2일 때 최종 HN은 H_u,t₁(2) = {v_b, v_d}다.

3.3 Step 2 — DoP로 hard negative를 샘플링

선호 특성이 높아도 사용자와 지리적으로 멀면 그 시점에 방문할 가능성은 낮다.

OTT·이커머스처럼 잠재 특성 공간의 거리만 보면 되는 도메인과 달리, next-POI 도메인에서는 지리적 거리도 반드시 고려해야 한다는 것이 논문의 주장이다. C_u,t(m)에 속한 negative POI v̄가 u의 선호 특성을 많이 갖더라도 u에서 지리적으로 멀리 있으면, u가 시점 t에 v̄를 체크인할 가능성은 낮다.

통계적 근거 — 연속 체크인 쌍의 거리 분포 (그림 4, 부록 C.2)

사용자의 체크인 확률과 거리의 관계를 확인하기 위해, u가 시퀀스에서 연속으로 체크인한 두 positive POI 사이의 지리적 거리를 계산하고 그 분포를 구했다. NYC와 TKY 모두 전체 쌍의 약 70%가 5km 미만 구간에 속했다. 사용자는 다음 방문지로 현재 위치에 가까운 POI를 택하는 경향이 강하다.

절차

• C_u,t(m)의 각 POI v̄에 대해 식 (3)으로 Haversine 거리를 계산. 학습 시 사용자 위치는 그 시점 positive POI v_u,t의 위치로 삼는다.
• 얻은 d 값들에 min–max 스케일링을 적용한다. u에서 가장 먼 v̄의 d는 1, 가장 가까운 v̄의 d는 0이 된다(0 ≤ d ≤ 1).
• 식 (4)로 DoP를 계산하고, m개 후보 중 DoP 상위 n개를 HN으로 샘플링(식 5).

그림 3의 예에서 v_b, v_d, v_e의 c는 서로 비슷하지만 v_e가 v_a(= u의 위치)에서 더 멀기 때문에 DoP(u, v_e, t₁)가 나머지 둘보다 작아진다. 따라서 n = 2에서 최종 HN은 v_b와 v_d다. 결과적으로 DoP 개념은 잠재 특성 공간에서도, 지리 공간에서도 positive에 가까운 HN POI를 효과적으로 골라낸다.

3.4 학습 절차 — 체크인 시점마다 다시 고르는 동적 샘플링

positive 1개와 HN n개로 손실을 계산해 모델을 갱신하고, 갱신된 모델로 다음 시점의 HN을 다시 고른다.

Step 2에서 얻은 HN 집합 H_u,t(n)과 대응하는 positive POI v_u,t로 모델 Q_u,(t−1)을 식 (6)의 교차 엔트로피 손실로 학습한다. 손실을 최소화하면 Q는 v_u,t의 선호 점수를 1에 가깝게, H_u,t(n)에 속한 v̄들의 점수를 0에 가깝게 예측하도록 학습된다. 이렇게 학습된 모델을 Q_u,t라 하고, '다음' 시점 (t+1)에서 Q_u,t로 Step 1과 2를 다시 수행한다. 예를 들어 시점 t₂의 HN은, t₁에서 positive v_a와 HN v_b·v_d로 학습된 Q_u,t₁을 써서 새로 뽑는다.

이 과정을 u의 시퀀스 마지막 시점까지 반복하고, 다른 모든 사용자에 대해서도 각자의 마지막 시점까지 반복한다. 최종적으로 모든 사용자의 전체 체크인 시퀀스로 학습된 모델 Q로 각 사용자의 현재 시점 next-POI를 추천한다.

정리하면 한 사용자의 한 epoch은 체크인 시점 수 T만큼 같은 네 단계를 반복하는 것이다 — 미방문 POI M개로 후보 모집단을 구성하고, 학습 중인 모델의 예측 선호 점수로 정렬해 상위 m개를 후보로 남기고(Step 1), 후보의 지리 거리로 DoP를 계산해 상위 n개를 HN으로 삼고(Step 2), positive 하나와 그 HN들로 손실을 계산해 모델을 갱신한다. 마지막 시점까지 갱신된 모델로 시점 (T+1)에 u가 체크인할 POI를 추천한다.

3.5 시간 복잡도와 실측 학습 시간 — 비용은 수렴 epoch 감소로 상쇄된다

epoch당 시간은 2.7배 늘지만 수렴 epoch가 47 → 12로 줄어, 총 학습 시간은 약 30% 감소했다.

샘플 하나의 선호 점수 예측에 걸리는 시간을 s라 하면, Step 1은 M개 샘플의 점수 계산과 정렬로 O(M·s + M·log M), Step 2는 m개 후보의 DoP 계산·정렬로 O(m·log m)이다. M개 전체의 점수를 이미 계산해 두었으므로 손실 계산에는 O(n)만 든다. 전체는 O(M·s + M·log M + m·log m + n)이고, m과 n이 M보다 훨씬 작으므로(예: M = 500, m = 50, n = 10) O(M·s + M·log M)으로 근사된다. RN 샘플링은 negative를 찾는 데 O(1), 손실 계산에 O(n·s + n)이므로 O(n·s)로 근사된다.

GPU 병렬화를 쓰면 점수 예측 복잡도는 최대 s까지, 정렬 복잡도는 최대 log M까지 줄어든다(처리 유닛 수에 따라). 따라서 병렬화 하에서 제안 기법은 O(s + log M), RN 샘플링은 O(s)다. 나아가 수렴에 필요한 epoch 수는 일반적으로 RN 샘플링이 HN 샘플링보다 크다는 선행 연구 결과가 있으므로, 전체 학습의 복잡도는 각각 O((s + log M)·e)와 O(s·E)가 된다(e < E).

실측 학습 시간 (표 4 · PLSPL, NYC)

Step 1·2가 추가되어 epoch당 시간은 140.4초에서 384.5초로 늘어난다. 그러나 수렴에 필요한 총 epoch 수가 47에서 12로 크게 줄어 — HN 샘플링이 RN 샘플링보다 적은 epoch에 수렴한다는 선행 연구 결과와 대체로 일치한다 — 모든 아이디어를 적용해도 수렴까지의 총 시간은 원래 PLSPL보다 약 30% 적었다.

4.1 실험 설계 — 샘플러만 바꿔 원인을 분리했다

모델 구조·데이터 분할·하이퍼파라미터는 원 논문 그대로 두고 negative를 고르는 방식만 교체했다.

데이터셋 (표 A)

희소도는 user-POI 체크인 행렬 전체 셀 중 결측 셀의 비율이다. NYC·TKY는 각각 뉴욕과 도쿄에서 2012.04.12–2013.02.16에 수집된 체크인 데이터이고, Brightkite는 2008.04–2010.10 기간의 대규모 체크인을 담고 있다.

전처리

• NYC·TKY: 5개보다 많은 POI를 방문한 사용자만, 5명보다 많은 사용자가 방문한 POI만 유지. 단 GeoSAN은 메모리 문제로 체크인 시퀀스 길이가 최소 100 이상인 사용자만 유지.
• Brightkite: 시퀀스 길이 최소 100 이상인 사용자, 10명보다 많은 사용자가 방문한 POI만 유지.
• PLSPL과 CatDM은 POI 카테고리를 쓰는데 Brightkite에는 카테고리 정보가 없다. Foursquare에서 POI 카테고리를 얻어 Brightkite에 병합했다.

지표와 설정

기존 연구에서 널리 쓰이는 두 지표 — hit rate(H)와 NDCG(G), K = 5, 10. HN 후보 수 m = 50, 매 시점 샘플링하는 HN 수 n = 10. 다섯 모델의 실험은 모두 같은 GPU 데스크톱 한 대에서 수행했다.

베이스 모델 5종과 평가 프로토콜 (부록 A.3)

비교 설계. Orig = 각 모델을 원래 샘플링으로 학습, Ours = 같은 모델을 제안 기법으로 학습. 구조·분할·하이퍼파라미터가 동일하므로 두 결과의 차이는 샘플링에서만 온다.

다섯 가지 연구 질문

• RQ 1. 제안 학습 기법이 SOTA 베이스 모델에 얼마나 효과적인가
• RQ 2. Step 1에서 POI를 걸러내는 것이 얼마나 효과적인가
• RQ 3. Step 2에서 거리를 고려하는 것이 얼마나 효과적인가
• RQ 4. 제안 기법에 얼마의 시간이 드는가
• RQ 5. n 값에 따라 정확도가 어떻게 변하는가 (m은 부록 C.6)

4.2.1 RQ1 — 주 결과: 60개 조합 전부 향상, 최대 +82.8%

세 데이터셋 × 다섯 모델 × 네 지표 모든 조합에서 Ours가 Orig를 앞섰다.

표 1 — 원래 RN 샘플링(Orig)과 제안 HN 샘플링(Ours)의 정확도 비교

논문의 해석 (4.2.1절)

• 일관되고 보편적인 향상. 모든 데이터셋에서, 모든 모델이, 모든 지표에서 Ours가 Orig를 상회했다. 가장 큰 향상은 TKY의 PLSPL — H@5 +82.5%, G@5 +82.8%.
• Brightkite는 향상 폭이 다소 작다. 논문은 이를 Brightkite의 사용자당 평균 방문 POI 수(18)가 NYC(44)·TKY(60)보다 훨씬 적어, 모델이 negative POI에 정확한 선호 점수를 부여하기 상대적으로 어렵기 때문으로 해석한다.
• 결론은 유지된다. 그럼에도 모든 데이터셋에서 결과가 일관되므로, DoP 개념을 사용한 제안 기법이 기존 모델의 RN 샘플링보다 정확도 향상에 더 유익하다는 것이 검증된다.

4.2.2 RQ2 — Step 1의 필터 기준: Ours > w/o Filt > Filt-d

HN을 정확히 찾는 데는 거리보다 선호 점수를 우선하는 것이 더 효과적이다.

Step 1의 필터링에 대해 두 변형을 설계했다. (i) Filt-d — d가 큰(사용자에서 지리적으로 먼) negative POI를 먼저 걸러내고 남은 POI에서 DoP로 HN을 샘플링. 즉 d를 c보다 우선하는 전략. (ii) w/o Filt — 어떤 negative POI도 걸러내지 않고 DoP만으로 HN을 샘플링. 즉 두 요인에 동등한 우선순위를 주는 전략.

표 2 — Step 1 필터링 변형 비교 (NYC·TKY)

세 기법의 정확도 순서는 모델과 무관하게 Ours > w/o Filt > Filt-d였다. 이는 거리(d)보다 선호 점수(c)를 우선하는 것이 HN POI를 정확히 찾는 데 더 효과적임을 뜻한다.

학습 곡선 (그림 5·부록 C.4, 검증셋 G@10)

이 negative들이 학습 중 positive를 높은 순위에 올바르게 위치시키는지 확인하기 위해, 최대 50 epoch 동안 매 epoch의 정확도 차이를 관찰했다(NYC는 그림 5, TKY는 그림 C). PLSPL과 CatDM에서는 Ours가 학습 초기부터 정확도를 상당히 끌어올리고 다른 두 기법보다 높은 값으로 수렴했다. STAN에서는 학습 초기(5 epoch 미만)에는 세 기법의 차이가 크지 않으나, 학습이 진행되면서 Ours가 가장 크게 향상되어 최고 정확도로 수렴했다.

4.2.3 RQ3 — Step 2의 거리: 가까운 곳을 HN으로 쓸 때가 가장 좋다

거리를 반대로 쓰면 선호 점수만 쓰는 것보다도 나쁘다. 그러나 거리만 쓰면 더 나쁘다.

Step 2의 거리 고려에 대해 두 변형을 설계했다. (i) Dist-l — Step 1에서 얻은 POI 중 사용자와 거리가 먼 POI를 HN으로 샘플링(원안과 반대). 구체적으로 DoP_long(u, v̄, t) = c(u, v̄, t) · d(u, v̄, t)의 상위 n개를 HN으로 뽑는다. (ii) w/o Dist — 거리를 고려하지 않고 c가 가장 높은 상위 n개를 뽑는다.

표 3 — Step 2 거리 활용 변형 비교 (NYC·TKY)

두 가지 관찰이 나온다. (i) 원안과 반대 전략으로 거리를 활용하면(Dist-l) 선호 점수만으로 HN을 찾는 것(w/o Dist)보다 정확도가 나쁘다. (ii) HN 샘플링에서 높은 선호 점수와 짧은 거리를 함께 추구할 때 정확도가 높아진다.

거리만 쓰면 어떻게 되는가 (부록 C.5, 표 D·E)

설계 판단을 더 검증하기 위해 거리만 쓰는 w/o Score도 평가했다. 대부분의 베이스 모델에서 선호 점수만 쓰는 w/o Dist가 거리만 쓰는 w/o Score보다 높은 정확도를 보였다 — DoP 결정에서 선호 점수의 중요도가 거리보다 높다는 뜻이다.

4.2.5 RQ5와 부록 — 하이퍼파라미터 민감도, 결합 함수, 기존 HN 기법과의 비교

n(5–20)과 m(0–75)에는 둔감하고, 곱 결합이 sigmoid보다 약 2.5% 우세하며, GDNS를 크게 앞선다.

n에 대한 민감도 (그림 6, NYC)

샘플링할 HN 수 n을 5부터 20까지 5 단위로 바꿔 PLSPL·CatDM·STAN의 정확도(H@5, G@5)를 관찰했다. 전반적으로 제안 학습 기법은 n 값에 둔감했고, 나머지보다 약간 나은 결과를 보인 10을 n으로 채택했다.

m에 대한 민감도 (부록 C.6, 그림 D, STAN)

HN 후보 수 m을 0부터 75까지 25 단위로 바꿔 관찰했다. m = 0은 어떤 negative POI도 걸러내지 않고 HN을 샘플링하는 경우다. m 값과 무관하게 필터링을 통해 후보 HN을 얻는 것이 m = 0보다 항상 효과적이었고, m 값에 따른 정확도 차이는 크지 않아 50을 채택했다.

DoP 결합 함수 — 곱 vs sigmoid (부록 C.3, 표 C · STAN, NYC)

DoP 계산 방식으로 c와 d의 선형 결합에 sigmoid를 적용하는 방법 — DoP(u, v̄, t) = σ( c(u, v̄, t) · (1 − d(u, v̄, t)) ) — 을 추가로 설계해 비교했다.

지표와 무관하게 곱 결합이 sigmoid보다 약 2.5% 높은 정확도를 보였다.

기존 SOTA HN 샘플링 기법과의 비교 — GDNS (부록 C.7, 표 F)

일반 도메인의 SOTA HN 샘플링 기법 중 하나인 GDNS를 next-POI 추천 모델에 적용해 비교했다. GDNS는 여러 epoch에 걸쳐 선호 점수가 계속 높은 아이템은 false negative일 가능성이 높다는 가정에서, 처음에는 점수가 높았다가 epoch가 지나며 낮아진 아이템만 사용자의 HN으로 간주한다. STAN을 베이스 모델로, 각 데이터셋에서 무작위로 뽑은 사용자 100명에 대해서만 정확도를 평가했다.

거리를 아예 쓰지 않은 Ours w/o Dist만으로도 GDNS를 크게 앞섰다.

5. 관련 연구 — 일반 도메인 HN 샘플링과의 차이

잠재 공간 거리만 보는 기존 기법과 달리, 지리적 거리를 함께 쓰고 아이템 집합 대신 체크인 시퀀스로 선호를 추론한다.

이 논문의 차별점

• next-POI 추천에서 HN 샘플링 기반 모델 학습 기법을 처음 제안했다.
• HN POI를 찾을 때 잠재 특성 공간의 거리뿐 아니라 지리적 거리도 함께 사용한다. OTT·이커머스에서는 잠재 공간 거리만으로 HN을 찾을 수 있지만, next-POI에서는 선호 특성이 높아도 지리적으로 먼 POI는 그 시점에 방문할 가능성이 낮다.
• 일반 도메인처럼 사용자가 소비한 아이템 집합으로 HN을 샘플링하는 대신, 사용자가 체크인한 POI의 시퀀스로 선호를 추론한다. 따라서 이 연구는 시퀀스 기반 추천 시스템에서 HN 샘플링이 RN 샘플링보다 효과적일 수 있다는 통찰을 제공한다.

6. 결론과 성과

관찰로 기존 관행의 한계를 지적하고, DoP 기반 2단계 학습 기법으로 다섯 SOTA 모델을 모두 향상시켰다.

• 핵심 관찰 — 학습이 진행되면 RN 샘플링은 EN 샘플링으로 작동하며, EN 샘플링은 HN 샘플링보다 정확도 향상에 불리하다. 이로써 기존 연구의 한계를 실험으로 지적했다.
• 제안 — HN POI를 결정하는 DoP 개념을 도입하고, (Step 1) 사용자가 선호하는 특성을 갖는 정도로 POI를 필터링하고, (Step 2) 잠재 공간과 지리 공간 양쪽에서 positive에 가까운 HN POI를 DoP로 샘플링하는 2단계 학습 기법을 제안했다.
• 검증 — 실세계 데이터셋 3종에서 제안 기법을 결합한 모든 SOTA 모델이 정확도에서 유의한 이득을 얻었으며, 최대 약 82.8% 향상됐다.

산출

• WWW '24 게재 — Hong-Kyun Bae*, Yebeen Kim*, Hyunjoon Kim†, Sang-Wook Kim† (한양대학교, * 공동 제1저자, † 공동 교신저자), The ACM Web Conference 2024, Singapore, 2024.05, pp. 3888–3899, DOI 10.1145/3589334.3645681.
• 예비 연구 ASK 2023(정보처리학회 춘계학술발표대회, Vol. 30, No. 1) 제1저자 논문 「체크인 시퀀스 기반의 next POI 추천 시스템을 위한 네거티브 샘플링 방법」 — 우수논문상.
• 「Next-POI 추천을 위한 네거티브 POI 샘플링 방법 및 그 시스템」 국내·국제 특허 출원(2024.03).

연구비 지원

과학기술정보통신부 재원 정보통신기획평가원(IITP) 지원 — RS-2022-00155586(실세계 다운스트림 태스크를 위한 고성능 빅-하이퍼그래프 마이닝 플랫폼), 2020-0-01373(인공지능대학원 지원사업, 한양대학교), 2022-0-00352.

이 연구에서 남는 것

학습 신호의 '보이지 않는 기본값'을 의심하는 습관.

이 연구의 기여는 새로운 아키텍처가 아니다. 다섯 모델의 구조를 하나도 바꾸지 않고, 모두가 기본값으로 두고 지나갔던 negative를 고르는 한 줄만 바꿔 60개 조합 전부를 개선했다. 관찰(무엇이 실제로 학습되고 있었나) → 정식화(DoP) → 도메인 제약의 반영(지리 거리) → 변형 실험으로 각 구성 요소의 필요성 검증 → 비용 회계(epoch당 시간 vs 수렴 epoch)라는 흐름은 이후 다른 문제를 볼 때도 그대로 쓰는 틀이 되었다.

논문을 세 가지 질문으로 — 그리고 핵심 용어 정리

슬라이드 25의 개요 카드. 논문 전체가 Q1(관찰)–Q2(제안)–Q3(검증)의 세 질문에 답하는 구조로 짜여 있다.

핵심 용어

설계 판단 세 가지 — 근거와 실험적 확인의 대조

슬라이드 29의 대조표. 세 가지 설계 판단마다 '왜 그렇게 했는가(근거)'와 '정말 그런가(실험)'가 짝지어 제시된다.

이 표는 논문의 주장 구조를 그대로 드러낸다. 각 판단은 선행 연구에서 온 근거와 이 논문이 직접 측정한 증거를 동시에 갖고 있고, 셋 중 어느 하나도 근거만으로 넘어가지 않는다.

베이스 모델·데이터셋·비교 기법의 원 출처

논문이 재현하거나 비교한 대상의 정식 제목과 게재처. 모델 이름만으로는 무엇을 재현했는지가 남지 않는다.

베이스 모델 5종 (+ 언급된 TGSTAN)

데이터셋 출처

비교·인용된 네거티브 샘플링 기법

기법 구성 요소의 인용 근거

• Haversine 공식 — Van Brummelen, Hamm. Heavenly Mathematics: The Forgotten Art of Spherical Trigonometry, 2014. next-POI 추천 선행 연구에서 널리 쓰여 왔다는 근거로 SIGIR'22의 두 연구를 함께 인용한다.
• 교차 엔트로피 손실(식 6) — Kang, McAuley. "Self-attentive Sequential Recommendation"(SASRec). ICDM 2018, 197–206.
• 곱셈 결합(식 4) — LANCER(AAAI 2023, 4141–4148), competition-aware TV show recommendation(ICDE 2023, 2822–2834), "No, That's Not My Feedback"(ICDE 2019, 316–327) 등 추천 시스템 연구의 선례.
• GPU 병렬화로 복잡도가 줄어든다는 근거 — MSGD(IEEE TPDS 29(7), 2018, 1530–1544), Tan·Cao·Fong(HPDC 2016, 219–230).
• HN 샘플링이 RN보다 적은 epoch에 수렴한다는 근거 — AOBPR(WSDM'14), DNS(SIGIR'13), 그리고 Xu et al. "Negative Sampling for Contrastive Representation Learning: A Review"(arXiv:2206.00212, 2022).
• 시퀀스 모델 계열 — RNN(Rumelhart et al., Nature 1986), LSTM(Hochreiter & Schmidhuber, 1997), Transformer(Vaswani et al., NeurIPS 2017).
• 도메인 서베이 — Islam et al. "A Survey on Deep Learning based POI Recommendations"(Neurocomputing 472, 2022, 306–325), Werneck et al.(WebMedia 2020, 185–192).

거리를 넣어도 되는지를 확인한 방법 — 그림 4와 그림 B의 실제 축

'약 70%가 5km 이내'는 5km 단위로 45km까지 잘라 본 히스토그램에서 나온 수치다.

Step 2에서 지리 거리를 쓰기 전에, 논문은 사용자의 체크인 확률과 거리의 관계를 통계적으로 확인했다. 각 사용자의 체크인 시퀀스에서 연속으로 체크인한 두 positive POI 사이의 지리 거리를 모두 계산하고, 그 거리의 분포를 구했다.

• x축 — 거리 구간을 0–5, 5–10, 10–15, 15–20, 20–25, 25–30, 30–35, 35–40, 40–45 (km)의 5km 단위 아홉 구간으로 나눈다.
• y축 — 각 구간에 속하는 연속 POI 쌍의 비율(%). 축의 상한은 80%다.
• NYC 결과가 본문 그림 4, TKY 결과가 부록 C.2의 그림 B다.
• 두 데이터셋 모두 전체 쌍의 약 70%가 0–5km 구간에 몰렸고, 나머지는 긴 꼬리로 45km까지 흩어진다.

즉 거리를 DoP에 넣은 것은 직관이 아니라 이 분포에 근거한 판단이다. 사용자는 다음 방문지로 현재 위치에 가까운 POI를 택하는 경향이 강하다.

논문 표기법 — 부록 B, 표 B

식 (1)–(6)에 등장하는 기호의 정의. rank(·)가 두 번, 서로 다른 집합 위에서 정의된다는 점이 핵심이다.

두 rank의 정의역이 다르다는 점이 2단계 구조를 그대로 반영한다. Step 1의 순위는 무작위 추출한 미방문 POI 전체(V̄) 위에서, Step 2의 순위는 걸러낸 후보 집합(C) 위에서 계산된다.

학습 곡선의 실제 축 — 그림 5(NYC)와 그림 C(TKY)

모델마다 epoch 축이 다르다. PLSPL은 20 epoch까지, CatDM·STAN은 50 epoch까지 그린다.

Step 1의 필터 기준 세 가지(Filt-d / w/o Filt / Ours)가 학습 중 어떻게 갈라지는지를, 최대 50 epoch까지 검증셋 NDCG(G@10)로 관찰했다. 그래프의 축은 다음과 같다.

PLSPL의 축이 20에서 끊기는 것은 원 논문 설정의 학습 epoch가 20이기 때문이다. NYC 결과가 그림 5, 같은 실험의 TKY 결과가 부록 C.4의 그림 C이며, 두 데이터셋에서 세 기법의 우열과 수렴 양상이 같게 나타난다.

참고로 하이퍼파라미터 민감도 그래프의 축도 함께 적어 둔다. 그림 6(n에 대한 민감도, NYC)은 x축 n = 5, 10, 15, 20에 대해 PLSPL(y 0.1–0.5), CatDM(0.15–0.30), STAN(0.2–0.4)의 H@5·G@5를 그리고, 부록 C.6의 그림 D(m에 대한 민감도, STAN)는 x축 m = 0, 25, 50, 75에 대해 NYC(y 0.1–0.5)와 TKY(0.1–0.4)를 그린다.

ASK'23 → WWW'24, 항목별로 무엇이 바뀌었나

예비 연구와 최종 논문의 차이를 여섯 항목으로 대조하면, 확장의 방향이 '정적·사후적 설계 → 학습 동역학에 연동된 설계'였음이 드러난다.

ASK'23의 실험 설정 (표 2, 슬라이드 37)

• 분할 — 시간순 정렬 후 사용자별 처음 70% 훈련 / 10% 검증 / 최근 20% 테스트. WWW'24가 각 모델 원 논문의 8:1:1 분할을 따른 것과 다르다.
• 학습 — NYC 50 epoch, TKY 60 epoch. 거리 필터 N = 10km. 사전 학습 epoch K = 30(NYC) / 50(TKY).
• 비교군 다섯 가지 — 랜덤 샘플링(기준), 하드 네거티브 샘플링(warm-up 유·무), 이지 네거티브 샘플링(warm-up 유·무, 거리 필터는 동일).
• NYC 표 3의 대표 수치 — recall@5는 랜덤 0.3155 → 제안(warm-up O) 0.3675, warm-up X는 0.2770으로 하락. NDCG@5는 0.2274 → 0.2712. R/M/G를 각각 K = 5, 10, 15, 20에서 보고했다.

즉 예비 연구에서 warm-up이 필수 조건이었던 이유(사전 학습된 모델이 없으면 HN을 못 고른다)가, WWW'24에서는 '학습 중인 모델을 그대로 c의 산출기로 쓴다'는 설계로 해소된다. warm-up 하이퍼파라미터 K가 사라진 것이 두 논문 사이의 가장 구조적인 변화다.

서지 정보와 초록의 논지 순서

게재 정보와, 초록이 주장을 쌓아 올리는 순서.

초록이 쌓는 순서

• 기존 딥러닝 기반 next-POI 연구는 모델 학습에 무작위 네거티브(RN) 샘플링을 써 왔다.
• 이 논문은 학습이 진행되면 그 RN 샘플링이 실제로는 EN 샘플링으로 작동한다는 것을 주장하고 검증한다 — EN은 사용자가 그 체크인 시점에 방문할 가능성이 매우 낮았던 POI다.
• 이어서 EN 샘플링이 HN 샘플링보다 정확도 향상에 불리하다는 것을 확인한다.
• 이 한계를 다루기 위해 두 요인 — (i) POI가 사용자가 선호하는 특성을 갖는 정도, (ii) 사용자와 POI 사이의 지리적 거리 — 으로 정식화되는 DoP 개념을 제시한다.
• 그리고 DoP를 사용한 HN 샘플링 기반 모델 학습 기법을 제안한다.
• 실세계 데이터셋 NYC·TKY·Brightkite에서, 이 기법으로 학습한 모든 SOTA 모델이 최대 약 82.8%의 극적인 정확도 향상을 보였다.

제목의 세 단어(Observation, Approach, Evaluation)가 그대로 논문의 2·3·4장이고, 초록도 이 순서를 따른다. 논문이 스스로를 '방법 논문'이 아니라 관찰에서 출발한 논문으로 규정하고 있다는 점이 제목에 드러나 있다.