패리티 학습
Parity learning패리티 학습은 기계 학습의 문제다.이 문제를 해결하는 알고리즘은 일부 샘플(x, ƒ(x))과 ƒ이 일부 고정된 위치에서 비트 패리티를 계산한다는 확신이 주어진 경우 함수 ƒ을 찾아야 한다.샘플은 입력에 대한 일부 분포를 사용하여 생성된다.알고리즘에 충분한 수의 표본(너무 치우치지 않은 분포로부터)이 제공된다면 가우스 제거를 사용하여 문제를 해결하기가 쉽다.
노이즈가 있는 버전("노이즈가 있는 학습 패리티")
LPN(Learning Parity with Noise)에서 샘플은 일부 오류를 포함할 수 있다.샘플(x, ƒ(x)) 대신 알고리즘이 (x, y)와 함께 제공되며, 여기서 랜덤 부울 { }
패리티 학습 문제의 시끄러운 버전은 어려울 것으로 추측된다.[1]
참고 항목
참조
- ^ Wasserman, Hal; Kalai, Adam; Blum, Avrim (2000-10-15). "Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model". arXiv:cs/0010022.
- Avrim Blum, Adam Kalai, Hal Wasserman, "Noise-tolant learning, parametic problem and statistical querm model", J. ACM 50, no. 4번 (2003): 506–519.
- Adam Tauman Kalai, Yishay Mansour, Elad Verbin은 제 40회 ACM 이론 심포지엄 진행(Victoria, British Columbia, Canada: ACM, 2008), 629–638, http://portal.acm.org/citation.cfm?id=1374466에서 "불가독성 부스팅 및 패리티 학습에 대하여"를 발표했다.
- 오드 레게브(Oed Regev), "오류, 무작위 선형 코드 및 암호학을 이용한 학습"은 계산 이론에 관한 30개 연례 ACM 심포지엄(Baltimore, MD, USA: ACM, 2005), 84–93, http://portal.acm.org/citation.cfm?id=1060590.1060603에서 확인할 수 있다.
