PRML演習問題 6.12(標準) www - 機械学習基礎理論独習

問題

あらかじめ固定された集合 $D$ のすべての部分集合 $A$ の空間を考え、カーネル関数 $(6.27)$ は、
写像 ${\boldsymbol\phi}(A)$ によって定義される $2^{|D|}$ 次元の特徴空間における内積であることを示せ。
なお、 $A$ は $D$ の部分集合であり、部分集合 $U$ で指定される ${\boldsymbol\phi}(A)$ の各要素 $\phi_U(A)$ は、以下で与えられるとする。

$\begin{eqnarray} \phi_U(A)= \left\{ \begin{array}{l} 1,\ U \subseteq A \ のとき\\ 0,\ それ以外. \end{array}\tag{6.95} \right. \end{eqnarray}$

ここで、 $U\subseteq A$ は、 $U$ は $A$ の部分集合ではあるか、 $A$ そのものであることを表すとする。

参照

$\begin{eqnarray} k(A_1,A_2)=2^{|A_1\cap A_2|}\tag{6.27} \end{eqnarray}$

解答

$2^{|A_1\cap A_2|}$ は $A_1$ と $A_2$ の共通部分のべき集合の個数を表しており、
${\boldsymbol\phi}(A_1)^\top {\boldsymbol\phi}(A_2)$ は $A_1$ と $A_2$ に共通な部分集合の個数を表している。
よって、 $k(A_1,A_2)=2^{|A_1\cap A_2|}={\boldsymbol\phi}(A_1)^\top {\boldsymbol\phi}(A_2)$ が成り立つ。
従って題意は示された。