Hace un par de años, mientras estudiaba la convergencia del Teorema de Glivenko-Cantelli (conocido también como el teorema fundamental de la estadística) me encontré varias veces con el estadístico Kolmogorov-Smirnov, el cual al leerlo me dije instantáneamente “¡Pero que buen nombre de Vodka!“, y no resistí simular cómo quedaría un test de hipótesis con grado etílico:

Para quienes no conozcan los teoremas que acabo de mencionar, el de Glivenko-Cantelli es muy importante para el estudio de las Máquinas de Aprendizaje, de hecho Vapnik lo cita bastante al principio de su libro Statistical Learning Theory ya que sin un teorema tan poderoso podría ser absurdo buscar máquinas de aproximación si no existe convergencia entre una observación y un fenómeno. El Teorema de Glivenko-Cantelli asegura que si la muestra de una distribución empírica tiende a infinito, entonces la distribución converge en probabilidad a la distribución desconocida del fenómeno:

El estadístico de Kolmogorov-Smirnov se utiliza para analizar las distribuciones de probabilidad y efectuar un test de hipótesis que pueda determinar si dos distribuciones son iguales:

Si lo relacionamos con el Teorema de Glivenko-Cantelli, el estadístico converge a cero si la distribución de probabilidad empírica se forma a partir de muestras obtenidas de la distribución del fenómeno F(x).

Hermoso, ¿cierto? Aunque esto es sólo una pincelada, ya que el análisis de los matemáticos mencionados para llegar a tales conclusiones es mucho más interesante, y hablando de cosas interesantes, merece especial atención el aporte de Kolmogorov a la teoría de la complejidad computacional.

Kolmogorov y Smirnov merecen tener un vodka en su honor.

Usualmente cuando camino por la calle acostumbro jugar a pisar las lineas, o pisar bloques con un solo pie sin tocar los bordes. Es una manera un tanto infantil pero entretenida para pasar el tiempo caminando por el centro. Sin embargo, en ocasiones cuando veo caminos estrechos me gusta hacer otro juego, intento seguir un camino que equidiste de ambos lados tal como se ve en la figura de a continuación, es decir, la linea azul representa la ruta por la que camino y las lineas de los lados son bordes.

Lo que no había imaginado es que Dirichlet alrededor de 1850 se había cuestionado un problema similar el cual fue estudiado en profundidad por Voronoi después del 1900. El problema era buscar caminos entre varios puntos de tal forma que equidisten entre ellos formando una región máxima alrededor de cada punto.

En la siguiente figura se entiende mejor la idea:

Si se fijan, las lineas negras intentan pasar justo por el centro entre los puntos formando poligonos alrededor de ellos. A esto se le llama Diagrama de Voronoi.

Descubrí esto viendo aplicaciones a la rápida de la triangulación de Delaunay, la cual he ocupado para eliminar falsas rectas en búsqueda de cuadriláteros teniendo un conjunto de puntos.

Una triangulación es simplemente formar una malla de triángulos uniendo con rectas los puntos de un conjunto de puntos. La condición de Delaunay dice que no debe haber ningún punto en el interior de una circunferencia circunscrita en uno de los triángulos formados, por ejemplo el siguiente caso es correcto:

Pero el siguiente es incorrecto ya que un cuarto punto esta adentro de las circunferencias de los triángulos formados:

Esta triangulación da una solución al problema del diagrama de Voronoi, simplemente se deben unir los centros de las circunferencias de los triangulos formados, esta unión va a formar el polígono que rodea a los puntos tal como se ve en la siguiente figura:

Como ven, no es nada de otro mundo, nada espectacular, pero me parecieron entretenidos estos diagramas y por eso quise escribir sobre ellos, quizás mas adelante escriba sobre los convex hulls cuando lea mas sobre ellos, y quizás ahora al caminar me preocupe de pisar los centros de las circunferencias cuando vea algún conjunto de puntos en el suelo para variar mis juegos con los pies al caminar.

