[3주차] Empirical Process 1 (데이터 기반 추정)

 Empirical Process 1 (경험 과정)

분포를 모를 때, 샘플 데이터 \(X_1\),... ,\(X_n\) 에 의존한 추정 기법을 다룬다.

앞의 1~2주차는 머신러닝을 위한 기초 수리통계 이론이며, 실제 머신러닝은 Data-Driven(고등 수리통계) 이론을 따른다.

※ 일반 수리통계(Classical mathematics statistics) 이론은 분포가 중요하며 분포의 parameter 추정이 주요 목표이다.
   · e.g.) 정규분포 \(N(\mu\,,\sigma^2)\)
1. 확률변수(random variable)
   · X : Ω → R
2. 조건확률/기대치(conditional probability and expectation)
3. 확률변수의 분포(r.v. of distribution)
   · 이항(Binomial), 포아송(Poisson), 감마(Gamma), 카이제곱(Chi-square), 정규(Normal) 분포
4. 샘플링 이론(sampling)
   · function of random variable 의 분포
5. 추정(estimation)
6. 가설검증 및 평가(Testing)

※ 하지만, 고등 수리통계(Advenced mathematics statistics) 이론에서는 분포가 중요하지 않다.
→ 분포를 모른다고 가정하고 추정(Estimation)을 시행 => Statistical Learning Theory(SLT)

※ 분포 - 정규 분포(Normal Distribution)와 이항 분포(Binomial Distribution)에 대하여..
- 정규 분포(Normal Distribution) 또는 가우시안 분포(Gaussian Distribution)
  → 연속확률분포, 완벽한 좌우대칭
   · \(y = \frac{1}{\sigma \sqrt{2\pi}} e^{-\frac{(x-m)^2}{2\sigma^2}}\)
   · 정규 분포의 모수는 2개이다. (평균: \(\mu\), 분산: \(\sigma\))
   → 평균으로부터 어느정도 떨어져 있는가?
- 이항 분포(Binomial Distribution) ... 베르누이 분포(Bernoulli Distribution)
  → 이산확률분포, n 번의 복원추출로 실험
   · \(p(k) = {n \choose k}p^k(1-p)^{n-k}, {n \choose k} = {_{n}C_k} = \frac{n!}{k! (n-k)!} \)
   · 이항 분포의 모수는 2개이다. (횟수: \(n\), 확률: \(p\))
   → 베르누이 분포는 모수가 p 1개 뿐이며, n 번의 베르누이 시행에 대한 확률 분포가 이항 분포이다.

 

 A. Conditional probabilities and expectations (조건확률과 기대치)

 · Review - 복습하기

※ 조건 확률(conditional probability)
- \(Pr\{A|B\} = \frac{Pr\{A \cap B\}}{Pr\{B\}},\,\, Pr\{B\} \gt 0,\)
※ 조건 분포함수(conditional distribution function)
   · \(F_{X|Y}(x|y) = \frac{Pr\{X≤x|Y=y\}}{Pr\{Y=y\}},\,\, Pr\{Y=y\} \gt 0,\)
   → X 가 이산일 때, 조건 분포함수(Y=y)
   · \(F_{X|Y}(x|y) = \frac{\int_{-∞}^x {\color{Red}f_{X, Y}(\xi, y)}\, d\xi}{{\color{Red}f_Y(y)}},\,\, f_Y(y) \gt 0,\)
   → X 가 연속일 때, 조건 분포함수(Y=y)
   · 이때, 기본적으로 분포 함수의 성질을 만족해야 한다. \(F_{X|Y}(∞|y)=1\), \(F_{X|Y}(-∞|y)=0\) ...
※ 결합 분포함수(joint distribution function)
- \(F(x,y) = Pr\{X≤x, Y≤y\} = \int_{-∞}^y F_{X|Y}(x|\eta)\,dF_Y(\eta)\)
   · \({\color{Red}F(x)} = Pr\{X≤x\} = Pr\{X≤x, Y≤{\color{Red}∞}\} = \int_{-∞}^{\color{Red}∞} F_{X|Y}(x|\eta)\,dF_Y(\eta)\)
   · y→∞ Then, The law of total probability.

   · When Y is discrete ... Then, \(Pr\{X≤x\} = \sum\limits_{y} Pr\{X≤x, Y=y\}\, {\color{Red}Pr\{Y=y\}}\)
   · When Y is continuous ... Then, \(Pr\{X≤x\} = \int_{-∞}^{∞} F_{X|Y}(x|\eta)\,{\color{Red}f_Y(\eta)\,dy}\)
