6.9 프레임 문제와 형식 공리 체계의 구조적 제약

1. 프레임 문제의 정의

프레임 문제(Frame Problem)는 매카시(John McCarthy)와 헤이스(Patrick Hayes)가 1969년 “Some Philosophical Problems from the Standpoint of Artificial Intelligence“에서 제기한 인공지능의 근본적 문제이다.

프레임 문제의 핵심: 행동(Action)이 세계(World)에 미치는 효과(Effect)를 형식적으로 기술할 때, 행동에 의해 변하지 않�� 측면(비변화, Non-Effect)을 어떻게 효율적으로 기술할 것��가?

형식적으로: 행동 $A$ 가 수행되었을 때, $A$ 에 의해 변화하는 명제들만을 명시하고, 나머지 모든 명제는 변하지 않는다는 것을 어떻게 형식적으로 표현할 것인가?

2. 프레임 문제의 기술적 구조

2.1 상황 계산법(Situation Calculus)에서의 프레임 문제

매카시의 상황 계산법에서 세계�� 상태는 상황(Situation)으로 모델링되며, 행동에 의해 한 상황에서 다른 상황��로 전이한다.

유창 사실(Fluent): 상황에 따라 변할 수 있는 명제. 예: $\text{On}(\text{BlockA}, \text{Table}, s)$ (“상황 $s$ 에서 블록 A가 테이블 위에 있다”).

행동 효과의 명시: 행동 $\text{Move}(\text{BlockA}, \text{BlockB})$ 의 효과를 명시한다:

$\text{On}(\text{BlockA}, \text{BlockB}, \text{Result}(\text{Move}(\text{BlockA}, \text{BlockB}), s))$

프레임 공리(Frame Axiom)의 필요성

행동이 변화시키지 않는 유창 사실을 명시하는 프레임 공리가 필요하다. 예: “블록 A를 블록 B 위로 이동하는 행동은 블록 C의 위치를 변화시키지 않는다.”

$\text{On}(\text{BlockC}, x, s) \wedge x \neq \text{BlockA} \rightarrow \text{On}(\text{BlockC}, x, \text{Result}(\text{Move}(\text{BlockA}, \text{BlockB}), s))$

2.2 조합적 폭발

$n$ 개의 유창 사실과 $m$ 개의 행동이 있을 때, 프레임 공리의 수는 $O(n \times m)$ 이다. 현실적 환경에서 유창 사실과 행동의 수가 많으면 프레임 공리의 수가 폭발적으로 증가한다. 이것이 프레임 문제의 기술적 핵심이다.

3. 프레임 문제와 불완전성의 관��

3.1 형식 체계의 표현력 한계

프레임 문제는 형식적 공리 체계로 세계의 동적 변화를 완전하고 효율적으로 기술하는 것의 근본적 어려움을 드러낸다. 이 어려움은 불완전성 정리와 직접적으로 동일하지는 않으나, “형식적 기술의 한계“라는 공통 주제에 속한다.

불완전성 정리가 “형식 체계는 모든 산술적 진리를 포착할 수 없다“를 보여주듯, 프레임 문제는 “형식 체계는 세계의 동적 변화를 효율적으로 포착할 수 없다“는 실용적 한계를 드러낸다.

3.2 비단조성(Nonmonotonicity)의 필요성

프레임 문제의 해결에는 비단조 추론(Nonmonotonic Reasoning)이 필요하다. 표준 논리는 단조적(Monotonic)이다—전제가 추가되면 결론이 증가만 한다. 그러나 프레임 문제에서는 “별도의 정보가 없으면 변화하지 않는다“라는 비단조적 가정이 필요하다.

4. 프레임 문제의 해결 시도

4.1 외접(Circumscription, McCarthy 1980)

외접은 비단조 ��론의 형식화로서, “변화하는 유창 사실을 최소화한다“는 원리에 기반한다. 행동에 의해 변화하는 것으로 명시적으로 기술된 유창 사실만 변화하고, 나머지는 변화하지 않는다고 가정한다.

외접은 프레임 문제에 대한 우아한 이론적 해결을 제공하지만, 추론의 계산 복잡도가 높아 실용적 적용에 한계가 있다(일반적으로 $\Pi_2^P$ -완전).

4.2 후자 상태 공리(Successor State Axiom, Reiter 1991)

라이터(Raymond Reiter)�� 효과 공리(Effect Axiom)로부터 프레임 공리를 자동으로 도출하는 후자 상태 공리를 제안하였다:

$\text{Fluent}(x, \text{do}(a, s)) \leftrightarrow \gamma^+_{\text{Fluent}}(x, a, s) \vee (\text{Fluent}(x, s) \wedge \neg\gamma^-_{\text{Fluent}}(x, a, s))$

여기서 $\gamma^+$ 는 유창 사실을 참으로 만드는 조건, $\gamma^-$ 는 거짓으로 만드는 조건이다. 이 공리는 프레임 공리의 조합적 폭발을 해소한다.

STRIPS와 상태 공간 계획

STRIPS(Stanford Research Institute Problem Solver, Fikes & Nilsson, 1971)는 프레임 문제를 실용적으로 우회하는 접근이다. 행동의 전제조건(Precondition), 추가 목록(Add List), 삭제 목록(Delete List)만을 명시하고, 나머지 상태는 변화하지 않는다는 STRIPS 가정(STRIPS Assumption)을 채택한다.

이 가정은 폐쇄 세계 가정(Closed World Assumption)의 동적 버전이며, 형식적으로 완전하지 않으나 실용적으로 효과적이다.

넓은 의미의 프레임 문제

철학적 프레임 문제

데넷(Daniel Dennett, 1984)은 프레임 문제를 기술적 문제를 넘어 인공지능의 근본적 철학적 문제로 확장하였다. 넓은 의미의 프레임 문제: “지능적 체계가 변화하는 환경에서 관련 있는 정보만을 효율적으로 선택하고 처리��는 것이 어떻게 가능한가?”

인간은 이 문제를 암묵적·자동적으로 해결하지만, 이를 형식적으로 기술하고 기계에 구현하는 것은 극도로 어렵다. 이 어려움은 상식 추론의 형식화 난점과 맞닿아 있다.

자격 문제(Qualification Problem)와 파급 문제(Ramification Problem)

프레임 문제의 관련 문제:

자격 문제: 행동의 전제조건을 완전히 열거하는 것의 어려움. “열쇠가 있으면 문을 열 수 있다“의 전제조건에는 “문이 고장 나지 않았다”, “열쇠가 부러지지 않았다”, “중력이 작용한다” 등 무한히 많은 자격 조건이 암묵적으로 포함된다.

파급 문제: 행동의 간접적 효과(파급 효과)를 예측하는 것의 어려움. 블록을 이동��면 블록 위의 다른 블록도 함께 이동하며, 이 연쇄 효과의 완전한 기술이 필요하다.

인공지능에 대한 함의

프레임 문제는 형식 공리 체계에 기반한 AI의 구조적 제약을 가장 직접적으로 드러내는 문제이다. 이 문제는 불완전성 정리의 직접적 귀결은 아니지만, “형식적 기술의 한계“라는 동일한 범주에 속하며, 기호주의 AI의 실용적 한계를 규정하는 핵심 요인이다.

현대 딥러닝 기반 AI는 프레임 문제를 학습에 의해 암묵적으로 우회한다. 신경망이 데이터로부터 환경 변화의 패턴을 학습함으로써, 명시적 프레임 공리 없이도 행동의 효과와 비효과를 처리할 수 있다. 그러나 이 접근의 일반성과 신뢰성에 관한 이론적 보장은 아직 충분하지 않다.