Learning from Uncertain Data: From Possible Worlds to Possible Models

We thank the reviewer for their thoughtful review. Due to space limitations, we have summarized each question and numbered them from Q1 to Q9.

Q1. Are possible models more important than possible predictions?

We did not mean to argue that understanding possible models is more important than understanding possible predictions. We wanted to convey that our approach and adversarial robustness differ in which sources of uncertainty they support: uncertain test data in the case of adversarial robustness and uncertain training (and optionally also test) data for our approach. In our setting, we have to reason about possible models even if we are only interested in possible predictions as the uncertainty in the training data leads to model uncertainty which in turn also affects prediction uncertainty. We will rephrase this paragraph to make this distinction more clear. There are applications, like the causal inference use case we cover in the experiments, where the outcome of interest are the parameters of the model.

Q2. (line 24) why not use structurally simple models?

While selecting models with structural simplicity can be effective under certain assumptions—specifically where a model exists that performs near optimal across all possible worlds—it is not applicable in situations where data quality issues result in significant variability across the possible worlds. In such cases, this approach may yield a highly suboptimal model. However, the primary application of our approach is to evaluate or certify robustness for a given learning procedure based on worst-case analysis with prediction intervals which is crucial in high-stakes decision-making where the ground truth is not recoverable.

Q3. Sec 2.1 where do sets of datasets come from?

We take an erroneous dataset as input, which might have missing values, detected outliers, or other data quality issues or sources of uncertainty. When these errors appear not at random, the ground truth values are typically not identifiable. Therefore, we consider a range of all possible clean data values in place of erroneous values. As mentioned in Appendix D, the ranges could be obtained from background knowledge, or reliable imputation techniques. To the best of our knowledge, there is no direct application of the Bayesian approach that derives the full distribution of models for capturing uncertainty due to general data multiplicity. We will clarify in the paper that our approach does not introduce any data quality issues, but rather enables modeling of data quality issues and evaluating their impact on model and prediction uncertainty. Regarding the difference with Bayesian approaches, please see Q7.

Q4. App. D missing definition of ε. Use maximum entropy distribution for missing data?

In Appendix D, $\epsilon$ refers to the uncertainty range radius. For instance, a temperature sensor may be accurate within 2 degrees. When encoding uncertainty, we do not make any assumptions about the distribution within the ranges. This allows for worst-case analysis even if probabilities are unknown. Intuitively, our over-approximation guarantees on prediction ranges and model parameters hold independent of how values are distributed within a range. We will add clarifications.

Q5. Terminology: prediction set, or "efficiency ratio" vs."robustness ratio"?

We agree that showing the distribution of prediction ranges will provide more fine-grained information. We will add additional plots to show distributions of prediction interval sizes. Regarding the nomenclature, while prediction set / efficiency is the common terminology used in conformal prediction (CP), robustness has been used in more closely related work [a]. We will add clarifications to relate our terminology to CP. Please also see our response to Q7.

[a] Meyer et al. Certifying robustness to programmable data bias in decision trees. NeurIPS 2021

Q6. How are the robustness thresholds chosen?

Please see our response in the main rebuttal section.

Q7. Experimental comparison with uncertainty quantification?

While many uncertainty quantification techniques output prediction intervals including Bayesian neural networks and conformal prediction (CP), we did not compare against these techniques as they are either not applicable to our setting (e.g., because their assumptions are violated or they are designed for a different type of uncertainty) and / or they provide only probabilistic guarantees, underestimating the true prediction ranges. For instance, CP’s assumption of exchangeability is violated when data errors are non-random and CP only guarantees that the ground truth label is within the prediction set in expectation and provides no guarantees for individual datapoints. Contrast this with our guarantees: we cover the prediction made by a model trained on the unknown ground truth training dataset with 100% probability. To also confirm this experimentally, we did evaluate prediction intervals produced by BNNs. We provide a detailed discussion in the general rebuttal.

Q8. For Figure 3: How were errors injected? How was multidimensional data generated?

