생성 시스템 (Production System)

 

인공지능 원론 : 유석인, 교학사, 1988, Page 27~56

 

1. 생성 시스템 (production system)

     (1) 8-퍼즐 문제

     (2) 기본 프로시쥬어 (basic procedure)

     (3) 제어 (control)

     (4) 제어방법의 예

     (5) 문제 표현 방법

     (6) 문제 표현의 예

     (7) 후향 및 양방향 생성 시스템

2. 특별한 생성 시스템

     (1) 가환 생성 시스템 (commutative production system)

     (2) 가분해 생성 시스템 (decomposable production system)

3. 결론

연습문제

 

 

대부분의 인공지능 시스템들은 자료 (data), 규칙 (operation), 제어 (control) 라는 세 가지 계산요소들을 다소 엄격히 구별하고 있다. 즉 이들이 적절하게 묘사되어졌다면 우리는 전반적인 제어 방법 (control strategy) 아래서 뚜렷이 정의된 규칙들에 의해 운용되어지는 전체 데이터베이스 (global database) 라 불리울 수 있는 한 중심체를 쉽게 명시할 수 있다. 이 장에서는 인공지능 시스템을 구축하기 위한 적절하고 중추적인 역할을 하는 데이터베이스, 규칙, 그리고 제어요소들로 구성되어지는 시스템에 관해 설명한다.

1. 생성 시스템 (production system)

생성 시스템으로 알려진 일반적인 체계화된 시스템들은 위에서 지적한 요소들을 명확히 구분하고 있어서 여러 인공지능 시스템 운용의 본질성을 취하고 있다. 인공지능 생성 시스템의 주요 구성 요소들로는 전체 데이터베이스, 생성규칙들로 이루어진 집합 그리고 제어 시스템이다.

전체 데이터베이스 (global database) 는 인공지능 생성 시스템에서 사용되는 중심 데이터 구조로서, 적용에 따라 간단할 수도 매우 복잡할 수도 있다 (여기서 언급하는 전체 데이터베이스라는 용어는 데이터베이스 시스템들에서 사용되는 데이터베이스와는 구별되어져야만 한다).

생성규칙 (production rule) 은 전체 데이터베이스에 적용되는데 각 규칙은 이 규칙이 적용되어지는 특정 전체 데이터베이스를 묘사하는 전제조건 (precondition) 을 가진다. 만일 어떠한 전체 데이터베이스에 특정 규칙의 전제조건이 만족된다면 이 규칙이 적용되어 전체 데이터베이스가 변화되어진다. 제어 시스템 (control system) 이란, 어떤 데이터베이스에 대해서 적용가능한 한 개 이상의 여러 규칙들 가운데 어느 규칙의 적용이 바람직한지를 결정하고 선택하여 적용하는 것으로 이러한 과정은 종결조건 (termination condition) 을 만족시키는 전체 데이터베이스가 유도되어질 때까지 반복 수행된다.

이러한 생성 시스템 구조와 계층적으로 구조화된 프로그램을 사용하는 전통적인 계산 시스템 간에는 여러 차이점이 있다. 전체 데이터베이스는 각각의 규칙들에 대해 적용 가능성이 타진될 수 있다. 즉, 전체 데이터베이스의 일부가 어느 한 규칙에 대해서만 특별히 적용가능한 것만은 아니다. 또한 규칙은 다른 규칙을 호출 (call) 하지 않으며, 규칙들간의 통신은 전체 데이터베이스를 통해서만 가능하다. 생성 시스템의 이러한 특성들은 많은 양의 지식을 요하는 거대한 인공지능 시스템의 개발과 부합된다. 인공지능의 응용 시스템으로 계층적으로 구조화된 프로그램을 사용하는 기존의 시스템을 사용할 경우, 커다란 난점 중의 하나는 지식 베이스 (knowledge base) 에 대한 변경이 이와 연관된 기존의 프로그램과 데이터 구조, 부 프로그램 (subroutine) 에 대한 광범한 수정을 필요로 하게 한다는 점이다. 이에 반해 생성 시스템은 훨씬 단위적으로 구성되어져서, 지식 베이스의 변경, 제어 시스템의 변경, 규칙들의 변경 등이 비교적 독립적으로 이루어질 수 있다.

생성 시스템의 다양한 종류는 이것이 사용하는 제어 시스템 종류와, 규칙, 데이터 베이스의 속성들 그리고 이것들이 특정문제에 적용되어지는 방식에 의해 나누어진다.

인공지능 생성 시스템에 대한 예로써, 간단한 퍼즐 (puzzle) 문제를 해결하는 방법을 살펴 보기로 하자.

(1) 8-퍼즐 문제

여러 인공지능 응용 시스템들은 일련의 동작들을 요구하게 된다. 로보트의 동작 조정과 자동프로그래밍이 이러한 예들이다 (이 두 가지 문제는 6 장에서 자세히 언급됨). 이런 종류의 간단하고 낯익은 문제로써 기본적인 개념을 잘 나타내는 8-퍼즐 문제가 있다. 8-퍼즐 문제는 3 행과 3 열로 이루어진 (3 × 3) 틀에 이동이 가능한 8 개의 숫자 타일들로 구성되어 간다. 틀 내의 한부분은 항상 비어 있어서 (공백 타일이라고 부름) 인접된 숫자 타일을 이 빈 부분으로 옮길 수 있다 (바꾸어 말하면 공백 타일과 인저비된 어느 숫자 타일과의 자리교환이 가능하다). 이와 같은 퍼즐은 그림 1 에서 두 가지 배열 형태로 주어져 있다. 초기 배열형태를 목표 배열형태로 변환시키기 위한 문제의 해결책은, 타일 6 을 아래로 내리고 타일 8 을 아래로 내리며 그 다음에 타일 2 를 오른쪽으로 이동시키고, 그다음에 타일 1 을 위로 옮기며, 마지막으로 타일 8 을 왼쪽으로 옮김에 의해 이루어진다.

2

8

3

 

1

2

3

1

6

4

⇒

8

 

4

7

 

5

 

7

6

5

초기

 

목표

그림 1  8-퍼즐에 대한 초기 및 목표 배열형태

이 문제를 생성 시스템을 사용해서 해결하기 위해 전체 데이터베이스와 규칙들 그리고 제어방법을 명시해야 한다. 어떤 주어진 문제 설명을 생성 시스템의 이러한 세 가지 요소로써 전환하는 것을 인공지능에서 표현문제 (representation problem) 라 흔히 부른다. 문제를 표현하는 데는 여러 방법이 있을 수 있다. 그러나 좋은 표현방법을 설정하는 것은 실제 문제에 인공지능기법을 적용하는 데 생각되어야만 하는 중요한 작업 중의 하나이다.

8-퍼즐을 포함하는 특정부류 문제들에 대해서는, 이 세 가지 요소들과 대응되는 문제의 요소들을 쉽게 유도할 수 있다. 이들 요소란 문제 상태 (state), 이동 (move) 그리고 목표 (goal) 이다. 8-퍼즐 문제에서 각 타일들의 배열된 전체 형태가 문제상태이다.

