MLT HW3 - HackMD

# MLT HW3 資工二 B07902046 高長聖 ## 1 (1) 由於對於所有的$x_i^{(l-1)}, w_{ij}^{(l)}$都是independent的，因此: $E[s_j^{(l)}] = E[\sum_{i=1}^{d^{(l-1)}}w_{ij}^{(l)}x_i^{(l-1)}]$ $= \sum_{i=1}^{d^{(l-1)}}E[w_{ij}^{(l)}]E[x_i^{(l-1)}]$ $= \sum_{i=1}^{d^{(l-1)}}0 * E[x_i^{(l-1)}]$ ($w_{ij}^{(l)}$ is zero mean) $= 0$ $\Rightarrow$ $s_j^{(l)}$ are zero mean (2) 由於$s_j^{(l)} = \sum_{i=1}^{d^{(l-1)}}w_{ij}^{(l)}x_i^{(l-1)}$ 在given $x^{(l-1)}$，$s_j^{(l)}$是independent random variable $w_{ij}^{(l)}$的線性組合因此，對於每個j，$P(s_j^{(l)}) = P(w_{1j}^{(l)})P(w_{2j}^{(l)})...P(w_{d^{(l-1)}j}^{(l)})$ 又由於$w_{ij}^{(l)}$是互相獨立的，因此$(w_{1j_1}^{(l)}, w_{2j_1}^{(l)}, ...)$也會和$(w_{1j_2}^{(l)}, w_{2j_2}^{(l)}, ...)$獨立因此，對於任何j，$s_j^{(l)}$之間也會是獨立的。 ## 2 referece: http://people.stern.nyu.edu/wgreene/MathStat/Problem3-Solutions.pdf lemma 1: $Var(XY) = \sigma_x^2\sigma_y^2+\sigma_x^2\mu_y^2+\sigma_y^2\mu_x^2$ proof: $Var(XY) = E[X^2Y^2]-(E[XY])^2$ $= E[X^2]E[Y^2] - (E[X]E[Y])^2$ $= (\sigma_x^2+\mu_x^2)(\sigma_y^2+\mu_y^2) - \mu_x^2\mu_y^2$ $= \sigma_x^2\sigma_y^2+\sigma_x^2\mu_y^2+\sigma_y^2\mu_x^2$ $Var(s_i^{(l)}) = Var(\sum_{i=1}^{d^{(l-1)}}w_{ij}^{(l)}x_i^{(l-1)}) = \sum_{i=1}^{d^{(l-1)}}Var(w_{ij}^{(l)}x_i^{(l-1)})$ $= \sum_{i=1}^{d^{(l-1)}}(\sigma_w^2\sigma_x^2+\sigma_w^2\mu_x^2+\sigma_x^2\mu_w^2)$ $= d^{(l-1)}(\sigma_w^2\sigma_x^2+\sigma_w^2\mu_x^2)$ $= d^{(l-1)}\sigma_w^2E[(x^{(l-1)}_i)^2]$ $= d^{(l-1)}\sigma_w^2*(\sigma_x^2+\bar{x}^2)$ ## 3 經過ReLU activation的轉換，$x_i^{(l-1)}$的c.m.f會變成: $$\left\{ \begin{aligned} 0, \ \ x_i^{(l-1)} < 0\\ 0.5, \ \ x_i^{(l-1)} = 0 \\ F(s_i^{(l-1)}), \ \ otherwise \end{aligned} \right. $$ 因此，$x_i^{(l-1)}$的p.d.f會變成: $$\left\{ \begin{aligned} 0, \ \ x_i^{(l-1)} < 0\\ \infty, \ \ x_i^{(l-1)} = 0 \\ f(s_i^{(l-1)}), \ \ otherwise \end{aligned} \right. $$ $\Rightarrow$ $E[(x_i^{(l-1)})^2] = \lim_{n\rightarrow0^-}\int_{-\infty}^{n}(x_i^{(l-1)})^2* 0dx_i^{(l-1)} + 0 + \lim_{n\rightarrow0^+}\int_{n}^{\infty}(x_i^{(l-1)})^2* f(x_i^{(l-1)})dx_i^{(l-1)}$ $= 0 + 0 + \lim_{n\rightarrow0^+}\int_{n}^{\infty}(s_i^{(l-1)})^2*f(s_i^{(l-1)})ds_i^{(l-1)}$ $= \frac{1}{2}E[(s_i^{(l-1)})^2]$ # ## 4 referece: http://people.stern.nyu.edu/wgreene/MathStat/Problem3-Solutions.pdf lemma 1: $Var(XY) = \sigma_x^2\sigma_y^2+\sigma_x^2\mu_y^2+\sigma_y^2\mu_x^2$ proof: $Var(XY) = E[X^2Y^2]-(E[XY])^2$ $= E[X^2]E[Y^2] - (E[X]E[Y])^2$ $= (\sigma_x^2+\mu_x^2)(\sigma_y^2+\mu_y^2) - \mu_x^2\mu_y^2$ $= \sigma_x^2\sigma_y^2+\sigma_x^2\mu_y^2+\sigma_y^2\mu_x^2$ $Var(s_i^{(l)}) = Var(\sum_{i=1}^{d^{(l-1)}}w_{ij}^{(l)}x_i^{(l-1)}) = \sum_{i=1}^{d^{(l-1)}}Var(w_{ij}^{(l)}x_i^{(l-1)})$ $= \sum_{i=1}^{d^{(l-1)}}(\sigma_w^2\sigma_x^2+\sigma_w^2\mu_x^2+\sigma_x^2\mu_w^2)$ $= d^{(l-1)}(\sigma_w^2\sigma_x^2+\sigma_w^2\mu_x^2)$ $= d^{(l-1)}\sigma_w^2E[(x^{(l-1)}_i)^2]$ $= d^{(l-1)}\sigma_w^2* \frac{1}{2}E[(s_i^{(l-1)})^2]$ (by problem 3) $= \frac{d^{(l-1)}}{2}\sigma_w^2(Var(s_i^{(l-1)})+\mu_s^2)$ $= \frac{d^{(l-1)}}{2}\sigma_w^2Var(s_i^{(l-1)})$ # ## 5 ![](https://i.imgur.com/MJc59IN.jpg) 因此，只要從: $\mu = 0, \sigma^2 = \frac{2}{(a^2+1)d^{(l-1)}}$ 的distribution中挑選w即可。 ## 6 $v_0 = 0$ $v_1 = 0 + (1-\beta)\Delta_1$ $v_2 = \beta(1-\beta)\Delta_1 + (1 - \beta)\Delta_2$ $v_3 = \beta^2(1-\beta)\Delta_1+\beta(1-\beta)\Delta_2+(1-\beta)\Delta_3$ . . $v_T=\sum_{t=1}^{T}\beta^{T-t}(1-\beta)\Delta_t$ $\Rightarrow$ $\alpha_t=\beta^{T-t}(1-\beta)$ ## 7 $\alpha_1=\beta^{T-1}(1-\beta)\leq\frac{1}{2}$ $\beta^{T-1}\leq\frac{1}{2(1-\beta)}$ $(\beta^{-1})^{T-1}\geq2(1-\beta)$ $T-1\geq\log_{\beta^{-1}}2(1-\beta)$ $T\geq1+\log_{\beta^{-1}}2(1-\beta)$ $\Rightarrow$T的最小值為$max(1, ceil(1+\log_{\beta^{-1}}2(1-\beta)))$ ## 8 $\alpha_T=(1-\beta), \alpha_{T-1}=\beta(1-\beta), ..., \alpha_1=\beta^{T-1}(1-\beta)$ $\Rightarrow$ $\sum_{t=1}^{T}\alpha_t = \frac{(1-\beta)(1-\beta^T)}{1-\beta}=1-\beta^T$ $\alpha'_t=\frac{\alpha_t}{1-\beta^T} = \frac{\beta^{T-t}(1-\beta)}{1-\beta^T}$ ## 9 $\alpha'_1=\frac{\beta^{T-1}(1-\beta)}{1-\beta^T}\leq\frac{1}{2}$ $\Rightarrow$ $\beta^{T-1}(1-\beta)\leq\frac{1}{2}-\frac{\beta^T}{2}$ $\beta^{T-1}(1-\frac{\beta}{2})\leq\frac{1}{2}$ $\beta^{T-1}\leq\frac{1}{2-\beta}$ $(\beta^{-1})^{T-1}\geq2-\beta$ $T-1\geq\log_{\beta^{-1}}(2-\beta)$ $T\geq1+log_{\beta^{-1}}(2-\beta)$ $\Rightarrow$ T最小值為$max(1, ceil(1+log_{\beta^{-1}}(2-\beta)))$ ## 10 Discussed with B07501122 $E_p[||y-X(w⊙p)||^2]$ $=E_p[||y||^2-2y^TX(w⊙p)+||X(w⊙p)||^2]$ $= E_p[||y||^2]-2y^TX(w⊙E_p[p]) + E_p[||X(w⊙p)||^2]$ 看$E_p[||X(w⊙p)||^2]$: $= E_p[\sum_{i=1}(X(w⊙p))^2_i]$ $= E_p[\sum_{i=1}(\sum_{j=1}x_{ij}(w_jp_j))^2]$ $= E_p[\sum_{i=1}(\sum_{j=1}x_{ij}w_jE_p[p])^2]$ $= 0.5 * \sum_{i=1}(\sum_{j=1}x_{ij}w_j)^2$ $= 0.5 ||xw||^2$ 代回原本的式子: $E_p[||y||^2]-2y^TXw * 0.5 + 0.5||Xw||^2$ 對w偏微分: $-y^TX + 2*0.5(Xw)^TX = 0$ $(Xw)^TX = y^TX$ $X^TXw=X^Ty$ $w=X^{-1}(X^T)^{-1}X^Ty$ # ## 11 (1) lower bound: 要達到有最低的$E_{out}$，在投票了時候，兩個以上錯誤票的重疊要越少越好，因此，最好的情況，是$g_1$、$g_2$、$g_3$錯誤的點都沒有交集。而0.08 + 0.16 + 0.24 < 1，可以達成上述狀況，因此$E_{out}$的lower bound是0。 (2) upper bound: 要達到有最高的$E_{out}$，在投票了時候，兩個錯誤票的重疊要越多越好，因此，當$g_1$和$g_2$錯誤的點完全沒有重疊，而兩者所有錯誤的點都和$g_3$重疊的話，會有$E_{out}(G) = 0.16 + 0.08 = 0.24$，此時的0.24為$E_{out}(G)$的upper bound。 $\Rightarrow$ $0 \leq E_{out}(G) \leq 0.24$ ## 12 若存在$E_{out}(G) = \frac{2}{K+1}\sum_{k=1}^{K}e_k + \eta$，其中$\eta > 0$，代表有$\frac{2}{K+1}\sum_{k=1}^{K}e_k + \eta$ 比例的資料，得到大於等於$\frac{K+1}{2}$票。因此，$(\frac{2}{K+1}\sum_{k=1}^{K}e_k + \eta) * \frac{K+1}{2} = \sum_{k=1}^{K}e_k + \frac{K+1}{2}\eta \geq \sum_{k=1}^{K}e_k$，矛盾。 $\Rightarrow$$E_{out}(G) \leq \frac{2}{K+1}\sum_{k=1}^{K}e_k$ $\Rightarrow$$E_{out}(G)$的upper bound為$\frac{2}{K+1}\sum_{k=1}^{K}e_k$ ## 13 對於一個example: P(sampled at least once) = 1 - P(never be sampled) 因此，單一example在N'次挑選未被sample的機率: $P(never \ be \ sampled \ in \ pN) = \lim_{N\rightarrow\infty}(1-\frac{1}{N})^{Np} = e^{-p}$ $\Rightarrow$有被sample至少一次的機率為: $1 - e^{-p}$ 因此在N'中未被sample的example期望個數: $E = N * (1 - e^{-p}) = N - (e^{-p}N)$ # ## 14 在維度i中，不考慮全正或全負的情況，總共有: (5 - 0 - 1) * 2 + 2 = 10 (+2: $g_{-1, i, L}(x)$和$g_{1, i, R}(x)$的狀況) $\Rightarrow$因為總共有四個維度: 4 * 10 + 2 = 42 (+2: 加上全正和全負的情形) ## 15 lemma 1: 對於同一維度的$n_{i'}, m_{i'}$，則在i = i'中所有的decision stump中，會將兩者分為不同類的decision stump個數為$2|n_{i'}-m_{i'}|$ proof: Without loss of generality, let $n_{i'} \leq m_{i'}$ (1) $n_{i'} = m_{i'}$: 所有decision stump都會將兩者分為同類: 0 = $2|n_{i'}-m_{i'}|$ (2) $n_{i'} < m_{i'}$ 在$n_{i'}$和$m_{i'}$之間(不包含$n_{i'}$和$m_{i'}$)區間個數為: $|n_{i'} - m_{i'}| - 1$ 因此，會將兩者分錯的decision stump個數為: $2(|n_{i'} - m_{i'}| - 1) + 2 = 2|n_{i'} - m_{i'}|$ (+2: $g_{-1, i', n_{i'}}$、$g_{1, i', m_{i'}}$) $\Rightarrow$ 得證回到題目，由於符號上的方便，令$\zeta = |G|$ $K_{ds}(x, x') = (\phi_{ds}(x))^T(\phi_{ds}(x')) = \sum_{k=1}^{\zeta}g_{s_k, i_k, \theta_k}(x)g_{s_k, i_k, \theta_k}(x')$ $= \sum_{k=1}^{\zeta}sign(x_{i_k}- \theta_k)sign(x'_{i_k}-\theta_k)$ 假設$x = (x_1, x_2, ..., x_d), x'=(x'_1, x'_2, ..., x'_d)$ 對於所有i = i'的decision stump，根據lemma 1，會將$x_{i'}$和$x'_{i'}$分錯的decision stump總數為$2|x_{i'} - x'_{i'}|$ 因此，對於所有decision stump，會分類錯的decision stump總數為: $2\sum_{i=1}^{d}|x_i-x'_i|$ $\Rightarrow$ 根據上題，由於$\zeta = d((R - L - 1) * 2 + 2) + 2 = 2dR-2dL + 2$ (R-L-1: 在R和L之間，不包含R和L的點的個數) 因此$K_{ds}(x, x') = \zeta - 2 * (分類錯的decision \ stump總數) = 2dR-2dL+2-4\sum_{i=1}^{d}|x_i-x'_i|$ $=2dR-2dL+2-4||x-x'||_1$ (其中$|| \ ||_1$是one norm)# ## 16 lemma 2: 在實數系上，尋找一點$s\in(n, m)$，則(n, s)上所有點可以完美對應到(s, m)上的點，且(s, m)上所有的點也可以完美對應到(n, s)上的點。 proof: (1) 取一點$a\in(n, s)$，則可以找到一點$b\in(s, m)$，$b = \frac{m * (a - n) + s * (s - a)}{s - n}$與a進行對應 (2) 取一點$b\in(s, m)$則可以找到一點$a\in(n, s)$，$a=\frac{n * (m-b) + s * (b - s)}{m - s}$與b進行對應。將(1)中的式子進行移項，可以發現$a = \frac{n * (m-b) + s * (b - s)}{m - s}$，與(2)中b所對應的a相同。因此，可以知道在(n, s)上取一點a，可以與(s, m)上的其中一點b進行一一對應。得證# $\Rightarrow$回到題目: 假設對於同一維度的$n_k, m_k$，在不失一般性，假設$n_k \leq m_k$。則有以下狀況: (1) $n_k, m_k$都不在邊界上，且$n_k \neq m_k$ (2) $n_k, m_k$都不在邊界上，且$n_k = m_k$ (3) $n_k$和$m_k$其中之一在邊界上，且$n_k \neq m_k$ (4) $n_k$和$m_k$都在邊界上，且$n_k = m_k$ (5) $n_k$和$m_k$都在邊界上，且$n_k \neq m_k$ (所謂邊界即是R或者L) * 考慮(1)的狀況: 隨意找一點$s\in(n_k, m_k)$，則根據lemma 2，$\theta\in(L, n_k)$的decision stump(分為同類)會和$\theta\in(n_k, s)$的decision stump(分為不同類)進行一一對應。因此，兩者互相抵消。同理，$\theta\in(s, m_k)$的decision stump也可和$\theta\in(m_k, R)$的decision stump抵銷。對於$\theta = L \ or \ R$且不是全正或全負的decision stump，有兩個能將$n_k, m_k$分為同類對於$\theta = n_k \ or \ m_k$，有兩個decision stump將兩者分為同類，兩個分為不同類$\Rightarrow$互相抵銷對於$\theta = s$，則有一個decision stump把$n_k$和$m_k$分為不同類 $\Rightarrow$$K_{ds}: 2-1 = 1$ * 考慮(3)的情況: 第一種狀況，$n_k = L$，則根據lemma 2，$\theta\in(n_k, m_k)$的decision stump(分為不同類)會和$\theta\in(m_k, R)$的decision stump(分為同類)互相抵消。對於$\theta = R$的decision stump，會有2個將兩者分為同類的decision stump。對於$\theta=m_k$的decision stump，會有一個分為同類，一個分為不同類，互相抵銷。對於$\theta = n_k = L$，在不考慮全正的情況，有一個分為不同類的decision stump。同理，當$m_k = R$的時候也會相同結果 $\Rightarrow$ $K_{ds}: 1 * 2 = 2$ * 考慮(4)、(2)、(5) 在不考慮$\theta = R \ or \ L$的狀況下: (2)和(4)中的所有decision stump都會將兩者分為同類 (5)中的所有decision stump都會將兩者分為不同類。在(5)中取一點$s\in(L, R)$，則(L, s)的decision stump可以一一對應(2)的decision stump，而(s, R)的decision stumpd可以一一對應(4)中的decision stump，全部互相抵銷。在不考慮全正和全負的狀況: 在(2)中，$\theta = R \ or L$的狀況，各會增加一個將兩者分為同類的decision stump 在(4)中，若$n_k = m_k = L$的情況下，在$\theta = R \ or L$都各會增加兩個分為同類的decision stump。與此類似，$n_k = m_k = R$的情況下也會增加兩個分為同類的decision stump。在(5)中，$\theta = L \ or R$，都各會增加一個分類在不同類的decision stump。 $\Rightarrow$ $K_{ds}: 2 + 4 - 2 = 4$ 統整上述所說，並再加上全正和全負的情況: $K_{ds} = d(1 + 2 + 4) + 2 = 7d+2$