一個關於數據存取方式的問題
統計查詢學習器詢問近似平均值,例如某個規則與標籤的相關性;它不接收用於形成這些平均值的單個樣本。這種限制是否重要?奇偶函數提供了一個鮮明的測試:單個有標籤樣本是二元域上的一個線性方程,而近似平均值卻可能在許多相互正交的候選中隱藏有關目標的線索。
下文的結果是針對明確統計查詢模型的資訊存取下界,不是密碼學困難性定理,也不是說普通樣本下奇偶函數難以學習。事實上,最後會給出從有標籤樣本高效精確學習的算法。下界還依賴查詢容差:允許極高精度的回答會改變一個查詢能夠透露的資訊。
模型與記號
定義 7.1.1
(均勻分布下的奇偶目標)
固定整數 ,令 ,並從 均勻抽取 。對每個子集 定義
未知目標是這 個奇偶函數之一,標籤準確地滿足 。分類器可以是任意函數 ,不一定是奇偶函數。對目標 ,其總體錯誤率為 。
輸入分布公開且固定,只有 未知。我們包含空集對應的常值一函數,以取得全部 個特徵函數。此處輸入和標籤使用正負號;稍後求解線性方程時會明確換成二進制位。正交性計算依賴均勻分布,此處不聲稱對任意輸入分布都有相同結論。
定義 7.1.2
(統計查詢存取與容差)
一個查詢是任意函數 。固定容差 ,針對目標 的預言機可返回任何滿足下式的實數 :
學習器知道 、均勻輸入邊緣分布和 ,可利用此前全部答案選擇下一查詢。每個答案計一次查詢;下文的 是每次運行及每個隨機種子上的最壞情況上限,不是期望查詢次數。保證必須對每個目標以及每個滿足容差條件的回答序列成立,包括由對手選擇的回答。此模型中學習器不接收單個有標籤樣本;我們不限制查詢或最終分類器的計算量,下界只計算查詢次數。
對優勢 ,錯誤率至多為 表示比隨機猜測好至少 。當 時,
因此達到該精度需要至少 的相關性。這個恆等式討論的是均勻總體分布,而不是某個有限樣本上的表現。
正交性限制一次查詢
定理 7.1.3
(奇偶特徵函數與單查詢計數引理)
在均勻分布下,
對任意查詢 定義
目標 下的期望為 。其期望與共同值 的距離超過 的目標,至多有 個。
證明
(正交性與 Bessel 不等式)
若 ,乘積 是非空對稱差 的奇偶函數。取對稱差中的一個座標;它是均值為零的獨立均勻正負號,因此整個乘積的期望為零。若 ,乘積恆為一。
個函數 對內積 構成標準正交族。對任意實值 ,有限維 Bessel 不等式給出
對上述查詢,兩個查詢值均在 ,所以 ,相關性平方和至多為一。若超過 個相關性的絕對值嚴格大於 ,其平方和就會超過一,矛盾,故得計數結論。
至於期望恆等式,對 寫出 ,再代入 即得。共同回答 由查詢和已知均勻邊緣分布決定,不依賴目標。
同樣的正交性也限制一個最終分類器。因為 ,Bessel 不等式給出
因此滿足 的目標奇偶函數至多有 個。這只討論一個固定的 ;下文證明還必須處理學習器在收到回答後才選擇 的情況。
概念視角分析
查詢讀取的是立方體上的傅立葉(Fourier)係數
在目標 之下,回答中唯一依賴目標的部分是 ,也就是 在 上函數的奇偶基下的係數。這 個函數構成一組基,所以 Bessel 不等式在這裏成為等式:。有界查詢的總譜權重至多為一,因此絕對值超過 的係數至多有 個。
對手回答下的查詢下界
定理 7.1.4
(確定性有限查詢下界)
若確定性學習器至多進行 個容差為 的查詢,並必須對每個目標及每個容差有效的預言機輸出錯誤率至多 的分類器,則
若右邊為負,此不等式沒有實際約束。查詢次數 是整數,因此正的非整數下界可以向上取整。
證明
(一個共同查詢記錄保留許多可能目標)
先讓確定性學習器與一個參考預言機互動:每個查詢 都回答與目標無關的 。這確定了至多 個查詢、相應參考回答以及一個最終分類器 。參考預言機只是構造記錄的工具,其回答不必對每個目標都有效。
對該記錄上的每個查詢,引理說明參考回答無效的目標至多有 個。刪去所有這些例外集合的並集,至少還剩 個目標。對於其中任一目標,每個參考回答都在容差內。由於學習器是確定性的,預言機給出這些答案時,它會提出完全相同的後續查詢並輸出同一個 ;自適應性不會使這條路徑分叉。
最終分類器計數說明, 對至多 個目標達到所需優勢。若 ,至少有一個剩餘目標既容許參考記錄,又使 失敗,矛盾。否定該嚴格不等式並整理,得到定理。
證明透視
自適應性在何處得到處理
證明並未假設學習器事先固定全部查詢。它沿著「每次都收到共同基準值」這一條記錄運行;自適應記錄確定後,才統計哪些目標使這條路徑上的每個回答都有效。這些目標對本次運行不可區分,即使其他回答序列可能使算法走向別處。
也有隨機化版本。設對每個目標及每個有效預言機,算法對自身隨機選擇的成功概率至少為 ,其中 。那麼必有
附加論證如下。對每個目標採用一個固定預言機策略:查詢 時,如果 與真實回答的距離在容差內,則返回它;否則返回精確期望。該策略對每次查詢都有效。固定學習器的隨機種子,將其運行與該種子對應的基準記錄比較。對均勻隨機目標,沿此記錄用並集界可知,發生至少一次偏離基準回答的概率至多為 。若從未偏離,輸出固定,而它至多對 個目標成功。再對隨機種子取平均,平均成功概率至多為
若所聲稱的保證對每個目標及這個有效策略都成立,其平均值至少為 ,整理便得下界。對手策略在隨機種子抽取之前固定,不需要知道種子。這並不是說每個可能的預言機回答都沒有資訊:精確回答可能比容差保證所要求的回答提供更多資訊。
例題
例題 7.1.5
(一次相關性查詢)
對固定子集 查詢 。若 ,其期望為一,否則為零。當容差小於 ,該查詢可以檢驗這一個候選,卻不能自動確定其餘 個候選中哪個正確。上面的下界適用於比這種簡單檢驗更一般的有界查詢,也適用於自適應選擇的查詢。
例題 7.1.6
(一個有限的數值下界)
取 、、,共有 個目標。若確定性學習器對每個目標及每個有效預言機都保證錯誤率至多為 ,它至少需要
次查詢。這是下界,並未給出恰用這麼多查詢的算法。固定正的 和 時,主項隨 指數增長;若 隨 縮小,則必須把該依賴代入公式,不能自動稱其為指數下界。
例題 7.1.7
(單個有標籤樣本給出線性方程)
寫 、,當 時令 ,否則令 。一個有標籤樣本給出
若有 個獨立均勻輸入,由各行 構成的 矩陣有非零核向量的概率至多為 :每個固定非零向量與一個均勻隨機行正交的概率為 ,各行獨立,而非零向量共有 個。因此對 ,取 ,不能唯一恢復目標的概率小於 。在滿秩事件上,高斯(Gauss)消去法可以多項式時間精確恢復 。
這一比較改變了提供給學習器的資訊,不能將統計查詢下界當作普通樣本模型中的計算困難性結論。
反例模式
假設類很大本身不能證明統計查詢下界
個奇偶目標確實很多,但數量本身不是證明。在某些模型中,一個精確實數回答可以編碼許多可能性,而一個查詢也可以同時涉及所有座標。下界使用了均勻分布下特定的正交性、每次查詢的有界值域,以及預言機可返回容差內任意答案的自由。去掉任一條件,都必須重新分析。
常見錯誤
常見錯誤
(假設預言機總給出精確均值)
精確期望是允許的回答,但統計查詢保證必須容忍 範圍內每一個回答。一個只有在預言機恰好透露精確值時才成功的算法,不滿足所述模型。反過來,這個對手容差下界也不是對必須返回精確期望的預言機的下界。
常見錯誤
(忽略容差如何隨維度變化)
確定性下界包含 因子。固定優勢和常數容差時,它關於 指數增長;若容差指數級縮小,下界可能很弱甚至沒有約束。透過樣本取得高精度查詢本身可能有成本,必須另行分析,不能悄悄略去。
容差為何是一種資源,可以透過一個具體模擬看出。如果獨立有標籤樣本只用於估計查詢均值,那麼對至多 個自適應有界查詢,固定 ,每次使用一批新的、大小滿足
的樣本,由 Hoeffding 不等式與並集界,以至少 的概率所有回答同時落在容差內。每一批新樣本都與此前記錄獨立。這是某個模擬方法的充分樣本界,並非對所有方法的下界。若 極小,此模擬相應昂貴;僅靠查詢次數定理不能量化這一成本。
總結
均勻分布下的奇偶特徵函數相互正交。有界查詢只能與有限個目標具有較大相關性,因此容差有效的基準回答可以使許多目標與同一條自適應記錄一致;最終分類器又只能對有限個目標具有固定優勢。所得查詢界依賴具體模型,同時存在從單個有標籤樣本高效精確學習的方法。
練習
快速檢查
(對 ,設 、。計算 及其在均勻 下的期望。)
利用 。
解答 · 答案
,因為 。獨立性和均勻正負號的零均值給出期望零。
快速檢查
(對 、、,用確定性定理給出 的整數下界。)
計算 並向上取整。
解答 · 答案
,。下界為 ;查詢次數為整數,所以 。
快速檢查
(令 。某統計查詢預言機對 的回答為 、容差為 。哪些奇偶目標與這一個回答相容?)
對四個目標分別計算查詢的真實期望。
解答 · 答案
查詢期望為 ; 時為一,其餘三個子集時為零。回答零對 超出容差,對 均有效。這排除了一個目標,但不能確定剩餘三個中的哪一個正確。
快速檢查
(對 、,要滿足文中滿秩概率保證,多少個獨立同分布有標籤樣本足夠?解釋每個樣本為何給出一個線性方程。)
用 。
解答 · 答案
文中充分樣本數為 。寫 後,標籤位滿足模二方程 ,所以每個有標籤對給出一行方程。八行不能確定五位向量的概率至多為 。