※ 조건 기대치(conditional expectation)
- \(E[g(x)|Y=y]\) = \(\int_x g(x)\, dF_{X|Y}(x|y)\)
   · When X and Y are discrete ... Then, \(E[g(x)|Y=y]\) = \(\sum\limits_{x} g(x) Pr\{X=x|Y=y\}\) = \(\sum\limits_{x} g(x) f_{X|Y}(x|y)\)
   · When X and Y are continuous ... Then, \(E[g(x)|Y=y]\) = \(\int_x g(x)\, f_{X|Y}(x|y)\, dx\)
   · 이때, 조건으로는 g(X)는 적분이 존재해야 한다. \(E[|g(X)|] \lt ∞\)
   · 또한, function h 에 바운드 되어있는 조건 기대치를 구할 때 h(Y) 값을 주어지면 상수처럼 밖으로 나올 수 있다.
   · \(E[g(X)\, {\color{Red}h(Y)}]\) = \(\int E[g(X)|Y=y]\, {\color{Red}h(y)}\, dF_Y(y)\) = \(E\{E[g(X)|Y]\, {\color{Red}h(Y)}\}\) ... 증명 참조
   · h(y)≡1 Then, The law of total expectation. (항등식)
   · \(E[g(X)]\) = \(\int E[g(X)|Y=y]\, dF_Y(y)\) = \(EE[g(X)|Y] \)
   · When Y is discrete ... Then, \(E[g(X)] = \sum\limits_{y} E[g(X)|Y=y]\, Pr\{Y=y\}\)
   · When Y is continuous ... Then, \(E[g(X)] = \int E[g(X)|Y=y]\, f_Y(y)\, dy\)
   · 조건 확률은 조건 기대치의 특별한 케이스이다. \(P(B|X) = E[\mathbb{1}_{B}|X]\)

자주 사용되는 조건 기대치

 

Example: Roll a die until we get a 6. Let Y be the total number of rolls and X the number of 1's we get. We compute E[X|Y=y].

예제: 숫자 6이 나올때까지 주사위를 던진다. 그때 숫자 1이 나올 횟수의 평균은?
Y: 총 굴리는 횟수, X: 숫자 1이 나올 횟수 (Binomial Distribution)
· The event Y=y means that there were y-1 rolls that were not a 6 and then the y-th roll was a 6.
· Given this event, \(X \sim B(y-1, \frac{1}{5}) \implies\) E[X|Y=y] = np = \(\frac{1}{5}(y-1)\)
  → 한번 시행에서 1이 나올 확률(p) = 1/5 (If 6, Stop), 시행(n): y-1 ... E(X) = np
  ※ \(y=Y(w)\), \(E(X|Y) = \frac{1}{5}(Y-1)\) ... random variable

[Summary - 요약]

 · 확률 공간(probability space)  - \((\Omega, \mathcal{F}, P)\)

  1) 확률변수(random variable)

  -. random variable X 는 \((\Omega, \mathcal{F})\) → \((R, B)\)인 함수(real-valued function)이다.

  2) 분포함수(distribution function)

  -. distribution function of a random variable X 는 \(F(x) = Pr\{X≤x\} = P(-∞, x)\)이다.

  3) 기대치(expectation) - \(E[☆]\) = \(\int_{☆}☆\, dF(☆) \)

  -. \(E(X) = \int_\Omega X\, dP = \int_\Omega X(w)\, P(dw) = \int_\Omega X(w)\, dP(w) = \int_{-∞}^{∞} x\, dF(x)\)

 · 조건 분포함수(conditional distribution function) 

  -. \(F({x|y}) = Pr\{X≤x|Y=y\} = \begin{cases} \frac{Pr\{X≤x|Y=y\}}{Pr\{Y=y\}} \\ \frac{\int_{-∞}^x f(\xi, y)\, d\xi}{f_Y(y)} \end{cases}\)

 · 조건 기대치(conditional expectation) 

  -. \(E[☆|△]\) = \(\int_{☆}☆\, dF(☆|△) \)

 · 전체 확률의 법칙(law of total probability) 

  -. \(P(☆)\) = \(EP(☆|△)\) = \(\int_{△}P(☆|△)\, dF(△)\)

 · 총 기대치의 법칙(law of total expectation) 

  -. \(E(☆)\) = \(EE[☆|△]\) = \(\int_{△}E[☆|△]\, dF(△)\)

 

 B. Empirical Process (경험 과정)