Sin lugar a dudas, han existido algoritmos que han influenciado enormemente los avances tecnológicos, y sin ellos probablemente el enfoque de la computación seria otro mucho menos eficiente, no existirían las compresiones de archivos ni las optimizaciones por dar un pequeño ejemplo.

En este artículo se mencionan los 10 algoritmos mas influyentes del siglo pasado, a continuación los menciono:

1. the Monte Carlo method or Metropolis algorithm, devised by John von Neumann, Stanislaw Ulam, and Nicholas Metropolis;
2. the simplex method of linear programming, developed by George Dantzig;
3. the Krylov Subspace Iteration method, developed by Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos;
4. the Householder matrix decomposition, developed by Alston Householder;
5. the Fortran compiler, developed by a team lead by John Backus;
6. the QR algorithm for eigenvalue calculation, developed by J Francis;
7. the Quicksort algorithm, developed by Anthony Hoare;
8. the Fast Fourier Transform, developed by James Cooley and John Tukey;
9. the Integer Relation Detection Algorithm, developed by Helaman Ferguson and Rodney Forcade; (given N real values XI, is there a nontrivial set of integer coefficients AI so that sum ( 1 <= I <= N ) AI * XI = 0?
10. the fast Multipole algorithm, developed by Leslie Greengard and Vladimir Rokhlin; (to calculate gravitational forces in an N-body problem normally requires N^2 calculations. The fast multipole method uses order N calculations, by approximating the effects of groups of distant particles using multipole expansions)

De esa lista no conocía el 3, el 9 ni el 10.

Como referencias rápidas de los que conozco, el 1 es esencial para simulación, el 2 increiblemente necesario para resolver modelos matemáticos lineales, el 4 para darle sentido al álgebra computacional, el 5 para potenciar los lenguajes de programación, el 6 para resolver montones de problemas algebraicos, el 7 para ordenar datos de manera inteligentemente rápida, y el 8 para aplicaciones en todo donde convenga usar datos en el espacio de frecuencias.

Personalmente, habría agregado el algorítmo Levenberg-Marquardt iteration, a mi parecer es el algoritmo más elaborado para refinamiento iterativo de datos, tiene buena convergencia y no es tan costoso como otros métodos menos eficientes. También me hubiese gustado ver la descomposición de matrices SVD, si bien es cierto que es mas útil el uso de QR, SVD no se queda atrás y yo al menos lo uso bastante. Por último, habria agregado RANSAC no por su influencia histórica, sino porque personalmente me gusta mucho como funciona y aunque no es muy rápido entrega resultados muy robustos.

Les recomiendo que lean el artículo, es bastante interesante.

En la literatura inglesa existen dos palabras muy similares: Homograph y Homography. La primera tiene una traducción oficial al español como Homografía. Una Homografía es un fenómeno de la lingüista que ocurre cuando dos palabras se escriben de forma idéntica pero tienen significado o incluso (en el caso del inglés) pronunciación diferente. Sin embargo, la segunda palabra que describí al principio, Homography, no tiene una traducción estandarizada al español, personalmente yo le digo Homografía (por similitud a todas las palabras que tienen como postfijo “phy”).

Y bueno, ¿Qué es una Homography para que me preocupe tanto de cómo decirla en español?

Es una relación matemática que he usado mucho para mi trabajo con estimación de pose en realidad aumentada. Consiste en pasar los puntos (representados en forma homogenea) que se encuentran en un sistema de coordenadas a otro sistema diferente. Esta relación se logra gracias a una Homography Matrix como la siguiente:

Tenemos los siguientes puntos a y b, y su correspondiente Homography Matrix de 9 componentes

Luego, se logra la siguiente propiedad:

Es decir, si tenemos la matriz H podremos pasar cualquier punto de un sistema de coordenadas a otro, encontrar la matriz H es un problema que no voy a abordar (por ahora).

Ese era un ejemplo para mostrar la importancia de la palabra Homography, y de ahora en adelante le seguiré diciendo Homografía como acostumbro hacerlo, por lo tanto dada la similitud de las palabras en español, para mi la palabra Homografía es una Homografía (a no ser que a otra persona se le ocurra una mejor traducción a Homography).