2012年12月19日,星期三

你真的有大数据吗?

有个 宗教战争 在ML社区酝酿。一方面,那些认为大型集群是处理大数据的方式的人。另一方面,那些认为高端台式机可以提供足够的功能而又不那么复杂的人。我认为这场辩论是由不同的扩展动机驱动的。
  1. 对于数据。本质上,有人希望学习尽可能多的数据以获得最佳模型。大型群集可能是该数据的操作存储,并且将数据编组到高端台式机上是不可行的,因此算法必须在群集上运行。原型问题是使用文本特征的广告定位(高经济价值和高数据量)(这样,双线性模型可以很好地实现,但是特征是zipf分布的,因此大数据可以提供有意义的改进)。
  2. 用于计算。数据量可能相对较少,但是学习问题在计算上很激烈。这里的原型问题是在自然数据集上使用神经网络进行深度学习(计算成本较高)(尽管其大小通常适合于舒适地放置在桌面上, 这正在改变)以原始表示形式(因此需要非凸面的``特征发现''样式优化)。
因此,即使您仅针对计算进行扩展,为什么不使用群集?具有多个核心和多个GPU的高端台式机实质上是一个(小型)群集,但其中一个具有高速互连。使用时,这种高速互连是关键 新元 解决非凸优化问题。 新元是一种惊人的通用优化策略,但具有致命弱点:它会生成许多小的更新,这在分布式环境中意味着高同步成本。在单台机器上,比在群集上减轻此问题(例如,通过微型批处理和流水线操作)更容易。目前,在商品交换集群上,我们几乎只知道如何很好地解决凸优化问题(使用批处理算法)。

单个桌面的带宽相对有限,这意味着单机工作流程可能始于将大型集群上的数据与运营商店争用(例如,通过Hive),但是在某些时候,数据被二次采样到可以由单机管理的大小。这种二次采样实际上可能很早就开始了,有时是在数据生成时开始的,在这种情况下,它变得隐含了(例如,使用编辑判断而不是行为穷举)。

从这个角度来看,辩论的确是:您需要多少数据才能为特定问题建立良好的解决方案,并且最好是针对较少的数据来解决更复杂的优化问题,而针对较多的数据来解决不太复杂的优化问题。概括的问题是``您真的有大数据吗?''这取决于问题,使宗教战争得以持续。

在这种情况下,以下示例很有趣。我拿了 mnist 并在其上训练了不同的预测变量,在其中我改变了隐藏单元的数量。输入与输出之间存在直接连接,因此零隐藏单位表示线性预测变量。这是我正在寻找的一种``模型复杂度表盘'' 以前的帖子 (尽管这远非理想,因为从0到1的步长将东西从凸形更改为非凸形)。毫不奇怪,添加隐藏单元可以提高泛化能力,但也可以增加运行时间。 (注意:我选择了学习率,通过次数等来优化线性预测器,然后在添加隐藏单位的同时重复使用相同的设置。)


现在想象一下一个计算约束:训练线性预测器只需要27秒。我在每种情况下都随机抽样数据,以使训练时间在所有情况下均约为27秒,然后我评估了整个测试集的概括性(因此您可以将这些数字与上一张图表进行比较)。


对于mnist来说,抛弃数据以学习更复杂的模型似乎最初是个好策略。总的来说,我希望这是高度依赖问题的,作为研究人员或从业人员,最好直觉知道自己偏爱的方法在哪里竞争。 YMMV。

2012年12月14日,星期五

潜在模型的光谱方法

今年在NIPS上有几个热门趋势,我将在以后的文章中对会议进行广泛介绍。现在,我想深入研究正在迅速发展且看起来非常有前途的特定研究领域: 潜在变量模型的谱算法。这是我对该主题的第三次主要曝光,并最终获得点击。正如我们将看到的,我需要3个观察值是合适的。

tl; dr版本如下:
  1. 潜在变量模型的频谱方法基于 瞬间法 而不是最大可能性。希望矩方法可以在学习过程中避免E步(``推论''),从而提高计算效率。
  2. 具有相关潜值的观测时刻具有低秩结构,当解码时可识别模型。
  3. 如果观测值足够高维,那么第三刻就足以识别模型(``维数祝福'')。特别是从前三个矩得出的对称张量的正交分解所产生的方向(``螺旋方向'')揭示了潜在结构。
这里的一切都是基于一组研究人员的开创性工作,其中包括Animashree Anandkumar,Dean P. Foster,Rong Ge,Daniel Hsu,Furong Huang,Sham M. Kakade,Yi-Kai Liu,Matus Telgarsky,还有可能是我俯瞰(对不起,提前!); 阿南库玛(Anandkumar)等等 提供了此博客文章的具体灵感。

瞬间方法

从某种意义上说,概率潜在变量模型与任何其他参数概率模型没有什么不同,因为一个人实际上从不观察概率分布的参数,仅是实现。例如,以Wikipedia示例为例,如果给您一个示例$ \ {x_i \} $从Gamma分布\ [
\ begin {aligned}
X&\ sim \ Gamma(\ alpha,\ beta),\\
\ frac {d \ Gamma(\ alpha,\ beta)} {d \ mu}&\doteq g (x;\ alpha,\ beta)= \ frac {x ^ {\ alpha-1} e ^ {-x / \ beta}} {\ beta ^ \ alpha \ Gamma(\ alpha)},
\ end {aligned}
\],则可以使用最大似然法或矩量法从样本中估算$ \ alpha $和$ \ beta $。要使用矩量方法,请将您关心的参数$(\ alpha,\ beta)$与可观测量的期望\ [
\ begin {aligned}
\ mathbb {E} [X]&= \ alpha \ beta,\\
\ mathbb {E} [X ^ 2]&= \ beta ^ 2 \ alpha(\ alpha +1),
\ end {aligned}
\]然后将期望值替换为样本估计值并求解参数。

从历史上看,矩方法被最大似然率所取代,主要是因为统计效率,这在机器学习术语中是一个样本复杂性问题。但是,如今,我们拥有大量数据,并且本质上是受计算限制的(作为此断言的证据,请考虑 大学习NIPS研讨会)。因此,最重要的是,如果矩量方法在计算上更易处理,那么它将胜过样本复杂性问题。相信基于矩量法的方法在计算上会便宜得多的原因之一是,潜在变量模型的最大可能性看起来像 电磁,而E-step(“推论”)价格昂贵;而矩量法则避免了学习过程中的E步。

相关潜在结构的观测

考虑以下简单的潜在变量模型:翻转有偏差的硬币,在该硬币的基础上翻转,从两个有偏差的硬币中选择一个,然后翻转该硬币并报告正面或反面,\ [
\ begin {aligned}
Z&\ sim \ mathcal {B}(\ pi,1),\\
X | Z&\ sim \ mathcal {B}(q_Z,1)。
\ end {aligned}
\]这里有3个未知数,因此直观地讲我们需要3个方程。让我们开始计算一下,从平均值\ [
\ begin {aligned}
\ mu&\ doteq \ mathbb {E} [X] = \ pi q_0 +(1-\ pi)q_1。 \\
\ end {aligned}
到目前为止,一切顺利,现在让我们再试一下,考虑两个观察值的乘积的期望值,
\ begin {aligned}
\ mathbb {E} [X_1 X_2]&= \ pi ^ 2 q_0 ^ 2 + 2 \ pi(1-\ pi)q_0 q_1 +(1-\ pi)q_1 ^ 2 = \ mu ^ 2。
\ end {aligned}
\]糟糕。实际上,我们并不需要所有的代数:由于观测值是同余的,因此所有高阶矩将是$ \ mu $的幂,并且上述形式的观测结果中没有其他信息。这不是力矩方法的限制,因为仅给出此信息,最大似然度也会失败。从根本上仅给出以上信息,就无法区分两种非常偏向的硬币的混合物与两种中等偏向的硬币的不同混合物。

