GPU 네이티브 NeSy: KLay와 Lobster

📍 현재 위치: 3부 · 미분 가능 프레임워크 — 11장. 로직 텐서 네트워크는 공리가 손실이 될 수 있도록 1차 논리를 텐서 위의 연산으로 다시 구성했습니다; 이 장은 의미론은 정확하게 유지한 채 기계 장치를 다시 짓습니다: 2부가 인증한 바로 그 추론을, 신경 절반과 같은 하드웨어 위를 달리는 행렬곱과 계층화된 배열 패스로 다시 배치합니다.

이 권에서 지금까지 등장한 모든 정확한 시스템은 조용한 각주 하나를 달고 있었습니다: 잘못된 하드웨어 위에서 돌아간다는 것입니다. 분포 의미론, 가중 모델 계수, 컴파일된 회로, 경사 세미링, 이 모두는 CPU(central processing unit, 중앙 처리 장치) 위에서 불규칙한 자료 구조를 포인터로 쫓아가는 재귀 프로그램으로 지어졌지만, 그것들이 통합하는 신경망은 GPU(graphics processing unit, 딥러닝이 돌아가는 가속기) 위에서 배치된 밀집 선형대수를 통해 질주합니다. 이 장은 의미론을 건드리지 않고 이 간극을 메웁니다. 검증할 주장은 아키텍처적입니다: 뉴로-심볼릭(NeSy, 이 장의 제목에 쓰인 약어) 시스템을 느리게 만든 것은 정확성이 아니라 메모리 레이아웃이었다는 것입니다. 우리 학계 세계에서 실제로 돌려 볼 수 있는 두 가지 텐서화가 이 논지를 증명합니다. 하나는 관계를 행렬로 바꾸어 규칙 적용을 행렬곱으로 만들고, 다른 하나는 컴파일된 회로를 계층으로 바꾸어 평가를 벡터화된 gather와 축약(reduction)의 나열로 만듭니다. 언어 수준에서 다루는 세 번째 시스템은 데이터로그 엔진 전체를 GPU 위로 낮춥니다.

쉽게 말하면

주문을 한 번에 하나씩 처리하는 창고를 상상해 보십시오. 피커 한 명이 주문서 한 장을 들고 선반으로 걸어가, 다른 선반을 가리키는 쪽지를 읽고, 그곳으로 걸어가고, 이런 식으로 주문이 완성될 때까지 반복합니다: 정확하지만 대부분 걷는 일입니다. 이제 같은 창고를 스테이징 열(row)로 재편성해 봅시다: 1단계에 필요한 모든 것이 1열에, 2단계에 필요한 모든 것이 2열에 놓이고, 천 장의 주문서를 실은 카트 전체가 그 열들을 함께 굴러 내려가며, 각 열은 한 번의 훑기로 처리됩니다. 물건 하나도 바뀌지 않았고 어떤 주문도 다르게 처리되지 않습니다; 오직 평면도만 바뀌었고, 걷는 일이 사라졌습니다. 그것이 이 장입니다. "주문"은 정확한 논리 질의이고, "다른 선반을 가리키는 쪽지"는 2부의 재귀적 평가자이며, 재편성된 평면도가 바로 TensorLog가 규칙에, KLay가 회로에 하는 일입니다.

이 장에서 다루는 내용

• 병목의 정확한 지목: 2부의 파이프라인(접지, 컴파일, 평가)은 정확하지만, 그 평가자들은 불규칙한 메모리 접근을 가진 재귀적 트리 순회이고, 신경 절반은 배치된 밀집 커널을 누리는데, 시스템적 질문은 정확한 논리가 같은 하드웨어를 탈 수 있는가입니다.
• 선형대수로서의 논리: 5개 관계 각각이 13×13 불리언 인접 행렬이 되고, 몸체 원자 하나가 행렬-벡터 곱이 되며, grandAdvisor = advises ∘ advises(∘는 관계 합성입니다: advises 엣지 하나를 따른 다음 또 하나를 따르는 것)는 그 지지 집합이 집합으로서 1권의 전방 연쇄 사실과 같다고 컴패니언이 증명하는 단일 행렬곱입니다.
• 행렬 관점이 사 오는 것과 감추는 것: 배치된 k-홉 도달 가능성과 미분 가능성을 공짜로 얻지만, 그 밑에는 행렬 항목이 증명-경로 개수이지 진리값이 아니라는 사실이 숨어 있어, 불리언 의미론에는 명시적 클램프가 필요하며 이는 두 가지 유도로 사실 위에서 다뤄집니다.
• 우리 자신의 회로 위에서 실행하는 KLay의 세 알고리즘: 노드 높이에 따른 계층화, 평탄한 정수 버퍼로의 텐서화, gather와 segment-reduce에 의한 평가로, 1000개의 가중치 벡터에 걸쳐 재귀적 가중 모델 계수와 1e-10까지 일치합니다.
• 제대로 다룬 로그 세미링: 긴 곱셈이 왜 언더플로하는지, 완전히 유도되고 잔차가 유계인 logsumexp max 트릭, 그리고 커밋된 선형-대-로그 일치가 1e-9라는 것.
• 정직한 벤치마크와 언어 수준: 있는 그대로로 짜인(GPU 이야기에 대한 NumPy 프록시로서) 실측 타이밍 표, Scallop의 데이터로그를 GPU로 낮추는 Lobster, 그리고 부상 중인 스택에서 어느 시스템이 어느 층을 소유하는지의 지도.

병목의 정확한 지목

2부가 실제로 지은 것을 떠올려 봅시다. 회로는 우리에게 접지, 컴파일, 평가 파이프라인을 주었습니다: 확률적 프로그램을 명제 논리식으로 접지하고, 이를 한 번에 매끄러운 결정론적 분해 가능 회로로 컴파일한 다음, 회로 크기에 선형이며 엣지당 세미링 연산 하나인 상향식 한 번의 패스로 모든 질의에 답합니다. 문제는 패스라는 단어에 있습니다. circuit.py(336–366행)의 평가자는 위상 정렬된 이질적 노드 튜플 목록을 순회하며, 메모리 곳곳에 흩어진 자식 색인을 따라가고, 방문할 때마다 노드 종류에 따라 분기합니다: 방문마다 포인터 역참조 하나, 분기 하나, 약간의 산술 연산 하나이며, 이는 정확히 현대 프로세서를 굶기는 접근 패턴입니다. 현대 프로세서의 속도는 예측 가능하고 연속적이며 폭넓은 읽기에서 나오기 때문입니다. 한편 신경 절반은 시간을 행렬곱에 씁니다: 밀집하고, 규칙적이고, 배치되어 있으며, 오직 그것만을 위해 지어진 하드웨어가 이를 처리합니다. DeepProbLog에서처럼 공동으로 학습시키면, 그 프로파일은 한쪽으로 완전히 쏠립니다: 지각 신경망은 가속기 시간으로 마이크로초 만에 배치를 끝내고, 그런 다음 파이썬 재귀가 회로를 한 번에 한 질의씩 평가하는 동안 기다립니다. 비용은 정확히 그 지점에 집중됩니다: 컴파일은 한 번만 치르는 대가이지만, 학습은 매 경사 하강 단계마다 컴파일된 회로를 다시 평가하며, 이렇게 반복되는 회로 평가는 현재의 뉴로-심볼릭 아키텍처가 지닌 주요 병목 중 하나로 지목되어 왔습니다 [1].

그래서 이 장의 시스템적 질문은 이것입니다: 의미론을 건드리지 않은 채로 정확한 추론을, 하드웨어가 말하는 어휘, 즉 배치된 밀집 배열 연산으로 다시 표현할 수 있는가? 발표된 두 답이 그렇다고 말하며, 스택의 서로 다른 두 층에서 그렇게 합니다. TensorLog는 규칙 수준에서 답합니다: 관계를 인접 행렬로 인코딩하면 데이터로그 규칙 적용이 행렬곱이 되고, 공짜로 미분 가능해집니다 [2]. KLay는 회로 수준에서 답합니다: 컴파일된 회로를 독립 노드들의 계층으로 재편성하면 평가가 벡터화된 gather와 분할된 축약(reduction)의 짧은 나열이 됩니다 [1]. 세 번째 시스템인 Lobster는 언어 수준에서 답하며, Scallop의 프로버넌스를 나르는 데이터로그 전체를 GPU로 낮춥니다 [3]; 앞의 두 답이 실행을 마친 뒤 우리는 이 시스템으로 돌아옵니다. 컴패니언 모듈 tensor_ops.py는 이 앞의 두 시스템을 학계 세계 위에서, 순수 NumPy로, 모든 의미론적 주장을 assert로 지켜 가며 축소 재현합니다; 이 모듈이 축소 재현할 수 없는 유일한 것은 실리콘 자체이며, 모듈은 그 사실을 그대로 말합니다.

나란히 놓인 두 텐서화: 왼쪽에서는 규칙 적용이 행렬곱 하나로 축약되고, 오른쪽에서는 회로 장에서 나온 같은 컴파일된 회로가 다섯 개의 평평한 계층으로 재편성되어 gather와 segment-reduce로 평가된다; 어느 쪽 이동도 답을 단 하나도 바꾸지 않는다.

저자가 AI의 도움을 받아 직접 제작한 원본 도해.

선형대수로서의 논리: 관계가 행렬이 되다

표기법부터 시작합시다. 3권 kg.py의 학계 지식 그래프는 13개의 개체(ENTITIES, kg.py 49행: alice, bob, carol, cmu, dave, erin, logic, mit, ml, nesy, p1, p2, p3, 정렬된 순서)와 18개의 주장된 엣지를 실어 나르는 5개의 기본 관계를 가지고 있습니다. $N$을 개체의 수라 쓰면 $N = 13$이고, 딕셔너리 E_ID(kg.py 53행)를 통해 모든 개체에 고정된 정수 색인을 부여합니다. 각 관계 $r$에 대해, 인접 행렬(adjacency matrix) $M_r$을 정의합니다. 이는 0과 1로 이루어진 $N \times N$ 배열로,

$$M_r[h, t] \;=\; \begin{cases} 1 & \text{사실 } (h, r, t) \text{가 주장되어 있으면,} \\ 0 & \text{그렇지 않으면,} \end{cases}$$

여기서 $h$는 엣지의 머리(출발) 개체를, $t$는 꼬리(도착) 개체를 색인합니다. 컴패니언은 트리플 저장소로부터 다섯 개 행렬 모두를 직접 짓습니다(tensor_ops.py 88–96행):

def rel_matrix(rel: str) -> np.ndarray:
    """The 13x13 0/1 adjacency matrix of one relation over the FULL graph
    (kg.TRIPLES — forward chaining runs on the full fact base, so the
    matmul must too):  M_r[E_ID[h], E_ID[t]] = 1  iff  (h, r, t) holds."""
    m = np.zeros((N_E, N_E))
    for h, r, t in kg.TRIPLES:
        if r == rel:
            m[kg.E_ID[h], kg.E_ID[t]] = 1.0
    return m

개체는 원-핫 벡터(one-hot vector)가 됩니다: $N$개의 숫자로 이루어진 행벡터이며, 그 개체의 색인 위치 한 곳만 1이고 나머지는 모두 0입니다. alice의 원-핫 행벡터를 $v_{\text{alice}}$라 씁시다. 이제 평범한 행렬 대수가 논리에 무엇을 하는지 보십시오. 행벡터와 행렬의 곱은 좌표별로 $(v M_r)[t] = \sum_{h} v[h]\, M_r[h, t]$로 정의되며, 이 합은 $N$개의 모든 머리 색인에 걸쳐 돕니다. $v = v_{\text{alice}}$일 때, $h \ne \text{alice}$인 모든 항은 사라지고, $(v_{\text{alice}} M_r)[t] = M_r[\text{alice}, t]$만 남습니다: 이 곱은 단순히 alice의 행을 읽어 낸 것이며, alice가 $r$-관계로 맺어진 모든 개체 위치에 1이 있는 벡터입니다. 논리적 용어로 말하면, $M_r$을 곱하는 것은 몸체 원자 하나를 적용하는 것입니다: "alice"라는 집합을 "alice가 $r$-관계를 맺는 모든 것"이라는 집합으로 사상합니다. 이것이 TensorLog의 창시적 관찰입니다: 모든 프롤로그 엔진의 안쪽 루프인, 사실 데이터베이스에 대한 단일화(unification)는 희소 행렬-벡터 곱이며, 따라서 몸체 원자들의 사슬은 그러한 곱들의 사슬입니다 [2].

이제 실행 규칙을 봅시다. 1권의 kb.py는 grandAdvisor를 혼 절 grandAdvisor(X, Z) :- advises(X, Y), advises(Y, Z)로 정의합니다. 기호 :-는 "만약"으로 읽습니다: 왼쪽의 머리(head)인 grandAdvisor(X, Z)는 오른쪽의 두 몸체 원자(body atom)인 advises(X, Y)와 advises(Y, Z)가 모두 성립할 때마다 성립합니다. 몸체 원자가 두 개이므로 곱도 두 번이지만, 결합법칙 덕분에 이를 먼저 하나의 행렬-행렬 곱으로 축약할 수 있습니다. $M_{\text{advises}}$를 자기 자신과 곱한 정의를 항목별로 펼쳐 보십시오.

$$\big(M_{\text{advises}}\, M_{\text{advises}}\big)[x, z] \;=\; \sum_{y=1}^{N} M_{\text{advises}}[x, y]\; M_{\text{advises}}[y, z].$$

각 항은 각각 0 또는 1인 두 항목의 곱이므로, 두 엣지가 모두 존재할 때, 즉 $y$가 advises$(x, y)$와 advises$(y, z)$ 둘 다 주장되어 있는 중간 인물일 때 정확히 1이 됩니다. 따라서 $y$의 모든 $N$가지 선택에 걸쳐 합산하면 $x$에서 $z$로 가는 advising 2-경로의 개수를 세는 셈입니다: 이 항목은 grandAdvisor$(x, z)$의 서로 다른 유도의 개수, 즉 규칙의 중간 변수 결속 하나당 하나씩입니다. 그래프에는 네 개의 advises 엣지가 있습니다: alice→bob, bob→carol, bob→dave, carol→erin. 두 홉을 거치는 alice의 행을 손으로 추적해 봅시다. 첫 홉: $v_{\text{alice}} M_{\text{advises}} = v_{\text{bob}}$, bob에서의 원-핫 행인데, bob이 alice가 지도하는 유일한 사람이기 때문입니다. 둘째 홉: $v_{\text{bob}} M_{\text{advises}} = v_{\text{carol}} + v_{\text{dave}}$, carol과 dave 위치에 1이 있는 벡터입니다. bob의 두 지도 대상이기 때문입니다. 그래서 제곱된 행렬의 alice 행에서 정확히 두 항목, carol과 dave가 켜지고, 각각 값이 1입니다(각각 2-경로가 하나씩). bob에서 같은 추적을 하면 carol을 거쳐 erin만 켜지고, 나머지 모든 사람에게서는 그 행이 0입니다. 합계 세 개의 0이 아닌 항목입니다.

이것이 정확히 1권의 전방 연쇄기가 유도한 것이며, 컴패니언은 이 우연을 검사 없이 넘기기를 거부합니다. 컴패니언은 이 곱을 계산하고, 그 지지 집합(support, 0이 아닌 값을 가지는 색인 쌍들의 집합으로, support(tensor_ops.py 99–102행)에 의해 개체 이름으로 복호화됩니다)을 읽어 들여 연쇄기가 유도한 사실들과 집합 동등성을 단언한 다음, 정의에 따른 경로-개수 오라클에 대해 모든 항목을 다시 유도합니다(tensor_ops.py 325–336행):

    # [a1] ONE matmul applies grandAdvisor(X,Z) :- advises(X,Y), advises(Y,Z).
    g2 = mats["advises"] @ mats["advises"]
    fc_grand = {(a[1], a[2]) for a in derived if a[0] == "grandAdvisor"}
    # THE claim: the product's support IS the forward chainer's derivation.
    assert support(g2) == fc_grand, "matmul support != forward-chain facts"

커밋된 실행은 판정을 배치의 보너스와 함께 출력합니다.

[2] one rule, one matmul: grandAdvisor(X,Z) :- advises(X,Y), advises(Y,Z)
      (M_advises @ M_advises)[x, z] = Σ_y M[x,y] M[y,z] = #advising 2-paths
      support of the product : [('alice', 'carol'), ('alice', 'dave'), ('bob', 'erin')]
      Volume 1 forward chain  : the SAME 3 grandAdvisor facts (asserted
      as exact set equality; every entry equals the 2-path count)   PASS
      batched: 13 stacked one-hot sources = I₁₃ @ M² in one product;
      the alice row answers (alice, grandAdvisor, ?) = ['carol', 'dave']

배치를 다루는 줄이 이 경제적 논지 전체를 하나의 항등식으로 담고 있습니다. 질의 하나는 원-핫 행 하나에 제곱된 행렬을 곱한 것이고, 천 개의 질의는 천 개의 원-핫 행을 쌓은 것에 제곱된 행렬을 곱한 것으로, 여전히 곱셈 한 번입니다. 가능한 13개의 출발점을 모두 쌓으면 항등 행렬 $I_{13}$이 되고, $I_{13}\, M^2 = M^2$이므로, 제곱된 행렬 자체가 모든 grandAdvisor 질의에 대한 완전한 답변표입니다(tensor_ops.py 339–342행이 이를 단언하고 alice의 행을 다시 읽어 들입니다). GPU가 존재하는 이유인 배치는 논리에 아무 비용도 물리지 않습니다: 그것은 그저 행들의 무더기일 뿐입니다.

행렬 관점이 사 오는 것, 그리고 감추는 것

이 관점에는 두 가지가 딸려 옵니다. 첫째는 반복 곱셈에 의한 k-홉 추론입니다: 곱 하나가 몸체 원자 하나를 적용한다면, $k$제곱 $M^k$는 정확히 길이 $k$인 경로를 세고, $k$개의 관계 홉을 합성하는 질의는 위와 정확히 같은 방식으로 출발점들에 걸쳐 배치된 $k$개의 연쇄된 곱입니다. 컴패니언은 $M_{\text{advises}}$의 거듭제곱을 계산하고 그 전체 프로파일을 그래프와 대조합니다(tensor_ops.py 345–351행):

[3] k-hop by repeated matmul: powers of M_advises
      k   #pairs with a k-hop advising path   support
      1      4                                alice→bob, bob→carol, bob→dave, carol→erin
      2      3                                alice→carol, alice→dave, bob→erin
      3      1                                alice→erin
      4      0                                (none: DAG depth 3)

advising 그래프는 깊이 3의 유향 비순환 그래프(DAG, directed acyclic graph)이므로 네제곱은 영행렬이 됩니다; 모듈은 크기 수열 4, 3, 1, 0을 단언하고 유일한 3-홉 쌍을 alice→erin으로 고정합니다. 두 번째로 사 온 것은 이 부(part)가 존재하는 이유 그 자체입니다: 공짜로 얻는 미분 가능성입니다. 행렬곱은 그 항목들에 대한 다항식이므로, 항목들이 고정된 0/1 상수이기를 멈추고 학습된 파라미터가 되면 새로운 수학 없이도 경사가 규칙 적용을 통과해 흐릅니다; 그리고 어느 행렬을 곱할지의 선택 자체를 부드럽게, 즉 관계들에 대한 가중 혼합으로 만들면, 경사 하강은 규칙 자체를 학습할 수 있습니다. 이 이동이 다음 장의 주제이며, TensorLog는 그것의 직계 조상입니다 [2].

이제 감추어진 비용을 봅시다. 모듈은 이를 숨기지 않고 보여 줍니다. 행렬 항목은 진리값이 아니라 증명-경로 개수입니다. grandAdvisor의 경우 이 구별은 보이지 않았습니다(제곱 행렬의 모든 항목이 0 아니면 1이었고, 이는 tensor_ops.py 336행에서 주장됩니다). 그러나 규칙 하나만 더 있으면 이것이 드러납니다. sharesAuthor(P, Q) :- authored(X, P), authored(X, Q)를 생각해 보십시오: 어떤 사람 X가 두 논문을 모두 썼을 때 두 논문은 저자를 공유합니다. 첫 번째 원자는 역방향으로(논문에서 사람으로) 실행되며, 이는 전치(transposition)로 처리됩니다: 그 행렬은 $M_{\text{authored}}^{\top} M_{\text{authored}}$이며, 위 첨자 $\top$는 전치(transpose)를 나타냅니다. 즉 행과 열의 역할이 뒤바뀌도록 대각선을 기준으로 뒤집은 행렬입니다. 논문 p1에서의 대각 항목은 2입니다: X의 두 결속(alice와 bob, 공동 저자)이 각각 같은 사실 sharesAuthor(p1, p1)의 유도를 하나씩 완성하기 때문입니다. 논리적으로는 하나의 사실이지만, 산술적으로는 두 개의 경로입니다. 불리언 의미론은 유도 가능한지 아닌지에 대한 답을 필요로 하므로, 모듈은 명시적 클램프 $\min(\cdot, 1)$을 적용하고 클램핑이 값은 바꾸지만 지지 집합은 바꾸지 않음을 단언합니다(tensor_ops.py 354–367행). TensorLog 자체는 다른 선택을 합니다: 원래 항목을 정규화되지 않은 증명-개수 점수, 즉 진리값이 아니라 유도들에 대한 합으로 그대로 유지하는데, 이는 순위 매기기에는 특징이지만 논리학에는 버그입니다 [2]. 재귀적 규칙에서도 같은 주의가 다시 필요합니다: 전이적 폐쇄(transitive closure)는 고정된 거듭제곱이 아니라 최소 부동점(least fixpoint)이므로, 모듈은 지금까지 누적된 도달 가능성인 $R$(초깃값은 $M$)을 아무것도 바뀌지 않을 때까지 $R \leftarrow \min(R + R M, 1)$로 반복합니다(boolean_closure, tensor_ops.py 105–120행). 이는 1권의 체이스(chase)를 행렬로 옮긴 것입니다. 인용 그래프에서는 $k = 2$ 라운드 만에 수렴합니다.

      closure rule: R ← min(R + R·M_cites, 1) reaches its fixpoint at k = 2,
      support [('p2', 'p1'), ('p3', 'p1'), ('p3', 'p2')]
      == forward-chain citesTransitively (asserted set equality)   PASS

이것이 첫 번째 텐서화에 대한 정직한 요약입니다: 관계의 사슬은 곱이 되고, 출발점은 쌓인 행들로 배치되며, 경사는 공짜로 따라오고, 그 대가는 유도를 세는 일과 진리를 단언하는 일 사이의 차이에 대해 영원히 경계해야 한다는 것입니다. 경로 개수가 아니라 정확한 의미론을 가진 확률을 원한다면, 두 번째 텐서화가 필요합니다.

계층으로서의 회로: 우리 자신의 회로 위 KLay의 세 알고리즘

회로 장은 질의 grandAdvisor(alice, Z)를 매끄러운 결정론적 분해 가능 부정 정규형(d-DNNF, deterministic decomposable negation normal form) 회로로 컴파일했습니다: 3개의 변수(주석 달린 사실 advises(alice, bob), advises(bob, carol), advises(bob, dave), 확률은 각각 0.9, 0.9, 0.85), 10개의 노드, 10개의 엣지, 그리고 무차별 열거와 1e-12까지 일치하는 가중 모델 계수(WMC, weighted model count) 0.8865를 가집니다. 그 회로는 불규칙한 희소 DAG이며, 바로 GPU가 서투르다고 여겨졌던 형태입니다. KLay의 응답은 세 가지 알고리즘이며, 컴패니언은 각각을 이 정확한 회로 위에서 재현합니다 [1]. 이 알고리즘들이 재편성하는 것은 대수적 모델 계수의 세미링-매개변수적 회로 평가, 즉 엣지당 세미링 연산 하나(OR 노드에서는 ⊕, 세미링 합; AND 노드에서는 ⊗, 세미링 곱)입니다 [4]; 이 알고리즘들이 위에서 실행되는 대상은 표준 컴파일 타깃인 d-DNNF와 그 표준적 사촌인 문장 결정 다이어그램(SDD, sentential decision diagram)입니다 [5].

알고리즘 하나: 계층화(layerize). 모든 노드 $n$에 높이(height) $h_n$을 부여합니다: 잎(leaf)이면 0, 게이트라면 그 자식들의 높이 중 최댓값에 1을 더한 값 $1 + \max$입니다(tensor_ops.py 156–161행). 그런 다음 노드들을 높이별로 묶어 계층(layer)을 만듭니다. 이로부터 얻는 보상은 독립성 보장이며, 이는 정의로부터 한 걸음 만에 따라 나옵니다: 모든 엣지는 자식 $c$에서 부모 $p$로 향하며 $h_p \ge 1 + h_c \gt h_c$이므로, 같은 높이의 두 노드를 잇는 엣지는 없고, 따라서 한 계층 안의 어떤 노드도 자기 자신의 계층을 읽지 않습니다. 계층 전체는, 그 아래 계층들만 주어지면, 동시에 평가될 수 있습니다. 한 가지 걸림돌이 있습니다: 어떤 엣지는 여러 단계를 건너뛸 수 있습니다(높이 0인 잎이 높이 4인 게이트로 들어가는 경우). 그런 경우 계층화기는 건너뛴 계층 하나당 하나씩, 단항 통과(pass-through) 노드의 사슬을 삽입하여, 이후로는 모든 엣지가 엄격히 인접한 계층들만 잇고 평가가 깔끔한 하향에서 상향으로의 훑기가 되도록 합니다(tensor_ops.py 180–189행). 통과 노드는 의미론이 아니라 장부 정리입니다: 자식이 하나뿐인 ⊕ 세그먼트이며, 원소 하나를 축약하면 그것을 바꾸지 않고 그대로 돌려줍니다. 이 계산은 서술이 아니라 단언으로 확인됩니다: 계층화된 노드 수 = 회로 노드 수 + 통과 노드 수, 그리고 버퍼 엣지 수 = 회로 엣지 수 + 통과 노드 수입니다(tensor_ops.py 388–392행).

알고리즘 둘: 텐서화(tensorize). 한 계층은 벡터 프로세서가 소비할 수 있는 무언가, 즉 노드 객체가 아니라 평평한 정수 버퍼가 되어야 합니다. 각 계층 $l$에 대해 컴패니언은 gather-색인 배열 $S_l$(들어오는 모든 엣지에 대해, 계층 $l-1$의 값 벡터에서 그것이 읽는 위치), 세그먼트 오프셋(각 노드의 연속된 엣지 블록이 시작되는 곳), 그리고 연산자 분할(모든 ⊕ 노드(OR 게이트와 통과 노드)를 먼저, 모든 ⊗ 노드(AND 게이트)를 그 뒤에 재배열하여, 하나의 벡터화된 합-축약과 하나의 곱-축약이 계층 전체를 처리하도록 함)을 기록합니다(tensor_ops.py 201–236행). 지금까지 다뤄온 회로에 대해 커밋된 실행은 결과의 모양과 계층 구성을 출력합니다:

[5] KLay-lite: layerize by height, insert pass-throughs, flatten to buffers
      circuit                     vars  nodes  edges | layers  +pass  buffer edges
      ...
      grandAdvisor(alice, Z)         3     10     10 |      5      5            15
      ...
      grandAdvisor(alice, Z) layer mix — L1: 1 OR, 1 AND, 2 pass; L2: 0 OR, 1 AND, 2 pass; L3: 1 OR, 0 AND, 1 pass; L4: 0 OR, 1 AND, 0 pass

10개의 회로 노드가 높이 0에서 4까지 퍼져 있고, 잎을 포함하여 다섯 개의 계층이 있으며, 다섯 개의 통과 노드가 삽입됩니다(높이 4의 루트에서만 소비되는 잎 advises(alice, bob)는 그중 세 개를 거쳐 위로 호위됩니다). 버퍼는 15개의 엣지를 실어 나르는데, 이는 정확히 10 + 5입니다. "평평한 정수 버퍼"를 구체적으로 보이기 위해, 계층화기가 실제로 짓는 대로의 계층 1을 커밋된 코드의 실행에서 그대로 읽어 봅시다. 계층 0은 다섯 개의 리터럴 슬롯을 순서대로 담고 있습니다: advises(alice, bob), advises(bob, carol), ¬advises(bob, carol), advises(bob, dave), ¬advises(bob, dave).

계층-1 노드	종류	$S_1$의 세그먼트	계층-0 슬롯 중 읽는 것	계산 내용
slot 0	⊕ (OR)	위치 0–1	3, 4	회로 장의 매끄러움(smoothing) 게이트 pt = advises(bob, dave) ∨ ¬advises(bob, dave)(이진 OR이며, 이 장의 단항 통과 노드와는 다릅니다)
slot 1	⊕ (통과)	위치 2	1	advises(bob, carol), 위로 실려 감
slot 2	⊕ (통과)	위치 3	0	advises(alice, bob), 위로 실려 감
slot 3	⊗ (AND)	위치 4–5	2, 3	¬advises(bob, carol) ∧ advises(bob, dave)

따라서 $S_1 = [3, 4, 1, 0, 2, 3]$입니다: 여섯 개의 정수, 오프셋 0, 2, 3에서 시작하는 세 개의 ⊕ 세그먼트, 그리고 위치 4에서 분할된 뒤의 ⊗ 세그먼트 하나. 포인터는 하나도 남지 않습니다; 이 계층은 두 개의 평평한 배열과 하나의 오프셋 목록입니다.

알고리즘 셋: 평가(evaluate). 버퍼가 마련되면, 한 계층의 비용은 정확히 두 개의 배열 원시 연산으로 끝납니다: gather(팬시 인덱싱이 모든 엣지의 출발 값을 하나의 연속 배열로 끌어당깁니다)와 segment-reduce(각 노드가 자신의 연속된 gather된 값 블록을 자신의 세미링 연산자로 접습니다). 이것은 대수적 모델 계수의 평가이며, 의미는 그대로 유지된 채 모든 배열 프레임워크가 제공하는 두 가지 원시 연산으로 다시 표현된 것입니다 [4]. 내부 루프는 통째로 인용할 만큼 짧습니다(tensor_ops.py 258–269행, eval_batch 내부):

        n = np.where(self.leaf_sign, w[:, self.leaf_var],
                     1.0 - w[:, self.leaf_var])
        for lay in self.layers:
            e = n[:, lay["S"]]                                    # gather
            out = np.empty((w.shape[0], lay["n_nodes"]))
            if lay["n_sum"]:
                out[:, :lay["n_sum"]] = np.add.reduceat(
                    e[:, :lay["split"]], lay["off_sum"], axis=1)
            if lay["n_sum"] < lay["n_nodes"]:
                out[:, lay["n_sum"]:] = np.multiply.reduceat(
                    e[:, lay["split"]:], lay["off_prod"], axis=1)
            n = out

첫 줄에서 배치를 읽어 보십시오: w는 $B \times n_{\text{vars}}$ 배열이며, 배치의 가중치 벡터 하나당 한 행(여기서 배치 크기 $B$는 1000입니다), 회로 변수 하나당 한 열이고, 잎 줄은 $B$개의 잎 계층 전체를 한 번에 실체화하며, 양의 리터럴에는 $w$를, 음의 리터럴에는 $1 - w$를 취합니다. 그 뒤의 모든 gather와 축약은 배치 차원을 건드리지 않고 함께 나릅니다: 천 개의 회로 평가는 오직 데이터만 다를 뿐 제어 흐름은 결코 다르지 않으며, 이것이 하드웨어 친화성의 정의입니다. 옮겨지는 데이터의 단위는 행 하나, 엣지 하나당 gather된 값 하나이며, 여기서 그 개수가 달라집니다: 재귀적 평가자는 회로 엣지 하나당 값 하나를 읽는 반면, 계층화된 패스는 버퍼 엣지 하나당 하나를 gather하는데, 이는 회로의 엣지 수에 통과 노드당 엣지 하나를 더한 것입니다(여기서는 15 대 10; [5]번 표의 가장 깊은 사슬에서는 1032 대 238). 따라서 계층화된 패스는 메모리를 통해 엄밀히 더 많은 데이터를 옮깁니다. (세미링 연산의 적용 횟수는, 굳이 말하자면, 오히려 줄어듭니다: reduceat은 $k$개의 gather된 값으로 이루어진 세그먼트를 $k-1$번의 적용으로 접는 반면 — 여기서 $k$는 세그먼트의 엣지 수입니다 — 재귀적 평가자는 세미링의 항등원에서 시작해 각 노드를 접으며 $k$번을 씁니다.) 결정적으로 바뀌는 것은 일정(schedule)입니다: 수천 번의 해석된 노드 방문이 계층당 두 개의 벡터화된 원시 연산이 됩니다. 그리고 답은 조금도 움직여서는 안 됩니다. 모듈은 스위트의 모든 회로를 재귀 방식과 계층화 방식 양쪽으로 평가하고 $10^{-10}$ 미만의 일치를 단언합니다(tensor_ops.py 393–396행):

[6] correctness: layered gather/reduce pass == recursive bottom-up pass
      circuit                     layered WMC      recursive WMC    |diff|
      ...
      grandAdvisor(alice, Z)      0.886500000000   0.886500000000   0.0e+00
      ...
      chain n=20                  0.999728026391   0.999728026391   0.0e+00

가중 모델 계수 장의 #P-벽(계수 난해성 벤치마크) 사슬 계열(그 표시 chain n=20은 $n = 20$개의 변수, 곧 독립적인 2-동전 사슬 하나당 두 개씩인 동전들 위의 사슬 회로로 읽습니다)을 포함한 모든 회로에서, 그 차이는 허용 오차 아래일 뿐만 아니라, 두 패스가 같은 순서로 호환되는 덧셈과 곱셈을 수행하여 비트 단위로 일치합니다.

제대로 다룬 로그 세미링

실제 배포는 회로를 확률이 아니라 로그-확률 위에서 평가하는데, 여기에는 구체적인 이유가 있습니다. ⊗ 노드는 자식들을 곱하고, 깊은 회로는 많은 확률을 곱합니다: $k$개의 $\tfrac{1}{2}$ 인수의 곱은 $2^{-k}$이고, 배정밀도 부동소수점은 대략 $4.9 \times 10^{-324}$ 아래의 어떤 양수도 표현할 수 없으므로, $k = 1075$에서 그 곱은 소리 없이 정확한 0으로 밀려나고 그것을 통과하는 모든 경사는 죽습니다. 해결책은 $p$ 대신 $x = \log p$($e$를 밑으로 하는 자연로그이며, 지수함수 $e^x$의 역함수입니다)를 나르고 두 세미링 연산을 번역하는 것입니다. 곱은 스스로 번역됩니다: $\log(ab) = \log a + \log b$이므로, ⊗는 로그 값들의 평범한 덧셈이 되며, 이것이 로그-공간 평가자가 AND 세그먼트에 대해 np.add.reduceat을 실행하는 이유입니다. 까다로운 쪽은 합입니다. ⊕ 노드는 자식들의 로그 값 $x_i = \log p_i$로부터 $\log(\sum_i p_i)$를 필요로 합니다. 즉,

$$\bigoplus(x_1, \ldots, x_k) \;=\; \log \sum_{i=1}^{k} e^{x_i},$$

logsumexp 함수이며, 여기서 $k$는 세그먼트 안 자식의 수입니다. 이를 문자 그대로 계산하면 먼저 지수를 취해야 하고, 이는 피하려던 바로 그 언더플로를(그리고 $x_i$가 크다면 오버플로까지) 다시 만들어 냅니다. max 트릭이 두 문제를 모두 고치며, 그 유도는 세 줄입니다. $m = \max_i x_i$를, 로그 값들 중 가장 큰 것이라 합시다. $e^{x_i} = e^{m} e^{x_i - m}$을 이용해 합의 모든 항에서 $e^m$을 빼냅니다.

$$\log \sum_{i=1}^{k} e^{x_i} \;=\; \log \Big( e^{m} \sum_{i=1}^{k} e^{x_i - m} \Big) \;=\; m + \log \sum_{i=1}^{k} e^{x_i - m},$$

마지막 단계는 곱의 로그가 로그들의 합이라는 사실에서 나옵니다. 이제 잔차 합 $S = \sum_i e^{x_i - m}$을 유계로 만들어 봅시다. 모든 지수는 $x_i - m \le 0$을 만족하므로 모든 항은 많아야 $e^{0} = 1$이며, 최댓값을 주는 자식은 정확히 $e^{m - m} = 1$을 기여합니다. 따라서 $1 \le S \le k$이고, 보정항 $\log S$는 구간 $[0, \log k]$ 안에 있습니다: 완벽하게 표현 가능한 작은 수입니다. 아무것도 오버플로하지 않으며(지수화된 값 중 가장 큰 것은 1입니다), 최댓값보다 훨씬 작은 항들은 해롭지 않게 0으로 언더플로합니다. $x_i - m$이 대략 $-36$ 아래인 항은 무엇이든 머신 엡실론(약 $2.2 \times 10^{-16}$이며, 1 부근에서 인접한 배정밀도 수들 사이의 간격입니다)보다 작게 $S$에 기여하기 때문입니다. 컴패니언의 로그-공간 평가자는 정확히 이것을, 세그먼트마다, 배치로 구현합니다(tensor_ops.py 286–293행):

            if lay["n_sum"]:
                es = e[:, :lay["split"]]
                # m = per-segment max (the trick's shift), broadcast back
                # over each segment's edges by repeating it sizes_sum times.
                m = np.maximum.reduceat(es, lay["off_sum"], axis=1)
                shift = np.repeat(m, lay["sizes_sum"], axis=1)
                out[:, :lay["n_sum"]] = m + np.log(np.add.reduceat(
                    np.exp(es - shift), lay["off_sum"], axis=1))

검증은 앞서와 같은 규율을 따릅니다: 로그-공간 답을 지수화하여 선형-공간 답과 비교하되, $B = 1000$개의 무작위 가중치 벡터 전체 배치에 걸쳐 $10^{-9}$ 미만임을 단언합니다(tensor_ops.py 412–415행):

[7] batched: B = 1000 random weight vectors (rng seed 0) in ONE pass
      circuit                 max|vector − loop|   max|exp(log) − linear|
      grandAdvisor(alice, Z)             0.0e+00                  2.2e-16
      chain n=20                         0.0e+00                  7.8e-16
      (asserted < 1e-10 and < 1e-09; the log semiring uses ⊗ = +, ⊕ = logsumexp
       with the max trick m + log Σ e^(x−m), so nothing under/overflows)

2천 번의 회로 평가 전체에 걸친 최악의 불일치는 $7.8 \times 10^{-16}$이며, 이는 배정밀도 수의 마지막 이진 자릿수 몇 개 수준입니다: 로그 세미링은 근사가 아니라 그저 좌표 변환일 뿐입니다.

정직한 벤치마크

이 모듈은 타이밍 표로 끝나며, 모듈도 이 장도 그것을 신중하게 짜 놓았습니다. 비교 대상은 가중치 벡터 하나당 한 번씩 호출되는 재귀적 파이썬 평가자(해석된 회로 순회 $B = 1000$회의 루프, _recursive_batch, tensor_ops.py 301–309행)와, 네 개의 컴파일된 사슬 회로에 대해 1000개 행 전체를 한 번에 처리하는 계층화된 gather/segment-reduce 패스입니다(tensor_ops.py 419–433행). 시간은 실측 wall-clock으로 측정되므로, 이 장의 다른 모든 숫자와 달리 실행마다 달라집니다; 모듈은 이를 "규모 감을 잡기 위한 것일 뿐"으로 출력하고 그것에 대해서는 아무것도 단언하지 않으며, 오직 두 평가가 같은 값을 낸다는 것만 단언합니다. examples/integration/README.md에 커밋된 정본 실행은 다음을 출력합니다(당신의 기계에서 나온 절대값은 다르겠지만, 중간 행들은 실행마다 흔들리며, 재현되는 것은 가장 얕은 사슬에서 가장 깊은 사슬로 갈수록 나타나는 전반적인 하락세입니다):

[8] honest timing, B = 1000 weight vectors (measured wall-clock, shown
    for scale only, asserted NOWHERE — the asserted content is [6]/[7])
      circuit        nodes  edges  layers   loop ms*  vector ms*  speedup*
      chain n=8         41     64      14      11.7        0.85     13.7x
      chain n=12        65    114      22      18.8        1.81     10.4x
      chain n=16        89    172      30      25.8        2.99      8.6x
      chain n=20       113    238      38      33.2        4.39      7.6x

정직한 읽기는 두 가지입니다. 첫째, 속도 향상은 실재하지만 완만하여 대략 한 자릿수 정도이며, 가장 얕은 사슬보다 가장 깊은 사슬에서 오히려 더 작은데(표의 중간 행들은 실행마다 흔들립니다), 이는 두 가지가 겹쳐지기 때문입니다: 계층이 늘어날 때마다 고정된 계층당 오버헤드가 붙고(gather 하나에 최대 두 번의 축약 호출이 붙지만, 어떤 계층의 노드가 모두 ⊕이거나 모두 ⊗이면 호출은 하나뿐입니다), 통과 노드 삽입이 버퍼를 부풀립니다($n = 20$에서 회로 엣지 238개가 버퍼 엣지 1032개가 됩니다). 그래서 계층화된 패스는 계층이 불어나는 바로 그 깊고 건너뛰기가 많은 회로에서 엄밀히 더 많은 데이터를 옮깁니다. 이 사슬 회로들은 넓게가 아니라 깊게 자라며, 이는 계층화된 일정에 불리한 영역입니다. 둘째, 더 중요한 것은, 이것이 GPU 이야기 자체가 아니라 NumPy 프록시라는 점입니다: 두 경쟁자 모두 같은 CPU 코어 위에서 실행되므로, 이 표는 하드웨어의 변화가 아니라 일정의 변화(배치된 벡터화된 훑기 대 해석된 포인터 쫓기)를 분리해 보여 줄 뿐입니다. 동일한 회로에 대한 단순 노드별(node-by-node) 평가와 대비하여, 실제 GPU 커널 위에서 같은 계층화-텐서화-평가 알고리즘을 실행하는 발표된 시스템은 가장 큰 벤치마크에서 최대 네 자릿수(만 배)에 이르는 속도 향상을 보고합니다 [1]. 이 축소판은 그 숫자를 재현하지 않으며 재현할 수도 없습니다; 이 축소판이 assert와 함께 재현하는 것은 신뢰에서 정말로 중요한 주장입니다: 빠른 레이아웃이 느린 레이아웃과 정확히 같은 함수를 계산한다는 것입니다.

Lobster: 언어 수준

TensorLog는 규칙을 텐서화했고, KLay는 회로를 텐서화했습니다. 남은 것은 그 주위의 모든 것입니다: 조인, 부정, 집계, 재귀, 실무자가 실제로 작성하는 언어 그 자체입니다. Scallop은 그 언어에 프로버넌스-세미링 의미론을 주었고, Lobster는 그것을 통째로 GPU 위로 낮춥니다 [3]. 그 설계를 한 문단으로 말하면 이렇습니다: Scallop 프로그램은 열 지향(columnar) 관계(관계를 튜플의 행이 아니라 열들의 병렬 배열로 저장하는 것으로, 위의 인접 행렬과 색인 버퍼와 같은 레이아웃입니다) 위의 정적 단일 대입(SSA, static-single-assignment) 중간 표현으로 컴파일됩니다; 관계 연산자들은 GPU 커널 원시 연산이 되고, 그것들 사이의 조인은 대규모 병렬 해시 조인이 됩니다; 재귀는 고전적 데이터로그의 반순진(semi-naive) 부동점 루프로 실행되며, 매 반복은 새 튜플만을 유도하는 커널 실행 배치입니다; 그리고 프로버넌스 태그는 추가 열을 타고 함께 흐르므로, 하나의 컴파일된 프로그램이 세미링을 바꾸는 것만으로 이산 추론, 확률적 추론, 경사 계산을 모두 제공합니다. 이는 회로 장에서 나온 aProbLog(algebraic ProbLog, 대수적 ProbLog)의 이동을 디바이스 위에서 실행하는 것입니다. 정직하게 짚어 둘 점은 이것입니다: GPU 위에서의 Lobster의 미분 가능한 프로버넌스는 현재 top-1-proof 세미링(모든 유도가 아니라 단일 최선의 유도만을 추적)으로 제한되어 있어, 그 정확성의 다이얼은 컴파일된 회로가 제공하는 것보다 낮은 곳에 놓여 있습니다 [3].

한 걸음 물러서면 이 부의 노동 분업이 하나의 스택으로 눈에 보이며, 이 부의 각 장이 그중 한 층씩을 소유합니다.

시스템	스택에서의 층	텐서화하는 대상	정확성 다이얼
TensorLog	규칙 적용	관계를 행렬로, 규칙을 행렬곱으로	확률이 아니라 증명 개수; 불리언 진리를 위한 클램프
Scallop / Lobster	언어(데이터로그 + 프로버넌스)	열 지향 관계, 해시 조인과 부동점 커널	세미링 선택 가능; GPU 미분 가능 경로는 top-1-proof
의미 손실	손실 함수	목적함수 내부의 컴파일된 제약 회로	제약의 정확한 WMC
KLay	회로 커널	gather + segment-reduce로서의 d-DNNF/SDD 평가	마지막 비트까지 정확

이 장의 교훈은 가장 오른쪽 열과 위의 실행 결과에 담겨 있습니다: 이 스택의 어디에서도 속도를 얻기 위해 의미론이 바뀌지 않았습니다. grandAdvisor 곱은 전방 연쇄기의 부동점과 집합으로서 같습니다; 계층화된 패스는 재귀적 패스와 머신 정밀도까지 같습니다; 로그 세미링은 좌표 변환을 통해 선형 세미링과 같습니다. 바뀐 것은 메모리 레이아웃, 즉 포인터에서 평평한 버퍼로의 변화이고, 일정, 즉 한 번에 하나씩의 재귀에서 배치된 훑기로의 변화입니다. 정확성은 결코 병목이 아니었습니다. 평면도가 병목이었습니다.

아직 풀리지 않은 부분

계층화된 평가는 그것에게 주어진 회로만큼만 좋으며, 이 장은 회로를 더 작게 만드는 일은 하지 않았습니다. 회로 장이 남긴 경고, 즉 컴파일된 크기가 변수 순서에 잔혹하리만큼 좌우되고 잘못된 논리식에서는 지수적으로 커질 수 있다는 경고는 여기서 사라지기는커녕 오히려 겹쳐집니다: 지수적으로 큰 회로를 아주 빠르게 평가하는 GPU도 여전히 지수적인 작업을 하고 있는 것이며, 컴파일 자체는 여전히 순차적이고 CPU에 묶인 탐색으로, 이 장의 어떤 장치도 그것을 가속하지 않습니다. 둘째, 배치는 동질적일 때에만 깔끔합니다. 우리의 $B = 1000$개 행은 하나의 회로를 공유했고 오직 가중치만 달랐습니다; 실제 DeepProbLog 질의 학습 배치는 모양이 서로 다른 다양한 회로들을 낳으며, 이것들을 함께 평가하려면 패딩(낭비: 모든 회로를 배치에서 가장 큰 계층 프로파일에 맞춰 패딩)과 스트리밍(직렬화: 배치가 다시 큐로 풀림) 사이에서 선택해야 하는데, 아직 완전히 만족스러운 답은 없습니다. 셋째, 언어 수준은 2부가 닫았던 문 하나를 다시 엽니다: 정확한 WMC는 모든 증명에 걸쳐 합산하지만, Lobster의 미분 가능한 GPU 경로는 현재 top-1-proof 프로버넌스만을 추적합니다 [3]. 이는 Scallop 장이 의도적으로 올랐던 근사의 사다리이며, 지금은 선택된 것이 아니라 하드웨어 이식에 의해 강요된 것입니다. 완전히 정확한 프로버넌스를 GPU 네이티브로 만들 수 있는지, 아니면 가속기가 언어 수준에서 정확성에 영구적으로 세금을 매기는지는 열린 시스템적 질문입니다.

왜 중요한가

이 장은 실전에서 마주치게 될 어떤 무시하는 태도, 즉 "정확한 방법은 우아하지만 확장되지 않으므로, 프로덕션 시스템은 엉성해야 한다"에 대한 이 권의 답변입니다. 표들은 그렇지 않다고 말합니다; 느림은 1980년대 자료 구조를 2020년대 하드웨어 위에 구현한 데서 온 인공물이었고, 레이아웃이 고쳐지면 정확성은 마지막 비트까지 살아남습니다. 이는 앞으로도 중요합니다: 5권의 신뢰 장들은 확률 추정치가 의미론이 말하는 바를 정확히 의미한다는 것 위에 서 있으며, 추론기의 출력을 재검사하는 검증기는 서빙 시점에 그 정확한 검사가 감당할 만할 때에만 배포 가능합니다; 가속기 속도로 실행되는 gather-plus-segment-reduce가 바로 그 감당할 만함의 모습입니다. 이는 또한 뒤로도, 즉 두 기둥에 대해서도 중요합니다: 신경 기둥은 자신의 하드웨어와 공진화함으로써 부분적으로 그 십 년을 이겼고, 기호 기둥도 이제 같은 일을 하고 있으며, 1권의 전방 연쇄기의 의미론은 새로운 평면도 아래에서도 그대로 유지됩니다. 두 기둥 사이의 다리는 양쪽 끝이 같은 실리콘 위에서 돌아갈 때 더 이상 세금이 아니게 됩니다.

핵심 용어

• 인접 행렬(adjacency matrix) $M_r$: 관계 하나의 $N \times N$ 0/1 배열이며, $(h, r, t)$가 성립할 때 정확히 $M_r[h, t] = 1$입니다; 몸체 원자를 적용하는 것은 $M_r$을 곱하는 것입니다.
• 원-핫 벡터(one-hot vector): 개체 하나를 표시하는 1이 하나뿐인 행벡터; 질의 출발점들의 배치는 원-핫 행들의 무더기이며, 가능한 13개 출발점을 모두 쌓으면 항등 행렬이 됩니다.
• 증명-경로 개수(proof-path count): 행렬곱 항목이며, 사실의 진리값이 아니라 규칙 유도의 개수입니다; 불리언 의미론은 클램프 $\min(\cdot, 1)$을 요구합니다.
• 계층화(layerization): 회로 노드를 높이별로 묶는 것($h = 0$은 잎, 게이트는 자식 높이의 최댓값에 1을 더한 값 $1 + \max$)으로, 같은 계층의 노드들은 엣지를 공유하지 않고 함께 평가됩니다; 단계를 건너뛰는 엣지는 단항 통과 노드로 수리됩니다.
• 텐서화(tensorization): 각 계층을 정수 버퍼로 평탄화하는 것으로, gather 색인 $S_l$과 세그먼트 오프셋을 두고, ⊕ 노드를 ⊗ 노드보다 앞에 두어 두 번의 축약이 계층 전체를 처리하도록 합니다.
• Gather / segment-reduce: 계층화된 평가의 두 배열 원시 연산으로, 아래 계층으로의 팬시 인덱싱 다음에 세미링 연산자로 하는 세그먼트별 접기입니다.
• 로그 세미링(log semiring): $x = \log p$라는 좌표 변환으로, 그 아래에서 ⊗는 $+$가 되고 ⊕는 logsumexp가 됩니다; max 트릭 $m + \log \sum_i e^{x_i - m}$은 지수화된 모든 항을 많아야 1로 유지하며, 보정항은 $\log k$로 유계입니다.
• 반순진 부동점(semi-naive fixpoint): 매 라운드마다 새 튜플만 유도하는 데이터로그 평가 전략; GPU 위에서는(Lobster에서처럼) 매 라운드가 열 지향 해시 조인 커널의 배치입니다.

이 장이 향하는 곳

행렬 관점은 이 장이 예고만 해 둔 것 하나를 더 사 왔습니다: 경사입니다. 관계 행렬에 학습 가능한 가중치를 부여하고, 각 홉에서 어느 관계를 곱할지의 선택을 관계 어휘 전체에 대한 부드러운 주의(attention)로 만든다면, 규칙 자체, 즉 어떤 홉의 순서가 데이터를 설명하는지가 경사 하강이 탐색할 수 있는 연속적인 대상이 됩니다. 이것이 정확히 Neural-LP와 DRUM의 구성입니다: 이 장의 행렬곱 바로 위에 지어진 미분 가능한 규칙 학습이며, 여기서 컴패니언의 학습된 주의는 advises ∘ advises를 신뢰도 0.9990의 최상위 규칙으로 복호화합니다. 평면도는 이제 빨라졌습니다; 다음 장은 그것이 학습하도록 만듭니다.