Paper :
Presentation content :
Main interest
지식 그래프(Knowledge Graph, KG)는 실세계 지식들을 담고 있는 특수 그래프이다. 노드는 entity, 방향 간선은 relation이라고 하며 하나의 triplet(i.e. $(h, r, t)$ 또는 $r(h, r)$)을 데이터 단위로 한다. 이를 사용해 추천 시스템, question answering, 다양한 추론 등에 활용할 수 있기 때문에 활용도가 무궁무진한 그래프 구조이다.
본 연구에서는 이런 semantic 데이터를 사용해 논리적 추론을 할 수 있는 모델을 만들고자 한다. 가령 위의 예시에서 $(Tim\, Cook,Succesor\,of,Steve\, Jobs)\wedge(Steve\, Jobs,Former\,CEO\,of,Apple\,Inc.)$가 참이면 $(Tim\,Cook, CEO\,of, Apple\,Inc.)$이 참일 신뢰도가 얼마인지 계산할 수 있는 모델을 만들고 싶은 것이다. 즉 다르게 이야기해보면 일부의 정보가 주어졌을 때 구하고자 하는 정보를 얻어내고자 하는 것이며 이렇게 다른 triple의 연쇄 조합으로 정보를 얻어내는 접근 방법을 logical rule mining이라고 한다.
조금 더 예시를 들어가며 설명을 해보겠다. $hasGrandma$이라는 relation이 있다고 하자. 아래와 같은 KG가 있다고 상상할 수 있을 것이다.
$hasGrandma(x,y)\leftarrow hasMother(x,a)\wedge hasMother(a,y)$는 우리 인간의 상식선에서 문제가 되지 않는 rule이다. 하지만 전자의 rule과 같은 형태로 head relation($hasGrandma$)을 감고 있는 $hasGrandma(x,y)\leftarrow hasSameFirstName(x,b)\wedge hasMother(b,y)$ rule은 항상 참이라고 보기 힘들다. 즉 head relation을 단순히 구성하고 있다고 해서 언제나 믿음직한 rule이 되지 못하며 엄연히 rule마다 quality 평가 지표가 필요한 법이다. 하지만 이렇게 rule을 수집하면 결국 무엇이 좋은가? 가령 $hasGrandma(x,y)\leftarrow hasMother(x,a)\wedge hasMother(a,y)$가 KG에서 모델이 추출한 신뢰도 높은 rule이라고 가정하자. 이 추출을 거친 모델은 다른 KG에서 $x$가 누군가와 $hasGrandma$이라는 relation이 보이지 않아도 $x$를 기점으로 주변을 탐색해 $hasMother(x,a)\wedge hasMother(a,y)$가 존재함을 찾게 되면 $y$가 $x$의 할머니라는 사실을 추론할 수 있는 것이다.
즉 rule mining 모델은 KG에서 복잡한 관계들을 rule로써 학습하고자 하는 것이다.
Problem with previous approaches
Logical rule을 mining하기 위해서 기존에 다양한 접근들이 있었다. 그들 중 비교적 최근의 접근법들은 neural network와 RNN을 합쳐 rule의 구성과 신뢰도를 함께 계산하는 NeuralLP(NeurIPS, 2017)과 DRUM(NeurIPS, 2019), EM 알고리즘을 기반으로 rule 구성과 신뢰도 계산을 별개의 모델에서 관할하게 하는 RNNLogic(ICLR, 2021) 등이 있다. 모두 그 당시에 성공적인 모델이었지만 RLogic의 저자들은 두 가지 문제점을 지적한다.
첫 째, rule instance에 대한 근거가 부족한 rule은 mining 할 수 없다.
가령 위와 같은 KG가 있다고 하자, $hasGrandma(x,y)\leftarrow hasMother(x,a)\wedge hasMother(a,y)$는 도출할 수 있겠지만 Dana와 Faye를 연결하고 있는 $hasGrandma$의 부제 때문에 $hasUncle(x,y)\leftarrow hasGrandma(x,b)\wedge hasSon(b,y)$를 도출하지 못한다(참고로 위의 예시만 갖고 $hasUncle(x,y)\leftarrow hasGrandma(x,b)\wedge hasSon(b,y)$를 rule로 도출할 수 있다는 뜻이 아니다. 다만 직접적인 support 없이도 $hasUncle(x,y)\leftarrow hasGrandma(x,b)\wedge hasSon(b,y)$를 학습에 포함시킬 수 있는 것이 RLogic의 능력이다.). 이에 따라 자연스럽게 떠오르는 또 다른 문제점이 있다.
둘째, 기존의 접근들은 logical rule을 서로 독립적이라고 가정한다. 이는 RLogic 저자들이 사용하고자 하는 deductive nature와 완전히 상반되는 가정이다. 연역 추론은 갖고 있는 rule들을 사용해 새로운 rule을 구축하기 때문에 rule 간의 종속성이 보장되어야 한다.
Logical rule은 schema level에 있지만 학습하기 위해 instance level 증거들이 필요하다. Instance level 증거들을 완전히 사용하지 않을 수도 없지만 가능하면 schema level에서 직접적으로 학습을 하고 싶어 하는 것이 저자들의 목적이다.
Architecture
먼저 어떤 것을 수행하는 모델을 만들건지 정확히 정의하고 넘어가자. 어떤 head relation을 $r_h$라고 명명하고 이를 구성, 표현할 수 있는 rule들을 찾는 것이 일차적인 목표이다. 즉 $r_h$를 표현할 수 있는 rule body $[r_{b_1},\cdots ,r_{b_n}]$를 찾고자 하는 것이며($n$은 body의 길이) 이는 AI와 지식 표현에 있어 매우 중요한 FOL(First-order logic) rule을 mining한다고 볼 수 있다. 물론 head를 구성하는 body가 연관성 없는 relation을 포함하고 있으면 안 되기 때문에 우리는 chain-like rule을 구성함에 관심이 있다.
Rule에 있는 entity variable(e.g.$, x, y, z_1$)에 실제 entity를 대입하면 하나의 rule instance를 얻을 수 있으며 이는 closed path임을 알 수 있다. 아래와 같은 예시처럼 말이다.
항상 염두해두어야 할 사실은 logical rule은 schema level 개념이지만 이를 지지해 줄 근거는 instance level에 있다. 따라서 instance level 관측과 schema level 추상화 사이의 간극을 줄이기 위해 closed path에 있는 모든 구체적인 entity를 배제한 채로 relation path와 target relation을 소개한다.
(1) relation path($\textbf{r}_b$)는 두 entity(e.g., $e_i,e_j$)를 잇는 relation 경로이다. 이는 특정 rule의 body에 해당한다.
(2) target relation($r_t$)은 단일 relation $r_t$으로 $e_i$와 $e_j$를 이어줌으로써 relation path를 닫을 수 있다.
결국 우리는 logical rule learning을 위해 하나의 closed path $(r_t, \textbf{r}_b)$에 대해 타당한 score($s(r_h, \textbf{r}_b)$)를 할당해 줄 수 있어야 한다.
RLogic Approach
하나의 triple을 input으로 사용하지 않고 sample path를 input으로 사용한다. 샘플링 방법은 나중에 설명하고 지금은 그런 경로를 input으로 사용한다 정도로 이해해도 충분하다. 연역적 추론을 rule mining에 사용하기 위해 RLogic은 긴 path를 여러 개의 작은 path로 재귀적으로 나누어 path를 하나의 relation(결국 head relation이 될 relation)으로 압축한다. 이 방법은 rule instance에서 근거를 찾지 못하는 rule 구성에 있어 매우 중요한 접근이다. 구체적으로는 아래와 같은 방법으로 2개의 relation을 1개로 압축하고 relation path에 포함시키고 다시 2개를 1개로 압축하고 이 방법을 1개의 relation이 남을 때까지 계속해서 실행하는 것이다.
물론 어떤 2개의 relation을 먼저 압축하느냐에 따라 결과가 달라질 것이다. 이 순서를 결정하는 방법에 대해서는 나중에 이야기하겠다.
Rule Evaluation
Rule을 평가하는 방법에 대해서 confidence가 가장 널리 사용된 지표이다.
위는 KG에서 body instance가 발견된 개수와 rule instance가 발견된 개수의 비율이다. 하지만 이는 우리가 앞서 논의한 문제에서 헤어나오지를 못한다. 바로 "모르는 정보"와 "틀린 정보"를 구별하지 못한다는 것인데, 그 이유는 위 식에서도 나와 있듯이 관측되지 못하는 정보는 틀렸다고 판단한다. 즉 instance가 충분히 관찰되지 못하는 지역(unknown region)에서 어떤 rule들의 score가 낮아질 위험이 크기 때문에 confidence는 data bias에 민감한 지표임을 알 수 있다.
따라서 우리는 rule에 대한 새로운 평가 지표를 만들어야 한다. 이는 rule body가 rule head를 대체할 수 있는 확률을 나타낸다.
순차적으로 구성되는 body에 대해 최종 score를 도출하는 것에 대해 RNN이 자연스러운 선택이겠지만 rule 길이 $l$에 대해 $|R|^{(l+1)}$차원의 텐서가 필요하기 때문에 너무 무겁다. 연역적 추론을 다시 떠올려보면 우리는 $q(r_h|\textbf{r}_b)$를 계산하기 위해 여러 회의(재귀적으로) $q(r_h|r_i,r_j)$가 필요하다. 가령 relation path $[r_{b_1},r_{b_2},r_{b_3}]$에 대해 $q(r_h|r_{b_1},r_{b_2},r_{b_3})$의 계산은 다음과 같다.
하지만 추측한 head가 있어도 정작 KG의 sparsity 때문에 head relation이 관측되지 않을 수도 있다. 즉 $e_i$와 $e_j$를 이어주는 relation이 없을 수도 있다는 것이다. 기존의 confidence 기반 모델들은 이에 대해 강하게 penalize 하였겠지만 RLogic에서는 $p(r_t|r_h)$를 통해 "이상적 학습(logical rule)"과 "관측 사실(KG)"의 간극을 좁힌다.
지금까지는 어떤 body $\textbf{r}_b$가 $r_h$로 표현될 확률(신뢰도)을 계산하는 방법에 대해서만 논의한다고 보면 되겠다. 지금부터 $p$와 $q$의 구체적인 계산 방법에 대해 설명하겠다.
Framework
위의 제안된 평가 방법에 대해 우리가 구체적으로 모델링 해야할 것은 $q(r_h|\textbf{r}_b)$(relation path encoder), $p(r_t|r_h)$(close ratio predictor)이다. Path $\textbf{r}_b$가 주어졌을 때 relation path encoder가 path를 $r_h$로 나타내고 이후에 $\textbf{r}_b$가 닫힐 확률을 close ratio predictor가 계산해 준다.
Predicate Representation Learning
Predicate(relation)은 logical rule에서 하나의 단위이다. Predicate을 표현하기 위해 저 차원 벡터로 이들을 학습한다. 이를 통해 어휘적으로 다른 predicate도 KG의 맥락에 따라 비슷하게 또는 다르게 표현할 수 있다(e.g., $GrandPa$, $GrandFather$). 추가적으로 KG에 들어 있지 않은(=아직 관측되지 않은) predicate도 표현해 줄 필요가 있다. 이를 수용하기 위해 null predicate($R_0$)을 추가한다. 결론적으로 score function은 predicate의 임베딩들로 계산된다.
Relation Path Encoder
두 가지 문제를 해결해야 한다. 하나는 path에 있는 relation들 중에서 어느 둘을 먼저 압축해야 할지, 다른 하나는 그렇게 압축될 relation이 뭐인지까지 알아내야 한다.
- Learning the order to deduct a relation path
어떤 쌍을 먼저 압축해야 할까? 즉 아래와 같은 문제를 해결해야 한다.
빨간 경로를 먼저 압축할 것인 파란색을 먼저 압출할 것이냐를 정해야 한다. Path의 길이가 $l$일때 모든 경우를 다 고려하여 최고의 relation 쌍을 고르게 되면 총 $\prod_{k=2}^{l-1}(l-1+k)/k$개의 경우의 수를 계산해야 한다(카탈랑 수). 하지만 이 방법은 너무 무겁기 때문에 그리디한 접근을 사용하여 계산량을 줄일 수 있다. 즉 존재하는 쌍 중에서 가장 유망한 쌍 1개를 압축하는 것이다. 더 넘어선 미래를 고려하지 않겠다는 것이다. 즉 이 방법을 사용하면 $\sum_{k=1}^{l-1}(l-k)$번만에 끝낼 수 있다.
어떤 것을 압축하는 것이 가장 best인지 알기 위해 엔트로피를 사용한다.
쌍 $(r_i,r_j)$에 대한 엔트로피가 작을수록 그 둘을 압축하기에 유망한 $r_h$를 찾을 확률이 높다는 뜻이다. 즉 매 단계마다 엔트로피가 가장 작은 쌍을 그리디하게 고른다.
- Learning the probability to replace a relation pair with a single relation
연역적 추론 순서를 알아냈다고 가정했을 때 $q(r_h|r_i,r_j)$를 어떻게 계산해야 할지 알아보자. 본 연구에서는 이를 근사하기 위해 MLP classifier를 사용한다. $f_\theta(\textbf{r}_i,\textbf{r}_j)$는 파라미터 $\theta$로 이루어져 있는 2층 NN이다. 두 predicate $r_i,r_j$를 입력으로 받고 출력 층에서는 결론적으로 압축될 수 있는 relation의 확률을 null predicate을 포함한 채로 출력한다.
$q$는 categorical distribution을 따르기 위해 마지막 출력층에서 softmax를 사용한다. 결국 이 MLP를 사용하면 3개의 relation을 줄이는 예시에서 다음과 같이 표현할 수 있다.
하지만 문제는 $q(r_h|r_{b_1},r_{b_2},r_{b_3})$를 계산하기 위해 $f_\theta$를 총 $|R|+2$번($q(r_k|r_{b_1},r_{b_2})$계산 위해 1번, 이를 통해 나온 logit $|R|+1$개에 대해 각각 $f_\theta(\textbf{r}_k,\textbf{r}_{b_3})$ 연산해주어야 한다. 연산의 경량화를 위해 식 (11)을 $f_\theta(\tilde{\textbf{r}},\textbf{r}_{b_3})$으로 근사한다.
$\tilde{\textbf{r}}$는 모든 predicate에 대한 "가중 평균"으로 이해할 수 있다. 이를 사용하면 $f_\theta$를 2번만 통과시키면 된다.
Close Ratio Predicate
이제까지 path를 하나의 predicate으로 압축하는 과정을 살펴보았다. 하지만 KG에서의 "실제 관측"과 logical rule에 따르는 "이상적 추측" 사이의 간극을 아직 해소하지 못했다. 즉 $p(r_t|r_h)$를 계산하기 위해 2층 MLP를 제안한다. 입력층은 ReLU, 출력층은 predicate의 독립적인 확률을 계산해야 하므로 sigmoid를 사용한다. 입력으로는 relation path encoder의 마지막 층에서 얻은 $\tilde{\textbf{r}}$와 $\textbf{r}_t$를 사용해 닫힐 확률을 계산한다. $p(r_t|r_h)$를 계산하는데 $r_h$가 왜 input으로 없는지 의문이 들 수도 있다. 논문에서는 생략된 표현이지만 모든 $r_h$에 대한 $p$를 구하고 싶으면 $p$를 총 $|R|+1$번 계산해주어야 하기 때문에 $q$에서 사용한 근사 기법을 여기서도 사용한 것이다. 따라서 $\tilde{\textbf{r}}$을 $r_h$ 대신 사용한다.
Model Training
앞까지는 계산 과정이 어떻게 되는지에 대한 소개였고 이 섹션에서는 $p$와 $q$가 어떻게 학습되는지 소개한다.
Closed Path Sampler for Training Data Generation
KG에 존재하는 모든 closed path를 sample 하는 것은 수고스러우니 모델 학습을 위해 훈련셋을 random walk에 기반해 작은 부분 sample 한다. 기존의 random walk와는 다르게 처음 시작 노드 $x_0$와 이후에 샘플링되는 노드 $x_i$ 사이에 closed path를 만들기 위해 간선을 추가한다.
- Objective function for training relation path encoder
샘플링된 closed path는 positive example로 취급 가능하며 negative sample은 positive sample에서 head relation을 다른 랜덤 relation으로 대체함으로써 얻을 수 있다.
KG는 Open World Assumption(OWA)을 따르기 때문에 negative sample은 필연적으로 "틀렸다"가 아닌 "positive에 비해 덜 유효한"으로 이해할 수 있기 때문에 margin 하이퍼파라미터 $\gamma$를 사용해 positive와 negative의 경계를 구분 지어준다. 이러한 OWA 가정 때문에 sampling시 closed path를 위한 간선을 생성해도 괜찮다는 입장인 것이다. Closed World Assumption(CWA)이었다면 하면 안 될 짓이지만 말이다.
- Object function for training close ratio predictor
Logical rule을 따르는 "이상적 학습"과 "실제 관측"사이의 간극을 좁히는 모델이다. KG에서 관측된 closed path는 positive, 그렇지 않은 경로들은 negative라고 할 수 있으며 여기서 negative는 위의 경우와 다르게 그냥 틀린 경우로 분류한다(그래서 $gamma$가 없다). "닫힘"과 "열림" 둘을 구분할 수 있어야 하므로 binary cross-entropy loss를 사용한다.
위의 경우 $\tilde{\textbf{r}}$를 필요로 함을 함축한다. 이때 $r_h$는 $\textbf{r}_b$에서 얻은 head이다.
마지막으로 정리를 해보겠다.
$q$(relation path encoder) : 특정 path를 하나의 relation으로 표현해주는 함수이다.
$p$(closed ratio predictor) : path로부터 도출된 $r_h$가 $r_t$와 $p$의 MLP에 들어갔을 때 결괏값이 크도록 (positive example 한정) 계산해준다. $q$의 역할은 경로 압축 뿐, 추론의 추론의 추론의 결과물이 그래서 결국 닫히냐에 대한 정보는 포함되지 않기 때문에 이를 보조해주는 역할이 $p$이다.
Rule extraction
RLogic에 의해 학습된 rule들 중에서 특정 rule들만 rule로 인정할 것이다. RLogic은 특정 relation 하나에 대해 rule을 도출할 수 있는 다른 모델들과는 다르게 전역적으로 rule 생성이 가능하다. 따라서 KG를 가장 잘 설명할 수 있는 rule을 뽑아낼 수 있는 것이다. 식 (7)에 의해 $q$가 최종 score 역할을 하기 때문에 이 값에 기반해 path를 가장 잘 나타내는 상위 $k$개의 rule을 선택하면 되는 것이다.
하지만 rule extraction에서 $q$만 사용되면 $p$의 역할은 어디가는 것인가? 모델의 구조로 미루어보았을 때 $p$는 penalize 결과물을 $q$로 스며들게 해주는 역할을 할 뿐이다. 즉 $q$는 자기 자신과 $p$를 통해 받은 feedback을 모두 학습하는 것으로 볼 수 있고 $p$는 그저 간접적인 보조 역할로 이해할 수 있다.
Experiments
KG Completion Task
RLogic이 completion에 특화된 모델(KGE)이 아님에도 비교적 좋은 성능을 보임을 알 수 있다.
RLogic의 completion task에서의 약세를 보강하기 위해 만들어진 RLogic+. RotatE를 사용해 KG의 sparsity를 해결하고 RLogic과 마찬가지로 forward chaining으로 missing tiplet을 예측하는 모델이다.
아래는 훈련 시간(단위는 분)이다.
Quality of Learned Rules in Terms of Rule Head Prediction Task
여기서부터는 rule에 대해 head relation을 얼마나 잘 예측하였는가에 대한 평가이다. Human annotation을 사용해 mining 된 rule들의 수준을 평가할 수 있다.
아래는 Family dataset에 대해 동일 길이 rule detection에 대한 MAP 지표이다.
아래는 RLogic의 relation path encoder를 RNN, LSTM으로 대체했을 때 기존 모델과의 비교이다. 좌측은 전체적인 rule detection 성과, 우측은 rule의 body 길이에 따른 모델의 성능이다.
아래는 recursive setup의 효력을 case study를 통해 증명한다. 쿼리가 주어졌을 때 head relation을 추측하는 과정에서 recursive setup이 가장 정확함을 알 수 있다.
Conclusion
순전히 rule instance에 의존해 학습하지 않고 deductive nature를 활용해 KG 추론에 있어 일반성을 잃지 않았다. 연역적 추론을 path를 압축함에 사용하여 긴 path도 효율적으로 mining 할 수 있음을 실험적으로 보여줌으로써 강력한 모델임을 피력하였다.
