it.uniroma2.sag.kelp.kernel.tree

Class SmoothedPartialTreeKernel

java.lang.Object

it.uniroma2.sag.kelp.kernel.Kernel

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

it.uniroma2.sag.kelp.kernel.tree.SmoothedPartialTreeKernel

public class SmoothedPartialTreeKernel
extends DirectKernel<TreeRepresentation>

Partial Tree Kernel implementation. A Partial Tree 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)=\sum^{|F|}_i=1 I_i(n_1) I_i(n_2)\), that is the number of common fragments rooted at the n1 and n2. It can be computed as:
- if the involved node are leaves then \(\Delta_{\sigma}(n_1,n_2)=\mu\lambda\sigma(n_1,n_2)\)
- else \( * \Delta_{\sigma}(n_1,n_2)= \displaystyle \mu \sigma(n_1,n_2)\times \Big (\lambda^2 + \hspace{-2em} \sum_{\vec{I}_1,\vec{I}_2,l(\vec{I}_1)=l(\vec{I}_2)} \lambda^{d(\vec{I}_1)+d(\vec{I}_2)} \prod_{j=1}^{l(\vec{I}_1)} \Delta_{\sigma}(c_{n_1}({\vec{I}_{1j}}),c_{n_2}({\vec{I}_{2j})})\Big) \)
where:
- \(\sigma(n_1, n_2)\) is any similarity function between nodes \(n_1\) and \(n_2\), e.g., between their lexical labels;
- \(\vec I_1\) and \(\vec I_2\) denote two sequences of indexes, i.e., \(\vec I = (i_1, i_{2},..,l(I))\), with \(1 \leq i_1 < i_2 < ..< i_{l(I)} \);
- \({d(\vec{I}_1)} = \vec{I}_{1l(\vec{I}_1)} - \vec{I}_{11}+1$ and $d(\vec{I}_2)= \vec{I}_{2l(\vec{I}_2)} -\vec{I}_{21}+1$;
- \(c_{n_{1}}(h)\) is the \(h^{th}\) child of the node \(n_{1}\);
- \(\lambda, \mu \in [0,1]\) are decay factors to penalize the contribution of large sized fragments.

For more details
[Croce et al(2011)] Croce D., Moschitti A., Basili R. (2011) Structured lexical similarity via convolution kernels on dependency trees. In: Proceedings of EMNLP, Edinburgh, Scotland, UK.

Author:

Danilo Croce, Giuseppe Castellucci

Field Summary

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

representation

Constructor Summary

Constructors

Constructor and Description
SmoothedPartialTreeKernel()
SmoothedPartialTreeKernel(float LAMBDA, float MU, float terminalFactor, float similarityThreshold, StructureElementSimilarityI nodeSimilarity, String representationIdentifier)

Method Summary

Methods

Modifier and Type	Method and Description
DeltaMatrix	getDeltaMatrix()
float	getLambda() Get the Vertical Decay factor
int	getMaxSubseqLeng()
float	getMu() Get the Horizontal Decay factor
StructureElementSimilarityI	getNodeSimilarity()
float	getSimilarityThreshold()
float	getTerminalFactor()
float	kernelComputation(TreeRepresentation repA, TreeRepresentation repB) Computes the kernel similarity between two specific representations
void	setDeltaMatrix(DeltaMatrix deltaMatrix) Deprecated.
void	setLambda(float lambda)
void	setMaxSubseqLeng(int maxSubseqLeng)
void	setMu(float mu)
void	setNodeSimilarity(StructureElementSimilarityI nodeSimilarity)
void	setSimilarityThreshold(float similarityThreshold)
void	setTerminalFactor(float terminalFactor)

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

SmoothedPartialTreeKernel

public SmoothedPartialTreeKernel()

SmoothedPartialTreeKernel

public SmoothedPartialTreeKernel(float LAMBDA,
                         float MU,
                         float terminalFactor,
                         float similarityThreshold,
                         StructureElementSimilarityI nodeSimilarity,
                         String representationIdentifier)

Parameters:

LAMBDA - Horizontal Decay factor

MU - Vertical Decay Factor

terminalFactor - Multiplicative factor to scale up/down the leaves contribution

similarityThreshold - All similarity score below this threshold are ignored

nodeSimilarityI - The similarity function between tree nodes

representationIdentifier - the representation on which operate

Method Detail

getDeltaMatrix

public DeltaMatrix getDeltaMatrix()

getLambda

public float getLambda()

Get the Vertical Decay factor

Returns:

Vertical Decay factor

getMu

public float getMu()

Get the Horizontal Decay factor

Returns:

Horizontal Decay factor

getNodeSimilarity

public StructureElementSimilarityI getNodeSimilarity()

Returns:

The similarity function between tree nodes

getSimilarityThreshold

public float getSimilarityThreshold()

Returns:

The similarity threshold. All similarity score below this threshold are ignored

getTerminalFactor

public float getTerminalFactor()

Returns:

Multiplicative factor to scale up/down the leaves contribution

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

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 -

setLambda

public void setLambda(float lambda)

Parameters:

lambda - Horizontal Decay factor

setMu

public void setMu(float mu)

Parameters:

mu - Vertical Decay Factor

setNodeSimilarity

public void setNodeSimilarity(StructureElementSimilarityI nodeSimilarity)

Parameters:

nodeSimilarity - The similarity function between structure elements contained in tree nodes

setSimilarityThreshold

public void setSimilarityThreshold(float similarityThreshold)

Parameters:

similarityThreshold - All similarity score below this threshold are ignored

setTerminalFactor

public void setTerminalFactor(float terminalFactor)

Parameters:

terminalFactor - Multiplicative factor to scale up/down the leaves contribution

getMaxSubseqLeng

public int getMaxSubseqLeng()

Returns:

The maximum length of common subsequences considered in the recursion. It reflects the maximum branching factor allowed to the tree fragments.

setMaxSubseqLeng

public void setMaxSubseqLeng(int maxSubseqLeng)

Parameters:

maxSubseqLeng - The maximum length of common subsequences considered in the recursion. It reflects the maximum branching factor allowed to the tree fragments.