5. REAKSJONENE
5.2 N OEN ENKELTHETER
mais Pr´oximo
Geralmente, para detectar objetos de diferentes classes em imagens com cen´arios comple- xos utiliza-se diferentes abordagens de classificadores, por exemplo: Adaboost, Random Forest, m´aquinas de aprendizagem baseados em discriminantes como o SVM, entre ou- tros. Adota-se o classificador em cascata de “uma classe” devido `a r´apida rejei¸c˜ao dos exemplos negativos porque centra-se em modelar s´o a classe positiva. Por isso, chama-se m´etodos de uma ´unica classe, j´a que s˜ao classificadores simples e r´apidos nas primei- ras etapas da cascata e nas ´ultimas decidem se o exemplo pertence a classe positiva ou negativa, portanto reduz significativamente a complexidade do classificador (quando treinado com bases complexas, o modelo ser´a eficiente e n˜ao ser´a t˜ao complexo como um classificador forte bem correlacionado com a classe verdadeira).
A cascata consiste em trˆes etapas (Figura 3.9) (Cevikalp et al. 2013): a primeira utiliza um classificador de “uma classe” que aproxima a regi˜ao ocupada pelos vetores de caracter´ısticas da classe positiva afastando-os da classe negativa mediante a distˆancia linear a um hiperplano, a segunda etapa ´e um classificador de Support Vector Data
Descriptor, (Tax and Duin 2004), que est´a baseado em um modelo de uma hiperesfera
linear no espa¸co de caracter´ısticas de entrada. A ´ultima etapa toma a decis˜ao de qual classe o objeto de entrada pertence, utilizando um modelo de hiperesfera n˜ao linear que aproxima as classes dos objetos. O classificador de modelo convexo mais pr´oximo atinge um desempenho competitivo em rela¸c˜ao aos algoritmos do estado da arte, por exemplo: os classificadores lineares utilizados nas primeiras etapas s˜ao simples, r´apidos, tem menos restri¸c˜oes de tempo e menor n´umero de vetores de suporte a diferen¸ca dos classificadores discriminativos linear e n˜ao linear (maior complexidade computacional), (Cevikalp and Triggs 2012).
Geralmente, o espa¸co de caracter´ısticas da classe positiva encontra-se em regi˜oes es- pec´ıficas dentro do modelo e os exemplos negativos (outliers) encontra-se dispersos no espa¸co. Para classificar os exemplos como positivos ou negativos determina-se um limiar a partir do resultado das distˆancias do espa¸co de caracter´ısticas ao modelo convexo. O problema de classifica¸c˜ao do modelo convexo mais pr´oximo segue a propriedade de qual- quer conjunto convexo, onde todos os elementos devem encontrar-se envolvidos dentro da regi˜ao limitada.
28 Referencial Te´orico
Figura 3.9: (a) Dados de entrada: o espa¸co de caracter´ısticas dos objetos da classe positiva e o fundo da classe negativa s˜ao representados como triˆangulos azuis e pontos pretos. (b) Na primeira etapa da cascata, usa-se um classificador linear que utiliza a intersec¸c˜ao de hiperplanos para aproximar a classe. Exemplos que ficam fora dos hiperplanos s˜ao classificados como negativos e s˜ao rejeitados. Os exemplos de fundo que sobreviveram a essa etapa s˜ao mostrados como pontos vermelhos. (c) A segunda etapa ´e um classificador de uma classe no espa¸co linear, que aproxima a regi˜ao da classe dos objetos com uma hiperesfera delimitadora. A maioria dos falsos positivos que sobreviveram na primeira etapa s˜ao rejeitados. (d) A etapa final da cascata ´e um classificador de uma classe n˜ao linear, que aproxima a regi˜ao positiva com mais acur´acia e toma a decis˜ao final, (Cevikalp and Triggs 2012).
linear e hiperesfera n˜ao linear.
1. Aproxima¸c˜ao do hiperplano linear
A primeira etapa do classificador em cascata utiliza um classificador de uma classe, pois tenta aproximar `a classe positiva mediante o c´alculo da distˆancia dos vetores de caracter´ısticas a cada hiperplano, um a um (ver Figura 3.10). Se essa distˆancia encontra-se entre alguns limiares predefinidos (determinados durante o treina- mento) ´e considerado face, caso contrario ´e rejeitado (Cevikalp et al. 2013), ou seja a diferen¸ca do SVM os vetores de caracter´ısticas da classe positiva encontram- se dentro das margens do hiperplano afastando-os dos exemplos negativos. Seja
Referencial Te´orico 29
x o vetor de caracter´ısticas e wTx + b = 0 a equa¸c˜ao do hiperplano. Ent˜ao para
encontrar o hiperplano que melhor se ajusta ao problema, formula-se a seguinte Equa¸c˜ao 3.18:
Figura 3.10: Hiperplano linear que aproxima a classe positiva.
arg min w,ǫ>=0 1 2kwk 2+ C + X i (ǫi+ ǫ∗i) + C− X j ǫj (3.18) tais que: wTxi+ b ≤ ∆ + ǫi, wTx i+ b ≥ −∆ − ǫ∗i, wTxj + b ≥ ∆ + 1 − ǫj, i ∈ I+, j ∈ I−
Onde C+(C−) ´e o parˆametro definido pelo usu´ario que controla o peso dos erros
associados com os exemplos positivos (negativos), I+(I−) ´e o conjunto dos ´ındices
dos exemplos positivos (negativos), ∆ ´e um parˆametro de restri¸c˜ao entre 0 e 1. Mediante essa f´ormula, restringimos os vetores de caracter´ısticas dos exemplos positivos que fiquem dentro de dois hiperplanos paralelos wTx + b = ∆ e wTx + b =
−∆. Os exemplos negativos ficam do lado direito do hiperplano wTx + b = 1 + ∆
separados dos exemplos positivos por um margem m´ınima 1/kwk. As vari´aveis de folga positivas ǫi, ǫ∗i, ǫj s˜ao introduzidas para aqueles exemplos que n˜ao cumprem
30 Referencial Te´orico
pode ser resolvido por qualquer algoritmo de programa¸c˜ao quadr´atica. Em espa¸cos de altas dimens˜oes, essa f´ormula ´e mais robusta e ajusta-se melhor comparada com a f´ormula dos m´ınimos quadrados, (Cevikalp et al. 2013).
Na pr´atica, utilizamos Optimized Cutting Plane Algorithm (OCAS, em portuguˆes Algoritmo de Corte de Plano Otimizado) para treinar a primeira etapa do classi- ficador em cascata. Vojtˇech and Soeren (2008) desenvolveram uma nova m´aquina de suporte vetorial linear que supera significativamente os SVMs atuais, como:
SVM light , SVM perf e BMRM de (Teo et al. 2007), obtendo a mesma solu¸c˜ao
precisa, mostrando uma r´apida convergˆencia e quando paraleliza-se efetivamente o OCAS pode treinar base de dados de tamanho de 15 milh˜oes de exemplos em 671 segundos.
A equa¸c˜ao 3.19 centra-se em encontrar solu¸c˜oes do problema primal sem restri¸c˜oes do SVM linear: w∗ = arg min w∈RnF (w) := 1 2kwk 2+ CR(w) (3.19)
onde o w denota o vetor de parˆametros a ser aprendido, 1 2kwk
2 ´e o termo de
regulariza¸c˜ao, C > 0 ´e uma constante fixa e R ´e um risco convexo que aproxima o erro do treino. Entre os algoritmos mais eficientes para resolver o problema primal (Equa¸c˜ao3.19), encontra-se o Cutting Plane Algorithm (CPA, em portuguˆes Algoritmo de Plano de Corte). A id´eia do CPA ´e aproximar por partes o risco R mediante uma fun¸c˜ao linear m´axima sobre um conjunto de planos de corte pr´oximos do m´ınimo valor de w∗
. Vojtˇech and Soeren (2008) mostraram que se precisa o menor n´umero de planos de corte para aproximar a Equa¸c˜ao 3.19 e n˜ao depende do n´umero dos exemplos de treino (dimens˜ao).
A ineficiˆencia desse algoritmo est´a no n´umero de itera¸c˜oes na sele¸c˜ao do plano de corte no problema reduzido da Equa¸c˜ao 3.19, ou seja, converge arbitrariamente em um m´ınimo local que n˜ao est´a necessariamente na vizinhan¸ca de w∗. Isso acontece
porque em cada itera¸c˜ao o CPA seleciona um plano de corte que perfeitamente aproxima-se ao objetivo do problema primal na solu¸c˜ao atual. Enquanto, isso n˜ao garante que o plano de corte seja uma restri¸c˜ao ativa na vizinhan¸ca do valor ´otimo de w∗. Resulta que v´arios planos de cortes selecionados n˜ao contribuem
a aproxima¸c˜ao do objetivo do problema primal perto do valor ´otimo, portanto aumenta o n´umero de itera¸c˜oes. Para acelerar a convergˆencia do CPA, otimiza-
Referencial Te´orico 31
se o algoritmo de plano de corte (em inglˆes Optimized Cutting Plane Algorithm, OCA), onde seleciona-se o plano que tenha a maior oportunidade de ativamente contribuir `a aproxima¸c˜ao da fun¸c˜ao objetivo do problema primal perto do valor ´otimo de w∗. Assim, foi desenvolvido eficientemente o OCA para SVM linear
bin´ario e multiclasse. Vojtˇech and Soeren (2008), mostraram que o procedimento de linha de busca requerido para resolver exatamente os problemas bin´arios e multiclasses ´e de O(mlogm) e O(m.Y2+ m.Y log(m.Y )), respectivamente, onde m
´e o n´umero de exemplos e Y o n´umero de classes.
2. Aproxima¸c˜ao da hiperesfera linear
A segunda etapa da cascata ´e um classificador de Vetores de Suporte de Descri¸c˜ao de Dados Linear (SVDD do inglˆes Support Vector Data Description), baseado em um modelo de hiperesfera linear no espa¸co de caracter´ısticas de entrada. ´E computacionalmente eficiente, j´a que aceita quase todos os exemplos positivos (faces) e rejeita alguns exemplos negativos (fundo da imagem) que foram aceitos pelo primeiro est´agio (hiperplano linear). Esse classificador ´e mais custoso do que o anterior porque para treinar utiliza uma formula¸c˜ao de margem m´axima antes de um ajuste linear simples (ver Figura 3.11).
Figura 3.11: Hiperesfera linear que aproxima a classe positiva.
Essa hiperesfera delimitadora de um conjunto de pontos: xi|i = 1....n ´e caracte-
rizada pelo centro c e raio r. Isso pode ser resolvido mediante um problema de programa¸c˜ao quadr´atica, 3.20.
32 Referencial Te´orico arg min c,r≥0,ǫ≥0 r 2 + γX i ǫi ! (3.20) tais que: kxi− ck2 ≤ r2+ ǫi, i = 1, ..., n Ou seu dual argmin α X i,j αiαjhxi, xji − X i αikxik2 ! (3.21) tais que: X i αi = 1, ∀i 0 ≤ αi ≤ γ,
onde h.i representa o produto escalar (possivelmente n˜ao linear), αi s˜ao os multipli-
cadores de Lagrange e γ ∈ [1/n, 1] ´e um parˆametro limite que pode ser configurado a um valor menor do que 1 para reduzir a influˆencia dos outliers . Tratando-se de um problema convexo, o m´ınimo global pode ser determinado eficientemente atrav´es de um solucionador de problemas quadr´aticos. No caso de mapear o espa¸co de caracter´ısticas com uma fun¸c˜ao kernel, a informa¸c˜ao dual fica dentro de uma solu¸c˜ao espalhada em termos de vetores de suporte (ou seja, os exemplos ficam exatamente na hiperesfera), isso faz com que o modelo seja mais eficiente e n˜ao precise de modelar a distribui¸c˜ao completa dos dados de entrada pois ´e mais flex´ıvel utilizando fun¸c˜oes de kernel.
Os exemplos negativos s˜ao utilizados para aperfei¸coar o modelo, for¸cando-os ficar fora dos limites da hiperesfera (diminui o volume da hiperesfera para evitar os outliers ou exemplos negativos). Suponha que temos n1 exemplos positivos de
treino enumerados pelos ´ındices i, j e n2 exemplos negativos enumerados por l, m.
A hiperesfera mais compacta que inclui os exemplos positivos e exclui os exemplos negativos, pode ser encontrada mediante um problema de programa¸c˜ao quadr´atica, 3.22:
Referencial Te´orico 33 arg min c,r≥0,ǫ≥0 r 2+ γ i X i ǫi+ γ2 X l ǫl ! (3.22) tais que: kxi − ck2 ≤ r2+ ǫi, i = 1, ..., n1 kxl− ck2 ≥ r2+ ǫl, l = 1, ..., n2 Ou seu dual argmin α X i,j αiαjhxi, xji + X l,m αlαmhxl, xmi − 2X l,j αlαjhxl, xji + ( X l αlkxjk2− X i αikxik2) (3.23) tais que: X i αi− X l αl = 1, ∀i, j 0 ≤ αi ≤ γl, 0 ≤ αl ≤ γ2
Esse problema tamb´em ´e convexo e pode ser solucionado mediante algoritmos de programa¸c˜ao quadr´atica. Dados os coeficientes de Lagrange ´otimos αi, o centro da
hiperesfera limitada calcula-se na Equa¸c˜ao 3.24:
c = X i αixi− X l αlxl (3.24)
A maior parte dos coeficientes s˜ao zeros mas os exemplos daqueles coeficientes que s˜ao diferentes de zero, chamam-se vetores de suporte, e o maior n´umero deles correspondem `a classe positiva (exemplos das faces). Al´em disso, o n´umero de vetores de suporte retornados s˜ao muito menores do que o n´umero retornado pelo algoritmo SVM. Uma vez encontrado o centro da hiperesfera, o raio ´e calculado mediante as restri¸c˜oes da Equa¸c˜ao 3.22.
Esse modelo difere de um SVM cl´assico porque encontra uma hiperesfera estreita circundante a classe dos objetos (positivos), e n˜ao um hiperplano que os separa dos exemplos negativos. Ent˜ao, Cevikalp and Triggs (2012) encontraram que in-
34 Referencial Te´orico
cluindo os exemplos negativos significativamente melhora a performance do detec- tor em cascata. No caso das Equa¸c˜oes 3.21 e 3.23 s˜ao algoritmos de programa¸c˜ao quadr´atica com um m´ınimo global.
Durante a detec¸c˜ao de objetos, encontra-se a distˆancia de cada vetor de carac- ter´ısticas das sub-janelas ao centro da hiperesfera linear, rejeitando os exemplos negativos se a distˆancia for maior do que o raio.
3. Classificador n˜ao linear
A terceira etapa da cascata ´e um classificador de hiperesfera n˜ao linear que toma a decis˜ao final (´e o mais complexo), porque faz uma discrimina¸c˜ao mais fina das etapas anteriores pois poucos exemplos conseguiram chegar at´e esta etapa (ver Figura 3.12).
Figura 3.12: Hiperesfera n˜ao linear que aproxima a classe positiva.
O modelo da hiperesfera pode substituir os produtos escalares hxi, xji por ava-
lia¸c˜oes de kernel K(xi, xj) = hφ(xi), φ(xj)i na Equa¸c˜ao 3.23, onde φ ´e o espa¸co de
caracter´ısticas mapeado pelo kernel. O treinamento ´e simples mas a avalia¸c˜ao das distˆancias dos exemplos x ao centro da hiperesfera limitada requer de avalia¸c˜oes do kernel K(xi, x), em contra dos vetores de suporte xi. Isso faz que o SVDD
kernelized seja mais complexo do que o linear e o n´umero de vetores de suporte, sendo ainda menor do que o n´umero dos exemplos de treino.
Enquanto na pr´atica encontraram que o classificador SVDD kernelized tem um n´umero menor de vetores de suporte (a maior parte corresponde dos exemplos po- sitivos), assim s˜ao mais r´apidos do que os SVM kernelized, porque eles apresentam muitos vetores de suporte negativos necess´arios para rejeitar os exemplos negati-
Referencial Te´orico 35
vos complexos. Portanto, ´e mais eficiente utilizar esse tipo de classificadores na cascata do que o SVM kernelized.