A Modules-Based, Task-Navigational Dialogue SystemMotoki Yatsu
Rafal Rzepka
Kenji Araki
Graduate School of Information Science and Technology, Hokkaido University{my, kabura, araki}@media.eng.hokudai.ac.jp
Abstract
There are needs of dialogue system that can act as anavigator to tasks that a user has but are uncertain of. We
can realize smooth navigation to certain tasks, combining
multiple non-task-oriented conversational agents withtask-oriented ones. Methodology of treating both nontask-oriented and task-oriented modular dialogue systems
in one integrated system has yet to be developed. The
proposal method, which adopts FSM (finite-statemachine) model, has each state for non-task-oriented andtask-oriented dialogue, conditioned with a user’s aimvector a: which has WordNet semantic similarity of user’sutterance and keyword set of task domains as itscomponent. Decision of a task domain is performed
through evaluation of components of the vector on a statetransition. Two dialogue examples which show theappropriateness of the task decision are presented.

Key Words- Dialogue, Integrated Dialogue System,
Human-Computer Interaction, domain selection, ontology

1. Introduction
We propose a dialogue system which can find user’s
need for assistance from a task-oriented dialogue system.
Until the system find the user’s need (domain decision), it
can perform non-task-oriented dialogue, in which nodefinite task is assigned to the system.

1.1 Desire for communication
In some developed countries, it has been warned [1]that there will be more elderly people who live alone andhave less communication opportunities with theirneighbor people, which leads to desire for communication
unsatisfied. From a worldwide view, the emergence ofsocial media such as Twitter 1 and Facebook 2 also makes
us estimate that people have unsatisfied desire tocommunicate.
A system was invented in the computer’s first age as a
substitute to a psychiatrist for a patient to talk to, known
as ELIZA [2]. The technology was then improved to
become systems that can imitate human’s basic ability to1
2

http://twitter.com
http://www.facebook.com

converse with other social beings. We now call such
systems chatterbots.
Not many researches had sought these objectives inmethodological and multilingual perspectives until
recently, but in this field we can notice a chatterbots
which generates utterance in Japanese using linguisticknowledge in sentence end [3] and a statistical method [4],which applies word n-gram models in Japanese utterance
generation in multiple ways.
On the other hand, dialogue agents which havemultiple task domains were also developed, and are
already implemented as automated online assistants, suchas the online help center of IKEA 3.

1.2 Text-based dialogue interfaces
In works such as [5][6], the domain of dialogues werelimited to task-oriented ones. Imai et al. [7] expanded it to
non-task-oriented dialogues. However, the method does
not accept a multi-turn task-oriented component dialoguesystem because the system selects an utterance from its
components based on the scores calculated in each one
turn.
The proposal method enables multi-turn task-oriented
dialogue to be performed in the integrated system byadopting a state transition model.

1.3 Outline of this paper
In this paper, first we introduce the aim vector, thenwe overview the experimental system for the proposal
method, and the method to calculate definiteness of theuser’s goal is reviewed. Then we evaluate two examples
in which non-task-oriented dialogues were performed
with domain decisions made successfully or not.
The turn differential ∆𝒂 of aim vector 𝒂 (see 2.1) has
a component which equals to an average of semantic
similarity values (see 2.3) of all the nouns in user
utterance to nouns from all the keyword sets (see 2.4)
defined for each task-oriented component dialogue system.
The system judges if the degree ‖𝒂‖ (see 2.1) of theaim vector exceeds the threshold, and if it does, it transits
to the task-oriented dialogue state after selecting thenearest domain (see 3.2).

3

http://www.ikea.com/

Detect‖𝒂‖ ≥ 𝑡ℎ𝑟𝑟𝑟ℎ𝑜𝑜𝑜

Continue
dialogue(Domain decision)

Taskoriented
dialogue

Non-taskoriented
dialogueContinue
dialogue

Extract 𝑁𝑈 nouns 𝑢1 … 𝑢𝑁𝑈
from input utterance 𝑈

End of dialogue oruser quits

