Уточненный анализ обобщения для экстремального многоклассового обучения контрастным представлениям с учителем

Аннотация

Контрастивное обучение представлений (CRL) достигло значительных эмпирических успехов во многих дисциплинах машинного обучения, однако его теоретическая сложность выборки остается недостаточно изученной. Существующие анализы обычно предполагают, что входные кортежи распределены независимо и одинаково, что нарушается в большинстве практических условий, где контрастивные кортежи формируются из ограниченного набора размеченных данных, что порождает зависимости между кортежами. Хотя в одной недавней работе эта среда обучения анализировалась с использованием U-статистики для оценки популяционного риска, используемые там методы требуют равномерной концентрации риска каждого класса, из-за чего границы избыточного риска масштабируются в порядке $\rho_{\min}^{-{1}/{2}}$, где $\rho_{\min}$ обозначает вероятность самого редкого класса. Такая зависимость может быть чрезмерно пессимистичной в условиях экстремальной многоклассовости, где существует множество редких классов, которые вносят минимальный вклад в общий популяционный риск. Наш вклад заключается в двух аспектах. Во-первых, мы улучшаем предыдущую работу и доказываем границу со сложностью выборки того же порядка, что и количество классов $R$, независимо от распределения по классам. Кроме того, мы формулируем другой оценщик, который учитывает концентрацию риска по классам, что позволяет получить более точные границы в сценариях экстремального многоклассового обучения, особенно там, где распределения классов имеют «длинный хвост». При выполнении мягких допущений относительно распределений классов результирующая сложность выборки составляет $\mathcal{{O}}(k)$, где $k$ — это количество выборок на кортеж..

1 Введение

Эффективность моделей машинного обучения критически зависит от представления данных. В многоклассовой классификации эффективные представления обычно способствуют компактности внутри класса и разделимости между классами. Контрастивное обучение представлений (CRL) поэтому стало популярным подходом для изучения структурированных представлений из необработанных данных перед выполнением последующих задач. Несмотря на эмпирический успех, теоретическое понимание CRL все еще находится на ранней стадии. Существующие анализы границ избыточного риска, такие как article:arora19 и article:lei2023, обычно предполагают, что неразмеченные входные $(k+2)$-кортежи извлекаются независимо и одинаково распределенно из неизвестного распределения. Хотя это удобно для анализа, данное допущение может не отражать практические конвейеры CRL. Во многих реальных реализациях контрастивные кортежи формируются из конечного набора размеченных примеров (article:sohn2016; article:khosla2020; article:dejiao2021), что приводит к повторному использованию точек данных в разных кортежах, тем самым нарушая допущение о независимости..

Для явного моделирования зависимостей кортежей в контролируемом CRL, article:hieu2025 представили оценщик на основе U-статистики, который разлагает совокупный риск на сумму рисков по классам, а затем оценивает каждый компонент независимо (см. Eqn. (LABEL:eq:hieu_ledent_estimator)). Хотя эта формулировка является естественной и эффективной при умеренном количестве классов, она неявно связывает общую сложность выборки с наихудшей ошибкой оценки по классам. В частности, их анализ требует, чтобы все оценщики риска по классам концентрировались одновременно, что приводит к сложности выборки, которая масштабируется с $\rho_{\min}^{-1}$, где $\rho_{\min}$ обозначает вероятность самого редкого класса. Как следствие, граница становится чрезмерно пессимистичной в режимах с большим количеством классов, где $\rho_{\min}$ неизбежно мала, и сводится к зависимости от количества классов $R$ только в ограничивающем случае идеально сбалансированных распределений классов..

Наш первый вклад ослабляет это требование наихудшего случая, допуская неоднородную точность для оценок по классам. Интуитивно понятно, что классы с незначительным вкладом в популяционный риск не требуют оценки с той же точностью, что и доминирующие. Это устраняет паразитическую зависимость от $\rho_{\min}$ и дает границы, зависящие от $R$, независимо от распределения классов. Тем не менее, даже этот масштаб остается пессимистичным в экстремальных многоклассовых условиях, где $R$ очень велико, и это контрастирует с классическими результатами по границам избыточного риска для обучения $k$-кортежей, где сложность выборки зависит только от размера кортежа $k$ (article:clemencon2008; journal:clemencon2016). Это несоответствие предполагает, что контроль оценок по классам, даже в совокупности, является фундаментально субоптимальным. Поэтому мы вводим совершенно иную формулировку U-статистики (см. Eqn. (LABEL:eq:natural_estimator)), которая обеспечивает совместную концентрацию по классам. Результирующая сложность выборки масштабируется как $k(1-\tau)^{2}$, где $\tau$ — общая вероятность коллизии классов (см., например, article:ash2022; article:awasthi2022 или article:arora19). В частности, когда отрицательные примеры выбираются без исключения положительных классов, $\tau$ представляет общую вероятность того, что среди выбранных отрицательных примеров существует хотя бы один образец положительного класса (см. Eqn. (LABEL:eq:collision_probability)). В экстремальном многоклассовом режиме $\tau\to 0$, что восстанавливает зависимость только от $k$ и согласуется с установленными результатами по обучению кортежей..

