CMU的研究人员Yichong Xu等提出了一种半监督算法排序回归.doc
《CMU的研究人员Yichong Xu等提出了一种半监督算法排序回归.doc》由会员分享,可在线阅读,更多相关《CMU的研究人员Yichong Xu等提出了一种半监督算法排序回归.doc(7页珍藏版)》请在三一文库上搜索。
1、CMU的研究人员Yichong Xu等提出了一种半监督算法排序回归非参数回归(nonparametric regression)是一种在实践中很有吸引力的方法,因为它非常灵活,对未知回归函数的先验结构假定限制相对宽松。然而,相应的代价是它需要大量标注数据,且随着维度的增加而指数级增长所谓维度的诅咒(curse of dimensionality)。标注数据极为耗时耗力,而在很多场景下,序信息(ordinal information)的获取则相对而言成本较低。有鉴于此,CMU的研究人员Yichong Xu等提出了一种半监督算法排序回归(Ranking-Regression),结合少量标注样本,加
2、上大量未标注样本的序信息,逃脱维度的诅咒。非参数方法在监督学习问题中,我们有一些标注过的数据(观测),然后寻找一个能够较好地拟合这些数据的函数。给定一些数据点,寻找拟合这些数据点的函数,我们首先想到的就是线性回归:其中:y为因变量(即目标变量);w为模型的参数;X为观测及其特征矩阵;为对应于随机、不可预测的模型错误的变量。我们可以看到,线性回归的过程,其实就是找出能够最好地拟合观测的参数w,因此,线性回归属于参数方法。然而,线性回归假定线性模型可以很好地拟合数据,这一假定未必成立。很多数据之间的关系是非线性的,而且很难用线性关系逼近。在这种情况下,我们需要用其他模型才能较好地拟合数据,比如,多
3、项式回归。绿线为线性回归,红线为多项式回归;图片来源:ardianumam.wordpress无论是线性回归,还是多项式回归,预先都对模型的结构有比较强的假定,例如数据可以通过线性函数或多项式函数来拟合,而这些假定不一定成立。因此,许多场景下,我们需要使用非参数回归,也就是说,我们不仅需要找到回归函数的参数,还需要找到回归函数的结构。图片来源:Brmccune;许可: CC BY-SA 3.0例如,通常用于分类的K近邻算法,其实还可以用于回归。用于回归的K近邻算法,其基本流程和一般的用于分类的K近邻算法差不多,唯一的区别是,分类时,目标变量的分类为它的最近邻中最常见的分类(众数),而回归时,目
4、标变量的值为它的最近邻的均值(或中位数)。用于回归的K近邻算法,就是一种非参数回归方法。当然,非参数方法的灵活性不是没有代价的。由于不仅回归函数的参数未知,回归函数的结构也未知,相比参数方法,我们需要更多的标注数据来训练,以得到较好的结果。而随着维度的增加,我们需要的标注数据的数量呈指数级增长。这也正是我们前面提到的维度的诅咒。前面我们举了K近邻作为非线性回归的例子,而K近邻正因受维度诅咒限制而出名。有鉴于此,许多研究致力于通过给非参数回归增加结构上的限制来缓解这一问题,例如,稀疏性或流形的限制(很多时候,高维数据空间是稀疏的,有时高维数据甚至基本上处于一个低维流形之上)。这是一件很有意思的事
5、情。在实践中,之所以选用非参数回归,正是看重其灵活性,对拟合函数的结构没有很强的假定。然而,当非参数回归遇到维度诅咒的时候,我们又退回一步,通过加强结构上的假定来缓解维度诅咒问题。而CMU的研究人员Yichong Xu、Hariank Muthakana、Sivaraman Balakrishnan、Aarti Singh、 Artur Dubrawski则采用了另外的做法,使用具有序信息的较大数据集补充带标注的较小数据集,缓解非参数回归在高维度下的问题。这一做法在实践中意义很大,因为相对标签而言,序信息的收集成本要低很多。例如,在临床上,精确地评估单个患者的健康状况可能比较困难,但是比较两个
6、患者谁更健康,则比较容易,也比较精确。排序回归算法研究人员提出的排序回归(Ranking-Regression)算法(以下简称R2),其基本直觉是根据序信息推断未标注数据点的值。具体而言,根据序信息排序数据点,之后应用保序回归(isotonic regression),然后根据已标注数据点和序信息推断未标注数据点的值。经过以上过程之后,就可以用最近邻算法估计新数据点的值了。算法示意图上为R2算法示意图。当然,如果你更习惯看伪代码的话:R2的上下界显然,用序信息代替标签,有以次充好之嫌。因此,研究人员研究了R2算法的误差上下界。正如之前提到的,非参数回归对结构的假定比较宽松,但也并不是毫无限制的
7、。研究人员采用了经典的非参数回归限制:未标签数据集X1, ., Xn中,Xi X 0,1d,且Xi均匀独立抽取自分布Px。而Px满足其密度p(x)对x 0,1d而言是有界的,即 0 在满足以上条件的条件下,研究人员证明了R2得出的回归函数的均方误差上界为:其中,C1、C2为大于0的常数。而回归函数的均方误差下界为:其中,C为大于0的常数。由误差上下界可知,基于序信息的排序回归效果不错,从对数因子上来说是最优的。另外,从R2误差的上界来看,只有序信息(n)依赖于维度d(不等式右侧第二项),而标注信息并不依赖维度d(不等式右侧第一项),也就是说,R2逃脱了维度的诅咒。限于篇幅,这里就不介绍了证明过
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- CMU的研究人员Yichong Xu等提出了一种半监督算法排序回归 CMU 研究人员 Yichong Xu 提出 一种 监督 算法 排序 回归
链接地址:https://www.31doc.com/p-3250596.html