Changes between Version 42 and Version 43 of OfficialTolArchiveNetworkBysSamplerPostProccess

Timestamp:

Jan 9, 2011, 12:54:55 AM (14 years ago)

Author:

Víctor de Buen Remiro

Comment:

--

OfficialTolArchiveNetworkBysSamplerPostProccess

@@ -8 +8 @@
 ||''Tamaño de paso demasiado grande''||''Tamaño de paso demasiado pequeño''||
 
-Otra situación habitual es que los algoritmos pasan por un periodo de convergencia, normalmente al principio de la cadena, pero podría ocurrir en más ocasiones y entonces la técnica ''burn-in'' no es aplicable. Pero incluso cuando sólo ocurre al principio no es trivial establecer el número de muestras a eliminar.
 [[Image(source:/tolp/OfficialTolArchiveNetwork/BysSampler/doc/mcmc-post-filtering/mcmc.post-filter.004.gif)]]
 [[BR]]''Cadena de Markov con periodo de convergencia inicial (Vista parcial)''
@@ -15 +14 @@
 [[BR]]''La misma cadena anterior pero completa y vista como scatter''
 
-Tampoco existe ninguna forma trivial de aseverar que una cadena de Markov ha recorrido el dominio de la distribución de forma suficientemente exhaustiva, es decir, de asegurar que no hay lagunas inframuestreadas.
-
-Las cadenas simuladas con BysSampler cuentan con una ventaja adicional al conocerse el logaritmo de la verosimiltud de cada punto muestral, salvo una constante aditiva, pues esto permite contrastarla directamente con la masa local empírica, es decir el número de puntos que han sido generados en sus cercanías.
-
 [[Image(source:/tolp/OfficialTolArchiveNetwork/BysSampler/doc/mcmc-post-filtering/mcmc.post-filter.005.gif)]]
-[[BR]]''La misma cadena anterior junto a los valores de la función de densidad''
-
-En una cadena perfectamente muestreada el número de puntos generados en torno a un punto dado debería ser proporcional a la verosimilitud media alrededor de dicho punto. Esto permite diseñar un criterio completamente objetivo para eliminar puntos de zonas supoerpobladas e incluso sustituirlos por puntos en otras zonas inframuestreadas.
-
-[[Image(source:/tolp/OfficialTolArchiveNetwork/BysSampler/doc/mcmc-post-filtering/mcmc.post-filter.006.png)]]
-[[BR]]''Función de densidad (salvo una constante) de la cadena de Markov anterior''
+[[BR]]''La misma cadena anterior (abajo) junto a los valores de la función de densidad (arriba)''
+
+|| Otra situación habitual es que los algoritmos pasan por un periodo de convergencia, normalmente al principio de la cadena, pero podría ocurrir en más ocasiones y entonces la técnica ''burn-in'' no es aplicable. Pero incluso cuando sólo ocurre al principio no es trivial establecer el número de muestras a eliminar.[[BR]][[BR]] Tampoco existe ninguna forma trivial de aseverar que una cadena de Markov ha recorrido el dominio de la distribución de forma suficientemente exhaustiva, es decir, de asegurar que no hay lagunas inframuestreadas.[[BR]][[BR]]Las cadenas simuladas con BysSampler cuentan con una ventaja adicional al conocerse el logaritmo de la verosimiltud de cada punto muestral, salvo una constante aditiva, pues esto permite contrastarla directamente con la masa local empírica, es decir el número de puntos que han sido generados en sus cercanías.[[BR]][[BR]]En una cadena perfectamente muestreada el número de puntos generados en torno a un punto dado debería ser proporcional a la verosimilitud media alrededor de dicho punto. Esto permite diseñar un criterio completamente objetivo para eliminar puntos de zonas supoerpobladas e incluso sustituirlos por puntos en otras zonas inframuestreadas.[[BR]][[BR]]En la gráfica de la derecha se observa muy claramente que hay demasiados puntos con muy poca probabilidad, y lo que se pretende aquí es crear un sistema que sea capaz de detectar y subsanar este tipo de problemas para cualquier número de dimensiones. || [[Image(source:/tolp/OfficialTolArchiveNetwork/BysSampler/doc/mcmc-post-filtering/mcmc.post-filter.006.png)]][[BR]]''Función de densidad (salvo una constante) de la cadena de Markov anterior'' ||
+
 
 == Diseño de entornos locales solapados ==
 
