레테 알고리즘

Rete algorithm

레테 알고리즘(//riːtiː/RE-tee, /ˈreɪtiː/RAY-tee, 드물게 /ˈriːt/REET, /rrteɪ/re-Tay)은 규칙 기반 시스템을 구현하기 위한 패턴 매칭 알고리즘이다. 알고리즘은 지식 기반에서 많은 규칙이나 패턴을 많은 사물이나 사실에 효율적으로 적용하기 위해 개발되었다. 그것은 그것의 데이터 저장소와 사실에 근거하여 어떤 시스템 규칙들이 발사되어야 하는지를 결정하는 데 사용된다. 레테 알고리즘은 찰스 L에 의해 설계되었다. 카네기 멜론 대학용서, 1974년 작업 논문으로 처음 발표되었고, 이후 1979년 박사 논문과 1982년 논문에서 상세히 기술되었다.[1]

개요

전문가 시스템순진한 구현은 각 규칙지식 기반에서 알려진 사실들과 대조하여, 필요한 경우 그 규칙을 해제한 다음, 다음 규칙으로 넘어갈 수 있다(그리고 완료되었을 때 첫 번째 규칙으로 되돌릴 수 있다. 심지어 중간 크기의 규칙과 사실 지식베이스를 위해, 이 순진한 접근법은 너무 느리게 수행된다. 레테 알고리즘은 보다 효율적인 구현을 위한 기초를 제공한다. 레테 기반의 전문가 시스템은 노드 네트워크를 구축하는데, 여기서 각 노드(루트 제외)는 규칙의 왼쪽(조건 부분)에서 발생하는 패턴에 해당한다. 루트 노드에서 리프 노드까지의 경로는 왼쪽의 완전한 규칙을 정의한다. 각각의 노드는 그 패턴을 만족시키는 사실에 대한 기억을 가지고 있다. 이 구조는 본질적으로 일반화된 3단계다. 새로운 사실이 주장되거나 수정될 때, 그것들은 네트워크를 따라 전파되어, 그 사실이 그 패턴과 일치할 때 노드에 주석을 달게 한다. 사실 또는 사실의 조합으로 인해 주어진 규칙에 대한 모든 패턴이 충족되면 리프 노드에 도달하고 해당 규칙이 트리거된다.

Rete는 디지털 장비 주식회사 R1을 포함한 초기 시스템을 구축하는 데 사용된 OPS5 생산 시스템 언어의 핵심 엔진으로 처음 사용되었다. Rete는 Tibco Business Events, Newgen OmniRules, CLIP, Jess, Drools, IBM Operational Decision Management, OPSJ, Blaze Advisor, BizTalk Rules Engine, Sleak, Clara 및 Sparklon Logic SMARS 등 많은 인기 있는 규칙 엔진과 전문가 시스템 쉘의 기반이 되었다. 레테'라는 단어는 라틴어로 '넷'이나 '콤비'를 의미한다. 현대 이탈리아어에서는 같은 단어가 네트워크라는 뜻으로 쓰인다. 보도에 따르면 찰스 구디는 '레테'라는 용어를 채택한 것은 해부학에서 혈관과 신경섬유의 네트워크를 묘사하기 위해 사용했기 때문이라고 한다.[2]

레테 알고리즘은 속도를 높이기 위해 메모리를 희생하도록 설계되었다. 대부분의 경우, 순전한 구현에 대한 속도 증가는 몇 가지 정도(Rete 성능은 이론적으로 시스템의 규칙 수와 무관하기 때문에)이다. 그러나 매우 큰 전문가 시스템에서는 원래의 레테 알고리즘이 메모리와 서버 소비 문제에 부딪히는 경향이 있다. 새로운 알고리즘과 레테 기반 알고리즘은 그 이후 더 적은 메모리(예: Rete*[3] 또는 Collection Oriented Match[4])를 필요로 하는 다른 알고리즘이 설계되었다.

설명

Rete 알고리즘은 패턴 매칭 생산 시스템(규칙 엔진의 범주)에서 생산("규칙")과 데이터 튜플("사실")을 일치시키는 기능을 담당하는 기능의 구현에 대한 일반적인 논리적 설명을 제공한다. 생산은 하나 이상의 조건과 조건과 일치하는 각각의 전체 사실 집합에 대해 수행될 수 있는 일련의 행동들로 구성된다. 조건 테스트 팩트 속성(사실 유형 지정자/식별자 포함) 레테 알고리즘은 다음과 같은 주요 특성을 나타낸다.

  • 노드 공유를 통해 특정 유형의 중복성을 감소시키거나 제거한다.
  • 서로 다른 팩트 유형 간의 조인을 수행할 때 부분 일치를 저장한다. 이는 다시 생산 시스템의 작업 메모리에 변경이 이루어질 때마다 생산 시스템이 모든 사실에 대한 완전한 재평가를 피할 수 있게 한다. 대신 생산 시스템은 작동 메모리에 대한 변화(델타)만 평가하면 된다.
  • 그것은 사실들이 작동 기억에서 철회될 때 기억 요소의 효율적인 제거를 가능하게 한다.

레테 알고리즘은 전방 체인과 회의지원하기 위해 매치-리졸브-액션 사이클을 이용하는 패턴 매칭 엔진 내에서 매칭 기능을 구현하는 데 널리 사용된다.

  • 그것은 검색 네트워크에서 많은 또는 모든 가능한 해결책을 찾아야 할 때 중요한 기능인 다대다 일치의 수단을 제공한다.

검색은 상위 수준의 규칙 집합을 나타내는 반복 그래프로 지시된다. 그것들은 일반적으로 인메모리 객체의 네트워크를 이용하여 런타임에 표현된다. 이러한 네트워크는 규칙 조건(패턴)과 사실(관계 데이터 튜플)을 일치시킨다. Rete 네트워크는 임의의 수의 데이터 튜플에 조건부로 투영, 선택 및 결합을 수행하는 관계형 쿼리 프로세서의 한 유형으로 작용한다.

프로덕션(규칙)은 일반적으로 분석가와 개발자가 일부 고급 규칙 언어를 사용하여 캡처하고 정의한다. 그것들은 규칙 집합으로 수집되고, 종종 런타임에 실행 가능한 레트로 변환된다.

사실들이 작동 메모리에 "asserted"될 때, 엔진은 각각의 사실에 대한 WME(Working Memory Elements)를 만든다. 사실들은 n-tuple이며 따라서 임의의 수의 데이터 항목을 포함할 수 있다. 각 WME는 전체 n-투플을 보유할 수도 있고, 또는 각 WME가 고정 길이 튜플을 포함하는 WME 집합으로 각 사실을 나타낼 수도 있다. 이 경우 튜플은 일반적으로 3중(쌍 3중)이다.

각 WME는 단일 루트 노드에서 Rete 네트워크에 들어간다. 루트 노드는 각 WME를 하위 노드로 전달하며, 각 WME는 네트워크를 통해 전파되어, 터미널 노드에 도착할 때까지 중간 메모리에 저장될 수 있다.

알파 네트워크

노드 그래프의 "왼쪽" (알파) 쪽은 WME 속성과 상수 값을 일치시키는 간단한 조건부 테스트를 기반으로 개별 WME를 선택하는 것을 담당하는 차별 네트워크를 형성한다. 차별 네트워크의 노드들은 또한 동일한 WME의 둘 이상의 속성을 비교하는 테스트를 수행할 수 있다. 만약 WME가 한 노드로 대표되는 조건과 성공적으로 일치한다면, 그것은 다음 노드로 전달된다. 대부분의 엔진에서 루트 노드의 즉각적인 하위 노드는 각 WME의 엔터티 식별자 또는 팩트 유형을 테스트하는 데 사용된다. 따라서 동일한 엔터티 유형을 나타내는 모든 WME는 일반적으로 차별 네트워크에서 주어진 노드 분기를 통과한다.

차별 네트워크 내에서 알파 노드(일명 1입력 노드라고도 함)의 각 분기는 알파 메모리라고 하는 메모리에서 종료된다. 이러한 메모리는 주어진 노드 분기의 각 노드의 각 조건과 일치하는 WME 컬렉션을 저장한다. 분기에서 적어도 하나의 조건을 일치시키지 못하는 WME는 해당 알파 메모리 내에서 구체화되지 않는다. 알파 노드 분기는 조건 중복성을 최소화하기 위해 분기할 수 있다.

베타 네트워크

그래프의 "우측"(베타)은 주로 서로 다른 WME 사이의 조인을 수행한다. 그것은 선택사항이며, 필요한 경우에만 포함된다. 각 노드가 "좌" 및 "우" 입력을 갖는 2입력 노드로 구성된다. 각 베타 노드는 그 출력을 베타 메모리로 보낸다.

레테에 대한 설명에서, 베타 네트워크 내에서 토큰 패싱을 언급하는 것이 일반적이다. 그러나 이 기사에서는 서로 다른 구현 옵션과 토큰의 기본 목적 및 사용을 인정하여 토큰이 아닌 WME 목록 관점에서 데이터 전파를 기술할 것이다. 어떤 WME 목록이라도 베타 네트워크를 통과하면 새로운 WME가 추가될 수 있고 그 목록은 베타 메모리에 저장될 수 있다. 베타 메모리의 WME 목록은 주어진 생산 조건의 부분 일치를 나타낸다.

베타 노드 분기의 끝에 도달하는 WME 목록은 단일 생산에 대한 완전한 일치를 나타내며, 터미널 노드로 전달된다. 이러한 노드를 p-노드라고 부르기도 하는데, 여기서 "p"는 생산을 의미한다. 각 터미널 노드는 단일 생산을 나타내며, 터미널 노드에 도착하는 각 WME 목록은 해당 생산 조건과 일치하는 WME의 전체 집합을 나타낸다. 그것이 받는 각 WME 목록에 대해, 생산 노드는 "agenda"에서 새로운 생산 인스턴스를 "활성화" 의제는 일반적으로 우선순위가 정해진 대기열로 구현된다.

베타 노드는 일반적으로 베타 메모리에 저장된 WME 목록과 알파 메모리에 저장된 개별 WME 목록 사이에서 조인을 수행한다. 각 베타 노드는 두 개의 입력 메모리와 연관되어 있다. 알파 메모리는 WM을 보유하며 새로운 WME를 저장할 때마다 베타 노드에서 "오른쪽" 활성화를 수행한다. 베타 메모리는 새로운 WME 목록을 저장할 때마다 WME 목록을 보유하며 베타 노드에서 "왼쪽" 활성화를 수행한다. 조인 노드가 올바르게 활성화되면 입력 알파 메모리에서 새로 저장된 WME의 하나 이상의 속성을 입력 베타 메모리에 포함된 각 WME 목록의 특정 WME의 지정된 속성과 비교한다. 조인 노드가 왼쪽 활성화되면 베타 메모리에 새로 저장된 단일 WME 목록을 통과하여 지정된 WME의 특정 속성 값을 검색한다. 이 값을 알파 메모리에 있는 각 WME의 속성 값과 비교한다.

각 베타 노드는 베타 메모리에 저장되거나 터미널 노드로 직접 전송되는 WME 목록을 출력한다. 엔진이 후속 베타 노드에서 왼쪽 활성화를 추가로 수행할 때마다 WME 목록은 베타 메모리에 저장된다.

논리적으로 베타 노드의 분기의 머리 부분에 있는 베타 노드는 네트워크에 있는 어떤 베타 메모리로부터도 입력을 받지 않기 때문에 특별한 경우다. 엔진마다 다른 방식으로 이 문제를 처리한다. 일부 엔진은 특수 어댑터 노드를 사용하여 베타 노드의 왼쪽 입력에 알파 메모리를 연결한다. 다른 엔진은 베타 노드가 두 개의 알파 메모리에서 직접 입력을 가져갈 수 있도록 해, 하나는 "좌측" 입력으로, 다른 하나는 "우측" 입력으로 취급한다. 두 경우 모두, "헤드" 베타 노드는 두 개의 알파 메모리로부터 입력 정보를 얻는다.

노드 중복을 제거하기 위해 알파 또는 베타 메모리 하나를 사용하여 여러 베타 노드에서 활성화를 수행할 수 있다. 결합 노드뿐만 아니라 베타 네트워크는 아래에 설명된 추가 노드 유형을 포함할 수 있다. Rete에 베타 네트워크가 없는 경우 알파 노드는 각각 단일 WME를 포함하는 토큰을 p-노드로 직접 공급한다. 이 경우 WME를 알파 메모리에 저장할 필요가 없을 수도 있다.

갈등해결

어떤 한 번의 매치 리졸브-액션 사이클 동안 엔진은 현재 작동 메모리에 주장된 사실에 대해 가능한 모든 매칭을 찾을 것이다. 현재의 모든 일치 항목이 발견되고 해당 생산 인스턴스가 의제에 활성화되면 엔진은 생산 인스턴스를 "해고"할 수 있는 순서를 결정한다. 이를 갈등 해결이라고 하며, 활성화된 생산 인스턴스 목록을 갈등 세트라고 한다. 순서는 규칙 우선 순위(생활성), 규칙 순서, 각 사례에 포함된 사실이 작업 메모리에 주장된 시간, 각 생산의 복잡성 또는 기타 기준에 기초할 수 있다. 많은 엔진은 규칙 개발자들이 서로 다른 충돌 해결 전략들 사이에서 선택하거나 여러 전략들의 선택을 연쇄적으로 할 수 있게 해준다.

충돌해결은 레테 알고리즘의 일부로 정의되지 않고 알고리즘과 함께 사용된다. 일부 특수 생산 시스템은 충돌 해결을 수행하지 않는다.

생산실행

충돌 해결을 수행한 엔진은 이제 첫 번째 생산 인스턴스를 "발사"하여 생산과 관련된 조치 목록을 실행한다. 작업은 프로덕션 인스턴스의 WME 목록으로 대표되는 데이터에 작용한다.

기본적으로 엔진은 모든 생산 인스턴스가 발사될 때까지 각 생산 인스턴스를 순서대로 계속 발사한다. 각 생산 인스턴스는 한 번의 매치 리졸브-액션 사이클 동안 기껏해야 한 번만 실행된다. 이 특성은 굴절이라고 불린다. 단, 생산 인스턴스 발생 순서는 작업 메모리를 변경하여 어느 단계에서나 중단될 수 있다. 규칙 동작은 엔진의 작동 메모리에서 WME를 주장하거나 철회하는 지침을 포함할 수 있다. 모든 단일 생산 인스턴스가 하나 이상의 그러한 변경을 수행할 때마다 엔진은 즉시 새로운 매치 리졸브-액션 사이클로 들어간다. 여기에는 현재 작동 중인 메모리에 있는 WME에 대한 "업데이트"가 포함된다. 업데이트는 WME를 리트랙트한 다음 다시 어젠다에 대한 생산 인스턴스 목록이 변경될 수 있는 변경된 데이터의 일치를 엔진에서 수행한다. 따라서 특정 생산 인스턴스에 대한 조치가 실행된 후 이전에 활성화된 인스턴스가 비활성화되어 의제에서 제거되고 새로운 인스턴스가 활성화되었을 수 있다.

새로운 매치 리졸브-액션 사이클의 일환으로 엔진은 의제에 대한 충돌 해결을 수행한 다음 현재 첫 번째 인스턴스를 실행한다. 엔진은 더 이상의 생산 인스턴스가 의제에 존재하지 않을 때까지 생산 인스턴스를 계속 발사하고 새로운 매치 리졸브-액션 사이클에 돌입한다. 이 시점에서 규칙 엔진은 작업을 완료한 것으로 간주되고 정지한다.

일부 엔진은 이전 사이클에서 실행된 특정 생산 사례가 여전히 의제에 존재할 수 있음에도 불구하고 새로운 사이클에서 다시 실행되지 않는 고급 굴절 전략을 지원한다.

의제가 결코 빈 상태에 도달하지 않는 끝없는 루프로 엔진이 진입하는 것이 가능하다. 이러한 이유로 대부분의 엔진은 생산 액션 목록에서 호출할 수 있는 명시적인 "할트" 동사를 지원한다. 또한 일정 횟수의 반복 후에 끝나지 않는 루프가 자동으로 정지되는 자동 루프 감지 기능을 제공할 수 있다. 일부 엔진은 의제가 비어 있을 때 엔진이 정지하는 대신 외부적으로 새로운 사실이 주장될 때까지 엔진이 대기 상태로 들어가는 모델을 지원한다.

분쟁 해결의 경우, 활성화된 생산 인스턴스(instance)의 발사는 레테 알고리즘의 특징이 아니다. 그러나, 그것은 레테 네트워크를 사용하는 엔진의 중심적인 특징이다. Rete 네트워크에 의해 제공되는 최적화 중 일부는 엔진이 다중 매치 리졸브-액션 사이클을 수행하는 시나리오에서만 유용하다.

실존적 및 보편적 수량화

조건부 테스트는 개별 튜플에서 선택과 조인을 수행하는 데 가장 일반적으로 사용된다. 그러나 추가적인 베타 노드 유형을 구현함으로써, 레테 네트워크는 정량화를 수행할 수 있다. 실존적 정량화는 작동 메모리에 적어도 하나의 일치하는 WME의 존재에 대한 시험을 포함한다. 보편적 정량화에는 작동 메모리의 전체 WME 세트가 주어진 조건을 만족하는지 시험하는 것이 포함된다. 범용 정량화의 변동은 일련의 WME에서 도출된 특정 수의 WME가 주어진 기준을 충족하는지 시험할 수 있다. 이는 정확한 수 또는 최소 일치 항목 수에 대한 테스트의 관점에서 볼 수 있다.

Rete 엔진에서는 정량화가 보편적으로 구현되지 않으며, 이를 지원하는 곳에는 몇 가지 변형이 존재한다. 부정이라고 일컬어지는 실존적 정량화의 변형은 보편적으로는 아니지만 광범위하게 지지되고 있으며, 정량적 문서에 기술되어 있다. 실존적으로 부정된 조건과 접속사에는 일치하는 WME 또는 WME 집합의 존재하지 않는지를 테스트하는 특수 베타 노드의 사용이 포함된다. 이 노드는 일치하는 항목이 없을 때만 WME 목록을 전파한다. 부정의 정확한 실행은 다양하다. 하나의 접근방식에서, 노드는 왼쪽 입력에서 수신하는 각 WME 목록에 대해 간단한 카운트를 유지한다. 카운트는 오른쪽 입력에서 받은 WME와 일치하는 항목 수를 지정한다. 노드는 카운트가 0인 WME 목록만 전파한다. 또 다른 접근방식에서, 노드는 왼쪽 입력으로부터 수신된 각 WME 목록에 추가 메모리를 유지한다. 이러한 기억은 베타 메모리의 한 형태로, 각 매칭에 대한 WME 목록을 올바른 입력에 저장한다. WME 목록에 해당 메모리에 WME 목록이 없으면 네트워크로 전파된다. 이 접근법에서 부정 노드는 일반적으로 추가 베타 메모리에 출력을 저장하는 대신 추가 베타 노드를 직접 활성화한다. 부정 노드는 '실패로서의 부정'의 형태를 제공한다.

작업 메모리가 변경되면 이전에 WME가 없는 것과 일치했던 WME 목록이 이제 새로 주장된 WME와 일치할 수 있다. 이 경우, 전파된 WME 목록과 그것의 모든 확장 사본은 베타 메모리로부터 네트워크 아래로 더 멀리 떨어져야 한다. 위에서 설명한 두 번째 접근방식은 종종 WME 목록 제거를 위한 효율적인 메커니즘을 지원하기 위해 사용된다. WME 목록이 제거되면 해당 생산 인스턴스가 비활성화되어 의제에서 제거된다.

실존 계량화는 두 개의 부정 베타 노드를 결합하여 수행할 수 있다. 이는 이중 부정의 의미론(예: "만약 일치하는 WME가 없다면...")을 나타낸다. 이것은 여러 생산 시스템에 의해 취해지는 일반적인 접근법이다.

메모리 인덱싱

Rete 알고리즘은 작동 메모리를 인덱싱하는 특정한 접근방식을 요구하지 않는다. 그러나 대부분의 현대적인 생산 시스템은 지수화 메커니즘을 제공한다. 어떤 경우에는 베타 메모리만 인덱싱되고, 다른 경우에는 인덱싱이 알파 메모리와 베타 메모리에 모두 사용된다. 우수한 인덱싱 전략은 생산 시스템의 전반적인 성능을 결정하는데 중요한 요소로서, 특히 조합 패턴 매칭(즉, 베타 결합 노드의 집중적 사용)이 높은 규칙 세트를 실행할 때, 또는 일부 엔진의 경우 다중 작업 중에 상당한 수의 WME 수축을 수행하는 규칙 세트를 실행할 때 특히 그러하다.일반 매치-액션 사이클 메모리는 해시 테이블의 조합을 이용하여 구현되는 경우가 많으며, 해시 값은 메모리의 전체 내용보다는 WME 목록과 WME의 하위 집합에 조건부 조인을 수행하는 데 사용된다. 이는 결과적으로 레테 네트워크에 의해 수행되는 평가의 수를 현저하게 감소시킨다.

WME 및 WME 목록 제거

WME가 작동 메모리에서 수축될 때, WME가 저장된 모든 알파 메모리에서 제거되어야 한다. 또한 WME를 포함하는 WME 목록은 베타 메모리에서 제거되어야 하며, 이러한 WME 목록에 대한 활성화된 생산 인스턴스는 비활성화되어 의제에서 제거되어야 한다. 트리 기반 및 재매치 기반 제거를 포함하여 몇 가지 구현 차이가 존재한다. 메모리 인덱싱은 일부 경우 제거를 최적화하기 위해 사용될 수 있다.

처리 ORED 조건

규칙 집합에서 프로덕션을 정의할 때 OR 연결 장치를 사용하여 조건을 그룹화할 수 있도록 허용하는 것이 일반적이다. 많은 생산 시스템에서 이것은 다중 ORED 패턴을 포함하는 단일 생산을 복수 생산과 동등한 것으로 해석함으로써 처리된다. 그 결과로 만들어진 Rete 네트워크는, 함께, 단일 생산물을 나타내는 일련의 터미널 노드들을 포함한다. 이 접근방식은 ORED 조건의 어떠한 형태의 단락도 허용하지 않는다. 또한 경우에 따라 동일한 세트의 WME가 여러 개의 내부 생산과 일치하는 의제에 중복 생산 인스턴스가 활성화될 수 있다. 일부 엔진은 이 문제를 처리하기 위해 의제 중복 제거를 제공한다.

도표

다음 도표는 기본적인 레테 지형을 보여주고 있으며, 서로 다른 노드 유형과 메모리 사이의 연관성을 보여준다.

기본 레테를 설명한다.
  • 대부분의 구현은 n-투플 작동 메모리 요소에 대해 첫 번째 수준의 선택을 수행하기 위해 유형 노드를 사용한다. 유형 노드는 전문 선택 노드로 간주할 수 있다. 그들은 서로 다른 튜플 관계 유형을 구별한다.
  • 도표는 부정 접속사 노드와 같은 전문 노드 유형의 사용을 나타내지 않는다. 일부 엔진은 기능성을 확장하고 최적화를 극대화하기 위해 몇 가지 다른 노드 전문화를 구현한다.
  • 그 도표는 레테의 논리적 전망을 제공한다. 구현은 물리적 세부 사항에 따라 다를 수 있다. 특히, 도표는 베타 노드 지점의 머리에서 올바른 활성화를 제공하는 더미 입력을 보여준다. 엔진은 알파 메모리가 올바른 작동을 직접 수행할 수 있도록 하는 어댑터와 같은 다른 접근방식을 구현할 수 있다.
  • 이 다이어그램은 모든 노드 공유 가능성을 설명하지는 않는다.

레테 알고리즘에 대한 보다 상세하고 완전한 설명은 로버트 두렌보스(Robert Doorenbos)의 대형 학습 시스템을 위한 생산 매칭(Production Matching for Large Learning Systems) 2장(아래 링크 참조)을 참조한다.

대안

알파 네트워크

가능한 변화는 차별 네트워크의 각 중간 노드에 추가 메모리를 도입하는 것이다. 이것은 레테의 오버헤드를 증가시키지만, 레테에 규칙이 동적으로 추가되거나 레테에서 제거되어 차별 네트워크의 토폴로지를 동적으로 변화시키는 것을 더 쉽게 하는 상황에서는 이점을 가질 수 있다.

대체 구현은 Doorenbos에 의해 설명된다.[5] 이 경우 차별 네트워크는 일련의 기억과 지수로 대체된다. 인덱스는 해시 테이블을 사용하여 구현할 수 있다. 각 메모리는 단일 조건부 패턴과 일치하는 WME를 보유하고 있으며, 인덱스는 패턴별로 메모리를 참조하는 데 사용된다. 이 접근방식은 WME가 고정 길이 튜플을 나타내고 각 튜플의 길이가 짧을 때만 실용적이다(예: 3-튜플). 또한 이 접근법은 상수 값에 대해 동등성 검사를 수행하는 조건부 패턴에만 적용된다. WME가 Rete에 들어갈 때, 인덱스는 WME 속성과 조건부 패턴이 일치하는 메모리 세트를 찾는 데 사용되며, WME는 이러한 각각의 메모리에 직접 추가된다. 이 구현 자체에는 1입력 노드가 없다. 그러나, 비균등성 시험을 구현하기 위해, Rete는 메모리에 배치되기 전에 WME를 통과하는 추가 1입력 노드 네트워크를 포함할 수 있다. 또는 아래에 설명된 베타 네트워크에서 비균등 시험을 수행할 수 있다.

베타 네트워크

일반적인 변화는 각각의 토큰이 단일 WME를 보유하는 토큰의 링크된 목록을 작성하는 것이다. 이 경우 부분 일치를 위한 WME 목록은 토큰의 링크된 목록으로 표현된다. 이 접근방식은 WME 목록을 한 토큰에서 다른 토큰으로 복사할 필요가 없기 때문에 더 나을 수 있다. 대신 베타 노드는 부분 일치 목록에 가입하려는 WME를 보유하기 위해 새 토큰을 만든 다음 입력 베타 메모리에 저장된 상위 토큰에 연결하기만 하면 된다. 새로운 토큰은 이제 토큰 목록의 헤드를 형성하고 출력 베타 메모리에 저장된다.

베타 노드 프로세스 토큰. 토큰은 메모리 내의 저장 단위를 의미하며 또한 메모리와 노드 사이의 교환 단위를 의미한다. 많은 구현에서 토큰은 단일 WME를 보유하는 데 사용되는 알파 메모리 내에 도입된다. 이 토큰들은 베타 네트워크로 전달된다.

각 베타 노드는 작업을 수행하고 결과적으로 부분 일치를 나타내는 WME 목록을 보유하는 새로운 토큰을 생성할 수 있다. 이러한 확장 토큰은 베타 메모리에 저장되고 이후 베타 노드로 전달된다. 이 경우 베타 노드는 일반적으로 수신된 각 토큰의 기존 WME 목록을 새 토큰으로 복사한 다음 조인 또는 기타 작업을 수행한 결과로 목록에 추가 WME를 추가함으로써 베타 네트워크를 통해 WME 목록을 전달한다. 그런 다음 새 토큰은 출력 메모리에 저장된다.

기타 고려사항

비록 레테 알고리즘에 의해 정의되지는 않았지만, 일부 엔진은 진실 유지에 대한 더 큰 제어를 지원하기 위해 확장된 기능을 제공한다. 예를 들어, 한 생산에 대해 일치하는 것이 발견되면, 이는 새로운 WME를 주장하게 될 수 있으며, 이는 다시 다른 생산에 대한 조건과 일치한다. 이후 작업 메모리가 변경되어 1차 시합을 무효로 만든다면, 이는 2차 시합을 무효로 한 것을 암시하는 것일 수도 있다. 레테 알고리즘은 이러한 논리적 진실 의존성을 자동으로 정의하고 처리하기 위한 어떤 메커니즘도 정의하지 않는다. 그러나 일부 엔진은 진실 의존성이 자동으로 유지될 수 있는 추가적인 기능을 지원한다. 이 경우, 하나의 WME의 철회로 인해 논리적 진실 주장을 유지하기 위해 추가 WME가 자동으로 철회될 수 있다.

Rete 알고리즘은 정당성에 대한 어떤 접근법도 정의하지 않는다. 정당성은 전문가와 의사결정 시스템에서 일반적으로 요구되는 메커니즘을 말하며, 가장 간단한 경우 시스템이 어떤 최종 결론에 도달하기 위해 사용한 내부 결정을 각각 보고한다. 예를 들어, 전문가 시스템은 동물이 크고, 회색이며, 큰 귀와, 줄기와 엄니를 가지고 있다고 보고함으로써 동물이 코끼리라는 결론을 정당화할 수 있다. 일부 엔진은 레테 알고리즘의 구현과 함께 내장된 정당성 시스템을 제공한다.

이 글은 레테 알고리즘의 모든 가능한 변화나 확장에 대한 완전한 설명을 제공하지 않는다. 다른 고려사항과 혁신이 존재한다. 예를 들어, 엔진은 프로그래밍 객체, XML 데이터 또는 관계형 데이터 테이블과 같은 특정 데이터 유형과 소스에 패턴 매칭 규칙 처리를 적용하기 위해 Rete 네트워크 내에서 전문화된 지원을 제공할 수 있다. 또 다른 예는 Rete 네트워크에 진입하는 각 WME에 대해 많은 엔진에 의해 제공되는 추가적인 시간 스탬프 설비 및 이러한 시간 스탬프를 갈등 해결 전략과 함께 사용하는 것과 관련된 것이다. 엔진은 엔진과 그 작동 메모리에 프로그래밍 방식으로 접근할 수 있는 방법에 상당한 변화를 보이며, 기본 Rete 모델을 병렬 처리 및 분산 처리 형태를 지원하도록 확장할 수 있다.

최적화 및 성능

레테에 대한 몇 가지 최적화가 학술 문헌에서 확인되고 기술되었다. 그러나 이들 중 몇 가지는 매우 구체적인 시나리오에만 적용되므로 범용 규칙 엔진에는 거의 또는 전혀 적용되지 않는 경우가 많다. 또한 Daniel P가 개발한 TREE와 같은 대체 알고리즘도 있다. Miranker[6] LEAPS 및 설계 시간 회의(Deferencing)추가 성능 개선을 제공할 수 있는 TI)가 공식화되었다.

레테 알고리즘은 기존 사실에서 새로운 사실을 계산하거나, 어떤 결론에 도달하기 위해 사실을 필터링하고 폐기하기 위해 전방 체인과 "회의"를 사용하는 시나리오에 적합하다. 그것은 또한 팩트 튜플 사이에서 많은 수의 조인을 수행해야 하는 사실에 대한 높은 조합 평가를 수행하기 위한 상당히 효율적인 메커니즘으로 이용된다. 의사결정 나무의 사용이나 순차적 엔진의 구현과 같은 규칙 평가 수행에 대한 다른 접근법이 단순한 시나리오에 더 적합할 수 있으며 가능한 대안으로 고려해야 한다.

Rete의 성능도 크게 (네트워크 토폴로지와 무관하게) 구현 선택의 문제인데, 그 중 하나(해시 테이블의 사용)가 주요한 개선으로 이어진다. 웹에서 이용할 수 있는 대부분의 성능 벤치마크와 비교는 어떤 식으로든 편향되어 있다. 빈번한 편향과 불공평한 유형의 비교만을 언급하는 것: 1) 매너와 왈츠의 예와 같은 장난감 문제의 사용; 그러한 예들은 구현의 특정 특성을 추정하는 데 유용하지만, 그것들은 복잡한 용도에 실제 성능을 반영하지 않을 수 있다; 2) 오래된 구현의 사용, 예를 들어 의 참조. 다음 두 섹션(Rete II 및 Rete-NT)은 일부 상용 제품을 완전히 구식 버전의 CLIP와 비교하며, 상용 제품이 CLIP보다 더 빠른 크기 주문일 수 있다고 주장한다. 이는 CLIP 6.30(Rete II와 같은 해시 테이블의 도입)이 사용된 버전보다 더 빠른 크기 주문이라는 사실을 잊고 있다. 비교용(CLIPS 6.04)

