假設(shè)空間
令c表示“概念”（concept），這是從樣本空間X到標(biāo)記空間Y的映射，它決定示例x的真實(shí)標(biāo)記y。若對(duì)任何樣例（x,y）有c(x)=y成立，則稱c為目標(biāo)概念；所有我們希望學(xué)得的目標(biāo)概念所構(gòu)成的集合稱為“概念類”（concept class），用符號(hào)C表示。給定學(xué)習(xí)算法L，它所考慮的所有可能概念的集合稱為“假設(shè)空間”（hypothesis space），用符號(hào)H表示。由于學(xué)習(xí)算法事先并不知道概念類的真實(shí)存在，因此H和C通常是不同的。學(xué)習(xí)算法會(huì)把自認(rèn)為可能的目標(biāo)概念集中起來構(gòu)成H，對(duì)H中的每一個(gè)h，由于并不能確定它是否真是目標(biāo)概念，因此稱為假設(shè)。顯然，假設(shè)h也是從樣本空間到標(biāo)記空間的映射。若目標(biāo)概念c屬于H,則H中存在假設(shè)能將所有示例按與真實(shí)標(biāo)記一致的方式完全分開，我們稱該問題對(duì)學(xué)習(xí)算法L是可分的（separable），或者稱為“一致的”（consistent）；若c不屬于H，則H中不存在任何假設(shè)能將所有示例完全正確分開，稱該問題對(duì)學(xué)習(xí)算法L是“不可分的”（non-separable）或“不一致的”（non-consistent）。一般而言，假設(shè)空間越大，其包含任意目標(biāo)概念的可能性越大，但是從中找到某個(gè)具體目標(biāo)概念的難度也越大。當(dāng)假設(shè)空間大小有限時(shí)，我們稱其為“有限假設(shè)空間”，否則稱為“無限假設(shè)空間”。
