動機
如果能看見權重如何構造、誤差由甚麼量控制,以及需要多少運算單元,普適近似的存在結論便更具體。多變量不能只照搬一維插值:不同座標的權重會相乘。ReLU 網絡只有分段仿射運算,沒有精確乘法閘,所以必須近似乘法,再追蹤誤差如何沿構造累積。
本節分開兩個任務。張量網格先給出經典連續插值器,誤差由目標的連續模控制;有限 ReLU 電路再近似每個插值權重乘積。相加兩種誤差,便得到明確網絡保證。所得大小隨維數可能非常昂貴。把這個代價寫出來,正是理解「普適」的內容,不能把它藏在一個名稱後面。
架構也須交代清楚。我們計算無環電路中的純量 ReLU 閘,仿射邊可跨過中間層,然後說明如何轉成通常逐層網絡。閘數不是稠密可訓練參數數目,也不證明學習算法能用少量樣本推回這些權重。近似、最優化及統計問題不能互相偷換。
定義
定義 6.1.1
(目標類、網格帽函數與電路大小)
設 ,,且 、。取整數 ,網格寬度 ,定義
其中 、。帽函數非負且和為一。每個網格頂點 的權重為 。大小計算 ReLU 閘,容許仿射組合及輸出偏置;深度是輸入至輸出路徑上最多經過的 ReLU 閘數。
邊界帽函數只是同一公式的限制。每個網格區間只有兩個帽函數非零,就是通常線性插值權重。因此張量乘積亦非負且和為一。理想插值器為 ,頂點數 。
概念視角代數
張量帽插值器在每個格子上是多重線性的
在格子 上記 。這時 的每個因子是 或 ,所以 對每個 分別是至多一次的多項式;它是在 個角點取值 的唯一這類函數。 時就是雙線性插值 ,而權重的乘積正是 ReLU 乘法器需要近似的對象。
對整數 ,令 是平方函數在 的等距 段線性插值器。令 為投影到 的截斷映射,定義近似乘法
輸入始終在 ,故平方評估留在已聲明區間。這個截斷公式沒有聲稱在無界輸入上近似乘法。
定理/命題
定理 6.1.2
(具明確誤差預算的構造近似)
在上述假設下,有 ReLU 電路 滿足
一個構造至多使用 個 ReLU 閘,深度至多 。若 ,要誤差不超過 ,充分選擇是
一般連續目標也可任意準確近似,只須把 換成連續模 。
定理 6.1.3
(有限仿射區域限制精確性與準確度)
把通常 ReLU 網絡限制在一條線段,若隱藏層寬度為 ,輸出至多有 個仿射區間。任何至多 段的分段仿射函數,在 近似 的一致誤差至少為 。因此有限 ReLU 網絡不能在一個線區間上精確表示二階導數非零的二次函數。
區域界通常不銳利,亦不表示每組權重都實現那麼多區間。下界先依真實區間數成立,換成架構上界仍有效但可能較弱。它只用一條線的限制,未聲稱為最佳多維下界。
證明思路
以下依次證明兩個定理。第一個證明把精確的插值誤差與另行控制的乘法誤差相加。
證明
(先精確插值,再近似乘法)
理想權重和為一,而在 有正權重的頂點都與它相距至多 。所以
一般連續目標用同一論證得到 。立方體緊緻性令連續模趨零,也給有限幅度界 。這一步的插值完全精確,尚未加入神經運算誤差。
在區間 ,平方函數的線性插值超出目標 。平方網格寬度為 ,故誤差非負且至多 。插值器又有折點公式
它只需 個 ReLU 加仿射項。由 ,未截斷乘法的誤差至多 。真實乘積在 ,而對該區間的 有 ,故截斷不增加誤差。記 ,乘法輸出在 、閘數為 、深度至多二。
逐次近似 因子乘積:先取 ,再取 。因真實與近似部分乘積都在 ,
歸納得誤差至多 。
對每個頂點構造 ,再令 。係數幅度界給 ,與插值誤差相加便得誤差界。即使不共享帽函數,每個頂點只需 個帽閘,以及 個各有 閘的乘法器,這就證明了所述大小上界。先一層帽函數,再逐次兩層乘法,深度就是 。最後,當 時 ;當 時乘法項至多 。
證明透視
截斷與頂點數在哪裏起作用
證明有兩個互相獨立的誤差來源,由一次三角不等式連接:插值誤差只用 Lipschitz 假設與單位分解,電路誤差只用幅度界 與乘法器精度。兩個估計互不相干,所以參數可以依次選取:先為插值選 ,再為電路選 ,因為 取決於 。
截斷用了兩次,而歸納兩次都需要。它令每個近似部分乘積留在 ,於是下一個乘法器的參數留在 具有所述精度的區間 內;它也容許使用 ,阻止較早的誤差被放大。因子 出現,是因為獨立近似的乘積未必仍精確和為一,所以要對全部係數的誤差取絕對值相加。若要刪去這個因子,須有新的正規化或局部性論證。有些特殊乘法器保留額外的零值性質,可支援更銳利構造,但不能未經證明便套到目前電路。
轉成相鄰層網絡時,可用恆等 ReLU 傳遞之前的閘輸出及立方體輸入,因這些量非負。依電路深度排列,至多需 個單元,再接仿射輸出。這是刻意粗糙的轉換,只證明它屬通常有限前饋架構,並非最小寬度。計參數還須計邊;無環電路的加權有向邊至多 ,這也只是未利用稀疏性的粗界。
第二個定理只需一個計數論證和平方函數的一條恆等式。
證明
(逐層計算切點,再用二階差分)
從輸入線段的一個區間開始。在每個既有區間,下一層各預激活都是線參數的仿射函數;非恆零者至多一個零點,恆零者不產生切點。因此寬度 的一層至多把每段分成 段,歸納即得乘積界,輸出仿射層不再切分。
至多 段中,必有一段長 。若仿射函數 在此段近似平方,誤差至多 ,從平方恆等式
減去仿射恆等式 。三個誤差項總絕對值至多 ,故 。這同時證明定量限制與不可能精確表示。
大小公式透露的限制
網格頂點數 隨維數迅速增加,尚未計乘法精度已昂貴。這顯示廣泛目標類的維數困難。若目標只依賴少數座標或本身有組合結構,可以另建較有效構造,但本定理沒有這些假設,不能暗中借用例子裏的特殊結構。
這個上界容許權重隨目標與精度而改變,並未規定一套固定有限權重同時近似所有目標。輸出係數由頂點函數值決定,網格斜率則隨精度改變。若額外限制權重大小、量化精度或數據取得方式,就須重新追蹤那些限制,不能直接聲稱現有閘數已包含其成本。
Yarotsky 的研究論文分析更銳利的平方及乘法子網絡。本節使用基本等距插值,自行追蹤常數,並未聲稱平方閘的多項式成本是深度相關結果中的最佳界。
例題詳解
例題 6.1.4
(兩個輸入的乘積)
對 ,一個雙線性格已精確插值:只有 的標籤非零,權重就是 。直接把輸入送入 ,至多需二十九個閘、深度二,誤差至多 。這利用了代數結構;若機械套用每頂點重複構造,會多算許多不必要閘。
例題 6.1.5
(追蹤保守但有效的預算)
取 。選 ,有 ;再選 ,因 。插值誤差為 ,乘法項為 ,合計小於 。閘數至多 ,深度三。這是構造上的充分預算,不代表每個目標都需要一萬六千多個閘。
例題 6.1.6
(線限制也約束多變量網絡)
兩個隱藏層寬度為三及四時,任何輸入線上至多有 個仿射區間。若目標沿該線為 ,一致誤差至少 。界雖弱但非零;其他方向維數增加不能移除這條線已有的限制。實際區間數更少時,下界還更強。
常見錯誤
反例模式
精確乘法不是有限 ReLU 運算
若有限網絡能在單位正方形精確表示 ,沿 限制後便會精確表示 ,與有限區域定理矛盾。正確做法是在聲明的有界範圍使用近似乘法,再傳播其誤差。
一致連續性給足夠細網格的存在,沒有已知連續模則未提供數值速率。閘數也不指定稠密參數、位元精度或樣本複雜度。本構造使用全部頂點的真實目標值;數據不同的學習程序須另證如何取得相當資訊。深度增加可以擴大區域上界,卻未證明某算法一定用得到。
常見錯誤
(在選網格之前先定乘法精度)
電路項 含有 ,所以只能在定下 之後再選 。若按猜測的網格選定 ,之後再加密網格,電路項便隨 增大,誤差預算不再成立。在 的例子中,保留 而把網格加密至 ,則 ,電路項約為 ,單此一項已超過 。
常見錯誤
(把未截斷的部分乘積送入下一個乘法器)
乘法器的保證只對 中的輸入成立。沒有 ,近似部分乘積可能稍稍越出 ;下一次平方評估便可能離開 ,在那裏 只是線性外推,沒有 的保證,遞推亦失去 這個界。截斷每個乘法器只多用兩個閘,卻正是歸納成立的原因。
總結
張量帽函數控制經典插值,平方閘近似乘法,截斷維持組合運算的有效範圍。於是誤差與大小都可明確追蹤。有限仿射區域同時給出真實限制,讓構造普適性與架構約束並列研究。
練習
快速檢查
(在一段網格上驗證帽函數和為一,再推導張量權重和為一。)
在 到 的區間上記 。
解答 · 答案
在 與 之間,只有 與 為正,值為 與 ,其中 。和為一,端點亦成立。所有張量乘積之和可分解成各座標帽函數和的乘積,因此仍為一。
快速檢查
(取 ,求平方閘及乘法器的誤差界,並計算乘法器的 ReLU 閘數。)
解答 · 答案
平方誤差至多 ,乘法誤差至多 ,閘數為 。它們是一致上界,截斷可改善個別位置的誤差。
快速檢查
(三個 中的數逐次相乘,每個模組誤差至多 且輸出截斷至 。求總誤差界,並指出所需的歸納條件。)
解答 · 答案
第一次乘法誤差至多 。把這個近似值乘以第三個數時,因第三因子不超過一,傳遞下來的誤差不會放大;新模組再加至多 ,合計至多 。截斷確保中間近似因子留在下一模組誤差保證所適用的定義域,這正是歸納能繼續的條件。
快速檢查
(至多十段的分段仿射函數在 近似 ,可得甚麼一致誤差下界?與十段等距插值的誤差比較。)
解答 · 答案
下界為 。取 ,等距線性插值的精確最大誤差為 ,因為插值器比 高出 。減去常數 後函數仍連續且分段仿射,誤差落在 ,所以誤差 可以達到:對十段而言這個下界是銳利的。