Новый алгоритм учитывает все возможные решения, чтобы найти лучший ответ
Недавно созданная компьютерная программа работает умнее, а не сложнее, решая задачи быстрее своих предшественников.
Алгоритм предназначен для нахождения наилучшего решения поставленной задачи среди всех возможных вариантов. В то время как другие компьютерные программы отсеивают возможности по очереди, новая программа, представленная 12 июля на Международной конференции по машинному обучению в Стокгольме, исключает множество вариантов сразу.
Например, представьте, что компьютер назначен для составления рекомендаций по фильмам на основе определенного фильма. Идеальный список рекомендаций будет включать предложения, которые похожи на оригинальный фильм, скажем, в одном жанре, но достаточно отличаются друг от друга, чтобы дать зрителю широкий выбор.
Традиционная система рекомендаций будет охватывать всю библиотеку фильмов, с тем чтобы найти фильмы, которые наилучшим образом отвечают этим критериям, и будет добавлять фильмы в свой список рекомендаций один за другим, что является относительно медленным и утомительным процессом.
Напротив, новая программа запускается случайным образом, выбирая много фильмов из библиотеки. Среди этого множества образцов система сохраняет фильмы, которые обеспечивают наилучший баланс между релевантностью оригинальному фильму и разнообразием, и отбрасывает остальные.
Из этого меньшего пула алгоритм снова выбирает фильмы случайным образом и сохраняет только лучшее из группы. Эта стратегия помогает алгоритму строить список намного быстрее.
Новый алгоритм, построенный компьютерными учеными Гарвардского университета Яроном Сингером и Эриком Балкански, собрал предложения к фильмам более чем в 10 раз быстрее, чем стандартная рекомендательная система.
В другом испытании он разработал оптимальные маршруты для такси в Нью-Йорке примерно в шесть раз быстрее, чем обычный автоматический диспетчер.
Эта программа также может ускорить обработку данных для всего, от обнаружения наркотиков до аналитики в социальных сетях и анализа генетических данных.
Больше информации: E. Balkanski and Y. Singer. Approximation guarantees for adaptive sampling. International Conference on Machine Learning. Stockholm, July 12, 2018.