Random walk graph kernels and rational kernels
published: Sept. 7, 2007, recorded: September 2007, views: 8646
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Random walk graph kernels (Gartner et al., 2003 ; Borgwardt et al., 2005 ) count matching random walks, and are defined using the tensor product graph. Loosely speaking, rational kernels (Cortes et al., 2004, 2003, 2002 [4, 3, 2]) use the weight assigned by a transducer to define a kernel. The kernel is shown to be positive semi-definite when the transducer can be written as a composition of two identical transducers. In our talk we will establish explicit connections between random walk graph kernels and rational kernels. More concretely, we show that composition of transducers is analogous to computing product graphs, and that rational kernels on weighted transducers may be viewed as generalizations of random walk kernels to weighted automata. In order to make these connections explicit we adapt slightly non-standard notation for weighted transducers, extensively using matrices and tensors wherever possible. We prove that under certain conditions rational kernels are positive semi-definite. Our proof only uses basic linear algebra and is simpler than the one presented in Cortes et al., 2004.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !