8 Время выполнения обучения

До сих пор в книге мы рассматривали статистическую перспективу обучения, то есть сколько выборок необходимо для обучения. Другими словами, мы ориентируемся на количество информации, необходимой для обучения. Однако при рассмотрении автоматизированного обучения вычислительные ресурсы также играют важную роль в определении сложности задачи: то есть того, сколько вычислений требуется для выполнения задачи обучения. После того, как учащемуся будет предоставлено достаточное количество обучающих образцов, можно выполнить некоторые вычисления для извлечения гипотез или определения меток для данного экземпляра теста. Все эти вычислительные ресурсы имеют решающее значение для практического применения машинного обучения. Мы называем эти два типа ресурсов примерами сложности и вычислительной сложностью. В этой главе мы обратим внимание на вычислительную сложность обучения.

$\qquad$Вычислительную сложность обучения следует рассматривать в более широком контексте вычислительной сложности общих алгоритмических задач. Эта область была тщательно исследована: см., например, (Sipser 2006). Вводные комментарии, которые следуют ниже, резюмируют основные идеи общей теории, наиболее важные для нашего обсуждения.

$\qquad$Фактическое время работы алгоритма (в секундах) зависит от конкретной машины, на которой реализуется алгоритм (например, производительность машины).CPUкакая тактовая частота). Чтобы избежать зависимости от конкретной машины, принято анализировать время выполнения алгоритма в изотопическом смысле. Например, предположим, что вычислительная сложность алгоритма сортировки слиянием (сортировка списка из n элементов) равна$О (n журнал (n))$. Это означает, что мы можем реализовать алгоритм на любой машине, удовлетворяющей требованиям некоторой принятой абстрактной вычислительной модели, а фактическое время выполнения в секундах будет удовлетворять следующим требованиям: существуют константы c и$n_0$, что может зависеть от реальной машины, поэтому для$n>n_0$, сортировать любое значение в секундах$n$Время работы элемента не более$cn(log(n))$. Часто используют термин «выполнимый» или «эффективный» для расчета, который можно рассчитать по времени работы как$О (р (п))$Алгоритм выполняет несколько многофункциональных п. Обратите внимание, что этот тип анализа зависит от определения входного размера n любого экземпляра, к которому предполагается применить алгоритм. Для задач «чистого алгоритма», как описано в общей литературе по вычислительной сложности, этот размер входных данных четко определен: алгоритм получает входной экземпляр, например, список для сортировки или арифметическую операцию для вычисления, которая имеет хорошо определенный размер (например, для расчета). Для задач машинного обучения понятие размера входных данных не столь однозначно. Алгоритмы предназначены для обнаружения определенных шаблонов в наборе данных и имеют доступ только к случайной выборке этих данных.

$\qquad$Сначала мы обсудим этот вопрос и определим вычислительную сложность обучения. Для продвинутых студентов мы также предоставляем подробные формальные определения. Затем мы переходим к рассмотрению вычислительной сложности реализации правил ERM. Начнем с нескольких примеров гипотетических классов, гдеERMПравила могут быть эффективно применены, а затем рассмотрены некоторые случаи, хотя класс действительно учится эффективно, ноERMРеализация вычислительно сложна. Следовательно, сложность внедрения ERM не означает сложности обучения. Наконец, мы кратко обсудим, как показать сложность данной учебной задачи, то есть ни один алгоритм обучения не может решить ее эффективно.

8.1 Вычислительная сложность обучения

Напомним, что алгоритмы обучения имеют доступ к предметной области,$\mathcal{Z}$, гипотетический класс,$\mathcal{H}$, функция потерь и$\mathcal{Z}$по неизвестной раздаче$\mathcal{D}$Примерный набор образцов.$\эпсилон, \дельта$Алгоритм должен выводить гипотезу$h$, так что вероятность не менее$1-\delta$

$\qquad$Как упоминалось ранее, фактическое время работы алгоритма в секундах зависит от конкретной машины. Чтобы обеспечить машинно-независимый анализ, мы используем стандартные методы теории вычислительной сложности. Во-первых, мы полагаемся на понятие абстрактных машин, таких как машины Тьюринга (или машины Тьюринга над реальным (Blum, Schub, & Smalley, 1989). Во-вторых, мы анализируем значение времени работы в асимпатическом смысле. Постоянный фактор игнорируется, поэтому конкретная машина не имеет значения, если она реализует абстрактную машину. Как правило, неизотопность связана с размером входных данных алгоритма. Например, для алгоритма сортировки слиянием, упомянутого ранее, мы запустим временной анализ A Функция для количества элементов, подлежащих сортировке.

$\qquad$С точки зрения алгоритмов обучения не существует явного понятия «размер ввода». Можно определить размер входных данных как размер обучающей выборки, полученной алгоритмом, но это бессмысленно. Если мы дадим алгоритму очень большое количество примеров, намного превышающее сложность выборки задачи обучения, алгоритм может проигнорировать лишние примеры. Следовательно, больший обучающий набор не усложняет задачу обучения, и, следовательно, время работы алгоритма обучения не должно увеличиваться по мере увеличения размера обучающего набора. Точно так же мы все еще можем анализировать время выполнения как функцию естественных параметров задачи, таких как точность цели, уверенность в достижении этой точности, размерность набора доменов или сравнение некоторой меры сложность гипотетического класса с выходом алгоритма.

$\qquad$Чтобы проиллюстрировать это, рассмотрим алгоритм обучения для задачи изучения прямоугольников, выровненных по оси. Изучите конкретную проблему прямоугольников, выровненных по оси, указав$\эпсилон, \дельта$и размер пространства экземпляра. мы можем исправить$\эпсилон, \дельта$и измените размер на$г = 2, 3, 4 \cdots$определить ряд задач типа «обучения прямоугольником», мы также можем исправить это с помощью$д. \ дельта$и измените целевую точность на$\epsilon=\frac{1}{2}, \frac{1}{3}\cdots$определить другую последовательность задач «обучения прямоугольником». Конечно, можно выбрать и другие последовательности таких задач. Как только последовательность проблем зафиксирована, можно проанализировать время работы без звука как функцию переменных последовательности.

$\qquad$Прежде чем мы сможем ввести формальное определение, нам нужно рассмотреть более тонкий вопрос. Основываясь на вышеизложенном, алгоритмы обучения могут «обманывать», перекладывая вычислительную нагрузку на исходные предположения. Например, алгоритм может просто определить выходную гипотезу как функцию, которая хранит в памяти свой обучающий набор, и всякий раз, когда он получает тестовый пример$x$, он вычисляетERMгипотеза и в$x$применить его на. Обратите внимание, что в этом случае наш алгоритм имеет фиксированный результат (т. е. функцию, которую мы только что описали) и может работать за постоянное время. Однако обучение по-прежнему затруднено — теперь в выходном классификаторе реализована жесткость для получения прогнозов меток. Чтобы предотвратить этот «обман», мы требуем, чтобы выходные данные алгоритма обучения применялись для прогнозирования меток новых примеров не дольше, чем время выполнения обучения (т. е. вычисление выходного классификатора из входных обучающих примеров). В следующем подразделе продвинутые читатели могут найти формальное определение вычислительной сложности для обучения.

8.1.1 Формальные определения*

Приведенные ниже определения основаны на понятии фундаментальной абстрактной машины, которая обычно является машиной Тьюринга или машиной Тьюринга над вещественным числом. Мы будем измерять вычислительную сложность алгоритма, используя количество «операций», которые должен выполнить алгоритм. Мы предполагаем, что для любой машины, реализующей базовый абстрактный компьютер, существует константа$c$, так что любое такое "действие" сработает на автомате$c$секунд для выполнения.

Определение 8.1(Вычислительная сложность алгоритма обучения) Мы определяем сложность обучения в два этапа. Во-первых, мы рассматриваем вычислительную сложность фиксированной задачи обучения (состоящей из троек ($\mathcal{Z, H}$) и набор доменов, класс эталонной гипотезы и решение функции потерь). Затем, на втором этапе, мы рассматриваем скорость изменения этой сложности с точки зрения ряда таких задач.

1. учитывая функцию$f : (0, 1)^2 \rightarrow \mathbb N$, учебная задача$\mathcal{(Z, Н, л)}$и алгоритм обучения$\mathcal{A}$, мы говорим$\mathcal{A}$время решать учебные задачи$Из)$Если есть постоянные числа$c$, например, для каждого распределения вероятностей$\mathcal D$Превосходить$Z$, и ввод$\эпсилон,\дельта\в (0, 1)$, когда A имеет доступ к образцу i.i.d., сгенерированному$\mathcal D$

