Lista 1

\[ \def\argmin{\operatorname*{argmin}} % \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\Regret{\mathrm{Regret}} \def\bR{\mathbb{R}} \def\bN{\mathbb{N}} \def\cC{\mathcal{C}} \def\cD{\mathcal{D}} \def\cH{\mathcal{H}} \def\cX{\mathcal{X}} \def\cY{\mathcal{Y}} \def\cV{\mathcal{V}} \]

1. PAC-Aprendizado com Tresholds. Considere um caso de classificação binária com custo 0-1 e com os conjuntos \(\cX \coloneqq [n] = \{1, \dotsc, n\}\) e \(\cY = \{0,1\}\). Considere também a classe de hipóteses de tresholds dada por \[ \cH \coloneqq \{ h_{\tau}(x) \coloneqq \ones[x \geq \tau] \colon \tau \in [n + 1]\}. \]

   1. Qual o tamanho de \(\cH\) (em função de \(n\))? Usando só essa informação e os resultados vistos em aula, mostre cotas superiores na complexidade amostral de PAC learning (\(M`(\eps, \delta)\) na definição vista em aula) para ambos os casos realizável e não-realizável.

   2. Para qualquer conjunto \(S \in (\cX \times \cY)^m\), defina \(\tau(S) \coloneqq \max\{x \colon (x,0) \in S\}+ 1\). Mostre que \(h_S(x) \coloneqq \ones[x \geq \tau(S)]\) é um ERM para \(\cH\) no caso realizável.

   3. Mostre que, para qualquer distribuição \(\cD\) sobre \((\cX \times \cY)\) que realiza \(\cH\) e \(\eps > 0\), se \(S \sim \cD^m\) então \[ \prob(L_{D}(h_{S}) > \eps) \leq \exp(-\eps m). \] Isto é, para garantirmos erro não mais que \(\eps\) do ERM com probabilidade pelo menos \(1 - \delta\), basta garantir \(m \geq \log(1/\delta)/\eps\) (note que esse valor não depende de \(n\)).

2. Generalização com Conhecimento a Priori. [MRT Ex. 2.12] Seja \(\cH \subseteq \cX^\cY\) um conjunto de hipóteses enumerável para o problema de classificação binária. Suponha que existe \(p \colon \cH \to (0, \infty)\) tal que \(\sum_{h \in \cH} p(h) = 1\) e seja \(\cD\) uma distribuição sobre \(\cX \times \cY\). Mostre que, para \(S \sim \cD^m\) temos que \[ \prob\Bigg( L_{D}(h) - L_{S}(h) \leq \sqrt{\frac{1}{2m} \cdot \Big(\log \frac{1}{p(h)} + \log \frac{1}{\delta} \Big)}~\textbf{para todo}~h \in \cH \Bigg) \geq 1 - \delta. \] Dica: A cota da união vale para uma coleção enumerável de eventos: link da Wikipedia