Дискретные задачи размещения в машинном обучении

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