Automated Acquisition of Case Frames with Case Order
Kiyonori Ohtake, Masahiko Nedu, Shigeru Masuyama, andDepartment of Knowledge-based Info. Eng., Toyohashi University of Technology
1-1 Hibarigaoka, Tempaku-cho, Toyohashi 441-8580, Japan{otake,nedu,masuyama}@smlab.tutkie.tut.ac.jp
Kazuhide Yamamoto
ATR Interpreting Telecommunications Research Laboratories
2-2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0288, Japan
yamamoto@itl.atr.co.jp
Abstract
This paper proposes a case transition networkmodel to provide a framework for representingcase order information in addition to a Japanesecase frame. The model is regarded as an extension of bi-gram model employing a case element
as a unit. A preliminary investigation of themodel leads us to the conclusions that the transition network has sufficient capacity to acquirecase frames with case order.

1

word orders ignored difference of verbs, and did
not mention that whether patterns of word orders differ depending on a verb or not. If patterns of word orders differ depending on a verb,
word order information must be useful on detailing a verbal semantic classification.
The acquisition of case frames with case order
has a great significance from the practical pointof view. We hope that case frames with caseorder will be applied to:• acquisition of information, such as stress,
that will contribute to a pragmatic context
analysis,• detailing a verbal semantic classification,and• generation of sentences with natural caseorder.

Introduction

Case frames are useful for syntactic and semantic disambiguation. However, case frames whichhave been collected are insufficient for natural
language processing systems because most of
the past works collecting case frames were performed manually(e.g. (IPA, 1987)).
We propose a model which considers the order of case element in a simple sentence anda method acquiring verbal case frames statistically. Here, a case element is composed of thesemantic features and the case marker, and wecall it a simple sentence if a sentence has only
one verb and there has been no noun after the
position of the verb.
Although a number of studies have been doneon automatic acquisition of Japanese verbal
case frames(Mine et al., 1997; Oishi and Matsumoto, 1995), there is no consideration on thecase orders in the case frames, because changing a case order does not affect the meaning
expressed by the case frame.
Although Japanese is considered to be a free
word-ordered language, the most general orderis as follows: “a time ingredient – a place ingredient – a nominative – a dative – an accusative– a verb(Teramura et al., 1987)”, and this fact
is confirmed statistically in (Institute, 1964).
However, the investigation(Institute, 1964) of

2

Case transition network

We propose the case transition network as aframework for representing case order in addition to a case frame. We consider a methodof acquiring case frames statistically from instances on a monolingual corpus.
We expand the bi-gram model employing acase element as a unit to reflect the word orderprecisely. The method proposed in this paper
acquires surface verbal case frames by learningfrom a monolingual corpus on the case transition network.
The case transition network is roughly illustrated in Fig. 1. Outline of the learning on themodel is as follows.
1. The model scans a case element from the
beginning of a sentence.
2. The model transits a state to another by
the appearance of a case element. Thenthe weight on the arc is calculated.

3. Finally, transition reaches to the terminal
state by the appearance of a verb, andlearning for a sentence is completed.
A path from the starting state to the terminal state, which consists of arcs having non-zerovalue, represents a case frame.
Starting
state

...

...

s i,m

s i+1,m

.
.
.

.
.
.

Terminal
state

Fig. 1: Overview of the case transition networkmodel
The case transition network model is formallydefined as follows. When a verb v, and a number of case elements n are given, the case transition network N (v, n) = (S, A, w) is composedof three components, set S of states, set A ofarcs, and weight w of arcs.
State: There are three kinds of states: starting,intermediate, and terminal states. A startingstate corresponds to the beginning of a simple
sentence, an intermediate state corresponds to acase element, and a terminal state corresponds
to a verb. Each case transition network has exactly one starting and one terminal state. Intermediate states are distinguished by the appearance position, and are divided into layers. Eachlayer consists of all case elements. An intermediate state is represented by si,m (1 ≤ i ≤ n),
where i denotes the position of a case element
in a simple sentence, and m denotes a case element.
Arc: An arc represents the relation between
two states. The transition, from si,k to si+1,l ,is represented by arc (si,k , si+1,l ). An arc(si,k , si+1,l ) has a weight w(si,k , si+1,l ).
The weight on arcs: The weight w(si,k , si+1,l )is given by the conditional probabilityp(si+1,l |si,k ), where p(si,k , si+1,l ) corresponds
to the transitional probability from s i,k to
si+1,l and p(si,k ) corresponds to the appearance
probability of si,k . Then the p(si+1,l |si,k ) is
given by formula (1).
w(si,k , si+1,l ) = p(si+1,l |si,k ) =p(si,k , si+1,l )p(si,k )(1)

