Могут ли любые существующие структуры машинного обучения правильно эмулировать рекурсивные функции, такие как последовательность Фибоначчи?

Ответ 1

Хорошо, с чего начать...

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

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

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

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

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

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

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

Я думаю, что вы также хорошо разбираетесь в этом:

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

Другие ответы дают долгий путь, чтобы сообщить вам, где находится современное состояние. Если вы хотите больше, впереди будет новый путь исследования!

Ответ 2

Согласно Колмогорову и др. О представлении непрерывных функций многих переменных путем наложения непрерывных функций одной переменной и сложения трехслойная нейронная сеть может моделировать произвольную функцию с линейной и логистической функциями, включая f(n) = ((1+sqrt(5))^n - (1-sqrt(5))^n) / (2^n * sqrt(5)), которая является близким решением формы последовательности Фибоначчи.

Если вы хотите рассматривать проблему как рекурсивную последовательность без решения с закрытой формой, я бы рассматривал ее как особый подход с подвижным окном (я назвал его особенным, потому что размер вашего окна кажется фиксированным как 2). Есть более общие исследования по размеру окна для вашего интереса. См. Эти два сообщения:

Прогнозирование временных рядов через нейронные сети

Правильный способ использования рекуррентной нейронной сети для анализа временных рядов

Ответ 3

См. статью:

Тьюринговые машины - это повторяющиеся нейронные сети

http://lipas.uwasa.fi/stes/step96/step96/hyotyniemi1/

В документе описывается, как рекуррентная нейронная сеть может имитировать машину регистрации, которая, как известно, является универсальной вычислительной моделью, эквивалентной машине Тьюринга. Результат - "академический" в том смысле, что нейроны должны быть способны вычислять с неограниченными числами. Это работает математически, но будет иметь проблемы прагматично.

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

Ответ 4

Генетические алгоритмы должны уметь делать трюк. Важным является это (как всегда, с GA) представление.

Если вы определяете пространство поиска как синтаксические деревья, представляющие арифметические формулы, и предоставляете достаточно данных обучения (как и с любым алгоритмом машинного обучения), он, вероятно, сходится к закрытое решение для чисел Фибоначчи, которое:

Fib (n) = ((1 + srqt (5)) ^ n - (1-sqrt (5)) ^ n)/(2 ^ n * sqrt (5)) [Источник]

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

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

Изменить: Я также хотел бы отметить, что в некоторых случаях всегда существует решение с замкнутой формой рекурсивной функции:

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

Ответ 5

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

Вот краткий обзор других исследований ГП, в которых используется проблема Фибоначчи в разделе 3.4.2 моей кандидатской диссертации, доступна здесь: http://kar.kent.ac.uk/34799/. Остальная часть тезиса также описывает мой собственный подход, который более подробно рассматривается в этой статье: http://www.cs.kent.ac.uk/pubs/2012/3202/

Другим заметным исследованием, которое использовало проблему Фибоначчи, является работа Саймона Хардинга с самомодифицирующимся декартовым GP (http://www.cartesiangp.co.uk/papers/eurogp2009-harding.pdf).