Feature Inference Based on Label Propagation
on Wikidata Graph for DST
Yukitoshi Murase, Koichiro Yoshino, Masahiro Mizukami, Satoshi Nakamura

Abstract One of the major problems in Dialog State Tracking (DST) is the large
size of user intention space, and thus data preparation for statistical models is hard.
In this paper, we propose a method to estimate reliable features of utterances basedon creation of a knowledge graph and inference of features on the graph. For theknowledge graph, Wikidata, a large knowledge base consists of concepts and theirrelations on web, applied to construct a task-domain dependent graph structure. On
the created graph, the label propagation algorithm is used to infer features. This
inference algorithm propagates of unobserved word nodes from observed words inuser utterances. In addition, dialog history words in previous turns is considered
as inputs of label propagation. A large vector is created with the inference algorithm, and it is used as a feature of machine learning model. Multi-layer perceptron
is adopted as machine learning model of the dialog state tracker, which predicts
user intentions. Experimental results show that the proposed method obtain various
and stable features, and the results achieve higher scores than the prepared baseline
tracker, which does not use the inferred features from the knowledge graph.

1 Introduction
Dialog state tracking (DST) is an important task of spoken language understanding.
DST is a task to trace user intentions (dialog states) of input utterances and several
dialog histories [12, 5]. One major problem of DST is the large size of user intention
space, which consists of every possible intention on tasks or domains. Collecting
enough training data, which covers every user intention in test data, is hard dueto the size of the space [10]. User intentions are mostly depended on tasks anddomains, and this is one of the major reasons why preparing large scale data is hard.
Yukitoshi Murase, Koichiro Yoshino, Masahiro Mizukami, Satoshi Nakamura
Graduate School of Information, Nara Institute Science and Technology (NAIST), Takayama-cho,Ikoma, Nara, 6300192, Japane-mail: y-murase@is.naist.jp

1

2

Yukitoshi Murase, Koichiro Yoshino, Masahiro Mizukami, Satoshi Nakamura

In this paper, we extend and relax words in an user utterance into the generalizedclass word by the inference on knowledge graph. Knowledge graph has been widelyused as resources for spoken dialog systems [9, 1], especially on Bayesian update of
dialog state [4, 2, 7]. These works construct graphs by hands or unsupervised manners from Web search queries. Yi et al. [15] constructed the graph from database of
web search queries and inferred the queries on the graph such as dialog state tracking. This work inspires our proposed method where the inference on knowledge
graph can be used for feature, which improves the machine learning-based dialog
state tracker.
Our proposed method adopted Wikidata and label propagation, which are respectively used as the graph and the inference algorithm. Wikidata is a free andopen knowledge base [8], which contains numerous items and their properties. The
items expresses names of concepts, and their properties expresses relationships between items. According to the characteristic of the data structure, undirected graphis created with items as nodes and properties as links.
Bag-of-words (BoW) is a basic feature and commonly used as the baseline feature of statistical dialog state tracker. However, the vector space of the word feature
will be sparse because training data is not often enough for statistical learning. One
solution for this problem is employing embedded expressions of words [13, 6] thatis trained from large-scale data. This method compresses a vector of each word into
fixed-length dimensions by using distribution of surrounding words in contexts torepresent the meaning of the word implicitly. In contrast, subgraph is constructed tocapture meanings of utterances with inferring neighbors in the our proposed method.
Once some words are observed in an utterance, label propagation infers the featureson the subgraph by using node discrimination [14, 11]. This method realize given
values to some diversions of sparse word vectors.
Label propagation algorithm is one of the node discrimination methods and propagates labels from the observed node (seen words in the user utterance) to neighbors.
Combinations of estimated labels can be used as a feature for the utterance. The algorithm has several procedures for feature extraction. In other words, the labels of
seen nodes are labeled as known class (=1), and other nodes are labeled as unknownclass (=0) at the first step. The label of each node is propagated to neighbors once thelabel propagation is executed on the graph. The advantages of the proposed method
are that subgraph of Wikidata is easily created, and label propagation is applicableon any graph.

