Aprendizaje de paridad

El aprendizaje de paridad es un problema del aprendizaje automático . Un algoritmo que resuelve este problema debe encontrar una función ƒ , dadas algunas muestras ( x , ƒ ( x )) y la garantía de que ƒ calcula la paridad de los bits en ciertas posiciones fijas. Las muestras se generan utilizando alguna distribución sobre la entrada. El problema es fácil de resolver mediante la eliminación gaussiana, siempre que se proporcione al algoritmo un número suficiente de muestras (de una distribución que no esté demasiado sesgada). 

En Learning Parity with Noise (LPN), las muestras pueden contener algún error. En lugar de muestras ( x , ƒ ( x )), el algoritmo recibe ( x , y ), donde para booleanos aleatorios  ${\displaystyle b\in \{0,1\}}$

${\displaystyle y={\begin{cases}f(x),&{\text{si }}b\\1-f(x),&{\text{en otro caso}}\end{cases}}}$

Se conjetura que la versión ruidosa del problema de aprendizaje de paridad es difícil ^{[ 1 ]} y se utiliza ampliamente en criptografía. ^{[ 2 ]}

• Aprender de los errores

• Avrim Blum, Adam Kalai y Hal Wasserman, “Aprendizaje tolerante al ruido, el problema de la paridad y el modelo de consulta estadística”, J. ACM 50, n.º 4 (2003): 506 – 519.
• Adam Tauman Kalai, Yishay Mansour y Elad Verbin, “Sobre el boosting agnóstico y el aprendizaje de paridad”, en Actas del 40.º simposio anual de la ACM sobre teoría de la computación (Victoria, Columbia Británica, Canadá: ACM, 2008), 629 – 638, http://portal.acm.org/citation.cfm?id=1374466 .
• Oded Regev, “Sobre retículos, aprendizaje con errores, códigos lineales aleatorios y criptografía”, en Actas del trigésimo séptimo simposio anual de la ACM sobre Teoría de la Computación (Baltimore, MD, EE. UU.: ACM, 2005), 84 – 93, http://portal.acm.org/citation.cfm?id=1060590.1060603 .