jueves, 26 de noviembre de 2015

Regresión lineal simple: Algoritmo de gradiente descendente en Python


Bueno, ya mas viejo regreso a las andadas y en esta oportunidad tengo algo para aportar relacionado con algoritmos iniciales de Machine Learning.

En este caso, y a efectos pedagógicos, quiero compartir, como lo dice el título, una implementación en Python del algoritmo de la función de gradiente descendente para la minimización de los parámetro theta0 y theta1 en la función hipótesis de regresión lineal simple.

Este pequeño artículo no busca profundizar en las cuestiones netamente teóricas, dado que en la web se pueden encontrar innumerables artículos académicos que explican los fundamentos teóricos de está técnica introductoria de Machine Learning mucho mejor de lo que podría hacerlo yo ;)

Vagamente y muy al pasar, vamos a decir que el aprendizaje automático, el campo de estudio que da a las computadoras la capacidad de aprender sin ser programadas de forma explícita, puede dividirse en aprendizaje supervisado y no supervisado.

Algunos autores sugieren, a su vez, que el aprendizaje supervisado está formado por técnicas de clasificación (predicción de targets de tipo categóricas) y regresión (predicción de targets de tipo continuas).

La puerta de entrada a las técnicas de regresión, es la regresión lineal simple. Podemos decir, someramente, que un problema de regresión lineal simple es aquel en el cual se predice un único valor de salida, de tipo continuo, a partir de una única variable de entrada.

¿Como se hace? Bueno, esto se lleva adelante a través de la búsqueda de una función hipótesis que permita convertir las x provistas como entradas en salidas (y).
La función hipótesis tiene este aspecto:

hθ(x)=θ0+θ1x

Lo que nosotros, naturalmente debemos encontrar son los valores de los parámetros theta0 y theta1 que realicen las mejores predicciones para nuestro problema.

Ahora bien, ¿como sabemos cuales son los valores de los parámetros que hacen a una función lineal mejor que otra? Existen funciones denominadas "función costo" que permiten verificar cual es el error de predicción de una función determinada con respecto al conjunto de datos preexistentes. En nuestro caso, utilizaremos la función del error cuadrático medio, que luce así:

J(θ0,θ1)=12mi=1m(hθ(x(i))y(i))2

Básicamente, lo que hace la función anterior, es ir comparando la predicción o clasificación de nuestra hipótesis (h0) contra el valor real (y) para cada uno de los datos que tenemos. Luego, lo divide por el doble de la cantidad de instancias a efectos de conseguir un valor mas "decoroso".

Si, si claro Juan pero... voy a tener que probar todos los valores posibles para los parámetros theta0 y theta1 y ver cual minimiza la función costo? No, para ello, existen varias técnicas que "recorren la gráfica de la función costo" buscando aquellos valores de theta0 y theta1 que la minimizan. Existen métodos analíticos y métodos iterativos, en nuestro caso utilizaremos un método analítico, el de gradiente descendente, cuya ecuación tiene la siguiente pinta:




repeat until convergence:
θj:=θjαθjJ(θ0,θ1)

En la función anterior, el simbolo j, naturalmente podrá tomar los valores 0 y 1 (por theta0 y theta1... ahhhh). Luego, el símbolo alpha es un valor arbitrario que determinará el consumidor, y que se podría pensar como un acelerador de la velocidad con que se recorre la curva de costo buscando el mínimo. Conforme determinemos un alpha mas grande, el paso será mayor.

Ven el simbolito de la derivada que está junto a la función J? Bueno, si resolvemos esa derivada para nuestra función J (función costo de error cuadrático medio), el algoritmo nos queda con la siguiente pinta:

repeat until convergence: {θ0:=θ1:=}θ0α1mi=1m(hθ(x(i))y(i))θ1α1mi=1m((hθ(x(i))y(i))x(i))

Otra cosa que naaaaadie explica y a mi no me pareció tan obvio es el tema de "repetir hasta converger". Básicamente, vamos a decir que el algoritmo converge cuando, tanto los valores de theta0 como theta1, no varían con respecto a la iteración anterior.

Ahora bien, basta de charlatanería... Les copio a continuación el código, el cual no es el mas eficiente que puede desarrollarse pero permite trabajar con diferentes datasets pasados como parámetros, establecer un valor de alpha y jugar con los valores iniciales de theta0 y theta1:


#!/usr/bin/env python
from __future__ import division
import csv

def j(archivo, t0, t1, calculo):
 # Leemos los datos desde el archivo
 dataset = open(archivo, 'r')
 dataset.readline() #Saco el encabezado
 # Parametros
 i = 1
 pendiente = 0
 m = len(open(archivo).readlines())-1
 total = 0

 # Comienza la sumatoria
 for instancia in dataset:
  instancia = instancia[:-1] #Quitamos el salto de linea
  x,y = instancia.split(",")
  x = int(x)
  y = int(y)
  h0 = t0+t1*x
  if calculo == 'theta0':
   total = total + (h0-y)
  elif calculo == 'theta1':
   total = total + (h0-y)*x
  i=i+1

 total = total * (1/m)

 #Devuelvo resultado
 return total

converge = False

theta0 = raw_input("Ingrese el valor inicial para theta0: ")  
theta1 = raw_input("Ingrese el valor inicial para theta1: ")  
alpha = float(raw_input("Ingrese el valor de alpha: "))
archivo = raw_input("Ingrese la ruta y nombre del dataset: ")

theta0_calc=int(theta0)
theta1_calc=int(theta1)

i = 1
while not(converge):
 theta0 = theta0_calc
 theta1 = theta1_calc

 print 'Theta0: '+str(theta0)
 print 'Theta1: '+str(theta1)
 
 theta0_calc = theta0_calc - alpha*j(archivo, theta0, theta1, 'theta0')
 theta1_calc = theta1_calc - alpha*j(archivo, theta0, theta1, 'theta1')

 print 'Theta0 Actualizado: '+str(theta0_calc)
 print 'Theta1 Actualizado: '+str(theta1_calc)

 if (theta0_calc == theta0) and (theta1_calc == theta1):
  print 'Converge en la iteracion '+str(i)
  print 'h0 = '+str(theta0)+' + '+str(theta1)+ '*X'  
  converge = True
 i=i+1


Cuando me largué a publicarlo, realmente lo hice porque en la web encontré mucha teoría pero nada implementado, espero haber aportado algo a esta maravillosa red de conocimiento ;)

Hasta la próxima...