EL 계열: 작은 논리, 큰 온톨로지

📍 현재 위치: 2부 · 서술 논리 — 5장. 서술 논리는 우리에게 개념과 역할의 완전한 문법과, 정의들의 TBox와 사실들의 ABox 사이의 구분과, 하나의 공리가 정확히 무엇을 뜻하는지를 말해 주는 모델 이론적 의미론(model-theoretic semantics)을 건네주었습니다. 이제 우리는 실수처럼 들리는 일을 합니다: 그 문법 대부분을 내던져 버리는 것입니다 — 그리고 남은 파편이야말로 지구상에서 가장 큰 온톨로지들로 규모를 확장하는 바로 그것임을 발견합니다.

서술 논리는 개념을 정의하기 위한 풍부한 언어를 제공합니다: 부정, 논리합, 전칭 및 존재 제한, 개수 제한입니다. 문제는 그 풍부함에 시간으로 치러야 하는 대가가 있다는 것입니다 — 더 많이 말할 수 있을수록, 기계는 무엇이 따라 나오는지를 결정하기 위해 더 힘겹게 일해야 하며, 어떤 지점을 넘어서면 그 작업은 폭발해 버립니다. EL 계열은 정반대의 내기를 겁니다. 그것은 의도적으로 아주 작은 하위 언어를 유지하고, 그 작은 언어가 방대한 부류의 실제 정의들에 충분하다는 것을 증명하며, 온톨로지가 아무리 커지더라도 추론기가 빠른 채로 남는다는 형태로 그 절제를 현금화합니다. 이 장은 바로 그 내기와, 그것이 왜 이기는지에 관한 것입니다.

쉽게 말하면

세상의 무엇이든 묘사할 수 있지만 오직 세 가지 동작만 쓸 수 있다고 상상해 보십시오: 범주 이름 대기("교수"), "이것이면서 동시에 저것"이라고 말하기("학생을 지도하는 교수"), 그리고 "어떤 종류의 것과 관계 맺음"을 말하기("어떤 학생을 지도함")입니다. "아니다"라고도, "둘 중 하나"라고도, "모두 다"라고도 결코 말할 수 없습니다. 무력하게 느껴집니다 — 의학 사전의 거의 모든 정의("심장마비란 막힌 어떤 동맥에 의해 야기된 조직 괴사이다")가 오직 그 세 가지 동작만을 쓴다는 것을, 그리고 그 위험한 낱말들을 치워 버렸기 때문에 기계가 그런 정의 수백만 개를 하루 오후 만에 서로 견주어 확인할 수 있다는 것을 알아채기 전까지는 말입니다. EL 계열이 바로 그 세 동작짜리 언어를, 정밀하게 다듬어 놓은 것입니다.

이 장에서 다루는 내용

EL이 남겨 두는 것 — 오직 논리곱 $\sqcap$ , 존재 제한 $\exists r.C$ , 그리고 최상위 개념 $\top$ 뿐입니다; 각각에 대한 평이한 해설과, EL이 거부하는 모든 것에 대한 뾰족한 목록입니다.
EL++가 다시 더하는 것 — 바닥 개념 $\bot$ (따라서 분리성), 역할 포함 $r \sqsubseteq s$ 와 역할 사슬 $r \circ s \sqsubseteq t$ , 노미널, 그리고 ABox — 이들 모두가 학계 세계에 나타나며 — EL 대 EL++ 표로 정리됩니다.
빈곤함이 값을 하는 이유 — EL과 EL++에서 포섭은 다항 시간에 결정 가능하지만, 표현력이 풍부한 논리에서는 ExpTime이나 그보다 더 나쁩니다; 우리가 인용하고 직접 실행하는 완성 알고리즘이 바로 그 이유입니다.
분류된 학계 세계 — classify()는 14개의 공리를 16개의 정규형 공리로 정규화하고, 3라운드 만에 고정점까지 포화시키며, 8개의 이름 붙은 포섭 관계와 2개의 충족 불가능한 개념을 읽어 냅니다.
미묘한 상호작용 — 두 개의 역할 공리가 어떻게 Professor ⊑ Researcher를 역할을 통해 다시 도출해 내는지, 그래서 이 작은 언어가 조용히 진짜 추론을 수행하고 있음을 보여 줍니다.
실전에서의 보상 — 각각 수십만 개의 개념을 지닌 SNOMED CT와 Gene Ontology가 실제로 EL 추론기에 의해 분류됩니다.

EL이 남겨 두는 세 가지 동작 — 그리고 그것이 내던지는 모든 것

