[단단한 머신러닝 연습문제 해답] 1장: 서론

문제 1.1

표 1.1에서 만약 인덱스 1과 4 두 개의 샘플만 포함하고 있을 때, 이에 상응하는 버전 공간을 나타내라.

풀이

먼저 두 샘플의 정보를 확인합니다.

번호	색깔	꼭지	소리	좋은 수박?
1	청록	말림	탁함	예 (양성)
4	오흑	약간 말림	둔탁함	아니오 (음성)

버전 공간이란 “양성 샘플은 맞게, 음성 샘플은 틀리게 분류하는 가설들의 집합”입니다.

Step 1. 샘플 1(양성)을 맞추는 가설 후보를 나열합니다. 각 속성은 “정확한 값” 또는 ”*(모두 허용)” 중 하나를 쓸 수 있으므로 $2^3 = 8$ 가지입니다.

(청록, 말림, 탁함)
(청록, 말림, *)
(청록, *, 탁함)
(*, 말림, 탁함)
(청록, *, *)
(*, 말림, *)
(*, *, 탁함)
(*, *, *)         ← 샘플 4도 양성으로 분류 → 제거

Step 2. 이 중에서 샘플 4(음성)를 잘못 양성으로 분류하는 가설을 제거합니다.

(*, *, *)는 모든 샘플을 “좋은 수박”으로 분류하므로, 음성인 샘플 4도 양성으로 분류해버립니다. 따라서 제거합니다.

따라서 버전 공간은 다음 7개입니다.

(청록, 말림, 탁함)
(청록, 말림, *)
(청록, *, 탁함)
(*, 말림, 탁함)
(청록, *, *)
(*, 말림, *)
(*, *, 탁함)

문제 1.2

단일 논리곱을 사용하여 가설 표현을 비교하고, 논리합 정규식(DNF)을 사용하여 가설 공간에 더 강력한 표현 능력을 입혀라. 만약 최대 k개의 논리곱을 포함하는 논리합 정규식을 사용하여 수박 분류 문제의 가설 공간을 표현한다면, 총 몇 가지 종류의 가능한 공간이 있을지 계산해 보아라.

풀이

먼저 용어를 정리합니다.

논리곱(AND절): (색깔=청록) ∧ (꼭지=말림)처럼 조건들을 AND로 묶은 것
논리합 정규식(DNF): 여러 AND절을 OR로 연결한 것 → (조건A) ∨ (조건B)

단일 논리곱만 쓰면 하나의 패턴만 표현할 수 있지만, DNF를 쓰면 “여러 패턴 중 하나라도 해당되면 수박”으로 표현할 수 있어 훨씬 유연합니다.

가설 공간 크기 계산:

표 1.1 기준으로 속성값의 수는 색깔 2가지, 꼭지 3가지, 소리 3가지입니다.

단일 논리곱 가설에서는 각 속성에 대해 특정 값을 지정하거나, 아무 값이나 허용하는 *를 사용할 수 있습니다. 따라서 가능한 단일 논리곱 가설의 수는:

$(2+1)(3+1)(3+1) = 48$

최대 k개의 논리곱을 OR로 연결하는 DNF의 수는:

$\sum_{i=1}^{k} \binom{48}{i}$

단, 일반화된 논리곱들은 서로 포함 관계를 가질 수 있으므로, 서로 다른 DNF 표현이 실제로는 같은 분류 함수를 나타낼 수 있습니다. 따라서 이 값은 중복 표현을 포함한 계산입니다.

참고: 만약 *를 허용하지 않고 완전히 구체적인 값만 쓰는 minterm 기준으로 계산하면 $2 \times 3 \times 3 = 18$ 개가 되고, 이 경우 DNF 수는 $\sum_{i=1}^{k}\binom{18}{i}$ 가 됩니다.

문제 1.3

만약 데이터에 노이즈가 있다면 가설 공간 중에 모든 훈련 샘플과 일치하는 가설이 존재하지 않을 가능성이 있다. 이러한 경우에 가설 선택을 할 수 있는 귀납 편향을 만들어 보아라.

풀이

노이즈가 있다는 게 무슨 의미일까요?

완전히 똑같이 생긴 수박인데 한 번은 “좋은 수박”, 한 번은 “나쁜 수박”으로 레이블이 달린 경우입니다. 이러면 두 샘플을 동시에 만족하는 가설이 없어서 버전 공간이 비어버립니다.

이럴 때 쓸 수 있는 귀납 편향(가설 선택 기준):

단순한 가설 선호 (Occam’s Razor): 훈련 오차를 일부 허용하더라도 가장 단순한 가설을 선택합니다.
다수결 기준: 틀리는 샘플 수가 가장 적은 가설을 선택합니다.
정규화(Regularization): 훈련 오차와 복잡도를 동시에 최소화하는 가설을 선택합니다. 수식으로 표현하면:

$h^* = \arg\min_h \left[ \text{훈련오차}(h) + \lambda \cdot \text{복잡도}(h) \right]$

여기서 $\lambda$ 는 복잡도에 얼마나 벌점을 줄지 조절하는 값입니다.

핵심은 “모든 샘플을 완벽히 맞추려 하지 말고, 노이즈를 어느 정도 무시할 수 있는 기준을 도입하자”는 것입니다.

문제 1.4* (심화)

다른 성능 측도를 사용해도 ‘공짜 점심은 없다’가 여전히 성립함을 증명하라.

$E_{ote}(\mathfrak{L}_a|X,f) = \sum_h \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x})\, \ell(h(\boldsymbol{x}),f(\boldsymbol{x}))\, P(h \mid X, \mathfrak{L}_a)$

풀이

NFL 정리가 뭔가요?

“어떤 알고리즘도 모든 문제에서 평균적으로 가장 좋을 수 없다”는 정리입니다. 알고리즘 A가 어떤 문제에서 잘 되면, 반드시 다른 문제에서는 더 나빠집니다.

증명:

두 알고리즘 $\mathfrak{L}_a$ 와 $\mathfrak{L}_{a'}$ 에 대해, 가능한 모든 목표 함수 $f$ 에 대해 합산하면:

$\sum_f E_{ote}(\mathfrak{L}_a|X,f) = \sum_f \sum_h \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x})\, \ell(h(\boldsymbol{x}),f(\boldsymbol{x}))\, P(h \mid X, \mathfrak{L}_a)$

합산 순서를 바꾸면:

$= \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_h P(h \mid X, \mathfrak{L}_a) \sum_f \ell(h(\boldsymbol{x}),f(\boldsymbol{x}))$

여기서 핵심은 $\sum_f \ell(h(\boldsymbol{x}),f(\boldsymbol{x}))$ 부분입니다.

$f$ 가 가능한 모든 함수에 걸쳐 균등하게 분포한다고 가정하면, 특정 입력 $\boldsymbol{x}$ 에 대해 가능한 모든 레이블 값이 $f(\boldsymbol{x})$ 로 동일한 횟수만큼 등장합니다. 따라서 이 합은 $h(\boldsymbol{x})$ 가 어떤 값이든 상관없이 알고리즘과 무관한 상수가 됩니다.

또한 $\sum_h P(h \mid X, \mathfrak{L}_a) = 1$ 이므로, 전체 식은 알고리즘 $\mathfrak{L}_a$ 에 전혀 의존하지 않습니다.

따라서:

$\sum_f E_{ote}(\mathfrak{L}_a|X,f) = \sum_f E_{ote}(\mathfrak{L}_{a'}|X,f)$

분류 오차율이나 레이블에 대해 대칭적인 손실 함수처럼, 가능한 모든 목표 함수에 대해 평균을 냈을 때 특정 예측값이 구조적으로 유리하지 않은 일반적인 분류 성능 척도에 대해서도 ‘공짜 점심은 없다’는 결론은 유지됩니다. ∎

문제 1.5

머신러닝이 인터넷 검색의 어떤 부분에서 어떤 역할을 하는지에 대해 기술하라.

풀이

인터넷 검색 시스템은 크게 세 단계로 나뉘며, 각 단계에서 머신러닝이 핵심 역할을 합니다.

① 쿼리 이해 단계: 사용자가 검색어를 입력할 때

오타 교정: “수방” → “수박”으로 자동 수정
검색 의도 파악: “사과”가 과일인지 회사(Apple)인지 분류
연관 검색어 추천: 입력 중 자동완성 제안

② 문서 검색 및 랭킹 단계: 어떤 결과를 보여줄지 결정할 때

Learning to Rank: 쿼리와 웹페이지의 관련성 점수를 학습하여 결과 순위를 결정
스팸 페이지 필터링: 품질이 낮거나 악의적인 페이지를 자동으로 분류하여 제거
초기 검색 시스템에서는 PageRank 같은 링크 기반 알고리즘이 중요했지만, 현대 검색 시스템에서는 Learning to Rank, 신경망 기반 의미 검색, 클릭 피드백 학습 등이 함께 사용됩니다.

③ 사용자 경험 개선 단계: 결과를 보여준 이후

클릭률(CTR) 예측: 사용자가 어떤 결과를 클릭할지 예측하여 랭킹 피드백으로 활용
개인화: 사용자의 검색 히스토리, 위치, 관심사를 학습하여 맞춤 결과 제공
광고 매칭: 검색어에 가장 적합한 광고를 학습 기반으로 선택