이러한 모든 가능한 배열형태들로 이루어진 집합은 이 문제의 문제공간 (problem space) 이 된다. 관심이 되는 대부분의 문제들이 매우 큰 문제공간을 가지고 있다. 그러나 8-퍼즐 문제는 비교적 작은 문제공간을 가진다 (단지 362,880 ( = 9! ) 개의 상태가 존재함 : 이 공간은 각각 9!/2 상태들의 공간인 두 개의 겹치지 않는 부공간 (subspace) 으로 분할되어 질 수 있다.

일단 문제상태들이 개념적으로 확인되면 이들을 컴퓨터 표현으로 구성해야 한다. 이 표현은 생성 시스템의 전체 데이터베이스로 이용되며, 8-퍼즐에서는 3 × 3 행렬로 주어질 수 있다. 초기 전체 데이터베이스는 초기문제상태에 대한 이러한 표현이다.상태를 표현하기 위해서는 문자열 (string), 벡터 (vector), 집합 (set), 트리 (tree), 리스트 (list) 등 어떠한 데이터 구조도 사용될 수 있다. 8-퍼즐에서처럼, 데이터 구조의 형태가 해결하고자 하는 문제의 외형과 매우 유사한 경우도 있다.

이동 (move) 은 한 문제상태에서 다른 문제상태로 변형시키는데, 8-퍼즐의 경우는 빈 공간 (공백 타일) 을 상, 하, 좌, 우의 네 가지 이동을 갖는 것으로 해석된다. 이들 이동들은 주어진 상태표현 상에서 운용되는 생성규칙들로 적절히 정형화되어진다. 생성규칙들 각각이 상태표현에 적용가능하기 위해서 이 만족해야만 하는 전제조건을 가지고 있다. 따라서 빈 공간을 위로 옮기라는 규칙에 대한 전제조건은 빈 공간이 문제상태에서 가장 윗줄에 있어서는 안 된다는 요구조건에서 유도되어진다.

8-퍼즐 문제에서는 하나의 특정한 문제상태 (목표상태) 를 명시하게 된다. 어떤 문제에서는 여러 개의 목표상태들을 명시하고 이들 가운데 하나를 해결하는 것을 목표로 하는 경우도 있다. 좀더 일반화하여 상태에 관해 참/거짓의 조건을 목표조건 (goal condition) (종결조건 (termination condition) 이라고도 함) 으로 명시할 수 있다. 그러면 문제 목표란, 이 종결조건을 만족하는 어떠한 상태에 이르는 것이 된다. 이러한 종결조건은 암시적으로 목표상태들로 이루어지는 집합을 정의하게 된다. 이제까지 설명한 상태, 이동 그리고 목표라는 개념에 의해 문제 해결의 정의를 초기상태에서 목표상태로 변환시키는 일련의 이동을 유도하는 것이라 할 수 있다.

제어 시스템은 목표상태표현이 유도될 때까지 상태표현에 규칙들을 계속 적용하며 동시에 적용되어온 규칙들을 유지하고 있음으로 해서 나중에 수행 종결이 이루어진 후 문제 해결에 이르기까지의 적용되어온 규칙순서를 알게끔 한다.

어떤 문제에 대해서는 해결에 이른 결과가 여분의 어떤 제약조건을 가져야만 하는 경우도 있다. 예를 들어, 8-퍼즐 문제에서 이용횟수를 최소화하는 해결책을 원할 수도 있다. 일반적으로 각 이동에는 이동 적용에 대한 비용 (cost) 이 주어지며, 문제 해결경로로서 최소비용의 해결경로를 요구하는 문제도 있다 (여기에 대한 자세한 설명은 제 4 장에서 언급됨).

(2) 기본 프로시쥬어 (basic procedure)

8-퍼즐과 같은 문제를 해결하는 기본적인 생성 시스템 알고리즘은 다음과 같이 표현될 수 있다.

(3) 제어 (control)

위의 프로시쥬어는 단계 4 에서 적용할 규칙을 어떻게 선택할 것인지에 대해 명확히 언급되어 있지 않다. 생성 시스템에서 제어방법의 형성이란 규칙을 선택하고 동시에 수행과정에서 여태까지 적요되어온 일련의 규칙과 이것들에 의해 유도된 데이터베이스를 유지함을 말한다. 대부분의 인공지능 응용에 있어, 제어방법을 위한 정보는 충분한 것이 아니어서 위의 프로시쥬어에서 단계 4 를 매번 수행할 때, 여러 규칙들 가운데 어느 규칙이 가장 적절한 규칙인가를 완벽히 결정하지 못한다. 그러므로 인공지능 생성 시스템의 수행과정은 종결조건을 만족하는 데이터베이스를 유도하는 일련의 규칙들이 발견될 때까지 규칙을 적용해가는 탐색과정 (search process) 이라 할 수 있다.

제어방법은 크게 두 가지 종류로 분류된다 : 과정 회복 불가능한 (irrevocable) 제어방법과 과정 회복 가능한 (tentative) 제어방법을 들 수가 있다. 과정 회복 불가능한 제어방법에서는, 적용할 규칙이 일단 선택되어 적용이 되어 버리면 나중에 이 상황으로 다시 올 수 없다. 과정 회복 가능한 제어방법에서는, 규칙이 선택되어 (무작위이거나 어떤 이유로 인해서나 간에) 적용이 되어도 나중에 이 상황으로 다시 되돌아와서 다른 규칙의 적용이 가능하다.

과정 회복 가능한 제어방법은 두 가지 형태의 역행 (backtracking) 방법과 그래프 탐색 (graph search) 방법이 있다. 역행방법에서는 한 규칙이 선택될 때 역행점 (backt racking point) 이 설정된다. 그래서 차후 계산에서 해결책 유도의 어려움이 발견되면 이 역행점으로 계산상태를 되돌려 다른 규칙을 적용함에 의해 과정을 진행시킨다. 그래프 탐색방법에서는 여러 개의 규칙들에 의한 효과를 동시에 추적할 수 있도록 되어 있으며 이들이 다루어지는 제약에 따라 여러 구조의 그래프들과 그래프 탐색방법이 있게 된다.

(4) 제어방법의 예

    ① 과정 회복 불가능 (irrevocable) 한 제어

과정 회복 불가능한 제어방법은 탐색에 의한 문제를 해결하려는 생성 시스템에는 부적합한 것으로 보일 수도 있다. 예를 들어 퍼즐 문제를 해결하는 데는 시행착오적 (trial-and-error) 방법이 적격일 수 있다. 또한 생성 시스템의 제어방법이 각 상태표현에 적용할 규칙을 아주 완벽히 선택할 만큼 충분한 지식을 제공받는다면, 퍼즐 문제는 이미 해결되어져 있다 해도 무방하다 할 수도 있다. 그러나 이러한 주장은 어떤 상태에서 목표상태로 어떻게 수행이 진행되어야 하는가에 대한 명확히 나타난 국부적 (local) 지식과 위에서 말한 완전한 해결의 암시된 전체 지식과의 차이를 인식하지 못한데서 비롯된다. 확실한 국부적 지식의 사용이 가능하다면 과정 회복 불가능한 생성 시스템은 이것을 사용해서 해결의 명확한 전체 지식을 형성할 수 있게 된다.

전체 해결을 형성하기 위해 국부적 지식을 이용하는 가장 흔한 예의 하나로 함수의 극대값을 구하는 언덕-오르기 (hill-climbing) 과정을 들 수 있다. 수행과정의 어느 지점에서도 가장 가파른 각도의 방향으로 수행이 진행되게 된다. 언덕-오르기 과정이 과정 회복 불가능한 생성 시스템에 직접 적용되기 위해서는 단지 전체 데이터베이스에 어떤 실수값 함수만 설정하면 된다. 제어방법은 규칙을 선택하는데 이 함수를 사용한다. 즉 함수의 값을 가장 크게 증가시켜 주는 데이터베이스를 생성하는 적용가능한 규칙이 선택 (회복 불가능하게) 된다. 여기서 언덕-오르기 함수는 종결조건을 만족하는 데이터베이스에 대해 극대값을 갖는 것이어야 한다.

언덕-오르기 과정을 8-퍼즐 문제에 적용하고자 할 때, 상태표현의 함수로 이 상태와 목표상태를 비교해서 놓인 위치가 일치하지 않는 타일의 갯수에 음수기호 (-) 를 붙인 것으로 정할 수 있다. 예를 들어, 그림 2 의 초기상태에서 함수값은 -4 이고 목표상태에서는 0 이 되며, 그외 어떠한 상태에 대해서도 이 함수값을 쉽게 계산할 수 있다.

그림 2  8-퍼즐 문제에서의 상태들에 대한 함수값

초기상태로부터 다음 단계에서 가장 증가된 값을 얻기 위해서는 공백 타일을 위로 이동시킴에 의해 이루어진다. 그림 2 에서 이러한 과정 반복이 목표상태에 이를 때까지 (이 때는 함수값이 최고값이 된다) 계속된다. 그림에서 보듯이 어떤 단계에서는 함수값이 증가되지 않았다. 적용가능한 어떠한 규칙도 함수값을 증가시키지 않을 경우에는 함수값을 감소시키지 않는 규칙을 선택한다. 만일 이러한 규칙이 없다면 언덕-오르기 과정은 멈추게 된다.

그림 2 의 8-퍼즐 문제에서 보듯이, 언덕-오르기 제어방법의 사용은 목표상태에 이르는 경로를 구하게 한다. 그러나 일반적으로 언덕-오르기 함수들은 다수의 국부적 극대값을 가질 수 있으므로 언덕-오르기 과정이 실패로 멈추는 수도 있다. 예를 들어 목표상태와 초기상태가 다음과 같다고 가정하자.

이 경우에 초기상태에 어떠한 규칙이 적용되어도 언덕-오르기 함수값은 감소된다. 이러한 현상은 초기상태의 함수값이 국부적 극대값 (전체의 극대값 아님) 을 가지고 있음을 의미한다.

언덕-오르기 과정이 실패할 수도 있는 또 다른 이유가 있다. 함수값이 평원 (plateau) 혹은 산등성이 (ridge) 에 도착했을 때이다. 이러한 난점은 더 효과적인 언덕-오르기 함수, 예를 들어, 단 하나의 전체 극대값만 가지며 평원이 존재하지 않도록 하는 함수를 고안해 낸다면 해결될 수 있다. 인공지능에 관계되는 문제들에서 쉽게 계산될 수 있는 함수들을 대개 위에서 언급한 몇 가지 난점들을 가지고 있다. 그러므로 과정 회복 불가능한 생성 시스템에서 규칙 선택을 결정하기 위해 언덕-오르기 방법의 사용은 아주 제한된 문제에 한하게 된다.

그러나 비록 제어방법에 의해서 각 단계에서 항상 가장 유망한 규칙이 선택되기는 불가능할지라도 과정 회복 불가능한 제어방법이 적절한 경우가 있다. 부적절한 규칙으로 판명된 규칙을 적용해 버렸다고 해서 차후 적절한 규칙들이 적용되는데 방해를 주지 않는다면, 과정 회복 불가능한 규칙 적용을 하는데 아무런 (과다한 규칙 적용이 아닌) 위험 부담이 없다. 이러한 가능성의 예는 차후 제시된다.

    ② 역행 (backtracking)

많은 종류의 문제에서 부적절한 규칙이 적용되면 성공적인 종결이 안되거나 또는 상당한 지연을 가져오게 된다. 이러한 경우에는 규칙 적용을 시도해 봐서 나중에 이 규칙 적용이 적절한 것이 아니었다고 판명되면 원래 위치에 되돌아와서 다른 규칙을 재시도해 볼 수 있도록 하는 제어방법이 필요하다.

역행방법은 과정 회복 가능한 제어방법의 한 종류로써, 어떤 규칙이 선택되어 이 규칙이 해결점에 이르지 못하면 지금까지의 시행단계를 무시하고 다시 이 지점으로 되돌아와서 다른 규칙을 선택하여 시도하게 된다. 역행방법은 규칙 선택을 위해 정보를 제공받는 양에 관계없이 이용될 수 있다. 만일 아무런 정보도 제공받지 않을 경우 규칙 선택은 무작위 (random) 로 이루어진다. 그러나 결국에는 합당한 규칙이 선택될 때까지 제어가 역행을 반복하게 될 것이다. 만일 적절한 규칙 선택에 도움을 줄 수 있는 정보를 제공받은 제어는 훨씬 적은 역행이 이루어진다. 따라서 전체 수행과정은 더 효율적이 된다.

한 가지 예로써, 역행하여 규칙이 선택되는 우선순위가 공백 타일이 좌로 이동, 위로 이동, 우로 이동, 아래로 이동하는 순서에 따르는 그림 3 의 8-퍼즐 문제에 대해 살펴 보자. 역행이 일어나는 상태는 다음의 세 가지에 의한다 : (a) 이 상태에서 초기상태로의 경로 상에 이미 이 상태가 나타난 적이 있는 경우, (b) 목표상태에 도달하기 전에 적용되어온 규칙갯수가 임의의 정한 숫자 (이것을 역행과정의 깊이 한계라 함) 를 넘는 순간, (c) 더 이상 적용할 규칙이 없을 때이다. 그림 3 에서 역행방법이 8-퍼즐에 어떻게 적용되는지를 묘사하기 위해 일련의 과정 회복 가능한 규칙 선택과 역행을 보여 주고 있다. 여기서 각 상태표현은 생성 시스템에 의해 유도 되어온 상태표현의 순서를 정하기 위해 원 내에 숫자가 적혀 있다. 이 그림에서는 해결까지 이르는 동안의 전 탐색과정을 묘사하지 않았다 (너무나 광범위함). 그러나 그림에서 보듯이 깊이 한계 6 까지의 가능한 경로가 탐색된 경우, 결국에는 해결점에 이르게 된다. 그러나 깊이 한계가 너무 낮게 정해지면 해결점은 유도하지 못하는 경우도 있다.

역행 방법은 가장 유망한 이동을 위해 도움을 주는 정보를 가지는 경우에 더 효율적이다. 만일 이러한 정보가 상당히 신뢰할만 하다면 항상 적절한 규칙 선택 가능성이 높아져 역행할 필요가 적어지게 된다. 예를 들어 8-퍼즐 문제에서, 규칙 선택을 위한 수단으로 언덕-오르기 함수를 사용할 수 있다. 과정 회복 불가능한 제어에서는 국부 극대값에 봉착하는 수도 있지만, 역행 제어에서는 역행에 의해 다시 다른 경로를 추적해 갈 수 있다.

그림 3  8-퍼즐 문제에 적용된 역행 제어방법

    ③ 그래프 탐색

그래프, 특히 트리 (tree) 는 일련의 규칙 적용 효과를 추적함에 있어 매우 유용한 구조이다. 이 구조들에 대해서는 제 4 장에서 상세히 다루게 되며 여기서는 이 구조들의 이용에 대한 간단한 예를 보여 준다.

그림 1 에 나타난 8-퍼즐 문제에 그래프 탐색 제어방법이 이용된다고 하자. 이 방법에 의해 수행과정 중에 적용되어온 여러 규칙들과 이 때 유도된 데이터베이스들은 탐색 트리 (search tree) 라 불리는 구조에 의해 추정될 수 있다. 이러한 트리의 예가 그림 4 에 보여진다. 트리의 제일 꼭대기 노드 (node) 는 초기상태를 나타내고 있으며, 각 적용가능한 규칙에 대응되게 한 상태에서 적용했을 때 유도되는 다음 상태로 아크 (arc) 가 주어진다. 그래프 탐색 제어방법은 종결조건을 만족하는 데이터베이스가 생성될 때까지 트리를 확장한다.

그림 4 는 각 상태표현에서 적용가능한 모든 규칙들이 적용된 것을 보여준다. 이러한 식의 노드 확장은 트리가 아주 빨리 커지게 되어 상당히 비효율적인 것이 된다. 그러나 좀더 지적인 제어방법에 의해서 목표 노드에 집중적으로 탐색이 가해지도록 하는 특정지식의 이용은 탐색 트리의 폭을 좁게 만든다. 제 4 장에서는 이러한 탐색 트리가 유도되게 하는 여러 방법들에 대해 다루게 된다.

이러한 그래프 구조를 그래프 탐색 제어방법에서만 이용하고 있다고는 하나, 과정 회복 불가능한 제어방법도 탐색 트리의 단 하나의 경로만 따르는 것이라 할 수 있다 (이런 간단한 제어 방법이 가끔 유용할 수 있음을 이미 보였음).

그러나 역행방법은 전체 탐색 트리 구조를 유지하지 않으며, 필요할 경우에만 경로 수정이 가해지고 단지 현재 수행 중인 경로 (초기상태에서 현재상태까지의 경로 : 이 경로는 언제든지 수정이 가능함) 만을 유지한다.

그림 4  8-퍼즐 문제에 대한 탐색 트리

(5) 문제 표현 방법

효율적인 문제 풀이는 효율적인 제어방법뿐만 아니라 문제상태, 규칙, 종결조건 등이 어떻게 표현되어지는가에도 영향을 받는다. 어떤 문제 표현은 그 문제의 해결에 필요한 노력에 매우 중대한 영향을 미친다. 분명히 작은 상태공간을 지닌 표현이 바람직하다. 외면상으로는 어려운 문제인 것같지만 적절히 표현한다면 매우 작은 상태공간을 지닌 문제가 되는 예가 많다. 흔히 어떤 규칙은 제거가능하고 또 어떤 규칙들은 서로 결합하여질 수 있다는 사실을 인식할 수 있다면 주어진 상태공간이 축소될 수도 있다. 또한 이러한 간단한 변형이 이루어질 수 없는 경우라 하더라도, 문제를 완전히 재구성함으로써 (예를 들어, 상태라는 개념 자체를 변경시킴) 보다 작은 상태공간을 이루게 할 수 있는 경우도 있다.

처음에 문제를 표현하고 이 표현을 향상된 표현으로 전환시켜가는 과정에 대해 따라야하는 분명한 기준은 아직 정해져 있지 않다. 문제 표현에 있어서의 바람직한 전환은 아마도 주어진 표현으로 문제를 해결하려는 노력에서 얻어지는 경험에 좌우된다 할 수 있다. 이러한 경험은 예를 들어 대칭성 또는 연속적으로 자주 적용되는 일련의 규칙들이 매크로 (macro) 규칙 형성 등을 인식함에 의해 개념들의 단순화를 이루게 한다. 예를 들어 8-퍼즐 문제의 처음 표현은 다음과 같은 32 개의 규칙을 명시할지도 모른다 : 1 번 타일을 왼쪽으로 이동, 1 번 타일을 오른쪽으로 이동, 1 번 타일을 위로 이동, 1 번 타일을 아래로 이동, 2 번 타일을 왼쪽으로 이동 등이다. 물론 이들 규칙들 중의 대부분은 어떠한 주어진 상태표현에 결코 적용되지 않는다. 그러므로 이러한 사실이 인식된다면 좀더 나은 표현방식으로 (예를 들어 공백 타일 (빈 공간) 의 이동) 전환될 수 있다.

이제 두 가지 문제 예를 통해서 생성 시스템에 의한 문제 풀이를 위해 문제 표현이 어떻게 이루어지는지 살펴보자.

(6) 문제 표현의 예

여러 다양한 문제들이 생성 시스템에 의한 풀이를 위해 설정될 수 있다. 아래의 예에서 보일 문제 표현 기법이 반드시 그 문제 해결의 유일한 방법은 아니므로 더 나은 대안을 생각해 볼 수도 있다.

    ① 판매사원 방문 문제 (traveling salesman problem)

어떤 판매사원이 그림 5 의 지도에 나타난 5 개 도시를 각각 방문해야 한다고 하자. 모든 도시들 사이에는 도로가 있으며 거리값이 주어져 있다. 문제는 판매사원이 A 도시에서 출발하여 각 도시를 한번만 방문하고 A 로 되돌아오는 최단거리의 경로를 구하는 것이다.

그림 5  판매사원 방문문제에 대한 지도

이 문제에 대한 표현 설정은 다음과 같이 명시된다.

전체 데이터베이스는 방문한 도시들의 리스트가 된다. 따라서 초기 전체 데이터베이스는 리스트 (A) 로 표현된다. 모든 도시를 거치고 나서 A 가 다시 나오는 경우를 제외하고는 한 도시가 다시 나오는 리스트는 허용하지 않는다.

규칙들은 다음과 같다 : (a) A 도시로 가라, (b) B 도시로 가라, (c) C 도시로 가라, (d) D 도시로 가라, (e) E 도시로 가라.

규칙은 현재의 데이터베이스 (리스트 표현) 에 적용되어 유도될 다음의 데이터베이스가 앞서 명시한 리스트의 제약조건을 위배하지 않아야 한다. 만일 위배한다면 이 규칙은 현재의 데이터베이스에 적용가능하지 않다. 따라서 "A 도시로 가라" 의 규칙은 모든 도시의 이름을 가지지 않는 리스트에는 적용불가능하다.

A 로 시작하고 A 로 끝나며 그 사이에 나머지 모든 도시의 이름을 가지는 어떠한 전체 데이터베이스도 종결조건을 만족한다. 그림 5 에 나타난 거리를 사용하여 어떠한 방문 경로의 총 거리를 계산할 수 있으며 최적의 해결경로란 최소거리를 가지는 방문경로라 하겠다.

그림 6 은 이 문제를 해결하는데 그래프 탐색 제어방법을 사용했을 때 유도되는 탐색트리의 일부를 보여주는데, 각 아크 옆의 숫자는 여태까지의 경로거리와 이 아크에 해당되는 규칙의 거리를 더한 증가된 거리값을 나타낸다.

그림 6  판매사원 방문문제에 대한 탐색 트리

    ② 구문 해석 문제 (syntax analysis problem)

심볼들로 이루어진 어떤 일련의 나열된 형태 (문자열) 가 언어의 문장이 될 수 있는지 (즉, 문법에 의해 유도가능한 문장인가를) 를 알아보는 문제를 생성 시스템에 의해 해결되도록 할 수 있다. 문자열이 문장인가 하는 결정은 파싱 (parsing) 문제이며 파싱 문제도 생성 시스템에 의해 해결 가능하다.

언어를 정의하는 간단한 문맥과 상관없는 문법 (context-free grammar) 이 주어져 있다고 가정한다. 예로써 문법이 다음과 같은 종결 심볼들을 지니고 있고,

또한 다음과 같은 비종결 심볼들을 지니고 있다고 하자.

문법은 다음과 같은 규칙들로 정의된다.

이 문법은 너무 간단하여 대부분의 영어문장을 해석하는 데에 유용하진 않지만 다소 현실적인 것으로 확장될 수 있다.

다음과 같은 문자열이 언어의 문장인가를 결정하려 한다 하자.

이 문제에 대한 표현 설정은 다음과 같이 명시된다.

전체 데이터베이스는 문자열로 이루어진다. 초기 전체 데이터베이스는 검사하기 위해 처음에 주어진 문자열이 된다.

생성규칙들은 문법의 재표기규칙 (rewrite rule), 들로부터 유도된다. 문법규칙에 대해서 전체 데이터베이스에 나타나는 규칙 왼편은 규칙 오른편으로 대치가 가능하다. 예를 들어 문법규칙 DNP VP → S 는 DNPㆍVP 를 지니고 있는 어떠한 전체 데이터베이스도 이것이 S 로 대치된 것으로 변경시키는 데에 사용된다. 전체 데이터베이스가 해당 문법규칙의 왼편을 갖고 있지 않으면 이 규칙은 적용될 수 없다.

단일 기호 S 로 구성된 데이터베이스만이 종결조건을 만족한다.

이 문제에 대한 탐색 트리의 일부는 그림 7 에 보여진다. 이 간단한 예에서는 가능한 다른 규칙 적용 순서를 제외하고는 트리의 가지 (branch) 가 매우 적다.

그림 7  구문 해석 문제에 대한 탐색 트리

(7) 후향 및 양방향 생성 시스템

8-퍼즐 문제를 해결하기 위해 앞서 사용한 생성 시스템은 초기상태에서 목표상태로 전향 (forward) 으로 작업을 수행했다고 말할 수 있다. 그러므로 이러한 생성 시스템을 전향 생성 시스템이라 부른다. 또한 목표상태에서 시작하여 후진이동 (backward move) 을 행하여 초기상태에 이르도록 함에 의해서 문제를 해결할 수도 있다. 이러한 방식으로 8-퍼즐 문제를 해결하기 위한 생성 시스템이란 단지 상태들과 목표 상태의 개념을 역으로 생각하고 후진이동에 해당되는 규칙들을 사용하는 것이다.

8-퍼즐 문제의 경우에 후향 생성 시스템의 설정은 목표상태가 명확히 표현되어져 있으므로 간단하다. 목표가 어떤 조건에 의해 표현될 때에도 후향 생성 시스템이 설정될 수 있다. 이러한 목표조건은 흔히 서술논리문 (predicate calculus) 에 의해 표현 가능하다.

전진방향으로 작동하는 생성 시스템과 후향으로 작동하는 생성 시스템 간에 형식적인 차이점은 없다 할지라도 이 두 가지를 명확히 구분짓는 것이 바람직하다. 어떤 문제가 분명한 상태들과 목표상태를 갖고 생성 시스템이 이 상태들을 전체 데이터베이스들로 간주할 때 이 시스템은 전향 생성 시스템이 된다. 이 때 규칙은 상태표현에 적용되어 새로운 상태표현을 생성하는데 이러한 규칙을 F-규칙이라 한다. 만약 목표상태들을 (여기서 목표상태란 규칙의 역적용에 의한 부목표 (subgoal) 상태의 통칭을 의미함) 전체 데이터베이스들로 간주한다면 이 시스템을 후향 생성 시스템이라 한다. 이 때 규칙은 목표상태에 적용되어 부목표상태를 생성하는데 (이 순간은 부목표상태에서 목표상태까지는 적용되어 부목표상태를 생성하는데 (이 순간은 부목표상태에서 목표상태까지는 구해진 것이므로 초기상태에서 현재의 부목표상태까지의 경로만 구하면 된다), 이러한 규칙을 B-규칙이라 한다.

단일의 초기상태와 단일의 목표상태를 지닌 8-퍼즐 문제에서는 전향을 써서 해결하는 것과 후향 해결 간에는 차이가 없으며 계산비용은 양편이 모두 동일하다 할 수 있다. 그러나 어느 한 편이 다른 편보다 더욱 효율적인 경우가 있다. 예를 들어, 목표상태는 다수 개이며 초기상태는 하나인 문제가 있다고 가정해보자. 이 문제를 후향으로 해결하고자 하는 것은 바람직하지 않다 하겠다. 이 경우에는 어느 목표 상태가 초기상태에 가장 가까운가 하는 것은 미리 알지 못하므로 최적의 해결경로를 구하고자 하는 경우에 후향 탐색은 상당한 계산비용이 필요하게 된다. 그러므로 일반적으로, 가장 효율적인 해결 방향의 선정은 상태공간의 구조에 따른다.

문제 해결을 위한 탐색을 전향과 후향으로 동시에 행할 수 있다. 생성 시스템으로 이러한 효과를 얻기 위해서는 전체 데이터베이스는 전향으로 유도되는 상태와 후향으로 유도되는 상태를 동시에 포함하는 상태표현을 가지게 된다. 여기서는 전향으로 유도된 상태에는 F-규칙이 적용되는 한편, 후향으로 유도된 상태에는 B-규칙이 적용되며 문제 해결이 종결되도록 하기 위해 종결조건을 전체 데이터베이스의 두 가지 상태 (전향에 의한 상태와 후향에 의한 상태) 의 비교선택에 의한 적절한 형태로 지정되어야 한다. 제어 시스템은 또한 매 단계마다 F-규칙을 적용할 것인지 또는 B-규칙을 적용할 것인지를 결정해야 한다.

2. 특별한 생성 시스템

(1) 가환 생성 시스템 (commutative production system)

특정 조건하에서는 적용가능한 일련의 규칙들에 대해 이것이 적용되는 순서에 관계없이 언제나 동일한 결과를 얻는 경우가 있다. 이러한 조건이 이루어진다면 생성 시스템은 동등한 해결경로 (규칙들이 적용되는 순서를 무시한 의미에서 동등) 들을 중복해서 불필요하게 탐색하지 않음으로 해서 효율성을 높인다.

그림 8  그래프에서의 동등한 경로들

그림 8 에는 세 개의 규칙 R1, R2, R3 가 SO 라 표시된 데이터베이스에 적용가능하며, 세 개 규칙들 가운데 어느 하나가 적용된 후에도 그 결과로 나타난 데이터베이스에 세 개의 규칙이 모두 다시 적용가능하다. 더우기 그림 8 은 {R1, R2, R3} 의 어떠한 규칙 적용 순서에도 관계없이 SO 데이터베이스에서 동일한 데이터베이스 SG 를 유도해 낸다.

생성 시스템이 어떠한 데이터베이스 D 에 대해서도 다음과 같은 속성을 지닐 때 가환 생성 시스템 (commutative production system) 이라 한다.

그림 8 에서의 규칙 적용은 이러한 가환의 속성을 가지고 있다. 그림 8 의 SG 라 표시된 데이터베이스의 유도에 있어서, 여러 경로들 중에서 분명히 단 하나만을 고려할 필요가 있다. 가환 시스템에 있어서 경로의 중복탐색을 피하는 방법은 매우 중요하다.

가환 시스템이란 어떤 주어진 데이터베이스를 어떤 주어진 조건을 만족하는 데이터베이스로 변환시키는데 적용된 규칙들 전체에 대해 규칙 적용 순서가 바뀌어도 무방하다는 의미는 아니다. 어떤 규칙이 데이터베이스에 적용된 후에 추가적인 규칙 적용이 가능할 수도 있기 때문이다. 초기에 데이터베이스에 적용가능한 규칙들만에 대해 이들 사이의 적용 순서가 바뀌어도 동일한 결과의 데이터베이스가 유도됨을 의미한다. 이 차이점은 중요하다.

가환 생성 시스템은 특별한 속성을 지니는 한 중요한 부류이다. 예를 들어, 이 시스템에서는 위의 정의에 의해 규칙의 적용이 역행되거나 취소될 필요가 없으므로 과정 회복 불가능한 (irrevocable) 제어방법이 항상 사용될 수 있다. 이전의 데이터베이스에 적용가능했던 어떠한 규칙들도 현재의 데이터베이스에 적용가능하므로 규칙들을 다른 순서로 적용하기 위한 기법을 따로 제공할 필요는 없다. 부적절한 규칙이 적용되면 단지 종결을 연기시킬 뿐이며 결코 종결이 안되는 것은 아니다. 종결 후에 유도되어온 규칙 적용 순서에서 무관한 규칙들이 존재할 수 있는데 이것들은 제거되어도 관계없다. 가환 시스템은 나중에 더욱 상세히 검토될 것이다.

어떠한 생성 시스템도 가환 생성 시스템으로 전환시킬 수 있는 간단한 방법이 있다. 생성 시스템에 의한 해결을 위해 문제가 표현되어 있다 가정하자. 문제 표현 방법에서 언급했듯이, 아마도 이 생성 시스템은 전체 데이터베이스와 이것을 수정하는 규칙들 그리고 전체 데이터베이스의 탐색 트리를 유도할 그래프 탐색 제어방법을 가지게 될 것이다. 이제 또다른 생성 시스템으로, 앞의 생성 시스템의 전체 탐색 트리를 전체 데이터베이스로 가지는 생성 시스템을 생각해 보자. 이 새로운 시스템의 규칙들은 앞의 생성 시스템에서의 제어방법 수행에 의해 탐색 트리가 수정될 수 있는 다양한 방식들을 나타낸다. 그러므로 분명히 어느 단계에서 적용가능한 이 새로운 시스템의 어떠한 규칙도 그 후에는 계속 적용가능한 상태로 남게 된다. 앞의 시스템의 제어방법에 의존했던 과정 회복 가능한 제어방법을 새로운 시스템에서는 분명히 가환 속성에 의해 구현하고 있다 하겠다. 이러한 전환은 전체 데이터베이스와 규칙들을 더욱 복잡하게 하나 제어방법이 보다 간단해 진다 (과정 회복 불가능한 제어방법).

(2) 가분해 생성 시스템 (decomposable production system)

가환의 성질이 규칙 적용에 어떤 자유를 부여하는 유일한 조건은 아니다. 예를 들어, 초기 데이터베이스가 (C, B, Z) 이고 생성규칙들이 다음과 같은 재표기규칙에 근거를 두는 시스템을 고려해 보자.

그리고 종결조건은 데이터베이스가 M 들만으로 구성되어진 상태를 말한다.

그래프 탐색 제어방법은 M 들만을 갖는 데이터베이스를 유도함에 있어서 여러 동등한 경로들을 탐색할지도 모른다. 그림 9 에서는 이러한 두 가지 경로가 나타나 있다. 중복된 경로들을 제어방법이 이들 모두를 탐색할 경우도 있으므로 비효율적이지만, 이보다 더 나쁜 것은 성공적으로 종결되지 않는 경로를 탐색하는 과정에 있어서의 많은 유용한 작업들을 결국에는 낭비해 버리는 것이다 (그림 9 에서 트리의 오른쪽 가지에 있는 규칙 적용들의 대부분은 해결에 필요한 것이다).

그림 9  재표기 문제에 대한 해결 순서

중복된 경로들에 대한 이러한 불필요한 탐색을 피하는 한 가지 방법은 초기 데이터베이스를 독립적으로 처리될 수 있는 개별요소들로 분해하는 것이다. 본 예에서, 초기 데이터베이스는 C, B, Z 의 세 개의 요소 (component) 로 분해될 수 있으며 생성 규칙들은 이들 각각에 독립적으로 적용될 수 있다 (가능하다면 각각이 병행적으로). 이러한 적용의 결과들도 각 구성요소 데이터베이스가 M 들만을 갖게 될 때까지 분해, 적용의 과정을 반복하게 된다.

인공지능 생성 시스템은 이러한 방식으로 분해가능한 전체 데이터베이스를 갖고 있는 경우가 많다. 이러한 데이터베이스는 원자들이 모여서 형성된 분자에 비유될 수 있다. 만일 규칙 적용가능조건이 개별 원자에게만 구한된다고 하며 규칙 적용의 결과로 해당 원자가 어떤 새로운 분자 (이 분자도 마찬가지로 원자들로 이루어짐) 로 대치된다면, 그 분자를 원자들로 다시 분해해서 각각에 대해 독립적으로 규칙을 적용할 수 있다. 각 규칙 적용은 규칙 적용의 전제조건을 성립시키기 위해 사용된 전체 데이터베이스의 요소에만 영향을 미친다. 각 수성요소에 대한 규칙 적용들은 실질적으로 병행하여 적용가능하므로 이들 규칙 적용 순서는 중요하지 않다.

데이터베이스를 분해하면 또한 종결조건을 분해할 수 있어야 한다. 다시 말하면 각 구성요소들을 개별적으로 수행한다면, 이 구성요소들의 종결조건들이 표현되어질 수 있어야 하며 이들이 모여 전체 종결조건을 형성하게 된다. 전체 종결조건이 형성되는 흔한 경우는 각 요소 데이터베이스들에 대한 종결조건을 표현 (아마도 서술 논리문에 의한 표현) 의 논리곱으로 나타나는 경우이다. 달리 언급되지 않는다면 항상 이 경우를 가정하기로 한다.

전체 데이터베이스와 종결조건을 분해할 수 있는 생성 시스템을 가분해 생성 시스템 (decomposable production system) 이라 한다. 이러한 가분해 생성 시스템의 기본 프로시쥬어는 다음과 같다.

SPLIT 의 제어방법은 단계 5 에서 요소 데이터베이스 D* 를 선택하야 하고, 단계 7 에서 적용할 규칙 R 을 선택해야 한다. 단계 3 을 만족시키기 위해서는 어느 형태의 제어방법으로도 결국에는 {Di} 내의 모든 요소들을 선택해야 한다. 그러나 선택된 D* 에 대해서는 적용가능한 규칙들 가운데 하나만 선택한다.

요소 데이터베이스들의 병행처리가 가능할지라도 어떤 순서에 의해 수행되는 제어방법에 대해 살펴보자. 요소들의 이러한 수행순서를 정하는 데는 두 가지 방법이 있다 : (a) 요소들이 생성됨과 동시에 언제나 이들은 고정된 순서에 의해 수행될 순서가 정해진다. (b) 수행 중에 요소들은 재조정이 가능하다. (a) 의 경우에는, 각 구성요소는 다음의 요소가 수행되기 전에 수행을 완전히 완료한다. 물론 생성규칙이 요소에 적용되어 생성되는 데이터베이스는 또한 분해될지도 모르며, 이때 이 분해된 요소 데이터베이스들은 고정된 순서에 의해 순환적으로 처리된다. 일반적으로 역행방법에서의 규칙을 선택하는 요령은 이 구성 데이터베이스들의 이러한 고정 순서 처리방법과 관계되어 이용된다.

가분해 생성 시스템의 더욱 융통성이 있는 제어방법은 수행과정에서 요소 데이터베이스들의 순서를 동적 (dynamic) 으로 재조정하는 것이다. AND/OR 그래프 구조는 이러한 제어방법하의 생성 시스템의 수행과정을 표현하는 데 유용하다. 그림 10 은 앞에서 언급한 재표기문제의 AND/OR 그래프를 나타낸다. 평범한 보통의 그래프와 마찬가지로 AND/OR 그래프도 전체 데이터베이스로 명칭이 붙여진 노드들로 구성된다. 분해가능한 데이터베이스로 명칭이 붙여진 노드는 후계 노드들과 연결되는데 이 후계 노드들은 각기 분해된 요소 데이터베이스로 명칭이 붙여진 노드들이다. 이와 같이 분해가능한 부모 노드의 데이터베이스가 종결되기 위해서는 이것의 후계 노드들의 데이터베이스들이 모두 종결되어야 하기 때문에 이 후계 노드들을 AND 노드들이라 한다. 이러한 AND 노드들의 표현은 그림에서 보듯이 반원으로 묶여져 나타낸다.

요소 데이터베이스에는 규칙들이 적용될 수 있다. 이 요소 데이터베이스의 노드는 규칙이 적용된 후에 생성되는 데이터베이스로 명칭이 붙여지는 후계 노드를 갖게 된다. 그러므로 적용가능한 여러 규칙들로 인해 생성되는 여러 후계 노드들을 가질 수 있다. 위의 요소 데이터베이스가 종결되기 위해서는 이것의 후계 노드들 가운데 하나만 종결조건을 만족하면 된다. 그러므로 이러한 후계 노드들을 OR 노드들이라 부른다.

그림 10  재표기문제의 AND/OR 트리

그림 10 에서, 종결조건을 만족하는 요소 데이터베이스들은 해당되는 노드에 모두 이중의 사각형으로 그려져 있는데 이러한 노드들을 종결 노드 (terminal node) 들이라 한다 (그림 10 은 그래프로도 표현이 가능하다. 데이터베이스 (M, M) 이 나타나는 네 개의 노드를 하나로 하고 화살표의 방향들을 수정시키면 그래프가 된다).

이 재표기 문제의 해결경로는 AND/OR 그래프에서의 한 부 그래프 (subgraph) 로 나타내어진다. 이 해결경로는 그림 10 에서 굵은 선으로 표시된 부 그래프이다. 이 부 그래프에서 끝단 노드들은 모두 종결조건을 만족하는 데이터베이스들에 해당된다. AND/OR 그래프를 이용한 해결경로의 유도방법은 제 4 장에서 논의된다.

이제 가분해 생성 시스템이 다음의 몇 가지 예에서 어떻게 적용되는지를 살펴보자.

    1) 화학구조 유도 문제

화합물의 분광사진과 같은 실험적 데이터로부터 이 복잡한 화합물의 구조가 무엇인가하는 것을 결정하는 것은 유기화학에서 중요한 문제이다. DENDRAL 이라 불리는 인공지능 시스템은 이러한 복잡한 화합물의 구조를 결정하기 위해 고안된 시스템이다. DENDRAL 의 중요한 수행부분은 화합물에 대한 화학식이 주어진 상황에서 이 화합물의 가능할 수 있는 형성구조들을 유도해 내는 것이다. 이 가능한 구조들이 유도되는 방법에 대한 상세한 설명은 생략하기로 하며, 단지 간단한 탄화수소에 대해 어떻게 처리하는지를 설명하기로 한다.

가능할 수 있는 구조들을 유도하기 위한 시스템은 생성 시스템으로 간주할 수 있다. 전체 데이터베이스는 부분적으로 구조화된 화합물로서, 생성 시스템은 이 데이터베이스 상에서 수행되어 구조화의 정도를 증가시킨다. 초기에 데이터베이스는 어떠한 화학구조도 표현하지 않으며 단지 화학식만을 갖고 있다. 중간단계에서, 데이터베이스는 화합물의 일부 구조를 표현하게 되며, 과정의 마지막에 데이터베이스는 화합물의 전체구조에 대한 표현을 갖게 된다.

이 문제에 있어서 데이터베이스는 부분들로 분해되어 일부는 원래 화학식의 구조가 유도 안 된 일부 화학식이 되게 할 수 있으므로 가분해 생성 시스템을 사용할 수 있다. 여기서 생성규칙들은 구조표현이 안 된 화학식을 부분적인 구조를 제공하는 표현으로 전환시키는 구조 제시 (structure-proposing) 규칙들이다. 종결조건을 만족하는 데이터베이스는 구조화 안 된 화학식을 하나도 가지지 않는 데이터베이스들이 된다.

간단히 구조 제시 규칙이 어떻게 적용되는지 살펴보자. 화학식 C5H12 의 구조를 유도하고자 한다 가정하자. 여기서 논하는 생성 시스템은 이 화학식에 대한 가능할 수 있는 구조들을 제시하게 된다. 그러나 제시된 이 구조들이 모두 실질적으로 가능한 것이 아니다. 실제적인 DENDRAL 시스템은 분광사진 외에 다른 화학지식을 사용해서 이들 유도된 구조들의 상당한 구조들을 제시한다. 초기 데이터베이스는 단지 화학식 C5H12 이다. 이 경우에 있어 다음과 같은 부분적 구조들을 제시한다.

위의 부분적 구조에서, 수직선 (| |) 내에 있는 화학식들은 구조표현이 아직 안된 것들이다. 이러한 부분들은 데이터베이스에서 구조화된 부분으로부터 분해되어 이들 각각에 대해 독립적으로 관련되는 구조 제시 규칙들을 적용할 수 있다. 예를 들어 규칙은 화학식 - |C2H5| 에 대해 다음과 같은 구조를 제시한다.

 

C5H12 문제에 대한 부분적인 AND/OR 트리는 그림 11 과 같다. 각 해결경로의 부분 트리는 가능한 구조에 해당된다. 굵은 선으로 표시된 해결경로는 다음과 같은 구조에 해당된다.

그림 11  화학 구조 문제에 대한 AND/OR 트리

    2) 적분 문제

