[ML] Feasibility of Learning

Feasibility of Learning (Part 5)

Ultimate goal of learning

• 처음 보는 데이터에 대해서도 잘 예측하는 것, 처음 보는 문제도 잘 푸는 것
• learning produces a hypothesis g to approximate unknown f
  • 만약 성공적이면, g should approximate f well
  • E_out(g) = 0에 가까워야 함. 하지만 이것은 우리가 ascretain 하기 어려움
• 하지만 지금까지 E_out(g) = E_in(g)에 대해서 배워왔음.(호에프딩 부등식) => 이 과정이 잘 안 되는 경우가 오버 피팅 => regularizer, more data로 해결
• E_in(g)를 0으로 보내야 함! => 이 과정이 잘 안 되는 경우 언더 피팅 => better opt, complex model로 해결
• E_in(g)는 우리가 0으로 보낼 수 있을 것.

The feasibility of learning

• out-of-sample error를 0에 가깝게 해야 한다. 그러나 이것은 우리가 어떻게 할 방법이 없음.
• 2개의 질문으로 쪼개어 생각
  1. in-sample error와 out-of-sample error를 비슷하게 만들 수 있는가? => 잘 안되면 오버 피팅
  2. in-sample error를 충분히 작게 만들 수 있는가? => 잘 안되면 언더 피팅
• 호에프딩 부등식 => 1번 질문을 다룸
• 2번 질문 => 실제 데이터 확보 후 알고리즘 실행한 다음 해결해 볼 수 있음

Complexity of components of learning

• 앞서 2개의 질문으로 쪼갠 덕분에 머신러닝 컴포넌트에 대한 복잡도를 생각해 볼 수 있음.
• 2가지 타입의 복잡도
  • hypothesis set (H)의 복잡도
  • target function (f)의 복잡도
  • sample complexity (트레이닝 샘플 수)는 단순히 샘플의 숫자를 말함.

Complexity of hypothesis set H

• hypothesis의 복잡도는 M으로 표현하고, H라는 set의 cardinality M을 복잡도로 나타냄
• in-sample error와 out-of-sample error를 비슷하게 만들기 위해서는 M이 작은 less complex를 유지하는 것이 좋음.
• in-sample error 자체를 낮추기 위해서는 M이 큰 것(more complex)이 좋음 (무기고에 무기를 다양하게 만드는 것)
• 이를 approxiamtion-generalization trade-off라고 부름!
• approximation: in-sample error 낮추는 것
• generalization: in-sample err와 out-of-sample err 낮추는 것.

Complexity of target function f

• 직관적으로 복잡한 f가 간단한 f보다 learning 하기 어렵다.
  앞서 고려했던 두 가지 질문에 대해 다시 고려

1. in-sample error와 out-of-sample error를 비슷하게 만들 수 있는가?
2. in-sample error를 충분히 작게 만들 수 있는가?

• 호에프딩 부등식은 target function의 복잡도와는 연관이 없다.
• f가 복잡할수록 두 번째 질문의 in-sample error가 더 높아짐.
• 쉽게 말해서 f의 복잡도가 높아질수록 learn이 더욱 어려워짐.

Recap

• feasibility of learning for infinite M: 여기선 M을 model complexity라고 부름, hypothesis complexity랑 비슷하다고 일단 생각할 것.
• tradeoff
  • model complexity: up, E_in: down
  • model complexity: up, E_out - E_in: up
• 머신러닝 엔지니어의 최대 목표: 주어진 데이터셋에 맞는 최적의 model complexity를 찾는 것!!