Aprendizaje en paridad

El aprendizaje de paridad es un problema en el aprendizaje automático . Un algoritmo que resuelva este problema debe encontrar una función ƒ , dadas algunas muestras ( x ,  ƒ ( x )) y la seguridad de que ƒ calcula la paridad de bits en algunas ubicaciones fijas. Las muestras se generan utilizando alguna distribución sobre la entrada. El problema es fácil de resolver utilizando la eliminación gaussiana siempre que se proporcione al algoritmo una cantidad suficiente de muestras (de una distribución que no esté demasiado sesgada).

Versión ruidosa ("Aprender la paridad con el ruido")

En el aprendizaje de paridad con ruido (LPN), las muestras pueden contener algún error. En lugar de muestras ( x ,  ƒ ( x )), el algoritmo se proporciona con ( x ,  y ), donde para valores booleanos aleatorios ${\displaystyle b\in \{0,1\}}$

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

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

Véase también

• Aprendiendo con errores

Referencias

1. Wasserman, Hal; Kalai, Adam; Blum, Avrim (15 de octubre de 2000). "Aprendizaje tolerante al ruido, el problema de la paridad y el modelo de consulta estadística". arXiv : cs/0010022 .
2. Pietrzak, Krzysztof (2012). "Criptografía a partir de la paridad de aprendizaje con ruido" (PDF) . Conferencia internacional sobre tendencias actuales en teoría y práctica de la informática : 99-114. doi :10.1007/978-3-642-27660-6_9.

• 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, no. 4 (2003): 506–519.
• Adam Tauman Kalai, Yishay Mansour y Elad Verbin, “Sobre el impulso agnóstico y el aprendizaje paritario”, 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 redes, 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.