Natural Language Generation Using Monte Carlo Tree Search

Paper:Natural Language Generation Using Monte Carlo Tree Search
Kaori Kumagai∗1 , Ichiro Kobayashi∗1, Daichi Mochihashi∗2 , Hideki Asoh∗3 ,Tomoaki Nakamura∗4 , and Takayuki Nagai∗4∗1 Advanced Sciences, Graduate School of Humanities and Sciences, Ochanomizu University

2-1-1 Ohtsuka, Bunkyo-ku, Tokyo 112-8610, Japan
E-mail: kumagai.kaori@is.ocha.ac.jp∗2 The Institute of Statistical Mathematics
10-3 Midori-cho, Tachikawa city, Tokyo 190-0014, Japan
E-mail: daichi@ism.ac.jp∗3 National Institute of Advanced Industrial Science and Technology (AIST)
1-1-1 Umezono, Tsukuba, Ibaraki 305-8560, Japan
E-mail: h.asoh@aist.go.jp∗4 The University of Electro-Communications
1-5-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan
E-mail: {tnakamura, tnagai}@ee.uec.ac.jp[Received March 17, 2018; accepted July 31, 2018]

We propose a method of simulation-based natural language generation that accounts for both building a correct syntactic structure and reflecting the given situational information as input for the generated sentence. We employ the Monte Carlo tree search forthis nontrivial search problem in simulation, using
context-free grammar rules as search operators. We
evaluated numerous generation results from two aspects: the appropriateness of sentence contents for the
given input information and the sequence of words ina generated sentence. Furthermore, in order to realize an efficient search in simulation, we introduced
procedures to unfold syntactic structures from words
strongly related to the given situational information,and increased the probability of selecting those related
words. Through a numbers of experiments, we confirmed that our method can effectively generate a sentence with various words and phrasings.

Keywords: natural language generation, Monte Carlotree search, syntactic tree, context-free grammar

1. Introduction
People subconsciously produce utterances in daily life
according to different situations. When a person encounters a situation in which a dog eats a piece of bread, heor she retrieves appropriate words and creates a naturalsentence, retaining the dependent relationships among thewords in proper order, to describe the situation. In addition, the words and phrases used in the descriptions arediverse. For example, when a person describes “a dog,”
it is sometimes called “a puppy,” or “a big dog.” Thisability of natural language generation (NLG) in such situVol.22 No.5, 2018ations will become essential for robots and conversational
agents in the future.
However, this problem is intrinsically difficult because
it is difficult to encode what to say into a sentence while
ensuring its syntactic correctness and the possibility of avariety of words and phrases. In previous work [1], we
proposed using Monte Carlo tree search (MCTS) [2, 3], astochastic search algorithm for decision processes, to findan optimal solution in the decision space. Upon receiving the situational input, we built a search tree of possible
syntactic trees to generate a sentence by selecting proper
rules through numerous random simulations of possible
outputs. We confirmed that our method could generate
sentences with various words and phrasings while ensuring their syntactic correctness.
However, there was room for improvement. In thisstudy, in order to realize more accurate and efficient sentence generation, we have improved three aspects. One
is an improvement in feasible search in MCTS. To evaluate a generated sentence, in addition to evaluation of then-gram language model, we adopt evaluation of the content of a sentence. The second improvement is to achieving efficient search. This is achieved through two steps:
one is changing the search policy in MCTS. In our priorstudy, we used the left-most derivation to unfold a syntactic structure; however, in this study, we unfold the mostimportant part in a sentence, i.e., the predicate. The second step is changing the sampling method: we set theprobabilistic distribution considering the situational input
and the n-gram language model. The third improvement
is preparing lexicons considering their semantic characteristics, i.e., the semantics of given words as situational
input. In concrete terms, in [1], the lexicons used in a generated sentence had to be prepared manually in advance,
whereas we obtain lexicons whose meanings are similar
to the lexicon of the situational input based on distributed

Journal of Advanced Computational Intelligenceand Intelligent Informatics

777

Kumagai, K. et al.

semantics. In addition, words that co-occur are obtainedby a topic model.
The paper is organized as follows. Section 2 describes
our work with respect to the existing work. Section 3
presents the basic algorithm for sentence generation using MCTS. In Section 4, we introduce how to evaluate
generated sentences for feasible search (Section 4.1), andthen we explain setting the upper confidence bounds one(UCB1)-value for MCTS to converge all these evaluation
values (Section 4.2). Section 5 describes the two means
for achieving efficient search, and in Section 6, we explain how to prepare the lexical resources. In Section 7,
we conduct the experiment, and finally, we draw conclusions in Section 8.

