A theory of quasi-static object discovery
Brandon Sanders, Randal C. Nelson · 2005
Discovery (OD) is the problem of grouping all observations springing from a single object without including any observations generated by other objects. In this dissertation we ignore spatial information and examine the utility and limitations of temporal information alone for OD. We show that under many real-world situations, time rather than space provides the most reliable information from which to discover objects. This dissertation introduces the Quasi-static World Model in which all change is instantaneous; objects do not move from location to location, rather they instantaneously materialize in one location and then later instantaneously vanish from that exact same location. The Quasi-static World Model is simple enough to be theoretically treatable and yet rich enough to allow direct implementation of Object Discoverers with good real-world performance. We discuss the implementation of two different systems that use the Quasi-static World Model to discover objects. The first is a deterministic batch-mode discoverer that illustrates how each sensel's observation history may be successfully modeled by a visage DAG hypothesis while the entire global history is well modeled by a global schedule containing object materialization and vanishment events. Using this system we show that given a global schedule and a visage DAG, our quasi-static labeling algorithm provides the maximally informative mapping from observations to the objects from which they could possibly stem. The second system adds a particle filtering framework to the first in order to transform it into an online probabilistic discoverer. The online probabilistic discoverer employs a feedforward pathway that exponentially enumerates all global schedules and visage DAGs that are consistent with the pre-filtered observations. Feedback between the late stage global schedule hypotheses and early stage visage DAG hypotheses is used to limit the exponential explosion of the enumerated hypothesis spaces. The Minimum Description Length (MDL) principle provides a robust metric for model selection and is employed to evaluate the competing hypotheses and prune those that are least likely given the observations.