2 Dialog State Inference on Knowledge Graph
Our work is inspired by the previous work which tried transforming knowledge baseto inference knowledge graphs (IKG) as graphical models [15]. In this work, IKG
predicts dialog states by inferring confidence of each node. Markov Random Field(MRF) is used to find the most appropriate node as dialog state. The knowledge
base contains data types of entities and attributes where they represent items andFeature Inference Based on Label Propagation on Wikidata Graph for DST

3

relationships. The graphical model contains both entities and attributes as nodes. In
other words, attribute nodes are always exist between entity nodes, and the attributenodes can be factored nodes when a inference method executed on MRF. Their approach can utilize any inference method, and the method extracts factors from anutterance to infer some unknown entity class. A node, that have the highest confidence, is selected as the current dialog states. In contrast, we constructed undirected
graph with only entities (items in Wikidata), where its edges represent relationships,
and our proposed method inferred particular node with label propagation algorithm.

3 Feature Inference on Wikidata Graph
3.1 Subgraph Creation from Wikidata
Wikidata consists of items and properties for creating a graph, and items and properties respectively become nodes and edges on the graph. On the graph, label propagation algorithm extracts features for input of machine learning based tracker. However, Wikidata has numerous items, and thus label propagation costs a large calculation time during the inference process on the Wikidata graph. Due to the calculation
time, a subgraph is created with words in utterances of data sets, and the words arematched with a name of items in Wikidata.
For the graph creation process, each utterance is tokenized by NLTK1 tokenizer,
and words that matched with NLTK stopwords, “!”, “?”, and etc are cleared. Uncleared words are added as initial nodes on the subgraph, and all related items ofinitial nodes are added as neighbor nodes on the subgraph. Finally, all nodes are
given unique ids since there exists name duplications between some items.
An example of a subgraph is shown in Fig. 1 and consists corresponding nodes of“Singapore”. The “Singapore” node is added on the subgraph with its neighboring
nodes (“Asia”, “City”, “Island nation”, “Country” and “Malaysia”). Nodes on 1hop relation are also added (“Area” and “Continent”). In addition, we assume that
Malaysia is also observed in utterances, and related nodes in Wikidata are connectedto the nodes of “Malaysia” (“Country” and “Asia”).

3.2 Label Propagation on SubgraphLabel propagation predicts class labels of unobserved nodes when labels of someobserved nodes are given. The algorithm assumes that neighboring nodes in thegraph network may have the same class label. Our proposed method defines observed class nodes and unobserved class nodes from utterances and infers class labels of unobserved nodes to extract features for machine learning models.
1 NLTK: http://www.nltk.org/

4

Yukitoshi Murase, Koichiro Yoshino, Masahiro Mizukami, Satoshi Nakamura

instance ofContinent

Asia

Continent
continent

Malaysia
shares border withCity

instance ofSingapore

instance ofinstance ofproperties forthis typeinstance ofIslandnationAreasubclass ofCountry

Fig. 1 An example of Wikidata graph with the appeared words “Singapore” and “Malaysia”. There
are titles of relations on edges, and neighbors. Some neighbors have shared relations of other nodes
and an independent relation itself.

In label propagation algorithm, node links are represented as W. W is an N × N
matrix where N is the number of nodes in the graph. Each element in W represents
the link existence. y is a vector and contains class labels for each node. In our case, yexpresses the observation of the word in the current utterance. In other words, label
1 means that the node is observed, and 0 means that the node is not observed in theutterance. f is a vector of predicted class label of each node. The objective functionof label propagation to be minimized is defined as,n

J( f ) = ∑ (yi − fi )2 + λ ∑ wi, j ( fi + f j )2 .
i=1

(1)

i< j

The first term in Equation (1) approximates the predicted vector f to be close to the
input vector y. The second term approximates the predicted values of neighboring
nodes. λ is a constant value to keep balance between the first and the second terms.
Formula deformation of Equation (1) with Laplacian matrix is,J( f ) = ∥y − f∥22 + λ fT Lf.

(2)

L ≡ D − W is Laplacian matrix, and D is the summation of each row into diagonalcomponents. This minimization problem is solved with,(I + λ L)f = y,(3)

as defined in [14].
We implemented equation (3), where observed words in utterances are vectorized
as y, and f is a vector of predicted values of relaxed class nodes inferred by the
Wikidata graph. y’s elements are initially ones if words are observed in the input
utterance. Then, we calculate f by,

Feature Inference Based on Label Propagation on Wikidata Graph for DST

f = y(I + λ L)−1 .

5(4)

The previous values of y are also added with a discount value γ , which is a value
between 0 ≤ d ≤ 1 to consider the sequence of dialog. Once the discount value isfactored on previous values, y is replaced with factored values and added labels at
the current utterance. At the end, f is calculated by equation (4) and returned as
the feature vector of the current utterance. Label propagation with γ is shown in
Algorithm1.
Algorithm 1 Label Propagation with Discount Factor
Require: λ > 0, 0 ≤ d ≤ 1, i = index and t = time
if Initial Utterance in Sessions thenfor yi,t in the word list do
yi,t = 1
end forelse
From second utterance do:for yi,t do
if yi,t in the word list thenyi,t = 1 + γ yi,t−1
else
yi,t = γ yi,t−1
end ifend forend if
f = y(I + λ L)−1
return fContinent
y = 0.0

Asia
y = 0.0
Malaysia
y = 1.0

Cityy = 0.0

Singaporey = 1.0

Areay = 0.0

Islandnationy = 0.0

Countryy = 0.0

Fig. 2 An example of Wikidata graph with the appeared words “Singapore” and “Malaysia”, andeach node has a y value to be 1 for appeared nodes and 0 for others.

6

Yukitoshi Murase, Koichiro Yoshino, Masahiro Mizukami, Satoshi Nakamura

Continent
f = 0.07704

Asia
f = 0.23112
Malaysia
f = 0.59371

City
f = 0.13223

Singaporef = 0.48486

Area
f = 0.04407

Islandnationf = 0.18436

Countryf = 0.25259

Fig. 3 An example of Wikidata graph after running label propagation on Fig. 2, and nodes have fvalues. Of course, observed nodes have higher values, and closer nodes also have higher values. For
example, “Country ” and “Asia” are linked to both observed nodes, and “Country” is also linked
to “Singapore” 1-hop away by “Island nation”. Thus, “Country” has a little higher predicted value
than the value in “Asia”.

4 Experimental Evaluation
4.1 Data Set and Task Description
We evaluated the proposed method on DSTC4 main task, which tracks dialog states
at each utterance level. The corpus consists of conversations on touristic informationfor Singapore and contains 35 dialogs by 3 tour guides and 35 tourists. The corpus
also contains 31,034 utterances and 273,580 words, which are manually transcribedand annotated. The corpus is respectively divided into training, development and test
set, and each data set has 14, 6, and 9 dialogs. Each dialog is divided into sub-dialogs
with annotations of begin/inside/others (BIO) tagging. ‘B’ annotation represents the
beginning of the sub-dialog session, and ‘I’ annotation represents inside of the subdialog session. Otherwise, ‘O’ is annotated to the utterance. Each sub-dialog session
is annotated with topics of five categories, and dialog states, which specify the contents of sub-dialog. The dialog states belong to one of topics for whole sub-dialog
session. The number of possible dialog state is about 5,000, and each utterance has
multiple states. We define that the main task’s problem is solved as multi-label classification of machine learning method.
For experimental comparison, a baseline method, which is fuzzy string matchingwith ontology, is provided. We also examined BoW, BoW with Word2Vec (W2V),
and our proposed method for the fair comparison. The baseline method matchessome part of utterance and ontology’s entries. Ontology is constructed as tree structure and has all possible dialog states at its leaves. The best score’s method at DSTC4
are provided as different methods.
Accuracy and F-measure scores are used for evaluation metrics. The accuracy
is harmonic mean of precision and recall of utterances that the tracker successfully

