Linked visualisations via Galois dependencies
Extended paper with additional supporting material
Roly Perera

The Alan Turing Institute

University of Bristol

Minh Nguyen

University of Bristol

Tomas Petricek

University of Kent

The Alan Turing Institute

Meng Wang

University of Bristol

§ INTRODUCTION

Techniques for dynamic dependency analysis have been fruitful, with applications ranging from information-flow security <cit.> and optimisation <cit.> to debugging and program comprehension <cit.>. There are, however, few methods suitable for fine-grained analysis of richly structured outputs, such as data visualisations and multidimensional arrays. Dataflow analyses <cit.> tend to focus on analysing variables rather than parts of structured values. Where-provenance <cit.> and related data provenance techniques are fine-grained, but are specific to relational query languages. Taint tracking <cit.> is also fine-grained, but works forwards from input to output. For many applications, it would be useful to be able to focus on a particular part of a structured output, and have an analysis isolate the input data pertinent only to that substructure.

This is a need that increasingly arises outside of traditional programming. Journalists and data scientists use programs to compute charts and other visual summaries from data, charts which must be interpreted by colleagues, policy makers and lay readers alike. Interpreting a chart correctly means understanding what the components of the visualisation actually represent, i.e. the mapping between data and visual elements. But this is a hard task, requiring time and expertise, even with access to the data and source code used to create the visualisation. In practice it is easy for innocent (but devastating) mistakes such as transposing two columns of data to go unnoticed <cit.>. Since visualisations are simply cases of programs that transform structured inputs (data tables) into structured outputs (charts and other graphics), general-purpose language-based techiques for fine-grained dependency tracking should be able to help with this, by making it possible to reveal these relationships automatically to an interested user.

§.§ Linking structured outputs to structured inputs

First, interpreting a chart would be much easier if the user were able to explore the relationship between the various parts of the chart and the underlying data interactively, discovering the relevant relationships on a need-to-know basis. For example, selecting a particular bar in a bar chart could highlight the relevant data in a table, perhaps showing only the relevant rows, as illustrated in introduction:data-linking. We could certainly do more and say something about the nature of the relationship (summation, in this case), but even just revealing the relevant data puts a reader in a much better position to fact-check or confirm their own understanding of what they are looking at. Indeed, visualisation designers sometimes create “data-linked” artefacts like these by hand, such as Nadieh Bremer's award-winning visualisation of population density growth in Asian cities <cit.>, at the cost of significant programming effort. Libraries such as Altair <cit.> alleviate some of this work, but require data transformations  to specified using a limited set of combinators provided (and understood) by the library.

Fine-grained linking of outputs to inputs, focusing on data for USA (left) and China (right).

What we would rather do instead is allow a data scientist to author analyses and visualisations using an expressive functional language like the one shown in introduction:data-linking, with data linking provided automatically for the computed artefact, as baked-in transparency feature. At the core of this is a program analysis problem: we want to be able to focus on a particular chart element, and determine the inputs that contribute to it. Given the output selection, this is a matter of performing some kind of backwards analysis to identify the relevant data. As well providing a path to automation, framing data linking as a program analysis problem invites interesting questions that a hand-crafted solution is unlikely to properly address. For example, does the union of two output selections depend on the union of their respective dependencies? Do dependencies “round-trip”, in that they identify sufficient resources to reconstruct the selected output? Are they minimal? These questions are important to establishing trust and a language-based approach offers a chance to address them.

§.§ Linking structured outputs to other structured outputs

Second, authors often present distinct but related aspects of data in separate charts. In this situation a reader should be able to focus on (select) a visual element in one chart or other structured output and automatically see elements of a different chart which were computed using related inputs. For example in introduction:vis-linking below, selecting the bar on the left should automatically highlight all the related visual elements on the right. This is a well-recognised use case called brushing and linking <cit.>, which is supported by geospatial applications like GeoDa <cit.> and charting libraries like Plotly, but tends to be baked into specific views, or require programmer effort and therefore anticipation in advance by the chart designer. Moreover these applications and libraries provide no direct access to the common data which explains why elements are related.

Linking visualisations via common data dependencies

Again, we would like to enable a more automated (and ubiquitous) version of brushing and linking, without imposing a burden on the programmer. They should be able to express visualisations and other data transformations using standard functional programming features such as those shown in introduction:vis-linking, and have brushing and linking enabled automatically between computed artefacts which depend on common data. At the core of this requirement is a variant of our original program analysis problem: we want to select a part of the output and perform a backwards analysis to identify the required inputs, as before, but then also to perform a forwards analysis to identify dependent parts of the other output. Moreover, we would also like the brushing and linking feature to be able to provide a concise view of the data that explain why the two selections are linked. Note that the intuition behind the forwards analysis here is not the same as the one we appealed to in the context of round-tripping: there the (hypothetical) question was whether the selected data was sufficient to reconstruct the selected output, whereas to identify related items in another view, we must determine those parts for which the selected data is necessary. As before, a language-based approach offers the prospect of addressing these sorts of question in a robust way.

§.§ Contributions

To make progress towards these challenges, we present a bidirectional analysis which tracks fine-grained data dependencies between input and output selections, with round-tripping properties characterised by Galois connections. Selections have a complement, which we use to adapt the analysis to compute fine-grained dependencies between two outputs which depend on common inputs. Recent program slicing techniques <cit.> allow the user to focus on the output by “erasing” parts deemed to be irrelevant; the erased parts, called holes, are propagated backwards by a backwards analysis which identifies parts of the program and input which are no longer needed. Although these approaches also enjoy useful round-tripping properties characterised by Galois connections, they only allow focusing on prefixes of a structured output, rather than arbitrary substructures, a notion which is not closed under complement. Our specific contributions are as follows:

– a new bidirectional dynamic dependency analysis which operates on selections of arbitrary parts of data values, for a core calculus with lists, records and mutual recursion, and a proof that the analysis is a Galois connection (data-dependencies);

– a second bidirectional dependency analysis, derived from the first by De Morgan duality, which is also a Galois connection and which can be composed with the first analysis to link outputs to outputs, with an extended example based on matrix convolution  (de-morgan);

– a richer surface language called , implemented in PureScript, with familiar functional programming features such as piecewise definitions and list comprehensions, and a further Galois connection linking selections between the core and surface languages (surface-language).

First we introduce the core calculus which provides the setting for the rest of the paper, and which will serve as the desugaring target for the surface syntax presented in surface-language.

§ CORE LANGUAGE

The core calculus is a mostly standard call-by-value functional language with datatypes and records. The main distinguishing feature is the use of eliminators, a trie-like pattern-matching construct that more familiar pattern-matching features like case expressions and piecewise function definitions easily desugar into. (A single core construct allows us to define the semantics of pattern-matching once and defer syntactic considerations to the surface language.) We give a big-step environment-based semantics, which is easier for the backward and forward dependency analyses in data-dependencies, and introduce a compact (term-like) representation of derivation trees in the operational semantics, called traces, which we will use to define the analyses over a fixed execution. Mutual recursion requires some care for the backwards analysis so we also treat that as a core language feature.

§.§ Syntax and typing

Although our implementation in untyped, types help describe the structure of the core language. core-language:syntax introduces the types $A, B$ which include $\tyBool$, $\tyInt$ and function types $\tyFun{A}{B}$, but also lists $\tyList{A}$ and records $\tyRec{\vec{\bind{x}{A}}}$ which exemplify the two kinds of structured data of which are of interest: recursive datatypes with varying structure, and tabular data with a fixed shape. As usual the notation $\bind{x}{A}$ denotes the binding of $x$ to $A$ (understood formally as a pair); $\seq{\bind{x}{A}}$ denotes the sequence of bindings that results from zipping same-length sequences $\vec{x}$ and $\vec{A}$. In a record type $\tyRec{\vec{\bind{x}{A}}}$ the field names in $\vec{x}$ are required to be unique.

The terms of the language are defined in core-language:syntax. These include Boolean constants $\exTrue$ and $\exFalse$, integers $n$, variables $x$, and applications $\exApp{e}{e'}$. Primitives are not first-class; the expression $\exAppPrim{\phi}{\vec{e}}$ is the fully saturated application of $\phi$ to a sequence of arguments. (First-class and infix primitives are provided by desugarings in surface-language). We also provide list constructors $\exNil$ and $\exCons{e}{e'}$, record construction $\exRec{\vec{\bind{x}{e}}}$ and record projection $\exRecProj{e}{x}$. The final two term forms, anonymous functions $\exLambda{\sigma}$ and recursive let-bindings $\exLetRecMutual{h}{e}$ where $h$ is of the form $\vec{\bind{x}{\sigma}}$, are explained below after we introduce the pattern-matching construct $\sigma$ (eliminator). The typing rules for terms are given in core-language:typing, and are intended only to help a reader understand the language; therefore the rules are simple and do not include features such as polymorphism. The main typing rules of interest are the ones which involve eliminators.

§.§ Eliminators

Eliminators $\sigma, \tau$ are also defined in core-language:syntax, and are inspired by 's notion of generalised trie <cit.>, elaborated further by <cit.>. Eliminators specify how to match against a partial value of some type and select a continuation $\kappa$ for further execution, where $\kappa$ is either a term $e$ or another eliminator $\sigma$. The Boolean eliminator $\elimBool{\kappa}{\kappa'}$ selects either $\kappa$ or $\kappa'$ depending on whether a Boolean value is $\exTrue$ or $\exFalse$. The record eliminator $\elimRec{\seq{x}}{\kappa}$ matches a record with fields $\seq{x}$ and then returns $\kappa$ with the variables $\seq{x}$ bound to the components of the record. The list eliminator $\elimList{\kappa}{\sigma}$ maps the empty list to $\kappa$ and a non-empty list to another eliminator $\sigma$ which specifies how the head and tail of the list are to be matched. The variable eliminator $\elimVar{x}{\kappa}$ extends the usual notion of trie, matching any value, binding it to $x$, and then returning $\kappa$. Eliminators resemble the “case trees” commonly used as an intermediate form when compiling languages with pattern-matching <cit.>, and can serve as an elaboration target for more advanced features such as the piecewise definitions described in surface-language.

The use of nested eliminators to match sub-values will become clearer if we consider the typing judgement $\Gamma \vdash \sigma: \tyFun{A}{B}$ for eliminators given in core-language:typing. (Eliminators always have function type, so this should be read as a four-place relation, with $\to$ part of the notation.) The typing rule for variable eliminators reveals the connection between eliminators and functions: it converts a continuation $\kappa$ which can be assigned type $B$ under the assumption that $x$ is of type $A$ into an eliminator of type $\tyFun{A}{B}$. The typing rule for Boolean eliminators says that to make an eliminator of type $\tyFun{\tyBool}{A}$, we simply need two continuations $\kappa$ and $\kappa'$ of type $A$. The rule for the empty record states that to make an eliminator of type $\tyFun{\tyRec{}}{A}$, we simply need a continuation $\kappa$ of type $A$. The rule for non-empty records allows us to treat an eliminator of type $\tyFun{\tyRec{\vec{\bind{x}{A}}}}{\tyFun{A'}{B}}$ as an eliminator of type $\tyFun{\tyRec{\vec{\bind{x}{A}} \concat \bind{y}{A'}}}{B}$, representing the isomorphism between $\tyFun{\tyFun{A}{B}}{C}$ and $\tyFun{\tyProd{A}{B}}{C}$ but at the level of record types <cit.>. (Formalising eliminators precisely requires -style nested datatypes <cit.> and polymorphic recursion, but these details need not concern us here.)

The typing rule for list eliminators $\elimList{\kappa}{\sigma}$ combines some of the flavour of record and Boolean eliminators. To make an eliminator of type $\tyFun{\tyList{A}}{B}$, we need a continuation of type $B$ for the empty case, and in the non-empty case, an eliminator of type $\tyFun{A}{\tyFun{\tyList{A}}{B}}$ which can be treated as an eliminator of type $\tyFun{\tyProd{A}{\tyList{A}}}{B}$ in order to process the head and tail.

§.§.§ Eliminators as functions

We can now revisit the term forms $\exLambda{\sigma}$ and $\exLetRecMutual{h}{e}$. If $\sigma$ is an eliminator of type $\tyFun{A}{B}$, then $\exLambda{\sigma}$ is an anonymous function of the same type. If $h$ is of the form $\vec{\bind{x}{\sigma}}$, then $\exLetRecMutual{h}{e}$ introduces a sequence of mutually recursive functions which are in scope in $e$. The typing rule for $\exLetRecMutual{h}{e}$ uses an auxiliary typing judgement $\Gamma \vdash h : \Delta$ which assigns to every $x$ in $\Delta$ a function type $\tyFun{A}{B}$ as long as the $\sigma$ to which $x$ is bound in $h$ has that type.

§.§.§ Values

Values $v, u$, and environments $\rho$ are also defined in core-language:syntax, and are standard for call-by-value. (Environments are more convenient than substitution for tracking variable usage.) To support mutual recursion, the closure form  $\exClosure{\rho}{h}{\sigma}$ captures the (possibly empty) sequence $h$ of functions with which the function was mutually defined, in addition to the ambient environment $\rho$. For the typing judgements $\vdash \rho: \Gamma$ and $\vdash v: A$ for environments and values (core-language:typing), only the closure case is worth noting, which delegates to the typing rules for recursive definitions and eliminators.

§.§.§ Evaluation

core-language:semantics gives the operational semantics of the core language. In data-dependencies we will define forward and backward analyses over a single execution; in anticipation of that use case, we treat the operational semantics as an inductive data type, following the “proved transitions” approach of  for reversible CCS <cit.>. The inhabitants of this data type are derivation trees explaining how a result was computed, and the analyses will be defined by structural recursion over these trees. Expressed in terms of inference rules, these trees can become quite cumbersome, so we introduce an equivalent but more term-like syntax for them, called a trace (core-language:syntax-trace), similar to the approach taken by  for $\pi$-calculus <cit.>.

Operational semantics

The judgement $T :: \rho, e \evalR v$ defined at the top of core-language:semantics states that term $e$ under environment $\rho$ evaluates to value $v$, and that $T$ is a proof term that witness that fact. (In the figure the traces appear in grey, to reinforce the idea that they are not part of the definition of $\evalR$ but rather a notation for its inhabitants.) The rules for Booleans, integers and lists are standard and have unsurprising trace forms. For variables, we give an explicit inductive definition of the environment lookup relation $\envLookupR$ at the bottom of the figure, again so that later we can perform analysis over a proof that an environment contains a binding. The lambda rule is standard except that we specify $\seqEmpty$ for the sequence of definitions being simultaneously defined, since a lambda is not recursive. For record construction, the trace form contains a subtrace $T_i$ for each field, and for record projection, which also uses the lookup relation $\envLookupR$, the trace form $\trRecProj{T}{\vec{\bind{x}{v}}}{y}$ records both the record $\vec{\bind{x}{v}}$ and the field name $y$ that was selected.

The rule for (mutually) recursive functions $\exLetRecMutual{h}{e}$, where $h$ is a sequence $\vec{\bind{x}{\sigma}}$ of function definitions, makes use of the auxiliary relation $\rho, h \closeDefsR \rho'$ at the bottom of core-language:semantics which turns $h$ into an environment $\rho'$ binding each function name $x_i$ to a closure $\exClosure{\rho}{h}{\sigma_i}$ capturing $\rho$ and a copy of $h$. For primitive applications, the trace records the values of the arguments which were passed to the operation $\phi$. The rule for application $\exApp{e}{e'}$ is slightly non-standard, because it must deal with both mutual recursion and pattern-matching. First we unpack the recursive definitions $h$ from the closure $\exClosure{\rho_1}{h}{\sigma}$ computed by $e$, and again use the auxiliary relation $\closeDefsR$ to promote this into an environment $\rho_2$ of closures. We then use the relation $\matchR$ explained below to match $v$ against the eliminator $\sigma$, obtaining the branch $e^\twoPrime$ of the function to be executed and parameter bindings $\rho_3$. In addition to subtraces $T$ and $U$ for the function and argument, the application trace $\trApp{T}{U}{w}{T'}$ also has subtraces $w$ for the pattern-match and $T'$ for the selected branch.

§.§.§ Pattern matching

The judgement $w :: v, \sigma \matchR \rho, \kappa$ also defined in core-language:semantics states that eliminator $\sigma$ can match $v$ and produce environment $\rho$ and continuation $\kappa$, with $\rho$ containing the variable bindings that arose during the match. Matches $w$ are a compact notation for proof terms for the $\matchR$ relation, analogous to traces for the $\evalR$ relation, and again appear in grey in the figure.

Variable eliminators $\elimVar{x}{\kappa}$ match any value, returning the singleton environment $\bind{x}{v}$ and continuation $\kappa$. Boolean eliminators match any Boolean value, returning the appropriate branch and empty environment $\seqEmpty$. List eliminators $\elimList{\kappa}{\sigma}$ match any list. The nil case is analogous to the handling of Booleans; the cons case depends on the fact that the nested eliminator $\sigma$ for the cons branch has the curried type $\tyFun{A}{\tyFun{\tyList{A}}{B}}$. First, we recursively match the head $v$ of type $A$ using $\sigma$, obtaining bindings $\rho$ and eliminator $\tau: \tyFun{\tyList{A}}{B}$ as the continuation. Then the tail $v'$ is matched using $\tau$ to yield additional bindings $\rho'$ and final continuation $\kappa'$. Record matching is similar: the empty record case resembles the nil case, and the non-empty case relies on the nested eliminator having curried type $\tyFun{\tyRec{\vec{\bind{x}{A}}}}{\tyFun{A'}{B}}$. The initial part $\vec{\bind{x}{v}}$ of the record is matched using $\sigma$, returning another eliminator $\sigma'$ of type $\tyFun{A'}{B}$. Then the last field $\bind{y}{u}$ is matched using $\sigma'$ to yield final continuation $\kappa$.

§ A BIDIRECTIONAL DYNAMIC DEPENDENCY ANALYSIS

We now extend the core language from core-language with a bidirectional mechanism for tracking data dependencies. data-dependencies:lattices-of-selections establishes a way of selecting (parts of) values, such as the height of a bar in a bar chart. data-dependencies:analyses:fwd defines a forward analysis function $\evalFwdF{T}$ which specifies how selections on programs and environments (collectively: input selections) becomes selection on outputs; selections represent availability, with the computed output selection indicating the data available to the downstream computation. data-dependencies:analyses:bwd defines a backward dependency function $\evalBwdF{T}$ specifying how output selections are mapped back to inputs; then selections represent demands, with the computed input selection identifying the data needed from the upstream computation. Both functions are monotonic; this will become important in data-dependencies:galois-connections, where show that $\evalBwdF{T}$ and $\evalFwdF{T}$ form a Galois connection, establishing the round-tripping properties sketched intuitively in introduction:data-linking which are important for trusting the results of the analyses.

§ DE MORGAN DEPENDENCIES FOR BRUSHING AND LINKING

data-dependencies addresses the first kind of question we motivated in the introduction (introduction:data-linking). In particular $\evalBwdF{T}$ can answer questions like: “what data is needed to compute this bar in a bar chart?”, and indeed we were able to use our implementation to generate introduction:data-linking. The second problem we set ourselves was how to link selections between cognate outputs, i.e. outputs computed from the same data (introduction:vis-linking). This is called “brushing and linking” <cit.> in data visualisation, and has been extensive studied as an interaction paradigm, but with little emphasis on techniques for automation. Intuitively, the problem has a bidirectional flavour: one must consider how dependencies flow backward from a selection in one output to a selection $v$ in the common data, and then forward from the selected data $v$ to a corresponding selection in the other output. A natural question then is whether the analysis established in data-dependencies can supply the information required to support an automated solution.

An immediate problem is that the flavour of the forward dependency required here differs from that provided by the forward analysis $\evalFwdF{T}$ defined in data-dependencies:analyses:fwd. That was able to answer the question: what can we compute given only the data selected in $v$? But to identify the related data in another output, we must determine not what the input selection $v$ is sufficient for, but what it is necessary for: those parts of the other output that depend on $v$. In fact the question can be formulated as a kind of dual: what would we not be able to compute if the data selected in $v$ were unavailable?

§.§ De Morgan duality

Why $\evalFwdF{T}$ is unsuitable as a forward dependency relation for linking cognate outputs can also be understood in terms of compositionality. Suppose $\Ann{V}_1$ and $\Ann{V}_2$ are the lattices of selections for two views computed from a shared input source, and $\Ann{D}$ is the lattice of selections for the shared input. Using the procedure given in data-dependencies, we can obtain two Galois connections $f: \Ann{V}_1 \to \Ann{D}$ and $g: \Ann{V}_2 \to \Ann{D}$ as shown in example:de-morgan:non-composable below; we ask the reader to ignore example:de-morgan:composable for the moment.

