MIT OCW, Machine Learning 10日目 モデル選択の理論1

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 9

Kernel Optimization

kernelのあるパラメータを変えて,問題により適したkernelをつくることができる. 例えばradial basis kernelの$\beta$のようなパラメータを変化させたり,$\mathbf{x}$の次元に重み付けをしてから$\phi$に渡すような方法が考えられる. パラメータのよさの基準には,cross-validationやgeneralization errorに関連した基準(marginなど)が用いられる. marginは$\phi$を定数倍すると同時に倍化するため,normalization $\|\phi(\mathbf{x})\|=1$という制限を加える.normalizationは例えば
$$\tilde{K}(\mathbf{x}, \mathbf{x'})=\frac{K(\mathbf{x, x'})}{\sqrt{K(\mathbf{x,x'})K(\mathbf{x,x'})}}$$
で実現できる.
他のkernel optimizationの方法にkernel alignentがある. すなわち,パラメータやGram matrixを理想的なkernelに近づけるように調整するのである. 例えばclassificationでは
$$K^*_{ij}=y_iy_j$$
を標的となるkernelのGram matrixとする.というのは,$\alpha_j = 1/n$とすれば,
$$\sum_{j=1}^n \alpha_j y_j K^*_{ij}=y_i$$
と,全てのtraining exampleが等しいmarginで正しく分類できるためである.
kernelをこの標的に近づける方法を考える.
$$K(\mathbf{x}, \mathbf{x'};\theta) = \sum_{i=1}^m \theta_i K_i(\mathbf{x,x'}), \theta_i \geq 0, \sum_{i=1}^m \theta_i=1$$

のように,kernelたちのconvex combinationによってkernel $K$を構成するとき,$\theta_i$が我々が選べるパラメータである. $K$のGram matrix $K_{ij}(\phi)$を,標的のGram matrix $K^*_{ij}$に近づけるため,Gram matrixをベクトルと考えて,その内積を
$$<K^*, K_\theta> = \sum_{i,j=1}^n K^*_{ij}K_{ij}(\theta)$$
と定める. こうして$\theta$は$K^*$と$K(\theta)$のcosine類似度
$$\frac{<K^*, K_\theta>}{\sqrt{<K^*,K^*><K_\theta,K_\theta}}$$
を最大化させる$\theta$を求めれば良い.

Model (kernel) selection

少ないtraining exampleに複雑すぎるmodel(kernel)を使うと,over-fittingという問題が起きる. 問題によって使うkernelの種類を制限することがある. kernelを選ぶことで
linearな$K_1$があるとき,discriminant functionは
$$f_1(\mathbf{x}; \theta, \theta_0) = \theta^T \phi^{(1)}(\mathbf{x})+\theta_0$$
という形をしている.$\phi^{(1)}(\mathbf{x})$は$K_1(\mathbf{x, x'})=\phi^{(1)}(\mathbf{x})^T\phi^{(1)}(\mathbf{x'})$となる関数で,$\mathbf{x}$の$K_1$によるfeature representationという. $\theta, \theta_0$を変えることで可能なdiscriminant functionの集合
$$\mathcal{F}_1 = \{f_1(\cdot; \theta, \theta_0): \theta \in \mathbb{R}^d_1, \theta_0 \in \mathbb{R}\}$$
を構成できる. 同様にquadratic kernelによって可能な集合$\mathcal{F}_2$がある. このように

Model Selection Preliminaries

