2 Структура обучения PAC (стр. 20 21)

Пример 2.4 формула k-терминальной ДНФ

Формула дизъюнктивной нормальной формы (ДНФ) — это формула дизъюнкции нескольких терминов, каждый из которых является конъюнкцией логических литералов. $k$ Термин ДНФ определяется выражением $k$ Формула ДНФ для дизъюнктивного определения терминов, каждый термин определяется не более чем $n$ Булев литерал. Следовательно, для $к=2$ и $п=3$ , пример k-членной ДНФ: $(x_1∧ \overline x_2∧ x_3)∨ (\overline x_1∧ x_3)$ .
$k$ член формулы ДНФ $C$ Являются ли классы PAC изучаемыми? Мощность класса $3^{nk}$ мощности, так как каждый член не более $n$ конъюнкцию переменных и имеют $3^n$ такое соединение, как было замечено ранее. набор гипотез $H$ должен содержать $C$ для достижения согласованности, поэтому $|Н|≥ 3^{нк}$ . Теорема 2.1 дает следующую оценку сложности выборки:

m\ge\frac{1}{\epsilon}\big((log3)nk+log\frac{1}{δ}\big),(2.12)

Это полиномиальное. Однако можно показать, что проблема обучения k-членной ДНФ $RP$ середина, $RP$ это класс сложных задач, которые позволяют решать стохастические решения за полиномиальное время. Следовательно, если $RP=NP$ , в противном случае проблема неразрешима с вычислительной точки зрения, что обычно считается не так. Следовательно, хотя размер выборки, необходимый для изучения формулировки k-терминальной ДНФ, является только полиномиальным, если только $RP=NP$ , иначе эффективное обучение таких ПАК невозможно.

Пример 2.5 Формула k-CNF

Формула конъюнктивной нормальной формы (CNF) представляет собой конъюнкцию дизъюнкций. Формула k-CNF: $T_1∧ ... ∧T_j$ выражения вида произвольной длины $j∈N$ , и каждый терм представляет собой дизъюнкт не более чем k булевых свойств. Задача изучения формулы k-CNF может быть сведена к проблеме изучения связей булевых литералов, которая, как упоминалось ранее, является PAC-обучаемым классом понятий. Для этого просто поместите каждый элемент $T_i$ Просто свяжите его с новой переменной. Затем это можно сделать с помощью следующей биекции:

a_i(x_i)∨...∨a_i(x_n)\стрелка вправо Y_{a_i(x_i),...,a_i(x_n)}, (2.13)

В формуле $а_я (х_j)$ выраженный в $T_i$ пара предметов $x_i$ назначение. Это упрощение обучения PAC для логических литеральных соединений может повлиять на исходное распределение, но это не проблема, поскольку в структуре PAC не делается никаких предположений о распределении. Следовательно, обучаемость PAC булевой литеральной связи подразумевает обучаемость PAC формулировки k-CNF.
Однако это неожиданный результат, поскольку любая k-членная формула ДНФ может быть записана как формула k-КНФ. Фактически, используя ассоциативность, k-членная ДНФ может быть переписана как формула k-CNF:

\bigvee ^k_{i=1}a_i(x_i)\wedge...\wedge a_i(x_n)=\bigwedge ^n_{i_1,...,i_{k}=1}a_1(x_{i_1})\vee...\vee a_k(x_{i_k}).

Чтобы проиллюстрировать это переписывание в конкретном случае, обратите внимание, например, на

(u_1\wedge u_2\wedge u_3)\vee (v_1\wedge v_2\wedge v_3)=\bigvee ^3_{i,j=1}(u_i\vee v_j)

Однако, как мы видели ранее, формулировка DNF с k-терминами не является действительным обучаемым PAC! Чем можно объяснить это кажущееся несоответствие? Заметим, что количество новых переменных, необходимых для записи k-членной ДНФ в виде формулы k-КНФ с помощью только что описанного преобразования, экспоненциально по k, $O(nk)$ . Разница заключается в размере представления концепта. Формулировка DNF с k-членом может быть экспоненциально более компактным представлением, и если требуется полином временной сложности такого размера, эффективное обучение PAC становится невозможным. Таким образом, этот очевидный парадокс включает в себя ключевые аспекты обучения PAC, в том числе стоимость представления концепции и выбор наборов гипотез.