В лаборатории теории игр разработана новая библиотека для топологического анализа данных

Заместитель заведующего лабораторией Константин Сорокин совместно с коллегами опубликовал программную библиотеку qfcore для работы с большими наборами данных и препринт A data structure for quotient flag complexes представляющий инструментарий для топологического анализа данных.

В мире науки о данных исследователи часто пытаются понять форму информации. Они берут огромные облака точек (например, звёзды в галактике, гены в клетке или клиентов на рынке) и соединяют ближайшие точки, образуя сетку из треугольников, тетраэдров и многомерных фигур. Эта сетка, известная как флаговый комплекс, служит своего рода скелетом, который выявляет скрытые в данных дыры, петли и пустоты. Чтобы разобраться в этих формах, учёные используют стандартный инструмент, называемый симплициальным деревом (simplex tree), по сути, очень эффективную картотеку. Поскольку правила, которым подчиняются такие формы, строги, картотеке не нужно хранить каждую связь: достаточно знать, какие точки соединены, а остальная структура восстанавливается автоматически. Такая экономия позволяет компьютерам обрабатывать огромные наборы данных, которые иначе были бы слишком велики.

Однако реальные данные редко бывают статичными. Иногда известно, что часть данных неважна или избыточна, и учёные хотят стянуть её в одну точку, чтобы упростить анализ. Представьте, что вы берёте запутанный клубок верёвки и сплющиваете определённую петлю до одной точки. Остальная верёвка остаётся на месте, но её связи с этой точкой меняются. Эта операция, называемая факторизацией (quotient), создаёт новую форму, для которой прежние правила больше не действуют. Аккуратная картотека, работавшая раньше, перестаёт работать, потому что у новой формы есть петли и связи, которые нельзя угадать, просто глядя на точки. Возникает вопрос: как эффективно хранить эту новую, изменённую форму, не потеряв информацию, необходимую для понимания её истинной структуры?

Группа исследователей разработала новую структуру данных, названную QF-деревом (QF-tree), специально для работы с такими «стянутыми» формами. Их работа посвящена фундаментальной проблеме: когда вы стягиваете часть сложной формы, оставшиеся фрагменты прикрепляются друг к другу способами, которые уже не очевидны. Простое ребро может превратиться в петлю, а треугольник может оказаться приклеенным к одной линии. Исследователи доказали, что если стягиваемая часть подчиняется определённому геометрическому правилу, то есть состоит из всех возможных связей между своими точками, то новая форма сохраняет предсказуемый порядок. Они обнаружили, что в таких случаях не нужно хранить всю новую форму целиком, чтобы знать, что она собой представляет. Вместо этого достаточно отслеживать лишь небольшие фрагменты, а именно те, у которых не более трёх вершин, а остальное компьютер может восстановить. Это существенная экономия: требования к памяти растут не вместе с размером всей формы, а лишь вместе со сложностью её мельчайших «строительных блоков».

Команда также обнаружила точный порог, при котором новый метод оказывается лучше прежнего способа решения таких задач. Традиционно, если учёные хотели упростить форму, они присоединяли конус к той части, которую хотели стянуть. Получалась гомотопически эквивалентная модель, которую проще хранить, но которая математически отличается в деталях. Исследователи подсчитали, что если стягиваемая часть составляет больше определённой доли всей формы (а именно доли, определяемой средним числом связей у каждого из оставшихся элементов), то новый метод на основе QF-дерева расходует меньше памяти, чем метод с конусом. В тестах с миллионами точек данных новый метод стабильно занимал меньше места, когда стягиваемая часть была достаточно велика, а предсказанная точка пересечения с высокой точностью совпала с реальными измерениями.

Помимо хранения, исследователи создали программную библиотеку, позволяющую выполнять эти операции локально. Вместо того чтобы заново перестраивать всю форму каждый раз, когда стягивается небольшая часть, система может обновлять только затронутую область, которая часто представляет собой тонкую оболочку вокруг стянутого участка. Это делает процесс невероятно быстрым, особенно для больших наборов данных. В экспериментах поддержание формы локально оказалось в сотни раз дешевле, чем её перестроение с нуля. Кроме того, когда учёным требовалось выполнить сложные вычисления на получившейся форме, например, проанализировать петли и дыры, чтобы понять топологию данных, делать это на сохранённом факторе оказалось значительно быстрее, чем начинать заново с исходных, не стянутых данных. Библиотека даже допускает динамические изменения: исследователи могут добавлять и удалять точки и связи, сохраняя структуру целостной, а также вычислять фундаментальные свойства, такие как число дыр или способы образования петель.

Работа также проясняет, что происходит при нарушении правил. Если стягиваемая часть не содержит всех связей между своими точками, новая форма может стать нерегулярной и непредсказуемой, утратив те хорошие свойства, которые делают её удобной для хранения. Исследователи показали, что в таких случаях простая картотека не работает и требуются более сложные данные. Они предложили чёткий критерий для проверки того, останется ли форма регулярной после стягивания: если каждое ребро, соединяющее две точки в стягиваемой области, также принадлежит самой этой области, то новая форма будет «хорошо себя вести». Это знание помогает учёным решать, когда можно безопасно использовать эффективный метод хранения, а когда нужно действовать осторожнее.

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