지식 그래프 완성원홉 질의를 푸는 세 계보 — 심볼릭 추론, 표현 학습, 그리고 둘의 통합

KG 완성은 형식적으로 머리 엔티티와 관계가 주어질 때 꼬리 엔티티를 추론하는 문제 (ei, rk, ?) 또는 꼬리 엔티티와 관계가 주어질 때 머리 엔티티를 추론하는 문제 (?, rk, ej)로 정식화된다. 예컨대 아래 Fig. 3.1에서 질의 (Mary Stilwell, LiveIn, ?)는 “Mary Stilwell은 어디에 사는가”를 묻는다. KG 완성은 다음 장에서 논의할 복합 질의와 대비되는 원홉 질의로 볼 수 있다.

기존 방법은 세 갈래로 나뉜다.

심볼릭 추론 기반 KG 완성에서는 미리 정의된 논리 규칙을 사용해 기존 사실을 근거로 새로운 사실을 추론한다. 이 규칙은 통상 1차 논리 같은 형식 논리로 표현된다. 예컨대 아래 규칙이 주어지면 추론을 통해 질의 SpeakLanguage(Mina Miller, ?)에 답할 수 있다.

SpeakLanguage(x, y) ← LiveIn(x, z) ∧ OfficialLanguage(z, y)(3.1)

구체적으로 규칙 (3.1)의 변수 x, y, z를 구체적 엔티티 “Mina Miller”, “English”, “USA”로 대체해 기저 규칙을 얻는다.

SpeakLanguage(Mina Miller, English) ← LiveIn(Mina Miller, USA)
                                     ∧ OfficialLanguage(USA, English) (3.2)

LiveIn(Mina Miller, USA)와 OfficialLanguage(USA, English)는 KG에서 관측된 두 트리플에 의해 참이므로 규칙 몸통이 참이다. 전건 긍정을 적용하면 결론 SpeakLanguage(Mina Miller, English)도 True다. 따라서 “English”가 질의의 답이 된다.

심볼릭 추론 기반 KG 완성은 논리 규칙 형태의 도메인 지식을 추론 과정에 자연스럽게 결합할 수 있다. 전체 과정이 투명하고 해석 가능하므로, 효과성과 해석 가능성이 동시에 결정적인 의료·금융·과학 연구 같은 도메인에서 특히 유용하다.

3.2.1문제 정의

G = {E, R, O}를 KG라 하고, 각 트리플 (ei, rk, ej) ∈ O를 심볼릭 추론 맥락의 기저 술어로 본다. 관측된 기저 술어를 vO = {rk(ei, ej) | (ei, rk, ej) ∈ O}로 표기하며, 모든 rk(ei, ej) ∈ vO의 진리값은 1이다.

미리 정의된 논리식 집합 F = {Fi}가 주어질 때, 심볼릭 추론 관점의 KG 완성 태스크는 만족되는 논리식의 총 개수를 최대화하도록 모든 은닉 기저 술어 vH에 진리값을 할당하는 것이다. 이는 본질적으로 최대 충족 가능성 문제(MAX-SAT)다. 더 일반적으로는 각 논리식 Fi에 중요도를 나타내는 가중치 wi를 도입해 가중 MAX-SAT 문제, 즉 만족된 규칙의 가중 합을 최대화하는 진리값 할당을 찾는 문제로 전환된다.

각 기저 술어에 할당되는 진리값에 따라 기존 심볼릭 방법은 크게 두 범주로 나뉜다. (1) 불 논리 기반 — 진리값 할당이 불 값이다(I(rk(ei, ej)) ∈ {0, 1}). (2) 확률 논리 기반 — 각 가능 세계에 확률이 결합되거나 기저 술어의 진리값이 [0, 1] 범위를 취한다.

3.2.2불 논리 기반 추론

각 술어에 True(1) 또는 False(0)가 할당되면 KG 완성 태스크는 본질적으로 MAX-SAT 문제다. MAX-SAT의 표준형은 이산 최적화 문제이며, 주어진 CNF 불 논리식에 대해 만족되는 절의 최대 개수를 결정한다. KG 맥락에서 각 원자는 rk(ei, ej) ∈ vO ∪ vH 형태의 기저 술어이고, 각 논리 규칙이 하나의 절에 대응한다. 예컨대 규칙 Q ← P1 ∧ P2는 절 ¬P1 ∨ ¬P2 ∨ Q로 표현된다.

목표는 만족되는 절의 개수를 최대화하는 은닉 변수 vH의 진리값 할당을 찾는 것이다. 각 논리식에 가중치가 결합되면 가중 MAX-SAT가 되고, 목표는 만족된 절의 총 가중치를 최대화하는 할당을 찾는 것이 된다. 모든 가중치가 같으면 가중 MAX-SAT는 표준 MAX-SAT로 환원된다.

MAX-SAT는 NP-난해하다 [6]. 즉 최적해를 찾는 데 최악의 경우 지수 시간이 필요하므로, 크고 복잡한 인스턴스에서 정확해는 흔히 실현 불가능하다. 이 때문에 실무에서는 다수의 근사 알고리즘이 사용된다. 지역 탐색(local search)은 가장 대표적인 근사 알고리즘으로, 변수의 현재 할당에 작은 변화(플립)를 주며 해 공간을 탐색해 만족되는 절의 개수를 최대화하는 할당을 찾는다.

MAX-SAT의 NP-난해성 때문에 논리적 추론은 일반적으로 어렵지만, 논리 규칙을 확정적 Horn 규칙으로 제한하면 다항 시간의 더 효율적인 알고리즘을 사용할 수 있다. 널리 쓰이는 두 추론 알고리즘은 전방 연쇄와 후방 연쇄다.

3.2.2.3 전방 연쇄와 후방 연쇄의 비교

