• DocumentCode
    1034479
  • Title

    On the sample complexity of PAC learning half-spaces against the uniform distribution

  • Author

    Long, Philip M.

  • Author_Institution
    Res. Triangle Inst., Research Triangle Park, NC, USA
  • Volume
    6
  • Issue
    6
  • fYear
    1995
  • fDate
    11/1/1995 12:00:00 AM
  • Firstpage
    1556
  • Lastpage
    1559
  • Abstract
    We prove an Ω(d/ε+1/εlog1/δ) lower bound on the PAC (probably approximately correct) learning sample complexity of learning half-spaces against the uniform distribution on the unit ball in Rd
  • Keywords
    computational complexity; learning (artificial intelligence); neural nets; probability; PAC learning; half-spaces; lower bound; probability distribution; probably approximately correct learning; sample complexity; Discrete wavelet transforms; Feedforward neural networks; Information analysis; Information processing; Network synthesis; Neural networks; Notice of Violation; Time frequency analysis; Wavelet analysis; Wavelet transforms;
  • fLanguage
    English
  • Journal_Title
    Neural Networks, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    1045-9227
  • Type

    jour

  • DOI
    10.1109/72.471352
  • Filename
    471352
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1034479