변형

레테 2세

1980년대에 찰스 구디레테 2라는 이름의 레테 알고리즘의 후계자를 개발했다.[7] 원래의 레테(공영 도메인)와는 달리 이 알고리즘은 공개되지 않았다. Rete II는 더 복잡한 문제(규모의[8] 순서까지)에 대해 더 나은 성능을 주장하며, C/++ 구현인 CLIP/R2와 1998년 자바 구현인 OPSJ에서 공식적으로 구현된다. Rete II는 KnowledgeBased Systems Corporation[9] 벤치마크에서 알 수 있듯이 더욱 복잡한 문제에서 약 100-1배 향상된 성능을 제공한다.

Rete II는 두 가지 개선 영역으로 특징지어질 수 있다; Rete 네트워크의 일반적 성과와 관련된 특정 최적화(더 큰 데이터 집합으로 성능을 높이기 위해 해시 메모리를 사용하는 것 포함), 그리고 Rete 네트워크 상단에서 실행되도록 맞춤화된 후방 체인 알고리즘의 포함. 역방향 체인만으로도 Rete와 관련된 벤치마크의 가장 극단적인 변화를 설명할 수 있다. 레테 2세 Rete II는 이전에 Fair Isaac이라고 불렸던 FICO의 상용 제품 어드바이저에서 구현되었다.

