饱和样条和特征选择艺术设计专业

1. 简介 样条具有连续性约束的分段多项式广泛用于拟合数据1,5.1。分段多项式的一个问题是它们的行为超出了它们的边界结点，并且（典型地）在该范围之外没有限制地增长1,5.2。这种不稳定性使得推断是危险的; 从业人员必须注意避免查询训练数据范围附近或之外的样条模型。平滑样条算法2 - 4通过拟合自然样条来改善这个问题，该自然样条在边界结点之后降低到较低阶的多项式。最常用的各种光滑样条是三次光滑样条（在边界结外部减少到线性的三度样条）以及线性平滑样条，这些样条一直保持不变。我们提出的饱和样条与线性平滑样条密切相关。平滑样条使用或二次方复杂度概念，因此可以用预先确定的密集结点集合拟合模型1,5.4。另一方面，自适应回归样条5使用型惩罚，这可以导致自适应选择结点的稀疏集合。然而，自适应回归样条不会在最大结点范围之外降低到较低程度，因此可能会出现不稳定性。我们提出拟合自适应回归样条曲线，其中对某个区间之外的样条曲线的程度有明确的约束。我们称这些样条为饱和样条。虽然我们采用的方法可以扩展到拟合具有任意导数约束的样条曲线，但在本文中，我们将重点放在拟合数据范围之外平坦（恒定）的线性样条; 我们在8中提到对更高阶样条的扩展。我们证明饱和样条继承了自适应回归样条的结点选择属性，同时其行为与数据边界附近的自然样条相似。在饱和样条坐标函数拟合广义相加模型6的背景下，我们还展示了我们方法的一个非常重要的好处：饱和约束自然导致变量选择。我们不仅通过结点选择来控制每个坐标函数的复杂性，而且在饱和条件下，变量上没有结点表示变量不在模型中。对于自适应样条，这是不正确的，因为线性项是未被去除的，因此每个变量总是在模型中。缺乏特征选择会伤害可解释性，并且在某些情况下会导致泛化。我们提出的饱和约束排除了线性函数，并且与自适应样条型惩罚配合，鼓励坐标函数相同为零。因此，广义相加模型适合于饱和样条组件函数通常仅依赖于少数输入特征。 像平滑样条曲线和自适应回归样条一样，饱和样条曲线是解决某些自然函数回归问题的方法。我们将饱和样条拟合问题作为一个凸空问题上的凸优化问题来解决，粗略地说就是拟合函数的二阶导数。据我们所知，这种方法是新颖的。然后，我们将经典的条件梯度方法7和8应用于这个问题。在我们算法的每次迭代中，都会产生一个原子量度；此外，我们可以统一限制样条函数中结点个数对应的原子个数。（当我们操纵原子测量时，我们在有限总变差的所有测量空间上解决问题。）与标准坐标下降方法相反，在条件梯度方法的每次迭代中，调整两个结点的权重。在完全校正步骤中，我们用和简单的线性约束来求解有限维凸优化问题。数值实验表明该方法在实际中非常有效。我们的优化方法可以利用热启动，即它可以对拟合函数使用初始猜测。这使我们能够有效地计算整个正则化路径，其代价通常只是解决正则化参数的一个值的问题的一小部分。由于我们的算法是基于条件梯度法，我们可以使用9的框架来计算一个可证明的次优近似正则化路径。当拟合广义相加模型时，正则化路径具有吸引人的特征：在正则化参数的临界值处，新的回归因子被带入（或偶尔出于）模型，或新的结点被添加到（或从中删除） 的现有坐标函数，因此我们的方法结合了特征选择和结点选择。2. 单变量函数拟合我们希望从数据集拟合一个连续的有界函数 要做到这一点，我们将选择来最小化数据的不匹配或损失函数，但要受到鼓励中规则性的约束条件以及我们在下面描述的额外约束条件和饱和度的限制。损失由以下公式给出：其中是非负的，二次可微的，并且在它的第一个参数中是严格凸的。典型的损失函数包括（标准回归，），或者（逻辑回归，其中）。损失是函数的凸函数，仅取决于数据点处的的值。损失越小，越符合给定的数据。我们通过限制非负正则化泛函的值来约束函数是简单的。在本文中，我们将作为的微分的总变化量，一个的凸函数。对于一个二次可微函数，我们已知， （1）即正则化是二阶导数的范数。（正如我们在下一节中所讨论的那样，总变差的现代定义把这种平等扩展到不可微函数。）我们对施加的总变差限是，其中是我们用来折衷模型的参数拟合度和模型规律。这种正则化约束隐含地约束几乎无处不在，其导数具有有限的总变差。我们的模型将受到另一个约束，即它饱和（在区间0,1之外），这意味着它是0,1之外两个区间上的（可能不同的）常量：对，；对，。换句话说，在0,1的标称数据范围外延伸为一个常数。就导数而言，这相当于要求存在且在0,1之外为零。那么该拟合问题可以描述为； 满足 （2），对，其中为正则化参数。要确定的变量是函数，它是连续函数的矢量空间中的有限总变差的导数。这个拟合问题是一个无限维凸优化问题。在应用中，问题（2）解决了一系列值，这产生了正则化路径。最终模型是使用一个保留集或交叉验证来选择的。对于，必须是常数，并且问题（2）减少到适合数据的最佳常数。随着增加，的约束更小，并且我们的拟合模型变得更复杂; 最终我们期望过度拟合。例如，在回归的情况下，对于满足的损失函数和具有不同的数据，对于足够大的来说，拟合函数是插值数据的分段线性函数。3. 样条函数和有界变差函数在本节中，我们探讨拟合问题与一次样条的连接，即分段线性连续函数，其形式如下 ， （3）其中。我们假设是不同的，并将它们称为结点或简单结。标量是权重，是偏移量。我们将映射称为铰链函数，因此一阶样条是铰链函数的有限线性组合加上一个常数。3.1 有界变差函数一个右连续函数是有界变差的，当且仅当在0,1上存在一个有符号的度量，满足 ， （4）其中，对，否则等于0。度量是唯一的；我们可以认为它是的导数。 也就是说，（4）基本上是微积分的第二个基本定理，其中被代替。我们也有。（这称为度量的总变差。）我们将使用符号来作为它的记号，以强调与有限维情况的相似性，或者当是可微的情况：.当度量是原子的时候，函数是分段常数，在的支持下的点处发生跳跃。3.2 样条函数和有界变差导数现在假设具有有界变差的右连续导数。从（4），运用以及微积分的基本定理，我们有 （5） （6）. （7）这表明任何这样的函数是铰链函数的一个（可能是无限的）线性组合加上一个常数（即）。在这种情况下，度量可以被认为是的二阶导数。当是原子并且在有限集上被支持时，也就是说，是形式（3）的一阶样条，其中。因此，一阶样条完全对应于度量（大致二阶导数）具有有限支持的情况。我们引入记号 （8） 来表示从度量导出的函数。粗略地说，这是度量的双重积分或与度量有关的铰链函数的（可能有无限个的）线性组合。从到的映射是线性的，那么我们有。图1显示了一个的简单例子，它的一阶导数和它的（原子度量）二阶导数。 图1：由原子度量产生的和。正则化函数就是中尖峰的绝对值之和。需要特别注意的是，中所有尖峰的（带符号）和为零：也就是说，这意味着饱和。3.3 通过优化度量拟合样条确定，我们可以通过最小化0，1上的有界测度和常数来解决拟合问题（2）。度量是的二阶导数，常数对应于。总变差正则化约束对应于。当时，饱和度条件成立；为了确保当时，我们需要换句话说，的饱和度对应于具有总（净）质量零的。因此（2）可以改写为 满足， （9）有界测度在0，1上，同时。这里会稍微多用一些记号：我们现在（以及本文的其余部分）认为是上的函数。 在上面，是将映射到由（8）给出的向量的线性算子。显然是线性的，因为它是函数：对的积分。我们将直接应用条件梯度法来解决这个问题。为了获得关于优化问题的直觉（9），我们可以认为它是标准lasso的无限维模拟10。 lasso是优化问题 满足 （10）的解决方案。这里是中的一个向量，是一个矩阵。忽略常数项，我们看到，（9）看起来非常类似于（10），其中起着的作用；的确，本质上是一个有行和无限多列的矩阵。我们对lasso的直觉表明，应该有属于（9）的解是稀疏的，这意味着是原子的。就而言，稀疏性意味着存在一维样条的原始函数拟合问题（2）的解。事实确实如此。定理1表明存在（9）的原子解，其支持不超过个点；换句话说，是一个具有的一阶样条。此外，在实际中（9）的解将会支持远远少于个点。定理1. 固定和，为（右连续）的有界总变差，并且在0,1之外为常数。那么就存在一个一阶饱和样条（最多有个结点），它在上与相匹配，并满足。证明: 不失一般性，我们假设。令。由于约束了总变差，所以在0,1上存在一个度量，使得：也就是说，是一个无限多结的样条。我们的想法是使用Caratheodory的凸包理论来看到，因为我们只关心在有限数量函数上的作用（基本上，我们只关心在上的值），所以我们可以用一种可在有限的点上支持的度量来替代。为了使这个想法严谨，请注意矢量必须位于（凸）组的凸包中，因为。凸包的Caratheodory定理确保了可以表示为从选取的最多个点的凸组合。让这些个点由它们的标记表示，以及它们的权重，我们定义得到： 这里。因为，我们有。 #对于本文的其余部分，我们将忽略常数项。使用我们提供的算法来处理常量项并不难，但这样做确实会增加一些符号复杂性。也可以最小化，因为它不影响正则化项；由此产生的问题在中仍然是凸的。4. 拟合样条的条件梯度法在本节中，我们概述了求解（9）（因此也是（2）的算法。为此，我们简要回顾一下经典的条件梯度法7和8中提出的测量理论版本。我们需要解决的优化问题（9）（没有常数项c）是: 满足, （11）.正如上一节所述，（11）是一个衡量空间的凸优化问题。我们密切关注8中采用的方法，并直接对这个问题应用条件梯度法。这种方法的主要好处是我们可以将注意力限制在原子度量上，即的形式为.通过简单地存储成对的的列表，这种形式的度量在计算机中很容易表示。定理1确保我们需要存储的结的数量是绝对有界的，即我们的算法运行在有界存储器中。当我们操纵原子测量时，我们解决了所有有界测量的问题（11）。关于有限支持的原子测量值需要注意的一点是我们可以很容易地对结点位置固定的权重进行优化，因为这对应于适用于任何标准算法的有限维凸优化问题。我们的算法利用了这个事实，并且在每次迭代之间交替添加结对并对权重进行优化。在后一步骤中，结可以（并且事实上最终必须）被去除。在附加和可选步骤中，结点可以在0,1内连续移动，或者连续移动到相邻的数据点。理论上的收敛不需要这一步，但可以在实践中改善收敛性和最终解决方案的稀疏性。4.1 条件梯度法条件梯度法（CGM）解决了形式为 满足, （12）的约束凸优化问题，变量。在上面，我们总是假定（凸）函数是可微分的。在CGM的每次迭代中，我们在当前迭代处形成函数的标准线性逼近：这里是函数在点方向d上的方向导数，定义为：我们在这里使用方向导数可能会令人惊讶：对于上的可微函数，总是等于。方向导数对度量的凸函数的直接适用性促使我们倾向于使用它。的凸性意味着是的下界，即： . （13）在CGM的下一步中，我们在可行集上最小化这个一阶近似：.点称为的条件梯度。请注意，在上提供了一个下界：.特别地，我们可以限制点的次优性： . （14）图2：函数在点处的条件梯度法的单次迭代示意图。集合是由实线表示的区间-0.25,1.25，一阶近似值绘制为在处与相切的虚线。条件梯度是点-0.25。可以看到（如7），这个界限减少到零，这意味着它可以用作（非启发式）终止标准。确定之后，有几个更新的选项。在本文中，我们将使用CGM的完全校正变体，它选择在的凸包上来最小化。请注意，随着增长，这最后一步可能会变得计算密集，并且实际上限制了条件梯度方法对这一步在计算上可行的问题的适用性。一种选择是一旦在最小化步骤中未选择先前的条件梯度，就删除先前的条件梯度。Caratheodory定理确保我们需要跟踪的先前的条件梯度集合然后以为界。然而，在实践中，算法通常在迭代之前终止。算法1.完全校正条件梯度法对,.1、 线性化：.2、 最小化：.3、 更新：.4.2 度量的条件梯度在本小节中，我们将条件梯度法应用于无穷维问题（11），我们在此重复： 满足， （15）.首先我们将表明，条件梯度即度量，可以被选择为恰好支持两个点，并且可以在时间上线性地计算。目标函数在点处的度量s方向上的方向导数由下式给出:然后，我们可以将中的内积与中的积分互换： . （16）令。请注意在的情况下，仅仅是残差，是残差与位于的单个铰链函数之间的相关性。条件梯度是以下优化问题的解决方案： 满足， （17）.如果没有积分约束条件，我们可以期望有一个解（17），即单点质量：目标函数是标量值函数与有界度量的积分。我们将证明（17）总是有一个解决方案正好支持两点。此外，我们将显示这两点可以按时间线性计算。首先，我们将为（17）构造一个特定的可行点，然后我们将显示它达到最优值。令.定义.达到的目标值是.我们将证明，对于（17）而言，任何可行的度量的目标值都低于或对于（11）是最优的。将分解为两个相互独立的非负测度的差值：。那么，当是可行的时，我们有达到的目标值可以如下所示：假设。那么上面的论证意味着是（11）的条件梯度，因此（14）意味着是最优的。否则，我们有这意味着这证明了我们的断言。请注意，发现和在0，1上包含两个单独的优化问题，而不是0,10,1上的一个。这些问题很容易通过网格来解决，但是在这种情况下，如果我们有权访问数据点的排序矢量，它们可以在时间上精确地按时间线性地求解。为了看到这一点，我们对上面的扩展了的目标函数：如果对进行排序，我们可以精确地计算每对连续数据点之间的最小值，因为这只是计算一段时间内线性函数的最小值。因此，在数据的一次传递中，我们可以精确地计算整体最小值。在计算和之后，我们可以使用（14）来限制的次优性：通过选择条件梯度，完全校正步骤是一个有限维凸问题。修复到目前为止遇到的结点位置，通过求解下面的优化问题我们至少可以做到完全修正算法。 （18）这相当于中的以下优化问题： （19） 我们可以使用任何现有的算法来解决这个问题11，12。在我们的实现中，为了简单起见，我们使用条件梯度法和线搜索。通过以不断增加的序列进行热启动，我们可以高效地计算近似的规则化路径。事实上，我们甚至可以使用9的方法提供可证明的次优路径。4.3 收敛正如在ADCG 8收敛的情况下，立即从一般的Banach空间7，13，14中的条件梯度法证明。条件梯度法的收敛取决于曲率参数。是一个常数，所有和满足以下不等式：为了我们的目的，仅仅是和。有限的一个简单的充分条件是在Lipschitz梯度下可积。如果是有限的，则条件梯度方法以至少的速率收敛（根据函数值），其中是迭代计数器。5. 广义相加模型单变量样条的一个自然应用是将广义相加模型6拟合为多元数据：。也就是说，拟合以下形式的函数：其中每个是从到的简单函数（这里是向量的第个坐标）。 我们可以在标量情况下模拟我们的方法，其优化问题如下： （20）这里是标量情况下使用相同正则化参数，即在标量情况下，可以表明总是有一个最优的，每个坐标函数都是一阶饱和样条。这使得我们可以将（20）改写为一个优于度量的优化问题。与标量情况相比，唯一的变化是该度量超过了集合每个结现在都附加到特定的坐标上。换句话说，我们搜索以下形式的函数：我们再次在的范数和正则化项之间具有平等性：那么与（11）类似的是： （21） 标量情况下的条件梯度算法立即推广到拟合广义相加模型唯一的区别是我们现在需要为同一个坐标找到一对结点。这涉及在0,1上解决对非凸优化问题同样可以通过网格化或对训练数据进行排序来完成。拟合广义相加模型时，饱和样条曲线比标准自适应样条曲线更具优势。在拟合广义相加模型时，饱和约束的增加（在0,1之外是常数）自然会导致变量选择。我们所说的变量选择是指函数通常恰好为0。这是因为饱和约束意味着线性坐标函数不再逃避正则化（事实上，它们是不可能的）。这与没有饱和约束的标准自适应样条设置非常不同。在这种情况下，线性函数，即完全避开了正则化，因此基本上总是包含在模型中。线性函数在饱和约束下不是自由的（实际上，在函数0之外，它们是不可行的）。当我们求解（21）时，我们同时拟合非线性坐标函数，同时做可变选择。6. 相关现有成果平滑样条也可以解释为无限维优化问题1,5.4。实际上，（一阶）平滑样条解决了问题 （22）其中（22）的解也是在0,1之外饱和的一阶自然样条。然而，（22）和（2）的解决方案是非常不同的。粗略地说，（22）类似于岭回归，而（2）类似于lasso。也就是说，（22）拟合具有与数据点一样多的节点的函数，而（2）通常适合几何节点很少的样条函数。另一种自适应但不饱和的样条是自适应回归样条5。这些样条函数也可以作为函数回归问题 （23）的解决方案，其中请注意，（2）没有饱和约束。求解（23）（对于一阶样条）的算法基于定理1的扩展，这表明在数据点上实际上支持（23）的解决方案。因此可以使用lasso算法来找到解决方案。这也表明解决我们的问题的一个非常简单的方法（9）：我们将个结点固定为数据的值，并且求解有限维凸优化问题以找到权重。虽然像GLMNet 15这样简单的坐标下降方法由于饱和约束不会立即适用，但可以修改它们以处理约束。这种方法可行，但可能比我们的要慢得多，因为在实践中，对于正则化参数的有用值，结点的数目通常远小于，而对于个基函数的有限维问题的条件非常不好。这就是说，我们提出的算法对于分段线性情况可以被解释为有限维问题的前向有效集方法，其中我们避免明确评估所有基函数。我们测量理论方法的一个优点是，它立即推广到高阶样条，其中的支持不需要在数据点上，我们将在9中看到。在这种情况下（9）是真正无限维的，但我们的算法仍然可以直接应用。趋势滤波是一种非参数函数估计技术，首先在16中介绍，这与自适应样条非常相似。事实上，如17所述，常数或分段线性情况下的趋势滤波估计与自适应样条估计完全相同。趋势过滤越来越普遍，因为它承认了非常有效强大的算法17，18。事实上，这些算法中的一些（尤其是适合GAMs的算法19）可能适用于有效拟合饱和趋势滤波器估计，这将受益于饱和样条的特征选择属性和趋势滤波的计算效率。有许多用样条函数拟合广义相加模型的方法。一种方法（参见20）是使用（6）的组lasso版本：扩展这个想法，21使用重叠组lasso来促进零、线性和非线性项之间的选择。这些方法和我们的方法之间的差异类似于标准组lasso和lasso之间的差异。虽然两者都进行特征选择，但惩罚函数（6）不会在每个坐标函数内进行结点选择。在22中讨论了一种非常类似的拟合样条的方法，它不需要结点选择（但不包含饱和度）。7. 实例实施细节：我们在Rust语言中提供了一个简单的，未优化的实现。 我们算法的运行时间由完全校正步骤决定，即求解有限维凸优化问题（19）。 我们使用近似牛顿法和标准条件梯度法来求解（19），并使用精确的分解。准确地说，在每次迭代中，我们形成目标函数的二阶近似，然后我们使用有（精确的）行搜索的标准条件梯度方法来最小化（超过约束集）。 请注意，这是一个固定步长为1的牛顿步骤：如GLMNET 15中所述，为了提高速度，我们省略了行搜索。我们选择使用近端牛顿法，因为它相对简单；其他标准凸面优化算法可能会给出更好的实际性能，特别是当数据点数量非常大时。在所有的例子中，我们仿射地预处理数据，使得所有训练特征位于0,1中，并且将相同的变换应用于测试特征（因此可能具有0,1之外的值）。所有的划分都是按照标准化的特点。对于骨密度和鲍鱼数据集，我们选择来最小化验证集上的错误。对于垃圾邮件和ALS数据集，我们使用交叉验证来估计。我们从训练集中提取一个大小为100的随机子集并训练其余数据。对于每个随机验证/训练分离，我们估计以最小化保持误差，并将我们的最终估计作为50次试验的平均值。 图三：对于正则化参数的3个值，饱和样条符合骨密度数据（显示为散点）。顶部：；中间：；底部：。7.1 骨密度我们从一个简单的1,5.4中的单变量数据集开始。该数据集的响应变量是女性青少年的两次医生访视之间脊柱骨密度的变化与年龄的函数关系。有259个数据点，其中我们保留了120个用于验证的数据点，剩下139个数据点，以适应饱和脊柱。我们从平方损失开始。结果如图3所示，对于正则化参数的三个值。散点是训练数据，实线是我们算法的饱和样条拟合。该图表明了与优化样条曲线的复杂性之间的明确联系。样本外验证建议设置，从而验证RMSE为0.036。为了证明我们提出的方法与更一般的损失函数一起工作，我们将30个模拟的异常值添加到训练集并且拟合了伪Huber损耗23，这是对Huber损失函数的平滑近似：其中是在绝对值损失和平方损失之间插值的参数。对于我们的实验，我们取；粗略地说，平方和线性损耗之间的转换发生在附近。结果如图4所示。这些图表明我们的算法可以拟合除平方损失之外的损失，并且证实了伪Huber损失比基本平方损失函数对异常值更加强大。事实上，在验证集上，最小二乘法拟合的最小RMSE为0.096，而伪Huber拟合达到0.038，仅比在将训练数据加入异常值之前获得的拟合稍差。 虽然这个一维问题非常容易，但它显示了自适应样条罚款在平滑样条上的一个优点：最优模型只有5个结点。图4：对于平方损失函数（左）和伪Huber损失函数（右）的模拟异常值，饱和样条拟合骨密度数据（以散点表示），每个值用于最小化测试集上RMSE的值。7.2 鲍鱼数据集我们用饱和样条坐标函数的广义加法模型拟合来自UCI Machine Learning Repository 24的鲍鱼数据集。数据包括鲍鱼8个特征的4177个观察值以及目标变量鲍鱼的年龄。我们将400个数据点作为验证集合保留，剩下3777个数据点以适合模型。第一个特征（标记为性别）有三个值：雄性，雌性和少年，编码值为0,1,2；其他7个是（直接）实数。任务是从特征中估计鲍鱼的年龄。交叉验证表明我们选择了，它实现了验证集合RMSE为2.131。由于特征数量很少，我们可以绘制整个广义相加模型。每个图表显示的一个坐标函数作为0，1中标准化特征的函数。显示了三个值的坐标函数，中间值对应于最小化交叉验证RMSE的值。当坐标函数为零时，即模型中未使用该特征时，它将显示为蓝色。我们可以看到，在强正则化（）的情况下，几个坐标不被使用；对于最佳模型（），使用所有特征，其中一些特征仅具有小的影响。看到性因素如何进入最佳模型是很有趣的。它对于男性或女性都是中性的，但是从其年龄预测中为少年鲍鱼减去一小部分固定量。这个数据集足够小，我们可以使用粗网格0，1与标准自适应样条进行比较。对于这个实验，我们使用GLMNET 15来拟合具有标准自适应样条组件函数的GAM。标准自适应GAM拟合没有变量选择，实现了验证集合RMSE为2.137，并没有比饱和样条模型差得多。然而，我们的算法选择了更少的节点。拟合GLMNET时结节数量的增加可能是由于网格问题的条件不佳造成的。图5：用于使样条广义相加模型饱和的坐标函数适合于鲍鱼数据以获得正则化参数的三个值。图6：饱和样条广义相加模型的验证误差符合垃圾邮件数据集与调整参数。7.3 垃圾邮件我们将电子邮件分类为垃圾邮件和非垃圾邮件的两类，并从ESL获取数据集1。该数据集包含来自4601封电子邮件的57个词频特征，以及其标签为垃圾邮件或非垃圾邮件。遵循ESL中的方法1，我们对特征进行对数转换，并使用标准训练/验证分割，训练集为3065，测试集为1536个样本。我们拟合了具有标准逻辑损失的饱和样条广义加法模型。图6显示了验证错误与正则化参数的关系。交叉验证表明选择。为了说明非线性坐标函数的好处，我们还包含了使用线性模型（使用GLMNet 15拟合）获得的最佳验证误差。在正则化参数的情况下，该模型选择57个特征中的55个。我们注意到我们的饱和样条广义加法模型比ESL的许多方法略微胜过1。例如，平滑样条曲线产生5.3的误差，而我们的模型误差率远低于5。图7显示了的模型的坐标函数（一些）。坐标函数使用非常少的节点，使其易于解释。为了比较，我们使用标准自适应样条坐标函数来拟合GAM。为此，我们用20个节点对每个维度进行网格划分，并用GLMNET 15解决由此产生的有限维问题。请注意，自适应样条不会惩罚线性函数，因此不会选择特征。自适应样条的最小误差为4.8，比饱和样条要差得多。图7：的16个坐标函数，每个标有相应的特征名称。图8：验证ALS数据集与正则化参数的MSE。7.4 ALS我们尝试使用这个数据集来预测医学患者的ALS（肌萎缩侧索硬化症）的进展速度，通过功能评分的变化率来衡量，这是对功能障碍的测量。该数据集被分成1197个实例的训练集和625个额外患者的验证集。每个数据点的维数为369。我们用一个最小二乘目标函数拟合了一个具有饱和样条函数的广义加法模型。在25,17.2之后，我们使用均方差来衡量表现。我们使用交叉验证来估计的最优值，其中保留大小为100个示例和50个样本；这个程序建议。图8显示了验证误差与正则化参数；通过交叉验证选择的的值实现了低误差。在同一图上，我们还使用增强回归树和随机森林显示25的结果。最优饱和样条GAM模型只选择了369个特征中的50个，而增强回归树使用了267。饱和样条GAM模型与增强回归树和随机森林相当。这是令人惊讶的，因为饱和样条GAM没有交互条件。它还使用了少得多的功能，进一步提高了解释能力。我们再次使用具有标准自适应样条坐标功能的GAM（使用GLMNET）来展示饱和度的优势。标准自适应样条拟合实现了0.547的MSE，比其他任何模型都差得多。我们推测这是因为非线性函数导致立即过拟合。事实上，去除未经去除的线性函数并仅用铰链拟合模型就可以得到与饱和样条拟合非常相似的性能，这表明饱和度的主要优势在于去除未经去除的线性函数。饱和样条的实用优势：这些实验表明，饱和样条曲线在小分类和回归数据集上十分有效。 此外，实验证明饱和样条展示结点选择和特征选择在拟合GAMs的情况下。 虽然饱和样条曲线比平滑样条曲线（选择完全密集的结集）选择更少的节点并不奇怪，但我们的算法选择的节数比即使与GLMNET适合的自适应样条曲线也有点令人惊讶。最后，垃圾邮件和ALS数据集展示了自适应样条曲线比自适应样条曲线饱和的一个主要优势：它们同时执行非线性坐标函数拟合和特征选择。这有助于泛化性能和可解释性。特别是，对于ALS数据集，饱和样条GAM通过仅选择36个可用特征中的50个来实现自适应样条GAM的一半测试MSE。8.高阶样条在本文的大部分研究中，我们关注函数回归问题（2），对一阶导数和对零导数（函数本身）的饱和约束有一个总变差约束。在本节中，我们考虑对高阶导数的约束，导致高阶样条的解。 （24）我们考虑以为指标的非参数函数估计问题族。这是函数回归问题（2）的类比，其中对第阶导数的总变差约束和对第阶导数的饱和约束。本文中的饱和样条情形是（24）的特例，其中。广泛使用的立方自然样条对应于。注意，不同于自然样条，自然样条只为和的某些值定义，而这里对和没有约束。我们现在表明高阶饱和样条一般解决（24）。由于是有界，所以存在一个度量那么对某些我们有：在上面，所有迭代的积分发生次。请注意，对于所有，的约束意味着多项式项单独为零。 所以，我们有：对于，我们可以消除非线性，即对于，只是的多项式的积分。我们可以从积分中将包含的项取出，得到x的多项式，其系数是的前个矩的非零倍数：同样地，我们注意到，由于这个多项式对于无限多点都是零，所有的系数必须为零。就度量而言，这意味着：这表明的第阶导数饱和的约束条件转化为约束的所有时刻直到第个时刻。虽然条件梯度变得更加复杂，但增加了更多的矩约束条件，但本文采用的方法仍然可以应用于（24），只要相当小（24）的条件梯度步骤包含在上的非凸优化问题。这是因为我们至少需要个点质量来满足时间约束。因此，拟合线性饱和的二次样条曲线非常容易事实上，这样做的代码与拟合分段线性饱和样条曲线的代码基本相同但由于附加的线性条件，拟合到常数的二次样条稍微困难一些对度量的约束。然而，对于较大的和值，我们不能再希望通过分析找到条件梯度，并且必须求助于递归网格或其他全局优化算法来查找新节点的位置。图9：前两幅图分别显示了时的条件梯度，其中和。虚线表示点质量的位置：当时，条件梯度由三个点质量组成。底部的图表显示了相应的度量。9.变体和扩展虽然饱和度往往是一个自然的先验，但我们在本文中采用的方法也可以应用于（9）上的其他（凸）变体。例如，我们可以添加约束条件，即拟合的函数是单调非递减的，或者在给定的时间间隔内取值。一个简单的算法扩展就是在8的精神中加入非凸优化。在每次迭代中，我们调整原子量度的权重，但我们也可以调整结点位置。（19）中的目标在中是非凸的，但我们仍然可以试图找到一个局部最小值。只要我们不增加目标函数，算法仍然保证收敛8。在一阶样条的情况下，我们可以使用这样的事实，即结点可以在不失一般性的情况下选择在数据点上以对结点位置进行离散调整。为了拟合矢量值函数，例如在多类别分类中，我们需要扩展（9）以使用矢量值度量。这是组lasso的自然测量理论模拟。在多变量拟合问题中，特征之间存在显着相互作用的问题可能会出现广义相加模型。一种可能的解决方案是使用单层神经网络：即学习形式为的函数。在上面，被限制在单位球中。但是，这种形式的网络的条件梯度步骤是NP-hard 26。然而，在许多实际应用中，我们可能预期交互的程度是有限的。也就是说，每个都有界限基数。如果我们假设，即我们只适合配对相互作用，我们仍然可以应用条件梯度方法。在这种情况下，拟合函数是由基本元素形成的变量对的函数的和，其中（连续）参数为和以及（指数）参数为和（即，）。（仅适用于当足够小时）。这些函数捕获（成对）变量之间的非线性关系。10.结论在本文中，我们提出了修改自适应样条回归模型即饱和约束。我们证明饱和样条函数继承自适应样条的结点选择，并且在广义相加模型的背景下具有非常重要的质量：特征选择。这允许饱和样条广义相加模型保持可解释性，并且（至关重要）在应用于多元数据时避免过拟合。我们还提出了一种基于标准条件梯度法求解任意凸损失饱和样条估计问题的简单有效算法。最后，我们将我们的算法应用于多个数据集，展示了最终模型的简单性。