(57)【要約】【課題】  対話戦略を学習するまでに必要な手間を削減すること。【解決手段】  対話戦略学習装置２が、マルコフ決定過程を学習するために、ユーザ端末への応答に対する評価値の入力を受け付ける手順と、状態の遷移の頻度に着目して類似する１つ以上の状態を１つのクラスタに統合する手順と、強化学習法によって評価値およびクラスタから第１マルコフ決定過程を作成する手順と、第１マルコフ決定過程のクラスタを統合される前の状態に分解して第２マルコフ決定過程を作成して記憶手段に記憶する手順と、第２マルコフ決定過程を対話システムで使用するマルコフ決定過程として出力する手順と、を実行することを特徴とする。【選択図】      図１
2006072477.tif 000002
【特許請求の範囲】
【請求項１】
ユーザ端末からの問い合わせ内容を、変数名を示すスロットと、そのスロットに代入される値との組で表現するシステム理解状態として保持し、現時点までに収集した対話データをもとにした対話の進捗度合いを表す有限個の状態と、前記状態において対話システムの次の発話内容を決定するための有限個のシステム行動から構成されるマルコフ決定過程に従って、前記システム理解状態から次のシステム行動を選択し、前記次のシステムの行動をもとにユーザ端末に応答する前記対話システムにおいて、前記マルコフ決定過程を学習する対話戦略学習方法であって、
コンピュータが、前記ユーザ端末への応答に対する評価値の入力を受け付ける手順と、前記状態の遷移の頻度に着目して類似する１つ以上の状態を１つのクラスタに統合する手順と、強化学習法によって前記評価値および前記クラスタから第１マルコフ決定過程を作成する手順と、前記第１マルコフ決定過程のクラスタを統合される前の状態に分解して第２マルコフ決定過程を作成して記憶手段に記憶する手順と、前記第２マルコフ決定過程を前記対話システムで使用するマルコフ決定過程として出力する手順と、
を実行することを特徴とする対話戦略学習方法。
【請求項２】
前記１つのクラスタに統合する手順は、強化学習アルゴリズムであるＱ−Ｌｅａｒｎｉｎｇの時刻ｔにおけるＱ値を最大にする行動が、所定の確率ｐで同じとなるような各状態を、１つのクラスタに統合することを特徴とする請求項１に記載の対話戦略学習方法。
【請求項３】
前記第１マルコフ決定過程を作成する手順は、過去に第２マルコフ決定過程を作成する手順において作成された前記第２マルコフ決定過程をもとに、現在の前記第１マルコフ決定過程を作成することを特徴とする請求項１または請求項２に記載の対話戦略学習方法。
【請求項４】
ユーザ端末からの問い合わせ内容を、変数名を示すスロットと、そのスロットに代入される値との組で表現するシステム理解状態として保持し、現時点までに収集した対話データをもとにした対話の進捗度合いを表す有限個の状態と、前記状態において対話システムの次の発話内容を決定するための有限個のシステム行動から構成されるマルコフ決定過程に従って、前記システム理解状態から次のシステムの行動を選択し、前記次のシステムの行動をもとにユーザ端末に応答する前記対話システムにおいて、前記マルコフ決定過程を学習する対話戦略学習装置であって、
ユーザ端末との対話ごとにフィードバックを収集および記録する対話評価収集部と、前記状態を分類することでクラスタを構成するクラスタ構成部と、強化学習法によって前記評価値および前記クラスタから第１マルコフ決定過程を作成し、前記第１マルコフ決定過程のクラスタを統合される前の状態に分解して第２マルコフ決定過程を作成する強化学習部と、
を有することを特徴とする対話戦略学習装置。
【請求項５】
前記クラスタ構成部は、強化学習アルゴリズムであるＱ−Ｌｅａｒｎｉｎｇの時刻ｔにおけるＱ値を最大にする行動が、所定の確率ｐで同じとなるような各状態を、１つのクラスタに統合することを特徴とする請求項４に記載の対話戦略学習装置。
【請求項６】
前記強化学習部は、過去に作成した前記第２マルコフ決定過程をもとに、現在の前記第１マルコフ決定過程を作成することを特徴とする請求項４または請求項５に記載の対話戦略学習装置。
【請求項７】
前記対話戦略学習装置は、前記対話システムをさらに含めて構成されることを特徴とする請求項４ないし請求項６のいずれか１項に記載の対話戦略学習装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、対話戦略学習方法、対話戦略学習プログラム、記憶媒体、および、対話戦略学習装置に関する。
【背景技術】
【０００２】
音声対話システムとユーザの対話は、ユーザとシステムが交互に音声で発話を行うことにより進行する。ここで、ユーザとは、厳密にはユーザが操作するユーザ端末である。ユーザ端末は、例えば、ユーザからの対話情報のインタフェースであるマイクロフォンやスピーカなどの周辺機器でもよいし、ＣＰＵ（Central Processing Unit）とメモリを有するパーソナルコンピュータでもよい。以下、ユーザがユーザ端末を操作してシステムと対話することを、単にシステムとユーザとの対話と省略する。
【０００３】
システムは、ユーザとの対話を通して、ユーザの問い合わせ内容を理解していく。システムがユーザの問い合わせ内容を理解した結果は、システム理解状態として保持される。システム理解状態は、通常スロットと値の対として表現される。システムは、ユーザ応答を受け付けるたびごとに、システム理解状態を更新する。対話の各時点において、システムは、その時点のシステム理解状態に基づいて、次にとるべきシステム行動を決定する。
【０００４】
対話の各時点においてシステムのとるべき行動を決定するためのルールは、システムの対話戦略、あるいは対話ポリシーと呼ばれる。システムの対話戦略は、システムの性能に対して大きな影響を及ぼす。しかし、システムが直面するあらゆる場面を想定して、最適な対話戦略を前もって人手で作成することは多大な労力を必要とする。また、対話戦略の良し悪しはユーザの振る舞いに依存するが、そもそも、ユーザの振る舞いを前もって予測することは困難である。そこで、従来から、システムの対話戦略を自動的に学習するための方法が考案されてきている。
【０００５】
システムの対話戦略を自動的に学習するための従来の技術として、Ｓｉｎｇｈ（非特許文献１）は、強化学習のアルゴリズムであるＱ−Ｌｅａｒｎｉｎｇ（非特許文献２）にしたがって、音声対話システムの対話戦略を学習する方法を提案した。Ｑ−Ｌｅａｒｎｉｎｇを用いた音声対話システムの対話戦略学習法としては、Ｓｃｈｅｆｆｅｒ（非特許文献３）によるＱ（λ）−Ｌｅａｒｎｉｎｇと呼ばれるＱ−Ｌｅａｒｎｉｎｇの変種を用いた方法もあるが、Ｓｉｎｇｈ（非特許文献１）の方法と本質的には同等である。
【０００６】
これらの従来技術では、まず、人手で簡易な対話戦略を作成する。この時点での対話戦略は最適なものを作成することは目指さずに、労力をかけずに人手で容易に作成できる対話戦略を用意する。この初期の対話戦略に基づいて動作するシステムを構築する。これを初期システムと呼ぶ。
【０００７】
次に、強化学習にしたがって対話戦略を学習する従来技術では、先に述べた初期システムを使って、ユーザとの対話を収集し、記録する。つまり、初期システムとユーザとの対話を複数回行い、対話ごとにユーザが対話の良し悪しを評価したフィードバック（評価値または報酬とも呼ばれる）を与える。
【０００８】
そして、音声対話システムは、ユーザの対話と、ユーザのフィードバックを収集および記録し、この記録されたデータから対話戦略を学習する。具体的には、収集された対話とユーザのフィードバックを用いて、Ｑ−Ｌｅａｒｎｉｎｇを適用し、ユーザの評価が最高になるように、状態間の遷移確率と、状態ごとに適用すべき最適の行動を決定する。これが対話戦略の学習である。
【０００９】
そして、音声対話システムは、新たに学習された対話戦略に基づいて動作するシステムを構築し、このシステムとユーザとの対話とユーザからのフィードバックを収集する。このように、初期システムから始まって、ユーザとの対話とユーザからのフィーバックに基づいて段階的に対話戦略を学習していく。
【非特許文献１】S.Singh、D.Litman、M.Kearns、and M、Walker著、“Optimizing Dialogue Management with Reinforcement Learning：Experiments with the NJFun System”、Jorunal of Artificial Intelligence Research、16、pp.105−133（2002）
【非特許文献２】R.S.Sutton and A.G.Barto著、“Reinforcement Learning”、MIT Press（1998）
【非特許文献３】K.Scheffler and S.J.Young著、“Corpus−based dialogue simulation for automatic strategy learning and evaluation”、In Proceedings NAACL Workshop on Adaptation in Dialogue Systems、pp.64−70（2001）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
強化学習によって対話戦略を学習するためには、状態と行動の組み合わせから成る探索空間を探索し、最適な対話戦略を見つける必要がある。
【００１１】
このとき、従来から認識されている問題として、状態と行動との組み合わせが膨大なものとなるため、対話戦略を学習するために要する対話データとユーザからのフィードバックを大量に用意しなければならず、対話戦略を学習するまでに手間がかかりすぎるという問題があった。
【００１２】
そこで、本発明は、前記した問題を解決し、対話戦略を学習するまでに必要な手間を削減することを主な目的とする。
【課題を解決するための手段】
【００１３】
前記課題を解決するため、本発明は、ユーザ端末からの問い合わせ内容を、変数名を示すスロットと、そのスロットに代入される値との組で表現するシステム理解状態として保持し、現時点までに収集した対話データをもとにした対話の進捗度合いを表す有限個の状態と、前記状態において対話システムの次の発話内容を決定するための有限個のシステム行動から構成されるマルコフ決定過程に従って、前記システム理解状態から次のシステム行動を選択し、前記次のシステムの行動をもとにユーザ端末に応答する前記対話システムにおいて、前記マルコフ決定過程を学習する対話戦略学習方法であって、コンピュータが、前記ユーザ端末への応答に対する評価値の入力を受け付ける手順と、前記状態の遷移の頻度に着目して類似する１つ以上の状態を１つのクラスタに統合する手順と、強化学習法によって前記評価値および前記クラスタから第１マルコフ決定過程を作成する手順と、前記第１マルコフ決定過程のクラスタを統合される前の状態に分解して第２マルコフ決定過程を作成して記憶手段に記憶する手順と、前記第２マルコフ決定過程を前記対話システムで使用するマルコフ決定過程として出力する手順と、を実行することを特徴とする。
【００１４】
これにより、状態クラスタの総数は状態の総数よりも小さくなるので、探索空間の大きさを削減することができ、従来方法と比較して、必要とされる対話データの量とユーザのフィードバックの量を削減することが可能となる。
【００１５】
本発明は、前記１つのクラスタに統合する手順が、強化学習アルゴリズムであるＱ−Ｌｅａｒｎｉｎｇの時刻ｔにおけるＱ値を最大にする行動が、所定の確率ｐで同じとなるような各状態を、１つのクラスタに統合することを特徴とする。
【００１６】
これにより、確率ｐを大きくするとクラスタに属する状態数を少なくし、確率ｐを小さくするとクラスタに属する状態数を多くするように、クラスタに属する状態数を操作することができる。
【００１７】
本発明は、前記第１マルコフ決定過程を作成する手順が、過去に第２マルコフ決定過程を作成する手順において作成された前記第２マルコフ決定過程をもとに、現在の前記第１マルコフ決定過程を作成することを特徴とする。
【００１８】
これにより、対話を重ねていくに従って、ユーザの満足度が徐々に向上する。
【００１９】
本発明は、ユーザ端末からの問い合わせ内容を、変数名を示すスロットと、そのスロットに代入される値との組で表現するシステム理解状態として保持し、現時点までに収集した対話データをもとにした対話の進捗度合いを表す有限個の状態と、前記状態において対話システムの次の発話内容を決定するための有限個のシステム行動から構成されるマルコフ決定過程に従って、前記システム理解状態から次のシステムの行動を選択し、前記次のシステムの行動をもとにユーザ端末に応答する前記対話システムにおいて、前記マルコフ決定過程を学習する対話戦略学習装置であって、ユーザ端末との対話ごとにフィードバックを収集および記録する対話評価収集部と、前記状態を分類することでクラスタを構成するクラスタ構成部と、強化学習法によって前記評価値および前記クラスタから第１マルコフ決定過程を作成し、前記第１マルコフ決定過程のクラスタを統合される前の状態に分解して第２マルコフ決定過程を作成する強化学習部と、を有することを特徴とする。
【００２０】
これにより、状態クラスタの総数は状態の総数よりも小さくなるので、探索空間の大きさを削減することができ、従来方法と比較して、必要とされる対話データの量とユーザのフィードバックの量を削減することが可能となる。
【００２１】
本発明は、前記クラスタ構成部が、強化学習アルゴリズムであるＱ−Ｌｅａｒｎｉｎｇの時刻ｔにおけるＱ値を最大にする行動が、所定の確率ｐで同じとなるような各状態を、１つのクラスタに統合することを特徴とする。
【００２２】
これにより、確率ｐを大きくするとクラスタに属する状態数を少なくし、確率ｐを小さくするとクラスタに属する状態数を多くするように、クラスタに属する状態数を操作することができる。
【００２３】
本発明は、前記強化学習部が、過去に作成した前記第２マルコフ決定過程をもとに、現在の前記第１マルコフ決定過程を作成することを特徴とする。
【００２４】
これにより、対話を重ねていくに従って、ユーザの満足度が徐々に向上する。
【００２５】
本発明は、前記対話戦略学習装置が、前記対話システムをさらに含めて構成されることを特徴とする。
【００２６】
これにより、ユーザとの対話機能と、その対話を改良する機能が１つの装置に納められることにより、効率的に学習成果を提供することができる。
【発明の効果】
【００２７】
本発明は、同様の状態を状態クラスタとしてまとめ、このクラスタによる近似解を活用することを特徴とする。これにより、状態クラスタの総数は状態の総数よりも小さくなるので、探索空間の大きさを削減することができ、従来方法と比較して、必要とされる対話データの量とユーザのフィードバックの量を削減することが可能となった。よって、対話戦略を学習するまでに必要な手間を削減することができた。
【発明を実施するための最良の形態】
【００２８】
以下に、本発明が適用される音声対話システムの一実施形態について、図面を参照して詳細に説明する。まず、対話戦略を強化学習によって学習する本実施形態の音声対話システムの構成について、図１を参照して説明する。
【００２９】
図１に示す本実施形態の音声対話システムは、交通経路、交通機関のスケジュール、テレビ番組表、個人のスケジュール表、飲食店情報、気象情報などのユーザが知りたい情報を記録したデータベース、あるいは、そういった情報に対してアクセスする機能をもつシステムである。
【００３０】
音声対話システムは、ユーザが必要とする情報についての問い合わせを音声により入力するとき、ユーザとの音声対話を通して、ユーザの問い合わせ内容を確定し、確定した問い合わせ内容にしたがって、ユーザが必要とする情報をユーザに提示する。そして、本実施形態の音声対話システムは、このユーザとの問い合わせと応答との対話の進め方を決定する対話戦略を自動的に学習することを特徴とする。以下、バス時刻表の案内を行う音声対話システムを例示する。
【００３１】
図１に示す音声対話システムは、対話戦略学習装置２が、ユーザと対話を行うものとする。なお、対話戦略学習装置２は、演算処理を行う際に用いられる記憶手段としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるコンピュータとして構成される。なお、メモリは、ＲＡＭ（Random Access Memory）などにより構成される。演算処理は、ＣＰＵによって構成される演算処理装置が、メモリ上のプログラムを実行することで、実現される。
【００３２】
対話戦略学習装置２は、ユーザの音声を入力するためのマイクロフォン１２と、システム音声を出力するためのスピーカ１４と、アプリケーションごとに与えられる対話に回答するための情報を格納する回答データベース１６と、を用いて、ユーザに案内する。なお、回答データベース１６は、ユーザの質問に答えるための情報を格納するものであり、例えば、バスの案内を行う際のバスの時刻表を管理する。なお、この回答データベース１６は、対話戦略学習装置２とは別の装置に構成し、その別の装置からネットワークによって対話戦略学習装置２が情報を取得するようにしてもよい。
【００３３】
ユーザが扱う前記ユーザ端末は、マイクロフォン１２とスピーカ１４として構成される。また、ユーザ端末は、これらの入出力手段としたのは、あくまで一例であり、コンピュータの装置として構成してもよい。
【００３４】
対話戦略学習装置２は、ユーザと音声で対話するために、ユーザの音声による発話の内容をもとにシステム理解状態を更新する発話理解部２２と、ユーザ発話内容をスロットと値の対として格納するシステム理解状態格納部２４と、対話の各時点におけるシステム理解状態にしたがって次の行動を決定する対話制御部２６と、システム理解状態を評価するフィーチャー関数を格納するフィーチャー関数格納部２８と、システムがとりうる行動を格納するシステム行動格納部３０と、決定されたシステム行動を言語表現として生成してスピーカ１４から出力する発話生成部３２と、を含めて構成される。
【００３５】
さらに、対話戦略学習装置２は、ユーザとの対話の満足度（ユーザから入力される評価値）を向上させるために、収集された対話とユーザのフィードバックを用いてユーザの評価が最高になるように行動を決定する強化学習部４０と、システムの状態を分類することでクラスタを構成するクラスタ構成部４２と、ユーザとの対話ごとにフィードバックを収集および記録する対話評価収集部４４と、を含めて構成され、これらの構成要素は、前記ユーザと音声で対話するためのアルゴリズムを、強化学習法によって改良することを特徴とする。
【００３６】
以下、対話戦略学習装置２の構成要素について、具体的に説明する。
【００３７】
発話理解部２２は、ユーザの音声による発話の内容を理解して、その発話の内容を示すシステム理解状態を更新する。そして、システム理解状態格納部２４は、システムの理解状態を、ユーザ発話内容（ユーザの問い合わせ内容を理解した結果）を表すスロットと値の対として格納する。
【００３８】
例えば、スロットとしては、到着地を表すＡｒｒｉｖａｌ  Ｌｏｃａｔｉｏｎ、出発地を表すＤｅｐａｒｔｕｒｅ  Ｌｏｃａｔｉｏｎ、出発日を表すＤａｙ、出発時刻を表すＴｉｍｅの４つのスロットを用いる。表１のスロットと値の対は、Ｗｅｅｋｄａｙ（平日）の１５：３０（１５時３０分）にＨｏｎａｔｓｕｇｉｅｋｉ（本厚木駅）に到着するバスに乗るというシステム理解状態を表す。つまり、スロットとはコンピュータが扱う変数名に相当し、値とはそのスロットに代入される変数値である。
【００３９】
【表１】
2006072477.tif 000003
さらに、対話戦略学習装置２は、システム理解状態の内容をユーザに確認する。たとえば、前記のシステム理解状態において、「到着地は本厚木駅ですか？」という確認をユーザに対して行う。システムの確認に対してユーザが肯定を意味する表現（例：「はい」）で応答した場合、確認内容がユーザによって承認されたと呼ぶ。
【００４０】
対話制御部２６は、対話の各時点におけるシステム理解状態にしたがって、システムの次の行動を決定する。この対話制御部２６を実現するアルゴリズムは、マルコフ決定過程として表現される。マルコフ決定過程は、有限個の状態と、有限個のシステム行動により構成され、各状態において適用できる行動が決まっている。なお、状態は、現時点までで収集した対話データをもとにした対話の進捗度合いを表す。また、システム行動は、前記状態において、対話戦略学習装置２の次の発話内容を決定するための状態遷移を表す。
【００４１】
ある状態において、特定の行動が選択され、実行されると、状態は次の状態に移行する。状態から状態への遷移確率は前もって与えられている。マルコフ決定過程の各状態において、一つの行動を決定するルールはポリシーと呼ばれる。このポリシーが、音声対話システムの場合、対話戦略、対話ポリシーに対応するものである。
【００４２】
マルコフ決定過程の各状態は、対話の状態の特定の局面を表すフィーチャー関数と呼ぶ関数によって定義する。フィーチャー関数格納部２８は、フィーチャー関数を管理する。以下、フィーチャー関数の一例について表２を参照して説明する。
【００４３】
【表２】
2006072477.tif 000004
フィーチャー関数Ｃｏｎｆｉｒｍａｔｉｏｎは、すべてのスロットの値がユーザにより承認されているなら、ａｌｌ  ｃｏｎｆｉｒｍｅｄという値をとり、一つのスロットの値も承認されていないなら、ａｌｌ  ｕｎｃｏｎｆｉｒｍｅｄという値をとり、そのいずれでもないなら、ｓｏｍｅ  ｕｎｃｏｎｆｉｒｍｅｄという値をとる。
【００４４】
フィーチャー関数Ｉｎｆｏｒｍａｔｉｏｎは、すべてのスロットに対して値が与えられているなら、ａｌｌ  ｆｉｌｌｅｄという値をとり、一つのスロットにも値が与えられていないなら、ｎｏ  ｆｉｌｌｅｄという値をとり、そのいずれでもないなら、ｓｏｍｅ  ｆｉｌｌｅｄという値をとる。
【００４５】
フィーチャー関数Ｌｅｎｇｔｈ  ｏｆ  Iｎｐｕｔは、ユーザの入力の長さについてあらかじめ決めた基準にしたがって、ユーザの入力が短ければｓｈｏｒｔ、中程度であればｉｎｔｅｒｍｅｄｉａｔｅ、長ければｌｏｎｇ、非常に長ければｖｅｒｙ  ｌｏｎｇを値としてとる。
【００４６】
フィーチャー関数Ｍｉｎｉｍａｌ  Ｃｏｎｆｉｄｅｎｃｅは、すべてのスロットの値に付随する信頼度の中で最小の信頼度を選択し、その信頼度が高ければｈｉｇｈ、中程度であればｍｅｄｉｕｍ、低ければｌｏｗを値としてとる。
【００４７】
フィーチャー関数Ｍａｘｉｍａｌ  Ｃｏｎｆｉｄｅｎｃｅは、すべてのスロットの値に付随する信頼度の中で最大の信頼度を選択し、その信頼度が高ければｈｉｇｈ、中程度であればｍｅｄｉｕｍ、低ければｌｏｗを値としてとる。
【００４８】
フィーチャー関数Ｉｎｔｅｎｔｉｏｎは、ユーザの問い合わせのタイプが決まっていないなら、ｓｅｌｅｃｔｅｄという値をとり、ユーザの問い合わせタイプは決まったが、その問い合わせタイプの内容を決定するために必要な値が与えられていないスロットが存在するなら、ｄｅｔｅｒｍｉｎｅｄという値をとり、ユーザの問い合わせタイプが決まり、かつ、必要なスロットの値がすべて与えられているなら、ｆｉｎａｌｉｚｅｄという値をとる。
【００４９】
次に、システム行動格納部３０が管理するシステム行動の一例について、表３を参照して説明する。
【００５０】
【表３】
2006072477.tif 000005
システム行動としては、ユーザにスロットの値を確認する確認型の行動と、ユーザにスロットの値を要求する情報要求型の行動がある。確認型であり、かつ、情報要求型の行動もある。また、単一スロットのみに関わる行動、複数スロットに関わる行動がある。表２で、Ｅｘｐｌ．ｃｏｎｆｉｒｍａｔｉｏｎというシステム行動は、単一スロットの値をユーザに確認する行動である。
【００５１】
Ｐｒｏｍｐｔ  ｏｎｅというシステム行動は、単一スロットの値をユーザに要求する行動である。Ｐｒｏｍｐｔ  ｍｕｌｔｉｐｌｅは複数スロットの値をユーザに要求する行動である。Ｉｍｐｌ．ｃｏｎｆ．ｐｒｏｍｐｔ  ｏｎｅというシステム行動は、あるスロットの値を陰に確認しつつ、単一スロットの値をユーザに要求する行動である。Ｉｍｐｌ．ｃｏｎｆ．ｐｒｏｍｐｔ  ｍｕｌｔｉｐｌｅというシステム行動は、あるスロットの値を陰に確認しつつ、複数スロットの値をユーザに要求する行動である。
【００５２】
強化学習部４０は、収集された対話とユーザのフィードバックを用いて、Ｑ−Ｌｅａｒｎｉｎｇ（非特許文献２）を適用し、ユーザの評価が最高になるように、状態間の遷移確率と、状態ごとに適用すべき最適の行動を決定する。Ｑ−Ｌｅａｒｎｉｎｇは、マルコフ決定過程上で動作する強化学習のアルゴリズムである。Ｑ−Ｌｅａｒｎｉｎｇを適用するためには、システムの動作を前記のマルコフ決定過程として記述する必要がある。そして、強化学習部４０は、学習されたマルコフ決定過程を、対話制御部２６へ更新することで、ユーザとの対話の満足度を向上させる。
【００５３】
強化学習部４０が、マルコフ決定過程を作成する方法を、２つ挙げる。
【００５４】
マルコフ決定過程の第１の作成方法は、初期システムを作成する方法である。これは、最適な戦略をあらかじめ与えることは困難であるために、初期システムとして簡易な対話戦略を作成することである。この時点での対話戦略は最適なものを作成することは目指さずに、既にテンプレートとして作成された初期の対話戦略を利用する。この初期の対話戦略に基づいて動作する初期システムを構築する。
【００５５】
マルコフ決定過程の第２の作成方法は、ユーザとの対話を重ねていくことによって、前記初期システムを徐々に改良していく方法である。この改良方法における特徴として、マルコフ決定過程を構成する１つ以上の状態を１つの仮想的な状態（以下、クラスタと呼ぶ）にまとめてから、このクラスタに対してマルコフ決定過程を作成することが挙げられる。
【００５６】
クラスタ構成部４２は、１つ以上の状態を１つのクラスタにまとめるための計算を行う際に、前記フィーチャー関数格納部２８に格納されているフィーチャー関数を活用する。
【００５７】
対話評価収集部４４は、マルコフ決定過程を作成するために必要なフィードバック（評価値）を収集する。つまり、初期システムとユーザとの対話を複数回行い、対話ごとにユーザが対話の良し悪しを評価したフィードバックを与える。システムとユーザの対話と、ユーザのフィードバックを収集および記録する。そして、各対話の終わりに、ユーザは対話の良し悪しを評価したフィードバックを与え、システムはこれを記録する。フィードバックは、−１、０、１のいずれかであり、直感的には、−１は対話の質が悪かったこと、Ｏは対話の質が良くも悪くもなかったこと、１は対話の質が良かったことを示す。
【００５８】
ここで、マルコフ決定過程の作成方法について、具体的に説明する。まず、以下の説明のために、マルコフ決定過程を表現するための数学的表記を説明する。マルコフ決定過程は、＜Ｓ、Ａ、Ｐ、Ｒ＞の４組で表される。このとき、Ｓは状態（ｓ１，．．．，ｓｎ）の有限集合であり、Ａは行動（ａ１，．．．，ａｍ）の有限集合であり、Ｐ（ｓ’｜ｓ、ａ）は、状態ｓにおいて行動ａをとった後に状態ｓから状態ｓ’に移行する確率を表し、Ｒ（ｓ、ａ、ｓ’）は、行動ａによって状態ｓから状態ｓ’に遷移する際に得られる報酬を表す。
【００５９】
状態ｓにおいて行動ａをとったときに、行動ａの期待報酬Ｒ（ｓ，ａ）は次のように定義される。
【００６０】
【数１】
2006072477.tif 000006
次に、マルコフ決定過程の第１の作成方法について、具体的に説明する。なお、第１の作成方法は、強化学習（非特許文献２）について説明するものである。強化学習とは、システムが、システムを取り囲む環境（音声対話システムの場合はユーザ）との試行錯誤的なインタラクションを通して、最適なポリシーを学習するという課題を解決する方法の総称である。以下、強化学習の概要について、説明する。後記の式（２）、式（３）によってポリシーを段階的に洗練していく手順は、ポリシー改良（ｐｏｌｉｃｙ  ｉｍｐｒｏｖｅｍｅｎｔ）と呼ばれ、マルコフ決定過程を解くための一般的に知られた手順である（非特許文献２）。
【００６１】
Ｑ−Ｌｅａｒｎｉｎｇの時刻ｔにおけるシステムのポリシーπtは、状態ｓで行動ａを選択することの良さを推定する、時刻ｔにおける行動価値関数Ｑ’（ｓ，ａ）に基づいて決定される。行動価値関数の値は、Ｑ値とも呼ばれる。Ｑ値の真の値は、次の式（２）を解くことによって、計算される。ここで、γはＯより大きく１より小さな値であり、関数πは、システムのポリシーを表す関数であって、状態ｓからｓで採用する行動ａへの関数である。
【００６２】
【数２】
2006072477.tif 000007
式（２）に基づいて、時刻ｔにおける行動価値関数Ｑt（ｓ，ａ）を時刻ｔにおけるポリシーπtから求める。次に、時刻ｔにおける行動価値関数Ｑt（ｓ，ａ）に基づいて、次式（３）を使って、時刻ｔ＋１におけるポリシーを決定する。
【００６３】
【数３】
2006072477.tif 000008
以上の概要を実現するためのアルゴリズムは、図２の通りである。
【００６４】
対話戦略学習装置２は、システムの初期の状態をｓ０とし、現在の状態ｓｆにｓ０を初期設定として代入する（Ｓ１０１）。対話戦略学習装置２は、システムの行動のそれぞれについて、その行動が現在のシステムの状態ｓｆにおいて適用可能かどうか判断する（Ｓ１０２）。まず、適用可能であれば、対話戦略学習装置２は、ステップＳ１０２で見つけた適用可能な行動の中で、マルコフ決定過程において定義される期待報酬を最大とするような行動ａｆを選択する（Ｓ１０３）。一方、適用可能でなければ、処理を終了する。
【００６５】
対話戦略学習装置２は、選択された行動ａｆを適用し、ユーザの応答を待つ（Ｓ１０４）。対話戦略学習装置２は、ユーザの応答によってシステムの理解状態を更新する（Ｓ１０５）。対話戦略学習装置２は、システムの状態を更新し、更新後の状態をシステムの現在の状態ｓｆに設定し（Ｓ１０６）、ステップＳ１０２に戻る。
【００６６】
さらに、マルコフ決定過程の第２の作成方法について、その概要を説明する。なお、第１の作成方法と第２の作成方法との差異は、マルコフ決定過程の状態をクラスタとして集約しないか（第１の作成方法）、または、クラスタとして集約するか（第２の作成方法）である。
【００６７】
まず、状態クラスタを構成するために、クラスタ関数ｃ：｛１，．．．，ｎ｝→｛１，．．．，ｋ｝、ｋ＞ｎを導入する、関数ｃによって、元のマルコフ決定過程の各状態ｓ1，．．．，ｓnをｋ個のクラスタＳ1，．．．，Ｓkのいずれかに割り当てる。
【００６８】
ここで、システムがクラスタＳjにいるときに状態ｓiが選ばれるサンプリング関数ｑ（ｓ｜Ｓ）を導入する。この関数は次のように計算される。
【００６９】
【数４】
2006072477.tif 000009
ただし、Ｐ（ｓ）はシステムが状態ｓにいる確率である。
【００７０】
次に、システムが、クラスタ８において行動ａをとったときに、クラスタＳ’に遷移する確率Ｐ（Ｓ’｜Ｓ、ａ）を次のように計算する。
【００７１】
【数５】
2006072477.tif 000010
同様にして、行動ａによってクラスタＳからクラスタＳ’に遷移する際の報酬関数は次のように計算する。
【００７２】
【数６】
2006072477.tif 000011
以上のようにして、クラスタ、クラスタ間の遷移確率、クラスタにおける報酬関数を計算することにより、集約されたマルコフ決定過程を作成する。次に、マルコフ決定過程を解く標準的な方法であるポリシー改良法（非特許文献２）を使って、集約されたマルコフ決定過程を解く。その後、次の式にしたがって、集約されたマルコフ決定過程の解を元のマルコフ決定過程の解に分解し、元のマルコフ決定過程の近似的な解を得る。この解は、対話戦略学習装置２の記憶手段（メモリやハードディスクなどのハードウェア資源）に記憶される。
【００７３】
【数７】
2006072477.tif 000012
式（７）を適用する前と後でＱ値の変化が、あらかじめ与えておく閾値よりも大きくなったときは、解が安定していないと推定されるので、得られた解の質が良くないとする。このとき、式（７）で得られた新たなＱ値に基づいてクラスタ関数を選択し直し、クラスタを作成し直す。
【００７４】
なお、クラスタを作成し直した後は、既に説明したように、式（４）、式（５）、式（６）に基づいて、集約されたマルコフ決定過程をあらためて作成することになるが、このとき、集約されたマルコフ決定過程におけるＱ値の計算は、次の式（８）に従う。
【００７５】
【数８】
2006072477.tif 000013
得られた解の質が十分でないなら、クラスタ関数の選択をやり直す。
【００７６】
以上説明した概要を実現するためのアルゴリズムとして、図３を参照して、具体的に説明する。
【００７７】
対話戦略学習装置２は、クラスタ関数ｃを選択する（Ｓ２０１）。対話戦略学習装置２は、式（４）、（５）、（６）にしたがって、集約されたマルコフ決定過程を作成する。集約されたマルコフ決定過程におけるＱ値は、式（８）に基づいて計算する（Ｓ２０２）。
【００７８】
対話戦略学習装置２は、ポリシー改良法（非特許文献２）などのマルコフ決定過程を解く標準的な方法にしたがって、集約されたマルコフ決定過程を解く（Ｓ２０３）。対話戦略学習装置２は、式（７）にしたがって、集約されたマルコフ決定過程の解を元のマルコフ決定過程の解に分解することで、元のマルコフ決定過程の近似的な解を得る（Ｓ２０４）。対話戦略学習装置２は、Ｑ値の変化が、あらかじめ与えておく閾値よりも大きくなったときは、ステップＳ２０１に戻る（Ｓ２０５）。一方、閾値よりも大きくならないときは、Ｑ値が安定したとして、処理を終了する。
【００７９】
ここで、マルコフ決定過程の第２の作成方法におけるステップＳ２０１について、具体的に説明する。
【００８０】
ステップＳ２０１において、クラスタ関数を選択し、クラスタを構成する必要がある。ここでは、クラスタは、すでに説明したフィーチャー関数に基づいて構成される。
【００８１】
フィーチャー関数ｆは、システム理解状態や、音声認識結果の信頼度に基づいて、システムの状態を分類することによって、クラスタを構成するという役割を果たすと考えることができる。すなわち、あるフィーチャー関数ｆがとる値によって状態を分類し、クラスタを構成することができる。たとえば、Ｃｏｎｆｉｒｍａｔｉｏｎというフィーチャー関数がａｌｌ  ｕｎｃｏｎｆｉｒｍｅｄという値をとるような状態を取り出して、一つのクラスタを構成し、ｓｏｍｅ  ｃｏｎｆｉｒｍｅｄという値をとるような状態を取り出して、一つのクラスタを構成し、ａｌｌ  ｃｏｎｆｉｒｍｅｄという値をとるような状態を取り出して、一つのクラスタを構成するというように、クラスタを構成することができる。
【００８２】
考慮するフィーチャー関数をｆ１，．．．，ｆｌと書くこととする。フィーチャー関数が特定の値をとるような状態を取り出して、一つのクラスタを構成するということは、次の制約集合を満たすような状態の集合を一つのクラスタと考えることを意味する。ただし、それぞれのフィーチャー関数がとる値をｖ１，．．．，ｖｌと書くものとする。
【００８３】
【数９】
2006072477.tif 000014
システムで用意したすべてのフィーチャー関数を考慮し、それぞれのフィーチャー関数が特定の値をとるという制約の下に一つのクラスタを構成する場合には、一つの状態のみから構成される最小のクラスタを与えることになる。考慮するフィーチャー関数を減らしていくことにより、より大きなクラスタを構成することができる。本発明の実施においては、同じような状態をできるだけまとめあげ、一つのクラスタとすることにより、できるだけ大きなクラスタを構成し、クラスタの総数を減らす処理を行う。この処理により、計算量を削減することができる。以下、クラスタの総数を減らす処理を説明する。
【００８４】
まず、時刻ｔにおける行動価値関数Ｑt（ｓ，ａ）が与えられるとき、各状態ｓにおいて行動価値関数Ｑt（ｓ，ａ）を最大にする行動が、確率ｐで同じ行動ａ*になる状態を一つのクラスタとするように、最小の制約集合を求める。なお、この１つのクラスタとなる状態は、前記状態の遷移の頻度に着目して類似するといえる。すなわち、次の式を満たすような状態ｓが一つのクラスタの中に入るような最小の制約集合を求める。
【００８５】
【数１０】
2006072477.tif 000015
このようにして、クラスタを構成する。既に説明したように、クラスタ関数はＱ値に依存するので、図３のステップＳ２０１においては、このステップが実行されるときのＱ値に基づいてクラスタ関数が選択される。
【００８６】
以上に述べた方法によって、状態クラスタの総数は状態の総数よりも小さくなるので、探索空間の大きさを削減することができ、従来方法と比較して、必要とされる対話データの量とユーザのフィードバックの量を削減することが可能となる。そして、このことにより、対話戦略を学習するまでに必要な手間を削減することができる。
【００８７】
以上の本実施形態の要約は、以下のとおりである。ユーザと音声で対話しながらユーザの問い合わせ内容を理解する音声対話システムにおいて、ユーザの問い合わせ内容を理解した結果をスロットと値の対として表現したシステム理解状態を保持し、この状態を状態クラスタとしてまとめあげ、この状態クラスタから構成されるサイズのより小さいマルコフ決定過程を作成し、このマルコフ決定過程を解いた後で、この近似的な解を元のマルコフ決定過程の解に戻し、あらかじめ記録したフィードバックの情報から強化学習法を使って、対話各時点のシステムの行動を選択するための対話戦略を学習する。
【００８８】
以上説明した本発明は、以下のようにその趣旨を逸脱しない範囲で広く変形実施することができる。
【００８９】
例えば、対話戦略学習装置２は、対話戦略の学習（マルコフ決定過程の作成）について、１回ではなく継続的に行うことができる。つまり、Ｎ回目のマルコフ決定過程の作成結果をもとに、Ｎ＋１回目のマルコフ決定過程を作成する。そして、１回目のマルコフ決定過程の作成は、初期システムを作成する。
【００９０】
また、対話戦略学習装置２は、大きく２つの系統に分類することができる。まず、マルコフ決定過程の作成系は、強化学習部４０、クラスタ構成部４２（さらに、クラスタの構成に必要なフィーチャー関数格納部２８）、対話評価収集部４４である。一方、マルコフ決定過程の実行系は、対話戦略学習装置２から前記マルコフ決定過程の作成系を除外して、フィーチャー関数格納部２８を追加したものである。この分類に従って、１つの対話戦略学習装置２を２つの装置に分割し、各装置をネットワークで接続するような実施形態も構成可能である。このようにすることで、機能分担に関する処理能力の軽減が可能となる。
【００９１】
さらに、対話戦略学習装置２によるユーザとの対話の種別（メディア）は、音声信号（マイクロフォン１２とスピーカ１４が処理する）だけに限定されず、映像データや、テキストデータなど、様々なものが活用可能である。その際には、回答データベース１６においてユーザからの質問に答えられるように、インタフェースに種別の変換処理をもたせればよい。例えば、映像データが入力されたときには、その映像データから音声データを抽出し、その音声データをテキストデータに変換するような処理が、変換処理の一例として挙げられる。
【図面の簡単な説明】
【００９２】
【図１】本発明の一実施形態に関する音声対話システムの構成図である。
【図２】本発明の一実施形態に関するクラスタを作成しないマルコフ決定過程の動作を示すフローチャートである。
【図３】本発明の一実施形態に関するクラスタを作成するマルコフ決定過程の動作を示すフローチャートである。
【符号の説明】
【００９３】
２      対話戦略学習装置
２２    発話理解部
２４    システム理解状態格納部
２６    対話制御部
２８    フィーチャー関数格納部
３０    システム行動格納部
３２    発話生成部
４０    強化学習部
４２    クラスタ構成部
４４    対話評価収集部
【図１】
2006072477.tif 000016
【図２】
2006072477.tif 000017
【図３】
2006072477.tif 000018