1. Introduction

해당 논문은 Knowledge Base의 Structured Embedding 방법에 관한 글이다. Knowledge Base(혹은 지식 그래프)에 대한 설명은 이전에 썼던 설명으로 갈음하겠다.

지식 그래프는 Multi-relational data라고 볼 수 있으며 기본적으로 entity 와 그 사이의 relation으로 구성되어 있다.

1-(1) Symbolic & Non-Symbolic

symbolic과 non-symbolic 표현의 차이점은 인간이 알아볼 수 있는가? 이다. symbolic데이터의 한 예시는 질의응답을 예로 들 수 있겠다.

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

위의 예시를 보면 '서울'과 '남한'은 '(~의) 수도' 관계로 이루어진 symbolic 데이터로 볼 수 있다.

이와 반대로 non-symbolic데이터는 인간이 알아볼 수 없는 표현(주로 자연어가 아님)으로 만들어진 데이터를 말한다. 그 예로 인공신경망의 가중치 행렬을 들 수 있겠다. 가중치 행렬은 실수로 이루어져 있고, 인공 신경망의 학습에 따라 조절된다. 그러나 non-symbolic한 가중치의 해석 불가능성이 곧 딥 러닝의 블랙 박스 현상으로 이어진다.

1-(2) Knowledge Graph Embedding

지식 그래프 임베딩은, symbolic데이터인 지식 그래프를 non-symbolic하게 만들어 기계가 지식 그래프 구조 인식, 학습 등을 가능하게 만드는 방법이다. 이전 포스트에 소개한 TransE도 그 방법 중 하나이다.

이 논문에서는 left hand side, right hand side 두 가지의 공유된 행렬을 사용한 지식 그래프 임베딩 방법을 소개하고 있고, 이를 Structured Embeddings이라고 한다.

2. Framework

2-(1) Datasets

논문에서는 두 가지의 Dataset을 소개한다: WordNet, Freebase
두 가지 모두 지식 그래프 형태를 띠고 있으며, 해당 데이터셋은 이 사이트에서 받아볼 수 있다. 다만 Freebase 데이터셋의 경우 엔티티가 엔티티 id 형태로 인코딩되어 있는데 현재 Freebase 사이트에 접속이 불가능해 디코딩이 불가 (내가 아는 선에서는) 하다. 혹시 그 방법을 아시는 분은 댓글로 달아주시면 감사하겠다.

다만 WordNet 데이터셋의 엔티티는 python nltk 라이브러리 안의 nltk.corpus.wordnet 클래스의 synset_from_pos_and_offset 메소드로 디코딩 가능하다. 따라서 이 논문을 구현해보실 분은 WordNet 데이터셋을 사용하시길 권장드린다.

Freebase 데이터셋은 다음과 같이 구성되어 있다.
예시)

(_marylin_monroe, _profession, _actress)
(_pablo_picasso, _place_of_birth, _malaga)
(_john_f_kennedy, _religion, _catholicism)

WordNet 데이터셋은 다음과 같이 구성되어 있다.
예시)

(_door_1, _has_part, _lock_2)
(_brain_1, _type_of, _neural_structure_1)
(_auto_1, _has_instance, _s_u_v_1)

두 데이터셋 모두 엔티티의 값은 많은 데 반해, Relation type은 비교적 적다. 논문에서 사용된 Relation type의 개수는 Freebase, WordNet 각각 13, 11개이다.

3. Embedding Knowledge Bases

여기서는 SE Model의 구체적인 알고리즘을 소개하겠다.

3-(1) Structured Embeddings

• 엔티티는 embedding space라고 불리는 $d$-차원 공간에 모델링될 수 있다.
• 이제 우리는 두 엔티티 간의 관계를 모델링하고 연산할 것이다. 여기서 주의할 점은 두 엔티티의 관계는 대칭적이지 않다! -> 위의 서울 예시를 보자. 서울은 남한의 수도이지만 남한은 서울의 수도가 아니다.
• 따라서 이 논문에서는 왼쪽 엔티티, 오른쪽 엔티티에 대해 각각의 Relation matrix $R_k$를 모델링하였다.

$R_k = (R_k^{lhs}, R_k^{rhs})$ for $k^{th}$ given relation

• 여기서 두 relation matrix ($R_k^{lhs}, R_k^{rhs}$) 는 $d \times d$ 크기이다.
• 이 개념을 가지고 다음과 같이 similarity function을 정의해 볼 수 있다.

