Classifying documents by language

Alfredo Flores Hernandez 1, Cesar Charalla Mesahuanca 2, Luis Callehuanca Vergara 3, Davis Garcı́a
Fernandez 4, Luis Flores Luyo 5

Facultad de Ciencias, Universidad Nacional de Ingenierı́a 1, 2, 3, 4, 5

Resumen
En el presente trabajo, usaremos la teorı́a de hiperplanos de separación para poder darle
una forma aplicativa al tratar de clasificar documentos por el lenguaje en el cual se encuentren
escritos: Construyendo un algoritmo que nos pueda predecir si un artı́culo está escrito en inglés
u holandes. Primero daremos una introducción a la importancia de machine learning como
fuente de funcionamiento de nuestro programa para luego definir la construccion del mismo
basados en las propiedades que tiene un hiperplano separador, buscaremos un clasificador en
base a datos conocidos para luego poder aplicarlo en la predicción del idioma de cualquier
documento solo sabiendo ciertas caracterı́sticas del mismo en particular.

Palabras Claves: Hiperplanos de separacion, Optimizacion lineal, Machine Learning, Conjunto de

aprendizaje, Conjunto de validación.

Abstract

In the present work, we will use the theory of separation hyperplanes to give it an applicative
form when trying to classify documents by the language in which they are written: Building an
algorithm that can predict whether an article is written in English or Dutch. First we will give
an introduction to the importance of machine learning as a source of operation of our program
and then define its construction based on the properties that a separating hyperplane has, we
will look for a classifier based on known data and then be able to apply it in the prediction of
the language of any document only knowing certain characteristics of it in particular.

Keywords: Keywords: Separation hyperplanes, Linear optimization, Machine Learning, Learning set,
Validation set.

1 Introducción
Machine learning es una rama de la inteligencia artificial que se ocupa de algoritmos que identifican
(aprenden) relaciones complejas en datos empı́ricos. Estas relaciones se pueden utilizar para realizar
predicciones basadas en datos nuevos. Las aplicaciones del aprendizaje automático incluyen detección de
correo electrónico no deseado, reconocimiento facial, reconocimiento de voz, clasificación de páginas web
en motores de búsqueda de Internet, procesamiento del lenguaje natural, diagnóstico médico basado en los
sı́ntomas de los pacientes, detección de fraude para tarjetas de crédito, control de robots y juegos como
ajedrez y backgammom.

Un impulso importante detrás del desarrollo de algoritmos de machine learning ha sido la comercial-
ización de Internet en las últimas dos décadas. Las grandes empresas de Internet, como los operadores de
motores de búsqueda y redes sociales, procesan grandes cantidades de datos de todo el mundo. Para dar
sentido a estos datos, se emplea una amplia gama de técnicas de aprendizaje automático.

2 Conceptos previos

2.1 Machine Learning

Machine learning es una rama de las matemáticas aplicadas y la informática que tiene como objetivo
desarrollar métodos computacionales que utilizan la experiencia en forma de datos para hacer predicciones
precisas. Por lo general, la ”experiencia” se presenta en forma de ejemplos. En general, un algoritmo de
machine learning utiliza estos ejemplos para ”aprender” sobre las relaciones entre los ejemplos. En términos
generales, existen algunos tipos diferentes pero relacionados de tales algoritmos. El presente capı́tulo trata
sobre el llamado algoritmo de clasificación. Un algoritmo de clasificación requiere un conjunto de ejemplos,
cada uno de los cuales tiene una etiqueta. Un ejemplo de un problema de clasificación es el problema al que
se enfrentan los proveedores de correo electrónico para clasificar los mensajes de correo electrónico entrantes
en spam y no spam. Los ejemplos de un problema de clasificación de este tipo serı́an varios mensajes de
correo electrónico, cada uno etiquetado como ”spam” o ”no spam”. El objetivo del algoritmo de clasificación
es encontrar una forma de predecir con precisión las etiquetas de nuevas observaciones. Las etiquetas de
los ejemplos suelen ser proporcionadas por personas. Podrı́a tratarse de alguien que mire explı́citamente los
ejemplos y los clasifique como ”spam” o ”no spam”, o los usuarios del servicio de correo electrónico podrı́an
proporcionarlo. Por ejemplo, cuando un usuario hace clic en el botón ”Marcar este mensaje como spam” en
una aplicación de correo electrónico, el mensaje en cuestión se etiqueta como ”spam” y esta información se
puede utilizar para futuras predicciones.

Otras áreas del aprendizaje automático incluyen: regresión, donde el objetivo es predecir un número
en lugar de una etiqueta (por ejemplo, el gasto fiscal basado en los ingresos, consulte también la Sección
1.6.2) ; ranking, donde el objetivo es aprender a clasificar objetos (por ejemplo, en motores de búsqueda de
Internet); agrupación, que significa determinar grupos de objetos que son similares entre sı́. En los casos
de clasificación y regresión, los ejemplos suelen tener etiquetas adjuntas, y estas etiquetas se consideran
las etiquetas ”correctas”. Entonces, el objetivo de los algoritmos es ”aprender” a predecir estas etiquetas.
A veces, estos problemas se clasifican como aprendizaje automático supervisado. Por el contrario, en la
clasificación y el agrupamiento, los ejemplos generalmente no tienen etiquetas y, por lo tanto, se clasifican
como aprendizaje automático no supervisado.[1]

El trabajo actual es un estudio de caso de un algoritmo de clasificación (supervisado). Para que un

