¿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