본론으로 돌아오면, 경험과정(Empirical Process)은 머신러닝의 기초이며 실험(Random Sample)에 의존한 방식이다. 향후 Advenced 수리통계의 기본이 될것이다.

※ 랜덤 샘플(random sample)
   · Based on a random sample from (unknown) distribution fuction
   · Define: random sample {\(X_1\),... ,\(X_n\)}
   ※ i.i.d: independent and identically distributed
   → \(X_1\),... ,\(X_n\) : i.i.d random variables \(from \begin{cases} F & \mbox{distribution} \\ f & \mbox{probability density} \end{cases} \)
   \(\Leftrightarrow \) \(X_1\),... ,\(X_n\) : i.i.d copies of a random variable X from F
   \(\Leftrightarrow \) \(X_1\),... ,\(X_n\) : a random sample on X from F
   \(\Leftrightarrow \) The joint pdf of \(X_1\),... ,\(X_n\) can be divided into each pdf of X.
   \[f_{X_1,...,X_n}(x_1,...,x_n) = f(x_1) \cdots f(x_n) \]
   · Define: sample mean \(\overline{X_n}\), sample variance \({S_n^2}\)
   \[\begin{cases} · \overline{X_n} = \frac{1}{n} \overset{n}\sum\limits_{i=1} X_i & \mbox{mean} \\ · {S_n^2} = \frac{1}{n-1} \overset{n}\sum\limits_{i=1} (X_i - \overline{X_n})^2 & \mbox{variance} \end{cases} \]
   Assume, \(E(X)\) = \(\mu\), \(Var(X)\) = \(\sigma^2\)
   \[Var(X) \triangleq E(X-E(X))^2 = EX^2 - (EX)^2 \]
   Then,
   -. \(E(\overline{X_n})\) = \(E(\frac{1}{n} \overset{n}\sum\limits_{i=1} X_i) = {\color{Red}\frac{1}{n}} E \overset{n}\sum\limits_{i=1} X_i = \frac{1}{n} \overset{n}\sum\limits_{i=1} \underbrace{EX_i}_{\mu} = \mu \)
   -. \(Var(\overline{X_n})\) = \(Var(\frac{1}{n} \sum X_i) = {\color{Red}\frac{1}{n^2}} \overset{n}\sum\limits_{i=1} Var(X_i) = \frac{\sigma^2}{n} \) ※ Var(Constant)→Constant²
   -. \(E({S_n^2})\) = \(\frac{1}{n-1}\{E\sum(X_i-\mu)^2 - nE(\overline{X_n}-\mu)^2 \} = \frac{1}{n-1}(n\sigma^2-n\frac{\sigma^2}{n}) = \sigma^2 \)
   ∴ \(E[\overline{X_n}]\) = \(\mu\), \(E[{S_n^2}]\) = \(\sigma^2\) ... unbiased estimation of \(\mu\), \(\sigma^2\)
   ※ 불편파추정(unbiased estimation): 추정량의 기댓값과 모수의 실제값의 차이가 0(편파성이 없는)인 추정치

※ 확률변수의 수렴(Convergence)은 Sampling 이론에서 필요한 개념으로, 3 가지 타입을 살펴보자.
   · Define: Types of convergence in statistics
   · {\(X_1\),... ,\(X_n\), \(X\)} is a collection of random variables.
   \[F_{X_n}(x) = Pr\{X_n≤x\}\, , F(x) = Pr\{X≤x\}\, ←df \]
1. 분포로서 수렴(convergence in distribution)
   \[ \lim_{n \to \infty} F_{X_n}(x) = F(x)\, \cdots \forall x \]
   · 가장 약한 수렴, denoted by: \(X_n \buildrel D \over → X,\, X_n \overbrace{\rightsquigarrow}^{weak} X,\, X_n \Rightarrow X\)
2. 확률로서 수렴(convergence in probability)
   \[ \lim_{n \to \infty} P\{|X_n-X|> \varepsilon \} = 0\]
   · denoted by: \(X_n \buildrel P \over → X\)
3. 확률 1 로서 거의 확실한 수렴(convergence with probability 1 or convergence almost surely (a.s.))
   \[ P\{\lim_{n \to \infty} X_n=X \} = 1\]
   · 가장 강한 수렴, denoted by: \(X_n \buildrel a.s. \over → X,\, X_n → X\, a.s.\)

※ 1, 2, 3 번으로 내려갈수록 강력한 수렴.
→ 3 번 거의 확실한 수렴은 확률변수 자체가 수렴하게 되는 경우이다.

※ 대수의법칙(Law of Large Number)
- 샘플사이즈 n이 커지면, 모집단의 파라메터로 수렴한다.
※ 약한 대수의법칙(Weak LLN) 증명
   → \(X_1\),... ,\(X_n\) : independent random variable with finite mean and variance (identically 할 필요는 없음)
   Then, \(\overline{X_n} \buildrel P \over → EX_n\) ※ 샘플 평균이 1 확률로 수렴한다.
   · 체비셰프 부등식에 의해 아래와 같이 증명 가능하다.
\[ \eqalign{ P\{|\overline{X_n}-E\overline{X_n}|> \varepsilon\} & ≤ \frac{E(\overline{X_n}-EX_n)^2}{\varepsilon^2} \\ &= \frac{Var(\overline{X_n})}{\varepsilon^2} = \frac{\sum \sigma_i^2}{n^2\, \varepsilon^2} < ∞ } \]
   · 참고: 체비셰프 부등식(Chebyshev's lnequality)
   · \(Pr\{X>a\} ≤ \frac{E \phi(X)}{\phi(a)} \)
   · \(\phi = R → [0, ∞]\) 증가 함수를 의미, 양 변에 극한을 취해 WLLN 증명하였다.
※ 강한 대수의법칙(Strong LLN) 증명
   → \(X_1\),... ,\(X_n\) : i.i.d random variable with finite mean \(\mu\) (independent & identically)
   Then, \(\overline{X_n} \buildrel a.s. \over → \mu \) ※ 샘플 평균이 거의 확실하게 모집단의 평균으로 수렴한다.
※ 중심 극한 정리(central limit theorem)
- 샘플사이즈 n이 커지면, 모두 표준 정규분포로 수렴한다.
   → \(X_1\),... ,\(X_n\) : i.i.d random variable with mean \(\mu\) and variance \(\sigma^2\) (\(\mu\), \(\sigma^2\) 를 가지는 모집단 추출, 분포는 모름)
   Then, \(\sqrt{n}(\overline{X_n}-\mu) \buildrel D \over → N(0, \sigma^2)\) ※ \(\sigma^2\) 경우.. 수정.
   Then, \(\sqrt{n}(\frac{\overline{X_n}-\mu}{\sigma}) \buildrel D \over → N(0, 1)\) ※ 샘플사이즈가 커지고 표준화하면 표준 정규분포로 수렴한다.
   · 샘플 평균이 정규화를 통해 아래와 같이 Standard Normal Distribution 으로 수렴한다.
\[ \eqalign{ \frac{\overline{X_n}-E\overline{X_n}}{\sqrt{Var\, \overline{X_n}}} = \frac{\overline{X_n}-\mu}{\frac{\sigma}{\sqrt{n}}} & = \sqrt{n}(\frac{\overline{X_n}-\mu}{\sigma}) \\ & \buildrel D \over → N(0, 1) } \]
   · 샘플사이즈만 커지면 노멀분포로 추정하는것만으로도 충분하였다.
   → 샘플만 잘 맞아도 적당한 양(경우에 따라 20 개도 큰 것이 됨)이면 Standard Normal Distribution 추정에 맞았다.
   · 빅데이터로 추정해보니 샘플사이즈가 커져도 노멀분포에 맞지 않았다.
   → 전통적인 통계 이론에서는 LLN, CLT 추정이 충분하였지만, 현대 머신러닝에 대한 새로운 이론이 필요하게 되었다.

※ 경험 과정(empirical process)

- 현대 머신러닝에 대한 새로운 이론으로써, 모집단에서 뽑은 랜덤 샘플을 이용한 데이터 기반의 추정이다.

 

먼저, 경험적 분포 함수(empirical distribution function)과 경험적 척도(empirical measure) 개념을 이해하고 과정을 살펴보자. 앞으로 나오는 n은 모집단에서 뽑은 샘플의 갯수를 의미한다.

· Define: random sample {\(X_1\),... ,\(X_n\)} : i.i.d random variables on \((\Omega, \mathcal{F}, P)\)
   ※ n개의 랜덤 샘플에 대한 분포함수를 정의

\[F(x) = P\{X≤x\}\]

1) 경험적 분포 함수(empirical distribution function) : \(F_n\)