기호 적분 문제에서 입력으로 와 같은 어떠한 부정적분을 취하여 출력으로 1/9 sin 3x - 1/3x cos x 와 같은 해답을 자동적으로 유도하기를 원한다. 이를 위해서는 아래와 같은 간단한 적분공식들에 대한 도표가 필요하다.

    

기호 적분 문제는 주어진 적분을 도표 내에 나타나는 표현들의 형태로 전환하는 생성 시스템에 의해 해결될 수 있다.

생성규칙들은 부분적분과 적분의 분해 그리고 대수 및 삼각함수 치환과 같은 다른 변환법칙에 기초한다. 부분적분에 따른 생성규칙은 를 로 변환시킨다. 원래 적분될 함수의 어느 부분이 u 이고 어느 부분이 dv 에 해당할 것인지에 선택을 가지는 경우에는 각각에 대해 개별적으로 규칙을 적용할 수 있다.

적분의 분해규칙은 어떤 합의 함수에 대한 적분을 각 요소에 대한 적분들의 합으로 변환시키며, 또한 인수분해하는 규칙은 와 같은 표현을 로 변환시킨다. 그외 다른 규칙들은 그림 12 에 제시된 과정에 기초한다.

대수치환

    (예)  

삼각함수 치환

    (예)  

분수

    (예)  

