Value Error: k must not be greater than n.

[inagege]

Dear readers,

I've got a problem with using the prim implementation of ema workbench. I run the Prim algorithm repeatedly, using the same data but changing the number of dimensions and datapoints. I afterwards compare density and coverage.
Every time I generate a new Prim Object and use the .find_box() function. After a few iterations I always get the same error message (see below). It's not always at the same iteration, but newer on the first.
Has anybody had similar problems or a solution to the problem?

`ValueError`                                Traceback (most recent call last)
Cell In[2], line 1
----> 1 create_plot_generated_data(calculate_y_ackley, 15, package)

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/Utils/util_functions.py:253, in create_plot_generated_data(function_string, dimension_max, package)
    250 x = x[selected_columns]
    251 x_test_temp = x_test[selected_columns]
--> 253 precisions, recalls, boxes = get_list_all_precisions_recalls_boxes(x, y, package)
    254 if len(precisions) <= 0:
    255     prec_train.append(0)

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/Utils/util_functions.py:83, in get_list_all_precisions_recalls_boxes(x, y, package)
     80 precision = []
     82 prim_alg = prim_emaworkbench.Prim(x, y, peel_alpha=0.1, threshold=0.7)
---> 83 boxes = prim_alg.find_box()
     85 for index, row in boxes.peeling_trajectory.iterrows():
     86     recall.append(row['coverage'])

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/ema_workbench/analysis/prim.py:1092, in Prim.find_box(self)
   1089 box = PrimBox(self, self.box_init, self.yi_remaining[:])
   1091 #  perform peeling phase
-> 1092 box = self._peel(box)
   1093 _logger.debug("peeling completed")
   1095 # perform pasting phase

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/ema_workbench/analysis/prim.py:1230, in Prim._peel(self, box)
   1228 if (mass_new >= self.mass_min) & (mass_new < mass_old) & (obj_score > 0):
   1229     box.update(box_new, indices)
-> 1230     return self._peel(box)
   1231 else:
   1232     # else return received box
   1233     return box

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/ema_workbench/analysis/prim.py:1230, in Prim._peel(self, box)
   1228 if (mass_new >= self.mass_min) & (mass_new < mass_old) & (obj_score > 0):
   1229     box.update(box_new, indices)
-> 1230     return self._peel(box)
   1231 else:
   1232     # else return received box
   1233     return box

    [... skipping similar frames: Prim._peel at line 1230 (14 times)]

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/ema_workbench/analysis/prim.py:1230, in Prim._peel(self, box)
   1228 if (mass_new >= self.mass_min) & (mass_new < mass_old) & (obj_score > 0):
   1229     box.update(box_new, indices)
-> 1230     return self._peel(box)
   1231 else:
   1232     # else return received box
   1233     return box

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/ema_workbench/analysis/prim.py:1229, in Prim._peel(self, box)
   1226 mass_new = self.y[indices].shape[0] / self.n
   1228 if (mass_new >= self.mass_min) & (mass_new < mass_old) & (obj_score > 0):
-> 1229     box.update(box_new, indices)
   1230     return self._peel(box)
   1231 else:
   1232     # else return received box

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/ema_workbench/analysis/prim.py:806, in PrimBox.update(self, box_lims, indices)
    801 self.peeling_trajectory = pd.concat(
    802     [self.peeling_trajectory, new_row], ignore_index=True, sort=True
    803 )
    805 # boxlims
--> 806 qp = self._calculate_quasi_p(i, restricted_dims)
    807 self.qp.append(qp)
    808 self._cur_box = len(self.peeling_trajectory) - 1

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/ema_workbench/analysis/prim.py:903, in PrimBox._calculate_quasi_p(self, i, restricted_dims)
    899 y = self.prim.y[self.prim.yi_remaining]
    901 # TODO use apply on df?
--> 903 qp_values = box_lim.apply(
    904     calculate_qp,
    905     axis=0,
    906     result_type="expand",
    907     args=[x, y, Hbox, Tbox, box_lim, self.box_lims[0]],
    908 )
    910 # TODO:: this has knock on consequences
    911 # TODO:: elsewhere in the code (e.g. all box visualizations
    912 # TODO:: as well as in CART etc.)
    913 # qp_values = qp_values.replace(-1, np.NaN)
    914 qp_values = qp_values.to_dict(orient="list")

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/pandas/core/frame.py:8848, in DataFrame.apply(self, func, axis, raw, result_type, args, **kwargs)
   8837 from pandas.core.apply import frame_apply
   8839 op = frame_apply(
   8840     self,
   8841     func=func,
   (...)
   8846     kwargs=kwargs,
   8847 )
