고속 Factored POMDP 알고리즘과 이의 대화 관리에의 응용

Abstract

주어진 대화 상황에서 최적의 시스템 발화를 결정하는 대화 관리 시스템은 대화형 인터페이스의가장 중요한 요소중 하나이다. 불가피한 음성인식에서의 오류로 인해 현재의 대화 상태를 정확히 알 수 없기 때문에 대화 관리에서의 의사 결정 문제는 매우 어렵다고 알려져 있다. 대화 관리에서의 의사 결정 문제를 Factored partially observable Markov decision process (POMDP)로 나타내면 음성 인식 오류를 고려하여 대화의 의사 결정 문제를 자연스럽게 모델링 할 수 있으나, 이 문제를 푸는 기존의 Point-based 근사 알고리즘들은 수집된 Belief point들에 따라 정책의 품질이 크게 영향을 받게 된다. 또한 대화의 동적인 상태 요소간 독립관계 역시 기존 알고리즘으로는 충분히 활용하지 못했다. 이 논문에서는 먼저, Factored POMDP를 위한 고속 알고리즘을 제안한다. 이는 Algebraic Decision Diagram (ADD)를 사용하여 Heuristic Search Value Iteration (HSVI) 알고리즘을 Factored POMDP를 다룰 수 있게 확장한 것으로, 제안한 방법이 벤치 마크 테스트 문제들에서 다른 알고리즘들 보다 월등히 빠른 계산속도를 가짐을 보였다. 그리고 실제 데이터를 사용하여 POMDP 대화 모델을 구축하였다. 우리는 Bigram이나 Levin 같은 전통적인 MDP 대화 모델에 음성 인식 오류를 추가하여 POMDP 대화 모델로 확장하였고 구축된 POMDP 모델에서 얻어진 최적 정책이 MDP 모델에서 얻어진 최적 정책보다 좋은 품질을 가짐을 실험으로 보일 수 있었다.