PAC Learning with Generalized Samples and an Application to Stochastic Geometry

Sanjeev R. Kulkarni; Sanjoy K. Mitter; John N. Tsitsiklis; Ofer Zeitouni

doi:10.1109/34.232080

PAC Learning with Generalized Samples and an Application to Stochastic Geometry

Sanjeev R. Kulkarni, Sanjoy K. Mitter, John N. Tsitsiklis, Ofer Zeitouni

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

In this paper we introduce an extension of the standard probably approximately correct (PAC) learning model, which allows the use of generalized samples. We view a generalized sample as a pair consisting of a functional on the concept class together with the value obtained by the functional operating on the unknown concept. It appears that this model can be applied to a number of problems in signal processing and geometric reconstruction to provide sample size bounds under a PAC criterion. We consider a specific application of the generalized model to a problem of curve reconstruction and discuss some connections with a result from stochastic geometry.

Original language	English (US)
Pages (from-to)	933-942
Number of pages	10
Journal	IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume	15
Issue number	9
DOIs	https://doi.org/10.1109/34.232080
State	Published - Sep 1993

All Science Journal Classification (ASJC) codes

Software
Computer Vision and Pattern Recognition
Computational Theory and Mathematics
Artificial Intelligence
Applied Mathematics

Keywords

Curves
PAC
generalized samples
learning
model
stochastic geometry

Access to Document

10.1109/34.232080

Cite this

@article{ce0185a78e7d42bcac922bd3c1be52cf,

title = "PAC Learning with Generalized Samples and an Application to Stochastic Geometry",

abstract = "In this paper we introduce an extension of the standard probably approximately correct (PAC) learning model, which allows the use of generalized samples. We view a generalized sample as a pair consisting of a functional on the concept class together with the value obtained by the functional operating on the unknown concept. It appears that this model can be applied to a number of problems in signal processing and geometric reconstruction to provide sample size bounds under a PAC criterion. We consider a specific application of the generalized model to a problem of curve reconstruction and discuss some connections with a result from stochastic geometry.",

keywords = "Curves, PAC, generalized samples, learning, model, stochastic geometry",

author = "Kulkarni, {Sanjeev R.} and Mitter, {Sanjoy K.} and Tsitsiklis, {John N.} and Ofer Zeitouni",

note = "Funding Information: Manuscript received August 5, 1991; revised June 29, 1992. This work was supported by the US. Army Research Office under Contract D N 3 - 8 6 - K - 0171, by the Department of the Navy under Air Force Contract F19628-90-C-0002, by the National Science Foundation under contract ECS-8552419, and by the Air Force under contract AFOSR-91-0368. Recommended for acceptance by Associate Editor T. Dean.",

year = "1993",

month = sep,

doi = "10.1109/34.232080",

language = "English (US)",

volume = "15",

pages = "933--942",

journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",

issn = "0162-8828",

publisher = "IEEE Computer Society",

number = "9",

}

TY - JOUR

T1 - PAC Learning with Generalized Samples and an Application to Stochastic Geometry

AU - Kulkarni, Sanjeev R.

AU - Mitter, Sanjoy K.

AU - Tsitsiklis, John N.

AU - Zeitouni, Ofer

N1 - Funding Information: Manuscript received August 5, 1991; revised June 29, 1992. This work was supported by the US. Army Research Office under Contract D N 3 - 8 6 - K - 0171, by the Department of the Navy under Air Force Contract F19628-90-C-0002, by the National Science Foundation under contract ECS-8552419, and by the Air Force under contract AFOSR-91-0368. Recommended for acceptance by Associate Editor T. Dean.

PY - 1993/9

Y1 - 1993/9

N2 - In this paper we introduce an extension of the standard probably approximately correct (PAC) learning model, which allows the use of generalized samples. We view a generalized sample as a pair consisting of a functional on the concept class together with the value obtained by the functional operating on the unknown concept. It appears that this model can be applied to a number of problems in signal processing and geometric reconstruction to provide sample size bounds under a PAC criterion. We consider a specific application of the generalized model to a problem of curve reconstruction and discuss some connections with a result from stochastic geometry.

AB - In this paper we introduce an extension of the standard probably approximately correct (PAC) learning model, which allows the use of generalized samples. We view a generalized sample as a pair consisting of a functional on the concept class together with the value obtained by the functional operating on the unknown concept. It appears that this model can be applied to a number of problems in signal processing and geometric reconstruction to provide sample size bounds under a PAC criterion. We consider a specific application of the generalized model to a problem of curve reconstruction and discuss some connections with a result from stochastic geometry.

KW - Curves

KW - PAC

KW - generalized samples

KW - learning

KW - model

KW - stochastic geometry

UR - http://www.scopus.com/inward/record.url?scp=0027656678&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027656678&partnerID=8YFLogxK

U2 - 10.1109/34.232080

DO - 10.1109/34.232080

M3 - Article

AN - SCOPUS:0027656678

SN - 0162-8828

VL - 15

SP - 933

EP - 942

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

IS - 9

ER -

PAC Learning with Generalized Samples and an Application to Stochastic Geometry

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this