# Symbolic Computation in Software Science:
My Personal View

Bruno Buchberger Research Institute for Symbolic Computation (RISC)
Johannes Kepler University
Linz / Schloss Hagenberg, Austria<EMAIL_ADDRESS>
###### Abstract

In this note, I develop my personal view on the scope and relevance of
symbolic computation in software science. For this, I discuss the interaction
and differences between symbolic computation, software science, automatic
programming, mathematical knowledge management, artificial intelligence,
algorithmic intelligence, numerical computation, and machine learning. In the
discussion of these notions, I allow myself to refer also to papers (1982,
1985, 2001, 2003, 2013) of mine in which I expressed my views on these areas
at early stages of some of these fields.

## The Intention of This Note

It is a great joy to see that the SCSS (Symbolic Computation in Software
Science) conference series, this year, experiences its 9th edition. A big
Thank You to the organizers, referees, and contributors who kept the series
going over the years! The series emerged from a couple of meetings of research
groups in Austria, Japan, and Tunisia, including my Theorema Group at RISC,
see the home pages of the SCSS series since 2006. In 2012, we decided to
define “Symbolic Computation in Software Science” as the scope for our
meetings and to establish them as an open conference series with this title.

As always, when one puts two terms like “symbolic computation” and “software
science” together, one is tempted to read the preposition in between - in our
case “in” - as just a set-theoretic union. Pragmatically, this is reasonable
if one does not want to embark on scrutinizing discussions. However, since I
was one of the initiators of the SCSS series, let me take the opportunity to
explain the intention behind SC in SS in this note. Also, this note, for me,
is a kind of revision and summary of thoughts I had over the years on the
subject of SCSS and related subjects. Hence, allow me to refer to a couple of
my papers with basic considerations on the subject. I do not discuss, however,
any of my technical contributions to the subject of SCSS (which would be,
mainly, Gröbner bases and the Theorema system). In some way, this note
continues, updates, and specializes the note on mathematics in the 21st
century I gave at the beginning of SCSS 2013, see [4], from which I quote:

> In my view, mathematics of the 21st century will evolve as a unified body of
> mathematical logic, abstract structural mathematics, and computer
> mathematics with no boundaries between the three aspects. Working
> mathematicians will have to master the three aspects equally well and
> integrate them into their daily work. More specifically, working in
> mathematics will proceed on the object level of developing new mathematical
> content (abstract knowledge and computational methods) and, at the same
> time, on the meta-level of developing automated reasoning methods for
> supporting research on the object level. This massage of the mathematical
> brain by jumping back and forth between the object and the meta-level will
> guide mathematics onto a new level of sophistication. Symbolic computation
> is just a way of expressing this general view of mathematics of the 21 st
> century and it also should be clear that software science is just another
> way of expressing the algorithmic aspect of this view.

Continuing the discussion on the intended meaning of “Symbolic Computation in
Software Science” in this note will hopefully help to advocate the central
importance of this topic for the future of mathematics, logic, and computer
science. This should also motivate more and more people to submit papers to
the conferences in the SCSS series.

## What is Symbolic Computation?

In 1984, Academic Press London issued a call for designing a new journal for a
new field that had emerged approximately since 1960. Various names were in use
for this field: computer algebra, symbolic and algebraic manipulation,
analytic computation, formula manipulation, computation in finite terms,
symbolic computation, and others. As a response to this call, I submitted a
proposal to Academic Press for a “Journal of Symbolic Computation”. My
proposal was selected and my clarification of the scope of “symbolic
computation” formed also the Editorial of the journal, see [3].

I defined “symbolic computation” as the area that deals with algorithms on
symbolic objects, and I proposed “symbolic objects” to be defined as finitary
representations of infinite mathematical entities. Here, “finitary” means
“storable in a computer memory”. For example, finitely many generators with
finitely many relations between words formed from the generators form a
finitary object that may represent an infinite group (or, at least, a “large”
group, i.e. a group whose number of elements is much much larger than the size
of the finitary representation). Algorithms can only work on finitary objects
and the flavor of “symbolic” is exactly the point that we want to solve
problems on infinite (or “large”) mathematical entities by finding algorithms
that work on finitary (small), “symbolic”, representations of these entities.
Also, numerical computation works on finitary representations (for example,
lists of rational numbers that represent a function consisting of infinitely
many pairs of real numbers). In this sense, numerical computation is a
subfield of symbolic computation. However, usually, for algorithms to be
called “symbolic” we request that the representation of the abstract
mathematical domains by finitary domains must be an isomorphism w.r.t. to the
operations on the objects we study. In numerical computation, for the sake of
efficiency, this request has to be given up. Instead, we are satisfied with
“approximations”.

Pragmatically, in the editorial of the Journal of Symbolic Computation, I
named three main areas for symbolic computation: computer algebra, automated
reasoning, and “automatic programming”. I also emphasized that all aspects of
these areas should be in the scope of the Journal of Symbolic Computation:
mathematical theory on which symbolic algorithms can be based, the algorithms
with their correctness proofs and complexity analysis, the details of the
implementation of the algorithms, languages and software systems for symbolic
computation, and applications. Indeed, the three main branches of symbolic
computation consider three important classes of “symbolic objects”:

  * –

computer algebra: symbolic objects that represent algebraic entities like
terms that represent functions, differential operators, etc. or finite
relations that represent residue class structures;

  * –

automated reasoning: symbolic objects containing (quantified) variables that
are considered as statements on (infinite) domains;

  * –

automatic programming: symbolic objects containing variables that are
considered as programs that define processes on potentially infinitely many
inputs.

(Of course, these three sub-areas of symbolic computation are intimately
connected and, in some precise way, even embedded in each other. The
distinction between the three areas is more or less only a matter of
“flavor”.)

In other words, symbolic objects are finitary objects that have “semantics”
attached to them where, typically, the semantics is “large”, even infinite,
not tangible by computers whereas the symbolic objects are “small”, finitary,
tangible by algorithms. Any field of mathematics can be studied under the
“symbolic” view and, actually, in any field of mathematics, if we want to
solve problems by algorithms, we have to find finitary representations for the
objects in the field. Finding suitable finitary representations, by itself,
may be a difficult - sometimes provably impossible - mathematical problem:
Before embarking on deeper questions, deciding whether or not two symbolic
objects represent the same abstract mathematical object and finding
“canonical” representatives for symbolic objects may already be very difficult
(sometimes provably impossible). By finding representations of mathematical
objects in any field of mathematics, the field becomes “algebraic”, and
problems in the algebraic disguise of the field, essentially, become
combinatorial problems. Thus, very sketchy, one may say: symbolic computation,
ultimately, is the “combinatorization” of all of mathematics via finitary
representations of infinite mathematical entities.

It is a common misunderstanding that symbolic computation is the trivial side
of mathematics, i.e. some people believe that, whereas “pure” mathematics
lives in difficult spaces needing deep and difficult thinking, algorithmic
mathematics (which must be “symbolic” in the above sense) “just” puts
everything to the computer and presses the start button. The truth is, that
the “just” needs more and deeper mathematics than a mathematics that allows
non-algorithmic constructions for problem-solving like the unlimited set
quantifier, infinite summation, infinite unions, transition to residua class
domains etc. (A trivial example: In “pure” mathematics, a Gröbner basis for
given ideal generators can be “easily” found by just taking the ideal
generated by the generators. However, the definition of the ideal generated by
generators involves an infinite set construction!) Hence, with some
provocation, in my view, mathematics only starts at the moment when it tries
to solve problems by “symbolic computation”.

Recently, in 2020, we issued a call for running for the editor-in-chief
position of the Journal of Symbolic Computation (JSC). At that occasion, we
asked the candidates to submit also their views on the scope of “symbolic
computation” and of the JSC. Interestingly, the view of symbolic computation
in the editorial of the JSC (and summarized above) was backed by all
candidates and, basically, no dramatic changes or extensions were proposed
except that “artificial intelligence” was mentioned a couple of times.

Mentioning artificial intelligence, for me, raises some nostalgia because,
when I founded the Research Institute for Symbolic Computation (also in 1985),
for some time I was torn between using “symbolic computation” or “artificial
intelligence” as the main notion in the name of the new institute. At that
time, bringing symbolic computation under the umbrella of artificial
intelligence was quite tempting and also quite common: For example, finding
symbolic integrals was considered an “artificial intelligence” task like
playing chess, with lots of heuristics. Correspondingly, the most
comprehensive symbolic computation software system at that time, MACSYMA, had
“MAC” ($=$ Machine Aided Cognition) in its name! And, of course, implementing
heuristics is still a very important approach for improving the practical
efficiency of methods for symbolic computation problems. However, in 1985, I
deliberately decided against having “artificial intelligence” in the name of
my institute since I wanted to emphasize the logical, mathematical, formal
approach to problem-solving over the psychological, experimental aspect, which
some people (then and now) believe that goes “beyond mathematics”. I will go
deeper into the analysis of the relationship between symbolic computation and
artificial intelligence later in this note.