서술 논리(description logic)는 개념 이름(Professor 같은), 역할 이름(advises 같은), 그리고 고정된 구성자(constructor) 집합으로부터 복합 개념을 만들어 냅니다. EL — 존재 제한(E $\mathcal{E}$ xistential restriction)의 E와, 논리곱과 최상위를 공급하는 경량(lightweight) 기반 언어의 L — 은 정확히 세 개의 구성자만을 남겨 둡니다 [1]. 개념 이름을 $A$ 로, 역할을 $r$ 로, 임의의 개념을 $C, D$ 로 쓰면, 그 전체 문법은 한 줄입니다:

C, D \;::=\; \top \;\mid\; A \;\mid\; C \sqcap D \;\mid\; \exists r.C

::=는 "다음과 같이 구성된다"로 읽고, 세로 막대는 대안들을 구분합니다. 하나씩 풀어 보면: $\top$ (최상위(top), "모든 것"으로 읽습니다)은 모든 개체가 속하는 개념입니다; $A$ 는 순수한 개념 이름(concept name)입니다; $C \sqcap D$ (논리곱(conjunction), $\sqcap$ 는 "그리고"로 읽습니다)는 $C$ 이면서 동시에 $D$ 인 것들입니다; 그리고 $\exists r.C$ (존재 제한(existential restriction), "어떤 $C$ 와 $r$ 로 관계 맺음"으로 읽습니다)는 $C$ 안에 놓인 $r$ -후속자를 적어도 하나 가진 것들입니다. 그것이 전체 도구 상자입니다. 학계 세계의 ontology.py는 오직 두 개의 보조 구성자 And와 Some만으로 개념을 만드는데, 이는 정확히 $\sqcap$ 와 $\exists$ 에 대응합니다(ontology.py 53-61번째 줄).

이제 뾰족한 부분입니다 — EL이 여러분에게 결코 쓰지 못하게 하는 것들입니다:

부정(negation) 없음 ¬ $C$ . "교수가 아니다"라고 말할 수 없습니다.
논리합(disjunction) 없음 $C \sqcup D$ . "교수 또는 학생"이라고 말할 수 없습니다.
전칭 제한(universal restriction) 없음 $\forall r.C$ . "오직 학생만을 지도한다"라고 말할 수 없습니다.

이들 하나하나는 $\mathcal{ALC}$ 같은 더 표현력이 풍부한 논리라면 자유롭게 제공하는 구성자이며, 다음 절에서 보여 주듯 각각은 추론을 조합적으로 더 어렵게 만드는 구성자이기도 합니다. EL의 논제는 그것들의 부재가 특성(feature)이라는 것입니다: 언어를 세 가지 단조적이고 긍정적인 동작만으로 벗겨 내면 결정 문제는 저렴한 채로 남습니다.

EL++가 다시 더하는 것

순수한 EL은 거의 너무 가난합니다 — 두 클래스가 양립할 수 없다는 것조차 진술할 수 없습니다. EL++("EL 플러스 플러스"라고 읽습니다)는 다항 시간을 벗어나지 않은 채로 진정으로 유용한 구성자들을 더하는 확장입니다 [1]. 결정적으로, 그것은 부정이나 논리합을 다시 더하지 않습니다; 대신 추론이 다루기 쉬운(tractable) 채로 남는, 신중하게 골라낸 몇 가지만을 더하며, 그 하나하나가 학계 세계에 나타납니다. 다음이 전체 비교입니다.

구성자	구문	읽는 법	EL 포함	EL++ 포함	학계 세계 속 어디에
최상위(Top)	$\top$	모든 것 (owl:Thing)	예	예	모든 $S(A)$ 에 암묵적으로 존재
개념 이름(Concept name)	$A$	원자적 클래스	예	예	Person, Professor, Student, Dean, …
논리곱(Conjunction)	$C \sqcap D$	$C$ 이면서 동시에 $D$	예	예	Professor ⊓ Student; Person ⊓ ∃authored.Paper
존재 제한(Existential)	$\exists r.C$	어떤 $C$ 와 $r$ 로 관계 맺음	예	예	∃advises.Student; ∃advises.Professor
바닥(Bottom)	$\bot$	빈 클래스 (owl:Nothing)	아니오	예	Professor ⊓ Student ⊑ ⊥ (분리성)
역할 포함(Role inclusion)	$r \sqsubseteq s$	모든 $r$ -엣지는 $s$ -엣지이기도 함	아니오	예	`RoleSub`를 통해 지원됨(아래의 사슬이 실제로 쓰이는 공리)
역할 사슬(Role chain)	$r \circ s \sqsubseteq t$	$r$ 다음에 $s$ 가 이어지면 $t$ 가 성립함	아니오	예	advises ∘ advises ⊑ grandAdvisor
노미널(Nominal)	$\{a\}$	정확히 개체 $a$ 하나로 이루어진 클래스	아니오	예	단칭 개념(singleton concept)으로서의 ABox 개체들
ABox	$A(a)$ , $r(a,b)$	개체에 관한 단언	아니오	예	개념 단언 13개 + 역할 단언 18개

