Prediction on a Graph with a Perceptron
Prediction on a Graph with a Perceptron
复制标题
DOI：
10.7551/mitpress/7503.003.0077
复制
发表时间：
2006-12
期刊：
影响因子：
--
通讯作者：
M. Herbster;M. Pontil
中科院分区：
文献类型：
--
作者：
M. Herbster;M. Pontil
我们研究了带有感知器的图的噪声标记的在线预测问题。我们同时处理标签噪声和概念噪声。图学习被描述为在有限集合上预测的一个实例。为了处理标签噪声，我们证明了Gentile[1]推导的在线感知器学习的铰链损失界在应用于有限集上的预测时可以转化为具有最优引导常数的相对误差界。这些界限在很大程度上取决于所学概念的规范。通常，一个概念的标准可能会有很大的不同，标签中只有很小的扰动。我们分析了一个在扰动下稳定范数的简单变换。我们得到了一个上界，它只取决于图的自然性质--图的直径和图的划分的割大小--这只间接取决于图的大小。图测地线最近邻算法的这种界限是不可能的。
We study the problem of online prediction of a noisy labeling of a graph with the perceptron. We address both label noise and concept noise. Graph learning is framed as an instance of prediction on a finite set. To treat label noise we show that the hinge loss bounds derived by Gentile [1] for online perceptron learning can be transformed to relative mistake bounds with an optimal leading constant when applied to prediction on a finite set. These bounds depend crucially on the norm of the learned concept. Often the norm of a concept can vary dramatically with only small perturbations in a labeling. We analyze a simple transformation that stabilizes the norm under perturbations. We derive an upper bound that depends only on natural properties of the graph – the graph diameter and the cut size of a partitioning of the graph – which are only indirectly dependent on the size of the graph. The impossibility of such bounds for the graph geodesic nearest neighbors algorithm will be demonstrated.