Path Kernels and Multiplicative Updates
Path Kernels and Multiplicative Updates
复制标题
DOI：
10.1007/3-540-45435-7_6
复制
发表时间：
2002-07
期刊：
影响因子：
--
通讯作者：
Eiji Takimoto;Manfred K. Warmuth
中科院分区：
文献类型：
--
作者：
Eiji Takimoto;Manfred K. Warmuth
我们考虑由有向图定义的自然卷积核。每条边贡献一个输入。沿着路径的输入沿着形成乘积，并且对所有路径的乘积求和。我们还在边缘上设置了一组概率，以便每个节点的流出量为1。然后，我们讨论乘法更新这些图的预测基本上是一个内核计算和更新有助于每个边缘的一个因素。现在从每个节点流出的总流量不再是1了。然而，一些聪明的算法重新规范化路径上的权重，使每个节点的总流出量再次为1。最后，我们讨论了使用正则表达式来加速内核和重新规范化计算。特别是，我们重写的乘法算法，预测以及最好的修剪一系列并行图的高效内核计算。
We consider a natural convolution kernel defined by a directed graph. Each edge contributes an input. The inputs along a path form a product and the products for all paths are summed. We also have a set of probabilities on the edges so that the outflow from each node is one. We then discuss multiplicative updates on these graphs where the prediction is essentially a kernel computation and the update contributes a factor to each edge. Now the total outflow out of each node is not one any more. However some clever algorithms re-normalize the weights on the paths so that the total outflow out of each node is one again. Finally we discuss the use of regular expressions for speeding up the kernel and re-normalization computation. In particular we rewrite the multiplicative algorithms that predict as well as the best pruning of a series parallel graph in terms of efficient kernel computations.