Anyway, although symbolic computation (in the sense of the editorial of the
JSC) seems to be a quite established and stable notion, as a matter of fact,
in the JSC over the years one can observe that

  * –

the majority of papers in the JSC is on computer algebra,

  * –

more and more, but still much fewer, papers are in automated reasoning,

  * –

only a few papers came in on automatic programming.

## Symbolic Computation in Software Science

Software science is the science of the process of developing software. This
process starts from problems in some “reality” (part of the real world) and
creates software that solves the problems in an appropriate finitary model of
this reality. Since the beginning of the software age, the software
development process has matured from being a kind of “magic” and being an
“art” to a decent engineering discipline called “software engineering”. In
parallel, since the very beginning, people have also tried to establish a
“science” of software and the software development process to make the process
more reliable, provably correct, faster, more flexible, more economic, and
ultimately automatic or semi-automatic. Research in this direction is mostly
summarized under the heading “theoretical computer science”. Interestingly,
the term “software science”, which seems quite natural to me, in comparison to
“theoretical computer science”, is only used quite rarely. (This can easily be
verified by googling the two notions and comparing the number of relevant
results.)

Anyway, I think that “software science” is a quite useful notion that focuses
on the actual development process of software and on its automation and,
hence, has a high impact on one of the central technologies - if not the
central technology - of our age.

Since the objects of software science are formal models (domains with finitary
objects and algorithmic operators on the objects), automation or semi-
automation of the software design process is essentially a “symbolic
computation” process according to the definition of symbolic computation we
considered above. In other words, it should be clear that symbolic computation
is the area that naturally should include also the (semi-)automation of the
software development process. Unfortunately, this logical analysis did not
really create a big stream of papers on automating software development to the
JSC (and neither to conferences in the area of symbolic computation like
ISSAC, ACA, SYNASC, etc.). Therefore, in 2012, I argued that the topic
“Symbolic Computation in Software Science” could and should get special
attention by turning our group meetings into a conference series with this
name.

Still, the idea that symbolic computation should have a major application in
software science - in particular in the automation of the software development
process - did not create a big echo in the symbolic computation community.
Neither do many people who work in software engineering realize that the
automation of the software development process is essentially a symbolic
computation task. One reason for this is, surely, that there are strong
conference series and journals in the area of automated reasoning and related
subjects. (A side-remark: As some readers may know, when I built up RISC
starting from 1985, I also devoted much of my time to building up the
“Softwarepark Hagenberg”. With this, I wanted to demonstrate that the
mathematically deep field of symbolic computation has also the power to create
something with a strong practical impact: I started the Softwarepark with 25
people. When I stepped back as the director of the Softwarepark Hagenberg in
2013, 2500 people working and/or studying in the Softwarepark. I hoped that
the government and the administration of my university would have noticed and
recognized the unique power that RISC / symbolic computation had created and
had turned into innovation in the software foundations, into software
development, and into software business. Therefore, in 2013, I asked the
government and university administration to establish an extra professorship
“Software Science” in the frame of RISC with the task of continuing my work
for directing and expanding the Softwarepark based on solid research on
symbolic computation in software science. Indeed, in response to my request
and argumentation, a professor position for “Software Science” was created but
then, much to my displeasure, giving in to the pressure of the informatics
department, the position was finally used for something “more useful” for the
education of the informatics undergraduates.)

Now, what I called “automatic programming” in the preface of the JSC, could
also be called “symbolic computation in software science”. In more detail, I
want to make this clear in this note. If seen in the right way, I think that
symbolic computation in software science is / could be / should be the most /
one of the most fascinating topics of the next stage of mathematics / logic /
computer science. (I like to call mathematics, logic, and computer science
together “thinking technologies” or just “full-stack mathematics”.
Unfortunately, “mathematics” sounds old-fashioned to some people, sounds “non-
creative” to others, boring to others, intimidating to again others. However,
one may bend and turn this as one likes, finally, at the top of the creative
hierarchy of problem-solving and gaining knowledge by thinking, there is
mathematics at higher and higher levels - whether certain people in politics,
science, economy, philosophy, culture, media or the people at the beer table
like it or not.)

## A Stream of Problems on the Way

On the way from a problem description / a collection of problem descriptions
to an algorithm / program / software system that solves the problem there are
many creative steps each of which can be handled ad hoc for the particular
problem at hand by a mathematician, computer scientist, developer. Each of
these steps, however, can also be considered as a problem on the meta-level
with some symbolic objects (like software requirements, programs, algorithm
schemata, verification conditions, etc.) as input and symbolic objects as
output for which we would like to have a general algorithmic solution.

In this section, we assume that all the symbolic objects on the way from a
problem specification/requirements to an algorithm / piece of software are
expressions that describe or at least try to describe something “in general
terms”. In particular, we assume that the problem specification (even a vague
attempt of a specification that may need much clarification and reformulation)
tries to describe the problem in general and not only by examples.

The important case that a problem specification, for certain reasons, can only
be given by examples and cannot be explained in general terms, is analyzed in
detail in the next section in the paragraph on machine learning.

In the majority of cases, problem specifications are explicit in the sense
that they are specified by an expression $P[x,y]$ with input variable(s) $x$
and output variables(s) $y$, and a solution algorithm $A$ has to satisfy
$P[x,A[x]]$, for all $x$. (However, there are important classes of algorithmic
problems that cannot be described in explicit form. For example, a canonical
simplifier $A$ for an equivalence relation $P$ cannot be described in this
form. More generally, for example, the specification of operations on data
structures by axioms or the construction of algorithmic isomorphic
representations of mathematical domains is not an explicit specification. We
cannot go into more details about this here.)

Depending on the situation, the initial (often vague) problem descriptions may
be given in natural language, maybe mixed with drawings and diagrams, or in
some formal language.

Also, it is important to distinguish between two extremes:

  * •

Finding algorithms for fundamental, non-trivial, stand-alone algorithmic
problems: In this case, the problem specification and the solution algorithm
are completely formal, symbolic objects and everything that happens between
problem and solution should be amenable to algorithmic treatment on the meta-
level, i.e. to symbolic computation. For such problems, typically, time and
memory complexity is an issue. Examples: the problem of finding shortest paths
in graphs; the problem of finding symbolic integrals; the problem of finding
Gröbner bases; etc.

  * •

Developing software for an entire application: In this case, the individual
parts of the system (called “units”) should implement a (big) number of
functionalities, most of which are not really difficult. Only some of the
functionalities may involve the algorithmic solution of fundamental problems.
The algorithms for these functionalities, typically, are known and taken from
reliable sources. The complexity of such systems originates from the huge
number of units and the various (desired and undesired) interactions of the
units. Also tuning of the known algorithms to the application at hand is an
issue.

This distinction is important for the following reason: The application of
formal methods for establishing the correctness of software only makes sense
if we consider non-trivial algorithmic problems. In contrast, for most of the
millions of units to be developed in large software systems a formal
specification of the problem to be solved by the unit would be essentially
identical to the code to be developed. In other words, a proposal for the code
of a unit, in the case of “easy” problems, is a way for describing the problem
to be solved. This is the reason why rapid prototyping and agile software
development, in such situations, is so useful. It is also the reason why
formal algorithm verification methods are rarely used in the practice of
developing large software systems.

Example. In a calendar software system, probably, we want one unit that should
check whether a proposed new calendar entry collides with one of the existing
entries. Let us assume that a calendar entry is characterized by its start
time and end time. The input to the unit will then consist of four time
moments $s_{\\_}1,e_{\\_}1,s_{\\_}2,e_{\\_}2$ for the start time and the end
time of the first and the second entry, respectively, with input condition
$s_{\\_}1<e_{\\_}1$ and $s_{\\_}2<e_{\\_}2$. “After some thinking”, the
problem will then be described by most developers by a sentence like this:
“The two calendar entries characterized by
$s_{\\_}1,e_{\\_}1,s_{\\_}2,e_{\\_}2$ collide iff $s_{\\_}2\leq s_{\\_}1\leq
e_{\\_}2$ or $s_{\\_}1\leq s_{\\_}2\leq e_{\\_}1$.” Now it is clear that this
“specification” of the problem is, basically, already the solution algorithm.
Only some transformation into the syntax of the programming language used is
necessary. No powerful algorithm verification method or algorithm synthesis
method is necessary in such a case.