-El método propuesto comenzará por utilizar el algoritmo [http://es.wikipedia.org/wiki/Knn KNN] que está disponible dentro del paquete TOL MatQuery, para encontrar los vecinos más próximos de cada punto de la muestra de tamaño [[LatexEquation( S )]]. Como en los métodos de simulación tipo ''accept-reject'' hay por definición puntos repetidos, para que el algoritmo tenga sentido habría que tomar los [[LatexEquation( S' \leq S )]] puntos únicos 
+Buscamos una forma de contrastar la proporción respecto del total de los puntos que hay en una zona determinada del espacio recorrido con la probabilidad de esa zona correspondiente a la función de densidad que es conocida en cada punto de la muestra, y queremos hacerlo para cualquier zona analizada. Evidentemente esto es demasiado abstracto para ser implementado y hay que concretar qué tipo de zonas queremos contrastar, qué forma y qué tamaño deben tener y cómo construirlas de forma que efectivamente abarquen todo el espacio objetivo.
+
+El método propuesto comenzará por utilizar el algoritmo [http://es.wikipedia.org/wiki/Knn KNN] que está disponible dentro del paquete TOL MatQuery, para encontrar los vecinos más próximos de cada punto de la muestra de tamaño [[LatexEquation( S )]] de una forma muy eficiente. Concretamente la librería que se usa es [http://www.cs.umd.edu/~mount/ANN/ Approximate Nearest Neighbor Searching (ANN)] de David M. Mount and Sunil Arya. Esto nos permitirá definir entornos esféricos centrados en cada uno de los puntos de la muestra, lo cual asegura la cobertura total de la muestra sin ningún género de dudas.
+
+Como en los métodos de simulación tipo ''accept-reject'' hay por definición puntos repetidos, para que el algoritmo tenga sentido habría que tomar los [[LatexEquation( S' \leq S )]] puntos únicos 
 
   [[LatexEquation( x_{i} \in\mathbb{R}^{n} \forall i=1 \dots S' )]]
@@ -71 +68 @@
 == Distribución del tamaño muestral local ==
 
-Así las cosas tenemos que el tamaño muestral local, es decir, el número total de puntos muestrales en [[LatexEquation( \Omega_{i} )]], es
+En una muestra aleatoria perfecta de la función de distribución, cada punto generado es independiente de los demás y la probabilidad de que caiga precisamente en LatexEquation( \Omega_{i} )]] es la integral de la función de densidad en dicho entorno local
+
+  [[LatexEquation( p_{i}=\int_{\Omega_{i}}\pi\left(y\right)\mathrm{d}y  )]]
+
+El tamaño muestral local, es decir, el número total de puntos muestrales en [[LatexEquation( \Omega_{i} )]], es
 
   [[LatexEquation( h_{i} = k+s_i )]]
-
-cantidad que se distribuye como una binomial
+  
+cantidad que se distribuye evidentemente como una binomial
 
   [[LatexEquation( \eta_{i} = B\left(S, p_i\rigtht))]]
-
-donde [[LatexEquation( p_i )]] es la probabilidad de la hiperesfera, es decir, la integral de la función de densidad en cada entorno local
-
-  [[LatexEquation( p_{i}=\int_{\Omega_{i}}\pi\left(y\right)\mathrm{d}y  )]]
 
 La esperanza del tamaño muestral local es
@@ -97 +94 @@
   [[LatexEquation( p_{i}=\frac{1}{N}\underset{j=1}{\overset{N}{\sum}}\pi\left(z_{i,j}\right)V\left(\Omega_{i}\right)\wedge z_{i,j}\in\Omega_{i}\forall j=1\ldots N\wedge i=1\ldots S' )]]
   
-El error en este tipo de aproximaciones decrece proporcionalmente a la raíz del número de puntos en el que evaluamos la verosimilitud pero sólo tenemos [[LatexEquation( k+1 )]] puntos interiores. Por otra parte tampoco conocemos la verosimilitud sino una función porporcional a la misma. Es decir, lo único conocemos sin coste adicional es el logaritmo de la verosimilitud, salvo una constante [[LatexEquation(\lambda_1)]] desconocida, evaluado en cada uno de los puntos muestrales, es decir, conocemos
+El error en este tipo de aproximaciones decrece proporcionalmente a la raíz del número de puntos en el que evaluamos la verosimilitud pero sólo tenemos [[LatexEquation( k+1 )]] puntos interiores. Por otra parte tampoco conocemos la verosimilitud sino una función porporcional a la misma. Es decir, lo único que conocemos sin coste adicional es el logaritmo de la verosimilitud, salvo una constante [[LatexEquation(\lambda_1)]] desconocida, evaluado en cada uno de los puntos muestrales, es decir, conocemos
 
   [[LatexEquation( \ln\pi_{i}=\ln\pi\left(x_{i}\right)+\lambda_1 )]]
 
   [[LatexEquation( \ln\pi_{i,j}=\ln\pi\left(y_{i,j}\right)+\lambda_1 )]]
-  
 
 Como evaluar la función demasiadas veces podría ser muy costoso la única forma de mejorar la aproximación de la integral es por interpolación, concretamente mediante el [http://www.alglib.net/interpolation/inversedistanceweighting.php método de Sheppard de ponderación inversa a la distancia] que es muy eficiente pues no requiere de ninguna evaluación extra. Esto es especialemente recomendable si existen grandes diferencias en las verosimilitudes de los distintos puntos del vecindario. La interpolación será mejor realizarla en términos logarítmicos pues eso suavizará la función.
@@ -114 +110 @@
   [[LatexEquation( \ln\pi\left(z\right)-\lambda_{1}\backsimeq\ln\tilde{\pi}\left(z\right)=\frac{\underset{j=0}{\overset{k}{\sum}}w_{j}\left(z\right)\ln\pi_{i,j}}{\underset{j=0}{\overset{k}{\sum}}w_{j}\left(z\right)}\wedge y_{i,0}=x_{i}\wedge\pi_{i,0}=\pi_{i}\wedge w_{j}\left(z\right)=\left\Vert z-y_{i,j}\right\Vert ^{-2}  )]]
     
-Si el número [[LatexEquation( k+1 )]] de puntos básicos de la interpolación [[LatexEquation( y_{i,j} \wedge j=0 \dots k)]], es demasiado pequeño se puede ampliar con sus vecinos, los vecinos de sus vecinos y así sucesivamente hasta que haya suficientes puntos básicos distintos. Gracias al algoritmo KNN esto no supondrá apenas ningún sobrecoste.
+Si el número [[LatexEquation( k+1 )]] de puntos básicos de la interpolación [[LatexEquation( y_{i,j} \wedge j=0 \dots k)]], es demasiado pequeño se puede ampliar con sus vecinos, los vecinos de sus vecinos y así sucesivamente hasta que haya suficientes puntos básicos distintos. Gracias al algoritmo KNN realizado anteriormente esto no supondrá apenas ningún sobrecoste.
     
 Nos queda finalmente la fórmula de aproximación 
@@ -146 +142 @@
   [[LatexEquation( \mu_{0}\approx\tilde{\mu}_{0}=Log\left(\underset{i=1}{\overset{S'}{\sum}}h_{i}\right)-Log\left(\underset{i=1}{\overset{S'}{\sum}}e^{\nu_{i}}\right)-Log\left(S\right) )]]
     
-Sin embargo, esta aproximación sólo es adecuada para muestras exactas, y puesto que existen serias sospechas sobre exceso de repeticiones y lagunas inframuestreadas, es posible que necesitemos un criterio más robusto para establecer cuál debe ser el valor de la constante [[LatexEquation( \mu_{0} )]]. Dado que conocemos la forma de la distribución podemos encontrar su valor máximo-verosímil. Lo que sí es posible hacer es utilizar la anterior aproximación para establecer un buen intervalo para el algoritmo de optimización que es algo que facilita mucho el trabajo.
+Sin embargo, esta aproximación sólo es adecuada para muestras exactas, y puesto que existen serias sospechas sobre exceso de repeticiones y lagunas inframuestreadas, es posible que necesitemos un criterio más robusto para establecer cuál debe ser el valor de la constante [[LatexEquation( \mu_{0} )]]. Dado que conocemos la forma de la distribución podemos encontrar su valor máximo-verosímil. Lo que sí es posible hacer es utilizar la anterior aproximación para establecer un buen intervalo para el algoritmo de optimización que es algo que facilita mucho el trabajo. ''(Pendiente de desarrollo)''
 
 === Estimación de la constante ===
@@ -211 +207 @@
   [[LatexEquation( \mathrm{Pr}\left[\eta_{i}\geq h_{i}\right] \leq \alpha_1)]]
 
+''(Pendiente de desarrollo)''
   
 === Colonización de zonas infreamuestreadas ===
@@ -226 +223 @@
 Una posibilidad sería continuar el mismo método utilizado en la generación de la muestra analizada comenzando por los puntos centrales de los entornos más despoblados hasta compensar la masa faltante. 
 Pero dada la información acumulada sería quizás más razonable utilizar un generador de candidatos con media en los puntos centrales en lugar de usar un paseo aleatorio. Incluso se podría usar el método de ensayo múltiple generalizado usando como precandidatos los mismos puntos generados anteriormente para la aproximación de la integral.
+
+''(Pendiente de desarrollo)''