Finally, it is worth contrasting progressive computation with progressive disclosure. While in the former, the progressive nature comes from the computation side (e.g., new data chunks computed), in the latter, all the data has already been processed and the progressiveness is applied only on the rendering part to ease comprehension or provide information about the provenance of the result and relative visualization. For example, Rosenbaum *et al.* [252, 254] explain how it can be valuable to progressively show a user more of a pre-computed treemap or parallel coordinates view, depending on their screen size. Interestingly, these visual mappings do not update the layout of the visualization, mitigating the tension between stability and quality. On the other hand, they require the full pre-computation of the data and visual mapping, limiting their application to cases in which this is reasonable in terms of the time and resources needed.

One possible solution to address this trade-off between stability and quality is to maintain stability by default and allow the user to interactively trigger “repairing” of the visualization, explicitly breaking the stability to achieve better quality, as mentioned by Jo *et al.* [142]. **Research Agenda:** This strategy has implications for the whole progressive system, since algorithms should inform the user that repair actions are available. Changing the visualization layout certainly breaks the user’s mental map and would require mechanisms to help users recover it, e.g., through history navigation or animated transitions.

<figure><img src="image_46.png" /></figure>

**Uncertainty and Quality** In contrast to classic visualization, progressive visualization can exhibit a high level of uncertainty when the computation is not yet complete (see Chapter 6). The visualization needs to communicate this *PDA uncertainty* using extra visual channels. For example, the SampleAction system superimposes whiskers on each bar to convey the error information as a *confidence interval*. Pangloss similarly shows a pair of heatmaps, one showing the aggregated scatterplot and a second showing the uncertainty of that same scatterplot [205]. Patil *et al.* [224] study the effectiveness of techniques to convey the uncertainty of progressive bar charts and conclude that humans can interpret some of them well. In some systems, it is impossible to bound the approximation, but it is still valuable to present the user with a level of *quality* to illustrate how far the algorithm has advanced.

These are all confounded with other sources of uncertainty in visualization. Visual encodings themselves may try to convey uncertainty (e.g., “value suppressing uncertainty palettes” [60]), and the scaling issues mentioned in Section 5.1 can cause additional uncertainty, as users become unable to read an overplotted or heavily sampled plot. Users consuming the analysis can be prone to perception and interpretation
<figure><img src="image_47.png" /></figure>

bias, which can be exacerbated during PDA, as discussed in Section 7.5.

The next chapter (Chapter 6) further discusses the issue of identifying, quantifying, and visualizing uncertainty in PDA. **Research Agenda:** While there is already a body of research on visualizing quantitative uncertainty, visualizing progressive uncertainty is a newer area that calls for further study.

### 5.2.2 Interaction, Steering, and Control

In addition to the visual considerations, Progressive Visual Analytics introduces new issues related to interaction. These include interacting with visualizations (R12), steering analytical processes through their visualization (R13, R14), and controlling the progressive process itself (R15, R16).

**Interaction with progressive visualizations** The dynamics of PVA completely change how we define and realize user interaction. To illustrate these issues, consider a situation where a user makes a selection by brushing on a scatterplot. With a static scatterplot, the intention of the user is clear: the user wants to select the items in the brushed area. But with a progressive scatterplot, things become more ambiguous. Does the user want to select the points by their current values? If some points in the scatterplot change values and now move outside the range, should they be removed from the selection as well? Are the points added progressively to the scatterplot also added to the selection automatically? If the axes of the scatterplot change, how should the range of the brush selection change?

In addition, points on a progressive visualization can have uncertainty associated with them. Points have a probability of being inside a certain range. What are the semantics of selection with uncertain data?

These issues can be illuminated by understanding the underlying goal of the user. For example, if the user wants to select some outliers on a changing visualization, does the system need to notify the user if the selected points are no longer outliers? The system should clearly inform the user how the meaning and outcome of interactions are being managed throughout the progressive computation. Examples of work in this area include Falcon by Moritz et al. [206] for managing uncertainty and level of approximation while interacting with data, Turkay et al. [304] where a specific adaptation of brushing technique for progressive systems, called “keyframed brushing”, is proposed, Badam et al. [16] where the visualizations are frozen while interaction is in progress (consistent with R13), and Högrafer and Angelini et al. [123], where an adaptation of brushing expressing a user’s query on a bi-dimensional
scatterplot allows steering of the progressive visualization and quickly prioritizing
the generation and visualization of all the data items answering the query. **Research
Agenda:** A number of questions remain to be explored concerning how to make use
of the user's interactions with direct visualization.

<figure><img src="image_48.png" /></figure>

**Steering** Progressive steering is another challenging area. The idea of steering (see Section 2.2) refers to the ability of the user to give direction back to the computation. Steering includes query steering, such as interactive filtering of data to remove irrelevant results, and hyperparameter steering in machine learning, such as interactively changing the number of clusters in a progressive *k*-means algorithm [16]. Some kinds of steering can produce immediate feedback, but others might need more time to become noticeable, while users need immediate feedback, at least to confirm that the changes requested are being taken into account and will be visible soon. **Research Agenda:** Some hyperparameters might be hard to steer due to the computation cost of changing them, or might require recomputation from the start, while others can be adaptively adjusted. A progressive system may warn users when they try to change them, but more research is needed to allow exploration of the hyperparameter space using PVA.

<figure><img src="image_49.png" /></figure>

**Control** PDA design requirements listed in Table 2.1 mention several types of controls that PDA systems should provide (R12–R16), such as pausing or canceling the computation. Others are listed in later publications, such as navigating the history of visualizations in [16] and slowing down a progressive process to better understand it [314]. Jo *et al.* [142] also mention the algorithm notifying the user that triggering a recomputation will improve the visualization at the cost of reducing stability, and so potentially breaking the user’s mental map. **Research Agenda:** Further work should be done to identify the types of controls that are needed by PVA and evaluate their pro and cons on real systems.

<figure><img src="image_50.png" /></figure>

**5.3 Designing a Progressive Visual Analytics System**

The process of adding a visualization for PDA poses a set of constraints and trade
offs that need to be managed during the design process.

**5.3.1 Choose the Right Visual Mapping**

The first important step is the choice of a visual mapping that is able to support the
PDA computation. While, in principle, this step is also applicable to data visualization
<figure><img src="image_51.png" /></figure>

more generally, it must take into consideration how well the visual mapping chosen
fits in terms of the production of partial results coming from the PDA process and
their effects on the visual channels used (R1 and R2).

As we discuss in Section 5.2.1, the requirements for a chart with data that can
change dynamically will have different implications. The mapping must be chosen to
ensure that the visual mapping will be scalable (in the case of big data visualizations)
as well as robust to stability challenges.

Several papers propose design requirements for a progressive system, touching
on visualization aspects [11, 16, 207, 304]. **Research Agenda:** We need guidelines on
how to meet visualization requirements, how to select the best visual encoding for a
progressive visualization, and which features it should provide.

**5.3.2 Represent the Changes**

The second design constraint concerns the representation of changes resulting from
the PDA computation. When the progressive computation is completed, the visual-
ization is updated and must choose when and how these updates should be shown.
We can summarize these as *when* and *how* to visualize the changes.

**When to visualize changes?** The simplest strategy would be to always visualize, using the chosen visual mapping(s), all the changes (or partial results) produced by the progressive process. However, this may not necessarily result in a smooth visual convergence toward a visually stable result, but rather in a sequence of abruptly changing visualizations that can potentially distract the user (against R4) and diminish their trust in the visualization. An unstable visualization will be challenging for a user to interpret, as explained in Section 5.2.1. A rapidly changing visualization is likewise challenging to interact with.

Consider the confusion generated by an unstable visualization. A frequently
changing layout makes it hard to track single elements, meaning that the user is
exposed to confusing rearrangements of elements in position and size. Worse, any
single partial result could be an artifact or an outlier; it may take multiple partial
results to recognize a converging trend. Smoothing both the visual mapping and the
results can help keep the user from being confused. For example, in the work by
Angelini and Santucci [9], visualizations of different partial results that are considered
very similar are omitted from rendering so as not to disturb the user with insignificant
visual changes, while speeding up the progression. In Badam *et al.* [16], the user can
choose between a monitoring mode where the visualization is automatically updated
and an interaction mode where the visualization is only updated when requested. This implies that the visualization has to be notified by the underlying algorithm(s) that refreshing will reveal new information (R13).

**How to visualize changes?** The changes from the progressive computation should be conveyed to users based on the visual mapping being used. A recent survey by Ulmer *et al.* [307] investigated the main aspects of progressive visualization. Among these, the authors identified the *visual update pattern* as a prominent aspect and one that is dependent on the chosen visual mappings. Visual update pattern types describe how visualizations are progressively updated when new data chunks or algorithm iterations are produced. This pertains to factors like animation design and controlled update frequency, which are directly relevant to what has been discussed about the question of when to visualize changes. Moreover, it also concerns visual attribute mapping and the pattern of updates, for which the authors identify two main types: *extension* and *overwrite*.

Extension denotes the process in which new visual elements are added to the visual-ization, which is extended to display new data. Old data is not lost and can help the user preserve context while new data is coming in.

Overwrite, on the other hand, removes old results and presents just the new visual-ization state. The authors model it as a partial overwrite, where only the elements that were changed with new partial results are modified, and a full overwrite, where the previous results are removed completely and new results are displayed. There are pros and cons with both strategies, and the authors investigated their spread with respect to the main visual mappings: temporal, geospatial, hierarchical, and multidimensional visualizations seem to present an even representation of both strategies, while network and field visualizations show a predominance of the overwrite strategy.

Finally, an important aspect is the visual communication of the changes that are taking place. Since the progressive visualization needs to be updated, it may be helpful to highlight to the user where changes are happening. In aggregate visualizations, visual glyphs may change size, shape, as well as location.

**Research Agenda:** There are opportunities for design languages to show changes in progressive visualization.

<figure><img src="image_52.png" /></figure>

### 5.3.3 Visualizing the Progression

The third important aspect to consider is how to visualize the data progression coming from the progressive process itself (R10, R11). In PDA, there is a second layer of
data, referring to the progressive process itself. The system must provide elements that describe how the progression is unfolding (e.g., progress bars that show the progression of computation) and allow the user to infer the quality of the visualized results. The way in which these quality indicators are visualized and communicated to the user is an important consideration during the design of visualization for PDA.

A line of previous works points to a clear division between properties that concern the progression and those that concern the application domain data, with the latter simply reacting to the changes produced in the former. Several projects represent changes from the progressive computation directly on the main visualization [83, 293, 304]. This saves visual space, allowing the visualization to dedicate more space to the visual representation. This technique can be most effective when both the analysis technique and the representation both refer to a clear concept of uncertainty.

Others complement the visualization with an area dedicated to metrics governing the progression itself [16, 89, 270]. At the cost of both using more space and dividing the user's attention, these techniques allow the system to portray uncertainty or progress in greater detail. For example, in Fisher et al. [89], the visualization shows two density maps: one for the estimated outcome and another for uncertainty in the data. A different approach for that work might have instead used a value-suppressing uncertainty palette [60].

**Research Agenda:** More research is needed on the advantages, disadvantages, and design patterns for this topic.

<figure><img src="image_53.png" /></figure>

### 5.3.4 Interaction Between Visualization and Progression

In progressive visualization, the user should be able to control the progression (R12, R13, R14, R15, R16), thus avoiding new design requirements. We will discuss different roles for interaction in Chapter 7. The system should allow the user to interact with the progression, for example, by pausing and resuming computation. Some systems may allow the user to intervene in the computation, for example, by changing parameters. With slow visualization and computation, other systems may allow the user to schedule multiple ongoing visualizations with limited resources.

## 5.4 Existing Visualization Approaches in PDA

In this section, we briefly describe three research PVA systems to demonstrate how the aforementioned considerations are realized in practice. Each one exemplifies a
combination of design choices, and we analyze how each example responds to the considerations we present. These examples do not cover the full range of design possibilities, of course. **Research Agenda:** A systematic approach is needed to identify the design space of choices for controlling and interacting with PVA. The recent survey on progressive visualization by Ulmer *et al*.is a promising first step in this direction.

<figure><img src="image_54.png" /></figure>

<figure><img src="image_55.png" /><figcaption>Figure 5.5: The DimXplorer System [304] adopts an adaptive sampling strategy to deliver progressive responses.</figcaption></figure>

5.4.1 DimXplorer

DimXplorer [304] (Figure 5.5) is an interactive and progressive analysis system for
exploring high-dimensional data. This system introduces two analysis techniques into
progressive data analysis: Principal Component Analysis (PCA) and *k*-means. To
guarantee the response time, the system employs the two techniques using online al-
gorithms, Online PCA [255] and Mini-batch *k*-means [272]. These online algorithms
work on small pieces of data or *batches*, generating and delivering intermediate
results quickly during the computation. These intermediate results become more
<figure><img src="image_56.png" /><figcaption>Figure 5.6: Visual components in DimXplorer [304]. (a) Assigning unique hues to points and maintaining them during transition can help the user track the changes. (b) Bin sizes are used as a visual cue for progression. The bins become narrower as the computation progresses, revealing more details.</figcaption></figure>

accurate as more batches are processed and are used to update the visualizations in
the interface.

The size of batches plays an important role in ensuring that the responsiveness of
the system is below the progressive quantum, as explained in Section 4.7. If the batch
size is too large, the system will not be able to achieve the desired response time, while
a too-small batch size will undermine the system’s throughput. DimXplorer adopts
an adaptive sampling strategy to fine-tune the batch size. This iterative algorithm
starts with an initial batch size, *b*, that is estimated to be small enough to deliver
the response in time. If the actual execution time is longer than the desired time, *b*
increases by one factor, and if it is not, *b* decreases by another factor. In this way an
optimal batch size is found while observing temporal constraints.

To provide coherency between visualizations and maintain the pace of interaction, the system introduces the following strategies. The system seeks consistency between two consecutive computation results. For example, we know that PCA by nature finds principal components (PCs) with arbitrary rotations and signs; we can find mirrored and/or flipped PCs even for the same data. If we display the projection result as is, it would be extremely hard for humans to follow the change. The system addresses this problem by checking the Pearson correlations of the axes between the first and second PCs and mirroring and/or flipping PCs if needed.

DimXplorer supports animated transitions in visualization, providing temporal
coherency for visual elements. An animation sequence takes one second, which is consistent with the desired response time of online algorithms. In addition to transitions, color is used to reveal the relationships between the two scatterplots. Each data point in a scatterplot is assigned a color based on its position, and the color is maintained during the transition (Figure 5.6a).

To provide animated transitions between clustering results, it is necessary to identify a mapping between two consecutive results, i.e., which cluster in the current result ($C_{cur}$) corresponds to which cluster in the previous result ($C_{old}$)? To this end, the authors measured the similarity between each pair of clusters (one from $C_{old}$ and the other from $C_{cur}$) by computing the Jaccard coefficients and setting the cluster with the highest coefficient as counterpart.

Although a one-to-one visual mapping (i.e., scatterplots) is the default visualization approach, the user can switch to a many-to-one visual mapping, or density maps, if necessary. One interesting idea is for the authors to adaptively adjust the bin size of the density map to reflect the progress of the computation—the bins become narrower as the computation progresses—as a means of representing the uncertainty (Figure 5.6b). In this approach, the interpretation of fine details in early visualization results is deliberately made more difficult, thereby preventing the user from making decisions too quickly, while also providing extra clues regarding the progression and uncertainty, in addition to the progress bars.

### 5.4.2 InsightsFeed

InsightsFeed [16] is a progressive visual analysis tool for exploring Twitter data at scale. Its interface consists of three views (Figure 5.7), which are updated progressively: a tweet list view (a list of tweets), sentiment and popularity visualizations (bar charts), and a tweet map (a density map for a t-SNE projection [311] and k-means [186] clustering of tweets). Like DimXplorer, InsightsFeed adopts animated transitions to show updates in views. The difference is that it adopts staged animations to maintain cognitive workflow on updates. For example, the axes of a bar chart are updated first, then new labels are added, and finally, the length of the bars is adjusted (Implication 1).

Each view in InsightsFeed has a dedicated control panel (Figure 5.8) to communicate and control the progress (Implication 3 and Implication 5). This small widget allows the user to play, pause, and stop the progression (R15) and steer the hyperparameters of progressive algorithms (R14), such as chunk size (the number of tweets in a chunk), hyperparameters of the t-SNE algorithm, and the maximum
<figure><img src="image_57.png" /><figcaption>Figure 5.7: The user interface of InsightsFeed [16] for analyzing Twitter data. (A) a list of tweets, (B) a sentiment chart, (C) user popularity chart, (D) a map from a 2D projection of tweets with important keywords highlighted in each region, and (E) feedback and controls over the progression and computations. The interface is progressively updated as more data is processed at a rate limited by the Twitter API used to download the data and by the analytical operations.</figcaption></figure>

number of iterations for the *t*-SNE algorithm. In contrast to DimXplorer, where the progression is simply shown as a progress bar, this explicit widget permits the user to visit the history interactively.

It is worth emphasizing how InsightsFeed measures and communicates the stability of intermediate results. Unlike many PDA systems, which consider the amount of data processed as the main quality metric, the authors introduce a *quality metric* for the four views that increases with computation quality. For example, the metric for the tweet map is defined as the inverse of the projection error obtained from *t*-SNE. For the tweet list and the popularity visualization, the metric is defined as the number of new keywords/users added per chunk, respectively. These quality metrics are visualized over time as line charts in the control panel (Figure 5.8 top), and the user can move a vertical playhead on the line chart to return to a previous state and replay animation from there. The adoption of stability measures offers a clear example of how Implication 2 and Implication 3 can resonate with each other. For example,
<figure><img src="image_58.png" /><figcaption>Figure 5.8: Each view in InsightsFeed is augmented by user interface elements, such as a small widget that shows a stability metric and other widgets that allow the user to steer the computation.</figcaption></figure>

stability measures can be used to predict the amount of visual changes that will occur (Implication 2) and, at the same time, can serve as aggregated uncertainty indicators (Implication 3).

### 5.4.3 ProReveal

ProReveal [141] is a visualization system that implements a new exploration concept—Progressive Visual Analytics with safeguards—as a means of managing the uncertainty of intermediate knowledge during progressive data analysis.

In contrast to the two previous examples, in which the number of views on the screen was fixed, ProReveal allows the user to create new visualizations. This means that the number of running visualizations at a given time can change, and should thus share the limited amount of computation resources. ProReveal allows the user to set the priority between visualizations (R16) through drag-and-drop interaction with a priority list, which is a more sophisticated form of progression management than simple pause-and-play controls (R15, Implication 4). The user can also delay the reflection of partial results in the visualization to prevent abrupt changes (R3, Implication 2).

ProReveal provides a means of managing the uncertainty arising from progressive data exploration. During exploration, the user can interactively create *PVA-Guards*, a hypothetical or *speculative* representation of intermediate knowledge, on a progres-
<figure><img src="image_59.png" /><figcaption>Figure 5.9: The ProReveal System [141] allows the user to add progressive visualizations on demand and manage their relative priority.</figcaption></figure>

sive visualization. A PVA-Guard might represent the concept, for example, that “sales revenue is over 10000”. The PVA-Guards can be verified both online (in the middle of exploration) and offline (after exploration) without user intervention, providing a means of ensuring the correctness of the conclusion and of understanding the reason for intermediate knowledge becoming invalid.

ProReveal adopts two visualization techniques for visualizing uncertainty: gradient plots [59] and density maps with Value-Suppressing Uncertainty Palette (VSUP) [60] (R7, Implication 1). A gradient plot uses bars to visualize univariate values and the uncertainty associated with each value. In each bar, a value is shown as a black line at the center, and the confidence interval of the value is encoded using opacity; 95% two-tailed *t* confidence intervals are shown as fully opaque, while outside the intervals the opacity decays relative to the cumulative probability of an underlying *t* distribution (Figure 5.9). For density maps, ProReveal uses VSUP to encode value and its uncertainty to color simultaneously. In VSUP, the hue channel is mapped to value, and the lightness and saturation channels are mapped to uncertainty. When uncertainty is high, the hue range allocated for values narrows, deliberately making it harder for the readers to read the value and encouraging more cautious decision-making.
**5.5 Challenges for Progressive Visual Analytics**

In this section, we summarize the main challenges that are addressed in the literature, along with the considerations that have been raised in this chapter, which, if properly addressed, should make it possible to realize the scenario presented at the beginning of this chapter. **Research Agenda:** These challenges are relevant to researchers, practitioners, and stakeholders of PDA visualization.

<figure><img src="image_60.png" /></figure>

* **Taxonomy of effective visual mappings for PVA:** More research is needed to explore the characteristics of existing visual mappings and their adaptability to progressive computation. Such effort should help to improve our understanding of what data characteristics, tasks, and degree of change during computation are supported by existing visual mappings. It should identify what aspects are critical to consider in adapting those visual mappings to PDA, while highlighting the combinations for which no existing visual mapping can be used. Ulmer et al. have provided an initial exploration of this space, identifying network and hierarchical visualizations as underexplored areas for progressive visualization. This may lead to specific extensions of the popular “Grammar of Graphics” (GoG) [332] and its implementations [266, 329] to better support PVA.

* **Research and novel visual mappings for PVA:** Based on the outcome of the previous challenge, research should focus on the creation of novel or “custom” visual mappings specifically created for supporting progressive visualization in certain domains. Those mappings could be derived from existing ones, perhaps even making significant changes to the original behavior in order to better support the visualization of partial results. Or, they could be completely new, derived from intrinsic characteristics of a progression that could be used as foundations to build on top of a novel visual mapping. Whatever kind is used, it should natively consider from the start interaction means and management of uncertainty.

* **Develop strategies for governing progression** From a visualization standpoint, PDA may have different ways of managing the progression that unfolds. Aspects that should be considered include: how to support the management of visual changes and visual update patterns; how to manage the user's visual attention and help her identify significant changes, or recover the current status of the progression, at any given time; how to manage needs concerning analysis time or the speed of production of new partial results. Finally, research should also focus on how to manage mid to long-lasting computation, where
the PDA process takes time to complete. Elements such as quick identifica-
tion of changes relative to the last result seen and notification/context restore
mechanism should be investigated.

* **Provide mechanisms for attention management in PVA** Research should focus on steering mechanisms for the progression that are able to represent both the “semantic” user desiderata and its adaptation to the sequence of partial results. Examples of aspects to consider range from managing the communication of progression metadata, giving priority to the smoothness of the unfolding, or highlighting “spikes,” in both static (fixed) or dynamic (changing at run-time or by user selection) versions. Attention to a mechanism for integrating progression uncertainty into the visualization is also important, as it is possible to have good quality in a local area while the quality of the overall process remains low. Finally, support for speculative analysis and exploration of multiple concurrent progressive runs forming an ensemble are also aspects that need more visual support.

* **Expand the progression management on more than one dimension** As described in this chapter and revealed by Ulmer et al., most of the existing approaches on progressive visualization apply the progression on a single dimension, which can be temporal, geospatial, etc. There may be cases where multiple dimensions require the application of progressive computation and visualization, such as dynamic networks, presenting both the management of changes over time and changes in the topology. Only one study [16] has explored this scenario to any degree, combining Twitter stream analysis with a changing *t*-SNE projection. Further research is needed to identify the most common combinations of dimensions on which to apply progression, how to make coexisting visual changes that come from these different dimensions, and how to effectively communicate those changes to the user in a way that is not confusing.

5.6 Summary

This chapter discusses the five ways of scaling visualization techniques: sampling, filtering, aggregation, multidimensional projection, and summarization. It explores the challenges of scalability and stability for visual rendering, and of controlling progress and steering for interactivity. The review of those aspects spans different phases of the design, from the choice of visual mapping to the interdependencies
of the progression that unfolds with it, and finally, how to manage interaction with
“progression-aware” interaction means. A description of three main contributions
in the Progressive Visual Analytics field helps to understand what they mean in
practice and what solutions might exist to address those concerns. Finally, we
summarize recent challenges that researchers have encountered that might represent
promising topics of research in the future. We hope the reader interested in designing
a progressive visualization will benefit from this discussion of the implications to be
considered during their design and from these example solutions.
# 6 Uncertainty and Quality

<table><tr><td>6.1</td><td>Introduction</td><td>92</td></tr><tr><td>6.2</td><td>Example Pipelines</td><td>95</td></tr><tr><td>6.3</td><td>Sources of PDA Uncertainty</td><td>96</td></tr><tr><td>6.3.1</td><td>Uncertainty from Data Processing</td><td>96</td></tr><tr><td>6.3.2</td><td>Uncertainty from Computation</td><td>97</td></tr><tr><td>6.3.3</td><td>Uncertainty from the Progression</td><td>98</td></tr><tr><td>6.4</td><td>Measures/Quantification of Uncertainty</td><td>99</td></tr><tr><td>6.4.1</td><td>Sampling Approximations</td><td>100</td></tr><tr><td>6.4.2</td><td>Aggregation Approximates</td><td>103</td></tr><tr><td>6.4.3</td><td>Computation-based Approximates</td><td>104</td></tr><tr><td>6.4.4</td><td>Progressive Measures</td><td>105</td></tr><tr><td>6.5</td><td>Visualization of PDA Uncertainty</td><td>105</td></tr><tr><td>6.6</td><td>Summary</td><td>107</td></tr></table>

Authors Anna Vilanova, Marco Angelini, Sriram Karthik Badam, and Jean-Daniel Fekete

## 6.1 Introduction

The ability to effectively model and communicate the quality and uncertainty of the current result is an essential component of Progressive Data Analysis. By definition, the intermediate results that a PDA system displays during a computation are not yet complete, and so are estimates of the final result [8]. Users must be able to evaluate the *PDA quality* or *PDA uncertainty* of the intermediate results to make well-informed decisions. The user has to decide if the information computed and presented so far is close enough to the final result to make a decision, or if more time is needed, as shown in Figure 6.1.
**Definition 10 (PDA uncertainty).** PDA uncertainty is defined in this chapter as the uncertainty about how likely the partial result is to deviate from the final result. Most processing pipelines generate results with uncertainties, e.g., due to noise in the data or parameter settings. PDA uncertainty focuses on the uncertainty that is introduced by the specific features of the progressive process to the intrinsic uncertainty of the results. It encompasses measures related to traditional uncertainty measures in statistics, such as confidence intervals (CIs) and Bayesian posteriors, that are used to measure the uncertainty of a single value generated from a specific function or endpoint (e.g., mean). It also encompasses uncertainty models used with more complex endpoints, data, and function types.

**Definition 11 (The PDA quality).** PDA quality of a progressive result is defined in this chapter as the general degree at which any given partial result is a good approximation of the final result. A PDA quality measure is not a direct measure of the variability of the result, but is a more indirect measure intended to give a relative sense of how complete the current result is, e.g., the percentage of data samples processed.

<figure><img src="image_61.png" /><figcaption>Figure 6.1: The three phases of PDA uncertainty. The vertical axis represents the error $\epsilon$ due to PDA uncertainty, which should be as small as possible at the end. The uncertainty $\epsilon$ should improve over time, from a (1) *chaotic* phase, in which the estimates are unreliable, a (2) *converging* phase, in which the estimates become more stable and slowly begin to show reliable patterns for decision-making, and a (3) *converged* phase, in which the estimates converge, signifying that decisions can be made accurately and the progression can end.</figcaption></figure>

One of the main decisions that a user has to make is whether to act on an intermediate result or wait for the PDA to progress. Similar to Angelini et al. [8], we
divide the process of a PDA analysis into three phases, as shown in Figure 6.1. In the first phase, the error $\varepsilon$ due to *PDA uncertainty* is high, so the results are highly uncertain; there is a high risk when drawing any conclusion in this phase. In the second phase, intermediate results carry enough useful information to be interpreted. However, substantial *PDA uncertainty* remains and needs to be considered. During this phase, the user can make some predictions but cannot yet be sure of the results. In the third phase, the results are close to the final result, and further increases in quality will not influence the information carried by the results. The *PDA uncertainty* will not influence the analysis. In the final phase, the time spent on refinement can be considered wasted because there is no corresponding improvement in the results and uncertainty. An effective *PDA uncertainty* visualization both aids the user in determining the phase they are in and allows the user to assess the time needed to make well-informed decisions. *PDA quality* is used when we cannot model *PDA uncertainty*; it is a measure of the progress that indirectly relates to the quality of the results.

While visualization has long grappled with the implications of uncertainty in data [105, 140], *PDA uncertainty* and *quality* are intrinsic to PDA. By ignoring them, there is a real risk that users will make unfounded decisions based on premature results. For example, users might be tempted to stop progressivity at a point when the results confirm their own beliefs, but allowing the progression to run longer would have shown that the current result is an artifact. Conversely, users may take longer than needed to make good decisions if they cannot interpret the *PDA uncertainty* and *quality* correctly. Effective visualization of the *PDA uncertainty* and *quality* should aim at reducing or avoiding potential bias and errors as quickly as possible; the problem relates to the theory of sequential statistics [321] and *optimal stopping* [52].

The rest of this chapter offers an overview of *PDA uncertainty*. We begin with a motivating example to help illustrate how *PDA uncertainty* plays out in practice. Section 6.3 discusses the different sources of uncertainty in progressive data analysis, which are directly related to methods used to achieve the PDA strategy. Section 6.4 provides an overview of different methods that can be used to quantify *PDA uncertainty* and *quality* given the different axes that characterize them. Section 6.5 presents the different visual representations.
<figure><img src="image_62.png" /><figcaption>Figure 6.2: The user interface of InsightsFeed [16], same as Figure 5.7 with the *PDA uncertainty* and *quality* visualization aspects highlighted.</figcaption></figure>

## 6.2 Example Pipelines

Let us begin by reviewing a sample system from the perspective of uncertainty. Section 1.3 introduces the InsightsFeed system [16]. In Figure 6.2, we see the system with four progressive visualizations, each dealing with different quality or uncertainty measures. They are unified visually using a simplified quality line chart over time displayed on top of the visualizations in the progress bar; the quality value in the line chart goes up when quality increases. However, the meaning of the quality measure is different for each visualization.

For example, in (A), the *PDA quality* is simply the percentage of tweets processed over the total, improving along with the progress bar. This particular screen shows that 340 of some 2500 tweets have been examined so far. In (B), the bar chart shows the distribution of the sentiments among the three categories *negative*, *neutral*, and *positive*. Its *PDA uncertainty* relates to the number of tweets in each category/bar, as later studied by Patil *et al.* [224]. (D) shows a *t*-SNE projection and its *PDA quality* can be seen as related to the objective function computed during the optimization process: the KL divergence [166] between the distances in high-dimension and low-dimension [311]. This is a mixture of *PDA quality* and the intrinsic quality of the
final *t*-SNE result itself. In this case, it is not possible to separate the intrinsic quality
from the *PDA quality* since the final value of the objective function is not known.

In this example, the quality visualization allows us to answer some simple ques-
tions: Is the process improving over time? Is it stabilized? If the quality is not
stabilized, it is still in the first or second phase, and the current result might be
inaccurate. If the quality of the results is not improving, it may be that it has reached
the final stage and will not improve any further, or there is something wrong either in
the data or the process (i.e., it is not shuffled, it has a strange distribution, it contains
outliers or it does not converge).

Ideally, each visualization should provide a meaningful assessment of the *PDA uncertainty* or at least *PDA quality* computed from the data and the process, and in a form that allows users to make these decisions. For example, some dense areas of a *t*-SNE projection may become reliable sooner than sparse ones. *PDA uncertainty* and *quality* encompasses the choice of meaningful measures for each stage of a pipeline, their combination, and their visualization in a way that facilitates decision-making but does not hurt readability or users' attention.

6.3 Sources of PDA Uncertainty

Any data analysis system must wrestle with some forms of uncertainty: there are
intrinsic uncertainties regardless of progressivity. Uncertainties and errors are in-
trinsic to the data, implying limitations in computation and visualization trustwor-
thiness. Considerable attention has been devoted in recent years to the question of
how to provide effective methods to communicate uncertainties in the visualization
pipeline [105, 131, 140, 221, 287].

*PDA uncertainty* comes from the three main ways of making progressiveness
possible: *data processing* (applies to *progressive-in-chunks*), *computation* (applies to
*progressive-in-iterations*), and *the progression* itself. The goal of this section is to
highlight these three sources and types of uncertainty. Once we identify the sources,
we can quantify and visualize *PDA uncertainty* or *quality* to raise awareness among
users and provide a complete picture for decision-making. Therefore, we will isolate
the types of uncertainties.

### 6.3.1 Uncertainty from Data Processing

Fundamentally, the source of uncertainty in *progressive-in-chunks* PDA systems (introduced in Section 2.4) is that only part of the data is known at any point in the
computation. Depending on the data sampling method, different assumptions can be
made about the final results from the intermediate results.

Let's take the simple example of progressive bar charts, which are used in many
progressive visualization articles (e.g., [16, 89, 141, 342]) and are studied by Patil
et al. [224]. A bar chart is computed by aggregating values from categorical data,
such as counting the number of tweets collected from a tweet feed, which are tagged
as either *negative*, *neutral* or *positive*. When the aggregated values are computed
progressively, the bars will not reflect all of the data. The intermediate result will
have different uncertainties depending on whether the sampling method distributes
the samples proportionally through the classes of the categorical attribute. In general,
there are two aspects to consider with *PDA uncertainty*:

**Sampling approximations** lead to inconsistencies in the statistics presented to the user or sent downstream of a pipeline. The sampling strategy can define how the overall data statistics appear in data samples, as explained in Section 3.5.1. Random sampling can miss underrepresented entities in the data, while stratified sampling can be misleading because of high-level characteristics. In many PVA examples random sampling is used [16]; however, it is not uncommon to use the distribution statistics to define the progression [205], or to use data-specific sampling strategies [126].

**Aggregation approximations** are made when an aggregation function is applied to the sampled data. If this aggregation is not *distributive*, approximations are used. For example, the median operation is not distributive: the median of multiple chunks of values is not the same as the median of each chunk's median. Operations such as *median* are called *holistic*, since they require all of the data to be computed accurately [330]. Examples of useful holistic aggregation operators include the *median*, all the *quantiles* (except 0, and 100%, i.e., min and max), and the count of distinct values. Several of these holistic aggregations can be computed approximately using data sketches [57], but the approximation generates uncertainty in the results.

6.3.2 Uncertainty from Computation

*Progressive-in-iterations* methods (introduced in Section 2.4) create results from
computations that approximate and incrementally approach the final computational
outcomes. Some algorithms, such as optimization methods, have progression inherent
to them. For example, *k*-means clustering is iterative until convergence is achieved
based on a specific objective function that is optimized. Often, as in the case of
*k*-means, convergence does not always mean that the best possible functional value is obtained—*k*-means algorithms are heuristics that often yield a local optimum, not a global one, so the functional end value is unknown. In this situation, it is difficult to evaluate the *PDA uncertainty* or *quality* independently of the intrinsic accuracy.

The stability of the functional value becomes a proxy for the *PDA quality* of the intermediate results as an indicator of convergence. Beyond the use of intermediate iterative optimization results, there are PDA methods that approximate computations. For example, computing the *k*-Nearest Neighbors approximately to accelerate the process (e.g., approximate *k*-Nearest Neighbors [142], progressive *t*-SNE [233], and progressive UMAP [160]). Here, more neighbors are computed progressively, creating more accurate results. In this way, the number of neighbors from *k* that are computed exactly increases through progression until all (or most) neighbors are exactly computed. Mühlbacher *et al.* [207] provide guidelines for creating such methods.

### 6.3.3 Uncertainty from the Progression

The progression itself, combined with the user and tasks, adds a layer of uncertainty. The evolving nature of the estimates and the continuous changes to the results can be challenging to follow. There are two types of uncertainty here:

**Temporal uncertainty** (see Figure 6.1): From a user's perspective, we can divide the progression of the results into three distinct phases of uncertainty, as explained in the introduction section. Overall, the user is interested in knowing which phase the progression is in and when the PDA results are good enough to make a decision, which is likely earlier than the time needed to reach the final result. Indicators presenting this information will be essential to the decision-making process of the user.

**User/task uncertainties** In addition, uncertainty may also arise from the user's task (see Section 7.3). The uncertainty can differ based on the nature of the task—hypothesis formation can occur earlier than the confirmation or communication of results. Ultimately, the user gets to decide when the result is good enough. As PDA designers, we should strive to identify all the types of uncertainty and provide as much information to the user as possible. Good PDA systems will help the user steer the process to the final results through the uncertainty phases as defined in Figure 6.1.
**6.4 Measures/Quantification of Uncertainty**

Now that we have defined the principal sources of PDA *uncertainty* in a progressive
data analysis process, in this section, we provide an overview of the process of
measuring or quantifying PDA *uncertainty* and *quality*. For example, we might
want to present confidence bounds on results that are shown to users so that they
can understand the accuracy of the approximation that appears at any given stage.
Different parameters will influence the definition of PDA *uncertainty* or *quality*
measures:

**Absolute vs. relative measures** These measures can be additionally considered with respect to their absolute values (i.e., a value per partial result with respect to the final iteration) or their relative value (i.e., difference between values for two generic partial results). For example, the objective function of the *t*-SNE algorithm is an absolute quality value that will converge to an optimum over the course of the optimization process. Conversely, the sum of the displacements of *k*-Nearest Neighbors centroids between two progressive iterations is relative.

**Global vs. local measures** A measure is global if a single value is computed for a whole partial result, and local when computed for part of the partial result or individual elements. For example, computing the stability of a *k*-Nearest Neighbors algorithm, as explained above, is a global measure, whereas computing the confidence interval of each bar in a progressive bar chart is a local form. In the latter case, a part is again considered for different stages of a pipeline (Data Processing or Visualization) or for different data intervals (e.g., a PDA process that computes a distribution of values can be stable in a fixed interval of partial results). Aggregation approximation strategies are a logical choice when you need to identify local versus global changes. For example, when aggregating a distribution by binning, the bin becomes the local unit. When aggregating a map across administrative boundaries (e.g., in a choropleth map), the administrative subdivision becomes the local unit.

**Closed- vs. Open-world scenario** A Closed-world scenario is one in which the total number of data points is known in advance, along with its characteristics (e.g., distribution). In a *progressive-in-chunks* system, for example, it means that the remaining number of data points to be processed is known. In a *progressive-in-iterations* system, it could mean the number of iterations that remain. In an Open-world scenario, on the other hand, the end target is not known, as, for example, with chunks read from a data stream of unknown size or from an iterative algorithm with
an unknown end condition. The usefulness of a measure for uncertainty quantification will depend on whether we are in an Open- or Closed-world scenario.

Angelini et al.'s proposed a framework [8] for classifying the measures of in-
termediate results uses a three-aspect model: (1) *progression*, (2) *stability*, and (3) *uncertainty*. Here, each aspect allows the system to provide more precise estimates to the user regarding the potential *PDA uncertainty* or *quality* of the results available.

**Progression:** The requirement for this aspect is that it be possible to measure or estimate the amount of work remaining for the PDA to finish, i.e., a Closed-world scenario. A measure of progress can enable the user to estimate the likelihood that the actual results will not change much by the end of the process. *Progression* is the least effective measure of quality among the three, but it also serves other purposes (R9, R10, R11).

**Stability:** This refers to the degree of variation of the results produced by a PDA process. This measure can be used by the user as an indicator of how much the estimate of the final result is changing and to decide on that basis whether the current results can be considered sufficiently valid. We discuss stability with regards to convergence in Section 2.2. While unstable results cannot be reliable, stable results can be inaccurate. Therefore, it can be misleading to rely on stability alone.

**Uncertainty:** PDA *uncertainty* is defined as a measure of the degree by which the current partial result can still deviate from the final result (Definition 10). In Closed-world scenarios, when all the data has been processed, there is no more *PDA uncertainty*. In progressive scenarios (before completion), uncertainty estimation becomes a challenge. It cannot always be computed directly and conclusively.

*PDA uncertainty* quantification is a non-trivial problem since, in many situations, off-the-shelf solutions are not directly applicable to a progressive setting. Uncertainty quantification approaches can be classified according to the main types of progressivity described in Section 6.3. In the rest of this section, we present the different measures and quantification of *PDA uncertainty* and *quality* based on the sources of uncertainty.

**6.4.1 Sampling Approximations**

Sampling approximations are a widely used method in statistics for the study of un-
certainty quantification (e.g., using confidence intervals and significance testing). The
applicability of these methods is based on assumptions regarding the characteristics
of the full data set from which we are sampling (i.e., Closed-world vs. Open-world).

If the overall sample size is known, a global *PDA quality* estimator is the ratio of the samples already processed and the total sample size of the full data set. This *PDA quality* estimator assumes that the more data that is processed, the more accurate the result will be.

Many systems use confidence intervals (CIs) as their indicator of uncertainty. For example, for the mean computation of a random variable, CIs are computed based on the central limit theorem. A confidence level of 95%, for example, means that the chances that the real mean value of the full population is inside the interval are above 95%. Therefore, there is a 5% chance that the real value is not inside the interval.

CIs for statistical parameter estimators, such as the mean, median, or total population, have been extensively studied in statistics. These CIs assume that the sampled data is independent and identically distributed (iid) and that there is a known overall data set sample size. In a PDA setting, these conditions are often violated and cannot be directly applied.

Uncertainty measures such as CIs can be updated progressively, but they introduce the problem of *repeated tests*. If humans want to make a decision based on progressively computed results and the associated uncertainty, they might carry out tests multiple times using the same samples. In our election example in Section 1.1, for example, a test to decide early who the winner is might be: does candidate A have significantly more votes than candidate B? While observing the progression of the count hour by hour, we would perform a test every hour. If we use a 95% confidence level for the test, there will be a 5% chance that we will make an error each time. Overall, the chances of an error will grow each time; if we conduct *m* tests, we will have a probability of error of $0.95^m$, assuming the tests are performed with independent samples. But this is not the case; since they are cumulative. Therefore, the chance of making an error is slightly different, but the principle is the same: we need to correct the test each time to keep the confidence level constant. The statistics related to the problem of compensating for multiple tests have been studied in the domain of sequential analysis [321].

Sequential analysis methods are used in applications where, for example, the cost of data collection is high, or there are ethical reasons for not collecting unnecessary samples. Instead of having a fixed sample size, the tests are done sequentially and stopped when there are enough samples. Popular methods to address the *optimal stopping* [52] problem and making the right decision include SPRT [321], Haybittle-Peto, and O'Brien-Fleming boundary tests [218, 236]. However, these are complex to use in an exploratory setting.
Distribution bias is another important issue in statistical analysis that is related to the difficulty of making decisions when the distribution of the samples is not known or is not well-behaved. In that case, guessing the distribution is also difficult, and there is no magic method for creating a black-box sequential significance test [224]. Several tests can be used heuristically, but aside from a few special cases, e.g., normal or well-behaved distributions, they will all have an unpredictable error one way or the other. Therefore, it falls to the human user to arrive at a final answer. Returning to the election data, we are aware of the non-stationary sequence for counting the ballots. Cities have different distributions than rural areas, foreign voters are different from domestic voters, etc. We have to allow for all these factors whenever we attempt to predict the outcome of an election before the counting of ballots is finished. But sometimes, even with all of our experience, our attempts fail. And sometimes the statistics methods themselves fail, depending on the confidence level requested.

For a histogram estimator, simple known distributions after a certain number of samples of the underlying probability distribution can be fitted and guessed. The accuracy can also be measured by a confidence interval per bin, although by doing so, there is a dependency that is ignored. Patil *et al.* [224] have studied sequential analysis for a few tasks on bar charts. They report that humans are quite good at finding a good trade-off between wait time and accuracy in making decisions. They also show that statistical tests can be used, sometimes with good results on their experimental data, but without any formal guarantees. They also attempted to infer data distributions empirically, but concluded that this is generally difficult and unreliable.

When the distribution is unknown or the estimator or data is complex, non-parametric Monte Carlo simulations or bootstrapping methods [76] can be used to evaluate uncertainties. Monte Carlo simulation and bootstrapping methods are more flexible and can be used for complex functions as parameter estimators (i.e., processing pipelines) that have no analytical solutions. They are based on simulation techniques that use resampling strategies to obtain multiple possible output samples that describe the variability of the output. These multiple output samples often need to be modeled or summarized to be communicated and to adequately represent the output uncertainties [86,285]. However, they are computationally costly [340] and challenging to model since assumptions, e.g., on fitting parametric distributions, do not hold.

In summary, while an extensive amount of work exists in statistics on the definition of errors and confidence intervals, for complex real-world PDA problems, the necessary assumptions for these methods will be violated and out-of-the-box methods will
not be adequate.

**Research Agenda:** The implications of using traditional statistics are unclear when certain assumptions, such as the iid, are violated, as is often the case with PDA problems. The use of sequential analysis methods in PDA solutions appears to be an under-explored area.

**Research Agenda:** High-dimensional complex data analysis and complex estimators remain an open problem with regard to *PDA uncertainty*. There is no unique way to indicate the uncertainty of complex data beyond well-defined high-dimensional numerical spaces.

<figure><img src="image_63.png" /></figure>

<figure><img src="image_64.png" /></figure>

## 6.4.2 Aggregation Approximates

Aggregation approximates are used in progressive refinement approaches, in which there is typically a hierarchy defined that aggregates data at different levels of detail in a pre-processing step. In these approximations, we are often in a Closed-world scenario. For example, a volumetric multiresolution grid (e.g., octree) is built to accelerate simulations or volume rendering, or a data hierarchy is built to explore high-dimensional data (e.g., HSNE [232]) at different levels of detail. These methods can use traditional statistics and summaries that indicate the level of approximation at each hierarchy node. The estimation of uncertainty can either be local or an aggregation to indicate global. A *PDA quality* indicator can also be the level in the hierarchy that is being analyzed.

For example, processing GPS data at country-, city- or neighborhood-level aggregates creates approximations that follow progressive refinement. A simple measure of uncertainty is the level of aggregation being processed at the most detailed level. It is often possible to compute the information that is lost on the data aggregation based on the variation of the elements that form it. This measure shows, either locally or globally, the uncertainty of the distribution of error in the input data. Processing the GPS locations is done with grid-based approximation (approximating them to the nearest grid location) or creating routes inside them using simplification algorithms (e.g., Douglas-Peucker algorithm [73]).

However, the analytical propagation of the uncertainty in the input to the output result can only be done in special situations and not in general cases. For that reason, the direct quantification of output uncertainty is often challenging, and Monte Carlo or bootstrap methods combined with heuristics will be used.
6.4.3 Computation-based Approximates

Computation-based approximates are a common way to accelerate processes in
which the computational complexity itself is high. In these methods, the compu-
tations are approximated to accelerate the process or to ensure that it is possible
to obtain any result at all. There are multiple examples of these approaches. In
visualization, for example, progressive dimensionality reduction implementations of
*t*-SNE [142, 233, 311] or clustering methods such as *k*-means are commonly used.
Randomized computations, such as Monte Carlo approximation [343] for numerical
approaches, are a common example of approximation. These methods usually have
clear theoretical error bounds that can be computed analytically. Heuristic approaches
are also used, for example, by using the locality of a problem. In that case, the bounds
are harder to define. Error tolerance can be allowed, for example, approximating
instead of computing an exact *k*-Nearest Neighbors, which requires the computation
of the distance between all pairs of dataset points. Using the locality of the prob-
lem, the neighborhood can be approximated with a predefined uncertainty level (i.e.,
the number of *k*-neighbors computed accurately). This level can be progressively
refined [233]. The measure of uncertainty in the output (e.g., distance computation)
cannot be computed. However, a local indicator of *PDA quality* is the number of
neighbors from *k* that have been exactly computed per data point. In this case, we
have a clear global endpoint in which all *k* nearest neighbors per data point are exactly
computed.

Optimization algorithms, e.g., based on gradient descent [173] lean easily towards
progressivity, given their iterative nature. The evolution of the optimization or cost
function provides an indication of the *PDA quality* of the result [16] and, therefore,
it is not possible to discern the *PDA quality* from the intrinsic quality of the final
result. However, it remains unclear at which exact value the minimum or maximum
will be achieved, and it is not adequate as a measure of uncertainty. The evaluation
of the value would be expected to be similar to the one presented in Figure 6.1.
Unfortunately, the absolute values of the error ε are unknown in advance. It is
not, however, an uncertainty measure. Stability would relate to when the current
objective function values and the ones in the past iterations are not changing, which is
a common measure of convergence. For example, the well-known *k*-means clustering
algorithm is NP-complete to find the optimal solution, so its implementations are
heuristics that generate errors and uncertainty on the cluster members and cluster
centroid locations. Progressive implementations, like most implementations, use
the stability of the cluster centroids as quality, but they cannot show the bounds or
represent the uncertainty in the form of, for example, confidence intervals.

### 6.4.4 Progressive Measures

In principle, in a PDA process, the *PDA uncertainty* or *quality* indicators are computed synchronously with every partial result. However, if the computation of a measure is expensive, it could also be computed in a progressive fashion and thus appear asynchronously. For example, using bootstrapping to compute CIs is iterative and can be done in a progressive way for complex computations.

**Research Agenda:** The *PDA uncertainty* or *quality* would appear with a delay or might force the visualization of the result to be delayed. More research is needed to better understand how users can interpret *PDA uncertainty* or *quality* measures when they appear to be delayed.

<figure><img src="image_65.png" /></figure>

## 6.5 Visualization of PDA Uncertainty

After finding the sources of uncertainty and ways to quantify them, it is important to visualize this information to the user in an unbiased and adequate way. In this section, we present visual encoding strategies for *PDA uncertainty* and *quality* as a complement to Chapter 5.

General guidelines exist for visualizing uncertainty in the research literature [131, 140, 221]. Standard visual variables offer a good starting point, but they are often already used to convey the data itself. Position, length, and color are popular choices in many progressive systems for conveying uncertainty. Examples include, (1) utilizing heatmaps to convey uncertainty in position [16, 293], (2) error bars to convey uncertainties in value and distribution of variables [224, 342], (3) transparency and color saturation to convey uncertainty in bi-variate distributions [141, 205, 293], and (4) using multiple visualizations to couple data insights and uncertainty separately [16].

Visualizing uncertainty goes hand-in-hand with providing a sense of *PDA uncertainty* or *quality* in the progression, as described in previous sections. Stability in PDA corresponds to the amount of change in the visualization or, rather, the outcomes from the underlying computation or data sampling. When progressive visualizations are updated, the change between frames is visible as an animation. Therefore, animation is the most straightforward way to indicate stability. On the other hand, quality can be quantifiable from the underlying computation in terms of the error and accuracy estimates provided by the algorithms. For instance, when using *k*-means, the centroid shifts can be visualized as an indicator of the stability of the computation [83].
**Differences in PDA vs. general uncertainty** The main novel issues related to *PDA uncertainty* are the need to monitor the progression, time-evolving stability, and quality or uncertainty related to PDA. Avoiding bias in the users by showing progression results is also a major subject of interest.

For the progression, most PVA systems use some sort of progress bar in the interface. InsightsFeed introduces specific UI elements to show the progression and, on top of it, the stability as a line chart of quality (see Figure 5.8). The TensorFlow Playground [298] also visualizes the loss over time while running a neural network learning session. Discrete/unit visualizations are preferable for conveying uncertain outcomes in related work [130]. This is because unit visualizations can provide an open representation of the units within the data. Hence, in contrast to continuous/aggregate representations such as line charts and bar charts, discrete representations have an innate sense of uncertainty. Dot plots [84] and density maps are examples of discrete visualizations. These plots make generous use of visual marks to show individual data points (or a few data points), making it possible to keep track of sampling uncertainties.

Unfortunately, in many cases, progressive visualizations do not have the luxury of representing individual data points due to the sheer size of the datasets. Therefore, progressive visualizations face challenges in providing a complete picture of the uncertainty in the progression, outcomes, and user understanding.

**Research Agenda:** More research is needed on the question of a systematic approach to conveying progression, quality, and stability, along with interactive controls over the progression to assist users.

**Uncertainty/quality changes over time** Similar to the progressive outcome itself, it is important to visualize the changes in uncertainty and to provide the user with controls over the progressive outcome, as highlighted by the requirements of PDA systems listed in Table 2.1. Animation is commonly used to show the progression. However, animation has its limitations, such as a tendency to direct too much of the users' attention to small changes, thus overloading short-term memory. In some progressive systems, the presence of multiple progressive visualizations can be challenging for the user [205]. In such a situation, tracking absolute and relative progress for each progressive visualization is important. The uncertainty measures have been conveyed with line charts in the relevant literature [16,83]. Basic controls to pause, replay, stop, and refresh the progressive visualizations, and advanced controls over the parameters of the underlying visualizations, offer ways to understand and deal with the *PDA uncertainty* outcomes from the progression using animation [83].

<figure><img src="image_66.png" /></figure>
Showing *PDA uncertainty* and *quality* is essential, but translating them into decisions is another important step in the process. A PDA system can help in this regard. It can either provide advice on how to read and make use of uncertainty, as explained in the training from Patil *et al.* [224], or by adding tools to support decision-making, as explained in Ferreira *et al.* [85] and in the ProReveal system [141]. While these tools can mitigate possible cognitive biases (see Section 7.5), they should not be blindly trusted, as the existing tests are sensitive to difficult data distributions, outliers, and biased sampling. **Research Agenda:** More research is needed on the question of how to better guide users in interpreting uncertainty/quality over time for decision-making.

<figure><img src="image_67.png" /></figure>

**6.6 Summary**

In this chapter, we presented multiple classifications and ways of presenting the uncertainty that is an intrinsic part of a PDA system, *PDA uncertainty* and *quality*. We introduced three phases of uncertainty (chaotic, converging, and converged), while defining the characteristics and expectations of uncertainty during the PDA process. The multiple sources of uncertainty are presented: sampling for *progressive-in-chunks*, convergence for *progressive-in-iterations*, and many others arising from the progression itself. We classified the different characteristics of the uncertainty measures and quantification based on the assumptions and knowledge of the specific PDA situation described in the literature. Most measures that are well-established, such as using CIs, are based on assumptions that often are not applicable for testing in a PDA setting, and alternatives like the ones proposed by sequential analysis should be considered. Finally, the challenges and existing strategies for the visualization of *PDA uncertainty* and *quality* were presented. The characteristics of progressivity add another layer of complexity and additional constraints to traditional uncertainty visualization and thus call for more research.
# 7 Human Aspects

<table><tr><td>7.1</td><td>Time Engineering for Human Factors</td><td>110</td></tr><tr><td>7.2</td><td>User Roles</td><td>111</td></tr><tr><td>7.2.1</td><td>Role 1: The Progressive Observer</td><td>111</td></tr><tr><td>7.2.2</td><td>Role 2: The Progressive Searcher</td><td>112</td></tr><tr><td>7.2.3</td><td>Role 3: The Progressive Explorer</td><td>113</td></tr><tr><td>7.3</td><td>User Tasks</td><td>114</td></tr><tr><td>7.3.1</td><td>The Observer's Analytic Tasks</td><td>115</td></tr><tr><td>7.3.2</td><td>The Searcher's Analytic Tasks</td><td>116</td></tr><tr><td>7.3.3</td><td>The Explorer's Analytic Tasks</td><td>116</td></tr><tr><td>7.4</td><td>User Focus</td><td>117</td></tr><tr><td>7.4.1</td><td>F1: Focus on the Data Space</td><td>118</td></tr><tr><td>7.4.2</td><td>F2: Focus on the Algorithm Space</td><td>119</td></tr><tr><td>7.5</td><td>User Complications and Biases</td><td>120</td></tr><tr><td>7.6</td><td>Application Example: Crisis Management</td><td>124</td></tr><tr><td>7.6.1</td><td>The Background</td><td>124</td></tr><tr><td>7.6.2</td><td>An Illustrating Scenario</td><td>126</td></tr><tr><td>7.6.3</td><td>The Design Guidance</td><td>128</td></tr><tr><td>7.7</td><td>Summary</td><td>130</td></tr></table>

