(57)【特許請求の範囲】
【請求項１】
被験者の挙動についてのコスト関数及び価値関数を推定するための逆強化学習の方法であって、コンピュータが、
前記被験者の挙動を定義する状態変数の変化を表すデータを取得し、
方程式（１）によって与えられる修正ベルマン方程式を、取得した前記データに適用し、
0006417629.tif 000069
ここで、ｑ（ｘ）とＶ（ｘ）はそれぞれ状態ｘのコスト関数及び価値関数を示しており、γは割引率を表しており、ｐ（ｙ｜ｘ）とπ（ｙ｜ｘ）はそれぞれ学習前後の状態遷移確率を示している。
方程式（１）における密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定し、
推定された前記密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）に従って最小二乗法を使用して方程式（１）におけるｑ（ｘ）及びＶ（ｘ）を推定し、
推定された前記ｑ（ｘ）及び前記Ｖ（ｘ）を出力する、
ことを特徴とする方法。
【請求項２】
前記密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定するステップは、ｕＬＳＩＦを使用することを含む、
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定するステップは、最小二乗条件付き密度推定（ＬＳＣＤＥ）を使用することを含む、
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定するステップは、ロジスティック回帰を使用することを含む、
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定するステップは、ガウス過程を使用することを含む、
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記コスト関数ｑ（ｘ）及び前記価値関数Ｖ（ｘ）を推定するステップは、正則化付き最小二乗法を使用することを含む、
ことを特徴とする請求項１に記載の方法。
【請求項７】
被験者の挙動についてのコスト関数及び価値関数を推定するための逆強化学習用アルゴリズムをプロセッサに実行させる指示を記憶する非一時的な記憶媒体であって、前記指示は前記プロセッサに、
前記被験者の挙動を定義する状態変数の変化を表すデータを取得し、
方程式（１）によって与えられる修正ベルマン方程式を、取得した前記データに適用し、
0006417629.tif 000070
ここで、ｑ（ｘ）とＶ（ｘ）はそれぞれ状態ｘのコスト関数及び価値関数を示しており、γは割引率を表しており、ｐ（ｙ｜ｘ）とπ（ｙ｜ｘ）はそれぞれ学習前後の状態遷移確率を示している。
方程式（１）における密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定し、
推定された前記密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）に従って最小二乗法を使用して方程式（１）におけるｑ（ｘ）及びＶ（ｘ）を推定し、
推定された前記ｑ（ｘ）及び前記Ｖ（ｘ）を出力する、
ステップを行わせることを特徴とする記憶媒体。
【請求項８】
被験者の挙動についてのコスト関数及び価値関数を推定するための逆強化学習用システムであって、
前記被験者の挙動を定義する状態変数の変化を表すデータを取得するデータ取得手段と、
プロセッサとメモリが、
方程式（１）によって与えられる修正ベルマン方程式を、取得した前記データに適用し、
0006417629.tif 000071
ここで、ｑ（ｘ）とＶ（ｘ）はそれぞれ状態ｘのコスト関数及び価値関数を示しており、γは割引率を表しており、ｐ（ｙ｜ｘ）とπ（ｙ｜ｘ）はそれぞれ学習前後の状態遷移確率を示している。
方程式（１）における密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定し、
推定された前記密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）に従って最小二乗法を使用して方程式（１）におけるｑ（ｘ）及びＶ（ｘ）を推定する、
ように構成されたメモリ付きのプロセッサと、
推定された前記ｑ（ｘ）及び前記Ｖ（ｘ）を出力する出力インタフェースと、
有するシステム。
【請求項９】
インターネットのウェブサーフィンでユーザが選んだ一連の記事から前記ユーザが読みそうな記事の嗜好を予測するためのシステムであって、
前記インターネットに接続されたコンピュータで実施される、請求項８に記載の逆強化学習用システムを含み、
前記被験者は前記ユーザであり、前記被験者の挙動を定義する前記状態変数は各ウェブページを閲覧している間に前記ユーザによって選ばれた記事のトピックスを含み、
前記プロセッサは、前記ユーザがインターネットウェブサイトを閲覧しているインタフェースに、推定された前記コスト関数及び前記価値関数に従って前記ユーザが読むための推奨記事を表示させる、
システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、密度比推定による逆強化学習、特に、逆強化学習のシステム及び方法に関する。この出願は、参考として、２０１４年８月７日に出願された米国特許仮出願番号第６２／０３４，５１０号の全体をここに組み込んでいる。
【背景技術】
【０００２】
観察から人間の挙動を理解することは、人間と相互作用できる人工システムを発展させるために、とても重要である。我々の意思決定の過程は、選択されたアクションと関連付けられた報酬や費用に影響を受けるので、観察した挙動から報酬／費用の推定として問題を定式化することができる。
【０００３】
逆強化学習の発想は、元はNg and Russel（２０００）（非特許文献１４）によって提案されている。Dvijotham and Todorov（２０１０）（非特許文献６）によって提案されたＯｐｔＶアルゴリズムは事前作業であり、デモンストレータの方策が、線形ベルマン方程式の解である価値関数によって近似されることを示している。
【０００４】
一般的に言えば、強化学習（ＲＬ）は、環境と相互作用することによって最適な方策を学習できる生体システム及び人工システム双方の意思決定過程を調査するための計算の枠組みである。ＲＬには解決されていないいくつもの疑問が存在しており、１つの重大な問題は適切な報酬関数／コスト関数を設計し用意する方法である。タスクが成し遂げられるときには正の報酬を与え、そうでなければゼロを与える、疎な報酬関数を設計することは易しいが、それが最適な方策の発見を困難にしている。
【０００５】
いくつかの状況では、所望の挙動の例を用意することは適切な報酬関数／コスト関数を手作りすることより易しい。近年、デモンストレータのパフォーマンスから報酬関数／コスト関数を導き出すために、かつ、模倣学習を実施するために、逆強化学習（ＩＲＬ）（Ng and Russel、２０００、非特許文献１４）と徒弟学習（Abbeel & Ng、２００４、非特許文献１）のいくつもの方法が提案されてきた。しかしながら、現行の研究（Abbeel & Ng、２００４、非特許文献１；Ratliffら、２００９、非特許文献１６；Ziebartら、２００８、非特許文献２６）のほとんどは推定された報酬関数／コスト関数と共に順強化学習の問題を解くためのルーティンを要求する。この処理はたとえ環境のモデルが利用可能であるときでも、通常、とても時間を食う。
【０００６】
最近では、線形可解マルコフ決定過程（ＬＭＤＰ）のコンセプトが紹介されている（Todorov，２００７；２００９，ＮＰＬｓ２３−２４）。ＬＭＤＰはコスト関数の形式を制限することによるマルコフ決定過程の下位分類である。この制限はＩＲＬにおいて重要な役割を果たす。ＬＭＤＰはＫＬ制御や経路積分型アプローチ（Kappenら，２０１２，非特許文献１０；Theodorouら，２０１０，非特許文献２１）としても知られており、類似の考えが制御理論の分野で提案されている（Fleming and Soner，２００６，非特許文献７）。経路積分法に基づくモデルフリーなＩＲＬアルゴリズムはAghasadeghi＆Bretl（２０１１）（非特許文献２）；Kalakrishnanら（２０１３）（非特許文献８）によって提案されている。最適な軌跡の尤度はコスト関数によってパラメータ化されるので、コストのパラメータを最大化尤度によって最適化することができる。しかしながら、これらの方法は軌跡全体のデータを要求する。モデルベースのＩＲＬ法はＬＭＤＰの枠組みに基づくDvijotham and Todorov（２０１０）（非特許文献６）によって提案されている。この中で、最適な状態遷移の尤度が価値関数により表わされている。ＩＲＬの経路積分型アプローチとは対照的に、状態遷移のあらゆるデータセットから最適化することができる。大きな欠点は、解析的に解決できない積分を評価することである。実際、これらは積分を総和と交換するために状態空間を離散化したが、高次元の連続問題で実現不可能である。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Abbeel, P. and Ng, A.Y., "Apprenticeship learning via inverse reinforcement learning", The 21st International Conference on Machine Learning, 2004.
【非特許文献２】Aghasadeghi, N. and Bretl, T., "Maximum entropy inverse reinforcement learning in continuous state spaces with path integrals", IEEE/RSJ International Conference on Intelligent Robots and Systems, pp.1561-1566, 2011.
【非特許文献３】Boularias, A., Kober, J. and Peters, J.,  "Relative entropy inverse reinforcement learning",  The 14th International Conference on Artificial Intelligence and Statistics, volume 15, 2011.
【非特許文献４】Deisenroth, M.P., Rasmussen, C.E and Peters, J., "Gaussian process dynamic programming", Neurocomputing, 72(7-9):1508-1524, 2009.
【非特許文献５】Doya, K. "Reinforcement learning in continuous time and space", Neural Computation, 12:219-245, 2000.
【非特許文献６】Dvijotham, K. and Todorov, E., "Inverse optimal control with linearly solvable MDPs",  The 27th International Conference on Machine Learning, 2010.
【非特許文献７】Fleming, W.H. and Soner, H.M., "Controlled Markov Processes and Viscosity Solutions",  Springer, second edition, 2006.
【非特許文献８】Kalakrishnan, M., Pastor, P., Righetti, L. and Schaal, S., "Learning objective functions for manipulation", IEEE International Conference on Robotics and Automation, pp.1331-1336, 2013.
【非特許文献９】Kanamori, T., Hido, S. and Sugiyama, M., "A Least-squares Approach to Direct Importance Estimation", Journal of Machine Learning Research, 10:1391-1445, 2009.
【非特許文献１０】Kappen, H.J., Gomez, V. and Opper, M., "Optimal control as a graphical model inference problem", Machine Learning, 87(2):159-182, 2012.
【非特許文献１１】Kinjo, K., Uchibe, E. and Doya, K., "Evaluation of linearly solvable Markov decision process with dynamic model learning in a mobile robot navigation task", Frontiers in Neurorobotics, 7(7), 2013.
【非特許文献１２】Levine, S. and Koltun, V., "Continuous inverse optimal control with locally optimal examples", The 27th International Conference on Machine Learning, 2012.
【非特許文献１３】Levine, S., Popovi?, Z. and Koltun, V., "Nonlinear inverse reinforcement learning with Gaussian processes", Advances in Neural Information Processing Systems 24, pp.19-27. 2011.
【非特許文献１４】Ng, A.Y. and Russell, S., "Algorithms for inverse reinforcement learning", The 17th International Conference on Machine Learning, 2000.
【非特許文献１５】Rasmussen, C.E. and Williams, C.K.I., "Gaussian Processes for Machine Learning", MIT Press, 2006.
【非特許文献１６】Ratliff, N.D., Silver, D and Bagnell, J.A., "Learning to search: Functional gradient techniques for imitation learning", Autonomous Robots, 27(1):25-53, 2009.
【非特許文献１７】Stulp, F. and Sigaud, O., "Path integral policy improvement with covariance matrix adaptation", The 10th European Workshop on Reinforcement Learning, 2012.
【非特許文献１８】Sugimoto, N. and Morimoto, J., "Phase-dependent trajectory optimization for periodic movement using path integral reinforcement learning", The 21st Annual Conference of the Japanese Neural Network Society, 2011.
【非特許文献１９】Sugiyama, M., Takeuchi, I., Suzuki, T., Kanamori, T., Hachiya, H. and Okanohara, D., "Least-squares conditional density estimation", IEICE Transactions on Information and Systems, E93-D(3):583-594, 2010.
【非特許文献２０】Sugiyama, M., Suzuki, T. and Kanamori, T., "Density ratio estimation in machine learning", Cambridge University Press, 2012.
【非特許文献２１】Theodorou, E., Buchli, J. and Schaal, S., "A generalized path integral control approach to reinforcement learning", Journal of Machine Learning Research, 11:3137-3181, 2010.
【非特許文献２２】Theodorou, E.A and Todorov, E., "Relative entropy and free energy dualities: Connections to path integral and KL control", The 51st IEEE Conference on Decision and Control, pp.1466-1473, 2012.
【非特許文献２３】Todorov, E., "Linearly-solvable Markov decision problems", Advances in Neural Information Processing Systems 19, pp.1369-1376. MIT Press, 2007.
【非特許文献２４】Todorov, E., "Efficient computation of optimal actions", Proceedings of the National Academy of Sciences of the United States of America, 106(28): 11478-83, 2009.
【非特許文献２５】Todorov, E., "Eigenfunction approximation methods for linearly-solvable optimal control problems", The 2nd IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, pp.161-168, 2009.
【非特許文献２６】Ziebart, B.D., Maas, A., Bagnell, J.A. and Dey, A.K., "Maximum entropy inverse reinforcement learning", The 23rd AAAI Conference on Artificial Intelligence, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
逆強化学習は上記課題を解決するための枠組みであるが、上述したように、現行の方法は以下の欠点がある（１）状態が連続するときの解決困難、（２）計算コストが高い、（３）推定のために状態の軌跡全体を必要とすべき。この開示に開示される方法はこれらの欠点を解決する。特に、非特許文献１４で提案された以前の方法は、報告された以前の多くの研究のようにはうまくはいかない。さらに、これらのアルゴリズムは積分の複雑な評価を含むので、実際、非特許文献６で提案された方法は連続問題を解決できない。
【０００９】
本発明は、逆強化学習のためのシステム及び方法を対象とする。
【００１０】
本発明の目的は、従来技術の１以上の課題を除去するように新規で改良された逆強化学習のシステム及び方法を提供することである。
【課題を解決するための手段】
【００１１】
本発明の目的に従って、且つ、これらの利点及びその他の利点を達成するために、具現化しかつ広く記載されているように、１つの態様では、本発明は、被験者の挙動についてのコスト関数及び価値関数を推定するための逆強化学習の方法であって、コンピュータが、前記被験者の挙動を定義する状態変数の変化を表すデータを取得し、方程式（１）によって与えられる修正ベルマン方程式を、取得した前記データに適用し、
0006417629.tif 000002
ここで、ｑ（ｘ）とＶ（ｘ）はそれぞれ状態ｘのコスト関数及び価値関数を示しており、γは割引率を表しており、ｐ（ｙ｜ｘ）とπ（ｙ｜ｘ）はそれぞれ学習前後の状態遷移確率を示している。方程式（１）における密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定し、推定された前記密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）に従って最小二乗法を使用して方程式（１）におけるｑ（ｘ）及びＶ（ｘ）を推定し、推定された前記ｑ（ｘ）及び前記Ｖ（ｘ）を出力する、ことを特徴とする方法を提供する。
【００１２】
別の点では、本発明は、被験者の挙動についてのコスト関数及び価値関数を推定するための逆強化学習用アルゴリズムをプロセッサに実行させる指示を記憶する、ＣＤ−ＲＯＭや他の形式の非一時的な記憶媒体といった、非一時的な記憶媒体であって、前記指示は前記プロセッサに、前記被験者の挙動を定義する状態変数の変化を表すデータを取得し、方程式（１）によって与えられる修正ベルマン方程式を、取得した前記データに適用し、
0006417629.tif 000003
ここで、ｑ（ｘ）とＶ（ｘ）はそれぞれ状態ｘのコスト関数及び価値関数を示しており、γは割引率を表しており、ｐ（ｙ｜ｘ）とπ（ｙ｜ｘ）はそれぞれ学習前後の状態遷移確率を示している。方程式（１）における密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定し、推定された前記密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）に従って最小二乗法を使用して方程式（１）におけるｑ（ｘ）及びＶ（ｘ）を推定し、推定された前記ｑ（ｘ）及び前記Ｖ（ｘ）を出力する、ステップを行わせることを特徴とする記憶媒体を提供する。
別の点では、本発明は、被験者の挙動についてのコスト関数及び価値関数を推定するための逆強化学習用システムであって、前記被験者の挙動を定義する状態変数の変化を表すデータを取得するデータ取得手段と、プロセッサとメモリが、方程式（１）によって与えられる修正ベルマン方程式を、取得した前記データに適用し、
0006417629.tif 000004
ここで、ｑ（ｘ）とＶ（ｘ）はそれぞれ状態ｘのコスト関数及び価値関数を示しており、γは割引率を表しており、ｐ（ｙ｜ｘ）とπ（ｙ｜ｘ）はそれぞれ学習前後の状態遷移確率を示している。方程式（１）における密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定し、推定された前記密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）に従って最小二乗法を使用して方程式（１）におけるｑ（ｘ）及びＶ（ｘ）を推定する、ように構成されたメモリ付きのプロセッサと、推定された前記ｑ（ｘ）及び前記Ｖ（ｘ）を出力する出力インタフェースと、有するシステムを提供する。
別の点では、本発明は、インターネットのウェブサーフィンでユーザが選んだ一連の記事から前記ユーザが読みそうな記事の嗜好を予測するためのシステムであって、前記インターネットに接続されたコンピュータで実施される、上述した逆強化学習用システムを含み、前記被験者は前記ユーザであり、前記被験者の挙動を定義する前記状態変数は各ウェブページを閲覧している間に前記ユーザによって選ばれた記事のトピックスを含み、前記プロセッサは、前記ユーザがインターネットウェブサイトを閲覧しているインタフェースに、推定された前記コスト関数及び前記価値関数に従って前記ユーザが読むための推奨記事を表示させる、システムを提供する。
【発明の効果】
【００１３】
本発明の１以上の態様によれば、逆強化学習を効果的かつ効率良く行うことが可能になる。いくつかの実施形態では、環境ダイナミクスを事前に知る必要がなく、積分を実行する必要がない。
【００１４】
本発明の追加の又は個々の特徴と利点は、以下の記載において説明され、一部はその記載から明らかであり、あるいは、本発明の実施により習得することができる。本発明の目的と他の利点は添付図面だけでなくその明細書及び特許請求の範囲において特に指摘される構成によって実現され、達成されることになる。
【００１５】
上述の一般的な説明及び後述の詳細な説明は、いずれも具体例であって例示を目的としており、特許請求されている本発明の範囲の詳しい説明を提供することが意図されていることを理解すべきである。
【図面の簡単な説明】
【００１６】
【図１】図１は、本発明の実施形態が以下の密度比推定法（１）ＬＳＣＤＥ−ＩＲＬ、（２）ｕＬＳＩＦ−ＩＲＬ、（３）ＬｏｇＲｅｇ−ＩＲＬ、（４）Ｇａｕｓｓ−ＩＲＬ、（５）ＬＳＣＤＥ−ＯｐｔＶ、及び（６）Ｇａｕｓｓ−ＯｐｔＶの各々に適用された、倒立振り子の振り上げ実験の結果に対する正規化二乗誤差を示している。
【図２】図２は、倒立振り子の振り上げ実験の交差検証誤差をさまざまな密度比推定法に対して示したグラフである。
【図３】図３は、ロングポールに対するポールバランシングタスクの実験手順を示しており、左がスタート位置、中央がゴール位置、右が状態変数を示している。
【図４】図４は、本発明の実施形態に係る、さまざまな対象者に関するポールバランシングタスク実験の学習曲線を示しており、実線がロングポールを示し、破線がショートポールを示している。
【図５】図５は、規定部分空間に投影された、対象者番号４、５及び７に対する本発明の実施形態に係るポールバランシングタスク実験に対して導き出された推定コスト関数を示している。
【図６】図６は、推定コスト関数を評価する、対象者番号４及び７のポールバランシングタスク実験のテストデータセットに対する負の対数尤度値を示している。
【図７】図７は、デモンストレータによって生成された観察した状態遷移から目的関数を推測できる、本発明の実施形態に係る逆強化学習の枠組みを概略的に示している。
【図８】図８は、ロボットの挙動を模倣学習する際の本発明の逆強化学習の実施例を示す概略的なブロック図である。
【図９】図９は、人間の挙動を解釈する際の本発明の逆強化学習の実施例を示す概略的なブロック図である。
【図１０】図１０は、ウェブビジターによる、ウェブサーフィンの際のトピックスにおけるビジターの嗜好を示す一連のクリックアクションを概略的に示している。
【図１１】図１１は、本発明の実施形態に係る逆強化学習システムの一例を概略的に示している。
【発明を実施するための形態】
【００１７】
本開示は、線形可解マルコフ決定過程（ＬＭＤＰ）の枠組みの下における密度比推定に基づく新規な逆強化学習方法及びシステムを提供する。ＬＭＤＰでは、制御された状態遷移密度と制御されていない状態遷移密度の対数比が状態依存のコスト関数と価値関数によって表される。本発明の１つの態様では、密度比推定方法は遷移密度比を推定するために使用され、正則化付き最小二乗法はその関係を満足する状態依存のコスト関数と価値関数を推定するために使用される。この方法は分配関数を評価するといった積分の計算を回避することができる。後述するように、振り子の振り上げの簡易な数値シミュレーションが行われ、慣用的な方法を超えるその優位性が実証された。本発明者らはさらにその方法をポールバランシングタスク実行時の人間の挙動に適用し、満足のいくやり方で推定されたコスト関数が新たな試行や環境において被験者のパフォーマンスを予測できることを示す。
【００１８】
本発明の１つの態様はＯｐｔＶアルゴリズムのような線形可解マルコフ決定過程の枠組みに基づいている。本発明者らは以下によって与えられる新規なベルマン方程式を導き出した。
0006417629.tif 000005
ここで、ｑ（ｘ）とＶ（ｘ）は状態ｘのコスト関数及び価値関数を示しており、γは割引率を表している。ｐ（ｙ｜ｘ）とπ（ｙ｜ｘ）はそれぞれ学習前の状態遷移確率と学習後の状態遷移確率を示している。上記方程式の左手側、密度比は密度比推定法により、観察された挙動から効率良く計算されている。いったん密度比が推定されると、コスト関数及び価値関数は正則化最小二乗法によって推定することができる。重要な特徴は、我々の方法が、たいてい高い計算コストで算出される積分の計算を回避できるということである。本発明者らはこの方法をポールバランシングタスク実行時の人間の挙動に適用し、制御システム、機械学習、オペレーションズリサーチ、情報理論などにおいてよく認識された広い利用可能性を有する逆強化学習でこの新たな計算技術の万能な利用可能性及び有効性を確かめながら、推定されたコスト関数が新たな試行や環境で被験者のパフォーマンスを予測できることを示している。
【００１９】
＜１．線形可解マルコフ決定過程＞
＜１．１．順強化学習＞
本開示はマルコフ決定過程と離散時間連続空間のためのその単純化について簡単に紹介する。連続的な状態と連続的な行動空間をそれぞれＸとＵとする。ある時間ステップｔで、学習エージェントは環境の現在の状態
0006417629.tif 000006
を観察し、確率的方策からサンプリングされた行動
0006417629.tif 000007
を実行する。その結果として、中間コストｃ（ｘｔ，ｕｔ）がその環境から与えられ、行動ｕｔの下でｘｔから
0006417629.tif 000008
までの状態遷移確率ＰＴ（ｙ｜ｘｔ，ｕｔ）に従って環境が状態遷移を作成する。強化学習のゴールは所定の目的関数を最小化する最適な方策π（ｕ｜ｘ）を構築することである。いくつもの目的関数が存在するが、最も広く使用されるものは
0006417629.tif 000009
によって与えられた割り引かれたコストの和である。ここで、
0006417629.tif 000010
は、割引率と呼ばれる。最適価値関数は以下のベルマン方程式を満たすことが知られている。
0006417629.tif 000011
方程式（２）はｍｉｎの作用素に起因する非線形な方程式である。
【００２０】
線形可解マルコフ決定過程（ＬＭＤＰ）はいくつかの仮定の下で方程式（２）を簡略化する（Todorov，２００７；２００９ａ，非特許文献２３−２４）。ＬＭＤＰのキートリックは、方策を最適化する代わりに状態遷移確率を直接最適化することである。より具体的に、２つの条件付き確率密度関数を紹介する。一方は、ｐ（ｙ｜ｘ）によって示され、固有の状態遷移として扱うことができるuncontrolled probabilityである。ｐ（ｙ｜ｘ）は任意であり、
0006417629.tif 000012
によって構築することができる。ここで、π０（ｕ｜ｘ）はランダムな方策である。他方は、π（ｙ｜ｘ）によって示され、最適な状態遷移として解釈することができるcontrolled probabilityである。その際、コスト関数は以下の形式に制限される。
0006417629.tif 000013
ここで、ｑ（ｘ）とＫＬ（ｐ（・｜ｘ）｜｜ｐ（・｜ｘ））はそれぞれ状態依存コスト関数と制御された状態遷移密度と制御されてない状態遷移密度の間のカルバック・ライブラー情報量を示している。この場合、ベルマン方程式（２）は以下の方程式に簡略化される。
0006417629.tif 000014
最適なcontrolled probabilityは
0006417629.tif 000015
によって与えられる。注目すべきは、たとえ希望関数Ｚ（ｘ）＝ｅｘｐ（−Ｖ（ｘ））が導入されても、割引率γが存在するので、方程式（４）が依然として非線形であるということである。ＬＭＤＰの枠組みの下での順強化学習では、Ｖ（ｘ）は方程式（４）を解くことによって計算され、その際にπ（ｙ｜ｘ）が計算される（Todorov，２００９，非特許文献２５）。
【００２１】
＜１．２．逆強化学習＞
ＬＭＤＰ下における逆強化学習（ＩＲＬ）アルゴリズムはDvijotham and Todorov（２０１０）（非特許文献６）により提案された。特に、ＯｐｔＶは離散状態問題に極めて効率的である。ＯｐｔＶの利点は、価値関数の推定に最尤法が適用できるように、最適な状態遷移が価値関数によって明確に表されることである。観察された軌道が最適な状態遷移密度（５）によって生成されると仮定する。価値関数は以下の線形モデルによって近似される。
0006417629.tif 000016
ここで、ｗＶとψＶ（ｘ）はそれぞれ学習の重みと基底関数ベクトルを示している。
【００２２】
controlled probabilityは方程式（５）によって与えられるので、重みベクトルｗＶは尤度を最大化することによって最適化することができる。状態遷移のデータセット
0006417629.tif 000017
を持つと仮定する。ここで、Ｎπはcontrolled probabilityからのデータ数を示している。その際、対数尤度とその微分係数は
0006417629.tif 000018
0006417629.tif 000019
によって与えられる。ここで、π（ｙ｜ｘ；ｗＶ）は価値関数が方程式（６）によってパラメータ化される制御された方策である。いったん勾配が評価されると、重みベクトルｗＶは勾配上昇法に従って更新される。
【００２３】
価値関数が推定された後、コスト関数を抽出するために簡略化されたベルマン方程式（４）を使用することができる。
0006417629.tif 000020
とγが与えられ、コスト関数ｑ（ｘ）が価値関数で使用される基底関数によって表現されると、ｑ（ｘ）が一意的に決定されることを意味している。コスト関数の表明が模倣学習の場合に重要でない一方、分析のためには我々はもっと単純なコストの表現を発見したい。それゆえ、本発明者らは近似器を導入する。
0006417629.tif 000021
ここで、ｗｑとψＶ（ｘ）はそれぞれ学習の重みと基底関数ベクトルを示している。ｗｑを最適化するためのＬ１型正則化付き目的関数は
0006417629.tif 000022
0006417629.tif 000023
によって与えられる。ここで、λｑは正則化定数である。単純な勾配降下アルゴリズムが採用され、Ｊ（ｗｑ）が観察された状態で評価される。
【００２４】
Dvijotham and Todorov（２０１０）（非特許文献６）の最も重大な問題は、解析的に解決できない、方程式（８）及び（１０）の積分であり、彼らは状態空間を離散化し、積分を総和で置換した。しかしながら、彼らが示唆したように、高次元の問題では実行不可能である。また、uncontrolled probability ｐ（ｙ｜ｘ）は必ずしもガウシアンではない。本発明の少なくともいくつかの実施形態では、対数尤度の勾配を評価するためにメトロポリスハスティングアルゴリズムが適用され、そこではuncontrolled probability ｐ（ｙ｜ｘ）が因果密度として使用されている。
【００２５】
＜２．密度比推定による逆強化学習＞
＜２．１．ＩＲＬのためのベルマン方程式＞
方程式（４）及び（５）から、本発明者らは割引コスト問題に対し以下の重要な関係を導き出した。
0006417629.tif 000024
方程式（１１）は本発明の実施形態に係るＩＲＬアルゴリズムで重要な役割を果たす。最初の出口問題、平均コスト問題、及び有限範囲問題に対する類似の方程式を導き出すことができる。注意すべきは、ｑ（ｘ）が方程式（３）で示されるコスト関数の状態依存部分であるため、方程式（１１）の左手側がＴＤ誤差（Temporal Difference error）でないということである。
コスト関数の形式がＬＭＤＰ下で方程式（３）によって束縛されるが、我々のＩＲＬは依然として不良設定問題であり、コスト関数は一意に決定されない。より具体的には、状態依存コスト関数が
0006417629.tif 000025
によって修正される場合、対応する価値関数が
0006417629.tif 000026
に変更される。ここで、Ｃは定数値である。その際、Ｖ（ｘ）から導き出されたcontrolled probabilityはＶ´（ｘ）から導き出されたものと全く同じである。この特性は後述するようにコスト関数を推定する際に役に立つ。本発明の１つの態様では、開示されたＩＲＬ法は２つの部分からなる。一方は後述する方程式（１１）の右手側の密度比を推定することである。他方は以下に示すように、正則化付き最小二乗法によってｑ（ｘ）とＶ（ｘ）を推定することである。
【００２６】
制御された遷移確率密度と制御されていない遷移確率密度の比を推定することは密度比推定の問題として扱われる（Sugiyamaら，２０１２，非特許文献２０）。問題の設定に従い、本開示は以下の公式化を考える。
【００２７】
＜２．２．１．一般的な場合＞
まず、一般的な場合を考える。状態遷移の２つのデータセットを持つと仮定する。一方は方程式（７）で示されるＤπであり、他方はuncontrolled probabilityからのデータセット
0006417629.tif 000027
である。ここで、Ｎｐはデータ数を示している。その際、ＤｐとＤπから比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）を推定することに我々は関心がある。
【００２８】
方程式（１１）から、我々は以下の２つの分析を考えることができる。
0006417629.tif 000028
0006417629.tif 000029
はじめの分解（１４）は条件付き確率密度の対数の差を示している。方程式（１４）を推定するために、本開示は２つの実施を考える。はじめはπ（ｙ｜ｘ）及びｐ（ｙ｜ｘ）を推定するために最小二乗条件付き密度推定（ＬＳＣＤＥ）（Sugiyamaら，２０１０）を採用するＬＳＣＤＥ−ＩＲＬである。他方は方程式（１４）の状態密度を推定するためにガウシアン過程（Rasmussen and Williams，２００６，非特許文献１５）を使用するＧａｕｓｓ−ＩＲＬである。
【００２９】
第２の分解（１５）は密度比の対数の差を示している。第２の分析の利点はπ（ｘ）＝ｐ（ｘ）なら、ｌｎ π（ｘ）／ｐ（ｘ）を無視できるということである。設定によりこの条件を満たしてもよい。今回、π（ｘ）／ｐ（ｘ）及びπ（ｘ，ｙ）／ｐ（ｘ，ｙ）を推定するために、２つの方法が実施される。一方は拘束なし最小二乗重要度適合法（ｕＬＳＩＦ）（Kanamoriら，２００９，非特許文献９）を使用するｕＬＳＩＦ−ＩＲＬである。他方は、異なるやり方でロジスティック回帰を利用する、ＬｏｇＲｅｇである。以下の２．３章はこれらの実施について述べる。
【００３０】
＜２．２．２  ｐ（ｙ｜ｘ）が未知のとき＞
状態遷移確率Ｐｔ（ｙ｜ｘ，ｕ）は標準的なＩＲＬ問題の場合では事前に知られていると想定され、これはuncontrolled probability ｐ（ｙ｜ｘ）がＬＭＤＰの場合に与えられるという想定に対応する。これはモデルベースのＩＲＬとして取り扱うことできる。この場合、方程式（１４）がふさわしく、データセットＤｐからcontrolled probability π（ｙ｜ｘ）を推定するのに十分である。
【００３１】
状況によっては、我々は制御されていな確率密度から分析モデルもデータセットももっていない。その際、ｐ（ｙ｜ｘ）は、未束縛変数のための不正分布である一様分布に置き換わる。コスト関数と価値関数を方程式（１２）及び（１３）により移行することによって補うことができるので、一般性を失うことなく、ｐ（ｙ｜ｘ）は１に設定される。
【００３２】
＜２．３．密度比推定アルゴリズム＞
この章はこの開示で開示されるＩＲＬ法にふさわしい密度比推定アルゴリズムについて述べる。
＜２．３．１．ｕＬＳＩＦ＞
ｕＬＳＩＦ（Kanamoriら，２００９，非特許文献９）は密度比直接推定法のための最小二乗法である。ｕＬＳＩＦのゴールは２つの密度比π（ｘ）／ｐ（ｘ）及びπ（ｘ，ｙ）／ｐ（ｘ，ｙ）を推定することである。以後、本開示は簡略化のためにｚ＝（ｘ，ｙ）の場合においてＤｐとＤπからｒ（ｚ）＝π（ｚ）／ｐ（ｚ）を推定するやり方について説明する。線形モデルによって比率を近似させる。
ここで、それぞれφ（ｚ）は基底関数ベクトルを示しており、αは学習されるパラメータである。目的関数は
によって与えられる。ここで、λは正則化定数であり、
である。注意すべきは、ｈはＤπから推定される一方で、ＨはＤｐから推定されるということである。方程式（１６）は解析的に
として最小化することができるが、この最小化は密度比の非負の拘束を無視する。この問題を補償するために、ｕＬＳＩＦは
によって解を修正する。ここで、上記ｍａｘの作用素は要素ごとの方式に適用される。Kanamoriら（２００９）（非特許文献９）によって推奨されるように、Ｄπの状態を中心とするガウシアン関数は
によって記述される基底関数として使用される。ここで、σは幅パラメータである。
はＤπから無作為に選択される状態である。パラメータλ及びσは一個抜き交差検証によって選択される。
【００３３】
＜２．３．２．ＬＳＣＤＥ＞
ＬＳＣＤＥ（Sugiyamaら，２０１０，非特許文献１９）は条件付き確率密度関数を推定するｕＬＳＩＦの特別な場合と扱われる。例えば、Ｄπからからπ（ｙ｜ｘ）＝π（ｘ，ｙ）／π（ｘ）を推定するための目的関数は
0006417629.tif 000030
0006417629.tif 000031
によって与えられる。ここで
0006417629.tif 000032
は線形モデルであり、λは正則化定数である。ＬＳＣＤＥでＨとｈを計算することはｕＬＳＩＦでこれらを計算することとわずかに異なり、以下のように計算される。
0006417629.tif 000033
0006417629.tif 000034
ここで、
0006417629.tif 000035
は以下のように定義される。
0006417629.tif 000036
方程式（１８）で示す基底関数が使用されるので、この積分は解析的に計算することができる。ＬＳＣＤＥの推定重みは方程式（１７）によって与えられる。推定比が条件付き密度であると想定するために、解がコスト関数と価値関数を推定するために使用されるときには、解は正規化されるべきである。
【００３４】
＜２．３．３．ＬｏｇＲｅｇ＞
ＬｏｇＲｅｇはロジスティック回帰を使用する密度推定の方法である。uncontrolled probabilityからのサンプルにセレクタ変数η＝−１を割り当て、controlled probabilityからのサンプルにセレクタ変数η＝１を割り当てよう。
密度比は、以下のようにベイズのルールを利用することによって表すことができる。
１番目の比率Ｐｒ（η＝−１）／Ｐｒ（η＝１）はＮｐ／Ｎπによって推定され、２番目の比率はロジスティック回帰分類器
によって条件付き確率Ｐ（η｜ｚ）を推定した後に計算される。ここで、ηはラベルとして扱われる。注意すべきことは、密度比の対数がＬｏｇＲｅｇ
の場合に線形モデルによって与えられるということである。第２項ｌｎ Ｎｐ／Ｎπは方程式（１５）に示す我々のＩＲＬの定式化で無視することができる。目的関数は
によって表される負の正則化対数尤度から導き出される。閉形式解は導き出されないが、この目的関数が凸関数であるので標準的な非線形最適化法によって効率良く最小化することができる。
【００３５】
＜２．４．コスト関数及び価値関数の推定＞
いったん密度比π（ｙ｜ｘ）／ｐ（ｙ｜ｘ）が推定されると、正則化付き最小二乗法は状態依存のコスト関数ｑ（ｘ）及び価値関数Ｖ（ｘ）を推定するために利用される。
0006417629.tif 000037
が負の対数比
0006417629.tif 000038
の近似であると仮定し、方程式（６）及び（９）でそれぞれ定義されるように、ｑ（ｘ）及びＶ（ｘ）の線形近似を考慮する。目的関数は
0006417629.tif 000039
0006417629.tif 000040
によって与えられる。ここで、λｑ及びλＶは正則化定数である。Ｌ２型正則化は数値安定性を達成する効果的な手段であるため、Ｌ２型正則化はｗＶのために使用される。他方、Ｌ１型正則化は実験者によってより容易に解釈される疎性モデルをｗｑが生み出すために使用される。スパース性が重要でない場合、ｗｑに対してＬ２型正則化を使用することは可能である。また、ｗｑとｗＶの非負の拘束は導入されない。なぜなら、方程式（１２）は非負のコスト関数を効率良く満足させるための設定
0006417629.tif 000041
により使用することができるからである。
理論上、我々は任意の基底関数を選ぶことができる。本発明の一つの実施形態では、方程式（１８）に示すガウシアン関数が簡略化ために使用される。
0006417629.tif 000042
ここで、σは幅パラメータである。中央の位置
0006417629.tif 000043
はＤＰから無作為に選択される。
【００３６】
＜３．実験＞
＜３．１．倒立振子の振り上げ＞
＜３．１．１．タスク記述＞
本発明の上述した実施形態の有効性を実演して確認するために、本発明者らは状態ベクトルが２次元ベクトルｘ＝［ｑ，ｗ］Ｔによって与えられる倒立振子振り上げ問題を研究した。ここで、ｑとｗはそれぞれポールの角度と角速度を示している。運動方程式は以下の確率差分方程式
によって与えられる。ここで、ｌ、ｍ、ｇ、κ、σｅ、及びωは、それぞれ、ポールの長さ、質量、重力加速度、摩擦係数、ノイズ用スケーリングパラメータ、及びブラウニアンノイズを示している。以前の研究（Deisenrothら、２００９、非特許文献４；Doya、２０００、非特許文献５）とは対照的に、利用されたトルクは制限されておらず、直接振り上げることが可能である。時間軸をステップｈで離散化することによって、ガウス分布によって表される、対応する状態遷移確率ＰＴ（ｙ｜ｘ，ｕ）が得られる。このシミュレーションでは、パラメータが以下のように与えられる。ｌ＝１［ｍ］、ｍ＝１［ｋｇ］、ｇ＝９．８［ｍ／ｓ２］、κ＝０．０５［ｋｇｍ２／ｓ］、ｈ＝０．０１［ｓ］、σｅ＝４、及び
本発明者らは、以下のように（１）状態依存のコスト関数ｑ（ｘ）、（２）uncontrolled probability ｐ（ｙ｜ｘ）、及び（３）データセットＤｐ及びＤπを変更することによって、一連の実験を行った。
【００３７】
＜コスト関数＞
到達点はポールを直立状態に維持することであり、以下の３つのコスト関数
0006417629.tif 000044
0006417629.tif 000045
が用意される。ここで、Ｑ＝ｄｉａｇ[１，０．２]。ｑｅｘｐ（ｘ）はDeisenrothら（２００９）（非特許文献４）によって使用される一方で、ｑｃｏｓｔ（ｘ）はDoya（２０００）によって使用される。
【００３８】
＜Uncontrolled Probability＞
２つの密度ｐＧ（ｙ｜ｘ）とｐｍ（ｙ｜ｘ）を考える。ｐＧ（ｙ｜ｘ）はガウス分布によって表される確率的方策π（ｕ｜ｘ）を使用することにより構築される。離散時間の運動方程式はガウス分布によって与えられるので、ｐＧ（ｙ｜ｘ）もまたガウス分布である。ｐｍ（ｙ｜ｘ）の場合では、混合ガウス分布が確率的方策として使用される。
【００３９】
＜データセットの用意＞
２つのサンプリング方法を考える。一方は一様のサンプリングであり、他方は軌道に基づいたサンプリングである。一様のサンプリング方法では、ｘが状態空間全体で定義される一様分布からサンプリングされる。言い換えれば、ｐ（ｘ）及びπ（ｘ）は一様分布として扱われる。その際、ｙはＤｐ及びＤπを構築するためにuncontrolled probabilityとcontrolled probabilityからそれぞれサンプリングされる。軌道に基づいたサンプリング方法では、ｐ（ｙ｜ｘ）及びπ（ｙ｜ｘ）は同じ開始状態ｘから状態の軌道を生成するために使用される。その際、Ｄｐ及びＤπを構築するために一対の状態遷移が軌道から無作為に選択される。ｐ（ｘ）はπ（ｘ）と異なると期待される。
【００４０】
各コスト関数に対し、方程式（４）を解くことによって対応する価値関数が算出され、方程式（５）によって対応する最適なcontrolled probabilityが評価される。以前の方法（Todorov、２００９ｂ、非特許文献２５）では、ｅｘｐ（−Ｖ（ｘ））が線形モデルによって表されるが、目的関数（１）の下では困難である。なぜならば、割引率γが線形モデルを複雑にするからである。それゆえ、価値関数は方程式（６）に示す線形モデルにより近似され、積分を評価するためにメトロポリス・ヘイスティングアルゴリズムが使用される。
【００４１】
本発明の実施形態に係る方法をＯｐｔＶと比較することができる。なぜなら、ＯｐｔＶの前提は本発明の実施形態に係る我々の前提と同じだからである。密度比推定方法の選択によれば、上述したようにいくつもの変形が存在する。より具体的には、以下の６つのアルゴリズムを考える。（１）ＬＳＣＤＥ−ＩＲＬ、（２）ｕＬＳＩＦ−ＩＲＬ、（３）ＬｏｇＲｅｇ−ＩＲＬ、（４）Ｇａｕｓｓ−ＩＲＬ、（５）ＬＳＣＤＥ−ＯｐｔＶ、これはｐ（ｙ｜ｘ）がＬＳＣＤＥによって推定されるＯｐｔＶの方法である、及び（６）Ｇａｕｓｓ−ＯｐｔＶ、ここで、ガウス過程の方法はｐ（ｙ｜ｘ）を推定するために使用される。
【００４２】
我々はＤｐとＤπのサンプル数をＮｐ＝Ｎπ＝３００で設定する。パラメータλｑ、λＶ、σ、及びγは以下の領域ｌｏｇ λｑ、
0006417629.tif 000046
0006417629.tif 000047
及び
0006417629.tif 000048
から交差検証によって最適化される。ここで、ｌｉｎｓｐａｃｅ（ｘｍｉｎ，ｘｍａｘ，ｎ）はｘｍｉｎとｘｍａｘの間で等間隔である一式のｎポイントを生成する。
【００４３】
＜３．１．２．実験結果＞
推定されたコスト関数の精度はテストサンプル
0006417629.tif 000049
に対する正規化二乗誤差によって測定される。ここで、それぞれｑ（ｘｊ）は方程式（１９）に示す状態ｘｊにおける１つの真のコスト関数である一方、
0006417629.tif 000050
は推定されたコスト関数である。図１（ａ）−（ｄ）は本実施形態のＩＲＬ方法の精度を比べている。我々の方法（１）−（４）は全ての設定でＯｐｔＶの方法（５）−（６）より良い成績を収めたことが示されている。より具体的には、ＬｏｇＲｅｇ−ＩＲＬは最良の成績を示したが、我々の方法（１）−（３）の中では大した差はなかった。もし確率的方策π（ｕ｜ｘ）が混合ガウスによって与えられたなら、Ｇａｕｓｓ―ＩＲＬによって推定されたコストの精度は大幅に増加した。なぜなら、標準的なガウス過程は混合ガウスを表すことができないからである。
【００４４】
図２はλｑ、λＶ、及びσといった他のパラメータが最適値に設定された場合における割引率γの交差検証誤差を示している。このシミュレーションでは、交差検証誤差は全ての方法において真の割引率
0006417629.tif 000051
で最小であった。図２に示すように、また、上記図１でも説明したように、本発明の実施形態が十分に小さな誤差を有することが判明し、本発明の効果の有効性を確認した。
【００４５】
＜３．２．人間の挙動の分析＞
＜３．２．１．タスク詳解＞
我々のＩＲＬアルゴリズムを現実の状況で評価するために、本発明者らはモーターで動的に制御するポールバランシング問題を行った。図３は実験手順を示している。被験者はポールを何回も揺らすために台座を左右上下に動かすことができ、倒立位置でバランスするようにポールを減速させる。ダイナミクスは６次元状態ベクトル
0006417629.tif 000052
によって記載される。ここで、θと
0006417629.tif 000053
はポールの角度と角速度であり、ｘとｙは台座の水平位置と垂直位置である。そして、
0006417629.tif 000054
と
0006417629.tif 000055
はそれぞれその時間微分である。
【００４６】
タスクは２つの条件：ロングポール（７３ｃｍ）とショートポール（２９ｃｍ）の下で行われた。各被験者について各条件でポールをバランスさせるための試行を１５回行った。各被験者がポールを３秒間又は４０秒間経過して直立状態を維持できたときに各試行が終了した。我々は７人の被験者（内、５人が右利き、２人が左利き）からデータを収集し、controlling probabilityの以下の２つのデータセット、ｉ番目の被験者のトレーニング用
0006417629.tif 000056
とｉ番目の被験者のテスト用
0006417629.tif 000057
を構築するために、軌道に基づいたサンプリング法が使用された。全ての被験者が、無作為な方策によって生成された、一様なuncontrolled probability ｐ（ｙ｜ｘ）を持ったと仮定する。これはトレーニング用
0006417629.tif 000058
とテスト用
0006417629.tif 000059
というデータセットが被験者間で共有されることを意味している。データセットのサンプル数は３００だった。
【００４７】
＜４．２．２．実験結果＞
図４は７つの被験者の学習曲線を示しているが、これは学習過程が被験者間で全く異なったことを示している。Ｎｏ．１とＮｏ．３の２人の被験者はタスクを達成できなかった。成功軌道一式はＩＲＬアルゴリズムによって使用されるべきであるので、我々はＮｏ．２及びＮｏ．４−Ｎｏ．７の５人の被験者からデータを拾い上げた。
【００４８】
ＬｏｇＲｅｇ−ＩＲＬを使用した場合の実験結果を以下に記載する（ＬＳＣＤＥ−ＩＲＬとｕＬＳＩＦ−ＩＲＬは似たような結果を示した）。図５は部分空間
0006417629.tif 000060
に投影された、被験者４、５、及び７の推定されたコスト関数を示している一方で、ｘ、ｙ、
0006417629.tif 000061
及び
0006417629.tif 000062
は視覚化のためにゼロに設定されている。被験者７の場合、ロングポール条件のコスト関数はショートポール条件のコスト関数とそんなに異ならなかった一方、図４に示すようなショートポール条件ではうまくいかなかった、被験者５の場合とは顕著な違いがあった。
【００４９】
トレーニングデータセットから推定されたコスト関数を評価するために、我々は推定されたコスト関数に対して最適に制御された遷移確率を発見するために、順強化学習を利用し、その際、テストデータセット
0006417629.tif 000063
に対する負の対数尤度を計算した。ここで、
0006417629.tif 000064
は、
0006417629.tif 000065
のサンプル数である。図６は結果を示している。左の挿絵（ａ）で、我々はロングポール条件における被験者４のテストデータセット
0006417629.tif 000066
を使用した。最小の負の対数尤度は同じ条件のトレーニングデータセット
0006417629.tif 000067
及び
0006417629.tif 000068
から推定されたコスト関数によって達成された。図６の右のパネル（ｂ）は、ロングポール条件とショートポール条件の両方における被験者７のテストデータがロングポール条件だけにおける同じ被験者７のトレーニングデータセットから推定されたコスト関数によって最も良く予測されたことを示している。すなわち、本発明の実施形態の有効性及び有用性がこの実験によって同様に確認され、実証された。
【００５０】
本開示はＬＭＤＰの枠組みの下での新規な逆強化学習を示した。本発明の特徴の１つは方程式（１１）を示すことであるが、これは最適な価値関数にとって対応するコスト関数と共にＴＤ誤差がゼロであることを示している。方程式（１１）の右手側はサンプルから密度比推定の効率的な方法によって推定できるので、結果的に本発明のＩＲＬは簡易な正則化付き最小二乗法になる。また、本発明の実施形態に係る方法は、高次元の連続問題では通常扱いにくい、積分を計算する必要がない。結果として、開示された方法はＯｐｔＶより計算的に安上がりになる。
【００５１】
ＬＭＤＰと経路積分法はロボットの分野及び機械学習の分野で近年注目を浴びてきた（Theodorou & Todorov、２０１２、非特許文献２２）。なぜなら、線形ベルマン方程式には多くの興味深い性質が存在するからである（Todorov、２００９ａ、非特許文献２４）。これらは大きな自由度とともにロボットに対する確率的方策の学習にうまく利用されてきた（Kinjoら、２０１３、非特許文献１１；Stulp & Sigaud、２０１２、非特許文献１７；Sugimoto and Morimoto、２０１１、非特許文献１８；Theodorouら、２０１０、非特許文献２１）。本発明の実施形態に係るＩＲＬ法は複雑なコントローラを設計するために現行の順強化学習と一体化してもよい。
【００５２】
上述したように、本発明の少なくともいくつかの態様では、本開示は観察された挙動から効果的に報酬関数／コスト関数を推測できる計算アルゴリズムを提供する。本発明の実施形態のアルゴリズムは、特別に設計された専用のハードウェア／ソフトウェアと同様に、適切なハードウェア及びソフトウェアを備えている汎用のコンピュータシステムで実施可能である。本発明の少なくともいくつかの実施形態に係るさまざまな利点は以下を含んでいる。
Ａ）モデルにとらわれない方法／システム：本発明の実施形態に係る方法及びシステムは環境ダイナミクスを事前に知る必要がない。すなわち、先行技術のいくつかのやり方は環境ダイナミクスが事前に知られているということを前提としているが、この方法／システムはモデルにとらわれない方法と扱われ、対象のダイナミクスをはっきりと作る必要がない。
Ｂ）データ効率：以前の多くの方法は状態の軌道一式を要求するが、本発明の実施形態に係る方法及びシステムのためのデータセットは状態遷移一式からなる。したがって、本発明の実施形態に係る方法及びシステムでは、データを集め易い。
Ｃ）計算効率（１）：本発明の実施形態に係る方法及びシステムは（順）強化学習の問題を解く必要がない。対照的に、以前のいくつの方法は推定された報酬関数・推定されたコスト関数で何度もこのような順強化学習の問題を解くことを要求した。その計算は各候補に対して行わなければならず、最適解を発見するためには通常長い時間がかかる。
Ｄ）計算効率（２）：本発明の実施形態に係る方法及びシステムは２つの最適化プログラム：（ａ）密度比推定、及び（ｂ）正則化最小二乗、を使用する。対照的に、以前のいくつの方法は、最小二乗法と比較してたいてい最適化のための時間がかかる、確率的勾配法やマルコフ連鎖モンテカルロ法を使用している。
【００５３】
上述したように、１つの態様では、本発明はデモンストレータによって生成された観察された状態遷移から目的関数を推測できる逆強化学習を提供する。図７は本発明の実施形態に係る方法の枠組みを概略的に示している。本発明に係る逆強化学習の実施形態は２つの構成要素、（１）密度比推定を伴う状態遷移確率と密度比推定を伴わない状態遷移確率の比、及び（２）正則化付き最小二乗法による遷移確率比と矛盾しないコスト関数と価値関数の推定、を含んでいる。各ステップのための効率的なアルゴリズムを使用することにより、本発明の実施形態は他の逆強化学習法よりデータ及び計算の点で効率的である。
【００５４】
逆強化学習の産業上の利用可能性及び有用性は十分に理解され認められた。以下では、本発明の実施形態を適用できるシステム例及び構成例を記載する。
【００５５】
＜ロボット挙動の模倣学習＞
複雑なタスクを行うためのロボットをプログラミングすることは、モーションプランニングといった標準的な方法とともに困難である。多くの状況で、ロボットに対して設計された挙動を実演することの方がはるかに易しい。しかしながら、古典的な模倣学習の大きな欠点は、獲得したコントローラが実演された動作をただ再現するだけだから新しい状況に対処できないことである。本発明の実施形態は実演された挙動から目的関数を推定でき、その際、推定された目的関数は異なる状況に対する異なる挙動を学習するために使用することができる。
【００５６】
図８はこのような本発明の実施を概略的に示している。まず、デモンストレータはロボットにタスクを遂行させると、状態と行動の順序が記録される。次いで、本発明の実施形態に係る逆強化学習部はコスト関数と価値関数を推定する。その後、これらは異なるロボットに対する順強化学習のコントローラに与えられる。
【００５７】
＜人間の挙動の解釈＞
挙動の背後にある人間の意図を理解することはユーザフレンドリーな支援システムを構築する際に基本的な論点である。一般的に、挙動は、動作追跡システムによって抽出される、一連の状態によって表される。本発明の実施形態に係る逆強化学習の方法／システムによって推定されたコスト関数は、所定の挙動のデータセットを説明するためにコンパクトな表現として扱うことができる。推定されたコスト関数のパターン分類を通じて、ユーザの専門知識又は嗜好を推定することが可能になる。図９は本発明の実施形態に係るこの実施を概略的に示している。
【００５８】
＜Ｗｅｂエクスペリエンスの分析＞
ビジターに対して提供される記事を読むためのビジター用見込みを増加させるために、例えば、オンラインニュースサイトの設計者は意思決定の観点からビジターのＷｅｂエクスペリエンスを調査すべきである。特に、推奨システムは個人向けサービスに対する重要なビジネスアプリとして注目を浴びている。しかしながら、協調フィルタリングといった以前の方法は明らかに意思決定の順序を考慮していない。本発明の実施形態は、ネットサーフィン中のビジターの挙動をモデル化するための別の効果的な手法を提供することができる。図１０は、トピックスがどんな順序でユーザによってアクセスされたかを示す、ユーザによる一連のクリックアクションの一例を示している。ビジターが読んでいるトピックスは状態として扱われ、リンクをクリックすることはアクションとして考慮される。その際、本発明の実施形態に係る逆強化学習はユーザのネットサーフィンでの意思決定を分析することができる。推定されたコスト関数はビジターの嗜好を表すので、ユーザ向けの記事のリストを推奨することができる。
【００５９】
上述したように、本発明の実施形態に係る逆強化学習スキームは、広く様々な産業上、及び／又は、商業上のシステムに適用可能である。図１１は汎用コンピュータシステム及びセンサシステムを使用する実施例を示している。数学の方程式と共に以上説明した方法は、例えばこのような汎用コンピュータシステムで実施可能である。挿絵に示すように、この例のシステムは、状態遷移についての情報、すなわち観察した挙動、を観察されている対象から受信するセンサシステム１１１（データ取得手段の一例）を含んでいる。センサシステム１１１は画像処理ソフト／画像処理ハード、変位センサ、速度センサ、加速度センサ、マイク、キーボード、及び他のあらゆる入力装置と共に、一以上の画像キャプチャ装置を含んでいてもよい。センサシステム１１１は、本発明の実施形態に従って受信データを分析できるような、プロセッサ１１３を適切なメモリ１１４と共に備えるコンピュータ１１２に接続される。分析の結果は、表示モニタ、コントローラ、ドライバなど（出力インタフェースの例）、又は、その結果をコントロール用に活用する場合にコントロールされるべき対象といった、あらゆる出力システム１１５に出力される。上述したように、結果はプログラムに使用できたり、ユーザの相互作用に応答する別のロボット、コンピュータ、又はウェブサイトのソフトといった、別のシステムに転送できたりする。
【００６０】
上述したユーザのＷｅｂ記事嗜好を予測する場合、実施システムは、インターネットに接続されたコンピュータで実施される、上記実施形態のいずれか１つで述べたような逆強化学習用システムを含んでいてもよい。ここで、ユーザの挙動を定義する状態変数は、各ウェブページを閲覧している間にユーザによって選択された記事のトピックスを含んでいる。その際、逆強化学習の結果は、ユーザがインターネットのＷｅｂサイトを閲覧する、携帯用のスマートフォンやパーソナルコンピュータなどといったインタフェースに、ユーザ向けの推奨記事を表示させるために使用される。
【００６１】
本発明の趣旨又は範囲から逸脱することなく本発明に対して様々な修正及び変形を行えることは当業者には自明である。すなわち、本発明は添付の特許請求の範囲とその均等物の範囲内で生じる修正及び変形を包含することが意図されている。特に、上述したいずれか２以上の実施形態及びその修正のいずれかの一部又は全体が結合されて本発明の範囲内でみなされることは明示的に熟慮される。
【図１】
0006417629.tif 000072
【図２】
0006417629.tif 000073
【図３】
0006417629.tif 000074
【図４】
0006417629.tif 000075
【図５】
0006417629.tif 000076
【図６】
0006417629.tif 000077
【図７】
0006417629.tif 000078
【図８】
0006417629.tif 000079
【図９】
0006417629.tif 000080
【図１０】
0006417629.tif 000081
【図１１】
0006417629.tif 000082