제스(최소한 버전 5.0 이상)도 레테 네트워크 상단에 상용 후진 체인 알고리즘을 추가하지만, 부분적으로 완전한 사양이 공개되지 않기 때문에 레테 II를 완전히 구현한다고는 말할 수 없다.

레테III

2000년대 초, Rete III 엔진은 FICO 엔지니어들과 협력하여 Charles Gudy에 의해 개발되었다. Rete-NT가 아닌 Rete III 알고리즘은 Rete II의 FICO 상표로 FICO Advisor 엔진의 일부로 구현된다. 기본적으로 어드바이저 엔진은 다른 FICO 제품에 접근할 수 있기 때문에 어드바이저 엔진에 접근할 수 있는 API를 갖춘 레테 II 엔진이다.[11]

레테-NT

2010년, 구디는 새로운 세대의 레테 알고리즘을 개발했다. InfoWorld 벤치마크에서 알고리즘은 원래 Rete 알고리즘보다 500배, 이전 알고리즘인 Rete II보다 10배 빠른 것으로 간주되었다.[12] 이 알고리즘은 현재 구디가 투자자와 전략고문으로 가입한 회사인 스파클링 로직(SMARTS)에 스마트S 제품의 추론엔진으로 라이선스된다.[13][14]

레터OO

Rete가 1차 주문 논리(기본적으로 if-then-else 문장의 경우)를 지원하는 것을 목표로 하고 있다는 점을 감안, Rete-OO는[15] 불확실성(결정을 내릴 정보가 누락되거나 부정확한 경우)을 지원하는 규칙 기반의 시스템을 제공하는 것을 목표로 한다. 저자들의 제안에 따르면 '위험 그때 경보'라는 규칙은 '위험의 확률을 감안할 때 경보음이 들릴 확률은 어느 정도 있을 것' 또는 '위험이 클수록 경보음이 커야 한다'와 같은 것으로 개선된다. 이를 위해 퍼지 논리베이시안 네트워크와 같은 확률론적 논리를 지원하도록 드롤스 언어(이미 레테 알고리즘을 구현하고 있음)를 확장한다.

