Automatic Story Generation: A Survey of Approaches (1)

1. Automatic Story Generation

SG system 연구는 1960년 대 초기에 시작되었으나 아직까지 (2021년) 사람을 능가할만한 모델은 없다. 또한 창의성이 인간과 비교할 수 없기 때문에 여전히 취약하다.

인간이 어떻게 스토리를 생성하는지 이해해야 컴퓨터에게 스토리 생성 방법을 가르칠 수 있다.

Task

자동화된 스토리 생성(Automatic Story Generation, ASG)은 기준 set을 만족하고 스토리로 볼 수 있는 event나 action sequence를 자동적으로 선택하는 문제이다.

각 스토리는 story world, interactive characters, object가 있으며, events를 통해 독자에게 전달하고자 하는 메세지인 author goal이 있다.

Main Challenge

창의성을 위해서는 이전에 본 것과 다른 이야기를 생성해야 한다.
동시에 story setting도 고려해야 한다.

Story setting
Time, space, story character, character의 desire, desire를 달성하기 위한 plan, character 간의 interaction, desire 사이에서 발생하는 conflict

이 모든 속성을 고려하는 것은 story space를 엄청 크게 만들고, 그 안에서 스토리를 찾아나가는 것은 너무 어렵다.

ASG's Category

본 논문에서는 story generator를 세 가지 카테고리로 분류했다.

1) Structural model
2) Planning-based model
3) Machine learning model

2. Definitions

Story generator들을 살펴보기 전에 기본적인 개념과 정의부터 짚고 넘어가자.

Story

스토리는 엔터테이먼트나 교육과 같은 하나 이상의 목표를 달성하기 위해 생성된 캐릭터 및 이벤트에 대한 설명이다.

Theme

일반적으로 스토리에는 하나 이상의 주제가 있으며, 이는 author가 receiver한테 전달하고자 하는 핵심 아이디어이다.

Event

스토리 이벤트는 특정 시간과 장소에서 발생하며, story world를 하나의 state에서 다른 state로 변환한다.

Plot

각 스토리에는 일련의 이벤트(sequence of event)와 이러한 이벤트에 영향을 미치는 원인인 plot이 있다.

Character & Protagonist

캐릭터는 스토리의 actor나 actor에게 영향을 받는 사람이다.
대부분의 plot과 이벤트, 그리고 이벤트 간의 인과관계에 연결된 캐릭터를 protagonist(주인공)이라고 한다.

Story Space

Story space에는 캐릭터, 설정,소품 뿐만 아니라 narrative space에 물리적, 추상적으로 존재하는 모든 것이 포함된다.

Fabula & Syuzhet

Fabula는 이야기 사건이 연대순으로 일어나는 story world를 의미한다.
Syuzhet은 독자를 고려하여 파블라의 내용을 선택하여 특정 순서로 배열한다.

Discourse

스토리가 표면적 표현으로 조직되는 방식의 구조이다.
+) 담론, 어떤 주제에 대해 체계적으로 논의를 하는 것이다. 말해지거나 글로 쓰여지는 의사소통을 의미한다.

Plot graph

SG 시스템에서 plot space를 모델링할 때 사용되는 표현이다.
스토리를 개별 Plot 포인트로 추상화한 후 각 플롯 포인트는 스토리의 일부 이벤트를 나타낸다.
가능한 이벤트 시퀀스의 공간을 정의하기 위해 방향 비순환 그래프에 플롯 포인트를 배치하여 일부 순서 제약 조건을 플롯 포인트에 할당한다.
또는 함께 발생하지 않는 스토리 포인트를 지정하기 위해 추가적인 분리 제약 조건을 적용한다.

https://thegradient.pub/an-introduction-to-ai-story-generation/

Script

스크립트는 특정 컨텍스트에서 적절한 이벤트 시퀀스를 설명하는 구조이다.
스토리를 일련의 슬롯으로 나타내고 이러한 슬롯을 채울 수 있는 것에 제약을 부과한다.
슬롯 내용은 스크립트의 다른 슬롯 내용의 영향을 받을 수도 있다.

Frame

스토리 프레임은 다양한 스토리 요소를 나타내는데 사용된다.
캐릭터 프레임은 이름, 역할 및 상태와 같은 캐릭터에 대한 특정 정보를 저장한다.
이벤트 프레임은 actor, 장소, 가능한 액션과 같은 이벤트의 속성과 제약을 형식화한다.

Setting

사실적인 모습을 위해서는 스토리의 시간과 장소 등의 부가적인 설정이 추가되어야 한다.

Story structure

스토리 목표를 달성하고 재미있는 스토리를 만들기 위해서는 스토리 플롯이 잘 구성되어야 한다.
스토리를 분석하고 생성하기 위한 많은 스토리 구조 모델이 존재한다.
가장 잘 알려진 스토리 구조는 Freytag's pyramid이다.

https://writers.com/freytags-pyramid

다섯 가지 주요 구성 요소로 나눌 수 있다.

• Exposition: 메인 캐릭터와 설정이 소개된다.
• Rising action: climax로 이어지는 이벤트가 시작한다.
• Climax:스토리의 주요 액션 또는 최고의 긴장감이 발생하는 지점이다.
• Falling action: climax에서 resolution으로 이어지는 일련의 이벤트이다.
• Resolution: 스토리의 주요 문제가 해결되고 스토리가 끝난다.

Freytag's pyramid의 스토리 구조는 다른 유형의 문학과 구별되는 점이며,
스토리 구조는 목표를 달성하는 것 뿐만 아니라 재미를 높이는 것에도 중요하다.

Consistency

스토리의 believability(신빙성)은 이벤트 시퀀스가 독자에게 논리적으로 보이는 일관성에 크게 영향을 받는다.
스토리 일관성에 기여하는 세 가지 요소는 다음과 같다.

• 이벤트 간의 인과 관계 (cause-effect)
• 이벤트와 story world 간의 일치성 (conformity)
• 캐릭터의 성격과 액션 간의 일치 (accordance)

스토리 일관성은 스토리 구조로서 필요한 것이며, 생성된 모든 스토리의 필수 요구 사항이다.

3. Structural Models

인지 과학에서 story grammar 이론은 스토리를 스크립트로 간주한다.
스트립트는 특정 context에서 적절한 일련의 사건을 설명하는 구조이다.
이러한 이론은 실제 세계에서 사건이 일반적으로 틀에 박힌 패턴으로 발생한다는 사실에서 비롯되었다.

식당 컨텍스트) 사람이 식당에서 식사를 한다.
이벤트 1) 식당에 들어간다.
이벤트 2) 테이블에 앉는다.
이벤트 3) 메뉴를 읽는다.
이벤트 4) 음식을 주문한다.
이벤트 5) 음식을 먹는다.
이벤트 6) 돈을 지불한다.
이벤트 7) 식당을 나간다.

이러한 패턴은 스토리 생성을 안내하는 schema로 사용된다.
하지만, 시나리오가 달라짐에 따라 컨텍스트에서도 다른 패턴이 발생할 수 있다.
예를 들어, 식당 컨텍스트에서 테이블에 메뉴가 없는 경우가 있을수도 있고
식당이 패스트푸드인 경우 돈을 지불하는 이벤트가 음식을 먹는 이벤트보다 먼저 등장해야 한다.

이러한 패턴의 다양성은 생성된 스토리의 다양성을 향상시킨다.

스토리 생성 분야에서는 다음과 같이 스키마를 사용한다.
스토리를 주어진 스키마(패턴)에 따라 슬롯으로 나누어, 구조화된 스토리를 자동으로 생성한다.
그런 다음 생성된 스토리 슬롯 간의 상호 효과를 고려하여 유사한 슬롯을 채운다.
이때, 주석이 달린 스토리를 사용하여 유사한 슬롯을 찾을 수 있다.

Vladmir Propp

600개의 러시아 민담을 분석하여, 모든 민담이 function이라고 부르는 31개의 인물 행동으로 구성되어 있다고 주장했다.
이 function은 모든 이야기에 나타나지 않을 수 있지만, 등장하는 function은 엄격한 순서를 따른다.
Propp의 구조는 초기 연구에서 자동 스토리 생성에 널리 사용되었다.

3.1 Graph-based Approaches

스크립트의 가장 간단한 형태는 스토리 그래프를 구축하는 것이다.
1) Design phase: 가능한 모든 스토리 공간을 나타내는 branching story graph를 구성한다.
2) Generation phase: 생성된 스토리를 나타내는 linear path를 찾기 위해 그래프를 탐색한다.

생성된 스토리의 품질은 주로 구성된 그래프의 품질에 따라 달라진다.
또한 path의 길이나 제약을 추가하여 스토리 품질을 향상 시킬 수 있다.

Maranda는 propp의 이야기 구조를 기반으로 설화를 생성할 수 있는 그래프를 개발했다.
특정 시작 노드와 종료 노드가 있는 propp의 function을 포함하는 노드로 구성된다.
주석이 달린 지식 베이스는 노드를 통과하며 노드 function과 일치하는 조각을 검색한다.
검색된 조각이 생성된 스토리에 연결되는 과정을 반복한다.
해당 그래프는 cyclic하기 때문에 무한 반복 과정을 거칠 수 있다.

CHEHERAZADE sysytem은 스크립트 형식으로 topic domain에 대한 인간의 경험을 수집한다.
스크립트를 기반으로 플롯 그래프를 학습하고, 학습된 그래프를 순회하며 스토리를 생성한다.
하지만 해당 그래프는 acyclic하며, 일부 이벤트에 대해 상호 포괄적인 제약 조건을 적용한다.

3.2 Grammar-based Approaches

Lakoff는 Propp의 story structure를 story grammar로 재구성하였다.
Propp의 function을 narrative의 알파벳으로 취급하는 관점에서 스토리를 보고
확장 가능한 rewrite rule을 사용하여 스토리를 생성하는 것이다.

Pemberton은 오래된 프랑스 서사시를 위한 스토리 문법을 제안했으며
이를 기반으로 스토리를 생성하는 프로그램인 GESTER가 구현되었다.

BRUTUS는 스토리 문법을 기반으로 배신 스토리를 생성하는 시스템이으로,
캐릭터, 사건 등 스토리의 모든 요소를 스토리 프레임으로 간주하여 복잡한 스토리를 만들었다.

위 스토리 문법들은 모두 특정 영역에 한정된 전문화된 문법이며, 일반적인 스토리를 위한 문법이 필요했다.

Rumelhart는 일반적인 이야기 문법을 처음으로 제안했고,
단순성을 가진 Thorndyke의 문법이 널리 사용되고 있다.

Story structural 모델의 장점
Story structural 모델은 쉽고 빠른 구현으로 잘 구조화된 스토리를 생성할 수 있다.

Story structural 모델의 단점
하지만, 이야기의 구조에 초점을 맞추기 때문에 의미론적인 부분을 고려하지 못할 수 있다.
스토리 이벤트 간의 논리적 관계와 캐릭터 의도와 행동 간의 논리적 관계를 고려하지 못해 스토리의 일관성과 신뢰도에 부정적인 영향을 미칠 수 있다.
복잡한 논리적 관계를 피하기 위해 주인공은 한 명으로 제한되며 목표가 충돌하는 경우에도 적용할 수 없다.
또한, 제공된 스토리 구조를 만족하는 스토리만 생성할 수 있기 때문에 지식을 수정하여 다른 스토리를 생성하는 것이 어렵다.
마지막으로, over-generation 문제를 겪기도 한다. 스토리가 아닌 텍스트를 생성하고 이야기로 받아들이는 경우이다.

