Що змінюється, коли кластеризація сама вивчає геометрію?

Кластеризація ділить набір даних на групи. Найпоширеніша версія — k-means — обирає центральні точки і відносить кожну точку даних до найближчої. Ця процедура математично еквівалентна квантуванню ймовірнісної міри за Вассерштейном. Квантування Вассерштейна працює всередині фіксованого метричного простору. Геометрія цього простору задана і не змінюється.

Громов-Вассерштейнове квантування змінює премісу. Воно порівнює метричні мірові простори за внутрішніми структурами відстаней, а не за покоординатним розташуванням. Мета — знайти дискретний простір, що наближає і розподіл маси, і парну геометрію оригіналу. Стаття доводить існування розв'язків. Надає також характеристику, що обґрунтовує ітеративний алгоритм, аналогічний методу Ллойда для k-means.

Алгоритм чергує два етапи

Один етап фіксує дискретну геометрію і оновлює розподіл маси. Інший етап фіксує розподіл і оновлює дискретні відстані. Кожна ітерація зменшує ціль Громова-Вассерштейна. Процедура збігається до стаціонарної точки.

Автори реалізували схему і перевірили її на синтетичних і реальних геометріях.

Швидкість квантування показує ціну вивчення геометрії

Для евклідових просторів зі стандартною метрикою стаття розраховує асимптотичну швидкість квантування. Вона збігається з класичною Вассерштейновою до постійного множника, що залежить лише від виміру. Вивчення геометрії не змінює показник поліноміального спаду. Постійний множник кількісно виражає додаткову складність одночасного наближення відстаней.

Експерименти виходять за межі точкових хмар

Метод застосовано до геодезичних відстаней на тривимірних формах. Він також виконує структурне скорочення нейромереж, групуючи вагові матриці з їхньою внутрішньою кореляційною геометрією. У обох випадках алгоритм дає дискретні наближення, якість яких відповідає теоретично оптимальним швидкостям.

Стаття не повідомляє час виконання чи обсяг пам'яті для цих експериментів. Доведення існування припускає компактні метричні мірові простори. Розрахунок швидкості охоплює евклідове геометрії зі стандартною метрикою. Алгоритм гарантує зменшення цільової функції, але не досягнення глобального мінімуму. Числовий розділ не порівнює з усіма існуючими GW-солверами. Автори не обговорюють диференційованість дискретної геометрії за вхідними даними.