Рубрика «методы оптимизации»

План статьи

  1. Постановка задачи.
  2. Формальное описание задачи.
  3. Примеры задач.
  4. Несколько примеров на синтетических данных со скрытыми линейными зависимостями.
  5. Какие ещё скрытые зависимости могут содержаться в данных.
  6. Автоматизация поиска зависимостей.

  • Число признаков меньше пороговой величины.
  • Число признаков превышает пороговую величину.

Постановка задачи

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

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

Формальное описание задачи

Перед нами ставится задача классификации L объектов, заданных n вещественными числами. Мы будем рассматривать простой двухклассовый случай, когда метки классов — это −1 и +1. Наша цель — построить линейный классификатор, то есть такую функцию, которая возвращает −1 или + 1. При этом набор признаковых описаний таков, что для объектов противоположных классов, измеренных на данном множестве признаков, практически не работает гипотеза компактности, а разделяющая гиперплоскость строится крайне неэффективно.

Иными словами, всё выглядит так, будто задача классификации на данном множестве объектов не может быть решена эффективно.
Читать полностью »

Введение

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

Постановка задачи

В публикациях [1,2] рассматривались решения прямых задач оптимизации методом линейного программирования и был предложен обоснованный выбор решателя scipy. optimize.

Однако известно [3], что каждой задаче линейного программирования соответствует так называемая выделенная(двойственная)задача. В ней по сравнению с прямой задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или наоборот, вместо минимума — максимум). Задача, двойственная к двойственной — эта сама исходная задача.

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

Оптимальные значения стоимости материала и труда будут оцениваться по их вкладу в целевую функцию. В результате будут получены «объективно обусловленные оценки» сырья и рабочей силы, которые не совпадают с рыночными ценами.Читать полностью »

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

Умеют ли коты строить регрессию? - 1

Читать полностью »

Доброго времени суток!

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

Закончив специалитет и готовясь к защите кандидатской диссертации, я задался вполне логичным вопросом: «а что же дальше?» Имея за плечами опыт как обычной работы, так и исследовательской, я вновь вернулся к той самой идее, которая, казалось бы, должна была утонуть под толщей пыли. Но вернулся я к этой идее в более осознанной форме.

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

Прикладное применение задачи нелинейного программирования - 1

Ну что ж, всем заинтересовавшимся:
Читать полностью »

Алгоритм Левенберга — Марквардта для нелинейного метода наименьших квадратов и его реализация на Python - 1

Нахождение экстремума (минимума или максимума) целевой функции является важной задачей в математике и её приложениях (в частности, в машинном обучении есть задача curve-fitting). Наверняка каждый слышал о методе наискорейшего спуска (МНС) и методе Ньютона (МН). К сожалению, эти методы имеют ряд существенных недостатков, в частности — метод наискорейшего спуска может очень долго сходиться в конце оптимизации, а метод Ньютона требует вычисления вторых производных, для чего требуется очень много вычислений.

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

Алгоритм Левенберга — Марквардта для нелинейного метода наименьших квадратов и его реализация на Python - 2

Алгоритм Левенберга — Марквардта используется для решения нелинейного метода наименьших квадратов. Статья содержит:

  • объяснение алгоритма
  • объяснение методов: наискорейшего спуска, Ньтона, Гаусса-Ньютона
  • приведена реализация на Python с исходниками на github
  • сравнение методов

Читать полностью »

Сегодня мы рассмотрим алгоритм TILT (Transform Invariant Low-rank Texture) и множество его методов применения в области Computer Vision. Статья будет нести несколько обзорный характер, без плотного углубления в математические дебри.
Алгоритм TILT или нестандартное использование ранга матрицы - 1
Читать полностью »

Требуемые знания: знакомство с методами линейного программирования, методы решения транспортной задачи(особенно метод потенциалов).

Год назад, на третьемimage курсе в качестве одной из лабораторных работ по курсу «Методы оптимизации» мне задали реализовать решение транспортной задачи, но с одним небольшим условием: перевозки происходят партиями. Это значит, что теперь, в отличие от классической постановки, оплачивается перевозка партии товаров (e.g. 10 штук), и, даже если Вам надо перевезти 11 штук, Вы заплатите за две партии(в один трейлер 11 штук не влезут). Казалось бы, мелкое дополнение, однако как теперь решать задачу, да хотя бы как её формализовать? Как студенту кафедры прикладной математики, мне было не привыкать, что великий google.ru чего-то не знает, но каково же было моё удивление, когда ни его старший брат — англоязычный google, ни тьма перебранных мной книг по теории оптимизации не смогли ответить на этот вопрос.
Читать полностью »

Преамбула

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

Постановка

Крайне важную нишу в методах оптимизации занимают задачи линейного программирования (ЛП). Они заключаются в минимизации (или максимизации) целевого линейного функционала на многомерном пространстве при наличии ограничений, заданных в виде линейных неравенств. Формально каноническая задача ЛП выглядит следующим образом:
Требуется найти Симплекс метод при заданных ограничениях Симплекс метод. Для ясности: x — вектор переменных, C — вектор коэффициентов (C^T[N]*x[N] и задает линейный функционал). Матрица А является матрицей полного ранга, иначе говоря rang A[M, N] = min(M, N).
Приведем тривиальный пример. Допустим, мы ищем Симплекс метод при условиях: Симплекс метод
Для лучшего представления прикладываю график множества ограничений:
Симплекс метод
Читать полностью »