가장 중대한 파급력을 가진 추가는 $\bot$ (바닥(bottom), "아무것도 아님"으로 읽습니다)입니다 — 어떤 개체도 속할 수 없는 개념입니다. 이것이 바로 EL++가 분리성(disjointness)을 표현할 수 있게 해 주는 것입니다: 교수와 학생이 결코 겹치지 않는다고 말하려면, 그들의 논리곱이 공집합이라고 단언하면 됩니다,

\text{Professor} \sqcap \text{Student} \sqsubseteq \bot,

이는 ontology.py가 Sub(And("Professor", "Student"), BOT)로 적어 두는 것입니다(ontology.py 142-143번째 줄). 이름 붙은 임의의 $A$ 에 대해 $A \sqsubseteq \bot$ 을 도출하는 것이야말로, 추론기가 $A$ 가 충족 불가능(unsatisfiable)하다고 — 여러분이 실수로 아무것도 그 인스턴스가 될 수 없는 클래스를 정의해 버렸다고 — 보고하는 정확한 방식입니다. 학계 세계는 그런 함정을 일부러 두 개 심어 두어서(교수이면서 동시에 학생으로 선언된 TenuredStudent, 그리고 그런 학생을 지도하는 TenuredStudentAdvisor) 바닥 규칙이 제 몫을 톡톡히 해내도록 만듭니다.

EL++는 또한 역할 포함(role inclusion) $r \sqsubseteq s$ 과 역할 사슬(role chain) $r \circ s \sqsubseteq t$ ( $\circ$ 는 "다음에," 혹은 "합성한"으로 읽습니다)를 더하는데, 이는 학계 세계의 대표 공리 advises ∘ advises ⊑ grandAdvisor — 누군가의 지도교수를 지도하면 그의 지도교수의 지도교수(grand-advisor)가 된다 — 뒤에 있는 장치입니다. 끝으로 그것은 노미널(nominal)(한 개체를 이름 붙이는 단칭 개념 $\{a\}$ )을 받아들이고, 그것과 함께 단언들의 전체 ABox를 받아들여서, 순수한 스키마 언어를 이름 붙은 데이터에 대해 추론할 수 있는 언어로 바꾸어 놓습니다. 이 모든 것을 합쳐, ontology.py의 열 개의 이름 붙은 개념과 여섯 개의 역할, 그리고 열네 개의 TBox 공리는 정확히 EL++ 안에 자리 잡으며, 그 summary()는 그 모양을 정확히 출력합니다:

10 named concepts, 6 roles, 14 TBox axioms; ABox: 13 concept assertions, 18 role assertions over 13 individuals.

EL은 세 개의 구성자만을 남겨 두며; EL++는 네 개를 더 더합니다 — 바닥, 역할 포함, 역할 사슬, 그리고 ABox와 함께하는 노미널입니다 — 그리고 그 절제에 대한 대가로 다항 시간 분류를 얻어 내는데, 이는 열 개의 개념을 지닌 학계 세계에서 SNOMED CT와 Gene Ontology의 수십만 개 클래스에 이르기까지 규모를 확장합니다. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

절제가 값을 하는 이유: 다항 시간

논리학자가 자발적으로 부정과 논리합을 포기할 만한 이유가 여기 있습니다. 핵심 추론 과제는 포섭(subsumption)입니다: TBox가 주어졌을 때, 한 개념이 다른 개념 안에 필연적으로 포함되는지를 결정하는 것이며, $C \sqsubseteq D$ ("모든 $C$ 는 $D$ 이다")로 씁니다. EL 계열에서 이 결정은 PTIME(다항 시간)입니다 — TBox 크기에 대한 다항식으로 시간이 한정되어 풀립니다 — 반면 EL이 남겨 둔 구성자들을 더하는 순간, 비용은 가파르게 치솟습니다 [1]:

\text{subsumption in } \mathcal{EL}^{++} \in \mathrm{PTIME}, \qquad \text{in } \mathcal{ALC} \in \mathrm{ExpTime}, \qquad \text{in } \mathcal{SROIQ}\ (\text{OWL 2 DL}) \in \mathrm{N2ExpTime}.

PTIME에서 ExpTime(지수 시간)으로의 도약은 사소한 조정 사항이 아닙니다; 그것은 몇 초 만에 분류되는 온톨로지와, 여러분의 인내심이 바닥나기 전에는 전혀 분류되지 않을지도 모르는 온톨로지 사이의 차이입니다. EL에게 그 다항식 한계를 사 주는 것이 바로 완성(completion)(또는 포화(saturation)) 알고리즘입니다 [2]: 표현력이 풍부한 DL의 테이블로(tableau)가 하듯이 반례 모델(counter-model)을 탐색하는 대신, 그것은 진술된 공리들로부터 시작하여 작고 고정된 도출 규칙 집합을 반복해서 발동시켜서, 한 라운드가 아무것도 더하지 못할 때까지 함의된 포섭 사실들을 추가해 나갑니다 — 1권의 전방 연쇄 $T_P$ 와 똑같은 모양을 한 단조 연산자(monotone operator)의 고정점(fixpoint)입니다. 먼저 모든 개념 포함(concept-inclusion) 공리가 정확히 네 개의 정규형(normal form) 중 하나로 다시 쓰이는데, 잎에는 기본 개념 $A, A_1, A_2, B$ (이름, $\top$ , 또는 $\bot$ )만이 놓입니다; 두 종류의 역할 공리 — 역할 포함 $r \sqsubseteq s$ 와 역할 사슬 $r \circ s \sqsubseteq t$ — 는 있는 그대로 남겨집니다(이것이 바로 아래의 형태별 분류가 여전히 chain 항목을 담고 있는 이유이며, 역할 사슬 규칙 CRχ가 그것을 곧바로 처리합니다):

정규형	모양	읽는 법
NF1	$A \sqsubseteq B$	하나의 이름이 다른 이름 아래에 있다
NF2	$A_1 \sqcap A_2 \sqsubseteq B$	논리곱이 하나의 이름 아래에 있다
NF3	$A \sqsubseteq \exists r.B$	하나의 이름이 어떤 종류의 $r$ -후속자를 가진다
NF4	$\exists r.B \sqsubseteq A$	그런 후속자를 가지는 것은 그 이름 아래에 놓이게 한다

그런 다음 추론기는 두 개의 표를 유지합니다 — $A$ 를 포섭한다고 알려진 이름들의 표인 $S(A)$ , 그리고 $A$ 가 $\exists r.B$ 를 만족한다고 알려진 쌍 $(A, B)$ 의 표인 $R(r)$ 입니다 — 그리고 여섯 개의 완성 규칙으로 이들을 포화시킵니다(el_completion.py 23-30번째 줄). 이 규칙들이 엔진의 전부이므로, 한 번은 읽어 볼 가치가 있습니다:

규칙	전제조건	추가	목적
CR1	$A' \in S(A)$ , $A' \sqsubseteq B$	$S(A)$ 에 $B$	이름 포함을 따라간다
CR2	$A_1, A_2 \in S(A)$ , $A_1 \sqcap A_2 \sqsubseteq B$	$S(A)$ 에 $B$	논리곱 공리를 발동시킨다
CR3	$A' \in S(A)$ , $A' \sqsubseteq \exists r.B$	$R(r)$ 에 $(A, B)$	역할 엣지를 만든다
CR4	$(A, B) \in R(r)$ , $B' \in S(B)$ , $\exists r.B' \sqsubseteq C$	$S(A)$ 에 $C$	후속자 공리를 발동시킨다
CR⊥	$(A, B) \in R(r)$ , $\bot \in S(B)$	$S(A)$ 에 $\bot$	충족 불가능성을 전파한다
CRχ	$(A, B) \in R(r)$ , $(B, C) \in R(s)$ , $r \circ s \sqsubseteq t$	$R(t)$ 에 $(A, C)$	역할 사슬을 발동시킨다

각 규칙은 오직 $S$ 와 $R$ 에 추가만 할 뿐이고, 둘 다 개념 이름 개수의 제곱으로 유계이므로, 이 루프는 단조적이며 다항식 개수만큼의 추가 이후에는 반드시 멈춥니다 — 다루기 쉬움(tractability) 보장이 구체적인 형태로 실현된 것입니다.

학계 세계 분류하기

