Classes de Preditores Finitos

Você está aqui

Como consequência do Teorema PAC para convergência uniforme (Teorema 1), para mostrarmos que toda classe finita é um aprendizado PAC basta provarmos que a propriedade de convergência uniforme é válida. Fixado $\epsilon , \delta \in (0,1)$, precisamos encontrar um tamanho amostral $m (\epsilon, \delta)$ tal que para toda probabilidade $\mathbb{P}$, temos que

\[
\mathbb{P}^n \left( {\bf o}_n \in \mathbb{O}^n : \sup_{h \in \mathcal{H}} \big|L_E ({\bf o}_n , h) - L(\mathbb{P} , h)  \big| \leq \epsilon, ~ \forall ~ h \in \mathcal{H}   \right) \geq 1- \delta , \quad n \geq m (\epsilon, \delta).
\] Ao tomarmos o complementar, obtemos que

\[
\mathbb{P}^n \left( {\bf o}_n \in \mathbb{O}^n : \sup_{h \in \mathcal{H}} \big|L_E ({\bf o}_n , h) - L(\mathbb{P} , h)  \big| > \epsilon  \right) < \delta .
\] Desde que $\mathcal{H} = \{h_1, h_2, \cdots , h_N\}$ é um conjunto finito $(N \in \mathbb{N})$, obtemos que

\[
\left\{ {\bf o}_n \in \mathbb{O}^n : \sup_{h \in \mathcal{H}} \big|L_E ({\bf o}_n , h) - L(\mathbb{P} , h)  \big| > \epsilon   \right\} = \bigcup_{h \in \mathcal{H}} \left\{ {\bf o}_n \in \mathbb{O}^n  : \big|L_E ({\bf o}_n , h) - L(\mathbb{P} , h)  \big| > \epsilon \right\} \in \beta(\mathbb{O}^n)
\] e, consequentemente

\[
\mathbb{P}^n \left( {\bf o}_n \in \mathbb{O}^n : \sup_{h \in \mathcal{H}} \big|L_E ({\bf o}_n , h) - L(\mathbb{P} , h)  \big| > \epsilon   \right)
\leq \sum_{h \in \mathcal{H}} \mathbb{P}^n \left({\bf o}_n \in \mathbb{O}^n  : \big|L_E ({\bf o}_n , h) - L(\mathbb{P} , h)  \big| > \epsilon  \right).
\]

Na sequência, vamos mostrar que cada componente da soma na equação acima é suficientemente pequeno para um determinado tamanho do conjunto de dados. Sabemos que

\[
L(\mathbb{P} , h ) = \mathbb{E}_{\mathbb{P}} \left(\ell (\cdot , h)  \right) \quad \text{e} \quad L_E ({\bf o}_n , h) = \frac{1}{n} \sum_{i=1}^n \ell ((x_i , y_i) , h).
\] Desde que ${\bf o}_n$ é uma amostra aleatória simples (iid), concluímos que

\[
\mathbb{E}_{\mathbb{P}} \left[ L_E ({\bf o}_n , h) \right] =   \mathbb{E}_{\mathbb{P}} \left[ \frac{1}{n} \sum_{i=1}^n \ell (\cdot , h) \right] = \mathbb{E}_{\mathbb{P}} \left[ \ell (\cdot , h)  \right] = L(\mathbb{P} , h ) .
\] Portanto, a quantidade $\mid L_E (\mathbb{S} , h) - L(\mathbb{P} , h) \mid$ expressa o desvio da variável aleatória $L_E ({\bf o}_n , h)$ em torno do seu valor esperado $L(\mathbb{P} , h )$. Desde que ${\bf o}_n$ é uma amostra aleatória simples, a lei dos grande números nos garante que a variável aleatória $L_E ({\bf o}_n , h)$ converge em probabilidade para o seu valor esperado $L(\mathbb{P} , h )$, para todo $h \in \mathcal{H}$. Porém, a lei dos grande números não nos fornece uma taxa de convergência. Para isto, vamos utilizar a desigualdade de Hoeffding que quantifica a diferença entre médias empíricas e o seu valor esperado.

