On one-sided versus two-sided classification
type: Item
instance of: scholarly article
title: On one-sided versus two-sided classification
zbMATH Open document ID: 1054.68076
author: Frank Stephan
published in: Archive for Mathematical Logic
publication date: 2003-09-16T00:00:00Z
review text: A classifier is an algorithm that reads initial segments of the characteristic function of a set and, for each such segment, outputs \(1\) or \(0\). A class of sets \(A\) is one-sided (classifiable) if there exists a classifier that on the initial segments of \(A\) converges to \(1\) if and only if \(A\) is in the class. A class of sets \(A\) is two-sided (classifiable) if there exists a classifier that on the initial segments of \(A\) converges to \(1\) if \(A\) is in the class and to \(0\) if \(A\) is not in the class. These concepts play an important role in computational learning theory. The paper undertakes a detailed analysis of one-sided and two-sided classes. We list here several results: (1) there is a one-sided infinite class which has no infinite two-sided class; (2) there are one-sided classes which are not two-sided relative to any oracle; (3) (the Turing complexity of a class is by definition the set of all oracles which allow a two-sided classifier for the class) there is a one-sided class with a non-recursive degree. The paper investigates different notions of reductions and completeness for classes and also the effective measurability of one-sided and two-sided classes.
reviewed by: Marius Zimand
Mathematics Subject Classification ID: 68Q32
Mathematics Subject Classification ID: 03D28
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 1982443
zbMATH Keywords: inductive inference
zbMATH Keywords: classifier
zbMATH Keywords: Turing degrees
zbMATH Keywords: computational learning theory
MaRDI profile type: Publication
full work available at URL: s001530100083
OpenAlex ID: W2065277885
DOI: 10.1007/S001530100083
Recommended article: Q3093184
Recommended article: PAC-learning in the presence of one-sided classification~noise
Recommended article: One-Sided Cross-Validation
Recommended article: Q4738922
description: scientific article; zbMATH DE number 1982443