아마도 대략적으로 정확한

최종 수정 2026.03.24

계산 학습 이론에서 아마도 대략적으로 정확한 (PAC) 학습은 기계 학습의 수학적 분석을 위한 프레임워크이다. 이 개념은 1984년 레슬리 밸리언트에 의해 제안되었다.[^1]

이 프레임워크에서 학습자는 표본을 받아 가능한 함수들의 특정 클래스에서 일반화 함수(가설이라 불림)를 선택해야 한다. 목표는 높은 확률로("아마도" 부분) 선택된 함수가 낮은 일반화 오류를 갖는 것이다("대략적으로 정확한" 부분). 학습자는 임의의 근사 비율, 성공 확률, 또는 표본의 분포가 주어지더라도 개념을 학습할 수 있어야 한다.

이 모델은 이후 잡음(잘못 분류된 표본)을 다루도록 확장되었다.

PAC 프레임워크의 중요한 혁신은 계산 복잡도 이론의 개념을 기계 학습에 도입한 것이다. 특히, 학습자는 효율적인 함수를 찾아야 하며(시간 및 공간 요구 사항이 예제 크기의 다항식으로 제한됨), 학습자 자체도 효율적인 절차를 구현해야 한다(필요한 예제 수가 개념 크기의 다항식으로 제한되며, 근사 및 가능성 한계에 의해 수정됨).

정의와 용어

PAC 학습 가능한 것에 대한 정의를 내리기 위해 먼저 몇 가지 용어를 소개해야 한다.[^2]

다음 정의에서는 두 가지 예시가 사용된다. 첫 번째는 이진 값 이미지를 인코딩하는 n 비트 배열이 주어졌을 때 문자를 인식하는 문제이다. 다른 예시는 구간 내의 점을 양성으로, 범위 밖의 점을 음성으로 올바르게 분류하는 구간을 찾는 문제이다.

X를 인스턴스 공간 또는 모든 표본의 인코딩이라 불리는 집합이라 하자. 문자 인식 문제에서 인스턴스 공간은 X={0,1}^n이다. 구간 문제에서 인스턴스 공간 X는 \mathbb{R}에서의 모든 유계 구간의 집합이며, 여기서 \mathbb{R}은 모든 실수의 집합을 나타낸다.

개념은 부분집합 c \subset X이다. 하나의 개념은 X={0,1}^n에서 문자 "P"의 그림을 인코딩하는 모든 비트 패턴의 집합이다. 두 번째 예시에서의 개념 예는 열린 구간의 집합 { (a,b) \mid 0 \leq a \leq \pi/2, \pi \leq b \leq \sqrt{13} }이며, 이들 각각은 양성 점만을 포함한다. 개념 클래스 C는 X 위의 개념들의 모음이다. 이것은 골격화된 4-연결(글꼴 너비가 1)인 비트 배열의 모든 부분집합의 집합이 될 수 있다.

\operatorname{EX}(c, D)를 확률 분포 D를 사용하여 예제 x를 추출하고 올바른 레이블 c(x)를 제공하는 절차라 하자. 이는 x \in c이면 1이고 그렇지 않으면 0이다.

이제 0<\epsilon,\delta<1 이 주어졌을 때, 알고리즘 A와 1/\epsilon, 1/\delta(및 클래스 C의 다른 관련 매개변수)에 대한 다항식 p가 존재하여, \operatorname{EX}(c, D)에 따라 추출된 크기 p의 표본이 주어졌을 때, 최소 1-\delta의 확률로 A가 동일한 분포 D를 가진 X에서 평균 오류가 \epsilon 이하인 가설 h \in C를 출력한다고 가정하자. 더 나아가 알고리즘 A 에 대한 위의 명제가 모든 개념 c \in C와 X 위의 모든 분포 D, 그리고 모든 0<\epsilon, \delta<1에 대해 참이면, C는 (효율적으로) PAC 학습 가능하다(또는 분포 무관 PAC 학습 가능하다)고 한다. 또한 A를 C에 대한 PAC 학습 알고리즘이라 할 수 있다.

동치성

일부 정칙성 조건 하에서 다음 조건들은 동치이다: [^3]

  1. 개념 클래스 C는 PAC 학습 가능하다.
  2. C의 VC 차원은 유한하다.
  3. C는 균등 글리벤코-칸텔리 클래스이다.
  4. C는 리틀스톤과 워머스의 의미에서 압축 가능하다.

같이 보기

  • 데이터 마이닝
  • 오류 허용 (PAC 학습)
  • 오컴 학습
  • 표본 복잡도

더 읽을거리

각주

[^1]: L. Valiant. ''[http://web.mit.edu/6.435/www/Valiant84.pdf 학습 가능한 것의 이론.]'' Communications of the ACM, 27, 1984.

[^2]: Kearns and Vazirani, 1-12쪽,

[^3]: Blumer, Anselm. 학습 가능성과 바프닉-체르보넨키스 차원. (1989년 10월)