Unfortunately, $f$ and $g$ are not composable, as their types makes clear. While the upper adjoint $\upperAdj{g}: \Ann{D} \to \Ann{V}_2$ has the correct type to compose with the lower adjoint $\lowerAdj{f}: \Ann{V}_1 \to \Ann{D}$, the result is not a Galois connection: $\upperAdj{g}$ preserves meets, whereas $\lowerAdj{f}$ preserves joins. However, it turns out that if selections are closed under complement, we can derive an analysis of what is necessary for a given input selection from an analysis of what it is sufficient for. The effect is to invert $g$, yielding a Galois connection $\dual{g}$ with a type that allows it to compose with $f$. Then the composite $\dual{g} \after f$ is a Galois connection linking $\Ann{V}_1$ to $\Ann{V}_2$ via $\Ann{D}$, as shown in example:de-morgan:composable, offering a general mechanism for brushing and linking, with nice round-tripping properties. We now unpack this in more detail.

First we shift settings from the lattices used in data-dependencies to Boolean lattices (or Boolean algebras) $\Ann{A}= \BoolLattice{\Ann{A}}{\top}{\bot}{\meet}{\join}{\neg}$, which are lattices equipped with an involution $\neg: \Ann{A} \to \Ann{A}$ called complement. Boolean algebras satisfy complementation laws $x \meet \neg x = \bot$ and $x \join \neg x = \top$ and De Morgan laws $\neg x \meet \neg y = \neg(x \join y)$ and $\neg x \join \neg y = \neg(x \meet y)$. If $\Ann{A}$ is a Boolean algebra, then $\Sel{\raw{v}}{A}$ is also a Boolean algebra, with the Boolean operations, and in particular $\neg_{\raw{v}}: \Sel{\raw{v}}{A} \to \Sel{\raw{v}}{A}$, defined pointwise. An additional distinguished selectable value $\blackhole$ serves as the negation of $\hole$. The two-point lattice $\Bool$ we used to illustrate data-dependencies is also a Boolean algebra $\BoolLattice{\Bool}{\TT}{\FF}{\wedge}{\vee}{\neg}$ with $\neg$ corresponding to logical negation.

It is an easy consequence of the complementation and De Morgan laws that any meet-preserving operation $g: \Ann{A} \to \Ann{B}$ on Boolean algebras has a join-preserving De Morgan dual $\dual{g}: \Ann{A} \to \Ann{B}$ given by $\neg_{\Ann{B}} \after g\after \neg_{\Ann{A}}$, and any join-preserving operation $h$ has a meet-preserving De Morgan dual $\dual{h}$ defined similarly. Moreover if $h$ is the lower adjoint of $g$, then $\dual{g}$ is the lower adjoint of $\dual{h}$. Thus Galois connections on Boolean algebras also admit a (contravariant) notion of De Morgan duality, defined component-wise.

Suppose $\Ann{A}$ and $\Ann{B}$ are Boolean algebras and $f: \Ann{A} \to \Ann{B}$ is a Galois connection $(\lowerAdj{f},\upperAdj{f})$. Define the De Morgan dual $\dual{f}$ of $f$ to be the Galois connection $(\dual{\upperAdj{f}}, \dual{\lowerAdj{f}}): \Ann{B} \to \Ann{A}$.

Dualising a Galois connection flips the direction of the arrow by swapping the roles of the upper and lower adjoints. So while $f: \Ann{A} \to \Ann{B}$ and $g: \Ann{C} \to \Ann{B}$ are not composable, $f$ and $\dual{g}: \Ann{B} \to \Ann{C}$ are, and the composition is achieved by transforming $\upperAdj{g}$ from something which determines what we can compute with $v$ into something which determines what we cannot compute without $v$. This offers a principled basis for an automated brushing and linking feature between cognate computations $T$ and $U$. When the user selects part of the output of $T$, we can use $\evalBwdF{T}$ to compute the needed data $v$, and then use $\dual{\evalFwdF{U}}$ to compute the parts of the output of $U$ that depend on $v$. This is the approach implemented in , and we used this to generate introduction:vis-linking in introduction:vis-linking.

§.§ Example: matrix convolution

We now illustrate the $\dual{\evalGC{T}}$ Galois connection, contrasting it with $\evalGC{T}$, using an example which computes the convolution of a $5 \times 5$ matrix with a $3 \times 3$ kernel. Convolution has an intuitive dependency structure and the values involved have an easy visual presentation, making it useful for conveying the flavour of the four distinct (but connected) dependency relations that arise in the framework. The source code for the example is given in example:convolve, and shows the convolve function, plus zero, wrap and extend which provide different methods for handling the boundaries of the input matrix. The angle-bracket notation is used to construct matrices, which were omitted from core-language. (The formal treatment is similar to records.)

was used to generate the diagrams in example:convolve-viz, which show the four dependency relations and two of their four possible round-trips. example:convolve-viz:galois-dependency shows the $\evalGC{T}$ Galois connection defined in data-dependencies:galois-connections. In the upper figure, the user selects (in green) the output cell at position $(2,2)$ (counting rows downwards from $1$). This induces a demand (via the lower adjoint $\evalBwdF{T}$) on the input matrix image and the kernel filter, revealing (in yellow) that the entire kernel was needed to compute the value $1$, but only some of the input matrix. In particular the elements at $(1,3)$ and $(3,1)$ in image were not needed, because of zeros present in filter. If we then “round-trip” that input selection, computing the corresponding availability on the output using the upper adjoint $\evalFwdF{T}$, the green selection grows: it turns out that the data needed to make $(2,2)$ available are sufficient to make $(1,1)$ available as well.

example:convolve-viz:de-morgan-dual shows the De Morgan dual $\dual{\evalGC{T}}$. In the upper part of the figure, the user selects (green) kernel cell $(1, 2)$ to see the output cells that depend on it. This is computed using the De Morgan dual of $\evalFwdF{T}$. First we negate the input selection, marking $(1, 2)$ as unavailable, and all other inputs as available. Then we forward-analyse with $\evalFwdF{T}$ to determine that with this data selection, we can only compute the top row of the output. (If it seems odd that we can compute even the top row, notice that the example uses the method zero for dealing with boundaries; wrap or extend would give a different behaviour.) Then we negate that top row selection to produce the (yellow) output selection shown in the figure. These are exactly the output cells which depend on kernel cell ($1, 2)$ in the sense that they cannot be computed if that input is unavailable.

We can then round-trip this output selection using the De Morgan dual of $\evalBwdF{T}$. We first negate the yellow output selection (selecting the top row of the output again), and then use $\evalBwdF{T}$ to determine the needed inputs, which turn out to be the top two rows of image, and the top row of filter. Negating again produces the green output selection shown in the lower figure. Thus the backwards De Morgan dual computes the inputs that would not be needed if the selected outputs were not needed: more economically, the inputs that are only needed for the selected output. Here the round-trip reveals that if kernel cell $(1, 2)$ is unavailable, then the entire top row of the kernel might as well have been unavailable too, and similarly for the bottom 3 rows of the input.

§.§ Relationship to Galois slicing

The De Morgan dual puts us in a better position to consider the relationship between the present system and earlier work on Galois slicing, a program slicing technique that has been explored for pure functional programs <cit.>, functional programs with effects <cit.>, and  <cit.>. We consider other related work in conclusion:other-related-work.

Galois slicing operates on lattices of slices, which are programs (or values) where parts deemed irrelevant are replaced by a hole $\hole$. (If we think of the notion of selection defined in data-dependencies:selections as picking out a subset of the paths in a term, then slices resembles selections which are prefix-closed, meaning that if a given path in a term is selected, then so are all of its prefixes.) For a fixed computation, a meet-preserving forward-slicing function is defined which takes input slices to output slices, discarding parts which cannot be computed because the needed input is not present, plus a join-preserving backward-slicing function taking output slices to input slices, retaining the parts needed for the output slice. For example example:diff-slicing:original shows a computation with output (0.4, 0.6), and example:diff-slicing:subtree gives the backward slice for output slice (0.4, $\hole$). Forward and backward slicing, for a given computation, form a Galois connection, giving the analyses the nice round-tripping properties we motivated in data-dependencies:galois-connections.

Unfortunately, the notion of slice does not lend itself to computing dependencies where the needed input or output is a proper part of a value, such as a component of a tuple. Differential slicing <cit.> improves on this by using Galois slicing to compute a pair of input slices $(e,e'$) for a pair of output slices $(v,v')$ where $v \leq v'$. By monotonicity, $e \leq e'$. This can be used to compute a (differential) slice for an arbitrary subtree, by setting $v$ to be the “spine” of the original output up to the location of the subtree, and $v'$ to be $v$ with the subtree of interest plugged back in. Here we could focus on the value 0.4 in the output by computing the backward slice for $\kw{($\hole$, $\hole$)}$ (example:diff-slicing:spine) and then comparing it with the backward slice for (0.4, $\hole$), generating a differential slice where the parts that are different are highlighted (example:diff-slicing:differential). But although it supports a notion of selection which is closer to what we need, the differential slice highlights only the program parts that are needed exclusively by the selected output. Here, 2 and 3 are needed to compute the spine as well (in order to decide which conditional branch to execute), so they are excluded from the differential slice. In fact differential slicing is similar to the dual of $\evalBwdF{T}$, and as such underapproximates the dependency information needed for data linking.

§ GALOIS CONNECTIONS FOR DESUGARING

Elaborating a richer surface language into a simpler core is a common pattern with well known benefits. It can, however, make it harder to express certain information to the programmer in terms of the surface language. We face this problem with the analysis in data-dependencies, which links outputs not only to inputs, but also to expressions responsible for introducing data. We could use this information in an IDE to link structured outputs to relevant code fragments, but only if we are able to map term selections back to the surface program. We now sketch a bidirectional desugaring procedure which addresses this, and which composes with the Galois dependency analysis defined in data-dependencies.

§.§ Surface language syntax

