(57)【要約】【課題】現時刻以降の将来の経路および経過時間を、より正確に予測することができるようにする。【解決手段】マルチストリーム入力行動学習部１１３は、位置の時系列データと、時刻の時系列データとに基づいて、ユーザの活動状態を確率的状態遷移モデルにより学習する。確率的状態遷移モデルとしては、例えば、マルチストリームHMMが採用される。行動認識部１４は、学習により得られたユーザ活動モデルを用いて、ユーザの現在地に対応する、ユーザの現在の活動状態を認識する。本発明は、例えば、確率的状態遷移モデルを用いた学習装置および予測装置に適用できる。【選択図】図１５
2011118777.tif 000002
【特許請求の範囲】
【請求項１】
ユーザの位置の時系列データを取得する位置取得手段と、
時刻の時系列データを取得する時刻取得手段と、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、前記ユーザの活動状態を表す活動モデルを、確率的状態遷移モデルとして学習する学習手段と
を備える学習装置。
【請求項２】
曜日の時系列データを取得する曜日取得手段をさらに備え、
前記学習手段は、前記曜日の時系列データをさらに入力として加え、前記ユーザの活動状態を表す活動モデルを学習する
請求項１に記載の学習装置。
【請求項３】
交通状況の時系列データを取得する交通状況取得手段か、または、
気象状況の時系列データを取得する気象状況取得手段の少なくとも一方をさらに備え、
前記学習手段は、前記交通状況または前記気象状況の少なくとも一方の時系列データをさらに入力として加え、前記ユーザの活動状態を表す活動モデルを学習する
請求項２に記載の学習装置。
【請求項４】
前記ユーザの位置と前記時刻以外の１種類以上の付加情報の時系列データを取得する付加情報取得手段と、
取得された前記位置の時系列データと前記時刻の時系列データを、前記学習手段により学習された前記ユーザの活動モデルに入力し、前記ユーザの活動モデルの状態ノードの時系列データを出力することにより、前記位置の時系列データと前記時刻の時系列データから、前記状態ノードの時系列データを生成する状態系列生成手段と、
前記付加情報取得手段により取得された前記付加情報の時系列データと、前記状態系列生成手段が生成した前記状態ノードの時系列データを対応付けて記憶し、前記学習手段により学習された前記ユーザの活動モデルを用いて現時点の前記ユーザの活動モデルを予測する場合に、記憶した時系列データのなかから、前記付加情報取得手段で取得された現時点の前記付加情報に対応する前記状態ノードの時系列データのみを選択する選択手段と、
前記選択手段により選択された前記状態ノードの時系列データを用いて、統計的処理により、前記ユーザの活動モデルのパラメータを再計算する再計算手段と
をさらに備える
請求項１に記載の学習装置。
【請求項５】
ユーザの活動状態を表す活動モデルを認識し、ユーザの行動を予測する予測装置で用いるための前記ユーザの活動モデルを確率的状態遷移モデルとして学習する学習装置が、
前記ユーザの位置の時系列データを取得し、
時刻の時系列データを取得し、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、前記ユーザの活動モデルを前記確率的状態遷移モデルとして学習する
学習方法。
【請求項６】
コンピュータに、
ユーザの位置の時系列データを取得する位置取得手段と、
時刻の時系列データを取得する時刻取得手段と、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、前記ユーザの活動状態を表す活動モデルを、確率的状態遷移モデルとして学習する学習手段
として機能させるためのプログラム。
【請求項７】
ユーザの位置の時系列データを取得する位置取得手段と、
時刻の時系列データを取得する時刻取得手段と、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、学習装置が前記ユーザの活動状態を表す活動モデルを確率的状態遷移モデルとして学習して得られた前記ユーザの活動モデルを用いて、前記ユーザの現在地を認識する行動認識手段と、
前記行動認識手段により認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測する行動予測手段と、
予測された前記経路と選択確率から、目的地へ到達する到達時間と到達確率を予測する到達時間予測手段と
を備える予測装置。
【請求項８】
曜日の時系列データを取得する曜日取得手段をさらに備え、
前記学習装置は、前記曜日の時系列データをさらに入力として加え、前記ユーザの活動モデルを学習し、
前記行動認識手段および前記行動予測手段は、前記曜日の時系列データをさらに入力として加えて学習して得られた前記ユーザの活動モデルを用いる
請求項７に記載の予測装置。
【請求項９】
前記ユーザの位置と前記時刻以外の１種類以上の付加情報の時系列データを取得する付加情報取得手段と、
学習用データとしての前記位置の時系列データと前記時刻の時系列データを、学習された前記ユーザの活動モデルに入力し、前記ユーザの活動モデルの状態ノードの時系列データを出力することにより、前記位置の時系列データと前記時刻の時系列データから前記学習装置の状態系列生成手段が生成した前記状態ノードの時系列データを、前記学習用データとしての前記位置の時系列データと前記時刻の時系列データが取得されたときの付加情報の時系列データに対応付けて記憶し、記憶した時系列データのなかから、前記付加情報取得手段で取得された現時点の前記付加情報に対応する前記状態ノードの時系列データのみを選択する選択手段と、
前記選択手段により選択された前記状態ノードの時系列データを用いて、統計的処理により、前記ユーザの活動モデルのパラメータを再計算する再計算手段と
をさらに備える
請求項７に記載の予測装置。
【請求項１０】
前記学習装置は、前記ユーザの位置に加えて、移動速度の時系列データも用いて、前記ユーザの活動モデルを学習し、
前記行動認識手段は、前記ユーザの移動速度の時系列データをさらに入力として、学習して得られた前記ユーザの活動モデルを用いて、少なくとも移動状態と滞在状態に区別される前記ユーザの行動状態も認識し、
前記到達時間予測手段は、さらに、前記ユーザの行動状態が前記滞在状態になる状態ノードを、前記目的地として予測する
請求項９に記載の予測装置。
【請求項１１】
学習装置がユーザの活動状態を表す活動モデルを確率的状態遷移モデルとして学習した前記ユーザの活動モデルを用いて予測する予測装置が、
前記ユーザの位置の時系列データを取得し、
時刻の時系列データを取得し、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、前記学習装置で学習した前記ユーザの活動モデルを用いて、前記ユーザの現在地を認識し、
認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測し、
予測された前記経路と選択確率から、目的地へ到達する到達時間と到達確率を予測する
予測方法。
【請求項１２】
コンピュータに、
ユーザの位置の時系列データを取得する位置取得手段と、
時刻の時系列データを取得する時刻取得手段と、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、学習装置が前記ユーザの活動状態を表す活動モデルを確率的状態遷移モデルとして学習して得られた前記ユーザの活動モデルを用いて、前記ユーザの現在地を認識する行動認識手段と、
前記行動認識手段により認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測する行動予測手段と、
予測された前記経路と選択確率から、目的地へ到達する到達時間と到達確率を予測する到達時間予測手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、学習装置および学習方法、予測装置および予測方法、並びにプログラムに関し、特に、現時刻以降の将来の経路および経過時間を、より正確に予測することができるようにする学習装置および学習方法、予測装置および予測方法、並びにプログラムに関する。
【背景技術】
【０００２】
近年、ユーザが身に着けられるセンサであるウェアラブルセンサから得られる時系列データを用いてユーザの状態をモデル化して学習し、学習により得られたモデルを用いてユーザの現在の状態を認識する研究が盛んである（例えば、特許文献１，２、非特許文献１）。
【０００３】
また、本出願人は、未来の所望の時刻におけるユーザの活動状態の複数の可能性を確率的に予測する方法を、特願２００９−１８０７８０（以下、先願１という）として先に提案している。先願１の方法では、時系列データからユーザの活動状態を確率的状態遷移モデルとして学習し、学習した確率的状態遷移モデルを用いて現在の活動状態を認識し、「所定時間後」のユーザの活動状態を確率的に予測することができる。そして、「所定時間後」のユーザの活動状態の予測の一例として、ユーザの現在の位置を認識し、所定時間後のユーザの行き先（場所）を予測する例が示されている。
【０００４】
さらに、本出願人は、先願１をさらに発展させ、「所定時間後」という現在時刻からの経過時間の指定がない場合であっても、複数の目的地への到達確率、経路、時間を予測する方法を、特願２００９−２０８０６４（以下、先願２という）として提案した。先願２の方法では、確率モデルを構成するノードの中から、目的地のノードに対応するものを見つけることで、目的地の候補を自動的に検出することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−１３４０８０号公報
【特許文献２】特開２００８−２０４０４０号公報
【非特許文献】
【０００６】
【非特許文献１】“Life Patterns: structure from wearable sensors”,Brian Patrick Clarkson, Doctor Thesis, MIT, 2002
【発明の概要】
【発明が解決しようとする課題】
【０００７】
先願２の方法では、例えば、ある目的地を往復する移動経路を確率モデルとして学習させた場合に、行きと帰りのいずれにおいても通過する共通地点については、行きと帰りを区別して異なるノードが割り当てられると考えられていた。
【０００８】
しかし、確率モデルに設定する初期状態やノードの数、時系列データのサンプリング間隔などの設定条件によっては、行きと帰りを区別して異なるノードが割り当てられない場合があった。これにより、例えば、予測処理において、帰路の途中、共通地点から出発地点に引き返すように経路を予測するなどということがあった。帰路の途中、共通地点から出発地点に引き返すように経路を予測することを防止するためには、行きの経路を探索経路から除外するなども考えられるが、そのように経路を除外することは実際の行動に照らすと得策ではない。
【０００９】
本発明は、このような状況に鑑みてなされたものであり、現時刻以降の将来の経路および経過時間を、より正確に予測することができるようにするものである。
【課題を解決するための手段】
【００１０】
本発明の第１の側面の学習装置は、
ユーザの位置の時系列データを取得する位置取得手段と、
時刻の時系列データを取得する時刻取得手段と、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、前記ユーザの活動状態を表す活動モデルを、確率的状態遷移モデルとして学習する学習手段と
を備える。
【００１１】
本発明の第１の側面の学習方法は、
ユーザの活動状態を表す活動モデルを認識し、ユーザの行動を予測する予測装置で用いるための前記ユーザの活動モデルを確率的状態遷移モデルとして学習する学習装置が、
前記ユーザの位置の時系列データを取得し、
時刻の時系列データを取得し、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、前記ユーザの活動モデルを前記確率的状態遷移モデルとして学習する。
【００１２】
本発明の第１の側面のプログラムは、
コンピュータに、
ユーザの位置の時系列データを取得する位置取得手段と、
時刻の時系列データを取得する時刻取得手段と、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、前記ユーザの活動状態を表す活動モデルを、確率的状態遷移モデルとして学習する学習手段
として機能させるためのものである。
【００１３】
本発明の第１の側面においては、ユーザの位置の時系列データが取得され、時刻の時系列データが取得され、取得された位置の時系列データと時刻の時系列データのそれぞれを入力として、ユーザの活動モデルが確率的状態遷移モデルとして学習される。
【００１４】
本発明の第２の側面の予測装置は、
ユーザの位置の時系列データを取得する位置取得手段と、
時刻の時系列データを取得する時刻取得手段と、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、学習装置が前記ユーザの活動状態を表す活動モデルを確率的状態遷移モデルとして学習して得られた前記ユーザの活動モデルを用いて、前記ユーザの現在地を認識する行動認識手段と、
前記行動認識手段により認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測する行動予測手段と、
予測された前記経路と選択確率から、目的地へ到達する到達時間と到達確率を予測する到達時間予測手段と
を備える。
【００１５】
本発明の第２の側面の予測方法は、
学習装置がユーザの活動状態を表す活動モデルを確率的状態遷移モデルとして学習した前記ユーザの活動モデルを用いて予測する予測装置が、
前記ユーザの位置の時系列データを取得し、
時刻の時系列データを取得し、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、前記学習装置で学習した前記ユーザの活動モデルを用いて、前記ユーザの現在地を認識し、
認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測し、
予測された前記経路と選択確率から、目的地へ到達する到達時間と到達確率を予測する。
【００１６】
本発明の第２の側面のプログラムは、
コンピュータに、
ユーザの位置の時系列データを取得する位置取得手段と、
時刻の時系列データを取得する時刻取得手段と、
取得された前記位置の時系列データと前記時刻の時系列データのそれぞれを入力として、学習装置が前記ユーザの活動状態を表す活動モデルを確率的状態遷移モデルとして学習して得られた前記ユーザの活動モデルを用いて、前記ユーザの現在地を認識する行動認識手段と、
前記行動認識手段により認識された前記ユーザの現在地から可能な経路と、その経路の選択確率を予測する行動予測手段と、
予測された前記経路と選択確率から、目的地へ到達する到達時間と到達確率を予測する到達時間予測手段
として機能させるためのものである。
【００１７】
本発明の第２の側面においては、ユーザの位置の時系列データが取得され、時刻の時系列データが取得され、取得された位置の時系列データと時刻の時系列データのそれぞれを入力として、学習装置で学習して得られたユーザの活動モデルを用いて、ユーザの現在地が認識され、認識されたユーザの現在地から可能な経路と、その経路の選択確率が予測され、予測された経路と選択確率から、目的地へ到達する到達時間と到達確率が予測される。
【００１８】
学習装置および予測装置は、独立した装置であっても良いし、１つの装置を構成している内部ブロックであっても良い。
【発明の効果】
【００１９】
本発明の第１の側面によれば、現時刻以降の将来の経路および経過時間を、より正確に予測する予測装置が用いる学習パラメータを学習することができる。
【００２０】
本発明の第２の側面によれば、現時刻以降の将来の経路および経過時間を、より正確に予測することができる。
【図面の簡単な説明】
【００２１】
【図１】先願２における予測システムの第１の構成例を示すブロック図である。
【図２】予測システムのハードウエア構成例を示すブロック図である。
【図３】予測システムに入力される時系列データの例を示す図である。
【図４】HMMの例を示す図である。
【図５】音声認識で利用されるHMMの例を示す図である。
【図６】スパース制約を与えたHMMの例を示す図である。
【図７】行動予測部による経路の探索処理の簡単な例を示す図である。
【図８】ユーザ活動モデル学習処理のフローチャートである。
【図９】到達時間予測処理のフローチャートである。
【図１０】先願２における予測システムの第２の構成例を示すブロック図である。
【図１１】図１０の行動学習部が採用することができる構成の一例を示す図である。
【図１２】予測システム１が認識する行動モードについて説明する図である。
【図１３】到達時間予測処理のフローチャートである。
【図１４】到達時間予測処理のフローチャートである。
【図１５】本発明を適用した予測システムの第１の実施の形態のブロック図である。
【図１６】本発明を適用した予測システムの第２の実施の形態のブロック図である。
【図１７】本発明を適用した予測システムの第３の実施の形態のブロック図である。
【図１８】パラメータ再計算部の詳細構成例を示すブロック図である。
【図１９】予測システムの第３の実施の形態における学習処理を説明するフローチャートである。
【図２０】予測システムの第３の実施の形態における予測処理を説明するフローチャートである。
【図２１】図２０のステップＳ１２３におけるパラメータ再計算処理を説明するフローチャートである。
【図２２】予測システム１００の第４の実施の形態における構成例の一部を示すブロック図である。
【図２３】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図２４】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図２５】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図２６】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図２７】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図２８】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図２９】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図３０】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図３１】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図３２】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図３３】本発明を適用した予測システムの効果を検証した実験の結果について説明する図である。
【図３４】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための形態】
【００２２】
以下、本発明を実施するための形態（以下、実施の形態という）について説明する。なお、説明は、［背景技術］に記載した先願と対比するため、先願２で提案した方法を簡単に説明した後、本発明を適用した実施の形態について説明する。即ち、説明は、以下の順序で行う。
１．先願２の第１の実施例（目的地が指定され、指定された目的地までの経路および到達時間を予測する例）
２．先願２の第２の実施例（目的地も予測して、目的地までの経路および到達時間を予測する例）
３．本発明の第１の実施の形態（時刻と位置の時系列データを用いたマルチストリーム入力のHMMを学習モデルとした実施の形態）
４．本発明の第２の実施の形態（時刻と位置の時系列データ以外の付加情報の時系列データも用いたマルチストリーム入力のHMMを学習モデルとした実施の形態）
５．本発明の第３の実施の形態（時刻と位置の時系列データを用いたマルチストリーム入力HMMとし、その他の情報を付加的に利用した実施の形態）
６．本発明の第４の実施の形態（本発明の第３の実施の形態に、行動モードも認識するようにして、目的地も予測する実施の形態）
７．本発明の実施の形態の検証実験結果の説明
【００２３】
＜１．先願２の第１の実施例＞
［先願２の第１の構成ブロック図］
図１は、先願２で提案した予測システムの第１の構成例を示すブロック図である。
【００２４】
予測システム１は、位置取得部１１、時系列データ記憶部１２、行動学習部１３、行動認識部１４、行動予測部１５、到達時間予測部１６、操作部１７、および表示部１８により構成される。
【００２５】
予測システム１は、位置取得部１１により取得される現在地を示す時系列データから、ユーザの活動状態（行動・活動パターンを表した状態）を確率的状態遷移モデルとして学習する学習処理を行う。また、予測システム１は、学習処理により得られたパラメータで表される確率的状態遷移モデル（ユーザ活動モデル）を用いて、ユーザが指定した目的地までの経路および時間を予測する予測処理も行う。
【００２６】
図１において、点線の矢印は、学習処理におけるデータの流れを示しており、実線の矢印は、予測処理におけるデータの流れを示している。
【００２７】
位置取得部１１は、例えば、GPSセンサなどにより構成され、自身の位置を示す緯度経度のデータを、一定時間間隔（たとえば、１５秒間隔）で順次取得する。なお、位置取得部１１が位置のデータを一定間隔に取得することができない場合もある。例えば、GPSセンサはトンネルや地下などでは人工衛星を捕捉することができず、取得間隔が長くなることもある。このような場合には、補間処理を行うことなどにより、データを補うことができる。
【００２８】
位置取得部１１は、学習処理においては、取得される位置（緯度経度）のデータを時系列データ記憶部１２に供給する。また、位置取得部１１は、予測処理においては、取得される位置のデータを行動認識部１４に供給する。
【００２９】
時系列データ記憶部１２は、位置取得部１１により連続して取得された位置のデータ、すなわち、位置の時系列データを記憶する。ユーザの行動・活動パターンを学習するので、例えば、数日分程度など、ある程度の期間について蓄積された時系列データが必要である。
【００３０】
行動学習部１３は、時系列データ記憶部１２に記憶されている時系列データに基づいて、位置取得部１１が組み込まれた機器を携行するユーザの活動状態を、確率的状態遷移モデルとして学習する。時系列データはユーザの位置を示すデータであるので、確率的状態遷移モデルとして学習されるユーザの活動状態は、ユーザの現在地の時系列変化、すなわちユーザの移動経路を表す状態となる。学習に使用される確率的状態遷移モデルとしては、例えば、エルゴディックHMM（Hidden Markov Model）などの、隠れ状態を含む確率的状態遷移モデルを採用することができる。予測システム１では、確率的状態遷移モデルとして、エルゴディックHMMにスパース制約を与えたものを採用する。なお、スパース制約を与えたエルゴディックHMM、エルゴディックHMMのパラメータの算出方法等については、図４乃至図６を参照して後述する。
【００３１】
行動学習部１３は、学習処理により得られた確率的状態遷移モデルのパラメータを行動認識部１４および行動予測部１５に供給する。
【００３２】
行動認識部１４は、学習により得られたパラメータの確率的状態遷移モデルを用いて、位置取得部１１からリアルタイムに供給される位置の時系列データから、ユーザの現在の活動状態、すなわち、ユーザの現在地を認識する。行動認識部１４は、ユーザの現在の状態ノードのノード番号を行動予測部１５に供給する。
【００３３】
行動予測部１５は、学習により得られたパラメータの確率的状態遷移モデルを用いて、行動認識部１４から供給される状態ノードのノード番号が示すユーザの現在地から、ユーザが取りうる経路を過不足なく探索（予測）する。また、行動予測部１５は、探索された経路ごとの生起確率を計算することにより、探索された経路が選択される確率である選択確率を予測する。
【００３４】
到達時間予測部１６には、行動予測部１５から、ユーザが取りうる経路と、その選択確率が供給される。また、到達時間予測部１６には、操作部１７から、ユーザが指定した目的地を示す情報が供給される。
【００３５】
到達時間予測部１６は、探索結果としてのユーザが取りうる経路から、ユーザが指定した目的地を含む経路を抽出し、抽出された各経路について目的地までの到達時間を予測する。また、到達時間予測部１６は、目的地へ到達する確率である到達確率を予測する。到達時間予測部１６は、目的地について複数の経路が存在する場合、その複数の経路の選択確率の和を、目的地の到達確率として算出する。目的地への経路が１つのみである場合には、その経路の選択確率が、そのまま目的地の到達確率となる。そして、到達時間予測部１６は、予測結果を示す情報を表示部１８に供給し、表示させる。
【００３６】
操作部１７は、ユーザが入力した目的地についての情報を受け付け、到達時間予測部１６に供給する。表示部１８は、到達時間予測部１６から供給される情報を表示する。
【００３７】
［予測システムのハードウエア構成例］
以上のように構成される予測システム１は、例えば、図２に示されるハードウエア構成を採用することができる。即ち、図２は、予測システム１のハードウエア構成例を示すブロック図である。
【００３８】
図２において、予測システム１は、３台のモバイル端末２１−１乃至２１−３とサーバ２２とにより構成されている。モバイル端末２１−１乃至２１−３は、同一機能を有する同型のモバイル端末２１であるが、モバイル端末２１−１乃至２１−３では、それを所有するユーザが異なる。従って、図２では、３台のモバイル端末２１−１乃至２１−３のみが示されているが、実際には、ユーザ数に応じた数のモバイル端末２１が存在する。
【００３９】
モバイル端末２１は、無線通信及びインターネット等のネットワークを介した通信により、サーバ２２とデータの授受を行うことができる。サーバ２２は、モバイル端末２１から送信されてくるデータを受信し、受信したデータに対し所定の処理を行う。そして、サーバ２２は、データ処理の処理結果を無線通信等によりモバイル端末２１に送信する。
【００４０】
従って、モバイル端末２１とサーバ２２は、無線または有線による通信を行う通信部を少なくとも有する。
【００４１】
さらに、モバイル端末２１が、図１の位置取得部１１、操作部１７、および表示部１８を備え、サーバ２２が、図１の時系列データ記憶部１２、行動学習部１３、行動認識部１４、行動予測部１５、および到達時間予測部１６を備える構成を採用することができる。
【００４２】
この構成が採用される場合、学習処理において、モバイル端末２１が、位置取得部１１により取得された時系列データを送信する。サーバ２２は、受信した学習用の時系列データに基づき、ユーザの活動状態を確率的状態遷移モデルにより学習する。そして、予測処理において、モバイル端末２１が、操作部１７を介してユーザによって指定された目的地を送信するとともに、位置取得部１１によりリアルタイムに取得される位置データを送信する。サーバ２２は、学習により得られたパラメータを用いて、ユーザの現在の活動状態、すなわち、ユーザの現在地を認識し、さらに、指定された目的地までの経路および時間を処理結果としてモバイル端末２１に送信する。モバイル端末２１は、サーバ２２から送信されてきた処理結果を表示部１８に表示する。
【００４３】
また例えば、モバイル端末２１が、図１の位置取得部１１、行動認識部１４、行動予測部１５、到達時間予測部１６、操作部１７、および表示部１８を備え、サーバ２２が、図１の時系列データ記憶部１２および行動学習部１３を備える構成を採用することができる。
【００４４】
この構成が採用される場合、学習処理において、モバイル端末２１が、位置取得部１１により取得された時系列データを送信する。サーバ２２は、受信した学習用の時系列データに基づき、ユーザの活動状態を確率的状態遷移モデルにより学習し、学習により得られたパラメータをモバイル端末２１に送信する。そして、予測処理において、モバイル端末２１が、位置取得部１１によりリアルタイムに取得される位置データを、サーバ２２から受信したパラメータを用いて、ユーザの現在地を認識し、さらに、指定された目的地までの経路および時間を演算する。そして、モバイル端末２１は、演算結果としての目的地までの経路および時間を表示部１８に表示する。
【００４５】
以上のようなモバイル端末２１とサーバ２２との間の役割分担は、それぞれのデータ処理装置としての処理能力や通信環境に応じて決定することができる。
【００４６】
学習処理は、処理に要する１回あたりの時間は非常に長いが、それほど頻繁に処理する必要はない。従って、一般的には、携行可能なモバイル端末２１よりもサーバ２２の方が処理能力が高いので、サーバ２２に、一日に一回程度蓄積された時系列データに基づいて学習処理（パラメータの更新）を行わせるようにすることができる。
【００４７】
一方、予測処理は、時々刻々とリアルタイムに更新される位置データに対応させて迅速に処理し、表示することが望ましいので、モバイル端末２１で処理を行う方が望ましい。通信環境がリッチであれば、上述したようにサーバ２２に予測処理も行わせ、予測結果のみをサーバ２２から受信する方が、携行可能な小型化が要求されるモバイル端末２１の負荷が軽減され、望ましい。
【００４８】
また、モバイル端末２１単独で、データ処理装置として学習処理および予測処理を高速に行うことが可能である場合には、図１の予測システム１の構成すべてをモバイル端末２１が備えるようにすることも勿論可能である。
【００４９】
［入力される時系列データの例］
図３は、予測システム１で取得された位置の時系列データの例を示している。図３において、横軸は経度を表し、縦軸は緯度を表している。
【００５０】
図３に示される時系列データは、実験者の１ヶ月半程度の期間に蓄積された時系列データを示している。図３に示されるように、時系列データは、主に、自宅周辺と、勤務先などの４か所の外出先を移動したデータとなっている。なお、この時系列データには、人工衛星を捕捉できず、位置データが飛んでいるデータも含まれている。
【００５１】
なお、図３に示される時系列データは、後述する検証実験に使用したデータとは別のデータ例である。
【００５２】
［エルゴディック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を示している。
【００７９】
予測システム１では、位置取得部１１が取得した位置データが、時系列データx=x1,x2,・・・,xTとして、時系列データ記憶部１２に供給される。行動学習部１３は、時系列データ記憶部１２に記憶されている時系列データx=x1,x2,・・・,xTを用い、ユーザ活動モデルを表すHMMのパラメータλを推定する。
【００８０】
即ち、ユーザの移動軌跡を表す各時刻の位置（緯度経度）のデータが、HMMの状態sjのいずれかに対応する地図上の一点から、所定の分散値の広がりを持って正規分布した確率変数の観測データであると考える。行動学習部１３は、各状態sjに対応する地図上の一点とその分散値、および状態遷移確率aijを最適化する。
【００８１】
なお、状態siの初期確率πiは、一様な値に設定することができる。例えば、M個の状態siそれぞれの初期確率πiが、1/Mに設定される。また、位置取得部１１が取得した位置データに対して補間処理などの所定の処理を施した後の位置データを、時系列データx=x1,x2,・・・,xTとして、時系列データ記憶部１２に供給してもよい。
【００８２】
行動認識部１４は、学習により得られたユーザ活動モデル（HMM）に対して、ビタビ法を適用し、位置取得部１１からの位置データ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]は、次式（１）で表すことができる。
【数１】
2011118777.tif 000003
ここで、δは、クロネッカー関数を表し、添え字のｉとｊが一致するときのみ１となり、それ以外は０となる関数である。
【００９７】
したがって、例えば、図７の状態s５の状態遷移確率aijが、自己遷移確率a５，５＝０．５，遷移確率a５，６＝０．２，遷移確率a５，１１＝０．３である場合、状態s５から状態s６または状態s１１に分岐する場合の遷移確率[a５，６]および遷移確率[a５，１１]は、それぞれ、０．４，０．６となる。
【００９８】
探索された経路の状態siのノード番号ｉが、（ｙ１，ｙ２，・・・，ｙｎ）であるとき、この経路の選択確率P（ｙ１，ｙ２，・・・，ｙｎ）は、規格化された遷移確率[aij]を用いて、次式（２）で表すことができる。
【００９９】
【数２】
2011118777.tif 000004
【０１００】
実際には、通過点での規格化された遷移確率[aij]は１であるので、分岐する際の規格化された遷移確率[aij]を順次乗算すれば足りる。
【０１０１】
図７の例では、経路Ａの選択確率は、０．４である。また、経路Ｂの選択確率は、０．２４＝０．６×０．４である。経路Ｃの選択確率は、０．３６＝０．６×０．６である。そして、計算された経路の選択確率の総和は１＝０．４＋０．２４＋０．３６であり、過不足ない探索を実現することができることがわかる。
【０１０２】
以上のように、現在地に基づいて探索された各経路とその選択確率が、行動予測部１５から到達時間予測部１６に供給される。
【０１０３】
到達時間予測部１６は、行動予測部１５によって探索された経路から、ユーザが指定した目的地を含む経路を抽出し、抽出された各経路について目的地までの時間を予測する。
【０１０４】
例えば、図７の例では、探索された３つの経路Ａ乃至Ｃのうち、目的地である状態s２８を含む経路は経路Ｂと経路Ｃである。到達時間予測部１６は、経路Ｂまたは経路Ｃを通って、目的地である状態s２８に到達するまでの時間を予測する。
【０１０５】
なお、目的地を含む経路が多数あり、全ての経路を表示すると見づらくなる場合や経路の提示数が所定数に設定されている場合には、目的地を含む全ての経路のなかから、表示部１８に表示させる経路（以下、適宜、表示経路ともいう。）を決定する必要がある。そのような場合、行動予測部１５では、各経路について選択確率が算出されているので、到達時間予測部１６は、選択確率の高い順に、所定数の経路を表示経路として決定することができる。
【０１０６】
現在時刻ｔ１の現在地が状態ｓｙ１であり、時刻（ｔ１，ｔ２，・・・，ｔｇ）における決定された経路が（ｓｙ１，ｓｙ２，・・・，ｓｙｇ）であるとする。換言すれば、決定された経路の状態siのノード番号ｉが（ｙ１，ｙ２，・・・，ｙｇ）であるとする。以下、簡単のため、位置に相当する状態siを、単に、そのノード番号ｉで表わす場合もある。
【０１０７】
現在時刻ｔ１での現在地ｙ１は、行動認識部１４の認識により確定しているので、現在時刻ｔ１の現在地がｙ１である確率Ｐｙ１（ｔ１）は１である。また、現在時刻ｔ１にｙ１以外の他の状態にいる確率は０である。
【０１０８】
一方、所定の時刻ｔｎにノード番号ｙｎにいる確率Ｐｙｎ（ｔｎ）は、
【数３】
2011118777.tif 000005
で表すことができる。式（３）の右辺第一項は、もともとその位置ｙｎにいて、自己遷移した場合の確率を表し、右辺第二項は、１つ前の位置ｙｎ−１から位置ｙｎに遷移してきた場合の確率を表している。式（３）では、経路の選択確率の計算とは異なり、学習により得られた状態遷移確率aijがそのまま利用される。
【０１０９】
目的地ｙｇへ到達するときの時刻ｔｇの予測値<ｔｇ>は、「その直前の時刻ｔｇ−１に目的地ｙｇの１つ前の位置ｙｇ−１にいて、時刻ｔｇに目的地ｙｇに移動する確率」を用いて、
【数４】
2011118777.tif 000006
と表すことができる。
【０１１０】
即ち、予測値<ｔｇ>は、現在時刻から、「その直前の時刻ｔｇ−１に状態ｓｙｇの１つ前の状態ｓｙｇ−１にいて、時刻ｔｇに状態ｓｙｇに移動するとき」までの時間の期待値で表される。
【０１１１】
［ユーザ活動モデル学習処理］
次に、図８のフローチャートを参照して、ユーザの移動経路を、ユーザの活動状態を表す確率的状態遷移モデルとして学習する、ユーザ活動モデル学習処理について説明する。
【０１１２】
初めに、ステップＳ１において、位置取得部１１は、位置データを取得し、時系列データ記憶部１２に供給する。
【０１１３】
ステップＳ２において、時系列データ記憶部１２は、位置取得部１１により連続して取得された位置データ、すなわち、位置の時系列データを記憶する。
【０１１４】
ステップＳ３において、行動学習部１３は、時系列データ記憶部１２に記憶されている時系列データに基づいて、ユーザ活動モデルを確率的状態遷移モデルとして学習する。即ち、行動学習部１３は、時系列データ記憶部１２に記憶されている時系列データに基づいて、確率的状態遷移モデル（ユーザ活動モデル）のパラメータλを算出する。
【０１１５】
ステップＳ４において、行動学習部１３は、ステップＳ３で算出された確率的状態遷移モデルのパラメータλを、行動認識部１４および行動予測部１５に供給し、処理を終了する。
【０１１６】
［到達時間予測処理］
次に、図８のユーザ活動モデル学習処理により得られたユーザ活動モデルを表す確率的状態遷移モデルのパラメータλを用いて、目的地までの経路を探索し、到達時間を算出してユーザに提示する到達時間予測処理について説明する。
【０１１７】
図９は、到達時間予測処理のフローチャートを示している。なお、この例では、図９の処理の前に、目的地が予め決められているものとするが、図９の処理の途中で目的地を入力するようにしてもよい。
【０１１８】
初めに、ステップＳ２１において、位置取得部１１は、位置の時系列データを取得し、行動認識部１４に供給する。行動認識部１４には、所定のサンプル数の位置の時系列データが一時的に記憶される。
【０１１９】
ステップＳ２２において、行動認識部１４は、学習により得られたパラメータλに基づくユーザ活動モデルから、ユーザの現在の活動状態を認識する。即ち、行動認識部１４は、ユーザの現在地を認識する。そして、行動認識部１４は、ユーザの現在の状態ノードのノード番号を行動予測部１５に供給する。
【０１２０】
ステップＳ２３において、行動予測部１５は、現在探索している状態ノード（以下、適宜、現在の状態ノードともいう。）に対応する点が、端点、通過点、分岐点、またはループのいずれであるかを判定する。ステップS２２の処理直後は、ユーザの現在地に対応する状態ノードが現在の状態ノードとなる。
【０１２１】
ステップＳ２３で、現在の状態ノードに対応する点が端点であると判定された場合、処理はステップＳ２４に進み、行動予測部１５は、現在の状態ノードをここまでの経路に接続し、この経路の探索を終了し、ステップＳ３１に進む。なお、現在の状態ノードが現在地に対応する状態ノードである場合、ここまでの経路は存在しないため、接続する処理は行われない。ステップＳ２５，Ｓ２７、Ｓ３０でも同様である。
【０１２２】
ステップＳ２３で、現在の状態ノードに対応する点が通過点であると判定された場合、処理はステップＳ２５に進み、行動予測部１５は、現在の状態ノードをここまでの経路に接続する。そして、ステップＳ２６において、行動予測部１５は、次の状態ノードを現在の状態ノードとし、移動する。ステップＳ２６の処理後、処理はステップＳ２３に戻る。
【０１２３】
ステップＳ２３で、現在の状態ノードに対応する点が分岐点であると判定された場合、処理はステップＳ２７に進み、行動予測部１５は、現在の状態ノードをここまでの経路と接続する。そして、ステップＳ２８において、行動予測部１５は、ここまでの経路を分岐の数だけ複製し、分岐先の状態ノードと接続する。さらにステップＳ２９において、行動予測部１５は、複製した経路の１つを選択し、その選択した経路の先の状態ノードを現在の状態ノードとし移動する。ステップＳ２９の処理後、処理はステップＳ２３に戻る。
【０１２４】
一方、ステップＳ２３で、現在の状態ノードに対応する点がループであると判定された場合、処理はステップＳ３０に進み、行動予測部１５は、現在の状態ノードをここまでの経路と接続せずに、この経路の探索を終了し、ステップＳ３１に進む。
【０１２５】
ステップＳ３１において、行動予測部１５は、未探索の経路があるかを判定する。ステップＳ３１で、未探索の経路があると判定された場合、処理はステップＳ３２に進み、行動予測部１５は、現在地の状態ノードに戻り、未探索の経路の次の状態ノードを現在の状態ノードとし移動する。ステップＳ３２の処理後、処理はステップＳ２３に戻る。これにより、未探索の経路について、端点またはループにより探索が終了するまで経路の探索が実行される。
【０１２６】
ステップＳ３１で、未探索の経路がないと判定された場合、処理はステップＳ３３に進み、行動予測部１５は、探索された各経路の選択確率（生起確率）を計算する。行動予測部１５は、各経路と、その選択確率を到達時間予測部１６に供給する。
【０１２７】
ステップＳ３４において、到達時間予測部１６は、行動予測部１５によって探索された経路から、入力された目的地を含む経路を抽出し、目的地の到達確率を算出する。具体的には、到達時間予測部１６は、目的地に複数の経路が存在する場合、その複数の経路の選択確率の和を、目的地の到達確率として計算する。目的地への経路が１つしかない場合、経路の選択確率が、そのまま、目的地の到達確率とされる。
【０１２８】
ステップＳ３５において、到達時間予測部１６は、抽出された経路の数が提示数として予め設定された所定個数より多いかを判定する。
【０１２９】
ステップＳ３５で、抽出された経路の数が所定個数より多いと判定された場合、処理はステップＳ３６に進み、到達時間予測部１６は、表示部１８に表示する所定個数の経路を決定する。例えば、到達時間予測部１６は、選択される可能性の高い順に、所定個数の経路を決定することができる。
【０１３０】
一方、ステップＳ３５で、抽出された経路の数が所定個数以下であると判定された場合、ステップＳ３６の処理がスキップされる。即ち、この場合、目的地に到達するための全ての経路が表示部１８に表示される。
【０１３１】
ステップＳ３７において、到達時間予測部１６は、表示部１８に表示すると決定された各経路の到達時間を計算する。そして、到達時間予測部１６は、目的地の到達確率および目的地までの経路と到達時間を表示する画像の信号を表示部１８に供給する。
【０１３２】
ステップ３８において、表示部１８は、到達時間予測部１６から供給される画像の信号に基づいて、目的地の到達確率および目的地までの経路と到達時間を表示して、処理を終了する。
【０１３３】
以上のように、予測システム１の第１の構成例では、位置取得部１１により取得される位置の時系列データから、ユーザの活動状態を確率的状態遷移モデルとして学習する学習処理を行う。そして、予測システム１は、学習処理により得られたパラメータλで表される確率的状態遷移モデルを用いて、入力された目的地の到達確率および目的地までの経路と到達時間を予測して、ユーザに提示する。
【０１３４】
したがって、予測システム１の第１の構成例によれば、ユーザが指定した目的地の到達確率および目的地までの経路とその到達時間を予測して、ユーザに提示することができる。
【０１３５】
＜２．先願２の第２の構成例＞
［先願２の第２の構成ブロック図］
図１０は、先願２で提案した予測システムの第２の構成例を示すブロック図である。なお、図１０において、上述した第１の構成例と対応する部分については同一の符号を付してあり、その説明は適宜省略する（その他の図についても同様）。
【０１３６】
図１０の予測システム１は、位置取得部１１、速度演算部５０、時系列データ記憶部５１、行動学習部５２、行動認識部５３、行動予測部５４、目的地予測部５５、操作部１７、および表示部１８により構成される。
【０１３７】
第１の構成例では、目的地はユーザが指定することとしたが、第２の構成例では、位置取得部１１により取得される位置データの時系列データに基づいて、目的地も予測システム１が予測する。目的地は１つだけでなく、複数の目的地が予測されることもある。予測システム１は、予測した目的地について到達確率、経路、および到達時間を算出してユーザに提示する。
【０１３８】
目的地とされる自宅や勤務先、駅、買い物先、レストランなどでは、ユーザはその場所に所定時間滞在するのが一般的であり、ユーザの移動速度はほぼゼロに近い状態となる。一方、ユーザが目的地に移動している場合には、ユーザの移動速度は、移動手段に応じた特定のパターンで遷移する状態となる。従って、ユーザの移動速度の情報からユーザの行動状態、即ち、ユーザが目的地に滞在している状態（滞在状態）であるのか、または、移動している状態（移動状態）であるのかを認識し、滞在状態の場所を目的地として予測することができる。
【０１３９】
速度演算部５０は、位置取得部１１から一定時間間隔で供給される位置データから移動速度を演算する。
【０１４０】
具体的には、一定の時間間隔でｋステップ目（ｋ個目）に得られるときの位置データを、時刻ｔｋ、経度ｙｋ、緯度ｘｋと表すと、ｋステップ目のｘ方向の移動速度ｖｘｋおよびｙ方向の移動速度ｖｙｋは、次式（５）により計算することができる。
【０１４１】
【数５】
2011118777.tif 000007
【０１４２】
式（５）では、位置取得部１１から得られる緯度経度のデータをそのまま利用しているが、緯度経度を距離に変換したり、速度を時速や分速で表すように変換するなどの処理は、必要に応じて適宜行うことができる。
【０１４３】
また、速度演算部５０は、式（５）で得られる移動速度ｖｘｋおよびｖｙｋからさらに、式（６）で表されるｋステップ目の移動速度ｖｋと進行方向の変化θｋを求め、これを利用することができる。
【０１４４】
【数６】
2011118777.tif 000008
【０１４５】
式（６）で表される移動速度ｖｋと進行方向の変化θｋを利用する方が、式（５）の移動速度ｖｘｋおよびｖｙｋよりも以下の点で、特徴をうまく取り出すことができる。
【０１４６】
１．移動速度ｖｘｋおよびｖｙｋのデータの分布は、緯度経度軸に対して偏りが生じるため、同じ移動手段（電車や徒歩など）であっても角度が異なった場合に識別できない可能性があるが、移動速度ｖｋであればそのような可能性が少ない。
２．移動速度の絶対的な大きさ（｜ｖ｜）だけで学習すると、機器のノイズによって生じる｜ｖ｜のため、徒歩と滞在を区別できない。進行方向の変化も考慮することで、ノイズの影響を軽減することができる。
３．移動している場合は進行方向の変化が少ないが、滞在している場合は進行方向が定まらないので、進行方向の変化を使うと移動と滞在の識別がしやすい。
【０１４７】
以上の理由から、速度演算部５０は、移動速度のデータとして、式（６）で表される移動速度ｖｋと進行方向の変化θｋを求め、位置データとともに、時系列データ記憶部１２または行動認識部５３に供給する。
【０１４８】
また、速度演算部５０は、移動速度ｖｋと進行方向の変化θｋの演算を行う前に、ノイズ成分を除去するため、移動平均によるフィルタリング処理（前処理）を行う。
【０１４９】
なお、以下では、進行方向の変化θｋを、進行方向θｋと略記する。
【０１５０】
位置取得部１１のなかには、移動速度を出力できるものも存在する。そのような位置取得部１１が採用されている場合、速度演算部５０を省略し、位置取得部１１が出力する移動速度をそのまま利用することができる。
【０１５１】
時系列データ記憶部５１は、速度演算部５０から供給される位置データおよび移動速度の時系列データを記憶する。
【０１５２】
行動学習部５２は、時系列データ記憶部５１に記憶されている時系列データに基づいて、ユーザの移動軌跡と行動状態を確率的状態遷移モデルとして学習する。即ち、行動学習部５２は、ユーザの現在地を認識し、目的地と、その経路および到達時間を予測するためのユーザ活動モデルを確率的状態遷移モデルとして学習する。
【０１５３】
行動学習部５２は、学習処理により得られた確率的状態遷移モデルのパラメータλを行動認識部５３、行動予測部５４、および目的地予測部５５に供給する。
【０１５４】
行動認識部５３は、学習により得られたパラメータλの確率的状態遷移モデルを用いて、位置および移動速度の時系列データから、ユーザの現在地を認識する。行動認識部５３は、ユーザの現在の状態ノードのノード番号を行動予測部５４に供給する。
【０１５５】
行動予測部５４は、学習により得られたパラメータλの確率的状態遷移モデルを用いて、ユーザの現在地から、ユーザが取りうる経路を過不足なく探索し、探索された経路ごとの選択確率を計算する。
【０１５６】
即ち、行動認識部５３および行動予測部５４は、移動速度の時系列データを加えることにより移動経路以外に行動状態をも学習したパラメータλを使用する点以外は、第１の構成例の行動認識部１４および行動予測部１５と同様である。
【０１５７】
目的地予測部５５は、学習により得られたパラメータλの確率的状態遷移モデルを用いて、ユーザの目的地を予測する。
【０１５８】
具体的には、目的地予測部５５は、最初に、目的地候補を列挙する。目的地予測部５５は、認識されるユーザの行動状態が滞在状態となる場所を目的地候補とする。
【０１５９】
そして、目的地予測部５５は、列挙した目的地候補のうち、行動予測部５４により探索された経路上にある目的地候補を目的地に決定する。
【０１６０】
次に、目的地予測部５５は、決定した目的地ごとの到達確率を算出する。
【０１６１】
目的地が多数検出された場合には、そのすべてについて表示部１８に表示すると見づらくなったり、行く可能性の少ない目的地まで表示することもあり得る。したがって、第１の構成例において、探索された経路を絞り込んだのと同様に、目的地についても、到達確率の高い所定個数の目的地や、到達確率が所定値以上の目的地のみを表示するように、表示対象の目的地を絞り込むことができる。なお、目的地と経路の表示個数は異なっていても構わない。
【０１６２】
表示対象の目的地が決定された場合、目的地予測部５５は、目的地までの経路の到達時間を計算し、表示部１８に表示させる。
【０１６３】
なお、目的地までの経路が多数存在する場合には、目的地予測部５５は、第１の構成例と同様に、選択確率に基づいて目的地への経路を所定個数に絞り込んだ上で、表示経路の到達時間のみを計算することができる。
【０１６４】
また、目的地までの経路が多数存在する場合、選択される可能性の高い順で表示経路を決定する以外に、到達時間の短い順や、目的地までの距離の短い順に、表示経路を決定することも可能である。到達時間の短い順に表示経路を決定する場合には、例えば、目的地予測部５５は、最初に、目的地までの経路の全てについて到達時間を計算し、計算された到達時間に基づいて、表示経路を決定する。目的地までの距離の短い順に表示経路を決定する場合には、例えば、目的地予測部５５は、最初に、目的地までの経路の全てについて、状態ノードに対応する緯度経度の情報に基づいて目的地までの距離を計算し、計算された距離に基づいて、表示経路を決定する。
【０１６５】
［行動学習部５２の詳細構成例］
図１１は、図１０の行動学習部５２が採用することができる構成の一例を示している。
【０１６６】
行動学習部５２は、時系列データ記憶部５１に記憶されている位置および移動速度の時系列データを用いて、ユーザの移動軌跡と行動状態を同時に学習する。
【０１６７】
行動学習部５２は、学習データ変換部６１と統合学習部６２により構成されている。
【０１６８】
学習データ変換部６１は、状態系列生成部７１と行動モード生成部７２により構成される。状態系列生成部７１は、位置の時系列データを、状態ノードsiの時系列データ（状態系列データ）に変換して、統合学習部６２に供給する。行動モード生成部７２は、移動速度のデータを、行動モードの時系列データ（行動モード系列データ）に変換して、統合学習部６２に供給する。
【０１６９】
時系列データ記憶部１２から供給される位置の時系列データは、状態系列生成部７１に供給される。状態系列生成部７１は、図１の行動認識部１４と同様の構成を採用することができる。即ち、状態系列生成部７１は、学習により得られたパラメータλに基づくユーザ活動モデルから、入力されたユーザの現在地に対応する、ユーザの現在の活動状態を認識する。そして、状態系列生成部７１は、認識結果としてのユーザの現在の状態ノードsiを、順次、統合学習部６２に供給する。
【０１７０】
時系列データ記憶部１２から供給される移動速度の時系列データは、行動モード生成部７２に供給される。行動モード生成部７２は、ユーザの行動状態を確率的状態遷移モデルとして学習して得られたパラメータλを用いて、供給される移動速度に対応するユーザの行動状態を認識し、認識結果を、順次、行動モードとして統合学習部６２に供給する。行動モード生成部７２が認識するユーザの行動状態としては、少なくとも滞在状態と移動状態が存在する必要がある。また、移動状態の行動モードを、さらに徒歩、自転車、車などの移動手段によって分類することができる。
【０１７１】
［行動モードの分類］
図１２は、行動モード生成部７２が認識するユーザの行動状態（行動モード）について説明する図である。
【０１７２】
図１２に示されるように、まず、ユーザの行動状態は、滞在状態と移動状態に分類することができる。予測システム１では、行動モード生成部７２が認識するユーザの行動状態としては、上述したように、少なくとも滞在状態と移動状態が存在する必要があるので、この２つに分類することは必須である。
【０１７３】
さらに、移動状態は、移動手段によって、電車、車（バスなども含む）、自転車、徒歩に分類することができる。電車は、さらに、特急、快速、ローカルなどに分類することができ、車は、さらに、高速、一般道などに分類することができる。また、徒歩は、走る、普通、散歩などに分類することができる。
【０１７４】
予測システム１では、ユーザの行動状態を、図１２において斜線で示される“滞在”、“電車（快速）”、“電車（ローカル）”、“車（高速）”、“車（一般道）”、“自転車”、および“徒歩”に分類することとする。なお、“電車（特急）”は、学習データが得られなかったため省略した。
【０１７５】
行動モードの分類の仕方が図１２に示した例に限定されるものではないことは言うまでもない。また、移動手段による移動速度の変化はユーザによって大きく異なるものではないので、学習データとしての移動速度の時系列データは、認識対象のユーザのものである必要はない。
【０１７６】
図１１に戻り、統合学習部６２は、複数の事象（モーダル）の時系列データを確率的状態遷移モデルにより統合学習する。統合学習部６２には、第１の事象の時系列データとして、状態系列データが供給され、第２の事象の時系列データとして、行動モード系列データが供給される。従って、統合学習部６２は、状態系列データと行動モード系列データとを用いて、ユーザの活動状態を表す確率的状態遷移モデルとしてのマルチストリームHMMのパラメータλを学習する。
【０１７７】
マルチストリームHMMは、通常のHMMと同様な遷移確率を有する状態ノードから、複数の異なる確率法則に従うデータが出力されるようなHMMである。マルチストリームHMMでは、パラメータλのうち、観測確率パラメータとしての出力確率密度関数bj(x)が時系列データごとに別々に用意され、更新される。
【０１７８】
第１の事象の時系列データの出力確率密度関数b1j(x)が、平均μｓ、標準偏差σｘｓの正規確率分布であり、第２の事象の時系列データの出力確率密度関数b2j(x)が、平均μｓ、標準偏差σｙｓの正規確率分布であるとすると、時刻ｔの第１の事象の時系列データのｘｔと第２の事象の時系列データのｙｔが、状態ｓｉから出力されたとする尤度Ｐ（ｓｉ｜ｘｔ，ｙｔ）は、次式（７）で与えられる。
【０１７９】
【数７】
2011118777.tif 000009
【０１８０】
式（７）において、ｗｘおよびｗｙは、重みであり、第１および第２の事象の時系列データが学習モデルに寄与する度合いを表す。この重みｗｘおよびｗｙは、対数尤度で考えると、各事象の対数尤度の線形結合であるといえる。従って、マルチストリームHMMでは、各状態ｓｉの尤度が、各ストリームに対して学習モデルの状態が持つ尤度を対数尤度で線形結合したものとなっている。
【０１８１】
なお、シングルストリームの入力である通常のHMMにおける状態ｓｉの尤度は、式（７）において、ｙｔの項がなく、重みｗｙを０としたものに相当する。
【０１８２】
観測確率パラメータとしての出力確率密度関数bj(x)が時系列データごとに別々に更新される点と、式（７）により尤度が計算される点を除いて、学習処理は、通常のHMMと同様である。
【０１８３】
この例では、時系列データが、状態系列データと行動モード系列データの２つであるので、統合学習部６２のマルチストリームHMMでは、地図上のインデックスと行動モードが関連付けられた形でユーザの活動状態が学習（統合学習）される。
【０１８４】
より具体的には、統合学習部６２は、各状態ノードの確率（どの状態ノードが出力されるかの確率）と、各状態ノードの出力する行動モードの確率（どの行動のモードが出力されるかの確率）を学習する。学習により得られた統合モデル（マルチストリームHMM）によれば、”滞在状態”の行動モードが確率的に出力されやすい状態ノードが求められる。そして、認識された状態ノードから、目的地候補の場所を認識することができる。さらに、目的地候補の場所が示す緯度経度分布から、目的地の位置を認識することができる。
【０１８５】
以上のように、観測される行動モードが“滞在状態”になる確率が高い状態ノードの示す位置がユーザの滞在場所であると推定される。そして、上述したように、“滞在状態”となる場所は多くの場合、目的地であるから、この滞在場所を目的地として推定することができる。
【０１８６】
統合学習部６２は、学習により得られた、ユーザの活動状態を表すマルチストリームHMMのパラメータλを、行動認識部１４、行動予測部１５、および到達時間予測部１６に供給する。
【０１８７】
なお、上述した例では、状態系列生成部７１と行動モード生成部７２において、HMMによりモデル化することで、時系列データ記憶部１２から供給される位置および移動速度の時系列データを、状態系列データと行動モード系列データに変換するようにした。
【０１８８】
しかし、これ以外の方法によって、位置および移動速度のデータを、状態系列データと行動モード系列データに変換するようにしてもよい。例えば、行動モードについては、位置取得部１１とは別に、加速度センサやジャイロセンサ等のモーションセンサを用いて、加速度等の検出結果から、ユーザの移動の有無を検出し、行動モードを判定した判定結果を取得するようにしてもよい。この場合、行動モード生成部７２は省略することができる。
【０１８９】
［目的地到達時間予測処理］
次に、図１３および図１４のフローチャートを参照して、図１０の予測システム１による目的地到達時間予測処理について説明する。
【０１９０】
即ち、図１３および図１４は、位置および移動速度の時系列データから、目的地を予測し、かつ、目的地までの経路および到達時間を算出してユーザに提示する目的地到達時間予測処理のフローチャートである。
【０１９１】
図１３のステップＳ５１乃至ステップＳ６３の処理は、ステップＳ５１で取得する時系列データが、位置と移動速度のデータである以外は、図９に示した到達時間予測処理のステップＳ２１乃至Ｓ３３と同様であるので、その説明は省略する。
【０１９２】
図１３のステップＳ５１乃至ステップＳ６３の処理により、ユーザの現在地が認識され、そこからユーザが取りうる経路が過不足なく探索され、各経路の選択確率が計算された後、処理は、図１４のステップＳ６４に進む。
【０１９３】
ステップＳ６４において、目的地予測部５５は、ユーザの目的地を予測する。具体的には、目的地予測部５５は、最初に、目的地候補を列挙する。目的地予測部５５は、ユーザの行動状態が滞在状態となる場所を目的地候補とする。そして、目的地予測部５５は、列挙した目的地候補のうち、行動予測部５４により探索された経路上にある目的地候補を目的地に決定する。
【０１９４】
ステップＳ６５において、目的地予測部５５は、目的地ごとの到達確率を計算する。即ち、目的地予測部５５は、複数の経路が存在する目的地については、その複数の経路の選択確率の和を、目的地の到達確率として計算する。１つの経路しかない目的地については、経路の選択確率が、そのまま、目的地の到達確率とされる。
【０１９５】
ステップＳ６６で、目的地予測部５５は、予測された目的地の数が所定個数より多いかを判定する。ステップＳ６６で、予測された目的地の数が所定個数より多いと判定された場合、処理はステップＳ６７に進み、目的地予測部５５は、表示部１８に表示する所定個数の目的地を決定する。例えば、目的地予測部５５は、目的地の到達確率の高い順に、所定個数の経路を決定することができる。
【０１９６】
一方、ステップＳ６６で、予測された目的地の数が所定個数以下であると判定された場合、ステップＳ６７はスキップされる。即ち、この場合、予測された目的地のすべてが表示部１８に表示される。
【０１９７】
ステップＳ６８において、目的地予測部５５は、行動予測部５４によって探索された経路から、予測された目的地を含む経路を抽出する。複数の目的地が予測されている場合には、予測された目的地それぞれについて、経路が抽出される。
【０１９８】
ステップＳ６９において、目的地予測部５５は、抽出された経路の数が提示数として予め設定された所定個数より多いかを判定する。
【０１９９】
ステップＳ６９で、抽出された経路の数が所定個数より多いと判定された場合、処理はステップＳ７０に進み、目的地予測部５５は、表示部１８に表示する所定個数の経路を決定する。例えば、目的地予測部５５は、選択される可能性の高い順に、所定個数の経路を決定することができる。
【０２００】
一方、ステップＳ６９で、抽出された経路の数が所定個数以下であると判定された場合、ステップＳ７０の処理がスキップされる。即ち、この場合、目的地に到達するための全ての経路が表示部１８に表示される。
【０２０１】
ステップＳ７１において、目的地予測部５５は、表示部１８に表示すると決定された各経路の到達時間を計算し、目的地の到達確率および目的地までの経路と到達時間を表示する画像の信号を表示部１８に供給する。
【０２０２】
ステップＳ７２において、表示部１８は、目的地予測部５５から供給される画像の信号に基づいて、目的地の到達確率および目的地までの経路と到達時間を表示して、処理を終了する。
【０２０３】
以上のように、図１０の予測システム１によれば、位置および移動速度の時系列データから、目的地を予測し、かつ、目的地の到達確率および目的地までの経路と到達時間を算出してユーザに提示することができる。
【０２０４】
［先願２の方法による問題］
先願２の方法において、一般に、HMMによる学習モデルは、入力された位置の時系列データについて、単なる緯度経度の値を学習するのではなく、その前後関係の時間的つながりをも学習するものである。従って、例えば、ある目的地を往復する移動経路をHMMに学習させた場合に、行きと帰りのいずれにおいても通過する共通地点については、行きと帰りを区別して異なるノードが割り当てられると考えられていた。
【０２０５】
しかし、学習モデル（HMM）に設定する初期状態やノードの数、時系列データのサンプリング間隔などの設定条件によっては、行きと帰りを区別して異なるノードが割り当てられない場合があった。これにより、例えば、予測処理において、帰路の途中、共通地点から出発地点に引き返すように経路を予測するなどということがあった。
【０２０６】
＜３．本発明の第１の実施の形態＞
そこで、帰路の途中、共通地点から出発地点に引き返すように経路を予測することを防ぎ、上述した先願２の方法よりも、より正確に、現時刻以降の将来に、現時刻以降の将来の経路および経過時間を予測することができる実施の形態について説明する。即ち、本発明の実施の形態について説明する。
【０２０７】
［本発明の第１の実施の形態のブロック図］
図１５は、本発明を適用した予測システムの第１の実施の形態のブロック図である。
【０２０８】
図１５において、上述した図１と対応する部分には同一の符号を付してあり、その説明は適宜省略する。
【０２０９】
図１に示した予約システム１では、位置（緯度経度）の時系列データのみに基づいて、ユーザの活動状態が学習された。これに対して、図１５の予約システム１００では、位置の時系列データと、時刻の時系列データの２つの時系列データに基づいて、ユーザの活動状態が学習される。なお、本実施の形態においても学習モデルとしては、スパース制約を与えたHMMが採用される。
【０２１０】
図１５の予測システム１００は、位置取得部１１、行動認識部１４、行動予測部１５、到達時間予測部１６、操作部１７、表示部１８、時刻取得部１１１、時系列データ記憶部１１２、およびマルチストリーム入力行動学習部１１３により構成される。
【０２１１】
時刻取得部１１１は、学習処理においては、現在時刻を順次取得し、時系列データ記憶部１１２に供給する。一方、時刻取得部１１１は、予測処理においては、現在時刻を順次取得し、行動認識部１４に供給する。位置取得部１１が、たとえば、GPSセンサで構成されている場合、一般的に、GPSセンサは時刻も取得できるので、時刻取得部１１１も、GPSセンサにより構成することができる。勿論、その他の時計機能を有する装置やセンサを使用することも可能である。
【０２１２】
時系列データ記憶部１１２は、位置取得部１１から供給される位置の時系列データと、時刻取得部１１１から供給される時刻の時系列データを記憶する。そして、時系列データ記憶部１１２は、マルチストリーム入力行動学習部１１３に、時刻と位置の時系列データを供給する。
【０２１３】
マルチストリーム入力行動学習部１１３は、位置の時系列データと、時刻の時系列データとに基づいて、ユーザの活動状態を確率的状態遷移モデルにより学習し、その結果得られるパラメータλを行動認識部１４および行動予測部１５に供給する。
【０２１４】
ここで、位置の時系列データと時刻の時系列データは、異なる性質の時系列データであるため、マルチストリーム入力行動学習部１１３は、図１１の統合学習部６２と同様、マルチストリームHMMのパラメータλを学習する。即ち、上述した第１の事象の時系列データが位置の時系列データに対応し、第２の事象の時系列データが時刻の時系列データに対応する。
【０２１５】
行動認識部１４には、予測処理において、位置取得部１１から位置の時系列データと、時刻取得部１１１から時刻の時系列データが供給される。
【０２１６】
行動認識部１４は、学習により得られたユーザ活動モデル（マルチストリームHMM）により、ユーザの現在地に対応する、ユーザの現在の活動状態を認識する。行動予測部１５は、認識されたユーザの現在地から経路を探索する。到達時間予測部１６は、行動予測部１５によって探索された経路から、ユーザが指定した目的地を含む経路を抽出し、抽出された各経路について目的地までの時間を予測する。
【０２１７】
図１５の予測システム１００による学習処理は、学習対象のユーザ活動モデルを表す確率的状態遷移モデルがマルチストリームHMMである点以外は図８と同様であるので、その説明を省略する。
【０２１８】
また、図１５の予測システム１００による予測処理も、ユーザ活動モデルがマルチストリームHMMである点以外は図９と同様であるので、その説明を省略する。
【０２１９】
図１５の予測システム１００の第１の実施の形態によれば、予測処理において、リアルタイムに供給される位置と時刻の時系列データに最も近い状態ノードがユーザの現在の活動状態として認識される。例えば、学習モデルは、行きと帰りでは異なる時刻として学習しているので、行きと帰りでは、別々の状態ノードが認識される。従って、リアルタイムに取得される現在時刻に最も近い状態ノードを探索することにより、行きの移動中において、帰りの経路を予測するようなことはない。即ち、現時刻以降の将来の経路および経過時間を、より正確に予測することができ、また、そのための学習パラメータを学習することができる。
【０２２０】
＜４．本発明の第２の実施の形態＞
［本発明の第２の実施の形態のブロック図］
次に、本発明を適用した予測システムの第２の実施の形態について説明する。
【０２２１】
図１６は、本発明を適用した予測システムの第２の実施の形態のブロック図である。
【０２２２】
図１６において、上述した図１５と対応する部分には同一の符号を付してあり、その説明は適宜省略する。
【０２２３】
図１５に示した予測システム１００の第１の実施の形態では、位置と時刻の時系列データのみに基づいて、ユーザの活動状態がスパース制約を与えたHMMにより学習された。さらに、ユーザの活動状態を学習する学習モデルに、より多くの情報を与えれば、より詳しく、ユーザの活動状態を識別することができる。
【０２２４】
そこで、図１６の予測システム１００の第２の実施の形態では、マルチストリームHMMは、時刻と位置の時系列データ以外の、曜日、交通状況、気象状況などの付加情報の時系列データも入力として受け付け、学習する。
【０２２５】
図１６の予測システム１００は、図１５の予測システム１００と比較して、曜日取得部１２１、交通状況取得部１２２、および気象状況取得部１２３が新たに設けられている。また、図１５の時系列データ記憶部１１２およびマルチストリーム入力行動学習部１１３に代えて、時系列データ記憶部１２４およびマルチストリーム入力行動学習部１２５が設けられている。
【０２２６】
曜日取得部１２１は、現時点の曜日を一定間隔で順次取得する。学習処理では、取得された曜日の時系列データは、時系列データ記憶部１２４に供給される。一方、予測処理では、取得された曜日の時系列データは、行動認識部１４に供給される。
【０２２７】
交通状況取得部１２２は、現時点の交通状況を一定間隔で順次取得する。学習処理では、取得された交通状況の時系列データは、時系列データ記憶部１２４に供給される。一方、予測処理では、取得された交通状況の時系列データは、行動認識部１４に供給される。
【０２２８】
気象状況取得部１２３は、現時点の気象状況を一定間隔で順次取得する。学習処理では、取得された気象状況の時系列データは、時系列データ記憶部１２４に供給される。一方、予測処理では、取得された気象状況の時系列データは、行動認識部１４に供給される。
【０２２９】
曜日取得部１２１、交通状況取得部１２２、および気象状況取得部１２３は、例えば、曜日、交通状況、および気象状況の各情報を提供するサーバに接続し、それらの情報を取得する通信装置により構成することができる。なお、位置取得部１１、時刻取得部１１１、曜日取得部１２１、交通状況取得部１２２、および気象状況取得部１２３のそれぞれが情報を取得するときの取得間隔は、同一である必要はない。
【０２３０】
時系列データ記憶部１２４は、各部から供給される、位置、時刻、曜日、交通状況、および気象状況の時系列データを記憶し、マルチストリーム入力行動学習部１２５に供給する。
【０２３１】
なお、本実施の形態では、位置および時刻の時系列データ以外に、曜日、交通状況、および気象状況の３つの時系列データをマルチストリーム入力行動学習部１２５に入力するものとするが、曜日、交通状況、および気象状況のいずれか１つまたは２つでもよい。
【０２３２】
曜日、交通状況、および気象状況の各時系列データは、独立に行動認識部１４および時系列データ記憶部１２４に供給される。ただし、図１６では、図を見やすくするため、時系列データの供給線を１本に統合して示している。この点については、後述する図１７についても同様である。
【０２３３】
マルチストリーム入力行動学習部１２５は、入力される複数のマルチストリームに基づいて、ユーザの活動状態を確率的状態遷移モデルにより学習し、その結果得られるパラメータλを行動認識部１４および行動予測部１５に供給する。即ち、マルチストリーム入力行動学習部１２５には、位置、時刻、曜日、交通状況、および気象状況の時系列データが供給され、５つのマルチストリームを入力とするマルチストリームHMMの学習を行う。
【０２３４】
予測システム１００の第２の実施の形態における学習処理および予測処理は、図１５の第１の実施の形態と同様である。
【０２３５】
図１６の予測システム１００の第２の実施の形態によれば、時刻と位置の時系列データ以外の、曜日、交通状況、気象状況などの付加情報の時系列データも含めて、学習処理および予測処理が実行される。従って、上述した時刻の時系列データで判別可能な行きと帰り以外に、例えば、曜日によって移動経路が異なる場合、天気や渋滞状況によって移動経路が異なる場合などにおいて、別々の状態ノードとして認識させることができる。具体的には、自宅から最寄り駅に向かって移動している場合、平日であれば、会社を目的地と予測し、休日であれば会社以外の場所を目的地とすることが可能である。
【０２３６】
即ち、予測システム１００の第２の実施の形態によれば、現時刻以降の将来の経路および経過時間を、より正確に予測することができ、また、そのための学習パラメータを学習することができる。
【０２３７】
しかし、マルチストリームHMMに入力し、学習させる時系列データ（ストリーム）の数が増えると、当然ながら、状態ノードの数も増やす必要があり、学習にかかる時間も増大する。曜日、交通状況、気象状況などの付加情報について、所定の条件ごとに時刻と位置の時系列データを分類し、条件ごとに個別に学習モデルを学習し、現時点の条件に合致する学習モデルを選択して予測する方法があるが、各学習モデルのノード数の総数と同程度の数が必要になる。
【０２３８】
また、ユーザの行動を決定する上での、曜日などの付加情報の時系列データの重み（式（７）の重みｗｘ，ｗｙに相当）は、時刻と位置の時系列データと同じではなく、また、ユーザや、行動の種類、日によってその重みが変わることも考えられる。
【０２３９】
＜５．本発明の第３の実施の形態＞
そこで、学習モデル（マルチストリームHMM）には、時刻と位置の時系列データのみを入力として学習させ、曜日、交通状況、気象状況などの付加情報を付加的な条件として与えることにより、付加情報を考慮し、かつ、より簡単、正確に、予測することができる実施の形態について説明する。
【０２４０】
［本発明の第３の実施の形態のブロック図］
図１７は、本発明を適用した予測システムの第３の実施の形態のブロック図である。
【０２４１】
図１７において、上述した図１５または図１６と対応する部分には同一の符号を付してあり、その説明は適宜省略する。
【０２４２】
図１７の予測システム１００の第３の実施の形態では、供給される時系列データから、学習モデルのパラメータλを求める学習装置は、時系列データ記憶部１４１、マルチストリーム入力行動学習部１１３、および状態系列生成部１４２を含んで構成される。
【０２４３】
一方、供給される時系列データから、ユーザの目的地までの経路とその到達時間を予測する予測装置は、状態系列分類部１４３、パラメータ再計算部１４４、行動認識部１４５、行動予測部１４６を含んで構成される。
【０２４４】
時系列データ記憶部１４１は、学習処理において、各部から供給される、位置、時刻、曜日、交通状況、および気象状況の時系列データを記憶する。時系列データ記憶部１４１は、位置および時刻の時系列データを、マルチストリーム入力行動学習部１１３に供給し、曜日などの付加情報の時系列データを、状態系列分類部１４３に供給する。
【０２４５】
マルチストリーム入力行動学習部１１３は、上述した第１の実施の形態と同様に、位置と時刻の時系列データに基づいて、ユーザ活動モデルを学習する。ユーザ活動モデルとしては、確率的状態遷移モデルとしてのマルチストリームHMMが採用される。学習の結果得られたマルチストリームHMMのパラメータλは、状態系列生成部１４２に供給される。
【０２４６】
状態系列生成部１４２は、時系列データ記憶部１４１から供給される位置と時刻の時系列データを、認識された状態ノードの時系列データ（以下、状態系列データとも称する。）に変換して、状態系列分類部１４３に供給する。具体的には、状態系列生成部１４２は、マルチストリーム入力行動学習部１１３から供給されたパラメータλに基づくユーザ活動モデルから、ユーザのその時点での活動状態を認識する。そして、状態系列生成部１４２は、認識結果としてのユーザの状態ノードを、順次、状態系列分類部１４３に供給する。
【０２４７】
状態系列分類部１４３には、学習処理において、時系列データ記憶部１４１から、曜日などの付加情報の時系列データと、位置および時刻の時系列データが供給される。また、状態系列分類部１４３には、学習処理において、付加情報を含む位置および時刻の時系列データに対応する状態系列データが、状態系列生成部１４２から供給される。
【０２４８】
状態系列分類部１４３は、付加情報を含む位置および時刻の時系列データと状態系列データとを対応付けて、内部の記憶部に記憶する。これにより、状態系列分類部１４３は、学習データとして使用された位置および時刻の時系列データに対応する状態系列データが、どのような付加条件（付加情報により決定される条件）のときのデータであるかを認識している。
【０２４９】
一方、予測処理では、状態系列分類部１４３に、リアルタイムの付加情報の時系列データが供給される。即ち、状態系列分類部１４３に、曜日取得部１２１、交通状況取得部１２２、および気象状況取得部１２３から、それぞれ、現時点の曜日、交通状況、および気象状況の時系列データが供給される。
【０２５０】
状態系列分類部１４３は、学習処理時に記憶しておいた状態系列データと位置および時刻の時系列データのなかから、供給されるリアルタイムの付加条件に合致する状態系列データと位置および時刻の時系列データのみを選択し、パラメータ再計算部１４４に供給する。
【０２５１】
パラメータ再計算部１４４は、予測処理において、統計的処理のみによってマルチストリームHMMのパラメータλを再計算する。即ち、パラメータ再計算部１４４は、全ての付加条件の位置と時刻の時系列データに対して求めたマルチストリームHMMのパラメータλを、現時点の付加情報に合致する位置と時刻の時系列データのみを用いて再計算する。なお、実際には、現時点の付加情報に合致する位置と時刻の時系列データに対応する状態系列データを用いてパラメータλが再計算される。パラメータ再計算部１４４のパラメータ再計算処理によって計算されたパラメータλを、再計算パラメータλ’とする。
【０２５２】
以上のように、状態系列分類部１４３とパラメータ再計算部１４４は、予測処理に使用される学習モデルのパラメータを計算するものであることから、状態系列分類部１４３とパラメータ再計算部１４４は、学習装置の一部であるということもできる。
【０２５３】
行動認識部１４５には、予測処理において、位置取得部１１から位置の時系列データと、時刻取得部１１１から時刻の時系列データが供給される。行動認識部１４５は、パラメータ再計算部１４４から供給された再計算パラメータλ’によるユーザ活動モデル（マルチストリームHMM）を用いて、ユーザの現在地に対応する、ユーザの現在の活動状態を認識する。従って、行動認識部１４５は、位置の時系列データと時刻の時系列データのみを用いて、ユーザの現在の活動状態を認識する。
【０２５４】
行動予測部１４６は、パラメータ再計算部１４４から供給された再計算パラメータλ’によるユーザ活動モデルを用いて、ユーザの現在地から取り得る経路を探索する。到達時間予測部１６は、行動予測部１５によって探索された経路から、ユーザが指定した目的地を含む経路を抽出し、抽出された各経路について目的地までの時間を予測する。
【０２５５】
［パラメータ再計算部１４４の構成例］
図１８は、パラメータ再計算部１４４の詳細構成例を示している。
【０２５６】
パラメータ再計算部１４４は、現時点の付加情報に合致する位置と時刻の時系列データに対応する状態系列データを用いてパラメータλを再計算する。
【０２５７】
パラメータ再計算部１４４は、遷移頻度カウント部１６１、遷移パラメータ計算部１６２、状態頻度カウント部１６３、時系列データ分類部１６４、および観測パラメータ計算部１６５により構成されている。
【０２５８】
遷移頻度カウント部１６１は、状態系列分類部１４３から供給される状態系列データを対象として、各状態遷移の頻度をカウントする。即ち、遷移頻度カウント部１６１は、状態ノードsiから状態ノードsjに移動する経路の頻度（カウント値）をｎｉｊと表すと、状態系列分類部１４３から供給される状態系列データを対象として、各状態遷移の頻度ｎｉｊ（ｉ＝１乃至Ｎ，ｊ＝１乃至Ｎ，Ｎは、時系列データの最後のノード番号（＝ノード数））を求める。
【０２５９】
遷移パラメータ計算部１６２は、HMMの状態遷移確率aijに対応する遷移パラメータを計算する。具体的には、遷移パラメータ計算部１６２は、遷移頻度カウント部１６１から供給される各状態遷移の頻度ｎｉｊを基に、式（８）により、遷移確率Aｉｊを計算する。
【０２６０】
【数８】
2011118777.tif 000010
【０２６１】
式（８）により、状態遷移が生じていない遷移確率Aｉｊはゼロとなる。通常のHMMを用いた学習モデルでは、繰り返し回数を十分に大きくしなければ、過去発生しなかった遷移の確率を小さくすることができない。しかし、式（８）によれば、状態遷移が生じていない遷移確率Aｉｊをゼロとすることができるという特徴がある。この特徴は、将来の経路の可能性を探索していくアルゴリズムにおいて、不要な経路の探索を削減するために重要なメリットとなる。
【０２６２】
遷移パラメータ計算部１６２は、計算された遷移確率Aｉｊを、HMMの状態遷移確率aijに対応する遷移パラメータとして出力する。
【０２６３】
状態頻度カウント部１６３は、状態系列分類部１４３から供給される状態系列データを対象として、状態頻度をカウントする。即ち、状態頻度カウント部１６３は、状態系列分類部１４３から供給される状態系列データを対象として、各状態ノードsiの総数cntiをカウントする。カウント結果である各状態ノードsiの総数cntiは、観測パラメータ計算部１６５に供給される。
【０２６４】
時系列データ分類部１６４には、状態系列分類部１４３から、状態系列データと位置および時刻の時系列データが供給される。
【０２６５】
時系列データ分類部１６４は、状態系列分類部１４３からから順次供給される位置データｘを、状態ノードごとに分類し、グループ化する。状態siにおける位置データの集合データXｉは、次式（９）で表すことができる。
【０２６６】
【数９】
2011118777.tif 000011
【０２６７】
状態ノードsiの総数がcntiであるので、集合データXｉの要素の個数はcntiとなる。なお、集合データXｉの各要素である位置のデータｘは、詳しくは、緯度と経度からなる２次元のデータであるが１次元のように省略して表している。
【０２６８】
また、時系列データ分類部１６４は、状態系列分類部１４３からから順次供給される時刻データｔを、状態ノードごとに分類し、グループ化する。状態ノードsiにおける時刻データの集合データTｉは、次式（１０）で表すことができる。
【０２６９】
【数１０】
2011118777.tif 000012
【０２７０】
式（１０）における集合データTｉの要素の個数もcntiである。
【０２７１】
時系列データ分類部１６４は、以上のように、位置と時刻の時系列データを状態ノードごとに分類した分類結果を観測パラメータ計算部１６５に供給する。換言すれば、時系列データ分類部１６４は、各状態ノードの集合データXと集合データTを観測パラメータ計算部１６５に供給する。
【０２７２】
観測パラメータ計算部１６５は、位置と時刻の時系列データそれぞれの観測パラメータを計算する。
【０２７３】
位置の時系列データの観測パラメータとして、観測パラメータ計算部１６５は、状態頻度カウント部１６３からの状態ノードsiの総数cntiと時系列データ分類部１６４からの集合データXｉを用いて、状態ノードsiの平均値μ1ｉと標準偏差σ1ｉを計算する。
【０２７４】
【数１１】
2011118777.tif 000013
【０２７５】
この状態ノードsiの平均値μ1ｉと標準偏差σ1ｉは、状態ノードsiにおける位置データｘの観測確率であり、上述したマルチストリーム入力行動学習部１１３（図１７）が出力するマルチストリームHMMの出力確率密度関数b1ｉ（ｘ）に対応する。
【０２７６】
また、観測パラメータ計算部１６５は、時刻の時系列データの観測パラメータとして、状態頻度カウント部１６３からの状態ノードsiの総数cntiと時系列データ分類部１６４からの集合データTｉを用いて、状態ノードsiの平均値μ2ｉと標準偏差σ2ｉを計算する。
【０２７７】
【数１２】
2011118777.tif 000014
【０２７８】
この状態ノードsiの平均値μ2ｉと標準偏差σ2ｉは、状態ノードsiにおける時刻データｔの観測確率であり、上述したマルチストリーム入力行動学習部１１３（図１７）が出力するマルチストリームHMMの出力確率密度関数b2ｉ（ｘ）に対応する。
【０２７９】
なお、要素数が少ない場合を考慮して、標準偏差σ1ｉおよびσ2ｉについては、所定の値よりも大きいようにする制約を設けてもよい。あるいは、マルチストリーム入力行動学習部１１３で学習された標準偏差を流用するようにしてもよい。
【０２８０】
パラメータ再計算部１４４は、以上の構成を採用することにより、状態系列生成部１４２から供給される状態系列データと位置および時刻の時系列データから、マルチモーダルの確率的状態遷移モデルのパラメータを演算することができる。
【０２８１】
［予測システム１００の第３の実施の形態における学習処理］
次に、図１９のフローチャートを参照して、予測システム１００の第３の実施の形態における学習処理について説明する。なお、この処理の開始前には、学習データとしての、付加情報を含む位置および時刻の時系列データが時系列データ記憶部１４１に既に記憶されているものとする。
【０２８２】
初めに、ステップＳ１０１において、マルチストリーム入力行動学習部１１３は、時系列データ記憶部１４１に記憶されている位置と時刻の時系列データに基づいて、ユーザ活動モデルを学習する。即ち、マルチストリーム入力行動学習部１１３は、時系列データ記憶部１４１に記憶されている位置と時刻の時系列データに基づいて、マルチストリームHMMのパラメータλを算出する。算出されたマルチストリームHMMのパラメータλは、状態系列生成部１４２に供給される。
【０２８３】
ステップＳ１０２において、状態系列生成部１４２は、マルチストリーム入力行動学習部１１３から供給されたパラメータλでなるユーザ活動モデルに基づいて、時系列データ記憶部１４１からの位置と時刻の時系列データを、状態系列データに変換して、状態系列分類部１４３に供給する。
【０２８４】
ステップＳ１０３において、時系列データ記憶部１４１は、状態系列生成部１４２に供給した位置と時刻の時系列データを、付加情報も含めた形で、状態系列分類部１４３に供給する。状態系列分類部１４３は、時系列データ記憶部１４１からの付加情報を含む位置および時刻の時系列データと、状態系列生成部１４２からの状態系列データとを対応付けて、内部の記憶部に記憶し、学習処理を終了する。
【０２８５】
［予測システム１００の第３の実施の形態における学習処理］
次に、図２０のフローチャートを参照して、予測システム１００の第３の実施の形態における予測処理について説明する。
【０２８６】
初めに、ステップＳ１２１において、状態系列分類部１４３は、現時点の付加情報を取得する。そして、ステップＳ１２２において、状態系列分類部１４３は、学習処理時に記憶しておいた状態系列データと位置および時刻の時系列データから、現時点の付加情報に合致する状態系列データと位置および時刻の時系列データのみを選択し、パラメータ再計算部１４４に供給する。
【０２８７】
ステップＳ１２３において、パラメータ再計算部１４４は、現時点の付加情報に合致するように、学習処理においてマルチストリーム入力行動学習部１１３が計算したマルチストリームHMMのパラメータλを再計算するパラメータ再計算処理を実行する。パラメータ再計算処理では、選択された状態系列データと位置および時刻の時系列データを用いた統計的処理によって、マルチストリームHMMのパラメータλが再計算される。パラメータ再計算部１４４は、再計算により得られた再計算パラメータλ’を、行動認識部１４５と行動予測部１４６に供給する。
【０２８８】
ステップＳ１２４において、行動認識部１４５は、位置取得部１１から供給される位置の時系列データと、時刻取得部１１１から供給される時刻の時系列データを取得する。
【０２８９】
ステップＳ１２５において、行動認識部１４５は、パラメータ再計算部１４４から供給された再計算パラメータλ’によるユーザ活動モデルを用いて、ユーザの現在の活動状態を表す状態ノードを認識することで、ユーザの現在地を認識する。この処理は、上述したステップＳ２２（図８）の処理と同様である。
【０２９０】
ステップＳ１２６において、行動予測部１４６は、パラメータ再計算部１４４から供給された再計算パラメータλ’によるユーザ活動モデルを用いて、ユーザの現在地から取り得る経路を探索する。また、行動予測部１４６は、探索された各経路の選択確率を計算する。この処理は、上述したステップＳ２３乃至Ｓ３３（図８）の処理と同様である。
【０２９１】
ステップＳ１２７において、到達時間予測部１６は、行動予測部１４６によって探索された経路から、入力された目的地を含む経路を抽出し、目的地の到達確率を算出する。また、到達時間予測部１６は、目的地までの各経路の到達時間を計算する。この処理は、上述したステップＳ３４乃至Ｓ３７（図８）の処理と同様である。
【０２９２】
ステップＳ１２８において、表示部１８は、目的地の到達確率および目的地までの経路と到達時間を表示して、処理を終了する。この処理は、上述したステップＳ３８（図８）の処理と同様である。
【０２９３】
［パラメータ再計算処理］
次に、図２１のフローチャートを参照して、図２０のステップＳ１２３におけるパラメータ再計算処理について説明する。
【０２９４】
初めに、ステップＳ１４１において、遷移頻度カウント部１６１は、状態系列分類部１４３から供給される状態系列データを対象として、各状態遷移の頻度ｎｉｊをカウントする。即ち、遷移頻度カウント部１６１は、状態ノードsiから状態ノードsjに移動する経路の頻度（カウント値）をｎｉｊと表すと、状態系列分類部１４３から供給される状態系列データを対象として、各状態遷移の頻度ｎｉｊ（ｉ＝１乃至Ｎ，ｊ＝１乃至Ｎ，Ｎは、時系列データの最後のノード番号（＝ノード数））を求める。
【０２９５】
ステップＳ１４２において、遷移パラメータ計算部１６２は、HMMの状態遷移確率aijに対応する遷移パラメータAｉｊを計算する。具体的には、遷移パラメータ計算部１６２は、遷移頻度カウント部１６１から供給される各状態遷移の頻度ｎｉｊを基に、式（８）により、遷移確率Aｉｊを計算する。
【０２９６】
ステップＳ１４３において、状態頻度カウント部１６３は、状態系列分類部１４３から供給される状態系列データを対象として、状態頻度cntiをカウントする。即ち、状態頻度カウント部１６３は、状態系列分類部１４３から供給される状態系列データを対象として、各状態ノードsiの総数cntiをカウントする。カウント結果である各状態ノードsiの総数cntiは、観測パラメータ計算部１６５に供給される。
【０２９７】
ステップＳ１４３の処理は、上述したステップＳ１４１およびＳ１４２の処理より先に実行してもよいし、ステップＳ１４１およびＳ１４２の処理と並行して実行してもよい。
【０２９８】
ステップＳ１４４において、時系列データ分類部１６４は、状態系列分類部１４３からから位置および時刻の時系列データを、状態ノードごとに分類する。即ち、時系列データ分類部１６４は、状態系列分類部１４３からから順次供給される位置データｘを、状態ノードごとに分類し、グループ化する。また、時系列データ分類部１６４は、状態系列分類部１４３からから順次供給される時刻データｔを、状態ノードごとに分類し、グループ化する。
【０２９９】
ステップＳ１４５において、観測パラメータ計算部１６５は、位置と時刻の時系列データそれぞれの観測パラメータを計算する。観測パラメータ計算部１６５は、位置の時系列データの観測パラメータとして、状態ノードsiの平均値μ1ｉと標準偏差σ1ｉを計算する。また、観測パラメータ計算部１６５は、時刻の時系列データの観測パラメータとして、状態ノードsiの平均値μ2ｉと標準偏差σ2ｉを計算する。
【０３００】
観測パラメータ計算部１６５は、計算された位置と時刻の時系列データそれぞれの観測パラメータを、行動認識部１４５と行動予測部１４６に供給して、図２０に戻り、ステップＳ１２４に進む。
【０３０１】
図２０および図２１の予測処理において、ステップＳ１２２とＳ１２３の処理はデータの選択と統計処理の演算であるから、再計算パラメータλ’は瞬時に計算することができる。従って、曜日、交通状況、気象状況などの付加情報を付加的な条件を考慮しつつ、目的地までの経路、到達時間等の予測を、より簡単かつ正確に行うことができる。
【０３０２】
＜６．本発明の第４の実施の形態＞
上述した予測システム１００の第１乃至第３の実施の形態は、先願２の予測システム１の第１の構成例に対応する形態である。即ち、目的地はユーザによって指定され、予測システム１００は、指定された目的地の到達確率および目的地までの経路と到達時間を予測する形態である。
【０３０３】
しかし、予測システム１００の第１乃至第３の実施の形態も、目的地をも予測する先願２の予測システム１の第２の構成例に対応する形態とすることが可能である。即ち、予測システム１００の第４の実施の形態は、上述した予測システム１００の第１乃至第３の実施の形態いずれかと予測システム１の第２の構成例との組み合わせで実現できる。
【０３０４】
上述した予測システム１００の第１または第２の実施の形態を、目的地も予測するようにした実施の形態とするためには、位置および時刻の時系列データの他に、移動速度の時系列データを取得し、行動モードの時系列データ（行動モード系列データ）を加えたマルチストリームHMMの学習を行うようにすればよい。そして、予測処理では、入力されたユーザの移動速度の時系列データから行動モードを認識して、滞在状態の場所を目的地として予測することができる。さらに、予測した目的地について到達確率、経路、および到達時間を算出して、ユーザに提示することができる。
【０３０５】
［本発明の第４の実施の形態のブロック図］
図２２は、予測システム１００の第３の実施の形態（図１７）を、目的地も予測するようにした形態（以下、予測システム１００の第４の実施の形態という。）の、パラメータ再計算処理に関係する部分のブロック図を示している。
【０３０６】
予測システム１００の第４の実施の形態では、位置および時刻の時系列データの他に、移動速度の時系列データが取得され、時系列データ１４１に記憶される。そして、図２２に示されるように、時系列データ１４１に記憶された移動速度の時系列データを、行動モードの時系列データ（行動モード系列データ）に変換するための行動モード生成部１８１が新たに設けられる。行動モード生成部１８１は、例えば、図１１の行動モード生成部７２と同様の構成を採用することができる。
【０３０７】
状態系列分類部１４３は、付加情報を含む位置および時刻の時系列データと、行動モード系列データおよび状態系列データとを対応付けて、内部の記憶部に記憶する。
【０３０８】
そして、予測処理において、状態系列分類部１４３は、供給されるリアルタイムの付加条件に合致する、行動モード系列データおよび状態系列データ、並びに、位置および時刻の時系列データを選択し、パラメータ再計算部１４４に供給する。状態系列データは、パラメータ再計算部１４４の、遷移頻度カウント部１６１、状態頻度カウント部１６３、および時系列データ分類部１６４に供給される。位置および時刻の時系列データと行動モード系列データは、時系列データ分類部１６４に供給される。
【０３０９】
パラメータ再計算部１４４における位置と時刻の時系列データの観測パラメータは、上述した式（１１）乃至式（１４）で計算される。
【０３１０】
一方、行動モードの時系列データの観測パラメータは、次のようにして計算される。
【０３１１】
時系列データ分類部１６４は、状態系列分類部１４３からから順次供給される行動モードｍを、状態ノードごとに分類し、グループ化する。状態ノードsiにおける行動モードｍの集合データMｉは、次式（１５）で表すことができる。
【０３１２】
【数１３】
2011118777.tif 000015
【０３１３】
式（１５）における集合データMｉの要素の個数もcntiである。
【０３１４】
観測パラメータ計算部１６５は、行動モードの時系列データの観測パラメータとして、状態ノードsiにおける行動モードの集合データMｉに対し、次式（１６）で表される各行動モードｍの出現頻度Ｐ（ｓｉ｜ｍ）を算出する。
【０３１５】
【数１４】
2011118777.tif 000016
【０３１６】
式（１６）において、N（Mｉ＝ｍ）は、集合データMｉのなかでの行動モードｍの個数を表す。なお、上述した式（１１）乃至（１４）のように、平均値と標準偏差ではなく、確率で求められるのは、行動モードが連続量ではなく離散値であるためである。
【０３１７】
観測パラメータ計算部１６５は、位置および時刻の時系列データと行動モードの観測確率である、各状態の平均値μ1ｉと標準偏差σ1ｉおよび平均値μ2ｉと標準偏差σ2ｉの他、出現頻度Ｐ（ｓｉ｜ｍ）を、観測パラメータとして出力する。
【０３１８】
予測システム１００の第４の実施の形態における予測処理では、以上のようにして再計算されたパラメータλ’を用いて、目的地予測部５５（図１０）が目的地を予測し、目的地ごとの到達確率を算出する。
【０３１９】
＜７．本発明の実施の形態の検証実験結果の説明＞
［予測システム１００の第１の実施の形態の検証］
図２３乃至図３３を参照して、本発明を適用した予測システム１００の効果について説明する。なお、図２３乃至図３３に示す実験は、移動速度の時系列データも入力ストリームとして学習モデル（マルチストリームHMM）に与え、目的地も予測するようにした実施の形態により行った。
【０３２０】
最初に、図２３と図２４を参照して、先願２の予測システムの第２の構成例（図１０）と、予測システム１００の第１の実施の形態（図２２）を移動速度の時系列データも入力ストリームとして目的地も予測するようにした実施の形態とを比較する。
【０３２１】
図２３は、図１０に示した先願２の予測システムの第２の構成例による予測結果を示している。即ち、図１０の予測システム１が、ユーザの現在地から、目的地、並びに、目的地までの経路、到達確率、および到達時間を予測した結果を示している。
【０３２２】
一方、図２４は、予測システム１００の第１の実施の形態（図１５）を移動速度の時系列データも入力ストリームとして目的地も予測するようにした実施の形態による予測結果を示している。
【０３２３】
図２３および図２４において、実際のユーザの行動（予測結果に対応する真値）として、現在地から、矢印で示される進行方向に従ってコンビニエンスストア（以下、コンビニと称する。）より先にある自宅に向かっていることがわかっている。
【０３２４】
予測システム１は、図２３に示されるように、予測結果として、会社の方に５０％の確率で５．５分後に戻るか、あるいは、コンビニに５０％の確率で３．９分後に寄り道することを出力している。
【０３２５】
従って、予測システム１は、現在値に対応する状態ノードか、あるいは、現在地から予測された将来通過するだろう状態ノードのいずれかが、行きと帰りの両方の経路を共有するため、現在地の状態ノードから逆向きの経路を予測して、会社へ戻ることも予測している。
【０３２６】
これに対して、図２４に示される予測システム１００は、現在地から、自宅に１００％の確率で、１０分後に到達することを予測している。予測システム１００では、行きと帰りで時刻が異なることを利用して、行きと帰りでは、同じ地点に対して別々の状態ノードが割り振られる。従って、予測を行った時刻は０時２０分であるが、現在地に対応する状態ノードには、単に緯度経度が近いというだけではなく、時刻０時ごろにある状態ノードが選ばれる。その結果、帰り道の予測のみを行うように、予測結果が改善されている。
【０３２７】
［予測システム１００の第３の実施の形態の検証］
次に、図２５乃至図３３を参照して、予測システム１００の第１の実施の形態（図１５）を移動速度の時系列データも入力ストリームとして目的地も予測するようにした形態と、予測システム１００の第４の実施の形態（図２２）とを比較する。
【０３２８】
図２５は、予測システム１００の第１の実施の形態（図１５）を目的地も予測するようにした形態において、学習処理後のユーザ行動モデルを地図上に示した図である。この学習データには、平日と休日の両方のユーザの行動が含まれているが、第１の実施の形態では、平日と休日を区別した学習はできない。
【０３２９】
図２５の学習処理後のユーザ行動モデルを参照すると、ユーザの主な目的地として、自宅、会社、のほかに、目的地１、目的地２、目的地３などが検出されている。
【０３３０】
図２６は、図２５のユーザ行動モデルを用いて、ある「平日」のユーザの行動を予測した予測結果を示している。
【０３３１】
図２６においては、実際のユーザの行動（予測結果に対応する真値）として、ユーザは、現在地から目的地１へ向かって矢印の進行方向に従って進んでいることがわかっている。
【０３３２】
目的地も予測する予測システム１００の第１の実施の形態で予測処理を行った予測結果は、次の通りである。
（１）  目的地１に１７％の到達確率で、１４．８分後に到着
（２）  目的地３に６％の到達確率で、５０．７分後に到着
（３）  目的地４に１１％の到達確率で、１３分後に到着
（４）  目的地５に１７％の到達確率で、１１．４分後に到着
【０３３３】
図２３の予測結果のような、来た道を逆向きに戻るような予測は無いものの、真値である目的地１の到達確率が低く、必ずしもよい予測結果とはいえない。
【０３３４】
図２７は、図２６の予測結果を、状態遷移が見易いように書き換えた図である。
【０３３５】
図２７の黒い太線は、現在地ノードまでに経由した状態ノード（通過経路）を表している。また、グレイの太線は、予測経路であり、予測経路の先の丸が目的地の状態ノードである。黒い細線は、状態ノード間の接続を表す。
【０３３６】
図２７によれば、現在地よりも左側の予測経路が入り組んでいて、これが複数の目的地、予測経路を表示する原因になっていることがわかった。
【０３３７】
図２８は、予測システム１００の第４の実施の形態（図２２）で、「平日」の状態系列データについてパラメータを再計算したときの学習処理後のユーザ行動モデルを地図上に示した図である。
【０３３８】
図２８では、自宅と会社を行き来するような経路のみが出現しており、このユーザの場合、平日は、ほとんど自宅と会社を行き来するような経路であることが学習されている。また、このユーザ行動モデルでは、平日の夕方に目的地１などに寄り道する経路などが出現している。実際のユーザは、平日であっても、祝日などの理由で会社に行かず、目的地１に行くことがあった。
【０３３９】
これに対して、図２８では、目的地３などに行く経路は出現していない。目的地２については、平日は普通、通り過ぎることがほとんどであり、図２８においても、目的地としては認識されていないような結果となっている。
【０３４０】
図２９は、予測システム１００の第４の実施の形態（図２２）で、「平日」のユーザの行動を予測した予測結果を示している。換言すれば、図２６の現在地と同一の位置から、予測システム１００の第４の実施の形態（図２２）で予測したときの予測結果を示している。
【０３４１】
図２９を参照すると、予測された目的地候補は目的地１のみに絞られている。このように、平日という条件で分類することで、一つの目的地に限定することができた。これは、平日という条件で、ユーザが現在地から移動する場合、目的地１に行って戻る例しか経験しなかったことによる。
【０３４２】
図３０は、図２９の予測結果を、状態遷移が見易いように書き換えた図である。
【０３４３】
図２７と図３０を比較すると、使われている状態ノードが少なくなっていることわかり、特に、現在地から目的地１にかけて、図２７では入り組んでいた部分が簡潔になっていることがわかる。このように、付加情報によってパラメータを再計算させることにより、候補を絞り込むことができ、より正確な予測を行なうことが可能になる。
【０３４４】
図３１は、予測システム１００の第４の実施の形態（図２２）で、「休日」の状態系列データについてパラメータを再計算したときの学習処理後のユーザ行動モデルを地図上に示した図である。
【０３４５】
図３１では、このユーザの学習データでは、休日に会社に行くことは一度も無く、その結果、会社の付近に向かう経路が無いユーザ活動モデルが生成されている。
【０３４６】
図３２は、予測システム１００の第４の実施の形態（図２２）で、「休日」のユーザの行動を予測した予測結果を示している。換言すれば、図２６の現在地と同一の位置から、予測システム１００の第４の実施の形態（図２２）で予測したときの予測結果を示している。
【０３４７】
図３２を参照すると、図２９と同様、予測された目的地候補は目的地１のみに絞られている。
【０３４８】
図３３は、図３２の予測結果を、状態遷移が見易いように書き換えた図である。
【０３４９】
図２９と図３２だけを参照すると、同じような予測結果に見えるが、図３０と図３３を比較すると、「平日」と「休日」で異なる経路で予測されていることがわかる。即ち、「平日」と「休日」でそれぞれ別々の状態系列を予測することが可能であることが確認できる。
【０３５０】
以上のように、本発明を適用した予測システム１００によれば、現時刻以降の将来の経路および経過時間を、より正確に予測することができ、また、そのための学習パラメータを学習することができる。
【０３５１】
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【０３５２】
図３４は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【０３５３】
コンピュータにおいて、CPU（Central Processing Unit）２０１，ROM（Read Only Memory）２０２，RAM（Random Access Memory）２０３は、バス２０４により相互に接続されている。
【０３５４】
バス２０４には、さらに、入出力インタフェース２０５が接続されている。入出力インタフェース２０５には、入力部２０６、出力部２０７、記憶部２０８、通信部２０９、ドライブ２１０、およびGPSセンサ２１１が接続されている。
【０３５５】
入力部２０６は、キーボード、マウス、マイクロホンなどよりなる。出力部２０７は、ディスプレイ、スピーカなどよりなる。記憶部２０８は、ハードディスクや不揮発性のメモリなどよりなる。通信部２０９は、ネットワークインタフェースなどよりなる。ドライブ２１０は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブル記録媒体２１２を駆動する。GPSセンサ２１１は、上述した位置取得部１１および時刻取得部１１１に対応する。
【０３５６】
以上のように構成されるコンピュータでは、CPU２０１が、例えば、記憶部２０８に記憶されているプログラムを、入出力インタフェース２０５及びバス２０４を介して、RAM２０３にロードして実行することにより、上述した一連の処理が行われる。
【０３５７】
コンピュータ（CPU２０１）が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブル記録媒体２１２に記録して提供することができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することができる。
【０３５８】
コンピュータでは、プログラムは、リムーバブル記録媒体２１２をドライブ２１０に装着することにより、入出力インタフェース２０５を介して、記憶部２０８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部２０９で受信し、記憶部２０８にインストールすることができる。その他、プログラムは、ROM２０２や記憶部２０８に、あらかじめインストールしておくことができる。
【０３５９】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０３６０】
なお、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる場合はもちろん、必ずしも時系列的に処理されなくとも、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで実行されてもよい。
【０３６１】
なお、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０３６２】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０３６３】
１１  位置取得部，  １４  行動認識部，  １５  行動予測部，  １６  到達時間予測部，  １００  予測システム，  １１１  時刻取得部，  １１２  時系列データ記憶部，  １１３  マルチストリーム入力行動学習部，  １２１  曜日取得部，  １２２  交通状況取得部，  １２３  気象状況取得部，  １２４  時系列データ記憶部，  １２５  マルチストリーム入力行動学習部，  １４１  時系列データ記憶部，  １４２  状態系列生成部，  １４３  状態系列分類部，  １４４  パラメータ再計算部，  １４５  行動認識部，  １４６  行動予測部，  １６１  遷移頻度カウント部，  １６２  遷移パラメータ計算部，  １６３  状態頻度カウント部，  １６４  時系列データ分類部，  １６５  観測パラメータ計算部，  １８１  行動モード生成部，  ２０１  CPU，  ２０２  ROM，  ２０３  RAM，  ２０８  記憶部
【図１】
2011118777.tif 000017
【図２】
2011118777.tif 000018
【図３】
2011118777.tif 000019
【図４】
2011118777.tif 000020
【図５】
2011118777.tif 000021
【図６】
2011118777.tif 000022
【図７】
2011118777.tif 000023
【図８】
2011118777.tif 000024
【図９】
2011118777.tif 000025
【図１０】
2011118777.tif 000026
【図１１】
2011118777.tif 000027
【図１２】
2011118777.tif 000028
【図１３】
2011118777.tif 000029
【図１４】
2011118777.tif 000030
【図１５】
2011118777.tif 000031
【図１６】
2011118777.tif 000032
【図１７】
2011118777.tif 000033
【図１８】
2011118777.tif 000034
【図１９】
2011118777.tif 000035
【図２０】
2011118777.tif 000036
【図２１】
2011118777.tif 000037
【図２２】
2011118777.tif 000038
【図２３】
2011118777.tif 000039
【図２４】
2011118777.tif 000040
【図２５】
2011118777.tif 000041
【図２６】
2011118777.tif 000042
【図２７】
2011118777.tif 000043
【図２８】
2011118777.tif 000044
【図２９】
2011118777.tif 000045
【図３０】
2011118777.tif 000046
【図３１】
2011118777.tif 000047
【図３２】
2011118777.tif 000048
【図３３】
2011118777.tif 000049
【図３４】
2011118777.tif 000050