Efficient Algorithm for Sentence Information Content Computing in Semantic Hierarchical Network

Hao WU  Heyan HUANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.1   pp.238-241
Publication Date: 2017/01/01
Publicized: 2016/10/18
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016EDL8177
Type of Manuscript: LETTER
Category: Natural Language Processing
Keyword: 
information content,  sentence IC,  inclusion-exclusion principle,  difference set,  hierarchical network,  

Full Text: PDF>>
Buy this Article



Summary: 
We previously proposed an unsupervised model using the inclusion-exclusion principle to compute sentence information content. Though it can achieve desirable experimental results in sentence semantic similarity, the computational complexity is more than O(2n). In this paper, we propose an efficient method to calculate sentence information content, which employs the thinking of the difference set in hierarchical network. Impressively, experimental results show that the computational complexity decreases to O(n). We prove the algorithm in the form of theorems. Performance analysis and experiments are also provided.