[Data processing]Bootstrapping /Compiler/ Statistic/ ML 관점의 정리
KoTiv
2022. 1. 21. 16:08
반응형
SMALL
Introduce : What's the bootstrapping
Density Forecasting for Long-Term Peak Electricity Demand 및 Constructing Probabilistic Load Forecast From Multiple Point Forecast: A Bootstrap Based Approach 의 논문을 보면 Bootstrapping 기법이 소개 되었다. 신호처리 관점에서 Sampling을 학부및 대학원과정에서 다루어 보았지만 다시한번 복귀하는 차원으로 검색을 해보았다.
BootStarp은 일반적으로 Random sampling with replacement에 기반한 통계 검증과 추정을 의미한다. 특정 통계량(추정량)의 분포를 구하기 위해, 관측된 Random Sample에서 Resampling을 수행하는 Case resampling기법이다.
Bootstrapping method를 검색하는 과정에서 각 분야의 관점별로 bootstrap이 전하는 의미가 조금씩 다른걸 확인하였다. Bootstrapping은 Compiler, Statics, Machine learning에서 조금씩 다른 의미로 사용하고 있고. 이에따라 간단한 예시와 함께 Bootstrap에 대하여 정리한후 Statics와 ML에서 적용 사례를 이야기하며 더 상세하게 알아보고자 한다 .
i.i.D what's ?
i i D 란 무었인가 . 기초 통계학을 보면 Independent and identically distribution 즉 독립 항등 분포라고한다.
의미 그대로 가져오면 Random Variable variabliity가 1. independent하고 identically distribution을 가지면 iid라고 정의하게 된다.
1.) independent
독립 이라는 것은 각 각의 사건이 다른 사건에 영향을 주지않는 것을 의미한다.
2) identically distribution.
같은 확률분포를 가진다는 건 주사위 굴리기, 동전 던지기처럼 동일한 확률분포를 가지는 걸 의미한다.
Bootstrap Sampling 사용 이유( Resampling ) - Compiler에는 해당하지 않는 내용이다.
Bootstrap Sampling을 사용하는 이유는 원시 데이터의 데이터적 제한으로 인해 Sample data SET 의 수가 1이라는 한계점이 존재한다 . 그렇기 때문에 Sample data set을 n개의 Data set으로 늘려주는 효과를 얻기위해 Bootstrap sampling을 사용하게 된다 . 결론적으로 Bootstrap을 통하여 Data의 Variance를 잘 근사 할 수 있는 결과를 얻을수 있게 된다.
1. Compiler - Bootstrapping
컴파일러에서 Bootstrapping은 컴파일 하고자 하는 프로그래밍의 언어로 작성되는 과정이라고 소개하고있다.
컴파일러에서 Bootstrapping 적용은 셀프 호스팅 컴파일로러 이어지게 된다.
what's self hosting compiler
self-hosting 은 동일한 프로그램의 새 버전을 생성하는 tool-chain 혹은 OS의 일부로 프로그램을 사용하는 것을 의미한다.
즉 자신의 Source Code를 컴파일할 수 있는 컴파일러로 Kernel, Assemblers, Command line interpreters과 같은 소프트웨어의 일종으로 이해하면 될것같다.
컴파일러를 부트스트래핑 하는 것은 다음과 같은 장점들을 가진다
컴파일러 부트스트래핑은 컴파일될 언어에 대한 중대한 테스트이다.
컴파일러 개발자들은 컴파일될 언어만 알면 된다.
컴파일러 개발이 컴파일될 해당 고급 언어로 이루어질 수 있다.
해당 컴파일러의 백엔드 개선이 범용 목적 프로그램 뿐만 아니라 해당 컴파일러 자신 또한 개선한다.
컴파일러가 언어 자신의 목적코드를 재생산해 내어야 하므로 컴파일러 부트스트래핑은 포괄적인 일관성 검사이다
통계학에서 Bootstrapping은 가설검증(Test) 또는 Metric을 계산하기 전 Random sampling과 Replacement를 적용하는 방법이다. [ 크게 Resampling method 로 바라보면 된다. ]
Bootstrapping은 Ramdom sampling method를 하여 대부분의 Sampling Distribution을 추정할수 있기 때문에 Bias, Variance, confidence intervals, prediction error ,등의 정확도 측정을 Sampling Estimated에 할당하게 된다.
근사 분포에 대한 한가지 표준 선택은 Observed data 의 empirical distrubutuin function 이다.
뿐만아니라 Observation data set은 독립적이고 균일하게 분포된 Population에서 추출된 Sample이라는 가정이 있을때 . Observation data를 기반으로 새로운 Sample을 Resampling하여 다 양한 수의 Data를 획득할 수 있게 된다 .
Bootstraping baisc Idea approch
1. Sample Data에서 Population Data의 추론은 Sample data를 다시 ReSampling 하여 Resampling data에 기반하여 Sample data에 대한 추론을 수행하여 모델링 하고자 하는 전제가 깔려 있다 .
2. Population set에 대하여 알수 없으므로 sample data에 기반한 통계의 실제 오류를 알수 없다.
3. 따라서 Resampling data에서 True Sample의 추론을 통하여 quality를 측정할 수 있게 된다 .
즉 Bootstrapping은 Origin data가 주어졌을때 실제 확률분포 J의 추론과
재샘플링된 데이터가 주어졌을때 경험적 분포 Ĵ 의 추론이 유사한 것으로 처리하여 작동하게 된다.
재샘플링된 데이터를 사용하여 Ĵ에 대한 추론의 정확도는 Ĵ를 알고 있기 때문에 정확도를 평가할 수 있게 되고 .
Ĵ가 J의 근거에 맞는 근사값이라면 J에 대한 Quality역시 추론될 수 있다는 가정이다 .
예를 들면 어떤 전체 데이터의 단일 통계치를 얻고싶다면 전체의 평균을 구하면 된다.
그런데 만약 평균의 confidence interval을 구한다면 데이터를 수집했던확률변수의 정확한 분포를 모르는 경우, 측정된 통계치의 신뢰도를 가늠할 방법이 없다.
이 때, bootstrapping을 사용한다. 측정된 n개의 데이터 중에서 중복을 허용하여 m개를 뽑고, 그들의 평균을 구하기를 여러 번 반복한다.
그럼 평균의 분포를 구할 수 있게 되고, 이로부터 95% 확률로 sample mean이 (a, b) 사이의 구간에 위치한다든가 하는 것을 언급할 수 있다.
이렇게 원래의 분포를 모르는 경우 외에도,측정된 샘플이 부족한 경우에도 사용할 수 있다고 한다.
Bootstrapping 의 장/단점
1. 장점
1.1. percentile points, proportions, odds ratio, and correlation coefficients와 같은 distribution의 복잡한 추정에 대해 Standard Error 및 confidence interval의 추정치를 도출하는 가장 간단한 방법이라 단순하다는 장점이 존재한다.
1.2. 단순하지만 복잡한 Sampling 설계에 적용 가능할 수 있다.
즉 Bootstrapping method는 Sampling 결과의 Stability를 제어하고 확인할 수 있는 방법이라 할 수 있다.
다시말해 Bootstrapping method는 Sampling 문제에서 Confidence interval에 대해 알 수 없지만, 부트스트랩은 sample variance 및 및 assumptions of nomality을 사용하여 얻은 standart intervals보다 훨씬 정확하다.
- DiCiccio TJ, Efron B (1996) Bootstrap confidence intervals (with Discussion). Statistical Science 11: 189–228- 참고
2. 단점
2.1 Bootstrapping method는 Estimate에 크게 의존하는 경향이 존재한다.
즉 위의 장점에서 Bootstrapping이 아주 단순하다는 장점을 제시했다 하지만 이 단순한 사용이 항상 유효한 결과를 이끌어 내지는 않는다[ finite-sample guarantees 제공이 안된다는 말이다 (오류를 발생할 가능성이 높다. Real data가아닌 Block size로 나누어 Random Resampling한 data set의 분포를 구성하기 때문이다 ) ].
다시말하면 결과는 Representativ sample에 강한 의존성을 보이며 Sample의 ReSampling 조건에 따라 결과는 달라지게 된다는 말이다 .
2.2 Sample의 independency or large scale sample size인 경우 Bootstrapping analysis을 진행시 Sample에서 사용하는 여러 중요한 assumption을 외곡 하거나 정보를 은폐할 수 도 있다.
3. Bootsrapping 권장사항
3.1 실질적인 결과물을 얻기 위해서는 컴퓨팅 성능과 시간을 고려하여 충분한 Sample을 사용해야한다.
3.2 Sample 수를 늘리게 되면 원 데이터의 정보양은 증가할 수 없게된다.
3.3 그러나 Bootstrapping procedure에서 발생할 수 있는 Random sampling의 Error의 영향은 줄일수 있다.
즉 통계의 이론적 분포가 복잡한 경우 Bootstrapping 을통한 Distribution은 Independency한 성격으로 Sample의 Basic distribution의 property 및 parametric variable을 평가하는 간접적인 방법을 Bootstrapping 에서 제공 받을수 있게된다.
Sample의 크기가 충분하지 않고 Basic distribution이 잘 알수 있는 경우 Bootstrapping은 Population을 완전하게 대표하지 않을 수 있는 특정 Sample로 인한 왜곡현상을 설명하는 방법을 제공하게 된다.
** 전력계산시 Sample size 계산은 통계의 표준편차에 의해 크게 의존적인 경향이 크다 .
사용된 추정치가 정확하지 않으면 필요 샘플의 크기가 잘못된것이다. 즉 작은 Sample을 사용하여 Variance를 얻기위해 Bootstrapping을 사용하는 방식이있다.
Types of Bootstrapping
1. Case Resampling
Bootstrap은 보통 사용하는 Z-statistic & t-statistic 을 제외하고 Mean , Variance Statistic 의 distribution 추론에 더 유용하다.
Bootstrap method는 대부분 Random quantities( 예를들면 Ratio of Variance and Mean)에 적용할 수 있기 때문에 대상이 되는 Data set의 Statistics의 일반적인 이론이나 분석기법들이 없을때, Distribution 핸들링 하여 Estimate하기 위해 주로 사용하게 된다.
즉 Bootstrap이 가장 흔하게 사용되는 경우로 Analystic한 통계적 분포를 구할수 없을 경우에 통계량의 분포를 추정하기 위해 Bootstrap을 사용하는 경우가 흔하다 .
The Monte Carlo Algorithm
Case Resampling방식에서 몬테카를로 알고리즘은 매우 단순하다.
첫번째로 Replacement로 Data를 다시 Resampling 을 진행하고 Resampling size는 Origin Sample의 size와 같아야한다 . ( Resample data set size = Origin data set Size )
이후 주목해야할 Origin data의 Resampling data의 통계수치는 Resampling stage에서 계산이 진행이 되며 통계(Mean , variance)값의 Bootstrap의 distribution보다 정확한 Estimate를 얻기위해 반복적으로 해당 루틴을 진행해야한다.
모든 Data의 Resampling 절차를 철저하게 진행해야한다.
위의 공식은 N이 DATA SET의 크기인 다른 Resampling set이다. 따라서 N= 5, 10 ,20, 30시 각각 상이한 Resample set을 구하게 된다.
Estimate the distribution of sample means;
예를들어 표준정규분포로부터 100개의 Observation data set X에서 iiD Random sample을 뽑는 경우를 고려해본다면
표본 평큔 X_hat 과 같이 간당한 통계량의 경우, 그 분포를 analytic하게 도출할 수 있다.
여기서 Random Sample에 대한 복잡한 통계량의 분포가 있다면 Population distribution에 대해 알지 못한다면 Population distribution을 알지못하는 상황에서 Random Sample, X1,X2,....X100에대해 10th order statistic , Y의 Sampling Distribution을 구하고자 할때 통계량은 복잡하고 Population set역시 알지 못하기때문에 Standard Original Data Mean값을 구하지못하여 Distribution을 도출할 수 없는 상황이 발생한다.
여기서 Bootstrap method를 사용하여 사실 Random sample의 10th order Statistic 의 데이터를 구할수 있게 된다.
Random Sample X1,X2, ...., X100의 값의 크기를 오름차순으로 정렬 후 , 열번째의 observation value인 Random Sample은 10th order Statistic이 되게된다. 하지만 이 10th order statstic은 단일의 값이기 때문에 즉 Pointer Estimate이기 때문에 활용할 가치가 없어지게 된다. 여기서 Bootstrap 을 활용하여 100개의 Random sample을 뽑고 10th order statistic, Y의 distribution을 알아내는것이 목적이다.
관측된 Random sample에서 X1, X2 ,.... ,X100 인 X set으로 부터 100개의 observation random sample을 Resampling 을 통하여 B개 생성하게 된다. 즉 Xset에서 100개를 Resampling 하는 작업을 B번 반복한다. Resampling은 Sample에서 다시 Sample을 뽑기때문에 Resampling이라고 정의한다.
Random Sample로 부터 획득한 Bootstrap sample B개에 대해 각 10th order statistic의값 { y*1, ... Y*B } = Y set 을 모두 구하게 된다.
B개의 Bootstrap sample들에서 구한 10th order statistic value Y set의 히스토그램을 그리고 , 이 히스토그램이 나타는 distribution이 100개의 random sample을 획득하였을때 10th order statistic Y의 distribution을 bootstrap을 이용해 추정한 그래프가 된다.
여기서 bootstrap method를 활용하여 기존에 analytic하게 구할 수 없던 통계량 Yset의 distribution을 bootstrap을 통하여 얻은 히스토그램으로 전체를 추정했다. 이제 Var(Y)가 알고 싶다면 Yset의 Standard variance를 구하고 Y의 mean은 Yset의 Standart mean을 구하면 된다.
2.2 Statistic - Theoretical Background of Bootstrap method
Bootstrap method는 어떠한 상황에서도 다 적용되는 general한 method처럼 보인다. 하지만 Bootstrap method를 적용할때 단점과 같이 Bootstrap 적용시 주의할 부분이 분명 존재하고 , Bootstrap을 이용한 통계량의 분포 추정이 가능한 이유에 대해 알아보고자 한다 .
바로 위의 목적에서 RandomSample X set = { X1, X2 , ...., X100}에서 10th order statistic, Y의 분포 (Sampling Distribution ) 을 구하는것이 목적이 었다.
더 구체적으로 보자면 Y의 Distribution, Variance Var(Y)를 구하게 되면
1. Random Sample의 (모집단의 분포)population distribution F로부터 100개의 Sample Xset을 구성 한후
2. Xset 100개의 Random Sample Observation 중 10th order statistic을 Y로 설정하게 된다.
위의 과정을 모든 가능한 Random Sample의 경우에 대해 모두 고려하여 분산을 구한 것이, Var(Y)가 생성되는 과정이라고 본다. 여기서 Bootstrap은 위의 과정을 따라하는 것이다. 그러나 population distribution F를 잘 알지 못하므로 Population set에서 Random Sample을 추출 할 수 없게된다. 따라서 Statistic Bootsrap의 맨처음 제시한 Empirical Distribution, F^ 으로부터 Random Sample을 뽑게된다.
Empirical Distribution F^
Emprical Distirubion이란 n개의 데이터셋 X= {X1,X2, .... ,Xn}이 존재할 때 각 Data Point에서 1/n씩의 Density를 갖는 이산확률분포이다. 주로 누적분포함수의 형태로 나타나며 Empirical distribution function은 각 데이터 점에서 1/n씩 상승하는 계단 모양의 Step Function이다.
표준정규분포에서 생성된 20개의 observation에 대한 Random Sample의 Empirical distribution function.
주황색 곡선으로 나타난 곡선은 표준정규분포의 실제 누적분포함수이다. Population의 실 확률 분포함수는 아니지만. Observation Random sample을 통해 empirically(경험적)으로 얻어진 확률분포라는 의미로 Empirical distribution Function이라고 한다. 만약 Random Sample의 크기를 20에서 160으로 늘리게 된다면 아래와 같은 개형을 가지게 된다.
표준정규분포에서 생성된 160개의 observation에 대한 Random Sample의 Empirical distribution function
위 그림에서 보면 Empricial distribution function F^ 는 Random Sample의 size(N)이 커질수록 실제 Population distribution function F에 거의 근사하게 수렴하는 것으로 알려져 있다. 이 때 Emprical distribution Function F^이 Population distribution function F에 수렴하려면 Emprical distribution이 기반한 Sample이 population으로부터 IID한 가정하에 추출된 Random Sample이어야 한다. Emprical distribution function의 Asymptotic behavior은 Glivenko-Cantelli theorem에 상세하게 저술되어 있다.
※ Glivenko-Cantelli theorem ( Emprical distribution function의 Asymptotic behavior )
Emprical distribution Function의 Asymptotic behavior을 independent이고 Identically distribution observation data의 수로 결정하게 되는 이론.
.
Emprical distribution과 Population ditribution을 비교하여 Observation Data & Sampling data num이 증가할 수록 Emprical distribution function이 Population ditribution function에 점적으로 근사하게 접근하는것을 보여주는 Graph 개형이다.
Bootstrap 을통하여 Y가 생성되는 Generating Process를 모방하여 Y의 분산 Var(Y)를 구하기 위해 Population distribution F에서 Random Sample 추출 대신 Emprical distribution F^에서 Random Sample을 추출하여 Bootstrap sample을 생성한 후, Y를 모방한 Y*를 만든다.
In the Real World
In the Bootstrap World.
즉 Population에서 추출한 Random Sample로 부터 복원 추출을하여 Bootstrap resampling하여 Y*를 구하게 된이유는 Emprical distribution의 iid ramdom Sample을 추출해야 했기 때문이고 . 통계량 Y를 Replicate하는것이 아닌 Y의 Distribution을 추정하는것이 목적이므로 Y = g(X) = g(X1, x2, .... , X100)의 분산 Var(Y)는
나타내게 된다.
dFj = fj(Xj)dXj = f(Xj)dXj이다 . dFx(x)/dx = fx(x)
CDF를 확률변수로 미분하면 PDF가 되는 Notation을 떠올리자.
Bootstrap의 Population 누적분포함수 F를 Emprical distribution Function F^으로 대체 하게 됐으므로 , Bootstrap으로 얻은 Var(Y)의 추정값은 아래와 같이 나타나게 된다.
이를 ideal한 bootstrap estimate 라고 하게 되고 적분 내부의 dF^j = f^(X*j)dX*j를 의미한다.
여기서 Bootstrap sample X* Set = {X*1, X*2, ... ,X*100 }이 생성된 Distribution F^를 알고 있지만 , Random Sample의 크기 N이 작지 않은 이상 위의 수식을 적용하는것은 쉽지 않다. 그렇기 때문에 Ideal bootstrap estimate를 Monte Carlo Intergration을 진행하여 한번더 근사하게 하여 최종적인 Bootstrap 추정치를 결과로 사용하게 된다.
Monte Carlo Integration
Monte Carlo Intergration은 적분 값을 근사를 통해 구하는 Numerical method 중 하나로 난수를 생성하여 적분 값 근사를 수행하게 된다.
적분 구간 D에서 f를 적분한 F를 구하는 경우
D를 support로 가지며 난수를 생성할 수 있는 PDF p(x)가 있다고 하면 , 이를 이용하여 위의 적분식을 아래의 식으로 변형 할수 있다.
즉 f(x)/p(x)를 p(x)의 PDF를 가지는 확률변수에 기대값을 취한것과 같아지게된다.
대수의 법칙은 N이 충분히 크다면 Random Sample로부터 생성한 표본평균이 Population average로 Probablicstic Converce 하는것을 보장하게 된다. 따라서 위와같이 근사할 수 있게 된다.
p(x)를 PDF로 가지는 난수 N개를 생성한 뒤 , 난수 X1,X2 , .... ,Xn에 대하여 f(x)/p(x)의 값을 각각 모두 구한후 , 표본평균을 구하는 방식으로 F의 적분값을 추정할 수 있게 된다.
즉 Monte Carlo Intergration을 취하여 Ideal bootstrap estimate를 추정한 Y의 distribution에 대한 Bootstrap estimate는 아래의 수식으로 표현할 수 있게 되고
observation Random Sample에 대해 Resampling을 통하여 Emprical distribution에서 Bootstrap sample을 B번 추출한후, 각 Y=g(X)의 편차의 제곱, (g(X*)-E[g(X*)])^2의 값을 구하여 표본 평균을 구하게 된다.
즉 B개의 Bootstrap sample에서 구한 각각의 10th order statistic의 값 y*1, ...., y*B의 histogram을 그린후. 이 분포가 100개의 random sample을 추출시 10th order statistic Y의 분포를 Bootstrap을 이용해 추정하게 된것이다.
다시한번 Boot strap 을 정리하면...
observation data sample X set , X = (X1, X2, .... , Xn) 으로부터 Bootstrap sample을 B번 생성한다고 하면, 통계량 Y=g(X) = g(X1, X2, ..., Xn)의 분산을 추정하게 되는것이다. 상세한 수식 Process는 아래와 같다.
Random Sample Set X , X = (X1, X2, .... , Xn)에서 N개를 Resampling하는 작업을 B번수행이후 그결과로 만들어진 B개의 Sample을 Bootstrap Sample이라한다.
Y는 Population distribution F에서 생성된 Random Sample X에 대한 함수이다. 이를 모방하기 위해 Emprical distribution F^으로부터 Bootstrap sample을 생성하게 되고, Glivenko-Cantelli 정리에 따라 Emprical distribution N이 커짐에 따라 Population Distribution에 Converce하게된다.
random sample로부터 추출한 bootstrap sampleB개에 대해, 각각10thorder statistic의 값,y∗1,⋯,y∗By∗1,⋯,y∗B을 모두 구한다.
B개의 bootstrap sample들에서 각각 구한10thorder statistic의 값,y∗1,⋯,y∗By∗1,⋯,y∗B의 히스토그램을 그린다. 이 히스토그램이 나타내는 분포가,100개의 random sample을 뽑았을 때의10thorder statistic,Y의 분포를 bootstrap을 이용해 추정한 것이다.
이는 ideal bootstrap 추정치를 Monte Carlo integration으로 추정하는 것과 같다.Y∗의편차 제곱의 기대값Var(Y)을Y∗의편차 제곱의 표본평균(Var^(Y))으로 추정하는 것. 이는 대수의 법칙에 의해 뒷받침된다
Bootstrap Standard Error of an Estimator/Test Statistic
Bootstrap은 통계량의 분포를 analytic하게 구할 수 없는 상황에서, random sample이 생성되는 과정을 모방함으로써, 통계량의 분포를 근사할 수 있게 해주는 방식이다. 이는 식의 도출로 analytical 표준오차(standard error)를 구하는 것이 불가능한 추정량(estimator) 및 검정통계량(test statistic)의 표준오차 및 신뢰구간을 구할 수 있게 해준다.
Bootstrap Prediction Error
모형의 선택(Selection)과 평가(Assessment)를 위해서, prediction error, 혹은 test error라고도 불리는 extra-sample error를 추정해야한다.
통계 모형 역시 true data generating function을 추정하는 추정량이기 때문에, 큰 틀에서는 Bootstrap Standard Error를 구하는 것과 같은 맥락이다. 하지만 bootstrap 후 loss의 평균을 구하는 것이 아니라
.632estimator,.632+estimator와 같이 test error를 정확히 추정하기 위한 방법들이 연구되고 있다.
이들은 실제로 test error를 구하는 데 있어서, cross validation과 비슷한 수준의 성능을 보여주는 것으로 알려져 있다.
Bagging
BootstrapAggregating, 부트스트랩 합치기. 위에서와 같이 모수 추정이나 예측의 정확성을 평가하기 위한 목적이 아니라, 추정 혹은 예측 자체의 성능을 개선시키는데 bootstrap을 사용하는 방법이다.
주어진 training data로부터 bootstrap sample을 resampling한 후, 각 bootstrap sample 내에서 fit된 모형들의 예측을 평균내는 방식으로 이루어진다. (classification인 경우는 다수결 원칙으로 결정.)
