(57)【要約】【課題】欠落した時系列データから、より正確に隠れマルコフモデルを学習する。【解決手段】データ補間部３１は、時系列データにおいて欠落しているデータを補間する。状態尤度計算部３２乃至バックワード尤度計算部３５は、正常位置データに対する状態尤度と補間位置データに対する状態尤度とを異なる条件で計算して、データが補間された時系列データに対する隠れマルコフモデルの尤度を計算する。初期確率遷移確率推定部３６乃至観測確率推定部３８は、時系列データから隠れマルコフモデルを推定するとともに、状態尤度計算部３２乃至バックワード尤度計算部３５により計算される尤度が大きくなるように、隠れマルコフモデルを更新する。本発明は、例えば、ユーザの活動モデルを学習する学習装置に適用できる。【選択図】図４
2011118755.tif 000002
【特許請求の範囲】
【請求項１】
時系列データにおいて欠落しているデータを補間する補間手段と、
前記時系列データから隠れマルコフモデルを推定する推定手段と、
推定された前記隠れマルコフモデルの尤度を計算する尤度計算手段と
を備え、
前記尤度計算手段は、欠落していないデータである正常データに対する尤度と補間されたデータである補間データに対する尤度とを異なる条件で計算して、データが補間された前記時系列データに対する前記隠れマルコフモデルの尤度を計算し、
前記推定手段は、前記尤度計算手段により計算される尤度が大きくなるように、前記隠れマルコフモデルを更新する
学習装置。
【請求項２】
前記尤度計算手段は、前記補間データに対する尤度を前記正常データに対する尤度より低くする
請求項１に記載の学習装置。
【請求項３】
前記補間手段は、前記時系列データの欠落期間の直前の第１のデータと直後の第２のデータに基づいて、前記欠落期間におけるデータを補間するとともに、補間したデータに対する信頼度を、前記欠落期間の初めまたは終わりに近いデータほど高く設定し、前記欠落期間の初めおよび終わりから遠いデータほど低く設定し、
前記尤度計算手段は、前記補間データの前記信頼度が低いほど、前記補間データに対する尤度を低くする
請求項２に記載の学習装置。
【請求項４】
前記尤度計算手段は、前記補間データに対する前記隠れマルコフモデルの各状態の尤度を全て同じ値にする
請求項１に記載の学習装置。
【請求項５】
前記推定手段は、前記隠れマルコフモデルの観測確率への前記補間データの寄与度を前記正常データの寄与度より低くする
請求項１乃至４のいずれかに記載の学習装置。
【請求項６】
時系列データから隠れマルコフモデルを学習する学習装置が、
前記時系列データにおいて欠落しているデータを補間し、
前記時系列データから前記隠れマルコフモデルを推定し、
推定された前記隠れマルコフモデルの尤度を計算するとともに、
欠落していないデータである正常データに対する尤度と補間されたデータである補間データに対する尤度とを異なる条件で計算して、データが補間された前記時系列データに対する前記隠れマルコフモデルの尤度を計算し、
計算される尤度が大きくなるように、前記隠れマルコフモデルを更新する
ステップを含む学習方法。
【請求項７】
時系列データにおいて欠落しているデータを補間し、
前記時系列データから隠れマルコフモデルを推定し、
推定された前記隠れマルコフモデルの尤度を計算するとともに、
欠落していないデータである正常データに対する尤度と補間されたデータである補間データに対する尤度とを異なる条件で計算して、データが補間された前記時系列データに対する前記隠れマルコフモデルの尤度を計算し、
計算される尤度が大きくなるように、前記隠れマルコフモデルを更新する
ステップを含む処理をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、学習装置、学習方法、およびプログラムに関し、特に、時系列データからユーザの活動状態を隠れマルコフモデルとして学習する学習装置、学習方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、ユーザが身に着けられるセンサであるウェアラブルセンサから得られる時系列データを用いてユーザの状態をモデル化して学習し、学習により得られたモデルを用いてユーザの現在の状態を認識する研究が盛んである（例えば、特許文献１，２、非特許文献１）。
【０００３】
また、本出願人は、未来の所望の時刻におけるユーザの活動状態の複数の可能性を確率的に予測する方法を、特願２００９−１８０７８０（以下、先願１という）として先に提案している。先願１の方法では、時系列データからユーザの活動状態を確率的状態遷移モデルとして学習し、学習した確率的状態遷移モデルを用いて現在の活動状態を認識し、「所定時間後」のユーザの活動状態を確率的に予測することができる。そして、「所定時間後」のユーザの活動状態の予測の一例として、ユーザの現在の位置を認識し、所定時間後のユーザの行き先（場所）を予測する例が示されている。
【０００４】
さらに、本出願人は、複数の目的地への到達確率、経路、到達時間を予測する方法、および、目的地の候補を自動的に検出する方法を、特願２００９−２０８０６４（以下、先願２という）として先に提案している。また、先願２では、確率的状態遷移モデルを構成する状態ノードの中から、目的地に対応する状態ノードを見つける方法が提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−１３４０８０号公報
【特許文献２】特開２００８−２０４０４０号公報
【非特許文献】
【０００６】
【非特許文献１】‘‘Life Patterns: structure from wearable sensors’’,Brian Patrick Clarkson, Doctor Thesis, MIT, 2002
【発明の概要】
【発明が解決しようとする課題】
【０００７】
先願１および２では、GPSセンサにより測定された位置（緯度経度）の時系列データから、ユーザの活動状態を隠れマルコフモデルとして学習する例が示されている。
【０００８】
この場合の隠れマルコフモデルは、等間隔にセンシングされた時系列データから、その背後の「隠れた」変数のダイナミクスを状態の確率的遷移として表現する確率モデルである。このように、時系列データから隠れマルコフモデルを学習する場合、使用する時系列データは、等間隔でサンプリングされたデータであることが望ましい。
【０００９】
一方、GPSセンサは、人工衛星からの信号を捕捉して、現在地の緯度経度を測定するセンサである。従って、GPSセンサは、人工衛星からの信号の届かない地下や建物内などでは、現在地の緯度経度を測定することができない。そして、GPSセンサが緯度経度を測定できなくなってから測定を再開するまでの間、位置（緯度経度）の時系列データに欠落期間が生じる。
【００１０】
このような欠落期間が生じた時系列データを用いても、隠れマルコフモデルの学習は可能である。しかし、この場合に得られるモデルには、欠落期間の前に対応する状態ノードと欠落期間の後に対応する状態ノードとを短絡する状態遷移が現れる。
【００１１】
例えば、図１は、先願２に示される学習方法により、実験者が鉄道を利用して自宅から会社に出勤する際にGPSセンサにより位置を１０日間にわたって測定した時系列データを用いて、通勤経路を隠れマルコフモデルとして学習した結果を示している。なお、図中、小さい丸は、学習した隠れマルコフモデルの各状態ノードの位置を示している。また、各状態ノード間を結ぶ直線は、状態ノード間の状態遷移を示している。また、図１の横軸は経度を表し、縦軸は緯度を表している。
【００１２】
また、図２は、通勤に利用した路線の各駅の位置関係が分かるように、図１の上に各駅の位置と駅名を示した図である。
【００１３】
この路線は、長原駅付近から荏原中延駅付近まで地下を通るため、その付近で時系列データの欠落が生じる。そのため、例えば、洗足池駅付近と旗の台駅付近、旗の台駅付近と戸越銀座駅付近、洗足池駅付近と荏原中延駅付近、洗足池駅付近と大崎広小路駅付近をそれぞれ短絡したようなデータが時系列データに出現する。従って、この時系列データを用いて学習処理を行うと、洗足池駅付近と旗の台駅付近、旗の台駅付近と戸越銀座駅付近、洗足池駅付近と荏原中延駅付近、洗足池駅付近と大崎広小路駅付近の状態ノードをそれぞれ直接結ぶ状態遷移（すなわち経路）を含んだモデルが学習されてしまう。
【００１４】
例えば、このように学習されたモデルを用いて、目的地への到達時間を予測した場合、目的地までの経路にワープしたような区間が出現する。そのため、目的地に到達するまでに遷移する状態ノードの数（以下、ステップ数という）が、本来あるべき値より少なくなり、目的地への到達時間の予測精度が悪化する。
【００１５】
また、同じ経路に対して、正常な経路と短絡された経路が存在することになり、それぞれ別の分岐した経路として認識されてしまう。さらに、時系列データが欠落する場所が一定でない場合、欠落する場所に応じて異なる短絡経路が学習され、その結果、学習したモデルに、大量の分岐経路が現れる。その結果、目的地までの経路を探索する場合に、本来存在しない多数の分岐経路を探索する必要が生じ、処理にかかる負荷が増大し、処理時間が長くなったり、処理結果の信頼度が低下したりする。
【００１６】
本発明は、このような状況を鑑みてなされたものであり、欠落した時系列データから、より正確に隠れマルコフモデルを学習できるようにするものである。
【課題を解決するための手段】
【００１７】
本発明の一側面の学習装置は、
時系列データにおいて欠落しているデータを補間する補間手段と、
前記時系列データから隠れマルコフモデルを推定する推定手段と、
推定された前記隠れマルコフモデルの尤度を計算する尤度計算手段と
を備え、
前記尤度計算手段は、欠落していないデータである正常データに対する尤度と補間されたデータである補間データに対する尤度とを異なる条件で計算して、データが補間された前記時系列データに対する前記隠れマルコフモデルの尤度を計算し、
前記推定手段は、前記尤度計算手段により計算される尤度が大きくなるように、前記隠れマルコフモデルを更新する。
【００１８】
本発明の一側面の学習方法は、
時系列データから隠れマルコフモデルを学習する学習装置が、
前記時系列データにおいて欠落しているデータを補間し、
前記時系列データから前記隠れマルコフモデルを推定し、
推定された前記隠れマルコフモデルの尤度を計算するとともに、
欠落していないデータである正常データに対する尤度と補間されたデータである補間データに対する尤度とを異なる条件で計算して、データが補間された前記時系列データに対する前記隠れマルコフモデルの尤度を計算し、
計算される尤度が大きくなるように、前記隠れマルコフモデルを更新する
ステップを含む。
【００１９】
本発明の一側面のプログラムは、
時系列データにおいて欠落しているデータを補間し、
前記時系列データから隠れマルコフモデルを推定し、
推定された前記隠れマルコフモデルの尤度を計算するとともに、
欠落していないデータである正常データに対する尤度と補間されたデータである補間データに対する尤度とを異なる条件で計算して、データが補間された前記時系列データに対する前記隠れマルコフモデルの尤度を計算し、
計算される尤度が大きくなるように、前記隠れマルコフモデルを更新する
ステップを含む処理をコンピュータに実行させる。
【００２０】
本発明の一側面においては、時系列データにおいて欠落しているデータが補間され、前記時系列データから隠れマルコフモデルが推定され、推定された前記隠れマルコフモデルの尤度が計算されるとともに、欠落していないデータである正常データに対する尤度と補間されたデータである補間データに対する尤度とが異なる条件で計算され、データが補間された前記時系列データに対する前記隠れマルコフモデルの尤度が計算され、計算される尤度が大きくなるように、前記隠れマルコフモデルが更新される。
【発明の効果】
【００２１】
本発明の一側面によれば、欠落した時系列データから、より正確に隠れマルコフモデルを学習することができる。
【図面の簡単な説明】
【００２２】
【図１】従来技術による隠れマルコフモデルの学習結果を示す図である。
【図２】従来技術による隠れマルコフモデルの学習結果を示す図である。
【図３】本発明を適用した予測システムの一実施の形態の構成例を示すブロック図である。
【図４】行動学習部の機能の構成の例を示すブロック図である。
【図５】予測システムのハードウエア構成例を示すブロック図である。
【図６】予測システムに入力される時系列データの例を示す図である。
【図７】HMMの例を示す図である。
【図８】音声認識で利用されるHMMの例を示す図である。
【図９】スパース制約を与えたHMMの例を示す図である。
【図１０】行動予測部による経路の探索処理の簡単な例を示す図である。
【図１１】ユーザ活動モデル学習処理のフローチャートである。
【図１２】パラメータ更新処理のフローチャートである。
【図１３】データ補間処理のフローチャートである。
【図１４】到達時間予測処理のフローチャートである。
【図１５】本発明の効果の具体例を説明するための図である。
【図１６】本発明とは異なる第１の方法による隠れマルコフモデルの学習結果を示す図である。
【図１７】本発明とは異なる第２の方法による隠れマルコフモデルの学習結果を示す図である。
【図１８】本発明とは異なる第２の方法による隠れマルコフモデルの学習結果を示す図である。
【図１９】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための形態】
【００２３】
以下、本発明を実施するための形態（以下、実施の形態という）について説明する。なお、説明は以下の順序で行う。
１．実施の形態
２．変形例
【００２４】
＜１．実施の形態＞
［予測システムの実施の形態のブロック図］
図３は、本発明を適用した予測システムの一実施の形態の構成例を示すブロック図である。
【００２５】
予測システム１は、GPSセンサ１１、時系列データ記憶部１２、行動学習部１３、行動認識部１４、行動予測部１５、到達時間予測部１６、操作部１７、および表示部１８により構成される。
【００２６】
予測システム１は、GPSセンサ１１により取得される現在地および現在時刻を示す時系列データから、ユーザの活動状態（行動・活動パターンを表した状態）を確率的状態遷移モデルとして学習する学習処理を行う。また、予測システム１は、学習処理により得られたパラメータで表される確率的状態遷移モデル（ユーザ活動モデル）を用いて、ユーザが指定した目的地までの経路および時間を予測する予測処理も行う。
【００２７】
図３において、点線の矢印は、学習処理におけるデータの流れを示しており、実線の矢印は、予測処理におけるデータの流れを示している。
【００２８】
GPSセンサ１１は、一定時間間隔（たとえば、１５秒間隔）で人工衛星からの信号を受信し、自身の現在地の緯度経度を測定する。そして、GPSセンサ１１は、学習処理においては、測定した位置（緯度経度）と測定した時刻（以下、測定時刻ともいう）のデータ（以下、GPSデータという）を時系列データ記憶部１２に供給する。また、GPSセンサ１１は、予測処理においては、GPSデータを行動認識部１４に供給する。
【００２９】
時系列データ記憶部１２は、GPSセンサ１１により連続して取得されたGPSデータ、すなわち、位置と測定時刻の時系列データを記憶する。ユーザの行動・活動パターンを学習するので、例えば、数日分程度など、ある程度の期間について蓄積された時系列データが必要である。
【００３０】
行動学習部１３は、時系列データ記憶部１２に記憶されている時系列データに基づいて、GPSセンサ１１が組み込まれた機器を携行するユーザの活動状態を、確率的状態遷移モデルとして学習する。時系列データはユーザの位置と測定時刻を示すデータであるので、確率的状態遷移モデルとして学習されるユーザの活動状態は、ユーザの現在地の時系列変化、すなわちユーザの移動経路を表す状態となる。学習に使用される確率的状態遷移モデルとしては、例えば、エルゴディックHMM（Hidden Markov Model，隠れマルコフモデル）などの、隠れ状態を含む確率的状態遷移モデルを採用することができる。本実施の形態では、確率的状態遷移モデルとして、エルゴディックHMMにスパース制約を与えたものを採用する。なお、スパース制約を与えたエルゴディックHMM、エルゴディックHMMのパラメータの算出方法等については、図７乃至図９を参照して後述する。
【００３１】
また、上述したように、GPSセンサ１１が現在地を測定することができない場合、時系列データに欠落期間が生じる。このような場合、行動学習部１３は、図１３を参照して後述するように、時系列データにおいて欠落したデータを補間して、ユーザの活動状態を学習する。
【００３２】
行動学習部１３は、学習結果を示すデータを表示部１８に供給し、表示させる。また、行動学習部１３は、学習処理により得られた確率的状態遷移モデルのパラメータを行動認識部１４および行動予測部１５に供給する。
【００３３】
行動認識部１４は、学習により得られたパラメータの確率的状態遷移モデルを用いて、GPSセンサ１１からリアルタイムに供給される位置の時系列データから、ユーザの現在の活動状態、すなわち、ユーザの現在地を認識する。行動認識部１４は、ユーザの現在の状態ノードのノード番号を行動予測部１５に供給する。
【００３４】
行動予測部１５は、学習により得られたパラメータの確率的状態遷移モデルを用いて、行動認識部１４から供給される状態ノードのノード番号が示すユーザの現在地から、ユーザが取りうる経路を過不足なく探索（予測）する。また、行動予測部１５は、探索された経路ごとの生起確率を計算することにより、探索された経路が選択される確率である選択確率を予測する。
【００３５】
到達時間予測部１６には、行動予測部１５から、ユーザが取りうる経路と、その選択確率が供給される。また、到達時間予測部１６には、操作部１７から、ユーザが指定した目的地を示す情報が供給される。
【００３６】
到達時間予測部１６は、探索結果としてのユーザが取りうる経路から、ユーザが指定した目的地を含む経路を抽出し、抽出された各経路について目的地までの到達時間を予測する。また、到達時間予測部１６は、目的地へ到達する確率である到達確率を予測する。到達時間予測部１６は、目的地について複数の経路が存在する場合、その複数の経路の選択確率の和を、目的地の到達確率として算出する。目的地への経路が１つのみである場合には、その経路の選択確率が、そのまま目的地の到達確率となる。そして、到達時間予測部１６は、予測結果を示す情報を表示部１８に供給し、表示させる。
【００３７】
操作部１７は、ユーザが入力した目的地についての情報を受け付け、到達時間予測部１６に供給する。表示部１８は、行動学習部１３または到達時間予測部１６から供給される情報を表示する。
【００３８】
［行動学習部の機能の構成の例］
図４は、予測システム１の行動学習部１３の機能の構成の例を示すブロック図である。
【００３９】
行動学習部１３は、データ補間部３１、状態尤度計算部３２、状態尤度修正部３３、フォワード尤度計算部３４、バックワード尤度計算部３５、初期確率遷移確率推定部３６、観測確率推定前処理部３７、および、観測確率推定部３８により構成される。
【００４０】
データ補間部３１は、時系列データ記憶部１２に記憶されている時系列データを取得し、図１３を参照して後述するように、時系列データの欠落期間のデータを補間する。データ補間部３１は、補間した時系列データを状態尤度計算部３２に供給する。
【００４１】
状態尤度計算部３２は、図１２を参照して後述するように、ユーザの活動モデルを表すHMMの各状態の時系列データに対する尤度（以下、状態尤度ともいう）を計算する。状態尤度計算部３２は、計算した状態尤度を示すデータ、および、時系列データを状態尤度修正部３３に供給する。
【００４２】
状態尤度修正部３３は、図１２を参照して後述するように、時系列データの欠落期間に対する状態尤度を修正し、修正した状態尤度を示すデータ、および、時系列データをフォワード尤度計算部３４に供給する。
【００４３】
フォワード尤度計算部３４は、図１２を参照して後述するように、ユーザの活動モデルを表すHMMの時系列データに対するフォワード尤度を計算する。フォワード尤度計算部３４は、状態尤度修正部３３から取得したデータに、計算したフォワード尤度を示すデータを追加して、バックワード尤度計算部３５に供給する。
【００４４】
バックワード尤度計算部３５は、図１２を参照して後述するように、ユーザの活動モデルを表すHMMの時系列データに対するバックワード尤度を計算する。バックワード尤度計算部３５は、フォワード尤度計算部３４から取得したデータに、計算したバックワード尤度を示すデータを追加して、初期確率遷移確率推定部３６に供給する。
【００４５】
初期確率遷移確率推定部３６は、図１２を参照して後述するように、ユーザの活動モデルを表すHMMの初期確率および状態遷移確率を推定する。初期確率遷移確率推定部３６は、バックワード尤度計算部３５から取得したデータに、計算した初期確率および状態遷移確率を示すデータを追加して、観測確率推定前処理部３７に供給する。
【００４６】
観測確率推定前処理部３７は、図１２を参照して後述するように、ユーザの活動モデルを表すHMMの観測確率を推定する前に、時系列データの欠落期間に対するフォワード尤度およびバックワード尤度を変更する。観測確率推定前処理部３７は、初期確率遷移確率推定部３６から取得したデータに対して、フォワード尤度およびバックワード尤度を変更したデータを観測確率推定部３８に供給する。
【００４７】
観測確率推定部３８は、図１２を参照して後述するように、ユーザの活動モデルを表すHMMの初期確率を推定する。観測確率推定部３８は、HMMのパラメータ（初期確率、状態遷移確率、観測確率）を示すデータを、行動認識部１４および行動予測部１５、または、状態尤度計算部３２に供給する。
【００４８】
［予測システムのハードウエア構成例］
以上のように構成される予測システム１は、例えば、図５に示されるハードウエア構成を採用することができる。即ち、図５は、予測システム１のハードウエア構成例を示すブロック図である。
【００４９】
図５において、予測システム１は、３台のモバイル端末５１−１乃至５１−３とサーバ５２とにより構成されている。モバイル端末５１−１乃至５１−３は、同一機能を有する同型のモバイル端末５１であるが、モバイル端末５１−１乃至５１−３では、それを所有するユーザが異なる。従って、図５では、３台のモバイル端末５１−１乃至５１−３のみが示されているが、実際には、ユーザ数に応じた数のモバイル端末５１が存在する。
【００５０】
モバイル端末５１は、無線通信及びインターネット等のネットワークを介した通信により、サーバ５２とデータの授受を行うことができる。サーバ５２は、モバイル端末５１から送信されてくるデータを受信し、受信したデータに対し所定の処理を行う。そして、サーバ５２は、データ処理の処理結果を無線通信等によりモバイル端末５１に送信する。
【００５１】
従って、モバイル端末５１とサーバ５２は、無線または有線による通信を行う通信部を少なくとも有する。
【００５２】
さらに、モバイル端末５１が、図３のGPSセンサ１１、操作部１７、および表示部１８を備え、サーバ５２が、図３の時系列データ記憶部１２、行動学習部１３、行動認識部１４、行動予測部１５、および到達時間予測部１６を備える構成を採用することができる。
【００５３】
この構成が採用される場合、学習処理において、モバイル端末５１が、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の最尤推定法を用いたパラメータλの推定方法の詳細については、図１２を参照して後述する。
【００７３】
また、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センサ１１が取得したGPSデータが、時系列データとして、時系列データ記憶部１２に供給される。行動学習部１３は、時系列データ記憶部１２に記憶されているGPSデータの時系列データのうちの位置の時系列データx=x1,x2,・・・,xTを用い、ユーザ活動モデルを表すHMMのパラメータλを推定する。
【００９１】
即ち、ユーザの移動軌跡を表す各時刻の位置（緯度経度）のデータが、HMMの状態sjのいずれかに対応する地図上の一点から、所定の分散値の広がりを持って正規分布した確率変数の観測データであると考える。行動学習部１３は、各状態sjに対応する地図上の一点とその分散値、および状態遷移確率aijを最適化する。
【００９２】
行動認識部１４は、学習により得られたユーザ活動モデル（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に対応する各点は、端点、通過点、分岐点、ループのいずれかに分類することができる。端点とは、自己遷移以外の確率が極めて小さく（自己遷移以外の確率が所定の値以下であり）、次に移動可能な点がない点である。通過点とは、自己遷移以外に有意な遷移が一つある、換言すれば、次に移動可能な点が一つある点である。分岐点とは、自己遷移以外に有意な遷移が二つ以上ある、換言すれば、次に移動可能な点が二つ以上ある点である。ループとは、これまで通過した経路上のどれかと一致する点である。
【００９７】
目的地への経路を探索する場合、異なる経路がある場合には、それぞれの経路について必要時間等の情報を提示することが望まれる。そこで、可能な経路を過不足なく探索するために、次の条件を設定する。
（１）一度分岐した経路は再度合流した場合でも、別の経路とみなす。
（２）経路内に端点か、これまで通過した経路内に含まれる点が現れた場合、その経路の探索を終了する。
【００９８】
行動予測部１５は、行動認識部１４により認識されたユーザの現在の活動状態、即ち、ユーザの現在の点を出発点として、次の移動先としての状態遷移が可能な点を端点、通過点、分岐点、ループのいずれかに分類することを（２）の終了条件まで繰り返す。
【００９９】
行動予測部１５は、現在の点が端点であると分類された場合、現在の点をここまでの経路に接続してから、この経路の探索を終了する。
【０１００】
一方、現在の点が通過点であると分類された場合、行動予測部１５は、現在の点をここまでの経路に接続してから、次の点へ移動する。
【０１０１】
また、現在の点が分岐点であると分類された場合、行動予測部１５は、現在の点をこれまでの経路に接続して、さらに分岐の数だけ、これまでの経路を複製し、分岐点と接続する。そして、行動予測部１５は、分岐点の１つを次の点として移動する。
【０１０２】
現在の点がループであると分類された場合、行動予測部１５は、現在の点をこれまでの経路に接続せずに、この経路の探索を終了する。なお、現在の点から、１つ前の点に経路を逆戻りする場合はループに含まれるため考慮しない。
【０１０３】
［探索処理の例］
図１０は、行動予測部１５による経路の探索処理の簡単な例を示している。
【０１０４】
図１０の例において、状態s1が現在地である場合、最終的に３通りの経路が探索されることになる。１つめの経路は、状態s1から状態s5，状態s6等を経由して状態s10までの経路（以下、経路Ａともいう。）である。２つめの経路は、状態s1から状態s5，状態s11，状態s14，状態s23等を経由して状態s29までの経路（以下、経路Ｂともいう。）である。３つめの経路は、状態s1から状態s5，状態s11，状態s19，状態s23等を経由して状態s29までの経路（以下、経路Ｃともいう。）である。
【０１０５】
行動予測部１５は、探索された各経路が選択される確率（経路の選択確率）を計算する。経路の選択確率は、経路を構成する状態間の遷移確率を順次乗算することで求められる。ただし、次の状態に遷移する場合のみを考慮し、その場所に滞留する場合は考慮する必要がないので、学習により求められた各状態の状態遷移確率aijから、自己遷移確率を除いて規格化された遷移確率[aij]を用いて、経路の選択確率が求められる。
【０１０６】
自己遷移確率を除いて規格化された遷移確率[aij]は、次式（１）で表すことができる。
【数１】
2011118755.tif 000003
ここで、δは、クロネッカー関数を表し、添え字のｉとｊが一致するときのみ１となり、それ以外は０となる関数である。
【０１０７】
したがって、例えば、図１０の状態s5の状態遷移確率aijが、自己遷移確率a5,5＝０．５，遷移確率a5,6＝０．２，遷移確率a5,11＝０．３である場合、状態s5から状態s6または状態s11に分岐する場合の遷移確率[a5,6]および遷移確率[a5,11]は、それぞれ、０．４，０．６となる。
【０１０８】
探索された経路の状態siのノード番号ｉが、（ｙ1，ｙ2，・・・，ｙn）であるとき、この経路の選択確率は、規格化された遷移確率[aij]を用いて、次式（２）で表すことができる。
【０１０９】
【数２】
2011118755.tif 000004
実際には、通過点での規格化された遷移確率[aij]は１であるので、分岐する際の規格化された遷移確率[aij]を順次乗算すれば足りる。
【０１１０】
図１０の例では、経路Ａの選択確率は、０．４である。また、経路Ｂの選択確率は、０．２４＝０．６×０．４である。経路Ｃの選択確率は、０．３６＝０．６×０．６である。そして、計算された経路の選択確率の総和は１＝０．４＋０．２４＋０．３６であり、過不足ない探索を実現することができることがわかる。
【０１１１】
以上のように、現在地に基づいて探索された各経路とその選択確率が、行動予測部１５から到達時間予測部１６に供給される。
【０１１２】
到達時間予測部１６は、行動予測部１５によって探索された経路から、ユーザが指定した目的地を含む経路を抽出し、抽出された各経路について目的地までの時間を予測する。
【０１１３】
例えば、図１０の例では、探索された３つの経路Ａ乃至Ｃのうち、目的地である状態s28を含む経路は経路Ｂと経路Ｃである。到達時間予測部１６は、経路Ｂまたは経路Ｃを通って、目的地である状態s28に到達するまでの時間を予測する。
【０１１４】
なお、目的地を含む経路が多数あり、全ての経路を表示すると見づらくなる場合や経路の提示数が所定数に設定されている場合には、目的地を含む全ての経路のなかから、表示部１８に表示させる経路（以下、適宜、表示経路ともいう。）を決定する必要がある。そのような場合、行動予測部１５では、各経路について選択確率が算出されているので、到達時間予測部１６は、選択確率の高い順に、所定数の経路を表示経路として決定することができる。
【０１１５】
現在時刻ｔ１の現在地が状態ｓy1であり、時刻（ｔ1，ｔ2，・・・，ｔg）における決定された経路が（ｓy1，ｓy2，・・・，ｓyg）であるとする。換言すれば、決定された経路の状態siのノード番号ｉが（ｙ1，ｙ2，・・・，ｙg）であるとする。以下、簡単のため、位置に相当する状態siを、単に、そのノード番号ｉで表わす場合もある。
【０１１６】
現在時刻ｔ1での現在地ｙ1は、行動認識部１４の認識により確定しているので、現在時刻ｔ1の現在地がｙ1である確率Ｐy1（ｔ1）は、
Ｐy1（ｔ1）＝１
である。また、現在時刻ｔ1にｙ1以外の他の状態にいる確率は０である。
【０１１７】
一方、所定の時刻ｔnにノード番号ｙnにいる確率Ｐyn（ｔn）は、
【数３】
2011118755.tif 000005
で表すことができる。式（３）の右辺第一項は、もともとその位置ｙnにいて、自己遷移した場合の確率を表し、右辺第二項は、１つ前の位置ｙn-1から位置ｙnに遷移してきた場合の確率を表している。式（３）では、経路の選択確率の計算とは異なり、学習により得られた状態遷移確率aijがそのまま利用される。
【０１１８】
目的地ｙgへ到達するときの時刻ｔgの予測値<ｔg>は、「その直前の時刻ｔg-1に目的地ｙgの１つ前の位置ｙg-1にいて、時刻ｔgに目的地ｙgに移動する確率」を用いて、
【数４】
2011118755.tif 000006
と表すことができる。
【０１１９】
即ち、予測値<ｔg>は、現在時刻から、「その直前の時刻ｔg-1に状態ｓygの１つ前の状態ｓyg-1にいて、時刻ｔgに状態ｓygに移動するとき」までの時間の期待値で表される。
【０１２０】
［背景技術］の欄で提示した先願１の方法により、目的地への到達時間の予測値を求める場合、「所定時間後」の目的地に相当する状態の状態遷移確率aijを時間ｔに関して積分する必要があるが、この場合、積分区間をどれくらいに設定するのかが問題となる。先願１の方法では、ループする経路を通って目的地に到達する場合を区別できない。そのため、目的地までの途中の経路にループが存在している場合、積分区間を長めに設定すると、ループを介して二度目、三度目に目的地に到達する場合も含まれるため、目的地までの到達時間を正しく算出することができない。
【０１２１】
式（４）で表される、本発明による目的地への到達時間の予測値の演算では、同じく、時刻ｔについて積分（Σ）する必要はある。しかし、探索経路において、ループする経路を通って目的地に到達する場合が除外されているため、期待値の積分区間として十分長い区間を設定することが可能である。式（４）における積分区間は、例えば、学習した経路のなかで移動時間の最大の移動時間の１倍や２倍程度とすることができる。
【０１２２】
［ユーザ活動モデル学習処理］
次に、図１１のフローチャートを参照して、ユーザの移動経路を、ユーザの活動状態を表す確率的状態遷移モデルとして学習するユーザ活動モデル学習処理について説明する。
【０１２３】
初めに、ステップＳ１において、GPSセンサ１１は、GPSデータを取得する。即ち、GPSセンサ１１は、現在地の緯度経度を測定し、測定した位置（緯度経度）と測定時刻を示すGPSデータを時系列データ記憶部１２に供給する。
【０１２４】
ステップＳ２において、時系列データ記憶部１２は、GPSセンサ１１により連続して取得されたGPSデータ、すなわち、位置と測定時刻の時系列データを記憶する。
【０１２５】
ステップＳ３において、行動学習部１３は、パラメータ推定処理を行い、ユーザ活動モデル学習処理は終了する。
【０１２６】
［パラメータ推定処理］
ここで、図１２を参照して、図１１のステップＳ３のパラメータ推定処理の詳細について説明する。
【０１２７】
ステップＳ２１において、データ補間部３１は、時系列データ記憶部１２に記憶されているGPSデータの時系列データ、即ち、位置と測定時刻の時系列データを取得する。
【０１２８】
ステップＳ２２において、データ補間部３１は、データ補間処理を実行する。
【０１２９】
［データ補間処理］
ここで、図１３のフローチャートを参照して、図１２のステップＳ２２のデータ補間処理の詳細について説明する。
【０１３０】
ステップＳ５１において、データ補間部３１は、時系列データの欠落期間を探索する。上述したように、GPSセンサ１１が人工衛星からの信号を捕捉できている間は、GPSデータは一定の時間間隔（以下、サンプリング周期ともいう）で取得されている。従って、データ補間部３１は、時系列データの各データの測定時刻に基づいて、GPSデータが取得された間隔がサンプリング周期より長い期間を探索し、検出した期間を欠落期間とする。
【０１３１】
ステップＳ５２において、データ補間部３１は、時刻データを補間する。即ち、データ補間部３１は、GPSデータのサンプリング周期に基づいて、時系列データの欠落期間における測定時刻を補間する。
【０１３２】
ステップＳ５３において、データ補間部３１は、補間した測定時刻に対応する位置データを補間する。
【０１３３】
例えば、位置データを補間する方法として、GPSデータの欠落期間における位置を、欠落期間の直前に測定された位置（以下、消失点という）に固定する方法が考えられる。この方法は容易ではあるが、欠落期間の直後に測定された位置（以下、復活点という）に関係なく、欠落期間における位置が固定されてしまうため、補間した位置データの信頼度は低くなる。
【０１３４】
そこで、データ補間部３１は、消失点と復活点の間を線形補間することにより位置データを補間する。即ち、データ補間部３１は、消失点と復活点を結ぶ直線上に、欠落期間のサンプル数と同じ数の点を等間隔に配置し、配置した点の位置を示すデータを、補間した各測定時刻に対応する位置データとして補間する。
【０１３５】
なお、直線補間以外の方法、例えば、一次以上の多項式補間、対数補間、シンク関数を用いた補間などを用いて、位置データを補間するようにしてもよい。
【０１３６】
ステップＳ５４において、データ補間部３１は、位置データの信頼度を設定する。具体的には、補間した位置データ（以下、補間位置データという）は、欠落期間以外の期間（以下、正常期間という）の元々存在する位置データ（以下、正常位置データともいう）と比較して、データの信頼度が低い。そこで、例えば、データ補間部３１は、正常位置データと補間位置データとを後で区別できるように、２つのデータを区別するパラメータを時系列データに追加する。これにより、後の処理で正常位置データと補間位置データとを区別し、補間位置データを信頼度が低いデータとして扱うことが可能になる。
【０１３７】
また、例えば、データ補間部３１は、各位置データの値が、実際にその時刻に存在していた位置（以下、単に実際の位置ともいう）にどの程度近いかを表す信頼度として、各位置データの値を中心とする分散（あるいは標準偏差）を設定する。例えば、データ補間部３１は、正常位置データの分散を０または所定の定数に設定し、補間位置データの分散を正常位置データの分散より大きい値の定数に設定する。
【０１３８】
あるいは、補間位置データの分散を定数ではなく、その位置に応じた値に設定するようにしてもよい。具体的には、補間位置データに示される位置は、欠落期間の初めまたは終わりに近いデータほど、実際の位置との差が小さくなり、欠落期間の初めおよび終わりから遠いデータほど、実際の位置との差が大きくなると考えられる。そこで、例えば、データ補間部３１は、欠落期間の初めまたは終わりに時間的に近い補間位置データほど分散を小さい値に設定し（即ち、信頼度を高く設定し）、欠落期間の初めおよび終わりから時間的に遠い補間位置データほど分散を大きい値に設定する（即ち、信頼度を低く設定する）。
【０１３９】
なお、この信頼度として設定された分散（あるいは標準偏差）は、補間位置データに示される位置は必ずしも正しい値ではないが、その位置の周辺に、設定された分散（あるいは標準偏差）で、正しい位置が確率的に見つかることを表す。
【０１４０】
ステップＳ５５において、データ補間部３１は、補間した時系列データを状態尤度計算部３２に供給する。即ち、データ補間部３１は、欠落期間の測定時刻と位置データを補間し、各位置データの信頼度を設定した時系列データを状態尤度計算部３２に供給する。その後、データ補間処理は終了する。
【０１４１】
［パラメータ推定処理の続き］
図１２に戻り、ステップＳ２３において、状態尤度計算部３２は、位置データに対する各状態の尤度を計算する。具体的には、状態尤度計算部３２は、ユーザ活動モデルを表すHMMの状態ｓiへの遷移時に、時系列データの時刻tの位置データｘtが出力されると仮定した場合の状態尤度Ｐ（ｓi｜ｘt）を、次式（５）により計算する。
【０１４２】
【数５】
2011118755.tif 000007
なお、時刻ｔは、時系列データの測定時刻ではなく、時系列データの順番を表し、１からＴ（時系列データのサンプル数）までの値をとる。
【０１４３】
また、式（５）のＤは、位置データの次元数を示している。いまの場合、位置データは緯度と経度の２次元なので、Ｄ＝２となる。そして、ｘt（１）、ｘt（２）が、それぞれ位置データｘtの緯度、経度を表すものとする。また、状態ｓiへの遷移時に出力される位置データの緯度および経度の出力確率密度関数がそれぞれ単一正規分布に従い、μsi（１）、σsi（１）は、緯度の出力確率密度関数の中心値および標準偏差を表し、μsi（２）、σsi（２）は、経度の出力確率密度関数の中心値および標準偏差を表すものとする。
【０１４４】
なお、式（５）は、Baum-Welchの最尤推定法で一般的に用いられる式である。
【０１４５】
状態尤度計算部３２は、全ての状態ｓiと位置データｘtの組み合わせについて、式（５）により状態尤度Ｐ（ｓi｜ｘt）を計算し、計算した状態尤度Ｐ（ｓi｜ｘt）を示すデータおよび時系列データを状態尤度修正部３３に供給する。
【０１４６】
ステップＳ２４において、状態尤度修正部３３は、補間した位置データに対する各状態の尤度を修正する。例えば、状態尤度修正部３３は、補間した位置データｘtに対する状態尤度Ｐ（ｓi｜ｘt）を、次式（６）により修正する。
【０１４７】
【数６】
2011118755.tif 000008
なお、式（６）のＭはHMMの状態ノード数を表す。
【０１４８】
式（６）は、欠落期間内の時刻ｔの位置データｘtが出力された際に各状態ｓiに遷移する確率が全て等しいと仮定した場合の状態尤度Ｐ（ｓi｜ｘt）を示しており、補間位置データに対する状態尤度Ｐ（ｓi｜ｘt）が全て同じ値となる。
【０１４９】
あるいは、例えば、状態尤度修正部３３は、補間した位置データｘtに対する状態尤度Ｐ（ｓi｜ｘt）を、次式（７）により修正する。
【０１５０】
【数７】
2011118755.tif 000009
なお、式（７）のσt（ｄ）2には、上述した図１３のステップＳ５４の処理で、各位置データの信頼度として設定された分散が用いられる。
【０１５１】
これにより、状態尤度Ｐ（ｓi｜ｘt）に補間位置データの信頼度が反映され、補間位置データに対する状態尤度Ｐ（ｓi｜ｘt）が、正常位置データに対する状態尤度Ｐ（ｓi｜ｘt）より相対的に低い値に設定される。即ち、同じ値の補間位置データと正常位置データに対して、補間位置データに対する状態尤度Ｐ（ｓi｜ｘt）が、正常位置データに対する状態尤度Ｐ（ｓi｜ｘt）より低い値に設定される。また、補間位置データに対する状態尤度Ｐ（ｓi｜ｘt）は、補間位置データの信頼度が高いほど（分散σt（ｄ）2が小さいほど）高くなり、補間位置データの信頼度が低いほど（分散σt（ｄ）2が大きいほど）低くなる。
【０１５２】
状態尤度修正部３３は、全ての状態ｓiと全ての補間した位置データｘtの組み合わせについて、式（６）または式（７）により状態尤度Ｐ（ｓi｜ｘt）を修正する。状態尤度修正部３３は、修正した状態尤度Ｐ（ｓi｜ｘt）を含む全ての状態尤度Ｐ（ｓi｜ｘt）のデータおよび時系列データをフォワード尤度計算部３４に供給する。
【０１５３】
このステップＳ２４の処理により、結果的に、補間位置データに対する状態尤度Ｐ（ｓi｜ｘt）と正常位置データに対する状態尤度Ｐ（ｓi｜ｘt）が異なる条件で計算されることになる。なお、ステップＳ２３において、補間位置データに対する状態尤度Ｐ（ｓi｜ｘt）を計算しないようにしてもよい。
【０１５４】
ステップＳ２５において、フォワード尤度計算部３４は、フォワード尤度を計算する。即ち、フォワード尤度計算部３４は、次式（８）および（９）を用いて、時刻ｔにおける状態ｓiのフォワード尤度αt（ｓi）を時刻１から最終の時刻Ｔまで順番に計算する。
【０１５５】
【数８】
2011118755.tif 000010
なお、式（８）のπsiは、状態ｓiの初期確率を表す。また、式（９）のａjiは、状態ｓjから状態ｓiへの状態遷移確率を表す。なお、初期確率πsiおよび状態遷移確率ａjiの初期値は、例えば、外部から与えられる。
【０１５６】
なお、式（８）および（９）は、Baum-Welchの最尤推定法のフォワードアルゴリズムにおいて一般的に用いられる式である。
【０１５７】
フォワード尤度計算部３４は、各時刻ｔにおける全ての状態ｓiのフォワード尤度αt（ｓi）を計算する。そして、フォワード尤度計算部３４は、状態尤度修正部３３から取得したデータに、計算したフォワード尤度αt（ｓi）を示すデータを追加して、バックワード尤度計算部３５に供給する。
【０１５８】
ステップＳ２６において、バックワード尤度計算部３５は、バックワード尤度を計算する。即ち、バックワード尤度計算部３５は、次式（１０）および（１１）を用いて、時刻ｔにおける状態ｓiのバックワード尤度βt（ｓi）を、最終の時刻Ｔから時刻１まで逆順に計算する。
【０１５９】
【数９】
2011118755.tif 000011
なお、式（１０）では、時刻Ｔに各状態ｓiである確率が全て等しいものとしている。
【０１６０】
なお、式（１０）および（１１）は、Baum-Welchの最尤推定法のバックワードアルゴリズムにおいて一般的に用いられる式である。
【０１６１】
バックワード尤度計算部３５は、各時刻ｔにおける全ての状態ｓiのバックワード尤度βt（ｓi）を計算する。そして、バックワード尤度計算部３５は、フォワード尤度計算部３４から取得したデータに、計算したバックワード尤度βt（ｓi）を示すデータを追加して、初期確率遷移確率推定部３６に供給する。
【０１６２】
このように、ステップＳ２３乃至Ｓ２６の処理により、データを補間した時系列データに対する隠れマルコフモデルの各種の尤度が計算される。
【０１６３】
ステップＳ２７において、初期確率遷移確率推定部３６は、初期確率、状態遷移確率を更新する。即ち、初期確率遷移確率推定部３６は、各状態ｓiの初期確率πsi、各状態間の状態遷移確率ａijを、次の式（１２）および式（１３）で求まる初期確率πsi’、状態遷移確率ａij’にそれぞれ更新する。
【０１６４】
【数１０】
2011118755.tif 000012
なお、式（１２）および式（１３）は、Baum-Welchの最尤推定法で一般的に用いられる式である。
【０１６５】
初期確率遷移確率推定部３６は、バックワード尤度計算部３５から取得したデータに、更新した初期確率πsiおよび状態遷移確率ａijを示すデータを追加して、観測確率推定前処理部３７に供給する。
【０１６６】
ステップＳ２８において、観測確率推定前処理部３７は、補間した位置データの観測確率への寄与度を低減する。具体的には、観測確率推定前処理部３７は、欠落期間内の時刻ｔにおけるフォワード尤度αt（ｓi）およびバックワード尤度βt（ｓi）を全て０に設定する。観測確率推定前処理部３７は、初期確率遷移確率推定部３６から取得したデータに対して、このようにフォワード尤度αt（ｓi）およびバックワード尤度βt（ｓi）を変更したデータを観測確率推定部３８に供給する。
【０１６７】
ステップＳ２９において、観測確率推定部３８は、観測確率を更新する。即ち、観測確率推定部３８は、各状態ｓiの出力確率密度関数の中心値μsi（ｄ）、分散σsi（ｄ）2を、次の式（１４）および式（１５）で求まる中心値μsi（ｄ）’、分散σsi（ｄ）’2にそれぞれ更新する。
【０１６８】
【数１１】
2011118755.tif 000013
なお、式（１４）および式（１５）のｄは、データの次元を表し、いまの場合、１または２となる。
【０１６９】
なお、式（１４）および式（１５）は、Baum-Welchの最尤推定法で一般的に用いられる式である。
【０１７０】
ここで、ステップＳ２８において、欠落期間内の時刻ｔにおけるフォワード尤度αt（ｓi）およびバックワード尤度βt（ｓi）が全て０に設定されている。従って、特別な計算式を用いることなく、各状態ｓiの観測確率（中心値μsi（ｄ）、分散σsi（ｄ）2）への補間位置データの寄与度が、正常位置データの寄与度より低くなり、ほぼ０になる。これにより、観測確率の推定に、信頼度が低い補間位置データがほとんど反映されなくなり、観測確率の推定精度が向上する。
【０１７１】
ステップＳ３０において、観測確率推定部３８は、パラメータの更新を終了するか否かを判定する。観測確率推定部３８は、後述する所定の更新終了条件がまだ成立していない場合、パラメータの更新を終了しないと判定し、処理はステップＳ３１に進む。
【０１７２】
ステップＳ３１において、観測確率推定部３８は、更新されたパラメータを状態尤度計算部３２に供給する。即ち、観測確率推定部３８は、ステップＳ２７乃至Ｓ２９の処理で更新された、各状態ｓiの初期確率πsi、中心値μsi（ｄ）および分散σsi（ｄ）2、並びに、各状態間の状態遷移確率ａijを示すデータを状態尤度計算部３２に供給する。
【０１７３】
その後、ステップＳ３０において、パラメータの更新を終了すると判定されるまで、ステップＳ２３乃至Ｓ３１の処理が繰り返し実行される。これにより、状態ｓiの系列の各種の尤度、すなわち、状態尤度Ｐ（ｓi｜ｘt）、フォワード尤度αt（ｓi）、バックワード尤度βt（ｓi））が次第に増加し、最終的に最大になるように、HMMのパラメータの更新が行われる。
【０１７４】
一方、ステップＳ３０において、観測確率推定部３８は、例えば、各尤度の増分が所定の値以下となり、パラメータの更新の収束条件を満たした場合、パラメータの更新を終了すると判定し、処理はステップＳ３２に進む。あるいは、観測確率推定部３８は、例えば、ステップＳ２３乃至Ｓ３１の更新処理が所定の回数実行された場合、パラメータの更新を終了すると判定し、処理はステップＳ３２に進む。
【０１７５】
ステップＳ３２において、観測確率推定部３８は、最終的なパラメータを状態尤度計算部３２に供給する。即ち、観測確率推定部３８は、ステップＳ２３乃至Ｓ３１の更新処理で最終的に求められた、各状態ｓiの初期確率πsi、中心値μsi（ｄ）および分散σsi（ｄ）2、並びに、各状態間の状態遷移確率ａijを示すデータを、行動認識部１４および行動予測部１５に供給する。
【０１７６】
その後、パラメータ推定処理は終了する。
【０１７７】
［到達時間予測処理］
次に、図１１のユーザ活動モデル学習処理により得られたユーザ活動モデルを表す確率的状態遷移モデルのパラメータを用いて、目的地までの経路を探索し、到達時間を算出してユーザに提示する到達時間予測処理について説明する。
【０１７８】
図１４は、到達時間予測処理のフローチャートを示している。なお、この例では、図１４の処理の前に、目的地が予め決められているものとするが、図１４の処理の途中で目的地を入力するようにしてもよい。
【０１７９】
初めに、ステップＳ１０１において、GPSセンサ１１は、位置の時系列データを取得し、行動認識部１４に供給する。行動認識部１４には、所定のサンプル数の位置の時系列データが一時的に記憶される。
【０１８０】
ステップＳ１０２において、行動認識部１４は、学習により得られたパラメータに基づくユーザ活動モデルから、ユーザの現在の活動状態を認識する。即ち、行動認識部１４は、ユーザの現在地を認識する。そして、行動認識部１４は、ユーザの現在の状態ノードのノード番号を行動予測部１５に供給する。
【０１８１】
ステップＳ１０３において、行動予測部１５は、現在探索している状態ノード（以下、適宜、現在の状態ノードともいう。）に対応する点が、端点、通過点、分岐点、またはループのいずれであるかを判定する。ステップＳ１０２の処理直後は、ユーザの現在地に対応する状態ノードが現在の状態ノードとなる。
【０１８２】
ステップＳ１０３で、現在の状態ノードに対応する点が端点であると判定された場合、処理はステップＳ１０４に進み、行動予測部１５は、現在の状態ノードをここまでの経路に接続し、この経路の探索を終了し、ステップＳ１１１に進む。なお、現在の状態ノードが現在地に対応する状態ノードである場合、ここまでの経路は存在しないため、接続する処理は行われない。ステップＳ１０５，Ｓ１０７、Ｓ１１０でも同様である。
【０１８３】
ステップＳ１０３で、現在の状態ノードに対応する点が通過点であると判定された場合、処理はステップＳ１０５に進み、行動予測部１５は、現在の状態ノードをここまでの経路に接続する。そして、ステップＳ１０６において、行動予測部１５は、次の状態ノードを現在の状態ノードとし、移動する。ステップＳ１０６の処理後、処理はステップＳ１０３に戻る。
【０１８４】
ステップＳ１０３で、現在の状態ノードに対応する点が分岐点であると判定された場合、処理はステップＳ１０７に進み、行動予測部１５は、現在の状態ノードをここまでの経路と接続する。そして、ステップＳ１０８において、行動予測部１５は、ここまでの経路を分岐の数だけ複製し、分岐先の状態ノードと接続する。さらにステップＳ１０９において、行動予測部１５は、複製した経路の１つを選択し、その選択した経路の先の状態ノードを現在の状態ノードとし移動する。ステップＳ１０９の処理後、処理はステップＳ１０３に戻る。
【０１８５】
一方、ステップＳ１０３で、現在の状態ノードに対応する点がループであると判定された場合、処理はステップＳ１１０に進み、行動予測部１５は、現在の状態ノードをここまでの経路と接続せずに、この経路の探索を終了し、ステップＳ１１１に進む。
【０１８６】
ステップＳ１１１において、行動予測部１５は、未探索の経路があるかを判定する。ステップＳ１１１で、未探索の経路があると判定された場合、処理はステップＳ１１２に進み、行動予測部１５は、現在地の状態ノードに戻り、未探索の経路の次の状態ノードを現在の状態ノードとし移動する。ステップＳ１１２の処理後、処理はステップＳ１０３に戻る。これにより、未探索の経路について、端点またはループにより探索が終了するまで経路の探索が実行される。
【０１８７】
ステップＳ１１１で、未探索の経路がないと判定された場合、処理はステップＳ１１３に進み、行動予測部１５は、探索された各経路の選択確率（生起確率）を計算する。行動予測部１５は、各経路と、その選択確率を到達時間予測部１６に供給する。
【０１８８】
ステップＳ１１４において、到達時間予測部１６は、行動予測部１５によって探索された経路から、入力された目的地を含む経路を抽出し、目的地の到達確率を算出する。具体的には、到達時間予測部１６は、目的地に複数の経路が存在する場合、その複数の経路の選択確率の和を、目的地の到達確率として計算する。目的地への経路が１つしかない場合、経路の選択確率が、そのまま、目的地の到達確率とされる。
【０１８９】
ステップＳ１１５において、到達時間予測部１６は、抽出された経路の数が提示数として予め設定された所定個数より多いかを判定する。
【０１９０】
ステップＳ１１５で、抽出された経路の数が所定個数より多いと判定された場合、処理はステップＳ１１６に進み、到達時間予測部１６は、表示部１８に表示する所定個数の経路を決定する。例えば、到達時間予測部１６は、選択される可能性の高い順に、所定個数の経路を決定することができる。
【０１９１】
一方、ステップＳ１１５で、抽出された経路の数が所定個数以下であると判定された場合、ステップＳ１１６の処理がスキップされる。即ち、この場合、目的地に到達するための全ての経路が表示部１８に表示される。
【０１９２】
ステップＳ１１７において、到達時間予測部１６は、表示部１８に表示すると決定された各経路の到達時間を計算する。そして、到達時間予測部１６は、目的地の到達確率および目的地までの経路と到達時間を表示する画像の信号を表示部１８に供給する。
【０１９３】
ステップＳ１１８において、表示部１８は、到達時間予測部１６から供給される画像の信号に基づいて、目的地の到達確率および目的地までの経路と到達時間を表示して、処理を終了する。
【０１９４】
［本発明の効果の説明］
以上のように、予測システム１では、GPSセンサ１１により取得される位置と測定時刻の時系列データの欠落期間のデータを補間して、補間した時系列データを用いて、ユーザの活動状態を隠れマルコフモデルとして学習する学習処理を行う。従って、時系列データに欠落期間が存在していても、正確にユーザの活動状態を学習することができる。
【０１９５】
ここで、図１５を参照して、予測システム１の学習処理の効果の具体例を説明する。
【０１９６】
図１５は、図１および図２を参照して上述した実験と同じ時系列データを用いて、予測システム１により学習処理を行った結果を示す図である。なお、このときの学習処理では、図１２のステップＳ２４における状態尤度Ｐ（ｓi｜ｘt）の修正に、式（６）を用いている。
【０１９７】
図１５と図１を比較すると、図１５では、距離が離れた状態ノードを短絡する状態遷移の数が減っていることが分かる。
【０１９８】
なお、式（６）により、欠落期間の補間位置データに対する状態尤度Ｐ（ｓi｜ｘt）を全て同じ値にしても、フォワード尤度αt（ｓi）およびバックワード尤度βt（ｓi）を計算する際に、補間した位置データに対して、その近くにある状態ノードが自動的に割り当てられるため、状態ノードを短絡する状態遷移が学習されることが防止される。
【０１９９】
また、状態尤度Ｐ（ｓi｜ｘt）の修正に上述した式（７）を用いても、ほぼ同じ学習結果を得ることができる。ただし、式（７）を用いた方が、より状態尤度Ｐ（ｓi｜ｘt）の信頼度が向上するため、より正確にユーザ活動モデルを学習することができる。
【０２００】
なお、参考までに、図１６乃至図１８を参照して、同じ時系列データを用いて、予測システム１とは異なる対策を行った場合の学習結果の例について説明する。
【０２０１】
図１６は、時系列データの欠落期間において、消失点と同じ位置のデータを補間した時系列データを用いて学習処理を行った結果を示している。即ち、欠落期間中、消失点と同じ位置でホールドされた時系列データを用いて学習処理を行った結果を示している。この方法を用いれば、ホールドされた位置付近に複数の状態ノードが割り当てられたり、ホールドされた位置付近の状態ノードの自己遷移確率が高くなったりする。従って、目的地までのステップ数の不足の問題は解消され、目的地への到達時間の予測精度は向上する。しかし、図１と比較して、短絡経路の数を削減することはできず、処理負荷が増大する問題は解消されない。
【０２０２】
図１７は、欠落期間が所定の時間以上になったら、時系列データを分割し、別の系統の時系列データとするようにした場合の学習結果を示している。ちなみに、図１７は、欠落期間が２分以上になったら時系列データを分割するようにした場合の例を示している。この場合、学習に用いる時系列データに欠落期間がなくなるため、図１７に示されるように、通勤経路が一本の経路として学習されることが分かる。ただし、この場合、時系列データを分割する条件となる時間を適正に設定する必要がある。
【０２０３】
例えば、図１８は、欠落期間が１分以上になったら、時系列データを分割するようにした場合の学習結果を示している。この場合、時系列データを分割するタイミングが多くなりすぎて、その結果、通勤経路が分断され、１本につながっていない。このように経路が分断されてしまうと、例えば、目的地への到達時間を予測する場合に、目的地に到達する経路を１つも見つけられずに処理が終わってしまう可能性がある。
【０２０４】
これに対して、予測システム１では、各種のパラメータの調整を行う必要がなく、同じ時系列データに対して、常に同じ学習結果を得ることができる。
【０２０５】
また、予測システム１は、学習処理により得られたパラメータで表される確率的状態遷移モデルを用いて、入力された目的地の到達確率および目的地までの経路と到達時間を予測して、ユーザに提示する。
【０２０６】
したがって、予測システム１によれば、ユーザが指定した目的地の到達確率および目的地までの経路とその到達時間を予測して、ユーザに提示することができる。また、上述したように、予測システム１では、時系列データが欠落していても、正確にユーザの活動モデルが学習されるため、それらの予測精度が向上する。
【０２０７】
＜２.変形例＞
以上の説明では、１系統の時系列データに対する学習処理を中心に説明したが、本発明は、複数系統の時系列データに対する学習処理にも適用することができる。
【０２０８】
また、以上の説明では、ユーザの活動モデルの学習に、位置の時系列データのみを用いる例を示したが、測定時刻の時系列データも用いるようにしてもよい。ただし、測定時刻は、位置データと異なり、補間した値に誤差が生じない。従って、例えば、補間位置データに対する状態尤度Ｐ（ｓi｜ｘt）の計算式（７）を、次式（１６）に変更するようにすればよい。
【０２０９】
【数１２】
2011118755.tif 000014
なお、ｘt（１）、ｘt（２）、ｘt（３）は、それぞれ時系列データの時刻ｔのデータｘtの緯度、経度、測定時刻を表す。また、μsi（１）、σsi（１）は、状態ｓiの緯度の出力確率密度関数の中心値および標準偏差を表す。さらに、μsi（２）、σsi（２）は、状態ｓiの経度の出力確率密度関数の中心値および標準偏差を表す。また、μsi（３）、σsi（３）は、状態ｓiの測定時刻の出力確率密度関数の中心値および標準偏差を表す。さらに、σt（１）2、σt（２）2は、それぞれ時系列データの時刻ｔのデータｘtの緯度の分散（信頼度）、経度の分散（信頼度）を表す。また、ｗ１およびｗ２は重みを示し、各データの時系列データの構造に寄与する度合いに応じて設定される。
【０２１０】
式（１６）を用いることにより、補間した緯度および経度の信頼度のみが状態尤度Ｐ（ｓi｜ｘt）に反映されるようになる。
【０２１１】
なお、式（１６）の代わりに、式（６）を用いることも可能である。
【０２１２】
さらに、以上の説明では、位置の時系列データを用いて、ユーザの活動モデルを表すHMMを学習する例を示したが、本発明は、データの種類を問わず、時系列データからHMMを学習する場合に適用できる。
【０２１３】
また、学習に用いる時系列データの欠落期間以外の期間（正常期間）において、データのサンプリング間隔が一定でない場合、サンプリング間隔が一定になるように、再サンプリング処理等を行うようにしてもよい。
【０２１４】
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【０２１５】
図１９は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【０２１６】
コンピュータにおいて、CPU（Central Processing Unit）２０１，ROM（Read Only Memory）２０２，RAM（Random Access Memory）２０３は、バス２０４により相互に接続されている。
【０２１７】
バス２０４には、さらに、入出力インタフェース２０５が接続されている。入出力インタフェース２０５には、入力部２０６、出力部２０７、記憶部２０８、通信部２０９、ドライブ２１０、およびGPSセンサ２１１が接続されている。
【０２１８】
入力部２０６は、キーボード、マウス、マイクロホンなどよりなる。出力部２０７は、ディスプレイ、スピーカなどよりなる。記憶部２０８は、ハードディスクや不揮発性のメモリなどよりなる。通信部２０９は、ネットワークインタフェースなどよりなる。ドライブ２１０は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブル記録媒体２１２を駆動する。GPSセンサ２１１は、図１のGPSセンサ１１に対応する。
【０２１９】
以上のように構成されるコンピュータでは、CPU２０１が、例えば、記憶部２０８に記憶されているプログラムを、入出力インタフェース２０５及びバス２０４を介して、RAM２０３にロードして実行することにより、上述した一連の処理が行われる。
【０２２０】
コンピュータ（CPU２０１）が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブル記録媒体２１２に記録して提供することができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することができる。
【０２２１】
コンピュータでは、プログラムは、リムーバブル記録媒体２１２をドライブ２１０に装着することにより、入出力インタフェース２０５を介して、記憶部２０８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部２０９で受信し、記憶部２０８にインストールすることができる。その他、プログラムは、ROM２０２や記憶部２０８に、あらかじめインストールしておくことができる。
【０２２２】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０２２３】
なお、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる場合はもちろん、必ずしも時系列的に処理されなくとも、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで実行されてもよい。
【０２２４】
なお、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０２２５】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０２２６】
１  予測システム，  １３  行動学習部，  １４  行動認識部，  １５  行動予測部，  １６  到達時間予測部，  ３１  データ補間部，  ３２  状態尤度計算部，  ３３  状態尤度修正部，  ３４  フォワード尤度計算部，  ３５  バックワード尤度計算部，  ３６  初期確率遷移確率推定部，  ３７  観測確率推定前処理部，  ３８  観測確率推定部
【図１】
2011118755.tif 000015
【図２】
2011118755.tif 000016
【図３】
2011118755.tif 000017
【図４】
2011118755.tif 000018
【図５】
2011118755.tif 000019
【図６】
2011118755.tif 000020
【図７】
2011118755.tif 000021
【図８】
2011118755.tif 000022
【図９】
2011118755.tif 000023
【図１０】
2011118755.tif 000024
【図１１】
2011118755.tif 000025
【図１２】
2011118755.tif 000026
【図１３】
2011118755.tif 000027
【図１４】
2011118755.tif 000028
【図１５】
2011118755.tif 000029
【図１６】
2011118755.tif 000030
【図１７】
2011118755.tif 000031
【図１８】
2011118755.tif 000032
【図１９】
2011118755.tif 000033