-> 8848 return op.apply().__finalize__(self, method="apply")

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/pandas/core/apply.py:733, in FrameApply.apply(self)
    730 elif self.raw:
    731     return self.apply_raw()
--> 733 return self.apply_standard()

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/pandas/core/apply.py:857, in FrameApply.apply_standard(self)
    856 def apply_standard(self):
--> 857     results, res_index = self.apply_series_generator()
    859     # wrap results
    860     return self.wrap_results(results, res_index)

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/pandas/core/apply.py:873, in FrameApply.apply_series_generator(self)
    870 with option_context("mode.chained_assignment", None):
    871     for i, v in enumerate(series_gen):
    872         # ignore SettingWithCopy here in case the user mutates
--> 873         results[i] = self.f(v)
    874         if isinstance(results[i], ABCSeries):
    875             # If we have a view on v, we need to make a copy because
    876             #  series_generator will swap out the underlying data
    877             results[i] = results[i].copy(deep=False)

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/pandas/core/apply.py:138, in Apply.__init__.<locals>.f(x)
    137 def f(x):
--> 138     return func(x, *args, **kwargs)

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/ema_workbench/analysis/prim_util.py:100, in calculate_qp(data, x, y, Hbox, Tbox, box_lim, initial_boxlim)
     98     temp_box = box_lim.copy()
     99     temp_box.at[direction, u] = unlimit
--> 100     qp = sdutil._calculate_quasip(x, y, temp_box, Hbox, Tbox)
    101 else:
    102     qp = -1

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/ema_workbench/analysis/scenario_discovery_util.py:310, in _calculate_quasip(x, y, box, Hbox, Tbox)
    307 Tbox = int(Tbox)
    309 # force one sided
--> 310 qp = sp.stats.binomtest(Hbox, Tbox, p, alternative="greater")  # @UndefinedVariable
    312 return qp.pvalue

File ~/Documents/00_Uni/Bachelorarbeit/ImprovingSubgroupDiscovery/venv/lib/python3.9/site-packages/scipy/stats/_binomtest.py:290, in binomtest(k, n, p, alternative)
    288 n = _validate_int(n, 'n', minimum=1)
    289 if k > n:
--> 290     raise ValueError('k must not be greater than n.')
    292 if not (0 <= p <= 1):
    293     raise ValueError("p must be in range [0,1]")

`

[EwoutH]

Thanks for reaching out!

The ValueError: k must not be greater than n suggests that there's an issue with the binomial test, specifically in the _calculate_quasip method within the PrimBox class.

This error occurs when the number of successes k in the binomial test (sp.stats.binomtest) is greater than the number of trials n. In the context of PRIM, this could happen if the box being evaluated ends up with a configuration where the number of cases of interest (Hbox) inside the box is somehow greater than the total number of cases (Tbox) in that box.

It could have something to do with the way in which you are running the Prim algorithm repeatedly. Could you give us a minimal reproducible example? Please include both the code and data of this minimal reproducible example and upload it as a ZIP to this discussion.

[EwoutH]

Have you tried running with more dimensions?

Did we change things between 2.4.1 and the current master branch?

[EwoutH]

After looking in to it a bit more, it seems that spicy.stats.binom_test, which is currently being used by the workbench is being deprecated and is being replaced with spicy.stats.binomtest.

We already migrated to the new binomtest with #227, which was part of the EMAworkbench 2.4.0 release.

[quaquel]

my bad, I thought I was using master, but it referred to an old install in site packages.

I can now confirm the error and as expected k = n+1, so it seems to be a rounding error in how n and k are estimated rather than determined exactly. This is clearly a bug and needs to be fixed, probably by storing n and k explicitly next to storing coverage and density.

[EwoutH]

Nice job!

Do you think it’s a regression/modification from the old binom_test to the new binomtest behaviour? If so, we should probably report it to SciPy.

I updated the error messages in SciPy to actually provide the values of k and n (see scipy/scipy#19540).

[quaquel]

no, I managed to replicate it also with the old version so it is a workbench thing. It is just a really weird corner case due to floating point math.