(57)【特許請求の範囲】
【請求項１】
入力された、移動する対象物毎に、前記対象物が状態間を遷移した履歴を表す遷移履歴データに基づいて、対象物間で関係性を有する前記遷移履歴データに対する前記対象物毎の各状態の目的地への到達しやすさを表す価値関数の因子行列、及び状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、前記対象物毎の前記価値関数、及び前記状態間の基本遷移確率を交互に更新することを繰り返す価値関数基本遷移関数推定部と、
前記価値関数基本遷移関数推定部によって推定された前記対象物毎の前記価値関数、及び前記状態間の基本遷移確率に基づいて、前記対象物毎に、前記対象物の前記状態間の基本遷移確率と、前記価値関数における前記対象物の各状態での遷移の最尤推定量とを用いた、各状態についての目的地らしさを表す報酬関数を推定する報酬関数推定部と、
を含む内部基準推定装置。
【請求項２】
入力された、時間帯毎に、移動する対象物が状態間を遷移した履歴を表す遷移履歴データに基づいて、時間帯間で関係性を有する前記遷移履歴データに対する前記時間帯毎の各状態の目的地への到達しやすさを表す価値関数の因子行列、及び状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、前記時間帯毎の前記価値関数、及び前記状態間の基本遷移確率を交互に更新することを繰り返す価値関数基本遷移関数推定部と、
前記価値関数基本遷移関数推定部によって推定された前記時間帯毎の前記価値関数、及び前記状態間の基本遷移確率に基づいて、前記時間帯毎に、前記時間帯の前記状態間の基本遷移確率と、前記価値関数における前記時間帯の各状態での遷移の最尤推定量とを用いた、各状態についての目的地らしさを表す報酬関数を推定する報酬関数推定部と、
を含む内部基準推定装置。
【請求項３】
前記目的関数は、前記対象物と前記状態との組み合わせについての前記状態が現れた回数、前記価値関数、及び前記状態間の基本遷移確率を含む項と、全ての前記対象物の状態間の遷移の回数、及び前記状態間の基本遷移確率を含む項とを持つ請求項１に記載の内部基準推定装置。
【請求項４】
前記目的関数は、前記時間帯と前記状態との組み合わせについての前記状態が現れた回数、前記価値関数、及び前記状態間の基本遷移確率を含む項と、全ての前記時間帯の状態間の遷移の回数、及び前記状態間の基本遷移確率を含む項とを持つ請求項２に記載の内部基準推定装置。
【請求項５】
価値関数基本遷移関数推定部が、入力された、移動する対象物毎に、前記対象物が状態間を遷移した履歴を表す遷移履歴データに基づいて、対象物間で関係性を有する前記遷移履歴データに対する前記対象物毎の各状態の目的地への到達しやすさを表す価値関数の因子行列、及び前記状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、前記対象物毎の前記価値関数、及び前記状態間の基本遷移確率を交互に更新することを繰り返すステップと、
報酬関数推定部が、前記価値関数基本遷移関数推定部によって推定された前記対象物毎の前記価値関数、及び前記状態間の基本遷移確率に基づいて、前記対象物毎に、前記対象物の状態間の基本遷移確率と、前記価値関数における前記対象物の各状態での遷移の最尤推定量とを用いた、各状態についての目的地らしさを表す報酬関数を推定するステップと、
を含む内部基準推定方法。
【請求項６】
価値関数基本遷移関数推定部が、入力された、時間帯毎に、移動する対象物が状態間を遷移した履歴を表す遷移履歴データに基づいて、時間帯間で関係性を有する前記遷移履歴データに対する前記時間帯毎の各状態の目的地への到達しやすさを表す価値関数の因子行列、及び前記状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、前記時間帯毎の前記価値関数、及び前記状態間の基本遷移確率を交互に更新することを繰り返すステップと、
報酬関数推定部が、前記価値関数基本遷移関数推定部によって推定された前記時間帯毎の前記価値関数、及び前記状態間の基本遷移確率に基づいて、前記時間帯毎に、前記時間帯の状態間の基本遷移確率と、前記価値関数における前記時間帯の各状態での遷移の最尤推定量とを用いた、各状態についての目的地らしさを表す報酬関数を推定するステップと、
を含む内部基準推定方法。
【請求項７】
前記目的関数は、前記対象物と前記状態との組み合わせについての前記状態が現れた回数、前記価値関数、及び前記状態間の基本遷移確率を含む項と、全ての前記対象物の状態間の遷移の回数、及び前記状態間の基本遷移確率を含む項とを持つ請求項５に記載の内部基準推定方法。
【請求項８】
前記目的関数は、前記時間帯と前記状態との組み合わせについての前記状態が現れた回数、前記価値関数、及び前記状態間の基本遷移確率を含む項と、全ての前記時間帯の状態間の遷移の回数、及び前記状態間の基本遷移確率を含む項とを持つ請求項６に記載の内部基準推定方法。
【請求項９】
コンピュータを、請求項１〜請求項４のいずれか１項に記載の内部基準推定装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、内部基準推定装置、方法、及びプログラムに係り、特に、対象物の流れを予測するための報酬関数を推定する内部基準推定装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
人の意思決定は、ある人個人がもつ固有の内部基準と、その個人には属さない外部環境に依存して決定している。例えばあるユーザがショッピングセンター（ＳＣ）内の店舗を見て回るケースを考えてみれば、各通路において、まっすぐ進むのか、もしくはエスカレーターを登るのかという意思決定には、そのユーザ個人のショッピングの目的や各店舗に対する選好の度合いといった内部基準と、ＳＣ内にどのような通路が存在し、どこにどの店舗が配置されているかという外部環境が影響している。外部環境とは独立なその人の内部基準を把握することができれば、ユーザがなぜそのように移動したのかという原因を探ったり、ユーザがそことは別のＳＣにおいてどのように移動するかをシミュレートできるようになることが期待される。
【０００３】
また、人の移動履歴から、その人の持つ内部基準を推定する手法として、逆強化学習と呼ばれる研究がこれまで進められている（非特許文献１、及び非特許文献２参照）。逆強化学習は、マルコフ決定過程（Ｍａｒｋｏｖ Ｄｅｃｉｓｉｏｎ Ｐｒｏｃｅｓｓ、ＭＤＰ）における報酬関数（これが内部基準に相当する）を移動履歴から推定される問題として定式化される。報酬関数が既知のもとで最適な移動方法を考察する問題である、強化学習（非特許文献３参照）とは逆の問題を解いていることが“逆”強化学習と呼ばれる所以である。これまでの成果として非特許文献２では、タクシー運転手の好むドライブ特性（整備されている道路を好むか、直進を好むか）を示す内部基準を移動系列データから獲得できたことを報告している。また、ロボット制御、自然言語処理における特筆すべき成功例も存在する（非特許文献４、及び非特許文献５参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】AndrewY Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In in Proc. 17th International Conf. on Machine Learning, 2000.
【非特許文献２】BrianD Ziebart, AndrewL Maas, JAndrew Bagnell, and AnindK Dey. Maximum entropy inverse reinforcement learning. In AAAI, pages 1433{1438,
【０００５】
2008.
【非特許文献３】RichardS Sutton and AndrewG Barto. Reinforcement learning: An introduction. MIT press Cambridge, 1998. 邦題: 強化学習訳: 三上貞芳, 皆川
【０００６】
雅章.
【非特許文献４】Pieter Abbeel and AndrewY Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, page1. ACM, 2004.
【非特許文献５】Gergely Neu and Csaba Szepesva´ri. Training parsers by inverse reinforcement learning. Machine learning, 77(2-3):303-337, 2009.
【非特許文献６】Emanuel Todorov. Linearly-solvable markov decision problems. In Advances in neural information processing systems, pages 1369-1376, 2006.
【非特許文献７】Krishnamurthy Dvijotham and Emanuel Todorov. Inverse optimal control with linearly-solvable mdps. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 335-342, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、内部基準を推定する、という強い動機づけにもかかわらず逆強化学習手法は、これまで広く応用されている技術となってはいなかった。原因はいくつか考えられるが、非特許文献１において、『観測系列が最適な遷移であると説明する報酬関数は一意に定められないことが示されていること』や、非特許文献１、及び非特許文献２の既存の主要アルゴリズムでは、『その内部で最適な遷移を求める順問題と報酬関数を求める逆問題を交互に繰り返し解くことが必要される煩雑なものであること』などが挙げられる。そんな中、近年提案された線形可解マルコフ決定過程（ＬｉｎｅａｒｌｙＳｏｌｖａｂｌｅＭＤＰ、ＬＭＤＰ）（非特許文献６参照）において、逆強化学習を考えるというアプローチ（非特許文献７参照）がこの状況を変えることに成功している。ＬＭＤＰにおける逆強化学習では、報酬関数の推定は、順問題・逆問題の繰り返しの必要なく、求めることができるからである。
【０００８】
しかしながら、非特許文献７では、ユーザ個人や時間帯（昼、夜など）毎に報酬関数を持つ状況は考慮されていない、という問題がある。また、報酬関数によらない場合の遷移確率（基本遷移確率）については既知である状況が考えられており、遷移確率が既知でない状況が考慮されていなかった。
【０００９】
本発明は、上記問題点を解決するために成されたものであり、できる内部基準推定装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、第１の発明に係る内部基準推定装置は、入力された、移動する対象物毎又は時間帯毎に、前記対象物が状態間を遷移した履歴を表す遷移履歴データに基づいて、前記対象物毎又は時間帯毎の各状態の目的地への到達しやすさを表す価値関数、及び状態間の基本遷移確率を推定する価値関数基本遷移関数推定部と、前記価値関数基本遷移関数推定部によって推定された前記対象物毎又は時間帯毎の前記価値関数、及び前記状態間の基本遷移確率に基づいて、前記対象物毎又は時間帯毎に、各状態についての目的地らしさを表す報酬関数を推定する報酬関数推定部と、を含んで構成されている。
【００１１】
また、第１の発明に係る内部基準推定装置において、前記価値関数基本遷移関数推定部は、前記遷移履歴データに基づいて、前記遷移履歴データに対する前記対象物毎又は時間帯毎の前記価値関数及び前記状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、前記対象物毎又は時間帯毎の前記価値関数、及び前記状態間の基本遷移確率を交互に更新することを繰り返すようにしてもよい。
【００１２】
また、第１の発明に係る内部基準推定装置において、前記対象物毎の前記価値関数は、前記対象物間で関係性を有し、前記価値関数基本遷移関数推定部は、前記対象物毎の前記価値関数を更新する際に、前記遷移履歴データに対する前記対象物毎の前記価値関数の因子行列及び前記状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、前記対象物毎の前記価値関数の因子行列を更新するようにしてもよい。
【００１３】
また、第１の発明に係る内部基準推定装置において、前記時間帯毎の前記価値関数は、前記時間帯間で関係性を有し、前記価値関数基本遷移関数推定部は、前記時間帯毎の前記価値関数を更新する際に、前記遷移履歴データに対する前記時間帯毎の前記価値関数の因子行列及び前記状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、前記時間帯毎の前記価値関数の因子行列を更新するようにしてもよい。
【００１４】
第１の発明に係る内部基準推定方法は、価値関数基本遷移関数推定部が、入力された、移動する対象物毎又は時間帯毎に、前記対象物が状態間を遷移した履歴を表す遷移履歴データに基づいて、前記対象物毎又は時間帯毎の各状態の目的地への到達しやすさを表す価値関数、及び状態間の基本遷移確率を推定するステップと、報酬関数推定部が、前記価値関数基本遷移関数推定部によって推定された前記対象物毎又は時間帯毎の前記価値関数、及び前記状態間の基本遷移確率に基づいて、前記対象物毎又は時間帯毎に、各状態についての目的地らしさを表す報酬関数を推定するステップと、を含んで実行することを特徴とする。
【００１５】
また、第２の発明に係る内部基準推定方法において、前記価値関数基本遷移関数推定部が推定するステップは、前記遷移履歴データに基づいて、前記遷移履歴データに対する前記対象物毎又は時間帯毎の前記価値関数及び前記状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、前記対象物毎又は時間帯毎の前記価値関数、及び前記状態間の基本遷移確率を交互に更新することを繰り返すようにしてもよい。
【００１６】
また、第２の発明に係る内部基準推定方法において、前記対象物毎の前記価値関数は、前記対象物間で関係性を有し、前記価値関数基本遷移関数推定部が推定するステップは、前記対象物毎の前記価値関数を更新する際に、前記遷移履歴データに対する前記対象物毎の前記価値関数の因子行列及び前記状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、前記対象物毎の前記価値関数の因子行列を更新するようにしてもよい。
【００１７】
また、第３の発明に係るプログラムは、コンピュータを、上記第１の発明に係る内部基準推定装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１８】
本発明の内部基準推定装置、方法、及びプログラムによれば、移動する対象物毎又は時間帯毎に、対象物又は時間帯が状態間を遷移した履歴を表す遷移履歴データに基づいて、対象物毎又は時間帯毎の各状態の目的地への到達しやすさを表す価値関数、及び状態間の基本遷移確率を推定し、対象物毎又は時間帯毎の価値関数、及び状態間の基本遷移確率に基づいて、対象物毎又は時間帯毎に、各状態についての目的地らしさを表す報酬関数を推定することにより、対象物毎又は時間帯毎に異なる報酬関数を推定することができる、という効果が得られる。
【図面の簡単な説明】
【００１９】
【図１】線形可解マルコフ決定過程（ＭＬＤＰ）における状態集合、基本遷移関数、及び報酬関数の一例を示す抽象図である。
【図２】本発明の実施の形態に係る内部基準推定装置の構成を示すブロック図である。
【図３】本発明の実施の形態に係る内部基準推定装置における内部基準推定処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２１】
＜本発明の実施の形態に係る原理＞
【００２２】
まず、本発明の実施の形態における原理を説明する。ここでは、実施の形態の構成及び作用において用いる記号、アルゴリズムについて記述する。なお、ここでは、各ユーザ毎に異なる行動の内部基準が存在する例を用いて説明するが、時間帯毎に異なる内部基準が存在する場合であっても同様である。なお、ユーザが対象物の一例である。
【００２３】
［線形可解マルコフ決定過程（ＬＭＤＰ）の定義］
【００２４】
まず、上記非特許文献６を参照して線形可解マルコフ決定過程（ＬＭＤＰ）について説明する。線形可解マルコフ決定過程（ＬＭＤＰ）では、状態集合
【００２５】
【数１】
0006513557.tif 000002
【００２６】
、基本遷移関数
【００２７】
【数２】
0006513557.tif 000003
【００２８】
、報酬関数
【００２９】
【数３】
0006513557.tif 000004
【００３０】
が定義された環境を考える。本実施の形態では、ユーザ毎に報酬関数が存在する例について述べるため、上記の定義を、非特許文献６から若干変更する。ユーザ数をＩ、状態数をＪとする。状態集合は
【００３１】
【数４】
0006513557.tif 000005
【００３２】
、基本遷移関数はＪ×Ｊ行列
【００３３】
【数５】
0006513557.tif 000006
【００３４】
、報酬関数はＩ×Ｊ行列
【００３５】
【数６】
0006513557.tif 000007
【００３６】
と定義する。非特許文献６の定義では、上記定義においてユーザ数Ｉ＝１であり、報酬関数がＪ列ベクトルで与えられる場合を考えていることに相当する。上記３つ組
【００３７】
【数７】
0006513557.tif 000008
【００３８】
の具体例を図１に示す。図１中の各グリッドが、状態集合
【００３９】
【数８】
0006513557.tif 000009
【００４０】
中のいずれかの状態ｓｊに対応し、各グリッド間の“基本的な”遷移の確率が基本遷移関数
【００４１】
【数９】
0006513557.tif 000010
【００４２】
で決められている。“基本的な”と注釈をつけたのは、ＬＭＤＰでは行動
【００４３】
【数１０】
0006513557.tif 000011
【００４４】
を実行し、行動コストを支払うことでこの遷移の確率を変更することが許されているからである。具体的には、行動
【００４５】
【数１１】
0006513557.tif 000012
【００４６】
を実行することで、状態ｊから状態ｋへの遷移の確率を
【００４７】
【数１２】
0006513557.tif 000013
【００４８】
から
【００４９】
【数１３】
0006513557.tif 000014
【００５０】
へと変更することができる。
【００５１】
【数１４】
0006513557.tif 000015
【００５２】
ａｊの値が大きければ大きいほど、状態ｊへの遷移の確率を増加できることがわかる。ただし、
【００５３】
【数１５】
0006513557.tif 000016
【００５４】
の値は確率の和が１となることを満たすもの、すなわち
【００５５】
【数１６】
0006513557.tif 000017
【００５６】
を満たすものに限られる。
【００５７】
【数１７】
0006513557.tif 000018
【００５８】
また、上記のように状態ｊで行動
【００５９】
【数１８】
0006513557.tif 000019
【００６０】
を実行することにより発生するコスト
【００６１】
【数１９】
0006513557.tif 000020
【００６２】
は、確率分布の類似度を図る尺度であるＫＬ距離を用いて以下（３）式のように定義される。ＫＬ距離は、値が小さいほど類似していることを表し、一致すれば０となる。
【００６３】
【数２０】
0006513557.tif 000021
【００６４】
つまり、上記（３）式においては遷移の確率を￣ｐｊｋから変化させればさせるほど、支払うコストが多くなる。上記の行動コストとは別に、ユーザと状態のみに依存した状態コストを表すのが、報酬関数
【００６５】
【数２１】
0006513557.tif 000022
【００６６】
である。上記図１の例で示すように、この報酬関数の値ｒｉｊは例えば、“ユーザｉにとっての状態ｊの目的地らしさ”に対応した値などに対応し、値が小さいほど目的地らしいといえる。さらに、各状態ｓｊにおいて実行する行動
【００６７】
【数２２】
0006513557.tif 000023
【００６８】
を定めたものを方策
【００６９】
【数２３】
0006513557.tif 000024
【００７０】
と呼ぶこととする。
【００７１】
方策πにしたがって行動するユーザｉを考えると、上記（１）式にしたがって確率的に状態間を遷移し、遷移する度に行動コストと状態コストとの和
【００７２】
【数２４】
0006513557.tif 000025
【００７３】
を支払う動きがモデリングできる。状態遷移を十分な回数繰り返した際に、遷移の過程で支払ったコスト（行動コストと状態コストとの和）の累積和の期待値が最小になるような方策を最適方策と呼び、
【００７４】
【数２５】
0006513557.tif 000026
【００７５】
と書く。すなわち、最適方策とは、先ほどの例を用いると、できるだけ少ない行動コストで状態コストの低い目的地に早く到達できる方策であり、直感的には、目的地に到達する最適な手順を表しているとみなせる。このように、基本遷移関数
【００７６】
【数２６】
0006513557.tif 000027
【００７７】
と報酬関数
【００７８】
【数２７】
0006513557.tif 000028
【００７９】
が既知の時に、最適方策
【００８０】
【数２８】
0006513557.tif 000029
【００８１】
を求める問題が、ＬＭＤＰにおける順問題である。ユーザｉの最適方策は、以下（４）式の最適性方程式を満たす価値関数
【００８２】
【数２９】
0006513557.tif 000030
【００８３】
を求めることで、次の（６）式のように算出できる。なお、上記（４）式から（５）式への式展開は上記参考文献３を参照できる。また、価値関数は、各状態の目的地への到達しやすさを表す。価値関数の求め方は後述する。
【００８４】
【数３０】
0006513557.tif 000031
【００８５】
ここで、上記（６）式により得られたａ＊ｉｊの値を上記（１）式に代入することで、最適方策により行動を選択する場合の遷移確率は、以下（７）式で与えられることがわかる。
【００８６】
【数３１】
0006513557.tif 000032
【００８７】
したがって、価値関数
【００８８】
【数３２】
0006513557.tif 000033
【００８９】
が計算できれば、ＬＭＤＰの順問題が解けることになる。
【００９０】
［価値関数計算アルゴリズム］
【００９１】
次に、非特許文献７を参照して価値関数を計算するアルゴリズムについて説明する。価値関数を計算するアルゴリズムは上記（５）式から導かれる。両辺の符号を変換したのち、指数をとると、以下の（８）式が求まる。
【００９２】
【数３３】
0006513557.tif 000034
【００９３】
ここで
【００９４】
【数３４】
0006513557.tif 000035
【００９５】
と定義すると、上記（８）式は以下（９）式のようにベクトル表記できる。
【００９６】
【数３５】
0006513557.tif 000036
【００９７】
これより明らかに
【００９８】
【数３６】
0006513557.tif 000037
【００９９】
は行列
【０１００】
【数３７】
0006513557.tif 000038
【０１０１】
の固有値１の固有ベクトルであることがわかる。また、これが最大固有ベクトルであることも示せる。よって、以下（１０）式に従い、
【０１０２】
【数３８】
0006513557.tif 000039
【０１０３】
と収束するまで更新することで上記（９）式を満たす
【０１０４】
【数３９】
0006513557.tif 000040
【０１０５】
を求めることができる。
【０１０６】
【数４０】
0006513557.tif 000041
【０１０７】
最後に
【０１０８】
【数４１】
0006513557.tif 000042
【０１０９】
の定義より、
【０１１０】
【数４２】
0006513557.tif 000043
【０１１１】
と変換することで価値関数
【０１１２】
【数４３】
0006513557.tif 000044
【０１１３】
が求まる。各ユーザｉについて以上の手続きを繰り返すことで、価値関数
【０１１４】
【数４４】
0006513557.tif 000045
【０１１５】
が求まる。以上がＬＭＤＰの順問題の解法である。なお、ユーザ数Ｉ＝１であれば、上記の手続きは非特許文献６による価値関数計算方法と同等であり、計算方法に本質的な違いは存在しない。
【０１１６】
［逆問題の解法］
【０１１７】
次に参考文献３を参照してＬＭＤＰの逆問題を説明する。ＬＭＤＰの逆問題は、人、ロボットの遷移の系列と基本遷移関数とを入力とし、報酬関数を推定する問題、として定式化される。逆問題における解法の鍵は、人、ロボットの遷移は上記（７）式の最適方策による遷移確率にしたがって得られているとみなすことにある。ユーザｉの遷移系列データ
【０１１８】
【数４５】
0006513557.tif 000046
【０１１９】
を（遷移前の状態、遷移後の状態）という１ステップの遷移の履歴の集合で表現し、ｎｊを状態ｊが遷移前の状態として現れた回数、ｎ′ｊを状態ｊが遷移後の状態として現れた回数とする。ユーザｉの価値関数ｖｉを未知のパラメタとみなすと、上記（７）式から、負の対数尤度関数
【０１２０】
【数４６】
0006513557.tif 000047
【０１２１】
を最小化する
【０１２２】
【数４７】
0006513557.tif 000048
【０１２３】
が、入力の遷移の履歴
【０１２４】
【数４８】
0006513557.tif 000049
【０１２５】
を生成する確率の最も高い最尤推定量
【０１２６】
【数４９】
0006513557.tif 000050
【０１２７】
となる。
【０１２８】
【数５０】
0006513557.tif 000051
【０１２９】
上記の関数の最小化には、最急降下法やニュートン法など任意の方法が適用できる。上記（５）式に最尤推定量
【０１３０】
【数５１】
0006513557.tif 000052
【０１３１】
を代入すれば、報酬関数は次の（１２）式により求めることができる。
【０１３２】
【数５２】
0006513557.tif 000053
【０１３３】
以上がＬＭＤＰの逆問題の解法である。上記のアプローチでは、ユーザｉの推定にはユーザｉの遷移系列データ
【０１３４】
【数５３】
0006513557.tif 000054
【０１３５】
のみを利用して推定を行っている。また基本遷移確率
【０１３６】
【数５４】
0006513557.tif 000055
【０１３７】
は既知であるとしていた。
【０１３８】
＜本発明の第１の実施の形態に係る概要＞
【０１３９】
本発明の第１の実施の形態に係る技術は、ユーザ毎に報酬関数が存在する状況において、（ｉ）各ユーザ毎の報酬関数と（ｉｉ）基本遷移確率を同時に推定することが可能な新しい手法である。本技術は、ユーザｉ＝１，・・・，Ｉの遷移系列データＤ＝（Ｄ１，・・・，ＤＩ）を入力し、ユーザｉの状態ｊの報酬ｒｉｊを示す報酬関数Ｉ×Ｊ行列
【０１４０】
【数５５】
0006513557.tif 000056
【０１４１】
を出力する。本手法は、上記（１１）式と同様に報酬関数
【０１４２】
【数５６】
0006513557.tif 000057
【０１４３】
でなく価値関数
【０１４４】
【数５７】
0006513557.tif 000058
【０１４５】
をパラメタとする目的関数を考える。基本遷移関数も未知であるので、価値関数
【０１４６】
【数５８】
0006513557.tif 000059
【０１４７】
と基本遷移関数
【０１４８】
【数５９】
0006513557.tif 000060
【０１４９】
とがパラメタである。よって上記（１１）式の拡張として次の（１３）式に示す目的関数を考える。
【０１５０】
【数６０】
0006513557.tif 000061
【０１５１】
ただし、ｎ´´ｊｋはユーザ全体で状態ｊから状態ｋへ遷移した回数を表す。
【０１５２】
提案手法は、価値関数
【０１５３】
【数６１】
0006513557.tif 000062
【０１５４】
、基本遷移関数
【０１５５】
【数６２】
0006513557.tif 000063
【０１５６】
を交互に繰り返し更新することでパラメタを推定する方法である。すなわち、ｔ回目の繰り返し時点における価値関数、及び基本遷移関数の各関数
【０１５７】
【数６３】
0006513557.tif 000064
【０１５８】
において、基本遷移関数
【０１５９】
【数６４】
0006513557.tif 000065
【０１６０】
を固定したうえで、価値関数を
【０１６１】
【数６５】
0006513557.tif 000066
【０１６２】
と更新し、次は価値関数
【０１６３】
【数６６】
0006513557.tif 000067
【０１６４】
を固定したうえで、基本遷移関数を
【０１６５】
【数６７】
0006513557.tif 000068
【０１６６】
と更新する。ここから、その各パラメタの更新式に関する説明をする。なお、本実施の形態における価値関数
【０１６７】
【数６８】
0006513557.tif 000069
【０１６８】
は、ユーザ毎に独立に価値関数を推定する方法により得られる。また、価値関数と報酬関数には対応関係があることから、報酬関数がユーザ間で独立、といえる。
【０１６９】
［価値関数の推定：ユーザ間の価値関数が独立である場合］
【０１７０】
本実施の形態における価値関数の更新式は、上記（１１）の目的関数を考える既存手法がそのまま適用できる。よって既存手法と同じく各ユーザｉ毎に最急降下法やニュートン法を用いた価値関数の更新を行えばよい。最急降下法を用いた場合の更新式は以下のようになる。
【０１７１】
【数６９】
0006513557.tif 000070
【０１７２】
［基本遷移関数の更新］
【０１７３】
次に価値関数
【０１７４】
【数７０】
0006513557.tif 000071
【０１７５】
を固定した際の基本遷移関数の更新式を導出する。導出には、ラグランジュの未定乗数法を用いる。基本遷移関数の行和が１になるという制約より、ラグランジュ関数は以下（１５）式により与えられる。
【０１７６】
【数７１】
0006513557.tif 000072
【０１７７】
ここで、ｎｉｊをユーザｉにおいて状態ｊが遷移前の状態として現れた回数、ｎ′ｉｊをユーザｉにおいて状態ｊが遷移後の状態として現れた回数とする。
【０１７８】
上記（１５）式を解くと、￣ｐｊｋは以下（１６）式を満たさなければならないことが分かる。
【０１７９】
【数７２】
0006513557.tif 000073
【０１８０】
すなわち￣ｐｊｋは更新後の値を（１６）式の非線形連立方程式の解｛￣ｐｊｋｓｏｌｕｔｉｏｎ｝ｊ，ｋとすればよい。
【０１８１】
【数７３】
0006513557.tif 000074
【０１８２】
なお、非線形連立方程式の解はニュートン・ラフソン法などを用いて数値的に求めることが可能である。
【０１８３】
上記により導かれた、価値関数がユーザ毎に独立とした場合における価値関数
【０１８４】
【数７４】
0006513557.tif 000075
【０１８５】
と、基本遷移関数
【０１８６】
【数７５】
0006513557.tif 000076
【０１８７】
とを交互に更新するアルゴリズムが、第１の実施の形態に係る技術の新規性である。
【０１８８】
＜本発明の第１の実施の形態に係る装置の構成＞
【０１８９】
次に、本発明の第１の実施の形態に係る内部基準推定装置の構成について説明する。図２に示すように、本発明の第１の実施の形態に係る内部基準推定装置１００は、ＣＰＵと、ＲＡＭと、後述する内部基準推定処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この内部基準推定装置１００は、機能的には図２に示すように入出力部１５０と、遷移履歴処理部１０と、価値関数基本遷移関数推定部２０と、報酬関数推定部３０と、報酬関数処理部４０と、記録部５０とを備えている。
【０１９０】
入出力部１５０は、外部装置２００から出力された、各ユーザが状態間を遷移した履歴を表す遷移履歴データ
【０１９１】
【数７６】
0006513557.tif 000077
【０１９２】
を受け付ける。また、入出力部１５０は、報酬関数処理部４０により得られたユーザ毎の報酬関数を、外部装置２００に出力する。
【０１９３】
記録部５０は、遷移履歴記録部５１、基本遷移関数記録部５２、価値関数記録部５３、及び報酬関数記録部５４を有する。
【０１９４】
遷移履歴処理部１０は、入出力部１５０により受け付けた、各ユーザが状態間を遷移した履歴を表す遷移履歴データ
【０１９５】
【数７７】
0006513557.tif 000078
【０１９６】
を遷移履歴記録部５１に格納する。
【０１９７】
価値関数基本遷移関数推定部２０は、各ユーザが状態間を遷移した履歴を表す遷移履歴データに基づいて、ユーザ毎の各状態の目的地への到達しやすさを表す価値関数、及び状態間の基本遷移確率を推定する。また、価値関数基本遷移関数推定部２０は、基本遷移確率の推定において、遷移履歴データに基づいて、遷移履歴データに対するユーザ毎の価値関数及び状態間の基本遷移確率の尤もらしさを表す上記（１３）式に示す目的関数を最適化するように、ユーザ毎の価値関数、及び状態間の基本遷移確率を交互に更新することを繰り返す。
【０１９８】
価値関数基本遷移関数推定部２０は、具体的には、ユーザ毎に以下に説明する第１〜第４の処理を行う。まず第１の処理として、当該ユーザの基本遷移関数
【０１９９】
【数７８】
0006513557.tif 000079
【０２００】
と、価値関数
【０２０１】
【数７９】
0006513557.tif 000080
【０２０２】
とを初期化する。また、終了条件に用いる変数として、更新量の最大変化幅を示す変数δを同様に初期化する。なお、終了条件の閾値ε、及び最大繰り返し回数はあらかじめ設定されているものとする。
【０２０３】
次に、価値関数基本遷移関数推定部２０は、第２の処理として、基本遷移関数の初期値又は前回更新された基本遷移関数に基づいて、基本遷移関数の値を固定し、上記（１３）式の目的関数の値を最小化するように、価値関数
【０２０４】
【数８０】
0006513557.tif 000081
【０２０５】
を上記（１４）式に従い更新する。この時、更新前と更新後の価値関数
【０２０６】
【数８１】
0006513557.tif 000082
【０２０７】
の差の絶対値の最大値ｍａｘｉｒ|ｖｉｒｏｌｄ−ｖｉｒｎｅｗ|がδより大きければδ←ｍａｘｉｒ|ｖｉｒｏｌｄ−ｖｉｒｎｅｗ|と更新する。ただし更新前の価値関数
【０２０８】
【数８２】
0006513557.tif 000083
【０２０９】
の要素をｖｉｒｏｌｄ、更新後の要素をｖｉｒｎｅｗと記述した。
【０２１０】
次に、価値関数基本遷移関数推定部２０は、第３の処理として、価値関数の初期値又は前回更新された価値関数に基づいて、価値関数の値を固定し、上記（１３）式の目的関数の値を最小化するように、基本遷移関数
【０２１１】
【数８３】
0006513557.tif 000084
【０２１２】
における状態間の基本遷移確率を上記（１７）式に従い更新する。この時、更新前と更新後の基本遷移関数
【０２１３】
【数８４】
0006513557.tif 000085
【０２１４】
の各要素である基本遷移確率の差の絶対値の最大値ｍａｘｊｋ|￣ｐｊｋｏｌｄ−￣ｐｊｋｎｅｗ|がδより大きければδ←ｍａｘｊｋ|￣ｐｊｋｏｌｄ−￣ｐｊｋｎｅｗ|と更新する。ただし更新前の基本遷移関数
【０２１５】
【数８５】
0006513557.tif 000086
【０２１６】
の各要素である基本遷移確率を￣ｐｊｋｏｌｄ、更新後の基本遷移確率を￣ｐｊｋｎｅｗと記述した。
【０２１７】
次に、価値関数基本遷移関数推定部２０は、第４の処理として、繰り返し処理の終了判定を行う。計算繰り返し回数を更新し、終了条件を満たしていれば、繰り返し処理を終了し、終了条件を満たしていなければδ←０として第２〜第４の処理を繰り返す。終了条件は、計算繰り返し回数があらかじめ定めた繰り返し回数を超えるか、又は更新量の最大変化幅を示す変数δがあらかじめ定めた閾値εより小さいこととする。
【０２１８】
報酬関数推定部３０は、価値関数基本遷移関数推定部２０によって推定されたユーザ毎の価値関数
【０２１９】
【数８６】
0006513557.tif 000087
【０２２０】
、及び基本遷移関数
【０２２１】
【数８７】
0006513557.tif 000088
【０２２２】
における状態間の基本遷移確率に基づいて、上記（１２）式に従って、ユーザ毎に、各状態についての目的地らしさを表す報酬関数
【０２２３】
【数８８】
0006513557.tif 000089
【０２２４】
を推定し、報酬関数記録部５４に格納する。
【０２２５】
報酬関数処理部４０は報酬関数記録部５４に格納されたユーザ毎の報酬関数
【０２２６】
【数８９】
0006513557.tif 000090
【０２２７】
を外部装置２００に出力する。
【０２２８】
＜本発明の第１の実施の形態に係る内部基準推定装置の作用＞
【０２２９】
次に、本発明の実施の形態に係る内部基準推定装置１００の作用について説明する。入出力部１５０において遷移履歴データを受け付け遷移履歴記録部９１に格納すると、内部基準推定装置１００は、図３に示す内部基準推定処理ルーチンを実行する。なお、終了条件の閾値ε、及び最大繰り返し回数があらかじめ設定されている。
【０２３０】
まず、ステップＳ１００では、基本遷移関数と、ユーザ毎の価値関数とを初期化する。
【０２３１】
次に、ステップＳ１０２では、更新量の最大変化幅を示す変数δを初期化する。
【０２３２】
ステップＳ１０４では、基本遷移関数の初期値又は前回更新された基本遷移関数に基づいて、基本遷移関数の値を固定し、上記（１３）式の目的関数の値を最小化するように、ユーザ毎の価値関数を上記（１４）式に従って更新すると共に、ｍａｘｉｒ|ｖｉｒｏｌｄ−ｖｉｒｎｅｗ|＞δである場合に、変数δを更新する。
【０２３３】
ステップＳ１０６では、価値関数の初期値又は前回更新された価値関数に基づいて、ユーザ毎の価値関数の値を固定し、上記（１３）式の目的関数の値を最小化するように、基本遷移関数における状態間の基本遷移確率を上記（１７）式に従い更新すると共に、ｍａｘｊｋ|￣ｐｊｋｏｌｄ−￣ｐｊｋｎｅｗ|＞δである場合に、変数δを更新する。
【０２３４】
ステップＳ１０８では、繰り返し回数をカウントアップする。
【０２３５】
ステップＳ１１０では、終了条件を満たしているかを判定し、終了条件を満たしていれば、繰り返し処理を終了し、ステップＳ１１２へ移行する。終了条件を満たしていなければ、ステップＳ１１２でδ←０としてステップＳ１０４〜Ｓ１０８を繰り返す。
【０２３６】
ステップＳ１１４では、ステップＳ１０４及びＳ１０６によって推定されたユーザ毎の価値関数、及び基本遷移関数における状態間の基本遷移確率に基づいて、上記（１２）式に従って、各状態についての目的地らしさを表すユーザ毎の報酬関数を推定し、報酬関数記録部５４に格納する。
【０２３７】
ステップＳ１１６では、報酬関数記録部５４に格納された報酬関数を外部装置２００に出力し処理を終了する。
【０２３８】
以上説明したように、本発明の第１の実施の形態に係る内部基準推定装置によれば、移動するユーザ毎に、ユーザが状態間を遷移した履歴を表す遷移履歴データに基づいて、上記（１４）式、及び（１７）式に従って、ユーザ毎の各状態の目的地への到達しやすさを表す価値関数、及び状態間の基本遷移確率を推定し、ユーザ毎の価値関数、及び状態間の基本遷移確率に基づいて、上記（１２）式に従って、ユーザ毎に、各状態についての目的地らしさを表す報酬関数を推定することにより、ユーザ毎に異なる報酬関数を推定することができる。
【０２３９】
また、本実施の形態に係る技術によって、各ユーザ毎に異なる行動の内部基準が推定できるようになり、ある特定の個人の移動の原因を探ったり、異なる環境におけるそのユーザの移動をユーザ毎の違いを考慮してシミュレートできるようになる。また、本技術によって、既存技術では入力として必要であった基本遷移確率と呼ばれるパラメタをデータから推定することも可能となる。よって基本遷移確率パラメタの事前の計算や設定なしに内部基準を推定することが可能になる。
【０２４０】
＜本発明の第２の実施の形態に係る概要＞
【０２４１】
次に、第２の実施の形態の概要を説明する。
【０２４２】
第２の実施の形態では、ユーザ毎の価値関数は、ユーザ間で関係性を有している点が第１の実施の形態と異なっている。本実施の形態における価値関数
【０２４３】
【数９０】
0006513557.tif 000091
【０２４４】
は、ユーザ間の価値関数に関係性を保ちながら推定する方法により得られる。また、価値関数と報酬関数には対応関係があることから、報酬関数がユーザ間で関係する、といえる。
【０２４５】
［価値関数の推定：ユーザ間の価値関数が関係性をもつ場合］
【０２４６】
本実施の形態における価値関数の更新式を説明する前に本手法の利点を説明する。ユーザ間の価値関数に関係性を導入することには複数の利点がある。例えば履歴を持つユーザ数が１００人を超えるような場合、類似した価値関数、及び報酬関数を持つユーザをグルーピング（例えば１０グループ）することができれば、その１０グループの報酬関数に着目することで、１００人全員の報酬関数を観察することなくデータが解釈できるようになる。また、ある特定のユーザに関する遷移の履歴の量が十分でない場合、所属グループさえ自動に特定できれば、その他の同一グループ所属ユーザのデータを利用できることで少ないデータ量でもそのユーザの報酬関数を推定できることが期待される。
【０２４７】
そこで、ユーザ間の価値関数の間に関係性を導入するために価値関数Ｖを因子行列
【０２４８】
【数９１】
0006513557.tif 000092
【０２４９】
の積
【０２５０】
【数９２】
0006513557.tif 000093
【０２５１】
で表現することを考える。因子行列
【０２５２】
【数９３】
0006513557.tif 000094
【０２５３】
の積で定義される行列を
【０２５４】
【数９４】
0006513557.tif 000095
【０２５５】
と書くこととする。その要素は次の（１８）式ように定義される。
【０２５６】
【数９５】
0006513557.tif 000096
【０２５７】
よって、上記（１３）式を修正して目的関数として以下（１９）式で定義されるものを考える。
【０２５８】
【数９６】
0006513557.tif 000097
【０２５９】
上記（１９）式の目的関数を最小化する因子行列
【０２６０】
【数９７】
0006513557.tif 000098
【０２６１】
の更新には、最急降下法やニュートン法が適用できる。目的関数の各因子行列の要素に関する微分はそれぞれ以下（２０）式、及び（２１）式のように与えられる。
【０２６２】
【数９８】
0006513557.tif 000099
ただし、＾ｐｉｊｋ＊は次の（２２）式のように定義した。
【０２６３】
【数９９】
0006513557.tif 000100
【０２６４】
よって最急降下法を用いる場合、次の（２３）式、及び（２４）式のような因子行列の更新が考えられる。
【０２６５】
【数１００】
0006513557.tif 000101
【０２６６】
ただし、因子行列の推定は最急降下法以外の任意の手法が適用可能である。
【０２６７】
上記により導かれた、価値関数がユーザ毎に関係性をもつ場合における価値関数
【０２６８】
【数１０１】
0006513557.tif 000102
【０２６９】
と、基本遷移関数
【０２７０】
【数１０２】
0006513557.tif 000103
【０２７１】
とを交互に更新するアルゴリズムが、第２の実施の形態に係る技術の新規性である。
【０２７２】
＜本発明の第２の実施の形態に係る内部基準推定装置の構成＞
【０２７３】
次に、本発明の実施の形態に係る内部基準推定装置の構成について説明する。なお、第１の実施の形態と同様となる箇所は同一符号を付して説明を省略する。
【０２７４】
上記図２に示すように、本発明の第２の実施の形態に係る内部基準推定装置１００は、第１の実施の形態と同様に、入出力部１５０と、遷移履歴処理部１０と、価値関数基本遷移関数推定部２０と、報酬関数推定部３０と、報酬関数処理部４０と、記録部５０とを備えている。
【０２７５】
第２の実施の形態に係る価値関数基本遷移関数推定部２０は、各ユーザが状態間を遷移した履歴を表す遷移履歴データに基づいて、ユーザ毎の各状態の目的地への到達しやすさを表す価値関数、及び状態間の基本遷移確率を推定する。また、価値関数基本遷移関数推定部２０は、基本遷移確率の推定において、遷移履歴データに基づいて、遷移履歴データに対するユーザ毎の価値関数及び状態間の基本遷移確率の尤もらしさを表す上記（１９）式に示す目的関数を最適化するように、ユーザ毎の価値関数、及び状態間の基本遷移確率を交互に更新することを繰り返す。ここでは、ユーザ毎の価値関数を更新する際に、遷移履歴データに対するユーザ毎の価値関数の因子行列及び状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、ユーザ毎の価値関数の因子行列を更新する。
【０２７６】
価値関数基本遷移関数推定部２０は、具体的には、ユーザ毎に以下に説明する第１〜第５の処理を行う。第１の処理は第１の実施の形態と同様の処理を行う。
【０２７７】
次に、価値関数基本遷移関数推定部２０は、第２の処理として、基本遷移関数の初期値又は前回更新された基本遷移関数に基づいて、基本遷移関数の値を固定し、上記（１９）式の目的関数の値を最小化するように、価値関数の因子行列
【０２７８】
【数１０３】
0006513557.tif 000104
【０２７９】
を上記（２３）式に従い更新する。この時、更新前と更新後の価値関数の因子行列
【０２８０】
【数１０４】
0006513557.tif 000105
【０２８１】
の差の絶対値の最大値ｍａｘｉｒ|ａｉｒｏｌｄ−ａｉｒｎｅｗ|がδより大きければδ←ｍａｘｉｒ|ａｉｒｏｌｄ−ｖｉｒｎｅｗ|と更新する。ただし更新前の価値関数の因子行列
【０２８２】
【数１０５】
0006513557.tif 000106
【０２８３】
の要素をａｉｒｏｌｄ、更新後の要素をａｉｒｎｅｗと記述した。
【０２８４】
次に、価値関数基本遷移関数推定部２０は、第３の処理として、基本遷移関数の初期値又は前回更新された基本遷移関数に基づいて、基本遷移関数の値を固定し、上記（１９）式の目的関数の値を最小化するように、価値関数の因子行列
【０２８５】
【数１０６】
0006513557.tif 000107
【０２８６】
を上記（２４）式に従い更新する。この時、更新前と更新後の価値関数の因子行列
【０２８７】
【数１０７】
0006513557.tif 000108
【０２８８】
の差の絶対値の最大値ｍａｘｉｒ|ｂｉｒｏｌｄ−ｂｉｒｎｅｗ|がδより大きければδ←ｍａｘｉｒ|ｂｉｒｏｌｄ−ｂｉｒｎｅｗ|と更新する。ただし更新前の価値関数の因子行列
【０２８９】
【数１０８】
0006513557.tif 000109
【０２９０】
の要素をｂｉｒｏｌｄ、更新後の要素をｂｉｒｎｅｗと記述した。また、価値関数基本遷移関数推定部２０における第４、及び第５の処理は、第１の実施の形態における第３、第４の処理と同様である。
【０２９１】
なお、第２の実施の形態における他の構成は、第１の実施の形態と同様であるため説明を省略する。
【０２９２】
＜本発明の第２の実施の形態に係る内部基準推定装置の作用＞
【０２９３】
次に、本発明の第２の実施の形態に係る内部基準推定装置１００の作用について説明する。第２の実施の形態では、上記図３に示す内部基準推定処理ルーチンにおいて、ステップＳ１０４の処理を次のステップＳ２００及びＳ２０２の処理に置き換えて実行する。
【０２９４】
ステップＳ２００では、基本遷移関数の初期値又は前回更新された基本遷移関数に基づいて、基本遷移関数の値を固定し、上記（１９）式の目的関数の値を最小化するように、ユーザ毎の価値関数の因子行列
【０２９５】
【数１０９】
0006513557.tif 000110
【０２９６】
を上記（２３）式に従って更新すると共に、ｍａｘｉｒ|ａｉｒｏｌｄ−ａｉｒｎｅｗ|＞δである場合に、変数δを更新する。
【０２９７】
ステップＳ２０２では、基本遷移関数の初期値又は前回更新された基本遷移関数に基づいて、基本遷移関数の値を固定し、上記（１９）式の目的関数の値を最小化するように、ユーザ毎の価値関数の因子行列
【０２９８】
【数１１０】
0006513557.tif 000111
【０２９９】
を上記（２４）式に従って更新すると共に、ｍａｘｉｒ|ｂｉｒｏｌｄ−ｂｉｒｎｅｗ|＞δである場合に、変数δを更新する。
【０３００】
なお、第２の実施の形態における他の作用は、第１の実施の形態と同様であるため説明を省略する。
【０３０１】
以上説明したように、本発明の第２の実施の形態に係る内部基準推定装置によれば、移動するユーザ毎に、ユーザが状態間を遷移した履歴を表す遷移履歴データに基づいて、上記（２３）式、（２４）式、及び（１７）式に従って、ユーザ毎の各状態の目的地への到達しやすさを表す価値関数、及び状態間の基本遷移確率を推定し、ユーザ毎の価値関数、及び状態間の基本遷移確率に基づいて、上記（１２）式に従って、ユーザ毎に、各状態についての目的地らしさを表す報酬関数を推定することにより、ユーザ毎に異なる報酬関数を推定することができる。
【０３０２】
＜本発明の第３の実施の形態に係る内部基準推定装置の構成＞
【０３０３】
次に、本発明の第３の実施の形態に係る内部基準推定装置の構成について説明する。なお、第２の実施の形態と同様となる箇所は同一符号を付して説明を省略する。
【０３０４】
第２の実施の形態では、ユーザ間の価値関数が関係性をもつことを仮定して、ユーザ毎に価値関数、及び基本遷移関数を推定し、ユーザ毎の報酬関数を推定していたが、第３の実施の形態では、時間帯間の価値関数が関係性をもつことを仮定して、時間帯毎の価値関数、及び基本遷移関数を推定し、時間帯毎の報酬関数を推定している点が第２の実施の形態と異なっている。また、本実施の形態において、時間帯毎の価値関数は、時間帯間で関係性を有している。
【０３０５】
上記図２に示すように、本発明の第３の実施の形態に係る内部基準推定装置１００は、第２の実施の形態と同様に、入出力部１５０と、遷移履歴処理部１０と、価値関数基本遷移関数推定部２０と、報酬関数推定部３０と、報酬関数処理部４０と、記録部５０とを備えている。
【０３０６】
第３の実施の形態に係る入出力部１５０は、外部装置２００から出力された、時間帯毎の、移動するユーザが状態間を遷移した履歴を表す遷移履歴データ
【０３０７】
【数１１１】
0006513557.tif 000112
【０３０８】
を受け付ける。また、入出力部１５０は、報酬関数処理部４０により得られた時間帯毎の報酬関数を、外部装置２００に出力する。
【０３０９】
価値関数基本遷移関数推定部２０は、時間帯毎に、対象物が状態間を遷移した履歴を表す遷移履歴データに基づいて、時間帯毎の各状態の目的地への到達しやすさを表す価値関数、及び状態間の基本遷移確率を推定する。また、価値関数基本遷移関数推定部２０は、基本遷移確率の推定において、遷移履歴データに基づいて、遷移履歴データに対する時間帯毎の価値関数及び状態間の基本遷移確率の尤もらしさを表す上記（１９）式に示す目的関数を最適化するように、時間帯毎の価値関数、及び状態間の基本遷移確率を交互に更新することを繰り返す。ここでは、時間帯毎の価値関数を更新する際に、遷移履歴データに対する時間帯毎の価値関数の因子行列及び状態間の基本遷移確率の尤もらしさを表す目的関数を最適化するように、時間帯毎の価値関数の因子行列を更新する。
【０３１０】
報酬関数推定部３０は、価値関数基本遷移関数推定部２０によって推定された時間帯毎の価値関数
【０３１１】
【数１１２】
0006513557.tif 000113
【０３１２】
、及び基本遷移関数
【０３１３】
【数１１３】
0006513557.tif 000114
【０３１４】
における状態間の基本遷移確率に基づいて、上記（１２）式に従って、時間帯毎に、各状態についての目的地らしさを表す報酬関数
【０３１５】
【数１１４】
0006513557.tif 000115
【０３１６】
を推定し、報酬関数記録部５４に格納する。
【０３１７】
報酬関数処理部４０は報酬関数記録部５４に格納された時間帯毎の報酬関数
【０３１８】
【数１１５】
0006513557.tif 000116
【０３１９】
を外部装置２００に出力する。
【０３２０】
なお、第３の実施の形態の他の構成及び作用は、上記の実施の形態におけるユーザｉを、時間帯ｉに置き換えれば、第２の実施の形態と同様であるため説明を省略する。
【０３２１】
以上説明したように、本発明の第３の実施の形態に係る内部基準推定装置によれば、時間帯毎に、対象物が状態間を遷移した履歴を表す遷移履歴データに基づいて、上記（２３）式、（２４）式、及び（１７）式に従って、時間帯毎の各状態の目的地への到達しやすさを表す価値関数、及び状態間の基本遷移確率を推定し、時間帯毎の価値関数、及び状態間の基本遷移確率に基づいて、上記（１２）式に従って、時間帯毎に、各状態についての目的地らしさを表す報酬関数を推定することにより、時間帯毎に異なる報酬関数を推定することができる。
【０３２２】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０３２３】
例えば、上述した第２及び第３の実施の形態では、各因子行列
【０３２４】
【数１１６】
0006513557.tif 000117
【０３２５】
の更新式に最急降下法を利用しているが、上記（１９）式を最小化する他のいかなる方法を用いても良い。また、上記の実施の形態の図２に示す内部基準推定装置は、各構成要素の動作をプログラムとして構築し、内部基準推定装置として利用されるコンピュータにインストールして実行させる、またはネットワークを介して流通させることが可能である。
【０３２６】
また、上記の第３の実施の形態において、時間帯間の価値関数が独立である場合を仮定して、時間帯毎に異なる報酬関数を推定することができる。この場合には、上記の第１の実施の形態と同様に、上記（１４）式を用いて価値関数を推定すればよい。
【０３２７】
また、移動する対象物が、人物である場合を例に説明したが、これに限定されるものではなく、移動する対象物として、人物以外のもの、例えば、ロボット、動物、車両などであってもよい。
【符号の説明】
【０３２８】
１０   遷移履歴処理部
２０   価値関数基本遷移関数推定部
３０   報酬関数推定部
４０   報酬関数処理部
５０   記録部
５１   遷移履歴記録部
５２   基本遷移関数記録部
５３   価値関数記録部
５４   報酬関数記録部
９１   遷移履歴記録部
１００ 内部基準推定装置
１５０ 入出力部
２００ 外部装置
【図１】
0006513557.tif 000118
【図２】
0006513557.tif 000119
【図３】
0006513557.tif 000120