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

28

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

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

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

Минков
источник
4
Я беру вопрос с "и таким образом можно научиться". Есть очень эффективно вычисляемые функции (скажем, DFA), которые ОЧЕНЬ трудно изучить, даже приблизительно.
Арье
3
Вероятно, в этом нет смысла, но как насчет класса (скажем) -базированных булевых функций? (То есть, более или менее, случайная функция, каждое значение которой равно с вероятностью ). Для любого обучение PAC при равномерном распределении тривиально (необходим 0 выборок, постоянная функция - хорошая гипотеза), но, похоже, любой алгоритм оценки должен провести суперполиномиальное время (так как нет функции для функции). Скорее всего, я неправильно понимаю вопрос. 12-2n1 ε>2-2n 0ε>2n0
Клемент С.
3
Ваша терминология немного сбивает с толку. Когда мы говорим «эффективно учиться», мы обычно имеем в виду вычислительную эффективность. Просто сказать «обучаемый» достаточно, чтобы подразумевать эффективность выборки.
Лев Рейзин
1
@Minkov Чтобы PAC учился, вы должны учиться в отношении любого дистрибутива. Иначе вопрос не интересен (как отмечает Клемент).
Лев Рейзин
2
Почему люди голосуют за закрытие? Я думаю, что это глубокий и тонкий вопрос!
Арье

Ответы:

11

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

Пусть - концептуальный класс всех языков распознаваемых машинами Тьюринга в состояниях или меньше. В общем, для и проблема вычисления неразрешима.CnLΣnxΣfCnf(x)

Однако предположим, что у нас есть доступ к (правильному, реализуемому) оракулу обучения PAC для . То есть для любого оракул запрашивает помеченную выборку размера , так что, если предположить, что такая выборка была извлечена из неизвестного дистрибутива , оракул выводит гипотезу которая с вероятностью не менее имеет ошибку генерализации не более . Мы покажем, что этот оракул не является вычислимым по Тьюрингу.ACnϵ,δ>0m0(n,ϵ,δ)DFC п 1 - δ D εAf^Cn1δDϵ

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

Мы сделаем следующие условные обозначения. Определите с помощью помощью обычного лексикографического порядка. Для мы говорим, что TM "S-prints" если он принимает все строки в соответствующие индексам st и не принять (возможно, не останавливая) любую из строк, соответствующих индексам . Поскольку (по предположению) разрешима, из этого следует, что функция , определенная как наименьшее такое, что некоторый TM вΣN={0,1,2,}x{0,1}MxΣixi=1xi=0KK~:xkkCk S-prints , вычислимо по Тьюрингу. Далее следует, что функция , которая отображает a в наименьшую (лексикографически) строку такую, что , также вычислимо.xg:kxkNx{0,1}K~(x)>k

Теперь определите TM следующим образом: S-prints , где - кодировка , обозначает длину строки, а рекурсия теорема быть вызвана , чтобы утверждать существование такого . Тогда имеет некоторую длину кодирования,, и он S-печатает некоторую строку, . По построению, , и, следовательно, не может быть S-напечатан любой TM с длиной описанияMMg(|M|)MM|x|MM=|M|xM{0,1}K~(xM)>xMили короче. И все же это определяется как вывод S-print ТМ с длиной описания --- противоречие.

Арье
источник
2
Задача: преобразовать мой «бесконечный» аргумент с помощью вычислимости в финитарный с помощью эффективности. Я думаю, что ответ на вопрос @ minkov отрицательный: вы не можете эффективно выучить класс функций, который вы не можете эффективно оценить. Я думаю, что это будет по-прежнему верно, если вы выйдете за рамки правильного или реализуемого PAC.
Арье