Classificação Binária

Você está aqui

Na seção Classe de Preditores Finitos, mostramos que qualquer classe de preditores admissíveis finita é um aprendizado PAC. Todavia, muitas classes interessantes não são finitas. No caso de classes de preditores finitas, a complexidade do aprendizado PAC é determinada pela cardinalidade (complexidade) da classe. Então, para ampliar nossa classe de preditores admissíveis, precisamos encontrar uma forma melhor de medir a complexidade de uma classe de funções. Para isto, vamos introduzir a complexidade de Rademacher e então, utilizá-la para deduzir a dimensão de Vapnik–Chervonenkis (VC) aplicada ao problema de classificação binária. De forma geral, a medida de complexidade da classe de preditores admissíveis defini quantas rotulagens diferentes podemos produzir para uma amostra finita. A partir da dimensão VC, vamos estabelecer condições necessárias e suficientes para o aprendizado PAC. Neste capítulo, vamos tratar a questão do aprendizado PAC no contexto de classificadores binários.

Dado $\mathbb{O}=\chi \times \mathcal{Y}$ o espaço de observações no qual $\chi$ é um espaço de Borel e $\mathcal{Y}=\{0,1\}$. Para toda probabilidade $\mathbb{P}$ sobre o espaço de Borel $\mathbb{O}$, existe um par $(\mathbb{P}_{\chi}, \nu)$ no qual $\mathbb{P}_{\chi}$ é uma probabilidade sobre $(\chi , \beta(\chi))$ e $\nu$ é uma probabilidade de transição de $\chi$ para $\mathcal{Y}$ denominada  "distribuição a posteriori". Relacionado com a probabilidade $\mathbb{P}$ sobre $(\mathbb{O} , \beta(\mathbb{O}))$, existe $(X,Y)$ um par de elementos aleatórios a valores em $\mathbb{O}$ e com distribuição dada por $\mathbb{P}$. Qualquer função $h:\chi \rightarrow \{0,1\}$ Borel mensurável é denominada preditor ou classificador. O risco associado ao preditor $h$ é dado pela probabilidade de erro de classificação,

\begin{eqnarray*}
L(\mathbb{P} , h) &=& \mathbb{E}_{\mathbb{P}} \left[ 1\!\!1_{ \{ Y \neq  h(X) \}} \right] = \mathbb{P} \left[  Y \neq  h(X) \right] \\  &=& \int_{\chi} \left(  1\!\!1_{ \{ h(x)=1 \} } \nu (\{0\}  \mid x ) + 1\!\!1_{ \{ h(x)=0 \} } \nu (\{1\}  \mid x ) \right) \mathbb{P}_{\chi} (dx) \\
&=&\int_{\{h(x) =1\}} \nu (\{0\}  \mid x ) \mathbb{P}_{\chi} (dx)  +  \int_{\{h(x) =0\}} \nu (\{1\}  \mid x ) \mathbb{P}_{\chi} (dx) .
\end{eqnarray*} Sabemos que  o mínimo de $L(\mathbb{P}, \cdot)$ é dado pelo classificador de Bayes

\[
\Phi(\mathbb{P}) = h^{\star}(X) =  \left\{
  \begin{array}{ll}
    1, & \hbox{se} ~  ~  \mathbb{E}_{\mathbb{P}} (Y \mid X) = \nu(\{1\} \mid X) \geq \frac{1}{2}, \\ \\
    0, & \hbox{se} ~  ~  \mathbb{E}_{\mathbb{P}} (Y \mid X) = \nu(\{1\} \mid X) < \frac{1}{2}.
  \end{array}
\right.
\] A seguir, vamos mostrar que o classificador de Bayes minimiza a função de risco esperada.

Lema 1: Classificador de Bayes

Para qualquer preditor possível $h \in \bar{\mathcal{H}}$, temos que 

\[
\mathbb{P} \left[Y \neq h^\star (X) \right] \leq \mathbb{P} \left[Y \neq h(X) \right].
\] 

Prova: 

Dado $X=x$, o erro condicional de classificação de um preditor qualquer $h$ é dado por 

\[
\mathbb{P} \left[Y \neq h(X) \mid X=x  \right] = 1 - \mathbb{P} \left[Y = h(X) \mid X=x  \right] = \] \[1- \left(  \mathbb{P} \left[Y=1, h(X)=1 \mid X=x  \right] + \mathbb{P} \left[Y=0, h(X)=0 \mid X=x  \right] \right) = \] \[  1- \left(   1\!\!1_{\{h(x)=1 \}} \mathbb{P}\left[Y=1 \mid X=x  \right] + 1\!\!1_{\{h(x)=0 \}} \mathbb{P} \left[Y=0 \mid X=x  \right] \right) \] \[= 1- \left(   1\!\!1_{\{h(x)=1 \}} \nu\left[\{1\} \mid x  \right] + 1\!\!1_{\{h(x)=0 \}} \nu\left[\{0\} \mid x  \right] \right).
\] Assim, para todo $x \in \chi$, temos que \[ \mathbb{P} \left[Y \neq h (X) \mid X=x  \right] - \mathbb{P} \left[Y \neq h^\star(X) \mid X=x  \right] = \]  \[\left(  1\!\!1_{\{h^\star(x)=1 \}}-  1\!\!1_{\{h(x)=1 \}} \right) \nu\left[\{1\} \mid x  \right] + \left(1\!\!1_{\{h^\star (x)=0 \}} - 1\!\!1_{\{h(x)=0 \}}\right) \nu\left[\{0\} \mid x  \right] = \] \[
\left(  1\!\!1_{\{h^\star(x)=1 \}}-  1\!\!1_{\{h(x)=1 \}} \right) \nu\left[\{1\} \mid x  \right] + \left(1\!\!1_{\{h^\star (x)=0 \}} - 1\!\!1_{\{h(x)=0 \}}\right) \left(1-\nu\left[\{1\} \mid x  \right] \right) = \] \[ \left(  1\!\!1_{\{h^\star(x)=1 \}}-  1\!\!1_{\{h(x)=1 \}} \right) \nu\left[\{1\} \mid x  \right] - \left(1\!\!1_{\{h^\star (x)=1 \}} - 1\!\!1_{\{h(x)=1 \}}\right) \left(1-\nu\left[\{1\} \mid x  \right] \right) = \] \[
\left(2\nu\left[\{1\} \mid x  \right] -1 \right) \left(  1\!\!1_{\{h^\star(x)=1 \}}-  1\!\!1_{\{h(x)=1 \}} \right) \geq 0,
\] como consequência da definição do preditor de Bayes $h^\star$. Ao integrarmos em relação a $\mathbb{P}_{\chi}$ concluímos o lema.

Como consequência do lema 1, temos que

\[
L(\mathbb{P} , h) = 1- \mathbb{E}_{\mathbb{P}_\chi} \left[ 1\!\!1_{ \{ h(X)=1 \}} \nu\left[\{1\} \mid X  \right] + 1\!\!1_{ \{ h(X)=0 \}}  \nu\left[\{0\} \mid X  \right]   \right].
\]
Em particular, para o preditor de Bayes, o risco esperado é dado por

\[
L(\mathbb{P} , h^\star) = 1- \mathbb{E}_{\mathbb{P}_\chi} \left[ 1\!\!1_{ \{ \nu\left[\{1\} \mid X  \right] \geq \frac{1}{2} \}} \nu\left[\{1\} \mid X  \right] + 1\!\!1_{ \{ \nu\left[\{1\} \mid X  \right] < \frac{1}{2} \}}  \nu\left[\{0\} \mid X  \right]   \right].
\] Além disso,  obtemos que 

\[
L(\mathbb{P} , h)  - L(\mathbb{P} , h^\star) = \int_{\chi}  1\!\!1_{\{h^\star(x) \neq h(x) \}} \mid 2\nu\left[\{1\} \mid x  \right] -1  \mid \mathbb{P}_\chi (dx).
\] 

Sabemos que se a classe $\mathcal{H}$ é finita, então esta classe admite uma estratégia de aprendizado PAC baseado no princípio da minimização do risco empírico ( ver seção Classe de preditores Finitos). A seguir, vamos ilustrar através de um exemplo, que este resultado pode ser estendido para classes infinitas. Considere o problema classificação binária, no qual tomamos $\mathcal{H}$ a classe de funções $h_a: \mathbb{R} \rightarrow \{0,1\}$ tal que $h_a = 1\!\!1_{\{x<a\}}$ para $a \in \mathbb{R}$. Obviamente, a classe de preditores admissíveis $\mathcal{H}$ é infinita. Suponha que existe uma função $h^\star (x) = 1\!\!1_{\{x < a^\star \}} \in \mathcal{H}$ que corresponde  à ``verdadeira''  função  geradora de rótulos. Assim, para cada $x \in \chi$ existe um único rótulo $y=h^\star(x)$.  Todo problema de classificação que satisfaz esta propriedade é denominado realizável. Para um problema de classificação binária realizável, mostramos no lema 2 que a classe $\mathcal{H}$ de preditores admissíveis é um aprendizado PAC com algoritmo obtido do princípio da MRE.

Lema 2: Classe de Preditores com valor de corte (threshold)

Considere o problema de classificação binária realizável com classe de preditores admissíveis $\mathcal{H}=\{1\!\!1_{\{x<a\}} : a \in \mathbb{R} \}$. Então, a classe $\mathcal{H}$ é um aprendizado PAC com algoritmo obtido pelo princípio da MRE e complexidade amostral

\[
m_{\mathcal{H}} (\epsilon , \delta) \leq \frac{Ln(2/\delta)}{\epsilon}, \quad (\epsilon , \delta) \in (0,1)^2.
\]

Prova: 

Seja $a^\star$ o limitante tal que o preditor $h^\star (x) = 1\!\!1_{\{x < a^\star \}}$ satisfaça $L(\mathbb{P},h^\star) =0$. Denotamos por $\mathbb{P}_{\chi}$ a distribuição marginal sobre $(\chi, \beta(\chi))$ e tomamos $a_0 < a^\star < a_1$ tal que

\[
\mathbb{P}_{\chi} \left( X \in (a_0 , a^\star)  \right) = \mathbb{P}_{\chi} \left( X \in (a^\star , a_1)  \right) = \epsilon .
\] Se $\mathbb{P}_{\chi} \left( X \in (-\infty , a^\star)  \right) \leq \epsilon$ tomamos $a_0 = - \infty$ e de forma similar para $a_1$. Dado um conjunto de dados de treinamento ${\bf o}_n \in \mathbb{O}^n$, tomamos

\[
b_0 ({\bf o}_n)= \max \{x: (x,1) \in {\bf o}_n \} \quad \text{e} \quad b_1 ({\bf o}_n)= \min \{x: (x,0) \in {\bf o}_n \}.
\] Se nenhum dado em ${\bf o}_n$ assume rótulo $1 ~ (0)$ tomamos $b_0 ({\bf o}_n)=-\infty ~ (b_1 ({\bf o}_n) = \infty)$. Seja $b_E ({\bf o}_n )$ o correspondente limitante obtido pelo princípio da MRE a partir do conjunto de dados ${\bf o}_n \in \mathbb{O}^n $, no qual

\[
h_E ({\bf o}_n , x) = 1\!\!1_{\{ x < b_E ({\bf o}_n ) \}}, ~~ x \in \mathbb{R} \quad \text{e} \quad b_0 ({\bf o}_n )< b_E ({\bf o}_n ) < b_1({\bf o}_n ).
\] Assim, uma condição suficiente para que $L(\mathbb{P}, h_E) \leq \epsilon$ é que $b_0 ({\bf o}_n) \geq a_0$ e $b_1 ({\bf o}_n) \leq a_1$. Com isso, obtemos que

\[
\mathbb{P}^n \left[ {\bf o}_n \in \mathbb{O}^n : L\left(\mathbb{P} , h_E ({\bf o}_n) \right) > \epsilon  \right] \leq 
\]

\[
\mathbb{P}^n \left[ \{ {\bf o}_n \in \mathbb{O}^n: b_0 ({\bf o}_n) < a_0\} \cup \{ {\bf o}_n \in \mathbb{O}^n: b_1 ({\bf o}_n) > a_1\}  \right] \\ \label{efdn11}
\leq
\]

\[
\mathbb{P}^n \left[ \{ {\bf o}_n \in \mathbb{O}^n: b_0 ({\bf o}_n) < a_0\} \right] + \mathbb{P}^n \left[  \{ {\bf o}_n \in \mathbb{O}^n: b_1 ({\bf o}_n) > a_1\}  \right].
\]

O evento $\{ {\bf o}_n \in \mathbb{O}^n: b_0 ({\bf o}_n) < a_0\}$ ocorre se, e só se, todas as observações do conjunto de dados ${\bf o}_n$ não estão no intervalo $(a_0 , a^\star)$. Desta forma, temos que

\begin{equation} \label{efdn12}
\mathbb{P}^n \left[ \{ {\bf o}_n \in \mathbb{O}^n: b_0 ({\bf o}_n) < a_0\} \right] = \mathbb{P}^n \left[{\bf o}_n \in \mathbb{O}^n : x_i \not \in (a_0,a^\star)  \right] = (1-\epsilon)^n \leq \exp^{-\epsilon n} .
\end{equation} Como consequência das equações acima, concluímos que

\[
\mathbb{P}^n \left[ {\bf o}_n \in \mathbb{O}^n : L\left(\mathbb{P} , h_E ({\bf o}_n) \right) > \epsilon  \right] \leq \exp^{-\epsilon n} + \exp^{-\epsilon n} = 2 \exp^{-\epsilon n}.
\] Ao tomarmos $n > \frac{Ln(2/\delta)}{\epsilon}$, obtemos que

\[
\mathbb{P}^n \left[ {\bf o}_n \in \mathbb{O}^n : L\left(\mathbb{P} , h_E ({\bf o}_n) \right) > \epsilon  \right] < \delta.
\] Segue o lema.

Com este lema, mostramos que a propriedade de aprendizado PAC não está restrita a classes finitas de preditores admissíves. Neste módulo, vamos estabelecer condições necessárias e suficientes para que uma classe de preditores admissíveis $\mathcal{H}$ seja PAC para um problema de classificação binária.

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]