**Author** Hans-Jörg Schulz, Michaël Aupetit, Danyel Fisher

From a user-interaction perspective, what makes Progressive Data Analytics different from classic visual analytics is that it introduces a new temporal rhythm to data analysis loops. Following Dimara and Perin [69], we understand interaction for visualization to be “the interplay between a person and a data interface involving a data-related intent, at least one action from the person and an interface reaction that is perceived as such.” Time perception is crucial in that interaction dialogue, and time reaction expectations can differ depending on the context [42, 180].

We turn in this chapter to five aspects of human interaction in visual analytics:

**Time Engineering:** We discuss temporal implications for user interfaces. In contrast to eager systems, where we simply try to design interfaces that are as fast as
possible, progressive systems offer us design opportunities for maintaining interactivity.

**User Roles:** We think of two concurrent processes: a computer system carrying out computations, and a human observing them. Depending on how often and how much these two concurrent processes inform each other, PDA users can have different levels of involvement in the progression—from merely monitoring the stream of results like viewing an animation to actively steering the progression along a computational path of choice.

**User Tasks:** Managing how these two processes interleave requires users to perform various additional tasks that are not needed in non-progressive analysis setups. For example, users need to gauge the uncertainty of an intermediate in-progress result (see also Chapter 6). They also may want to refine the search space of a progressive analysis process after making an observation in an intermediate output.

**User Focus:** Different motivations can be behind the use of PDA. Some users may employ the progression to come to a speedy conclusion about a dataset under investigation, while others may use the progression to interactively explore differently parameterized computations by observing and comparing their progress while they run.

**User Complications and Biases:** Given the greater influence of the user over the computational process, users' subjectivity and biases have a higher potential of affecting the analysis (see also Chapter 9). This includes, for example, the possibility of cherry-picking results by terminating the computation just at the right moment while it is showing a desired output.

Our goal is to better understand how and when a PDA system can be useful (or harmful) and how different PDA techniques can be used to address different user needs. This characterization is adapted in part from Micallef et al. [197]. We believe that articulating this set of personas and tasks can help with both the design of, and research on, progressive systems. The aspects identified and discussed here might be useful for:

* application designers, to identify potential user needs; to consider users taking different or supplementary roles to their current one to benefit from the full scope of PDA techniques; and to explore alternative solutions afforded by PDA to inform their final proposal;

* software engineers, to take inspiration from the literature linked to the PDA usages specific to each role, to derive the best technical solution to support progressive tasks for their respective users;
* domain experts and end-users during a collaborative design process [337] with PDA designers to identify and discuss the potential pitfalls and determine the actual risks of such biases, their impact, and ways to mitigate them;

* PDA system designers to provide frameworks for PDA designers to ensure that PDA systems are evaluated with respect to the different types of usage by covering relevant user roles and tasks; and to propose to software engineers PDA workflows providing adequate methods and tailored visual details for typical progressive usage scenarios specific to an application domain.

We conclude this chapter by bringing together these themes in a single usage scenario showing how these concepts can guide a designer in charge of improving a crisis management system.

## 7.1 Time Engineering for Human Factors

We begin with a broad observation about building interactive tools. One major goal of PDA is to ensure users can maintain an interactive experience, even across large datasets and complex computations. To do so, it is valuable to understand what “interactive” means.

A user will perceive an interface as “interactive” if it responds in under a second; an interface that doesn’t show updates or changes within ten seconds will likely seem frozen [42,180]. Different interface designs can build expectations of responsiveness: a visual progress indicator can help show updates, but will seem very slow if it does not make visible progress; while a numerical indicator can help maintain an appearance of change. In contrast, a user might expect a slider to respond interactively, while they might be prepared to wait for a response to a button press [281].

Interface design also drives users’ expectations with the system. An interface that responds quickly invites exploration, but also quick judgment; it also risks having too many things change too quickly. Unless the visualizations are stabilized (see Section 5.2.1), the rapid changes may disorient the user. Conversely, an interface with a higher latency encourages a user to be thoughtful about firing off a new query, but therefore discourages freewheeling exploration. With high enough latency, a user is likely to switch tasks, multitasking while they wait for a slow job to finish.

Progressive Data Analysis aims at handling these time constraints by presenting meaningful partial results to the user early and frequently enough before full completion—and the user can, in turn, respond concurrently, steering or tweaking the computation as it runs. This makes for a tighter, more interactive analytic loop.
## 7.2 User Roles

At the most basic level, while a user is in the process of carrying out data exploration with a Progressive Data Analysis system, they will issue a series of queries, then wait for the system to produce results. There are a number of ways that a PDA system can allow for increased user involvement, from being able to indicate the internal state of a computational process (e.g., stalled vs. running) to actively steering the computation toward subspaces of interest while it is running (e.g., data subspaces, parameter subspaces) [207]. Here, we draw a distinction between three user roles characterized by their increasing involvement in the PDA interaction loop. These roles range from the more passive *Observer*, to the goal-oriented *Searcher*, all the way to the free-reigning *Explorer*.

### 7.2.1 Role 1: The Progressive Observer

The Observer's main interest is in monitoring a progressive process, often without having any knowledge of that process or of PDA as an underlying concept. Thus, the Observer mainly wants to stay informed about the state of the computation for confirming its aliveness (R9) [207], for estimating how long it will take until it is finished (R10), and for establishing a sense of provenance of the result (R8) by seeing it unfold. An Observer might, for example, watch a progressive treemap [252] being refined with more data over time. The ability to watch the evolution of the treemap from a single top-level rectangle that is then further and further subdivided instills an understanding of the generation process, gives an indication of its progress, and helps the user learn about the hierarchy as internal nodes are drawn before their children. Tracking this process lets them understand the data they are visualizing, the algorithm being used, and gives them a continuing sense of progress.

An Observer's expectation of the underlying PDA process is a steadily improving output that arrives at a predictable end. This is familiar from applications that show gradually-refining images, or from loading progress bars. To support an Observer in using PDA without an extra learning curve for understanding its progressivity, a PDA system can be tailored to meet the Observer's expectations by the following affordances:

A. Reduce visual complexity, fluctuations, jumps, flickering, or any other indication of the underlying process not smoothly and predictably producing progressive outputs—in particular if these are induced by external influences (garbage collection, memory swapping, etc.); they also relate to design requirements R3 and
R4 (see Chapter 2).

B. Use commonplace metaphors and familiar abstractions that are already part of the interface—e.g., that of a progressively loading “online map application”, as we often see in large graph visualization [213].

C. Maintain the users' mental map, e.g., by introducing anchors [16] or by slowing down fast computations [314].

### 7.2.2 Role 2: The Progressive Searcher

The Searcher's main interest is using PDA to quickly find an answer to a concrete question or a solution to a particular problem in a large amount of data and information. To that end, the Searcher usually comes with a specific, run-time-intensive query that shall be processed in a resource-conscious way. For example, this resource may be time, when basing an urgent decision on the query result. It may also be usage of computing infrastructure and the incurred costs for running it (e.g., electricity, network traffic, cloud billing), which shall be cut down to the necessary minimum. Hence, the Searcher is after a trustworthy intermediate result that is just good enough for the purpose for which it is needed, permitting them to cancel the running query, saving the system a costly exhaustive search. The query is not confined to the data space, but can also entail a search among algorithms and parameters to quickly identify promising computational models. Thus, Searchers use PDA mainly for terminating processes mid-run in an informed manner—either to dismiss erroneous queries or to terminate the progression ahead of time once a good enough result is computed. Both of these can be leveraged to guide the search process by subsequently eliminating bad search paths in order to reduce the search space, effectively speeding up the overall search spanning multiple queries. A Searcher's expectation of the underlying PDA is that of a step-wise process that produces constantly updated results, which can be terminated at any time to readjust the computation or use its intermediate result instead of a final result for subsequent analytic operations. To facilitate the needs of a Searcher, a PDA system can employ the following affordances:

A. Reflect—maybe even emphasize—any fluctuations, jumps, and other indications of the underlying process to make the user aware of possible issues with the query or model (also relates to R5);

B. Indicate uncertainty in a domain-specific and visual manner that allows judging of the reliability of the intermediate results [8, 10] (R7, see also Chapter 6);

C. Provide the option to subdivide large queries or model runs so that each sequential step in them can be run and checked individually for success.
**D.** Provide the option to parallelize queries or model runs (see Section 3.4), yielding an ensemble of progressively refining outputs that can be compared for their agreement [238].

### 7.2.3 Role 3: The Progressive Explorer

The Explorer's main interest in PDA is to get to know their dataset rapidly, and to explore questions that they may not have formulated clearly yet. It is often not a single result in which the Explorer is interested, but rather in gaining a comprehensive understanding of data and process. They may wish to get to know distributions of their data, or understand how different dimensions relate to each other. Hence, Explorers use the intermediate results of PDA to orient themselves and to decide in which direction to steer their “tour” through the data or parameter space, swiftly adjusting queries, views, runtime constraints, or all three simultaneously [66] based on what they observe in the intermediate outputs.

Their expectation of PDA is that of an open, malleable process that can be redirected, re-parametrized, re-prioritized, refocused, and interactively perturbed. Explorers are aware of the progressive nature of the underlying process, as well as the fluctuations and discontinuities their interactive adjustments introduce into that process. In fact, it is often these repercussions of their actions that they are interested in, as these may reflect underlying data properties or functional dependencies. To support such an involved use, PDA systems can offer affordances like:

A. Expose details and parameters of the PDA system to the user and make them adjustable on the fly;

B. Incorporate summaries, statistics, and overviews to provide a global context for evaluating current assumptions and insights, if possible automatically [141];

C. Allow possible changes in a What-If manner that branches off alternatives and compares them later [1].

Users might switch roles during a PDA session—for example, a Searcher might start off wanting to run a quick progressive query, before discovering that the running query does not report back sensible intermediate results. That might prompt them to shift to an Explorer role to test different parameter settings on the fly, to “help the query along”. **Research Agenda:** How to recognize the need for such a switch and how to facilitate these switches is an open research question. In essence, a PDA system should only expose as much complexity and functionality to the user as is currently needed, but how to do this best and as seamlessly as possible is not a settled question. Does the Observer automatically become a Searcher the moment they start

<figure><img src="image_68.png" /></figure>
interacting with the progressive outputs? Do switches between user roles only go in one direction (e.g., from less to more involved in the progression) or are there also scenarios in which it would make sense to “down-grade” an Explorer to an Observer if they have not interacted in a while?

From the perspective of designing PDA systems, increased user involvement can incur greater computational overhead. This overhead stems from providing the necessary interactive flexibility to change and re-parameterize the progression on the fly, as well as from ensuring that the progression can always be interrupted. Many of these additional complexities of progressive data handling and computations are discussed in Chapter 3 and Chapter 4. When designing a PDA system, it thus makes sense to strike a sensible balance between desired user involvement and acceptable overhead.

## 7.3 User Tasks

In general, a PDA approach can support the same user tasks as described in the visual analytics (VA) literature (e.g., [35] or [263]). The progressive nature of the process might influence and change a user's workflow. These changes might range from expanding the task scope to understanding the semantics of tasks differently.

A certain coupling arises in this approach between an understanding of the data (e.g., compare results of analyses, explore the data overview) and an understanding of the underlying progressive process (e.g., comparison between partial results, evaluation of uncertainty of the progression, exploration of a succession of partial results). This coupling motivates the reformulation of these tasks in a way that respects the progressive nature of the process but also becomes a primary concern of the analysis.

For example, tasks that usually have clear answers are transformed into probabilistic queries: “is column A taller than column B” becomes “how likely is it that column A is taller than column B”? [85]. This, in turn, introduces the additional task of evaluating uncertainty: “Is it certain enough that A is taller than B to proceed with our analysis?”

In the following, we give a set of characteristic analytic tasks for the different PDA user roles and their respective affordances (see Section 7.2). These advanced tasks come in addition to the basic ones required to deal with the progressive process—e.g., running, pausing, terminating the computation, or increasing, decreasing the step size/chunk size, judging the overall quality of intermediate results, or identifying
what has changed between visual updates.

**Research Agenda:** None of the tasks below directly explore the meaning of progression for the classic visual analysis tasks. As such, it is still an open question how to adapt Shneiderman's Visual Information-Seeking Mantra [282] "Overview first, zoom & filter, details on demand." for progressive visualization. In PVA, we do not have a complete overview of the data to start from, let alone any details that may come only at the very end of a progression. How do we best support visual information-seeking on incomplete, intermediate results?

<figure><img src="image_69.png" /></figure>

### 7.3.1 The Observer's Analytic Tasks

Although the Observer's role in PDA is typically passive, they will still aim to achieve analysis tasks—be it to simply monitor the progression to understand the build-up of a large information space [253], or to track individual patterns such as forming clusters, which are also important tasks in streaming data scenarios [251]. Specifically, we note that an Observer would use PDA to perform the following actions:

**T1. Ascertain suitable quantity of processed data and stability of the computation results (RO1-A)** for subsequent analysis steps. In situations where minimally viable results need to be available quickly, it might be helpful to monitor the sequence of progressive results to ensure these scenario-dependent constraints are met [8, 10].

**T2. View large information spaces progressively (RO1-B)** as complex datasets, computation results, or visualizations are built up incrementally. This kind of monitoring of the build-up of complex results allows for forming and keeping a train of thought alongside the running progression, instead of being confronted with a possibly cluttered end result in one go. This task is supported, for example, by Progressive Parallel Coordinates [254] that build up step by step into the full and usually cluttered view showing all the data.

**T3. Understand an algorithm and its inner workings (RO1-C)** by observing its output and internal state as it runs, for instance visualizing a sorting algorithm [187]. This is important when ensuring the provenance of computational results, which ultimately builds trust in the otherwise hidden computational part of the visual analytics process.
### 7.3.2 The Searcher's Analytic Tasks

Searchers may perform all of the Observers' tasks to monitor the progress of their search. In addition, they actively influence the progression through their queries and parameter adjustments, which requires carrying out additional tasks. As the Searchers' analyses involve a specific question to be answered, their tasks reflect the notion of a sequence of coupled actions and reactions in the sense of a dialogue between analyst and progressive process, as put forth by Turkay et al. [304]. We list four common tasks for the Searcher:

**T4. Analyze an approximate or partial result of a costly query (RO2-B&D)** as one may not be able to wait for the arrival of the final result [89]. This analysis should be done with the explicit knowledge that the analyzed result is uncertain and the actual final result may differ.

**T5. Refine search space based on the intermediate results provided by the progression (RO2-D)**, so as to make the progressive results more meaningful by targeting a given parameter or data subspace of interest [66, 123]. This task aims to specify a search objective in a number of quick, iterative steps based on early outcomes of the progression in order to yield more pertinent partial results earlier.

**T6. Compare different executions of the computation (RO2-A&C)** to analyze the effects of different parameter settings or input data on a computational method, so as to find the search term or the parameterization of the search that yields the best results [181].

**T7. Stop a costly progressive computation not showing promising results (RO2-B)** to stop a computation early when trying to perform a costly operation when there is no hope of the operation yielding satisfying results, saving time and energy.

### 7.3.3 The Explorer's Analytic Tasks

Explorers must be able to perform all the tasks of the Observers and the Searchers. But since they also need to actively steer the progression and interact heavily with the underlying progressive process [210], they also need support in the following tasks:

**T8. Gain an overview of an unfamiliar information space (RO3-B)**, as often Explorers are dealing with datasets or parameter spaces for the first time. Hence, they need to be able to get a quick first glance at the big picture to orient themselves before steering the analysis in a particular direction [275]. This may
involve visualizations of distributions of different dimensions, or the use of a
"breadth-first" style progression of samples of the full information space typical
of cluster visualization of search results [45, 46].

**T9. Identify possibilities for furthering the computation by integrating the user's tacit knowledge or preferences (RO3-A)** at different stages of the on-going computation. This might involve, for example, influencing an otherwise unsupervised algorithm by interactively adding tacit knowledge [269] in clustering or considering *Must-Link* and *Cannot-link* constraints [320], or it might involve interactively sampling a high-dimensional energy function through its low-dimensional projection [72].

**T10. Investigate alternative scenarios (RO3-C)** by branching off the analysis into What-if scenarios, pursuing them in parallel, only to then decide for the better one in the end or to merge their results [325]. Because of the progression, this can actually be done mid-computation; as of T7, less fruitful analyses can be stopped early.

7.4 User Focus

Due to long execution times often inherent in eager visual analytics, it is common to
separate the visual analytics process into two stages: a planning phase, in which the
analytics process is planned in the *algorithm space* by choosing and configuring the
computational methods, models, and parameters; and an execution phase, in which the
configured analysis workflow is carried out in the *data space* [338]. This separation is
so ingrained in current practices that it is only explicitly mentioned in a few ambitious
cases aiming to combine both, e.g., [165, 268]. This distinction is less relevant in
PDA, and users can and should switch seamlessly between investigating the data
and adjusting the algorithm while the analysis runs. Yet because PDA increasingly
blurs the lines between these two analytic foci, considering them explicitly for the
design and evaluation of PDA systems becomes even more important. Mülbacher *et al.*
has proposed the notion of *entity of interest* [207], which distinguishes between
the execution of a computation and that computation's results (intermediate or final).
In that spirit, the following classification distinguishes between the data being the
focus of the progressive visual analysis, or the algorithms and the process of running
them.
7.4.1 F1: Focus on the Data Space

When focusing on the data, analysts want to make use of PDA for analyzing their
data without necessarily having to understand the internal workings of the progres-
sive algorithms. This means that decisions about chunk size, feedback about the
stability/certainty of the intermediate result, potentially setting “progressive guards”
etc. that require understanding the underlying progressive processes, are not within
the scope of the Observer.

In the simplest case, the Observer (RO1) can **Monitor the Data (U1)** for staying informed about an ongoing background process in the data space—whether it be a computation or a data transmission. This information includes, for example, the progression's aliveness and progress. A prime example of this kind of use is *visual sedimentation* [132], which renders otherwise invisible data updates as a trickling stream of particles settling down into a preliminary result.

