加快 K 折交叉验证中的优化

机器算法验证 机器学习 交叉验证 最大似然 优化
2022-04-13 04:01:04

简短版本:如果有的话,加速优化的方法是什么?k-折叠交叉验证(k10)对于数据点在统计上独立的通用模型,通过利用每个折叠的最优值可能彼此接近的事实?


长版: 让我们考虑一下k-模型评估的折叠交叉验证,与k10.

对于每一折,我都在执行最大似然估计 (MLE)k1k-th 个数据点,然后计算测试数据的(对数)可能性。这些模型都是非线性的并且相当复杂,但是数据点xi,1iN, 假设在给定参数的情况下是独立的θ, 那是:

logf(x|θ)=i=1Nlogfi(xi|θ).
在实践中,k-fold 交叉验证相当于运行最少k独立优化(每折叠一个)以找到 MLE;如果景观是非凸的,则可能从多个起点重复每个优化,以尽量避免局部最优。

重点是,跑步k 独立优化(可能多次)可能非常昂贵并且看起来很浪费。如果k很大(并且N很大),并且褶皱在统计上是独立同分布的(例如,因为数据近似,并且我们使用分层),不同褶皱的最优值将(通常)彼此接近。因此,似乎应该有办法利用这些信息来指导优化和保存函数评估。例如,一种简单的方法可能包括从前一个折叠的(附近)最优值或完整函数的最优值初始化每个折叠的优化,或者以某种方式利用从其他折叠的优化中获得的信息(各种想法)想到如何这样做)。

例如,多任务贝叶斯优化(Swersky、Snoek 和 Adams,NIPS 2013)推断相关函数之间的相关核以加速同时优化。多任务 BO 不是专门为交叉验证而构建的(它是一个可能的应用程序),它适用于代价高昂的函数评估,因此不适合我目前正在做的事情。

如果有的话,文献中的其他已知技术 [编辑:基于 BO,这只是一个例子] 在这种情况下可用于加速交叉验证的优化?论文的具体指针将不胜感激。

(作为记录,我已经知道 Vehtari 和 Gelman,2015 年的Pareto 平滑重要性抽样 留一法 CV;但这是针对 MCMC 抽样,而不是 MLE,在我的情况下它失败了。)

2个回答

警告:这本质上是一个非答案。

我你的k-fold 交叉验证用于验证目的,优化的独立性实际上是至关重要的。如果您使用在完整模型上获得的模型参数来初始化任何代理模型训练,则该代理模型不再独立于完整数据集。即,代理模型与其测试数据之间也存在依赖关系!对于交叉验证的任何两个代理模型也是如此:一个代理模型的测试数据始终是另一个代理模型的训练数据。

很有可能这种对假设(!)相似性的利用将导致比您在其他情况下获得的模型更相似。因此,我会说这组加速优化的代理模型实际上是由(稍微)不同的训练算法产生的,因此是不同的模型。


我实际上进行交叉验证的原因之一是证明获得的(代理)模型非常相似,即使是独立优化/训练的,即我使用(迭代/重复)k-折叠交叉验证以测量模型稳定性。

也就是说,您想利用的相似性实际上是我认为要通过交叉验证来衡量/验证的部分内容。


更新以回答@lacerbi 的评论

假设与构建相似性:我们在这里至少在 3 个不同的级别上谈论相似性——这就是我的看法:

  1. 我们构建了非常相似的训练数据。
  2. 我们假设(或希望)非常相似的训练数据也会导致非常相似的模型。
    但是,这并不能保证:我们称具有此特征的模型是稳定的(训练数据中存在小的差异/扰动)。
  3. 同样,我们假设模型的预测非常相似(对于相同的测试用例)。这是一个假设,它构成了重新采样验证的整个想法的基础,它允许我们使用交叉验证模型的预测作为所讨论模型的独立测试用例预测的替代品。

