aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
gibbsOperator_tpl.h
Go to the documentation of this file.
1/****************************************************************************
2 * This file is part of the aGrUM/pyAgrum library. *
3 * *
4 * Copyright (c) 2005-2026 by *
5 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
6 * - Christophe GONZALES(_at_AMU) *
7 * *
8 * The aGrUM/pyAgrum library is free software; you can redistribute it *
9 * and/or modify it under the terms of either : *
10 * *
11 * - the GNU Lesser General Public License as published by *
12 * the Free Software Foundation, either version 3 of the License, *
13 * or (at your option) any later version, *
14 * - the MIT license (MIT), *
15 * - or both in dual license, as here. *
16 * *
17 * (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html) *
18 * *
19 * This aGrUM/pyAgrum library is distributed in the hope that it will be *
20 * useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, *
21 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
22 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
26 * OTHER DEALINGS IN THE SOFTWARE. *
27 * *
28 * See LICENCES for more details. *
29 * *
30 * SPDX-FileCopyrightText: Copyright 2005-2026 *
31 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
32 * - Christophe GONZALES(_at_AMU) *
33 * SPDX-License-Identifier: LGPL-3.0-or-later OR MIT *
34 * *
35 * Contact : info_at_agrum_dot_org *
36 * homepage : http://agrum.gitlab.io *
37 * gitlab : https://gitlab.com/agrumery/agrum *
38 * *
39 ****************************************************************************/
40
41#pragma once
42
43
50
51
52#include <algorithm>
53#include <cstdint>
54
57
59
60namespace gum {
61
62 template < GUM_Numeric GUM_SCALAR >
64 const NodeProperty< Idx >* hardEv,
65 const std::string& section) :
67 BN,
68 hardEv,
69 // number of variables drawn between two samples (percentage of the variables, in [0,100]
70 // according to the domain of the key)
71 1
72 + (BN.size()
73 * static_cast< Size >(
74 Configuration::instance().typed< std::int64_t >(section, "percentDrawnSample"))
75 / 100),
76 Configuration::instance().typed< bool >(section, "drawnAtRandom")) {}
77
78 template < GUM_Numeric GUM_SCALAR >
80 const NodeProperty< Idx >* hardEv,
81 Size nbr,
82 bool atRandom) :
83 counting_(0), samplingBn_(BN), hardEv_(hardEv), nbr_(nbr), atRandom_(atRandom) {
84 GUM_CONSTRUCTOR(GibbsOperator);
85 }
86
87 template < GUM_Numeric GUM_SCALAR >
91
92 template < GUM_Numeric GUM_SCALAR >
94 samplingNodes_.clear();
95 for (const auto node: samplingBn_.nodes())
96 if (hardEv_ == nullptr || !hardEv_->exists(node)) { samplingNodes_.insert(node); }
97 if (samplingNodes_.size() == 0) {
98 GUM_ERROR(InvalidArgument, "No node to sample (too many nodes or too much evidence)!")
99 }
100 if (nbr_ > samplingNodes_.size()) nbr_ = samplingNodes_.size();
101 }
102
103 // returns a first sample with a positive probability (see the documentation in gibbsOperator.h)
104 template < GUM_Numeric GUM_SCALAR >
106 // From a sample with a null probability, every Gibbs move may have a null mass: the chain would
107 // stay there forever. Hence the first sample must have a positive probability.
108
109 // 0. the values that cannot belong to such a sample are pruned
110 if (!_pruneDomains_()) {
112 "The hard evidence has a null probability (incompatible with the model)")
113 }
114
115 // 1. a few forward samples (in the pruned domains)
117 for (Size tries = 0; tries < _nbrRejectionTries_; ++tries) {
118 I = _forwardSample_();
119 if (_isCompatible_(I)) return I;
120 }
121
122 // 2. Gibbs moves in a smoothed model (null probabilities replaced by epsilon): the chain is
123 // attracted by the samples with fewer null probabilities. A small epsilon gives a strong
124 // attraction, a larger one helps to get through samples with more null probabilities: epsilon
125 // grows only when the chain is stuck. The sampled distribution does not matter here: we stop as
126 // soon as the sample is compatible. The chain may still be stuck on a plateau, depending on its
127 // start: hence a few restarts from new forward samples.
128 std::vector< NodeId > sampled;
129 for (const auto node: samplingBn_.nodes())
130 if (hardEv_ == nullptr || !hardEv_->exists(node)) sampled.push_back(node);
131
132 // the smallest positive probability of each CPT (used by the smoothing) is computed once
133 _minNonZero_.clear();
134 for (const auto node: samplingBn_.nodes())
135 _minNonZero_.insert(node, samplingBn_.cpt(node).minNonZero());
136
137 for (Size restart = 0; restart < _nbrSmoothingRestarts_; ++restart) {
138 if (restart > 0) I = _forwardSample_();
139 for (const auto epsilon: _smoothingLevels_) {
140 for (Size sweep = 0; sweep < _nbrSweepsBySmoothingLevel_; ++sweep) {
141 for (const auto node: sampled)
142 _smoothedGibbsSample_(node, &I, GUM_SCALAR(epsilon));
143 if (_isCompatible_(I)) return I;
144 }
145 }
146 }
148 "No sample with a positive probability found: the evidence may be incompatible "
149 "with the model")
150 }
151
152 template < GUM_Numeric GUM_SCALAR >
155
156 for (const auto nod: samplingBn_.topologicalOrder()) {
157 I.add(samplingBn_.variable(nod));
158 if (hardEv_ != nullptr && hardEv_->exists(nod)) {
159 I.chgVal(samplingBn_.variable(nod), (*hardEv_)[nod]);
160 } else {
161 _drawVarMonteCarlo_(nod, &I);
162 }
163 }
164 return I;
165 }
166
167 template < GUM_Numeric GUM_SCALAR >
169 for (const auto node: samplingBn_.nodes())
170 if (samplingBn_.cpt(node).get(I) == GUM_SCALAR(0)) return false;
171 return true;
172 }
173
174 template < GUM_Numeric GUM_SCALAR >
176 Instantiation* I,
177 GUM_SCALAR epsilon) {
178 gum::Instantiation Itop(*I);
179 Itop.erase(samplingBn_.variable(id));
180 // a null probability is replaced by epsilon times the smallest positive probability of its CPT:
181 // a null probability always weighs less than any positive probability of the same CPT
182 auto smoothed = [this, epsilon](NodeId node, Tensor< GUM_SCALAR > t) {
183 const GUM_SCALAR replacement = epsilon * _minNonZero_[node];
184 Instantiation J(t);
185 for (J.setFirst(); !J.end(); J.inc())
186 if (t[J] == GUM_SCALAR(0)) t.set(J, replacement);
187 return t;
188 };
189 gum::Tensor< GUM_SCALAR > p = smoothed(id, samplingBn_.cpt(id).extract(Itop));
190 for (const auto nod: samplingBn_.children(id))
191 p *= smoothed(nod, samplingBn_.cpt(nod).extract(Itop));
192 _mask_(id, p);
193 p.normalize();
194 I->chgVal(samplingBn_.variable(id), p.draw());
195 }
196
197 template < GUM_Numeric GUM_SCALAR >
199 _allowed_.clear();
200 for (const auto node: samplingBn_.nodes()) {
201 const auto domainSize = samplingBn_.variable(node).domainSize();
202 if (hardEv_ != nullptr && hardEv_->exists(node)) {
203 std::vector< bool > allowed(domainSize, false);
204 allowed[(*hardEv_)[node]] = true;
205 _allowed_.insert(node, std::move(allowed));
206 } else {
207 _allowed_.insert(node, std::vector< bool >(domainSize, true));
208 }
209 }
210
211 // only the CPTs with null probabilities may prune values
212 NodeSet withZeros;
213 NodeSet inQueue;
214 std::vector< NodeId > queue;
215 for (const auto node: samplingBn_.nodes())
216 if (samplingBn_.cpt(node).min() == GUM_SCALAR(0)) {
217 withZeros.insert(node);
218 inQueue.insert(node);
219 queue.push_back(node);
220 }
221
222 while (!queue.empty()) {
223 const NodeId f = queue.back();
224 queue.pop_back();
225 inQueue.erase(f);
226
227 // the supported values: those in a positive entry of the CPT whose values are all allowed
228 const auto& cpt = samplingBn_.cpt(f);
229 const auto& vars = cpt.variablesSequence();
230 std::vector< NodeId > ids;
231 std::vector< std::vector< bool > > supported;
232 for (const auto var: vars) {
233 ids.push_back(samplingBn_.nodeId(*var));
234 supported.emplace_back(var->domainSize(), false);
235 }
236 Instantiation I(cpt);
237 for (I.setFirst(); !I.end(); I.inc()) {
238 if (cpt[I] == GUM_SCALAR(0)) continue;
239 bool allowed = true;
240 for (Idx k = 0; k < ids.size() && allowed; ++k)
241 allowed = _allowed_[ids[k]][I.val(k)];
242 if (allowed)
243 for (Idx k = 0; k < ids.size(); ++k)
244 supported[k][I.val(k)] = true;
245 }
246
247 // removing the unsupported values
248 for (Idx k = 0; k < ids.size(); ++k) {
249 auto& allowed = _allowed_[ids[k]];
250 bool changed = false;
251 bool empty = true;
252 for (Idx val = 0; val < allowed.size(); ++val) {
253 if (allowed[val] && !supported[k][val]) {
254 allowed[val] = false;
255 changed = true;
256 }
257 if (allowed[val]) empty = false;
258 }
259 if (empty) return false;
260
261 if (changed) { // the CPTs containing this node have to be revised
262 auto revise = [&](NodeId g) {
263 if (withZeros.contains(g) && !inQueue.contains(g)) {
264 inQueue.insert(g);
265 queue.push_back(g);
266 }
267 };
268 revise(ids[k]);
269 for (const auto child: samplingBn_.children(ids[k]))
270 revise(child);
271 }
272 }
273 }
274 return true;
275 }
276
277 template < GUM_Numeric GUM_SCALAR >
278 void GibbsOperator< GUM_SCALAR >::_mask_(NodeId node, Tensor< GUM_SCALAR >& p) const {
279 const auto allowed = _allowed_.tryGet(node);
280 if (!allowed) return;
281 Instantiation J(p);
282 for (J.setFirst(); !J.end(); J.inc())
283 if (!(*allowed)[J.val(0)]) p.set(J, GUM_SCALAR(0));
284 }
285
286 template < GUM_Numeric GUM_SCALAR >
288 gum::Instantiation Itop(*I);
289 Itop.erase(samplingBn_.variable(nod));
290 auto p = samplingBn_.cpt(nod).extract(Itop);
291 _mask_(nod, p);
292 // if no allowed value is possible, the sample is incompatible anyway
293 if (p.sum() == GUM_SCALAR(0)) p = samplingBn_.cpt(nod).extract(Itop);
294 else p.normalize();
295 I->chgVal(samplingBn_.variable(nod), p.draw());
296 }
297
298 template < GUM_Numeric GUM_SCALAR >
300 for (Idx i = 0; i < nbr_; i++) {
301 auto pos
303 this->_GibbsSample_(samplingNodes_[pos], &prev);
304 counting_++;
305 }
306 return prev;
307 }
308
310
311 template < GUM_Numeric GUM_SCALAR >
313 gum::Instantiation Itop(*I);
314 Itop.erase(samplingBn_.variable(id));
316 for (const auto nod: samplingBn_.children(id))
317 p *= samplingBn_.cpt(nod).extract(Itop);
318 GUM_ASSERT(p.nbrDim() == 1);
319 if (p.sum() != 0) {
320 p.normalize();
321 I->chgVal(samplingBn_.variable(id), p.draw());
322 }
323 }
324
325 template < GUM_Numeric GUM_SCALAR >
329
330 template < GUM_Numeric GUM_SCALAR >
334
335 template < GUM_Numeric GUM_SCALAR >
339
340 template < GUM_Numeric GUM_SCALAR >
342 atRandom_ = atRandom;
343 }
344
345} // namespace gum
Sectioned key/value configuration with typed and documented keys.
NodeProperty< std::vector< bool > > _allowed_
the values of each node that may belong to a sample with a positive probability
void setDrawnAtRandom(bool atRandom)
void _smoothedGibbsSample_(NodeId id, Instantiation *I, GUM_SCALAR epsilon)
Size nbrDrawnVar() const
Getters and setters.
void _drawVarMonteCarlo_(NodeId nod, Instantiation *I)
static constexpr Size _nbrSweepsBySmoothingLevel_
maximal number of sweeps (over the non-evidence nodes) for each smoothing level
void setNbrDrawnVar(Size nbr)
bool _isCompatible_(const Instantiation &I) const
static constexpr std::array< double, 4 > _smoothingLevels_
growing smoothing levels: a null probability is replaced by epsilon times the smallest positive proba...
const IBayesNet< GUM_SCALAR > & samplingBn_
void _GibbsSample_(NodeId id, Instantiation *I)
change in Instantiation I a new drawn value for id
Instantiation nextSample(Instantiation prev)
draws next sample of Gibbs sampling
Instantiation _forwardSample_()
Sequence< NodeId > samplingNodes_
Instantiation monteCarloSample()
draws a first sample with a positive probability (starting point of a Gibbs chain)
const NodeProperty< Idx > * hardEv_
static constexpr Size _nbrSmoothingRestarts_
number of restarts (from a new forward sample) of the smoothed Gibbs moves
bool isDrawnAtRandom() const
GibbsOperator(const IBayesNet< GUM_SCALAR > &BN, const NodeProperty< Idx > *hardEv, Size nbr=1, bool atRandom=false)
constructor
void _mask_(NodeId node, Tensor< GUM_SCALAR > &p) const
virtual ~GibbsOperator()
Destructor.
static constexpr Size _nbrRejectionTries_
number of forward samples drawn before searching a compatible sample by smoothed Gibbs moves
NodeProperty< GUM_SCALAR > _minNonZero_
the smallest positive probability of the CPT of each node (for the smoothed Gibbs moves)
Class representing the minimal interface for Bayesian network with no numerical data.
Definition IBayesNet.h:79
Exception : several evidence are incompatible together (proba=0).
Class for assigning/browsing values to tuples of discrete variables.
Instantiation & chgVal(const DiscreteVariable &v, Idx newval)
Assign newval to variable v in the Instantiation.
bool end() const
Returns true if the Instantiation reached the end.
void inc()
Operator increment.
void add(const DiscreteVariable &v) final
Adds a new variable in the Instantiation.
void erase(const DiscreteVariable &v) final
Removes a variable from the Instantiation.
Idx val(Idx i) const
Returns the current value of the variable at position i.
void setFirst()
Assign the first values to the tuple of the Instantiation.
Exception: at least one argument passed to a function is not what was expected.
Idx nbrDim() const final
Returns the number of vars in the multidimensional container.
Exception : operation not allowed.
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition set_tpl.h:468
void insert(const Key &k)
Inserts a new element into the set.
Definition set_tpl.h:510
void erase(const Key &k)
Erases an element from the set.
Definition set_tpl.h:553
aGrUM's Tensor is a multi-dimensional array with tensor operators.
Definition tensor.h:85
Idx draw() const
get a value at random from a 1-D distribution
Definition tensor_tpl.h:737
Tensor< GUM_SCALAR > extract(const Instantiation &inst) const
create a new Tensor extracted from *this given a partial instantiation
Definition tensor_tpl.h:729
const Tensor< GUM_SCALAR > & normalize() const
normalisation of this do nothing if sum is 0
Definition tensor_tpl.h:433
GUM_SCALAR sum() const
sum of all elements in the Tensor
Definition tensor_tpl.h:158
Typed, documented, sectioned configuration singleton read from an .ini content.
#define GUM_ERROR(type, msg)
Definition exceptions.h:76
This file contains Gibbs sampling (for BNs) class definitions.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition types.h:74
Size Idx
Type for indexes.
Definition types.h:79
Size NodeId
Type for node ids.
HashTable< NodeId, VAL > NodeProperty
Property on graph elements.
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
GUM_SHARED_PUBLIC Idx randomValue(const Size max=2)
Returns a random Idx between 0 and max-1 included.
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
STL namespace.
Contains useful methods for random stuff.