Реализуемая Байесовская согласованность для общих функций потерь метрик

Дан Цир Коэн Стив Хэннеке Aryeh Kontorovich

Аннотация

Мы изучаем сильную универсальную байесовскую согласованность в реализуемом случае обучения с обобщенными метрическими потерями, расширяя классические характеристики за пределы $0$ - $1$ классификации (Bousquet et al., 2020; Hanneke et al., 2021) и вещественнозначной регрессии (Attias et al., 2024b). Пусть дано пространство экземпляров $(\mathcal{X},\rho)$ , пространство меток $(\mathcal{Y},\ell)$ с возможно неограниченной потерей и класс гипотез $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ ; мы разрешаем реализуемый случай открытой проблемы, представленной в Tsir Cohen & Kontorovich (2022). В частности, мы находим необходимые и достаточные условия для класса гипотез $\mathcal{H}$ , при которых существует правило обучения, не зависящее от распределения, чья риск-функция сходится почти всюду к лучшему в классе риску (который равен нулю) для каждой реализуемой порождающей данные распределения. Наш основной вклад — это точная характеристика в терминах комбинаторного препятствия: Аналогично Attias et al. (2024a), мы вводим понятие бесконечного неубывающего $(\gamma_{k})$ -дерева Литтлстоуна, где $\gamma_{k}\to\infty$ . Это расширяет структуру дерева Литтлстоуна, используемую в Bousquet et al. (2020), на случай метрических потерь.

регрессия; метрическое пространство; согласованность по Байесу; теория обучения

1 Введение

Многие задачи обучения естественным образом выражаются с помощью метрической функции потерь в пространстве меток: одна предсказывает метку $y\in{\mathcal{Y}}$ и подвергается штрафу на величину расстояния $\ell(\hat{y},y)$ . Это охватывает многоклассовое предсказание (дискретные метрики), регрессию (абсолютная потеря), структурированные выходы с потерями типа редактирования и обобщенное предсказание с учетом стоимости. В таких условиях ${\mathcal{Y}}$ обычно бесконечна, а $\ell$ может быть неограниченной. Хотя неограниченные потери являются стандартными в регрессии, они гораздо менее изучены в более общем контексте метрических функций потерь — с самой базовой точки зрения, не зависящей от распределения: когда вообще возможна сильная универсальная согласованность?

Реализуемая сильная универсальная байесовская согласованность.

Зафиксируйте пространство примеров $({\mathcal{X}},\rho)$ , пространство меток $({\mathcal{Y}},\ell)$ (где $\rho$ и $\ell$ — это метрики) и класс гипотез ${\mathcal{H}}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ . $\ell$ — это функция потерь (возможно, неограниченная). Дано i.i.d. выборочное множество $(X_{i},Y_{i})_{i\in[n]}\sim{\bar{\mu}}^{n}$ из неизвестного распределения ${\bar{\mu}}$ на ${\mathcal{X}}\times{\mathcal{Y}}$ , обучающийся выдает предиктор $f_{n}:{\mathcal{X}}\to{\mathcal{Y}}$ и несет риск

R_{{\bar{\mu}}}(f_{n})\ :=\ \mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\,\ell(f_{n}(X),Y).

Мы сосредоточиваемся на реализуемой постановке: ${\bar{\mu}}$ реализуемо по ${\mathcal{H}}$ , если $\inf_{h\in{\mathcal{H}}}R_{{\bar{\mu}}}(h)=0$ .111При сделанном в наших основных результатах предположении о компактном параметризовании (компакт $\Theta$ , $h$ непрерывен по $\theta$ , Лемма 4.3) реализуемость эквивалентна существованию $f^{\star}\in{\mathcal{H}}$ с $Y=f^{\star}(X)$ почти наверное (строгая реализуемость), поскольку инфимум по компактному образу $\Theta$ достигается. Мы используем эту эквивалентность свободно в доказательствах. См. Приложение A.4.5 для дальнейшего обсуждения. Мы ищем правило обучения, не зависящее от распределения, такое что его риск сходится к $0$ почти наверное для любого реализуемого ${\bar{\mu}}$ . Это естественный аналог сильного закона для универсальной согласованности. В условиях ограниченных потерь реализуемость уже является мощным структурным предположением и часто сводит различие между «риск стремится к $0$ » и «ошибки стремятся к $0$ ». Для неограниченных метрических функций потерь это интуитивное понимание рушится очень конкретным образом: обучающийся может совершать ошибки на событиях, чья вероятность убывает с $n$ , однако масштаб этих ошибок может расти настолько быстро, что риск не исчезает (и может даже быть бесконечным). Понимание того, когда такие катастрофические редкособытийные отказы можно избежать равномерно для всех реализуемых распределений, является сутью проблемы.

Почему неограниченные функции потерь труднее на самом деле.

При любой ограниченной по величине потере кажд ошибку стоит не более некоторой постоянной, поэтому управление вероятностью ошибки по сути эквивалентно управлению риском. При обобщенных метрических потерях обучающийся может быть вынужден угадывать между двумя метками, которые крайне далеки друг от друга в областях пространства экземпляров, встречающихся редко, но не являющихся пренебрежимо малыми. Одной только реализуемости недостаточно, чтобы исключить это: противник может «спрятать» бесконечную последовательность все более разнесенных вариантов выбора меток за быстро убывающей вероятностной массой. Это явление отсутствует в теории ограниченных по величине потерь и не отражается чисто распределительными условиями конечности (например, допущения-кандидаты вроде $R^{\star}<\infty$ ); действительно, в разделе 3 мы приводим явный контрпример, показывающий, что такие условия типа конечности не достаточны для гарантии существования любого распределительно-независимого согласованного обучающегося в реализуемом режиме неограниченных по величине потерь.

Основной результат (неформально; см. раздел 4).

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

Неформально, бесконечное неубывающее дерево $(\gamma_{k})$ -Littlestone является полным двоичным деревом экземпляров, глубины $k$ узлы которого допускают две исходящие метки на метрическом расстоянии не менее $\gamma_{k}$ , где $\gamma_{k}\uparrow\infty$ , и такое, что каждая конечная схема разметки от корня до листа реализуема некоторой $h\in{\mathcal{H}}$ (Определение 4.1). При сделанном слабо-компактном предположении о параметризации (Лемма 4.3) это условие для конечных префиксов автоматически гарантирует, что каждый бесконечный путь реализуется одной гипотезой. В частности, контрпример из Раздела 3 естественным образом удовлетворяет этому предположению, демонстрируя, что необучаемость остается возможной даже при нем (см. Приложение A.4.3 для подробностей).

Для метрических потерь (возможно неограниченных) реализуемая сильная универсальная байесовская согласованность возможна для ${\mathcal{H}}$ тогда и только тогда, когда ${\mathcal{H}}$ не содержит бесконечное невозрастающее $(\gamma_{k})$ -дерево Литтлстоуна с $\gamma_{k}\to\infty$ . Кроме того:

⟦(Lower bound.) Если существует такое дерево, то для каждого алгоритма обучения ${\mathcal{A}}$ существует реализуемое распределение ${\bar{\mu}}$ , при котором обучающийся сталкивается с катастрофическими ошибками редких событий; в частности, $\mathop{\mathbb{E}}_{S_{n}\sim{\bar{\mu}}^{n}}[R_{{\bar{\mu}}}({\mathcal{A}}(S_{n}))]=\infty$ для каждого $n$ (Теорема 5.1).
⟦• (Верхняя граница.) Если не существует такого дерева, то имеется явное не зависящее от распределения правило обучения, у которого риск сходится к $0$ почти наверное для каждого реализуемого ${\bar{\mu}}$ (Теорема 6.5).

Архитектура доказательства.

Нижняя граница преобразует дерево с неограниченным разрывом в реализуемое распределение на случайном пути от корня к листу: на глубинах выборка пропускает (которые существуют для каждого конечного $n$ ), обучающийся вынужден угадывать между двумя метками, разделенными $\gamma_{k}$ , и если $\gamma_{k}$ растет достаточно быстро, ожидаемый риск расходится. Это аналог метрической потери классической противниковой роли деревьев Littlestone, но с новым ингредиентом, что масштаб неоднозначности расходится. Верхняя граница следует дополняющему маршруту из теории игр. Отсутствие бесконечного дерева с неограниченным разрывом означает, что обучающийся выигрывает бесконечную игру Gale-Stewart над реализуемыми противниковыми продолжениями — в смысле Bousquet et al. (2020). Симуляция выигрышной стратегии на выборке i.i.d. стабилизирует a.s. после конечного числа продвижений, обеспечивая для каждого $x$ множество допустимых меток ограниченного диаметра, которое содержит истинную метку. Затем зависящее от данных счетное разбиение ${\mathcal{X}}$ сводит задачу к счетному числу подзадач с ограниченной потерей, решаемых существующими обучающими алгоритмами с метрической потерей.

Вклад.

В заключение, данная статья предоставляет:

⟦• полная характеристика класса гипотез, реализующих сильную универсальную Байесовскую согласованность для общих метрических функций потерь, через препятствие в виде бесконечного неограниченного разрыва дерева Литтлстоуна (Теорема 4.5);
⟦• конструктивное правило обучения в беспрепятственном режиме, доказанное как сильно универсально согласованное по Байесу в разрешимом случае (Теорема 6.5);
• разделение, демонстрирующее, что естественные условия типа конечности (например, кандидаты на основе $R^{\star}<\infty$ ) не передают корректную характеристику в задаче реализуемости с неограниченной метрикой потерь, разрешая реализуемый случай открытой задачи, поставленной Tsir Cohen & Kontorovich (2022).

Приведены конкретные примеры классов гипотез, которые допускают и не допускают дерево с неограниченным разрывом, иллюстрирующие практическую область применимости характеристики, в Приложении A.1. Продолжение характеристики на агоностическом уровне, где ${\bar{\mu}}$ не обязательно реализуем, является важным направлением для будущих исследований; мы обсуждаем барьеры для такого расширения в Приложении A.5⟧.

Организация.

Раздел 2 рассматривает связанную работу с акцентом на универсальном обучении и описаниях деревьев/игровых персонажей (Bousquet et al., 2020; Hanneke et al., 2023; Attias et al., 2024b), алгоритмах обучения с метрикой-потерей (Tsir Cohen & Kontorovich, 2022) и комбинаторных описаниях обучаемости (Brukhim et al., 2022). Раздел 3 приводит контрпример, показывающий, что только условия типа конечности не гарантируют распределённо-независимую согласованность для неограниченных метрических потерь. Раздел 4 представляет основную характеристику и её доказательство, которое состоит из двух частей: Раздел 5 доказывает реализуемую нижнюю оценку: существование бесконечного дерева Littlestone с неограниченным разрывом подразумевает, что ни один обучающийся не может быть согласованным (Теорема 5.1). Раздел 6 доказывает соответствующую верхнюю оценку: при отсутствии такого дерева мы строим сильно универсальный Bayes-согласованный обучающийся (Теорема 6.5).

2 Смежные работы

Универсальные характеристики обучения и теоретико-игровой характеризации.

Наша работа опирается на недавнюю программу понимания универсальной (то есть независимой от распределений) обучаемости через призму бесконечных игр и комбинаторных деревьев. В достижимой $0$ - $1$ постановке Bousquet et al. (2020) ввел универсальную обучающую модель (позволяющую константам зависеть от распределения) и разработал точную теорию достижимых скоростей с помощью игр Gale-Stewart и препятствий в виде деревьев, подчеркнув роль бесконечных структур типа Littlestone и измеримость выигрышных стратегий. Эта схема была расширена на многоклассовое предсказание силами Hanneke et al. (2023), который выявил дополнительные препятствия в виде деревьев, задающие ландшафт универсальных скоростей за пределами бинарной постановки. Более недавно Attias et al. (2024a) изучал достижимую регрессию как в PAC, так и в онлайн-обучении (в частности, для потерь с отсечением и абсолютных потерь), предоставив описания обучаемости через несколько комбинаторных измерений: масштабированную размерность Graph для обучаемости по ERM, масштабированную размерность One-Inclusion-Graph (OIG) для общей PAC-обучаемости, и онлайн-размерность на основе масштабированных деревьев Littlestone (где разделение меток контролируется параметром разрешения или последовательностью масштабов), которая характеризует оптимальную совокупную потерю в онлайн-обучении (тем самым разрешая открытую задачу из предыдущей работы). Настоящая статья продолжает это направление в другом направлении: вместо того чтобы фокусироваться на скоростях при ограниченных потерях, мы изучаем сильную универсальную байесовскую согласованность при общих метрических потерях, включая неограниченные, и даем необходимую-и-достаточную характеристику в терминах препятствия типа Littlestone с неограниченным разрывом.

Обучение с метрическими потерями и неограниченным риском.

Обучение с обобщенными метрическими функциями потерь в последнее время привлекло внимание как общее обобщение многоклассовой классификации и регрессии с действительнозначными значениями. Наиболее непосредственно связано с этим — алгоритм MedNet из Tsir Cohen & Kontorovich (2022), который дает конструктивный сильный универсальный байесовски-совместимый обучающий алгоритм в агоностической постановке при предположениях о разделимости и при условии ограниченности по ожиданию (BIE) для $({\mathcal{Y}},\ell)$ . Эта работа продолжает парадигму «оптимистически универсального» ближайшего соседа, начатую для обучения $0$ - $1$ в метрических пространствах экземпляров (например, OptiNet и последующие работы Hanneke et al., 2021), для общих метрических пространств меток, и подчеркивает, что наивные расширения классических методов метрических пространств могут терпеть неудачу при общих геометриях функций потерь. Наши результаты дополняют друг друга двумя способами. Во-первых, мы рассматриваем разрешимую постановку и спрашиваем, когда сильная универсальная байесовская согласованность возможна как функция класса гипотез ${\mathcal{H}}$ , а не накладываем условий интегрируемости на ${\mathcal{Y}}$ или распределительных условий на ${\bar{\mu}}$ . Во-вторых, конструкция нижней границы, лежащая в основе нашей характеристики, проясняет, почему неограниченные функции потерь фундаментально меняют картину: даже когда оптимальный байесовский риск равен $0$ , редкие ошибки предсказания при возрастающих масштабах потерь могут препятствовать сильной универсальной байесовской согласованности. В частности, наш контрпример показывает, что условия типа конечности, такие как $R^{\ast}<\infty$ , предложенные как кандидат в Tsir Cohen & Kontorovich (2022), в общем случае недостаточны без дополнительных структурных предположений.

Обучение в метри́ческом пространстве, методы Липшица и структура двойника.

Параллельный поток изучает обучение и обобщение, когда экземпляры наделены метрикой и алгоритмы должны использовать только информацию о расстоянии. Известный подход рассматривает классификаторы/регрессоры как функции Липшица и контролирует сложность с помощью метрических понятий, таких как (удвоение) размерность и fat-shattering. Например, Готтлиб и Краутгамер и соавторы разработали эффективные алгоритмы классификации с большим отступом для метрических данных, чье время работы и гарантии зависят от удвоения размерности и аппроксимационных примитивов поиска близости/расширения Липшица (например, Gottlieb et al., 2014; см. также структуры данных для близости в почти удваивающихся метриках Gottlieb & Krauthgamer, 2013). Эти работы дают алгоритмические и перспективы конечной выборки, адаптированные к геометрическим режимам (предположения о ограниченном диаметре, удвоении или отступе). Наша постановка ортогональна: мы не предполагаем низкоразмерной геометрии или глобально ограниченного диаметра, и препятствие, которое мы выявляем, является комбинаторным (на основе деревьев), а не геометрическим. Тем не менее, наша конструкция верхней границы явно использует подзадачи с ограниченным диаметром (получаемые с помощью управляемого данными разбиения ${\mathcal{X}}$ ) и поэтому может рассматриваться как редукция, позволяющая встраивать существующие метрические обучающие алгоритмы с ограниченной потерь или ограниченным диапазоном (включая MedNet, как используется здесь) локально.

Связи с классическими комбинаторными размерностями.

Параметры на основе деревьев повсеместны в моделях обучения. В равномерной/теории ПАК измерение Вапника—Червоненкиса (для бинарного случая) и его многоклассовые обобщения (например, измерения Натарраджана и родственные) характеризуют обучаемость, причём недавние точные результаты включают характеристику DS-для многоклассовой ПАК-обучаемости (Brukhim et al., 2022). В условном онлайн-обучении с противником измерение Литтлстоуна и его многоклассовые обобщения определяют границы числа ошибок и сожаления. Линия универсального обучения (Bousquet et al., 2020; Hanneke et al., 2023; Attias et al., 2024b) показывает, что бесконечные препятствия в виде деревьев (и уточнения этого) также управляют зависящим от распределения поведением за пределами равномерной сходимости. Наш вклад состоит в том, чтобы показать, что для общих функций потерь по метрике в реализуемом режиме решающее препятствие заключается в существовании бесконечного дерева типа Литтлстоуна, зазоры в метках которого можно принудительно заставлять расти без ограничения по глубине. Это точно указывает на то, каким образом неограниченные величины потерь взаимодействуют с реализуемостью, делая возможной либо невозможной сильную универсальную байесовскую согласованность.

3 $R^{*}<\infty$ недостаточно

В Tsir Cohen & Kontorovich (2022) достигается сильно универсальный Байес-согласованный обучающий алгоритм для неограниченных потерь ( ${\mathsf{MedNet}}$ ) только тогда, когда пространство меток ${\mathcal{Y}}$ является BIE. Пространство меток ${\mathcal{Y}}$ ограничено по ожиданию (BIE), если $\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\ell(y_{0},Y)<\infty$ для некоторого $y_{0}\in{\mathcal{Y}}$ .

Условие BIE является естественным метрическим аналогом предположения о моментах для вещественнозначных величин $\mathop{\mathbb{E}}|Y|<\infty$ . Было показано, что оно достаточно для байесовской согласованности ${\mathsf{MedNet}}$ , и оно побуждает к более общей постановке вопроса о том, что именно требуется для сильной байесовской согласованности, когда функция потерь не ограничена. Соответственно, Tsir Cohen & Kontorovich (2022) поставило открытой проблемой дать необходимое и достаточное условие для $({\mathcal{X}},\rho)$ , $({\mathcal{Y}},\ell)$ и ${\bar{\mu}}$ , при котором ${\mathsf{MedNet}}$ - или какой-либо другой алгоритм обучения — будет сильно байесовски согласован. Естественным и оптимистичным кандидатом была конечность байесовского риска, $R^{*}<\infty$ . В этом разделе мы показываем, что это условие недостаточно: без дополнительных предположений не может существовать ни один сильно универсально байесовски согласованный обучающийся.

Мы покажем, что для любого алгоритма обучения ${\mathcal{A}}$ существует распределение $\mu$ , такое что ожидаемый риск (по случайности заданного набора $S_{n}\sim\mu^{n}$ ) выученной гипотезы $h_{n}:={\mathcal{A}}(S_{n})$ не стремится к нулю по мере роста размера выборки до $\infty$ ⟧:

\mathop{\mathbb{E}}_{S_{n}\sim\mu^{n}}\left[R({\mathcal{A}}(S_{n}))\right]\nrightarrow 0\text{ as }n\to\infty

Значит, что без дополнительных предположений ни один обучающийся не является сильно универсально Байес-согласованным. Пусть ${\mathcal{X}}$ — это открытый интервал $(0,1)$ . Пусть ${\mathcal{Y}}=\mathbb{N}_{0}:=\{0,1,2,\dots\}$ при стандартной $\ell_{1}$ потере. Определим для любого $k\in\mathbb{N}$ :

I_{k}:=\left(\frac{1}{2^{k}},\frac{1}{2^{k-1}}\right).

Таким образом ${\mathcal{X}}=\bigcup_{k\in\mathbb{N}}I_{k}$ . Мы рассматриваем реализуемый случай с равномерным распределением $\mu$ по ${\mathcal{X}}$ , реализованный семейством функций:

{\mathcal{H}}:=\left\{f:\forall k\in\mathbb{N},\forall x\in I_{k}:f(x)\in\left\{0,2^{2k+1}\right\}\right\},

таким образом, задавая семейство возможных распределений на $({\mathcal{X}},{\mathcal{Y}})$ . Теперь мы определяем реализуемое распределение через явную конструкцию произведения (подбрасывание монеты). Пусть $B=(B_{k})_{k\geq 1}$ будут независимыми и одинаково распределенными честными битами, $B_{k}\sim\mathrm{Ber}(1/2)$ , и определим $f_{B}\in{\mathcal{H}}$ посредством

f_{B}(x):=\begin{cases}0&x\in I_{k}\ \text{and}\ B_{k}=0,\\ 2^{2k+1}&x\in I_{k}\ \text{and}\ B_{k}=1.\end{cases}

Для каждого фиксированного $B$ пусть ${\bar{\mu}}_{B}$ будет распределением на ${\mathcal{X}}\times{\mathcal{Y}}$ , задаваемым $X\sim\mathrm{Unif}(0,1)$ и $Y=f_{B}(X)$ . Тогда ${\bar{\mu}}_{B}$ реализуемо через $f_{B}$ , следовательно, $R^{*}({\bar{\mu}}_{B})=0<\infty$ . Таким образом, мы рассматриваем это как задачу, в которой обучающий (learning algorithm) видит выборку $S_{n}=\{(X_{1},Y_{1}),\dots,(X_{n},Y_{n})\}\sim{\bar{\mu}}_{B}^{n}$ i.i.d. и стремится выдать предиктор $h_{n}:={\mathcal{A}}(S_{n})$ , чтобы минимизировать риск:

R_{{\bar{\mu}}_{B}}(h_{n}):=\mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}_{B}}\ell(h_{n}(X),Y).

Ключевой момент заключается в том, что при любом реализованном образце $S_{n}$ бесконечно много интервалов $I_{k}$ остаются не наблюденными, поэтому $B_{k}$ остается свежей справедливой монетой на каждом таком интервале. На $I_{k}$ по меньшей мере один из двух возможных ярлыков $\{0,2^{2k+1}\}$ должен понести убыток по меньшей мере $2^{k}$ (за счет неравенства треугольника и интегрирования по $|I_{k}|=2^{-k}$ ), так что с условной вероятностью по меньшей мере $1/2$ интервал вносит $\geq 2^{k}$ в риск. Независимость по отношению к неувиденным $k$ и лемма Бореля—Кантелли затем вынуждают бесконечно много таких вкладов, что означает, что $R_{{\bar{\mu}}_{B}}(h_{n})=\infty$ почти наверное. Полное выведение приведено в Приложении A.6⟧.

4 Основной результат: характеристика ${\mathcal{H}}$

Теперь мы формулируем основную теорему, которая характеризует, когда сильная универсальная Байесовская согласованность достижима в реализуемом случае при общих (возможно неограниченных) метрических потерях. Характеризация дана через единственную комбинаторную преграду: неограниченную по разрыву Lиттлстоуна-дерево.

Definition 4.1 (н невозрастающая- $\gamma_{k}$ -Дерево Littlestone).

Зафиксируйте неубывающую последовательность $(\gamma_{k})_{k\geq 1}$ с $\gamma_{k}\to\infty$ . Неубывающее- $\gamma_{k}$ -Littlestone-дерево для ${\mathcal{H}}$ (вариант, основанный на метрической функции потерь классического Littlestone-дерева (Littlestone, 1988); см. также Bousquet et al. (2020, Definition 1.7)) — это укоренённое полное двоичное дерево, внутренние узлы которого на глубине $k$ помечены экземплярами $x_{k,i}\in{\mathcal{X}}$ , и из каждого такого узла выходят два ребра, помеченные $y_{k,i,1},y_{k,i,2}\in{\mathcal{Y}}$ , удовлетворяющие $\ell(y_{k,i,1},y_{k,i,2})\geq\gamma_{k}$ , при этом свойство состоит в том, что каждая конечная траектория от корня до листа реализуема некоторой $h\in{\mathcal{H}}$ (то есть $h$ согласуется с метками рёбер вдоль этого конечного пути).

Definition 4.2 (реализуемая невозрастающая- $\gamma_{k}$ -Littlestone tree).

Бесконечное неубывающее- $\gamma_{k}$ -Littlestone-дерево является деревом бесконечной глубины, удовлетворяющим условиям определения 4.1 на каждой конечной глубине $k$ . Такое бесконечное дерево реализуемо, если, помимо реализуемости на конечных префиксах, каждая бесконечная ветвь от корня к листу имеет всю свою маркировку, реализованную одним-единственным гипотезом в ${\mathcal{H}}$ (то есть для каждого бесконечного пути существует $h\in{\mathcal{H}}$ , согласующаяся со всеми метками рёбер вдоль этого пути).

Lemma 4.3 (Лемма связи: реализуемость с конечным префиксом влечёт реализуемость с бесконечным путём).

Предположим, что ${\mathcal{H}}$ удовлетворяет условию измеримости для Bousquet et al. (2020, Definition 3.3) при компактном параметрическом пространстве $\Theta$ и функции $h\colon\Theta\times{\mathcal{X}}\to{\mathcal{Y}}$ , которая непрерывна по $\theta$ (то есть $\theta\mapsto h(\theta,x)$ непрерывна для каждого фиксированного $x\in{\mathcal{X}}$ ). Тогда всякое бесконечное неубывающее- $\gamma_{k}$ -Littlestone-дерево (Определение 4.1) автоматически реализуемо (Определение 4.2).

Доказательство.

Доказательство следует из свойства конечного пересечения компактных пространств; см. Приложение A.4. ∎

Remark 4.4.

Лемма 4.3 требует предположения компактной параметризации (компакт $\Theta$ , $h$ непрерывна по $\theta$ ); мы обсуждаем в Приложении A.4, почему это предположение необходимо в общем случае, приводим конкретный пример, где два понятия дерева различаются без него, и утверждаем, что это предположение является мягким и охватывает практически все настройки практического интереса.

Theorem 4.5 (Основная характеристика).

Предположим, что $({\mathcal{X}},\rho)$ и $({\mathcal{Y}},\ell)$ являются польскими, а ${\mathcal{H}}$ удовлетворяет условию измеримости Bousquet et al. (2020, Definition 3.3) при компактных $\Theta$ и $h$ , непрерывных в $\theta$ (см. Лемма 4.3). Тогда следующие утверждения эквивалентны:

⟦Существует (не зависящее от распределения) правило обучения ${\mathcal{A}}$ такое, что для каждого реализуемого распределения ${\bar{\mu}}$ на ${\mathcal{X}}\times{\mathcal{Y}}$ обученные предикторы $h_{n}:={\mathcal{A}}(S_{n})$ удовлетворяют

$R_{{\bar{\mu}}}(h_{n})\to 0\qquad\text{almost surely as }n\to\infty.$
⟦2. ${\mathcal{H}}$ не допускает бесконечного неубывающего- $(\gamma_{k})$ -Littlestone-дерева (для любой неубывающей последовательности зазоров $(\gamma_{k})$ с $\gamma_{k}\to\infty$ ).

Доказательство.

$(1)\implies(2)$ : Обращение по контрапозиции: предположим, что существует бесконечное неубывающее- $\gamma_{k}$ -дерево Литтлстоуна (Определение 4.1). По лемме 4.3 дерево автоматически реализуемо (Определение 4.2). Теорема 5.1 затем показывает, что ни один обучающийся не может быть согласованным. $(2)\implies(1)$ : Если не существует такого препятствия, то явный обучающийся, построенный в разделе 6.5, является сильно универсально байесовски-согласованным для каждого реализуемого ${\bar{\mu}}$ (Теорема 6.5). ∎

5 Нижняя граница: существование бесконечного дерева не подразумевает согласованность

Theorem 5.1 (Нижняя граница).

Пусть ${\mathcal{H}}$ — это класс гипотез, который содержит реализуемое бесконечное неубывающее- $\gamma_{k}$ -Littlestone дерево с $\gamma_{k}\to\infty$ . Тогда для любого алгоритма обучения ${\mathcal{A}}$ существует реализуемое распределение ${\bar{\mu}}$ такое, что ожидаемый риск бесконечен:

\mathop{\mathbb{E}}_{S_{n}\sim{\bar{\mu}}^{n}}[R({\mathcal{A}}(S_{n}))]=\infty

для всех $n$ . В частности, ни один обучающийся не является согласованным.

Эскиз доказательства; полное доказательство в Приложении A.7..

Аргумент обобщает контрпример из раздела 3: мы строим реализуемое распределение, поддерживаемое на выбранных узлах дерева, где разрыв велик, затем показываем, что каждый обучающийся несёт бесконечный риск посредством аргумента Бореля–Кантелли на неувиданных узлах.

Построение распределения.

Поскольку $\gamma_{k}\to\infty$ , мы можем выбирать глубины $k_{1}<k_{2}<\cdots$ вдоль дерева, где $\gamma_{k_{m}}\geq m^{2}$ . Назначим массу вероятности $p_{m}\propto 1/m^{2}$ узлу глубины- $k_{m}$ (нормированную так, что $\sum p_{m}=1$ ). Случайный путь от корня к листу выбирается бросками независимых честных монет $(B_{k})_{k\geq 1}$ , по одной на каждый уровень дерева; монета $B_{k_{m}}$ выбирает, какая из двух исходящих меток на глубине $k_{m}$ является истинной меткой. Поскольку дерево реализуемо (определение 4.2), полученное распределение ${\bar{\mu}}_{B}$ реализуемо некоторыми $f_{B}^{\star}\in{\mathcal{H}}$ .

Непознанные глубины действуют как справедливые монеты.

Исправьте любого обучающегося ${\mathcal{A}}$ и размер выборки $n$ . Выборка $S_{n}\sim{\bar{\mu}}_{B}^{n}$ может затронуть не более $n$ из счетного множества глубин $k_{m}$ , так что все, кроме конечного числа, остаются не наблюдаемыми. На каждой ненаблюдаемой глубине $k_{m}$ монета $B_{k_{m}}$ независима от $S_{n}$ , то есть прогноз обучающегося $h_{n}(x_{k_{m}})$ выбирается без информации о истинной метке. Так как две кандидатные метки находятся на расстоянии $\geq\gamma_{k_{m}}\geq m^{2}$ , неравенство треугольника вынуждает $\mathop{\mathbb{E}}[\ell(h_{n}(x_{k_{m}}),\,Y)\mid S_{n}]\geq m^{2}/2$ независимо от того, что предсказывает обучающийся.

Расхождение через Бореля–Кантелли.

Точнее, какое бы обозначение ни было ближе к предсказанию обучающегося, “плохой” исход монеты (другое обозначение) происходит с условной вероятностью $1/2$ независимо на различных не наблюдавшихся глубинах. На этом событии вклад в потери по меньшей мере $p_{m}\cdot m^{2}/2=\Theta(1)$ . По второй лемме Бореля—Кантелли, бесконечно многие такие плохие события происходят почти наверное, так что $R_{{\bar{\mu}}_{B}}(h_{n})=\infty$ п.н. Аргумент Фубини по случайной траектории $B$ и счётное пересечение по $n\in\mathbb{N}$ затем дают для фиксированного обучающегося ${\mathcal{A}}$ единственное распределение ${\bar{\mu}}$ с бесконечным ожидаемым риском при любом размере выборки. ∎

6 Верхняя граница: отсутствие бесконечного дерева влечёт сильную универсальную согласованность

В этом разделе мы завершаем обоснование того, что при подходящем комбинаторном условии на ${\mathcal{H}}$ возможно сильное универсальное байесовски согласованное обучение в реализуемом случае, даже когда функция потерь не ограничена.

План-график доказательства.

Верхняя граница осуществляется в четыре этапа: (1) мы кодируем препятствие для дерева как игру Гейла—Стюарта и вызываем аппарат измеримо-стратегий Bousquet et al. (2020) (раздел 6.1); (2) мы показываем, что запуск этой игры на i.i.d. выборке приводит к тому, что она стабилизируется после конечного числа раундов почти наверное, и для каждого $x$ получается набор допустимых меток $H_{K}(x)$ с ограниченным диаметром (разделы 6.2-6.3); (3) мы разбиваем ${\mathcal{X}}$ на счетно много ячеек, каждая из которых имеет общую область ограниченных меток (раздел 6.4); (4) в каждой ячейке мы применяем обучающий алгоритм с ограниченным диапазоном ${\mathsf{MedNet}}$ из Tsir Cohen & Kontorovich (2022) и агрегируем (разделы 6.5-6.6).

Стоящие допущения о измеримости.

Чтобы избежать паталогий, возникающих из-за мер (измеримая детерминированность / измеримые стратегии и измеримые выборы), мы предполагаем, что и $({\mathcal{X}},\rho)$ , и $({\mathcal{Y}},\ell)$ являются польскими пространствами. В частности, $({\mathcal{Y}},\ell)$ сепарабельно, следовательно допускает счётное плотное подмножество, которое мы будем использовать для построения счётного разбиения ${\mathcal{X}}$ . Кроме того, мы предполагаем, что класс гипотез ${\mathcal{H}}$ удовлетворяет условию измеримости Bousquet et al. (2020, Definition 3.3): существует польское пространство $\Theta$ (параметрическое пространство) и борелевски измеримая функция оценки $h\colon\Theta\times{\mathcal{X}}\to{\mathcal{Y}}$ , $(\theta,x)\mapsto h(\theta,x)$ , такая что ${\mathcal{H}}=\{h(\theta,\cdot):\theta\in\Theta\}$ . Мы усиливаем это требованием, чтобы $\Theta$ было компактным, а $h$ непрерывным по $\theta$ (то есть $\theta\mapsto h(\theta,x)$ непрерывна для каждого фиксированного $x\in{\mathcal{X}}$ ; см. Лемма 4.3, а также Приложение A.4 для обсуждения того, почему это усиление необходимо и почему оно является мягким), так что игра в Разделе 6.1 допускает универсально измеримую выигрышную стратегию для обучающегося. Всякий раз, когда мы определяем отображения со множествами значений или индексы, используя эту стратегию (например, $H_{k}(\cdot)$ , $j_{k}(\cdot)$ , и ячейки $C_{k,j}$ ), мы неявно работаем с универсально измеримыми вариантами, так что эти объекты (и итоговый предиктор) можно считать универсально измеримыми.222В частности, этого можно добиться стандартными результатами о выборе на польских пространствах (например, выбор типа Jankov-von Neumann), применёнными к аналитическим множествам, возникающим из отношения разрешённых ходов и стратегии $\sigma$ .

6.1 Игра Гейл–Стюарта

Зафиксируйте неубывающую последовательность $(\gamma_{k})_{k\geq 1}$ с $\gamma_{k}\to\infty$ . Особый выбор расходящегося графика зазоров несуществен: если ${\mathcal{H}}$ содержит бесконечное дерево с неубывающими зазорами, у которого зазоры стремятся к $\infty$ , то для любой заданной расходящейся последовательности $(\tilde{\gamma}_{m})_{m\geq 1}$ можно получить бесконечное дерево с неубывающими- $(\tilde{\gamma}_{m})$ зазорами, переходя к подпоследовательности глубин, вдоль которых исходные зазоры превышают $\tilde{\gamma}_{m}$ («пропуск уровней»). Вследствие этого отсутствие бесконечного дерева с неубывающими- $(\gamma_{k})$ зазорами для некоторого расходящегося $(\gamma_{k})$ эквивалентно отсутствию любой бесконечной неограниченной-заоблачной обструкции Littlestone-дерева.

Теперь мы задаём бесконечную игру Гейла — Стюарта между противником $P_{A}$ и обучающимся $P_{L}$ . На раунде $k=1,2,\dots$ :

⟦• $P_{A}$ выбирает тройку $(\xi_{k},\eta_{k,1},\eta_{k,2})\in{\mathcal{X}}\times{\mathcal{Y}}\times{\mathcal{Y}}$ такую, что $\ell(\eta_{k,1},\eta_{k,2})\geq\gamma_{k}$ и такая, что существует $h\in{\mathcal{H}}$ , согласующееся с предыдущим ходом и удовлетворяющее $h(\xi_{k})\in\{\eta_{k,1},\eta_{k,2}\}$ .
⟦• $P_{L}$ выбирает одну из двух меток, обозначенную $\hat{\eta}_{k}\in\{\eta_{k,1},\eta_{k,2}\}$ .

Обучающийся выигрывает, если в некотором конечном раунде у противника нет допустимого хода; в противном случае выигрывает противник (то есть если игра продолжается бесконечно). Вспомните определение неубывающего- $\gamma_{k}$ -Littlestone-дерева из определения 4.1. Непосредственно следует, что существует бесконечное неубывающее- $\gamma_{k}$ Littlestone-дерево тогда и только тогда, когда $P_{A}$ имеет выигрышную стратегию. Следовательно, если не существует такого бесконечного дерева, то $P_{L}$ имеет выигрышную стратегию. При польских предположениях мы фиксируем измеримую выигрышную стратегию $\sigma$ для $P_{L}$ . Существование такой измеримой стратегии объясняется в приложении A.3, где мы проверяем, что условия Bousquet et al. (2020, Theorem B.1) выполнены в нашей игре.

6.2 Исторически-условные наборы меток

Definition 6.1 (Исторически-условные наборы меток).

Пусть $\tau_{k}$ обозначает конечную историю, возникающую из судебного разбирательства по $\sigma$ . Дано такую историю и точку $x\in{\mathcal{X}}$ , определите множество допустимых меток, условное по истории

	$\displaystyle V_{k}(x)=\{y\in{\mathcal{Y}}:$	$\displaystyle\exists h\in{\mathcal{H}}\$
		$\displaystyle\text{consistent with }\tau_{k}\text{ such that }h(x)=y\},$

и множество меток, зависящее от истории

	$\displaystyle H_{k}(x)=\bigl\{y\in V_{k}(x):$	$\displaystyle\forall y^{\prime}\in V_{k}(x)\ \text{with }\ell(y,y^{\prime})\geq\gamma_{k+1},$
		$\displaystyle\sigma\ \text{does not choose }y\ \text{at round }k{+}1$
		when presented with
		$\displaystyle(\xi_{k+1},\eta_{k+1,1},\eta_{k+1,2})=(x,y,y^{\prime})\bigr\}.$

Интуитивно, $H_{k}(x)$ — это множество меток на $x$ , которые стратегия $\sigma$ никогда не выбирает в следующем раунде при сочетании с любой достаточно далёкой реализуемой альтернативой.

Lemma 6.2 (Ограниченный диаметр наборов меток, зависящих от истории).

Для любой реализуемой истории $\tau_{k}$ и для любой $x\in{\mathcal{X}}$ ⟧,

\operatorname{diam}(H_{k}(x)):=\sup_{y,y^{\prime}\in H_{k}(x)}\ell(y,y^{\prime})\leq\gamma_{k+1}.

Доказательство.

Предположим $y,y^{\prime}\in H_{k}(x)$ и $\ell(y,y^{\prime})>\gamma_{k+1}$ . Тогда противник может предъявить $(x,y,y^{\prime})$ на раунде $k{+}1$ (этот ход разрешён, поскольку $y\in V_{k}(x)$ ), в таком случае $\sigma$ должно выбрать одно из $y$ или $y^{\prime}$ , что противоречит определяющему свойству $H_{k}(x)$ для выбранной метки. Следовательно $\ell(y,y^{\prime})\leq\gamma_{k+1}$ . ∎

6.3 Стабилизация на бесконечной выборке i.i.d.

Пусть ${\bar{\mu}}$ будет любой реализуемым распределением на ${\mathcal{X}}\times{\mathcal{Y}}$ , реализованным некоторым $f^{*}\in{\mathcal{H}}$ . Пусть $S_{\infty}=((X_{i},Y_{i}))_{i\geq 1}\sim{\bar{\mu}}^{\infty}$ .

Мы реализуем симуляцию игры, используя $S_{\infty}$ следующим образом. Поддерживайте текущий счетчик раундов $k\geq 0$ и текущую допустимую историю. Просканируйте $i=1,2,\dots$ . Если существует свидетель $y^{\prime}\in{\mathcal{Y}}$ с $\ell(Y_{i},y^{\prime})\geq\gamma_{k+1}$ такой, что (i) если противник сыграет $(X_{i},Y_{i},y^{\prime})$ следующим, то $\sigma$ выбирает $Y_{i}$ , и (ii) расширенная история остается реализуемой некоторой гипотезой в ${\mathcal{H}}$ , то мы продвигаем игру: добавьте этот ход и установите $k\leftarrow k+1$ . В противном случае ничего не делайте и продолжайте. Поскольку $\sigma$ — это выигрышная стратегия, противник не может вынудить бесконечную допустимую игру под $\sigma$ . Таким образом, вдоль любого исхода $S_{\infty}$ , описанная выше процедура может продвинуться лишь конечное число раз. Пусть $K_{\infty}=K(S_{\infty})<\infty$ будет заключительным раундом, а $\tau_{K_{\infty}}$ — конечной историей.

Lemma 6.3 (Истинная метка содержится в a.s. при новом независимом выборе).

С вероятностью один над $S_{\infty}\sim{\bar{\mu}}^{\infty}$ , для конечной истории $\tau_{K_{\infty}}$ у нас

{\bar{\mu}}\bigl(\{(x,y):y\notin H_{K_{\infty}}(x)\}\bigr)=0.

Эквивалентно, при условии $S_{\infty}$ , независимая точка тестирования $(X,Y)\sim{\bar{\mu}}$ удовлетворяет $Y\in H_{K_{\infty}}(X)$ почти наверное.

Доказательство.

Зафиксируйте результат $S_{\infty}$ , при котором процедура стабилизируется на $K_{\infty}$ с историей $\tau_{K_{\infty}}$ . Определите $E:=\{(x,y):y\in V_{K_{\infty}}(x)\ \text{and}\ y\notin H_{K_{\infty}}(x)\}.$ Поскольку ${\bar{\mu}}$ реализуемо некоторыми $f^{*}\in{\mathcal{H}}$ и $\tau_{K_{\infty}}$ является реализуемой историей (в самом деле согласованной с $f^{*}$ ), получаем $Y=f^{*}(X)\in V_{K_{\infty}}(X)$ почти наверняка для $(X,Y)\sim{\bar{\mu}}$ , и потому

{\bar{\mu}}\bigl(\{(x,y):y\notin H_{K_{\infty}}(x)\}\bigr)={\bar{\mu}}(E).

По определению $H_{K_{\infty}}(x)$ , для каждого $(x,y)\in E$ существует $y^{\prime}\in V_{K_{\infty}}(x)$ с $\ell(y,y^{\prime})\geq\gamma_{K_{\infty}+1}$ таким образом, что если противник разыгрывает $(x,y,y^{\prime})$ далее, $\sigma$ выбрал бы $y$ . Кроме того, поскольку $y\in V_{K_{\infty}}(x)$ , существует $h\in{\mathcal{H}}$ , согласованное с $\tau_{K_{\infty}}$ с $h(x)=y$ , так что расширенная история после приписывания $(x,y,y^{\prime})$ и выбора $y$ остается осуществимой. Поэтому всякий раз, когда точка выборки $(X_{i},Y_{i})$ попадает в $E$ (при фиксированной заключительной истории), эта точка допускается для продвижения игры (используя ее свидетель $y^{\prime}$ ), что противоречит стабилизации, если это происходит только конечное число раз. Если ${\bar{\mu}}(E)>0$ , то тогда по лемме Бореля–Кантелли для i.i.d. выборок $(X_{i},Y_{i})\in E$ происходит бесконечно часто почти наверное, что приводит к противоречию. Следовательно, ${\bar{\mu}}(E)=0$ . ∎

6.4 Сокращение пер- $x$ ограниченный диаметр для счетного числа подзадач с ограниченным диапазоном

Лемма 6.2 показывает, что у каждого $H_{K_{\infty}}(x)$ диаметр не превосходит $\gamma_{K_{\infty}+1}$ . Однако объединение $\bigcup_{x}H_{K_{\infty}}(x)$ может не быть ограниченным, так что мы не можем напрямую применить один алгоритм обучения с ограниченным диаметром. Мы устраняем это, разбивая ${\mathcal{X}}$ на счетливо много областей, каждая из которых имеет общую ограниченную область меток. Зафиксируем счетное плотное подмножество $\{q_{1},q_{2},\dots\}\subseteq{\mathcal{Y}}$ . Это гарантировано тем, что ${\mathcal{Y}}$ является польским пространством. Для заданной истории $\tau_{k}$ определим для каждого $x\in{\mathcal{X}}$ индекс

j_{k}(x):=\min\Bigl\{j\in\mathbb{N}:\ \exists y\in H_{k}(x)\ \text{with}\ \ell(y,q_{j})\leq\gamma_{k+1}\Bigr\}.

(Существование следует из плотности $(q_{j})$ и непустоты $H_{k}(x)$ в правовых позициях.) Это приводит к счетному разбиению ${\mathcal{X}}=\bigsqcup_{j\geq 1}C_{k,j}$ где $C_{k,j}:=\{x:\ j_{k}(x)=j\}$ . Для каждой ячейки определите ограниченную область меток

{\mathcal{Y}}_{k,j}:=\{y\in{\mathcal{Y}}:\ \ell(y,q_{j})\leq 2\gamma_{k+1}\}.

Lemma 6.4 (Покрытие ограниченного диапазона по ячейкам).

Для каждого $k,j$ и для каждого $x\in C_{k,j}$ выполняется $H_{k}(x)\subseteq{\mathcal{Y}}_{k,j}$ . Следовательно, если ${\bar{\mu}}(\{(x,y):y\in H_{k}(x)\})=1$ , то ${\bar{\mu}}(Y\in{\mathcal{Y}}_{k,j}\mid X\in C_{k,j})=1$ для каждого $j$ при ${\bar{\mu}}(X\in C_{k,j})>0$ .

Доказательство.

Исправь $x\in C_{k,j}$ . По определению существует $y_{x}\in H_{k}(x)$ , такое что $\ell(y_{x},q_{j})\leq\gamma_{k+1}$ . Для любого $y\in H_{k}(x)$ , Лемма 6.2 дает $\ell(y,y_{x})\leq\gamma_{k+1}$ . Следовательно, по неравенству треугольника, $\ell(y,q_{j})\leq\ell(y,y_{x})+\ell(y_{x},q_{j})\leq 2\gamma_{k+1},$ так что $y\in{\mathcal{Y}}_{k,j}$ . ∎

6.5 Реализуемое правило обучения

Теперь определяем правило обучения, не зависящее от распределения.

Входной сигнал.

Маркированный образец $S_{n}=((X_{i},Y_{i}))_{i=1}^{n}\sim{\bar{\mu}}^{n}$ из реализуемого распределения ${\bar{\mu}}$ , реализованного некоторым $f^{*}\in{\mathcal{H}}$ .

Шаг 1: запускайте игру на половине выборки.

Разделите выборку на две половины, $S_{n}^{(1)}=((X_{i},Y_{i}))_{i=1}^{\lfloor n/2\rfloor}$ и $S_{n}^{(2)}=((X_{i},Y_{i}))_{i=\lfloor n/2\rfloor+1}^{n}$ . Запустите процедуру стабилизации из раздела 6.3 на $S_{n}^{(1)}$ , получив конечный раунд $K=K(S_{n}^{(1)})$ и конечную историю $\tau_{K}$ .

Шаг 2: разделение ${\mathcal{X}}$ using $(q_{j})$ .

Используя $\tau_{K}$ , вычислите отображение с множеством значений $H_{K}(\cdot)$ и индуцированное отображение $j_{K}(\cdot)$ , следовательно, множества ячеек $C_{K,j}$ и ограниченные области меток ${\mathcal{Y}}_{K,j}$ .

Для каждого $j$ пусть $S_{n,j}^{(2)}$ обозначает подпоследовательность выборки во второй половине $S_{n}^{(2)}$ , состоящую из тех примеров, которые имеют $X_{i}\in C_{K,j}$ . Затем запустите алгоритм, минимизирующий метрику-лосс ${\mathsf{MedNet}}$ из Tsir Cohen & Kontorovich (2022) (ограниченный областью меток ${\mathcal{Y}}_{K,j}$ ) на $S_{n,j}^{(2)}$ и на ограниченном классе гипотез ${\mathcal{H}}|_{C_{K,j}}:=\{h|_{C_{K,j}}:\ h\in{\mathcal{H}}\}$ и обозначьте получившийся предиктор как $\widehat{f}_{n,j}:C_{K,j}\to{\mathcal{Y}}_{K,j}$ .

Если $S_{n,j}^{(2)}$ пусто, определить $\widehat{f}_{n,j}(x)\equiv q_{j}$ на $C_{K,j}$ ⟧.

Вывод предиктора.

Определите $\widehat{f}_{n}:{\mathcal{X}}\to{\mathcal{Y}}$ через

\widehat{f}_{n}(x):=\widehat{f}_{n,j_{K}(x)}(x).

Операционально не требуется явно строить все разбиение: по вводу $x$ вычислите $j_{K}(x)$ и используйте только те обучающие точки в $S_{n}^{(2)}$ , которые лежат в той же ячейке. Смысл, в котором это правило обучения является «явным», — при наличии измеримой стратегии выигрыша $\sigma$ — обсуждается в Приложении A.2⟧.

6.6 Возможная сильная универсальная байесовская согласованность

Theorem 6.5 (Реализуемая верхняя граница).

Предположим, что ${\mathcal{H}}$ допускает не бесконечное неубывающее- $\gamma_{k}$ -дерево Литтлстоуна для некоторой неубывающей последовательности разрывов $(\gamma_{k})$ с $\gamma_{k}\to\infty$ . Предположим, что $({\mathcal{X}},\rho)$ и $({\mathcal{Y}},\ell)$ являются польскими. Пусть ${\bar{\mu}}$ будет любым распределением на ${\mathcal{X}}\times{\mathcal{Y}}$ , реализуемым некоторым $f^{*}\in{\mathcal{H}}$ .

Тогда правило обучения $S_{n}\mapsto\widehat{f}_{n}$ , определенное в разделе 6.5, является строго универсально согласованным по Байесу в реализуемом смысле:

R_{{\bar{\mu}}}(\widehat{f}_{n})\to 0\qquad\text{almost surely as }n\to\infty.

Доказательство.

Зафиксируйте реализуемое распределение ${\bar{\mu}}$ , реализованное некоторым $f^{*}\in{\mathcal{H}}$ , и свяжите всех обученных предикторов с i.i.d. бесконечной выборкой $S_{\infty}=((X_{i},Y_{i}))_{i\geq 1}\sim{\bar{\mu}}^{\infty}$ . Для каждого четного $n=2m$ правило обучения раздела 6.5 использует первую половину $S^{(1)}_{2m}=((X_{i},Y_{i}))_{i=1}^{m}$ для проведения моделирования игры, а вторую половину $S^{(2)}_{2m}=((X_{i},Y_{i}))_{i=m+1}^{2m}$ для обучения внутри ячеек. Поскольку $S^{(1)}_{2m}$ и $S^{(2)}_{2m}$ — непересекающиеся блоки i.i.d. последовательности, эти половины независимы. (Нечетный $n$ можно обрабатывать, игнорируя одну выборку; достаточно доказать сходимость вдоль четной подпоследовательности.) Доказательство организовано в четыре шага.

Шаг 1: стабилизация и последующее достижение согласия с терминальной историей.

Запустите процедуру стабилизации из раздела 6.3 на всем бесконечном префиксе $((X_{i},Y_{i}))_{i\geq 1}$ . Поскольку $\sigma$ является выигрышной стратегией, процедура продвигается только конечное число раз почти наверное; обозначим через $K_{\infty}=K(S_{\infty})<\infty$ финальный раунд и через $\tau_{K_{\infty}}$ получившуюся конечную историю. На фиксированном пути выборки $S_{\infty}$ пусть $N_{0}=N_{0}(S_{\infty})$ будет таким индексом, достаточно большим, что после сканирования $(X_{i},Y_{i})$ на предмет $i\leq N_{0}$ процедура уже сделала все свои (конечное число) продвижения, и ни одна дополнительная точка выборки $(X_{i},Y_{i})$ с $i>N_{0}$ не может продвинуть игру дальше раунда $K_{\infty}$ . Такой $N_{0}$ существует, потому что процедура продвигается только конечное число раз. Теперь рассмотрим запуск той же процедуры на конечном префиксе длины $m$ . Для каждого $m\geq N_{0}$ , запуск на $((X_{i},Y_{i}))_{i=1}^{m}$ должен дать точно тот же конечный раунд и историю, то есть.

K(S^{(1)}_{2m})=K_{\infty}\qquad\text{and}\qquad\tau_{K(S^{(1)}_{2m})}=\tau_{K_{\infty}}.

(1)

Действительно, по определению $N_{0}$ не существует допустимого шага продвижения после индекса $N_{0}$ , поэтому усечение сканирования на любом $m\geq N_{0}$ не может удалить продвижение, происходящее после $N_{0}$ (их нет), и не может создать новые продвижения. По лемме 6.3 для конечной истории $\tau_{K_{\infty}}$ мы имеем

{\bar{\mu}}\bigl(\{(x,y):y\notin H_{K_{\infty}}(x)\}\bigr)=0.

(2)

Объединяя (1) и (2), получаем, что на каждой траектории выборки $S_{\infty}$ в этом событии с вероятностью единица, для всех достаточно больших четных $n=2m$ (а именно, $m\geq N_{0}(S_{\infty})$ ) отображение множества, задаваемое данными, $H_{K(S^{(1)}_{2m})}(\cdot)$ , используемое обучающимся, совпадает с $H_{K_{\infty}}(\cdot)$ и, таким образом, почти наверное содержит истинную метку $Y$ при независимой выборке для тестирования.

Шаг 2: счетная разбиение и ограниченные области меток.

Укажите такой путь выборки $S_{\infty}$ и запишите $K:=K_{\infty}$ . Используя плотное множество $(q_{j})_{j\geq 1}$ , определите счётное разбиение $\{C_{K,j}\}_{j\geq 1}$ и ограниченные области ${\mathcal{Y}}_{K,j}$ , как в разделе 6.4. По лемме 6.4 и (2), для каждого $j$ с $p_{j}:={\bar{\mu}}(X\in C_{K,j})>0$ условное распределение ${\bar{\mu}}_{j}:={\bar{\mu}}(\cdot\mid X\in C_{K,j})$ опирается на ${\mathcal{X}}_{j}\times{\mathcal{Y}}_{K,j}$ , где ${\mathcal{X}}_{j}:=C_{K,j}$ , и, в частности

\ell(y,y^{\prime})\leq\operatorname{diam}({\mathcal{Y}}_{K,j})\leq 4\gamma_{K+1}\qquad\forall\,y,y^{\prime}\in{\mathcal{Y}}_{K,j}.

(3)

Таким образом, в каждой ячейке функция потерь ограничена конечной константой $4\gamma_{K+1}$ (которая зависит от реализованного конечного раунда $K$ , но является конечной на фиксированном пути выборки).

Шаг 3: сильная согласованность внутри каждой ячейки.

Рассмотрим любое фиксированное $j$ при $p_{j}>0$ . Вторая половина выборки $S^{(2)}_{2m}=((X_{i},Y_{i}))_{i=m+1}^{2m}$ являются независимыми и одинаково распределенными по ${\bar{\mu}}$ и независимы от первой половины, следовательно, независимы от (в конечном счете фиксированного) разбиения. Пусть $S^{(2)}_{2m,j}$ обозначает подпоследовательность этих примеров с $X_{i}\in C_{K,j}$ . При условии $X_{i}\in C_{K,j}$ эти примеры являются независимыми и одинаково распределенными по ${\bar{\mu}}_{j}$ . Кроме того, поскольку $p_{j}>0$ , число $N_{m,j}:=|S^{(2)}_{2m,j}|$ удовлетворяет $N_{m,j}\to\infty$ почти наверное при $m\to\infty$ (в силу сильного закона больших чисел для бернуллиевских индикаторов события $\{X\in C_{K,j}\}$ ). На ячейке $j$ правило обучения выполняется ${\mathsf{MedNet}}$ (ограниченное ${\mathcal{Y}}_{K,j}$ ) с использованием $S^{(2)}_{2m,j}$ , что дает предиктор $\widehat{f}_{2m,j}$ . Поскольку ${\bar{\mu}}$ осуществимо посредством $f^{*}\in{\mathcal{H}}$ , ограниченная целевая $f^{*}|_{C_{K,j}}$ реализуема в ограниченном классе ${\mathcal{H}}|_{C_{K,j}}$ , и согласно (3) условная задача на $C_{K,j}$ имеет ограниченную ошибку (следовательно, является BIE). Поэтому, в силу сильной универсальной гарантии Байеса- согласованности ${\mathsf{MedNet}}$ для метрических функций потерь на пространствах меток BIE (Tsir Cohen & Kontorovich, 2022), получаем

R_{{\bar{\mu}}_{j}}(\widehat{f}_{2m,j})\to 0\qquad\text{almost surely as }m\to\infty.

(4)

(Когда $S^{(2)}_{2m,j}$ пусто, правило выводит значение по умолчанию $q_{j}$ ; этот случай происходит только конечное число раз почти наверное, когда $p_{j}>0$ , и не влияет на предел.) Поскольку существует счетное число ячеек, мы можем пересечь события вероятности единица в (4) по всем $j\in\mathbb{N}$ , чтобы получить одно событие вероятности единица, на котором (4) выполняется для каждого $j$ одновременно (ячейки с $p_{j}=0$ несущественны).

Шаг 4: агрегировать риск и сделать вывод.

Для достаточно большого $n=2m$ , при котором выполняется (1), общий предсказатель удовлетворяет $\widehat{f}_{2m}(x)=\widehat{f}_{2m,j}(x)$ при $x\in C_{K,j}$ . Разлагая риск по разбиению,

R_{{\bar{\mu}}}(\widehat{f}_{2m}):=\sum_{j\geq 1}p_{j}\,R_{{\bar{\mu}}_{j}}(\widehat{f}_{2m,j}).

(5)

Зафиксируйте $\varepsilon>0$ . Начиная с $\sum_{j\geq 1}p_{j}=1$ , выберите $J$ так, чтобы $\sum_{j>J}p_{j}<\varepsilon$ . На событии вероятности один, на котором (4) выполняется для всех $j\leq J$ , выберите $m$ достаточно большим, чтобы $R_{{\bar{\mu}}_{j}}(\widehat{f}_{2m,j})<\varepsilon$ для каждого $j\leq J$ . Затем, используя (3), чтобы ограничить каждую условную величину риска величиной $4\gamma_{K+1}$ ,

R_{{\bar{\mu}}}(\widehat{f}_{2m})\leq\sum_{j\leq J}p_{j}\,\varepsilon\;+\;\sum_{j>J}p_{j}\,(4\gamma_{K+1})\leq\varepsilon+4\gamma_{K+1}\,\varepsilon.

Поскольку $K$ зафиксирована на пути выборки, $\gamma_{K+1}<\infty$ , и потому что $\varepsilon>0$ была произвольной, это показывает $R_{{\bar{\mu}}}(\widehat{f}_{2m})\to 0$ почти наверняка по четной подпоследовательности. Полная последовательность $R_{{\bar{\mu}}}(\widehat{f}_{n})$ также сходится к $0$ почти наверняка, потому что $R_{{\bar{\mu}}}(\widehat{f}_{2m})\to 0$ подразумевает $\limsup_{n\to\infty}R_{{\bar{\mu}}}(\widehat{f}_{n})=0$ (например, если рассмотреть ближайший четный индекс и отметить, что построение отличается только на $O(1)$ наблюдений). Это завершает доказательство. ∎

Ссылки

⟦Attias, I., Hanneke, S., Kalavasis, A., Karbasi, A., and Velegkas, G. Оптимальные обучающиеся для реализуемой регрессии: Pac learning и online learning, 2024a. URL https://arxiv.org/abs/2307.03848.
⟦Attias et al. (2024b) Аттиас, И., Ханнеке, С., Калавасис, А., Карбаси, А., и Велейскас, Г. Универсальные скорости для регрессии: разделения между граничным и абсолютным значением потерь. В материалах Тридцать седьмой конференции по обучению теории, стр. 359–405. PMLR, июнь 2024b. URL https://proceedings.mlr.press/v247/attias24a.html. ISSN: 2640-3498.
⟦Bousquet et al. (2020) Bousquet, O., Hanneke, S., Moran, S., van Handel, R., and Yehudayoff, A. A theory of universal learning, 2020. URL https://arxiv.org/abs/2011.04483.
⟦Brukhim et al. (2022) Брухим, Н., Кармон, Д., Динур, И., Моран, С., и Йехудайофф, А. Характеризация многоклассовой обучаемости, март 2022. URL http://arxiv.org/abs/2203.01550. arXiv:2203.01550 [cs].
Gottlieb et al. (2014) Gottlieb, L., Kontorovich, A., и Krauthgamer, R. Эффективная классификация для метрических данных (расширенный тезис COLT 2010). IEEE Transactions on Information Theory, 60(9):5750–5759, 2014. doi: 10.1109/TIT.2014.2339840. URL http://dx.doi.org/10.1109/TIT.2014.2339840.
⟦Gottlieb, L.-A. и Krauthgamer, R. Алгоритмы близости для почти удвоения пространств. SIAM J. Discrete Math., 27(4):1759–1769, 2013.
⟦Hanneke, S., Kontorovich, A., Sabato, S., and Weiss, R. Универсальная байесовская сходимость в метрических пространствах, 2021. URL https://arxiv.org/abs/1906.09855.
Hanneke et al. (2023) Ханнеке, С., Моран, С., и Чжан, Ц. Универсальные скорости для многоклассового обучения, июль 2023. URL http://arxiv.org/abs/2307.02066. arXiv:2307.02066 [cs].
Littlestone (1988) Литтлстоун, Н. Обучение с высокой скоростью при наличии множества несущественных атрибутов: новый линейно-пороговый алгоритм. Машинное обучение, 2(4):285–318, 1988. doi: 10.1007/BF00116827.
Tsir Cohen & Kontorovich (2022) Цир Коэн, Д. и Конторович, А. Обучение с метрическими потерями. В Loh, P.-L. и Raginsky, M. (ред.), Proceedings of Thirty Fifth Conference on Learning Theory, том 178 из Proceedings of Machine Learning Research, стр. 662–700. PMLR, 02–05 Jul 2022. URL https://proceedings.mlr.press/v178/cohen22a.html.

Appendix A Дополнительные материалы

A.1 Практическая значимость и примеры

Наша характеристика применяется к любому классу гипотез ${\mathcal{H}}\subseteq{\mathcal{Y}}^{\mathcal{X}}$ над польскими пространствами. Естественный вопрос заключается в том, какие часто изучаемые классы удовлетворяют условию без деревьев (то есть допускают отсутствие бесконечного неубывающего- $(\gamma_{k})$ -Littlestone-дерева с $\gamma_{k}\to\infty$ ) и, следовательно, допускают реализуемую сильную универсальную байесовскую-согласованность (RSUBC)? Мы приводим один положительный и один отрицательный пример, чтобы сформировать интуицию.

Пример 1: класс, который допускает дерево с неограниченным разрывом (не поддающееся обучению).

Контрпример из Раздела 3 неявно строит неограниченно-разнесённое дерево Littlestone. Вспомните ${\mathcal{H}}=\{f:\forall k\in\mathbb{N},\;f(x)\in\{0,2^{2k+1}\}\text{ for }x\in I_{k}\}$ , где $I_{k}=(2^{-k},2^{-(k-1)})$ . Дерево строится следующим образом: на глубине $k$ разместите экземпляр $x_{k}$ в любой точке $I_{k}$ , и назначьте две исходящие метки $y_{k,1}=0$ и $y_{k,2}=2^{2k+1}$ . Промежуток равен $\ell(y_{k,1},y_{k,2})=2^{2k+1}\to\infty$ . Поскольку интервалы $(I_{k})_{k\geq 1}$ попарно не пересекаются, выбор меток на разных глубинах независим: для каждого пути от корня к листу (конечного или бесконечного) гипотеза в ${\mathcal{H}}$ , которая реализует соответствующий двоичный выбор на каждом интервале, осуществляет его. Это реализуемое монотонно-неубывающее- $\gamma_{k}$ -дерево Littlestone с $\gamma_{k}=2^{2k+1}$ (Определения 4.1–4.2), и Теорема 5.1 показывает, что ни один обучающийся не может быть согласованным.

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