Feature Inference Based on Label Propagation on Wikidata Graph for DST

7

recognized the all of slots. The f-measure score is the ratio of slots that the tracker
successfully recognized. There are two categories of scores: schedule1 calculates
score at each utterance; and schedule2 calculates score at each end of sub-dialog.

4.2 Evaluation Settings
Feed forward neural network (FF-NN) model is adopted as machine-learning basedclassifier. Inputs of the classifier are defined three types of features: BoW; BoW
with W2V; and our proposed method. BoW is a sparse vector of observed word inuser utterance. W2V is summation of word vectors, which is calculated by W2V for
all observed words in the user utterance. All Wikipedia articles are used to train theW2V with the default setting of gensim2 library. Dialog histories are also consideredduring sub-dialog session by just adding previous feature vectors.
For FF-NN model, sigmoid function is used as the activation function of output
layer. The following parameters are used to train the FF-NN: learning rate=0.000025;
optimization method=Adam; dropout=0.2.

4.3 Parameters of the Proposed Method
We describe several parameters introduced by label propagation and the thresholdfor output of the NN model before showing the results. The input of label propagation includes dialog histories with discounted value γ . This discount value decides
the degree to consider dialog histories. Note that γ =0 means the system does notconsider any history, and γ =1 means the system never forget what users previously
said. We assume that the smaller γ is more efficient for prediction. λ , which balances between two terms in label propagation, is needed to be decided. However,
we do not have intuition for λ , so we set the balanced value between 0.5 to 8. The
last parameter is threshold τ to decide the output of NN. 0.5 is generally used, andthe smaller τ s allow the NN to output candidates that NN has smaller belief. In otherwords, setting the τ smaller will cause the increasing of recall and the decreasing of
precision. We simply set the stride by 0.1 between 0.1 and 0.9. Table 1 shows theparameter candidates that are used in experiments. We tried grid search to find thebest combination that achieves higher accuracy.

2 https://radimrehurek.com/gensim/

8

Yukitoshi Murase, Koichiro Yoshino, Masahiro Mizukami, Satoshi Nakamura

Table 1 All three parameters lists.

λDiscounts (γ )Threshold (τ )

0.5
1
1.5
2
3
8

0
0.125
0.25
0.5
0.7
0.8
0.9
1

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9

Total number of combination of parameters is 432.

4.4 Experimental Results
Table. 2 and 3 show the results of using BoW as the feature, and the results are
obtained by changing threshold τ , which makes decision to output candidates. All
scores are still lower than those of the baseline methods as the results on the tables. This is probably because using the BoW is too sparse for NN of multi-label
prediction, which has high dimensional output layer.

Table 2 Top 3 Accuracies of Bag of Words

Table 3 Top 3 F-measures of Bag of Words

Thresholdschedule1

schedule2

Thresholdschedule1

schedule2

0.9
0.8
0.7

0.00610.00540.00370.00950.00850.0066

0.7
0.6
0.5

0.01610.01530.01360.01590.01540.0132

Table 4 Top 5 Accuracies for schedule1 with Table 5 Top 5 Accuracies for schedule2 with
Proposal Features
Proposal Features

λDiscount:γ Threshold:τ Accuracy

0.5 1.0
0.5 1.0
0.5 1.0
1
1.0
3
1.0
baseline

0.3
0.2
0.4
0.3
0.3

0.04900.04810.04560.04520.04270.0374

λDiscount:γ Threshold:τ Accuracy

0.5 1.0
0.5 1.0
0.5 1.0
0.5 1.03
1.0baseline

0.3
0.2
0.4
0.5
0.3

0.05590.05590.05490.05210.05020.0488Feature Inference Based on Label Propagation on Wikidata Graph for DST

9Table 6 Top 5 F-measure for schedule1 with Table 7 Top 5 F-measure for schedule2 with
Proposal Features
Proposal Features

λDiscount:γ Threshold:τ F-measure

0.5 1.0
3
1.0
1
1.0
8
1.0
2
1.0
baseline

0.2
0.2
0.2
0.2
0.2

0.34440.33970.3391
0.33810.33710.2506

λDiscount:γ Threshold:τ F-measure

1
1.0
3
1.0
8
1.0
0.5 1.02
1.0baseline

0.2
0.2
0.2
0.2
0.2

0.37590.37630.37540.37500.37270.3014

Table 4 - 7 shows the results of our proposed method’s feature. Specifically,
Table 4 and 5 show accuracies and Table 6 and 7 show f-measure for each schedulewith 5-best parameter conditions. Our proposed method outperformed the baseline
method on each metrics according the highest results on tables.
According to the result tables, discount factor (γ )=1 achieves higher results, andthus we could conclude that all histories without discounting contributes the better
result. Lower λ and thresholds (τ ) call higher scores for accuracies. All top 5 resultsof f-measures have threshold τ =0.2, and non-stable value for λ for F-measure.
Fig. 4 and Fig. 5 respectively show changes of f-measures on schedule 1 and
2 according to the changes of discount factor γ . λ is fixed as 0.5 where the value
achieved the best results on Table 4 - 6. Fig. 6 and Fig. 7 respectively show relations
between threshold τ and scores (precision, recall and F-measure) on both schedules.
The highest F-measure is achieved at discount γ =1.0 and threshold τ =0.2 according
to curves on Fig. 6 and Fig. 7. Lower threshold allows the FF-NN classifier to output
much more candidates of the output, which increase the recall and decrease theprecision.

Fig. 4 Lines represent f-measure versus discount Fig. 5 Lines represent f-measure versus discountvalues along different thresholds thresholds on values along different thresholds thresholds onschedule1.
schedule2.

10

Yukitoshi Murase, Koichiro Yoshino, Masahiro Mizukami, Satoshi Nakamura

Fig. 6 Precision and recall. X-axis represents Fig. 7 Precision and recall. X-axis representschanges of thresholds, and y-axis represents f- changes of thresholds, and y-axis represents fmeasure on schedule1.
measure on schedule2.

An example of the differences between baseline, proposed method, and gold
standard labels are shown on Table 8. Compared to the baseline, the proposed
method predicted value ‘Fee’ for ‘INFO’ where gold standard label also has. The
word ‘Fee’ is not observed in the utterance, however, the proposed method may
successfully predicted the label by features, which is probably inferred from ‘free
entry’ in the user utterance.
Table 8 Frame Labels of Baseline, Proposed Method, and Gold Standard for an Utterance
UtteranceBaseline ProposedMethod

Uh National Museum, you may even get {}free entry because it’s a- if it’s a public
holiday.

{’INFO’: [’Fee’]}GoldStandard{’PLACE’: [’National
Museum of Singapore’],’INFO’: [’Fee’]}All scores of 5 methods on schedule1 and schedule2 are showed on Table
9 and 10 for the last comparison. The new results are BoW with W2V as input
for NN model and the best results at DSTC4. Our proposed method outperforms
baseline, BoW, BoW with W2V, however, the best result at DSTC4 has over 0.2
higher for f-measure [3]. One of the reasons why the best results outperforms all theother results is that the method used multiple kinds of features with elaborate handcrafted rule-based features. The method requires hard work to imitate. The biggest
difference with our proposed method is that our method used fully automated andunsupervised feature creation.

Feature Inference Based on Label Propagation on Wikidata Graph for DST

11

Table 9 Scores on schedule1

Accuracy
Precision
RecallF-measure

Baseline

BoW

BoW w/ W2V Proposed
MethodThe Best Score
at DSTC4

0.03740.35890.19250.25060.00360.00990.04400.01630.00970.28500.06590.10700.11830.57800.49040.5306

Baseline

BoW

