Absolute Versus Probabilistic Classification in a Logical Setting Authors: Sanjay Jain, Eric Martin, and Frank Stephan Source: Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings, (Sanjay Jain, Hans Ulrich Simon and Etsuji Tomita, Eds.), Lecture Notes in Artificial Intelligence 3734, pp. 327 - 342, Springer 2005. Abstract. Given a set of logical structures, or possible worlds, a set of logical formulas, or possible data, and a logical formula φ, we consider the classification problem of determining in the limit and almost always correctly whether a possible world satisfies φ, from a complete enumeration of the possible data that are true in . One interpretation of almost always correctly is that the classification might be wrong on a set of possible worlds of measure 0, w.r.t. some natural probability distribution over the set of possible worlds. Another interpretation is that the classifier is only required to classify a set of possible worlds of measure 1, without having to produce any claim in the limit on the truth of φ in the members of the complement of in . We compare these notions with absolute classification of w.r.t. a formula that is almost always equivalent to φ , hence investigate whether the set of possible worlds on which the classification is correct is definable. Finally, in the spirit of the kind of computations considered in Logic programming, we address the issue of computing almost correctly in the limit witnesses to leading existentially quantified variables in existential formulas. ©Copyright 2005, Springer