飽和樣條和特征選擇藝術(shù)設(shè)計專業(yè)

《飽和樣條和特征選擇藝術(shù)設(shè)計專業(yè)》由會員分享，可在線閱讀，更多相關(guān)《飽和樣條和特征選擇藝術(shù)設(shè)計專業(yè)（26頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1. 簡介 樣條——具有連續(xù)性約束的分段多項式——廣泛用于擬合數(shù)據(jù)[1,5.1]。分段多項式的一個問題是它們的行為超出了它們的邊界結(jié)點，并且（典型地）在該范圍之外沒有限制地增長[1,5.2]。這種不穩(wěn)定性使得推斷是危險的; 從業(yè)人員必須注意避免查詢訓練數(shù)據(jù)范圍附近或之外的樣條模型。 平滑樣條算法[2] - [4]通過擬合自然樣條來改善這個問題，該自然樣條在邊界結(jié)點之后降低到較低階的多項式。最常用的各種光滑樣條是三次光滑樣條（在邊界結(jié)外部減少到線性的三度樣條）以及線性平滑樣條，這些樣條一直保持不變。我們提出的飽和樣條與線性平滑樣條密切相關(guān)。 平滑樣條使用或二次方復雜度概念，因此可以用

2、預先確定的密集結(jié)點集合擬合模型[1,5.4]。另一方面，自適應(yīng)回歸樣條[5]使用型懲罰，這可以導致自適應(yīng)選擇結(jié)點的稀疏集合。然而，自適應(yīng)回歸樣條不會在最大結(jié)點范圍之外降低到較低程度，因此可能會出現(xiàn)不穩(wěn)定性。 我們提出擬合自適應(yīng)回歸樣條曲線，其中對某個區(qū)間之外的樣條曲線的程度有明確的約束。我們稱這些樣條為飽和樣條。雖然我們采用的方法可以擴展到擬合具有任意導數(shù)約束的樣條曲線，但在本文中，我們將重點放在擬合數(shù)據(jù)范圍之外平坦（恒定）的線性樣條; 我們在8中提到對更高階樣條的擴展。我們證明飽和樣條繼承了自適應(yīng)回歸樣條的結(jié)點選擇屬性，同時其行為與數(shù)據(jù)邊界附近的自然樣條相似。 在飽和樣條坐標函數(shù)擬合廣義

3、相加模型[6]的背景下，我們還展示了我們方法的一個非常重要的好處：飽和約束自然導致變量選擇。我們不僅通過結(jié)點選擇來控制每個坐標函數(shù)的復雜性，而且在飽和條件下，變量上沒有結(jié)點表示變量不在模型中。對于自適應(yīng)樣條，這是不正確的，因為線性項是未被去除的，因此每個變量總是在模型中。缺乏特征選擇會傷害可解釋性，并且在某些情況下會導致泛化。 我們提出的飽和約束排除了線性函數(shù)，并且與自適應(yīng)樣條型懲罰配合，鼓勵坐標函數(shù)相同為零。因此，廣義相加模型適合于飽和樣條組件函數(shù)通常僅依賴于少數(shù)輸入特征。 像平滑樣條曲線和自適應(yīng)回歸樣條一樣，飽和樣條曲線是解決某些自然函數(shù)回歸問題的方法。我們將飽和樣條擬合問題作

4、為一個凸空問題上的凸優(yōu)化問題來解決，粗略地說就是擬合函數(shù)的二階導數(shù)。據(jù)我們所知，這種方法是新穎的。然后，我們將經(jīng)典的條件梯度方法[7]和[8]應(yīng)用于這個問題。在我們算法的每次迭代中，都會產(chǎn)生一個原子量度；此外，我們可以統(tǒng)一限制樣條函數(shù)中結(jié)點個數(shù)對應(yīng)的原子個數(shù)。（當我們操縱原子測量時，我們在有限總變差的所有測量空間上解決問題。）與標準坐標下降方法相反，在條件梯度方法的每次迭代中，調(diào)整兩個結(jié)點的權(quán)重。在完全校正步驟中，我們用和簡單的線性約束來求解有限維凸優(yōu)化問題。數(shù)值實驗表明該方法在實際中非常有效。 我們的優(yōu)化方法可以利用熱啟動，即它可以對擬合函數(shù)使用初始猜測。這使我們能夠有效地計算整個正則

5、化路徑，其代價通常只是解決正則化參數(shù)的一個值的問題的一小部分。由于我們的算法是基于條件梯度法，我們可以使用[9]的框架來計算一個可證明的次優(yōu)近似正則化路徑。當擬合廣義相加模型時，正則化路徑具有吸引人的特征：在正則化參數(shù)的臨界值處，新的回歸因子被帶入（或偶爾出于）模型，或新的結(jié)點被添加到（或從中刪除） 的現(xiàn)有坐標函數(shù)，因此我們的方法結(jié)合了特征選擇和結(jié)點選擇。 2. 單變量函數(shù)擬合 我們希望從數(shù)據(jù)集擬合一個連續(xù)的有界函數(shù) 要做到這一點，我們將選擇來最小化數(shù)據(jù)的不匹配或損失函數(shù)，但要受到鼓勵中規(guī)則性的約束條件以及我們在下面描述的額外約束條件和飽和度的限制。損失由以下公式給出：