$S_k(E_i,E_j) = ||R_k^{lhs} E_i - R_k^{rhs} E_j||_p$

• 여기서는 p=1 norm을 사용하였지만 p-2 norm도 사용 가능하다.

3-(2) Training Objective

위의 similarity function을 사용한 학습 과정은 인공신경망의 일종 (특히 siamese network) 이라 볼 수 있다. 우리의 학습 목적은 두 엔티티 간의 관계를 알아내는 것이다. 그러기 위해 우리는 몇 가지 가정사항이 필요하다.

• 모델은 오른쪽의 엔티티가 비어 있어도 왼쪽 엔티티와 relation을 통해 맞는 엔티티를 찾아낼 수 있어야 한다.

이 개념을 수식으로 표현하면 다음과 같다. (예측 대상이 바뀐 경우에도 동일하다)

$f(e_i^l, r_i, e_i^r) < f(e_j^l, r_i, e_i^r), \forall j: f(e_j^l, r_i, e_i^r) \notin x$

이 $f$라는 목적식의 개념을 수학적으로 이해해 보자면, 모든 정답이 아닌 triplet에 대해서 정답인 triplet의 (엔티티 간의) similarity가 더 작아야 함을 뜻한다.

따라서 $f$라는 함수를 수식으로 정의해 보면 다음과 같다.

$f(e_i^l, r_i, e_i^r) = ||R_{r_i}^{lhs} E v(e_i^l) - R_{r_i}^{rhs} E v(e_i^r)||_1$

• $R_{r_i}^{lhs}, R_{r_i}^{rhs}$는 모두 $d \times d \times D_r$ 텐서이다. 여기서 $D_r$은 relation의 개수를 뜻한다. 따라서 이 값은 (논문의 실험에서) Freebase에 대해 13, WordNet 데이터셋에 대해 11일 것이다. $r_i$는 이 relation 중 하나를 골라 유사도를 계산한다는 것을 뜻한다. $r_i$ 가 고정되면 $R_{r_i}^{lhs}, R_{r_i}^{rhs}$는 $d \times d$ 행렬이 된다.

• E는 $d \times D_e$ 행렬이며 $v(e_i^l)$은 특정한 $e_i^l$이 1인 one-hot vector이다.

• 따라서 $R_{r_i}^{lhs} E v(e_i^l)$ 식은 $e_i^l$을 뽑고 given relation $r_i$에 대해 행렬 연산을 수행하여 $d \times 1$ vector을 만드는 식이 된다.

• 위의 연산은 오른쪽에 있는 엔티티에도 적용되어 마지막으로 1-norm distance (similarity)를 계산한다.

• 중요한 것은 여기서 엔티티는 모든 Relation에 대하여 가중치를 공유한다는 점이다. 저자는 이 방법을 통해 파라미터의 수 (d = 50) 를 줄이고 보다 큰 지식그래프에 대해서 적용을 용이하게 만들었다고 한다.

4. Algorithm

4-(1) Training

아래는 학습 알고리즘이다.

1. 정답 triplet $x_i$를 무작위로 고른다.
2. 왼쪽의 엔티티나, 오른쪽의 엔티티 둘 중 하나를 negative entity (틀린 엔티티)로 바꾼다. 이 작업은 학습 데이터를 만드는 셈이 된다.
3. 만약 $f(x_i) > f(x^{neg} -1)$ 일 경우 $max(0,1-f(x^{neg} + f(x_i))$ 식을 최소화하는 방향으로 경사하강을 한다. (이 논문에서는 SGD를 사용하였다고 한다)
4. 각각의 엔티티 column에 대해 normalizing을 한다. $||E_i|| = 1, \forall i$

4-(2) Probability Landscape Estimation

학습이 모두 완료된 후, 저자는 임베딩 공간의 특정 포인트에 대해 확률밀도를 추정하기 위해 Kernel Density Estimation을 사용했다. Gaussian Kernel을 사용했고, triplet의 pair에 대한 kernel density estimator은 다음과 같다.

$f_{kde}(x_i) = \frac{1}{|S(x_i)|} \sum_{x_j \in S(x_i)} K(x_i, x_j)$

$f_{kde}$는 모든 triplet에 대해 확률밀도를 추정할 수 있기 때문에, 예측을 위해서도 사용될 수 있다. 예측 수식은 다음과 같다.

$\hat{e}^r = argmax_{e \in D_e} f_{kde} (( e^l, r, e ))$