제곱

    (예)  

그림 12  적분규칙의 예

적분들의 합의 형태를 포함하는 표현은 개별적분들로 분산될 수 있는데, 이들 각각은 독립적으로 처리될 수 있으므로 이 생성 시스템은 가분해 생성 시스템이 된다.

그림 13  적분 문제의 AND/OR 트리

이 여러 규칙들의 유용성은 적분함수의 형태에 절대적으로 좌우된다. SAINT (slagle, 1963) 라는 기호적분 시스템에서는 적분함수들을 이들이 지니고 있는 여러 특성들에 따라 분류하였다. 각 분류된 적분함수들에 대해서는 이들에 적용가능한 규칙들을 경험적인 체험에 의해 선택하게 된다.

그림 13 에서는 가분해 생성 시스템에 의해 탐색된 한 AND/OR 트리를 보여 준다. 이 문제는 다음과 같은 식을 구하는 식이다.

        

트리의 노드들은 적분될 수식을 나타내고 있다. 적분도표에 있는 기초적인 적분에 해당하는 수식은 종결조건을 만족하므로 이중의 사각형으로 표시된다. 여기서 굵은 선은 이 문제에 대한 해결경로의 트리를 가리키는데 이 해결 트리와 적분도 표로부터 해답을 구하면 다음과 같게 된다.

    

3. 결론

이제까지 인공지능 생성 시스템의 두 가지 형태 즉, 일반 형태인 PRODUCTION 프로시쥬어와 분해형태인 SPLIT 프로시쥬어에 대해 논하였다. 문제가 생성 시스템에 의한 해결을 위해 표현되는 방식에 따라 이 생성 시스템들은 전향 또는 후향으로 수행이 된다. 또한 이들은 과정 회복가능한, 또는 과정 회복 불가능한 (irrevocable) 제어방법에 의해 제어된다. 이와같은 차이들에 기초한 생성 시스템의 분류는 다양한 인공지능 시스템과 일관성있는 개념 정립에 큰 도움을 준다.

여기서 논의되는 차이점이란 단지 다른 종류의 인공지능 시스템들 간의 차이점을 의미하는 것이지 해결해야 할 문제들 사이에서의 차이점은 아니다. 동일한 문제가 전적으로 다른 종류의 시스템들에 의해 제각기 표현되고 해결되는 예를 나중에 보게 될 것이다.

앞으로 문제 표현에 대한 여러 가지 예가 제시될 것이다. 어떤 주어진 문제에 대한 전체 데이터베이스, 규칙들, 그리고 종결조건 등의 설정은 다소 기술을 요하며 예에 의해 가장 잘 이해될 수 있다. 지금까지 사용된 대부분의 문제 예는 퍼즐과 같은 초보적인 문제였으므로 과연 생성 시스템이 실제로 지능적인 시스템의 기초를 형성하기에 충분한지에 의문을 가질 수도 있을 것이다. 나중에 생성 시스템의 광범한 활용성을 보여주는 더욱 현실적이고 복잡한 문제들을 다루게 될 것이다.

