Graph branch algorithm : An optimum tree search method for scored dependency graph with arc co-occurrence constraints
-
- HIRAKAWA H.
- Knowledge Media Laboratory TOSHIBA Corporate Research & Development Center
Search this article
Abstract
Preference Dependency Grammar (PDG) is a framework for the morphological, syntactic and semantic analysis of natural language sentences. PDG gives packed shared data structures for encompassing the various ambiguities in each levels of sentence analysis with preference scores and a method for calculating the most plausible interpretation of a sentence. This paper proposes the Graph Branch Algorithm for computing the optimum dependency tree (the most plausible interpretation of a sentence) from a scored dependency forest which is a packed shared data structure encompassing all possible dependency trees (interpretations) of a sentence. The graph branch algorithm adopts the branch and bound principle for managing arbitral arc co-occurrence constraints including the single valence occupation constraint which is a basic semantic constraint in PDG.
Journal
-
- IPSJ SIG Notes
-
IPSJ SIG Notes 169 101-108, 2005
Information Processing Society of Japan (IPSJ)
- Tweet
Details 詳細情報について
-
- CRID
- 1572824502073223552
-
- NII Article ID
- 110002952166
-
- NII Book ID
- AN10115061
-
- Text Lang
- en
-
- Data Source
-
- CiNii Articles