[Deep learning book] 5.2.1 The No Free Lunch Theorem

5.2.1 The No Free Lunch Theorem

• no free lunch theorem
  -  machine learning algorithm can generalize well from a finite training set of examples
  
  
• number of examples & error
  - the quadratic model, the training error increases as the size of the training set increases
  - larger datasets are harder to fit.
  - the quadratic model does not have enough capacity to solve the task, so its test error asymptotes to a high value
  - The test error at optimal capacity asymptotes to the Bayes error
  - The training error can fall below the Bayes error, due to the ability of the training algorithm to memorize specific instances of the training set

• number of examples & capacity
  - As the training set size increases, the optimal capacity

---

5.2.1 The No Free Lunch Theorem

• no free lunch theorem
  - 특정 문제에만 최적화된 머신 러닝 알고리즘은 다른 문제에서는 좋은 성능을 낼 수 없다. 
  
  
• number of examples & error
  - quadratic model ( 2차 ) 은 데이터 세트가 커질수록 이해하기 어렵기 때문에 오차 증가 
  - quadratic model ( 2차 ) 은 capacity 가 충분하지 않기 때문에 test error 가 Bayes error 점근선보다 높은 값을 가짐 
  - optimal capacity 모델의 test error ( 빨간색 ) 은 Bayes error 값에 가까워짐
  - optimal capacity 모델이 train set 을 학습할 때, 각 데이터들을 암기할 수 있기 때문에 train error 는 Bayes error 보다 낮아질 수 있음 

• number of examples & capacity
  - 훈련세트 크기가 증가하면 optimal capacity 도 증가