(57)【要約】      （修正有）【課題】価値反復計算を高速に近似実行することが可能な制御方策決定装置を提供する。【解決手段】制御方策決定装置は、不確定性を含む環境センシング情報に基づいて、信念空間上の価値関数の線形要素を与える線形関数の候補集合を生成する初期線形関数生成部１と、信念空間上の候補集合を双対空間上の複数の点に変換する双対変換部２と、複数の点の近似凸包を計算する凸包近似計算部３２と、近似凸包の頂点のメンバーシップ関数を決定するメンバーシップ決定部３４と、近似凸包の上辺を抽出する凸包上辺抽出部３６と、上辺に属する頂点を信念空間上の線形関数に逆変換する逆双対変換部４と、得られた線形関数に基づいて、バックアップステップ数に応じて線形関数を更新して双対変換部２に出力する線形関数更新部６と、線形関数の更新の後に逆変換によって得られた線形関数に基づいて、近似価値関数の複数の線形要素を求める価値関数決定部５を備えている。【選択図】図２
2014179064.tif 000002
【特許請求の範囲】
【請求項１】
不確定性を含む環境センシング情報に基づいて制御方策を決定する制御方策決定装置であって、
前記環境センシング情報に基づいて、信念空間上の価値関数の線形要素を与える線形関数の候補集合を生成する線形関数生成部と、
前記信念空間上の前記候補集合を双対空間上の複数の点に変換する双対変換部と、
前記複数の点の凸包を近似する近似凸包を計算する凸包近似計算部と、
前記近似凸包の頂点のメンバーシップ関数を決定するメンバーシップ決定部と、
前記近似凸包の上辺を抽出する凸包上辺抽出部と、
前記上辺に属する頂点を前記信念空間上の線形関数に逆変換する逆双対変換部と、
前記逆変換によって得られた線形関数に基づいて、バックアップステップ数に応じて線形関数を更新する線形関数更新部と、
を備え、
前記双対変換部は、さらに前記バックアップステップ数に応じて更新された線形関数を前記候補集合として、双対空間上の複数の点に変換し、
前記制御方策決定装置は、さらに、
前記バックアップステップ数の線形関数の更新の後に前記逆変換によって得られた線形関数に基づいて、近似価値関数の複数の線形要素を求める価値関数決定部と、
前記近似価値関数の複数の線形要素の各々に対して、前記メンバーシップ関数に従って行動を割り当てる方策決定部と、
を備えたことを特徴とする制御方策決定装置。
【請求項２】
前記メンバーシップ決定部は、前記双対空間上の複数の点に適用した場合に正しいメンバーシップが得られるメンバーシップ関数を、前記近似凸包の頂点のメンバーシップ関数として決定することを特徴とする請求項１に記載の制御方策決定装置。
【請求項３】
前記メンバーシップ決定部は、前記双対空間上の複数の点を前記近似凸包に変換する行列でもって、前記双対空間上の複数の点のメンバーシップ関数を変換したものを、前記近似凸包の頂点のメンバーシップ関数として決定することを特徴とする請求項２に記載の制御方策決定装置。
【請求項４】
前記線形関数更新部は、各バックアップステップにおける前記線形関数の更新を観測値ごとに行うことを特徴とする請求項１ないし３のいずれかに記載の制御方策決定装置。
【請求項５】
請求項１ないし４のいずれかに記載の制御方策決定装置と、
前記環境センシング情報を入力する環境センシング情報入力部と、
前記制御方策決定装置にて割り当てられた行動を実行するための制御コマンドを出力する出力部と、
を備えたことを特徴とする制御システム。
【請求項６】
不確定性を含む環境センシング情報に基づいて制御方策を獲得する制御方策決定方法であって、
前記環境センシング情報を入力する環境センシング情報入力ステップと、
前記環境センシング情報に基づいて、信念空間上の価値関数の線形要素を与える線形関数の候補集合を生成する線形関数生成ステップと、
前記信念空間上の前記候補集合を双対空間上の複数の点に変換する双対変換ステップと、
前記複数の点の凸包を近似する近似凸包を計算する近似凸包計算ステップと、
前記近似凸包の頂点のメンバーシップ関数を決定するメンバーシップ決定ステップと、
前記近似凸包の上辺を抽出する凸包上辺抽出ステップと、
前記上辺に属する頂点を前記信念空間上の線形関数に逆変換する逆双対変換ステップと、
前記逆変換によって得られた線形関数に基づいて、バックアップステップ数に応じて線形関数を更新する線形関数更新ステップと、
を含み、
前記双対変換ステップは、さらに前記バックアップステップ数に応じて更新された線形関数を前記候補集合として、双対空間上の複数の点に変換し、
前記制御方策決定方法は、さらに、
前記バックアップステップ数の線形関数の更新の後に前記逆変換によって得られた線形関数に基づいて、近似価値関数の複数の線形要素を求める価値関数決定ステップと、
前記近似価値関数の複数の線形要素の各々に対して、前記メンバーシップ関数に従って行動を割り当てる方策決定ステップと、
を含むことを特徴とする制御方策決定方法。
【請求項７】
コンピュータを、
不確定性を含む環境センシング情報に基づいて制御方策を決定する制御方策決定装置であって、
前記環境センシング情報に基づいて、信念空間上の価値関数の線形要素を与える線形関数の候補集合を生成する線形関数生成部と、
前記信念空間上の前記候補集合を双対空間上の複数の点に変換する双対変換部と、
前記複数の点の凸包を近似する近似凸包を計算する凸包近似計算部と、
前記近似凸包の頂点のメンバーシップ関数を決定するメンバーシップ決定部と、
前記近似凸包の上辺を抽出する凸包上辺抽出部と、
前記上辺に属する頂点を前記信念空間上の線形関数に逆変換する逆双対変換部と、
前記逆変換によって得られた線形関数に基づいて、バックアップステップ数に応じて線形関数を更新する線形関数更新部と、
を備え、
前記双対変換部は、さらに前記バックアップステップ数に応じて更新された線形関数を前記候補集合として、双対空間上の複数の点に変換し、
前記制御方策決定装置は、さらに、
前記バックアップステップ数の線形関数の更新の後に前記逆変換によって得られた線形関数に基づいて、近似価値関数の複数の線形要素を求める価値関数決定部と、
前記近似価値関数の複数の線形要素の各々に対して、前記メンバーシップ関数に従って行動を割り当てる方策決定部と、
を備えた制御方策決定装置として機能させるための制御方策決定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、対話システム、自立移動ロボットや車両等におけるノイズ等の不確定性を含む環境センシング情報に基づいて制御方策を決定する制御方策決定装置及びそれを含む制御システム、制御方策決定方法に関するものである。
【背景技術】
【０００２】
従来より、部分観測可能マルコフ決定過程（ＰＯＭＤＰ：Partially Observable Markov Decision Process）に基づいて、システムの最適な制御方策を決定する価値関数を強化学習の枠組みによって自動的に獲得する技術が知られている。
【０００３】
状態数とアクション（行動）とが有限（離散的）である場合、ＰＯＭＤＰの価値関数は、信念空間上の区分線形な関数で表されることが知られている。信念空間は、次元が状態数と等しいユークリッド空間の中で、各座標値が正でかつそれらの和が１となるような超平面として与えられる。信念空間上の点の各座標値は、対応する状態をシステムが取る確率となっている。また、各線形関数には、アクションの１つが対応する。
【０００４】
この区分線形な価値関数は、複数の線形関数が決定する下半空間の上界として与えられる。これらの線形関数の数は、制御方策を決定するために先読みするステップ数に関して指数関数的に増加する。そのような多くの線形関数の中から、上界を与える線形関数を決定するには、膨大な計算量を要する。従って、このＰＯＭＤＰの定式そのままでは、現実的な問題へ適用することが困難である。
【０００５】
そのため、近似的に価値関数を計算する方法が提案されてきた。特に、ＰＢＶＩ（Point-Based Value Iteration）という方法は、実装が容易であり、よく利用されている。また、ＰＢＶＩの様々な拡張がなされている（例えば、非特許文献１）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】G. Shani, J. Pineau and R. Kaplow, "A Survey of Point-Based POMDP solvers" , Auton Agent Multi-Agent Syst (Published Online, 08 June 2012), DOI 10.1007/s10458-012-9200-2.
【非特許文献２】C. Thurau, K. Kersting and C. Bauckhage, "Convex Non-Negative Matrix Factorization in the Wild", (ICDM 2009, pp. 523-532), DOI: 10.1109/ICDM.2009.55.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、ＰＢＶＩによる方法は、純粋なＰＯＭＤＰに比べて、大きく計算量が削減されてはいるが、以下のような課題がある。すなわち、ＰＢＶＩによる方法は、近似に用いる点の決め方によって近似精度が大きく影響するところ、理論的にどのような点を選択するべきか、明確な基準がないという課題がある。そのため、近似の精度を上げるためには多くの点を採用する必要があり、結果として、依然として大きな計算リソースを必要とする。通常、この点の数は、状態数に対して指数関数的に増大するため、やはり実用的な問題への適用する際に大きな制約がある。
【０００８】
本発明は、上記の問題に鑑みてなされたものであり、部分観測可能マルコフ決定過程（ＰＯＭＤＰ）によりシステム制御をモデル化し、その価値関数を強化学習によって自動獲得するための計算コストを削減し、このようなシステム制御モデルを実用的な問題へ適用可能にすることを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、本発明の制御方策決定装置は、不確定性を含む環境センシング情報に基づいて制御方策を決定する制御方策決定装置であって、前記環境センシング情報に基づいて、信念空間上の価値関数の線形要素を与える線形関数の候補集合を生成する線形関数生成部と、前記信念空間上の前記候補集合を双対空間上の複数の点に変換する双対変換部と、前記複数の点の凸包を近似する近似凸包を計算する凸包近似計算部と、前記近似凸包の頂点のメンバーシップ関数を決定するメンバーシップ決定部と、前記近似凸包の上辺を抽出する凸包上辺抽出部と、前記上辺に属する頂点を前記信念空間上の線形関数に逆変換する逆双対変換部と、前記逆変換によって得られた線形関数に基づいて、バックアップステップ数に応じて線形関数を更新する線形関数更新部とを備え、前記双対変換部は、さらに前記バックアップステップ数に応じて更新された線形関数を前記候補集合として、双対空間上の複数の点に変換し、前記制御方策決定装置は、さらに、前記バックアップステップ数の線形関数の更新の後に前記逆変換によって得られた線形関数に基づいて、近似価値関数の複数の線形要素を求める価値関数決定部と、前記近似価値関数の複数の線形要素の各々に対して、前記メンバーシップ関数に従って行動を割り当てる方策決定部とを備えた構成を有している。
【００１０】
この構成により、信念空間上の候補集合が双対空間に写像された上で、その凸包を近似する近似凸包の上辺の頂点及びそのメンバーシップ関数が求められるので、バックアップステップ数（価値反復区間）が大きくなった場合にも、近似価値関数を高速に計算して、候補集合の要素に行動を割り当てることができる。
【００１１】
上記の制御方策決定装置において、前記メンバーシップ決定部は、前記双対空間上の複数の点に適用した場合に正しいメンバーシップが得られるメンバーシップ関数を、前記近似凸包の頂点のメンバーシップ関数として決定してよい。
【００１２】
この構成により、近似凸包が双対空間上の複数の点の凸包に一致する場合に、正しいメンバーシップに帰着するという条件を満たすメンバーシップ関数を得ることができる。
【００１３】
上記の制御方策決定装置において、前記メンバーシップ決定部は、前記双対空間上の複数の点を前記近似凸包に変換する行列でもって、前記双対空間上の複数の点のメンバーシップ関数を変換したものを、前記近似凸包の頂点のメンバーシップ関数として決定してよい。
【００１４】
上記の制御方策決定装置において、前記線形関数更新部は、各バックアップステップにおける前記線形関数の更新を観測値ごとに行ってよい。
【００１５】
本発明の制御システムは、上記の制御方策決定装置と、前記環境センシング情報を入力する環境センシング情報入力部と、前記制御方策決定装置にて割り当てられた行動を実行するための制御コマンドを出力する出力部とを備え構成を有している。
【００１６】
この構成によっても、信念空間上の候補集合が双対空間に写像された上で、その凸包を近似する近似凸包の上辺の頂点及びそのメンバーシップ関数が求められるので、価値反復区間（バックアップステップ数）が大きくなった場合にも、近似価値関数を高速に計算して、候補集合の要素に行動を割り当てることができる。
【００１７】
本発明の制御方策決定方法は、不確定性を含む環境センシング情報に基づいて制御方策を獲得する制御方策決定方法であって、前記環境センシング情報を入力する環境センシング情報入力ステップと、前記環境センシング情報に基づいて、信念空間上の価値関数の線形要素を与える線形関数の候補集合を生成する線形関数生成ステップと、前記信念空間上の前記候補集合を双対空間上の複数の点に変換する双対変換ステップと、前記複数の点の凸包を近似する近似凸包を計算する近似凸包計算ステップと、前記近似凸包の頂点のメンバーシップ関数を決定するメンバーシップ決定ステップと、前記近似凸包の上辺を抽出する凸包上辺抽出ステップと、前記上辺に属する頂点を前記信念空間上の線形関数に逆変換する逆双対変換ステップと、前記逆変換によって得られた線形関数に基づいて、バックアップステップ数に応じて線形関数を更新する線形関数更新ステップとを含み、前記双対変換ステップは、さらに前記バックアップステップ数に応じて更新された線形関数を前記候補集合として、双対空間上の複数の点に変換し、前記制御方策決定方法は、さらに、前記バックアップステップ数の線形関数の更新の後に前記逆変換によって得られた線形関数に基づいて、近似価値関数の複数の線形要素を求める価値関数決定ステップと、前記近似価値関数の複数の線形要素の各々に対して、前記メンバーシップ関数に従って行動を割り当てる方策決定ステップとを含む構成を有している。
【００１８】
この構成によっても、信念空間上の候補集合が双対空間に写像された上で、その凸包を近似する近似凸包の上辺の頂点及びそのメンバーシップ関数が求められるので、価値反復区間（バックアップステップ数）が大きくなった場合にも、近似価値関数を高速に計算して、候補集合の要素に行動を割り当てることができる。
【００１９】
本発明のさらに別の態様は、コンピュータを上記の制御方策決定装置として機能させるための制御方策決定プログラムである。
【発明の効果】
【００２０】
本発明によれば、ＰＯＭＤＰにおける価値反復計算を高速に近似実行することが可能となり、音声認識誤りに対して頑健な音声対話システムにおける対話制御や実世界での自立ロボットや車両制御など状態数が大きな現実の問題へＰＯＭＤＰの枠組みを適用することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施の形態における対話システムの構成を示すブロック図
【図２】本発明の実施の形態における価値関数計算部の構成を示すブロック図
【図３】本発明の実施の形態における候補集合（Ｔ＝１）の例を示すグラフ
【図４】（ａ）本発明の実施の形態における候補集合の例を示すグラフ  （ｂ）本発明の実施の形態における価値関数の例を示すグラフ
【図５】本発明の実施の形態における候補集合（Ｔ＝２）の例を示すグラフ
【図６】本発明の実施の形態における候補集合（Ｔ＝３）の例を示すグラフ
【図７】（ａ）本発明の実施の形態における候補集合（Ｔ＝１）の例を示すグラフ  （ｂ）本発明の実施の形態における双対変換された点集合の例を示すグラフ
【図８】（ａ）本発明の実施の形態における候補集合（Ｔ＝１）の例を示すグラフ  （ｂ）本発明の実施の形態における双対変換された点集合の例を示すグラフ
【図９】本発明の実施の形態における近似凸包の例を示すグラフ
【図１０】（ａ）本発明の実施の形態における近似凸包の例を示すグラフ  （ｂ）本発明の実施の形態における逆双対変換された線形関数の例を示すグラフ
【図１１】（ａ）本発明の実施の形態における候補集合（Ｔ＝２）の例を示すグラフ  （ｂ）本発明の実施の形態における双対変換された点集合の例を示すグラフ
【図１２】（ａ）本発明の実施の形態における候補集合（Ｔ＝３）の例を示すグラフ  （ｂ）本発明の実施の形態における双対変換された点集合の例を示すグラフ
【図１３】（ａ）本発明の実施の形態における候補集合（Ｔ＝２）の例を示すグラフ  （ｂ）本発明の実施の形態における近似凸包の例を示すグラフ
【図１４】（ａ）本発明の実施の形態における候補集合（Ｔ＝３）の例を示すグラフ  （ｂ）本発明の実施の形態における近似凸包の例を示すグラフ
【図１５】本発明の実施の形態における近似価値関数（Ｔ＝３）の例を示すグラフ
【図１６】（ａ）本発明の実施の形態における近似価値関数の例を示すグラフ  （ｂ）本発明の実施の形態における厳密な価値関数の例を示すグラフ
【図１７】本発明の実施の形態における価値関数と最適な行動方策の例を示すグラフ
【図１８】本発明の実施の形態における制御方策決定装置の動作フロー図
【図１９】本発明の実施の形態の変形例における制御方策決定装置の動作フロー図
【発明を実施するための形態】
【００２２】
まず、本発明によって上記のようなＰＯＭＤＰにおける価値関数の学習における課題を解決する原理の概要を説明する。
【００２３】
本発明の一態様では、まず、信念空間上の線形関数の集合を別のユークリッド空間（以下、「双対空間」という。）上の点に対応させる。つまり、信念空間上の線形関数の集合を双対空間における点の集合として扱う。双対空間の次元は状態数に等しい。
【００２４】
次に、双対空間における点の集合に関する凸包を求める。さらに、信念空間上での価値関数の上下関係から定まる双対空間における上下関係に関して、先に求めた凸包の上半面を求める。この上半面上にある点が対応する信念空間上の線形関数が、価値関数の一部となる。よって、双対空間における凸包の上半面上の点を信念空間上の線形関数へ逆変換することで、所望の価値関数を得ることができる。
【００２５】
一般に、高次元空間における凸包を厳密に求めるための計算量は次元数と共に指数関数的に増加する。この課題を解決するために、本発明の一態様では、凸包を求める問題を、点集合を全て含む凸集合の中で体積が最小となるものを求める最小化問題という連続的な問題へと緩和する。そして、本発明の一態様では、この最小化問題の近似解を高速に構成する。この近似解を求める際に、実際の凸包よりも頂点の数を小さくすることもでき、その場合には、より計算量を小さくすることが可能である。
【００２６】
近似的に求められた凸包（近似凸包）の頂点は、一般に、信念空間の線形関数から双対空間に写像された点とは一致しないので、その頂点を信念空間へ逆変換したときに、どのアクションに対応するものとすればよいかが課題となる。そこで、本発明の一態様では、これらの各頂点への信念空間における線形関数から写像された点集合の各点のメンバーシップ関数を定義する。なお、このような写像は１つとは限らないが、その１つを適切な基準で選択する。本発明の一態様において、ある近似凸包の頂点に対応するアクションは、信念空間における線形関数から写像された点集合を同じアクションを持つ部分集合へ分割し、各部分集合の点と対応する頂点へのメンバーシップ関数を足し上げ、その和が最大となる部分集合のアクションとして定義する。
【００２７】
このように近似凸包の各頂点についてアクションを決め、逆変換によって信念空間へ戻し、それらの下半空間の上界を求めることで、価値反復によるＰＯＭＤＰの近似価値関数を構成することができる。
【００２８】
以下、本発明の実施の形態のシステム制御装置について、図面を参照しながら説明する。なお、以下に説明する実施の形態は、本発明を実施する場合の一例を示すものであって、本発明を以下に説明する具体的構成に限定するものではない。本発明の実施にあたっては、実施の形態に応じた具体的構成が適宜採用されてよい。
【００２９】
以下では簡単のために、状態数が２つである場合について説明する。但し、本発明の実施の形態の数式などは、状態が離散的で有限である限り、任意の状態数Ｎの場合にもそのまま適用できる。また、本実施の形態における図も、説明を簡単にするため２状態の場合について説明するが、同様に状態が離散的で有限である限り、任意の状態数について、それらを高次元空間へ拡張したものを考えることが可能である。
【００３０】
本発明の実施の形態を説明する上で、具体的な問題設定は必ずしも必要ではないが、理解を助けるために、例として次のような対話システムの制御を考える。この対話システムにおいて、ユーザは、「食事をしたい」か「買物をしたい」かのどちらかの意図を持っているものとし、そのユーザ意図を音声対話によって判別するものとする。
【００３１】
以下、これらのユーザ意図を「状態」と呼び、「食事をしたい」という状態をｘ1、「買物したい」という状態をｘ2と表す。対話システムからユーザへの意図の問合せに対して、ユーザは、音声によって「食事」あるいは「買物」と発話して応答するものとする。これらの応答を観測量と呼び、「食事」という観測をｏ1、「買物」という観測をｏ2と表す。なお、一般には、Ｍ個の離散的な観測値が得られる。また、状態ｘにおいて、観測量ｏは、確率ｐ（ｏ｜ｘ）に従って得られるものと仮定する。この確率ｐ（ｏ｜ｘ）を知覚モデルと呼ぶ。
【００３２】
図１は、本実施の形態の対話システムの構成を示すブロック図である。図１に示すように、対話システム１００は、音声入力部１０、音声認識部２０、制御方策決定装置３０、及び出力部４０を備えている。音声入力部１０、音声認識部２０、及び出力部４０は、制御方策決定装置３０に対して環境センシング情報を入力し、制御方策決定装置３０が決定した方策に応じた出力を行う環境Ｅである。制御方策決定装置３０の以下に説明する各機能は、演算処理部、メモリ、記憶装置、入力部、出力部等を備えたコンピュータが、所定のプログラムを実行することで実現される。
【００３３】
音声入力部１０は、音声の入力を受けて、それを音声信号に変換する。音声認識部２０は、音声入力部１０で生成された音声信号に対して、音声認識処理を行って音声内容を認識し、認識結果を環境センシング情報として制御方策決定装置３０に入力する。音声入力部１０及び音声認識部２０からなる構成は、環境をセンシングして、環境センシング情報を制御方策決定装置３０に与えるものであり、本発明の「環境センシング情報入力部」に相当する。
【００３４】
制御方策決定装置３０は、音声認識部２０にて認識された音声内容に基づいて、制御方策を決定する。出力部４０は、制御演算部３０で決定された制御方策に基づいて、その方策を実行するための制御コマンドを制御対象に対して出力する。制御方策決定装置３０は、信念計算部３１０、システムモデル部３２０、環境モデル部３３０、価値関数計算部３４０、及び方策決定部３５０を備えている。信念計算部３１０は、初期信念生成部３１１、及び信念更新部３１２を備えている。システムモデル部３２０は、行動モデル部３２１、知覚モデル部３２２、及び方策モデル部３２３からなる。環境モデル部３３０は報酬関数モデル部３３１を備えている。
【００３５】
信念計算部３１１は、初期信念を生成するとともに、信念を更新する。システムモデル部３２０は行動モデル、知覚モデル、及び方策モデルが記憶されている。環境モデル部３３０には、報酬関数モデルが記憶されている。価値関数計算部３４０は、価値関数を算出する。方策決定部３５０は、価値関数計算部３４０で算出された価値関数を用いて、方策モデルに従って制御方策を決定する。
【００３６】
本実施の形態の対話システム１００において、音声認識部２０は、発話を音声認識し、「食事」あるいは「買物」と認識する。一般に、音声認識では誤認識により、ユーザが「食事」と発話したとしても、「買物」と認識されてしまうことが問題となる。つまり、音声認識の結果はユーザの状態を特定するものではなく、ユーザの状態を反映したある確率的現象を観測したものにすぎないとみなすことができる。これが制御方策決定装置３０において確率的な知覚モデルｐ（ｏ｜ｘ）を扱う理由である。なお、知覚モデルは、知覚モデル部３２２に記憶されている。
【００３７】
この知覚モデルの確率的な性質により、たとえシステムが観測を行ったとしても、ユーザの状態は確率的にしか把握できないことになる。そこで、状態がｘ1である確率をｐ1＝ｐ（ｘ1）、状態がｘ2である確率をｐ2＝ｐ（ｘ2）とおき、これらの確率の組ｂ＝（ｐ1，ｐ2）を信念と呼ぶ。但し、ｐ1＋ｐ2＝１である。可能なｐ1，ｐ2の値全体を信念空間とよぶ。すなわち、本システムの場合、（ｐ1，ｐ2）という［０，１］×［０，１］の正方領域内のｐ1＋ｐ2＝１を満たす直線上が信念空間となる。
【００３８】
このように、システムの状態は、ｘ1かあるいはｘ2か確定的に定められない代わりに、信念ｂによって、拡張された意味でシステムの状態が与えられると考えることができる。従来の状態空間がｘ1とｘ2の２状態で与えられるのは、信念空間が（１，０）と（０，１）のみからなる場合とみなすことができる。その意味で、以下、信念も状態と呼ぶことがある。
【００３９】
対話システム１００は、信念の値に応じて、「食事に関する情報を提示する」か、あるいは、「買物に関する情報を提示する」か、あるいは、ユーザに対してもう一度「聞き直す」かの処理を実行することができるものとする。以下、これらのシステムの処理を特に「行動」と呼び、「食事に関する情報を提示する」という行動をｕ1、「買物に関する情報を提示する」という行動をｕ2、「聞き直す」という行動をｕ3と表す。なお、一般には、Ｌ個の離散的な行動をとることができる。方策決定部３５０は、これらのいずれの行動をとるかを決定する。
【００４０】
一般に、行動は「聞き直す」という行動のように、「状態に関する観測を行う行動」と、行動ｕ1、ｕ2のように「最終決定を行う行動」という２つの大きな行動のカテゴリへ分類することができる。「最終決定を行う行動」カテゴリに属する行動が選択された場合、そこでシステム制御の問題は一旦、完了となる。システム制御の問題は、「状態に関する観測を行う行動」カテゴリに属する行動が選択されている限り、「最終決定を行う行動」カテゴリに属する行動が選択されるまで継続する。
【００４１】
以下、状態ｘにおいて、行動ｕを実行したときに、状態はｘ´へ確率ｐ（ｘ´｜ｘ，ｕ）に従って遷移するものと仮定する。この確率ｐ（ｘ´｜ｘ，ｕ）を行動モデルと呼ぶ。この行動モデルが、行動モデル部３２１に記憶されている。以下、「最終決定を行う行動」カテゴリに属する行動ｕ*が選択された場合は、任意の状態ｘ、ｘ´について、ｐ（ｘ´｜ｘ，ｕ*）＝０であるとする。なお、この場合には、厳密にはｐは確率とは解釈できないが、便宜的にそのように定義する。
【００４２】
また、状態ｘにおいて、行動ｕを実行したとき、システムは報酬ｒ（ｘ，ｕ）を受け取るものとする。この報酬モデルｒ（ｘ，ｕ）が環境モデル部３３０の報酬関数モデル部３３１に記憶されている。信念がｂである状態からＴステップ先の将来までに受け取る報酬の和の期待値の最大値をその状態の価値関数と呼び、Ｖr（ｂ）と表す。また、その価値関数を得るために、信念がｂであるときに取るべき行動を最適方策と呼び、πT（ｂ）と表す。
【００４３】
但し、報酬の和の期待値を計算する際に、一般には、将来得られる報酬については、割引率γ（０＜γ≦１）をバックアップステップ数だけ冪乗した重み付けをして（すなわち、τステップ後に得られる報酬に関しては、γτを乗じて）、期待値を取る。この最適方策πT（ｂ）は、方策モデルとして方策モデル部３２３に記憶されている。
【００４４】
以上のように、状態が観測によって確率的にしか推定されない状況で、現在得られている信念の値に基づいてその時点での最適なシステムの行動を選択すること、すなわち、最適な方策を決定することが、ＰＯＭＤＰを対話システム制御へ適用する際の基本的な問題設定である。
【００４５】
このような問題設定において、最適な方策は各状態ｘiにおける価値関数を最大化するものとして決定される。従って、その価値関数を求めることができれば、ＰＯＭＤＰによる対話制御ができる。システム制御部の価値関数計算部３４０は、この価値関数を求める。以下では、本実施の形態の価値関数計算部３４０が、価値反復手法による価値関数を求める方法を説明する。
【００４６】
図２は、価値関数計算部３４０の構成を示すブロック図である。価値関数計算部３４０は、初期線形関数生成部１、双対変換部２、双対価値反復処理部３、逆双対変換部４、価値関数決定部５、及び線形関数更新部６を備えている。双対価値反復処理部３は、ラベル付凸包近似計算部３１及び枝刈り部３５からなる。ラベル付凸包近似計算部３１は、ＣｏｎｖｅｘＮＭＦ計算部３３からなる凸包近似計算部３２と、メンバーシップ決定部３４とからなる。
【００４７】
まず、本実施の形態のように、状態数が離散的で有限である場合、ＰＯＭＤＰの価値関数は、信念空間上の区分線形関数として表現されることが理論的に示される（非特許文献１参照）。また、この区分線形関数は一般に下に凸であることも理論的に示すことができる。価値関数計算部３４０は、この区分線形関数が下に凸であるという性質を利用して価値関数を計算する。以下、具体的に説明する。
【００４８】
各区分を与える線形関数（以下、「線形要素」ともいう。）を式（１）のようにおく。なお、以下では、一般的に状態数をＮ、観測値数をＭ、行動数をＬとする。本実施の形態では、Ｎ＝２、Ｍ＝２、Ｌ＝３である。
【数１】
2014179064.tif 000003
線形関数φν（ｂ）は、その係数ベクトル
【数２】
2014179064.tif 000004
と同一視することができる。
【００４９】
（初期線形関数生成処理）
初期線形関数生成部１は、まず、バックアップステップ数をＴ＝１として、このときの価値関数の線形要素を与える線形関数の組を初期化する線形関数を計算する。具体的には、初期線形関数生成部１は、各行動ｕl（ｌ＝１，２，・・・，Ｌ）について、各状態ｘnのときに得られる報酬関数γから式（２）を計算する。
【数３】
2014179064.tif 000005
【００５０】
初期線形関数生成部１は、このようにして得られる初期線形関数の組によって、式（３）により価値関数の線形要素となる候補集合Γ(1)を取得する。
【数４】
2014179064.tif 000006
図３は、この候補集合Γ(1)の例を示すグラフである。図３のグラフでは、横軸に信念空間、縦軸に信念価値をとっている。なお、図３は、Ｌ＝６の場合の候補集合Γ(1)を示している。図３における線は、それぞれ初期線形関数を表しており、Ｌ＝６であるので、線形関数も６本となっている。
【００５１】
ここで、価値関数Ｖ1（ｂ）は、この候補集合Γ(1)から式（４）によって与えられる。
【数５】
2014179064.tif 000007
図４の左側は、ある候補集合Γ(1)の例を示すグラフであり、図４の右側は、当該候補集合Γ(1)から得られる価値関数Ｖ1（ｂ）を示すグラフである。価値関数Ｖ1（ｂ）の値は、信念価値とも呼ばれる。
【００５２】
図４に示すように、候補集合Γ(1)の全ての要素が価値関数Ｖ1（ｂ）の線形要素となる訳ではない。実際には、そのごく一部が寄与するのみである。図４の左のグラフの実線で示した要素のみが価値関数Ｖ1（ｂ）の線形要素となる。図４の右のグラフでは、この価値関数Ｖ1（ｂ）の線形要素として貢献する要素のみを示している。このように、候補集合Γ(1)から価値関数Ｖ1（ｂ）の線形要素とならない要素を排除することを枝刈りと呼ぶ。
【００５３】
図５は、図３の例において、バックアップステップ数Ｔ＝２となった場合の候補集合Γ(1)を示すグラフであり、図６は、図３の例において、バックアップステップ数Ｔ＝３となった場合の候補集合Γ(1)を示すグラフである。図５及び図６に例示するように、一般にこの枝刈り処理は、バックアップステップ数（価値反復区間ともいう。）の増加に対して候補集合の要素数が指数関数的に増加することから、計算量が極めて多くなり、計算負荷が増大し、計算時間も長くなる。このことがＰＯＭＤＰにおける価値反復による価値関数の計算方法の問題となっている。
【００５４】
そこで、本実施の形態では、その枝刈りの問題を解決するために、厳密に候補集合Γ(1)から価値関数Ｖ1（ｂ）の線形要素となるものを選ぶのではなく、価値関数Ｖ1（ｂ）の線形要素を近似する線形関数を計算する。
【００５５】
（双対変換）
このために、まず、双対変換部２は、候補集合Γ(1)の要素
【数６】
2014179064.tif 000008
を、以下のようにして、あるＮ次元空間の点と対応させる。係数（ν(1)）nをＮ次元空間での点の座標値とみなすことで、線形関数
【数７】
2014179064.tif 000009
から、Ｎ次元空間の点
【数８】
2014179064.tif 000010
への写像を定義できる。これを双対変換といい、その写像先のＮ次元空間を双対空間という。
【００５６】
図７は、双対変換の例を示すグラフである。図７の例において、線形関数１０１〜１０６は、双対空間の点２０１〜２０６にそれぞれ写像されている。なお、ここで示した双対変換は、例の１つに過ぎず、ここで説明したものに限定されない。また、候補集合Γ(1)の要素を双対空間へ写像した点からなる集合をΓ´(1)と表すことにする。
【００５７】
（凸包と価値関数）
信念空間上の線形関数の上下関係は、双対空間においても保存する。すなわち、図８に示すように、価値関数が下に凸な区分線形関数で与えられるという性質により、価値関数を与える線形要素は、双対空間へ写像した候補集合の点集合Γ´(1)に対する凸包の上辺となる。従って、候補集合Γ(1)から価値関数の線形要素を求める問題は、双対空間の点集合Γ´(1)に対する凸包の上辺を求める問題に帰着する。
【００５８】
状態数Ｎ＝２である場合には、双対空間は２次元であり、その場合凸包を求めるアルゴリズムは本質的にソートの問題となり、それは高速な処理アルゴリズムが知られている。例えば、Ｋｉｒｋｐａｔｒｉｃｋ−Ｓｅｉｄｅｌのクイック凸包アルゴリズムが利用できる。よって、双対空間へ問題を写像することで、高速に価値関数を計算することができることになる。つまり、この処理により状態数Ｎ＝２である場合には、ＰＯＭＤＰの価値反復による価値関数計算の困難を解決できる。
【００５９】
しかし、状態数Ｎ＝３以上の空間では、これまで知られている最善のアルゴリズムを用いても、凸包を求めるための計算量は次元数に関して指数関数的に増加することが知られている。そのため、双対空間における凸包計算問題へ写像しただけでは、ＰＯＭＤＰの価値反復による価値関数計算の困難を簡単には解決することはできない。
【００６０】
さらに考慮すべきことは、空間の次元Ｎが高くなるに連れて、凸包の頂点数は点集合Γ´(1)の点の数に比例して増大するということである。つまり、価値関数は非常に多くの区分に細分化されたものになるということである。厳密にはそうであったとしても、逆に隣り合った区分での違いは小さくなり、滑らかな関数へ変わっていく。実用的には、そのような滑らかな関数よりも、それを良く近似する少ない区分での区分線形関数で近似するほうが望ましい。
【００６１】
（ＮＭＦによる凸包の近似計算）
以上のような理由により、本実施の形態では価値関数計算部３４０の双対価値反復処理部３が凸包近似計算部３２を備えている。凸包近似計算部３２は、凸包を厳密に求めるのではなく、非負値行列因子分解（Non-negative Matrix Factorization：ＮＭＦ）によって、それをよく近似するポリトープを求める。以下、このようなポリトープを簡単のため「近似凸包」という。このように近似凸包を考えるということは、離散的な点集合Γ´(1)に対してその凸包と求めるという離散組合せ問題を、連続なＮ次元空間全体の中で、点集合Γ´(1)の凸包を良く近似するポリトープを計算するという問題へと緩和することを意味する。
【００６２】
いま、点集合Γ´(1)の要素数が｜Γ´(1)｜個あるとして、それらを並べたＮ×｜Γ´(1)｜行列を式（５）のようにおく。
【数９】
2014179064.tif 000011
ここで、φr´(1)は、縦ベクトルであるとする。点集合Γ´(1)の凸包の頂点数は不明であるが、ここではその頂点数がＫで与えられるものと仮定する。換言すれば、ここでは、十分高速に計算できる計算量となるように頂点数Ｋを抑えて、その上で凸包を最もよく近似するようなポリトープを求めるという問題を考える。
【００６３】
いま、この求めるポリトープの頂点をｗk(1)（ｋ＝１，２，・・・，Ｋ）とおく。これらはＮ次元ベクトルであり、このポリトープが点集合Γ´(1)を包含するという条件は、式（６）及び式（７）で与えられる。
【数１０】
2014179064.tif 000012
【数１１】
2014179064.tif 000013
【００６４】
ここで、ｈr(1)は、Ｋ次元ベクトルであり、式（８）が成り立つ。
【数１２】
2014179064.tif 000014
また、Ｗ(1)はＮ×Ｋ行列、Ｈ(1)はＫ×｜Γ´(1)｜行列であり、以下の式（９）及び式（１０）が成り立つ。
【数１３】
2014179064.tif 000015
【数１４】
2014179064.tif 000016
【００６５】
さらに、このポリトープの頂点数が実際の凸包の頂点数と等しいときに、凸包と一致するようにするために、ポリトープの頂点ｗk(1)が、点集合Γ´(1)の要素によって表されるということを要請する。すなわち、式（１１）及び式（１２）の通りとする。
【数１５】
2014179064.tif 000017
【数１６】
2014179064.tif 000018
ただし、ｇk(1)は｜Γ´(1)｜次元ベクトルであり、式（１３）を満足する。
【数１７】
2014179064.tif 000019
また、Ｇ(1)は｜Γ´(1)｜×Ｋ行列であり、式（１４）の通りである。
【数１８】
2014179064.tif 000020
式（６）、式（７）、式（１１）、式（１２）から、下記の式（１５）、式（１６）という自己無撞着な因子分解問題が得られる。
【数１９】
2014179064.tif 000021
【数２０】
2014179064.tif 000022
【００６６】
この問題を解くアルゴリズムは、例えば非特許文献２に与えられている。この文献にある方法によれば、実際には式（１５）、式（１６）の問題を解く際に、まずある２次元空間への射影を取り、その２次元空間内で凸包を求め、それを元の空間へ戻すという操作を繰り返す。この手法によれば点集合Γ´(1)のサイズ｜Γ´(1)｜が増加しても高速に計算することが可能である。
【００６７】
式（１５）、式（１６）を解くことによって、近似凸包の頂点Ｗ(1)＝Ｖ(1)Ｇ(1)が求まる。図９は、近似凸包の計算例を示すグラフである。図９の例では、Ｋ＝５としている。図中、破線はもとの凸包であり、実線はそれを近似した近似凸包である。
【００６８】
（メンバーシップ関数の定義）
候補集合Γ(1)の各要素φには、それぞれある行動ｕが割り当てられている。要素φがどの行動ｕに割り当てられているかをメンバーシップという。これを一般化し、要素φの行動ｕlへの寄与の割合をαl（φ）∈［０，１］で表し、α（φ）＝（α1（φ），α2（φ），・・・αL（φ））をメンバーシップ関数と呼ぶ。
【００６９】
メンバーシップ決定部３４は、近似凸包の頂点ｗk(1)のメンバーシップを決定する。双対集合Γ´(1)の要素φ´のメンバーシップは、対応する候補集合Γ(1)の要素φのメンバーシップによって与えられる。すなわち、候補集合Γ(1)の要素φが行動ｕlに対応する場合、要素φ´(1)のメンバーシップは、式（１７）により与えられる。
【数２１】
2014179064.tif 000023
以下、簡単のために、αl´（φl´(1)）＝δll´と表記する。
【００７０】
点集合Γ´(1)上の制限を外して近似を行ったことで、得られた近似凸包の頂点ｗk(1)のメンバーシップが非自明となる。そこで、メンバーシップ決定部３４は、頂点ｗk(1)が点集合Γ´(1)の各要素とどのように結びついているかという重みで足しあげることで頂点ｗk(1)のメンバーシップを決定する。換言すれば、近似凸包の頂点ｗk(1)のメンバーシップ関数は、それを点集合Γ´(1)の各要素に適用した場合に正しいメンバーシップが得られる関数である。このようにしてメンバーシップを決定することで、近似凸包が厳密に点集合Γ´(1)の凸包に一致する場合には、正しいメンバーシップに帰着するものと期待できる。
【００７１】
具体的には、メンバーシップ決定部３４は、頂点ｗk(1)に対するメンバーシップ関数を下式（１８）によって求める。
【数２２】
2014179064.tif 000024
式（１８）に示すように、メンバーシップ決定部３４は、点集合Γ´(1)の各要素を近似凸包に変換する変換行列Ｇでもって、点集合Γ´(1)の各要素のメンバーシップを変換したものを、近似凸包の頂点のメンバーシップとして決定する。
【００７２】
頂点ｗk(1)に対応する行動
【数２３】
2014179064.tif 000025
は、下式（１９）で決定する。
【数２４】
2014179064.tif 000026
【００７３】
（近似凸包の上辺）
上記のようにしてラベル付凸包近似計算部３１で、近似凸包の頂点ｗk(1)とそのメンバーシップが求まると、枝刈り部３５の凸包上辺抽出部３６は、近似凸包からその上辺を取り出すことで、近似価値関数に対応する関数を取得する。
【００７４】
この凸包上辺の抽出においては、Ｎ次元空間の座標
【数２５】
2014179064.tif 000027
に対して、その方向余弦
【数２６】
2014179064.tif 000028
を考える。
【００７５】
凸包の上辺の抽出においては、双対空間内のある凸包と双対空間内の先の方向余弦と平行な原点から延びる半直線と凸包との交点のうち、原点からの距離が最も大きい点のみを残し、このようにして残された点からなる集合を、双対空間における凸包の上辺として抽出できる。この双対集合Γ´(1)の凸包の上辺の頂点は、価値関数に対応する線形関数を与える。
【００７６】
近似凸包に対しても同様に、上辺を定義し、近似凸包の頂点ｗk(1)（ｋ＝１，２，・・・，Ｋ）のうち、上辺に属するものを
【数２７】
2014179064.tif 000029
とおく。ここで、Ｋ≦Ｊ、かつ１≦ｋs≠ｋt≦Ｋ（ｓ≠ｔ）である。
【００７７】
（近似結果の逆変換と価値関数）
逆双対変換部４は、近似凸包の上辺に属する頂点
【数２８】
2014179064.tif 000030
を逆双対変換によって、信念空間上の線形関数へ戻す。逆双対変換部４は、近似凸包の上辺に属する頂点
【数２９】
2014179064.tif 000031
を用いて、信念空間上の線形関数を式（２０）によって求める。
【数３０】
2014179064.tif 000032
【００７８】
図１０は、逆双対変換の例を示すグラフである。図１０の左のグラフにおいて、近似凸包の上辺に属する頂点２１１、２１２、２１３、２１４が、それぞれ図１０の右のグラフの信念空間上の線形関数１１１、１１２、１１３、１１４に変換されている。
【００７９】
価値関数決定部５は、これらの線形関数に基づいて、式（２１）によって近似価値関数
【数３１】
2014179064.tif 000033
の区分線形要素を求める。
【数３２】
2014179064.tif 000034
【００８０】
以上の処理によって、価値関数計算部３４０は、バックアップステップ数Ｔ＝１での近似価値関数を求めることができる。なお、仮に凸包を近似ではなく、厳密に求めていた場合には、厳密な価値関数Ｖ1（ｂ）が得られることになる。
【００８１】
（観測による信念更新）
以上の説明では、価値関数計算部３４０は、すぐに得られる報酬のみを使って価値関数を計算した。しかし、将来に得られる報酬を考慮することで、一般に、よりよい価値関数を得ることができるようになる。
【００８２】
このことは、「最終決定を行う行動」カテゴリに属する行動を選択する前に、「状態に関する観測を行う行動」カテゴリに属する行動を選択すること、すなわち、次の行動の前に観測を行って、信念の状態を更新することができることを意味する。この観測によって、信念の値をより正しく認識することができるため、最終的に得られる報酬の和の期待値が向上する。
【００８３】
まず、信念がｂ＝（ｐ1，ｐ2，・・・，ｐN）であったとする。ここで行動ｕを実行することで、別の信念状態へ遷移するものとする。そこで更に観測を実行し、観測値ｏが得られたとすると、信念に関する事後分布が式（２２）によって得られる。
【数３３】
2014179064.tif 000035
【００８４】
この信念の事後分布に関する最適な行動方策は、価値関数
【数３４】
2014179064.tif 000036
で与えられる。
【００８５】
そこで、線形関数更新部６は、将来に得られる報酬の和の期待値を向上させるため線形関数を更新する。具体的には、線形関数更新部６は、候補集合Γ(1)の要素を式（２３）によって更新する。
【数３５】
2014179064.tif 000037
更新された候補集合は、双対変換部２に出力されて、上記と同様の処理によって、バックアップステップ数Ｔ＝２の価値関数を求める。
【００８６】
式（２２）より、バックアップステップ数Ｔ＝２での価値関数Ｖ2（ｂ）は、式（２４）で算出される。
【数３６】
2014179064.tif 000038
【００８７】
式（２４）は、以下の式（２５）、式（２６）のように書き直すことができる。
【数３７】
2014179064.tif 000039
【数３８】
2014179064.tif 000040
ここで、
【数３９】
2014179064.tif 000041
と略記した。
【００８８】
価値関数計算部３４０は、式（２７）の候補集合Γ(2)の線形関数の集合から、式（２８）によって価値関数Ｖ2（ｂ）を算出する。
【数４０】
2014179064.tif 000042
【数４１】
2014179064.tif 000043
【００８９】
また、メンバーシップ決定部３４は、要素
【数４２】
2014179064.tif 000044
のメンバーシップを、式（２９）で求める。
【数４３】
2014179064.tif 000045
【００９０】
候補集合Γ(1)から近似価値関数
【数４４】
2014179064.tif 000046
の線形要素
【数４５】
2014179064.tif 000047
を求めたのと同じ手順を繰り返すことで、候補集合Γ(2)から価値関数Ｖ2（ｂ）あるいはその近似関数
【数４６】
2014179064.tif 000048
の線形要素
【数４７】
2014179064.tif 000049
を求めることができる。
【００９１】
さらに、バックアップステップを増やすことにより、線形要素
【数４８】
2014179064.tif 000050
から候補集合Γ(2)を生成したのを同じ手順を繰り返すことにより、線形要素
【数４９】
2014179064.tif 000051
から候補集合Γ(3)を生成することができる。
【００９２】
このように、任意の価値反復区間Ｔについて、バックアップステップを行った価値関数ＶT（ｂ）あるいはその近似関数
【数５０】
2014179064.tif 000052
を計算することができる。価値関数計算部３４０は、上記のようにして、価値関数ＶT（ｂ）及びその近似関数
【数５１】
2014179064.tif 000053
を計算する。
【００９３】
方策決定部３５０は、各線形要素に対して、行動
【数５２】
2014179064.tif 000054
を割り当てる。
【００９４】
図１１及び図１２は、バックアップステップＴ＝２、Ｔ＝３における候補集合Γ(2)、Γ(3)とその双対変換の例を示すグラフである。図１１の例において、線形関数１２１〜１２４は、双対空間の点２２１〜２２４にそれぞれ写像されている。
【００９５】
図１３及び図１４は、バックアップステップＴ＝２、Ｔ＝３における近似凸包計算の例を示すグラフである。図１５は、バックアップステップＴ＝３まで行ったときの近似価値関数の例を示すグラフである。図１６（ａ）は、近似価値関数の例を示すグラフであり、図１６（ｂ）は、厳密な価値関数の例を示すグラフである。図１６（ａ）と図１６（ｂ）を比較して分かるように、厳密な価値関数と近似の価値関数との差は小さく、本実施の形態の計算方法が有効であることが分かる。
【００９６】
信念空間上の点ｂにおいて価値関数を与える線形関数の重み係数は、式（３０）によって与えられる。
【数５３】
2014179064.tif 000055
方策決定部３５０は、その線形関数のメンバーシップから式（３１）によって最適方策を決定する。
【数５４】
2014179064.tif 000056
【００９７】
図１７は、本実施の形態における価値関数と最適な行動方策の例を示すグラフである。図１７に示すように、対話システム１００は、価値関数に従って、信念空間が０〜３．２であれば、「食事に関する情報を提示する」という行動を実行する制御コマンドを出力し、信念空間が０．３２〜８．２であれば、「聞き直す」という行動を実行し、信念空間が８．２〜１であれば、「買物に関する情報を提示する」という行動を実行する制御コマンドを出力する。
【００９８】
次に、制御方策決定装置３０の動作を説明する。図１８は、制御方策決定装置３０の動作フロー図である。価値関数計算部３４０は、知覚モデル部３２２、行動モデル部３２１、報酬関数モデル部３３１からそれぞれ知覚モデル、行動モデル、報酬関数をロードする（ステップＳ１１）。次に、バックアップステップ数をＴ＝１として（ステップＳ１２）、初期線形関数生成部１が初期線形関数の組を生成する（ステップＳ１３）。そして、Ｔが上限（Ｔmax）に達していないかを判断して（ステップＳ１４）、達していない場合には（ステップＳ１４にてＮＯ）、双対変換部２が、線形関数の組を双対変換する（ステップＳ１５）。
【００９９】
次に、凸包近似計算部３２が、双対変換によって得られた複数の点の近似凸包を計算する（ステップＳ１６）。そして、メンバーシップ決定部１４は、近似凸包の頂点のメンバーシップを計算し（ステップＳ１７）、凸包上辺抽出部３６が近似凸包の上辺を抽出する（ステップＳ１８）。近似凸包の上辺が抽出されると、逆双対変換部４は、近似凸包の上辺の頂点について逆双対変換を行う（ステップＳ１９）。そして、価値関数決定部５は、逆双対変換によって得られた価値関数の線形要素をもって、線形関数の組を更新する（ステップＳ２０）。
【０１００】
その後、バックアップステップ数Ｔをインクリメントし（ステップＳ２１）、再びバックアップステップ数が上限（Ｔmax）を超えていないかを判断する（ステップＳ１４）。このようにして、バックアップステップ数が上限を超えるまでステップＳ１５〜ステップＳ２１を繰り返し、バックアップステップ数が上限を超えると（ステップＳ１４にてＹＥＳ）、価値関数計算部３４０は、そのときに得られている、価値関数を与える線形関数の組を出力する（ステップＳ２２）。このときの価値関数は、上述の近似価値関数である。方策決定部３５０は、この近似価値関数を用いて、最適方策を決定する。
【０１０１】
なお上記の実施の形態では、バックアップステップ数が２以上のとき、線形要素の候補集合の更新を式（２６）のように観測値すべてについて一度に行ったが、変形例として、式（２５）の最大化処理を、観測値ごとに逐次的に実行してもよい。すなわち、線形要素の候補集合の更新は、観測値ごとに逐次的に実行し、その部分的に更新された線形関数組について枝刈り処理を行いながら全ての観測値に関する線形要素の候補集合の更新処理を実行してもよい。
【０１０２】
この変形例における制御方策決定装置３０の動作を説明する。図１９は、変形例の制御方策決定装置３０の動作フロー図である。価値関数計算部３４０は、知覚モデル部３２２、行動モデル部３２１、報酬関数モデル部３３１からそれぞれ知覚モデル、行動モデル、報酬関数をロードする（ステップＳ３１）。次に、バックアップステップ数をＴ＝１として（ステップＳ３２）、初期線形関数生成部１が初期線形関数の組を生成する（ステップＳ３３）。そして、双対変換部２が、初期線形関数の組を双対変換する（ステップＳ３４）。
【０１０３】
次に、凸包近似計算部３２が、双対変換によって得られた複数の点の近似凸包を計算する（ステップＳ３５）。そして、メンバーシップ決定部１４は、近似凸包の頂点のメンバーシップを計算し（ステップＳ３６）、凸包上辺抽出部３６が近似凸包の上辺を抽出する（ステップＳ３７）。近似凸包の上辺が抽出されると、逆双対変換部４は、近似凸包の上辺の頂点について逆双対変換を行う（ステップＳ３８）。以上の処理によって、バックアップステップ数Ｔ＝１の価値関数が求まる。
【０１０４】
その後、バックアップステップ数Ｔをインクリメントし（ステップＳ３９）、バックアップステップ数Ｔが上限（Ｔmax）を超えていないかを判断する（ステップＳ４０）。Ｔが上限（Ｔmax）に達していない場合には（ステップＳ４０にてＮＯ）、観測値ｍを１とする（ステップＳ４１）。そして、線形関数更新部６が、観測値ｍに関する線形関数組を更新する（ステップＳ４２）。
【０１０５】
次に、双対変換部２が、線形関数の組を双対変換し（ステップＳ４３）、凸包近似計算部３２が、双対変換によって得られた複数の点の近似凸包を計算し（ステップＳ４４）、メンバーシップ決定部１４が、近似凸包の頂点のメンバーシップを計算し（ステップＳ４５）、凸包上辺抽出部３６が、近似凸包の上辺を抽出し（ステップＳ４６）、逆双対変換部４が、近似凸包の上辺の頂点について逆双対変換を行うことで（ステップＳ４７）、価値関数を取得する。そして、観測値ｍをインクリメントして（ステップＳ４８）、ｍが観測値数Ｍを超えているかを判断し（ステップＳ４９）、超えていない場合には（ステップＳ４９にてＮＯ）、ステップＳ４２に戻って、ステップＳ４２〜Ｓ４９の処理を繰り返す。
【０１０６】
インクリメントされた観測値ｍが観測値数Ｍを超えている場合（ステップＳ４９にてＹＥＳ）、すなわち、すべての観測値について線形関数組を更新して価値関数を算出した場合には、ステップＳ３９に戻ってバックアップステップ数Ｔをインクリメントして、バックアップステップ数Ｔが上限（Ｔmax）を超えていないかを判断する。このようにして、バックアップステップ数が上限を超えるまでステップＳ３９〜ステップＳ４９を繰り返し、バックアップステップ数が上限を超えると（ステップＳ４０にてＹＥＳ）、価値関数計算部３４０は、そのときに得られている、価値関数を与える線形関数の組を出力する（ステップＳ５０）。このときの価値関数は、上述の近似価値関数である。方策決定部３５０は、この近似価値関数を用いて、最適方策を決定する。
【０１０７】
以上、対話システムの制御を事例として実施形態を説明してきたが、本発明の制御方策決定装置の応用は、このような対話システムの制御に制限されるものではない。
【産業上の利用可能性】
【０１０８】
本発明は、価値反復計算を高速に近似実行することが可能となるという効果を有し、環境センシング情報に基づいて制御方策を決定する制御方策決定装置等として有用である。
【符号の説明】
【０１０９】
１  初期線形関数生成部
２  双対変換部
３  双対価値反復処理部
４  逆双対変換部
５  価値関数決定部
６  線形関数更新部
１０  音声入力部
２０  音声認識部
３０  制御方策決定装置
３１  ラベル付凸包近似計算部
３２  凸包近似計算部
３３  ＣｏｎｖｅｘＮＭＦ計算部
３４  メンバーシップ決定部
３５  枝刈り部
３６  凸包上辺抽出部
４０  出力部
１００  対話システム
【図１】
2014179064.tif 000057
【図２】
2014179064.tif 000058
【図３】
2014179064.tif 000059
【図４】
2014179064.tif 000060
【図５】
2014179064.tif 000061
【図６】
2014179064.tif 000062
【図７】
2014179064.tif 000063
【図８】
2014179064.tif 000064
【図９】
2014179064.tif 000065
【図１０】
2014179064.tif 000066
【図１１】
2014179064.tif 000067
【図１２】
2014179064.tif 000068
【図１３】
2014179064.tif 000069
【図１４】
2014179064.tif 000070
【図１５】
2014179064.tif 000071
【図１６】
2014179064.tif 000072
【図１７】
2014179064.tif 000073
【図１８】
2014179064.tif 000074
【図１９】
2014179064.tif 000075