Функции, которые неэффективно вычислимы, но обучаемы

Мы знаем, что (см., Например, теоремы 1 и 3 из [1]), грубо говоря, при подходящих условиях функции, которые могут быть эффективно вычислены машиной Тьюринга за полиномиальное время («эффективно вычисляемое»), могут быть выражены полиномиальными нейронными сетями. с разумными размерами, и, таким образом, может быть изучен с полиномиальной сложностью выборки («обучаемость») при любых входных распределениях.

Здесь «обучаемость» касается только сложности образца, независимо от сложности вычислений.

Я задаюсь вопросом об очень тесно связанной проблеме: существует ли функция, которая не может быть эффективно вычислена машиной Тьюринга за полиномиальное время («неэффективно вычисляемо»), но в то же время может быть изучена с полиномиальной сложностью выборки («обучаемая») под любым входным распределением?

• [1] Рой Ливни, Шай Шалев-Шварц, Охад Шамир, « Об вычислительной эффективности обучения нейронных сетей », 2014 г.

Я формализую вариант этого вопроса, где «эффективность» заменяется «вычислимостью».

Пусть - концептуальный класс всех языков распознаваемых машинами Тьюринга в состояниях или меньше. В общем, для и проблема вычисления неразрешима.$C_n$$L\subseteq\Sigma^*$$n$$x\in\Sigma^*$$f\in C_n$$f(x)$

Однако предположим, что у нас есть доступ к (правильному, реализуемому) оракулу обучения PAC для . То есть для любого оракул запрашивает помеченную выборку размера , так что, если предположить, что такая выборка была извлечена из неизвестного дистрибутива , оракул выводит гипотезу которая с вероятностью не менее имеет ошибку генерализации не более . Мы покажем, что этот оракул не является вычислимым по Тьюрингу.$A$$C_n$$\epsilon,\delta>0$$m_0(n,\epsilon,\delta)$$D$F ∈ C п 1 - δ D ε$A$$\hat f\in C_n$$1-\delta$$D$$\epsilon$

На самом деле, мы покажем , что более простая задача неразрешима: Один из определения, учитывая меченый образец , существует ли в в соответствии с . Предположим (чтобы получить противоречие), что является машиной Тьюринга, которая решает проблему согласованности.$S$$f\in C_n$$S$$K$

Мы сделаем следующие условные обозначения. Определите с помощью помощью обычного лексикографического порядка. Для мы говорим, что TM "S-prints" если он принимает все строки в соответствующие индексам st и не принять (возможно, не останавливая) любую из строк, соответствующих индексам . Поскольку (по предположению) разрешима, из этого следует, что функция , определенная как наименьшее такое, что некоторый TM в$\Sigma^*$$\mathbb{N}=\{0,1,2,\ldots\}$$x\in\{0,1\}^*$$M$$x$$\Sigma^*$$i$$x_i=1$$x_i=0$$K$$\tilde K:x\mapsto k$$k$$C_k$ S-prints , вычислимо по Тьюрингу. Далее следует, что функция , которая отображает a в наименьшую (лексикографически) строку такую, что , также вычислимо.$x$$g:k\mapsto x$$k\in\mathbb{N}$$x\in\{0,1\}^*$$\tilde K(x)>k$

Теперь определите TM следующим образом: S-prints , где - кодировка , обозначает длину строки, а рекурсия теорема быть вызвана , чтобы утверждать существование такого . Тогда имеет некоторую длину кодирования,, и он S-печатает некоторую строку, . По построению, , и, следовательно, не может быть S-напечатан любой TM с длиной описания$M$$M$$g(|\langle M\rangle|)$$\langle M\rangle$$M$$|x|$$M$$M$$\ell=|\langle M\rangle|$$x_M\in\{0,1\}^*$$\tilde K(x_M)>\ell$$x_M$$\ell$или короче. И все же это определяется как вывод S-print ТМ с длиной описания --- противоречие.$\ell$