1. Introduction

해당 논문은 지식 그래프의 벡터 임베딩의 포문을 연 글이다. 이 글 이후에 TransH, TransR 등 후속 논문들이 등장했고 지식그래프와 Question Answering 등등 여러 도메인에서 기초가 되었다고도 볼 수 있다.

1-1. Knowledge Graph

먼저 지식 그래프를 간단하게 살펴보도록 하자. 지식 그래프는 Multi-relational data라고 볼 수 있으며 기본적으로 entity 와 그 사이의 relation으로 구성되어 있다.

간단히 말해 그래프의 일종이라고 생각하면 된다! 또한 지식 그래프에서 사용하는 데이터 표현 방법을 알아 두고 가는 것이 중요하다!

$(h, l, t)$ -> head, label, tail

head와 tail은 두 엔티티이며, label은 두 엔티티 간의 관계이다. 기본적으로 지식 그래프는 방향성을 가진 그래프로 정의된다.

head, label, tail의 예시를 하나만 들자면 다음과 같다.

Seoul (HEAD) is capital of (LABEL) South Korea (TAIL).

1-2. Modeling multi-relational data

이런 지식 그래프, 혹은 엔티티 간의 연결구조와 그 예측에 관한 시도는 여러 번 있어왔다. 이는 추천 시스템과도 연관이 있는데, 간단한 예로 구글 검색을 할 때 오른쪽에 뜨는 작은 창은 지식 그래프의 유명한 예시이다.

이렇게 지식 그래프를 만들고 예측하는 방법은 여러 가지가 있는데, 논문에서 그 중 몇 개를 소개해 놓았다.

1. Stochastic Blockmodel
2. Tensor Factorization
3. Collective Matrix Factorization

하지만 이런 모델들은 모델의 표현성을 중시하다 보니 계산 코스트와 동시에 모델 복잡도가 올라갔고, 해석이 어려워졌다는 문제가 생겼다.

또한 이러한 high-capacity모델은 regularization이 힘든 부분이 있고, 또한 언더피팅 이슈도 있어 사용하기 조심스러웠다.

따라서 논문에서는 모델의 구조가 좀더 간단하며, 그 와중에도 좋은 성능을 유지할 수 있는 모델(TransE)을 제안하였다고 한다.

1-3 What is Translation?

translation은 TransE의 핵심 요소이다. 그렇다면 과연 translation은 무엇일까? 저자는 head와 tail 간의 relationship vector를 translation vector라고 한다. 직관적으로 말하자면 어떠한 개체를 translation을 통해 다른 개체로 매핑한다 고 볼 수 있겠다.

2. Translation-based model

2-1. Algorithm

TransE 모델의 알고리즘은 다음과 같다.

Initialization
1. 각각의 $l$ ( label ) 에 대해 $Unif(-\frac{6}{\sqrt{k}}, \frac{6}{\sqrt{k}})$ 로 초기화한다.
2. 각각의 $l$ 에 대해 vector normalizing을 시행한다.
3. 각각의 $e$ ( entity ) 에 대해 $Unif(-\frac{6}{\sqrt{k}}, \frac{6}{\sqrt{k}})$ 로 초기화한다.

loop
1. 각각의 $e$ ( entity ) 에 대해 vector normalizing을 시행한다.
2. Size $b$의 미니배치를 $S$ (traning set) 에서 샘플링한다. -> $S_{batch}$
3. $T_{batch} = \emptyset$으로 초기화한다.
4. for문: corrupted triplet에서 $S'$를 샘플링하고, $T_{batch}$에 uncorrupted triplet과 합한다.
5. 임베딩을 업데이트한다.
$\sum_{((h,l,t),(h',l',t')) \in T_{batch}} \nabla [\gamma + d(h+l,t) - d(h'+l, t')]_{+}$

모델의 기본적인 가정은 다음과 같다:

1. head vector에 relation vector를 더하면 tail vector에 근접할 것이다!
2. 라벨 $(h,l,t)$에서 $t$는 $h+l$과 가장 가까운 이웃이어야 한다.

다시 말해 (이상적으로는) translation을 통해 head vector를 tail vector로 매핑할 수 있다는 뜻이 된다.
그렇다면 $(head+label-tail)$ 수식으로 distance function을 만들 수 있을 것이다. $l1$과 $l2$ measure를 모두 사용할 수 있다. euclidian distance를 사용하면 다음과 같이 표현할 수 있다:
$f = ||h+l-t||_2^2$

그리고 목적함수(objective function)으로는 margin-based ranking criterion을 사용하였다. 식은 다음과 같다:
$\sum_{(h,l,t) \in S} \sum_{(h',l',t') \in S'} \nabla [\gamma + d(h+l,t) - d(h'+l, t')]_{+}$

2-2 Corrupted Set

지식 그래프는 non-corrupted set만 저장이 되어 있다. 다시 말해 정답인 데이터만 가지고 있기 때문에, 원래 데이터로만은 학습이 불가능하다.

따라서 저자는 원래 데이터의 $head$나 $tail$을 랜덤하게 바꾸어서 corrupted set을 만들고, 여기서 샘플링을 하여 학습을 진행했다.

3. Conclusion

이렇게 지식 그래프의 벡터 임베딩 방법을 소개한 논문 TransE를 알아보았다. 다음 포스트에서는 TransE의 한계와 후속 논문들을 살펴볼 것이다.