Factorization Machine (FM)

💡 들어가며

추천 시스템은 현대 디지털 환경에서 사용자 경험을 개인화하는 핵심 기술입니다. 특히 식품 분야에서 개인의 취향과 영양 요구를 고려한 추천은 건강한 식생활을 지원하는 중요한 요소가 되었습니다. 오늘은 2010년에 발표된 Factorization Machine(FM)에 대해 살펴보고, 이 모델이 식품 특성 정보를 함께 활용하여 어떻게 정교한 추천을 가능하게 하는지 알아보겠습니다.

---

I. Matrix Factorization의 이해와 한계

Matrix Factorization(MF)는 User와 Item 간의 평가 정보를 나타내는 Rating Matrix를 User Latent Matrix와 Item Latent Matrix로 분해하는 기법입니다.

Rating Matrix는 (User의 수) × (Item의 수)로 구성된 행렬인데, 각 칸에는 각 유저가 기록한 해당 아이템에 대한 평가가 수치로 기록됩니다. 대부분의 경우 모든 유저가 모든 아이템을 평가하지 않기 때문에 Rating Matrix는 일반적으로 Sparse Matrix(희소 행렬)가 됩니다. MF는 이러한 행렬 분해 과정에서 빈칸을 채울만한 평점을 예측하는 과정이라고 볼 수 있습니다.

 

평가 데이터는 Explicit Feedback(명시적 지표)으로 평점이나 별점이 될 수도 있지만, Implicit Feedback(암시적 지표) 역시 충분히 활용 가능합니다.

Rating Matrix는 MF를 통해 다음과 같이 두 개의 행렬로 나누어집니다:

• User Latent Matrix(U) = (User의 수) × K
• Item Latent Matrix(I) = (Item의 수) × K
• Rating Matrix(R) = (User × K) × (K × Item) => User × Item

여기서 K는 잠재 요인의 차원을 의미하며, 이 두 행렬 중 하나를 전치(Transpose)하여 행렬곱을 수행하면 원래의 Rating Matrix 형태로 돌아오게 됩니다.

Latent Matrix의 각 행(row)은 유저나 아이템의 잠재적 정보를 저장하는 벡터로, User Matrix의 유저(u) 행과 Item Matrix의 아이템(i) 행의 내적을 수행하면 "유저 u의 아이템 i에 대한 평가"가 계산됩니다.

>> Matrix Factorization의 한계

기존 Matrix Factorization은 유저와 아이템, 그리고 평점 정보만을 활용합니다. 즉, 유저와 아이템의 다양한 특성 정보는 활용하지 못한다는 한계가 있습니다. 식품 분야에서는 식재료의 영양 성분, 조리법, 알레르기 정보 등 다양한 특성이 중요한데, 이러한 정보를 추천 시스템에 반영하기 어렵다는 문제가 있었습니다.

---

II. 추천 시스템의 도전 과제

SVM 활용의 어려움

SVM(Support Vector Machine)은 General Predictor로서 데이터 형태에 크게 규제받지 않고 분류, 회귀 등 다양한 작업을 수행할 수 있어 머신러닝 및 데이터 마이닝 분야에서 자주 사용됩니다.

하지만 추천 시스템의 경우, 대부분의 유저가 모든 아이템을 평가하지 않기 때문에 데이터가 매우 Sparse한 환경이 일반적입니다. 이러한 환경에서는 SVM의 복잡한 커널 트릭이 잘 작동하지 않는 한계가 있습니다.

협업 필터링의 제한점

추천 시스템을 대표하는 알고리즘 중 하나는 협업 필터링의 일종인 Latent Factor 모델입니다. Matrix Factorization은 가장 대중적인 Latent Factor 모델로, SVD와 유사하게 유저와 아이템을 f차원의 잠재 공간(latent factor space)으로 매핑합니다.

Latent Factor는 User, Item 사이에 존재하는 패턴을 통해 찾을 수 있으며, f개의 latent factor로 표현된 user, item 벡터의 내적으로 둘 사이의 상호 관계를 계산할 수 있습니다.

---

III. Factorization Machine

Factorization Machine(FM)은 SVM과 Matrix Factorization의 장점을 결합한 모델로, 다음과 같은 세 가지 주요 특징을 가지고 있습니다:

1. Sparse 데이터 처리 능력: SVM으로 학습하기 어려운 Sparse 환경에서도 파라미터를 효과적으로 추정 가능합니다.
2. 선형 복잡도(Linear Complexity): 선형 복잡도를 가지고 있어 SVM과 같은 쌍대문제를 풀지 않아도 되므로 계산 효율성이 높습니다.
3. 범용성(General Predictor): 어떠한 실수 벡터 형태의 데이터에도 적용 가능한 General Predictor로서의 역할을 수행합니다.

Input 표현 방식

FM의 가장 큰 특징은 다양한 Feature를 하나의 벡터로 통합(concatenate)하여 사용한다는 점입니다. 이는 다음과 같은 장점을 제공합니다:

• 어떠한 암시적(implicit) 특성이라도 실수 형태로 하나의 특성 벡터에 추가할 수 있습니다.
• 범주형(Categorical) 특성은 One-hot 인코딩 형태로 표현할 수 있습니다.
• Feature engineering을 통해 SVM과 유사하게 데이터를 표현할 수 있습니다.

2-way Factorization Machine Model

FM은 기본적으로 선형 회귀 모델을 확장한 형태로, 변수들 간의 상호작용(interaction)까지 모델링합니다.

선형 회귀 모델은 다음과 같이 표현됩니다:

 

$$\hat{y}(x) = w_0 + \sum_{i=1}^{n} w_i x_i, w_0 \in \mathbb{R}, w \in \mathbb{R}^n$$

 

이 모델의 장점은 계산이 간단하고 빠르다는 것이지만, 변수 간 상호작용이 반영되지 않아 정확한 예측이 어렵다는 단점이 있습니다.

FM은 이 선형 모델에 변수들 간의 상호작용을 추가하여 다음과 같이 확장합니다:

 

$$\hat{y}(x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} W_{ij}x_i x_j, w_0 \in \mathbb{R}, w \in \mathbb{R}^n, W \in \mathbb{R}^{n \times n}$$

 

여기서 $W_{ij}x_i x_j$는 상호작용 효과를 표현하기 위한 항으로, 변수들 간의 곱을 모델에 추가합니다.

FM의 혁신적인 점은 다항 회귀와 유사하지만, 상호작용 항의 계수를 단순한 값이 아닌 변수 간 잠재 벡터(Latent Vector)의 내적으로 사용한다는 것입니다.

파라미터 분해를 통한 효율성 증대

FM은 각 파라미터마다 임베딩 벡터(embedding vector)를 생성하여 내적 연산을 수행합니다. 이 과정에서 계산량이 늘어날 수 있지만, 수학적 분해를 통해 계산 효율성을 높일 수 있습니다.

 

$$\hat{y}(\mathbf{x}) := w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle\mathbf{v}_i, \mathbf{v}_j\rangle x_i x_j$$

 

여기서 $\langle\mathbf{v}_i, \mathbf{v}_j\rangle$는 $i$번째와 $j$번째 특성에 대한 k차원 잠재 벡터의 내적을 의미합니다:

$$W_{ij} = \langle\mathbf{v}i, \mathbf{v}j\rangle = \sum{f=1}^{k} v{i,f} v_{j,f}$$

이러한 분해 방식을 통해 FM은 개별 변수의 가중치만을 사용하는 것이 아니라, factorizing(분해)을 통해 interaction을 효과적으로 모델링합니다. 이로 인해 sparsity한 상황에서도 high-order interaction의 파라미터를 추정할 수 있게 됩니다.

d-way Factorization Machine

FM은 2개 특성 간의 상호작용뿐만 아니라, d개 특성 간의 상호작용도 모델링할 수 있는 d-way Factorization Machine으로 확장 가능합니다. d-way FM 역시 선형 시간의 계산 복잡도를 유지하여 효율적인 학습이 가능합니다.

---

IV. 실험 결과 분석

Factorization Machine의 성능을 평가하기 위해 Netflix 데이터셋과 같은 매우 sparse한 환경에서 SVM과 비교 실험을 진행한 결과, 흥미로운 발견이 있었습니다.

 

 

SVM은 Sparse한 환경에서 학습에 실패한 반면, FM은 차원이 증가함에 따라 학습이 안정적으로 진행되었으며 예측 오차(RMSE)가 점진적으로 감소하는 추세를 보였습니다. 특히 잠재 요인의 차원(k)이 60 이상일 때 FM의 성능이 최적화되는 것으로 나타났습니다.

---

V. 결론

Factorization Machine은 SVM과 Matrix Factorization의 장점을 결합한 혁신적인 추천 시스템 알고리즘으로, 특히 식품과 같이 다양한 특성 정보를 고려해야 하는 도메인에서 큰 잠재력을 가지고 있습니다.

FM의 주요 강점은 다음과 같습니다:

1. 특성 정보의 유연한 통합: 다양한 유형의 식품 특성 정보를 하나의 모델에 통합할 수 있습니다.
2. 희소 데이터 처리 능력: 모든 사용자가 모든 식품을 평가하지 않는 실제 환경에서 효과적으로 작동합니다.
3. 계산 효율성: 선형 복잡도를 유지하여 대규모 식품 데이터베이스에서도 효율적으로 학습 가능합니다.
4. 확장성: 다양한 특성 간의 상호작용을 모델링할 수 있어 복잡한 식품 선호도 패턴을 포착할 수 있습니다.

앞으로 건강과 웰빙에 대한 관심이 높아지는 시대에, Factorization Machine은 개인의 건강 목표와 식품 특성을 고려한 맞춤형 식품 추천 시스템을 구축하는 데 중요한 역할을 할 것으로 기대됩니다.

---

참고 문헌:

• Rendle, S. (2010). Factorization machines. In 2010 IEEE International Conference on Data Mining (pp. 995-1000).
• Rendle, S. (2012). Factorization machines with libFM. ACM Transactions on Intelligent Systems and Technology (TIST), 3(3), 1-22.