Managing Uncertainty in Text To Sketch

Text to sketch is a class of problems that involves spatial reasoning and geolocation using textual descriptions. Generally speaking, can we find locations on a map that are described or referred to in human-generated text? Our research involves expanding the text to sketch challenge to produce temporally extended sketches (annotated maps of locations and routes) of an entity's movements and locations over time based on textual accounts.

Text to sketch for tracking problems is a difficult challenge because there are many sources of uncertainty inherent to the problem. Computers are notoriously bad at processing natural (human) language, and struggle with its many ambiguaties: from part of speech tagging, to parsing, to polysemy and reference resolution. A computer is rarely completely certain of the meaning of human language. Similarly, textual descriptions of movements and landmarks are also by nature often spatially ambiguous or vague; humans use vast commonsense and contextual knowledge to know which coffee shop a conversation partner is referring to when she says, "the coffee shop". Automated systems may have a database containing known locations of many coffee shops, yet require a reasoning mechanism for either selecting the correct one or its representing uncertainty about the actual coffee shop being described.

Our approach to managing uncertainty combines off-the-shelf natural language tools[1] for syntatic processing with an in-house semantic interpretation engine and a framework for model estimation known as a particle filter as a probabilistic framework. Our particle filter implementation is based on adaptations of that technique to mobile robot localization[2] and allows for the generation of hypotheses, sketches, and their likelihoods.

  • [1] Marie-Catherine de Marneffe, Bill MacCartney and Christopher D. Manning. Generating Typed Dependency Parses from Phrase Structure Parses. In LREC 2006.
  • [2] Austin I. Eliazar and Ronald Parr. Hierarchical Linear/Constant Time SLAM using Particle Filters for Dense Maps. In Advances in Neural Information Processing Systems (NIPS-19) 2005.