The surface language  extends the core syntax with list notation $\kw{[} s \comma \ldots \comma s' \kw{]}$, Haskell 98-style list comprehensions <cit.>, list enumerations, first-class primitives and piecewise function definitions and pattern-matching, as shown in surface-language:syntax. Typing rules are given in surface-language, surface-language:typing-termsurface-language:typing-pattern. We attach selection states $\alpha$ to (selectable) surface terms $s, t$ that desugar to selectable core terms, and let $\raw{s}$, $\raw{t}$ range over “raw” surface terms, which are isomorphic to the selectable terms where the type of selection states is the unit lattice $\Unit$.

surface-language:example-1 shows how the end-to-end mapping would appear to a user. (For illustrative purposes the library function map and some raw data are included in the same source file.) On the left, the user selects a cons cell (green) in the output; by backwards evaluating and then backwards desugaring, we are able to highlight the list comprehension, the cons in the second clause of map, and both occurrences of the constant "Hydro". These last two are highlighted because the selected cons cell was constructed by eliminating a Boolean that was in turn constructed by the primitive == operator, which consumed the two strings. The user might then conjecture that the two occurrences of "Geo" were somehow responsible for the inclusion of the third cons cell in the output; they can confirm this by making the green selection on the right. (Highlighting == too would clearly be helpful here; we discuss this possibility in conclusion:other-related-work.) The grey selection is included to contrast the cons highlighting with the data demanded by the list elements themselves, which is quite different.

Source selections (yellow) resulting from selecting different list cells (green)

§.§ Forward desugaring

To define the forward evaluation function $\evalFwdF{T}$ in data-dependencies:analyses:fwd, we performed a regular evaluation using $\evalR$ to obtain a trace $T$, and then defined $\evalFwdF{T}$ by recursion over $T$, with $T$ guiding the analysis in the presence of $\hole$. There are no holes in the surface language, so we can take a simpler approach, defining a single forward desugaring relation $\desugarFwdR$, and then showing that for every raw surface term $\raw{t} \desugarFwdR \raw{e}$, there is a monotonic function $\desugarFwdF{t}: \Sel{\raw{t}}{A} \to \Sel{\raw{e}}{A}$, which is simply $\desugarFwdR$ domain-restricted to $\Sel{\raw{t}}{A}$. The full definition of $\desugarFwdR$ is given in surface-language ; surface-language:desugar gives a representative selection of the rules.

Forwards and backwards desugaring (selected rules only)

The definition follows a similar pattern to $\evalFwdF{T}$. At each step, we take the meet of the availability on any parts of $s$ being consumed at that step, and use that as the availability of any parts of $e$ being generated at that step. Thus the rules for list notation simply transfer the selection state $\alpha$ on the opening and closing brackets $\annot{\kw{[}}{\alpha}$ and $\annot{\kw{]}}{\alpha}$ to the corresponding cons and nil of the resulting list, and those on intervening delimiters $\annot{\comma}{\alpha}$ to the corresponding cons. List comprehensions $\annListComp{s}{\vec{q}}{\alpha}$ have a rule for each kind of qualifier $q$ at the head of $\vec{q}$, plus a rule for when $\vec{q}$ is $\seqEmpty$. The general pattern is to push the $\alpha$ on the comprehension itself through recursively, so it ends up on all core terms generated during its elaboration: in particular the false branch when $q$ is a guard, and the singleton list when $\vec{q}$ is empty. Auxiliary relations $\clauseFwdR$ and $\totaliseFwdR{p}$ (defined in surface-language, surface-language:clause-fwdsurface-language:totalise-fwd) transfer availability on guards and generators onto the eliminators they elaborate into.

§.§ Backward desugaring

The backwards analysis is then defined as a family of backward desugaring functions $\desugarBwdR{\raw{t}}: \Sel{\raw{e}}{A} \to \Sel{\raw{t}}{A}$ for any $\raw{t} \desugarFwdR \raw{e}$, with the raw surface term $\raw{t}$ guiding the analysis backwards. (The role of $\raw{t}$ in disambiguating the backwards rules should be clear if you consider that $e$ typically matches multiple rules but only one for a given $\raw{t}$.) surface-language:desugar gives some representative rules; the full definition is given in surface-language . To reverse a desugaring step, we take the join of the demand on any parts of $e$ which were constructed at this step, and use that as the demand on the parts of $s$ which were consumed at this step, turning demand on the core term into (minimal) demand on the surface term. Thus the effect of the list comprehension rules and auxiliary judgements is to set the demand on the comprehension itself to be the join of the demand of all the syntax generated during the elaboration of the comprehension, using auxiliary judgments $\totaliseBwdR{p}$ and $\clauseBwdR{p}$ (surface-language, surface-language:totalise-bwdsurface-language:clause-bwd) to transfer demand from eliminators back onto the guards and generators.

§.§ Round-tripping properties and compositionality

It is easy to verify that $\desugarFwdF{t}$ and $\desugarBwdF{t}$ are monotonic. Moreover they form an adjoint pair.

Suppose $t \desugarFwdR e$. Then ${\desugarGC{t}} \eqdef (\desugarBwdF{t}, \desugarFwdF{t}): \Sel{\raw{e}}{A} \to \Sel{\raw{t}}{A}$ is a Galois connection.

See proofs-surface:desugar:gc.

The $\desugarGC{\raw{t}}$ Galois connection readily composes with $\evalGC{T}$ to produce surface-language selections like the ones shown in surface-language:example-1. This is useful, although somewhat monolithic. In future work we will investigate techniques for backwards desugaring at arbitrary steps in the computation (perhaps by interleaving desugaring with execution), and presenting selections on intermediate values (such as lists) in the surface language, even though they were not obtained via desugaring.

§ CONCLUSION

Our research was motived by the goal of making computational outputs which are automatically able to reveal how they relate to data in a fine-grained way. A casual reader who wants to understand or fact-check a chart, or a scientist evaluating another's work, should be able to do so by interacting directly with an output. Recent work by  suggests that developers would also benefit from such a feature while implementing visualisations, for example to check whether a quantity is represented by diameter or area in a bubble chart <cit.>.

Galois connections provide an appealing setting for this problem because of their elegant round-tripping properties. However,  existing dynamic analysis techniques based on Galois connections do not lend themselves to richly structured outputs like visualisations and matrices. We presented an approach that allows focusing on arbitrary substructures, which also means data selections can be inverted. This enables linking not just of outputs to data, but of outputs to other outputs, providing a mathematical basis for a widely used (but so far ad hoc) feature in data visualisation. We implemented our approach in , a realistic high-level functional programming language.

A link to our GitHub repository is included in the non-anonymised version of the paper.

Our implementation can be found at <https://github.com/explorable-viz/fluid>.

§.§ Other related work and future directions

We close by considering some limitations and opportunities in the context of other related work. Galois slicing <cit.> was considered in de-morgan:galois-slicing.

Executable slicing. Executable slices <cit.> are programs with some parts removed, but which are still executable. Our approach computes data selections, not executable slices, but such a notion has obvious relevance in data science, since “explaining” a part of a result should (arguably) entail being able to recompute it. Expression provenance <cit.> explains how primitive values are computed using only primitive operations; however, this still omits crucial information, and does not obviously generalise to structured outputs. Work on executable slicing in term rewriting <cit.> could perhaps be adapted to structured values in our setting.

Dynamic program analysis. Dynamic analysis techniques like dataflow analysis <cit.> and taint tracking <cit.> tend to focus on variables, rather than parts of structured values, and lack round-tripping properties; Galois dependencies have a clear advantage here. A limitation of dynamic techniques which is shared by our approach is that they can usually only reveal that certain dependencies arise, not why, which requires analysing path conditions <cit.>. In a data science setting this would clearly be valuable too, and it would be interesting to see if the benefits of the Galois framework can be extended to techniques for computing dynamic path conditions.

Brushing and linking. Brushing and linking has been extensive studied in the data visualisation community <cit.>, but although <cit.> argued it should be ubiquitous, no automated method of implementation has been proposed to date. Geospatial applications like GeoDa <cit.> hard-code view coordination features into specific views, and libraries like d3.js and Plotly support ad hoc linking mechanisms, with varying degrees of programmer effort required. No existing approach provides automation or round-tripping guarantees, or is able to provide data selections explaining why visual selections are linked.

Data provenance in data visualisation. A recent vision paper by <cit.> is the only work we are aware of that proposes that brushing and linking, and related view cooordination features like cross-filtering, can be understood in terms of data provenance. In a relational (query processing) setting, where the relevant notion of provenance is lineage, they propose backward-analysing to data, and then forward-analysing to another view (but again, without the round-tripping features of Galois connections). However, theirs is primarily a concept paper, proposing a research programme, rather than solving a specific problem.

Perera was supported by The UKRI Strategic Priorities Fund under EPSRC Grant EP/T001569/1, particularly the Tools, Practices and Systems theme within that grant, and by The Alan Turing Institute under EPSRC grant EP/N510129/1.


# Bidirectional Uncertainty-Based Active Learning for Open Set Annotation

Chen-Chen Zong1 Ye-Wen Wang 1 Kun-Peng Ning2 Haibo Ye1&Sheng-Jun Huang1
1Nanjing University of Aeronautics and Astronautics
2Peking University {chencz<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Active learning (AL) in open set scenarios presents a novel challenge of
identifying the most valuable examples in an unlabeled data pool that
comprises data from both known and unknown classes. Traditional methods
prioritize selecting informative examples with low confidence, with the risk
of mistakenly selecting unknown-class examples with similarly low confidence.
Recent methods favor the most probable known-class examples, with the risk of
picking simple already mastered examples. In this paper, we attempt to query
examples that are both likely from known classes and highly informative, and
propose a Bidirectional Uncertainty-based Active Learning (BUAL) framework.
Specifically, we achieve this by first pushing the unknown class examples
toward regions with high-confidence predictions with our proposed Random Label
Negative Learning method. Then, we propose a Bidirectional Uncertainty
sampling strategy by jointly estimating uncertainty posed by both positive and
negative learning to perform consistent and stable sampling. BUAL successfully
extends existing uncertainty-based AL methods to complex open-set scenarios.
Extensive experiments on multiple datasets with varying openness demonstrate
that BUAL achieves state-of-the-art performance.

##  1 Introduction

Labeling data can be costly and time-consuming, often requiring high levels of
expertise from annotators Settles (2009). This expense poses a significant
challenge when dealing with insufficient labeled data in deep learning tasks.
Recently, active learning (AL) has emerged as a prominent approach to tackle
this issue and has gained widespread attention Mahmood et al. (2021); Huang et
al. (2021); Ren et al. (2021). It iteratively selects the most informative
examples from the unlabeled data pool and queries their labels from an oracle,
enabling the learning of an effective model with reduced labeling costs.

Existing AL methods Roy and McCallum (2001); Fu et al. (2013); Huang et al.
(2010); You et al. (2014); Sinha et al. (2019); Yoo and Kweon (2019); Ning et
al. (2021) typically operate under the closed-set assumption, assuming that
the label categories in the unlabeled data pool match those of the target
task. However, this assumption often does not hold in practical scenarios. For
example, consider a task that involves classifying images into two target
categories, “Dog” and “Cat”. Collecting training examples through keyword-
based image search inevitably introduces irrelevant images from other
categories (i.e., unknown classes), alongside the two target categories (i.e.,
known classes).

In such open-set scenarios, many previous AL methods, which prefer querying
examples with less confident predictions, may lead to failure since examples
from unknown classes often receive uncertain predictions. To mitigate the
impact of unknown class examples, some AL methods designed specifically for
open-set scenarios attempt to query examples that are more likely to belong to
known classes based on sample similarity Du et al. (2021) or model-predicted
max activation value (MAV) Ning et al. (2022). However, since examples similar
to the labeled ones may be already mastered data, they do not significantly
benefit the target model. These methods only perform well when the proportion
of unknown class examples is high. When the proportion is low, they tend to
perform poorly than traditional AL methods, even inferior to random sampling
(please refer to Figure 6). However, determining the proportion of unknown
class examples in practical scenarios is often challenging. This further
limits the usability of these methods.

In this paper, we start with a specific question: can we effectively
distinguish the “informative” examples of known classes from examples of
unknown classes? Intuitively, if we can push the unknown class examples toward
regions with high-confidence predictions, existing uncertainty-based AL
methods can be applied directly in open-set scenarios. To achieve this, we
propose to fine-tune the model by performing negative learning (NL) Kim et al.
(2019); Luo et al. (2021); Lee et al. (2021) on unlabeled examples. NL is an
indirect learning manner that explores the utility of complementary labels,
i.e., the label categories that an instance does not belong to. For a
$K$-classification problem, the NL loss is defined as:

$\ell_{NL}\left(f,\bar{y}\right)=-\textstyle\sum_{k=1}^{K}\bar{y}_{k}\log{(1-p_{k})}.$
(1)

where $\bar{y}$ and
$\bm{\bar{y}}=\left[\bar{y}_{1},\dots,\bar{y}_{k},\dots,\bar{y}_{K}\right]$
represent a complementary label and its corresponding one-hot form,
respectively, and $p_{k}$ denotes the probability of the $k$-th category.

Specifically, the fine-tuning process comprises two parts. On one hand, for
already labeled examples, we train them directly using Equation 1. On the
other hand, for unlabeled examples, we first randomly assign labels to them in
each training round and then train the model using Equation 1. Notably, the
unlabeled known class example has a relatively higher chance of receiving the
correct label, whereas the unknown class example will never be assigned the
correct label. Once unlabeled known class data receive the correct labels,
they suffer a larger penalty and are reduced confidence predictions by the
model since they deviate from the distribution information obtained from
labeled data. In contrast, unlabeled unknown class data are not constrained to
move towards the high-confidence region for counteracting the update gradient
produced by the labeled data111More detailed explanations are provided in
subsection 3.2..

To validate this, we conducted preliminary experiments on CIFAR-10 Krizhevsky
et al. (2009) with 4 known classes and 6 unknown classes. Figure 1 illustrates
the confidence statistics for all unlabeled examples in a fixed query round
before and after fine-tuning the model. As expected, known class examples are
more prevalent in the low-confidence region, while unknown class ones are more
common in high-confidence regions. This distribution characteristic presents a
potential solution to the aforementioned problem and offers a promising
approach to AL for open-set scenarios.

(a) w/o NL

(b) w NL

Figure 1: The statistics of prediction confidence before and after fine-tuning
the model. Note that in the zoomed-in area of Figure 1(b), we swapped the
display order of the two to prevent occlusion, allowing for a more intuitive
view of how the distribution has changed.

Based on this, we propose a Bidirectional Uncertainty-based Active Learning
framework (BUAL). On one hand, we propose the Random Label Negative Learning
(RLNL) method to fine-tune the model and leverage information from the
unlabeled data pool. Specifically, we first train a model using all labeled
data as a positive classifier. Then, negative learning is performed to fine-
tune the model as a negative classifier by randomly assigning labels to data
from the unlabeled pool in each training iteration. This effectively
distinguishes known class examples with lower confidence predictions from
unknown class ones. On the other hand, we propose a Bidirectional Uncertainty
(BU) sampling strategy for active selection, which estimates prediction
uncertainty from both positive and negative classifiers. By selecting examples
with the highest uncertainty, we expect to identify the most informative
instances from the known classes. Experiments are performed on multiple
datasets with different unknown class ratios. The results demonstrate that
BUAL can query more informative known class examples and that the model
performance obtained by BUAL is substantially improved compared with existing
state-of-the-art methods.

##  2 Related Work

Active learning (AL) is a prominent approach aimed at reducing label costs by
selecting a batch of examples that are most valuable for model training.
Existing AL methods can be broadly categorized into three groups based on
sample selection strategies: uncertainty-based, representative-based, and
hybrid strategies which combine both aspects. Uncertainty-based strategies
focus on sampling informative instances to reduce model uncertainty. Typical
methods include Least Confident Sampling Li and Sethi (2006), Margin-based
Sampling Balcan et al. (2007), and Entropy-based Sampling Holub et al. (2008),
etc. Representative-based strategies start from the sample distribution and
aim to select representative instances that match the overall distribution. A
typical method is Coreset Sener and Savarese (2017). Hybrid strategies combine
uncertainty and representativeness by incorporating sample distribution
information and the model’s specific needs. Notable methods in this category
include QUIRE Huang et al. (2010) and BADGE Ash et al. (2019), etc.

Figure 2: The framework of BUAL. A two-stage $K$ classifier is trained, where
the first stage is trained in a normal manner saved as $f_{p}(\cdot)$, and the
second stage is trained using the proposed random label negative learning
method denoted as $f_{n}(\cdot)$. An auxiliary $K+1$ classifier
$f_{aux}(\cdot)$ is trained in parallel. By collecting the predicted
uncertainty of $f_{p}(\cdot)$ and $f_{n}(\cdot)$ on each candidate example
along with the global and local balancing factors, the proposed bidirectional
sampling strategy can accurately estimate the potential utility of each
example and perform effective sample sampling under complex open-set
scenarios.

Open-set annotation (OSA) involves active learning under open-set scenarios Du
et al. (2021); Ning et al. (2022). Existing methods primarily focus on
selecting examples that are most likely to belong to known classes. For
instance, CCAL Du et al. (2021) employs contrastive learning to extract
semantic and distinctive features of examples, facilitating discrimination of
known class examples. LfOSA Ning et al. (2022) introduces an auxiliary network
to model the per-example max activation value (MAV) distribution and
dynamically selects examples with the highest probability from known classes.
However, these methods exhibit sensitivity to the openness of the dataset and
may not consistently perform well. Open-set recognition (OSR) Scheirer et al.
(2012); Salehi et al. (2021); Moon et al. (2022) is a related problem setting
to OSA, aiming to predict correct labels for known class examples while
simultaneously detecting examples from unknown classes. Nevertheless, direct
use of OSR methods often falls short of expected effectiveness Ning et al.
(2022), mainly due to limited training examples and the inability to identify
highly informative instances.

Complementary labels are labels other than the ground-truth label assigned to
an example. Complementary label learning Ishida et al. (2017); Yu et al.
(2018); Feng et al. (2020) was initially introduced in Ishida et al. (2017),
where the authors leveraged the lower acquisition cost and higher correct
labeling rate of complementary labels to address multi-class classification
problems. However, complementary labels contain less information compared to
the correct labels, which can result in slow convergence of the model and
challenges in achieving the desired performance when directly using
complementary labels for training. Authors in Kim et al. (2019) made the first
attempt to combine complementary label learning with the noise labeling
problem and proposed an indirect and robust training schema called negative
learning (NL). In this paper, we exploit the properties of NL and extend NL to
open-set and label-free settings for the first time.

##  3 Methodology

###  3.1 Preliminaries

Notations. In open-set annotation (OSA) settings, there are two labeled data
pools:
$D_{l}^{kno}=\left\\{(x_{i}^{l},y_{i}^{l})\right\\}_{i=1}^{n_{l}^{kno}}$ for
known classes and
$D_{l}^{unk}=\left\\{(x_{i}^{l})\right\\}_{i=1}^{n_{l}^{unk}}$ for unknown
classes, as well as an unlabeled data pool:
$D_{u}=\left\\{(x_{i}^{u})\right\\}_{i=1}^{n_{u}^{kno}}\cup\left\\{(x_{i}^{u})\right\\}_{i=1}^{n_{u}^{unk}}$
containing examples from both known and unknown classes. Each known class
example belongs to one of $K$ known classes in the label space
$\mathcal{Y}=\left\\{1,2,\dots,K\right\\}$. The unknown class examples are
uniformly grouped into one category, denoted as $y=\emptyset$. In each
training round, active learning (AL) queries a batch of $b$ examples according
to a given query strategy $\mathcal{A}$, denoted as
$X_{query}=X_{query}^{kno}\cup X_{query}^{unk}$. Once the labeled feedback is
obtained, we can calculate a ratio $r=\frac{|X_{query}^{kno}|}{|X_{query}|}$
to represent the precision of known classes.

Overview. The proposed Bidirectional Uncertainty-based Active Learning (BUAL)
framework is depicted in Figure 2. In each iteration, there are in general
three steps:

  * •

Model Training: the algorithm first trains a target classifier in a normal
learning manner, dubbed positive classifier $f_{p}(\cdot)$. Then, the
algorithm fine-tunes the classifier with a new classifier head by the proposed
Random Label Negative Learning method, dubbed negative classifier
$f_{n}(\cdot)$. Similar to Ning et al. (2022), a $K+1$ auxiliary classifier
$f_{aux}(\cdot)$ is trained in parallel.

  * •

Example Selection: the Bidirectional Uncertainty Sampling Strategy estimates
uncertainty bidirectionally using both the positive and negative classifier
heads. This estimation is combined with dynamic balance factors generated by
the auxiliary classifier and query feedback to select the most informative
known class examples.

  * •

Oracle Labeling: the annotators assign class labels to the selected examples.
Based on the feedback results, update the corresponding data pools
accordingly.

###  3.2 Random Label Negative Learning

In OSA scenarios, conventional uncertainty-based AL methods tend to be
ineffective for example selection, mainly due to the unconfident predictions
generated for the unknown class examples. Existing OSA methods prioritize
sample purity without fully exploring sample informativeness, resulting in
queries with too many mastered examples that are not useful for model
training. Thus, a key question arises: how to distinguish between unknown and
known class examples.

To cope with this problem, we propose a general method by pushing unknown
class examples toward the high-confidence regions, while pushing known class
examples to the low-confidence regions. If this separation is achieved, we can
leverage existing uncertainty-based AL methods directly to handle various
complex open-set scenarios. Fortunately, we achieve this to some extent by
employing negative learning (NL), where we assign random labels to unlabeled
examples and fine-tune the model with a new classifier head accordingly,
dubbed Random Label Negative Learning (RLNL).

In the model training stage, we first train a $K$-class classifier
$f_{p}(\cdot)$ in a normal training manner (e.g., cross-entropy loss) based on
$D_{l}^{kno}$. Note that $f_{p}(\cdot)$ can be the target model we eventually
need to output. After training on the labeled data, $f_{p}(\cdot)$ can own a
good discriminative ability for known class examples at the representation
level. Then, to perform NL, we replace the last layer of $f_{p}(\cdot)$ and
train a new classifier head $f_{n}(\cdot)$ with Equation 1. In this phase,
unlabeled examples in $D_{u}$ are involved in training to help achieve the
goal mentioned above pushing unknown and known class examples toward the high
and low confidence regions, respectively. All labeled examples in
$D_{l}^{kno}$ are still involved to prevent them from being incorrectly
shifted in the distribution. Here, considering that the number of examples in
$D_{u}$ is usually much larger than that in $D_{l}^{kno}$, a small subset
$D_{sub}$ is randomly selected from the $D_{u}$ to save training cost.
Specifically, we assign random labels to the unlabeled examples in $D_{u}$,
while using the complementary labels instead for the labeled known class
examples, i.e., for an example $\bm{x}$:

$P(\bar{y}=s)=\frac{1}{\left|S\right|},s\in\begin{cases}S=\mathcal{Y}\setminus
y^{l},&\text{ if }\bm{x}\in D_{l}^{kno},\\\ S=\mathcal{Y},&\text{ if
}\bm{x}\in D_{u}.\end{cases}$ (2)

where $\bar{y}$ is uniformly sampled at each training iteration.

Figure 3: Use all labels per iteration for negative learning (left) vs. use
one random label per iteration for negative learning (right).

Why RLNL works? The first question one may hold is why it shouldn’t be optimal
for the unlabeled examples to be the uniform distribution as $\bar{y}$ is
sampled at each iteration. To explain this, we take two different kinds of
updating for a single example in the binary classification scenario of “Dog
vs. Cat” as illustrations: negative learning using all labels at each
iteration and negative learning using one random label at each iteration. One
possible case is shown in Figure 3. If each iteration uses all labels for
negative learning, i.e., such an example is neither a “Cat” nor a “Dog”, it is
apparent that an update gradient of 0 is only achieved when the example is at
the decision boundary. In contrast, if each iteration gives a random label for
negative learning, i.e., such an example is not a “Cat” or a “Dog”, then for
an instance that is not a “Cat”, pushing it as much as possible towards the
“Dog” side will result in a gradient update of 0, and vice versa. Obviously,
there is no fixed optimal scenario for this type of data.

Figure 4: The possible RLNL update scenario for unlabeled unknown class data
in batch deep learning manner. The green “$\longrightarrow$” is the batch
update gradient produced by the example itself, and the purple
“$\longrightarrow$” is the batch update gradient produced by labeled data.

(a) Before RLNL

(b) After RLNL

Figure 5: The t-SNE feature visualization of labeled data, unlabeled known
class data, and unlabeled unknown class data on CIFAR-10 with an openness
ratio of 0.5 before and after performing RLNL. For a more intuitive
visualization, we only show a single known class.

In RLNL, we utilize this property by exploiting the prior knowledge contained
in the labeled data. For unlabeled known class data, they might have
overlapping regions with labeled data in the feature space, benefiting from
the feature representations learned in the previous stage and the simultaneous
introduction of labeled data for negative learning. The mapping of such
examples in the feature space will remain or be close to the labeled ones in
subsequent model updates, as they will receive invisible constraints provided
by the prior knowledge from the labeled data, owing to similar features.

As shown in Figure 4, we first present the possible update scenario for
unlabeled unknown class examples in the commonly adopted batch deep learning
manner. Here, the green arrow indicates the batch update gradient produced by
itself, while the purple arrow indicates the batch update gradient produced by
labeled data. Different from Figure 3, where data oscillates on both sides of
the decision boundary, the unlabeled unknown class examples will oscillate at
uncharted away from the decision boundary to counteract the update gradient
due to the labeled ones. In contrast, unlabeled known class examples will move
much less than unknown class ones in magnitude in the feature space within the
constraints of the prior knowledge provided by the labeled data. This is
further confirmed in Figure 5, which illustrates the t-SNE feature
visualization of labeled data, unlabeled known class data, and unlabeled
unknown class data before and after performing RLNL. This ultimately leads to
the result in Figure 1(b).

###  3.3 Bidirectional Uncertainty Sampling Strategy

During the fine-tuning process, we observed that the predictions of
$f_{n}(\cdot)$ for examples in $D_{u}$ tend to oscillate between epochs. To
ensure stable sampling, on one hand, we test all unlabeled examples $t$ times
at $m$ round intervals to obtain the predicted probabilities
$\bm{p_{t}^{-}}=(p_{1}^{t},...,p_{K}^{t})$, which will further be averaged as
$\bm{\mathcal{P}^{-}}=\frac{1}{t}\sum_{i=1}^{t}\bm{p_{i}^{-}}=(\frac{1}{t}\sum_{i=1}^{t}p_{1}^{i},...,\frac{1}{t}\sum_{i=1}^{t}p_{K}^{i})$.
On the other hand, we reuse the predictions of $f_{p}(\cdot)$ to produce
predicted probabilities $\bm{p^{+}}=(p_{1},...,p_{K})$ for all unlabeled
examples, as $f_{p}(\cdot)$ are accurate for measuring known class ones.

Compared to the positive head, the negative head is slightly biased for the
measurement of sample uncertainty due to the unstable training. Therefore, if
an example is likelier to belong to the known classes, we prefer to utilize
the sample uncertainty obtained from $f_{p}(\cdot)$. On the contrary, once an
example has a higher risk of belonging to the unknown classes, the uncertainty
obtained from $f_{p}(\cdot)$ is unreliable, and thus the uncertainty by
$f_{n}(\cdot)$ should be given a higher weight.

To achieve this, we introduce two balancing factors based on global and local
observations. In open-set scenarios, some unknown class examples might be
mistakenly selected for annotation. Although these examples cannot be directly
used for training the target model, they are valuable for measuring sample
purity. Therefore, similar to Ning et al. (2022), we train a $K+1$ classifier
$f_{aux}(\cdot)$ in a normal training manner based on the examples from both
$D_{l}^{kno}$ and $D_{l}^{unk}$. Then, we can obtain the predicted probability
$p_{K+1}^{aux}(\bm{x})=f_{aux}(\emptyset\mid\bm{x})$ for each example. This
can act as a local balancing factor, since the larger the value of
$p_{K+1}^{aux}(\bm{x})$ the more likely $\bm{x}$ is to belong to the unknown
class.

Additionally, once the selected examples are sent to the oracle for
annotation, we can calculate the ratio $r$, which provides a rough estimate of
the current openness of $D_{u}$ and can serve as a global balancing factor.
With the two balancing factors, we propose a bidirectional uncertainty
sampling strategy defined as follows:

$\bm{x}^{*}=arg\max_{\bm{x}}p_{K+1}^{aux}(\bm{x})unc_{n}+r\left[1-p_{K+1}^{aux}(\bm{x})\right]unc_{p},$
(3)

where $unc_{p}$ and $unc_{n}$ denote the uncertainty of $\bm{x}$ to the
positive classifier head and the negative classifier head, respectively.
Noteworthy, this sampling strategy remains applicable even in closed-set
settings. If there are no unknown class examples, the ratio $r$ will always be
equal to 1, and $p_{K+1}^{aux}(\bm{x})$ will be 0, effectively making the
strategy equivalent to a normal uncertainty sampling strategy.

Eventually, extending the existing closed-set uncertainty-based active
learning methods to open-set scenarios is possible. In this paper, we focus on
three classical uncertainty sampling strategies: least confident sampling,
margin-based sampling, and entropy-based sampling. The corresponding modified
versions for open-set scenarios are as follows:

  * $\bullet$

Bidirectional Least Confident Sampling

$\displaystyle\bm{x}^{*}=$
$\displaystyle\mathop{\arg\max}_{\bm{x}}p_{K+1}^{aux}(\bm{x})\left[1-\bm{\mathcal{P}}_{y^{-}}^{-}(\bm{x})\right]$
(4)
$\displaystyle+r\left[1-p_{K+1}^{aux}(\bm{x})\right]\left[1-\bm{p}_{y^{+}}^{+}(\bm{x})\right],$

where $y^{-}=\mathop{\arg\max}_{y}\bm{\mathcal{P}}_{y}^{-}(\bm{x})$,
$y^{+}=\mathop{\arg\max}_{y}\bm{p}_{y}^{+}(\bm{x})$.

  * $\bullet$

Bidirectional Margin-Based Sampling

$\displaystyle\bm{x}^{*}=$
$\displaystyle\mathop{\arg\max}_{\bm{x}}p_{K+1}^{aux}(\bm{x})\left[\bm{\mathcal{P}}_{y_{1}^{-}}^{-}(\bm{x})-\bm{\mathcal{P}}_{y_{2}^{-}}^{-}(\bm{x})\right]$
(5)
$\displaystyle+r\left[1-p_{K+1}^{aux}(\bm{x})\right]\left[\bm{p}_{y_{1}^{+}}^{+}(\bm{x})-\bm{p}_{y_{2}^{+}}^{+}(\bm{x})\right],$

where $y_{1}^{-}=\mathop{\arg\max}_{y}\bm{\mathcal{P}}_{y}^{-}(\bm{x})$,
$y_{1}^{+}=\mathop{\arg\max}_{y}\bm{p}_{y}^{+}(\bm{x})$
$y_{2}^{-}=\mathop{\arg\max}_{y\setminus
y_{1}^{-}}\bm{\mathcal{P}}_{y}^{-}(\bm{x})$,
$y_{2}^{+}=\mathop{\arg\max}_{y\setminus y_{1}^{+}}\bm{p}_{y}^{+}(\bm{x})$.

  * $\bullet$

Bidirectional Entropy-Based Sampling

$\displaystyle\bm{x}^{*}=$
$\displaystyle\mathop{\arg\max}_{\bm{x}}p_{K+1}^{aux}(\bm{x})\left[-\bm{\mathcal{P}}_{y^{-}}^{-}(\bm{x})\log{\bm{\mathcal{P}}_{y^{-}}^{-}(\bm{x})}\right]$
(6)
$\displaystyle+r\left[1-p_{K+1}^{aux}(\bm{x})\right]\left[-\bm{p}_{y^{+}}^{+}(\bm{x})\log{\bm{p}_{y^{+}}^{+}(\bm{x})}\right],$

where $y^{-}$ and $y^{+}$ are consistent with the previous definition.

##  4 Experiments

Figure 6: Accuracy comparison on CIFAR-10 (first column), CIFAR-100 (second
column), and Tiny-Imagenet (third column). The ratio of unknown class examples
to the total number of examples is fixed at 0.4 (first row) and 0.6 (second
row) for each dataset. The results of 0.2 and 0.8 openness ratios are shown in
the supplementary file.

Datasets. We conduct experiments on three benchmark datasets: CIFAR-10,
CIFAR-100 Krizhevsky et al. (2009), and Tiny-Imagenet Yao and Miller (2015).
Tiny-Imagenet is a subset of the Imagenet Krizhevsky et al. (2012), consisting
of 200 classes with 500 training images per class. The openness of each
dataset is defined as the ratio of unknown classes to the total number of
classes, and we set its value to 0.2, 0.4, 0.6, and 0.8 for all datasets.

Comparing methods. We select nine query strategies for comparison, which can
be further categorized into six groups: (1) Random: Randomly select examples
from the unlabeled pool for labeling. (2) Traditional uncertainty-based
strategies: Least confident sampling (LC), Margin-based sampling (Margin), and
Entropy-based sampling (Entropy). (3) Diversity-based strategy: Coreset. (4)
Hybrid-based strategy: BADGE. (5) OSA methods: CCAL and LfOSA. (6) OSR method:
DIAS Moon et al. (2022). Correspondingly, our methods are Bidirectional Least
confident sampling (B-LC), Bidirectional Margin-based sampling (B-Margin), and
Bidirectional Entropy-based sampling (B-Entropy).

Datasets | CIFAR-10 | CIFAR-100 | Tiny-Imagenet
---|---|---|---
Openness Ratio | 0.2 | 0.4 | 0.6 | 0.8 | 0.2 | 0.4 | 0.6 | 0.8 | 0.2 | 0.4 | 0.6 | 0.8
(1) | Random | $83.3_{\pm 0.3}$ | $82.5_{\pm 0.1}$ | $87.2_{\pm 0.3}$ | $96.9_{\pm 0.5}$ | $57.6_{\pm 0.5}$ | $58.3_{\pm 0.5}$ | $58.7_{\pm 0.9}$ | $61.2_{\pm 1.0}$ | $45.7_{\pm 1.1}$ | $47.2_{\pm 0.3}$ | $50.9_{\pm 0.4}$ | $55.0_{\pm 0.9}$
(2) | LC | $84.3_{\pm 0.2}$ | $81.6_{\pm 1.0}$ | $87.5_{\pm 0.3}$ | $96.2_{\pm 1.0}$ | $55.8_{\pm 1.0}$ | $54.6_{\pm 1.3}$ | $54.0_{\pm 0.9}$ | $56.2_{\pm 1.9}$ | $44.8_{\pm 0.2}$ | $45.9_{\pm 0.4}$ | $48.4_{\pm 0.3}$ | $51.6_{\pm 0.2}$
Margin | $86.0_{\pm 0.6}$ | $84.1_{\pm 1.0}$ | $89.0_{\pm 0.4}$ | $97.0_{\pm 0.3}$ | $59.3_{\pm 0.6}$ | $59.6_{\pm 0.5}$ | $58.8_{\pm 0.9}$ | $58.9_{\pm 1.5}$ | $46.4_{\pm 0.1}$ | $47.1_{\pm 0.8}$ | $50.8_{\pm 0.3}$ | $54.0_{\pm 1.2}$
Entropy | $85.4_{\pm 0.4}$ | $83.4_{\pm 0.7}$ | $88.0_{\pm 0.1}$ | $96.8_{\pm 0.3}$ | $57.1_{\pm 0.8}$ | $56.8_{\pm 1.7}$ | $55.7_{\pm 1.0}$ | $56.4_{\pm 0.9}$ | $44.6_{\pm 0.3}$ | $44.5_{\pm 0.3}$ | $46.9_{\pm 0.6}$ | $50.7_{\pm 1.0}$
(3) | Coreset | $85.0_{\pm 0.6}$ | $81.8_{\pm 0.4}$ | $86.4_{\pm 0.3}$ | $97.4_{\pm 0.3}$ | $60.2_{\pm 0.5}$ | $61.2_{\pm 0.9}$ | $61.8_{\pm 0.2}$ | $64.2_{\pm 0.9}$ | $46.2_{\pm 0.2}$ | $47.8_{\pm 0.5}$ | $51.8_{\pm 0.2}$ | $54.0_{\pm 0.6}$
(4) | BADGE | $86.8_{\pm 0.4}$ | $84.2_{\pm 0.4}$ | $89.2_{\pm 0.5}$ | $96.4_{\pm 0.9}$ | $60.2_{\pm 0.9}$ | $60.8_{\pm 0.6}$ | $60.4_{\pm 1.5}$ | $62.0_{\pm 0.7}$ | $46.3_{\pm 0.1}$ | $47.8_{\pm 0.7}$ | $51.8_{\pm 0.2}$ | $53.3_{\pm 2.1}$
(5) | LfOSA | $73.7_{\pm 1.8}$ | $78.7_{\pm 0.3}$ | $87.0_{\pm 0.4}$ | $98.6_{\pm 0.2}$ | $52.3_{\pm 0.5}$ | $56.6_{\pm 0.4}$ | $62.4_{\pm 0.1}$ | $68.2_{\pm 0.6}$ | $42.5_{\pm 0.4}$ | $46.6_{\pm 0.1}$ | $52.4_{\pm 0.1}$ | $59.9_{\pm 1.0}$
CCAL | $80.8_{\pm 0.2}$ | $81.5_{\pm 0.3}$ | $88.0_{\pm 0.1}$ | $98.1_{\pm 0.2}$ | $55.9_{\pm 0.3}$ | $60.0_{\pm 0.1}$ | $64.7_{\pm 0.2}$ | $67.7_{\pm 0.4}$ | $44.4_{\pm 0.2}$ | $46.3_{\pm 0.4}$ | $50.3_{\pm 0.4}$ | $57.0_{\pm 0.7}$
(6) | DIAS | $81.8_{\pm 0.4}$ | $80.7_{\pm 0.5}$ | $83.0_{\pm 0.5}$ | $94.0_{\pm 1.3}$ | $55.7_{\pm 0.6}$ | $56.1_{\pm 1.1}$ | $56.9_{\pm 1.4}$ | $57.2_{\pm 1.8}$ | $43.1_{\pm 0.5}$ | $45.1_{\pm 0.5}$ | $47.5_{\pm 0.1}$ | $54.4_{\pm 0.7}$
Ours | B-LC | $\mathbf{87.0}_{\pm 1.0}$ | $87.2_{\pm 0.5}$ | $92.5_{\pm 0.2}$ | $\mathbf{99.1}_{\pm 0.1}$ | $59.3_{\pm 0.1}$ | $62.8_{\pm 0.2}$ | $67.5_{\pm 0.4}$ | $\mathbf{72.1}_{\pm 1.1}$ | $45.7_{\pm 0.2}$ | $48.7_{\pm 0.3}$ | $54.7_{\pm 0.9}$ | $60.6_{\pm 1.3}$
B-Margin | $86.5_{\pm 0.2}$ | $87.0_{\pm 0.5}$ | $\mathbf{92.6}_{\pm 0.3}$ | $98.9_{\pm 0.1}$ | $\mathbf{60.9}_{\pm 0.5}$ | $\mathbf{63.1}_{\pm 0.1}$ | $\mathbf{68.3}_{\pm 0.5}$ | $71.5_{\pm 1.0}$ | $\mathbf{46.5}_{\pm 0.1}$ | $\mathbf{49.5}_{\pm 0.5}$ | $\mathbf{55.7}_{\pm 0.1}$ | $\mathbf{61.2}_{\pm 0.7}$
B-Entropy | $86.9_{\pm 0.3}$ | $\mathbf{87.4}_{\pm 0.3}$ | $\mathbf{92.6}_{\pm 0.2}$ | $\mathbf{99.1}_{\pm 0.0}$ | $58.9_{\pm 0.6}$ | $61.7_{\pm 0.5}$ | $66.9_{\pm 0.5}$ | $71.4_{\pm 1.0}$ | $45.4_{\pm 0.3}$ | $47.5_{\pm 0.6}$ | $55.2_{\pm 0.1}$ | $61.0_{\pm 0.9}$

Table 1: The final round average accuracy (mean$\pm$std) of different methods
on CIFAR-10, CIFAR-100, and Tiny-Imagenet. The best performance is highlighted
in bold.

Training details. On CIFAR-10, CIFAR-100, and Tiny-Imagenet, we randomly
sample 1%, 8%, and 8% known class examples as the initial labeled data,
respectively. All the models involved in the experiments are ResNet18 He et
al. (2016), trained for 100 epochs, using SGD as the optimizer, where the
learning rate is 0.01, momentum is 0.9, weight decay is 1e-4, and batch size
is 128. We perform the experiments for 3 runs and report the average results.
For CIFAR-10 and CIFAR-100, 5000 examples are randomly selected from the
unlabeled pool as $D_{sub}$, and 1500 examples are queried in each query
round. Due to the doubling of data volume, we randomly select 10000 examples
as $D_{sub}$ and query 3000 examples in each query round for Tiny-Imagenet.

###  4.1 Performance Comparison

Figure 6 presents the variation curves for the classification accuracy of the
proposed methods and the comparison methods. Here, to better observe the
variation curves, we only show the B-Margin for the proposed methods and the
Margin for the compared traditional uncertainty methods. Table 1 reports the
final round average accuracy for all methods.

We can observe that our proposed methods consistently achieve the highest
classification accuracy, demonstrating the effectiveness and superiority of
our BUAL framework over other methods. Some notable observations are as
follows: 1) The OSA methods, CCAL and LfOSA, gradually lose effectiveness as
the proportion of known classes in the dataset increases. In contrast,
traditional uncertainty-based methods perform better as the openness ratio
decreases. This is consistent with our previous analysis. 2) The performance
of Coreset and BADGE also deteriorates when the openness ratio is high. These
methods tend to select examples with diverse characteristics. However, unknown
class examples often differ significantly in characteristics from the labeled
ones, making them more likely to be sampled and thus undermining the
effectiveness of this type of method. 3) The OSR method DIAS does not perform
well in all situations. The limited labeled data prevents the model from
learning a robust representation for identifying open-set examples
effectively. Moreover, DIAS cannot identify highly informative examples,
resulting in its queries often being simple and unhelpful examples. 4) All our
methods remain stable and do not suffer significantly from changes in the
openness ratio. This can demonstrate two points. The dynamic balance factors
in the proposed framework can adaptively assign appropriate weights to
positive and negative uncertainties regardless of the openness of the dataset,
and negative uncertainties are indeed effective for querying highly
informative known class examples.

Figure 7: The average recognition rate on CIFAR-10 (first column), CIFAR-100
(second column), and Tiny-Imagenet (third column).

(a) LfOSA

(b) BUAL (ours)

Figure 8: The t-SNE feature visualization of data from one query and labeled
pool on CIFAR-10 with an openness ratio of 0.5.

Figure 7 shows the average recognition rate of known class examples across
queries and openness ratios. We can observe that traditional AL methods all
perform poorly due to their inability to recognize known class examples from
those with high uncertainty and/or representative. As an OSR method, DIAS
shows only marginal improvement compared to the traditional AL methods, unable
to fully exploit its exceptional performance with limited training data. The
recognition ability of CCAL decreases slightly with the increase of dataset
categories compared to our method. It is noted that LfOSA achieved the highest
query precision on all datasets. However, combining the results in Table 1, we
can find that the performance of models trained by LfOSA is not satisfactory
compared to other methods. To explain why, we visualize the queried examples’
feature representation and labeled examples’ feature representation for our
method and LfOSA in Figure 8. We can observe that the features of examples
queried by LfOSA are highly overlapping with the labeled ones, which are often
examples that the model has already mastered and cannot provide an effective
bonus for model training. On the contrary, the sample features queried by our
method have little overlap and are more distributed in low-density regions,
consistent with the goal of AL. These results validate the effectiveness of
our approach in querying more informative examples of known classes and
maintaining a high recognition rate.

###  4.2 Ablation Study

The ablation study is conducted on CIFAR-10 with an openness ratio of 0.6 to
validate the effectiveness of each component in our proposed query strategy
(Equation 3). The final round accuracy is shown in Table 2. Here,
$\bm{unc\\_n}$ and $\bm{unc\\_p}$ indicate that only $unc_{n}$ and $unc_{p}$
is adopted for active sampling, respectively. $\bm{w/o}$ $\bm{w}$ denotes the
removal of all balancing factors, i.e., both $f_{aux}$ and $r$. $\bm{w/o}$
$\bm{f_{aux}}$ means only removing the local balancing factor $f_{aux}$.

We can observe that removing any of the components leads to performance
degradation. Although $\bm{unc_{n}}$ and $\bm{unc_{p}}$ are significantly less
effective than B-LC, $\bm{unc_{n}}$ has a substantial improvement compared to
$\bm{unc_{p}}$ due to its ability to distinguish informative examples of known
classes from examples of unknown classes. The direct combination of $unc_{n}$
and $unc_{p}$, i.e., $\bm{w/o}$ $\bm{w}$, works better than $\bm{unc\\_n}$, as
models trained by RLNL may produce oscillate output and thus the uncertainty
obtained in $\bm{unc\\_n}$ is not necessarily accurate. By adding the dynamic
global balancing factor $r$, $\bm{w/o}$ $\bm{f_{aux}}$ achieves a better
performance. However, it still falls short in comparison to B-LC, which
validates the effectiveness of local balancing factor $f_{aux}$. These results
further corroborate the soundness of our strategy design.

