Представлена CLIPPER: теоретико-графическая структура для надежной ассоциации данных

Представлена CLIPPER: теоретико-графическая структура для надежной ассоциации данных Источник фото: pixabay.com

Ученые представили CLIPPER – структуру для надежной ассоциации данных в присутствии шума и выбросов. Они сформулировали проблему в рамках теории графов, используя понятие геометрической согласованности.

Современные системы, которые используют эту структуру, используют либо методы комбинаторной оптимизации, которые плохо масштабируются для задач большого размера, либо используют эвристические приближения, которые обеспечивают низкую точность в режимах с высоким уровнем шума и высокими выбросами.

CLIPPER использует ослабление комбинаторной проблемы и возвращает решения, которые гарантированно соответствуют оптимумам исходной проблемы. Низкая временная сложность достигается за счет эффективного подхода спроектированного градиентного подъема.

Эксперименты показывают, что CLIPPER поддерживает стабильно низкое время выполнения задач (15 мс), тогда как точным методам может потребоваться до 24 секунд даже для небольших задач с 200 ассоциациями.

При оценке зашумленных проблем с регистрацией облака точек, CLIPPER достигает 100% точности и 98% отзыва в режимах 90% выбросов, тогда как конкурирующие алгоритмы начинают становиться неэффективными с 70% выбросов.

Источник: arxiv.org