Guo, C., & Berkhahn, F. (2016). Entity embeddings of categorical variables. arXiv preprint arXiv:1604.06737.
본 눈문은 앞서 리뷰했던 TabNet 논문보다 이전에 나온 논문으로, TabNet과 마찬가지로 정형 데이터에서 Neural Network보다 트리 기반 머신러닝 기법이 더 활발하게 사용되는 상황을 지적하며, 이를 개선하기 위해 범주형 데이터에 One-hot encoding 대신 Entity Embedding을 적용하는 방법을 제안하고 있습니다. 논문에 대한 전체적인 내용을 살펴보도록 하겠습니다.
1. Introduction
비정형 데이터 분야에서는 딥러닝의 적용이 활발한 편이지만, 정형 데이터 분야에서는 딥러닝보다 트리 기반의 머신러닝 기법이 더 많이 적용되고 있습니다. 이는 Neural network와 트리 기반 기법의 차이에서 비롯됩니다. Neural Network는 학습 과정에서 데이터의 연속성을 가정하는 반면, 트리 기반의 기법들은 데이터의 연속성을 가정하지 않습니다. 이미지, 텍스트와 같은 비정형 데이터는 Flattening과 Word embedding 등을 통해 연속적인 데이터로 변환하는 것이 수월하지만, 정형 데이터의 범주형 변수는 연속형 변수로 변환하기가 쉽지 않습니다. 범주형 변수는 연속적이지 않고 이산적이기 때문에, Neural network가 범주형 변수를 포함하게 되는 대부분의 정형 데이터들에서 성능을 내지 못했던 것입니다.
이러한 문제점을 해결하기 위해 대부분 One-hot encoding 기법을 활용했지만, 이 기법은 1) Cardinality가 높은 변수들은 과도하게 계산량이 증가하게 되고, 2) 변수 내의 각 값들의 관계를 무시하게 된다는 단점이 존재합니다. 따라서 본 논문에서는 Entity Embedding을 통해 범주형 변수들을 연속적인 즉, 다차원 공간의 벡터 형태로 변환하고, 해당 값을 딥러닝 학습에 사용하는 방법을 제안하였습니다. 자세한 내용은 계속해서 다루도록 하겠습니다.
2. Related Work
신경망 분야에서 Entity Embedding은 Relational Data(관계형 데이터)의 표현에서 시작됩니다. 관계형 데이터의 기본적인 구조는 (\( h \), \( r \), \( t \))로, \( h \)와 \( t \)는 객체를, \( r \)은 관계를 나타냅니다. 자연어 처리 분야에서는 Word Embedding이 주로 활용되는데, 이는 단어를 의미적인 공간에 연속적인 벡터 형태로 매핑시키며, 거리와 방향을 통해 단어 간의 유사성을 표현합니다.
3. Tree Based Methods
트리 기반 기법들은 정형 데이터에서 활발히 적용되고 있으며, 그 중 Random Forset와 Gradient Boosted Trees이 특히 유명합니다. 이 파트에서는 1) Single decision tree(단일 의사결정나무), 2) Random Forest(랜덤 포레스트), 3) Gradient Boosted Trees(그라디언트 부스팅)에 대해 간단하게 살펴보도록 하겠습니다.
A. Single decision tree
단일 의사결정나무는 feature space \( X \)를 \( M \)개의 서로 다른 sub-space(부분공간) \( R_1 \), \( R_2 \), ... \( R_M \)로 구분하는 것이 목적입니다. 하지만 최적의 부분공간을 찾기 위해 각 부분공간마다 손실함수를 최소화하는 계산 방법은 feature space \( X \)의 크기에 따라 과도한 계산량을 요구하게 됩니다. 이에 따라 데이터를 Split(분할)하는 순간마다 최적이라고 판단되는 결과를 선택해나가는 방식인 Greedy Algorithm(탐욕 알고리즘)을 적용하게 되었습니다. 그러나 이 방식은 분할하는 횟수가 많아질수록 모델의 복잡성, 즉 훈련 데이터에 과적합될 우려가 증가하게 됩니다. 따라서 Prunning 방식을 적용하는 것을 통해 나무의 크기가 과도하게 커지는 것을 방지하였습니다.
$$ C_\alpha = \sum_{i} (y_i - f(x_i))^2 + \alpha|T| $$
위의 수식과 같이 Prunning은 실제값과 예측값의 차이를 최소화하는 것과 동시에 Terminal node(터미널 노드)의 수를 패널티 항으로 넣어 분할 횟수가 많아질수록 cost가 증가하는 식을 활용했습니다.
B. Random forests
단일 의사결정나무는 전형적으로 편향은 낮고 분산이 높아 과적합 문제가 발생할 수 있습니다. 랜덤 포레스트는 이러한 과적합 문제를 해결하기 위해 여러 개의 단일 의사결정나무를 만들고 집계하는 방식을 사용하였습니다. 과정과 수식은 다음과 같습니다.
- 부트스트랩 샘플링을 통해 훈련 데이터에서 n개의 샘플을 추출
- 각 샘플별로 m개의 변수를 무작위로 선택하고 의사결정나무 생성
- 모든 의사결정나무의 결과를 결합
$$ f(x) = \frac{1}{N}\sum_{i=1}^N T_i(x) $$
\( T_i \)는 각 의사결정나무를 의미하며, 단일 의사결정나무를 통해 편향을 낮추고, 각 결과를 평균하는 것을 통해 분산도 낮춘 것이 랜덤 포레스트입니다.
C. Gradient boosted trees
여러 샘플을 통해 생성된 의사결정나무 결과를 집계하는 랜덤 포레스트와는 달리 그라디언트 부스팅은 n-1번째 의사결정나무를 보완하여 보다 개선된 n번째 의사결정나무를 생성하는 기법입니다. 각 단계마다 손실 함수를 최소화하는 것을 반복적으로 진행하여 점진적으로 결과를 개선해 나간다는 의미에서 gradient라는 명칭이 사용되었으며, 랜덤 포레스트와 같이 편향과 분산을 최소화하는 것을 목적으로 합니다.
4. Structured Data
본 논문에서 정의하고 있는 정형 데이터는 우리가 일반적으로 알고 있는 테이블 형태의 데이터입니다. 정형 데이터에서 주로 사용되는 변수 유형은 연속형 변수와 이산적 변수입니다. 이산적 변수라고 하더라도 명목형 변수와 같이 숫자로 표현될 수 있고, 월(month)과 같은 순서형 변수처럼 표현될 수 있습니다. Entity Embedding은 이러한 이산적 변수들을 다차원 공간의 값으로 매핑하는 것이며, 결과값은 의미가 유사할수록 해당 값들이 더 가까이 위치하게 됩니다.
5. Entity Embedding
위의 그림은 Entity Embedding의 전체적인 과정을 나타내고 있습니다. 위의 그림과 수식을 통해 Entity Embedding을 설명하고자 합니다. Entity Embedding은 최종적으로 다음 식과 같이 이산적 변수를 벡터로 매핑시키는 방법입니다.
$$ e_i : x_i \mapsto \mathbf{x}_i $$
Entity Embedding의 첫 번째 과정은 이산적 변수를 one-hot encoding을 통해 변환시켜주는 것입니다. 식은 다음과 같이 표현됩니다. 여기서 one-hot encoding은 \( \delta_{x_i \alpha} \), Kronecker delta로 표현되며, \( x_i \)와 \( \alpha \)가 같을 때는 1, 아닐 때는 0으로 계산되는 식입니다. 그림에서는 가장 아래의 one-hot encoding layer를 만들어주는 단계입니다.
$$ u_i : x_i \mapsto \delta_{x_i \alpha} $$
다음으로 가중치인 \( w_{\alpha \beta} \)를 통해 one-hot encoding layer를 embedding layer로 연결해주는 과정을 진행합니다. 위의 그림에서는 EE(Entity Embedding) layer를 생성하고 dense layer 0에 입력되기 전에 합쳐지는 단계를 나타냅니다. 이러한 과정은 다음 식으로 표현됩니다.
$$ \mathbf{x}_i \equiv \sum_\alpha w_{\alpha \beta} \delta_{x_i \alpha} = w_{x_i \beta}$$
위의 식에서 \( \delta_{x_i \alpha} \)는 \( \alpha \)와 \( x_i \)가 일치하지 않으면 0이 되고 일치하면 1이 됩니다. \( \delta_{x_i \alpha} \)와 가중치들을 곱하고 이 값들을 합하게 되면, 결국 \( \alpha \)와 \( x_i \)가 일치하는 가중치만 남게 되어 하나의 변수 형태로 변환할 수 있습니다. one-hot encoding을 사용하였다면 변수의 cardinality만큼 변수가 증가했겠지만, 위의 과정을 통해 하나의 연속적인 변수, \( \mathbf{x}_i \)만을 생성하였고 Neural Network에서 다른 연속적 변수와 동일하게 활용할 수 있습니다.
Embedding 과정에서는 hyper-parameter로 embedding layer의 차원의 수를 설정해야합니다. 차원의 범위는 1부터 \( m_i - 1 \)이며, \( m_i \)는 범주형 변수 \( x_i \)의 값들의 갯수를 의미합니다. 차원의 수는 복잡할수록 커야하며, 가이드라인이 없을 경우 \( m_i - 1 \)부터 시작하면 됩니다.
6. Experiments
본 논문에서는 Kaggle의 Rossmann Sale Prediction competition의 데이터를 예제로 활용하였습니다. 해당 competition의 목적은 Dirk Rossmann GmbH(유럽의 약국 체인점)의 각 지점의 일매출(Daily Sales)을 예측하는 것이었습니다. 2.5년 간 1,115개의 매장에 대한 데이터이며, 데이터의 수는 총 1,017,210개입니다. Sales를 제외한 변수의 목록과 entity embedding의 차원은 아래의 Table 1과 같습니다. 모든 변수들이 연속형 변수가 아닌 범주형 변수인 것을 확인할 수 있습니다.
해당데이터의 90%는 훈련 데이터로, 10%는 평가 데이터로 활용하였으며, 1) 훈련 데이터와 평가 데이터의 통계적 분포가 유사한 shuffled 데이터, 2) 시간 기반으로 분리된 unshuffled 데이터, 총 두 가지의 데이터셋을 생성하였습니다.
A. Comparison of different methods
방법론으로는 neural network(NN), k-nearest neighbors(KNN), random forests(RF), gradient boosted trees(GBT), 총 4개가 적용되었고, 평가 방법으로는 mean absolute percentage error(MAPE)가 사용되었습니다. 아래의 Table 3과 4가 그 결과입니다. Shuffled data에서는 GBT와 NN이 우수한 정확도를 보여주었고, unshuffled data에서는 NN이 가장 좋은 결과를 나타냈습니다. 또한 unshuffled data에서 one-hot encoding보다는 entity embedding을 적용했을 때 더 좋은 결과를 도출하였습니다.
이러한 결과의 이유는 One-hot encoding의 경우 Sales를 제외한 변수들이 모두 범주형 변수들이기에 데이터 전체에 대해 제대로 학습하기가 어려웠지만, entity embedding을 활용하게 되면 Sales뿐만 아니라 모든 변수들의 본질적인 특성을 학습할 수 있었기 때문입니다.
B. Distribution in the embedding space
Entity embedding의 주요 목적은 embedding 공간에서 유사한 범주들을 서로 가깝게 위치시키는 것, 즉 embedding 공간과 데이터의 분포를 유사하게 만드는 것입니다. Embedding 공간을 2D로 시각화하기 위해 t-SNE를 사용하였으며, Fig 3은 독일의 State 변수를 embedding한 결과를 보여줍니다. 해당 결과는 각 State의 실제 위치와 상당히 유사하다고 합니다. 이는 embedding한 결과가 각 State의 경제적, 문화적 환경을 잘 반영했기 때문입니다.
다음 Fig 4는 각 지점을 Sales의 분포와 t-SNE 결과의 주요 요소 및 무작위 방향에 따라 시각화한 결과입니다. 첫 번째 그림을 제외하고는 뚜렷한 경향을 보여주고 있지는 않지만, 첫 번째 주요 요소와 Sales 간의 뚜렷한 경향성을 보여주는 것은 각 지점 간의 관계를 NN이 제대로 학습할 수 있을 것이라고 해석하고 있습니다.
7. Future Work
본 논문에서는 추후에 1) cardinality가 높은 데이터셋을 다양하게 활용하여 검증, 2) embedding 공간에서의 각 entity 간의 관계에 대한 심도깊은 이해, 3) 다른 활성 함수 활용 등의 연구가 필요하다고 언급하며 마무리하고 있습니다.
논문에 대한 리뷰는 저의 해석대로 작성되었기 때문에, 읽으시면서 잘못되거나 보완될 부분이 있다면 댓글로 알려주시길 바랍니다.
댓글