Распознавание гомотопического типа объекта с помощью дифференциально-топологических инвариантов аппроксимирующего отображения

Курочкин С.В.

Национальный исследовательский университет «Высшая школа экономики», Москва, Россия

Аннотация:
Предложен новый метод топологического анализа данных, позволяющий получить информацию о гомотопическом типе анализируемого объекта. В отличие от наиболее хорошо разработанных и широко применяемых методов, использующих понятие персистентных гомологий, данный метод основан на анализе дифференциальных инвариантов аппроксимирующего отображения. Таким образом, в противоположность комбинаторно-топологическому подходу, используются методы дифференциальной топологии и прямая аналогия с основным результатом теории Морса. При этом аппроксимирующее графический объект гладкое отображение может быть построено с использованием общедоступного инструментария, например, нейронной сети. Доказано, в частности, что метод позволяет полностью распознать гомотопический тип объекта на плоскости: топологическая степень некоторого вспомогательного отображения и количество окружностей в гомотопически эквивалентном представлении объекта в виде букета связаны соотношением. Работа алгоритма продемонстрирована на примере символов из базы данных MNIST и их трансформаций. Рассмотрены обобщения и открытые вопросы, возникающие в случае более высоких размерностей.

Ключевые слова:
машинное обучение, топологические инварианты, степень отображения, обработка изображений

Цитирование:
Курочкин, С.В. Распознавание гомотопического типа объекта с помощью дифференциально-топологических инвариантов аппроксимирующего отображения / С.В. Курочкин // Компьютерная оптика. – 2019. – Т. 43, № 4. – С. 611-617. – DOI: 10.18287/2412-6179-2019-43-4-611-617.

Литература:

  1. Carlsson, G. Topology and data / G. Carlsson // Bulletin of the American Mathematical Society. – 2009. – Vol. 46, Issue 2. – P. 255-308. – DOI: 10.1090/S0273-0979-09-01249-X.
  2. Zomorodian, A. Topological data analysis / A. Zomorodian. – In Book: Advances in applied and computational topology / ed. by A. Zomorodian. – American Mathematical Society, 2012. – P. 1-40. – ISBN: 978-0-8218-5327-6.
  3. Mervis, J. What makes DARPA tick? / J. Mervis // Science. – 2016. – Vol. 351, Issue 6273. – P. 549-553.
  4. DARPA – Frontiers of engineering [Electronical Resource]. – URL: https://www.naefrontiers.org/File.aspx?id=22017 (request date 30.10.2018).
  5. Рогозин, Д.О. Высокие технологии в США: Опыт министерства обороны и других ведомств. / Д.О. Рогозин, И.А. Шеремет, С.В. Гарбук, А.М. Губинский. – М.: МГУ, 2013. – 380 с.
  6. Edelsbrunner, H. Topological persistence and simplification / H. Edelsbrunner, D. Letscher, A. Zomorodian // Discrete and Computational Geometry. – 2002. – Vol. 28, Issue 4. – P. 511-533. – DOI: 10.1007/s00454-002-2885-2.
  7. Adamaszek, M. On homotopy types of euclidean rips complexes [Electronical Resource] / M. Adamaszek, F. Frick, A. Vakili. – URL: https://arxiv.org/pdf/1602.04131.pdf (request date 30.10.2018).
  8. Постников, М.М. Введение в теорию Морса / М.М. Постников. – М.: Наука, 1971.
  9. Фоменко, А.Т. Курс гомотопической топологии / А.Т. Фоменко, Д.Б. Фукс. – М.: Наука, 1989.
  10. Демидов, Е.Е. Нелинейный корреляционный анализ / Е.Е. Демидов, Ю.В. Даревская, О.А. Моренков, А.А. Товчигречко // Обозрение прикладной и промышленной математики. – 1999. – Том 6, Вып. 1. – С. 4-57.
  11. Chazal, F. A sampling theory for compact sets in Euclidean space / F. Chazal, D. Cohen-Steiner, A. Lieutier // Discete and Computational Geometry. – 2009. – Vol. 41, Issue 3. – P. 461-479. – DOI: 10.1007/s00454-009-9144-8.
  12. Chazal, F. High-dimensional topological data analysis. Handbook of discrete and computational geometry. – Boca Raton, FL: CRC Press, 2017. – ISBN: 978-1-4987-1139-5.
  13. Ribeiro, M. “Why should i trust you?” Explaining the predictions of any classifier [Electronical Resource] / M. Ribeiro, S. Singh, C. Guestrin. – URL: https://arxiv.org/abs/1602.04938 (request date 30.10.2018).
  14. Katok A. Introduction to modern topology and geometry / A. Katok, A. Sossinsky [Electronical Resource]. – URL: http://www.personal.psu.edu/axk29/TOPOLOGY/ (request date 30.10.2018).
  15. Erickson J. CS 598: Computational topology. Spring 2013 [Electronical Resource]. – URL: http://jeffe.cs.illi­nois.edu/teaching/comptop/index.html (request date 30.10.2018).
  16. The MNIST database of handwritten digits [Electronical Resource]. – URL: http://yann.lecun.com/exdb/mnist/ (request date 30.10.2018).
  17. Hennig, C. Dissolution point and isolation robustness: Robustness criteria for general cluster analysis methods / C. Hennig // Journal of Multivariate Analysis. – 2008. – Vol. 99, Issue 6. – P. 1154-1176. – DOI: 10.1016/j.jmva.2007.07.002.

     


© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20