박스 임베딩: Query2Box 기하

📍 현재 위치: II부 · 영역과 기하 임베딩 — 5장. 공과 원뿔은 개념에게 영역을 주었습니다. 이 장은 질의에게 영역을 주며, 교집합을 취해도 같은 부류 안에 머무르는 단 하나의 도형을 고릅니다.

앞 장은 씁쓸한 기하학적 여운을 남기며 끝났습니다: 공(ball)은 단일 개념을 위한 영역 계산법으로는 훌륭하지만, 두 공의 교집합은 렌즈 모양이고, 렌즈는 공이 아닙니다. 이 실패는 우리가 엣지 하나에 관해 묻는 일을 멈추고 "누가 p1을 저술했고 alice에게 지도받는가?" 같은 진짜 질문을 던지기 시작하는 순간 문제가 됩니다. 왜냐하면 그리고(and)의 자연스러운 의미론이 곧 교집합이기 때문입니다. 이 장은 그 문제를 고치는 영역 계열을 만듭니다. Query2Box는 개념뿐 아니라 질의(query) 자체를 축에 정렬된 박스로 표현합니다: 앵커 개체(anchor entity)는 점이고, 관계마다의 홉(hop)은 현재 박스를 이동시키고 넓히며, 논리곱은 모서리별 최댓값과 최솟값으로 박스를 정확하게 교집합시킵니다 [1]. 우리는 이 계산법의 두 부분으로 이루어진 거리를 항별로 유도하고, 그 꺾인 지점마다 모든 하위그래디언트를 구해 내며, 학계 그래프 위에서 손으로 쓴 그래디언트로 모델을 훈련한 다음, 정답을 기호적으로, 즉 순회를 통해 계산해 둔 세 개의 다중 홉 질의에 답하게 함으로써 기하학이 정직하게 견줄 대상을 갖도록 만들 것입니다.

쉽게 말하면

지도에서 아파트를 찾는다고 상상해 보십시오. "대학교 근처"는 하나의 핀이 아니라, 받아들일 만한 블록들을 색칠한 사각형입니다. "지하철 노선 위"는 또 다른 사각형입니다. 두 조건을 모두 만족해야 한다면, 여러분은 두 사각형을 평균 내어 타협한 핀 하나로 만들지 않습니다; 그 둘이 겹치는 영역을 색칠할 뿐이고, 마침 두 사각형이 겹치는 부분은 또 하나의 사각형입니다. Query2Box는 데이터베이스 질의도 똑같은 방식으로 다룹니다: 질문의 각 홉은 임베딩 공간에 박스 하나를 그리고, 그리고(and)는 "그 박스들을 겹친다"는 뜻이며, 답은 최종 박스 안에 핀이 떨어지는 개체들입니다. 이 모든 것이 작동하는 이유는 직사각형이 지닌 작은 초능력 때문입니다: 직사각형을 직사각형과 겹쳐도 여전히 직사각형이며, 이는 지난 장에서 원(circle)이 결코 해내지 못했던 바로 그 일입니다.

이 장에서 다루는 내용

• 하나의 꼬리에서 꼬리들의 집합으로: EPFO(existential positive first-order, 실존 긍정 1차) 질의는 답이 하나의 집합이므로, 질의는 점이 아니라 영역을 가질 자격이 있습니다; 답하기는 소속 순위 매김이 됩니다.
• 박스와 그 거리, 유도하기: 중심 $\mathbf{c}$, 음이 아닌 오프셋 $\mathbf{o}$, 그리고 거리 $\operatorname{dist}_{\text{outside}} + \alpha \cdot \operatorname{dist}_{\text{inside}}$를 다룹니다. 각 항은 구간 기하학으로부터 유도되고 boxes.py와 대조됩니다.
• 이동-후-확장으로서의 관계 투영: $\text{box}' = (\mathbf{c} + \mathbf{t}_r,\ \mathbf{o} + \operatorname{softplus}(\mathbf{s}_r))$이며, 한 홉이 왜 영역을 키우기만 할 수 있는지에 관한 단조성 논증, 그리고 역방향 엣지를 위해 두 배로 늘린 관계 어휘를 다룹니다.
• 정확한 교집합: 박스가 교집합에 대해 닫혀 있음을 보이는 두 줄짜리 증명, 덤으로 딸려 오는 공집합 판정, 그리고 학습된 어텐션 연산자 및 실패했던 공들과의 대조를 다룹니다.
• 하위그래디언트로 훈련하기: 1홉 질의에 대한 마진 손실, $\max/\min$의 꺾인 지점을 관통하는 모든 하위그래디언트, softplus를 관통하는 연쇄 법칙, 그리고 실제로 커밋된 손실 추이를 다룹니다.
• 기하학적으로 답한 세 개의 질의: 학계 그래프 위의 1p, 2p, 2i 질의를 각각 순회로 계산한 기호적 답과 대조하고, 실행 결과에서 나온 교집합의 모서리와 20개 점 폐쇄성 검사를 다룹니다.
• 정직한 소규모 결과 읽기: 무엇이 정확히 일치했는지(셋 중 둘), 무엇이 근접한 순위에 머물렀는지, 그리고 13개 개체짜리 그래프가 왜 벤치마크가 아니라 시연인지를 다룹니다.

"어느 꼬리인가?"에서 "어느 꼬리들의 집합인가?"로

I부의 모든 것은 트리플 하나씩을 점수 매겼습니다. TransE, DistMult, ComplEx는 모두 "엣지 $(h, r, t)$ 하나가 얼마나 그럴듯한가?"에 답했고, 링크 예측(link prediction)은 advises(bob, ?) 같은 질의를 후보 꼬리 하나하나를 따로 점수 매기는 일로 환원했습니다. 이 틀은 하나의 유형 오류를 숨기고 있습니다. 질의 advises(bob, ?)는 하나의 답을 갖지 않습니다; 그것은 하나의 답 집합(answer set)을 갖습니다. 학계 그래프에서 그 집합은 $\{$carol, dave$\}$이고, $\mathbb{R}^d$(실수 $d$차원 공간, 여기서 $d$는 임베딩 차원입니다) 안의 어떤 단일 점도 carol의 점과 dave의 점, 그리고 다른 모든 답 집합의 모든 원소에 동시에 가까이 있을 수는 없습니다. 점에는 내부가 없지만, 집합에는 내부가 필요합니다.

신경 써야 할 질의들은 이 불일치를 더 악화시킵니다. 이 장이 다루는 목표 부류는 EPFO 질의로, existential positive first-order(실존 긍정 1차)의 줄임말입니다: 논리곱($\wedge$, "그리고"), 논리합($\vee$, "또는"), 존재 한정($\exists$, "어떤 것이 존재한다")을 사용해 관계 원자(atom)들로 지어지고, 부정도 전칭 한정사도 없는 질의입니다 [1]. 풀어 쓰면, 우리의 세 번째 시연 질의는

$$q[v]\;=\;\text{authored}(v,\, p1)\ \wedge\ \text{advises}(\text{alice},\, v),$$

이며, 읽으면 "p1을 저술했고 그리고 alice가 지도하는 개체 $v$"입니다. $q[v]$의 대괄호는 $v$를 답 변수(answer variable)로 표시합니다: 이 변수는 한정사에 결코 묶이지 않고 자유로 남는데, 질의가 이 변수를 채울 수 있는 개체들의 집합을 나타내기 때문입니다. 부류 이름의 $\exists$는 오직 중간 변수, 즉 연쇄된 질의가 거쳐 가지만 답으로 돌려주지는 않는 변수만을 묶습니다; 이 2i 질의에는 그런 변수가 없지만, 2p 질의 $q[v] = \exists\, y:\ \text{advises}(\text{alice}, y) \wedge \text{advises}(y, v)$, 즉 "alice의 어떤 지도학생 $y$의 지도학생인 $v$들"에는 하나가 있습니다. EPFO 질의는 앵커 개체(anchor entity, 상수 p1과 alice)에서 관계 엣지를 거쳐 하나의 자유 변수로 이어지는 작은 유향 그래프이며, 그 답은 그 변수를 채울 수 있는 개체들의 집합입니다. 표준적인 형태 이름은 홉 수를 셉니다: 1p는 하나의 투영 advises(bob, ?)이고, 2p는 두 개의 투영을 연쇄하며, 2i는 두 개의 1p 가지를 교집합합니다 [1].

이런 질의에 답하는 기호적 방법은 그래프 순회입니다: 각 앵커에서 시작해, 엣지를 따라가며, 집합들을 교집합합니다. 순회는 정확하지만 취약합니다: 불완전한 그래프 위에서는(링크 예측의 전제) 엣지 하나가 빠지는 것만으로도 답 집합이 조용히 잘려 나가고, 큰 그래프에서는 중간 집합들이 폭발적으로 커집니다. 첫 번째 신경망 대안인 Graph Query Embedding은 질의 자체를 점으로 임베딩하여, 학습된 연산자로 홉들을 합성하고 최근접 이웃 탐색으로 답했습니다 [2]. 이는 유형 오류를 그대로 물려받습니다: 점값 질의는 여전히 "원소가 세 개인 집합"을 나타낼 수 없습니다. Query2Box는 질의의 유형을 점에서 영역(region)으로 격상시킵니다: 질의는 그 내부가 곧 답 집합인 박스가 되고, 따라서 답하기는 소속 순위 매김이 됩니다. 즉 모든 개체를 그 점이 박스에서 얼마나 떨어져 있는지에 따라 정렬하는 것입니다 [1]. 개체는 여전히 점으로 남고, 오직 질의만 박스가 됩니다. (세 번째 패러다임은 질의 임베딩 없이, 평범한 1홉 예측기를 퍼지(fuzzy)하게 합성합니다; 이 장의 끝에서 다시 다룹니다 [3].)

박스, 형식적으로

기호보다 먼저 대상을 풀어 읽겠습니다. 박스(box)는 $\mathbb{R}^d$ 안에 삽니다; 이 장 전체에서 $d = 8$이고, 색인 $i \in \{1, \ldots, d\}$는 좌표축 하나를 가리킵니다. 박스는 두 벡터로 저장됩니다: 박스의 중점인 중심(center) $\mathbf{c} \in \mathbb{R}^d$와, 각 성분이 $o_i \ge 0$을 만족하며 각 축을 따른 박스의 반너비(half-width)인 오프셋(offset) $\mathbf{o} \in \mathbb{R}^d$입니다. 박스 자체는 구간들의 곱입니다

$$\operatorname{Box}(\mathbf{c}, \mathbf{o}) \;=\; \bigl\{\, \mathbf{v} \in \mathbb{R}^d \;:\; c_i - o_i \,\le\, v_i \,\le\, c_i + o_i \ \text{ for every } i \,\bigr\},$$

이며, 아래 모서리(lower corner)는 $\mathbf{c} - \mathbf{o}$, 위 모서리(upper corner)는 $\mathbf{c} + \mathbf{o}$입니다. 소속 여부는 차원별 구간 검사이며, 이는 깔끔하게 압축됩니다. 축 $i$를 따라 점이 중심에서 떨어진 거리를 $a_i = \lvert v_i - c_i \rvert$로 씁니다(막대 $\lvert \cdot \rvert$는 절댓값을 나타냅니다). 그러면 $c_i - o_i \le v_i \le c_i + o_i$는 정확히 $a_i \le o_i$일 때 성립하므로

$$\mathbf{v} \in \operatorname{Box}(\mathbf{c}, \mathbf{o}) \quad\Longleftrightarrow\quad a_i \le o_i \ \text{ for every dimension } i.$$

동반 모듈 boxes.py에서 박스는 말 그대로 배열 두 개의 쌍이고(boxes.py 89번째 줄), 개체는 오프셋이 0인 퇴화된 박스, 즉 하나의 점으로 임베딩됩니다(boxes.py 144–146번째 줄):

def point_box(e: str, V: np.ndarray) -> Box:
    """An entity as a degenerate box: its point with a zero offset."""
    return V[E_ID[e]].copy(), np.zeros(D)

거리, 항별로 유도하기

순위를 매기려면 "이 개체가 답이 되기까지 얼마나 먼가"에 대한 등급 있는 척도가 필요하며, Query2Box는 바깥쪽과 안쪽 사이에 의도적인 비대칭을 둔 두 부분짜리 거리를 사용합니다 [1]. 다음은 커밋된 구현이며, 그 독스트링(docstring)이 두 부분을 모두 명시합니다(boxes.py 105–119번째 줄):

def box_dist(v: np.ndarray, c: np.ndarray, o: np.ndarray) -> float:
    """Query2Box point-to-box distance, with a = |v - c| per dimension:

        dist_outside(v, box) = || max(0, a - o) ||_1   L1 path from v to the
                                                       box surface (0 inside);
        dist_inside(v, box)  = || min(a, o) ||_1       L1 path from the surface
                                                       toward the center,
                                                       capped at the offset;
        dist = dist_outside + ALPHA * dist_inside      ALPHA = 0.2 makes every
                                                       point inside the box
                                                       near-equally good, yet
                                                       still ordered centerward.
    """
    a = np.abs(v - c)
    return float(np.maximum(a - o, 0.0).sum() + ALPHA * np.minimum(a, o).sum())

표기 $\lVert \cdot \rVert_1$은 L1 노름(L1 norm)입니다: 벡터 성분들의 절댓값의 합입니다. 두 항을 그냥 받아들이는 대신 직접 유도해 보겠습니다.

바깥쪽 항은 박스에서 가장 가까운 점까지의 L1 거리입니다. 박스가 구간들의 곱이므로, $\mathbf{v}$에 가장 가까운 박스 위의 점은 축 하나씩 따로 구할 수 있습니다: 그것은 클램프(clamp) $p^{\ast}_i = \min\bigl(\max(v_i,\, c_i - o_i),\ c_i + o_i\bigr)$이며, $v_i$가 이미 구간 안에 있으면 그대로 두고 그렇지 않으면 더 가까운 끝점으로 밀어 넣습니다. 축별 간격 $\lvert v_i - p^{\ast}_i \rvert$의 세 경우를 확인해 봅시다. $v_i \gt c_i + o_i$(구간 위쪽)이면 클램프는 $c_i + o_i$를 돌려주고, $v_i \gt c_i$이므로 $a_i = v_i - c_i$가 성립해 간격은 $v_i - (c_i + o_i) = a_i - o_i$입니다. $v_i \lt c_i - o_i$(구간 아래쪽)이면, 거울상 계산에 의해 간격은 $(c_i - o_i) - v_i = a_i - o_i$입니다. $v_i$가 구간 안에 있으면 클램프는 $v_i$ 자신이고 간격은 $0$입니다. 세 경우 모두 하나의 식 $\max(0,\, a_i - o_i)$로 표현되며, 축에 대해 합하면

$$\operatorname{dist}_{\text{outside}}(\mathbf{v}; \mathbf{c}, \mathbf{o}) \;=\; \bigl\lVert \max(\mathbf{0},\, \mathbf{a} - \mathbf{o}) \bigr\rVert_1 \;=\; \sum_{i=1}^{d} \max(0,\ a_i - o_i),$$

를 얻으며, 이는 $\mathbf{v}$가 박스 안에 있을 때 정확히 $0$이 됩니다: 바깥쪽 항은 소속 검사를 정량화한 것입니다.

안쪽 항은 내부를 중심 방향으로 정렬하되, 표면에서 값이 멈춥니다. 축마다, $\min(a_i, o_i)$는 점이 구간 안에 있을 때는 $a_i$(중심에서의 축 방향 거리)와 같고, 점이 바깥에 있게 되는 순간 반너비 $o_i$에서 포화됩니다. 합산하면 이 항에는 깔끔한 항등식이 성립합니다: $\operatorname{dist}_{\text{inside}} = \sum_i \min(a_i, o_i) = \lVert \mathbf{c} - \mathbf{p}^{\ast} \rVert_1$, 즉 중심에서 클램프 $\mathbf{p}^{\ast}$(점을 박스에 투영한 것)까지의 L1 거리입니다. 내부 점에서는 클램프가 점 자신이므로 이 항은 정확히 중심-점 거리이고, 점이 바깥에 있는 모든 축에서는 클램프가 면(face) 위에 놓여 기여분이 반너비에서 포화됩니다. 따라서 이 항은 반너비의 합 $\lVert \mathbf{o} \rVert_1$을 결코 넘지 않습니다. 전체 거리는 이 항을 $\alpha$만큼 할인합니다:

$$\operatorname{dist}(\mathbf{v}; \mathbf{c}, \mathbf{o}) \;=\; \operatorname{dist}_{\text{outside}} \;+\; \alpha \cdot \operatorname{dist}_{\text{inside}}, \qquad \alpha = 0.2 .$$

상수 $\alpha$(모듈의 ALPHA, boxes.py 51번째 줄)는 박스가 경계가 부드러운 집합처럼 행동하게 만드는 설계상의 결정입니다: $\alpha$가 작으면 박스 안의 모든 점이 거의 똑같이 좋지만(모든 답은 답입니다), 그럼에도 동점은 여전히 중심 쪽으로 깨지므로 박스 내부의 순위 매김은 결정적이고 훈련 가능한 상태로 남습니다 [1]. 차원별 경우 분석은 하나의 표로 압축됩니다:

$v_i$의 위치	조건	바깥쪽 항 $\max(0, a_i - o_i)$	안쪽 항 $\min(a_i, o_i)$	dist에 대한 기여분
중심에서	$a_i = 0$	$0$	$0$	$0$
엄격히 내부	$0 \lt a_i \lt o_i$	$0$	$a_i$	$\alpha\, a_i$
면 위에서	$a_i = o_i$	$0$	$o_i$	$\alpha\, o_i$
외부	$a_i \gt o_i$	$a_i - o_i$	$o_i$	$(a_i - o_i) + \alpha\, o_i$

마지막 열에서 두 가지 사실을 읽어 낼 수 있습니다. 첫째, 거리는 면에서 연속입니다: 내부에서 $a_i = o_i$에 접근하면 $\alpha\, a_i \to \alpha\, o_i$이고, 외부에서 접근하면 $(a_i - o_i) + \alpha\, o_i \to \alpha\, o_i$입니다; 양쪽 극한이 일치하므로 도약은 없고 오직 꺾임만 있습니다. 둘째, $a_i$에 대한 기울기는 이 꺾인 지점에서 내부의 $\alpha = 0.2$에서 외부의 $1$로 도약합니다: 박스 바깥의 개체는 내부의 개체가 중심을 향해 느끼는 것보다 다섯 배 더 강하게 표면 쪽으로 끌립니다. 이 꺾인 지점이 바로 훈련 절에서 다룰 하위그래디언트가 사는 곳입니다.

Query2Box의 세 가지 동작: 관계 홉은 점을 박스로 이동시키고(왼쪽), 논리곱은 모서리별 최댓값과 최솟값으로 박스를 정확히 교집합하며(가운데), 순위 매김은 표면까지의 L1 경로에 중심까지의 α로 할인된 경로를 더한 두 부분짜리 거리를 사용합니다(오른쪽). 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

관계 투영: 이동과 확장

1홉 질의는 앵커 점에서 시작해 하나의 관계를 따라갑니다. Query2Box는 각 관계 $r$에 학습된 벡터 두 개를 부여합니다: 중심을 옮기는 이동(translation) $\mathbf{t}_r \in \mathbb{R}^d$(이동 모델에서 TransE가 했던 것과 같은 동작입니다)와, 오프셋을 키우는 확장(widening)입니다. 동반 모듈은 확장을 softplus를 통해 매개변수화하여 결코 음수가 될 수 없게 만듭니다(boxes.py 149–156번째 줄):

def project(box: Box, r: str, T: np.ndarray, S: np.ndarray) -> Box:
    """Relation projection P_r(box) = (c + t_r, o + softplus(s_r)): translate
    the center (the TransE move) and *widen* the offset by a non-negative
    amount — following one more hop can only make a query region larger, never
    sharper, so the widening must not be allowed to shrink the box."""
    c, o = box
    ri = REL_ID[r]
    return c + T[ri], o + softplus(S[ri])

여기서 $\operatorname{softplus}(x) = \ln(1 + e^{x})$이며, $\ln$은 자연로그이고 $e^{x}$는 지수함수입니다; $e^{x}$는 언제나 $0$보다 크므로 로그의 인자는 $1$을 넘고, 그 출력은 엄밀히 양수입니다(boxes.py 92–96번째 줄). 따라서 투영은

$$P_r\bigl(\operatorname{Box}(\mathbf{c}, \mathbf{o})\bigr) \;=\; \operatorname{Box}\bigl(\mathbf{c} + \mathbf{t}_r,\ \ \mathbf{o} + \operatorname{softplus}(\mathbf{s}_r)\bigr),$$

이며, 여기서 $\mathbf{s}_r \in \mathbb{R}^d$는 관계의 원시 너비 벡터(raw width vector)로, 자유 매개변수입니다.

홉은 왜 반드시 확장해야 할까요? 현재 영역이 개체 집합 $Y$를 나타낸다면, 다음 영역은 $\{\,t : (y, r, t) \text{ for some } y \in Y\,\}$, 즉 $Y$의 모든 원소가 갖는 $r$-후속자들의 합집합을 나타내야 합니다. 하나의 원소가 여러 후속자를 가질 수도 있고(bob은 carol과 dave를 모두 지도합니다), 서로 다른 원소들의 후속자 집합은 서로 다른 곳에 놓이므로, 관계에 의한 집합의 상(image)은 일반적으로 그 집합을 한 번 이동시킨 것보다 더 넓게 퍼져 있습니다. 이동은 후속자들이 평균적으로 어디에 사는지를 다루고, 확장은 그 퍼짐을 위한 여유분입니다. 이 매개변수화는 올바른 단조성을 강제합니다: $\operatorname{softplus}(\mathbf{s}_r) \gt \mathbf{0}$이 성분별로 성립하므로, 모든 차원 $i$에서 $o_i \le o_i + \operatorname{softplus}(s_{r,i})$가 성립하고, 따라서 예전 박스를 이동시킨 사본은 새 박스에 포함됩니다:

$$\mathbf{t}_r + \operatorname{Box}(\mathbf{c}, \mathbf{o}) \;=\; \operatorname{Box}(\mathbf{c} + \mathbf{t}_r,\ \mathbf{o}) \;\subseteq\; \operatorname{Box}\bigl(\mathbf{c} + \mathbf{t}_r,\ \mathbf{o} + \operatorname{softplus}(\mathbf{s}_r)\bigr).$$

어떤 그래디언트 단계도 홉이 영역을 줄이도록 가르칠 수 없고, 오직 이동시키고 많든 적든 키우도록만 가르칠 수 있으며, 이는 의미론과 정확히 맞아떨어집니다: 더 긴 존재 한정 사슬은 적어도 그만큼 더 흩어진 증인(witness) 집합에 의해서만 만족될 수 있습니다.

한 가지 실무적인 골칫거리가 있습니다: EPFO 질의는 엣지를 거꾸로 걸어야 할 때가 있습니다. "누가 p1을 저술했는가?"는 authored 관계를 꼬리에서 머리로 순회합니다. 방향을 특수 사례로 처리하는 대신, 이 모듈은 관계 어휘를 두 배로 늘려, 5개의 기본 관계 각각에 형식적인 역관계를 부여합니다(boxes.py 70–77번째 줄):

REL10: list[str] = RELATIONS + [f"{r}_inv" for r in RELATIONS]
REL_ID: dict[str, int] = {r: i for i, r in enumerate(REL10)}
assert len(REL10) == 10 and all(REL_ID[r] == R_ID[r] for r in RELATIONS)


def _with_inverses(triples: list[tuple[str, str, str]]) -> list[tuple[str, str, str]]:
    """The triples plus, for each (h, r, t), the inverse triple (t, r_inv, h)."""
    return list(triples) + [(t, f"{r}_inv", h) for h, r, t in triples]

모든 훈련 트리플 $(h, r, t)$는 $(t, r_{\text{inv}}, h)$도 함께 훈련시키므로, kg.py의 15개 훈련 트리플은 30개의 방향 있는 양성 예제(positive)가 되고, authored_inv(p1, ?)("누가 p1을 저술했는가?") 같은 질의는 그저 하나의 순방향 투영일 뿐입니다.

교집합은 박스에 대해 정확하다

이제 진짜 성과를 볼 도형입니다. 두 박스 $A = \operatorname{Box}(\mathbf{c}^A, \mathbf{o}^A)$와 $B = \operatorname{Box}(\mathbf{c}^B, \mathbf{o}^B)$를 놓고, 모서리 벡터를 $\mathbf{l}^A = \mathbf{c}^A - \mathbf{o}^A$, $\mathbf{u}^A = \mathbf{c}^A + \mathbf{o}^A$로, $B$에 대해서도 마찬가지로 정의합니다. 한 점이 집합 교집합 $A \cap B$ 안에 있다는 것은 정확히 두 소속 검사를 모두 만족한다는 뜻이고, 두 검사 모두 차원별 구간 제약이므로, 각 $i$에 대해

$$l^A_i \le v_i \le u^A_i \ \ \text{and}\ \ l^B_i \le v_i \le u^B_i \quad\Longleftrightarrow\quad \max\bigl(l^A_i, l^B_i\bigr) \,\le\, v_i \,\le\, \min\bigl(u^A_i, u^B_i\bigr),$$

가 성립합니다. 두 아래 경계를 모두 만족하는 것은 그중 더 큰 쪽을 만족하는 것과 같고, 두 위 경계를 모두 만족하는 것은 그중 더 작은 쪽을 만족하는 것과 같기 때문입니다. 우변 자체도 차원마다 하나의 구간 제약입니다. 따라서 $A \cap B$는 그 자체로 하나의 축에 정렬된 박스이며, 그 모서리는

$$\mathbf{l}^{\cap} = \max\bigl(\mathbf{l}^A, \mathbf{l}^B\bigr), \qquad \mathbf{u}^{\cap} = \min\bigl(\mathbf{u}^A, \mathbf{u}^B\bigr)$$

을 성분별로 취한 것이고, 어떤 차원 $i$에서든 $l^{\cap}_i \gt u^{\cap}_i$이면 정확히 그때 공집합이 됩니다(아래 끝이 위 끝보다 높은 구간은 아무것도 담지 않습니다). 이것이 증명의 전부입니다: 박스는 교집합에 대해 닫혀 있고, 질의의 논리곱은 영역의 교집합이며, 이 연산의 비용은 차원마다 최댓값 하나와 최솟값 하나입니다. 중심-오프셋 형태로 다시 바꾸려면, 시연 코드가 순위를 매기기 전에 하듯이 $\mathbf{c}^{\cap} = (\mathbf{l}^{\cap} + \mathbf{u}^{\cap})/2$와 $\mathbf{o}^{\cap} = (\mathbf{u}^{\cap} - \mathbf{l}^{\cap})/2$를 취하면 됩니다(boxes.py 350번째 줄). 공과 원뿔의 공(ball)들과 대조해 보십시오: 겹치는 두 공의 교집합은 날카로운 테두리를 가진 렌즈 모양이고, 어떤 공도 이와 같지 않으며, 그것을 둘러싸는 어떤 공도 거짓 양성(false positive)을 허용합니다. 박스는 축 정렬(기울일 수 없음)이라는 대가를 치르고 이 닫힘성을 얻으며, 교집합 아래에서 박스들의 계열은 완전한 격자(lattice) 구조를 이루어 확률 측도를 뒷받침하는데, 이는 질의 응답과는 독립적으로 발전해 온 흐름입니다 [4].

동반 모듈은 이 정확한 연산을 구현하며, 그 독스트링에는 원래 시스템에 관한 중요한 정직한 기록이 담겨 있습니다(boxes.py 165–174번째 줄):

def intersect(box_a: Box, box_b: Box) -> tuple[np.ndarray, np.ndarray, bool]:
    """The *exact* geometric intersection, as (lower, upper, empty): elementwise
    max of the lower corners, min of the upper corners; the region is empty iff
    lower > upper in any dimension.  (Query2Box instead *learns* intersection —
    attention over the operand centers plus a DeepSets network that shrinks the
    offsets — which can never return an empty box; the exact operation here is
    the set semantics that learned operator approximates.)"""
    (la, ua), (lb, ub) = corners(box_a), corners(box_b)
    lower, upper = np.maximum(la, lb), np.minimum(ua, ub)
    return lower, upper, bool(np.any(lower > upper))

발표된 Query2Box는 정확한 모서리 공식을 쓰지 않습니다. 그것은 교집합 연산자를 학습합니다: 새 중심은 피연산자 중심들의 어텐션 가중 평균이고, 새 오프셋은 피연산자 오프셋들의 성분별 최솟값을 DeepSets 네트워크(피연산자 집합에 대한 순열 불변 함수)로 줄인 것입니다 [1]. 이 학습된 연산자는 어디서나 미분 가능하고 피연산자 박스가 다소 부정확하게 놓여도 관대하지만, 결코 공집합 박스를 돌려줄 수 없고, 따라서 공집합을 보고할 수도 없습니다: 논리적 명확함을 훈련 가능성과 맞바꾼 것입니다. 우리 모듈이 정확한 연산을 택한 이유는 이 규모에서 집합 의미론을 수치적으로 검증하고 싶기 때문이며, 정확한 교집합이야말로 학습된 연산자가 근사하려는 명세(specification)입니다.

훈련: 마진 손실과 그 하위그래디언트

모델은 세 개의 매개변수 블록을 가지며, 모두 합쳐 264개의 숫자입니다:

블록	모양	개수	역할
개체 점 $V$	$13 \times 8$	$104$	개체마다 점 하나
이동 $T$	$10 \times 8$	$80$	관계마다의 중심 이동(기본 5개 + 역관계 5개)
원시 너비 $S$	$10 \times 8$	$80$	관계마다의 오프셋 증가분 $\operatorname{softplus}(S)$
합계		$\mathbf{264}$

훈련은 오직 1홉 질의만을 지도합니다. 방향 있는 각 양성 예제 $(h, r, t)$는 다음 요구로 읽힙니다: 질의 박스 $q = P_r(\operatorname{point}(h))$(중심은 $\mathbf{c} = \mathbf{v}_h + \mathbf{t}_r$이고 오프셋은 $\mathbf{o} = \operatorname{softplus}(\mathbf{s}_r)$입니다. 점은 오프셋이 0이므로, 관계의 확장분이 오프셋 전체가 됩니다)는 $t$의 점을 가까이 붙잡고 표본으로 뽑힌 비답(non-answer)은 멀리 밀어내야 합니다. 균등하게 표본으로 뽑힌 음성 꼬리(negative tail) $\tilde{t}$ 하나를 사용하며, 이미 참으로 알려진 트리플을 이루는 동안에는 다시 표본을 뽑아 진짜 답이 결코 밀려나지 않도록 합니다(boxes.py 222–224번째 줄). 예제마다의 마진 손실(margin loss)은

$$L \;=\; \max\Bigl(0,\ \ \gamma \;+\; \operatorname{dist}\bigl(\mathbf{v}_t;\, \mathbf{c}, \mathbf{o}\bigr) \;-\; \operatorname{dist}\bigl(\mathbf{v}_{\tilde{t}};\, \mathbf{c}, \mathbf{o}\bigr)\Bigr),$$

이며, 마진은 $\gamma = 1.75$입니다(boxes.py 47번째 줄): 음성 예제는 박스로부터 양성 예제보다 적어도 $\gamma$만큼 더 멀리 있어야 하고, 일단 그렇게 되면 손실은 0이 되고 그 예제는 더 이상 건드리지 않습니다. 두 거리를 줄여 $d_{\text{pos}} = \operatorname{dist}(\mathbf{v}_t;\, \mathbf{c}, \mathbf{o})$, 즉 참인 꼬리가 질의 박스에서 떨어진 거리와, $d_{\text{neg}} = \operatorname{dist}(\mathbf{v}_{\tilde{t}};\, \mathbf{c}, \mathbf{o})$, 즉 표본으로 뽑힌 음성 예제의 거리로 씁니다; 이것이 코드의 d_pos와 d_neg입니다(boxes.py 227–228번째 줄). 그래디언트를 구하려면 $\partial \operatorname{dist} / \partial \mathbf{v}$와 $\partial \operatorname{dist} / \partial \mathbf{o}$, 즉 편미분(partial derivative)이 필요하고(기호 $\partial$는 나머지를 모두 고정한 채 $\mathbf{v}$ 또는 $\mathbf{o}$의 좌표 하나가 움직일 때 거리가 얼마나 빨리 변하는지를 묻습니다), 거리는 꺾인 지점을 가진 $\max$와 $\min$으로 이루어져 있습니다. 차원별로 하나씩 계산해 봅시다. $\operatorname{diff}_i = v_i - c_i$, $a_i = \lvert \operatorname{diff}_i \rvert$, $s_i = \operatorname{sign}(\operatorname{diff}_i)$(부호는 $+1$, $-1$, $0$ 중 하나입니다)로 씁니다. 꺾인 지점에서 벗어나 있으면, 절댓값을 관통하는 연쇄 법칙에 의해 $\partial a_i / \partial v_i = s_i$이고, 거리의 각 항은 경우를 나누어 미분됩니다:

• 바깥쪽 항 $\max(0,\, a_i - o_i)$. $a_i \gt o_i$이면 max는 두 번째 인자를 취하므로 $\partial/\partial v_i = \partial(a_i - o_i)/\partial v_i = s_i$이고 $\partial/\partial o_i = -1$입니다. $a_i \lt o_i$이면 max는 상수 $0$이 되어 두 미분 모두 사라집니다.
• 안쪽 항 $\alpha \min(a_i,\, o_i)$. $a_i \lt o_i$이면 min은 $a$ 쪽 가지를 취하므로 $\partial/\partial v_i = \alpha\, s_i$이고 $\partial/\partial o_i = 0$입니다. $a_i \gt o_i$이면 $o$ 쪽 가지를 취하므로 $\partial/\partial v_i = 0$이고 $\partial/\partial o_i = \alpha$입니다.

지시자 마스크(indicator mask)로 경우들을 쌓으면($P$가 성립하면 $1$, 아니면 $0$을 $[\,P\,]$로 씁니다):

$$\frac{\partial \operatorname{dist}}{\partial v_i} = s_i\,[\,a_i \gt o_i\,] + \alpha\, s_i\,[\,a_i \lt o_i\,], \qquad \frac{\partial \operatorname{dist}}{\partial o_i} = -\,[\,a_i \gt o_i\,] + \alpha\,[\,a_i \ge o_i\,].$$

이것이 box_dist_grads이며, 마스크 하나하나를 그대로 옮긴 것입니다(boxes.py 122–141번째 줄):

    diff = v - c
    a, s = np.abs(diff), np.sign(diff)
    m_out = (a > o).astype(float)          # outside-active dimensions
    m_in_v = (a < o).astype(float)         # inside min takes the a-branch
    g_v = s * m_out + ALPHA * s * m_in_v
    g_o = -m_out + ALPHA * (1.0 - m_in_v)  # o-branch mask = (a >= o) = 1 - m_in_v
    return g_v, g_o

꺾인 지점에서 정확히 무슨 일이 일어나며, 왜 안전한가. $a_i = o_i$에서 $a_i$에 대한 좌우 편미분은 서로 어긋납니다: 내부에서는 $\alpha$, 외부에서는 $1$입니다(바깥쪽 항이 깨어나고 안쪽 항은 얼어붙습니다). 그럼에도 거리는 그 지점에서 여전히 연속이므로(양쪽 극한이 $\alpha\, o_i$에서 일치했습니다), 이 함수는 절벽이 아니라 꺾임을 가지며, 꺾인 지점에서는 두 좌우 기울기 사이의 어떤 값이든 유효한 하위그래디언트(subgradient)입니다: 그 근방에서 함수보다 아래에 머무르는 선형 외삽을 주는 기울기이며, 이는 하강 단계가 평균적으로 진전을 이루는 데 필요한 전부입니다. 코드의 엄격한 마스크는 동점에서 혼합된 선택을 합니다($m_{\text{out}} = 0$은 바깥쪽 항을 비활성으로 취급하고, min은 $o$ 쪽 가지를 취합니다. boxes.py 132–134번째 줄의 독스트링대로입니다), 그래서 축별 쌍 $(g_{v_i}, g_{o_i}) = (0, \alpha)$를 돌려줍니다. 정직하게 말하자면 이 혼합된 쌍 자체는 하위그래디언트 집합의 원소가 아닙니다: 동점에서 유효한 기울기의 범위는 $v_i$에서는 $\alpha\, s_i$부터 $s_i$까지, $o_i$에서는 $\alpha - 1$부터 $0$까지인데, 돌려준 $0$은 $s_i \neq 0$일 때마다 첫 번째 구간을 벗어나고, 돌려준 $\alpha = 0.2$도 두 번째 구간을 벗어납니다(부호마저 틀렸습니다). 이 선택이 무해한 이유는 더 투박한 것입니다: 동점 $a_i = o_i$는 측도 0인 사건, 즉 실숫값을 갖는 반복값(iterate)에서는 확률 0으로 일어나는 사건이므로, 실제로 훈련 루프는 결코 그 지점에 정확히 도달하지 않으며, 어느 가지를 고르든 그것이 결정하는 것은 정확성이 아니라 재현성입니다. (어차피 볼록성 보장은 애초부터 없었습니다: 각 거리는 $\mathbf{v}$와 $\mathbf{o}$ 각각에 대해서는 볼록하지만, 점 $V$, 이동 $T$, 원시 너비 $S$에 걸친 결합 목적함수는 비볼록입니다.) 같은 논리가 $\operatorname{diff}_i = 0$에서 절댓값의 꺾인 지점에도 적용되는데, 여기서 NumPy의 $\operatorname{sign}(0) = 0$은 0인 하위그래디언트를 고르며, 이는 $\lvert \cdot \rvert$ 꺾임의 바닥에서 어떤 1차 이동도 도움이 되지 않을 때의 합리적인 선택입니다.

경첩(hinge)이 활성일 때($L \gt 0$이므로 $\partial L / \partial d_{\text{pos}} = +1$, $\partial L / \partial d_{\text{neg}} = -1$입니다) 세 번의 연쇄 법칙 도약이 매개변수 그래디언트를 조립합니다:

1. 중심. 거리는 오직 $\operatorname{diff} = \mathbf{v} - \mathbf{c}$를 통해서만 $\mathbf{v}$와 $\mathbf{c}$에 의존하고, $\partial \operatorname{diff}_i / \partial c_i = -1$이면서 $\partial \operatorname{diff}_i / \partial v_i = +1$이므로 $\partial \operatorname{dist} / \partial \mathbf{c} = -\,\partial \operatorname{dist} / \partial \mathbf{v}$입니다: 중심의 그래디언트는 점의 그래디언트에 부호를 뒤집은 것입니다.
2. 머리와 이동. $\mathbf{c} = \mathbf{v}_h + \mathbf{t}_r$는 단순한 합이므로, $\mathbf{v}_h$와 $\mathbf{t}_r$ 둘 다 중심의 그래디언트를 그대로 받습니다(야코비안(Jacobian), 즉 출력 벡터를 한 입력 벡터로 편미분하여 얻는 행렬은, 단순한 합에서는 각 인자에 대해 항등 행렬입니다).
3. 원시 너비. $\mathbf{o} = \operatorname{softplus}(\mathbf{s}_r)$가 성분별로 성립하므로, $\operatorname{softplus}'$가 필요합니다. $\ln(1 + e^{x})$를 미분하면, 연쇄 법칙에 의해 $\frac{e^{x}}{1 + e^{x}}$가 나오고, 분자와 분모에 $e^{-x}$를 곱하면 이는 $\frac{1}{e^{-x} + 1} = \sigma(x)$, 즉 시그모이드(sigmoid)가 됩니다(boxes.py 99–102번째 줄). 따라서 $\partial L / \partial s_{r,i} = (\partial L / \partial o_i)\, \sigma(s_{r,i})$입니다.

내부 루프는 정확히 이것들을 적용하며, 갱신식 $\theta \leftarrow \theta - \eta\, \partial L / \partial \theta$에서 학습률은 $\eta = 0.05$이고, $\theta$는 세 매개변수 블록($V$, $T$, $S$) 가운데 지금 조정되는 블록을 두루 가리키는 기호입니다(boxes.py 233–246번째 줄):

            # Active hinge: dL/dtheta = d d_pos/dtheta - d d_neg/dtheta.
            gv_p, go_p = box_dist_grads(V[ti], c, o)
            gv_n, go_n = box_dist_grads(V[ni], c, o)
            # dL/dv_t = +(d d_pos/dv);  dL/dv_neg = -(d d_neg/dv).
            # dL/dc   = -(d d_pos/dv) + (d d_neg/dv)   [d dist/dc = -d dist/dv],
            #           and c = v_h + t_r, so v_h and t_r share this gradient.
            # dL/ds_r = (d d_pos/do - d d_neg/do) * sigmoid(s_r)
            #           [chain rule through o = softplus(s_r), softplus' = sigmoid].
            g_c = -gv_p + gv_n
            V[ti] -= LR * gv_p
            V[ni] += LR * gv_n
            V[hi] -= LR * g_c
            T[ri] -= LR * g_c
            S[ri] -= LR * (go_p - go_n) * sigmoid(S[ri])

음성 개체 갱신의 부호에 주목하십시오: $\partial L / \partial \mathbf{v}_{\tilde{t}} = -\,\partial d_{\text{neg}} / \partial \mathbf{v}$이므로, $L$을 따라 하강한다는 것은 $\eta\, \mathbf{g}_{v}^{\text{neg}}$를 더한다는 뜻이며, 이는 표본으로 뽑힌 비답을 박스에서 밀어내는 것입니다. 이름을 붙일 만큼 중요한 초기화 선택이 두 가지 있습니다. 점들은 작게 시작하고(INIT = 0.3, boxes.py 52–58번째 줄), 박스가 놓일 자리 근처에 모여 있으므로, 개체는 어떤 그래디언트가 명시적으로 밀어낼 때에만 박스를 벗어납니다. 그다음 알려진-참 음성 필터는 advises(bob, ?)의 dave처럼 유보된 답이, 그것이 실제로 속하는 박스에서 결코 직접적으로 밀려나지 않도록 보장합니다; 이 필터가 부수효과로 인한 표류(drift)를 막지는 못합니다(dave의 점은 dave가 다른 질의의 음성으로 뽑힐 때마다 여전히 움직입니다), 하지만 이번 실행에서는 작은 시작값과 필터가 함께 작용해 dave가 안쪽에 머무르기에 충분했고, 관찰된 이 메커니즘이야말로 보지 못한 답에 대한 일반화가 나오는 지점입니다. 원시 너비는 $s = -1$에서 시작하므로, 모든 오프셋은 $\operatorname{softplus}(-1) \approx 0.313$에서 시작합니다: 박스는 좁게 시작해 자신의 양성 예제를 덮으려면 커져야 하며, 이는 최종 영역이 공허하게 커지는 대신 또렷하게 남도록 해 줍니다(boxes.py 59–61번째 줄). 모듈을 실행하면(python3 boxes.py) 커밋된 실행 추이가 출력됩니다:

training (manual gradients: margin 1.75, lr 0.05, 1 negative per positive, seed 0)
  epoch    1  mean margin loss 1.6447
  epoch  100  mean margin loss 0.0103
  epoch  500  mean margin loss 0.0000
  epoch 1000  mean margin loss 0.0000
  epoch 1500  mean margin loss 0.0000
  held-out link prediction (filtered): MRR 0.9167  hits@1 0.8333  ranks [1, 1, 1, 1, 1, 2]

첫 에폭의 평균 손실 $1.6447$은 마진 $\gamma = 1.75$ 바로 아래에 있으며, 이는 무작위 시작이 어떤 모습인지를 보여 줍니다: 양성과 음성은 처음에는 모든 박스로부터 거의 같은 거리에 있으므로, 경첩은 평균적으로 거의 완전히 열려 있습니다. 100 에폭에 이르면 평균 손실은 $0.0103$이 되고, 500 에폭부터는 30개의 방향 있는 양성 예제 전부가 마진을 정확히 넘어섭니다. I부와의 정합성 다리로서, 훈련된 박스들은 kg.py(110–122번째 줄)의 공유된 필터링 하니스를 통해 링크 예측기 역할도 겸합니다. 꼬리가 1홉 박스로부터 떨어진 거리에 부호를 뒤집어 트리플을 점수 매기면: 유보된 여섯 개의 순위 질의 가운데 다섯 개가 1위에 오고 하나가 2위에 올라, 필터링된 평균 역순위(Mean Reciprocal Rank)는 $0.9167$입니다.

세 개의 질의, 기하학적으로 답하다

이제 진짜 성과를 볼 차례입니다. 이 모듈은 오직 기하학만으로 세 개의 EPFO 질의에 답하고(박스를 짓고, box_dist로 13개 개체 전부의 순위를 매깁니다), 각각을 기호적 정답(symbolic ground truth)과 대조합니다: 이는 sym_tails를 통해 유보된 시험 엣지를 포함한 18개 트리플 전체에 대한 그래프 순회로 계산된 답 집합입니다(boxes.py 185–192번째 줄). 정답은 가정된 것이 아니라 계산된 것이며, 비교 규칙은 엄격합니다: 정답 집합의 크기를 $k$라 할 때, 기하학적으로 매긴 상위 $k$개 집합이 정답 집합과 정확히 일치해야 합니다.

q1 (1p): advises(bob, ?)는 bob의 점에서 시작하는 하나의 투영입니다. 순회는 답이 carol과 dave라고 말하며, 흥미로운 쪽은 후자입니다: 엣지 (bob, advises, dave)는 결코 훈련에 쓰이지 않은 유보된 시험 트리플이므로, dave를 되찾아 내는 것은 암기가 아니라 일반화입니다. 실행 결과:

q1 (1p)  advises(bob, ?)
  symbolic answers (traversal over all 18 triples): ['carol', 'dave']
  geometric top-4 by box distance:
    1. carol  0.1876  <- gold
    2. dave   2.2971  <- gold
    3. bob    2.3359
    4. erin   2.4306
  top-2 set equals the symbolic set: True

q2 (2p): advises(alice, Y) ∧ advises(Y, ?), 즉 alice의 지도학생의 지도학생들은 두 개의 연쇄된 투영입니다: $P_{\text{advises}}(P_{\text{advises}}(\operatorname{point}(\text{alice})))$. 순회는 중간 집합 $Y = \{$bob$\}$과 답 집합 $\{$carol, dave$\}$를 내놓습니다:

q2 (2p)  advises(alice, Y) . advises(Y, ?)
  symbolic answers (traversal over all 18 triples): ['carol', 'dave']
  geometric top-4 by box distance:
    1. carol  0.2436  <- gold
    2. erin   1.2500
    3. dave   1.5862  <- gold
    4. bob    1.6437
  top-2 set equals the symbolic set: False

이는 정직한 실패이며 자세히 읽어 볼 가치가 있습니다: 두 정답 모두 13개 중 상위 3위 안에 들지만, erin이 2위에 끼어들고, erin은 무작위로 끼어든 침입자가 아닙니다. 그래프에는 (carol, advises, erin)이 들어 있으므로, erin은 정확히 advises 박스가 놓이는 자리에 사는 종류의 점, 즉 지도학생 모양의 개체입니다; 두 번의 확장을 거친 뒤 2p 박스는 erin의 점이 dave의 점보다 살짝 더 가깝게 놓일 만큼 넓어져 있습니다. 박스는 두 홉의 확장이 반드시 해야 하는 일, 즉 커지는 일을 했고, 그 결과 근접한 이웃 하나가 순위 안으로 미끄러져 들어왔습니다.

q3 (2i): authored_inv(p1, ?) ∧ advises(alice, ?), 즉 "누가 p1을 저술했고 그리고 alice에게 지도받는가?"는 교집합 질의입니다. 각 논리곱 성분은 하나의 1p 박스이며, 모서리별 정확한 교집합이 이를 결합합니다:

q3 (2i)  authored_inv(p1, ?) AND advises(alice, ?)
  operand traversal: authored_inv(p1,?) = ['alice', 'bob'], advises(alice,?) = ['bob'], intersection = ['bob']
  box A lower [0.507 -0.017 -1.452 -1.158 1.010 -0.229 -0.204 -0.184]
        upper [1.020 0.587 -0.820 -0.585 1.587 0.289 0.354 0.478]
  box B lower [0.241 -0.131 -0.863 -0.836 0.542 -0.550 -0.503 -0.154]
        upper [0.767 0.334 -0.358 -0.309 1.129 0.145 0.141 0.450]
  exact intersection (nonempty):
        lower [0.507 -0.017 -0.863 -0.836 1.010 -0.229 -0.204 -0.154]
        upper [0.767 0.334 -0.820 -0.585 1.129 0.145 0.141 0.450]
  closure on 20 sampled points: inA=10 inB=10 inA&B=4 inI=4 mismatches=0

1차원에서 모서리 계산을 정리와 대조해 봅시다: 박스 A의 아래 모서리는 $0.507$, 박스 B의 아래 모서리는 $0.241$이고, 교집합의 아래 모서리는 $\max(0.507, 0.241) = 0.507$입니다; 위 모서리는 각각 $1.020$과 $0.767$이고, 교집합의 위 모서리는 $\min(1.020, 0.767) = 0.767$입니다. 출력된 모든 좌표가 최댓값/최솟값 규칙을 따르고, 어느 차원에서도 아래 모서리가 위 모서리보다 크지 않으므로, 이 영역은 공집합이 아닙니다. 그다음 폐쇄성 검사(closure check)는 흥미로운 경우들에 걸쳐 시드로 고정된 20개의 점을 표본으로 뽑아(A 내부 6개, B 내부 6개, 교집합 내부 4개, 전체를 둘러싼 여유 있는 외피에서 4개; boxes.py 359–377번째 줄), 교집합 박스에 속하는 것이 A에 속하는 것 그리고 B에 속하는 것과 같은지를 점 하나하나 검증합니다: 10개의 점이 A 안에, 10개가 B 안에, 정확히 4개가 둘 다 안에 놓였고, 정확히 그 4개가 교집합 박스 안에 놓여, 불일치는 0건입니다. 이것이 바로 논리곱의 집합 의미론이 수치적으로 성립하는 모습입니다. 교집합 박스에 대한 순위 매김 결과:

q3 (2i)  ranked by distance to the intersection box
  symbolic answers (traversal over all 18 triples): ['bob']
  geometric top-4 by box distance:
    1. bob    0.5525  <- gold
    2. alice  2.5787
    3. carol  3.6868
    4. p1     3.7172

bob은 1위로 되찾아지며 2위와 큰 격차를 보입니다($0.5525$ 대 $2.5787$), 그리고 2위는 alice, 즉 p1의 또 다른 저자로서 두 논리곱 성분 중 하나만 만족하고 둘 다는 만족하지 않는 개체입니다. 이 모듈의 컴피턴시 검사(competency assert)는 이 모든 것을 코드로 못 박습니다: 교집합의 정답 집합은 앞선 두 투영 질의, 즉 q1과 q2의 정답 집합과 달라야 하며, 그래서 이 교집합 시연이 이미 답한 질의를 다시 실행하는 것이 아니게 됩니다(단, 피연산자 하나의 집합과는 일치할 수 있고 실제로 여기서 그렇습니다: advises(alice, ?)는 이미 정확히 bob만을 돌려줍니다); 세 질의 중 적어도 둘은 정답 집합을 정확히 되찾아야 하며; 폐쇄성 검사는 불일치가 0건이어야 합니다(boxes.py 390–398번째 줄).

질의	형태	기호적 답(순회)	기하학적 상위 $k$개, $k = \lvert\text{gold}\rvert$	정확히 일치
advises(bob, ?)	1p	carol, dave	carol ($0.1876$), dave ($2.2971$)	예
advises(alice, Y) ∧ advises(Y, ?)	2p	carol, dave	carol ($0.2436$), erin ($1.2500$)	아니오: dave는 3위
authored_inv(p1, ?) ∧ advises(alice, ?)	2i	bob	bob ($0.5525$)	예

결과를 정직하게 읽기

세 질의 중 둘은 기호적 정답 집합을 정확히 되찾았고, 셋째는 두 정답 모두를 13개 중 상위 3위 안에 두었으며, 정확한 교집합은 정리가 요구하는 대로 정확히 작동했습니다. 이는 이 계산법의 진짜 시연입니다: 투영, 연쇄, 논리곱이 모두 기하학으로 실행되었고, q1에서는 유보된 답으로의 일반화까지 있었습니다. 이것은 벤치마크 결과가 아닙니다. 13개의 개체는 12개의 방해 요소를 가진 순위 매김 과제일 뿐이며, 모델은 264개의 매개변수를 가지고 훈련 중에 모든 개체를 보았습니다. Query2Box가 실제로 사는 서식지는 FB15k, FB15k-237, NELL995 규모의 지식 그래프, 즉 수만 개의 개체를 가진 그래프이며, 그곳에서는 질의가 아홉 가지 의존 그래프 형태에 걸쳐 생성되고 모델은 만 오천 개의 후보에 맞서 순위를 매깁니다 [1]. 그 규모에서는 학습된 어텐션 교집합이 정확한 교집합보다 제 몫을 해내며(피연산자 박스가 불완전하므로, 관대한 겹침이 더 잘 일반화됩니다), 논리합은 재작성 정리로 처리됩니다: 어떤 EPFO 질의든 순수하게 논리곱으로만 이루어진 가지들의 합집합인 논리합 표준형(disjunctive normal form)으로 변환될 수 있으므로, 합집합은 각 가지를 자신만의 박스로 임베딩하고 가지들에 걸쳐 최소 거리를 취함으로써 답해집니다 [1]. 영역이 유일한 패러다임도 아닙니다: 같은 질의들은 ComplEx 같은 평범한 1홉 예측기를 그대로 두고, 그 점수를 퍼지 논리곱(t-노름)으로 합성하면서 중간 변수에 대해 빔 탐색(beam search)을 수행하는 방식으로도 답할 수 있는데, 이 경우 질의 연산자는 전혀 훈련되지 않으며, 표준 벤치마크에서 이 합성 방식은 강력한 경쟁자입니다 [3]. 박스 계산법은 다른 축에서 이깁니다: 중간 배정에 대한 탐색 대신, 질의마다 하나의 기하학적 대상과 한 번의 최근접 이웃 훑기만 있으면 됩니다.

아직 풀리지 않은 부분

박스는 논리곱에 대한 닫힘성을 사 오지만, 그 대가는 논리 연산자 하나만 더 지나면 드러납니다: 부정이 없다는 것입니다. 박스의 여집합은 박스가 아닙니다. 1차원에서 이는 이미 훤히 보입니다: 구간 $[l, u]$의 여집합은 두 개의 반직선, 즉 $l$ 아래의 모든 것과 $u$ 위의 모든 것의 합집합이며, 어떤 단일 구간도 이를 나타낼 수 없습니다; $d$차원에서 여집합은 박스를 $2d$개의 모든 면에서 둘러싸며 무한히 뻗어 나가, 집합이 박스답지 않을 수 있는 만큼 박스답지 않습니다. 그래서 "cmu에 소속되어 있고 그리고 bob에게 지도받지 않는다" 같은 질의는 이 계산법 안에 자리가 없습니다: 박스는 교집합에 대해서는 닫혀 있지만 여집합에 대해서는 닫혀 있지 않고, Query2Box가 다루는 부류인 EPFO는 정확히 부정을 배제함으로써 정의됩니다 [1]. 더 조용한 두 번째 한계도 있습니다: 정확한 교집합은 공집합임을 보고할 수 있지만, 규모가 커졌을 때 그것을 대체하는 어텐션 연산자는 결코 공집합 박스를 내놓지 않으므로, 훈련된 모델은 결코 "이 질의에는 답이 없다"고 말할 수 없습니다. 부정을 표현하고 "답 없음"을 본디부터 표현하는 기하학은 꽉 찬 영역보다 더 풍부한 대상이 필요합니다; 다음 장은 영역을 확률분포로 대체하며, 그곳에서 여집합은 정확한 매개변수 사상이 됩니다.

왜 중요한가

이 장은 신경-기호(neuro-symbolic) 프로그램 전체에 중요한 하나의 선을 넘었습니다: 이 권에서 처음으로, 원자 하나가 아니라 복합 논리식이 온전히 임베딩 공간 안에서 실행되었습니다. 논리곱은 최댓값/최솟값 연산으로 실행되었고, 존재 한정은 이동-후-확장으로 실행되었으며, 그 결과는 눈대중이 아니라 순회로 얻은 정답과 대조되어 검증되었습니다. 이는 4권이 미분 가능한 추론(differentiable reasoning)에 의한 복합 질의 응답으로 다룰 것의 배아 형태입니다: 논리 구조가 기하학적 연산자로 컴파일되고, 그래디언트로 훈련되며, 순위 매김으로 평가됩니다. 이 장은 또한 II부의 설계 교훈을 더 날카롭게 다듬었습니다: 저장해야 할 대상뿐 아니라 지원해야 할 연산에 맞추어 표현 계열을 골라야 한다는 것입니다. 공은 개념을 아름답게 저장하지만 논리곱에서 실패하고, 박스는 논리곱을 정확히 처리하지만 부정에서 실패합니다; 질의 언어에 추가되는 모든 연산자는 기하학에 대한 닫힘성 요구입니다. 그리고 여기서의 폐쇄성 검사, 즉 최댓값/최솟값 규칙을 따르는 모서리들과 소속 불일치가 0건인 20개의 표본 점은, 이 시리즈가 계속 고집해 온 하나의 규율의 작은 사례입니다: 신경망 구조가 어떤 논리 연산을 구현한다고 주장할 때는, 그 주장을 기호적 오라클(oracle)에 맞서 검증하라는 것입니다.

핵심 용어

• EPFO 질의(existential positive first-order, 실존 긍정 1차): 논리곱, 논리합, 존재 한정으로 지어지고 부정은 없는, 관계 원자들로 이루어진 질의입니다. 그 답은 개체들의 집합입니다.
• 박스 임베딩(Box embedding): 중심 $\mathbf{c}$, 음이 아닌 차원별 오프셋 $\mathbf{o}$, 모서리 $\mathbf{c} \pm \mathbf{o}$를 갖는 축에 정렬된 영역 $\operatorname{Box}(\mathbf{c}, \mathbf{o})$입니다.
• Query2Box 거리(Query2Box distance): $\operatorname{dist}_{\text{outside}} + \alpha \cdot \operatorname{dist}_{\text{inside}}$이며, 박스 표면까지의 L1 거리에 중심으로의 $\alpha$로 할인된 끌림을 더한 것입니다; 바깥쪽 항이 0이면 소속을 뜻합니다.
• 관계 투영(Relation projection): $P_r(\mathbf{c}, \mathbf{o}) = (\mathbf{c} + \mathbf{t}_r,\ \mathbf{o} + \operatorname{softplus}(\mathbf{s}_r))$이며, 이동은 영역을 옮기고, softplus로 양수가 보장된 확장은 한 홉이 영역을 키우기만 할 수 있음을 보장합니다.
• 역관계(Inverse relation): 뒤집힌 엣지 위에서 훈련되는 형식적 관계 $r_{\text{inv}}$로, 질의가 엣지를 거꾸로 순회할 수 있도록 관계 어휘를 두 배로 늘립니다.
• 정확한 박스 교집합(Exact box intersection): 아래 모서리는 $\max(\mathbf{l}^A, \mathbf{l}^B)$, 위 모서리는 $\min(\mathbf{u}^A, \mathbf{u}^B)$이며 성분별로 계산됩니다; 어떤 아래 모서리가 그 위 모서리를 넘으면 정확히 그때 공집합입니다.
• 서브그래디언트(Subgradient): 연속인 조각별 선형 함수의 볼록한 꺾인 지점(왼쪽 기울기가 오른쪽 기울기보다 작은 곳)에서는 두 단측 도함수 사이의 어떤 기울기든 서브그래디언트입니다. 한쪽의 도함수 전체를 취하는 것도 타당한 선택이며, 코드가 항마다 양쪽을 섞어 고르는 방식조차 실제 실행에서는 동점을 만나지 않으므로 해롭지 않습니다.
• 마진(경첩) 손실(Margin (hinge) loss): $\max(0, \gamma + d_{\text{pos}} - d_{\text{neg}})$이며, 음성 예제가 양성 예제보다 박스에서 적어도 $\gamma$만큼 더 멀어지면 손실도 그래디언트도 0이 됩니다.
• 폐쇄성 검사(Closure check): 표본으로 뽑은 점들에서, 교집합 박스에 속하는 것이 두 피연산자 모두에 속하는 것과 같은지를 경험적으로 검증하는 것입니다.
• 논리합 표준형 재작성(DNF rewriting, disjunctive normal form): 어떤 EPFO 질의든 논리곱으로만 이루어진 가지들의 합집합으로 재작성하여, 논리곱만 다루는 기하학이 논리합에 가지별로 답할 수 있게 하는 것입니다.

이 장이 이끄는 곳

박스는 우리에게 그리고를 정확하게, 또는을 재작성을 통해 주었지만, 아님(not) 앞에서 딱 멈추어 섰습니다: 박스의 여집합은 박스가 아니므로, 이런 모양의 순수하게 영역에 기반한 계산법은 그 무엇도 "cmu에 소속되어 있고 bob에게 지도받지 않는다"에 답할 수 없습니다. 다음 장인 베타 및 확률 임베딩은 부정을 사 오는 표현상의 도약을 이루어 냅니다. 모든 개체와 모든 질의는 베타 분포(Beta distribution)의 벡터가 됩니다; 적합도는 닫힌 형식의 쿨백-라이블러 발산(Kullback–Leibler divergence)으로 측정되고, 논리곱은 밀도를 곱해 매개변수가 그저 더해지도록 만들며, 어떤 공도 박스도 표현할 수 없었던 연산인 부정은 정확한 매개변수 사상 $(\alpha, \beta) \mapsto (1/\alpha,\, 1/\beta)$이 됩니다. 영역을 확률분포와 맞바꾸는 대가와 보상이 그 장의 이야기입니다.

---

짝이 되는 코드: examples/neural/boxes.py는 이 장의 모든 것을 구현합니다. 박스 기하(box_dist, project, intersect), 손으로 유도한 하위그래디언트(box_dist_grads), 마진 손실 훈련 루프, 그리고 examples/neural/kg.py의 공유된 그래프와 평가 하니스 위에서 순회로 얻은 정답 및 폐쇄성 검사를 갖춘 세 질의 시연입니다. 위에서 인용한 모든 숫자를 재현하려면 python3 examples/neural/boxes.py를 실행하십시오; 이 모듈의 컴피턴시 검사는 교집합 질의가 앞선 질의의 답 집합을 그저 되풀이하거나, 세 질의 중 정답 집합을 정확히 되찾는 것이 둘 미만이거나, 어떤 폐쇄성 불일치라도 나타나면 실행을 실패시킵니다.