パリティ学習

パリティ学習は機械学習における問題です。この問題を解決するアルゴリズムは、いくつかのサンプル ( x、  ƒ ( x )) と、 ƒ がいくつかの固定位置でビットのパリティを計算するという保証を与えられた場合に、関数ƒを見つけなければなりません。サンプルは、入力に対する何らかの分布を使用して生成されます。十分な数のサンプル (あまり偏っていない分布から) がアルゴリズムに提供されていれば、 ガウス消去法を使用してこの問題を簡単に解決できます。

ノイズ付きパリティ学習（LPN）では、サンプルに多少の誤差が含まれる可能性があります。サンプル（x、  ƒ（x））の代わりに、アルゴリズムは（x、  y）を提供します。ここで、ランダムブール${\displaystyle b\in \{0,1\}}$

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

パリティ学習問題のノイズバージョンは困難であると推測されており^[1]、暗号技術で広く使用されています。^[2]

• 間違いから学ぶ

• Avrim Blum、Adam Kalai、Hal Wasserman、「ノイズ耐性学習、パリティ問題、統計クエリモデル」、J. ACM 50、第4号（2003年）：506-519。
• Adam Tauman Kalai、Yishay Mansour、Elad Verbin、「アグノスティックブースティングとパリティ学習について」、第40回ACMコンピューティング理論シンポジウム議事録（ビクトリア、ブリティッシュコロンビア、カナダ：ACM、2008年）、629-638、http://portal.acm.org/citation.cfm?id=1374466。
• Oded Regev、「格子、エラー学習、ランダム線形コード、暗号化について」、第 37 回 ACM コンピューティング理論シンポジウム議事録 (米国メリーランド州ボルチモア: ACM、2005 年)、84 ～ 93 ページ、http://portal.acm.org/citation.cfm?id=1060590.1060603。