Presentation	2002/4/18 Path Kernels and Multiplicative Updates Eiji TAKIMOTO, Manfred WARMUTH,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Assume a directed graph with a source and a sink is given. We maintain transition probabilities v_e on the edges which define the path probability w_P=П_> for any source-sink path P. Each such path contributes a feature w_P to the feature vector w=Ф(v) and we consider the kernel associated with the feature mapping Ф. In various problems the edges are given weights x_e and it is required to calculate values based on the kernel computation K(v,x)=Ф(v)・Ф(x)=Σ_PП_>. Moreover the edge weights v_e are often multiplicatively updated where the update contributes a factor to each edge. Now the new path weights may not sum to one any more. However some clever algorithms re-normalize the path weights so that the total outflow out of each node is one again. Under this framework we give some applications such as a dynamic routing problem, an on-line shortest path problem and on-line pruning problem of a decision graph defined by a regular expression.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	kernel / on-line prediction / multiplicative weight update / dynamic routing / shortest path problem / pruning
Paper #	COMP2002-7
Date of Issue

Conference Information
Committee	COMP
Conference Date	2002/4/18(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Path Kernels and Multiplicative Updates
Sub Title (in English)
Keyword(1)	kernel
Keyword(2)	on-line prediction
Keyword(3)	multiplicative weight update
Keyword(4)	dynamic routing
Keyword(5)	shortest path problem
Keyword(6)	pruning
1st Author's Name	Eiji TAKIMOTO
1st Author's Affiliation	GSIS, Tohoku University()
2nd Author's Name	Manfred WARMUTH
2nd Author's Affiliation	Computer Science Department, UC Santa Cruz
Date	2002/4/18
Paper #	COMP2002-7
Volume (vol)	vol.102
Number (no)	31
Page	pp.pp.-
#Pages	8
Date of Issue