유도 로직 프로그래밍

유도 논리 프로그래밍(ILP)은 예시, 배경 지식 및 가설을 통일된 표현으로 논리 프로그래밍을 사용하는 기호 인공지능의 하위 필드입니다.알려진 배경지식의 부호화와 사실의 논리적 데이터베이스로 표현되는 일련의 예제를 고려할 때 ILP 시스템은 모든 긍정적이고 부정적인 예제를 포함하지 않는 가설 논리 프로그램을 도출할 것이다.

스키마: 긍정적인 예 + 부정적인 예 + 배경 지식 hypothes 가설.

귀납 논리 프로그래밍은 생물 정보학 및 자연 언어 처리에서 특히 유용합니다.Gordon Plotkin과 Ehud Shapiro는 논리적 ^[1]^[2]^[3]환경에서 귀납적 기계 학습을 위한 초기 이론적 기반을 마련했습니다.Shapiro는 1981년에 ^[4]첫 번째 구현(모델 추론 시스템)을 구축했습니다.이것은 긍정과 부정의 예로부터 유도적으로 논리 프로그램을 추론하는 프롤로그 프로그램입니다.유도 논리 프로그래밍이라는 용어는 1991년 ^[6]Stephen Muggleton의 논문에서 처음^[5] 소개되었습니다.Muggleton은 또한 유도 논리 프로그래밍에 관한 연례 국제 컨퍼런스를 설립하여 술어 발명, 역해상도 ^[7]및 ^[8]역행렬의 이론적 아이디어를 소개하였습니다.Muggleton은 PROGOL 시스템에서 처음으로 Inverse causion을 구현했습니다.여기서 "유도적"이라는 용어는 수학적 귀납(즉, 질서 있는 집합의 모든 구성원에 대한 속성 증명)보다는 철학적인(즉, 관찰된 사실을 설명하기 위한 이론을 제안하는) 것을 의미한다.

형식적 정의

배경 지식은 논리 $이론$ B로 제공되며, 일반적으로 논리 프로그래밍에서 사용되는 혼 절의 형태로 제공됩니다.긍정 및 부정 예는 각각 부정 및 부정 그라운드 리터럴의 $E^{+}$ E $E^{+}$ + {\ $displaystyle$ E $^{+}}$ 와 $E^{+}$ $E^{-}$ E $E^{-}$ - {\ $displaystyle$ E $^{-}}$ 의 $E^{-}$ 결합으로 $E^{+}$ 된다.올바른 $가설$ h는 다음의 ^[9]요건을 만족시키는 논리 명제이다.