As simple as the example is, it is not too simple to guarantee the avoidance
of severe flaws in the development. I tested the example out by presenting it
to various (reasonably experienced) developers. Amazingly, a few came up with
the following specification / code: “The two calendar entries characterized by
$s_{\\_}1,e_{\\_}1,s_{\\_}2,e_{\\_}2$ collide iff either $s_{\\_}2\leq
s_{\\_}1\leq e_{\\_}2$ or $s_{\\_}2\leq e_{\\_}1\leq e_{\\_}2$.” This
specification is “incorrect” because it does not include the case
$s_{\\_}1<s_{\\_}2<e_{\\_}2<e_{\\_}1$, which of course “everybody” would also
consider as a collision, even a “particularly heavy one”. (I put “incorrect”
in quotation marks because, at the very first stage of uttering a request, the
“customer is always right”. Maybe, he really wants what he tells! Either one
just implements what he tells or one may consider the subsequent discussion as
a way to find out what he “really wants” or to change his mind about what he
wants.) This shows that already in the “thinking” between a vague indication
of a problem and its specification (by a general statement, not only by
examples), severe mistakes may be made (or, considered differently, the
request of the customer may undergo serious changes). In our example, we also
could start a little “earlier” and just say: “The two calendar entries
characterized by $s_{\\_}1,e_{\\_}1,s_{\\_}2,e_{\\_}2$ collide iff the time
interval $\left[s_{\\_}1,e_{\\_}1\right]$ intersects with the time interval
$\left[s_{\\_}2,e_{\\_}2\right]$.” Now we could question the notion
“intersects” and might agree on the following: “The two calendar entries
characterized by $s_{\\_}1,e_{\\_}1,s_{\\_}2,e_{\\_}2$ collide iff there is a
time moment x such that $s_{\\_}1\leq x\leq e_{\\_}1$ and $s_{\\_}2\leq x\leq
e_{\\_}2$.” In this form, we can send the condition into a quantifier
elimination algorithm and we will get an answer which will be equivalent to
“$s_{\\_}2\leq s_{\\_}1\leq e_{\\_}2$ or $s_{\\_}1\leq s_{\\_}2\leq
e_{\\_}1$.” (Please try it out, it is worthwhile!) Hence, this simple example
shows that, actually, already in the very early stage of discussing and
clarifying even seemingly simple requirements a lot of systematic/formal
thinking is involved, which in principle should be amenable to automating and,
hence, symbolic computation!

Thus, we start at the very early stage of having a vague desire of achieving
something by software and go through all the stages of developing a piece of
software that fulfills the desire and, further, through all the stages of
maintaining, updating, improving, and integrating pieces of software to
fulfill more and more sophisticated desires. Through all these stages, we ask
ourselves how much of this process can be (semi-)automated. This gives a rich
list of R$\&$D topics, which make up the important topics in the scope of
“symbolic computation in software science” as described in the calls for the
SCSS series, see the latest version in the call for SCSS 2021. This call
contains, roughly, 20 important and quite diverse but strongly interconnected
topics on the way from requirements to software.

I do not list these topics and comment on all these topics here. Rather, let
me give some personal remarks that emphasize, and maybe expand, some of the
subjects, themes, and objectives of the topics in the SCSS calls.

  * •

My feeling is that relatively little research is available on
(semi-)automating the development of large software systems consisting of tons
of simple “units” of the type we have seen above in the example. Research has
focused more on symbolic methods for algorithm verification and synthesis for
non-trivial algorithms. In some way, this is unfortunate because the
construction of tons of software is necessary today, semi-automation of this
process is needed and could be a big business. Our research results are too
much oriented on automating the invention of “important”, “difficult”
algorithms. However, the (semi-) automation of the development of huge amounts
of simple programs and their interaction, in some way, is quite challenging,
much needed, and asks for formal methods to guarantee the quality of the
process.

  * •

As a variant of developing big software systems consisting of many simple
units we also should consider the task of re-engineering big software systems
that were written years ago in programming languages that are antiquated now.
Often, the documentation of such systems is lost or fragmentary, and finding
out what the units should do, i.e. getting a problem specification from code,
is a major task.

  * •

In most cases, software development starts from vague requirements in natural
language (maybe with diagrams or drawings). The task is to come up, maybe in
an interactive dialogue, with a bunch of formal requirements. Here, we should
allow natural language or, maybe, a simplified version of natural language as
a symbolic language: The sentences that formulate requirements are “finitary”
with infinite semantics since, normally, requirements have hidden universal
quantifiers in it. (See the simple example above: The requirement is
formulated for arbitrary calendar entries. In our first step towards
formalization, the hidden universal quantifier goes over
$s_{\\_}1,e_{\\_}1,s_{\\_}2,e_{\\_}2$.) We also should allow diagrams or
drawings as symbolic objects: They are surely “finitary” and, usually, have
infinite semantics, since a drawing normally tries to convey the important
features of infinitely many possible individual situations. Specifying
requirements by natural language text or drawings is very different from the
specification of requirements by finitely many input/output pairs, see the
analysis of “machine learning” in the next section. Allowing natural language
or drawings in requirements is of course a big challenge but I think we should
take this deliberately under the umbrella of SCSS because it will need much
more than just ordinary NLP (natural language processing) and graphics.
Rather, a systematic connection to logic is necessary. (In fact, in dynamic
geometry systems a lot of work in this direction is already done when
graphical input explaining geometrical situations “in general positions” is
allowed.)

  * •

As we have seen in the simple example above, we also would like to go a step
further and go from requirements in natural language and/or drawings right
away to algorithms/programs that satisfy the requirements. As we have argued
in the example, in the majority of “units” in application software systems
this will not be significantly more difficult than coming up with formal
requirements.

  * •

The individual algorithms/programs in software systems do not live in empty
air but inside a whole hierarchy of data structures and domains which,
depending on the context, are called (algorithmic) “models” of reality. Such
models consist of problem specifications, definitions of notions, knowledge,
algorithms, and - in the ideal case - arguments/proofs why the
operations/algorithms in the system meet their specifications. Hence, seen in
this way, software systems can also be considered mathematical knowledge
systems. Hence, (semi-)automation of building and maintaining such systems can
also be seen under the umbrella of Mathematical Knowledge Management (MKM). We
introduced this term a couple of years ago in a slightly different context,
see the preface of the proceedings [5], which were expanded as the special
issue [6]. We propose that SCSS and MKM should be considered together and,
maybe, SCSS and MKM should be collocated in the future.

  * •

In practice, the correctness of software is established by testing rather than
by formal verification. Testing is a highly developed “technology” in software
engineering: There is an arsenal of “automated software testing” systems
available. They are well integrated into the various software development
environments and they are quite helpful for managing large test suites for the
consecutive versions of software systems. However, I think that much more
could be done by applying formal methods for coming up with complete systems
of test data from a given problem specification and program. Here,
completeness means that we would get one test input/output for each
equivalence class of inputs that generate the same program path during
execution. Of course, in general, the set of these equivalence classes is not
finite. However, in the practical case of large software systems consisting of
a huge number of relatively simple units, the set of equivalence may well be
finite, see the example above. As can be seen in the example, generating a
complete system of equivalence classes for inputs might be essentially the
same task as coming up with the code for the program. In fact, this automated
generation of equivalence classes should start from the problem specification
and not from a program code - as most of the commercial “white box” test
generation programs do.

## How Does Artificial Intelligence Fit into the Picture?

Undoubtedly, in the past two decades, artificial intelligence has gained
enormous attention. This is due to the fact that, by the drastically increased
computational power of current computer systems and the availability of huge
databases of “labeled” data, a couple of difficult and urgent problems have
received impressive solutions by artificial intelligence methods, as for
example machine translation of natural languages.

Amazingly, there is still a lot of mystery, nebulosity, and misunderstanding
around what artificial intelligence (AI) actually is and why it is / may be /
is believed to be essentially different from all computational approaches so
far. This nebulosity is all over the place: in politics, in the media, even in
science, and, of course, with the man on the street. At times, I have the
impression that even quite some researchers in the AI area do not have a very
clear picture of the distinctive characteristics of AI when compared with
other computational approaches. Also, labeling a project with AI, may have a
beneficial effect when it comes to funding, societal respect, political
influence etc. Thus, it is tempting to keep the notion ambiguous. What amazes
me, even more, is that the nebulosity about the essence of AI did not
disappear since the field started in the middle of the fifties. I remember
talks of AI evangelists around 1980, i.e. in the “first wave of AI research”,
who believed and spread that “AI can solve hard problems that cannot be solved
by mathematics”. And still, when I participate in political discussions about
the importance of mathematical education (in the sense of training
mathematical thinking), I hear the argument that, actually, the ability to do
mathematics will be less and less important because “tedious” mathematical
thinking, in the presence of “artificial intelligences” (plural!), will not be
necessary anymore and that we should teach the youngsters more “creative”
things than mathematics.

Now all such statements may be true or false according to which notion of
artificial intelligence one has in mind. For clarifying this notion, I want to
distinguish three possible characterizations of AI:

Hard Problems:

Artificial Intelligence may be described as the field that tries to solve
problems that, at a certain historic moment, are considered to be “hard” in
the sense that they apparently need a decent amount of (human) “intelligence”
to solve them. For example, playing chess or finding symbolic integrals, at
some historic moment, were considered as needing human intelligence.
Algorithms (invented by humans!) that finally were able to solve these
problems were then (and still are) considered to be the result of “AI
research”.

Now, in my opinion, this definition of the notion of AI is quite shallow. It
is the natural flow of science and technology that we can solve harder and
harder problems automatically, i.e. by algorithms. However, from some point
on, people think that now “algorithms are taking over”, “artificial
intelligence is replacing humans” etc. forgetting that this happened and
happens already since centuries and that this is the very goal of science and
technology. And, of course, whatever the methods behind automation were and
are, we humans should stay in control and decide how far we let problems be
solved and decisions be taken by algorithms. Anyway, the notion of a “hard”
problem is relative and “hard” problems for which an algorithmic solution was
finally found very soon are considered to be “easy” by the consumer. For
example, car drivers nowadays take the functionality of a navigation system
for granted. Some thirty years ago, the current functionality of navigation
systems would have been considered unbelievably intelligent. In fact, the
stack of scientific findings and algorithmic techniques involved in a
navigation system for guiding a driver from $A$ to $B$ is quite deep.

In my opinion, one should not use the notion of “artificial intelligence” for
“finding algorithms for hard problems” but rather continue to call this just
“mathematical, algorithmic solution of hard problems”. Attaching the label
“AI” to algorithms depending on whether they solve hard or easy problems is
more a question of marketing rather than a logically sound distinction.

Simulate the Brain:

A completely different view (and branch) of artificial intelligence is
artificial intelligence as the science of understanding and simulating
biological structures that show “intelligence”, notably the human brain. This
type of AI research, historically, was one of the origins of the field of AI
that started, maybe, 1943 with the investigations of W. McCulloch and W. Pitts
who introduced a simple mathematical model of the functionality of a neuron.
Of course, understanding and simulating the most complex biological systems,
which are commonly considered to display “intelligence”, is a highly
fascinating and relevant undertaking. Well, why not call this type of research
“artificial intelligence” in the same way as a technical realization of the
phenomenon of flying could be called “artificial flying”.

“Artificial intelligence” in the sense of brain simulation has little overlap
with symbolic computation in software science except that, of course, there
may be applications of symbolic computation in developing models of the brain.
Also, studying biological structures (like the brain, like swarms of animals,
or like the evolution of life on earth) motivated some of the algorithmic
methods that today are called “AI methods”, see next paragraphs.

“Intelligent” Methods:

The third approach of characterizing artificial intelligence is by specifying
certain algorithmic methods as “intelligent”. These algorithms would
constitute the area of “artificial intelligence”. I hope I do not overlook
something important but my impression is that, essentially, “machine learning”
is the only such method or, better, class of methods that has not already been
around before the term “artificial intelligence” was coined. The many other
algorithmic methods that are often labeled as “AI methods”, like automated
reasoning, semantic networks, graph search, expert systems, regression, etc.,
in my view, are algorithmic methods that are not specific to AI. They are, so
to say, usual algorithmic methods and were applied also to problems that, for
some reason, got the label “AI”, see the remarks about hard problems above.

In my view, machine learning methods cannot actually be specified by the way
how they work but, rather, by the way the problems these methods should solve
are specified. As we have seen in the previous section, the fundamental part
of algorithm and software development is the transition from a given problem
specification $P$ to an algorithm (program, system) $A$ that solves the
problem for any admissible input. As long as the steps for going from a
problem specification to a solution algorithm are done by a human this is just
the “usual” business of mathematics/informatics. If finding these steps is
(partially) supported by algorithms (invented by humans) this is what we can
call “symbolic computation in software science”. How and when does “machine
learning” come in and why, if at all, is this different from “usual”
mathematics and “usual” (maybe quite sophisticated) symbolic computation in
software science?

The point is that, in many situations, when we want to specify a problem, we
do not have a specification “in general terms” available. For example, let’s
consider the seemingly simple problem of deciding whether a given English
sentence contains information of the type “somebody cooperates with somebody
else”. An algorithm for this problem should produce the answer “no” in case no
such information is in the input sentence and should produce “yes” and the two
“somebodies” if such information is in the sentence. Now, of course, before
trying to invent such an algorithm, we will ask: What exactly do you mean by
“cooperate”? Among the English speaking community, under the natural
assumption of a long experience of using English in thousands of different
situations, it would be natural the start to explain “cooperate” in terms of a
couple of other notions like “working together”, “having a common goal”, …Oh,
“having a common goal” may not always be sufficient for speaking about
“cooperation”. One may have a common goal but fight against each other. Thus,
“supporting each other” etc. should be added. Some more subtle details should
be explained, some other things excluded etc. A long list of sentences
explaining the meaning of “cooperate” would be necessary. Then one could, in
the attempt of finding an algorithm for this little problem, try to put these
numerous explanations into algorithmic rules (assuming that we already have
access to a powerful grammar parsing algorithm for all of English). As a
result, we would hope that this rule system would be able to do the job. For
example, if we now would input “Peter and Ann found a way to help each other
for passing the exam”, the algorithm should answer “yes”, “Peter”, “Ann”. If
we would input “Peter and Ann passed the exam on the same day”, it should
answer “no”. Should it really answer “no”? Shouldn’t it rather answer “don’t
know” or “could be” or “could be but not explicitly mentioned”.

I now want to explain what, in my view, is the essence of the machine learning
approach. For this, we need not at all bother about what “learning” is. I just
consider those methods that, over the years, have been named “machine
learning” methods. The common feature of these methods is not how they proceed
but the type of specification of the problems to which they are applied:
Namely, they all are applied to problems of the kind above where a spelled-out
complete specification is not possible or, at least, not feasible. Now, the
fundamental idea of machine learning for solving such problems is:

  * •

Instead of spending time trying to specify the problem by a huge number of
general definitions, cases, rules, etc., one spends the time giving a huge
number of examples of input instances together with the answers. (In this
paper, we consider only “supervised learning”.) In this context, the answers
are called “labels”.

  * •

One sets up an algorithm from a certain class of relatively simply structured
algorithms (like the class of neural networks, the class of hyperplanes in a
high-dimensional space, the class of nested if-then-else expressions, etc.)
with some constants $c_{\\_}1,\ldots,c_{\\_}n$ (for example the weights at the
inputs of neurons in neural networks) in the algorithm left unspecified. For
each choice of numerical values for the $c_{\\_}1,\ldots,c_{\\_}n$, the
algorithm would produce an answer for each admissible input for the problem.

  * •

One uses techniques of mathematical optimization (or other, experimental
techniques, for example techniques that mimic biological evolution) to change
the initial values for $c_{\\_}1,\ldots,c_{\\_}n$ iteratively until the answer
of the algorithm to more and more inputs from the set of labeled data would
give the answer specified by the label. In the jargon of machine learning,
this iteration is called “training a model”.

  * •

One stops the iteration on the $c_{\\_}1,\ldots,c_{\\_}n$ when sufficiently
many answers are identical to the labels. Practically, at the beginning of the
whole operation, one partitions the set of labeled input into a “training set”
that is used for the iterations and a “test set” on which the algorithm with
the current values for the $c_{\\_}1,\ldots,c_{\\_}n$ \- which in the jargon
of machine learning is called the “trained model” - is tested.

The impressive success of this approach in the past two decades hinges on
three ingredients:

  * •

a huge amount of mathematical research on good and, partly provably
convergent, techniques for improving the algorithm parameters
$c_{\\_}1,\ldots,c_{\\_}n$; such research was partly already available in the
first phase of AI between 1960 and 1980, but it did not convince because of
the next two ingredients were not available,

  * •

huge corpora of labeled data; for example, in the spectacular application of
machine translation, a huge amount of “labeled data” is now available in the
form of files that contain an original book and its translation - by humans -
to some other language,

  * •

high-performance computing; the number of iterations of the machine learning
steps for determining suitable $c_{\\_}1,\ldots,c_{\\_}n$ and the
computational effort in each step is huge and is only manageable by computers
in recent years.

In principle, the approach is not radically new. Examples of historical
“learning from examples” problems are: Given points in the plane, find the
coefficients $c_{\\_}1,\ldots,c_{\\_}n$ of a polynomial that goes through the
given points (the interpolation problem). Given a function with some
properties on differentiability, an interval, and a distance, find the
coefficients $c_{\\_}1,\ldots,c_{\\_}n$ of a polynomial that is closer to the
function than the given distance everywhere on the interval (approximation
problem). Given points in the plane, find the coefficients of a straight line
such that the distance to all points is minimal (regression problem). Given a
function with certain differentiability properties, find the coefficients
$c_{\\_}1,\ldots,c_{\\_}n$ of a finite Fourier approximates of the function.
Etc.

Artificial Intelligence in the form of machine learning falls neatly into the
“automatic programming” view: It is the method of choice in cases where the
problem is not specified by general (formal or natural language) statements
but, rather, is specified only by a (huge) number of examples of admissible
input and desired output. In the case of general specifications of problems,
the transition from the problem to a solving algorithm, in principle, is a
reasoning process that is executed by humans or, in the symbolic computation
approach advocated in this paper, is a reasoning process (partly) executed by
symbolic computation methods. In the case of problems that are specified only
by examples, this process can still be automated by the machine learning
approach.

From the simple summary of the machine learning approach I gave above, one
important deficiency of the machine learning approach should be clear: The
algorithm which we get for a given problem just does the job of delivering (in
sufficiently many cases) desired answers. However, in general, no reason can
be given why, for example, the particular neural network that translates one
natural language to the other mimics certain fundamental insights about the
environment both languages share as their semantics. This is, in fact, similar
to the situation in the historical predecessors of “learning from examples”:
The Fourier analysis just does the job of finding an optimal Fourier sum. In
the example, where the function to be represented is the frequency spectrum of
a musical tone, the representation by a finite Fourier sum has a reasonable
“explanatory” power: The tone is composed of tones and overtones that occur in
the physical “music” world (for example, when picking the strings of a
guitar). However, if a Fourier representation of some arbitrary other function
is executed, there will be some outcome but there may not be any reasonable
interpretation of what this representation means in the reality from which the
function is taken.

The problem of weak explanatory power in the models (algorithms) created in
machine learning is well known. Lots of research was recently started to
extract “meaning” from such models. This research area is called “explainable
AI”.

In the frame of the analysis of this paper, I summarize: The machine learning
approach can be well subsumed under the general target of (semi-)automating
the process of software development (“automatic programming”). It can be
viewed as a numerical, rather than a symbolic, approach to automatic
programming. Thus, it is probably a very good idea to integrate machine
learning into the scope of the SCSS series because, of course, the interaction
of symbolic and numerical computation as the two possible approaches to
compute on finitary representations of abstract mathematical domains is of
utmost importance. The integration of machine learning into the scope of SCSS
can generate a stream of new ideas in both directions: Applying symbolic
methods to mathematical sub-problems of machine learning (e.g. the
determination of weights in neural networks) and applying machine learning to
symbolic algorithms (e.g. “learning” a priori complexity estimates for
computation-intensive methods like Gröbner bases etc.).

However, there is no reason to establish a flavor of “intelligence beyond
mathematics” when speaking about machine learning: I hope I have been able to
show the machine learning is just another mathematical method. As in the past,
of course, we can hope and expect also for the future that more and more
powerful algorithmic problem-solving methods will be invented.

Personally, when speaking to people who do not (want to) understand the
timeless, universal, always new, creative power of mathematics, I like to use
the term algorithmic intelligence for what we are doing: Algorithmic
intelligence is the human intelligence that produces algorithms for more and
more challenging problems in all areas of human activity. By an algorithm, an
infinite class of individual problem instances can then be treated by a
completely unintelligent machine. People who do not really understand what is
going on may believe that these machines display “intelligence”. The
algorithmic intelligence - by reflection, i.e. jumps to higher and higher
meta-levels - also provides more and more sophisticated algorithms for
producing algorithms. The incompleteness theorem of Kurt Gödel (1931), in a
somewhat liberal interpretation, shows that this tour through higher and
higher levels of algorithmization has no upper bound. In comparison to
“artificial intelligence”, the term “algorithmic intelligence” is used quite
rarely, which can be verified by Googling. However, my impression is that
“algorithmic intelligence” appears in more serious discussions about the
essence of AI. Therefore, I like to expand the abbreviation “AI” as
“algorithmic intelligence”.

Implicitly, I expressed this view already in the early days of AI, see [2]. At
the “Spring School of AI” in Teisendorf, 1982, I contributed a long article
summarizing the most important “symbolic” methods for automating the
algorithm/software development process that were known at that time. And we
had long, intensive, and quite controversial discussions at this conference on
the question of whether AI is something that goes beyond mathematics. As you
may guess, my answer then was “no” with essentially the arguments which I
expanded above. In my hectic years of research on methods for “algorithmic
intelligence” and research management, I never found the time and occasion to
spell out these arguments in a paper. Thus, I am grateful that I am given the
opportunity here.

## References

  * [1]
  * [2] Bruno Buchberger (1982): _Computer-unterstützter Algorithmenentwurf (Computer-Aided Algorithm Design)_.  In Wolfgang Bibel & Jörg H. Siekmann, editors: Proceedings of the Frühjahrsschule Künstliche Intelligenz (Spring School in Artificial Intelligence), Teisendorf, Germany, 15.-24. März 1982, Informatik-Fachberichte 59, Springer, pp. 141–201, 10.1007/978-3-642-68828-7_4.
  * [3] Bruno Buchberger (1985): _Symbolic Computation (An Editorial)_.  Journal of Symbolic Computation 1(1), pp. 1–6, 10.1016/S0747-7171(85)80025-0.
  * [4] Bruno Buchberger (2013): _Mathematics of the 21st Century: A Personal View_.  In Laura Kovács & Temur Kutsia, editors: Proceedings of the Fifth International Symposium on Symbolic Computation in Software Science (SCSS 2013), RISC Report Series 13-06, Johannes Kepler University, Linz/Hagenberg, Austria, p. 1.  Available at https://www.risc.jku.at/publications/download/risc_4737/TR_13_06_SCSS2013.pdf.  (See also the link to the slides of this talk on the website of SCSS 2013 at https://www.risc.jku.at/conferences/scss2013/program.html.).
  * [5] Bruno Buchberger & Olga Caprotti, editors (2001): _Electronic Proceedings of the First International Workshop on Mathematical Knowledge Management (MKM 2001)_. RISC, Johannes Kepler University, Linz/Hagenberg, Austria.  Available at https://www.risc.jku.at/conferences/MKM2001/Proceedings/.
  * [6] Bruno Buchberger, Gaston H. Gonnet & Michiel Hazewinkel (2003): _Mathematical Knowledge Management._ Special issue of the Annals of Mathematics and Artificial Intelligence 38(1-3), pp. 1–2, 10.1023/A:1022900528196.


# Deep Active Learning for Multi-Label Classification of Remote Sensing Images

Lars Möllenbrok , Gencer Sumbul, , Begüm Demir L. Möllenbrok, G. Sumbul and B.
Demir are with the Faculty of Electrical Engineering and Computer Science,
Technische Universität Berlin, 10623 Berlin, Germany, also with the BIFOLD -
Berlin Institute for the Foundations of Learning and Data, 10623 Berlin,
Germany. Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>This work is supported by the European Research Council
(ERC) through the ERC-2017-STG BigEarth Project under Grant 759764 and by the
German Ministry for Education and Research as BIFOLD - Berlin Institute for
the Foundations of Learning and Data (01IS18025A).

###### Abstract

In this letter, we introduce deep active learning (AL) for multi-label image
classification (MLC) problems in remote sensing (RS). In particular, we
investigate the effectiveness of several AL query functions for MLC of RS
images. Unlike the existing AL query functions (which are defined for single-
label classification or semantic segmentation problems), each query function
in this paper is based on the evaluation of two criteria: i) multi-label
uncertainty; and ii) multi-label diversity. The multi-label uncertainty
criterion is associated to the confidence of the deep neural networks (DNNs)
in correctly assigning multi-labels to each image. To assess this criterion,
we investigate three strategies: i) learning multi-label loss ordering; ii)
measuring temporal discrepancy of multi-label predictions; and iii) measuring
magnitude of approximated gradient embeddings. The multi-label diversity
criterion is associated to the selection of a set of images that are as
diverse as possible to each other that prevents redundancy among them. To
assess this criterion, we exploit a clustering based strategy. We combine each
of the above-mentioned uncertainty strategies with the clustering based
diversity strategy, resulting in three different query functions. All the
considered query functions are introduced for the first time in the framework
of MLC problems in RS. Experimental results obtained on two benchmark archives
show that these query functions result in the selection of a highly
informative set of samples at each iteration of the AL process.

###### Index Terms:

Multi-label classification, active learning, deep learning, remote sensing.

##  I Introduction

The development of multi-label image classification (MLC) methods (which aim
to automatically assign multiple land-use land-cover class labels [i.e.,
multi-labels] to each image scene in a remote sensing (RS) image archive) is a
growing research interest in RS [1]. In recent years, deep neural networks
(DNNs) have attracted great attention for MLC of RS images due to their high
capability to describe the complex spatial and spectral content of RS images.
For effectively learning the model parameters of DNNs, a sufficient number of
high-quality (i.e., reliable) training images annotated with multiple class
labels is required. However, the collection of multi-labels is highly costly
in terms of human time and effort [2]. To reduce annotation efforts, active
learning (AL), which aims at iteratively expanding an initial labeled training
set based on interaction between the user and the classification system, can
be used. At each AL iteration, for a given classifier the most informative
unlabeled images (i.e., samples) are selected based on a function (i.e., query
function). Then, these samples are labeled by a supervisor and added to the
current training set. The supervisor is usually a human expert, who annotates
the selected samples with the true class labels. The iterative process is
terminated once performance converges or a predefined budget limit is reached.