Пример 2: класс без деревьев с неограниченным разрывом (обучаемый).

Пусть ${\mathcal{X}}=[0,1]$ , ${\mathcal{Y}}=\mathbb{R}$ , $\ell(y,y^{\prime})=|y-y^{\prime}|$ , и пусть ${\mathcal{H}}=\{f:[0,1]\to\mathbb{R}:f\text{ is }L\text{-Lipschitz}\}$ для фиксированной константы $L>0$ . Этот класс имеет неограниченный диапазон (поскольку $f(0)$ не ограничено), однако он не допускает бесконечного неубывающего- $\gamma_{k}$ -дерева Littlestone с $\gamma_{k}\to\infty$ .

Чтобы понять почему, предположим, что злоумышленник пытается построить такое дерево. На глубине $1$ злоумышленник может предъявить любой экземпляр $x_{1}\in[0,1]$ с двумя метками $y_{1,1},y_{1,2}$ , сколь угодно далеко разнесёнными (две $L$ -Lipschitz-функции с разными «сдвигами» могут расходиться в любой величине в одной точке). Но как только обучающийся фиксирует метку $v_{1}$ в $x_{1}$ , каждая $L$ -Lipschitz-функция, согласованная с этим выбором, должна удовлетворять $|f(x)-v_{1}|\leq L|x-x_{1}|\leq L$ для всех $x\in[0,1]$ . Следовательно, на любой глубине $k\geq 2$ разрыв между двумя предложенными метками не превосходит $2L$ . Поскольку $\gamma_{k}\to\infty$ , в конечном итоге $\gamma_{k}>2L$ , и у злоумышленника нет допустимого хода. Поэтому не существует бесконечного дерева с неограниченным разрывом, и согласно Теореме 4.5 существует сильно универсально Bayes-совместимый обучающийся для этого класса.

Обсуждение.

Любой класс гипотез с ограниченным диапазоном ( $\sup_{h\in{\mathcal{H}},\,x\in{\mathcal{X}}}\ell(h(x),y_{0})<\infty$ для некоторого $y_{0}\in{\mathcal{Y}}$ ) тривиально не имеет бесконечного бесконечного-расщепляющего дерева. Пример Липшица выше показывает, что даже классы с неограниченным диапазоном могут быть без деревьев, когда условие регулярности (здесь, ограничение Липшица на компактной области) не позволяет противнику поддерживать сколь угодно большие разрывы между метками.

Компактность области имеет решающее значение: класс функций $L$ -Липшица на всём $\mathbb{R}$ допускает бесконечное дерево с неограниченными разрывами (соперник может разнести экземпляры, чтобы создавать растущие разрывы). Аналогично, класс всех монотонных неубывающих функций из $[0,1]$ в $\mathbb{R}$ допускает такое дерево, несмотря на ограничение монотонности: соперник размещает экземпляры $x_{1}<x_{2}<\cdots$ в $[0,1]$ и на каждой глубине $k$ предлагает метки $v$ и $v+\gamma_{k}$ (где $v$ — ранее зафиксированное значение), которые всегда согласуются с монотонностью. Эти контрастирующие примеры иллюстрируют, что препятствие в виде дерева отражает тонкое взаимодействие между структурой класса гипотез, геометрией функции потерь и геометрией области, выходя за рамки простых условий ограниченности.

A.2 О конструктивном характере правила обучения

Правило обучения Раздела 6.5 является «явным» в следующем смысле: при наличии доступа к измеримой выигрышной стратегии $\sigma$ для $P_{L}$ в игре Gale-Stewart шаги алгоритма (вести игру на половине данных, разделить ${\mathcal{X}}$ по терминальной истории, запускать ${\mathsf{MedNet}}$ по ячейкам) полностью конкретны и зависят от данных.

Существование (и универсальная измеримость) $\sigma$ само по себе гарантируется Bousquet et al. (2020, Corollary 3.5) посредством неконструктивного аргумента о определенности (их Теорема B.1). Это аналогично ситуации в Bousquet et al. (2020), чья универсальная обучающая машина для $0$ – $1$ классификации также опирается на измеримую выигрышную стратегию, чье существование следует из определенности. Как отмечено в их Разделе 3.4, для классов гипотез с счётным порядковым Littlestone измерением стратегия $\sigma$ может быть описана явно с помощью трансфинитной индукции по порядковому измерению. Любая измеримая ${\mathcal{H}}$ имеет не более чем счётное порядковое Littlestone измерение (Bousquet et al., 2020, Lemma B.7), поэтому в принципе стратегия допускает конкретное (пусть и сложное) описание для любого класса, встречающегося на практике.

A.3 Измеримость выигрышной стратегии

Существование универсально измеримой выигрышной стратегии $\sigma$ для $P_{L}$ следует из Bousquet et al. (2020, Corollary 3.5), которая устанавливает, что при предположениях о польском пространстве и измеримости класса понятий (в смысле их Определения 3.3) любая игра Гейла—Стюарта с выигрышным условием, допускающим конечное распознавание, имеет универсально измеримую выигрышную стратегию для обучающегося.

Непосредственная теорема B.1 из Bousquet et al. (2020) требует, чтобы множества ответов обучаемого $\{Y_{t}\}$ были счетными. В нашей игре $P_{L}$ выбирает индекс из $\{1,2\}$ (выбирая одну из двух предложенных меток), поэтому каждое $Y_{t}=\{1,2\}$ является счетным; пространства ходов противника $X_{t}={\mathcal{X}}\times{\mathcal{Y}}\times{\mathcal{Y}}$ являются польскими. Условие выигрыша разрешимо конечным числом шагов (игра заканчивается, когда у $P_{A}$ нет допустимого хода), а коаналитичность множества выигрыша $W$ следует тем же аргументом о проекции, что и в доказательстве Bousquet et al. (2020, Corollary 3.5): дополнение $W^{c}$ (игра продолжается вечно) является аналитическим, поскольку на каждом конечном префиксе условие корректности « $\exists\,h\in{\mathcal{H}}$ согласовано с историей» выразимо как проекция на польское параметрическое пространство $\Theta$ из определения 3.3. Поэтому теорема B.1 применяется непосредственно.

A.4 При предположении о компактной параметризации

В Теореме 4.5 характеризация формулируется в терминах понятия конечного префиксного дерева (Определение 4.1), тогда как нижняя оценка (Теорема 5.1) требует, чтобы каждый бесконечный путь через дерево был реализован одной-единственной гипотезой (Определение 4.2). Лемма 4.3 устраняет этот разрыв при сделанном предположении о компактной параметризации.

A.4.1 Доказательство Леммы 4.3

Доказательство.

Зафиксируйте бесконечный путь $b=(b_{1},b_{2},\ldots)\in\{1,2\}^{\mathbb{N}}$ через дерево. Для каждого конечного префикса длины $k$ конечнопрефиксная осуществимость дает параметр $\theta_{k}\in\Theta$ так что $h(\theta_{k},x_{j})=y_{j,b_{j}}$ для всех $j\leq k$ . Определите

\Theta_{k}(b)\;=\;\bigl\{\theta\in\Theta:h(\theta,x_{j})=y_{j,b_{j}}\;\text{for all }j\leq k\bigr\}.

Каждое $\Theta_{k}(b)$ непусто (оно содержит $\theta_{k}$ ) и замкнуто (прообраз замкнутого множества $\{y_{j,b_{j}}\}$ при отображении $\theta\mapsto h(\theta,x_{j})$ , которое непрерывно в $\theta$ по предположению, пересечённый по конечно многим $j$ ). Кроме того $\Theta_{1}(b)\supseteq\Theta_{2}(b)\supseteq\cdots$ является убывающей цепочкой непустых замкнутых подмножеств компактного пространства $\Theta$ . Поскольку цепочка убывает, каждая конечная подколлекция $\Theta_{k_{1}}(b),\ldots,\Theta_{k_{m}}(b)$ удовлетворяет $\bigcap_{i=1}^{m}\Theta_{k_{i}}(b)=\Theta_{\max_{i}k_{i}}(b)\neq\emptyset$ , так что семейство $\{\Theta_{k}(b)\}_{k\geq 1}$ имеет свойство конечного пересечения. Поскольку каждое $\Theta_{k}(b)$ является замкнутым подмножеством компактного пространства $\Theta$ , компактность влечёт $\bigcap_{k\geq 1}\Theta_{k}(b)\neq\emptyset$ . Любое $\theta^{*}$ в этом пересечении удовлетворяет $h(\theta^{*},x_{j})=y_{j,b_{j}}$ для всех $j$ , так что $h(\theta^{*},\cdot)\in{\mathcal{H}}$ реализует весь бесконечный путь $b$ . ∎

A.4.2 Почему это предположение необходимо

Без предположения компактной параметризации два понятия дерева могут различаться. Рассмотрим следующий пример.

Настройка. Пусть $\Theta=\mathbb{N}_{0}$ (неотрицательные целые числа с дискретной топологией, которая является польской), ${\mathcal{X}}=\{x_{k}:k\in\mathbb{N}\}$ (счётные, дискретные), ${\mathcal{Y}}=\mathbb{R}$ с $\ell(y,y^{\prime})=|y-y^{\prime}|$ , и определим

h(n,x_{k})\;=\;(\text{$k$-th binary digit of $n$})\cdot k,

так, чтобы ${\mathcal{H}}=\{h_{n}:n\in\mathbb{N}_{0}\}$ где $h_{n}(\cdot)=h(n,\cdot)$ .

Существует дерево определения 4.1. На глубине $k$ разместите экземпляр $x_{k}$ с метками $y_{k,1}=0$ и $y_{k,2}=k$ ; зазор равен $\ell(0,k)=k\to\infty$ , поэтому зазоры невозрастающие и расходящиеся. Каждый конечный путь $(b_{1},\dots,b_{K})\in\{1,2\}^{K}$ реализуется $n=\sum_{k=1}^{K}\mathbf{1}[b_{k}=2]\cdot 2^{k-1}$ (установите $k$ -й двоичный разряд числа $n$ в $1$ тогда и только тогда, когда $b_{k}=2$ ).

Не всякий бесконечный путь реализуем. Весь путь- $2$ , $b_{k}=2$ для всех $k$ , требует $n$ , у которой каждый двоичный разряд равен $1$ , то есть $n=\sum_{k\geq 1}2^{k-1}=\infty$ . Ни одно конечное целое число не обладает этим свойством, так что ни $h_{n}\in{\mathcal{H}}$ не реализует этот бесконечный путь.

Поскольку ${\mathcal{H}}$ RSUBC. Каждый $h_{n}$ имеет только конечное число ненулевых значений (так как $n$ имеет конечное число двоичных разрядов, равных $1$ ). Обучающий memorize-and-predict- $0$ достигает риска $\to 0$ для каждой строго реализуемой распределения (так как $f^{\star}$ имеет конечную область поддержки, каждая точка области поддержки в конечном счёте наблюдается). В действительности, тот же самый обучающий также работает при несоблюдении строгости реализуемости; см. Раздел A.4.5.

Этот пример показывает, что Определение 4.1 дерево может сосуществовать с RSUBC. Следовательно, нижнюю границу нельзя доказать только из Определение 4.1; разрыв между двумя определениями является подлинным. Заметьте, что $\Theta=\mathbb{N}_{0}$ не компактно (оно дискретно и бесконечно), поэтому предположение о компактной параметризации Леммы 4.3 не выполняется.

A.4.3 Предположение не исключает неоучаемость

Предположение о компактной параметризации не ограничивает ${\mathcal{Y}}$ быть ограниченным, и невозможность обучения остается возможной даже когда это предположение выполняется. Пространство меток ${\mathcal{Y}}$ остается общим (возможно, неограниченным) полным пространством Полиша, и интервалы между метками вдоль дерева все еще могут расходиться ( $\gamma_{k}\to\infty$ ), сохраняя характер бесконечных потерь в характеризации. То, что гарантирует это предположение, состоит в том, что для каждого фиксированного экземпляра $x$ достижимое множество меток $\{h(\theta,x):\theta\in\Theta\}$ является компактным в ${\mathcal{Y}}$ ; однако диаметр этого множества может расти без ограничения по мере того, как $x$ меняется.

