Local Graph Matching with Active Learning for
Recognizing Inference in Text at NTCIR-10
Tsuyoshi Okita
Dublin City University

tokita@computing.dcu.ie

ABSTRACTThis paper describes the textual entailment system developped at Dublin City University for participation in the
textual entailment task in NTCIR-10. Our system is a local graph matching-based system with active learning: we
explore reducing the unknown words and unknown namedentities, incorporating meaning in parentheses / rhetoricalexpressions / semantic roles, and employing text understanding technique using simple logic. We deploy an additional feature of language model from deep learning. Our
result was 80.49 for macro F1 score, 84.95 for precision forthe positive entailment, and 79.95 for recall for negative entailment.

Categories and Subject Descriptors
I.2.7 [Computation and Language]: natural language
processing—textual entailment

General Terms
Languages

Keywords
Textual Entailment, Text Understanding, Relation Extraction, Paraphrase
Team Name: DCUMT
Task: BC subtask

1. INTRODUCTION
This paper describes the textual entailment system developed at Dublin City University for participation in the textual entailment task in NTCIR-10 [40]. A textual entailment task addresses the variability of semantic expression
whether the same meaning can be expressed by or inferredfrom diﬀerent texts [13]. More formally, let us call a pairof text expressions T (”Text”) and H (“Hypothesis”) where
the entailing side is T and the entailed side is H. A textual
entailment task is to judge for a given pair (T,H) whether

T entails H or not: T entails H if a human reading T would
infer that H is most likely true. The variability of semantic expressions is a common theme in various applications
in NLP including Question Answering (QA), Information
Extraction (IE), summarization, and machine translation(MT). A textual entailment task typically involves a wide
range of NLP tools in the domain of semantics and various
approaches have appeared.
A graph matching approach [19] is a classical approach. Sentences are represented as normalized syntactic dependency
graphs and entailment is approximated with an alignment
between the graph representing the hypothesis and a portionof the corresponding graph(s) representing the text. Unfortunately, this approach is known to have three problems: (1)other material in the text will not aﬀect the validity of thematch since it assumes the upward monotonicity, (2) dropping a restrictive modifier does not preserve entailment ina negative context since the search is based on global features, and (3) it has the inherent problem that alignment
and entailment determination is confounding. MacCartney
et al. [23] instead employ typed dependency graphs, partial alignment between the typed dependency graphs representing the hypothesis and the text, and a decision ofentailment. Mirkin et al. [26] deploy the partial graphwhich they call a subsentential textual entailment. Bentivogli et al. [4] focus on coreference in the context of discourse. First, the topic is often among coreferent (In event
coreference resolution, event is often among the topic) and,hence, anaphoric NPs seem to be important which are related to the second subproblem in a coreference resolution
task consisting of three subproblems: named entity recognition, anaphoricity determination, and coreference element
detection [38]. Anaphoricity determination is to extract deterministic anaphoric NPs from the text in the case of English [2]. Second, the resolution of time / space references
are in itself necessary to determine whether T entails H.
Our approach is a graph matching-based approach similar
with Haghighi et al. [19], with the similar modification by
MacCartney et al. [23] or Mirkin et al. [26]. Especially, we
explore various preparation methods in its preprocessing inorder to augment the indispensable data for graph matching:hence, this is active learning. The characteristics of our system lies in these three. First, our system prepares indispensable additional data with preprocessing which reduces theunknown words and unknown named-entities, incorporates
meaning in parenthesis / rhetorical expressions / semantic

roles, and prepares the (simple) text understanding capability in graph matching. Second, in psychology and color
comparison [15], the comparison between two with a big difference tends to be avoided. This is called a principle of justnoticeable diﬀerence. Followed by this, our approach tries
not to compare T ′ and H in big diﬀerence. We tried to decide whether this T entails H or not within a single aspectwith very small diﬀerence. Third, the context-dependent
language model is developed in the context of deep learningwhich became popular recently [3, 37, 25]. This contextdependent language model is reported to be of less perplexity than the state-of-the-art language model. As is shown by
Collobert [11], this context-dependent language model facilitated the implementation of Semantic Role Labeller (SRL),
named-entity recognizer, and parser. As far as we know,
there have been no reports as this being applied to a textual
entailment task.
The remainder of this paper is organized as follows. Section 2 describes the overview of our systems. In Section 3,
we describe the linguistic and shallow preprocessing step for
preparing indispensable data for graph matching, while in
Section 4 we describe the determination step of graph matching. Our experimental results are presented in Section5. We
conclude in Section 5.

2. OVERVIEWS∑
where w(v) denotes the weight for node v, and Z (= v∈Hv w(v))
denotes a normalization constant. Similarly, let P athSub(e, ϕM (e))
be a model for assessing the cost of substituting a direct relation e for ϕM (e) under the matching. Relation cost isrepresented as in (4):1 ∑RelCost(M ) =w(e)P athSub(e, ϕM (e)) (4)
Z v∈H
v

∑
where w(e) denotes a edge cost, and Z (= v∈Hv w(e)) denotes a normalization constant. In sum, this model yields
T entails H when MatchCost(H, T ) is low, and otherwise T
does not entail H.

Our Model. Now in our model, we introduce the locality
to the graph matching algorithm. Let Tj be subgraph of T
and Hi be subgraph of H. For example, when T consistsof multiples of sentences, Tj may be a simple sentence. Let
Hi ≈ Tj denote that Hi is close enough to Tj . Avoiding
to assess the cost globally, we decompose Cost(H, T, M(i,j) )with a set of LocalCost(Hi , Tj , M(i,j) ) where each decomposed subgraph which includes a close pair of Hi and Tj
which satisfies Hi ≈ Tj . Hence, the modified version of the
MatchCost(H,T) can be written as in (6):MatchCost(H,T) =Cost(H, T, M(i,j) ) =(5)
min Cost(H, T, M(i,j) )∑LocalCost(Hi , Tj , M(i,j) )(6)M ∈M

Hi ≈Tj

Review of Graph Matching Model. As is similar with
Haghighi et al. [19], we represent text of T and H as agraph in the following way. First, T and H are represented as a dependency tree using the modified version ofCollins’ head propagation rules [10], i.e. main verbs areplaced at the head of sentences. Second, the dependency
nodes such as collocations and named-entities are collapsed.
Note that collocations include verbs and their adjacent particles. Third, certain dependencies such as modifying prepositions are folded. Fourth, the graph representation is augmented by Propbank-style semantic roles. Each predicate
adds an arc labeled with the appropriate semantic role tothe head of the argument phrase. Modifying phrases arelabeled with their semantic types.
The summary of the graph matching model introduced byHaghighi et al. [19] is as follows. Let H denote hypothesis
graph, T denote a text graph, M denote a mapping fromthe vertices of H to those of T , M (v) denote the match in
T for vertex v in H , and Cost(M ) be the cost of matching
M . When M is a set of matching, the cost of matching H
to T is defined as in (1):MatchCost(H,T) =min Cost(M )

M ∈M

(1)

where Cost(M ) is given by a convex mixture of the nodeand relational match costs as in (2):
Cost(M) =αNodeCost(M) + (1 − α)RelCost(M) (2)where NodeCost(M) denotes a node cost, and RelCost(M)denotes relational match cost. Let N odeSub(v, M (v)) be amodel for substituting node v for M (v). Then, node cost isrepresented as in (3):1 ∑w(v)N odeSub(v, M (v)) (3)NodeCost(M ) =Z v∈Hv

Note that this Hi ≈ Tj corresponds to the principle of thejust noticeable diﬀerence in psychology [15]. Although thisindicates that for given T and H it may not be possible tofind out such (a set of) Hi and a set of Tj . Other note is that
if Hi only refers a subset of T , it may not need to consider
other part of T . This means that we may not need to iterate
all of subset of T to compare Hi . This also means that wetreat this as if a set of Hi and Ti is almost mutual exclusive
and only a couple of pairs of Hi and Ti are active in practice.

Deep / Shallow Linguistic Preprocessing Step. As iswritten in Haghighi et al. [19], the node and edge substitution models uses some linguistic preprocessing such as PartOf-Speech (POS) tagger, Latent Semantic Analysis (LSA),
Wordnet, stemmer, and so forth. In our view, the information obtained by those linguistic preprocessing are fairly limited and basically passive processing. We extend this and actively prepare the presumably indispensable information to
calculate a correct MatchCost(H,T). In this reason, we callthis active learning. The elements of active learning is otherthan the conventional linguistic methods: parsing, morphological analysis, noun phrase extraction (and named-entity
extraction), and so forth. We do determination of unknown
noun phrases and unknown named-entities, rhetoric detection, relation extraction, text understanding, paraphrasing,time / space coreference resolution. Especially, text understanding is to actively examine the elements in text and infer
using a simple logic. We also training of context-dependent
language models.
Based on these preprocessing steps, T and H will have various semantic annotations with the representation as dependency graphs. One more processing is subject alignment
and transformation: first, the subject in H is aligned to thephrase Ts in the partial fragment in T . If Ts is not thesubject in the original T , T is transformed with Ts as the
subject. For example, suppose that we are given the following T and H:• T: 自激漏（じげきろう）は、1434 年に中世李氏朝鮮の科学者、蒋英実が作った水時計である。
• H: 蒋英実は中世李氏朝鮮の科学者である。
In this case, the subject alignment connects ‘蒋英実’ in H
with ‘蒋英実’ in T . Then, the transformation yields thegraph containing several subtrees. If we extract such subtrees, this becomes the following four subtrees in T .
• T1 : <person>蒋英実</person>は、<job>科学者</job>である。

• Dependency parser: KNP [21].
• Named-entity recognizer, NLTK [5], MALLET [24].
• Paraphrase generator [9]; ngram-Hidden Markov Model(HMM) language model [6]; bootstrap method (“X deploy Y”).
• Wordnet [7], Wiki, monolingual corpora, and parallel
corpora.
• Internet search engine: Google; Yahoo.
• Deep learning component: context-dependent recurrent neural network language model [25], ngram-HMM
language model [6];Unknown Words (OOV Words). In textual entailment task,

it is expected that unknown words or out-of-vocabulary words(OOV words) have negative eﬀects whatever the steps are.
When the system encounters unexpected POS sequences or
doubtful sequences, based on the heuristic to derive candi• T3 : <person>蒋英実</person>は、<time>1434 年</time>
date phrases based on the knowledge of case particles, ourに<object>水時計</object>を作った。
system searches the Internet resources and obtain the (rank
1 to rank 100) results. We use the heuristic that it is often• T4 : coordination [<phrase>自激漏</phrase>, <phrase>
possible to segment phrases by the knowledge of Japanese
じげきろう</phrase>]case particles and that of other segments which are more
• H: <person topic=’Y’>蒋英実</person>は<country>
certain. If the results include titles, it is often likely that
中世李氏朝鮮</country>の<job>科学者</job>である。
the candidate phrase is identified. We make a correction of
the phrase boundaries. (Upon recognizing a mistake, we runHence, the graph matching algorithm eventually calculates
again the morphological analyzer and parser with replacing
the cost mostly between H and T2 .
some easier candidates and later replace back.)• T2 : <person>蒋英実</person>は、<country>中世李氏朝鮮</country>の<job>科学者</job>である。

3. DEEP / SHALLOW LINGUISTIC PREPROCESSING STEP
The deep / shallow linguistic preprocessing step modifies
the original structures of H and T in order to provide Hi
and Tj which are subset of H and T with corresponding
features in the classification step. Using the equation (5)and (6), our algorithm makes the size of the source and thetarget sentences shrinked in order that we can compare theHi and Tj where Hi and Tj are close enough and whereother LocalCost(Hi ,Tj ,M(i,j) ) can be considered to be zero(although this is not always the case). In this process, thestructure of texts are actively investigated in two directions:(1) make T from complex / compound sentences into simple
sentences and (2) make the form of T simplified with considering the easier match with H. At the same time, the feature
extraction are actively proceeded in order to help the simplification of T . We call this mechanism as active learning since
the features used in the standard SVM are not modified but
are globally evaluated. Note that although it is often thecase that active learning let increase the training data, theactive learning here let decrease the substructure of training
data and let extract the features according to this dynamical substructure. The conversion of subjects relations (orsubject alignment) of Ti towards Hi is done in this process,as well as replacement of unknown words / named-entities,
text understanding and other linguistic preprocessing which
are enumerated in this chapter. In the experiments, we usedvarious deep / shallow linguistic preprocessing tools as well
as resources, which are shown below.
• Morphological analyzer: JUMAN [22].

Unknown Named Entities (Multi-Word Expressions). The
unknown named-entities of the proper nouns, such as person name, company names, and titles, may also considerably
decrease the overall performance of the system. We use thesimilar heuristic as unknown words to find a possibly correct named entities (Multi-Word Expressions). Note thatname can be written in various ways. For example, Leonald
Da Vinci is equivalent with “Da Vinci”, “Mr. Leonald Da
Vince”, “Leonald”, and so forth.

Parenthesis and Quotation. There are several diﬀerent
meanings of parenthesis and quotation. It is expected thatthe text within parenthesis are equivalent expression of theitems before the parenthesis. Such symbols include “『』”, “（）”, “「」”, “”’, ”“ “, and so forth. Sometimes the (syntactic) adjuncts are also better to be considered as one namedentity. For example, “第 8 回『このミステリーがすごい!』大賞”
can be considered as one entity rather than only considering“『このミステリーがすごい!』”.
• Equivalent expression:– 1993 年 (平成 5 年), 世界保健機関 (WHO)• Explanation:– ラフテー（東坡肉が元祖）• More specific / generic explanation:– 携帯の一般的な入力方法（トグル打ち・マルチタップ）• Explanation of attribute (birthday, organization, andso forth):– ロバート・エドワード・ターナー三世（1938 年 11
月 19 日 -）• Specification of segmentation:– 後に、『新世紀エヴァンゲリオン』における「Project
EVA」

Noisy Characters. The text between parentheses and quotes
may include noisy characters. For example, “第 8 回『このミステリーがすごい!』大賞” includes “!”. “略称”, “例：”, “「」”,
and so forth.
• “『』”, “!”, “-”.
– 第 8 回『このミステリーがすごい!』大賞• “略称”– 独立行政法人情報処理推進機構（じょうほうしょりす
いしんきこう、Information-technology Promotion
Agency Japan、略称「IPA」）

Hypergraph Representation of T . We identify the dependency structure of T and H by dependency parser. We formulate a hypergraph. For example, T can be decomposed
into several sentences {T1 , . . . , Tn }, which is shown in thefollowing example.
• T :せたまるは、Suica と同じく非接触式 IC カード通信技
術 FeliCa を採用しているが、カード端の切欠きはなく、IC チップ内のファイル構造も Suica とは一部異なる。
• T1 : せたまるは、Suica と同じく非接触式 IC カード通信
技術 FeliCa を採用している。
– T11 : (せたまるは、非接触式 IC カード通信技術 FeliCa を採用している。)– T12 : (Suica は、非接触式 IC カード通信技術 FeliCaを採用している。)• T2 : せたまるは、カード端の切欠きはない。
• T3 : せたまるは、IC チップ内のファイル構造も Suica とは一部異なる。
Note that T1 is further decomposed into T11 and T12 .

Subject Alignment. The subject can be freely modified according with H. In the following examples, the focus of H
is on ’ ナチス・ドイツ’ and its counter part ’ ポーランド’. T
is decomposed according to this information: that is, (1) ’ナチス・ドイツ’ は、’ ポーランド’ に侵略した, (2) ’ ナチス・ドイツ’ は、’ ポーランド’ をホロコーストの舞台とした, and (3)ナチス・ドイツとポーランドとの間では、共同研究が進んでいなかった.
• T:ナチス・ドイツが侵略し、ホロコーストの主な舞台になったポーランドとの間では、東西冷戦の影響で共同研究が進んでいなかった。
• H:ナチス・ドイツはポーランドに侵略した。

Coordination. At the same time when we derive a hypergraph, we obtained the relation of coordination if there is.
1. T ′ : 天才といえば古くはレオナルド・ダ・ヴィンチ、近代に入ってはエジソンとアインシュタインと決まっている。
2. coordination: レオナルド・ダ・ヴィンチ, エジソン, ア
インシュタインCoreference Resolution / Identification of Nonanaphoric
NPs. In coreference resolution, the non-anaphoric definite
NPs [2] are often given, but in our context they should be
identified in its preparation. This should be also true forrelative pronouns, reflexive pronouns, personal pronouns as
well. Note that since there is no article in Japanese we haveno distinction between whether definite NPs and nondefinite
NPs. We identify the nonanaphoric NPs.

Coreference Resolution of Space / Time References. We
employ the space and time coreference resolution to identify
the fluctuation of space and time expressions.

Text Understanding. A graph-matching-based textual entailment [19, 23] has limitation in that they will not detect
whether T requires to understand the content of H. Suppose that T =’Bob bought a red car from Mary and Tom.’and H=’Three persons are related to the conversation’. In
T , there is no number appeared, but human beings can readthis sentence and understand that there are three persons
in T . Slightly more diﬃcult example, such as follows, isappeared in development set.
• T:世界の地震の約１割が日本周辺で起きていて、マグニ
チュード８を超える巨大地震も２割近くが日本周辺で起きているという。
• H:マグニチュード８を超える巨大地震の約１割が日本周辺で起きている。
In this example, RTE system needs a simple calculation. ’ 日
本周辺の地震’ は約１割, ’ マグニチュード８を超える地震’ は２割. Hence, the superposition of ’ マグニチュード８を超える巨大地震’ and ’ 日本周辺の地震’ is 約 0.2 割 by subtracting ２割約１割. The system should have the capability of understandthe sentence and calculate in this way.
Note that our system only supports very simple operations
by first-order logic since it is very diﬃcult to simulate whole
the capability of human beings. We categorize (1) time description (“when”), (2) location description (“where”), (3)who description (“who”), (4) what description (“what” or“which”), (5) size description (“how” followed by an adjective), (6) number description (“how many”), and (7) why
description (“why”). Note that although there is no question sentence in corpus of textual entailment it would bepossible that we assume that a hypothesis sentences can be
categorize one of these which answers to the question which
is hidden behind the scene.

Text Understanding Time Inference. It is often that thetime description may need to deal with the time information
given in T. The following example needs to understand thata week after 31/May/2012 means 6/June/2012 and hence
2/June/2012 is before this date.

• T: The explosion was happened on 31/May/2012 andit made the airplane delayed for a week.
• H: The airplane on 2/June/2012 was not delayed.

is often that the title becomes rhetoric, such as in the case of“『Hey Hey おおきに毎度あり』”, in the sense that even if themeaning in the title matches with the surrounding meaning,
it does not mean that T entails H. The text within “『』”should be considered to be a diﬀerent layer of meaning.

Text Understanding Location Inference. Similarly, location description may need to deal with the location information given in T. In the following example, in order to judge
the entailment of this example, it is required to understandsimple location knowledge: ’Japan’ ⊆ ’World’.

• 『Hey Hey おおきに毎度あり』は，タイトルが表すように、歌詞は全編関西弁で描かれ、メロディ部分はほぼ台詞であったりという変わった作風である。ト・ト」（全軍
突撃せよ）及び「トラトラトラ」（奇襲ニ成功セリ）が淵
田中佐機から打電されたことで知られる。

• T: There are thousands of earthquake in the world.
• H: The number of earthquake in Japan is less thanthousands.
Slightly diﬀerent setting is in scene understanding. In thisexample, in order to judge the entailment of this example,
it is required to understand the location of each object inspace: hence, a dog is behind a big building, implicatingthat a dog is not visible from Tom.
• T: There is a big building in front of Tom and there isa dog behind the building.
• H: Tom cannot see a dog.

Text Understanding Number Inference. In the following,
it is required to count there are 3 persons appeared in a
sentence. In order to do this, it is required a function whichcounts how many person exist in a sentence.
• T: 天才といえば古くはレオナルド・ダ・ヴィンチ、近代に入ってはエジソンとアインシュタインと決まっている。

4.

DETERMINATION STEP

The determination step judges the similarity of the Ti and
Hi by the SVM classification [8, 12] where Ti and Hi are thepossible correspondent fragments. As is mentioned above,
the feature extraction for the SVM classification algorithm
are applied for the selected Hi and Tj . We used L1-loss
function with Radial Basis Function (RBF) kernel where C
and γ were determined by cross-validation. Major features
which we used in our system are described below.

Lexical Entailment / Hyponymy Relations / Antonymy
Relations / Location Relations / Adjective Gradation
Features. These features are the same as [14] and [23].
Note that depending on the deep / shallow linguistic preprocessing, hyponymy relations and antonymy relations areexchanged.

Modality / Polarity / Factivity Features. These features
capture the contexts which reverse or block monotonicity[23] where these are often marked by the presence or absence of linguistic markers. Modality feature capture modal
reasoning where possibility will not entail actuality. Factivity feature• coordination: レオナルド・ダ・ヴィンチ, エジソン, ア
インシュタイン

Adjunct Feature. This feature suggests the dropping orHypernym and Antonym. This example is an usual situ-

Quantifier Features. These features captures entailment

ation for many literature. In a word level, if there is some
diﬀerence in terms of the level of abstraction in two words,
i.e. 中高年 and 中高生, it is required to judge whether 中高
年 is a hypernym of 中高生 or these two does not have such
relationships. Such relationships in word can be judge using
lexical resources such as (Japanese) WordNet [7].

relations among sentences involving quantification [23].

Quantifier Detection. In English sentence, a quantifier,Parenthesis and Quotation Features. These features in-such as ’all’ and ’every’, needs to be examined in order tograsp the correct meaning. These are detected by the predefined vocabularies.

dicate the presence or absence of possible equivalent expressions. This enables the similarity matching with the expression among parenthesis and quotation.

adding of syntactic adjuncts moving from T to H [23].

Semantic Role Matching Feature. This feature indicates
whether the corresponding semantic role relations are equivalent or not. As with this feature, some pair of features are
preprocessed to give true or false beforehand.

Noisy Character / Rhetoric Feature. These features sug• 刑事訴訟では疑わしきは罰せずという推定無罪が原則であるため、保険金殺人の事件が殺人罪として有罪にならないこともある。

Rhetoric Detection. If the sentence includes rhetoric, suchas metaphor, prosopopoeia, and the idiomatic expression
such as the four-word Kanji (i.e. “温故知新” and “南船北馬”),
this may prevent the similarity-based matching approach. It

gest to drop the corresponding fragments from the similarity
matching.

Time / Date / Number Features. The presence of thesefeatures can be preprocessed by coreference resolution of
space / time references (or some localization software) which
will detect diﬀerent form of equivalent expressions. Thesefeatures are often preprocessed beforehand whether they aretrue of false.

Text Understanding Features. Classification can only capture the similar expressions between Ti and Hj . As is mentioned in Chapter 3, when Hj requests some capability oftext understanding of Ti , this feature would suggest somebasic inference results in the deep / shallow linguistic preprocessing. This enables a judge whether Ti can be entailed
Hj . Note that the capability of these features are limited intime, location, and number and in very basic case.

Content Length Feature. If H contains more information
than T , this can be immediately decided that T does notentail to H.
Deep Learning Language Model Feature. Context- dependent language model feature is derived by context-dependent
recurrent neural network language model [25] and ngramHMM language model [6].

Genre ID Feature. Genre ID feature is derived by Latent
Dirichlet Allocation (LDA) [24].

5. EXPERIMENTAL SETTINGS AND RESULTS
The statistics of development and test set for textual entail
BC task is shown in 5. The result by our approach is shownin Table 5. The Macro F1 score was 80.49. The precision
for yes entailment was high, while the recall for no entail
was high. As is indicated by the row of our submission, ourtextual entailment system gave output of ’yes’ with muchsmaller number than the correct answer, while it gave output
of ’no’ in larger number.

JA devset
JA testset
Our submission

MacroF1
Accuracy
Y-F1
Y-Prec
Y-Rec

Yes
240
256
206

DCUMT
80.49
81.64
75.76
84.95
68.36

No
371
354
404

Total
611
610
610

N-F1
N-Prec
N-Rec

85.22
79.95
91.24

