奇偶性学习

奇偶性学习是机器学习中的一个问题。解决这个问题的算法必须找到一个函数ƒ，给定一些样本（x，ƒ(x)），并保证ƒ能计算一些固定位置的比特的奇偶性。这些样本是通过对输入的某种分布产生的。这个问题很容易用高斯消除法解决，只要向算法提供足够数量的样本（来自一个不太偏斜的分布）。有噪声的版本（带噪声的学习奇偶性）在带噪声的学习奇偶性（LPN）中，样本可能包含一些错误。

算法得到的不是样本（x,ƒ(x)），而是（x,y），其中的随机布尔值{displaystylebin{0,1}}中的随机布尔值{displaystyley={begin{cases}f(x),&{text{if}}b1-f(x),&{text{otherwise}}end{cases}}}噪声版的奇偶性学习问题被猜测为是困难的。