퍼지·무학습 CLQA: CQD, GNN-QE, QTO

📍 현재 위치: V부 · 복합 논리 질의 응답 — 17장. GQE에서 BetaE로는 질의 구조마다 새로운 기하를 학습함으로써, 즉 표집된 다중 홉 질의로 훈련함으로써 복합 질의에 답했습니다. 이 장은 그 학습을 지우고, 퍼지 논리로 합성된 단 하나의 보정된 1홉 예측기만으로 이미 충분한지를 묻습니다.

앞 장의 질의 임베딩 계열에는 숨은 청구서가 딸려 있습니다. GQE, Query2Box, BetaE는 각각 질의 수준의 매개변수, 곧 교집합 네트워크, 박스 오프셋, 베타 분포 연산자를 학습하는데, 이들은 모두 표집된 수백만 개의 질의-답 쌍 위에서 경사 하강법으로 맞춰지며, 질의 구조마다 하나씩의 훈련 분포를 필요로 합니다. 훈련 시점에 어떤 구조 하나를 빠뜨리면, 모델은 그 모양을 한 번도 본 적이 없는 채로 남습니다. 이 장은 그 반대되는 논제를 세웁니다. 복합 질의가 필요로 하는 지식은 이미 1홉 예측기 안에 들어 있으며, 원자 위에 놓이는 모든 것은 학습이 아니라 추론이라는 것입니다. 링크 예측기의 점수를 0과 1 사이의 진리값으로 보정하기만 하면, I부의 퍼지 연결사가 나머지 일을 합니다. 논리곱은 곱셈이 되고, 존재 한정사는 최댓값을 취하는 일이 되며, 질의 전체는 그 계산 그래프가 조직하는 하나의 최적화 문제가 됩니다. 우리는 이 논제를 학계 세계 위에서 세 가지 방식으로 실행합니다. 탐욕적으로는 구체적 개체 위에서 벌이는 CQD의 빔 탐색이고, 조밀하게는 모든 노드에서 13개 개체 전부의 소속 점수를 유지하는 퍼지 집합 읽기이며, 정확하게는 질의 트리 위에서 증명 가능한 최적값을 검사 가능한 증명과 함께 내놓는 QTO의 동적 계획법입니다.

쉽게 말하면

신뢰도 표를 가지고 두 구간짜리 여행을 계획한다고 상상해 보십시오. 모든 도시 쌍마다 직항편이 얼마나 믿을 만한지를 나타내는 0과 1 사이의 숫자가 하나씩 적혀 있습니다. 누구도 특별한 "두 구간 모델"을 따로 다시 훈련하지 않습니다. 경유 도시를 거치는 두 구간짜리 여행은 그중 더 약한 구간이 허락하는 만큼만 믿을 만하며(두 숫자를 곱하면 됩니다), 최선의 경유지는 그 곱을 최대로 만드는 도시입니다. 서두르는 계획자는 가장 유망한 경유지 네 곳만 추려 내고 나머지는 무시합니다. 빠르긴 하지만, 만약 진짜 최선의 경유지가 그 목록에서 빠졌다면 그 뒤로 아무리 영리하게 굴어도 되찾을 수 없습니다. 신중한 계획자는 지도 위의 모든 도시에 대해 점수를 계속 갱신하므로, 아무것도 버려지지 않습니다. 그리고 넉넉히 큰 스프레드시트를 가진 인내심 있는 계획자는 정확한 최선의 여정을 계산해 내고 영수증까지 건네줍니다. 이 두 구간이, 이 두 신뢰도로, 곱해져서 정확히 이 점수가 된다는 영수증입니다. 이 세 계획자가 각각 CQD-Beam, 퍼지 집합 실행기, QTO이며, 신뢰도 표는 이들 모두가 공유하는 보정된 1홉 예측기입니다.

이 장에서 다루는 내용

정량화된 도발: 앞 장의 모델들은 표집된 복합 질의로 훈련되지만, CQD의 주장은 사전 훈련된 1홉 예측기에 t-노름 합성을 더했을 뿐 질의 수준의 훈련은 전혀 없다는 것이며, 이는 복합 질의 능력을 학습의 성질이 아니라 추론의 성질로 다시 규정합니다.
조심스레 지어진 원자 층: 3권의 ComplEx를 관측된 15개 엣지 위에서 다시 훈련한 다음, 행별 소프트맥스 방식으로 신경 인접 행렬 $M_r \in [0,1]^{13 \times 13}$ (관계 $r$ 마다 하나씩인, 0과 1 사이의 진리값으로 이루어진 13행 13열 격자이며, 원자 층 절에서 완전히 해독합니다)로 보정하는데, 관측된 엣지는 모두 정확히 1로 고정되고 채워 넣은 항목은 모두 1 미만으로 엄격히 상한이 매겨집니다.
퍼지 최적화로서의 질의: 논리곱은 곱 t-노름으로, 존재 한정사는 13개 후보 결속에 대한 최댓값으로, 부정은 언어가 그것을 지원하는 곳에서 여집합으로 표현됩니다. 2p 질의의 전체 목적함수를 기호 하나하나까지 풀어 써서 해독합니다.
세 실행기, 하나의 대수: 해석 가능하고 탐욕적이며 손실이 유도 가능한 CQD-Beam의 상위 k개 구체적 개체, 아무것도 가지치기하지 않는 완전한 소속 벡터, 그리고 QTO의 정확한 최댓값-곱 동적 계획법을 다루며, 왜 트리가 정확한 DP를 허락하는지도 유도합니다.
충실한 증명: 증인이 되는 할당을 추출하는 역방향 argmax 패스를 커밋된 실행에서 그대로 인용해 엣지 하나하나까지 검사하며, 증명 가능한 답은 1로 고정된 엣지를 타고 가기 때문에 결코 놓치지 않는다는 축소판 따름정리도 함께 다룹니다.
커밋된 세 갈래 표: 기호적 순회는 어려운 답 MRR 0.1465에 머물고, 무학습 답변기 둘은 모두 0.8000, 오라클은 1.0000이며, 남은 0.2가 어디로 갔는지를 정직하게 읽어 냅니다.
정직한 문구: "무학습"은 오직 질의 수준에서만 성립합니다. 1홉 예측기는 여전히 훈련되며, 그 보정이 이후의 모든 것을 소리 없이 제한합니다.

도발: 질의 수준 학습 없는 능력

앞 장의 비용 모델을 정확히 짚어 봅시다. 질의 임베딩 시스템은 자신의 질의 언어가 담고 있는 모든 연산자에 대해 매개변수를 학습해야 하며, 그 매개변수는 표집된 복합 질의 위에서 맞춰집니다: 표준 파이프라인은 훈련 그래프로부터 각 구조(1p, 2p, 2i, 그리고 나머지)의 질의 인스턴스를 수십만 개, 총합으로는 수백만 개를 채굴하여 그 전부에 대해 대조적 경사 하강법을 실행하는데, 이 훈련 비용은 앞 장이 정량화하여 그 마무리 절에서 표준 벤치마크에 맞대어 인용한 것입니다. 이제 훈련 집합은 더 이상 지식 그래프가 아니라 질의 모양 위의 합성된 분포이며, 본 적 없는 모양으로의 일반화는 경험적 도박입니다.

CQD(Continuous Query Decomposition)는 정반대의 내기를 겁니다 [1]. 3권이 이미 지어 둔 1홉 링크 예측기 말고는 아무것도 훈련하지 않는 것입니다. 모든 복합 질의는 $r(a, x)$ , 즉 "개체 $a$ 는 관계 $r$ 을 통해 후보 $x$ 와 관계된다" 형태의 원자들로 조립되며, 1홉 예측기는 이미 그런 원자마다 점수를 매겨 두고 있습니다. 빠진 것은 지식이 아니라 합성입니다. 논리곱과 존재 한정사에 걸쳐 원자 점수들을 결합하는 원칙 있는 방법이 빠져 있는 것입니다. 이 권의 I부가 정확히 그 기계 장치를 만들었습니다. t-노름과 t-코노름 장은 t-노름이 $[0,1]$ 안의 진리값 쌍을 그 논리곱의 진리값으로 어떻게 바꾸는지 보여 주었습니다. 그러니 조리법은 이렇습니다. 원자 점수를 $[0,1]$ 안으로 눌러 담고, t-노름으로 그것들을 합성하고, 질의를 미지 변수들에 대한 최적화 문제로 읽는 것입니다. 교집합 네트워크도, 박스 오프셋도, 베타 매개변수도 없습니다. 이것이 훈련된 기하들만큼 근사적으로라도 잘 작동한다면, 복합 질의 응답은 질의 인코더의 학습 성질이 아니라 좋은 링크 예측기의 추론 성질이 되며, V부 전체가 바로 그 재규정 위에서 돌아갑니다.

이 주장은 우리 규모에서 검사 가능한데, 시험대가 전혀 바뀌지 않기 때문입니다. 같은 13개 개체, 5개 관계의 학계 세계, 같은 3개의 제외해 둔 엣지를 가진 15개 엣지짜리 훈련 그래프, 그리고 이 부의 앞에서 query_dag.py가 고정해 둔 것과 같은 쉬운/어려운 답 프로토콜입니다(쉬운 답은 관측된 엣지를 순회해 도달할 수 있고, 어려운 답은 제외해 둔 엣지 하나를 채워 넣어야 하므로 순회는 정의상 그 위에서 0점을 받습니다). 동반 모듈 cqd.py가 이 논변 전체를 처음부터 끝까지 실행합니다.

원자 층: 점수에서 보정된 진리값으로

모든 것은 재사용에서 시작됩니다. 1홉 예측기는 새로운 모델이 아닙니다. 3권의 ComplEx를 같은 시드로부터 바이트 단위까지 동일하게, 훈련 분할 위에서만 다시 훈련한 것입니다(cqd.py 304–306행):

    # -- 1-hop ComplEx, retrained exactly as in the Volume 3 suite (seed 0).
    e_re, e_im, w_re, w_im, snaps = bilinear.train_complex(seed=0)
    S = complex_score_table(e_re, e_im, w_re, w_im)

여기서 bilinear.train_complex는 bilinear.py 256–287행의 훈련 루프 그 자체입니다(16개의 실수 차원을 8개의 복소수로 읽고, 로지스틱 손실을 쓰며, 양성마다 균등 분포에서 뽑은 음성 하나를 짝지어 1000 에폭을 돌립니다). 그리고 complex_score_table(cqd.py 77–96행)은 훈련된 점수 함수를 모든 조합에 대해 한꺼번에 평가하여, 관계 $r$ , 머리 개체 $h$ , 꼬리 개체 $t$ 로 인덱싱되는 원(raw) 점수 텐서 $S[r, h, t]$ 를 내놓습니다. 이 모듈은 이 표의 $5 \times 13 \times 13 = 845$ 개 항목 전부를 bilinear.complex_score에 대해 트리플 하나씩 대조 검사하고, 가장 큰 불일치가 $10^{-9}$ 미만임을 단언합니다(cqd.py 307–312행). 그래서 이후의 모든 숫자는 재구현의 의견이 아니라 훈련된 모델 자신의 의견입니다.

원점수는 진리값이 될 수 없습니다. ComplEx 점수는 위로 유계가 아닌 실수입니다. 로지스틱 훈련 손실은 그저 양성 트리플을 0 위로, 음성 트리플을 0 아래로 밀어낼 뿐이므로, 3.2와 5.1이라는 점수는 둘 다 상한 없이 "참에 가까운" 값이고, 순위 매김에 의미 있는 것은 오직 그 값들의 순서뿐입니다. 곱 t-노름이 필요로 하는 것은 순서보다 더 많습니다. $[0,1]$ 안의 입력에 대해서는 곱셈이 논리곱을 정의하는 건전성 법칙을 만족시킵니다. $y \le 1$ 이면 $x \cdot y \le x \cdot 1 = x$ 이고, 대칭적으로 $x \cdot y \le y$ 이므로, 논리곱은 그것을 이루는 가장 약한 항보다 결코 더 참일 수 없습니다. 그런데 곱셈에 원점수를 그대로 먹이면 이 법칙은 무너집니다. $3.2 \times 5.1 = 16.32$ 는 두 항 어느 쪽보다도 더 확신에 찬 "논리곱"이 되어 버립니다. 그러므로 합성에는 보정(calibration)이 필요합니다. 원점수를 $[0,1]$ 로 보내되 예측기의 순위는 그대로 지키면서 그 출력에 진리값 눈금을 부여하는 단조 사상입니다.

커밋된 보정 방식은 QTO(Query Computation Tree Optimization)의 조리법이며 [2], neural_adjacency(cqd.py 99–128행)에 구현되어 있습니다. 코드를 읽기 전에 먼저 해독해 둡시다. 머리 개체 $h$ 와 관계 $r$ 을 고정하고, 모든 후보 꼬리에 걸친 원점수의 행을 봅니다. 그 행의 소프트맥스 $\exp(S[r,h,t]) / \sum_{e \in V} \exp(S[r,h,e])$ 는 각 점수를 지수화하여(모든 것을 양수로 만들고) 행의 총합으로 나누므로, 그 행은 합이 1이 되는 확률 비슷한 벡터가 됩니다. 여기서 $V$ 는 개체 집합이고 $\sum_{e \in V}$ 는 "13개 후보 꼬리 전부에 걸쳐 합한다"로 읽습니다. 그러나 한 머리 개체는 실제로 여러 꼬리를 가질 수 있고(bob은 학생을 한 명보다 많이 지도합니다), 합이 1인 벡터로는 "이 중 둘이 완전히 참이다"라고 말할 수 없습니다. 그래서 이 조리법은 그 행을 $N_t$ , 곧 훈련 그래프에서 $(h, r)$ 에 대해 관측된 꼬리의 개수로 다시 스케일링합니다(관측된 꼬리가 없는 행이 0으로 죽어 버리지 않도록 최소 1로 바닥을 정합니다). 마지막으로 두 개의 클램프가 이 행렬에 논리적 이빨을 달아 줍니다. 모든 항목은 $\delta = 10^{-4}$ 인 $1 - \delta$ 에서 상한이 매겨지므로 어떤 채워 넣은 엣지도 결코 진리값 1에 이를 수 없으며, 그런 다음 관측된 훈련 엣지는 모두 정확히 1로 고정됩니다:

    # Observed tails per (head, relation), from the TRAIN graph only.
    n_tails = np.zeros((N_R, N_E))
    for h, r, t in kg.TRAIN:
        n_tails[kg.R_ID[r], kg.E_ID[h]] += 1.0
    # exp(S) / Σ_tails exp(S), computed stably by shifting each row's max.
    ex = np.exp(S - S.max(axis=2, keepdims=True))
    softmax = ex / ex.sum(axis=2, keepdims=True)
    # r̂ = softmax · N_t  (N_t floored at 1), then the 1-δ cap.
    rhat = softmax * np.maximum(n_tails, 1.0)[:, :, None]
    M = np.minimum(rhat, 1.0 - DELTA)
    # Pin: (e_i, r, e_j) ∈ TRAIN  ⇒  M_r[i,j] = 1 exactly.
    for h, r, t in kg.TRAIN:
        M[kg.R_ID[r], kg.E_ID[h], kg.E_ID[t]] = 1.0
    return M

그 결과가 신경 인접 행렬입니다. 관계 $r$ 마다 행렬 $M_r \in [0,1]^{13 \times 13}$ 이 하나씩 있는데(0과 1 사이의 숫자로 이루어진 13행 13열 격자로, 행마다 머리 개체 하나, 열마다 후보 꼬리 하나가 대응한다고 읽습니다), 그 항목 $M_r[h,t]$ 는 원자 $r(h,t)$ 의 보정된 진리값입니다. 이는 그래프 알고리즘이 쓸 법한 딱 떨어지는 인접 행렬을 퍼지하게 일반화한 것으로, 관측된 엣지는 정확히 1이고 나머지는 모두 모델이 등급을 매겨 내놓은 추측이며 엄격히 1 미만입니다. 커밋된 실행은 우리의 관통 질의에 가장 중요한 행을 출력합니다:

[1] the neural adjacency M_r (QTO Eq. 3-4 over the trained ComplEx)
  calibration: per (head, r), softmax raw scores over tails, x N_t observed tails,
  cap at 1-delta (delta=0.0001); then every TRAIN edge pinned to exactly 1.0
  15 pinned entries (the 15 TRAIN edges); largest imputed entry 0.9999
  row M[advises][bob, :] — how the model imputes bob's advisees:
    carol    1.000000   pinned: TRAIN edge
    dave     0.000411   imputed: held-out TEST edge
    nesy     0.000005   imputed: not an edge

이 행을 방법 전체의 축소판으로 읽으십시오. 관측된 엣지 (bob, advises, carol)는 정확히 1.000000에 앉아 있는데, 이는 모델이 그것을 벌어들여서가 아니라 고정되었기 때문입니다. 모델이 한 번도 본 적 없는 제외해 둔 엣지 (bob, advises, dave)는 0.000411로 채워 넣어집니다. 작은 숫자이지만 엣지가 아닌 (bob, advises, nesy)의 0.000005보다는 두 자릿수 위이며, 순위 매김이 기대는 것은 바로 그 비율입니다. 여기서 한 가지 정직함의 표지판을 세워 두고 결코 내리지 말아야 합니다. 이 장의 이후 모든 보장은 이 숫자들을 가지고 계산하는 것에 대한 보장이지, 그 숫자들이 옳다는 것에 대한 보장이 아닙니다. QTO의 최적성 정리는 보정된 목적함수의 정확한 최대화 항을 찾아냅니다. 만약 보정이 어떤 엣지의 순위를 잘못 매겼다면, 정확한 최적화기는 그 잘못된 순위를 그대로 물려받습니다. 이 장 끝의 커밋된 표는 정확히 이 실패를 한 번 보여 주며, 5권의 보정 장이 이 질문을 일반적으로 파고듭니다.

합성: 퍼지 최적화 문제로서의 질의

관통 2p 질의를 1차 논리 형태 $q(x) = \exists y.\, \mathrm{advises}(\mathrm{alice}, y) \wedge \mathrm{advises}(y, x)$ 로 가져와 봅시다. "alice의 어떤 지도학생에게 지도받는 사람은 누구인가?"라는 뜻입니다. 여기서 $x$ 는 목표 변수(target variable, 순위가 매겨지는 개체)이고, $y$ 는 구속 변수(bound variable, 질의가 언급하지만 답으로 돌려주지는 않는 중간 개체)이며, $\exists$ 는 "존재한다"로, $\wedge$ 는 "그리고"로 읽습니다. 앞 장의 딱 떨어지는 의미론 아래에서는, 어떤 증인 $y$ 가 두 원자를 모두 참인 엣지로 만들 때 개체 $x$ 가 질의에 답합니다. 퍼지 의미론은 각 딱 떨어지는 원자를 그 보정된 진리값으로, 각 연결사를 그 퍼지 연산자로 바꾸어, 모든 후보 $x$ 에게 등급이 매겨진 진리값을 부여합니다:

T(x) \;=\; \max_{y \in V}\; M_{\mathrm{advises}}[\mathrm{alice}, y] \cdot M_{\mathrm{advises}}[y, x].

조각마다 해독해 봅시다. $M_{\mathrm{advises}}[\mathrm{alice}, y]$ 는 구속 변수를 후보 $y$ 로 고정했을 때 첫 원자의 보정된 진리값입니다. 곱셈 $\cdot$ 는 $\wedge$ 역할을 하는 곱 t-노름이므로, 한 접지(grounding)의 진리값은 그 원자들의 진리값의 곱입니다. 그리고 13개 후보 $y$ 결속 전부에 대한 최댓값인 $\max_{y \in V}$ 는 $\exists$ 역할을 합니다. 존재 주장은 그 최선의 증인이 만들어 주는 만큼만 참입니다. (최댓값은 $\exists$ 에 대한 표준적인 퍼지 읽기입니다. 한정사를 집계 연산자로 보는 이 관점은 로직 텐서 네트워크 장이 일반적으로 전개한 것입니다. 이를 I부의 목록에 있는 $\wedge$ 에 대한 곱 t-노름과 짝짓는 것이 바로 질의 응답을 최적화로 바꾸는 대목입니다.) 이제 질의 전체는 하나의 이산 최적화 문제입니다. 각 목표 $x$ 에 대해, 구속 변수들의 배정에 걸쳐 행렬 항목들의 곱을 최대화하는 것입니다. 이 부의 첫 장이 딱 떨어지는 집합 연산을 조직하는 데 썼던 질의의 계산 DAG(computation DAG; directed acyclic graph, 유향 비순환 그래프)는 이제 정확히 이 최적화를 조직합니다. 각 노드는 13개 개체에 걸친 진리값 벡터를 가지고 있고, 각 엣지는 퍼지 연산자 하나를 적용합니다. 전체 연산자 목록과 각각을 구현하는 cqd.py의 정확한 줄은 다음과 같습니다:

질의 노드	딱 떨어지는 집합 의미론(`query_dag.py`)	벡터 $v \in [0,1]^{13}$ 위의 퍼지 연산자	`cqd.py`
앵커 $e$	$e$ 하나만을 담은 단일 원소 집합	원-핫 벡터: $v[e] = 1$ , 나머지는 0	167–170행
$r$ 에 의한 투영	$r$ -엣지를 따라간다	$v'[t] = \max_h v[h] \cdot M_r[h,t]$	189행
교집합	집합 교집합	항별 곱 $v = \prod_i v_i$	191–195행
합집합	집합 합집합	확률적 합 $v = 1 - \prod_i (1 - v_i)$	171–176행
부정	여집합 $V - S$	$v' = 1 - v$ (실행되지 않음: 뱅크가 EPFO이므로)	179행에서 거부

표에 대한 해독 참고 사항이 두 가지 있습니다. 교집합과 합집합 행에서 $\prod_i$ 는 그 노드로 들어오는 가지 $i$ 에 걸쳐, 가지마다 하나씩의 소속 벡터 $v_i$ 를 곱합니다. 그리고 커밋된 다섯 유형 뱅크는 앵커, 투영, 교집합 행만을 실행합니다. 합집합 연산자는 구현되어 있지만 커밋된 실행에서는 결코 호출되지 않으며(이 장 뒤에서 나오는 정확한 동적 계획법이 그것을 불필요한 것으로 거부합니다, cqd.py 221행), 부정이 거부되는 것과 마찬가지입니다.

EPFO(existential positive first-order, 존재 긍정 1차)는 부정이 없는 조각을 가리키는 이름입니다. 오직 $\exists$ , $\wedge$ , $\vee$ 만으로 지어진 질의로, CQD의 언어이자 이 장의 다섯 질의 유형(1p, 2p, 2i, pi, ip)의 범위입니다. 여집합 행은 부정이 존재할 때 GNN-QE(Graph Neural Network Query Executor)와 QTO가 같은 대수를 확장하는 자리입니다. 이 장의 세 시스템은 하나의 같은 목적함수를 평가하는 세 가지 전략입니다. 다른 것은 오직 각 노드의 벡터가 얼마나 많이 살아남는가뿐입니다.

하나의 보정된 인접 행렬, 하나의 퍼지 목적함수, 세 가지 평가 전략: 네 개의 후보로 가지치기하거나(CQD-Beam), 전체 소속 벡터를 유지하거나(퍼지 집합 읽기), 정확히 풀어 증인을 추출하거나(QTO)입니다. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

CQD-Beam: 구체적 개체 위의 탐욕적 탐색

CQD의 빔 변형은 DAG를 위상 순서로(부모보다 자식을 먼저, 앵커를 가장 먼저) 평가하며, 모든 구속 변수에서 오직 점수가 가장 높은 상위 $k$ 개의 개체만 남기고 나머지는 모두 0으로 만듭니다. 여기서 $k$ 는 빔 폭(beam width)이며, 커밋된 실행에서는 4로 설정되어 있습니다. 발표된 시스템은 데이터셋마다 4에서 256에 이르는 그리드 위에서 이를 조정합니다 [1]. 구현의 핵심은 코드 열한 줄에 주석 세 줄을 더한 것입니다(cqd.py 177–190행):

    # Projection chain (sub, (r1, ..., rn)): truncate, hop, repeat.
    if query_dag._is_chain(q):
        assert N not in q[1], "CQD is EPFO-only: no negation atoms"
        v = cqd_beam(q[0], M, k, trace)
        for r in q[1]:
            # Beam: only the top-k bindings of this bound variable survive.
            v = _truncate(v, k)
            if trace is not None:
                beam = [(kg.ENTITIES[i], float(v[i]))
                        for i in np.argsort(-v, kind="stable") if v[i] > 0.0]
                trace.append((r, beam))
            # Atom + ⊤: v'[t] = max_h v[h] · M_r[h,t]  (max-merge of beams).
            v = (v[:, None] * M[kg.R_ID[r]]).max(axis=0)
        return v

홉 줄은 2p 목적함수 그대로입니다. v[:, None] * M[kg.R_ID[r]]는 곱 $v[h] \cdot M_r[h,t]$ 의 $13 \times 13$ 배열을 만들고, .max(axis=0)은 선행 개체 $h$ 에 대해 최대화하여 같은 꼬리에 도달하는 빔들을 병합합니다. 구체적 개체 빔이 주는 보상은 해석 가능성입니다. 탐색 상태는 이름과 점수를 가진 짧은 개체 목록이며, 커밋된 실행은 2p 질의에 대해 이를 출력합니다:

[2] CQD-Beam trace (k=4, product t-norm) — 2p query:
  q(x) = EXISTS y. advises(alice, y) AND advises(y, x)
  hop 1 (advises ) beam in : alice:1.000000
  hop 2 (advises ) beam in : bob:1.000000, cmu:0.000043, p1:0.000028, carol:0.000026
  final scores (top 3 of 13):
    carol    1.000000   easy answer
    dave     0.000411   HARD answer
    alice    0.000027   non-answer
  dave's score is exactly M[advises][bob, dave] = 0.000411: the pinned
  alice->bob hop costs nothing, the imputed bob->dave hop is the whole price.

숫자를 따라가 봅시다. 홉 1이 끝나면 구속 변수 $y$ 에 대한 빔은 정확히 1.000000인 bob(고정된 엣지 alice → bob)과 거의 0에 가까운 낙오자 셋을 담고 있습니다. 홉 2가 끝나면 어려운 답 dave는 $1.000000 \times 0.000411 = 0.000411$ 로 점수가 매겨집니다. 곱 t-노름 아래에서는 관측된 홉이 공짜이고 채워 넣은 홉이 값을 전부 치르므로, dave의 최종 점수가 단일 행렬 항목 $M_{\mathrm{advises}}[\mathrm{bob}, \mathrm{dave}]$ 와 같은 것은 바로 그 때문입니다(cqd.py 352–353행에서 단언됨).

이제 탐욕성이 어떤 실패 양상을 사는지 유도해 봅시다. 어떤 답 $x^{\ast}$ 의 진짜 최선의 증인이 중간 개체 $y^{\ast}$ 인데, 그 점수가 절단 시점에 $k$ 번째 생존자보다 낮은 순위라고 합시다. _truncate(cqd.py 135–143행)는 $v[y^{\ast}]$ 를 0으로 만들고, 이후의 모든 값은 오직 살아남은 벡터로부터만 계산됩니다. 홉은 $\max_h v[h] \cdot M_r[h,t]$ 를 읽는데, 0이 된 $v[y^{\ast}]$ 는 그 최댓값에 $0 \cdot M_r[y^{\ast}, t] = 0$ 만을 기여합니다. 재귀가 결코 되돌아가지 않으므로, 어떤 나중의 증거도 잘려 나간 결속을 되살릴 수 없습니다. 답 $x^{\ast}$ 는 이제 자신이 가진 최선의 살아남은 증인을 타야 하는데, 그 점수는 0에 임의로 가까울 수 있습니다. 가지치기는 되돌릴 수 없으며, 오류는 사슬을 따라 누적됩니다. 커밋된 실행은 놓침을 보이지 않습니다. 13개 개체에서는 모든 어려운 답의 증인이 모든 $k = 4$ 빔의 꼭대기에 오릅니다. 아홉 사례 가운데 여덟 사례에서는 증인이 결정적인 홉에 정확히 1.0으로 들어옵니다(1p와 2i 답에서는 앵커의 원-핫 벡터이고, 2p와 pi에서는 고정된 엣지 접두사입니다). 교집합이 마지막 홉보다 앞에 오는 ip 질의에서는 증인 p1이 겨우 0.000260으로(고정된 alice 저술 원자에 채워 넣은 bob 저술 엣지를 곱한 값) about 홉의 빔에 들어오지만 그래도 자신의 빔을 이끌며, 차점자는 0.000015로 점수가 매겨집니다. 그러므로 $k = 4$ 빔과 정확한 최적값은 순위 대 순위로 동점입니다. 여기서 정확성이 무엇을 보장하는지는 정밀하게 말해야 합니다. 절단은 음이 아닌 벡터의 항목을 낮출 수만 있고, 그 위의 모든 연산자(곱과 최댓값)는 입력에 대해 단조적이므로, 각 개체에 대한 빔의 최종 점수는 QTO의 점수 이하입니다. 즉 정확한 점수는 빔 점수를 항목별로 지배합니다. 그러나 점수 지배만으로 순위 지배가 따라오지는 않습니다. 빔이 정답이 아닌 개체의 최선 증인을 잘라 그 경쟁자의 점수를 낮추면, 어려운 정답은 정확한 DP에서보다 빔에서 엄격히 더 좋은 순위를 받을 수도 있습니다. 따라서 MRR에 대한 QTO ≥ 빔 순서는 정리가 아니라 이 질의 뱅크에서의 경험적 사실이며, cqd.py 381행은 바로 그런 사실로서 이를 단언합니다. 여기서는 둘이 정확히 동점입니다. 후보가 수천 개이고 고정된 접두사가 거의 없으며 $k \ll \lvert V \rvert$ 인(빔 폭이 개체 수 $\lvert V \rvert$ 보다 훨씬 작은) 현장 규모에서는 그 절단이 진짜로 물어뜯으며, 그 비용은 QTO가 발표한 비교가 정량화하고 커밋된 표를 다루는 절에서 인용합니다 [2]. CQD 논문은 구체적 개체 위에서 탐색하는 대신 경사 상승법으로 구속 변수의 완화된 임베딩을 최적화하는 연속 변형도 제공합니다 [1].

퍼지 집합 읽기: 모든 것을 유지하기

명백한 수선책은 절단을 멈추는 것입니다. DAG의 모든 노드에서 전체 소속 벡터 $v \in [0,1]^{13}$ 를 유지합니다. 항목 $v[e]$ 는 개체 $e$ 가 그 노드의 답 집합에 속하는 퍼지 정도입니다. 이것이 바로 GNN-QE가 자신의 시스템을 세우는 실행기입니다 [3]. 질의는 관계 투영과 퍼지 집합 연산으로 분해되며, 교집합은 항별 곱이고, 합집합은 확률적 합 $1 - \prod_i(1 - v_i)$ 이며, 부정은 여집합 $1 - v$ 이고, 투영은 하나의 퍼지 집합을 그 관계 아래의 퍼지 상(image)으로 사상합니다. 우리의 축소판에서는 그 퍼지 상이 행렬을 통과합니다, $v'[t] = \max_h v[h] \cdot M_r[h,t]$ . 그리고 이 읽기는 말 그대로 빔을 $V$ 전체로 넓힌 cqd_beam입니다. $k = \lvert V \rvert = 13$ 에서는 절단이 항등 사상이 되어 아무것도 잘리지 않으며, 모듈은 전체 폭 빔이 뱅크의 모든 질의에서 정확한 동적 계획법과 $10^{-12}$ 이내로 일치한다고 단언합니다(cqd.py 326–330행):

    # -- QTO ≡ CQD-Beam at full width: the exact DP is the k=|V| beam.
    for t in TYPES:
        for q in QUERY_BANK[t]:
            gap = np.abs(cqd_beam(q, M, k=N_E) - qto_forward(q, M)[0]).max()
            assert gap < 1e-12, f"beam(k=13) diverged from the exact DP: {gap}"

결과는 두 가지, 하나는 반갑고 하나는 값비쌉니다. 반가운 쪽은 점검 가능성(inspectability)입니다. 모든 중간 상태는 정도가 매겨진 개체 전부의 순위 목록이므로, 디버깅 세션은 질의의 어느 지점에서든 모델이 무엇을 믿고 있는지 출력할 수 있습니다. 커밋된 트레이스가 "final scores (top 3 of 13): carol 1.000000, dave 0.000411, alice 0.000027"을 출력한 그대로입니다. 이를 중간 상태가 어떤 개체의 이름도 대지 않는 베타 분포 매개변수 벡터인 BetaE와 견주어 보십시오. 값비싼 결과는 이제 모든 노드가 $\lvert V \rvert$ 크기의 조밀한 상태를 지녀야 한다는 것입니다. 13개 개체에서는 13개의 부동소수점 수이지만, 15,000개 개체에서는 질의당 노드당 15,000개가 되며, 투영의 행렬 형태는 관계마다 $\lvert V \rvert \times \lvert V \rvert$ 가 필요해집니다. 실제 규모에서 GNN-QE의 답은 투영을 학습하는 것입니다. 그래프 신경망(3권이 마무리 지은 것과 같은 관계형 메시지 전달 계열인 NBFNet의 계보에 속합니다)이 현재의 퍼지 집합과 관계를 받아 다음 퍼지 집합을 직접 만들어 내며, 구체화된 행렬은 필요 없습니다 [3]. 이것이 무엇을 다시 들여오는지는 정확히 짚어야 합니다. GNN-QE의 학습 가능한 매개변수는 전부 그 구조에 무관한 투영 연산자 안에 있습니다(그 위의 퍼지 연산들은 매개변수 없는 대수이므로, 학습할 구조별 연산자가 아예 존재하지 않습니다). 그러나 발표된 시스템은 그 투영기를, 1홉 링크만이 아니라 정답 집합이 딸린 표집된 다중 홉 질의 위에서 끝에서 끝까지 맞춥니다. 즉 지워지는 것은 질의 구조 매개변수이지, 질의 수준의 지도(supervision)가 아닙니다. 임베딩 쪽에서 더 강한 무학습 주장을 입증하는 것은 오히려 FuzzQE입니다. 논리곱, 논리합, 부정이 구성상 논리 법칙을 만족하는 t-노름 연산자인 질의 대수는, 순수한 1홉 링크 예측만으로 훈련되고도 여전히 경쟁력 있게 복합 질의에 답할 수 있습니다 [4]. 이 실행기를 잘 챙겨 두십시오. 파운데이션 모델 장은 ultra_lite.py의 전이 가능한 투영기를 정확히 이 퍼지 집합 루프에 꽂아 넣습니다.

QTO: 질의 트리 위의 정확한 최댓값-곱 동적 계획법

QTO는 가지치기 없는 읽기를 논리적 결론까지 밀어붙입니다. 질의 DAG가 트리라면(각 구속 변수가 정확히 하나의 부모로 흘러 들어가며, 이는 우리 뱅크의 다섯 유형 전부에서 성립합니다), 퍼지 목적함수는 동적 계획법으로 다항 시간 안에 정확히 최대화될 수 있고, 그 최대화 배정은 나중에 되찾을 수 있습니다 [2]. 두 주장 모두 유도해 볼 가치가 있습니다.

왜 트리가 정확한 DP를 허락하는가. 음이 아닌 수들의 최댓값과 곱셈에 관한 두 가지 기초적인 사실이 모든 일을 해냅니다. 첫째, 음이 아닌 상수는 최댓값 바깥으로 빼낼 수 있습니다. $c \ge 0$ 이면 모든 $z$ 에 대해 $c \cdot f(z) \le c \cdot \max_z f(z)$ 이므로, 왼쪽의 최댓값은 오른쪽보다 크지 않습니다. 그리고 이 상계는 $f$ 의 최대화 지점에서 달성되므로,

\max_z \, c \cdot f(z) \;=\; c \cdot \max_z f(z).

둘째, 서로소인 변수 블록에 걸친 최댓값은 곱셈에 걸쳐 인수분해됩니다. $f \ge 0$ 이 오직 블록 $z_1$ 에만, $g \ge 0$ 이 오직 $z_2$ 에만 의존한다면, 모든 결합 선택에 대해 $f(z_1)\, g(z_2) \le \big(\max_{z_1} f\big)\big(\max_{z_2} g\big)$ 이며, 등호는 두 블록 각각의 최대화 지점을 짝지음으로써 달성되므로,

\max_{z_1, z_2} \, f(z_1)\, g(z_2) \;=\; \Big(\max_{z_1} f(z_1)\Big) \cdot \Big(\max_{z_2} g(z_2)\Big).

이제 질의 트리의 각 노드 $u$ 에 대해 벡터 $T^{\ast}_u[e]$ 를 정의합니다. $u$ 자신의 변수를 개체 $e$ 로 고정한 채, $u$ 보다 엄격히 아래에 있는 구속 변수들의 모든 배정에 걸친 부분트리 원자 진리값들의 곱의 최댓값입니다. 트리 구조는 이 벡터를 아래에서 위로 계산할 수 있게 해 줍니다. 앵커에는 그 아래에 아무것도 없으므로 $T^{\ast}$ 는 원-핫 벡터입니다. 자식 $c$ 에서 부모 $u$ 로 향하는, 관계 $r$ 에 대한 투영 홉에서는, 부분트리의 원자들이 자식 부분트리의 원자들에 새로운 원자 $M_r[h, t]$ 를 곱한 것입니다. 고정된 머리 후보 $h$ 에 대해, 인수 $M_r[h,t]$ 는 더 깊은 변수들에 대해 음이 아닌 상수이므로, 첫 번째 사실에 의해 안쪽의 최댓값은 $T^{\ast}_c[h]$ 로 붕괴되고, 새로 결속된 $h$ 에 대해 최대화하면 다음을 얻습니다:

T^{\ast}_u[t] \;=\; \max_{h \in V} \; T^{\ast}_c[h] \cdot M_r[h, t].

교집합 노드에서는 가지들이 오직 그 노드 자신의 변수만을 공유하므로, 그 구속 변수 블록들은 서로소입니다. 두 번째 사실에 의해 결합 최댓값은 가지별 최댓값들의 곱으로 인수분해됩니다, $T^{\ast}_u[e] = \prod_i T^{\ast}_{c_i}[e]$ . 이 서로소성이야말로 정확히 트리는 보장하지만 일반적인 DAG는 보장하지 않는 것입니다. 만약 같은 구속 변수를 두 가지가 공유한다면, 곱셈이 그 블록들을 결합시켜 버려서 이 인수분해는 거짓이 될 것입니다. 이 재귀가 qto_forward(cqd.py 200–237행)이며, 그 사슬 경우는 역방향 패스가 필요로 할 홉 이전 벡터들을 메모이제이션합니다(222–231행). 복잡도는 이렇습니다. 홉 하나는 $\lvert V \rvert^2$ 번의 곱셈-최댓값 연산이 들므로, 원자 $p$ 개짜리 질의는 $p \lvert V \rvert^2$ 정도의 연산, 즉 $O(p \lvert V \rvert^2)$ 이 드는데, 이는 무작정 열거하는 $\lvert V \rvert^{\text{(구속 변수의 개수)}}$ 개의 접지와 대비됩니다. 곱셈이 최댓값에 분배되기(위에서 유도한 바로 그 두 사실 덕분에) 때문에 지수가 이차로 바뀌었고, 이것이 최댓값들을 중첩할 수 있게 해 줍니다. 가중 모델 계수 장의 반환(semiring) 어휘로 말하면, 이 DP는 최댓값-곱 반환 위에서 돌아가며, 분배 법칙이 바로 그것을 허가하는 법칙입니다.

역방향 argmax 패스. 순방향 유도의 각 붕괴가 특정한 최대화 지점에서 달성되는 등식이기 때문에, 그 등식들을 거꾸로 실행하면 그 원자들의 곱이 순방향 점수와 같은 증인 할당을 되찾을 수 있습니다. 목표를 어떤 답 $t$ 에 결속한 다음, 각 사슬을 오른쪽에서 왼쪽으로 걸으며, 매 홉마다 최댓값을 달성한 머리를 고릅니다(cqd.py 263–272행):

    t = t_idx
    hop_atoms: list = []
    for r, v_before in zip(reversed(memo["rels"]), reversed(memo["before"])):
        # Eq. 13:  h = argmax_j T*_before[j] · M_r[j, t]
        h = int(np.argmax(v_before * M[kg.R_ID[r], :, t]))
        hop_atoms.append((kg.ENTITIES[h], r, kg.ENTITIES[t],
                          float(M[kg.R_ID[r], h, t])))
        t = h
    atoms.extend(reversed(hop_atoms))  # report atoms anchor-outward
    qto_backward(memo["child"], M, t, atoms)

교집합에서는 모든 가지가 부모의 개체를 물려받아 자신만의 사슬을 추출합니다. 출력은 각각 자신의 행렬 값을 지닌 접지 원자들의 목록입니다. 즉 충실한 증명(faithful proof)이며, 나열된 값들의 곱이 근사가 아니라 정확히 답의 점수와 같다는 정밀한 의미에서 그렇습니다. 커밋된 실행은 pi 질의의 어려운 답에 대해 이를 하나 추출합니다:

[3] QTO-lite: exact forward max-product DP + backward argmax proof — pi query:
  q(x) = [EXISTS y. advises(alice, y) AND advises(y, x)] AND advises(bob, x)
  forward T*(x) (top 3 of 13):
    carol    1.0000e+00   easy answer
    dave     1.6867e-07   HARD answer
    alice    3.9755e-11   non-answer
  backward proof for the HARD answer dave (every atom checked against the graph):
    alice --advises--> bob   M = 1.000000   edge-valid: True   TRAIN edge (pinned 1.0)
    bob --advises--> dave   M = 0.000411   edge-valid: True   held-out TEST edge (imputed!)
    bob --advises--> dave   M = 0.000411   edge-valid: True   held-out TEST edge (imputed!)
  product of proof atoms = 1.6867e-07 = T*(dave) — the proof IS the score,
  and it names the held-out edge (bob, advises, dave) it imputed.

모듈이 하듯 엣지 하나하나까지 검사해 봅시다(cqd.py 355–366행). 사슬 가지는 $y$ 를 bob으로 접지하여 alice → bob(고정, 1.0)을 탄 다음 bob → dave(채워 넣음, 0.000411)를 탑니다. 직접 가지는 자신의 단일 원자를 같은 bob → dave 엣지로 접지합니다. 모든 원자는 전체 그래프의 실제 엣지이며, 채워 넣은 것은 정확히 제외해 둔 테스트 엣지입니다. 산술을 정직하게 지키기 위한 정밀도 참고 사항이 하나 있습니다. 트레이스는 각 원자를 소수점 여섯째 자리로 반올림해 출력하는데, 반올림된 0.000411을 제곱하면 출력된 점수가 아니라 $1.6892 \times 10^{-7}$ 이 나옵니다. 완전 정밀도에서 채워 넣은 항목은 $4.106935 \times 10^{-4}$ 이며, $1.0 \times (4.106935 \times 10^{-4})^2 = 1.6867 \times 10^{-7}$ 은 마지막으로 출력된 자릿수까지 $T^{\ast}(\mathrm{dave})$ 를 재현하며, 모듈은 완전 정밀도의 곱이 $10^{-15}$ 이내임을 단언합니다(cqd.py 361행). 이 증명이 함께 고백하는 것도 눈여겨보십시오. 같은 불확실한 엣지가 가지마다 한 번씩 두 번 청구되므로, 점수는 그 엣지 진리값의 제곱입니다. 확률적 의미론이라면 그 엣지가 성립하는 하나의 세계에 조건화하여 그것을 한 번만 셀 것입니다. 가중 모델 계수 장이 정확히 그 기계 장치를 지었습니다. 곱 t-노름은 확률이 아니며, 충실한 증명은 바로 그 차이를 산술 속에서 보게 해 주는 것입니다.

축소판 따름정리. QTO의 고정은 겉치레가 아니라 하나의 보장을 지니고 있습니다. 만약 어떤 답이 쉬운 답이라면(관측된 엣지만으로 도출 가능하다면), 그 증인이 되는 접지는 오직 고정된 원자들만을 사용하므로 순방향 점수는 정확히 1인 값들의 곱, 곧 1이 됩니다. 그리고 모든 행렬 항목이 최대 1이므로 어떤 점수도 1을 넘을 수 없어, 쉬운 답은 정확히 꼭대기에 자리 잡습니다. 이와 대조적으로 답이 아닌 개체는 전체 그래프 위에 아무런 접지도 갖지 못하므로, 그것이 내놓는 모든 접지는 적어도 하나의 관측되지 않은 원자를 사용하고, 그 각각은 $1 - \delta$ 에서 상한이 매겨져, 점수는 쉬운 답들보다 엄격히 낮은 $1 - \delta$ 로 제한됩니다. 그러므로 증명 가능한 답은 언제나 1등으로 순위 매겨집니다. 기호적 기준선은 신경망의 이득을 위해 결코 희생되지 않습니다. 모듈은 이를 논문의 따름정리로서 뱅크 전체에 걸쳐 정량화하여 진술하고 검사합니다(cqd.py 332–344행):

    # -- QTO never misses an EASY answer (Corollary 3.3).  Precisely: for
    #    every query in the 5-type bank, every easy answer's witnessing
    #    grounding uses only pinned-to-1 TRAIN edges, so its forward score is
    #    EXACTLY 1.0; and every non-answer needs at least one non-observed
    #    atom, each capped at 1-δ, so it scores ≤ 1-δ.  Hence every easy
    #    answer ranks strictly ahead of every non-answer: rank 1, never missed.
    for t in TYPES:
        for q in QUERY_BANK[t]:
            T_star, _ = qto_forward(q, M)
            assert all(T_star[kg.E_ID[e]] == 1.0 for e in easy_answers(q)), \
                f"QTO missed an easy answer of a {t} query"
            non = sorted(V - all_answers(q))
            assert max(T_star[kg.E_ID[e]] for e in non) <= 1.0 - DELTA + 1e-12

이는 이 권이 되풀이하는 건전성 패턴이 새 옷을 입은 것입니다. 고정된 엣지는 기호적 바닥이고, 채워 넣은 항목은 그 위로 뻗은 신경망의 손길이며, 이 정리는 그 손길이 결코 바닥을 무너뜨리지 않는다고 말합니다 [2].

커밋된 표, 정직하게 읽기

이 장의 평결은 표 하나입니다. 필터링된 MRR(mean reciprocal rank, 평균 역순위: 각 어려운 답에 대해 답이 아닌 것들 사이에서 그 순위 분의 1을 구해 평균한 것; 1.0은 모든 어려운 답이 1위로 순위 매겨졌다는 뜻입니다)을, 이 부의 필터링된 프로토콜(query_dag.py 367–408행) 아래에서 뱅크의 어려운 답 9개에 대해 다섯 점수 매김기별로 나타냅니다:

[4] hard-answer MRR on the 5-type bank (filtered, query_dag protocol, 9 hard answers)
  model                              1p       2p       2i       pi       ip   pooled
  G_train traversal (symbolic)   0.1484   0.1484   0.1429   0.1484   0.1429   0.1465
  random scorer (seed 0)         0.2250   0.1010   0.1125   0.5625   0.1000   0.2336
  CQD-Beam (k=4)                 0.5500   0.5500   1.0000   1.0000   1.0000   0.8000
  QTO-lite (exact DP)            0.5500   0.5500   1.0000   1.0000   1.0000   0.8000
  G_full oracle (gold ceiling)   1.0000   1.0000   1.0000   1.0000   1.0000   1.0000

표를 한 행씩 정직하게 읽어 봅시다. 훈련 그래프의 기호적 순회는 0.1465에 모입니다. 이는 잘못 지어져서가 아니라, 모든 어려운 답에서 정의상 0점을 받기 때문입니다(어렵다는 것은 "제외해 둔 엣지를 채워 넣어야 한다"는 뜻입니다). 그러므로 그 0이 아닌 MRR은 순전히 동점 처리 잡음입니다. 무작위 점수 매김기의 0.2336은 아무 정보도 없는 바닥입니다. 두 무학습 답변기는 모두 0.8000에 모이며, 모듈은 눈대중이 아니라 순서 주장을 단언합니다. QTO는 자신이 상계로 삼는 빔과 적어도 같으며, 둘 다 무작위보다 0.2 넘게 앞서고, QTO는 순회보다도 같은 폭으로 앞섭니다(cqd.py 379–387행). 이 규모에서 빔에 대한 QTO의 보장은 승리가 아니라 동점이며, 그 이유는 정확히 말해 둘 가치가 있습니다. 모든 어려운 답의 증인이 모든 k = 4 빔의 꼭대기에 오르는데, 아홉 건 중 여덟 건은 정확히 1.0인 고정된 접두사를 타고 가고, ip 질의의 경우에는 채워 넣은 bob 저술 엣지를 거쳐 0.000260으로 자신의 빔을 이끌기 때문에, 빔은 정확한 DP가 필요로 하는 것을 결코 가지치기하지 않습니다. 이 보장이 뜻하는 것은 QTO가 결코 더 나쁠 수 없다는 것이며, 현장 규모의 숫자는 빔이 실제로 놓칠 때 그 보장이 무엇을 값하는지 보여 줍니다. 먼저 보고 관례 하나를 짚어 둡시다. 발표된 벤치마크는 MRR에 100을 곱해 인용하므로, 보고된 74.0은 이 장의 0에서 1 사이 척도로는 0.740입니다. 표준 벤치마크 지식 그래프인 FB15k에서 QTO의 정확한 최적화는 아홉 개 EPFO 질의 유형에 대해 평균 74.0을 기록하여 CQD-Beam의 58.2에 맞섭니다 [2]. 가지치기의 비용이 측정 가능해진 것입니다. 그리고 FB15k에서 파생된 더 어려운 벤치마크인 FB15k-237에서 QTO는 33.5를 보고하는데, 이는 BetaE의 20.9, GNN-QE의 26.8에 맞선 숫자입니다 [2]. 보정된 1홉 진리값 위의 정확한 최적화기가 그 시대의 모든 훈련된 질의 인코더를 이기며, 이는 이 장 서두의 도발이 논제에서 측정으로 격상된 것입니다.

우리에게 남은 0.2는 어디로 갔을까요? 1p와 2p 열을 보십시오. 각각 0.5500이고, 각 열은 정확히 두 개의 어려운 답을 평균하므로, 산술이 순위 1 하나와 순위 10 하나를 강제합니다. $(1/1 + 1/10)/2 = 0.55$ 이기 때문입니다. 순위 1인 답은 dave이며, 우리는 그 채워 넣은 advises 엣지가 경쟁자들을 압도하는 것을 지켜보았습니다. 순위 10인 답은 $\mathrm{authored}(\mathrm{bob}, x)$ 아래의 p1입니다. bob에 대한 보정된 authored 행은 논문조차 아닌 개체들에 자신의 질량을 두며, 제외해 둔 그 논문은 10등에 안착합니다. 탐욕적이든 정확하든 두 실행기 모두 그 순위를 똑같이 물려받는데, 결함이 논리 층이 아니라 원자 층에 있기 때문입니다. 아무리 정확한 최적화를 해도 잘못 보정된 행렬을 고칠 수는 없으며, 이것이 바로 보정 정직성 참고 사항이 예고했던 실패입니다. 또한 교집합이 도움이 되었다는 점도 눈여겨보십시오. 2i, pi, ip는 모두 1.0000에 자리하는데, 곱 t-노름이 어느 가지에서든 실패한 후보를 벌하여 원자 층의 잡음을 걸러 내기 때문입니다.

마지막으로 계산 장부를 봅시다. 13개 개체는 15,000개가 숨기지 못하는 것을 숨기기 때문입니다. 여기서 신경 인접 행렬은 845개의 부동소수점 수로 이루어진 조밀한 $5 \times 13 \times 13$ 배열이며, 한 번만 미리 계산됩니다. 지식 그래프 규모에서는 같은 객체가 관계마다 하나씩인 $\lvert V \rvert \times \lvert V \rvert$ 행렬이 됩니다. 개체 15,000개라면 희소화 이전에 관계당 $2.25 \times 10^{8}$ 개의 항목이 되며, QTO는 오직 0에 가까운 항목을 문턱값으로 걸러 희소 저장소로 만듦으로써만 배포됩니다 [2]. 정확성은 이차 메모리로 사들이고, 빔은 증인을 가지치기할 위험으로 사들이며, 이 분야는 현재 그 거래를 질의마다 결정합니다. 그리고 그 모든 것 아래에 있는 원자 점수 매김기는 시종일관 같은 1홉 일꾼입니다. 3권 이래로 바뀌지 않은 ComplEx이며, 그것이 발표한 전체 기여는 더 나은 단순한 링크 예측기였습니다 [5]. 그러므로 "무학습"은 오직 그 수식어가 붙어야만 정직합니다. 질의 수준에서의 무학습입니다. 예측기는 훈련되어 있고, 보정은 훈련 그래프에 맞춰져 있습니다. 사라진 것은 질의 구조 훈련이며, 그것이 바로 앞 장이 자신의 모든 매개변수를 쏟아부었던 조각입니다.

아직 풀리지 않은 부분

이 장의 모든 것은 하나의 고리에 매달려 있습니다. 보정된 진리값입니다. 최적성 정리도, 충실한 증명들도, 쉬운 답에 관한 따름정리도, 모두 $M_r$ 을 가지고 계산하는 것에 대한 진술이며, 커밋된 표는 잘못 보정된 행 하나가 두 실행기 모두에게 아홉 개의 순위를 물어 가는데도 어떤 정확성으로도 되사지 못하는 것을 보여 주었습니다. 이것을 공학적 잡무가 아니라 열린 문제로 만드는 것은 개방 세계입니다. 보정이란 예측된 확신을 진리의 빈도와 맞추는 일인데, 지식 그래프의 빠진 엣지들은 레이블이 없으므로 진리의 빈도 자체가 관측되지 않습니다. 5권의 보정 장이 이를 중심 질문으로 다룹니다. 부정은 이 고리를 더 무겁게 만듭니다. 여집합 $1 - x$ 는 지나치게 확신에 찬 틀린 0.3을 확신에 찬 틀린 0.7로 보내므로, 잘못된 보정은 그저 물려받는 데서 그치지 않고 뒤집힙니다. 부정을 지닌 질의 유형이 바로 퍼지 실행기가 가장 먼저 무너지는 곳입니다. 앞 절에서 풀이한 100을 곱하는 현장 척도로, FB15k-237에서 QTO의 부정 유형 평균 MRR은 15.5로 자신의 EPFO 평균 33.5에 못 미치고, GNN-QE는 26.8에 대해 10.2입니다 [2], [3]. 그리고 빔의 속도와 DP의 보장 사이에는 이 분야가 아직 닫지 못한 시스템 질문이 놓여 있습니다. 예산 아래에서 빔을 넓혀 가다가 중단되는 시점에 정확한 최적값으로부터 자신이 아직 얼마나 떨어져 있을 수 있는지에 대한 공인된 상계를 보고하는 애니타임(anytime) 알고리즘입니다. 지금의 도구 상자 어디에도 그런 보증서는 없습니다.

