it.uniroma2.sag.kelp.kernel.tree

Class TreeKernelUtils

java.lang.Object

it.uniroma2.sag.kelp.kernel.tree.TreeKernelUtils

public class TreeKernelUtils
extends Object

Class providing some static methods useful for various tree kernels

Author:

Danilo Croce, Simone Filice

Constructor Summary

Constructors

Constructor and Description
TreeKernelUtils()

Method Summary

Methods

Modifier and Type	Method and Description
static ArrayList<TreeNodePairs>	findCommonNodesByProduction(TreeRepresentation a, TreeRepresentation b, DeltaMatrix deltaMatrix, boolean includeLeaves) Determine the nodes sharing the same production in the given trees.
static float	productionBasedDeltaFunction(TreeNode Nx, TreeNode Nz, int sigma, float lambda, DeltaMatrix deltaMatrix) Delta Function for tree kernels operation at production level, like SubTreeKernel and SubSetTreeKernel.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TreeKernelUtils

public TreeKernelUtils()

Method Detail

findCommonNodesByProduction

public static ArrayList<TreeNodePairs> findCommonNodesByProduction(TreeRepresentation a,
                                                   TreeRepresentation b,
                                                   DeltaMatrix deltaMatrix,
                                                   boolean includeLeaves)

Determine the nodes sharing the same production in the given trees. This is an optimization proposed in [Moschitti, EACL 2006] for a fast implementation of the SubTreeKernel and the SubSetTreeKernel.

Parameters:

a - First Tree

b - Second Tree

Returns:

The node pairs having the same production

productionBasedDeltaFunction

public static float productionBasedDeltaFunction(TreeNode Nx,
                                 TreeNode Nz,
                                 int sigma,
                                 float lambda,
                                 DeltaMatrix deltaMatrix)

Delta Function for tree kernels operation at production level, like SubTreeKernel and SubSetTreeKernel. Given two nodes \(n_1\) and \(n_2\) \(\Delta(n_1,n_2)\) can be computed as:
- if productions at \(n_1\) and \(n_2\) are different then \(\Delta(n_1,n_2)=0\)
- if the productions at n1 and n2 are the same, and \(n_1\) and \(n_2\) have only leaf children then \(\Delta(n_1,n_2)=\lambda\)
- if the productions at n1 and n2 are the same, and \(n_1\) and \(n_2\) are not pre-terminals then
\(\Delta(n_1,n_2)=\lambda \prod_{j=1}^{nc(n_1)} (\sigma + \Delta(c_{n_1}^j, c_{n_2}^j))\)

Parameters:

Nx - the root of the first tree

Nz - the root of the second tree

sigma - the sigma coefficient in the delta formula (sigma=0 for SubTreeKernel, sigma=1 for SubSetTreeKernel)

lambda - the lambda decay factor in the delta formula

DeltaMatrix - the delta matrix where the partial delta evaluations are stored

Returns:

the result of the delta function