---
# System prepended metadata

title: MLT HW3

---

# 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)}$之間也會是獨立的。
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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)$

<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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]$ #
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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)})$ #
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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)$
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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)))$
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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}$
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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)))$
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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$ #
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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$
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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$
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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)$ #
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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: 加上全正和全負的情形)
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
<br></br>
## 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)#
<br></br>
<br></br>
<br></br>
<br></br>
## 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$

