Parallel Tree Kernel Computation
Souad Taouti Hadda Cherroun Djelloul Ziadi
Tree kernels are fundamental tools that have been leveraged in many
applications, particularly those based on machine learning for Natural Language
Processing tasks. In this paper, we devise a parallel implementation of the
sequential algorithm for the computation of some tree kernels of two finite
sets of trees (Ouali-Sebti, 2015). Our comparison is narrowed on a sequential
implementation of SubTree kernel computation. This latter is mainly reduced to
an intersection of weighted tree automata. Our approach relies on the nature of
the data parallelism source inherent in this computation by deploying the
MapReduce paradigm. One of the key benefits of our approach is its versatility
in being adaptable to a wide range of substructure tree kernel-based learning
methods. To evaluate the efficacy of our parallel approach, we conducted a
series of experiments that compared it against the sequential version using a
diverse set of synthetic tree language datasets that were manually crafted for
our analysis. The reached results clearly demonstrate that the proposed
parallel algorithm outperforms the sequential one in terms of latency.