In this chapter, we will discuss the main theories thatgovern the proposal method.

2.3 Semantic Similarity in WordNet
From a user utterance, the system calculates a turndifferential ∆𝒂 = 𝒂(𝑡) − 𝒂(𝑡 − 1) of 𝒂 that suggests thedegree of interest by the user to each keyword set tied totasks. Calculation is performed using the algorithm
depicted in Figure 2. We used morphological analyzer
MeCab 4 for extraction of nouns. In calculation, LeacockChodorow [8] semantic similarity is obtained:(1)𝑟𝑎𝑎(𝑐1 , 𝑐2 ) = max �−log�𝑁𝑝 /2𝐷��
where 𝑁𝑝 stands for the shortest path length between
twowords 𝑐1 and 𝑐2 , and 𝐷 the depth of taxonomy. We4

http://mecab.sourceforge.net

K1: (food, meal)
K2: (movement, travel,journey)⋮
KM: (clothes, fashion)𝑖Difference of a is given as𝑎𝑎𝑎𝑎𝑎𝑎(𝑈, 𝐾1 )⎛⎞∆𝒂 = ⎜ 𝑎𝑎𝑎𝑎𝑎𝑎(𝑈, 𝐾2 ) ⎟⋮⎝𝑎𝑎𝑎𝑎𝑎𝑎(𝑈, 𝐾𝑀 )⎠2.1 Aim vector and definiteness of user’s aim

The proposal method adopts a model of finite-statemachine; in which one state transits to another if thetransitional condition of a state is met. The system has
two states: non-task-oriented dialogue state and taskoriented dialogue state. Figure 1 shows the state diagram.
(See Chapter 3 for detailed description.)

For each keyword set,calculate average of sim()

𝑗2. Core methods

2.2 State Transition ModelModules
Configuration
for 𝑀 modules

𝑎𝑎𝑎𝑎𝑎𝑎(𝑈, 𝐾𝑛 )1=� � 𝑠𝑠𝑠(𝑢𝑖 , 𝑘𝑗 )𝑁𝑈 𝑁𝐾𝑛Figure 1. The system overview shown in a state diagram.

An aim vector 𝒂 represents the orientation of user’s
current aim. In this paper, we define an aim as the user’s
goal with a certain orientation with which we canassociate a task domain (see 3.3) and with a measureable
degree of definiteness.
The definiteness of the current user’s aim can be
expressed in Euclidean norm ‖𝒂‖ . In the discussions
below, 𝑡 as in 𝒂(𝑡) denotes the number of present turn ina dialogue.

Get keyword sets(𝑁𝐾𝑛 nouns in set 𝐾𝑛 )Figure 2. Chart of the algorithm which evaluates ∆𝒂,the displacement of aim vector a and an example of keyword sets

used Natural Language Toolkit 5 running on Python andJapanese WordNet [9] to analyze Japanese utterance input
and system outputs.

2.4 Domains, keyword sets
A keyword set (an example shown in Figure 2) used inthe proposal method includes a group of nouns related toa task domain. Each keyword set corresponds to a task
domain which the task-oriented component dialoguesystem takes account of.

2.5 Modules
The component dialogue systems, whether taskoriented or non-task-oriented, of the proposal dialoguesystem are implemented modularly. The modules areconfigured using also a text file so that one can add an
infinite number of modules without altering the main
dialogue system program. For non-task-oriented dialogue,each module is modified based on an independentdialogue system and can input one line utterance andreturn one to the main system. To select a response, theweighted score sums of non-task-oriented dialogue
modules are calculated using scripted evaluation methods(inner modules). We used the three methods from thework of Imai et al. [7] to evaluate the overall relevance ofan input utterance to an output from a module.
5

http://www.nltk.org/

Usr >The lectures will begin tomorrow
Sys >Anyhow the lectures will begin, so dashi (noise)
Usr >so dashi what?
part (1)
Sys >It is obvious that it is delicious ta (noise).
Usr >certainly it has some delicious taste, but it is about lectures in my university that I want to know.
Sys >But, it is unmistakable that fat is a delicious taste, and the body needs a moderate amount of it.
Usr >Do you know something about lectures in the university?
Sys >Exactly I know much about it demo (noise).
Usr >Lectures will be started in the university, so I need information about them.
Sys >You need it, is it university?
Usr >It’s university.
Sys >On the contrary, some people who got 80% marks seems to have been rejected.
Usr > No, it’s not about exams, it’s on lectures. It might be better I’d ask the office instead.
Sys >I am sure it is high.
part (2)Usr >What do you mean by high?
Sys >Well.
Usr >No information about lecture is on the Internet, so I have to go directly to the office. But it takes more than 2 hours by train…
Sys >It was that University is surely high.
Usr >I don’t mean it stands on the high place. It takes a long time to move there because my house is far away from it.
Guide >From the conversation with the chat system, you seem interested in: health, illness.
Figure 3. A dialogue log between a user and the proposal system.
Japanese particles which can be regarded as noises are written with annotation. (threshold = 10.0)

The three methods were: computing Levenshtein distance
between the output and a response in a man-to-man chatlog, evaluation of grammaticality using N-gramprobability, and comparison of word-end expressions.

We can consider the end of task-oriented dialogue or
user’s halt from the dialogue as the condition of the statetransition from the task-oriented state to the initial state.

4. Evaluation of the proposal system
3. The proposal method as a state machine
In this chapter, we will view the system’s behavior asa finite-state machine.

3.1 Initial state
The user, who holds an aim with some degree ofindefiniteness, starts a dialogue with the system. In ourreal world, the domain of the aim is oriented to a task
domain or it is not to any task domain. In the latter case,the user engages in a non-task-oriented dialogue. Basedon this observation the proposal system holds the nontask-oriented dialogue state.
The system responds to a user input with an utterance
which scores the highest among the non-task-orientedmodules (see 2.5).

3.2 State transition and domain decision
If the norm ‖𝒂‖ of cumulated vector 𝒂 exceeds thethreshold value, which suggests that the user’s current
interest to one of domains becomes definite, the non-taskoriented dialogue state transits to task oriented dialogue
state. Before a state transition occurs, the system finds thelargest component of 𝒂, which is defined as related to (asdescribed in 3.1) the nearest domain keyword set. The
nearest domain is applied to a task-oriented dialogue
module most desirable to the user.

In the subsections below, we will discuss what isneeded for the proposal system to satisfy the demand of
the main usage case. We show here 2 results from an
ongoing Web experiment 6 with 5 keyword sets we choserandomly.

4.1 Erroneous decision
An example of domain decision is shown in Figure 3.
This sample 7 was taken by one of us and the source
dialogue text is in Japanese. In the dialogue part (1), theuser shows that she is interested in the information about
lectures given in her university and then asks the system
for it. The unnatural word end of the system’s utterance(“dashi”) makes the user respond by reduplication of thechunks. The system returns a response, however, in acompletely different context (with “dashi” interpreted as anoun), which delays the user’s decision making.
In part (2) occurs another change of topic through anentire conversation. The user takes two extra turns
conversing with the system in order to provide it withappropriate information.
In the end of the dialogue, the system shows the user adomain that is considered the most relevant (i.e.
associated to the strongest component of 𝒂) to the topic ofthe dialogue. However, we can consider this example as
an erroneous decision since there are neither words of
6

3.3 End of task-oriented dialogue

http://arakilab.media.eng.hokudai.ac.jp/~my/experiment.html
All the dialogues shown in this paper are translated from Japaneseoriginals, and any residual Japanese word or morpheme is italicized.

7

regions of body nor names of illness in the user’sutterances in this dialogue example.

4.2 Correct decision
In Figure 4 is an example where a decision of adomain was correctly performed but in an earlier stage
than the user had expected. In this case the user might
have had other opinions about what she would like to
do/talk against the computer. This example was chosen bya researcher not in the field of computational linguistics.

