Automatic Acquisition of Useful English
Expressions Using Dependency Relations
Yoshihide Kato

Kazuya Kuzuhara

Shigeki Matsubara

Information Technology Center
Nagoya University
Furo-cho, Chikusa-ku, Nagoya
464-8601 Japan

Graduate School of Information Science
Nagoya University
Furo-cho, Chikusa-ku, Nagoya
464-8601 Japan

Graduate School of Information Science
Nagoya University
Furo-cho, Chikusa-ku, Nagoya
464-8601 Japan

Abstract—In this paper, we propose a method to acquire
English expressions useful for academic writing. The method
utilizes dependency relations between words and their statisticalinformation. It acquires subsequences of English sentences whose
words are connected with dependency relations, and discriminates useful ones for academic writing by using statistical information. We conducted an experiment and the result demonstrates
the effectiveness of our method.

I. I NTRODUCTION
English academic writing is a difficult task for non-nativeresearchers. To reduce the difficulty, they often rely on lexicaof English phrases (e.g. [4], [5]) to know useful expressions
for English academic writing. However, the lexica do not havesufficient amounts of expressions.
To solve this problem, Kozawa et al. have proposed amethod of automatically extracting phrasal English expressions from English research papers[2]. Their method extracts
word sequences useful for English academic writing by using
statistical information such as their frequencies. However, their
method has the following drawbacks:
The method cannot obtain the expressions which are in
the form of discontinuous word sequences.
• The method may mistakenly obtain expressions whose
words have no relationship.
•To overcome the drawbacks, we propose a method ofextracting English expressions utilizing dependency relations.
Our proposed method extracts word sequences whose words
are connected with dependency relations. Our method canobtain English expressions which are in the form of discontinuous word sequences, because dependency relations
exist between discontinuous words. Furthermore, the obtained
expressions are guaranteed to be connected with dependencyrelations.
To demonstrate the effectiveness of our method, we conducted an experiment. We extracted English expressions fromthe proceedings of the ACL from 2001 to 2008. We evaluatedthe precision and the recall of our method. The precision is38.0% and the recall is 81.5%.
This paper is organized as follows: Sec. II describes whatkind of expressions we want to acquire. Sec. III proposes amethod of acquiring English expressions using dependency

relations. Sec. IV reports an experimental result. Sec. V
concludes this paper.
II. E NGLISH E XPRESSIONS AND THEIR ACQUISITION
This section explains the English expressions which wewant to acquire. In this paper, the term “English expression” isused to describe a word sequence which satisfies the following
conditions:••It is useful for English academic writing.
It can be used as an indexing term of lexica.

As an example, let us consider the following word sequences:
1) In this paper, we describe . . .
2) The reason why . . . is that . . .
3) For instance, it . . .
Word sequences 1) and 2) are English expressions. These word
sequences are useful for English academic writing. On theother hand, word sequence 3) is not an English expression.
Though it may be useful for English academic writing, we do
not want to use it as an indexing term. Because the word “it”
is unnecessary. The word sequence “For instance, . . .” is more
appropriate for the indexing term. Our aim is to automaticallyacquire word sequences such as 1) and 2) and to discard word
sequences such as 3).
A. Previous Works
Kozawa et al. proposed a method of extracting English
expressions from research papers[2]. Their method discriminates English expressions using statistical information about
word sequences. The method cannot obtain discontinuous
English expressions such as 2). The reason is that the method
first extracts continuous word sequences which occur in research papers and selects English expressions from the wordsequences. Because the word sequence “The reason why”
and the word sequence “is that” in English expression 2)
usually appear separately in sentences, the word sequence“the reason why . . . is that . . .” is not extracted at the firststage. Furthermore, the method may mistakenly obtain word
sequence 3) as an English expression, when it frequentlyoccurs in the research papers.

In this paper, we describe ...

The reason why ... is that ...

For instance, it ...
Fig. 1.

