Algoritmos baseados em função Custo

Você está aqui

A partir do Teorema de Vapnik e Chervonenkis temos que minimizar a função de risco empírica com respeito a uma classe $\mathcal{H}$ de preditores admissíveis com dimensão VC bem menor que o tamanho da amostra. Ao requerermos dimensão VC baixa, impomos sérias limitações com respeito a propriedade de aproximação da classe de preditores admissíveis. Além disso, também temos um problema numérico.  No problema de classificação binária queremos minimizar o erro de classificação empírico, que geralmente é bem complicado do ponto de vista computacional. Mesmo em casos bem simples o problema pode ter dificuldade NP. 

Uma das formas de contornar estes dois problemas consiste em modificar a função de risco empírica ao introduzirmos uma função custo.  Considere os preditores admissíveis na forma $$h(x) = 1\!\!1_{\{ f(x) \geq 0\}}, \quad x \in \chi ,$$ no qual $f: \chi \rightarrow \mathbb{R}$ é uma função Borel mensurável que separa ponto no espaço domínio $\chi$. Denotamos por $\mathcal{F} \subset \mathbb{R}^\chi$ uma subclasse de funções $f \chi \rightarrow \mathbb{R}$ Borel mensuráveis. A classe de preditores admissíveis será denotada por $\mathcal{H}_{\mathcal{F}} = \{ h(\cdot) = 1\!\!1_{\{ f(\cdot) \geq 0\}} : f \in \mathcal{F} \}$. Neste caso, a probabilidade de erro de classificação do preditor $h$ satisfaz $$L(\mathbb{P} , h) = \mathbb{P} \left( Y \neq h(X) \right) = \mathbb{E}_{\mathbb{P}} \left( 1\!\!1_{\{Y \neq h(X)\}} \right) \leq \mathbb{E}_{\mathbb{P}} \left( 1\!\!1_{\{(2Y -1)  f(X) < 0 \}} \right) .$$

Seja $\psi : \mathbb{R} \rightarrow [0 , \infty)$ uma função Borel mensurável satisfazendo $\psi(x) \geq 1\!\!1_{\{ x > 0\}}$.  Típicas escolhas para $\psi$ incluem $\psi(x)=e^x$, $\psi(x) = \log_2 (1+ e^x)$   e  $\psi(x) = \max \{1+x , 0\}$, entre outras. A função $\psi$ será de denominada função custo. Com esta notação, introduzimos a função custo esperado e sua versão empírica $$C(f, \mathbb{P}) = \mathbb{E}_{\mathbb{P}} \psi(-f(X) (2Y-1)) \quad \text{e} \quad C_E ({\bf o}_n , f) =  \frac{1}{n}  \sum_{i=1}^n \psi(-f(x_i) (2y_i-1)) , $$ para todo ${\bf o}_n = ((x_1,y_1), \cdots , (x_n,y_n)) \in \mathbb{O}^n$. Obviamente que $L(\mathbb{P} , h_f) \leq C(f, \mathbb{P})$ e $L_E( {\bf o}_n , h_f) \leq C_E ({\bf o}_n , f)$, para todo $h_f \in \mathcal{H}_{\mathcal{F}}$ com $h_f = 1\!\!1_{ \{ f \geq 0 \}}$. Com isso, obtemos que \[  L(\mathbb{P} , h_f) \leq C(f, \mathbb{P}) = C(f, \mathbb{P}) + C_E ({\bf o}_n , f) - C_E ({\bf o}_n , f) \leq \]  \[  C_E ({\bf o}_n , f)  + \sup_{f \in \mathcal{F}} \mid C(f, \mathbb{P})  - C_E ({\bf o}_n , f) \mid ~ ~ (\text{Desigualdade 1}) .\]

Para todo conjunto de dados ${\bf o}_n =((x_1, y_1) , \cdots (x_n , y_n)) \in \mathbb{O}^n$, denotamos por $$\mathcal{C}_{\mathcal{F}}({\bf o}_n) := \{ (-(2y_1 - 1) f(x_1) , \cdots , -(2y_n - 1)f(x_n)) : f \in \mathcal{F} \}.$$ A complexidade de Rademacher relacionada com a classe $\mathcal{H}_{\mathcal{F}}({\bf o}_n)$ é dada por \[ \hat{\mathcal{R}}_n (\psi \circ \mathcal{C}_{\mathcal{F}}({\bf o}_n)) = \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{i=1}^n \sigma_i \psi(-(2y_n - 1)f(x_n)) =  \mathbb{E}_{\mu^n} \sup_{a \in \psi \circ \mathcal{C}_{\mathcal{F}}({\bf o}_n)} \frac{1}{n}  \sum_{i=1}^n \sigma_i a_i ,\] no qual $\psi \circ \mathcal{C}_{\mathcal{F}}({\bf o}_n) = \{ (\psi(a_1), \cdots , \psi(a_n)): (a_1, \cdots , a_n) \in  \mathcal{C}_{\mathcal{F}}({\bf o}_n) \} $ .  Para todo $0 \leq \delta \leq 1/2$, obtemos do teorema da complexidade de Rademacher  que existe um conjunto $\hat{G} \in \beta(\mathbb{O}^n)$ com $\mathbb{P}(\hat{G}) > 1-\delta$ satifazendo

\[ \sup_{f \in \mathcal{F}} \mid C(f, \mathbb{P})  - C_E ({\bf o}_n , f) \mid \leq 2  \hat{\mathcal{R}}_n (\psi \circ \mathcal{C}_{\mathcal{F}}({\bf o}_n)) + 3 B \sqrt{\frac{\ln(2/\delta)}{2n} }, \quad {\bf o}_n \in \hat{G} ~ ~ (\text{Desigualdade 2}),\] no qual assumimos que $$\sup_{ \{ (x,y) \in \mathbb{O}\} } \psi(-(2y - 1) f(x)) \leq B, $$ com $B$ uma constante positiva . 

Teorema 1: Considere $\psi$ uma função Lipschitz com constante $L_{\psi}$. Então, temos que $$L(\mathbb{P} , h_f) \leq C_E({\bf o}_n , f  ) + 2L_{\psi} \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{i=1}^n \sigma_if(x_i) +   3 B \sqrt{\frac{\ln(2/\delta)}{2n} }, \quad {\bf o}_n \in \hat{G}.$$

Prova: Como consequência das desigualdades (1) e (2) e do teorema da contração de Ledoux e Talagrand, obtemos que  \[ L(\mathbb{P} , h_f) \leq C_E({\bf o}_n , f  ) + 2L_{\psi} \hat{\mathcal{R}}_n (\mathcal{C}_{\mathcal{F}}({\bf o}_n)) + 3 B \sqrt{\frac{\ln(2/\delta)}{2n} }. \] Agora, a complexidade de Rademacher é dada por

\[ \hat{\mathcal{R}}_n (\mathcal{C}_{\mathcal{F}}({\bf o}_n)) = \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{i=1}^n \sigma_i  \left( -(2y_n - 1)f(x_i) \right) =  \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{i=1}^n (-\sigma_i)   (2y_n - 1)f(x_i) = \] \[   \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{i=1}^n \sigma_i   (2y_n - 1)f(x_i) =  \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{i=1}^n \sigma_if(x_i), \] pois a distribuição de $\sigma_i$ é simétrica no conjunto $\{-1,1\}$. Segue o teorema.

A partir do Teorema 1, sabemos que a complexidade de Rademacher de uma classe de funções reais $\mathcal{F}$ limita a performance dos preditores admissíveis $\mathcal{H}_{\mathcal{F}}$. 

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]