Usr >My job hunting begins next month.
Sys >Is warm fun?
Usr >I think it is better for me to buy a new business suit.
Sys >I don’t understand better well.
Usr >Is there any shop that sells clothes cheap around here?
Sys >Cheap around here?
Usr >Yes, like a clothes corner in the department store.
Sys >Are talking about cheap?
Usr >Yes. About being cheap.
Sys >Continue about that.
Usr >Tell me about a store that sells clothes for men.
Guide >From the conversation with the chat system, you seem interested
in: clothes.

Figure 4. A correct domain decision example.
(threshold = 5.0)

5. Discussion

References

The accidental changes that caused the erroneousdecision shown in the dialogue of Figure 3 are supposedly
due to no preservation of context. The main cause of nopreservation of context is caused both for modules’internal reasons, which are innate in some types ofcomponent dialogue systems (e.g. which uses no turntaking way of response-generation) thus cannot be fixed,
and also caused by the system’s criteria to switch modules
we described in (2.5).
One way to deal with the problem may be to add acontext inspector as an inner module (see 2.5) and let themain system prefer an output that stays in the domain towhich the previous utterance belongs.
On the other hand, we can conclude that the correct
domain decision is caused mainly by user’s disregard ofutterance from the component dialogue systems. This
assumption suggests that non-task-oriented dialogue statewith only randomly generated responses are notnecessarily effective to the user’s domain selection. Also,
the proposal system seems responsible for assisting theuser on more stages rather than leaving entire dialogue tonon-task-oriented modules, in order to preserve thecontext.

[1] PK. Kam, “Empowering Elderly People: A Community
Work Approach”, Community Development Journal, Oxford
University Press, 1996, pp. 230-240.

6. Conclusion and Future WorkIn this paper, we observed how the proposal method
which adopts FSM model is applied to certain usages. In
the discussion we found issues such as no context
preservation in dialogue, and innate problems in dialogue
modules, and we mentioned a possible solution in thesection. We must also consider what advantages modular
architecture has in a dialogue system.
In this research, the system has a dialogue interface
which deals with both the non-task-oriented and taskoriented dialogue, but not fully task-independent
conversational capability, as shown in the experiment. In
the future research, we aim to survey further inquantitative aspects, including threshold and error/successratio.

[2] J. Weizenbaum, “ELIZA—a computer program for the studyof natural language communication between man and machine”,
Communications of the ACM, New York, NY, USA, 1966, pp.
36-45.
[3] S. Higuchi, R. Rzepka and K. Araki, “A Casual
Conversation System Using Modality and Word Associations
Retrieved from the Web”, Proc.of the 2008 EMNLP, October
2008, pp. 382-390.
[4] M. Takahashi, R. Rzepka, and K. Araki, “A Performance
Evaluation of Sentence Generation Method Using Web Searchand Word N-gram Models”, NLP2010 Proceedings (inJapanese), March 2010, pp. 391-394.
[5] N. Kanda, K. Komatani, et al, “Robust Domain Selection
Using Dialogue History in Multi-domain Spoken Dialogue
Systems(Speech Processing)”, Transactions of Information
Processing Society of Japan 48(5) (in Japanese), 2007-05-15, pp.
1980-1989.
[6] S. Ueno, I.R. Lane, and T. Kawahara, ”Example-based
training of dialogue planning incorporating user and situation
models”, Proc. ICSLP, 2004, pp.2837-2840.
[7] K. Imai, R. Rzepka, and K. Araki, “Performance Evaluationof Method for Selecting Best Replies from Candidate Sentencesfrom Different Dialogue System”, IPSJ SIG Technical Report)(in Japanese), 2010-NL-195(10), 2010, pp. 1-7.
[8] C. Leacock and M. Chodorow, “Combining local context
and WordNet similarity for word sense identification”, AnElectronic Lexical Database In WordNet: A Lexical Reference
System and its Application, The MIT Press, 1998, pp. 265–283.
[9] K. Kuroda, F. Bond and K. Torisawa, ”Why Wikipedia
needs to make Friends with WordNet” in The 5th International
Conference of the Global WordNet Association (GWC-2010),
Mumbagi, 2010, pp 9-16.