One cool way to construct a new kernel from an existing set of (base) kernels is through graphs. Let G = (V, E) be a directed acyclic graph (DAG), where V denotes the nodes and E denotes the arcs (directed edges). For convenience let us assume there is a source node s that has no incoming arc and there is a sink node t that has no outgoing arc. We put a base kernel Ke (that is, a function ke : X X X R) on each arc e = (u + v) E E. For each path P = (Up + U1 + ... + ud) with Ui-1 + U being an arc in E, we can define the kernel for the path P as the product of kernels along the path: Vx, z E X, kp(x,z) II Ku-17u: (X, Z). (1) i=1 Then, we define the kernel for the graph G as the sum of all possible s + t path kernels: Vx,z E X, KG(X, Z) = (2) KP(x,z). Pepath(s+t) 1. (1 pt) Prove that kg is indeed a kernel. 2. (1 pt) Let x = 1 and 2 = -1. Compute the kernel value kg(1, -1) for the graph in Figure 1. One cool way to construct a new kernel from an existing set of (base) kernels is through graphs. Let G = (V, E) be a directed acyclic graph (DAG), where V denotes the nodes and E denotes the arcs (directed edges). For convenience let us assume there is a source node s that has no incoming arc and there is a sink node t that has no outgoing arc. We put a base kernel Ke (that is, a function ke : X X X R) on each arc e = (u + v) E E. For each path P = (Up + U1 + ... + ud) with Ui-1 + U being an arc in E, we can define the kernel for the path P as the product of kernels along the path: Vx, z E X, kp(x,z) II Ku-17u: (X, Z). (1) i=1 Then, we define the kernel for the graph G as the sum of all possible s + t path kernels: Vx,z E X, KG(X, Z) = (2) KP(x,z). Pepath(s+t) 1. (1 pt) Prove that kg is indeed a kernel. 2. (1 pt) Let x = 1 and 2 = -1. Compute the kernel value kg(1, -1) for the graph in Figure 1