6、其中是非負的，二次可微的，并且在它的第一個參數(shù)中是嚴格凸的。典型的損失函數(shù)包括（標準回歸，），或者（邏輯回歸，其中）。損失是函數(shù)的凸函數(shù)，僅取決于數(shù)據(jù)點處的的值。損失越小，越符合給定的數(shù)據(jù)。 我們通過限制非負正則化泛函的值來約束函數(shù)是簡單的。在本文中，我們將作為的微分的總變化量， ， 一個的凸函數(shù)。對于一個二次可微函數(shù)，我們已知， ， （1） 即正則化是二階導數(shù)的范數(shù)。（正如我們在下一節(jié)中所討論的那樣，總變差的現(xiàn)代定義把這種平等擴展到不可微函數(shù)。）我們對施加的總變差限是，其中是我們用來折衷模型的參數(shù)擬合度和模型規(guī)律。這種正則化約束隱含地約束幾乎無處不

7、在，其導數(shù)具有有限的總變差。 我們的模型將受到另一個約束，即它飽和（在區(qū)間[0,1]之外），這意味著它是[0,1]之外兩個區(qū)間上的（可能不同的）常量：對，；對，。換句話說，在[0,1]的標稱數(shù)據(jù)范圍外延伸為一個常數(shù)。就導數(shù)而言，這相當于要求存在且在[0,1]之外為零。 那么該擬合問題可以描述為 ； 滿足 （2） ，對， 其中為正則化參數(shù)。要確定的變量是函數(shù)，它是連續(xù)函數(shù)的矢量空間中的有限總變差的導數(shù)。這個擬合問題是一個無限維凸優(yōu)化問題。 在應(yīng)用中，問題（2）解決

8、了一系列值，這產(chǎn)生了正則化路徑。最終模型是使用一個保留集或交叉驗證來選擇的。對于，必須是常數(shù)，并且問題（2）減少到適合數(shù)據(jù)的最佳常數(shù)。隨著增加，的約束更小，并且我們的擬合模型變得更復雜; 最終我們期望過度擬合。例如，在回歸的情況下，對于滿足的損失函數(shù)和具有不同的數(shù)據(jù)，對于足夠大的來說，擬合函數(shù)是插值數(shù)據(jù)的分段線性函數(shù)。 3. 樣條函數(shù)和有界變差函數(shù) 在本節(jié)中，我們探討擬合問題與一次樣條的連接，即分段線性連續(xù)函數(shù)，其形式如下 ， （3） 其中。我們假設(shè)是不同的，并將它們稱為結(jié)點或簡單結(jié)。

9、標量是權(quán)重，是偏移量。我們將映射稱為鉸鏈函數(shù)，因此一階樣條是鉸鏈函數(shù)的有限線性組合加上一個常數(shù)。 3.1 有界變差函數(shù) 一個右連續(xù)函數(shù)是有界變差的，當且僅當在[0,1]上存在一個有符號的度量，滿足 ， （4） 其中，對，否則等于0。度量是唯一的；我們可以認為它是的導數(shù)。 也就是說，（4）基本上是微積分的第二個基本定理，其中被代替。 我們也有。（這稱為度量的總變差。）我們將使用符號來作為它的記號，以強調(diào)與有限維情況的相似性，或者當是可微的情況：.當度量是原子的時候，函數(shù)是分段常數(shù)，在

10、的支持下的點處發(fā)生跳躍。 3.2 樣條函數(shù)和有界變差導數(shù) 現(xiàn)在假設(shè)具有有界變差的右連續(xù)導數(shù)。從（4），運用以及微積分的基本定理，我們有 （5） （6） . （7） 這表明任何這樣的函數(shù)是鉸鏈函數(shù)的一個（可能是無限的）線性組合加上一個常數(shù)（即）。在這種情況下，度量可以被認為是的二階導數(shù)。 當是原子并且在有限集上被支持時，也就是說， ， 是形式（3）的一階樣條，其中。因此，一階樣條完全對應(yīng)于度量（大致二階導數(shù)）具有

11、有限支持的情況。 我們引入記號 （8） 來表示從度量導出的函數(shù)。粗略地說，這是度量的雙重積分或與度量μ有關(guān)的鉸鏈函數(shù)的（可能有無限個的）線性組合。從到的映射是線性的，那么我們有。圖1顯示了一個的簡單例子，它的一階導數(shù)和它的（原子度量）二階導數(shù)。 圖1：由原子度量產(chǎn)生的和。正則化函數(shù)就是中尖峰的絕對值之和。需要特別注意的是，中所有尖峰的（帶符號）和為零：也就是說，，這意味著飽和。 3.3 通過優(yōu)化度量擬合樣條 確定，我們可以通過最小化[0，1]上的有界測度和常數(shù)來解決擬合問

12、題（2）。度量是的二階導數(shù)，常數(shù)對應(yīng)于?？傋儾钫齽t化約束對應(yīng)于。當時，飽和度條件成立；為了確保當時，我們需要 換句話說，的飽和度對應(yīng)于具有總（凈）質(zhì)量零的。因此（2）可以改寫為 滿足， （9） 有界測度在[0，1]上，同時。這里會稍微多用一些記號：我們現(xiàn)在（以及本文的其余部分）認為是上的函數(shù)。 在上面，是將映射到由（8）給出的向量的線性算子。顯然是線性的，因為它是函數(shù)： 對的積分。我們將直接應(yīng)用條件梯度法來解決這個問題。 為了獲得關(guān)于優(yōu)化問題的直覺（9），我們可以認

13、為它是標準lasso的無限維模擬[10]。 lasso是優(yōu)化問題 滿足 （10） 的解決方案。這里是中的一個向量，是一個矩陣。忽略常數(shù)項，我們看到，（9）看起來非常類似于（10），其中起著的作用；的確，本質(zhì)上是一個有行和無限多列的矩陣。我們對lasso的直覺表明，應(yīng)該有屬于（9）的解是稀疏的，這意味著是原子的。就而言，稀疏性意味著存在一維樣條的原始函數(shù)擬合問題（2）的解。事實確實如此。定理1表明存在（9）的原子解，其支持不超過個點；換句話說，是一個具有的一階樣條。此外，在實際中（9）的解

14、將會支持遠遠少于個點。 定理1. 固定和，為（右連續(xù)）的有界總變差，并且在[0,1]之外為常數(shù)。那么就存在一個一階飽和樣條（最多有個結(jié)點），它在上與相匹配，并滿足。 證明: 不失一般性，我們假設(shè)。令。由于約束了總變差，所以在[0,1]上存在一個度量，使得： 也就是說，是一個無限多結(jié)的樣條。我們的想法是使用Caratheodory的凸包理論來看到，因為我們只關(guān)心在有限數(shù)量函數(shù)上的作用（基本上，我們只關(guān)心在上的值），所以我們可以用一種可在有限的點上支持的度量來替代。 為了使這個想法嚴謹，請注意矢量 必須位于（凸）組 的凸包中，因為。凸包的Caratheodory定理確保

15、了可以表示為從選取的最多個點的凸組合。讓這些個點由它們的標記表示，以及它們的權(quán)重，我們定義得到： 這里。因為，我們有。 # 對于本文的其余部分，我們將忽略常數(shù)項。使用我們提供的算法來處理常量項并不難，但這樣做確實會增加一些符號復雜性。也可以最小化，因為它不影響正則化項；由此產(chǎn)生的問題在中仍然是凸的。 4. 擬合樣條的條件梯度法 在本節(jié)中，我們概述了求解（9）（因此也是（2））的算法。為此，我們簡要回顧一下經(jīng)典的條件梯度法[7]和[8]中提出的測量理論版本。 我們需要解決的優(yōu)化問題（9）（沒有常數(shù)項c）是:

16、 滿足, （11） . 正如上一節(jié)所述，（11）是一個衡量空間的凸優(yōu)化問題。我們密切關(guān)注[8]中采用的方法，并直接對這個問題應(yīng)用條件梯度法。這種方法的主要好處是我們可以將注意力限制在原子度量上，即的形式為 . 通過簡單地存儲成對的的列表，這種形式的度量在計算機中很容易表示。定理1確保我們需要存儲的結(jié)的數(shù)量是絕對有界的，即我們的算法運行在有界存儲器中。當我們操縱原子測量時，我們解決了所有有界測量的問題（11）。 關(guān)于有限支持的原子測量值需要注意的一點是我們可以很容易地對結(jié)點位置固定的權(quán)重進行優(yōu)化，因為這對應(yīng)于適用于任何

17、標準算法的有限維凸優(yōu)化問題。我們的算法利用了這個事實，并且在每次迭代之間交替添加結(jié)對并對權(quán)重進行優(yōu)化。在后一步驟中，結(jié)可以（并且事實上最終必須）被去除。在附加和可選步驟中，結(jié)點可以在[0,1]內(nèi)連續(xù)移動，或者連續(xù)移動到相鄰的數(shù)據(jù)點。理論上的收斂不需要這一步，但可以在實踐中改善收斂性和最終解決方案的稀疏性。 4.1 條件梯度法 條件梯度法（CGM）解決了形式為 滿足, （12） 的約束凸優(yōu)化問題，變量。在上面，我們總是假定（凸）函數(shù)是可微分的。在CGM的每次迭代中，我們在當前迭代處

18、形成函數(shù)的標準線性逼近： 這里是函數(shù)在點方向d上的方向?qū)?shù)，定義為： 我們在這里使用方向?qū)?shù)可能會令人驚訝：對于上的可微函數(shù)，總是等于。方向?qū)?shù)對度量的凸函數(shù)的直接適用性促使我們傾向于使用它。 的凸性意味著是的下界，即： . （13） 在CGM的下一步中，我們在可行集上最小化這個一階近似： . 點稱為的條件梯度。請注意，在上提供了一個下界： . 特別地，我們可以限制點的次優(yōu)性： . （14） 圖2：函數(shù)在點處

