Как лучше всего подойти к проблеме определения формы неизвестной функции

Question

У меня есть набор переменных X, Y, ..., Z. Моя задача - создать функцию, которая принимает этот набор переменных и дает целое число. У меня есть функция фитнеса, чтобы проверить это.

Мой первый удар на проблему заключается в предположении, что я могу моделировать f быть линейной функцией:

f(X, Y, ..., Z) -> aX + bY ... cZ 

Моя первая идея состояла в том, чтобы использовать либо ПСО (Particle Swarm Optimization) или генетические алгоритмы для решения f для a, b, .., c, и я уверен, что они наверняка принесут хорошие результаты.

С другой стороны, мне кажется, что такие эволюционные алгоритмы действительно не нужны. Прежде всего, я могу представить пару хороших «отправных точек» для a,b, .., c. Будучи f линейной функцией, не должно быть проще просто попробовать пару точек, а затем сделать что-то вроде линейной регрессии? И после линейной регрессии, пробуя еще пару очков, на этот раз ближе к тому, что выглядит как хорошее «пятно», снова создавая линейную регрессию?

Каковы же его недостатки? Любой, у кого есть опыт в подобных проблемах? Самый большой, о котором я могу думать, это то, что, может быть, то, что я считаю хорошим стартовым значением для a,b, .., c, может быть «локальным оптимизмом», и наличие какого-то эволюционного алгоритма даст мне глобальный характер.

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

Благодаря

Answer 1

Вы описываете проблему регрессии, это классическая проблема машинного обучения. Есть тысячи научных статей и целых учебников, написанных только по этой теме. Я бы предложил взглянуть на некоторые классы машинного обучения онлайн или проверить standard machine learning text.

Общий подход подобен тому, что вы упомянули, для решения линейных коэффициентов для переменных, чтобы минимизировать потери, как правило, суммы квадратов ошибок (L2 Loss). Это желательно, потому что это выпуклая функция и поэтому содержит один минимум, а весы могут быть решены в течение полиномиального времени. Однако, как вы уже упоминали, истинная функция может не лежать в этом классе функций, и вы будете иметь плохую оценку. Подход в этом случае составляет , а не, чтобы попробовать какую-то невыпуклую оптимизацию с помощью некоторых неясных методов роевых частиц или генетических алгоритмов или любой другой глобальной методики оптимизации. Ваше утверждение «... может быть« локальным оптимизмом », и наличие какого-то эволюционного алгоритма даст мне глобальный». является наивным. Глобальная оптимизация NP-Hard, эти методы являются приблизительными и не имеют абсолютно никаких гарантий относительно времени выполнения или оптимальности, и они почти никогда не работают.

Гораздо более приемлемым подходом является использование «расширения функций», которое принимает ваши переменные X, Y, ..., Z и применяет нелинейное преобразование к некоторому новому набору phi(X), phi(Y), ..., phi(Z). На этом этапе вы можете найти оптимальный линейный вес для каждой функции с наименьшими квадратами (если вы используете L2) или что угодно. Как найти хорошие функции - это открытая проблема машинного обучения, но для этого есть лодка идей и свободно доступных алгоритмов.

Answer 2

Учитывая, что вы работаете над игрой, то первое, что приходит на ум, это древняя программа для игры в шашки, разработанная Arthur Samuel в 1950-х годах и упоминается Russell and Norvig в их главе, посвященной игре игры (среди прочих, он по-прежнему является классическим при неконтролируемом/полуконтролируемом механическом обучении).

Эта программа предполагала, что значение платы шашек было линейной функцией положения платы. Я не знаю деталей, но я полагаю, что каждая из частей игрока стоила +1, части противника -1 и пустые поля 0. Каждый квадрат имел вес, связанный с ним, что было изучено, позволяя программе играть против сам (большое) количество раз, оценивая игру после каждого матча.

Эта стратегия называется самообучением и также применяется в классическом программном обеспечении нарды TD-Gammon, которое основано на нейронных сетях (многослойных/нелинейных). На странице Википедии об этой программе есть некоторые потенциально интересные ссылки.

Этот ответ превращается в эссе о чем-то, в котором я не эксперт. См. Соответствующую литературу.

Answer 3

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

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