{"id":728,"date":"2017-03-12T12:11:00","date_gmt":"2017-03-12T12:11:00","guid":{"rendered":"http:\/\/www.kelp-ml.org\/?page_id=728"},"modified":"2017-07-20T10:51:29","modified_gmt":"2017-07-20T10:51:29","slug":"kernels-on-trees","status":"publish","type":"page","link":"http:\/\/www.kelp-ml.org\/?page_id=728","title":{"rendered":"Kernels on Trees"},"content":{"rendered":"<p>they are\u00a0<a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/kernel\/DirectKernel.html\">DirectKernel<\/a>s operating on <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/data\/representation\/tree\/TreeRepresentation.html\">TreeRepresentation<\/a>s.\u00a0Tree kernels mostly differ on the tree fragments considered when they estimate the similarity between two trees. The following figure exemplifies some possible tree fragments. For more info about tree kernels, please refer to this <a href=\"http:\/\/www.kelp-ml.org\/?page_id=207\">page<\/a>. To generate tree data structures from text snippets please refer to this <a href=\"http:\/\/www.kelp-ml.org\/?page_id=1025\">page<\/a>.<\/p>\n<div id=\"attachment_273\" style=\"width: 359px\" class=\"wp-caption aligncenter\"><img aria-describedby=\"caption-attachment-273\" decoding=\"async\" loading=\"lazy\" class=\"wp-image-273\" src=\"http:\/\/www.kelp-ml.org\/wp-content\/uploads\/2017\/02\/tree_and_fragments-1.png\" width=\"349\" height=\"426\" \/><p id=\"caption-attachment-273\" class=\"wp-caption-text\">a) Constituency parse tree for the sentence <em>Federer won against Nadal<\/em>, b) some subtrees, c) some subset trees, d) some partial trees.<\/p><\/div>\n<hr \/>\n<h3>Subtree Kernel<\/h3>\n<p><strong>Java class<\/strong>: <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/SubTreeKernel.html\">SubTreeKernel<\/a><\/p>\n<p><strong>Source code<\/strong>: <a href=\"https:\/\/github.com\/SAG-KeLP\/kelp-additional-kernels\/blob\/master\/src\/main\/java\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/SubTreeKernel.java\" target=\"_blank\">SubTreeKernel.java<\/a><\/p>\n<p><strong>Maven Project<\/strong>: <a href=\"https:\/\/github.com\/SAG-KeLP\/kelp-additional-kernels\">kelp-additional-kernels<\/a><\/p>\n<p><strong>JSON type<\/strong>:\u00a0stk<\/p>\n<p><strong>Description<\/strong>:\u00a0a SubTree Kernel is a convolution kernel that evaluates the tree fragments shared between two trees. The considered fragments are subtrees, i.e., a node and its complete descendancy. For more details see (Vishwanathan and Smola, 2003).<\/p>\n<p><strong>Parameters<\/strong>:<\/p>\n<ul>\n<li><em>representation<\/em>: the String identifying the representation on which the kernel must operate<\/li>\n<li><em>includeLeaves<\/em>: whether the leaves must be involved in the kernel computation. Regardless its value, two subtrees are matched even if their leaves differ (but the other nodes must match). When it is true, matching leaves contribute to the kernel function; this corresponds to adding a bag-of-words similarity to the kernel function.<\/li>\n<li><em>lambda<\/em>: the decay factor (associated to the height of a subtree).<\/li>\n<\/ul>\n<hr \/>\n<h3>Subset Tree Kernel<\/h3>\n<p><strong>Java class<\/strong>: <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/SubSetTreeKernel.html\">SubSetTreeKernel<\/a><\/p>\n<p><strong>Source code<\/strong>: <a href=\"https:\/\/github.com\/SAG-KeLP\/kelp-additional-kernels\/blob\/master\/src\/main\/java\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/SubSetTreeKernel.java\" target=\"_blank\">SubSetTreeKernel.java<\/a><\/p>\n<p><strong>Maven Project<\/strong>: <a href=\"https:\/\/github.com\/SAG-KeLP\/kelp-additional-kernels\">kelp-additional-kernels<\/a><\/p>\n<p><strong>JSON type<\/strong>:\u00a0sstk<\/p>\n<p><strong>Description<\/strong>: the SubSetTree Kernel, a.k.a. Syntactic Tree Kernel, is a convolution kernel that evaluates the tree fragments shared between two trees. The considered fragments are subset-trees, i.e.,\u00a0a 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). For further details see (Collins and Duffy, 2001).<\/p>\n<p><strong>Parameters<\/strong>:<\/p>\n<ul>\n<li><em>representation<\/em>: the String identifying the representation on which the kernel must operate<\/li>\n<li><em>includeLeaves<\/em>: whether the leaves must be involved in the kernel computation. Regardless its value, two subtrees are matched even if their leaves differ (but the other nodes must match). When it is true, matching leaves contribute to the kernel function; this corresponds to adding a bag-of-words similarity to the kernel function.<\/li>\n<li><em>lambda<\/em>: the decay factor (associated to the height of a subset tree).<\/li>\n<\/ul>\n<hr \/>\n<h3>Partial\u00a0Tree Kernel<\/h3>\n<p><strong>Java class<\/strong>: <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/PartialTreeKernel.html\">PartialTreeKernel<\/a><\/p>\n<p><strong>Source code<\/strong>: <a href=\"https:\/\/github.com\/SAG-KeLP\/kelp-additional-kernels\/blob\/master\/src\/main\/java\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/PartialTreeKernel.java\" target=\"_blank\">PartialTreeKernel.java<\/a><\/p>\n<p><strong>Maven Project<\/strong>: <a href=\"https:\/\/github.com\/SAG-KeLP\/kelp-additional-kernels\">kelp-additional-kernels<\/a><\/p>\n<p><strong>JSON type<\/strong>: ptk<\/p>\n<p><strong>Description<\/strong>: it is a convolution kernel that evaluates the tree fragments shared between two trees. The considered fragments are partial trees, i.e.,\u00a0a node and its partial descendancy (the descendancy can be incomplete, i.e.,\u00a0a partial production is allowed). For further details see (Moschitti, 2006).<\/p>\n<p>Some examples are reported in this <a href=\"http:\/\/www.kelp-ml.org\/?page_id=207\">tutorial page<\/a>.<\/p>\n<p><strong>Parameters<\/strong>:<\/p>\n<ul>\n<li><em>representation<\/em>: the String identifying the representation on which the kernel must operate<\/li>\n<li><em>includeLeaves<\/em>: whether the leaves must be involved in the kernel computation. Regardless its value, two subtrees are matched even if their leaves differ (but the other nodes must match). When it is true, matching leaves contribute to the kernel function; this corresponds to adding a bag-of-words similarity to the kernel function.<\/li>\n<li><em>lambda<\/em>: the decay factor (associated to the length of a production, including gaps).<\/li>\n<li><em>mu<\/em>: the decay factor (associated to the height of a partial tree).<\/li>\n<li><em>terminalFactor<\/em>: multiplicative factor to scale up\/down the leaves contribution.<\/li>\n<li><em>maxSubseqLeng<\/em>: maximum length of common subsequences considered in the recursion. It reflects the maximum branching factor allowed to the tree fragments.<\/li>\n<\/ul>\n<hr \/>\n<h3>Smoothed Partial\u00a0Tree Kernel<\/h3>\n<p><strong>Java class<\/strong>: <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/SmoothedPartialTreeKernel.html\">SmoothedPartialTreeKernel<\/a><\/p>\n<p><strong>Source code<\/strong>: <a href=\"https:\/\/github.com\/SAG-KeLP\/kelp-additional-kernels\/blob\/master\/src\/main\/java\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/SmoothedPartialTreeKernel.java\" target=\"_blank\">SmoothedPartialTreeKernel.java<\/a><\/p>\n<p><strong>Maven Project<\/strong>: <a href=\"https:\/\/github.com\/SAG-KeLP\/kelp-additional-kernels\">kelp-additional-kernels<\/a><\/p>\n<p><strong>JSON type<\/strong>: sptk<\/p>\n<p><strong>Description<\/strong>: it\u00a0is a convolution kernel that evaluates the tree fragments shared between two trees (Croce et al., 2011). The considered fragments are partial trees (as for the\u00a0<a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/PartialTreeKernel.html\">PartialTreeKernel<\/a>) whose nodes are identical or similar according to a node similarity function: the contribution of the fragment pairs in the overall kernel thus depends on the number of shared substructures, whose nodes contribute according to such a metrics.<\/p>\n<p>Some examples are reported in this <a href=\"http:\/\/www.kelp-ml.org\/?page_id=207\">tutorial page<\/a>.<\/p>\n<p><strong>Parameters<\/strong>:<\/p>\n<ul>\n<li><em>representation<\/em>: the String identifying the representation on which the kernel must operate<\/li>\n<li><em>includeLeaves<\/em>: whether the leaves must be involved in the kernel computation. Regardless its value, two subtrees are matched even if their leaves differ (but the other nodes must match). When it is true, matching leaves contribute to the kernel function; this corresponds to adding a bag-of-words similarity to the kernel function.<\/li>\n<li><em>lambda<\/em>: the decay factor (associated to the length of a production, including gaps).<\/li>\n<li><em>mu<\/em>: the decay factor (associated to the height of a partial tree).<\/li>\n<li><em>terminalFactor<\/em>: multiplicative factor to scale up\/down the leaves contribution.<\/li>\n<li><em>maxSubseqLeng<\/em>: maximum length of common subsequences considered in the recursion. It reflects the maximum branching factor allowed to the tree fragments.<\/li>\n<li><em>nodeSimilarity<\/em>: it is the similarity function that must be applied when comparing two nodes. In particular, the input function must be an implementation of the <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/data\/representation\/structure\/similarity\/StructureElementSimilarityI.html\">StructureElementSimilarityI<\/a> interface. this interface allows the implementation of similarity functions between StructureElements, \u00a0i.e., the structure that KeLP associates to each node. content of each node, reflecting the node information.\u00a0This\u00a0function should return a similarity score that is a kernel itself, otherwise it is not guaranteed the convergence of \u00a0several learning algorithms, such as Support Vector Machine. Several\u00a0similarity functions are included\u00a0in KeLP. In particular, the <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/data\/representation\/structure\/similarity\/LexicalStructureElementSimilarity.html\">LexicalStructureElementSimilarity<\/a>\u00a0applies\u00a0a similarity based on word embeddings, as described in\u00a0(Croce et al., 2011). Different kernels can be defined by varying this parameter (for instance, see the below Compositionally Smoothed Partial Tree Kernel).<\/li>\n<li><em>similarityThreshold<\/em>: it is a threshold applied to the similarity function, also used to speed up the kernel computation: node pairs whose score is below this threshold are ignored in the evaluation.<\/li>\n<\/ul>\n<hr \/>\n<h3>Compositionally Smoothed Partial\u00a0Tree Kernel<\/h3>\n<p><strong>Java class<\/strong>: <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/SmoothedPartialTreeKernel.html\">SmoothedPartialTreeKernel<\/a>\u00a0in combination with an implementation of <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/data\/representation\/structure\/similarity\/compositional\/CompositionalNodeSimilarity.html\">CompositionalNodeSimilarity<\/a><\/p>\n<p><strong>Maven Project<\/strong>: <a href=\"https:\/\/github.com\/SAG-KeLP\/kelp-additional-kernels\">kelp-additional-kernels<\/a><\/p>\n<p><strong>JSON type<\/strong>: sptk<\/p>\n<p><strong>Description<\/strong>: it is an extension of the\u00a0<a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/SmoothedPartialTreeKernel.html\">SmoothedPartialTreeKernel<\/a>\u00a0that enable the\u00a0integration of \u00a0Distributional Compositional Semantic operators (implemented extending the interface\u00a0<a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/data\/representation\/structure\/similarity\/compositional\/CompositionalNodeSimilarity.html\">CompositionalNodeSimilarity<\/a>)\u00a0into the tree kernel evaluation, by acting both over lexical leaves and non-terminal, i.e. complex compositional, nodes\u00a0(Annesi et al, 2014).<\/p>\n<p>Some examples are reported in this <a href=\"http:\/\/www.kelp-ml.org\/?page_id=207\">tutorial page<\/a>.<\/p>\n<p><strong>Paramenters<\/strong>: this kernel inherits several parameters from the\u00a0<a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/kernel\/tree\/SmoothedPartialTreeKernel.html\">SmoothedPartialTreeKernel<\/a><\/p>\n<ul>\n<li><em>representation<\/em>: the String identifying the representation on which the kernel must operate<\/li>\n<li><em>includeLeaves<\/em>: whether the leaves must be involved in the kernel computation. Regardless its value, two subtrees are matched even if their leaves differ (but the other nodes must match). When it is true, matching leaves contribute to the kernel function; this corresponds to adding a bag-of-words similarity to the kernel function.<\/li>\n<li><em>lambda<\/em>: the decay factor (associated to the length of a production, including gaps).<\/li>\n<li><em>mu<\/em>: the decay factor (associated to the height of a partial tree).<\/li>\n<li><em>terminalFactor<\/em>: multiplicative factor to scale up\/down the leaves contribution.<\/li>\n<li><em>maxSubseqLeng<\/em>: maximum length of common subsequences considered in the recursion. It reflects the maximum branching factor allowed to the tree fragments.<\/li>\n<li><em>nodeSimilarity<\/em>: it is the similarity function that must be applied when comparing two nodes. In particular, the input function <strong>should\u00a0be an implementation of the \u00a0<\/strong><a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/data\/representation\/structure\/similarity\/compositional\/CompositionalNodeSimilarity.html\">CompositionalNodeSimilarity<\/a>\u00a0<strong>interface<\/strong>. This interface allows the implementation of compositional similarity\u00a0functions between <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/data\/representation\/structure\/CompositionalStructureElement.html\">CompositionalStructureElement<\/a>.\u00a0This specific similarity function between the so-called Compositional nodes \u00a0should return a similarity score that is a kernel itself, otherwise it is not guaranteed the convergence of \u00a0several learning algorithms, such as Support Vector Machine. Several\u00a0similarity functions are included\u00a0in KeLP. In particular, the <a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/data\/representation\/structure\/similarity\/compositional\/sum\/CompositionalNodeSimilaritySum.html\">CompositionalNodeSimilaritySum<\/a>\u00a0applies\u00a0a Compositional similarity based on word embeddings of both head\/modifiers elements in a semantic\/syntactic pairs, as described in\u00a0(Annesi et al., 2011), that linearly combines the embedding associated to single head and modifier in the pair. Further implementations of such\u00a0Compositional similarity functions exist, such as\u00a0<a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/data\/representation\/structure\/similarity\/compositional\/dilation\/CompositionalNodeSimilarityDilation.html\">CompositionalNodeSimilarityDilation<\/a> or\u00a0<a href=\"http:\/\/www.kelp-ml.org\/kelp-javadoc\/current-version\/it\/uniroma2\/sag\/kelp\/data\/representation\/structure\/similarity\/compositional\/product\/CompositionalNodeSimilarityProduct.html\">CompositionalNodeSimilarityProduct<\/a>.<\/li>\n<li><em>similarityThreshold<\/em>: it is a threshold applied to the similarity function, also used to speed up the kernel computation: node pairs whose score is below this threshold are ignored in the evaluation.<\/li>\n<\/ul>\n<hr \/>\n<h3>References<\/h3>\n<p>Paolo Annesi, Danilo Croce, and Roberto Basili.\u00a0<em>Semantic compositionality in tree kernels<\/em>. In Proceedings of the 23rd ACM International Conference on Conference on In- formation and Knowledge Management, CIKM \u201914, pages 1029\u20131038, New York, NY, USA, 2014. ACM.<\/p>\n<p>Michael Collins and Nigel Duffy.\u00a0<em>Convolution kernels for natural language<\/em>. In Proceedings of the 14th Conference on Neural Information Processing Systems, 2001.<\/p>\n<p>Danilo Croce, Alessandro Moschitti, and Roberto Basili.\u00a0<em>Structured lexical similarity via convolution kernels on dependency trees<\/em>. In Proceedings of EMNLP, Edinburgh, Scotland, UK., 2011.<\/p>\n<p>Alessandro Moschitti.\u00a0<em>Efficient convolution kernels for dependency and constituent syntactic trees<\/em>. In ECML, Berlin, Germany, September 2006.<\/p>\n<p>S.V.N. <span class=\"s1\">Vishwanathan<\/span> and A.J. <span class=\"s1\">Smola<\/span>. Fast\u00a0kernels on strings and trees. In Proceedings of Neural Information Processing\u00a0Systems (NIPS), 2003.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>they are\u00a0DirectKernels operating on TreeRepresentations.\u00a0Tree kernels mostly differ on the tree fragments considered when they estimate the similarity between two trees. The following figure exemplifies some possible tree fragments. For more info about tree kernels, please refer to this page. To generate tree data structures from text snippets please refer to this page. Subtree Kernel <a href=\"http:\/\/www.kelp-ml.org\/?page_id=728\" rel=\"nofollow\"><span class=\"sr-only\">Read more about Kernels on Trees<\/span>[&hellip;]<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/www.kelp-ml.org\/index.php?rest_route=\/wp\/v2\/pages\/728"}],"collection":[{"href":"http:\/\/www.kelp-ml.org\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/www.kelp-ml.org\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/www.kelp-ml.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.kelp-ml.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=728"}],"version-history":[{"count":13,"href":"http:\/\/www.kelp-ml.org\/index.php?rest_route=\/wp\/v2\/pages\/728\/revisions"}],"predecessor-version":[{"id":1041,"href":"http:\/\/www.kelp-ml.org\/index.php?rest_route=\/wp\/v2\/pages\/728\/revisions\/1041"}],"wp:attachment":[{"href":"http:\/\/www.kelp-ml.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=728"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}