dependency relations in English expressions

B. Syntactic Characteristic of English ExpressionsTo solve the problem described in the previous section,
we focus on dependency relations which appear in English
expressions. Dependency relations refer to certain kinds ofrelations between words, such as modifier-modifee relations,predicate-argument relations and so on. From the viewpoint ofdependency relations, word sequence 1) and 2) are connectedwith dependency relations (see Fig.1). On the other hand, word
sequence 3) is not connected with dependency relations. In
general, English expressions are connected with dependency
relations. An important point is that discontinuous English
expression 2) is connected with dependency relations. By
extracting word sequences whose words are connected withdependency relations, we expect that discontinuous English
expressions such as 2) can be obtained and that the numberof the word sequences such as 3) which are not English
expressions is reduced.
III. E NGLISH E XPRESSION ACQUISITION BASED ON
D EPENDENCY R ELATIONSThis section proposes a method of extracting English expressions using dependency relations. The outline of ourproposed method is as follows:1) English sentences in research papers are parsed by adependency parser. Each parsed sentence is represented
as a dependency tree.
2) Frequent tree patterns are extracted from the dependency
trees. The tree patterns corresponds to continuous ordiscontinuous word sequences.
3) Tree patterns which correspond to English expressions
are discriminated using statistical information about dependency relations.
4) Word sequences are recovered from the discriminatedtree patterns.
A. Tree Representation of Dependency Relations
Our proposed method focuses on dependency relations. Dependency relations refer to certain kinds of relations between
words. In a dependency relation, one word is called head,
and the other word is called dependent. When a word wd isa dependent of a word wh , we say that wd depends on wh ,and write wd → wh . The dependency relations in a sentence
can be represented as a tree structure. Each node is labeledwith a word in the sentence. When a word wd depends ona word wh , the node labeled with wd is a child of the nodelabeled with wh . By extracting tree patterns which occur in thedependency trees, our method obtains word sequences whose
words are connected with dependency relations. However,word sequences cannot be recovered from the tree patterns,
because they lack the following information:
1) There is no information about word order. When a nodelabeled with wd is a child of a node labeled with wh ,we cannot determine whether wd precedes wh or not.
2) There is no information about abbreviations of constituents, which are represented by the symbol “. . .” inEnglish expressions.
To avoid this problem, we extend the tree structures as follows:
1) Each node which corresponds to a word has two children. The children’s labels are LEFT and RIGHT. If aword wd depends on a word wh from left, the node
wd is the child of the LEFT node of the node wh . If wd
depends on wh from right, the node wd is the child of theRIGHT node of the node wh . By using this additional
nodes, we can determine the order of the words in adependency tree.
2) Each node has additional information about constituents.
For example, if the words dominated by a node constitute a noun phrase, the node is labeled with ⟨NP⟩.
B. Extracting Tree Patterns
To obtain word sequences whose words are connected withdependency relations, our method parses sentences in English
research papers by using a dependency parser, and extracts tree
patterns from the parsed sentences. Because it is intractable toextract all tree patterns, we uses a tree mining algorithm basedon FREQT[1]. FREQT extracts frequent tree patterns from a
set of trees. At first, FREQT extracts frequent tree patterns
with size 1, which consist of single nodes. Then, FREQT
iteratively enumerates candidate tree patterns with size k byattaching new nodes to the frequent tree patterns with sizek − 1, and discards the tree patterns whose frequencies is lessthan a threshold.
We extend FREQT to deal with the symbol “. . .” in English
expressions. In our method, several nodes in the dependency
trees have labels which represent constituents. The labels
correspond to the symbol “. . .”. For example, The English
expression “The reason why . . . is that . . .” are obtained fromthe tree pattern shown in Fig. 2. To extract this kind of tree
patterns, we extend the enumeration of tree patterns as follows:• In attaching node phase, if the attached node has constituent label, our method creates two tree patterns: theone is the result of attaching a node labeled with its wordlabel, the other is the result of attaching a node labeledwith its constituent label.
Furthermore, our method does not attach a node in thefollowing case:T rees(T ) is a set of trees which match T . N odes(n, T ) is aset of nodes which is defined as follows:

isLEFT

RIGHT

reasonthatLEFT

RIGHT

RIGHT

thewhy

<CL>

RIGHT
<CL>
Fig. 2. the tree pattern corresponding to the expression “the reason why ...
is that ...”

N odes(n, T )= {m | ∃TD ∈ T rees(T )[m is a node of TD
and m corresponds to n]}
N odes(n, T ) is a set of nodes which corresponds to n. For anode n of a tree pattern T , we define four types of adjacentnodes of n as follows:
Adr (n, T )= {m′′ | ∃m, m′ [m ∈ N odes(n, T )and m′ is the parent of m
and m′ has the label RIGHT
and m′′ is the parent of m′ ]}•New node is not attached to the node with a constituent
label of a tree pattern.

C. Discriminating English Expressions
Previous section describes a method of extracting frequent
tree patterns. By recovering word sequences from the treepatterns, we can obtain frequent word sequences whose words
are connected with dependency relations. Here, note that not
all the frequent word sequences are English expressions. Our
method selects English expressions from the frequent wordsequences by using statistical information about tree patterns.
1) Discrimination Based on Statistical Information: Firstof all, let us consider the following word sequences:
1) the reason why . . . is2) the reason why . . . is that
Word sequence 2) includes word sequence 1). If word sequence 1) frequently co-occurs the word “that”, word sequence2) is more useful than 1). That is, we want to accept word
sequence 2) and discard word sequence 1).
Our method discards word sequences which are included
by useful word sequences by using statistical information. Inorder to do so, for each node in the tree patterns, our method
assesses whether a specific word or constituent is attached toit. We define an entropy of a node label. That the entropyof a node label of a tree pattern is low means that the nodefrequently labeled with a specific word or constituent. Thatis, the possibility that the tree pattern is a part of an English
expression is high. Our method discards the tree patterns.
In the following, we define the entropy of a node label of atree pattern. First of all, we introduce some notations. Let D
be a set of dependency trees, which are obtained from English
research papers. Let T and n be a tree pattern and a node in
T , respectively. T rees(T ) is a set of trees which is defined asfollows:
T rees(T ) = {TD | TD matches T and TD occurs in D}

Adl (n, T )= {m′′ | ∃m, m′ [m ∈ N odes(n, T )and m′ is the parent of m
and m′ has the label LEF T
and m′′ is the parent of m′ ]}Ahr (n, T )= {m′′ | ∃m, m′ [m ∈ N odes(n, T )and m′ is a child of m
and m′ has the label RIGHT
and m′′ is a child of m′ ]}Ahl (n, T )= {m′′ | ∃m, m′ [m ∈ N odes(n, T )and m′ is a child of m
and m′ has the label LEF T
and m′′ is a child of m′ ]}We define EX(T, n, type) as a set of labels with which theadjacent nodes of n are labeled as follows (see Fig.3):
EX(T, n, type)= {l | ∃m ∈ Atype (n, T )[l is the label of m
and m does not correspond to any node in T ]or [Atype (n, T ) = ∅ and l = null]}null is a special symbol which represents that n has noadjacent nodes. We define an entropy of labels of adjacentnodes as follows:
Htype (L | T, n)∑= −l∈EX(T,n,type)

Ptype (L = l | T, n) log Ptype (L = l | T, n)TABLE I

A set of tree
isisLEFT

LEFT
reasonreasonLEFT
thenulla tree pattern T
reason

nLEFT

LEFT

RIGHT

thewhyLEFT
reasonRIGHT

theforelements of EX(T, n, hr)

an example of EX(T, n, type)Fig. 3.

