Sampling and learning distance-based probability models for permutation spaces

Abstract

Esta tesis est¿a dedicada al aprendizaje y muestreo de los modelos de probabilidadsobre permutaciones basados en distancias. En concreto, las distancias consideradasson la ¿ de Kendall, Cayley, Hamming y Ulam. El objetivo es definire implementar operaciones eficientes. Las operaciones fundamentales para distribucionesde probabilidad son el muestreo y aprendizaje. Se han definido unao varias funciones de muestreo y aprendizaje para cada uno de los modelos consideradosy la esperanza de la distancia en todos los casos. Adem¿as, se discutesobre cada uno de ellos, su aplicaci¿on y relaciones con distintos modelos en laliteratura.Para lograr el objetivo de dar con funciones eficientes, esta tesis se enmarcano solo en el campo de la computaci¿on, si no tambi¿en en los de estad¿¿stica ycombinatoria.Las permutaciones son funciones de un conjunto de n items a ¿el mismo. Enesta tesis se usa la representaci¿on cl¿asica en la forma de un vector ordenado delos n primeros n¿umeros naturales.La literatura sobre modelos probabilicos para espacios de permutaciones noes reciente e incluye diferentes modelos. Los m¿as destacados son los modelosbasados en pares de comparaciones, los modelos de Thurstone, Plackett-Lucey los modelos basados en distancias. Esta tesis se dedica a ¿estos ¿ultimos yextensiones sobre los mismos.Los modelos basados en distancias son de la familia de los exponenciales. Suforma general se denomina modelo de Mallows (MM) en honor al autor que lospropuso originalmente. La definici¿on formal de un MM es la siguiente:p(") =exp(