Nube de Etiquetas
(Ah?)

lunes, febrero 11, 2008

¿Regresión usando Programación Lineal?

Alfredo me comentaba que había leído varios tópicos de Investigación de Operaciones, pero que ninguno de los tópicos era Data-Mining, por ejemplo, o métodos Multi-Superficie. En mi respuesta le insinué que ciertamente no son tópicos de la IO, pero no por ello es imposible que si se idea una formulación adecuada del modelo, la IO pueda aportar en campos que en principio se asumen como "diferentes".

En un post anterior escribí sobre la diferencia entre Regresión y Clasificación. Para la mayoría de los que han tenido contacto con cursos introductorios de IO, estará claro que no son parte del temario de IO.

Todo esto me inclinó a escribir hoy acerca de una aplicación de IO para Regresión. Ya a muchos les quedó claro que me he ocupado bastante del uso de la IO para clasificar, y bueno, la Regresión quedó huerfanita, al parecer... ;o)

Antes que todo, quiero dejar claro que el modelo más famoso en la actualidad, para realizar clasificación binaria (los SVM) también es utilizado para regresión. Con esto quiero decir, que lo que voy a desarrollar acá no es la invención de la rueda.
Es un simple ejemplo ilustrativo, que me permitirá (espero yo!) mostrar una regresión mediate IO, sin entrar en detalles sobre los SVMs (vale la pena acotar que fue parte de los ejercicios de un curso de Análisis de Sistemas Lineales del Prof. Ubaldo García Palomares de la USB).

El ejemplo es el siguiente:

Se tienen 4 puntos en el plano cartesiano...
e1 = (0.1 , 1.0)
e2 = (0.8 , 2.2)
e3 = (2.2 , 2.8)
e4 = (3.3 , 3.9)

Que lucen más o menos así, al graficarlos en Excel (disculpen la cuña!):


Bueno. Se nos pide que, sin usar mínimos cuadrados, aproximemos una recta

y = a*x + b

que pase lo más cerca posible a todos esos puntos.

Yo voy a resolver el problema formulando un modelo de programación lineal... primero, tengo como información que la función a aproximar es una línea recta. Si me disculpan una notación extremadamente simple, diré que cuando tenga un i-ésimo punto ei, con componentes (xi , yi), tendré un error dado por la resta

[ yi - yi~ ]

donde yi~ es el estimado que me arroja la función de la recta, es decir:

yi~ = a*xi + b.

En mínimos cuadrados, se quiere hacer pequeña la suma de los errores cuadráticos:

[ yi - yi~ ]^2

Bueno, como me pidieron que no fuese una minimización de los errores cuadráticos, me quedaré con la expresión [ yi - yi~ ].

Ahora, ese error me va a dar positivo cuando el estimado sea menor que el valor real, y negativo cuando pase lo contrario... y si sumo los errores así, podrían cancelarse positivos con negativos, dando una suma que realmente no significará nada para mi.

Así que voy a hacer pequeña, en cambio, a la suma de los errores absolutos:

| yi - yi~ |

Ahora, recordemos de bachillerato que la función "valor absoluto" ( y=|x| ) no es lineal, así que... evidentemente no puedo resolverlo con Programación Lineal....

... O SI!!!

Yo puedo respirar profundo, abrir y cerrar los ojos, y escribir lo mismo, de forma un poquito diferente. Puedo tranquilamente decir que yi~ es igual a yi, más una variable "di" que mide el i-ésimo error de forma no-absoluta, así:

di = yi - yi~

yi~ + di = yi

Ahora, todavía la suma de los errores "di" me deja en las mismas, porque podría tener positivos y negativos (con toda seguridad!). No he hecho nada interesante aún. Sin embargo, ahora si respiro profundo y me aseguro de que mi lapiz tiene punta, porque voy a jugar con ese error "di". Quiero jugar de forma que tenga sólo variables no-negativas, que crezcan cuando hay error. Por ello, voy hacer lo primero que se me ocurre: expresarlo como una resta de dos valores positivos.

NOTA: cualquier número puede expresarse como
la diferencia
de dos valores no-negativos. Ejemplo:
1 = 34-33
-8 = 10 - 18

Por lo tanto, "nadie me quita lo bailao" si yo decido escribir ahora la diferencia así:

yi~ + (dip - din) = yi

donde dip, vale di, si el error es positivo... (y din = 0)
y din, vale -di, si éste es negativo... (y dip = 0)

Digamos, para mostrarlo fácilmente, que si yi = 2, y el estimado yi~ = 3, entonces tendremos:
3 + 0 - 1 = 2

en otras palabras, dip = 0, y din = 1.

Por lo que din estaría sumando 1 a mi total de errores, en lugar de un -1 (aunque el error que he definido es negativo, porque el verdadero valor es más pequeño que el estimado).

Ahora tengo lo siguiente, si lo aplicamos a los 4 puntos:

