Factorization Machine

정의

Factorization Machine (FM)은 Rendle (2010)이 제안한 범용 예측 모델로, 모든 feature 쌍 간의 상호작용을 latent factor 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$

$w_0 \in \mathbb{R}$ : global bias
$\mathbf{w} \in \mathbb{R}^n$ : feature별 weight
$\mathbf{v}_i \in \mathbb{R}^k$ : feature $i$ 의 latent vector ( $k$ : embedding 차원)
$\langle \mathbf{v}_i, \mathbf{v}_j \rangle = \sum_{f=1}^{k} v_{i,f} \cdot v_{j,f}$ : 두 latent vector의 내적

계산 트릭: $O(kn)$ 선형 시간

Naive한 pairwise 계산은 $O(kn^2)$ 이지만, 다음 등식을 이용하면 $O(kn)$ 으로 줄일 수 있다:

$\sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j = \frac{1}{2} \sum_{f=1}^{k} \left[ \left( \sum_{i=1}^{n} v_{i,f} x_i \right)^2 - \sum_{i=1}^{n} v_{i,f}^2 x_i^2 \right]$

이는 $(\sum a_i)^2 = \sum a_i^2 + 2\sum_{i<j} a_i a_j$ 항등식에서 유도된다.

직관적 이해

추천시스템에서 user-item interaction 데이터는 극도로 희소(sparse) 하다. 예를 들어 “User A가 Item B를 클릭했는가?”의 직접 관측은 매우 적다.

FM의 핵심 아이디어: 각 feature에 $k$ 차원 latent vector를 부여하면, 직접 관측되지 않은 feature 쌍의 상호작용도 일반화(generalize) 할 수 있다. Feature $i$ 와 $j$ 의 상호작용 강도를 독립 파라미터 $w_{ij}$ 로 추정하는 대신, $\langle \mathbf{v}_i, \mathbf{v}_j \rangle$ 로 모델링하면:

데이터 효율성: 한 feature가 참여한 모든 상호작용에서 해당 latent vector가 학습됨
일반화: 학습된 latent vector를 통해 관측되지 않은 쌍의 상호작용 예측 가능
파라미터 효율성: $O(n^2)$ 개의 독립 파라미터 대신 $O(kn)$ 개만 필요

Matrix Factorization과의 관계

Matrix Factorization (MF)는 FM의 특수 사례이다.

MF의 user $u$ 와 item $i$ 에 대한 예측:

$\hat{y} = \mu + b_u + b_i + \langle \mathbf{p}_u, \mathbf{q}_i \rangle$

이를 FM으로 표현하면, input vector $\mathbf{x}$ 를 user와 item의 one-hot encoding으로 구성:

$\mathbf{x} = (\underbrace{0, \ldots, 1, \ldots, 0}_{\text{user}}, \underbrace{0, \ldots, 1, \ldots, 0}_{\text{item}})$

이 경우 FM의 2차 항에서 활성화되는 유일한 상호작용이 $\langle \mathbf{v}_u, \mathbf{v}_i \rangle$ 이므로, MF와 동치가 된다.

기준	Matrix Factorization	Factorization Machine
입력	user-item rating matrix	임의의 feature vector
상호작용	user-item만	모든 feature 쌍
Side info	별도 처리 필요	자연스럽게 통합
범용성	추천(CF)에 특화	분류/회귀/랭킹 모두 가능

다른 접근법과의 비교

모델	Feature Interaction	희소 데이터	계산 복잡도	비고
Linear Model	없음	가능	$O(n)$	상호작용 무시
Polynomial Regression	독립 $w_{ij}$	불가	$O(n^2)$	희소 시 $w_{ij}$ 학습 불가
SVM (Polynomial kernel)	$w_{ij}$	불가	$O(n^2)$	dual form, 희소 일반화 불가
FM	$\langle \mathbf{v}_i, \mathbf{v}_j \rangle$	가능	$O(kn)$	latent vector로 일반화

핵심 차이: Polynomial Regression과 SVM은 $w_{ij}$ 를 독립 파라미터로 추정하므로 관측 데이터가 없으면 학습이 불가하지만, FM은 latent vector 분해를 통해 간접적으로 학습한다.

FM 변형 및 발전 계보

Factorization Machine

Mermaid source (click to expand)

> flowchart TD
>     FM["<b>FM</b><br/>Rendle 2010<br/>2차 feature interaction"] --> FFM["<b>FFM</b><br/>Juan et al. 2016<br/>field-aware latent vectors"]
>     FM --> DeepFM["<b>DeepFM</b><br/>Guo et al. 2017<br/>FM + DNN 병렬 결합"]
>     FM --> AFM["<b>AFM</b><br/>Xiao et al. 2017<br/>attention-based interaction"]
>     DeepFM --> xDeepFM["<b>xDeepFM</b><br/>Lian et al. 2018<br/>explicit + implicit<br/>high-order interaction"]
>     DeepFM --> AutoInt["<b>AutoInt</b><br/>Song et al. 2019<br/>self-attention interaction"]
>

모델	핵심 개선	Interaction Order
FM	Latent vector 내적으로 2차 상호작용	2차
FFM	Field별 서로 다른 latent vector 사용	2차 (field-aware)
DeepFM	FM (explicit 2차) + DNN (implicit high-order) 병렬 결합	2차 + high-order
AFM	Attention으로 중요한 interaction에 가중치	2차 (weighted)
xDeepFM	CIN으로 explicit high-order interaction 학습	explicit high-order

장단점

장점:

$O(kn)$ 선형 시간 학습 및 추론: 대규모 희소 데이터에 적합
희소 데이터에서 관측되지 않은 feature 쌍도 일반화 가능
범용 모델: CF, 분류, 회귀, 랭킹에 모두 적용 가능
MF, SVD++, PITF 등의 기존 모델을 특수 사례로 포함
Side information (context features)을 자연스럽게 통합

단점:

2차 상호작용만 모델링 (higher-order는 DeepFM 등 후속 모델 필요)
DNN 기반 모델 대비 표현력(expressiveness) 한계
Embedding 차원 $k$ 선택에 민감
매우 고차원 상호작용이 중요한 태스크에서는 부족

구현

FM의 2차 항 핵심 연산 (PyTorch):

import torch
import torch.nn as nn

class FMInteraction(nn.Module):
    """FM 2차 상호작용 레이어"""
    def __init__(self, num_features: int, k: int):
        super().__init__()
        self.V = nn.Parameter(torch.randn(num_features, k) * 0.01)

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        # x: (batch_size, num_features)
        # O(kn) 계산 트릭 적용
        vx = x @ self.V                          # (batch, k)
        square_of_sum = vx ** 2                   # (Σ v_i x_i)²
        sum_of_square = (x ** 2) @ (self.V ** 2)  # Σ v_i² x_i²
        interaction = 0.5 * (square_of_sum - sum_of_square).sum(dim=1)
        return interaction  # (batch_size,)

참고 논문

rendleFactorizationMachines2010 - FM 원논문; SVM + factorization model 결합
guoDeepFMFactorizationMachineBased2017 - DeepFM; FM + DNN 병렬 결합으로 CTR 예측
Juan, Y., et al. (2016). Field-aware factorization machines for CTR prediction. RecSys 2016.
Lian, J., et al. (2018). xDeepFM: Combining explicit and implicit feature interactions for recommender systems. KDD 2018.

정의