4.Planning-based Model

Story structural 모델의 한계점을 극복하고자 story point 이론이 제안되었다.
해당 이론은 스토리를 최종 목표를 추구하기 위해 인과적으로 연결된 일련의 이벤트로 간주한다.

Cook은 1,852개의 plot fragment에 관한 논문을 출판했다.
각 Plot fragment는 몇 가지 잠재적인 Predecessor와 Successor를 결합하여 완전한 plot을 생성하는 방법에 대한 지침이 포함되어있다.
cook의 접근 방식은 전체 구조보다는 연속적인 plot fragment 사이의 논리적 흐름에 초첨을 맞추는 스토리 포인트 이론을 따른다.

Egeret은 Plotter를 제안했다.
Plotter는 plot fragment와 관련 명령어들로부터 plot들을 생성하는 computational story generator이다.
이때 일관성과 논리성을 개선하기 위해, 각 fragment의 AI planning operator representation을 사용할 것을 제안했다.

실제로 story point 이론은 AI planning 알고리즘을 사용한 ASG에 널리 사용되었다.
일반적으로 AI planning을 이용해 스토리를 생성하는 것은 행동을 추론하는 reasoner에게 초기 state와 goal을 제공하고, 궁극적으로 초기 state를 goal로 이끄는 방식으로 작동한다.

4.1 Goal-Directed Approaches

Goal-directed approaches는 최초의 지능형 story generator였다.

4.1.1 Simulation Approach

Meehan은 TALE-SPIN에서 ASG를 위한 AI를 처음으로 도입했다.
TALE-SPIN은 AI를 활용하여 캐릭터의 needs와 intention을 충족하고자 했다.
world simulation planner를 구축하여 전적으로 캐릭터의 goal에 따라 작동했다.

1) Initial state에서 시작한다.
즉, story world에 대한 설명과 하나 이상의 캐릭터 목표를 설정한다.
2) Reasoner(Inference Engine)을 사용하여 forward chaining 알고리즘을 구현한다.
이를 통해, 각 이벤트가 story world에 미치는 영향을 고려하여 인과적 이벤트 체인을 추론하며 스토리 계획을 생성한다.
3) 캐릭터 goal에 도달할 때까지 반복한다.

이 방식은 스토리 캐릭터에게 분명한 의도를 부여하여 신뢰도를 높인다.
TALE-SPIN은 이솝 우화와 같은 짧고 일관된 이야기를 생성할 수 있다.

TALE-SPIN의 한계점
캐릭터의 Needs를 충족시키기 위해 행동에 초점을 맞추게 되면 절정이나 해결이 없는 흥미롭지 않은 이야기가 생성될 수 있다.
또한, 지식을 구축하기 위해 사용한 소스 스토리를 재조립하여 "좋은" 스토리를 생성하는 경우가 많다.

4.1.2 Global-Schema Approach

작가는 스토리를 쓸 때, 이야기의 skeleton(뼈대)이 되는 일련의 목표를 만들어서 일관되고 흥미진진한 이야기를 쓰는 것을 목표로 한다.
그리고 캐릭터가 이러한 목표를 추구하도록 지시한다.

스토리 구조를 개선하기 위해서, 캐릭터의 목표에서 작가의 목표(global goal)로 초점을 옮겨 프로세스를 시뮬레이션했다.
작가는 스토리 world의 일부가 아니기 때문에 어떤 경쟁에도 위협 받거나 관여하지 않으며 기회로부터 혜택을 받지도 않는다.
따라서, 작가는 독립된 주체로서 특정 인물에게 유리한 입장을 주지 않고 좋은 이야기를 만들어낸다.
또한, 작가의 목표는 이야기의 다른 캐릭터 간의 목표 경쟁이나 갈등을 초래하여 이야기의 재미를 증가시킨다.

