[선형대수학]Factorization Machines

목차

• Introduction
• Factorization Machines
  • Definition
  • Characteristics
• Calculation
• Conclusion

 

[선형대수학]머신러닝과 딥 러닝의 핵심, 선형대수학의 역할과 중요성

[선형대수학]부분행렬과 분할행렬: 공통점과 차이점, ML/DL에의 응용

[선형대수학]역행렬과 행렬식의 성질, ML/DL과의 관계

[선형대수학]행렬의 해와 감소된 행 계단형(Reduced Row Echelon Form, RREF)

[선형대수학]벡터 공간(Vector Spaces)

[선형대수학]벡터 공간과 일차 독립

[선형대수학]벡터 공간과 기저, 차원 그리고 ML/DL

[선형대수학]차원의 저주: 데이터 분석의 걸림돌

[선형대수학]행렬의 랭크와 그 응용

[선형대수학]벡터의 내적과 그 응용

[선형대수학]정규직교 기저와 그람-슈미트 프로세스

[선형대수학]최소 제곱해

[선형대수학]선형변환과 고윳값의 이해: 머신러닝/딥러닝에서의 응용

[선형대수학]벡터 공간의 대각화와 그 응용 - 유사 행렬 및 머신러닝에서의 중요성

[선형대수학]특이값 분해(SVD): 기본부터 머신러닝/딥러닝까지의 응용

[선형대수학]특이값 분해와 고윳값: 공통점과 차이점

[선형대수학]실 이차 형식과 양의 정부호 행렬: 머신러닝/딥러닝에의 응용

[선형대수학]주성분 분석(Principal Component Analysis, PCA)

[선형대수학]Factorization Machines

 

Introduction

팩토라이제이션 머신(Factorization Machines, FM)은 

 

기계 학습에서 다양한 특성 간의 상호작용을 모델링하는 데 사용되는 알고리즘이다.

 

이는 특히 추천 시스템, 자연어 처리 등에서 유용하게 쓰이며,

 

선형 회귀(linear regression)와 행렬 인수분해(matrix factorization)의 개념을 활용하여

 

특성 간 복잡한 관계를 효율적으로 계산할 수 있다.

 

본 게시글에서는 팩토라이제이션 머신의 정의, 특징 및 계산 방법에 대해 자세히 설명하고자 한다.

 

Factorization Machines

 

팩토라이제이션 머신은 다차원 특성 데이터 간의 상호작용을 모델링할 수 있는 범용 예측 모델이다.

 

이 모델은 특성의 선형 조합뿐만 아니라, 특성 간의 이차 상호작용까지 고려하여 예측 정확도를 향상시키는 것이 특징이다.

 

Definition

 

FM은 입력 벡터 $x_i\in \mathbb{R}^n$에 대해 예측 값을 $\hat{y}(x)$로 출력하는 모델로, 다음과 같은 수식으로 표현된다.

 

$$\hat{y}(x)=w_0+\sum_{i=1}^{n}w_ix_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n}W_{ij}x_ix_j$$

 

여기서, $w_o, w_i는 선형 회귀의 계수이며,$W_{ij}$는 특성$x_i$와$x_j$간의 상호작용을 나타내는 계수이다.

 

여기서:

 

• $w_0$는 모델의 전역 편향(global bias)
• $w_i$는 각 특성 $x_i$의 선형 가중치
• $W_{ij}$는 두 특성 $x_i$와 $x_j$ 사이의 상호작용을 모델링하는 인수분해 가능한 가중치

이다. $W_{ij}$는 특성의 상호작용을 모델링하지만, 직접적으로 모든 $W_{ij}$값을 계산하는 것은 복잡도가 $O(n^2)$로 매우 크다.

 

Characteristics

 

FM의 가장 큰 특징은 특성 간 상호작용을 효율적으로 계산할 수 있다는 점이다.

 

이는 $W$행렬을 저차원 벡터의 내적으로 표현함으로써 가능해지며, 계산 복잡도를 $O(n^2)$에서 $O(kn)$으로 대폭 줄일 수 있다.

 

Calculation

 

계속해서 FM 예측모델을 이용해 계산 복잡도를 줄이는 과정을 따라가 보자.

 

위에 언급했듯이, FM의 예측 모델은 주어진 입력 벡터 $x\in \mathbb{R}^n$에 대해 다음과 같이 정의된다.

 

$$\hat{y}(x)=w_0+\sum_{i=1}^{n}w_ix_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n}W_{ij}x_ix_j$$

 

여기서 행렬$W_{ij}$는 저차원 벡터의 내적으로 바꿔 표현할 수 있는데,

 

$$W_{ij} = <v_i, v_j> = \sum_{f=1}^{k}v_{if}v_{jf}$$

 

그 근거는 $W$가 대칭이자 Positive Semi-definite이기 때문이다.

 

• 대칭 행렬(Symmetric Matrix): $W=W^T$
• Positive Semi-definite: 모든 벡터 $x$에 대해 $x^TWx \geq 0$, 혹은 $W=VV^T$.이는 의도적인 사항이다.

위와 같은 조건을 가지고 계산을 이어가면 다음과 같은 결과를 얻을 수 있다.

 

$$\begin{align*} \hat{y}(x) &= w_0+\sum_{i=1}^{n}w_ix_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n}<v_i, v_j>x_ix_j\\    &= w_0+\sum_{i=1}^{n}w_ix_i + \frac{1}{2}(\sum_{i=1}^{n}\sum_{j=1}^{n}<v_i, v_j>x_ix_j - \sum_{i=1}^{n}<v_i, v_j>x_i^2)\\ &= w_0+\sum_{i=1}^{n}w_ix_i + \frac{1}{2}(\sum_{f=1}^{k}(\sum_{i=1}^{n}v_{if}x_i)^2- \sum_{i=1}^{n}\sum_{f=1}^{k}v_{if}^2x_i^2)) \\ &=w_0+\sum_{i=1}^{n}w_ix_i + \frac{1}{2}\sum_{f=1}^{k}((\sum_{i=1}^{n}v_{if}x_i)^2- \sum_{i=1}^{n}v_{if}^2x_i^2) \end{align*}$$

 

여기서 $\sum_{f=1}^{k}(\sum_{i=1}^{n}v_{if}x_i)^2$ 항은 모든 특성 간의 상호작용을 포함하며,

 

이를 계산하는 복잡도는 각 특성에 대해 $k$차원 벡터를 한 번만 계산하면 되므로 $O(kn)$이 된다.

 

Conclusion

 

팩토라이제이션 머신(FM)은 복잡한 특성 간 상호작용을 효율적으로 모델링할 수 있는 강력한 도구이다.

 

이를 통해 추천 시스템, 자연어 처리 등의 다양한 분야에서 더욱 정확한 예측을 가능하게 한다.

 

FM의 이해와 적용은 머신러닝 모델의 성능을 극대화하는 데 있어 필수적인 요소 중 하나라 할 수 있다.