Представляем GIST: следующий этап в интеллектуальном отборе проб.

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

Быстрые ссылки

• Бумага
• Делиться
  • Скопировать ссылку ×

Современное машинное обучение (МО) открыло беспрецедентные возможности, но ценой необходимости обработки все более масштабных и сложных наборов данных. От больших языковых моделей (ЛСМ) до систем компьютерного зрения существует общая проблема: обработка огромного количества данных, которая обходится дорого.

Это требует выбора подмножества — задачи выбора меньшей, репрезентативной группы точек данных из полного набора данных для типичной задачи обучения (а не тонкой настройки). Тогда возникает вопрос: как мы можем быть уверены, что это подмножество содержит достаточно информации для обучения точной модели?

На конференции NeurIPS 2025 мы представили алгоритм Greedy Independent Set Thresholding (GIST), который помогает решить эту проблему, балансируя «разнообразие» данных (гарантируя, что выбранные данные не являются избыточными) и «полезность» данных (данные, которые релевантны и полезны для задачи). GIST не только превосходит современные эталонные задачи, такие как классификация изображений, но и делает это с математической гарантией качества своего решения.

Конфликт: Почему разумная выборка — это сложно

При выборе подмножества данных исследователям необходимо сбалансировать две часто противоречащие друг другу цели: разнообразие и полезность. Обеспечение разнообразия данных гарантирует, что выбранные точки не будут избыточными. Полезность измеряет общую полезность или информационную ценность выбранного подмножества.

Для обеспечения разнообразия мы фокусируемся на максимизации минимального расстояния (обычно в пространстве вложений) между любыми двумя выбранными точками данных, что также известно как разнообразие по принципу максимума-минимума. Если вы выбираете две очень похожие точки данных (например, две почти идентичные фотографии золотистого ретривера), ваше разнообразие будет низким. Разнообразие по принципу максимума-минимума заставляет вас выбирать точки, которые максимально удалены друг от друга, минимизируя избыточность и обеспечивая широкое покрытие ландшафта данных. Для обеспечения полезности мы фокусируемся на классе монотонных субмодулярных функций, которые стремятся максимизировать общую уникальную информацию, покрываемую подмножеством.

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

Этот внутренний конфликт требует продуманной стратегии приближения.

Как работает GIST

Поскольку поиск идеального подмножества нецелесообразен, цель смещается в сторону поиска алгоритма с доказуемой гарантией приближения — математической страховочной сетью, которая гарантирует, что решение всегда будет близко к истинному оптимуму. Именно здесь GIST предлагает свое новаторское решение.

GIST разбивает задачу обеспечения разнообразия и полезности на ряд более простых, но связанных между собой задач оптимизации:

1. Определение порогового значения компонента разнообразия.

GIST начинает с временной изоляции компонента разнообразия. Вместо того чтобы пытаться максимизировать минимальное расстояние между всеми точками (самая сложная часть), GIST решает более простой вопрос: «Для определенного фиксированного минимального расстояния, какое наилучшее подмножество данных мы можем выбрать?»

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

GIST ищет точку с наивысшим баллом, которая ещё не находится в чьей-либо «пузыре». Затем он выбирает наиболее высокобалльные «VIP»-точки данных (точки с цифрами) и обводит их «запретной зоной», чтобы гарантировать высокое качество и разнообразие окончательного выбора. Чем выше число, тем ценнее данный фрагмент данных для обучения.

2. Аппроксимация независимого множества

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

Поскольку задача о максимальном независимом множестве сама по себе является NP-полной (то есть широко распространено мнение, что не существует эффективного алгоритма для нахождения абсолютно «идеального» ответа для огромного набора данных) и не допускает разумных алгоритмов аппроксимации, GIST использует тщательно разработанный двухкритериальный жадный алгоритм для эффективной аппроксимации решения. Он перебирает множество возможных пороговых значений расстояния, решая соответствующую задачу о независимом множестве и в конечном итоге выбирая лучшее решение, найденное при всех пороговых значениях. Для любого минимального расстояния d, достигнутого оптимальным решением, GIST обеспечивает сопоставимую полезность с оптимальной полезностью при пороговом значении расстояния d /2.

Двухкритериальный жадный алгоритм действует как систематический «регулятор», который находит правильный баланс между разнообразием и ценностью данных. Вместо того чтобы гадать, он анализирует фактические расстояния между всеми точками данных, чтобы создать список потенциальных правил размещения. Затем он проверяет эти правила по одному: для каждого правила он «жадно» выбирает наиболее ценные точки, которые может найти, при условии, что они не слишком близки к уже выбранным точкам. Запуская этот процесс для каждого соответствующего расстояния и сравнивая результаты, алгоритм определяет конкретную «оптимальную точку», которая позволяет получить наиболее полезную информацию, обеспечивая при этом максимальное распределение данных.

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

Результаты

Надежные гарантии

Наиболее значимыми результатами являются наши теоретические выводы: GIST — первый алгоритм, предоставляющий надежную, доказуемую гарантию компромисса между разнообразием и полезностью. Алгоритм GIST гарантированно находит подмножество данных, значение которого составляет не менее половины значения абсолютного оптимального решения (подробности см. в статье). Эта надежная гарантия обеспечивает практикующим специалистам необходимую математическую подстраховку, гарантируя, что алгоритм осуществляет эффективный компромисс между максимизацией полезности и обеспечением диверсификации. Кроме того, мы доказываем, что найти подмножество, значение которого превышает 0,56 от оптимального значения, является NP-трудной задачей.

Влияние на реальный мир

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

• Случайный подход: простой и несложный метод, способствующий разнообразию во многих ситуациях и предлагающий эффективные решения.
• Параметр «Margin» выбирает точки данных, в отношении которых модель в данный момент «не уверена» и не заинтересована в выводе разнообразного набора обучающих примеров.
• k -центрирование: выбирает подмножество точек данных таким образом, чтобы каждая точка в исходном, огромном наборе данных была как можно ближе к одному из выбранных представителей. Вместо поиска наиболее важных или интересных точек, оно пытается устранить «слепые зоны».
• Submod: выбирает «важные» точки (полезность), одновременно следя за тем, чтобы они не были «слишком похожи» (разнообразие). Однако он использует несколько устаревший математический способ определения разнообразия, который иногда может быть непоследовательным при больших размерах набора данных.

Затем мы объединили GIST с другими стратегиями, чтобы посмотреть, сможет ли это улучшить ситуацию.

• GIST-margin: Эта стратегия, основанная на «выборе сложных случаев», вынуждена следовать строгим правилам разнообразия GIST. Она гласит: «Выбирайте наиболее запутанные примеры, но я запрещаю вам выбирать два запутанных примера, которые слишком похожи друг на друга».
• GIST-submod: Submod использует структуру GIST для более строгой обработки вопроса разнообразия, чем это было возможно в оригинальном подходе submod .

Выборка данных для классификации изображений

В экспериментах с использованием модели ResNet-56 на таких наборах данных, как ImageNet, GIST продемонстрировал значительные преимущества в выборе подмножества данных за один шаг. Одношаговое уменьшение разрешения данных за один шаг сокращает объем набора данных — обычно изображений, сигналов или многомерных данных — при сохранении важной информации. В отличие от итеративных или многоэтапных процессов, этот подход максимизирует скорость и эффективность и часто используется для снижения вычислительной нагрузки или оптимизации производительности рендеринга в задачах, связанных с графикой.

Точность классификации Top-1 (%) для GIST на ImageNet при использовании различных алгоритмов уменьшения разрешения данных за один проход. Ограничение по количеству элементов ограничивает число выбираемых изображений. Например, если имеется пул из 1,3 миллиона изображений, ограничение по количеству в 10% (k=10%) означает, что алгоритму строго запрещено выбирать более 130 000 изображений для обучения модели.

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

Продолжительность

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

Мы также оценили эффективность подхода «максимальное-минимальное разнообразие» на примере команды, занимающейся ранжированием видео на главной странице YouTube, которая использовала аналогичный принцип для повышения разнообразия видеорекомендаций и, следовательно, улучшения долгосрочной ценности для пользователей.

Заключение: Основа для масштабируемого искусственного интеллекта.

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

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

Благодарности

Мы благодарим Сару Ахмадиан из Google Research; Шрикумара Рамалингама, Джулию ДеСальво и Ги Цитовски из Google DeepMind; а также Чинара Баннерджи, Кристоса Гудроу, Фабио Сольдо и Су-Лин Ву из YouTube, которые внесли свой вклад в эту работу. Мэтью Фарбах, Мортеза Задимогхаддам и Шрикумар Рамалингам внесли равный вклад в этот исследовательский проект.

Источник: research.google