Introductory Guide – Factorization Machines & their application on huge datasets (with codes in Python)

참고 : https://www.analyticsvidhya.com/blog/2018/01/factorization-machines/ 링크의 글을 번역한 글입니다.

Introduction

나는 아직도 클릭 예측 문제로 처음 만났던 순간을 기억합니다. 이전에는 나는 데이터 과학을 배우고 있었고 나의 진전에 대해 기분이 좋았습니다. ML hackathons에 대한 자신감을 갖기 시작했고 나는 몇 가지의 도전을 하기로 결심했습니다.

더 잘하기 위해서, 나는 16GB RAM과 i7 프로세서를 갖춘 기계를 조달했습니다. 그러나 데이터 세트를 처음 보았을 때 불안감이 있었습니다. 압축을 풀 때의 데이터는 50GB 이상이었습니다. 그런 데이터 세트의 클릭을 예측하는 방법을 알지 못했습니다. 고맙게도 Factorization 기계가 나를 구조해 주었습니다.

클릭 예측 (Click Prediction) 문제 또는 추천 시스템에서 작업 한 사람은 비슷한 상황(데이터 사이즈가 큰 상황)에 처했을 것입니다. 데이터 세트가 크기  때문에 이러한 데이터 세트에 대한 예측은 제한된 계산 리소스로 인해 어려워집니다.

추가적으로 대부분의 경우 이러한 데이터 세트는 희소(Sparse)합니다.  예측에 중요하지 않은 몇 가지 기능이 있기 때문에, Factorization은 원시 데이터로부터 가장 중요한 잠재 or 숨겨진 변수를 추출해 내는데에 많은 도움이 됩니다.

Factorization은 low dimension dense matrix를 사용하여 목표와 예측자 사이 동일한 관계를 표현하는 데 도움이됩니다. 이 기사에서는 파이썬을 사용한 구현으로 회귀 / 분류 문제에서 FM(Factorization Machines)과  FFM(Field Aware Factorization Machines)에 대해 설명합니다. 

Table of Contents

• Factorization의 직관적 이해
• 어떻게 FM이 다항식과 선형모델을 대체합니까?
• FFM의 사용 영역
• xLearn Library를 사용한 실습
• 정리

1. Factorization의 직관적 이해(Intuition behind Factorization)

matrix factorization의 직관적 이해를 얻기 위해 다음과 같은 예시를 생각해 봅시다. 우리는 5명의 유저에 대해 영화평점을 1~5점으로 나눌 것 입니다.

	Star Wars 1	Inception	Godfather	The Notebook
USER1	5	3	-	1
USER2	4	-	-	1
USER3	1	1	-	5
USER4	1	-	-	4
USER5	-	1	5	4

우리는 표에서 평점이 비어있는 부분을 관찰하였고 비어있는 부분을 예측할 방법을 고안했다. matrix factorization을 이용해서 이 문제를 해결하는 직관은 고객이 영화의 평점을 어떻게 매기는지에 대한 몇몇 latent features(관측불가능한 특징들)이 있다는 점이다. 예를들어, 유저A와 B가 Ai Pacino 배우의 팬이라면 영화의 평점을 높게 매길 것이다. (여기서 배우를 향한 선호가 숨겨진 변수이다. )

우리가 이제 K개의 latent(hidden) features을 계산한다고 가정하자. 우리가 해야할 일은 아래의 Matrix를 찾는 일이다.

이제 P의 각 행은 사용자와 변수간의 연관성을 나타내고 Q의 각 행은 동일한 강도를 나타냅니다. 유저 ui에 의해 매겨진 영화 평점 dj를 얻기 위해, 우리는 아래의 rij를 계산할 수 있어야 한다. 

우리가 해야 할 일은 P와 Q 행렬을 계산하는 것 뿐입니다. 이를 위해 gradient descent 알고리즘을 사용합니다. 목표는 실제 등급과 P 및 Q로 추정 된 오차의 제곱을 최소화하는 것 입니다. 오차의 제곱은 다음 방정식에서 주어집니다.

이제 pik와 qkj에 대한 업데이트 규칙을 정의해야합니다. 그래디언트 디센트의 업데이트 규칙은 그라디언트 오류를 최소화하는것으로 정의됩니다. 

