Local Outlier Factor(LOF)とDensity Estimationの関係


## 概要

Local Outlier FactorとDensity Estimationの関係を考えてみました。

- Local Outlier Factorは、確率密度関数の対数の微分の絶対値のようなものであることがわかりました。
- Local Outlier Factorは複数の幅のガウス分布が混在する場合、幅の小さいガウス分布を厳しく判定することがわかりました <- 間違い (後述のパターン3参照)
- 確率密度関数の入力のスケーリングと出力のスケーリングに依存しないLOF的なものを提案しました

## Local Outlier Factorとは？

正解データのみから、正解不正解を識別する教師なし学習です。
LOFと略されます。
詳細は以下を見てください。

https://en.wikipedia.org/wiki/Local_outlier_factor
https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.LocalOutlierFactor.html#sklearn.neighbors.LocalOutlierFactor

## Density Estimationとは？

サンプルから確率分布を推定する教師なし学習です。

詳細は以下を見てください。
https://scikit-learn.org/stable/modules/density.html

## LOFとDensity Estimationの関係

あまり厳密な議論ではないです。
(勾配は本当はベクトルなのにスカラーみたいに扱っています。ちゃんと書いても、結論は変わらないと思いますが。ちゃんと学びたい人は参考にしないでください)

LOFの式は簡単に書くと以下のようになります。
D(x)は確率密度関数です。

```
LOF(x) = D(x + Δx) / D(x)
```

変形すると以下になります。D'(x)は勾配です。

```
LOF(x) = (D(x) + D'(x) * Δｘ) / D(x)
```

半径Δxの球の中に入る点の数はΔx^d * D(x)に比例します。
dは次元です。Δxがk-neighbor distanceだとすると
k ∝ Δx^d * D(x)なので

```
Δx = C / D(x)^(1/d)
```

Cは適当な係数。

これを使ってLOFの式を変形していきます。

```
LOF(x) = (D(x) + D'(x) * Δｘ) / D(x)
  = (D(x) + D'(x) * C * (k * D(x))^(1/d)) / D(x)
  = 1 + D'(x) / D(x) * C / D(x)^(1/d)
  = 1 + D'(x) / D(x) * C (dが十分大きい場合の近似)
  = 1 + C * δ/δx (Log(D(x)))
```

つまり、LOF(x)は確率密度の対数の微分の絶対値に1を足したものです。

任意のDensity Estimationを使ってLOFみたいなアルゴリズムを実現できるということです。

また、微分を使っているので、確率密度が定数倍になっても結果が変わりません。
outlier detectionに使った場合、学習データの偏りに強いと思います。

## dが十分大きい場合の近似について

上記の式変形で使った、dが十分大きい場合の近似についてです。
近似する前と、近似したあとのどちらが妥当なのでしょうか？
式の扱いやすさとシンプルさで、近似後を採用したほうが良い気がします。

近似しないとパターン3になりますが、GMMなどを単純に使うとexpが含まれるので不安定になりそうです。

## ガウス関数の場合

D(x) = exp(-x^2 / (2 * σ^2))
の場合は

LOF(x) = 1 + |x| / σ^2
です。

ガウス分布の高さに依存せずに標準偏差にのみ依存するところがポイントですが、
少し残念なのは、σとxを両方スケーリングすると、LOFの値が変わることです。

複数のσの混合ガウス分布みたいな分布の場合、
LOFのスレッショルドを固定で決めてしまうと、幅の小さいガウス分布のほうが厳しく判定されてしまうということです。

確率密度の対数の微分ではなく、確率密度の対数を使えばこうならないですが、
今度はガウス分布の高さに依存してしまいます。
両方の性質を持つようななにかは作れるのでしょうか？

ぱっと思いついたのは、適当なハイパーパラメータαで

```
F(x) = |δ/δx (Log(D(x)))| + α * Log(D(x)
```

としてしまい、outlier detectionのスコアがもっとも高いαを探索するという方法です。outlier detectionの教師データがある場合のみ使えますが