• $\mathcal A$выполнить не более$cf(\эпсилон,\дельта)$Прекратить после операции
• $\mathcal A$выход (представляющий$h_\mathcal{A}$) можно использовать для прогнозирования меток для новых примеров при выполнении не более$cf(\эпсилон,\дельта)$действовать
• $\mathcal A$Выход, вероятно, будет приблизительно правильным: то есть с вероятностью не менее$1-\delta$(более чем случайная выборка$\mathcal A$перенимать),$L_\mathcal D(h_\mathcal A)\leq min_{h^{'}\in \mathcal H} l_\mathcal D(h^{'})+\epsilon$

2. Рассмотрите ряд проблем обучения$(Z_n, \mathcal H_n, l_n)_{n=1}^\infty$, где проблема$n$по домену$Z_n$, гипотетический класс$\mathcal H_n$и функция потерь$l_n$определение. позволять$\mathcal A$быть алгоритмом обучения для решения этой формы задачи обучения. заданная функция$g : \mathbb N\times(0, 1)^2\стрелка вправо\mathbb N$,мы говорим$\mathcal A$Время выполнения предыдущей последовательности равно$O(g)$, если для всех$n, \mathcal A$Проблема решена своевременно$(Z_n,\mathcal H_n, l_n)$,в$f_n:(0,1)^2\rightarrow \mathbb N$Зависит от$f_n(\epsilon,\delta)=g(n,\epsilon,\delta)$определение.

Мы говорим, что если$\mathcal A$Время работы$O(p(n,1/\epsilon,1/\delta))$,но$\mathcal A$для многочлена$p$последовательность$(Z_n, \mathcal H_n, l_n)$является эффективным алгоритмом.

$\qquad$Из этого определения мы видим, что возможность эффективного решения общей учебной задачи зависит от того, как она разлагается на ряд конкретных учебных задач. Например, рассмотрим задачу изучения класса конечных гипотез. Как мы показали в предыдущих главах, если количество обучающих примеров$m_\mathcal H(\epsilon,\delta)=log(\mid H\mid/\delta)/\epsilon^2$лог (тогда$\mathcal H$изERMГарантия правил$(\epsilon,\delta)-обучение\mathcal{H}$). Предполагая, что оценка примерной гипотезы занимает постоянное время, ее можно реализовать за времяERMправило$O(\mid \mathcal H\mid m_{\mathcal H}(\epsilon,\delta))$через пару$\mathcal H$Проведите исчерпывающий поиск и приходите с набором размеров$m_{\mathcal H}(\epsilon,\delta)$Обучающий набор. для любого фиксированного конечного$\mathcal H$, алгоритм исчерпывающего поиска запускается несколько раз. Более того, если мы определим ряд задач, где$\mid \mathcal H_n\mid=n$, полный поиск по-прежнему считается действительным. Однако если мы определим ряд задач$\mid \mathcal H_n\mid=2^n$, то сложность выборки по-прежнему$n$несколько существительных в , но вычислительная сложность алгоритма полного перебора увеличивается с$n$растет в геометрической прогрессии (следовательно, рендеринг неэффективен).

8.2 Внедрение правил ERM

Учитывая гипотетический класс$\mathcal H$,ERM $_\mathcal H$Правила, пожалуй, самая естественная парадигма обучения. Кроме того, для задач бинарной классификации мы видим, что если обучение возможно, тоERMПравила возможны. В этом разделе мы обсудили реализацию для нескольких гипотетических классов.ERMВычислительная сложность правил.

$\qquad$Учитывая гипотетический класс,$\mathcal H$, набор доменов$Z$и функция потерь$l$,соответствующийERM $_\mathcal H$Правила можно определить как:

$\qquad\qquad$пример с ограниченным вводом$S\in Z^m$вывод о$h\in H$, чтобы свести к минимуму потерю опыта,$L_S(h)=\frac{1}{\mid S\mid}\sum_{z\in S}l(h,z)$.

$\qquad\qquad$Выполнение этого исследованияERMВремя выполнения правил для нескольких примеров обучающих задач.

8.2.1 Конечные классы