효율적인 인공지능 시스템이 되기 위해서는 문제영역에 대한 지식을 필요로 한다. 이러한 지식은 생성 시스템의 데이터베이스, 규칙들, 그리고 제어부분에 대응하여 세 가지로 분류된다. 전체 데이터베이스에 나타난 문제에 대한 지식을 흔히 선언적 지식 (declarative knowledge) 이라 부른다. 예를 들어 지적인 정보 추출 시스템에서 선언적 지식은 특정사실들로 이루어진 중심된 데이터베이스를 포함하게 된다. 규칙들로 표현되는 문제에 대한 지식을 흔히 프로시쥬어에 관한 지식 (procedural knowledge) 라 부른다. 지적인 정보 추출 시스템에서 프로시쥬어에 관한 지식은 선언적 지식을 다루기 위한 일반적인 정보를 포함하게 된다. 제어방법에 의해 표현되어지는 문제에 대한 지식을 흔히 제어 지식 (control knowledge) 이라 부른다. 제어 지식은 문제 해결의 전체과정을 제어하기 위해 사용하는 여러가지 수행과정, 전략, 구조 등에 관한 지식을 포함한다.

이 책에서 관심있게 다루는 중심적인 주제는 인공지능 생성 시스템의 운용을 위해 문제에 대한 지식을 어떻게 선언적 지식, 프로시쥬어에 의한 지식, 그리고 제어 지식으로 적절히 분류하여 표현할 것인가 하는 것이다.

연습문제

1. 다음과 같은 선교사와 식인종 문제를 해결하기 위한 생성 시스템의 전체 데이터베이스, 규칙들, 그리고 종결조건을 명시하여라 :
세 명의 선교사와 세 명의 식인종이 강을 건너고자 한다. 강에는 배가 하나 있는데 이 배에는 한 명 내지 두 명만 탈 수 있다. 이들이 이 배를 이용해서 강을 건너는데 한가지 제약은 강의 양편에는 항상 식인종 숫자가 선교사 숫자를 넘지 않아야 한다는 것이다 (넘으면 잡아 먹힌다). 이러한 제약조건하에서 선교사들이 배를 어떻게 이용해서 여섯 명 모두를 건네게 할 수 있겠는가? 전체 데이터베이스 상에서 운용될 수 있을 언덕-오르기 함수를 명시해보아라. 이 함수를 과정 회복 불가능한 제어방법과 역행제어방법이 이 문제 해결을 위해 어떻게 사용하는지 묘사하여라.

2. 다음과 같은 물 항아리 문제를 해결하기 위한 생성 시스템의 전체 데이터베이스와 규칙들, 그리고 종결조건을 명시하여라 :
물이 가득 채워진 5 리터짜리 항아리와 물이 하나도 없는 2 리터짜리 항아리가 있다. 2 리터짜리 항아리를 정확히 1 리터의 물로 채워지도록 하기 위해서는 어떠한 과정을 밟아야 하나? 여기서 제약은 물을 한 항아리에서 다른 항아리로 붓는 것이 가능하며 또한 한 항아리에서의 물이 필요한 만큼 없어지게 할 수 있다.

3. 상호교환 가능한 어떤 생성 시스템의 규칙 R 이 데이터베이스 D 에 적용되어 데이터베이스 D' 를 유도한다고 가정하자. 만일 규칙 R 의 역이 존재한다면 D' 에 적용가능한 규칙들로 이루어진 집합은 D 에 적용가능한 규칙들로 이루어진 집합과 동일함을 보여라.

4. 어떤 시스템이 정수들로 구성된 집합을 전체 데이터베이스로 가진다. 이 전체 데이터베이스는 내포된 어느 두 개의 정수를 곱하여 생기는 값 (정수) 을 첨가함에 의해 확장이 된다. 이러한 생성 시스템은 상호 교환가능한 생성 시스템임을 보여라.

5. 10 진수를 2 진수로 변환하기 위한 생성 시스템을 묘사하여라.
10 진수 141 을 예로서 위 시스템의 수행과정을 보여라.

6. 다음의 주장에 대해 비판하여 보아라 :
문제상태들 사이에 중복된 경로가 있을 때 역행제어방법 (또는 깊이-우선 그래프 탐색) 은 이 모든 경로에 대한 탐색을 피하고자 하는 경향이 있으므로 이 제어방법이 사용되어져야 한다.

7. 프로시쥬어 SPLIT 수행하는 역행제어방법을 사용하는 경우, 단계 5 에서의 선택은 역행점에 해당되는가? 만일 단계 5 가 역행점이 아니라면 역행방법하에서의 프로시쥬어 SPLIT 와 역행 방법하에서의 프로시쥬어 PRODUCTION 과는 어떠한 차이가 있는가?