Changes between Version 9 and Version 10 of OfficialTolArchiveNetworkBysSamplerRandWalkInPolytope

Timestamp:

Feb 1, 2011, 4:55:31 PM (14 years ago)

Author:

Víctor de Buen Remiro

Comment:

--

OfficialTolArchiveNetworkBysSamplerRandWalkInPolytope

@@ -7 +7 @@
 [[LatexEquation( A x \ge a \wedge x\in\mathbb{R}^{n} \wedge  a\in\mathbb{R}^{r} \wedge A\in\mathbb{R}^{r\times n} )]]
 
-caben dos posibilidades, utilizar un generador de candidatos que cumpla las restricciones por construcción o usar uno libre y luego rechazar los candidatos no factibles. La ventaja de este último es que puede ser simétrico y evita el cálculo de la verosimilitud del candidato pero el problema es que puede ser que tarde mucho en encontrar uno factible si el punto actual está demasiado cerca de la frontera, lo cual será muy habitual si el punto de máxima verosimilitud se encuentra fuera del politopo definido por las anteriores inecuaciones.
+caben dos posibilidades, utilizar un generador de candidatos que cumpla las restricciones por 
+construcción o usar uno libre y luego rechazar los candidatos no factibles. La ventaja de este 
+último es que puede ser simétrico y evita el cálculo de la verosimilitud del candidato pero el 
+problema es que puede ser que tarde mucho en encontrar uno factible si el punto actual está 
+demasiado cerca de la frontera, lo cual será muy habitual si el punto de máxima verosimilitud 
+se encuentra fuera del politopo definido por las anteriores inecuaciones.
 
-En la siguiente figura se observa un caso en el que el punto máximo verosímil sin restricciones (en verde) se encuentra fuera del politopo (en gris), por lo que el punto máximo-verosimil restringido (en rojo) se encuentra en la frontera del politopo. La cadena tenderá a estar cerca de ese punto y por tanto cerca de la frontera. Es evidente que cualquier entorno de generación simétrica de candidatos (en  rosa), tendrá como máximo la mitad de área en la zona factible, lo cual es perfectamente asumible. 
+En la siguiente figura se observa un caso en el que el punto máximo verosímil sin restricciones 
+(en verde) se encuentra fuera del politopo (en gris), por lo que el punto máximo-verosimil 
+restringido (en rojo) se encuentra en la frontera del politopo. La cadena tenderá a estar cerca 
+de ese punto y por tanto cerca de la frontera. Es evidente que cualquier entorno de generación 
+simétrica de candidatos (en  rosa), tendrá como máximo la mitad de área en la zona factible, lo 
+cual es perfectamente asumible. 
 
 [[Image(source:/tolp/OfficialTolArchiveNetwork/BysSampler/doc/image/RandWalk.InPolytope.chart.1026074815.png)]]
 
-Es claro que no es preciso que el punto se encuentre en la frontera para que sus entornos tengan incluso menos de la mitad, como ocurre con el entorno amarillo de la figura anterior. La pregunta es  ¿qué pasaría si no estuviera en la frontera por inclumplir sólo una de las restricciones sino que incumpliera varias al mismo tiempo? Pues que la probabilidad de generar un punto factible decrecería exponencialmente, dependiendo también de los ángulos formados por los hiperplanos que definen cada restricción. Y eso ya no es asumible a nada que se tengan 3 ó mas restricciones incumplidas. En dos dimensiones sólo se pueden cruzar dos restricciones activas al mismo tiempo pero es fácil de extrapolar lo que ocurriría en espacios de dimensiones más altas:
+Es claro que no es preciso que el punto se encuentre en la frontera para que sus entornos tengan 
+incluso menos de la mitad, como ocurre con el entorno amarillo de la figura anterior. La pregunta 
+es  ¿qué pasaría si no estuviera en la frontera por inclumplir sólo una de las restricciones sino 
+que incumpliera varias al mismo tiempo? Pues que la probabilidad de generar un punto factible 
+decrecería exponencialmente, dependiendo también de los ángulos formados por los hiperplanos que 
+definen cada restricción. Y eso ya no es asumible a nada que se tengan 3 ó mas restricciones 
+incumplidas. En dos dimensiones sólo se pueden cruzar dos restricciones activas al mismo tiempo 
+pero es fácil de extrapolar lo que ocurriría en espacios de dimensiones más altas:
 
 [[Image(source:/tolp/OfficialTolArchiveNetwork/BysSampler/doc/image/RandWalk.InPolytope.chart.726488582.png)]]
 
-== Diseño del generador ==
+== Diseños de generadores de candidatos factibles ==
 
-Se hace necesario por lo tanto disponer de un generador de candidatos que por construcción estén siempre dentro del politopo, es decir un generador de candidatos factibles. Tal generador no podrá ser simétrico por lo que será necesario no sólo poder generar muestras sino también calcular su densidad de una forma eficiente.
+Se hace necesario por lo tanto disponer de generadores de candidatos que por construcción estén siempre 
+dentro del politopo, es decir generadores de candidatos factibles. Tal generador no podrá ser simétrico 
+por lo que será necesario no sólo poder generar muestras sino también calcular su densidad de una forma 
+eficiente.
 
 === Definiciones ===
@@ -34 +54 @@
 [[LatexEquation( \left\langle x,\mathcal{P}\left(A,a\right)\right\rangle =  \underset{i=1\ldots r}{min}\left\{ \left\langle x,\mathcal{H}\left(A_i,a_i\right)\right\rangle \} > 0 )]]
 
-=== Distribución de los candidatos ===
-Se propone utilizar un generador con distribución uniforme en una hiperesfera centrada en el último punto generado y que esté incluida estrictamente en el politopo lo cual será cierto si el radio es menor que la distancia del punto a la frontera:
+=== Paseo aleatorio hiperesférico ===
+Se propone en primer lugar utilizar un generador con distribución uniforme en una hiperesfera centrada 
+en el último punto generado y que esté incluida estrictamente en el politopo lo cual será cierto si el 
+radio es menor que la distancia del punto a la frontera:
 
 [[LatexEquation( \begin{array}{c} y=x + h u\\ A y \leq a\\ \left\Vert u\right\Vert = 1 \\ 0 < h \le \rho < \left\langle x,\mathcal{P}\left(A,a\right)\right\rangle \end{array}  )]]
 
-Al igual que se hace con los generadores simétricos habituales es necesario fijar un tamaño de paso máximo [[LatexEquation(s)]] que para que se generen puntos no demasiado lejanos del acutual, de forma que el ratio de aceptación sea razonable.
+Al igual que se hace con los generadores simétricos habituales es necesario fijar un tamaño de paso 
+máximo [[LatexEquation(s)]] que para que se generen puntos no demasiado lejanos del acutual, de forma 
+que el ratio de aceptación sea razonable.
 De esta forma se podría definir el radio de la hiperesfera como
 
@@ -56 +80 @@
 [[LatexEquation( \ln Q\left(x,y\right) = n \ln \rho\left(x; s, \lambda\right))]]
 
-el cual depende de la posición del punto de partida respecto a las fronteras del politopo y no es por tanto un generador simétrico necesariamente, auqnue sí puede serlo eventualmente si el la distancia del punto a la frontera es menor que el tamaño de paso actual.
+el cual depende de la posición del punto de partida respecto a las fronteras del politopo y no es por 
+tanto un generador simétrico necesariamente, auqnue sí puede serlo eventualmente si el la distancia 
+del punto a la frontera es menor que el tamaño de paso actual.
 
 ==== Función generatriz ====
 
-Para generar un candidato [[LatexEquation(y)]] a partir del actual [[LatexEquation(x)]] con esta distribución se procederá como sigue
+Para generar un candidato [[LatexEquation(y)]] a partir del actual [[LatexEquation(x)]] con esta 
+distribución se procederá como sigue
 
  1. Primero se simulará un vector multinormal estandarizado [[BR]] [[BR]]
     [[LatexEquation(w\sim Normal\left(0,I\right)\in\mathbb{R}^{n} )]] [[BR]] [[BR]]
