最近『異常検知と変化検知』を読んでたら思わぬところで半正定値計画問題が出てきたので、その話をしてみたい。
これは数理最適化 Advent Calendar 2023の3日目の記事です。
※はてなブログの数式表示がちょっとおかしいかも。。。
線形計画問題と半正定値計画問題
数理最適化でお馴染みの問題といえば、線形計画問題：
これを拡張したものとして半正定値計画問題がある：
ただし、をn次実対称行列の集合として、
であり、
は行列
が半正定値行列であること、すなわち
であることを意味する。
また、
は行列
の内積で、
である。
半正定値計画問題（通称SDP, SemiDefinite Programming）は線形計画問題だけでなく2次錐計画問題などを包含するので重要と言われている。 また、最大カット問題に対する（近似率の保証がある）近似アルゴリズムは、問題をSDPに緩和することで得られてたりと、近似アルゴリズムで重要な役割を果たしていることも知られている。
一方で、この「が半正定値である」という制約がどんなときに使えるのかが、自分にはいまいちよく分かってなかったり。
いやまぁ勉強不足なだけではあるんだけど（＾＾；
そんなわけでSDPに定式化できる例を知って自分でも使えるようになりたいと思ってたんだけど、それが『異常検知と変化検知』を読んでたら出てきたので、ちょっと驚いた。
k-近傍法と計量学習
さて、異常検知をやりたいとして、正常データと異常データがどちらも得られているのだとしたら、一番シンプルに考えられるのは、異常かどうか判断したいデータの周りに正常データと異常データのどちらが多いかをみることが考えられる。 このアイディアを整理したのがk-近傍法。
このk-近傍法ではデータ間の距離が重要になるわけだけど、普通のユークリッド距離がいいとは限らない。 たとえば正常なデータが潰れた楕円みたいな分布になっていたとしたら、長い方向よりも短い方向の軸の方が距離の重みが大きくなっていた方がよさそうと考えられる。
そこで適当な半正定値行列を使ってデータ
間の距離の2乗
を次のように定義してみる：
ここでを半正定値行列と制限しているのは、距離の2乗なので
となってほしいから。
そして、
として単位行列
を持ってくれば普通のユークリッド距離となるので、これは通常の距離の拡張となっている。
このをデータを使っていい感じに求めるのが計量学習（metric learning）で、リーマン幾何学だとこの
を計量テンソル（metric tensor）やリーマン計量（Riemannian metric）と呼ぶらしい。
半正定値計画問題へ
じゃあ、このをどうすべきかといえば、同じグループに入るデータ間の距離はできるだけ近く、そして異なるグループに入るデータ間の距離はできるだけ遠くなるようにするといい。
ここではデータのグループをの2つとして、同じグループに入るデータ間の距離の2乗の合計は次のように書ける：
これはできるだけ小さくしたい。
そして、異なるグループに入るデータ間の距離はできるだけ遠くしたいというのは、あるデータについて、同じグループに入るデータ
と違うグループに入るデータ
を選んできたときに、
となっていてほしいといえる。 で、不等号には等号が含まれていてほしいので、一般性を失うことなくこれを
と表現することにして（で空間が伸び縮みするのでマージンは一律1としていい）、問題はこれを違反する度合いなので、違反度合い
を
と定義して、違反度合いの合計は次のように書ける：
この違反度合いの合計もできるだけ小さくしたい。
したがって、この問題は次のような最小化問題に定式化できる：
目的関数が複雑だけど、これは整理すればSDPになってることが分かる。
本ではこの問題を勾配法で解いていくんだけど、SDPに定式化できているなら普通のソルバーを使って解くこともできたりする。 次はそれを試してみたい。
今日はここまで！
