Lista 2
\[ \def\argmin{\operatorname*{argmin}} \def\Regret{\operatorname*{Regret}} \def\PRegret{\operatorname*{P-Regret}} \def\WL{\operatorname*{WL}} % \def\T{\mathsf{T}} \def\prob{\mathbb{P}} \def\expect{\mathbb{E}} \def\ones{\mathbf{1}} \def\eps{\varepsilon} \def\ERM{\mathrm{ERM}} \def\DESC{\mathrm{DESC}} \def\VC{\mathrm{VC}} \def\LDim{\mathrm{LDim}} \def\bR{\mathbb{R}} \def\bN{\mathbb{N}} \def\cC{\mathcal{C}} \def\cD{\mathcal{D}} \def\cH{\mathcal{H}} \def\cB{\mathcal{B}} \def\cX{\mathcal{X}} \def\cY{\mathcal{Y}} \def\cV{\mathcal{V}} \]
Dimensão VC de funções simétricas [MRT Ex. 3.26.a]. Defina \(\cX = \{0,1\}^n\). Uma função \(h \colon \cX \to \{0,1\}\) é dita simétrica se \(h(x)\) depende apenas do número de 1’s em \(x\), isto é, para cada \(h \in \cH\) existe \(\phi \colon \bN \to \{0,1\}\) tal que \[ h(x) = \phi\Big(\sum_{i = 1}^n x_i\Big), \qquad \text{para todo}~x \in \cX \] Mostre que a dimensão VC da classe \(\cH \subseteq \{0,1\}^\cX\) de todas as funções simétricas é \(n + 1\).
Piores casos de CONSISTENTE e HALVING. No caso de classifiação binária online, mostre uma classe de hipóteses \(\cH\) e uma sequência de escolhas para o adversário tais que CONSISTENTE comete. \(|\cH| - 1\) erros. Mostre também uma classe de hipóteses \(\cH\) e uma sequência de exemplos para o adversário tais que HALVING comete \(\log |\cH|\) erros.