NIPS2018読みメモ: Precision and Recall for Time Series

以下の論文を読みます。解釈誤りは筆者に帰属します。問題点がありましたらご指摘いただけますと幸いです。

Nesime Tatbul, Tae Jun Lee, Stan Zdonik, Mejbah Alam, Justin Gottschlich. Precision and Recall for Time Series. In Proceedings of NIPS 2018. https://papers.nips.cc/paper/7462-precision-and-recall-for-time-series

f:id:cookie-box:20180305232608p:plain:w60

ハヤト、今年もNIPS読みやりますよ。

f:id:cookie-box:20180305231302p:plain:w60

俺たちは去年読んでないだろ! 去年読んでたの別の子たちだよ!

f:id:cookie-box:20180305232608p:plain:w60

この論文のタイトルは「時系列の精度(Precision)と感度(Recall)」ですね。

f:id:cookie-box:20180305231302p:plain:w60

精度と感度? って確か…。

f:id:cookie-box:20180305232608p:plain:w60

どちらもモデルの判定のよさの指標ですね。「スパムメールフォルダに振り分けられたメールのうち、何%が本当にスパムメールだったか」が精度、「届いたスパムメールのうち、何%をちゃんとスパムメールフォルダに振り分けたか」が感度ですね。分子は同じですが分母が違いますね。「スパムメール判定の『精度』がよいか」、「スパムメール検出の『感度』がよいか」と覚えると覚えやすいですよね。

スパム判定器がスパムメール
フォルダに振り分けた
(陽性:Positive)
スパム判定器がスパムメール
フォルダに振り分けなかった
(陰性:Negative)
届いた全てのスパムメール
のうち
正しく振り分けた件数
=True Positive(真陽性:TP)
誤って振り分けなかった件数
=False Negative(偽陰性:FN)
届いた全てのスパムではない
メールのうち
誤って振り分けた件数
=False Positive(偽陽性:FP)
正しく振り分けなかった件数
=True Negative(真陰性:TN)
精度: Precision = TP / (TP + FP) 分母はスパムメールフォルダに振り分けたメールの件数
感度: Recall = TP / (TP + FN) 分母は届いた全てのスパムメールの件数

f:id:cookie-box:20180305231302p:plain:w60

いや覚えやすくなってねーよ! 現にプロデューサーちっとも覚える気配なくて毎回定義検索してるよ!

f:id:cookie-box:20180305232608p:plain:w60

アブストラクトによると、伝統的な異常検知では「点」ベースで、つまり、時系列であればある一時点の値がそれ単体で異常かどうかを検知しますが、通常現実世界での異常はある程度の期間にわたって起きる(range-based)。このことを考慮して、時系列の分類モデルを評価する手法を考案した、という話のようですね。アブストラクトからはこれ以上詳しい内容はわかりませんね…。

f:id:cookie-box:20180305231302p:plain:w60

ふーん…あれでも、そういうある程度の期間にわたって起きる時系列の異常に対する検知手法って普通になかったっけ?

f:id:cookie-box:20180305232608p:plain:w60

その辺は伝統的な異常検知という扱いではないんだと思います。というか検知手法があるかではなくて評価手法があるかって話なんで。

f:id:cookie-box:20180305231302p:plain:w60

そっか。

f:id:cookie-box:20180305232608p:plain:w60

ちょっと情報不足なので先に結論も読んでしまいますね。この論文ではある期間にわたる「モデルの予測値」と「実際に観測された値」の距離のようなものを表す量を定義したみたいですね。予測値と実績値の重なりとか、相対位置とか。そして、バイアス関数なるものでさまざまな基準の重み付けをカスタマイズできるみたいです。さまざまなデータ及び異常検知モデルに対して、他の2つの評価モデルと提案評価モデルを比較したところ、提案評価モデルの方が expressive で flexible で extensible だったと…これらの意味するところは後で要確認ですね。提案評価モデルは適用ドメインによってカスタマイズすべきであるものの、extensible なので論文内で示したセッティングでもじゅうぶん機能するだろうとあります。

f:id:cookie-box:20180305231302p:plain:w60

評価手法の評価って意味わかんなくなってくるな…それに、色んなデータに適用できますって本当なのかな。時系列データって色々あると思うし。