19、的條件梯度法的單次迭代示意圖。集合是由實線表示的區(qū)間[-0.25,1.25]，一階近似值繪制為在處與相切的虛線。條件梯度是點-0.25。 可以看到（如[7]），這個界限減少到零，這意味著它可以用作（非啟發(fā)式）終止標準。確定之后，有幾個更新的選項。在本文中，我們將使用CGM的完全校正變體，它選擇在的凸包上來最小化。請注意，隨著增長，這最后一步可能會變得計算密集，并且實際上限制了條件梯度方法對這一步在計算上可行的問題的適用性。一種選擇是一旦在最小化步驟中未選擇先前的條件梯度，就刪除先前的條件梯度。Caratheodory定理確保我們需要跟蹤的先前的條件梯度集合然后以為界。然而，在實踐中，算法

20、通常在迭代之前終止。 算法1.完全校正條件梯度法 對,... 1、 線性化：. 2、 最小化：. 3、 更新：. 4.2 度量的條件梯度 在本小節(jié)中，我們將條件梯度法應(yīng)用于無窮維問題（11），我們在此重復： 滿足， （15） . 首先我們將表明，條件梯度即度量，可以被選擇為恰好支持兩個點，并且可以在時間上線性地計算。目標函數(shù)在點處的度量s方向上的方向?qū)?shù)由下式給出: 然后，我們可以將中的內(nèi)積與中的積分互換：

21、 . （16） 令。請注意在的情況下，僅僅是殘差 ，是殘差與位于的單個鉸鏈函數(shù)之間的相關(guān)性。條件梯度是以下優(yōu)化問題的解決方案： 滿足， （17） . 如果沒有積分約束條件，我們可以期望有一個解（17），即單點質(zhì)量：目標函數(shù)是標量值函數(shù)與有界度量的積分。我們將證明（17）總是有一個解決方案正好支持兩點。此外，我們將顯示這兩點可以按時間線性計算。 首先，我們將為（17）構(gòu)造一個特定的可行點，然后我們將顯示它達到最優(yōu)值。令. 定義 . 達到的目標值是 .

22、 我們將證明，對于（17）而言，任何可行的度量的目標值都低于或?qū)τ冢?1）是最優(yōu)的。將分解為兩個相互獨立的非負測度的差值： 。那么，當是可行的時，我們有 達到的目標值可以如下所示： 假設(shè)。那么上面的論證意味著是（11）的條件梯度，因此（14）意味著是最優(yōu)的。否則，我們有 這意味著 這證明了我們的斷言。 請注意，發(fā)現(xiàn)和在[0，1]上包含兩個單獨的優(yōu)化問題，而不是[0,1][0,1]上的一個。這些問題很容易通過網(wǎng)格來解決，但是在這種情況下，如果我們有權(quán)訪問數(shù)據(jù)點的排序矢量，它們可以在時間上精確地按時間線性地求解。為了看到這一點，我們對上面的擴

23、展了的目標函數(shù)： 如果對進行排序，我們可以精確地計算每對連續(xù)數(shù)據(jù)點之間的最小值，因為這只是計算一段時間內(nèi)線性函數(shù)的最小值。因此，在數(shù)據(jù)的一次傳遞中，我們可以精確地計算整體最小值。 在計算和之后，我們可以使用（14）來限制的次優(yōu)性： 通過選擇條件梯度，完全校正步驟是一個有限維凸問題。修復到目前為止遇到的結(jié)點位置，，通過求解下面的優(yōu)化問題我們至少可以做到完全修正算法。 （18） 這相當

24、于中的以下優(yōu)化問題： （19） 我們可以使用任何現(xiàn)有的算法來解決這個問題[11]，[12]。在我們的實現(xiàn)中，為了簡單起見，我們使用條件梯度法和線搜索。 通過以不斷增加的序列進行熱啟動，我們可以高效地計算近似的規(guī)則化路徑。事實上，我們甚至可以使用[9]的方法提供可證明的次優(yōu)路徑。 4.3 收斂 正如在ADCG [8]收斂的情況下，

25、立即從一般的Banach空間[7]，[13]，[14]中的條件梯度法證明。條件梯度法的收斂取決于曲率參數(shù)。是一個常數(shù)，所有和滿足以下不等式： 為了我們的目的，僅僅是和。有限的一個簡單的充分條件是在Lipschitz梯度下可積。如果是有限的，則條件梯度方法以至少的速率收斂（根據(jù)函數(shù)值），其中是迭代計數(shù)器。 5. 廣義相加模型 單變量樣條的一個自然應(yīng)用是將廣義相加模型[6]擬合為多元數(shù)據(jù)：。也就是說，擬合以下形式的函數(shù)： 其中每個是從到的簡單函數(shù)（這里是向量的第個坐標）。 我們可以在標量情況下模擬我們的方法，其優(yōu)化問題如下：

26、 （20） 這里是標量情況下使用相同正則化參數(shù)，即 在標量情況下，可以表明總是有一個最優(yōu)的，每個坐標函數(shù)都是一階飽和樣條。 這使得我們可以將（20）改寫為一個優(yōu)于度量的優(yōu)化問題。與標量情況相比，唯一的變化是該度量超過了集合——每個結(jié)現(xiàn)在都附加到特定的坐標上。換句話說，我們搜索以下形式的函數(shù)： 我們再次在的范數(shù)和正則化項之間具有平等性： 那么與（11）類似的是：

27、 （21） 標量情況下的條件梯度算法立即推廣到擬合廣義相加模型——唯一的區(qū)別是我們現(xiàn)在需要為同一個坐標找到一對結(jié)點。這涉及在[0,1]上解決對非凸優(yōu)化問題——同樣可以通過網(wǎng)格化或?qū)τ柧殧?shù)據(jù)進行排序來完成。 擬合廣義相加模型時，飽和樣條曲線比標準自適應(yīng)樣條曲線更具優(yōu)勢。在擬合廣義相加模型時，飽和約束的增加（在[0,1]之外是常數(shù)）自然會導致變量選擇。我們所說的變量選擇是指函數(shù)通常恰好為0。這是因為飽

28、和約束意味著線性坐標函數(shù)不再逃避正則化（事實上，它們是不可能的）。這與沒有飽和約束的標準自適應(yīng)樣條設(shè)置非常不同。在這種情況下，線性函數(shù)，即完全避開了正則化，因此基本上總是包含在模型中。線性函數(shù)在飽和約束下不是自由的（實際上，在函數(shù)0之外，它們是不可行的）。當我們求解（21）時，我們同時擬合非線性坐標函數(shù)，同時做可變選擇。 6. 相關(guān)現(xiàn)有成果 平滑樣條也可以解釋為無限維優(yōu)化問題[1,5.4]。實際上，（一階）平滑樣條解決了問題

29、 （22） 其中 （22）的解也是在[0,1]之外飽和的一階自然樣條。然而，（22）和（2）的解決方案是非常不同的。粗略地說，（22）類似于嶺回歸，而（2）類似于lasso。也就是說，（22）擬合具有與數(shù)據(jù)點一樣多的節(jié)點的函數(shù)，而（2）通常適合幾何節(jié)點很少的樣條函數(shù)。 另一種自適應(yīng)但不飽和的樣條是自適應(yīng)回歸樣條[5]。這些樣條函數(shù)也可以作為函數(shù)回歸問題

30、 （23） 的解決方案，其中 請注意，（2）沒有飽和約束。求解（23）（對于一階樣條）的算法基于定理1的擴展，這表明在數(shù)據(jù)點上實際上支持（23）的解決方案。因此可以使用lasso算法來找到解決方案。這也表明解決我們的問題的一個非常簡單的方法（9）：我們將個結(jié)點固定為數(shù)據(jù)的值，并且求解有限維凸優(yōu)化問題以找到權(quán)重。雖然像GLMNet [15]這樣簡單的坐標下降方法由于飽和約束不會立即適用，但可以修改它們以處理約束。 這種方法可行，但可能比我們的要慢得多，因為在實踐中，對于正則化參數(shù)的有用值，結(jié)點的數(shù)目通常遠小于，而對于個基函數(shù)

31、的有限維問題的條件非常不好。這就是說，我們提出的算法——對于分段線性情況——可以被解釋為有限維問題的前向有效集方法，其中我們避免明確評估所有基函數(shù)。我們測量理論方法的一個優(yōu)點是，它立即推廣到高階樣條，其中的支持不需要在數(shù)據(jù)點上，我們將在9中看到。在這種情況下（9）是真正無限維的，但我們的算法仍然可以直接應(yīng)用。 趨勢濾波是一種非參數(shù)函數(shù)估計技術(shù)，首先在[16]中介紹，這與自適應(yīng)樣條非常相似。事實上，如[17]所述，常數(shù)或分段線性情況下的趨勢濾波估計與自適應(yīng)樣條估計完全相同。趨勢過濾越來越普遍，因為它承認了非常有效強大的算法[17]，[18]。事實上，這些算法中的一些（尤其是適合GAMs的算法[

32、19]）可能適用于有效擬合飽和趨勢濾波器估計，這將受益于飽和樣條的特征選擇屬性和趨勢濾波的計算效率。 有許多用樣條函數(shù)擬合廣義相加模型的方法。一種方法（參見[20]）是使用（6）的組lasso版本： 擴展這個想法，[21]使用重疊組lasso來促進零、線性和非線性項之間的選擇。這些方法和我們的方法之間的差異類似于標準組lasso和lasso之間的差異。雖然兩者都進行特征選擇，但懲罰函數(shù)（6）不會在每個坐標函數(shù)內(nèi)進行結(jié)點選擇。 在[22]中討論了一種非常類似的擬合樣條的方法，它不需要結(jié)點選擇（但不包含飽和度）。 7. 實例 實施細節(jié)： 我們在Rust語言中提供了一個簡

33、單的，未優(yōu)化的實現(xiàn)。 我們算法的運行時間由完全校正步驟決定，即求解有限維凸優(yōu)化問題（19）。 我們使用近似牛頓法和標準條件梯度法來求解（19），并使用精確的分解。準確地說，在每次迭代中，我們形成目標函數(shù) 的二階近似，然后我們使用有（精確的）行搜索的標準條件梯度方法來最小化（超過約束集）。 請注意，這是一個固定步長為1的牛頓步驟：如GLMNET [15]中所述，為了提高速度，我們省略了行搜索。 我們選擇使用近端牛頓法，因為它相對簡單；其他標準凸面優(yōu)化算法可能會給出更好的實際性能，特別是當數(shù)據(jù)點數(shù)量非常大時。 在所有的例子中，我們仿射地預處理數(shù)據(jù)，使得所有訓練特征位于[0,1]中