6. CONCLUSION
We participated in textual entailment task for NTCIR-10.
Our system is a variant of graph matching-based systemwith additional capability of reducing the unknown words
and unknown named-entities, incorporating meaning in parentheses / rhetorical expressions / semantic roles, understanding of simple logic. We used an additional feature of language model from deep learning. Our result was 80.49 formacro F1 score, 84.95 for precision for the positive entailment, and 79.95 for recall for negative entailment. The reason for high precision for the positive entailment may be
due to the fact that we tried to determine the entailment
only when the distance between T ′ and H becomes small
depending on deep / shallow linguistic preprocessing anddetermination.
There are several avenues for further work. First, we applied
Japanese textual entailment. We would like to extend thisto English textual entailment as well as cross-lingual textual
entailment. Although the direct application would be theevaluation task in SMT, it is possible to apply this techniqueto SMT components such as word alignment task [27, 31, 30]
and decoding task [34, 35]. This would lead to the (deep)
semantically informed SMT. Second, we would like to use
the testset which has not much unknown words in orderto specify the eﬀect of deep learning architecture although
our usage is limited in paraphrasing which is similar to [28,29] which applied to system combination task [35]. Thisway of building SMT components is related to unsupervised
learning of sentence or language model [37]. This line ofresearch would lead to the (shallow) semantically informed
SMT [28, 32, 33].

7.

ACKNOWLEDGMENTS

We thank John Judge for proof-reading of Introduction.
This research is supported by the Science Foundation Ireland(Grant 07/CE/I1142) as part of the Centre for Next Generation Localisation (http://www.cngl.ie) at Dublin City
University. We would also like to thank the Irish Centre forHigh-End Computing.

8.

REFERENCES[1] M. J. Beal. Variational algorithms for approximate
bayesian inference. PhD Thesis at Gatsby
Computational Neuroscience Unit, University College
London, 2003.
[2] D. Bean and E. Riloﬀ. Unsupervised learning ofcontextual role knowledge for coreference resolution.
In Proceedings of the Annual Meeting of the North
American Chapter of the Association for
Computational Linguistics (HLT/NAACL 2004), 2004.
[3] Y. Bengio, R. Ducharme, and P. Vincent. A neuralprobabilistic language model. In Proceeding of theAdvances in Neural Information Processing Systems
13 (NIPS00) –MIT Press, 2001.
[4] L. Bentivogli, I. Dagan, H. T. Dang, D. Giampiccolo,
M. L. Leggio, and B. Magnini. Considering discourse
references in textual entailment annotation. 5thInternational Conference on Generative Approaches tothe Lexicon (GL 2009), 2009.
[5] S. Bird, E. Klein, and E. Loper. Natural language
processing with python— analyzing text with thenatural language toolkit. O’Reilly Media, 2009.
[6] P. Blunsom and T. Cohn. A hierarchical pitman-yor
process hmm for unsupervised part of speech
induction. In Proceedings of Annual Meeting of the
Association for Computational Linguistics (ACL-11),
2011.
[7] F. Bond, H. Isahara, S. Fujita, K. Uchimoto,T. Kuribayashi, and K. Kanzaki. Enhancing thejapanese wordnet. In Proceedings of the 7th Workshop
on Asian Language Resources (in conjunction with
ACL-IJCNLP 2009), 2009.
[8] B. E. Boser, I. M. Isabelle M. Guyon, and V. N.
Vapnik. A training algorithm for optimal marginclassifiers. In Proceedings of the 5th Annual ACM
Workshop on COLT, pages 144–152, 1992.
[9] C. Callison-Burch, D. Talbot, and M. Osborne.
Statistical machine translation with word- andsentence-aligned parallel corpora. In Proceedings of the42th Annual Meeting of the Association for
Computational Linguistics (ACL-04), pages 175–182,
2004.
[10] M. Collins. Head-driven statistical models for natural
language parsing. PhD Dissertation (University ofPennsylvania), 1999.
[11] R. Collobert and J. Weston. A unified architecture fornatural language processing: Deep neural networks
with multitask learning. International Conference on
Machine Learning, ICML, 2008.
[12] N. Cristianini and J. Showe-Taylor. Introduction to
support vector machines. Kyoritsu Publisher, 2005.
Translated by Tsuyoshi Okita.
[13] I. Dagan, O. Glickman, and B. Magnini. The pascal
recognising textual entailment challenge. In
Proceedings of the First PASCAL Recognizing Textual
Entailment Workshop, 2006.
[14] M.-C. de Marneﬀe, T. Grenager, B. MacCartney,
D. Cer, D. Ramage, C. Kiddon, and C. D. Manning.
Aligning semantic graphs for textual inference andmachine reading. AAAI Spring Symposium at
Stanford, 2006.
[15] D. A. Forsyth and J. Ponce. Computer vision.
Kyoritsu Publisher, 2007. Translated by Tsuyoshi
Okita.
[16] J. V. Gael, A. Vlachos, and Z. Ghahramani. The
infinite hmm for unsupervised pos tagging. The 2009
Conference on Empirical Methods on Natural
Language Processing (EMNLP 2009), 2009.
[17] Z. Ghahramani. An introduction to hidden markov
models and bayesian networks. International Journalof Pattern Recognition and Artificial Intelligence,15(1):9–42, 2001.
[18] S. Goldwater, T. L. Griﬃths, and M. Johnson.
Contextual dependencies in unsupervised word
segmentation. In Proceedings of Conference on
Computational Linguistics / Association for
Computational Linguistics (COLING-ACL06), pages
673–680, 2006.
[19] A. Haghighi, A. Ng, and C. D. Manning. Robust
textual inference via graph matching. In Proceedingsof the Empirical Methods in Natural Language
Processing (EMNLP 2005), 2005.
[20] R. Kneser and H. Ney. Improved backing-oﬀ forn-gram language modeling. In Proceedings of theIEEE International Conference on Acoustics, Speechand Signal Processing, pages 181–184, 1995.
[21] S. Kurohashi and M. Nagao. KN Parser : Japanese
Dependency/Case Structure Analyzer. In Proceedingsof The International Workshop on Sharable Natural
Language Resources, pages 48–55, 1994.
[22] S. Kurohashi, T. Nakamura, Y. Matsumoto, and
M. Nagao. Improvements of Japanese Morphological
Analyzer JUMAN. In Proceedings of The
International Workshop on Sharable Natural Language
Resources, pages 22–28, 1994.
[23] B. MacCartney, T. Grenager, M.-C. de Marneﬀe,
D. Cer, and C. D. Manning. Learning to recognize
features of valid textual entailments. Proceedings ofthe Human Language Technology Conference of theNorth American Chapter of the Association for
Computational Linguistics (HLT-NAACL 2006), 2008.

[24] A. K. McCallum. Mallet: A machine learning forlanguage toolkit. http://mallet.cs.umass.edu, 2002.
[25] T. Mikolov and G. Zweig. Context dependent
recurrent neural network language model.
MSR-TR-2012-92, 2012.
[26] S. Mirkin, I. Dagan, and E. Shnarch. Evaluating theinferential utility of lexical-semantic resources. In
Proceedings of Joint Conference of the 47th Annual
Meeting of the Association for Computational
Linguistics and the 4th International Joint Conference
on Natural Language Processing of the AsianFederation of Natural Language Processing(ACL-IJCNLP 2009) Student Research Workshop,
2009.
[27] T. Okita. Data cleaning for word alignment. In
Proceedings of Joint Conference of the 47th Annual
Meeting of the Association for Computational
Linguistics and the 4th International Joint Conference
on Natural Language Processing of the AsianFederation of Natural Language Processing(ACL-IJCNLP 2009) Student Research Workshop,
pages 72–80, 2009.
[28] T. Okita. Neural Probabilistic Language Model for
System Combination. In Proceedings of ML4HMT
Workshop, collocated with COLING 2012, 2012.
[29] T. Okita. Joint Space Neural Probabilistic Language
Model for Statistical Machine Translation. arXiv:
1301.3614, 2013.
[30] T. Okita, Y. Graham, and A. Way. Gap between
theory and practice: Noise sensitive word alignment inmachine translation. In Proceedings of the Workshop
on Applications of Pattern Analysis (WAPA2010).
Cumberland Lodge, Engl and., 2010.
[31] T. Okita, A. M. Guerra, Y. Graham, and A. Way.
Multi-Word Expression sensitive word alignment. In
Proceedings of the Fourth International Workshop On
Cross Lingual Information Access (CLIA2010, co
llocated with COLING2010), Beijing, China., pages
1–8, 2010.
[32] T. Okita, R. Rubino, and J. van Genabith.
Sentence-level quality estimation for MT system
combination. In Proceedings of ML4HMT Workshop,
collocated with COLING 2012, 2012.
[33] T. Okita, A. Toral, and J. van Genabith. Topic
modeling-based domain adaptation for system
combination. In Proceedings of ML4HMT Workshop,
collocated with COLING 2012, 2012.
[34] T. Okita and J. van Genabith. DCU Confusion
Network-based System Combination for ML4HMT.
Shared Task on Applying Machine Learning techniques
to optimising the division of labour in Hybrid MT(ML4HMT-2011, collocated with LIHMT-2011), 2011.
[35] T. Okita and J. van Genabith. Minimum Bayes Risk
Decoding with Enlarged Hypothesis Space in System
Combination. In Proceedings of 13th International
Conference on Intelligent Text Processing andComputational Linguistics (CICLING 2012), pages
40–51, 2012.
[36] L. R. Rabiner. A tutorial on hidden markov models
and selected applications in speech recognition.
Proceedings of the IEEE, 77(2):257–286, 1989.
[37] H. Schwenk and J.-L. Gauvain. Connectionist language

modeling for large vocabulary continuous speech
recognition. In International Conference on Acoustics
Speech and Signal Processing, pages 765–768, 2002.
[38] V. Stoyanov, N. Gilbert, C. Cardie, and E. Riloﬀ.
Conundrums in noun phrase coreference resolution:
Making sense of the state-of-the-art. In Proceedings of
the Joint Conference of the 47th Annual Meeting of the
Association for Computational Linguistics and the 4thInternational Joint Conference on Natural Language
Processing of the Asian Federation of Natural
Language Processing (ACL-IJCNLP 2009), 2011.
[39] Y. W. Teh. A hierarchical bayesian language model
based on pitman-yor processes. In Proceedings of the44th Annual Meeting of the Association for
Computational Linguistics (ACL-06), Prague, Czech
Republic, pages 985–992, 2006.
[40] Y. Watanabe, Y. Miyao, J. Mizuno, T. Shibata,H. Kanayama, C.-W. Lee, C.-J. Lin, S. Shi,
T. Mitamura, N. Kando, H. Shima, and K. Takeda.
Overview of the Recognizing Inference in Text
(RITE-2) at NTCIR-10. Proceedings of the 10th
NTCIR Conference, 2013.

Appendix: Ngram-HMM Language Model
Generative model. Figure 1 depicted an example of ngramHMM language model [6] in blue (in the center): Hidden
Markov Model (HMM) [36, 17, 1] of size K emits n-gramword sequence wi , . . . , wi−K+1 where hi , . . . , hi−K+1 denotecorresponding hidden states, while the arcs from wi−3 to wi ,· · · , wi−1 to wi show the backoﬀ relations appeared in language model smoothing, such as Kneser-Ney smoothing [20]and hierarchical Pitman-Yor LM smoothing [39].
γ

β

G0

α

πk

G0

H

θ0

ϕ

Gu
u=1,...,K

k=1,...,T

d0
θu
du

Figure 1: Figure shows the 4-gram HMM language
model and generative model.
In the left side in Figure 1, we place one Dirichlet Process
prior DP(α, H), with concentration parameter α and basemeasure H, for the transition probabilities going out fromeach hidden state. This construction is borrowed from theinfinite HMM [1, 16]. The observation likelihood for thehidden word ht are parameterized as in wt |ht ∼ F (ϕst ) since
the hidden variables of HMM is limited in its representation
power. This is since the observations can be regarded as
being generated from a dynamic mixture model [16] as in (7),the Dirichlet priors on the rows have a shared parameter.
p(wi |hi−1 = k) =K∑p(hi |hi−1 = k)p(wi |hi )

hi =1

=

K
∑
hi =1

πk,hi p(wi |ϕhi )(7)

In the right side in Figure 1, we place Pitman-Yor prior PY:
wi |w1:i−1∼ PY(di , θi , Gi )(8)

where α is a concentration parameter, θ is a strength parameter, and Gi is a base measure. This construction isborrowed from hierarchical Pitman-Yor language model [39].

Inference. We compute the expected value of the posterior distribution of the hidden variables with a beam search[16]. This blocked Gibbs sampler samples the parameters(transition matrix, output parameters), the state sequence,
hyper-parameters, and the parameters related to language
model smoothing, turn in turn. As is mentioned in [16], thissampler has characteristic in that it adaptively truncates thestate space and run dynamic programming as in (9):p(ht |w1:t , u1:t ) = p(wt |ht )∑p(ht−1 |w1:t−1 , u1:t−1 )ht−1 :ut <π(9)(ht−1 ,ht )where ut is only valid if this is smaller than the transition probabilities of the hidden word sequence h1 , . . . , hK .
Note that we use an auxiliary variable ui which samples
for each word in the sequence from the distribution ui ∼Uniform(0, π (hi−1 ,hi ) ). The implementation of the beam
sampler consists of preprocessing the transition matrix π
and sorting its elements in descending order.

Initialization. First, we obtain the parameters for hierarchical Pitman-Yor process-based language model [39, 18].
Second, in order to obtain a better initialization value h forthe above inference, we perform the following EM algorithm
instead of giving the distribution of h randomly. This EM
algorithm incorporates the above mentioned truncation [16].
expected value of the posterior distribution of the hidden
variables. For every position hi , we send a forward messageα(hi−n+1:i−1 ) in a single path from the start to the end of
the chain (which is the standard forward recursion in HMM).
Here we normalize the sum of α considering the truncatedvariables ui−n+1:i−1 .
∑∑α(hi−n+1:i−1 )α(hi−n+2:i ) = ∑P (wi |hi )α(ui−n+1:i−1 )α(ui−n+1:i−1 )P (hi |hi−n+1:i−1 )Then, for every position hj , we send a message β(hi−n+2:i , hj )in multiple paths from the start to the end of the chain as
in (10),∑α(hi−n+1:i−1 )β(hi−n+2:i , hj ) = ∑P (wi |hi )α(ui−n+1:i−1 )∑β(hi−n+1:i−1 , hj )P (hi |hi−n+1:i−1 )This step aims at obtaining the expected value of the posterior distribution. In the M-step, using this expected valueof the posterior distribution obtained in the E-step to evaluate the expectation of the logarithm of the complete-data
likelihood.