Anytime Inference in Valuation Algebras

Abstract

The novel contribution of this work is the construction of anytime algorithms in a generic framework, which automatically gives us instantiations in many useful domains. We also show that semiring induced valuation algebras, an important subclass of valuation algebras are amenable to anytime inference. Anytime inference, and inference algorithms in general have been a well-researched area in the last few decades. Inference is an important component in most pattern recognition and machine learning algorithms; it also shares theoretical connections with other branches of computer science like theorem-proving. Anytime inference is important in applications with limited space, for efficiency reasons, such as in continuous learning and robotics. In this article we construct an anytime inference algorithm based on principles introduced in the theory of generic inference; and in particular, extending the work done on ordered valuation algebras.