別の拡張は、分数微分みたいななにかを用意して( https://ja.wikipedia.org/wiki/%E5%88%86%E6%95%B0%E9%9A%8E%E5%BE%AE%E7%A9%8D%E5%88%86%E5%AD%A6 )

```
F(x) = |分数微分(Log(D(x)), dim)|
```

dimをハイパーパラメータとして探索する方法です。

また、ガウス分布ではなく以下の分布だとLOFが定数になるので、outlier判定できなそうです。

```
D(x) = exp(-|x| / σ)
```
->
```
LOF(x) = 1 / σ
```

## 分布の高さと幅に依存しないLOF的なものは作れるか？

以下の性質を持つ関数F(確率密度関数の対数とxを受け取り、LOF的なものを返す)があるか？という問題です。 (対数をとったのでk * Dがk + Dにおきかわっています)

```
A: F(D, x) =  F(D(x / k), k * x) (for all k, x)
B: F(D, x) =  F(k + D, x) (for all , xk)
```

F(D, x) = D(x)の場合はAが成立しますが、Bが成立しません。
F(D, x) = 微分(D(x))の場合はBが成立しますが、Aが成立しません。

F(D, x) = 定数はA, Bをみたしますが意味がありません。

無理やりでっちあげてみました。

```
F(D, x) = （Δ/Δｘ）D(x) / Sqrt(（Δ^2/Δｘ^2）D(x))
```

確認します。

```
A: F(D, x) =  (（Δ/Δｘ）D(x) / k) / Sqrt(（Δ^2/Δｘ^2）D(x) / k^2)
           =  （Δ/Δｘ）D(x) / Sqrt(（Δ^2/Δｘ^2）D(x))
B: F(D, x) =  （Δ/Δｘ）D(x) / Sqrt(（Δ^2/Δｘ^2）D(x))
```

つまり、対数ではなく元のスケールになおすと

```
LOF(x) = |（Δ/Δｘ）Log(D(x))| / Sqrt(|（Δ^2/Δｘ^2）Log(D(x))|)
```

とすれば良さそうです。

ガウス分布の場合は

```
LOF(x) = (|x| / σ^2) / Sqrt(1 / σ^2) = |x| / σ
```

さきほどLOF(x)が使えなかった分布(D(x) = exp(-|x| / σ))の場合は、

```
LOF(x) = (1 / σ) / Sqrt(0) = ∞
```

試しに以下の分布だと？

D(x) = exp(-x^n / (n * σ^n))

LOF(x) = (|x|^(n - 1) / σ^n) / Sqrt((n - 1) * |x|^(n - 2) / σ^n)
  = |x|^(n / 2) / ((n - 1)^0.5 * σ^(n / 2))

確かにσとxの次数が合っているので、xをスケールしても変わらないですね。

もっと簡単な方法を考えました。まず、微分を使えば定数項を消せます。
微分によって出てきてしまうkは、Δxを使えば消せます。

```
F(D, x) = （Δ/Δｘ）D(x) * Δx
```

元のスケールで書くと

```
F(D, x) = （Δ/Δｘ）(Log(D(x)) * Δx
```

LOFの近似前の式になりました。LOFは一周回って妥当だったということでしょうか？
Δx = C / D(x)^(1/d)
Cは次元とkによって決まる定数なので排除してしまうと

```
F(D, x) = （Δ/Δｘ）(Log(D(x)) / D(x)^(1/d)
```

dが十分大きければ近似的に確率密度関数の高さが変化しても影響を受けないし、この式の形ならxをスケーリングしても結果が変わらないので良いのかもしれません。
さらに欲を出して、nにも依存しないLOF的なものは作れるのでしょうか？

↑の議論はけっこう適当だが、結論
originalのLOFは全ての方向に均一にスケーリングする場合に不変だと思う。
不均一だと、ΔxがD(x)^(1/d)で近似できなくなるので変わる。
結果が変わる。直感的にも正しそう。
originalのLOFはスケールの違う球が混在していてもOKだが、楕円が交じるとoutlier detectionの厳しさに不公平が生じるというレベル。

アフィン変換に対して不変な方法は、ヘッセ行列を使って工夫するか、
付近の極小点を探し(mean shiftなどで)、そことの対数確率の差をLOFにする。
この方法なら様々なスケールの楕円と球が混在していても、
自然にoutlier detectionできると思う。
極小点との対数確率の差をLOFにする方法は、その差が変わらなければ不変だから、空間が歪んでいても、少しであれば影響を受けないと思う。
正規化やPCAも不要になる。
mean shiftで実装したらかなり重いかもしれないが、極小点を探すためのインデックスを作っておけば良さそう

一般化座標のアイデアを使えば、任意の座標変換に対して不変なLOF的なものを作れるのでは？
https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%EF%BC%9D%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E6%96%B9%E7%A8%8B%E5%BC%8F

## LOFの評価

教師データがない場合、LOFの評価はどうすれば良いでしょうか？
一つの方法は、
Density Estimationを評価する方法です(エントロピーなどで)。

正確なDensity Estimationを元にしたLOFは、以下の式を使って一意に定まります。それぞれの式ごとに現実のデータに対する有効性は異なってくると思いますが、その部分がある程度うまくいくと仮定すれば、Density Estimationさえちゃんとやれば良いはずです。

```
LOF(x) = Log(D(x)) (パターン1、上記条件Bを満たす)
LOF(x) = |（Δ/Δｘ）(Log(D(x))| (パターン2、上記条件Aを満たす)
LOF(x) = |（Δ/Δｘ）(Log(D(x))| / D(x)^(1/d) (パターン3、上記条件Aを満たし、上記条件Bを近似的に満たす)
LOF(x) = |（Δ/Δｘ）Log(D(x))| / |（Δ/Δｘ）|（Δ/Δｘ）Log(D(x))||^0.5 (パターン4、上記条件A, Bを満たす)
LOF(x) = future work (パターン5、任意の座標変換に対して不変)
```

Density Estimationの正確さと、それを元にしたLOFの正確さは異なります。つまり、Density Estimation的には結構正確だが、LOF的には不正確なケースやその逆がありえます(LOFを計算するには微分も推定しないといけないが、Density Estimationをエントロピーで評価したりすると、微分の正確さを評価できない)。真の確率密度によって得られたLOFと、推定された確率密度によって得られたLOFの近さはどうやって測れば良いのでしょうか？

確率密度の微分の推定は研究されているみたいです。
https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/224764/1/1999-13.pdf
http://proceedings.mlr.press/v54/ashizawa17a/ashizawa17a.pdf
https://github.com/t-sakai-kure/R-LSLDGC
https://en.wikipedia.org/wiki/Mean_shift
http://takashiijiri.com/study/ImgProc/MeanShift.htm
http://www.ms.k.u-tokyo.ac.jp/software.html#LSLDG
https://scikit-learn.org/stable/modules/clustering.html#mean-shift
式変形を参考にすれば、LOFに対して、誤差を評価できそうですね。
また、mean-shiftとLOFって似ていますね。LOFはmean-shiftの勾配が大きいものをoutlierと判定するということだと思います。mean shiftにneighborを使ったものと勾配推定を使ったアルゴリズムがあるように、LOFにも両方ありうると思います。でもまだ勾配推定版は無さそう。
mean-shiftとautoencoderのreconstruction errorを使ったoutlier detectionも似ていると思います。

https://www.researchgate.net/publication/221506334_Outlier_Detection_with_Kernel_Density_Functions
LOFの亜種。勾配推定のアイデアが入っていると思ったが違う

https://arxiv.org/pdf/1702.06354.pdf
勾配ではなくoutlier inlinerのDensity Ratioに注目するのはよくあるらしい

https://d-nb.info/1048522377/34
LOFのreachable distanceや平均のとりかたはいろいろな亜種があるが、それらの違いがまとめられている。

LOFのPercentileから計算したなにかなら座標変換に依存しなそうです。Percentileに対する妥当な量はROCのAUCなどがありそうですが、最初は単純に2乗誤差とかでも。
これも上の式変形を参考にして頑張れば行けるかもしれません。

ポイント

- 確率密度の微分の推定
- LOFの推定
- それぞれ座標に依存しない評価方法はあるのか？

## 微分の推定について

微分の2乗誤差を評価関数にすると、高周波成分が抑制されそうです。
LOFは、reachable distanceや距離の調和平均などでなんとか誤差を減らしていますが、微分の2乗誤差を評価関数にして直接推定すれば、LOFの誤差がかなり改善するかもしれません。サンプル数が少ないときに有効かもしれません。

## 確率密度関数から定義したLOF(LOFD)とその近似精度の評価

### 定義

以下のようにLOFDを定義する。
LOFDの式の形はoriginalのLOFから類推した。

```
x: d次元ベクトル
p(x): 確率密度関数
L(x) = ∇Log(p(x)) / p(x)^(1/d)
LOFD(x) = |L(x)| (LOF from Density)
```

### 問題設定

LOFDを使った、
教師なし学習outlier detectionでのゴールは、
p(x)の有限個のサンプリングを使い、
L(x)をなるべくうまく近似したM(x)を計算することである。

### 近似アルゴリズム

具体的な近似アルゴリズムは、original LOFやmean shift LOFである。
この２つは本格的には分析していないが、軽く分析したところ、たぶんL(x)の近似になっている。

### 近似精度の評価

アルゴリズム間の比較や、データに対する手法の有効性をデータ間で比較するために、近似精度の評価をできると便利である。

例えば、確率密度の近似精度はエントロピーで評価できる。
例えば、対数確率密度勾配の近似精度の評価方法は以下で紹介されている。
確率密度微分の直接推定と機械学習への応用 (Statistical
Inference on Divergence Measures and Its Related Topics)
https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/224764/1/1999-13.pdf

対数確率密度勾配の近似精度評価方法を参考に、
真のL(x)と近似したM(x)の間の誤差を計算してみます。

誤差を以下で定義します。

```
J(M(x)) = ∫|M(x) - L(x)|^2 * p(x) dx
```

上記リンクに習って式変形していきます。

```
J(M(x)) = ∫M(x)^2 * p(x) dx
 - 2 * ∫M(x) * L(x) * p(x) dx
 + ∫L(x)^2 * p(x) dx
```

最初の項はサンプルからかんたんに期待値計算可能です。
最後の項はp(x)だけに依存した項なので、アルゴリズム間の比較目的なら不要です。
問題は真ん中の項です。

リンクに習って部分積分します。

```
∫M_j(x) * L_j(x) * p(x) dx
= ∫M_j(x) * (δ/δx_j)p(x) / p(x)^(1/d) dx
= -∫(δ/δx_j)M_j(x) * p(x)^(1-1/d) / (1-1/d) dx
```

ただし、lim(x->∞) M(x) * p(x)(1-1/d) = 0

うまく行きません。p(x)の指数が1にならないとサンプルの平均の形に変換できません。

TODO

## Future Work

- いろいろなDensity Estimationを使って、上記方法でLOF的なものを構成し、Outlier Detectionの従来手法と性能を比較してみる
- 上記、入力と出力のスケーリングに依存しないLOF的なものを使って、Outlier Detectionの従来手法と性能を比較してみる
- LOFの直接推定モデルを作ってみる (GMMの微分とかで)
- 既存の対数確率密度勾配推定を使って、LOFを作ってみる
- mean-shiftを使って、LOFを作ってみる。
- 任意の座標変換に対して不変なLOF的なものを考えてみる
- LOFの評価方法を考えてみる

## まとめ

間違えていたら教えてください。