Geek AI 路雪编译

ICML 2018 | Petuum提出新型正则化方法:非重叠促进型变量选择

第 35 届国际机器学习会议(ICML 2018)正在瑞典斯德哥尔摩举行。人工智能创业公司 Petuum 共有 5 篇论文入选,包含门控规划网络、变换自回归网络和无限可微分蒙特卡罗估计器等研究。本文将摘要介绍其中一篇论文《Nonoverlap-Promoting Variable Selection》,其中提出了一种有效的新型正则化方法,能够促进变量选择中的非重叠效应。

在评估模型质量的各种指标中,有两个比较常用:(1)在未曾见过的数据上的预测准确度;(2)对模型的解释。对于(2),科学家更喜欢更简单的模型,因为响应和协变量之间的关系更清晰。当预测量(predictor)的数量很大时,简约性问题就会变得尤其重要。当预测量的数量很大时,我们往往希望确定出一个能展现最强效果的小子集。

为了能在选择出重要因素的一个子集的同时得到准确的预测,研究者常常使用基于正则化的变量选择方法。其中最值得提及的是 L1 正则化(Tibshirani, 1996),这能促进模型系数变得稀疏。其变体包括 L1/L2 范数(Yuan & Lin, 2006),其中引入了组稀疏效应(group sparsity effect)和弹性网络(elastic net)(Zou & Hastie, 2005),这能强烈地促进大量预测量中互相相关的预测量共同进入或离开模型。

在很多机器学习问题中,都可以基于同一个协变量集预测出多种响应。比如,在多任务分类任务中,具有 m 个类别的分类器建立在一个共享的特征集之上,而且每个分类器都有一个类别特定的系数向量。在主题建模任务(Blei et al., 2003)中,可以在同一个词汇库上学习到多个主题,并且每个主题都有一个基于词的特有多项式分布。不同的响应与协变量的不同子集相关。比如,教育主题会与「学生」、「大学」和「教授」等词相关,而政治主题则会与「政府」、「总统」和「选举」等词相关。为了在执行变量选择时考虑到不同响应之间的差异,我们希望为不同响应选出的变量之间的重叠更少。

这个问题可用以下数学形式描述。设有 m 个响应共享 d 个协变量。每个响应都有一个特定的 d 维权重向量 w,其中每一维都对应于一个协变量。设为 w 的支撑集,索引了一个响应的所选变量。对于任意两个响应 i 和 j,我们希望它们的所选变量 s(wi) 和 s(wj) 有更少的重叠,其重叠度的衡量方式为。为了达到这个效果,我们提出了一种正则化器(regularizer),可同时促进不同的权重向量接近正交且每个向量变得稀疏,这能联合促使向量的支撑集的重叠更小。我们也通过实验表明:最小化该正则化器能够降低所选变量之间的重叠。

这项研究工作的主要贡献包括:

  • 我们提出了一种新型正则化方法,能够促进变量选择中的非重叠效应。

  • 我们将新提出的正则化器应用在了 4 种模型上:多类 logistic 回归、距离度量学习、稀疏编码和深度神经网络

  • 我们导出了求解这些正则化问题的有效算法。尤其值得提及的是,我们为正则化稀疏编码开发了一种基于 ADMM 和坐标下降(coordinate descent)的算法。

  • 我们分析了新提出的正则化器能提升泛化性能的原因。

  • 我们通过实验表明了这种正则化器的实际有效性。

方法

在这一节,我们提出了一种非重叠促进型正则化器,并将其应用在了 4 种机器学习模型上。

1 非重叠促进型正则化

我们假设模型有 m 个响应,其中每一个都使用一个权重向量进行了参数化。对于向量 w,其支撑集 s(w) 定义为——w 中非零项的索引。而且这个支撑集包含所选变量的索引。我们首先定义一个分数来衡量两个响应的所选变量之间的重叠程度:

这是支撑集的 Jaccard 指数。越小,则两个所选变量的集合之间的重叠程度就越低。对于 m 个变量集,重叠分数则定义为各对分数之和:

这个分数函数不是平滑的,如果被用作正则化器会很难优化。我们则根据提出了一个平滑的函数,并且可以实现与 o(W) 相近的效果。其基本思想是:为了促进重叠较小,我们可以让(1)每个向量有少量非零项,(2)向量之间的支撑集的交集较小。为了实现(1),我们使用一个 L1 正则化器来促使向量变得稀疏。为了实现(2),我们促使向量接近正交状态。对于两个稀疏向量,如果它们接近正交,那么它们的支撑集将会落在不同的位置。这样能让支撑集的交集较小。

我们遵循了(Xie et al., 2017b)提出的方法来促进正交性。为了让两个向量 wi 和 wj 接近正交,可让它们的 L2 范数接近 1,让它们的内积接近 0。基于此,就可通过促使这些向量的 Gram 矩阵接近于一个单位矩阵 I 来促进一组向量之间的正交性。因为 G 和 I 各自的对角线上没有了和 0,而分别是和 1,所以要让 G 接近 I,本质上就是让接近 0,让接近 1。由此,就促使 wi 和 wj 接近正交了。(Xie et al., 2017b)提出的一种用于衡量两个矩阵之间的「接近度」的方法是使用对数行列式散度(LDD:log-determinant divergence)(Kulis et al., 2009)。两个 m×m 正定矩阵 X 和 Y 之间的 LDD 定义为,其中 tr(·) 表示矩阵的迹。G 和 I 之间的接近度可以通过让它们的 LDD更小来得到。

