Parity learning

Parity learning is a problem in machine learning. An algorithm that solves this problem must find a function ƒ, given some samples (x, ƒ(x)) and the assurance that ƒ computes the parity of bits at some fixed locations. The samples are generated using some distribution over the input. The problem is easy to solve using Gaussian elimination provided that a sufficient number of samples (from a distribution which is not too skewed) are provided to the algorithm.

Noisy version ("Learning Parity with Noise")

In Learning Parity with Noise (LPN), the samples may contain some error. Instead of samples (x, ƒ(x)), the algorithm is provided with (x, y), where for random boolean

The noisy version of the parity learning problem is conjectured to be hard[1]

gollark: Just iterate over all possible strings and look for the most problemy ones.
gollark: Oh yes, I'll just do a 1729-dimensional Fourier transform on this 8051 to multiply these integers
gollark: In any case, the asymptotically-fastest multiplication algorithms are worse for any problem which fits into the universe.
gollark: Just take `x << 3 + x << 1` or something like that, unless it has something faster; you don't need some ultrahyperfast algorithm.
gollark: What? It's multiplication by a constant. This is stupid.

See also

References
  1. Wasserman, Hal; Kalai, Adam; Blum, Avrim (2000-10-15). "Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model". arXiv:cs/0010022.
  • Avrim Blum, Adam Kalai, and Hal Wasserman, “Noise-tolerant learning, the parity problem, and the statistical query model,” J. ACM 50, no. 4 (2003): 506–519.
  • Adam Tauman Kalai, Yishay Mansour, and Elad Verbin, “On agnostic boosting and parity learning,” in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 629–638, http://portal.acm.org/citation.cfm?id=1374466.
  • Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84–93, http://portal.acm.org/citation.cfm?id=1060590.1060603.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.