Dimensão de Vapnik e Chervonenkis

Você está aqui

No problema de classificação binária avaliado na seção Complexidade de Rademacher, toda função $f \in \mathcal{W}$ é a indicadora de algum conjunto na forma $\{ (x,y) \in \mathbb{O}: y \neq h(x)\}$ com $h\in \mathcal{H}$. A projeção da classe $\mathcal{W}$ no ponto ${\bf o}_n$ é dada por

\[
\mathcal{W} ({\bf o}_n )= \{(1\!\!1_{\{y_1 \neq h(x_1) \}} , \cdots , 1\!\!1_{\{y_n \neq h(x_n)\}} ) : h \in \mathcal{H}\}.
\] A partir da desigualdade de Massart, obtemos que

\[
 \hat{\mathcal{R}}_n (\mathcal{W} ({\bf o}_n ) ) = \mathbb{E}_{\sigma} \sup_{a \in \mathcal{W} ({\bf o}_n )} \frac{1}{n} \sum_{i=1}^n \sigma_i a_i \leq \sqrt{ \frac{2 \ln (Card(\mathcal{W} ({\bf o}_n )))}{n}}, ~ {\bf o}_n \in \mathbb{O}^n,
\] pois $r \leq \sqrt{n}$. Portanto, precisamos estudar a Cardinalidade do conjunto $\mathcal{W} ({\bf o}_n )$.  Agora, o conjunto $\mathcal{W} ({\bf o}_n )$ depende da função de risco $\ell$, da entrada do processo $X$ e da saída $Y$. No caso de classificação binária, no qual utilizamos como função de risco a probabilidade de erro de classificação, temos a seguinte simplificação 

\[ \hat{\mathcal{R}}_n (\mathcal{W} ({\bf o}_n ) ) = \hat{\mathcal{R}}_n ( {\bf o}_n , \mathcal{H} ) = \mathbb{E}_{\mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n}  \sum_{i=1}^n \sigma_i \ell (o_i  , h) )   = \]  \[ \mathbb{E}_{\mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n}  \sum_{i=1}^n \sigma_i 1\!\!1_{ \{ y_i \neq h(x_i)\}} = \mathbb{E}_{\mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n}  \sum_{i=1}^n \sigma_i \mid y_i - h(x_i) \mid =  \] \[ \mathbb{E}_{\mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n}  \sum_{i=1}^n \sigma_i \mid h(x_i) - y_i\mid = \mathbb{E}_{\mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n}  \sum_{i=1}^n \sigma_i  \left( h(x_i) (1-2y_i) + y_i \right) = \]  \[  \mathbb{E}_{\mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n}  \sum_{i=1}^n \sigma_i  h(x_i)) , \] para todo $ {\bf o}_n = (o_1, \cdots , o_n)\in \mathbb{O}^n$, pois sabemos que $\mid a - b \mid = a(1-2b) + b $ para todo $a,b \in \{0,1\}$, $(1-2y_i)\sigma_i$ também tem distribuição de Rademacher e $\sigma_i y_i$ tem valor esperado nulo. Com isto, mostramos que a complexidade de Rademacher depende apenas da entrada do processo ${\bf x}_n=(x_1, \cdots , x_n)$ composta com o preditor admissível $h$ . 

Todo preditor $h \in \mathcal{H}$ pode ser interpretado como um subconjunto do espaço domínio $\chi$. Na realidade, ao tomarmos $B= \{x \in \chi: h(x) = 1  \} = h^{-1} (\{1\})$, concluímos que $h = 1\!\!1_{ B }$. Para todo elemento ${\bf x}_n= (x_1, \cdots x_n)\in \chi^n$, denotamos por $\mathcal{H} ({\bf x}_n)$ a projeção de $\mathcal{H}$ sobre ${\bf x}_n$ na forma, $$\mathcal{H} ({\bf x}_n):=\{ \{h(x_1), \cdots , h(x_n)\}, h \in \mathcal{H} \} \quad \text{e} \quad \hat{\mathcal{R}}_n (\mathcal{H} ({\bf x}_n) ) := \mathbb{E}_{\sigma} \sup_{a \in \mathcal{H} ({\bf x}_n)} \frac{1}{n} \sum_{i=1}^n \sigma_i a_i.$$  Assim, ao aplicarmos a desigualdade Massart, concluímos que 

\[ \hat{\mathcal{R}}_n (\mathcal{W} ({\bf o}_n ) ) = \hat{\mathcal{R}}_n (\mathcal{H} ({\bf x}_n) ) \leq \sqrt{ \frac{2 \ln (Card(\mathcal{H} ({\bf x}_n)))}{n}}, ~ {\bf o}_n \in \mathbb{O}^n, ~ ~ (\text{Desigualdade 1}) \]

Desta forma, a partir da desigualdade 14 na seção "Complexidade de Rademacher" e da desgualdade 1, obtemos que 

\[
 \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big| \leq  2 \sqrt{ \frac{2 \ln (Card(\mathcal{H} ({\bf x}_n )))}{n}} + 3
    \sqrt{\frac{\ln (2/ \delta)}{2n}}, ~ {\bf o}_n \in \hat{G}, ~ ~ (\text{Desigualdade 2}).
\] Com a complexidade de Rademacher, resumimos o problema de aprendizado PAC na questão de avaliar a como a dimensão da classe de preditores composta com os dados de entrada aumenta em função do tamanh da amostra. Dizemos que o subconjunto ${\bf x}_n =\{x_1, \cdots , x_n\} \subset \chi$ é particionado por $\mathcal{H}$ se a cardinalidade de $\mathcal{H} ({\bf x}_n)$ for igual a $2^{n}$. Nesta condição, temos que $\mathcal{H} ({\bf x}_n) = \{0,1\}^n$. Obviamente que se ${\bf x}_n$ é particionado por $\mathcal{H}$, então qualquer subconjunto de ${\bf x}_n$ também é particionado.

Definição 1: Dimensão de Vapnik e Chervonenkis
Seja $\mathcal{H}$ uma classe de preditores admissíveis. A VC-dim da classe $\mathcal{H}$ de preditores admissíveis é dada por
$$VC-dim (\mathcal{H}) = max \{n : {\bf x}_n ~ \text{é particionado por} ~ \mathcal{H}, ~ \text{para todo} ~ {\bf x}_n \subset \chi^n\}.$$

Para ilustrar, calculamos a dimensão de Vapnik–Chervonenkis para algumas classes usuais de preditores admissíveis.

Exemplo 1:

Seja $\mathcal{H}:=\{h_\theta\}_{\theta \in \mathbb{R}}$ o conjunto de  preditores $h_\theta:\mathbb{R}\rightarrow \{0,1\}$ definido por
$$h_\theta(z)=\left\{\begin{array}{lc}
        1, &  \text{se } z\geq \theta \\
        0, & \text{se } z< \theta
      \end{array}\right.
$$ para $\theta \in \mathbb{R}$. Então, $VC-dim(\mathcal{H}) = 1$, pois para qualquer conjunto $(x_1,x_2)$, com $x_1<x_2$ não existe $\theta\in \mathbb{R}$ tal que $h_\theta(x_1)=1$ e $h_\theta(x_2)=0$. Todavia, dado $x \in \mathbb{R}$ existe $\theta\in \mathbb{R}$ tal que $h_{\theta}(x)=1$ e existe $\eta \in \mathbb{R}$ tal que $h_{\eta}(x)=0$.

Exemplo 2:

Seja $\mathcal{H}=\{h_0\}$ um classificador $h_0:\mathbb{R}\rightarrow \{0,1\}$ definido por
$$h_0(z)=\left\{\begin{array}{lc}
        1, &  \text{se } z\geq 0 \\
        0, & \text{se } z< 0
      \end{array}\right.
$$
Então, $VC-dim(\mathcal{H})=0$,  pois $h_0$ não particiona nenhum conjunto unitário $\{x\}$, pois ele sempre induz o mesmo rótulo ($1$, se $x\geq 0$, e $0$, se $x <0$), nunca ambos. Por isso, $VC-dim(h_0) < 1$. Por outro lado, o conjunto vazio, é particionado por $h_0$.

A função de crescimento de uma classe $\mathcal{H}$ de preditores admissíveis, denotada por $\tau_{\mathcal{H}}:\mathcal{N}\rightarrow \mathcal{N}$, é definida como
$$\tau_\mathcal{H}(n)=\max_{{\bf x}_n \in \chi^n }  Card(\mathcal{H} ({\bf x}_n)).$$
Em outras palavras, $\tau_\mathcal{H}(n)$ é o número máximo de preditores admissíveis distintos que podem ser obtidos ao projetarmos classe $\mathcal{H}$ em conjuntos de dados de tamanho $n$. Note que, se $VC-dim(\mathcal{H}) = d$, então para qualquer $n\leq d,$ temos $\tau_{\mathcal{H}}(n)=2^n$.  A seguir, enunciamos o Lema de Vapnik - Chervonenkis - Sauer - Shelah.

Lema 1: Lema de Vapnik - Chervonenkis - Sauer - Shelah

Seja $\mathcal{H}$ uma classe de preditores com $VC-dim(\mathcal{H})=d<\infty$. Então para todo $n$, $\tau_\mathcal{H}(n)\leq \sum_{i=0}^d\binom{n}{i} = (n+1)^d$. Em particular, se $n>d$ então $\tau_{\mathcal{H}}(n)\leq \left(\frac{en}{d}\right)^d$

Prova:

Para $n\leq d$, segue trivialmente que $\tau_\mathcal{H}(n)\leq \sum_{i=0}^d\binom{n}{i}$ uma vez que, neste caso $\sum_{i=0}^d\binom{n}{i}=2^n$. Com $n> d$ e o conjunto $S=\{x_1,\dots,x_n\}\subset \chi$ fixo, definimos
$$\mathcal{B}=\left\{\{x_i\in S:f(x_i)=1\}, ~i=1, \cdots n :f\in \mathcal{H}\right\}.$$
Assim, temos que $Card(\mathcal{B})\leq \sum_{i=0}^d\binom{n}{i}$, uma vez que $VC-dim(\mathcal{H})=d$. Agora, como $S$ é arbitrário, temos que 

\[
\tau_\mathcal{H}(n) \leq Card(\mathcal{B})\leq \sum_{i=0}^d\binom{n}{i} .
\] Agora, note que para $0\leq i\leq d$ e $n\geq d$, temos que
$$\frac{(n/d)^d}{(d/n)^i}\geq 1$$
Portanto,
\begin{equation}
\begin{split}
\sum_{i=0}^d\binom{n}{i}&\leq (n/d)^d\sum_{i=0}^d\binom{n}{i}(d/n)^i\\
&\leq (n/d)^d(1+(d/n))^n\\
&\leq \left(\frac{ e n}{d}\right)^d
\end{split}
\end{equation}
no qual a ultima desigualdade decorre da desigualdade de Euler. Segue o lema.

Esse resultado nos mostra que o número de rotulagens induzido por uma amostra cresce de forma polinomial em $n$, caso a dimensão de Vapnik e Chervonenkis da classe de preditores admissíveis seja finita. A partir do Lema 1, concluímos que 

\[
\ln ( Card(\mathcal{H} ({\bf x}_n))) \leq d \ln(n+1),
\] no qual $VC-dim(\mathcal{H})=d<\infty$. Assim, como consequência da desigualdade 2, obtemos que 

\[
 \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big| \leq   \sqrt{ \frac{16 d \ln(n+1) }{2n}} + 
    \sqrt{\frac{9 \ln (2/ \delta)}{2n}}, ~ {\bf o}_n \in \hat{G}, ~ ~ (\text{Desigualdade 3}),
\] no qual $\mathbb{P}^n (\hat{G}) \geq 1 - \delta$ com $0 \leq \delta \leq 1/2$. Sabemos que para $a,b$ constantes não negativas $\sqrt{a} + \sqrt{b} \leq 2 \sqrt{a+b} $. Com isso, temos que 

\[
\sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big| \leq 2 \sqrt{\frac{16 d \ln(n+1) + 9 \ln (2/ \delta )}{2n}}, ~ {\bf o}_n \in \hat{G}.
\] Com isso, obtemos o teorema de Vapnik e Chervonenkis.

Teorema 1: Teorema de Vapnik e Chervonenkis

Suponha que a classe de preditores admissíveis $\mathcal{H}$ satisfaça $VC-dim(\mathcal{H})=d<\infty$. Então, obtemos que  

\[
\sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big|  \leq 2 \sqrt{\frac{16 d \ln(n+1) + 9 \ln (2/ \delta )}{2n}}, ~ {\bf o}_n \in \hat{G},
\] no qual $\mathbb{P}^n (\hat{G}) \geq 1 - \delta$ com $0 \leq \delta \leq 1/2$. Além disso, temos que

\[
\mathbb{E}_{\mathbb{P}^n} \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big|  \leq 2  \sqrt{ \frac{2 d \ln(n+1) }{n}}.
\]

Com o teorema de Vapnik e Chervonenkis concluímos que a função de risco empírica converge uniformemente para a função de risco esperado com probabilidade $1$ e no $L^1$. A partir das desigualdades 1 e 2 da seção Complexidade de Rademacher e do Teorema de Vapnik e Chervonenkis (Teorema 1), obtemos que


\[
L(\mathbb{P}, A_E({\bf o}_n)) - \inf_{h \in \mathcal{H}} L(\mathbb{P} , h) \leq
4 \sqrt{\frac{16 d \ln(n+1) + 9 \ln (2/ \delta )}{2n}}
\] e

\[
\mid L(\mathbb{P}, A_E({\bf o}_n)) - L_E ({\bf o}_n, A_E({\bf o}_n)) \mid ~ \leq ~  4 \sqrt{\frac{16 d \ln(n+1) + 9 \ln (2/ \delta )}{2n}}, 
\] para todo $ {\bf o}_n \in \hat{G}$. Assim, obtemos o seguinte corolário.

Corolário 1:

Suponha que a classe de preditores admissíveis $\mathcal{H}$ satisfaça $VC-dim(\mathcal{H})=d<\infty$. Então, a estratégia $A_E$ obtida pelo princípio da minimização do risco empírico é PAC.

Teorema 2: 

Seja $V$ um subespaço vetorial do espaço $\mathbb{R}^\chi$ de todas as funções reais sobre o domínio $\chi$. A $VC-dim$ da classe de preditores $\mathcal{H}$ tal que $h_f\in \mathcal{H}$ tal que

$$1\!\!1_{C_f}(x)=\left\{\begin{array}{lc}
                              1, & \text{ se } x\in C_f \\
                              0, & x\notin C_f
                            \end{array}
\right.$$
com $$C_f=\{x\in \chi:f(x)\geq 0\}, \quad f \in V,$$ é menor ou igual a dim $V$.

Prova: 

Seja a $dimV=d$. Como todo ponto $x\in \chi$ pode ser associado a um funcional linear $f_x$ da forma $f\mapsto f(x)$ no qual $f\in V$. O funcional $f_x$ pertence ao espaço vetorial dual $V^\star$. Agora seja $A\subset \chi$ um conjunto com $d+1$ pontos distintos. Como a dimensão de $V$ é $d$, um dos funcionais lineares é combinação linear dos pontos restantes, seja $x_{d+1}\in A$, tal que é combinação linear dos demais. Então,
$$f_{x_{d+1}}=\sum_{i=1}^d \lambda_i f_{x_{i}}, \quad x_i \in A.$$

Defina $$B=\{x_i:0\leq i\leq d, \lambda_i\geq 0\}\subset A$$
Seja $f \in V$ tal que $C_f\cap \{x_1,x_2,\dots,x_d\}=B$. Neste caso, temos que $f(x_i)\geq 0$ se, e somente se, $x_i\in B$ e concluímos que
$$f(x_{d+1})=f_{x_{d+1}}\sum_{i=1}^d \lambda_i f_{x_{i}}\geq 0$$
logo obtemos que $x_{d+1}\in C_f$ e portanto, para qualquer $h\in \mathcal{H}$ temos que $h(x_{d+1})=1$. Logo $\mathcal{H}$, não particiona $A$, pois não existe um $h \in \mathcal{H}$ tal que $h(x_{d+1})=0$.

 

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]