algoritmo de clasificación sea exitoso, se determinan ciertas caracterı́sticas de los mensajes que (con suerte)
llevan conocimiento predictivo. Por ejemplo, para la clasificación de spam, puede ser útil contar la cantidad
de palabras en el mensaje que se relacionan con productos farmacéuticos, o si el mensaje de correo electrónico
está dirigido a muchos destinatarios en lugar de a un destinatario en particular. Estas caracterı́sticas son
indicativas de que el mensaje se clasifica como spam. Otras palabras, como el nombre de los amigos del
destinatario, pueden indicar que el mensaje no es spam. Las caracterı́sticas se representan como números y,
por lo tanto, las caracterı́sticas de un solo ejemplo se pueden agrupar como un vector. Por lo general, no es
una caracterı́stica en particular lo que determina la etiqueta de un ejemplo, sino más bien la combinación
de ellas. Por ejemplo, un mensaje de correo electrónico que se envı́a a muchos destinatarios diferentes y
que contiene cinco referencias a productos farmacéuticos probablemente se puede clasificar como spam,
mientras que un mensaje que tiene varios destinatarios e incluye diez de los amigos del destinatario principal
probablemente deberı́a clasificarse como no spam. Un algoritmo de clasificación intenta dar sentido a las
caracterı́sticas y etiquetas proporcionadas, y las utiliza para clasificar ejemplos nuevos sin etiquetas.

Claramente, el diseño de funciones es crucial y depende del problema en cuestión. Se deben elegir
caracterı́sticas que tengan poder predictivo y, por lo tanto, el diseño utiliza conocimientos previos sobre el
problema. En muchos casos, es posible que no quede claro de inmediato cómo elegir las funciones.

2.2 Clasificación de documentos utilizando hiperplanos de separación

En el análisis de texto automatizado, un problema básico es determinar el idioma en el que está escrito
un documento de texto dado (por ejemplo, un artı́culo de periódico o un correo electrónico). En este trabajo,
mostraremos cómo se puede utilizar la optimización lineal para clasificar documentos de texto en dos idiomas,
inglés y holandés.

Supongamos que tenemos un conjunto D (potencialmente muy grande) de documentos de texto, al-
gunos de los cuales están escritos en inglés y otros en holandés. Para cada documento d en D, calculamos m
las llamadas caracterı́sticas denotadas por f1d , ..., fm
d
. Usaremos como caracterı́sticas la frecuencia relativa
de cada letra, es decir, el número de veces que aparece cada letra dividido por el número total de letras en
el documento. Por supuesto, uno puede pensar en muchas más caracterı́sticas que pueden ser relevantes, por
ejemplo, la longitud promedio de las palabras, la frecuencia relativa de las palabras de longitud 1,2,3,... o
la frecuencia relativa de ciertas combinaciones de letras. Nos limitaremos a la frecuencia relativa de letras
individuales. Para simplificar, también trataremos las letras mayúsculas y minúsculas por igual. Entonces, en
nuestro caso tenemos que m = 26. Por lo tanto, para cada documento, construimos un vector m-dimensional
que contiene estas caracterı́sticas. Dicho vector se denomina vector caracterı́stica. Dado que tenemos |D|
documentos, tenemos |D| de estos vectores caracterı́stica m-dimensionales. Para cada documento d ∈ D, sea
fd (∈ Rm ) el vector caracterı́stica para d. Para cualquier subconjunto D0 ⊆ D, se define F (D0 ) = {fd |d ∈ D0 }.

Como ejemplo, hemos tomado 31 artı́culos de periódicos en inglés y 39 holandeses de Internet y hemos
calculado las frecuencias de las letras. La figura 1 muestra las frecuencias relativas de las 26 letras para
seis artı́culos de periódicos en inglés y seis en holandés. Las columnas de la tabla son los doce vectores
caracterı́stica correspondientes fd (d = 1, ..., 12).

Nuestro objetivo es construir una función g : Rm R, un llamado clasificador (también llamado máquina de
vectores de soporte), que, para cada documento d ∈ D, asigna al vector caracterı́stica fd un número real que
servirá como una herramienta para decidir en qué idioma se escribió el documento d. La interpretación del
valor g(fd ) es la siguiente. Para cualquier documento d ∈ D, si g(fd ) > 0, entonces concluimos que el texto
fue escrito en inglés; si g(fd ) < 0, concluimos que el texto fue escrito en holandés.

Para construir un clasificador de este tipo, asumimos que para un pequeño subconjunto de los docu-
mentos, el idioma se conoce de antemano (por ejemplo, los artı́culos han sido leı́dos y clasificados por una
persona). Dividimos este subconjunto en dos subconjuntos, L y V . El subconjunto L se denomina conjunto
de aprendizaje y se utilizará para construir un clasificador. El subconjunto V se denomina conjunto de
validación y se utilizará para comprobar que el clasificador construido a partir del conjunto de aprendizaje
predice correctamente el idioma de los documentos dados. Si el clasificador funciona satisfactoriamente para
el conjunto de validación, entonces se acepta como un clasificador válido y se puede usar para determinar el
idioma de los documentos que no están en L ∪ V (es decir, para los documentos para los que el idioma es
actualmente desconocido). Sea L1 el subconjunto de L que se sabe que está escrito en inglés y, de manera
similar, sea L2 el subconjunto de L que se sabe que está escrito en holandés. Defina V1 y V2 de forma
análoga. En nuestro ejemplo de artı́culos periodı́sticos, utilizaremos los datos de la tabla (Figura 1) como
conjunto de aprendizaje.

Restringiremos nuestra atención a los clasificadores lineales, es decir, el clasificador g está restringido a
tener la forma

m
X
g(f ) = wj fj + b para f = [f1 ...fm ]> ∈ Rm ,
j=1
 Figure 1: Frecuencias relativas de letras (en porcentajes) de varios artı́culos de periódicos.

donde w(∈ Rm \ {0}) se llama vector de peso del clasificador, b(∈ R) es la intersección y f es cualquier vector
caracterı́stica. Nótese que excluimos la posibilidad de que w = 0, porque el clasificador correspondiente no
tiene en cuenta ninguna caracterı́stica y, por lo tanto, no sirve para predecir el idioma de un documento.
Nuestro objetivo es construir un vector de peso w y una intersección b tal que:

d ∈ L1 =⇒ w > 0
(1)
d ∈ L2 =⇒ w> fd + b < 0.
Los clasificadores lineales tienen la siguiente interpretación geométrica. Para cualquier w ∈ Rm \ 0 y
b ∈ R se define el hiperplano H(w, b) = {f ∈ Rm |w> f + b = 0}, y los dos semi espacios (estrictos)
H + (w, b) = {f ∈ Rm |w> f + b < 0} y H − (w, b) = {f|w> f + b > 0} correspondiente a H(w, b)[2]. Por tanto
(Eq 11.1) es equivalente a:

F (L1 ) = {fd |d ∈ L1 } ⊆ H + (w, b)

(2)
F (L2 ) = {fd |d ∈ L2 } ⊆ H − (w, b).
Restringiremos nuestra atención a los clasificadores lineales, es decir, el clasificador g está restringido a tener
la forma
 m
X
g(f ) = wj fj + b para f = [f1 ...fm ]> ∈ Rm ,
j=1
m
donde w(∈ R \ {0}) se llama vector de peso del clasificador, b(∈ R) es la intersección y f es cualquier vector
caracterı́stica. Nótese que excluimos la posibilidad de que w = 0, porque el clasificador correspondiente no
tiene en cuenta ninguna caracterı́stica y, por lo tanto, no sirve para predecir el idioma de un documento.
Nuestro objetivo es construir un vector de peso w y una intersección b tal que:

d ∈ L1 =⇒ w> fd + b > 0
(3)
d ∈ L2 =⇒ w> fd + b < 0.
Los clasificadores lineales tienen la siguiente interpretación geométrica. Para cualquier w ∈ Rm \ 0 y
b ∈ R se define el hiperplano H(w, b) = {f ∈ Rm |w> f + b = 0}, y los dos semi espacios (estrictos)
H + (w, b) = {f ∈ Rm |w> f + b < 0} y H − (w, b) = {f|w> f + b > 0} correspondiente a H(w, b). Por tanto la
ecuación (1) es equivalente a:

F (L1 ) = {fd |d ∈ L1 } ⊆ H + (w, b)

(4)
F (L2 ) = {fd |d ∈ L2 } ⊆ H − (w, b).

Figure 2: Conjunto de aprendizaje separable con 40 documentos. Las lı́neas continuas y punteadas son
hiperplanos de separación.

Entonces, queremos construir un hiperplano en Rm tal que los vectores de caracterı́sticas correspondientes
a los documentos en L1 se encuentren en el semiespacio H + (w, b), y los vectores correspondientes a L2 en
Figure 3: Conjunto de aprendizaje no separable con 40 documentos. Las cápsulas convexas de los conjuntos
de aprendizaje se intersectan.

H − (w, b).
Si existe un vector de peso w y una intersección b tal que se satisfacen las condiciones de (2), entonces
se dice que F (L1 ) y F (L2 ) son separables; de lo contrario, se denominan no separables. El hiperplano
correspondiente H(w, b) se denomina hiperplano de separación para F (L1 ) y F (L2 ), y la función w> fd + b se
denomina separador de F (L1 ) y F (L2 ). Hacemos las siguientes observaciones

B H + (−w, −b) = H − (w, b) para w ∈ Rm \ {0}, b ∈ R

B H(λw, λb) = H(w, b) para w ∈ Rm \ {0}, b ∈ R y λ 6= 0.

B Si w y b definen un hiperplano separador para F (L1 ) y F (L2 ) tal que F (L1 ) ⊆ H + (w, b) y
F (L2 ) ⊆ H − (w, b), entonces también tenemos que conv(F (L1 )) ⊆ H + (w, b) y conv(F (L2 )) ⊆ H − (w, b); por
lo tanto, w y b también definen un hiperplano de separación para conv(F (L1 )) y conv(F (L2 )).

Tenga en cuenta que incluso para un pequeño conjunto de aprendizaje L, no está claro de antemano
si F (L1 ) y F (L2 ) son o no separables. Entonces, la primera pregunta que debe abordarse es: ¿existe un
hiperplano de separación para F (L1 ) y F (L2 )? La figura 2 muestra un ejemplo de un conjunto de aprendizaje
separable con 2 caracterı́sticas. Los cuadrados corresponden a los vectores de caracterı́sticas en F (L1 ) y
los cı́rculos a los vectores de caracterı́sticas en F (L2 ). Además, se muestran los cascos convexos de puntos
cuadrados y los puntos circulares. Las lı́neas continuas y discontinuas representan dos posibles hiperplanos.
La figura 3 muestra un conjunto de aprendizaje que no es separable.

La figura 2 ilustra otro hecho importante. Suponga que descartamos la caracterı́stica f2 y solo consid-
eramos la caracterı́stica f1 . Sea F 0 (L1 )(⊂ R1 ) y F 0 (L2 )(⊂ R1 ) los ’vectores’ de caracterı́sticas obtenidos al
descartar la caracterı́stica f2 . Entonces, los vectores en F 0 (L1 ) y F 0 (L2 ) son unidimensionales y se pueden
trazar en una lı́nea; vea la Figura 4 (Este gráfico también se puede construir moviendo todos los puntos en
la figura 2 hacia abajo sobre el eje horizontal). Un hiperplano en el espacio euclidiano unidimensional es un
punto. Por lo tanto, el conjunto de aprendizaje unidimensional es separable si y solo si existe un punto P
en la lı́nea tal que todos los vectores en F 0 (L1 ) están estrictamente a la izquierda de P , y todos los vectores
en F 0 (L2 ) están estrictamente en la derecha de P . De esta figura, está claro que tal punto no existe. Por lo
tanto, el conjunto de aprendizaje se ha vuelto inseparable.

Figure 4: El conjunto de aprendizaje de la Figura 2 después de descartar la caracterı́stica f2

Este hecho también se puede ver inmediatamente en la Figura 2 como sigue. Descartar la caracterı́stica
f2 equivale a requerir que el peso w2 asignado a f2 sea cero. Esto, a su vez, equivale a requerir que
el hiperplano separador sea ”vertical” en la figura. Claramente, no hay un hiperplano de separación
vertical para el conjunto de aprendizaje dibujado en la Figura 2. Lo mismo ocurre cuando se descarta
la caracterı́stica f1 y solo se considera f2 , lo que equivale a requerir que el hiperplano separador sea horizontal.

En general, las siguientes observaciones son válidas

B Si un conjunto de aprendizaje con un determinado conjunto de caracterı́sticas es separable, agregar

una caracterı́stica mantiene el conjunto de aprendizaje separable. Sin embargo, eliminar una función puede
hacer que el conjunto de aprendizaje no sea separable.

B Si un conjunto de aprendizaje con un determinado conjunto de caracterı́sticas no es separable, la

eliminación de una caracterı́stica mantiene el conjunto de aprendizaje inseparable. Sin embargo, agregar una
función puede hacer que el conjunto de aprendizaje sea separable.
3 Análisis y modelado del problema

3.1 Modelo LO para encontrar hiperplanos separadores

La construcción de un hiperplano de separación para el conjunto de aprendizaje L1 ∪ L2 se puede hacer
diseñando y resolviendo un modelo LO de la siguiente manera. Las variables de decisión del modelo LO serán
las entradas w1 , ..., wm del vector de peso w, y la intersección b. Dado que el valor del clasificador debe ser
estrictamente positivo si el documento d fue escrito en inglés (es decir, d ∈ L1 ), y estrictamente negativo si el
documento d fue escrito en holandés (es decir, d ∈ L2 ), tenemos las restricciones:

w> fd + b > 0 para d ∈ L1

(5)
w> fd + b < 0 para d ∈ L2 .

Debido a que estas desigualdades son desigualdades estrictas, no se pueden utilizar en un modelo LO[3]. Para
eludir esta ”limitación”, mostraremos que es suficiente utilizar las siguientes desigualdades ” ≥ ” y ” ≤ ” en
su lugar:

w> fd + b ≥ 1 para d ∈ L1
(6)
w> fd + b ≤ −1 para d ∈ L2 .

Claramente, el conjunto solución (en términos de w y b) de (4) es en general un subconjunto estricto del
conjunto solución de (3). Sin embargo, los conjuntos de hiperplanos definidos por (3) y (4) coinciden. Para
ser precisos, sea H1 = {H(w, b)|wyb satisfacen (3)}, es decir, H1 es la colección de hiperplanos definidos por
las soluciones de (3). Sea H2 = {H(w, b)|w y b satisfacen (4)}. Afirmamos que H1 = H2 . Es fácil comprobar
que H2 ⊆ H1 . Para ver que H1 ⊆ H2 , tome cualquier w y b que satisfagan (3). Entonces, debido a que L1 y
L2 son conjuntos finitos, existe  > 0 tal que w> fd + b ≥  para d ∈ L1 y w> fd + b ≤  para d ∈ L2 . Defina
ŵ = 1 w y b̂ = 1 b. Entonces, es sencillo comprobar que ŵ y b̂ satisfacen (4) y que H(ŵ, b̂) = H(w, b), como
se requiere.
De ahora en adelante, solo consideraremos las desigualdades de (4). Para cada w ∈ Rm \ {0} y b ∈ R, defina
los siguientes medios espacios:

H +1 (w, b) = {f ∈ R|w> fd + b ≥ 1}
H −1 (w, b) = {f ∈ R|w> fd + b ≤ −1}

Luego, (4) es equivalente a:

F (L1 ) ⊆ H +1 (w, b), y F (L2 ) ⊆ H −1 (w, b). (7)

Si los medios espacios H +1 (w, b) y H −1 (w, b) satisfacen las condiciones de (5), entonces el conjunto {f ∈
Rm |1 ≤ w> f + b ≤ 1} se llama separación para F (L1 ) y F (L2 ), porque ’separa’ F (L1 ) de F (L2 ). La siguiente
figura ilustra este concepto. Si los medios espacios H +1 (w, b) y H −1 (w, b) satisfacen las condiciones de (5),
entonces el conjunto {f ∈ Rm |1 ≤ w> f + b ≤ 1} se llama separación para F (L1 ) y F (L2 ), porque ’separa’
F (L1 ) de F (L2 )[4].
De la discusión anterior se deduce que, para encontrar un hiperplano separador para F (L1 ) y F (L2 ), es
necesario resolver el sistema de desigualdades (4). Esto se puede hacer resolviendo el siguiente modelo LO:

min 0
s.t. w1 f1d + ... + wm fm
d
+b≥1 para d ∈ L1 (8)
w1 f1d + ... + d
wm fm + b ≤ −1 para d ∈ L2
En este modelo LO, las variables de decisión son los pesos w1 , ..., wm y la intersección b del clasificador.
Los valores de fid con i ∈ {1, ..., m} y d ∈ L1 ∪ L2 son parámetros del modelo. Una vez que se ha construido
un clasificador (equivalentemente, un hiperplano de separación) para el conjunto de aprendizaje L1 ∪ L2
resolviendo el modelo LO , este clasificador puede usarse para predecir el lenguaje de cualquier documento
d ∈ D. Esta predicción se realiza de la siguiente manera. Sea w1∗ , ..., wm
∗
, b∗ una solución óptima del modelo[4].
Esta solución óptima define el valor del clasificador w1∗ f1d + ... + wm fm + b∗ para el documento d, basado en
∗ d

