樣本複雜度界

多少資料才夠？樣本複雜度精確地回答：學習者要達到目標準確度 epsilon、信賴水準一減 delta，需要多少訓練樣本。它是可學習性的貨幣——一個類別可學習，恰當這個數目有限、且僅隨你要求的準確度與信賴度多項式成長。把它想成貼在某個保證上的價格標籤，以樣本數計價。

對二元分類，典範界說：可實現情形約需「d 加上 log 一除以 delta，再全部除以 epsilon」個樣本，不可知情形則是同一分子除以 epsilon 的平方，其中 d 是 VC 維度——一除以 epsilon 是二次方還是一次方，正是慢速率與快速率之別。更精細的界以 Rademacher 複雜度、覆蓋數或間隔型量取代 d，以捕捉資料相依結構。透過機率方法或資訊論論證所證明的相符下界，顯示這些數目無法再減，從而釘住真正的難度。

樣本複雜度是學習理論的實務核心：它告訴你，手上的資料能否讓問題可行、準確度隨蒐集更多而如何縮放、以及哪些結構假設（間隔、稀疏、平滑）能換來更便宜的學習。它也框定了意在擊敗被動界的主動學習與半監督學習。提醒仍是慣常的最壞情況鬆弛——真實分布所需的樣本，往往遠少於與分布無關的界所預測的。