MIT OCW, Machine Learning 11日目 宿題3

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.

assigmnemt 3
Q and A

1.

答案.

(b) $E[error_{LOOCV}(S_n)]=E[\frac{1}{n}\sum_t error_t(S_n)] = \frac{n}{n} \cdot E[(y-\hat{f}_{S_{n-1}}(\mathbf{x}))^2]=E[(y-\hat{f}_{S_{n-1}}(\mathbf{x}))^2]$
(c)

$$\begin{aligned}var[error_{LOOCV}(S_n)] &= var[\frac{1}{n} (error_1(S_n) + \cdots+error_n(S_n))] \\ &=\frac{1}{n^2}var(\sum_1^n error_i(S_n)) <_{(1)} var(error_1(S_n)) \\ &= E[(y-\hat{f}_{S_{n-1}}(\mathbf{x}))^2] \end{aligned}$$
(1)の不等号を示せなければならなのだが,模範解答でも定性的に言及されただけだからもう明らかでいいと思う
(d)
$f^k_{keep}$がtraining errorを0にするというのは，任意の$t\in\{1,..,n\}$で$y_t = x^{(t)}_r$が成り立つということ. $y_t$を生成する$Y$と$x_r$を生成する$X_r$は独立で,$P(Y=1)=P(X_r=1)=0.5, P(Y=-1)=P(X_r=-1)=0.5$だから,$f^{k}_{keep}$がtraining errorを0にする確率は$P(\forall t. Y=X_r)=_{(1)}\prod_t P(Y=X_r)=1/2^n$. (1): 各サンプルの生成の独立性
$f^k_{flip}$も同様で,足し合わせると求める確率$2^{-(n-1)}$が得られる.
(e)
$\mathcal{M}_r$において$f^r_{keep}$のtraining error $\epsilon << 1/2$とする.
$f^r_{keep}$の$error_i(S_n)$を考える($i = 1,..., n$)
$\epsilon << 1/2$だから，training setから$i$番目を引いても$\mathcal{M}_r$から選ばれるestimatorは変わらず.$f^r_{keep}$のまま. したがって$\hat{f^r}_{-i} = f^r_{keep}$が任意の$i$で成立.
よって$error_{LOOCV}(S_n) = (1/n) \cdot \sum_i (y_i - f^r_{-i}(x_i))^2 = (1/n)\cdot\sum_i (y_i-f^r_{keep}(x_i))^2$
これは$f^r_{flip}$のtraining errorが$\epsilon << 1/2$の時も同じ. よって示せた.

模範解答.

(a)
r.v. $A, B$が同じdistributionをもつとき，$E[f(A)]=E[f(B)]$であるのを利用する.これは

$$E[f(A)] = \int f(x)p_A(x)dx = \int f(x)p_B(x)dx = E[f(B)]$$
からわかる.
$A,B$がそれぞれr.v.の集合であっても成立する. $A=\{S^{-1}_n, (\mathbf{x}_1, y_1)\},\ B=\{S_{n-1}, (\mathbf{x}, y)\}$とする.ただし$S_n^{-1}$でtrainし，$(\mathbf{x}_1, y_1)$を識別子, $S_{n-1}$は$n-1$個のtraining dataで$(\mathbf{x}, y)$を識別する. $A,B$は同じdistributionを持つから,与えられた四季が成立する.
(f)
training error を$\delta$とすると,classifierは$n\delta/4$回間違える. ある次元$i$においてtraining errorが$\epsilon$以下である時,すなわち間違いがせいぜい$floor(n\epsilon/4)$であるとする.間違いの回数を$k$とおくと,間違いの起こる場合の数は$nCk$通りで,まさにそこで間違いが起こる確率は$2^{1-n}$. よってtraining errorが$\epsilon$未満である確率は
$$p = \sum_{k=0}^{floor(n\epsilon/4)} nCk \frac{1}{2^{n-1}}$$
errorが$\epsilon$以上である確率は$1-p$で,$d$次元全てがそうである確率は$(1-p)^d$.これが$1/2$以下であれば少なくとも1つの次元でerrorが$\epsilon$未満となる. よって
$(1-p)^d \leq 1/2$を解くと,
$$d \geq \frac{1}{\log_2 \frac{1}{1-p}}$$

2.

答案.

(a)

$$P(S_n|\{l\}) = \sum_{\theta \in \{-1, 1\}} 2^{-1} \prod_{t=1}^n \left[ \frac{1+y_t\theta_l x_{t_l}}{2} \right]=\frac{1}{2^{n+1}} \left[\prod_{t=1}^n (1+y_tx_{t_l})+\prod_{t=1}^n(1-y_tx_{t_l}) \right]$$
(d) marginal likelihoodが減少し始めるとき

模範解答.

(b) 与えられた式は間違いに対して確率0を割り当ててしまう.

$$P(S_n|\mathcal{J})=\sum_{\theta \in \{1, -1\}^{|\mathcal{J}|}}2^{-|\mathcal{J}|}\prod \left[\frac{1}{|\mathcal{J}|}\sum_{j \in \mathcal{J}} f(y_t\theta_j , x_{tj}) \right]$$
とする.