Мотивирующий контрпример из раздела 3 наглядно демонстрирует это. Вспомните ${\mathcal{H}}=\{f:\forall k\in\mathbb{N},\;f(x)\in\{0,2^{2k+1}\}\text{ for }x\in I_{k}\}$ , где $I_{k}=(2^{-k},2^{-(k-1)})$ . Каждая функция в ${\mathcal{H}}$ определяется двоичной последовательностью $\theta=(\theta_{1},\theta_{2},\ldots)\in\{0,1\}^{\mathbb{N}}$ , где $\theta_{k}$ выбирает, определяет ли $f$ отображение $I_{k}$ в $0$ или в $2^{2k+1}$ . Таким образом естественное параметрическое пространство есть $\Theta=\{0,1\}^{\mathbb{N}}$ , и оно компактно (в силу теоремы Тихонова, как счетное произведение конечных пространств) и польское (метрика произведения $d(\theta,\theta^{\prime})=\sum_{k}2^{-k}|\theta_{k}-\theta^{\prime}_{k}|$ полна и сепарабельна). Оценочное отображение $h(\theta,x)=\theta_{k}\cdot 2^{2k+1}$ для $x\in I_{k}$ непрерывно по $\theta$ (оно зависит только от $k$ -й координаты, которая является непрерывной проекцией в топологии произведения).

Однако разрывы меток на глубине $k$ соответствующего дерева Littlestone равны $\gamma_{k}=2^{2k+1}\to\infty$ , поэтому класс допускает дерево с неограниченными разрывами и не является RSUBC согласно теореме 5.1. Иными словами, предположение о компактной параметризации совместимо с полным диапазоном явлений необучаемости, которые охватывает наша характеристика.

A.4.4 Примеры настроек, удовлетворяющих предположению

• Конечные или компактные пространства меток. Когда ${\mathcal{Y}}$ компактно (например, бинарная классификация с ${\mathcal{Y}}=\{0,1\}$ , многоклассовая классификация с конечным ${\mathcal{Y}}$ или ограниченная регрессия с ${\mathcal{Y}}=[a,b]$ ), пространство функций ${\mathcal{Y}}^{\mathcal{X}}$ компактно в произведенческой топологии в силу теоремы Тихонова, а классическое аргументирование компактности Bousquet et al. (2020) показывает, что две понятия дерева совпадают автоматически. В этом случае наше допущение компактной параметризации не требуется и является строго слабее, чем компактность ${\mathcal{Y}}$ .
⟦• Параметрические семейства с ограниченными параметрами. Нейронные сети с ограниченными весами, опорные векторные машины с ограниченными ядрами и липшицевы функции на компактных областях естественным образом имеют компактные пространства параметров (например, $\Theta=[-W,W]^{d}$ ) и непрерывные отображения оценки.
⟦• Контрпример патологический. Разделяющий пример из Раздела A.4.2 использует $\Theta=\mathbb{N}_{0}$ (дискретное, некомпактное) и разрывное отображение оценки. Классы, параметризованные счетным бесконечным дискретным пространством без предельных точек, необычны в практических задачах обучения. В отличие от этого, предположение о компактной параметризации позволяет $\Theta$ быть любой компактной польской пространством, которое включает все компактные подмножества $\mathbb{R}^{d}$ , компактные многообразия и многие бесконечномерные пространства (например, компактные подмножества пространств функций в компактно-открытой топологии).

A.4.5 Осуществимость без компактности

В данной работе реализуемость определяется как $\inf_{h\in{\mathcal{H}}}R_{{\bar{\mu}}}(h)=0$ (незначимая реализуемость). Без предположения о компактной параметризации это не гарантирует существование гипотезы, достигающей нулевого риска, и две естественные концепции реализуемости могут расходиться:

⟦Строгая реализуемость: существует $f^{\star}\in{\mathcal{H}}$ такая, что $Y=f^{\star}(X)$ почти наверное, то есть некоторая гипотеза в ${\mathcal{H}}$ достигает нулевого риска.
⟦Нестрогое достижение реализуемости (определение, используемое в данной статье): $\inf_{h\in{\mathcal{H}}}R_{{\bar{\mu}}}(h)=0$ , то есть байесовский риск равен нулю, но ни одна отдельная гипотеза не обязана его достигать.

При допущении компактной параметризации (компактное $\Theta$ , $h$ непрерывно по $\theta$ ) образ ${\mathcal{H}}=\{h(\theta,\cdot):\theta\in\Theta\}$ компактен в произведенной топологии на ${\mathcal{Y}}^{\mathcal{X}}$ . Если $\inf_{h\in{\mathcal{H}}}R_{{\bar{\mu}}}(h)=0$ , то последовательность $\theta_{n}$ , минимизирующая риск, в компактном пространстве $\Theta$ имеет сходящуюся подпоследовательность $\theta_{n_{j}}\to\theta^{\star}$ , а непрерывность дает $R_{{\bar{\mu}}}(h(\theta^{\star},\cdot))=0$ , так что инфимум достигается и две формулировки совпадают.

Без компактности инфимум может не достигаться. Рассмотрим ${\mathcal{X}}=\mathbb{N}$ (дискретное), ${\mathcal{Y}}=\mathbb{N}_{0}$ с $\ell_{1}$ -loss и ${\mathcal{H}}=\{h:\mathbb{N}\to\mathbb{N}_{0}:\operatorname{supp}(h)\text{ is finite}\}$ . Пусть $g:\mathbb{N}\to\mathbb{N}_{0}$ будет любой функцией с бесконечной поддержкой (например, $g(k)=k$ ), и пусть ${\bar{\mu}}$ будет распределением с $X\sim\mu_{X}$ , поддержанной на всём $\mathbb{N}$ (например, $\mu_{X}(\{k\})=c/k^{3}$ для константы нормировки $c$ ) и $Y=g(X)$ . Определяя $h_{N}(k)=g(k)\mathbf{1}_{k\leq N}$ , получаем $h_{N}\in{\mathcal{H}}$ с $R_{{\bar{\mu}}}(h_{N})=\sum_{k>N}\mu_{X}(\{k\})\,|g(k)|$ . Для этого ${\mathcal{H}}$ нестрогая реализуемость ( $\inf_{h\in{\mathcal{H}}}R_{{\bar{\mu}}}(h)=0$ ) на самом деле эквивалентна условию по первому моменту $\sum_{k}\mu_{X}(\{k\})\,|g(k)|<\infty$ : сходимость ряда означает, что хвосты исчезают, тогда как расходимость заставляет каждую $h\in{\mathcal{H}}$ (с конечной поддержкой) нести бесконечный риск. Когда выполняется условие по первому моменту, $R_{{\bar{\mu}}}(h_{N})\to 0$ , так что $\inf_{h\in{\mathcal{H}}}R_{{\bar{\mu}}}(h)=0$ . Однако $g\notin{\mathcal{H}}$ (бесконечная поддержка), поэтому ни один $f^{\star}\in{\mathcal{H}}$ не достигает нулевого риска: ${\bar{\mu}}$ нестрого реализуема, но не строго реализуема.

Несмотря на этот разрыв, запоминающе-и-предсказывающий $0$ обучающийся успешно работает при обоих понятиях реализуемости. При строгой реализуемости рассуждение является непосредственным ( $f^{\star}$ имеет конечную поддержку, так что любая точка поддержки в конечном итоге наблюдается). При неточной реализуемости риск обучающегося равен $\sum_{k}\mu_{X}(\{k\})\,|g(k)|\,\mathbf{1}\{k\notin\{X_{1},\dots,X_{n}\}\}$ ; каждая атомарная компонента с $\mu_{X}(\{k\})>0$ в конечном итоге наблюдается почти наверняка, и термины ограничены суммируемой $\mu_{X}(\{k\})\,|g(k)|$ , так что по теореме о предельном переходе, ограниченном $R_{{\bar{\mu}}}(A(S_{n}))\to 0$ почти наверняка.

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

A.4.6 Открытый вопрос: удаление компактности

Является ли характеристика теоремы 4.5 применимой к общим многочленам Польши $\Theta$ (без компактности), является интересной открытой задачей.

Мы знаем, что Определение 4.1 (реализуемость с конечным префиксом) не является корректным препятствием в общем случае. Разделяющий пример из Раздела A.4.2 демонстрирует это: класс ${\mathcal{H}}=\{h:\mathbb{N}\to\mathbb{N}_{0}:\operatorname{supp}(h)\text{ is finite}\}$ допускает Определение 4.1-дерево с $\gamma_{k}=k\to\infty$ , однако не каждая бесконечная ветвь реализуема (ветвь «все ненулевые» требует бесконечную поддержку), и тем не менее класс является RSUBC. Таким образом, препятствие, связанное с деревом конечного префикса, порождает ложные срабатывания без предположения компактной параметризации. Полная характеристика в некопактном случае, вероятно, потребует иного понятия дерева; одно возможное направление — вариант «допускающий монеты», при котором случайно выбранная бесконечная ветвь реализуема с вероятностью единица, а не требует, чтобы реализуемой была каждая детерминированная ветвь. Остается открытым вопрос о нахождении минимальных топологических или мерно-теоретических условий (более слабых, чем компактность), при которых рассуждение о конечных пересечениях Леммы 4.3 по-прежнему сохраняет силу.

A.5 Барьеры для универсального расширения

Наша характеристика рассматривает реализуемый случай: предполагается, что порождающее данные распределение ${\bar{\mu}}$ является реализуемым ( $\inf_{h\in{\mathcal{H}}}R_{{\bar{\mu}}}(h)=0$ ). Естественным продолжением является вопрос о том, распространяется ли данная характеристика на анонимный случай, где ${\bar{\mu}}$ может быть не реализуемым.

Ключевое препятствие заключается в аргументе верхней границы. Процедура стабилизации (раздел 6.3) приводит игру Гейла—Стюарта в действие, используя точки выборки $(X_{i},Y_{i})$ и, что особенно важно, опирается на то, что $Y_{i}=f^{\star}(X_{i})\in V_{k}(X_{i})$ (истинная метка достижима, исходя из текущей истории). В агностической постановке метки не обязаны происходить из какого-либо $h\in{\mathcal{H}}$ , поэтому точки выборки могут не представлять собой допустимые ходы в игре, и аргумент стабилизации рушится.

Кроме того, контрпример из Раздела 3 показывает, что естественное распределительное условие $R^{\star}<\infty$ недостаточно даже в реализуемом случае. В агностическом случае нужно было бы одновременно учитывать ошибку аппроксимации (разрыв между $R^{\star}$ и $0$ ) и трудность оценивания при неограниченном масштабе, вероятно требуя принципиально иного описания. Агастический аналог нашего результата является интересной открытой проблемой (связанной с открытым вопросом, первоначально поставленным Tsir Cohen & Kontorovich (2022)), оставленной для будущих исследований.

A.6 Контрпример: бесконечный риск на не наблюдавшихся интервалах

Здесь мы приводим вычисление, отложенное для раздела 3, показывающее, что при любом реализованном выборочном наборе обученный предиктор несёт бесконечный риск почти наверное.

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

I(S_{n}):=\{k\in\mathbb{N}:\ \exists i\leq n\ \text{with}\ X_{i}\in I_{k}\}.

Условие на реализованной выборке $S_{n}$ . Тогда $h_{n}={\mathcal{A}}(S_{n})$ зафиксировано, и для каждого неувиденного интервала $k\notin I(S_{n})$ бит $B_{k}$ остается независимой честной монетой при условном законе (поскольку ни одна точка выборки не попала в $I_{k}$ ). Запишите вклад интервала $I_{k}$ в риск как

	$\displaystyle R_{k}(B_{k})$	$\displaystyle=\int_{I_{k}}\ell\bigl(h_{n}(x),f_{B}(x)\bigr)\,dx$
		$\displaystyle=$

По неравенству треугольника, для каждого $x\in I_{k}$ , $|h_{n}(x)|+|h_{n}(x)-2^{2k+1}|\geq 2^{2k+1}$ . Интегрирование по $I_{k}$ дает

	$\displaystyle\int_{I_{k}}\|h_{n}(x)\|\,dx\;+\;\int_{I_{k}}\|h_{n}(x)-2^{2k+1}\|\,dx$	$\displaystyle\geq\|I_{k}\|\cdot 2^{2k+1}$
		$\displaystyle=2^{-k}\cdot 2^{2k+1}$
		$\displaystyle=2^{k+1}.$

Отсюда по крайней мере один из двух показанных интегралов не меньше $2^{k}$ , так что $\operatorname{\mathbb{P}}(R_{k}(B_{k})\geq 2^{k}\mid S_{n})\geq\tfrac{1}{2}$ . Поскольку события $\{R_{k}(B_{k})\geq 2^{k}\}$ по $k\notin I(S_{n})$ независимы при условии $S_{n}$ , второе лемма Бореля—Кантелли означает, что почти наверное (по $B$ при условии $S_{n}$ ) бесконечно много неувиденных $k$ удовлетворяют $R_{k}(B_{k})\geq 2^{k}$ . Следовательно,

	$\displaystyle R_{{\bar{\mu}}_{B}}(h_{n})$	$\displaystyle=\sum_{k\geq 1}R_{k}(B_{k})\geq\sum_{\begin{subarray}{c}k\notin I(S_{n})\\ R_{k}(B_{k})\geq 2^{k}\end{subarray}}2^{k}$
		$\displaystyle=\infty\quad\text{almost surely (over $B$ conditional on $S_{n}$).}$

