2013年7月19日,星期五

使用更少的数据

在一个 以前的帖子 我指出,在进行数据科学时,对较小的数据集进行操作是确保生产率和快速实验的最佳方法之一。在ICML 2013上,我和Nikos提出了 一般策略 使用较少的数据来解决各种各样的问题。

这个想法的灵感来自 类不平衡二次采样启发式。这是计算广告从业者中的一个众所周知的技巧,这种技术的奇特效果一直吸引着我。诀窍在于:当二元分类数据集主要由一个类别的示例组成时,可以对更频繁的类别进行二次采样而不会影响最终分类器的质量。事实证明,我们能够将这一技巧概括如下。

假设您打算通过最小化损失函数$ \ mathcal {L} $(即经验风险最小化(ERM))来从集合$ \ mathcal {H} $中选择假设$ h ^ * $。还要假设有人给您一个假设$ \ tilde h \ in \ mathcal {H} $。您可以在执行ERM之前使用$ \ tilde h $对数据集进行子采样,并且引入的超额风险是适度的(有关确切的超额风险界限,请参见本文)。可以丢弃的数据量取决于$ \ tilde h $的经验损失。如果$ \ tilde h $的经验损失较低,那么您可以主动进行子采样。该策略很简单:以与$ x $上$ \ tilde h $的损失成比例的比率对每个示例$ x $进行采样。您必须对最终子样本进行重要性加权以保持无偏,并在最后一步中将重要性加权的经验损失降至​​最低,但是许多机器学习算法可以直接合并重要性加权(如果没有,则可以使用 将重要性加权损失减少为均匀加权损失 通过拒绝采样)。

在这种解释中,类不平衡子采样启发法对应于使用$ \ tilde h $,它是一个常量预测变量,例如,$ \ forall x,\ tilde h(x)= 0 $对于在正数广告中是一个很好的选择例子(例如点击)相对较少。但是,此技术的概括适用范围更广。首先,我们有一个非常广泛的损失概念,不仅包括分类,回归,排名和结构化预测。但是还有一些无监督的设置,这些设置可以优化逐点丢失,例如重构错误或困惑。其次,我们允许使用假设集$ \ mathcal {H} $中的任何$ \ tilde h $。通常,对于\\ tilde h $的一个很好的选择是可以容易地按比例估计但损失很小的任何假设。对于类不平衡的问题,最好的常数预测器是很好的,并且很容易按比例估计(只需对标签计数!),但是即使对于那些不平衡的问题,自由选择$ \ tilde h $的能力也具有很大的灵活性。

作为自由选择$ \ tilde h $启用的功能的示例,考虑一下我以前工作过的eHarmony。 eHarmony的一个问题是估计两个人(如果匹配)彼此交流的可能性。 eHarmony已派发约10次6 多年来每天都进行匹配,因此它们拥有庞大的数据集。尽管eHarmony使用数百种功能来预测通信,但仍有一些功能非常有用,而许多功能则非常有用。如果您在会议期间获得了Vaclav Petricek的精彩演讲 UAI 2013推荐研讨会,您知道身高差,年龄差和身体距离是三个具有较高预测价值的功能。仅基于这三个预测变量的预测变量可以轻松地仅使用Hive进行大规模组装,而并非最优的它将损失相对较低。因此,这是$ \ tilde h $的不错的选择。我没有在eHarmony的数据上尝试过此操作,因为在那儿工作时我并不了解这些事情,但是我与Vaclav进行了交谈,他愿意尝试一下。

此技术的一个重要特殊情况是对\\ tilde h $使用线性预测器,对最终ERM使用神经网络或决策树。这很有用,因为线性预测变量可以 估计规模。请注意,要满足定理的条件,您必须确保线性预测变量在$ \ mathcal {H} $中,这对于神经网络意味着从输入到最后一层的直接连接,而对于这两种技术,这意味着非线性预测变量具有访问所有线性特征(可以为最终ERM添加特征)。作为额外的效果,对于线性模型也适用的特征表示也将 也倾向于帮助非线性模型.

因此,现在您有一个原则性的方法可以对巨型数据集进行二次采样,这将在比类不平衡更一般的设置中工作。继续并丢弃一些数据!

7条评论:

  1. 感谢您的这篇文章和您的论文。您能否更非正式地告诉我们如何处理新引入的​​超参数?在论文中您声明:

    """
    实际上,根据子样本预算选择Pmin和λ,因为子样本的预期大小上限为(Pmin +λRX(h̃))。不幸的是,这里有两个超参数,这里提出的分析除了建议约束Pmin之外,没有指导选择。≥ RX (h ̃ ) and λ ≥1;这是未来研究的主题。
    """

    在实践中,您是否在大数据集的较小均匀子集上对Pmin和λ进行网格搜索,然后选择验证误差减少最快的(Pmin,λ)对?还是只是根据预算(例如0.01)和网格搜索λ确定Pmin?

    同样在本文中,我不确定是否定义R_X(h̃)的损失函数由h优化̃(例如线性支持向量机的铰链损耗平方)或您感兴趣的真实目标损耗(例如零一损耗)。

    回复删除
    回覆
    1. 最初,Pmin不在本文中,我们只是将代名词h的经验损失设置为最小概率。审阅者指出,在这种情况下,超额风险范围有所不同,因此我们添加了Pmin,但我们怀疑Pmin的正确选择是代数h的经验损失。然后,您设置lambda以达到子样本预算大小。这是我们为DNA实验所做的,尽管我们需要更多的问题经验,才能自信地说这是路要走。 (请注意,如果给定大数据集上的霍夫丁,波浪号h的损失与零是无法区分的,波浪号h是您要寻找的假设,所以您实际上不这样做'不需要二次采样。)

      损失是要优化的代理(例如,逻辑损失),而不是真正的基础损失(例如,零一),因为我们利用了证明中优化所隐含的排序。

      删除
    2. "一位审查员指出,在这种情况下,超额风险的界限有所不同"

      By "this case"我的意思是波浪号h的损失为零。

      删除
  2. 顺便说一句,我认为文章中有一个错字:R_X(h)是根据h的总和定义的。它应该是l_h的总和。

    回复删除
    回覆
    1. h!

      本来我们没有'不能像经验伯恩斯坦论文中那样区分假设和诱发损失,但审阅者确实认为,这使论述变得混乱(事后看来,它们是正确的)。因此,我们将损失通过了所有准备就绪的摄像头,但显然并非没有错误:)

      删除
  3. 我有点困惑,尽管与您的文章相比,可能与我的知识更多有关:)。

    让's说我有n个样本,m个特征。我应该找到一个线性回归(h),它将最小化损失。

    然后,我应该使用h来:
    一种。选择N个样本,直到达到最大AUC? (就像您似乎在做论文一样?)
    b。使用h可以构建更多的特征m,并尝试改善它们的AUC。
    C。都?

    感谢您提供的任何直觉。

    回复删除
    回覆
    1. 本文中的技术仅讨论了从原始数据集中制作一个较小的,具有学习逼真度(ERM)的数据集的过程。因此,我们在本文中做a)只是为了让人们了解这种选择子样本的方法比其他方法更好的方法。您的问题建议花费时间获取子样本的大小"optimally small"从某种意义上讲,但这是避风港't been how I'运用了这项技术。实际上,子样本的大小是由一些计算预算决定的,例如,您的桌面上有多少RAM或在5分钟内可以处理多少数据以进行快速实验。

      您希望较小的数据集执行类似b)的操作,即,运行大量的建模实验,所以可以。

      删除