Ограничение класса гипотез конечным классом можно рассматривать как довольно мягкое ограничение. Например,$\mathcal H$Может быть набором всех предикторов, которые могут быть реализованы программой на C++, написанной до 10000 битов кода. Другими примерами полезных конечных классов являются любые гипотетические классы, которые могут быть параметризованы конечным числом параметров, и мы довольствуемся использованием конечного числа битов для представления каждого параметра, например, когда параметры, определяющие любой данный прямоугольник, определяют классы для прямоугольники с выравниванием по осям в евклидовом пространстве с некоторой ограниченной точностью$\mathbb R^d$.

$\qquad$Как мы показали в предыдущих главах, примерная сложность изучения конечных классов ограничена$m_\mathcal H(\epsilon,\delta) = clog(c|\mathcal H|/\delta)/\epsilon^c$верхний предел которого$c = 1$где достижимо и$c = 2$при невозможных обстоятельствах. Таким образом, сложность выборки$\mathcal H$Есть небольшая зависимость от размера. Взяв в качестве примера программу C++, упомянутую ранее, предполагаемая величина равна$2^{10,000}$, но сложность выборки составляет всего$c(10,000+log(c/\delta))/\epsilon^c$

$\qquad$Реализовано в ограниченных гипотетических классахERMПростой способ установить правило — выполнить исчерпывающий поиск. То есть для каждого$h\in \mathcal H$, вычисляем эмпирический риск$L_S(h)$и возвращает гипотезу, минимизирующую эмпирический риск. Предполагая, что на одном примере$l(h,z)$Оценка занимает постоянное время k, время выполнения этого полного перебора станет равным$k\mid \mathcal H\mid_m$,в$m$это размер обучающей выборки. Если мы позволим мне быть верхней границей сложности приведенных выше примеров, то время выполнения станет равным$k |\mathcal H| c log(c| \mathcal H|/\delta)/\epsilon^c$.

$\qquad$пара времени работы$\mathcal H$Линейная зависимость размера делает этот подход неэффективным (и непрактичным) для больших классов. Формально, если мы определим ряд задач$(Z_n,H_n,l_n)^\infty_{n=1}$Такой$log(|\mathcal H_n|)=n$, то метод исчерпывающего поиска дает экспоненциальное время выполнения. В примере программы на C++, если$\mathcal H_n$можно пройти до$n$Набор функций, реализованных программой на C++, написанной в битовом коде, время выполнения будет увеличиваться в геометрической прогрессии, а это означает, что метод полного перебора нецелесообразен для практического использования. На самом деле эта проблема является одной из причин, по которой мы имеем дело с другими гипотетическими классами, такими как линейные предикторы, с которыми мы столкнемся в следующей главе, а не просто сосредотачиваемся на ограниченных классах.

$\qquad$Важно понимать, что только потому, что алгоритмический подход (такой как полный перебор) неэффективен, не означает, что не существует эффективных методов.ERMвыполнить. На самом деле мы покажем, что можно эффективно выполнятьERMпример правил

8.2.2 Осесимметричные прямоугольники

позволять$\mathcal H_n$стать$\mathbb R_n$Класс оси выровненного по центру прямоугольника, т.е.

тем самым

Эффективное обучение, когда оно достижимо

Рассмотрите возможность внедрения там, где это возможноERMправило. То есть мы получаем набор$S = (x_1, y_1), \ cdots, (x_m, y_m)$например, чтобы существовал выровненный по оси прямоугольник,$h\in\mathcal H_n$,к этому концу$ч (х_я) = у_я$для всех$i$. Наша цель — найти такой выровненный по оси прямоугольник с нулевой ошибкой обучения, то есть прямоугольник, который согласуется со всеми метками выше S.

$\qquad$Позже мы докажем, что это можно сделать за время$O(nm)$. В самом деле, для каждого$i\in[n]$, настраивать$a_i =min \{ xi:(x,1)\in S\}$и$b_i = max\{ xi:(x,1)\in S\}$. Другими словами, мы положили$a_i$в виде$S$Первый из примеров Zhongzheng$i$минимальное значение координат,$b_i$в виде$S$Первый из примеров Zhongzheng$i$максимальное значение координат. Легко проверить, что сгенерированные прямоугольники не имеют ошибок обучения, и найти каждый$a_i$и$b_i$Время работы$O(m)$. Таким образом, общее время выполнения этого процесса равно$O(nm)$.

