비모수 함수 추정론 중간대비

 

 

서론

비모수 함수 추정론 중간고사를 대비해서 중요한 것들 중 제가 잘 모르는 정리들을 정리해 놓고 그 증명 방법들을 요약하는 cheat sheet을 만들 계획...입니다만...다 적고 나서 계획한 대로 되어 있을지는 모르겠네요.

 

해보죠.

 

본 포스팅은 서울대학교 박병욱 교수님의 비모수함수추정론 강의노트를 참고하여 기록되었습니다.

 

본론

2장

1. KDE optimal kernel

MISE($h_{opt}$)는 정해졌는데 이 MISE를 다시 최적화 하려면 $\mu_2(K)(\int K^2)^2$를 최소화하는 $K$를 찾아야 합니다.

$$\frac{5}{4} \left( \mu_2(K) \left( \int K^2 \right)^2 \right)^{2/5} \left( \int (p'')^2 \right)^{1/5} n^{-4/5} + o(n^{-4/5})$$

 

어떻게?

Scale invariance를 사용합시다.

Suppose $K \ge 0$, symmetric.

 

$$\mu_2(K)(\int K^2)^2 = \mu_2(K_sigma)(\int K_{\sigma}^2)^2 \quad (\sigma >0)$$

우리가 평소에 쓰는 $K_h$와 같습니다.

 

그럼 최소화 하면 되는데, $\mu_2(K) = \int u^2 K(u) du = c_1$으로 고정해도 어차피 곱은 일정하니까 $\int K^2$만 최소화합시다.

 

어떻게?

그냥 lagrange multiplier로 목적 함수 미분하는 게 제일 편하다.

$L(K) = \int K^2 du + \lambda_1 \int u^2K(u) du + \lambda_2 \int K(u)du$ 쓰고

 

제약조건을 아래와 같이 줍니다.

$\int u^2K(u) du = c_1$

$\int K(u)du = 1$

$K(u) \ge 0$

 

$K^2+ \lambda_1 \mu^2K + \lambda_2 K$를 K로 미분하면 $2K + \lambda \mu^2 + \lambda_2 = 0$이 나오고.

이걸 정리하면 $K(u) = -a-bu^2$으로 치환해서 생각할 수 있고 제약조건에 의해 0보다 커야 하므로 $K(u) = (-a-bu^2)_{+}$.

 

식을 풀고 $\int K(u) du = 1$로 정리한 후, $c_1$은 1이라고 놓으면 Epanechnikov kernel.

 

4장 N-W estimator

1. x를 추정할 때 $h$ 반경에 $X_i$가 하나라도 있어야 한다.

이걸 보이는 건 되게 간단한데 $P(\hat{p}=0) \to 0$을 보일 수 있다.

 

point $x$에서 확률이 있다를 $x$ 반경에서 (truncated 반경)에서 확률이 조금이라도 있다를 다음과 같이 표현.

$$p_{min, \epsilon} := \inf \{p(u) : (x- \epsilon) \vee 0 < u < (x+\epsilon) \wedge 1 \} > 0$$

 

$$\begin{aligned} P(\hat{p}=0) &= (1 - \int^{x+h}_{x-h} p(x))^n \\&\le (1-2h*p_{min,\epsilon})^n \\&\le exp(-2nh*p_{min,\epsilon}) \to 0 \end{aligned}$$

 

2. N-W의 bias

1) 비모수의 모든 bias를 구할 때 첫 번째 거쳐야 할 절차는 쪼개는 것, 

 

위처럼 쪼갤 수도 있고, $\sum_i w_iy_i$로 놓고 $\sum_i w_i =1$로도 쪼갤 수 있고 결론은 똑같지만 과정은 다양하게 할 수 있다.

 

이렇게 쪼개는 이유는 first term의 conditional expectation이 0이기 때문.

그래서 뒷 항만 구하면 된다.

 

2) $Z_n  =  E[Z_n] + O_p(\sqrt{varZ_n})$

위의 공식이 핵심 공식이고 Markov inequality로 증명됩니다.

 

조건부 기댓값을 쓴 뒤 남은 식은 아래와 같습니다.

 

$$\frac{\frac{1}{n} \sum_{i=1}^n K_h(X_i-x)(m(X_i)-m(x))}{\hat{p}}$$

 

여기서 분자 분모를 모두 $Z_n  =  E[Z_n] + O_p(\sqrt{varZ_n})$로 쪼개고 정리하면 끝입니다.

 

1) 분모

$$\hat{p}(x) = E[\hat{p}(x)] + O_p(\sqrt{\hat{p}(x)})$$

expectation 부분은 convolution이고 $p$는 continuously differentiable이니, 1차까지 전개.