$S_n = \{(\mathbf{x}_1, y_1)...,(\mathbf{x}_n,y_n)\}$はtraining setとする. $\mathcal{F}_i$をmodelとして選んで,$\hat{f}_i \in \mathcal{F}_i$をbest fitting discriminant functionとすると,$\hat{f}_i$は
$$J(\theta, \theta_0) = \sum_t Loss(y_t, f(\mathbf{x}_t; \theta, \theta_0))+\lambda_n \|\theta\|^2$$
を最小化する.$Loss$はhinge lossでもlogisticでも他の何でもよい. $\lambda_n$は$n$によってへｋ擦るregularization parameterである. $\hat{f}_i=f(\mathbf{x};\hat{\theta}, \hat{\theta_0})$が新しいexampleにどれほどgeneralizeできているかが問題となる.
それぞれの$(\theta,\theta_0)$すなわちそれぞれのdiscriminant functionはexpected lossあるいはrisk
$$R(\theta,\theta_0) = E_{(\mathbf{x},y)\sim P}\left\{Loss^* (y, f(\mathbf{x};\theta,\theta_0)) \right\}$$
をもつ.ここで$P$は問題となるデータを生成している分布で，普通は未知であり,$(\mathbf{x},y)$もそこから生成されていると考える. これが,我々が最小化したいgeneralization errorである. $S_n$によって決まる$\hat{f}_i$のrisk $R(\hat{f}_i)$を最小化する$\mathcal{F}_i$を選ぶことが最終的な目標である. ただし$S_n$は$P$から生成されるので,$R(\hat{f}_i)$も$\hat{f_i}$も確率変数である(理論的には便利な仮定だが,実際に$S_n$が正しく$P$から生成されているとは限らない).
$P$が既知であるなら$argmax_y P(y|\mathbf{x})$を考えれば良いが，ここでは$P$は未知として,$S_n$だけを使って$\hat{f}_i \in \mathcal{F}_i$を，さらには$\mathcal{F}_i$をも選ばなければならない.
簡単のため,$\mathcal{F}_1, \mathcal{F}_2$を，linearとquadraticなdiscriminant functionの集合とし,$\mathcal{F_1, F_2}$のみを議論する. $\mathcal{F}_1 \subset \mathcal{F}_2$だから,$\mathcal{F}_2$から選ぶことで必ずtraining setにおけるerrorが小さい$f$を得られるが,example とlabelの関係が線形であるときにも非線形な$\mathcal{F}_2$から選ぶと，over-fittingしているかもしれない. 真の分布が線形分離可能であるとき,quadraticなdecison boundaryはノイズに影響されてgeneralizeがうまく行っていないということである. したがって$\mathcal{F}$が複雑になるほどtraining setに対する性能が向上する一方でtest setに対する性能は低下していく(fig.1). よって適切な複雑さを選ぶことが重要になってくる.

Model selection criteria: structural risk minimization

expected risk
$$R(\hat{f}_i) = E_{(\mathbf{x}|y)\sim P}\left\{ Loss^* (y, \hat{f_i}(\mathbf{x})) \right\}$$
とempirical risk(training errro)
$$R_n(\hat{f}_i) = \frac{1}{n} \sum_{t=1}^n \left( Loss^* (y, \hat{f_i}(\mathbf{x})) \right)$$
を関連付けることができれば,$R_n(\hat{f}_i)$を計算することで$R(\hat{f}_i)$を議論することが出来る. モデルが複雑になるほどtraining errorがgeneralization errorを表現しなくなっていくと考えられるので,$R_n$と$R$の関係を以下のように記述する.
$$R(\hat{f}_i) \leq R_n(\hat{f_i}) +C(n, \mathcal{F}_i, \delta) \ \ \ \ (16)$$
$C$はcomplexity penaltyといって,$\mathcal{F}_i$が複雑になるほど増大し,$n$によって減少する.
(16)はupper bound guarantee of generalization errorを与える. このupper boundが最小になるような$\mathcal{F}_i$を選べば良い. fig.2 はモデルの複雑さとこのboundの関係である.

