はじめに

タイトルの通りカーネル関数の話。内積のことを考えるとカーネル関数から作られるグラム行列は正定値でないとダメな気がしたがそんなことはなくて半正定値であればよい、それは何故か？という話。

いくつかの書籍に書いてある話なのでわざわざ記事にしなくてもよいかもしれないが、自分が抱いた疑問やその解消に至るまでの経緯などを含めて備忘録として残しておく。

なお、カーネル関数については以前書いた以下の記事でも触れているので参考までに。

yamagensakam.hatenablog.com

カーネル関数と再生性

本題に入る前に前提となるカーネル関数の定義や対象とする空間および再生性という性質について簡単に述べておく。

まず集合 $\mathcal{X}$ 上の2変数関数であって、対称性と半正定値性を有する関数 $k$ をカーネル関数と呼ぶ。これは、任意 $x_1 , \cdots, x_n \in \mathcal{X}$ に対し $i$ 行 $j$ 列目が $k(x_i, x_j)$ のグラム行列 $\mathbf{K}$ を作ると、それが半正定値対称行列になることを意味する。

また、カーネル関数 $k$ について、第2引数を $x \in \mathcal{X}$ で固定した1変数関数を $k(\cdot, x) = k_x(\cdot) = k_x$ と表記する。

そして、この1変数関数を用いて内積空間 $\mathcal{V}$ を以下のように定義する。

$\displaystyle \mathcal{V} = \left \{ \sum_{i=1}^{n} a_i k_{x_i} \ \middle| \ x_i \in \mathcal{X}, \ a_i \in \mathbb{R}, \ n \in \mathbb{N} \right\} \tag{1}$

この空間の内積は $f = \sum_{i = 1}^{n} a_i k_{x_i}, \ g = \sum_{j = 1}^{m} b_j k_{y_j} \in \mathcal{V}$ として、

$\displaystyle \langle f, g \rangle = \sum_{i=1}^{n} \sum_{j=1}^{m} a_i b_j k(y_j, x_i) \tag{2}$

と定義する。後述の零関数の例にもある通り $f \in \mathcal{V}$ の表現方法は複数存在する可能性がある（つまり、 $a_i$ や $x_i$ が異なっていても同じ $f$ になることがある）。それでも式（2）で定義する内積はwell-definedであり、 $f, g$ の表し方によらず1つに定まる。

このように定義した内積空間では、任意の $f \in \mathcal{V}, \ x \in \mathcal{X}$ に対し以下のような再生性という性質を有する。

$\displaystyle f(x) = \langle f, k_x \rangle \tag{3}$

これは関数 $f$ に $x$ を代入する操作が内積の形で表せることを意味し、この性質から様々な定理が導かれる。

ちなみに、このままでは完備性を有しておらずヒルベルト空間とは呼べない（と思われる*1）。この $\mathcal{V}$ に対し完備化という操作を施し完備性を有した空間は再生核ヒルベルト空間になるが、今回の内容には絡まないのでこれ以上は触れない。

疑問点

このように定めた内積空間 $\mathcal{V}$ において

$\displaystyle \langle f, f \rangle = \sum_{i = 1}^{n} \sum_{j = 1}^{n} a_i a_j k(x_i, x_j) = \mathbf{a}^T \mathbf{K} \mathbf{a} \tag{4}$

を考える（ $\mathbf{a}$ は $a_i$ を $i$ 番目の要素に持つベクトル）。カーネル関数が半正定値ということはグラム行列 $\mathbf{K}$ が半正定値で $\rm{rank} (\mathbf{K}) \lt n$ にもなり得る。ということは、 $\rm{rank} (\mathbf{K}) \lt n$ であれば $\langle f, f \rangle = 0$ となる $\mathbf{0}$ 以外の $\mathbf{a}$ が存在することになる。

ところが、内積の定義を考えると $\langle f, f \rangle = 0 \Leftrightarrow f = 0$ のはずで、それにもかかわらず $\mathbf{a}$ が $\mathbf{0}$ でなくとも式（4）を $0$ にできるのはなんか奇妙、というのが今回の論点。

疑問の解消

そもそもの話

考えてみれば $f = 0$ とはどういうことだろう？ $f = \sum_{i = 1}^{n} a_i k_{x_i}$ で $a_i = 0\ ( i = 1, \cdots, n)$ というなら分かるが、それ以外に意味することはあるのだろうか？

これはベクトル空間に立ち返ると $f$ は零ベクトルであることを意味する。零ベクトルなので任意の $g \in \mathcal{V}$ に対して、 $f + g = g + f = g$ となればよい。関数なので表現方法が異なっていても入出力関係が変わらなければよい。すなわち、任意の $x\in \mathcal{X}$ に対して $f(x) + g(x) = g(x) + f(x) = g(x)$ であれば $f$ は零ベクトルと言える*2。これを達成する $f$ は何を入力しても $0$ を出力する関数、つまり零関数である。 $f$ が零関数であれば、 $a_i$ が全て $0$ である必要もない。

$\langle f, f \rangle = 0 \Leftrightarrow f = 0$ の証明

$f=0 \Rightarrow \langle f, f \rangle = 0$ は自明なので $\langle f, f \rangle = 0 \Rightarrow f = 0$ のみ示す。まず、 $f, g \in \mathcal{V}$ について以下のコーシー・シュワルツの不等式が成り立つことを示す。