This communicates the aliveness of the background process, the speed at which
the data comes in, as well as the fact that the current visualization is not yet final.
Building up a visualization in such an animated manner can also be used to mitigate
the problem of cluttered visualizations. For instance, a thoughtfully prioritized
progressive loading of different predetermined aspects of a data set (e.g., outliers or
subtle trends) can ensure that such data aspects are shown during intermediate steps
before they disappear in the clutter of the full visualization [253].

The Searcher (RO2) can **Query the Data Progressively (U2)**, to query a very large data set when they are not able to wait for the timely and costly data retrieval computation to return the accurate results. Because PDA makes intermediate results usable and explorable as if they were already complete, the searcher can start inspecting query results as they appear. The way in which the Searcher zeros in on some parts of the data (e.g., through zooming, panning, or selection) while disregarding others data subspaces can then be used to refine the query to better reflect the user interest expressed in these actions [66, 125].

The Explorer (RO3) can **Explore the Data Progressively (U3)**, they make use of PDA to provide an overview even of large information spaces that refines over time and enables early interaction, such as zooming into regions that seem particularly promising. This, in turn, can direct the progressive computation to the parts of the space that the user would like to explore further [241]. Such user interaction not only speeds up the computation by focusing it on the data subsets of interest but also supports the user in gradually building a mental model of the data and forming hypotheses. PDA systems enabling this form of interaction have proven
to be successful for exploration of data subsets in Twitter data [16] and patterns
in a large set of medical event sequences that are progressively revealed by the
computation [293]. Showing provenance information, i.e., meta-information about
the simplifications made to the current intermediate results, is important in allowing
the user to make more informed decisions about which parts of the data space is
worth exploring and which could actually be pruned [207].

7.4.2 F2: Focus on the Algorithm Space

When focusing on the progress of the algorithm, analysts aim to improve the results of the progressive analysis.

The Observer (RO1) can **Monitor the Computation (U4)**, aiming first and foremost to gain an understanding of the inner workings of a computational process. To this end, the absolute progress of a process can be visualized sequentially and in real-time in the form of an algorithm animation [155]. In visual analytics, animations of complex network layouts and data clustering algorithms are routinely used to help users understand and tune their parameters. Similarly, it is possible to smoothly display the evolution of complex algorithms and to observe, for example, the inner workings of a neural network, such as the dataflow between input, hidden layers, and output [288].

The Searcher (RO2) can **Adjust Algorithm Run-time Parameters (U5)**, interrupting the computation, changing parameter settings, or swapping out entire computational modules or models. They can evaluate new algorithmic configurations by test-driving them on datasets with known ground truth in order to find one that satisfies the given computational objectives. In this case, the user can run multiple executions of the same progressive computation using different parameter sets, compare their intermediate results, and successively terminate executions once it becomes obvious that they are not performing according to the analyst's expectations [11]. A similar approach can also be adopted when debugging an algorithm to, for instance, compare the results of different rule execution sequences as the rules are dynamically executed [308]. **Research Agenda:** When the Searcher runs a black-box or complex model as during training of a deep neural network classifier, it is not trivial to identify the leading cause of the change in the progressive outcome in order to determine how to adjust parameters or which module must be corrected in priority [231]. Various explainable approaches and techniques [7, 264] could be explored to guide the Searcher in making these adjustments.

The Explorer (RO3) can **Explore the Algorithm at Run-Time (U6)**, that is,

<figure><img src="image_70.png" /></figure>
browsing through and experimenting with the multitude of process behaviors as they result from different algorithm choices or parameters. A PDA system can make this possible by allowing the user to not only view the inner workings of an algorithm but also interact with it at run-time to further explore performance or stability aspects of the algorithm, and also to steer it through user input. For instance, PDA can allow users to integrate tacit knowledge and preferences into a typical unsupervised dimensionality reduction or clustering algorithm (e.g., Self-Organizing Maps) as it runs, leading to improved cluster results [269]. In other cases, a user may want to explore the parameter space of a computation while it is running, as is the case in interactive flooding simulations where different constellations of water influx and barriers are tested in What-If scenarios [325].

## 7.5 User Complications and Biases

One of the main characteristics of PDA is its ability to increase user involvement in visual data analysis. The user introduces into the analysis process not only creativity, background knowledge, and past experiences, but also personal preferences and the subjectivity of human judgment. Unfortunately, this entails risks: the user may jump to conclusions based on highly unreliable intermediate results, or the possibility of steering away from a seemingly unpromising analysis path that would have yielded important insights later. In this section, we look at four different such pitfalls that complicate the use of PDA by the human analyst.

**Using incomplete results to confirm a preferred hypothesis.** This complication is particularly relevant for the Searcher, who works towards a clear analysis goal for which a desired or “most plausible” outcome may already been known upfront. Given the incomplete and often fluctuating nature of intermediate results in PDA, confirming a desired result can be seen as an exercise in finding the right time to stop the progressive computation. Note that such a misuse of PDA may not necessarily be a conscious act, but can also be a result of *confirmation bias* [188]. This well-known phenomenon captures an analyst’s skew towards finding insights and drawing conclusions that are in line with prior-held personal beliefs. Even if the progression of intermediate results is mixed and also shows outputs that could be used to refute a hypothesis—human users tend not only to ignore evidence that rejects a believable conclusion (*Belief bias* [79]), but also to exaggerate the evidence supporting the preferred hypothesis (*Exaggerated expectation* [319]).

**Research Agenda:** PDA systems could try to mitigate the *confirmation bias* by

<figure><img src="image_71.png" /></figure>
<figure><img src="image_72.png" /><figcaption>Figure 7.1: User Roles (RO1-RO3), Tasks (T1–T10), Focus (F1–F2), and Usage (U1-U6) in Progressive Visual Analytics systems. Usage examples: ¹ et al. 2013 [132], ² Rosenbaum & Schumann 2009 [253], ³ Kerren & Stasko 2002 [155], ⁴ Smilkov et al. 2017 [288] ⁵ Hellerstein et al. 1999 [116], ⁶ Fisher et al. 2012 [89], ⁷ Khan et al. 2017 [156], ⁸ Angelini et al. 2018 [11], ⁹ Urban et al. 2003 [308], ¹⁰ Badam et al. 2017 [16], ¹¹ Stolper et al. 2014 [293], ¹² Schreck et al. 2009 [269], ¹³ Wäser et al. 2010 [325].</figcaption></figure>
supporting the user in carrying out an “analysis of competing hypotheses” [120] before making a decision. For instance, some analytic tools try to make it easy to link evidence confirming or rejecting different hypotheses to the analysis (e.g., [335]); others try to incorporate it as an integral part of the decision process [331]. Another approach is to ensure a certain degree of coverage of the full dataset by an intermediate result [322] before the option to terminate the progression becomes available to the user.

**Read something into incomplete results that is not there.** The risk of falling prey to *apophenia*—i.e., seeing relations between unrelated things—is already high in eager visualizations [163]. In PDA, that risk can be aggravated as false patterns and visual artifacts can appear in the stream of intermediate results due to the progression and not because they actually exist in the full dataset. This is particularly problematic if the analyst uses these patterns as insights to terminate the computation early and move on to the next analysis step or a decision based on them. There are multiple reasons why an analyst might do so:

* **Overconfidence:** the analyst (e.g., the Observer RO1) overestimates their understanding of the progressive process and its likely outcome (cf. *Overconfidence effect* [203,204]).

* **Confirmation:** the observed patterns “confirm” a prior assumption held by the analyst (e.g., the Searcher RO2) (cf. *Confirmation bias* [188]);

* **Delay discounting:** the analyst (e.g., the Explorer RO3) values an insight gained now higher than the possibility of a different insight gained at an unknown later point (cf. *Present bias* [91,219]);

It should also be noted that frequent exposure of the analyst to intermediate results that are not representative of the final result increases the chances of the analyst considering the illusion as true (*Illusory truth effect* [111, 197] and *Attentional bias* [139]). Similarly, priming and anchoring effects [309], according to which later judgments will be affected by earlier stimuli, might play a more pronounced role in progressive systems.

PDA systems could try to mitigate apophenia in several ways. One might be to encourage users to specify the assumptions they take away from an intermediate result in an explicit form—e.g., as progressive safeguards [141]. For example, a user searching the New York Taxi dataset [214] might specify their belief that “over half of daytime taxi rides go through this six-block region of midtown Manhattan”). This allows the system to continuously check these assumptions and to alert the user if any of them no longer hold. Of course, this only works if the computation is not terminated after gaining the insight on which the user’s assumption is built. One way
to achieve this is to continue the computation as a background process that notifies
the user of any major changes and makes it possible to reverse any analysis steps
completed since [11].

**Waiting for information irrelevant to the intended goal.** In PDA, analysts can easily get distracted by the constant influx of updated results, leading to a paralysis in their decision-making ability. This traces back to the *Information bias* [18], which leads users to believe that more information also leads to more informed decisions— even when this information is irrelevant to that decision. Interestingly, the opposite is often true, as a number of decision strategies and heuristics have actually been shown to work better with less information. This is known as the *less-is-more effect*, and it has been found, for example, when judging the more valuable of two objects [17]— apparently, multi-criteria optimization is not something that comes naturally to the human user.

For example, PDA systems could try to mitigate this complication by showing
density plots that aggregate the data points and do not show them individually. This
way, adding a few individual data points here or there will not create a visual cue
suggesting that there is still a lot of new data with unseen properties worth waiting
for. Instead, the color of the bins in which they are placed will simply turn a slightly
darker shade. This strategy was, for example, applied by Badam *et al.*'s progressive
tweet map [16].

**Misjudging the uncertainty of intermediate results.** The intermediate results shown by a PDA system are incomplete approximations based on only part of the data, as discussed in Chapter 6. Before making a decision based on these intermediate results, the user must judge the uncertainty of the depicted results. Yet if, for example, the progression exhibits fluctuations in the results and generates seemingly ambiguous outcomes, the user might not trust an otherwise good approximation.

Thus, it is important to use effective representations of probabilistic data in PDA
systems. Yet, the way that uncertainty of the intermediate results is presented to
the user will greatly influence any decisions made using this information. User
behavior is likely to be different depending on whether the inaccuracy or accuracy of
an intermediate result is shown, as humans react differently to the same information
being presented negatively or positively. This is known as the *Framing effect* [306],
which finds that humans make riskier decisions when being confronted with neg-
atively framed information. For PDA, this could mean that users are more likely
to steer the progression away from computations whose uncertainty is presented as
inaccuracy—i.e., something undesirable with a negative connotation—than from the
same computation whose uncertainty is presented as accuracy.
PDA systems can try to mitigate this effect by asking users for their rationale and logging it when, for example, terminating a progressive computation or changing its parameters. This would not only improve the reproducibility of the analysis, but it is also known to effectively counter the framing effect by preventing “gut decisions,” which are prone to be affected by such biases [198, 299].

## 7.6 Application Example: Crisis Management

This section brings together the roles, tasks, and biases and discusses them in a practical example. Specifically, we discuss a usage scenario illustrating how the understanding of the human user outlined above can guide the design of PDA systems. We take the example of a designer in charge of improving a crisis management system.

### 7.6.1 The Background: Visual Analytics for Crisis Management and Emergency Response

During natural or man-made disasters, it is critical to get the relevant emergency response at the correct location and time. During such crises, people increasingly use social networks like Twitter to get the latest updates about the disaster event, post about their own situation, or report on possible damages or danger nearby them, asking for or offering help [40, 129, 291]. This online stream contains valuable information as text, pictures or video, which are very useful for humanitarian or governmental organizations to gain early insights from an on-going situation [134]. Beyond aftermath analysis [5], studies have shown the utility of this online content for disaster response and management [215, 257] if processed timely and effectively, but this task is very challenging and is the topic of ongoing research [64].

The Artificial Intelligence for Disaster Response (AIDR) system [135] processes streams of millions of social media data with automatic classifiers trained with crowd-sourced data tagged by volunteers. This system has been enriched with an interactive dashboard [14] (Figure 7.2) to visualize social media data during crisis events. Such decision support systems must facilitate collaborative decisions involving different types of users:

* the **Emergency Rescuer** (ER) leads a team of rescuers in the field, looks for guidance from and reports to the Crisis Responder;

* the **Crisis Responder** (CR) is the application expert able to interpret the meaning of the data and to decide about emergency actions and messages to send to the ERs;
* the **Data Analyst** (DA) is the visual and data analytic expert collaborating with the CR to support timely delivery of relevant automatic models, processed data, and visualizations.

These systems face multiple technical challenges. There are a huge number of messages posted on social media at any time and even more during crisis events, but only a small part of social media data is relevant to a given ongoing crisis event. Interactive monitoring tools can provide rapid access to the most critical and important situational information to support humanitarian organizations or affected people such as *persons, organizations* and *locations* [14].

These tools can be technically complex. All forms of media need to be processed: both images and text can contain critical information. Image processing has been used to extract actionable information (i.e., damage severity assessment) from social media images to get situational awareness during an ongoing crisis event [4, 220]. Natural Language Processing (NLP) techniques have been used to automate the filtering of text data like *reports of injured or dead people, urgent needs, missing persons, critical infrastructure damages* etc., but identifying this information is very difficult because many social media messages are short, informal, and use slang and abbreviations informal language [136, 215].

These models are prone to errors either due to uncertain labels gathered through crowdsourcing, inherent uncertainty until field checking, erroneous model prediction, or irrelevant feature spaces. Time is a scarce resource during a crisis, and can cost lives—but it takes time to train these models, but also to assess that a noisy pattern is actually a signal. Indeed, a processing bottleneck may be human effort: the AIDR system [135] (Figure 7.2) uses supervised classification trained through live crowdsourcing with thousands of volunteers tagging messages and images *in real time* during a crisis event [220]. The CR decides **topic categories** of interest to which they want posts to be assigned by the volunteers, like *reports of injured or dead people, urgent needs, missing persons, critical infrastructure damages* etc. Volunteers tag posts; the posts are used to further train the classifier.

This example corresponds to a progressive scenario. Presuming that all the relevant social media messages have been ingested, there is a definite end result to reach for each event—its characteristics in the real world to guide relevant, timely emergency response. Time is bounded, but computation cost is not. As we extract images and run textual analysis on more postings, the intermediate result should get progressively closer to the end result by processing more and more data.

Note that here, we intentionally frame this as a PDA problem, not a streaming one. In reality, it is likely that additional social media posts might also be streaming
in, adding a temporal component—meaning that the end result might also change dynamically.

We can now look at the roles we established earlier. The Data Analyst (DA) is likely to act as the *Explorer*. The DA is interested in understanding how the algorithms are performing, and may tune the image recognition and NLP algorithms as they learn more about the data. For example, certain scenes and keywords may recur in the postings, and it may be useful to train the system to recognize these keywords and identify them.

The Crisis Responder (CR) is likely to act more like the *Searcher*. They will be looking to answer specific questions: where resources need to be sent, what resources are needed, and where problems are emerging. They will be interested in focusing on the domain of the algorithms, asking the NLP to focus in particular on posts relevant to specific topics.

Finally, the Emergency Rescuer (ER) will look like the *Observer*. They are likely to be interested in the progress of the analysis so that they know when they will be dispatched and will want to see partial results to start their planning process. However, they are less likely to manipulate parameters or alter queries.

### 7.6.2 An Example Scenario: Coordinating Wildfire Response using incoming Twitter Data

We describe a usage scenario where the designer of PDA systems observed a crisis management team using the AIDR system during a dramatic event, and is tasked to provide this system with progressive functionalities. Here is the designer's report annotated with usages (Uj) and tasks (Ti) from Figure 7.1 and issues (ξk) also collected in Table 7.1:

> A wildfire fueled by strong winds has raged for two days in California and is currently intensifying. The fire has reached villas and residences near Malibay County and is approaching Las Esmeralda's densely populated suburbs.

> The CR collects information from ERs in the field and from social media. Automatic processes extract data and images from tweets based on location, text, and image content. The DA sets the model's parameters based on previous wildfire and hurricane historical tweet records, and from the last two days of crowd-sourced image and text tagging.

> At some point, the name “Brad Spears” starts appearing in the top-K persons from messages in the category “critical infrastructure damage”. The CR looks at the related tweets. They turn out to be from press coverage, telling how the hurricane
<figure><img src="image_73.png" /><figcaption>Figure 7.2: The AIDR dashboard prototype [14] has only basic progressive functions (see Table 7.1). It allows for filtering tweets by time (A,D), categories with color-coded confidence level (B), and location (C). The numbers and names of top-K critical entities (persons, locations, organizations) are displayed as bar charts (E), which can be selected and filtered to show only the most relevant messages (F).</figcaption></figure>

ripped off the roof of his Malibay villa. A local ER team is sent on-site (ξ1). The CR takes note of this name and manually filters it out of the displayed results (ξ2). The CR focuses their attention on a collapsed bridge that appears as a likely event in the filtered categories and in the related tweets they read based on the increasing number of occurrences (U2-T4). If the bridge is damaged, it could prevent emergency vehicles from reaching a strategic area to fight the fire. They decide to query for related confounding locations with the same name mentioned in the corresponding messages and are supported with the detailed map of related geo-located tweets (ξ3). Classifier confidence indicators (U1-T1) help the CR decide to redirect a few ERs toward the two most likely locations for further verification. They get a trustworthy detailed report from the second one: "The Linden bridge is damaged but not collapsed. But a multi-story residential building is on fire with about 10 people on the rooftop, and the nearby woods are already on fire." The CR collects information from other ER teams to redirect a squad there and lets the ER leader organize on-site tasks.
Meanwhile, the DA is checking ongoing tweet categorization and NLP techniques, when he spots slow convergence of the training process of the model (U4-T1). Looking at the current errors on the validation set, some labels look buggy (U4-T3) (ξ4). They send new requests on social media to recruit more crowd-sourced tagging volunteers in the hope of increasing filters' accuracy.

### 7.6.3 The Design Guidance: Identifying Progressive User Requirements for such a Scenario

Analyzing their notes, the designer determined that the CR and DA have a Searcher role (RO2) based on the type of tasks they can achieve with the current system. The ERs, however, are not informed based on a progressive approach. They get their orders from the CR decision without indication of potential uncertainty and alternative options that led to it (Table 7.1(ξ1)). ERs could benefit from being part of the PDA system as Observers (RO1): progressively updated by the system with the certainty degree of concurrent options (building/bridge/critical asset location, severity of the damages) typical of (U1-T1) task, combined with data they would collect in the field (physical obstacles, local risk conditions, asking more relevant questions to local eyewitnesses, etc.), the ER team leader could take a better-informed decision on how to manage their team on the spot and provide a faster and more accurate emergency response.