그래디언트를 얻은 후에 이제 pik 및 qkj에 대한 업데이트 규칙을 공식화 할 수 있습니다. 

여기서 α는 업데이트 크기를 제어 할 수있는 학습 속도입니다. 위의 업데이트 규칙을 사용하여 오류가 최소로 수렴 될 때까지 반복적으로 작업을 수행 할 수 있습니다. 다음 방정식을 사용하여 계산 된 전체 오류를 확인하고 프로세스를 중단해야하는 시점을 결정할 수 있습니다.

위의 솔루션은 간단하며 기존의 등급이 정확하게 예측되지만 종종 보이지 않는 데이터에서도 잘 일반화되지 않는 경우 초과 적용으로 이어진다. 이 문제를 해결하기 위해 우리는 각각 P와 Q의 사용자 특징과 영화 특징 벡터를 제어하고 등급에 대한 좋은 근사치를 제공하는 정규화 매개 변수 β를 도입 할 수 있습니다.

파이썬 구현에 관심이있는 사람들에게 똑같은 세부 정보가이 링크로 연결될 수 있습니다. 위의 방법론을 사용하여 P와 Q를 계산하면 대략적인 평가 매트릭스가 다음과 같이 표시됩니다.

	Star Wars 1	Inception	Godfather	The Notebook
USER1	4.97	2.98	2.18	0.98
USER2	3.97	2.4	1.97	0.99
USER3	1.02	0.93	5.32	4.93
USER4	1.00	0.85	4.59	3.93
USER5	1.36	1.07	4.89	4.12

우리가 기존 등급을 다시 생성 할 수있는 방법에 주목하십시오. 또한 알 수없는 등급 값에 대해 공정한 근사치를 얻을 수 있습니다.

2. 어떻게 FM이 다항식과 선형모델을 대체합니까? (How Factorization Machines trump Polynomial and linear models?)

클릭 예측 데이터 세트의 몇 가지 예제를 고려해 보겠습니다. 데이터 세트는 스포츠 뉴스 웹 사이트 (게시자) 및 스포츠 장비 회사 (광고주)를 통해 광고 클릭을 예측합니다.

Clicked	Publisher(P)	Advertiser(A)	Gender(G)
Yes	ESPN	Nike	Male
No	NBC	Adidas	Male

FM 또는 FFM에 관해 이야기 할 때 데이터 세트의 각 열 (게시자, 광고주 ...)은 필드로 참조되고 각 값 (ESPN, Nike ...)은 피쳐 (feature)라고합니다.

선형 또는 로지스틱 모델링 기법은 훌륭하고 다양한 문제에서 잘 수행되지만 단점은 모델이 모든 변수 또는 기능의 효과를 조합이 아닌 개별적으로 학습한다는 것입니다.

여기서 w0, wESPN 등은 매개 변수를 나타내고 xESPN, xNike는 데이터 집합의 개별 기능을 나타냅니다. 위의 함수에 대한 로그 손실을 최소화함으로써 로지스틱 회귀를 얻습니다. 피쳐 상호 작용을 포착하는 한 가지 방법은 각 제품을 개별 변수로 취급하는 피쳐의 각 쌍의 제품에 대한 개별 매개 변수를 학습하는 다항식 함수입니다. 

우리는 한 용어에 2 개의 특징을 조합하는 것을 고려하고 있기 때문에 Poly2 모델이라고도 할 수 있습니다. 

• 이 문제는 중형 데이터 세트의 경우에도, 메모리와 학습하는 데 걸리는 시간이 많이 든다는 점입니다.
• 두 번째로, sparse 데이터 세트의 경우, 이 선형모델은 모든 가중치 또는 매개 변수를 신뢰성있게 습득하기에는 좋지 않을 것입니다. 즉, 각 가중치를 신뢰할 수 있게 하기 위해 각 피쳐 쌍에 대한 충분한 훈련이 되지 않습니다.

FM to the rescue

