Новый алгоритм сокращает время вычислений на порядки

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

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

Как это работает?

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

Алгоритм Breakthrough использует адаптивную выборку. Он требует O(log n) последовательных шагов и достигает приближения, произвольно близкого к 1/3. При включении параллелизма алгоритм достигает постоянной факторной аппроксимации экспоненциально быстрее любого существующего метода для субмодулярной максимизации.

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

Новый алгоритм же случайным образом сэмплирует набор фильмов, отсеивая те, которые совсем не подходят. Это дает разнообразную коллекцию фильмов (ведь вы не хотите 10 фильмов о Супермене в рекомендациях), похожих на «Звездные войны». Алгоритм продолжает добавлять разнообразие на каждом шаге, пока не наберет достаточно элементов для рекомендации. Ключ к принятию ценных решений на каждом шаге кроется в адаптивном процессе сэмплирования.

Тестирование и применение

Исследователи протестировали свой адаптивный алгоритм на большом наборе данных, содержащем 1 миллион оценок 4000 фильмов от 6000 пользователей. Он успешно рекомендовал персонализированные и разнообразные фильмы для человека в 20 раз быстрее традиционных алгоритмов.

Они также применили этот алгоритм к проблеме диспетчеризации такси — выбрать лучшие локации для обслуживания максимального числа клиентов с ограниченным парком такси. Для 2 миллионов поездок на такси алгоритм работал в 6 раз быстрее передового уровня.

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

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