BoW w/ W2V Proposed
MethodThe Best Score
at DSTC4

0.04880.37500.25190.30140.00660.00930.53350.01590.01320.25630.0736
0.11430.14730.58980.56780.5786

0.03890.44450.27490.3397

Table 10 Scores on schedule2

Accuracy
Precision
RecallF-measure0.05020.4596
0.3186
0.37635 Conclusion
Label propagation on Wikidata graph ideally inferred features for Neural Networkmodel, and the trained model outperformed other models, which is trained by otherfeatures. In other words, our proposed method automatically created features forlarge user intention space and had improved accuracy and f-measure. The experimental results showed some better combinations of parameters which had higherscores on the test set. Specially, discount and threshold values were static for fmeasure’s top 5 results. Inferred feature on subgraph created with nodes of words inthe data set, although subgraph was not considered multi-word expressions. Moreover, the graph is created with nodes of 1-hop away from nodes, and this limit expresses less relations (properties) of nodes. We will also consider multi-word expressions and more distant nodes from the observed words in user utterances, andthus these improvement will bring a variety of properties to existing nodes for future
work. Consequently, we will focus on improving the graph creation.

6 Acknowledgments
This research and development work was supported by the MIC/SCOPE #152307004.

12

Yukitoshi Murase, Koichiro Yoshino, Masahiro Mizukami, Satoshi Nakamura

References
1. Ali E.K., Xiaohu L., Ruhi S., Gokhan T., Dilek H.T., Larry H.: Extending domain coverage oflanguage understanding systems via intent transfer between domains using knowledge graphs
and search query click logs. In: Proc. ICASSP, 4067-4071, (2014)
2. Antoine R., Yi M.: Efficient probabilistic tracking of user goal and dialog history for spoken
dialog systems. In: Proc. INTERSPEECH, 801-804, (2011)
3. Franck D., Ji Y.L., Trung H.B., Hung H.B.: Robust Dialog State Tracking for Large Ontologies. Dialogues with Social Robots, Springer Singapore, 475-485, (2017)
4. Fabio C., Puay L. Lee.: Searching the web by constrained spreading activation. In: Proc.
Information Processing and Management 36.4, 585-605, (2000)
5. Jason W., Antoine R., Deepak R., Alan B.: The dialog state tracking challenge. In: Proc.
SIGDIAL, 404-413, (2013)
6. Jeffrey P., Richard S., Christopher D.M.: Distributed representations of words and phrases
and theircompositionality. In: Proc. EMNLP, 1532-1543, (2014)
7. Judea P.: Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann (2014).
8. Kurt B., Colin E., Praveen P., Tim S., Jamie T.: Freebase: a collaboratively created graphdatabase for structuring human knowledge. In: Proc. ACM SIGMOD, 1247-1250, (2008)
9. Lu W., Larry H., and Dilek H.T.: Leveraging semantic web search and browse sessions for
multi-turn spoken dialog systems. In: Proc. ICASSP, 4082-4086, (2014)
10. Matthew H., Blaise T., and Jason W.: Dialog state tracking challenge 2 and 3. (2014)
11. Oliver Chapelle B.S., and Alexander Z.: Semi-supervised Learning MIT Press, (2006)
12. Seokhwan K., Luis F.D., Rafael E.B., Jason W., Matthew H., Koichiro Y.: The fifth dialog
state tracking challenge. In: Proc. IEEE Workshop on SLT (2016)
13. Tomas M., Ilya S., Kai C., Greg S.C., Jeff D.: Distributed representations of words and phrases
and theircompositionality. In: Proc. NIPS, 3111-3119, (2013)
14. Tsuyoshi K., Hisahi K., Masashi S.: Robust label propagation on multiple networks. In: Proc.
IEEE Transactions on Neural Networks, 35-44, (2009)
15. Yi M., Paul A.C., Ruhi S., and Eric F.: Knowledge graph inference for spoken dialog systems.
In: Proc. ICASSP, 5346-5305, (2015)