[머신러닝] 학습의 기본 원리 (The Learning Problem)

1. 학습 문제의 구조

기계학습의 핵심 질문은 단순합니다: "유한한 데이터로 미지의 규칙을 배울 수 있는가?" 이 질문에 답하려면, 학습 문제를 구성하는 네 가지 요소를 이해해야 합니다.

X입력 공간

Y출력 공간

f목표 함수

H가설 집합

g ≈ f

학습 결과

훈련 데이터

(x₁, y₁), ..., (xₙ, yₙ)

위 다이어그램의 요소에 마우스를 올려 상세 설명을 확인하세요

핵심 통찰

학습이란 를 직접 관찰할 수 없는 상황에서, 유한한 훈련 데이터 만을 가지고 가설 집합 안에서 에 가장 가까운 함수 를 찾는 과정입니다.

2. 학습 가능성의 정의 — PAC 학습

Valiant(1984)는 "학습 가능하다"를 엄밀하게 정의했습니다. 핵심 아이디어는 확률적 보장입니다: 완벽한 학습은 불가능하지만, "높은 확률로, 근사적으로 정확한" 학습은 가능합니다.

PAC 정의 (비형식적)

클래스 가 학습 가능(learnable)하다 ⟺ 알고리즘 가 존재하여, 모든 목표 함수 와 모든 분포 에 대해:
를 만족하는 를 다항 시간 내에 출력한다.

매개변수 는 정확도 요구 수준을 제어합니다. 아래 슬라이더로 를 조절하며 확률과 오차 한계가 어떻게 변하는지 확인해 보세요.

정확도 매개변수 h = 10

성공 확률 (Probably)

≥ 90.0%

1 − 1/10

오차 한계 (Approximately)

≤ 10.0%

1/10

h = 10: 성공 확률 90%, 오차 10.0% 이하. 합리적인 수준입니다.

왜 '확률적'인가?

확률은 두 곳에서 발생합니다.
첫째, 훈련 데이터의 무작위 샘플링(운이 나쁘면 편향된 데이터를 받을 수 있음).
둘째, 근사의 불완전성(가 와 모든 곳에서 일치하지는 않음).
가 두 가지를 동시에 제어합니다.

3. 세 가지 학습 패러다임

학습 문제는 알고리즘에 어떤 정보가 주어지는가에 따라 세 가지로 나뉩니다.

📋

지도 학습

Supervised Learning

Valiant의 PAC 프레임워크가 바로 이 패러다임을 형식화한 것입니다. 학습 알고리즘은 (x, f(x)) 쌍을 받아 미지의 f를 근사합니다. 스팸 필터, 의료 진단, 이미지 분류 등이 대표적 응용입니다.

입력 x

정답 y = f(x)

함수 g 학습

핵심: 무엇이 정답인지 직접 알려준다

4. 일반화의 문제

학습의 진짜 목표는 훈련 데이터에서 잘 하는 것이 아니라, 본 적 없는 데이터에서도 잘 하는 것입니다. 이것이 일반화(generalization) 문제이며, 과 의 차이로 측정됩니다.

훈련 샘플 수 N = 5

가설 공간 크기 |H| 큼

19%

E_in

훈련 오차

30%

E_out

일반화 오차

일반화 격차: 10.2% — ✓ 양호

선택 편향 (Selection Bias)

에서 을 최소화하는 를 선택하면, 그 의 은 을 과소추정합니다.
100명이 동전을 10번 던져서 앞면이 가장 많은 사람을 뽑는 것과 같습니다 — 뽑힌 사람의 결과는 동전의 실제 확률을 반영하지 않습니다.
가 클수록 이 편향이 심해집니다.

일반화의 두 가지 조건

① 이 충분히 크면 큰 수의 법칙에 의해 (고정된 에 대해).
② 가 충분히 작으면 선택 편향이 제한되어, 선택된 에 대해서도 .

5. 귀납적 편향

학습이 가능하려면 를 제한해야 합니다. 이 제한을 귀납적 편향(inductive bias)이라 부릅니다. "어떤 종류의 함수가 답일 것이다"라는 사전 가정이며, 이것 없이는 일반화가 불가능합니다.

모든 함수

f (목표)

다항식의 차수를 제한합니다. d가 작으면 표현력이 부족하고(과소적합), d가 크면 과적합 위험이 있습니다. 적절한 d를 선택하는 것이 핵심입니다.

과적합 위험

중간

일반화 가능성

가능 (조건부)

No Free Lunch 정리

모든 가능한 목표 함수 에 대해 평균적으로 잘 작동하는 학습 알고리즘은 존재하지 않습니다.
어떤 에서 잘 하려면, 다른 에서 성능을 포기해야 합니다.
를 제한하는 것은 "이 종류의 에 집중하겠다"는 명시적 선택입니다.

오컴의 면도날

동일한 을 달성하는 여러 가설이 있을 때, 더 단순한 가설을 선택하라.
단순한 에서 찾은 가 더 잘 일반화될 가능성이 높기 때문입니다.
이것은 MDL(최소 기술 길이) 원리와 깊이 연결됩니다.