JP2015176329A - 生成装置、生成方法、情報処理方法、及び、プログラム - Google Patents

Abstract

【課題】観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルにおける最適施策を高速に算出することを課題とする。
【解決手段】観測可能な可視状態、及び、観測不能な隠れ状態を備え、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルについて、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に生成する生成装置であって、隠れ状態毎に累積利得の成分を含む利得ベクトルのうち利得ベクトルの集合に含めるベクトルを選択するために用いる選択用の隠れ状態の確率分布を設定する設定部と、選択用の確率分布について累積期待利得の最大値を与える利得ベクトルを優先して利得ベクトルの集合に含める選択部とを備える生成装置を提供する。
【選択図】図１

Description

本発明は、生成方法、選択方法、及び、プログラムに関する。

観測可能でない状態を含む環境における逐次的意思決定は部分観測マルコフ決定過程（ＰＯＭＤＰ）として定式化されていた（特許文献１〜３）。しかし、意思決定問題の中には、状態の観測可能性や不変性が定まっている場合、例えば、状態の一部が完全に観測可能で残りが観測不可能な場合がある。また、観測不可能な部分が不変である場合がある。従来は、このような場合においても汎用のＰＯＭＤＰソルバにより最適施策を算出していた。
［特許文献１］特開２０１１−５３７３５号公報
［特許文献２］特開２０１２−１２３５２９号公報
［特許文献３］特開２０１２−１９００６２号公報

完全に観測可能な可視状態、及び、観測不可能な隠れ状態を備える遷移モデルにおける最適施策を高速に算出することを課題とする。

本発明の第１の態様においては、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルについて、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に生成する生成装置であって、隠れ状態毎に累積利得の成分を含む利得ベクトルのうち利得ベクトルの集合に含めるベクトルを選択するために用いる選択用の隠れ状態の確率分布を設定する設定部と、選択用の確率分布について累積期待利得の最大値を与える利得ベクトルを優先して利得ベクトルの集合に含める選択部とを備える生成装置、生成装置を用いた生成方法、及び、プログラムを提供する。

本発明の第２の態様においては、利得ベクトルの集合を生成する生成装置と、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルにおいて最適な入力を選択する選択装置であって、生成装置が生成した利得ベクトルの集合を取得する取得部、現在の可視状態に応じた利得ベクトルの中から、現時点における隠れ状態の確率分布に対し累積期待利得を最大化する利得ベクトルを選択する利得選択部、及び、選択した利得ベクトルに対応する入力を、最適な入力として選択する入力選択部を備える選択装置とを備える情報処理システムを提供する。

なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではない。また、これらの特徴群のサブコンビネーションもまた、発明となりうる。

本実施形態の情報処理システムの概要を示す。 本実施形態に係る可視状態ｓ及び隠れ状態ｂの一例を示す。 本実施形態の生成装置１０の処理フローを示す。 本実施形態における生成部１４０による集合Λ_ｎ（ｓ）の生成方法の一例を示す。 図３における処理フローの具体的アルゴリズムの一例を示す。 本実施形態における集合Λ_ｓ，ｎと累積期待利得の関係を示す。 図３における処理フローの具体的アルゴリズムの別の一例を示す。 本実施形態の選択装置２０の処理フローを示す。 本実施形態の変形例に係る情報処理システムの概要を示す。 本変形例の生成装置３０の処理フローの一例を示す。 図１０における処理フローの具体的アルゴリズムの一例を示す。 本変形例における集合Λ_ｓ，ｎと累積期待利得の関係を示す。 本実施形態の本変形例の処理フローの別の一例を示す。 コンピュータ１９００のハードウェア構成の一例を示す。

以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。

図１は、本実施形態の情報処理システムを示す。本実施形態の情報処理システムは、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力及び／又は隠れ状態に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルを定式化した利得ベクトルの集合を生成し、利得ベクトルの集合に基づいて最適な入力を選択する。

例えば、消費者が特定の商品（例えば、家電製品）のテレビＣＭを視聴した後の状態か、及び、消費者が特定の商品に興味を持った状態かは観測不能な隠れ状態となるが、消費者が特定の商品のＷｅｂ広告を閲覧した状態であるかはクッキー等により観測可能な可視状態である。

本実施形態の情報処理システムは、このような遷移モデルを定式化し、消費者から得られる期待利得（例えば、売り上げ）を最大化するための入力（例えば、テレビＣＭ、ダイレクトメール、及び、Ｅメール等）を選択する。本実施形態の情報処理システムは、利得ベクトルの集合を生成する生成装置１０と、利得ベクトルの集合に従って最適な入力を選択する選択装置２０を有する。

生成装置１０は、学習用データに基づいて基準時点以降で予め定められた将来の時点までの各時点の期待利得を累積した累積期待利得の成分を隠れ成分毎に含み、累積期待利得の算出に用いることができる利得ベクトルの集合を可視状態毎に生成する。生成装置１０は、一例として、コンピュータ上でソフトウェアを実行することにより実現される。生成装置１０は、入力部１１０、算出部１２０、初期化部１３０、及び、生成部１４０を備える。

入力部１１０は、外部のデータベース１０００等の記憶装置又は生成装置１０の内部から利得ベクトルの集合を生成するための学習用データを入力する。入力部１１０は、学習用データを算出部１２０に提供する。学習用データは、例えば、消費者の購買履歴及び行動履歴等であってよい。

算出部１２０は、学習用データから各可視状態からの遷移確率を表す状態遷移確率、及び、各可視状態において入力に応じて期待される利得である期待利得を算出する。算出部１２０は、状態遷移確率、及び、期待利得を生成部１４０に供給する。

初期化部１３０は、選択関数に用いられる可視状態毎の利得ベクトルの集合を、遷移モデルが対象とする期間全体において算出するのに先立って、予め定められた将来の時点（例えば、期間の最後の時点）における利得ベクトルの集合を初期化する。例えば、初期化部１３０は、将来のある時点における可視状態毎の利得ベクトルの集合をゼロベクトルの集合とすることにより初期化する。初期化部１３０は、初期化された利得ベクトルの集合を生成部１４０に提供する。

生成部１４０は、状態遷移確率及び期待利得に基づいて、基準時点以降の累積期待利得の算出に用いられる少なくとも１つの利得ベクトルを有し、累積期待利得の最大値を与える利得ベクトルが選択されるべき利得ベクトルの集合を、将来の時点から遡って再帰的に生成する。また、生成部１４０は、生成した利得ベクトルの集合から基準時点における累積期待利得が最大となる利得ベクトルが選択される選択関数を生成してよい。生成部１４０による利得ベクトルの集合等の詳細な生成方法については追って説明する。

また、生成部１４０は、利得ベクトルの集合を生成するときに入力と利得ベクトルとの対応付けを含む入力対応情報を生成する。生成部１４０は、生成した利得ベクトルの集合、状態遷移確率、及び、入力対応情報を選択装置２０に供給してよい。生成部１４０は、利得ベクトルの集合に代えて選択関数を選択装置２０に供給してもよい。

選択装置２０は、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力及び／又は隠れ状態に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルにおいて、利得ベクトルの集合に基づいて最適な入力を選択する。例えば、選択装置は、利得を最大化させる施策を最適な入力として選択する。選択装置２０は、一例として、コンピュータ上でソフトウェアを実行することにより実現される。選択装置２０は、取得部２１０、利得選択部２２０、入力選択部２３０、及び、遷移部２４０を有する。

取得部２１０は、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を取得する。例えば、取得部２１０は、生成装置１０が生成した利得ベクトルの集合を取得してよい。

また、取得部２１０は、状態遷移確率、及び、入力対応情報を生成装置１０から取得してよい。取得部２１０は、取得した利得ベクトルの集合及び入力対応情報を利得選択部２２０に供給する。また、取得部２１０は、状態遷移確率を遷移部２４０に供給する。

利得選択部２２０は、利得ベクトルの集合に基づいて、現在の可視状態に応じた利得ベクトルの中から、現時点における隠れ状態の確率分布に対し累積期待利得を最大化する利得ベクトルを選択する。例えば、利得選択部２２０は、利得ベクトルの集合から一の利得ベクトルを選択する選択関数を生成し、当該選択関数に基づいて累積期待利得を最大化する利得ベクトルを選択する。利得選択部２２０は、選択した利得ベクトル及び入力対応情報を入力選択部２３０に供給する。