2 Связанные работы

Эмпирическая минимизация U-статистик: U-статистики были введены article:hoeffding1948 для оценки параметров с использованием симметричных ядер. Позднее концентрационные свойства U-статистик были строго проанализированы article:ginezinn1984 и article:arconesgine1993, что заложило основу для работ в теории статистического обучения, где функции потерь зависят от двух или более выборок. Концентрационные неравенства для U-статистик использовались во многих дисциплинах машинного обучения, включая ранжирование (article:clemencon2008), метрическое обучение (article:Cao2016; article:jin2009), попарное обучение (article:yleiregularizedpairwise2018; article:yleiledent2020), кластеризацию (article:liliu2021) и самообучение (article:haochen2021).

Обобщение в режиме i.i.d. кортежей: Структура i.i.d. кортежей была представлена article:arora19, которые формализовали неконтролируемый риск для контрастивного обучения. Без учета зависимости от класса функций их границы избыточного риска масштабируются как $\mathcal{O}(\sqrt{{k}/{\mathrm{N}}})$, где $k$ обозначает количество отрицательных примеров, а ${\mathrm{N}}$ — количество i.i.d. кортежей, доступных обучающемуся. Используя такие инструменты, как сложность Радемахера для худшего случая и fat-shattering dimension, article:lei2023 впоследствии улучшили эту зависимость до $\widetilde{\mathcal{O}}(\sqrt{{1}/{\mathrm{N}}})$. Мы отмечаем, что в этих работах «сложность выборки» выражается через количество $\mathrm{N}$ необходимых $(k+2)$-кортежей (где каждый кортеж является одним «примером»), в то время как в нашей работе она относится к количеству $N$ необходимых размеченных точек данных, которые впоследствии используются для формирования кортежей без коллизий. Следовательно, сложность выборки $\widetilde{\mathcal{O}}(k)$ в формулировке контролируемого CRL сопоставима со сложностью выборки $\widetilde{\mathcal{O}}(1)$ в режиме i.i.d. кортежей. Действительно, этого и следует ожидать от аргумента типа Хефдинга при чисто кортежном обучении (без ограничений на коллизии), поскольку $\mathcal{O}({N}/{k})$ кортежей могут быть сформированы из $N$ примеров. Впоследствии работа article:arora19 была расширена на другие настройки CRL, такие как состязательное CRL (article:xinandwei2023; article:ghanooni2024), PAC-Байесовский анализ и глубокое CRL (article:nozawa2020; article:nozawa2021; article:alves2024; article:hieu2024). Помимо обобщения, предыдущие работы, вдохновленные режимом i.i.d., также исследуют другие аспекты теории контрастивного обучения, такие как роль отрицательных примеров (article:ash2022; article:awasthi2022; bao2022surrogate), смягчение влияния ложных признаков в CRL (article:ghanooni2025) и влияние неконтролируемого риска на последующие задачи (article:arora19; article:chuang2020; article:liliu2021; bao2022surrogate; article:huang2023; cui2025inclusive; article:cui2025)⟧.

