142강부터 145강까지 표본평균을 두 가지 방식으로 다뤘습니다. 둘 다 만족스럽지 않습니다.
| 도구 | 성립 범위 | 문제 |
|---|---|---|
| 체비쇼프(142강) | 모든 에서 옳습니다 | 으로만 줄어 매우 느슨합니다 |
| 중심극한정리(143강) | 날카롭습니다 | 극한이라 유한한 에서 보장이 없습니다 |
우리가 원하는 것은 둘 다입니다. 어떤 에서나 반드시 옳으면서 지수적으로 줄어드는 상한이 필요합니다.
이것이 호에프딩 부등식이며, 분포의 모양을 하나도 모른 채 "값이 안에 있다"는 것만으로 이 상한을 얻습니다.
그리고 이 부등식이 기계학습 이론의 출발점입니다. 검증 정확도가 참 정확도에서 얼마나 벗어날 수 있는지, 모델을 여러 개 비교할 때 얼마나 조심해야 하는지가 전부 여기서 나옵니다.
문제. 142강 문제 2와 같은 설정입니다. 주사위 평균을 오차 , 실패 확률 로 알고 싶습니다.
(1) 호에프딩이 요구하는 을 구하세요.
(2) 체비쇼프, 정규근사와 비교하세요.
(3) 에 따라 두 상한의 우열이 바뀌는지 판정하세요.
생각의 실마리. 주사위는 값이 부터 까지이므로 입니다. 평균도 분산도 몰라도 이 사실만으로 상한이 나옵니다.
풀이. (1) 상한을 이하로 만들면 됩니다.
, , 이므로 ****입니다.
(2) 세 방법을 나란히 놓습니다.
| 방법 | 필요한 | 쓰는 정보 | 성립 범위 |
|---|---|---|---|
| 정규근사 | 분산, 큰 가정 | 근사입니다 | |
| 호에프딩 | 값의 범위 | 모든 | |
| 체비쇼프 | 분산 | 모든 |
호에프딩이 체비쇼프의 배이며, 분산조차 쓰지 않았는데 더 적은 표본을 요구합니다. 정규근사의 배이므로 안전을 위해 네 배를 더 뽑는 셈입니다.
(3) 을 바꿔 가며 상한을 봅니다.
| 체비쇼프 상한 | 호에프딩 상한 | 정규근사 참값 | |
|---|---|---|---|
우열이 바뀝니다. 에서는 체비쇼프가 낫고 부터 호에프딩이 앞섭니다.
이 문제에서 배우는 것: 호에프딩 부등식.
호에프딩 부등식. 가 독립이고 이면
같은 분포일 필요가 없습니다. 각 항의 범위만 알면 되며, 이것이 실무에서 매우 유용합니다.
| 상한 | 감소 속도 | 필요한 정보 |
|---|---|---|
| 마르코프 | 평균 | |
| 체비쇼프 | 분산 | |
| 호에프딩 | 범위 | |
| 중심극한정리 | 분산, 극한 |
넷째 줄과 셋째 줄의 지수를 비교하면 호에프딩의 대가가 보입니다. 분모에 대신 가 들어가며, 주사위에서 대 이므로 약 배 손해입니다. 문제 2에서 이 숫자가 어디에서 오는지 밝힙니다.
이 여기서도 나옵니다. 상한을 로 고정하면 입니다.
정확도를 한 자리 올리려면 표본을 배 늘려야 한다는 142강의 결론이 그대로이며, 달라진 것은 상수뿐입니다.
바로 확인 1.
확인 1-1. 호에프딩 부등식의 상한을 쓰세요.
답. 입니다.
확인 1-2. 필요한 표본 크기 공식을 쓰세요.
답. 입니다.
확인 1-3. 호에프딩이 쓰는 정보를 쓰세요.
답. 값이 놓인 범위뿐입니다.
문제. 135강의 체르노프 방법을 다시 씁니다.
(1) 주사위에서 를 실제로 계산하세요.
(2) 호에프딩 보조정리의 상한과 비교하세요.
(3) 분산만 쓴 값과도 비교하고 손해를 계산하세요.
생각의 실마리. 135강에서 에 마르코프를 적용하면 지수 상한이 나왔습니다. 문제는 적률생성함수를 모르는 상황에서 그것을 어떻게 제한하느냐입니다.
풀이. (1)(2)(3) 검산 결과입니다.
| 실제 | 보조정리 상한 | 분산만 쓴 값 | 상한/실제 | |
|---|---|---|---|---|
가 작을 때는 거의 정확하고 커지면 크게 벌어집니다. 다행히 실제로 쓰는 최적 는 작은 값입니다.
셋째 열이 실제에 매우 가깝습니다. 에서 대 이며, 분산만 알아도 적률생성함수를 잘 근사할 수 있습니다.
이 문제에서 배우는 것: 체르노프 방법과 호에프딩 보조정리.
체르노프 방법. 임의의 에 대해
세 단계입니다. 마르코프를 에 적용하고, 독립성으로 곱으로 쪼개고, 를 최적화합니다.
호에프딩 보조정리. 이고 이면
이 한 줄이 전부입니다. 곱하면 이 되고, 을 곱한 뒤 로 최소화하면 지수가 가 됩니다.
보조정리가 분산을 로 잡습니다. 주사위에서 인데 실제 분산은 이므로 배 부풀린 값입니다.
왜 인가. 안의 확률변수가 가질 수 있는 최대 분산이며, 양 끝에 확률 씩 놓았을 때입니다.
최악의 경우를 가정한 대가이며, 그래서 분포를 몰라도 됩니다. 133강 문제 2에서 두 점 분포가 체비쇼프의 등호를 준 것과 같은 구조입니다.
바로 확인 2.
확인 2-1. 체르노프 방법의 세 단계를 쓰세요.
답. 지수에 마르코프를 적용하고 독립으로 쪼갠 뒤 를 최적화합니다.
확인 2-2. 호에프딩 보조정리를 쓰세요.
답. 입니다.
확인 2-3. 보조정리가 쓰는 분산 대용값과 그 이유를 쓰세요.
답. 이며 그 구간에서 가능한 최대 분산이기 때문입니다.
문제. 성공 확률 인 희귀 사건을 로 추정합니다.
(1) 실제 이항 꼬리 확률을 정확히 계산하세요.
(2) 호에프딩 상한과 비교하세요.
(3) 베른슈타인 상한과도 비교하고 판정하세요.
생각의 실마리. 이면 분산이 로 매우 작은데, 호에프딩은 범위 만 보므로 분산을 로 잡습니다. 배 부풀린 값입니다.
풀이. (1)(2)(3) 검산 결과입니다.
| 실제 이항 꼬리 | 호에프딩 | 베른슈타인 | 호에프딩/실제 | 베른슈타인/실제 | |
|---|---|---|---|---|---|
| 6.3027\times10^ | |||||
| 3.3315\times10^ | 4.5721\times10^ | 3.002\times10^ | 1.372\times10^ | ||
| 2.4848\times10^ | 7.3576\times10^ | 1.2487\times10^ | 2.961\times10^ | 5.025\times10^ | |
| 4.0316\times10^ | 3.6631\times10^ | 3.0395\times10^ | 9.086\times10^ | 7.539\times10^ |
호에프딩이 무너집니다. 에서 실제 확률의 배이며, 상한이 인데 참값이 입니다.
베른슈타인은 견딥니다. 같은 자리에서 배이며, 지수의 모양 자체가 맞습니다.
이 문제에서 배우는 것: 베른슈타인 부등식.
베른슈타인 부등식. 이고 분산이 이면
분모에 분산이 직접 들어갑니다. 에서 지수 안의 계수가 호에프딩의 배입니다.
| 영역 | 지배하는 항 | 모양 |
|---|---|---|
| 이 작을 때 | 2\sigma^ | 정규 꼬리 |
| 이 클 때 | 지수 꼬리 e^ |
두 영역이 자동으로 전환됩니다. 작은 편차에서는 중심극한정리와 같은 모양을 주고, 큰 편차에서는 더 느리지만 여전히 지수로 줄어듭니다.
언제 어느 것을 쓰는가. 이 에 가까우면 호에프딩으로 충분하고, 훨씬 작으면 베른슈타인을 씁니다.
희귀 사건이 그 전형입니다. 클릭률, 전환율, 결함률, 이상탐지처럼 가 작은 문제에서 호에프딩을 쓰면 필요 없는 표본을 수십 배 요구합니다.
바로 확인 3.
확인 3-1. 베른슈타인 부등식의 지수 분모를 쓰세요.
답. 입니다.
확인 3-2. 호에프딩이 희귀 사건에서 느슨한 이유를 쓰세요.
답. 분산을 보지 않고 범위만 보므로 로 잡기 때문입니다.
확인 3-3. 베른슈타인의 두 영역을 쓰세요.
답. 작은 편차에서 정규 꼬리, 큰 편차에서 지수 꼬리입니다.
문제. 후보 모델이 개이고 모두에 대해 동시에 보장하려 합니다.
(1) 필요한 오차 을 의 함수로 쓰세요.
(2) 을 억 배 늘리면 이 몇 배 커지는지 계산하세요.
(3) 상한이 실제로 성립하는지 확인하세요.
생각의 실마리. 142강 심화 4에서 본 문제입니다. 자료를 보고 고른 모델은 자료와 독립이 아니므로 하나에 대한 보장으로는 부족합니다.
풀이. (1)(2) 검산 결과입니다. , 입니다.
| 필요한 | 대비 배수 | |
|---|---|---|
| 10^ | ||
| 10^ |
이 억 배가 되어도 은 배만 커집니다. 이 로그로 들어가기 때문입니다.
(3) 모의실험으로 확인합니다.
| 설정 | 보장 오차 | 실제 최대 초과율 | 목표 |
|---|---|---|---|
| , | 이하 | ||
| , | 이하 |
성립하며 크게 여유가 있습니다. 실제 초과율이 목표의 정도이므로 상한이 보수적입니다.
이 문제에서 배우는 것: 합집합 상한.
합집합 상한. 입니다. 각 에 호에프딩을 적용하면
122강의 부울 부등식이 여기서 이론의 뼈대가 됩니다. 확률의 공리에서 곧바로 나오는 가장 단순한 부등식인데, 기계학습의 일반화 보장 전체가 이것 위에 서 있습니다.
| 이 들어가는 방식 | 결과 |
|---|---|
| 곱으로 | 상한이 배 |
| 지수 밖에서 로그로 | 이 배 |
| 필요한 에 |
셋째 줄이 결정적입니다. 후보가 억 개여도 표본은 배만 있으면 되며, 모델 선택이 실제로 가능한 이유입니다.
그런데 후보가 무한하면 어떻게 되는가. 이 발산하므로 이 논법이 그대로는 무너집니다.
VC 차원과 라데마허 복잡도가 그 답입니다. 무한한 가설공간이라도 개의 점에서 만들어 내는 서로 다른 라벨 패턴은 유한하며, 그 개수가 의 자리를 대신합니다. 214강 모델 복잡도와 과적합이 이 계산입니다.
바로 확인 4.
확인 4-1. 합집합 상한을 쓰세요.
답. 입니다.
확인 4-2. 개 동시 보장에 필요한 을 쓰세요.
답. 입니다.
확인 4-3. 이 필요한 표본 크기에 들어가는 방식을 쓰세요.
답. 에 비례합니다.
문제. 파레토 는 평균이 이고 분산이 무한합니다.
(1) 표본평균의 오차 분위수를 재세요.
(2) 블록별 평균의 중앙값과 비교하세요.
(3) 어느 쪽을 써야 하는지 판정하세요.
생각의 실마리. 호에프딩은 유계를, 베른슈타인은 유계와 분산을 요구합니다. 둘 다 없으면 지수 상한을 얻을 길이 없습니다.
풀이. (1)(2) 을 개 블록으로 나누고 번 시행한 결과입니다.
| 분위수 | 표본평균 오차 | 중앙값의 평균 오차 | 비 |
|---|---|---|---|
중앙값을 취하는 방법이 중앙에서는 조금 나쁘고 꼬리에서 크게 좋습니다. 최악의 경우 표본평균은 이나 벗어났는데 중앙값 방법은 입니다.
(3) 꼬리를 보장해야 하면 중앙값 방법을 씁니다. 집중 부등식이 관심을 갖는 것이 바로 꼬리이며, 표본평균은 그 자리에서 무너집니다.
이 문제에서 배우는 것: 집중은 조건이 필요합니다.
하위가우시안. 를 만족하면 하위가우시안이라 하고, 정규와 같은 꼬리 상한을 얻습니다.
| 조건 | 얻는 꼬리 | 예 |
|---|---|---|
| 유계 | 지시함수, 정확도, 구간 자료 | |
| 하위가우시안 | 정규, 유계 | |
| 하위지수 | 작은 에서 | 지수, 카이제곱 |
| 분산만 유한 | 체비쇼프뿐입니다 | |
| 분산 무한 | 지수 상한 없음 | 파레토 , 코시 |
넷째와 다섯째 줄이 실무의 위험 지대입니다. 손실액, 대기 시간, 트래픽, 강화학습의 보상 합처럼 꼬리가 두꺼운 양은 표본을 늘려도 지수적 보장을 주지 않습니다.
블록 평균의 중앙값. 자료를 개 블록으로 나눠 각 블록의 평균을 내고 그 중앙값을 취하면, 분산만 유한해도 지수 상한을 얻습니다.
요령이 단순합니다. 각 블록이 절반 이상 확률로 참값 근처에 있으면 중앙값도 그렇게 되며, 블록이 다 같이 실패할 확률이 지수로 줄어듭니다.
대가는 중앙에서의 손해입니다. 표의 첫 줄에서 중앙값 방법이 배 나쁩니다. 평상시의 정밀도를 조금 내주고 최악의 경우를 사는 거래입니다.
바로 확인 5.
확인 5-1. 하위가우시안의 정의를 쓰세요.
답. 를 만족하는 것입니다.
확인 5-2. 분산이 무한하면 무엇을 얻을 수 있는지 쓰세요.
답. 지수 상한을 얻을 수 없습니다.
확인 5-3. 블록 평균의 중앙값이 주는 상한을 쓰세요.
답. 블록이 개일 때 꼴입니다.
| 부등식 | 상한 | 필요한 조건 |
|---|---|---|
| 마르코프 | ||
| 체비쇼프 | 분산 유한 | |
| 체르노프 | \inf_{\lambda}e^{-\lambda t}M(\lambda)^ | 적률생성함수 존재 |
| 호에프딩 | 유계 | |
| 베른슈타인 | 유계, 분산 | |
| 합집합 | 각각 유계 | |
| 블록 중앙값 | e^ | 분산 유한 |
| 목표 | 필요한 또는 |
|---|---|
| 호에프딩의 | |
| 호에프딩의 | (b-a)\sqrt |
| 개 동시 | (b-a)\sqrt |
| 표본 크기의 의존 |
| 주사위 예 | 필요한 |
|---|---|
| 정규근사 | |
| 호에프딩 | |
| 체비쇼프 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 호에프딩이 언제나 체비쇼프보다 낫다고 봅니다 | 작은 에서는 체비쇼프가 낫습니다 |
| 희귀 사건에 호에프딩을 씁니다 | 베른슈타인이 수십 배 날카롭습니다 |
| 모델을 여러 개 보고 하나에만 보장을 씁니다 | 합집합 상한이 필요합니다 |
| 이 크면 못 쓴다고 봅니다 | 이라 억 개도 괜찮습니다 |
| 꼬리가 두꺼워도 지수 상한이 있다고 봅니다 | 분산이 무한하면 없습니다 |
| 상한을 실제 확률로 읽습니다 | 배까지 벌어질 수 있습니다 |
문제 6. 호에프딩 부등식을 쓰세요.
답. 입니다.
문제 7. 호에프딩이 요구하는 조건과 요구하지 않는 것을 쓰세요.
답. 독립과 유계만 요구하며 같은 분포도 분산도 요구하지 않습니다.
문제 8. 주사위 예에서 세 방법이 요구하는 을 쓰세요.
답. 정규근사 , 호에프딩 , 체비쇼프 입니다.
문제 9. 체비쇼프가 호에프딩보다 나은 경우를 쓰세요.
답. 이 작아 지수가 아직 작동하지 않을 때입니다.
문제 10. 체르노프 방법의 세 단계를 쓰세요.
답. 지수에 마르코프를 적용하고 독립으로 쪼갠 뒤 를 최적화합니다.
문제 11. 호에프딩 보조정리와 그것이 쓰는 분산 대용값을 쓰세요.
답. 이며 를 씁니다.
문제 12. 주사위에서 그 대용값이 실제 분산의 몇 배인지 쓰세요.
답. 배입니다.
문제 13. 베른슈타인 부등식과 그 이점을 쓰세요.
답. 지수 분모가 이며 분산이 작으면 훨씬 날카롭습니다.
문제 14. 에서 두 상한의 지수 계수 비를 쓰세요.
답. 베른슈타인이 호에프딩의 배입니다.
문제 15. 합집합 상한과 개 동시 보장의 을 쓰세요.
답. 이며 입니다.
문제 16. 이 일 때 이 몇 배가 되는지 쓰세요.
답. 의 배입니다.
문제 17. 분산이 무한할 때 얻을 수 있는 것과 없는 것을 쓰세요.
답. 큰 수의 법칙은 성립하지만 지수 상한은 얻을 수 없습니다.
문제 18. 블록 평균의 중앙값이 주는 것과 그 대가를 쓰세요.
답. 꼴의 지수 상한을 주며 대가는 중앙에서의 정밀도 손해입니다.
심화 1. 집중 부등식의 계보를 정리하세요.
모두 하나에서 갈라져 나왔습니다.
| 부등식 | 무엇에 마르코프를 적용하는가 | 추가로 쓰는 것 |
|---|---|---|
| 마르코프 | 없습니다 | |
| 체비쇼프 | (X-\mu)^ | 분산 |
| 체르노프 | e^ | 적률생성함수 |
| 호에프딩 | e^ | 유계, 보조정리 |
| 베른슈타인 | e^ | 유계, 분산 |
| 베넷 | e^ | 유계, 분산, 더 정밀한 전개 |
| 맥디아미드 | e^ | 유계 차분, 마팅게일 |
| 탈라그랑 | 등주 부등식 | 볼록 거리 |
135강에서 "셋 다 마르코프 하나에서 나온다"고 한 것이 여기서 여덟 줄로 늘어났습니다. 확률론에서 가장 단순한 부등식 하나가 집중 현상 이론 전체를 떠받칩니다.
여섯째 줄의 베넷이 베른슈타인보다 날카롭습니다. 지수가 꼴이며, 를 아래에서 근사해 단순화하면 베른슈타인이 나옵니다.
심화 2. 하위가우시안과 하위지수를 정리하세요.
집중의 속도는 적률생성함수의 증가 속도가 정합니다.
| 종류 | 조건 | 꼬리 | 예 |
|---|---|---|---|
| 하위가우시안 | 모든 | 정규, 유계 | |
| 하위지수 | 위 식이 에서만 | 작으면 제곱, 크면 선형 | 지수, 카이제곱 |
| 무거운 꼬리 | 어떤 에서도 발산 | 다항식 | 파레토, , 로그정규 |
둘째 줄이 실무에서 매우 자주 나옵니다. 제곱 오차, 카이제곱 통계량, 분산 추정량이 모두 하위지수이며, 작은 편차에서는 정규처럼 큰 편차에서는 지수처럼 행동합니다.
하위가우시안 변수의 제곱이 하위지수입니다. 그래서 평균에 대한 보장은 제곱 형태로 넘어가면 한 단계 약해지며, 144강 문제 5에서 이 보다 예민했던 것과 같은 이야기입니다.
세 종류 모두 노름을 정의할 수 있습니다. 와 을 오를리츠 노름이라 하며, 고차원 확률론의 표준 언어입니다.
심화 3. 평균이 아닌 함수의 집중을 정리하세요.
지금까지는 만 다뤘습니다. 일반적인 함수도 집중합니다.
맥디아미드 부등식. 가 유계 차분 조건을 만족하면, 즉 좌표 하나만 바꿨을 때 값의 변화가 이하이면
가 평균이면 이라 호에프딩이 그대로 나옵니다. 진짜 값어치는 평균이 아닌 함수에 있습니다.
| 함수 | 유계 차분 | 쓰이는 곳 |
|---|---|---|
| 표본평균 | 호에프딩 | |
| 최댓값, 분위수 | 작습니다 | 순서통계량 |
| 경험위험의 상한 | 일반화 상한 | |
| 학습 알고리즘의 출력 손실 | 안정성 계수 | 안정성 기반 일반화 |
| 그래프의 부분구조 개수 | 국소적 | 무작위 그래프 |
넷째 줄이 깊습니다. 훈련 표본 하나를 바꿨을 때 학습된 모델의 손실이 조금만 변하면, 그 알고리즘은 일반화합니다. 가설공간의 크기를 전혀 재지 않고도 일반화 보장을 얻는 길이며, 확률경사하강법의 일반화 분석이 이 경로를 씁니다.
심화 4. 학습이론의 일반화 상한을 정리하세요.
문제 4의 논법이 그대로 이어집니다.
| 가설공간 | 의 자리 | 상한 |
|---|---|---|
| 유한 개 | \sqrt | |
| VC 차원 | \sqrt | |
| 라데마허 복잡도 | 2\mathfrak{R}_{n}+\sqrt | |
| 마진 기반 | 마진으로 나눈 노름 | 차원과 무관할 수 있습니다 |
| PAC-베이즈 | KL 발산 | 사전분포에 의존합니다 |
셋째 줄이 가장 날카롭습니다. 라데마허 복잡도는 가설공간이 무작위 라벨을 얼마나 잘 맞추는지를 재며, 자료 분포를 반영하므로 VC 차원보다 덜 보수적입니다.
넷째 줄이 심층학습의 수수께끼와 맞닿습니다. 모수가 자료보다 훨씬 많은데도 일반화하는 현상은 VC 차원으로 설명되지 않으며, 마진, 노름, 암묵적 정규화로 설명하려는 시도가 이어지고 있습니다.
다섯째 줄이 211강의 정규화와 만납니다. 사후분포가 사전분포에서 멀지 않으면 일반화가 보장되며, KL 발산 벌점이 정규화 항의 이론적 정당화입니다.
심화 5. 고차원에서의 측도 집중을 정리하세요.
집중은 표본 개수만의 이야기가 아닙니다. 차원이 커져도 일어납니다.
| 현상 | 내용 |
|---|---|
| 구면 집중 | 의 질량이 적도 근처 폭 띠에 몰립니다 |
| 노름의 집중 | 이 근처에 폭으로 몰립니다 |
| 거리의 집중 | 임의의 두 점 사이 거리가 거의 같아집니다 |
| 존슨-린덴슈트라우스 | 차원으로 사영해도 거리가 보존됩니다 |
| 리프시츠 함수 | 구면 위 리프시츠 함수가 중앙값 근처에 집중합니다 |
셋째 줄이 213강 차원의 저주입니다. 모든 거리가 비슷해지면 최근접 이웃이 뜻을 잃습니다.
넷째 줄은 같은 현상의 좋은 얼굴입니다. 무작위 사영 행렬의 각 성분에 호에프딩을 적용하고 합집합 상한을 씌우면 나오며, 개 점의 거리를 모두 보존하는 데 필요한 차원이 뿐입니다. 224강의 차원축소와 랜덤 특징이 여기에 기댑니다.
140강 심화의 고차원 측도 집중이 여기서 정리됩니다. 다변량 정규에서 표본이 원점이 아니라 반지름 인 얇은 껍질에 몰리는 현상이 둘째 줄입니다.
심화 6. 기계학습에서 이 부등식들이 쓰이는 자리를 정리하세요.
| 자리 | 어느 부등식 | 관련 강의 |
|---|---|---|
| 검증 정확도의 오차 막대 | 호에프딩 | 209강 |
| 모델 선택의 다중 비교 | 합집합 상한 | 212강 |
| 밴딧의 UCB | 호에프딩 | 278강 |
| A/B 테스트의 순차 모니터링 | 마팅게일, 언제나 유효한 구간 | 152강 |
| 일반화 상한 | 맥디아미드, 라데마허 | 214강 |
| 차분 프라이버시의 합성 | 베른슈타인 계열 | 468강 |
| 무작위 사영 | 존슨-린덴슈트라우스 | 224강 |
| 강화학습의 표본 복잡도 | 베른슈타인 | 274강 |
셋째 줄이 가장 아름다운 응용입니다. 팔 하나를 번 당겨 평균 보상 를 얻었다면, 호에프딩이 주는 신뢰 폭을 더해 상한이 가장 큰 팔을 고릅니다.
탐색과 활용의 균형이 부등식 하나에서 나옵니다. 덜 당겨 본 팔은 폭이 넓어 자동으로 선택되고, 많이 당긴 팔은 폭이 좁아져 평균으로 승부합니다.
넷째 줄이 실무에서 자주 틀리는 자리입니다. A/B 테스트를 매일 들여다보며 유의해지면 멈추는 방식은 다중 비교와 같은 문제를 일으키며, 명목 가 실제로는 훨씬 커집니다. 모든 시점에서 동시에 유효한 구간이 필요하며, 그것이 마팅게일 기반 방법입니다.
여섯째 줄이 프라이버시와 만납니다. 질의를 여러 번 하면 프라이버시 손실이 쌓이는데, 단순히 더하는 대신 집중 부등식을 쓰면 로 줄일 수 있습니다. 469강 차분 프라이버시 확률경사하강법이 이 계산에 기댑니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 값의 범위 | 호에프딩의 유일한 재료입니다 | |
| 람다 | 체르노프에서 최적화하는 모수입니다 | |
| 델타 | 허용하는 실패 확률입니다 | |
| 후보 개수 | 가설공간의 크기입니다 | |
| 호에프딩 | Hoeffding | 유계 변수의 지수 상한입니다 |
| 베른슈타인 | Bernstein | 분산을 함께 쓰는 상한입니다 |
| 베넷 | Bennett | 베른슈타인보다 날카롭습니다 |
| 맥디아미드 | McDiarmid | 유계 차분 함수의 집중입니다 |
| 합집합 상한 | union bound | 부울 부등식입니다 |
| 하위가우시안 | sub-Gaussian | 정규와 같은 꼬리입니다 |
| 하위지수 | sub-exponential | 두 영역을 갖는 꼬리입니다 |
| 블록 중앙값 | median-of-means | 무거운 꼬리의 대안입니다 |
| 라데마허 복잡도 | Rademacher complexity | 자료를 반영한 복잡도입니다 |
| 존슨-린덴슈트라우스 | Johnson-Lindenstrauss | 거리를 보존하는 무작위 사영입니다 |
| UCB | upper confidence bound | 신뢰 상한으로 팔을 고릅니다 |
다음은 147강 몬테카를로 추정입니다. 이 단원의 도구를 모두 씁니다.
적분을 표본평균으로 바꾸는 것이며, 142강의 큰 수의 법칙이 수렴을 보장하고 143강의 중심극한정리가 오차 막대를 주며 이 강의의 부등식이 유한 표본 보장을 줍니다. 차원이 아무리 높아도 오차가 인 이유가 147강의 요점입니다.
import numpy as np
rng = np.random.default_rng(20260814)
zg = (np.arange(240001) - 120000) * 1e-4 # 표준정규 분포함수를 격자 누적으로 만듭니다
phig = np.exp(-zg * zg / 2) / np.sqrt(2 * np.pi)
cdfg = (np.cumsum(phig) - 0.5 * phig) * 1e-4
cdfg = cdfg - cdfg[120000] + 0.5
def Phi(z):
return np.interp(z, zg, cdfg)
# --- 문제 1: 유계라는 조건 하나로 얼마나 좋아지는가 ---------------------
print(" 주사위 평균을 오차 0.1 안에서 실패확률 5% 이하로 알고 싶습니다")
mu, sig2, rng_len = 3.5, 35.0 / 12.0, 5.0
eps, delta = 0.1, 0.05
n_cheb = int(np.ceil(sig2 / (delta * eps * eps)))
n_hoef = int(np.ceil(rng_len ** 2 * np.log(2 / delta) / (2 * eps * eps)))
z975 = float(np.interp(0.975, cdfg, zg))
n_clt = int(np.ceil((z975 * np.sqrt(sig2) / eps) ** 2))
print(" 체비쇼프 n = %d, 호에프딩 n = %d, 정규근사 n = %d"
% (n_cheb, n_hoef, n_clt))
print(" 호에프딩은 체비쇼프의 %.3f 배이고 정규근사의 %.2f 배입니다"
% (n_hoef / n_cheb, n_hoef / n_clt))
print(" n 체비쇼프 상한 호에프딩 상한 정규근사 참값")
for n in [100, 1000, 5000, 20000, 100000]:
cb = min(sig2 / (n * eps * eps), 1.0)
hf = min(2 * np.exp(-2 * n * eps * eps / rng_len ** 2), 1.0)
tv = 2 * (1 - float(Phi(eps * np.sqrt(n) / np.sqrt(sig2))))
print(" %9d %14.10f %14.10f %14.10f" % (n, cb, hf, tv))
print(" 체비쇼프는 1/n 로 줄고 호에프딩은 지수로 줄어듭니다")
print(" n 이 커질수록 호에프딩이 압도적으로 좋아집니다")
# --- 문제 2: 왜 지수가 나오는가 -----------------------------------------
print(" 체르노프 방법의 재료인 호에프딩 보조정리를 확인합니다")
x = np.arange(1, 7) - 3.5
print(" 람다 실제 E[e^{la X}] 보조정리 상한 분산만 쓴 값 상한/실제")
for la in [0.2, 0.5, 1.0, 2.0]:
act = float(np.mean(np.exp(la * x)))
ub = float(np.exp(la * la * rng_len ** 2 / 8))
vb = float(np.exp(la * la * sig2 / 2))
print(" %9.1f %16.8f %16.8f %16.8f %10.4f" % (la, act, ub, vb, ub / act))
print(" 보조정리는 분산을 (b-a)^2/4 = %.4f 로 잡습니다. 실제는 %.4f 입니다"
% (rng_len ** 2 / 4, sig2))
print(" 즉 %.4f 배 부풀린 분산을 쓰는 대가로 유계만으로 결론을 냅니다"
% (rng_len ** 2 / 4 / sig2))
print(" 최적 람다를 넣으면 지수 안이 -2 n eps^2 / (b-a)^2 이 됩니다")
print(" eps = %.2f 에서 최적 람다 = 4 n eps/(b-a)^2 이고 지수는 %.6f n 입니다"
% (eps, -2 * eps * eps / rng_len ** 2))
# --- 문제 3: 분산을 알면 더 좋아지는가 ---------------------------------
print(" 희귀 사건 p = 0.01 에서 세 상한을 견줍니다. 오차는 0.01 입니다")
p, e3 = 0.01, 0.01
v3 = p * (1 - p)
print(" n 실제 이항 꼬리 호에프딩 베른슈타인 호에프딩/실제 베른슈타인/실제")
pmf = np.array([1.0])
ber = np.array([1 - p, p])
keep = {}
for i in range(1, 20001):
pmf = np.convolve(pmf, ber)
if i in [100, 1000, 5000, 20000]:
keep[i] = pmf.copy()
for n in [100, 1000, 5000, 20000]:
k = np.arange(n + 1)
tail = float(keep[n][np.abs(k / n - p) >= e3 - 1e-12].sum())
hf = min(2 * np.exp(-2 * n * e3 * e3), 1.0)
bs = min(2 * np.exp(-n * e3 * e3 / (2 * v3 + 2 * e3 / 3)), 1.0)
print(" %9d %12.4e %12.4e %12.4e %10.3e %10.3e"
% (n, tail, hf, bs, hf / tail, bs / tail))
print(" 호에프딩은 분산을 보지 않아 희귀 사건에서 크게 느슨합니다")
print(" 베른슈타인은 분산을 써서 훨씬 날카롭습니다. 지수 안의 비는 %.2f 배입니다"
% ((e3 * e3 / (2 * v3 + 2 * e3 / 3)) / (2 * e3 * e3)))
# --- 문제 4: 여러 개를 한꺼번에 보장하려면 ------------------------------
print(" 가설이 M 개일 때 모두 동시에 보장하려면 오차가 얼마나 필요한지 봅니다")
n4, d4 = 10000, 0.05
print(" M 필요한 eps M = 1 대비 배수")
for Mh in [1, 10, 1000, 10 ** 6, 10 ** 9]:
e = np.sqrt(np.log(2 * Mh / d4) / (2 * n4))
e1 = np.sqrt(np.log(2 / d4) / (2 * n4))
print(" %12d %14.8f %14.4f" % (Mh, e, e / e1))
print(" M 이 10 억 배가 되어도 오차는 %.2f 배만 커집니다. 로그로 들어가기 때문입니다"
% (np.sqrt(np.log(2 * 10 ** 9 / d4)) / np.sqrt(np.log(2 / d4))))
print(" 상한이 실제로 성립하는지 모의실험으로 확인합니다")
for Mh in [10, 1000]:
e = np.sqrt(np.log(2 * Mh / d4) / (2 * 500))
X = rng.integers(0, 2, size=(4000, Mh, 500)).astype(float)
dev = np.abs(X.mean(2) - 0.5).max(1)
print(" M = %5d, n = 500, 보장 오차 %.6f, 실제 최대 초과율 %.4f (목표 %.2f 이하)"
% (Mh, e, float((dev > e).mean()), d4))
print(" 실제 초과율이 목표보다 훨씬 작습니다. 합집합 상한이 보수적이기 때문입니다")
# --- 문제 5: 유계가 아니면 어떻게 되는가 --------------------------------
print(" 유계도 아니고 분산도 무한한 파레토 a=1.5 에서 두 방법을 견줍니다")
n5, T = 10000, 4000
k5 = 31
blk = n5 // k5
err_mean, err_mom = [], []
for _ in range(T):
xs = 1.0 + rng.pareto(1.5, size=n5)
err_mean.append(abs(float(xs.mean()) - 3.0))
b = xs[:k5 * blk].reshape(k5, blk).mean(1)
err_mom.append(abs(float(np.median(b)) - 3.0))
em, eo = np.array(err_mean), np.array(err_mom)
print(" n = %d, 블록 %d 개, 시행 %d 회" % (n5, k5, T))
print(" 분위수 표본평균 오차 중앙값의 평균 오차 비")
for q in [0.5, 0.9, 0.99, 1.0]:
a, b = float(np.quantile(em, q)), float(np.quantile(eo, q))
print(" %13.2f %14.6f %16.6f %8.3f" % (q, a, b, a / b))
print(" 중앙값이 절반 이상에서는 조금 나쁘지만 꼬리에서 크게 좋습니다")
print(" 표본평균은 최악의 경우 오차가 %.4f 인데 중앙값 방법은 %.4f 입니다"
% (float(em.max()), float(eo.max())))
print(" 꼬리가 두꺼우면 지수 상한을 얻는 길이 평균이 아니라 중앙값입니다")
# 주사위 평균을 오차 0.1 안에서 실패확률 5% 이하로 알고 싶습니다
# 체비쇼프 n = 5834, 호에프딩 n = 4612, 정규근사 n = 1121
# 호에프딩은 체비쇼프의 0.791 배이고 정규근사의 4.11 배입니다
# n 체비쇼프 상한 호에프딩 상한 정규근사 참값
# 100 1.0000000000 1.0000000000 0.5581846502
# 1000 0.2916666667 0.8986579282 0.0640775070
# 5000 0.0583333333 0.0366312778 0.0000346711
# 20000 0.0145833333 0.0000002251 0.0000000000
# 100000 0.0029166667 0.0000000000 0.0000000000
# 체비쇼프는 1/n 로 줄고 호에프딩은 지수로 줄어듭니다
# n 이 커질수록 호에프딩이 압도적으로 좋아집니다
# 체르노프 방법의 재료인 호에프딩 보조정리를 확인합니다
# 람다 실제 E[e^{la X}] 보조정리 상한 분산만 쓴 값 상한/실제
# 0.2 1.05932288 1.13314845 1.06006829 1.0697
# 0.5 1.40484009 2.18420081 1.43991392 1.5548
# 1.0 3.20410835 22.75989509 4.29878891 7.1033
# 2.0 28.60689705 268337.28652087 341.49510099 9380.1605
# 보조정리는 분산을 (b-a)^2/4 = 6.2500 로 잡습니다. 실제는 2.9167 입니다
# 즉 2.1429 배 부풀린 분산을 쓰는 대가로 유계만으로 결론을 냅니다
# 최적 람다를 넣으면 지수 안이 -2 n eps^2 / (b-a)^2 이 됩니다
# eps = 0.10 에서 최적 람다 = 4 n eps/(b-a)^2 이고 지수는 -0.000800 n 입니다
# 희귀 사건 p = 0.01 에서 세 상한을 견줍니다. 오차는 0.01 입니다
# n 실제 이항 꼬리 호에프딩 베른슈타인 호에프딩/실제 베른슈타인/실제
# 100 6.3027e-01 1.0000e+00 1.0000e+00 1.587e+00 1.587e+00
# 1000 3.3315e-03 1.0000e+00 4.5721e-02 3.002e+02 1.372e+01
# 5000 2.4848e-10 7.3576e-01 1.2487e-08 2.961e+09 5.025e+01
# 20000 4.0316e-36 3.6631e-02 3.0395e-33 9.086e+33 7.539e+02
# 호에프딩은 분산을 보지 않아 희귀 사건에서 크게 느슨합니다
# 베른슈타인은 분산을 써서 훨씬 날카롭습니다. 지수 안의 비는 18.89 배입니다
# 가설이 M 개일 때 모두 동시에 보장하려면 오차가 얼마나 필요한지 봅니다
# M 필요한 eps M = 1 대비 배수
# 1 0.01358102 1.0000
# 10 0.01730818 1.2744
# 1000 0.02301807 1.6949
# 1000000 0.02958411 2.1783
# 1000000000 0.03493719 2.5725
# M 이 10 억 배가 되어도 오차는 2.57 배만 커집니다. 로그로 들어가기 때문입니다
# 상한이 실제로 성립하는지 모의실험으로 확인합니다
# M = 10, n = 500, 보장 오차 0.077405, 실제 최대 초과율 0.0065 (목표 0.05 이하)
# M = 1000, n = 500, 보장 오차 0.102940, 실제 최대 초과율 0.0037 (목표 0.05 이하)
# 실제 초과율이 목표보다 훨씬 작습니다. 합집합 상한이 보수적이기 때문입니다
# 유계도 아니고 분산도 무한한 파레토 a=1.5 에서 두 방법을 견줍니다
# n = 10000, 블록 31 개, 시행 4000 회
# 분위수 표본평균 오차 중앙값의 평균 오차 비
# 0.50 0.110328 0.206670 0.534
# 0.90 0.245623 0.305554 0.804
# 0.99 1.008407 0.372143 2.710
# 1.00 6.357181 0.462246 13.753
# 중앙값이 절반 이상에서는 조금 나쁘지만 꼬리에서 크게 좋습니다
# 표본평균은 최악의 경우 오차가 6.3572 인데 중앙값 방법은 0.4622 입니다
# 꼬리가 두꺼우면 지수 상한을 얻는 길이 평균이 아니라 중앙값입니다