$\mathcal{F}_i$が有限集合である時の不等式(16)の意味を考える.
$$P(\max_{f\in\mathcal{F}_i} |R(f)-R_n(f)|>\epsilon) \leq \delta$$
の上限を見積もる. これは少なくとも1つの$f$について，そのtraining errorとriskの差が$\epsilon$を上回る確率で,sample spaceは$S_n$の選び方である.
$\delta = P(\max_{f \in \mathcal{F}_i} |R(f)-R_n(f)|>\epsilon) \ \ (6)$は
$$R(f) \leq R_n(f) + \epsilon \ \ \text{for all } f \in \mathcal{F}_i$$
という主張が成立しない確率と言える. $\delta$を固定すると,(6)をみたす最小の$\epsilon =\epsilon(n, \mathcal{F}_i, \delta)$がcomplexity penaltyとなる.
$(6)$によって$\delta$を計算することはふつう不可能だから，上限を与える.
$$\begin{aligned}P(\max_{f \in \mathcal{F}_i} |R(f)-R_n(f)|>\epsilon)&=P(\exists f : |R(f)-R_n()|>\epsilon) \\ &\leq \sum_{\mathcal{F_i}} P(|R(f)-R_n(f)|>\epsilon)\ \ \ (8)\end{aligned}$$
$f$を固定して$P(|R(f)-R_n(f)|>\epsilon)$を考える. training sample $(\mathbf{x}_t, y_t)$がi.i.d.に得られて,$s_t = \begin{cases} 1 \ \ &\text{ if } y_tf(\mathbf{x}_t)\leq 0 \\ 0 &\text{otherwise}\end{cases}$とすると empirical error $R_n(f)$は$s_t$の和で,
$$R_n(f) = \frac{1}{n}\sum_{t=1}^n s_t$$
$E[s_t]=R(f)$だから,
$$P(|R(f)-R_n(f)|>\epsilon) = P(|q-\frac{1}{n}\sum_t s_t|>\epsilon)$$
ただし$q=R(f)$で,確率のsample spaceは$P(s_t=1)=q$をみたす$s_1, ..., s_n$である.
Hoeffding’s inequalityから
$$P(|q-\frac{1}{n}\sum_{t=1}^n s_t| > \epsilon)\leq 2 \exp(-2n\epsilon^2)$$
が成立する. この上限は$f$によらない. この結果を(8)に代入して，
$$P(\max_{f \in \mathcal{F}_i}|R(f)-R_n(f)|>\epsilon) \leq 2|\mathcal{F}_i|\exp(-2n\epsilon^2)=\delta$$
が成立する. $\epsilon$に解いて,
$$\epsilon=\epsilon(n,\mathcal{F}_i, \delta) = \sqrt{\frac{\log|\mathcal{F}_i|+\log(2/\delta)}{2n}}$$
である.これが$\mathcal{F}_i <\infty$の場合のcomplexity penaltyである.
以上より,少なくとも$1-\delta$の確率で
$$R(f) \leq R_n(f) + \sqrt{\frac{\log|\mathcal{F}_i| + \log (2/\delta)}{2n}}, \text{ uniformly for all }f \in \mathcal{F}_i$$
が成立する. model selectionでは$\{\mathcal{F}_i\}$のそれぞれについて$\hat{f_i}$を選び，$\hat{f}_i, |\mathcal{F}_i|$によってboundを計算し,boundが最小となる$\mathcal{F}_i$を選ぶ． このとき$n$と$\delta$は固定する．

Example

$\delta=0.05$とし,training error 0, generalization error が最大10%であるようにtraining exampleの個数$n$を見積もる.
$$R(f) \leq 0 + \sqrt{\frac{\log |\mathcal{F}_i| + \log (2/0.05)}{2n}}\leq 0.10$$
だから,
$$n = \frac{\log|\mathcal{F}_i| + \log (2/0.05)}{2(0.10)^2}$$
である.

Model selection criteria: Bayesian score, Bayesian information criterion

linear regressionの例を通じてBayesian scoreについての理解を深める. モデル$\mathcal{F}$は$d$次元のインプット$\mathbf{x}$を$y \in \mathbb{R}$に写す写像で,
$$P(y|\mathbf{x}, \theta, \sigma^2) = N(y; \theta^T \mathbf{x}, \sigma^2)$$
とする. $\sigma^2$を固定して,$\theta$だけを動かすとする. $D=\{(\mathbf{x}_1, y_1),...,(\mathbf{x}_n, y_n)\}$が与えられたとき,likelihoodは
$$L(D;\theta) = \prod_{t=1}^n N(y_t; \theta^T\mathbf{x}_t,\sigma^2) = \prod_t \frac{1}{\sqrt{2\pi \sigma^2}}\exp(-\frac{1}{2}(y_t-\theta^T\mathbf{x}_t)^2)$$
以前は$L$を最大化する$\hat{\theta}$を唯一つ選んだが，Bayesian analysisではlinear regression functionたちを$L(D;\theta)$によって重み付けして，それら全てを利用する.
このような枠組みでは,$D$を得た後の$\theta$の知識はposterior distribution $P(\theta|D)$であって,これは$L(D;\theta)$と相似である.つまり$P(\theta|D) \propto L(D;\theta)$.
しかし例えば$D=\phi$の場合には$\forall \theta. L(D;\theta)=1$だから,$P(\theta|D)$が発散してしまう．　よってprior distribution $P(\theta)$を導入する.
$$P(\theta) = N(\theta; 0, \sigma^2_P \cdot I)$$
すると
$$P(\theta|D) \propto L(D;\theta) P(\theta)$$
で,normalization constantは
$$P(D|\mathcal{F}) = \int L(D;\theta)P(\theta)d\theta$$
であり,marginal likelihoodともいう. これは$\mathcal{F}$と$D$にのみよる. regressionでは
$$\begin{aligned} \log P(D|\mathcal{F}) &= -\frac{n}{2} \log(2\pi\sigma^2) + \frac{d}{2} \log \lambda - \frac{1}{2} \log |\mathbf{X^TX}+\lambda I| \\ &-\frac{1}{2\sigma^2}(\|\mathbf{y}\|-\mathbf{y^TX}(\mathbf{X^TX}+\lambda I)^{-1}\mathbf{X^ty})\end{aligned}$$

