Miss Fisher enquête | My Pet Monster | Watch now!

Máquinas de Vectores Soporte Adaptativas


Save this PDF as:
 WORD  PNG  TXT  JPG

Tamaño: px
Comenzar la demostración a partir de la página:

Download "Máquinas de Vectores Soporte Adaptativas"

Transcripción

1 Máqunas de Vectores Soporte Adaptatvas Gullermo Grnblat y Alejandro Ceccatto Centro Internaconal Franco-Argentno de Cencas de la Informacón y de Sstemas (CIFASIS) - Unversdad de Marsella/UNR/CONICET Bvd. 7 de Febrero 10 Bs, 000 Rosaro, Repúblca Argentna Resumen Se propone un método de clasfcacón adaptatvo capaz de aprender un concepto y segur su evolucón temporal como consecuenca de cambos lentos en sstemas evolutvos. Para ello se realza una modfcacón del clasfcador SVM (máquna de vectores soporte), consstente en usar múltples hperplanos váldos en pequeñas localdades temporales (ventanas) para realzar la clasfcacón. A dferenca de otras propuestas de este tpo en la lteratura, en este caso se realza un aprendzaje de todos los hperplanos en forma global, mnmzando una cantdad que contene al error que comete la famla de clasfcadores locales más una medda asocada a la dmensón VC de los msmos. Para conceptos estaconaros, la msma dea aplcada a localdades en el espaco de característcas permte obtener resultados comparables a los que proporcona SVM con kernel gausano. 1. INTRODUCCIÓN Muchos problemas de clasfcacón asocados a sstemas del mundo real varían con el tempo. Por ejemplo, un sstema puede varar por razones físcas como las estacones del año, o puede ser necesara su adaptacón por cambo en las expectatvas o ntereses de los usuaros del msmo. En la mayoría de los casos, la causa y característcas de este cambo no se presentan en los datos a analzar de manera obva, por lo que el clasfcador asocado tene que ser capaz no sólo de aprender la relacón entrada-salda correcta en cada nstante de tempo sno además advertr el cambo en el concepto y adaptarse a él. Habtualmente este problema se trata usando una ventana temporal, suponendo que el cambo en el concepto a aprender es desprecable dentro de ella [1]. S la ventana es de ancho muy grande, dcha suposcón en general no es válda y el tempo de adaptacón del algortmo resulta excesvo. Por el contraro, cuando el ancho de la ventana es chco el algortmo se adapta rápdamente, pero es más sensble al rudo y se torna mprecso ya que debe aprender la relacón entrada-salda a partr de unos pocos ejemplos. Dentro de esta aproxmacón al problema, exsten algortmos que usan un ancho de ventana adaptable [1], donde se dvden los datos en grupos ( batchs ) y se usa como ventana la cantdad de grupos óptma. Aún así, es gualmente necesaro suponer que el concepto no camba dentro de cada grupo de datos. Por otro lado, un enfoque puramente estadístco del aprendzaje de conceptos evolutvos puede hallarse en []. 1476

2 En este trabajo presentamos una nueva forma de encarar este problema, en la cual los clasfcadores sucesvos varían sguendo la mutacón del concepto pero su ajuste se realza de manera global. Es partcular, la ventana temporal de valdez de un clasfcador puede ser tan chca como se desee (nclusve un sólo punto), pero los clasfcadores se entrenan mnmzando una medda global de error en lugar de ajustarse localmente. Esta flosofía se aplca onsderando una adaptacón de uno de los métodos de clasfcacón más potentes y estudados en la actualdad, las llamadas maqunas de vectores soporte o SVM por sus sglas en nglés [3]. En el caso de clasfcacón estaconara, la flosofía arrba descrpta puede aplcarse reemplazando las ventanas temporales por vecndades de un punto en el espaco de característcas del problema. De esta forma, el clasfcador SVM puede descrbr fronteras de decsón complejas (no smples hperplanos) sn necesdad de apelar al truco del kernel ( kernel trck )[3] para lograr un clasfcador no lneal. Mostraremos, a través de un ejemplo smple, que con esta mplementacón de SVM adaptatvo es posble alcanzar resultados equvalentes a SVM con kernel gausano.. JUSTIFICACIÓN DEL MÉTODO Supongamos que tenemos un conjunto de datos [(x 1, y 1 )..., (x n, y n )], donde (x, y ) fue obtendo en el nstante t = y y = ±1. Defnmos: Clase F : Clase de clasfcadores tal que f F mplca que f mplementa una frontera de decsón consttuda por hperplanos que camban con t. Así, un punto en un nstante dado es clasfcado de acuerdo al lado del hperplano correspondente a ese nstante en que se encuentra. Note que la dmensón de Vapnk-Chervonenks (VC) [4] de F es, ya que s el hperplano camba lo sufcente desde el nstante 1 al nstante, podrá clasfcar ben el punto x sn mportar dónde se encuentre. Clase F reducda: Sea f F v un clasfcador pertenecente a F, tal que el cambo del hperplano de un nstante al sguente está acotado por v. Para ser más precsos, s en el nstante el hperplano es f = w x + b, entonces f F v (w 1 w ) + (b 1 b ) v. (1) Sea F v el conjunto de clasfcadores que no camban más que v, con v v. Como F v F v, la dmensón VC de F v la dmensón VC de F v. Por otro lado, la dmensón VC de F v=0 en R n es n + 1, ya que es el conjunto de hperplanos que no varían. Es decr, la dmensón VC de F v crece con v. De acuerdo a esto, s queremos controlar la complejdad de las funcones f podemos lmtarnos a elegr funcones de F v para certo v. O, por la teoría de regularzacón, en vez de buscar la funcón de F v que mnmce certo error Err(f, x, y), podemos buscar la funcón de F que mnmce Err(f, x, y) + C comp(f) 1477

3 donde C es una constante que defne la mportanca relatva de los errores de clasfcacón con respecto a la complejdad de la funcón comp(f) = máx [(w 1 w ) + (b 1 b ) ]. Alternatvamente, podemos hacer el msmo razonamento defnendo F v como la clase de hperplanos que en promedo se mueven menos que v, con lo que llegaríamos a mnmzar Err(f, x, y) + C 1 (w 1 w ) + (b 1 b ) n Por un razonamento smlar al realzado anterormente, podemos llegar a la conclusón de que la dmensón VC baja cuando el margen promedo del hperplano móvl crece. Defnmos entonces la complejdad de f como comp(f) = 1 n w + n (w 1 w ) + (b 1 b ) donde ndca a qué causa de aumento de la dmensón VC le damos más mportanca. Defnendo ahora Err(f, x, y) = máx[0, 1 y (w x + b )], llegamos al problema mín C 3 máx(0, 1 y (w x +b ))+ 1 w + n n que es equvalente a sujeto a mín C 3 ξ + 1 w + n n (w 1 w ) +(b 1 b ), (w 1 w ) + (b 1 b ), ξ 0 y (w x + b ) 1 + ξ SVM ADAPTATIVO Tal como fuera explctado más arrba, tenemos n puntos, x 1... x n, dvddos en dos clases, con y = ±1 la clase del punto x. Defnmos ahora V como el conjunto de puntos vecnos a x y denotamos N al número de puntos en V. En lo sucesvo llamaremos M a la fla de la matrz M y M j a la columna j de dcha matrz. Con P Q ndcaremos el producto membro a membro de las matrces P y Q; es decr, (P Q) j = P j Q j. 1478

4 Partmos del problema 1 n mín w + w,b n =1 con w = w w, sujeto a w w j + (b b j ) + C 3 ξ, j V ξ 0 y (w x + b ) 1 + ξ 0. El correspondente lagrangeano es: L = 1 n w + C w w j + (b b j ) + C 3 n =1 j V α (y (w x + b ) 1 + ξ ) ξ β ξ, () donde α 0 y β 0. Tenemos que maxmzar L con respecto a los α y β y mnmzarlo con respecto a los w, b y ξ. En este punto de mínmo, las dervadas con respecto a las varables prmales tenen que ser nulas: lo cual mplca que L ξ = 0 = C 3 α β, 0 α C 3. Por otro lado, tenendo en cuenta que cada ξ está en L multplcado por C 3 α β, () queda L = 1 n w + C w w j + (b b j ) α (y (w x +b ) 1). n =1 j V (3) En el caso de los w se tene L = 0 = 1 w + (w w j ) α y x, w n j V donde se ha consderado que s x j es vecno de x, x es vecno de x j. Esta ecuacón resulta 1 (1 + N )w w j = α y x. (4) n j V 1479

5 S defnmos la matrz M y el vector z como (1 + N )/n s = j M j = /n s j V 0 caso contraro. z = α y x podemos poner (4) en la forma Mw = z, o ben w = (M 1 ) z. Reemplazando en (3) obtenemos L = 1 n αt ((M 1 ) K)α + 4n αt ((M 1 QM 1 ) K)α + C (b b j ) 4n j V α T ((M 1 ) K)α + α α y b. (5) donde hemos defndo dos matrces N N, K j = y y j x x j y Q dada por N s = j Q j = 1 s es vecno de j 0 caso contraro En el caso de los b, de lo que obtenemos Defnendo h como: L = 0 = b n podemos escrbr (6) en la forma N n b n j V (b b j ) α y, j V b j = α y. (6) α 1 y 1 h =.. α n y n Qb = h. (7) n Dado que Q es sngular, N 1 j V 1 0 Q1 =. N n =. j V n 1 0 se puede afrmar que 0 = n 0b = n 1Qb = 1h = α y. 1480

6 3.1. Elmnacón de los b Es posble elmnar b de (5). La parte que depende de b es Por otro lado, con lo que (b b j ) 4n j V De (7) sabemos que con lo cual queda b T Qb = α y b = C (b b j ) h T b. 4n j V j V (b b j )b. (b b j ) h T b = 4n n bt Qb h T b. j V b T Q = nht, nh T b h T b = ht b n. Dagonalzando Q resulta Q = P DP T, con P 1 = P T ya que Q es smétrca, con lo cual de (7) podemos obtener DP T b = P T nh S defnmos b = P T b y h = P T h, esto es Db = nh. Como D es dagonal, es fácl encontrar los b para los cuales D = λ 0: b = nh λ, s λ 0. S el autovalor λ = 0, de (7) tenemos que P Qb T = P T nh 0b = P T nh 0 = nh. 0 = h 1481

7 Es decr, cuando no podemos determnar b por la ecuacón anteror, h = 0. Volvamos a lo que queremos obtener: ht b = P P T b ht = 1 h T b = 1 h b = 1 n Λ h donde Λ = 1 λ s λ 0 y Λ = 0 s λ = 0. S se defne D como la matrz dagonal D = Λ e Y dada por Y j = y y j, esto últmo queda Reemplazando en (5) obtenemos ht b = n h T P D P T h = n α T ((P D P T ) Y )α. L = 1 n αt ((M 1 ) K)α + 4n αt ((M 1 QM 1 ) K)rrα α T ((M 1 ) K)α + α n α T ((P D P T ) Y )α Es decr, L = α T [( 1 n M + 4n M 1 QM 1 M 1 ) K n ] (P D P T ) Y α+ α, lo que mplca que es de la forma L = α T Rα + α con la matrz R defnda de manera adecuada. El problema dual queda entonces máx α αt Rα + α, 148

8 sujeto a 0 α C 3 α y = 0, que es el problema resuelto en SVM (aunque con otra R). En consecuenca, para resolverlo se puede usar cualquera de las técncas empleadas para SVM convenconal, como por ejemplo SMO[3]. 4. EXPERIMENTOS 4.1. Bases de Datos Artfcales Se probó el método en las sguentes tres bases de datos artfcales: Dataset 1: Se generó un dataset de puntos x R, dvddos en dos clases, la clase 1 formada por 50 puntos centrados en (0, 1), con un desvío estandar de 0,1 en cada dmensón y la clase 1 formada por 50 puntos centrados en (0, 1), con el msmo desvío. Para smular un cambo a través del tempo, a cada punto x, representado en coordenadas polares, se le sumó un ángulo de π 500 radanes. Al algortmo se le presentaron los puntos en coordenadas rectangulares. El resultado se grafca en la fgura 1. Fgura 1. Dataset 1 Dataset : A los msmos puntos que en el dataset anteror se les sumó un ángulo 3π π 1000 en vez de 500. En este caso el solapamento de las clases es mayor (ver fgura ). 1483

9 Fgura. Dataset Dataset 3: Se tomaron 500 puntos x R al azar con x 1 [ 0,; 1,] y x [ 5; 5], con dstrbucón unforme. Al punto x se le asgnó la clase 1 s 1 x, 1 + e x 1, y la clase 1 en caso contraro (ver Fgura 3). Fgura 3. Dataset

10 La ntencón de las pruebas con los dos prmeros datasets fue ver cómo evolucona el clasfcador a través del tempo al varar el parámetro y compararlo con la solucón encontrada por SVM estándar con kernel lneal (que no tene en cuenta el tempo en que cada una de las muestras fue colectada). Para que el método busque una evolucón temporal, se consderó como conjunto de puntos vecno a x a {x 1, x +1 } (salvo en el caso de los extremos). Es decr, se usó una matrz Q dada por Q 11 = Q nn = 1 Q,+1 = Q, 1 = 1 Q = para 1 e n Q j = 0 en otros casos. El parámetro C 3 se dejó fjo en 1 mentras se varaba. Acorde a esto, se usó C = 1 para el parámetro de SVM. Los resultados obtendos muestran que el clasfcador camba de la msma forma en que se generaron los puntos para los valores más bajos de y tende a la solucón encontrada por SVM estándar a medda que crece. El error de entrenamento es 0, salvo para valores altos de, que oblgan a que el clasfcador no varíe mucho y en consecuenca no puede segur la evolucón de los datos (cabe aclarar que los datasets no tenen puntos mal clasfcados). En la fgura 4 se ve la evolucón del clasfcador para {10, 10 3, 10 6, 10 8 }. Las líneas unen el extremo de cada vector w con el de los vectores w +1 y w 1 ; es decr, consttuyen la gráfca de la curva w(t). Los errores de entrenamento para estos cuatro casos fueron 0, 0, 0 y,6 %, respectvamente. Fgura 4. Dataset 1. Las líneas muestran la evolucón w(t) para = 10 (verde), 10 3 (azul), 10 6 (roja) y 10 8 (negra); el punto negro corresponde al w obtendo con SVM no adaptvo. 1485

11 Para el dataset se obtuveron resultados smlares. En la fgura 5 se ven las curvas correspondentes a {10 3, 10 6, 10 7, 10 8 }. Los errores de entrenamento fueron de 0, 0, 0, % y 8,8 % para cada uno de estos valores. Cabe destacar que el alto valor de error correspondente a = 10 8 consttuye aproxmadamente el resultado esperado para SVM estándar (no adaptatvo), debdo a la alta superposcón de las clases. Fgura 5. Dataset. Las líneas muestran la evolucón w(t) para = 10 (verde), 10 3 (azul), 10 6 (roja) y 10 8 (negra); el punto negro corresponde al w obtendo con SVM no adaptatvo. Con el tercer dataset se ejemplfca cómo se comporta el método en problemas cuya frontera de decsón no sea un smple hperplano (tratando esta stuacón como un cambo adaptatvo en el espaco de característcas del problema en lugar del tempo). S ben la frontera de decsón es una funcón compleja de la entrada, se pueden separar las clases con un hperplano que varíe lentamente a medda que camba una de las coordenadas. Note que en este caso la aplcacón del método se realza sobre un sstema estaconaro, por lo que este ejemplo en realdad explora la capacdad del algortmo aquí propuesto de constturse en una alternatva al uso de SVM con kernels no-lneales. Para que el método busque solucones que varíen localmente se consderó como vecnos a los puntos x y x j s x es uno de los 5 vecnos más próxmos a x j o x j es uno de los 5 vecnos más próxmos a x. Lo msmo que antes, el parámetro C 3 se dejó fjo en 1 y se usó tambén 1 para el parámetro C de SVM. Como conjunto de test consderamos una grlla de puntos dentro del msmo rectángulo que los datos de entrenamento. A cada punto de test se lo clasfcó con el hperplano asocado a su vecno más próxmo dentro del dataset orgnal usado para aprendzaje del clasfcador. 1486

12 En las fguras 6-9 se muestran los resultados obtendos sobre el conjunto de test para valores de de 10 3, 10 4, y respectvamente. Como era esperable, para grande la frontera de decsón obtenda es muy smlar a la que producría el SVM estaconaro con kernel lneal. Fgura 6. Dataset 3. Resultados para = Tambén se compararon los resultados con los obtendos con SVM con kernel gausano. El reportado en el cuadro 1 es el mejor que se pudo consegur varando el parámetro γ de la gausana y dejando el parámetro C fjo en 1. Cuadro 1. Errores de test para el dataset 3. Prueba Error ( %) = ,61 = 10 4,1 = ,81 = ,17 SVM lneal 5,73 SVM gausano (γ =,94),37 Como puede verse en la tabla, nuestro método supera al resultado óptmo de SVM con kernel gausano, aunque los resultados tenen que consderarse prelmnares dado que para nnguno de los dos métodos se realzó un ajuste exhaustvo de los parámetros. 1487

