提出一种新方法,在已知所有数据的情况下实现更优的预测性能。
Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregation
- 基于近似经验风险最小化水平集构造聚合预测器
- 在多种任务中证明了乘法型最优误差上界
- 适用于分类、回归等场景,尤其适合小样本学习
我们重新研究了转导学习问题,即在所有协变量已知的前提下进行预测。在留一法(LOO)设置下,利用其余样本点的标签进行预测,并以平均误差作为评估标准。针对包括0-1损失分类、平方损失回归、密度估计和逻辑回归等多种任务,我们研究了泛化情况下的乘法型奥拉克不等式。具体地,提出了“水平集聚合的中位数”(MLSA)聚合方法,该方法基于接近经验风险最小化(ERM)的水平集构建。我们证明了LOO误差的一般乘法型奥拉克不等式: LOO_S(MLSA) ≤ C (1/n min_{h∈H} L_S(h) + log|H|/n),C>1,其中H为假设类。该不等式在局部水平集增长条件下且损失满足弱单调性时成立。对于具有VC维d的分类任务(0-1损失),log|H|项可改进为d log n,与Long (1998)结果一致,仅差一个log n因子。对于有界协变量和参数的逻辑回归,该项可改进为d log n(含问题相关因子),其中d为环境维度。
原文摘要 · Abstract (English)
We revisit transductive learning where predictions are made with the set of all covariates known in advance. In the leave-one-out (LOO) setting, the prediction is made with labels of the remaining sample points and evaluated by the average error. In particular, we study multiplicative oracle inequalities for agnostic transductive LOO prediction for a variety of tasks, including classification with 0-1 loss, squared loss regression, density estimation, and logistic regression. Specifically, we introduce \emph{Median of Level-Set Aggregation} (MLSA), an aggregation procedure built on near-ERM level sets (i.e., empirical-risk level sets around the ERM). We prove a general multiplicative oracle inequality for the LOO error of the form \[ LOO_S(MLSA) \;\le\; C \left( \frac{1}{n} \min_{h\in H} L_S(h) \;+\; \frac{\log |H|}{n}\right), \qquad C>1, \] where $H$ is the hypothesis/function class. This inequality holds for hypothesis classes under a local level-set growth condition together with losses satisfying a mild monotonicity assumption. For classification with VC classes under the $0$--$1$ loss, the $\log |H|$ factor can be improved to be $d\log n$, where $d$ is the VC dimension, recovering Long (1998) up to a $\log n$ factor. For logistic regression with bounded covariates and parameters, the $\log |H|$ factor can be improved to be $d\log n$ up to problem-dependent factors, where $d$ is the ambient dimension.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。