2. Related Studies
As for the nondeterministic approach to NLG, somestudies view NLG as a planning problem. As an example of planning, there is a method called pipe-line generation [4], in which the contents to be generated are first
decided by considering what the generated sentence expresses, and then the contents are translated into natural
language, which corresponds to surface realization. To
replace pipeline generation, there are methods that simultaneously plan the contents of a generated sentence andtranslate it to natural language expressions. CRISP [5]and PCRISP [6] have adopted this approach.
As another way to handle the indeterminate characteristics of NLG, Lemon [7, 8] and Rieser [9] modeled dialog
as Markov decision processes (MDPs) and solved themby means of reinforcement learning [10].
Similar to our approach, STRUCT [11] and SSTRUCT [12] considered the NLG process as an MDP
with a suitably defined reward function to achieve efficient sentence generation using an MCTS algorithm.
However, these methods aim to generate a target sentencewith a constraint on input information in terms of semantics, so we cannot expect that a variety of sentences could
be generated by these methods. Contrary to these methods, our proposed method is able to generate a variety ofsentences.
Another nondeterministic approach uses a neural language model [13], Wen et al. [14–16] used a Long ShortTerm Memory generator, which can learn from unaligned
data by concurrently optimizing sentence planning andsurface realization using a simple cross-entropy training
criterion, and easily achieves language variation by sampling from output candidates. However, this method predicts a word sequence only, and does not consider syntactic structures.
As another search-based algorithm that considers syntactic structures in generating a sentence, Liu et al. [17]proposed a syntactic linearization of given words using beam-search for an appropriate structure for a sentence. However, it treats the word order problem of generating sentences using only given words. Technically,
their method employs a beam search with a predefined778

beamwidth. On the other hand, MCTS realizes an efficient search that does not restrict the search range in advance.
Moreover, Silver et al. [18] developed AlphaGo, which
defeated a top-level professional Go player. They combined MCTS with a deep reinforcement learning framework, and provided MCTS with learning ability; both thepolicy and value networks of the system are trained to
predict human expert behaviors using deep reinforcement
learning. This framework could be applied to NLG in the
future.

3. NLG with MCTS Simulations
3.1. MCTS
MCTS combines random simulation and best-firstsearch in its search process [2]. It has been successfully
applied as an algorithm for playing the Go game and similar planning problems. In fact, both the Go game and
NLG share the same characteristic: their outputs can beevaluated only when the process reaches the last state.
Therefore, we expect that the process of NLG can be represented in MCTS simulations.
MCTS uses the UCB1 value to determine the next
move from the viewpoint of the multi-armed bandit problem [19].

2 logNUCB1 = vi +C. . . . . . . . . (1)niHere, vi is the winning rate of candidate i, C is an adjustment coefficient, N is the total number of simulations, andni is the number of visits to the candidate i. The first termof Eq. (1) corresponds to exploitation and the second term
corresponds to exploration within the simulation, achieving a balanced search between the two factors [20].
3.2. Algorithm
Our MCTS provides opportunities for selecting various
syntactic structures and words for a generated sentence.
We use probabilistic context-free grammar (PCFG) rules
obtained from the Penn Tree Bank [21] as a search operator in MCTS.
The MCTS algorithm is shown in Fig. 1.
Essentially, our MCTS builds a search space of possible derivations, and starting from the initial symbol S,
we iteratively determine what rule to apply to extend thecurrent tree, by simulating numerous possible derivations
from the candidate rules.
In addition, as the content to press, we input situational
information corresponding to the lexical information ofsubject, predicate, and object (SVO).

4. Method for Feasible Search
Unlike win or lose in the Go game, it is difficult for amachine to evaluate generated sentences in a binary state.

Journal of Advanced Computational Intelligenceand Intelligent Informatics

Vol.22 No.5, 2018

Natural Language Generation Using Monte Carlo Tree Search    "#"#"% !( ( & !# !, #"6-% 2$(.#('(" /* (,$+-, #"5)2'"" # ,!" "!'-!!!"" ")      →    0!"1*$#, #"4)2-(!'"" # " "!!") ""! ', #"5)1-(%! ")               " " "3(!'"" #! ! "!" "'!" #"!, #"5)2-#"!'!" !'!)

0! 



!%

"

 

!"! ! "!", #"4)1-(% ! ! !#, #"4)2-)
 !#"!" w ! !   "# ""!"" ""% "!1*$# #")
"  "# !#"!  "2" "5$ #("%!!"$!"!"&" ") "" "# !" "2)

Fig. 1. MCTS algorithm for NLG.

In order to realize a feasible search, it is necessary to set
up an appropriate evaluation for a generated sentence. In
this section, we describe how to set evaluation values fora sentence, and how to set UCB1-values to converge allof these evaluation values.

4.1. Evaluation Values for Generated Sentences
We explain the score of the generated sentence described in step 5 in Fig. 1. As the score of a generated
sentence for a feasible search, we adopt evaluation values
from two perspectives: one is the correctness of the sequence of words, and the other is the appropriateness ofthe contents of a sentence. The details of the evaluation
values are as follows:
1. Appropriateness of sentence contents
We used distributed representations by Word2vec for
situational input words, and the words used as SVO
in a generated sentence, and used their cosine similarities as evaluation values.
2. Correctness of the sequence of words
We used evaluation values based on the n-gram language model. Moreover, we used one of the following two types and compared the tendency of thewords that appeared in the generated sentences.
• Perplexity (hereinafter, PP)

We use the perplexity of tri-grams with KneserNey smoothing [22].
Vol.22 No.5, 2018

• Acceptability (hereinafter, AP)

We use a score called Acceptability proposedin [23], which measures the acceptability of a sentence for an English native speaker. In this study,
we use Acceptability as defined by Eq. (2) for asentence s:1
pmodel (s) |s|
Acceptability(s) = log(2)puni (s)As an n-gram language model pmodel (s), we use
trigrams with Kneser-Ney smoothing [22], where
puni (s) denotes the probability with a unigram distribution.

4.2. UCB1-Value and Judgement of Winning
We explain how to judge winning or losing at step 4 inFig. 1. In order to converge all of the evaluation values
mentioned in Section 4.1, the UCB1-value in this study isdefined according to the following Eq. (3).

2 logN
cond.
S
VO
PPorAPvi+ vi + vi + vi + vi
+C
. (3)
ni
Here, because the expected values of the sum of the winning rates is [0, 5], we set C to 5 to maintain balance between exploitation and exploration in the simulation. We
PPorAP in the following.
explain vcond.
, vSi , vVi , vOii , and vi• vcond.
i

First, we set the minimum conditions of a sentence
so that the generated sentence should have SVO, andJournal of Advanced Computational Intelligenceand Intelligent Informatics

779

Kumagai, K. et al.

satisfies the constraints on sentence length. Whenthese conditions are satisfied, this state is regarded asa win. Then, 1 point is returned in the calculation of
the winning rate. On the other hand, when the conditions are not satisfied, this state is regarded as a loss,
then 0 is returned. The reason for setting the minimum conditions is explained in the following. In theinitial search, we observed many sentences without
SVO. Furthermore, there was difficulty in creatinga difference in the UCB-1 value between candidate
nodes, which slowed the convergence of the search.
To accelerate the convergence of search at the initialstage, it was necessary to provide rewards when theminimum conditions for generating a sentence weresatisfied.
V O• vS
i , vi , vi
These are the winning rates based on cosine similarity, which are regarded as evaluation values for theappropriateness of sentence contents mentioned previously. Only when the minimum conditions mentioned above are satisfied do we calculate the cosine
similarities of S, V, and O. When those values arelarger than their averages at other candidate nodes, awin (1 point) is returned, and otherwise 0 is returned.
AP• vPPi or vi
This is the winning rate using AP or PP, and is regarded as an evaluation value for the correctness ofthe sequence of words mentioned previously. Only
when vSi , vVi , and vO
i win do we calculate either PP
or AP. Moreover, when the value is larger than PP or
AP averages at other candidate nodes, 1 is returned
as a winning point, and otherwise 0 is returned.

5. Method for Efficient Search
In this section, we explain two approaches for efficient
search.

5.1. Search Policy and SVO Judgment
In the previous work [1], we used left-most derivationin the formation of a syntactic tree. In this case, a word
is selected depending on the confirmed left-most word.
For example, if the left-most word is the article “a,” theword to the right of “a” has to be selected considering
the connection with “a.” In this paper, a syntactic tree isbuilt from elements strongly related to situational input.
Considering this, a syntactic tree is built in the following order: verb, noun, either adjective or adverb, and stop
words. The reason for building from a verb first is thatthe predicate is related to the lexical selection of both thesubject and the object. Here, because SVO is not directly
judged by the syntactic tree built by PCFG, a syntactic
tree is built in the following order, and then SVO is determined.
1. Unfold the part-of-speech (POS) related to verb
The terminal symbol initially unfolded is regarded as
the predicate of a generated sentence.
780

2. From the left side of predicate, unfold the POS related to noun
The terminal symbol initially unfolded is regarded as
the subject of a generated sentence.
3. From the right side of predicate, unfold the POS related to noun
The terminal symbol initially unfolded is regarded as
the object of a generated sentence.
4. Unfold the POS related to either adjective or adverb.
5. Unfold the other POSs.
In 1, 2, and 3 above, the reason why the initially unfolded
terminals should be SVO is because there is a high possibility that the words located in the shallow part of a syntactic tree become important components in a sentence.

5.2. Setting Probabilistic Distribution for Sampling
TargetIn the simulation (step 3 in Fig. 1), in the previous
work [1], we sampled the grammar rules from a uniform
distribution. In this case, for example, even if “eat” isgiven as the predicate of the situational input, “eat” and“run” are selected with the same probability. In orderto achieve an efficient simulation, we set probability distributions for sampling grammar rules, considering situational input, connection with surrounding words, andPCFG probabilities. Specifically, we set probability distributions by choosing nonterminal symbols, SVO, independent words not including the words for SVO, and stopwords. The details are shown below.
• Nonterminal symbols

We use the probabilities from PCFG.
• SVO
In order to increase the probability of selecting words
whose meanings are similar to the words in the situational input, we use distributed representations by
Word2vec and adapt the cosine similarity to each situational input word. The normalization method forcosine similarity is shown in Eq. (4).
exp(β r)∑(exp(β r)). . . . . . . . . . . (4)Here, r is cosine similarity, and β = 2.0.
• Independent words not including SVO

In order to increase the probability of selecting words
that are likely to co-occur with situational input
words, we obtain the word distributions p(v|W ),where W indicates situational input words, e.g.,{dog, eat, bread}. We use latent Dirichlet allocation (hereinafter, called LDA) [24]. First, we find the
topic distribution θnew on the new document W using
the pre-trained LDA model – let this be p(θnew |W ).
Second, using the word distribution for each topic φ ,we obtain p(v|θnew ) from Eq. (5). Finally, p(v|W ) is
obtained from Eq. (6).
p(v|θnew ) = ∑ φk,v θnew,k . . . . . . . (5)Journal of Advanced Computational Intelligenceand Intelligent Informaticsk

Vol.22 No.5, 2018

Natural Language Generation Using Monte Carlo Tree Search
• SVO

S
VP

NP

DT

JJ

the

cute

NN

    

VBZ
JJ

puppy has big






NP 

NNS
breads

7. Experiment

 

 

   

  
   
!     !      # " $  

Fig. 2. Overview of setting of probabilistic distribution.

p(v|W) =

Delete the lexicons whose cosine similarity is lessthan 0.3.
• Independent words other than SVO
In each part-of-speech, delete the lexicons except
the ones in the top 20 based on the conditional
probability p(v|W) mentioned in Section 5.2.

p(v|θnew )p(θnew |W )d θnew. (6)• Stopwords

Considering the connectivity of the words before andafter, we obtain the bigram and backward bigram
probabilities and use their average value.
An image of the above explanation for this method ofchoosing words is shown in Fig. 2.

6. Lexical Resources
In the case of using MCTS to generate a sentence, if
there are quite a few lexical elements collected from thecorpus, it enlarges the search space for the algorithm.
This becomes a considerable problem if a large numberof simulations are required. In order to solve this problem, it is necessary to pare down lexical resources appropriately based on the situational input. In the previous work [1], when we narrowed down lexicons that welikely to co-occur with the situational input, we collected
lexical resources by collecting two words before and after each word of situational input from the corpus. Thismethod has to be done manually before the MCTS simulation. In any case, the situational input words cannot
all be considered simultaneously. That is, in the case thatsituational input words are “dog,” “eat,” and “bread,” thelexical resources become the combination of words likely
to co-occur with “dog,” “eat,” and “bread.” In this paper,
considering the collection of lexicons that are likely to cooccur simultaneously with all the words of situational input, we adopt a probability distribution of words obtainedby a topic model. The concrete procedure of narrowing
down lexicons is shown below.
1. Delete the lexicons whose number of occurrences in
the corpus is less than 5.
2. Consider the distribution we have set in Section 5.2.

7.1. Experimental Settings
As for the corpus for LDA, we used all 85,413 sentences in the Microsoft Research Video Description Corpus (MVDC).1 We also used Wikipedia English Corpus2
to make Word2vec distributed semantics and n-grams.
As for making PCFG, we used the corpus 0000–0009
of WST100 in Penn TreeBank [21], and made 717 syntactic rules from the corpus. As for lexicons, we used
4, 464 words that appear more than 5 times in MVDC. As
the situational input to generate the contents of a sentence,
we evaluated three kinds of situational input as shown below.
W = {dog, eat, bread}, {boy, play, soccer}{man, write, letter}
We conducted experiments with two sets of constraints
on the length of a generated sentence as it becomes three
to five or six to eight words in length. The number ofsimulations is set to 100 for the number of the candidate
nodes.

7.2. Results and Discussion
The result of sentence generation is shown in Table 1.
As shown in Table 1, various expressions of a sentence
are generated under the same conditions. As for SVO, we
confirmed that proper words were selected for those categories. As we can see, there is a case where read was selected when write was provided for V, we have confirmedthat there is a case where various words with large cosine
similarity in the embedding space by Word2vec were selected. We also confirmed that various independent words
such as nouns, adjuncts, and verbs appeared when using
AP rather than PP.
Next, we analyze the evaluation values of the sentencesamong searching. Fig. 3 shows the transitions in the ratio of satisfying the minimum conditions of a sentenceeach time the root node is updated with an example ofgenerating a sentence with the situational input {dog, eat,bread} in MCTS simulation. We found that this probability converges to 1 as the search progresses. That is, at the
beginning of the search it is difficult to satisfy the minimum conditions. On the other hand, in the latter half ofthe search, the conditions are satisfied in most cases.
Figure 4 shows the transitions of the average and variance for each evaluation value for each time the root node
1. https://www.microsoft.com/en-us/download/details.aspx?id=52422
2. http://dumps.wikimedia.org/enwiki/

Vol.22 No.5, 2018

Journal of Advanced Computational Intelligenceand Intelligent Informatics

781

Kumagai, K. et al.

Table 1. Examples of generated sentence.
W{dog, eat, bread}

Len.
3∼5

6∼8

{boy, play, basketball}

3∼5

6∼8

{man, write, letter}

3∼5

6∼8

AP
· another dog eaten smallest breads· another dog ate connecticut breads· another dog eats smallest breads· another dog eating smallest breads· dogs eaten bread connecticut· either dog ate underneath jeff connecticut breads· another dog eaten automatically recumbent
breads automatically· every dog eat underneath another outstretchedbread breads· another dog eats automatically recumbent breads· another dog eats automatically battering breads· another boy play overweight soccer· another boy play eight soccer· boys play another soccer ’s· another boy played overweight soccer· another boy play eight soccer· another boy play underneath soccer vaccination· half boy play underneath soccer connecticut· these boy play underneath soccer vaccination· another boy play recumbent soccer horizontally
fistfighting soccer· the boy play underneath soccer vaccination
proffestionals· man learn letter vaccination· another man read letter· overweight men read letter· men wrote letter vaccination· man wrote another smallest letter· that man wrote underneath letter connecticut· another man read together letter connecticut· another man read together letter vaccination letters binoculars· overweight men read another overweight letter· another man read together letter connecticut

is updated in the MCTS simulation in the above example.
From this figure, we can see the variances of all evaluation values converge to low values. Although there are no
big changes, the averages are slightly higher at the end of
the search than at the beginning. In other words, it means
the search progressed so that all the values converged athigh values.
Next, in comparison with the previous work [1], we
consider the effects obtained by the three improvements.
First, as for the effect of the method for feasible search,
because the generated sentence is evaluated for the meaning of the words for SVO, words that are similar to situational input words are used for SVO in the sentence.
Therefore, it is possible to generate sentences considering
the syntactic categories of situational input words. For example, in the previous work [1], there is a possibility thata word corresponding to the situational input may not be
assigned to the position of SVO. In fact, when the situational input words are {boy, play, basketball}, the sentence “boys tennis was played to all the” was generated.
On the contrary, in the current method, we confirmed thatwords corresponding to situational input words were assigned to the position of SVO of the generated sentence.
Second, we explain the effect obtained by the method for782

PP· both dog eats quick bread· both dog gather bread washington· dog eating eight bread· dog ate 1 bread· the dog eaten either breads· both dog ate with the breads and passengers· both dog eat on combining breads· a dog eat with italian quick breads poles· the dog eaten bread ’ aggressively· an dog eat lighter breads overboard· refreshing boys played soccer· the boy play an soccer· powerful boys played soccer· every boy play five soccer· the boy play their soccer· any boy play for any soccer· every boy play till olympic soccer· a boy play between olympic soccer· the boy play soccer episode ritually· any boy play for its soccer· an man learn 10 letter· these man read letter washington· men read both italian letter· man learn your letter· these woman wrote letter washington· the man read in no smallest letter· the man read open letter episode· the man read together italian letter· the man read in both letter ’· the man read in an lower letter



 
 



    







                   

Fig. 3. Ratio of satisfying the minimum conditions (sentence of length 6 to 8 words, and having SVO).

efficient search. In the generation process, we consider
syntactic categories, i.e., SVO, in the unfolding order ofa syntactic tree, as well as the probabilistic distribution ofsyntactic rules, therefore, syntax errors are reduced. For
example, in the above example sentence “boys tennis wasplayed to all the,” not only is the content of the sentence

Journal of Advanced Computational Intelligenceand Intelligent Informatics

Vol.22 No.5, 2018

Natural Language Generation Using Monte Carlo Tree Search






















         








               





















                        

                  

Fig. 4. Transitions of average and variance for each evaluation value.

wrong, but errors in syntactic structure can also be seen.
Third, we describe the effects of changing the method ofparing down lexical resources. In the previous work [1],we collected words appearing with the words given as situational input words. In contrast, in this method, because
we selected words that were likely to co-occur with all situational input words by means of a topic model, we could
narrow down words efficiently. Specifically, when {dog,eat, bread} were received as situational input words, inthe previous work [1], there were 20798 words. On theother hand, there were only 215 words by this method.
Next, we will refer to the grammatical errors seen in
the generated sentences. The purpose is to generate sentences with correct syntactic structures and a variety ofwords and phrasings, so we did not consider grammatical information such as verbs and noun deformations. For
this reason, grammatical errors such as transformation ofverbs by tense and change of inflection of single and plural nouns are seen in the generated sentences. On the other
hand, because the methods use neural networks, whichhave often been referred to in recent years as a sentence
generation method, use language models that are learned
from a large amount of data, they can cope with the deformation of verbs and noun statistically. However, because
words are selected based on statistical information, themodel is influenced by frequent words in the training data.
Thus, it is difficult to generate a variety of sentences, andthe methods using neural networks can not achieve our
purpose.
Finally, we describe the problem in this experiment.
We observed the generation of sentences that were semantically difficult to understand. This may be the reason why
we did not provide any information about the words except the words for SVO. We think that the evaluation fora generated sentence is still insufficient to some extent.

Vol.22 No.5, 2018

8. Conclusion
In this study, we proposed a robust method to generate sentences with various phrasing for the same meaning, using MCTS and applying PCFG syntactic rules as
search operators. To effectively achieve MCTS, we devised the settings for search, the way of selecting words,
the evaluation metric for generated sentences, the lexical
resources, UCB1 value, etc. In the experiments, we confirmed that various sentences were generated by following
the input information, however, there were cases whereuninterpretable sentences were generated. In the future,
we will revise the evaluation metric for generated sentences and then generate more understandable sentences.
Acknowledgements
Part of this study was financially supported by KAKENHI (15K12104).

References:[1] K. Kumagai, I. Kobayashi, D. Mochihashi, H. Asoh, T. Nakamura,and T. Nagai, “Human-like Natural Language Generation Using
Monte Carlo Tree Search,” Proc. of the INLG 2016 Workshop on
Computational Creativity in Natural Language Generation, pp. 1118, 2016.
[2] L. Kocsis and C. Szepesvari, “Bandit based Monte Carlo planning,”
ECML 2006, pp. 282-293, 2006.
[3] C. Browne, E. Powley, D. Whitehouse, S. Lucas, P. I. Cowling,
P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton,“Survey of Monte Carlo Tree Search Methods,” Technical Report 1,
2012.
[4] E. Reiter and R. Dale, “Building applied natural language generation systems,” Nat. Lang. Eng., Vol.3, No.1, pp. 57-87, 1997.
[5] A. Koller and M. Stone, “Sentence generation as a planning problem,” Int. Natural Language Generation Workshop, Vol.12, pp. 1724, 2007.
[6] D. Bauer and A. Koller, “Sentence generation as planning withprobabilistic LTAG,” Proc. of the 10th Int. Workshop on Tree Adjoining Grammar and Related Formalisms, 2010.
[7] O. Lemon, “Adaptive natural language generation in dialogue using
reinforcement learning,” Workshop on the Semantics and Pragmatics of Dialogue (SEMDIAL), pp. 141-148, 2008.

Journal of Advanced Computational Intelligenceand Intelligent Informatics

783

Kumagai, K. et al.

[8] O. Lemon, “Learning what to say and how to say it: joint optimization of spoken dialogue management and natural language generation,” Computer Speech and Language, Vol.25, No.2, pp. 210-221,
2011.
[9] V. Rieser and O. Lemon, “Natural Language Generation as Planningunder Uncertainty for Spoken Dialogue Systems,” EACL 2009,
pp. 683-691, 2009.
[10] R. S. Sutton and A. G. Barto, “Reinforcement Learning: An Introduction,” MIT Press, 1998.
[11] N. McKinley and S. Ray, “A Decision-Theoretic Approach to Natural Language Generation,” Proc. of the 52nd Annual Meeting of
the Association for Computational Linguistics, Vol.1: Long Papers,
pp. 552-561, 2014.
[12] J. Pfeil and S. Ray, “Scaling a Natural Language Generation System,” Proc. of the 54th Annual Meeting of the Association for Computational Linguistics, Vol.1: Long Papers, pp. 1148-1157, 2016.
[13] Y. Bengio, R. Ducharme, P. Vincent, and C. Janvin, “A Neural Probabilistic Language Model,” J. of Machine Learning Research, Vol.3,
pp. 1137-1155, 2003.
[14] T.-H. Wen, M. Gašić, D. Kim, N. Mrkšić, P.-H. Su, D. Vandyke, andS. Young, “Stochastic Language Generation in Dialogue using Recurrent Neural Networks with Convolutional Sentence Reranking,”
Proc. of the 16th Annual Meeting of the Special Interest Group on
Discourse and Dialogue (SIGDIAL), 2015.
[15] T.-H. Wen, M. Gašić, N. Mrkšić, P.-H. Su, D. Vandyke, andS. Young, “Semantically Conditioned LSTM-based Natural Language Generation for Spoken Dialogue Systems,” Proc. of the2015 Conf. on Empirical Methods in Natural Language Processing(EMNLP), 2015.
[16] T.-H. Wen, M. Gašić, N. Mrkšić, L. M. Rojas-Barahona, P.-H. Su,
D. Vandyke, and S. Young, “Multi-domain Neural Network Language Generation for Spoken Dialogue Systems,” Proc. of the 2016
Conf. on North American Chapter of the Association for Computational Linguistics (NAACL), 2016.
[17] Y. Liu, Y. Zhang, W. Che, and B. Qin, “Transition-Based Syntactic
Linearization,” NAACL 2015, pp. 113-122, 2015.
[18] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever,T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, “Mastering the game of Go with deep neural networks and tree
search,” Nature, Vol.529, pp. 484-489, 2016.
[19] M. N. Katehakis and A. F. Veinott, “The Multi-Armed Bandit Problem: Decomposition and Computation,” Mathematics of Operations
Research, Vol.12, No.2, pp. 262-268, 1987.
[20] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysisof the multi-armed bandit problem,” Machine Learning, Vol.47,
pp. 235-256, 2002.
[21] M. P. Marcus, B. Santorini, and M. A. Marcinkiewicz, “Building aLarge Annotated Corpus of English: The Penn Treebank,” Computational Linguistics, Vol.19, No.2, pp. 313-330, 1993.
[22] R. Kneser and H. Ney, “Improved backing-off for n-gram language
modeling,” ICASSP, Vol.1, pp. 181-184, 1995.
[23] J. H. Lau, A. Clark, and S. Lappin, “Unsupervised Prediction of
Acceptability Judgements,” ACL 2015, Vol.53, pp. 15-1000, 2015.
[24] D. Blei, A. Ng, and M. Jordan, “Latent Dirichlet Allocation,” J. of
Machine Learning Research, Vol.3, pp. 993-1022, 2003.

784

Name:
Kaori Kumagai

Affiliation:
Advanced Sciences, Graduate School of Humanities and Sciences, Ochanomizu University

Address:
2-1-1 Ohtsuka, Bunkyo-ku, Tokyo 112-8610, Japan

Brief Biographical History:
2017 Received Master Degree in Information Science, Ochanomizu
University
2017- Doctor Candidate, Information Science, Ochanomizu University

Main Works:• “Human-like Natural Language Generation Using Monte Carlo Tree
Search,” Proc., INLG 2016 Workshop on Computational Creativity in
Natural Language Generation, pp. 11-18, 2016.

Name:
Ichiro Kobayashi

Affiliation:
Advanced Sciences, Graduate School of Humanities and Sciences, Ochanomizu University

Address:
2-1-1 Ohtsuka, Bunkyo-ku, Tokyo 112-8610, Japan

Brief Biographical History:
1995 Assistant Professor, Hosei University
1996-2003 Associate Professor, Hosei University
2003-2010 Associate Professor, Ochanomizu University
2011- Professor, Ochanomizu University
2017- Visiting Research Scholor, National Institute of Advanced Industrial
Science and Technology (AIST)

Main Works:• “Describing Semantic Representations of Brain Activity Evoked by
Visual Stimuli,” IEEE-SMC2018.

Membership in Academic Societies:• The Association for Computational Linguistics (ACL)• The Japanese Society for Artificial Intelligence (JSAI)

Journal of Advanced Computational Intelligenceand Intelligent Informatics

Vol.22 No.5, 2018

Natural Language Generation Using Monte Carlo Tree Search

Name:

Name:

Daichi Mochihashi

Tomoaki Nakamura

Affiliation:

Affiliation:

The Institute of Statistical Mathematics

Department of Mechanical Engineering and Intelligent Systems, The University of ElectroCommunications

Address:

Address:

10-3 Midori-cho, Tachikawa city, Tokyo 190-0014, Japan

1-5-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan

Brief Biographical History:

Brief Biographical History:

1998 B.S. Degree, the University of Tokyo
2005 Ph.D., Nara Institute of Science and Technology
2003-2006 ATR Spoken Language Communication Research Laboratories
2007-2010 NTT Communication Science Laboratories
2011- The Institute of Statistical Mathematics

2011- Research Fellow, Japan Society for the Promotion of Science
2013- Researcher, Honda Research Institute Japan Co., Ltd.
2014- Assistant Professor, The University of Electro-Communications

Main Works:• R. Fujii, R. Domoto, and D. Mochihashi, “Nonparametric BayesianSemi-supervised Word Segmentation,” TACL, Vol.5, pp. 179-189, 2017
• T. Nakamura et al., “Segmenting Continuous Motions with Hidden
Semi-Markov Models and Gaussian Processes,” Frontiers in
Neurorobotics, Vol.11, p. 67, 2017.

Main Works:• “Online Algorithm for Robots to Learn Object Concepts and Language
Model,” IEEE Trans. on Cognitive and Developmental Systems, Vol.9,
No.3, pp. 255-268, 2017.

Membership in Academic Societies:• The Robotics Society of Japan (RSJ)• The Japanese Society for Artificial Intelligence (JSAI)

Membership in Academic Societies:• Information Processing Society of Japan (IPSJ)• The Japan Statistical Society

Name:
Takayuki Nagai

Affiliation:

Name:

Professor, Graduate School of Informatics
and Engineering, The University of ElectroCommunications

Hideki Asoh

Affiliation:
Deputy Director, Artificial Intelligence ResearchCenter, National Institute of Advanced Industrial
Science and Technology (AIST)

Address:
1-5-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan

Brief Biographical History:
1-1-1 Umezono, Tsukuba, Ibaraki 305-8560, Japan

1998- Associate Professor, The University of Electro-Communications
2002- Visiting Researcher, University of California, San Diego
2014- Professor, The University of Electro-Communications

Brief Biographical History:

Main Works:

Address:
1983- Electrotechnical Laboratory, Ministry of International Trade andIndustry
1993-1994 Visiting Researcher, German National Research Center for
Information Technology (GMD)
2001- National Institute of Advanced Industrial Science and Technology(AIST)

Main Works:• “Jijo-2: An office robot that communicates and learns,” IEEE Intelligent
Systems, Vol.16, No.5, pp. 46-55, 2001
• “On the mean convergence time of evolutionary algorithms without
selection and mutation,” Proc. of the 3rd Int. Conf. on Parallel Problem
Solving from Nature, pp. 88-97, 1994.

• “Online Algorithm for Robots to Learn Object Concepts and Language
Model,” IEEE Trans. on Cognitive and Developmental Systems, Vol.9,
No.3, pp. 255-268, 2017.

Membership in Academic Societies:• The Robotics Society of Japan (RSJ)• The Japanese Society for Artificial Intelligence (JSAI)• The Institute of Electrical and Electronics Engineers (IEEE)

Membership in Academic Societies:• The Japanese Society for Artificial Intelligence (JSAI)• The Institute of Electronics, Information and Communication Engineers(IEICE)• Japanese Neural Network Society (JNNS)

Vol.22 No.5, 2018

Journal of Advanced Computational Intelligenceand Intelligent Informatics

785