FM은 pairwise feature 상호 작용을 고려하는 문제를 해결합니다. 그것은 우리가 모델의 특징들의 쌍으로 된 조합으로부터의 신뢰할 수 있는 정보 (잠복 된 특징들)에 기초하여 훈련시킬 수 있게 한다. FM은 또한 우리가 시간과 공간의 복잡성 측면에서 효율적인 방법으로 이것을 가능하게 합니다. 쌍방향 특징 상호 작용을 저 차원 벡터의 내적 (길이 = k)으로 모델링합니다. 이것은 degree = 2 인수 분해 기계에 대한 다음 방정식으로 설명됩니다.

FM (k = 3)의 각 매개 변수는 다음과 같이 설명 할 수 있습니다.

여기에서 각 용어에 대해 2 개의 피쳐에 해당하는 잠재 인자의 내적을 계산했습니다.

모델링 관점에서 보았을 때 이것은 강력한 특징입니다. 왜냐하면 각 기능이 비슷한 기능이 서로 인접 해있는 공간으로 변형되기 때문입니다. 간단히 말하면, 내적은 기본적으로 숨겨진 피쳐의 유사성을 나타내고 피쳐가 이웃에 있을 때 더 높습니다.

코사인 함수는 theta가 0 일 때 1 (최대)이고 theta가 180 ° 일 때 -1로 감소합니다. theta가 0에 가까울 때 유사도가 최대라는 것이 분명합니다.

FM의 또 다른 큰 이점은 위의 방정식에 간단한 수학적 조작을 사용하여 선형 시간 복잡도에서 모든 쌍으로 상호 작용을 모델링하는 용어를 계산할 수 있다는 것입니다. 이에 필요한 정확한 단계를보고 싶다면 링크의 최초 Factorization Machines 연구 논문을 참조하십시오.

Example: Demonstration of how FM is better than POLY2

다음과 같은 인위적 클릭률 (CTR) 데이터를 고려하십시오. 

이것은 Publisher 및 Advertiser로 구성된 데이터 집합입니다. 광고는 팝업으로 나타나며 사용자는 광고를 클릭하거나 닫을 수 있습니다.

• 세번째 행 (ESPN, Adidas)에 대한 Unclicks는 하나뿐입니다. Poly2의 경우 매우 낮은 웨이트 (wespN) 인 Adidas는이 쌍에 대해 배울 수 있습니다. FM의 경우 (ESPN, Adidas)의 예측이 wESPN · wAdidas에 의해 결정되고 wESPN 및 wAdidas가 다른 기능 쌍 (예 : (ESPN, Nike), (NBC, Adidas))에서도 학습되기 때문에 FM의 경우, 예측이 더 정확할 수 있습니다. 
• 또 다른 예는 쌍 (NBC, Gucci)에 대한 교육 데이터가 없다는 것입니다. Poly2의 경우이 쌍의 예측은 0이지만 FM의 경우 wNBC 및 wGucci는 다른 쌍에서 배울 수 있기 때문에 의미있는 예측을 수행 할 수 있습니다. 

3. FFM의 사용 영역(Field-Aware Factorization Machines)

Clicked	Publisher(P)	Advertisor(A)	Gender(G)
Yes	ESPN	Nike	Male

FFM을 이해하려면 필드의 의미를 깨달을 필요가 있습니다. 필드는 일반적으로 특정 기능을 포함하는 더 광범위한 범주입니다. 위의 예제 에서 필드는 Publisher (P), Advertiser (A) 및 Gender (G)입니다. 

• FM에서 모든 피쳐는 다른 피쳐와 함께 잠복 효과를 배우기 위해 하나의 잠복 벡터 v만을가집니다. ESPN을 예로 들자면, wESPN은 Nike (wESPN · wNike)와 Male (wESPN.wMale)의 잠복 효과를 배우는 데 사용됩니다.
• 그러나 ESPN과 Male은 서로 다른 분야에 속하기 때문에 (ESPN, Nike)와 (ESPN, Male)의 잠재 효과는 다를 수 있습니다. 두 경우 모두 내적 요소에 대해 동일한 매개 변수를 사용하기 때문에 FM는 이를 포착하지 않습니다.
• FFM에서, 각 피처는 몇 개의 잠재적 벡터를 가지고 있습니다. 예를 들어, ESPN과 Nike의 상호 작용 용어를 고려할 때 ESPN의 숨겨진 기능은 표기법 (wESPN, A)를 가지며 A (광고주)는 ​​Nike 기능의 필드를 나타냅니다. 성별 필드에서도 마찬가지로 다른 매개 변수 인 wESPN, G가 학습됩니다. (아래의 예제를 보고 이해하는게 빠를 것 같습니다.)

FFM은 Criteo, Avazu, Outbrain이 주관하는 3 회 CTR (클릭률) 대회에서 1 위를 차지하기 위해 필수적이었으며 RecSys Challenge 2015의 3 위를 획득했습니다. CTR 데이터 세트는 Kaggle에서 액세스 할 수 있습니다.

4. xLearn Library를 사용한 실습(Implementation using xLearn Library in Python)

파이썬에서 가장 널리 사용되는 라이브러리는 다음과 같습니다.

Package Name	Description
LibFM	Earliest library by the author himself for FMs
LibFFM	Library exclusively FFMs
xLearn	Scalable ML package for oth FM & FFMs
tffm	Tensorflow implemetation of arbitary order FMs

데이터 세트에서 FM을 사용하려면 libSVM 형식이라는 특정 형식으로 변환해야합니다. 교육 및 테스트 데이터 파일의 형식은 다음과 같습니다.

<label> <feature1> : <value1> <feature2> : <value2> ...

범주 형 필드의 경우 해당 기능은 고유하게 인코딩되고 값 1이 할당됩니다. 위의 그림에서 ESPN은 코드 1로 표시되고, Nike는 코드 2로 표시됩니다. 각 줄에는 이에 상응하는 훈련 예가 들어 있으며 '\ n'또는 줄 바꿈 문자로 끝납니다. 

• 분류 (이진 / 다중 클래스)의 경우 <label>은 클래스 레이블을 나타내는 정수입니다. 
• 회귀 분석의 경우 <label>은 임의의 실수 일 수있는 대상 값입니다.
• 테스트 파일의 레이블은 정확성이나 오류를 계산하는 데에만 사용됩니다. 알 수없는 경우 첫 번째 열을 숫자로 채울 수 있습니다.

마찬가지로 FFM의 경우 데이터를 libffm 형식으로 변환해야합니다. 여기서 ffm은 학습을위한 필드 정보를 필요로하기 때문에 필드를 인코딩해야합니다. 같은 형식은 다음과 같습니다.

<label> <field1> : <feature1> : <value1> <field2> : <feature2> : <value2>

수치적인 특징에 관한 중요한 노트(Important note on numerical features)

수치 적 특징은 이산 적이어야 하며 (특정 범위의 전체 범위를 작은 범위로 나누고 각 범위를 별도로 분류하여 분류함으로써 범주 적 특징으로 변환 된 후) 위에서 설명한 것처럼 libffm 형식으로 변환해야합니다.

또 다른 가능성은 feature 값과 동일한 더미 필드를 추가하는 것입니다. 특정 행에 대한 숫자 피쳐가됩니다 (예 : 값 45.3의 피쳐를 1 : 1 : 45.3으로 변환 할 수 있음). 그러나 더미 필드는 단순히 기능의 중복이기 때문에 유익하지 않을 수 있습니다.

xLearn

최근 출시 된 xLearn 라이브러리는 다양한 데이터 세트에서 FM 및 FFM 모델을 구현하는 빠른 솔루션을 제공합니다. libfm 및 libffm 라이브러리보다 훨씬 빠르며 모델 테스트 및 튜닝에 더 나은 기능을 제공합니다. 

여기서 크리 테오의 클릭 예측 도전에서 나온 CTR 데이터 세트의 작은 샘플 (1 %)에 대한 FFM의 예를 설명합니다.

먼저 xLearn이 모델에 적합하도록 필요한 데이터 세트를 libffm 포맷으로 변환해야합니다. 다음 함수는 표준 데이터 프레임 형식의 데이터 집합을 libffm 형식으로 변환하는 작업을 수행합니다.

df = Dataframe to be converted to ffm format

Type = Train/Test/Val

Numerics = list of all numeric fields

Categories = list of all categorical fields

Features = list of all features except the Label and Id

# Based on Kaggle kernel by Scirpus

