납치 논리 프로그래밍

유괴형 논리 프로그래밍(ALP)은 유괴적 추론에 근거해 선언적으로 문제를 해결하는 데 사용할 수 있는 고도의 지식 표현 프레임워크다. 그것은 일부 술어를 불완전하게 정의하고, 강제할 수 있는 술어로 선언하도록 허용함으로써 정상적인 논리 프로그래밍을 확장한다. 문제해결은 이러한 불가침적 술어(추정적 가설)에 대한 가설을 풀 문제해결 솔루션으로 도출함으로써 효과를 얻는다. 이러한 문제들은 (고전적 납치에서와 같이) 설명이 필요한 관찰이나 (정상적인 논리 프로그래밍에서와 같이) 달성해야 할 목표가 될 수 있다. 진단, 계획, 자연어, 기계학습 등의 문제를 해결하는 데 활용할 수 있다. 부정의 오류를 유괴적 추론의 한 형태로 해석하는 데도 사용되어 왔다.

구문

납치 논리 프로그램에는 $\langle P,A,IC\rangle ,$ 가지 요소가 있는데, $\langle P,A,IC\rangle ,$ ⟨ P $\langle P,A,IC\rangle ,$ , A $\langle P,A,IC\rangle ,$ , $\langle P,A,IC\rangle ,$ $\langle P,A,IC\rangle ,$ $\langle P,A,IC\rangle ,$ , ${\displaystyle \langle P,A,$ $IC\rangele ,}$ 여기서 $\langle P,A,IC\rangle ,$ :

P는 논리 프로그래밍에서와 정확히 같은 형태의 논리 프로그램이다.
A는 술어의 집합으로, 강제적인 술어로 불린다.
IC는 1차 클래식 공식의 집합체다.

일반적으로 논리 프로그램 P는 머리(또는 결론)가 강제적인 술어를 가리키는 조항을 포함하지 않는다. (이 제한은 일반성의 손실 없이 할 수 있다.) 또한 실제로 IC의 무결성 제약은 종종 부정의 형태로 제한된다. 즉, 다음과 같은 형식의 조항이다.

   거짓:- A1,...An, B1, ..., Bm이 아니다.

그러한 제약조건은 A1,...An이 모두 진실인 동시에 B1, ...Bm이 모두 거짓인 것은 불가능하다는 것을 의미한다.

비공식적 의미와 문제 해결

P의 조항은 불가침 술어 집합을 정의하며 이를 통해 문제 영역에 대한 설명(또는 모델)을 제공한다. IC의 무결성 제약조건은 문제의 어떤 해결책에서도 존중되어야 할 문제 영역의 일반적인 속성을 명시한다.

설명해야 할 관찰이나 원하는 목표를 표현하는 문제, G는 양수(NAF)와 음수(NAF) 리터럴의 결합으로 표현된다. 이런 문제는 G의 '추적 설명'을 계산해 해결한다.

문제 G에 대한 유괴적 설명은 강제적 술어들의 긍정적(그리고 때로는 부정적) 접지 인스턴스 집합으로, 이러한 요소들이 논리 프로그램 P에 추가되었을 때, 문제 G와 무결성 제약조건 IC가 모두 안고 있는 것이다. 따라서 유괴적 설명은 강제적 술어의 전체 또는 부분적 정의를 추가하여 논리 프로그램 P를 확장한다. 이렇게 하면 P와 IC의 문제 영역에 대한 설명에 따라 납북적 설명이 문제의 해답을 형성한다. 납북적 설명이 제공하는 문제 설명의 연장이나 완성은 지금까지 문제 해결책에 포함되지 않았던 새로운 정보를 제공한다. 종종 무결성 제약으로 표현되는 다른 솔루션보다 한 솔루션을 선호하기 위한 품질 기준을 적용하여 문제 G에 대한 특정 납치적 설명을 선택할 수 있다.

ALP의 연산에서는 정규 로직 프로그래밍의 역추론(문제를 하위 문제로 줄이기 위해)과 일종의 무결성 검사를 결합하여 납북적 설명이 무결성 제약조건을 만족한다는 것을 보여준다.

다음의 두 가지 예는 ALP의 엄격한 구문이 아닌 간단한 구조화된 영어로 쓰여져 있으며, ALP에서 유괴적 설명의 개념과 문제 해결과의 관계를 보여준다.

예 1

