iid Bernoulli
model
Here we assume that the data \(y_{1:n}=\{y_1,\ldots,y_n\}\) is modeled as
a random sample from \(Bernoulli(\theta)\). In our classroom
example, the binary random variable \(y_i=1\) if individual \(i\) (attending the class) has three or more
siblings, including himself or herself, with \(y_i=0\), otherwise. One of the main goals
is to access the uncertainty around \(\theta\), i.e. the posterior \(p(\theta|y_{1:n})\), and then obtain \(Pr(y_{n+1}=1|y_{1:n})\), the probability
that the \((n+1)\) individual has three
or more siblings, including himself or herself.
Maximum likelihood
estimation
From basic likelihood-based statistical inference, it is easy to see
that \[
{\widehat \theta}_{mle} \equiv \mbox{arg}\max_{\theta \in (0,1)}
L(\theta;y_{1:n}),
\] where the likelihood function \(L(\theta;\mbox{data})\) is given by \[
L(\theta;\mbox{data}) = \prod_{i=1}^n \theta^{y_i}(1-\theta)^{1-y_i} =
\theta^{s_n}(1-\theta)^{n-s_n},
\] where \(s_n = \sum_{i=1}^n
y_i\) is the number of sucesses out of \(n\) (Bernoulli) trials. We compute the MLE
of \(\theta\) based on \(n=10\) observations and \(y_{1:10}=\{0,0,0,1,0,1,0,1,0,1\}\), so
$s_{10}=4 and \({\widehat
\theta}_{mle}=4/10=0.4\).
n = 10
y = c(0,0,0,1,0,1,0,1,0,1)
s = sum(y==1)
mle = s/n
c(n,s,mle)
## [1] 10.0 4.0 0.4
Prior, likelihood and
posterior for \(\theta\)
We have elicited a prior for \(\theta\) in class (with the help of
Vitória) and arrived at the following Beta distribution: \(\theta \sim Beta(a,b)\) where \(a=2\) and \(b=6\), such that \[\begin{eqnarray*}
E(\theta) &=& \frac{a}{a+b}\\
Mode(\theta) &=& \frac{a-1}{a+b-2}, \quad \qquad a,b>1\\
Median(\theta) &=& \frac{a-1/3}{a+b-2/3}, \qquad a,b>1 \ \
\mbox{(approximation)}
\end{eqnarray*}\]
a = 2
b = 5
E = a/(a+b)
Mo = (a-1)/(a+b-2)
Me = (a-1/3)/(a+b-2/3)
c(E,Mo,Me)
## [1] 0.2857143 0.2000000 0.2631579
The Bernoulli likelihood and the Beta prior conjugate, which means
that the posterior for \(\theta\) also
follow a Beta distribution. The conjugacy property makes the Bayesian
updating straightforward: \[\begin{eqnarray*}
p(\theta|y_{1:n},a,b) &\equiv& p(\theta|n,s_n,a,b) =
\frac{\left\{\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}\theta^{a-1}(1-\theta)^{b-1}\right\}
\theta^{s_n}(1-\theta)^{n-s_n}}{p(y_{1:n}|a,b)}\\
&\propto& \theta^{a+s_n-1}(1-\theta)^{b+n-s_n-1} \equiv
\theta^{a_n-1}(1-\theta)^{b_n-1},
\end{eqnarray*}\] where \[
p(y_{1:n}|n,a,b)=\int_0^1 \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}
\theta^{a-1}(1-\theta)^{b-1} \theta^{s_n}(1-\theta)^{n-s_n}d\theta =
\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}
\frac{\Gamma(a+s_n)\Gamma(b+n-s_n)}{\Gamma(a+b+n)},
\] is the normalizing constant, also known as marginal likelihood
or prior predictive, or even simply predictive.
It is easy to see that the posterior distribution of \(\theta\) is Beta with hypeparameters \[
a_n = a + s_n \ \ \ \mbox{and} \ \ \ b_n = b + n - s_n.
\] Therefore, \[\begin{eqnarray*}
E(\theta|y_{1:n},a,b) &=& \frac{a+s_n}{a+b+n},\\
Mode(\theta|y_{1:n},a,b) &=& \frac{a+s_n-1}{a+b+n-1},\\
Median(\theta|y_{1:n},a,b) &=& \frac{a+s_n-1/3}{a+b+n-2/3}.
\end{eqnarray*}\]
a1 = a+s
b1 = b+n-s
E1 = a1/(a1+b1)
Mo1 = (a1-1)/(a1+b1-2)
Me1 = (a1-1/3)/(a1+b1-2/3)
tab = rbind(c(E,Mo,Me),c(E1,Mo1,Me1))
colnames(tab) = c("Mean","Mode","Median")
rownames(tab) = c("Prior","Posterior")
round(tab,3)
## Mean Mode Median
## Prior 0.286 0.200 0.263
## Posterior 0.353 0.333 0.347
predictive1 = (gamma(a+b)/(gamma(a)*gamma(b)))*gamma(a1)*gamma(b1)/gamma(a1+b1)
predictive1
## [1] 0.0006243756
Output: Prior and
posterior densities
theta = seq(0,1,length=1000)
par(mfrow=c(1,1))
plot(theta,dbeta(theta,a,b),type="l",lwd=2,ylim=c(0,4),xlab=expression(theta),ylab="Density")
lines(theta,dbeta(theta,a1,b1),col=2,lwd=2)
abline(v=E)
abline(v=Mo,lty=2)
abline(v=Me,lty=3)
abline(v=E1,col=2)
abline(v=Mo1,lty=2,col=2)
abline(v=Me1,lty=3,col=2)
abline(v=mle,col=3,lwd=2)
legend("topright",legend=c("Prior density","Posterior density"),col=1:2,lty=1,bty="n",lwd=2)
legend("right",legend=c("Mean","Mode","Median","MLE"),lty=c(1:3,1),col=c(1,1,1,3),bty="n",lwd=2)
Logit Bernoulli
model
We now bring to our modeling exercise the covariate \(x_i\) with is also binary with \(x_i=0\) if the age of the respondent \(i\) is less than 30, while \(x_i=1\) if the age is greater than equal to
30. In this way, this more complex model is given by \[
y_i|x_i,\theta \sim Bernoulli(\theta_i),
\] where \[
\log\left(\frac{\theta_i}{1-\theta_i}\right) = \alpha + \beta x_i,
\] such that \[\begin{eqnarray*}
\theta_i &=& \frac{1}{1+\exp\{-\alpha\}} = \pi_0, \qquad
\mbox{when} \ \ x_i=0\\
\theta_i &=& \frac{1}{1+\exp\{-(\alpha+\beta)\}} = \pi_1, \qquad
\mbox{when} \ \ x_i=1.
\end{eqnarray*}\]
In words, \(\theta_i\) can take only
two possible values, the probabilities \(\pi_0\) and \(\pi_1\), which are equivalent to the
probability \(\theta\) from the iid
Bernoulli model.
n = 10
y = c(0,0,0,1,0,1,0,1,0,1)
x = c(1,0,0,1,0,0,0,1,0,1)
n0 = sum(x==0)
n1 = sum(x==1)
s0 = sum(y[x==0])
s1 = sum(y[x==1])
c(n0,n1,s0,s1)
## [1] 6 4 1 3
Posterior
inference
Posterior inference for \(\pi_0\)
and \(\pi_1\) (or \(\alpha,\beta\)) is unavailable in closed
form. We will us Monte Carlo method (here we use sampling importance
resampling, SIR) to be able to approximate the posterior distribution
and compute posterior means, modes, medians and other posterior
summaries as needed.
Prior on \((\alpha,\beta)\)
We will assume \(\alpha\) and \(\beta\) are, a priori, independent
Gaussians: \[
p(\alpha,\beta)=p(\alpha|\mu_\alpha,\sigma_\alpha^2)p(\beta|\mu_\beta,\sigma_\beta^2),
\] with hyperparameters \(\mu_\alpha=-0.7\), \(\mu_\beta=1.4\) and \(\sigma_\mu=\sigma_\beta=1\). The intuition
is that these marginal priors induce prior means for \(\pi_0\) and \(\pi_1\) around the following values: \[
\frac{1}{1+\exp\{0.7\}} \approx 1/3 \qquad \mbox{and} \qquad
\frac{1}{1+\exp\{0.7-1.4\}} \approx 2/3.
\] Below we show draws from the induced prior on \((\pi_0,\pi_1)\).
M = 10000
alpha = rnorm(M,-0.7,1)
beta = rnorm(M,1.4,1)
# Induced prior on (pi0,pi1)
pi0 = 1/(1+exp(-alpha))
pi1 = 1/(1+exp(-alpha-beta))
par(mfrow=c(2,2))
plot(alpha,beta,xlab=expression(alpha),ylab=expression(beta))
boxplot(alpha,alpha+beta,outline=FALSE,names=c(expression(alpha),expression(alpha+beta)))
plot(pi0,pi1,xlim=c(0,1),ylim=c(0,1),xlab=expression(pi[0]),ylab=expression(pi[1]))
abline(0,1,col=2,lwd=2)
boxplot(1/(1+exp(-alpha)),1/(1+exp(-alpha-beta)),names=c("Age<30 (i=0)","Age>=30 (i=1)"),ylab=expression(pi[i]))
Monte Carlo-based
posterior inference
Obviously, the posterior distribution of \((\alpha,\beta)\) is of no known form and
analytically intractable: \[
p(\alpha,\beta|y_{1:n},n,\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)
\propto
p(\alpha,\beta|\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)\prod_{i=1}^n
\theta_i^{y_i}(1-\theta_i)^{1-y_i}.
\] Recall that \(\theta_i =
1/(1+\exp\{-(\alpha+\beta x_i)\})\), for \(i=1,\ldots,n\), so the likelihood is a
function of \((\alpha,\beta)\).
As we will see throughout this course, Monte Carlo-based posterior
inference has become the most common scheme to be able to accurately
approximate highly complex posterior distributions. The the dimension of
the parameter is relatively low (here we have \(\alpha\) and \(\beta\), so 2-dimensional) a simple
strategy is to sample draws from the prior and resample those draws with
weights proportional to the likelihood, which translates into the
well-known sampling importance resampling (SIR) scheme. The
course notes is full of examples illustrating the implementation, and
drawbacks, of SIR-based posterior inference. For now, let us just assume
the following piece of code does the magic:
like = rep(0,M)
for (i in 1:M)
like[i] = pi0[i]^s0*(1-pi0[i])^(n0-s0)*pi1[i]^s1*(1-pi1[i])^(n1-s1)
predictive2 = mean(like)
ind = sample(1:M,size=M,replace=TRUE,prob=like)
pi0.post = pi0[ind]
pi1.post = pi1[ind]
alpha.post = alpha[ind]
beta.post = beta[ind]
predictive2
## [1] 0.002290277
The variables pi0.post and pi1.post are samples (draws) from the
joint posterior distribution \(p(\alpha,\beta|y_{1:n},n,\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)\).
Similarly for alpha.post and beta.post.
Graphical output
par(mfrow=c(2,2))
plot(pi0,pi1,xlim=c(0,1),ylim=c(0,1),xlab=expression(pi[0]),ylab=expression(pi[1]))
points(pi0.post,pi1.post,col=2)
legend("bottomright",legend=c("Prior draws","Posterior draws"),col=1:2,pch=16,bty="n")
plot(alpha,beta,xlab=expression(alpha),ylab=expression(beta))
points(alpha.post,beta.post,col=2)
title(paste("Correlation=",round(cor(alpha.post,beta.post),2),sep=""))
plot(density(pi0),ylim=c(0,4),xlim=c(0,1),main="",xlab=expression(pi[0]))
lines(density(pi0.post),col=2)
legend("topright",legend=c(expression(x[i]==0)))
plot(density(pi1),ylim=c(0,3),xlab=expression(pi[1]),xlim=c(0,1),main="")
lines(density(pi1.post),col=2)
legend("topright",legend=c(expression(x[i]==1)))
Comparing the two
Bernoulli models
par(mfrow=c(1,1))
plot(theta,dbeta(theta,a1,b1),type="l",lwd=2,ylim=c(0,4),
xlab="Probability of sucess",ylab="Posterior density")
lines(density(pi0[ind]),col=2,lwd=2)
lines(density(pi1[ind]),col=3,lwd=2)
legend("topright",legend=c(expression(theta),expression(pi[0]),expression(pi[1])),lty=1,lwd=2,col=1:3,bty="n")
A few commonly used posterior summaries are as follows:
tab = rbind(
qbeta(c(0.05,0.5,0.95),a1,b1),
quantile(pi0[ind],c(0.05,0.5,0.95)),
quantile(pi1[ind],c(0.05,0.5,0.95)))
rownames(tab) = c("theta","pi0","pi1")
round(tab,2)
## 5% 50% 95%
## theta 0.18 0.35 0.55
## pi0 0.11 0.27 0.50
## pi1 0.36 0.68 0.90
Bayes factor
Let call the iid Bernoulli model \(M_1\), while the logit Bernoulli model
\(M_2\). Then, the Bayes factor is
defined as \[
BF_{12} =
\frac{p(y_{1:n}|a,b)}{p(y_{1:n}|x_{1:n},\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)}
\approx
\frac{p(y_{1:n}|a,b)}{p_{SIR}(y_{1:n}|x_{1:n},\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)},
\] where \(p_{SIR}(y_{1:n}|x_{1:n},\mu_\alpha,\sigma_\alpha,\mu_\beta,\sigma_\beta)\)
is the SIR-based approximatin to the prior predictive under the logit
Bernoulli model. We will explain why that is correct later!
c(predictive1,predictive2)
## [1] 0.0006243756 0.0022902770
BF12 = predictive1/predictive2
BF21 = 1/BF12
BF21
## [1] 3.668108
In a review paper entitled Bayes Factors, that appeared in
JASA in 1995 (Volume 90, Issue 430), Robert E. Kass and Adrian E.
Raftery suggested the following rule of thumb in order to quantity
evidence against \(M_1\):
- \(B_{21} \in (1,3)\): Not worth
more than a bare mention
- \(B_{21} \in (3,20)\):
Positive
- \(B_{21} \in (20,150)\):
Strong
- \(B_{21} \in (150,\infty)\): Very
strong.
Therefore, in our case, the data provides positive evidence against
\(M_1\).
LS0tCnRpdGxlOiAiVHdvIEJlcm5vdWxsaSBtb2RlbHMiCmF1dGhvcjogIkhlZGliZXJ0IEZyZWl0YXMgTG9wZXMiCmRhdGU6ICI4LzI3LzIwMjQiCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDMKICAgIHRvY19jb2xsYXBzZWQ6IHRydWUKICAgIGNvZGVfZG93bmxvYWQ6IHllcwogICAgbnVtYmVyX3NlY3Rpb25zOiB0cnVlCi0tLQoKIyBpaWQgQmVybm91bGxpIG1vZGVsCkhlcmUgd2UgYXNzdW1lIHRoYXQgdGhlIGRhdGEgJHlfezE6bn09XHt5XzEsXGxkb3RzLHlfblx9JCBpcyBtb2RlbGVkIGFzIGEgcmFuZG9tIHNhbXBsZSBmcm9tICRCZXJub3VsbGkoXHRoZXRhKSQuICBJbiBvdXIgY2xhc3Nyb29tIGV4YW1wbGUsIHRoZSBiaW5hcnkgcmFuZG9tIHZhcmlhYmxlICR5X2k9MSQgaWYgaW5kaXZpZHVhbCAkaSQgKGF0dGVuZGluZyB0aGUgY2xhc3MpIGhhcyB0aHJlZSBvciBtb3JlIHNpYmxpbmdzLCBpbmNsdWRpbmcgaGltc2VsZiBvciBoZXJzZWxmLCB3aXRoICR5X2k9MCQsIG90aGVyd2lzZS4gIE9uZSBvZiB0aGUgbWFpbiBnb2FscyBpcyB0byBhY2Nlc3MgdGhlIHVuY2VydGFpbnR5IGFyb3VuZCAkXHRoZXRhJCwgaS5lLiB0aGUgcG9zdGVyaW9yICRwKFx0aGV0YXx5X3sxOm59KSQsIGFuZCB0aGVuIG9idGFpbiAkUHIoeV97bisxfT0xfHlfezE6bn0pJCwgdGhlIHByb2JhYmlsaXR5IHRoYXQgdGhlICQobisxKSQgaW5kaXZpZHVhbCBoYXMgdGhyZWUgb3IgbW9yZSBzaWJsaW5ncywgaW5jbHVkaW5nIGhpbXNlbGYgb3IgaGVyc2VsZi4KCiMjIE1heGltdW0gbGlrZWxpaG9vZCBlc3RpbWF0aW9uCkZyb20gYmFzaWMgbGlrZWxpaG9vZC1iYXNlZCBzdGF0aXN0aWNhbCBpbmZlcmVuY2UsIGl0IGlzIGVhc3kgdG8gc2VlIHRoYXQKJCQKe1x3aWRlaGF0IFx0aGV0YX1fe21sZX0gXGVxdWl2IFxtYm94e2FyZ31cbWF4X3tcdGhldGEgXGluICgwLDEpfSBMKFx0aGV0YTt5X3sxOm59KSwKJCQKd2hlcmUgdGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gJEwoXHRoZXRhO1xtYm94e2RhdGF9KSQgaXMgZ2l2ZW4gYnkKJCQKTChcdGhldGE7XG1ib3h7ZGF0YX0pID0gXHByb2Rfe2k9MX1ebiBcdGhldGFee3lfaX0oMS1cdGhldGEpXnsxLXlfaX0gPSBcdGhldGFee3Nfbn0oMS1cdGhldGEpXntuLXNfbn0sCiQkCndoZXJlICRzX24gPSBcc3VtX3tpPTF9Xm4geV9pJCBpcyB0aGUgbnVtYmVyIG9mIHN1Y2Vzc2VzIG91dCBvZiAkbiQgKEJlcm5vdWxsaSkgdHJpYWxzLiAgV2UgY29tcHV0ZSB0aGUgTUxFIG9mICRcdGhldGEkIGJhc2VkIG9uICRuPTEwJCBvYnNlcnZhdGlvbnMgYW5kICR5X3sxOjEwfT1cezAsMCwwLDEsMCwxLDAsMSwwLDFcfSQsIHNvICRzX3sxMH09NCBhbmQgJHtcd2lkZWhhdCBcdGhldGF9X3ttbGV9PTQvMTA9MC40JC4KCmBgYHtyfQpuID0gMTAKeSA9IGMoMCwwLDAsMSwwLDEsMCwxLDAsMSkKcyA9IHN1bSh5PT0xKQoKbWxlID0gcy9uCmMobixzLG1sZSkKYGBgCgojIyBQcmlvciwgbGlrZWxpaG9vZCBhbmQgcG9zdGVyaW9yIGZvciAkXHRoZXRhJAoKV2UgaGF2ZSBlbGljaXRlZCBhIHByaW9yIGZvciAkXHRoZXRhJCBpbiBjbGFzcyAod2l0aCB0aGUgaGVscCBvZiBWaXTDs3JpYSkgYW5kIGFycml2ZWQgYXQgdGhlIGZvbGxvd2luZyAKQmV0YSBkaXN0cmlidXRpb246ICAkXHRoZXRhIFxzaW0gQmV0YShhLGIpJCB3aGVyZSAkYT0yJCBhbmQgJGI9NiQsIHN1Y2ggdGhhdApcYmVnaW57ZXFuYXJyYXkqfQpFKFx0aGV0YSkgICAgICAmPSYgXGZyYWN7YX17YStifVxcCk1vZGUoXHRoZXRhKSAgICY9JiBcZnJhY3thLTF9e2ErYi0yfSwgXHF1YWQgXHFxdWFkICBhLGI+MVxcCk1lZGlhbihcdGhldGEpICY9JiBcZnJhY3thLTEvM317YStiLTIvM30sIFxxcXVhZCBhLGI+MSBcIFwgXG1ib3h7KGFwcHJveGltYXRpb24pfQpcZW5ke2VxbmFycmF5Kn0KCmBgYHtyIGZpZy53aWR0aD02LCBmaWcuaGVpZ2h0PTEwLCBmaWcuYWxpZ249J2NlbnRlcid9CmEgPSAyCmIgPSA1CkUgPSBhLyhhK2IpCk1vID0gKGEtMSkvKGErYi0yKQpNZSA9IChhLTEvMykvKGErYi0yLzMpCmMoRSxNbyxNZSkKYGBgCgpUaGUgQmVybm91bGxpIGxpa2VsaWhvb2QgYW5kIHRoZSBCZXRhIHByaW9yIGNvbmp1Z2F0ZSwgd2hpY2ggbWVhbnMgdGhhdCB0aGUgcG9zdGVyaW9yIGZvciAkXHRoZXRhJCBhbHNvIGZvbGxvdyBhIEJldGEgZGlzdHJpYnV0aW9uLiAgVGhlIGNvbmp1Z2FjeSBwcm9wZXJ0eSBtYWtlcyB0aGUgQmF5ZXNpYW4gdXBkYXRpbmcgc3RyYWlnaHRmb3J3YXJkOgpcYmVnaW57ZXFuYXJyYXkqfQpwKFx0aGV0YXx5X3sxOm59LGEsYikgJlxlcXVpdiYgcChcdGhldGF8bixzX24sYSxiKSA9IApcZnJhY3tcbGVmdFx7XGZyYWN7XEdhbW1hKGErYil9e1xHYW1tYShhKVxHYW1tYShiKX1cdGhldGFee2EtMX0oMS1cdGhldGEpXntiLTF9XHJpZ2h0XH0KXHRoZXRhXntzX259KDEtXHRoZXRhKV57bi1zX259fXtwKHlfezE6bn18YSxiKX1cXAomXHByb3B0byYgXHRoZXRhXnthK3Nfbi0xfSgxLVx0aGV0YSlee2Irbi1zX24tMX0gXGVxdWl2IFx0aGV0YV57YV9uLTF9KDEtXHRoZXRhKV57Yl9uLTF9LApcZW5ke2VxbmFycmF5Kn0Kd2hlcmUgCiQkCnAoeV97MTpufXxuLGEsYik9XGludF8wXjEgXGZyYWN7XEdhbW1hKGErYil9e1xHYW1tYShhKVxHYW1tYShiKX0KXHRoZXRhXnthLTF9KDEtXHRoZXRhKV57Yi0xfSBcdGhldGFee3Nfbn0oMS1cdGhldGEpXntuLXNfbn1kXHRoZXRhID0gClxmcmFje1xHYW1tYShhK2IpfXtcR2FtbWEoYSlcR2FtbWEoYil9ClxmcmFje1xHYW1tYShhK3NfbilcR2FtbWEoYituLXNfbil9e1xHYW1tYShhK2Irbil9LAokJAppcyB0aGUgbm9ybWFsaXppbmcgY29uc3RhbnQsIGFsc28ga25vd24gYXMgbWFyZ2luYWwgbGlrZWxpaG9vZCBvciBwcmlvciBwcmVkaWN0aXZlLCBvciBldmVuIHNpbXBseSBwcmVkaWN0aXZlLiAgCgpJdCBpcyBlYXN5IHRvIHNlZSB0aGF0IHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIG9mICRcdGhldGEkIGlzIEJldGEgd2l0aCBoeXBlcGFyYW1ldGVycwokJAphX24gPSBhICsgc19uIFwgXCBcIFxtYm94e2FuZH0gXCBcIFwgYl9uID0gYiArIG4gLSBzX24uCiQkClRoZXJlZm9yZSwgClxiZWdpbntlcW5hcnJheSp9CkUoXHRoZXRhfHlfezE6bn0sYSxiKSAgICAgICY9JiBcZnJhY3thK3Nfbn17YStiK259LFxcCk1vZGUoXHRoZXRhfHlfezE6bn0sYSxiKSAgICY9JiBcZnJhY3thK3Nfbi0xfXthK2Irbi0xfSxcXApNZWRpYW4oXHRoZXRhfHlfezE6bn0sYSxiKSAmPSYgXGZyYWN7YStzX24tMS8zfXthK2Irbi0yLzN9LgpcZW5ke2VxbmFycmF5Kn0KCmBgYHtyfQphMSA9IGErcwpiMSA9IGIrbi1zCkUxID0gYTEvKGExK2IxKQpNbzEgPSAoYTEtMSkvKGExK2IxLTIpCk1lMSA9IChhMS0xLzMpLyhhMStiMS0yLzMpCnRhYiA9IHJiaW5kKGMoRSxNbyxNZSksYyhFMSxNbzEsTWUxKSkKY29sbmFtZXModGFiKSA9IGMoIk1lYW4iLCJNb2RlIiwiTWVkaWFuIikKcm93bmFtZXModGFiKSA9IGMoIlByaW9yIiwiUG9zdGVyaW9yIikKcm91bmQodGFiLDMpCgpwcmVkaWN0aXZlMSA9IChnYW1tYShhK2IpLyhnYW1tYShhKSpnYW1tYShiKSkpKmdhbW1hKGExKSpnYW1tYShiMSkvZ2FtbWEoYTErYjEpCnByZWRpY3RpdmUxCmBgYAoKIyMgT3V0cHV0OiBQcmlvciBhbmQgcG9zdGVyaW9yIGRlbnNpdGllcwpgYGB7ciBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD02LCBmaWcuYWxpZ249J2NlbnRlcid9CnRoZXRhID0gc2VxKDAsMSxsZW5ndGg9MTAwMCkKcGFyKG1mcm93PWMoMSwxKSkKcGxvdCh0aGV0YSxkYmV0YSh0aGV0YSxhLGIpLHR5cGU9ImwiLGx3ZD0yLHlsaW09YygwLDQpLHhsYWI9ZXhwcmVzc2lvbih0aGV0YSkseWxhYj0iRGVuc2l0eSIpCmxpbmVzKHRoZXRhLGRiZXRhKHRoZXRhLGExLGIxKSxjb2w9Mixsd2Q9MikKYWJsaW5lKHY9RSkKYWJsaW5lKHY9TW8sbHR5PTIpCmFibGluZSh2PU1lLGx0eT0zKQphYmxpbmUodj1FMSxjb2w9MikKYWJsaW5lKHY9TW8xLGx0eT0yLGNvbD0yKQphYmxpbmUodj1NZTEsbHR5PTMsY29sPTIpCmFibGluZSh2PW1sZSxjb2w9Myxsd2Q9MikKbGVnZW5kKCJ0b3ByaWdodCIsbGVnZW5kPWMoIlByaW9yIGRlbnNpdHkiLCJQb3N0ZXJpb3IgZGVuc2l0eSIpLGNvbD0xOjIsbHR5PTEsYnR5PSJuIixsd2Q9MikKbGVnZW5kKCJyaWdodCIsbGVnZW5kPWMoIk1lYW4iLCJNb2RlIiwiTWVkaWFuIiwiTUxFIiksbHR5PWMoMTozLDEpLGNvbD1jKDEsMSwxLDMpLGJ0eT0ibiIsbHdkPTIpCmBgYAoKIyBMb2dpdCBCZXJub3VsbGkgbW9kZWwKV2Ugbm93IGJyaW5nIHRvIG91ciBtb2RlbGluZyBleGVyY2lzZSB0aGUgY292YXJpYXRlICR4X2kkIHdpdGggaXMgYWxzbyBiaW5hcnkgd2l0aCAkeF9pPTAkIGlmIHRoZSBhZ2Ugb2YgdGhlIHJlc3BvbmRlbnQgJGkkIGlzIGxlc3MgdGhhbiAzMCwgd2hpbGUgJHhfaT0xJCBpZiB0aGUgYWdlIGlzIGdyZWF0ZXIgdGhhbiBlcXVhbCB0byAzMC4gIEluIHRoaXMgd2F5LCB0aGlzIG1vcmUgY29tcGxleCBtb2RlbCBpcyBnaXZlbiBieQokJAp5X2l8eF9pLFx0aGV0YSBcc2ltIEJlcm5vdWxsaShcdGhldGFfaSksCiQkCndoZXJlIAokJApcbG9nXGxlZnQoXGZyYWN7XHRoZXRhX2l9ezEtXHRoZXRhX2l9XHJpZ2h0KSA9IFxhbHBoYSArIFxiZXRhIHhfaSwKJCQKc3VjaCB0aGF0IApcYmVnaW57ZXFuYXJyYXkqfQpcdGhldGFfaSAmPSYgXGZyYWN7MX17MStcZXhwXHstXGFscGhhXH19ID0gXHBpXzAsIFxxcXVhZCBcbWJveHt3aGVufSBcIFwgeF9pPTBcXApcdGhldGFfaSAmPSYgXGZyYWN7MX17MStcZXhwXHstKFxhbHBoYStcYmV0YSlcfX0gPSBccGlfMSwgXHFxdWFkIFxtYm94e3doZW59IFwgXCB4X2k9MS4KXGVuZHtlcW5hcnJheSp9CgpJbiB3b3JkcywgJFx0aGV0YV9pJCBjYW4gdGFrZSBvbmx5IHR3byBwb3NzaWJsZSB2YWx1ZXMsIHRoZSBwcm9iYWJpbGl0aWVzICRccGlfMCQgYW5kICRccGlfMSQsIHdoaWNoIGFyZSBlcXVpdmFsZW50IHRvIHRoZSBwcm9iYWJpbGl0eSAkXHRoZXRhJCBmcm9tIHRoZSBpaWQgQmVybm91bGxpIG1vZGVsLgoKYGBge3J9Cm4gID0gMTAKeSAgPSBjKDAsMCwwLDEsMCwxLDAsMSwwLDEpCnggID0gYygxLDAsMCwxLDAsMCwwLDEsMCwxKQpuMCA9IHN1bSh4PT0wKQpuMSA9IHN1bSh4PT0xKQpzMCA9IHN1bSh5W3g9PTBdKQpzMSA9IHN1bSh5W3g9PTFdKQpjKG4wLG4xLHMwLHMxKQpgYGAKCiMjIFBvc3RlcmlvciBpbmZlcmVuY2UKUG9zdGVyaW9yIGluZmVyZW5jZSBmb3IgJFxwaV8wJCBhbmQgJFxwaV8xJCAob3IgJFxhbHBoYSxcYmV0YSQpIGlzIHVuYXZhaWxhYmxlIGluIGNsb3NlZCBmb3JtLiAgV2Ugd2lsbCB1cyBNb250ZSBDYXJsbyBtZXRob2QgKGhlcmUgd2UgdXNlIHNhbXBsaW5nIGltcG9ydGFuY2UgcmVzYW1wbGluZywgU0lSKSB0byBiZSBhYmxlIHRvIGFwcHJveGltYXRlIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIGFuZCBjb21wdXRlIHBvc3RlcmlvciBtZWFucywgbW9kZXMsIG1lZGlhbnMgYW5kIG90aGVyIHBvc3RlcmlvciBzdW1tYXJpZXMgYXMgbmVlZGVkLgoKIyMgUHJpb3Igb24gJChcYWxwaGEsXGJldGEpJAoKV2Ugd2lsbCBhc3N1bWUgJFxhbHBoYSQgYW5kICRcYmV0YSQgYXJlLCAqYSBwcmlvcmkqLCBpbmRlcGVuZGVudCBHYXVzc2lhbnM6IAokJApwKFxhbHBoYSxcYmV0YSk9cChcYWxwaGF8XG11X1xhbHBoYSxcc2lnbWFfXGFscGhhXjIpcChcYmV0YXxcbXVfXGJldGEsXHNpZ21hX1xiZXRhXjIpLAokJAp3aXRoIGh5cGVycGFyYW1ldGVycyAkXG11X1xhbHBoYT0tMC43JCwgJFxtdV9cYmV0YT0xLjQkIGFuZCAkXHNpZ21hX1xtdT1cc2lnbWFfXGJldGE9MSQuICBUaGUgaW50dWl0aW9uIGlzIHRoYXQgdGhlc2UgbWFyZ2luYWwgcHJpb3JzIGluZHVjZSBwcmlvciBtZWFucyBmb3IgJFxwaV8wJCBhbmQgJFxwaV8xJCBhcm91bmQgdGhlIGZvbGxvd2luZyB2YWx1ZXM6CiQkClxmcmFjezF9ezErXGV4cFx7MC43XH19IFxhcHByb3ggMS8zIFxxcXVhZCBcbWJveHthbmR9IFxxcXVhZApcZnJhY3sxfXsxK1xleHBcezAuNy0xLjRcfX0gXGFwcHJveCAyLzMuCiQkCkJlbG93IHdlIHNob3cgZHJhd3MgZnJvbSB0aGUgaW5kdWNlZCBwcmlvciBvbiAkKFxwaV8wLFxwaV8xKSQuCmBgYHtyIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTgsIGZpZy5hbGlnbj0nY2VudGVyJ30KTSAgICAgPSAxMDAwMAphbHBoYSA9IHJub3JtKE0sLTAuNywxKQpiZXRhICA9IHJub3JtKE0sMS40LDEpCgojIEluZHVjZWQgcHJpb3Igb24gKHBpMCxwaTEpCnBpMCA9IDEvKDErZXhwKC1hbHBoYSkpCnBpMSA9IDEvKDErZXhwKC1hbHBoYS1iZXRhKSkKCnBhcihtZnJvdz1jKDIsMikpCnBsb3QoYWxwaGEsYmV0YSx4bGFiPWV4cHJlc3Npb24oYWxwaGEpLHlsYWI9ZXhwcmVzc2lvbihiZXRhKSkKYm94cGxvdChhbHBoYSxhbHBoYStiZXRhLG91dGxpbmU9RkFMU0UsbmFtZXM9YyhleHByZXNzaW9uKGFscGhhKSxleHByZXNzaW9uKGFscGhhK2JldGEpKSkKcGxvdChwaTAscGkxLHhsaW09YygwLDEpLHlsaW09YygwLDEpLHhsYWI9ZXhwcmVzc2lvbihwaVswXSkseWxhYj1leHByZXNzaW9uKHBpWzFdKSkKYWJsaW5lKDAsMSxjb2w9Mixsd2Q9MikKYm94cGxvdCgxLygxK2V4cCgtYWxwaGEpKSwxLygxK2V4cCgtYWxwaGEtYmV0YSkpLG5hbWVzPWMoIkFnZTwzMCAoaT0wKSIsIkFnZT49MzAgKGk9MSkiKSx5bGFiPWV4cHJlc3Npb24ocGlbaV0pKQpgYGAKCiMjIE1vbnRlIENhcmxvLWJhc2VkIHBvc3RlcmlvciBpbmZlcmVuY2UKT2J2aW91c2x5LCB0aGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBvZiAkKFxhbHBoYSxcYmV0YSkkIGlzIG9mIG5vIGtub3duIGZvcm0gYW5kIGFuYWx5dGljYWxseSBpbnRyYWN0YWJsZToKJCQKcChcYWxwaGEsXGJldGF8eV97MTpufSxuLFxtdV9cYWxwaGEsXHNpZ21hX1xhbHBoYSxcbXVfXGJldGEsXHNpZ21hX1xiZXRhKSBccHJvcHRvIHAoXGFscGhhLFxiZXRhfFxtdV9cYWxwaGEsXHNpZ21hX1xhbHBoYSxcbXVfXGJldGEsXHNpZ21hX1xiZXRhKVxwcm9kX3tpPTF9Xm4gXHRoZXRhX2lee3lfaX0oMS1cdGhldGFfaSleezEteV9pfS4KJCQKUmVjYWxsIHRoYXQgJFx0aGV0YV9pID0gMS8oMStcZXhwXHstKFxhbHBoYStcYmV0YSB4X2kpXH0pJCwgZm9yICRpPTEsXGxkb3RzLG4kLCBzbyB0aGUgbGlrZWxpaG9vZCBpcyBhIGZ1bmN0aW9uIG9mICQoXGFscGhhLFxiZXRhKSQuCgpBcyB3ZSB3aWxsIHNlZSB0aHJvdWdob3V0IHRoaXMgY291cnNlLCBNb250ZSBDYXJsby1iYXNlZCBwb3N0ZXJpb3IgaW5mZXJlbmNlIGhhcyBiZWNvbWUgdGhlIG1vc3QgY29tbW9uIHNjaGVtZSB0byBiZSBhYmxlIHRvIGFjY3VyYXRlbHkgYXBwcm94aW1hdGUgaGlnaGx5IGNvbXBsZXggcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbnMuICBUaGUgdGhlIGRpbWVuc2lvbiBvZiB0aGUgcGFyYW1ldGVyIGlzIHJlbGF0aXZlbHkgbG93IChoZXJlIHdlIGhhdmUgJFxhbHBoYSQgYW5kICRcYmV0YSQsIHNvIDItZGltZW5zaW9uYWwpIGEgc2ltcGxlIHN0cmF0ZWd5IGlzIHRvIHNhbXBsZSBkcmF3cyBmcm9tIHRoZSBwcmlvciBhbmQgcmVzYW1wbGUgdGhvc2UgZHJhd3Mgd2l0aCB3ZWlnaHRzIHByb3BvcnRpb25hbCB0byB0aGUgbGlrZWxpaG9vZCwgd2hpY2ggdHJhbnNsYXRlcyBpbnRvIHRoZSB3ZWxsLWtub3duICpzYW1wbGluZyBpbXBvcnRhbmNlIHJlc2FtcGxpbmcgKFNJUikqIHNjaGVtZS4gIFRoZSBjb3Vyc2Ugbm90ZXMgaXMgZnVsbCBvZiBleGFtcGxlcyBpbGx1c3RyYXRpbmcgdGhlIGltcGxlbWVudGF0aW9uLCBhbmQgZHJhd2JhY2tzLCBvZiBTSVItYmFzZWQgcG9zdGVyaW9yIGluZmVyZW5jZS4gIEZvciBub3csIGxldCB1cyBqdXN0IGFzc3VtZSB0aGUgZm9sbG93aW5nIHBpZWNlIG9mIGNvZGUgZG9lcyB0aGUgbWFnaWM6CgpgYGB7cn0KbGlrZSA9IHJlcCgwLE0pCmZvciAoaSBpbiAxOk0pCiAgbGlrZVtpXSA9IHBpMFtpXV5zMCooMS1waTBbaV0pXihuMC1zMCkqcGkxW2ldXnMxKigxLXBpMVtpXSleKG4xLXMxKQpwcmVkaWN0aXZlMiA9IG1lYW4obGlrZSkKaW5kID0gc2FtcGxlKDE6TSxzaXplPU0scmVwbGFjZT1UUlVFLHByb2I9bGlrZSkKcGkwLnBvc3QgPSBwaTBbaW5kXQpwaTEucG9zdCA9IHBpMVtpbmRdCmFscGhhLnBvc3QgPSBhbHBoYVtpbmRdCmJldGEucG9zdCA9IGJldGFbaW5kXQpwcmVkaWN0aXZlMgpgYGAKClRoZSB2YXJpYWJsZXMgcGkwLnBvc3QgYW5kIHBpMS5wb3N0IGFyZSBzYW1wbGVzIChkcmF3cykgZnJvbSB0aGUgam9pbnQgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiAkcChcYWxwaGEsXGJldGF8eV97MTpufSxuLFxtdV9cYWxwaGEsXHNpZ21hX1xhbHBoYSxcbXVfXGJldGEsXHNpZ21hX1xiZXRhKSQuICBTaW1pbGFybHkgZm9yIGFscGhhLnBvc3QgYW5kIGJldGEucG9zdC4KCiMjIEdyYXBoaWNhbCBvdXRwdXQKYGBge3IgZmlnLndpZHRoPTgsIGZpZy5oZWlnaHQ9NywgZmlnLmFsaWduPSdjZW50ZXInfQpwYXIobWZyb3c9YygyLDIpKQpwbG90KHBpMCxwaTEseGxpbT1jKDAsMSkseWxpbT1jKDAsMSkseGxhYj1leHByZXNzaW9uKHBpWzBdKSx5bGFiPWV4cHJlc3Npb24ocGlbMV0pKQpwb2ludHMocGkwLnBvc3QscGkxLnBvc3QsY29sPTIpCmxlZ2VuZCgiYm90dG9tcmlnaHQiLGxlZ2VuZD1jKCJQcmlvciBkcmF3cyIsIlBvc3RlcmlvciBkcmF3cyIpLGNvbD0xOjIscGNoPTE2LGJ0eT0ibiIpCgpwbG90KGFscGhhLGJldGEseGxhYj1leHByZXNzaW9uKGFscGhhKSx5bGFiPWV4cHJlc3Npb24oYmV0YSkpCnBvaW50cyhhbHBoYS5wb3N0LGJldGEucG9zdCxjb2w9MikKdGl0bGUocGFzdGUoIkNvcnJlbGF0aW9uPSIscm91bmQoY29yKGFscGhhLnBvc3QsYmV0YS5wb3N0KSwyKSxzZXA9IiIpKQoKcGxvdChkZW5zaXR5KHBpMCkseWxpbT1jKDAsNCkseGxpbT1jKDAsMSksbWFpbj0iIix4bGFiPWV4cHJlc3Npb24ocGlbMF0pKQpsaW5lcyhkZW5zaXR5KHBpMC5wb3N0KSxjb2w9MikKbGVnZW5kKCJ0b3ByaWdodCIsbGVnZW5kPWMoZXhwcmVzc2lvbih4W2ldPT0wKSkpCgpwbG90KGRlbnNpdHkocGkxKSx5bGltPWMoMCwzKSx4bGFiPWV4cHJlc3Npb24ocGlbMV0pLHhsaW09YygwLDEpLG1haW49IiIpCmxpbmVzKGRlbnNpdHkocGkxLnBvc3QpLGNvbD0yKQpsZWdlbmQoInRvcHJpZ2h0IixsZWdlbmQ9YyhleHByZXNzaW9uKHhbaV09PTEpKSkKYGBgCgoKIyBDb21wYXJpbmcgdGhlIHR3byBCZXJub3VsbGkgbW9kZWxzCgpgYGB7ciBmaWcud2lkdGg9NSwgZmlnLmhlaWdodD01LCBmaWcuYWxpZ249J2NlbnRlcid9CnBhcihtZnJvdz1jKDEsMSkpCnBsb3QodGhldGEsZGJldGEodGhldGEsYTEsYjEpLHR5cGU9ImwiLGx3ZD0yLHlsaW09YygwLDQpLAogICAgIHhsYWI9IlByb2JhYmlsaXR5IG9mIHN1Y2VzcyIseWxhYj0iUG9zdGVyaW9yIGRlbnNpdHkiKQpsaW5lcyhkZW5zaXR5KHBpMFtpbmRdKSxjb2w9Mixsd2Q9MikKbGluZXMoZGVuc2l0eShwaTFbaW5kXSksY29sPTMsbHdkPTIpCmxlZ2VuZCgidG9wcmlnaHQiLGxlZ2VuZD1jKGV4cHJlc3Npb24odGhldGEpLGV4cHJlc3Npb24ocGlbMF0pLGV4cHJlc3Npb24ocGlbMV0pKSxsdHk9MSxsd2Q9Mixjb2w9MTozLGJ0eT0ibiIpCmBgYCAgICAgICAKCkEgZmV3IGNvbW1vbmx5IHVzZWQgcG9zdGVyaW9yIHN1bW1hcmllcyBhcmUgYXMgZm9sbG93czoKYGBge3J9CnRhYiA9IHJiaW5kKApxYmV0YShjKDAuMDUsMC41LDAuOTUpLGExLGIxKSwKcXVhbnRpbGUocGkwW2luZF0sYygwLjA1LDAuNSwwLjk1KSksCnF1YW50aWxlKHBpMVtpbmRdLGMoMC4wNSwwLjUsMC45NSkpKQpyb3duYW1lcyh0YWIpID0gYygidGhldGEiLCJwaTAiLCJwaTEiKQpyb3VuZCh0YWIsMikKYGBgCgojIyBCYXllcyBmYWN0b3IKTGV0IGNhbGwgdGhlIGlpZCBCZXJub3VsbGkgbW9kZWwgJE1fMSQsIHdoaWxlIHRoZSBsb2dpdCBCZXJub3VsbGkgbW9kZWwgJE1fMiQuICBUaGVuLCB0aGUgQmF5ZXMgZmFjdG9yIGlzIGRlZmluZWQgYXMKJCQKQkZfezEyfSA9IFxmcmFje3AoeV97MTpufXxhLGIpfXtwKHlfezE6bn18eF97MTpufSxcbXVfXGFscGhhLFxzaWdtYV9cYWxwaGEsXG11X1xiZXRhLFxzaWdtYV9cYmV0YSl9IFxhcHByb3gKXGZyYWN7cCh5X3sxOm59fGEsYil9e3Bfe1NJUn0oeV97MTpufXx4X3sxOm59LFxtdV9cYWxwaGEsXHNpZ21hX1xhbHBoYSxcbXVfXGJldGEsXHNpZ21hX1xiZXRhKX0sCiQkCndoZXJlICRwX3tTSVJ9KHlfezE6bn18eF97MTpufSxcbXVfXGFscGhhLFxzaWdtYV9cYWxwaGEsXG11X1xiZXRhLFxzaWdtYV9cYmV0YSkkIGlzIHRoZSBTSVItYmFzZWQgYXBwcm94aW1hdGluIHRvIHRoZSBwcmlvciBwcmVkaWN0aXZlIHVuZGVyIHRoZSBsb2dpdCBCZXJub3VsbGkgbW9kZWwuICBXZSB3aWxsIGV4cGxhaW4gd2h5IHRoYXQgaXMgY29ycmVjdCBsYXRlciEKCmBgYHtyfQpjKHByZWRpY3RpdmUxLHByZWRpY3RpdmUyKQpCRjEyID0gcHJlZGljdGl2ZTEvcHJlZGljdGl2ZTIKQkYyMSA9IDEvQkYxMgpCRjIxCmBgYAoKSW4gYSByZXZpZXcgcGFwZXIgZW50aXRsZWQgKkJheWVzIEZhY3RvcnMqLCB0aGF0IGFwcGVhcmVkIGluIEpBU0EgaW4gMTk5NSAoVm9sdW1lIDkwLCBJc3N1ZSA0MzApLCBSb2JlcnQgRS4gS2FzcyBhbmQgQWRyaWFuIEUuIFJhZnRlcnkgc3VnZ2VzdGVkIHRoZSBmb2xsb3dpbmcgcnVsZSBvZiB0aHVtYiBpbiBvcmRlciB0byBxdWFudGl0eSBldmlkZW5jZSBhZ2FpbnN0ICRNXzEkOgoKKiAkQl97MjF9IFxpbiAoMSwzKSQ6IE5vdCB3b3J0aCBtb3JlIHRoYW4gYSBiYXJlIG1lbnRpb24gCiogJEJfezIxfSBcaW4gKDMsMjApJDogUG9zaXRpdmUgCiogJEJfezIxfSBcaW4gKDIwLDE1MCkkOiBTdHJvbmcKKiAkQl97MjF9IFxpbiAoMTUwLFxpbmZ0eSkkOiBWZXJ5IHN0cm9uZy4KClRoZXJlZm9yZSwgaW4gb3VyIGNhc2UsIHRoZSBkYXRhIHByb3ZpZGVzIHBvc2l0aXZlIGV2aWRlbmNlIGFnYWluc3QgJE1fMSQuCg==