데이터마이닝방법론1 과목에서 다루었던 수리통계에 대해 복습한다. 1960년대 기점으로 일반 수리통계이론(MLE, CLT, LLN) 내용과 함께, 컴퓨터의 발달로 인한 데이터 기반의 고등 수리통계이론(SLT) 내용에 대해 다룬다.
① 1960년 이전 - MLE, CLT, LLN (3가지 툴로 모든 문제 해결)
이미 알고 있는 분포에 대하여 확률변수, 확률분포 그리고 샘플링 이론을 바탕으로 분포의 파라미터(평균, 분산, etc.)를 추정하고 테스트했었다.
[Definition] 랜덤 샘플(Random Sample) {X₁,⋯,X𝑛} \[X₁,⋯,X𝑛 : {\color{Red}i.i.d\, \, \mbox{random varialbes }}from \begin{cases} & \mbox{distribution function F} \\ & \mbox{probability density function f} \end{cases} \] →i.i.d 자체는 랜덤 샘플에 대한 정의다. 또 다른 표현으로는, ⇔X₁,⋯,X𝑛 : i.i.d copies of a r.v X∽F 분포 F 를 따르는 확률 변수 X 이다. (∽F means from) ⇔X₁,⋯,X𝑛 : a random sample on X∽F 분포 F 를 따르는 X 의 랜덤 샘플이다. ⇔X₁,⋯,X𝑛 : the joint pdf of X₁,⋯,X𝑛 \(f_{X_1,⋯,X_n}(x_1,⋯,x_n)\) = \(f(x_1)⋯f(x_n)\), when \(f(x)\) is the pdf (probability distribution function) of X = 결합확률밀도함수로 각각 쪼개질 수 있다는 의미이다.
※ "확률 변수"의 우도가 아닌 "파라메터"에 대한 우도 추정이다. [Definition] 최대 우도 추정 MLE (Maximum Likelihood Estimation) X₁,⋯,X𝑛 : a random sample from a distribution having pdf f(x : θ), θ∈Ω The joint pdf of X₁,⋯,X𝑛 : \[f(x_1:θ)⋯f(x_n:θ) = \prod\limits_{i=1}^{n}f(x_i:θ) \] The likelihood function L of the random sample : \[L(θ:x_1,⋯,x_n) = \prod\limits_{i=1}^{n}f(x_i:θ), θ∈Ω \] ⇒MLE(Estimator) of θ = \( \operatorname*{arg\,max}\limits_{θ∈Ω} L(θ : x_1,⋯,x_n) \) (argmax 정의)\( \operatorname*{arg\,max}\limits_{x∈C} 𝑓(𝑥) \) = {𝑥* | 𝑓(𝑥*) ≥ 𝑓(𝑥), ∀ 𝑥 ∈ C} (argmin 정의)\( \operatorname*{arg\,min}\limits_{x∈C} 𝑓(x) \) = {𝑥* | 𝑓(𝑥*) ≤ 𝑓(𝑥), ∀ 𝑥 ∈ C}
[Definition] 중심 극한 정리 CLT (Central Limit Theorem) X₁,⋯,X𝑛 : i.i.d random variables with mean \(\mu\) and variance \(\sigma^2\) sample mean : \(\overline{X_n} = \frac{1}{n} \overset{n}\sum\limits_{i=1} (X_i)\) \[ \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) } \] 또는, \( \sqrt{n}(\overline{X_n}-\mu) \buildrel D \over → N(0, 1) \) 으로 나타낼 수 있다. ⇒샘플 사이즈가 커지면, 노멀 분포로 수렴한다. 평균과 분산 공식 (by CLT) 기대치와 배리언스에서 스칼라가 나올 때의 공식 참고, = i.i.d random variables 이기 때문에 Var(𝑥𝑖)가 나올 수가 있다.
[Definition] 통계학의 수렴 타입 (Types of convergence in statistics) X₁,⋯,X𝑛 : a collection of random variables \[\begin{cases} F_{X_n}(x) \triangleq Pr\{X_n≤x\} & \mbox{random sample} \\ F(x) = Pr\{X≤x\} & \mbox{distribution function} \end{cases} \] 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.\)
[Definition] 대수의 법칙 LLN (Law of Large Number) - 동전을 무한히 많이 던지면 앞면 1/2, 뒷면 1/2 (the frequency converges as a probability) 1) WLLN : Weak LLN X₁,⋯,X𝑛 :independent random variable with finite mean and variance (identically 할 필요는 없음) Then, \(\overline{X_n} \buildrel P \over → EX_n\) ※ 샘플 평균이 1 확률로 수렴한다. 2) SLLN : Strong LLN X₁,⋯,X𝑛 :i.i.d random variable with finite mean \(\mu\) (independent & identically) Then, \(\overline{X_n} \buildrel a.s. \over → \mu \) ※ 샘플 평균이 거의 확실하게 모집단의 평균으로 수렴한다.
② 1960년 이후 - 컴퓨터의 발달 (Data-driven advenced SLT, MLE → ERM)
대용량 데이터가 쌓이게 되고, 이를 처리할 수 있는 강력한 컴퓨팅 파워가 등장하고 있다. 이에 따라 기존의 분포가 잘 맞지 않으며, MLE 방법이 최선이 아님을 알게 되었다.
• 새로운 통계이론을 채용 SLT (Statistical Learning Theory) • Data Anaylysis → Inductive Inference - 데이터 기반의 귀납 추론을 통해 하나씩 해보면서, 1969년 VC 이론(Vapnik-Chervonenkis theory, 미국) 등장과 함께 SLT를 채용
지금까지의 수리통계에서는 분포의 Parameter(𝒩(𝜇, 𝜎), 𝑒𝑥𝑝(𝜆), etc.)를 찾았다. 이제부터는 분포를 모른다고 가정하며, 분포의 Parameter 찾기가 목적이 아니고 아예 특정한 예측 함수(Prediction Function)를 찾는 것이 목표이다. 따라서, VC 이론은 가장 기본적인 학습이론이 되겠다.
참고로 VC 이론에서는, 특정 예측 함수(classifier...)가 존재하는 공간(집합체, \(\mathbb{g}\))은 ULLN(Uniform Law of Large Number)을 만족해야 한다는 조건이 있다. ⇒Uniform LLN •‖𝑃𝑛−𝑃‖𝒢 → 0 𝑎.𝑠. Empirical 분포와 True 분포의 𝒢-Norm이 0이 된다. • 𝑅(𝑔𝑛) → 𝑅* 𝑎.𝑠. Empirical Risk가 Bayes Risk로 수렴한다.
모두 동일한 정의(ULLN 가 성립하는 공간)이다. (1)GC-class , 글리벤코 칸탈리 클래스이다. (2)VC dim (𝒢) < ∞ , 유한해야 한다. (3)Entropy of 𝒢 < ∞ , 유한해야 한다. (4)PAC-Learnable , 해야 한다.
• 지도학습 기반 분류 (Classification : Supervised Learning) [Assumption] featureSpace X output ~P 확률로 수렴 A pair of random variables (X, Y) ∈ 𝑥 x 𝑦 ~P (unknown) X: feature vector Y: label (← supervisor) Data: We observe a set of 𝑛 i.i.d pairs (X𝑖, Y𝑖) ~P, 𝑖=1,⋯,𝑛 Goal: Construct a function 𝑔 : 𝑥 → 𝑦, which predict Y from X
* Measure of goodness of 𝑔 [Definition] 손실 함수 (Loss function) The loss function 𝐿 : 𝒴 x 𝒴 → 𝑅 (real) assign a loss to every pair (𝑖, 𝑗) when class 𝑖 is classified as class 𝑗 𝒴 = {1,⋯,𝑘} : the set of class 1) Usually, 𝐿(𝑖, 𝑗) = 0 2) A good classifier 𝑔 : 𝐿(𝑦, 𝑔(𝑥)) is small ⇒ (𝑥, 𝑦) → 𝑥 를 𝑦 로 분류해주는 함수 𝑔 [Definition] 리스크 (The risk of a classifier 𝑔 in the expected loss) 𝑅(𝑔) ≜ 𝔼 𝐿(Y, 𝑔(X)) = ∫𝐿(𝑦, 𝑔(𝑥)) dF(𝑥, 𝑦) ⇒ F(𝑥, 𝑦) : (𝑥, 𝑦) 의 𝑑𝑓
• 경험적 위험 최소화 ERM (Empirical Risk Minimization) Classification : A pair (X, Y) ~F(𝑥, 𝑦) (unknown) Select a 𝑔 ∈ 𝒢∙∋∙(such that)𝑅(𝑔) = 𝔼 𝐿(Y, 𝑔(X)) is as low as possible.
[Definition] Empirical Risk 𝑅𝑛(𝑔) based on data {(X𝑖, Y𝑖)} \(\sideset{_{}^{}}{_{𝑖=1}^𝑛}{}\)(일종의 랜덤 샘플, Training data set) \[𝑅_𝑛(𝑔) = \frac{1}{𝑛} \overset{𝑛}\sum\limits_{𝑖=1} 𝐿(Y_𝑖, 𝑔(X_𝑖))\] \[ ↑ 𝑅(𝑔) = ∫𝐿(𝑦, 𝑔(𝑥)) dF(𝑥, 𝑦)\]
* 𝐿 is 0-1 loss (symmetric) 𝐿(Y, 𝑔(X)) = 𝟙{Y≠𝑔(X)} \[{𝟙_A} = \begin{cases} 1, & if\, A\, accars \\ 0, & \mbox{otherwise} \end{cases} \] \[{𝟙_A}(x) = \begin{cases} 1, & if\, x∈A \\ 0, & \mbox{otherwise} \end{cases} \] \( \mbox{⇒ 𝐿(Y, 𝑔(X)) =} \begin{cases} 1, & \mbox{Y≠𝑔(X)} \\ 0, & \mbox{otherwise} \end{cases} \) 𝑅(𝑔) = 𝔼 𝟙{Y≠𝑔(X)}⋯ 0 또는 1 = 0 x 𝑃{Y=𝑔(X)} + 1 x 𝑃{Y≠𝑔(X)} = 𝑃{Y≠𝑔(X)} ⇒ probability of misclassification ⇒ probability of error ⇒ error rate 𝑅𝑛(𝑔) = \( \frac{1}{𝑛} \overset{𝑛}\sum\limits_{𝑖=1} \) 𝟙{Y𝑖≠𝑔(X𝑖)} • ERM procedure 1) choose a model 𝒢 (the set of all possible classifier) 2) minimize 𝑅𝑛(𝑔) over 𝒢 : Learning Algorithm Produce 𝑔̂ = \( \operatorname*{arg\,min}\limits_{𝑔 ∈ 𝒢} \) 𝑅𝑛(𝑔) ⋯ empirical risk minimizer ⇒ 어떤 데이터가 주어지면, 그 데이터로 최적의 Classifier 를 찾는데, 그 방법은 ERM 이다. (V. Vapnik, 1992)
* Loss funtion ℓ : 𝒴 x 𝒴 → 𝑅 (real) ① square loss ℓ(𝑦, 𝑦') = (𝑦 - 𝑦')² ← Regression 할 때 ② 0-1 loss ℓ(𝑦, 𝑦') = 𝟙{𝑦≠𝑦'} ← Classification 할 때 ③ hinge loss ℓ(𝑦, 𝑦') = (1-𝑦𝑦')+ = max{0, 1-𝑦𝑦'} ← Support Vector Machine 할 때 ④ logistic loss ℓ(𝑦, 𝑦') = log(1+𝑒\({}^{-𝑦𝑦'}\)) ← Logistic Regression 할 때 ⑤ boosting loss ℓ(𝑦, 𝑦') = 𝑒\({}^{-𝑦𝑦'}\) ← Boosting 할 때 ⑥ 𝜀-insensitive loss ℓ(𝑦, 𝑦') = (|𝑦 - 𝑦'|-𝜀)+ = max{0, |𝑦 - 𝑦'|-𝜀} ← Support Vector Regression 할 때
• Notation in this paper * Prediction function space (Hypothesis space) ℋ = {ℎ((∙, 𝑤) : 𝑤 ∈ ℝⁿ} - Loss function space ℱ = {𝑓 = ℓ(ℎ(𝑥, 𝑤), 𝑦) : 𝑤 ∈ ℝ\({}^{𝑑}\)} 𝑓(𝑥, 𝑦) ≜ 𝑓(𝑤 : 𝑥, 𝑦) = ℓ(ℎ(𝑥, 𝑤), 𝑦) ≜ 𝑓(𝑤 : 𝜉), 𝜉=(𝑥, 𝑦) - Expected loss of ℎ ∈ ℋ 𝑅(ℎ) ≜ 𝑅(𝑤) = 𝔼 ℓ(ℎ(𝑥; 𝑤), 𝑦) ← Risk (= Expected Risk, True Risk) - Empirical Risk 𝑅𝑛(ℎ) ≜ 𝑅𝑛(𝑤) = \(\frac{1}{n} \overset{n}\sum\limits_{i=1}\)ℓ(ℎ(𝑥\({}^𝑖\); 𝑤), 𝑦\({}_𝑖\)) based on training data set {(𝑥\({}^𝑖\), 𝑦\({}_𝑖\))} \(\sideset{_{}^{}}{_{𝑖=1}^𝑛}{}\)
Example. 기계학습 기초 (지도학습 중심)
:: (X𝑖, Y𝑖) : 𝑖.𝑖.𝑑 copies of (X, Y) ∽𝐹 X ∈ 𝒳 (feature space, input space) Y ∈ 𝒴 (set of class, output space) classification 패턴을 찾거나, regression 모델을 찾는다.
1. 분류 (Classification) : 𝒴 = {0, 1,⋯,𝑘-1} ⋯ 𝑘-class 0-1 loss : probability of the misclassification \[𝑅_𝑛(𝑔) = \frac{1}{𝑛} \overset{𝑛}\sum\limits_{𝑖=1} \mbox{𝟙{Y𝑖 ≠ 𝑔(X𝑖)}}\]
3. 분포 추정 (Density Estimation) (minimize cross entropy ℋ(☆, △)) • data {𝑥¹, ⋯,𝑥ⁿ} : 비 지도학습(unsupervised learning) - No 𝑌𝑖 • true distribution function : 𝑓(𝑥) || probability density function : 𝑓(𝑥) • we want to estimate 𝑝𝑑𝑓 𝑓(𝑥) of X∽F(𝑥) • loss function : 𝐿(𝑔) = -log 𝑔 𝑅(𝑔) = \(𝔼 [-log(X)] \) = \( -\int log(𝑥)\, dF(𝑥) \) = \( -\int 𝑓(𝑥)\, log\, 𝑔(𝑥)\, dx \) = \(𝔼_{X∽𝑓(𝑥)} [log\, \frac{1}{𝑔(𝑥)}] \) : Cross entropy ℋ(𝑓, 𝑔) 𝑅𝑛(𝑔) = \( \frac{1}{𝑛} \overset{𝑛}\sum\limits_{𝑖=1} log\, \frac{1}{𝑔(X^𝑖)} \) • ERM : \( \operatorname*{min}\limits_{𝑔 ∈ 𝒢} \) \( \frac{1}{𝑛} \overset{𝑛}\sum\limits_{𝑖=1} log\, \frac{1}{𝑔(X^𝑖)} \) ⟺ \( \operatorname*{max}\limits_{𝑔 ∈ 𝒢} \) \(log\, \overset{n}\prod\limits_{i=1} 𝑔(X^𝑖)\) ⋯ MLE와 일치 (min -𝑓 = -max 𝑓 ⋯ ERM도 결국 MLE와 동일)
[Definition] 1) Entropy ℋ(☆) = \( \sum ☆\, log\, \frac{1}{☆} \) 2) Cross Entropy ℋ(☆, △) = \( \sum ☆\, log\, \frac{1}{△} \) 3) kullback-leibler divergence 𝒟𝐾𝐿(☆||△) = \( \sum ☆\, log\, \frac{☆}{△} \) ⇒ ℋ(☆, △) = 𝒟𝐾𝐿(☆||△) + ℋ(☆) ※ 𝒟𝐾𝐿(☆||△) 는 두 분모 ☆과 △가 얼마나 일치하는 가의 측도. ☆과 △의 거리로 생각할 수 있다. 따라서, 𝒟𝐾𝐿(☆||△)=0 가 되면 ☆=△ 가 성립. ※ ☆ : true distribution △ : estimation △* = \( \operatorname*{arg\,min}\limits_{△} \) 𝒟𝐾𝐿(☆||△) = \( \operatorname*{arg\,min}\limits_{△} \) ℋ(☆, △) 즉, 주어진 ☆ 에 대하여 Cross Entropy 의 최소화 ⟺ 𝒟𝐾𝐿의 최소화
• Cross Entropy : ℋ(☆, △) - 주로 분포의 추정에 사용 - ☆ : true distribution 실제 분포를 모르기 때문에 이 경우에는, empirical distribution function 또는 ground truth (실측 자료)라고 부른다. ⇒ true 를 모르기 때문에 sample 을 통해 추정 - △ : model of distribution function (parameter 로 정의) - Objective : 최적 △ 를 구한다. 즉, sample 을 통하여 분포의 parameter 를 추정 △* = \( \operatorname*{arg\,min}\limits_{△} \) 𝒟𝐾𝐿(☆||△) = \( \operatorname*{arg\,min}\limits_{△} \) ℋ(☆, △) = \( \operatorname*{arg\,min}\limits_{△} \) \( \underbrace{\sum ☆\, log\, \frac{1}{△}}_{\color{Red}{cross\, entropy\, loss}} \)
• Example of the Cross Entropy: 𝒴 = {0, 1} ⋯ binary-class 앞의 로지스틱 방법과 유사하지만 접근 방법이 다르다. - Model : 𝑝̂(𝑦|𝑥) = \( {𝑝̂(1|𝑥^𝑖)}^{𝑦} {𝑝̂(0|𝑥^𝑖)}^{1-𝑦} \) Estimation of posterior distribution function of 𝑦 given 𝑥
- CE loss for the training data set {(𝑥\({}^𝑖\), 𝑦\({}_𝑖\))} \(\sideset{_{}^{}}{_{𝑖=1}^𝑛}{}\) \[ 𝑦̂_𝑖 = {𝜎(𝑤^𝑇𝑥^𝑖 +𝑏)} \] \[ 𝐿_𝑖 = {-[𝑦_𝑖\, log\, 𝑦̂_𝑖 + (1-𝑦_𝑖)\, log\, (1-𝑦̂_𝑖)]} \] Total CE loss : \(𝐿 = \frac{1}{𝑛} \overset{𝑛}\sum\limits_{𝑖=1}\, 𝐿_𝑖\)
