기술 요약: 머신러닝 모델을 위한 쿼리 언어

문제 정의

본 논문은 본질적으로 이산적 구조(그래프 토폴로지)와 연속적인 수치 성분(가중치 및 편향)이 결합된 하이브리드 모델인 신경망과 같은 머신러닝(ML) 모델을 공식적으로 분석하고 쿼리하는 과제를 다룹니다. 유한 모델 이론(Finite Model Theory)은 관계형 데이터베이스와 이산적 계산 문제를 성공적으로 분석해 왔으나, 표준 논리들은 가중치가 있는 구조의 동작을 기술하는 데 필요한 수치적 집계(aggregation)와 산술 연산을 처리할 메커니즘이 부족합니다.

기존의 ML 분석 접근 방식은 종종 고정된 일반적 설명 방법(예: 특정 입력에 대한 반사실적 설명)에 의존하거나 모델을 블랙박스로 취급합니다. 저자는 데이터베이스 이론과 유한 모델 이론에 뿌리를 둔 관점을 제안하며, ML 모델을 유연한 논리적 쿼리의 대상이 되는 데이터 구조로 취급해야 한다고 주장합니다. 이를 통해 특정 입력 평가에 국한되지 않고, 로컬 구성 요소의 기능성과 글로벌 시맨틱 속성(예: 강건성, 정확성 또는 함수 공간에 대한 적분)을 모두 조사할 수 있습니다.

방법론

본 논문은 가중 유한 구조(가중치 함수가 확장된 실수 $\mathbb{R}_\perp$로 매핑되는 유한 우주를 가진 구조)를 위해 설계된 두 가지 특정 논리를 조사합니다:

1. FO(SUM): 합산 연산자($\sum$)와 조건부 항이 확장된 1차 논리(First-order logic)입니다. 이 논리는 구조 내의 정의 가능한 집합에 대해 가중치를 집계할 수 있게 합니다.
2. IFP(SUM): 팽창적 고정점 연산자(Inflationary fixed-point operators)를 사용하여 FO(SUM)를 재귀적으로 확장한 것입니다. 이는 신경망의 무제한 깊이를 평가하는 데 필요한 귀납적 과정을 정의할 수 있게 합니다.

방법론은 다음과 같습니다:

• 신경망의 정식화: 피드포워드 신경망(FNN)을 특정 어휘($\{wt, bias, \le_{in}, \le_{out}\}$)를 가진 가중치 유향 비순환 그래프(DAG)로 표현합니다.
• 의미론(Semantics) 정의: 항(term)은 $\mathbb{R}_\perp$의 값으로 평가되고, 공식(formula)은 불리언 값으로 평가되는 가중 구조 상에서의 이 논리들의 의미론을 확립합니다.
• 표현력 분석: FNN의 속성(예: 평가, 파라미터 카운팅, 쓸모없는 엣지 찾기, 적분 계산)이 이러한 논리들로 어떻게 표현될 수 있는지 결정합니다.
• 복잡도 분석: 이러한 쿼리를 평가하는 데이터 복잡도를 고려하여, 균등 회로 복잡도 클래스(예: $\mathsf{TC}^0$)와 다항 시간($\mathsf{P}$)을 모두 분석합니다.
• 모델 불가지론적 쿼리(Model-Agnostic Queries): 네트워크의 특정 아키텍처나 가중치가 아닌, 네트워크가 계산하는 함수($f^N$)에 의해서만 결과가 결정되는 쿼리를 조사하여, "모델 불가지론적" 속성과 "완전한 모델 불가지론적" 속성을 구분합니다.

주요 기여 및 결과

1. FO(SUM)의 표현력

• 유한 깊이 평가: FO(SUM)는 유한한 깊이를 가진 FNN의 평가를 표현할 수 있습니다. 이 논리는 가중 입력을 집계하기 위한 합산과 ReLU 활성화 함수를 시뮬레이션하기 위한 조건부 항을 사용하여 고정된 깊이 $d$까지 노드의 값을 재귀적으로 정의할 수 있습니다.
• 글로벌 속성: 이 논리는 전체 가중치의 총합, "쓸모없는" 엣지 집합(출력을 변경하지 않는 엣지), 그리고 네트워크가 계산하는 함수에 대한 적분(함수의 원통형 셀 분해를 통해)과 같은 글로벌 속성을 정의할 수 있습니다.
• 무제한 깊이에 대한 한계: FO(SUM)는 무제한 깊이를 가진 FNN의 평가 함수를 표현할 수 없습니다. 이 논리는 로컬 속성에 국한되어 있으며, 일반적인 FNN 평가에 필요한 무제한 재귀를 시뮬레이션할 수 없습니다.
• 모델 불가지론적 한계: 핵심적인 부정적 결과(정리 3.14)는 모든 FNN 클래스에 대해 모델 불가지론적(동일한 함수를 계산하는 서로 다른 아키텍처에 대해 불변)인 모든 FO(SUM) 문장은 자명하다(모두 참이거나 모두 거짓임)는 것입니다. 따라서 비자명한 모델 불가지론적 쿼리(네트워크가 모든 곳에서 0을 출력하는지 확인하는 것 등)는 무제한 깊이에 대해 FO(SUM)에서 표현될 수 없습니다.
• 유한 깊이 동등성: 그러나 유한한 깊이($N_d(m, 1)$)를 가진 FNN의 경우, FO(SUM)는 놀라울 정도로 강력합니다. 정리 3.18은 함수($f$)에 의해 확장된 실수 위에서의 1차 논리($FO(\mathbb{R}_{lin}, f)$)로 표현 가능한 모든 쿼리가 FO(SUM)에서도 표현 가능하다는 것을 입증합니다. 이는 함수의 원통형 분해의 셀(cell)들에 대한 양화(quantification)를 통해 실수에 대한 양화를 시뮬레이션함으로써 달성됩니다.

2. IFP(SUM)의 표현력

• 무제한 깊이: IFP(SUM)는 고정점 연산자를 도입하여 FO(SUM)의 깊이 제한을 극복합니다. 이는 무제한 깊이를 가진 FNN의 평가 함수를 표현할 수 있습니다(예시 4.1).
• 복잡도 및 스칼라 단편(Scalar Fragments): 표준 고정점 논리가 순서 구조 위에서 다항 시간을 포착하는 것과 달리, 가중 구조 위의 IFP(SUM)는 복잡한 문제에 직면합니다: 항(term)의 크기가 지수적으로 성장할 수 있습니다(예: 반복 제곱). 이를 해결하기 위해, 본 논문은 의도적 심볼(intensional symbols)이 포함된 곱셈과 나눗셈을 제한하는 **스칼라 단편 sIFP(SUM)**를 도입합니다.
  • 정리 4.5: 유리수 가중 구조에 대한 sIFP(SUM)의 데이터 복잡도는 P(다항 시간)에 속합니다.
• 표현력의 한계: BSS 모델에서 다항 시간을 포착함에도 불구하고, IFP(SUM)(및 sIFP(SUM))은 모든 다항 시간 계산 가능한 모델 불가지론적 쿼리를 표현할 수 없습니다. 정리 4.7은 이진 가중치를 가진 $N(1, 1)$에 대해 IFP(SUM)로 표현할 수 없는 다항 시간 결정 가능한 모델 불가지론적 쿼리가 존재함을 보여줍니다. 이러한 제한은 논리가 수치 값에 대해 임의의 계산을 수행할 수 없다는 점(숫자에 대한 변수가 없음)에서 기인합니다.
• 축소된 FNN: 본 논문은 "축소된 FNN"(동형성 유사한 동치 관계로 팩터링된 형태)을 도입합니다. 정리 4.8은 축소된 형태의 가중치의 비트 크기가 유한한 FNN에 대해 sIFP(SUM)가 모든 다항 시간 결정 가능한 모델 불가지론적 쿼리를 포착함을 보여줍니다.

3. 복잡도 결과

• FO(SUM): FO(SUM) 식을 평가하는 데이터 복잡도는 균등 $\mathsf{TC}^0$에 속합니다(정리 3.9). 이 클래스는 임계 게이트(threshold gates)와 반복 덧셈을 허용하며, 이는 필요한 산술 연산에 충분합니다.
• sIFP(SUM): 데이터 복잡도는 P에 속합니다(정리 4.5).

의의 및 주장

본 논문은 자신을 "개인적 관점(personal perspective)"이자 ML에 유한 모델 이론을 적용하기 위한 기초적인 단계로 규정합니다. 주요 의의는 다음과 같습니다:

1. ML 쿼리 작업의 정식화: 블랙박스 평가를 넘어 구조적 및 기능적 분석으로 나아가는, 신경망의 내부 시맨틱을 쿼리하기 위한 엄격한 논리적 프레임워크를 제공합니다.
2. 이산과 연속의 가교: 메타-유한 모델 이론(메타-유한 모델 이론을 하이브리드 구조로 확장하는 것)이 자연스럽게 가중 그래프로 표현되는 신경망에 어떻게 적용될 수 있는지 보여줍니다.
3. 표현력의 한계 규정: 무엇이 논리적으로 표현 가능하고 불가능한지에 대한 명확한 경계를 설정합니다. 특히, 유한 깊이 네트워크는 FO(SUM)를 통해 논리적 분석이 용이하지만, 무제한 깊이는 재귀(IFP)를 요구하는 복잡성을 초래하며 여전히 모델 불가지론적 속성에 관한 근본적인 표현력 장벽에 직면한다는 점을 강조합니다.
4. 복잡도 통찰: 논리적 표현력과 계산 복잡도를 연결하여, 고정점 연산자를 사용하더라도 모든 다항 시간 모델 불가지론적 속성을 포착하려면 가중치의 수치적 비트 크기에 대한 제한이 필요함을 보여줍니다.

저자는 [22, 23]에서 상당한 진전이 있었으나, 특히 임의의 입력 차원으로의 결과 확장, 복잡도 이론적 가정 없는 유한 깊이 가정의 해제, 그리고 서로 다른 집계 연산자 간의 상호 정의 가능성(inter-definability)과 관련된 많은 미해결 과제가 남아 있다고 결론짓습니다. 본 논문은 "설명 가능한 AI(XAI)" 문제를 완전히 해결한다고 주장하는 것이 아니라, 특정 유형의 설명과 검증을 정의하고 분석하기 위한 이론적 도구 세트를 제공하는 데 목적이 있습니다.