上界說明樣本足夠時某個算法能夠成功。下界提出另一問題:樣本更少時,是否存在任何算法能一致地成功?下面的困難不在於計算緩慢,而在於缺少資訊:從未觀察到的標籤仍可能取任一值。
打散集合上的困難族
設二元分類器類 打散互異的點 ,其中 。這就是說,這些點的每一種二元標記都由 中至少一個成員實現。設 為這些點上的均勻分布。學習器獲得 個來自 的獨立帶標籤樣本,其標籤由未知的固定目標 給出;學習器輸出可測二元分類器。學習器可以隨機化,也不必輸出 的成員;其內部隨機位獨立於目標和樣本。
記 。對隨機化學習器,風險的概率或期望同時涉及樣本和學習器的隨機位。
定理 2.3.1
(未見點下界)
對每個這樣的學習器,都存在某個固定目標 ,使得
特別地,若 ,存在某個固定目標滿足 。
證明
(對打散集合上所有標記求平均)
暫時獨立均勻地從 選取 個目標標籤,且這些標籤獨立於樣本輸入和學習器的隨機位。這個隨機目標僅用於求平均:打散性質保證每一種標記都由原類中的一個目標實現。對樣本點、其觀察到的標籤和學習器隨機位取條件。對於每個未出現在樣本中的點,它的目標標籤仍是獨立於所有這些資訊的公平二元隨機變量。不論學習器在該點預測甚麼,其條件錯誤概率都是 。
一個特定點未被抽到的概率為 。對所有點的條件錯誤求和並取平均,得到上述期望。由於這是對有限多個可實現目標標記求平均,至少有一個固定目標達到該值;在由此得到的學習問題中,這個目標在實際抽樣前選定。
若 ,Bernoulli 不等式給出 ,因此該目標的期望風險至少為 。由於 ,
整理得到所述概率下界。
證明透視
每個假設在求平均論證中的作用
這個證明只有一步不顯然:把未知目標換成隨機目標,對學習器能看到的一切取條件,然後發現每個未見標籤仍是公平硬幣。用到三個假設,各在一處。
打散性質只在由隨機標記回到原類時使用。它保證全部 種標記都可實現,因此平均是對 的真正成員取的。若改取 ,看過一個帶標籤樣本後所有標籤都已知,沒有任何隱藏資訊,平均誤差為 。
的均勻性以及標籤與樣本輸入的獨立性用在取條件這一步。獨立性使未見點的標籤在給定學習器全部所見資訊後仍是公平二元值,所以在該點任何預測的錯誤概率都不低於 。均勻性使每個點的權重為 ,且以相同概率 被漏掉;若 非均勻,同樣的計算給出 。
論證之所以閉合,是因為有限多個數的平均不超過其最大值,所以某個固定標記的期望風險至少等於平均。選出的標記依賴於學習器和 ,但不依賴樣本:隨機目標在學習問題本身中從不存在。Bernoulli 不等式一步以及由期望轉到概率一步屬於常規計算,只用到 。
即使允許輸出類外分類器和不受限計算,這也說明固定精度與置信度下所需樣本數量必須隨 至少線性增長。它並未說每個目標都困難,也未說學習器必然失敗;它本身也沒有證明對任意精度和置信度參數的完整依賴關係。
例。 若 、,則某個固定目標的期望風險下界為 。這裏是有放回地抽取四次:重複抽到同一點不會揭示新標籤,定理已經計入這種可能性。
置信度可能要求觀察稀有樣本
現在取兩個被打散的點 ,固定 。令 、。選取兩個可實現目標,它們在 處都標記為零,在 處的標記相反。令 為訓練輸入中沒有 的事件,則 。
在 上,兩個目標下帶標籤樣本和學習器獨立隨機位的聯合分布相同,且 在兩個目標下的概率相同。對於每個可能的輸出,其在 的二元預測至少與兩個目標之一不一致。在該目標下,風險至少為 。對兩個目標和學習器隨機性求平均,得出某個固定目標滿足
因此,若要保證兩個目標下的失敗概率均至多為 ,其中 ,必要條件是
第二個不等式利用 ()及 。所有對數均為自然對數。這是該困難族的必要條件,而不是一般 PAC 學習的充分樣本量。每個學習問題中的目標和分布都是固定的,不能在看到樣本後改變。
反例模式
訓練誤差為零不能證明泛化
錯誤命題:若分類器在訓練樣本上誤差為零,則其真實誤差很小。取 , 為 上全部 種標記的類, 為均勻分布,目標為 (依 的次序)。設樣本為 。分類器 與兩個觀察到的標籤都一致,故訓練誤差為 。但 在 、 處與 不同,所以 。而 本身同樣與此樣本一致,且 :樣本無法區分 與 。這兩次抽樣的輸入都落在 的概率為 ,而下界保證不論學習器如何,某個目標的期望風險至少為 。要修正這個命題,必須有控制整個類的陳述:當 相對於 的容量足夠大時,一致分類器才保證風險小;而依本定理,若 打散 個點, 至少須為 的量級。
下界說明了甚麼,又沒有說明甚麼
兩種構造作用不同。第一種統計打散集合上可以隱藏多少獨立標籤選擇。第二種使一個有資訊的點變得稀有,從而解釋對所要求失敗概率的對數依賴。兩者都沒有使用運行時間假設。某個算法在簡單分布或特定目標上表現很好,並不違反最壞情況的下界。
論證假設樣本獨立且預測為二元值。如果允許學習器主動查詢所選點的標籤,或者進一步限制數據分布和目標,這個證明並不會自動適用於改變後的學習模型。選出的困難目標可以依賴學習器,但樣本仍是在目標固定後才抽取。
練習與解答
快速檢查
(當 、 時,計算保證對某個目標成立的期望風險下界。)
解答 · 答案
。
快速檢查
(當 、 時,計算兩個目標中某一個的稀有事件失敗概率下界。)
解答 · 答案
。
快速檢查
(為甚麼學習器的內部隨機化不能消除未見點論證?)
解答 · 答案
連同觀察到的樣本一起對學習器隨機位取條件;每個未見標籤仍是獨立的公平二元隨機變量。
快速檢查
(第一個定理是否說每個目標的期望風險都至少為所示下界?解釋原因。)
解答 · 答案
不是。求平均只證明對該學習器及樣本量至少存在一個固定困難目標;其他目標可能很容易。