Беря ожидание по совместной выборке $(B,S_{n})$ и применяя формулу Фубини, мы получаем: для каждого фиксированного $n$ для $\operatorname{\mathbb{P}}$ -почти всех $B$ выполняется $\operatorname{\mathbb{P}}_{S_{n}\sim{\bar{\mu}}_{B}^{n}}(R_{{\bar{\mu}}_{B}}({\mathcal{A}}(S_{n}))=\infty)=1$ , следовательно $\mathop{\mathbb{E}}_{S_{n}\sim{\bar{\mu}}_{B}^{n}}[R_{{\bar{\mu}}_{B}}({\mathcal{A}}(S_{n}))]=\infty$ . Наконец, беря счетное пересечение по $n\in\mathbb{N}$ , существует единственное фиксированное $B^{\star}$ (эквивалентно, единственное фиксированное $f^{\star}=f_{B^{\star}}\in{\mathcal{H}}$ ), такое что для фиксированного реализуемого распределения ${\bar{\mu}}:={\bar{\mu}}_{B^{\star}}$ ,

\mathop{\mathbb{E}}_{S_{n}\sim{\bar{\mu}}^{n}}\bigl[R_{{\bar{\mu}}}({\mathcal{A}}(S_{n}))\bigr]=\infty\qquad\text{for all }n\in\mathbb{N}.

A.7 Доказательство теоремы 5.1

Доказательство.

Зафиксируйте реализуемое бесконечное неубывающее- $\gamma_{k}$ -дерево Литтлстоуна, как в определении 4.2. Так как $\gamma_{k}\to\infty$ , для каждого $m\geq 1$ задайте индекс

k_{m}:=\min\{k\geq 1:\ \gamma_{k}\geq m^{2}\},

которое конечно и неубывающе в $m$ (и строго возрастает после удаления дубликатов). Пусть $p_{m}:=\frac{6}{\pi^{2}}\cdot\frac{1}{m^{2}}$ так, что $\sum_{m\geq 1}p_{m}=1$ . Теперь выберем случайный бесконечный путь от корня к листу, нарисовав i.i.d. справедливые биты $(B_{k})_{k\geq 1}$ , $B_{k}\in\{1,2\}$ . Для каждого исхода $B$ пусть ${\bar{\mu}}_{B}$ будет распределением, поддержанным на узлах пути на глубинах $(k_{m})$ :

\operatorname{\mathbb{P}}_{{\bar{\mu}}_{B}}\!\bigl(X=x_{k_{m}}(B)\bigr)=p_{m},

Y=y_{k_{m},B_{k_{m}}}(B)\ \ \text{(deterministically)}.

Здесь $x_{k_{m}}(B)$ обозначает экземпляр глубины- $k_{m}$ на пути, определяемом $B_{1},\dots,B_{k_{m}-1}$ , а $y_{k_{m},1}(B),y_{k_{m},2}(B)$ — это две метки исходящих ребер в этой вершине. В силу реализуемости дерева, для каждого $B$ существует $f_{B}^{\star}\in{\mathcal{H}}$ , реализующее весь путь; в частности $Y=f_{B}^{\star}(X)$ почти наверняка под ${\bar{\mu}}_{B}$ , так что ${\bar{\mu}}_{B}$ реализуемо.

Исправьте любой алгоритм обучения ${\mathcal{A}}$ и любой $n$ . Постройте $B$ , а затем $S_{n}\sim{\bar{\mu}}_{B}^{n}$ , и пусть $h_{n}:={\mathcal{A}}(S_{n})$ . Пусть $M(S_{n})$ будет максимальным индексом $m$ , таким что выборка содержит точку с $X=x_{k_{m}}(B)$ (берите $M(S_{n})=0$ , если нет). Тогда $M(S_{n})<\infty$ детерминированно, поскольку это максимум из $n$ положительных целых чисел (хотя $M(S_{n})$ случайна и не ограничена никакой фиксированной константой равномерно по $B$ ).

Рассмотрим любое $m>M(S_{n})$ . При условии $S_{n}$ и истории пути вплоть до глубины $k_{m}{-}1$ , узел $x_{k_{m}}(B)$ и его две метки $y_{k_{m},1}(B),y_{k_{m},2}(B)$ зафиксированы, в то время как $B_{k_{m}}$ по-прежнему честная монета. Таким образом, по неравенству треугольника,

		$\displaystyle\mathop{\mathbb{E}}\!\left[\ell\bigl(h_{n}(x_{k_{m}}(B)),\,Y\bigr)\ \middle\|\ S_{n},\ (B_{j})_{j<k_{m}}\right]$
		$\displaystyle\quad=\tfrac{1}{2}\,\ell\bigl(h_{n}(x_{k_{m}}(B)),y_{k_{m},1}(B)\bigr)$
		$\displaystyle\qquad+\tfrac{1}{2}\,\ell\bigl(h_{n}(x_{k_{m}}(B)),y_{k_{m},2}(B)\bigr)$
		$\displaystyle\quad\geq\tfrac{1}{2}\,\ell\bigl(y_{k_{m},1}(B),y_{k_{m},2}(B)\bigr)$
		$\displaystyle\quad\geq\tfrac{\gamma_{k_{m}}}{2}$
		$\displaystyle\quad\geq\tfrac{m^{2}}{2}.$

Для каждого $m>M(S_{n})$ определите

\displaystyle b_{m}^{\mathrm{bad}}=\arg\max_{b\in\{1,2\}}\ell\bigl(h_{n}(x_{k_{m}}(B)),\,y_{k_{m},b}(B)\bigr)

(произвольно разрывает связи), и событие $E_{m}:=\{B_{k_{m}}=b_{m}^{\mathrm{bad}}\}$ . Поскольку $B_{k_{m}}$ является свежей справедливой монетой при условии $S_{n}$ и $(B_{j})_{j<k_{m}}$ , получаем

\operatorname{\mathbb{P}}(E_{m}\mid S_{n},\,(B_{j})_{j<k_{m}})=\tfrac{1}{2},

и на $E_{m}$ ,

	$\displaystyle\ell\bigl(h_{n}(x_{k_{m}}(B)),\,Y\bigr)$	$\displaystyle=\ell\bigl(h_{n}(x_{k_{m}}(B)),\,y_{k_{m},B_{k_{m}}}(B)\bigr)$
		$\displaystyle\geq\tfrac{1}{2}\,\ell\bigl(y_{k_{m},1}(B),y_{k_{m},2}(B)\bigr)$
		$\displaystyle\geq\tfrac{m^{2}}{2}.$

Кроме того, при условии $S_{n}$ и полной истории путей $(B_{j})_{j\geq 1}$ за исключением координат $\{B_{k_{m}}:m>M(S_{n})\}$ , биты $\{B_{k_{m}}:m>M(S_{n})\}$ являются независимыми честными монетами. Следовательно, в силу (условного) Borel-Cantelli, $\operatorname{\mathbb{P}}(E_{m}\ \text{i.o.}\mid S_{n})=1$ . Поэтому почти наверное,

	$\displaystyle R_{{\bar{\mu}}_{B}}(h_{n})$	$\displaystyle\;=\;\sum_{m\geq 1}p_{m}\,\ell\bigl(h_{n}(x_{k_{m}}(B)),\,y_{k_{m},B_{k_{m}}}(B)\bigr)$
		$\displaystyle\;\geq\;\sum_{m>M(S_{n})}p_{m}\cdot\frac{m^{2}}{2}\mathbbm{1}\{E_{m}\}$
		$\displaystyle\;=\;\frac{3}{\pi^{2}}\sum_{m>M(S_{n})}\mathbbm{1}\{E_{m}\}$
		$\displaystyle\;=\;\infty.$

В частности, для каждого фиксированного $n$ , $\operatorname{\mathbb{P}}_{B,S_{n}}\!\bigl(R_{{\bar{\mu}}_{B}}({\mathcal{A}}(S_{n}))=\infty\bigr)=1$ , так как по теореме Фубини, для $\operatorname{\mathbb{P}}_{B}$ -почти всех $B$ имеем $\mathop{\mathbb{E}}_{S_{n}\sim{\bar{\mu}}_{B}^{n}}[R_{{\bar{\mu}}_{B}}({\mathcal{A}}(S_{n}))]=\infty$ . Переходя к счетному пересечению по $n\in\mathbb{N}$ этих множеств вероятности один для $B$ , мы можем зафиксировать одно $B^{\star}$ такое, что ожидаемый риск бесконечен для всех $n$ . Установив ${\bar{\mu}}:={\bar{\mu}}_{B^{\star}}$ , завершаем доказательство. ∎

Реализуемая Байесовская согласованность для общих функций потерь метрик

Аннотация

1 Введение

Реализуемая сильная универсальная байесовская согласованность.

Почему неограниченные функции потерь труднее на самом деле.

Основной результат (неформально; см. раздел 4).

Архитектура доказательства.

Вклад.

Организация.

2 Смежные работы

Универсальные характеристики обучения и теоретико-игровой характеризации.

Обучение с метрическими потерями и неограниченным риском.

Обучение в метри́ческом пространстве, методы Липшица и структура двойника.

Связи с классическими комбинаторными размерностями.

3 R∗<∞R^{*}<\infty недостаточно

4 Основной результат: характеристика ℋ{\mathcal{H}}

Definition 4.1 (н невозрастающая-γk\gamma_{k}-Дерево Littlestone).

Definition 4.2 (реализуемая невозрастающая-γk\gamma_{k}-Littlestone tree).

Lemma 4.3 (Лемма связи: реализуемость с конечным префиксом влечёт реализуемость с бесконечным путём).

Доказательство.

Remark 4.4.

Theorem 4.5 (Основная характеристика).

Доказательство.

5 Нижняя граница: существование бесконечного дерева не подразумевает согласованность

Theorem 5.1 (Нижняя граница).

Эскиз доказательства; полное доказательство в Приложении A.7..

Построение распределения.

Непознанные глубины действуют как справедливые монеты.

Расхождение через Бореля–Кантелли.

6 Верхняя граница: отсутствие бесконечного дерева влечёт сильную универсальную согласованность

План-график доказательства.

Стоящие допущения о измеримости.

6.1 Игра Гейл–Стюарта

6.2 Исторически-условные наборы меток

Definition 6.1 (Исторически-условные наборы меток).

Lemma 6.2 (Ограниченный диаметр наборов меток, зависящих от истории).

Доказательство.

6.3 Стабилизация на бесконечной выборке i.i.d.

Lemma 6.3 (Истинная метка содержится в a.s. при новом независимом выборе).

Доказательство.

6.4 Сокращение пер-xx ограниченный диаметр для счетного числа подзадач с ограниченным диапазоном

Lemma 6.4 (Покрытие ограниченного диапазона по ячейкам).

Доказательство.

6.5 Реализуемое правило обучения

Входной сигнал.

Шаг 1: запускайте игру на половине выборки.

Шаг 2: разделение 𝒳{\mathcal{X}} using (qj)(q_{j}).

Вывод предиктора.

6.6 Возможная сильная универсальная байесовская согласованность

Theorem 6.5 (Реализуемая верхняя граница).

Доказательство.

Шаг 1: стабилизация и последующее достижение согласия с терминальной историей.

Шаг 2: счетная разбиение и ограниченные области меток.

Шаг 3: сильная согласованность внутри каждой ячейки.

Шаг 4: агрегировать риск и сделать вывод.

Ссылки

Appendix A Дополнительные материалы

A.1 Практическая значимость и примеры

Пример 1: класс, который допускает дерево с неограниченным разрывом (не поддающееся обучению).

Пример 2: класс без деревьев с неограниченным разрывом (обучаемый).

Обсуждение.

A.2 О конструктивном характере правила обучения

A.3 Измеримость выигрышной стратегии

A.4 При предположении о компактной параметризации

A.4.1 Доказательство Леммы 4.3

Доказательство.

A.4.2 Почему это предположение необходимо

A.4.3 Предположение не исключает неоучаемость

A.4.4 Примеры настроек, удовлетворяющих предположению

A.4.5 Осуществимость без компактности

A.4.6 Открытый вопрос: удаление компактности

A.5 Барьеры для универсального расширения

A.6 Контрпример: бесконечный риск на не наблюдавшихся интервалах

A.7 Доказательство теоремы 5.1

Доказательство.

3 $R^{*}<\infty$ недостаточно

4 Основной результат: характеристика ${\mathcal{H}}$

Definition 4.1 (н невозрастающая- $\gamma_{k}$ -Дерево Littlestone).

Definition 4.2 (реализуемая невозрастающая- $\gamma_{k}$ -Littlestone tree).

6.4 Сокращение пер- $x$ ограниченный диаметр для счетного числа подзадач с ограниченным диапазоном

Шаг 2: разделение ${\mathcal{X}}$ using $(q_{j})$ .