맞춤형 문제 추천을 위한 머신러닝과 통계학적 원리
1. 개요
본 온라인 저지(Online Judge)의 다음의 목표 실현을 위해 머신러닝과 통계학적인 기법을 활용한다.
- 개인화(Personalization): 사용자별로 성공 가능성이 높은 문제를 우선 제시
- 통계적 안정성(Statistical Reliability): 저표본 노이즈(예: 1/1=100%)를 완화
2. 데이터와 기호
- 사용자 집합: $U$
- 문제 집합: $I$
- 사용자 $u$의 문제 $i$에 대한 상호작용(시도/정답): $x_{ui}$
- 문제 $i$의 시도자 수: $n_i$
- 문제 $i$의 성공자 수: $k_i$
- 문제 $i$의 관측 정답률: $\hat p_i = k_i / n_i$
- 전체 평균 정답률: $p_0$
저표본 왜곡을 줄이기 위해 본 시스템은 $n_i < 20$ 문제를 추천 후보에서 제외한다.
3. 개인화 모델: SVD 협업필터링
사용자-문제 평점 행렬 $R$를 잠재요인으로 분해한다.
$$\hat r_{ui} = \mu + b_u + b_i + q_i^\top p_u$$
- $\mu$: 전체 평균 평점
- $b_u, b_i$: 사용자/문제 편향
- $p_u, q_i$: 잠재요인 벡터
최적화는 정규화된 제곱오차 최소화:
$$\min \sum_{(u,i)\in\Omega}(r_{ui}-\hat r_{ui})^2 + \lambda\left(\|p_u\|^2+\|q_i\|^2+b_u^2+b_i^2\right)$$
여기서 $\Omega$는 관측된 상호작용 쌍이다.
4. 아이템 유사도: KNN (Cosine Similarity)
문제 $i, j$의 유사도:
$$\mathrm{sim}(i,j)=\frac{v_i^\top v_j}{\|v_i\|\|v_j\|}$$
이는 “이 문제를 푼 사용자는 다음으로 무엇을 푸는가”를 보조적으로 설명하는 데 사용한다.
5. 통계 안정화 1: Empirical Bayes 정답률 (adj_rate)
관측 정답률 $\hat p_i$는 저표본에서 분산이 크다. 이를 완화하기 위해 전체 평균 $p_0$ 쪽으로 수축(shrinkage)하는 베이지안 보정을 사용한다.
$$\mathrm{adj\_rate}_i = \frac{k_i + \alpha p_0}{n_i + \alpha}$$
- $\alpha$: 가상표본 강도(현재 시스템: $\alpha=20$)
- $n_i$가 작을수록 $p_0$의 영향이 크고, $n_i$가 커질수록 관측값 $\hat p_i$에 수렴
6. 통계 안정화 2: Wilson 하한 (wilson_lower)
이항비율 신뢰구간의 보수적 하한을 사용한다.
$$ \mathrm{WL}_i = \frac{ \hat p_i + \frac{z^2}{2n_i} - z\sqrt{\frac{\hat p_i(1-\hat p_i)}{n_i}+\frac{z^2}{4n_i^2}} }{ 1+\frac{z^2}{n_i} } $$
- $z=1.96$ (95% 신뢰수준)
- Wilson 하한은 “보수적으로 보아도 이 문제가 얼마나 쉬운가”를 반영
7. p-value 계산(유의성 지표)
귀무가설 $H_0: p_i = p_0$에 대해 정규근사 양측검정을 계산한다.
$$ z_i = \frac{\hat p_i - p_0}{\sqrt{p_0(1-p_0)/n_i}},\quad p\text{-value}_i = 2(1-\Phi(|z_i|)) $$
실무 구현에서는 수치안정성을 위해 동치 형태(erfc)를 사용한다.
8. 최종 정렬 및 레벨 분류
현재 추천 목록 정렬의 우선순위:
- $\mathrm{wilson\_lower}$ 내림차순
- $\mathrm{adj\_rate}$ 내림차순
- 개인화 점수(예측 점수) 내림차순
레벨 분류(예시):
- 쉬움: $\mathrm{wilson\_lower}\ge 0.5$
- 도전: $0.2 \le \mathrm{wilson\_lower} < 0.5$
- 어려움: $\mathrm{wilson\_lower}<0.2$
9. 해석 가이드
adj_rate는 평균 수축된 안정 정답률wilson_lower는 보수적 신뢰 하한- 개인화 점수는 사용자 특이적 선호/난이도 적합도