- 講師：津田宏治
- 資料：生物データマイニング論(2019)
In [1]:
import numpy as np
import matplotlib.pyplot as plt
講義の構成
パターン認識
- 対象を識別するルールを訓練データより、自動的に取得する。
- 各対象を全データ共通次元のベクトルで表現すれば、識別関数 $f(\mathbf{x})$ は、特徴空間上に定義される。
- 元の空間（入力空間）を非線形に写像すれば、写像先（特徴空間）で線形識別することで非線形識別が達成される。 $$\phi:\mathbf{X}\rightarrow\mathbb{R}^m$$
- どのように写像を定めるかは難しい問題。
カーネル法の紹介
- 上で紹介した写像を、類似度関数（カーネル関数）に基づいて決める手法。（例：ガウシアンカーネル $K(\mathbf{x},\mathbf{x}^{\prime}) = \exp\left(-\frac{\|\mathbf{x}-\mathbf{x}^{\prime}\|}{\sigma}\right)$）
- 類似度さえ定義できればどのような対象（例：生物学的ネットワーク上のタンパク質の分類）にでも適用できる。
- 複雑な問題になると非常に高い次元に写像する必要があるが、カーネル関数さえ求められれば写像 $\phi$ を陽に求める必要はない（カーネルトリック）。
- $k(\mathbf{x},\mathbf{x}^{\prime})$ が有効なカーネル関数であるための必要十分条件は、任意の $\{\mathbf{x}_n\}$ に対して、要素が $k(\mathbf{x}_n,\mathbf{x}_m)$ で与えられるグラム行列 $\mathbf{K}$ が半正定値であること。
- 新しいカーネル関数を定義してそれが有効な関数かを確認するのは大変なので、次の性質を用いて新たな関数を定義することが多い。
新たなカーネル関数を構築するための方法¶
有効なカーネルとして $k_1(\mathbf{x},\mathbf{x}^{\prime})$ と $k_2(\mathbf{x},\mathbf{x}^{\prime})$ が与えられた時、次の関数もやはりカーネル関数として有効である。
$$\begin{aligned} k\left(\mathbf{x}, \mathbf{x}^{\prime}\right) &=c k_{1}\left(\mathbf{x}, \mathbf{x}^{\prime}\right) & (6.13)\\ k\left(\mathbf{x}, \mathbf{x}^{\prime}\right) &=f(\mathbf{x}) k_{1}\left(\mathbf{x}, \mathbf{x}^{\prime}\right) f\left(\mathbf{x}^{\prime}\right) & (6.14)\\ k\left(\mathbf{x}, \mathbf{x}^{\prime}\right) &=q\left(k_{1}\left(\mathbf{x}, \mathbf{x}^{\prime}\right)\right) & (6.15)\\ k\left(\mathbf{x}, \mathbf{x}^{\prime}\right) &=\exp \left(k_{1}\left(\mathbf{x}, \mathbf{x}^{\prime}\right)\right) & (6.16)\\ k\left(\mathbf{x}, \mathbf{x}^{\prime}\right) &=k_{1}\left(\mathbf{x}, \mathbf{x}^{\prime}\right)+k_{2}\left(\mathbf{x}, \mathbf{x}^{\prime}\right)& (6.17)\\ k\left(\mathbf{x}, \mathbf{x}^{\prime}\right) &=k_{1}\left(\mathbf{x}, \mathbf{x}^{\prime}\right) k_{2}\left(\mathbf{x}, \mathbf{x}^{\prime}\right) & (6.18)\\ k\left(\mathbf{x}, \mathbf{x}^{\prime}\right) &=k_{3}\left(\phi(\mathbf{x}), \phi\left(\mathbf{x}^{\prime}\right)\right) & (6.19)\\ k\left(\mathbf{x}, \mathbf{x}^{\prime}\right) &=\mathbf{x}^{\mathrm{T}} \mathbf{A} \mathbf{x}^{\prime}& (6.20) \\ k\left(\mathbf{x}, \mathbf{x}^{\prime}\right) &=k_{a}\left(\mathbf{x}_{a}, \mathbf{x}_{a}^{\prime}\right)+k_{b}\left(\mathbf{x}_{b}, \mathbf{x}_{b}^{\prime}\right) & (6.21)\\ k\left(\mathbf{x}, \mathbf{x}^{\prime}\right) &=k_{a}\left(\mathbf{x}_{a}, \mathbf{x}_{a}^{\prime}\right) k_{b}\left(\mathbf{x}_{b}, \mathbf{x}_{b}^{\prime}\right) & (6.22) \end{aligned}$$※ ここで、それぞれの変数は以下の意味を持つ。
| 変数 | 説明 |
|---|---|
| $c>0$ | 定数 |
| $f(\cdot)$ | 任意の関数 |
| $q(\cdot)$ | 非負の係数を持つ多項式 |
| $\phi(\mathbf{x})$ | $\mathbf{x}$ から $\mathbb{R}^{M}$ への関数 |
| $k_3(\cdot,\cdot)$ | $\mathbb{R}^{M}$ で定義された有効なカーネル |
| $\mathbf{A}$ | 対象な半正定値行列 |
| $\mathbf{x}_a,\mathbf{x}_b$ | $\mathbf{x}=(\mathbf{x}_a,\mathbf{x}_b)$ であるような変数（必ずしも互いに素である必要はない） |
| $k_a,k_b$ | それぞれの特徴空間において有効なカーネル関数 |
カーネル関数の例¶
$$k(x,x^{\prime}) = \boldsymbol{\phi}(x)^T\boldsymbol{\phi}(x^{\prime}) = \sum_{i=1}^M\phi_i(x)\phi_i(x^{\prime})\qquad (6.10)$$
| # | 多項式 | ガウス | シグモイド |
|---|---|---|---|
| 基底関数 | $$\phi_j(x) = cx^j$$ | $$\phi_j(x) = \exp\left\{-\frac{(x-\mu_j)^2}{2s^2}\right\}\qquad(3.4)$$ | $$\begin{aligned}\phi_j(x) &= \sigma\left(\frac{x-\mu_j}{s}\right) & (3.5)\\\sigma(a) &=\frac{1}{1+\exp(-a)} & (3.6)\end{aligned}$$ |
In [2]:
# mapping function
def polynomial(x,d,c=1): return c*x**d
def gaussian(x,mu,s=0.1): return np.exp( -((x-mu)**2) / (2*s**2) )
def logistic(x,mu,s=0.1): return 1 / (1 + np.exp(- (x-mu)/s ))
In [3]:
# mapping function
kernel = lambda phi,x_prime,X,key=None,**params : np.array([sum([phi(x_prime,**{key:val}) * phi(x,**{key:val}) for val in params[key]]) for x in X])
In [4]:
params = [
(polynomial, -0.5, "d", np.linspace(1,11,11)),
(gaussian, 0, "mu", np.linspace(-1,1,11)),
(logistic, 0, "mu", np.linspace(-1,1,11)),
]
In [5]:
X = np.linspace(-1,1,1000)
In [6]:
ncol=len(params)
fig = plt.figure(figsize=(12, 6))
for i,param in enumerate(params):
phi,x_prime,key,vals = param
ax_base = plt.subplot2grid((5,ncol),(0,i), rowspan=3)
for val in vals:
Y = phi(X,**{key:val})
ax_base.plot(X,Y)
ax_base.set_title(phi.__name__)
ax_kernel = plt.subplot2grid((5,ncol),(3,i), rowspan=2)
ax_kernel.plot(X, kernel(phi,x_prime,X,key,**{key:vals}))
ax_kernel.scatter(x_prime,min(ax_kernel.get_ylim()),marker="x",color="black",label="$x^{\prime}$")
ax_kernel.set_xlabel("$x$"), ax_kernel.set_title("$k(x,x^{\prime})$"), ax_kernel.legend()
plt.tight_layout()
plt.show()
様々なカーネル¶
- 生物学的配列のカーネル
- Spectrum kernel (Leslie et al., 2002)
- Marginalized kernel (Tsuda et al., 2002)
- Profile kernel (Kuang et al., 2004)
- Local alignment kernel (Saigo et al., 2004)
- 木構造に関するカーネル
- Kernel for phylogenetic profiles (Vert, 2002)
- Kernel for natural language (Suzuki et al., 2003)
- Kernel for RNA sequences (Kin et al., 2002)
最適化理論の復習
ラグランジュ未定乗数法に記載。
サポートベクターマシーン
- マージン最大化に基づく線形識別器
- カーネル関数と組み合わせることによって非線形な識別も可能
- サンプル間の類似度にしか依存しない（→非ベクトルデータの分類にも適用可能）
詳しくは サポートベクターマシン(SVM) に記載。
In [ ]: