Predicting the Labelling of a Graph via Minimum $p$-Seminorm Interpolation
Predicting the Labelling of a Graph via Minimum $p$-Seminorm Interpolation
复制标题
通过最小 $p$-Seminorm 插值预测图的标签
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Guy Lever
中科院分区：
文献类型：
--
作者：
M. Herbster;Guy Lever
我们研究预测图标签的问题。给出图表，然后逐步向学习者显示（顶点，标签）对的试验序列。在每次试验中，都会查询一个顶点，并且学习器会预测一个布尔标签。然后返回真实标签。学习者的目标是尽量减少错误预测。我们提出最小 p-半范插值来解决这个问题。为此，我们给出图标签空间上的 p-半范数。因此，在每次试验中，我们都使用最小化 p-半范数的标签进行预测，并且也与显示的（顶点，标签）对一致。当 p = 2 时，这是[22]的谐波能量最小化过程，在[1]中也称为（拉普拉斯）插值正则化。在 p → 1 的限制下，这相当于使用标签一致的最小割进行预测。我们给出了与标签一致的最小切割和图形的电阻覆盖相关的错误界限。如果连接的顶点具有不一致的标签，我们就说一条边相对于标签被切割。我们发现，用 p = 1 + (其中 → 0 作为图直径 D → ∞) 最小化 p-半范数给出了 O(Φ logD) 的界限，而当 p = 2 时则给出了 O(Φ logD) 的界限，其中 Φ 是切边的数量。
We study the problem of predicting the labelling of a graph. The graph is given and a trial sequence of (vertex,label) pairs is then incrementally revealed to the learner. On each trial a vertex is queried and the learner predicts a boolean label. The true label is then returned. The learner’s goal is to minimise mistaken predictions. We propose minimum p-seminorm interpolation to solve this problem. To this end we give a p-seminorm on the space of graph labellings. Thus on every trial we predict using the labelling which minimises the p-seminorm and is also consistent with the revealed (vertex, label) pairs. When p = 2 this is the harmonic energy minimisation procedure of [22], also called (Laplacian) interpolated regularisation in [1]. In the limit as p → 1 this is equivalent to predicting with a label-consistent mincut. We give mistake bounds relative to a label-consistent mincut and a resistive cover of the graph. We say an edge is cut with respect to a labelling if the connected vertices have disagreeing labels. We find that minimising the p-seminorm with p = 1 + where → 0 as the graph diameter D → ∞ gives a bound of O(Φ logD) versus a bound of O(ΦD) when p = 2 where Φ is the number of cut edges.