Неспособность эффективно учиться, не будучи агностиком

В агностике мы не принимаем определенные предположения$h$Метки всех примеров в обучающем наборе точно предсказаны. Поэтому наша цель найти$h$, тем самым сводя к минимуму$y_i\not= h(x_i)$количество примеров. Оказывается, что для многих распространенных гипотетических классов, включая рассматриваемый нами класс выровненных по оси прямоугольников, решение в независимой настройкеERMпроблема в том$NP-hard$(в большинстве случаев даже трудно найти некоторые$h\in\mathcal H$, погрешность которого не превышает некоторой постоянной$c>1$умноженная на минимизацию эмпирического риска при$\mathcal H$середина). То есть, если$P = NP$, иначе время работы без алгоритма равно$m$и$n$многозначных в , гарантированно найдется для этих задачERMГипотеза (Бен-Дэвид, Айрон и Лонг, 2003).

$\qquad$С другой стороны, стоит отметить, что если мы зафиксируем конкретный гипотетический класс, например, выровненные по оси прямоугольники в некотором фиксированном измерении$n$Тогда есть эффективные алгоритмы обучения для этого класса. Другими словами, существует успешный агностицизм.PACученик, в$1/\epsilon$и$1/\delta$запускать полиномы во времени (но их зависимость от размерности n не является полиномиальной).

Чтобы увидеть эту ситуацию, просмотрите наше предложение для достижимого случая.ERMвыполнение правил, из которых можно определить до$2n$Выровненный по оси прямоугольник в этом примере. Поэтому при указании размера$m$Когда тренировочный набор$2n$Выполните полный поиск по всем подмножествам обучающего набора из 3 примеров и постройте прямоугольник из каждого такого подмножества. Затем мы можем выбрать прямоугольник с наименьшим количеством ошибок обучения. Этот процесс гарантирует нахождениеERMгипотеза, а время выполнения процесса равно$м ^ {О (п)}$. Следовательно, если$n$фиксировано, то время работы является полиномом от размера выборки. Это не противоречит приведенным выше результатам твердости, потому что там мы утверждаем, что если$P=NP$Не может быть алгоритма, который$n$Зависимости также многогранны.

8.2.3 Логические соединения

Булевы союзы происходят от$\mathcal X=\{0, 1\}^n$прибыть$Y = \{0, 1\}$Отображение , которое может быть представлено в виде таблицы$x_{i_1}\bigwedge\cdots\bigwedge x_{i_k}\bigwedge\neg x_{j_1}\bigwedge\cdots\bigwedge\neg x_{j_r}$Пропозициональная формула , для некоторых показателей$i_1,\cdots,i_k,j_1,\cdots,j_r\in [n]$Функция, определяемая такой пропозициональной формулой, есть

$\qquad$позволять$\mathcal H^n_C$Быть классом всех булевых соединений над$\{0, 1\}^n$.$\mathcal H^n_C$размер не более$3^n+1$(Поскольку в формуле соединения каждый элемент x либо появляется, либо знак отрицания, либо вообще отсутствует, у нас также есть все отрицательные формулы). Поэтому используйтеERMизучение правил$\mathcal H^n_C$Сложность выборки не более$nlog(3/\дельта)/\эпсилон$.

Эффективное обучение, когда оно достижимо

Далее покажем, что можно решить за время$h^n_C$изERMпроблема. Идея состоит в том, чтобы определить, включив в гипотезу все буквальные комбинации, которые не противоречат ни одному положительному примеру отметки.ERMкомбинировать. позволять$v_1,\cdots,v_{m^+}$быть входным примером$S$Все экземпляры положительной маркировки в . мы проходим в$i\leq m^+$По индукции определить набор предположений (или конъюнкций). Давайте будем комбинацией всех возможных литералов. который$h_0 = x_1\bigwedge \neg x1 \bigwedge x2\bigwedge\cdots\bigwedge x_n\bigwedge\neg x_n$. Пожалуйста, обрати внимание,$h_0$присвоить метку 0$\mathcal X$всех элементов. Получаем удалением из соединения всех неудовлетворенных литералов$h_{i+1}$. Алгоритм выводит гипотезу$h{m_+}$. Пожалуйста, обрати внимание,$h_{m+}$Наклейка Наклейка на лицевой стороне Все примеры маркировки на лицевой стороне в формате S. Кроме того, для каждого$i\leq m^+$,$h_i$является самой строгой обязывающей этикеткой$v_1,\cdots,v_i$Теперь, поскольку мы рассматриваем обучение в достижимых условиях, существует обязывающая гипотеза,$f\in H^n_C$, что то же самое, что$S$Все примеры в . так как$h_{m^+}$является строжайшей привязкой, маркирующей положительно все положительные маркировки$S$член, любой тег экземпляра$0$Зависит от$f$также отмечен$0$Зависит от$h_{m^+}$. следовательно,$h_{m^+}$нет ошибок обучения$(W.R.T.S)$Поэтому законныйERMгипотеза. Обратите внимание, что время работы этого алгоритма равно$О (мн)$.

Неспособность эффективно учиться, не будучи агностиком

Как и в случае прямоугольников, выровненных по оси, за исключением$P = NP$, иначе время работы без алгоритма равно$m$и$n$многозначные в , которые гарантированно будут найдены для логических классов привязки в случае, когда это невозможноERMгипотеза.

8.2.4 Изучение трехчленной ДНФ

Далее мы покажем, что небольшое обобщение класса логической конкатенации приводит, даже когда это достижимо, к решениюERMнеразрешимость проблемы. Рассмотрим формулу 3-периодной нормальной формы разделения (3 термина ДНФ) категория. Пространство экземпляра$\mathcal X = \{0, 1\}^n$, каждая гипотеза задается в виде$h(x)= A_1(x)\bigvee A_2(x)\bigvee A_3(x)$Булева формула представления , где каждый$A_i(x)$является логической ассоциацией (как определено в предыдущем разделе). если$A_1(x) или A_2(x) или A_3(x)$Выходная метка 1, выход h(x) равен 1. Если все три конкатенации выводят метку 0, то$ч (х) = 0$.

$\qquad$позволять$\mathcal H^n_{3DNF}$В качестве гипотетического класса для всех таких формул c$\mathcal H^n_{3DNF}$по крайней мере, размер$3^{3n}$, поэтому используйтеERMизучение правил$\mathcal H^n_{3DNF}$Примерная сложность не более$3n log(3/\delta)/\epsilon$.

$\qquad$Однако эта задача обучения сложна с вычислительной точки зрения. Было показано (см. (Pete and Valiant 1988, Kearns et al. 1994)), если только$RP = NP$, без множественных временных алгоритмов правильно выучить серию3 термина ДНФпроблемы с обучением, где первое$n$Размерность вопроса$n$. Под «правильным» мы подразумеваем, что алгоритм должен выводить предположение, что3 термина ДНФ. В частности, поскольку$ERM_{\mathcal H^N_{3DNF}}$вывод3 термина ДНФформула, это правильный ученик, поэтому ее трудно реализовать. Доказательство использует сокращение задачи графа с тремя цветами.PACучиться3 термина ДНФПроблема. Подробные техники на практике$3$приведены в. См. также (Кернс и Вазирани, 1994, раздел 1.4).

8.3 Эффективное обучение, но не с помощью надлежащего ERM

В предыдущем разделе мы видели, что это невозможно сделать эффективно.$3-DNF$шаблонный$H^n_{3 DNF}$своего родаERMправило. В этом разделе мы покажем, что этот класс может быть изучен эффективно, но с использованиемERMучиться в больших классах.

Представлять самостоятельное обучение не сложно

Далее мы покажем, что можно эффективно учиться3 термина ДНФформула. Нет противоречия с результатами по сложности, упомянутыми в предыдущем разделе, поскольку теперь мы допускаем «репрезентативное независимое» обучение. То есть мы позволяем алгоритму обучения выводить гипотезу, которая не3 термина формула ДНФ. Основная идея состоит в том, чтобы3 термина формула ДНФИсходный класс гипотез заменяется более крупным классом гипотез, чтобы новый класс было легко изучить. Алгоритмы обучения могут возвращать гипотезы, не принадлежащие исходному классу гипотез: отсюда и название «независимое» обучение. Подчеркнем, что в большинстве случаев нас действительно интересует возвращение гипотез с хорошей предсказательной силой.

