Online Prediction on Large Diameter Graphs
Online Prediction on Large Diameter Graphs
复制标题
DOI：
--
复制
发表时间：
2008-12
期刊：
影响因子：
--
通讯作者：
M. Herbster;Guy Lever;M. Pontil
中科院分区：
文献类型：
--
作者：
M. Herbster;Guy Lever;M. Pontil
我们继续我们的研究在线预测的标签的图。我们展示了基于拉普拉斯的算法的一个基本限制：如果图具有大的直径，则此类算法所犯的错误数量可能与顶点数量的平方根成比例，即使在处理简单问题时也是如此。我们克服了这个缺点，通过一个有效的算法，实现了对数错误界。它是基于一个脊柱的概念，路径图，提供了一个线性嵌入的原始图。在实践中，图可能会表现出集群结构，因此在最后一部分，我们提出了一个修改后的算法，实现了“两全其美”：它表现良好的本地集群结构的存在下，和全球大直径图。
We continue our study of online prediction of the labelling of a graph. We show a fundamental limitation of Laplacian-based algorithms: if the graph has a large diameter then the number of mistakes made by such algorithms may be proportional to the square root of the number of vertices, even when tackling simple problems. We overcome this drawback by means of an efficient algorithm which achieves a logarithmic mistake bound. It is based on the notion of a spine, a path graph which provides a linear embedding of the original graph. In practice, graphs may exhibit cluster structure; thus in the last part, we present a modified algorithm which achieves the "best of both worlds": it performs well locally in the presence of cluster structure, and globally on large diameter graphs.