y1~ + d1p - d1n = y1
y2~ + d2p - d2n = y2
y3~ + d3p - d3n = y3
y4~ + d4p - d4n = y4

con d1p, d2p, d3p, d4p, d1n, d2n, d3n, d4n todos >= 0.

Esas serían las restricciones de mi modelo, que si sustituímos los estimados por la expresión que proporciona el estimado en base a el xi (componente x del i-ésimo punto) en cada caso, sería lo mismo que:

(a*x1 + b) + d1p - d1n = y1
(a*x2 + b) + d2p - d2n = y2
(a*x3 + b) + d3p - d3n = y3
(a*x4 + b) + d4p - d4n = y4
d1p, d2p, d3p, d4p, d1n, d2n, d3n, d4n >= 0

Nótese que he colocado las variables en color azul. Lo que esté en negro es "dato".

Ahora, me podría asustar y gritar: ¡ahora tengo 2 veces más incógnitas que antes! ... pero en este tipo de cosas lo que se nos pide es que tengamos la valentía de seguir adelante a ver a donde se llega, hasta que se llegue,... a la solución...

...o a una calle ciega... lo cual es siempre una posibilidad que no tiene por qué desanimarnos si no estamos en un exámen.. jeje.

Así que tomamos un poco de chocolate caliente para el alma, y nos preguntamos: ¿qué es lo que quiero hacer pequeño? Respuesta: la suma de los errores dip y din.

Es decir, que mi función objetivo es la suma de los errores positivos y negativos:

Minimizar Z = (d1p + d2p + d3p + d4p) + (d1n + d2n + d3n + d4n)

Esto hará, que en la resolución el algoritmo utilizado quiera hacer que todas las variables dip y din tengan el menor valor posible: cero (0), colocando la recta justo para que pase por los puntos.... en tus sueños!! jaja...

Como lo más probable es que no lo logre, tendrá que sacrificar alguna de las variables dejándola que sea mayor que cero. Pero en ningún momento hará que una que no sea necesaria, sea mayor que cero. El modelo entonces queda formulado completo así:

Minimizar Z = (d1p + d2p + d3p + d4p) + (d1n + d2n + d3n + d4n)
din, dip, a, b

Sujeto a:
(a*x1 + b) + d1p - d1n = y1
(a*x2 + b) + d2p - d2n = y2

(a*x3 + b) + d3p - d3n = y3

(a*x4 + b) + d4p - d4n = y4
d1p, d2p, d3p, d4p, d1n, d2n, d3n, d4n >= 0

Abajo tengo una imágen donde muestro en excel como saqué las cuentas en la hoja de cálculo, para la función objetivo y los valores que necesito para las restricciones. Lo amarillo es celda que representa a una variable, y lo azul son celdas que cambian en función de las variables (diferente a como coloreé las cosas en el texto). Guardé ese pantallazo mostrando en particular la fórmula con que estoy calculando el y~.


Ya es el momento de llamar a la máquina que me dirá cuáles son los valores óptimos de "a" y "b" de la recta, es decir, aquellos que podrán existir haciendo la suma de los errores lo más pequeña posible. La forma en que llené los datos en el Solver, la muestro abajo. Dense cuenta de que hice que los dip y din fuesen no-negativos, pero no restringí en absoluto a las variables "a" y "b":

(Las dudas sobre lo que significa lo que se ve arriba las podemos aclarar luego en la medida en que me pregunten, si lo desean)

Finalmente, y para no seguir alargando el post, veamos el resultado que arroja el Solver, así como una graficación de la recta que resulta:


¿No está mal, eh? Bueno. Aquí termina el ejemplo de hoy.

Traté de hacer esto de forma que todos pudiesen replicar el resultado fácilmente. Espero haberlo logrado. ¡Cualquier cosa, como siempre: pregunten!

Así pues, tenemos una regresión, no basada en minimización de errores cuadrados, sino obtenida mediante la resolución de la clase de modelo más emblemático de la IO: la Programación Lineal.

¿Es la Regresión Lineal un problema de IO? Probablemente no... pero no significa que pueda usarla para resolver el problema. ¡Ese es el espíritu!

Nota: para los recién iniciados en esto, que estén curiosos y quieran ver más allá de lo evidente, les adelanto que este tipo de regresión tiene cierto tipo de ventajas respecto a la regresión cuadrática bajo ciertas circunstancias. Se llama minimización en "norma - 1", mientras que en la de mínimos cuadrados se minimiza la "norma - 2"....

...pero eso es parte de otra historia

XoD

3 comentarios:

Alfredo dijo...

Hola Orestes, primero mil gracias por responder el comentario, de verdad que aclarastes mis inquietudes, y de verdad que entre el liberman, tu blog, y mi profesor, las ganas de aprender un poco mas sobre esta materia crecen

Creo que aun tengo un poco de preguntas que hacer y de clases que recibir, pero espero que poco a poco se vayan aclarando.

Ahora tengo otras preguntas (voy a englobar en este comentario, tu post sobre la respuesta y tu post sobre regresion usando programacion lineal).