A sequence of case elements are represented
by a path from the starting state to the terminal
state. We call it learning to give the weights tothe arcs.
The presuming probability in appearance fora sequence of case elements by a case transition
network is given by the product of the weights
on arcs at the path. For the definition of thecase transition network, the network may have acase frame which does not appear in the corpus
for learning. We expect that when the network
has a case frame which does not appear in the
corpus but has a high appearance probability,
the case frame will be practically useful.

3

Experiments

To examine the appropriateness of the casetransition network, we carried out two experiments. Firstly, to examine how much information of a sequence of case elements is preservedby the case transition network, we executed
experiments of comparing the frequency of asequence of case elements with the presumed
probability by the case transition network. Thisis because, the case transition network basedon a bi-gram model, therefore the network does
not handle long distance dependencies of cases.
Secondly, we investigated whether the case order information by a case transition network is
proper or not.
We used articles in The Nihon Keizai Shimbun, a Japanese daily newspaper for business,
as a corpus. We obtained 557,048 sentences as aconsequence of extracting simple sentences fromthe corpus.
We must assign semantic features to anoun.
We adopted eighteen semantic features mentioned in IPAL verb dictionary(IPA,
1987) which is collected manually by IPA(The
Information-technology Promotion Agency,
Japan).
We constructed a dictionary toassign semantic features to nouns by allocating semantic features to categories of the‘Kadokawa Ruigo Shinjiten’ (Kadokawa New
Thesaurus)(Oono and Hamanishi, 1981), andwe revised a part of the dictionary. We also
added some nouns to the dictionary.
We picked up nine postpositional particles:“ha, ga, wo, ni, kara, he, to, yori, de” as casemarkers. Note that, although ‘ha’ is not a casemarker, we handle, in this paper, the ‘ha’ forThe probability in appearance which ispresumed by the case transition network
for a sequence of case elements

special postpositional particle as a case marker.
The method of extracting a sequence of caseorder for a verb is given as follows.
1. We obtain simple sentences in advance
where a verb is designated from the corpus
analyzed by morphological analyzer JUMAN1 .
2. The simple sentence is parsed by KNP 1 .
3. We mark the case elements which consistof a noun and a case marker in the parsed
sentence. If there is a suffix, the noun andthe suffix are put together as a noun.
4. We assign semantic features to each nounin case elements by exact matching. If we
can not assign semantic features to a noun
by exact matching, we try the longest-first
method from behind of the noun. Finally,
when we can not assign semantic features
to a noun, then we mark the noun as impossible assignment. It is possible that anoun is assigned several semantic features.
5. We output the sequence of case elements.
When a noun is assigned several semantic features in a sequences of case elements, sequencesof case elements in compliance with the numberof semantic features are produced.
We choose the verbs, “hiraku(to open),hajimeru(to begin), matomeru(to organize),deru(to exit), hairu(to enter)”, which have beenranked higher in the corpus as a subject of ourinvestigation.
3.1

1

http://pine.kuee.kyoto-u.ac.jp/nl-resource/

0.06
0.05
0.04
0.03
0.02
0.01
0

0

50

100

150

200

250

300

350

The frequency of a sequence of case elementsin the learning corpus

Fig. 2: The relation between presumed sequences of case elements by the network and thesequences in the corpus for the verb, ‘hiraku’appearance probability becomes higher in proportion to the frequency of sequences by caseelements in the corpus in a manner similar tothe case of Fig. 2.
3.2 Investigation of case orders
To evaluate how case orders are preserved by thecase transition network, we examined sentences
having three case elements.
We defined preservation ratio to evaluate it asfollows. Firstly, when a number of case elements
is three, a sequence αi of case elements, andsequences obtained by changing case order of α i ,consist of six sequences, then we let {α i1 , ..., αi5 }stand for the sequences except αi . In addition,
we defined a function g:g(αi ) ≡Investigation of probability
presumed

We experimented on condition that a verb is ‘hiraku(to open)’, and the number of case elements
in a simple sentence is equal to three. Fig. 2
demonstrates the relevance between presumed
sequences of case elements by the network andfrequencies of sequences of case elements in thelearning corpus. In Fig. 2, the horizontal axis
indicates the frequency of a sequence of case elements, and the vertical axis indicates the probability of appearance for a sequence of case elements presumed by the case transition network.
We also investigated the other verbs. Though
the frequency and presumed appearance probability differ, the result shows that the presumed

