Branch data Line data Source code
1 : : #include "Spn.hpp"
2 : :
3 : : #include <iomanip>
4 : : #include "mutable/util/AdjacencyMatrix.hpp"
5 : : #include <mutable/util/fn.hpp>
6 : : #include "util/Kmeans.hpp"
7 : : #include "util/RDC.hpp"
8 : :
9 : :
10 : : using namespace m;
11 : : using namespace Eigen;
12 : :
13 : :
14 : : namespace {
15 : :
16 : : std::size_t MIN_INSTANCE_SLICE = 0;
17 : : const int MAX_K = 7;
18 : : const float RDC_THRESHOLD = 0.3f;
19 : :
20 : 18 : MatrixXf normalize_minmax(const MatrixXf &data)
21 : : {
22 : 18 : const RowVectorXf mins = data.colwise().minCoeff();
23 [ + - + - : 18 : const RowVectorXf maxs = data.colwise().maxCoeff() - mins;
+ - + - ]
24 : :
25 [ - + ]: 18 : MatrixXf normalized(data.rows(), data.cols());
26 [ + + ]: 68 : for (unsigned i = 0; i != data.cols(); ++i) {
27 [ + - + - : 50 : if (maxs.array()[i] == 0) // min == max => empty range [min, max)
+ + ]
28 [ + - + - : 20 : normalized.col(i) = VectorXf::Zero(data.rows());
+ - ]
29 : : else
30 [ + - + - : 30 : normalized.col(i) = (data.col(i).array() - mins.array()[i]) / maxs.array()[i];
+ - + - +
- + - + -
+ - + - +
- ]
31 : 50 : }
32 : 18 : return normalized;
33 [ + - ]: 18 : }
34 : :
35 : : /** Compute the splitting of the columns (attributes) of the given data with the RDC algorithm.
36 : : *
37 : : * @param data the data to be split
38 : 1 : * @param variables the variable scope of the data
39 : : * @return the variable id and column id splitting candidates
40 : : */
41 : 412 : std::pair<std::vector<SmallBitset>, std::vector<SmallBitset>>rdc_split(const MatrixXf &data, SmallBitset variables)
42 : : {
43 : 412 : const auto num_cols = data.cols();
44 : 412 : AdjacencyMatrix adjacency_matrix(num_cols);
45 [ + - ]: 412 : std::vector<MatrixXf> CDF_matrices(num_cols);
46 : :
47 : : /* precompute CDF matrices */
48 [ + + + - : 1250 : for (int i = 0; i < num_cols; i++) { CDF_matrices[i] = create_CDF_matrix(data.col(i)); }
+ - + - ]
49 : :
50 : : /* build a graph with edges between correlated columns (attributes) */
51 [ + + ]: 838 : for (unsigned i = 0; i < num_cols - 1; i++) {
52 [ + + ]: 866 : for (unsigned j = i+1; j < num_cols; j++) {
53 [ + - + - ]: 440 : const float rdc_value = rdc_precomputed_CDF(CDF_matrices[i], CDF_matrices[j]);
54 : : /* if the rdc value is greater or equal to the threshold, consider columns dependent */
55 [ + + ]: 440 : if (rdc_value >= RDC_THRESHOLD) {
56 [ + - + - ]: 407 : adjacency_matrix(i,j) = true;
57 [ + - + - ]: 408 : adjacency_matrix(j,i) = true;
58 : 407 : }
59 : 440 : }
60 : 426 : }
61 : :
62 [ + - ]: 412 : SmallBitset remaining = SmallBitset::All(num_cols);
63 : 412 : std::vector<SmallBitset> connected_subgraphs;
64 : :
65 : : /* build the connected subgraphs(dependent subsets of attributes) */
66 [ + - + + ]: 843 : while (remaining) {
67 [ + - ]: 431 : auto next = remaining.begin();
68 [ + - + - ]: 431 : const SmallBitset CSG = adjacency_matrix.reachable(next.as_set());
69 [ + - ]: 431 : connected_subgraphs.emplace_back(CSG);
70 [ + - ]: 431 : remaining -= CSG;
71 : : }
72 : :
73 [ + - ]: 412 : std::vector<SmallBitset> variable_candidates(connected_subgraphs.size());
74 : 1 :
75 : 412 : std::vector<std::size_t> temp_variables;
76 [ + - ]: 412 : temp_variables.reserve(num_cols);
77 [ + - + - : 1250 : for (auto it = variables.begin(); it != variables.end(); ++it) { temp_variables.emplace_back(*it); }
+ - + + +
- + - +
- ]
78 : :
79 : : /* translate SmallBitset to correct output */
80 [ + + ]: 843 : for (std::size_t i = 0; i < connected_subgraphs.size(); ++i) {
81 [ + - + - : 1269 : for (auto it = connected_subgraphs[i].begin(); it != connected_subgraphs[i].end(); ++it) {
+ - + + +
- ]
82 [ + - + - : 838 : variable_candidates[i][temp_variables[*it]] = true;
+ - ]
83 : 838 : }
84 : 431 : }
85 : :
86 [ + - ]: 412 : return std::make_pair(connected_subgraphs, variable_candidates);
87 : 412 : }
88 : :
89 : : }
90 : :
91 : :
92 : 0 : void Spn::Node::dump() const { dump(std::cerr); }
93 : 0 : void Spn::Node::dump(std::ostream &out) const { print(out, 0); }
94 : :
95 : :
96 : : /*======================================================================================================================
97 : : * Sum Node
98 : : *====================================================================================================================*/
99 : :
100 : 70 : std::pair<float, float> Spn::Sum::evaluate(const Filter &filter, unsigned leaf_id, EvalType eval_type) const
101 : : {
102 : 70 : float expectation_result = 0.f;
103 : 70 : float likelihood_result = 0.f;
104 [ + + ]: 250 : for (auto &child : children) {
105 : 540 : auto [expectation, likelihood] = child->child->evaluate(filter, leaf_id, eval_type);
106 : 360 : expectation_result += child->weight * expectation;
107 : 360 : likelihood_result += child->weight * likelihood;
108 : : }
109 : :
110 : 70 : return { expectation_result, likelihood_result };
111 : : }
112 : :
113 : 0 : void Spn::Sum::update(VectorXf &row, SmallBitset variables, Spn::UpdateType update_type)
114 : : {
115 : : /* compute nearest cluster */
116 : 0 : unsigned nearest_centroid = 0;
117 : 0 : std::size_t num_clusters = children.size();
118 : 0 : float delta = (children[0]->centroid - row).squaredNorm();
119 [ # # ]: 0 : for (std::size_t i = 1; i < num_clusters; i++) {
120 : 0 : float next_delta = (children[i]->centroid - row).squaredNorm();
121 [ # # ]: 0 : if (next_delta < delta) {
122 : 0 : delta = next_delta;
123 : 0 : nearest_centroid = i;
124 : 0 : }
125 : 0 : }
126 : :
127 : : /* adjust weights of the sum nodes */
128 : 0 : children[nearest_centroid]->child->num_rows++;
129 : 0 : num_rows++;
130 : :
131 [ # # ]: 0 : for (std::size_t i = 0; i < num_clusters; i++) {
132 : 0 : children[i]->weight = children[i]->child->num_rows / float(num_rows);
133 : 0 : }
134 : :
135 : 0 : children[nearest_centroid]->child->update(row, variables, update_type);
136 : 0 : }
137 : :
138 : 0 : std::size_t Spn::Sum::estimate_number_distinct_values(unsigned id) const
139 : : {
140 : 0 : std::size_t result = 0;
141 [ # # ]: 0 : for (auto &child : children) {
142 : 0 : result += child->child->estimate_number_distinct_values(id);
143 : : }
144 : :
145 : 0 : return std::min(result, num_rows);
146 : : }
147 : :
148 : 0 : void Spn::Sum::print(std::ostream &out, std::size_t num_tabs) const
149 : : {
150 [ # # ]: 0 : for (std::size_t i = 0; i < children.size(); i++) {
151 [ # # ]: 0 : for (std::size_t n = 0; n < num_tabs; n++) { out << "\t"; }
152 [ # # ]: 0 : if (i != 0) { out << "+ "; }
153 : 0 : out << children[i]->weight << "\n";
154 : 0 : children[i]->child->print(out, num_tabs+1);
155 : 0 : }
156 : 0 : }
157 : :
158 : :
159 : : /*======================================================================================================================
160 : : * Product Node
161 : : *====================================================================================================================*/
162 : :
163 : 133 : std::pair<float, float> Spn::Product::evaluate(const Filter &filter, unsigned leaf_id, EvalType eval_type) const
164 : : {
165 : 133 : float expectation_result = 1.f;
166 : 133 : float likelihood_result = 1.f;
167 [ + + ]: 399 : for (auto &child : children) {
168 [ + + ]: 399 : for (const auto & it : filter) {
169 [ + + ]: 266 : if (child->variables[it.first]) {
170 : 266 : auto [expectation, likelihood] = child->child->evaluate(filter, it.first, eval_type);
171 : 134 : expectation_result *= expectation;
172 : 133 : likelihood_result *= likelihood;
173 : 133 : break;
174 : : }
175 : : }
176 : : }
177 : 133 : return {expectation_result, likelihood_result };
178 : : }
179 : :
180 : 0 : void Spn::Product::update(VectorXf &row, SmallBitset variables, UpdateType update_type)
181 : : {
182 : 0 : std::unordered_map<unsigned, unsigned> variable_to_index;
183 : 0 : unsigned index = 0;
184 [ # # # # : 0 : for (auto it = variables.begin(); it != variables.end(); ++it) { variable_to_index.emplace(*it, index++); }
# # # # #
# # # #
# ]
185 : :
186 : : /* update each child of the product node with the according subset of attributes of the row */
187 [ # # ]: 0 : for (auto &child : children) {
188 [ # # ]: 0 : std::size_t num_cols = child->variables.size();
189 [ # # ]: 1 : VectorXf proj_row(num_cols);
190 [ # # ]: 0 : auto it = child->variables.begin();
191 [ # # ]: 0 : for (std::size_t i = 0; i < num_cols; ++i) {
192 [ # # # # : 0 : proj_row(i) = row(variable_to_index[*it]);
# # # # ]
193 [ # # ]: 0 : ++it;
194 : 0 : }
195 [ # # ]: 0 : child->child->update(proj_row, child->variables, update_type);
196 : 0 : }
197 : 0 : }
198 : :
199 : 0 : std::size_t Spn::Product::estimate_number_distinct_values(unsigned id) const
200 : : {
201 [ # # ]: 0 : for (auto &child : children) {
202 [ # # ]: 0 : if (child->variables[id]) {
203 : 0 : return child->child->estimate_number_distinct_values(id);
204 : : }
205 : : }
206 : :
207 : 0 : return 0;
208 : 0 : }
209 : :
210 : 0 : void Spn::Product::print(std::ostream &out, std::size_t num_tabs) const
211 : : {
212 [ # # ]: 0 : for (std::size_t i = 0; i < children.size(); i++) {
213 [ # # ]: 0 : for (std::size_t n = 0; n < num_tabs; n++) { out << "\t"; }
214 [ # # ]: 0 : if (i != 0) { out << "* "; }
215 : 0 : out << "variable scope=(";
216 [ # # ]: 0 : for (auto it = children[i]->variables.begin(); it != children[i]->variables.end(); ++it) { out << *it; }
217 : 0 : out << "):" << "\n";
218 : 0 : children[i]->child->print(out, num_tabs+1);
219 : 0 : }
220 : 0 : }
221 : :
222 : :
223 : : /*======================================================================================================================
224 : : * DiscreteLeaf Node
225 : : *====================================================================================================================*/
226 : :
227 : 62 : std::pair<float, float> Spn::DiscreteLeaf::evaluate(const Filter &filter, unsigned leaf_id, EvalType eval_type) const
228 : : {
229 : 114 : auto [spn_operator, value] = filter.at(leaf_id);
230 : :
231 [ + + ]: 62 : if (spn_operator == IS_NULL) { return { null_probability, null_probability }; }
232 : :
233 [ - + ]: 50 : if (bins.empty()) { return { 0.f, 0.f }; }
234 : :
235 [ + + ]: 50 : if (spn_operator == EXPECTATION) {
236 : 1 : float expectation = bins[0].cumulative_probability * bins[0].value;
237 : 1 : float prev_probability = bins[0].cumulative_probability;
238 [ - + ]: 1 : for (std::size_t bin_id = 1; bin_id < bins.size(); bin_id++) {
239 : 0 : float cumulative_probability = bins[bin_id].cumulative_probability;
240 : 0 : float probability = cumulative_probability - prev_probability;
241 : 0 : expectation += probability * bins[bin_id].value;
242 : 0 : prev_probability = cumulative_probability;
243 : 0 : }
244 : 1 : return {expectation, 1.f };
245 : : }
246 : : /* probability of last bin, because the cumulative probability of the last bin is not always 1 because of NULL */
247 : 49 : float last_prob = std::prev(bins.end())->cumulative_probability;
248 : 49 : float probability = 0.f;
249 : :
250 [ + + ]: 49 : if (spn_operator == SpnOperator::EQUAL) {
251 [ - + - + : 2 : if (bins.begin()->value > value or (std::prev(bins.end()))->value < value) { return { 0.f, 0.f }; }
- + ]
252 : 2 : auto lower_bound = std::lower_bound(bins.begin(), bins.end(), value);
253 [ - + - + ]: 2 : if (lower_bound->value == value) {
254 : 1 : probability = lower_bound->cumulative_probability;
255 [ + - ]: 1 : if (lower_bound != bins.begin()) { probability -= (--lower_bound)->cumulative_probability; }
256 : 1 : }
257 : 1 : return { probability, probability };
258 : : }
259 : :
260 [ + + ]: 48 : if (spn_operator == SpnOperator::LESS) {
261 [ - + - + ]: 24 : if (bins.begin()->value >= value) { return { 0.f, 0.f }; }
262 [ + - + - ]: 24 : if ((std::prev(bins.end()))->value < value) { return { last_prob, last_prob }; }
263 : 0 : auto lower_bound = std::lower_bound(bins.begin(), bins.end(), value);
264 : 0 : probability = (--lower_bound)->cumulative_probability;
265 : 0 : return { probability, probability };
266 : : }
267 : :
268 [ + + ]: 36 : if (spn_operator == SpnOperator::LESS_EQUAL) {
269 [ - + - + ]: 24 : if (bins.begin()->value > value) { return { 0.f, 0.f }; }
270 [ + - + - ]: 24 : if ((std::prev(bins.end()))->value <= value) { return { last_prob, last_prob }; }
271 : 0 : auto upper_bound = std::upper_bound(bins.begin(), bins.end(), value,
272 : 0 : [](float bin_value, DiscreteLeaf::Bin bin) { return bin_value < bin.value; }
273 : : );
274 : 0 : probability = (--upper_bound)->cumulative_probability;
275 : 0 : return { probability, probability };
276 : : }
277 : :
278 [ + + ]: 24 : if (spn_operator == SpnOperator::GREATER) {
279 [ + - + - ]: 24 : if (bins.begin()->value > value) { return { last_prob, last_prob }; }
280 [ # # # # ]: 0 : if ((std::prev(bins.end()))->value <= value) { return { 0.f, 0.f }; }
281 : 0 : auto upper_bound = std::upper_bound(bins.begin(), bins.end(), value,
282 : 0 : [](float bin_value, DiscreteLeaf::Bin bin) { return bin_value < bin.value; }
283 : : );
284 : 0 : probability = last_prob - (--upper_bound)->cumulative_probability;
285 : 0 : return { probability, probability };
286 : : }
287 : :
288 [ + - ]: 12 : if (spn_operator == SpnOperator::GREATER_EQUAL) {
289 [ + - + - ]: 24 : if (bins.begin()->value >= value) { return { last_prob, last_prob }; }
290 [ # # # # ]: 0 : if ((std::prev(bins.end()))->value < value) { return { 0.f, 0.f }; }
291 : 0 : auto lower_bound = std::lower_bound(bins.begin(), bins.end(), value);
292 : 0 : probability = last_prob - (--lower_bound)->cumulative_probability;
293 : 0 : return { probability, probability };
294 : : }
295 : :
296 : 0 : return { 0.f, 0.f };
297 : 62 : }
298 : :
299 : 0 : void Spn::DiscreteLeaf::update(VectorXf &row, SmallBitset variables, Spn::UpdateType update_type)
300 : : {
301 : 0 : const float value = row(0);
302 : :
303 [ # # ]: 0 : if (bins.empty()) {
304 [ # # ]: 0 : if (update_type == INSERT) {
305 : 0 : bins.emplace_back(value, 1.f/(num_rows + 1));
306 : 0 : null_probability = (null_probability * num_rows) / (num_rows + 1);
307 : 0 : num_rows++;
308 : 0 : }
309 : 0 : return;
310 : : }
311 : :
312 : : /* copy bins with the actual number of values in a bin */
313 : 0 : std::vector<Bin> updated_bins;
314 [ # # ]: 0 : updated_bins.reserve(bins.size());
315 [ # # ]: 0 : updated_bins.emplace_back(bins[0].value, bins[0].cumulative_probability * num_rows);
316 [ # # ]: 0 : for (std::size_t i = 1; i < bins.size(); i++) {
317 [ # # ]: 0 : updated_bins.emplace_back(
318 : 0 : bins[i].value,
319 : 0 : (bins[i].cumulative_probability - bins[i-1].cumulative_probability) * num_rows
320 : : );
321 : 0 : }
322 : :
323 : : /* insert the update value into the correct bin or create a new one if the bin does not exist */
324 [ # # ]: 0 : if (update_type == INSERT) {
325 [ # # ]: 0 : auto lower_bound = std::lower_bound(updated_bins.begin(), updated_bins.end(), value);
326 [ # # # # ]: 0 : if (lower_bound == updated_bins.end()) { updated_bins.emplace_back(value, 1.f); }
327 [ # # # # ]: 0 : else if (lower_bound->value != value) { updated_bins.emplace(lower_bound, value, 1.f); }
328 : 0 : else { lower_bound->cumulative_probability += 1; }
329 : 0 : num_rows++;
330 : 0 : }
331 : : /* delete the update value from the correct bin */
332 : : else {
333 [ # # ]: 0 : auto lower_bound = std::lower_bound(updated_bins.begin(), updated_bins.end(), value);
334 [ # # ]: 0 : if (lower_bound->value != value) { return; }
335 : 0 : lower_bound->cumulative_probability -= 1;
336 : 0 : num_rows--;
337 : : }
338 : :
339 : : /* calculate the cumulative probability */
340 : 0 : updated_bins[0].cumulative_probability /= float(num_rows);
341 [ # # ]: 0 : for (std::size_t i = 1; i < updated_bins.size(); i++) {
342 : 0 : updated_bins[i].cumulative_probability /= float(num_rows);
343 : 0 : updated_bins[i].cumulative_probability += updated_bins[i-1].cumulative_probability;
344 : 0 : }
345 : :
346 : 0 : bins = std::move(updated_bins);
347 [ # # ]: 0 : }
348 : :
349 : 0 : std::size_t Spn::DiscreteLeaf::estimate_number_distinct_values(unsigned id) const
350 : : {
351 : 0 : return bins.size();
352 : : }
353 : :
354 : 0 : void Spn::DiscreteLeaf::print(std::ostream &out, std::size_t num_tabs) const
355 : : {
356 [ # # ]: 0 : for (std::size_t n = 0; n < num_tabs; n++) { out << "\t"; }
357 : 0 : out << "[";
358 [ # # ]: 0 : if (not bins.empty()) {
359 : 0 : out << bins[0].value << ":" << bins[0].cumulative_probability;
360 [ # # ]: 0 : for (std::size_t i = 1; i < bins.size(); i++) {
361 : 0 : out << ", " << bins[i].value << ":" << bins[i].cumulative_probability - bins[i-1].cumulative_probability;
362 : 0 : }
363 : 0 : out << " ";
364 : 0 : }
365 : 0 : out << "null_prob:" << null_probability;
366 : 0 : out << "]";
367 : 0 : out << "\n";
368 : 0 : }
369 : :
370 : :
371 : : /*======================================================================================================================
372 : : * ContinuousLeaf Node
373 : : *====================================================================================================================*/
374 : :
375 : 61 : std::pair<float, float> Spn::ContinuousLeaf::evaluate(const Filter &filter, unsigned leaf_id, EvalType eval_type) const
376 : : {
377 : 172 : auto [spn_operator, value] = filter.at(leaf_id);
378 : 61 : float probability = 0.f;
379 [ + + ]: 61 : if (spn_operator == IS_NULL) { return { null_probability, null_probability }; }
380 [ - + ]: 49 : if (bins.empty()) { return { 0.f, 0.f }; }
381 : :
382 [ - + ]: 49 : if (spn_operator == SpnOperator::EXPECTATION) {
383 : 0 : float expectation = lower_bound * lower_bound_probability;
384 : 0 : expectation += bins[0].cumulative_probability * ((bins[0].upper_bound + lower_bound) / 2.f);
385 : 0 : float prev_probability = bins[0].cumulative_probability;
386 : 0 : float prev_upper_bound = bins[0].upper_bound;
387 [ # # ]: 0 : for (std::size_t bin_id = 1; bin_id < bins.size(); bin_id++) {
388 : 0 : float upper_bound = bins[bin_id].upper_bound;
389 : 0 : float cumulative_probability = bins[bin_id].cumulative_probability;
390 : 0 : float current_probability = cumulative_probability - prev_probability;
391 : 0 : expectation += current_probability * ((prev_upper_bound + upper_bound) / 2);
392 : 0 : prev_probability = cumulative_probability;
393 : 0 : prev_upper_bound = upper_bound;
394 : 0 : }
395 : 0 : return std::make_pair(expectation, 1.f);
396 : : }
397 : :
398 [ + + ]: 49 : if (spn_operator == SpnOperator::EQUAL) {
399 [ - + - + : 2 : if (lower_bound > value or (std::prev(bins.end()))->upper_bound < value) { return { 0.f, 0.f }; }
- + ]
400 [ + - + - ]: 2 : if (lower_bound == value) { return { lower_bound_probability, lower_bound_probability }; }
401 [ # # ]: 0 : if (value <= bins[0].upper_bound) {
402 : 0 : probability = bins[0].cumulative_probability - lower_bound_probability;
403 : 0 : return { probability, probability };
404 : : }
405 : 0 : auto std_lower_bound = std::lower_bound(bins.begin(), bins.end(), value);
406 : 0 : probability = std_lower_bound->cumulative_probability - (--std_lower_bound)->cumulative_probability;
407 : 0 : return { probability, probability };
408 : : }
409 : :
410 [ + + + + ]: 48 : if (spn_operator == LESS or spn_operator == LESS_EQUAL) {
411 [ - + - + ]: 48 : if (lower_bound >= value) {
412 [ # # # # : 0 : if (lower_bound == value and spn_operator == LESS_EQUAL) {
# # ]
413 : 0 : return { lower_bound_probability, lower_bound_probability };
414 : : }
415 : 0 : return { 0.f, 0.f };
416 : : }
417 [ + - + - ]: 48 : if ((std::prev(bins.end()))->upper_bound <= value) {
418 : 24 : probability = std::prev(bins.end())->cumulative_probability;
419 : 24 : return { probability, probability };
420 : : }
421 [ # # ]: 0 : if (value <= bins[0].upper_bound) {
422 : 0 : float prob = bins[0].cumulative_probability - lower_bound_probability;
423 : 0 : probability = lower_bound_probability +
424 : 0 : (prob * ((value - lower_bound) / (bins[0].upper_bound - lower_bound)));
425 : 0 : return { probability, probability };
426 : : }
427 : 0 : auto std_lower_bound = std::lower_bound(bins.begin(), bins.end(), value);
428 : 0 : auto &bin = *std_lower_bound;
429 : 0 : auto &prev_bin = *(--std_lower_bound);
430 : 0 : float bin_probability = bin.cumulative_probability - prev_bin.cumulative_probability;
431 : 0 : float percentile = (value - prev_bin.upper_bound) / (bin.upper_bound - prev_bin.upper_bound);
432 [ # # # # ]: 0 : switch (eval_type) {
433 : : case APPROXIMATE:
434 : 0 : probability = prev_bin.cumulative_probability + (bin_probability * percentile);
435 : : case UPPER_BOUND:
436 : 0 : probability = bin.cumulative_probability;
437 : : case LOWER_BOUND:
438 : 0 : probability = prev_bin.cumulative_probability;
439 : 0 : }
440 : 0 : return { probability, probability };
441 : : }
442 : :
443 [ + + + - ]: 24 : if (spn_operator == GREATER_EQUAL or spn_operator == GREATER) {
444 : 24 : float last_prob = std::prev(bins.end())->cumulative_probability;
445 [ + - + - ]: 48 : if (lower_bound >= value) {
446 [ + + + + : 48 : if (lower_bound == value and spn_operator == GREATER) {
+ - ]
447 : 0 : probability = last_prob - lower_bound_probability;
448 : 0 : return { probability, probability };
449 : : }
450 : 24 : return { last_prob, last_prob };
451 : : }
452 [ # # # # ]: 0 : if ((std::prev(bins.end()))->upper_bound <= value) { return { 0.f, 0.f }; }
453 [ # # ]: 0 : if (value <= bins[0].upper_bound) {
454 : 0 : float prob = bins[0].cumulative_probability - lower_bound_probability;
455 : 0 : float split_bin_prob = (prob * (1.f - ((value - lower_bound) / (bins[0].upper_bound - lower_bound))));
456 : 0 : probability = last_prob - bins[0].cumulative_probability + split_bin_prob;
457 : 0 : return { probability, probability };
458 : : }
459 : 0 : auto std_lower_bound = std::lower_bound(bins.begin(), bins.end(), value);
460 : 0 : auto &bin = *std_lower_bound;
461 : 0 : auto &prev_bin = *(--std_lower_bound);
462 : 0 : float bin_probability = bin.cumulative_probability - prev_bin.cumulative_probability;
463 : 0 : float percentile = 1.f - ((value - prev_bin.upper_bound) / (bin.upper_bound - prev_bin.upper_bound));
464 [ # # # # ]: 0 : switch (eval_type) {
465 : : case APPROXIMATE:
466 : 0 : probability = last_prob - bin.cumulative_probability + (bin_probability * percentile);
467 : : case UPPER_BOUND:
468 : 0 : probability = last_prob - prev_bin.cumulative_probability;
469 : : case LOWER_BOUND:
470 : 0 : probability = last_prob - bin.cumulative_probability;
471 : 0 : }
472 : 0 : return { probability, probability };
473 : : }
474 : :
475 : 0 : return { 0.f, 0.f };
476 : 61 : }
477 : :
478 : 0 : void Spn::ContinuousLeaf::update(VectorXf &row, SmallBitset variables, Spn::UpdateType update_type)
479 : : {
480 : 0 : const float value = row(0);
481 : :
482 [ # # ]: 0 : if (bins.empty()) {
483 [ # # ]: 0 : if (update_type == INSERT) {
484 : 0 : bins.emplace_back(value, 1.f/(num_rows + 1));
485 : 0 : null_probability = (null_probability * num_rows) / (num_rows + 1);
486 : 0 : num_rows++;
487 : 0 : }
488 : 0 : return;
489 : : }
490 : :
491 : : /* copy bins with the actual number of values in a bin */
492 : 0 : std::vector<Bin> updated_bins;
493 : 0 : float updated_lower_bound_prob = lower_bound_probability * num_rows;
494 [ # # ]: 0 : updated_bins.reserve(bins.size());
495 [ # # ]: 0 : updated_bins.emplace_back(
496 : 0 : bins[0].upper_bound,
497 : 0 : (bins[0].cumulative_probability - lower_bound_probability) * num_rows
498 : : );
499 [ # # ]: 0 : for (std::size_t i = 1; i < bins.size(); i++) {
500 [ # # ]: 0 : updated_bins.emplace_back(
501 : 0 : bins[i].upper_bound,
502 : 0 : (bins[i].cumulative_probability - bins[i-1].cumulative_probability) * num_rows
503 : : );
504 : 0 : }
505 : :
506 : : /* insert the update value into the correct bin or create a new one if the bin does not exist */
507 [ # # ]: 0 : if (update_type == INSERT) {
508 [ # # ]: 0 : if (value == lower_bound) {
509 : 0 : updated_lower_bound_prob += 1;
510 [ # # ]: 0 : } else if (value < lower_bound) {
511 : 0 : updated_bins[0].cumulative_probability += updated_lower_bound_prob;
512 : 0 : lower_bound = value;
513 : 0 : updated_lower_bound_prob = 1.f;
514 [ # # ]: 0 : } else if (value > updated_bins[updated_bins.size() - 1].upper_bound) {
515 [ # # ]: 0 : updated_bins.emplace_back(value, 1.f);
516 : 0 : } else {
517 [ # # ]: 0 : auto std_lower_bound = std::lower_bound(updated_bins.begin(), updated_bins.end(), value);
518 : 0 : std_lower_bound->cumulative_probability += 1;
519 : : }
520 : 0 : num_rows++;
521 : 0 : }
522 : : /* delete the update value from the correct bin */
523 : : else {
524 [ # # # # ]: 0 : if (value < lower_bound or value > updated_bins[updated_bins.size() - 1].upper_bound) { return; }
525 [ # # ]: 0 : if (value == lower_bound) {
526 : 0 : updated_lower_bound_prob += 1;
527 : 0 : } else {
528 [ # # ]: 0 : auto std_lower_bound = std::lower_bound(updated_bins.begin(), updated_bins.end(), value);
529 [ # # ]: 0 : if (std_lower_bound->cumulative_probability == 0) { return; }
530 : 0 : std_lower_bound->cumulative_probability -= 1;
531 : : }
532 : 0 : num_rows--;
533 : : }
534 : :
535 : : /* calculate the cumulative probability */
536 : 0 : updated_lower_bound_prob /= float(num_rows);
537 : 0 : updated_bins[0].cumulative_probability /= float(num_rows);
538 : 0 : updated_bins[0].cumulative_probability += updated_lower_bound_prob;
539 [ # # ]: 0 : for (std::size_t i = 1; i < updated_bins.size(); i++) {
540 : 0 : updated_bins[i].cumulative_probability /= float(num_rows);
541 : 0 : updated_bins[i].cumulative_probability += updated_bins[i-1].cumulative_probability;
542 : 0 : }
543 : 0 : lower_bound_probability = updated_lower_bound_prob;
544 : 0 : bins = std::move(updated_bins);
545 [ # # ]: 0 : }
546 : :
547 : 0 : std::size_t Spn::ContinuousLeaf::estimate_number_distinct_values(unsigned id) const
548 : : {
549 : 0 : return num_rows;
550 : : }
551 : :
552 : 0 : void Spn::ContinuousLeaf::print(std::ostream &out, std::size_t num_tabs) const
553 : : {
554 [ # # ]: 0 : for (std::size_t n = 0; n < num_tabs; n++) { out << "\t"; }
555 : 0 : out << "[";
556 [ # # ]: 0 : if (not bins.empty()) {
557 : 0 : out << lower_bound_probability << ": ";
558 : 0 : out << lower_bound;
559 : 0 : out << " :" << bins[0].cumulative_probability - lower_bound_probability << ": " << bins[0].upper_bound;
560 [ # # ]: 0 : for (std::size_t i = 1; i < bins.size(); i++) {
561 : 0 : out << " :" << bins[i].cumulative_probability - bins[i-1].cumulative_probability;
562 : 0 : out << ": " << bins[i].upper_bound;
563 : 0 : }
564 : 0 : out << " ";
565 : 0 : }
566 : 0 : out << "null_prob:" << null_probability;
567 : 0 : out << "]";
568 : 0 : out << "\n";
569 : 0 : }
570 : :
571 : : /*======================================================================================================================
572 : : * Spn
573 : : *====================================================================================================================*/
574 : :
575 : : /*----- Learning helper methods --------------------------------------------------------------------------------------*/
576 : :
577 : 170 : std::unique_ptr<Spn::Product> Spn::create_product_min_slice(LearningData &ld)
578 : : {
579 : 170 : std::vector<std::unique_ptr<Product::ChildWithVariables>> children;
580 [ + - ]: 170 : auto variable_it = ld.variables.begin();
581 [ + + ]: 511 : for (auto i = 0; i < ld.data.cols(); i++) {
582 [ + - + - ]: 341 : const MatrixXf &data = ld.data.col(i);
583 [ + - + - ]: 341 : const MatrixXf &normalized = ld.normalized.col(i);
584 [ + - + - ]: 341 : const MatrixXi &null_matrix = ld.null_matrix.col(i);
585 [ + - ]: 341 : SmallBitset variables(variable_it.as_set());
586 [ + - ]: 341 : ++variable_it;
587 [ + - ]: 341 : std::vector<LeafType> split_leaf_types{ld.leaf_types[i]};
588 [ - + ]: 341 : LearningData split_data(
589 : 341 : data,
590 : 341 : normalized,
591 : 341 : null_matrix,
592 : 341 : variables,
593 [ - + ]: 341 : split_leaf_types
594 : : );
595 [ - + - + ]: 341 : auto child = std::make_unique<Product::ChildWithVariables>(learn_node(split_data), variables);
596 [ - + ]: 341 : children.push_back(std::move(child));
597 : 341 : }
598 [ + - ]: 170 : return std::make_unique<Product>(std::move(children), ld.data.rows());
599 : 170 : }
600 : :
601 : :
602 : 16 : std::unique_ptr<Spn::Product> Spn::create_product_rdc(
603 : : LearningData &ld,
604 : : std::vector<SmallBitset> &column_candidates,
605 : : std::vector<SmallBitset> &variable_candidates
606 : : )
607 : : {
608 : 16 : std::vector<std::unique_ptr<Product::ChildWithVariables>> children;
609 [ + + ]: 48 : for (std::size_t current_split = 0; current_split < column_candidates.size(); current_split++) {
610 [ + - ]: 32 : std::size_t split_size = column_candidates[current_split].size();
611 : 32 : std::vector<LeafType> split_leaf_types;
612 [ + - ]: 32 : split_leaf_types.reserve(split_size);
613 : 32 : std::vector<unsigned> column_index;
614 [ + - ]: 32 : column_index.reserve(split_size);
615 [ + - + - : 78 : for (auto it = column_candidates[current_split].begin(); it != column_candidates[current_split].end(); ++it) {
+ - + + +
- ]
616 [ + - + - ]: 46 : split_leaf_types.push_back(ld.leaf_types[*it]);
617 [ + - + - ]: 46 : column_index.push_back(*it);
618 : 46 : }
619 : :
620 [ + - + - ]: 32 : const MatrixXf &data = ld.data(all, column_index);
621 [ + - + - ]: 32 : const MatrixXf &normalized = ld.normalized(all, column_index);
622 [ + - + - ]: 32 : const MatrixXi &null_matrix = ld.null_matrix(all, column_index);
623 [ + - + - ]: 32 : LearningData split_data(data, normalized, null_matrix, variable_candidates[current_split], split_leaf_types);
624 [ - + ]: 32 : auto child = std::make_unique<Product::ChildWithVariables>(
625 [ + - ]: 32 : learn_node(split_data),
626 : 32 : variable_candidates[current_split]
627 : : );
628 [ - + ]: 32 : children.push_back(std::move(child));
629 : 32 : }
630 [ + - ]: 16 : return std::make_unique<Product>(std::move(children), ld.data.rows());
631 : 16 : }
632 : :
633 : 99 : std::unique_ptr<Spn::Sum> Spn::create_sum(Spn::LearningData &ld)
634 : : {
635 : 99 : const auto num_rows = ld.data.rows();
636 : :
637 : 99 : int k = 2;
638 : :
639 : 99 : unsigned prev_num_split_nodes = 0;
640 : 99 : std::vector<std::vector<SmallBitset>> prev_cluster_column_candidates;
641 : 99 : std::vector<std::vector<SmallBitset>> prev_cluster_variable_candidates;
642 : 99 : std::vector<std::vector<unsigned>> prev_cluster_row_ids;
643 [ + - ]: 99 : MatrixRXf prev_centroids;
644 : :
645 : : /* increment k of Kmeans until we get a good clustering according to RDC splits in the clusters */
646 : 254 : while (true) {
647 : 254 : unsigned num_split_nodes = 0;
648 : :
649 [ + - ]: 11629 : auto [labels, centroids] = kmeans_with_centroids(ld.normalized, k);
650 : :
651 [ + - ]: 254 : std::vector<std::vector<SmallBitset>> cluster_column_candidates(k);
652 [ + - ]: 254 : std::vector<std::vector<SmallBitset>> cluster_variable_candidates(k);
653 [ + - ]: 254 : std::vector<std::vector<unsigned>> cluster_row_ids(k);
654 : :
655 [ + + ]: 11474 : for (unsigned current_row = 0; current_row < num_rows; current_row++) {
656 [ + - ]: 11220 : cluster_row_ids[labels[current_row]].push_back(current_row);
657 : 11220 : }
658 : :
659 : : /* if only one cluster, split this cluster into k clusters */
660 : 254 : bool only_one_cluster = not cluster_row_ids[0].empty();
661 [ + + ]: 803 : for (int i = 1; i < k; i++)
662 [ + + ]: 549 : only_one_cluster = only_one_cluster and cluster_row_ids[i].empty();
663 : :
664 [ + - ]: 254 : if (only_one_cluster) {
665 : 0 : const std::size_t subvector_size = cluster_row_ids[0].size() / k;
666 [ # # ]: 0 : std::vector<std::vector<unsigned>> new_cluster_row_ids(k);
667 [ # # ]: 0 : for (std::size_t cluster_id = 0; cluster_id < k - 1; cluster_id++) {
668 [ # # ]: 0 : std::vector<unsigned> subvector(
669 : 0 : cluster_row_ids[0].begin() + (cluster_id * subvector_size),
670 : 0 : cluster_row_ids[0].begin() + ((cluster_id + 1) * subvector_size)
671 : : );
672 : 0 : new_cluster_row_ids[cluster_id] = std::move(subvector);
673 : 0 : }
674 [ # # ]: 0 : std::vector<unsigned> last_subvector(
675 : 0 : cluster_row_ids[0].begin() + ((k - 1) * subvector_size),
676 : 0 : cluster_row_ids[0].end()
677 : : );
678 : 0 : new_cluster_row_ids[k - 1] = std::move(last_subvector);
679 : :
680 : 0 : cluster_row_ids = std::move(new_cluster_row_ids);
681 : 0 : }
682 : :
683 : : /* check the splitting of attributes in each cluster */
684 [ + + ]: 1057 : for (unsigned label_id = 0; label_id < k; label_id++) {
685 : 803 : std::size_t cluster_size = cluster_row_ids[label_id].size();
686 [ + - ]: 803 : if (cluster_size == 0) { continue; }
687 : :
688 [ + - + - ]: 803 : const MatrixXf &data = ld.data(cluster_row_ids[label_id], all);
689 : :
690 [ + + ]: 803 : if (cluster_size <= MIN_INSTANCE_SLICE) {
691 : 420 : num_split_nodes++;
692 : 420 : cluster_column_candidates[label_id] = std::vector<SmallBitset>();
693 : 420 : cluster_variable_candidates[label_id] = std::vector<SmallBitset>();
694 : 420 : } else {
695 [ + - ]: 393 : auto [current_column_candidates, current_variable_candidates] = rdc_split(data, ld.variables);
696 [ + + ]: 383 : if (current_column_candidates.size() > 1) { num_split_nodes++; }
697 : 383 : cluster_column_candidates[label_id] = std::move(current_column_candidates);
698 : 383 : cluster_variable_candidates[label_id] = std::move(current_variable_candidates);
699 : 383 : }
700 : 803 : }
701 : :
702 : : /* if the number of split attributes does not increase or if there is a split in each cluster, build sum node */
703 : : if (
704 [ + + ]: 409 : ((num_split_nodes <= prev_num_split_nodes or prev_num_split_nodes == prev_cluster_row_ids.size())
705 [ + + ]: 254 : and prev_num_split_nodes != 0) or k >= MAX_K
706 : : ) {
707 : 99 : std::vector<std::unique_ptr<Sum::ChildWithWeight>> children;
708 [ + + ]: 353 : for (std::size_t cluster_id = 0; cluster_id < k - 1; cluster_id++) {
709 [ + - + - ]: 254 : const MatrixXf &data = ld.data(prev_cluster_row_ids[cluster_id], all);
710 [ + - + - ]: 254 : const MatrixXf &normalized = ld.normalized(prev_cluster_row_ids[cluster_id], all);
711 [ + - + - ]: 254 : const MatrixXi &null_matrix = ld.null_matrix(prev_cluster_row_ids[cluster_id], all);
712 [ + - + - ]: 254 : LearningData cluster_data(data, normalized, null_matrix, ld.variables, ld.leaf_types);
713 : 254 : const float weight = float(data.rows())/float(num_rows);
714 : 254 : std::size_t cluster_vertical_partitions = prev_cluster_column_candidates[cluster_id].size();
715 : :
716 : : /* since we already determined the node type of each cluster (child of the sum node), we can
717 : : * directly build the children of the sum node */
718 : 254 : std::unique_ptr<Node> child_node;
719 [ + + ]: 254 : if (cluster_vertical_partitions == 0) {
720 [ + - ]: 168 : child_node = create_product_min_slice(cluster_data);
721 [ + + ]: 254 : } else if (cluster_vertical_partitions == 1) {
722 [ + - ]: 84 : child_node = create_sum(cluster_data);
723 : 84 : } else {
724 [ + - ]: 2 : child_node = create_product_rdc(
725 : : cluster_data,
726 : 2 : prev_cluster_column_candidates[cluster_id],
727 : 2 : prev_cluster_variable_candidates[cluster_id]
728 : : );
729 : : }
730 [ + - ]: 254 : std::unique_ptr<Sum::ChildWithWeight> child = std::make_unique<Sum::ChildWithWeight>(
731 : : std::move(child_node),
732 : : weight,
733 [ + - ]: 254 : prev_centroids.row(cluster_id)
734 : : );
735 : :
736 [ + - ]: 254 : children.push_back(std::move(child));
737 : 254 : }
738 : :
739 [ + - ]: 99 : return std::make_unique<Sum>(std::move(children), num_rows);
740 : 99 : }
741 : 155 : prev_num_split_nodes = num_split_nodes;
742 : 155 : prev_cluster_column_candidates = std::move(cluster_column_candidates);
743 : 155 : prev_cluster_variable_candidates = std::move(cluster_variable_candidates);
744 : 155 : prev_cluster_row_ids = std::move(cluster_row_ids);
745 [ + - ]: 155 : prev_centroids = centroids;
746 : 155 : k++;
747 [ + + ]: 254 : }
748 : 99 : }
749 : :
750 : :
751 : 391 : std::unique_ptr<Spn::Node> Spn::learn_node(LearningData &ld)
752 : : {
753 : 391 : const auto num_rows = ld.data.rows();
754 : 391 : const auto num_cols = ld.data.cols();
755 : :
756 : : /* build leaf */
757 [ + + ]: 391 : if (num_cols == 1) {
758 [ + + ]: 360 : if (ld.leaf_types[0] == DISCRETE) {
759 : 185 : std::vector<DiscreteLeaf::Bin> bins;
760 : : /* If every value is NULL */
761 [ + - - + ]: 185 : if (ld.null_matrix.minCoeff() == 1) {
762 [ # # ]: 0 : return std::make_unique<DiscreteLeaf>(std::move(bins), 1.f, num_rows);
763 : : }
764 : 185 : unsigned null_counter = 0;
765 [ + + ]: 2311 : for (auto i = 0; i < num_rows; i++) {
766 [ + - + - ]: 2126 : if (ld.null_matrix(i, 0) == 1) {
767 : 0 : null_counter++;
768 : 0 : continue;
769 : : }
770 [ + - ]: 2126 : const auto current_value = ld.data(i, 0);
771 : : /* insert value into sorted vector of bins */
772 [ + - ]: 2126 : auto lower_bound = std::lower_bound(bins.begin(), bins.end(), current_value);
773 [ + + + - ]: 2126 : if (lower_bound == bins.end()) { bins.emplace_back(current_value, 1.f); }
774 : : /* if bin already exists, increment counter */
775 [ - + ]: 701 : else if (lower_bound->value == current_value) { lower_bound->cumulative_probability++; }
776 [ # # ]: 0 : else { bins.emplace(lower_bound, current_value, 1.f); }
777 : 2126 : }
778 : :
779 : 185 : bins[0].cumulative_probability /= float(num_rows);
780 [ + + ]: 1425 : for (std::size_t i = 1; i < bins.size(); i++) {
781 : 1240 : bins[i].cumulative_probability /= float(num_rows);
782 : 1240 : bins[i].cumulative_probability += bins[i-1].cumulative_probability;
783 : 1240 : }
784 [ + - ]: 185 : return std::make_unique<DiscreteLeaf>(std::move(bins), null_counter / float(num_rows), num_rows);
785 : 185 : } else {
786 : 175 : std::vector<ContinuousLeaf::Bin> bins;
787 : : /* If every value is NULL */
788 [ + - - + ]: 175 : if (ld.null_matrix.minCoeff() == 1) {
789 [ # # ]: 0 : return std::make_unique<ContinuousLeaf>(std::move(bins), 0.f, 0.f, 1.f, num_rows);
790 : : }
791 [ + - ]: 175 : const float max = ld.data.maxCoeff();
792 [ + - ]: 175 : const float min = ld.data.minCoeff();
793 [ + - ]: 175 : const auto num_bins = 1 + log2_ceil(std::size_t(num_rows));
794 : 175 : const float bin_width = (max - min) / float(num_bins);
795 : 175 : const float lower_bound = min;
796 : 175 : unsigned lower_bound_counter = 0.f;
797 : 175 : unsigned null_counter = 0.f;
798 : :
799 : : /* initialise bins */
800 [ + - ]: 175 : bins.reserve(num_bins);
801 [ + + ]: 959 : for(std::size_t bin_id = 0; bin_id < num_bins; bin_id++) {
802 [ + - ]: 784 : bins.emplace_back(min + (float(bin_id + 1) * bin_width), 0.f);
803 : 784 : }
804 : :
805 : : /* fill the values into the existing bins */
806 [ + + ]: 2275 : for (unsigned i = 0; i < num_rows; i++) {
807 [ + - + - ]: 2100 : if (ld.null_matrix(i, 0) == 1) {
808 : 0 : null_counter++;
809 : 0 : continue;
810 : : }
811 [ + - ]: 2100 : const auto current_value = ld.data(i, 0);
812 [ + + ]: 2100 : if (current_value == lower_bound) {
813 : 868 : lower_bound_counter++;
814 : 868 : continue;
815 : : }
816 [ + - ]: 1232 : auto std_lower_bound = std::lower_bound(bins.begin(), bins.end(), current_value);
817 : 1232 : std_lower_bound->cumulative_probability++;
818 : 1232 : }
819 : :
820 : 175 : float lower_bound_probability = lower_bound_counter / float(num_rows);
821 : 175 : bins[0].cumulative_probability /= float(num_rows);
822 : 175 : bins[0].cumulative_probability += lower_bound_probability;
823 : :
824 [ + + ]: 784 : for (std::size_t i = 1; i < bins.size(); i++) {
825 : 609 : bins[i].cumulative_probability /= float(num_rows);
826 : 609 : bins[i].cumulative_probability += bins[i-1].cumulative_probability;
827 : 609 : }
828 [ + - ]: 175 : return std::make_unique<ContinuousLeaf>(
829 : : std::move(bins),
830 : : lower_bound,
831 : : lower_bound_probability,
832 : 175 : null_counter / float(num_rows),
833 : : num_rows
834 : : );
835 : 175 : }
836 : : }
837 : :
838 : : /* build product node with the minimum instance slice */
839 [ + + ]: 31 : if (num_rows <= MIN_INSTANCE_SLICE) { return create_product_min_slice(ld); }
840 : :
841 : : /* build product node with the RDC algorithm */
842 : 29 : auto [column_candidates, variable_candidates] = rdc_split(ld.data, ld.variables);
843 [ + + + - : 29 : if (column_candidates.size() != 1) { return create_product_rdc(ld, column_candidates, variable_candidates); }
+ - ]
844 : :
845 : : /* build sum node */
846 [ + - ]: 15 : else { return create_sum(ld); }
847 : 391 : }
848 : :
849 : : /*----- Learning -----------------------------------------------------------------------------------------------------*/
850 : :
851 : 19 : Spn Spn::learn_spn(Eigen::MatrixXf &data, Eigen::MatrixXi &null_matrix, std::vector<LeafType> &leaf_types)
852 : : {
853 : 19 : std::size_t num_rows = data.rows();
854 : 19 : MIN_INSTANCE_SLICE = std::max<std::size_t>((0.1 * num_rows), 1);
855 : :
856 [ + + ]: 19 : if (num_rows == 0) {
857 : 1 : std::vector<DiscreteLeaf::Bin> bins;
858 [ + - - + ]: 1 : return Spn(0, std::make_unique<DiscreteLeaf>(std::move(bins), 0, 0));
859 : 1 : }
860 : :
861 : : /* replace NULL in the data matrix with the mean of the attribute */
862 [ + + ]: 68 : for (std::size_t col_id = 0; col_id < data.cols(); col_id++) {
863 [ + - ]: 50 : if (null_matrix.col(col_id).maxCoeff() == 0) { continue; } // there is no NULL
864 [ # # ]: 0 : if (null_matrix.col(col_id).minCoeff() == 1) { continue; } // there is only NULL
865 : 0 : float mean = 0;
866 : 0 : int num_not_null = 0;
867 [ # # ]: 0 : for (std::size_t row_id = 0; row_id < data.rows(); row_id++) {
868 [ # # ]: 0 : if (null_matrix(row_id, col_id) == 1) { continue; }
869 : 0 : mean += (data(row_id, col_id) - mean) / ++num_not_null; // iterative mean
870 : 0 : }
871 [ # # ]: 0 : for (std::size_t row_id = 0; row_id < data.rows(); row_id++) {
872 [ # # ]: 0 : if (null_matrix(row_id, col_id) == 1) { data(row_id, col_id) = mean; }
873 : 0 : }
874 : 0 : }
875 : :
876 : 18 : SmallBitset variables = SmallBitset::All(data.cols());
877 : :
878 : 18 : auto normalized = normalize_minmax(data);
879 [ + - ]: 18 : LearningData ld(
880 : 18 : data,
881 : : normalized,
882 : 18 : null_matrix,
883 : 18 : variables,
884 : 18 : std::move(leaf_types)
885 : : );
886 : :
887 [ + - + - ]: 18 : return Spn(num_rows, learn_node(ld));
888 : 19 : }
889 : :
890 : : /*----- Inference ----------------------------------------------------------------------------------------------------*/
891 : :
892 : 0 : void Spn::update(VectorXf &row, UpdateType update_type)
893 : : {
894 : 0 : SmallBitset variables((1 << row.size()) - 1);
895 : 0 : root_->update(row, variables, update_type);
896 : 0 : }
897 : :
898 : 12 : float Spn::likelihood(const Filter &filter) const
899 : : {
900 : 12 : return root_->evaluate(filter, filter.begin()->first, APPROXIMATE).second;
901 : : }
902 : :
903 : 0 : float Spn::upper_bound(const Filter &filter) const
904 : : {
905 : 0 : return root_->evaluate(filter, filter.begin()->first, UPPER_BOUND).second;
906 : : }
907 : :
908 : 0 : float Spn::lower_bound(const Filter &filter) const
909 : : {
910 : 0 : return root_->evaluate(filter, filter.begin()->first, LOWER_BOUND).second;
911 : : }
912 : :
913 : 1 : float Spn::expectation(unsigned attribute_id, const Filter &filter) const
914 : : {
915 : 1 : auto filter_copy = filter;
916 [ + - + - ]: 1 : filter_copy.emplace(attribute_id, std::make_pair(EXPECTATION, 0.f));
917 : :
918 [ + - ]: 1 : auto [cond_expectation, likelihood] = root_->evaluate(filter_copy, filter_copy.begin()->first, APPROXIMATE);
919 : 1 : float llh = 1.f;
920 [ + - ]: 1 : if (!filter.empty()) {
921 [ # # ]: 0 : if (likelihood == 0) { return 0; }
922 : 0 : llh = likelihood;
923 : 0 : }
924 : :
925 : 1 : return cond_expectation / llh;
926 : 1 : }
927 : :
928 : 0 : void Spn::update_row(VectorXf &old_row, VectorXf &updated_row)
929 : : {
930 : 0 : delete_row(old_row);
931 : 0 : insert_row(updated_row);
932 : 0 : }
933 : :
934 : 0 : void Spn::insert_row(VectorXf &row)
935 : : {
936 : 0 : update(row, INSERT);
937 : 0 : num_rows_++;
938 : 0 : }
939 : :
940 : 0 : void Spn::delete_row(VectorXf &row)
941 : : {
942 : 0 : update(row, DELETE);
943 : 0 : num_rows_--;
944 : 0 : }
945 : :
946 : 0 : std::size_t Spn::estimate_number_distinct_values(unsigned attribute_id) const
947 : : {
948 : 0 : return root_->estimate_number_distinct_values(attribute_id);
949 : : }
950 : :
951 : 0 : void Spn::dump() const { dump(std::cerr); }
952 : :
953 : 0 : void Spn::dump(std::ostream &out) const
954 : : {
955 : 0 : out << "\n";
956 : 0 : root_->dump(out);
957 : 0 : }
|
