Tree kernel computation based on tree binarization

Abstract

Machine learning use intelligent methods of data analysis from massive collections and under the pressure of applications, we are confronted with problems in which the data structure carries essential information. Linear methods of data analysis and learning were among the first to be developed. They have also been intensively studied, in particular many applications are data that can be represented in structured form (sequences, trees, graphs,. . . ). The kernel methods make it possible to find nonlinear decision functions. However, the advent of kernel methods has lead to research renewal as these methods are generic and can be applied to a wide variety of domains when we are able to conceive a kernel function. Tree kernel has been proposed for applications to machine learning in natural language processing or for the calculation of XML documents similarity. Our aim is to investigate the tree kernels proposed by (Moschitti, 2006a) and his algorithm for the evaluation of ST and SST kernels and to study the effect of these kernels on the similarity between the two analysed trees, We evaluated the impact of tree kernels in k-ary tree and its equivalent binary tree. We carried out a comparative study between tree kernel in k-ary tree and binary tree equivalent to it. the Comparison included similarity and running time. We concluded that proposed method perfect than Knuth method in some cases.