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 agents 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 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2011
- Accession Number
- AD1158383
Entities
People
- Abe Kazemzadeh
- Panayiotis Georgiou
- Shrikanth Narayanan
- Sungbok Lee
Organizations
- University of Southern California