공개 진입점은 세 가지 움직임 — 정규화하고, 완성하고, 분류하는 것 — 을 하나의 호출로 묶어 냅니다. 전문을 인용할 가치가 있습니다(el_completion.py 302-319번째 줄):

def classify(tbox=None, trace=False):
    """Normalize, complete, and return everything a classification report needs:
    a dict with the normalized axioms, fresh names, saturated S and R, the
    saturation ``rounds``, the ``subsumptions`` and the ``unsatisfiable`` set."""
    if tbox is None:
        tbox = onto.TBOX
    normalized, fresh = normalize(tbox)
    S, R, rounds = complete(normalized, trace=True)
    result = {
        "normalized": normalized,
        "fresh": fresh,
        "S": S,
        "R": R,
        "rounds": rounds,
        "subsumptions": subsumptions(S, only=set(onto.CONCEPTS)),
        "unsatisfiable": unsatisfiable(S),
    }
    return result if not trace else result

이 모듈을 실행하면 14개의 TBox 공리가 16개의 정규형 공리로 정규화되고(이미 정규형이 아니었던 두 개의 복합 공리를 위해 두 개의 새 이름을 도입합니다), 그런 다음 $S$ 와 $R$ 을 고정점까지 포화시킵니다. 추적 기록은 그 상승이 파도처럼 일어나는 모습을 보여 줍니다 — 도출된 사실 개수 $|S|$ 와 $|R|$ 이 올라가다가 멈추어 서는데, 이는 정확히 최소 고정점의 "한 라운드가 아무것도 바꾸지 못한다"는 멈춤입니다:

normalization: 14 axioms → 16 normal-form axioms, introducing 2 fresh names ['_N1', '_N2']
  by normal form: {'chain': 1, 'nf1': 6, 'nf2': 2, 'nf3': 3, 'nf4': 4}

saturation reached a fixpoint in 3 rounds
  round : |S| |R|  (derived subsumers, derived role pairs)
      0 :  23   0
      1 :  34   7
      2 :  39   7
      3 :  39   7

'chain': 1이라는 개수는 열여섯 개 중 손대지 않고 남아 있는 그 역할 사슬 공리이며, 나머지 열다섯 개의 NF1–NF4 공리(NF1 여섯 개, NF2 두 개, NF3 세 개, NF4 네 개)가 네 가지 정규형이 실제로 담당하는 것입니다. 포화된 $S$ 에서 답을 읽어내면 — $B \in S(A)$ 일 때 정확히 $A \sqsubseteq B$ 입니다 — 학계 세계 전체의 분류가 여덟 줄로 나오며, 여기에 일부러 망가뜨린 두 개의 개념이 충족 불가능하다고 표시되어 더해집니다:

classification: 8 subsumptions between named concepts
  Dean ⊑ Person
  Dean ⊑ Professor
  Dean ⊑ Researcher
  Professor ⊑ Person
  Professor ⊑ Researcher
  Researcher ⊑ Person
  Student ⊑ Person
  Student ⊑ Researcher

unsatisfiable concepts (2): ['TenuredStudent', 'TenuredStudentAdvisor']

여덟 개 모두 TBox와 견주어 눈으로 확인할 수 있습니다. 명시된 위계는 Professor ⊑ Researcher, Student ⊑ Researcher, Researcher ⊑ Person, 그리고 Dean ⊑ Professor를 직접 줍니다; 추론기의 임무는 그것들의 이행적 폐쇄(transitive closure)를 계산하는 것이어서, 어떤 공리도 명시적으로 말하지 않았음에도 Professor ⊑ Person, Student ⊑ Person, Dean ⊑ Researcher, 그리고 Dean ⊑ Person 모두가 떨어져 나옵니다. 두 개의 충족 불가능한 개념은 서로 다른 메커니즘으로 실패합니다. 교수이면서 동시에 학생으로 선언된 TenuredStudent는 CR2 단독으로 분리성 공리에 걸려 넘어집니다: CR1이 Professor와 Student를 $S(\text{TenuredStudent})$ 에 넣고, $\text{Professor} \sqcap \text{Student} \sqsubseteq \bot$ 이 우변이 $\bot$ 인 단 하나의 NF2 공리이므로, CR2가 그 쌍에서 발동하여 $\bot$ 을 $S(\text{TenuredStudent})$ 에 직접 추가합니다 — 어떤 역할 엣지도 관여하지 않습니다. (불가능한) 종신 학생을 지도한다는 것만이 유일한 죄인 TenuredStudentAdvisor는 CR⊥를 필요로 하는 쪽입니다: 바닥 규칙이 충족 불가능한 후속자로부터 그 전임자에게로 advises 엣지를 따라 거꾸로 $\bot$ 을 전파합니다. 두 개의 모델링 버그가, 다항 시간 추론기에 의해 공짜로 붙잡힙니다 — $\bot$ 의 일상적인 보상입니다.

