1차 유도 학습자

기계학습에서 1차 유도학습자(FOIL)는 규칙 기반 학습 알고리즘입니다.

배경

1990년 로스 퀸랜에 ^[1]의해 개발된 FOIL은 1차 술어 미적분의 부분 집합인 함수 없는 혼 절을 학습합니다.어떤 개념의 긍정적 및 부정적 예와 일련의 배경지식 술어가 주어지면 FOLE은 유도적으로 개념에 대한 논리적 개념 정의 또는 규칙을 생성합니다.유도 규칙은 상수(color(X, red)가 color(X,Y), red(Y)가 되는 함수 기호를 포함하지 않아야 하지만 부정 술어를 허용할 수 있습니다. 재귀 개념도 학습할 수 있습니다.

ID3 알고리즘과 마찬가지로 FOLE Hill은 정보 이론에 기초한 메트릭을 사용하여 데이터를 포함하는 규칙을 구축합니다.단, ID3과 달리 FOIL은 분할 및 정복이 아닌 분리 및 정복 방식을 사용하며,^{[citation needed]} 한 번에 하나의 규칙을 만들고 알고리즘의 다음 반복을 위해 확인되지 않은 예를 수집하는 데 초점을 맞추고 있습니다.

알고리즘.

FOLE 알고리즘은 다음과 같습니다.

입력 예 목록

산출량 1차 술어 논리에서의 규칙

포일(예)

Pos를 긍정적인 예로 들자.

Pred를 학습할 술어로 합니다.

Pos가 비워질 때까지 다음을 수행합니다.

부정적인 예를 들자.

본문을 공백으로 설정

LearnClause Body 호출

규칙에 사전 ← 본문 추가

본문을 만족시키는 모든 예제를 Pos에서 제거합니다.

절차 LearnClause Body

Neg가 비워질 때까지 다음을 수행합니다.

리터럴 L을 선택합니다.

L을 본체에 연결

L을 충족하지 않는 예제를 Neg에서 제거합니다.

예

FOIL의 과제는 아버지(X,Y)와 부모(X,Y)의 관계가 주어졌을 때 할아버지(X,Y)의 개념을 배우는 것이라고 가정합니다.또한, 우리의 현재 신체는 할아버지(X,Y) ← 부모(X,Z)로 구성되어 있다고 가정합니다.이 리터럴을 작성하려면 Body를 리터럴 father(X,X), father(Y,Z), parent(U,Y) 또는 그 외의 많은 리터럴과 결합함으로써 확장할 수 있습니다.알고리즘은 술어 이름과 술어 변수 세트를 모두 선택해야 합니다(이 중 적어도1개는 절의 부정되지 않은 리터럴에 이미 존재해야 합니다).FOIL이 리터럴 부모(X,Z)를 결합함으로써 절 grandper(X,Y) ← true를 확장하면 새로운 변수 Z를 도입하는 것이다.현재 긍정적인 예는 할아버지(X,Y)가 참이고 부모(X,Z)가 참인 값 <X,Y,Z>로 구성됩니다.부정적인 예는 할아버지(X,Y)가 참이지만 부모(X,Z)가 거짓인 값입니다.

부모(X,Z)가 추가된 후 다음 FOIL 반복 시 알고리즘은 새로운 리터럴의 적어도1개의 변수가 기존 구에 존재하도록 술어 이름과 변수의 모든 조합을 고려합니다.따라서 검색 ^[2]공간이 매우 넓어집니다.FOIL 이론의 몇 가지 확장에 따르면 기본 알고리즘에 추가할 경우 이 검색 공간을 ^{[citation needed]}대폭 줄일 수 있습니다.

내선번호

FOCL 알고리즘^[3](First Order Combined Learner)은 다양한 방법으로 FOLE을 확장하며, 이는 FOCL이 구축 중인 절을 확장하면서 테스트할 리터럴을 선택하는 방법에 영향을 미칩니다.일련의 예(강력 술어라고 함)가 아닌 규칙에 정의된 술어처럼 서치 공간에 대한 제약이 허용됩니다. 가장 중요한 것은 잠재적으로 잘못된 가설이 학습되는 술어에 대한 초기 근사치로서 허용됩니다.FOCL의 주요 목표는 설명 기반 학습(EBL) 방법을 FOLE의 경험적 방법에 통합하는 것이다.

그러나 FOCL over FOLE에 대한 추가 지식이 제공되지 않는 경우에도 깊이 우선 검색과 유사한 반복 확장 검색 전략을 활용합니다. 즉, FOCL은 자유 변수를 도입하지 않고 절을 학습하려고 시도합니다.이것이 실패했을 경우(양수 게인 없음), 자유 변수의 수가 술어에 사용되는 최대값을 초과할 때까지 장애마다 1개의 자유 변수가 추가로 허용됩니다.

제약

변수에 타이핑 제한을 두지 않는 FOLE과 달리, FOCL은 간단한 형태의 배경 지식을 통합하는 저렴한 방법으로 타이핑을 사용합니다.예를 들어, 술어 livesAt(X,Y)에는 livesAt(사람, 위치) 유형이 있을 수 있습니다.단, 타입이 없는 경우 nextDoor(X,Y)는 사람 X와 사람 Y가 서로 이웃하고 있는지, 또는 두 위치가 서로 이웃하고 있는지 여부를 판단할 수 있습니다.타입의 경우 이 기능을 유지하려면 nextDoor(person, person)와 nextDoor(location, location)의 두 가지 다른 술어가 필요합니다.단, 이 입력 메커니즘은 isPerson(X)이나 isLocation(Y) 등의 술어가 필요하지 않으며, A와 B가 사람 변수로 정의되어 있을 때 livesAt(A, B)를 고려할 필요가 없기 때문에 서치 공간이 줄어듭니다.또한, 입력은 높은 정보 이득을 가지고 있는 것처럼 보일 수 있는 lifesAt(A,B)와 같은 불가능한 리터럴을 고려에서 제거함으로써 결과 규칙의 정확성을 향상시킬 수 있습니다.

FOCL은 equals(X,X) 또는 between(X,X,Y)와 같은 사소한 술어를 구현하는 대신 변수에 암묵적인 제약 조건을 도입하여 검색 공간을 더욱 줄입니다.일부 술어는 모든 변수가 고유해야 하며, 다른 술어는 교환성(인접(X,Y)은 인접(Y,X)과 동일)을 가져야 하며, 다른 술어는 특정 변수가 current 절에 존재해야 하며, 다른 많은 잠재적 제약 조건이 필요할 수 있습니다.

조작 규칙

운영 규칙은 확장적으로 정의되거나 술어가 참인 튜플 목록으로 정의되는 규칙입니다.FOLE은 동작 규칙만 허용합니다.FOCL은 비동작 규칙이라고 불리는 규칙과 부분적으로 정의되거나 잘못된 규칙의 조합을 허용하도록 기술 기반을 확장합니다.부분 정의를 허용하면 알고리즘이 자체적으로 이러한 부분 정의를 생성할 필요가 없기 때문에 필요한 작업량을 줄일 수 있습니다.또한 잘못된 규칙은 양의 정보를 얻을 수 없다고 판단될 경우 폐기되므로 필요한 작업에 크게 추가되지 않습니다.비작동 규칙은 결합하는 개별 규칙이 정보 이득을 제공하는 것이 아니라 결합할 때 유용하기 때문에 유리합니다.FOCL의 반복에서 가장 많은 정보 게인을 가진 리터럴이 작동하지 않을 경우 리터럴은 동작 가능하며 그 정의는 작성 중인 절에 추가됩니다.

입력 조작할 리터럴, 긍정적인 예 목록, 부정적인 예 목록

산출량 조작 형식의 리터럴

Operationalize(리터럴, 긍정적인 예, 부정적인 예)

리터럴이 동작 가능한 경우

리터럴 반환

빈 세트에 OperationalLiterals 초기화

리터럴 정의의 각 절에 대해

긍정적인 예와 부정적인 예에 대한 절의 정보 게인을 계산합니다.

게인이 최대인 절의 경우

절의 각 리터럴 L에 대해

Operationalize(L, 긍정적인 예, 부정적인 예)를 Operational Literals에 추가합니다.

작업 규칙은 문자 그대로 lessThan(X,Y)일 수 있으며, 비작업 규칙은 (X,Y,Z) ← lessThan(X,Y), lessThan(Y,Z) 사이일 수 있습니다.

초기 규칙

기술 자료에 비작동 규칙을 추가하면 FOCL이 검색해야 하는 공간의 크기가 증가합니다.알고리즘은 단순히 대상 개념(예를 들어 할아버지(X,Y))으로 알고리즘을 제공하는 대신 정확성을 테스트하고 학습된 개념에 대해 연산하는 일련의 비연산 규칙을 입력으로 받아들인다.올바른 목표 개념을 사용하면 계산 시간과 정확도가 분명히 향상되지만, 잘못된 개념이라도 알고리즘에 작업 기반을 제공하고 정확도와 ^[3]시간을 향상시킬 수 있습니다.

레퍼런스

• http://www.csc.liv.ac.uk/~frans/KDD/소프트웨어/FOIL_PRM_CPAR/foil.html