| 1 |
""" |
| 2 |
Adaptive Rejection Sampling (ARS) |
| 3 |
|
| 4 |
The ARS class generates a single random sample from a |
| 5 |
univariate distribution specified by an instance of the |
| 6 |
LogProb class, implemented by the user. An instance of |
| 7 |
LogProb returns the log of the probability density and |
| 8 |
its derivative. The log probability function passed must |
| 9 |
be concave. |
| 10 |
|
| 11 |
The user must also supply initial guesses. It is not |
| 12 |
essential that these values be very accurate, but performance |
| 13 |
will generally depend on their accuracy. |
| 14 |
""" |
| 15 |
|
| 16 |
from numpy import exp, log |
| 17 |
|
| 18 |
class Envelope(object): |
| 19 |
""" |
| 20 |
Envelope function for adaptive rejection sampling. |
| 21 |
|
| 22 |
The envelope defines a piecewise linear upper and lower |
| 23 |
bounding function of the concave log-probability. |
| 24 |
""" |
| 25 |
def __init__(self, x, h, dh): |
| 26 |
|
| 27 |
from numpy import array, inf |
| 28 |
|
| 29 |
self.x = array(x) |
| 30 |
self.h = array(h) |
| 31 |
self.dh = array(dh) |
| 32 |
self.z0 = -inf |
| 33 |
self.zk = inf |
| 34 |
|
| 35 |
def z(self): |
| 36 |
""" |
| 37 |
Support intervals for upper bounding function. |
| 38 |
""" |
| 39 |
from numpy import concatenate |
| 40 |
|
| 41 |
h = self.h |
| 42 |
dh = self.dh |
| 43 |
x = self.x |
| 44 |
|
| 45 |
z = (h[1:] - h[:-1] + x[:-1] * dh[:-1] - x[1:] * dh[1:]) / \ |
| 46 |
(dh[:-1] - dh[1:]) |
| 47 |
|
| 48 |
return concatenate(([self.z0], z, [self.zk])) |
| 49 |
|
| 50 |
def u(self, x): |
| 51 |
""" |
| 52 |
Piecewise linear upper bounding function. |
| 53 |
""" |
| 54 |
z = self.z()[1:-1] |
| 55 |
j = (x > z).sum() |
| 56 |
|
| 57 |
return self.h[j] + self.dh[j] * (x - self.x[j]) |
| 58 |
|
| 59 |
def u_max(self): |
| 60 |
|
| 61 |
z = self.z()[1:-1] |
| 62 |
|
| 63 |
return (self.h + self.dh * (z - self.x)).max() |
| 64 |
|
| 65 |
def l(self, x): |
| 66 |
""" |
| 67 |
Piecewise linear lower bounding function. |
| 68 |
""" |
| 69 |
from numpy import inf |
| 70 |
|
| 71 |
j = (x > self.x).sum() |
| 72 |
|
| 73 |
if j == 0 or j == len(self.x): |
| 74 |
return -inf |
| 75 |
else: |
| 76 |
j -= 1 |
| 77 |
return ((self.x[j + 1] - x) * self.h[j] + (x - self.x[j]) * self.h[j + 1]) / \ |
| 78 |
(self.x[j + 1] - self.x[j]) |
| 79 |
|
| 80 |
def insert(self, x, h, dh): |
| 81 |
""" |
| 82 |
Insert new support point for lower bounding function |
| 83 |
(and indirectly for upper bounding function). |
| 84 |
""" |
| 85 |
from numpy import concatenate |
| 86 |
|
| 87 |
j = (x > self.x).sum() |
| 88 |
|
| 89 |
self.x = concatenate((self.x[:j], [x], self.x[j:])) |
| 90 |
self.h = concatenate((self.h[:j], [h], self.h[j:])) |
| 91 |
self.dh = concatenate((self.dh[:j], [dh], self.dh[j:])) |
| 92 |
|
| 93 |
def log_masses(self): |
| 94 |
|
| 95 |
from numpy import abs, putmask |
| 96 |
|
| 97 |
z = self.z() |
| 98 |
b = self.h - self.x * self.dh |
| 99 |
a = abs(self.dh) |
| 100 |
m = (self.dh > 0) |
| 101 |
q = self.x * 0. |
| 102 |
putmask(q, m, z[1:]) |
| 103 |
putmask(q, 1 - m, z[:-1]) |
| 104 |
|
| 105 |
log_M = b - log(a) + log(1 - exp(-a * (z[1:] - z[:-1]))) + \ |
| 106 |
self.dh * q |
| 107 |
|
| 108 |
return log_M |
| 109 |
|
| 110 |
def masses(self): |
| 111 |
|
| 112 |
z = self.z() |
| 113 |
b = self.h - self.x * self.dh |
| 114 |
a = self.dh |
| 115 |
|
| 116 |
return exp(b) * (exp(a * z[1:]) - exp(a * z[:-1])) / a |
| 117 |
|
| 118 |
def sample(self): |
| 119 |
|
| 120 |
from numpy.random import random |
| 121 |
from numpy import add |
| 122 |
from csb.numeric import log_sum_exp |
| 123 |
|
| 124 |
log_m = self.log_masses() |
| 125 |
log_M = log_sum_exp(log_m) |
| 126 |
c = add.accumulate(exp(log_m - log_M)) |
| 127 |
u = random() |
| 128 |
j = (u > c).sum() |
| 129 |
|
| 130 |
a = self.dh[j] |
| 131 |
z = self.z() |
| 132 |
|
| 133 |
xmin, xmax = z[j], z[j + 1] |
| 134 |
|
| 135 |
u = random() |
| 136 |
|
| 137 |
if a > 0: |
| 138 |
return xmax + log(u + (1 - u) * exp(-a * (xmax - xmin))) / a |
| 139 |
else: |
| 140 |
return xmin + log(u + (1 - u) * exp(a * (xmax - xmin))) / a |
| 141 |
|
| 142 |
|
| 143 |
class LogProb(object): |
| 144 |
|
| 145 |
def __call__(self, x): |
| 146 |
raise NotImplementedError() |
| 147 |
|
| 148 |
class Gauss(LogProb): |
| 149 |
|
| 150 |
def __init__(self, mu, sigma=1.): |
| 151 |
|
| 152 |
self.mu = float(mu) |
| 153 |
self.sigma = float(sigma) |
| 154 |
|
| 155 |
def __call__(self, x): |
| 156 |
|
| 157 |
return -0.5 * (x - self.mu) ** 2 / self.sigma ** 2, \ |
| 158 |
- (x - self.mu) / self.sigma ** 2 |
| 159 |
|
| 160 |
|
| 161 |
class ARS(object): |
| 162 |
|
| 163 |
from numpy import inf |
| 164 |
|
| 165 |
def __init__(self, logp): |
| 166 |
|
| 167 |
self.logp = logp |
| 168 |
|
| 169 |
def initialize(self, x, z0=-inf, zmax=inf): |
| 170 |
|
| 171 |
from numpy import array |
| 172 |
|
| 173 |
self.hull = Envelope(array(x), *self.logp(array(x))) |
| 174 |
self.hull.z0 = z0 |
| 175 |
self.hull.zk = zmax |
| 176 |
|
| 177 |
def sample(self, maxiter=100): |
| 178 |
|
| 179 |
from numpy.random import random |
| 180 |
|
| 181 |
for i in range(maxiter): |
| 182 |
|
| 183 |
x = self.hull.sample() |
| 184 |
l = self.hull.l(x) |
| 185 |
u = self.hull.u(x) |
| 186 |
w = random() |
| 187 |
|
| 188 |
if w <= exp(l - u): return x |
| 189 |
|
| 190 |
h, dh = self.logp(x) |
| 191 |
|
| 192 |
if w <= exp(h - u): return x |
| 193 |
|
| 194 |
self.hull.insert(x, h, dh) |