$\langle P,A,{\mathit {IC}}\rangle$ 논리 프로그램, $\langle P,A,{\mathit {IC}}\rangle$ P $\langle P,A,{\mathit {IC}}\rangle$ , $\langle P,A,{\mathit {IC}}\rangle$ , I $\langle P,A,{\mathit {IC}}\rangle$ $\langle P,A,{\mathit {IC}}\rangle$ ${\displaystyle \langle P,A,{\mathit$ { $IC$ $}\rangele$ $\langle P,A,{\mathit {IC}}\rangle$ 에는 다음 문장이 $P$ P $P$ 에 있다.

  비가 오면 풀이 젖는다.
   스프링클러가 켜져 있으면 잔디가 젖는다.
   태양이 빛나고 있었다.

$A$ $A$ 의 과부하 술어는 "비가 내렸다" "스프링클러가 켜졌다" 및 ${\mathit {IC}}$ ${\mathit {IC}}$ ${\$ 의 유일한 무결성 제약 조건이다 $A$ . $IC}}$ 은(는) 다음과 ${\mathit {IC}}$ 같다.

  비가 와서 햇빛이 비쳤다면 거짓이었다.

풀이 젖었다는 관측에는 '비가 왔다'와 '스프링클러가 켜졌다'라는 두 가지 잠재적 설명이 담겨 있어 관측을 수반한다. 그러나 두 번째 잠재적 설명인 "스프링클러가 켜져 있었다"만이 무결성 제약을 만족시킨다.

예 2

다음(간단한) 조항으로 구성된 납치 논리 프로그램을 고려하십시오.

  X가 미국에서 태어났다면 X는 시민이다.
   X는 미국 밖에서 X가 태어나고 X는 미국 거주자, X는 귀화하면 시민이다.
   X는 미국 밖에서 X가 태어나고 Y는 X의 어머니, Y는 시민이고 X가 등록되어 있으면 시민이다.
   메리는 존의 어머니다.
   메리는 시민이다.

"미국에서 태어나다" "미국 밖에서 태어나다" "미국에서 태어나다" "미국에서 태어나다" "귀화한다" "등록된다" 및 무결성 제약 조건과 함께 다음과 같은 다섯 가지 강제적 술어와 함께:

  존이 미국 거주자라면 거짓이다.

"존은 시민이다"라는 목표는 두 가지 납치 해결책을 가지고 있는데, 그 중 하나는 "존은 미국에서 태어났다"이고, 다른 하나는 "존은 미국 밖에서 태어났다"와 "존은 미국 밖에서 태어났다"이다. 주거와 귀화에 의한 시민이 되는 잠재적 해결책은 청렴의 제약을 위반하기 때문에 실패한다.

ALP의 보다 공식적인 구문에도 기재된 보다 복잡한 예는 다음과 같다.

예 3

아래의 유괴 논리 프로그램은 대장균 박테리아의 유당 신진대사의 간단한 모델을 설명한다. 프로그램 P는 대장균이 두 개의 효소를 침투시켜 갈락토시다아제를 만들면 당유당을 먹일 수 있다고 (첫 번째 규칙에서) 설명한다. 모든 효소와 마찬가지로 이러한 효소들이 발현되는 유전자(Gene)에 의해 코딩되면 만들어진다(두 번째 규칙으로 설명된다). 투과효소와 갈락토시다효소의 두 효소는 각각 두 개의 유전자인 lac(y)와 lac(z)에 의해 코딩되는데, 이는 피연산자로 불리는 유전자의 군집(lac(X)에서 나타나며, 이는 포도당의 양(amt)이 적고 유당량이 높거나 둘 다 중간 수준일 때 발현된다(제4와 제50 참조).h rule). 추정 가능한 술어의 모든 지상 인스턴스(instance)를 "금액"으로 선언한다. 이는 모델에서 다양한 물질의 양을 알 수 없다는 것을 반영한다. 이것은 각각의 문제 사례에서 결정되어야 할 불완전한 정보다. 무결성 제약인 IC는 모든 물질의 양(S)은 오직 하나의 값만 취할 수 있다고 명시한다.

도메인 지식(P)

   먹이다(유당의) :- 만들다(스며들다), 만들다(갈락토시다아제).    만들다(효소) :- 부호를 붙이다(유전자, 효소), 표현하다(유전자).    표현하다(옻칠을 하다(X)) :- 분량(포도당, 낮은), 분량(유당의, 안녕).    표현하다(옻칠을 하다(X)) :- 분량(포도당, 중간의), 분량(유당의, 중간의).    부호를 붙이다(옻칠을 하다(y), 스며들다).    부호를 붙이다(옻칠을 하다(z), 갈락토시다아제).    온도(낮은) :- 분량(포도당, 낮은).

무결성 제약 조건(IC)

   거짓의 :- 분량(S, V1), 분량(S, V2), V1 ≠ V2.

무형자산(A)

   강제적_불가역적(분량).

문제 목표는 $G={\text{feed(lactose)}}$ = $){\$ G $={\text{feed(락토스$ 이것은 설명해야 할 관찰로 발생할 수도 있고, 계획을 찾아 달성해야 할 사정으로 나타날 수도 있다. 이 목표에는 두 가지 유괴 설명이 있다.

{\begin}\Delta _{1}=\{\text{양(lactose, hi), 양(글루코스, low)\\\\Delta _{2}=\text}{양(lactose, medium), 양(글루코스, medium)}}\}\end{case}}

둘 중 어느 쪽을 채택할 것인가는 이용 가능한 추가 정보에 의존할 수 있다. 예를 들어, 포도당 수치가 낮을 때 유기체가 특정한 행동을 보인다는 것을 알 수 있다 - 그러한 추가 정보는 유기체의 온도가 낮다는 것이다 – 그리고 이것의 진실이나 거짓을 관찰함으로써 가능하다.첫 번째 설명과 두 번째 설명을 각각 선택하기 위해 울다.

일단 설명이 선택되면, 이것은 이론의 일부가 되며, 이것은 새로운 결론을 도출하는 데 사용될 수 있다. 설명과 더 일반적으로는 이러한 새로운 결론들이 문제의 해결책을 형성한다.

형식 의미론

ALP에서 유괴적 설명의 중심 개념의 공식적 의미론은 다음과 같은 방법으로 정의될 수 있다.

납치 논리 $\langle P,A,{\mathit {IC}}\rangle$ 인 $\langle P,A,{\mathit {IC}}\rangle$ P $\langle P,A,{\mathit {IC}}\rangle$ , $\langle P,A,{\mathit {IC}}\rangle$ , $\langle P,A,{\mathit {IC}}\rangle$ $\langle P,A,{\mathit {IC}}\rangle$ $\langle P,A,{\mathit {IC}}\rangle$ ${\displaystyle \langle P,A,{\mathit$ { $IC}}\rangele$ 문제 $G$ $G$ 에 대한 유괴적 설명은 다음과 같은 과부하 술어에 대한 접지 $\Delta$ 원자의 $\Delta$ {\ $displaystyle$ \ $Delta }$ 집합이다 $G$ .

$\displaystyle P\cup \Delta \models G}$
$\displaystyle P\cup \Delta \models IC}$
$P\cup \Delta$ $P\cup \Delta$ $P\cup \Delta$ $P\cup \Delta$ 이 $P \cup \Delta$ (가) 일관됨

이 정의는 로직 프로그래밍의 기본 의미론의 선택을 열어두며, 이를 통해 우리는 관련 관계 $⊨{\displaystyle \models}$ 와 $\models$ (확장된) 로직 프로그램의 일관성 개념을 정확히 알 수 있다. 완료, 안정적 또는 근거가 충분한 의미론과 같은 로직 프로그래밍의 다른 의미론들은 납치적 설명과 그에 따라 다른 형태의 ALP 프레임워크에 대한 다른 개념을 주기 위해 (실무에 사용되어 왔다) 수 있다.

위의 정의는 I ${\mathit {IC}}$ ${\$ mathit {}의 무결성 제약 조건의 역할 공식화에 대한 특정한 견해를 취한다. $IC}}$ 을(를) 가능한 유괴 해결책에 대한 제한 사항으로 ${\mathit {IC}}$ . 이는 납치 해법으로 확장된 논리 프로그램에 의해 수반되어야 하므로 확장 논리 프로그램의 모든 모델( $\Delta$ ${\displaystyle \Delta$ 에서 무결성 제약 조건의 요건을 충족함을 의미한다. 경우에 따라서는 불필요하게 강력하고 일관성이 약한 요구 조건( $P\cup {\mathit {IC}}\cup \Delta$ , P $P\cup {\mathit {IC}}\cup \Delta$ I C $P\cup {\mathit {IC}}\cup \Delta$ Δ $P\cup {\mathit {IC}}\cup \Delta$ {\ $displaystyle P$ \cup {\ $mathit {\$ mathit ${\$ displaystyle P\ $cup$ }). $IC}\cup \Delta }$ 은 $P \cup \mathit{IC} \cup \Delta$ (는) 일관성이 있으며 충분할 수 있으며, 이는 무결성 제약이 지속되는 확장 프로그램의 최소한 하나의 모델(후속 세계)이 존재함을 의미한다. 실제로, 많은 경우, 무결성 제약의 역할을 공식화하는 이 두 가지 방법은 논리 프로그램과 그 확장성이 항상 고유한 모델을 가지고 있기 때문에 일치한다. 많은 ALP 시스템은 무결성 제약조건의 수반 관점을 사용한다. 이 관점은 문제 목표와 동일한 방식으로 제약조건을 다루기 때문에 무결성 제약조건의 충족을 위한 추가적인 전문적 절차 없이도 쉽게 구현될 수 있기 때문이다. 많은 실제 사례에서 ALP의 납치적 설명에 대한 이 공식 정의의 세 번째 조건은 사소한 것으로 만족되거나 일관성을 포착하는 특정 무결성 제약조건을 이용하여 두 번째 조건에 포함된다.

구현 및 시스템

ALP 구현의 대부분은 로직 프로그래밍의 SLD 해상도 기반 연산 모델을 확장한다. 또한 ALP는 ASP 시스템을 채용할 수 있는 ASP(Answer Set Programming)와의 연계를 통해 구현될 수 있다. 이전 접근법의 시스템 예로는 ACLP, A-system, CIFF, SCIFF, ABDUAL 및 ProLogICA가 있다.

참고 항목

메모들

참조

Poole, D.; Goebel, R.; Aleliunas, R. (1987). "Theorist: a logical reasoning system for defaults and diagnosis". In Cercone, Nick; McCalla, Gordon (eds.). The Knowledge Frontier: Essays in the Representation of Knowledge. Springer. pp. 331–352. ISBN 978-0-387-96557-4.
Kakas, A.C.; Mancarella, P. (1990). "Generalised Stable Models: A Semantics for Abduction". In Aiello, L.C. (ed.). ECAI 90: proceedings of the 9th European Conference on Artificial Intelligence. Pitman. pp. 385–391. ISBN 978-0273088226.
Console, L.; Dupre, D.T.; Torasso, P. (1991). "On the Relationship between Abduction and Deduction". Journal of Logic and Computation. 1 (5): 661–690. CiteSeerX 10.1.1.31.9982. doi:10.1093/logcom/1.5.661.
Kakas, A.C.; Kowalski, R.A.; Toni, F. (1993). "Abductive Logic Programming". Journal of Logic and Computation. 2 (6): 719–770. CiteSeerX 10.1.1.37.3655. doi:10.1093/logcom/2.6.719.
Denecker, Marc; De Schreye, Danny (February 1998). "SLDNFA: An Abductive Procedure for Abductive Logic Programs". Journal of Logic Programming. 34 (2): 111–167. CiteSeerX 10.1.1.21.6503. doi:10.1016/S0743-1066(97)00074-5.
Denecker, M.; Kakas, A.C. (July 2000). "Special issue: abductive logic programming". Journal of Logic Programming. 44 (1–3): 1–4. doi:10.1016/S0743-1066(99)00078-3.
Denecker, M.; Kakas, A.C. (2002). "Abduction in Logic Programming". In Kakas, A.C.; Sadri, F. (eds.). Computational Logic: Logic Programming and Beyond: Essays in Honour of Robert A. Kowalski. Lecture Notes in Computer Science. Vol. 2407. Springer. pp. 402–437. ISBN 978-3-540-43959-2.
Poole, D. (1993). "Probabilistic Horn abduction and Bayesian networks" (PDF). Artificial Intelligence. 64 (1): 81–129. doi:10.1016/0004-3702(93)90061-F.
Esposito, F.; Ferilli, S.; Basile, T.M.A.; Di Mauro, N. (February 2007). "Inference of abduction theories for handling incompleteness in first-order learning" (PDF). Knowl. Inf. Syst. 11 (2): 217–242. doi:10.1007/s10115-006-0019-5. S2CID 10699982. Archived from the original (PDF) on 2011-07-17.

외부 링크

Search