0.07

 1, ∀j, p(αi ) > p(αij ),s.t. f (αi ) > f (αij ),0, otherwise.

Here, f (αi ) denotes the frequency of αi at the
corpus, and p(αi ) denotes the presuming probability by the case transition network of α i . Let
Z be a set of sequences obtained by learning.
Then the preservation ratio of case orders is defined by the following formula.
P∀αi ∈Z g(αi )|Z|× 100(%)(2)

The results on investigation of five verbs areshown in Table 1.

4

Discussions

Fig. 2 shows that the case transition network
presumes a sequence of case elements in pro-Table 1: The preservation ratio of case orders
the verb(A) (%) (B)hiraku(to open)
95.0
2143
hajimeru(to begin)
98.7
1304
matomeru(to organize)
97.2
205
deru(to exit)
97.6
336
hairu(to enter)
95.7
419
average
96.8
881.4(A): the preservation ratio of case order(B): the number of simple sentences
portion to the frequency of the sequence of caseelements in the corpus for learning. We canconclude by Table 1 that the transition network
is a model which sufficiently preserves the caseorder information. These results lead us to theconclusion that the transition network has a sufficient capacity to acquire case frames with caseorder.
When the number of case elements in a simple
sentence is not less than three, the case transition network can cope with the problem of data
sparseness by definition. However, the verification of the capacity to cope with the data
sparseness is difficult owing to the ambiguity inthe dictionary of semantic features.
In this model, we can assign several semantic
features to each noun. Consequently, several semantic features on a noun demand the several
learning sequences of case elements. Hence thenumber of learning sequences is very large compared with the number of simple sentences. For
example, if a verb is ‘hiraku(to open)’, and thenumber of case elements in a simple sentence isthree, then 5,256 learning sequences of case elements are obtained from 2,143 simple sentences.
It is easy for us to imagine that the above fact
will do harm to the learning process of the casetransition network. For the reasons mentioned
above, employing a semantic feature dictionary
with high quality will be needed to improve thecase transition network. How to tackle these
problems remains for future work.
Unfortunately, we could not examine the ability of the case transition network for detailing verbal semantic classification. However, theverb ’hiraku’ has two examples “N1 ga N2 de
N3 wo” and “N1 ga N2 wo N3 de” as semantically different examples in the IPAL verb dictionary(IPA, 1987). The fact encourages us tobelieve the possibility of verbal semantic classification by the case transition network.

5

Conclusion

We proposed the case transition network model
for acquiring case frames automatically. The
case transition network is remarkable as it preserves case order on case frames. The following
conclusions were derived from our experimental
results and discussions.
1. The proposed case transition network presumes a sequence of case elements in proportion to the frequency of case elements
sequence frequency in a learning corpus.
2. The network has a sufficient ability to keepcase order.
3. Employing a semantic feature dictionary
with high quality will be required for improving the case transition network forpractical use.

Acknowledgment
The authors are heartily grateful to Kadokawa
Publishing Co. who provided ‘Kadokawa Ruigo
Shinjiten’ (Oono and Hamanishi, 1981) in amachine-readable form.

References
The National Language Research Institute,1964. Vocabulary and Chinese Characters in
Ninety Magazines of Today (3)–Analysis–,pages 171–239. SHUEI SHUPPAN, Japan.
(in Japanese).
IPA, 1987. IPA Lexicon of the Japanese Language for computers IPAL (Basic Verbs). (inJapanese).
T. Mine, M. Higashi, and M.Amamiya. 1997.
Case frame acquisition and verb sense disambiguation on a large scale electronic dictionary. In Proc. of NLPRS ’97, pages 221–226.
A. Oishi and Y. Matsumoto. 1995. Lexical knowledge acquisition for Japanese verbs
based on surface case pattern analysis. Trans.
of IPSJ, 36(11):2597–2610. (in Japanese).
S. Oono and M. Hamanishi. 1981. Kadokawa
Ruigo Shinjiten (Kadokawa New Thesaurus).
Kadokawa Publishing Co. (in Japanese).
H. Teramura, Y. Suzuki, N. Noda, and Makoto
Yazawa, editors. 1987. Case Study Nihon
Bunpou(Case Studies of Japanese Grammar).
O-U-FU-U. (in Japanese).