Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo khoa học: "Graph Branch Algorithm: An Optimum Tree Search Method for Scored Dependency Graph with Arc Co-occurrence Constraints"

Various kinds of scored dependency graphs are proposed as packed shared data structures in combination with optimum dependency tree search algorithms. This paper classifies the scored dependency graphs and discusses the specific features of the “Dependency Forest” (DF) which is the packed shared data structure adopted in the “Preference Dependency Grammar” (PDG), and proposes the “Graph Branch Algorithm” for computing the optimum dependency tree from a DF. This paper also reports the experiment showing the computational amount and behavior of the graph branch algorithm. . | Graph Branch Algorithm An Optimum Tree Search Method for Scored Dependency Graph with Arc Co-occurrence Constraints Hideki Hirakawa Toshiba R D Center 1 Komukai Toshiba-cho Saiwai-ku Kawasaki 210 JAPAN hideki.hirakawa@toshiba.co.jp Abstract Various kinds of scored dependency graphs are proposed as packed shared data structures in combination with optimum dependency tree search algorithms. This paper classifies the scored dependency graphs and discusses the specific features of the Dependency Forest DF which is the packed shared data structure adopted in the Preference Dependency Grammar PDG and proposes the Graph Branch Algorithm for computing the optimum dependency tree from a DF. This paper also reports the experiment showing the computational amount and behavior of the graph branch algorithm. 1 Introduction The dependency graph DG is a packed shared data structure which consists of the nodes corresponding to the words in a sentence and the arcs showing dependency relations between the nodes. The scored DG has preference scores attached to the arcs and is widely used as a basis of the optimum tree search method. For example the scored DG is used in Japanese Kakari-uke analysis1 to represent all possible kakari-uke dependency trees Ozeki 1994 Hirakawa 2001 . McDonald et al. 2005 proposed a dependency analysis method using a scored DG and some maximum spanning tree search algorithms. In this method scores on arcs are computed from a set of features obtained from the dependency trees based on the Kakari-uke relation widely adopted in Japanese sentence analysis is projective dependency relation with a constraint such that the dependent word is located at the left-hand side of its governor word. optimum parameters for scoring dependency arcs obtained by the discriminative learning method. There are various kinds of dependency analysis methods based on the scored DGs. This paper classifies these methods based on the types of the DGs and the basic well-formed .