$\displaystyle | \langle f, g \rangle |^2 \leq \langle f, f \rangle \langle g, g \rangle \tag{5}$

これは $\langle tf + g, tf + g \rangle \ \ (t \in \mathbb{R})$ を考えると、

$\displaystyle \begin{align} \langle tf + g, tf + g \rangle = t^2 \langle f, f \rangle + 2t \langle f, g \rangle + \langle g, g \rangle \geq 0 \end{align}$

であり、これが任意の実数 $t$ に対して成立するためには判別式が $0$ 以下、すなわち $4\langle f, g \rangle^2 - 4 \langle f, f \rangle \langle g, g \rangle \leq 0$ となる必要があるため、これを展開して式（5）が導かれる。

また、任意の $x \in \mathcal{X}$ に対し $|f(x)|^2 = 0$ であれば $f = 0$ である。 $|f(x)|^2$ を式（3）の再生性と式（5）を用いて展開すると、

$\displaystyle | f(x) |^2 = | \langle f, k_x \rangle |^2 \leq \langle f, f \rangle \langle k_x , k_x \rangle \tag{6}$

となる。そして、 $\langle f, f\rangle = 0$ なので $0 \leq |f(x)|^2 \leq 0$ となり $f = 0$ が導かれる。

具体例で検証

このことと式（4）より $\mathbf{a}^T \mathbf{K} \mathbf{a} = 0$ となる $a_i, \ x_i \ \ (i =1, \cdots, n)$ の組み合わせでは $f = \sum_{i = 1}^{n} a_i k_{x_i}$ は零関数であり、任意の $y \in \mathcal{X}$ について $f(y) = \sum_{i = 1}^{n} a_i k(y, x_i) = 0$ となる。

これをカーネル関数として2次の多項式カーネル $k(\mathbf{y}, \mathbf{x}) = (1 + \mathbf{x}^T \mathbf{y})^2 \ \ (\mathbf{x}, \mathbf{y} \in \mathbb{R}^d)$ を採用した場合を例にとって考えてみると、 $\mathbf{a}^T \mathbf{K} \mathbf{a} = 0$ であれば任意の $\mathbf{y}$ に対して $f(\mathbf{y}) = \sum_{i = 1}^{n} a_i (1 +\mathbf{x}_i^T \mathbf{y})^2 = 0$ が成り立つ。

ここまで見てもまだ直感と反する気がするので、一応このことをスクリプトを書いて確かめてみる。多項式カーネルなので $d \ll n$ なら $\rm{rank} (\mathbf{K}) \lt n$ となる。そして、 $\mathbf{K}$ の零固有値に対応する固有ベクトルを $\mathbf{a}$ とすれば $\mathbf{a}^T \mathbf{K} \mathbf{a} = 0$ となる。この $\mathbf{a}$ を用いて作った $f$ は果たして適当な $\mathbf{y}$ に対して $f(\mathbf{y}) = 0$ となるのか、ということを確かめるスクリプトが以下。

import numpy as np

def func(a, X, y, k):
    res = 0
    for i in range(a.shape[0]):
        res += a[i] * k(y, X[i, :])
    return res

if __name__ == '__main__':
    np.random.seed(3407)
    d = 6
    n = 30
    X = np.random.randn(n, d)

    # 2次多項式カーネル
    k = lambda x, y: (1 + x @ y) ** 2

    K = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            K[i, j] = k(X[i, :], X[j, :])

    print ("rank(K) =", np.linalg.matrix_rank(K))

    # Kの零固有値に対応する固有ベクトルを抽出
    # このベクトルaはa @ K @ a = 0を満たす
    l, U = np.linalg.eigh(K)
    a = U[:, np.abs(l) < 1e-12]

    # 入力を適当に生成
    y = -50 + 100 * np.random.rand(d)

    for i in range(a.shape[1]):
        f = lambda y : func(a[:, i], X, y, k)
        print("f" + str(i) + "(x) =", f(y))

結果としては、

rank(K) = 28
f0(x) = -1.4438228390645236e-11
f1(x) = -1.4743761767022079e-12

演算誤差もあるので完全に $0$ とはならないが、ほぼ $0$ になったといえる。また乱数のseedを変えて何度か試しても同じくらいの値になるので、とりあえず納得。

おわりに

最後に参考文献。冒頭に述べた以前書いた記事でも同様の参考文献を挙げたが今回もお世話なったので改めて記載。

機械学習のための関数解析入門: ヒルベルト空間とカーネル法

作者:瀬戸道生,伊吹竜也,畑中健志
内田老鶴圃

Amazon

*1:これは自分の中でまだ理解が怪しい。式（1）の定義だと有限個の和なので完備になったりしないか？ $n \rightarrow \infty$ として解析するときに完備性の議論が必要なる？

*2:関数同士の和は $(f + g)(x) = f(x) + g(x)$ としていいのかという話もある。おそらく一般的にも関数の和はこのように定義するのだと思うが、少なくとも今回の場合は、再生性より $(f + g)(x) = \langle f + g, k_x \rangle = \langle f, k_x \rangle + \langle g, k_x \rangle = f(x) + g(x)$ として得られる。