Abstract
Recent systems for natural language understanding are strong at overcominglinguistic variability for lookup style reasoning. Yet, their accuracy dropsdramatically as the number of reasoning steps increases. We present the firstformal framework to study such empirical observations, addressing theambiguity, redundancy, incompleteness, and inaccuracy that the use of languageintroduces when representing a hidden conceptual space. Our formal model usestwo interrelated spaces: a conceptual meaning space that is unambiguous andcomplete but hidden, and a linguistic symbol space that captures a noisygrounding of the meaning space in the symbols or words of a language. We apply this framework to study the connectivity problem in undirectedgraphs---a core reasoning problem that forms the basis for more complexmulti-hop reasoning. We show that it is indeed possible to construct ahigh-quality algorithm for detecting connectivity in the (latent) meaninggraph, based on an observed noisy symbol graph, as long as the noise is belowour quantified noise level and only a few hops are needed. On the other hand,we also prove an impossibility result: if a query requires a large number(specifically, logarithmic in the size of the meaning graph) of hops, noreasoning system operating over the symbol graph is likely to recover anyuseful property of the meaning graph. This highlights a fundamental barrier fora class of reasoning problems and systems, and suggests the need to limit thedistance between the two spaces, rather than investing in multi-hop reasoningwith "many" hops.