Towards Robustness and Explainability of Automatic Algorithm Selection

Weakness 1 / Q3

Thanks for your insightful comments. In practical scenarios, informative algorithm features are not always readily available, just as pointed out by Reviewer nswt. In this study, we recognize that the availability of algorithm features has a vital impact on the model's performance. Therefore, we will add an assumption and discussion about the informativeness of algorithm features in Section 2:

Assumption 3: Informative algorithm features are available for the algorithm selection task.

In the context of algorithm selection, the availability of informative algorithm features is a crucial yet often overlooked aspect. This assumption implies that we can obtain algorithm-related characteristics that carry meaningful information for differentiating the performance of different algorithms on various problem instances. This assumption serves as a fundamental basis for DAG-AS. Currently, there are several established algorithm representation methods, such as hyperparameters, model structure information, code-related statistical features, AST features, and code features extracted by LLMs. These features provided valuable insights into the algorithms' properties and significantly contributed to the performance of DAG-AS. However, we are also aware that in some cases, obtaining such informative features can be challenging. For example, code-related features cannot be obtained in the closed-source scenario.

Weakness 2

We sincerely appreciate your valuable suggestions. Intervening on algorithm features indeed holds the potential to achieve broader goals beyond the algorithm selection task itself. In real-world scenarios, the most suitable algorithm may not always be present in the candidate set, or may not even have been designed yet. By examining $P(S=1 \mid **PF**,do(**AF**=**a**+\delta_{**AF**}))$, we can explore how to adjust the optimal algorithms within the candidate set based on $\delta_{**AF**}$ for a given problem. This intervention can assist us in two ways:

1. It helps in searching for more suitable algorithms within or beyond the existing candidate set;
2. It generates valuable suggestions to aid in the automated algorithm design.

However, in the context of ASlib, due to the high level of abstraction of the algorithm features and the fact that many candidate algorithms are closed-source, we are unable to optimize these candidate algorithms according to the results of algorithm feature interventions. As a result, empirical study in this aspect is currently not feasible. In the future, such research could potentially be carried out in scenarios where the physical meaning of features is more explicit. For example, in the selection of deep-learning models, the hyperparameters and architecture features of the models can be used as algorithm features. Interventions on these features can help users to further improve existing models or generate new ones based on the candidate algorithm set.

Regarding the generation of new algorithms, we already have some well-developed ideas. Specifically, by combining the DAG learned by DAG-AS and the results of algorithm feature interventions, we can generate suggestions for improving candidate algorithms. These suggestions, along with the code of the candidate algorithms, can then be submitted to a LLM. Leveraging the code-related ability of the LLM, we can achieve the automated optimization and design of algorithms. We will incorporate the discussion into the final version to further enhance the depth of our research.

Q1

The goal of classic SHAP analysis is to explain the prediction results of a model by calculating the contribution of each feature to the prediction. It focuses on quantifying the impact of individual features on the output within the model's framework. In contrast, our paper aims to achieve multi-level explainability in algorithm selection. It not only considers the influence of features on the selection result but also delves into the causal relations between problem features and algorithm features, as well as the overall causal structure. This helps users understand not only which features are important but also how they interact and influence the algorithm selection process in a causal sense.

Q2

We appreciate your astute observation. We indeed introduced additional constraints to simplify the search process for determining the appropriate perturbation range and step size in instance-level explanations. As detailed in our last response to the Reviewer BWG1, we have proposed some methods to assist in solving the optimization problem. Due to space limitations, we cannot elaborate on these here. Moreover, it is unnecessary to adjust Eq.15 since this equation represents the original form of the optimization problem.

Q4

The construction of the directed cyclic graph still based on the two assumptions. As for performance degradation on SAT03-16-INDU, please read the 5th response to Reviewer nswt.

Experiments: Missing SOTA approaches. None of the baselines use algorithm features.

Thanks for your valuable suggestions. We acknowledge that our experiments lacked some SOTA comparison methods. In response, we have now incorporated ASAP and AutoFolio into our experiments.

Regarding the absence of methods based on algorithm features in our original study, there are two main reasons: 1) these methods mainly differ in feature types rather than model design, and 2) in some scenarios of ASlib, it was difficult to obtain the source code, which made it challenging to extract algorithm features, such as features derived from code or hyperparameters.

According to your suggestion, we selected the method proposed by Pulatov et al and AS-LLM as additional comparison baselines. Due to space constraints, we have plotted the experimental results in a figure and presented them at the anonymous link https://imgur.com/a/QmDoUeA. It should be noted that AS-LLM can only be evaluated in scenarios where the source code is available. From the experimental results, it can be clearly seen that DAG-AS still maintains the best performance in most scenarios.

Whether counterfactual interpretations depends on the DAG-AS

Counterfactual interpretations are indeed closely related to DAG-AS. As described in Page 7, the three steps of counterfactual calculation all rely on the causal model learned by DAG-AS:

1. Abduction step needs to use the structural equations in DAG-AS to infer the exogenous variables;
2. Intervention step uses do-operator to modify the causal graph learned by DAG-AS.
3. Prediction step calculates the results based on the modified causal graph.

In summary, while counterfactual interpretations can be conceptually applied in other settings, in our work, the DAG-AS framework provides the necessary foundation for a systematic and accurate implementation of counterfactual analysis in algorithm selection.

Which modeling assumptions are specific to algorithm selection and which ones are quite established modeling approaches for causal learning.

The two assumptions in the paper are both proposed based on the characteristics of the algorithm selection task, mainly to simplify the complexity of the causal graph. There are some assumptions in causal learning itself, such as causal sufficiency, which are not included in this paper.

Someone not being fully familiar with causal learning notation is lost in the main paper.

We sincerely apologize for any confusion caused to readers. We will make adjustments and add a notation tabel into the final version.

When DAG-AS fails and when not

We think that DAG-AS may not perform well under 3 cases:

1. When the features themselves lack informativeness or when the correlation between problem features and algorithm features is extremely weak.
2. When the data violates the causal sufficiency assumption. This means that there are confounding factors that are not included in the feature set.
3. When the causal relationships within the dataset are overly complex.

However, it should be noted that cases 2 and 3 can potentially be addressed by improving DAG-AS. In the causal learning field, there are numerous specialized models designed to handle complex causal relations, such as those dealing with multivariable or nonlinear causality. Additionally, there are studies focused on identifying causality in scenarios where the causal sufficiency assumption is violated. To enhance the performance of DAG-AS, more advanced causal learning models can be adopted to replace the Eq(8,9).

I’m least convinced by the interpretation advantage of DAG-AS.

We sincerely appreciate your criticism. We acknowledge that the interpretability aspect in the context of ASlib may not be as immediately intuitive. The reason is that the algorithm features used in ASlib are AST features, which are highly abstract in terms of their physical meaning. However, the interpretability can be extremely valuable in scenarios where the physical meaning of features is explicit. For example, when considering the architecture features or hyperparameters of deep-learning models as algorithm features. In such cases, if the causal graph reveals which problem features influence the number of neurons in specific layers, this interpretability can significantly assist users in understanding the model design. It also provides great utility for experts when debugging the DAG-AS model.

Due to space limitations, the following issues are addressed in the response of other Reviewers:

Paragraph discussing the assumption on the availability of informative algorithm features.

Please refer to the 1st response of Reviewer oy94 (Weakness1)

More discussion on the intervention of algorithm features

Please refer to the 2rd response of Reviewer oy94 (Weakness2)

Weights for loss function

Please refer to the 2rd response of Reviewer BWG1 (Weakness2)

Weakness 1

Thanks for your valuable comments. It's right that "for a defined problem characteristic, the optimal algorithm should also be defined", which implies that $P(AF|PF)$ remains constant. In Appendix E.4, our intention was not to change $P(AF|PF)$, but rather to manipulate the marginal distributions $P(AF)$ and $P(PF)$. The “Shift on Optimal Algorithm Distribution” was achieved through a deliberate selection process of the training and test data. Specifically, any candidate algorithm can be the optimal ones for a certain proportion of problems. We manipulate this proportion to induce a distribution shift of the optimal algorithm. For example, in the training data, algorithms A and B are the best-performing ones for 20% and 80% of the problems respectively, while in the test data, these proportions are reversed, with A being optimal for 80% and B for 20% of the problems. We construct the training and test sets by selecting problem instances from the original dataset according to these proportions. Since $P(AF|PF)$ is fixed in algorithm selection, any adjustment to either $P(AF)$ or $P(PF)$ will lead to a corresponding change in the other. Therefore, during the implementation of the “Shift on Optimal Algorithm Distribution”, the distribution of problem features also changed accordingly.

Weakness 2

Thanks for your reminder. We have used hyperparameters to balance the impacts of various losses. As stated on line 278, “The overall loss function is the weighted average of the causal learning loss and algorithm selection loss.” However, we apologize for the misunderstanding caused by not presenting the final form of loss function. In the final version, we will provide the complete loss function with hyperparameters: $L = L_{\text{reconstruction}} + \alpha L_{\text{sparsity}} + \beta L_{\text{acyclicity}}+ \gamma L_{\text{selection}}$. Current experimental results were obtained under the same parameter settings, where $\beta=\gamma=1$ and $\alpha=0.0001$. Based on your suggestion, we conducted a hyperparameter analysis on SAT11-INDU. The results can be found at the anonymous link: https://imgur.com/a/b8C9l5G. In left figure, we analyzed the balance between reconstruction loss and two causal learning constraints (analyzing $\alpha$ and $\beta$), while keeping $\gamma=1$. In right figure, we analyzed the balance between the causal learning loss and the algorithm selection loss (analyzing $\gamma$), while keeping $\beta=1,\alpha=0.0001$. It can be seen that DAG-AS can maintain relatively good performance within a wide range of parameters. In the final version, we will supplement more detailed hyperparameter analysis.

Other Comments & Suggestions

We sincerely appreciate your suggestions. We'll incorporate more details into the final version to highlight the significance of this area, including its practical applications in machine learning, scientific computing, and engineering optimization, as well as its superiority in enabling efficient decision-making, especially in real-time applications. In terms of CausPref, it is a typical study in which causal learning enhances robustness. The strategies of CausPref in causal preference modeling and negative sampling are worth learning. We will cite this paper in the final version and discuss the inspiration for our study.

Q1

We apologize for the ambiguity in this part. Our intention was not to illustrate “The advantages of modelling causality over correlation” through Eq(2). Rather, we aimed to express the connection between the two modelling approaches, i.e., $P(S=1|PF,AF)$ and $P(AF|PF,S=1)$ are equivalent in terms of modelling in the algorithm selection task. However, $P(AF|PF,S=1)$ directly models the conditional distribution, which enables it to be more resilient against the marginal distribution shifts. After these discussions, we propose using a causal DAG to model $P(AF|PF,S=1)$.

Q2

First, we would like to clarify that the process does not necessarily require iterating through all PFs. This mainly depends on the DAG learned by DAG-AS. We only need to intervene on all the parent nodes of the algorithm features. Therefore, the DAG has already reduced the dimensionality for counterfactual calculations.

However, even with this reduction, a large number of problem features may still be involved in the counterfactual calculations, so improving the efficiency of this process is essential. One potential approach is to model the interpretability calculations as a reinforcement learning system, where the action space would include the features of intervention and their magnitudes, and the reward space would be defined by the changes in the algorithm selection decision. We could take several interventions as samples to train separate Action and Reward networks. This approach may require an independent research paper for in-depth discussion. Therefore, we plan to present this future work in the final version.

The paper's performance on GLUHACK-18 and SAT03-16-INDU, is not as strong as on others, indicating potential limitations ...

