Online Prediction at the Limit of Zero Temperature
Online Prediction at the Limit of Zero Temperature
复制标题
零温极限在线预测
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Shaon Ghosh
中科院分区：
文献类型：
--
作者：
M. Herbster;Stephen Pasteris;Shaon Ghosh
我们设计了一个在线算法来对图的顶点进行分类。支持该算法的是与该图同构的伊辛模型的概率分布。每种分类都是基于预测相对于迄今所见的标签和顶点在零温极限中具有最大边际概率的标签。不幸的是，计算这些分类是基于一个#P-完全问题。这促使我们开发了一种算法，对于该算法，我们在在线错误界限框架中给出了顺序保证。当图是与文献[1]中的结果匹配的树时，我们的算法是最优的。对于一般的图，该算法利用树上的额外连通性来提供每个簇的界限。该算法是有效的，因为顺序预测图的所有顶点的累积时间是图的大小的二次。
We design an online algorithm to classify the vertices of a graph. Underpinning the algorithm is the probability distribution of an Ising model isomorphic to the graph. Each classification is based on predicting the label with maximum marginal probability in the limit of zero-temperature with respect to the labels and vertices seen so far. Computing these classifications is unfortunately based on a #P-complete problem. This motivates us to develop an algorithm for which we give a sequential guarantee in the online mistake bound framework. Our algorithm is optimal when the graph is a tree matching the prior results in [1]. For a general graph, the algorithm exploits the additional connectivity over a tree to provide a per-cluster bound. The algorithm is efficient, as the cumulative time to sequentially predict all of the vertices of the graph is quadratic in the size of the graph.