미묘한 상호작용: 역할이 위계를 다시 도출하다

EL을 클래스 트리 위의 그럴듯하게 포장된 이행적 폐쇄 엔진 정도로 치부해 버리기는 쉬울 것입니다. 학계 세계 안의 두 공리는 트리 조회로는 결코 할 수 없는 어떤 일을 EL이 해내는 모습을 보여 줍니다: 포섭 관계를 역할을 통해 다시 도출하는 것입니다. 공리 (4)는 모든 교수가 어떤 학생을 지도한다고 말하고, 공리 (5)는 무엇이든 지도하는 사람은 누구나 연구자라고 말합니다(ontology.py 132-138번째 줄):

    # (4) Every professor advises some student.  Normal form A ⊑ ∃r.B.
    Sub("Professor", Some("advises", "Student")),

    # (5) Anyone who advises anything at all is a researcher.  Normal form ∃r.⊤ ⊑ A.
    # Together with (4) this *re-derives* Professor ⊑ Researcher through the roles,
    # a nice internal cross-check of the completion rules CR3 + CR4.
    Sub(Some("advises", TOP), "Researcher"),

두 공리 중 어느 것도 서로의 개념을 언급하지 않지만, 둘이 함께 Professor ⊑ Researcher를 함의합니다 — 이는 명시적 위계 역시 진술하는 사실이며, 완전히 독립적인 경로로 도달한 것입니다. 그것을 해내는 두 규칙을 추적해 봅시다(el_completion.py 227-238번째 줄):

        # CR3: A' ∈ S(A), A' ⊑ ∃r.B  ⟹  (A, B) ∈ R(r)
        for _, a_prime, r, b in nf3:
            for A in names:
                if a_prime in S[A]:
                    if add_r(r, (A, b)):
                        changed = True

        # CR4: (A, B) ∈ R(r), B' ∈ S(B), ∃r.B' ⊑ C  ⟹  C ∈ S(A)
        for _, r, b_prime, c in nf4:
            for (A, B) in list(R.get(r, ())):
                if b_prime in S[B] and c not in S[A]:
                    S[A].add(c); changed = True

CR3는 공리 (4)를 읽어 역할 엣지 $(\text{Professor}, \text{Student})$ 를 $R(\text{advises})$ 에 추가합니다. 그런 다음 CR4는 공리 (5) — 정규형으로는 $\exists\text{advises}.\top \sqsubseteq \text{Researcher}$ — 를 읽고, $\top \in S(\text{Student})$ 가 언제나 성립하므로, 바로 그 엣지 위에서 발동하여 Researcher를 $S(\text{Professor})$ 에 추가합니다. 따라서 포섭 관계 Professor ⊑ Researcher는 이중으로 함의되는데, 한 번은 위계에 의해서, 또 한 번은 역할에 의해서이며, 완성 알고리즘은 둘 다 찾아냅니다. 이것이 바로 이 실행이 그 역할 사슬 출력 grandAdvisor: [('Dean', 'Student'), …]과 나란히 도출된 advises 엣지 $(\text{Professor}, \text{Student})$ 도 함께 보고하는 이유입니다: 이 작은 언어는 단지 트리를 걷는 것이 아니라, 조용히 존재 한정을 합성하고, 역할을 사슬로 잇고, 귀결을 전파하고 있는 것입니다. 절제는 표현력을 대가로 치르지만, 추론을 대가로 치르지는 않습니다.

실전에서의 보상: SNOMED CT와 Gene Ontology