왜 중요한가

이 장은 이 권의 제목이 말하는 바를 가장 순수하게 보여 주는 표본입니다. 여기서 논리는 손실이 되지 않았습니다. 훈련된 모델이 오직 원자만을 공급하는 가운데, 논리 그 자체가 추론 엔진이 되었습니다. 이 노동의 분업 덕분에 각 조각을 따로따로 감사할 수 있었습니다. 대수는 유도로(트리 DP는 정확하며, 최댓값-곱 대수 네 줄로 증명됩니다), 원자는 측정으로(잘못된 행 하나를 찾아내 이름 붙였습니다), 인터페이스는 구성으로(고정된 엣지가 기호적 바닥을 보장합니다) 감사되었습니다. 충실한 증명은 5권이 가장 무겁게 기댈 부분입니다. "dave입니다. alice가 bob을 지도하고 bob이 dave를 지도하기 때문이며, 저는 두 번째 엣지를 0.000411로 채워 넣었습니다"라고 답하는 시스템은 순위를 특정 엣지들에 관한 감사 가능한 주장으로 바꾸어 놓았으며, 이것이 바로 신뢰의 원재료입니다. 이차 메모리 장부와 애니타임 간극은 규모의 질문이고, 능력을 잘 보정된 기반 위의 추론으로 다시 규정하는 이 재구성 자체가, V부의 나머지와 다음 권이 계속 시험할 연구상의 내기입니다.

핵심 용어

무학습 CLQA(training-free complex logical query answering) — 표집된 복합 질의 위의 훈련 없이, 사전 훈련된 1홉 링크 예측기와 고정된 퍼지 논리 합성 층만으로 다중 홉 논리 질의에 답하는 것입니다. CQD가 도입했습니다 [1].
신경 인접 행렬(neural adjacency matrix) $M_r$ — 관계 $r$ 마다, 보정된 원자 진리값들의 행렬 $M_r[h,t] \in [0,1]$ 입니다. 후보 꼬리에 대한 소프트맥스를 관측된 꼬리 개수로 다시 스케일링하고, $1-\delta$ 에서 상한을 매기며, 관측된 훈련 엣지는 정확히 1로 고정합니다 [2].
보정(calibration) — t-노름 합성이 의미를 갖게 만들기 위해 예측기의 원점수를 $[0,1]$ 로 단조롭게 다시 스케일링하는 것입니다. 이후의 모든 보장에 소리 없이 걸리는 상한입니다.
질의의 퍼지 최적화 읽기 — 각 후보 답의 진리값은 구속 변수들의 배정에 걸친 원자 진리값들의 곱의 최댓값입니다. $\wedge$ 는 곱 t-노름이고, $\exists$ 는 최댓값이며, $\vee$ 는 확률적 합이고, $\neg$ 는 여집합 $1-x$ 입니다.
빔 폭(beam width) $k$ — CQD-Beam이 구속 변수마다 유지하는 구체적 후보 개체의 수입니다. 잘려 나간 증인은 되찾을 수 없으며, 이는 빔이 유도적으로 지니는 실패 양상입니다.
소속 벡터(membership vector, 퍼지 집합) — 가지치기 없는 실행기가 질의 노드마다 유지하는 상태로, 개체마다 $[0,1]$ 안의 정도 하나씩이며 순위 목록으로 점검할 수 있습니다. GNN-QE의 표현 방식이며, 실제 규모에서는 그래프 신경망이 행렬 투영을 대신합니다 [3].
최댓값-곱 동적 계획법(max-product dynamic programming) — 트리 모양 질의에 대한 QTO의 정확한 평가입니다. 상수는 최댓값 바깥으로 빠지고 서로소인 변수 블록은 곱셈에 걸쳐 인수분해되므로, 아래에서 위로의 국소적 단계들이 $O(p\lvert V\rvert^2)$ 에 전역 최적값을 계산합니다.
충실한 증명(faithful proof, 역방향 argmax) — 각 순방향 최댓값을 argmax로 다시 실행하여 되찾는 증인이 되는 접지입니다. 그 원자 값들의 곱은 답의 점수와 정확히 같으며, 각 원자는 그래프에 대해 검사할 수 있습니다.
쉬운/어려운 답(easy/hard answers) — 쉬운 답은 관측된 엣지만으로 도출 가능합니다(고정을 통해 QTO는 언제나 이를 1위로 순위 매깁니다). 어려운 답은 제외해 둔 엣지 하나를 채워 넣어야 하며, 필터링된 MRR 프로토콜이 점수 매기는 것은 오직 이 답들뿐입니다.

이 장이 이끄는 곳

이 장의 모든 시스템은 여전히 자신의 원자 층을 질의를 받게 될 바로 그 그래프 위에서 훈련합니다. 3권의 ComplEx는 alice와 bob을 그들의 행으로 알고 있을 뿐이며, 새로운 개체와 새로운 관계를 가진 낯선 지식 그래프 위에서는 속수무책일 것입니다. 다음 장인 CLQA를 위한 파운데이션 모델은 그 마지막 의존성마저 없앱니다. ULTRA는 본 적 없는 어휘를 가진, 본 적 없는 그래프로 전이되는 관계 표현을 학습하며, UltraQuery는 정확히 이 장의 퍼지 실행기를 그 전이 가능한 투영기 위에 얹어, 사전 훈련된 모델 하나가 한 번도 본 적 없는 그래프 위에서 제로샷으로 복합 질의에 답하게 만듭니다. 논리 층은 바뀌지 않고 살아남으며, 이제는 원자 층이 일반화할 차례입니다.

동반 코드: examples/integration/cqd.py는 이 장 전체를 구현합니다. 3권의 ComplEx에 대한 845개 항목 대조 검사를 포함한 점수 표(77–96행과 307–312행), 상한과 고정을 갖춘 신경 인접 행렬(99–128행), 해석 가능한 트레이스를 갖춘 CQD-Beam(131–195행), 정확한 트리 DP와 역방향 증명 추출기(198–281행), 그리고 동치성, 따름정리, 증명의 충실성, 표의 순서를 지키는 역량 검사 단언들(326–387행)입니다. python3 examples/integration/cqd.py를 실행하면 이 장의 모든 숫자를 바이트 단위까지 재현할 수 있습니다. 그 실행은 다음으로 끝납니다: SUMMARY cqd: beam_mrr=0.8000 qto_mrr=0.8000 traversal_mrr=0.1465 random_mrr=0.2336 pinned=15 m_bob_adv_dave=0.000411 proof_atoms=3 proof_valid=True.

이 장에서 다루는 내용​

도발: 질의 수준 학습 없는 능력​

원자 층: 점수에서 보정된 진리값으로​

합성: 퍼지 최적화 문제로서의 질의​

CQD-Beam: 구체적 개체 위의 탐욕적 탐색​

퍼지 집합 읽기: 모든 것을 유지하기​

QTO: 질의 트리 위의 정확한 최댓값-곱 동적 계획법​

커밋된 표, 정직하게 읽기​

아직 풀리지 않은 부분​

왜 중요한가​

핵심 용어​

이 장이 이끄는 곳​