Goldberg, Paul W. (2001) Learning fixed-dimension linear thresholds from fragmented data. Information and Computation, Volume 171 (Number 1). pp. 98-122. doi:10.1006/inco.2001.3059 ISSN 0890-5401.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

We investigate PAC-leaming in a situation in which examples (consisting of an input vector and 0/1 label) have some of the components of the input vector concealed from the learner. This is a special case of restricted focus of attention (RFA) learning. Our interest here is in 1-RFA learning, where only a single component of an input vector is given, for each example. We argue that 1-RFA learning merits special consideration within the wider field of RFA learning. It is the most restrictive form of RFA learning (so that positive results apply in general), and it models a ty-pe of "data fusion" scenario, where we have sets of observations from a number of separate sensors, but these sensors are uncorrelated sources. within this setting we study the well-known class of linear threshold functions, the characteristic functions of Euclidean half-spaces. The sample complexity (i.e., sample-size requirement as a function of the parameters) of this learning problem is affected by the input distribution. We show that the sample complexity is always finite, for any given input distribution, but we also exhibit methods for defining "bad" input distributions for which the sample complexity can grow arbitrarily fast. We identify fairly general sufficient conditions for an input distribution to give rise to sample complexity that is polynomial in the PAC parameters epsilon -1 and delta -1. We give an algorithm whose sample complexity is polynomial in these parameters and the dimension (number of input components), for input distributions that satisfy our conditions. The run-time is polynomial in epsilon -1 and delta -1 provided that the dimension is any constant. We show how to adapt the algorithm to handle uniform misclassification noise.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title:	Information and Computation
Publisher:	Academic Press
ISSN:	0890-5401
Official Date:	25 November 2001
Dates:	Date Event 25 November 2001 Published
Volume:	Volume 171
Number:	Number 1
Number of Pages:	25
Page Range:	pp. 98-122
DOI:	10.1006/inco.2001.3059
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item