Можно ли использовать нейронные сети для разработки алгоритмов?

После новых и новых успехов нейронных сетей в игре в настольные игры, мы чувствуем, что следующая наша цель может быть чем-то более полезным, чем победа над людьми в Starcraft. Точнее, я задавался вопросом,

Можно ли обучить нейронные сети для решения классических алгоритмических задач?

Здесь я имею в виду, что, например, сеть получит входной граф $G$ со взвешенными ребрами и двумя вершинами $s$ а также $t$ указал, и мы попросили его найти кратчайший $st$путь как можно быстрее. Тогда я думаю, что нейронная сеть обнаружит и обучит себя использовать Dijkstra или что-то подобное.

С одной стороны, мы знаем, что вычислительная мощность нейронных сетей$TC^0$, С другой стороны, я не знаю, обязательно ли это связано с моим вопросом. Тем не менее, для большинства проблем мы не знаем, могут ли они быть решены в$TC^0$или нет. Проверка того, может ли нейронная сеть обучаться сама по себе, может быть хорошим показателем того, существует ли быстрый алгоритм или нет. Например, если нейронные сети не могут подготовиться к быстрому решению SAT, то это повышает вероятность того, что$NP\not\subset TC^0$, Интересно, что будет делать нейронная сеть с ГРАФИЗОМОРФИЗМОМ или ФАКТОРИЗАЦИЕЙ?

Конечно, извлечение алгоритма - это совсем другой вопрос. Я подозреваю, что эксперты знают, как это сделать, но обсуждение этого вопроса не является темой этого вопроса.

Добавлено через два дня: После просмотра ответов позвольте мне указать, что если вы ответите отрицательно, то я хотел бы знать,

Почему играть в шахматы легче, чем Дейкстра или Графисоморфизм?

Согласно этому блогу Резы Заде , обучение нейронной сети для получения правильных результатов даже для двух третей обучающих примеров является сложным в вычислительном отношении:

Действительно, в 1988 году Дж. Стивен Джадд показал, что NP-сложность состоит в следующем:

Принимая во внимание общую нейронную сеть и набор обучающих примеров, существует ли набор граничных весов для сети, так что сеть выдает правильный результат для всех обучающих примеров?

Джадд также показывает, что проблема остается NP-трудной, даже если для ее получения требуется всего лишь две трети обучающих примеров, когда сеть требует только правильного вывода, что подразумевает, что даже приблизительное обучение нейронной сети само по себе сложно в худшем случае. В 1993 году Blum и Rivest усугубляют эту новость: даже простая сеть, состоящая всего из двух слоев и трех узлов, является NP-сложной для обучения!

Это не полный ответ, и я не очень опытен в нейронных сетях, но, возможно, полезен.

NN по сути дают входные данные и дают ответ. Затем они обучаются на практике для получения схожих ответов на «аналогичные» входные данные в домене, например, одинаковую метку с изображениями одного и того же животного или высокие оценки для «хороших» шахматных позиций, где хорошее означает высокие шансы на победу.

Как я уже говорил, нейронные сети - это неоднородная модель вычислений, которая работает совершенно иначе, чем пошаговые алгоритмы, работающие на машинах Тьюринга. Вместо этого, думайте о них как о «мягких» схемах, которые используют непрерывную математику, а не логическое, и могут быть настроены или обучены, и могут допускать ошибки.

Почему играть в шахматы легче, чем Дейкстра или Графисоморфизм?

Частично, это разница между тем, чтобы попросить кого-то ответить на вопрос в меру своих способностей, и попросить его дать один правильный ответ вместе с доказательством того, что он правильный. Частично, это разница между решением проблемы фиксированного размера и одновременным решением проблемы для всех возможных входных размеров.

Каждый раз, когда Дейкстра запускается на экземпляре, который может иметь любой размер, он неявно доказывает, что его вывод - это один верный ответ, а не другой. В шахматах и ​​распознавании образов каждый дает лучший ответ, а ошибки допускаются. Кроме того, только обучают сети решать эти проблемы одного размера за один раз. Я не думаю, что мы еще знаем, как обобщить такое решение нейронной сети, скажем, для проблемных случаев совершенно разных размеров и форм.

Я не думаю, что мы должны предполагать, что нейронные сети не могут решать кратчайшие пути или подобные алгоритмические проблемы, но они решают проблемы принципиально иным способом, чем пошаговый алгоритм, который всегда корректен.

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

Я ни в коем случае не эксперт, но пока не понимаю, почему нет.

Нейронные сети в основном выполняют оптимизацию в соответствии с некой «моделью затрат / выгод», которая часто уже известна заранее. Кроме того, пространство поиска четко определено, с известными допустимыми и недействительными перемещениями и легко определяемыми «вариациями». Даже для AlphaZero и AlphaGo функции затрат, вероятно, основаны на выигрышной ставке и результирующем распределении выигрышных ставок для всех возможных ходов после хода или какой-то эвристики для этого.

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

Однако даже для некоторых программ метрики «пригодности» могут быть довольно сложно определить. Время? Использование пространства? Количественная оценка "побочных эффектов?" Оптимально, вы будете генерировать «самую короткую программу», которая выполняет только то, что вы хотите.

Я полагаю, что если вы найдете правильные показатели пригодности и алгоритмы настройки, вы сможете это сделать.

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

Я инженер QA Automation, поэтому не претендую на опыт в нейронных сетях, но, тавтологически, да, NN может самостоятельно создавать алгоритмы. Сами люди на каком-то уровне являются NN, и мы создаем алгоритмы, поэтому понятно, что искусственные системы NN, которые мы создаем, могут сами создавать алгоритмы.