Version space

즉, specific hypothesis $s$, general hypothesis $g$ 에 대하여, $s\le h\le g$인 어떠한 $H$에 속하는 집합 h들의 집합이라고 할 수 있다.

• $s$: train data를 모두 만족시키며, 데이터에 맞추기 위한 필수적인 조건만 포함된 hypothesis set.
• $g$: train data를 모두 만족시키며, 가능한 한 적은 조건을 포함해 다양한 데이터를 포괄할 수 있는 hypothesis set.

$s$와 $g$는 Consistent하며, 즉 positive한 example(or instance)만 포함한다.

train data가 추가됨에 따라 점진적으로 업데이트 된다. 이 때, 새로운 데이터를 설명하지 못하는 (혹은 Shattering하지 못하는) hypothesis는 Version Space에서 제거된다.

즉, Shattering 혹은 설명 여부가 Version Space의 dimension을 결정한다.

Ill-posed problem

---

Overfitting이 발생하게 된다면, Version Space의 가설들이 지나치게 train data에 Consistent하게 되어서, test data에 대한 prediction이 제대로 이루어지지 못하는 문제를 말한다.

• Version Space 너무 넓은 경우:
  • 데이터에 noise가 많거나, 학습 데이터가 충분하지 않아 여러 hypothesis가 train data를 만족시켜 version space가 커지는 경우.
  • 이 경우 진짜 해의 구분이 어려워진다.
• Version Space가 너무 작은 경우:
  • 과도한 제약의 모델로 인해, 데이터의 다양한 패턴을 설명 불가능한 경우.
  • Train data 마저도 제대로 설명하지 못하는 경우가 생길 수 있다.

즉, 너무 복잡한 Version Space가 생기게 되어 발생하는 문제가 된다.

Inductive bias

---

• hypothesis space를 설정하는 것 또한 이 일부이다.
• SVM
• KNeighbors Classifier

보통, 단순한 모델일수록 Generalization이 더 잘 이루어지게 한다.
곧 이는 Variance와 Bias의 trade-off 관계로 이루어지는데, Bias가 상승함에 따라 Variance가 적어지게 되며 Overfitting을 방지한다.

다만, 너무 단순한 모델이라면 Underfitting이 발생하게 되니 이에 유의해야 한다.