(57)【要約】      （修正有）【課題】観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルにおける最適施策を高速に算出する。【解決手段】観測可能な可視状態、及び、観測不能な隠れ状態を備え、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルについて、基準時点以降の累積期待利得を算出するための利得ベクトルの集合を可視状態毎に生成する生成装置であって、隠れ状態毎に累積期待利得の成分を含む利得ベクトルを少なくとも１つ含み累積期待利得の最大値を与える利得ベクトルが選択されるべき利得ベクトルの集合を将来の時点から基準時点へと遡って再帰的に生成する生成部を備える。【選択図】図３
2015176328.tif 000002
【特許請求の範囲】
【請求項１】
観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する前記遷移モデルについて、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に生成する、コンピュータにより実行される生成方法であって、
隠れ状態毎に累積期待利得の成分を含む利得ベクトルを少なくとも１つ含み前記累積期待利得の最大値を与える利得ベクトルが選択されるべき前記利得ベクトルの集合を、将来の時点から前記基準時点へと遡って再帰的に生成する生成段階を備える、
生成方法。
【請求項２】
前記将来の時点Ｎ（但し、Ｎは２以上の整数）における利得ベクトルの集合を初期化する初期化部を更に備える請求項１に記載の生成方法。
【請求項３】
前記生成段階は、
時点ｎにおける可視状態ｓ（ｓ∈Ｓ、Ｓは可視状態の集合）についての利得ベクトルαｓ，ｎの集合Λｎ（ｓ）を、次の時点ｎ＋１における１以上の各可視状態ｓ'（ｓ'∈Ｓ）についての利得ベクトルαｓ'，ｎ＋１の集合Λｎ＋１（ｓ'）に基づいて再帰的に生成する段階を含む、
請求項１又は２に記載の生成方法。
【請求項４】
前記生成段階は、入力に応じて時点ｎにおける一の可視状態ｓから時点ｎ＋１における可視状態ｓ'に遷移する状態遷移確率、及び、可視状態ｓ'において入力に応じて得られる期待利得に更に基づいて、利得ベクトルαｓ，ｎの集合Λｎ（ｓ）を生成する段階を含む、
請求項３に記載の生成方法。
【請求項５】
生成段階は、各時点ｎ及び各可視状態ｓにおいて、利得ベクトルの集合Λｎ（ｓ）に含まれる利得ベクトルαｓ，ｎの集合から、隠れ状態ｉの確率分布の少なくとも一部の範囲において最大値を構成する利得ベクトル以外を除去する段階を含む、
請求項３又は４に記載の生成方法。
【請求項６】
前記生成段階は、更に割引率γに基づいて、時点ｎの可視状態ｓに対応する利得ベクトルの集合Λｎ（ｓ）を生成する段階を含む、
請求項５に記載の生成方法。
【請求項７】
前記生成段階は、前記利得ベクトルの集合から、隠れ状態の確率分布に応じて基準時点以降の累積期待利得が最大となる利得ベクトルを選択する選択関数を生成する段階を含む、
請求項１から６のいずれか１項に記載の生成方法。
【請求項８】
前記生成段階は、各隠れ状態を取る確率に利得ベクトルの各成分を乗じた合計値に基づく累積期待利得が最大となる利得ベクトルを選択する選択関数を生成する段階を含む、
請求項７に記載の生成方法。
【請求項９】
前記生成段階は、
前記隠れ状態の確率分布における隠れ状態ｉを取る確率ｂ（ｉ）、及び、時点ｎの可視状態ｓに対応するｋ番目の利得ベクトルαｓ，ｎｋの隠れ状態ｉに対応する成分αｓ，ｎｋ（ｉ）に基づき、
数式（１）（但し、Ｎは前記基準時点の時点を表す２以上の整数）に示される前記選択関数Ｋｍａｘｎ（ｓ，ｂ）を生成する段階を含む、
【数１】
2015176328.tif 000007
…数式（１）
請求項８に記載の生成方法。
【請求項１０】
観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルにおいて最適な入力を選択する、コンピュータにより実行される選択方法であって、
隠れ状態毎に累積期待利得の成分を含む利得ベクトルを少なくとも１つ含み基準時点以降の累積期待利得を算出するための利得ベクトルの集合を可視状態毎に取得する取得段階と、
現在の可視状態に応じた前記利得ベクトルの中から、現時点における隠れ状態の確率分布に対し累積期待利得を最大化する前記利得ベクトルを選択する利得選択段階と、
選択した前記利得ベクトルに対応する入力を、最適な入力として選択する入力選択段階と、
を備える選択方法。
【請求項１１】
前記取得段階は、請求項１から６のいずれか１項に記載の生成方法により生成された利得ベクトルの集合を取得する段階を含む、
請求項１０に記載の選択方法。
【請求項１２】
前記利得選択段階は、前記利得ベクトルの集合から、数式（１）で表される隠れ状態ｉを取る確率ｂ（ｉ）、及び、時点ｎの可視状態ｓに対応するｋ番目の利得ベクトルαｓ，ｎｋの隠れ状態ｉに対応するαｓ，ｎｋ（ｉ）に基づく選択関数Ｋｍａｘｎ（ｓ，ｂ）を生成する段階と、
前記選択関数Ｋｍａｘｎ（ｓ，ｂ）に基づき前記隠れ状態の確率分布ｂに対応して決定される利得ベクトルαｓ，ｎｋ（ｉ）を選択する段階を含む、
【数２】
2015176328.tif 000008
…数式（１）
請求項１１に記載の選択方法。
【請求項１３】
前記取得段階は、隠れ状態ｉにおいて一の入力ａをしたときに状態集合Ｓにおいて一の可視状態ｓから別の可視状態ｓ'に遷移する状態遷移確率Ｐａｓ，ｉ，ｓ'を取得する段階を含み、
前記入力選択段階で選択された入力ａを実行したことに応じて、前記選択された入力ａに対応する前記状態遷移確率Ｐａｓ，ｉ，ｓ'及び現在の隠れ状態の確率分布に基づき、可視状態ｓを遷移させる遷移段階を更に備える、
請求項１０から１２のいずれか１項に記載の選択方法。
【請求項１４】
前記遷移段階は、前記状態遷移確率Ｐａｓ，ｉ，ｓ'及び現在の隠れ状態の確率分布に基づき、隠れ状態の確率分布ｂを更新する段階を含む、
請求項１３に記載の選択方法。
【請求項１５】
前記遷移段階は、前記入力選択段階において選択された入力に応じて、隠れ状態ｉをとる確率ｂ（ｉ）に数式（２）の計算結果を代入することにより隠れ状態の確率分布ｂを更新する段階を含む、
【数３】
2015176328.tif 000009
…数式（２）
（但し、Ｐａｓ，ｉ；ｓ'は隠れ状態ｉ及び可視状態ｓにおいて入力ａにより可視状態ｓから可視状態ｓ'に遷移する状態遷移確率を示す。）
請求項１４に記載の選択方法。
【請求項１６】
前記遷移段階は、前記入力選択段階において選択された入力に応じて、隠れ状態ｉをとる確率ｂ（ｉ）に数式（３）の計算結果を代入することにより隠れ状態の確率分布ｂを更新する段階を含む、
【数４】
2015176328.tif 000010
…数式（３）
（但し、Ｐａｓ，ｉ；ｓ'，ｚは隠れ状態ｉ及び可視状態ｓにおいて入力ａにより可視状態ｓから可視状態ｓ'に遷移し、観測ｚが観測される状態遷移確率を示す。）
請求項１４に記載の選択方法。
【請求項１７】
観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルについて、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に生成する生成装置であって、
隠れ状態毎に累積期待利得の成分を含む利得ベクトルを少なくとも１つ含み前記累積期待利得の最大値を与える利得ベクトルが選択されるべき前記利得ベクトルの集合を将来の時点から前記基準時点へと遡って再帰的に生成する生成部を備える、
生成装置。
【請求項１８】
コンピュータを、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルについて、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に生成する生成装置として機能させるプログラムであって、実行されると当該コンピュータを、
隠れ状態毎に累積期待利得の成分を含む利得ベクトルを少なくとも１つ含み前記累積期待利得の最大値を与える利得ベクトルが選択されるべき前記利得ベクトルの集合を将来の時点から前記基準時点へと遡って再帰的に生成する生成部として機能させる、
プログラム。
【請求項１９】
観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルにおいて最適な入力を選択する選択装置であって、
隠れ状態毎に累積期待利得の成分を含む利得ベクトルを少なくとも１つ含み基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に取得する取得部と、
現在の可視状態に応じた利得ベクトルの中から、現時点における隠れ状態の確率分布に対し累積期待利得を最大化する利得ベクトルを選択する利得選択部と、
選択した利得ベクトルに対応する入力を、最適な入力として選択する入力選択部と、
を備える選択装置。
【請求項２０】
コンピュータを、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルにおいて最適な入力を選択する選択装置として機能させるプログラムであって、
実行させると当該コンピュータを、
隠れ状態毎に累積期待利得の成分を含む利得ベクトルを少なくとも１つ含み基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に取得する取得部と、
現在の可視状態に応じた利得ベクトルの中から、現時点における隠れ状態の確率分布に対し累積期待利得を最大化する利得ベクトルを選択する利得選択部と、
選択した利得ベクトルに対応する入力を、最適な入力として選択する入力選択部と、
として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、生成装置、選択装置、生成方法、選択方法、及び、プログラムに関する。
【背景技術】
【０００２】
観測可能でない状態を含む環境における逐次的意思決定は部分観測マルコフ決定過程（ＰＯＭＤＰ）として定式化されていた（特許文献１〜３）。しかし、意思決定問題の中には、状態の観測可能性や不変性が定まっている場合、例えば、状態の一部が完全に観測可能で残りが観測不可能な場合がある。また、観測不可能な部分が不変である場合がある。従来は、このような場合においても汎用のＰＯＭＤＰソルバにより最適施策を算出していた。
［特許文献１］特開２０１１−５３７３５号公報
［特許文献２］特開２０１２−１２３５２９号公報
［特許文献３］特開２０１２−１９００６２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００３】
完全に観測可能な可視状態、及び、観測不可能な隠れ状態を備える遷移モデルにおける最適施策を高速に算出することを課題とする。
【課題を解決するための手段】
【０００４】
本発明の第１の態様においては、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルについて、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に生成する生成装置であって、隠れ状態毎に累積期待利得の成分を含む利得ベクトルを少なくとも１つ含み累積期待利得の最大値を与える利得ベクトルが選択されるべき利得ベクトルの集合を将来の時点から基準時点へと遡って再帰的に生成する生成部を備える生成装置、生成装置を用いた生成方法、及び生成装置に用いるプログラムを提供する。
【０００５】
本発明の第２の態様においては、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルにおいて最適な入力を選択する選択装置であって、隠れ状態毎に累積期待利得の成分を含む利得ベクトルを少なくとも１つ含み基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を可視状態毎に取得する取得部と、現在の可視状態に応じた利得ベクトルの中から、現時点における隠れ状態の確率分布に対し累積期待利得を最大化する利得ベクトルを選択する利得選択部と、選択した利得ベクトルに対応する入力を、最適な入力として選択する入力選択部とを備える選択装置、選択装置を用いる選択方法、及びプログラムを提供する。
【０００６】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではない。また、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【図面の簡単な説明】
【０００７】
【図１】本実施形態の情報処理システムの概要を示す。
【図２】本実施形態に係る可視状態ｓ及び隠れ状態ｂの一例を示す。
【図３】本実施形態の生成装置１０の処理フローを示す。
【図４】本実施形態における生成部１４０による集合Λｎ（ｓ）の生成方法の一例を示す。
【図５】図３における処理フローの具体的アルゴリズムの一例を示す。
【図６】集合Λｓ，ｎと累積期待利得の関係を示す。
【図７】図３における処理フローの具体的アルゴリズムの別の一例を示す。
【図８】本実施形態の選択装置２０の処理フローを示す。
【図９】コンピュータ１９００のハードウェア構成の一例を示す。
【発明を実施するための形態】
【０００８】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【０００９】
図１は、本実施形態の情報処理システムを示す。本実施形態の情報処理システムは、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力及び／又は隠れ状態に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルを定式化した利得ベクトルの集合を生成し、利得ベクトルの集合に基づいて最適な入力を選択する。
【００１０】
例えば、消費者が特定の商品（例えば、家電製品）のテレビＣＭを視聴した後の状態か、及び、消費者が特定の商品に興味を持った状態かは観測不能な隠れ状態となるが、消費者が特定の商品のＷｅｂ広告を閲覧した状態であるかはクッキー等により観測可能な可視状態である。
【００１１】
本実施形態の情報処理システムは、このような遷移モデルを定式化し、消費者から得られる期待利得（例えば、売り上げ）を最大化するための入力（例えば、テレビＣＭ、ダイレクトメール、及び、Ｅメール等）を選択する。本実施形態の情報処理システムは、利得ベクトルの集合を生成する生成装置１０と、利得ベクトルの集合に従って最適な入力を選択する選択装置２０を有する。
【００１２】
生成装置１０は、学習用データに基づいて基準時点以降で予め定められた将来の時点までの各時点の期待利得を累積した累積期待利得の成分を隠れ成分毎に含み、累積期待利得の算出に用いることができる利得ベクトルの集合を可視状態毎に生成する。生成装置１０は、一例として、コンピュータ上でソフトウェアを実行することにより実現される。生成装置１０は、入力部１１０、算出部１２０、初期化部１３０、及び、生成部１４０を備える。
【００１３】
入力部１１０は、外部のデータベース１０００等の記憶装置又は生成装置１０の内部から利得ベクトルの集合を生成するための学習用データを入力する。入力部１１０は、学習用データを算出部１２０に提供する。学習用データは、例えば、消費者の購買履歴及び行動履歴等であってよい。
【００１４】
算出部１２０は、学習用データから各可視状態からの遷移確率を表す状態遷移確率、及び、各可視状態において入力に応じて期待される利得である期待利得を算出する。算出部１２０は、状態遷移確率、及び、期待利得を生成部１４０に供給する。
【００１５】
初期化部１３０は、選択関数に用いられる可視状態毎の利得ベクトルの集合を、遷移モデルが対象とする期間全体において算出するのに先立って、予め定められた将来の時点（例えば、期間の最後の時点）における利得ベクトルの集合を初期化する。例えば、初期化部１３０は、将来のある時点における可視状態毎の利得ベクトルの集合をゼロベクトルの集合とすることにより初期化する。初期化部１３０は、初期化された利得ベクトルの集合を生成部１４０に提供する。
【００１６】
生成部１４０は、状態遷移確率及び期待利得に基づいて、基準時点以降の累積期待利得の算出に用いられる少なくとも１つの利得ベクトルを有し、累積期待利得の最大値を与える利得ベクトルが選択されるべき利得ベクトルの集合を、将来の時点から遡って再帰的に生成する。また、生成部１４０は、生成した利得ベクトルの集合から基準時点における累積期待利得が最大となる利得ベクトルが選択される選択関数を生成してよい。生成部１４０による利得ベクトルの集合等の詳細な生成方法については追って説明する。
【００１７】
また、生成部１４０は、利得ベクトルの集合を生成するときに入力と利得ベクトルとの対応付けを含む入力対応情報を生成する。生成部１４０は、生成した利得ベクトルの集合、状態遷移確率、及び、入力対応情報を選択装置２０に供給してよい。生成部１４０は、利得ベクトルの集合に代えて選択関数を選択装置２０に供給してもよい。
【００１８】
選択装置２０は、観測可能な可視状態、及び、観測不能な隠れ状態を備える遷移モデルであって、入力及び／又は隠れ状態に応じて現在の可視状態から次の可視状態へと遷移する遷移モデルにおいて、利得ベクトルの集合に基づいて最適な入力を選択する。例えば、選択装置は、利得を最大化させる施策を最適な入力として選択する。選択装置２０は、一例として、コンピュータ上でソフトウェアを実行することにより実現される。選択装置２０は、取得部２１０、利得選択部２２０、入力選択部２３０、及び、遷移部２４０を有する。
【００１９】
取得部２１０は、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合を取得する。例えば、取得部２１０は、生成装置１０が生成した利得ベクトルの集合を取得してよい。
【００２０】
また、取得部２１０は、状態遷移確率、及び、入力対応情報を生成装置１０から取得してよい。取得部２１０は、取得した利得ベクトルの集合及び入力対応情報を利得選択部２２０に供給する。また、取得部２１０は、状態遷移確率を遷移部２４０に供給する。
【００２１】
利得選択部２２０は、利得ベクトルの集合に基づいて、現在の可視状態に応じた利得ベクトルの中から、現時点における隠れ状態の確率分布に対し累積期待利得を最大化する利得ベクトルを選択する。例えば、利得選択部２２０は、利得ベクトルの集合から一の利得ベクトルを選択する選択関数を生成し、当該選択関数に基づいて累積期待利得を最大化する利得ベクトルを選択する。利得選択部２２０は、選択した利得ベクトル及び入力対応情報を入力選択部２３０に供給する。
【００２２】
入力選択部２３０は、入力対応情報に基づき、利得選択部２２０が選択した利得ベクトルに対応する入力を最適な入力として選択する。入力選択部２３０は、例えば、累積期待利得を最大化する施策を最適な入力として選択する。入力選択部２３０は、選択した入力を遷移部２４０に供給する。
【００２３】
遷移部２４０は、入力選択部２３０に選択された入力に対応する状態遷移確率、及び、現在の隠れ状態の確率分布に基づき、可視状態を確率的に遷移させる。また、遷移部２４０は、選択された入力に応じて、隠れ状態の確率分布を更新する。遷移部２４０は、更新した可視状態及び隠れ状態の確率分布を利得選択部２２０に供給し、再度、利得選択部２２０に可視状態及び隠れ状態の確率分布に基づき利得ベクトルを選択させる。
【００２４】
このように、本実施形態の情報処理システムによると、観測可能な可視状態が遷移する遷移モデルに再帰的手法を適用することにより、生成装置１０が利得ベクトルの集合を高速に生成することができる。また、選択装置２０は、生成装置１０が生成した利得ベクトルの集合に基づいて最適な入力を選択することができる。
【００２５】
図２は、本実施形態に係る遷移モデルの可視状態ｓ及び隠れ状態ｂの一例を示す。図示するように、本実施形態の情報処理システムは、観測可能な可視状態ｓ１、ｓ２、ｓ３…及び観測不可能な隠れ状態ｂ１、ｂ２、ｂ３…を有する。本実施形態において、可視状態、及び、隠れ状態は、図示するようにそれぞれ独立して与えられる。
【００２６】
すなわち、本実施形態において、可視状態のいずれか（例えば、可視状態ｓ２）と隠れ状態のいずれか（例えば、隠れ状態ｂ２）が同時に与えられる。例えば、ウェブベースの販売サイトにおいて、顧客との間の商取引により得られる累積期待利得を最大化するマーケティング施策を出力するアプリケーションを本実施形態の情報処理システムに適用する場合、顧客に対して行ったマーケティング施策及び顧客の反応は外部から観測できる可視状態であり、隠れ状態は顧客の嗜好等の外部から直接観測できない状態であってよい。
【００２７】
そして、本実施形態の情報処理システムは、期間中に可視状態は遷移し得るが（例えば、可視状態ｓ２→ｓ１又はｓ３等）、隠れ状態間では遷移しない（例えば、隠れ状態ｂ２のまま遷移しない）遷移モデルを扱う。
【００２８】
なお、隠れ状態は観測不可能なので、実際には図示するように一の隠れ状態ｂ２を特定することはできず、それぞれの隠れ状態ｉにある確率を表す確率分布ｂ｛ｂ（ｉ）｜ｉ＝１，...，｜Ｂ｜｝のみが算出される。可視状態の状態遷移の結果、どの隠れ状態にあるかの確からしさが間接的に判明していく場合があり、確率分布ｂは遷移し得る。例えば、隠れ状態ｂ２において可視状態ｓ２→ｓ１に遷移する確率が非常に高い場合、時点ｔから時点ｔ＋１において可視状態ｓ２→ｓ１が観測されたことに応じて、時点ｔ＋１における確率分布ｂにおいて隠れ状態ｂ２を与える確率が高くなる。
【００２９】
図３は、本実施形態の生成装置１０の処理フローを示す。本実施形態において、生成装置１０は、Ｓ１１０〜Ｓ１６０の処理を実行することにより、利得ベクトルの集合を生成する。
【００３０】
まず、Ｓ１１０において、入力部１１０は、外部又は生成装置１０内部のデータベース１０００から学習用データを取得する。例えば、入力部１１０は、可視状態、入力の内容、及び、観測結果等が予め時系列で定義されたデータを学習用データとして入力してよい。
【００３１】
これに代えて、入力部１１０は、可視状態が定義されていないデータを学習用データとして取得してもよい。一例として、入力部１１０は、まず、複数の消費者に対して提供された広告等の施策、及び、消費者の商品購入等の行動履歴等を取得してよい。次に、入力部１１０は、行動履歴等から状態ベクトルの時系列を生成し、状態ベクトルを離散化することで可視状態を定義してもよい。
【００３２】
また、入力部１１０は、学習用データとして、隠れ状態の推測に利用できるデータを取得してよい。例えば、入力部１１０は、学習用データとして消費者の嗜好等が記載されたアンケート結果を取得してよい。入力部１１０は、アンケート結果等から特徴ベクトルを生成し、特徴ベクトルを離散化することで隠れ状態を定義してもよい。入力部１１０は、学習用データを算出部１２０に提供する。
【００３３】
Ｓ１２０において、算出部１２０は、学習用データから状態遷移確率及び期待利得を算出する。例えば、算出部１２０は、学習用データから互いに遷移可能な１以上の可視状態ｓ（ｓ∈Ｓ）、及び、互いに遷移しない１以上の隠れ状態ｉ（ｉ∈Ｂ）を定義し、可視状態ｓ、隠れ状態ｉにおいて入力ａを実行したときに可視状態ｓから可視状態ｔに遷移し、zが観測される状態遷移確率Ｐａｓ，ｉ；ｔ，ｚと、可視状態ｓ及び隠れ状態ｉにおいて入力ａを実行したときの期待利得ｑａｓ（ｉ）を算出する。算出部１２０は、Ｑ学習などの強化学習法により状態遷移確率Ｐａｓ，ｉ；ｔ，ｚ及び期待利得ｑａｓ（ｉ）を算出してよい。算出部１２０は、算出した状態遷移確率Ｐａｓ，ｉ；ｔ，ｚ及び期待利得ｑａｓ（ｉ）を生成部１４０に供給する。
【００３４】
次に、Ｓ１３０において、初期化部１３０は、遷移モデルにおける将来の時点Ｎ（Ｎは２以上の整数）における可視状態ｓについての利得ベクトルαｓ，Ｎの集合ΛＮ（ｓ）を初期化する。例えば、初期化部１３０は、αｓ，Ｎの集合ΛＮ（ｓ）を長さが隠れ状態の数｜Ｂ｜と同じ数のゼロベクトルだけからなる集合｛（０，...，０）｝として集合ΛＮ（ｓ）を初期化する。また、初期化部１３０は、ｎ＝Ｎ−１としてｎを初期化する。初期化部１３０は、初期化された集合ΛＮ（ｓ）等を生成部１４０に提供する。
【００３５】
次に、Ｓ１４０において、生成部１４０は、１≦ｎ≦Ｎ−１となるｎについて利得ベクトルαｓ，ｎの集合Λｎ（ｓ）を集合Λｎ＋１（ｓ）から生成する。生成部１４０が生成する利得ベクトルαｓ，ｎの集合Λｎ（ｓ）は、隠れ状態ｉ毎に累積期待利得の成分αｓ，ｎ（ｉ）を有する利得ベクトルαｓ，ｎを少なくとも１つ含む。
【００３６】
図４は、本実施形態における生成部１４０による集合Λｎ（ｓ）の生成方法の一例を示す。生成部１４０は、時点ｎにおける可視状態ｓ（ｓ∈Ｓ、Ｓは可視状態の集合）についての利得ベクトルαｓ，ｎの集合Λｎ（ｓ）を、次の時点ｎ＋１における各可視状態ｓ'（ｓ'∈Ｓ）についての利得ベクトルαｓ'，ｎ＋１の集合Λｎ＋１（ｓ'）に基づいて再帰的に生成する。
【００３７】
例えば、図示するように可視状態ｓ１が可視状態ｓ１、ｓ２及びｓ３を含む場合、生成部１４０は、時点ｎ＋１の利得ベクトルの集合Λｎ＋１（１）、Λｎ＋１（２）、及び、Λｎ＋１（３）から時点ｎの利得ベクトルの集合Λｎ（１）を生成してよい。生成部１４０は、利得ベクトルの集合を、入力に応じて一の可視状態ｓから時点ｎ＋１の可視状態ｓ'に遷移する状態遷移確率、及び、可視状態ｓ'において入力に応じて得られる期待利得に基づいて生成する。この具体的な生成方法は後述する。
【００３８】
ここで、生成部１４０は、生成した利得ベクトルαｓ，ｎの集合Λｎ（ｓ）に基づいて、可視状態ｓ及び隠れ状態の確率分布ｂに応じて基準時点ｎ以降の累積期待利得が最大となる利得ベクトルを選択する選択関数Ｋｍａｘｎ（ｓ，ｂ）を生成してよい。例えば、生成部１４０は、確率分布ｂにおける各隠れ状態ｉを取る確率に利得ベクトルの各成分を乗じた合計値に基づく累積期待利得が最大となる利得ベクトルを選択する選択関数を生成する。
【００３９】
一例として、生成部１４０は、数式（１）に示す選択関数Ｋｍａｘｎ（ｓ，ｂ）を生成する。なお、ｂ（ｉ）は隠れ状態の確率分布における隠れ状態ｉを取る確率を示し、αｓ，ｎｋ（ｉ）は、時点ｎにおける可視状態ｓに対応するｋ番目の利得ベクトルαｓ，ｎｋの隠れ状態ｉに対応する成分を示す。また、生成部１４０は、選択関数Ｋｍａｘｎ（ｓ，ｂ）を生成する過程において、入力と利得ベクトルとの対応付けを含む入力対応情報を生成する。
【数１】
2015176328.tif 000003
…数式（１）
【００４０】
次に、Ｓ１５０において、生成部１４０は、ｎから１を減じて処理をＳ１６０に進める。
【００４１】
次に、Ｓ１６０において、生成部１４０は、ｎ＝０となるか否かを判断する。ｎ＝０となる場合、生成部１４０は処理を終了し、そうでない場合は処理をＳ１４０に戻す。これにより、生成部１４０は、ｎがＮから０になるまで利得ベクトルの集合Λｎ（ｓ）、及び／又は、選択関数Ｋｍａｘｎ（ｓ，ｂ）を再帰的に生成する。
【００４２】
このように生成装置１０は、学習用データからまず状態遷移確率Ｐａｓ，ｉ；ｔ，ｚ、及び、期待利得ｑａｓ（ｉ）を算出し、これらに基づいて利得ベクトルの集合Λｎ＋１（ｓ）からΛｎ（ｓ）を再帰的に算出する。生成装置１０は、隠れ状態ｂが遷移しないモデルにおける利得ベクトルの集合Λｎ（ｓ）を生成するので処理をより高速化することができる。
【００４３】
なお、遷移しない隠れ状態ｂは、環境中において短時間で変化しにくい特性と考えることができる。例えば、生成装置１０は、通常観測することが難しくかつ長期間変化しない消費者個人の好み（例えば、食事、又は、趣味等の好み）をモデルに組み入れた上で、最適施策を選択するための利得ベクトルの集合を生成することができる。
【００４４】
また、生成装置１０は、複数のセンサを備える自律行動するロボットに用いることができる。例えば、生成装置１０は、複数のセンサのうち一部のセンサが故障した状態を遷移しない隠れ状態に当てはめることができる。例えば、生成装置１０は、故障したセンサが検出する事項を隠れた状態とおくことにより、故障したセンサを考慮した上で最適施策を選択するための利得ベクトルの集合を提供することができる。
【００４５】
また、生成装置１０は、音声認識装置に用いた会話生成装置に適用することができる。例えば、生成装置１０は、完全に聞き取れなかった会話の内容を隠れ状態と考えることができる。これにより、生成装置１０は、人の会話等を完全に聞き取れなかった場合においても、最適施策（例えば、人に対する会話の回答）を選択するための利得ベクトルの集合を提供することができる。
【００４６】
図５は、図３における処理フローの具体的アルゴリズムの一例を示す。ここでは、図５を例にＳ１４０の処理のアルゴリズムを説明する。
【００４７】
まず、１行目に示すように、生成部１４０は、時点ｎ＋１、状態ｔ（ｔ∈Ｓ）における利得ベクトルの集合Λｔ，ｎ＋１を取得する。なお、集合Λｘ（ｙ）を集合Λｘ，ｙ又は集合Λ（ｙ，ｘ）と記載する場合がある。
【００４８】
次に、２行目に示すように、生成部１４０は、時点ｎにおける全入力に対応する利得ベクトルの集合Λ＊ｓ，ｎを空集合とすることにより初期化する。
【００４９】
次に、３行目に示すように、生成部１４０は、各々の入力ａ（ａ∈Ａ、Ａは入力の集合）に対して、３〜１４行目で定義する第１ループ処理を実行する。
【００５０】
４行目に示すように、生成部１４０は、第１ループ処理内で入力ａに対応づけられた利得ベクトルの集合Λａｓ，ｎを空集合とすることにより初期化する。
【００５１】
次に、５行目に示すように、生成部１４０は、第１ループ処理内で各々の可視状態ｔ（ｔ∈Ｓ）及び観測ｚ（ｚ∈Ｚ、Ｚは観測の集合）の組み合わせに対して、５〜１２行目で定義する第２ループ処理を実行する。
【００５２】
６行目に示すように、生成部１４０は、第２ループ処理内で、ベクトル集合Φを空集合とすることにより初期化する。
【００５３】
次に、７行目に示すように、生成部１４０は、第２ループ処理内で各々の利得ベクトルα（α∈Λ＊ｓ，ｎ＋１）に対して、７〜９行目で定義する第３ループ処理を実行する。
【００５４】
８行目に示すように、生成部１４０は、第３ループ処理内でベクトル集合Φを更新する。具体的には、生成部１４０は、従前のベクトル集合Φと時点ｎ＋１における利得ベクトルαに基づいて生成される新しいベクトルの和集合を生成する。
【００５５】
生成部１４０は、各々の隠れ状態ｉについて、期待利得ｑａｓ（ｉ）を可視状態ｓの数｜Ｓ｜及び観測ｚの数｜Ｚ｜で除した値と、将来の利得に対する割引率γ（０＜γ＜１）、状態遷移確率Ｐａｓ，ｉ；ｔ，ｚ、及び、利得ベクトルαの隠れ状態ｉの成分α（ｉ）（すなわち、隠れ状態ｉに対応する累積期待利得の成分）の積の値との和を、隠れ状態ｉに対応する成分として有する、時刻ｎの新しいベクトルを生成する。
【００５６】
生成部１４０は、γ＝１とすることにより将来の利得を割り引くことなく新しいベクトルを生成してもよい。
【００５７】
次に、１０行目に示すように、生成部１４０は、第２ループ処理内で第３ループ処理の後に、更新されたベクトル集合ΦをＰｒｕｎｅ関数によって枝刈りしてよい。ここで、Ｐｒｕｎｅ関数は、入力されたベクトル集合に含まれるベクトルのうち、隠れ状態ｉの確率分布ｂの少なくとも一部の範囲において隠れ状態ｉに対応する成分が最大値を構成するベクトル以外のベクトルを入力集合から除去する。
【００５８】
次に、１１行目に示すように、生成部１４０は、第２ループ処理内で時点ｎの利得ベクトルの集合Λａｓ，ｎを生成する。具体的には、生成部１４０は、現在の利得ベクトルの集合Λａｓ，ｎに含まれるベクトルα、及び、ベクトル集合Φに含まれるベクトルα'の全ての組み合わせについて、ベクトルα及びベクトルα'の和から合算ベクトルを生成し、当該合算ベクトルをＰｒｕｎｅ関数により枝刈りすることにより、新しい利得ベクトルの集合Λａｓ，ｎを生成する。これにより、生成部１４０は、入力ａに対応する利得ベクトルの集合Λａｓ，ｎを生成するので、入力と利得ベクトルの対応情報である入力対応情報を生成することができる。
【００５９】
次に、１３行目に示すように、生成部１４０は、第１ループ処理内で第２ループ処理の後に、利得ベクトルの集合Λ＊ｓ，ｎを更新する。具体的には、生成部１４０は、集合Λ＊ｓ，ｎと集合Λａｓ，ｎとの和集合を取ることにより集合Λ＊ｓ，ｎを更新する。
【００６０】
次に、１５行目に示すように、生成部１４０は、第１ループ処理の後に、集合Λ＊ｓ，ｎを更新する。具体的には、生成部１４０は、Ｐｒｕｎｅ関数に集合Λ＊ｓ，ｎを入力することにより集合Λ＊ｓ，ｎを更新する。
【００６１】
次に、１６行目において、生成部１４０は、集合Λ＊ｓ，ｎを時点ｎ、状態ｓにおける利得ベクトルの集合として出力する。
【００６２】
このように、生成装置１０は、時点ｎ＋１の可視状態ｓにおける隠れ状態ｉ毎の期待利得ｑａｓ（ｉ）、時点ｎ＋１の可視状態ｓにおけるΛｓ，ｎ＋１、及び、割引率γに基づいて、時点ｎの可視状態ｓに対応する利得ベクトルΛｓ，ｎを生成する。
【００６３】
また、生成装置１０は、Ｐｒｕｎｅ関数により、各時点ｎ及び各可視状態ｓにおいて、集合Λｓ，ｎに含まれる利得ベクトルαｓ，ｎの集合から、隠れ状態ｉの確率分布の少なくとも一部の範囲において最大値を構成する利得ベクトル以外を除去することにより、集合Λｓ，ｎを生成する。
【００６４】
図６は、利得ベクトルの集合Λｓ，ｎと累積期待利得の関係を示す。図６（ａ）は集合Λｓ，ｎと累積期待利得との関係を示す。ここで利得ベクトルα１、α２、α３、及びα４を含む利得ベクトルの集合Λｓ，ｎを想定する。各利得ベクトルは、隠れ状態の確率分布ｂに応じた累積期待利得の値を算出するのに用いることができる。図６では説明のために便宜的に、各利得ベクトルが、確率分布ｂではなく単一の隠れ状態ｉである確率ｂ（ｉ）の値のみに応じて累積期待利得の値を返すものとして説明する。
【００６５】
例えば、隠れ状態ｉである確率ｂ（ｉ）がｂ１である場合、利得ベクトルα１はｂ１の値に応じた累積期待利得ｒ１を返し、利得ベクトルα２はｂ１の値に応じた累積期待利得ｒ２を返し、利得ベクトルα３はｂ１の値に応じた累積期待利得ｒ３を返し、利得ベクトルα４はｂ１の値に応じた累積期待利得ｒ４を返す。
【００６６】
図示するように、累積期待利得ｒ１〜ｒ４のうち最大値を取るのは累積期待利得ｒ１であるので、利得ベクトルα１〜α４の集合から確率ｂ１に応じて累積期待利得ｒ１に対応する利得ベクトルα１を選択することができる。例えば、選択関数は、確率ｂ１が入力されたことに応じて、利得ベクトルα１に対応する番号１を出力する。同様に、選択関数は、確率ｂ２に応じて累積期待利得の最大値を取る利得ベクトルα２を出力し、ｂ３に応じて累積期待利得の最大値を取る利得ベクトルα３を出力する。
【００６７】
ここで、各利得ベクトルには入力が対応付けられているので、選択関数に隠れ状態の確率分布ｂを入力することで、最適な入力を選択することができる。例えば、選択関数が利得ベクトルα１に対応する番号１を出力した場合、番号１に対応する入力を最適な入力して選択することができる。
【００６８】
図６（ｂ）は、最大値を取る利得ベクトルの部分を連結することにより得られる、累積期待利得の最大値を返す利得関数を示す。図示するように、複数の利得ベクトルα１〜α４のうち累積期待利得が最大値となる区間のみを連結すると、太線で示す下に凸が向いた区分線形凸関数となる利得関数ｖｎ（ｓ，ｂ）が得られる。利得関数ｖｎ（ｓ，ｂ）は、ｖｎ（ｓ，ｂ）＝ｍａｘ［Σｉｂ（ｉ）α（ｉ）］で表される可視状態ｓ及び隠れ状態の確率分布ｂに依存する関数となる。
【００６９】
ここで、生成部１４０は、集合Λｓ，ｎを生成する際に、Ｐｒｕｎｅ関数により累積期待利得が最大値となる区間を有しない利得ベクトル（例えば、利得ベクトルα４）を除去している。これにより、生成部１４０は、選択関数に用いる利得ベクトルから入力の選択に寄与しない無意味なものを排除し、計算をより効率化することができる。
【００７０】
図７は、図３における処理フローの具体的アルゴリズムの別の一例を示す。図７は、図５を例にＳ１４０の処理のアルゴリズムを説明する。本例のアルゴリズムは、図５で示したものと異なり、観測ｚ（ｚ∈Ｚ）を考慮せずに集合Λｎ，ｔを算出する。
【００７１】
まず、１行目に示すように、生成部１４０は、各々の可視状態ｓ（ｓ∈Ｓ）に対して、１〜１１行目で定義する第１ループ処理を実行する。
【００７２】
次に、２行目に示すように、生成部１４０は、第１ループ処理内で全入力に対応する利得ベクトルの集合Λ（ｓ，ｎ）を空集合とすることにより初期化する。
【００７３】
次に、３行目に示すように、生成部１４０は、各々の入力ａ（ａ∈Ａ）に対して、３〜１０行目で定義する第２ループ処理を実行する。
【００７４】
４行目に示すように、生成部１４０は、第２ループ処理内で入力ａに対応づけられた利得ベクトルの集合Λ（ｓ，ｎ，ａ）を空集合とすることにより初期化する。
【００７５】
次に、５行目に示すように、生成部１４０は、第２ループ処理内で各々の可視状態ｓ'（ｓ'∈Ｓ）に対して、５〜８行目で定義する第３ループ処理を実行する。ここで、可視状態ｓ'は時点ｎ＋１における可視状態を示す。
【００７６】
６行目に示すように、生成部１４０は、第３ループ処理内でベクトルの集合Λ（ｓ，ｎ，ａ，ｓ'）を生成する。具体的には、生成部１４０は、時点ｎ＋１の集合Λ（ｓ'，ｎ＋１）に含まれる各々の利得ベクトルαについて、新しいベクトルを生成する。状態遷移確率Ｐａｓ，ｉ；s'は、可視状態ｓ、隠れ状態ｉにおいて入力ａを実行したときに可視状態ｓから可視状態s'に遷移する確率を表す。
【００７７】
例えば、生成部１４０は、各々の隠れ状態ｉについて、期待利得ｑａｓ，ｉを可視状態ｓの数｜Ｓ｜で除した値と、状態遷移確率Ｐａｓ，ｉ；ｓ'、及び、利得ベクトルαの隠れ状態ｉの成分α（ｉ）の積の値との和を、新しいベクトルの隠れ状態ｉに対応する成分とすることにより利得ベクトルαから新しいベクトルを生成する。生成部１４０を、生成した新しいベクトルをＰｒｕｎｅ関数に入力することにより、集合Λ（ｓ，ｎ，ａ，ｓ'）を生成する。
【００７８】
次に、７行目に示すように、生成部１４０は、第３ループ処理内で集合Λ（ｓ，ｎ，ａ）を生成する。具体的には、生成部１４０は、集合Λ（ｓ，ｎ，ａ）に含まれるベクトルα、及び、集合Λ（ｓ，ｎ，ａ，ｓ'）に含まれるベクトルα'の全ての組み合わせについて、ベクトルα及びベクトルα'の和から合算ベクトルを生成し、当該合算ベクトルをＰｒｕｎｅ関数に入力することにより、新しい利得ベクトルの集合Λ（ｓ，ｎ，ａ）を生成する。これにより、生成部１４０は、入力ａと集合Λ（ｓ，ｎ，ａ）に含まれる利得ベクトルとを対応付けることができる。
【００７９】
次に、９行目に示すように、生成部１４０は、第２ループ処理内で第３ループ処理の後に、集合Λ（ｓ，ｎ）を更新する。具体的には、生成部１４０は、集合Λ（ｓ，ｎ）と集合Λ（ｓ，ｎ，ａ）との和集合を取ることにより集合Λ（ｓ，ｎ）を更新する。
【００８０】
図８は、本実施形態の選択装置２０の処理フローを示す。本実施形態において、選択装置２０は、Ｓ３１０〜Ｓ３８０の処理を実行することにより、最適な入力を選択する。
【００８１】
まず、Ｓ３１０において、取得部２１０は、基準時点以降の累積期待利得の算出に用いる利得ベクトルの集合Λｓ，ｎを取得する。
【００８２】
また、取得部２１０は、生成装置１０から、隠れ状態ｉにおいて一の入力ａをしたときに状態集合Ｓにおいて一の可視状態ｓから別の可視状態ｓ'に遷移する状態遷移確率Ｐａｓ，ｉ，ｓ'、及び、入力ａと利得ベクトルαｓ，ｎａとの対応付けを含む入力対応情報を取得してよい。
【００８３】
取得部２１０は、取得した利得ベクトルの集合Λｓ，ｎ及び入力対応情報を利得選択部２２０に供給する。また、取得部２１０は、状態遷移確率Ｐａｓ，ｉ，ｓ'を遷移部２４０に供給する。
【００８４】
次に、Ｓ３２０において、取得部２１０は、シミュレーションの対象となる環境の初期化処理を実行する。例えば、取得部２１０は、可視状態、及び、隠れ状態の初期条件を設定する。
【００８５】
一例として、取得部２１０は、生成装置１０がデータベース１０００から取得した学習用データにおける将来の時点における可視状態ｓ０、及び、隠れ状態の確率分布ｂ０をシミュレーションの初期条件（ｓ０，ｂ０）としてよい。また、例えば、取得部２１０は、環境の可視状態、及び、隠れ状態についての初期条件を直接データベース１０００等から取得してもよい。
【００８６】
また、取得部２１０は、時点ｎを１に設定することで初期化する。取得部２１０は、将来の時点Ｎを設定する。例えば、取得部２１０は、時点Ｎに予め定められた数を設定する。取得部２１０は、初期化の結果を利得選択部２２０に供給する。
【００８７】
次に、Ｓ３３０において、利得選択部２２０は、現在の可視状態ｓに応じた利得ベクトルαの中から、現時点における隠れ状態の確率分布ｂに対し累積期待利得を最大化する利得ベクトルαを選択する。
【００８８】
例えば、まず、利得選択部２２０は、利得ベクトルの集合Λｓ，ｎから数式（１）で表される隠れ状態ｉを取る確率ｂ（ｉ）、及び、時点ｎの可視状態ｓに対応するｋ番目の利得ベクトルαｓ，ｎｋの隠れ状態ｉに対応するαｓ，ｎｋ（ｉ）に基づく規定される選択関数Ｋｍａｘｎ（ｓ，ｂ）を生成する。
【数２】
2015176328.tif 000004
…数式（１）
【００８９】
次に、利得選択部２２０は、選択関数Ｋｍａｘｎ（ｓ，ｂ）に現在の可視状態ｓ及び隠れ状態の確率分布ｂを入力して、隠れ状態の確率分布ｂに対応して決定される利得ベクトルαｋｓ，ｎを選択する。利得選択部２２０は、利得ベクトルの集合Λｓ，ｎの代わりに取得部２１０を介して取得した選択関数Ｋｍａｘｎ（ｓ，ｂ）により利得ベクトルαｋｓ，ｎを選択してもよい。利得選択部２２０は、選択した利得ベクトルαｋｓ，ｎ及び入力対応情報を入力選択部２３０に供給する。
【００９０】
次に、Ｓ３４０において、入力選択部２３０は、利得選択部２２０が選択した利得ベクトルに対応する入力を、最適な入力として選択する。例えば、入力選択部２３０は、入力対応情報に基づき、利得ベクトルαｋｓ，ｎと予め対応付けられた入力ｋを、時点ｎにおいて実行した場合に最大の累積期待利得を与える最適な入力ｋとして選択する。入力選択部２３０は、選択した入力ｋを遷移部２４０に供給する。
【００９１】
次に、Ｓ３５０において、遷移部２４０は、入力選択部２３０に選択された入力ｋを実行したことに応じて、選択された入力に対応する状態遷移確率及び現在の隠れ状態の確率分布ｂに基づき、可視状態ｓを確率的に遷移させる。
【００９２】
すなわち、遷移部２４０は、現在の可視状態ｓを状態遷移確率Ｐｋｓ，ｉ；ｔ，ｚの確率でいずれか１つの可視状態ｔ（ｔ∈Ｓ）に遷移させる。
【００９３】
次に、遷移部２４０は、選択された入力ｋに対応する状態遷移確率Ｐｋｓ，ｉ，ｓ'，ｚ及び現在の隠れ状態の確率分布ｂに基づき、隠れ状態の確率分布ｂを更新する。例えば、遷移部２４０は、隠れ状態ｉをとる確率ｂ（ｉ）に数式（２）の計算結果を代入することにより隠れ状態の確率分布ｂを更新する。
【数３】
2015176328.tif 000005
…数式（２）
【００９４】
観測ｚを考慮しない遷移モデルの場合、遷移部２４０は、選択された入力ｋに対応する状態遷移確率Ｐｋｓ，ｉ，ｓ'及び現在の隠れ状態の確率分布ｂに基づき、隠れ状態の確率分布ｂを更新する。例えば、遷移部２４０は、隠れ状態ｉをとる確率ｂ（ｉ）に数式（３）の計算結果を代入することにより隠れ状態の確率分布ｂを更新する。
【数４】
2015176328.tif 000006
…数式（３）
【００９５】
次に、Ｓ３７０において、遷移部２４０は、ｎに１を加える。遷移部２４０は、処理をＳ３８０に進める。
【００９６】
次に、Ｓ３８０において、遷移部２４０は、ｎがＮを超えるか否かを判断する。ｎ＞Ｎとなる場合、遷移部２４０は処理を終了し、そうでない場合は処理をＳ３３０に戻す。
【００９７】
このように、選択装置２０は、生成装置１０が生成した利得ベクトルの集合Λｓ，ｎを用いて、可視状態ｓ及び隠れ状態の確率分布ｂに応じた最適な施策を選択して出力することができる。
【００９８】
図９は、生成装置１０及び／又は選択装置２０として機能するコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、及び表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有するレガシー入出力部を備える。
【００９９】
ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【０１００】
入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェイス２０３０は、有線又は無線によりネットワークを介して他の装置と通信する。また、通信インターフェイスは、通信を行うハードウェアとして機能する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。
【０１０１】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラム、及び／又は、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０を入出力コントローラ２０８４へと接続するとともに、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を入出力コントローラ２０８４へと接続する。
【０１０２】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。
【０１０３】
コンピュータ１９００にインストールされ、コンピュータ１９００を生成装置１０及び選択装置２０として機能させるプログラムは、入力モジュール、算出モジュール、初期化モジュール、生成モジュール、取得モジュール、利得選択モジュール、入力選択モジュール、及び、遷移モジュールを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、入力部１１０、算出部１２０、初期化部１３０、生成部１４０、取得部２１０、利得選択部２２０、入力選択部２３０、及び、遷移部２４０としてそれぞれ機能させてよい。
【０１０４】
これらのプログラムに記述された情報処理は、コンピュータ１９００に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である入力部１１０、算出部１２０、初期化部１３０、生成部１４０、取得部２１０、利得選択部２２０、入力選択部２３０、及び、遷移部２４０として機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ１９００の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有の生成装置１０及び選択装置２０が構築される。
【０１０５】
一例として、コンピュータ１９００と外部の装置等との間で通信を行う場合には、ＣＰＵ２０００は、ＲＡＭ２０２０上にロードされた通信プログラムを実行し、通信プログラムに記述された処理内容に基づいて、通信インターフェイス２０３０に対して通信処理を指示する。通信インターフェイス２０３０は、ＣＰＵ２０００の制御を受けて、ＲＡＭ２０２０、ハードディスクドライブ２０４０、フレキシブルディスク２０９０、又はＣＤ−ＲＯＭ２０９５等の記憶装置上に設けた送信バッファ領域等に記憶された送信データを読み出してネットワークへと送信し、もしくは、ネットワークから受信した受信データを記憶装置上に設けた受信バッファ領域等へと書き込む。このように、通信インターフェイス２０３０は、ＤＭＡ（ダイレクト・メモリ・アクセス）方式により記憶装置との間で送受信データを転送してもよく、これに代えて、ＣＰＵ２０００が転送元の記憶装置又は通信インターフェイス２０３０からデータを読み出し、転送先の通信インターフェイス２０３０又は記憶装置へとデータを書き込むことにより送受信データを転送してもよい。
【０１０６】
また、ＣＰＵ２０００は、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０（ＣＤ−ＲＯＭ２０９５）、フレキシブルディスク・ドライブ２０５０（フレキシブルディスク２０９０）等の外部記憶装置に格納されたファイルまたはデータベース等の中から、全部または必要な部分をＤＭＡ転送等によりＲＡＭ２０２０へと読み込ませ、ＲＡＭ２０２０上のデータに対して各種の処理を行う。そして、ＣＰＵ２０００は、処理を終えたデータを、ＤＭＡ転送等により外部記憶装置へと書き戻す。このような処理において、ＲＡＭ２０２０は、外部記憶装置の内容を一時的に保持するものとみなせるから、本実施形態においてはＲＡＭ２０２０及び外部記憶装置等をメモリ、記憶部、または記憶装置等と総称する。
【０１０７】
本実施形態における各種のプログラム、データ、テーブル、データベース等の各種の情報は、このような記憶装置上に格納されて、情報処理の対象となる。なお、ＣＰＵ２０００は、ＲＡＭ２０２０の一部をキャッシュメモリに保持し、キャッシュメモリ上で読み書きを行うこともできる。このような形態においても、キャッシュメモリはＲＡＭ２０２０の機能の一部を担うから、本実施形態においては、区別して示す場合を除き、キャッシュメモリもＲＡＭ２０２０、メモリ、及び／又は記憶装置に含まれるものとする。
【０１０８】
また、ＣＰＵ２０００は、ＲＡＭ２０２０から読み出したデータに対して、プログラムの命令列により指定された、本実施形態中に記載した各種の演算、情報の加工、条件判断、情報の検索・置換等を含む各種の処理を行い、ＲＡＭ２０２０へと書き戻す。例えば、ＣＰＵ２０００は、条件判断を行う場合においては、本実施形態において示した各種の変数が、他の変数または定数と比較して、大きい、小さい、以上、以下、等しい等の条件を満たすか否かを判断し、条件が成立した場合（又は不成立であった場合）に、異なる命令列へと分岐し、またはサブルーチンを呼び出す。
【０１０９】
また、ＣＰＵ２０００は、記憶装置内のファイルまたはデータベース等に格納された情報を検索することができる。例えば、第１属性の属性値に対し第２属性の属性値がそれぞれ対応付けられた複数のエントリが記憶装置に格納されている場合において、ＣＰＵ２０００は、記憶装置に格納されている複数のエントリの中から第１属性の属性値が指定された条件と一致するエントリを検索し、そのエントリに格納されている第２属性の属性値を読み出すことにより、所定の条件を満たす第１属性に対応付けられた第２属性の属性値を得ることができる。
【０１１０】
以上に示したプログラム又はモジュールは、外部の記録媒体に格納されてもよい。記録媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤ又はＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワーク又はインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。
【０１１１】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【０１１２】
特許請求の範囲、明細書、および図面中において示した装置、システム、プログラム、および方法における動作、手順、ステップ、および段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り、任意の順序で実現しうることに留意すべきである。特許請求の範囲、明細書、および図面中の動作フローに関して、便宜上「まず、」、「次に、」等を用いて説明したとしても、この順で実施することが必須であることを意味するものではない。
【符号の説明】
【０１１３】
１０  生成装置、１１０  入力部、１２０  算出部、１３０  初期化部、１４０  生成部、２０  選択装置、２１０  取得部、２２０  利得選択部、２３０  入力選択部、２４０  遷移部、１０００  データベース、１９００  コンピュータ、２０００  ＣＰＵ、２０１０  ＲＯＭ、２０２０  ＲＡＭ、２０３０  通信インターフェイス、２０４０  ハードディスクドライブ、２０５０  フレキシブルディスク・ドライブ、２０６０  ＣＤ−ＲＯＭドライブ、２０７０  入出力チップ、２０７５  グラフィック・コントローラ、２０８０  表示装置、２０８２  ホスト・コントローラ、２０８４  入出力コントローラ、２０９０  フレキシブルディスク、２０９５  ＣＤ−ＲＯＭ
【図１】
2015176328.tif 000011
【図２】
2015176328.tif 000012
【図３】
2015176328.tif 000013
【図４】
2015176328.tif 000014
【図５】
2015176328.tif 000015
【図６】
2015176328.tif 000016
【図７】
2015176328.tif 000017
【図８】
2015176328.tif 000018
【図９】
2015176328.tif 000019