We acknowledge that DAG-AS did not perform well on GLUHACK-18 and SAT03-16-INDU. However, it is unjustified to undermine the significance of DAG-AS merely based on its performance on these 2 datasets. Specifically,

1. It is challenging for any single method to achieve optimal performance across all problems. In this paper, we conducted comprehensive evaluation on 10 datasets. The results demonstrate that DAG-AS outperformed all the comparison methods on 8 of these data. Notably, on half of them, DAG-AS significantly outperformed other methods, which illustrates the distinct advantages of DAG-AS.
2. Regarding the DAG-AS's performance on GLUHACK-18 and SAT03-16-INDU, it may be due to the data violating the causal sufficiency assumption or the overly complex causal relations within the data. Nevertheless, these issues are not insurmountable in the causal learning field. There are numerous models specifically designed for complex causality in the causal learning domain, such as models for handling multivariate/non-linear causality, and models for scenarios where the causal sufficiency assumption is violated. The causal learning module of DAG-AS is a relatively simple MLP, mainly to highlight the impact of introducing causality into algorithm selection (AS). If further performance improvement is desired, more advanced causal learning models can be employed to replace Eq(8,9).

Computational complexity of DAG-AS

There is no significant difference in computational complexity between DAG-AS and existing methods. Compared to traditional methods, DAG-AS needs to construct a causal DAG and reconstruct algorithm features, while traditional methods often directly predict the optimal algorithm. However, due to the sparsity of the DAG, the reconstruction model for each algorithm feature is actually small-scale. We have provided the running times comparison at the anonymous link: https://imgur.com/a/1w6eLIQ. It can be seen that the running time of DAG-AS is comparable to existing methods. Despite this, DAG-AS achieves remarkable performance gains, indicating its practicability.

Can DAG-AS be applied to other domains or types of problems beyond those included in the ASlib benchmark?

DAG-AS is designed to be applicable to a wide range of AS scenarios, far beyond the scenarios in the ASlib benchmark. The key requirement for applying DAG-AS is the availability of the general configuration for the AS task, including problem features, algorithm features, and performance data. As long as these elements are provided, DAG-AS can be effectively utilized. Actually, the ASlib itself is also composed of problems from diverse domains.

How does the choice of problem and algorithm features impact the performance and explainability of DAG-AS?

Performance Impact: Different features carry distinct information about the nature of the problem and algorithm. In datasets with a rich set of features that are informative and highly relevant to the algorithm's performance, DAG-AS can better capture the causal relationships. This is similar for other AS methods. Traditional algorithms aim for these features to be correlated with the algorithm's performance, while DAG-AS expects there to be causal relationships behind such correlations.

Explainability Impact: When it comes to the impact on explainability, the nature of features matters depending on the user's goals. If users want to understand the decision-making logic of DAG-AS and interpret the causal relationships between features in the DAG, these features should have physical meaning, rather than being representations extracted by deep networks. However, if the sole expectation is for DAG-AS to make AS decisions, features without clear physical meaning can also be perfectly suitable. For example, since ASlib did not provide algorithm features for the BNSL-2016, we used a LLM to extract representations from the code of candidate algorithms. Despite the lack of obvious physical meaning in these features, DAG-AS still achieved the best performance.

Are there any specific types of distribution shifts or problem characteristics where DAG-AS may not perform well?

The causal learning module in DAG-AS is essentially built on modeling conditional probabilities. Hence, it can mitigate the impact of covariate shift and prior probability shift. It has been verified in Fig.6 that DAG-AS can handle distribution shifts on problem features and optimal algorithm distributions well. However, DAG-AS may face challenges in dealing with shifts in $P(AF|PF)$. But in AS, $P(AF|PF)$ implies what characteristics an algorithm needs to solve a problem with specific feature values, which does not shift in a given AS task. As for problem characteristics, DAG-AS has no specific requirements regarding the problem domain, as mentioned in previous responses.