Uczenie się parytetu

Uczenie się parzystości jest problemem w uczeniu maszynowym . Algorytm, który rozwiązuje ten problem, musi znaleźć funkcję ƒ , mając dane próbki ( x , ƒ ( x )) i pewność, że ƒ oblicza parzystość bitów w pewnych ustalonych miejscach. Próbki są generowane przy użyciu pewnego rozkładu danych wejściowych. Problem jest łatwy do rozwiązania za pomocą eliminacji Gaussa , pod warunkiem, że do algorytmu zostanie dostarczona odpowiednia liczba próbek (z rozkładu, który nie jest zbyt skośny).

Wersja hałaśliwa („Learning Parity with Noise”)

W przypadku uczenia się parzystości z szumem (LPN) próbki mogą zawierać pewne błędy. Zamiast próbek ( x , ƒ ( x )) algorytm jest wyposażony w ( x , y ), gdzie dla losowej wartości logicznej ${\ Displaystyle b \ in \ {0,1 \}}$

${\ Displaystyle y = {\ rozpocząć {przypadki} f (x) i {\ tekst {jeśli}} b \\ 1-f (x ),&{\text{inaczej}}\end{przypadki}}}$

Przypuszcza się, że hałaśliwa wersja problemu uczenia się z parzystością jest trudna.

Zobacz też

• Nauka z błędami

• Avrim Blum, Adam Kalai i Hal Wasserman, „Uczenie się odporne na hałas, problem parzystości i model zapytań statystycznych”, J. ACM 50, no. 4 (2003): 506–519.
• Adam Tauman Kalai, Yishay Mansour i Elad Verbin, „On agnostic boosting and parity learning”, w Proceedings of 40th Annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 629–638, http ://portal.acm.org/citation.cfm?id=1374466 .
• Oded Regev, „On kraty, uczenie się z błędami, losowe kody liniowe i kryptografia”, w Proceedings of the 37th Annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84–93, http ://portal.acm.org/citation.cfm?id=1060590.1060603 .