KCS とは
KCS(Kernel with Compact Support)とはコンパクトな台を持つカーネル関数のことである。関数の台とは、集合X上の関数の値が0になっていない部分の閉包のことで
\operatorname{supp}(f) := \overline{\{ x \in X \mid f(x) \neq 0 \}}
により定義される。コンパクトな台を持つ関数とは\operatorname{supp}(f)がコンパクト性を満たすもの、要するに関数が0にならない部分がひとつの有界閉区間[a, b]で覆えるものである。要するにこんな形をしている関数である。
コンパクトな台を持つ関数の例 (from Wikipedia)
コンパクトなサポートを持つ関数f(x)があるとなぜ嬉しいかというと、関数f(x)は閉区間[a, b]の外では値が0になるので
\int _ {- \infty} ^ {+ \infty} f(x) dx = \int _ {a} ^ {b} f(x) dx
より、f(x)の関わる積分がほとんど有界閉区間[a, b]の積分に置き換えられるからである。
今回の実験に用いた Google Colab の notebook はこちら。
https://colab.research.google.com/drive/16VurMnNQmJyCXgus3jmNqiRygg35srBc?usp=sharing
参考文献
KCS について調べたモチベ
ガウス関数の裾野が無限大というのが気に入らない状況がある。たとえばカーネル回帰においては、正定値カーネルk \colon \mathcal{X} \times \mathcal{X} \to \mathbb{R}と、データセット
\mathcal{D} := \bigl\{ (x ^ {(1)}, y ^ {(1)}), (x ^ {(2)}, y ^ {(2)}), \ldots, (x ^ {(N)}, y ^ {(N)}) \bigr\} \subset \mathcal{X} \times \mathbb{R}
が与えられた上で、未知の入力x ^ \astに対する出力y ^ \astの予測値\hat{y}を
\hat{y} = \sum _ {i = 1} ^ N \alpha _ i k(x ^ {(i)}, x ^ \ast) \tag{1}
と回帰する。ここでカーネル関数がガウスカーネル
k(x, y) = \exp( - \beta \| x - y \| ^ 2)
だったりすると、k(x, y)はxとyがどれだけ離れていても正の値を持つから、(1)式を計算するときにはデータセットに存在するすべてのデータx ^ {(i)}についての総和を取らなければならず、観測したデータが増えれば増えるほど計算量が大きくなる。
だがよく考えてみるとカーネル関数の値はデータどうしの距離\| x ^ {(i)} - x ^ \ast \|に対して指数的に減衰する、たとえば\beta = 1, \| x ^ {(i)} - x ^ \ast \| ^ 2 = 10という条件で既に
\exp(-10) \fallingdotseq 4.534 \times 10 ^ {-5}
となっていて、このようなデータx ^ {(i)}はデータセット中に存在していても、x ^ \astに対応する予測値を算出する際にはほとんど寄与していないと考えられる。これがいっそ 0 になっていたらそもそも足す必要すらないのにって思わないだろうか？
ガウスカーネルが無限の裾野を持つせいでデータセット中のすべての入力を考慮しないといけない。ある範囲から外れたら寄与がはっきりと 0 になる、つまりコンパクトな台を持つカーネル関数を使えば、自分と近い距離にあるデータだけを参照して学習したり予測したりする効率的なモデルを組めるのではないか？
と思ったんだけど、それは要するにk-近傍法だしあんまり面白いこと思いつかなかったので、今回作ったコンパクトサポートなカーネル関数だけ公開します。みなさんの何かに役立てば幸いです。
今回作成した KCS
今回作成した KCS は『KCS — New Kernel Family with Compact Support in Scale Space: Formulation and Impact』で提案されたカーネル関数をほぼそのまま使っていて、以下の式で定義されます。
k(x, y) := \begin{cases}
\exp \Bigl( \frac{\gamma ^ 2}{\beta \| x - y \| ^ 2 - \gamma} + \gamma \Bigr) & \text{if} \quad \beta \| x - y \| ^ 2 < \gamma \\
0 & \text{otherwise}
\end{cases}
入力x, yがともにベクトルであると仮定したときの Python 実装は以下です。
def kcs(x, y, beta=1, gamma=1):
zs = np.empty(np.shape(x))
r = beta * (x - y) ** 2
zs[r >= gamma] = 0
zs[r < gamma] = np.exp(gamma ** 2 / (r[r < gamma] - gamma) + gamma)
return zs
ガウスカーネル（緑）と KCS（青）を\beta = 1で比較プロットしたのが以下です。青太線は\gamma = 1の KCS で、青細線は\gamma = 2, 5, 10, 20と徐々に大きくしたものです。KCS は\gammaを大きくしていくとガウスカーネルに漸近することがわかります。\betaはスケーリングパラメータで、KCS は\gammaを大きくしていくと\betaが等しいガウスカーネルに漸近します。
実験に用いた Google Colab の notebook はこちら。
https://colab.research.google.com/drive/16VurMnNQmJyCXgus3jmNqiRygg35srBc?usp=sharing
面白い使い方を思いついた人がいたら教えてください。では今回はこれにて。
Discussion