今更聞けないリプレゼンター定理の解説

定義

リプレゼンター定理(Representer theorem)とは、

「損失関数が$\boldsymbol{\omega}^{ \mathrm{ T } }\boldsymbol{\phi}(\boldsymbol{x}_i)$（パラメータ$\boldsymbol{\omega}$と特徴ベクトルの積）の関数として表現できるとする。この損失関数に正則化項を加えて最適化する問題において、その正則化項が$\lambda\boldsymbol{\omega}^{ \mathrm{ T } }\boldsymbol{\omega}$という形をしていれば、その最適解$\hat{\boldsymbol{\omega}}$は$\boldsymbol{\phi}(\boldsymbol{x}_i)$で張られる空間に存在する」

というものである。

この定義だけでは理解し難いので、具体例を記しておく。

例えば、以下の(1)のような二乗誤差関数の最小化問題を考えた場合に、重みの最適解$\hat{\boldsymbol{\omega}}$は(2)の形で表せることを意味する。
$$\begin{eqnarray} \hat{\boldsymbol{\omega}} &=& arg\min_\boldsymbol{\omega}\displaystyle \sum_{i} (y_i - \boldsymbol{\omega}^{ \mathrm{ T } }\boldsymbol{\phi}(\boldsymbol{x}_i))^2+\lambda\boldsymbol{\omega}^{ \mathrm{ T } }\boldsymbol{\omega}\\ \hat{\boldsymbol{\omega}} &=& \sum_{i}\alpha_i\boldsymbol{\phi}(\boldsymbol{x}_i) \end{eqnarray}$$

証明

では、なぜ重みの最適解は(2)の形で表現できるのであろうか。
最適解が$\boldsymbol{\phi}(\boldsymbol{x}_i)$で張られる空間に存在しない場合、つまり重み$\boldsymbol{\omega}$が、以下の(3)(4)の形で表現できた場合を考える。
$$\begin{eqnarray} \boldsymbol{\omega} &=& \boldsymbol{\omega_0}+\boldsymbol{\xi}\\ \boldsymbol{\omega_0} &=& \sum_{i}\alpha_i\boldsymbol{\phi}(\boldsymbol{x}_i) \end{eqnarray}$$
ただし、$\boldsymbol{\xi}$はすべての$\boldsymbol{\phi}(\boldsymbol{x}_i)$に直交する。

この時、最適化問題は以下の(5)式のようになる。
損失関数の部分については、$\boldsymbol{\xi}$が$\boldsymbol{\phi}(\boldsymbol{x}_i)$に直交するため、影響を与えない。対して、正則化項の部分は$\|\boldsymbol{\xi}\|^2 \geq 0$が残る。よって、(5)式は(6)式と同値である。
$$\small{ \begin{eqnarray} \displaystyle \sum_{i} (y_i -  (\boldsymbol{\omega_0}+\boldsymbol{\xi})^{ \mathrm{ T } }\boldsymbol{\phi}(\boldsymbol{x}_i))^2+\lambda(\boldsymbol{\omega_0}+\boldsymbol{\xi})^{ \mathrm{ T } }(\boldsymbol{\omega_0}+\boldsymbol{\xi})\\ \Leftrightarrow\displaystyle \sum_{i} (y_i -  \boldsymbol{\omega_0}^{ \mathrm{ T } }\boldsymbol{\phi}(\boldsymbol{x}_i))^2+\lambda(\|\boldsymbol{\omega_0}\|^2+\|\boldsymbol{\xi}\|^2) \end{eqnarray} }$$
さて、最小化を考えた場合、正則化項の$\|\boldsymbol{\xi}\|^2$の増加分を最小にするためには、$\boldsymbol{\xi}$が$\boldsymbol{0}$となる。よって、重みの最適解$\hat{\boldsymbol{\omega}}$は以下の式(7),式(8)で表され、式(2)で表せることが証明できた。

$$\begin{eqnarray} \hat{\boldsymbol{\omega}} &=& \boldsymbol{\omega_0}\\ &=& \sum_{i}\alpha_i\boldsymbol{\phi}(\boldsymbol{x}_i) \end{eqnarray}$$

何が嬉しいか

最適解が式(2)で表現できて何が嬉しいのだろうか。
$\boldsymbol{\alpha}$の次元はサンプリングされたデータ数$N$と一致する。
また、$\boldsymbol{\omega}$は特徴ベクトルの次元数$d$と一致する。

非線形な分類を可能にするため、データ$x_i$は多くの場合、高次元の特徴ベクトル空間$\boldsymbol{\phi}(\boldsymbol{x}_i)$に写像される（無限次元の特徴ベクトル空間への写像の場合もある）。

最適化を考えた場合、変数は小さい方が簡単である。
$\boldsymbol{\omega}$を直接最適化することももちろん理論的には可能であるが、超高次元な特徴ベクトル空間の場合には、そのパラメータの最適化は現実的ではない。そこで、リプレゼンター定理を用いて、データ数の数だけの変数を持つパラメータ$\boldsymbol{\alpha}$を最適化することで、計算量を削減すること（現実的に解くこと）が可能となる。

使い方

以上のことを踏まえて、ケースに最適化するパラメータを変化させると良いだろう。

$d \gg N$の場合：サンプリングデータの線形結合係数 $\alpha$（次元数$d$）（リプレゼンター定理の利用）
$d \ll N$の場合：元々の重み係数$\omega$（次元数$N$）

以上