假设您有不同的信息:告诉您观察对共享相同的(未知!)潜在值。 \ [
\ begin {aligned}
\ mathbb {E} [X_1 X_2 | Z_1 = Z_2] = \ pi q_0 ^ 2 +(1-\ pi)q_1 ^ 2。
\ end {aligned}
\]哈哈!第二条信息。需要我们只需要1,因此请考虑具有相同(未知!)潜在值\ [
\ begin {aligned}
\ mathbb {E} [X_1 X_2 X_3 | Z_1 = Z_2 = Z_3] = \ pi q_0 ^ 3 +(1-\ pi)q_1 ^ 3。
\ end {aligned}
\]现在我们有3个方程,并假设$ q_0 \ neq q_1 $,我们可以估计$ q_0 $,$ q_1 $和$ \ pi $,\ [
\ begin {aligned}
\ mathbb {E} [X]&= \ pi q_0 +(1-\ pi)q_1,\\
\ mathbb {E} [X_1 X_2 | Z_1 = Z_2]&= \ pi q_0 ^ 2 +(1-\ pi)q_1 ^ 2,\\
\ mathbb {E} [X_1 X_2 X_3 | Z_1 = Z_2 = Z_3]&= \ pi q_0 ^ 3 +(1-\ pi)q_1 ^ 3,
\ end {aligned}
\]在实践中,我们将期望值替换为样本均值。

关键是具有相关潜在结构的观测集是可识别性的关键。在上面的示例中,潜在值完全相同,但是(惊奇!)足以知道该潜在值是从相同的分布中得出的(又名``来自同一文档'')。

维度的祝福

对于更复杂的潜在结构,我们是否需要提高阶数?让我们修改模型,使其具有三个潜在状态。 \ [
\ begin {aligned}
Z&\ sim \ mathrm {Trinomial}(\ pi),\\
X | Z&\ sim \ mathcal {B}(q_Z,1)。
\ end {aligned}
\]现在我们有五个未知数($ \ pi_0,\ pi_1,q_0,q_1,q_2 $),因此看来我们必须转到五阶统计信息来识别参数。但是事实证明,这是观察到的结果是单次掷硬币的结果。如果观测值具有足够高的维数,则(惊奇!)三阶统计量就足够了。让我们再次修改模型,以便观察值是向量值\ [
\ begin {aligned}
Z&\ sim \ mathrm {Trinomial}(\ pi),\\
\ mathbb {E} [X | Z]&\ sim \ mu_Z。
\ end {aligned}
\]请注意,我们可以使用单次热编码$ \ mu_Z =(1- q_Z,q_Z)$恢复先前的二项式观察模型,但是现在我们将$ \ mu_Z $视为$ d >2 $尺寸。乍一看,这似乎没有任何优势,因为我们每个观测都有额外的信息,但也有额外的参数可以估算。但是,较高时刻中的信息内容比其他参数的数量增长得更快,从而使三阶时刻就足够了。看到这一点,瞬间展开,\ [
\ begin {aligned}
\ mathbb {E} [X]&= \ sum \ pi_i \ mu_i,\\
\ mathbb {E} [X_1 \ otimes X_2 | Z_1 = Z_2]&= \ sum \ pi_i \ mu_i \ otimes \ mu_i,\\
\ mathbb {E} [X_1 \ otimes X_2 \ otimes X_3 | Z_1 = Z_2 = Z_3]&= \ sum \ pi_i \ mu_i \ otimes \ mu_i \ otimes \ mu_i。
\ end {aligned}
\]天真的参数计数表明,第一和第二阶矩足以识别模型,但是$ \ mu_i $不是正交的,因此我们不能仅用例如SVD。但是,我们可以在协方差上使用SVD来构建$ \ mu_i $跨度的正交标准,并且在此基础上,三方差张量具有唯一的正交分解,其特征向量确定$ \ mu_i $。

如果$ \ mu_i $不是线性独立的,则前一个参数将失败,并且特别是这意味着观测值的维数必须至少是潜在变量的基数。幸运的是,我们在机器学习中通常具有非常高的维度数据,这种情况通常会产生问题(``维度的诅咒''),但在这里却创造了机会,可以从低阶矩中识别出丰富的潜在结构(``维度的祝福'')。 ”)。

对于更复杂的潜在模型,如何操纵前三个矩以提取所需的潜在参数的细节会发生变化,但基本策略是将问题简化为使用前三个矩构造的张量的正交分解。张量分解是一个特殊的优化问题,由于其广泛的适用性,我怀疑这可能是新的``$ L_2 $惩罚性铰链损失'',即在不久的将来有相当一部分机器学习可以被表征为找出如何(近似)快速解决此特定优化问题。

2012年12月2日,星期日

模型复杂度,数据资源和计算约束

阿布·莫斯托法(Abu-Mostofa)在他的精彩视频讲座之一(讲座8 在视频中@ 44:45)指出了“将模型复杂度与数据资源相匹配,而不是目标复杂度”。但是,在大数据机器学习中,这是没有做的。例如,如果您想赢得 卡格勒 涉及约10个数据集的竞赛5 行和大约102 在列中,您使用了庞大的增强决策树集合(与其他东西组合在一起)。但是,将这些数字缩放4个数量级,并且(主要)线性预测变量或接近朴素的贝叶斯风格的方法占主导地位。更多数据,更简单的模型。 ??

发生的事情是计算约束占主导。您可能会认为这是纯粹的工程问题,需要通过分布式学习,GPU等来扩展更复杂的模型。但是,您还可以利用所有额外的功能将更多的数据提供给更简单的模型。因此,这就引出了一个问题:为了学习更复杂的模型,值得丢弃一些数据资源吗?还是放弃一些模型复杂性以保留更多数据资源更好?请注意,考虑到生成模型所需的数据量和计算量,我只是考虑最终模型的质量:在实践中,诸如模型评估时间等用于预测面向消费者的互联网服务至关重要,但让我们忽略这一点。

在我最近的职业生涯中,我只是认为以模型复杂性(较少)换取数据资源(更多)是更好的选择,但是我从未真正对此进行调查或质疑。最近,我开始在Kaggle上玩耍,我发现有很多有趣的数据集并没有那么大,而重磅锦标赛风格的收益促使人们使用比我通常专业使用的模型更为复杂的模型。这让我很想添加一些更强大的技术 威杜布 现在有一个神经网络简化,但你猜怎么着?是s-l-o-w。 Vee-dub具有分布式学习功能,所以我有一个分布式神经网络学习系统,但是如果我要为一个问题吃掉整个集群,我应该使用相对快速的线性学习和更多数据,还是使用相对较慢的神经网络学习,从而减少学习数据?这里有一个数据模型的复杂性前沿,正确的权衡尚不清楚。

对于固定算法,有很多示例,例如, 阿加瓦尔(Agarwal)等。等;对于固定的数据集,有很多示例比更简单的模型要好,例如, mnist。想象一个3维图,其中z轴是``模型真棒'',x轴是数据资源,而y轴是模型复杂度。这些结果基本上是关于此二维函数的一维轴平行语句。有没有可以在两个维度上进行比较的结果?一项很棒的研究将比较,例如,在同一问题上对万亿级线性学习与千兆深度学习进行了比较,并尝试对每种技术使用相同的计算资源。

我怀疑对于万亿级学习问题,拥抱线性预测器是一个好主意(到目前为止!),但是鉴于当前可用的数据资源和计算约束条件,在建模能力方面仍有一定的改进空间。这表明对于这种情况,所写的神经网络简化方法是不可取的,因为它没有从输入层到输出层的直接连接。如果我增加这些多余的连接,希望不会增加任何隐患,并且从相对较少的隐藏单元中获得一些适度的好处(尽管我在学习线性预测器的同时还难以学习低阶潜在模型,因此无法保证) 。

对于Kaggle区域,我非常确定能够将大约10台机器扔掉6 大约10行3 隐藏的单位将会很棒。