Repository: optuna/optuna
Pull request: Handle `single` distributions in `fANOVA` evaluator
<!-- Thank you for creating a pull request! In general, we merge your pull requests after they get two or more approvals. -->

## Motivation
<!-- Describe your motivation why you will submit this PR. This is useful for reviewers to understand the context of PR. -->
This PR fixes #2542 by making `FanovaImportanceEvaluator` correctly handle param distributions with equal lower and upper bounds. This is an alternative implementation, as discussed in #3074 (thanks @hvy!).

## Description of the changes
<!-- Describe the changes in this PR. -->
* Handle `single` distributions in `FanovaImportanceEvaluator.evaluate`
* Write tests

Problem statement:
`ZeroDivisionError` when plotting parameter importance
Plotting parameter importance of a multi-objective study causes a `ZeroDivisionError: Weights sum to zero, can't be normalized.` The error happens with a with two-objective study, which otherwise runs nicely and produces a Pareto plot without any problem.

## Expected behavior

Generate a plot of parameter importance based on a multi-objective study, as described in the documentation.

## Environment

- Optuna version: 2.6.0
- Python version: 3.8
- OS: Ubuntu 18.04

## Error messages, stack traces, or logs

```
ERROR Traceback (most recent call last):
  File "/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/visualization/_param_importances.py", line 126, in plot_param_importances
    importances = optuna.importance.get_param_importances(
  File "/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/__init__.py", line 91, in get_param_importances
    return evaluator.evaluate(study, params=params, target=target)
  File "/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/_fanova/_evaluator.py", line 121, in evaluate
    evaluator.fit(
  File "/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/_fanova/_fanova.py", line 74, in fit
    self._trees = [_FanovaTree(e.tree_, search_spaces) for e in self._forest.estimators_]
  File "/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/_fanova/_fanova.py", line 74, in <listcomp>
    self._trees = [_FanovaTree(e.tree_, search_spaces) for e in self._forest.estimators_]
  File "/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/_fanova/_tree.py", line 23, in __init__
    statistics = self._precompute_statistics()
  File "/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/_fanova/_tree.py", line 185, in _precompute_statistics
    value = numpy.average(child_values, weights=child_weights)
  File "<__array_function__ internals>", line 5, in average
  File "/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/numpy/lib/function_base.py", line 409, in average
    raise ZeroDivisionError(
ZeroDivisionError: Weights sum to zero, can't be normalized

---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-10-380c9d9887b3> in <module>
/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/... in create_param_importance_plot(self)
    168 
    169     def create_param_importance_plot(self):
--> 170         param_importance_fig = optuna.visualization.plot_param_importances(
    171             self.study, target_name=Q_METRIC_NAME, target=lambda t: t.values[0]
    172         )

/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/visualization/_param_importances.py in plot_param_importances(study, evaluator, params, target, target_name)
    124         return go.Figure(data=[], layout=layout)
    125 
--> 126     importances = optuna.importance.get_param_importances(
    127         study, evaluator=evaluator, params=params, target=target
    128     )

/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/__init__.py in get_param_importances(study, evaluator, params, target)
     89         raise TypeError("Evaluator must be a subclass of BaseImportanceEvaluator.")
     90 
---> 91     return evaluator.evaluate(study, params=params, target=target)

/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/_fanova/_evaluator.py in evaluate(self, study, params, target)
    119 
    120         evaluator = self._evaluator
--> 121         evaluator.fit(
    122             X=trans_params,
    123             y=trans_values,

/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/_fanova/_fanova.py in fit(self, X, y, search_spaces, column_to_encoded_columns)
     72         self._forest.fit(X, y)
     73 
---> 74         self._trees = [_FanovaTree(e.tree_, search_spaces) for e in self._forest.estimators_]
     75         self._column_to_encoded_columns = column_to_encoded_columns
     76         self._variances = {}

/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/_fanova/_fanova.py in <listcomp>(.0)
     72         self._forest.fit(X, y)
     73 
---> 74         self._trees = [_FanovaTree(e.tree_, search_spaces) for e in self._forest.estimators_]
     75         self._column_to_encoded_columns = column_to_encoded_columns
     76         self._variances = {}

/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/_fanova/_tree.py in __init__(self, tree, search_spaces)
     21         self._search_spaces = search_spaces
     22 
---> 23         statistics = self._precompute_statistics()
     24         split_midpoints, split_sizes = self._precompute_split_midpoints_and_sizes()
     25         subtree_active_features = self._precompute_subtree_active_features()

/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/optuna/importance/_fanova/_tree.py in _precompute_statistics(self)
    183                     child_values.append(statistics[child_node_index, 0])
    184                     child_weights.append(statistics[child_node_index, 1])
--> 185                 value = numpy.average(child_values, weights=child_weights)
    186                 weight = numpy.sum(child_weights)
    187                 statistics[node_index] = [value, weight]

<__array_function__ internals> in average(*args, **kwargs)

/opt/mt/anaconda3/envs/develop/lib/python3.8/site-packages/numpy/lib/function_base.py in average(a, axis, weights, returned)
    407         scl = wgt.sum(axis=axis, dtype=result_dtype)
    408         if np.any(scl == 0.0):
--> 409             raise ZeroDivisionError(
    410                 "Weights sum to zero, can't be normalized")
    411 

ZeroDivisionError: Weights sum to zero, can't be normalized
```

## Steps to reproduce

1. Configure and run a default study with two objectives (maximize, maximize), the main function returning the result of a rounded float for one objective and an integer division for the second objective.
2. Generate a parameter importance plot with:
```python
fig = optuna.visualization.plot_param_importances(study, target_name=METRIC_NAME, target=lambda t: t.values[0]) 
```

## Additional context (optional)

Apart from the param importances not being generated, the study runs smoothly and I can generate a Pareto front plot without any problem.

Hints from issue discussion:
@dmar1n Could you share the reproducible code? I could not reproduce the bug.
Thanks for looking at it, @nzw0301. I eventually found the cause for this error. I was generating a trial parameter with a range of integer values of length 1, like so:

`trial.suggest_int(x, (1024, 1024, 128))`

The issue is fixed with a range longer than one value (e.g. `(512, 1024, 128)`).

Even if the configuration I was using didn't make sense, it was still correct, as low and high values are both included in the range according to the doc. Maybe it would be good to add a check/warning for this case? Otherwise, this issue can be closed.
Hi, @dmar1n! thank you for your explanation and your suggestion! Your suggestion seems to make sense. I'll dig into this issue.

Let me put a reproducible code for a simpler case -- single objective.

```python
import optuna


def objective(trial):
    x = trial.suggest_float("x", 0, 5)
    y = trial.suggest_float("y", 1, 1)

    v0 = 4 * x ** 2 + 4 * y ** 2
    
    return v0


study = optuna.create_study()
study.optimize(objective, n_trials=10)
fig = optuna.visualization.plot_param_importances(study)
```

I locally confirmed that the Matplotlib backend has the same issue.
This issue has not seen any recent activity.

Commit message: Add comment on empty search spaces edge case

Patch to review:
diff --git a/optuna/importance/_fanova/_evaluator.py b/optuna/importance/_fanova/_evaluator.py
index 569088e2648..5d1b5d79943 100644
--- a/optuna/importance/_fanova/_evaluator.py
+++ b/optuna/importance/_fanova/_evaluator.py
@@ -88,6 +88,12 @@ def evaluate(
         if len(distributions) == 0:
             return OrderedDict()
 
+        # fANOVA does not support parameter distributions with a single value.
+        # However, there is no reason to calculate parameter importance in such case anyway,
+        # since it will always be 0 as the parameter is constant in the objective function.
+        zero_importances = {name: 0.0 for name, dist in distributions.items() if dist.single()}
+        distributions = {name: dist for name, dist in distributions.items() if not dist.single()}
+
         trials = []
         for trial in study.trials:
             if trial.state != TrialState.COMPLETE:
@@ -131,6 +137,7 @@ def evaluate(
             importance, _ = evaluator.get_importance((i,))
             importances[name] = importance
 
+        importances = {**importances, **zero_importances}
         total_importance = sum(importances.values())
         for name in importances:
             importances[name] /= total_importance
diff --git a/tests/importance_tests/test_fanova.py b/tests/importance_tests/test_fanova.py
index 02ef009ff72..eda76c416c3 100644
--- a/tests/importance_tests/test_fanova.py
+++ b/tests/importance_tests/test_fanova.py
@@ -71,3 +71,19 @@ def test_fanova_importance_evaluator_with_target() -> None:
     )
 
     assert param_importance != param_importance_with_target
+
+
+def test_fanova_importance_evaluator_single_distribution() -> None:
+    def _objective(trial: Trial) -> float:
+        x = trial.suggest_float("x", 0, 5)
+        y = trial.suggest_float("y", 1, 1)
+        v0 = 4 * x ** 2 + 4 * y ** 2
+        return v0
+
+    study = create_study()
+    study.optimize(_objective, n_trials=3)
+
+    evaluator = FanovaImportanceEvaluator()
+    importances = evaluator.evaluate(study)
+
+    assert importances["y"] == 0.0


Code review comments:
diff_hunk: @@ -71,3 +71,19 @@ def test_fanova_importance_evaluator_with_target() -> None:
     )
 
     assert param_importance != param_importance_with_target
+
+
+def test_fanova_importance_evaluator_single_distribution() -> None:
+    def _objective(trial: Trial) -> float:
+        x = trial.suggest_float("x", 0, 5)
+        y = trial.suggest_float("y", 1, 1)
+        v0 = 4 * x ** 2 + 4 * y ** 2
+        return v0
+
+    study = create_study()
+    study.optimize(_objective, n_trials=3)
+
+    evaluator = FanovaImportanceEvaluator()
+    importances = evaluator.evaluate(study)
+
+    assert importances["y"] == 0.0
path: tests/importance_tests/test_fanova.py
text: @user1:
Leaving this test might be fine but do you think it's better suited in https://github.com/optuna/optuna/blob/master/tests/importance_tests/test_init.py ? That is, in the general importance tests, not just fANOVA (although the change is limited to this evaluator).

@author:
I was thinking about it, but concluded that such test would require to also check the behavior of `MeanDecreaseImpurityImportanceEvaluator`, which i think is out of scope here. How about i tackle this in follow-up? If it works I'll just add parametrized tests as you suggested, and if not I'll also fix the other evaluator.

@user1:
That sounds like a much better approach. Let me approve this PR as I think it looks good in that case. 👍 
(I think you can start checking the `MeanDecreaseImpurityImportanceEvaluator` while waiting for a second review, if you like of course)

@author:
> I think you can start checking the MeanDecreaseImpurityImportanceEvaluator while waiting for a second review, if you like of course

I will. Do you think we should remove above test when it's moved to `test_init.py`?

@user1:
I'm fine either way.

The test you added is obviously reasonable since it's testing the behavior of public API, but at the same time, we've left most of the general behavioral checks to `test_init.py`, given that `get_param_importances` is basically just calling `BaseImportanceEvaluator.evaluate`. With that said, for consistency and simplicity (don't "overdo" tests that don't contribute to the code coverage), I slightly lean towards removing.