Теоретический анализ для SS-CRL: Значительный объем работ, вдохновленных article:arora19, исследует обобщение и другие теоретические аспекты самообучающегося CRL. Например, article:wang2022 предложили теорию перекрытия аугментаций, предполагая, что агрессивная аугментация данных может неявно улучшить внутриклассовую компактность. В аналогичном ключе article:cui2025 изучают, как аугментация влияет на производительность последующих задач, связывая контролируемый риск с эмпирическим самообучающимся риском (по набору i.i.d. кортежей) и ожидаемым расстоянием аугментации для одного класса или одного экземпляра. cui2025inclusive предоставляют как теоретические, так и практические выводы о варианте контролируемого CRL с неколлизионными i.i.d. кортежами с шумом в метках. article:huang2023 изучили влияние самообучающегося риска на классификацию путем ограничения частоты ошибок классификаторов ближайшего соседа, построенных поверх функций представления с использованием вероятности рассогласования. article:nozawa2021 предоставили теоретическое объяснение того, почему использование большого количества отрицательных примеров улучшает производительность последующих задач. В article:haochen2021 авторы установили гарантии для избыточного контрастивного риска для функций потерь от двух аргументов, построенных из фиксированного пула неразмеченных выборок посредством независимой аугментации обоих образцов. Хотя это включает U-статистику второго порядка, данная работа не накладывает ограничений на допустимые пары/кортежи с точки зрения коллизии классов, что делает концентрацию неконтролируемого риска прямолинейной: основной вклад заключается во взаимосвязи между контрастивным риском и риском классификации линейного зонда при структурных предположениях об информативности генерации аугментации данных. Их структура была позже расширена до других анализов обобщения для вариантов SS-CRL, включая адаптацию домена (article:shen2022), слабоконтролируемое обучение (article:cui2023), мультимодальное обучение (article:zhang2023multimodal)⟧.

Обобщение в контролируемом CRL: article:hieu2025 исследовали условия CRL, где входные кортежи выбираются из конечного пула размеченных выборок. В этом режиме авторы предложили формулировку U-статистики, которая оценивает каждый контрастивный риск по классам отдельно. В их анализе требуется, чтобы все оценки по классам сходились с одинаковой точностью, что приводит к зависимости от $\rho_{\min}$, наименьшей вероятности класса. Для нашего оценщика мы достигаем зависимости от $R$. Мы также достигаем более высокой скорости $k$ за счет построения принципиально иного оценщика и анализа..

3 Предварительные сведения

3.1 Определения и обозначения

Пусть $\mathcal{X}$ — пространство входных данных, а $[R]=\{1,\dots,R\}$ — набор меток. Нам дан (размеченный) набор данных $S=\left\{X_{j}\right\}_{j=1}^{N}\sim\mathcal{\bar{D}}^{\otimes N}$, где $\mathcal{\bar{D}}:=\sum_{r=1}^{R}\rho_{r}\mathcal{D}_{r}$ представляет собой смесь распределений, в которой $\rho_{1},\dots,\rho_{R}$ обозначает вероятности классов, а $\mathcal{D}_{r}$ — условные распределения классов на $\mathcal{X}$. В рамках обучения с учителем CRL мы стремимся оценить риск, связанный с некоторой контрастивной функцией потерь, используя доступные размеченные точки данных. В частности, для определенной функции представления $f\in\mathcal{F}$, где $\mathcal{F}$ — это заданный класс функций (например, нейронные сети, линейные отображения и т. д.), мы определяем $\ell_{\phi,f}:\mathcal{X}^{k+2}\to\mathbb{R}_{+}$ как кортежную функцию потерь, вычисляемую на представлениях, созданных $f$, следующим образом:

$$\ell_{\phi,f}\left(X,X^{+},\left\{X_{i}^{-}\right\}_{i=1}^{k}\right)=$$ (1)

$$\qquad\qquad\phi\Big(\Big\{f(X)^{\top}\left[f(X^{+})-f(X_{i}^{-})\right]\Big\}_{i=1}^{k}\Big),$$

где $k\geqslant 1$ — количество отрицательных примеров, а $\phi:\mathbb{R}^{k}\to\mathbb{R}_{+}$ — векторная функция, часто называемая контрастивной функцией потерь. Например, если мы используем логистическую функцию потерь (article:sohn2016) для обучения, то для всех $k$-мерных векторов ${\bf v}=(v_{1},\dots,v_{k})^{\top}$ мы имеем $\phi({\bf v}):=\ln\Big(1+\sum_{i=1}^{k}e^{-v_{i}}\Big)$. В данной статье нас интересует ограничение равномерного избыточного риска (по классу функций представления), связанного с контрастивным риском, который определяется следующим образом.

Definition 3.1 (Популяционный контрастивный риск).

Пусть $f\in\mathcal{F}$ будет функцией представления, а $\phi:\mathbb{R}^{k}\to\mathbb{R}_{+}$ — контрастивной функцией потерь (где $k\geqslant 1$ — количество отрицательных примеров). Тогда контрастивный риск $f$, обозначаемый $\mathrm{L}_{\phi}(f)$, определяется как:

$$\mathrm{L}_{\phi}(f)=$$ (2)

$$\underset{r\sim\rho}{\mathbb{E}}\underset{\begin{subarray}{c}X,X^{+}\sim\mathcal{D}_{r}^{\otimes 2}\\ \left\{X_{i}^{-}\right\}_{i=1}^{k}\sim\mathcal{\bar{D}}_{r}^{\otimes k}\end{subarray}}{\mathbb{E}}\left[\ell_{\phi,f}\left(X,X^{+},\left\{X_{i}^{-}\right\}_{i=1}^{k}\right)\right],$$

где $\rho$ — это дискретное распределение по классам, которое присваивает вероятность $\rho_{r}$ классу $r$ для всех $r\in[R]$, а $\mathcal{\bar{D}}_{r}$ — это распределение по $\mathcal{X}$, определяемое следующей смесью:

$$\mathcal{\bar{D}}_{r}:=\frac{1}{1-\rho_{r}}\sum_{q\neq r}\rho_{q}\mathcal{D}_{q},$$ (3)

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

Remark 3.2.

Определение в Eqn. (2) отличается от определения отрицательного распределения, используемого в article:arora19. Наша формулировка запрещает отрицательным образцам $\left\{X_{i}^{-}\right\}_{i=1}^{k}$ иметь общие классы с парой якорь–положительный $(X,X^{+})$, тогда как article:arora19 допускают такие столкновения классов, выбирая отрицательные образцы i.i.d. из полной смеси $\bar{\mathcal{D}}$, а не $\bar{\mathcal{D}}_{r}$. В случае самообучения (article:chen2020; He_2020_CVPR; Caron20; article:cui2025) столкновение классов часто неизбежно, поскольку метки недоступны для его предотвращения. С другой стороны, в контролируемом CRL естественно избегать столкновения классов, так как было показано, что это улучшает производительность (article:khosla2020; article:chuang2020; article:robinson2021; chen2022incrementalfalsenegativedetection; article:huynh2022). Поэтому это основной параметр, который мы исследуем. Тем не менее, мы также предоставляем гарантию избыточного риска (Thm. LABEL:thm:concentration_of_bar_Uomega) для риска с допущением столкновений в article:arora19, хотя этот результат в основном служит промежуточным шагом для обеспечения гарантий избыточного риска для желаемого риска $\mathrm{L}_{\phi}$⟧.

Обозначения: На протяжении всей данной рукописи мы используем ${\mathbb{E}}_{X\sim\mu}[\cdot]$ для обозначения математического ожидания по некоторому распределению $\mu$ или просто $\mathbb{E}[\cdot]$, когда распределение очевидно в данном контексте. Кроме того, мы используем $\widehat{\mathbb{E}}_{V}[\cdot]$ или $\widehat{\mathbb{E}}_{v\sim V}[\cdot]$ для обозначения эмпирического среднего по элементам $v$ некоторого множества $V$. Например, $\widehat{\mathbb{E}}_{V}[g]=\widehat{\mathbb{E}}_{v\sim V}[g(v)]:=\frac{1}{|V|}\sum_{v\in V}g(v)$. Для каждого $r\in[R]$ мы также обозначаем $S_{r}\subseteq S$ как множество размеченных точек данных, принадлежащих классу $r$, $N_{r}:=|S_{r}|$ и $\widehat{\rho}_{r}:=\frac{N_{r}}{N}$. Наконец, мы предполагаем, что контрастивная функция потерь равномерно ограничена, то есть $|\ell_{\phi,f}|\leqslant\mathcal{B}$ для всех $f\in\mathcal{F}$ для некоторого $\mathcal{B}\in\mathbb{R}_{+}$. Для удобства читателя мы приводим исчерпывающий список обозначений в приложении (Table LABEL:tab:notations).

3.2 Вклад

В данной работе мы заинтересованы в формулировании оценок для популяционного риска без коллизий классов, определенного в уравнении (2), и ограничении соответствующего равномерного избыточного риска. Наши вклады можно резюмировать следующим образом:

