epsilon representation

학생 때 열심히 배웠던 epsilon–delta 논법이 있다.

해석학, 미적분에서 극한을 엄밀하게 정의하는 방법으로 등장하는, 어찌 보면 “수학적 엄밀성의 첫 관문” 같은 개념이다.

(\lim_{x \rightarrow a} f(x) = L)
(\forall \epsilon > 0, \exists \delta > 0) such that
if (0 < |x-a| < \delta), then (|f(x) - L| < \epsilon)

고등학교 때 참고서에서 처음 보고, 대학교에서는 해석학 수업 중간고사에서 끊임없이 연습하던 바로 그 논법이다. 처음엔 다소 형식적으로 느껴지지만, 사실 이 구조는 굉장히 강력하다.

핵심은 단순하다:

“출력 오차 (\epsilon)을 마음대로 작게 요구해도,
입력을 (\delta)만큼 잘 조절하면 항상 그 요구를 만족시킬 수 있다.”

---

요즘 공부하고 있는 learning theory에서도, 이와 매우 닮은 구조를 다시 만나게 된다. 바로 ε-representative sample이라는 개념이다.

Sample (S) on distribution (D) is (\epsilon)-representative (w.r.t. hypothesis class (H)) if
[
\forall h \in H,\quad |L_D(h) - L_S(h)| \leq \epsilon
]

여기서

• (L_D(h) = \mathbb{P}_{(x,y)\sim D}(h(x) \neq y)): 전체 분포에서의 true error
• (L_S(h)): 샘플 (S) 위에서 계산한 empirical error

이다.

---

이 정의를 처음 보면, 묘하게 ε–δ 논법이 떠오른다. 실제로 구조적으로 보면 상당히 비슷하다.

구조 비교

• ε–δ:

  • (|f(x) - L| < \epsilon)
  • “함수값이 극한값에 가깝다”

• ε-representation:

  • (|L_D(h) - L_S(h)| < \epsilon)
  • “샘플 기반 추정이 실제 분포와 가깝다”

둘 다 공통적으로

“두 값의 차이를 (\epsilon) 이하로 통제한다”

는 구조를 갖고 있다.

---

하지만 여기서 중요한 차이가 하나 있다.

ε–δ 논법은 완전히 결정론적(deterministic)이다. 조건 (0 < |x-a| < \delta)를 만족하면, 결과는 항상 성립한다.

반면 learning theory에서는 상황이 다르다.

• 샘플 (S)는 확률적으로 뽑힌다
• 따라서 위의 조건은 보통 이렇게 강화된다:

“높은 확률로 (S)가 ε-representative이다”

즉, 실제로는 다음과 같은 형태가 된다:

[
\mathbb{P}_{S \sim D^m}\left( \forall h \in H,\ |L_D(h) - L_S(h)| \le \epsilon \right) \ge 1 - \delta
]

여기서의 (\delta)는 이제 완전히 다른 의미를 가진다. 해석학에서의 입력 범위가 아니라,

“이 조건이 깨질 확률 (failure probability)”

을 의미한다.

---

이걸 한 문장으로 정리하면 이렇다:

• ε–δ 논법:

  “입력을 잘 제한하면, 출력은 반드시 ε 안으로 들어온다”

• learning theory:

  “충분히 큰 샘플을 쓰면, 높은 확률로 오차가 ε 안으로 들어온다”

---

개인적으로 흥미로운 점은, 학부 때는 ε–δ를 “형식적인 정의”로만 느꼈는데,

learning theory를 공부하다 보니 그 구조가 다른 분야에서 다시 등장한다는 것이다.

단지 변수의 의미만 바뀌었을 뿐,

• ε: 여전히 “허용 오차”
• (\delta): 이제는 “확률적 실패 허용”

이라는 식으로 재해석된다.

---

이러한 구조는 자연스럽게 PAC learning으로 이어진다.

PAC(Probably Approximately Correct)라는 이름 자체가 이미 모든 것을 말해준다:

• Approximately (ε): 얼마나 정확해야 하는가
• Probably (δ): 그 정확도가 얼마나 높은 확률로 보장되는가

---

PAC learning의 핵심 정의는 다음과 같은 형태를 가진다:

[
\mathbb{P}_{S \sim D^m}\Big( L_D(h_S) \le \epsilon \Big) \ge 1 - \delta
]

여기서

• (h_S): 샘플 (S)로부터 학습된 hypothesis
• (\epsilon): 허용 오차
• (\delta): 실패 확률

이다.

---

이제 구조를 다시 보면, 우리가 앞에서 본 두 개념이 하나로 합쳐진다.

• ε-representation:
  [
  |L_D(h) - L_S(h)| \le \epsilon
  ]

• 확률적 보장:
  [
  \mathbb{P}(\text{good sample}) \ge 1 - \delta
  ]

이 둘이 결합되면

“좋은 샘플이 나올 확률이 높고,
그 샘플에서는 empirical error가 true error를 잘 근사한다”

는 그림이 된다.

---

여기서 핵심적인 구조는 다음과 같이 요약된다:

• 해석학:
  [
  \forall \epsilon > 0,\ \exists \delta > 0
  ]

• PAC learning:
  [
  \forall \epsilon, \delta > 0,\ \exists m
  ]

즉,

ε를 줄이기 위해
해석학에서는 입력 범위 (\delta)를 조절하고,
learning theory에서는 샘플 수 (m)을 조절한다.

---

결국 두 이론은 같은 질문을 던지고 있다:

“원하는 만큼 정확하게 만들려면, 무엇을 조절해야 하는가?”

• 해석학의 답: 입력을 정밀하게 제한하라
• 학습이론의 답: 데이터를 충분히 확보하라

---

이 관점에서 보면, ε–δ 논법은 단순한 정의가 아니라

오차를 통제하는 하나의 보편적인 프레임워크

이고,

PAC learning은 그것을

확률과 데이터의 언어로 확장한 형태

라고 볼 수 있다.

---

세상에는 이런 순간들이 있다.
겉보기에는 전혀 다른 분야처럼 보이는데, 조금 더 깊이 들어가 보면 같은 구조가 반복해서 등장하는 순간들.

ε–δ 논법에서 시작된 사고 방식이 learning theory에서 다시 나타나고, PAC learning으로 정리되는 것을 보면,

수학은 새로운 것을 배우는 과정이라기보다,
이미 알고 있던 구조를 다른 곳에서 다시 발견하는 과정인지도 모른다.

---

아마 그래서 수학과 물리를 좋아하게 되는 것 같다.

계산이 맞아떨어지는 즐거움 때문이 아니라,

서로 멀리 떨어져 있던 개념들이
하나의 구조로 연결되는 순간

그 장면이 주는 감각 때문이다.

---

그리고 그런 연결을 한 번 보기 시작하면,
이후에는 계속해서 비슷한 패턴이 눈에 들어온다.

ε–δ 논법도, ε-representation도, PAC learning도,
결국은 같은 말을 하고 있었던 것처럼.

---

이것이 아마, 공부와 연구를 계속하게 만드는 이유일 것이다.