학계 세계는 열 개의 개념을 가지고 있습니다; EL을 위한 논변은 바로 그 알고리즘이, 아무것도 바꾸지 않은 채로, 네 자릿수 넘게 더 큰 온톨로지들을 분류한다는 것입니다. 전 세계 보건 시스템에서 쓰이는 임상 용어 체계인 SNOMED CT는 거의 전적으로 논리곱과 존재 제한 — 정확히 EL의 세 동작 — 만으로 약 35만 개의 개념을 정의하는데, 이는 임상 정의("충수염이란 어떤 충수에 위치한 염증이다")가 자연스럽게 존재 제한들의 긍정적 논리곱이지, 결코 논리합이나 부정이 아니기 때문입니다 [1]. 수만 개의 생물학적 과정, 분자 기능, 세포 구성 요소를 기술하는 Gene Ontology도 같은 모양을 하고 있습니다. 둘 다 위의 완성 루프를 정확히 구현하는 전용 EL 추론기 — ELK, CEL, 그리고 다른 것들 — 에 의해 실전에서 분류되며, 둘 다 평범한 상용 하드웨어에서 몇 분 만에 분류됩니다. 그것이 바로 작은 논리를 위한 실전 배치의 논변입니다: 교과서 TBox 위에서는 아름답던 ExpTime 테이블로 추론기가 실제 TBox 위에서는 숨 막힐 수 있는 반면, "빈곤한" EL 추론기는 매번 끝까지 해냅니다, 최악의 경우가 지수가 아니라 다항식이기 때문입니다. 그 절제는 학구적인 겸손이 아닙니다; 그것은 웹 규모의 생물의학 온톨로지를 애초에 추론 가능하게 만든 공학적 결정입니다.

아직 풀리지 않은 부분

EL의 다항식 보장은 실재하지만 가장자리에서는 취약하며, 정직한 미해결 질문은 정확히 언어가 끊어지기 전에 얼마나 멀리 밀어붙일 수 있는가입니다. EL++는 이미 다루기 쉬운(tractable) 최대 확장에 가깝습니다: 겉보기에 무해해 보이는 구성자를 더하는 것조차 이를 무너뜨립니다. 전칭 제한 $\forall r.C$ , 논리합 $C \sqcup D$ , 또는 부정 $\neg C$ 각각은 단독으로 포섭을 PTIME 바깥으로 끌어올리며, 그렇지 않으면 무해할 특성들의 어떤 조합(예를 들어 치역 제한(range restriction)과 노미널의 특정한 상호작용)은 포섭을 다루기 쉬운 것에서 다루기 힘든 것으로, 심지어 결정 불가능한 것으로 바꾸어 버립니다 [3]. 그러므로 그 경계는 깔끔한 벽이 아니라 들쭉날쭉한 해안선입니다: EL++는 바로 그 안쪽에 자리 잡고 있으며, 어떤 추가가 다항식으로 남고, 어떤 추가가 ExpTime으로 뛰어오르며, 어떤 추가가 결정 불가능성으로 떨어지는지를 지도로 그리는 일은 진정으로 복잡하며 완전히 매듭지어지지 않았습니다. 신경-기호(neuro-symbolic) 독자에게 더 깊은 불안은, EL이 금지하는 구성자들 — "아니다," "또는," "오직" — 이 바로 자연스러운 지식이 흔히 필요로 하는 것들이라는 점입니다. 백만 개의 개념 위에서 실행될 만큼 저렴한 논리는 어떤 도메인 전문가가 뜻하는 바를 말하기에는 너무 약할 수 있으며, 어떤 만큼의 추론기 공학도 그 간극을 메우지는 못합니다; 그것은 구현이 아니라 언어의 속성입니다.

왜 중요한가

EL 계열은 이 책에서 신경-기호 프로그램 전체가 계속해서 다시 배우는 교훈의 첫 번째 깔끔한 사례입니다: 여러분은 원칙에 따른 표현력의 손실로 확장성을 사들이며, 그 기예는 그 손실을 의도적으로 선택하는 데 있습니다. EL이 논리합을 표현하지 못하는 것은 우연이 아닙니다; 그것은 거부하는 것인데, 그 거부야말로 그것의 고정점을 다항식으로, 그리고 그 추론을 남김없이 완전하게 유지해 주는 것이기 때문입니다. 이는 지식 그래프 임베딩이 증명하는 대신 근사할 때 치르는 것과 같은 거래이지만, 다만 여기서는 그 손실이 정확하고 미리 알려져 있습니다 — 여러분은 EL이 결론지을 수 없는 것이 정확히 무엇인지 말할 수 있습니다. 이후의 권들이 신경망 학습기를 기호 추론기에 붙일 때, EL은 붙이기에 자연스러운 기호적 절반인데, 그 보장이 저렴하고, 완전하며, 총체적이기 때문입니다: 모든 개념을 분류하고, 언제나 멈추며, 결코 폭발하지 않습니다. 훈련 루프 안에서 추론기를 수천 번 호출해야 하는 하이브리드 시스템은 ExpTime 오라클을 감당할 수 없습니다; EL 오라클이라면 감당할 수 있습니다. 이 작은 논리는 여러분이 참고 견디는 타협이 아닙니다 — 그것은 학습 안에 추론을 들여놓는 일을 애초에 가능하게 만드는 조건입니다.