34、，并且將相同的變換應(yīng)用于測試特征（因此可能具有[0,1]之外的值）。所有的劃分都是按照標準化的特點。對于骨密度和鮑魚數(shù)據(jù)集，我們選擇來最小化驗證集上的錯誤。對于垃圾郵件和ALS數(shù)據(jù)集，我們使用交叉驗證來估計。我們從訓練集中提取一個大小為100的隨機子集并訓練其余數(shù)據(jù)。對于每個隨機驗證/訓練分離，我們估計以最小化保持誤差，并將我們的最終估計作為50次試驗的平均值。 圖三：對于正則化參數(shù)的3個值，飽和樣條符合骨密度數(shù)據(jù)（顯示為散點）。頂部：；中間：；底部：。 7.1 骨密度 我們從一個簡單的[1,5

35、.4]中的單變量數(shù)據(jù)集開始。該數(shù)據(jù)集的響應(yīng)變量是女性青少年的兩次醫(yī)生訪視之間脊柱骨密度的變化與年齡的函數(shù)關(guān)系。有259個數(shù)據(jù)點，其中我們保留了120個用于驗證的數(shù)據(jù)點，剩下139個數(shù)據(jù)點，以適應(yīng)飽和脊柱。我們從平方損失開始。 結(jié)果如圖3所示，對于正則化參數(shù)的三個值。散點是訓練數(shù)據(jù)，實線是我們算法的飽和樣條擬合。該圖表明了與優(yōu)化樣條曲線的復雜性之間的明確聯(lián)系。樣本外驗證建議設(shè)置，從而驗證RMSE為0.036。 為了證明我們提出的方法與更一般的損失函數(shù)一起工作，我們將30個模擬的異常值添加到訓練集并且擬合了偽Huber損耗[23]，這是對Huber損失函數(shù)的平滑近似： 其中是在絕

36、對值損失和平方損失之間插值的參數(shù)。對于我們的實驗，我們?nèi)。淮致缘卣f，平方和線性損耗之間的轉(zhuǎn)換發(fā)生在附近。結(jié)果如圖4所示。這些圖表明我們的算法可以擬合除平方損失之外的損失，并且證實了偽Huber損失比基本平方損失函數(shù)對異常值更加強大。事實上，在驗證集上，最小二乘法擬合的最小RMSE為0.096，而偽Huber擬合達到0.038，僅比在將訓練數(shù)據(jù)加入異常值之前獲得的擬合稍差。 雖然這個一維問題非常容易，但它顯示了自適應(yīng)樣條罰款在平滑樣條上的一個優(yōu)點：最優(yōu)模型只有5個結(jié)點。 圖4：對于平方損失函數(shù)（左）和偽Huber損

37、失函數(shù)（右）的模擬異常值，飽和樣條擬合骨密度數(shù)據(jù)（以散點表示），每個值用于最小化測試集上RMSE的值。 7.2 鮑魚數(shù)據(jù)集 我們用飽和樣條坐標函數(shù)的廣義加法模型擬合來自UCI Machine Learning Repository [24]的鮑魚數(shù)據(jù)集。數(shù)據(jù)包括鮑魚8個特征的4177個觀察值以及目標變量鮑魚的年齡。我們將400個數(shù)據(jù)點作為驗證集合保留，剩下3777個數(shù)據(jù)點以適合模型。第一個特征（標記為性別）有三個值：雄性，雌性和少年，編碼值為0,1,2；其他7個是（直接）實數(shù)。任務(wù)是從特征中估計鮑魚的年齡。 交叉驗證表明我們選擇了，它實現(xiàn)了驗證集合RMSE為2.131。由于特征數(shù)量很少，

38、我們可以繪制整個廣義相加模型。每個圖表顯示的一個坐標函數(shù)作為[0，1]中標準化特征的函數(shù)。顯示了三個值的坐標函數(shù)，中間值對應(yīng)于最小化交叉驗證RMSE的值。當坐標函數(shù)為零時，即模型中未使用該特征時，它將顯示為藍色。我們可以看到，在強正則化（）的情況下，幾個坐標不被使用；對于最佳模型（），使用所有特征，其中一些特征僅具有小的影響?？吹叫砸蛩厝绾芜M入最佳模型是很有趣的。它對于男性或女性都是中性的，但是從其年齡預測中為少年鮑魚減去一小部分固定量。 這個數(shù)據(jù)集足夠小，我們可以使用粗網(wǎng)格[0，1]與標準自適應(yīng)樣條進行比較。對于這個實驗，我們使用GLMNET [15]來擬合具有標準自適應(yīng)樣條組件函數(shù)的GA

39、M。標準自適應(yīng)GAM擬合沒有變量選擇，實現(xiàn)了驗證集合RMSE為2.137，并沒有比飽和樣條模型差得多。然而，我們的算法選擇了更少的節(jié)點。擬合GLMNET時結(jié)節(jié)數(shù)量的增加可能是由于網(wǎng)格問題的條件不佳造成的。 圖5：用于使樣條廣義相加模型飽和的坐標函數(shù)適合于鮑魚數(shù)據(jù)以獲得正則化參數(shù)的三個值。 圖6：飽和樣條廣義相加模型的驗證誤差符合垃圾郵件數(shù)據(jù)集與調(diào)整參數(shù)。 7.3 垃圾郵件 我們將電子郵件分類為垃圾郵件和非垃圾郵件的兩類，并從ESL獲取數(shù)據(jù)集[1]。

40、該數(shù)據(jù)集包含來自4601封電子郵件的57個詞頻特征，以及其標簽為垃圾郵件或非垃圾郵件。遵循ESL中的方法[1]，我們對特征進行對數(shù)轉(zhuǎn)換，并使用標準訓練/驗證分割，訓練集為3065，測試集為1536個樣本。我們擬合了具有標準邏輯損失的飽和樣條廣義加法模型。 圖6顯示了驗證錯誤與正則化參數(shù)的關(guān)系。交叉驗證表明選擇。為了說明非線性坐標函數(shù)的好處，我們還包含了使用線性模型（使用GLMNet [15]擬合）獲得的最佳驗證誤差。 在正則化參數(shù)的情況下，該模型選擇57個特征中的55個。我們注意到我們的飽和樣條廣義加法模型比ESL的許多方法略微勝過[1]。例如，平滑樣條曲線產(chǎn)生5.3％的誤差，而我們的模型

41、誤差率遠低于5％。圖7顯示了的模型的坐標函數(shù)（一些）。坐標函數(shù)使用非常少的節(jié)點，使其易于解釋。 為了比較，我們使用標準自適應(yīng)樣條坐標函數(shù)來擬合GAM。為此，我們用20個節(jié)點對每個維度進行網(wǎng)格劃分，并用GLMNET [15]解決由此產(chǎn)生的有限維問題。請注意，自適應(yīng)樣條不會懲罰線性函數(shù)，因此不會選擇特征。自適應(yīng)樣條的最小誤差為4.8％，比飽和樣條要差得多。 圖7：的16個坐標函數(shù)，每個標有相應(yīng)的特征名稱。 圖8：驗證ALS數(shù)據(jù)集與正則化參數(shù)的MSE。 7.4 ALS 我們嘗試使用這個數(shù)據(jù)集來預測醫(yī)

42、學患者的ALS（肌萎縮側(cè)索硬化癥）的進展速度，通過功能評分的變化率來衡量，這是對功能障礙的測量。該數(shù)據(jù)集被分成1197個實例的訓練集和625個額外患者的驗證集。每個數(shù)據(jù)點的維數(shù)為369。我們用一個最小二乘目標函數(shù)擬合了一個具有飽和樣條函數(shù)的廣義加法模型。在[25,17.2]之后，我們使用均方差來衡量表現(xiàn)。 我們使用交叉驗證來估計的最優(yōu)值，其中保留大小為100個示例和50個樣本；這個程序建議。圖8顯示了驗證誤差與正則化參數(shù)；通過交叉驗證選擇的的值實現(xiàn)了低誤差。在同一圖上，我們還使用增強回歸樹和隨機森林顯示[25]的結(jié)果。最優(yōu)飽和樣條GAM模型只選擇了369個特征中的50個，而增強回歸樹使用了2

43、67。飽和樣條GAM模型與增強回歸樹和隨機森林相當。這是令人驚訝的，因為飽和樣條GAM沒有交互條件。它還使用了少得多的功能，進一步提高了解釋能力。 我們再次使用具有標準自適應(yīng)樣條坐標功能的GAM（使用GLMNET）來展示飽和度的優(yōu)勢。標準自適應(yīng)樣條擬合實現(xiàn)了0.547的MSE，比其他任何模型都差得多。我們推測這是因為非線性函數(shù)導致立即過擬合。事實上，去除未經(jīng)去除的線性函數(shù)并僅用鉸鏈擬合模型就可以得到與飽和樣條擬合非常相似的性能，這表明飽和度的主要優(yōu)勢在于去除未經(jīng)去除的線性函數(shù)。 飽和樣條的實用優(yōu)勢：這些實驗表明，飽和樣條曲線在小分類和回歸數(shù)據(jù)集上十分有效。 此外，實驗證明飽和樣條展示結(jié)

44、點選擇和特征選擇——在擬合GAMs的情況下。 雖然飽和樣條曲線比平滑樣條曲線（選擇完全密集的結(jié)集）選擇更少的節(jié)點并不奇怪，但我們的算法選擇的節(jié)數(shù)比即使與GLMNET適合的自適應(yīng)樣條曲線也有點令人驚訝。最后，垃圾郵件和ALS數(shù)據(jù)集展示了自適應(yīng)樣條曲線比自適應(yīng)樣條曲線飽和的一個主要優(yōu)勢：它們同時執(zhí)行非線性坐標函數(shù)擬合和特征選擇。這有助于泛化性能和可解釋性。特別是，對于ALS數(shù)據(jù)集，飽和樣條GAM通過僅選擇36個可用特征中的50個來實現(xiàn)自適應(yīng)樣條GAM的一半測試MSE。 8.高階樣條 在本文的大部分研究中，我們關(guān)注函數(shù)回歸問題（2），對一階導數(shù)和對零導數(shù)（函數(shù)本身）的飽和約束有一個總變差