Most of the existing AL methods for DNNs are developed for pixel-based
classification (i.e., semantic segmentation) problems for land-cover maps
generation or change detection [3, 4, 5] in RS. For MLC problems, AL is seldom
considered in RS [2, 6]. An AL technique is introduced in [2] for multi-label
support vector machines. It exploits a query function based on the evaluation
of two criteria: i) multi-label uncertainty; and ii) multi-label diversity.
The multi-label uncertainty criterion is associated to the confidence of the
MLC algorithm in correctly assigning multi-labels to the considered sample,
while the multi-label diversity criterion aims at selecting a set of uncertain
samples that are as diverse as possible, and thus reducing the redundancy
among the selected uncertain samples. As that technique defines the
informativeness of samples based on traditional supervised classifiers with
hand-crafted features, its query function is not suitable to be directly used
with DNNs. For MLC of RS images through DNNs, an AL strategy is introduced in
[6] to reduce annotation errors by partially annotating images with salient
labels. Instead of selecting the most informative samples to be annotated, in
that strategy each sample is partially annotated with class labels, for which
the confidence of the considered DNN is high. This can lead to unnecessary and
redundant labeling of non-informative images, and thus an increase in labeling
cost and a limited DNN model capacity.

The development of DNN-based AL methods is much more extended in the computer
vision (CV) community with a main focus on single-label classification or
semantic segmentation problems. As an example, in [7] a core set approach
based on a greedy k-centre like algorithm is proposed to find a set of diverse
samples. It has been found to be an effective strategy for sample diversity if
the number of classes are not high. In [8], an AL framework is introduced as
an ensemble method to measure the prediction confidence of DNNs through
stochastic forward passes for assessing sample uncertainty. Although such
ensemble methods are found to be successful for AL, they suffer from slow
sample selection due to their requirement for multiple forward passes on DNNs.
In recent years, informative sample selection through the estimation of DNN
loss functions has attracted increasing attention for AL in CV [9, 10]. We
refer readers to [11] for a detailed review of AL methods in CV.

In this letter, we take the first step to introduce deep AL for selecting the
most informative unlabeled images to be annotated with multi-labels, and thus
minimizing annotation efforts of MLC problems in RS. In this context, we
investigate the effectiveness of three different AL query functions designed
to assess the multi-label uncertainty and multi-label diversity.

##  II Investigated Query Functions for AL in MLC

Let $\mathcal{X}=\\{\mathbf{X}_{1},\ldots,\mathbf{X}_{N}\\}$ be an archive of
$N$ RS images (i.e., samples), where $\mathbf{X}_{n}$ is the $n$th image in
the archive. We assume that an initial training set $\mathcal{T}^{1}$ with $M$
samples annotated with multi-labels
$\mathcal{Y}^{1}=\\{\mathbf{y}_{1},\ldots,\mathbf{y}_{M}\\}$ is available.
$\mathbf{y}_{j}=[y^{j}_{1},\ldots,y^{j}_{C}]\in\\{0,1\\}^{C}$ is the multi-
label vector of the image $\mathbf{X}_{j}\in\mathcal{T}^{1}$ that shows which
classes are present in the image, where $C$ is the number of classes. AL aims
to iteratively enrich the training set from a large set of unlabeled samples
by selecting the most informative samples. In the context of DNNs, at every
iteration $\tau$ (starting with $\tau=1$) a DNN $\mathcal{F}$ is trained using
the training set $\mathcal{T}^{\tau}$, and then $b$ samples are selected from
the set $\mathcal{U}^{\tau}=\mathcal{X}\setminus\mathcal{T}^{\tau}$ of
unlabeled samples based on a query function that finds the most informative
samples for $\mathcal{F}$. The value of $b$ is associated to labeling budget
per iteration. The samples selected through the query function are labeled by
a human expert and added to the training set to form the enriched training set
$\mathcal{T}^{\tau+1}$ with labels $\mathcal{Y}^{\tau+1}$. In this paper, we
investigate three AL query functions that are based on the evaluation of two
criteria: i) multi-label uncertainty; and ii) multi-label diversity. These
criteria are applied in two consecutive steps as follows. The most uncertain
$mb$ samples are selected in the first step, and then $b$ uncertain samples
(which are as diverse as possible to each other) are selected in the second
step, where $m$ is a hyperparameter. For training $\mathcal{F}$, we exploit
the binary cross entropy (BCE) loss function, which is defined as follows:

$\mathcal{L}_{BCE}(\mathcal{F}(\mathbf{X}_{j}),\mathbf{y}_{j})=-\\!\\!\sum^{C}_{i=1}y^{j}_{i}\log(p^{j}_{i})\\!+\\!(1\\!-\\!y^{j}_{i})\log(1\\!-\\!p^{j}_{i}),$
(1)

where $[p^{j}_{1},\ldots,p^{j}_{C}]$ is the class probability vector obtained
from $\mathcal{F}(\mathbf{X}_{j})$. In the subsections II-A and II-B, the
strategies for evaluating multi-label uncertainty and multi-label diversity
are presented.

###  II-A Evaluation of the Multi-Label Uncertainty

The multi-label uncertainty of an unlabeled sample is associated to the
confidence of the considered DNN in correctly assigning multi-labels to the
considered sample. To measure the multi-label uncertainty in the framework of
DNNs, we investigate three different strategies: 1) learning multi-label loss
ordering (denoted as LL); 2) measuring temporal discrepancy of multi-label
prediction (denoted as TPD); and 3) measuring the magnitude of approximated
gradient embeddings (denoted as MGE).

####  II-A1 The LL strategy

It aims to measure the multi-label uncertainty through the estimation of
potential losses. To this end, it exploits a subnetwork to predict the
ordering of unlabeled samples based on their potential losses inspired by [9].
Then, high-ranked samples in the ordering are assumed to produce a high loss.
Such samples are considered to be uncertain and selected for annotation. In
detail, in addition to $\mathcal{F}$ we employ an auxiliary subnetwork
$\mathcal{F}_{L}$ connected to $\mathcal{F}$. For the $j$th training sample
$\mathbf{X}_{j}$, the hidden features from $\mathcal{F}$ (which are denoted by
$\mathcal{F}_{hidden}(\mathbf{X}_{j})$) are fed to $\mathcal{F}_{L}$. In
$\mathcal{F}_{L}$, these features are transformed using global average pooling
followed by a fully connected layer with ReLU activation function that results
in the prediction of the multi-label loss ranking
$\hat{l}_{j}=\mathcal{F}_{L}(\mathcal{F}_{hidden}(\mathbf{X}_{j}))$.
$\mathcal{F}$ and $\mathcal{F}_{L}$ are trained jointly. Let $B^{p}$ be the
set of training sample pairs, which are randomly selected from a given mini-
batch $B$. For a pair ($\mathbf{X}_{j},\mathbf{X}_{k})\in B^{p}$, the loss
function for training $\mathcal{F}_{L}$ is defined as follows:

$\mathcal{L}_{\mathcal{F}_{L}}((l_{j},l_{k}),(\hat{l}_{j},\hat{l}_{k}))\\!=\\!\max(0,\\!-sign(l_{j}\\!-\\!l_{k})(\hat{l}_{j}\\!-\\!\hat{l}_{k})+\xi),$
(2)

where $l_{i}=\mathcal{L}_{BCE}(\mathcal{F}(\mathbf{X}_{i}),\mathbf{y}_{i})$
denotes the true loss of a sample $\mathbf{X}_{i}$ and $\xi>0$ is the margin
hyperparameter. The loss $\mathcal{L}_{\mathcal{F}_{L}}$ is high if the order
of the predicted values is not inline with the order of the true losses (e.g.,
$\hat{l}_{j}>\hat{l}_{k}$ while $l_{k}>l_{j}$). By this way, $\mathcal{F}_{L}$
learns the relative relations of the samples based on their multi-label loss
values that can be used to rank samples. For $B$, the overall loss function
for jointly training $\mathcal{F}$ and $\mathcal{F}_{L}$ is written as
follows:

$\mathcal{L}=\frac{1}{|B|}\sum_{\mathbf{X}_{i}\in
B}l_{i}+\lambda\frac{2}{|B|}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\sum_{\quad\quad(\mathbf{X}_{j},\mathbf{X}_{k})\in
B^{p}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathcal{L}_{\mathcal{F}_{L}}((l_{j},l_{k}),(\hat{l}_{j},\hat{l}_{k})),$
(3)

where $\lambda$ is a hyperparameter controlling the contribution of
$\mathcal{F}_{L}$ to the overall training. Once $\mathcal{F}$ and
$\mathcal{F}_{L}$ are jointly trained, the uncertainty of an unlabeled sample
$\mathbf{X}_{j}$ is evaluated as follows:

$Unc^{LL}(\mathbf{X}_{j})=\hat{l}_{j}.$ (4)

####  II-A2 The TPD strategy

It aims to measure the multi-label uncertainty of samples through temporal
discrepancies of samples. To this end, the temporal discrepancy of a sample is
measured based on the DNN outputs from two successive AL iterations inspired
by [10]. In this strategy, if the considered DNN is already confident in
predicting samples during previous AL iterations, the outputs of the DNN for
such samples are assumed to be more stable during successive AL iterations.
This condition is associated with small sample discrepancies and less
uncertain samples. In detail, let $\mathcal{F}^{\tau}$ be the DNN model
obtained after the $\tau$th iteration of the AL process and
$\mathbf{X}_{j}\in\mathcal{U}^{\tau}$ be an unlabeled sample. Then, the multi-
label uncertainty of $\mathbf{X}_{j}$ at the $\tau$th iteration is computed
based on the temporal prediction discrepancy as follows:

$Unc^{TPD}(\mathbf{X}_{j})=\|\mathcal{F}^{\tau}(\mathbf{X}_{j})-\mathcal{F}^{\tau-1}(\mathbf{X}_{j})\|_{2}.$
(5)

It is noted that in the first iteration ($\tau=1$), there is no reference DNN
$\mathcal{F}^{\tau-1}$ available. In this case, this strategy relies on random
sampling.

####  II-A3 The MGE strategy

It aims to estimate multi-label uncertainty by exploiting gradient
approximations. Since the gradient magnitude of a loss function determines the
extent of the model parameter change of a DNN, a high value of the gradient
magnitude for $\mathcal{L}_{BCE}$ is regarded as the indicator of uncertainty
in this strategy. To approximate the gradients with respect to the penultimate
layer of the considered DNN, we utilize the pseudo-labels inspired by [12].
Let
$\hat{\mathbf{y}}_{j}=[\hat{y}^{j}_{1},\ldots,\hat{y}^{j}_{C}]\in\\{0,1\\}^{C}$
be the pseudo-label for $\mathbf{X}_{j}$ obtained by thresholding the output
probabilities $\mathcal{F}(\mathbf{X}_{j})$ with a value of $0.5$. The
approximation of the gradients with respect to the penultimate layer of
$\mathcal{F}$ for the loss $\mathcal{L}_{BCE}$ is defined as follows:

$g_{\mathbf{X}_{j}}^{\hat{\mathbf{y}}_{j}}=\nabla_{W}\mathcal{L}_{BCE}(\mathcal{F}(\mathbf{X}_{j}),\hat{\mathbf{y}}_{j}),$
(6)

where $W$ is the set of the parameters of the last layer in $\mathcal{F}$. For
all the unlabeled samples, we compute the gradient approximations associated
with them and utilize the corresponding magnitude values to assess their
uncertainty. In detail, the multi-label uncertainty of an unlabeled sample
based on the magnitude of approximated gradient embeddings is defined as
follows:

$Unc^{MGE}(\mathbf{X}_{j})=\|g_{\mathbf{X}_{j}}^{\hat{\mathbf{y}}_{j}}\|_{2}.$
(7)

###  II-B Evaluation of Multi-Label Diversity

To assess the diversity of unlabeled samples, we exploit a clustering-based
strategy as it has been found an effective way in RS [13] due to the fact that
unlabeled uncertain images from different clusters are implicitly sparse in
the feature space. To this end, the most uncertain $mb$ samples (which are
selected using one of the above-mentioned strategies to measure the multi-
label uncertainty) are clustered into $b$ clusters by using the Kmeans++
algorithm. Then, from each cluster we select the sample associated to the
highest multi-label uncertainty that results in $b$ selected samples. Due to
selection of one sample from each cluster, the multi-label diversity of
samples at each AL iteration is achieved.

We combine each multi-label uncertainty strategy with the clustering based
multi-label diversity strategy. This results in three different query
functions investigated in this paper: 1) LL with Clustering (denoted by
LL+Clustering); 2) TPD with Clustering (denoted by TPD+Clustering); and 3) MGE
with Clustering (denoted by MGE+Clustering).

##  III Experimental Results

###  III-A Dataset Description and Design of Experiments

Experiments were conducted on the UCMerced [14] and TreeSatAI [15] datasets.
The UCMerced dataset consists of 2100 RGB images, each of which has the size
of 256 $\times$ 256 pixels with a spatial resolution of 30cm. Each image in
this dataset is annotated with multi-labels in [1], while the total number of
classes is 17. The images (i.e., samples) were randomly divided to derive a
validation set of 525 samples, a test set of 525 samples, and a pool of 1050
samples. From the pool, 40 images were randomly chosen to construct the
initial training set and the rest were considered as unlabeled samples. The
TreeSatAI dataset is made up of 50381 aerial images, each of which has the
size of 302 $\times$ 302 pixels and include RGB and near infrared bands. The
images in this dataset were resized to 288 $\times$ 288 pixels for the
experiments. Each image is annotated with multi-labels, while the total number
of classes is 15 and each class label is associated with an area coverage
ratio. We retained a class label if its coverage ratio is higher than 0.07.
This resulted in the derivation of a validation set of 6799 samples, a test
set of 5043 samples, and a pool of 38531 samples. From the pool, 1000 images
were randomly chosen to construct the initial training set and the rest are
considered as unlabeled samples.

We report our results in terms of $F_{1}$ scores. All experimental results are
referred to the average accuracies obtained in three trials, while an initial
training set was randomly reconstructed in each trial. We used Densenet121
architecture for $\mathcal{F}$. For training, we utilized the stochastic
gradient descent (SGD) optimizer with an initial learning rate of 0.025 and
0.01 on UCMerced and TreeSatAI, respectively. For UCMerced, training was
conducted for 100 epochs with the mini-batch size of 10. For TreeSatAI, we
increased the number of epochs to 200 and used a mini-batch size of 100. We
reduced the learning rate by a factor of $0.1$ after 80 and 160 epochs on
UCMerced and TreeSatAI, respectively. For the images of both datasets, we
applied horizontal flipping and random rotation of $r\in\\{0,90,180,270\\}$
degrees. The value of the clustering parameter $m$ is set to 3 and 4 for the
UCMerced and TreeSatAI datasets, respectively. For LL, $\xi$ was set to $1$ by
following the suggestion in [9]. For the auxiliary subnetwork of LL, we used
the Adam optimizer with the same initial learning rate with $\mathcal{F}$. The
gradient propagation of the subnetwork to $\mathcal{F}$ was stopped after 60
and 120 epochs for UCMerced and TreeSatAI, respectively, as suggested in [9].

Figure 1: Micro $F_{1}$ score versus number of training samples obtained by
LL+Clustering with different $b$ values (UCMerced).

###  III-B Sensitivity Analysis

In this subsection, we initially analyze the performances under different
values of the labeling budget $b$ by fixing the query function. Fig. 1 shows
the $F_{1}$ score versus number of training samples obtained by LL+Clustering
query function for the UCMerced dataset. From the figure, one can observe that
selecting small $b$ values results in higher $F_{1}$ scores under the same
number of labeled samples. Furthermore, in the case of using small $b$ values
higher $F_{1}$ scores are achieved with less samples compared to the cases of
larger $b$ values. However, since at each AL iteration the DNN has to be
trained on all the labeled samples, small $b$ values are associated to the
higher training complexity. It is noted that similar behaviors are observed
for the other query functions applied to both datasets (not provided due to
space limitations). We also analyze accuracies obtained by using only multi-
label uncertainty criterion and its combination with multi-label diversity
criterion. Fig. 2 shows the average $F_{1}$ score versus number of training
samples obtained by LL and LL+Clustering on the UCMerced dataset when $m$ and
$b$ are set to 1 and 20, respectively. By analyzing the figure, one can
observe that the classification performances are significantly improved by
using both uncertainty and diversity criteria under each number of labeled
samples. These results are also confirmed in the experiments with the other
query functions applied to both datasets (not reported for space constraints).

Figure 2: Micro $F_{1}$ score versus number of training samples obtained by LL
and LL+Clustering when $b$=20 (UCMerced).

The last analysis of this subsection is associated to the initialization of
the model parameters. There are two different strategies for initializing the
model parameters at each AL iteration: 1) random initialization that is
associated to cold-starting; and 2) using the parameters learned in the
previous AL iterations (except in the first iteration where the parameters are
randomly initialized) that is associated to warm-starting. Fig. 3 shows the
mean $F_{1}$ scores for LL+Clustering on UCMerced and TreeSatAI using warm-
starting and cold-starting. From the figure, one can see that using warm-
starting results in higher scores on the UCMerced dataset (Fig. 3 (a)). In the
first few iterations, the model achieves already a high performance, which
means that the learned weights already capture valuable knowledge about the
data. Therefore, the model can benefit from re-initialization with previously
learned weights. However, the figure shows that cold-starting leads to higher
$F_{1}$ scores compared to warm-starting for TreeSatAI (Fig. 3 (b)). In
addition, at the first iterations warm-starting shows no benefit, whereas
during subsequent iterations, when the model already achieves relatively good
results, there are minor benefits. However, at later iterations warm-starting
leads the model to overfit, and thus results in low accuracies. This is due to
the accumulation of network updates over the course of the AL iterations.

(a)

(b)

Figure 3: Micro $F_{1}$ scores obtained by LL+Clustering on (a) UCMerced and
(b) TreeSatAI when cold-starting and warm-starting are used. Figure 4: Micro
$F_{1}$ score versus number of labeled samples obtained by our query functions
and random sampling using warm-starting (UCMerced).

###  III-C Comparison Among the Investigated Query Functions

In this section, we compare our query functions (LL+Clustering,
TPD+Clustering, MGE+Clustering) among each other and with random sampling in
terms of classification accuracy and complexity (associated to the trainable
parameters and time needed for sampling). Fig. 4 shows the micro $F_{1}$ score
versus number of labeled samples for the UCMerced dataset using warm-starting.
From the figure, one can see that all our query functions provide similar
performances. However, MGE+Clustering generally results in slightly higher
micro $F_{1}$ scores. In addition, our query functions outperform random
sampling, particularly at the later AL iterations. As an example,
MGE+Clustering outperforms random sampling by more than 2% reaching a micro
$F_{1}$ score of 79.87% with 200 labeled samples, and more than 1% reaching a
micro $F_{1}$ score of 85.81% with 400 labeled samples. As another example,
LL+Clustering outperforms random sampling by more than 1% with a micro $F_{1}$
score of 86.29% at 400 labeled samples. We have found similar results in terms
of macro $F_{1}$ score, but could not report for space constraints. Fig. 5
shows the $F_{1}$ score versus number of training samples obtained for
TreeSatAI using cold-starting. From the figure, one can observe that the three
query functions show similar performances, while outperforming random sampling
in terms of micro $F_{1}$ score (Fig. 5 (a)). For example, LL+Clustering
outperforms random sampling by more than 2% reaching a micro $F_{1}$ score of
69.90% with 18000 labeled samples. From Fig. 5 (b), one can see that
LL+Clustering provides the highest macro $F_{1}$ scores. LL+Clustering
outperforms random sampling by 8% reaching a macro $F_{1}$ score of 59.05%
with 14000 labeled samples. MGE+Clustering outperforms random sampling by
about 5% with 14000 labeled samples reaching a macro $F_{1}$ scores of 55.49%,
while TPD+Clustering outperforms random sampling by more than 4% reaching a
macro $F_{1}$ score of 54.74%. Table I shows the sampling time and the number
of trainable parameters for each method. LL+Clustering has the highest number
of trainable parameters as well as hyperparameters, which may require some
additional effort for tuning. The time for selecting the most informative
samples at one AL iteration are similar for LL+Clustering and MGE+Clustering,
whereas TPD+Clustering is slightly slower due to the computation overhead of
the reference model.

(a)

(b)

Figure 5: (a) Micro $F_{1}$ and (b) macro $F_{1}$ scores versus number of
labeled samples obtained by our query functions and random sampling using
cold-starting (TreeSatAI).

##  IV Conclusion

In this letter, we have investigated three different AL query functions in the
framework of DNNs for the MLC of RS images. The presented query functions are
based on the evaluation of two criteria: i) multi-label uncertainty; and ii)
multi-label diversity. To evaluate multi-label uncertainty, we have
investigated the effectiveness of three different strategies: i) learning
multi-label loss ordering; ii) measuring temporal discrepancy of multi-label
predictions; and iii) measuring magnitude of approximated gradient embeddings.
To achieve multi-label diversity, we have exploited a clustering based
strategy. We have combined each multi-label uncertainty evaluation strategy
with the clustering based strategy, resulting in three different query
functions. It is worth emphasizing that our query functions are independent
from the considered DNN and can be used with any DNN architecture designed for
MLC problems. From the experimental results, we have observed that the
combination of learning multi-label loss ordering with clustering leads to the
best overall performance, whereas that of measuring magnitude of approximated
gradient embeddings is computationally more efficient with a slight decrease
in the accuracy. As a future work, we plan to adapt and test our query
functions in the framework of multi-label RS image retrieval problems.

TABLE I: Time Needed for Selecting $b$ Unlabeled Samples and the Number of Trainable Parameters for Each AL Query Function When $b$=20 for UCMerced and $b$=1000 for TreeSatAI Query Function | Time | Number of Parameters
---|---|---
UCMerced | TreeSatAI
LL + Clustering | 7.25s | 141.5s | 7.33M
TPD + Clustering | 10.84s | 188.1s | 6.97M
MGE + Clustering | 7.06s | 142.2s | 6.97M

## References

  * [1] B. Chaudhuri, B. Demir, S. Chaudhuri, and L. Bruzzone, “Multilabel remote sensing image retrieval using a semisupervised graph-theoretic method,” _IEEE Trans. Geosci. Remote Sens._ , vol. 56, no. 2, pp. 1144–1158, 2018.
  * [2] B. T. Zegeye and B. Demir, “A novel active learning technique for multi-label remote sensing image scene classification,” in _Image Signal Process. Remote Sens._ , vol. 10789, 2018, pp. 100–107.
  * [3] R. Thoreau, V. Achard, L. Risser, B. Berthelot, and X. Briottet, “Active learning for hyperspectral image classification: A comparative review,” _IEEE Geosci. Remote Sens. Magazine_ , vol. 10, no. 3, pp. 256–278, 2022.
  * [4] G. Lenczner, A. Chan-Hon-Tong, B. Le Saux, N. Luminari, and G. Le Besnerais, “Dial: Deep interactive and active learning for semantic segmentation in remote sensing,” _IEEE J. Sel. Topics Appl. Earth Observ. Remote Sens._ , vol. 15, pp. 3376–3389, 2022.
  * [5] L. Khelifi and M. Mignotte, “Deep learning for change detection in remote sensing images: Comprehensive review and meta-analysis,” _IEEE Access_ , vol. 8, pp. 126 385–126 400, 2020.
  * [6] J. Lin, T. Yu, and Z. J. Wang, “Rethinking crowdsourcing annotation: Partial annotation with salient labels for multilabel aerial image classification,” _IEEE Trans. Geosci. Remote Sens._ , vol. 60, pp. 1–12, 2022.
  * [7] O. Sener and S. Savarese, “Active learning for convolutional neural networks: A core-set approach,” in _Intl. Conf. Learn. Represent._ , 2018.
  * [8] Y. Gal, R. Islam, and Z. Ghahramani, “Deep bayesian active learning with image data,” in _Intl. Conf. Mach. Learn._ PMLR, 2017, pp. 1183–1192.
  * [9] D. Yoo and I. S. Kweon, “Learning loss for active learning,” in _IEEE Conf. Comput. Vis. Pattern Recog._ , June 2019.
  * [10] S. Huang, T. Wang, H. Xiong, J. Huan, and D. Dou, “Semi-supervised active learning with temporal output discrepancy,” in _IEEE/CVF International Conference on Computer Vision_ , October 2021, pp. 3447–3456.
  * [11] P. Ren, Y. Xiao, X. Chang, P.-Y. Huang, Z. Li, B. B. Gupta, X. Chen, and X. Wang, “A survey of deep active learning,” _ACM computing surveys_ , vol. 54, no. 9, pp. 1–40, 2021.
  * [12] J. T. Ash, C. Zhang, A. Krishnamurthy, J. Langford, and A. Agarwal, “Deep batch active learning by diverse, uncertain gradient lower bounds,” in _Intl. Conf. Learn. Represent._ , 2020.
  * [13] B. Demir, C. Persello, and L. Bruzzone, “Batch-mode active-learning methods for the interactive classification of remote sensing images,” _IEEE Trans. Geosci. Remote Sens._ , vol. 49, no. 3, pp. 1014–1031, 2011.
  * [14] Y. Yang and S. Newsam, “Geographic image retrieval using local invariant features,” _IEEE Trans. Geosci. Remote Sens._ , vol. 51, no. 2, pp. 818–832, 2013.
  * [15] S. Ahlswede, C. Schulz, C. Gava, P. Helber, B. Bischke, M. Förster, F. Arias, J. Hees, B. Demir, and B. Kleinschmit, “TreeSatAI benchmark archive: A multi-sensor, multi-label dataset for tree species classification in remote sensing,” _Earth Syst. Sci. Data_ , 2022.