Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Learning fixed-dimension linear thresholds from fragmented data

Tools
- Tools
+ Tools

Goldberg, Paul W. (1999) Learning fixed-dimension linear thresholds from fragmented data. University of Warwick. Department of Computer Science. (Computer science research report). (Unpublished)

[img]
Preview
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-362.pdf - Requires a PDF viewer.

Download (429Kb) | Preview

Request Changes to record.

Abstract

We investigate PAC-learning 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 typical "datafusion" 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 e-1 and d-1. We give an algorithm (using an empirical e-cover) whose sample complexity is polynomial in these parameters and the dimension (number of inputs), for input distributions that satisfy our conditions. The runtime is polynomial in e-1 and d-1 provided that the dimension is any constant. We show how to adapt the algorithm to handle uniform misclassification noise.

Item Type: Report
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Supervised learning (Machine learning)
Series Name: Computer science research report
Publisher: University of Warwick. Department of Computer Science
Official Date: 10 September 1999
Dates:
DateEvent
10 September 1999Completion
Number: Number 362
DOI: CS-RR-362
Institution: University of Warwick
Theses Department: Department of Computer Science
Status: Not Peer Reviewed
Publication Status: Unpublished
Funder: European Strategic Programme of Research and Development in Information Technology (ESPRIT)
Grant number: 20244 (ESPRIT)
Related URLs:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us