두 알고리즘의 주된 차이는 추론의 방향이다. 전방 연쇄는 가용 증거로부터 앞으로 진행하고, 후방 연쇄는 목표(또는 결론)로부터 뒤로 진행한다. 전방 연쇄는 증거에서 시작하므로 데이터 주도이며, 추론 과정에서 우리 질문과 무관할 수 있는 다수의 결론까지 추론한다. 후방 연쇄는 목표에서 시작하므로 목표 주도이며, 추론 사슬에 포함된 증거와 규칙만 다루므로 통상 전방 연쇄보다 훨씬 빠르다.

3.2.3확률 논리 기반 추론

불 논리는 세계에 관한 복잡한 관계와 지식을 포착하는 데 효과적이지만, 다수의 실세계 응용에 존재하는 불확실성을 다룰 수 없다. 즉 서로 다른 확률로 참일 수 있는 여러 가능 세계가 존재할 수 있다. 이를 해결하기 위해 확률 논리는 논리와 확률을 통합하는 강력한 해법을 제공한다. FOL의 표현력과 확률적 접근의 강건성을 동시에 사용해 불확실성을 지닌 KG를 더 잘 모델링하고 추론할 수 있게 한다. 마르코프 논리 네트워크(MLN)와 확률적 연성 논리(PSL)가 가장 대표적인 두 접근이다.

3.2.3.1 마르코프 논리 네트워크 (MLN)

그래프 모델은 변수 사이의 복잡한 의존을 다루는 강력한 확률 모델군이다. MLN [7]은 (무향) 그래프 모델군에 속하는 마르코프 네트워크의 특수한 경우다 [8]. 마르코프 네트워크는 변수를 노드로, 의존을 엣지로 표현하며, 그래프 구조에 따라 모든 변수의 결합 확률을 정의한다. KG 완성 태스크에서 변수는 기저 술어 (vO ∪ vH)이며 1 또는 0을 취하는 이진 변수다.

FOL 논리식 집합 F와 가중치 벡터 w가 주어질 때 MLN은 다음 방식으로 마르코프 네트워크의 그래프 구조를 구성한다.

• KG의 관측·미관측 기저 술어를 모두 포함해, 각 기저 술어마다 노드를 하나 만든다. vO는 관측된 트리플에 대응하는 변수 전체, vH는 관측되지 않은 나머지 기저 술어 전체를 나타낸다.
• 두 기저 술어가 같은 기저 규칙에 참여할 때에만 두 노드를 잇는 엣지를 만든다.

일반적인 마르코프 네트워크는 클리크(완전 부분그래프)에 따라 모든 변수의 결합 확률을 분해한다. MLN의 경우 엣지가 두 변수의 동일 규칙 참여 여부로 정의되므로 클리크는 논리 규칙에 대응한다. 예컨대 Sport(A)와 Healthy(A)는 기저 규칙 Sport(A) ⇒ Healthy(A)에 대응하는 크기 2의 클리크를 형성한다. MLN에서 vO와 vH의 결합 확률은 다음과 같이 정의된다.

p_w(v_O, v_H) = (1 / Z(w)) · exp( Σ_{i : Fi ∈ F} w_i n_i(v_O, v_H) )(3.4)

여기서 wi는 FOL 논리식 Fi의 학습 가능한 가중치이고, ni(vO, vH)는 vO, vH의 값이 주어질 때 참인 Fi의 기저 논리식 개수이며, Z(w)는 모든 세계의 확률 합을 1로 만드는 정규화 상수다.

KG 완성 태스크는 MLN에서 vH에 대한 추론 문제, 즉 관측된 트리플과 모델이 주어질 때 미관측 트리플에 대한 최대 확률 할당을 계산하는 문제가 된다(maxvH pw(vH|vO) ≡ maxvH pw(vO, vH)). MLN 추론은 계산 비용이 크며 #P-완전이다 [7]. 계산 부담을 줄이기 위해 MLN 추론은 통상 마르코프 연쇄 몬테카를로(MCMC), 특히 깁스 샘플링 [9, 10]으로 근사해를 구한다. 기본 착상은 각 기저 술어를 자신의 마르코프 블랭킷(그래프에서의 이웃)이 주어진 조건에서 차례로 샘플링하는 것이다. 또 다른 인기 있는 방법은 신뢰 전파(belief propagation) [11, 12]로, 네트워크 구조의 의존성을 활용해 추론을 가속한다. 핵심 착상은 메시지 전달 알고리즘으로 신뢰(확률 분포)를 네트워크에 전파하며, 이웃에서 받은 메시지를 근거로 각 노드의 신뢰를 반복적으로 갱신하는 것이다.

추론 문제에서는 통상 각 논리식의 가중치 w가 주어졌다고 가정한다. 가중치는 실제로 우도 maxw pw(vO, vH)를 최대화해 학습할 수 있으며 이는 학습 문제에 해당한다. 가중치는 통상 의사 우도(pseudo-likelihood) [13]처럼 특정 의존을 제거해 원 목적식을 단순화하는 방식으로 근사적으로 학습된다. 학습 문제는 KG 완성 설정에서는 보통 논의되지 않는다.

3.2.3.2 확률적 연성 논리 (PSL)

PSL [14]은 불확실성을 추론 과정에 결합하는 또 다른 방법을 제공한다. 각 변수의 불 값 할당을 연성 확률로 완화하여, 기저 추론을 볼록 최적화 문제로 신속히 풀 수 있게 한다. I(rk(ei, ej))는 기저 술어에 부여된 [0, 1] 구간의 연성 진리값으로, 그 기저 술어가 참일 가능성을 나타낸다. 사상 I : vO ∪ vH → [0, 1]을 해석이라 부른다.

기저 규칙이 만족되는 정도를 판정하기 위해 PSL은 논리 AND·OR를 비이진 변수로 완화하는 데 우카시에비치 t-노름과 그 t-코노름 [15]을 사용한다.

I(x ∧ y) = max{0, I(x) + I(y) − 1}
I(x ∨ y) = min{1, I(x) + I(y)}
I(¬x) = 1 − I(x)

기저 논리 규칙은 함의 형식에서 논리합 형식으로 변환될 수 있으므로, 위 함수로 임의의 기저 규칙 f의 연성 진리값 I(f)를 계산할 수 있다.

r_head ← r_body ≡ r_head ∨ ¬r_body(3.5)

d(f) = 1 − I(f)를 만족까지의 거리(distance to satisfaction)로 정의하며, 이는 기저 규칙이 위반되는 정도를 연성으로 측정한다. 논리합 형식의 기저 논리 규칙에 위 연산자 정의를 적용하면 만족까지의 거리는 다음과 같이 계산된다.

d(f) = 1 − I(f)
      = 1 − min(1, I(r_head) + I(¬r_body))
      = max{0, I(r_body) − I(r_head)}

따라서 기저 규칙 f는 머리의 진리값이 몸통의 진리값과 같거나 그보다 높을 때에만 만족된다(d(f) = 0). 기저 원자 논리식 집합이 주어질 때 PSL 프로그램은 가능한 해석에 대한 분포를 정의한다. F를 프로그램 내 규칙의 인스턴스인 모든 기저 규칙의 집합이라 하면, I에 대한 확률 밀도 함수는 다음과 같다.

(1 / Z(w)) · exp( Σ_{i : fi ∈ F} w_i (I(f_i))^p )(3.6)

wi는 기저 규칙 fi의 가중치, Z(w)는 정규화 항의 연속 버전이며, p ∈ {1, 2}는 두 가지 손실 함수 선택을 제공한다. 비형식적으로 선형 손실(p = 1)은 상충하는 규칙의 만족 거리가 커지는 것을 감수하면서 하나의 규칙을 완전히 만족시키는 해석을 선호하고, 이차 손실(p = 2)은 모든 규칙을 어느 정도씩 만족시키는 해석을 선호하여 통상 극단값에서 더 먼 진리값을 갖는다.

MLN과 달리 PSL의 기저 추론 문제는 볼록 최적화 문제로 수학적으로 모델링되므로 풀기 쉽고 MLN보다 효율적이다. 이 덕분에 PSL은 확장성이 높아 대규모 응용에 더 적합하다. 또한 PSL의 템플릿은 유연하게 설계되어 사용자가 필요에 맞게 손쉽게 맞춤화할 수 있으므로 대체로 MLN보다 사용하기 쉽다. 예컨대 PSL은 엔티티 해소(entity resolution) 태스크를 효과적으로 다룰 수 있다 [14]. 두 엔티티가 같은 실세계 객체를 지칭하는지 판정하는 이 태스크에서, 두 엔티티가 동일하다고 믿는 정도는 이름의 유사도 같은 여러 요인에 의존한다. PSL에서는 이 의존을 다음 규칙으로 표현할 수 있다.

1.0 : Same(P₁, P₂) ← Name(P₁, N₁) ∧ Name(P₂, N₂) ∧ Similar(N₁, N₂)(3.7)

MLN과 마찬가지로 PSL 기반 접근도 여전히 논리 규칙의 기저화를 요구하므로 대규모 KG에서는 시간이 많이 소요된다.

전통적 심볼릭 방법은 KG 추론에서 강한 해석 가능성과 일반화 가능성을 보이지만, 실세계 KG가 통상 (1) 대규모이고 (2) 모호하며 (3) 노이즈를 포함하기 때문에 실세계 KG에 적용하기 어렵다.

위 문제를 해결하기 위해 지식 그래프 임베딩(KGE) 방법이 KG 완성에 널리 사용되고 있다. KGE의 일반적 착상은 엔티티와 관계 같은 이산 기호를 저차원 연속 벡터, 즉 임베딩으로 표현해 [16] 이 벡터들로 KG 구조를 보존하는 것이다. 학습된 임베딩은 새로운 사실을 예측하는 데 사용된다.

KGE는 확률적 경사 하강(SGD)으로 효율적으로 학습될 수 있어 상대적으로 적은 반복으로 빠르게 수렴하고 좋은 결과를 낸다. 확장성이 매우 높아 수백만 엔티티와 관계를 지닌 실세계 대규모 KG를 처리할 수 있다. 또한 엔티티 중의성 해소 같은 복잡한 패턴을 포착할 수 있다. 예컨대 (Steve Jobs, eat, apple)과 (Steve Jobs, co-found, Apple)의 두 트리플에서 “Apple”의 두 의미를 구별하는 별개의 하위 표현을 학습할 수 있다. KGE는 KG의 노이즈를 자연스럽게 처리하며, 유사한 엔티티와 유사한 관계 사이의 유사성을 임베딩 벡터에 보존한다.

3.3.1KGE 방법 개관

전통적 심볼릭 방법과 달리 KGE는 논리 규칙을 활용하지 않고 KG의 관측된 사실에만 의존한다. KG의 트리플이 얼마나 그럴듯한지를 측정하는 점수 함수가 KGE 모델의 핵심이다. 점수 함수의 차이에 따라 기존 KGE 방법은 크게 (1) 기하 연산 기반, (2) 이중선형, (3) 심층 학습 기반의 세 범주로 나뉜다.

전형적인 KG 임베딩 방법은 세 구성 요소로 이루어진다.

점수 함수의 선택은 서로 다른 의미적 성질에 따라 상이한 특성을 보이는 KG의 다양한 관계를 모델링하는 데 결정적이다. 강력한 임베딩 방법은 더 넓은 범위의 관계 성질을 포착할 수 있어야 한다.

3.3.2기하 변환 기반 KGE

이 계열에서 엔티티는 기하 공간의 점으로, 관계는 머리 엔티티를 꼬리 엔티티로 변환하는 기하 연산으로 취급된다. 엔티티와 관계 모두 학습 가능한 임베딩 벡터를 가지므로 얕은 임베딩에 속한다. KG의 관계를 표현하는 데 가장 널리 사용되는 기하 연산은 이동(translation)과 회전(rotation)이다.

3.3.2.1 이동 기반 모델: TransE와 변형

이동 기반 방법은 엔티티를 d차원 유클리드 공간의 점으로, 관계를 d차원 벡터로 표현되는 이동 연산으로 취급한다. TransE [17]는 KG 임베딩에 이동 착상을 처음 제안한 가장 대표적인 모델이다. 트리플 (ei, rk, ej)의 점수 함수는 ei + rk와 ej 사이 거리의 음수, 즉 투영된 꼬리 엔티티와 실제 꼬리 엔티티 사이의 거리로 정의된다.

f_rk(e_i, e_j) = − ‖ e_i + r_k − e_j ‖₂²(3.8)

단순함에도 TransE는 이동 연산이 일대일 사상이라는 성질 때문에 반사·대칭·1-N·N-1·N-N 관계를 다룰 수 없다. “Friend”는 대칭 관계지만, 이동 연산에 따르면 ei + rk = ej일 때 rk = 0이 아니면 ej + rk = ei가 성립하지 않는다. “hasSibling”은 1-N 관계여서 같은 엔티티에 여러 형제가 관측될 수 있지만, TransE는 이동 연산으로 엔티티를 한 점에만 투영할 수 있다. 이 한계를 넘기 위해 TransH [18], TransR [19], TransD [20] 같은 변형이 제안되었다(부록 A.1.1에 정리).

3.3.2.2 회전 기반 모델: RotatE

RotatE [21]는 복소 공간의 회전 연산에 기반한다. 엔티티를 복소 공간에 정의해 각 임베딩 차원이 복소수이며(ei, ej ∈ Cd), 관계는 각 차원에서 계수(modulus)가 1인 회전 연산이다(|rk,m| = 1). 오일러 공식에 따라 회전 연산은 eiθk,m = cos(θk,m) + i sin(θk,m)로 쓸 수 있으며, 머리 엔티티의 대응 복소수를 각 θk,m만큼 반시계 방향으로 회전시켜 꼬리 엔티티의 다른 복소수로 만든다. 트리플이 주어질 때 머리 엔티티의 회전은 아다마르(성분별) 곱 ei ∘ rk로 정의되며, 이것이 꼬리 엔티티 ej에 가까워지기를 기대한다.

f_rk(e_i, e_j) = − ‖ e_i ∘ r_k − e_j ‖_p     where  ‖v‖_p = (Σ_m |v_m|^p)^1/p(3.9)

RotatE는 대칭/비대칭 같은 서로 다른 성질을 보이는 관계를 모델링할 수 있고, 역·합성 같은 관계 간 관계도 수용한다. 각 성질이 만족해야 하는 요건은 다음과 같다.

• 대칭 관계 — 대칭 관계 임베딩의 각 차원이 rk,m = e0/iπ = ±1, 즉 θk,m = 0 또는 π를 만족한다. 회전을 두 번 적용하면 같은 엔티티로 돌아오는 것이 보장된다.
• 비대칭 관계 — rk의 차원 중 적어도 하나가 rk,m = ±1을 만족하지 않는다.
• 역 — 역 관계의 임베딩은 모든 성분에 대해 서로 켤레여야 한다. 즉 대응하는 각이 θ1,m = −θ2,m이다.
• 합성 — 두 관계 r1, r2가 주어질 때 합성의 표현은 자연스럽게 r3 = r1 ∘ r2로 계산된다.

TransE와 유사하게 RotatE도 반사·1-N·N-1·N-N 관계는 다룰 수 없다. 원 논문은 비대칭을 anti-symmetric이라 지칭했으나, anti-symmetric 관계는 반사적일 수 있고 이는 여기서 만족되지 않으므로 이 책은 asymmetric을 사용한다.

3.3.2.3 요약. 기하 연산 기반 모델은 엔티티 간 관계를 기하 변환으로 모델링하므로 다른 KGE 방법에 비해 통상 더 직관적이고 해석 가능하다. 다만 명확한 기하학적 해석이 없는 복잡한 관계를 모델링할 때 어려움에 부딪힐 수 있다.

3.3.3이중선형 KGE 모델

관계를 위한 기하 변환을 명시적으로 설계해 거리 기반 점수 함수를 유도하는 대신, 이중선형 모델로 트리플의 점수 함수를 직접 정의할 수 있다.

f_rk(e_i, e_j) = e_i^⊤ M_rk e_j

Mrk는 관계 rk에 대해 엔티티 임베딩 공간의 차원 사이 쌍별 상호작용을 모델링하는 d × d 행렬이다. 이중선형 모델은 ei를 관계별 선형 변환으로 투영한 뒤 Mrk⊤ei와 ej의 내적으로 점수를 계산하는 것으로도 볼 수 있다. 선형 변환은 회전·반사·스케일링·전단 등 여러 유형의 기하 연산을 포섭하므로 이론적으로 앞 절의 연산자보다 강력하다.

대표적인 정규 행렬

• 대칭 행렬 Mrk = Mrk⊤(대각 행렬은 특수 경우) — 대칭 관계 모델링에 사용된다. 예: [[1, 2], [2, 1]].
• 반대칭 행렬 Mrk = −Mrk⊤ — 비대칭 관계 모델링에 사용된다. 예: [[0, −1], [1, 0]].
• 회전 행렬 MrkMrk⊤ = I — 1-1 사상 관계 모델링에 사용된다. 예: [[1/2, −√3/2], [√3/2, 1/2]].
• 순환 행렬(circulant) — 각 행이 같은 원소 집합을 담고 다음 행은 이전 행의 최우측 원소를 최좌측으로 이동시킨 형태다. 완전 행렬보다 훨씬 적은 파라미터로 비대칭 관계를 모델링할 수 있다.

그 밖의 이중선형 변형으로 SimplE [25], HolE [26]가 제안되었다(부록 A.1.2에 정리). 3.3.3.3 요약. 이중선형 모델은 이중선형 함수로 엔티티 사이의 복잡한 상호작용을 포착하므로 기하 모델보다 표현력이 높다. 다만 기하 모델보다 해석하기 더 까다로울 수 있다.

3.3.4심층 표현 학습 기반 KGE 모델

앞선 모델은 모두 학습 가능한 임베딩을 점수 함수(디코더)에 직접 넣는 얕은 임베딩 범주에 속한다. CNN [28], RNN [29], Transformer [30], GNN [31] 같은 심층 학습 모델의 발전에 따라, 초기 학습 가능 임베딩을 더 깊은 표현으로 변환하는 복잡한 인코더가 설계되었다.

3.3.4.5 요약. 심층 학습 기반 모델은 강력하며 KG의 복잡한 패턴과 의존을 모델링할 수 있다. 다만 좋은 성능을 얻으려면 통상 많은 데이터를 요구하고, 관계를 위해 세심하게 설계된 초기 변환들에 비해 해석 가능성이 떨어진다.

3.3.5모델 학습

점수 함수가 잘 정의되어 KGE 모델이 구성되면, 모델 파라미터는 표준 기계 학습 학습 절차를 따라 학습된다. O를 KG의 관측 트리플 집합, (e′i, rk, e′j)를 양성 트리플에 대한 음성 트리플, N(ei, rk, ej)를 대응하는 음성 트리플 집합이라 하면, 학습 목적의 일반적 착상은 (1) 양성 트리플을 음성으로부터 구별하거나 (2) 양성 트리플을 음성보다 높게 순위 매기는 것이다.

3.3.5.1 학습 목적 — 분류 기반 손실

가장 단순한 손실 함수는 양성과 음성을 구별하는 교차 엔트로피 손실이다. DistMult [23], ANALOGY [27] 같은 이중선형 모델이 이 손실을 사용한다.

− Σ_{(ei,rk,ej) ∈ O} [ log σ(f_rk(e_i, e_j)) + Σ_{(e′i,rk,e′j) ∈ N} (1/|N|) log σ(−f_rk(e′_i, e′_j)) ](3.10)

교차 엔트로피 손실의 확장으로 확률을 조정하는 마진 항 γ > 0을 추가할 수 있다. RotatE [21]가 이 손실을 사용한다.

− Σ_{(ei,rk,ej) ∈ O} [ log σ(f_rk(e_i, e_j) + γ) + Σ_{(e′i,rk,e′j) ∈ N} (1/|N|) log σ(−f_rk(e′_i, e′_j) − γ) ](3.11)

순위 기반 손실

가장 빈번히 사용되는 손실 함수는 마진 기반 쌍별 순위 손실이다. 양성 트리플의 점수를 대응 음성보다 최소 γ만큼 높게 만들고, 그러지 못하면 벌점을 부과한다. TransE와 그 변형이 이 손실을 사용한다.

Σ_{(ei,rk,ej) ∈ O} Σ_{(e′i,rk,e′j) ∈ N} max( 0, γ − f_rk(e_i, e_j) + f_rk(e′_i, e′_j) )(3.12)

3.3.5.2 음성 트리플 생성

음성 트리플은 학습 목적을 정의하는 데 결정적이지만 KG는 양성 트리플만 담는다. 전통적 임베딩 모델은 닫힌 세계 가정(CWA), 즉 KG에 포함되지 않은 모든 트리플은 False라는 가정을 따라 음성 트리플을 구성한다. 양성 트리플의 머리 또는 꼬리 엔티티를 손상시켜 만든다.

N(e_i, r_k, e_j) = {(e′_i, r_k, e_j) | (e′_i, r_k, e_j) ∉ O} ∪ {(e_i, r_k, e′_j) | (e_i, r_k, e′_j) ∉ O}(3.13)

N(ei, rk, ej)는 통상 수천 개의 음성 트리플을 담으므로 전부 계산에 포함하는 것은 비현실적이다. 계산 복잡도를 줄이기 위해 소수만 무작위 샘플링하지만, 무작위 생성된 음성 일부는 양성과 구별하기 너무 쉬워 학습에 거의 기여하지 못한다.

전통적 논리 추론 접근은 논리 규칙으로 추론을 구현하며, 심볼릭 표현의 힘 덕분에 뛰어난 해석 가능성과 일반화 가능성을 보인다. 그러나 이산 심볼릭 표현은 심각한 확장성 문제를 야기하고 엔티티·관계 사이의 내재된 상관을 탐색할 수 없다. 반면 KGE는 엔티티를 연속 벡터 표현으로 임베딩해 KG의 네트워크 구조를 인코딩하며, 신경망으로 점수 함수를 학습해 누락 지식을 예측한다. KGE는 좋은 확장성과 원자 사이 상관 포착 능력을 보였지만, 대부분은 KG 관계의 고차 의존을 모델링하지 못하거나 논리 규칙 형태의 추가 지식을 고려하지 못한다. 두 기법을 통합된 프레임워크로 결합하면 뉴로-심볼릭 추론은 더 효율적이고 일반화 가능하며 해석 가능한 KG 추론 방식을 제공한다.

KGE의 점수 함수가 KG의 트리플에 연성 진리값을 제공하므로, 임베딩 모델과 사전 정의된 논리 규칙을 결합하는 데 확률적 프로그래밍 프레임워크가 널리 사용된다. 3.2절에서 소개한 확률적 프로그래밍 프레임워크의 유형에 따라 기존 뉴로-심볼릭 통합 연구는 크게 두 범주로 나뉜다. (1) MLN의 변분 추론을 위한 임베딩 기반 변분 분포, (2) 임베딩 모델을 정규화하는 퍼지 논리 기반 정규화.

3.4.1MLN을 위한 임베딩 기반 변분 추론

MLN [7]은 확률 그래프 모델과 FOL을 결합해 모든 기저 술어 변수에 대한 결합 확률을 정의할 수 있고, KG 완성 태스크는 확률 모델의 추론 문제가 된다. 그러나 MLN 구성은 술어와 논리 규칙의 기저화를 포함하고, MLN 추론은 확률적 추론을 포섭하여 #P-완전이다. 구성 복잡도와 추론 복잡도 모두가 대규모 데이터셋에서 MLN의 적용을 막는다.

최근 변분 추론 [46]이 훨씬 효율적인 방식으로 추론 문제의 근사해를 제공하기 위해 제안되었으며, 핵심은 원래의 사후 분포를 근사하는 변분 분포를 설계하는 것이다. KG 설정에서 KG 임베딩은 각 트리플이 참일 확률을 정의하는 데 사용될 수 있으므로, 임베딩 기반 분포가 MLN의 변분 추론을 수행하는 변분 분포로 자연스럽게 제안된다. 초기 연구는 각 트리플을 서로 독립으로 간주했고, 후기 연구는 의존을 포착하기 위해 KG 임베딩 모델로 그래프 신경망을 사용하여 더 효과적인 관계 데이터 모델링에 이르렀다.

3.4.1.1 pLogicNet

pLogicNet [47]은 MLN을 위한 가장 대표적인 임베딩 기반 변분 추론 알고리즘이다. MLN에 따르면 모든 술어 변수의 결합 확률은 pw(vO, vH)이며, KG 완성 태스크는 사후 확률 pw(vH|vO)를 최대화하는 할당 vH를 찾는 것이다.

변분 추론의 주된 착상은 참 사후 분포에 가까운 더 단순한 분포 qθ(vH)를 찾는 것이며, 두 분포의 거리는 KL 발산으로 측정된다. 참 사후 분포가 미지이므로 KL 발산을 직접 최소화하기는 어렵다. 다행히 증거 하한(ELBO)이라 불리는 다른 항을 최대화할 수 있다.

L(q_θ, p_w) = E_qθ(vH) [ log p_w(v_O, v_H) − log q_θ(v_H) ](3.17)

분포의 KL 발산과 ELBO의 합이 주변 분포의 로그 log pw(vO)와 같음을 증명할 수 있고, 이 값은 변분 분포의 파라미터에 대해 상수다. 따라서 두 분포의 KL 발산을 최소화하는 것은 ELBO를 최대화하는 것과 동등하다.

pLogicNet에서 변분 분포는 각 트리플의 진리값이 독립적으로 베르누이 분포를 따르고 그 파라미터가 임베딩 점수 함수로 지정된다고 가정해 KGE 모델로 정의된다.

q_θ(v_H) = ∏_{(ei,rk,ej) ∈ H} q_θ(r_k(e_i, e_j)) = ∏_{(ei,rk,ej) ∈ H} f_rk(r_k(e_i, e_j))(3.18)

rk(ei, ej) ∼ Ber(frk(ei, ej))이고 frk(ei, ej)는 트리플이 참일 확률을 나타내는 임베딩 점수다. 예컨대 DistMult에서는 σ(ei⊤ diag(rk) ej)로 정의될 수 있다. ELBO는 변분 EM 알고리즘 [48]으로 효과적으로 최적화된다.

실세계 KG에는 은닉 트리플이 매우 많으므로(|E| × |R| × |E| \ |O|) 전부 최적화하는 것은 계산 제약상 불가능하다. 부담을 줄이기 위해 은닉 트리플의 더 작은 부분집합을 샘플링해 은닉 집합 H를 구성한다. 한 가지 샘플링 방법은 규칙 몸통이 완전히 관측된 기저 규칙의 머리 역할을 하는 미관측 트리플을 선택하는 것이다. pLogicNet의 확장으로 GNN을 KG 임베딩 모델로 사용하는 ExpressGNN [50], pGAT [51]이 있다(부록 A.2.1).

3.4.2퍼지 논리 기반 정규화

퍼지 논리는 MLN의 대안적 접근을 제공한다. KG와 기저 논리 규칙으로 마르코프 네트워크를 구성하는 대신, PSL은 논리 규칙을 추가 제약으로 사용해 원래 KGE 손실에 정규화 항을 형성한다. 각 술어 기반 원자는 임베딩으로 정의될 수 있는 [0, 1] 범위의 연성 진리값을 갖고, 각 기저 논리 규칙이 논리식에 대응하여 퍼지 논리로 진리값이 평가된다. 직관적으로 임베딩은 논리 규칙과 일관되어야 하며, 이는 대응하는 기저 규칙의 진리값을 높인다.

3.4.2.1 기저 규칙에 대한 정규화

임베딩 기반 접근과 퍼지 논리를 잇는 다리는 각 기저 술어에 대한 연성 진리값 할당 I(rk(ei, ej))다. 임베딩 관점에서는 각 트리플의 점수 함수를 [0, 1] 범위로 변환할 수 있고, 퍼지 논리 관점에서는 각 기저 원자 논리식에 대한 진리값이 있으면 임의의 규칙의 진리값을 평가할 수 있다. 목표는 주어진 규칙에도 높은 진리값을 주는 임베딩을 찾는 것이다. 전형적인 통합은 다음 네 단계로 정의된다.

첫 시도 — Rocktäschel et al. [52]

이 계열의 첫 통합 시도 중 하나다. 임베딩 측면에서 개별 엔티티의 임베딩을 학습하는 대신 행렬 분해로 엔티티 쌍의 결합 임베딩 vei,ej와 관계 임베딩 vrk를 학습한다. 각 트리플의 점수 함수는 σ(vrk · vei,ej)로 정의된다. 임베딩이 주어질 때 가능 세계의 우도는 다음과 같다.

∏_{rk(ei,ej) ∈ vO} I(r_k(e_i, e_j))  ·  ∏_{rk(ei,ej) ∈ vH} (1 − I(r_k(e_i, e_j)))(3.19)

ℓ₂ 정규화 [53]와 함께 KG의 모든 관측 트리플에 대한 우도를 최대화하면, 관측 사실을 재구성하고 누락 사실로 일반화할 수 있는 엔티티 쌍·관계 임베딩을 학습한다. 이 목적식은 KGE의 분류 기반 손실 (3.10)과 동등하다. 논리 규칙 F를 임베딩에 주입하기 위해, 모델 하에서 F의 논리식이 참일 우도의 로그 변환의 음수로 로지스틱 손실을 정의한다.

− Σ_{f ∈ F} log( I(f) )(3.20)

기저 규칙 f의 연성 진리값 I(f)는 곱 논리를 따라 계산된다. 두 손실의 통합은 다음과 같이 쓸 수 있다.

− Σ_vO log(I(r_k(e_i, e_j))) − Σ_vH log(1 − I(r_k(e_i, e_j))) − Σ_f log(I(f))(3.21)

KALE [54]

첫 시도와 비교해 KALE는 (1) 각 트리플에 진리값을 부여하는 다른 점수 함수를 쓰고, (2) 양성 기저 규칙에 더해 음성 기저 규칙을 도입한다. 진리값에는 TransE 기반 점수 함수 I(rk(ei, ej)) = 1 − (1/(3√d)) ‖ei + rk − ej‖1를 사용한다.

다음으로 템플릿 논리 규칙이 주어질 때 양성·음성 기저 규칙 집합을 샘플링한다. 음성 기저 규칙은 양성 기저 규칙의 결론에 있는 관계를 무작위 관계로 대체해 구성한다.

f⁺ : liveIn(Edison, USA) ← isMarriedTo(Edison, Miller) ∧ liveIn(Miller, USA)

f⁻ : bornIn(Edison, USA) ← isMarriedTo(Edison, Miller) ∧ liveIn(Miller, USA)

샘플링된 규칙 외에 양성·음성 트리플도 전통적 KGE 방식과 유사하게 샘플링되며, 이들은 원자 논리식이다. 두 범주 모두 논리식이라는 개념으로 통일되어 f+, f−로 표기된다. KALE는 마진 기반 분류 손실을 따라 모든 샘플링된 논리식에 대한 손실을 정의해 양성 논리식을 음성으로부터 구별한다.

Σ_f⁺ Σ_{f⁻ ∈ Nf⁺} [ γ − I(f⁺) + I(f⁻) ]₊(3.22)

샘플링된 논리식 전체에서 기저 규칙을 제거하면 이 손실은 일반적인 TransE 기반 임베딩 손실로 축퇴한다.

UKGE [55] — 확률적 KG 모델링

대부분의 기존 방법이 결정론적 KG를 모델링하는 반면, UKGE는 각 트리플에 참일 신뢰 점수 crk(ei,ej)가 결합된 확률적 KG를 모델링하도록 확장한다. KGE 점수 함수를 [0, 1]의 신뢰값으로 변환하는 두 가지 사상 함수를 사용한다.

I(r_k(e_i, e_j)) = φ( f_rk(e_i, e_j) ),    φ : R⁺ ∪ {0} → [0, 1](3.23)

로지스틱 함수    φ(x) = 1 / (1 + e^−(wx+b))                        (3.24)
유계 정류기       φ(x) = min(max(wx + b, 0), 1)             (3.25)

UKGE는 DistMult 점수 함수 frk(ei, ej) = rk · (ei ∘ ej)를 사용한다. 정리하면 KG 트리플의 해석은 다음과 같이 정의된다.

I(r_k(e_i, e_j)) = c_rk(ei,ej)   (r_k(e_i, e_j) ∈ v_O)
I(r_k(e_i, e_j)) = φ(f_rk(e_i, e_j))   (r_k(e_i, e_j) ∈ v_H)(3.26)

미관측 트리플이 어떤 논리 규칙에 포함되면, 그 트리플을 규칙 머리로 하는 기저 규칙 집합을 샘플링할 수 있다. PSL에 따라 규칙의 만족까지의 거리는 d(f) = 1 − I(f)이며 I(f)는 우카시에비치 논리로 계산된다. UKGE의 목표는 두 부분으로 구성된다. (1) 관측 트리플의 정답 가중치와 예측된 연성 진리값 사이 MSE 최소화, (2) 미관측 트리플이 규칙 머리인 샘플링된 기저 규칙의 가중 만족 거리 최소화.

Σ_vO | I(r_k(e_i, e_j)) − c_rk(ei,ej) |²  +  Σ_vH Σ_{f ∈ Λ} | w_f d(f) |²(3.27)

3.4.2.2 템플릿 규칙에 대한 정규화 — FSL

위 방법들은 1차 논리 규칙의 기저화로 표현을 정규화한다. 그러나 대규모 KG에서 기저화를 확장하기는 어렵다. 확장성과 일반화 가능성을 개선하기 위해 템플릿 규칙 수준에서 정규화를 추가하는 방법들이 제안되었다. FSL [56]이 가장 대표적이며 Rocktäschel et al. [52]의 확장이다.

임의의 규칙 f : rh(x, y) ← rb(x, y)(예: employeeAt(x, y) ← professorAt(x, y))에 대해, 규칙이 만족되려면 머리의 진리 할당이 몸통보다 크거나 같아야 한다. 즉 임의의 ei, ej에 대해 I(rh(ei, ej)) ≥ I(rb(ei, ej))다. 이는 불 논리의 진리표뿐 아니라 2.2.4절의 세 퍼지 논리에서도 손쉽게 확인된다. 함의 규칙이 참이 되도록 강제하려면 ∀vei,ej : vrb⊤vei,ej ≤ vrh⊤vei,ej가 필요하다. 이 제약은 추천 시스템의 BPR 손실 [57]을 따라 (연성) 손실로 전환된다.

− Σ_{(ei, ∗, ej) ∈ vO} log σ( −[v_rb − v_rh]^⊤ ṽ_ei,ej )    where  ṽ_ei,ej = v_ei,ej / ‖v_ei,ej‖₁(3.28)

그렇다면 모든 엔티티 쌍을 훑지 않도록 엔티티를 어떻게 제거할 수 있는가. FSL은 옌센 부등식을 활용해 위 손실의 상한을 생성한다.

− Σ_vO log σ(−[v_rb − v_rh]^⊤ ṽ_ei,ej)
  ≤ − Σ_vO Σ_d (ṽ_ei,ej)_d log σ(−[v_rb − v_rh]_d)
  ≤ − Σ_d log σ(−[v_rb − v_rh]_d) · Σ_vO (ṽ_ei,ej)_d(3.29)

β를 ΣvO(ṽei,ej)d의 상한(예컨대 |vO|)이라 하면 상한은 −β Σd log σ(−[vrb − vrh]d)로 쓸 수 있으며, 이를 리프티드 손실(lifted loss)이라 부른다. 구체적 트리플을 모두 성공적으로 제거한 형태다. 리프티드 손실을 KG 임베딩 학습의 행렬 분해 모델과 결합하면 전체 손실은 다음과 같다.

− Σ_{rk(ei,ej) ∈ vO, rk(e′i,e′j) ∈ vH} log σ( −v_rk^⊤[v_e′i,e′j − v_ei,ej] )  −  β Σ_{(rb,rh) ∈ F} Σ_d log σ( −[v_rb − v_rh]_d )(3.30)

첫 항은 양성 트리플이 음성보다 높은 점수를 받도록 KG 임베딩을 학습하고, 둘째 항은 함의 규칙 집합 F의 모든 규칙에 대한 리프티드 손실을 나타낸다.

3.4.2.3 미관측 트리플에 대한 정규화 — RUGE

논리 규칙에 대해 손실을 정의하는 방법들과 달리 RUGE [58]는 트리플에 대해 손실 함수를 직접 정의한다. 트리플 모델링에는 ComplEx [24]의 점수 함수를 사용한다.

σ( Re( ⟨e_i, r_k, e̅_j⟩ ) )(3.31)

트리플은 관측(vO)과 은닉(vH)의 두 범주로 나뉜다. 관측 트리플은 하드 레이블 y = 1을 갖고 샘플링된 음성 트리플은 y = 0을 갖는다. 논리 규칙을 주입하기 위해 RUGE는 곱 논리로 샘플링된 규칙 인스턴스 안의 은닉 트리플의 연성 레이블 s ∈ [0, 1]을 예측하며, 샘플링된 규칙의 연성 진리값을 최대화한다. 관측 트리플의 정답 레이블과 은닉 트리플의 연성 레이블을 사용해, 트리플이 자신의 레이블과 일관되도록 강제해 임베딩을 학습한다.

(1/|O|) Σ_vO l( I(r_k(e_i, e_j)), y )  +  (1/|H|) Σ_vH l( I(r_k(e_i, e_j)), s )
where   l(x, y) = −y log x − (1 − y) log(1 − x)(3.32)

KG 완성은 지식 그래프의 누락되거나 불완전한 정보를 예측하는 태스크를 지칭한다. 심볼릭 방법과 신경 방법이 이에 사용되는 두 광범위한 접근 범주다.

심볼릭 방법은 논리적 추론과 규칙 기반 접근에 의존해 기존 사실을 근거로 새로운 사실을 추론한다. 주된 장점은 인간 전문가가 손쉽게 해석하고 검증할 수 있다는 점이다. 그러나 확장성이 제한되고, 논리 규칙이 모든 가능한 경우를 다루지 못할 수 있으므로 데이터의 복잡한 패턴을 포착하기 어렵다.

반면 신경 방법은 신경망으로 KG의 엔티티·관계 표현을 학습하고 이를 사용해 누락 링크를 예측한다. 데이터의 복잡하고 비선형적인 패턴을 학습할 수 있다는 장점이 있으나, 해석과 검증이 어렵고 많은 데이터와 계산 자원을 요구할 수 있다.

뉴로-심볼릭 방법은 논리적 추론과 표현 학습을 통합해 양쪽의 강점을 결합하는 것을 목표로 한다. 통상 신경망으로 엔티티·관계 표현을 학습하고 논리 규칙 또는 제약으로 학습 과정을 유도한다. 이를 통해 심볼릭 방법의 해석 가능성을 활용하면서 신경 방법의 학습 능력에서도 이득을 얻는다.

그러나 뉴로-심볼릭 방법은 여전히 초기 연구 영역이며 KG 완성에 대한 효과성도 계속 탐구되고 있다. 예컨대 확률적 프로그래밍 프레임워크로 신경과 심볼릭 방법을 통합하려는 시도가 있었으나 확장성 문제가 효과성을 제한했다. 이 한계를 넘기 위해 심볼릭 추론과 표현 학습을 성공적으로 결합하는 최신 방법으로 UniKER 알고리즘이 도입되었다.

경로 기반 KG 완성

지면 제약상 KG 완성의 주요 접근만 다룰 수 있었다. 이 영역의 또 다른 유망한 방향으로 경로 기반 방법이 있다. 경로 기반 방법은 KG에서 엔티티 사이의 경로를 발견하는 데 집중하고, 특정 경로의 존재 또는 부재로 누락 링크를 예측한다. 이때 찾아지는 추론 경로는 예측에 대한 해석 가능한 근거를 본질적으로 제공한다. 대표 연구는 전통적 경로 순위 알고리즘과 최근의 강화 학습 기반 방법으로 크게 나뉜다.