$O_p$ 파트는 그냥 $var(\hat{p})= O_p(\frac{1}{nh})$ 넣으면 될 듯?

 

2)분자

이것도 $Z_n$ 공식 써서 쪼개기.

 

First Term

$E[\frac{1}{n} \sum_{i=1}^n K_h(X_i-x)(m(X_i)-m(x))]$

적분으로 바꾼 후 $f = (m(u)-m(x)) p(u)$로 쓰면 $K * f$로 쓰기. 여기서 다시 taylor 전개.

 

그런데 어디까지? 여기서 조금 문제가 있는데 $p$는 한 번 밖에 미분이 안됨.

그러므로 $m$,$p$를 각각 따로 2번 1번씩 taylor 전개해서 합친 식을 $f$로 두고 정리

 

$m(u) - m(x) = m'(x)(u-x) + \frac{1}{2}m''(x)(u-x)^2 + o(|u-x|^2)$

$p(u) = p(x) + p'(x)(u-x) + o(|u-x|)$

놓고 곱해서 $o(|u-x|^2)$항으로 잘 흡수시키면,

$$(m(u)-m(x))p(u) = m'(x)p(x)(u-x) + \left[ m'(x)p'(x) + \frac{1}{2}m''(x)p(x) \right](u-x)^2 + o((u-x)^2)$$

 

이 term을 통해 taylor 전개하면,

$K*f = \mu_1(k) m'(x)p(x)h + \mu_2(K)(m'(x)p(x) + \frac{1}{2}m''(x)p(x))h^2 + o(h^2)$ 

 

Second Term

