Paper Info
Title
Determining What Questions To Ask, With The Help Of Spectral Graph Theory
Abstract
This paper considers questions and the objects being asked about to be a graph and formulates the knowledge goal of a question-asking agent in terms of connecting this graph. The game of twenty questions can be thought of as a testbed of such a question-asking agent's knowledge. If the agent's knowledge of the domain were completely specified, the goal of question-asking would be to find the answer as quickly as possible and could follow a decision tree approach to narrow down the candidate answers. However, if the agent's knowledge is incomplete, it must have a secondary goal for the questions it plans: to complete its knowledge. We claim that this secondary goal of a question asking agent can be formulated in terms of spectral graph theory. In particular, disconnected portions of the graph must be connected in a principled way. We show how the eigen-values of a graph Laplacian of the the question-object adjacency graph can identify whether a set of knowledge contains disconnected components and the zero elements of the powers of the question-object adjacency graph provide a way to identify these questions. We illustrate the approach using an emotion description task.
Year
Venue
Keywords
2011
12TH ANNUAL CONFERENCE OF THE INTERNATIONAL SPEECH COMMUNICATION ASSOCIATION 2011 (INTERSPEECH 2011), VOLS 1-5
dialog agents, question-asking, graph theory, emotions
Field
DocType
Citations 
Adjacency list,Laplacian matrix,Graph,Decision tree,Ask price,Spectral graph theory,Pattern recognition,Computer science,Testbed,Theoretical computer science,Artificial intelligence,Eigenvalues and eigenvectors
Conference
2
PageRank 
References 
Authors
0.45
6
4
Name
Order
Citations
PageRank
Abe Kazemzadeh195752.95
Sungbok Lee2139484.13
Georgiou Panayiotis342855.79
Narayanan Shrikanth45558439.23