참고 항목

참조

  1. ^ Charles Fordy: Rete: 많은 패턴/많은 객체 패턴 일치 문제를 위한 빠른 알고리즘. 인: 인공지능, 제19권, 페이지 17–37, 1982.
  2. ^ 캐롤 앤 마티뇽의 "레테 알고리즘 디미스티화! 1부"
  3. ^ Ian Wright; James Marshall. "The Execution Kernel of RC++: RETE* A Faster Rete with TREAT as a Special Case" (PDF). Archived from the original (PDF) on 2004-07-25. Retrieved 2013-09-13.
  4. ^ Anurag Acharya; Milind Tambe (1993). "Collection Oriented Match" (PDF). Proceedings of the second international conference on Information and knowledge management - CIKM '93. CIKM '93 Proceedings of the second international conference on Information and knowledge management. pp. 516–526. doi:10.1145/170088.170411. ISBN 0897916263. S2CID 5159932. Archived from the original (PDF) on 2012-03-18.
  5. ^ Carnegie Mellon University 컴퓨터 과학 학교 SCS 기술 보고서 모음의 대형 학습 시스템 생산 매칭
  6. ^ http://dl.acm.org/citation.cfm?id=39946 "TREATE: AI 생산 시스템을 위한 새롭고 효율적인 매치 알고리즘"
  7. ^ 프로덕션 시스템 기술의 RETE2
  8. ^ 생산 시스템 기술의 CLIP/R2 벤치마킹
  9. ^ KBSC
  10. ^ http://dmblog.fico.com/2005/09/what_is_rete_ii.html
  11. ^ http://dmblog.fico.com/2005/09/what_is_rete_ii.html
  12. ^ Owen, James (2010-09-20). "World's fastest rules engine Business rule management systems". InfoWorld. Retrieved 2012-04-07.
  13. ^ "It's Official, Dr. Charles Forgy Joins Sparkling Logic as Strategic Advisor". PR.com. 2011-10-31. Retrieved 2012-04-07.
  14. ^ "Dr. Charles Forgy, PhD". www.sparklinglogic.com. Retrieved 2012-04-07.
  15. ^ Sottara, Davide; Mello, Paola; Proctor, Mark (2010). "A Configurable Rete-OO Engine for Reasoning with Different Types of Imperfect Information". IEEE Transactions on Knowledge and Data Engineering. 22 (11): 1535–1548. doi:10.1109/TKDE.2010.125. S2CID 18895309. Archived from the original (PDF) on 2022-01-10. Retrieved 2022-01-10.

외부 링크