Classes de Preditores Lineares

Você está aqui

Neste módulo, vamos tratar o caso de preditores lineares em problemas de classificação binária. Considere os preditores admissíveis na forma $$h_f(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 pontos 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_f(\cdot) = 1\!\!1_{\{ f(\cdot) \geq 0\}} : f \in \mathcal{F} \}$. Aqui, vamos tomar $\mathbb{F}$ como a classe dos funcionais lineares. 

A partir do teorema da complexidade de Rademacher (Teorema 1), sabemos 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}$$ no qual $\hat{G} \in \beta (\mathbb{O}^n)$ com $\mathbb{P}^n(\hat{G}) \geq 1 - \delta$. Assim, limitamos o comportamento dos preditores admissíveis pela complexidade de Rademacher de uma classe de  funções $\mathcal{F}$. Na sequência, vamos estudar a complexidade de Rademacher da classe de funções lineares.  Iniciamente, vamos estudar o caso finito dimensional. Para todo $p \geq 1$, definimos

\[
B^d_p = \{ a \in \mathbb{R}^d :  \parallel a \parallel_p \leq 1 \}, 
\] a bola unitária em $\mathbb{R}^d$ com respeito a norma de ordem $p$. Sabemos que para dois pares $1 \leq p,q \leq \infty$ conjugados $\frac{1}{p} + \frac{1}{q}=1$, temos que 

\[
\parallel a \parallel_p = \sup_{b \in B^d_q} \mid \langle a , b \rangle \mid .
\]  Como consequência da desigualdade de Holder, temos que 

\[
\langle a , b \rangle \leq \parallel a \parallel_p ~ \parallel b \parallel_q , ~ ~ a \in B^d_p , ~ ~ b \in B^d_q.
\]  

Considere $\chi = B^d_2$ a bola unitária com produto interno $\langle \cdot , \cdot \rangle_{\chi}$. Dizemos que uma função é linear se $f(x)$ for linear em $x$. A classe $\mathcal{F}$ consiste em todas as funções lineares sobre $\chi$ com valores $\mathbb{R}$. No caso finito dimensional, também podemos interpretar $f$ como um vetor em  $B^d_2$ de tal forma que $f(x)=\langle f , x \rangle_{\chi}$.  Assim, para qualquer dado de entrada ${\bf x}_n \in \chi^n$, temos que 

\[
\mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{t=1}^n \sigma_t f(x_t)  = \mathbb{E}_{\mu^\infty} \sup_{f \in \mathcal{F}} \left[ \frac{1}{n} \sum_{t=1}^n \sigma_t \langle f , x_t \rangle_\chi  \right] = \mathbb{E}_{\mu^\infty} \sup_{f \in \mathcal{F}}  \langle f , \frac{1}{n} \sum_{t=1}^n \sigma_t x_t) \rangle_\chi = \mathbb{E}_{\mu^\infty} \parallel \frac{1}{n} \sum_{t=1}^n \sigma_t x_t \parallel_2,
\] pois $f \in \mathcal{F}$ é uma função linear. Assim, podemos interpretar a complexidade de Rademacher como a norma em $B^d_2$ do andar aleatório definido por $\sigma_t x_t$ normalizado por $n$. Como consequência, obtemos a desigualdade de Kahane e Khintchine 

\[
\mathbb{E}_{\mu^\infty} \parallel \sum_{t=1}^n \sigma_t a_t \parallel_2  \leq \left( \mathbb{E}_{\mu^\infty} \parallel  \sum_{t=1}^n \sigma_t x_t \parallel_2^2 \right)^{1/2} = \]  \[
\left( \mathbb{E}_{\mu^\infty} \sum_{t,s=1}^n \langle   \sigma_t x_t , \sigma_s x_s \rangle \right)^{1/2} =
\left( \sum_{t=1}^n \mathbb{E}_{\mu^\infty} \parallel   x_t \parallel_2^2 \right)^{1/2} \leq \sqrt{n} .
\] Assim, obtemos que  

\[\mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{t=1}^n \sigma_t f(x_t)  \leq \frac{1}{\sqrt{n}}. \]

Ao utilizarmos a desigualdade de Kahane e Khintchine também podemos obter um limitante inferior, na forma

\[\mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{t=1}^n \sigma_t f(x_t) \geq \frac{1}{2 \sqrt{n}}. \]

De forma similar podemos estender esta  propriedade para espaços de Hilbert. Seja $\chi$ um espaço de Hilbert separável com produto interno $\langle \cdot , \cdot \rangle_\chi$. Denotamos por $\chi^\star$ o espaço de todos os funcionais lineares sobre $\chi$ (dual topológico). Pelo teorema da representação de Riesz sabemos que para todo $f \in \chi^\star$ existe $x^f \in \chi$ tal que $$f(x) = \langle x , x^f \rangle_\chi , \quad x \in \chi.$$ Desta forma, identificamos o dual topológico do espaço de Hilbert $\chi$ com o próprio espaço de Hilbert via o produto interno. De forma usual, a norma dual é dada por $$ \parallel f \parallel_{\chi^\star} =  \sup_{x \in \chi} \mid f(x) \mid =  \sup_{x \in \chi}  \mid \langle x , x^f \rangle_\chi  \mid, \quad f \in \chi^\star .$$  Aqui, tomamos a classe de funções $\mathcal{F} = \chi^\star$. Ao aplicarmos os mesmos argumentos da Bola unitária  $B^d_2$, concluímos que 

\[ \frac{1}{2 \sqrt{n}} \leq  \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{t=1}^n \sigma_t f(x_t)  \leq \frac{1}{\sqrt{n}}.  \] 

Na sequência, vamos estender a teoria de classes de preditores lineares para espaços de Banach. Aqui, vamos utilizar resultados sobre análise convexa em espaços de Banach apresentados no livro:

  • J. Peypouquet (2014) - Convex Optimization in Normed Spaces. Springer.

Considere $\chi$ a bola unitária em um espaço de Banach separável e reflexivo com norma $\parallel \cdot \parallel$. O dual topológico do espaço de Banach $\chi$, definido como o espaço dos funcionais lineares sobre $\chi$, será denotado por $\chi^\star$ com norma dual

\[ \parallel f \parallel_{\star} =\sup_{x \in \chi} \mid \langle f , x \rangle \mid,\]  no qual $\langle \cdot , \cdot \rangle : \chi^\star \times \chi \rightarrow \mathbb{R}$ uma função bilinear tal que $\langle f , x \rangle = f(x)$ para todo funcional linear $f \in \chi^\star$ e todo ponto $x \in \chi$. Seja $\Psi^\star$ uma função fortemente $\theta$-convexa com respeito a norma $\parallel \cdot \parallel_{\star}$, isto é, para todos funcionais lineares $f,g \in \chi^\star$ temos que

\[ \Psi^\star(f) \geq   \Psi^\star(g) + \langle f-g , \nabla \Psi^\star (g)  \rangle + \frac{\theta}{2} \parallel f-g \parallel_{\star}^2 ,\] no qual $\theta$ é uma constante positiva e $\nabla : \chi^{\star \star}  \rightarrow \mathbb{R}$ é o funcional linear dado pela derivada de Gâteaux, no qual $\chi^{\star \star} $ é o dual topológico de $\chi^\star$ (ver, Peypouquet (2014), Teorema 3.12, pg 39).  Como $\chi$ é reflexivo, sabemos que $\chi^{\star \star} = \chi$.Por outro lado, o conjugado convexo de Fenchel da função $\Psi^\star$ é dado por 

\[ \Psi(x) = \sup_{f \in \mathcal{F}} \left\{ \langle f , x \rangle - \Psi^\star (h) \right\}, \] que satisfaz a propriedade conjugada. Para todo $x , x^\prime \in \chi$, temos que

\[  \Psi(x) \leq \Psi(x^\prime) + \langle \nabla \Psi (x^\prime) , x - x^\prime \rangle + \frac{1}{2 \theta} \parallel x - x^\prime \parallel ^2 ~ ~ (\text{Desigualdade 1}) .\] Seja $M^2 = \sup_{h \in \mathcal{H}} \Psi^\star (h)$. Através da definição de convexo conjugado acima, obtemos que para todo $\lambda > 0$,

\[ \mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{t=1}^n \sigma_t f(x_t)  = \frac{\lambda}{\lambda}  \mathbb{E}_{\mu^\infty} \sup_{f \in \mathcal{F}} \left[ \frac{1}{n} \sum_{t=1}^n \sigma_t \langle f , x_t \rangle  \right] = \frac{1}{\lambda} \mathbb{E}_{\mu^\infty} \sup_{f \in \mathcal{F}}  \langle f , \frac{\lambda}{n} \sum_{t=1}^n \sigma_t x_t) \rangle \leq \] \[ \frac{1}{\lambda} \left[ \sup_{f \in \mathcal{F}} \Psi^\star (f) + \mathbb{E}_{\mu^\infty} \Psi \left( \frac{\lambda}{n} \sum_{t=1}^n \sigma_t x_t \right)  \right]. \] Ao denotarmos por $$Z_k = \frac{\lambda}{n} \sum_{t=1}^k \sigma_t x_t , \quad k=1, \cdots , n,$$ concluímos da desigualdade 1 que valor esperado da expressão acima é dado por

\[ \mathbb{E}_{\mu^\infty} \Psi \left( Z_n \right)   \leq  \mathbb{E}_{\mu^\infty} \left[ \Psi \left( Z_{n-1} \right) + \langle \nabla \Psi (Z_{n-1}) , \frac{\lambda}{n} \sigma_n x_n \rangle + \frac{1}{2 \theta} \parallel \frac{\lambda}{n} x_n \parallel^2 \right]. \] Agora, temos que 

\[  \mathbb{E}_{\mu^\infty}  \langle \nabla \Psi (Z_{n-1}) , \frac{\lambda}{n} \sigma_n x_n \rangle = 0 \quad \text{e} \quad \mathbb{E}_{\mu^\infty} \frac{1}{2 \theta} \parallel \frac{\lambda}{n} x_n \parallel^2  \leq \frac{\lambda^2}{2 \theta n^2} ,\] pois $x_n$ pertence a bola unitária de um espaço de Banach $(\chi)$. Desta forma, concluímos que

\[\mathbb{E}_{\mu^n} \sup_{f \in \mathcal{F}} \frac{1}{n}  \sum_{t=1}^n \sigma_t f(x_t) \leq \frac{M^2}{\lambda} + \frac{\lambda}{2 \theta n} = M \sqrt{\frac{2}{\theta n}}, \] no qual $\lambda = M \sqrt{2 \theta n}$. 

 

 

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]