- 1. Dividiendo ese vector por su norma euclídea se obtendrá una dirección unitaria uniforme en la frontera de la hiperesfera de radio 1 centrada en el origen [[BR]] [[BR]]
+ 1. Dividiendo ese vector por su norma euclídea se obtendrá una dirección unitaria uniforme en la frontera 
+    de la hiperesfera de radio 1 centrada en el origen [[BR]] [[BR]]
     [[LatexEquation( u=\frac{w}{\left\Vert w\right\Vert _{2}}  )]] [[BR]] [[BR]]
- 1. Luego se multiplica ese vector por un radio [[LatexEquation(h)]] con densidad directamente proporcional a la hipersuperficie de dimensión n-1 de la hiperesfera correspondiente[[BR]] [[BR]]
+ 1. Luego se multiplica ese vector por un radio [[LatexEquation(h)]] con densidad directamente 
+    proporcional a la hipersuperficie de dimensión n-1 de la hiperesfera correspondiente[[BR]] [[BR]]
     [[LatexEquation( \begin{array}{c} F\left(h\right)=\intop_{0}^{h}c\cdot t^{n-1}\mathbf{d}t=\left.\frac{c}{n}t^{n}\right]_{0}^{h}=\frac{c}{n}h^{n}\\ F\left(\rho\right)=\frac{c}{n}\rho^{n}=1\Rightarrow c=n\rho^{-n}\\ F\left(h\right)=\left(\frac{h}{\rho}\right)^{n}\end{array} )]] [[BR]] [[BR]]
+
+=== Paseo aleatorio radial asimétrico ===
+Otra forma similar a la anterior pero que podría adaptarse mejor caundo el punto se acerca 
+demasiado a la frontera, e incluso es válido si está en la propia frontera.
+
+Se trataría de tomar una dirección unitaria aleatoria [[LatexEquation(u \wedge \left\Vert u\right\Vert = 1)]], 
+siguiendo los mismos dos pasos del punto anterior, y luego encontrar un intervalo en esa dirección que incluya 
+al punto actual pero no necesariamente centrado en él, para generar el candidato uniforme en dicho intervalo
+
+[[LatexEquation( y = x + h u )]]
+
+[[LatexEquation(h \sim U\left[\h^{-},h^{+}\right] \wedge \h^{-} \le 0 \ge h^{+}  )]]
+
+Los pasos para conseguirlo serían los siguientes
+ 1. Si los puntos [[LatexEquation( x - s u)]] y [[LatexEquation( x + s u)]] son ambos factibles
+    entonces se toma [[LatexEquation( h^{-} = -s)]] y [[LatexEquation( h^{+} = +s )]]
+ 1. Si [[LatexEquation( x - s u)]] no es factible habría que buscar mediante un método univariante 
+    como el de la bisectriz o el de Fibonacci el mínimo valor de [[LatexEquation( h^{-} )]] para el 
+    que el punto es factible, y que debe estar obligatoriamente en el intervalo 
+    [[LatexEquation(\left[-s,0\right]  )]]
+ 1. Análogamente, si [[LatexEquation( x + s u)]] no es factible habría que buscar el máximo valor 
+    de [[LatexEquation( h^{-} )]] para el que el punto es factible, y que debe estar obligatoriamente 
+    en el intervalo [[LatexEquation(\left[0,s\right]  )]]
+ 1. Si el intervalo es propio, es decir, si [[LatexEquation( h^{-} < h^{+})]], entonces ya se puede
+    generar la uniforme anterior. 
+ 1. Si el intervalo resulta ser un punto, o sea, [[LatexEquation( h^{-} = 0 = h^{+})]] entonces 
+    quiere decir que estamos en un vértice del politopo y hemos tomado una dirección completamente 
+    exterior