![A photo of Family sample for Inductive Logic Programming article](https://upload.wikimedia.org/wikipedia/commons/8/82/ILP_family2.png)

귀납 논리 프로그래밍

최종 수정 2026.03.25

A photo of Family sample for Inductive Logic Programming article

귀납 논리 프로그래밍(ILP)은 논리 프로그래밍을 예제, 배경 지식, 가설의 통일된 표현 방식으로 사용하는 기호 인공지능의 하위 분야이다. 여기서 "귀납적"이라는 용어는 수학적 귀납법(즉, 정렬 집합의 모든 원소에 대해 속성을 증명하는 것)이 아닌 철학적 귀납법(즉, 관찰된 사실을 설명하기 위한 이론을 제시하는 것)을 의미한다. 알려진 배경 지식의 부호화와 사실의 논리적 데이터베이스로 표현된 예제 집합이 주어지면, ILP 시스템은 모든 긍정적 예제를 함의하고 부정적 예제는 하나도 함의하지 않는 가설적 논리 프로그램을 도출한다.

도식: 긍정적 예제 + 부정적 예제 + 배경 지식 ⇒ 가설.

귀납 논리 프로그래밍은 특히 생물정보학과 자연어 처리에서 유용하다.

역사

귀납 추론에 관한 초기 연구를 기반으로, 고든 플로트킨은 1970년경 절 설정에서의 귀납법을 최초로 형식화하였으며, 예제로부터 일반화하는 접근법을 채택하였다.[^1][^2] 1981년, 에후드 샤피로는 모델 추론이라는 새로운 접근법에서 이 분야를 형성하게 될 여러 아이디어를 소개하였는데, 이는 주어진 예제의 완전한 공리화를 탐색하기 위해 정제와 역추적을 사용하는 알고리즘이었다.[^1][^11] 그의 최초 구현은 1981년의 모델 추론 시스템으로,[^12][^13] 긍정적 예제와 부정적 예제로부터 호른 절 논리 프로그램을 귀납적으로 추론하는 Prolog 프로그램이었다.[^1] 귀납 논리 프로그래밍이라는 용어는 1990년 스티븐 머글턴의 논문에서 기계 학습과 논리 프로그래밍의 교차점으로 정의되며 처음 도입되었다.[^1] 머글턴과 Wray Buntine은 1988년에 술어 발명과 역 분해를 도입하였다.[^1][^3]

1990년대 초에 영향력 있는 여러 귀납 논리 프로그래밍 시스템이 등장하였다. 1990년 로스 퀸란이 도입한 FOIL은[^14] 명제 학습 알고리즘 AQ와 ID3를 업그레이드하는 것에 기반하였다.[^4] 1990년 머글턴과 Feng이 도입한 Golem은 플로트킨의 최소 일반화 알고리즘의 제한된 형태로 회귀하였다.[^4][^5] 1995년 머글턴이 도입한 Progol 시스템은 역 함의를 최초로 구현하였으며, 이후 많은 시스템에 영감을 주었다.[^4][^6] Progol의 후속 시스템으로 2001년 애슈윈 스리니바산이 도입한 Aleph는 여전히 가장 널리 사용되는 시스템 중 하나이다.

거의 같은 시기에 최초의 실용적 응용이 등장하였는데, 특히 생물정보학 분야에서 2000년까지 귀납 논리 프로그래밍은 약물 설계, 발암성 및 변이원성 예측, 그리고 단백질의 구조와 기능 규명에 성공적으로 적용되었다.[^15] 초기 연구에 내재된 자동 프로그래밍에 대한 초점과 달리, 이러한 분야들은 관계형 데이터 마이닝의 관점에서 귀납 논리 프로그래밍 기법을 활용하였다. 이러한 초기 응용의 성공과 더 큰 규모의 전통적 논리 프로그램 복구에서의 진전 부족이 이 분야의 초점을 형성하였다.[^16]

최근에는 메타 해석적 학습의 도입으로 술어 발명과 재귀 프로그램 학습이 더욱 실현 가능해짐에 따라, 자동 프로그래밍의 고전적 과제가 다시 주목받고 있다. 이 기법은 2014년 머글턴, Dianhuan Lin, Niels Pahlavi, Alireza Tamaddoni-Nezhad가 도입한 Metagol 시스템으로 개척되었다.[^17] 이를 통해 ILP 시스템은 더 적은 예제로 작동할 수 있게 되었으며, 문자열 변환 프로그램, 응답 집합 문법 및 일반 알고리즘 학습에서 성과를 거두었다.[^18]

설정

귀납 논리 프로그래밍은 여러 가지 학습 설정을 채택해 왔으며, 그 중 가장 일반적인 것은 함의로부터의 학습과 해석으로부터의 학습이다. 두 경우 모두, 입력은 배경 지식의 형태로 제공되며, 이는 논리 이론(일반적으로 논리 프로그래밍에서 사용되는 절의 형태)과 양성 및 음성 사례로 구성되고, 각각 E^+와 E^{-}로 표기된다. 출력은 가설''''로 주어지며, 이는 일반적으로 하나 이상의 절로 구성된 논리 이론이다.

두 설정은 제시되는 사례의 형식에서 차이가 있다.

함의로부터의 학습

함의로부터의 학습은 귀납 논리 프로그래밍에서 단연코 가장 널리 사용되는 설정이다. 이 설정에서 양성 및 음성 사례는 각각 양성 및 부정된 기저 리터럴의 유한 집합 E^+와 E^{-}로 주어진다. 올바른 가설 ''''은 다음 요건을 충족하는 절의 집합이며, 여기서 턴스타일 기호 \models는 논리적 함의를 나타낸다:[^19][^20] \begin{array}{llll} \text{Completeness:} & B \cup H & \models & E^+ \ \text{Consistency: } & B \cup H \cup E^- & \not\models & \textit{false} \end{array} 완전성은 생성된 모든 가설 **'이 모든 양성 사례 E^+를 설명할 것을 요구하며, 일관성은 배경 지식 ''''이 주어졌을 때 음성 사례 E^{-}와 모순되는 가설 **'의 생성을 금지한다.

머글턴의 개념 학습 설정에서,[^7] "완전성"은 "충분성"으로, "일관성"은 "강한 일관성"으로 불린다. 여기에 두 가지 조건이 추가된다: "필요성"은 **'이 E^+를 함의하지 않는다는 것으로, **'에 제한을 가하는 것이 아니라, 양성 사실이 가설 없이도 설명 가능한 한 가설의 생성을 금지한다. "약한 일관성"은 B\land H로부터 모순이 도출될 수 없다는 것으로, 배경 지식 **'과 모순되는 가설 **'의 생성을 금지한다. 약한 일관성은 강한 일관성에 의해 함의된다; 음성 사례가 주어지지 않으면 두 요건은 일치한다. 약한 일관성은 잡음이 있는 데이터의 경우 특히 중요한데, 이 경우 완전성과 강한 일관성을 보장할 수 없기 때문이다.[^7]

해석으로부터의 학습

해석으로부터의 학습에서 양성 및 음성 사례는 완전하거나 부분적인 에르브랑 구조의 집합으로 주어지며, 각 구조는 그 자체로 기저 리터럴의 유한 집합이다. 이러한 구조 *''는 임의의 대입 \theta와 B \cup H에 속하는 임의의 절 \mathrm{head} \leftarrow \mathrm{body}에 대해 \mathrm{body}\theta \subseteq e이면 \mathrm{head}\theta \subseteq e도 성립할 때 절의 집합 B \cup H의 모델이라고 한다. 이때 목표는 완전한, 즉 모든 양성 사례가 B \cup H의 모델이고, *일관된,'' 즉 어떤 음성 사례도 B \cup H의 모델이 아닌 가설을 출력하는 것이다.

ILP에 대한 접근법

귀납 논리 프로그래밍 시스템은 논리 이론 B, E^+, E^-을 입력으로 받아 이론 B, E^+, E^-에 대해 올바른 가설을 출력하는 프로그램이다. 시스템이 완전하다는 것은 임의의 입력 논리 이론 B, E^+, E^-에 대해 이 입력 이론들에 관한 임의의 올바른 가설을 해당 시스템의 가설 탐색 절차로 찾을 수 있을 때, 그리고 오직 그때만 성립한다. 귀납 논리 프로그래밍 시스템은 대략 탐색 기반 시스템과 메타 해석적 시스템의 두 부류로 나눌 수 있다.

탐색 기반 시스템은 가능한 절들의 공간이 포섭 관계 하에서 완전 격자를 형성한다는 점을 활용하는데, 여기서 하나의 절 C_1이 다른 절 C_2를 포섭한다는 것은 C_1에 \theta를 적용한 결과인 C_1\theta가 C_2의 부분집합이 되는 치환 \theta가 존재한다는 것이다. 이 격자는 상향식 또는 하향식으로 탐색할 수 있다.

상향식 탐색

포섭 격자를 탐색하는 상향식 방법은 1970년 Plotkin이 절 논리에서 귀납을 형식화한 최초의 연구 이래로 조사되어 왔다.[^1][^2] 사용되는 기법에는 반단일화에 기반한 최소 일반 일반화와 분해 추론 규칙을 역전시키는 역분해가 포함된다.

최소 일반 일반화

최소 일반 일반화 알고리즘은 두 절 C_1과 C_2를 입력으로 받아 C_1과 C_2의 최소 일반 일반화를 출력하는데, 이는 C_1과 C_2를 포섭하면서 C_1과 C_2를 포섭하는 다른 모든 절에 의해 포섭되는 절 C이다. 최소 일반 일반화는 먼저 C_1과 C_2로부터 모든 선택을 계산하여 구할 수 있는데, 선택이란 동일한 술어 기호와 부정/비부정 상태를 공유하는 리터럴 쌍 (L,M) \in (C_1 \times C_2)이다. 그런 다음, 최소 일반 일반화는 개별 선택들의 최소 일반 일반화의 논리합으로 얻어지며, 이는 1차 구문론적 반단일화로 구할 수 있다.[^21]

배경 지식을 고려하기 위해 귀납 논리 프로그래밍 시스템은 상대적 최소 일반 일반화를 사용하는데, 이는 배경 이론에 대한 상대적 포섭으로 정의된다. 일반적으로 이러한 상대적 최소 일반 일반화의 존재가 보장되지는 않지만, 배경 이론 **'이 기저 리터럴의 유한 집합이면 **'의 부정 자체가 하나의 절이 된다. 이 경우, 상대적 최소 일반 일반화는 ''''의 부정을 C_1과 C_2 모두에 논리합한 후 이전과 같이 최소 일반 일반화를 계산하여 구할 수 있다.[^22]

상대적 최소 일반 일반화는 상향식 시스템 Golem의 기초이다.[^4][^5]

역분해

역분해는 분해 연산자를 역전시키는 귀납적 추론 기법이다.

역분해는 분해 단계의 분해항에 대한 정보를 사용하여 가능한 분해 절들을 계산한다. 귀납 논리 프로그래밍에서는 두 가지 유형의 역분해 연산자가 사용된다: V-연산자와 W-연산자이다. V-연산자는 절 R과 C_1을 입력으로 받아 R이 C_1과 C_2의 분해항이 되는 절 C_2를 반환한다. W-연산자는 두 절 R_1과 R_2를 받아 R_1이 C_1과 C_2의 분해항이고 R_2가 C_2와 C_3의 분해항이 되는 세 절 C_1, C_2, C_3를 반환한다.[^8]

역분해는 1988년 Stephen Muggleton과 Wray Buntine이 귀납 논리 프로그래밍 시스템 Cigol에서 사용하기 위해 처음 도입하였다.[^3] 1993년까지 이는 역분해 연산자와 그 성질에 대한 연구의 급증을 촉발하였다.[^8]

하향식 탐색

ILP 시스템 Progol,[^6] Hail [^23] 및 Imparo [^24]는 이론 , , 에 대한 역함의 원리[^6]를 사용하여 가설을 찾는다: B \land H \models E \iff B \land \neg E \models \neg H. 먼저 B \land \neg E \models F와 F \models \neg H 조건을 만족하는 브리지 이론이라는 중간 이론을 구성한다. 그런 다음 H \models \neg F이므로, 브리지 이론의 부정을 반함의로 일반화한다.[^25] 그러나 반함의 연산은 매우 비결정적이기 때문에 계산 비용이 더 높다. 따라서 반함의보다 비결정성이 적은 역포섭(반포섭) 연산을 대신 사용하여 대안적 가설 탐색을 수행할 수 있다.

특정 귀납 논리 프로그래밍 시스템의 가설 탐색 절차의 완전성에 대한 문제가 제기된다. 예를 들어, 역함의 추론 규칙에 기반한 Progol의 가설 탐색 절차는 야마모토의 예에 의해 완전하지 않다.[^26] 반면에 Imparo는 반함의 절차[^9]와 확장된 역포섭[^27] 절차 모두에 의해 완전하다.

메타 해석적 학습

가설 그래프를 명시적으로 탐색하는 대신, 메타 해석적 또는 메타 수준 시스템은 귀납 논리 프로그래밍 프로그램을 메타 수준 논리 프로그램으로 인코딩한 후 이를 풀어 최적의 가설을 얻는다. 문제 명세를 표현하는 데 사용되는 형식론에는 Prolog와 해집합 프로그래밍이 있으며, 기존의 Prolog 시스템과 해집합 풀이기가 제약 조건을 풀기 위해 사용된다.

Prolog 기반 시스템의 예로는 Prolog의 메타 해석기에 기반한 Metagol이 있으며, ASPAL과 ILASP는 귀납 논리 프로그래밍 문제를 해집합 프로그래밍으로 인코딩하는 방식에 기반한다.

진화적 학습

ILP에서의 진화 알고리즘은 집단 기반 접근법을 사용하여 가설을 진화시키며, 선택, 교차, 돌연변이를 통해 이를 정제한다. EvoLearner와 같은 방법은 구조화된 기계 학습 벤치마크에서 전통적인 접근법을 능가하는 것으로 나타났다. [^28]

구현 목록

1BC and 1BC2: first-order naive Bayesian classifiers:
ACE (A Combined Engine)
Aleph
Atom
Claudien
DL-Learner
DMax
FastLAS (Fast Learning from Answer Sets)
FOIL (First Order Inductive Learner)
Golem
ILASP (Inductive Learning of Answer Set Programs)
Imparo[^9]
Inthelex (INcremental THEory Learner from EXamples)
Lime
Metagol
Mio
Ehud Shapiro의 MIS (Model Inference System)
Ontolearn
Popper
PROGOL
RSD
Warmr (현재 ACE에 포함)
ProGolem [^29][^30]

확률적 귀납 논리 프로그래밍

확률적 귀납 논리 프로그래밍은 귀납 논리 프로그래밍의 설정을 확률적 논리 프로그램 학습에 적용한 것이다. 이는 확률적 논리 프로그래밍의 형식주의 내에서 통계적 관계 학습의 한 형태로 간주될 수 있다.[^31][^10]

주어진 조건:

확률적 논리 프로그램으로서의 배경 지식, 그리고
긍정적 예제와 부정적 예제의 집합 E^{+} 및 E^{-}

확률적 귀납 논리 프로그래밍의 목표는 {H \cup B}에 따른 긍정적 예제의 확률은 최대화하고 부정적 예제의 확률은 최소화하는 확률적 논리 프로그램 H를 찾는 것이다.[^10]

이 문제에는 매개변수 학습과 구조 학습이라는 두 가지 변형이 있다. 전자에서는 의 구조(절)가 주어지고 주어진 절의 확률 주석을 추론하는 것이 목표이며, 후자에서는 의 구조와 확률 매개변수를 모두 추론하는 것이 목표이다. 고전적 귀납 논리 프로그래밍에서와 마찬가지로, 예제는 개별 예제 또는 (부분적) 해석으로 주어질 수 있다.[^10]

매개변수 학습

분포 의미론을 따르는 언어에 대한 매개변수 학습은 기댓값 최대화 알고리즘이나 경사 하강법을 사용하여 수행되어 왔다. 기댓값 최대화 알고리즘은 기댓값 단계와 최대화 단계를 반복적으로 수행하는 순환으로 구성된다. 기댓값 단계에서는 현재 확률 매개변수 값에 따라 은닉 변수의 분포가 계산되며, 최대화 단계에서는 매개변수의 새로운 값이 계산된다. 경사 하강법은 목적 함수의 기울기를 계산하고 기울기 방향으로 이동하며 매개변수를 반복적으로 수정한다.[^10]

구조 학습

구조 학습은 1997년 Daphne Koller와 Avi Pfeffer에 의해 개척되었으며,[^32] 저자들은 관련 확률적 불확실성 매개변수를 가진 1차 규칙의 구조를 학습하였다. 그들의 접근법은 예비 단계에서 기저 그래프 모델을 생성한 다음 기댓값 최대화를 적용하는 것이다.[^10]

2008년 De Raedt 등은 ProbLog 프로그램에 대해 이론 압축을 수행하는 알고리즘을 제시하였는데, 여기서 이론 압축이란 주어진 긍정적 및 부정적 예제 집합의 확률을 최대화하기 위해 이론에서 가능한 한 많은 절을 제거하는 과정을 말한다. 이론에 새로운 절을 추가할 수는 없다.[^10][^33]

같은 해, Meert, W. 등은 접지된 확률적 논리 프로그램의 매개변수와 구조를 학습하는 방법을 도입하였는데, 이는 이에 상응하는 베이지안 네트워크를 고려하고 베이지안 네트워크 학습 기법을 적용하는 것이다.[^34][^10]

2010년 De Raedt와 Ingo Thon이 도입한 ProbFOIL은 귀납 논리 프로그래밍 시스템 FOIL과 ProbLog를 결합하였다. 예제 자체와 그 분류 모두가 확률적일 수 있다는 의미에서 확률적 데이터로부터 논리 규칙이 학습된다. 규칙 집합은 예제의 설명으로부터 예제의 확률을 예측할 수 있어야 한다. 이 설정에서 매개변수(확률 값)는 고정되어 있으며 구조를 학습해야 한다.[^35][^10]

2011년 Elena Bellodi와 Fabrizio Riguzzi는 SLIPCASE를 도입하였는데, 이는 확률적 이론을 반복적으로 정제하고 기댓값 최대화를 사용하여 각 이론의 매개변수를 최적화함으로써 확률적 논리 프로그램 사이에서 빔 탐색을 수행한다.[^36] 2014년에 제안된 확장판 SLIPCOVER는 Progol에서와 같이 생성된 하부 절을 사용하여 정제 과정을 안내함으로써 수정 횟수를 줄이고 탐색 공간을 더 효과적으로 탐색한다. 또한 SLIPCOVER는 유망한 절의 탐색과 이론의 탐색을 분리한다: 절의 공간은 빔 탐색으로 탐색되고, 이론의 공간은 탐욕적으로 탐색된다.[^37][^10]

## 같이 보기
- 상식 추론
- 형식 개념 분석
- 귀납적 추론
- 귀납적 프로그래밍
- 귀납적 확률
- 통계적 관계 학습
- 버전 공간 학습


- ## 더 읽을거리
- - - Atom 시스템에 의한 조부모 관계 귀납의 시각적 예시. http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html 


 

---