**Research Agenda:** This design process rests upon matching the user tasks (Section 7.3(T1-T9)) with the standard typology of visualization tasks [35], creating opportunities for developing a new typology and taxonomy of visualization tasks and idioms that would better support the graphic and interaction design specific to PDA systems.

The CR would like to black-list messages related to Brad Spears' villa, but current controls only hide irrelevant messages containing this entity with no effect on the actual filtering process (Table 7.1(ξ2)), so the incoming message can still contain messages related to that irrelevant event. A progressive system would modify the filters to make space for more relevant critical entities among the top-K (U2-T5) and steer the filtering processes (U6-T9) in future collected messages as well. The map shows the geo-location of the sender of the tweet message, which may not be related to the one of the event itself (Table 7.1(ξ3)). The CR would benefit from seeing a progressive location of the events (U1-T2) with decreasing uncertainty based on an analysis of the contents referring to the same event using geo-coding and NLP techniques. The CR is otherwise using the AIDR system in a progressive way

<figure><img src="image_74.png" /></figure>
<table><caption>Table 7.1: Comparison of the current AIDR system and its improvement, adding progressive functionalities (Section 7.6.3).</caption><thead><tr><th>Users</th><th>Action/Event</th><th>AIDR</th><th>Proposed PDA functions</th></tr></thead><tbody><tr><td>ER</td><td>Move to the event location</td><td>Get decisions from CR (ξ1) Lack of context leading to non optimal decision</td><td>Get certainty level of concurrent options (U1-T1)</td></tr><tr><td rowspan="3">CR</td><td>Brad Spears' villa is damaged</td><td>Filter on the display (ξ2) No impact on back-end filtering processes and classifiers</td><td>Refine filters (U2-T5) ♦ Steer ongoing processes (U6-T8)</td></tr><tr><td>A bridge collapsed</td><td>Classifier confidence indicators (U1-T1) ♦ Geo-located tweets on a map (ξ3) Not related to the event itself ♦ Analyze partial results (U2-T4)</td><td>Event progressive location on a map (U1-T2)</td></tr><tr><td>Exploring hypotheses</td><td>Not supported</td><td>Exploration role (U3-T8,9,10) (ξ5) Not during the crisis, but relevant in the crisis aftermath</td></tr><tr><td>DA</td><td>Monitoring classification and NLP processes</td><td>Spot slow convergence (U4-T1) ♦ Identify low accuracy (U4-T3) (ξ4) Lack of control and exploration capacities</td><td>Analyze parameters at play (U5-T4) ♦ Refine models (U5-T5) ♦ Compare different executions of the models (U5-T6) ♦ Control of the model features (U6-T9) ♦ Investigate alternative scenarios (U6-T9)</td></tr></tbody></table>

(U1-T1,U2-T4). Still, the feedback (black-listing) and decisions are just annotated on maps and visual indicators, but not used to steer the ongoing processes (U6-T9).

The designer also observed that the DA plays a crucial role in an emergency situation to support the CR. The current interface partially supports the DA in a Searcher role (U4-T1,T3), but the DA's expertise is not fully exploited (Table 7.1(ξ4)). The system could support them to analyze parameters at play (U5-T4), refine models (U5-T5), and compare different executions of the models (U5-T6). The DA could also take an Explorer role (RO2) to have more control over training features (U6-T9) and test hypotheses (U6-T9) during the training of the classifiers so as to get the most out of the tools at the earliest time.

The designer finally assumes that the CR could also benefit from exploring data progressively (U3-T8,9,10).

When inquiring about these potential unforeseen user needs, ERs and DA were interested in furthering these options. However, the CR mentioned that having
possibilities to test different scenarios (T9) as part of the Explorer role is not crucial during the unfolding of a crisis where the focus is on real-time rescue (Table 7.1(ξ5)), but is important to have in the aftermath of an event to better organize future missions. So the CR does not actually need a progressive approach as an Explorer.

As we see in this example, the designer would use our framework to inform their solution and ask questions about the type of support that could be helpful to the users at different times of their missions, actually useful needs they might not have expressed directly. Beyond the initial exploration and collection of the users’ needs, they could refer to the existing literature related to the specific usages (Notes in Figure 7.1) to inspire and inform their technical design and propose the best solution to support these progressive tasks for their respective users.

The pitfalls described in Section 7.5 will also be taken into consideration by the designer and could be discussed during a collaborative design process [337] with the users to determine the actual risks of such biases, their impact, and ways to mitigate them.

## 7.7 Summary

We have laid out a space for thinking about user tasks for progressive analytics. The three user roles—passive Observers, data-based Searchers, and active Explorers—suggest not just different tasks, but different designs. We believe that this distinction lays out a space for future design work that further refines and adapts these different roles to different applications.

In identifying the work done in PDA, we have added another type of analysis loop to the traditional visual analytics loops: where we might have once queried, responded, and refined, now there are new sub-loops around acting on partial results, verifying those results, and steering computation. **Research Agenda:** Just as we have rich knowledge of the requirements around query systems that can produce interactive answers, we now need to learn what the appropriate requirements are for PDA systems. What are the trade-offs between interactivity, accuracy, and timing? When is it worthwhile to produce more refined output, compared to producing responses to users? What sorts of users will tolerate a PDA system that takes longer than a baseline system to reach a final response—but can give partial results much more quickly?

The space of PDA design and understanding how users can take advantage of it can broaden across different areas of visual analytics. Can we take advantage of PDA

<figure><img src="image_75.png" /></figure>
techniques to design dashboards, for example, that make use of smaller sets of data, or
are based on sampled results? How can we take advantage of our insights about bias
and uncertainty to improve our ability to create traditional baseline chart types? And
how can we leverage and amplify the positive effects that active steering brings with
it—e.g., the self-generation effect [65] that indicates that self-generated information
can be recalled better than information that is simply read, or the IKEA effect [217]
that captures that humans place a higher value on outcomes they (partially) created
themselves.

PDA offers amazing opportunities for empowering users in new ways to explore
and understand datasets that previously could not have been analyzed in a visual-
interactive way. This chapter provides a framework for understanding user needs and
building tools that support them.

The attentive reader will by now have noticed that this chapter only speaks of
the user in their singular form. **Research Agenda:** Collaborative PDA scenarios
involving multiple users remain largely unexplored. While data prioritization and
computational steering based on user interaction/interest works well in single-user
settings, it is still an open question as to how to realize similar mechanisms for
multiple users with different user interests, possibly even different user roles. Can
this be achieved with a joint visualization, or should they each have their own display
giving them their own tailored view on a joint progression? Or does each user even
run their own tailored progression in the background? These questions are open to
further investigation in the future.

<figure><img src="image_76.png" /></figure>
# 8 Progressive Methods in Machine Learning

<table><tr><td>8.1 Introduction</td><td>132</td></tr><tr><td>8.2 Motivation</td><td>134</td></tr><tr><td>8.3 Progressive Machine Learning Algorithms</td><td>135</td></tr><tr><td>8.3.1 Characteristics of ML Algorithms</td><td>135</td></tr><tr><td>8.4 Examples of Progressive ML Algorithms</td><td>138</td></tr><tr><td>8.4.1 k-Nearest Neighbors Classifier</td><td>138</td></tr><tr><td>8.4.2 Support Vector Machines as Classifiers</td><td>140</td></tr><tr><td>8.4.3 Deep Neural Networks</td><td>143</td></tr><tr><td>8.5 Challenges and Recent Advances</td><td>145</td></tr><tr><td>8.6 Summary</td><td>147</td></tr></table>

Authors Cagatay Turkay, Nicola Pezzotti, Hendrik Strobelt, and Barbara Hammer

## 8.1 Introduction

Having looked at how to carry out Progressive Data Analysis, we now turn to a particular application area that might specifically benefit from progressive data analysis approaches: the field of Machine learning (ML). ML is now the major driving force behind many successful Artificial Intelligence (AI) applications. These applications often involve models that take a considerable amount of skill, creativity, and time to design and train due to the vast space of parameters and data features that need to be decided on during the design of the model, and due to the large volume of the data sets used in their training [324]. This process often involves several iterations and trials until satisfactory outcomes are reached [305]. This laborious model building process is then followed by the model being used in the wild by various stakeholders who need to understand how the model is performing, in particular when faced with the dynamically evolving characteristics of the “real world”. Progressive methods offer significant improvements and enhancements to these different processes. Progressivity can improve the quality of models by empowering the model builders, and support end-users of models in making decisions
while ensuring that the models continue to function over time, hence they are not
subject to any distribution drift.

With the ubiquity of such AI systems, different users interact with them at various stages and mapping these users is an important first step in thinking about the role of progressivity in these processes. Inspired by the user roles in Section 7.2, we can classify ML users into three groups: *Architects*, *Trainers* and *Model Users*. These three ML roles and the different contexts they appear in are illustrated in Figure 8.1. These roles should be seen as archetypes, and thus the same person can cover multiple roles at once.

Most AI applications start with the definition of a task, e.g., classification of images among a number of labels, and a large amount of data is collected that represents this task. A model is defined by a machine learning *Architect*; a researcher that develops new models to solve the defined task. The model is then trained to perform well on the task given the exemplary data, also called the training set. The user responsible for training the model is the *Trainer*; the person that will take a machine learning model and optimize its trainable parameters to achieve good results on the task at hand. In this case, the Trainer defines the objective function for which the model will be optimized, e.g., based on the misclassification rate of the model. The Architect and the Trainer can be the same person. As a matter of fact, this is common during the development of new machine learning models.

Finally, once the model is trained, it is deployed to perform the task in an applied setting, which we refer to as *model deployment*. Once a model is deployed, a *Model User* will interact with the model. Different stakeholders for a given model can be seen as *Model Users*, even if they do not interact directly with it; similarly, a *Model User* may not be aware of the fact that they are interacting with a model. For example, machine learning recommender systems are employed in the many web platforms such as YouTube, Netflix, and Amazon. The *Model User* can interact with the model in a passive way simply by receiving the recommendations, or in an active way by steering the model according to their preferences. Progressivity is important at all stages, although its benefits may vary.

When linking these three roles to the ones depicted in Chapter 7, an *Architect* would largely be an **R3: Progressive Explorer** (with their focus on the algorithm space, **F2**). A *Trainer* would likely take on the role of the **R2: Progressive Searcher** (with a focus on the data space **F1** & as well as the algorithm **F2**).

In a progressive ML system, the *Model User* would be an **R1: The Progressive Observer**. It is important to note that in certain cases, the model user may not be aware that they are interacting with a progressive model since they might be only
<figure><img src="image_77.png" /><figcaption>Figure 8.1: Different users and expectations for progressive machine learning</figcaption></figure>

interested in outcomes, e.g., a streaming service user getting recommendations.

## 8.2 Motivation

Applying machine learning solutions in complex applications requires understanding the impact of the choice of chosen algorithms, their parameters and hyperparameters. This is a challenging task and an increasing research effort is spent on Explainable and Interpretable AI. However, the *Architect* or a *Trainer* usually must wait until a new model is successfully trained before they can begin to assess and interpret the model. This is a lengthy process that reduces the effectiveness of the development of new machine learning solutions. Similarly, a Model User might also want to observe several versions of a model by varying parameters that could be interactively manipulated based on the tacit domain knowledge they might have. Progressive methods would foster such interactive exploration.

Modern models require weeks to be trained on tens, if not hundreds of GPUs that are deployed in expensive cloud environments. A good motivation for the development of progressive machine learning algorithms can be found in the GPT-3 model from OpenAI [37]. It is the state-of-the-art Natural Language Processing model which consists of 175 Billion parameters. It was trained in days and at a cost estimated at over 10 Million dollars. However, the authors report that a bug in the implementation was found only after training, introducing a contamination of the test set. Due to the cost of training, it was infeasible for the authors to fix the problem.

Progressive machine learning methods would compute the results in a progressive manner, returning a first approximation of the results quickly with iterative refine-
ments until converging to the final result [207]. Enabling Architects and Trainers to interact with intermediate results allows early detection of buggy implementations, or suboptimal parameter choices. Architects could quickly refine algorithmic features, parameter choices, and even the underlying machine learning technology. Model Users might benefit from being able to interact with many alternative models and outcomes, allowing for a more in-depth understanding of the implications of the outcomes. Enabling a progressive computation and verification of the model could potentially make these sorts of issues, as reported by OpenAI in the GPT-3 model, less frequent.

## 8.3 Progressive Machine Learning Algorithms

In this section, we elaborate on those characteristics of ML methods that might make them amenable to progressivity, and discuss their relevance for the different users. Like other algorithms, a progressive ML system will need to be designed to have several attributes that are not unlike those we have seen in Chapter 4. Most notably, the ML algorithm must exhibit both *convergence* and *stability* with respect to the resulting quality of the progressive methods. Optimally, the ML algorithms should exhibit *steerability*, allowing the user to interact with the system during processing to influence the methods and parameter choices, as well as the training set or features used, or even to interactively specify external logical constraints.

We will examine the progressive nature and steerability of several standard ML algorithms, such as kNN, SVM, and Deep Learning, and show that developing progressive variants involves a diverse set of challenges related to the areas of data management, ML algorithms, and visualization & interactivity.

### 8.3.1 Characteristics of ML Algorithms

Certain properties are required of Machine Learning algorithms in progressive settings. First, they must provide guarantees on their convergence (see Section 2.2) to a locally optimal solution. While this property is intrinsically required by all ML algorithms, a further required property of the convergence is that it must be stable (see Section 2.2). Therefore, the performance of the model should gradually improve with respect to its objective function with more data, more iterations, or both. This is an important requirement for the application of ML algorithms in a progressive setting; if the algorithm is not stable, the *Architect* and the *Trainer* observing the partial
results will not be able to trust them should they fluctuate wildly over time. Note that,
while we require the algorithms to converge, we do not expect monotonicity for the
objective function that is optimized. In the following, we build on the characteristics
of progressive algorithms outlined in Chapter 2 and present more specific criteria and
characteristics for progressive machine learning methods.

We identified the following criteria one would look for to assess the progressive
nature of an algorithm:

*   **Ability to Work on Partial Data:** The algorithm processes and learns from large datasets. Intermediate models are obtained by taking into consideration only a subset of the total data. An example of this kind of progressivity can be seen in kNN classifiers [90], where the *k* most similar items to the query at hand are searched in a large dataset.

*   **Iterative Computation:** The algorithm is iterative in nature and intermediate results or models are generated at every iteration. An example of this type of progressivity is the *k*-means clustering algorithm [186] where, in each iteration, the centroids identifying the clusters are moved according to the data distribution (see the example later in this chapter).

*   **Increasing Quality due to Heuristics or Approximations:** Algorithms may rely on heuristics and/or approximations. The quality of the approximation can be progressively improved while the algorithm evolves. Examples of this type of progressivity are manifold-learning algorithms that rely on approximated *k*-Nearest Neighbors queries [192, 232, 233].

*   **Evolution over Time:** Progressive computations are closely related to the notion that results improve over time. However, for some techniques, time is the only means available for characterizing their progressivity. Continual learning techniques [182, 279], i.e., machine learning algorithms that evolve without predefined datasets to learn from, are an example of these techniques.

Note that ML algorithms may belong to more than one category. An example is the Stochastic Gradient Descent (SGD) algorithm [31] which is used in several contexts, including the training of deep learning models [170]. At each iteration of the optimization, samples that are randomly selected from the data are used to update model parameters. However, the iterative nature of the algorithm is complemented by the notion of the coverage of the dataset. In SGD, the samples are selected so that the dataset is fully covered in a number of iterations that are defined as epochs of training. Multiple epochs are then needed to converge to the local optimum.

Another key feature of progressive ML algorithms is their **interactivity** and **steer-ability**. We define the interactivity of an algorithm as the ability of a user to control
it during its progressive computation by, for example, changing its hyperparameters.

We define *steerability* as the ability to control the algorithm in terms of the local minimum to which it converges.

We identified the following characteristics of an algorithm that enables its interactivity or steerability:

* **Algorithm Selection:** Different algorithms can be selected to train the same machine learning model. For example, several training algorithms have been developed for random-forest classifiers [36, 122]. The user can interact with the model by interactively changing the algorithm used for training.

* **Hyperparameters:** Hyperparameters are crucial for good performance and model generalization. While hyperparameter-tuning techniques can be adopted, as in AutoML [112], a user-in-the-loop approach may allow for a more efficient and effective selection [63].

* **Considered Features:** The user can perform feature selection and engineering and observe, in a progressive fashion, how the choices affected the algorithm at hand.

* **Logical Constraints:** Upon analysis of the data, the user can impose some logical constraints on the data. For example, features can be ignored for sub-parts of the data where they are not informative enough based on prior knowledge of the problem.

* **Model Complexity:** The user interactively controls the model complexity. As an example, the number of neighbors considered by a kNN classifier can be interactively changed and fine tuned by the user to achieve better results given the data at hand.

* **Training Set:** The user can add or remove data points from the training set to control the model performance. For example, the user may identify mislabeled points from intermediate models, which are then removed from the training set.

Note that while these are desired characteristics for an algorithm in a progressive computational environment, they can be difficult to achieve. Moreover, in cases where interactivity and steerability is maintained, there are questions as to their utility. One may argue that steerability is not needed if the learning is performed correctly and according to user needs, but how can one be sure that data is not corrupted and that a method chosen initially will perform as intended? **Research Agenda:** More research is required on this specific aspect of progressive computations for machine learning algorithms.

<figure><img src="image_78.png" /></figure>
**8.4 Examples of Progressive ML Algorithms**

In this section, we elaborate on the characteristics above by introducing three machine
learning algorithms and explaining how well they support progressive computations
in terms of stable convergence, interactivity, and steerability. We have selected
algorithms characterized by different degrees of model complexity with the aim of
providing an overview of the potential of progressive computations in a wide range
of applications.

As a simple example, we have selected a *k*-Nearest Neighbors classifier [90]. This
model does not have a training phase, which is replaced by a look-up strategy in the
existing training set. Therefore, progressive computations are adopted in this look-up,
where several existing methods can be applied. As an intermediate example, we
adopted support vector machines (SVM) [61]. SVMs include a training phase, which
can be performed progressively. Moreover, compared to a kNN classifier, the training
of SVMs requires the selection of a training algorithm and its hyperparameters.
Finally, as our most complex example, we introduce Deep Learning Models, a set
of techniques that in recent years achieved impressive results in several machine
learning tasks [22]. Deep neural networks are complex models with a large number
of hyperparameters. Moreover, the training of deep learning models is very slow,
thus posing challenges in the progressive visualization of their training.