Сначала мы замечаем, что, поскольку$\bigvee$распространяется в$\bigwedge$, каждый3 термина формула ДНФФормулу можно переписать как

Далее давайте определим$\psi:\{0,1\}^n\rightarrow \{0,1\}^{(2n)^3}$, так что для каждой тройки$у, в, ш$существует$\psi$В области видимости есть переменная, которая указывает вам$u\bigvee v\bigvee w$Это правда или ложь. Поэтому для каждого более$\{0, 1\}^n$из3 термина ДНФформула, существует более$\{0,1\}^{(2n)^3}$, с той же таблицей истинности. Поскольку мы предполагаем, что данные достижимы, мы можем решитьERMпроблема, ссылка на группу превышает$\{0,1\}^{(2n)^3}/$Кроме того, примерная сложность изучения связанных классов в многомерных пространствах не превышает$n^3 log(1/\delta)\epsilon$. Таким образом, общее время работы этого метода больше, чем$n$.

$\qquad$Интуитивно идея выглядит следующим образом. Мы начали с гипотетического урока, который было трудно усвоить. Мы переключаемся на другое представление, предполагая, что класс больше исходного, но имеет более сложную структуру, что позволяет более эффективноERMпоиск. В новой формулировке решитьERMПроблема проста.

8.4 Трудность обучения*

Мы только что доказали, что реализация$ERM_\mathcal H$Расчетная твердость не предполагает такого$\mathcal H$Классы нельзя выучить. Как доказать, что проблема обучения неразрешима?

$\qquad$Один из способов — полагаться на криптографические предположения. В некотором смысле криптография — это полная противоположность обучению. При обучении мы пытаемся обнаружить некоторые правила — основу примеров, которые мы видели, тогда как в криптографии цель состоит в том, чтобы гарантировать, что никто не сможет раскрыть какой-либо секрет, несмотря на то, что он может получить некоторую частичную информацию о нем. В рамках этой высокоуровневой интуиции результаты о криптографической безопасности некоторых систем трансформируются в результаты о необучаемости некоторых соответствующих задач. К сожалению, в настоящее время нет способа доказать, что протоколы шифрования невзламываемы. даже если$P\not =NP$Общепринятого предположения также недостаточно, чтобы доказать это (хотя оно может оказаться необходимым для большинства распространенных сценариев шифрования). Обычный способ доказать, что криптографический протокол безопасен, состоит в том, чтобы начать с некоторых криптографических предположений. Чем больше они используются в качестве основы для криптографии, тем больше мы уверены, что они действительно будут выполняться (или, по крайней мере, трудно найти алгоритмы, которые их опровергнут).

$\qquad$Теперь мы кратко опишем основную идею того, как сложность обучаемости выводится из криптографических предположений. Многие криптографические системы полагаются на предположение, что существует односторонняя функция. Грубо говоря, односторонняя функция — это функция$е: \{0, 1\}^n\стрелка вправо\{0, 1\}^n$(Более формально, это последовательность функций, каждое измерение$n$) легко вычислить, но трудно инвертировать. Более формально,$f$Многозначность может быть рассчитана по времени ($n$), но для любого случайного многократного алгоритма$A$и каждое многозначное$p(.)$рассчитать.

в соответствии с$\{0, 1\}^n$равномерное распределение и$A$Случайность , принимает вероятность более$x$случайный выбор.

$\qquad$односторонняя функция$f$называется Trapdoor односторонним функциями, если для некоторых нескольких функций$p$, для каждого$n$Существующая длина$\leq p(n)$битовая строка$s_n$(называемый секретным ключом), поэтому существует несколько временных алгоритмов, которые используются для каждого$n$и каждый$х\в\{0, 1\}^п$, для ввода$(е (х), s_n)$вывод$x$Другими словами, хотя$f$Трудно инвертировать, но как только люди получат доступ к своему секретному ключу, инвертировать$f$становится осуществимым. Эти функции параметризуются своими секретными ключами.

