집중부등식 (Concentration Inequality)
쉽게 풀면
표본평균이 참값에서 크게 벗어날 확률이 얼마나 되는지 정확히 알고 싶지만, 원래 분포를 정확히 모른다면 정확한 계산이 불가능하다. 집중부등식은 이럴 때 '이 정도 이상 벗어날 확률은 절대 이 값을 넘지 않는다'는 보수적이지만 확실한 상한선을 제시해주는 부등식들이다. 마르코프 부등식, 체비셰프 부등식, 회프딩 부등식 등이 대표적이며, 표본 크기가 얼마나 커야 추정 오차를 원하는 수준 이하로 억제할 수 있는지를 이론적으로 계산하는 데 널리 쓰인다.
왜 중요한가
실제 데이터는 정확한 확률분포를 알 수 없는 경우가 대부분이라, 추정치나 알고리즘 출력이 참값에서 얼마나 벗어날 수 있는지를 보이려면 분포에 의존하지 않는 도구가 필요하다. 집중부등식은 이런 상황에서 표본 크기, 신뢰수준, 오차 범위 사이의 관계를 수학적으로 정당화해주기 때문에 통계적 학습 이론, 고차원 통계, 최적화 알고리즘의 수렴성 분석 등에서 이론적 뒷받침으로 반복해서 등장한다. 특히 머신러닝에서는 일반화 오차의 상한을 증명하거나 샘플 복잡도를 논할 때 핵심적인 역할을 한다.
논문에서는 이렇게 쓰입니다
통계적 학습 이론이나 고차원 통계학에서 추정 오차의 확률적 한계를 이론적으로 증명할 때 자주 사용된다.
최적화 및 머신러닝 이론에서 알고리즘의 수렴 속도를 분산까지 고려해 더 정교하게 분석할 때 흔히 쓰이는 표현이다.
네트워크 분석이나 조합론적 확률론처럼 개별 변수 간 의존성이 있는 경우에도 집중 현상을 보이기 위해 확장된 형태의 부등식이 활용되는 예시이다.
조금 더 깊게 보면
집중부등식들은 확률변수의 어떤 정보를 활용하는지에 따라 상한의 정밀도가 크게 달라진다. 체비셰프 부등식은 분산만 이용하므로 상한이 느슨한 편이고, 회프딩·베른슈타인·아즈마 부등식처럼 적률생성함수(moment generating function)를 이용하는 방법들은 오차 확률이 표본 크기에 대해 지수적으로 감소한다는 훨씬 강한 결과를 보여준다. 논문에서 어떤 부등식이 쓰였는지를 보면 확률변수들이 독립인지, 유계인지, 마팅게일 구조를 갖는지 등 어떤 가정이 전제되어 있는지 짐작할 수 있다. 최근에는 이러한 고전적 부등식들을 행렬이나 함수 값으로 확장한 행렬 집중부등식(matrix concentration inequality) 등도 고차원 통계와 딥러닝 이론 분석에서 자주 언급된다.
주의할 점
집중부등식이 제공하는 상한은 일반적으로 매우 보수적(느슨한 상한)이어서, 실제 오차 확률보다 훨씬 크게 나올 수 있다는 점을 감안해서 해석해야 한다.