ここで$\lambda = \sigma^2/\sigma^2_P$はnoise とpriorの比で,$\mathbf{X}=[\mathbf{x}_1,...,\mathbf{x}_n]^T, \mathbf{y}=[y_1,...,y_n]^T$である.
このときposteriorは
$$P(\theta|D) = \frac{L(D;\theta)P(\theta)}{P(D|\mathcal{F})}$$
と正規化される.$P(\theta|D)=N(\theta;\mu,\Sigma)$とposteriorも正規分布する.
$$\begin{aligned} \mu = (\mathbf{X^TX}+\lambda I)^{-1}\mathbf{X^Ty} \\ \Sigma = \sigma^2 (\mathbf{X^TX}+\lambda I)^{-1} \end{aligned}$$

新たな$\mathbf{x}$に対する推測は
$$P(y|\mathbf{x},D) = \int P(y|\mathbf{x},\theta)P(\theta|D)d\theta$$
で与えられる. 真のBayesianはまさに全ての$\theta$について上の積分を行うが,我々はfeature mapping $\mathbf{x} \mapsto \phi(\mathbf{x})$で特徴づけられるregression modelに$\theta$を制限して議論することになる.linearな$\phi^{(1)}$とquadraticな$\phi^{(2)}$をfeature mappingとする.
$$\begin{aligned} \mathcal{F}_1: \ \ &P(y|\mathbf{x},\theta,\sigma^2) = N(y;\theta^T\phi^{(1)}(\mathbf{x}),\sigma^2), \theta \in \mathbb{R}^{d_1}, P(\theta|\mathcal{F}_1) \\ \mathcal{F}_2: &P(y|\mathbf{x},\theta,\sigma^2)=N(y;\theta^T \phi^{(2)}(\mathbf{x}),\sigma^2) , \theta \in \mathbb{R}^{d_2}, P(\theta|\mathcal{F}_2) \end{aligned}$$
が比較するmodelである. modelにPrior distribution $P(\theta|\mathcal{F})$を含むのには利点も欠点もあるが，どちらにせよ含まないのと大した差はない.
$\mathcal{F_1, F_2}$のうち,よりmarginal likelihood (Bayesian score)が大きい方を選ぶことになる. すなわち,$D$を与えられたら,$P(D|\mathcal{F}_i) > P(D|\mathcal{F}_j)$ならば$\mathcal{F}_i$を選ぶのである.

Model selection criteria: Bayesian information criterion(BIC)

Bayesian information criterion(BIC)はBayesian scoreに対するasymptotic(漸近的な) 近似であって，その単純さのためによく使われる.
$$BIC = l(D,\hat{\theta}) - \frac{d}{2}\log (n)$$
である.ここで$l(D;\theta)$はtraining dataに対するmaximum likelihoodの対数であって,$d$はmodelのindependent parameterの個数, $n$はtraining exampleの個数である. $BIC$は$n$が十分大きいときBayesian scoreに漸近する. Bayesian scoreの計算は困難なことが多いので,かわりにBICを使う. Bayesian scoreと同様に,BICが大きい方のmodelを選ぶ.