{\displaystyle {begin {array} {lll} {\text {필요성:}}&B&\models&E^{+}\{\text{충분:}}&B\land h&\color {blue}{\models}&E^{+}\{\text{\text}약한 일관성:}}&B\land h&\models &{\textit {false}\{\text {강력한 일관성:}}&B\land E^{-}&\models &{\textit {false}}\end {array}}이(가) 아니다.

"필요성"은 h에 $제한$ 을 가하지는 않지만, 그것 없이 긍정적인 사실이 설명되는 한 가설의 생성을 금지한다."충분성"은 생성된 $가설$ h를 모든 긍정적인 예 $E^{+}$ + {\ $displaystyle$ E $E^{+}$ 으로 설명한다. "약한 일관성"은 배경 $지식$ B와 모순되는 $가설$ h의 생성을 금지한다 $E^{-}$ "강한 일관성"은 또한 부정적인 $E^{-}$ E -와 모순되는 $가설$ h의 생성을 금지한다. $(\displaystyle$ E $E^{-}$ $배경지식$ B를 고려할 때 이는 "약한 일관성"을 의미합니다. 부정적인 예를 제시하지 않으면 두 요건이 일치합니다.제로스키는 "충분함"과 "강력한 일관성"만을 필요로 한다.

예

"예" 섹션의 가정된 가족 관계

가족관계의 정의를 배우는 것에 대한 다음의 잘 알려진 예는 약어를 사용합니다.

par :

부모

, 펨:

여성

,

도 :

딸

,

g :

조지

,

h :

헬렌

,

m :

메리

,

t :

탐

,

n :

낸시

,

e :

이브

.

배경지식부터 시작합니다(그림 참조).

{\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)

}(m)\land

{

textit

{fem}(

n)\land {textit

{fem}(

e

긍정적인 예

{\textit {dau}}(m,h)\land {\textit {dau}}(e,t)

(

{\textit {dau}}(m,h)\land {\textit {dau}}(e,t)

,

{\textit {dau}}(m,h)\land {\textit {dau}}(e,t)

)∧

{\textit {dau}}(m,h)\land {\textit {dau}}(e,t)

(

{\textit {dau}}(m,h)\land {\textit {dau}}(e,t)

,

{\textit {dau}}(m,h)\land {\textit {dau}}(e,t)

){

displaystyle

{

textit

{

display

} (

m

,

h

)\

land

{

textit

{

display

} (

e

,

t

)

{\textit {dau}}(m,h)\land {\textit {dau}}(e,t)

,

그리고 부정적인 예가 $없음$ 을 나타내는 사소한 명제는 참이다.

유도 논리 프로그래밍에 대한 Plotkin의 "상대적 최소 일반화(rlg)" 접근방식을 사용하여 딸 $관계$ 도우를 공식적으로 정의하는 방법에 대한 제안을 얻어야 한다.

이 방법에서는 다음 단계를 사용합니다.

각각의 긍정적인 예제를 완전한 배경지식으로 상대화한다.
${\begin{aligned}{\textit {dau}}(m,h)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\\{\textit {dau}}(e,t)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\end{aligned}}$ ${\begin{aligned}{\textit {dau}}(m,h)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\\{\textit {dau}}(e,t)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\end{aligned}}$ $extit {par}(h,m)\land {textit {par}(h,t)\land {textit$ { $par}(t,e)\land {textit {par}(n,e)\land {textit {fem}(m)\land {textit$ {textit fem}(m}( $m)\$ land {textit {textit par}(textit {t})}(textit {t}(m})\land $}\$ land $}$
절 정규 형식으로 변환:
${\begin{aligned}{\textit {dau}}(m,h)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\\{\textit {dau}}(e,t)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\end{aligned}}$ ${\begin{aligned}{\textit {dau}}(m,h)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\\{\textit {dau}}(e,t)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\end{aligned}}$ $t {fem}(n)\lor \textit {fem}(e)\{\textit {par}(e,t)\lor \lnot {textit {par}(h,t)\lor \textit {par}(lor {t}(gm)\lor {textit {par}(lar}(lar}(gm)\t)\lart)\lart)\lart}(t)\lor {t}(textit {t}(t}(t}(e)\textit$ ,
호환되는 각 리터럴 쌍을 통일 방지:
- ${\textit {dau}}(x_{me},x_{ht})$ ( ${\textit {dau}}(x_{me},x_{ht})$ ${\textit {dau}}(x_{me},x_{ht})$ e , ${\textit {dau}}(m,h)$ ${\textit {dau}}(x_{me},x_{ht})$ t ${\textit {dau}}(x_{me},x_{ht})$ ) ( ${\textit {dau}}(m,h)$ $display$ style { $textit$ $}$ ( $x$ $_$ { $me$ , x $_$ { $ht$ } ) daugh ${\textit {dau}}(m,h)$ ( $m$ , ${\textit {dau}}(m,h)$ h ) $daug$ ( ${\textit {dau}}(e,t)$ , ${\textit {dau}}(e,t)$ ) style { $display textit$ { $t}$ ( e , t ${\textit {dau}}(e,t)$ ) ${\textit {dau}}(e,t)$ 、
- $\lnot {\textit {par}}(x_{ht},x_{me})$ $\lnot {\textit {par}}(h,m)$ ( $\lnot {\textit {par}}(h,m)$ $\lnot {\textit {par}}(x_{ht},x_{me})$ $\lnot {\textit {par}}(x_{ht},x_{me})$ , $x$ m $\lnot {\textit {par}}(x_{ht},x_{me})$ e ) ( $\lnot {\textit {par}}(h,m)$ $displaystyle$ \ $lnot$ { par } ( $x$ _ { $ht$ , x _ { $\lnot {\textit {par}}(x_{ht},x_{me})$ me $\lnot {\textit {par}}(x_{ht},x_{me})$ } ) ( $displaystyle$ \ $lnot$ { $textit$ { $\lnot {\textit {par}}(h,m)$ $par$ } ( h , $\lnot {\textit {par}}(h,m)$ m $\lnot {\textit {par}}(h,m)$ ) $\lnot {\textit {par}}(t,e)$ $\lnot {\textit {par}}(t,e)$ ( t $\lnot {\textit {par}}(t,e)$ , $e$ ) ( $displaystyle$ \ l $not$ { $textit$ { par $}$ ( x $\lnot {\textit {par}}(t,e)$ $)$ ) ) $\lnot {\textit {par}}(t,e)$ 、
- $\lnot {\textit {fem}}(x_{me})$ from $\lnot {\textit {fem}}(m)$ and $\lnot {\textit {fem}}(e)$ ,
- $\lnot {\textit {par}}(g,m)$ $\lnot {\textit {par}}(g,m)$ $par$ ( $\lnot {\textit {par}}(g,m)$ g , m ){ display $style$ $\lnot {\textit {par}}(g,m)$ \ $lnot$ { $textit$ { $par$ $\lnot {\textit {par}}(g,m)$ } ( $g$ , m $\lnot {\textit {par}}(g,m)$ ) } $\lnot {\textit {par}}(g,m)$ ( ( ( ( ( ( ( ( ( ( $\lnot {\textit {par}}(g,m)$ $\lnot {\textit {par}}(g,m)$ $g$ , $\lnot {\textit {par}}(g,m)$ m $\lnot {\textit {par}}(g,m)$ ） $($ ( ( ( ( ( ( ( ( ( $파$ ( $\lnot {\textit {par}}(g,m)$ , $\lnot {\textit {par}}(g,m)$ m ) $\lnot {\textit {par}}(g,m)$ $\lnot {\textit {par}}(g,m)$ ( ( ( ( $liter$ liter liter liter liter liter liter liter liter liter liter liter $\lnot {\textit {par}}(g,m)$ \ lnot { $textit$ { par $） liter$ liter liter $liter$ liter liter liter liter liter liter liter liter { par liter liter liter liter liter liter liter liter liter liter liter liter liter liter liter liter liter $liter$ liter liter liter liter
- $\lnot {\textit {par}}(x_{gt},x_{me})$ ( $\lnot {\textit {par}}(x_{gt},x_{me})$ $\lnot {\textit {par}}(x_{gt},x_{me})$ $\lnot {\textit {par}}(t,e)$ , $\lnot {\textit {par}}(x_{gt},x_{me})$ m e ) $\lnot {\textit {par}}(x_{gt},x_{me})$ $\lnot {\textit {par}}(g,m)$ $、$ $\lnot {\textit {par}}(g,m)$ g , m $\lnot {\textit {par}}(t,e)$ ）、 $displaystyle$ \ $lnot$ \ $textit$ { $\lnot {\textit {par}}(x_{gt},x_{me})$ $par }$ $\lnot {\textit {par}}(g,m)$ ( $x _$ { $gt$ $\lnot {\textit {par}}(g,m)$ ; x _ { me $\lnot {\textit {par}}(t,e)$ } ) $from$ ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( $\lnot {\textit {par}}(t,e)$ ( $g$ , $\lnot {\textit {par}}(t,e)$ m $\lnot {\textit {par}}(g,m)$ ) 、 $($ ( ( ( ( ( ( ( ( $파$ ( g , m ) $\lnot {\textit {par}}(t,e)$ l ( ( ( ( ( ( ( \ \ \ ( ( ( ( ( ( ( ( ( $notnotl$ ( ( ( ( ( ( ( \ \ ( ( ( ( ( ( ( ( ( ( ( ( ( ( \
양의 리터럴에서 발생하지 않는 변수를 포함하는 모든 부정 리터럴을 삭제합니다.
- $x_{me},x_{ht}$ $x_{me},x_{ht}$ e $x_{me},x_{ht}$ $x_{me},x_{ht}$ h $x_{me},x_{ht}$ { $displaystyle x_{me$ }, $x_{ht$ $x_{me},x_{ht}$ 의 변수를 포함하는 모든 부정 리터럴을 삭제한 후 ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ ( ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ m ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ , ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ )∨ ( ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ ( ( ( ( ( ( ( ( ( ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ ( ( ( （ ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ m ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ e ) { $display style }( x$ _ $me$ , x _ $me,$ { $ht})$ { ht} { ht} { $tarit$ { ht} { $ht}$ \ parit } \ parit } \ $parit }$ ( $x_{me})$ 는 ${\textit {dau}}(x_{{me}},x_{{ht}})\lor \lnot {\textit {par}}(x_{{ht}},x_{{me}})\lor \lnot {\textit {fem}}(x_{{me}})$ 배경지식의 모든 기본 리터럴과 함께 남아 있습니다 $.$
절을 경음기 형식으로 다시 변환:
- $\displaystyle {textit {facts}(x_{me},x_{ht})\왼쪽 화살표 {par}(x_{ht},x_{me})\land {\textit {모든 배경 지식 팩트}}}}:$

결과 혼 절은 rlg 접근법에 의해 얻어진 $가설$ h이다. $x_{me}$ 조항은 배경지식사실을 무시한 채 $x_{ht}$ t { $displaystyle$ $x_{me}$ $x_$ ${$ ht $x_{ht}$ }가 x m $x_{me}$ $x_{me}$ { $displaystyle x_{$ me $}$ 의 $x_{{me}}$ 부모이고 x $x_{me}$ $x_{me}$ { $displaystyle x_{me}$ 가 $x_{{me}}$ 여성일 $x_{ht}$ x $x_{me}$ $x_{ht}$ { $displaystyle x_{ht$ }의 $x_{{me}}$ $x_{{ht}}$ 딸이라고 합니다.널리 받아들여지고 있는 정의.

상기 요건에 관해 "필요성"은 술어 $도우$ 가 배경지식에 나타나지 않기 때문에 충족되었다. 따라서 긍정적인 예와 같이 이 술어를 포함하는 속성을 의미할 수 없다."충분"은 배경지식의 ${\textit {par}}(h,m)\land {\textit {fem}}(m)$ par ${\textit {par}}(h,m)\land {\textit {fem}}(m)$ ( ${\textit {par}}(h,m)\land {\textit {fem}}(m)$ m ) ${\textit {par}}(h,m)\land {\textit {fem}}(m)$ fem ( ${\textit {par}}(h,m)\land {\textit {fem}}(m)$ $)\displaystyle {textit {par}$ ( $h, m$ )\ $land {textit {fem}$ ( $m$ ${dau}$ ( $,$ { $dau$ } (m, $h$ ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ 와 ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ 로 계산된 $가설$ h로 만족한다. ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ ) ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ ( e ) ( 、 { $display$ style { $par$ } ( $t ,$ ${\textit {dau}}(e,t)$ ) \ land { $textit { fem$ } ( $e$ ${\textit {dau}}(e,t)$ ) 、 ${\textit {dau}}(e,t)$ style { $dau$ ( $e$ , $t$ ) ${\textit {dau}}(e,t)$ t ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ $holds$ " " holds 、 h the the h $h$ h h h h by by by by by by by by by by by by by t t t t t by by by dau dau ${\textit {dau}}(e,t)$ ( ( ${\textit {dau}}(e,t)$ 。배경지식으로 설명되는 허브랜드 구조. "강력한 일관성"에 대해서도 유사합니다.

할머니 관계에 대한 일반적인 정의인 ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ . ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ ( ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ , z ) ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ ( ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ ) ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ ( ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ , y ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ ( ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ y ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ , z ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ ) $style$ display ${ textit$ { gra } ( x , $z$ )\ $leftarrow { textit$ { $fem }$ ( x $)\ land$ { $textit$ { par $}$ ( $x$ , y ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$ learned } $。$ ly; 대응하는 리터럴은 접근법의 네 번째 단계에서 삭제되었을 것입니다.이 결함을 해결하려면 다른 리터럴 선택 후 휴리스틱을 사용하여 매개 변수를 지정할 수 있도록 해당 단계를 수정해야 합니다.역사적으로, GOLEM의 구현은 rlg 접근법에 기초한다.

유도 논리 프로그래밍 시스템

유도 로직 프로그래밍 시스템은 입력 로직 $B,E^{+},E^{-}$ B $B,E^{+},E^{-}$ + , $B,E^{+},E^{-}$ - {\ $display style$ B, $E^{+}, E^{-}}$ 를 $B,E^{+},E^{-}$ 받아들여 올바른 $가설$ H wrt $B,E^{+},E^{-}$ B $B,E^{+},E^{-}$ $B,E^{+},E^{-}$ - {\ $display$ B, $E^+}, E^{-}$ 를 $B,E^{+},E^{-}$ 출력하는 프로그램이며, 알고리즘은 2개의 부분으로 구성됩니다.우선 귀납논리 프로그래밍 절차를 사용하여 가설을 탐색한 후, 발견된 가설의 서브셋(대부분의 시스템에서 하나의 가설)을 선택 알고리즘에 의해 선택한다.선택 알고리즘은 발견된 각 가설을 채점하고 점수가 가장 높은 가설을 반환합니다.점수 함수의 예로는 Kolmogorov 복잡도가 가장 낮은 가설이 가장 높은 점수를 가지고 반환되는 최소 압축 길이가 포함됩니다.가설 탐색 $B,E^{+},E^{-}$ 로 이들 입력 이론의 올바른 $가설$ Hwrt를 구할 수 있다면 ILP 시스템은 완전한 입력 논리 이론 B $B,E^{+},E^{-}$ +, $E$ - $B,E^{+},E^{-}$ { \ $displaystyle$ B, $E^{$ + , E $^$ { - } 。

가설 검색

Progol,[6]우박[15]과 Imparo처럼 근대 ILP 시스템이다. 우선 그들은 F다리를 이론은 조건을 만족시키라고 불리는 중간 이론을 가설 수소 이론들 B, E, H:B∧ H⊨ E⟺ B∧ ¬ E⊨ ¬ H{\displaystyle B\land H\models E\iff B\land \neg E\models \neg H}의 역 entailment[6]의 원리를 이용하여 찾[16]. B∧ ¬ E⊨ $(Displaystyle$ B $\land \neg$ E $\models$ F $H\models \neg F$ 및 F $H\models \neg F$ $Displaystyle$ F $neg$ H)는 H( $Displaystyle$ $F\models \neg H$ H $\neg$ F $H\models \neg F$ 로서 $H\models \neg F$ $이론$ F의 부정과 안티 에센탈먼트를 ^[17]일반화한다.그러나 매우 비결정적이기 때문에 안티엔티먼트의 연산은 계산적으로 더 비싸다.따라서 반증명보다 비결정성이 낮은 역가정(반증거) 연산을 사용하여 대체 가설 검색을 수행할 수 있다.

특정 ILP 시스템의 가설 탐색 절차의 완전성에 의문이 생긴다.예를 들어, 역귀속 추론 규칙에 근거한 프로골의 가설 탐색 절차는 야마모토의 ^[18]예에서는 완전하지 않다.반면 임파로는 반증거 절차와 연장된 역증거 절차로 완성된다.

실장

「」를 참조해 주세요.

레퍼런스

^ 플로트킨 G.D.귀납적 추론의 자동적 방법, 에든버러 대학 박사 논문, 1970.
^ 샤피로, 에후드 Y사실로부터 이론의 귀납적 추론, 연구 보고서 192, 예일 대학교 컴퓨터 과학부, 1981.J.-L. 라세즈, G. 플롯킨(Eds.), 계산 논리학, MIT 프레스, 케임브리지, MA, 1991, 페이지 199-254에 전재.
^ 샤피로, 에후드 Y.(1983)알고리즘 프로그램 디버깅케임브리지, 매사추세츠: MIT 프레스. ISBN 0-262-19218-7
^ 샤피로, 에후드 Y "모델 추론 시스템"제7회 인공지능 국제공동회의 진행 제2권.모건 카우프만 출판사, 1981년
^ 뤽 드 래트.유도 논리 프로그래밍에 대한 관점.Shakertown 로직 프로그래밍의 현재 및 미래 동향에 관한 워크숍은 Springer LNCS, 1999에 게재될 예정이다.CiteSeerX: 10.1.1.56.1790
^ ^a ^b ^c Muggleton, S.H. (1991). "Inductive logic programming". New Generation Computing. 8 (4): 295–318. CiteSeerX 10.1.1.329.5312. doi:10.1007/BF03037089.
^ Muggleton S.H.와 Buntine W. "해상도 반전을 통한 1차 술어의 기계 발명", 1988년 제5회 기계학습 국제회의의 진행.
^ Muggleton, S.H. (1995). "Inverting entailment and Progol". New Generation Computing. 13 (3–4): 245–286. CiteSeerX 10.1.1.31.1630. doi:10.1007/bf03037227.
^ Muggleton, Stephen (1999). "Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic". Artificial Intelligence. 114 (1–2): 283–296. doi:10.1016/s0004-3702(99)00067-3.;여기서: 제2.1장
^ Džeroski, Sašo (1996), "Inductive Logic Programming and Knowledge Discovery in Databases", in Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (eds.), Advances in Knowledge Discovery and Data Mining (PDF), MIT Press, pp. 117–152;여기서: 제5.2.4장
^ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D. (eds.). "A Note on Inductive Generalization". Machine Intelligence. 5: 153–163.
^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D. (eds.). "A Further Note on Inductive Generalization". Machine Intelligence. 6: 101–124.
^ 즉, 동일한 술어 기호와 부정/부정되지 않은 상태 공유
^ 일반적으로: n개의 양의 예시 리터럴이 $주어졌을$ 때 n-튜플
^ Ray, O., Broda, K. 및 Russo, A.M. (2003)하이브리드 유도 학습입니다^{[dead link]}.LNCS: 제2835권유도 로직 프로그래밍에 관한 제13회 국제 회의의 진행(pp. 311–328)베를린: 스프링거.
^ Kimber, T., Broda, K. 및 Russo, A.(2009).고장 시 유도: 연결된 경음기 이론을 학습합니다.LNCS: 제5753권제10회 논리 프로그래밍 및 비단조 추론에 관한 국제 회의의 진행 상황 (p. 169–181).베를린: 스프링거.
^ 야마모토 요시타카, 이노우에 카츠미, 이와누마 코지.완전한 설명 유도를 위한 역추정입니다.기계학습, 86 (1):115–139, 2012.
^ 야마모토 아키히로.어떤 가설이 역귀납으로 발견될 수 있는가?유도 로직 프로그래밍의 페이지 296 – 308.스프링거, 1997년
^ ^a ^b 티모시 킴버.고장 시 유도를 통해 확실하고 정상적인 논리 프로그램을 학습합니다.2012년 임페리얼 칼리지 런던 박사 논문.
^ David Toth(2014).임파로는 역수정에 의해 완성된다.arXiv: 1407.3836
^ Muggleton, Stephen; Santos, Jose; Tamaddoni-Nezhad, Alireza (2009). "ProGolem: a system based on relative minimal generalization" (PDF). ILP.
^ Santos, Jose; Nassif, Houssam; Page, David; Muggleton, Stephen; Sternberg, Mike (2012). "Automated identification of features of protein-ligand interactions using Inductive Logic Programming: a hexose binding case study" (PDF). BMC Bioinformatics. 13: 162. doi:10.1186/1471-2105-13-162. PMC 3458898. PMID 22783946.

추가 정보

Muggleton, S.; De Raedt, L. (1994). "Inductive Logic Programming: Theory and methods". The Journal of Logic Programming. 19–20: 629–679. doi:10.1016/0743-1066(94)90035-3.
Lavrac, N.; Dzeroski, S. (1994). Inductive Logic Programming: Techniques and Applications. New York: Ellis Horwood. ISBN 978-0-13-457870-5. Archived from the original on 2004-09-06. Retrieved 2004-09-22.
Atom 시스템에 의해 조부 관계를 유도하는 시각적 예.http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html

[1] 플로트킨 G.D.귀납적 추론의 자동적 방법, 에든버러 대학 박사 논문, 1970.

[2] 샤피로, 에후드 Y사실로부터 이론의 귀납적 추론, 연구 보고서 192, 예일 대학교 컴퓨터 과학부, 1981.J.-L. 라세즈, G. 플롯킨(Eds.), 계산 논리학, MIT 프레스, 케임브리지, MA, 1991, 페이지 199-254에 전재.

[3] 샤피로, 에후드 Y.(1983)알고리즘 프로그램 디버깅케임브리지, 매사추세츠: MIT 프레스. ISBN 0-262-19218-7

[4] 샤피로, 에후드 Y "모델 추론 시스템"제7회 인공지능 국제공동회의 진행 제2권.모건 카우프만 출판사, 1981년

[5] 뤽 드 래트.유도 논리 프로그래밍에 대한 관점.Shakertown 로직 프로그래밍의 현재 및 미래 동향에 관한 워크숍은 Springer LNCS, 1999에 게재될 예정이다.CiteSeerX: 10.1.1.56.1790

[muggleton1995inverse-6] Muggleton, S.H. (1991). "Inductive logic programming". New Generation Computing. 8 (4): 295–318. CiteSeerX 10.1.1.329.5312. doi:10.1007/BF03037089.

[7] Muggleton S.H.와 Buntine W. "해상도 반전을 통한 1차 술어의 기계 발명", 1988년 제5회 기계학습 국제회의의 진행.

[8] Muggleton, S.H. (1995). "Inverting entailment and Progol". New Generation Computing. 13 (3–4): 245–286. CiteSeerX 10.1.1.31.1630. doi:10.1007/bf03037227.

[9] Muggleton, Stephen (1999). "Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic". Artificial Intelligence. 114 (1–2): 283–296. doi:10.1016/s0004-3702(99)00067-3.;여기서: 제2.1장

[10] Džeroski, Sašo (1996), "Inductive Logic Programming and Knowledge Discovery in Databases", in Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (eds.), Advances in Knowledge Discovery and Data Mining (PDF), MIT Press, pp. 117–152;여기서: 제5.2.4장

[11] Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D. (eds.). "A Note on Inductive Generalization". Machine Intelligence. 5: 153–163.

[12] Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D. (eds.). "A Further Note on Inductive Generalization". Machine Intelligence. 6: 101–124.

[13] 즉, 동일한 술어 기호와 부정/부정되지 않은 상태 공유

[14] 일반적으로: n개의 양의 예시 리터럴이 $주어졌을$ 때 n-튜플

[15] Ray, O., Broda, K. 및 Russo, A.M. (2003)하이브리드 유도 학습입니다^{[dead link]}.LNCS: 제2835권유도 로직 프로그래밍에 관한 제13회 국제 회의의 진행(pp. 311–328)베를린: 스프링거.

[16] Kimber, T., Broda, K. 및 Russo, A.(2009).고장 시 유도: 연결된 경음기 이론을 학습합니다.LNCS: 제5753권제10회 논리 프로그래밍 및 비단조 추론에 관한 국제 회의의 진행 상황 (p. 169–181).베를린: 스프링거.

[17] 야마모토 요시타카, 이노우에 카츠미, 이와누마 코지.완전한 설명 유도를 위한 역추정입니다.기계학습, 86 (1):115–139, 2012.

[18] 야마모토 아키히로.어떤 가설이 역귀납으로 발견될 수 있는가?유도 로직 프로그래밍의 페이지 296 – 308.스프링거, 1997년

[kimber2009induction-19] 티모시 킴버.고장 시 유도를 통해 확실하고 정상적인 논리 프로그램을 학습합니다.2012년 임페리얼 칼리지 런던 박사 논문.

[20] David Toth(2014).임파로는 역수정에 의해 완성된다.arXiv: 1407.3836

[21] Muggleton, Stephen; Santos, Jose; Tamaddoni-Nezhad, Alireza (2009). "ProGolem: a system based on relative minimal generalization" (PDF). ILP.

[22] Santos, Jose; Nassif, Houssam; Page, David; Muggleton, Stephen; Sternberg, Mike (2012). "Automated identification of features of protein-ligand interactions using Inductive Logic Programming: a hexose binding case study" (PDF). BMC Bioinformatics. 13: 162. doi:10.1186/1471-2105-13-162. PMC 3458898. PMID 22783946.

[1]

[2]

[3]

[4]

[6]

[5]

[7]

[8]

[9]

[17]

[18]

[19]

[21]

[22]

Search

유도 로직 프로그래밍

네임스페이스

더

목차

형식적 정의

예

유도 논리 프로그래밍 시스템

가설 검색

실장

「」를 참조해 주세요.

레퍼런스

추가 정보

Search

유도 로직 프로그래밍

형식적 정의

예

유도 논리 프로그래밍 시스템

가설 검색

실장

「 」를 참조해 주세요.

레퍼런스

추가 정보

「」를 참조해 주세요.