Паритетное обучение

Обучение на четность — проблема машинного обучения . Алгоритм, который решает эту проблему, должен найти функцию ƒ по некоторым выборкам ( x , ƒ ( x )) и уверенности в том, что ƒ вычисляет четность битов в некоторых фиксированных местах. Выборки генерируются с использованием некоторого распределения по входным данным. Проблему легко решить с помощью метода исключения Гаусса при условии, что в алгоритм предоставлено достаточное количество выборок (из не слишком искаженного распределения).

Шумная версия («Изучение четности с шумом»)

При обучении четности с шумом (LPN) выборки могут содержать некоторую ошибку. Вместо выборок ( x , ƒ ( x ) ) в алгоритме используются ( x , y ), где для случайных логических значений $b\in \{0,1\}$

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

Предполагается, что шумная версия проблемы обучения четности сложна.

См. также

• Обучение с ошибками

Ссылки

• Аврим Блюм, Адам Калаи и Хэл Вассерман, «Обучение, устойчивое к шуму, проблема четности и модель статистических запросов», J. ACM 50, вып. 4 (2003): 506–519.
• Адам Тауман Калаи, Ишай Мансур и Элад Вербин, «Об агностическом повышении и обучении по четности», в Трудах 40-го ежегодного симпозиума ACM по теории вычислений (Виктория, Британская Колумбия, Канада: ACM, 2008), 629–638, http ://portal.acm.org/citation.cfm?id=1374466 .
• Одед Регев, «О решетках, обучении с ошибками, случайных линейных кодах и криптографии», в материалах тридцать седьмого ежегодного симпозиума ACM по теории вычислений (Балтимор, Мэриленд, США: ACM, 2005), 84–93, http. ://portal.acm.org/citation.cfm?id=1060590.1060603 .