$O_p(\sqrt{var(K_h(X_i-x)(m(X_i)-m(x))})$

 

사실 여기서는 $EZ_n^2$파트만 계산하면 됩니다. 위에 미리 계산한 $EZ_n$으로 $E[Z_n]^2$이 $EZ_n^2$보다 훨씬 작다는 걸 알게 되기 때문이죠.

 

 $g = (m(X_i)-m(x))^2p$라고 하면 g는 0,1차 미분은 0입니다. 2차 미분부터 값이 생깁니다.

$O_p(\sqrt{\frac{1}{nh} E[(K^2)_h * (m(u)-m(x))p*u)]})$ 를 계산해 주면 간단하게 $O_p(\sqrt{\frac{h}{n}}$이 유도됩니다.

 

 

이걸 계산하면 되는데 진짜 머리 아픕니다.

 

0. 분자에서 $O_p(\sqrt{\frac{h}{n}}) \to o_p(\frac{1}{\sqrt{nh}})$

1. 분모의 $\mu_0 p(x)$먼저 분자로 계산해 주기

2. 분모를 통째로 $\frac{1}{1+z} = 1-z+\frac{z^2}{1+z}$로 한 번에 계산할 것 $(1+h\frac{\mu_1p'(x)}{\mu_0p(x)})$는 1파트는 그대로, h파트는 모두 분자의 $o_p(h^2+n^{-1}h^{-1})$파트에 흡수 $O_p(h^2)$는 $o_p(h^2+n^{-1}h^{-1})$보다 작으므로.

3. 분모로부터 온 $O_p(h+n^{-1}h^{-1})$도 똑같이 흡수.

4. 문제는 $\frac{z^2}{1+z}$ term인데 분모가 1로 수렴. 밥 먹고 나니 이제 암산이 되는데 0. 사용해서 보니 $o_p(h^2+n^{-1}h^{-1})$에 모두 흡수.

 

3. Lemma 4.2

 

 

결론은 다음을 보이고 싶다.

$$\lim_{C' \to \infty} \limsup_{n \to \infty} \mathbb{P}(|Z_n| > C') = 0$$

 

순수하게 $n,C'$의 부등식을 세우자.

$\tilde{\mathcal{E}} = \mathcal{E} \cap (E[|Z_n| | X]<C)$

$$\begin{aligned}P(|Z_n| > C') &\le \frac{E[|Z_n|]I(\tilde{\mathcal{E}})}{C'} + \frac{E[|Z_n|]I(\tilde{\mathcal{E}^c})}{C'}\\&= \frac{E[E[|Z_n||{X}]I(\tilde{\mathcal{E}})]}{C'} + \frac{E[E[|Z_n||{X}]I(\tilde{\mathcal{E}^c})]}{C}\\&=\frac{C}{C'} + \frac{P(\tilde{\mathcal{E}})}{C'} \to 0\end{aligned}$$

 

4. Lemma 4.2'

 

웬만하면 다 치는데 칠 시간이 없네요.

 

Let $\epsilon > 0$. Then $\exists C$ s.t.

$$\liminf_{n \to \infty} \mathbb{P}\left[ \mathbb{E}(|Z_n| \mid X_1, \dots, X_n) < C \right] > 1 - \frac{\varepsilon}{2}$$

 

$O_p(1)$의 조건을 조작했습니다. $\mathbb{E}(|Z_n| \mid X_1, \dots, X_n) < C$를 유도하기 위해.

 

$$\liminf_{n \to \infty} P(\tilde{\mathbb{E}}) > 1-\frac{\epsilon}{2}$$

 

Apply Markov inequality

$\limsup_{n \to \infty} P(|Z_n| > C') \le \frac{E[E[|Z_n||{X}]I(\tilde{\mathcal{E}})]}{C'} + \frac{E[E[|Z_n||{X}]I(\tilde{\mathcal{E}^c})]}{C} \le \frac{C}{C'}+\frac{\epsilon}{2} \le \epsilon$.

where the last inequality holds for $C' \ge 2C/\epsilon$

 

6장 $L^{\infty}$ error

Lemma 6.2 Universal bound of KDE

Assume that $p$ is bounded on $[0,1]$.

Suppose that $K$ is Lipschitz continuous and $\frac{nh}{logn} \to \infty$ as $n \to \infty.$

Then, it holds that

$$\displaystyle \sup_{x \in [0,1]} |\hat{p}(x) - \mathbb{E}(\hat{p}(x))| = O_p(n^{-1/2}h^{-1/2}\sqrt{\log n})$$

---

직관적으로 많이 사용할 수 있는 KDE의 bound입니다.

증명을 할 건데, 핵심 아이디어는 Net입니다. Net을 만들어 sup을 두 단계로 나누어 증명하는 방법이 널리 쓰이는 방법이므로 그 방법을 차용하겠습니다.

 

$Z_n = \hat{p}(x) - \mathbb{E}[\hat{p}(x)]$, $(\tau_n)^{-1} = \frac{\sqrt{\log n}}{\sqrt{nh}}$라고 해봅시다.

이제 net $N(n^{-r})$을 정의할 건데, $n^{-r}$간격의 grid를 생각하시면 됩니다. 간단하게 $[0,1]$에서 생각하죠.

 

https://juhongyee.tistory.com/108

8 O_p(1)

 

위의 포스팅의 $O_p(1)$의 정의에 따라 식을 쓰고 두 부분으로 나누어 보겠습니다.

$\displaystyle \lim_{n \to \infty} \limsup_n P(\sup_{x \in [0,1]} |Z_n(x)| \ge C \cdot (\tau_n)^{-1})$

$\displaystyle\le \lim_{n \to \infty} \limsup_n P(\sup_{x \in [0,1], x' \in N(n^{-r})} |Z_n(x) - Z_n(x')|)$

$\displaystyle+ \lim_{n \to \infty} \limsup_n P(\sup_{x' \in N(n^{-r})} |Z_n(x')| \ge C \cdot (\tau_n)^{-1})$

 

모든 $x$로부터 $n^{-r}$ 반경을 펼치면 하나의 grid는 포함이 됩니다. 그래서 그 하나를 택해서 첫 번째 항을 만들었습니다. 두 번째 항은 삼각 부등식으로 쪼개고, 그 grid들 중 가장 큰 값을 선택하여 bound하였습니다.

 

First term

첫 번째 Term은 L-Lipshitz를 사용하여 bound합니다.

$\displaystyle P(\sup_{x \in [0,1], x' \in N(n^{-r})} |Z_n(x) - Z_n(x')|) \le \sum_{i=1}^n |K_h(X_i-x) - K_h(X_i-x')| + \sum_{i=1}^n |\mathbb{E}[K_h(X_i-x) - K_h(X_i-x')]|$

 

 $K_h(X_i-x) - K_h(X_i-x')$는 K가 Lipshitz이므로 $\frac{1}{h}L|(x-x')/h| \le \frac{1}{h^2}Ln^{-r}$로 bound할 수 있습니다.

 

두 항을 모두 계산하여 $\frac{2}{h}L|(x-x')/h| \le \frac{1}{h^2}Ln^{1-r}$정도로 bound할 수 있습니다.

$r$은 우리가 임의로 정할 수 있으니 후의 계산을 고려하여 $r>2$로 선택하겠습니다.

 

 

Second term

$P(\sup_{x' \in N(n^{-r})} |Z_n(x')| \ge C \cdot (\tau_n)^{-1})$은 정석적으로 전개하면 됩니다.

그런데 바로 Markov로 전개하기보다 조금 더 샤프한 bound를 필요로 합니다.

 

일단 maximal inequality로 전개합시다.

$$P \left( \sup_{x' \in N(n^{-r})} |Z_n(x')| \ge c(\tau_n)^{-1} \right) \le \sum_{x' \in N(n^{-r})} P(|Z_n(x')| \ge c(\tau_n)^{-1}) \le n^r \cdot \max_{x' \in N(n^{-r})} P(|Z_n(x')| \ge c(\tau_n)^{-1})$$

 

$$Let \quad \xi_i = K_h(X_i - x') - E[K_h(X_i - x')]$$

$$P(Z_n(x') \ge C \cdot \tau_n^{-1}) = P\left( \frac{1}{n} \sum_{i=1}^n \xi_i \ge C \cdot \frac{\sqrt{\log n}}{\sqrt{nh}} \right)$$

$$= P\left( \sqrt{\frac{n}{h}} \cdot \sqrt{\log n} \sum_{i=1}^n \xi_i \ge C \log n \right)$$

$$= P\left( e^{\sqrt{\frac{\log n}{nh}} \sum_{i=1}^n \xi_i} \ge n^C \right)$$

 

Markov inequality를 적용해줍시다.

$$\le n^{-C} E\left[ e^{\sqrt{\frac{\log n}{nh}} \sum \xi_i} \right]^n$$

$$\le n^{-C} E\left[ 1 + \sqrt{\frac{\log n}{nh}} \xi_1 + \frac{1}{2} \cdot \frac{\log n}{nh} \xi_1^2 e^{\sqrt{\frac{\log n}{nh}} \xi_1} \right]^n \quad (\because e^a \le 1 + a + \frac{a^2}{2} e^{|a|}, \text{ for } |a'| \le |a|)$$

$$= n^{-C} \left( 1 + \frac{1}{2} \frac{\log n}{nh} E[\xi_1^2] E[e^{\sqrt{\frac{\log n}{nh}} \xi_1}] \right)^n \quad (\because E[\xi_1] = E[K_h(X_i - x') - E[K_h(X_i - x')]] = 0)$$

$$\le n^{-C} \left( 1 + \frac{1}{2} \frac{\log n}{nh} C_0 e^{2 \sqrt{\frac{\log n}{nh}} \sup K} \right)^n \quad (\text{claim : } E[\xi_1^2] = \frac{C_0}{h}, \exists C_0 = \max_u p(u)) \int K^2(z) dz$$

 

$$\le n^{-C} \exp\left( n \cdot \frac{1}{2} \frac{\log n}{nh} C_0 e^{2 \sqrt{\frac{\log n}{nh}} \cdot \sup K} \right)$$

$$= n^{-C} \exp\left( \frac{\log n}{2} e^{2 \sqrt{\frac{\log n}{nh}} \cdot \sup K} \right)$$

$$\le n^{-C} \exp(\log n) \quad (\text{for sufficiently large } n, \text{ since } e^{2 \sqrt{\frac{\log n}{nh}} \sup K} \to 1)$$

$$= n^{1-C}$$

 

Proof of Claim)

$$E[\xi_1^2] = E[K_h^2] - E[K_h]^2 \le E[K_h^2] = E\left[ \frac{1}{h^2} K^2\left( \frac{X_i - x}{h} \right) \right]$$

$$= \frac{1}{h^2} \int K^2\left( \frac{u-x}{h} \right) p(u) du = \frac{1}{h} \int K^2(z) p(x + hz) dz \le \frac{1}{h} \max p(u) \int K^2(z) dz$$

 

 

반대의 부등식인 $Z_n(x') \le C \tau_n^{-1}$도 비슷하게 처리합시다.

그러면 다음이 성립합니다.

$$P \left( \sup_{x' \in N(n^{-r})} |Z_n(x')| \ge C \tau_n^{-1} \right) \le 2 \cdot n^{1+r-C} \text{ for sufficiently large } n.$$

$$\lim_{C \to \infty} \limsup_n P \left( \sup_{x' \in N(n^{-r})} |Z_n(x')| \ge C(\tau_n)^{-1} \right) = 0$$

 

7장 Local Linear Estimator

 

증명이 너무 길어 생략합니다.

 

결론

공부는 열심히 해봤는데 솔직히 많이 못했습니다. ㅋㅋㅋㅋ

그래도 제가 궁금했던 것들만 숙지해 봤습니다.

 

어떨 때 Markov를 어디까지 적용해야할지, Chernoff를 써야 할 지, 이렇게 변환하면 왜 더 좋은 bound가 나오는 건지 항상 헷갈리네요.

보통 고차 moment에서 값이 매우 작아지거나 하는 경우에 Chernoff가 더 이득입니다. Heavy tail일 경우에는 Markov가 더 좋을 수 있어요.

이 경우에는 kernel이 bound 되었기 때문에, 고차 moment도 factorial보다 는 작게 bound 할 수 있으므로 더 chernoff 방법이 잘 먹힌 것 같습니다.

 

 

끗!