In Figure 3, we uniformly at random picked a set of 8 data points to inject errors by running several missing value imputation techniques to generate 4 possible options for each of the 8 uncertain values, which is small enough such that we could enumerate all possible worlds and calculate the ground truth prediction ranges. In Figure 3(a), we varied the uncertainty radius by creating ranges directly that over-approximate the possible worlds (4 possible imputed values). In Figure 3(b), we appended additional random columns with normal distributions to the original data, and used different imputation techniques to derive the uncertainty radiuses, i.e., ranges.

Q9. An extension of the proposed approach beyond linear models seems difficult

Please see our response in the main rebuttal.

We thank the reviewer for engaging with our work and for the constructive feedback. Your suggestions and the references you provided are highly appreciated, and we have taken them into careful consideration. We also would like to mention that we did not mean to imply that techniques like [1-3] cannot be used in high stakes decision making. We meant to convey that in our use case, their assumptions are often violated and then their guarantees will fail to hold.

Experiments

In the additional experiments, we trained Bayesian regression models with the ELBO loss under two settings. In the first setting (Table 1), we used imputation and worked with the best guess possible world. In the second setting (Table 2), we sampled from the possible worlds and processed each sample independently. We did not create an ensemble of Bayesian regression models as each possible dataset was treated separately. For each trained Bayesian regression model, we sampled from the parameter distribution 1000 times and obtained 1000 possible models, each of which produced a possible prediction. We then combined the 1000 possible predictions to obtain prediction upper and lower bounds, i.e., prediction intervals. Please let us know if you have any further questions about these experiments.

Comparison with related work [1-3]

Similar to our approach, both [1] and [2] construct sets of models based on Likelihood Ratio methods, with [1] and [2] considering a sequential process that is not the focus of our work. While these approaches provide probabilistic guarantees, which could be acceptable in high-stakes scenarios where the probability of failure is minimal (e.g., 0.01%), our approach provides exact guarantees. However, a more critical difference lies in the types of uncertainty they can model. In [1], the confidence set $\mathcal{C}_t$ are derived under the assumption that the noise follows an exponential family distribution, allowing for efficient computation. However, in our scenario, the uncertainty arises from arbitrary data quality issues, e.g., missing data, which goes beyond uncertainty in the label to uncertainty in both labels and covariates, and cannot typically be modeled using a similar approach that warrants efficient computation. As a result, the shape of the confidence sets cannot be determined using the techniques from [1] as it is, as their distributional assumptions do not hold in our context.

Regarding the Confidence Ellipsoid approach in [3], the creation of confidence sets using Theorem 2 (Confidence Ellipsoid) depends on the covariance matrix derived from the data. However, in our setting, the uncertainty stems from arbitrary data quality issues, where we have a set of possible worlds, each potentially having its own distinct covariance matrix structure. For instance, this is particularly evident in scenarios involving missing data. As a result, applying these methods directly does not provide the exact guarantees we seek. There are two primary ways to handle this: one approach is to sample from the possible datasets or average over them, as we did in our experimental evaluation for Bayesian regression, or to clean the data and work with the best guess. However, both of these approaches do not provide any coverage guarantees, especially when the data quality issues are non-random, and the ground truth data/distribution is not recoverable—which is exactly the type of uncertainty we aim to address.

We will ensure that all these related works are properly cited in the final paper and that additional experiments are conducted to compare our approach with these methods. However, as discussed, similar to the Bayesian approach, these methods may fail to provide the theoretical guarantees required in our context, e.g., as their assumptions (including distributional) will not hold. Nonetheless, it would be interesting to explore combining these approaches with the methodology proposed in our paper to expand them to handle possible worlds through over-approximation. We will consider this as future work, and we thank the reviewer for their valuable suggestion.

If you have any specific ideas on how these methods could be effectively applied in our setting that we might have overlooked, or if any clarifications would help improve your evaluation, please let us know. Rest assured, we are committed to including all these methods in the revised paper, along with Bayesian approaches, to provide a comprehensive comparison. We truly appreciate your insightful feedback and the opportunity to refine and strengthen our work.

We thank the reviewer for their thoughtful review and suggestions. We will mention the numbers on figures on page 5 represent the iterations, and we will add a brief example of uncertain data around Definition 2.1 to make this more concrete. In response to the reviewer's other questions/comments:

1. Could you please comment on why the robustness threshold was set to different values for the two datasets?

Different practical applications may differ in how much uncertainty they are willing to tolerate. To account for this in the experiments, we wanted to test an application with a very tight threshold (0.5% for the insurance data) and a use case with a looser requirements (5% for the MPG data). We also explored other thresholds which did not impact the trends significantly: Zorro can consistently certify a larger fraction of the test datapoints than the baseline due to its use of the more expressive Zonotope domain. We have included the results of one such experiment in Figure 1 in the main rebuttal pdf document and will include them in the appendix.

2. For modeling uncertainty in features, the distribution was built around one feature. Does the choice of the feature, such as based on the correlation value between the feature and the label, affect the results

Yes, the variability of models will depend on the correlation that features with uncertainty have with the label, which then also affects our over-approximation of this set. As a rule of thumb, model variability will increase with correlation between the uncertain feature and the labels, leading in turn to less robust predictions. We conducted an additional experiment using the MPG dataset, focusing on the feature “acceleration,” which has relatively low correlation with the label. Unlike the feature “weight” (Figure 1(c) of the paper), where the robustness drops when the uncertainty radius is 10%, the robustness for “acceleration” starts to drop only when the uncertainty radius is increased to 16%. As expected, this result indicates that features with lower predictive power have less impact on the robustness of a model compared to features that are highly correlated with the label. Plese see Figure 2 in the main rebuttal pdf document that will include in the appendix. We will also convey this intuition in the main paper.

3. How much time does it take to compute the set of possible linear models for the discussed datasets?

We show the runtimes for computing the closed form solution on the MPG dataset, varying the numbers of uncertain data points, in Figure 3 in the main rebuttal pdf.

We will include these results in the appendix and add a brief discussion to the main paper. To evaluate what can be achieved by moving to a faster library for symbolic expressions, we implemented some components of the algorithm (symbolic matrix multiplication) with the generic symbolic computation C++ library GiNaC, which gives > 40x speedup on symbolic matrix multiplications. Therefore, we can anticipate a runtime of at most 0.2 seconds for 10% uncertain MPG data if we switch to an implementation using GiNaC or a custom C++ implementation.

Note that SymPy supports more general expressions than needed for our approach. It internally represents symbolic expressions as expression trees which are python objects. This is relatively inefficient for representing linear or even polynomial expressions. We plan to add runtime results using GiNaC.

Weaknesses: 1. As the authors acknowledge in the Limitation section, it is unclear how to scale the proposed approach to other, more complex hypothesis spaces or problems.

It is true that for linear models we benefit from the fact that we were able to derive a closed form solution which has the advantage of avoiding the repeated injection of an over-approximation that happens in each step of gradient descent. We are currently developing methods to (1) further improve the over-approximation quality by considering more complex abstract elements such as (constrained) polynomial zonotopes, and (2) scale our approach to gradient descent for larger models, e.g., deep neural networks, which involves parallelization, optimized data structures, etc. While challenging, we believe that it will be worthwhile to explore these future research directions.

Weaknesses: 2. Despite ZORRO being a more general approach, sampling seems to provide results closer to the ground truth even with 1k samples (Figure 7).

While sampling provides in this experiment an approximation that is closer to the ground truth, note that sampling inherently under-estimates the possible outcomes and, thus, cannot be used for high-stake decision-making applications where guaranteeing robustness is crucial for ensuring dependability and safety of models and systems. For such applications, falsely claiming robustness based on sampling is unacceptable. In Figure 7, sampling bounds are close to the ground truth ones because we have a small amount of uncertain data points (8 data points). This was necessary to ensure that we could compute the ground truth by enumerating all worlds (even with just k possible options per uncertain value, there are $n^k$ possible worlds if there are $n$ uncertain values in the training dataset). Thus, we did not conduct a corresponding experiment with more uncertainty as it is only computationally feasible to obtain the ground truth ranges for low uncertainty settings with small $n$ and $k$ . We will clarify this in the paper. In summary, (i) sampling cannot provide guarantees on covering the ground truth and (ii) in these experiments sampling did behave relatively well as we had to choose scenarios with a small number of possible worlds.

We thank the reviewer for their thoughtful review. Below are the response to reviewer's questions/comments.

Weaknesses: The techniques introduced in the paper are only applicable to linear models.

Please see our response in the main rebuttal.

Are there scenarios where the overapproximation of dataset variations and corresponding model parameter variations results in too broad outcome intervals? I would like to understand the limitations of the proposed method apart from the linearity assumption.

Over-approximation of a set of possible worlds in the training data may occur, for instance, when an uncertain value with few discrete possible values is represented through a range, leading to a superset of the actual possible worlds (all values in the range as opposed to all the discrete set of values). For instance, consider the following extreme example: there are two possible worlds in the training data where feature $A$ is $-c$ in one world for all data points while in the other world it is $c$. Using ranges leads to a large over-approximation as the ranges will contain all values between the two extremes $[-c,c]$. This leads to a large increase of the number of possible worlds which could possibly lead to a large over-approximation of prediction ranges. However, in our experiments, we did not encounter significant issues with over-approximation. The over-approximation error in our setup mostly resulted from over-approximation during learning. We will enhance the discussion on these limitations in the main paper to provide a more comprehensive understanding.

In the experimental evaluation, the dataset uncertainty is varied by changing the uncertain data percentage and uncertainty radius. Did the authors perform any experiments with missing data as the source of uncertainty? (I imagine that you could represent missing data by using a high uncertainty radius). How was the robustness threshold set for the experiments?

Correct, missing values can be modeled as ranges with a large uncertainty radius. Regarding experiments with missing data: our experiments with ground truth results are based on missing values. We randomly selected some data points to have missing values and then for each missing value determined a range by running several imputation techniques to get a set of possible values $G = \{c_1, \ldots, c_n\}$. We then use the smallest range that covers all values returned by the imputers: $[ min_{c \in G} c, max_{c \in G} c ]$. For these experiments (Figures 3 and 6), we did assume that each ground truth value $c$ is equal to one of the guesses returned by the imputers ($c \in G$). For experiments where we controlled for the uncertainty radius (Figure 3(a) and 6(b)), we did further over-approximate the ranges to achieve the desired uncertainty radius. We will add clarifications to the main paper and add a detailed description of how uncertainty was generated in the experiments to the appendix.

Regarding the robustness threshold, the rationale for this choice was that different practical applications may differ in how much uncertainty they are willing to tolerate. To account for this in the experiments, we selected both a low threshold (0.5% for the insurance data) and a high threshold (5% for the MPG data). We also explored other thresholds which did not impact the trends significantly: Zorro consistently can successfully certify a larger fraction of the test data points than the baseline due to its use of the more expressive Zonotope domain. We have included additional results in the main rebuttal varying the robustness threshold (Figure 1 in the attached pdf), and we will add these plots to the appendix.

Limitations: At the moment, the last section of the paper (Conclusions/broader impact/limitations) does not include any explicit limitations of their methods. It would be helpful to have a separate discussion on limitations in the main paper instead of appendix. Broader societal impacts may not be relevant for this work.

We will include a summarized discussion on the limitations of our techniques into the main paper and expand on this discussion in the appendix. As mentioned above, there are potential scenarios when the over-approximation can be large because of over-approximation of the uncertainty in a training dataset when there are few possibilities for an uncertain value induce large ranges or in general when the uncertainty in the training data is highly nonlinear.