Dataset Method | $\bm{unc_{p}}$ | $\bm{unc_{n}}$ |  $\bm{w/o}$ $\bm{w}$ |  $\bm{w/o}$ $\bm{f_{aux}}$ | B-LC
---|---|---|---|---|---
CIFAR-10 | 87.5 | 89.4 | 90.8 | 91.3 | 92.5
CIFAR-100 | 54.0 | 63.5 | 62.4 | 65.0 | 67.5
Tiny-Imagenet | 48.4 | 52.3 | 52.0 | 53.0 | 54.7

Table 2: Final accuracy of each component in Equation 3 on CIFAR-10,
CIFAR-100, and Tiny-Imagenet with an openness ratio of 0.6.

##  5 Conclusion

In this paper, we successfully expand the existing uncertainty-based active
learning methods to complex open-set scenarios by proposing a Bidirectional
Uncertainty-based Active Learning (BUAL) framework. On one hand, to achieve
the goal that distinguishing known and unknown class examples with high
uncertainty, we propose a simple but effective Random Label Negative Learning
(RLNL) method for pushing unknown and known class examples toward the high and
low confidence regions respectively. On the other hand, to better measure
sample uncertainty, we propose a Bidirectional Uncertainty (BU) sampling
strategy by dynamically fusing the sample uncertainty obtained from positive
learning and negative learning. The dynamic balancing factors in it can ensure
that the strategy is effective under various openness ratios. Extensive
experimental results show that the model trained with BUAL can achieve state-
of-the-art performance under complex and ever-changing open-set scenarios.