where L is a random variable which represents node labels.
Ptype (L = l | T, n) is the probability that the label of anadjacent node of n is l. The probability is defined as follows:
Ptype (l | T, n)=∑

our method
Kozawa et al.

precision(%)
37.8%
23.5%

recall(%)
81.5%
72.8%

F-value
51.7
35.5

theseems

LEFT

AN EXPERIMENTAL RESULT

C(expand(T, n, type, l))l∈EX(T,n,type) C(expand(T, n, type, l))where C(·) is the frequency of a tree pattern.
expand(T, n, type, l) is the tree pattern which is obtained byattaching a node with label l. When type = dr, the procedure
is as follows:
1) A node labeled with RIGHT is attached to n as its
parent (Let n′ be the attached node.).
2) A node labeled with l is attached to n′ as its parent.
Our method utilizes the entropy measure to discriminate
word sequences which are parts of English expressions. Our
method discards a tree pattern T , if the following conditions
hold for some n in T and some type ∈ {dr, dl, hr, hl}:1) Ptype (null|T, n) < α2) Htype (L|T, n) < β
α and β are thresholds. Condition 1) means that the node nfrequently has adjacent nodes. Condition 2) means that theadjacent nodes of n has a specific label.
IV. A N E XPERIMENTTo demonstrate the effectiveness of our method, we conducted an experiment. We used 165,116 sentences in theproceedings of the ACL from 2001 to 2008, and 500 word
sequences as evaluation data, which are extracted from thesentences. For each word sequence, whether it is an English
expression or not is manually judged. The sentences are parsed
using the parser Enju[3] and converted to dependency relations
using Pennconverter[6].

We set α and β to 0.5 and 1.3, respectively. We extracted
1,925,449 tree patterns from the proceedings. Our method
selects 127,059 word sequences obtained from tree patterns as
English expressions. We measured the precision and the recallof our method using the evaluation data. The result is shown in
Table I. Our method outperforms the previous method basedon word sequences. This result demonstrates the effectivenessof our method based on dependency relations.
We show examples of English expressions obtained by ourmethod.
• the fact that . . . suggests that . . .
• since . . . we can conclude that . . .
These examples show that our method can acquire English
expressions which are in the form of discontinuous word
sequences.
V. C ONCLUSION
This paper proposed a method of acquiring English expressions using dependency relations. Our method represents
sentences as dependency trees, and extracts frequent tree
patterns to obtain frequent word sequences whose words areconnected with dependency relations. Our method selects
English expressions for academic writing from the obtained
word sequences using statistical information about dependency
relations. An experimental result demonstrates that the dependency relation-based approach outperforms the word sequencebased approach.
Our method cannot obtain less frequent English expressions.
To overcome this problem, we will use a huge amount ofresearch papers to acquire English expressions.
ACKNOWLEDGMENT
This research is partially supported by the Kayamori Foundation of Informational Science Advancement.
R EFERENCES[1] T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Sakamoto and S. Arikawa:
Efficient Substructure Discovery from Large Semi-structured Data, Proc.
of 2nd SIAM Int. Conf. on Data Mining, pp.158–174, 2002.
[2] S. Kozawa, Y. Sakai, K. Sugiki and S. Matsubara: Automatic Extractionof Phrasal Expressions for Supporting English Academic Writing, Proc.
of 2nd Int. Symposium on Intelligent Decision Technologies, pp.485–493,
2010.
[3] Y. Miyao and J. Tsujii: Feature Forest Models for Probabilistic HPSG
parsing, Computational Linguistics, 34(1), pp.35–80, 2008.
[4] K. Sakimura: Useful Expressions for Research papers in English, Sogensha (1991) (in Japanese)[5] T. Sugino and F. Ito: How to Write a Better English Thesis, Natsume-sha(2008) (in Japanese)[6] http://fileadmin.cs.lth.se/nlp/software/pennconverter/pennconverter.jar