f:id:cookie-box:20180305232608p:plain:w60

とにかく最初からみていきましょう。イントロダクションに戻ると、この論文ではある程度の期間にわたって発生する異常を range-based anomalies とよぶようですが、range-based anomalies とは contextual な異常と collective な異常の部分集合だとありますね。特にその期間中に単体として異常な点が1つもなくても期間データとして異常を含む場合を range-based anomalies というそうです。

f:id:cookie-box:20180305231302p:plain:w60

contextual と collective?

f:id:cookie-box:20180305232608p:plain:w60

それぞれ参考文献である以下のドキュメントの 15:7 ページと 15:8 ページに記述があるようですね。
https://www.vs.inf.ethz.ch/edu/HS2011/CPS/papers/chandola09_anomaly-detection-survey.pdf

  • Contextual Anomalies というのはある「文脈」では異常だが他の「文脈」では異常ではない、という異常のことみたいです。だからこの異常を検知するには「文脈」も明らかになっていないといけません。…という説明だと抽象的で意味がわからないので具体例をあげると、東京である日の気温が10℃だったとします。それが1月だったら取り立てて珍しいことでもないですよね。でも8月だったら異常な事態だと思います。その点がグラフの中で自然な場所に位置するか、不自然な場所に位置するかといった感じですかね。
  • Collective Anomalies というのは1点1点は異常ではないが、まとまっていることで異常、といった感じですね。15:9 ページにグラフで載っている例は心電図で、一定の周期ごとに大きい値をとって小さい値をとるようなパルスがみられますが、1箇所だけそのパルスの間隔が大きくあいていますよね。その箇所のデータは1点1点が異常値というわけではないですが、その値がずっと続いていることが異常といえます。
これらのような異常を検知する場合、「点」ベースの異常の場合と異なり、単純な精度や感度によってモデルの性能を評価できません。にもかかわらず無理に適用することで誤った評価がなされるという弊害があったり、近年のリアルタイムデータの増加でこれらのような range-based な異常の検知手法の必要性も高まったりしているので評価指標の確立が求められている、といった内容が第一段落目までですかね。

f:id:cookie-box:20180305231302p:plain:w60

contextual な異常と collective な異常って、その気温と心電図の具体例はわかるけど一般的にはよくわかんないな…まあいっか。確かにそういう異常を検知するモデルをつくったときにどう評価するべきかってのは明らかじゃないかも。

f:id:cookie-box:20180305232608p:plain:w60

イントロダクションの続きを読むと、提案評価モデルは伝統的な評価指標も包含するみたいですね。かつ、特殊化関数なるもので評価軸ごとの重みをコントロールすることによってデータドメイン毎へのカスタマイズも可能だと。この論文のスコープ外になるが提案評価モデルは機械学習モデルの目的関数にもつかえるのでその方面での活用も期待できるとありますね。

f:id:cookie-box:20180305231302p:plain:w60

そっか、評価指標だったら学習の目的関数になるよな。回帰モデルの2乗誤差とかよく目的関数かつ評価指標になってるし。

f:id:cookie-box:20180305232608p:plain:w60

そこまでがイントロダクションで、次の第2節は背景と目的といった感じですかね。図1(b) に帯のような絵がありますが、これは帯の部分が検知すべき異常ということなんでしょうね。モデルの予測によると赤い帯が異常で、実際の異常は水色の帯だったということと思います。このときモデルの予測のよさをどう評価すればいいか、という話ですね。

f:id:cookie-box:20180305231302p:plain:w60

えっと、モデルの予測は実際の異常を少しは当ててるっちゃ当ててるけど、モデルが予測した異常と実際の異常が部分的に重なっていたり、モデルが予測した異常が実際の2つの異常にまたがっていたり…よくわかんない!

f:id:cookie-box:20180305232608p:plain:w60

ええ、本文にも「部分的な重なりがだいたい悪い」とありますね。モデルが予測した異常期間のうち一部が実際の異常期間に重なっていたら、モデルの予測は部分的には True Positive で部分的には False Positive みたいなことになるわけですが、この場合は TP と FP の比率を定量化できれば評価できそうです。しかし、例えば時間の長さの比などにしてしまえばよいかというとそうでもありません。実際の異常のどの箇所を当てたかなども判断基準になりうるので。一般的な実用場面では、異常の始点側を予測できた方がうれしいはずです。異常が終わりかけになって初めて予測できたのではあまりうれしくありません。そもそも、図1(b) の右側のようにモデルの予測した異常と実際の異常が1対1対応しない場合は、比率をどう定義すべきかよくわかりません。だから、異常の重なりをとらえるとき何か「濃度(cardinality)」をとらえたいと。ここでいう「濃度」は数学用語の「集合の元の個数」の拡張のような意味の濃度であって、日常語の濃度ではないので注意してください…まあ、実際の異常期間とモデルの異常期間が1対1対応であったらそうでない対応のときより評価すべき、という程度の意味でしょうが…。

f:id:cookie-box:20180305231302p:plain:w60

あー、例えば地震を予測するモデルだったら、その予測が揺れている期間の始まり側と重なっている場合と終わり側と重なっている場合の価値が違うな。揺れ始めてからアラートを出されても全然うれしくないし。でもそういわれると一般的にどんな時系列データでも「始まりの方が肝心」ってあてはまりそうな気がする…。

f:id:cookie-box:20180305232608p:plain:w60

続きには今回の評価指標の設計のゴールがありますね。あ、ここで Expressive, Flexible, Extensible の説明がありますね。

  • Expressive: range-based な異常特有の性質(部分的な重なり、異常の濃度)をとらえる。
  • Flexible: ドメインに応じて重み付けを調整できる。
  • Extensible: さらに必要に応じてドメイン特有の基準を追加できる。
これらを達成する評価モデルにしたいということです。

f:id:cookie-box:20180305231302p:plain:w60

ふーん…なんかゴールとしてその3点で足りてるのかとかよくわかんないな。

f:id:cookie-box:20180305232608p:plain:w60

まあこの3点が満たされている方がそうでないよりいいのでは。続く第3節は先行研究ですね。まず時系列データの分類や異常検知は重要という話があります。スペースシャトルに Web サービス、医療データやサイバー攻撃まで、異常検知が求められるドメインはたくさんあり、それぞれに手法が提案されてきましたが、評価モデルの確立は後手に回っていたと。といっても、センサーによる行動認識とか、変化点検知とか、評価モデルが提案されている領域もあるにはあるようです。特に Ward2011 らの手法はきめ細かいらしいですが、それらの既存評価モデルはチューニングができないと。Lavin2015 らも時系列データに対する確たる評価指標の不存在を指摘していたらしいですが、彼らの NAB(Numenta Anomaly Benchmark)評価モデルは本論文の提案手法より柔軟性に欠けるらしいです。このモデルは実験パートで提案手法の比較対象になっていますね。7ページ以降の図表で Numenta と表記されているのがそうですね。

f:id:cookie-box:20180305231302p:plain:w60

…なんかさ、この手の論文の先行研究パートって先行研究の粗探しみたいじゃない?

f:id:cookie-box:20180305232608p:plain:w60

論文なんだから先行研究に対して新規性や有効性がないと仕方ないでしょう…第4節は期間にわたるデータに対する感度と精度ですね。というか感度と精度という組合せは踏襲するんですね。先に感度からで…実際の異常期間の集合を  R = \{R_1, \cdots, R_{N_r}\} とし、モデルが予測した異常期間の集合を  P = \{P_1, \cdots, P_{N_p}\} として、全期間を通した平均感度を

 \displaystyle {\rm Recall}_T(R, P) = \frac{\sum_{i=1}^{N_r} {\rm Recall}_T (R_i, P)}{N_r}
と定義します。{\rm Recall}_T (R_i, P) は1つの異常期間 R_i を検知したかどうかで、これが肝心です。{\rm Recall}_T (R_i, P) は以下のようなものであってほしいです。
  • R_i が1点のみからなる異常であっても検知したかどうかを評価してほしい(存在)。
  • R_i のうち多くの割合の点を検知するほど高い感度になってほしい(サイズ)。
  • R_i のうちどの位置を検知したかも考慮するものであってほしい(位置)。
  • R_i を1つの予測異常期間 P_j で検知するのと、2つ以上の予測異常期間で検知するのとでは、前者の方をより評価してほしい(濃度)。

f:id:cookie-box:20180305231302p:plain:w60

注文多いな!