## References

  * Ash et al. [2019] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal.  Deep batch active learning by diverse, uncertain gradient lower bounds.  arXiv preprint arXiv:1906.03671, 2019.
  * Balcan et al. [2007] Maria-Florina Balcan, Andrei Broder, and Tong Zhang.  Margin based active learning.  In International Conference on Computational Learning Theory, pages 35–50. Springer, 2007.
  * Du et al. [2021] Pan Du, Suyun Zhao, Hui Chen, Shuwen Chai, Hong Chen, and Cuiping Li.  Contrastive coding for active learning under class distribution mismatch.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8927–8936, 2021.
  * Feng et al. [2020] Lei Feng, Takuo Kaneko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama.  Learning with multiple complementary labels.  In International Conference on Machine Learning, pages 3072–3081. PMLR, 2020.
  * Fu et al. [2013] Yifan Fu, Xingquan Zhu, and Bin Li.  A survey on instance selection for active learning.  Knowledge and information systems, 35(2):249–283, 2013.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * Holub et al. [2008] Alex Holub, Pietro Perona, and Michael C Burl.  Entropy-based active learning for object recognition.  In 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, pages 1–8. IEEE, 2008.
  * Huang et al. [2010] Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou.  Active learning by querying informative and representative examples.  Advances in neural information processing systems, 23, 2010.
  * Huang et al. [2021] Sheng-Jun Huang, Chen-Chen Zong, Kun-Peng Ning, and Hai-Bo Ye.  Asynchronous active learning with distributed label querying.  In IJCAI, pages 2570–2576, 2021.
  * Ishida et al. [2017] Takashi Ishida, Gang Niu, Weihua Hu, and Masashi Sugiyama.  Learning from complementary labels.  Advances in neural information processing systems, 30, 2017.
  * Kim et al. [2019] Youngdong Kim, Junho Yim, Juseung Yun, and Junmo Kim.  Nlnl: Negative learning for noisy labels.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 101–110, 2019.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25, 2012.
  * Lee et al. [2021] Jin-Ha Lee, Marcella Astrid, Muhammad Zaigham Zaheer, and Seung-Ik Lee.  Deep visual anomaly detection with negative learning.  In International Workshop on Frontiers of Computer Vision, pages 218–232. Springer, 2021.
  * Li and Sethi [2006] Mingkun Li and Ishwar K Sethi.  Confidence-based active learning.  IEEE transactions on pattern analysis and machine intelligence, 28(8):1251–1261, 2006.
  * Luo et al. [2021] Xin Luo, Wei Chen, Yusong Tan, Chen Li, Yulin He, and Xiaogang Jia.  Exploiting negative learning for implicit pseudo label rectification in source-free domain adaptive semantic segmentation.  arXiv preprint arXiv:2106.12123, 2021.
  * Mahmood et al. [2021] Rafid Mahmood, Sanja Fidler, and Marc T Law.  Low budget active learning via wasserstein distance: An integer programming approach.  arXiv preprint arXiv:2106.02968, 2021.
  * Moon et al. [2022] WonJun Moon, Junho Park, Hyun Seok Seong, Cheol-Ho Cho, and Jae-Pil Heo.  Difficulty-aware simulator for open set recognition.  arXiv preprint arXiv:2207.10024, 2022.
  * Ning et al. [2021] Kun-Peng Ning, Lue Tao, Songcan Chen, and Sheng-Jun Huang.  Improving model robustness by adaptively correcting perturbation levels with active queries.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9161–9169, 2021.
  * Ning et al. [2022] Kun-Peng Ning, Xun Zhao, Yu Li, and Sheng-Jun Huang.  Active learning for open-set annotation.  arXiv preprint arXiv:2201.06758, 2022.
  * Ren et al. [2021] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang.  A survey of deep active learning.  ACM computing surveys (CSUR), 54(9):1–40, 2021.
  * Roy and McCallum [2001] Nicholas Roy and Andrew McCallum.  Toward optimal active learning through sampling estimation of error reduction. int. conf. on machine learning.  2001\.
  * Salehi et al. [2021] Mohammadreza Salehi, Hossein Mirzaei, Dan Hendrycks, Yixuan Li, Mohammad Hossein Rohban, and Mohammad Sabokrou.  A unified survey on anomaly, novelty, open-set, and out-of-distribution detection: Solutions and future challenges.  arXiv preprint arXiv:2110.14051, 2021.
  * Scheirer et al. [2012] Walter J Scheirer, Anderson de Rezende Rocha, Archana Sapkota, and Terrance E Boult.  Toward open set recognition.  IEEE transactions on pattern analysis and machine intelligence, 35(7):1757–1772, 2012.
  * Sener and Savarese [2017] Ozan Sener and Silvio Savarese.  Active learning for convolutional neural networks: A core-set approach.  arXiv preprint arXiv:1708.00489, 2017.
  * Settles [2009] Burr Settles.  Active learning literature survey.  2009\.
  * Sinha et al. [2019] Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell.  Variational adversarial active learning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5972–5981, 2019.
  * Yao and Miller [2015] Leon Yao and John Miller.  Tiny imagenet classification with convolutional neural networks.  CS 231N, 2(5):8, 2015.
  * Yoo and Kweon [2019] Donggeun Yoo and In So Kweon.  Learning loss for active learning.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 93–102, 2019.
  * You et al. [2014] Xinge You, Ruxin Wang, and Dacheng Tao.  Diverse expected gradient active learning for relative attributes.  IEEE transactions on image processing, 23(7):3203–3217, 2014.
  * Yu et al. [2018] Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao.  Learning with biased complementary labels.  In Proceedings of the European conference on computer vision (ECCV), pages 68–83, 2018.