Lema 1: Desigualdade de Hoeffding

Considere $(\Omega , \mathcal{F}, \mu)$ um espaço de probabilidade. Seja $Z_1 , Z_2 , \cdots$ uma sequência de variáveis aleatórias iid definidas sobre $\Omega , \mathcal{F}, \mu$ com $\mathbb{E} (Z_i)=\theta$ e $\mu \left(a \leq Z_i \leq b  \right)=1$. Então, para todo $\epsilon > 0$, temos que

\[
\mu \left[ \left| \frac{1}{n} \sum_{i=1}^n Z_i - \theta \right| > \epsilon \right] \leq 2 \exp \left(\frac{-2 n \epsilon^2}{(b-a)^2}\right).
\]

Desde que a função perda $\ell$ é não negativa e limitada por $\bar{a}$ e o conjunto de dados ${\bf o}_n$ é uma amostra aleatória simples, segue da desigualdade de Hoeffding que

\begin{equation} \label{PCUPAC}
\mathbb{P}^n \left( {\bf o}_n \in \mathbb{O}^n :  \big|L_E ({\bf o}_n , h) - L(\mathbb{P} , h)  \big| > \epsilon \right) \leq 2 \exp \left(\frac{-2 n \epsilon^2}{(\bar{a})^2}\right).
\end{equation} A partir destas equações, concluímos que

\[
\mathbb{P}^n \left( {\bf o}_n \in \mathbb{O}^n : \sup_{h \in \mathcal{H}} \big|L_E ({\bf o}_n , h) - L(\mathbb{P} , h)  \big| > \epsilon   \right) \leq \sum_{h \in \mathcal{H}} 2 \exp \left(\frac{-2 n \epsilon^2}{(\bar{a})^2}\right) = 2 Card \left( \mathcal{H} \right)  \exp \left(\frac{-2 n \epsilon^2}{(\bar{a})^2}\right) ,
\] no qual $ Card (\cdot)$ representa a cardinalidade do conjunto. Ao escolhermos,

\[
n \geq \bar{a}^2 \frac{Ln(2 Card (\mathcal{H})/\delta)}{2 \epsilon^2 },
\] obtemos que

\[
\mathbb{P}^n \left( {\bf o}_n \in \mathbb{O}^n : \sup_{h \in \mathcal{H}} \big|L_E ({\bf o}_n , h) - L(\mathbb{P} , h)  \big| > \epsilon   \right) \leq \delta .
\]

Teorema 1: Classes Finitas

Seja $\mathcal{H}$ uma classe finita de preditores admissíveis e $\ell : \mathbb{O} \times \mathcal{H} \rightarrow [0, \bar{a}]$ a função perda. Então, a classe $\mathcal{H}$ satisfaz a propriedade de convergência uniforme com função de complexidade

\[
m_{\mathcal{H}}^{UC} (\epsilon , \delta) \leq \bar{a}^2 \frac{Ln(2 Card (\mathcal{H})/\delta)}{2 \epsilon^2 }.
\] Em particular, temos que a classe $\mathcal{H}$ também satisfaz a propriedade PAC com função de complexidade

\[
m_{\mathcal{H}} (\epsilon , \delta) \leq m_{\mathcal{H}}^{UC} (\epsilon , \delta) \leq \bar{a}^2 \frac{Ln(2 Card (\mathcal{H})/\delta)}{2 \epsilon^2 }.
\]

A partir do Teorema 1, concluímos que o aprendizado PAC depende da cardinalidade da classe de preditores admissíveis $\mathcal{H}$.

Sobre o Portal Action

O Portal Action é mantido pela Estatcamp - Consultoria Estatística e Qualidade, com o objetivo de disponibilizar uma ferramenta estatística em conjunto com uma fonte de informação útil aos profissionais interessados.

Facebook

CONTATO

  •  Maestro Joao Seppe, 900, São Carlos - SP | CEP 13561-180
  • Telefone: (16) 3376-2047
  • E-Mail: [email protected]