入力選択部２３０は、入力対応情報に基づき、利得選択部２２０が選択した利得ベクトルに対応する入力を最適な入力として選択する。入力選択部２３０は、例えば、累積期待利得を最大化する施策を最適な入力として選択する。入力選択部２３０は、選択した入力を遷移部２４０に供給する。

遷移部２４０は、入力選択部２３０に選択された入力に対応する状態遷移確率、及び、現在の隠れ状態の確率分布に基づき、可視状態を確率的に遷移させる。また、遷移部２４０は、選択された入力に応じて、隠れ状態の確率分布を更新する。遷移部２４０は、更新した可視状態及び隠れ状態の確率分布を利得選択部２２０に供給し、再度、利得選択部２２０に可視状態及び隠れ状態の確率分布に基づき利得ベクトルを選択させる。

このように、本実施形態の情報処理システムによると、観測可能な可視状態が遷移する遷移モデルに再帰的手法を適用することにより、生成装置１０が利得ベクトルの集合を高速に生成することができる。また、選択装置２０は、生成装置１０が生成した利得ベクトルの集合に基づいて最適な入力を選択することができる。

図２は、本実施形態に係る遷移モデルの可視状態ｓ及び隠れ状態ｂの一例を示す。図示するように、本実施形態の情報処理システムは、観測可能な可視状態ｓ１、ｓ２、ｓ３…及び観測不可能な隠れ状態ｂ１、ｂ２、ｂ３…を有する。本実施形態において、可視状態、及び、隠れ状態は、図示するようにそれぞれ独立して与えられる。

すなわち、本実施形態において、可視状態のいずれか（例えば、可視状態ｓ２）と隠れ状態のいずれか（例えば、隠れ状態ｂ２）が同時に与えられる。例えば、ウェブベースの販売サイトにおいて、顧客との間の商取引により得られる累積期待利得を最大化するマーケティング施策を出力するアプリケーションを本実施形態の情報処理システムに適用する場合、顧客に対して行ったマーケティング施策及び顧客の反応は外部から観測できる可視状態であり、隠れ状態は顧客の嗜好等の外部から直接観測できない状態であってよい。

そして、本実施形態の情報処理システムは、期間中に可視状態は遷移し得るが（例えば、可視状態ｓ２→ｓ１又はｓ３等）、隠れ状態間では遷移しない（例えば、隠れ状態ｂ２のまま遷移しない）遷移モデルを扱う。

なお、隠れ状態は観測不可能なので、実際には図示するように一の隠れ状態ｂ２を特定することはできず、それぞれの隠れ状態ｉにある確率を表す確率分布ｂ｛ｂ（ｉ）｜ｉ＝１，...，｜Ｂ｜｝のみが算出される。可視状態の状態遷移の結果、どの隠れ状態にあるかの確からしさが間接的に判明していく場合があり、確率分布ｂは遷移し得る。例えば、隠れ状態ｂ２において可視状態ｓ２→ｓ１に遷移する確率が非常に高い場合、時点ｔから時点ｔ＋１において可視状態ｓ２→ｓ１が観測されたことに応じて、時点ｔ＋１における確率分布ｂにおいて隠れ状態ｂ２を与える確率が高くなる。

図３は、本実施形態の生成装置１０の処理フローを示す。本実施形態において、生成装置１０は、Ｓ１１０〜Ｓ１６０の処理を実行することにより、利得ベクトルの集合を生成する。

まず、Ｓ１１０において、入力部１１０は、外部又は生成装置１０内部のデータベース１０００から学習用データを取得する。例えば、入力部１１０は、可視状態、入力の内容、及び、観測結果等が予め時系列で定義されたデータを学習用データとして入力してよい。

これに代えて、入力部１１０は、可視状態が定義されていないデータを学習用データとして取得してもよい。一例として、入力部１１０は、まず、複数の消費者に対して提供された広告等の施策、及び、消費者の商品購入等の行動履歴等を取得してよい。次に、入力部１１０は、行動履歴等から状態ベクトルの時系列を生成し、状態ベクトルを離散化することで可視状態を定義してもよい。

また、入力部１１０は、学習用データとして、隠れ状態の推測に利用できるデータを取得してよい。例えば、入力部１１０は、学習用データとして消費者の嗜好等が記載されたアンケート結果を取得してよい。入力部１１０は、アンケート結果等から特徴ベクトルを生成し、特徴ベクトルを離散化することで隠れ状態を定義してもよい。入力部１１０は、学習用データを算出部１２０に提供する。

Ｓ１２０において、算出部１２０は、学習用データから状態遷移確率及び期待利得を算出する。例えば、算出部１２０は、学習用データから互いに遷移可能な１以上の可視状態ｓ（ｓ∈Ｓ）、及び、互いに遷移しない１以上の隠れ状態ｉ（ｉ∈Ｂ）を定義し、可視状態ｓ、隠れ状態ｉにおいて入力ａを実行したときに可視状態ｓから可視状態ｔに遷移し、ｚが観測される状態遷移確率Ｐ^ａ _{ｓ，ｉ；ｔ，ｚ}と、可視状態ｓ及び隠れ状態ｉにおいて入力ａを実行したときの期待利得ｑ^ａ _ｓ（ｉ）を算出する。算出部１２０は、Ｑ学習などの強化学習法により状態遷移確率Ｐ^ａ _{ｓ，ｉ；ｔ，ｚ}及び期待利得ｑ^ａ _ｓ（ｉ）を算出してよい。算出部１２０は、算出した状態遷移確率Ｐ^ａ _{ｓ，ｉ；ｔ，ｚ}及び期待利得ｑ^ａ _ｓ（ｉ）を生成部１４０に供給する。

次に、Ｓ１３０において、初期化部１３０は、遷移モデルにおける将来の時点Ｎ（Ｎは２以上の整数）における可視状態ｓについての利得ベクトルα_ｓ，Ｎの集合Λ_Ｎ（ｓ）を初期化する。例えば、初期化部１３０は、α_ｓ，Ｎの集合Λ_Ｎ（ｓ）を長さが隠れ状態の数｜Ｂ｜と同じ数のゼロベクトルだけからなる集合｛（０，...，０）｝として集合Λ_Ｎ（ｓ）を初期化する。また、初期化部１３０は、ｎ＝Ｎ−１としてｎを初期化する。初期化部１３０は、初期化された集合Λ_Ｎ（ｓ）等を生成部１４０に提供する。

次に、Ｓ１４０において、生成部１４０は、１≦ｎ≦Ｎ−１となるｎについて利得ベクトルα_ｓ，ｎの集合Λ_ｎ（ｓ）を集合Λ_ｎ＋１（ｓ）から生成する。生成部１４０が生成する利得ベクトルα_ｓ，ｎの集合Λ_ｎ（ｓ）は、隠れ状態ｉ毎に累積期待利得の成分α_ｓ，ｎ（ｉ）を有する利得ベクトルα_ｓ，ｎを少なくとも１つ含む。

