지식 컴파일은 Artificial intelligence에서 명제 모델을 사용한 추론의 계산적 난해성을 해결하는 접근 방식의 한 계열이다. 잠재적으로 복잡한 모델에 대해 직접 질의에 응답하는 대신, 모델은 오프라인 단계에서 특정 질의를 다항식 시간 내에 지원하는 컴파일된 표현으로 변환된다. 이 두 단계 과정 - 컴파일 후 질의 응답 - 은 초기 계산 노력을 더 빠르고 예측 가능한 런타임 추론과 맞바꾼다.
핵심 과제는 적절한 컴파일된 표현을 선택하는 데 있으며, 서로 다른 표현은 서로 다른 절충점을 제공한다. 컴파일된 표현을 특징짓는 세 가지 주요 속성은 간결성(원래 모델을 얼마나 간결하게 나타내는지), 다항식 시간 내에 지원하는 질의 집합, 그리고 다항식 시간 내에 수행할 수 있는 변환이다. 어떤 단일 표현도 세 가지 모두에서 뛰어나지 않으므로, 실무자는 응답해야 할 질의와 애플리케이션의 크기 제약에 따라 표현을 선택한다.
표현 클래스
컴파일된 표현은 여러 광범위한 범주로 나뉜다. 다이어그램 클래스에는 결정 트리, 정렬된 이진 결정 다이어그램(OBDD), 자유 이진 결정 다이어그램(FBDD), 비결정적 OBDD, 다중 값 결정 다이어그램(MDD)이 포함된다. 이러한 그래픽 구조는 부울 함수를 방향성 비순환 그래프로 나타내며, 각 경로는 변수의 할당에 해당한다.
공식 클래스에는 분리 정규형(DNF)과 결합 정규형(CNF)이 포함된다. CNF는 많은 추론 작업의 일반적인 입력 형식이지만 모든 질의를 효율적으로 지원하지는 않으므로, 다른 형태로의 컴파일이 동기가 된다. 회로 클래스에는 부정 정규형(NNF), 분해 가능한 NNF(DNNF), 결정적 DNNF(d-DNNF), 문장 결정 다이어그램(SDD)이 포함된다. 이러한 회로는 일관성 검사나 모델 계수와 같은 특정 질의에 대해 다항식 시간 연산을 가능하게 하는 구조적 제약을 부과한다.
지식 컴파일러
지식 컴파일을 자동으로 수행하기 위해 여러 소프트웨어 도구가 개발되었다. c2d 컴파일러는 d-DNNF로의 컴파일을 지원하며, 이 표현은 다항식 시간 모델 계수와 일관성 검사를 허용한다. d4 컴파일러도 d-DNNF를 대상으로 하며 대규모 인스턴스에서의 효율성으로 알려져 있다. miniC2D는 SDD로 컴파일하며, 이는 더 광범위한 질의와 변환을 지원하는 최신 표현이다. KCBox는 OBDD, OBDD[AND], CCDD로의 컴파일을 지원하여 다양한 다이어그램 클래스에서 유연성을 제공한다.
이러한 컴파일러는 반복적인 질의 응답이 필요한 확률적 추론, 계획, 구성 관리와 같은 애플리케이션에서 사용된다. 모델을 한 번 컴파일함으로써 시스템은 많은 질의를 빠르게 응답할 수 있으며, 이는 실시간 또는 대화형 환경에서 중요하다.
절충점과 선택 기준
컴파일된 표현의 선택은 애플리케이션의 특정 요구 사항에 따라 달라진다. 예를 들어, OBDD는 많은 실제 함수에 대해 간결하며 다항식 시간 동등성 검사를 지원하지만, 일부 함수에서는 지수적으로 팽창할 수 있다. DNNF와 d-DNNF는 일반적으로 더 간결하지만 지원하는 질의가 더 적다. SDD는 중간 지점을 제공하며, 다항식 시간 내에 모델 계수와 조건화를 모두 지원하면서 컴파일을 용이하게 하는 구조적 속성을 유지한다.
변환도 중요하다. 일부 애플리케이션에서는 증거에 대한 조건화나 추가 제약과의 결합과 같이 컴파일된 표현을 수정해야 한다. 이러한 변환을 다항식 시간 내에 지원하는 표현은 덜 간결하더라도 동적 환경에서 선호된다.
기계 학습과의 관계
지식 컴파일은 데이터에서 패턴을 학습하는 데 초점을 맞추는 Machine learning 및 Deep learning과 개념적으로 구별된다. 그러나 컴파일된 표현은 학습된 모델을 더 해석 가능하게 만들거나 신경 접근 방식과 기호 추론을 통합하는 방법으로 탐구되어 왔다. 예를 들어, 결정 다이어그램은 훈련된 Neural network의 결정 경계를 형식 검증을 지원하는 형태로 나타내는 데 사용될 수 있다.
최근 연구는 Large language model 추론과의 연결도 검토하고 있으며, 컴파일된 지식 베이스가 생성 모델을 보강하기 위한 구조화된 배경 지식을 제공할 수 있다. 이러한 노력은 아직 초기 단계이지만, 기호 및 하위 기호 AI를 연결하는 도구로서 지식 컴파일의 지속적인 관련성을 강조한다.
현재 방향
지식 컴파일 연구는 더 나은 절충점을 가진 새로운 표현 클래스 개발, 컴파일러 확장성 개선, 명제 논리를 넘어 더 풍부한 논리 언어로의 컴파일 확장에 계속 초점을 맞추고 있다. 또한 데이터에서 직접 컴파일된 표현을 학습하는 데 대한 관심도 있으며, 이는 컴파일과 Machine learning 사이의 경계를 흐리게 할 것이다. AI 시스템이 더 복잡해짐에 따라 구조화된 지식에 대해 효율적으로 추론하는 능력은 여전히 중요한 과제이며, 지식 컴파일은 이를 해결하기 위한 원칙적인 프레임워크를 제공한다.
참고 문헌
- Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal of Artificial Intelligence Research, 17, 229-264.
- Huang, J., & Darwiche, A. (2007). On compiling system models to faster SAT solvers. In Proceedings of the National Conference on Artificial Intelligence.
- Muise, C., McIlraith, S., Beck, J. C., & Hsu, E. (2012). Dsharp: Fast d-DNNF compilation with sharpSAT. In Canadian Conference on Artificial Intelligence.