def convert_to_ffm(df,type,numerics,categories,features):

    currentcode = len(numerics)

    catdict = {}

    catcodes = {}

    # Flagging categorical and numerical fields

    for x in numerics:

         catdict[x] = 0

    for x in categories:

         catdict[x] = 1

    

    nrows = df.shape[0]

    ncolumns = len(features)

    with open(str(type) + "_ffm.txt", "w") as text_file:

    # Looping over rows to convert each row to libffm format

    for n, r in enumerate(range(nrows)):

         datastring = ""

         datarow = df.iloc[r].to_dict()

         datastring += str(int(datarow['Label']))

         # For numerical fields, we are creating a dummy field here

         for i, x in enumerate(catdict.keys()):

             if(catdict[x]==0):

                 datastring = datastring + " "+str(i)+":"+ str(i)+":"+ str(datarow[x])

             else:

         # For a new field appearing in a training example

                 if(x not in catcodes):

                     catcodes[x] = {}

                     currentcode +=1

                     catcodes[x][datarow[x]] = currentcode #encoding the feature

         # For already encoded fields

                 elif(datarow[x] not in catcodes[x]):

                     currentcode +=1

                     catcodes[x][datarow[x]] = currentcode #encoding the feature

                 code = catcodes[x][datarow[x]]

                 datastring = datastring + " "+str(i)+":"+ str(int(code))+":1"

         datastring += '\n'

         text_file.write(datastring)

xLearn은 FM을 구현하기 위해 csv와 libsvm 형식을 처리 할 수 ​​있지만 FFM을 사용하기 위해서는 반드시 libffm 형식으로 변환해야합니다. 여기에서 처리 된 데이터 세트를 다운로드 할 수 있습니다.

libffm 형식의 데이터 세트를 얻은 후에 xLearn 라이브러리를 사용하여 모델을 학습 할 수 있습니다.

다른 ML 알고리즘과 마찬가지로, 데이터 세트는 훈련 세트와 유효성 검증 세트로 나뉩니다. xLearn은 유효성 검사 / 테스트 로그 손실을 사용하여 early stopping를 자동으로 수행하며, stochastic gradient descent의 각 반복에 대한 유효성 집합에 대해 다른 평가함수를 적용할 수 있습니다.

다음 Python 스크립트는 ffm 형식의 데이터 세트에서 xlearn을 사용하여 FFM 모델의 하이퍼 매개 변수를 학습하고 조정하는 데 사용할 수 있습니다.

import xlearn as xl

ffm_model = xl.create_ffm()

ffm_model.setTrain("criteo.tr.r100.gbdt0.ffm")

ffm_model.setValidate("criteo.va.r100.gbdt0.ffm")

param = {'task':'binary', # ‘binary’ for classification, ‘reg’ for Regression

         'k':2,           # Size of latent factor

         'lr':0.1,        # Learning rate for GD

         'lambda':0.0002, # L2 Regularization Parameter

         'Metric':'auc',  # Metric for monitoring validation set performance

         'epoch':25       # Maximum number of Epochs

        }

ffm_model.fit(param, "model.out")

또한 cv () 함수를 사용하여 교차 유효성 검사를 사용할 수 있습니다.

ffm_model.cv(param)

다음 code snippet을 사용하여 테스트 세트에서 예측을 수행 할 수 있습니다.

# Convert output to 0/1

ffm_model.setTest("criteo.va.r100.gbdt0.ffm")

ffm_model.setSigmoid()

ffm_model.predict("model.out", "output.txt")

5. 정리(End Notes)

이 기사에서는 정상 분류 / 회귀 문제에 대한 인수 분해 사용법을 설명했습니다. 이 알고리즘이 귀하의 문제에 대해 어떻게 수행되었는지 알려주십시오. xlearn에 대한 자세한 문서는이 링크에서 제공되며 기고자의 정기적 인 지원이 제공됩니다.

출처 : https://www.analyticsvidhya.com/blog/2018/01/factorization-machines/

코드 : https://www.kaggle.com/scirpus/libffm-generator-lb-280

참고자료 :

https://www.kaggle.com/c/talkingdata-adtracking-fraud-detection/discussion/56497

https://github.com/jfpuget/LibFM_in_Keras/blob/master/keras_blog.ipynb

https://www.ibm.com/developerworks/community/blogs/jfp/entry/Implementing_Libfm_in_Keras?lang=en_us

https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf