2장은 그래프의 언어와 심볼릭 논리의 언어 두 가지로 지식 그래프를 정의하고, 명제 논리·1차 논리·퍼지 논리의 기본 개념을 정리한 뒤, 논리 규칙과 지식 그래프 사이의 대응 관계를 확립한다. 이 책은 심볼릭 추론 비중이 크므로, 심볼릭 논리 배경이 없는 독자를 위해 간략하지만 일반적인 소개를 제공한다. 이미 익숙한 독자는 2.2절을 건너뛰어도 된다.
“Logic is the foundation of the certainty of all the knowledge we acquire.” — Leonhard Euler
이 절은 그래프의 언어와 심볼릭 논리의 언어 두 가지 모두로 지식 그래프의 정의를 제시한다. 두 언어는 같은 대상을 서술하며, 이후 장에서 표현 학습과 논리 추론을 오갈 때 번역기로 쓰인다.
지식 그래프(KG)는 이종 그래프(heterogeneous graph)다. 노드는 엔티티를 나타내고, 링크는 엔티티 사이의 서로 다른 유형의 관계를 나타낸다. 형식적 정의는 다음과 같다.
지식 그래프는 유향 그래프 G = {E, R, O}이며, 엔티티 집합 E, 관계 집합 R, 사실 집합 O로 구성된다. 하나의 사실은 트리플 (e i, r k, e j) ∈ O로 표현되며, e i ∈ E는 머리(head), e j ∈ E는 꼬리(tail), r k ∈ R는 머리와 꼬리 사이의 관계다.
아래 Fig. 2.1의 KG는 “Bill Gates”, “Microsoft” 등 9개 엔티티, “Founded”, “BornIn” 등 8개 관계, (Bill Gates, Founded, Microsoft) 등 7개 사실을 포함한다.
위 예제에서 흥미로운 추론 태스크는 “Satya Nadella는 어떤 언어를 사용하는가”이며, 질의 (Satya Nadella, SpeakLanguage, ?)로 표기된다. 이 추론 태스크를 KG 완성이라 부르며, 그래프 학습의 링크 예측 태스크에 대응한다.
직관적인 그래프 관점 외에, KG는 심볼릭 논리의 형태로도 해석되고 추론될 수 있다. 심볼릭 논리의 세계에서 엔티티는 상수(constant)로, 관계는 이항 술어(binary predicate)로 간주된다. 술어는 인수 집합을 받아 True 또는 False를 출력하는 함수다 [1]. KG 환경에서 각 술어는 두 개의 인수를 받으므로 r(·,·)로 표기된다.
기저 술어(ground predicate, 원자 또는 원자 논리식)는 모든 인수가 특정 상수로 인스턴스화된 술어다. 예컨대 술어 Founded(·,·)에 상수 “Bill Gates”와 “Microsoft”를 대입하면 기저 술어 Founded(Bill Gates, Microsoft)를 얻는다. 트리플 (ei, rk, ej)는 본질적으로 기저 술어이며, 논리의 언어로는 rk(ei, ej)로 표기된다.
추론 태스크에서 기저 술어는 이진 확률 변수로 간주된다. 트리플 (ei, rk, ej)가 참이면 rk(ei, ej) = 1이고, 그렇지 않으면 0이다. 가능 세계(possible world)는 모든 기저 술어에 진리값 0 또는 1을 할당한다.
관측된 사실 O와 그에 대응하는 기저 술어 vO = {rk(ei, ej) | (ei, rk, ej) ∈ O}가 주어질 때, KG 완성 태스크는 모든 은닉 트리플(미관측 트리플) H = Ω \ O에 대응하는 기저 술어의 진리값을 예측하는 것이다. 여기서 Ω = E × R × E는 가능한 모든 트리플의 집합이다.
심볼릭 논리는 자연어와 대비되는, 추론을 위한 형식 언어를 제공하는 것을 목표로 한다. 명제 논리와 1차 논리가 심볼릭 논리의 두 주요 형식 체계다. 이 절은 3장·4장·5장에서 사용할 기본 개념을 정의하고 비교한다. 심볼릭 논리에 대한 보다 철저한 소개는 [2–4]에서 확인할 수 있다.
일상에서 선언을 위해 널리 사용되는 진술은 True 또는 False 중 하나다. 이러한 진술을 명제(proposition)라 부르며 P, Q 같은 기호로 표기한다. 유명한 예는 “Socrates is a man”이며 이는 True다. 명제 논리는 명제와 명제 사이의 관계를 다루며 0차 논리(zeroth-order logic)라고도 불린다.
더 작은 명제로 분해할 수 없는 명제를 원자 명제(atomic proposition)라 한다. “All men are mortal”, “Socrates is a man”, “Socrates is mortal”이 원자 명제의 예이며 각각 P, Q, R로 표기된다. 각 원자 명제에는 이진 진리값이 할당되며 이를 해석(interpretation)이라 부른다. 예컨대 P가 True이면 I(P) = 1로 쓴다.
원자 명제는 논리 접속사(logical connective)를 통해 더 복잡한 명제를 정의한다. 부정(¬), 논리합(∨), 논리곱(∧), 함의(→)가 이에 해당한다. 논리 접속사는 명제를 인수로 받아 더 복잡한 명제를 출력하는 함수로 볼 수 있다. 복합 명제의 진리값은 각 접속사의 진리표로 결정된다. 예컨대 I(P) = 1이면 I(¬P) = 0이다. 이 연산자들은 서로 독립이 아니며, 임의의 두 개로 나머지 두 개를 정의할 수 있다.
| P | Q | ¬P | P ∧ Q | P ∨ Q | P → Q |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 |
원자 명제 집합과 논리 접속사가 있으면 모든 유효한 논리식을 재귀적으로 정의할 수 있으며, 이를 정형식(well-formed formula)이라 부른다. 논리 접속사가 없는 정형식을 원자 논리식(atomic formula) 또는 원자(atom)라 한다. 명제 논리에서 원자 논리식은 본질적으로 원자 명제다. 논리식은 통상 φ, ψ, χ로 표기한다. 두 정형식 φ, ψ가 주어지면 (1) φ ∧ ψ, (2) φ ∨ ψ, (3) φ → ψ, (4) ¬φ는 모두 정형식이다.
위와 같이 정의된 논리 언어를 기반으로, 명제 논리의 추론 규칙인 전건 긍정(Modus Ponens)을 사용해 기존 명제로부터 새로운 명제를 연역할 수 있다. 전건 긍정은 전제 φ와 φ → ψ가 모두 True이면 결론 ψ도 True라고 진술하며, 이는 진리표로 검증된다. 다른 추론 규칙도 존재하지만 전건 긍정이 가장 단순하고 가장 널리 쓰인다.
명제 논리는 표현력이 제한적이어서 True 또는 False인 단순한 명제적 진술만 다룰 수 있다. 객체 사이의 관계나 객체의 속성 같은 더 복잡한 구조를 표현할 수 없고, 한정(quantification)도 허용하지 않는다. 예컨대 “All men are mortal”은 명제 논리에서 내부 구조를 더 탐색하지 못한 채 원자 명제 P로만 표현된다. 이 한계를 해결하기 위해 1차 논리(FOL, 술어 논리)는 명제 논리를 두 방향으로 확장한다. (1) 객체·함수·술어로 원자 표현을 풍부하게 하고, (2) 논리식에 변수와 한정 기호를 도입한다.
명제 논리에서 원자 논리식이 원자 명제인 것과 달리, FOL의 원자는 훨씬 풍부한 내부 구조를 가진다. FOL의 원자는 객체·함수·술어와 관련된 세 유형의 기호를 포함한다.
n항 함수는 f(t1, …, tn)로 쓴다. 예컨대 함수 FatherOf(Socrates)는 “Socrates의 아버지”로 해석된다. 함수 표현식도 항이다. 함수는 통상 KG에 존재하지 않는다.n항 술어는 P(t1, …, tn)로 쓴다. 술어는 원자다. 예컨대 술어 Men(Socrates)는 원자이며 “Socrates는 사람이다”를 뜻한다. 이는 명제 논리에서는 원자 명제 Q로만 표현될 수 있다. 대부분의 기존 KG는 이항 술어만 고려한다. Founded(Bill Gates, Microsoft)가 이항 술어의 예다. 술어가 객체 상수를 인수로 받으면 기저 술어라 부른다. Men(Socrates)와 Founded(Bill Gates, Microsoft)는 모두 기저 술어다.모든 객체 또는 일부 객체가 어떤 속성을 갖는 상황을 수용하기 위해 FOL은 객체 변수와 한정 기호를 도입한다.
Men(x)는 변수 x를 포함하며 “x는 사람이다”로 해석된다. 원자와 정형식은 Men(x), Founded(x, Microsoft)처럼 변수를 포함할 수 있다.φ가 변수 x를 가진 정형식이면 (∀x)φ와 (∃x)φ도 정형식이다. 예컨대 (∀x)(Men(x) → Mortal(x))로 “All men are mortal”을 표현한다.1차 논리의 정형식은 논리 접속사와 한정 기호를 통해 원자 위에서 재귀적으로 정의된다. 정형식의 예는 다음과 같으며, “Microsoft를 창업하고 Seattle에서 태어난 사람이 존재한다”를 나타낸다.
명제 논리의 모든 추론 규칙은 1차 논리에서도 작동한다. 여기에 두 가지 추론 규칙이 추가된다.
전칭 한정된 진술의 구체적 인스턴스를 추론할 수 있게 한다.
특정 인스턴스에 대한 진술을 인스턴스 부류 전체에 대한 진술로 일반화할 수 있게 한다.
요약하면 명제 논리는 명제의 진리값을 추론하는 단순한 체계이고, 1차 논리는 객체·객체 사이의 관계·객체의 속성을 추론하는 더 표현력 있는 체계다. 표현력이 더 강하므로 KG 추론에는 1차 논리가 더 나은 선택이다.
심볼릭 논리에서 빈번히 사용되는 그 밖의 용어를 정리한다.
l1 := P)은 양의 리터럴, 원자 논리식의 부정(예: l2 := ¬P)은 음의 리터럴이다.c는 리터럴 집합 위에 논리 접속사로 정의된 논리식이다. 논리곱 절은 리터럴의 논리곱(예: c := l1 ∧ l2 ∧ l3)이고, 논리합 절은 리터럴의 논리합(예: c := l1 ∨ l2 ∨ l3)이다.c1 ∧ c2 ∧ c3)이다.c1 ∨ c2 ∨ c3)으로 표현될 수 있다.이 규칙은 논리곱의 부정이 개별 명제 부정의 논리합과 동등하고, 논리합의 부정이 개별 명제 부정의 논리곱과 동등함을 진술한다.
고전적 FOL은 불 논리이므로 각 정형식은 True(1) 또는 False(0)만 취한다. 퍼지 논리는 [0, 1] 범위의 연성 진리값(soft truth value)을 허용해 FOL을 확장한다. 불 논리와 마찬가지로 원자에서 연성 진리값으로의 사상을 해석이라 부르며, 원자 x의 해석은 I(x)로 표기한다. 퍼지 논리는 문헌에서 폭넓게 연구되었으나 계산 방식에 대한 공통 표준은 아직 없다. 논리 AND, OR, NOT을 완화하는 데 널리 쓰이는 함수는 다음과 같다.
AND와 OR를 각각 min과 max로 단순 완화한다.
기본 논리 연산의 완화로 우카시에비치 t-노름을 사용한다.
세 번째 해석은 다음 함수로 기본 논리 연산을 근사한다.
| 완화 방식 | x ∧ y | x ∨ y | ¬x |
|---|---|---|---|
| Gödel | – | – | – |
| Łukasiewicz | – | – | – |
| Product | – | – | – |
퍼지 논리는 심볼릭 논리와 학습을 결합하는 중요한 방향을 제공하며, 3.2.3.2절, 3.4.2절, 4.4절에서 다시 다뤄진다.
논리 규칙은 심볼릭 지식이나 가설을 표현하는 데 빈번히 사용되며, 추론에서 핵심적으로 활용된다. 이 논리 규칙을 미분 가능한 방식으로 활용하는 방법이 뉴로-심볼릭 통합의 성공에 결정적이다. 따라서 논리 규칙을 형식적으로 도입하고 지식 그래프와 연결한다.
논리 규칙은 다음 표준 형식으로 주어진다.
ψ와 φ는 정형식이고, ψ는 규칙 머리(rule head, 결론), φ는 규칙 몸통(rule body, 전제)이라 부른다. 전제가 True일 때마다 결론이 True로 유도될 수 있음을 진술한다.
규칙이 변수를 포함하는지(일반 지식) 상수만 포함하는지(특정 지식)에 따라 (1) 템플릿 규칙과 (2) 기저 규칙으로 나뉜다.
템플릿 규칙 또는 1차 논리 규칙은 변수와 한정 기호를 포함하는 일반적 진술이다. 아래 예는 임의의 값을 취할 수 있는 변수 x 하나만 포함한다. 실무에서는 모호성이 없을 때 전칭 한정 기호를 생략할 수 있다.
기저 규칙은 모든 변수가 구체적 객체로 대체된 템플릿 규칙의 특정 인스턴스다. 템플릿 규칙의 변수 x를 구체적 객체 “Socrates”로 대체하고 전칭 예화(UI)를 적용하면 아래 기저 규칙을 얻는다.
가장 널리 사용되는 논리 규칙은 Horn 규칙에 속하며, 이를 처음 연구한 논리학자 Alfred Horn의 이름을 따랐다. Horn 규칙은 “P1 ∧ P2 ∧ … ∧ Pl이면 Q”의 형태다. (역)함의 형식으로 쓰면 다음과 같으며, P1, …, Pl은 양의 리터럴이다.
Horn 규칙은 양의 리터럴을 최대 하나만 갖는 절(리터럴의 논리합)로도 쓸 수 있으므로 Horn 절이라고도 불린다.
Horn 규칙이 양의 리터럴을 정확히 하나 가지면 확정적(definite) 또는 엄격(strict)이라 한다. 식 (2.4)는 Q가 양의 리터럴이면 확정적이다.
Horn 규칙은 기존 사실로부터 새로운 사실을 유도하기 위해 KG 맥락에서 널리 사용된다. Fig. 2.1에 대해 다음 확정적 Horn 규칙이 성립한다.
여기서 BornIn(x, z), OfficialLanguage(z, y), SpeakLanguage(x, y)는 각각 식 (2.4)의 P1, P2, Q에 대응한다. 이 규칙은 (1) “x가 z에서 태어났다”와 (2) “z가 y를 공용어로 갖는다”라는 두 조건을 만족하는 z가 존재하면, “x가 언어 y를 말할 수 있다”고 결론지을 수 있음을 진술한다. Horn 규칙의 변수는 규칙 전체를 범위로 하여 암묵적으로 전칭 한정된다. 즉 식 (2.5)는 아래 규칙의 단순화다.
사슬형 Horn 규칙은 Horn 규칙의 특수 형태다. 규칙의 모든 원자가 다른 원자와 하나의 변수를 공유하며, 그 변수들이 사슬을 형성할 것을 요구한다 [8]. 일반형은 다음과 같다.
x, z1, z2, …, zn−1, y는 KG의 객체 위를 변역하는 변수이고, rb1, …, rbn, rh는 KG의 이항 술어다. 식 (2.5)의 Horn 규칙은 사슬형이다. 사슬형 Horn 규칙의 몸통은 KG에서 x로 시작해 y로 끝나는 관계 경로(relation path)에 대응한다.
직관적으로 논리 규칙은 사실 사이의 관계에 관한 고수준 지식을 제공한다. 이런 규칙의 도움으로 인간은 관측한 사실을 기반으로 추론할 수 있다. 2.2.1절에서 논의했듯 기본 추론 규칙은 전건 긍정이며, 일반형은 “전제 φ와 φ → ψ가 모두 True이면 ψ도 True”로 표현된다. 예컨대 다음 논리 규칙을 가정한다.
아래 Fig. 2.2에 따르면 전제 hasMother(Eva, Faye)와 hasSon(Faye, Gino)는 모두 True다. 따라서 Eva에게 Gino라는 형제가 있다는 결론을 내릴 수 있다.
규칙이 변수와 한정 기호를 포함하면 추론 과정이 약간 복잡해진다. 이때 전칭 예화(UI)를 적용할 수 있다. 다음 논리식에 UI를 사용하는 방법을 Fig. 2.2의 KG로 설명한다.
변수 x, y, z를 각각 구체적 엔티티 “Eva”, “Gino”, “Faye”로 대체하면 이 일반 규칙은 기저 규칙 식 (2.8)로 이어지며, UI에 따라 이는 True다. 그다음 전건 긍정으로 동일한 추론을 따라가면 hasBrother(Eva, Gino)가 True임을 유도할 수 있다. 이 예에서 UI는 일반적 진술로부터 “Eva”, “Gino”, “Faye”에 관한 특정 진술로 이동할 수 있게 한다. 동일한 방식으로, x, y, z의 다른 인스턴스화를 적용해 같은 FOL 논리식으로 다른 개인들의 관계를 추론할 수 있다.
hasMother 관계가 사슬을 이루고, 여기에 hasGrandma, hasSon, hasUncle 관계가 더해진다. 빨간 점선은 식 (2.8)이 유도하는 hasBrother(Eva, Gino)다. 버튼으로 식 (2.10)의 두 닫힌 경로 CP₁·CP₂와 식 (2.8)의 닫힌 경로를 강조할 수 있다.
원문 도판은 닫힌 경로를 빨간 점선 삼각형으로 표시한다. 이 정리에서는 경로를 이루는 엣지 자체를 강조하는 방식으로 대체했다.
논리 규칙을 포함한 심볼릭 논리의 개념은 KG의 개념과 밀접히 연결된다. FOL의 상수는 KG의 엔티티에 대응한다(예: “Amy”). 술어는 KG의 관계에 대응하며 이항이다(예: hasGrandma(x, y)). 기저 술어는 KG의 트리플에 대응한다(예: hasGrandma(Amy, Cara), 트리플 형식으로는 (Amy, hasGrandma, Cara)).
사슬형 Horn 규칙의 인스턴스는 그래프에서 “닫힌 경로(closed path)”로 손쉽게 식별된다. 규칙 몸통은 KG의 경로에 대응하고, 규칙 머리는 몸통의 시작 엔티티와 끝 엔티티를 연결하는 엣지에 대응한다. Fig. 2.2의 KG에서 다음과 같은 닫힌 경로(규칙 인스턴스)를 관찰할 수 있다.
Table 2.1 심볼릭 논리의 언어와 KG의 언어에서 개념이 표현되는 방식의 비교.
이 책 전체에서 다음 표기를 사용한다.
| 표기 | 의미 |
|---|---|
| x | 볼드체 소문자는 벡터를 나타낸다 |
| xi | 벡터의 i번째 성분 |
| ‖x‖p | p ≥ 1에 대한 벡터의 ℓp 노름 |
| ‖x‖1/2 | ℓ1 노름 또는 ℓ2 노름 중 하나를 의미한다 |
| diag(x) | i번째 대각 성분이 xi인 대각 행렬 |
| |x| | 성분별 절대값 함수 |
| tanh(x) | 성분별 하이퍼볼릭 탄젠트 함수 |
| ReLU(x) | 성분별 정류 선형 유닛 |
| 표기 | 의미 |
|---|---|
| X | 볼드체 대문자는 행렬을 나타낸다 |
| Xij | 행렬의 ij번째 성분 |
| ‖X‖F | 행렬의 프로베니우스 노름 |
| tr(X) | 정방 행렬의 대각합(trace) |
| det(X) | 정방 행렬의 행렬식(determinant) |
KG는 유향 그래프 G = {E, R, O}이며, 동시에 상수·이항 술어·기저 술어로 이루어진 논리 구조다. KG 완성은 H = Ω \ O에 속하는 기저 술어의 진리값을 예측하는 문제로 형식화된다.
명제 논리는 0차 논리로서 표현력이 제한된다. 1차 논리는 객체·함수·술어로 원자를 확장하고 변수·한정 기호를 도입해 KG 추론에 적합한 표현력을 확보한다. 단, 함수는 통상 KG에 존재하지 않고 술어는 대개 이항으로 제한된다.
추론 규칙은 전건 긍정이 기본이며, FOL에서 전칭 예화(UI)와 존재 일반화(EG)가 추가된다. UI는 템플릿 규칙을 기저 규칙으로 내리는 장치다.
퍼지 논리는 진리값을 [0, 1]로 완화해 심볼릭 논리와 학습을 잇는다. 괴델·우카시에비치·곱 논리는 서로 다른 t-노름을 쓰며, 계산 방식에 공통 표준은 없다.
가장 널리 쓰이는 규칙 형태는 확정적 Horn 규칙이고, 그중 사슬형 Horn 규칙의 몸통은 KG의 관계 경로에 정확히 대응한다. 이 대응이 이후 규칙 학습과 질의 임베딩의 출발점이다.
Table 2.1의 대응 — 상수↔엔티티, 술어↔관계, 기저 술어↔트리플, 규칙 인스턴스↔닫힌 경로 — 가 심볼릭 추론과 그래프 연산을 같은 대상 위에서 수행할 수 있게 만든다.