f:id:cookie-box:20180305232608p:plain:w60

そこで、{\rm Recall}_T (R_i, P) を、「存在」を評価する {\rm ExistenceReward} と「サイズ、位置、濃度」を評価する {\rm OverlapReward} の重み付き和とすることにします。

 {\rm Recall}_T(R_i, P) = \alpha \times {\rm ExistenceReward}(R_i, P) + (1 - \alpha) \times {\rm OverlapReward}(R_i, P)
前者の {\rm ExistenceReward}R_i のうち1点でも検知したかどうかです。0 or 1 です。面倒なので式は省略します。{\rm OverlapReward} はさらに以下の要素からなります。
 \displaystyle {\rm OverlapReward}(R_i, P) = {\rm CardinalityFactor}(R_i, P) \times \sum_{j=1}^{N_p} \omega (R_i, \, R_i \cap P_j , \, \delta)
{\rm CardinalityFactor}(R_i, P)  = \begin{cases} 1 & ({\rm if } \, R_i  \, {\rm overlaps \, with \,  at  \, most  \, one} \, P_j \in P) \\ \gamma(R_i, P) & ({\rm otherwise}) \end{cases}
\gamma (\cdot)0 \leqq \gamma (\cdot) \leqq 1 となる関数で濃度要素を、\omega (\cdot)0 \leqq \omega (\cdot) \leqq 1 となる関数でサイズ要素を定義します。\delta (\cdot)1 \leqq \delta(\cdot) となる関数で、位置要素を定義します。関数 \gamma (\cdot), \, \omega (\cdot), \, \delta(\cdot) の具体形は…あ、関数自体がカスタマイズ対象なんですね。

f:id:cookie-box:20180305231302p:plain:w60

そこは自分で考えないといけないのか。

f:id:cookie-box:20180305232608p:plain:w60

でも実際ドメインによって何を重視して評価するかの差も出そうなところですしね。それに、4ページの図2にちゃんと \omega (\cdot), \, \delta(\cdot) の実装例がありますよ。 \omega (\cdot)R_i のうち多くの割合の点を検知するほど高い感度になるように定義すればいいですが、実装例ではシンプルに重み付き検知率ですね。R_i の全ての点を検知したら 1 だし、1つも検知しなかったら 0 だし(その場合そもそも {\rm ExistenceReward} がゼロですけど)、その中間だったら検知した点の重みによります。その重みを決めるのが \delta(\cdot) というだけです。位置により重みに差を付けない例と、前方/後方/中央の重みを大きくする例が紹介されていますね。 \gamma (\cdot) の例はないですけど、これは「1対1対応じゃなかったときにどれだけペナルティするか」なんで、ペナルティする必要がなかったら 1 でいいし、ペナルティする必要があったら「対応する予測異常期間が2つ以上だったら 0.5 にする」とか「予測異常期間の数の逆数にする」とか適当に決めればいいんじゃないですか。

f:id:cookie-box:20180305231302p:plain:w60

実装例が Figure 2 なのが地味に気になるんだけど…コードって図なの…?

f:id:cookie-box:20180305232608p:plain:w60

読めれば何でもいいでしょう…でもこういう疑似コードは普通 Algorithm 1 とかなっていることが多いんですかね。ちなみに、精度についても全期間を通した平均精度はほぼ同様ですね。(R_i, P) だったところを (P_i, R) にする必要がありますが。感度は「それぞれの実際の異常が検知されたか」なので R_i についての和ですが、精度は「それぞれの予測が正しかったか」ですから P_i についての和になりますね。そして、{\rm ExistenceReward} に相当するものはないですね。感度の場合は、それぞれの実際の異常期間が「そもそも検知されたか」「どれくらい理想的に検知されたか」の二段構えでしたが、精度の場合は、それぞれの実際の予測期間が「どれくらい理想的に実際の異常を予測したか」しかないです。「そもそも予測が何かしらの実際の異常にぶつかったか」という要素は考えないんですね。感度の場合は、異常が検知されただけで一定の価値を与えていましたが、予測の場合は、予測を異常にぶつけただけで一定の価値を与えるということはせず、ぶつけ方をみるということなんですね。この非対称性は何となくわかりますけど、すっきり説明しづらいですね。

(実験パートの追記があれば)つづく