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

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

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

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

Моей первой идеей было использовать либо PSO (оптимизация роя частиц), либо генетические алгоритмы для решения f вместо a, b, .., c, и я уверен, что они дадут хорошие результаты.

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

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

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

Спасибо


person devoured elysium    schedule 15.10.2010    source источник
comment
Я считаю, что такого рода проблемы практически невозможно решить, если вы не наложите на них некоторые ограничения, например, предполагая, что целевая функция является линейной или полиномом фиксированной степени.   -  person Fred Foo    schedule 15.10.2010
comment
Да, я хорошо осведомлен об этом факте. Одна из целей этого поста состояла в том, чтобы попытаться понять, предполагают ли люди, как правило, линейность функций, как это сделал я, или вообще неплохо попробовать какую-то другую форму функции. Может полиномиальная, я не знаю?   -  person devoured elysium    schedule 15.10.2010
comment
«Функции линейны» — это просто гипотезы, которые вам нужно проверить на ваших данных.   -  person Eugen Constantin Dinca    schedule 16.10.2010


Ответы (3)


Вы описываете проблему регрессии, это классическая проблема машинного обучения. Только на эту тему написаны тысячи научных работ и целых учебников. Я бы посоветовал взглянуть на некоторые онлайн-курсы по машинному обучению или ознакомиться со стандартным текстом по машинному обучению< /а>.

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

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

person fairidox    schedule 15.10.2010
comment
Я не беспокоюсь о том, как идентифицировать функции, я думаю, что уже определил хороший их набор. Я хотел бы узнать больше о расширении функций, я не могу найти статью в вики (по крайней мере, для этого имени). Не могли бы вы дать еще какие-нибудь ссылки об этом? - person devoured elysium; 16.10.2010
comment
Глава 5 учебника, на который я ссылался, Базисные расширения и регуляризация — это именно то, на что вы хотите обратить внимание. - person fairidox; 16.10.2010

Учитывая, что вы работаете над игрой, первое, что приходит на ум, это древняя программа для игры в шашки, разработанная Артура Сэмюэля в 1950-х годах и упоминается Расселом и Норвигом в их главе об играх (среди прочего, это все еще классика машинного обучения без учителя/полуконтроля).

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

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

Этот ответ превращается в эссе о чем-то, в чем я не эксперт. Пожалуйста, ознакомьтесь с соответствующей литературой.

person Fred Foo    schedule 15.10.2010

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

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

person Nick Larsen    schedule 15.10.2010
comment
Я до сих пор точно не знаю, какими будут входные переменные (поэтому я не знаю домен переменной). Твоя идея исправить каждую переменную по мере того, как я просматриваю каждую из них, не кажется такой уж хорошей. Идея использования эволюционных алгоритмов как раз и состоит в том, чтобы избежать перебора всех значений (пространство состояний огромно!). - person devoured elysium; 16.10.2010