Extracting Places and Activities from GPS traces
4章 行動認識のためのConditional random field
この章では、ロケーションデータから行動認識を行うためのCRFのアプリケーションについて述べる。そして、生のGPSデータから階層的な行動モデルに変換するCRFを作り出す方法、それと同時に全ての行動の種類と重要な場所をラベル付けする方法を述べる。
述べているように、空間的な関係に基づいてGPSデータを連続的なGPS軌跡に分割する。道路マップなしうまく(10mで実行したい)距離での分割をすることもできる。
しかし、マップに記載されている場所などとGPS軌跡を対応付けるためにはマップがあることが望ましい。
道路のassociationと軌跡の分割を同時に推定するために、10mのそれぞれのGPSの区間と道路を関連付ける。
5(a)の例を見るようにGPSはエラーや不正確さによってマップからかなりずれる可能性がある。ひとつの方法としては道に関連付けれるようポッキリと折ってやることができる。
しかし、これは全く間違った結果を与えることがある。矛盾しない関連付けを生成するために、GPSの認識間の空間的な関係を考慮に入れてCRFを生成しなければならない。
CRFの構造はFigure2になる。観測された密なノードgt(ここでtは時間を表す)、そして白いノードは道路の区間Stを表す、これはセクション3での隠れ状態yに相当する。それぞれのStの値はマップでのGPS読み取りGtのある一定の距離内の範囲の距離区間の範囲に及ぶ。
図2での線はCRFの部分完全木構造と定義する。この部分完全木を3つに分けて定義する。
測量クリーク(図2で黒く塗っているもの)
GPSのノイズやマップの不正確さはGPS測量と区間の中央との距離の二乗により測られる特徴を考慮に入れる。
その式は(その下)で、Gtはt番目のGPS測量値である。すこし汚く言うと、われわれはStをGtの付近の道路の区間の中央値として表記する。σは距離の比率を調整させるために必要。
明らかに、負の重みと組み合わせるとき、この特徴はGPS測量地が近くの区間に折れることを好む。??
特徴Fは全ての部分完全木のGPS測量地と道路区間とを結びつける可能性の表記に利用される。
ーーーよーするに、その点が道上にあるという可能性を表す?
矛盾しないクリーク(薄いグレーで塗ってるもの)
現在の正確さは連続するGPS測量値の空間的な関係と、関連付けられた区間の関係という4つのノードのクリークにより図ることが出来る。この関係がより似ていると、より正確な集団である。
この比較は、GPS測量と関連付けられた区間のベクトルを比較する特徴関数により行う。
(その式)
ここでStとSt+1は関連付けた時間の道の区間の中央を表す。
平滑にするクリーク(ちょいグレーで塗ってるもの)
このクリークは、頻繁に違う道に変化しない軌跡を好む。例えば、これは好ましくないことだが何秒かのあいだに違う道を行き来したりする。この情報をモデル化するとき、このレンゾkする区間が同じ道か、近接する道か、同じ方向かということを確かめた二値特徴を利用する。
例えば、もし両方の道のブロックと方向が同じときの二値特徴を調査するときは(25)の式となる。
ここでd(u,v)はもしuとvが一緒なら1、違うなら0の一致関数である。
推理の時、CRFはGPS軌跡と道路区間の繋がりにより分類を推定するためにこれらの特徴を利用している。
上に定義した特徴関数により、条件付き分布は(26)のように書ける
WmとWcとWsはそれぞれ特徴関数の重みと一致する。
読者は重みと特徴関数が時間について独立であると気づくかもしれない、そしてその独立が3.3.3で述べたパラメータシェアを利用することを為せるようになることにも気づくかもしれない。
図5(a)は、GPS軌跡とマップの最大事後確率を表している。直感的に、この連続値は、道路マップを離散化した人の移動軌跡の結果によるMAPの連続値と一致する。
この結合はまた、独特なGPS軌跡の分割を与える。これは同じ道路区間と組み合わせた連続的なGPS取得値と組み合わせることによって行われる。
4.2 行動推定と重要な場所のタイプ
いったんGPS軌跡を分割すると、我々のシステムはそれぞれの分割した部分での行動とその人にとっての重要な場所を推定する。
このようにするために、このシステムはGPS軌跡から抜き取った全ての区間のノードに隠れた行動を含む新しいCRFを生成する。このCRFは図3で示される下の2つのレベルを含める。
それぞれの行動ノードはいくつかの特徴と繋がる。GPS分割した結果を要約した情報であるが。それらの特徴は以下である。
・曜日や週、滞在期間などの現在の情報。この値はより柔軟な関数を揺するために離散値をとる。
たとえば、時間は朝昼夜午前午後など。それぞれの完全部分木のためのそれぞれの行動ノードと???
例えば、もし行動が仕事で日中なら下の関数は1を返し、そうでないなら0を返す。
Fig3
行動と場所をラベル付するためのCRF。行動ノードaiは全ての行動に及び、場所のノードはpiは全ての場所のタイプに及ぶ。それぞれの行動ノードは観測された場所ノードeたちと接続される。場所要素は時間や期間、そして動きの速度といった情報を含む。
場所ノードは行動レベルによって推測された行動に基づいて生成される。それぞれの場所ではその対応づく行動全てが接続されている。
・セグメント間のスピード、これは移動モードを識別するのに重要である。速度の値はまた、現在情報のように離散化され、指示関数が利用できる。この識別は多モードの速度分類を簡単に行うような線形特徴関数という点に有意である。
・地理的なデータベースから抜き出した情報、例えばどの区間がバスのルートなのか、どこがバス停と近いか、それからレストランやスーパーと近いか、など。これもまた情報を組み合わせることにより指示関数を作成する。
・プラスして、それぞれの行動ノードはそれらの近傍と接続する。これらの特徴は、その軌跡で近傍のノード間での行動タイプの一致性を示している。
例えば、これはとてもありえないことだが、ある場所でバスに乗った直後に近くで車を運転したとする。このとき、一致特徴関数はこうなる
このときaiとai+1は連続した行動ノードでの特徴的な行動である。この特徴の重みは教師あり学習後府の値になるだろう。そえrによって、この組み合わせを含むようなラベリングの可能性は低くなる。
我々のモデルはまた人にとって重要な行動を示す場所を決定することも狙っている。家や、仕事場、友達の家、スーパー、レストラン、バス停など。
重要な場所を示すノードは図3で示すCRFの最も高い層で表記される。
しかし、これらの場所は事前にはわかっていない。我々は追加的にこの人の重要な場所を見つける必要がある。
場所を見つけることを我々のシステムに追加するために、我々は繰り返し行動や場所を推定する反復アルゴリズムを利用する。
このアルゴリズムを述べる前に、それらの場所の数や位置がわかっているという状況下のもとで、一般に重要な場所を決定するために利用される特徴を見ましょう。
場所のタイプをすいていするために、CRF内での場所ノードpiと接続している完全部分グラフのための下の特徴を利用する。
・その場所で起こった行動はその場所のタイプを強く示している。例えば、スーパーでは基本的に買い物、友人の家では滞在か何かを載せたりおろしたりしている。
我々の特徴では、その場所で起こった行動の週での頻度を考慮に入れている。これは、それぞれの、その付近の全ての行動ノードを含んだ場所の完全部分グラフを生成することにより行われる。
例えば、図3においてp1,a1とaN-2が完全部分グラフをこのように形成している。このモデルはまたそれぞれの場所で生じた違う行動もカウントしている。我々の実験では、4つのカテゴリに離散化した。0、1、2~3、4~という。
また、場所のタイプと、行動のタイプと、カテゴリの頻度を組み合わせるように、我々は指示関数を持っている。
・その人は一般に限られた数の種類の家や職場しか持たない。ラベル場所を発展するためにこの知識を利用するために、我々はふたつの家や職場の数をカウントする2つの要約完全部分木を追加する。
このカウントは、もっともらしい家や職場の数の結果を生成するようなシステムにするように緩やかな制約を与える。
この特徴は簡単には総数で、総数が増えるとラベリングの可能性が指数的に減る。??
2つのタイプの特徴がCRFをとても大きく生成することになることを記す。これは何故かと言うと、私達は頻度と行動をカウントするためにその場所での全ての行動を部分完全木に構築する必要があり、家と職場の数を数えるために全ての場所ノードを繋げなければならない。
普通の確率伝播法ではこのような部分着は処理しにくい。幸運にも、特徴を要約した木構造のCRFsに変換しることが可能である。この構造では、BP推論は多項式時間で行うことができ、積和のために、これはまた高速フーリエ変換を適用することも可能である。
4.3 場所の検出とラベリングアルゴリズム
CRFではこれまでその人にとっての重要な場所の位置と数は事前に知っているということとして述べてきた。
しかし、それらの場所は知られていないので、推測するような階層的CRFが必要である。
表1は効果的なCRF構築のためのアルゴリズムの要約である。
ステップ3で、この軌跡は行動ノードaiに分割される。それぞれのノードはその場所と関連付けられるGPS情報から抜き出した情報による場所の証eiに特徴付けられる。
上で述べたように、軌跡の分割は近傍のGPS軌跡をクラスタリングでき、図2で示されたCRFを使ったGPS軌跡と離散的なマップを関連付けることも可能である。
行動ノードと、その証拠?(しるし?)は、図3で示されるようなCRFを形成するためにステップ4で使用される。
しかし、この状態では重要な場所はまだ知らないので、CRF0は場所ノードはまだ含んでいない。
最大事後確率推測はまた、MAP行動の、位置の連続とその場所での行動という情報を含んだ連続a0*を決定するための制限されたCRFを作るために利用される。(これがステップ5)
ループのスタートはステップ6で、この行動の連続は重要な場所を抜き出すために利用される。
これは、連続した中の個々の行動が重要な場所に所属するかどうかによりクラス分けされる。例えば、歩くや車を運転するやバスに乗るは重要な場所と関連付けられないし、働くやバスに乗り降りする場所は重要な場所であるとする。
全ての重要な行動による例は場所のノードを生成する。
この場所はこの連続の中の複数の時間で滞在している可能性が高いので、我々は空間的なクラスタリングと、まったく同じ場所を同じ場所のノードに統合する(複数できてることがあるので)。このクラス分けとクラスタリングは、ステップ8のgenerate_places()により行われ、K箇所の場所ノードpjとして返却される。
これらの、場所ー行動ー位置の4層が一般に完全なCRFとして生成される。
ステップ10では、新しいCRFに対してMAP推定を行っている。このCRFは最初のCRFと異なった構造を持っているので、違ったMAP行動の連続を生成するかもしれない。
このプロセスは行動の連続が変わらなくなるまで繰り返し行われる。このテストはステップ11で行う。
最後に、アルゴリズムは場所のセットとMAPのタイプに関してのMAP行動の連続として出力される。
我々の実験では、このアルゴリズムによる変換はとても早く、一般に3回か4回の繰り返しで終わる。
我々の実験はこのアルゴリズムがとても効果的で、頑健であることを示す。我々は現在、MAPの連続よりCRFの????
5 実験結果
我々の実験で、このシステムがどれほど重要な場所と人の行動をラベル付けして抜き出すことができているかを評価する。
その上、このシステムにより複数人から集めたデータから学習したモデルを他の人に適用することが可能であることを示す。
すなわち、我々のシステムはその人のデータの人為的なラベリングを要求することなく行動を認識することができた。
特に、我々はGPSデータを4人の違う人から一人あたりおよそ7日分集めた。それぞれのデータはおよそ40,000のGPS測量値にあたり、10,000のセグメントに分割された。
我々はまた、人為的に全ての行動と重要な場所をそれぞれの軌跡にラベル付けした。
我々は、評価を1個抜き交差検証によって行う。これは、学習は3人から集めたデータにより行い、評価を4番目の人で行う。
maximum pseudo-likelihood(擬似最尤法)を学習に利用する。これは、約1分で学習を収束させる。そして、これは全ての実験データを収束させた。
最尤法を利用しないのは、全て収束するとは限らなかったからである。このもっとも考えられる原因は、ループBPの近似は学習により正確な勾配を与えないということである。
しかし、全ての評価を実行している時に推測のアプローチとしてのループBPを使用することに成功した。
それぞれの評価において、我々は表1におけるアルゴリズム、1分のうちに1週間分の軌跡とMAP行動と抜き出すものであるが、を利用する。
道路地図が利用された時、アルゴリズムのステップ3で行われたGPS軌跡と道路マップの関連付けは4分追加して行われることとなった。
5.1 例の分析
GPS軌跡の分析のステップは図4に示す。
(b)は、GPS軌跡を地図上の10mの区間に変換したもの。????
この関連付けは表1のステップ3に対応し、セクション4.1で述べられているCRFを利用している。
この時間情報や期間情報を持った滞在のパッチは、行動CRFを作成するのに使用されている。これはステップ4で行われる。
CRFの決定におけるMAP推定は、それぞれの滞在のパッチに対して1つの行動を決める。図4の(c)で行われているように(アルゴリズムのステップ5に対応)
この分析ではバスの移動の左端でバスを降りる行動を取り逃していることに気づく。
MAP連続での重要な行動はクラス分けされ場所のノードを追加された新しいCRFを生成する。(ステップ8,9に対応)
このCRFが与えたMAP連続値は、推測された場所にラベルを与える。(図4のdのように)
このアルゴリズムは、MAP行動の連続値がこれ以上変化しなくなるまで繰り返し行われる。すべての実験において、4回以内の繰り返しによって収束された。
図5(a)は質を高く達成できたGPS軌跡を道路地図上にsnapした例である。
どのようにこの軌跡を道路に完璧にsnapさせられたかを気をつける。
表2は行動と訪れた場所のMAP連続値により与えられたその人の典型的な動きの要約である。
このシステムは重要な場所がどこかを決め、その箇所間をどのように動くかを決め、他の場所がその人にとってどのような役割をするかを決めるということであることに気をつける。
5.2 重要な場所の抜き出し
この実験では、我々のシステムの重要な場所を決定する能力と、広く使われているアプローチであるその場所が重要であるかどうかを決定するために時間しきい値を適用する手法を比較する。
我々のデータは3人のデータをもとに学習して、4人目の情報でテストを行った。
しきい値の方法では、我々は1分から10分の違ったしきい値の結果を生成した。51の違った重要な場所を含むこととなった。
図5(b)は、誤検出(重要じゃないのに検出したfalse positive)と偽陰性(重要なのに検出しなかった false negative)のそれぞれのアプローチについての数を表している。
これを見てわかるように、我々の方法はよりしきい値手法より優れている。
5.3 ほかの人から学習したモデルによる場所や行動のラベル付
表3~5は交差検証による結果の要約である。
表3では、重要な行動の結果のみによる行動の推定の結果を表す。誤検出と偽陰性を考慮する。
結果は、検知した場所を考慮に入れたときと入れないときそれぞれのモデルで与えられる。より明確に言うと、場所考慮なしにとは、表1のステップ5で生成されたCRF0を利用した結果で、考慮を入れるとは収束した後のモデルを利用した結果である。
もしこの両方の結果が一緒なら、一回やればいいってことになる。最初の結果で完全なモデルが与えられるからだ。
この表は2つの主要な結果を示している。まず第一に、我々の結果の正確性は極めて高い。とくに、我々のシステムが違う人々のわずか3週間の結果しか利用していないことを考慮すると。
そして、行動と場所を考慮に入れた推測は精度が向上したことが言える。
これらの結果は、道路地図があることを考慮に入れた生成結果である。我々はまた、道路地図を利用しないシステムでの分析を行った。
このケースでは、GPS軌跡はたんに生のGPSデータから10mごとに切り取ったものとする。
我々は、道路地図なしの結果が道路地図ありの時の結果とほぼ完全に一致したことがわかった。
表4ではそれぞれの評価による行動推測の正確さである。この表から見てもわかるように、我々のアプローチは85%以上の正確さを重要な行動を推定において達成した。道路地図ありでもなしでも。
最後に、表5は重要な場所の検出とラベル付である。これを見てわかるように、仕事場と家に関してラベル付に関して1つの間違いも生じなかった。全体の正確さは90.6%となった。この場所検出の結果は道路地図のありなしで一致した。
6 結論
我々は場所をベースにした行動認識を行う新しいアプローチを与えた。
これまでの技術との違いとして、我々のアプローチは、低いレベルの推測と、その人にとっての重要な場所の両方を連続としたフレームワークを利用したことである。
これは、階層的な条件付きランダム場を繰り返し構築することによって行われ、高いレベルは低いレベルのMAP推測により生成した。
いちど完璧なモデルを作れば、我々は完璧なCRFとして推測することができる。
pseudo-likelihoodと推測を利用した弁別的学習は我々のモデルにとても効果的にはたらいた。集めたGPSデータは普通のデスクトップPCでおよそ1分で分析できた。
我々のGPS軌跡による実験は、現存のアプローチよりとても優れていると証明された。それに加えて、その人にとっての重要な場所を学習することが出来るに加えて、低いレベル、歩く、働く、バスに乗るなどの推測も可能である。
実験結果は良好なものとなった。道路マップがあってもなくても。
ここで述べたシステムは、様々な分析の方向に広げられる。例えば、我々のアルゴリズムはMAP推定を利用した階層的なCRFを構築することが可能である。
我々は現在MCMC(マルコフ連鎖モンテカルロ法)かk-best approachを用いた複数のモデルを生成する技術について調査している。
これらの異なったモデルもまた全ての可能性あるデータをもとに評価される。
我々は、これら????
我々は現在、身につけられるマルチセンサーボードによるデータ収集など、さらにいろいろなタイプのセンサーからのデータを我々のモデルに追加することを行っている。
このセンサー機器は、3つの軸の加速度を測って収集できる。音声信号、気圧、光量。
このセンサーからの追加情報を利用することにより、よりきめの細かい行動認識を実現することが可能になると考えられる。