master thesis presentation
DESCRIPTION
My master thesis presentation on 2008-09-29TRANSCRIPT
Aproximaciones a S3VM multiclaseMaster en tecnologıas del lenguaje en la web
Arkaitz Zubiaga Mendialdua
UNED
29 de septiembre de 2008
Director: Vıctor Fresno Fernandez
Clasificacion automatica de textos
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 2 / 43
Clasificacion automatica de textos
¿Que es?
Se dispone de una coleccion de documentos:
D = {d1, ..., d|D|}
Y una serie de categorıas predefinidas:
C = {c1, ..., c|C |}
La clasificacion se define como:
〈dj , ci 〉 ∈ D × C
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 3 / 43
Clasificacion automatica de textos
¿Que es?
Se dispone de una coleccion de documentos:
D = {d1, ..., d|D|}
Y una serie de categorıas predefinidas:
C = {c1, ..., c|C |}
La clasificacion se define como:
〈dj , ci 〉 ∈ D × C
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 3 / 43
Clasificacion automatica de textos
¿Que es?
Se dispone de una coleccion de documentos:
D = {d1, ..., d|D|}
Y una serie de categorıas predefinidas:
C = {c1, ..., c|C |}
La clasificacion se define como:
〈dj , ci 〉 ∈ D × C
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 3 / 43
Clasificacion automatica de textos
Caracterısticas
Aprendizaje automatico
Aprendizaje supervisadoAprendizaje semisupervisado
Taxonomıa
BinariaMulticlase
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 4 / 43
Clasificacion automatica de textos
Caracterısticas
Aprendizaje automatico
Aprendizaje supervisadoAprendizaje semisupervisado
Taxonomıa
BinariaMulticlase
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 4 / 43
Motivacion
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 5 / 43
Motivacion
Motivacion
Muchos estudios para clasificacion de texto plano (noticias), peromenos sobre paginas web.
Problema tıpico de clasificacion de paginas web
Semisupervisado: pocos documentos etiquetados respecto a lacoleccion a clasificar.Multiclase: taxonomıa mayor que 2.
Tecnica de clasificacion escogida: SVM.
Problema: Poco trabajo para SVM semisupervisado multiclaseNecesidad de nuevas propuestas para resolver el problema planteado
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 6 / 43
Motivacion
Motivacion
Muchos estudios para clasificacion de texto plano (noticias), peromenos sobre paginas web.
Problema tıpico de clasificacion de paginas web
Semisupervisado: pocos documentos etiquetados respecto a lacoleccion a clasificar.Multiclase: taxonomıa mayor que 2.
Tecnica de clasificacion escogida: SVM.
Problema: Poco trabajo para SVM semisupervisado multiclaseNecesidad de nuevas propuestas para resolver el problema planteado
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 6 / 43
Motivacion
Motivacion
Muchos estudios para clasificacion de texto plano (noticias), peromenos sobre paginas web.
Problema tıpico de clasificacion de paginas web
Semisupervisado: pocos documentos etiquetados respecto a lacoleccion a clasificar.Multiclase: taxonomıa mayor que 2.
Tecnica de clasificacion escogida: SVM.
Problema: Poco trabajo para SVM semisupervisado multiclaseNecesidad de nuevas propuestas para resolver el problema planteado
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 6 / 43
Motivacion
Motivacion
Muchos estudios para clasificacion de texto plano (noticias), peromenos sobre paginas web.
Problema tıpico de clasificacion de paginas web
Semisupervisado: pocos documentos etiquetados respecto a lacoleccion a clasificar.Multiclase: taxonomıa mayor que 2.
Tecnica de clasificacion escogida: SVM.
Problema: Poco trabajo para SVM semisupervisado multiclase
Necesidad de nuevas propuestas para resolver el problema planteado
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 6 / 43
Motivacion
Motivacion
Muchos estudios para clasificacion de texto plano (noticias), peromenos sobre paginas web.
Problema tıpico de clasificacion de paginas web
Semisupervisado: pocos documentos etiquetados respecto a lacoleccion a clasificar.Multiclase: taxonomıa mayor que 2.
Tecnica de clasificacion escogida: SVM.
Problema: Poco trabajo para SVM semisupervisado multiclaseNecesidad de nuevas propuestas para resolver el problema planteado
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 6 / 43
¿Por que SVM?
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 7 / 43
¿Por que SVM?
¿Por que SVM?
Muchos estudios recientes: Bolelli et al. (2007); Bordes et al. (2007);Sun et al. (2007); Wang et al. (2007a,b); Zien et al. (2007);Heymann et al. (2008)).
Mejores resultados que otras tecnicas para clasificacion de textos.
La utilizacion de un kernel facilita la tarea de clasificacion para zonasdisjuntas.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 8 / 43
¿Por que SVM?
Comparativa con otras tecnicas
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 9 / 43
¿Por que SVM?
Comparativa con otras tecnicas
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 10 / 43
¿Por que SVM?
Comparativa con otras tecnicas
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 11 / 43
SVM
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 12 / 43
SVM
SVM
Modelo espacio vectorial
Busqueda de hiperplano de separacion
Maximizacion de margen
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 13 / 43
SVM
SVM
Modelo espacio vectorial
Busqueda de hiperplano de separacion
Maximizacion de margen
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 13 / 43
SVM
SVM
Modelo espacio vectorial
Busqueda de hiperplano de separacion
Maximizacion de margen
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 13 / 43
SVM
SVM
Modelo espacio vectorial
Busqueda de hiperplano de separacion
Maximizacion de margen
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 13 / 43
SVM
SVM
Funcion de optimizacion: f (x) = ω · x + b
Problema: Dificil de computar.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 14 / 43
SVM
SVM
Funcion de optimizacion: f (x) = ω · x + b
Problema: Dificil de computar.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 14 / 43
SVM
SVM
Funcion de optimizacion: f (x) = ω · x + b
Problema: Dificil de computar.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 14 / 43
SVM
SVM
Se utiliza funcion equivalente:
min1
2||ω||2 + C ·
n∑i=1
ξdi
Sujeto a: yi (ω · xi + b) ≥ 1− ξi , ξi ≥ 0
Utilizacion de funcion de kernel para casos no lineales.
Unicamente resuelve problemas binarios y supervisados.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 15 / 43
SVM
SVM
Se utiliza funcion equivalente:
min1
2||ω||2 + C ·
n∑i=1
ξdi
Sujeto a: yi (ω · xi + b) ≥ 1− ξi , ξi ≥ 0
Utilizacion de funcion de kernel para casos no lineales.
Unicamente resuelve problemas binarios y supervisados.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 15 / 43
SVM
SVM
Se utiliza funcion equivalente:
min1
2||ω||2 + C ·
n∑i=1
ξdi
Sujeto a: yi (ω · xi + b) ≥ 1− ξi , ξi ≥ 0
Utilizacion de funcion de kernel para casos no lineales.
Unicamente resuelve problemas binarios y supervisados.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 15 / 43
SVM multiclase
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 16 / 43
SVM multiclase
SVM multiclase
Aproximaciones a SVM multiclase:
Directa.
Combinacion de binarios.
One-against-one.One-against-all.
Se ha trabajado con colecciones supervisadas, pero apenas consemisupervisadas.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 17 / 43
SVM multiclase
SVM multiclase
Aproximaciones a SVM multiclase:
Directa.Combinacion de binarios.
One-against-one.One-against-all.
Se ha trabajado con colecciones supervisadas, pero apenas consemisupervisadas.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 17 / 43
SVM multiclase
SVM multiclase
Aproximaciones a SVM multiclase:
Directa.Combinacion de binarios.
One-against-one.One-against-all.
Se ha trabajado con colecciones supervisadas, pero apenas consemisupervisadas.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 17 / 43
SVM multiclase
SVM multiclase: Aproximacion directa
La funcion de optimizacion tiene en cuenta todos los hiperplanos.
mın1
2
n∑m=1
||wm||2 + Cl∑
i=1
∑m 6=yi
ξmi
Sujeto a:wyi · xi + byi ≥ wm · xi + bm + 2− ξmi , ξmi ≥ 0
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 18 / 43
SVM multiclase
SVM multiclase: Aproximacion directa
La funcion de optimizacion tiene en cuenta todos los hiperplanos.
mın1
2
n∑m=1
||wm||2 + Cl∑
i=1
∑m 6=yi
ξmi
Sujeto a:wyi · xi + byi ≥ wm · xi + bm + 2− ξmi , ξmi ≥ 0
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 18 / 43
SVM multiclase
SVM multiclase: One-against-one
Construye k·(k−1)2 clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 19 / 43
SVM multiclase
SVM multiclase: One-against-one
Construye k·(k−1)2 clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 19 / 43
SVM multiclase
SVM multiclase: One-against-one
Construye k·(k−1)2 clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 19 / 43
SVM multiclase
SVM multiclase: One-against-one
Construye k·(k−1)2 clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 19 / 43
SVM multiclase
SVM multiclase: One-against-one
Construye k·(k−1)2 clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 19 / 43
SVM multiclase
SVM multiclase: One-against-one
Construye k·(k−1)2 clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 19 / 43
SVM multiclase
SVM multiclase: One-against-one
Construye k·(k−1)2 clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 19 / 43
SVM multiclase
SVM multiclase: One-against-one
Construye k·(k−1)2 clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 19 / 43
SVM multiclase
SVM multiclase: One-against-one
Construye k·(k−1)2 clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 19 / 43
SVM multiclase
SVM multiclase: One-against-one
Construye k·(k−1)2 clasificadores binarios
sign(ωTij · x + bij) −→ Sumar un voto a clase positiva entre i y j
La clase con mas votos es la que el sistema predice.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 19 / 43
SVM multiclase
SVM multiclase: One-against-all
Construye k clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 20 / 43
SVM multiclase
SVM multiclase: One-against-all
Construye k clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 20 / 43
SVM multiclase
SVM multiclase: One-against-all
Construye k clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 20 / 43
SVM multiclase
SVM multiclase: One-against-all
Construye k clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 20 / 43
SVM multiclase
SVM multiclase: One-against-all
Construye k clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 20 / 43
SVM multiclase
SVM multiclase: One-against-all
Construye k clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 20 / 43
SVM multiclase
SVM multiclase: One-against-all
Construye k clasificadores binarios
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 20 / 43
SVM multiclase
SVM multiclase: One-against-all
Construye k clasificadores binarios
Ci = arg maxi=1,...,k
(ωi · x + bi )
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 20 / 43
S3VM
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 21 / 43
S3VM
SVM semisupervisado (S3VM)
Utilizacion de documentos no etiquetados en fase de aprendizaje.
Se anade un termino adicional a la funcion de optimizacion:
mın1
2· ||ω||2 + C ·
l∑i=1
ξdi + C ∗ ·u∑
j=1
ξ∗d
j
Problema: se representa mediante una funcion no convexa.
Soluciones de optimizacion convexa.
Utilizado sobre taxonomıas binarias, pero apenas en entornosmulticlase.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 22 / 43
S3VM
SVM semisupervisado (S3VM)
Utilizacion de documentos no etiquetados en fase de aprendizaje.
Se anade un termino adicional a la funcion de optimizacion:
mın1
2· ||ω||2 + C ·
l∑i=1
ξdi + C ∗ ·u∑
j=1
ξ∗d
j
Problema: se representa mediante una funcion no convexa.
Soluciones de optimizacion convexa.
Utilizado sobre taxonomıas binarias, pero apenas en entornosmulticlase.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 22 / 43
S3VM
SVM semisupervisado (S3VM)
Utilizacion de documentos no etiquetados en fase de aprendizaje.
Se anade un termino adicional a la funcion de optimizacion:
mın1
2· ||ω||2 + C ·
l∑i=1
ξdi
+ C ∗ ·u∑
j=1
ξ∗d
j
Problema: se representa mediante una funcion no convexa.
Soluciones de optimizacion convexa.
Utilizado sobre taxonomıas binarias, pero apenas en entornosmulticlase.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 22 / 43
S3VM
SVM semisupervisado (S3VM)
Utilizacion de documentos no etiquetados en fase de aprendizaje.
Se anade un termino adicional a la funcion de optimizacion:
mın1
2· ||ω||2 + C ·
l∑i=1
ξdi + C ∗ ·u∑
j=1
ξ∗d
j
Problema: se representa mediante una funcion no convexa.
Soluciones de optimizacion convexa.
Utilizado sobre taxonomıas binarias, pero apenas en entornosmulticlase.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 22 / 43
S3VM
SVM semisupervisado (S3VM)
Utilizacion de documentos no etiquetados en fase de aprendizaje.
Se anade un termino adicional a la funcion de optimizacion:
mın1
2· ||ω||2 + C ·
l∑i=1
ξdi + C ∗ ·u∑
j=1
ξ∗d
j
Problema: se representa mediante una funcion no convexa.
Soluciones de optimizacion convexa.
Utilizado sobre taxonomıas binarias, pero apenas en entornosmulticlase.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 22 / 43
S3VM
SVM semisupervisado (S3VM)
Utilizacion de documentos no etiquetados en fase de aprendizaje.
Se anade un termino adicional a la funcion de optimizacion:
mın1
2· ||ω||2 + C ·
l∑i=1
ξdi + C ∗ ·u∑
j=1
ξ∗d
j
Problema: se representa mediante una funcion no convexa.
Soluciones de optimizacion convexa.
Utilizado sobre taxonomıas binarias, pero apenas en entornosmulticlase.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 22 / 43
S3VM
SVM semisupervisado (S3VM)
Utilizacion de documentos no etiquetados en fase de aprendizaje.
Se anade un termino adicional a la funcion de optimizacion:
mın1
2· ||ω||2 + C ·
l∑i=1
ξdi + C ∗ ·u∑
j=1
ξ∗d
j
Problema: se representa mediante una funcion no convexa.
Soluciones de optimizacion convexa.
Utilizado sobre taxonomıas binarias, pero apenas en entornosmulticlase.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 22 / 43
S3VM
SVM vs S3VM
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 23 / 43
S3VM
SVM vs S3VM
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 23 / 43
S3VM
SVM vs S3VM
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 23 / 43
S3VM
SVM vs S3VM
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 23 / 43
S3VM
SVM vs S3VM
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 23 / 43
S3VM multiclase
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 24 / 43
S3VM multiclase
S3VM multiclase
Unica referencia hasta el momento (Yajima y Kuo, 2006):
mın(1
2
h∑i=1
βiT K−1βi + Cl∑
j=1
∑i 6=yj
max(0, 1− (βyj
j − βij ))2)
donde β representa el producto entre un vector de variables y una matrizde kernel definidas por el autor.
Su optimizacion puede resultar costosa, por lo que conviene estudiarnuevas aproximaciones.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 25 / 43
S3VM multiclase
S3VM multiclase
Unica referencia hasta el momento (Yajima y Kuo, 2006):
mın(1
2
h∑i=1
βiT K−1βi + Cl∑
j=1
∑i 6=yj
max(0, 1− (βyj
j − βij ))2)
donde β representa el producto entre un vector de variables y una matrizde kernel definidas por el autor.
Su optimizacion puede resultar costosa, por lo que conviene estudiarnuevas aproximaciones.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 25 / 43
S3VM multiclase
S3VM multiclase
Unica referencia hasta el momento (Yajima y Kuo, 2006):
mın(1
2
h∑i=1
βiT K−1βi + Cl∑
j=1
∑i 6=yj
max(0, 1− (βyj
j − βij ))2)
donde β representa el producto entre un vector de variables y una matrizde kernel definidas por el autor.
Su optimizacion puede resultar costosa, por lo que conviene estudiarnuevas aproximaciones.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 25 / 43
Alternativas para S3VM multiclase
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 26 / 43
Alternativas para S3VM multiclase
Alternativas para S3VM multiclase
One-against-all-S3VM: No aplicado sobre semisupervisado.
One-against-one-S3VM: No aplicado sobre semisupervisado.
¿Posible existencia de ruido al no poder seleccionar los debidosdocumentos no etiquetados?
Nuevas propuestas:
All-against-all-S3VM.2-steps-SVM.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 27 / 43
Alternativas para S3VM multiclase
Alternativas para S3VM multiclase: all-against-all-S3VM
Construye 2k−1 − 1 clasificadores binarios.
Para un ejemplo con 4 clases:
1 vs 2-3-41-2 vs 3-41-3 vs 2-41-4 vs 2-31-2-3 vs 41-2-4 vs 31-3-4 vs 2
sign(ωTij · x + bij) −→ Sumar margen resultante a clases del lado
positivo.
El sistema presenta como prediccion aquella clase con mayorpuntuacion.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 28 / 43
Alternativas para S3VM multiclase
Alternativas para S3VM multiclase: 2-steps-SVM
Se aplican 2 pasos de aprendizaje supervisado multiclase:
1 Aprendizaje sobre coleccion de entrenamiento: se aprende con losdocumentos etiquetados, prediciendo los no etiquetados.
121...300...0
2 Clasificacion de la coleccion de test: con la coleccion de entrenamientoetiquetada, se basa el aprendizaje en ella, clasificando la coleccion detest.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 29 / 43
Alternativas para S3VM multiclase
Alternativas para S3VM multiclase: 2-steps-SVM
Se aplican 2 pasos de aprendizaje supervisado multiclase:1 Aprendizaje sobre coleccion de entrenamiento: se aprende con los
documentos etiquetados, prediciendo los no etiquetados.
121...300...0
2 Clasificacion de la coleccion de test: con la coleccion de entrenamientoetiquetada, se basa el aprendizaje en ella, clasificando la coleccion detest.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 29 / 43
Alternativas para S3VM multiclase
Alternativas para S3VM multiclase: 2-steps-SVM
Se aplican 2 pasos de aprendizaje supervisado multiclase:1 Aprendizaje sobre coleccion de entrenamiento: se aprende con los
documentos etiquetados, prediciendo los no etiquetados.
1 −→ 12 −→ 21 −→ 1...3 −→ 30 −→ 30 −→ 2...0 −→ 1
2 Clasificacion de la coleccion de test: con la coleccion de entrenamientoetiquetada, se basa el aprendizaje en ella, clasificando la coleccion detest.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 29 / 43
Alternativas para S3VM multiclase
Alternativas para S3VM multiclase: 2-steps-SVM
Se aplican 2 pasos de aprendizaje supervisado multiclase:1 Aprendizaje sobre coleccion de entrenamiento: se aprende con los
documentos etiquetados, prediciendo los no etiquetados.
1 −→ 12 −→ 21 −→ 1...3 −→ 30 −→ 30 −→ 2...0 −→ 1
2 Clasificacion de la coleccion de test: con la coleccion de entrenamientoetiquetada, se basa el aprendizaje en ella, clasificando la coleccion detest.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 29 / 43
Experimentacion
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 30 / 43
Experimentacion
Experimentacion: colecciones
Colecciones utilizadas:
BankSearch: 10.000 documentos web / 10 categorıas (4.000entrenamiento).
WebKB: 4.518 documentos web / 6 categorıas (2.000 entrenamiento).Yahoo! Science: 788 documentos web / 6 categorıas (200entrenamiento).
Versiones con diferentes fracciones etiquetadas / no etiquetadas.
9 ejecuciones para cada una de las versiones.
Representacion: tf-idf.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 31 / 43
Experimentacion
Experimentacion: colecciones
Colecciones utilizadas:
BankSearch: 10.000 documentos web / 10 categorıas (4.000entrenamiento).WebKB: 4.518 documentos web / 6 categorıas (2.000 entrenamiento).
Yahoo! Science: 788 documentos web / 6 categorıas (200entrenamiento).
Versiones con diferentes fracciones etiquetadas / no etiquetadas.
9 ejecuciones para cada una de las versiones.
Representacion: tf-idf.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 31 / 43
Experimentacion
Experimentacion: colecciones
Colecciones utilizadas:
BankSearch: 10.000 documentos web / 10 categorıas (4.000entrenamiento).WebKB: 4.518 documentos web / 6 categorıas (2.000 entrenamiento).Yahoo! Science: 788 documentos web / 6 categorıas (200entrenamiento).
Versiones con diferentes fracciones etiquetadas / no etiquetadas.
9 ejecuciones para cada una de las versiones.
Representacion: tf-idf.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 31 / 43
Experimentacion
Experimentacion: colecciones
Colecciones utilizadas:
BankSearch: 10.000 documentos web / 10 categorıas (4.000entrenamiento).WebKB: 4.518 documentos web / 6 categorıas (2.000 entrenamiento).Yahoo! Science: 788 documentos web / 6 categorıas (200entrenamiento).
Versiones con diferentes fracciones etiquetadas / no etiquetadas.
9 ejecuciones para cada una de las versiones.
Representacion: tf-idf.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 31 / 43
Experimentacion
Experimentacion: colecciones
Colecciones utilizadas:
BankSearch: 10.000 documentos web / 10 categorıas (4.000entrenamiento).WebKB: 4.518 documentos web / 6 categorıas (2.000 entrenamiento).Yahoo! Science: 788 documentos web / 6 categorıas (200entrenamiento).
Versiones con diferentes fracciones etiquetadas / no etiquetadas.
9 ejecuciones para cada una de las versiones.
Representacion: tf-idf.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 31 / 43
Experimentacion
Experimentacion: colecciones
Colecciones utilizadas:
BankSearch: 10.000 documentos web / 10 categorıas (4.000entrenamiento).WebKB: 4.518 documentos web / 6 categorıas (2.000 entrenamiento).Yahoo! Science: 788 documentos web / 6 categorıas (200entrenamiento).
Versiones con diferentes fracciones etiquetadas / no etiquetadas.
9 ejecuciones para cada una de las versiones.
Representacion: tf-idf.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 31 / 43
Experimentacion
Experimentacion: implementacion
Software utilizado:
SVM-light (http://svmlight.joachims.org)SVM-multiclass
2-steps-SVM =⇒ 1 step-SVM
Ignorar documentos no etiquetados, ¿empeora los resultados?
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 32 / 43
Experimentacion
Experimentacion: implementacion
Software utilizado:
SVM-light (http://svmlight.joachims.org)SVM-multiclass
2-steps-SVM =⇒ 1 step-SVM
Ignorar documentos no etiquetados, ¿empeora los resultados?
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 32 / 43
Experimentacion
Experimentacion: evaluacion
Acierto (accuracy): % del numero de predicciones correctas sobre eltotal de documentos testeados.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 33 / 43
Resultados
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 34 / 43
Resultados
Resultados: BankSearch
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 35 / 43
Resultados
Resultados: WebKB
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 36 / 43
Resultados
Resultados: Yahoo! Science
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 37 / 43
Resultados
Resultados
Mejores resultados para combinacion de supervisados multiclase:2-steps-SVM y 1-step-SVM.
De las combinaciones binarias, destaca all-against-all-S3VM, mientrasque one-against-one-S3VM demuestra que el ruido previsto existe.
1-step-SVM muestra resultados similares que 2-steps-SVM, exceptoen WebKB, que gana; esa coleccion es mas homogenea.
Se mantiene el ranking de los algoritmos.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 38 / 43
Resultados
Resultados
Mejores resultados para combinacion de supervisados multiclase:2-steps-SVM y 1-step-SVM.
De las combinaciones binarias, destaca all-against-all-S3VM, mientrasque one-against-one-S3VM demuestra que el ruido previsto existe.
1-step-SVM muestra resultados similares que 2-steps-SVM, exceptoen WebKB, que gana; esa coleccion es mas homogenea.
Se mantiene el ranking de los algoritmos.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 38 / 43
Resultados
Resultados
Mejores resultados para combinacion de supervisados multiclase:2-steps-SVM y 1-step-SVM.
De las combinaciones binarias, destaca all-against-all-S3VM, mientrasque one-against-one-S3VM demuestra que el ruido previsto existe.
1-step-SVM muestra resultados similares que 2-steps-SVM, exceptoen WebKB, que gana; esa coleccion es mas homogenea.
Se mantiene el ranking de los algoritmos.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 38 / 43
Resultados
Resultados
Mejores resultados para combinacion de supervisados multiclase:2-steps-SVM y 1-step-SVM.
De las combinaciones binarias, destaca all-against-all-S3VM, mientrasque one-against-one-S3VM demuestra que el ruido previsto existe.
1-step-SVM muestra resultados similares que 2-steps-SVM, exceptoen WebKB, que gana; esa coleccion es mas homogenea.
Se mantiene el ranking de los algoritmos.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 38 / 43
Conclusiones y trabajo futuro
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 39 / 43
Conclusiones y trabajo futuro
Conclusiones
Se han comparado aproximaciones a S3VM multiclase paraclasificacion de paginas web:
Trasladando one-against-one y one-against-all al entornosemisupervisado.Presentando los metodos 2-steps-SVM y all-against-all-S3VM.
Se ha evaluado la aportacion de los documentos no etiquetados en elaprendizaje.
Los mejores resultados han sido para las combinaciones declasificadores supervisados multiclase.
La utilizacion de documentos no etiquetados no ha aportado mucho.
Esta aportacion ha sido algo mayor para colecciones homogeneas.
Entre las combinaciones de semisupervisados binarios,all-against-all-S3VM ha mostrado una gran efectividad, aunque sueficiencia debe mejorar.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 40 / 43
Conclusiones y trabajo futuro
Conclusiones
Se han comparado aproximaciones a S3VM multiclase paraclasificacion de paginas web:
Trasladando one-against-one y one-against-all al entornosemisupervisado.Presentando los metodos 2-steps-SVM y all-against-all-S3VM.
Se ha evaluado la aportacion de los documentos no etiquetados en elaprendizaje.
Los mejores resultados han sido para las combinaciones declasificadores supervisados multiclase.
La utilizacion de documentos no etiquetados no ha aportado mucho.
Esta aportacion ha sido algo mayor para colecciones homogeneas.
Entre las combinaciones de semisupervisados binarios,all-against-all-S3VM ha mostrado una gran efectividad, aunque sueficiencia debe mejorar.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 40 / 43
Conclusiones y trabajo futuro
Conclusiones
Se han comparado aproximaciones a S3VM multiclase paraclasificacion de paginas web:
Trasladando one-against-one y one-against-all al entornosemisupervisado.Presentando los metodos 2-steps-SVM y all-against-all-S3VM.
Se ha evaluado la aportacion de los documentos no etiquetados en elaprendizaje.
Los mejores resultados han sido para las combinaciones declasificadores supervisados multiclase.
La utilizacion de documentos no etiquetados no ha aportado mucho.
Esta aportacion ha sido algo mayor para colecciones homogeneas.
Entre las combinaciones de semisupervisados binarios,all-against-all-S3VM ha mostrado una gran efectividad, aunque sueficiencia debe mejorar.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 40 / 43
Conclusiones y trabajo futuro
Conclusiones
Se han comparado aproximaciones a S3VM multiclase paraclasificacion de paginas web:
Trasladando one-against-one y one-against-all al entornosemisupervisado.Presentando los metodos 2-steps-SVM y all-against-all-S3VM.
Se ha evaluado la aportacion de los documentos no etiquetados en elaprendizaje.
Los mejores resultados han sido para las combinaciones declasificadores supervisados multiclase.
La utilizacion de documentos no etiquetados no ha aportado mucho.
Esta aportacion ha sido algo mayor para colecciones homogeneas.
Entre las combinaciones de semisupervisados binarios,all-against-all-S3VM ha mostrado una gran efectividad, aunque sueficiencia debe mejorar.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 40 / 43
Conclusiones y trabajo futuro
Trabajo futuro
Anadir el metodo S3VM multiclase directo al estudio.
Aplicacion de diferentes metodos de representacion, aprovechando lascaracterısticas propias de las paginas web (etiquetado HTML, etc.).
Optimizar el rendimiento de la tecnica all-against-all-S3VM.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 41 / 43
Conclusiones y trabajo futuro
Trabajo futuro
Anadir el metodo S3VM multiclase directo al estudio.
Aplicacion de diferentes metodos de representacion, aprovechando lascaracterısticas propias de las paginas web (etiquetado HTML, etc.).
Optimizar el rendimiento de la tecnica all-against-all-S3VM.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 41 / 43
Conclusiones y trabajo futuro
Trabajo futuro
Anadir el metodo S3VM multiclase directo al estudio.
Aplicacion de diferentes metodos de representacion, aprovechando lascaracterısticas propias de las paginas web (etiquetado HTML, etc.).
Optimizar el rendimiento de la tecnica all-against-all-S3VM.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 41 / 43
Referencias
Indice
1 Clasificacion automatica de textos
2 Motivacion
3 ¿Por que SVM?
4 SVM
5 SVM multiclase
6 S3VM
7 S3VM multiclase
8 Alternativas para S3VM multiclase
9 Experimentacion
10 Resultados
11 Conclusiones y trabajo futuro
12 Referencias y trabajo futuro
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 42 / 43
Referencias
Referencias
T. Joachims. 2002. Learning to Classify Text using Support VectorMachines. Kluwer/Springer.
X. Qi y B.D. Davison. 2007. Web Page Classification: Features andAlgorithms. Informe Tecnico LU-CSE-07-010.
F. Sebastiani. 2002. Machine Learning in Automated TextCategorization. ACM Computing Surveys, pp. 1-47.
J. Weston y C. Watkins. 1999. Multi-class Support Vector Machines.Proceedings of ESAAN, the European Symposium on Artificial NeuralNetworks.
Y. Yajima y T.-F. Kuo. 2006. Optimization Approaches forSemi-Supervised Multiclass Classification. Proceedings of ICDMW’06,the 6th International Conference on Data Mining.
Arkaitz Zubiaga Mendialdua (UNED) Aproximaciones a S3VM multiclase 29 de septiembre de 2008 43 / 43