`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Леонид Бараш

Быстрая оптимизация вычислительных алгоритмов

+11
голос

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

На IEEE Symposium on Foundations of Computer Science трио из нынешних и прошлых аспирантов MIT выиграло награду «Лучшая студенческая статья» для нового алгоритма "отсекающей плоскости" - алгоритма общего назначения для решения задач оптимизации. Алгоритм улучшает время работы своих наиболее эффективных предшественников, и у исследователей есть некоторые основания полагать, что они, возможно, достигли теоретического предела.

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

«То, что мы пытаемся сделать, это возродить интерес людей к общей проблеме алгоритмических решений, - говорит Инь-Taт Ли (Yin-Tat Lee), аспирант MIT и один из соавторов статьи. - Раньше люди нуждались в разработке различных алгоритмов для каждой задачи, а затем они должны были оптимизировать их в течение длительного времени. Теперь мы говорим, если для решения многих задач есть один алгоритм, тогда, практически, мы можем попытаться оптимизировать один алгоритм вместо многих, и у нас будет больше шансов получить более быстрые алгоритмы для многих задач».

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

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

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

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

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

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

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

Они также описали новый способ адаптации методов отсекающей плоскости к конкретным типам задач оптимизации, с такими названиями, как субмодулярная минимизация, субмодулярный поток, пересечения матроидов и полудетерминированное программирование. И для многих из этих случаев они сообщают о значительных улучшениях в эффективности, от времени работы, которое уменьшается с пятой или шестой степени числа переменных (n5 или n6, на языке информатики) вплоть до второй или третьей степени (п2 или n3).

+11
голос

Напечатать Отправить другу

Читайте также

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT