질의 임베딩: 계산 DAG

📍 현재 위치: 5부 · 복합 논리 질의 응답 — 15장. RNNLogic과 기호 기준선 AnyBURL은 규칙 학습의 흐름을 마무리했습니다: 한 번에 빠진 엣지 하나씩 예측하는 기계였습니다. 이 장은 한 번에 온전한 1차 질문 하나를 던짐으로써, 그리고 이 부의 모든 신경망 모델이 채점의 기준으로 삼을 정확한 기호적 계측기를 만듦으로써 5부를 엽니다.

3권은 학계 세계에 한 가지 종류의 질문을 던졌습니다: 쌍 (bob, advises)가 주어졌을 때 어떤 꼬리 개체가 삼중항을 완성하는가? 4부는 이를 답하는 규칙을 학습했습니다. 그러나 사람들이 실제로 지식 그래프에 던지는 질문은 좀처럼 단일 엣지가 아닙니다. "alice의 지도 학생 중 한 명에게 지도받았지만 carol에게는 지도받지 않은 사람은 누구인가?"는 하나의 질문이지만, 세 개의 엣지를 건드리고, 중간 인물에 대해 정량화하며, 부정을 포함합니다. 이를 답하는 일이 복합 논리 질의 응답(complex logical query answering, CLQA)이며, 이 분야 전체는 하나의 표현에 의존합니다: 질의를 집합 연산의 작은 방향 그래프로 다시 써서 잎에서부터 위로 실행하는 것입니다. 이 장은 그 표현, 14가지 질의 형태의 정준 분류, 임의의 엣지 집합 위에서 각 형태를 답하는 정확한 실행기, 그리고 이 장이 토이 규모에서 재현하는 벤치마크(BetaE라는 이름은 아래 커밋된 코드에서 다시 나타나고, 다음 장에서는 모델로도 다시 등장합니다) [1]가 정의하는 평가 프로토콜, 즉 모델이 단순히 찾아볼 수 있는 정답과 실제로 추론해야만 하는 정답을 구분하는 프로토콜을 만듭니다. 모든 것은 실행되고, 모든 수치는 query_dag.py에 커밋되어 있습니다.

쉽게 말하면

탐정이 사건 하나를 맡아 투명한 시트 뭉치를 다루고 있다고 상상해 보십시오. 단서 하나당 시트 한 장입니다. "용의자는 alice의 학생 중 한 명에게 지도받았다": 이 단서는 alice에서 시작해 advises라는 라벨이 붙은 화살표를 두 번 따라가며, 닿는 모든 이름에 색을 칠합니다. "용의자는 carol에게 지도받지 않았다": 이 단서는 모두에게 색을 칠한 다음, carol의 지도 학생들만 지웁니다. 시트를 겹쳐 놓고 모든 시트에서 색칠된 이름만 남기면 그것이 답입니다. 이제 이 문제를 연구 문제로 만드는 반전이 나옵니다: 탐정의 사건 파일에는 빠진 페이지가 있습니다. 세상에 존재하는 어떤 화살표들은 결코 파일에 기록되지 않았습니다. 빠진 화살표를 통해서만 도달할 수 있는 용의자는 아무리 파일을 꼼꼼히 뒤져도 절대 찾을 수 없습니다. 그 용의자를 찾으려면 빠진 화살표를 올바르게 추측해야 합니다. 이 장은 시트(계산 DAG, 곧 집합 연산의 유향 비순환 그래프), 겹쳐 놓기(집합 교집합, 합집합, 여집합), 그리고 무엇보다도 채점 방식을 정식화합니다: 모델은 오직 파일만으로는 결코 도달할 수 없는 용의자에 대해서만 채점됩니다.

이 장에서 다루는 내용

과제의 이름과 경계: 사영, 논리곱, 논리합, 그리고 통제된 형태의 부정으로 지어지는, 자유 변수 하나를 가진 실존 1차 질의; 이 조각이 배제하는 것과 이 분야가 실제로 평가할 수 있는 조각이 왜 바로 이것인가.
계산 DAG: 잎에는 앵커, 내부 노드에는 네 개의 집합 연산자, 위상 순서로 이루어지는 평가; 실제 학계 세계 집합을 매 단계마다 보여 주며 노드 하나하나 짚어 가는 커밋된 질의 하나.
14가지 유형 분류법 해독하기: 1p, 2p, 3p, 2i, 3i, pi, ip, 2u, up, 2in, 3in, inp, pin, pni 뒤에 있는 명명 문법, 커밋된 36개 질의 은행의 집계, 그리고 구성적 일반화를 검사하는 다섯 유형 학습·네 유형 제로샷 관행.
스스로를 검증하는 기호 실행기: 약 30줄로 이루어진 재귀적 집합 평가, 그리고 모든 질의를 드모르간의 법칙으로 다시 써서 동일한 답을 요구함으로써 이루어지는 교차 검증, 36개 중 36개.
쉬움 대 어려움, 프로토콜의 핵심: 학습 그래프를 순회해 도달하는 정답과 홀드아웃된 엣지를 채워 넣어야 하는 정답의 구분; 구조적 귀납으로 증명된 단조성 정리, 커밋된 질의로 목격되는 부정 아래에서의 실패, 그리고 하드 정답에 대해서만 계산되는 필터링된 순위 지표.
왜 응답이 링크 하나 예측하기가 아닌가: 곱으로 유도되는 불완전성의 조합적 증폭, 그리고 두 엣지의 결합 진위에 유일한 정답이 좌우되는 커밋된 교집합 질의로 보여 주는 그 모습.

빠진 엣지 하나에서 1차 질문으로

표기법을 한 번에 고정합시다. 학계 세계는 개체 집합(entity set) $V$ 위의 지식 그래프이며, 이는 1권 지식 베이스의 13개 개체(5명의 사람, 3편의 논문, 2개의 기관, 3개의 주제)와 5개의 관계(advises, affiliated, authored, about, cites)로 이루어집니다. 엣지(edge)는 삼중항 $(h, r, t)$ 입니다: 머리 개체 $h$ , 관계 이름 $r$ , 꼬리 개체 $t$ 이며, " $h$ 는 $t$ 에 대해 관계 $r$ 에 놓인다"라고 읽습니다. 그러한 삼중항들의 집합이 엣지 집합 $E$ 이고, 완전한 학계 세계는 kg.TRIPLES에서 가져온 18개 엣지의 집합이며, 결코 다시 입력되지 않습니다(query_dag.py 70–74행).

이제 서두의 질문을 단계별로 형식화합니다. "alice의 지도 학생 중 한 명에게 지도받았지만 carol에게는 지도받지 않은 사람은 누구인가?"는 자유 변수(free variable) $x$ 하나를 가집니다: 답이 채우는 자리, 곧 우리가 찾고 있는 사람입니다. 그리고 존재 변수(existential variable) $y$ 하나를 가집니다: 이름 없는 중간 지도 학생으로, 이 질문은 그에 대해 오직 어떤 적합한 사람이 존재한다고만 주장합니다(기호 $\exists$ 는 "존재한다"라고 읽습니다). 그리고 세 개의 원자(atom), 곧 $\wedge$ ("그리고")로 연결된 단일 관계 진술들을 가지며, 그중 하나는 $\neg$ ("아니다")로 부정됩니다:

q(x) \;=\; \exists y.\; \underbrace{\text{advises}(\text{alice}, y)}_{\text{원자 1: } y \text{는 alice의 지도 학생이다}} \;\wedge\; \underbrace{\text{advises}(y, x)}_{\text{원자 2: } y \text{가 } x \text{를 지도한다}} \;\wedge\; \underbrace{\neg\,\text{advises}(\text{carol}, x)}_{\text{원자 3: carol은 } x \text{를 지도하지 않는다}}.

엣지 집합 $E$ 위에서 $q$ 의 정답 집합(answer set)은 $\llbracket q \rrbracket_E$ 로 쓰며(이중 대괄호는 "…의 의미"라고 읽습니다), $x$ 자리에 대입했을 때 공식을 참으로 만드는 개체들의 집합이고, $y$ 는 무엇이든 자유롭게 범위를 취할 수 있습니다. 이 질의는 커밋된 은행의 항목 pin[0]이며(query_dag.py 334–337행), 전체 18개 엣지 위에서의 정답은 carol과 dave를 담은 두 원소 집합입니다: alice는 bob을 지도하고, bob은 둘 다를 지도하며, carol은 둘 다 지도하지 않습니다.

이 부가 다루는 조각(fragment)은 정확히 이 재료들로 지어집니다. 실존 긍정 1차(Existential Positive First-Order, EPFO) 질의는 존재 한정, 논리곱, 그리고 논리합 $\vee$ ("또는")를 허용하며 자유 변수는 하나입니다. 이 분야는 아홉 가지 EPFO 형태로 표준화되었고 [2], 이후 교집합의 한쪽 피연산자에 부정을 적용하는 다섯 가지 형태로 확장되었습니다 [1]. 그 밖의 모든 것은 배제되며, 그 배제는 근거를 지탱합니다. 전칭 한정( $\forall$ , "모두에 대하여")은 없습니다: 전칭 한정된 질의는 이름 붙은 시작 개체에서 바깥으로 엣지를 따라가는 방식으로는 답할 수 없는데, 이는 하나의 존재를 요구하는 것이 아니라 모든 이웃을 제약하기 때문입니다. 두 번째 자유 변수도 없습니다: 자유 자리가 두 개면 답은 쌍의 집합이 되고, 아래의 순위 프로토콜은 단일 개체를 순위 매기므로 더 이상 적용되지 않습니다. 더 조용하지만 똑같이 근거를 지탱하는 제약이 하나 더 있습니다: 이 분야는 스스로를 의존 구조가 트리 모양이고 이름 붙은 앵커 개체에 뿌리를 둔 질의로 제한합니다. 위에서 정의한 EPFO는 두 존재 변수가 서로를 순환적으로 제약하는 순환적 논리곱 질의도 허용하지만, 그런 질의는 잎에서부터 위로 전혀 평가할 수 없으며, 질의 자체가 입력의 일부로 간주될 때 그 평가는 NP-난해입니다. 여기서 NP는 비결정적 다항 시간(nondeterministic polynomial time)의 약자로 후보 답을 다항 시간에 검사할 수 있는 문제들의 부류이고, NP-난해는 그 부류의 어떤 문제 못지않게 어렵다는 뜻입니다(고전적인 결과입니다: P = NP, 곧 다항 시간에 풀 수 있는 문제들의 부류 P가 NP와 같다는 거짓으로 널리 추측되는 등식이 성립하지 않는 한, 일반적인 문제에 대해서는 다항 시간 알고리즘이 존재하지 않습니다; 다만 단일하게 고정된 질의 하나는 데이터에 대해서는 여전히 다항 시간에 평가됩니다) [3]. 이 조각의 바깥에 놓인 것은 이 장의 끝에서 다시 다룹니다. 조각 안에서는 전체 방법론이 의존하는 두 성질이 성립합니다. 트리 모양이고 앵커에 뿌리를 둔 조각의 모든 질의는 알려진 엣지 집합에 대한 다항 시간 집합 연산으로 정확히 답할 수 있고(이 절의 실행기), 모든 중간 결과는 개체들의 집합이며, 이는 정확히 임베딩 모델이 벡터 공간의 한 영역으로 표현하고자 바랄 수 있는 종류의 대상입니다(다음 장의 움직임).

계산 DAG: 네 연산자, 잎에서부터 평가

근거를 지탱하는 표현은 공식을 질의 계산 DAG(query computation DAG)로 변환합니다: 잎이 앵커 개체(anchor entity, 질의에 이름 붙은 상수: alice, carol)이고 내부 노드가 집합 연산자인 유향 비순환 그래프이며, 위상 순서로 평가됩니다. 즉 모든 노드는 그것으로 들어오는 모든 노드가 계산된 뒤에야 계산됩니다 [4]. 이 조각 전체를 처리하는 데는 네 개의 연산자로 충분합니다. 각 연산자는 하나 이상의 개체 집합을 소비하여 하나를 생산합니다. 의미론 열에 나오는 기호 두 개는 등장하기 전에 해독해 둘 가치가 있습니다: $\in$ 는 "…의 원소이다"라고 읽고, 중괄호와 세로줄 패턴 $\lbrace t \mid \ldots \rbrace$ 는 "세로줄 뒤의 조건을 만족하는 모든 $t$ 의 집합"이라고 읽습니다(중괄호 안에서, 혹은 $\exists$ 뒤에서 쓰이는 쌍점 $:$ 도 같은 방식으로 "…를 만족하는"이라고 읽습니다). 다음은 정확한 의미론이며, $S$ 는 입력 집합, $r$ 은 관계, $S_1, \dots, S_m$ 은 피연산자 집합입니다(개수 $m$ 은 그 노드로 들어오는 가지의 수입니다):

연산자	평이한 읽기	집합 의미론	코드
앵커 $e$	"개체 $e$ 에서 시작한다"	$\lbrace e \rbrace$	`query_dag.py` 139–141행
사영 $P_r$	" $S$ 의 모든 원소에서 관계 $r$ 을 한 홉 따라간다"	$P_r(S) = \lbrace t \mid \exists h \in S : (h, r, t) \in E \rbrace$	121–124행
교집합	"모든 가지가 찾은 것만 남긴다"	$S_1 \cap \cdots \cap S_m$	152–157행
합집합	"어느 가지든 찾은 것을 모은다"	$S_1 \cup \cdots \cup S_m$	142–144행
부정	" $S$ 를 제외한 모든 것"	$V \setminus S$ (13개 개체 안에서의 여집합)	150행

부정 행 위에 무언가를 쌓기 전에 정직하게 짚어 둘 것이 하나 있습니다. $\neg$ 를 여집합 $V \setminus S$ 로 읽는 것은 닫힌 세계(closed-world) 관행입니다: 엣지 집합에서 도출되지 않는 모든 진술을 거짓으로 취급하는 것이며, 이는 우리 스스로 열거한 13개 개체 위에서는 정당하지만, 기록되지 않은 엣지가 그저 미기록일 뿐인 실제 지식 그래프 위에서는 정당화하기 훨씬 어렵습니다. 이 분야의 벤치마크는 정확히 이 해석을 채택하고 있으며(그것의 분포 기반 부정은 여집합을 근사하고, 우리의 실행기는 그것을 정확히 계산합니다), 그래서 이 토이는 관행을 만들어 내는 것이 아니라 물려받는 것입니다 [1]. 이것은 관행이며, 마지막 절에서 다시 다룹니다.

서두 질의의 DAG는 각 연산자를 자기만의 노드로 세면 일곱 개의 노드를 가집니다. 두 개의 앵커가 잎에 있습니다. alice 위에서는 두 개의 사영으로 이루어진 사슬이 원자 1과 2를 구현합니다: $\lbrace\text{alice}\rbrace$ 에서 advises를 따라가 alice의 지도 학생들을 얻고, 다시 advises를 따라가 그들의 지도 학생들을 얻습니다. carol 위에서는 사영 하나에 여집합이 이어져 원자 3을 구현합니다: carol의 지도 학생들, 그리고 그 나머지 전부입니다. 마지막 교집합 노드가 두 가지를 만나며, 그 출력이 $\llbracket q \rrbracket_E$ 입니다. 존재 변수 $y$ 는 어떤 노드로도 나타나지 않습니다: 그것은 사영에 흡수되는데, 사영은 구성상 중간항에 대해 양화하기 때문입니다(그 의미론은 이미 " $S$ 안에 $h$ 가 존재한다"라고 말하고 있습니다). 그 흡수가 트릭의 전부입니다; 그것이 바로 무한해 보이는 논리적 탐색이 유한한 집합 연산 파이프라인이 되는 이유입니다. (지금 고정해 둘 장부 관행 하나: 커밋된 실행기는 연속된 사영과 여집합의 각 연쇄를 하나의 체인(chain) 노드로 저장하므로, 이 질의에 대한 튜플은 다섯 노드, 즉 앵커 둘, 체인 둘, 교집합 하나입니다. 아래의 출력된 트리들도 체인을 같은 방식으로 그립니다.)

하나의 커밋된 질의를 계산 DAG로, 매 노드마다 실제 집합으로 잎에서부터 위로 평가하는 모습과, 그 정답 중 어느 것이 어려운지를 정의하는 두 그래프 프로토콜을 나란히 보여 줍니다. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

이러한 DAG를 평가하는 실행기는 31줄의 재귀적 파이썬 코드(그리고 작은 도우미 함수 _project와 _is_chain 둘)이며, 다음 네 개 장이 그 각 가지를 신경망 대응물로 교체하기 때문에 전체를 읽어 볼 가치가 있습니다(query_dag.py 127–157행):

def eval_query(q, edges: frozenset[tuple[str, str, str]]) -> frozenset[str]:
    """The exact answer set ⟦q⟧ of a query DAG over ``edges``.

    Node grammar (nested tuples, BetaE's data convention):
      * anchor          — an entity name (a plain string);
      * projection      — ``(sub, (t1, ..., tk))``: evaluate ``sub``, then
                          apply each token left to right, where a relation
                          name r maps S ↦ P_r(S) and the marker N maps
                          S ↦ V − S (closed-world complement);
      * union           — ``(q1, ..., qm, U)``: ⟦q1⟧ ∪ ... ∪ ⟦qm⟧;
      * intersection    — any other tuple ``(q1, ..., qm)``: ⟦q1⟧ ∩ ... ∩ ⟦qm⟧.
    """
    # Anchor: ⟦e⟧ = {e}.
    if isinstance(q, str):
        return frozenset({q})
    # Union node: ⟦(q1,...,qm,U)⟧ = ∪_i ⟦qi⟧.
    if q[-1] == U:
        return frozenset().union(*(eval_query(sub, edges) for sub in q[:-1]))
    # Projection node: fold the chain over ⟦sub⟧.
    if _is_chain(q):
        S = eval_query(q[0], edges)
        for tok in q[1]:
            # N: S ↦ V − S (complement).  r: S ↦ P_r(S) (projection).
            S = (V - S) if tok == N else _project(S, tok, edges)
        return S
    # Intersection node: ⟦(q1,...,qm)⟧ = ∩_i ⟦qi⟧.
    sets = [eval_query(sub, edges) for sub in q]
    out = sets[0]
    for s in sets[1:]:
        out &= s
    return out

전체 그래프 위에서 실행한, 여섯 연산자 DAG(실행기의 체인 형태로는 다섯 노드)의 커밋된 순회를 봅시다. 부정 계열의 예시로 실행기의 실제 집합이 끝에 출력됩니다(커밋된 데모는 질의 계열마다 이런 순회를 하나씩 출력하며, 이것은 실행의 [2] 블록입니다):

  negation (2in):  q(x) = advises(bob,x) ∧ ¬advises(carol,x)
    intersect ∩
    ├─ chain: project advises
    │  └─ anchor bob
    └─ chain: project advises ▸ ¬ complement
       └─ anchor carol
    EASY = ['carol']   ALL = ['carol', 'dave']   HARD = ['dave']

18개 엣지 그래프 위에서 노드 하나하나를 짚어 봅시다. 앵커 bob은 bob 하나만 담은 집합으로 평가됩니다. advises를 따라 사영하면 머리가 bob인 advises 엣지의 모든 꼬리가 모입니다: carol과 dave입니다. 다른 가지에서는 앵커 carol이 사영되어 erin을 담은 집합이 되고(carol은 erin만 지도하고 그 밖에는 아무도 지도하지 않습니다), 여집합은 그것을 나머지 12개 개체, 곧 erin을 제외한 모두로 바꿉니다. 교집합은 두 가지가 동의하는 것만 남깁니다: carol과 dave인데, 둘 다 erin이 아니기 때문입니다. 모든 노드의 모든 집합은 작고 명시적이며 눈으로 확인할 수 있습니다; 마지막 줄의 EASY, ALL, HARD 라벨은 이 장이 세우고 있는 프로토콜이며, 아래에서 독립된 절로 다룹니다.

14가지 형태, 하나의 명명 문법

이 분야는 임의의 공식 위에서 평가하지 않습니다. 14가지 정준 DAG 형태 위에서 평가하며, 그 이름들은 나중의 모든 표가 스스로 읽히도록 한 번 풀어 볼 가치가 있는 간결한 문법을 따릅니다. 앞자리 숫자는 뒤따르는 연산의 반복 횟수를 셉니다: p에서는 홉의 수, i와 u에서는 가지의 수입니다. 글자 p는 사영 한 홉입니다; i는 교집합입니다; u는 합집합입니다; n은 교집합의 한쪽 피연산자에 붙은 부정을 표시합니다. 글자는 합성 순서대로 읽습니다. 그래서 2p는 사슬로 이어진 두 개의 사영 홉이고; 3i는 세 개의 한 홉짜리 가지를 교집합하며; pi는 두 홉짜리 사영과 한 홉짜리 가지를 교집합에 먹이고; ip는 그 순서를 뒤집어 먼저 교집합한 다음 그 결과에서 사영하며; up은 합집합에서 한 홉을 사영하고; pni는 부정된 피연산자가 두 홉짜리 사슬인 교집합입니다(부정이 한 홉짜리 피연산자에 붙는 pin과 대조됩니다). 커밋된 은행은 각 형태를 학계 세계 위에서 두세 번씩 예시화하여 총 36개 질의를 이룹니다(query_dag.py 221–351행), 그리고 실행은 각 유형의 구조를 벤치마크 자체의 템플릿 표기법으로 집계하여 출력합니다. 여기서 e는 앵커, r은 관계, n은 부정 표지, u는 합집합 표지입니다:

[1] the 14 canonical query types (taxonomy of the bank)
  type  structure                          #q  #easy  #hard
  1p    (e,(r,))                            3      2      2
  2p    (e,(r,r))                           3      2      2
  3p    (e,(r,r,r))                         3      2      2
  2i    ((e,(r,)),(e,(r,)))                 3      1      2
  3i    ((e,(r,)),(e,(r,)),(e,(r,)))        2      0      2
  pi    ((e,(r,r)),(e,(r,)))                3      2      2
  ip    (((e,(r,)),(e,(r,))),(r,))          2      1      1
  2u    ((e,(r,)),(e,(r,)),(u,))            3      5      2
  up    (((e,(r,)),(e,(r,)),(u,)),(r,))     3      4      2
  2in   ((e,(r,)),(e,(r,n)))                3      2      2
  3in   ((e,(r,)),(e,(r,)),(e,(r,n)))       2      1      1
  inp   (((e,(r,)),(e,(r,n))),(r,))         2      2      1
  pin   ((e,(r,r)),(e,(r,n)))               2      2      1
  pni   ((e,(r,r,n)),(e,(r,)))              2      2      1
  all                                      36     28     23
  every one of the 14 types has ≥1 query with a nonempty HARD set (14/14)

1p 행은 정확히 3권입니다: 앵커 하나, 홉 하나, 빠진 꼬리 하나입니다. 그 아래는 모두 이 부가 연구하는 성장입니다. 또한 이 집계표가 무엇을 위한 것인지도 눈여겨보십시오: #easy와 #hard 열은 프로토콜의 장부 정리이고, 마지막 줄은 은행이 설계된 성질입니다. 하드 정답이 없는 유형이 있었다면 모든 지표에서 소리 없이 사라졌을 것이기 때문입니다.

이 분류법 위에 하나의 관행이 얹혀 있으며, 이는 이 부 전체를 위해 여기서 한 번 진술하는 프로토콜의 가장 날카로운 발상입니다. 모델은 1p, 2p, 3p, 2i, 3i 유형(부정을 지원하는 모델의 경우 부정 유형까지 [1])의 질의로 학습되고, 그런 다음 단 하나의 사례도 본 적 없는 ip, pi, 2u, up 유형에 대해 평가됩니다 [2]. 이것은 데이터 분할이 아니라 구조 분할입니다. 사슬과 교집합만 학습하고도 up 질의에 답하는 모델은 질의 템플릿을 암기한 것이 아니라 사영, 교집합, 합집합을 합성 가능한 연산자로 학습했음이 틀림없습니다: 구성상 그렇게 검사되는 제로샷 구성적 일반화입니다. 다음 장들이 유형별 수치를 보고할 때, 지켜봐야 할 것은 바로 이 홀드아웃된 열들입니다.

실행기는 스스로를 검증한다: 교차 검증으로서의 드모르간