핵심 용어

EL — 정확히 세 개의 구성자만을 가진 서술 논리: 최상위 $\top$ , 논리곱 $\sqcap$ , 존재 제한 $\exists r.C$ ; 부정도, 논리합도, 전칭 제한도 없습니다.
EL++ — EL의 다루기 쉬운 확장으로, 바닥 $\bot$ (따라서 분리성), 역할 포함 $r \sqsubseteq s$ , 역할 사슬 $r \circ s \sqsubseteq t$ , 노미널 $\{a\}$ , 그리고 ABox를 더합니다 — 모두 학계 세계에 존재합니다.
포섭(Subsumption) — 핵심 결정 $C \sqsubseteq D$ , "모든 $C$ 는 반드시 $D$ 인가"; EL 계열에서는 PTIME이고, 표현력이 풍부한 DL에서는 ExpTime이거나 그보다 더 나쁩니다.
바닥 $\bot$ / 충족 불가능(unsatisfiable) — 빈 개념; $A \sqsubseteq \bot$ 을 도출한다는 것은 $A$ 가 어떤 인스턴스도 가질 수 없다는 뜻이며, 이는 추론기가 자기모순적인 정의를 붙잡아 내는 방식입니다(TenuredStudent, TenuredStudentAdvisor).
완성(Completion) / 포화(saturation) — 개념 포함 공리를 네 가지 정규형으로 읽어 들이고(역할 포함과 역할 사슬은 있는 그대로 유지) 새로운 것이 더 이상 도출되지 않을 때까지 여섯 개의 규칙 CR1–CR4, CR⊥, CRχ를 발동시키는 고정점 알고리즘입니다; 다항식적이며, 여기서 다룬 EL 파편(바닥, 역할 포함, 역할 사슬)에 대해 건전하고 완전합니다 — 노미널과 구체 도메인(concrete domain)까지 갖춘 완전한 EL++는 몇 개의 규칙을 더 필요로 합니다.
정규형(Normal form) — NF1–NF4 중 하나로, 완성 규칙이 매칭하는 제한된 개념 포함 모양입니다; 학계 세계의 14개 공리는 16개로 정규화됩니다(NF1 여섯 개, NF2 두 개, NF3 세 개, NF4 네 개, 그리고 손대지 않은 채로 남은 유일한 역할 사슬 하나).
역할 사슬(Role chain) — 복합 역할 포함 $r \circ s \sqsubseteq t$ ; advises ∘ advises ⊑ grandAdvisor가 학계 세계의 예시이며, 어떤 정규형이 아니라 CRχ에 의해 처리됩니다.
분류(Classification) — 이름 붙은 개념들 사이의 모든 함의된 포섭 관계를 계산하는 것; 학계 세계는 8개를 산출합니다.

이 장이 이끄는 곳

EL은 다루기 쉬운 서술 논리들로 이루어진 전체 공간 안의 한 점이며, 각각은 표현력을 서로 다른 보장과 맞바꿉니다. OWL을 관장하는 표준화 기구는 EL 하나만을 축복한 것이 아닙니다; 그것은 세 개의 경량 하위 언어를 깎아 냈습니다 — 하나는 SNOMED CT 같은 아주 큰 클래스 위계를 위해 조율되었고, 하나는 거대한 데이터셋 위에서의 질의 응답을 위해, 그리고 하나는 규칙 스타일의 추론을 위해서입니다 — 각각은 "저렴하게 유지하라"는 똑같은 압력에 대한 서로 다른 답입니다. 다음 장인 OWL 2 프로파일은 그 세 개의 파편을 나란히 지도로 그려 냅니다: 각각이 무엇을 남기고, 무엇을 내던지며, 각각이 어떤 실제 과제를 빠르게 만들도록 설계되었는지 말입니다. EL은 여러분이 이제 온전히 만난 프로파일입니다; 그 두 형제가 다음입니다.

이 장에서 다루는 내용​

EL이 남겨 두는 세 가지 동작 — 그리고 그것이 내던지는 모든 것​

EL++가 다시 더하는 것​

절제가 값을 하는 이유: 다항 시간​

학계 세계 분류하기​

미묘한 상호작용: 역할이 위계를 다시 도출하다​

실전에서의 보상: SNOMED CT와 Gene Ontology​

아직 풀리지 않은 부분​

왜 중요한가​

핵심 용어​

이 장이 이끄는 곳​