(57)【要約】【課題】グラフ構造の一部のエッジのトラフィック量に基づき、グラフ構造全体のトラフィック量を推定する。【解決手段】複数のエッジが接続されたグラフ構造を取得するグラフ構造取得部と、グラフ構造内の一部のエッジである特定エッジを流れるトラフィック量を取得するトラフィック量取得部と、各エッジを通過したトラフィックが当該エッジに接続されたそれぞれのエッジに遷移する状態遷移確率の学習パラメータを含む状態遷移モデルの定常分布における、特定エッジのトラフィックの存在確率に応じたトラフィック量を、特定エッジを流れるトラフィック量に近付けるように学習して、グラフ構造内のトラフィックの流れを推定する推定部と、を備える推定装置、推定方法、およびプログラムを提供する。【選択図】図２
2015018377.tif 000002
【特許請求の範囲】
【請求項１】
複数のエッジが接続されたグラフ構造を取得するグラフ構造取得部と、
前記グラフ構造内の一部のエッジである特定エッジを流れるトラフィック量を取得するトラフィック量取得部と、
各エッジを通過したトラフィックが当該エッジに接続されたそれぞれのエッジに遷移する状態遷移確率の学習パラメータを含む状態遷移モデルの定常分布における、前記特定エッジのトラフィックの存在確率に応じたトラフィック量を、前記特定エッジを流れるトラフィック量に近付けるように学習して、前記グラフ構造内のトラフィックの流れを推定する推定部と、
を備える推定装置。
【請求項２】
前記推定部は、マルコフ連鎖モデルを用いて前記状態遷移モデルの定常分布を算出する請求項１に記載の推定装置。
【請求項３】
前記推定部は、前記定常分布における前記特定エッジのトラフィックの存在確率を、前記特定エッジを流れるトラフィック量に比例させるように学習する請求項１または２に記載の推定装置。
【請求項４】
前記推定部は、前記定常分布における複数の特定エッジ対のトラフィックの存在確率の比を、前記複数の特定エッジ対のトラフィック量の比に近付けるように学習する請求項１から３のいずれか一項に記載の推定装置。
【請求項５】
前記推定部は、各エッジに新たなトラフィックが出現する出現確率の学習パラメータと、前記グラフ構造全体のトラフィックのうち既に存在するトラフィックが継続される継続率の学習パラメータとを更に含む前記状態遷移モデルを用いて定常分布を算出する請求項１から４のいずれか一項に記載の推定装置。
【請求項６】
前記グラフ構造取得部は、各エッジの特徴を数値化したエッジ特徴量を更に取得し、
前記出現確率の学習パラメータは、前記グラフ構造内の各エッジに対応して設けた学習パラメータおよび前記グラフ構造の全エッジに共通して設けた学習パラメータを含み、
前記推定部は、各エッジの出現確率を、当該エッジに対応する学習パラメータと、当該エッジのエッジ特徴量に全エッジに共通する学習パラメータを乗じた値とに応じた確率とする請求項５に記載の推定装置。
【請求項７】
前記グラフ構造取得部は、各エッジから接続先エッジへの接続状態の特徴を数値化したエッジ対特徴量を更に取得し、
前記状態遷移確率の学習パラメータは、前記グラフ構造内の接続元および接続先のエッジの対に対応して設けた学習パラメータと、全エッジ対の接続に共通して設けた学習パラメータとを含み、
前記推定部は、各エッジ対の遷移確率を、当該エッジ対に対応する学習パラメータと、当該エッジ対のエッジ対特徴量に全エッジ対に共通する学習パラメータを乗じた値とに応じた確率とする請求項５または６に記載の推定装置。
【請求項８】
前記推定部は、複数の前記特定エッジのうちモデル構築用に選択した２以上の特定エッジに含まれる全ての２つの特定エッジの対について、トラフィック量の比および存在確率の比の差に応じた値を合計した値に正規化項を正則化パラメータの割合で加えた目的関数を最小化するように学習して、前記グラフ構造内のトラフィックの流れを推定し、
当該推定装置は、
複数通りの前記正則化パラメータについて前記推定部による推定処理を行わせ、前記複数の特定エッジのうちモデル評価用に選択した少なくとも１つの特定エッジについて算出されたトラフィックの存在確率に応じたトラフィック量が、当該少なくとも１つの特定エッジを流れるトラフィック量と最も近くなる前記正則化パラメータを選択する選択部
を更に備える請求項１から７のいずれか一項に記載の推定装置。
【請求項９】
前記特定エッジを流れるトラフィック量に基づいて、前記グラフ構造内の各エッジにおけるトラフィックの存在確率から、各エッジにおけるトラフィック量を予測する予測部を更に備える請求項１から８の何れか一項に記載の推定装置。
【請求項１０】
前記予測部は、
前記特定エッジにおけるトラフィックの存在確率の合計に対する、前記特定エッジを流れるトラフィック量の合計の比率である比例定数を算出する比例定数算出部と、
各エッジにおけるトラフィックの存在確率に前記比例定数を乗じて各エッジにおけるトラフィック量の予測値を算出する予測値算出部と、
を有する請求項９に記載の推定装置。
【請求項１１】
複数のエッジが接続されたグラフ構造内において全体のトラフィックが各エッジに分布する割合を示す存在確率を取得する存在確率取得部と、
前記グラフ構造内の一部のエッジである特定エッジを流れるトラフィック量を取得するトラフィック量取得部と、
前記特定エッジにおけるトラフィックの存在確率と、前記特定エッジを流れるトラフィック量とに基づいて、トラフィックの存在確率からトラフィック量への変換式を決定する決定部と、
各エッジにおけるトラフィックの存在確率から、前記変換式に基づいて各エッジにおけるトラフィック量の予測値を算出する予測値算出部と、
を備える推定装置。
【請求項１２】
前記決定部は、前記特定エッジにおけるトラフィックの存在確率の合計に対する、前記特定エッジを流れるトラフィック量の合計の比率である比例定数を算出し、
前記予測値算出部は、前記比例定数に応じた比例式によって、各エッジにおけるトラフィックの存在確率から各エッジにおけるトラフィック量の予測値を算出する
請求項１１に記載の推定装置。
【請求項１３】
複数のエッジが接続されたグラフ構造を取得するグラフ構造取得段階と、
前記グラフ構造内の一部のエッジである特定エッジを流れるトラフィック量を取得するトラフィック量取得段階と、
各エッジを通過したトラフィックが当該エッジに接続されたそれぞれのエッジに遷移する遷移確率分布の学習パラメータを含む状態遷移モデルの定常分布における、前記特定エッジのトラフィックの存在確率に応じたトラフィック量を、前記特定エッジを流れるトラフィック量に近付けるように学習して、前記グラフ構造内のトラフィックの流れを推定する推定段階と、
を備える推定方法。
【請求項１４】
前記特定エッジを流れるトラフィック量に基づいて、前記グラフ構造内の各エッジにおけるトラフィックの存在確率分布から、各エッジにおけるトラフィック量を予測する予測段階を更に備える請求項１３に記載の推定方法。
【請求項１５】
コンピュータに、請求項１から１２のいずれか一項に記載の推定装置として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、推定装置、推定方法、およびプログラムに関する。
【背景技術】
【０００２】
従来、道路交通網またはネットワーク上において、経路探索を実行して最適な経路を算出することが知られており、特に、マルコフ連鎖モデルを用いて経路を算出することが知られていた（例えば、特許文献１参照）。
［特許文献１］  特開２０１３−４１５３０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００３】
しかしながら、このような経路探索は、指定されたノードを始点とする複数の経路のうち、トラフィックが遷移する可能性が最も高い経路を算出するものであって、ネットワークを形成するそれぞれの経路のトラフィック量を把握することは、困難であった。したがって、ネットワーク内の限られたトラフィック量の測定結果に基づいて、ネットワーク全体のトラフィック量を推定することは困難であった。
【課題を解決するための手段】
【０００４】
本発明の第１の態様においては、複数のエッジが接続されたグラフ構造を取得するグラフ構造取得部と、グラフ構造内の一部のエッジである特定エッジを流れるトラフィック量を取得するトラフィック量取得部と、各エッジを通過したトラフィックが当該エッジに接続されたそれぞれのエッジに遷移する状態遷移確率の学習パラメータを含む状態遷移モデルの定常分布における、特定エッジのトラフィックの存在確率に応じたトラフィック量を、特定エッジを流れるトラフィック量に近付けるように学習して、グラフ構造内のトラフィックの流れを推定する推定部と、を備える推定装置、推定方法、およびプログラムを提供する。
【０００５】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではない。また、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【図面の簡単な説明】
【０００６】
【図１】本実施形態に係るグラフ構造１０の一例を示す。
【図２】本実施形態に係る推定装置１００の構成例を検出部１６と共に示す。
【図３】本実施形態に係る推定装置１００の動作フローを示す。
【図４】本実施形態に係る推定装置１００の変形例を検出部１６および存在確率算出装置２００と共に示す。
【図５】本実施形態に係る推定装置１００として機能するコンピュータ１９００のハードウェア構成の一例を示す。
【発明を実施するための形態】
【０００７】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【０００８】
図１は、本実施形態に係るグラフ構造１０の一例を示す。グラフ構造１０は、複数のエッジ１２が接続される。グラフ構造１０は、例えば、複数の車両が交通する複数の道路（エッジ）を備える交通網である。これに代えて、グラフ構造１０は、複数のノードに接続された経路（エッジ）を介してデータ等を通信するネットワーク等であってもよい。本実施例において、グラフ構造１０が交通網である例を説明する。
【０００９】
また、図１において、説明の便宜上、各エッジ１２を無向エッジとして表記しているが、実際には、通行方向に応じた有向エッジで表されたグラフ構造１０であってよい。この場合、図中の無向エッジは、道路が一方通行でなければ、一方向または反対方向のエッジの組で２つの有向エッジで表されてもよい。
【００１０】
グラフ構造１０は、複数のエッジ１２のうちの一部の特定エッジ１４のトラフィック量（交通量）を検出する検出部１６を備える。検出部１６は、一例として、特定エッジ１４のそれぞれに対応して配置され、各特定エッジ１４のトラフィック量をそれぞれ検出する。検出部１６は、対応する特定エッジ１４を交通する車両の動画または静止画を撮影するカメラを有してよく、これに代えて、交通する車両を検出するセンサを有していてもよい。また、検出部１６は、ほぼリアルタイムで検出結果を送信するライブカメラを有してもよい。
【００１１】
検出部１６は、有線または無線で接続されたネットワークに接続され、撮影した画像等をアクセス権限を有する要求者等に送信する。
【００１２】
グラフ構造１０の複数のエッジ１２のそれぞれのトラフィック量を把握したい場合、全てのエッジ１２を特定エッジ１４として、検出部１６を全てのエッジ１２に設け、特定エッジ１４の交通量を検出することが理想である。しかし、全てのエッジ１２に検出部１６を設けることが現実的では無い場合、許容されるコストの範囲で特定エッジ１４を設け、当該特定エッジ１４の検出結果から検出部１６が設けられていない他のエッジ１２のトラフィック量を推定すること等が考えられる。
【００１３】
しかしながら、例えば、特定エッジ１４が複数のエッジ１２のうちの略１０％程度以下の場合、全てのエッジ１２のトラフィック量を推定することは困難であった。特に、特定エッジ１４が複数のエッジ１２のうちの略３％程度の場合、検出部１６の検出結果から他のエッジ１２のトラフィック量を推定しても、推定誤差が大きくなってしまっていた。
【００１４】
一例として、このような推定方法に、始点と終点とを最短距離にすることに基づくＮｅｔｗｏｒｋ  ｔｏｍｏｇｒａｐｈｙ技術を適用すると、多くの主要道路でない道路の交通量をゼロに近づけてしまうので、実際のトラフィック量とは異なる結果しか得られなかった。そこで、本実施形態の推定装置は、複数のエッジ１２のうちの略１０％以下程度の限られた特定エッジ１４に設けられた検出部１６の検出結果に基づき、推定誤差を低減させつつ、他のエッジ１２のトラフィック量の予測を実行する。
【００１５】
図２は、本実施形態に係る推定装置１００の構成例を検出部１６と共に示す。推定装置１００は、グラフ構造１０のトラフィックシステムをマルコフ連鎖モデル等に基づく確率分布モデルで近似し、限られた地点に設けられた検出部１６の検出結果に基づいて定常状態における複数のエッジ１２のトラフィックの存在確率を求め、当該複数のエッジ１２のトラフィック量をそれぞれ予測する。推定装置１００は、グラフ構造取得部１１０と、トラフィック量取得部１３０と、推定部１４０と、予測部１５０とを備える。
【００１６】
グラフ構造取得部１１０は、複数のエッジ１２が接続されたグラフ構造１０を取得する。グラフ構造取得部１１０は、例えば、ブラウザ等の表示用ソフトウェアによって表示された地図情報のうち、ユーザにより指定された範囲の地図情報を取得する。これに代えて、グラフ構造取得部１１０は、ユーザが予め用意した地図情報等が入力されてもよい。
【００１７】
また、グラフ構造取得部１１０は、エッジ情報を取得する。ここで、エッジ情報は、入力されたグラフ構造１０内のエッジ１２の数、エッジ１２間の接続、および／または交差点の位置等に基づいて定められる情報である。
【００１８】
グラフ構造取得部１１０は、例えば、表示する地図情報に対応する複数のエッジ情報が予め記憶され、ユーザの範囲の指定に応じて、指定された地図情報の範囲内のエッジ情報が入力される。これに代えて、グラフ構造取得部１１０は、入力された地図情報に画像処理等を施してエッジ構造を解析してエッジ情報を取得してもよい。これに代えて、グラフ構造取得部１１０は、地図情報の入力と共に、ユーザがエッジ構造の入力または指定することにより、エッジ情報が入力されてもよい。
【００１９】
このように、グラフ構造取得部１１０は、入力された地図情報およびエッジ情報に応じたグラフ構造１０を取得する。また、グラフ構造取得部１１０は、各エッジ１２の特徴を数値化したエッジ特徴量を更に取得する。グラフ構造取得部１１０は、例えば、エッジ１２に隣接する建物等の情報を、エッジ特徴量として取得する。
【００２０】
グラフ構造取得部１１０は、例えば、エッジ情報と同様に、当該エッジ特徴量も予め記憶され、ユーザの範囲の指定に応じて、指定された地図情報の範囲内のエッジ特徴量が入力される。また、グラフ構造取得部１１０は、地図情報に画像処理等を施してエッジ特徴量を取得してもよく、これに代えて、ユーザの入力によってエッジ特徴量を取得してもよい。
【００２１】
また、グラフ構造取得部１１０は、各エッジ１２から接続先エッジ１２への接続状態の特徴を数値化したエッジ対特徴量を更に取得する。グラフ構造取得部１１０は、例えば、それぞれのエッジ１２と接続先エッジ１２との接続角度、道路種別、交通ルール等の情報を、エッジ対特徴量として取得する。グラフ構造取得部１１０は、エッジ特徴量と同様に、エッジ対特徴量を取得する。グラフ構造取得部１１０は、取得したグラフ構造１０、特徴量、およびエッジ対特徴量を推定部１４０に送信する。
【００２２】
トラフィック量取得部１３０は、グラフ構造１０内の一部のエッジ１２である特定エッジ１４を流れるトラフィック量を取得する。トラフィック量取得部１３０は、検出部１６にネットワークを介して接続され、特定エッジ１４を走行する車両のトラフィック量を取得する。
【００２３】
トラフィック量取得部１３０は、例えば、検出部１６から動画像または静止画像を検出結果として受け取る場合、当該画像等に画像処理を施して車両のトラフィック量を取得する。また、トラフィック量取得部１３０は、センサ等による車両の検出結果を受け取る場合、検出された車両の数をカウントして車両のトラフィック量を取得してもよい。トラフィック量取得部１３０は、取得したトラフィック量を推定部１４０に送信する。
【００２４】
推定部１４０は、各エッジ１２を通過したトラフィックが当該エッジ１２に接続されたそれぞれのエッジ１２に遷移する状態遷移確率の学習パラメータを含む状態遷移モデルの定常分布における、特定エッジ１４のトラフィックの存在確率に応じたトラフィック量を、特定エッジ１４を流れるトラフィック量に近付けるように学習して、グラフ構造１０内のトラフィックの流れを推定する。
【００２５】
推定部１４０は、グラフ構造取得部１１０に接続され、グラフ構造１０、エッジ特徴量、およびエッジ対特徴量を受け取る。また、推定部１４０は、トラフィック量取得部１３０に接続され、実際に特定エッジ１４を流れるトラフィック量を受け取る。ここで、状態遷移モデルは、一例として、初期状態確率と、状態遷移確率と、継続率とによって定められ、初期状態確率および状態遷移確率は、学習パラメータをそれぞれ含む。
【００２６】
推定部１４０は、遷移を開始するエッジ１２を決める確率分布として、初期状態確率を算出する。即ち、本実施形態の初期状態確率は、全てのエッジ１２のうち各エッジ１２に新たなトラフィックが出現する出現確率である。また、推定部１４０は、遷移元のエッジ１２から遷移先であるエッジ１２を決める確率分布として、状態遷移確率を算出する。ここで、遷移元のエッジ１２および遷移先のエッジ１２は、互いに隣接するエッジであり、遷移元のエッジ１２から遷移先のエッジ１２への車両の移動を「遷移」と称する。推定部１４０は、一のエッジ１２に対応する初期状態確率および状態遷移確率を継続率で関連づけた式を定義し、状態遷移モデルの定常分布を算出する。
【００２７】
ここで、状態遷移モデルの定常分布は、各エッジの車両の訪れやすさを示す確率分布である。また、「定常分布」とは、グラフ構造１０内のトラフィック量が、予め定められた時間内においての平均トラフィックの分布を示す。
【００２８】
推定部１４０は、２以上の特定エッジ１４のトラフィックの存在確率と、対応する２以上の特定エッジ１４で観測された実際のトラフィック量とを含む目的関数を算出する。そして、推定部１４０は、当該目的関数が最小となるように、初期状態確率および状態遷移確率の学習パラメータを決定する。ここで、推定部１４０による学習パラメータの決定を、「学習」と称する。
【００２９】
このように、推定部１４０は、トラフィックの存在確率に応じたトラフィック量を、特定エッジ１４を流れるトラフィック量に近付けて学習パラメータを決定する。そして、推定部１４０は、当該学習パラメータを用いて、特定エッジ１４を含む各エッジ１２のトラフィックの存在確率を推定する。推定部１４０は、推定した各エッジ１２のトラフィックの存在確率を予測部１５０に送信する。
【００３０】
予測部１５０は、特定エッジ１４を流れるトラフィック量に基づいて、グラフ構造１０内の各エッジ１２におけるトラフィックの存在確率から、各エッジ１２におけるトラフィック量を予測する。予測部１５０は、推定部１４０に接続され、各エッジ１２のトラフィックの存在確率と、実際に特定エッジ１４を流れるトラフィック量とを受け取る。予測部１５０は、比例定数算出部１５２と、予測値算出部１５４とを含む。
【００３１】
比例定数算出部１５２は、特定エッジ１４におけるトラフィックの存在確率の合計に対する、特定エッジ１４を流れるトラフィック量の合計の比率である比例定数を算出する。即ち、比例定数算出部１５２は、特定エッジ１４の推定されたトラフィックの存在確率の総和と、実際に特定エッジ１４を流れるトラフィック量の総和とをそれぞれ算出した後に、算出結果である２つの総和の比を取って比例定数を算出する。
【００３２】
ここで、比例定数は、特定エッジ１４の推定されたトラフィックの存在確率と観測された当該特定エッジ１４を流れるトラフィック量の比率であり、また、各エッジ１２の推定されたトラフィックの存在確率と実際に観測されるべきトラフィック量の比率でもある。比例定数算出部１５２は、算出した比例定数と各エッジ１２の推定されたトラフィックの存在確率とを予測値算出部１５４に送信する。
【００３３】
予測値算出部１５４は、各エッジ１２におけるトラフィックの存在確率に比例定数を乗じて各エッジ１２におけるトラフィック量の予測値を算出する。予測値算出部１５４は、比例定数算出部１５２に接続され、受け取った比例定数と各エッジ１２の推定されたトラフィックの存在確率とを乗じて、各エッジ１２において実際に観測されるべきトラフィック量の予測値を算出する。予測値算出部１５４は、算出した予測値を、推定装置１００の出力結果として出力する。
【００３４】
図３は、本実施形態に係る推定装置１００の動作フローを示す。推定装置１００は、当該動作フローを実行して、グラフ構造１０および特定エッジ１４のトラフィック量の検出結果から、各エッジ１２のトラフィック量の予測値を出力する。
【００３５】
まず、グラフ構造取得部１１０は、グラフ構造１０を取得する（Ｓ３１０）。ここで、エッジ１２をｘとし、グラフ構造１０に含まれるエッジ１２の集合をχとし、エッジ１２の数を｜χ｜とすると、ｘは次式のように定義される。
（数１）
ｘ∈χ≡｛１，２，...，｜χ｜｝
【００３６】
また、グラフ構造取得部１１０は、エッジ１２のエッジ特徴量から、次式で定義される特徴ベクトル関数φＩ（ｘ）を定める。本実施形態において、φＩ（ｘ）は、ｍ個の実数の要素を有する列ベクトルである。
【数２】
2015018377.tif 000003
【００３７】
φＩ（ｘ）の要素は、一例として、ｘの近傍に存在する建物情報に応じて１または０の値が定められる。ここで、建物情報は、例えば、ホテル、駅、銀行、郵便局、役所、公民館、病院、バス停、コンビニエンスストア、ショッピングモール、デパート、百貨店、ファストフードショップ、市民ホール、および／または住宅等を含む。
【００３８】
例えば、特徴ベクトル関数の１番目の要素がホテルを示し、２番目の要素が駅を示し、３番目の要素が銀行を示す場合において、φＩ（ｘ）Ｔ＝（１，０，１・・・）は、ｘにホテルおよび銀行が隣接することを示す。ここで、「Ｔ」は、ベクトルφＩ（ｘ）の転置を示す（即ち、φＩ（ｘ）Ｔは行ベクトルを示す）。
【００３９】
また、グラフ構造取得部１１０は、エッジ１２のエッジ対特徴量から、次式で定義される道路対の特徴ベクトル関数ψT（ｘ，ｘ'）を定める。本実施形態において、ψT（ｘ，ｘ'）は、ｎ個の実数の要素を有する列ベクトルである。
【数３】
2015018377.tif 000004
【００４０】
ψT（ｘ，ｘ'）は、｜χ｜×｜χ｜個の組み合わせがあるが、ｘとｘ'が接続されたエッジ対である場合に、ψT（ｘ，ｘ'）は物理的に意味のあるデータとなる。ここで、物理的に意味の無いデータ（即ち、要素の値）を、０とみなし、データの格納を省略してもよい。
【００４１】
ここで、ψT（ｘ，ｘ'）の要素は、例えば、ｘとｘ'のなす角度θｘ，ｘ'に基づく特徴量、およびｘ'が主要な道路か否かに基づく特徴量等を含む。より具体的には、ψT（ｘ，ｘ'）＝（ｃｏｓ（θｘ，ｘ'），ｒ（ｘ'），・・・）Ｔと定められてよい。ここで、関数ｒ（ｘ）は、一例として、道路が主要な道路か否かを示す関数であり、例えば、道路幅または車線数に応じて値が大きくなる関数である。また、関数ｒ（ｘ）は、予め定められた値の範囲に規格化された関数でよい。
【００４２】
次に、トラフィック量取得部１３０は、トラフィック量を取得する（Ｓ３２０）。これに代えて、トラフィック量取得部１３０は、グラフ構造取得部１１０のグラフ構造１０の取得と、並行してトラフィック量を取得してもよい。また、トラフィック量取得部１３０は、グラフ構造取得部１１０によるグラフ構造１０の取得の前に、トラフィック量を取得してもよい。
【００４３】
次に、推定部１４０は、パラメータの学習を実行する（Ｓ３３０）。推定部１４０は、マルコフ連鎖モデルを用いて状態遷移モデルの定常分布を算出する。ここで、マルコフ連鎖モデルは、離散的な状態が時間的に変化（遷移または推移）する確率過程において、遷移確率が過去の状態には依存せず、現在の状態にのみ依存するモデルである。例えば、一のエッジ１２を走行している車両が、交差点に達した後、次に他のエッジ１２に遷移する（例えば、直進する、左に曲がる、または右に曲がる）確率は、当該一のエッジ１２の前に走行していたエッジ１２には依存しないことを意味する。
【００４４】
本実施例において、推定部１４０は、初期状態確率ｐＩν（ｘ）と、状態遷移確率ｐＴω（ｘ'｜ｘ）と、継続率βとによって状態遷移モデルを定める。初期状態確率ｐＩν（ｘ）は、どのエッジ１２から遷移を開始するかを定める確率分布関数であり、本実施例において、当該確率分布関数は、次式で示すギブス分布に等しいとした。
【数４】
2015018377.tif 000005
【００４５】
ここで、ベクトルνは、列ベクトルνｌｏｃａｌおよびνｇｌｏｂａｌで定義される学習パラメータである。ここで、列ベクトルνｌｏｃａｌは、一例として、各エッジ１２にそれぞれ対応付けられたパラメータであり、エッジ１２の数｜χ｜と同数の実数の要素を有する。また、列ベクトルνｇｌｏｂａｌは、一例として、特徴ベクトル関数φＩ（ｘ）と作用するｍ個の実数の要素を有する列ベクトルである。ベクトルνは、次式で示される。
【数５】
2015018377.tif 000006
【００４６】
また、ｓＩ（ｘ；ν）は、次式で示す道路スコア関数である。ここで、νｌｏｃａｌｘは、ベクトルνｌｏｃａｌのｘ番目の要素（即ち、ｘに対応するパラメータ）を示す。
【数６】
2015018377.tif 000007
【００４７】
このように、初期状態確率ｐＩν（ｘ）の学習パラメータ（ベクトルν）は、グラフ構造１０内の各エッジ１２に対応して設けた学習パラメータνｌｏｃａｌおよびグラフ構造１０の全エッジ１２に共通して設けた学習パラメータνｇｌｏｂａｌを含む。そして、推定部１４０は、各エッジ１２の初期状態確率ｐＩν（ｘ）を、当該エッジ１２に対応する学習パラメータνｌｏｃａｌと、当該エッジ１２のエッジ特徴量に基づく関数φＩ（ｘ）Ｔに全エッジ１２に共通する学習パラメータνｇｌｏｂａｌを乗じた値とを加算した、道路スコア関数ｓＩ（ｘ；ν）に応じた確率とする。
【００４８】
このように、関数φＩ（ｘ）Ｔに学習パラメータνｇｌｏｂａｌを乗じるので、学習パラメータνｇｌｏｂａｌは、例えば、ホテル、駅等の建物の存在によりトラフィックの出現等に与える影響を調節するパラメータとなる。また、道路スコア関数ｓＩ（ｘ；ν）にエッジ１２毎に対応して設けた学習パラメータνｌｏｃａｌが加算されているので、学習パラメータνｌｏｃａｌは、各道路に固有の特徴がトラフィックの出現等に与える影響を調節するパラメータとなる。
【００４９】
状態遷移確率ｐＴω（ｘ'｜ｘ）は、エッジ１２（ｘ）から、エッジ１２に隣接したエッジ１２のうち、次にどのエッジ１２（ｘ'）に遷移するかを定める確率分布関数である。ここで、ｘ'は、ｘから車両が直接進むことができるエッジ１２の集合χｘに含まれる（ｘ'∈χｘ）。本実施例において、当該確率分布関数は、次式で示すギブス分布に等しいとした。
【数７】
2015018377.tif 000008
【００５０】
ここで、ベクトルωは、ｖｅｃ（Ωｌｏｃａｌ）およびωｇｌｏｂａｌで定義される学習パラメータである。ここで、ｖｅｃ（Ωｌｏｃａｌ）は、行列Ωｌｏｃａｌを列ベクトル表現に変換した列ベクトルである。また、Ωｌｏｃａｌは、遷移前のエッジ１２（ｘ）および遷移後のエッジ１２（ｘ'）の組み合わせにそれぞれ対応付けられた要素を有する行列であり、一例として、｜χ｜×｜χ｜個の数の実数の要素を有する。ここで、Ωｌｏｃａｌの要素のうち、隣り合う２つのエッジ１２の組み合わせに対応する要素が、物理的に意味のあるデータを有する。
【００５１】
また、列ベクトルωｇｌｏｂａｌは、一例として、道路対の特徴ベクトル関数ψT（ｘ，ｘ'）と作用するｎ個の実数の要素を有する列ベクトルである。ベクトルωは、次式で示される。
【数８】
2015018377.tif 000009
【００５２】
また、ｓＴ（ｘ，ｘ'；ω）は、次式で示す道路対スコア関数である。ここで、Ωｌｏｃａｌｘ，ｘ'は、行列Ωｌｏｃａｌのｘ行ｘ'列の要素（即ち、ｘおよびｘ'の組み合わせに対応するパラメータ）を示す。
【数９】
2015018377.tif 000010
【００５３】
このように、状態遷移確率ｐＴω（ｘ'｜ｘ）の学習パラメータ（ベクトルω）は、グラフ構造１０内の接続元および接続先のエッジの対（組）に対応して設けた学習パラメータｖｅｃ（Ωｌｏｃａｌ）と、全エッジ対の接続に共通して設けた学習パラメータωｇｌｏｂａｌとを含む。推定部１４０は、各エッジ１２間の状態遷移確率を、当該エッジ１２間に対応する学習パラメータΩｌｏｃａｌｘ，ｘ'と、当該エッジ対のエッジ対特徴量に基づく関数ψT（ｘ，ｘ'）Ｔに全エッジ対に共通する学習パラメータωｇｌｏｂａｌを乗じた値とを加算した、道路対スコア関数ｓＴ（ｘ，ｘ'；ω）に応じた確率とする。
【００５４】
このように、関数ψT（ｘ，ｘ'）Ｔに学習パラメータωｇｌｏｂａｌを乗じるので、学習パラメータωｇｌｏｂａｌは、例えば、遷移する前後の複数のエッジ１２間に共通する特徴が、トラフィックの遷移等に与える影響を調節するパラメータとなる。また、道路対スコア関数ｓＴ（ｘ，ｘ'；ω）にエッジ１２間毎に対応して設けた学習パラメータΩｌｏｃａｌｘ，ｘ'が加算されているので、学習パラメータΩｌｏｃａｌｘ，ｘ'は、各エッジ対に固有の特徴が、トラフィックの遷移等に与える影響を調節するパラメータとなる。
【００５５】
継続率βは、グラフ構造１０全体のトラフィックのうち既に存在するトラフィックが継続される割合を示す。継続率βは、一例として、当該継続率βの値が１の場合、全てのトラフィックが継続し、当該継続率βの値が０の場合、全てのトラフィックが継続しないと定義される。本実施形態において、継続率βをシグモイド関数ζ（ｂ）とし、ｂを学習パラメータとする。
【００５６】
ここで、シグモイド関数ζ（ｂ）は、ｙ＝０およびｙ＝１を漸近線とし、ｘがマイナス方向の無限大の値に近づくと、ζ（ｘ）は０に近づき、ｘがプラス方向の無限大の値に近づくと、ζ（ｘ）は１に近づく、１つの変曲点を有する単調増加関数である。シグモイド関数ζ（ｂ）は、次式のように示される。
【数１０】
2015018377.tif 000011
【００５７】
ここで、シグモイド関数ζ（ｂ）を用いるのは、任意の実数ｘに対して値が０から１の範囲に収まる連続関数であり、任意の値ｂに収束したとしてもβの値を０から１の範囲内に抑えられるようにして学習を容易化するためである。また、ここで、式中に用いた記号「：＝」は、右辺から左辺への代入を意味する。
【００５８】
以上のように、推定部１４０は、出現確率（初期状態確率ｐＩν（ｘ））の学習パラメータ（ベクトルν）と、状態遷移確率ｐＴω（ｘ'｜ｘ）の学習パラメータ（ベクトルω）と、継続率βの学習パラメータ（ｂ）とを含む状態遷移モデルを用いて定常分布を算出する。推定部１４０は、次式で定められるｘ行ｘ'列の要素を有する状態遷移確率行列Ｐθを算出する。ここで、θは学習パラメータν、ω、ｂをまとめたベクトルθ≡［νT， ωT，ｂ］Tである。
【数１１】
2015018377.tif 000012
【００５９】
即ち、推定部１４０は、トラフィックが他のエッジ１２から一のエッジ１２（ｘ'）に遷移した後に継続して定常分布となる確率を、状態遷移確率ｐＴω（ｘ'｜ｘ）に継続率βを乗じた値として算出する。また、推定部１４０は、トラフィックが一のエッジ１２（ｘ'）に発生して定常分布となる確率を、初期状態確率ｐＩν（ｘ）に継続率（１−β）を乗じた値として算出する。そして、推定部１４０は、算出した両者の和を、定常状態における一のエッジ１２（ｘ'）の状態遷移確率行列の要素｛Ｐθ｝ｘ，ｘ'とする。
【００６０】
そして、推定部１４０は、状態遷移確率行列Ｐθを正規化することで得られるベクトルを、定常確率ベクトルπθとする。即ち、Ｐθの固有値１に対応する固有ベクトルを算出し、当該固有ベクトルの要素の総和が１になるように正規化することによって、定常確率ベクトルπθを得る。
【００６１】
ここで、本実施形態の推定部１４０は、各エッジ１２のトラフィック量が当該エッジ１２の定常状態におけるトラフィックの存在確率（即ち、定常確率πθ（ｘ））に比例するものとして、学習を実行する。即ち、推定部１４０は、定常分布における特定エッジ１４のトラフィックの存在確率を、特定エッジ１４を流れるトラフィック量に比例させるように学習パラメータθを最適化する。
【００６２】
具体的には、推定部１４０は、トラフィック量取得部１３０が取得した特定エッジ１４のトラフィック量をｆ（ｘ）とすると、ｆ（ｘ）＝ｃ×πθ（ｘ）と仮定する。ここで、ｃは比例定数である。また、ｆ（ｘ）は、予め定められた時間内においての平均トラッフィク量である。推定部１４０は、定常分布における複数の特定エッジ１４間のトラフィックの存在確率の比を、複数の特定エッジ１４間のトラフィック量の比に近付けるように学習する。このように、推定部１４０は、複数の特定エッジ１４のトラフィック量の比を取ることで、比例定数をキャンセルして学習を実行する。
【００６３】
推定部１４０は、一例として、定常分布における２つの特定エッジ１４間のトラフィックの存在確率の比πθ（ｉ）／πθ（ｊ）を、２つの特定エッジ１４間のトラフィック量ｆ（ｉ）／ｆ（ｊ）の比に近付ける。推定部１４０は、次式で示される目的関数Ｌを最小化するように学習して、グラフ構造１０内のトラフィックの流れを推定する。推定部１４０は、状態遷移確率ｐＴωおよび存在確率πθ（ｘ）の少なくとも一方を推定してよい。
【数１２】
2015018377.tif 000013
【００６４】
このように、推定部１４０は、複数の特定エッジ１４のうちモデル構築用に選択した２以上の特定エッジ１４に含まれる全ての２つの特定エッジ１４の組について、トラフィック量の比および存在確率の比の差に応じた値を合計した値に正規化項（θＴθ／２）を正則化パラメータλの割合で加えた目的関数を最小化する。推定部１４０は、例えば、関数の傾きから当該関数の最小値を取得する最急降下法等の、勾配法によって目的関数を最小化する。
【００６５】
推定部１４０は、一例として、各パラメータを初期化して、目的関数の勾配を算出し、当該勾配の値に応じて学習パラメータを更新し、更新前の学習パラメータとの差分が予め定められた閾値以下になるまで学習パラメータの更新を繰り返す。具体的には、推定部１４０は、学習パラメータであるベクトルθを零ベクトルに、正則化パラメータλおよび更新パラメータηを予め定められた０以上の値にそれぞれ定める。
【００６６】
推定部１４０は、推定部１４０が定義した継続率β、状態遷移確率行列Ｐθ、および定常確率ベクトルπθをそれぞれ算出する。そして、推定部１４０は、次式のように、目的関数の勾配を算出する。
【数１３】
2015018377.tif 000014
【００６７】
ここで、｛πθ｝iは、ベクトルπθの第ｉ成分のことである。次に、推定部１４０は、算出した勾配と更新パラメータηとを乗じた値を学習パラメータから差し引いて、学習パラメータを次式のように更新する。
【数１４】
2015018377.tif 000015
【００６８】
推定部１４０は、更新前と更新後の学習パラメータの絶対値の差分が、予め定められた閾値未満となるまで、学習パラメータの更新を繰り返して学習する。推定部１４０は、当該差分が閾値未満となった場合の学習パラメータを、最適パラメータとする。これに代えて、推定部１４０は、学習パラメータの更新を予め定められた回数繰り返した後の学習パラメータを、最適パラメータとしてもよい。
【００６９】
次に、推定部１４０は、トラフィックの存在確率を推定する（Ｓ３４０）。推定部１４０は、最適パラメータにおける各エッジ１２の定常確率πθ（ｘ）を算出し、当該確率を各エッジ１２におけるトラフィックの存在確率と推定する。マルコフ連鎖モデルの場合には、このようにＰθからπθを得る算出方法は既知である。また、その他の任意のモデルにおいても、各エッジ１２の存在確率が収束するように繰り返し遷移させることで算出することができる。
【００７０】
次に、比例定数算出部１５２は、比例定数ｃを算出する（Ｓ３５０）。比例定数算出部１５２は、トラフィック量取得部１３０によって取得された全ての特定エッジ１４のトラフィック量の総和と、推定部１４０が推定した当該全ての特定エッジ１４に対応するトラフィックの存在確率の総和との比を算出する。比例定数算出部１５２は、特定エッジ１４のトラフィック量ｆ（ｘ）が、ｃ×πθ（ｘ）に等しいと仮定されているので、次式のように、比例定数ｃを算出することができる。
【数１５】
2015018377.tif 000016
【００７１】
次に、予測値算出部１５４は、グラフ構造１０内の特定エッジ１４を除く各エッジ１２のトラフィック量を予測する（Ｓ３６０）。ここで、各エッジ１２のトラフィック量も、特定エッジ１４と同様に、ｆ（ｘ）＝ｃ×πθ（ｘ）と仮定できるので、予測値算出部１５４は、比例定数算出部１５２が算出した比例定数ｃと、推定部１４０が推定した各エッジ１２のトラフィック量πθ（ｘ）とを乗じることにより、各エッジ１２のトラフィック量ｆ（ｘ）を予測できる。
【００７２】
以上の本実施形態に係る推定装置１００の動作フローによれば、推定装置１００は、限られた個数の検出部１６から取得したトラフィック量に基づき、グラフ構造１０内の各エッジ１２のトラフィック量を予測することができる。推定装置１００は、一例として、道路数（即ち、エッジ１２の総数）１４９７、ｗｅｂカメラを有する道路数（即ち、特定エッジ１４の総数）５２、および交差点数３４３４を含むグラフ構造１０のトラフィック量を予測し、モンテカルロ近似等による予測結果と比べて推定誤差を略半分にすることができた。
【００７３】
このように、本実施形態に係る推定装置１００は、マルコフ連鎖モデルを用いることにより、複数のエッジ１２のうちの略１０％以下程度の限られた特定エッジ１４に設けられた検出部１６の検出結果に基づき、推定誤差を低減させつつ、他のエッジ１２のトラフィック量の予測を実行することができる。また、推定装置１００は、エッジ特徴量およびエッジ対特徴量を定めることで、トラフィック量の予測を実行することができるので、従来手法に比べてより少ない情報量に基づいて道路交通網全体の交通状態を予測することができる。
【００７４】
以上の本実施形態に係る推定装置１００において、推定部１４０は、正則化パラメータλを予め定められた初期値に設定することを説明した。これに代えて、推定部１４０は、予め複数の正則化パラメータλの候補を用意し、適切なパラメータを選択する、交差検定法によって正則化パラメータλを定めてもよい。
【００７５】
この場合、推定装置１００は、複数通りの正則化パラメータλについて推定部１４０による推定処理を実行させる。そして、推定装置１００は、選択部を更に備え、当該選択部は、複数の特定エッジ１４のうちモデル評価用に選択した少なくとも１つの特定エッジ１４について算出されたトラフィックの存在確率πθ（ｘ）に応じたトラフィック量が、当該少なくとも１つの特定エッジ１４を流れるトラフィック量と最も近くなる正則化パラメータλを選択する。これによって、推定装置１００は、より推定誤差を低減させたトラフィック量の予測を実行することができる。
【００７６】
以上の本実施形態に係る推定装置１００は、特定エッジ１４のトラフィック量の検出結果に基づき、他のエッジ１２のトラフィック量の予測を実行することを説明した。ここで、推定装置１００は、交差検定法によって、予測したトラフィック量の誤差を測定してもよい。推定装置１００は、ｎ個の特定エッジ１４のうち、ｍ個（ｍ＜ｎ）の特定エッジ１４を用いて、他のエッジ１２のトラフィック量の予測を実行することができる。
【００７７】
すると、トラフィック量の予測には用いられなかったｎ−ｍ個の特定エッジ１４については、トラフィック量の予測結果と、検出部１６の検出結果とを得ることができる。したがって、推定装置１００は、予測結果と検出結果とを比較することによって、実行した予測の誤差を得ることができる。
【００７８】
そこで、推定装置１００は、例えば、予測結果と共に、当該誤差を出力する。また、推定装置１００は、予め定められた閾値よりも得られた誤差が小さい場合に、予測結果を出力してもよい。また、推定装置１００は、予め定められた閾値よりも得られた誤差が大きい場合に、予測に用いるパラメータの値および／またはパラメータの数を変更して予測を繰り返して実行してもよい。
【００７９】
図４は、本実施形態に係る推定装置１００の変形例を、検出部１６および存在確率算出装置２００と共に示す。本変形例の推定装置１００において、図２に示された本実施形態に係る推定装置１００の動作と略同一のものには同一の符号を付け、説明を省略する。本変形例の推定装置１００は、当該推定装置１００とは異なる外部の装置が算出した存在確率πθ（ｘ）を取得し、複数のエッジ１２のトラフィック量ｆ（ｘ）の予測を実行する。
【００８０】
ここで、外部の装置は、一例として、グラフ構造１０およびグラフ構造１０内の特定エッジ１４を流れるトラフィック量に応じて、グラフ構造１０内の各エッジ１２の存在確率πθ（ｘ）を算出する存在確率算出装置２００である。存在確率算出装置２００は、本変形例の推定装置１００とは個別に動作して、各エッジ１２の存在確率πθ（ｘ）を算出する。存在確率算出装置２００は、別個独立の装置であってよく、この場合、本変形例の推定装置１００とネットワーク等で接続される。
【００８１】
存在確率算出装置２００は、グラフ構造取得部１１０と、トラフィック量取得部１３０と、推定部１４０とを備える。存在確率算出装置２００が、各エッジ１２の存在確率πθ（ｘ）を算出する動作は、既に本実施形態に係る推定装置１００の動作において説明したので省略する。
【００８２】
本変形例の推定装置１００は、トラフィック量取得部１３０と、予測部１５０とを備える。トラフィック量取得部１３０は、検出部１６に接続され、グラフ構造１０内の一部のエッジである特定エッジ１４を流れるトラフィック量を取得する。予測部１５０は、トラフィック量取得部１３０および存在確率算出装置２００にそれぞれ接続され、特定エッジ１４のトラフィック量および各エッジ１２の存在確率に応じて、各エッジ１２のトラフィック量を予測する。予測部１５０は、存在確率取得部２１０と、決定部２２０と、予測値算出部２３０とを有する。
【００８３】
存在確率取得部２１０は、複数のエッジが接続されたグラフ構造内において全体のトラフィックが各エッジに分布する割合を示す存在確率πθ（ｘ）を取得する。存在確率取得部２１０は、存在確率算出装置２００から存在確率πθ（ｘ）を取得する。これに代えて、存在確率取得部２１０は、予め定められ、装置外部または装置内部に記憶された存在確率πθ（ｘ）を読み出して取得してもよい。
【００８４】
決定部２２０は、特定エッジ１４におけるトラフィックの存在確率πθ（ｘ）と、特定エッジ１４を流れるトラフィック量ｆ（ｘ）とに基づいて、トラフィックの存在確率πθ（ｘ）からトラフィック量ｆ（ｘ）への変換式を決定する。決定部２２０は、存在確率πθ（ｘ）およびトラフィック量ｆ（ｘ）の理想的な関係から変換式を決定してよく、これに代えて、存在確率πθ（ｘ）およびトラフィック量ｆ（ｘ）の値を対比させて変換式を決定してもよい。
【００８５】
決定部２２０は、例えば、特定エッジにおけるトラフィックの存在確率πθ（ｘ）の合計に対する、特定エッジ１４を流れるトラフィック量ｆ（ｘ）の合計の比率である比例定数ｃを算出する。この場合、決定部２２０の動作は、本実施形態に係る推定装置１００の比例定数算出部１５２の動作と略同一であり、即ち、当該比例定数算出部１５２は、本変形例の決定部２２０の一例である。
【００８６】
予測値算出部２３０は、各エッジ１２におけるトラフィックの存在確率πθ（ｘ）から、決定部２２０が決定した変換式に基づいて各エッジ１２におけるトラフィック量ｆ（ｘ）の予測値を算出する。予測値算出部２３０は、例えば、比例定数ｃに応じた比例式によって、各エッジ１２におけるトラフィックの存在確率πθ（ｘ）から各エッジ１２におけるトラフィック量ｆ（ｘ）の予測値を算出する。この場合、予測値算出部２３０の動作は、本実施形態に係る推定装置１００の予測値算出部１５４の動作と略同一であり、即ち、当該予測値算出部１５４は、本変形例の予測値算出部２３０の一例である。
【００８７】
以上の本変形例の推定装置１００によれば、予め外部の装置等で定められた存在確率πθ（ｘ）を用いて、複数のエッジ１２のトラフィック量ｆ（ｘ）の予測を実行することができる。これにより、本変形例の推定装置１００は、例えば、複数回の予測を実行する場合に、取得した存在確率πθ（ｘ）を用い続けることで、予測回数よりも少ない回数の存在確率の取得回数でトラフィック量ｆ（ｘ）の予測を実行することができる。また、外部の装置が、例えば時間帯等の異なる条件毎に複数の存在確率πθ（ｘ）を予め算出し、本変形例の推定装置１００が、特定エッジ１４の検出条件に対応する存在確率πθ（ｘ）を選択して予測を実行することで、特定エッジ１４のトラフィックを検出した条件応じたトラフィック量ｆ（ｘ）の予測を実行することができる。
【００８８】
図５は、本実施形態に係る推定装置１００として機能するコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、および表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、およびＤＶＤドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、および入出力チップ２０７０を有するレガシー入出力部と、を備える。
【００８９】
ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００およびグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０およびＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【００９０】
入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＤＶＤドライブ２０６０を接続する。通信インターフェイス２０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラムおよびデータを格納する。ＤＶＤドライブ２０６０は、ＤＶＤ−ＲＯＭ２０９５からプログラムまたはデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。
【００９１】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、および入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラム、および／または、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラムまたはデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０を入出力コントローラ２０８４へと接続すると共に、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を入出力コントローラ２０８４へと接続する。
【００９２】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＤＶＤ−ＲＯＭ２０９５、またはＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。
【００９３】
プログラムは、コンピュータ１９００にインストールされ、コンピュータ１９００をグラフ構造取得部１１０、トラフィック量取得部１３０、推定部１４０、および予測部１５０として機能させる。
【００９４】
プログラムに記述された情報処理は、コンピュータ１９００に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段であるグラフ構造取得部１１０、トラフィック量取得部１３０、推定部１４０、および予測部１５０として機能する。そして、この具体的手段によって、本実施形態におけるコンピュータ１９００の使用目的に応じた情報の演算または加工を実現することにより、使用目的に応じた特有の推定装置１００が構築される。
【００９５】
一例として、コンピュータ１９００と外部の装置等との間で通信を行う場合には、ＣＰＵ２０００は、ＲＡＭ２０２０上にロードされた通信プログラムを実行し、通信プログラムに記述された処理内容に基づいて、通信インターフェイス２０３０に対して通信処理を指示する。通信インターフェイス２０３０は、ＣＰＵ２０００の制御を受けて、ＲＡＭ２０２０、ハードディスクドライブ２０４０、フレキシブルディスク２０９０、またはＤＶＤ−ＲＯＭ２０９５等の記憶装置上に設けた送信バッファ領域等に記憶された送信データを読み出してネットワークへと送信し、もしくは、ネットワークから受信した受信データを記憶装置上に設けた受信バッファ領域等へと書き込む。このように、通信インターフェイス２０３０は、ＤＭＡ（ダイレクト・メモリ・アクセス）方式により記憶装置との間で送受信データを転送してもよく、これに代えて、ＣＰＵ２０００が転送元の記憶装置または通信インターフェイス２０３０からデータを読み出し、転送先の通信インターフェイス２０３０または記憶装置へとデータを書き込むことにより送受信データを転送してもよい。
【００９６】
また、ＣＰＵ２０００は、ハードディスクドライブ２０４０、ＤＶＤドライブ２０６０（ＤＶＤ−ＲＯＭ２０９５）、フレキシブルディスク・ドライブ２０５０（フレキシブルディスク２０９０）等の外部記憶装置に格納されたファイルまたはデータベース等の中から、全部または必要な部分をＤＭＡ転送等によりＲＡＭ２０２０へと読み込ませ、ＲＡＭ２０２０上のデータに対して各種の処理を行う。そして、ＣＰＵ２０００は、処理を終えたデータを、ＤＭＡ転送等により外部記憶装置へと書き戻す。このような処理において、ＲＡＭ２０２０は、外部記憶装置の内容を一時的に保持するものとみなせるから、本実施形態においてはＲＡＭ２０２０および外部記憶装置等をメモリ、記憶部、または記憶装置等と総称する。本実施形態における各種のプログラム、データ、テーブル、データベース等の各種の情報は、このような記憶装置上に格納されて、情報処理の対象となる。なお、ＣＰＵ２０００は、ＲＡＭ２０２０の一部をキャッシュメモリに保持し、キャッシュメモリ上で読み書きを行うこともできる。このような形態においても、キャッシュメモリはＲＡＭ２０２０の機能の一部を担うから、本実施形態においては、区別して示す場合を除き、キャッシュメモリもＲＡＭ２０２０、メモリ、および／または記憶装置に含まれるものとする。
【００９７】
また、ＣＰＵ２０００は、ＲＡＭ２０２０から読み出したデータに対して、プログラムの命令列により指定された、本実施形態中に記載した各種の演算、情報の加工、条件判断、情報の検索・置換等を含む各種の処理を行い、ＲＡＭ２０２０へと書き戻す。例えば、ＣＰＵ２０００は、条件判断を行う場合においては、本実施形態において示した各種の変数が、他の変数または定数と比較して、大きい、小さい、以上、以下、等しい等の条件を満たすかどうかを判断し、条件が成立した場合（または不成立であった場合）に、異なる命令列へと分岐し、またはサブルーチンを呼び出す。
【００９８】
また、ＣＰＵ２０００は、記憶装置内のファイルまたはデータベース等に格納された情報を検索することができる。例えば、第１属性の属性値に対し第２属性の属性値がそれぞれ対応付けられた複数のエントリが記憶装置に格納されている場合において、ＣＰＵ２０００は、記憶装置に格納されている複数のエントリの中から第１属性の属性値が指定された条件と一致するエントリを検索し、そのエントリに格納されている第２属性の属性値を読み出すことにより、所定の条件を満たす第１属性に対応付けられた第２属性の属性値を得ることができる。
【００９９】
以上に示したプログラムまたはモジュールは、外部の記録媒体に格納されてもよい。記録媒体としては、フレキシブルディスク２０９０、ＤＶＤ−ＲＯＭ２０９５の他に、ＤＶＤ、Ｂｌｕ−ｒａｙ（登録商標）、またはＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークまたはインターネットに接続されたサーバシステムに設けたハードディスクまたはＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。
【０１００】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【０１０１】
特許請求の範囲、明細書、および図面中において示した装置、システム、プログラム、および方法における動作、手順、ステップ、および段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り、任意の順序で実現しうることに留意すべきである。特許請求の範囲、明細書、および図面中の動作フローに関して、便宜上「まず、」、「次に、」等を用いて説明したとしても、この順で実施することが必須であることを意味するものではない。
【符号の説明】
【０１０２】
１０  グラフ構造、１２  エッジ、１４  特定エッジ、１６  検出部、１００  推定装置、１１０  グラフ構造取得部、１３０  トラフィック量取得部、１４０  推定部、１５０  予測部、１５２  比例定数算出部、１５４  予測値算出部、２００  存在確率算出装置、２１０  存在確率取得部、２２０  決定部、２３０  予測値算出部、１９００  コンピュータ、２０００  ＣＰＵ、２０１０  ＲＯＭ、２０２０  ＲＡＭ、２０３０  通信インターフェイス、２０４０  ハードディスクドライブ、２０５０  フレキシブルディスク・ドライブ、２０６０  ＤＶＤドライブ、２０７０  入出力チップ、２０７５  グラフィック・コントローラ、２０８０  表示装置、２０８２  ホスト・コントローラ、２０８４  入出力コントローラ、２０９０  フレキシブルディスク、２０９５  ＤＶＤ−ＲＯＭ
【図１】
2015018377.tif 000017
【図２】
2015018377.tif 000018
【図３】
2015018377.tif 000019
【図４】
2015018377.tif 000020
【図５】
2015018377.tif 000021