図４は、本実施形態における生成部１４０による集合Λ_ｎ（ｓ）の生成方法の一例を示す。生成部１４０は、時点ｎにおける可視状態ｓ（ｓ∈Ｓ、Ｓは可視状態の集合）についての利得ベクトルα_ｓ，ｎの集合Λ_ｎ（ｓ）を、次の時点ｎ＋１における各可視状態ｓ'（ｓ'∈Ｓ）についての利得ベクトルα_{ｓ'，ｎ＋１}の集合Λ_ｎ＋１（ｓ'）に基づいて再帰的に生成する。

例えば、図示するように可視状態ｓ１が可視状態ｓ１、ｓ２及びｓ３を含む場合、生成部１４０は、時点ｎ＋１の利得ベクトルの集合Λ_ｎ＋１（１）、Λ_ｎ＋１（２）、及び、Λ_ｎ＋１（３）から時点ｎの利得ベクトルの集合Λ_ｎ（１）を生成してよい。生成部１４０は、利得ベクトルの集合を、入力に応じて一の可視状態ｓから時点ｎ＋１の可視状態ｓ'に遷移する状態遷移確率、及び、可視状態ｓ'において入力に応じて得られる期待利得に基づいて生成する。この具体的な生成方法は後述する。

ここで、生成部１４０は、生成した利得ベクトルα_ｓ，ｎの集合Λ_ｎ（ｓ）に基づいて、可視状態ｓ及び隠れ状態の確率分布ｂに応じて基準時点ｎ以降の累積期待利得が最大となる利得ベクトルを選択する選択関数Ｋｍａｘ_ｎ（ｓ，ｂ）を生成してよい。例えば、生成部１４０は、確率分布ｂにおける各隠れ状態ｉを取る確率に利得ベクトルの各成分を乗じた合計値に基づく累積期待利得が最大となる利得ベクトルを選択する選択関数を生成する。

一例として、生成部１４０は、数式（１）に示す選択関数Ｋｍａｘ_ｎ（ｓ，ｂ）を生成する。なお、ｂ（ｉ）は隠れ状態の確率分布における隠れ状態ｉを取る確率を示し、α_ｓ，ｎ ^ｋ（ｉ）は、時点ｎにおける可視状態ｓに対応するｋ番目の利得ベクトルα_ｓ，ｎ ^ｋの隠れ状態ｉに対応する成分を示す。また、生成部１４０は、選択関数Ｋｍａｘ_ｎ（ｓ，ｂ）を生成する過程において、入力と利得ベクトルとの対応付けを含む入力対応情報を生成する。

…数式（１）

次に、Ｓ１５０において、生成部１４０は、ｎから１を減じて処理をＳ１６０に進める。

次に、Ｓ１６０において、生成部１４０は、ｎ＝０となるか否かを判断する。ｎ＝０となる場合、生成部１４０は処理を終了し、そうでない場合は処理をＳ１４０に戻す。これにより、生成部１４０は、ｎがＮから０になるまで利得ベクトルの集合Λ_ｎ（ｓ）、及び／又は、選択関数Ｋｍａｘ_ｎ（ｓ，ｂ）を再帰的に生成する。

このように生成装置１０は、学習用データからまず状態遷移確率Ｐ^ａ _{ｓ，ｉ；ｔ，ｚ}、及び、期待利得ｑ^ａ _ｓ（ｉ）を算出し、これらに基づいて利得ベクトルの集合Λ_ｎ＋１（ｓ）からΛ_ｎ（ｓ）を再帰的に算出する。生成装置１０は、隠れ状態ｂが遷移しないモデルにおける利得ベクトルの集合Λ_ｎ（ｓ）を生成するので処理をより高速化することができる。

なお、遷移しない隠れ状態ｂは、環境中において短時間で変化しにくい特性と考えることができる。例えば、生成装置１０は、通常観測することが難しくかつ長期間変化しない消費者個人の好み（例えば、食事、又は、趣味等の好み）をモデルに組み入れた上で、最適施策を選択するための利得ベクトルの集合を生成することができる。

また、生成装置１０は、複数のセンサを備える自律行動するロボットに用いることができる。例えば、生成装置１０は、複数のセンサのうち一部のセンサが故障した状態を遷移しない隠れ状態に当てはめることができる。例えば、生成装置１０は、故障したセンサが検出する事項を隠れた状態とおくことにより、故障したセンサを考慮した上で最適施策を選択するための利得ベクトルの集合を提供することができる。

また、生成装置１０は、音声認識装置に用いた会話生成装置に適用することができる。例えば、生成装置１０は、完全に聞き取れなかった会話の内容を隠れ状態と考えることができる。これにより、生成装置１０は、人の会話等を完全に聞き取れなかった場合においても、最適施策（例えば、人に対する会話の回答）を選択するための利得ベクトルの集合を提供することができる。

図５は、図３における処理フローの具体的アルゴリズムの一例を示す。ここでは、図５を例にＳ１４０の処理のアルゴリズムを説明する。

まず、１行目に示すように、生成部１４０は、時点ｎ＋１、状態ｔ（ｔ∈Ｓ）における利得ベクトルの集合Λ_{ｎ＋１，ｔ}を取得する。なお、集合Λ_ｘ（ｙ）を集合Λ_ｘ，ｙ又は集合Λ_{（ｙ，ｘ）}と記載する場合がある。

次に、２行目に示すように、生成部１４０は、時点ｎにおける全入力に対応する利得ベクトルの集合Λ^＊ _ｓ，ｎを空集合とすることにより初期化する。

次に、３行目に示すように、生成部１４０は、各々の入力ａ（ａ∈Ａ、Ａは入力の集合）に対して、３〜１４行目で定義する第１ループ処理を実行する。

４行目に示すように、生成部１４０は、第１ループ処理内で入力ａに対応づけられた利得ベクトルの集合Λ^ａ _ｓ，ｎを空集合とすることにより初期化する。

次に、５行目に示すように、生成部１４０は、第１ループ処理内で各々の可視状態ｔ（ｔ∈Ｓ）及び観測ｚ（ｚ∈Ｚ、Ｚは観測の集合）の組み合わせに対して、５〜１２行目で定義する第２ループ処理を実行する。

６行目に示すように、生成部１４０は、第２ループ処理内で、ベクトル集合Φを空集合とすることにより初期化する。

次に、７行目に示すように、生成部１４０は、第２ループ処理内で各々の利得ベクトルα（α∈Λ^＊ _{ｓ，ｎ＋１}）に対して、７〜９行目で定義する第３ループ処理を実行する。

８行目に示すように、生成部１４０は、第３ループ処理内でベクトル集合Φを更新する。具体的には、生成部１４０は、従前のベクトル集合Φと時点ｎ＋１における利得ベクトルαに基づいて生成される新しいベクトルの和集合を生成する。

生成部１４０は、各々の隠れ状態ｉについて、期待利得ｑ^ａ _ｓ（ｉ）を可視状態ｓの数｜Ｓ｜及び観測ｚの数｜Ｚ｜で除した値と、将来の利得に対する割引率γ（０＜γ＜１）、状態遷移確率Ｐ^ａ _{ｓ，ｉ；ｔ，ｚ}、及び、利得ベクトルαの隠れ状態ｉの成分α（ｉ）（すなわち、隠れ状態ｉに対応する累積期待利得の成分）の積の値との和を、隠れ状態ｉに対応する成分として有する、時刻ｎの新しいベクトルを生成する。

生成部１４０は、γ＝１とすることにより将来の利得を割り引くことなく新しいベクトルを生成してもよい。

次に、１０行目に示すように、生成部１４０は、第２ループ処理内で第３ループ処理の後に、更新されたベクトル集合ΦをＰｒｕｎｅ関数によって枝刈りしてよい。ここで、Ｐｒｕｎｅ関数は、入力されたベクトル集合に含まれるベクトルのうち、隠れ状態ｉの確率分布ｂの少なくとも一部の範囲において隠れ状態ｉに対応する成分が最大値を構成するベクトル以外のベクトルを入力集合から除去する。

次に、１１行目に示すように、生成部１４０は、第２ループ処理内で時点ｎの利得ベクトルの集合Λ^ａ _ｓ，ｎを生成する。具体的には、生成部１４０は、現在の利得ベクトルの集合Λ^ａ _ｓ，ｎに含まれるベクトルα、及び、ベクトル集合Φに含まれるベクトルα'の全ての組み合わせについて、ベクトルα及びベクトルα'の和から合算ベクトルを生成し、当該合算ベクトルをＰｒｕｎｅ関数により枝刈りすることにより、新しい利得ベクトルの集合Λ^ａ _ｓ，ｎを生成する。これにより、生成部１４０は、入力ａに対応する利得ベクトルの集合Λ^ａ _ｓ，ｎを生成するので、入力と利得ベクトルの対応情報である入力対応情報を生成することができる。

次に、１３行目に示すように、生成部１４０は、第１ループ処理内で第２ループ処理の後に、利得ベクトルの集合Λ^＊ _ｓ，ｎを更新する。具体的には、生成部１４０は、集合Λ^＊ _ｓ，ｎと集合Λ^ａ _ｓ，ｎとの和集合を取ることにより集合Λ^＊ _ｓ，ｎを更新する。

次に、１５行目に示すように、生成部１４０は、第１ループ処理の後に、集合Λ^＊ _ｓ，ｎを更新する。具体的には、生成部１４０は、Ｐｒｕｎｅ関数に集合Λ^＊ _ｓ，ｎを入力することにより集合Λ^＊ _ｓ，ｎを更新する。

次に、１６行目において、生成部１４０は、集合Λ^＊ _ｓ，ｎを時点ｎ、状態ｓにおける利得ベクトルの集合して出力する。

このように、生成装置１０は、時点ｎ＋１の可視状態ｓにおける隠れ状態ｉ毎の期待利得ｑ^ａ _ｓ（ｉ）、時点ｎ＋１の可視状態ｓにおけるΛ_{ｓ，ｎ＋１}、及び、割引率γに基づいて、時点ｎの可視状態ｓに対応する利得ベクトルΛ_ｓ，ｎを生成する。

また、生成装置１０は、Ｐｒｕｎｅ関数により、各時点ｎ及び各可視状態ｓにおいて、集合Λ_ｓ，ｎに含まれる利得ベクトルα_ｓ，ｎの集合から、隠れ状態ｉの確率分布の少なくとも一部の範囲において最大値を構成する利得ベクトル以外を除去することにより、集合Λ_ｓ，ｎを生成する。

図６は、利得ベクトルの集合Λ_ｓ，ｎと累積期待利得の関係を示す。図６（ａ）は集合Λ_ｓ，ｎと累積期待利得との関係を示す。ここで利得ベクトルα_１、α_２、α_３、及びα_４を含む利得ベクトルの集合Λ_ｓ，ｎを想定する。各利得ベクトルは、隠れ状態の確率分布ｂに応じた累積期待利得の値を算出するのに用いることができる。図６では説明のために便宜的に、各利得ベクトルが、確率分布ｂではなく単一の隠れ状態ｉである確率ｂ（ｉ）の値のみに応じて累積期待利得の値を返すものとして説明する。

例えば、隠れ状態ｉである確率ｂ（ｉ）がｂ_１である場合、利得ベクトルα_１はｂ_１の値に応じた累積期待利得ｒ_１を返し、利得ベクトルα_２はｂ_１の値に応じた累積期待利得ｒ_２を返し、利得ベクトルα_３はｂ_１の値に応じた累積期待利得ｒ_３を返し、利得ベクトルα_４はｂ_１の値に応じた累積期待利得ｒ_４を返す。

図示するように、累積期待利得ｒ_１〜ｒ_４のうち最大値を取るのは累積期待利得ｒ_１であるので、利得ベクトルα_１〜α_４の集合から確率ｂ_１に応じて累積期待利得ｒ_１に対応する利得ベクトルα_１を選択することができる。例えば、選択関数は、確率ｂ_１が入力されたことに応じて、利得ベクトルα_１に対応する番号１を出力する。同様に、選択関数は、確率ｂ_２に応じて累積期待利得の最大値を取る利得ベクトルα_２を出力し、ｂ_３に応じて累積期待利得の最大値を取る利得ベクトルα_３を出力する。

ここで、各利得ベクトルには入力が対応付けられているので、選択関数に隠れ状態の確率分布ｂを入力することで、最適な入力を選択することができる。例えば、選択関数が利得ベクトルα_１に対応する番号１を出力した場合、番号１に対応する入力を最適な入力して選択することができる。

図６（ｂ）は、最大値を取る利得ベクトルの部分を連結することにより得られる、累積期待利得の最大値を返す利得関数を示す。図示するように、複数の利得ベクトルα_１〜α_４のうち累積期待利得が最大値となる区間のみを連結すると、太線で示す下に凸が向いた区分線形凸関数となる利得関数ｖ_ｎ（ｓ，ｂ）が得られる。利得関数ｖ_ｎ（ｓ，ｂ）は、ｖ_ｎ（ｓ，ｂ）＝ｍａｘ［Σ_ｉｂ（ｉ）α（ｉ）］で表される可視状態ｓ及び隠れ状態の確率分布ｂに依存する関数となる。

ここで、生成部１４０は、集合Λ_ｓ，ｎを生成する際に、Ｐｒｕｎｅ関数により累積期待利得が最大値となる区間を有しない利得ベクトル（例えば、利得ベクトルα_４）を除去している。これにより、生成部１４０は、選択関数に用いる利得ベクトルから入力の選択に寄与しない無意味なものを排除し、計算をより効率化することができる。

図７は、図３における処理フローの具体的アルゴリズムの別の一例を示す。図７は、図５を例にＳ１４０の処理のアルゴリズムを説明する。本例のアルゴリズムは、図５で示したものと異なり、観測ｚ（ｚ∈Ｚ）を考慮せずに集合Λ_ｎ，ｔを算出する。

まず、１行目に示すように、生成部１４０は、各々の可視状態ｓ（ｓ∈Ｓ）に対して、１〜１１行目で定義する第１ループ処理を実行する。

次に、２行目に示すように、生成部１４０は、第１ループ処理内で全入力に対応する利得ベクトルの集合Λ_{（ｓ，ｎ）}を空集合とすることにより初期化する。

次に、３行目に示すように、生成部１４０は、各々の入力ａ（ａ∈Ａ）に対して、３〜１０行目で定義する第２ループ処理を実行する。

４行目に示すように、生成部１４０は、第２ループ処理内で入力ａに対応づけられた利得ベクトルの集合Λ_{（ｓ，ｎ，ａ）}を空集合とすることにより初期化する。

次に、５行目に示すように、生成部１４０は、第２ループ処理内で各々の可視状態ｓ'（ｓ'∈Ｓ）に対して、５〜８行目で定義する第３ループ処理を実行する。ここで、可視状態ｓ'は時点ｎ＋１における可視状態を示す。

６行目に示すように、生成部１４０は、第３ループ処理内でベクトルの集合Λ（ｓ，ｎ，ａ，ｓ'）を生成する。具体的には、生成部１４０は、時点ｎ＋１の集合Λ（ｓ'，ｎ＋１）に含まれる各々の利得ベクトルαについて、新しいベクトルを生成する。状態遷移確率Ｐ^ａ _{ｓ，ｉ；s'}は、可視状態ｓ、隠れ状態ｉにおいて入力ａを実行したときに可視状態ｓから可視状態s'に遷移する確率を表す。

例えば、生成部１４０は、各々の隠れ状態ｉについて、期待利得ｑ^ａ _ｓ，ｉを可視状態ｓの数｜Ｓ｜で除した値と、状態遷移確率Ｐ^ａ _{ｓ，ｉ；ｓ'}、及び、利得ベクトルαの隠れ状態ｉの成分α（ｉ）の積の値との和を、新しいベクトルの隠れ状態ｉに対応する成分とすることにより利得ベクトルαから新しいベクトルを生成する。生成部１４０を、生成した新しいベクトルをＰｒｕｎｅ関数に入力することにより、集合Λ（ｓ，ｎ，ａ，ｓ'）を生成する。

次に、７行目に示すように、生成部１４０は、第３ループ処理内で集合Λ（ｓ，ｎ，ａ）を生成する。具体的には、生成部１４０は、集合Λ（ｓ，ｎ，ａ）に含まれるベクトルα、及び、集合Λ（ｓ，ｎ，ａ，ｓ'）に含まれるベクトルα'の全ての組み合わせについて、ベクトルα及びベクトルα'の和から合算ベクトルを生成し、当該合算ベクトルをＰｒｕｎｅ関数に入力することにより、新しい利得ベクトルの集合Λ（ｓ，ｎ，ａ）を生成する。これにより、生成部１４０は、入力ａと集合Λ（ｓ，ｎ，ａ）に含まれる利得ベクトルとを対応付けることができる。

次に、９行目に示すように、生成部１４０は、第２ループ処理内で第３ループ処理の後に、集合Λ（ｓ，ｎ）を更新する。具体的には、生成部１４０は、集合Λ（ｓ，ｎ）と集合Λ（ｓ，ｎ，ａ）との和集合を取ることにより集合Λ（ｓ，ｎ）を更新する。

図８は、本実施形態の選択装置２０の処理フローを示す。本実施形態において、選択装置２０は、Ｓ３１０〜Ｓ３８０の処理を実行することにより、最適な入力を選択する。

まず、Ｓ３１０において、取得部２１０は、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合Λ_ｓ，ｎを取得する。

また、取得部２１０は、生成装置１０から、隠れ状態ｉにおいて一の入力ａをしたときに状態集合Ｓにおいて一の可視状態ｓから別の可視状態ｓ'に遷移する状態遷移確率Ｐ^ａ _{ｓ，ｉ，ｓ'}、及び、入力ａと利得ベクトルα_ｓ，ｎ ^ａとの対応付けを含む入力対応情報を取得してよい。

取得部２１０は、取得した利得ベクトルの集合Λ_ｓ，ｎ及び入力対応情報を利得選択部２２０に供給する。また、取得部２１０は、状態遷移確率Ｐ^ａ _{ｓ，ｉ，ｓ'}を遷移部２４０に供給する。

次に、Ｓ３２０において、取得部２１０は、シミュレーションの対象となる環境の初期化処理を実行する。例えば、取得部２１０は、可視状態、及び、隠れ状態の初期条件を設定する。

一例として、取得部２１０は、生成装置１０がデータベース１０００から取得した学習用データにおける将来の時点における可視状態ｓ_０、及び、隠れ状態の確率分布ｂ_０をシミュレーションの初期条件（ｓ_０，ｂ_０）としてよい。また、例えば、取得部２１０は、環境の可視状態、及び、隠れ状態についての初期条件を直接データベース１０００等から取得してもよい。

また、取得部２１０は、時点ｎを１に設定することで初期化する。取得部２１０は、将来の時点Ｎを設定する。例えば、取得部２１０は、時点Ｎに予め定められた数を設定する。取得部２１０は、初期化の結果を利得選択部２２０に供給する。

次に、Ｓ３３０において、利得選択部２２０は、現在の可視状態ｓに応じた利得ベクトルαの中から、現時点における隠れ状態の確率分布ｂに対し累積期待利得を最大化する利得ベクトルαを選択する。

例えば、まず、利得選択部２２０は、利得ベクトルの集合Λ_ｓ，ｎから数式（１）で表される隠れ状態ｉを取る確率ｂ（ｉ）、及び、時点ｎの可視状態ｓに対応するｋ番目の利得ベクトルα_ｓ，ｎ ^ｋの隠れ状態ｉに対応するα_ｓ，ｎ ^ｋ（ｉ）に基づく規定される選択関数Ｋｍａｘ_ｎ（ｓ，ｂ）を生成する。

…数式（１）

次に、利得選択部２２０は、選択関数Ｋｍａｘ_ｎ（ｓ，ｂ）に現在の可視状態ｓ及び隠れ状態の確率分布ｂを入力して、隠れ状態の確率分布ｂに対応して決定される利得ベクトルα^ｋ _ｓ，ｎを選択する。利得選択部２２０は、利得ベクトルの集合Λ_ｓ，ｎの代わりに取得部２１０を介して取得した選択関数Ｋｍａｘ_ｎ（ｓ，ｂ）により利得ベクトルα^ｋ _ｓ，ｎを選択してもよい。利得選択部２２０は、選択した利得ベクトルα^ｋ _ｓ，ｎ及び入力対応情報を入力選択部２３０に供給する。

次に、Ｓ３４０において、入力選択部２３０は、利得選択部２２０が選択した利得ベクトルに対応する入力を、最適な入力として選択する。例えば、入力選択部２３０は、入力対応情報に基づき、利得ベクトルα^ｋ _ｓ，ｎと予め対応付けられた入力ｋを、時点ｎにおいて実行した場合に最大の累積期待利得を与える最適な入力ｋとして選択する。入力選択部２３０は、選択した入力ｋを遷移部２４０に供給する。

次に、Ｓ３５０において、遷移部２４０は、入力選択部２３０に選択された入力ｋを実行したことに応じて、選択された入力に対応する状態遷移確率及び現在の隠れ状態の確率分布ｂに基づき、可視状態ｓを確率的に遷移させる。

すなわち、遷移部２４０は、現在の可視状態ｓを状態遷移確率Ｐ^ｋ _{ｓ，ｉ；ｔ，ｚ}の確率でいずれか１つの可視状態ｔ（ｔ∈Ｓ）に遷移させる。

次に、遷移部２４０は、選択された入力ｋに対応する状態遷移確率Ｐ^ｋ _{ｓ，ｉ，ｓ'，ｚ}及び現在の隠れ状態の確率分布ｂに基づき、隠れ状態の確率分布ｂを更新する。例えば、遷移部２４０は、隠れ状態ｉをとる確率ｂ（ｉ）に数式（２）の計算結果を代入することにより隠れ状態の確率分布ｂを更新する。

…数式（２）
Ｐ^ａ _{ｓ，ｉ；ｓ'，ｚ}は隠れ状態ｉ及び可視状態ｓにおいて入力ａにより可視状態ｓから可視状態ｓ'に遷移し、観測ｚが観測される状態遷移確率を示す。

観測ｚを考慮しない遷移モデルの場合、遷移部２４０は、選択された入力ｋに対応する状態遷移確率Ｐ^ｋ _{ｓ，ｉ，ｓ'}及び現在の隠れ状態の確率分布ｂに基づき、隠れ状態の確率分布ｂを更新する。例えば、遷移部２４０は、隠れ状態ｉをとる確率ｂ（ｉ）に数式（３）の計算結果を代入することにより隠れ状態の確率分布ｂを更新する。

…数式（３）
Ｐ^ａ _{ｓ，ｉ；ｓ'}は隠れ状態ｉ及び可視状態ｓにおいて入力ａにより可視状態ｓから可視状態ｓ'に遷移する状態遷移確率を示す。

次に、Ｓ３７０において、遷移部２４０は、ｎに１を加える。遷移部２４０は、処理をＳ３８０に進める。

次に、Ｓ３８０において、遷移部２４０は、ｎがＮを超えるか否かを判断する。ｎ＞Ｎとなる場合、遷移部２４０は処理を終了し、そうでない場合は処理をＳ３３０に戻す。

このように、選択装置２０は、生成装置１０が生成した利得ベクトルの集合Λ_ｓ，ｎを用いて、可視状態ｓ及び隠れ状態の確率分布ｂに応じた最適な施策を選択して出力することができる。

図９は、本実施形態の変形例に係る情報処理システムの概要を示す。本変形例では、生成装置３０は、利得ベクトルの集合を生成した後、生成した利得ベクトルの一部を選択して選択装置４０に供給する。

生成装置３０は、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力及び／又は隠れ状態に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルについて、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に生成する。生成装置３０は、入力部３１０、算出部３２０、初期化部３３０、生成部３４０、設定部３５０、及び、選択部３６０を備える。入力部３１０、算出部３２０、及び、初期化部３３０は、図１で説明した生成装置１０に係る入力部１１０、算出部１２０、及び、初期化部１３０と同様の構成であってよい。

生成部３４０は、生成部１４０と同様に状態遷移確率及び期待利得に基づいて、基準時点以降の累積期待利得の算出に用いられる少なくとも１つの利得ベクトルを有し、累積期待利得の最大値を与える利得ベクトルが選択されるべき利得ベクトルの集合を、将来の時点から遡って再帰的に生成する。

また、生成部３４０は、利得ベクトルの集合を生成するときに入力と利得ベクトルとの対応付けを含む入力対応情報を生成する。生成部３４０は、生成した利得ベクトルの集合、状態遷移確率、及び、入力対応情報を選択部３６０に供給してよい。

設定部３５０は、利得ベクトルの集合に含めるベクトルを選択するために用いる選択用の隠れ状態の確率分布を設定する。設定部３５０は、設定した選択用の確率分布を、選択部３６０に供給する。

選択部３６０は、設定した選択用の確率分布に基づいて、生成部３４０が生成した利得ベクトルの集合から少なくとも一部の利得ベクトルを選択する。例えば、選択部３６０は、選択用の確率分布について累積期待利得の最大値を与える利得ベクトルを優先して選択して利得ベクトルの集合に含めることにより、新しい利得ベクトルの集合を生成する。

選択部３６０は、生成したある時点ｎ＋の１における新しい利得ベクトルの集合を生成部３４０に供給し、生成部３４０に前の時点ｎにおける利得ベクトルの集合を生成させてよい。選択部３６０は、最終的に選択された利得ベクトルの集合、状態遷移確率、及び、入力対応情報を選択装置４０に供給する。

選択装置４０は、観測可能な可視状態、及び、観測不能な隠れ状態を備え、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルにおいて、利得ベクトルの集合に基づいて最適な入力を選択する。

選択装置４０は、取得部４１０、利得選択部４２０、入力選択部４３０、及び、遷移部４４０を有する。取得部４１０、利得選択部４２０、及び、入力選択部４３０は、図１で説明した選択装置２０に係る取得部２１０、利得選択部２２０、及び、入力選択部２３０と同様の構成であってよい。

遷移部４４０は、選択装置２０に係る遷移部２４０と同様に、入力選択部４３０に選択された入力に応じて、可視状態及び隠れ状態の確率分布を遷移させる。遷移部４４０は、更新した可視状態及び隠れ状態の確率分布を利得選択部４２０に供給し、再度、利得選択部４２０に可視状態及び隠れ状態の確率分布に基づき利得ベクトルを選択させる。また、遷移部４４０は、時刻ごとに更新される隠れ状態の確率分布の時系列を、生成装置３０の設定部３５０に供給してよい。

このように、本変形例の情報処理システムによると、生成装置３０は、選択用の確率分布に基づき利得ベクトルが選択された利得ベクトルの集合を生成して、選択装置４０に供給する。これにより選択装置４０は、より少数の利得ベクトルを用いることにより、更に効率的に最適な入力を算出することができる。

図１０は、本変形例の生成装置３０の処理フローの一例を示す。本変形例において、生成装置３０は、Ｓ５１０〜Ｓ５７０の処理を実行することにより、利得ベクトルの集合を生成する。生成装置３０は、Ｓ５１０〜Ｓ５３０の処理を、図３に係るＳ１１０〜Ｓ１３０の処理と同様に実行してよい。

Ｓ５４０において、設定部３５０は、選択装置４０に供給する利得ベクトルの集合に含めるベクトルを選択するために用いる選択用の隠れ状態の確率分布を設定する。例えば、設定部３５０は、予め定められたベクトルの集合を選択用の隠れ状態の確率分布として設定する。

一例として、設定部３５０は、選択用の確率分布に、長さが隠れ状態の数｜Ｂ｜となり、各隠れ状態ｉについて当該隠れ状態に対応する成分を予め定められた値（例えば、１）としたベクトル｛ｅ_ｉ｜ｉ＝１，...，｜Ｂ｜｝の集合を、選択用の確率分布として設定してよい。設定部３５０は、設定した選択用の確率分布を、選択部３６０に供給する。

次にＳ５５０において、生成部３４０は、Ｓ１４０と同様に、１≦ｎ≦Ｎ−１となる時点ｎについて利得ベクトルα_ｓ，ｎの集合Λ_ｎ（ｓ）を時点ｎ＋１についての集合Λ_ｎ＋１（ｓ）から再帰的に生成する。生成部３４０は、時点ｎについての利得ベクトルの集合Λ_ｎ（ｓ）等を選択部３６０に供給する。

次に、Ｓ５５２において、選択部３６０は、選択用の確率分布に基づいて利得ベクトルの集合から少なくとも一部の利得ベクトルのみを選択した利得ベクトルの集合を生成する。例えば、選択部３６０は、生成部３４０から受け取った時点ｎについての利得ベクトルの集合から、選択用の確率分布について累積期待利得の最大値を与える利得ベクトルを優先して選択して利得ベクトルの集合に含めることにより、時点ｎについて選択済みの利得ベクトルの集合を生成する。

すなわち、選択部３６０は、利得ベクトルの集合から選択用の確率分布について累積期待利得の最大値を与える利得ベクトル以外の利得ベクトルを除去する。選択部３６０は、生成した時点ｎについての選択済みの利得ベクトルの集合を生成部３４０に供給する。なお、選択部３６０による利得ベクトルの選択の具体的な処理内容につては後述する。

次に、Ｓ５６０において、選択部３６０は、ｎから１を減じて処理をＳ５７０に進める。

次に、Ｓ５７０において、選択部３６０は、ｎ＝０となるか否かを判断する。ｎ＝０となる場合、選択部３６０は処理を終了し、そうでない場合は処理をＳ５５０に戻す。２回目以降のＳ５５０の処理において、生成部３４０は、選択部３６０が生成した選択済みの利得ベクトルの集合に基づいて、再度利得ベクトルの集合を生成し、選択部３６０に供給する。これにより、生成部３４０及び選択部３６０は、ｎがＮから０になるまで利得ベクトルの集合Λ_ｎ（ｓ）を再帰的に生成する。

このように本変形例の生成装置３０は、生成部３４０が利得ベクトルの集合を生成し、選択部３６０が生成された利得ベクトルの一部のみを選択する。これにより、生成装置３０は、最終的に生成される利得ベクトルの集合に含まれる利得ベクトルの数を低減するので、選択装置４０による選択処理をより高速化することができる。

図１１は、図１０における処理フローの具体的アルゴリズムの一例を示す。ここでは、図１０のＳ５５０及びＳ５５２の処理のアルゴリズムを説明する。

まず、１行目に示すように、生成部３４０は、時点ｎ＋１、状態ｔ（ｔ∈Ｓ）における利得ベクトルの集合Λ_{ｔ，ｎ＋１}を取得し、選択部３６０は選択用の隠れ状態の確率分布ｂの集合Ｂを取得する。

次に、生成部３４０は、各々の入力ａ（ａ∈Ａ）、各々の可視状態ｔ（ｔ∈Ｓ）、及び、各々の観測ｚ（ｚ∈Ｚ）に対して、２〜４行目で定義する第１ループ処理を実行する。

３行目に示すように、生成部３４０は、第１ループ処理内でベクトル集合Θ^ａ _ｔ，ｚを更新する。具体的には、生成部３４０は、隠れ状態の各成分ｉについて、状態遷移確率Ｐ^ａ _{ｓ，ｉ；ｔ}、及び、時点ｎ＋１の利得ベクトルαの隠れ状態ｉの成分α（ｉ）（すなわち、隠れ状態ｉに対応する累積期待利得の成分）を乗じることにより、時点ｎの利得ベクトルα_ｔ，ｚ（α_ｔ，ｚ∈Θ^ａ _ｔ，ｚ）を生成する。

次に、選択部３６０は、各々の選択用の確率分布ｂ（ｂ∈Ｂ）について、５〜７行目に示す第２ループ処理を実行する。

６行目に示すように、選択部３６０は、利得ベクトルの集合θ^ａ _ｔ，ｚから利得ベクトルを選択してベクトル集合Ψ_ｂを生成する。具体的には、選択部３６０は、選択用の確率分布ｂの各々について、隠れ状態の確率分布ｂ及び利得ベクトルα_ｔ，ｚの積が最大化される利得ベクトルα_ｔ，ｚをａｒｇｍａｘ関数で選択し、選択された利得ベクトルα_ｔ，ｚと期待利得ｑ^ａ _ｓとの和をベクトル集合Ψ_ｂに加える。選択部３６０は、隠れ状態の確率分布ｂ及び利得ベクトルα_ｔ，ｚの積に割引率γ（０＜γ＜１）を更に乗じてもよい。

次に、８行目に示すように、選択部３６０は、ベクトル集合Ψ_ｂから利得ベクトルを選択して、時点ｎについての選択済みの利得ベクトルの集合Λ_ｓ，ｎを生成する。具体的には、選択部３６０は、隠れ状態の確率分布ｂ及び利得ベクトルα（α∈Ψ）の積が最大化される利得ベクトルαをａｒｇｍａｘ関数で選択し、これを選択済みの利得ベクトルの集合Λ_ｓ，ｎとする。

次に、９行目において、選択部３６０は、集合Λ_ｓ，ｎを時点ｎ、状態ｓにおける利得ベクトルの集合として出力する。

図１２は、本変形例における集合Λ_ｓ，ｎと累積期待利得の関係を示す。図１２（ａ）は図６（ａ）と同様に集合Λ_ｓ，ｎと累積期待利得との関係を示す。生成部３４０は、利得ベクトルα_１、α_２、α_３、及びα_４を含む利得ベクトルの集合Λ_ｓ，ｎを生成する。

本変形例において、設定部３５０は、選択用の確率分布ｂ_１'及びｂ_２'を設定する。なお、図１２では説明のため便宜的に、選択用の確率分布ｂ_１'及びｂ_２'はベクトルではなく、単一の隠れ状態ｉに対応した値ｂ（ｉ）であるものとして説明する。

例えば、選択部３６０は、選択用の確率分布ｂ_１'について、利得ベクトルα_１〜α_４のうち累積期待利得の最大値を与える利得ベクトルα_１を選択済みの利得ベクトルの集合に含める。また、選択部３６０は、選択用の確率分布ｂ_２'について、利得ベクトルα_１〜α_４のうち累積期待利得の最大値を与える利得ベクトルα_３を選択済みの利得ベクトルの集合に含める。このように、選択部３６０は、選択用の確率分布ｂ_１'及びｂ_２'に基づき、生成部３４０が生成した利得ベクトルα_１〜α_４から利得ベクトルα_１及びα_３を含む選択済みの利得ベクトルの集合を生成する。

図１２（ｂ）は、本変形例に係る生成装置３０が生成する利得ベクトルの集合に含まれる利得ベクトルの部分を連結することにより得られる、累積期待利得の最大値を返す利得関数を示す。

図示するように、選択済みの利得ベクトルの集合に含まれる利得ベクトルα_１及びα_３のうち累積期待利得が最大値となる区間のみを連結すると、太線で示す下に凸が向いた区分線形凸関数となる利得関数ｖ_ｎ（ｓ，ｂ）が得られる。αを選択済みの利得ベクトルの集合に含まれる利得ベクトルとしたときに、利得関数ｖ_ｎ（ｓ，ｂ）は、ｖ_ｎ（ｓ，ｂ）＝ｍａｘ［Σ_ｉｂ（ｉ）α（ｉ）］で表される可視状態ｓ及び隠れ状態の確率分布ｂに依存する関数となる。

このように本変形例によると、図６（ｂ）に示す利得関数と比べて、利得ベクトルの数を減らすことができる。これにより、選択装置４０は、選択関数による計算をより高速化及び効率化することができる。

図１３は、本実施形態の本変形例の処理フローの別の一例を示す。本変形例において、選択装置４０は予め定められた期間１〜Ｎについて選択関数により入力を選択して、確率分布の更新を実行し、生成装置３０は選択装置４０から更新された確率分布を受け取り、当該確率分布を選択用の確率分布として利用して利得ベクトルの集合を更新する。

生成装置３０はＳ７１０〜Ｓ７６０の処理を図１０のＳ５１０〜Ｓ５７０の処理と同様に実行してよい。Ｓ７７０において、生成部３４０は、ｎ＝０となるか否かを判断する。ｎ＝０となる場合、生成部３４０は処理をＳ７８０に進め、そうでない場合は処理をＳ７５０に戻す。

Ｓ７８０において、生成装置３０の選択部３６０は、生成した選択済みの利得ベクトルの集合、入力と利得ベクトルとの対応付けを含む入力対応情報、及び、可視状態の状態遷移確率を選択装置４０に供給する。

選択装置４０はＳ８１０〜Ｓ８７０の処理を図８のＳ３１０〜Ｓ３７０の処理と同様に実行してよい。

Ｓ８８０において、遷移部２４０は、ｎがＮを超えるか否かを判断する。ｎ＞Ｎとなる場合、遷移部２４０は処理をＳ８９０に進め、そうでない場合は処理をＳ８３０に戻す。

Ｓ８９０において、遷移部２４０は、選択装置４０が選択関数により入力を選択して確率分布の更新を実行すること、及び、生成装置３０が選択装置から更新された確率分布を受け取り当該確率分布を選択用の確率分布として利得ベクトルの集合を更新することを予め定められた回数繰り返し実行したか否かを判断する。

予め定められた回数の繰り返しが完了した場合、遷移部２４０は処理を終了し、そうでない場合は処理をＳ９００に戻す。

Ｓ９００において、遷移部４４０は、繰り返し実行されたＳ８６０の処理において生成された期間中の各時点における隠れ状態の確率分布の情報を生成装置３０に送信する。

次に、生成装置３０の設定部３５０は、再びＳ７４０の処理を実行して、遷移部４４０が更新した各時点における確率分布を受け取り、これを選択用の確率分布として設定する。ここで、設定部３５０は、既に設定された選択用の確率分布に加えて／代えて、遷移部４４０が更新した確率分布を選択用の確率分布として設定してよい。

このように、設定部３５０は、生成部３４０が生成した利得ベクトルの集合の中から累積期待利得の最大値を返す利得ベクトルに対応する入力が利得選択部４２０により選択された場合に、選択された入力に応じて遷移部４４０で更新される隠れ状態の確率分布を選択用の確率分布として設定することができる。

これにより、本変形例の情報処理システムは、生成装置３０による利得ベクトルの生成、及び、選択装置４０による最適入力の選択の繰り返しを実行するごとに、より現実に近い隠れ状態の確率分布に基づいて、利得ベクトルの集合に含める利得ベクトルを選択することができるので、選択装置４０は最適入力の選択をより正確かつ高速に実行することができる。

図１４は、生成装置１０、選択装置２０、生成装置３０、及び／又は、選択装置４０として機能するコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、及び表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有するレガシー入出力部を備える。

ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。

入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェイス２０３０は、有線又は無線によりネットワークを介して他の装置と通信する。また、通信インターフェイスは、通信を行うハードウェアとして機能する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。

また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラム、及び／又は、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０を入出力コントローラ２０８４へと接続するとともに、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を入出力コントローラ２０８４へと接続する。

ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。

コンピュータ１９００にインストールされ、コンピュータ１９００を生成装置１０及び選択装置２０として機能させるプログラムは、入力モジュール、算出モジュール、初期化モジュール、生成モジュール、設定モジュール、選択モジュール、取得モジュール、利得選択モジュール、入力選択モジュール、及び、遷移モジュールを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、入力部１１０、算出部１２０、初期化部１３０、生成部１４０、取得部２１０、利得選択部２２０、入力選択部２３０、遷移部２４０、入力部３１０、算出部３２０、初期化部３３０、生成部３４０、設定部３５０、選択部３６０、取得部４１０、利得選択部４２０、入力選択部４３０、及び、遷移部４４０としてそれぞれ機能させてよい。

これらのプログラムに記述された情報処理は、コンピュータ１９００に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である入力部１１０、算出部１２０、初期化部１３０、生成部１４０、取得部２１０、利得選択部２２０、入力選択部２３０、遷移部２４０、入力部３１０、算出部３２０、初期化部３３０、生成部３４０、設定部３５０、選択部３６０、取得部４１０、利得選択部４２０、入力選択部４３０、及び、遷移部４４０として機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ１９００の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有の生成装置１０、選択装置２０、生成装置３０、及び、選択装置４０が構築される。

一例として、コンピュータ１９００と外部の装置等との間で通信を行う場合には、ＣＰＵ２０００は、ＲＡＭ２０２０上にロードされた通信プログラムを実行し、通信プログラムに記述された処理内容に基づいて、通信インターフェイス２０３０に対して通信処理を指示する。通信インターフェイス２０３０は、ＣＰＵ２０００の制御を受けて、ＲＡＭ２０２０、ハードディスクドライブ２０４０、フレキシブルディスク２０９０、又はＣＤ−ＲＯＭ２０９５等の記憶装置上に設けた送信バッファ領域等に記憶された送信データを読み出してネットワークへと送信し、もしくは、ネットワークから受信した受信データを記憶装置上に設けた受信バッファ領域等へと書き込む。このように、通信インターフェイス２０３０は、ＤＭＡ（ダイレクト・メモリ・アクセス）方式により記憶装置との間で送受信データを転送してもよく、これに代えて、ＣＰＵ２０００が転送元の記憶装置又は通信インターフェイス２０３０からデータを読み出し、転送先の通信インターフェイス２０３０又は記憶装置へとデータを書き込むことにより送受信データを転送してもよい。

また、ＣＰＵ２０００は、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０（ＣＤ−ＲＯＭ２０９５）、フレキシブルディスク・ドライブ２０５０（フレキシブルディスク２０９０）等の外部記憶装置に格納されたファイルまたはデータベース等の中から、全部または必要な部分をＤＭＡ転送等によりＲＡＭ２０２０へと読み込ませ、ＲＡＭ２０２０上のデータに対して各種の処理を行う。そして、ＣＰＵ２０００は、処理を終えたデータを、ＤＭＡ転送等により外部記憶装置へと書き戻す。このような処理において、ＲＡＭ２０２０は、外部記憶装置の内容を一時的に保持するものとみなせるから、本実施形態においてはＲＡＭ２０２０及び外部記憶装置等をメモリ、記憶部、または記憶装置等と総称する。

本実施形態における各種のプログラム、データ、テーブル、データベース等の各種の情報は、このような記憶装置上に格納されて、情報処理の対象となる。なお、ＣＰＵ２０００は、ＲＡＭ２０２０の一部をキャッシュメモリに保持し、キャッシュメモリ上で読み書きを行うこともできる。このような形態においても、キャッシュメモリはＲＡＭ２０２０の機能の一部を担うから、本実施形態においては、区別して示す場合を除き、キャッシュメモリもＲＡＭ２０２０、メモリ、及び／又は記憶装置に含まれるものとする。

また、ＣＰＵ２０００は、ＲＡＭ２０２０から読み出したデータに対して、プログラムの命令列により指定された、本実施形態中に記載した各種の演算、情報の加工、条件判断、情報の検索・置換等を含む各種の処理を行い、ＲＡＭ２０２０へと書き戻す。例えば、ＣＰＵ２０００は、条件判断を行う場合においては、本実施形態において示した各種の変数が、他の変数または定数と比較して、大きい、小さい、以上、以下、等しい等の条件を満たすか否かを判断し、条件が成立した場合（又は不成立であった場合）に、異なる命令列へと分岐し、またはサブルーチンを呼び出す。

また、ＣＰＵ２０００は、記憶装置内のファイルまたはデータベース等に格納された情報を検索することができる。例えば、第１属性の属性値に対し第２属性の属性値がそれぞれ対応付けられた複数のエントリが記憶装置に格納されている場合において、ＣＰＵ２０００は、記憶装置に格納されている複数のエントリの中から第１属性の属性値が指定された条件と一致するエントリを検索し、そのエントリに格納されている第２属性の属性値を読み出すことにより、所定の条件を満たす第１属性に対応付けられた第２属性の属性値を得ることができる。

以上に示したプログラム又はモジュールは、外部の記録媒体に格納されてもよい。記録媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤ又はＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワーク又はインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。

以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。

特許請求の範囲、明細書、および図面中において示した装置、システム、プログラム、および方法における動作、手順、ステップ、および段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り、任意の順序で実現しうることに留意すべきである。特許請求の範囲、明細書、および図面中の動作フローに関して、便宜上「まず、」、「次に、」等を用いて説明したとしても、この順で実施することが必須であることを意味するものではない。

１０ 生成装置、１１０ 入力部、１２０ 算出部、１３０ 初期化部、１４０ 生成部、２０ 選択装置、２１０ 取得部、２２０ 利得選択部、２３０ 入力選択部、２４０ 遷移部、３０ 生成装置、３１０ 入力部、３２０ 算出部、３３０ 初期化部、３４０ 生成部、３５０ 設定部、３６０ 選択部、４０ 選択装置、４１０ 取得部、４２０ 利得選択部、４３０ 入力選択部、４４０ 遷移部、１０００ データベース、１９００ コンピュータ、２０００ ＣＰＵ、２０１０ ＲＯＭ、２０２０ ＲＡＭ、２０３０ 通信インターフェイス、２０４０ ハードディスクドライブ、２０５０ フレキシブルディスク・ドライブ、２０６０ ＣＤ−ＲＯＭドライブ、２０７０ 入出力チップ、２０７５ グラフィック・コントローラ、２０８０ 表示装置、２０８２ ホスト・コントローラ、２０８４ 入出力コントローラ、２０９０ フレキシブルディスク、２０９５ ＣＤ−ＲＯＭ

Claims (16)

1. 観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルについて、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に生成する、コンピュータにより実行される生成方法であって、
   隠れ状態毎に累積利得の成分を含む利得ベクトルのうち利得ベクトルの集合に含めるベクトルを選択するために用いる選択用の前記隠れ状態の確率分布を設定する設定段階と、
   選択用の前記確率分布について前記累積期待利得の最大値を与える利得ベクトルを優先して前記利得ベクトルの集合に含める選択段階と、
   を備える生成方法。
2. 前記利得ベクトルの集合を、将来の時点から前記基準時点へと遡って再帰的に生成する生成段階を更に備える、
   請求項１に記載の生成方法。
3. 前記設定段階は、選択用の前記確率分布に、長さが隠れ状態の数となり、各隠れ状態について当該隠れ状態に対応する成分を１としたベクトルを、選択用の前記確率分布として設定する段階を含む、
   請求項２に記載の生成方法。
4. 前記設定段階は、前記生成段階において生成した前記利得ベクトルの集合の中から前記累積期待利得の最大値を返す前記利得ベクトルに対応する入力が選択された場合に、選択された前記入力に応じて更新される隠れ状態の確率分布を選択用の前記確率分布として設定する段階を含む、
   請求項２又は３に記載の生成方法。
5. 前記将来の時点Ｎ（但し、Ｎは２以上の整数）における利得ベクトルの集合を初期化する初期化段階を更に備える請求項２から４のいずれか１項に記載の生成方法。
6. 前記生成段階は、
   時点ｎにおける可視状態ｓ（ｓ∈Ｓ、Ｓは可視状態の集合）についての利得ベクトルα_ｓ，ｎの集合Λ_ｎ（ｓ）を、次の時点ｎ＋１における各可視状態ｓ'（ｓ'∈Ｓ）についての利得ベクトルα_{ｓ'，ｎ＋１}の集合Λ_ｎ＋１（ｓ'）に基づいて再帰的に生成する段階を含む、
   請求項２から５のいずれか１項に記載の生成方法。
7. 前記生成段階は、一の可視状態ｓから別の可視状態ｓ'に遷移する状態遷移確率、及び、可視状態ｓ'における期待利得に更に基づいて、利得ベクトルα_ｓ，ｎの集合Λ_ｎ（ｓ）を生成する段階を含む、
   請求項６に記載の生成方法。
8. 請求項１から６のいずれか１項に記載の生成方法と、
   観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルにおいて最適な入力を選択する選択方法であって、
   前記生成方法において生成した利得ベクトルの集合を取得する取得段階、
   現在の可視状態に応じた前記利得ベクトルの中から、現時点における隠れ状態の確率分布に対し累積期待利得を最大化する前記利得ベクトルを選択する利得選択段階、及び、
   選択した前記利得ベクトルに対応する入力を、最適な入力として選択する入力選択段階を有する選択方法と、
   をコンピュータにより実行する情報処理方法。
9. 前記取得段階は、隠れ状態ｉにおいて一の入力ａをしたときに状態集合Ｓにおいて一の可視状態ｓから別の可視状態ｓ'に遷移する状態遷移確率Ｐ^ａ _{ｓ，ｉ，ｓ'}を取得し、
   前記選択段階は、前記入力選択段階で選択された入力ａを実行したことに応じて、前記選択された入力ａに対応する前記状態遷移確率Ｐ^ａ _{ｓ，ｉ，ｓ'}及び現在の隠れ状態の確率分布に基づき、可視状態ｓを遷移させる遷移段階を更に備える、
   請求項８に記載の情報処理方法。
10. 前記遷移段階は、前記状態遷移確率Ｐ^ａ _{ｓ，ｉ，ｓ'}及び現在の隠れ状態の確率分布に基づき、隠れ状態の確率分布ｂを更新する段階を含む、
    請求項９に記載の情報処理方法。
11. 前記遷移段階は、前記入力選択段階で選択された入力に応じて、隠れ状態ｉをとる確率ｂ（ｉ）に数式（１）の計算結果を代入することにより隠れ状態の確率分布ｂを更新する段階を含む、
    

    

    …数式（１）
    （但し、P^a _s,i;s'は隠れ状態ｉ及び可視状態ｓにおいて入力ａにより可視状態ｓから可視状態ｓ'に遷移する状態遷移確率を示す。）
    請求項１０に記載の情報処理方法。
12. 前記遷移段階は、前記入力選択段階で選択された入力に応じて、隠れ状態ｉをとる確率ｂ（ｉ）に数式（２）の計算結果を代入することにより隠れ状態の確率分布ｂを更新する段階を含む、
    

    

    …数式（２）
    （但し、P^a _s,i;s'は隠れ状態ｉ及び可視状態ｓにおいて入力ａにより可視状態ｓから可視状態ｓ'に遷移し、観測ｚが観測される状態遷移確率を示す。）
    請求項１０に記載の情報処理方法。
13. 前記設定段階は、前記遷移段階で更新した確率分布を選択用の確率分布として設定する段階を含む、
    請求項９から１２のいずれか１項に記載の情報処理方法。
14. 前記選択方法において、予め定められた期間について入力を選択して、前記確率分布の更新を実行することと、
    前記生成方法において、前記選択方法により前記更新された確率分布を受け取り、当該確率分布ｂを前記選択用の確率分布として前記利得ベクトルの集合を更新することとを繰り返す、
    請求項１３に記載の情報処理方法。
15. 観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルについて、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に生成する生成装置であって、
    隠れ状態毎に累積利得の成分を含む利得ベクトルのうち利得ベクトルの集合に含めるベクトルを選択するために用いる選択用の前記隠れ状態の確率分布を設定する設定部と、
    選択用の前記確率分布について前記累積期待利得の最大値を与える利得ベクトルを優先して前記利得ベクトルの集合に含める選択部と、
    を備える生成装置。
16. コンピュータを、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルについて、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に生成する生成装置として機能させるプログラムであって、実行されると当該コンピュータを、
    隠れ状態毎に累積利得の成分を含む利得ベクトルのうち利得ベクトルの集合に含めるベクトルを選択するために用いる選択用の前記隠れ状態の確率分布を設定する設定部と、
    選択用の前記確率分布について前記累積期待利得の最大値を与える利得ベクトルを優先して前記利得ベクトルの集合に含める選択部として機能させる、
    プログラム。

Images