Paper
Main interest
지식 그래프에서 해결하고자 하는 여러 가지 문제들 중에서 가장 기초적인 문제는 Knowledge Graph(KG) Completion이다. 즉 주어진 dataset의 link가 complete 하지 않기 때문에 빠진 link들을 채워주는 작업이다. 하지만 그 전에 entity와 relation의 저차원 임베딩을 목적으로 한다. 이를 통해 2개의 entity(h, t)와 1개 relation(l) 간의 관계를 학습하고 새로운 link(relation)를 예측하고자 노력한다.
일반적으로 이러한 multi-relation data를 모델링 하기 위해서는 그래프의 local 또는 global 특징을 추출해야한다. 이러한 패턴들을 학습하여 이후에 예측 작업을 진행하게 되는 것이다. Locality는 순전히 구조적(structural, 내 친구의 친구는 나의 친구이다. 소셜 네트워크 측면에서 간선의 이어짐으로 관계를 모색)일 수도 있고 entity 자체에 의존할 수도 있다(누군가가 Star Wars IV를 좋아하면 Star Wars V도 좋아하지만 Titanic은 좋아하지 않는 것처럼 Star Wars 시리즈라는 entity 집단은 좋아하지만 그 이외는 좋아하지 않는 것).
우리가 일반적인(generic) 모델이 필요한 이유는 single-relation data(A는 B의 친구이다)만 있는 것이 아니라 multi-relation data(책 A는 저자가 B고 출판사는 C고 장르는 D고 ...)를 모델링해야 하기 때문에 여타 기존의 임베딩 모델보다 더 복잡한 특성들을 잡아낼 수 있어야 하기 때문이다.
Problem with previous approaches
기존의 multi-relation 학습에서 성공적인 학습법은 entity와 relation의 잠재적 특성들을 학습시키는 방법이었다. 즉 벡터의 임베딩 값을 학습에 이용하며 이러한 접근을 extend하여 활용한 모델 종류는 non-parametric Bayesian extensions of the stochastic blockmodel, model based on tensor factorization, collective matrix factorization 등이 있다. 기존의 많은 연구들은 임베딩을 통해 그래프의 특성을 학습하기 위해 Bayesian clustering frameworks, energy-based framworks를 사용하였다.
여기서 우리가 주의해야 할 것은 모델의 복잡도가 커질 수록 더 많은 특성들을 찾을 수 있지만 동시에 연산량도 그에 상응해 커진다. 또한 매우 복잡한 모델은 적절한 regularization을 해주기 쉽지 않아 overfitting 문제에 빠질 가능성이 크고 non-convex optimization problem 때문에 underfitting 될 위험도 있다.
하지만 이 논문 에서는 단순한 모델(TransE)이 무거운 기존의 모델들만큼 충분히 다양한 특성을 포착하고 연산 효율에서 상당히 앞서 나간다고 주장한다. 즉 적절한 가정만 정의하면 단순한 모델도 학습할 수 있다는 것이다. 결국 TransE를 통해 필자는 정확도와 확장성(scalability) 간의 trade-off를 적절히 balance 시켜 모델 성능을 향상했다.
기존 모델들 3 가지의 문제점들을 살펴보자.
RESCAL(2011)
● tensor 기반 factorization 접근 방법 사용
● relation을 행렬, entity를 벡터로 표현
● $f(h,l,t)=\textbf{h}^\texttt{T}\textbf{R}_l\textbf{t}$ 와 같은 scoring function을 사용
SE(Structured Embeddings)(2011)
● scoring function을 2개의 bilinear form으로 분해함
● $f(h,l,t)=\left\|\textbf{M}_{l,1}\textbf{h}+\textbf{M}_{l,2}\textbf{t} \right\|$
SME(Sementic Matching Energy)(2012)
● neural network를 통해 학습함
● 두 가지의 scoring function(linear, bilinear)을 사용($g$는 비선형 함)
$f(h,l,t)=g(\textbf{W}_{l,1}\textbf{h}+\textbf{W}_{l,2}\textbf{t})$, $f(h,l,t)=g(\textbf{W}_{l,1}\textbf{h}, \textbf{W}_{l,2}\textbf{t})$
위 모델들의 공통된 문제점은 무거운 행렬 연산이 포함되어 있기 때문에 규모가 큰 KG로의 확장성이 제한된다는 것이다.
따라서 이 모델의 translation-based parameterization(entity의 관계를 벡터 공간에 표현)의 동기는 두 가지가 있다고 설명한다.
첫 번째는 knowledge base(KB; 지식 그래프 데이터)에서 계층적 구조가 흔하다는 것이다. 계층적 구조와 KB 사이의 관계는 아래와 같이 생각해 볼 수 있다.
즉 벡터 연산으로 이러한 관계를 표현하기 적합하다는 것이다. 애초에 <KB>에 있는 relation들을 벡터로 바라보면 더 직관적으로 명확해진다.
Entity 벡터의 좌표에 각각 A, B, C entity를 그려봐라! 위의 <KB>와 구조가 같아진다.
두 번째는 Word2Vec에서의 다른 종류의 entity 간의 1-to-1 관계 학습에 있다. 아래는 Word2Vec의 간단한 예시이다.
자세히 보면 man과 woman 사이의 차이가 벡터(보라색 점선 벡터)로 표현 되었고 이 차이 벡터는 king과 queen의 차이와 같음을 알 수 있다. 즉 entity의 종류가 달라도 규칙만 있다면 맥락적 특성을 임베딩할 수 있다는 것이다. 위의 그림 1도 충분히 같은 철학을 이어받고 있다고 할 수 있다.
이러한 배경을 정당성으로 사용해 TransE는 연산적으로 저비용인 임베딩 벡터의 합성으로 모델을 학습한다.
Architecutre
Energy-based인 TransE의 기초적인 재료들은 다음과 같다. 하나의 triplet(h, l, t)에 관해 저차원 벡터(이것이 임베딩 벡터이다)인 h, t와 r에 대해 학습한다. 이들을 활용해 $\textbf{h}+\textbf{l}\approx \textbf{r}$(볼드체는 각각 h, l, t의 임베딩 벡터이다)를 최대한 만족하도록 학습한다. 임베딩 벡터는 그냥 $k$차원으로 아무렇게나 초기화시킨다(entity가 어떤 feature을 갖고 있었는지 전혀 관심이 없고 사용조차 안 한다).
$\textbf{l}$과 $\textbf{e}$은 모든 feature들이 초기에 특정 범위에서 uniform draw 된 값을 갖는다. 모든 임베딩은 $k$차원의 벡터이고 $k$는 임베딩 차원이자 하이퍼 파라미터가 된다. 또한 주기적으로 임베딩 벡터는 regularized 되는데($l$은 초기에만 한다) 그 이유는 input 벡터들($\textbf{h}+\textbf{l},\textbf{t}$)의 크기가 너무 커져버리면 두 input의 dissimilarity가 작은 것이 실제로 유사해서 작은 건지 아니면 벡터의 크기가 커져서 차이가 미미해진지 알 수 없기 때문이다.
Minibatch로 샘플링해 각각의 샘플 triplet에 상응하는 corrupted triplet을 생성한다.
Corrupted triplet의 생성 방법은 아래와 같다.
$h$와 $t$중에서 하나만(동시에 바꾸지 않는다) random으로 negative sampling 한다.
위는 손실 함수이고 $d$는 dissimilarity 측정 함수이다. 옳은 triplet에 대해서는 작은 값, 틀린 데이터에 대해서는 큰 값을 부여도록 유도한다. $\left\|\textbf{h}+\textbf{l}-\textbf{t} \right\|_2$를 계산하지만 명확한 수식은 논문에서 언급한 바가 없다. 하지만 Related work에서 언급된 바에 의하면 SE와 NTN의 scoring function을 참고하여 $l,h,t$간의 상호작용이 있는 수식만 사용한다고 하였다.
왜냐하면 3개의 임베딩 벡터 간의 상호 관계가 있는 부분만이 유의미(h의 L2 norm이 크면 dissimilarity 가 커야하는 것인가? 아니다)하기 때문에 scoring 하려고 한다.
이 논문에서는 TransE의 다음 한계를 인정한다.
1. 여타 다른 모델들과 다르게 훨씬 적은 개수의 파라미터를 사용하여 KB의 다양한 특성들을 포착할 수 없다. 그러나 TransE는 그 단점을 상쇄할 만큼 단순성을 취한다.
2. 2-way interaction만 학습한다. 우리 기존 수식을 살펴보자. $d(\textbf{h}+\textbf{l},\textbf{t})$은 사실상 두 벡터의 연산으로 볼 수 있다($\textbf{X}\times\textbf{Y}$). 하지만 RESCAL 같은 모델은 3 요소가 독립적으로 연산이 된다($\textbf{X}\times\textbf{Y}\times \textbf{Z}$). 이러한 관점에서 TransE는 3-way interaction을 학습하지 못하며 더 다채로운 특성을 포착하지 못하여 cross-validation에서 기대에 못 미치는 성과를 낸다고 한다.
하지만 이러한 한계에도 불구하고 TransE는 모델 무게에 비해 상당한 성능을 낸다.
Experiments
MR, Hits@k의 metric에서 과거 모델들보다 향상된 성능을 보여준다.
Conclusion
과거 모델들이 공통적으로 겪고 있었던 무거움 문제를 해결하고자 훨씬 가벼운 벡터 합성 연산을 사용한 모델을 제안하였고 Word2Vec 등 타 모델들의 아이디어에 착안하여 모델의 정당성을 확보하였고 더 큰 KB로의 확장을 가능케 하였다.
APPENDIX
1. 해결 못한 한계점
논문의 마지막 부분에 제시된 의구점("Although it remains unclear to us if all relationship types(1-to-1, 1-to-Many, ...) can be modeled adequately by our approach")은 TransE의 대표적인 한계다. 이 한계는 3-way interaction 문제에서 발생하는데, 예를 들어 symmetric relation(A는 B와 친구이다, B는 A와 친구이다와 같이 (h, l, t), (t, l, h)를 동시에 만족시키는 relation)에 대해서 문제가 발생한다. $\textbf{h}+\textbf{l}\approx \textbf{t},\textbf{t}+\textbf{l}\approx \textbf{h}$ 두 수식을 모두 만족시키려면 $\textbf{r}=0$이 되고 결국 $\textbf{h}\approx\textbf{t}$까지 만족하게끔 임베딩이 진행된다. 이것은 복잡한 KG 관점에서 옳지 못하기 때문에 TransE의 대표적인 문제점으로 꼽히고 향후에 TransH, TransR의 탄생 배경이 된다.
2. Corrupted triplet 생성시 1개의 entity만 바꾸는 이유
예를 들어 (J.K. Rowling, wrote, Harry Potter1)가 있다고 가정하자. 여기서 1개 또는 2개를 바꾸었을 때 가능한 오류(negative로 학습하지만 사실상 참인 triplet이 생성될 경우)를 만들어보자.
Head 교체 : (Obam, wrote, Harry Potter1) -> 우연치 않게 J.K. Rowling을 다시 선택하지 않는 한 wrote라는 relation에 대해 head currupt는 절대 참일 수 없다.
Tail 교체 : (J.K. Rowling, wrote, Harry Potter2) -> 참이다. 하지만 반대로 (James Washington, born in, USA)에서 USA(tail)를 교체하면 반드시 거짓인 triplet이 생성된다.
Head, Tail 교체 : (James Dashner, wrote, The Maze Runner) -> 참이다.
물론 어느 샘플링 전략이든 일부 negative sample이 참일 가능성에 노출 되어 있다. 하지만 이것을 감안하고 진행하는 것이 negative sampling이고 우리가 현재 관심있는 것은 "어떤 방식이 거짓인 triplet을 생성할 확률이 더 큰가"이다. 위에서 보이듯이 entity를 1개만 교체하는 전략은 relation의 속성에 따라 반드시 거짓인 데이터를 만들어낼 수 있다. 반면 2개를 모두 교체하는 전략은 그것을 보장할 수 없기 때문에 본 연구에서 하나의 negative sample을 위해 하나의 entity만 corrupt한 것이 아닐까 생각한다.
물론 위의 추론은 나의 생각일 뿐이다. 하지만 본질적으로 접근하자면 애초에 negative sampling이 필요한 이유부터 생각해보도록 하자. 결국 negative sample에 대해서는 낮은 score를 도출하도록 학습시키고 싶은 것 아닌가? 이 맥락에서 바라보았을 때 A-relation-B(positive sample)를 더 잘 학습하기 위해 어떤 오답이 필요할까에 대해 생각해보자면 특정 사실에 대해 하나의 entity만 alter 하는 것이 더 자연스러워 보인다. 기존의 triplet에 대한 맥락을 절반 정도만 바꾸기 때문이 아닌지 생각이 든다. 또한 복잡도 측면에서도 2개를 바꾸는 것보다 1개만 바꾸는 것이 덜 복잡한 것도 사실이다.
3. Relation($l$)을 regularization 해주지 않는 이유
TransE의 알고리즘을 보면 entity의 임베딩 벡터의 L2-norm을 1로 regularization 해준다. 하지만 relation은 안해준다. 왜냐하면 relation의 역할은 두 entity간의 차이를 나타내는 역할일 뿐이기 때문이다. 예를 들어 entity가 모두 2차원에서 regularization 되었다면 이들은 전부 단위원 위에 있을 것이고 relation의 L2-norm은 최대 2, 최소 0으로 벡터의 크기가 유연해야 다양한 entity들을 이어줄 수 있기 때문에 relation 임베딩의 크기는 건드리지 않는다.
