-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathintroduction.html
219 lines (201 loc) · 12.5 KB
/
introduction.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
<!DOCTYPE html>
<html class="writer-html5" lang="en" >
<head>
<meta charset="utf-8" /><meta name="generator" content="Docutils 0.18.1: http://docutils.sourceforge.net/" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>1. Overview — pypmc 1.2.2 documentation</title>
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
<link rel="stylesheet" href="_static/plot_directive.css" type="text/css" />
<!--[if lt IE 9]>
<script src="_static/js/html5shiv.min.js"></script>
<![endif]-->
<script src="_static/jquery.js"></script>
<script src="_static/_sphinx_javascript_frameworks_compat.js"></script>
<script data-url_root="./" id="documentation_options" src="_static/documentation_options.js"></script>
<script src="_static/doctools.js"></script>
<script src="_static/sphinx_highlight.js"></script>
<script type="text/x-mathjax-config">MathJax.Hub.Config({"extensions": ["tex2jax.js"], "jax": ["input/TeX", "output/HTML-CSS"], "TeX": {"Macros": {"vecgamma": "{\\vec \\gamma}", "vecth": "{\\vec \\theta}"}}})</script>
<script async="async" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<script src="_static/js/theme.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="2. Installation" href="installation.html" />
<link rel="prev" title="pypmc" href="index.html" />
</head>
<body class="wy-body-for-nav">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search" >
<a href="index.html" class="icon icon-home">
pypmc
</a>
<div class="version">
1.2.2
</div>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="search.html" method="get">
<input type="text" name="q" placeholder="Search docs" aria-label="Search docs" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div><div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
<ul class="current">
<li class="toctree-l1 current"><a class="current reference internal" href="#">1. Overview</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#initial-proposal-density">1.1. Initial proposal density</a></li>
<li class="toctree-l2"><a class="reference internal" href="#proposal-updates">1.2. Proposal updates</a></li>
<li class="toctree-l2"><a class="reference internal" href="#pmc">1.3. PMC</a></li>
<li class="toctree-l2"><a class="reference internal" href="#variational-bayes">1.4. Variational Bayes</a></li>
<li class="toctree-l2"><a class="reference internal" href="#performance">1.5. Performance</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="installation.html">2. Installation</a></li>
<li class="toctree-l1"><a class="reference internal" href="user_guide.html">3. User guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="examples.html">4. Examples</a></li>
<li class="toctree-l1"><a class="reference internal" href="references.html">5. References</a></li>
<li class="toctree-l1"><a class="reference internal" href="api.html">6. Reference Guide</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap"><nav class="wy-nav-top" aria-label="Mobile navigation menu" >
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="index.html">pypmc</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="Page navigation">
<ul class="wy-breadcrumbs">
<li><a href="index.html" class="icon icon-home" aria-label="Home"></a></li>
<li class="breadcrumb-item active"><span class="section-number">1. </span>Overview</li>
<li class="wy-breadcrumbs-aside">
<a href="_sources/introduction.rst.txt" rel="nofollow"> View page source</a>
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<section id="overview">
<h1><span class="section-number">1. </span>Overview<a class="headerlink" href="#overview" title="Permalink to this heading"></a></h1>
<p>Let <span class="math notranslate nohighlight">\(P\)</span> denote the target density, and let <span class="math notranslate nohighlight">\(q\)</span>
equal the proposal density. Then the basic idea of importance sampling
is to approximate the integral of <span class="math notranslate nohighlight">\(P\)</span> as</p>
<div class="math notranslate nohighlight">
\[\int \mbox{d} x \, P(x) = \int \mbox{d} x \, q(x) \frac{P(x)}{q(x)}
\approx \frac{1}{N} \sum_{i=1}^{N} \frac{P(x_i)}{q(x_i)}\]</div>
<p>where each <span class="math notranslate nohighlight">\(x\)</span> is a <span class="math notranslate nohighlight">\(D\)</span>-dimensional vector drawn
independently from <span class="math notranslate nohighlight">\(q\)</span>. The <span class="math notranslate nohighlight">\(i\)</span>-th importance weight is
defined as</p>
<div class="math notranslate nohighlight">
\[w_i \equiv \frac{P(x_i)}{q(x_i)}\]</div>
<p>The most accurate estimate is obtained for <span class="math notranslate nohighlight">\(q=P\)</span>, so the goal is
make <span class="math notranslate nohighlight">\(q\)</span> as close as possible to <span class="math notranslate nohighlight">\(P\)</span>.</p>
<p>In pypmc, we choose <span class="math notranslate nohighlight">\(q\)</span> to be a mixture density composed of
either Gaussian or Student’s t components <span class="math notranslate nohighlight">\(q_j\)</span></p>
<div class="math notranslate nohighlight">
\[q(x) = \sum_j \alpha_j q_j(x), \: \sum_j \alpha_j = 1 \,.\]</div>
<section id="initial-proposal-density">
<h2><span class="section-number">1.1. </span>Initial proposal density<a class="headerlink" href="#initial-proposal-density" title="Permalink to this heading"></a></h2>
<p>The key ingredient to make adaptive importance sampling work is a good
initial proposal density that closely resembles the target density. A
general method to automatically determine the bulk of the target is to
run multiple Markov chains, and to use clustering to extract a mixture
density from the samples <a class="reference internal" href="references.html#bc13" id="id1"><span>[BC13]</span></a>. We provide a generic implementation
of adaptive local-random-walk MCMC <a class="reference internal" href="references.html#hst01" id="id2"><span>[HST01]</span></a> featuring Gauss and
Student’s t local proposals. MCMC can be used standalone and is
usually all one needs for a unimodal distribution if the evidence is
not of interest. For the clustering, we offer several options. At the
level of individual samples, we have</p>
<ul class="simple">
<li><p>population Monte Carlo <a class="reference internal" href="references.html#cap-08" id="id3"><span>[Cap+08]</span></a></p></li>
<li><p>variational Bayes for Gaussian mixtures <a class="reference internal" href="references.html#bis06" id="id4"><span>[Bis06]</span></a></p></li>
</ul>
<p>and at the level of Gaussian mixtures, there is</p>
<ul class="simple">
<li><p>hierarchical clustering <a class="reference internal" href="references.html#gr04" id="id5"><span>[GR04]</span></a> as suggested by Beaujean & Caldwell
<a class="reference internal" href="references.html#bc13" id="id6"><span>[BC13]</span></a></p></li>
<li><p>variational Bayes (VBmix) <a class="reference internal" href="references.html#bgp10" id="id7"><span>[BGP10]</span></a></p></li>
</ul>
</section>
<section id="proposal-updates">
<h2><span class="section-number">1.2. </span>Proposal updates<a class="headerlink" href="#proposal-updates" title="Permalink to this heading"></a></h2>
<p>Starting with an initial proposal, samples are drawn from the proposal
<span class="math notranslate nohighlight">\(q\)</span>, the importance weights are computed, and the proposal is
updated using the samples and weights to more closely approximate the
target density. The two main update algorithms included are:</p>
<ul class="simple">
<li><p>Population Monte Carlo (PMC)</p></li>
<li><p>Variational Bayes (VB)</p></li>
</ul>
</section>
<section id="pmc">
<h2><span class="section-number">1.3. </span>PMC<a class="headerlink" href="#pmc" title="Permalink to this heading"></a></h2>
<p>Based on the original proposal by Cappé et al. <a class="reference internal" href="references.html#cap-08" id="id8"><span>[Cap+08]</span></a>, we offer
updates for a mixture of Gaussian or Student’s t components. Important
improvements are:</p>
<ul class="simple">
<li><p>The option to adapt the Student’s t degree of freedom - individually
for each component - as in <a class="reference internal" href="references.html#hod12" id="id9"><span>[HOD12]</span></a>. That’s one less parameter that
the user has to guess.</p></li>
<li><p>The power to combine the proposals of subsequent steps
<a class="reference internal" href="references.html#cor-12" id="id10"><span>[Cor+12]</span></a>. This increases the effective sample size per wallclock
time and helps in reducing undesired samples with very large weight — <em>outliers</em> —
that adversely affect the variance of the integral estimate.</p></li>
</ul>
</section>
<section id="variational-bayes">
<h2><span class="section-number">1.4. </span>Variational Bayes<a class="headerlink" href="#variational-bayes" title="Permalink to this heading"></a></h2>
<p>A powerful alternative to PMC is to use the variational Bayes
algorithm <a class="reference internal" href="references.html#bis06" id="id11"><span>[Bis06]</span></a> to fit a Gaussian mixture to samples. We include a
variant that also works with importance-weighted samples. Our
implementation allows the user to set all values of the
prior/posterior hyperparameters. Variational Bayes can therefore be
used in a sequential manner to incrementally update the knowledge
about the Gaussian mixture as new (importance) samples arrive.</p>
</section>
<section id="performance">
<h2><span class="section-number">1.5. </span>Performance<a class="headerlink" href="#performance" title="Permalink to this heading"></a></h2>
<p>Importance sampling naturally lends itself to massive parallelization
because once the samples are drawn from the proposal, the computation
of <span class="math notranslate nohighlight">\(N\)</span> importance weights requires <span class="math notranslate nohighlight">\(N\)</span> independent calls to the target
density. Even for moderately complicated problems, these calls are
typically the most expensive part of the calculation. With pypmc, the
importance weights can optionally be computed in multiple processes on
a single machine or a whole cluster with mpi4py. Similarly, multiple
Markov chains are independent and can be run in separate processes.</p>
<p>The second major contribution to overall computing time is the update
algorithm itself. We profiled the program and transferred the relevant
loops from python to compiled C code via cython.</p>
<p>The code is designed such that it does not get into the user’s way;
full control over how individual components interact is a major design
goal.</p>
</section>
</section>
</div>
</div>
<footer><div class="rst-footer-buttons" role="navigation" aria-label="Footer">
<a href="index.html" class="btn btn-neutral float-left" title="pypmc" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left" aria-hidden="true"></span> Previous</a>
<a href="installation.html" class="btn btn-neutral float-right" title="2. Installation" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right" aria-hidden="true"></span></a>
</div>
<hr/>
<div role="contentinfo">
<p>© Copyright 2014-2021, Frederik Beaujean and Stephan Jahn and others.</p>
</div>
Built with <a href="https://www.sphinx-doc.org/">Sphinx</a> using a
<a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a>
provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
</div>
</div>
</section>
</div>
<script>
jQuery(function () {
SphinxRtdTheme.Navigation.enable(true);
});
</script>
</body>
</html>