Sylvain Iloga - Accurate comparison of tree sets using HMM-based descriptor vectors

arima:9107 - Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, August 23, 2022, Volume 36 - Special issue CRI 2021 -
Accurate comparison of tree sets using HMM-based descriptor vectors

Authors: Sylvain Iloga

    Trees are among the most studied data structures and several techniques have consequently been developed for comparing two trees belonging to the same category. Until the end of year 2020, there was a serious lack of suitable metrics for comparing two weighted trees or two trees from different categories. The problem of comparing two tree sets was not also specifically addressed. These limitations have been overcome in a paper published in 2021 where a customizable metric based on hidden Markov models has been proposed for comparing two tree sets, each containing a mixture of trees belonging to various categories. Unfortunately, that metric does not allow the use of non metric-dependent classifiers which take descriptor vectors as inputs. This paper addresses this drawback by deriving a descriptor vector for each tree set using meta-information related to its corresponding models. The comparison between two tree sets is then realized by comparing their associated descriptor vectors. Classification experiments carried out on the databases FirstLast-L (FL), FirstLast-LW (FLW) and Stanford Sentiment Treebank (SSTB) respectively showed best accuracies of 99.75%, 99.75% and 87.22%. These performances are respectively 40.75% and 20.52% better than the tree Edit distance respectively for FLW and SSTB. Additional clustering experiments exhibited 54.25%, 98.75% and 75.53% of correctly clustered instances for FL, FLW and SSTB. No clustering was performed in existing work.

    Volume: Volume 36 - Special issue CRI 2021
    Published on: August 23, 2022
    Accepted on: July 26, 2022
    Submitted on: February 21, 2022
    Keywords: Trees,Comparison of tree sets,Distance between trees,Hidden Markov Models,Classification,Clustering,Tree Edit distance,[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI],[INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG],[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation

    Consultation statistics

    This page has been seen 98 times.
    This article's PDF has been downloaded 64 times.