(57)【要約】【課題】十分なデータが存在しない道や場所があったとしても、妥当な値として潜在コストを推定する。【解決手段】潜在コスト推定装置８０は、入力された、移動する対象物が状態間を遷移した履歴を表す遷移履歴データ、及び状態間の基本遷移確率に基づいて、状態間の基本遷移確率、及び遷移履歴データから得られる状態間の遷移回数を用いて表される、各状態の目的地への到達し易さを表す価値関数の尤もらしさを表す尤度関数に、状態間の基本遷移確率から求められる、隣接する状態間の価値関数が類似した値となることを表すグラフラプラシアン正則化項を加えた目的関数を最適化することにより、各状態の価値関数を推定する価値関数推定部３０と、価値関数推定部３０によって推定された各状態の価値関数、及び状態間の基本遷移確率に基づいて、各状態についての目的地らしさを表す報酬関数を計算する報酬関数計算部４０と、を含む。【選択図】図２
2018197892.tif 000002
【特許請求の範囲】
【請求項１】
入力された、移動する対象物が状態間を遷移した履歴を表す遷移履歴データ、及び前記状態間の基本遷移確率に基づいて、前記状態間の基本遷移確率、及び前記遷移履歴データから得られる状態間の遷移回数を用いて表される、各状態の目的地への到達し易さを表す価値関数の尤もらしさを表す尤度関数に、前記状態間の基本遷移確率から求められる、隣接する状態間の価値関数が類似した値となることを表すグラフラプラシアン正則化項を加えた目的関数を最適化することにより、各状態の価値関数を推定する価値関数推定部と、
前記価値関数推定部によって推定された各状態の価値関数、及び前記状態間の基本遷移確率に基づいて、各状態についての目的地らしさを表す報酬関数を計算する報酬関数計算部と、
を含む潜在コスト推定装置。
【請求項２】
前記尤度関数は、前記状態間の基本遷移確率を用いて表される、最適方策により行動を選択する場合の状態間の遷移確率、及び前記遷移履歴データから得られる状態間の遷移回数を用いて表され、
前記報酬関数計算部は、前記価値関数推定部によって推定された各状態の価値関数、及び前記状態間の基本遷移確率を用いて表される、最適方策により行動を選択する場合の状態間の遷移確率に基づいて、各状態についての報酬関数を計算する請求項１に記載の潜在コスト推定装置。
【請求項３】
前記遷移履歴データは、対象物毎又は時間帯毎に入力され、
前記価値関数推定部は、前記対象物毎又は時間帯毎に、前記遷移履歴データを用いて、各状態の価値関数を推定し、
前記報酬関数計算部は、前記対象物毎又は時間帯毎に、各状態についての報酬関数を計算する請求項１又は２に記載の潜在コスト推定装置。
【請求項４】
前記価値関数推定部は、予め定められた反復終了条件を満たすまで、前記目的関数を最適化するように、前記価値関数を更新することを繰り返すことにより、各状態の価値関数を推定する請求項１〜３のいずれか１項に記載の潜在コスト推定装置。
【請求項５】
価値関数推定部が、入力された、移動する対象物が状態間を遷移した履歴を表す遷移履歴データ、及び前記状態間の基本遷移確率に基づいて、前記状態間の基本遷移確率、及び前記遷移履歴データから得られる状態間の遷移回数を用いて表される、各状態の目的地への到達し易さを表す価値関数の尤もらしさを表す尤度関数に、前記状態間の基本遷移確率から求められる、隣接する状態間の価値関数が類似した値となることを表すグラフラプラシアン正則化項を加えた目的関数を最適化することにより、各状態の価値関数を推定するステップと、
報酬関数計算部が、前記価値関数推定部によって推定された各状態の価値関数、及び前記状態間の基本遷移確率に基づいて、各状態についての目的地らしさを表す報酬関数を計算するステップと、
を含む潜在コスト推定方法。
【請求項６】
前記尤度関数は、前記状態間の基本遷移確率を用いて表される、最適方策により行動を選択する場合の状態間の遷移確率、及び前記遷移履歴データから得られる状態間の遷移回数を用いて表され、
前記報酬関数計算部が計算するステップは、前記価値関数推定部によって推定された各状態の価値関数、及び前記状態間の基本遷移確率を用いて表される、最適方策により行動を選択する場合の状態間の遷移確率に基づいて、各状態についての報酬関数を計算する請求項５に記載の潜在コスト推定方法。
【請求項７】
コンピュータを、請求項１〜４のいずれか１項に記載の潜在コスト推定装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、潜在コスト推定装置、方法、及びプログラムに係り、特に、対象物の移動経路における潜在的なコストを推定する潜在コスト推定装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
近年、人や車等の対象物の移動経路の選択をモデリングする手法として、逆強化学習（ＩＲＬ：Inverse Reinforcement Learning）と呼ばれる手法が利用されている（例えば、非特許文献１、２を参照）。ＩＲＬでは、対象物の一例である人の移動の際に通る道や場所に潜在的なコストが存在し、人は経路全体で支払うコストの和が小さい経路をより高い確率で選択しやすくなると仮定してモデル化される。
【０００３】
上記の仮定に基づいて、ＩＲＬでは、その人の過去の移動履歴から、その人にとっての各道や場所における潜在的なコストを推定する。例えば、非特許文献２に記載されているように、あるタクシー運転手の移動履歴を入力とすることで、その運転手における各道のコストを推定し、運転手の好む、コストの低い道路特性、例えば、整備されている道路を好むか、カーブのゆるやかな道路を好むか等を知ることができる。また、この運転手がある目的地に至るまでに選択しやすい経路がどれであるかを見つけることができる。ほかにもロボット制御、自然言語処理における特筆すべき成功例も存在する（例えば、非特許文献３、４を参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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.
【非特許文献３】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 Szepesv_ari. 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.
【非特許文献７】Mikhail Belkin, Irina Matveeva, and Partha Niyogi. Regularization and Semi-supervised Learning on Large Graphs. In International Conference on Computational Learning Theory, pages 624-638. Springer, 2004.
【非特許文献８】Dengyong Zhou, Bernhard Scholkopf, and Thomas Hofmann. Semi-supervised learning on directed graphs. In NIPS, volume 5, pages 1633-1640, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、既存のＩＲＬ手法では、あまり通過する人の少ない、つまり、データ数が少ない道や場所が存在するとき、推定性能が悪化する場合がある。これは、通過する人が少ないのは、該当する道や場所のコストが非常に高いと推定してしまうことが原因と考えられる。
【０００６】
この場合、十分なデータが集まっていない場所における、次の移動場所は、とりうる選択肢の中からランダムで決まるように、コストが推定されていることが現実的な妥協策になると考えられるが、既存のＩＲＬ手法では、このような性質が満たされるようにコストを推定することができない。
【０００７】
本発明は、上記の事情に鑑みてなされたもので、十分なデータが存在しない道や場所があったとしても、妥当な値として潜在コストを推定することができる潜在コスト推定装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、第１の発明に係る潜在コスト推定装置は、入力された、移動する対象物が状態間を遷移した履歴を表す遷移履歴データ、及び前記状態間の基本遷移確率に基づいて、前記状態間の基本遷移確率、及び前記遷移履歴データから得られる状態間の遷移回数を用いて表される、各状態の目的地への到達し易さを表す価値関数の尤もらしさを表す尤度関数に、前記状態間の基本遷移確率から求められる、隣接する状態間の価値関数が類似した値となることを表すグラフラプラシアン正則化項を加えた目的関数を最適化することにより、各状態の価値関数を推定する価値関数推定部と、前記価値関数推定部によって推定された各状態の価値関数、及び前記状態間の基本遷移確率に基づいて、各状態についての目的地らしさを表す報酬関数を計算する報酬関数計算部と、を含むものである。
【０００９】
第２の発明に係る潜在コスト推定装置は、第１の発明において、前記尤度関数が、前記状態間の基本遷移確率を用いて表される、最適方策により行動を選択する場合の状態間の遷移確率、及び前記遷移履歴データから得られる状態間の遷移回数を用いて表され、前記報酬関数計算部が、前記価値関数推定部によって推定された各状態の価値関数、及び前記状態間の基本遷移確率を用いて表される、最適方策により行動を選択する場合の状態間の遷移確率に基づいて、各状態についての報酬関数を計算するものである。
【００１０】
第３の発明に係る潜在コスト推定装置は、第１又は第２の発明において、前記遷移履歴データが、対象物毎又は時間帯毎に入力され、前記価値関数推定部が、前記対象物毎又は時間帯毎に、前記遷移履歴データを用いて、各状態の価値関数を推定し、前記報酬関数計算部が、前記対象物毎又は時間帯毎に、各状態についての報酬関数を計算するものである。
【００１１】
第４の発明に係る潜在コスト推定装置は、第１〜第３のいずれかの発明において、前記価値関数推定部が、予め定められた反復終了条件を満たすまで、前記目的関数を最適化するように、前記価値関数を更新することを繰り返すことにより、各状態の価値関数を推定するものである。
【００１２】
第５の発明に係る潜在コスト推定方法は、価値関数推定部が、入力された、移動する対象物が状態間を遷移した履歴を表す遷移履歴データ、及び前記状態間の基本遷移確率に基づいて、前記状態間の基本遷移確率、及び前記遷移履歴データから得られる状態間の遷移回数を用いて表される、各状態の目的地への到達し易さを表す価値関数の尤もらしさを表す尤度関数に、前記状態間の基本遷移確率から求められる、隣接する状態間の価値関数が類似した値となることを表すグラフラプラシアン正則化項を加えた目的関数を最適化することにより、各状態の価値関数を推定するステップと、報酬関数計算部が、前記価値関数推定部によって推定された各状態の価値関数、及び前記状態間の基本遷移確率に基づいて、各状態についての目的地らしさを表す報酬関数を計算するステップと、を含むものである。
【００１３】
第６の発明に係る潜在コスト推定方法は、第５の発明において、前記尤度関数が、前記状態間の基本遷移確率を用いて表される、最適方策により行動を選択する場合の状態間の遷移確率、及び前記遷移履歴データから得られる状態間の遷移回数を用いて表され、前記報酬関数計算部が計算するステップが、前記価値関数推定部によって推定された各状態の価値関数、及び前記状態間の基本遷移確率を用いて表される、最適方策により行動を選択する場合の状態間の遷移確率に基づいて、各状態についての報酬関数を計算するものである。
【００１４】
第７の発明に係るプログラムは、コンピュータを、第１〜第４のいずれかの発明に係る潜在コスト推定装置が備える各部として機能させるためのプログラムである。
【発明の効果】
【００１５】
以上説明したように、本発明に係る潜在コスト推定装置、方法、及びプログラムによれば、十分なデータが存在しない道や場所があったとしても、妥当な値として潜在コストを推定することができる。
これによって、データが少ない場所からの移動の予測の誤差が大きくなることを避けることができ、全体としてより正確に人等の対象物が選択する移動経路を予測することができるようになる。
【図面の簡単な説明】
【００１６】
【図１】実施形態に係る線形可解マルコフ決定過程（ＬＭＤＰ）における状態集合、基本遷移関数、及び報酬関数の一例を示す模式図である。
【図２】実施形態に係る潜在コスト推定装置の構成の一例を示すブロック図である。
【図３】実施形態に係る潜在コスト推定プログラムの処理の流れの一例を示すフローチャートである。
【図４】実施形態に係る潜在コスト推定プログラムのサブルーチンの処理の流れの一例を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、図面を参照して、本発明を実施するための形態の一例について詳細に説明する。
【００１８】
＜本発明の実施形態に係る原理＞
【００１９】
まず、本発明の実施形態における原理を、上記非特許文献５〜８を参考文献として提示しながら説明する。ここでは、本実施形態に係る構成及び作用の説明において用いる記号、アルゴリズムについて記述する。なお、本実施形態においては、対象物の一例であるユーザ（人）毎に異なる行動の内部基準（後述する報酬関数に相当する）が存在する例を用いて説明するが、時間帯毎に異なる内部基準が存在する場合であっても同様に適用することができる。
【００２０】
［線形可解マルコフ決定過程（ＬＭＤＰ：Linearly-solvable Markov Decision Process）の定義］
まず、上記非特許文献５を参照して、線形可解マルコフ決定過程（ＬＭＤＰ）について説明する。線形可解マルコフ決定過程（ＬＭＤＰ）では、状態集合
【００２１】
【数１】
2018197892.tif 000003
【００２２】
、基本遷移関数
【００２３】
【数２】
2018197892.tif 000004
【００２４】
、報酬関数
【００２５】
【数３】
2018197892.tif 000005
【００２６】
が定義された環境を考える。一例として、あるユーザについての状態数をＪとし、状態集合を
【００２７】
【数４】
2018197892.tif 000006
【００２８】
、基本遷移関数をＪ×Ｊ行列
【００２９】
【数５】
2018197892.tif 000007
【００３０】
、報酬関数をＪ列ベクトル
【００３１】
【数６】
2018197892.tif 000008
【００３２】
と定義する。上記３つ組
【００３３】
【数７】
2018197892.tif 000009
【００３４】
の具体例を図１に示す。なお、図１は、本実施形態に係る線形可解マルコフ決定過程（ＬＭＤＰ）における状態集合、基本遷移関数、及び報酬関数の一例を示す模式図である。図１中の各グリッドが、状態集合
【００３５】
【数８】
2018197892.tif 000010
【００３６】
中のいずれかの状態ｓｊに対応し、各グリッド間の“基本的な”遷移の確率（基本遷移確率）が基本遷移関数
【００３７】
【数９】
2018197892.tif 000011
【００３８】
で決められている。“基本的な”と注釈をつけたのは、ＬＭＤＰでは行動
【００３９】
【数１０】
2018197892.tif 000012
【００４０】
を実行し、行動コストを支払うことで、この遷移の確率を変更することが許されているからである。具体的には、行動
【００４１】
【数１１】
2018197892.tif 000013
【００４２】
を実行することで、状態ｊから状態ｋへの遷移の確率を
【００４３】
【数１２】
2018197892.tif 000014
【００４４】
から
【００４５】
【数１３】
2018197892.tif 000015
【００４６】
へ変更することができる。
【００４７】
【数１４】
2018197892.tif 000016
【００４８】
ａｊの値が大きければ大きいほど、状態ｊへの遷移の確率を増加できることがわかる。ただし、
【００４９】
【数１５】
2018197892.tif 000017
【００５０】
の値は確率の和が１となることを満たすもの、すなわち
【００５１】
【数１６】
2018197892.tif 000018
【００５２】
を満たすものに限られる。
【００５３】
【数１７】
2018197892.tif 000019
【００５４】
また、上記のように状態ｊで行動
【００５５】
【数１８】
2018197892.tif 000020
【００５６】
を実行することにより発生するコスト
【００５７】
【数１９】
2018197892.tif 000021
【００５８】
は、確率分布の類似度を図る尺度であるＫＬ（カルバックライブラーダイバージェンス）距離を用いて以下（３）式のように定義される。ＫＬ距離は、値が小さいほど類似していることを表し、一致すれば０となる。
【００５９】
【数２０】
2018197892.tif 000022
【００６０】
つまり、上記（３）式においては遷移の確率を
【００６１】
【数２１】
2018197892.tif 000023
【００６２】
から変化させればさせるほど、支払うコストが多くなる。上記の行動コストとは別に、状態のみに依存した状態コストを表すのが、報酬関数
【００６３】
【数２２】
2018197892.tif 000024
【００６４】
である。上記図１の例で示すように、この報酬関数の値ｒｊは、例えば、“状態ｊの目的地らしさ”に対応した値などに対応し、値が小さいほど目的地らしいといえる。さらに、各状態ｓｊにおいて実行する行動
【００６５】
【数２３】
2018197892.tif 000025
【００６６】
を定めたものを方策
【００６７】
【数２４】
2018197892.tif 000026
【００６８】
と呼ぶこととする。
【００６９】
方策πにしたがって行動する人や車を考えると、上記（１）式にしたがって確率的に状態間を遷移し、遷移する度に行動コストと状態コストとの和
【００７０】
【数２５】
2018197892.tif 000027
【００７１】
を支払う動きがモデリングできる。状態遷移を十分な回数繰り返した際に、遷移の過程で支払ったコスト（行動コストと状態コストとの和）の累積和の期待値が最小になるような方策を最適方策と呼び、
【００７２】
【数２６】
2018197892.tif 000028
【００７３】
と書く。すなわち、最適方策とは、先ほどの例を用いると、できるだけ少ない行動コストで状態コストの低い目的地に早く到達できる方策であり、直感的には、目的地に到達する最適な手順を表しているとみなせる。このように、基本遷移関数
【００７４】
【数２７】
2018197892.tif 000029
【００７５】
と報酬関数
【００７６】
【数２８】
2018197892.tif 000030
【００７７】
が既知の時に、最適方策
【００７８】
【数２９】
2018197892.tif 000031
【００７９】
を求める問題が、ＬＭＤＰにおける順問題である。最適方策は、以下（４）式の最適性方程式を満たす価値関数
【００８０】
【数３０】
2018197892.tif 000032
2018197892.tif 000033
【００８１】
を求めることで、次の（６）式のように算出できる。なお、上記（４）式から（５）式への式展開は、上記非特許文献５を参照できる。また、価値関数は、各状態の目的地への到達しやすさを表す。価値関数の求め方は後述する。
【００８２】
【数３１】
2018197892.tif 000034
【００８３】
ただし、γは、割引率
【００８４】
【数３２】
2018197892.tif 000035
【００８５】
であり、将来に得る報酬をどれだけ減衰させて評価するかを定めるものである。ここで、上記（６）式により得られた最適方策の値を上記（１）式に代入することで、最適方策により行動を選択する場合の遷移確率は、以下（７）式で与えられることがわかる。
【００８６】
【数３３】
2018197892.tif 000036
【００８７】
したがって、価値関数
【００８８】
【数３４】
2018197892.tif 000037
【００８９】
が計算できれば、ＬＭＤＰの順問題が解けることになる。
【００９０】
［価値関数計算アルゴリズム］
次に、価値関数を計算するアルゴリズムについて説明する。価値関数を計算するアルゴリズムは上記（５）式から導かれる。両辺の符号を変換したのち、指数をとると、以下の（８）式が求まる。
【００９１】
【数３５】
2018197892.tif 000038
【００９２】
ここで、
【００９３】
【数３６】
2018197892.tif 000039
【００９４】
と定義すると、上記（８）式は、以下（９）式のようにベクトル表記できる。
【００９５】
【数３７】
2018197892.tif 000040
【００９６】
そして、以下（１０）式に従い、
【００９７】
【数３８】
2018197892.tif 000041
【００９８】
と収束するまで更新することで、上記（９）式を満たす
【００９９】
【数３９】
2018197892.tif 000042
【０１００】
を求めることができる（上記非特許文献５を参照）。
【０１０１】
【数４０】
2018197892.tif 000043
【０１０２】
最後に、
【０１０３】
【数４１】
2018197892.tif 000044
【０１０４】
の定義より、ｖｊ＝−ｌｏｇ（ｚｊ）
【０１０５】
と変換することで、価値関数
【０１０６】
【数４２】
2018197892.tif 000045
【０１０７】
が求まる。以上がＬＭＤＰの順問題の解法である。
【０１０８】
［逆問題の解法］
次に、上記非特許文献６を参照して、ＬＭＤＰの逆問題を説明する。ＬＭＤＰの逆問題は、人、ロボットの遷移の系列と基本遷移関数とを入力とし、報酬関数を推定する問題、として定式化される。逆問題における解法の鍵は、人、ロボットの遷移が上記（７）式の最適方策による遷移確率にしたがって得られているとみなすことにある。遷移履歴データ
【０１０９】
【数４３】
2018197892.tif 000046
【０１１０】
を（遷移前の状態、遷移後の状態）という１ステップの遷移の履歴の集合で表現し、
【０１１１】
【数４４】
2018197892.tif 000047
【０１１２】
を状態ｊから状態ｋへ遷移した回数とする。また、以後の記述で、
【０１１３】
【数４５】
2018197892.tif 000048
【０１１４】
のように、添え字の一部をドット記号で記述されている場合には、その添え字に関しては和をとった値を表すこととする。すなわち、
【０１１５】
【数４６】
2018197892.tif 000049
【０１１６】
である。価値関数
【０１１７】
【数４７】
2018197892.tif 000050
【０１１８】
を未知のパラメタとみなすと、上記（７）式から、負の対数尤度関数
【０１１９】
【数４８】
2018197892.tif 000051
【０１２０】
を最小化する
【０１２１】
【数４９】
2018197892.tif 000052
【０１２２】
が、入力の遷移の履歴
【０１２３】
【数５０】
2018197892.tif 000053
【０１２４】
を生成する確率の最も高い最尤推定量
【０１２５】
【数５１】
2018197892.tif 000054
【０１２６】
となる。
【０１２７】
【数５２】
2018197892.tif 000055
【０１２８】
上記の尤度関数の最小化には、最急降下法やニュートン法など任意の方法が適用できる。上記（５）式に最尤推定量
【０１２９】
【数５３】
2018197892.tif 000056
【０１３０】
を代入すれば、報酬関数は、次の（１２）式により求めることができる。
【０１３１】
【数５４】
2018197892.tif 000057
【０１３２】
以上がＬＭＤＰの逆問題の解法である。
【０１３３】
＜本発明の実施形態に係る概要＞
【０１３４】
本実施形態に係る手法は、既存手法では不可能であった、十分なデータが存在しない道や場所があったとしても、妥当な値として潜在コストを推定することを可能とする手法である。本実施形態における主な特徴部分は、上記（１１）式で示される尤度関数に、グラフラプラシアン正則化項(ＧＬＲ: Graph Laplacian Regularization)を加えて目的関数とするところにある。
【０１３５】
上記ＧＬＲは、グラフ上のノードが値をもつ場合に隣接するノードの値が類似した値をとるほど小さい値をとる項であり、ノードの値を予測する半教師付き学習などで用いられている（例えば、上記非特許文献７、８を参照)。
【０１３６】
上記ＧＬＲは、グラフの隣接情報を利用して定義され、上記非特許文献７では、無向グラフ上で定義するＧＬＲが利用され、上記非特許文献８では、有向グラフ上で定義するＧＬＲが利用されている。
【０１３７】
本実施形態では、上記のいずれのグラフでも利用することができる。ＬＭＤＰでは、基本遷移関数が隣接情報を表現するため、例えば、状態ｊから状態ｋに遷移する基本遷移確率
【０１３８】
【数５５】
2018197892.tif 000058
【０１３９】
と、状態ｋから状態ｊに遷移する確率基本遷移確率
【０１４０】
【数５６】
2018197892.tif 000059
【０１４１】
との少なくとも片方が０より大きく、状態ｊと状態ｋに枝があるとみなすと、基本遷移関数から無向グラフを作ることができる。作成した無向グラフの隣接行列を
【０１４２】
【数５７】
2018197892.tif 000060
【０１４３】
と書く。隣接行列Ｗの行列要素
【０１４４】
【数５８】
2018197892.tif 000061
【０１４５】
は、状態ｊと状態ｋの間に枝があれば、
【０１４６】
【数５９】
2018197892.tif 000062
【０１４７】
、そうでなければ、
【０１４８】
【数６０】
2018197892.tif 000063
【０１４９】
、と定義される。
【０１５０】
【数６１】
2018197892.tif 000064
【０１５１】
【数６２】
2018197892.tif 000065
【０１５２】
は、
【０１５３】
【数６３】
2018197892.tif 000066
【０１５４】
と定義され、行列
【０１５５】
【数６４】
2018197892.tif 000067
【０１５６】
がグラフラプラシアンと呼ばれる量と対応していることからＧＬＲと呼ばれている。有向グラフにおけるＧＬＲも上記と同様にある行列
【０１５７】
【数６５】
2018197892.tif 000068
【０１５８】
を用いて
【０１５９】
【数６６】
2018197892.tif 000069
【０１６０】
と表現することができる(詳細は非特許文献８を参照)。また、行列
【０１６１】
【数６７】
2018197892.tif 000070
【０１６２】
と行列
【０１６３】
【数６８】
2018197892.tif 000071
【０１６４】
の定義が異なるだけで、以後の議論はどちらのＧＬＲを用いても成り立つ。また、上記以外にもグラフ構造を利用して隣接状態が類似した値をとるように設計された正則化項であって、ある行列
【０１６５】
【数６９】
2018197892.tif 000072
【０１６６】
を用いて
【０１６７】
【数７０】
2018197892.tif 000073
【０１６８】
と書き表せるものであれば、任意のものが利用できる。このため、以後は、ＧＬＲ項を
【０１６９】
【数７１】
2018197892.tif 000074
【０１７０】
と書く。よって、本実施形態においては、目的関数として、上記(１１)式に、上記ＧＬＲ項を加えた以下の式を最小化することで、価値関数を推定する。
【０１７１】
【数７２】
2018197892.tif 000075
【０１７２】
ただし、αは重みパラメタである。上記の関数の最小化には、最急降下法やニュートン法など任意の方法が適用できる。例えば、最急降下法を用いた場合の更新式は、以下のようになる。
【０１７３】
【数７３】
2018197892.tif 000076
【０１７４】
上記ＧＬＲ項の導入によって、例えば、十分なデータが存在しない状態があるときには、
【０１７５】
【数７４】
2018197892.tif 000077
【０１７６】
の値が小さいことから、状態
【０１７７】
【数７５】
2018197892.tif 000078
【０１７８】
に関する項については、上記（１６）式中において、ＧＬＲ項の値がより大きく寄与することとなり、
【０１７９】
【数７６】
2018197892.tif 000079
【０１８０】
が隣接する状態、例えば、状態ｋの価値関数値と近い値となるとき、目的関数が小さくなり、その値が推定値となる。そうなると、上記（７）式より、例えば、状態
【０１８１】
【数７７】
2018197892.tif 000080
【０１８２】
に隣接する状態ｊがあれば、状態ｊから状態ｋに遷移する確率と、状態ｊから状態
【０１８３】
【数７８】
2018197892.tif 000081
【０１８４】
に遷移する確率とが近い値となる。これによって、状態
【０１８５】
【数７９】
2018197892.tif 000082
【０１８６】
においてデータ数が十分存在しない場合であっても、状態
【０１８７】
【数８０】
2018197892.tif 000083
【０１８８】
に遷移する確率を低い値と推定することなく、価値関数とコストに対応する報酬関数を推定することが可能になる。
【０１８９】
＜本発明の実施形態に係る潜在コスト推定装置の構成＞
【０１９０】
図２は、本実施形態に係る潜在コスト推定装置８０の構成の一例を示すブロック図である。
図２に示すように、本実施形態に係る潜在コスト推定装置８０は、ＣＰＵ（Central Processing Unit）、ＲＡＭ(Random Access Memory)、ＲＯＭ(Read Only Memory)、及びＨＤＤ(Hard Disk Drive)等を備えたコンピュータとして構成される。ＲＯＭには、本実施形態に係る潜在コスト推定プログラムが記憶されている。なお、潜在コスト推定プログラムは、ＨＤＤに記憶されていてもよい。
【０１９１】
上記の潜在コスト推定プログラムは、例えば、潜在コスト推定装置８０に予めインストールされていてもよい。この潜在コスト推定プログラムは、不揮発性の記憶媒体に記憶して、又は、ネットワークを介して配布して、潜在コスト推定装置８０に適宜インストールすることで実現してもよい。なお、不揮発性の記憶媒体の例としては、ＣＤ-ＲＯＭ(Compact Disc Read Only Memory)、光磁気ディスク、ＤＶＤ-ＲＯＭ(Digital Versatile Disc Read Only Memory)、フラッシュメモリ、メモリカード等が挙げられる。
【０１９２】
ＣＰＵは、ＲＯＭに記憶されている潜在コスト推定プログラムを読み込んで実行することにより、遷移履歴処理部１０、基本遷移関数処理部２０、価値関数推定部３０、報酬関数計算部４０、及び報酬関数処理部５０として機能する。また、ＨＤＤは、記録部６０として機能する。記録部６０は、遷移履歴記録部６１、基本遷移関数記録部６２、価値関数記録部６３、及び報酬関数記録部６４を含む。
【０１９３】
潜在コスト推定装置８０は、入出力部７０を備える。入出力部７０は、外部装置８２から出力された、対象物が状態間を遷移した履歴を表す遷移履歴データ
【０１９４】
【数８１】
2018197892.tif 000084
【０１９５】
の入力を受け付ける。本実施の形態では、推定対象の対象物毎に、当該対象物が状態間を遷移した履歴を表す遷移履歴データの入力を受け付ける。
【０１９６】
遷移履歴処理部１０は、入出力部７０により入力を受け付けた遷移履歴データ
【０１９７】
【数８２】
2018197892.tif 000085
【０１９８】
を遷移履歴記録部６１に格納する。
【０１９９】
また、入出力部７０は、外部装置８２から出力された、状態間の基本遷移関数
【０２００】
【数８３】
2018197892.tif 000086
【０２０１】
の入力を受け付ける。
【０２０２】
基本遷移関数処理部２０は、入出力部７０により入力を受け付けた基本遷移関数
【０２０３】
【数８４】
2018197892.tif 000087
【０２０４】
を基本遷移関数記録部６２に格納する。
【０２０５】
価値関数推定部３０は、推定対象の対象物毎に、遷移履歴記録部６１に格納された当該対象物の遷移履歴データ
【０２０６】
【数８５】
2018197892.tif 000088
【０２０７】
及び基本遷移関数記録部６２に格納された基本遷移関数
【０２０８】
【数８６】
2018197892.tif 000089
【０２０９】
を入力とし、各状態の目的地への到達し易さを表す価値関数の尤もらしさを表す尤度関数（上記（１１）式）に、隣接する状態間の価値関数が類似した値であることを表すＧＬＲ項（上記（１５）式）を加えた目的関数（上記（１６）式）を最適化するように、各状態の目的地への到達し易さを表す価値関数
【０２１０】
【数８７】
2018197892.tif 000090
【０２１１】
を推定する。本実施形態では、目的関数を最小化することで、最適化しているが、利用する目的関数の種類によっては、目的関数を最大化することで、最適化してもよい。なお、上記尤度関数は、状態間の基本遷移確率を用いて表される、最適方策により行動を選択する場合の状態間の遷移確率（上記（７）式）、及び、遷移履歴データから得られる状態間の遷移回数を用いて表される。また、上記ＧＬＲ項は、状態間の基本遷移確率から求められる正則化項である。本実施形態に係る価値関数推定部３０は、上記目的関数を最小化することにより、各状態の目的地への到達し易さを表す価値関数
【０２１２】
【数８８】
2018197892.tif 000091
【０２１３】
を推定し、推定した価値関数
【０２１４】
【数８９】
2018197892.tif 000092
【０２１５】
を価値関数記録部６３に格納する。
【０２１６】
具体的には、価値関数推定部３０は、予め定められた反復終了条件を満たすまで、上記（１６）式で示される目的関数を最小化するように、価値関数を更新することを繰り返すことにより、各状態の価値関数を推定する。一例として、価値関数推定部３０は、上記（１６）式で示される目的関数が最小化するように、価値関数
【０２１７】
【数９０】
2018197892.tif 000093
【０２１８】
を所定の更新式（上述の最急降下法やニュートン法など）に従って更新する。そして、価値関数推定部３０は、更新前と更新後の価値関数
【０２１９】
【数９１】
2018197892.tif 000094
【０２２０】
の差の絶対値の最大値
【０２２１】
【数９２】
2018197892.tif 000095
【０２２２】
が、価値関数の更新量の最大変化幅を示す変数δより大きい場合に、変数δを上記最大値に更新する。但し、更新前の価値関数の要素を
【０２２３】
【数９３】
2018197892.tif 000096
【０２２４】
、更新後の要素を
【０２２５】
【数９４】
2018197892.tif 000097
【０２２６】
と記述した。
【０２２７】
そして、価値関数推定部３０は、変数δが予め定められた閾値εより小さい場合に、価値関数の更新を終了する。また、価値関数推定部３０は、価値関数の更新を繰り返し、繰り返し回数をカウントする。この場合、価値関数推定部３０は、カウントした繰り返し回数が予め定められた最大繰り返し回数を超える場合に、価値関数の更新を終了してもよい。
【０２２８】
報酬関数計算部４０は、推定対象の対象物毎に、基本遷移関数記録部６２に格納された基本遷移関数
【０２２９】
【数９５】
2018197892.tif 000098
【０２３０】
及び価値関数記録部６３に格納された当該対象物の価値関数
【０２３１】
【数９６】
2018197892.tif 000099
【０２３２】
を入力とし、各状態の価値関数、及び、状態間の基本遷移確率を用いて表される、最適方策により行動を選択する場合の状態間の遷移確率に基づいて、上記（１２）式を用いて、各状態についての目的地らしさを表す報酬関数
【０２３３】
【数９７】
2018197892.tif 000100
【０２３４】
を計算し、報酬関数記録部６４に格納する。
【０２３５】
報酬関数処理部５０は、報酬関数記録部６４に格納された報酬関数
【０２３６】
【数９８】
2018197892.tif 000101
【０２３７】
を、入出力部７０を介して外部装置８２に出力する。
【０２３８】
なお、本実施形態では、上記遷移履歴データが対象物毎に入力される場合について説明したが、上記遷移履歴データが時間帯毎に入力される場合についても同様に適用することができる。この場合、価値関数推定部３０は、時間帯毎に、当該時間帯において対象物が状態間を遷移した履歴を表す遷移履歴データを用いて、各状態の価値関数を推定する。報酬関数計算部４０は、時間帯毎に、各状態についての報酬関数を計算する。
【０２３９】
＜本発明の実施形態に係る潜在コスト推定装置の作用＞
【０２４０】
次に、図３を参照して、本実施形態に係る潜在コスト推定装置８０の作用について説明する。なお、図３は、本実施形態に係る潜在コスト推定プログラムの処理の流れの一例を示すフローチャートである。
【０２４１】
まず、図３のステップ１００では、遷移履歴処理部１０が、外部装置８２から入出力部７０を介して遷移履歴データの入力を受け付け、遷移履歴記録部６１に格納する。一方、基本遷移関数処理部２０は、外部装置８２から入出力部７０を介して基本遷移関数の入力を受け付け、基本遷移関数を基本遷移関数記録部６２に格納する。
【０２４２】
ステップ１０２では、価値関数推定部３０が、遷移履歴記録部６１に格納された遷移履歴データ、及び、基本遷移関数記録部６２に格納された基本遷移関数に基づいて、上記（１６）式に示す目的関数を最小化することで、価値関数を推定する。具体的には、価値関数の更新処理として、図４に示すサブルーチンが実行される。
【０２４３】
図４は、本実施形態に係る潜在コスト推定プログラムのサブルーチンの処理の流れの一例を示すフローチャートである。
【０２４４】
まず、図４のステップ２００では、価値関数推定部３０が、価値関数を初期化する。
【０２４５】
ステップ２０２では、価値関数推定部３０が、終了条件に用いる変数δを初期化する。そして、価値関数推定部３０は、終了条件となる閾値ε、及び最大繰り返し回数を設定する。
【０２４６】
ステップ２０４では、価値関数推定部３０が、価値関数を、上記（１７）式に従って更新する。このとき、更新前と更新後の価値関数の差の絶対値の最大値
【０２４７】
【数９９】
2018197892.tif 000102
【０２４８】
が変数δより大きい場合、変数δを上記最大値に更新する。
【０２４９】
ステップ２０６では、価値関数推定部３０が、価値関数の繰り返し回数をカウントアップする。
【０２５０】
ステップ２０８では、価値関数推定部３０が、終了条件を満たしているか否かを判定する。終了条件を満たしていると判定した場合（肯定判定の場合）、更新した価値関数を価値関数記録部６３に格納し、図３に示すステップ１０４に移行する。一方、終了条件を満たしていないと判定した場合（否定判定の場合）、ステップ２１０に移行し、変数δ←０として、ステップ２０４に戻り処理を繰り返す。なお、ここでいう終了条件としては、上述したように、繰り返し回数が最大繰り返し回数を超えた場合、又は、変数δが閾値εより小さい場合に、終了と判定される。
【０２５１】
次に、図３に戻り、ステップ１０４では、報酬関数計算部４０が、基本遷移関数記録部６２に格納された基本遷移関数及び価値関数記録部６３に格納された価値関数に基づいて、上記（１２）式を用いて、報酬関数を計算し、計算した報酬関数を報酬関数記録部６４に格納する。そして、報酬関数処理部５０は、報酬関数記録部６４に格納された報酬関数を、入出力部７０を介して外部装置８２に出力する。
【０２５２】
なお、上記では、価値関数の更新式に、一例として最急降下法を利用しているが、上記（１６）式を最小化する他のいかなる方法を用いても良い。また、ＧＬＲ項には、グラフ構造を利用して隣接状態が類似した値をとるように設計された正則化項であって、上記（１５）式の形式で表現できるものであれば、任意のものが利用できる。
【０２５３】
本実施形態によれば、十分なデータが存在しない道や場所があったとしても、妥当な値として潜在コストを推定することができる。
これによって、データが少ない場所からの移動の予測の誤差が大きくなることを避けることができ、全体としてより正確に人等の対象物が選択する移動経路を予測することができるようになる。
【０２５４】
以上、実施形態として潜在コスト推定装置を例示して説明した。実施形態は、コンピュータを、潜在コスト推定装置が備える各部として機能させるためのプログラムの形態としてもよい。実施形態は、このプログラムを記憶したコンピュータが読み取り可能な記憶媒体の形態としてもよい。
【０２５５】
その他、上記実施形態で説明した潜在コスト推定装置の構成は、一例であり、主旨を逸脱しない範囲内において状況に応じて変更してもよい。
【０２５６】
また、上記実施形態で説明したプログラムの処理の流れも、一例であり、主旨を逸脱しない範囲内において不要なステップを削除したり、新たなステップを追加したり、処理順序を入れ替えたりしてもよい。
【０２５７】
また、上記実施形態では、プログラムを実行することにより、実施形態に係る処理がコンピュータを利用してソフトウェア構成により実現される場合について説明したが、これに限らない。実施形態は、例えば、ハードウェア構成や、ハードウェア構成とソフトウェア構成との組み合わせによって実現してもよい。
【符号の説明】
【０２５８】
１０   遷移履歴処理部
２０   基本遷移関数処理部
３０   価値関数推定部
４０   報酬関数計算部
５０   報酬関数処理部
６０   記録部
６１   遷移履歴記録部
６２   基本遷移関数記録部
６３   価値関数記録部
６４   報酬関数記録部
７０   入出力部
８０   潜在コスト推定装置
８２   外部装置
【図１】
2018197892.tif 000103
【図２】
2018197892.tif 000104
【図３】
2018197892.tif 000105
【図４】
2018197892.tif 000106