Speaker
Description
Рассматриваются две формальные математические постановки одной из часто решаемых задач машинного обучения - задачи выбора подмножества типичных объектов в метрическом пространстве с помощью FRiS-функции [1]. В первом случае речь идет о задаче классификации, когда объекты обучающей выборки разделены на классы, во втором - о задаче таксономии, в которой принадлежность объекта к тому или иному классу изначально не задается. Для этих задачи доказывается, что они являются NP-трудными в сильном смысле. При этом предполагается, что типичными являются те объекты выборки, на которые похожи объекты того же класса (кластера) и не похожи объекты конкурирующих классов (кластеров).
В случае задачи классификации, к рассматриваемой задаче сводится NP-трудная в сильном смысле задача о p-медиане [2], а в случае задачи таксономии NP-трудная в сильном смысле задача 3D-Matching [3]. Так как доказанная NP-трудность в сильном смысле предполагает невозможность построения точных полиномиальных и псевдо-полиномиальных алгоритмов решения рассматриваемых задач, для этих целей предлагаются приближенные жадные алгоритмы.
Работа выполнена при поддержке программы фундаментальных научных исследований РАН, проект № FWNF-2022-0015.
Список литературы
1. N.G. Zagoruiko, I.А. Borisova, V.V. Dyubanov, О.А. Kutnenko. Methods of recognition based on the function of rival similarity // Pattern Recognition and Image Аnаlysis. – 2008. – Vol. 18, – № 1. – P. 1-6.
2. O. Kariv and S. Hakimi, An algoritmic approach to network Location Problems. The p-medians // SIAM J. of Appl. Math. – 1979. – № 37. – P. 539–560.
3. Garey, M. and Johnson, D. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.
| Секция конференции | Методы искусственного интеллекта и машинного обучения |
|---|
