it.uniroma2.sag.kelp.kernel.tree

Class SubSetTreeKernel

java.lang.Object

it.uniroma2.sag.kelp.kernel.Kernel

it.uniroma2.sag.kelp.kernel.DirectKernel<TreeRepresentation>

it.uniroma2.sag.kelp.kernel.tree.SubSetTreeKernel

public class SubSetTreeKernel
extends DirectKernel<TreeRepresentation>

A SubSetTree Kernel is a convolution kernel that evaluates the tree fragments shared between two trees. The considered fragments are are subset-trees, i.e. a node and its partial descendancy (the descendancy can be incomplete in depth, but no partial productions are allowed; in other words given a node either all its children or none of them must be considered). A SubSetTree Kernel is a convolution kernel. The kernel function is defined as:
\(K(T_1,T_2) = \sum_{n_1 \in N_{T_1}} \sum_{n_2 \in N_{T_2}} \Delta(n_1,n_2)\)
where \(\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)} (1 + \Delta(c_{n_1}^j, c_{n_2}^j))\)

For more details see [Vishwanathan and Smola, 2003; Moschitti, EACL 2006] [Vishwanathan and Smola, 2003], S.V.N. Vishwanathan and A.J. Smola. Fast kernels on strings and trees. In Proceedings of Neural Information Processing Systems, 2003. [Moschitti, EACL2006] Alessandro Moschitti. Making Tree Kernels Practical for Natural Language Learning EACL, (2006)

Author:

Danilo Croce, Giuseppe Castellucci, Simone Filice

Field Summary

Fields inherited from class it.uniroma2.sag.kelp.kernel.DirectKernel

representation

Constructor Summary

Constructors

Constructor and Description
SubSetTreeKernel() SubTree Kernel: default constructor.
SubSetTreeKernel(float lambda, String representationIdentifier) SubTree Kernel
SubSetTreeKernel(String representationIdentifier) SubTree Kernel constructor.

Method Summary

Methods

Modifier and Type	Method and Description
DeltaMatrix	getDeltaMatrix() Get the DeltaMatrix used to store the evaluated delta functions of this tree kernel
boolean	getIncludeLeaves() Returns whether the leaves must be involved in the kernel computation
float	getLambda() Get the decay factor
float	kernelComputation(TreeRepresentation repA, TreeRepresentation repB) Computes the kernel similarity between two specific representations
void	setDeltaMatrix(DeltaMatrix deltaMatrix) Deprecated.
void	setIncludeLeaves(boolean includeLeaves) Sets whether the leaves must be involved in the kernel computation.
void	setLambda(float lambda) Set the decay factor

Methods inherited from class it.uniroma2.sag.kelp.kernel.DirectKernel

getRepresentation, kernelComputation, setRepresentation

Methods inherited from class it.uniroma2.sag.kelp.kernel.Kernel

disableCache, getKernelCache, getKernelComputations, getNumberOfHits, getNumberOfMisses, getSquaredNormCache, innerProduct, load, reset, save, setKernelCache, setSquaredNormCache, squaredNorm, squaredNormOfTheDifference

Methods inherited from class java.lang.Object

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

Constructor Detail

SubSetTreeKernel

public SubSetTreeKernel(float lambda,
                String representationIdentifier)

SubTree Kernel

Parameters:

lambda - Decay Factor

representationIdentifier - Identifier of the Tree representation on which the kernel works

SubSetTreeKernel

public SubSetTreeKernel(String representationIdentifier)

SubTree Kernel constructor. It uses lambda=0.4

Parameters:

representationIdentifier - Identifier of the Tree representation on which the kernel works

SubSetTreeKernel

public SubSetTreeKernel()

SubTree Kernel: default constructor. It should not be used, please use SubTreeKernel(String) or SubTreeKernel(float,String). This is only used by the json serializer/deserializer.

Method Detail

getLambda

public float getLambda()

Get the decay factor

Returns:

the decay factor

setLambda

public void setLambda(float lambda)

Set the decay factor

Parameters:

lambda - the decay factor

getDeltaMatrix

public DeltaMatrix getDeltaMatrix()

Get the DeltaMatrix used to store the evaluated delta functions of this tree kernel

Returns:

the the DeltaMatrix

setDeltaMatrix

@Deprecated
public void setDeltaMatrix(DeltaMatrix deltaMatrix)

Deprecated.

Sets the delta matrix. This method should not be used, as the new KeLP versions are optimized to automatically set the proper delta matrix

Parameters:

deltaMatrix - to set

getIncludeLeaves

public boolean getIncludeLeaves()

Returns whether the leaves must be involved in the kernel computation

Returns:

the includeLeaves

setIncludeLeaves

public void setIncludeLeaves(boolean includeLeaves)

Sets whether the leaves must be involved in the kernel computation. When leaves are included this kernel corresponds to the SST-bow kernel in SvmLightTK (option -F 2). When leaves are not included this kernel corresponds to the SST kernel in SvmLightTK (option -F 1)

Parameters:

includeLeaves - the includeLeaves to set

kernelComputation

public float kernelComputation(TreeRepresentation repA,
                      TreeRepresentation repB)

Description copied from class: DirectKernel

Computes the kernel similarity between two specific representations

Specified by:

kernelComputation in class DirectKernel<TreeRepresentation>

Parameters:

repA - the first representation in the kernel similarity

repB - the second representation in the kernel similarity

Returns:

the kernel similarity