1. ⟦ Мы предоставляем уточненную гарантию избыточного риска для оценки U-Statistic, предложенной в article:hieu2025, путем полного исключения зависимости от $\rho_{\min}^{-1}$, вероятности редчайшего класса, из сложности выборки. Вводя неравномерную точность для концентрации каждой классовой U-Statistic, мы доказываем, что сложность выборки их оценки масштабируется линейно с $R$, количеством классов, независимо от структуры распределения классов..
2. ⟦ Мы предлагаем иную формулу U-Statistic, вдохновленную устранением смещения риска генеральной совокупности без учителя, используемого в предыдущих работах в режиме i.i.d. кортежей (article:arora19; article:lei2023), в котором произвольно допускается коллизия классов. В частности, мы разлагаем желаемый риск без коллизий на комбинацию рисков, обусловленных наличием по крайней мере одного и нуля столкнувшихся отрицательных образцов (Eqn. (LABEL:eq:decomposed_population_contrastive_risk)). Затем мы аппроксимируем каждый компонент отдельно для формулировки итогового оценщика.
3. ⟦ Мы доказываем, что предложенная в данной работе U-статистика обеспечивает выборочную сложность, которая масштабируется с $k(1-\tau)^{2}$, где $\tau$ — это вероятность коллизии классов в генеральной совокупности (уравнение ⟦LABEL:eq:collision_probability⟧). В типичных сценариях с экстремально большим количеством классов, где все вероятности классов малы, вероятность коллизии $\tau$ приблизительно равна нулю, а выборочная сложность восстанавливает скорость $\mathcal{{O}}(k)$. Таким образом, данный тип границы особенно полезен для задач обучения представлений с большим количеством классов, где $R$ значительно больше, чем $k$. Более того, для определенных несбалансированных распределений классов с «длинным хвостом» мы имеем $1-\tau\in\Omega(1)$ с высокой вероятностью. Следовательно, доминирующая зависимость от $k$ остается неизменной..

Обзор наших основных результатов (суммированных в показателях сложности выборки) в сравнении с предыдущими работами представлен в Таблице 3.2. Кроме того, мы приводим более подробный обзор литературы в Приложении LABEL:sec:summary_of_literature. Более того, в Приложении LABEL:sec:proof_discussion мы представляем краткое обсуждение различий между нашим анализом и предыдущими работами, а также сопутствующих дополнительных технических трудностей..

⟦Table 1: Сравнение нашей работы с предыдущим результатом с точки зрения сложности выборки. Для простоты мы предполагаем, что верхняя граница функции потерь $\mathcal{B}=1$. Обозначение игнорирует полилогарифмические множители всех соответствующих величин ($\mathfrak{C}^{2}_{N}$, $R$, $k$, ${1}/{(1-\tau)}$ и вероятность отказа $\Delta$). Для $\mathcal{L}$-липшицевых параметризованных классов функций $\mathcal{H}$ член сложности $\mathfrak{C}_{N}(\mathcal{H})$ растет не более чем как $\mathcal{\widetilde{O}}[(W)^{\frac{1}{2}}]$, где $W$ обозначает количество параметров, а нотация $\widetilde{\mathcal{O}}$ скрывает полилогарифмические множители $\mathcal{L}$ и $W$. Вероятность $\gamma_{k}$ определена в Eqn. (LABEL:eq:gamma_k).

Reference	Est.	Default	$\gamma_{k}\in\Omega(1)$	Relevant quantity
article:hieu2025	$U_{N}^{\mathrm{hl}}$	$[\mathfrak{C}^{2}_{N}(\mathcal{H})+1]\max\left[\rho_{\min}^{-1},(1-\rho_{\max})^{-1}\right]$		$\rho_{\min}:=\min_{r\in[R]}\rho_{r}$ $\rho_{\max}:=\max_{r\in[R]}\rho_{r}$
This Work	$U_{N}^{\mathrm{hl}}$	$\mathfrak{C}^{2}_{N}(\mathcal{H})[\widehat{\theta}_{k+2}R+(1-\widehat{\theta}_{k+2})^{2}k]\ +$ $[R+k^{2}]$ (Theorem LABEL:thm:refined_hieu_ledent_general/LABEL:thm:refined_hieu_ledent_general_appendix)	$\mathfrak{C}^{2}_{N}(\mathcal{H})R\ +$ $[R+k^{2}]$ (Theorem LABEL:thm:refined_hieu_ledent_small_probabilities)	$\widehat{\theta}_{k+2}:={\mathbb{P}_{\rho}}\big[\rho_{r}\leqslant\frac{2}{k+2}\big]$
This Work