(当我使用振动光谱时,我区分了 2 和 3,其中物理数据生成过程会导致相关性,这可能导致模型参数不如相应的预测稳定)

丢弃这些信息对我来说似乎不明智

这是一个非常有效的观点。但是,数据的双重使用会导致依赖。您将数据用于何种用途由您决定。我要说的是,如果您使用数据为您的训练生成良好的起始值,那么就使用独立数据进行验证而言,它已经用完了。

就通过使用所有数据进行训练来验证您获得的模型而言:您声明我们可以假设k要大。你解释了训练的代理模型k1k的数据集实际上是不稳定的(另见下文)。现在我认为更大的k,假设(某些)代理模型在找到全局最小值时存在问题,假设在所有数据上训练的模型是稳定的(找到全局最小值)的假设不太可信。因此,如果可能,验证过程应该显示代理模型的不稳定性:这种不稳定性不是代理模型的“意外”——它也是一个适用于所有数据训练的模型的问题,而你没有类似于您为代理模型建议的初始化。

假设不存在的独立性。

我看到交叉验证的方式,它传统上不假设独立性,而是模型之间几乎完全相似:恕我直言,它假设

  1. 受过训练的“代理模型”k1k的数据几乎与在所有数据上训练的模型相同。
  2. 由于 1. 经常显示违规迹象(例如众所周知的悲观偏见),因此较弱的假设是至少所有k代理模型彼此足够相似,因此我们可以汇总它们的测试结果。

仅假设每个代理模型与其相应的测试集之间存在独立性。

 在训练折叠之间不交换信息可能会阻止一个或多个折叠找到全局最优值(这发生在我的真实数据中)

这是对训练算法/其结果模型不稳定的担忧。初始化,也写。到实际的训练样本。这是模型的一个重要特征。交叉验证的优点之一是它可以(在某种程度上)测量这种不稳定性。这种可能性当然越重要,你的模型就越不稳定。

换句话说,只要有证据表明解决方案的稳定性不是问题,我就会认为通过这样的初始化来节省计算时间是一种合法且相当无害的捷径。但在你的情况下,证据是这样的。模型稳定性而不是不稳定性是一个问题,因此我不推荐建议的捷径。

请注意,模型聚合作为处理不稳定模型的一种方式与您的想法几乎相反:聚合不是强制解决方案朝向不稳定解决方案之一,而是尝试尽可能多地覆盖实际发生的变化,并且聚合(平均值) 解决方案。

偏差-方差-权衡

您在极端情况下建议的方差减少对应于选择一种解决方案,例如,第一折的解决方案。我看不出这有多大帮助。但是,我确实看到例如选择最常见的解决方案(或某种中值或平均模型)有所帮助。这里的重点是,我们实际上是在谈论某种聚合模型,它与进入此聚合的单个模型不同。而且您还应该非常清楚您提出的聚合方案使计算性能估计的袋外快捷方式无效,因为您为了更好的训练而牺牲了测试数据的独立性。

有一个用于改进交叉验证的通用框架 [2]。它不会重用在其他折叠上获得的最佳值(@cebeleites 已经提到过这种方法的危险),而是使用在不同数据集上训练的模型之间可能存在的关系,并定义“合并”两个模型的概念。

如果可以独立于模型训练集的大小来执行合并,则k折叠交叉验证可以在O(n+k)操作。

每个例子都考虑两个朴素贝叶斯模型(即在两个不同的训练集上训练的朴素贝叶斯模型)。将每个模型的条件概率相乘(并根据训练集的大小重新加权每个概率)相当于在整个数据上训练朴素贝叶斯。最近的质心方法具有相同的属性。

不幸的是,这方面的研究似乎并不多……

编辑

由于实际上有很多专门的方法,我最终写了一篇简短的博客文章,介绍了加速不同模型交叉验证的各种方法。

[2] M. Izbicki,“代数分类器:快速交叉验证、在线训练和并行训练的通用方法”,