12th Annual Conference of the International Speech Communication Association

Florence, Italy
August 27-31. 2011

Determining what Questions to Ask, with the Help of Spectral Graph Theory

Abe Kazemzadeh, Sungbok Lee, Panayiotis G. Georgiou, Shrikanth Narayanan

University of Southern California, USA

This paper considers questions and the objects being asked about to be a graph and formulates the knowledge goal of a questionasking 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 eigenvalues of a graph Laplacian of 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.

Full Paper

Bibliographic reference.  Kazemzadeh, Abe / Lee, Sungbok / Georgiou, Panayiotis G. / Narayanan, Shrikanth (2011): "Determining what questions to ask, with the help of spectral graph theory", In INTERSPEECH-2011, 2053-2056.