그 자체가 버그를 품고 있을지 모르는 정답 계측기는 아무 쓸모가 없습니다. 그래서 커밋된 모듈은 불 대수의 항등식으로 자신의 실행기를 교차 심문합니다. 드모르간의 법칙(De Morgan's law)은 교집합을 단 한 번도 직접 교집합하지 않고 계산할 수 있다고 말합니다:

S_1 \cap S_2 \cap \cdots \cap S_m \;=\; V \setminus \big( (V \setminus S_1) \cup (V \setminus S_2) \cup \cdots \cup (V \setminus S_m) \big).

증명은 네 개의 기초적인 단계입니다. 개체 $x$ 가 좌변에 속하는 것은 정확히 $x$ 가 모든 $S_i$ 에 속할 때입니다. 이는 정확히 $x \in V \setminus S_i$ 인 지표 $i$ 가 존재하지 않을 때 성립하고, 이는 정확히 $x$ 가 여집합들의 합집합 바깥에 놓일 때 성립하며, 이것이 바로 우변의 소속 조건입니다. 각 단계는 정의를 풀어 쓰는 것일 뿐이며, 그 밖의 것은 아무것도 사용되지 않습니다.

교차 검증(query_dag.py 170–195행 및 531–551행)은 은행 안의 모든 질의의 모든 교집합 노드를 여집합의 합집합의 여집합 형태로 다시 쓰고, 동일한 실행기를 다시 쓴 DAG 위에서 실행하며, 두 그래프 모두에서 두 정답 집합이 동일함을 단언합니다. 거울상의 재작성은 모든 합집합 노드를 같은 방식으로 해체하는데, 이는 정확히 벤치마크 자체가 자신의 합집합 유형을 위해 갖고 있는 대안 평가 모드입니다 [1]. 이 재작성은 모든 교집합 가지를 합집합·여집합 가지로 교체하므로, 두 경로는 서로 다른 연산자 코드를 거쳐 같은 집합을 계산하며, 둘이 일치한다는 것은 어느 쪽에도 버그가 없다는 증거입니다. 커밋된 실행 결과입니다:

[4] De Morgan cross-check — two independent evaluation routes
  ∩ as ¬(∪¬)  : 36/36 queries agree on G_train and G_full (21 rewrites non-identity, incl. all 11 negation queries)
  ∪ as ¬(∩¬)  : 36/36 agree (6 union queries — BetaE's --evaluate_union DM mode)

괄호 안의 개수는 공허한 통과를 막는 안전장치입니다: 36개 재작성 중 21개가 실제로 DAG를 바꾸었고(순수 사영 사슬 아홉 개와 합집합뿐인 2u/up 질의 여섯 개는 다시 쓸 교집합 노드가 없으므로, $36 - 9 - 6 = 21$ 입니다), 11개 부정 질의 전부가 그중에 포함되어 있으므로, 이 일치는 거저 얻어진 것이 아니라 값을 치른 것입니다. 이 모듈은 두 개수 모두를 단언합니다(query_dag.py 551행).

쉬움 대 어려움: 프로토콜의 핵심

이제 두 그래프입니다. 순위 프로토콜을 다룬 3권의 장은 18개 엣지의 결정적 분할을 고정했습니다: 15개의 학습 엣지( $G_{\text{train}}$ , kg.TRAIN에서 옴)와 3개의 홀드아웃된 테스트 엣지이며, 모든 개체와 관계가 여전히 학습 데이터에 나타나도록 선택되었습니다(kg.py 65–74행). 홀드아웃된 세 개는 (bob, advises, dave), (bob, authored, p1), (erin, affiliated, cmu)입니다. 18개 전부를 $G_{\text{full}}$ 이라고 씁시다. $G_{\text{train}} \subset G_{\text{full}}$ 이므로(기호 $\subset$ 는 "…의 진부분집합이다"라고 읽습니다), 모든 질의는 둘 위에서 모두 평가될 수 있고, 프로토콜의 세 집합은 뺄셈 하나만큼 떨어져 있습니다(query_dag.py 200–213행):

\text{EASY}(q) = \llbracket q \rrbracket_{G_{\text{train}}}, \qquad \text{ALL}(q) = \llbracket q \rrbracket_{G_{\text{full}}}, \qquad \text{HARD}(q) = \text{ALL}(q) \setminus \text{EASY}(q).

쉬운 정답은 모델이 학습한 엣지를 순회하여 도달할 수 있습니다: 그것을 만들어 내는 데는 어떤 일반화도 필요 없으며 오직 찾아보기만 하면 됩니다. 하드 정답은 적어도 하나의 홀드아웃된 엣지를 필요로 하므로, 학습 그래프 위에서 어떤 양의 순회로도 찾을 수 없습니다; 그것을 찾아낸 모델은 여러 단계의 계산에서 올바른 자리에 빠진 엣지 하나를 진짜로 추론해 낸 것입니다 [1]. 위에서 다룬 2in 질의를 학습 그래프 위에서 다시 실행해 봅시다: bob의 advises 사영은 이제 carol만을 내놓는데, (bob, advises, dave)가 홀드아웃되었기 때문이고, 교집합은 carol 하나로 줄어듭니다. EASY는 carol을 담은 집합이고; ALL은 carol과 dave를 담으며; HARD는 dave이고, dave가 하드인 것은 정확히 그에게 도달하는 유일한 엣지가 홀드아웃된 세 개 중 하나이기 때문입니다. 은행 전체로 보면, 집계표가 이미 총계를 보여 주었습니다: 쉬운 정답 28개, 하드 정답 23개, 모든 유형이 대표됩니다. 여기서 공개해야 할 토이 규모의 압축이 하나 있습니다: 실제 벤치마크는 세 개의 그래프(학습, 그다음 학습+검증, 그다음 전체 엣지)를 중첩시키고 테스트 질의의 쉬운 정답을 그 가운데 그래프 위에서 계산합니다; 우리의 두 그래프 분할은 검증을 학습으로 접어 넣으므로 EASY가 검증 그래프 정답 집합의 역할을 맡으며, query_dag.py는 이 단순화를 독스트링(30–34행)에서 그대로 명시합니다.

부정이 없는 질의의 경우 쉬운 집합은 결코 전체 집합을 넘칠 수 없으며, 이는 그저 넘어갈 것이 아니라 증명할 가치가 있습니다. 그 증명이 정확히 부정이 그것을 어디서 깨뜨리는지를 보여 주기 때문입니다. 주장: 질의 $q$ 가 부정을 포함하지 않는다면, $E \subseteq E'$ 는(기호 $\subseteq$ 는 위의 엄격한 $\subset$ 와 달리 "같음도 허용하는 부분집합이다"라고 읽습니다) $\llbracket q \rrbracket_E \subseteq \llbracket q \rrbracket_{E'}$ 를 함의합니다(엣지를 추가하는 것은 정답만을 추가할 뿐입니다; 평가는 단조(monotone)입니다). 증명은 DAG 위의 구조적 귀납이며, 입력 집합까지 추적하도록 강화되어 있습니다: 우리는 입력 집합과 엣지 집합이 모두 커질 때 각 연산자의 출력이 부분집합의 의미에서 커진다는 것을 보입니다. 앵커는 엣지와 무관하게 $\lbrace e \rbrace$ 로 평가됩니다: 단조입니다. 사영에 대해서는, 표의 $P_r(S)$ 를 엣지 집합 $E$ 위에서 계산한 것을 $P_r(S, E)$ 로 써서 표가 암묵적으로 두었던 엣지 집합을 명시합시다; 이제 $S \subseteq S'$ 이고 $E \subseteq E'$ 이라 하고, 임의의 $t \in P_r(S, E)$ 를 취합시다. 의미론에 따라 $(h, r, t) \in E$ 인 증인 $h \in S$ 가 존재합니다. 같은 $h$ 가 $S'$ 에 속하고 같은 삼중항이 $E'$ 에 속하므로, $t \in P_r(S', E')$ 입니다: 두 인자 모두에서 단조입니다. 교집합과 합집합에 대해서는, 모든 피연산자 $i$ 에 대해 $S_i \subseteq S_i'$ 이면, 모든 $S_i$ 에 속하는(각각, 어떤 $S_i$ 에 속하는) 임의의 $x$ 는 모든 $S_i'$ 에 속합니다(어떤 $S_i'$ 에 속합니다): 둘 다 단조입니다. 잎에서부터의 귀납은 이 성질을 뿌리까지 옮깁니다. 이제 여집합이 협조를 거부하는 것을 보십시오: $S \subseteq S'$ 는 $V \setminus S' \subseteq V \setminus S$ 를 줍니다. 반대 방향의 포함입니다. 부정 노드 하나가 성장의 방향을 뒤집고, 귀납은 거기서 죽습니다. 커밋된 실행은 부정이 없는 25개 질의 전부에 대해 이 정리를 단언하는 동시에, 설계된 증인으로 그 실패를 보여 줍니다(query_dag.py 553–565행):

[3] negation breaks monotonicity (why BetaE's protocol filters with care)
  q(x) = affiliated(dave,x) ∧ ¬affiliated(erin,x)   [2in]
    on G_train : ['cmu']  (erin's cmu edge is held out, so ¬ lets cmu through)
    on G_full  : []  (the held-out edge RETRACTS the answer)
  for ¬-free queries EASY ⊆ ALL always holds (asserted for all 25 EPFO queries)

학습 그래프 위에서는 erin이 무소속으로 나타나고, 여집합은 cmu를 통과시키며, 질의는 cmu라고 답합니다; 전체 그래프는 erin의 cmu 소속을 드러내고 그 정답은 철회됩니다. 부정 질의에 대한 학습 그래프의 "정답"은 빠진 엣지의 인공물일 수 있으며, 이것이 바로 프로토콜이 정답을 $G_{\text{full}}$ 에 대해 정의하고 학습 그래프 평가를 오직 찾아보기가 달성하는 것의 하한으로만 다루는 이유입니다.

하드 정답만을, 필터링하여 채점하기

채점은 집합을 위해 확장된 3권의 필터링된 순위입니다. 채점 모델(scoring model)은 개체 $e$ 가 질의 $q$ 의 정답일 그럴듯함을 나타내는 스칼라를 부여하는 임의의 함수 $s(q, e)$ 입니다; 값이 높을수록 더 그럴듯합니다. 각 질의의 각 하드 정답 $v$ 에 대해, 모델은 $v$ 를 비정답(non-answer) $V \setminus \text{ALL}(q)$ 과 겨루어 순위를 매깁니다: 다른 모든 참인 정답은 쉽든 어렵든 먼저 후보 목록에서 제거되며, 이는 정확히 3권의 순위 프로토콜 장에서 다룬 "필터링" 관행입니다. 그래서 모델이 한 정답을 다른 정답보다 위에 두었다고 벌점을 받는 일은 결코 없습니다 [1]. 여기서 새로운 강화 하나가 추가됩니다(query_dag.py 367–388행): 동점은 균등한 동점 처리 아래에서 기댓값 순위로 기여합니다,

\text{rank}(v) \;=\; 1 \;+\; \#\lbrace e : s(q,e) \gt s(q,v) \rbrace \;+\; \tfrac{1}{2}\,\#\lbrace e : s(q,e) = s(q,v) \rbrace,

여기서 $\#$ 은 비정답 후보들에 대해 집합의 원소 수를 셉니다. 3권의 낙관적 관행 아래에서라면 상수 채점기는 모든 것과 동점을 이루어 1위를 주장했을 것입니다; 기댓값 순위 관행은 $k$ 개가 동점을 이루는 고원(plateau)에 $k/2$ 자리만큼의 비용을 물리며, 이는 CLQA 채점기가 정확히 그런 고원을 만들어 내기 때문에 중요합니다. 그러면 지표는 은행 안의 23개 하드 정답 전부에 대한 $1/\text{rank}$ 의 평균인 필터링된 평균 역순위(filtered mean reciprocal rank, MRR)입니다(query_dag.py 391–408행).

커밋된 하네스는 척도를 고정하는 세 개의 기준 채점기를 실행합니다(query_dag.py 413–437행). 오라클(oracle)은 $e \in \text{ALL}(q)$ 이면 1을, 아니면 0을 매깁니다: 모든 하드 정답이 모든 비정답을 확실히 앞서고, 순위는 정확히 1이며, MRR은 정확히 1.0000, 천장입니다. 순회 기준선(traversal baseline)은 $e \in \text{EASY}(q)$ 이면 1을, 아니면 0을 매깁니다: 이는 학습 그래프를 완전한 것으로 취급하는 임의의 시스템이 오를 수 있는 천장이며, 그 그래프가 지지할 수 있는 가장 강한 순수 찾아보기이고, $\text{HARD} = \text{ALL} \setminus \text{EASY}$ 라는 정의에 의해 모든 하드 정답에서 0점을 받습니다. (기호적 규칙 학습기는 이 영점에 매이지 않습니다: 앞 장의 AnyBURL은 학습 그래프에서 홀드아웃된 엣지를 채워 넣는 규칙을 채굴하므로 하드 정답을 1위에 둘 수 있습니다. 오직 문자 그대로의 찾아보기만이 구성상 배제됩니다.) 고정된 무작위 채점기(random scorer, 시드 0)는 정보 없는 바닥을 줍니다. 실행 결과입니다:

[5] filtered MRR over the 23 hard answers (rank vs non-answers V − ALL; ties → expected rank)
  type   #hard   oracle  traversal  random(0)
  1p         2   1.0000     0.1484     0.2250
  2p         2   1.0000     0.1484     0.1010
  3p         2   1.0000     0.1484     0.4167
  2i         2   1.0000     0.1429     0.1125
  3i         2   1.0000     0.1429     0.0909
  pi         2   1.0000     0.1484     0.5625
  ip         1   1.0000     0.1429     0.1000
  2u         2   1.0000     0.1603     0.1056
  up         2   1.0000     0.1538     0.2917
  2in        2   1.0000     0.1484     0.1964
  3in        1   1.0000     0.1429     0.2500
  inp        1   1.0000     0.1538     0.0909
  pin        1   1.0000     0.1538     0.1250
  pni        1   1.0000     0.1538     0.1250
  pooled    23   1.0000     0.1491     0.2128

순회 열은 완전히 유도해 볼 가치가 있습니다. 그 수치들은 적합된 것이 아니라 강제된 것이기 때문입니다. 두 개의 하드 정답을 모으는 1p 행을 봅시다. 질의 advises(bob, $x$ )에 대해: ALL은 carol과 dave를 담고 있으므로 13개 개체 중 11개가 비정답입니다; 순회는 하드 정답 dave에 0점을 매기고, 모든 비정답에도 0점을 매깁니다(비정답은 이 부정 없는 질의에서 쉬운 정답일 수 없습니다. 단조성 정리에 의해 EASY ⊆ ALL이기 때문입니다). 11개의 동점은 기댓값 순위 $1 + 0 + 11/2 = 6.5$ 를 주고, 역수는 $1/6.5 = 0.153846$ 입니다. authored(bob, $x$ )에 대해서는: ALL이 논문 p1 하나뿐이므로 12개의 비정답이 동점을 이루고, 순위는 $1 + 12/2 = 7$ , 역수는 $0.142857$ 입니다. 둘의 평균은 $0.148352$ 이며, 이는 커밋된 0.1484로 반올림됩니다. 이 열의 모든 항목이 바로 이 산술이며, 오라클의 1.0000에 대비한 합산 0.1491은 신경망 모델이 좁혀야 할 불완전성의 간극을 수치로 표현한 것입니다. 무작위 열이 여러 행에서 순회를 이기는 것도 눈여겨보십시오(합산 0.2128): 후보가 십여 개뿐이면 눈먼 운이 때로 하드 정답을 높이 올려놓지만, 순회는 결코 그러지 못합니다. 순회는 게으른 약한 모델이 아닙니다; 그것은 구조적으로 배제되어 있는 것입니다.

왜 응답이 링크 하나 예측하기가 아닌가

CLQA를 "링크 예측을 반복한 것"으로 분류하고 싶은 유혹이 있습니다. 교집합 질의는 그것이 왜 과소평가인지를 보여 줍니다. 커밋된 2i 질의 2i[0]을 봅시다(query_dag.py 250–251행):

q(x) \;=\; \text{authored}(\text{alice}, x) \,\wedge\, \text{authored}(\text{bob}, x).

각 논리곱항 하나만 놓고 보면 완벽하게 풀 수 있는 1p 질의입니다: 전체 그래프 위에서 alice의 authored 사영은 p1을 담고, bob의 사영도 마찬가지입니다. 그러나 논리곱의 유일한 정답 p1은 두 개의 특정 엣지, (alice, authored, p1)과 (bob, authored, p1)의 결합 진위에 좌우됩니다. 학습 그래프는 첫 번째를 담고 두 번째를 홀드아웃하므로, 순회의 교집합은 공집합입니다: EASY는 공집합이고, HARD는 p1입니다. p1을 만들어 내려면 모델은 관측된 엣지 하나를 신뢰하는 동시에 빠진 엣지 하나를 채워 넣어야 하며, 두 논리곱항 중 어느 하나에서라도 한 번 틀리면 정답은 무너집니다.

이 증폭은 일반화되며, 두 줄짜리 확률 스케치가 그 경향을 정확하게 만들어 줍니다. 이상화하여, 각 참인 엣지가 확률 $p$ 로 독립적으로 학습 그래프에 살아남는다고 합시다(보존율이며, 여기서는 $15/18 = 5/6 \approx 0.833$ 입니다. 다만 커밋된 분할은 표본 추출된 것이 아니라 결정적이므로, 이 계산은 은행의 정확한 개수가 아니라 메커니즘을 보여 줍니다). 서로 다른 $k$ 개의 엣지를 사용하는 유도를 가진 정답이 있다고 합시다. 여기서 $k$ 는 특정 정답이 필요로 하는 원자의 수를 셉니다(2i 정답은 2, 3i나 3p 정답은 3입니다). 이 정답이 순회로 도달 가능하려면 $k$ 개 모두가 살아남아야 하며, 그 확률은

p^{k} \quad\text{: with } p = \tfrac{5}{6}, \qquad p^1 \approx 0.833, \qquad p^2 \approx 0.694, \qquad p^3 \approx 0.579.

실패 확률 $1 - p^k$ 는 홉과 논리곱항이 늘어날수록 커지므로, 질의가 더 깊고 넓을수록 순회가 볼 수 없는 참인 정답의 비율이 더 커집니다. 링크 예측은 $1 - p$ 를 한 번 마주하지만, CLQA는 그것을 복합적으로 늘립니다. 이것이 바로 이 과제가 "성장한" 링크 예측이라는 말의 정량적 의미입니다: 같은 불완전성이 합성을 통해 증폭되며, DAG가 정확히 어떤 엣지들이 결합적으로 옳아야 하는지를 지시합니다.

열세 개 개체 대 만오천 개

왜 약 30줄짜리 실행기가 이 부의 금본위(gold standard)로 쓰일 수 있을까요? 그 작업량을 세어 봅시다. $m$ 개의 연산자 노드를 가진 DAG는 위상 순서로 평가됩니다; 각 사영은 엣지 집합을 한 번 훑고( $|E|$ 개의 삼중항, $|\cdot|$ 은 집합의 크기를 나타냅니다), 각 여집합은 최대 $|V|$ 개의 개체를 건드리며, 각 교집합이나 합집합은 $|V|$ 보다 크지 않은 집합들을 병합합니다. 총 비용은 $O\!\big(m \cdot (|E| + |V|)\big)$ 이며, $O(\cdot)$ 는 "많아야 그것에 비례하여 자란다"라고 읽습니다: 18개 엣지와 13개 개체 위의 36개 질의라면 마이크로초 단위입니다. 토이 규모에서는 완전 탐색적 정확한 평가가 저렴하며, 바로 그것이 이 토이가 유용한 정확한 이유입니다: 다음 세 장에서 보고되는 모든 신경망 수치는 질의마다, 개체마다 완벽한 정답표와 비교될 수 있습니다.

벤치마크 규모에서는 같은 산술이 이 분야의 곤경을 설명합니다. 표준 벤치마크는 이런 질의 유형들을 수만 개의 개체와 수십만 개의 엣지를 가진 그래프 위에, 수백만 개로 표본 추출된 질의 은행과 함께 던집니다; 큰 중간 집합에서의 사영 하나만으로도 이미 전체 개체 어휘에 걸친 순위 문제가 되고, 중간 집합은 질의 도중 수천 개의 개체로 부풀어 오를 수 있으며, 실행기의 노드별 정확성은 더 이상 공짜가 아니게 됩니다 [5]. 더 근본적으로, 아무리 많은 연산을 쏟아부어도 관측된 그래프의 순회는 하드 정답을 찾을 수 없는 기준선으로 남습니다: 하드 집합에서의 그 영점은 어떤 규모에서든 정의에 의한 것이며, 이는 질의를 실행하는 대신 임베딩해야 한다는 이 분야의 상시적 논거입니다 [1]. 커밋된 토이는 그 논거를 슬로건이 아니라 재현 가능한 표로 만듭니다; 이 분야를 조망하는 그 서베이는 상당 부분 DAG를 포기하지 않으면서 0.1491이라는 열을 이겨 내는 방법들의 목록입니다 [5].

미해결로 남은 부분

이 장의 모든 것은 법칙의 옷을 입은 관행이며, 그 옷을 벗겨 보는 것이 정직합니다. 닫힌 세계 부정이 가장 큰 목소리를 냅니다: ¬를 우리 스스로 열거한 13개 개체의 여집합으로 읽는 것은 정당하지만, 웹 규모 그래프의 기록된 엣지의 여집합으로 읽는 것은 기록되지 않은 모든 소속이 거짓이라고 주장하는 것이며, 이는 정확히 이 프로토콜의 나머지가 거부하기 위해 존재하는 불완전성 가정입니다. 위의 증인 질의는 그 증상을 축소판으로 보여 주었습니다: 정답이 주장되었다가 엣지가 도착하면서 철회되었습니다. 자유 변수 하나라는 제약이 두 번째 사례입니다: 질문이 한 번에 두 개의 미지수를 묶는 순간("어떤 지도교수-학생 쌍이 논문을 공저했는가?") 정답은 튜플의 집합이 되고, DAG의 노드당 한 영역이라는 그림은 더 이상 들어맞지 않으며, 두 변수가 서로를 제약하는 순환적 질의 그래프는 잎에서부터의 평가를 완전히 벗어납니다; 트리 모양의 단일 변수 조각을 넘어서는 평가로 확장하는 것은 명시적이고 활발한 프론티어입니다 [6]. 그리고 이 둘 밑에는 3권이 링크 예측을 위해 가르쳤던 벤치마크 설계의 교훈이 놓여 있습니다: 질의 은행의 분포, 곧 어떤 구조가 표본 추출되는지, 어떤 앵커가, 어떤 관계가 표본 추출되는지가 보고되는 모든 수치를 소리 없이 빚습니다. 우리의 은행은 14개 유형 모두가 하드 정답을 갖도록 손수 고른 것입니다; 표본 추출된 은행은 그런 선택을 수천 번 보이지 않게 내리며, 어떤 MRR 표도 그것들을 알려 주지 않습니다.

왜 중요한가

DAG는 이 부 전체가 돌아가는 경첩입니다. 이 부의 남은 장들은 실행기의 집합 연산을 기하학적·확률적 대응물(집합을 위한 영역, 사영과 교집합을 위한 학습된 연산자)로 교체할 것이며, 그런 모델 하나하나는 다섯 유형 분할 위에서 학습되고, 23개의 하드 정답 위에서 채점되며, 여기서 세운 두 개의 기준 열, 곧 오라클의 1.0000과 순회의 0.1491과 비교될 것입니다. 그 평가에서 신경망적인 것은 아무것도 없습니다; 그것은 드모르간을 통해 교차 검증된 기호적 계측기이며, 토이 규모에서의 그 정확성이야말로 신경망 질의 응답기가 정확히 어디서 성공하고 어디서 실패하는지 우리가 말할 수 있게 해 주는 것입니다. 이 장은 또한 5권에도 앞당겨 지불합니다: 쉬움/어려움 분할은 "모델이 추론했는가, 아니면 찾아보았는가?"라는 질문의 이 분야 버전이고, 제로샷 구조 분할은 "모델이 연산자를 학습했는가, 아니면 템플릿을 학습했는가?"라는 질문의 이 분야 버전입니다. 추론기가 언어 모델일 때 이 두 질문은 훨씬 높은 판돈을 걸고 되돌아옵니다.

핵심 용어

복합 논리 질의 응답(Complex logical query answering, CLQA) — 불완전한 지식 그래프 위에서 존재 한정, 논리곱, 논리합, 제한된 부정을 가진 1차 질의에 답하는 것; 링크 예측은 그 원자 하나짜리 특수 사례입니다.
EPFO 질의(EPFO query) — 실존 긍정 1차 질의: 자유 변수 하나, 존재 변수들, ∧와 ∨, 부정 없음; 아홉 가지 긍정 정준 유형 [2]이 다섯 가지 부정 유형으로 확장됩니다 [1].
질의 계산 DAG(Query computation DAG) — 질의를 유향 비순환 그래프로 나타낸 것: 잎에는 앵커 개체, 내부 노드에는 집합 연산자(사영과 교집합은 [4]에서, 합집합은 [2]에서, 여집합은 [1]에서 왔습니다)가 있으며 위상 순서로 평가됩니다; 존재 변수는 사영에 흡수됩니다.
관계 사영(Relation projection) — $P_r(S) = \lbrace t \mid \exists h \in S : (h,r,t) \in E \rbrace$ , 집합의 한 홉 상(image)이며; 엣지 집합을 읽는 유일한 연산자입니다.
닫힌 세계 부정(Closed-world negation) — 알려진 개체 집합 안에서 ¬를 여집합 $V \setminus S$ 로 읽는 것; 이 분야의 관행이며 여기서 물려받은 것이고, 빠진 엣지에 대한 진리가 아니라 관행입니다.
쉬운/어려운 정답(Easy / hard answers) — $\text{EASY} = \llbracket q \rrbracket_{G_{\text{train}}}$ , $\text{ALL} = \llbracket q \rrbracket_{G_{\text{full}}}$ , $\text{HARD} = \text{ALL} \setminus \text{EASY}$ ; 하드 정답은 적어도 하나의 홀드아웃된 엣지를 채워 넣어야 하며, 지표는 하드 정답에 대해서만 계산됩니다.
단조성(Monotonicity) — 부정이 없는 질의에서는 엣지를 추가하는 것이 정답만을 추가합니다(구조적 귀납으로 증명됨); 여집합 노드 하나가 이를 깨뜨리며, 커밋된 철회 질의로 목격됩니다.
기댓값 순위 동점 처리를 갖춘 필터링된 MRR(Filtered MRR with expected-rank ties) — 비정답 $V \setminus \text{ALL}$ 에 대한 평균 역순위이며, 다른 참인 정답은 걸러 내고, 동점은 그 고원의 절반만큼 비용을 물립니다; 커밋된 은행에서 오라클 1.0000, 순회 0.1491, 무작위 0.2128입니다.
제로샷 구조 분할(Zero-shot structure split) — 1p, 2p, 3p, 2i, 3i(그리고 부정 유형 [1])로 학습하고, 본 적 없는 ip, pi, 2u, up으로 평가합니다: 구성상 검사되는 구성적 일반화입니다 [2].

다음으로 이어지는 곳

계측기는 만들어졌습니다; 이제 선수들이 등장할 차례입니다. 다음 장 GQE에서 BetaE로는 DAG를 미분 가능하게 만듭니다: 앵커 노드는 개체 임베딩이 되고, 사영은 학습된 변환이 되며, 교집합은 영역에 대한 연산(점, 그다음 박스, 그다음 베타 분포)이 되고, 실행기의 정확한 집합들은 그것을 근사하도록 학습된 기하가 됩니다. 이 장의 MRR 표에 있는 세 열은 네 번째 열을 기다리고 있습니다: 홀드아웃된 엣지를 실제로 추론함으로써 0.1491을 이기는 모델이며, 같은 23개의 하드 정답 위에서 같은 필터링된 프로토콜로 채점됩니다.

동반 코드: examples/integration/query_dag.py는 이 장 전체를 구현합니다: 두 그래프와 닫힌 세계(70–74행), 14가지 구조(84–99행), 실행기(112–157행), 드모르간 재작성과 그 36/36 교차 검증(160–195행 및 531–551행), 쉬움/어려움 프로토콜(198–213행), 질의별 1차 술어 해설을 갖춘 36개 질의 은행(216–351행), 필터링된 순위와 MRR 하네스(365–408행), 세 개의 기준 채점기(411–437행), 그리고 단조성 정리와 비단조 증인을 포함하여 여기서 이루어진 모든 주장을 지키는 assert들(501–588행)입니다. python3 examples/integration/query_dag.py를 실행하면 모든 숫자를 바이트 단위로 재현할 수 있습니다; 그 실행은 SUMMARY query_dag: types=14 queries=36 hard=23 hard_types=14 demorgan=36/36 oracle_mrr=1.0000 traversal_mrr=0.1491 random_mrr=0.2128로 끝납니다.

이 장에서 다루는 내용​

빠진 엣지 하나에서 1차 질문으로​

계산 DAG: 네 연산자, 잎에서부터 평가​

14가지 형태, 하나의 명명 문법​

실행기는 스스로를 검증한다: 교차 검증으로서의 드모르간​

쉬움 대 어려움: 프로토콜의 핵심​

하드 정답만을, 필터링하여 채점하기​

왜 응답이 링크 하나 예측하기가 아닌가​

열세 개 개체 대 만오천 개​

미해결로 남은 부분​

왜 중요한가​

핵심 용어​

다음으로 이어지는 곳​