将正交促进型 LDD 正则化器与稀疏度促进型 L1 正则化器组合到一起,我们就得到了以下 LDD-L1 正则化器:

其中 γ 是这两个正则化器之间的权衡参数。我们的实验已经验证,这种正则化器可以有效地促进非重叠。对(3)式和(2)式之间的关系的形式分析留待未来研究。值得提及的是,单独使用 L1 或 LDD 都不足以降低重叠。如图 1 所示,其中 (a) 是仅使用了 L1 的情况——尽管这两个向量是稀疏的,但它们的支撑集完全重叠。在 (b) 中仅使用了 LDD——尽管这两个向量非常接近正交,但因为它们是密集的,所以它们的支撑集完全重叠。(c) 中则使用了 LDD-L1 正则化器,这两个向量是稀疏的且接近正交。因此,它们的支撑集不重叠。

图 1:(a) 使用 L1 正则化的情况,向量是稀疏的但它们的支撑集重叠;(b) 使用 LDD 正则化的情况,向量是正交的但它们的支撑集重叠;(c) 使用 LDD-L1 正则化的情况,向量稀疏且互相正交,它们的支撑集不重叠。

2 案例研究

我们将 LDD-L1 正则化器应用在了 4 种机器学习模型上:

  • 多类 logistic 回归(MLR)

  • 距离度量学习(DML)

  • 稀疏编码(SC)

  • 深度神经网络(DNN)

3 算法 

对于 LDD-L1 正则化的 MLR、NN 和 DML 问题,我们使用近端梯度下降(Parikh & Boyd, 2014)求解它们。这种近端操作针对的是 LDD-L1 中的 L1 正则化器。算法会迭代地执行以下三个步骤,直到收敛:(1)计算的梯度,其中 L(W) 是未正则化机器学习模型的损失函数是 LDD-L1 中的 LDD 正则化器;(2)执行 W 的梯度下降更新;(3)将 L1 正则化器的近端算子应用于 W。

算法 1:求解 LDD-L1-SC 问题的算法

实验

表 2:在 20-News 和 RCV1 的测试集上的分类准确度,以及训练准确度和测试准确度之间的差距

表 4:在 PTB 测试集上的词级困惑度

表 5:在 CIFAR-10 测试集上的分类误差(%)

论文:非重叠促进型变量选择(Nonoverlap-Promoting Variable Selection)

论文地址:http://proceedings.mlr.press/v80/xie18b/xie18b.pdf

变量选择是机器学习(ML)领域内的一个经典问题,在寻找重要的解释因素以及提升机器学习模型的泛化能力和可解释性方面有广泛的应用。在这篇论文中,我们研究了要基于同一个协变量集预测多个响应的模型的变量选择。因为每个响应都与一个特定协变量子集有关,所以我们希望不同响应的所选变量之间有较小的重叠。我们提出了一种能同时促进正交性和稀疏性的正则化器,这两者能共同带来降低重叠的效果。我们将这种正则化器应用到了 4 种模型实例上,并开发了求解正则化问题的有效算法。我们对新提出的正则化器可以降低泛化误差的原因进行了形式分析。我们在仿真研究和真实世界数据集上都进行了实验,结果表明我们提出的正则化器在选择更少重叠的变量和提升泛化性能上是有效的。

理论ICMLICML 2018Petuum正则化论文
1
相关数据
深度神经网络技术
Deep neural network

深度神经网络(DNN)是深度学习的一种框架,它是一种具备至少一个隐层的神经网络。与浅层神经网络类似,深度神经网络也能够为复杂非线性系统提供建模,但多出的层次为模型提供了更高的抽象层次,因而提高了模型的能力。

收敛技术
Convergence

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

弹性网络技术
Elastic net

在统计学中,特别是在拟合线性或逻辑回归模型时,弹性网络是一个正则回归方法,线性组合了套索和脊线方法的L1和L2惩罚。

范数技术
Frobenius Norm

范数(norm),是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域,是一个函数,其为向量空间内的所有向量赋予非零的正长度或大小。半范数反而可以为非零的向量赋予零长度。

梯度下降技术
Gradient Descent

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

机器学习技术
Machine Learning

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

损失函数技术
Loss function

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

度量学习技术
Metric learning

即学习一个度量空间,在该空间中的学习异常高效,这种方法多用于小样本分类。直观来看,如果我们的目标是从少量样本图像中学习,那么一个简单的方法就是对比你想进行分类的图像和已有的样本图像。但是,正如你可能想到的那样,在像素空间里进行图像对比的效果并不好。不过,你可以训练一个 Siamese 网络或在学习的度量空间里进行图像对比。与前一个方法类似,元学习通过梯度下降(或者其他神经网络优化器)来进行,而学习者对应对比机制,即在元学习度量空间里对比最近邻。这些方法用于小样本分类时效果很好,不过度量学习方法的效果尚未在回归或强化学习等其他元学习领域中验证。

参数技术
parameter

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

正则化技术
Regularization

当模型的复杂度增大时,训练误差会逐渐减小并趋向于0;而测试误差会先减小,达到最小值后又增大。当选择的模型复杂度过大时,过拟合现象就会发生。这样,在学习时就要防止过拟合。进行最优模型的选择,即选择复杂度适当的模型,以达到使测试误差最小的学习目的。

权重技术
Weight

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

路雪
路雪

机器之心编辑

推荐文章
返回顶部