(57)【特許請求の範囲】
【請求項１】
ユーザの位置と移動速度のデータを取得するデータ取得手段と、
取得された前記ユーザの位置と移動速度のデータを記憶するデータ記憶手段と、
前記データ記憶手段に記憶されたデータを含む前記ユーザの位置と移動速度の時系列データを用いて隠れマルコフモデルにより学習して得られた、前記ユーザの活動状態を表す前記活動モデルのパラメータを用いて、少なくとも移動状態と滞在状態に区別される前記ユーザの行動状態及び前記ユーザの現在地を認識する行動認識手段と、
前記行動認識手段により認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測する行動予測手段と、
前記ユーザの行動状態が前記滞在状態になる状態ノードを目的地候補とし、その１以上の前記目的地候補のうち、予測された前記経路上にある目的地候補を目的地として、前記目的地までの経路と選択確率から、目的地へ到達する到達確率と到達時間を予測する到達時間予測手段と
を備えるデータ処理装置。
【請求項２】
前記学習では、前記隠れマルコフモデルの尤度が最大になるように隠れマルコフモデルのパラメータが求められる
請求項１に記載のデータ処理装置。
【請求項３】
前記行動認識手段は、前記ユーザの現在地に対応する状態ノードを求めることにより、前記ユーザの現在地を認識する
請求項１に記載のデータ処理装置。
【請求項４】
前記行動予測手段は、前記現在地に対応する状態ノードを出発点として、状態遷移が可能な状態ノードを次の移動先として、可能な全ての経路を探索し、探索された各経路の選択確率を算出する
請求項３に記載のデータ処理装置。
【請求項５】
前記行動予測手段は、経路の探索において、経路内に端点か、これまで通過した経路内に含まれる点が現れた場合、その経路の探索を終了する
請求項４に記載のデータ処理装置。
【請求項６】
前記行動予測手段は、学習により求められた各状態ノードの状態遷移確率から、自己遷移確率を除いて規格化された遷移確率を、経路を構成する状態ノード間で順次乗算することにより、前記経路の選択確率を算出する
請求項１に記載のデータ処理装置。
【請求項７】
前記到達時間予測手段は、前記目的地に対し、複数の経路が探索された場合、目的地への各経路の前記選択確率の和を計算することにより、前記目的地へ到達する到達確率を予測する
請求項１に記載のデータ処理装置。
【請求項８】
前記到達時間予測手段は、現在時刻から、前記目的地に対応する状態ノードの直前の状態ノードから前記目的地に対応する状態ノードに遷移するまでの時間の期待値として、予測された前記経路の到達時間を予測する
請求項１に記載のデータ処理装置。
【請求項９】
取得される前記ユーザの移動速度のデータは、移動速度と進行方向の変化を表す値である
請求項１に記載のデータ処理装置。
【請求項１０】
前記学習では、前記行動状態ごとに前記移動速度の時系列データを予め分類し、分類された前記行動状態ごとに、同一の隠れマルコフモデルの異なるパラメータが学習されており、
前記行動認識手段は、前記行動状態ごとの前記ユーザの活動モデルのうち、尤度の最も高い行動状態を、ユーザの行動状態として選択する
請求項１に記載のデータ処理装置。
【請求項１１】
前記学習では、前記移動速度の時系列データと、同時刻の対応する前記ユーザの行動状態の時系列データを関連付けるように前記隠れマルコフモデルが学習されており、
前記行動認識手段は、前記移動速度の時系列データに対応する前記隠れマルコフモデルにおける状態ノードのうち最も尤度の高い状態ノードを認識し、認識された状態ノードで最も確率の高い行動状態を、ユーザの行動状態として選択する
請求項１に記載のデータ処理装置。
【請求項１２】
前記学習では、前記ユーザの位置と行動状態に作用する行動条件の時系列データも用いて、前記ユーザの前記活動モデルが学習されており、
前記行動認識手段は、現在の行動条件下で、前記ユーザの位置および行動状態を認識する
請求項１に記載のデータ処理装置。
【請求項１３】
データ処理装置の、
データ取得手段が、ユーザの位置と移動速度のデータを取得し、
データ記憶手段が、取得された前記ユーザの位置と移動速度のデータを記憶し、
行動認識手段が、前記データ記憶手段に記憶されたデータを含む前記ユーザの位置と移動速度の時系列データを用いて隠れマルコフモデルにより学習して得られた、前記ユーザの活動状態を表す前記活動モデルのパラメータを用いて、少なくとも移動状態と滞在状態に区別される前記ユーザの行動状態及び前記ユーザの現在地を認識し、
行動予測手段が、認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測し、
到達時間予測手段が、前記ユーザの行動状態が前記滞在状態になる状態ノードを目的地候補とし、その１以上の前記目的地候補のうち、予測された前記経路上にある目的地候補を目的地として、前記目的地までの経路と選択確率から、目的地へ到達する到達確率と到達時間を予測する
ステップを含むデータ処理方法。
【請求項１４】
コンピュータを、
ユーザの位置と移動速度のデータを取得するデータ取得手段と、
取得された前記ユーザの位置と移動速度のデータをデータ記憶手段に記憶させるデータ記憶制御手段と、
前記データ記憶手段に記憶されたデータを含む前記ユーザの位置と移動速度の時系列データを用いて隠れマルコフモデルにより学習して得られた、前記ユーザの活動状態を表す前記活動モデルのパラメータを用いて、少なくとも移動状態と滞在状態に区別される前記ユーザの行動状態及び前記ユーザの現在地を認識する行動認識手段と、
前記行動認識手段により認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測する行動予測手段と、
前記ユーザの行動状態が前記滞在状態になる状態ノードを目的地候補とし、その１以上の前記目的地候補のうち、予測された前記経路上にある目的地候補を目的地として、前記目的地までの経路と選択確率から、目的地へ到達する到達確率と到達時間を予測する到達時間予測手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理方法、およびプログラムに関し、特に、時系列データからユーザの活動状態を確率的状態遷移モデルとして学習することによって、目的地までの経路および時間を求めることができるようにするデータ処理装置、データ処理方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、ユーザが身に着けられるセンサであるウェアラブルセンサから得られる時系列データを用いてユーザの状態をモデル化して学習し、学習により得られたモデルを用いてユーザの現在の状態を認識する研究が盛んである（例えば、特許文献１，２、非特許文献１）。
【０００３】
また、本出願人は、未来の所望の時刻におけるユーザの活動状態の複数の可能性を確率的に予測する方法を、特願２００９−１８０７８０（以下、先願という）として先に提案している。先願の方法では、時系列データからユーザの活動状態を確率的状態遷移モデルとして学習し、学習した確率的状態遷移モデルを用いて現在の活動状態を認識し、「所定時間後」のユーザの活動状態を確率的に予測することができる。そして、「所定時間後」のユーザの活動状態の予測の一例として、ユーザの現在の位置を認識し、所定時間後のユーザの行き先（場所）を予測する例が示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−１３４０８０号公報
【特許文献２】特開２００８−２０４０４０号公報
【非特許文献】
【０００５】
【非特許文献１】“Life Patterns: structure from wearable sensors”,Brian Patrick Clarkson, Doctor Thesis, MIT, 2002
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、所定時間後のユーザの行き先（場所）を予測したい場合もあるが、目的地が決まっている場合には、その目的地までの経路や時間が知りたい場合が多い。
【０００７】
しかしながら、先願の方法では、「所定時間後」という現在時刻からの経過時間の指定がない場合には、目的地までの経路および時間を求めることが困難であった。
【０００８】
本発明は、このような状況に鑑みてなされたものであり、時系列データからユーザの活動状態を確率的状態遷移モデルとして学習することによって、目的地までの経路および時間を求めることができるようにするものである。
【課題を解決するための手段】
【０００９】
本発明の一側面のデータ処理装置は、
ユーザの位置と移動速度のデータを取得するデータ取得手段と、
取得された前記ユーザの位置と移動速度のデータを記憶するデータ記憶手段と、
前記データ記憶手段に記憶されたデータを含む前記ユーザの位置と移動速度の時系列データを用いて隠れマルコフモデルにより学習して得られた、前記ユーザの活動状態を表す前記活動モデルのパラメータを用いて、少なくとも移動状態と滞在状態に区別される前記ユーザの行動状態及び前記ユーザの現在地を認識する行動認識手段と、
前記行動認識手段により認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測する行動予測手段と、
前記ユーザの行動状態が前記滞在状態になる状態ノードを目的地候補とし、その１以上の前記目的地候補のうち、予測された前記経路上にある目的地候補を目的地として、前記目的地までの経路と選択確率から、目的地へ到達する到達確率と到達時間を予測する到達時間予測手段と
を備える。
【００１０】
本発明の一側面のデータ処理方法は、
データ処理装置の、
データ取得手段が、ユーザの位置と移動速度のデータを取得し、
データ記憶手段が、取得された前記ユーザの位置と移動速度のデータを記憶し、
行動認識手段が、前記データ記憶手段に記憶されたデータを含む前記ユーザの位置と移動速度の時系列データを用いて隠れマルコフモデルにより学習して得られた、前記ユーザの活動状態を表す前記活動モデルのパラメータを用いて、少なくとも移動状態と滞在状態に区別される前記ユーザの行動状態及び前記ユーザの現在地を認識し、
行動予測手段が、認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測し、
到達時間予測手段が、前記ユーザの行動状態が前記滞在状態になる状態ノードを目的地候補とし、その１以上の前記目的地候補のうち、予測された前記経路上にある目的地候補を目的地として、前記目的地までの経路と選択確率から、目的地へ到達する到達確率と到達時間を予測する
ステップを含む。
【００１１】
本発明の一側面のプログラムは、
コンピュータを、
ユーザの位置と移動速度のデータを取得するデータ取得手段と、
取得された前記ユーザの位置と移動速度のデータをデータ記憶手段に記憶させるデータ記憶制御手段と、
前記データ記憶手段に記憶されたデータを含む前記ユーザの位置と移動速度の時系列データを用いて隠れマルコフモデルにより学習して得られた、前記ユーザの活動状態を表す前記活動モデルのパラメータを用いて、少なくとも移動状態と滞在状態に区別される前記ユーザの行動状態及び前記ユーザの現在地を認識する行動認識手段と、
前記行動認識手段により認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測する行動予測手段と、
前記ユーザの行動状態が前記滞在状態になる状態ノードを目的地候補とし、その１以上の前記目的地候補のうち、予測された前記経路上にある目的地候補を目的地として、前記目的地までの経路と選択確率から、目的地へ到達する到達確率と到達時間を予測する到達時間予測手段
として機能させる。
【００１２】
本発明の一側面においては、ユーザの位置と移動速度のデータが取得され、取得されたユーザの位置と移動速度のデータがデータ記憶手段に記憶され、データ記憶手段に記憶されたデータを含むユーザの位置と移動速度の時系列データを用いて隠れマルコフモデルにより学習して得られたユーザの活動状態を表す活動モデルのパラメータを用いて、少なくとも移動状態と滞在状態に区別されるユーザの行動状態及びユーザの現在地が認識され、認識されたユーザの現在地から可能な経路と、その経路の選択確率が予測され、ユーザの行動状態が滞在状態になる状態ノードが目的地候補とされ、その１以上の目的地候補のうち、予測された経路上にある目的地候補を目的地として、目的地までの経路と選択確率から、目的地へ到達する到達確率と到達時間が予測される。
【発明の効果】
【００１３】
本発明の一側面によれば、時系列データからユーザの活動状態を確率的状態遷移モデルとして学習し、目的地までの経路および時間を求めることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明を適用した予測システムの第１の実施の形態の構成例を示すブロック図である。
【図２】予測システムのハードウエア構成例を示すブロック図である。
【図３】予測システムに入力される時系列データの例を示す図である。
【図４】HMMの例を示す図である。
【図５】音声認識で利用されるHMMの例を示す図である。
【図６】スパース制約を与えたHMMの例を示す図である。
【図７】行動予測部による経路の探索処理の簡単な例を示す図である。
【図８】ユーザ活動モデル学習処理のフローチャートである。
【図９】到達時間予測処理のフローチャートである。
【図１０】本発明を適用した予測システムの第２の実施の形態の構成例を示すブロック図である。
【図１１】図１０の行動学習部の第１の構成例を示すブロック図である。
【図１２】図１０の行動学習部の第２の構成例を示すブロック図である。
【図１３】図１１の行動状態認識部に対応する学習器の第１の構成例を示すブロック図である。
【図１４】行動状態の分類例を示している。
【図１５】図１３の行動状態ラベリング部の処理例を説明する図である。
【図１６】図１３の行動状態ラベリング部の処理例を説明する図である。
【図１７】図１３の行動状態学習部の構成例を示すブロック図である。
【図１８】図１３の行動状態学習部による学習結果を示す図である。
【図１９】図１３の行動状態学習部に対応する行動状態認識部の構成例を示すブロック図である。
【図２０】図１１の行動状態認識部に対応する学習器の第２の構成例を示すブロック図である。
【図２１】行動状態ラベリング部の処理例を説明する図である。
【図２２】図２０の行動状態学習部による学習結果を示す図である。
【図２３】図２０の行動状態学習部に対応する行動状態認識部の構成例を示すブロック図である。
【図２４】目的地到達時間予測処理のフローチャートである。
【図２５】目的地到達時間予測処理のフローチャートである。
【図２６】図１０の予測システムの処理結果例を示す図である。
【図２７】図１０の予測システムの処理結果例を示す図である。
【図２８】図１０の予測システムの処理結果例を示す図である。
【図２９】図１０の予測システムの処理結果例を示す図である。
【図３０】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための形態】
【００１５】
以下、本発明を実施するための形態（以下、実施の形態という）について説明する。なお、説明は以下の順序で行う。
１．第1の実施の形態（目的地が指定された場合の目的地までの経路および到達時間を予測する例）
２．第２の実施の形態（目的地も予測して、目的地までの経路および到達時間を予測する場合の例）
【００１６】
＜１．第1の実施の形態＞
［予測システムの第1の実施の形態のブロック図］
図１は、本発明を適用した予測システムの第１の実施の形態の構成例を示すブロック図である。
【００１７】
予測システム１は、GPSセンサ１１、時系列データ記憶部１２、行動学習部１３、行動認識部１４、行動予測部１５、到達時間予測部１６、操作部１７、および表示部１８により構成される。
【００１８】
予測システム１は、GPSセンサ１１により取得される現在地を示す時系列データから、ユーザの活動状態（行動・活動パターンを表した状態）を確率的状態遷移モデルとして学習する学習処理を行う。また、予測システム１は、学習処理により得られたパラメータで表される確率的状態遷移モデル（ユーザ活動モデル）を用いて、ユーザが指定した目的地までの経路および時間を予測する予測処理も行う。
【００１９】
図１において、点線の矢印は、学習処理におけるデータの流れを示しており、実線の矢印は、予測処理におけるデータの流れを示している。
【００２０】
GPSセンサ１１は、自身の位置を示す緯度経度のデータを、一定時間間隔（たとえば、１５秒間隔）で順次取得する。なお、GPSセンサ１１が位置のデータを一定間隔に取得することができない場合もある。例えば、トンネルや地下にいる場合などには、人工衛星を捕捉することができず、取得間隔が長くなることもある。このような場合には、補間処理を行うことなどにより、データを補うことができる。
【００２１】
GPSセンサ１１は、学習処理においては、取得される位置（緯度経度）のデータを時系列データ記憶部１２に供給する。また、GPSセンサ１１は、予測処理においては、取得される位置データを行動認識部１４に供給する。
【００２２】
時系列データ記憶部１２は、GPSセンサ１１により連続して取得された位置データ、すなわち、位置の時系列データを記憶する。ユーザの行動・活動パターンを学習するので、例えば、数日分程度など、ある程度の期間について蓄積された時系列データが必要である。
【００２３】
行動学習部１３は、時系列データ記憶部１２に記憶されている時系列データに基づいて、GPSセンサ１１が組み込まれた機器を携行するユーザの活動状態を、確率的状態遷移モデルとして学習する。時系列データはユーザの位置を示すデータであるので、確率的状態遷移モデルとして学習されるユーザの活動状態は、ユーザの現在地の時系列変化、すなわちユーザの移動経路を表す状態となる。学習に使用される確率的状態遷移モデルとしては、例えば、エルゴディックHMM（Hidden Markov Model）などの、隠れ状態を含む確率的状態遷移モデルを採用することができる。本実施の形態では、確率的状態遷移モデルとして、エルゴディックHMMにスパース制約を与えたものを採用する。なお、スパース制約を与えたエルゴディックHMM、エルゴディックHMMのパラメータの算出方法等については、図４乃至図６を参照して後述する。
【００２４】
行動学習部１３は、学習結果を示すデータを表示部１８に供給し、表示させる。また、行動学習部１３は、学習処理により得られた確率的状態遷移モデルのパラメータを行動認識部１４および行動予測部１５に供給する。
【００２５】
行動認識部１４は、学習により得られたパラメータの確率的状態遷移モデルを用いて、GPSセンサ１１からリアルタイムに供給される位置の時系列データから、ユーザの現在の活動状態、すなわち、ユーザの現在地を認識する。行動認識部１４は、ユーザの現在の状態ノードのノード番号を行動予測部１５に供給する。
【００２６】
行動予測部１５は、学習により得られたパラメータの確率的状態遷移モデルを用いて、行動認識部１４から供給される状態ノードのノード番号が示すユーザの現在地から、ユーザが取りうる経路を過不足なく探索（予測）する。また、行動予測部１５は、探索された経路ごとの生起確率を計算することにより、探索された経路が選択される確率である選択確率を予測する。
【００２７】
到達時間予測部１６には、行動予測部１５から、ユーザが取りうる経路と、その選択確率が供給される。また、到達時間予測部１６には、操作部１７から、ユーザが指定した目的地を示す情報が供給される。
【００２８】
到達時間予測部１６は、探索結果としてのユーザが取りうる経路から、ユーザが指定した目的地を含む経路を抽出し、抽出された各経路について目的地までの到達時間を予測する。また、到達時間予測部１６は、目的地へ到達する確率である到達確率を予測する。到達時間予測部１６は、目的地について複数の経路が存在する場合、その複数の経路の選択確率の和を、目的地の到達確率として算出する。目的地への経路が１つのみである場合には、その経路の選択確率が、そのまま目的地の到達確率となる。そして、到達時間予測部１６は、予測結果を示す情報を表示部１８に供給し、表示させる。
【００２９】
操作部１７は、ユーザが入力した目的地についての情報を受け付け、到達時間予測部１６に供給する。表示部１８は、行動学習部１３または到達時間予測部１６から供給される情報を表示する。
【００３０】
［予測システムのハードウエア構成例］
以上のように構成される予測システム１は、例えば、図２に示されるハードウエア構成を採用することができる。即ち、図２は、予測システム１のハードウエア構成例を示すブロック図である。
【００３１】
図２において、予測システム１は、３台のモバイル端末２１−１乃至２１−３とサーバ２２とにより構成されている。モバイル端末２１−１乃至２１−３は、同一機能を有する同型のモバイル端末２１であるが、モバイル端末２１−１乃至２１−３では、それを所有するユーザが異なる。従って、図２では、３台のモバイル端末２１−１乃至２１−３のみが示されているが、実際には、ユーザ数に応じた数のモバイル端末２１が存在する。
【００３２】
モバイル端末２１は、無線通信及びインターネット等のネットワークを介した通信により、サーバ２２とデータの授受を行うことができる。サーバ２２は、モバイル端末２１から送信されてくるデータを受信し、受信したデータに対し所定の処理を行う。そして、サーバ２２は、データ処理の処理結果を無線通信等によりモバイル端末２１に送信する。
【００３３】
従って、モバイル端末２１とサーバ２２は、無線または有線による通信を行う通信部を少なくとも有する。
【００３４】
さらに、モバイル端末２１が、図１のGPSセンサ１１、操作部１７、および表示部１８を備え、サーバ２２が、図１の時系列データ記憶部１２、行動学習部１３、行動認識部１４、行動予測部１５、および到達時間予測部１６を備える構成を採用することができる。
【００３５】
この構成が採用される場合、学習処理において、モバイル端末２１が、GPSセンサ１１により取得された時系列データを送信する。サーバ２２は、受信した学習用の時系列データに基づき、ユーザの活動状態を確率的状態遷移モデルにより学習する。そして、予測処理において、モバイル端末２１が、操作部１７を介してユーザによって指定された目的地を送信するとともに、GPSセンサ１１によりリアルタイムに取得される位置データを送信する。サーバ２２は、学習により得られたパラメータを用いて、ユーザの現在の活動状態、すなわち、ユーザの現在地を認識し、さらに、指定された目的地までの経路および時間を処理結果としてモバイル端末２１に送信する。モバイル端末２１は、サーバ２２から送信されてきた処理結果を表示部１８に表示する。
【００３６】
また例えば、モバイル端末２１が、図１のGPSセンサ１１、行動認識部１４、行動予測部１５、到達時間予測部１６、操作部１７、および表示部１８を備え、サーバ２２が、図１の時系列データ記憶部１２および行動学習部１３を備える構成を採用することができる。
【００３７】
この構成が採用される場合、学習処理において、モバイル端末２１が、GPSセンサ１１により取得された時系列データを送信する。サーバ２２は、受信した学習用の時系列データに基づき、ユーザの活動状態を確率的状態遷移モデルにより学習し、学習により得られたパラメータをモバイル端末２１に送信する。そして、予測処理において、モバイル端末２１が、GPSセンサ１１によりリアルタイムに取得される位置データと、サーバ２２から受信したパラメータを用いて、ユーザの現在地を認識し、さらに、指定された目的地までの経路および時間を演算する。そして、モバイル端末２１は、演算結果としての目的地までの経路および時間を表示部１８に表示する。
【００３８】
以上のようなモバイル端末２１とサーバ２２との間の役割分担は、それぞれのデータ処理装置としての処理能力や通信環境に応じて決定することができる。
【００３９】
学習処理は、処理に要する１回あたりの時間は非常に長いが、それほど頻繁に処理する必要はない。従って、一般的には、携行可能なモバイル端末２１よりもサーバ２２の方が処理能力が高いので、サーバ２２に、一日に一回程度蓄積された時系列データに基づいて学習処理（パラメータの更新）を行わせるようにすることができる。
【００４０】
一方、予測処理は、時々刻々とリアルタイムに更新される位置データに対応させて迅速に処理し、表示することが望ましいので、モバイル端末２１で処理を行う方が望ましい。通信環境がリッチであれば、上述したようにサーバ２２に予測処理も行わせ、予測結果のみをサーバ２２から受信する方が、携行可能な小型化が要求されるモバイル端末２１の負荷が軽減され、望ましい。
【００４１】
また、モバイル端末２１単独で、データ処理装置として学習処理および予測処理を高速に行うことが可能である場合には、図１の予測システム１の構成すべてをモバイル端末２１が備えるようにすることも勿論可能である。
【００４２】
［入力される時系列データの例］
図３は、予測システム１で取得された位置の時系列データの例を示している。図３において、横軸は経度を表し、縦軸は緯度を表している。
【００４３】
図３に示される時系列データは、実験者の１ヶ月半程度の期間に蓄積された時系列データを示している。図３に示されるように、時系列データは、主に、自宅周辺と、勤務先などの４か所の外出先を移動したデータとなっている。なお、この時系列データには、人工衛星を捕捉できず、位置データが飛んでいるデータも含まれている。
【００４４】
図３に示される時系列データは、後述する検証実験において学習データとして使用した時系列データでもある。
【００４５】
［エルゴディックHMMについて］
次に、予測システム１が、学習モデルとして採用するエルゴディックHMMについて説明する。
【００４６】
図４は、HMMの例を示している。
【００４７】
HMMは、状態と状態間遷移とを有する状態遷移モデルである。
【００４８】
図４は、３状態のHMMの例を示している。
【００４９】
図４において（以降の図においても同様）、丸印は、状態を表し、矢印は、状態遷移を表す。なお、状態は、上述のユーザの活動状態に対応し、状態ノードと同義である。
【００５０】
また、図４において、si（図４では、i=1,2,3）は、状態（ノード）を表し、aijは、状態siから状態sjへの状態遷移確率を表す。さらに、bj(x)は、状態sjへの状態遷移時に、観測値xが観測される出力確率密度関数を表し、πiは、状態siが初期状態である初期確率を表す。
【００５１】
なお、出力確率密度関数bj(x)としては、例えば、混合正規確率分布等が用いられる。
【００５２】
ここで、HMM（連続HMM）は、状態遷移確率aij、出力確率密度関数bj(x)、及び初期確率πiによって定義される。これらの状態遷移確率aij、出力確率密度関数bj(x)、及び初期確率πiを、HMMのパラメータλ={aij,bj(x), πi,i=1,2,・・・,M，j=1,2,・・・,M}という。Mは、HMMの状態数を表す。
【００５３】
HMMのパラメータλを推定する方法としては、Baum-Welchの再尤推定法が広く利用されている。Baum-Welchの再尤推定法は、EMアルゴリズム(EM(Expectation-Maximization) algorithm)に基づくパラメータの推定方法である。
【００５４】
Baum-Welchの再尤推定法によれば、観測される時系列データx=x1,x2,・・・,xTに基づき、その時系列データが観測（生起）される確率である生起確率から求まる尤度を最大化するように、HMMのパラメータλの推定が行われる。ここで、xtは、時刻tに観測される信号（サンプル値）を表し、Tは、時系列データの長さ（サンプル数）を表す。
【００５５】
Baum-Welchの再尤推定法については、例えば、“パターン認識と機械学習（下）”，Ｃ．Ｍ．ビショップ著，P. 333（英語原書：“Pattern Recognition and Machine Learning (Information Science and Statistics) ”，Christopher M. BishopSpringer, New York, 2006.）（以下、文献Ａと称する）に記載されている。
【００５６】
なお、Baum-Welchの再尤推定法は、尤度最大化に基づくパラメータ推定方法ではあるが、最適性を保証するものではなく、HMMの構造やパラメータλの初期値によっては、局所解に収束することがある。
【００５７】
HMMは、音声認識で広く利用されているが、音声認識で利用されるHMMでは、一般に、状態の数や状態遷移の仕方等はあらかじめ決定される。
【００５８】
図５は、音声認識で利用されるHMMの例を示している。
【００５９】
図５のHMMは、left-to-right型と呼ばれる。
【００６０】
図５では、状態数は３になっており、状態遷移は、自己遷移（状態siから状態siへの状態遷移）と、左から右隣の状態への状態遷移とのみを許す構造に制約されている。
【００６１】
図５のHMMのように、状態遷移に制約があるHMMに対して、図４に示した、状態遷移に制約がないHMM、すなわち、任意の状態siから任意の状態sjへの状態遷移が可能なHMMは、エルゴディック(Ergodic)HMMと呼ばれる。
【００６２】
エルゴディックHMMは、構造としては最も自由度の高いHMMであるが、状態数が多くなると、パラメータλの推定が困難となる。
【００６３】
例えば、エルゴディックHMMの状態数が、１０００である場合、状態遷移の数は、１００万（＝１０００×１０００）となる。
【００６４】
したがって、この場合、パラメータλのうちの、例えば、状態遷移確率aijについては、１００万個の状態遷移確率aijを推定することが必要となる。
【００６５】
そこで、状態に対して設定する状態遷移には、例えば、スパース(Sparse)な構造であるという制約（スパース制約）をかけることができる。
【００６６】
ここで、スパースな構造とは、任意の状態から任意の状態への状態遷移が可能なエルゴディックHMMのような密な状態遷移ではなく、ある状態から状態遷移することができる状態が非常に限定されている構造である。なお、ここでは、スパースな構造であっても、他の状態への状態遷移は、少なくとも１つ存在し、また、自己遷移は存在することとする。
【００６７】
図６は、スパース制約を与えたHMMを示している。
【００６８】
ここで、図６では、２つの状態を結ぶ双方向の矢印は、その２つの状態の一方から他方への状態遷移と、他方から一方への状態遷移とを表す。また、図６において、各状態は、自己遷移が可能であり、その自己遷移を表す矢印の図示は、省略されている。
【００６９】
図６では、１６個の状態が、２次元空間上に格子状に配置されている。すなわち、図６では、横方向に、４個の状態が配置され、縦方向にも、４個の状態が配置されている。
【００７０】
いま、横方向に隣接する状態どうしの距離、及び、縦方向に隣接する状態どうしの距離を、いずれも１とすると、図６Ａは、距離が１以下の状態への状態遷移は可能とし、他の状態への状態遷移はできないというスパース制約を与えたHMMを示している。
【００７１】
また、図６Ｂは、距離が√２以下の状態への状態遷移は可能とし、他の状態への状態遷移はできないというスパース制約を与えたHMMを示している。
【００７２】
本実施の形態では、GPSセンサ１１が取得した位置データが、時系列データx=x1,x2,・・・,xTとして、時系列データ記憶部１２に供給される。行動学習部１３は、時系列データ記憶部１２に記憶されている時系列データx=x1,x2,・・・,xTを用い、ユーザ活動モデルを表すHMMのパラメータλを推定する。
【００７３】
即ち、ユーザの移動軌跡を表す各時刻の位置（緯度経度）のデータが、HMMの状態sjのいずれかに対応する地図上の一点から、所定の分散値の広がりを持って正規分布した確率変数の観測データであると考える。行動学習部１３は、各状態sjに対応する地図上の一点とその分散値、および状態遷移確率aijを最適化する。
【００７４】
なお、状態siの初期確率πiは、一様な値に設定することができる。例えば、M個の状態siそれぞれの初期確率πiが、1/Mに設定される。また、GPSセンサ１１が取得した位置データに対して補間処理などの所定の処理を施した後の位置データを、時系列データx=x1,x2,・・・,xTとして、時系列データ記憶部１２に供給してもよい。
【００７５】
行動認識部１４は、学習により得られたユーザ活動モデル（HMM）に対して、ビタビ法を適用し、GPSセンサ１１からの位置データx=x1,x2,・・・,xTが観測される尤度を最も大にする状態遷移の過程（状態の系列）（パス）（以下、最尤パスともいう）を求める。これにより、ユーザの現在の活動状態、即ち、ユーザの現在地に対応する状態siが認識される。
【００７６】
ここで、ビタビ法とは、各状態siを始点とする状態遷移のパスの中で、時刻tに、状態siから状態sjに状態遷移する状態遷移確率aijと、その状態遷移において、位置データx=x1,x2,・・・,xTのうちの時刻tのサンプル値xtが観測される確率（出力確率密度関数bj(x)から求められる出力確率）とを、処理後時系列データxの長さTに亘って累積した値（生起確率）を最大にするパス（最尤パス）を決定するアルゴリズムである。ビタビ法の詳細については上述の文献ＡのP.347に記載されている。
【００７７】
［行動予測部１５による経路の探索処理］
次に、行動予測部１５による経路の探索処理について説明する。
【００７８】
学習により得られたHMMの各状態siは、地図上の所定の点（位置）を表し、状態siと状態sjが結ばれているとき、状態siから状態sjを移動する経路を表していると考えることができる。
【００７９】
この場合、状態siに対応する各点は、端点、通過点、分岐点、ループのいずれかに分類することができる。端点とは、自己遷移以外の確率が極めて小さく（自己遷移以外の確率が所定の値以下であり）、次に移動可能な点がない点である。通過点とは、自己遷移以外に有意な遷移が一つある、換言すれば、次に移動可能な点が一つある点である。分岐点とは、自己遷移以外に有意な遷移が二つ以上ある、換言すれば、次に移動可能な点が二つ以上ある点である。ループとは、これまで通過した経路上のどれかと一致する点である。
【００８０】
目的地への経路を探索する場合、異なる経路がある場合には、それぞれの経路について必要時間等の情報を提示することが望まれる。そこで、可能な経路を過不足なく探索するために、次の条件を設定する。
（１）一度分岐した経路は再度合流した場合でも、別の経路とみなす。
（２）経路内に端点か、これまで通過した経路内に含まれる点が現れた場合、その経路の探索を終了する。
【００８１】
行動予測部１５は、行動認識部１４により認識されたユーザの現在の活動状態、即ち、ユーザの現在の点を出発点として、次の移動先としての状態遷移が可能な点を端点、通過点、分岐点、ループのいずれかに分類することを（２）の終了条件まで繰り返す。
【００８２】
行動予測部１５は、現在の点が端点であると分類された場合、現在の点をここまでの経路に接続してから、この経路の探索を終了する。
【００８３】
一方、現在の点が通過点であると分類された場合、行動予測部１５は、現在の点をここまでの経路に接続してから、次の点へ移動する。
【００８４】
また、現在の点が分岐点であると分類された場合、行動予測部１５は、現在の点をこれまでの経路に接続して、さらに分岐の数だけ、これまでの経路を複製し、分岐点と接続する。そして、行動予測部１５は、分岐点の１つを次の点として移動する。
【００８５】
現在の点がループであると分類された場合、行動予測部１５は、現在の点をこれまでの経路に接続せずに、この経路の探索を終了する。なお、現在の点から、１つ前の点に経路を逆戻りする場合はループに含まれるため考慮しない。
【００８６】
［探索処理の例］
図７は、行動予測部１５による経路の探索処理の簡単な例を示している。
【００８７】
図７の例において、状態s１が現在地である場合、最終的に３通りの経路が探索されることになる。１つめの経路は、状態s１から状態s５，状態s６等を経由して状態s１０までの経路（以下、経路Ａともいう。）である。２つめの経路は、状態s１から状態s５，状態s１１，状態s１４，状態s２３等を経由して状態s２９までの経路（以下、経路Ｂともいう。）である。３つめの経路は、状態s１から状態s５，状態s１１，状態s１９，状態s２３等を経由して状態s２９までの経路（以下、経路Ｃともいう。）である。
【００８８】
行動予測部１５は、探索された各経路が選択される確率（経路の選択確率）を計算する。経路の選択確率は、経路を構成する状態間の遷移確率を順次乗算することで求められる。ただし、次の状態に遷移する場合のみを考慮し、その場所に滞留する場合は考慮する必要がないので、学習により求められた各状態の状態遷移確率aijから、自己遷移確率を除いて規格化された遷移確率[aij]を用いて、経路の選択確率が求められる。
【００８９】
自己遷移確率を除いて規格化された遷移確率[aij]は、次式（１）で表すことができる。
【数１】
0005495014.tif 000002
ここで、δは、クロネッカー関数を表し、添え字のｉとｊが一致するときのみ１となり、それ以外は０となる関数である。
【００９０】
したがって、例えば、図７の状態s５の状態遷移確率aijが、自己遷移確率a５，５＝０．５，遷移確率a５，６＝０．２，遷移確率a５，１１＝０．３である場合、状態s５から状態s６または状態s１１に分岐する場合の遷移確率[a５，６]および遷移確率[a５，１１]は、それぞれ、０．４，０．６となる。
【００９１】
探索された経路の状態siのノード番号ｉが、（ｙ１，ｙ２，・・・，ｙｎ）であるとき、この経路の選択確率は、規格化された遷移確率[aij]を用いて、次式（２）で表すことができる。
【００９２】
【数２】
0005495014.tif 000003
【００９３】
実際には、通過点での規格化された遷移確率[aij]は１であるので、分岐する際の規格化された遷移確率[aij]を順次乗算すれば足りる。
【００９４】
図７の例では、経路Ａの選択確率は、０．４である。また、経路Ｂの選択確率は、０．２４＝０．６×０．４である。経路Ｃの選択確率は、０．３６＝０．６×０．６である。そして、計算された経路の選択確率の総和は１＝０．４＋０．２４＋０．３６であり、過不足ない探索を実現することができることがわかる。
【００９５】
以上のように、現在地に基づいて探索された各経路とその選択確率が、行動予測部１５から到達時間予測部１６に供給される。
【００９６】
到達時間予測部１６は、行動予測部１５によって探索された経路から、ユーザが指定した目的地を含む経路を抽出し、抽出された各経路について目的地までの時間を予測する。
【００９７】
例えば、図７の例では、探索された３つの経路Ａ乃至Ｃのうち、目的地である状態s２８を含む経路は経路Ｂと経路Ｃである。到達時間予測部１６は、経路Ｂまたは経路Ｃを通って、目的地である状態s２８に到達するまでの時間を予測する。
【００９８】
なお、目的地を含む経路が多数あり、全ての経路を表示すると見づらくなる場合や経路の提示数が所定数に設定されている場合には、目的地を含む全ての経路のなかから、表示部１８に表示させる経路（以下、適宜、表示経路ともいう。）を決定する必要がある。そのような場合、行動予測部１５では、各経路について選択確率が算出されているので、到達時間予測部１６は、選択確率の高い順に、所定数の経路を表示経路として決定することができる。
【００９９】
現在時刻ｔ１の現在地が状態ｓｙ１であり、時刻（ｔ１，ｔ２，・・・，ｔｇ）における決定された経路が（ｓｙ１，ｓｙ２，・・・，ｓｙｇ）であるとする。換言すれば、決定された経路の状態siのノード番号ｉが（ｙ１，ｙ２，・・・，ｙｇ）であるとする。以下、簡単のため、位置に相当する状態siを、単に、そのノード番号ｉで表わす場合もある。
【０１００】
現在時刻ｔ１での現在地ｙ１は、行動認識部１４の認識により確定しているので、現在時刻ｔ１の現在地がｙ１である確率Ｐｙ１（ｔ１）は、
Ｐｙ１（ｔ１）＝１
である。また、現在時刻ｔ１にｙ１以外の他の状態にいる確率は０である。
【０１０１】
一方、所定の時刻ｔｎにノード番号ｙｎにいる確率Ｐｙｎ（ｔｎ）は、
【数３】
0005495014.tif 000004
で表すことができる。式（３）の右辺第一項は、もともとその位置ｙｎにいて、自己遷移した場合の確率を表し、右辺第二項は、１つ前の位置ｙｎ−１から位置ｙｎに遷移してきた場合の確率を表している。式（３）では、経路の選択確率の計算とは異なり、学習により得られた状態遷移確率aijがそのまま利用される。
【０１０２】
目的地ｙｇへ到達するときの時刻ｔｇの予測値<ｔｇ>は、「その直前の時刻ｔｇ−１に目的地ｙｇの１つ前の位置ｙｇ−１にいて、時刻ｔｇに目的地ｙｇに移動する確率」を用いて、
【数４】
0005495014.tif 000005
と表すことができる。
【０１０３】
即ち、予測値<ｔｇ>は、現在時刻から、「その直前の時刻ｔｇ−１に状態ｓｙｇの１つ前の状態ｓｙｇ−１にいて、時刻ｔｇに状態ｓｙｇに移動するとき」までの時間の期待値で表される。
【０１０４】
［背景技術］の欄で提示した先願の方法により、目的地への到達時刻の予測値を求める場合、「所定時間後」の目的地に相当する状態の状態遷移確率aijを時間ｔに関して積分する必要があるが、この場合、積分区間をどれくらいに設定するのかが問題となる。先願の方法では、ループする経路を通って目的地に到達する場合を区別できない。そのため、目的地までの途中の経路にループが存在している場合、積分区間を長めに設定すると、ループを介して二度目、三度目に目的地に到達する場合も含まれるため、目的地までの到達時間を正しく算出することができない。
【０１０５】
式（４）で表される、本発明による目的地への到達時刻の予測値の演算では、同じく、時刻ｔについて積分（Σ）する必要はある。しかし、探索経路において、ループする経路を通って目的地に到達する場合が除外されているため、期待値の積分区間として十分長い区間を設定することが可能である。式（４）における積分区間は、例えば、学習した経路のなかで移動時間の最大の移動時間の１倍や２倍程度とすることができる。
【０１０６】
［ユーザ活動モデル学習処理］
次に、図８のフローチャートを参照して、ユーザの移動経路を、ユーザの活動状態を表す確率的状態遷移モデルとして学習するユーザ活動モデル学習処理について説明する。
【０１０７】
初めに、ステップＳ１において、GPSセンサ１１は、位置データを取得し、時系列データ記憶部１２に供給する。
【０１０８】
ステップＳ２において、時系列データ記憶部１２は、GPSセンサ１１により連続して取得された位置データ、すなわち、位置の時系列データを記憶する。
【０１０９】
ステップＳ３において、行動学習部１３は、時系列データ記憶部１２に記憶されている時系列データに基づいて、ユーザ活動モデルを確率的状態遷移モデルとして学習する。即ち、行動学習部１３は、時系列データ記憶部１２に記憶されている時系列データに基づいて、確率的状態遷移モデル（ユーザ活動モデル）のパラメータを算出する。
【０１１０】
ステップＳ４において、行動学習部１３は、ステップＳ３で算出された確率的状態遷移モデルのパラメータを、行動認識部１４および行動予測部１５に供給し、処理を終了する。
【０１１１】
［到達時間予測処理］
次に、図８のユーザ活動モデル学習処理により得られたユーザ活動モデルを表す確率的状態遷移モデルのパラメータを用いて、目的地までの経路を探索し、到達時間を算出してユーザに提示する到達時間予測処理について説明する。
【０１１２】
図９は、到達時間予測処理のフローチャートを示している。なお、この例では、図９の処理の前に、目的地が予め決められているものとするが、図９の処理の途中で目的地を入力するようにしてもよい。
【０１１３】
初めに、ステップＳ２１において、GPSセンサ１１は、位置の時系列データを取得し、行動認識部１４に供給する。行動認識部１４には、所定のサンプル数の位置の時系列データが一時的に記憶される。
【０１１４】
ステップＳ２２において、行動認識部１４は、学習により得られたパラメータに基づくユーザ活動モデルから、ユーザの現在の活動状態を認識する。即ち、行動認識部１４は、ユーザの現在地を認識する。そして、行動認識部１４は、ユーザの現在の状態ノードのノード番号を行動予測部１５に供給する。
【０１１５】
ステップＳ２３において、行動予測部１５は、現在探索している状態ノード（以下、適宜、現在の状態ノードともいう。）に対応する点が、端点、通過点、分岐点、またはループのいずれであるかを判定する。ステップS２２の処理直後は、ユーザの現在地に対応する状態ノードが現在の状態ノードとなる。
【０１１６】
ステップＳ２３で、現在の状態ノードに対応する点が端点であると判定された場合、処理はステップＳ２４に進み、行動予測部１５は、現在の状態ノードをここまでの経路に接続し、この経路の探索を終了し、ステップＳ３１に進む。なお、現在の状態ノードが現在地に対応する状態ノードである場合、ここまでの経路は存在しないため、接続する処理は行われない。ステップＳ２５，Ｓ２７、Ｓ３０でも同様である。
【０１１７】
ステップＳ２３で、現在の状態ノードに対応する点が通過点であると判定された場合、処理はステップＳ２５に進み、行動予測部１５は、現在の状態ノードをここまでの経路に接続する。そして、ステップＳ２６において、行動予測部１５は、次の状態ノードを現在の状態ノードとし、移動する。ステップＳ２６の処理後、処理はステップＳ２３に戻る。
【０１１８】
ステップＳ２３で、現在の状態ノードに対応する点が分岐点であると判定された場合、処理はステップＳ２７に進み、行動予測部１５は、現在の状態ノードをここまでの経路と接続する。そして、ステップＳ２８において、行動予測部１５は、ここまでの経路を分岐の数だけ複製し、分岐先の状態ノードと接続する。さらにステップＳ２９において、行動予測部１５は、複製した経路の１つを選択し、その選択した経路の先の状態ノードを現在の状態ノードとし移動する。ステップＳ２９の処理後、処理はステップＳ２３に戻る。
【０１１９】
一方、ステップＳ２３で、現在の状態ノードに対応する点がループであると判定された場合、処理はステップＳ３０に進み、行動予測部１５は、現在の状態ノードをここまでの経路と接続せずに、この経路の探索を終了し、ステップＳ３１に進む。
【０１２０】
ステップＳ３１において、行動予測部１５は、未探索の経路があるかを判定する。ステップＳ３１で、未探索の経路があると判定された場合、処理はステップＳ３２に進み、行動予測部１５は、現在地の状態ノードに戻り、未探索の経路の次の状態ノードを現在の状態ノードとし移動する。ステップＳ３２の処理後、処理はステップＳ２３に戻る。これにより、未探索の経路について、端点またはループにより探索が終了するまで経路の探索が実行される。
【０１２１】
ステップＳ３１で、未探索の経路がないと判定された場合、処理はステップＳ３３に進み、行動予測部１５は、探索された各経路の選択確率（生起確率）を計算する。行動予測部１５は、各経路と、その選択確率を到達時間予測部１６に供給する。
【０１２２】
ステップＳ３４において、到達時間予測部１６は、行動予測部１５によって探索された経路から、入力された目的地を含む経路を抽出し、目的地の到達確率を算出する。具体的には、到達時間予測部１６は、目的地に複数の経路が存在する場合、その複数の経路の選択確率の和を、目的地の到達確率として計算する。目的地への経路が１つしかない場合、経路の選択確率が、そのまま、目的地の到達確率とされる。
【０１２３】
ステップＳ３５において、到達時間予測部１６は、抽出された経路の数が提示数として予め設定された所定個数より多いかを判定する。
【０１２４】
ステップＳ３５で、抽出された経路の数が所定個数より多いと判定された場合、処理はステップＳ３６に進み、到達時間予測部１６は、表示部１８に表示する所定個数の経路を決定する。例えば、到達時間予測部１６は、選択される可能性の高い順に、所定個数の経路を決定することができる。
【０１２５】
一方、ステップＳ３５で、抽出された経路の数が所定個数以下であると判定された場合、ステップＳ３６の処理がスキップされる。即ち、この場合、目的地に到達するための全ての経路が表示部１８に表示される。
【０１２６】
ステップＳ３７において、到達時間予測部１６は、表示部１８に表示すると決定された各経路の到達時間を計算する。そして、到達時間予測部１６は、目的地の到達確率および目的地までの経路と到達時間を表示する画像の信号を表示部１８に供給する。
【０１２７】
ステップＳ３８において、表示部１８は、到達時間予測部１６から供給される画像の信号に基づいて、目的地の到達確率および目的地までの経路と到達時間を表示して、処理を終了する。
【０１２８】
以上のように、予測システム１の第１の実施の形態では、GPSセンサ１１により取得される位置の時系列データから、ユーザの活動状態を確率的状態遷移モデルとして学習する学習処理を行う。そして、予測システム１は、学習処理により得られたパラメータで表される確率的状態遷移モデルを用いて、入力された目的地の到達確率および目的地までの経路と到達時間を予測して、ユーザに提示する。
【０１２９】
したがって、予測システム１の第１の実施の形態によれば、ユーザが指定した目的地の到達確率および目的地までの経路とその到達時間を予測して、ユーザに提示することができる。
【０１３０】
＜２．第２の実施の形態＞
［予測システムの第２の実施の形態のブロック図］
図１０は、本発明を適用した予測システムの第２の実施の形態の構成例を示すブロック図である。なお、図１０において、上述した第１の実施の形態と対応する部分については同一の符号を付してあり、その説明は適宜省略する（その他の図についても同様）。
【０１３１】
図１０の予測システム１は、GPSセンサ１１、速度演算部５０、時系列データ記憶部５１、行動学習部５２、行動認識部５３、行動予測部５４、目的地予測部５５、操作部１７、および表示部１８により構成される。
【０１３２】
第１の実施の形態では、目的地はユーザが指定することとしたが、第２の実施の形態では、GPSセンサ１１により取得される位置の時系列データに基づいて、目的地も予測システム１が予測する。目的地は１つだけでなく、複数の目的地が予測されることもある。予測システム１は、予測した目的地について到達確率、経路、および到達時間を算出してユーザに提示する。
【０１３３】
目的地とされる自宅や勤務先、駅、買い物先、レストランなどでは、ユーザはその場所に所定時間滞在するのが一般的であり、ユーザの移動速度はほぼゼロに近い状態となる。一方、ユーザが目的地に移動している場合には、ユーザの移動速度は、移動手段に応じた特定のパターンで遷移する状態となる。従って、ユーザの移動速度の情報からユーザの行動状態、即ち、ユーザが目的地に滞在している状態（滞在状態）であるのか、または、移動している状態（移動状態）であるのかを認識し、滞在状態の場所を目的地として予測することができる。
【０１３４】
速度演算部５０は、GPSセンサ１１から一定時間間隔で供給される位置データから移動速度を演算する。
【０１３５】
具体的には、一定の時間間隔でｋステップ目（ｋ個目）に得られるときの位置データを、時刻ｔｋ、経度ｙｋ、緯度ｘｋと表すと、ｋステップ目のｘ方向の移動速度ｖｘｋおよびｙ方向の移動速度ｖｙｋは、次式（５）により計算することができる。
【０１３６】
【数５】
0005495014.tif 000006
【０１３７】
式（５）では、GPSセンサ１１から得られる緯度経度のデータをそのまま利用しているが、緯度経度を距離に変換したり、速度を時速や分速で表すように変換するなどの処理は、必要に応じて適宜行うことができる。
【０１３８】
また、速度演算部５０は、式（５）で得られる移動速度ｖｘｋおよびｖｙｋからさらに、式（６）で表されるｋステップ目の移動速度ｖｋと進行方向の変化θｋを求め、これを利用することができる。
【０１３９】
【数６】
0005495014.tif 000007
【０１４０】
式（６）で表される移動速度ｖｋと進行方向の変化θｋを利用する方が、式（５）の移動速度ｖｘｋおよびｖｙｋよりも以下の点で、特徴をうまく取り出すことができる。
【０１４１】
１．移動速度ｖｘｋおよびｖｙｋのデータの分布は、緯度経度軸に対して偏りが生じるため、同じ移動手段（電車や徒歩など）であっても角度が異なった場合に識別できない可能性があるが、移動速度ｖｋであればそのような可能性が少ない。
２．移動速度の絶対的な大きさ（｜ｖ｜）だけで学習すると、機器のノイズによって生じる｜ｖ｜のため、徒歩と滞在を区別できない。進行方向の変化も考慮することで、ノイズの影響を軽減することができる。
３．移動している場合は進行方向の変化が少ないが、滞在している場合は進行方向が定まらないので、進行方向の変化を使うと移動と滞在の識別がしやすい。
【０１４２】
以上の理由から、本実施の形態では、速度演算部５０は、移動速度のデータとして、式（６）で表される移動速度ｖｋと進行方向の変化θｋを求め、位置データとともに、時系列データ記憶部１２または行動認識部５３に供給する。
【０１４３】
また、速度演算部５０は、移動速度ｖｋと進行方向の変化θｋの演算を行う前に、ノイズ成分を除去するため、移動平均によるフィルタリング処理（前処理）を行う。
【０１４４】
なお、以下では、進行方向の変化θｋを、進行方向θｋと略記する。
【０１４５】
GPSセンサ１１のなかには、移動速度を出力できるものも存在する。そのようなGPSセンサ１１が採用されている場合、速度演算部５０を省略し、GPSセンサ１１が出力する移動速度をそのまま利用することができる。
【０１４６】
時系列データ記憶部５１は、速度演算部５０から供給される位置および移動速度の時系列データを記憶する。
【０１４７】
行動学習部５２は、時系列データ記憶部５１に記憶されている時系列データに基づいて、ユーザの移動軌跡と行動状態を確率的状態遷移モデルとして学習する。即ち、行動学習部５２は、ユーザの現在地を認識し、目的地と、その経路および到達時間を予測するためのユーザ活動モデルを確率的状態遷移モデルとして学習する。
【０１４８】
行動学習部５２は、学習処理により得られた確率的状態遷移モデルのパラメータを行動認識部５３、行動予測部５４、および目的地予測部５５に供給する。
【０１４９】
行動認識部５３は、学習により得られたパラメータの確率的状態遷移モデルを用いて、位置および移動速度の時系列データから、ユーザの現在地を認識する。行動認識部５３は、ユーザの現在の状態ノードのノード番号を行動予測部５４に供給する。
【０１５０】
行動予測部５４は、学習により得られたパラメータの確率的状態遷移モデルを用いて、ユーザの現在地から、ユーザが取りうる経路を過不足なく探索し、探索された経路ごとの選択確率を計算する。
【０１５１】
即ち、行動認識部５３および行動予測部５４は、移動速度の時系列データを加えることにより移動経路以外に行動状態をも学習したパラメータを使用する点以外は、第１の実施の形態の行動認識部１４および行動予測部１５と同様である。
【０１５２】
目的地予測部５５は、学習により得られたパラメータの確率的状態遷移モデルを用いて、ユーザの目的地を予測する。
【０１５３】
具体的には、目的地予測部５５は、最初に、目的地候補を列挙する。目的地予測部５５は、認識されるユーザの行動状態が滞在状態となる場所を目的地候補とする。
【０１５４】
そして、目的地予測部５５は、列挙した目的地候補のうち、行動予測部５４により探索された経路上にある目的地候補を目的地に決定する。
【０１５５】
次に、目的地予測部５５は、決定した目的地ごとの到達確率を算出する。
【０１５６】
目的地が多数検出された場合には、そのすべてについて表示部１８に表示すると見づらくなったり、行く可能性の少ない目的地まで表示することもあり得る。したがって、第１の実施の形態において、探索された経路を絞り込んだのと同様に、目的地についても、到達確率の高い所定個数の目的地や、到達確率が所定値以上の目的地のみを表示するように、表示対象の目的地を絞り込むことができる。なお、目的地と経路の表示個数は異なっていても構わない。
【０１５７】
表示対象の目的地が決定された場合、目的地予測部５５は、目的地までの経路の到達時間を計算し、表示部１８に表示させる。
【０１５８】
なお、目的地までの経路が多数存在する場合には、目的地予測部５５は、第１の実施の形態と同様に、選択確率に基づいて目的地への経路を所定個数に絞り込んだ上で、表示経路の到達時間のみを計算することができる。
【０１５９】
また、目的地までの経路が多数存在する場合、選択される可能性の高い順で表示経路を決定する以外に、到達時間の短い順や、目的地までの距離の短い順に、表示経路を決定することも可能である。到達時間の短い順に表示経路を決定する場合には、例えば、目的地予測部５５は、最初に、目的地までの経路の全てについて到達時間を計算し、計算された到達時間に基づいて、表示経路を決定する。目的地までの距離の短い順に表示経路を決定する場合には、例えば、目的地予測部５５は、最初に、目的地までの経路の全てについて、状態ノードに対応する緯度経度の情報に基づいて目的地までの距離を計算し、計算された距離に基づいて、表示経路を決定する。
【０１６０】
［行動学習部５２の第１の構成例］
図１１は、図１０の行動学習部５２の第１の構成例を示すブロック図である。
【０１６１】
行動学習部５２は、時系列データ記憶部５１（図１０）に記憶されている位置および移動速度の時系列データを用いて、ユーザの移動軌跡と行動状態を同時に学習する。
【０１６２】
行動学習部５２は、学習データ変換部６１と統合学習部６２により構成されている。
【０１６３】
学習データ変換部６１は、場所インデックス変換部７１と行動状態認識部７２により構成され、時系列データ記憶部５１から供給される位置および移動速度のデータを、場所インデックスと行動モードのデータに変換し、統合学習部６２に供給する。
【０１６４】
時系列データ記憶部５１から供給される位置の時系列データは、場所インデックス変換部７１に供給される。場所インデックス変換部７１は、図１の行動認識部１４と同様の構成を採用することができる。即ち、場所インデックス変換部７１は、学習により得られたパラメータに基づくユーザ活動モデルから、ユーザの現在地に対応する、ユーザの現在の活動状態を認識する。そして、場所インデックス変換部７１は、ユーザの現在の状態ノードのノード番号を、場所を示すインデックス（場所インデックス）として、統合学習部６２に供給する。
【０１６５】
場所インデックス変換部７１が採用するパラメータを学習する学習器には、図１の行動認識部１４の学習器である、図１の行動学習部１３の構成を採用することができる。
【０１６６】
時系列データ記憶部５１から供給される移動速度の時系列データは、行動状態認識部７２に供給される。行動状態認識部７２は、ユーザの行動状態を確率的状態遷移モデルとして学習して得られたパラメータを用いて、供給される移動速度に対応するユーザの行動状態を認識し、認識結果を行動モードとして統合学習部６２に供給する。行動状態認識部７２が認識するユーザの行動状態としては、少なくとも滞在状態と移動状態が存在する必要がある。本実施の形態では、図１４等を参照して後述するように、行動状態認識部７２は、移動状態を、さらに徒歩、自転車、車などの移動手段によって分類した行動モードを統合学習部６２に供給する。
【０１６７】
したがって、統合学習部６２には、地図上の位置に対応する場所インデックスをシンボルとする時系列離散データと、行動モードをシンボルとする時系列離散データとが、学習データ変換部６１から供給される。
【０１６８】
統合学習部６２は、場所インデックスをシンボルとする時系列離散データと、行動モードをシンボルとする時系列離散データとを用いて、ユーザの活動状態を確率的状態遷移モデルにより学習する。具体的には、統合学習部６２は、ユーザの活動状態を表すマルチストリームHMMのパラメータλを学習する。
【０１６９】
ここで、マルチストリームHMMは、通常のHMMと同様な遷移確率を有する状態ノードから、複数の異なる確率法則に従うデータが出力されるようなHMMである。マルチストリームHMMでは、パラメータλのうち、出力確率密度関数bj(x)が時系列データごとに別々に用意される。
【０１７０】
本実施の形態では、時系列データが、場所インデックスの時系列データと行動モードの時系列データの２つあるので、出力確率密度関数bj(x)が場所インデックスの時系列データに対応する出力確率密度関数b1j(x)と、行動モードの時系列データに対応する出力確率密度関数b2j(x)とが用意される。出力確率密度関数b1j(x)は、マルチストリームHMMの状態ノードがjであった場合に、地図上のインデックスがxとなる確率である。出力確率密度関数b2j(x)は、マルチストリームHMMの状態ノードがjであった場合に、行動モードがxとなる確率である。したがって、マルチストリームHMMでは、地図上のインデックスと行動モードが関連付けられた形でユーザの活動状態が学習（統合学習）される。
【０１７１】
より具体的には、統合学習部６２は、各状態ノードの出力する場所インデックスの確率（どの場所インデックスが出力されるかの確率）と、各状態ノードの出力する行動モードの確率（どの行動のモードが出力されるかの確率）を学習する。学習により得られた統合モデル（マルチストリームHMM）によれば、”滞在状態”の行動モードが確率的に出力されやすい状態ノードが求められる。そして、認識された状態ノードから、場所インデックスを求めることで、目的地候補の場所インデックスを認識することができる。さらに、目的地候補の場所インデックスが示す緯度経度分布から、目的地の位置を認識することができる。
【０１７２】
以上のように、観測される行動モードが“滞在状態”になる確率が高い状態ノードに対応する場所インデックスの示す位置がユーザの滞在場所であると推定される。そして、上述したように、“滞在状態”となる場所は多くの場合、目的地であるから、この滞在場所を目的地として推定することができる。
【０１７３】
統合学習部６２は、学習により得られた、ユーザの活動状態を表すマルチストリームHMMのパラメータλを、行動認識部５３、行動予測部５４、および目的地予測部５５に供給する。
【０１７４】
［行動学習部５２の第２の構成例］
図１２は、図１０の行動学習部５２の第２の構成例を示すブロック図である。
【０１７５】
図１２の行動学習部５２は、学習データ変換部６１’と統合学習部６２’により構成されている。
【０１７６】
学習データ変換部６１’は、図１１の学習データ変換部６１と同様の行動状態認識部７２のみを有している。学習データ変換部６１’では、時系列データ記憶部５１から供給される位置データは、そのまま統合学習部６２’に供給される。一方、時系列データ記憶部５１から供給される移動速度のデータは、行動状態認識部７２により行動モードに変換され、統合学習部６２’に供給される。
【０１７７】
図１１の行動学習部５２の第１の構成例では、位置データを場所インデックスに変換するため、統合学習部６２では、学習モデル（HMM）の尤度に、地図上で近い、遠いといった情報を反映できない。これに対して、図１２の行動学習部５２の第２の構成例では、位置データをそのまま統合学習部６２’に供給することにより、そのような距離の情報を学習モデル（HMM）の尤度に反映させることができる。
【０１７８】
また、第１の構成例では、場所インデックス変換部７１と行動状態認識部７２におけるユーザ活動モデル（HMM）の学習と、統合学習部６２におけるユーザ活動モデルの学習の２段階の学習が必要である。第２の構成例では、少なくとも場所インデックス変換部７１のユーザ活動モデルの学習は不要となるので、計算処理の負担が軽減される。
【０１７９】
一方で、第１の構成例では、インデックスに変換するので、変換前のデータは位置データに限らず、何であっても構わないが、第２の構成例では、位置データに限定されるので汎用性が低くなるともいえる。
【０１８０】
統合学習部６２’は、位置の時系列データと、行動モードをシンボルとする時系列離散データとを用いて、ユーザの活動状態を確率的状態遷移モデル（マルチストリームHMM）により学習する。具体的には、統合学習部６２’は、各状態ノードから出力される緯度経度の分布パラメータと、行動モードの確率を学習する。
【０１８１】
統合学習部６２’の学習により得られた統合モデル（マルチストリームHMM）によれば、”滞在状態”の行動モードが確率的に出力されやすい状態ノードが求められる。そして、求められた状態ノードから、緯度経度分布を求めることができる。さらに、緯度経度分布から、目的地の位置を求めることができる。
【０１８２】
以上のように、観測される行動モードが“滞在状態”になる確率が高い状態ノードに対応する緯度経度分布の示す場所が、ユーザの滞在場所であると推定される。そして、上述したように、“滞在状態”となる場所は多くの場合、目的地であるから、その滞在場所を目的地として推定することができる。
【０１８３】
次に、図１１および図１２の行動状態認識部７２で使用されるユーザ活動モデル（HMM）のパラメータを学習する学習器の構成例について説明する。以下では、行動状態認識部７２の学習器の構成例として、カテゴリHMMにより学習する学習器９１A（図１３）の例と、マルチストリームHMMにより学習する学習器９１B（図２０）の例を説明する。
【０１８４】
［行動状態認識部７２の学習器の第１の構成例］
図１３は、カテゴリHMMにより、行動状態認識部７２で使用されるユーザ活動モデルのパラメータを学習する学習器９１Aの構成例を示している。
【０１８５】
カテゴリHMMでは、学習する教師データが予めどのカテゴリ（クラス）に属するデータであるのかが既知であり、カテゴリごとにHMMのパラメータが学習される。
【０１８６】
学習器９１Aは、移動速度データ記憶部１０１、行動状態ラベリング部１０２、および行動状態学習部１０３により構成される。
【０１８７】
移動速度データ記憶部１０１は、時系列データ記憶部５１（図１０）から供給される移動速度の時系列データを記憶する。
【０１８８】
行動状態ラベリング部１０２は、移動速度データ記憶部１０１から時系列に順次供給される移動速度のデータに対し、ユーザの行動状態をラベル（カテゴリ）として付与する。行動状態ラベリング部１０２は、移動速度のデータに行動状態が対応付けられたラベル済み移動速度データを行動状態学習部１０３に供給する。例えば、ｋステップ目の移動速度ｖｋと進行方向θｋに対して、行動状態を表すラベルMを付与したデータが行動状態学習部１０３に供給される。
【０１８９】
行動状態学習部１０３は、行動状態ラベリング部１０２から供給されるラベル済み移動速度データを、カテゴリごとに分類し、カテゴリ単位で、ユーザ活動モデル（HMM）のパラメータを学習する。学習の結果得られたカテゴリ毎のパラメータは、図１０または図１１の行動状態認識部７２に供給される。
【０１９０】
［行動状態の分類例］
図１４は、行動状態をカテゴリごとに分類する場合の分類例を示している。
【０１９１】
図１４に示されるように、まず、ユーザの行動状態は、滞在状態と移動状態に分類することができる。本実施の形態では、行動状態認識部７２が認識するユーザの行動状態としては、上述したように、少なくとも滞在状態と移動状態が存在する必要があるので、この２つに分類することは必須である。
【０１９２】
さらに、移動状態は、移動手段によって、電車、車（バスなども含む）、自転車、徒歩に分類することができる。電車は、さらに、特急、快速、ローカルなどに分類することができ、車は、さらに、高速、一般道などに分類することができる。また、徒歩は、走る、普通、散歩などに分類することができる。
【０１９３】
本実施の形態では、ユーザの行動状態を、図１４において斜線で示される“滞在”、“電車（快速）”、“電車（ローカル）”、“車（高速）”、“車（一般道）”、“自転車”、および“徒歩”に分類することとする。なお、“電車（特急）”は、学習データが得られなかったため省略した。
【０１９４】
カテゴリの分類の仕方が図１４に示した例に限定されるものではないことは言うまでもない。また、移動手段による移動速度の変化はユーザによって大きく異なるものではないので、学習データとしての移動速度の時系列データは、認識対象のユーザのものである必要はない。
【０１９５】
［行動状態ラベリング部１０２の処理例］
次に、図１５および図１６を参照して、行動状態ラベリング部１０２の処理例について説明する。
【０１９６】
図１５は、行動状態ラベリング部１０２に供給される移動速度の時系列データの例を示している。
【０１９７】
図１５では、行動状態ラベリング部１０２から供給される移動速度のデータ（ｖ，θ）を、（ｔ，ｖ）および（ｔ，θ）の形で示している。図１５において、四角（■）のプロットは移動速度ｖを表し、丸（●）のプロットは進行方向θを表している。また、横軸は時間ｔを表し、右側の縦軸は進行方向θを、左側の縦軸は移動速度ｖを表す。
【０１９８】
図１５の時間軸の下方に示されている“電車（ローカル）”、“徒歩”、“滞在”の文字は、説明のため付加したものである。図１５の時系列データの最初は、ユーザが電車（ローカル）で移動中である場合の移動速度のデータであり、次が“徒歩”で移動中である場合、その次が“滞在”である場合の移動速度のデータとなっている。
【０１９９】
ユーザが“電車（ローカル）”で移動している場合、電車が駅で停車し、出発するとき加速し、再度減速して駅に停車することを繰り返すので、移動速度ｖのプロットが繰り返し上下に振れるという特徴が表れている。なお、電車が停止している場合でも移動速度が０になっていないのは、移動平均によるフィルタリング処理を行っているためである。
【０２００】
また、ユーザが“徒歩”で移動している場合と“滞在”している場合は、最も区別しにくい状態であるが、移動平均によるフィルタリング処理により、移動速度ｖに明らかな違いが見られる。また、“滞在”では、進行方向θが瞬時に大きく変化する特徴がみられ、“徒歩”との差別化が容易であることがわかる。このように、移動平均によるフィルタリング処理、および、ユーザの移動を移動速度ｖと進行方向θで表すことにより、“徒歩”と“滞在”の区別が容易になっていることがわかる。
【０２０１】
なお、“電車（ローカル）”と“徒歩”の間の部分は、フィルタリング処理のため、行動の切り替わり点がはっきりしない部分である。
【０２０２】
図１６は、図１５に示した時系列データに対して、ラベル付けを行う例を示している。
【０２０３】
例えば、行動状態ラベリング部１０２は、図１５に示した移動速度のデータをディスプレイに表示する。そして、ユーザは、ディスプレイに表示された移動速度のデータのうち、ラベル付けをしたい部分を矩形の領域で囲む操作を、マウスなどにより行う。また、ユーザは、指定したデータに対して付与するラベルをキーボードなどから入力する。行動状態ラベリング部１０２は、ユーザによって指定された矩形領域に含まれる移動速度のデータに、入力されたラベルを付与することにより、ラベル付けを行う。
【０２０４】
図１６では、“徒歩”に相当する部分の移動速度のデータを矩形の領域で指示した例が示されている。なお、このとき、フィルタリング処理のため、行動の切り替わり点がはっきりしない部分については、指示する領域に含めないようにすることができる。時系列データの長さは、行動の違いが時系列データに明確に出る長さから決める。例えば、２０ステップ（１５秒×２０ステップ＝３００秒）程度とすることができる。
【０２０５】
［行動状態学習部１０３の構成例］
図１７は、図１３の行動状態学習部１０３の構成例を示すブロック図である。
【０２０６】
行動状態学習部１０３は、分類部１２１とHMM学習部１２２１乃至１２２７により構成される。
【０２０７】
分類部１２１は、行動状態ラベリング部１０２から供給されるラベル済み移動速度データのラベルを参照し、ラベルに対応するHMM学習部１２２１乃至１２２７のいずれかに供給する。即ち、行動状態学習部１０３では、ラベル（カテゴリ）ごとにHMM学習部１２２が用意されており、行動状態ラベリング部１０２から供給されるラベル済み移動速度データが、ラベルごとに分類されて、供給される。
【０２０８】
HMM学習部１２２１乃至１２２７それぞれは、供給されるラベル済み移動速度データを用いて、学習モデル（HMM）を学習する。そして、HMM学習部１２２１乃至１２２７それぞれは、学習により得られるHMMのパラメータλを、図１０または図１１の行動状態認識部７２に供給する。
【０２０９】
HMM学習部１２２１は、ラベルが“滞在”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２２は、ラベルが“徒歩”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２３は、ラベルが“自転車”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２４は、ラベルが“電車（ローカル）”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２５は、ラベルが“車（一般道）”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２６は、ラベルが“電車（快速）”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２７は、ラベルが“車（高速）”である場合の、学習モデル（HMM）を学習する。
【０２１０】
［学習結果の例］
図１８は、行動状態学習部１０３による学習結果の一部を示している。
【０２１１】
図１８Aは、HMM学習部１２２１の学習結果、すなわち、ラベルが“滞在”である場合の学習結果を示している。図１８Bは、HMM学習部１２２２の学習結果、すなわち、ラベルが“徒歩”である場合の学習結果を示している。
【０２１２】
図１８Cは、HMM学習部１２２３の学習結果、すなわち、ラベルが“自転車”である場合の学習結果を示している。図１８Dは、HMM学習部１２２４の学習結果、すなわち、ラベルが“電車（ローカル）”である場合の学習結果を示している。
【０２１３】
図１８A乃至図１８Dにおいて、横軸は移動速度ｖを、縦軸は進行方向θを表し、グラフ上の各点は、供給された学習データをプロットしたものである。また、グラフ上の楕円は、学習により得られた状態ノードを表し、それぞれの混合正規確率分布の分布密度は同一である。従って、大きい楕円で示される状態ノードの分散は大きくなっている。
【０２１４】
図１８Aに示される、ラベルが“滞在”である場合の移動速度のデータは、移動速度ｖは０付近に集中し、進行方向θは全範囲に広がって、そのばらつきは大きい。
【０２１５】
一方、図１８B乃至図１８Dに示される、ラベルが“徒歩”、“自転車”、“電車（ローカル）”である場合には、進行方向θのばらつきは小さい。従って、進行方向θのばらつきに注目すると、滞在状態と移動状態の大分類が可能であることがわかる。
【０２１６】
また、移動状態のなかの“徒歩”、“自転車”、および“電車（ローカル）”では、移動速度ｖが異なり、その特徴がグラフでも示されている。“徒歩”と“自転車”は、一定速度で走ることが多く、“電車（ローカル）”は、速度の変化が大きいので、速度方向に関するばらつきが大きい。
【０２１７】
図１８A乃至図１８Dにおいて学習結果として示される楕円は、上記のような各カテゴリのプロットの特徴を捉えた形状を示しており、各行動状態が的確に学習されていると言える。
【０２１８】
［行動状態認識部７２の第１の構成例］
図１９は、学習器９１Aで学習されたパラメータを利用する場合の行動状態認識部７２である、行動状態認識部７２Aの構成例を示すブロック図である。
【０２１９】
行動状態認識部７２Aは、尤度計算部１４１１乃至１４１７と尤度比較部１４２とにより構成されている。
【０２２０】
尤度計算部１４１１は、HMM学習部１２２１の学習により得られたパラメータを用いて、時系列データ記憶部５１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１１は、行動状態が“滞在”である尤度を計算する。
【０２２１】
尤度計算部１４１２は、HMM学習部１２２２の学習により得られたパラメータを用いて、時系列データ記憶部５１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１２は、行動状態が“徒歩”である尤度を計算する。
【０２２２】
尤度計算部１４１３は、HMM学習部１２２３の学習により得られたパラメータを用いて、時系列データ記憶部５１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１３は、行動状態が“自転車”である尤度を計算する。
【０２２３】
尤度計算部１４１４は、HMM学習部１２２４の学習により得られたパラメータを用いて、時系列データ記憶部５１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１４は、行動状態が“電車（ローカル）”である尤度を計算する。
【０２２４】
尤度計算部１４１５は、HMM学習部１２２５の学習により得られたパラメータを用いて、時系列データ記憶部５１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１５は、行動状態が“車（一般道）”である尤度を計算する。
【０２２５】
尤度計算部１４１６は、HMM学習部１２２６の学習により得られたパラメータを用いて、時系列データ記憶部５１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１６は、行動状態が“電車（快速）”である尤度を計算する。
【０２２６】
尤度計算部１４１７は、HMM学習部１２２７の学習により得られたパラメータを用いて、時系列データ記憶部５１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１７は、行動状態が“車（高速）”である尤度を計算する。
【０２２７】
尤度比較部１４２は、尤度計算部１４１１乃至１４１７それぞれから供給される尤度を比較し、尤度の最も高い行動状態を選択し、行動モードとして出力する。
【０２２８】
［行動状態認識部７２の学習器の第２の構成例］
図２０は、マルチストリームHMMにより、行動状態認識部７２で使用されるユーザ活動モデルのパラメータを学習する学習器９１Bの構成例を示している。
【０２２９】
学習器９１Aは、移動速度データ記憶部１０１、行動状態ラベリング部１６１、および行動状態学習部１６２により構成される。
【０２３０】
行動状態ラベリング部１６１は、移動速度データ記憶部１０１から時系列に順次供給される移動速度のデータに対し、ユーザの行動状態をラベル（行動モード）として付与する。行動状態ラベリング部１６１は、移動速度の時系列データ（ｖ，θ）と、それと関連付けられた行動モードMの時系列データを行動状態学習部１６２に供給する。
【０２３１】
行動状態学習部１６２は、マルチストリームHMMにより、ユーザの行動状態を学習する。マルチストリームHMMでは、異なる種類の時系列データ（ストリーム）を関連付けながら学習することができる。行動状態学習部１６２には、連続量である移動速度ｖと進行方向θの時系列データと、離散量である行動モードMの時系列データが供給される。行動状態学習部１６２は、各状態ノードから出力される移動速度の分布パラメータと、行動モードの確率を学習する。学習により得られたマルチストリームHMMによれば、例えば、移動速度の時系列データから、現在の状態ノードが求められる。そして、求められた状態ノードから、行動モードを認識することができる。
【０２３２】
カテゴリHMMを用いた第１の構成例では、HMMをカテゴリごとに７個用意する必要があるが、マルチストリームHMMでは１個のHMMで十分である。ただし、状態ノードの数は、第１の構成例において７個のカテゴリで使用された状態ノードの総数と同程度用意する必要がある。
【０２３３】
［行動状態ラベリング部１６１の処理例］
図２１を参照して、行動状態ラベリング部１６１の処理例について説明する。
【０２３４】
上述した第１の構成例における行動状態ラベリング部１０２によるラベル付けの方法では、移動手段の遷移の情報は失われる。したがって、移動手段の遷移にあまり起こりえないものが生じる場合がある。行動状態ラベリング部１６１では、移動手段の遷移の情報を失わずに、移動速度のデータに対し、ユーザの行動状態のラベルを付与する。
【０２３５】
具体的には、ユーザは、移動速度ではなく、場所（位置）を見れば、その場所でどのような行動をしていたかを把握しやすい。そこで、行動状態ラベリング部１６１は、移動速度の時系列データに対応する位置データをユーザに示し、位置に対してラベルを付与させることで、移動速度の時系列データに、行動状態をラベル付けする。
【０２３６】
図２１の例では、移動速度の時系列データに対応する位置データが、横軸を経度、縦軸を緯度とする地図上に表示されている。ユーザは、所定の行動状態に対応する場所を矩形の領域で囲む操作を、マウスなどにより行う。また、ユーザは、指定した領域に対して付与するラベルをキーボードなどから入力する。行動状態ラベリング部１６１は、矩形の領域で囲まれた領域内にプロットされている位置に対応する移動速度の時系列データに、入力されたラベルを付与することにより、ラベル付けを行う。
【０２３７】
図２１では、“電車（ローカル）”および“自転車”に相当する部分を矩形の領域で指示した例が示されている。
【０２３８】
なお、図２１では、入力される時系列データの全てが表示されているが、データ数が多い場合には、例えば、２０ステップずつ表示することとし、表示されたデータに対するラベル付けを順次繰り返すような方法でもよい。また、ユーザ自身が過去のデータを振り返って日記のようにラベリングするアプリケーションなどを用意してもよい。即ち、ラベル付けの方法は特に限定されない。また、ラベル付けをするのは、データを作成した本人である必要はない。
【０２３９】
［学習結果の例］
図２２は、行動状態学習部１６２による学習結果を示している。
【０２４０】
図２２において、横軸は進行方向θを、縦軸は移動速度ｖを表し、グラフ上の各点は、供給された学習データをプロットしたものである。また、グラフ上の楕円は、学習により得られた状態ノードを表し、それぞれの混合正規確率分布の分布密度は同一である。従って、大きい楕円で示される状態ノードの分散は大きくなっている。図２２の状態ノードは、移動速度に対応する。行動モードについての情報は、図２２では図示されていないが、各状態ノードに、それぞれの行動ノードの観測確率が付随して学習されている。
【０２４１】
［行動状態認識部７２の第２の構成例］
図２３は、学習器９１Bで学習されたパラメータを利用する場合の行動状態認識部７２である、行動状態認識部７２Bの構成例を示すブロック図である。
【０２４２】
行動状態認識部７２Bは、状態ノード認識部１８１と行動モード認識部１８２により構成される。
【０２４３】
状態ノード認識部１８１は、学習器９１Bで学習されたマルチストリームHMMのパラメータを用いて、時系列データ記憶部５１から供給される移動速度の時系列データから、マルチストリームHMMの状態ノードを認識する。状態ノード認識部１８１は、認識された現在の状態ノードのノード番号を行動モード認識部１８２に供給する。
【０２４４】
行動モード認識部１８２は、状態ノード認識部１８１で認識された状態ノードで、最も確率の高い行動モードを、現在の行動モードとして認識し、出力する。
【０２４５】
なお、上述した例では、場所インデックス変換部７１と行動状態認識部７２において、HMMによりモデル化することで、時系列データ記憶部５１から供給される位置および移動速度のデータを、場所インデックスと行動モードのデータに変換するようにした。
【０２４６】
しかし、これ以外の方法によって、位置および移動速度のデータを、場所インデックスと行動モードのデータに変換するようにしてもよい。例えば、行動モードについては、GPSセンサ１１とは別に、加速度センサやジャイロセンサ等のモーションセンサを用いて、加速度等の検出結果から、ユーザの移動の有無を検出し、行動モードを判定するようにしてもよい。
【０２４７】
［目的地到達時間予測処理］
次に、図２４および図２５のフローチャートを参照して、図１０の予測システム１による目的地到達時間予測処理について説明する。
【０２４８】
即ち、図２４および図２５は、位置および移動速度の時系列データから、目的地を予測し、かつ、目的地までの経路および到達時間を算出してユーザに提示する目的地到達時間予測処理のフローチャートである。
【０２４９】
図２４のステップS５１乃至ステップＳ６３の処理は、ステップＳ５１で取得する時系列データが、位置と移動速度のデータである以外は、図９に示した到達時間予測処理のステップＳ２１乃至Ｓ３３と同様であるので、その説明は省略する。
【０２５０】
図２４のステップS５１乃至ステップＳ６３の処理により、ユーザの現在地が認識され、そこからユーザが取りうる経路が過不足なく探索され、各経路の選択確率が計算された後、処理は、図２５のステップＳ６４に進む。
【０２５１】
ステップＳ６４において、目的地予測部５５は、ユーザの目的地を予測する。具体的には、目的地予測部５５は、最初に、目的地候補を列挙する。目的地予測部５５は、ユーザの行動状態が滞在状態となる場所を目的地候補とする。そして、目的地予測部５５は、列挙した目的地候補のうち、行動予測部５４により探索された経路上にある目的地候補を目的地に決定する。
【０２５２】
ステップＳ６５において、目的地予測部５５は、目的地ごとの到達確率を計算する。即ち、目的地予測部５５は、複数の経路が存在する目的地については、その複数の経路の選択確率の和を、目的地の到達確率として計算する。１つの経路しかない目的地については、経路の選択確率が、そのまま、目的地の到達確率とされる。
【０２５３】
ステップＳ６６で、目的地予測部５５は、予測された目的地の数が所定個数より多いかを判定する。ステップＳ６６で、予測された目的地の数が所定個数より多いと判定された場合、処理はステップＳ６７に進み、目的地予測部５５は、表示部１８に表示する所定個数の目的地を決定する。例えば、目的地予測部５５は、目的地の到達確率の高い順に、所定個数の目的地を決定することができる。
【０２５４】
一方、ステップＳ６６で、予測された目的地の数が所定個数以下であると判定された場合、ステップＳ６７はスキップされる。即ち、この場合、予測された目的地のすべてが表示部１８に表示される。
【０２５５】
ステップＳ６８において、目的地予測部５５は、行動予測部５４によって探索された経路から、予測された目的地を含む経路を抽出する。複数の目的地が予測されている場合には、予測された目的地それぞれについて、経路が抽出される。
【０２５６】
ステップＳ６９において、目的地予測部５５は、抽出された経路の数が提示数として予め設定された所定個数より多いかを判定する。
【０２５７】
ステップＳ６９で、抽出された経路の数が所定個数より多いと判定された場合、処理はステップＳ７０に進み、目的地予測部５５は、表示部１８に表示する所定個数の経路を決定する。例えば、目的地予測部５５は、選択される可能性の高い順に、所定個数の経路を決定することができる。
【０２５８】
一方、ステップＳ６９で、抽出された経路の数が所定個数以下であると判定された場合、ステップＳ７０の処理がスキップされる。即ち、この場合、目的地に到達するための全ての経路が表示部１８に表示される。
【０２５９】
ステップＳ７１において、目的地予測部５５は、表示部１８に表示すると決定された各経路の到達時間を計算し、目的地の到達確率および目的地までの経路と到達時間を表示する画像の信号を表示部１８に供給する。
【０２６０】
ステップＳ７２において、表示部１８は、目的地予測部５５から供給される画像の信号に基づいて、目的地の到達確率および目的地までの経路と到達時間を表示して、処理を終了する。
【０２６１】
以上のように、図１０の予測システム１によれば、位置および移動速度の時系列データから、目的地を予測し、かつ、目的地の到達確率および目的地までの経路と到達時間を算出してユーザに提示することができる。
【０２６２】
［図１０の予測システム１の処理結果例］
図２６乃至図２９は、図１０の予測システム１による学習および目的地到達時間予測の処理を検証した検証実験の結果例を示している。なお、予測システム１の学習処理の学習データは、図３に示したデータが利用されている。
【０２６３】
図２６は、図１１の場所インデックス変換部７１に入力されるパラメータの学習結果を示している。
【０２６４】
この検証実験では、状態ノードの数を４００個で演算した。図２６において、状態ノードを示す楕円付近に付された数字は、状態ノードのノード番号を示している。図２６に示される学習されたマルチストリームHMMによれば、ユーザの移動経路を覆うように状態ノードが学習されている。即ち、ユーザの移動経路が的確に学習されていることがわかる。この状態ノードのノード番号が、場所インデックスとして統合学習部６２に入力される。
【０２６５】
図２７は、図１１の行動状態認識部７２に入力されるパラメータの学習結果を示している。
【０２６６】
図２７では、行動モードが“滞在”であると認識された点（位置）が、黒でプロットされている。また、行動モードが“滞在”以外（“徒歩”、“電車（ローカル）”など）であると認識された点が、灰色でプロットされている。
【０２６７】
また、図２７では、実際に学習データを作成した実験者が滞在場所としてリストアップした位置に、丸（○）が付されている。丸付近に記された番号は、単に、滞在場所を区別するために付した序数である。
【０２６８】
図２７によれば、学習により決定された滞在状態を示す位置と、実験者が滞在場所としてリストアップした位置は一致しており、ユーザの行動状態（行動モード）が的確に学習されていることがわかる。
【０２６９】
図２８は、統合学習部６２の学習結果を示している。
【０２７０】
図２８では、図面の制約上、その区別が現われていないが、学習により得られたマルチストリームHMMの各状態ノードのうち、“滞在”の観測確率が５０％以上となっている状態ノードについて調べると、図２７に示した位置と一致する。
【０２７１】
図２９は、統合学習部６２が学習した学習モデル（マルチストリームHMM）により、図２４および図２５の目的地到達時間予測処理を実行した結果を示している。
【０２７２】
図２９に示される処理結果によれば、現在地に対して、図３に示した外出先１乃至４が、それぞれ、目的地１乃至４として予測され、各目的地までの到達確率と到達時間が算出されている。
【０２７３】
目的地１の到達確率は５０％で、到達時間は３５分である。目的地２の到達確率は２０％で、到達時間は１０分である。目的地３の到達確率は２０％で、到達時間は２５分である。目的地４の到達確率は１０％で、到達時間は１８．２分である。また、目的地１乃至４それぞれまでの経路が太線の実線で示されている。
【０２７４】
したがって、図１０の予測システム１によれば、ユーザの現在地から目的地を予測し、その予測した目的地までの経路とその到達時間をさらに予測して、ユーザに提示することができる。
【０２７５】
なお、上述した例では、目的地をユーザの行動状態から予測するようにしたが、目的地の予測はこれに限定されない。例えば、ユーザが目的地として過去に入力した場所から目的地を予測するようにしてもよい。
【０２７６】
図１０の予測システム１は、このような予測結果から、さらに、到達確率の最も高い目的地についての情報を表示部１８に表示させるようにすることなども可能である。例えば、目的地が駅などである場合には、その駅の時刻表を表示させたり、目的地が店舗である場合には、店舗の詳細情報（営業時間やセール情報など）を表示させることができる。これにより、ユーザの利便性がさらに向上する。
【０２７７】
また、図１０の予測システム１には、時系列データとして、ユーザの行動を作用するその他の条件を時系列化して入力することで、行動の条件付き予測を行わせることもできる。例えば、曜日（平日休日）などの条件を入力して学習することで、曜日毎に行動（目的地）が異なる場合の目的地の予測を行うことができる。また、時間帯（または午前、午後、夜間）などの条件を入力して学習することで、時間帯別に行動が異なる場合の目的地の予測を行うことができる。さらに、天気（晴れ曇り雨）などの条件を入力して学習することで、天気によって異なる目的地を予測することができる。
【０２７８】
なお、上述した実施の形態では、行動状態認識部７２が、行動モードを統合学習部６２または６２’へ入力するため、移動速度から行動モードに変換する変換手段として設けられている。しかしながら、行動状態認識部７２を、入力される移動速度に対して、ユーザが移動状態かまたは滞在状態か、さらに移動状態である場合には何の移動手段で移動しているか等を識別して出力する行動状態識別装置として、それ単独で用いることも可能である。この場合、行動状態認識部７２の出力を、異なるアプリケーションへ入力することもできる。
【０２７９】
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【０２８０】
図３０は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【０２８１】
コンピュータにおいて、CPU（Central Processing Unit）２０１，ROM（Read Only Memory）２０２，RAM（Random Access Memory）２０３は、バス２０４により相互に接続されている。
【０２８２】
バス２０４には、さらに、入出力インタフェース２０５が接続されている。入出力インタフェース２０５には、入力部２０６、出力部２０７、記憶部２０８、通信部２０９、ドライブ２１０、およびGPSセンサ２１１が接続されている。
【０２８３】
入力部２０６は、キーボード、マウス、マイクロホンなどよりなる。出力部２０７は、ディスプレイ、スピーカなどよりなる。記憶部２０８は、ハードディスクや不揮発性のメモリなどよりなる。通信部２０９は、ネットワークインタフェースなどよりなる。ドライブ２１０は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブル記録媒体２１２を駆動する。GPSセンサ２１１は、図１のGPSセンサ１１に対応する。
【０２８４】
以上のように構成されるコンピュータでは、CPU２０１が、例えば、記憶部２０８に記憶されているプログラムを、入出力インタフェース２０５及びバス２０４を介して、RAM２０３にロードして実行することにより、上述した一連の処理が行われる。
【０２８５】
コンピュータ（CPU２０１）が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブル記録媒体２１２に記録して提供することができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することができる。
【０２８６】
コンピュータでは、プログラムは、リムーバブル記録媒体２１２をドライブ２１０に装着することにより、入出力インタフェース２０５を介して、記憶部２０８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部２０９で受信し、記憶部２０８にインストールすることができる。その他、プログラムは、ROM２０２や記憶部２０８に、あらかじめインストールしておくことができる。
【０２８７】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０２８８】
なお、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる場合はもちろん、必ずしも時系列的に処理されなくとも、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで実行されてもよい。
【０２８９】
なお、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０２９０】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０２９１】
１  予測システム，  １３  行動学習部，  １４  行動認識部，  １５  行動予測部，  １６  到達時間予測部，  ５２  行動学習部，  ５３  行動認識部，  ５４  行動予測部，  ５５  目的地予測部，  ６１，６１’  学習データ変換部，  ６２，６２’  統合学習部，  ７１  場所インデックス変換部，  ７２  行動状態認識部，  ９１A，９１B  学習器，  １０２  行動状態ラベリング部，  １０３  行動状態学習部，  １２１  分類部，  １２２１乃至１２２７  HMM学習部，  １４１１乃至１４１７  尤度計算部，  １４２  尤度比較部，  １６１  行動状態ラベリング部，  １６２  行動状態学習部，  １８１  状態ノード認識部，  １８２  行動ノード認識部
【図１】
0005495014.tif 000008
【図２】
0005495014.tif 000009
【図３】
0005495014.tif 000010
【図４】
0005495014.tif 000011
【図５】
0005495014.tif 000012
【図６】
0005495014.tif 000013
【図７】
0005495014.tif 000014
【図８】
0005495014.tif 000015
【図９】
0005495014.tif 000016
【図１０】
0005495014.tif 000017
【図１１】
0005495014.tif 000018
【図１２】
0005495014.tif 000019
【図１３】
0005495014.tif 000020
【図１４】
0005495014.tif 000021
【図１５】
0005495014.tif 000022
【図１６】
0005495014.tif 000023
【図１７】
0005495014.tif 000024
【図１８】
0005495014.tif 000025
【図１９】
0005495014.tif 000026
【図２０】
0005495014.tif 000027
【図２１】
0005495014.tif 000028
【図２２】
0005495014.tif 000029
【図２３】
0005495014.tif 000030
【図２４】
0005495014.tif 000031
【図２５】
0005495014.tif 000032
【図２６】
0005495014.tif 000033
【図２７】
0005495014.tif 000034
【図２８】
0005495014.tif 000035
【図２９】
0005495014.tif 000036
【図３０】
0005495014.tif 000037