Algoritmo de Aprendizado PAC

Você está aqui

Acabamos de mostrar que o princípio da MRE pode nos levar ao problema de sobreajuste. Apesar deste problema, a ideia não é abandonarmos este princípio, mas propormos formas de resolver o problema do sobreajuste. A partir desta seção, vamos propor condições para que o princípio da MRE não nos leve ao sobreajuste. Neste sentido, queremos condições para que se um preditor tenha boa performance para o risco empírico, então este preditor também tenha boa performance para função de risco com probabilidade arbitrária $\mathbb{P} \in \mathcal{P}(\mathbb{O})$.

Uma solução comum consiste em restringirmos a classe de preditores admissíveis $\mathcal{H}$ para aplicarmos o princípio da MRE. Formalmente, escolhemos uma classe apropriada de preditores $\mathcal{H}$ que depende do processo e das características que estudamos. Dado uma classe de preditores admissíveis $\mathcal{H} \subset \bar{\mathcal{H}}$ e um conjunto de dados de treinamento ${\bf o}_n \in \mathbb{O}^n$, queremos um preditor $h_E({\bf o}_n)$ que minimiza a função de risco empírica restrita a classe $\mathcal{H}$,

\begin{equation}
L_E ({\bf o}_n , h_E({\bf o}_n)) = \inf_{h \in \mathcal{H}} L_E ({\bf o}_n , h), \quad n \geq 1.
\end{equation}

 Observe que o preditor $h_E({\bf o}_n , \cdot)$ que minimiza a função de risco empírica não depende da probabilidade $\mathbb{P}$, ele depende do conjunto de dados de treinamento ${\bf o}_n \in \mathbb{O}^n$  e da classe de controles admissíveis $\mathcal{H}$. O algoritmo de aprendizado definido pelo princípio da MRE é denotado por $A_E$. Neste caso, temos que $A_E({\bf o}_n) = h_E({\bf o}_n , \cdot)$.

Ao restringirmos a classe de preditores admissíveis, introduzimos um vício ao princípio da MRE, que é denominado vício indutivo. Com isso, uma questão fundamental à teoria de aprendizado de máquina consiste em escolher a classe de preditores admissíveis $\mathcal{H}$ no qual o princípio da MRE não nos leva a um problema de sobreajuste. Intuitivamente, quando mais restrita for a classe de preditores admissíveis menor a possibilidade de sobreajuste, porém maior o vício indutivo.

Obviamente que a questão de existência de um preditor que minimiza a função de risco empírica deve ser avaliada. Suponha que a função de perda $\ell: \mathbb{O} \times \mathcal{H} \rightarrow [0,\bar{a}]$ seja semicontínua inferior e $\mathcal{H}$ seja um espaço compacto separável. Então, temos que $L_E: \mathbb{O}^n \times \mathcal{H} \rightarrow [0,\bar{a}]$ também é uma função semicontínua. Assim, segue do teorema de seleção Borel mensurável que existe uma função $h_E : \mathbb{O}^n \rightarrow \mathcal{H}$ que é Borel mensurável e satisfaz o princípio da minimização do risco empírico.

No caso do problema de classificação, provamos que o preditor de Bayes apresenta o menor risco na classe de todos os preditores possíveis $(\bar{\mathcal{H}})$. Porém, o fato de desconhecermos a probabilidade $\mathbb{P}$ inviabiliza a aplicação do preditor de Bayes. Para contornarmos esta situação, vamos relaxar a hipótese de que o preditor proposto pelo algoritmo de aprendizado minimize a função de risco. Neste sentido, queremos que nosso algoritmo de aprendizado encontre um preditor admissível cuja função de risco não seja muito maior que a função de risco de algum preditor referência, como o preditor de Bayes. A diferença máxima de performance corresponde ao parâmetro de vício do algoritmo de aprendizado.

Para continuarmos com esta seção, vamos fazer uma hipótese sobre a geração dos dados. Admitimos que as amostras são retiradas de forma independente e identicamente distribuídas (iid) a partir da probabilidade $\mathbb{P}$. Assim, para um conjunto de dados de tamanho $n\geq 1$, a probabilidade conjunta  é determinada pela probabilidade produto e denotada por $\mathbb{P}^n$.

Seja $A: \mathbb{O}^n \rightarrow \mathcal{H}$ um algoritmo de aprendizado e $\mathbb{P} \in \mathcal{P}(\mathbb{O})$. Desde que a função de risco $L(\mathbb{P} , A({\bf o}_n))$ depende do conjunto de dados de treinamento ${\bf o}_n$ e este conjunto de dados é uma amostra aleatória simples (iid) da probabilidade $\mathbb{P}$, concluímos que o preditor $A({\bf o}_n)$ é um elemento aleatório e, consequentemente, a função de risco $L(\mathbb{P} , A({\bf o}_n))$ é uma variável aleatória. Interpretamos a variável aleatória $L(\mathbb{P} , A({\bf o}_n))$ como a esperança condicional

\[
L(\mathbb{P} , A({\bf o}_n)) = \mathbb{E}_{\mathbb{P}^n} \left[ \mathbb{E}_{\mathbb{P}} \left( \ell (\cdot . A({\bf o}_n))  \right) \mid {\bf o}_n \right] = \int_{\mathbb{O}} \ell (o , A({\bf o}_n)) \mathbb{P} (do), \quad {\bf o}_n \in \mathbb{O}^n.
\]

Do ponto de vista probabilístico não temos certeza de que o conjunto de dados de treinamento ${\bf o}_n$ é representativo da probabilidade $\mathbb{P}$. Se voltarmos ao exemplo do rendimento do processo, temos (mesmo que pequena) a possibilidade de que todas as observações selecionadas resultem em rendimento acima de $90\%$ (sucesso). Neste caso, o princípio da MRE nos leva a um preditor constante no qual todos os rendimentos são "sucesso''. Como consequência, precisamos administrar a probabilidade de obtermos uma amostra que não seja representativa.

Para isto, propomos que a probabilidade de selecionarmos um conjunto de dados de treinamento ${\bf o}_n$ para o qual $L(\mathbb{P} , A({\bf o}_n))$ não é muito grande seja controlada. Em geral, denotamos por $\delta$ a probabilidade de obtermos uma amostra não representativa e, por $(1-\delta)$ o parâmetro de confiança. Por outro lado, não necessariamente atingimos a performance do preditor referência, pois não conhecemos a probabilidade $\mathbb{P} \in \mathcal{P}(\mathbb{O})$. Assim, introduzimos um parâmetro de vício $\epsilon \in (0,1)$, que corresponde a diferença máxima de performance entre o preditor proposto e o preditor referência. Para isto, admitimos que $(\mathcal{H} , \beta(\mathcal{H}))$ seja um espaço de Borel e que o algoritmo de aprendizado $A: \mathbb{O}^n \rightarrow \mathcal{H}$ seja uma função Borel mensurável para todo $n \geq 1$. Assim, temos que $L(\mathbb{P}, A(\cdot)): \mathbb{O} \rightarrow [0,\bar{a}]$ é uma variável aleatória.

Aprendizado PAC: Uma classe de preditores $\mathcal{H}$ tem a propriedade PAC (Provavelmente Aproximadamente Correto) se existe uma função $m_{\mathcal{H}} : (0,1)^2 \rightarrow \mathbb{N}$ e um algoritmo de aprendizado $A$ com a seguinte propriedade: Para todo $\epsilon , \delta \in (0,1)$ e toda a probabilidade $\mathbb{P} \in \mathcal{P}(\mathbb{O})$, o algoritmo de aprendizado $A$ retorna um preditor tal que,

\[
\mathbb{P}^n \left[ {\bf o}_n \in \mathbb{O}^n :  L(\mathbb{P} , A({\bf o}_n)) \leq \inf_{h \in \mathcal{H}} L(\mathbb{P} , h) + \epsilon \right] \geq 1- \delta , \quad \forall ~ n \geq m_{\mathcal{H}}(\epsilon , \delta).
\]

Dizemos que $1-\delta \in(0,1)$ corresponde ao parâmetro de confiança da previsão, enquanto que $\epsilon$ corresponde ao parâmetro de vício. A função $m_{\mathcal{H}}$ é denominada complexidade PAC da classe de preditores admissíveis $\mathcal{H}$.

Com a definição de aprendizado PAC, o preditor proposto pelo algoritmo de aprendizado é ótimo se o seu risco não é  "muito'' maior que o menor risco entre todos os preditores admissíveis em $\mathcal{H} \subset \bar{\mathcal{H}}$. Também exigimos que o preditor seja admissível $(h \in \mathcal{H})$, o que nos leva ao conceito de aprendizado próprio.

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]