En este blog iré comentando en español pequeños resúmenes de los módulos del curso Networks, friends, moneys and bytes de Coursera, conducido por el instructor Mung Chiang de la Universidad de Princeton, cualquier duda o comentario serán muy bienvenidos porque así aprendemos todos

domingo, 30 de septiembre de 2012

Filtrado colaborativo 2

El método usado por Netflix para recomendar sus películas se basa en buscar similitudes. Como vimos en la entrada anterior han acumulado millones de evaluaciones hechas por usuarios. Con toda esa información se puede crear una matriz, por ejemplo, donde en las columnas estén las películas y en las filas todos los usuarios que han hecho evaluaciones. Es una matriz enorme que puede tener millones de usuarios y decenas de miles de películas, además no es una matriz cuadrada, tiene más filas que columnas.

En la celda correspondiente al par (usuario, película) se guarda la evaluación del usuario Ui para la película i. La idea general es que a usuarios similares probablemente les gustarán películas similares, el problema es como definir esa "similaridad" a partir de las evaluaciones. Intuitivamente podemos pensar que si un usuario da la misma calificación a dos películas, estas serían -para el- de calidad similar. Y si dos usuarios le dan la misma calificación a una película estos tienen gustos similares. Cuando hay esta similaridad se dice que existe una vecindad entre películas y usuarios. Como decíamos la idea es que a cierta clase de personas le gusta cierta clase de películas.

Matemáticamente una de las maneras de detectar estas vecindades y usarlas para predecir es el método de los mínimos cuadrados. Pero antes de eso se usan los modelos paramétricos, que son modelos matemáticos que en un comienzo tienen algunos datos que son variables en la etapa de entrenamiento, pero serán fijos en la etapa de predicción. Así los modelos paramétricos tienen dos etapas: entrenamiento y predicción.

Un buen ejemplo de esto son los sistemas de reconocimiento de voz de los computadores o teléfonos (marcadores de voz). En su etapa de entrenamiento el usuario ingresa algunas frases conocidas para que el sistema ajuste sus parámetros al tono y modulación de una voz en particular, estos son los datos de línea base. Luego que ha sido entrenado, el sistema ya puede interpretar la voz prediciendo que ciertos sonidos corresponden a ciertas palabras. En general el esquema es así:


Simplificando al extremo, en el caso de Netflix se tiene un gran registro histórico de calificaciones que sirven para crear la línea base  para entrenar al modelo paramétrico. El modelo parte con una suposición burda, por ejemplo tomando el simple puntaje de evaluación promedio de todo el conjunto de evaluaciones, a esta se le agrega un factor por el sesgo que puede tener cada película y el sesgo que puede tener cada espectador (por ejemplo, que prefiera las de acción alas de romance). Se hace una primera estimación para una película con puntaje conocido y se compara la predicción con el puntaje real, la diferencia entre el valor de la predicción real y el predecido es el error.

Entonces se usa el método de error de los mínimos cuadrados, que mide cuan alejada o cerca está la curva de predicciones respecto de la curva real. Ahora se trata de optimizar esta curva de errores mínimos cuadrados para que se acerque a la real, minimizar los errores cuadráticos medios.

En estos modelos se usa la palabra "sintonizar" para describir como van convergiendo las predicciones con la línea base en la etapa de entrenamiento. Para complicar las cosas existe en los modelos paramétricos un problema llamado "overfitting" que ocurre cuando algunas predicciones concuerdan demasiado con la línea bae en el período de entrenamiento el modelo se va haciendo rígido y pierde poder predictivo. Para esto se hace cierto ajuste matemático llamado regularización de mínimos cuadrados.

Como la función que deseamos optimizar es cuadrática (mínimos cuadrados) no podemos usar la programación lineal, lo que se usa es optimización convexa. Mientras la programación lineal se hace con un sistema de inecuaciones lineales más restricciones que definen un espacio de soluciones factibles en forma de polígono, con aristas bruscas, la optimización convexa también define un espacio convexo, sin quiebres bruscos.

Hay una definición gráfica interesante: un conjunto es convexo si cualquier par de puntos en el conjunto se pueden unir por un segmento de recta que no salga del conjunto, por ejemplo (a) es convexo y (b) no lo es


La propiedad geométrica más importante es que entre dos conjuntos convexos que no s etoquen siempre se puede trazar una recta entre ellos que no los toque, cosa que no ocurre si al menos uno no es convexo. Una función convexa es intuitivamente una que se curva hacia arriba, como (a) en la figura


Es resumen, la minimización de una función convexa en un conjunto convexo es la llamada optimización convexa. Y en el caso especial de los mínimos cuadrados se optimiza un función convexa no sujeta a ninguna restricción. A grandes rasgos el predictor de línea base para el adiestramiento funciona minimizando una función de error por mínimos cuadrados.

Pese a la complicada fundamentación matemática este método de optimización podría resumirse en una sola frase: se define una función objetivo con la suma de los errores al cuadrado, para cada punto de esta función su segunda derivada se iguala a cero (porque está en un "valle" o sea un óptimo convexo) esto da una ecuación lineal que al resolverse entrega la predición. Si estoy equivocado que alguien me corrija, pero así es como yo lo entendí.

No hay comentarios:

Publicar un comentario