Convergência Uniforme

Você está aqui

A ideia da estratégia de aprendizado descrita neste texto é bem simples. Primeiro, restringimos a classe de preditores admissíveis $\mathcal{H} \subset \bar{\mathcal{H}}$ para evitar o sobreajuste. Na sequência, aplicamos o princípio da MRE restrito a subclasse $\mathcal{H}$.  A partir de um conjunto de dados de treinamento ${\bf o}_n \in \mathbb{O}^n$, a ideia do princípio da MRE consiste em avaliarmos o risco empírico de todos os preditores admissíveis $(h \in \mathcal{H})$ e, escolher o preditor $h_E \in \mathcal{H}$ que apresenta o menor risco empírico.

Com o princípio da MRE, esperamos que o preditor $h_E \in \mathcal{H}$  tenha função de risco próxima ao mínimo da função da risco com respeito a classe de preditores admissíveis. Em outras palavras, queremos que a classe de preditores admissíveis $\mathcal{H}$ admita a propriedade PAC com algoritmo de aprendizado $A_E$ dado pelo princípio da MRE. Para isto, devemos assegurar que a função de risco empírico de todos os membros de $\mathcal{H}$ são boas aproximações para a função de risco do respectivo membro.

Conjunto de dados $\epsilon$-representativo: Considere $\epsilon \in (0,1)$. Um conjunto de dados de treinamento ${\bf o}_n \in \mathbb{O}^n$ é denominado $\epsilon$-representativo, com respeito ao espaço de observações $\mathbb{O}$, a classe de preditores admissíveis $\mathcal{H}$, a função perda $\ell$ e a probabilidade $\mathbb{P}$ se,

\[
\sup_{h \in \mathcal{H}} ~ \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h) \big| \leq \epsilon .
\]

Na sequência, mostramos que se um conjunto de dados de treinamento é $\epsilon/2$-representativo, o algoritmo de aprendizado $A_E$ obtido pelo princípio da MRE tem um bom retorno.

Lema 1:  Assumimos que o conjunto de dados de treinamento ${\bf o}_n$ é $\epsilon/2$-representativo. Então, qualquer saída do algoritmo de aprendizado $A_E ({\bf o}_n)$ obtido pelo princípio da MRE satisfaz

\[
L(\mathbb{P} , A_E ({\bf o}_n)) - \inf_{h \in \mathcal{H}} L(\mathbb{P} , h) \leq \epsilon.
\]

Prova: 

Para todo $h \in \mathcal{H}$, temos que

\begin{eqnarray*}
L(\mathbb{P} , A_E ({\bf o}_n)) &\leq& L_E ({\bf o}_n , A_E ({\bf o}_n)) + \frac{\epsilon}{2} \leq L_E ({\bf o}_n , h) + \frac{\epsilon}{2} 
\leq L(\mathbb{P} , h) + \frac{\epsilon}{2} + \frac{\epsilon}{2} = L(\mathbb{P} , h) + \epsilon ,
\end{eqnarray*} nos quais a primeira e a terceira desigualdade são consequências da definição de de conjunto de dados $\epsilon$-representativo e a segunda desigualdade é consequência do princípio da MRE.

O lema 1 nos diz que um algoritmo $A_E$ dado pelo princípio da MRE é um aprendizado PAC se, com probabilidade pelo menos $1- \delta$, podemos escolher um conjunto de dados $\epsilon$-representativo. A seguinte condição de convergência uniforme formaliza este requerimento.


Definição de Convergência Uniforme:  Dizemos que uma classe de preditores admissíveis $\mathcal{H} \subset \bar{\mathcal{H}}$ tem a propriedade de convergência uniforme se, existe uma função $m_{\mathcal{H}}^{UC} : (0,1)^2 \rightarrow \mathbb{N}$ tal que:

\[
\sup_{\mathbb{P} \in \mathcal{P}(\mathbb{O})} ~\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 \right] \geq 1- \delta , \quad n \geq m_{\mathcal{H}}^{UC}(\epsilon , \delta),
\] para todo $\epsilon , \delta \in (0,1)$.

O termo uniforme se refere ao fato de que a função de complexidade $m_{\mathcal{H}}^{UC}$ define um tamanho de amostra independente do preditor admissível $(h \in \mathcal{H})$ e da probabilidade $\mathbb{P} \in \mathcal{P}(\mathbb{O})$. Similar a definição da complexidade para um aprendizado PAC $(m_{\mathcal{H}})$, a função $m_{\mathcal{H}}^{UC}$ estabelece a menor complexidade de uma amostra para obtermos a convergência uniforme. Neste caso, definimos o tamanho mínimo do conjunto de dados ($m_{\mathcal{H}}^{UC}$) que garante com probabilidade pelo menos $1-\delta$ que o conjunto de dados de treinamento será $\epsilon$-representativo. Dados $\epsilon , \delta \in (0,1)$ e $n \geq m_{\mathcal{H}}^{UC} (\epsilon , \delta)$, a propriedade da convergência uniforme nos diz 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 \right] \geq 1- \delta,
\] para todo probabilidade $\mathbb{P} \in \mathcal{P}(\mathbb{O})$.  Como consequência do lema 1, 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| \leq \frac{\epsilon}{2} \right\} \subset \left\{ {\bf o}_n \in \mathbb{O}^n: L(\mathbb{P} , h_E({\bf o}_n)) - \inf_{h \in \mathcal{H}} L(\mathbb{P} , h) \leq \epsilon \right\}
\]  Assim, derivamos o seguinte Teorema.

Teorema 1: Se uma classe $\mathcal{H}$ tem a propriedade de convergência uniforme com função de complexidade $m_{\mathcal{H}}^{UC}$, então esta classe também tem a propriedade de aprendizado PAC com $m_{\mathcal{H}} (\epsilon , \delta) \leq m_{\mathcal{H}}^{UC} (\epsilon/2 , \delta)$. Além disso, o princípio da MRE nos fornece um algoritmo de aprendizado PAC com a classe $\mathcal{H}$.

Prova: 

Como consequência da propriedade de convergência uniforme, temos que

\[
        \mathbb{P}^n \left\{ {\bf o}_n \in \mathbb{O}^n: L(\mathbb{P} , h_E({\bf o}_n)) - \inf_{h \in \mathcal{H}} L(\mathbb{P} , h) \leq \epsilon \right\}
        \geq \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 \frac{\epsilon}{2} \right\}
        \geq 1-\delta,
   \]
para todo $n \geq m_{\mathcal{H}}^{UC} (\frac{\epsilon}{2} , \delta)$.

A partir do Teorema 1 concluímos que a propriedade de convergência uniforme é suficiente para mostrarmos que uma determinada classe $\mathcal{H}$ de preditores admissíveis tenha a propriedade PAC.  Ao tomarmos o complementar em relação a propriedade de convergência uniforme, obtemos que

\begin{equation}
\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| \geq \epsilon \right] \leq \delta.
\end{equation}

Pelo teorema de extensão de Kolmogorov, sabemos que existe uma única probabilidade $\mathbb{P}^\infty$ definida sobre $(\mathbb{O}^\infty , \beta (\mathbb{O}^\infty))$ tal que a projeção em $(\mathbb{O}^n , \beta (\mathbb{O}^n))$ coincide com $\mathbb{P}^n$, para todo $n \geq 1$. Com isso, obtemos que

\[
\sup_{\mathbb{P}^\infty \in \mathcal{P}(\mathbb{O}^\infty)} \mathbb{P}^\infty \left[ {\bf o} \in \mathbb{O}^\infty : \sup_{h \in \mathcal{H}} \big| L_E (\pi_n ({\bf o}) , h) - L(\mathbb{P} , h) \big| \geq \epsilon \right] \leq \delta, \quad n \geq m_{\mathcal{H}}^{UC} (\epsilon , \delta),
\] no qual $\pi_n : \mathbb{O}^\infty \rightarrow \mathbb{O}^n$ denota a projeção coordenada para todo $n \geq 1$.  Como consequência, obtemos que $L_E (\pi_n ({\bf o}) , h)$ converge uniformemente em probabilidade para $L(\mathbb{P} , 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]