Недавно возник вопрос, похожий на ML, касающийся обмена стека теорий, и я опубликовал ответ, рекомендующий метод Пауэлла, градиентный спуск, генетические алгоритмы или другие «алгоритмы приближения». В комментарии кто-то сказал мне, что эти методы являются «эвристикой», а не «алгоритмами аппроксимации» и часто не приближаются к теоретическому оптимуму (потому что они «часто застревают в локальных минимумах»).
Другие согласны с этим? Кроме того, мне кажется, что есть ощущение, что эвристические алгоритмы могут быть гарантированно приближены к теоретическим оптимумам, если они настроены на исследование большой части пространства поиска (например, установка параметров / размеров шагов малыми), хотя я и не использовал не видел этого в газете. Кто-нибудь знает, было ли это показано или доказано в статье? (если не для большого класса алгоритмов, может быть для небольшого класса, скажем, NNs и т. д.)
Ответы:
Я думаю, что вы смешиваете несколько важных концепций. Позвольте мне попытаться уточнить пару вещей:
Существуют метаэвристические методы, которые представляют собой методы, которые итеративно пытаются улучшить подходящее решение. Примерами этого являются поиск по табу, имитация отжига, генетические алгоритмы и т. Д. Заметьте, что хотя во многих случаях эти методы работают хорошо, глубокого понимания того, когда эти методы работают, а когда нет, не существует. И что еще более важно, когда они не достигают решения, мы можем быть сколь угодно далеко от него. Проблемы, решаемые с помощью метаэвристических методов, имеют тенденцию быть дискретными по своей природе, потому что есть гораздо лучшие инструменты для решения непрерывных проблем. Но время от времени вы видите метаэвристику и для постоянных проблем.
Существуют численные методы оптимизации, люди в этом сообществе тщательно изучают природу функции, которая должна быть оптимизирована, и ограничения решения (на группы, такие как выпуклая оптимизация, квадратичное программирование, линейное программирование и т. Д.) И применяют алгоритмы, которые были показаны работать для этого типа функции, и эти типы ограничений. Когда люди в этой области говорят «показано на работу», они имеют в виду доказательство. Ситуация такова, что эти типы методов работают в постоянных задачах. Но когда ваша проблема попадает в эту категорию, это определенно инструмент для использования.
Существуют дискретные методы оптимизации, которые, как правило, связаны с алгоритмами для хорошо изученных дискретных задач, таких как кратчайшие пути, максимальный поток и т. Д. Люди в этой области также заботятся о том, чтобы их алгоритмы действительно работали (доказательства). В этой группе есть подгруппа людей, которые изучают действительно сложные задачи, для которых не ожидается быстрого алгоритма. Затем они изучают алгоритмы аппроксимации, которые являются быстрыми алгоритмами, для которых они способны показать, что их решение находится в пределах постоянного фактора истинного оптимума. Это называется "алгоритмы приближения". Эти люди также показывают свои результаты в качестве доказательства.
Итак ... чтобы ответить на ваш вопрос, я не думаю, что метаэвристика - это алгоритмы аппроксимации. Это не кажется мне чем-то связанным с мнением, это просто факт.
источник
Машинное обучение часто имеет дело с оптимизацией функции, которая имеет много локальных минимас. Нейронные сети прямой связи со скрытыми единицами - хороший пример. Независимо от того, являются ли эти функции дискретными или непрерывными, не существует метода, который достигает глобального минимума и останавливается. Нетрудно доказать, что не существует общего алгоритма для нахождения глобального минимума непрерывной функции, даже если она одномерна и гладка (имеет бесконечно много производных). На практике все алгоритмы обучения нейронных сетей застряли в локальном минимуме. Это легко проверить: создайте случайную нейронную сеть, сделайте большой набор ее ответов на случайные входы, затем попытайтесь изучить другую нейронную сеть с той же архитектурой, чтобы скопировать ответы. Хотя идеальное решение существует, ни обратное распространение, ни какой-либо другой алгоритм обучения не смогут его обнаружить,
Некоторые методы обучения, такие как имитация отжига или генетические алгоритмы, исследуют многие локальные минимы. Для непрерывных функций существуют методы типа градиентного спуска, которые находят ближайший локальный минимум. Они намного быстрее, поэтому широко используются на практике. Но, учитывая достаточное количество времени, первая группа методов превосходит более позднюю с точки зрения ошибки в обучающей установке. Но с разумными временными ограничениями для реальных проблем последняя группа обычно лучше.
Для некоторых моделей, таких как логистическая регрессия, существует один локальный минимум, функция выпуклая, минимизация сходится к минимуму, но сами модели являются упрощенными.
Это горькая правда.
Отметим также, что доказательство сходимости и доказательство сходимости к лучшему решению - это две разные вещи. Алгоритм K-средних является примером этого.
Наконец, для некоторых моделей мы вообще не знаем, как учиться. Например, если выходные данные являются произвольной вычислимой функцией входных данных, мы не знаем хороших алгоритмов, которые в разумные сроки находят механизм Тьюринга или эквивалентную машину, реализующую эту функцию. Например, если f (1) = 2, f (2) = 3, f (3) = 5, f (4) = 7, ..., f (10) = 29 (десять первых простых чисел), мы Не знаю ни одного алгоритма обучения, который мог бы за разумное время предсказать, что f (11) = 31, если он уже не знает концепцию простых чисел.
источник