Computing Values with Regression-based estimators is inefficient.

[mmschlk]

The computation with regression-based estimators is quite slow at the moment. There are multiple inefficiencies in the regression routine which should be optimized:

The following graph shows the computation of 2-SII scores with KernelSHAP-IQ for 1_000_000 sampled coalitions for an image classifier model with around 60 features: The time it takes to query the model is considerably faster than the computation which happens afterwards.

Potential Bottlenecks:

This:

        for coalition_pos, coalition in enumerate(coalitions_matrix):
            for interaction_pos, interaction in enumerate(
                powerset(self._grand_coalition_set, max_size=self.max_order)
            ):
                interaction_size = len(interaction)
                intersection_size = np.sum(coalition[list(interaction)])
                regression_matrix[coalition_pos, interaction_pos] = regression_coefficient_weight[
                    interaction_size, intersection_size
                ]

The Try-Except: (which is linked to #338)

        try:
            # try solving via solve function
            shapley_interactions_values = np.linalg.solve(
                regression_matrix.T @ weighted_regression_matrix,
                weighted_regression_matrix.T @ regression_response,
            )
        except np.linalg.LinAlgError:
            # solve WLSQ via lstsq function and throw warning
            regression_weights_sqrt_matrix = np.diag(np.sqrt(regression_weights))
            regression_lhs = np.dot(regression_weights_sqrt_matrix, regression_matrix)
            regression_rhs = np.dot(regression_weights_sqrt_matrix, regression_response)
            warnings.warn(
                UserWarning(
                    "Linear regression equation is singular, a least squares solutions is used "
                    "instead.\n"
                )
            )
            shapley_interactions_values = np.linalg.lstsq(
                regression_lhs, regression_rhs, rcond=None
            )[0]

[mmschlk]

Added:

1. A nicer vectorized creation of the regression matrix to replace the unholy for loop over the powerset 🫶

2. availability to use sklearn's lasso optimizer for the matrix like in shap. (Dunno about defaulting to this though)

[mmschlk]

The vectorized creation of the regression matrix is cool:

However, sklearn.linear_model.LassoLarsIC(criterion="aic") wants 7TB of memory which I don't have. 😔

[mmschlk]

Aaaah, okay @FFmgll and @hbaniecki found the problem with the exploding memory. We basically use the worst kind of operation to create the matrices. This should now be a very quick fix. I will do some more testing and finish this.