13 Fgura 7. Dataset 3. Resultados para = Fgura 8. Dataset 3. Resultados para =

14 Fgura 9. Dataset 3. Resultados para = Bases de Datos Reales De los dos prmeros ejemplos sntétcos consderados en la seccón anteror surge claramente la capacdad del algortmo propuesto para resolver problemas de clasfcacón adaptatva. Ello no es sorprendente en tanto el método fue específcamente dseñado tenendo en mente este tpo de aplcacones. Es destacable, en cambo, que el msmo permta resolver problemas de clasfcacón estándar con precsón comparable a la de SVM no lneal (Kernel SVM), tal como surge del análss del tercer dataset consderado prevamente. Para explorar más en detalle esta capacdad, se probó el método propuesto en un problema real. Para ello se usó el dataset breast cancer del IDA repostory [5]. Al gual que en [6], se consderaron 100 dvsones de los datos para entrenamento y test (00 para el entrenamento y 77 para test). Para selecconar los parámetros del método se hzo en cada una de las 100 pruebas una valdacón cruzada con 10 folds. Se probó varar el parámetro en {10, 10, 10 3, , 10 4, } y el número de vecnos usados en {3, 4, 5, 7, 10, 15, 0, 5}. En el cuadro se muestra el mejor resultado obtendo y el reportado en [6]: 1 Cuadro. Errores de test para el dataset breast cancer. Prueba Error ( %) Nuestro Método 7,0 ± 5,7 SVM 6,0 ± 4,7 1 En [6] el σ reportado para SVM es de 0,47, mentras que en el resumen en [5] fgura 4,

15 La pequeña dferenca en los promedos de error, que favorece al mejor resultado obtendo con SVM convenconal, no es sgnfcatva dada la gran dspersón observada en dchos promedos. Es decr, nuevamente aquí, sobre un problema real, se obtene que SVM adaptatvo es comparable a SVM con kernel gausano. Esta capacdad del método propuesto consttuye un mportante valor agregado del msmo, ya que permte generar un clasfcador no lneal en el espaco de característcas orgnal, ndependzándonos de la eleccón de un mapa a un espaco de mayor dmensón (a través del kernel utlzado). 5. CONCLUSIONES En el presente trabajo hemos propuesto un nuevo método de generacón de clasfcadores adaptatvos, capaces de aprender conceptos que mutan con el tempo. La dea se ejemplfcó desarrollando en detalle una versón local del clasfcador SVM, que permte recuperar la evolucón temporal de un problema de clasfcacón smple. La dea básca consste en usar múltples hperplanos váldos en pequeñas localdades temporales (ventanas) para realzar la clasfcacón pero, a dferenca de otras propuestas de este tpo, realzando un aprendzaje de todos los hperplanos en forma global. Para ello se mnmza una cantdad que contene al error que comete la famla de clasfcadores locales más una medda asocada a la dmensón de VC de los msmos. Por otro lado, la msma dea aplcada a localdades en el espaco de característcas del problema de clasfcacón permte obtener resultados comparables a los que proporcona SVM con kernel gausano. Los resultados presentados son prelmnares y requeren aún una expermentacón más exhaustva para establecer ventajas y desventajas del método propuesto. No obstante, al menos para sstemas no estaconaros, los msmos son lo sufcentemente prometedores como para ser optmsta en cuanto a la aplcacón de esta técnca a problemas reales en sstemas que mutan lentamente. Referencas 1. R. Klnkenberg, T. Joachms, Detectng Concept Drft wth Support Vector Machnes, Proceedngs of ICML-00, 17th Internatonal Conference on Machne Learnng (000). Renato Vcente, Osame Knouch, and Nestor Catcha, Statstcal Mechancs of Onlne Learnng of Drftng Concepts: A Varatonal Approach, Machne Learnng 3, (1998) 3. N. Crstann and J. Shawe-Taylor, An Introducton to Support Vector Machnes, Cambrdge Unversty Press, Cambrdge (000) 4. V. Vapnk, Statstcal Learnng Theory, Wley (1998) 5. IDA Benchmark repostory used n several boostng, KFD and SVM papers 6. K. R. Müller, S. Mka, G. Rätsch, K. Tsuda, B. Schölkopf, An Introducton to Kernel-Based Learnng Algorthms, IEEE Transactons on Neural Networks 1, No. (001) 1490

Sitemap