45、約束。在本節(jié)中，我們考慮對高階導數(shù)的約束，導致高階樣條的解。 （24） 我們考慮以為指標的非參數(shù)函數(shù)估計問題族。這是函數(shù)回歸問題（2）的類比，其中對第階導數(shù)的總變差約束和對第階導數(shù)的飽和約束。本文中的飽和樣條情形是（24）的特例，其中。廣泛使用的立方自然樣條對應(yīng)于。注意，不同于自然樣條，自然樣條只為和的某些值定義，而這里對和沒有約束。 我們現(xiàn)在表明高階飽和樣條

46、一般解決（24）。由于是有界，所以存在一個度量那么對某些我們有： 在上面，所有迭代的積分發(fā)生次。 請注意，對于所有，的約束意味著多項式項單獨為零。 所以，我們有： 對于，我們可以消除非線性，即對于，只是的多項式的積分。我們可以從積分中將包含的項取出，得到x的多項式，其系數(shù)是的前個矩的非零倍數(shù)： 同樣地，我們注意到，由于這個多項式對于無限多點都是零，所有的系數(shù)必須為零。就度量而言，這意味著： 這表明的第階導數(shù)飽和的約束條件轉(zhuǎn)化為約束的所有時刻直到第個時刻。 雖然條件梯度變得更加復雜，但增加了更多的矩約束條件，但本文采用的方法仍然可以應(yīng)用

47、于（24），只要相當小——（24）的條件梯度步驟包含在上的非凸優(yōu)化問題。這是因為我們至少需要個點質(zhì)量來滿足時間約束。因此，擬合線性飽和的二次樣條曲線非常容易——事實上，這樣做的代碼與擬合分段線性飽和樣條曲線的代碼基本相同——但由于附加的線性條件，擬合到常數(shù)的二次樣條稍微困難一些對度量的約束。然而，對于較大的和值，我們不能再希望通過分析找到條件梯度，并且必須求助于遞歸網(wǎng)格或其他全局優(yōu)化算法來查找新節(jié)點的位置。 圖9：前兩幅圖分別顯示了時的條件梯度，其中和。虛線表示點質(zhì)量的位置：當時，條件梯度由三個點質(zhì)量組成。底部的圖表

48、顯示了相應(yīng)的度量。 9.變體和擴展 雖然飽和度往往是一個自然的先驗，但我們在本文中采用的方法也可以應(yīng)用于（9）上的其他（凸）變體。例如，我們可以添加約束條件，即擬合的函數(shù)是單調(diào)非遞減的，或者在給定的時間間隔內(nèi)取值。 一個簡單的算法擴展就是在[8]的精神中加入非凸優(yōu)化。在每次迭代中，我們調(diào)整原子量度的權(quán)重，但我們也可以調(diào)整結(jié)點位置。（19）中的目標在中是非凸的，但我們?nèi)匀豢梢栽噲D找到一個局部最小值。只要我們不增加目標函數(shù)，算法仍然保證收斂[8]。在一階樣條的情況下，我們可以使用這樣的事實，即結(jié)點可以在不失一般性的情況下選擇在數(shù)據(jù)點上以對結(jié)點位置進行離散調(diào)整。 為了擬合矢量值函數(shù)，

49、例如在多類別分類中，我們需要擴展（9）以使用矢量值度量。這是組lasso的自然測量理論模擬。 在多變量擬合問題中，特征之間存在顯著相互作用的問題可能會出現(xiàn)廣義相加模型。一種可能的解決方案是使用單層神經(jīng)網(wǎng)絡(luò)：即學習形式為 的函數(shù)。在上面，被限制在單位球中。但是，這種形式的網(wǎng)絡(luò)的條件梯度步驟是NP-hard [26]。然而，在許多實際應(yīng)用中，我們可能預期交互的程度是有限的。也就是說，每個都有界限基數(shù)。如果我們假設(shè)，即我們只適合配對相互作用，我們?nèi)匀豢梢詰?yīng)用條件梯度方法。在這種情況下，擬合函數(shù)是由基本元素 形成的變量對的函數(shù)的和，其中（連續(xù)）參數(shù)為和以及（指數(shù)）參數(shù)為和（即，）。（僅適用于當足夠小時）。這些函數(shù)捕獲（成對）變量之間的非線性關(guān)系。 10.結(jié)論 在本文中，我們提出了修改自適應(yīng)樣條回歸模型——即飽和約束。我們證明飽和樣條函數(shù)繼承自適應(yīng)樣條的結(jié)點選擇，并且在廣義相加模型的背景下具有非常重要的質(zhì)量：特征選擇。這允許飽和樣條廣義相加模型保持可解釋性，并且（至關(guān)重要）在應(yīng)用于多元數(shù)據(jù)時避免過擬合。我們還提出了一種基于標準條件梯度法求解任意凸損失飽和樣條估計問題的簡單有效算法。最后，我們將我們的算法應(yīng)用于多個數(shù)據(jù)集，展示了最終模型的簡單性。