Dialogue management system which determines the system response in a given situation is a one of the important components in the spoken dialogue interface. The decision problem of dialogue management system is known to be very difficult because automatic speech recognition is unreliable and the state of conversation can never be known with certainty. We cast the problem as a factored partially observable Markov decision process (POMDP). POMDP can naturally model dialogue decision problem under speech recognition error but the qualities of policies from conventional point-based approximate algorithms are influenced by sampled belief points. Also, the statistical independence in the state dynamics is not sufficiently exploited in conventional algorithms.
This paper makes two contributions; first, we propose a fast algorithm for factored POMDP. Using Algebraic Decision Diagram (ADD), we extend Heuristic Search Value Iteration (HSVI) to deal with factored representation. In bench mark test problems, our algorithm shows order-of-magnitude speed up.
Second, we construct POMDP user models from real data corpus. Our POMDP user models add speech recognition error probability to conventional MDP user models such as Bigram and Levin model. Policies based on out POMDP models show more robust performance than those from MDP user models.
대화 관리 시스템에서 사용자와 시스템간의 대화의 동적 구조를 통계적 방법으로 모델링 할 때 POMDP가 우수하다는 것은 많은 사람들이 알고 있었으나 최적 정책 계산의 시간, 공간적 복잡도가 매우 높기 때문에 현실 세계의 문제를 다투기 위해서 보다 효율적인 근사 해법 알고리즘이 요구 되었다.
본 연구에서는 데이터로부터 POMDP 대화 관리 모델을 구축하고 빠르게 최적 정책을 얻을 수 있는 알고리즘을 제안한다. POMDP 대화 관리 모델을 구축하고 빠르게 최적 정책을 얻을 수 있는 알고리즘을 제안한다. POMDP문제의 최적 정책을 얻는 것은 계산 복잡도가 매우 높기 때문에 제한적인 Belief state에서만 가치를 계산하는 근사 알고리즘을 많이 사용하고 있다. 이 경우 Belief state를 수집하는 방법이 정책의 품질에 지대한 영향을 미치기 때문에 이를 효율적으로 수집하는 Heuristic Search Value Iteration 알고리즘을 사용하였다. 또 대화 관리의 POMDP문제는 상태의 각 요소간 조건부 독립 성질을 이용하여 여러 개의 상태 변수로 나누는 Factored POMDP로 나타낼 수가 있는데, 이에 대한 고려가 없는 기존 알고리즘에 그대로 적용하면 계산량이 많아진다. 따라서 Algebraic Decision Diagram을 사용하여 변수들의 독립 관계를 최대한 활용 할 수 있게 하여 계산량을 줄였다. 이 경우 데이터의 표현 방식이 달라지므로 Heuristic Search Value Iteration 알고리즘에서 가치 함수의 Upper bound를 구하거나 갱신하기가 까다로워지는데 이것을 결합하는 방법을 제시하였다.
여러 벤치마크 테스트 문제들을 사용하여 제안한 알고리즘을 현재 우수하다고 알려져 있는 알고리즘들과 비교 실험하여 약 40배 이상 빠른 계산속도를 가짐을 보였다. 또 실제 대화 관리자를 구축하기 위해 항공기 여행 예약에 관한 LDC Communicator 데이터를 사용하여 Bigram, Levin 모델에 따라 POMDP 대화 모델을 구성하고 최적 정책을 구하였다. 시뮬레이션 실험에서 MDP 대화 정책에 비해 POMDP 대화 정책을 사용했을 때 평균 획득 포상이 Biagram 모델에서는 40%, Levin 모델에서는 13% 높은 결과를 얻어, 언어 처리 오류가 있는 환경에서 POMDP 대화 관리자의 사용이 우수한 결과를 냄을 보였다.