Queria pedirte primero que me explicaras un poco mas sobre SVM y sobre los reconocimientos de patrones, creo haber agarrado la pista pero quede ay ay... (tu entiendes jeje)... no del todo claro (en si todo ese parrafo no me quedo claro, solo creo haber tomado una idea)

Sobre las faunas de IO, me dejas sin saber que preguntar, por que la materia la he visto muy metodica, muy "estas son las herramientas y se usan asi..." y no se debate mucho sobre que teorema sale de que, o tal herramienta está en la misma fauna que esta otra, (solo tengo ideas mas no nada claro, por ejemplo tengo entendido que teoria de juegos y teoria de decisiones se llevan de la mano por que ay un enfrentamiento, en el primero de dos personas, y en el segundo de una persona contra los eventos naturales que pudieran ocurrir, asi que no se si ambas entran en la misma fauna o son diferentes).

y sobre la clase de regresion usando programacion lineal, toda la clase fue exelente, y gracias por compartirla... peeeero... ¿que hiciste en excel? jeje me siento indigena preguntando eso, es que aqui en la udo todavia mandan a resolver un simplex usando cincel para escribir sobre laminas de piedra (unga unga XoD)

Bueno de momento creo que eso es todo... y mil gracias de antemano.. espero haber sido coherente en mis preguntas (creo que esta ves no fui tan preciso, creo que es por que ahora estan saliendo mas dudas a flote)

Orestes dijo...

Hola Alfredo!

Sobre SVM, no te preocupes que uno de estos días publico algo sobre ello. Disculpa que no lo haga ahora, pero no son mi interés principal (estoy tratando de cambiar ese paradigma, precisamente). Si quieres, avísame y te puedo recomendar bibliografía para que te inicies en eso (siempre será mejor que leer las superficialidades que yo pueda escribir en el blog!).

Sobre las faunas de IO, quiero decirte que no pretendí clasificar las técnicas, sino los enfoques de los profesionales de la IO. Sobre el ejemplo que me das, yo concuerdo contigo en meterlas en un saco, aunque tengan diferencias entre ellas. Criterios para clasificar las herramientas de IO hay muchos, sin embargo. Entiendo que en los cursos se busque dar una estructura definida y clara. Sin embargo las formas en que el ser humano innova e investiga son muchas, my friend... y de ahí las faunas de investigadores en esta área!

En cuanto a lo que hice en Excel, no te preocupes que no es gran cosa. Simplemente utilice un Add-in de Excel que se llama "Solver". Te resuelve modelos de optimización (no sólo lineales). Para comenzar, te recomendaría dos cosas:

1. El tutorial en español que está en esta dirección: mit.ocw.universia.net/15.053/s02/pdf/usingexcelsolver.pdf

2. El ejemplo que pone la gente de Solver para explicar el uso de su herramienta: http://www.solver.com/stepbystep.htm

Obviamente, usando Google, puedes teclear "+Solver +Tutorial" o algo así y podrás tener otro tipo de ayudas. Pero por los momentos esos creo que son buenos. Haz los ejemplos y vuelve a leer el post para que veas que lo que hice no es "rocket-science", sino un uso básico.

Lo posiblemente innovador es la formulación (aunque para los del área pueda parecer obvia). Los problemas que resuelves a cincel en la UDO, los puedes resolver en 3 milisegundos en Solver... :o)

¡Claro que hay docentes que consideran útil explicar el algoritmo Simplex!. Yo respeto eso, pero no lo comparto, a menos que la persona esté estudiando orientado hacia la algorítmica, o sea un curso avanzado. De resto, creo que sólo hacer una corrida en frío a modo ilustrativo es suficiente. Creo que se pierde "scope" del tema haciendo que los alumnos se lo aprendan y lo usen, y les evalúen eso en exámenes... los alumnos terminan creyendo que es importante saber hacer las iteraciones. En esto, estoy seguro de que habrá muchos que me saltarán encima a rebatirlo... Let them come! hablando seguro nos entenderemos.

Antes de continuar hay algo que no quiero dejar comentarte: hay otras herramientas mejores para resolver problemas que el Solver. El hecho de que te de una respuesta rápido, no significa que sea la mejor herramienta. A veces, usándolo, ha tenido resultados "raros", que me han creado una desconfianza en él. Pero para un curso introductorio puede ser bueno usar Solver.

Para terminar... de nuevo Alfredo, gracias por leerme, y por tu feedback!

Orestes dijo...

Por cierto... en la página de "The Science of the Better", hay un artículo que explica sobre la IO... http://www.scienceofbetter.org/what/index.htm

Ahí ellos resúmen las técnicas en tres grandes áreas:
1. Optimización
2. Simulación
3. Probabilidades y Estadística

Aunque haya áreas grises, y cosas que posiblemente no estén cubiertas en esos tres paraguas, creo que es una buena aproximación a las clases de fauna que pueden identificarse en las técnicas.