En casi todos los casos, estoy de acuerdo con Alon. Sin embargo, hay algunos ejemplos notables en los que algo como la simplificación de una prueba que antes era difícil de manejar ayudó a desarrollar mejores algoritmos / métodos computacionales. En estos casos, una comprensión profunda de una prueba, las técnicas utilizadas y la intuición detrás de la prueba terminan ayudando a desarrollar mejores herramientas matemáticas aplicadas.
- Detección comprimida
Antes de saltar al caso del algoritmo inspirador de pruebas, expongamos el problema:
Supongamos que tengo un vector [math] \ vec {s} \ in \ mathbb {R} ^ n [/ math] que representa la ‘señal real’ que quiero medir. Ahora en la práctica, supongamos que solo puedo hacer mediciones [math] m <n [/ math] de [math] \ vec {s} [/ math]. Esto significa que mido un vector [math] \ vec {y} \ in \ mathbb {R} ^ m [/ math]. Si sé que existe una relación lineal entre los dos vectores, entonces el objetivo es el siguiente: Dado [matemáticas] \ vec {y} + \ vec {\ epsilon} = \ mathsf {F} \ vec {s} [/ math], donde [math] F \ in \ mathbb {R} ^ {m \ times n} [/ math] y [math] \ vec {\ epsilon} \ sim \ mathcal {N} (\ vec {\ mu} , \ mathsf {\ Sigma}) [/ math]. Suponiendo que sé [math] \ vec {y}, \ mathsf {F} [/ math], ¿qué tan bien puedo recuperar [math] \ vec {s} [/ math]?
Terence Tao y Emmanuel Candes [0] dieron pruebas de límites de error (por ejemplo, cuantificación de ‘¿qué tan bien puedo recuperar X?’) Para la reconstrucción de [math] \ vec {s} [/ math] suponiendo que cada elemento de [math ] \ mathsf {F} [/ math] se extrajo de un gaussiano. Continuaron construyendo sobre estos resultados y demostraron más límites con el tiempo [1, 2]. Curiosamente, ha habido un montón de documentos que han utilizado las pruebas de estos límites de error como inspiración para algoritmos que pueden acercarse al límite teórico para minimizar [matemáticas] m [/ matemáticas] (Ver [3]). Si bien los algoritmos en sí mismos pueden no ser particularmente complicados desde el punto de vista de la codificación, requieren una buena cantidad de sofisticación matemática y una comprensión bastante profunda de las técnicas de prueba y, lo más importante, una comprensión de la intuición detrás de la prueba.
- ¿Por qué hay una ley de grupo en una curva elíptica?
- ¿Qué implica la representación de la ventana de tiempo de un creador de claves como un múltiplo de pi sobre la arquitectura matricial?
- ¿Cuál es el fondo más deseable para un trabajo como criptógrafo?
- Números primos: ¿Hay alguna investigación sobre la aplicación de la teoría de grafos para generar tamices primarios?
- ¿Qué esquemas de numeración de vértices para icosaedro y dodecaedro permiten más fácilmente el cálculo de adyacencia y distancia?
- Construcciones que rompen el palo de los prior bayesianos
El ahora popular Proceso de Dirichlet (DP) tiene sus raíces tanto en el estudio de Fisher de la genética de poblaciones (ver [4] para algunos antecedentes) como en el estudio general de medidas aleatorias. Como algunos de los resultados asociados para ambas aplicaciones se remontan a la década de 1970, es natural preguntarse por qué el Proceso de Dirichlet se ha puesto de moda. Parte de la respuesta, por supuesto, es que nuestro aumento en el poder de cómputo ha hecho posible la inferencia bayesiana. Sin embargo, una de las principales herramientas que permitió la formulación bayesiana del proceso de Dirichlet fue la construcción de ruptura de palo debido a Sethuraman [5]. Esto le dio al proceso de Dirichlet un enfoque amigable con el algoritmo para construir rutas de muestra y muestreo de Gibbs de este proceso. En este resultado, encontramos que una prueba de equivalencia entre un modelo que es cualitativamente agradable, pero difícil de implementar y un modelo que es cualitativamente confuso, pero fácil de implementar, nos brinda una forma de conectar la intuición y el algoritmo. Por ejemplo, sin una buena comprensión de la construcción de Sethuraman y partes de su prueba, sería difícil desarrollar muestreadores de Gibbs eficientes para este proceso.
Tenga en cuenta que también hay una nota negativa asociada a (la mayoría) de las implementaciones algorítmicas del muestreo de procesos de Dirichlet que cambiaría si se entendiera mejor la teoría de los antecedentes de Dirichlet. Mucha gente usa el DP con antecedentes un tanto informativos (por ejemplo, un previo no uniforme en el simplex de probabilidad) simplemente porque es algorítmicamente fácil. Sin embargo, uno debe notar el famoso resultado de Diaconis y Freedman [6] que muestra que para ciertas clases de antecedentes no informativos, el DP no es consistente y puede converger a una masa de puntos que no es igual a la distribución verdadera que uno es intentando probar En este caso, diría que si uno entendiera la teoría del proceso de Dirichlet (y sus degeneraciones), podría evitar tener que aplicar la heurística para “corregir” los resultados “aparentemente incorrectos”.
[0] (No es gratis) http://ieeexplore.ieee.org/xpl/l…
[1] (Gratis) http://projecteuclid.org/DPubS?s…
[2] (No es gratis) http://ieeexplore.ieee.org/xpl/l…
[3] (Gratis) http://prx.aps.org/abstract/PRX/…
[4] (No es gratuito) http://www.genetics.org/content/…
[5] (Gratis) http://www.seas.harvard.edu/cour…
[6] (Gratis) http://www-stat.stanford.edu/~cg…