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}$ : 전역 bias
$\mathbf{w} \in \mathbb{R}^n$ : 특성별 weight
$\mathbf{v}_i \in \mathbb{R}^k$ : 특성 $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)$ 선형 시간

쌍별(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$ 항등식에서 나온다.

직관적 이해

추천(recommendation)에서 사용자-아이템 상호작용 데이터는 극도로 희소(sparse) 하다. 예를 들어 “사용자 A가 아이템 B를 클릭했는가?”를 직접 관측한 경우는 매우 적다.

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

데이터 효율성: 한 특성이 참여한 모든 상호작용에서 그 latent vector가 함께 학습된다.
일반화: 학습된 latent vector로 관측되지 않은 쌍의 상호작용도 예측한다.
파라미터 효율성: $O(n^2)$ 개의 독립 파라미터 대신 $O(kn)$ 개만 있으면 된다.

Matrix Factorization과의 관계

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

MF에서 사용자 $u$ 와 아이템 $i$ 에 대한 예측은 다음과 같다.

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

이를 FM으로 표현하려면 입력 벡터 $\mathbf{x}$ 를 사용자와 아이템의 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
입력	사용자-아이템 평점 행렬	임의의 특성 벡터
상호작용	사용자-아이템만	모든 특성 쌍
부가 정보(side info)	별도 처리 필요	자연스럽게 통합
범용성	추천(CF)에 특화	분류·회귀·랭킹 모두 가능

다른 접근법과의 비교

모델	특성 상호작용	희소 데이터	계산 복잡도	비고
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)$ 선형 시간으로 학습·추론하므로 대규모 희소 데이터에 적합하다.
희소 데이터에서 관측되지 않은 특성 쌍도 일반화한다.
범용 모델로 CF, 분류, 회귀, 랭킹에 모두 적용된다.
MF, SVD++, PITF 등 기존 모델을 특수 사례로 포함한다.
부가 정보(context features)를 자연스럽게 통합한다.

단점:

2차 상호작용만 모델링한다(고차 상호작용은 DeepFM 등 후속 모델이 필요하다).
DNN 기반 모델보다 표현력(expressiveness)이 떨어진다.
임베딩 차원 $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.

정의