los valores de caracterı́sticas de ese documento. Si el valor del clasificador es ≥ 1, entonces el documento se
clasifica como documento en inglés; si el valor es ≤ −1, entonces el documento se clasifica como documento
holandés. Si el valor se encuentra entre -1 y 1, entonces el clasificador no determina claramente el idioma
del documento. En ese caso, cuanto más cerca esté el valor de 1, más seguros podemos estar de que d es un
documento en inglés. De manera similar, cuanto más cerca esté el valor de -1, más seguros podemos estar de
que d es un documento holandés.

3.2 Validación de un clasificador

Recuerde que el conjunto de documentos para los que se conoce el idioma se divide en dos partes, a saber,
el conjunto de aprendizaje L y el conjunto de validación V . Antes de usar un clasificador para predecir el
idioma de cualquier documento d ∈ D, es una buena práctica validarlo comparando sus predicciones con los
resultados esperados para el conjunto de validación V . Este paso de validación se realiza para verificar que
el clasificador encontrado por el modelo LO hace predicciones razonables para documentos que no están en el
conjunto de aprendizaje.

3.3 Robustez de los hiperplanos separadores; ancho de separación

El modelo LO generalmente tiene múltiples soluciones óptimas. De hecho, dado que la función objetivo
es la función cero, cualquier solución factible (cualquier elección de hiperplanos separadores) es óptima.
Recordemos que el objetivo de construir un clasificador es usar esta función para automáticamente clasificar
los documentos que no están en el conjunto de aprendizaje de los documentos de inglés y holandés.
 La figura debajo muestra dos hiperplanos H1 y H2, correspondientes a dos soluciones factibles.[5] Supong-
amos que encontramos como una solución óptima al hiperplano H1 (dibujado como una lı́nea sólida), y
supongamos que encontramos un documento de texto dˆ ∈ D cuyo vector de caracterı́sticas

ˆ = [f1 (d)f
f (d) ˆ 2 (d)]
ˆ T

es bastante cercano al vector de caracterı́sticas marcado con un astrisco arriba, pero solamente en el otro lado
de H1. Basado en H1, nosotros concluirı́amos que el nuevo documento de texto está escrito en Holandés. Sin
ˆ es mucho más cercano a un vector correspondiente a un documento
embargo, el vector de caracterı́sticas f (d)
en Inglés que a un vector correspondiente a un documento en Holandés. Entonces tiene más sentido concluir
que el documento dˆ fue escrito en Inglés. Observemos también que el hiperplano H2 no sufre tanto de este
problema. En otras palabras, el hiperplano H2 es más robusto con respecto a perturbaciones que el hiperplano
H2.
Para medir la robustidad de un hiperplano separador dado, calculamos su denominado ancho de separación.
Hablando informalmente, el ancho de separación es la generalización m-dimensional del ancho de banda entre
las lı́neas entrecortadas en la figura de arriba. Para un dado w ∈ Rm \ {0} y un b ∈ R, el ancho de separación
de un hiperplano

H(w, b) = {f ∈ Rm | wT f + b = 0}

está definido como la distancia entre los semiespacios H +1 (w, b) y H −1 (w, b). Es decir:

width(w, b) = min{||f − f 0 || | f ∈ H +1 (w, b), f 0 ∈ H −1 (w, b)},

donde ||f − f 0 || es la distancia Euclidiana entre los vectores f, f 0 ∈ Rm . Notemos que, para cualquier
w ∈ Rm \ {0} y b que pertenece a los reales, width(w, b) está bien definida porque el mı́nimo en el lado de la
mano derecha en la expresión de arriba es obtenido. De hecho, el siguiente teorema da una fórmula explı́cita
para el ancho de separación.
Teorema
Para cualquier w ∈ Rm \ {0} y b en los reales, se cumple que

2
width(w, b) =
||w||
Prueba
Toma un punto fˆ ∈ Rm tal que
wT fˆ + b = −1.

Notemos que
fˆ ∈ H −1 (w, b).
Definimos fˆ0 = fˆ + w∗ , con
2
w∗ = w.
||w||2
Luego, tenemos que
2
||w∗ || = .
||w||
De ello, sigue que:  
2
wT fˆ0 + b = wT fˆ + w +b=
||w||2
2wT w
= wT fˆ + b + = −1 + 2 = 1 ,
||w||2
donde hemos usado el hecho que wT w = ||w||2 . Entonces,

fˆ0 ∈ H +1 (w, b).

Asi, tenemos que

fˆ ∈ H −1 (w, b)

y tambien
fˆ0 ∈ H +1 (w, b).

Luego,
width(w, b) ≤ {||f − f 0 || | f ∈ H +1 (w, b), f 0 ∈ H −1 (w, b)},

Para demostrar que

2
width(w, b) ≥
||w||
, tomemos cualquier
fˆ0 ∈ H +1 (w, b)

y cualquier
fˆ ∈ H −1 (w, b)

Por las definiciones de los demiespacios H+1 y H-1, tenemos que:

wT fˆ + b ≥ 1

y tambien
wT fˆ0 + b ≤ 1

Restando la segunda desigualdad de la primera da la desigualdad

wT (fˆ0 − fˆ) ≥ 2.

La regla del coseno implica que:

wT (fˆ0 − fˆ)
cos θ =
||w||||fˆ0 − fˆ||
Donde theta es el angulo entre los vectores w y fˆ0 − fˆ. Dado que el coseno de theta es menoro igual que 1,
tenemos que:
2
≤1
||w||||f 0 − f ||
Reordenando, podemos obtener la forma final, lo cual termina la demostracion.

3.4 Modelos que maximizan el ancho de separación

Para encontrar un hiperplano que sea lo más robusto posible respecto a la separación, los valores del vector
de peso w y la intersección b deben elegirse para maximizar el ancho de separación. Según el teorema anterior,
2
el ancho de separación es . Observe que minimizar ||w|| produce los mismos valores óptimos para w y b
||w||
2
que maximizar [6]. Por tanto, basta con resolver el siguiente modelo de optimización para encontrar una
||w||
separación de ancho máximo para el conjunto de aprendizaje:

min ||w||
s.t wT + b ≥ 1 para d ∈ L1
wT + b ≤ −1 para d ∈ L2
b, wj libres para j = 1, . . . , m
v
u n 2
uX
La función objetivo ||w|| = t wi es obviamente una función no lineal de las variables de decisión
i=1
w1 , . . . , wm , por tanto es un modelo de optimización no lineal. Estos modelos pueden ser difı́ciles de re-
solver, especialmente cuando el número de documentos (y, por tanto, el número de variables) es muy grande.
Por tanto, buscamos una función objetivo lineal. En general, esto dará como resultado un clasificador de
menor calidad, es decir, el hiperplano correspondiente al resultante (w, b) tiene un ancho de separación menor
que el hiperplano óptimo correspondiente a una solución óptima (w∗ , b∗ ) del modelo.
La función objetivo del modelo de optimización anterior (no lineal) es la norma euclidiana del vector w. Una
generalización de la norma euclidiana es la llamada p-norma. La p-norma de un vector w = [w1 . . . wm ]T ∈ Rm
se define y denota como (p ≥ 1 y entero):
n
X 1/p
||w||p = |wi |p
i=1

Claramente, la norma euclidiana corresponde al caso especial p = 2, es decir, la norma euclidiana es la norma
2. Dado que la 2-norma 2 una función no lineal, no se puede incluir en un modelo LO. Sin embargo, a
continuación, veremos que otras dos opciones para p conducen a modelos LO, a saber, elegit p = 1 y p = ∞.
En el resto de esta sección, discutimos consecutivamente los modelos LO que minimizan la 1-norma 1 y la
∞-norma del vector peso.
3.5 Minimizar la 1-norma del vector peso
En esta sección, consideraremos minimizar la 1-norma del vector peso. La 1-norma de un vector w ∈ Rm se
define como:

m
X
||w||1 = |wi |
i=1
p
Entonces. reemplazamos el objetivo min w12 + ... + wm
2 del modelo por el objetivo:

m
X
min |wj |
j=1
Pm
La función j=1 |wj | no es una función lineal, por definición sabemos tratar los valores absolutos en el
contexto de la optimización lineal. Por otro lado, para convertir el objetivo en un objetivo lineal, definiremos
wj = wj+ − wj− para j = 1, ..., m..
Por lo tanto |wj | = wj+ − wj+ , con wj+ ≥ 0 y wj− ≥ 0. Esto nos lleva al siguiente modelo LO:

m
X
min (wj+ + wj− )
j=1
Xm
s.t. wj+ fjd − wj− fjd + b ≥ 1 para d ∈ L1
j=1
Xm
wj+ fjd − wj− fjd + b ≤ −1 para d ∈ L2
j=1

wj+ ≥ 0, wj− ≥ 0, bf ree para j = 1, ..., m.

Las restricciones siguen siendo lineales, ya que los valores de fji son parametros del modelo, por lo tanto la
funciones de las restricciones son lineales de las variables de decisión b, wj+ , ywj− (j = 1, ..., m)

3.6 Minimizar la ∞-norma del vector peso

En esta sección minimizaremos la ∞-norma del vector peso. Matemáticamente, la ∞-norma del vector se
define como limp→∞ ρ − norma.
Ahora veremos el siguiente teorema afirma que este lı́mite está bien definido, y de hecho es igual a la entrada
con el mayor valor absoluto.

Sea w = [w1 ...wm ]T es un vector. Entonces min ||w||p = max{|w1 |, ..., |wm |} (9)
p→∞

Prueba:
Definimos M = max{|wi ||i = 1, ..., m}, y sea p es cualquier número entero positivo. Tenemos
que:

Xm
||w||p = ( |wi |p )1/p ≥ (M p )1/p = M
i=1
Por otro lado, tenemos que:

Xm
||w||p = ( |wi |p )1/p ≤ (mM p )1/p = m1/p M
i=1
1/p
Se deduce que M ≤ ||w||p ≤ m M . Sea p → ∞ en esta expresion, encontramos que M ≤ limp→∞ ||w||p ≤ M ,
lo que equivale a limp→∞ ||w||p = M , según sea necesario.

Entonces, según el teorema (8), debemos considerar el siguiente objetivo:

min max{|w1 |, ..., |wm |}

La función objetivo max{|w1 |, ..., |wm |} vemos que no es lineal. Sin embargo se puede incorporar un modelo
LO mediante el uso del siguiente método. En primer lugar, introduciremos una nueva variable de decisión z,
que representa max{|w1 |, ..., |wm |}. El objetivo se sustituye por minx, y por último añadiremos las siguientes
restricciones:

|wj | ≤ x para j = 1, ..., m.

Debido a que el valor de la variable x se minimiza en cualquier solución óptima, tendremos que el valor
óptimo x∗ será lo más pequeño posible, al tiempo que satisface x∗ ≥ |wj | para j = 1, ..., m.

Esto significa que x∗ = max{|w1∗ |, ..., |wm

∗
|} en cualquier solución óptima. Combinando este método con el
tratamiento de valores absolutos como en el modelo anterior encontramos el siguiente modelo LO

min x
m
X
s.t. wj+ fjd − wj− fjd + b ≥ 1 para d ∈ L1
j=1
Xm
wj+ fjd − wj− fjd + b ≤ −1 para d ∈ L2
j=1

wj+ + wj− ≤ x para j = 1, ..., m

x ≥ 0, wj+ ≥ 0, wj− ≥ 0, b f ree para j = 1, ..., m
Los valores de las fji son parámetros del modelo y las variables de decesión son b, x, wj+ y wj− para j = 1, ..., m.

4 Resultados y discusiones
Considere el conjunto de aprendizaje de la tabla 1, donde L1 es el conjunto de los seis artı́culos de periódicos
escritos en inglés y L2 es el conjunto de los seis artı́culos de periódicos escritos en holandés. Resolver el modelo
usando un programa de optimización produce la siguiente solución óptima:

b = 0, w8∗ = 0.296, w15

∗ ∗
= 0.116, w17 ∗
= 1.978, w21 ∗
= −0.163, w26 = −2.116

Todas las demás variables de decisión tienen valor cero en esta solución óptima. El clasificador correspondiente
es:

g(f ) = 0.296f8 + 0.116f15 + 1.978f17 − 0.163f21 − 2.116f26

Los pesos corresponden a las letras H, O, Q, U y Z, respectivamente. Por tanto, el clasificador basa sus
∗
cálculos solo en las frecuencias relativas de las letras H, O, Q, U y Z. Observe que el peso w17 asignado a
la letra Q es positivo y relativamente grande en comparación con los otros valores positivos. Esto significa
que, para cualquier documento dado d ∈ D, la expresión w1 f1d . . . wm fm
d
+ b tiende a ser más positivo si
el documento contiene relativamente mucha presencia de la letra Q. Esto significa que es más probable que
∗
dicho documento se clasifique como un artı́culo en inglés. Por otro lado, el peso w26 asignado a la letra Z es
negativo, por lo que es probable que un documento que contenga relativamente muchas veces a la letra Z se
clasifique como un artı́culo en holandés.
Para la validación del clasificador del modelo anterior, tenemos un conjunto de validación que consta de
veinticinco artı́culos de periódicos en inglés y treinta y tres en holandés, es decir, |V 1| = 25 y |V 2| = 33.
La figura 5 enumera las frecuencias de letras relevantes, el valor del clasificador w1∗ f1d + ... + wm fm + b∗ , y
∗ d

la predicción de lenguaje encontrada para varios documentos d en L ∪ V . La fila ”Idioma previsto” indica
el idioma del artı́culo previsto por el clasificador. Un signo de interrogación indica que el clasificador no es
concluyente sobre el idioma; en ese caso, el signo del valor del clasificador determina si el clasificador se inclina
hacia uno de los dos idiomas.
Los documentos 1, 2, 7 y 8, que están en el conjunto de aprendizaje, están correctamente predichos. Esto no
deberı́a sorprender, ya que las restricciones del modelo aseguran este hecho. Para el conjunto de validación,
los resultados no son tan claros. El clasificador predice correctamente el idioma de la mayorı́a de los artı́culos
de periódicos en el conjunto de validación; estos casos se han omitido de la figura 5 (excepto el artı́culo 21).
El clasificador no es concluyente sobre los artı́culos 30 y 66, pero al menos el signo del valor del clasificador es
correcto, lo que significa que el clasificador se inclina hacia el lenguaje correcto. Sin embargo, para los artı́culos
57 y 67, incluso el signo del clasificador es incorrecto. El resultado anterior ilustra el hecho de que el paso de
validación puede revelar problemas con el clasificador construido usando el modelo anterior. Una forma de
mejorar el clasificador es aumentar el conjunto de aprendizaje. En el ejemplo, usamos solo seis documentos
Figure 5: Resultados de la validación del clasificador. Los artı́culos 1, 2, 7 y 8 están en el conjunto de
aprendizaje; los artı́culos 21, 30, 57, 66 y 67 están en el conjunto de validación. Los signos de interrogación
en la fila ”Lenguaje previsto” indican que el clasificador no es concluyente sobre el idioma.

por idioma. En aplicaciones de la vida real, el conjunto de aprendizaje generalmente se considera mucho
mayor. Hemos construido dos modelos LO que ”aproximadamente” resuelven el problema de maximizar el
ancho de separación. Es interesante comparar los resultados de los dos modelos. Para hacerlo, hemos utilizado
un programa para encontrar soluciones óptimas de los modelos 1 y 2 para el conjunto de aprendizaje de la
figura 1. El modelo 1, que corresponde a minimizar la 1-norma del vector peso, tiene la solución óptima (para
el conjunto de aprendizaje de la tabla 1):

w5∗ = −0.602, w15

∗
= 0.131, b∗ = 7.58

Todas las demás variables de decisión tienen un valor óptimo cero. Por lo tanto, el clasificador lineal corre-
spondiente g1 (f ) para este conjunto de aprendizaje es:

g1 (f ) = −0.602f5 + 0.131f19 + 7.58

Observe que este clasificador utiliza muy poca información del vector caracterı́stico f . Solo se tienen en cuenta
dos caracterı́sticas, a saber, las frecuencias relativas de las letras E y O. Como w15 > 0, es más probable que
un artı́culo en el cual la letra O aparece muchas veces sea clasificado como escrito en inglés, mientras que La
letra E se considera como un indicador de que el artı́culo está escrito en holandés.
Por el contrario, considere el modelo 2, que corresponde a minimizar la 1-norma del vector peso. Este modelo
tiene la solución óptima:

wj∗ = 0.0765 para j = 1, 3, 6, 8, 9, 13, 15, 17, 19, 20, 21, 23, 24, 25
wj∗ = −0.0765 para j = 2, 4, 5, 10, 11, 12, 14, 16, 18, 22, 26
w7∗ = 0.0463
b∗ = −0.5530
Sea g∞ (f ) el clasificador lineal correspondiente. A diferencia de g1 (f ) , el clasificador g∞ (f ) toma en cuenta

Figure 6: Comparación de clasificadores basada en minimizar la 1-norma del vector peso vs minimizar la
∞-norma.

todas las caracterı́sticas para hacer una predicción sobre el idioma de un artı́culo dado. El primer conjunto
de pesos en la solución anterior corresponde a las letras A, C, F, H, I, M, O, Q, S, T, U, W, X e Y. Dado que
estos pesos son todos positivos, el clasificador considera una frecuencia relativamente alta de cualquiera de
estas letras en un artı́culo dado como evidencia de que el artı́culo puede estar escrito en inglés. Por otro lado,
el segundo conjunto de pesos, correspondiente a las letras B, D, E, J, K, L, N, P, R, V y Z, son negativas.
Esto significa que una frecuencia relativamente alta de cualquiera de estas letras es tratado como evidencia
de que el artı́culo puede estar escrito en holandés. Observe que el peso w7∗ corresponde a la letra G.
Una pregunta interesante es: ¿es uno de los dos clasificadores significativamente mejor que el otro? Para
responder a esta pregunta, hemos calculado los valores de los dos clasificadores para todos los documentos en
el conjunto de aprendizaje y en el conjunto de validación. La figura 6 muestra los resultados de estos cálculos.
Cada punto de la figura representa un artı́culo. En el eje horizontal hemos graficado los valores de g1 (f d ),
y en el eje vertical hemos graficado los valores de g∞ (f d ) (d ∈ D). En la figura, vemos que los cuadrantes
”noroeste” y ”sureste” no contienen ningún punto en absoluto. Esto significa que los dos clasificadores tienen el
mismo signo para cada d ∈ D: siempre que g1 (f d ) sea positivo, g∞ (f d ) es positivo y viceversa. El cuadrante
”noreste” contiene puntos para los que ambos clasificadores son positivos, es decir, estos son los artı́culos
de periódicos que se prevé que estén en inglés por ambos clasificadores. De manera similar, el cuadrante
”suroeste” contiene los artı́culos de periódicos que se prevé que estén en holandés. Puede verse desde el
calcula que los valores de los dos clasificadores están más o menos relacionados linealmente, lo que significa
que dan como resultado aproximadamente las mismas predicciones. La zona sombeada horizontal en la figura
es el área en la que el clasificador g1 (f d ) tiene un valor entre -1 y 1, es decir, el área en la que el clasificador
no da una predicción clara. De manera similar, la zona sombeada vertical es el área en la que el clasificador
g∞ (f d ) no proporciona una predicción clara. La banda gris horizontal contiene 25 puntos, mientras que la
banda gris vertical contiene solo 9 puntos. A partir de esto, podemos concluir que el clasificador g∞ (f d )
tiende a dar predicciones más claras que g1 (f d ). Entonces, en ese sentido, el clasificador g∞ (f d ) es un mejor
clasificador que g1 (f d ).

5 Conclusiones
El inglés y holandés son considerados idiomas internacionales, en consecuencia, los recursos existentes
se encuentran más desarrollados en comparación a los de otros idiomas. Es conveniente considerar que
incorporar idiomas diferentes traerı́a consigo retos adicionales, los cuales pueden derivar en uso de doble
traducción, expansión de ejemplos vı́a internet, etc.

La clasificación por idioma representa una solución viable ya que utiliza herramientas para franquear la
barrera del lenguaje con el objetivo de aprovechar recursos existentes en uno o varios idiomas.

Los problemas de clasificación pueden abordarse utilizando información que se encuentra en el propio
conjunto escrito en el idioma objetivo. Utilizando dicha información se puede crear un proceso mediante
el cual se encuentren las similitudes existentes entre los documentos no etiquetados, considerando rasgos
propios del dominio.

Los modelos de optimizacion lineal que utilizan el metodo de maximizacion del ancho de separacion nos
permiten obtener una mejor separacion de hiperplanos, lo que hace a su vez que se pueda diferenciar de
forma mas clara si es una porcion de texto pertenece al idioma ingles o al idioma holandes.

El procedimiento realizado en este proyecto no es de uso exclusivo para diferenciacion o separacion de

documentos de texto en ingles y holandes, sino que tambien puede ser usado para clasificar otros idiomas.

References
[1] Gerard Sierksma, Yori Zwols (2015); Linear and Integer Optimization; 6000 Broken Sound Parkway NW,
Suite 300: Taylor and Francis Group.

[2] Bertsimas, D., and Tsitsiklis, J.N. (1997), Introduction to Linear Optimization, Athena Scientific, Bel-
mont, Massachusetts.
[3] Altier, W. J. (1999), The Thinking Manager’s Toolbox: Effective Processes for Problem Solving and
Decision Making, Oxford University Press.

[4] Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J. (2006), The Traveling Salesman Problem:
A Computational Study, Princeton University Press.

[5] Bazaraa, M. S., Sherali, H.D., and Shetty, C. M. (1993), Nonlinear Programming: Theory and Algorithms,
John Wiley and Sons, Inc., New York.

[6] Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993), Network Flows: Theory, Algorithms, and Appli-
cations, Prentice Hall, Englewood Cliffs, New Jersey.