**Research Agenda:** Progressive methods need to be rethought to support the monitoring of the training of very large deep neural networks that are considerably slower to train.

<figure><img src="image_79.png" /></figure>

**8.4.1 k-Nearest Neighbors Classifier**

As a promising method briefly touched upon in Section 4.4.4, we present the *k*-Nearest
Neighbors classifier (kNN-classifier) as a first example of a machine learning algo-
rithm that can benefit from a progressive computational framework. A kNN-classifier
is a non-parametric model that was developed by Fix and Hodges in 1951 [90].

Given a training set (x₁, y₁) ... (xN, yN), where N is the number of training items,
xᵢ ∈ ℝᵈ is the i-th training point with values in d dimensions and a corresponding
class yᵢ, the goal of the classifier, given a previously unseen data point x̄, is to obtain
the corresponding predicted label ŷ. The algorithm searches in the training set for the
k nearest neighbors to the point x̄, where the Euclidean distance is often used as the
metric. Once the k points are collected, the prediction ŷ is obtained by assigning the
label that is most frequent among the neighbors. The user has control of the prediction
power of the algorithm in two ways. Firstly, the bigger and more representative the training set, the easier it is to find a close match for the point $\bar{x}$, thus resulting in a more accurate prediction. Secondly, by changing the number *k* of neighbors used, the user can control the effect of the noise on the prediction. In the extreme case where *k* = 1, the noise in the training distribution, as well as the presence of outliers, may become dominant, thus resulting in a noisy prediction. Increasing *k* leads to a so-called smoother classification boundary, which has the effect of making the classifier more stable. However, this may come at the cost of misclassification, as the decision boundary will be directly effected, an effect that may be extreme when small sub-population of data are considered, i.e., when the size of the sub-population is a fraction of the selected value *k*. Therefore, the best choice of *k* depends on several factors, such as the size *N* of the training data, the number of sub-populations and the required trade-off between precision and recall of the resulting classifier.

In addition to its simplicity, the algorithm is also widely-used because of its easily
interpretable results and superior performance when dealing with relatively low-
dimensional input data. The main drawback with it has to do with the fact that a kNN
query has to be performed for each data point that has to be classified. Compared
with more advanced algorithms like SVM or deep learning-based classifiers, this can
lead to high computation runtime caused by searching the neighbors. In its simplest
form, the search can be executed by searching through all the available data points.
This results in a computational complexity that is linear to the size of the data, hence
$O(N)$ in big-O notation [273]. The computational complexity of the queries can be
improved by adopting advanced algorithms and data structures. For example, by
adopting tree structures the computational complexity of the search can be reduced
to $O(\log(N))$. Examples of these algorithms are the KD-tree [93] or some of its
extensions, which partition the space $\mathbb{R}^d$ into a hierarchy of regions. These regions
are then progressively explored to identify the nearest neighbors. It is observed that,
when the dimensionality $d$ of the data is high, the performance of the algorithms
degrades, becoming even worse than a linear search in the data, an effect know as
the *curse of dimensionality*. To counteract this phenomenon, approximated searches
can be used, where the trees are explored through heuristic criteria that provide
the neighbors with a controllable approximation. An example of this approach is
the FLANN algorithm [208]. Another widely used approach is known as locality-
sensitive hashing (LSH). Here, similar points are placed together in the same *"bucket"*
using appropriate hashing functions. The algorithm has a constant complexity $O(1)$,
but it is an approximation by nature. Given the relevance of providing efficient kNN
search at scale, several libraries have been developed over the years, with FAISS being one of the most notable examples [146].

Given the above description of the algorithm, it should not be surprising that the algorithm has great potential for a progressive computational framework. The key insight here is that the classification can be performed on an efficient and approximate computation of the closest neighbors, an approach that is often used in computer vision [256, 261] or in other machine learning tasks like dimensionality reduction [233]. In case of a suboptimal selection of the neighbors, the prediction will be less accurate and more noisy. However, given the fact that the prediction is easily computed from the neighborhood, the algorithm naturally allows for an improvement of the classification results by progressively improving the set of neighbors chosen. For example, a large set of the training set can be considered when the neighbors are collected. In this case, a progressively larger chunk of the data can be queried, leading to better results. More advanced solutions could make it possible to leverage the data structure used to query the data. All tree algorithms naturally support this, as the neighbors are located increasingly closer to the point $\bar{x}$ as the query progresses. Seminal work on providing a progressive implementation of the kNN-classifier is PANENE, a progressive algorithm for indexing and querying approximated $k$-Nearest Neighbors [142]. PANENE allows updating of the kNN algorithm in a time bounded manner for an interactive representation of the results.

**Research Agenda:** A number of fundamental algorithms, beyond kNN search, may be reformulated as progressive computation and become building blocks of novel progressive ML systems.

### 8.4.2 Support Vector Machines as Classifiers

Support vector machines (SVMs) as proposed by Vapnik constitute particularly powerful machine learning classifiers, combining the principle of error minimization with structural risk minimization while training [61]. Unlike kNN classifiers, they do not lend themselves to an immediate extension toward an incremental learning scheme, and different proposals exist on how to extend classical versions to progressive variants [70, 258], using different principles, as elaborated in the following. SVMs implement nonlinear models which can be shaped to approximate any reasonable underlying function, provided a suitable choice of their parameters and hyperparameters [292]. Their modeling and the derivative of their training algorithm relies on the duality principles of constraint optimization [33]. Hence they offer both, a parametric and a non-parametric point of view: in its primal formulation,

<figure><img src="image_80.png" /></figure>
SVMs constitute parametric linear classifiers in kernel space. That means, they are essentially parameterized by a weight vector for a linear mapping, which is used to classify data. Data are pre-processed by means of a fixed nonlinear function: the so-called feature map which is associated with a kernel. This principle ensures that the resulting overall function is nonlinear in the data space and that universal approximation capabilities result.

Depending on the chosen kernel, however, an explicit representation in the kernel space can require a high (even infinite) dimensional feature space, and an explicit computation of the nonlinear pre-processing might be computationally demanding or even impossible. Therefore, an SVM is commonly phrased via its dual formulation: this provides an expansion of the functional form in terms of support vectors, which are part of the training set, hence this yields a non-parametric representation. The complexity of the dual problem and also the representation of the SVM prescription in dual form typically depends on the size of the data set. Rather than the feature representation, training in dual formulation makes use of the Gram matrix which is associated to the nonlinear feature map and is evaluated on pairs of the given data [271]. Since the dual training problem is convex, convergence to a unique global optimum of the cost function can be guaranteed—hence an iteration of training improves the quality of the result. Furthermore, strong learning theoretical guarantees ensure that an SVM, when trained on ever larger subsets of the training data, provides ever better approximations of the true underlying regularity [61]. Thus, a progressive treatment of SVM by stratifying along the number of iterations of SVM training or along the number of used training samples is possible [70,258].

Yet, the classical formulation of SVMs hardly lends itself to learning for large data sets or efficient progressive analysis for larger data sets: the Gram matrix scales quadratically with the number of given training data. Hence training quickly becomes infeasible both in terms of time and memory constraints in the original formulation of Vapnik. Quite a few approaches have been proposed to overcome this challenge in machine learning, and they constitute interesting starting points for efficient progressive computations. Iterative SVM training processes data in chunks, whereby it heavily relies on the special property of SVMs to represent models in terms of support vectors rather than the full training data; this property enables an intelligent choice of suitable working sets, which guarantees a decrease in the training error over the process of training. These approaches combine convergence of the resulting quality with efficient incremental training [145], enabling efficient steering of the training set and resulting training time, respectively. Another approach approximates the training objective, such that finite core sets can be identified which
steer the training, allowing computation time to be traded for the approximation quality of the optima in this approach [302].

A different line of approximation techniques controls the effort required to compute the full Gram matrix, which size scales quadratically with the number of training data: the so-called Nyström technique offers an efficient low-rank approximation in the dual kernel space [284]. This enables efficient incremental learning schemes in the dual SVM formulation [336]. As an alternative, efficient approximations of the data representations in the kernel space have been proposed such as random Fourier features, which are based on an efficient low-rank kernel expansion, or, more generally, efficient approximations of the nonlinear data pre-processing in the feature space [15, 99, 344]. Such approaches enable a direct training of SVM models on an approximate embedding in the nonlinear feature space by means of a parametric linear mapping. Since linear maps can easily be adapted incrementally, this treatment enables the direct use of incremental linear learning schemes [301]. Yet, while these approximations immediately enable an efficient progression along an increasing number of training samples, it is not clear how a refinement of the approximation can be implemented efficiently for both the Nyström approximation (regarding the choice of data subset at the core of the approximation) and random Fourier features (the Fourier components for approximation). A change or refinement would require an exchange of the data representation or kernel matrix, respectively.

In general, model hyperparameters of batch learning can become model parameters in incremental learning schemes as soon as the complexity and characteristics of the observed data can no longer be reliably estimated based on just a small data sample. SVM training requires the choice of a few hyperparameters: one important hyperparameter controls the trade-off between the training set accuracy and generalization ability of the training objective. Another one, which also controls the smoothness of the function, is the kernel width in the popular RBF kernel. While these parameters are crucial, they can be reliably estimated on smaller parts of the training data when those are representative of the data characteristic, such that their change does not seem necessary for progressive computations. Another crucial aspect, however, is the representation of the data, i.e., the choice of the kernel itself. Provided the data representation is changed, a new kernel representation results, i.e., the question of how to set up such operations so that an efficient reuse of previous computational results is possible in progressive learning remains a challenge.

SVM is typically considered a black-box technique, such that a control of its parameters and hyperparameters widely remains subject of trial and error. Few approaches exist that offer an intuitive integration of expert knowledge into SVMs:
due to its intuitive primal formulation and training objective, it is comparably easy to account for data set biases in SVMs, or to add additional linear constraints or error weighting to the problem formulation. Further, there do exist methods that enable the incorporation of invariances such as rotation or translation invariance into the shape of the kernel function [98]. Such technologies constitute an excellent starting point for the definition of intuitive interaction schemes which enable the user to progressively steer the learning process. Yet, while some constraints can be integrated efficiently, others, such as the choice of the kernel, currently require the complete retraining of the models. Interestingly, this is currently also required for a seemingly simple operation: deleting examples from the training set. While incremental learning is possible for SVMs, it is less clear how to forget parts of the training set if they are progressively dubbed irrelevant by the user.

### 8.4.3 Deep Neural Networks

Deep neural networks (DNN) are multilayered artificial neural networks. Each DNN model is based on a network architecture that commonly describes a nonlinear combination of neurons and layers of neurons [22]. Many types of neurons have parameters, e.g., weights and biases, that are learned during model training. Training is most commonly achieved by using a large amount of data presented to a version of back-propagation [171]. The goal of the training process is to optimize an objective function that describes the task. The training process itself is configured by hyperparameters. After training, the model and its optimized parameters can be used to infer output data for new input data with regard to the model task.

The training process of a single DNN is often time-consuming and requires significant computing resources, memory, and storage. It is inherently progressive because after each batch of training data has been processed, the model and its weights have an updated state. This state can be evaluated and compared to the previous state. In practice, this update evaluation is only done after some significant data has been processed, e.g., many data rows or all training data (one epoch). In many cases, the evaluation includes quantitative measures like loss value or performance on test data. Ideally, these measures should show monotonic behavior during the progression of the training process. In practice, these measures can vary and only show trends. Qualitative comparison of model training progression appears to be an understudied field and should gain more interest.

**Research Agenda:** The integration of PDA into deep-learning frameworks, such as Torch or Keras, is an open problem and will enable advanced applications.

<figure><img src="image_81.png" /></figure>
Training a single model can help in finding a good parameterization for a predefined
architecture and pre-specified hyperparameters. But to optimize for a particular task,
searching for the right architecture and hyperparameters is itself a field of research
that can be described as a progressive approach. In this case, each progression step is
very costly and can consist of the full training of a model for the sampled combination
of architecture and hyperparameters. Common automatic methods decide on the
improvement of quantitative measures to either continue training a specific model
configuration or cancel it. More sophisticated algorithms learn about favorable
architectures and hyperparameters longitudinally across multiple tasks. Model search
and hyperparameter optimization are often not monotonic or deterministic, i.e., not
strictly progressive. We still think that user interaction paradigms for progressive
search can be applied to this process.

The inference process should be quick and consume minimal resources. For many
common tasks, it can be considered atomic, e.g., image classification or sentiment
analysis of a text should only yield a final label. Models that allow generation of
sequences are often auto-regressive, i.e., new predictions are conditioned on previous
predictions. Generation for these models is a progressive method and can be subject
to steering. For example, language models such as GPT2 [246] allow generation of
text phrases, word by word, from left to right. The selection of which word to choose
can be subject to human interference. This interaction can influence the right-side
progression of building the text phrase. It therefore helps to steer the output of a
DNN model in inference mode.

With the recent rise of foundation models, e.g., large language models, interaction
paradigms are shifting. The enormous amount of resources needed for training these
large models from scratch is paid forward to allow future and cheaper fine-tuning on
specific tasks. In addition, a completely new class of task adaptation has emerged:
prompting and prompt-tuning, which enable instructing a model to solve a task using
only the inference mode. The task instructions can either be given as a prefix in
plain text (discrete) or as embedding vectors (soft prompting). Iterations to find
the best prompts can be human-driven (prompt engineering) or automated (prompt
tuning). The potential of progressive analytics remains to be seen, but one area where
it might be found effective is in methods for qualitative evaluation of foundation
model fine-tuning and prompt tuning. Human-controlled prompt engineering and
time-intensive pre-training from scratch do not seem to be very well suited to the
task. An interesting special case of progression that is driven by users can be seen
in large language model training. These models are refined by human feedback
using a method called reinforcement learning through human feedback (RLHF) [53].
Evaluating the improvement by each RLHF step holds some progressive promise.

**Research Agenda:** While RLHF methods are natively progressive, it is interesting to investigate how to steer and verify the feedback process.

<figure><img src="image_82.png" /></figure>

## 8.5 Challenges and Recent Advances

**Research Agenda:** It is possible to report a number of cross-cutting challenges for advancing the progressive machine learning agenda.

<figure><img src="image_83.png" /></figure>

* **Algorithm development:** The progressive nature of the computations means that training is done over batches and should be done with increasingly available parts of the data. This requires incremental learning routines that can adapt to changes in the data [184]. The challenge is to determine how effective models can be built using partial data and with minimal storage requirements. Another fundamental challenge for progressive methods is to be adaptive to and robust against dynamically varying phenomena/concepts that change over time (i.e., non-stationarity). Despite being a common challenge for most ML methods, often referred to as *concept drift* [326] or *non-stationary learning* [296], this issue is particularly pronounced in progressive settings due to the progressive manner of the training process. Progressive algorithms should provide plasticity in adapting to changes but they should do so in ways that are not over-sensitive to variation in the data due to the progressive handling of the data.

Recent developments in online learning techniques [184] explored how some established techniques might be adapted to work in progressive settings [183]. Balancing the stability and flexibility of models in response to different ways that the changes in concepts manifest themselves is another area that has been explored. In addition, progressive solutions such as progressive neural networks [259] offer promising avenues for progressive ML methods. Developed to address problems in transfer learning, these approaches use a model learned in a source domain as an initial starting solution for a new problem domain [62].

* **Model building:** Building progressive machine learning models raises unique challenges during the model-building phase, in particular in relation to parameter selection and the fine-tuning of a model. *Model Architects* and *Trainers* need to make decisions on the design of the model before having access to the full data. For instance, if trial-error procedures are used as experiments to
<figure><img src="image_84.png" /></figure>

assess how the model performance varies in response to particular parameter choices, model builders need to make judgments on certain “early” indicators of performance and assess suitability of parameters based on such incomplete and dynamically varying signals. To further complicate matters, progressivity itself introduces its own parameters, such as rate of convergence or number of iterations, which can have implications on how measures of quality and performance are interpreted. **Research Agenda:** Thus, providing informative and consistent indicators of progress and performance assumes the utmost importance, as well as providing mechanisms to alter the progression process interactively during the training process.

Recent developments in the field of active learning, where a human “oracle” provides feedback to an algorithm on data instance level outcomes within unsupervised learning settings [55], offers the potential to enhance the model building process in progressive settings. In such techniques, early indications of model (un)certainty and quality can be utilized to gather targeted feedback from the user (Architect or Trainer) to guide the model development process during progression. Recent techniques where Generative Adversarial Networks are used to generate synthetic samples to speed up the training process [346], where methods actively learn on data features in addition to data instances [118], and interactive visual frameworks [24], can enrich and strengthen active learning protocols in progressive settings. Interactive visual techniques offer further opportunities to support the model building process by providing approximate solutions that can be steered effectively [233], as well as advanced interactions to explore parameter and feature spaces using progressive visual representations [304]. **Research Agenda:** Such advanced methods of “active learning” can elicit more complex tacit knowledge from people to facilitate more effective steering of models in progressive learning settings.

<figure><img src="image_85.png" /></figure>

* **Human factors:** The increasing complexity of most recent machine learning techniques is now known to be a particular challenge for their users due to issues around interpretability, transparency, and trustworthiness [200, 328]. These issues are exacerbated with notions of progression and uncertainty in progressive machine learning settings. Users of progressive ML systems need to assess the status of and outcomes from a model under such uncertain, dynamically changing contexts. This necessitates the careful consideration of human factors in designing progressive ML solutions. It is vital, for instance, to explore how interpretability of ML outcomes [127] can be supported when
“explanations” are dynamically changing and highly uncertain.

Recent techniques in visualization research provide some good examples of how human intervention can be incorporated even in the training of complex ML models such as Deep Neural Networks [127]. Visual representations that show the stability of some inner structures such as perplexity histograms [231] and aggregated views to reveal relations between parameters and outcomes [178] show great potential. Similar techniques are being applied in different application areas, such as health [167] or transportation [341], to advance our knowledge of how users in different contexts respond to such interactive interventions. Methods to allow investigation of foundation models can reveal progressive insights, especially when used for comparing model snapshots [295].

**Research Agenda:** Further research into how progressive ML methods are used "in the wild" are needed to respond to different needs and diverse stakeholders (see also Section 9.2).

<figure><img src="image_86.png" /></figure>

## 8.6 Summary

