Paper Study: A Composite Kernel Approach for Dialog Topic Tracking with Structured Domain Knowledge from Wikipedia



1 Introduction

Current weakness: previous work on dialog interfaces has focused on dealing with only a single target task

analyze and maintain dialog topics from a more systematic perspective:

1) a separate sub-problem of dialog management and attempted to solve it with text categorization approaches for the recognized utterances in a given turn.

2) domain models(knowledge-based methods) and their weakness.

This paper:  Our composite kernel consists of a history sequence and a domain context tree kernels, both of which are composed based on similar textual units in Wikipedia articles to a given dialog context.

2 Dialog Topic Tracking

Dialog topic tracking can be considered as a classification problem to detect topic transitions.

3 Wikipedia-based Composite Kernel for Dialog Topic Tracking

Classifier f can be built on the training examples annotated with topic labels using supervised machine learning techniques.

Fundamental features extracted from the utterances mentioned at a given turn or in a certain number of previous turns  is not sufficient to identify not only user-initiative, but also system-initiative topic transitions.

To overcome the above limitation, they propose to leverage on Wikipedia as an external knowledge source. This work aims at incorporating various knowledge obtained from Wikipedia into the model using a composite kernel method.

Two different kernels: 1) a history sequence kernel; 2) domain context tree kernel

These two kernels both represent the current dialog context at a given turn with a set of relevant Wikipedia paragraphs which are selected based on the cosine similarity between the term vectors of the recently mentioned utterances and each paragraph in the Wikipedia collection as follows

sim(x, pi)= φ(x)* φ(pi) / (| φ(x)| * | φ(pi)|)

where x is the utterances, pi is the i-th paragraph in the Wikipedia collection.  φ is the feature extraction function. φ(x) is computed as:

φ(x)=(α1, α2, …, α1|W|), where αi=sum(λ * tfidf(wi)), λ is the decay factor, and |W| is the size of word dictionary.

3.1 History Sequence Kernel

S=(s0,s1,s2,…,st), where sj=argmaxi(sim(xj, pi))

Hypothesis: the more similar the dialog histories of the two inputs are, the more similar aspects of topic transitions occur for them.

Sub-sequence kernel: Ks(S1, S2) (important paper cited here)

3.2 Domain Context Tree Kernel

The other kernel incorporates more various types of domain knowledge obtained from Wikipedia into the feature space. Each instance is encoded in a tree structure constructed following the rules. The root node of a tree has few children, each of which is a subtree rooted at each paragraph node in:

Pt = {pi | sim (xt, pi) > θ}, where θ is a threshold value to select the relevant paragraphs

we can explore these more enriched features to build the topic tracking model using a subset tree kernel(important paper cited here)

Kt(T1, T2)

3.3 Kernel Composition

The composition is performed by linear combination as follows:

K(x1, x2) =α · Kl(V1, V2) + β · Ks(S1, S2) + γ · Kt(T1, T2), and α + β + γ = 1

4 Evaluation

5 Conclusion




1、文章要解决的问题是dialog topic tracking,即需要判断对话的主题是否发生了改变

2、现有研究的缺点是,他们仅应用了对话上下文的信息,没有融合进领域的知识,于是这篇文章希望提出composite kernel来融合领域知识


1) Fundamental Features,抽取自对话本身以及语言学的处理;

2) History Sequence Kernel,这组kernel使用与当前对话cosine距离最接近的维基百科中的词条序号序列来表征对话历史,最后提出了一个公式来计算两个维基词条序列的相似度;

3) Domain Context Tree Kernel,针对每个对话来构建一棵领域上下文树,使用阈值来筛选相近词条来构建这棵树,最后使用subset tree kernel来计算树的相似度



6、两个关键点:1) 历史序列的相似度计算;2) 领域知识树的构建方法和相似度计算。这两个关键点可以留作扩展阅读

Leave a Reply