$\qquad$Теперь позвольте$F_n$стать лазейкой в$\{0, 1\}^n$семейства, эти функции могут быть вычислены некоторыми многократными алгоритмами времени. То есть мы фиксируем алгоритм, который дает секретный ключ (представляющий$F_n$функция в ) и входной вектор, который вычисляет значение функции, соответствующей секретному ключу во входном векторе, за несколько квот. Рассмотрим задачу изучения соответствующего обратного класса,$H^n_F =\{f^{-1}:f\in F_n\}$. Поскольку к каждой функции в этом классе можно получить доступ с помощью$n$секретный ключ полинома определенного размера в$s_n$с ног на голову,$H^n_F$Классы могут быть параметризованы этими ключами, и их размер не превышает$2 ^ {р (п)}$. Поэтому сложность его образцов кратна. Мы утверждаем, что в этом классе нет эффективных учеников. Если есть такой ученик,$L$, то методом случайной выборки$\{0, 1\}^n$строку с несколькими квотами и вычислить$f$На них мы можем сгенерировать отмеченную пару$(е (х), х)$, что должно быть достаточно для наших учащихся, чтобы понять$(\ эпсилон, \ дельта)$приблизительный$f^{-1}$($w.r.t.$существует$f$равномерное распределение в диапазоне), что нарушило бы$f$однонаправленное свойство.

$\qquad$Более подробное рассмотрение, а также конкретный пример можно найти в (Кернс и Вазирани, 1994, глава 6). Используя сокращения, они также показывают, что классы функций, которые могут быть вычислены с помощью небольших логических схем, не могут быть изучены эффективно, даже если это достижимо.

8.5 Резюме

Время работы алгоритма обучения анализируется без того же имени как функция различных параметров задачи обучения, таких как размер класса гипотез, наша мера точности, наша мера достоверности или размер набора доменов. Мы продемонстрировали, что можно эффективно выполнятьERMслучае правил. Например, мы выводим решения для класса логической связи и класса прямоугольников, выровненных по осям, в предположении о реализуемости.ERMЭффективный алгоритм решения проблемы. Однако внедрить ERM для этих классов сложно, не будучи агностиком. Напомним, что со статистической точки зрения нет никакой разницы между реализуемым случаем и агностическим случаем (т. е. если и только если существует конечная размерность VC, в обоих случаях класс является образовательным). Напротив, как мы видим, разница огромна с вычислительной точки зрения. Мы также показываем другой пример,3 термина ДНФкласс, реализующийERMТрудный, даже когда достижимый, класс может быть эффективно изучен другим алгоритмом.

$\qquad$Реализовано в нескольких классах естественных гипотезERMЖесткость правил побудила к разработке альтернативных методов обучения, которые мы обсудим в следующей части этой книги.

8.6 Библиографическое описание

Valiant (1984) представил эффективныеPACИзучите модель, в которой требуется время работы алгоритма.$1/\эпсилон, 1/\дельта$Полином от и предполагаемый размер представления в классе. Подробное обсуждение и обширные библиографические примечания приведены у Kearns and Wazirani (1994).

8.7 Упражнение

1, пусть$\mathcal H$становится интервальным классом на линии (формально эквивалентным размеру$n = 1$выровненный по оси прямоугольник в ). рекомендуемая реализация$ERM_\mathcal H$правила обучения (в агностическом случае) с заданным набором размеров$m$тренировочный набор, бег на время$О (м ^ 2)$.

2, пусть$\mathcal H_1,\mathcal H_2,\cdots$Предположим, что алгоритм обучения реализован там, где это достижимо.ERMправила, поэтому каждый$\mathcal H_n$Выходная гипотеза алгоритма класса зависит только от$На)$Пример. Кроме того, предполагается, что эти$На)$Пример (время$На)$Такие допущения рассчитываются, и эмпирический риск для каждого такого допущения может быть сделан вовремя.$О (мн)$оценивать. Например, если$\mathcal H_n$да$\mathbb R^n$Выровненный по оси класс среднего прямоугольника, мы находим, что самое большее$2n$Достижимый случай, определяемый примером, может быть найденERMгипотеза. Докажите, что в этом случае можно найти невозможное$\mathcal H_n$изERMгипотеза$О (мнм ^ {О (п)})$

3. В этом упражнении мы предлагаем несколько классов и находимERMКлассификаторы сложны в вычислительном отношении. Сначала введем класс n-мерных полупространств HSn для области X = Rn. Это класс всех функций вида hw,b(x) = symbol (hw,xi = b), где w,x ∈ Rn, hw,xi — их внутренние произведения, b ∈ R. Подробное описание см. в главе 9.