Paritetsinlärning

Paritetsinlärning är ett problem inom maskininlärning . En algoritm som löser detta problem måste hitta en funktion ƒ , givet några sampel ( x , ƒ ( x )) och försäkran om att ƒ beräknar pariteten för bitar på vissa fasta platser. Sampeln genereras med hjälp av viss fördelning över indata. Problemet är lätt att lösa med Gaussisk eliminering förutsatt att ett tillräckligt antal sampel (från en fördelning som inte är alltför skev) tillhandahålls till algoritmen.

Noisy version ("Learning Parity with Noise")

I Learning Parity with Noise (LPN) kan proverna innehålla något fel. Istället för sampel ( x , ƒ ( x )) är algoritmen försedd med ( x , y ), där för slumpmässigt booleskt $b\in \{0,1\}$

$y={\begin{cases}f(x),&{\text{if }}b\\1-f(x) ),&{\text{annars}}\end{cases}}$

Den bullriga versionen av paritetsinlärningsproblemet antas vara svår.

Se även

• Lärande med fel

• Avrim Blum, Adam Kalai och Hal Wasserman, "Noise-tolerant learning, the parity problem, and the statistic query model," J. ACM 50, nr. 4 (2003): 506–519.
• Adam Tauman Kalai, Yishay Mansour och Elad Verbin, "On agnostic boosting and parity learning," i Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Kanada: ACM, 2008), 629–638, http ://portal.acm.org/citation.cfm?id=1374466 .
• Oded Regev, "On lattices, learning with errors, random linear codes, and cryptography," i Proceedings of the trettiosjunde årliga ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84–93, http ://portal.acm.org/citation.cfm?id=1060590.1060603 .