Dehn은 저자 목표에 기반한 최초의 스토리 생성 시스템인 AUTHOR를 제안했다.
외부 문서를 사용하여 스토리 초안을 작성하고 최종 전달되기 전에 여러 번 수정하여 인간 작가를 시뮬레이션하는 재구성 동적 메모리 아키텍처를 구현한다.

1) 작가의 목표 set이 입력된다.
2) 세 개의 sub task loop가 시작된다.
2-1) 메모리에서 관련 자료를 찾는다.
2-2) 검색된 자료 중 가장 적절한 부분을 선택하여 뽑아낸다.
2-3) 작가의 목표를 검사하고 수정하여 개념적 재정립이 이루어진다.
3) 작가의 목표을 만족할 때까지 반복한다.

AUTHOR에 의해 생성된 스토리는 일반적으로 캐릭터 목표 기반보다 구조가 잘 짜여져 있고 더 흥미롭다.
그럼에도 불구하고 작가의 목표를 위해 캐릭터가 명확한 의도 없이 행동하는 경우가 있어서 캐릭터의 believability에 부정적 영향을 미친다.

4.1.3 Multi-Agent Approach

잘 구조화되고 일관된 이야기를 생성하기 위해, 연구자들은 캐릭터 목표와 작가 목표를 모두 사용하는 것을 시도했다.
이것은 사실 캐릭터 목표 방식과 유사하다.

Riedl은 잘못 구성된 스토리 생성을 방지하기 위해 스토리 생성 프로세스 전반에 걸쳐 캐릭터의 행동을 안내하는 Automated Story Director를 만들었다.

Virtual Storyteller는 지능형 에이전트를 사용하여 이야기를 생성한다.
캐릭터는 자신의 목표를 달성하기 위해 계획하고, plot 구조에 대한 일반적인 지식을 갖춘 가상 지능형 에이전트가 스토리의 구조(시작, 중간, 해피엔딩)을 유지하도록 캐릭터의 행동을 지시한다.
환경 제어(새로운 캐릭터 도입)와 동기 제어(새로운 캐릭터 목표 도입)를 사용하여 plot을 원하는 방향으로 이끈다.

IPOCL planner인 FABULIST는 두 가지 매커니즘으로 구성되어 있다.
첫번째 매커니즘은 partial order causal-link planner이다.
즉, 작가의 글로벌 목표에 의해 움직이는 캐릭터의 causal action chain을 추론하는 부분이다.
두번째 매커니즘은 독자의 의도 인식 프로세스를 시뮬레이션하여 캐릭터의 신뢰도를 보존하는 것을 목표로 한다.
IPOCL planner는 아주 느리다는 것이 큰 단점이다. 전체 계획을 생성하는데 약 12.3 시간이 걸린다.

그리고 Haslum의 연구와 CPOCL의 연구도 있다.

4.2 Analogy-Based Approaches

Computational analogy는 인간이 유추하는 인지 과정을 기반으로 하는 AI 접근법이다.
소스 도메인과 타겟 도메인 간에 유사성을 식별하고 지식을 전달하며 작동한다.
Analogy를 사용하여 이전에 알려진 유사한 문제에 솔루션을 적용하여 새로운 문제를 해결할 수 있다.
즉, 현재 스토리 world와 유사한 스토리 world의 상태에 대한 지식을 검색하여 스토리 생성 시스템에 적용한다.
이때 유사성 측정법은 시스템마다 다르다.

MINSTREL은 스토리 생성을 위한 최초의 Analogy-Based approaches이다.
MINSTREL은 에피소드 메모리에 scene(case)을 저장한다. (CBR)
만약 메모리에 일치하는 장면이 없다면 TRAMS를 사용하여 새로운 장면을 생성한다.
MINSTREL은 소설의 novelty를 위해서 같은 장면을 두 번 사용하는 것을 피한다.

MEXICA는 글쓰기의 engagement-reflection cognitive account를 기반으로 한다.
각 캐릭터에 대해 MEXICA는 감정적 연결을 기록하기 위해 스토리 world context를 생성한다.