- 경험적 분포 함수는 샘플사이즈 n으로부터 만든 함수이다.

\[ \eqalign{ F_n(x) & = \frac{\mbox{num(} \# \mbox{) of } X_i ≤ x}{n} \\ &= \frac{1}{n} \overset{n}\sum\limits_{i=1} \mathbb{1}\{X_i≤x\} } \]

* 여기서 잠깐 \(\mathbb{1}\)(Indicator) 에 대해서 알아보자.

· Define: Indicator \(\mathbb{1}\){\(X_i≤x\)} : i.i.d random variables with \(E\)\(\mathbb{1}\){\(X_i≤x\)} = \(Pr\{X_i≤x\}\) = \(F(x)\)
   ※ 1 또는 0 인 베르누이(Bernoulli) 법칙을 따른다.

\[\mathbb{1}\{X_i≤x\} = \begin{cases} 1, & X_i≤x \\ 0, & \mbox{otherwise} \end{cases} \]

이 인디케이터의 평균(Expectation)을 구해보면, random variables : 0 or 1 임으로 확률 P 와 같아진다.

\[ \eqalign{ E \underbrace{\mathbb{1}\{X_i≤x\}}_{0/1} & = \mbox{1 * }Pr\{X_i≤x\} \\ &\mbox{+ 0 * }Pr\{X_i≤x\} } \]

이 인디케이터의 Variance 도 구할 수 있다.

\[ Var \underbrace{\mathbb{1}\{X_i≤x\}}_{\sim Bern(F(x))} = F(x)\, [1-F(x)] \]

  · 참고: 베르누이 확률분포(X~Bern(P))
  → \(Var(X) = P(1-P)\,,\,E(X) = P \)

따라서 경험적 분포 함수는 인디케이터 함수로 계산이 되고, 전체 n개 중에 x 보다 작은것이 몇 개 뽑혔는지 찾는다.

\[ \eqalign{ E \underbrace{\mathbb{1}\{X_i≤x\}}_{0/1} & = \mbox{1 * }Pr\{X_i≤x\} \\ &\mbox{+ 0 * }Pr\{X_i≤x\} } \]

 

By SLLN(강한 대수의법칙에 의해서), \(F_n(x) → F(x)\, a.s.\, \forall x \)

※ ULLN 또는 글리벤코-칸텔리 정리(glivenko-cantelli theorem, 1933)
By ULLN(uniformal of LLN), VC-Theory 및 empirical process 의 기본적인 정리.
\[ \|F_n-F\|_∞ \triangleq \sup_{-∞\lt x \lt ∞} |F_n(x)-F(x)| → 0\, a.s.\]

 

2) 경험적 척도(empirical measure) : \(P_n\)

- (based on sample) 경험적 척도는 a sequance of random variables 특정 실현에서 발생하는 랜덤 척도이다.

- \(A\) 가 일어날 확률 \(P_n(A)\)는 다음과 같고, n개 뽑아서 사건 \(A\) 가 얼마나 일어나는지 확인한다.

\[ \eqalign{ P_n(A) & = \frac{\mbox{num(} \# \mbox{) of } X_i \in A}{n} \\ &= \frac{1}{n} \overset{n}\sum\limits_{i=1} \delta_{X_i} } \]

* 여기서 잠깐 \(\delta\)(dirac delta function) 에 대해서 알아보자.

\(\delta_X\) : Dirac measure : \(\delta_X(A) = \begin{cases} 1, & X_i \in A \\ 0, & \mbox{otherwise} \end{cases} \)

\(\int g\, d\delta_X = g(x) = \delta_X(g) \)

· Define: a given function \(g \in \mathbb{g}\)
   ※ \(\mathbb{g}\) : 어떠한 함수 집합 또는 a collection of measurable function \(\Omega → R \).

\[\begin{cases} P_ng \triangleq \int g\, dP_n = \frac{1}{n} \overset{n}\sum\limits_{i=1} {\color{Red}g(X_i)}\, \cdots\, (1) \\ Pg \triangleq \int g\, dP = E{\color{Red}g(X)}\, \cdots\, (2) \end{cases} \]

 

→ \(X_1\),... ,\(X_n\) : i.i.d random variables on \((\Omega, \mathcal{F}, P)\)

- random variable 으로부터 샘플링한 랜덤 샘플도 역시 random variable 이다. (확률공간으로부터 샘플링)

- 이 랜덤 샘플을 가지고 확률 \(P\) 를 추정(estimation) 한 것이 \(P_ng\)가 된다.

- (1) empirical measure \(P_n\) 에 함수 \(g\) 가 들어가면, 그냥 평균이 아니고 \(g(x)\) 를 넣은 "\(g(x)\) 에 대한 평균"이 되겠다.

- (2) scala measure \(P\) 에 함수 \(g\) 가 들어가면, original \(g(x)\)에 대한 모집단의 평균이 되겠다.

- 이때, 평균 E \(P_ng\) 가 모집단의 평균 E \(Pg\) 와 같아지면 \(P_ng\)를 unbiased estimator 라고 부른다.

  ※ Notice that \(g(x_i)\), 이 자체가 random variable 이다.
  \(g(x_i)\): i.i.d random variables with
  mean \(Eg(x_i) = Pg \) and,
  var \(g(x_i) = P(g-Pg)^2 = Pg^2-{(Pg)}^2 \)

 

By SLLN(강한 대수의법칙에 의해서), \(P_ng → Pg\, a.s.\, \forall g \in \mathbb{g} \)
... 모든 샘플 평균은 모든 g 에 대해서 almost surely 모집단의 평균으로 간다.

※ 샘플 n개를 뽑으면서 사건에 들어가는지 여부를 확인한다.
By ULLN(uniformal of LLN), 모든 샘플 평균은 함수에 관계없이 almost surely 모집단의 평균으로 간다.
\[ \|P_n-P\|_\mathbb{g} \triangleq \sup_{g \in \mathbb{g}} |P_ng-Pg| → 0\, a.s.\]

 

3) 경험 과정(empirical process) : \(G_n\)

- empirical process indexed by a set of function's \(\mathbb{g}\)

- 여기서부터는 샘플사이즈 n 이 중요한 것이 아니고, 함수의 집합 \(\mathbb{g}\) 가 중요한 인덱스가 된다.

* 여기서 잠깐 과정(process) 에 대해서 알아보자.

- process : a sequance of random variables indexed by type.

{\(X_1\),... ,\(X_n\)} : process 라고 부른다.

{\(X_t\) : \(t \in \mathbb{T}\)} : process 이런 형태도 프로세스이다.

· Define: The process {\(G_n\) : \(g \in \mathbb{g}\)} is called \(\mathbb{g}\)-indexed empirical process.
   ※ empirical process : 타입이 아니고 어떠한 함수에 대한 인덱스를 가지는 프로세스.

\[ \eqalign{ G_n & = \sqrt{n}(P_n-P) \\ &= \frac{\overset{n}\sum\limits_{i=1} \delta_{X_i}-P}{\sqrt{n}} } \]

 

By CLT(극한중심정리에 의해서), \(G_ng \buildrel D \over → N(0, P{(g-Pg)}^2)\, \mbox{for a fixed }g \)

※ emprical process 에서는 항상 uniformal 형태를 찾는다.
By UCLT(uniformal of CLT), 여러가지 응용 분야에서는 UCLT 까지 커버해야 하지만, 여기서는 ULLN 만으로 충분하다.
\[ G_n \overbrace{\rightsquigarrow}^{weak} G(Brownian\, Bridge) \cdots \mbox{brownian motion} \]