Please use this identifier to cite or link to this item:
Title: Absolute versus probabilistic classification in a logical setting
Authors: Jain, S. 
Martin, E.
Stephan, F. 
Keywords: Absolute classification
Inductive inference
Probabilistic classification
Issue Date: 2008
Citation: Jain, S., Martin, E., Stephan, F. (2008). Absolute versus probabilistic classification in a logical setting. Theoretical Computer Science 397 (1-3) : 114-128. ScholarBank@NUS Repository.
Abstract: Suppose we are given a set W of logical structures, or possible worlds, a set of logical formulas called possible data and a logical formula φ. We then consider the classification problem of determining in the limit and almost always correctly whether a possible world M satisfies φ, from a complete enumeration of the possible data that are true in M. One interpretation of almost always correctly is that the classification might be wrong on a set of possible worlds of measure 0, with respect to some natural probability distribution over the set of possible worlds. Another interpretation is that the classifier is only required to classify a set W ′ of possible worlds of measure 1, without having to produce any claim in the limit on the truth of φ for the members of the complement of W ′ in W. We compare these notions with absolute classification of W with respect to a formula that is almost always equivalent to φ in W, hence we investigate whether the set of possible worlds on which the classification is correct is definable. We mainly work with the probability distribution that corresponds to the standard measure on the Cantor space, but we also consider an alternative probability distribution proposed by Solomonoff and contrast it with the former. 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. © 2008 Elsevier Ltd. All rights reserved.
Source Title: Theoretical Computer Science
ISSN: 03043975
DOI: 10.1016/j.tcs.2008.02.026
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.