With datasets becoming larger and models more complex to design and train, progressive machine learning techniques are likely to be cornerstones in systems where algorithms are in constant interaction with humans, whether it be for learning from humans or for better explaining outcomes. This chapter explored this area of progressive machine learning from the perspective of the humans involved and the characteristics of the algorithms, and presented a number of examples as case studies to illustrate a series of challenges and some promising steps taken in related research areas. Progressivity presents new challenges and exacerbates some existing ones in how people design, train, evaluate, and then use machine learning models. **Research Agenda:** Inherent challenges of progressive techniques involving the online processing of data and rate of convergence become especially important to consider in designing effective algorithms, while issues of quality and uncertainty are key in facilitating functioning interactions between users and the algorithms. We explored several recent exciting areas of research that have begun to tackle these challenges, and expect to see growing activity in all of these and potentially new areas in the development and deployment of progressive machine learning systems. We discussed how recent advances in visualization and interaction research empower various stakeholders in designing, training, and using early instances of progressive machine learning.

<figure><img src="image_87.png" /></figure>
learning techniques, and we expect visualization to continue playing a key role as an
enabler for the development and adoption of progressive systems.
# 9 Evaluation

<table><tr><td>9.1 Scenario and Challenges</td><td>150</td></tr><tr><td>9.1.1 Approaches to Evaluation</td><td>150</td></tr><tr><td>9.1.2 Performance Measures</td><td>152</td></tr><tr><td>9.2 Evaluation at Multiple Stages of the Pipeline</td><td>153</td></tr><tr><td>9.2.1 Data Management</td><td>153</td></tr><tr><td>9.2.2 Algorithms</td><td>156</td></tr><tr><td>9.2.3 Visualization and Interaction</td><td>158</td></tr><tr><td>9.2.4 Human Factors: Perception and Cognition</td><td>163</td></tr><tr><td>9.2.5 Machine Learning</td><td>166</td></tr><tr><td>9.2.6 System Level</td><td>167</td></tr><tr><td>9.3 Summary</td><td>169</td></tr></table>

**Author** Gaëlle Richer, Jean-Daniel Fekete, and Michael Sedlmair

Designing progressive data analysis systems affords several degrees of freedom. Algorithms, systems, and techniques require evidence to demonstrate their feasibility, effectiveness, and usability. While this characteristic holds true for all visual analytics systems, the dynamic nature of progressive systems poses new challenges for the creation of this evidence due to the tighter connections between the two classes of systems involved: visualization and progressive data processing. The approaches to evaluating visualization and progressive data processing systems are fundamentally different and often incompatible. Evaluating visualization systems usually borrows methodologies from Human-Computer Interaction (HCI) and psychology, while progressive data processing utilizes standardized performance benchmarks. **Research Agenda:** Investigating the performance of each class of system individually is near-meaningless; instead, an integrated evaluation must be performed to demonstrate the value of a progressive data analysis system, similar to what is customary in evaluating visual analytics systems [235].

At the highest level, progressive systems offer a natural trade-off: wait time versus quality and confidence in the results. At one extreme is simply waiting for the results, and the task of helping humans with the waiting process is related to wait-time engineering [80, 278] (also discussed in Section 7.1). At the other extreme is the

<figure><img src="image_88.png" /></figure>
temptation to make decisions too quickly, regardless of the quality of the results. This time/quality trade-off can be critical in time-constrained exploration [161] and also important in other contexts, since time is a precious resource that should be used wisely. We want to build interfaces where users can make accurate decisions as soon as they have meaningful results that they can have confidence in—but no sooner.

At a lower level, progressive systems should efficiently manage both human and machine capabilities. Humans have limitations in their attention span: they have great difficulty remaining engaged with long latency, and too many blinking visualizations that have to be monitored can overwhelm their perceptual and cognitive capacities. Therefore, progressive systems should strive to ensure that human attention remains effective. On the other hand, some algorithms are effective but return results that do not comply with human capabilities, such as unstable intermediary results that are hard to track visually. Evaluating solutions that trade speed/quality and are compatible with human capabilities adds further levels of complexity.

## 9.1 Scenario and Challenges

Assuming that progressive systems become commonplace in the visualization & analytics system landscape, we can imagine that a typical evaluation scenario might be to demonstrate the effectiveness of a system, algorithm, or interface to (1) allow something that was previously impossible or (2) improve an existing progressive solution. For the former, case studies can describe the situations and problems that can be tackled now and why they could not be tackled before (e.g., [23]). For the latter, the important point for evaluation is to define the dimension(s) of success under consideration: the ability to make early and confident decisions, the ability to make decisions in a time-constrained situation, to save compute power (green computing), etc.

### 9.1.1 Approaches to Evaluation

Some papers evaluate the utility of a novel progressive technique (with a case study or observational study) or compare its performance against an eager system, i.e., a non-progressive equivalent that performs a complete computation before returning results (with a user-controlled study or algorithm performance comparison). In most cases, existing work targets both the time and the accuracy of user decisions.

In the best case, a progressive algorithm will be the fastest, as in time-series search from Gogolou et al. [102] and Progressive Topological Data Analysis with Vidal
et al. [316]. Will evaluating the speed then be sufficient? If the algorithm is used in a non-progressive context, the speed is sufficient, but in a progressive context it should also be evaluated according to the requirements mentioned in Table 2.1. These requirements are important, but they also introduce concepts that are not well specified, such as: *meaningful* partial results (R1), *structure-preserving* intermediate results (R2), *retaining cognitive workflow* on update (R3), *minimized distraction* during updates (R4), and *cues* for new results (R5). **Research Agenda:** Assessing whether a progressive system meets these requirements will require their authors, and ultimately the PDA community, to clarify these concepts and state that their system implements them fully, partially, or given specific definitions. To support the quantitative evaluation of requirements fulfillment (such as for R1 and R2), there is a need for dedicated quality measures in alignment with human judgments [274].

In general, **Research Agenda:** a first step when describing evaluation goals would be to clarify the contextual properties of the analysis: the data, the human context, and user involvement being considered, and whether the main task is one result (with a sequence of approximations) or of a search/gather nature which outputs an extending list of results, e.g., for exploring frequent sequences of temporal patterns [293].

For instance, regarding the expected stability of intermediate results, to clarify the contextual properties of the data involves assumptions about the bounds of the data (known, unbounded), the data stationarity nature (shuffled or not), and whether the user can steer the computation. In terms of the human context, we need to explain what we expect to be a satisfying result: the level of desired uncertainty and the contextual trade-offs between time and quality. Clarifying the tasks and data is necessary, since a progressive visualization or computation could be such that its intermediate results do not support a task, while its final result does. For example, the progressive visualization of sorted bar charts can be very unstable when bar values are nearly identical, yet may provide a usable final result once the values converge. The finding of an evaluation may greatly depend on the decision-making strategies that are adopted or communicated to users, including the goal trade-off between time and accuracy.

Many existing methodological approaches, such as measuring runtimes, running controlled experiments, and conducting design and field studies, will remain relevant for PDA and PVA. At the same time, new methodological challenges arise from the need to evaluate progressive tasks, such as (1) monitoring the unfolding of a complex process to understand its inner workings and make early decisions (e.g., detection of errors, unsuitability of the process, clear-cut result), (2) refining the scope of an analysis question or steering the computation based on an approximate overview,

<figure><img src="image_89.png" /></figure>

<figure><img src="image_90.png" /></figure>
<figure><img src="image_91.png" /></figure>

or (3) conducting branching or speculative analysis based on intermediate results.
**Research Agenda:** These tasks are challenging to evaluate because they involve a trade-off between wait time and confidence in the results, early-stopping [52], and steering of the progressive process.

**9.1.2 Performance Measures**

Performance measures that evaluate the ability to make early and confident decisions apply to the computation and user levels. The measures of performance for a progressive computation task include:

• bounds on time from start to first *meaningful* results

• time until first *accurate* results

• time until the *final* results

• *stability* or *convergence* of intermediate results;

• frequency of substantial result updates, and interface responsiveness

• relevance of the uncertainty/quality metric.

In the case of a progressive search/gather task (defined in *item 2.1*), intermediate results do not improve but expand, and measures of accuracy translate to measures of specificity and relevance. From a user's point of view, measures of performance also include:

• behavioral and psychological factors (e.g., maintaining attention and limiting fatigue)

• assessment of uncertainty, stability, and progress

• latency, amount, and accuracy of derived insights

• subjective level of confidence in results.

Progressive systems should also be evaluated, when appropriate, against human bias, as well as data and machine artifacts linked to progressive visual analytics, which can cause decision errors. One example we discuss in Section 7.5 is the illusion bias, which describes the lingering effect of a false intermediate pattern on the user, such as a clustering pattern [197]. One example of data artifacts can be the non-stationary dynamic of a sequence of chunks: if the chunks are not properly shuffled, the user might be lulled into a false sense of stable results and derive erroneous conclusions. Similarly, early results may look more certain than they truly are: a low-quality clustering result that depicts an overly prominent grouping of the data might mislead a user into thinking a cluster will be more important than it really is.

**Research Agenda:** The definition of user performance measures beyond time,

<figure><img src="image_92.png" /></figure>
accuracy, and confidence is one of the challenges of evaluating progressive systems. Additionally, user studies are needed to understand the landscape of guarantees from the underlying progressive processes and how they impact user perception, cognition, and decision. For example, what guarantees should be expected regarding latency and error bounds for intermediate results? These questions also relate to how uncertainty (R7) and progress (R9) are visually conveyed.

## 9.2 Evaluation at Multiple Stages of the Pipeline

Evaluation questions and methods take different forms along the visualization and analytics pipeline. In the following, we provide examples of measures of success and evaluation challenges for building blocks of the progressive pipeline.

### 9.2.1 Data Management

Evaluation of data management systems is concerned with the efficient management and distribution of more or less structured files. The criteria listed in Section 9.1 are important in serving queries. But the data management layer is also concerned with preparing the data to improve progressive computations, including indexing, but also more specific types of capabilities related to progressive computation, such as *shuffling* and *properties estimation* as mentioned in Section 3.6.

#### Properties Estimation

When data is queried progressively, data aggregation functions that are used to return point estimates in standard SQL (e.g., mean) can return confidence intervals or probability distributions to express the uncertainty of the running results. The evaluation of progressive queries should be clear about the expected return values computed since maintaining confidence intervals using, e.g., bootstrapping [76] or maintaining a value distribution are expensive operations that impact the performance of the queries and the complexity of the data structure returned.

It could also provide an estimate of the data distribution and various levels of statistics related to the queried data. Providing these can dramatically help the algorithms downstream, and therefore, progressive data management can be evaluated according to the richness of the properties that systems are able to provide to improve their accuracy while answering queries. For example, a web-based data management system can return a streaming CSV file, sometimes applying a simple SELECT filter
on the fly. A PDA application would need to progressively compute the min/max column values over the stream. A visualization of that stream would be unstable since the data scale would change each time a new minimum and maximum value is read from the stream. Such a system would be usable for PDA but would be unstable, and data would arrive in an unpredictable order, probably not shuffled and likely with a heavy trend, slowing down any downstream algorithm. A better system would provide additional capabilities serving the visualization, such as shuffling to avoid trending. But it would also send the min/max values upfront if possible, or, it would do so in a progressive way, faster than the progressive computation on the client would, allowing the visualization to be stabilized faster. An even better system would send distribution or quantile information in addition to min/max to further stabilize the visualization. Most big data tables have outliers that limit the utility of the min/max values and should use a scale based on the [5%,95%] quantiles. We expect the user feedback to be different for these varying levels of service of the PDA system, from a raw to a smarter and richer data streaming strategy. Ultimately, an evaluation should report on the effect of these differences.

## Data Management Evaluations

Battle at al. [19] discuss the problem of evaluating visual data analysis systems from the database and visualization community viewpoints. They mention three levels of evaluation: component, system, and work environment, and suggest a vision for new evaluation methods based on benchmarks and a trace repository.

As a follow-up and implementation of the vision for systems, Battle et al. [21] introduce a benchmark for evaluating interactive visualization applications served by a database. Their benchmark addresses continuous dynamic queries, requiring a latency below 0.1 s, with latency being the time between issuing a request and receiving its response. Their evaluation criteria are *responsiveness* and *accuracy*. Responsiveness assesses whether the returned results are fast enough and whether there are latency violations. They do this using two derived measures: *Response Rate* relative to the latency requirement, and *Average Query Duration*. Accuracy is assessed because, in progressive or AQP systems, “approximate results deviate from the ground truth, introducing error into the resulting visualizations and possibly misleading users” [21]. Accuracy is measured by the *Mean Relative Error*, which is the ratio of the error to the expected true result within a given time period. Finally, performance is also measured by *throughput*, the number of transactions processed per second. For large datasets, their benchmark shows poor performance with traditional non-progressive
database engines, whereas with the VerdictDB progressive database [223] the system
remains responsive and the accuracy is always acceptable.

Eichmann et al. [77] introduce a benchmark for interactive data querying systems—including progressive ones. The paper explores a number of factors for the time to interact with a dataset, including *data preparation time*: the time to load data into the database engine before it can process queries. They separately mention the support of *table joins*, since some systems use it heavily and others do not support it (see Section 3.4). The paper describes a metric composed of 7 measures: *time requirement violated*, *missing bins*, *mean relative error*, *cosine distance*, *mean margin or error*, *out of margin*, and *bias*.

Supporting joins is challenging, as noted in Section 3.4. Procopio et al. [242] discuss the specific problem of progressive joins, implemented using the “Wander Join” algorithm [243]. It is evaluated using the standard TPC-H [300] database benchmark in terms of relative error over sample size on a typical query. This evaluation highlights the difficulty of comparing absolute time in progressive algorithm benchmarks when comparing experimental systems with optimized implementations of non-progressive systems, hence the use of “sample size” instead of time. The behavior of their progressive algorithm is promising, but suffers from the fact that the TPC-H benchmark provides data that is not representative of exploratory data analysis workloads, and their implementation is not optimized.

To summarize, the main evaluation criteria mentioned in the articles are: *throughput*, *latency*, and *accuracy*, with several measures for each of them. In most cases, the evaluation is done using prepared datasets, i.e., indexed and prepared for fast shuffling. Since data management research relies heavily on benchmarks rather than ad-hoc datasets, the evaluations are performed on traditional TPC-H benchmarks or newly gathered benchmarks based on user traces. Unfortunately, both of these have flaws: TPC-H is not designed to be representative of an exploration workload; and the new benchmarks are not yet standardized (nor particularly diverse in their use patterns). **Research Agenda:** It would be very useful if more diverse benchmarks were developed with both representative data distributions and queries.

It is less clear how to evaluate the additional capabilities of data management
systems for progressive applications, which can greatly influence the performance
of analytical pipelines, as described in Section 3.7: in-situ systems allow process-
ing of raw data immediately without a long ingestion process, as well as bi-level
shuffling [50].

Other aspects of progressivity in data management have yet to be evaluated from a
data management perspective, such as *query steering*. However, query steering has

<figure><img src="image_93.png" /></figure>
<figure><img src="image_94.png" /></figure>

been evaluated from a user perspective. Selective Wander Join [242] implement query steering through importance sampling, driven by weights on the different groups in the query that can be interactively adjusted. They evaluate this steering capability at the system level, in an expert user study, rather than in the broader context of a progressive database system.

**Research Agenda:** More work will be needed to devise new evaluation methods for several aspects of progressive data management, in particular regarding human factors.

## 9.2.2 Algorithms

Evaluation of algorithms in the analytical part of the pipeline, or even in the visualization part for network layout or multidimensional projections, is concerned with (cumulative) resource usage and time to the final result. Like online algorithms, progressive algorithms can be evaluated with *competitive analysis* [30], comparing their time and memory consumption to their eager version [48]. They are also evaluated with other criteria specific to the progressive setting:

1. time to early meaningful results

2. latency between the intermediate results [142]

3. accuracy and precision or uncertainty/quality of the intermediate results [206, 304] for algorithms computing one result, or

4. recall and precision for algorithms searching for many results.

As introduced in Section 2.3, progressive algorithms can be split into two groups: *progressive-in-chunks* algorithms that return one result computed progressively—i.e., a result is not only a literal, but can also be compound values such as a vector, a matrix, or a table—and *progressive-in-iterations* algorithms that search/gather multiple values progressively. We discuss these here separately.

**Computing One Result** In eager algorithms, the main evaluation measures relate to accuracy (how close a given set of measurements are to their true value), precision (how close the measurements are to each other), computing time, and consumed resources. Progressive algorithms that compute one value can be sensitive to *data stationarity*. Therefore, papers on progressive algorithms need to specify the assumptions they are making or take counter-measures to continue working in degraded environments. Progressive algorithm evaluation borrows methods from online algorithms and streaming algorithms. Online algorithms are usually evaluated using *competitive analysis* [30]. Streaming algorithms are often evaluated according to
their low memory requirements, in addition to their accuracy and speed [212]. While competitive analysis is informative for progressive algorithms, it is not sufficient; other properties are also critical, such as the real-time constraints and steering capabilities. As for streaming algorithms, they are evaluated with strong assumptions of data stationarity, which are not always simple to enforce for progressive computations. Additionally, progressive algorithms should assess the quality/uncertainty of their results. **Research Agenda:** Therefore, there are opportunities for continuing to develop methods to articulate assumptions and evaluate progressive algorithms.

There are several examples of the evaluation of progressive algorithms that compute one result. An interesting example is Xin *et al.* [48], who evaluate progressive 2D sampling for scatterplots with several methods. These use competitive analysis, comparing the quality and time between the static version and the progressive version. They also compare running the static version frame by frame to the progressive version, trying to be as stable as possible between frames. The results show that the progressive version is both faster and more stable, but accumulates errors to maintain stability. This error can be shown to the user, who can decide to interactively recompute the sampling to optimize it rather than keeping it stable (requirements R2 and R13). A few other algorithms [142, 293] consider interactive interventions to allow the user to choose between accuracy and stability. **Research Agenda:** It is not clear how interactive interventions should be managed in progressive algorithm evaluation.

Overall, evaluations of algorithms focus on time and accuracy, but they start from different assumptions (data fully loaded, kNN fully computed, stationary data, static vs. dynamically filtered data). The results are presented with absolute time or number of iterations, and an iteration's meaning should be formally specified to be reproducible. Finally, several algorithms provide interactive methods to allow the user to trade stability for quality; such user interventions make it more complex to evaluate the algorithm.

**Searching/Gathering Multiple Values** A progressive search/gather algorithm returns a list of results that grow or improve with time (item 2.1). For a simple database query, more results will come with time. In eager algorithms, the main evaluation measures are related to precision (the fraction of relevant instances among the retrieved instances), recall (the fraction of relevant instances that were retrieved), computing time, and consumed resources. In PDA, the quality is also related to completeness and to the probability of finding more relevant results by waiting for more. In data mining, searched/gathered results may be more or less interesting (frequent or

<figure><img src="image_95.png" /></figure>

<figure><img src="image_96.png" /></figure>