# Knowledge acquisition for dialogue agents using reinforcement learning on
graph representations

Selene Baez Santamaria1, Shihan Wang2, Piek Vossen1,

1Vrije Universiteit Amsterdam, 2Utrecht University

###### Abstract

We develop an artificial agent motivated to augment its knowledge base beyond
its initial training. The agent actively participates in dialogues with other
agents, strategically acquiring new information. The agent models its
knowledge as an RDF knowledge graph, integrating new beliefs acquired through
conversation. Responses in dialogue are generated by identifying graph
patterns around these new integrated beliefs. We show that policies can be
learned using reinforcement learning to select effective graph patterns during
an interaction, without relying on explicit user feedback. Within this
context, our study is a proof of concept for leveraging users as effective
sources of information.

Knowledge acquisition for dialogue agents using reinforcement learning on
graph representations

Selene Baez Santamaria1, Shihan Wang2, Piek Vossen1, 1Vrije Universiteit
Amsterdam, 2Utrecht University

##  1 Introduction

Artificial interactive agents are designed to assist people. Usually,
interaction modelling starts from the user’s information need and not the
system’s information need. Such uni-directional modelling misses out to
leverage the user as a knowledge source for the agent and not only as a
knowledge seeker. To this end, we argue for knowledge-centered agents that can
(i) evaluate their knowledge state,  (ii) evaluate their knowledge needs,
(iii) acknowledge their lack of knowledge, and  (iv) actively try to obtain
the missing knowledge through interaction with users.

Figure 1: Dialogue management modelled as knowledge graphs. Information
conveyed by the interlocutor at every turn is represented as triples in an
interaction graph (in pink). This graph is integrated into the existing
episodic knowledge graph of the artificial agent (in blue). We focus on
specific graph patterns arising in the integrated neighbourhoods of the
resulting graph (in purple). These might represent, for example, knowledge
gaps (in green, bottom left) or conflicts (in green, bottom right). One
pattern gets selected to respond to the interlocutor and continue the
dialogue.

The knowledge targeted by such knowledge-centered agents might vary according
to the application and shift during interactions. For some scenarios, an
agent’s goal may be to acquire in-depth knowledge on a given topic. For
example, a customer service should know all factual information about the
company’s products, while a personal companion needs a complete overview of
any relevant personal information to support a user. In contrast, for other
scenarios, an agent should aim to gather diverse perspectives to break or
expand self-imposed filter bubbles Aicher et al. (2022). For example, an
online moderator should detect a wide range of opinions around the same topic
van der Meer et al. (2022), while news recommenders should provide
complementary perspectives reporting events Reuver et al. (2021). Lastly, we
argue that in any application, regardless of its training and performance,
knowledge gaps may arise that need to be resolved and thus require active
intervention of the agent. We therefore propose a solution to enhance agents
with such generic capability.

In this paper, we present a knowledge-centered conversational agent that

  1. 1.

Evaluates the status of its own knowledge.

  2. 2.

Can generate a wide range of responses in line with specific dialogue
strategies to prompt the user to communicate further knowledge.

  3. 3.

Learns a dialogue policy to choose from these options in specific
circumstances to improve its knowledge state.

We provide evidence that artificial agents can drive conversation to pursue
their own knowledge-centered goals by leveraging the user’s knowledge, and
without requiring explicit human feedback for learning. We formulate these
goals at an abstract level that generalizes over specific application contexts
and can therefore be used to adapt the agent’s knowledge in many applications.
Hence, we step in the direction of developing conversational agents that
become highly adaptable and responsive to a wide range of tasks and domains as
they expand their knowledge.

##  2 Related work

Knowledge-based conversational agents are an active area of research Ni et al.
(2023). Some approaches consider dialogue as a series of short Q&A tasks,
where the usage of structured knowledge sources for retrieval of factual
information particularly strengthens this type of dialogue Kim et al. (2023).
Another line of research adds a conversational layer to factual knowledge
bases to facilitate querying them over natural language Ait-Mlouk and Jiang
(2020). These techniques, however, fall short when a dialogue involves
personal or opinion-based knowledge.

Dialogue policy learning, particularly through reinforcement learning (RL),
also shows substantial attention. Many studies address on Task-oriented
Dialogue Rohmatillah et al. (2023) or Open-domain Dialogue Xu et al. (2020).
Few focus on the acquisition of knowledge, and these typically involve
inquiring the user about their satisfaction with the interaction. However, in
this work is concerned with filling domain or task-related knowledge gaps. For
a similar approach, Mazumder et al. propose a method for continuous open-world
knowledge base completion within a conversational setting.

##  3 Framework description

We propose a framework, formulated as a Belief-Desire-Intention (BDI) model
Bratman (1987), where artificial agents have informational intents. In our
approach, we model these intentions using symbolic knowledge bases.
Specifically, we choose graph and RDF111Resource Description Framework:
https://www.w3.org/RDF/ technologies to model the knowledge that agents either
have or aim to have.

To explain our approach, we use the running example of an agent that has the
goal to "know more" (as further defined in Section 3.1). However, the proposed
framework works for any informational intent, as long as this intention is
measurable in the proposed symbolic representation.

###  3.1 Defining a BDI model with KGs

#### Beliefs

We begin by modelling the informational state of the agent as a belief
network, specifically as a knowledge graph where entity nodes are connected
via semantically meaningful edges Since the beliefs originate from the user
input, we represent these as CLAIMS made by the user. These CLAIMS are the
basic knowledge units, represented as RDF statements with subject-predicate-
object triples. Each of these statements is embedded in its own RDF named
graph Carroll et al. (2005), thus allowing a triple to serve as a node in
other RDF statements. This simple, yet powerful knowledge representation
technique allows to express complex and nested meanings (see Table 1), where
"there is knowledge about things", and "there is further knowledge about the
known things". Furthermore, to recognize that the knowledge an agent has is
not necessarily absolute, but rather a perspective on the real world, each
CLAIM is associated to a PERSPECTIVE, hosting the particular source’s
certainty, polarity, and sentiment values of that belief. Through this
modelling, an agent to hold contradictory, uncertain or ambivalent beliefs
from multiple sources.

Table 1:  Example of an agent’s belief network. Top part showcases how knowledge units can be combined to express more complex knowledge. Bottom part showcases the quality of each knowledge unit, with specific polarity and certainty values.  Subject | Predicate | Object | Named Graph
---|---|---|---
lWorld:diana | n2mu:live | lWorld:paris | lWorld:diana_live_paris
lWorld:diana_live_paris | n2mu:duration | lWorld:fiveYears | lTalk:diana_live_paris_duration_fiveYears
lWorld:diana_live_paris | grasp:hasAttribution | lTalk:diana_live_paris_01 | lTalk:Perspectives
lTalk:diana_live_paris_01 | rdf:value | certainty:uncertain | lTalk:Perspectives
lTalk:diana_live_paris_01 | rdf:value | polarity:positive | lTalk:Perspectives

#### Intentions

This tractable definition of beliefs allows an agent to evaluate the quality
of its own knowledge by measuring specific aspects of its belief network. As a
consequence, the agent is also equipped with the ability to set a target for
any of these aspects. We regard these targets as the agent’s informational
intention, that is, the intended informational state of the agent. As a
concrete example, an agent with the intention of having more complete
knowledge (as introduced in Section 1) can be operationalized as an increasing
volume of CLAIMS; while an agent with the intention of having more diverse
knowledge can be operationalized as a growing volume of PERSPECTIVES. As such,
any informational intention can be addressed under this framework, provided
that the associated knowledge aspect can be measured on its belief network.

#### Desires

As the informational state of an agent changes, different graph patterns arise
on its belief network. Specific graph patterns are semantically meaningful and
are connected to different knowledge quality aspects, for example conflicting
knowledge or novel knowledge. An agent can select any of these patterns to
transform its current informational state into an intended one. Thus, we
regard these semantic patterns as the desires of the agent that represent
specific knowledge objectives relevant to its current informational state. In
this paper we define eight abstract desires, as show in Figure 9, each related
to a specific knowledge aspect: correctness, completeness, redundancy, and
interconnectedness Stvilia et al. (2007).222This is not a comprehensive
specification of patterns. Others could focus on complexity, consistency, or
temporality of knowledge.

###  3.2 Knowledge acquisition modelled as KGs

So far we have focused on modelling an agent that can keep track of its
current and intended informational state. Yet, we have not explained the
mechanisms by which the agent acquires knowledge to transform that
informational state. For this, an agent must engage in information-seeking
behaviours Belkin et al.  and actively interact with sources in order to find
the target knowledge. Similar to an information retrieval setting, two major
features in the search of information are a) the modes of interaction, and b)
the types of sources available. These two are typically intertwined, for
instance, an interaction mode like "sensory experience" implies visual and
auditory sources while a web search interaction mode implies sources like
online textual news or Semantic Web databases like Wikidata. In this paper we
experiment primarily with dialogue as an interaction mode, and human
interlocutors as knowledge sources.

To be able to perform a dialogue with human interlocutors, our BDI network
architecture needs to be integrated in a conversational agent. Throughout a
conversation between an artificial agent and a knowledge source, we model the
flow of information during their communication as episodic Knowledge Graphs
($eKG$), where each incoming utterance is transformed into RDF triples, and
the accumulation of conversations is stored in a triple store Baez Santamaria
et al. (2021). For this purpose, an $eKG$ is conformed of five sub-graphs:
(i) Ontology: containing the world model,  (ii) Instances: containing the
individual entities in claims and their inter-claim connections,  (iii)
Claims: containing the set of atomic pieces of knowledge collected thus far,
(iv) Perspectives: containing the specific viewpoint of the source regarding a
claim,  (v) Interactions: containing the conversational provenance of each
claim (e.g. source, place, and time of a chat).

In addition to the above knowledge structure, the agent needs to be equipped
with:

  1. 1.

language understanding to interpret the interlocutor’s input signal (e.g.
audio, text, gestures) as providing an interaction knowledge graph ($iKG$,
pink in Figure 1),

  2. 2.

belief integration to merge the incoming beliefs ($iKG$) with the existing
ones accumulated in the episodic knowledge graph ($eKG$, blue in Figure 1),

  3. 3.

desire generation to evaluate the merged beliefs and produce a set of focused
areas in the belief network to potentially improve upon on (green in Figure
1),

  4. 4.

desire selection to pick a specific belief that is to be changed by evoking
the next interlocutor’s input signal,

  5. 5.

language generation to formulate a response of the appropriate signal type
(e.g. audio, text, gestures) to evoke the interlocutor response

Through these five pipeline processes, the agent can create (pro-active)
responses during conversation, where the BDI framework replaces a classical
dialogue management module. The language understanding and language generation
modules correspond to well-established NLU and NLG tasks. In this paper, we
take the NLU and NLG components for granted and leave these for future work,
as we are focusing here on the BDI graph framework.

###  3.3 Measuring intent satisfaction by comparing KGs

As mentioned in Section 3.1, intents are associated with the comparison of a
current knowledge state and an intended knowledge state. To change its current
knowledge state, an agent makes use of desires, one per time step, to
gradually change its current knowledge state. As intents are associated to
specific aspects that can be measured on an agent’s belief network, it then
follows that every desire can be evaluated in the following manner:

  1. 1.

Apply the intent-related metric $m$ on the agent’s belief network $eKG$ at
time $\tau$

  2. 2.

Select desire $d$ and use it in a information-seeking interaction (in this
case, dialogue)

  3. 3.

Apply the intent-related metric $m$ on the agent’s belief network $eKG$ at
time $\tau+1$

  4. 4.

Calculate the difference $\Delta m$ between the values of the intent-related
metric before and after the desire $d$ was applied

  5. 5.

Determine whether the measured difference $\Delta m$ in the belief network
contributes, hinders, or has no effect towards the intent

Figure 2: Time-wise comparison of a belief network. At each time-step $\tau$,
the knowledge state is assessed by applying metric $m$ on the $eKG$. In order
to quantitatively evaluate the effect that a desire selected at time $\tau$
has on the belief network, the difference $\Delta m$ is calculated between the
states $\tau-1$ and $\tau$.

Depending on the specific metric in question, the measured difference can vary
in magnitude and direction. For the intention of having complete knowledge,
operationalized as the metric of volume of CLAIMS, a positive difference
contributes to the intention as it signals that more CLAIMS have been added to
the belief network, while a difference of $0$ has no effect signals that, even
if there had been changes to the belief network, these are not reflecting
progress towards the intention.

This framework thus allows an agent, not only to have intentions and produce
desires that pave a path towards satisfying this intention, but also provides
a way to evaluate each desire’s specific value, in the context of a given
intention.

##  4 Methodology

The selection of desires is a crucial step in knowledge acquisition through
dialogue. Thus, testing the utility of the proposed framework requires a
method that learns which graph pattern (desire) will lead to the most valuable
information (intent) in a specific but non-restrictive context.

For this, we use reinforcement learning (RL) to learn a policy that improves
the relevance of the system’s responses and augments the agent’s learning
abilities. We consider a fully observable environment where the state is the
agent’s accumulated $eKG$. The reward $r$ is calculated based on the
comparison of consecutive states, as measured by a specific intent-related
metric $m$. The problem presents a discrete action space, where the actions
refer to the instantiated graph patterns $d$ and change with every interaction
due to the specific entity and predicate types involved in the conversations.
We aim to learn an optimal policy to determine which graph pattern to select.

Figure 3: Computational pipeline to calculate Q-values for different knowledge
desires.

###  4.1 Problem formalization

We formalize our RL problem as a discrete finite Markov decision process (MDP)
and introduce the key components in the MDP as follows.

#### State

The state is represented as Directed Acyclic Graph (DAG), specifically using
the semantics of an $eKG$. This is formally defined as a tuple
$eKG=(\mathcal{V}_{e},\mathcal{E}_{e},\mathcal{\varsigma}_{e})$, where
$\mathcal{V}$ is a set of nodes, $\mathcal{E}$ is a set of directed edges
connecting pairs of nodes, and $\mathcal{\varsigma}$ is a set of statements. A
statement is comprised of $\sigma=(s,p,o,c)$, where $s$ and $o\in\mathcal{V}$
are the subject and object entities, $p\in\mathcal{E}$ is the connecting
relation and $c\in\mathcal{V}$ is the host named graph333Note that named
graphs serve the function of encapsulating a single SPO triple that can later
on be referred to in other statements, thus forming nested statements. As
such, named graphs are both graphs $c\in\mathcal{C}$, and nodes themselves
that can be head/tail entities in statements, resulting in $c\in\mathcal{V}$..
Furthermore, $\mathcal{T}$ is a set of entity types and $\mathcal{P}$ is a set
of predicate types. Every node has at least one entity type $t\in\mathcal{T}$
while every edge has exactly one predicate type $\rho\in\mathcal{R}$.

#### Action

Actions are generated by performing queries against the $eKG$, using
information from the last $iKG$. As queries can also be represented as DAGs,
each action type is also defined by a tuple of the form
$d=(\mathcal{V}_{a},\mathcal{E}_{a},\mathcal{\varsigma}_{a})$. The action
space is defined by eight abstract graph query patterns, where each query
pattern is characterized by a specific set of statements
$\mathcal{\varsigma}_{a}$ containing either constant, instantiated or variable
statement elements (full patterns are available on the Appendix, Table 5). As
with any graph query, constant elements provide the semantics behind each
action, while variable elements allow to search for a pattern in a given
$eKG$. In contrast, instantiated elements are specific to the $iKG$ and modify
an abstract query $d^{abs}$ on every dialogue turn thus making the actions
$d^{spe}$ applicable to the current state transition.

A selected action is sent in dialogue to the user, whose response generates an
$iKG$ to be integrated to the agent’s belief network.

#### Transition

Given an $eKG$ at time $\tau$, it transitions to a new state at time $\tau+1$
by incorporating an $iKG$ defined by a tuple
$iKG=(\mathcal{V}_{i},\mathcal{E}_{i},\mathcal{\varsigma}_{i})$. As mentioned
before, an $iKG$ represents the content of an utterance by the user in
dialogue, as shown in Table 6. Therefore, the structure of the $iKG$ is fixed
by this specific set of statements $\mathcal{\varsigma}_{i}$, while the
semantics are determined by the user and are reflected by instantiating
$\mathcal{V}_{i}$, $\mathcal{E}_{i}$.

At time $\tau$, there is no pre-established relation between the $eKG$ and its
$iKG$. However, as the $iKG$ gets incorporated into the $eKG$ at time
$\tau+1$, then we can say that
$\mathcal{V}_{i_{\tau}}\in\mathcal{V}_{e_{\tau+1}}$ and
$\mathcal{E}_{i_{\tau}}\in\mathcal{E}_{e_{\tau+1}}$.

#### Reward function

As stated in Section 3.3, comparing two consecutive states allows to quantify
the relative change in the belief network caused by selecting and employing
the latest knowledge desire. We thus define reward $r$ as:

$\mathbf{r}_{\tau}=\frac{f(\mathcal{V}_{e},\mathcal{E}_{e},\mathcal{\varsigma}_{e})_{\tau}}{f(\mathcal{V}_{e},\mathcal{E}_{e},\mathcal{\varsigma}_{e})_{\tau+1}}-1$
(1)

For this, we require a metric $m$ to be applied to the belief network at each
time step $\tau$. As mentioned in Section 3.1, these metrics $m$ play the role
of operationalizing a knowledge intent.

###  4.2 Policy optimization

We optimize the policy $\pi$ to maps a state $eKG$ to an action $d$ (i.e.
selecting the best graph pattern for a current $eKG$). Figure 3 illustrates
the architecture of this learning procedure.

#### Representing the state

Given the complexity of the $eKG$, we create a simplified graph where the
claims are the main nodes, connected to their respective perspective values.
For this we extract the Instances, Claims and Perspectives subgraphs
(described in Section 3.2). This new simplified graph is centered around the
perspective nodes, and their connection to claims thus represents the quality
of what is known.

As node features we use the instances that are involved in the claims, using a
one-hot-encoding representation. For the state encoder, we use an architecture
with two RGAT layers Busbridge et al. (2019) followed by a fully connected
layer, which results in node embeddings. To obtain a graph embedding we
aggregate these via a mean operator.

#### RL algorithm

We employ the D2Q algorithm Zhao et al. (2024) which provides a structure to
separate abstract actions from specific actions thus mapping to our set of
abstract and specific graph patterns. We consider abstract actions as the type
of graph pattern to select (e.g. negation conflict) while the specific actions
relate to the predicates and entities involved (e.g. conflict about diana live
paris). Learning can be efficient by using the entity types (e.g. person,
city) instead of the specific instances, allowing the agent to learn an
approximation of a pattern’s utility from fewer interactions.

The state vector is fed into a two-layers DQN architecture Mnih et al. (2013)
to estimate the Q-values per action (hidden layer size = 64, replay memory
size = 500). The output of this is fed into two parallel flows, each
consisting of a fully connected layer and a final softmax layer. On the one
hand, abstract actions are represented as the 8 possible graph patterns to
choose from. On the other hand, specific actions are represented as all entity
types available in a given ontology.

Selecting an action consists of two steps: selecting an abstract action, and
scoring the specific subactions. The abstract action is selected by taking the
item with the highest value from its softmax head. For specific actions, a
score is constructed as the weighted average of its entities types $e$, using
the values returned by the corresponding softmax head. This constructive
scoring method allows to score actions with novel combinations of entities.

Figure 4: Q-value distribution per abstract and specific action types (thought
types and entity types respectively). Seed state is an empty graph,
representing an agent with no knowledge on the topic yet. For visualization,
the probabilities are normalized by subtracting the average probability.
Shorter bars signal more equally distributed action values.

##  5 Experimental design

We investigate the following research questions:

  1. RQ1:

Characterizing agent behaviour Do different agent intentions produce different
dialogue strategies?

  2. RQ2:

Characterizing agent’s knowledge Do different agent intentions acquire
different knowledge?

  3. RQ3:

Impact of the source How do different knowledge sources impact the learning
process of agents with different intentions?

###  5.1 Experimental conditions

We investigate 8 knowledge intents, operationalized with the graph metrics
described in Table 2. As different metrics measure distinctive aspects of
knowledge, we hypothesize that each metric will produce distinct agent
behaviours.

Table 2:  Graph metrics and their knowledge-centered intention. Knowledge dimensions are inspired from Nurse et al. (2011) Metric |  Dimension | Formula
---|---|---
Sparseness |  Cohesion | $\frac{\mathcal{E}}{\mathcal{V}^{2}}$
Average degree |  Interconnectedness | $\frac{2|\mathcal{E}|}{\mathcal{V}}$
Shortest path |  Specificity | $\frac{1}{\mathcal{V}}\sum_{i\neq j}min(dist(v_{i},v_{j}))$
Total triples |  Volume | $\mathcal{\varsigma}$
Average population |  Spread | $\frac{1}{\mathcal{T}}\sum_{t\in\mathcal{T}}|e_{t}|$
Ratio claims to triples |  Completeness | $\frac{|{claims}|}{|\mathcal{\varsigma}|}$
Ratio perspectives to claims |  Diversity | $\frac{|{perspectives}|}{|{claims}|}$
Ratio conflicts to claims |  Correctness | $\frac{|{conflicts}|}{|{claims}|}$

We setup two experiments. In the first, the knowledge-centered agents converse
with a single user with perfect knowledge. In the second experiment, the
agents are exposed to users with varying knowledge quality to simulate the
diversity of knowledge sources available in the wild.

###  5.2 Evaluation

To answer RQ 1, we compare the dialogue policies learned by agents with
different intentions/rewards. This is estimated by the Q-values produced by
the D2Q network, as these indicate the expected return (associated with the
reward) by taking different actions given a certain state. Since the Q-values
are state dependent, we take as use case an empty $eKG$, representing the
beginning of a conversation and when the tone and topic are established.

To answer RQ 2, we compare the belief networks of agents with different
intentions/rewards. This is performed by measuring its knowledge
interconnectedness, specificity, volume, spread, completeness, diversity and
correctness as operationalized by the 8 metrics previously selected as
rewards.

To answer RQ 3, we analyze the changes in the rewards obtained by agents
conversing with users with perfect knowledge vs the ones exposed to users with
imperfect knowledge.

###  5.3 Data

We utilize the Harry Potter Dialogue (HPD) dataset Chen et al. (2023) which
also contains structured information about characters in the novel.
Furthermore, the data is temporally divided according to seven books, thus
allowing to simulate conversations over time where some attributes change,
while others remain stable. We transform the data into RDF triples, removing
invalid punctuation and splitting lists into individual values. The dataset
characteristics are shown in Table 3.

###  5.4 User model

Five user model types are created as knowledge bases of varied quality (Table
7). To simulate a conversation, the selected graph pattern $d$ is transformed
into a SPARQL query that can be run against the user model’s triple store. The
response triples are formatted as an $iKG$, representing the acquired
knowledge from the user. Please note that not all possible graph patterns $d$
will result in a successful query to the user model in which case, the user
model will randomly select a piece of knowledge, as a way to continue the
dialogue.

###  5.5 Training setup

Dialogue is carried out in RDF form directly to isolate the dialogue policy
optimization. As such, we do not include speech detection or generation.
Similarly, information extraction to transform natural language intro RDF
triples, and Natural Language Generation fall out of scope. Therefore, the
optimization focuses on learning policies for choosing adequate graph patterns
and is not influenced by errors from other pipeline systems. The agents are
trained for 8 conversations of 20 turns each (10 for the human and 10 for the
agent). We perform an update on the policy on every agent turn, resulting in
80 (10x8) policy updates. As the graphs get reset every second conversation,
the maximum number of state transitions is 20 (10x2). The network is saved at
the end of every conversation, resulting in 8 checkpoints. We run each setting
3 times and present the average results. More details about training
mechanisms and parameter settings in the RL algorithm are presented in
Appendix A.5.

##  6 Results and discussion

We first evaluate the training process per intention, by calculating the
average rewards during training under the corresponding reward function. In
Figure 5, we observe that 5 metrics stabilize in their learning, while 3 of
them do not. Taking the learning curve of Average-population (in orange) as an
example, the average reward increases during the early timesteps and converges
towards a stable level. This phenomenon shows the early learning process of
the RL algorithm and indicates its capability of finding a stable policy that
can select the best graph pattern for an $eKG$ under this intention. Looking
back at Table 2, those metrics that learn well are defined based on structural
aspects of the graph, while those defined as semantic ratios have difficulty
guiding the RL algorithm. This might signal that semantic rations have more
complex correlations (or maybe causal relations) between the number of claims
and the number of turns or consecutive conversations.

Figure 5: Average rewards obtained by the policy at every training step.

From this point forward we focus our analysis on the 5 intentions that proved
fast learning convergence into stable learned policies.

#### Learned dialogue policies (RQ1)

Figure 4 shows the distribution of action values per intention of the learned
policies where some intentions are more equally distributed, like Sparseness,
while others have a wider probability range like Shortest-path. We note that
some abstract actions are consistently preferred, like Overlaps, while other
abstract actions are mostly excluded, like Trust. Regardless of the overall
trends, we can confirm that different intentions produce distinct dialogue
strategies.

For example, Average degree can be characterized by dialogues where known
information is mentioned in order to get the user’s perspective (Agent: "Did
you know that Ginny has red hair, just like Ron?", User: "No, I am sure that
she does not have red hair") combined with trust judgments towards the user,
based these perspectives (Agent: "I do not trust you"). This type of policy
implicitly improves the interconnectedness between what is known and the user
perspectives on this knowledge, thus profiling the knowledge source.

While Average population and Total triples also prompt the user for their
perspective on what is known, in contrast these combine it with further
questions regarding subjects (Agent: "What color is Ginny’s hair") or objects
(Agent: "Who has red hair then?") respectively. Interestingly enough, these
two policies actively avoid making trust judgments on the user, and instead
focus on expanding their knowledge base further.

Figure 6: Profiles of the knowledge acquired by different intentions.
Knowledge dimensions are operationalized according to the graph metrics in
Table 2.

#### Acquired knowledge (RQ 2)

We analyze the final $eKG$ according to the 5 aforementioned metrics (Figure
6, further details on Table 4). Overall, we see evidence that three specific
knowledge profiles arise, distinguished by different intentions. The
intentions Sparseness, Average degree and Average population generate similar
knowledge profiles more centered around knowledge cohesion and
interconnectedness. Shortest path as an intention focuses more on the volume,
spread and specificity of knowledge. Total triples instead keep a balanced
profile, keeping most of the knowledge aspects at an equal level.

#### Policy updates (RQ 3)

We investigate the effects of imperfect knowledge sources by comparing the
cumulative reward for each intention across experiments 1 (user model with
perfect knowledge) and experiment 2 (user models with imperfect knowledge).
Figure 7 shows rewards are consistently lower when the agents are exposed to
imperfect knowledge sources, however, some rewards (e.g. Average population)
are more sensitive than others (e.g. Average degree). This can be explained by
looking back at the learned dialogue policies analyzed in RQ1. While trying to
expand its knowledge, Average population poses more questions to the user,
which can lead to unanswered questions given an imperfect knowledge source. In
contrast, Average degree focuses on profiling the knowledge source itself,
which can be done regardless of the quality of the knowledge source.

Figure 7: Cumulative rewards per intention using the trained network.
Comparison between experiment 1 (perfect knowledge user) and experiment 2
(imperfect knowledge user).

##  7 Conclusion

In this work we propose a theoretical and mathematical framework for
conversational agents to pursue their own knowledge goals in open-domain
settings. In this framework, specific knowledge goals (or intentions) can be
operationalized as domain independent graph metrics. We provide evidence that
some graph metrics can quickly learn stable and optimal dialogue policies via
reinforcement learning, and analyze such resulting dialogue policies. We test
these dialogue policies and compare the knowledge gathered by each of them.
Finally, we demonstrate that this framework is robust to knowledge sources of
different quality.

## Limitations

In this work we use operationalize knowledge quality aspects as measurable
graph properties. Though this has been proposed carefully, the terminology
might be too coarse for other specialized disciplines like epistemology.

On a different aspect, the scalability of the proposed methods are to be
further examined. As there are no restrictions on the size or structure of the
$eKG$, the state space is infinite and the learning procedure can be
challenging when the state space gets too big.

## Ethics statement

The framework proposed in this study aims to enable artificial agents to
pursue knowledge driven goals, utilizing people as knowledge sources.
Depending on the application and the users available, the misuse of these
technologies might result in concerns about privacy and monitoring,
particularly with vulnerable groups.

## References

  * Aicher et al. (2022) Annalena Aicher, Wolfgang Minker, and Stefan Ultes. 2022.  Towards modelling self-imposed filter bubbles in argumentative dialogue systems.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 4126–4134, Marseille, France. European Language Resources Association.
  * Ait-Mlouk and Jiang (2020) Addi Ait-Mlouk and Lili Jiang. 2020.  Kbot: a knowledge graph based chatbot for natural language understanding over linked data.  _IEEE Access_ , 8:149220–149230.
  * Baez Santamaria et al. (2021) Selene Baez Santamaria, Thomas Baier, Taewoon Kim, Lea Krause, Jaap Kruijt, and Piek Vossen. 2021.  EMISSOR: A platform for capturing multimodal interactions as episodic memories and interpretations with situated scenario-based ontological references.  In _Proceedings of the 1st Workshop on Multimodal Semantic Representations (MMSR)_ , pages 56–77, Groningen, Netherlands (Online). Association for Computational Linguistics.
  * (4) Nicholas J Belkin et al.  Interaction with texts: Information retrieval as information seeking behavior.
  * Bratman (1987) Michael Bratman. 1987.  Intention, plans, and practical reason.
  * Busbridge et al. (2019) Dan Busbridge, Dane Sherburn, Pietro Cavallo, and Nils Y Hammerla. 2019.  Relational graph attention networks.  _arXiv preprint arXiv:1904.05811_.
  * Carroll et al. (2005) Jeremy J Carroll, Christian Bizer, Pat Hayes, and Patrick Stickler. 2005.  Named graphs.  _Journal of Web Semantics_ , 3(4):247–267.
  * Chen et al. (2023) Nuo Chen, Yan Wang, Haiyun Jiang, Deng Cai, Yuhan Li, Ziyang Chen, Longyue Wang, and Jia Li. 2023.  Large language models meet harry potter: A dataset for aligning dialogue agents with characters.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 8506–8520, Singapore. Association for Computational Linguistics.
  * Kim et al. (2023) Seokhwan Kim, Spandana Gella, Chao Zhao, Di Jin, Alexandros Papangelis, Behnam Hedayatnia, Yang Liu, and Dilek Z Hakkani-Tur. 2023.  Task-oriented conversational modeling with subjective knowledge track in DSTC11.  In _Proceedings of The Eleventh Dialog System Technology Challenge_ , pages 274–281, Prague, Czech Republic. Association for Computational Linguistics.
  * Mazumder et al. (2020) Sahisnu Mazumder, Bing Liu, Nianzu Ma, Shuai Wang, and AI Amazon. 2020.  Continuous and interactive factual knowledge learning in verification dialogues.  In _NeurIPS-2020 Workshop on Human And Machine in-the-Loop Evaluation and Learning Strategies_.
  * Mnih et al. (2013) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. 2013.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_.
  * Ni et al. (2023) Jinjie Ni, Tom Young, Vlad Pandelea, Fuzhao Xue, and Erik Cambria. 2023.  Recent advances in deep learning based dialogue systems: A systematic survey.  _Artificial intelligence review_ , 56(4):3055–3155.
  * Nurse et al. (2011) Jason RC Nurse, Syed Sadiqur Rahman, Sadie Creese, Michael Goldsmith, and Koen Lamberts. 2011.  Information quality and trustworthiness: A topical state-of-the-art review.
  * Reuver et al. (2021) Myrthe Reuver, Nicolas Mattis, Marijn Sax, Suzan Verberne, Nava Tintarev, Natali Helberger, Judith Moeller, Sanne Vrijenhoek, Antske Fokkens, and Wouter van Atteveldt. 2021.  Are we human, or are we users? the role of natural language processing in human-centric news recommenders that nudge users to diverse content.  In _Proceedings of the 1st Workshop on NLP for Positive Impact_ , pages 47–59.
  * Rohmatillah et al. (2023) Mahdin Rohmatillah, Jen-Tzung Chien, et al. 2023.  Advances and challenges in multi-domain task-oriented dialogue policy optimization.  _APSIPA Transactions on Signal and Information Processing_ , 12(1).
  * Stvilia et al. (2007) Besiki Stvilia, Les Gasser, Michael B Twidale, and Linda C Smith. 2007.  A framework for information quality assessment.  _Journal of the American society for information science and technology_ , 58(12):1720–1733.
  * van der Meer et al. (2022) Michiel van der Meer, Enrico Liscio, Catholijn M Jonker, Aske Plaat, Piek Vossen, and Pradeep K Murukannaiah. 2022.  Hyena: A hybrid method for extracting arguments from opinions.
  * Xu et al. (2020) Jun Xu, Haifeng Wang, Zheng-Yu Niu, Hua Wu, Wanxiang Che, and Ting Liu. 2020.  Conversational graph grounded policy learning for open-domain conversation generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1835–1845, Online. Association for Computational Linguistics.
  * Zhao et al. (2024) Yangyang Zhao, Kai Yin, Zhenyu Wang, Mehdi Dastani, and Shihan Wang. 2024.  Decomposed deep q-network for coherent task-oriented dialogue policy learning.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_.

##  Appendix A Appendix

###  A.1 Desires as abstract graph patterns

We operationalize conversational desires (under the proposed BDI model) as
abstract RDF graph patterns. There are specified as triple patterns in Table 5
and visualized in Figure 9.

###  A.2 Dialogue management for knowledge acquisition

The details of the dialogue management process as a BDI model are explained
below:

#### Belief integration:

As input, the knowledge integration step takes a) an interaction knowledge
graph ($iKG$) with factoids acquired in the last conversational turn and b) an
episodic knowledge graph ($eKG$) containing the accumulated information
acquired by the artificial agent thus far. Table 6 illustrates how an $iKG$
represents the incoming beliefs and their provenance. An $eKG$ is a collection
of $iKG$, thus following a similar but larger structure.

#### Desire generation:

As explained in Section 3.1, the current framework proposes eight tailored
graph patterns that evaluate four different knowledge aspects: correctness,
completeness, redundancy, and interconnectedness. Each of these abstract
patterns can be instantiated with the specific Subject, Predicate and Object
present in the $iKG$, which typically produces a wide range of specific
desires. Thus, each of these desires targets a concrete belief that the agent
intends to change in a particular knowledge quality direction.

#### Desire selection:

A single desire is selected to form a response and continue the dialogue.
Different system responses vary significantly in relevance and semantic
plausibility, so they elicit distinct counter-responses from the human
interlocutor. Therefore, the agent’s chances of acquiring knowledge of
sufficient quality highly depend on the selected desire.

###  A.3 Dataset

Here we show some statistics on the range and domain of the different
predicates in the Harry Potter Dialogue Chen et al. (2023) dataset. This
information might bring insight into which abstract thought patterns are
better suited per predicate type. Predicates with a large domain scope (e.g
Gender) are better paired with object gaps and object overlaps, while
predicates with large range scope benefit from subject gaps and subject
overlaps.

Table 3:  Dataset statistics, after converted to RDF. For each role (Object or Subject) the number of distinct entities present in that role is reported.  Predicate | Range (Object) | Domain (Subject)
---|---|---
Looks | 428 | 107
Spells | 200 | 47
Belongings | 189 | 49
Title | 101 | 86
Personality | 39 | 46
Affiliation | 27 | 94
Hobbies | 23 | 22
Export | 16 | 24
Talents | 15 | 13
Lineage | 11 | 83
Age | 11 | 106
Gender | 2 | 124

###  A.4 User models

Five types of user models are used in this work, as described in Table 7. The
first one is modelled with perfect knowledge while the other four types have
imperfect knowledge. When creating each type, the base vanilla user is
corrupted in a specific way, as described on the last column of the table. For
each of the imperfect user types, 100 instances were generated.

###  A.5 Training and parameters

In order to facilitate learning we introduce two training mechanisms: reset
and shuffle. Reset, on the one hand, clears out the $eKG$ and restarts it to
an empty condition. This mechanism counters the fact that since we measure the
changes on the $eKG$ and the $eKG$ keeps growing, it may have a chance that
the same action leads to different rewards when the $eKG$ is getting bigger.
Shuffle, on the other hand, swaps the $eKG$ with another random one of similar
size. This mechanism exposes the networks to more varied states thus prevents
the networks from learning simply the specific state transitions. In the
experiments, we reset the $eKG$ every 2 conversations and shuffle every 2
conversations in an alternating manner. The D2Q network is optimized with a
learning rate of $1e-4$, a batch size of $4$, a $\gamma$ factor of $0.99$ and
a $\tau$ value of $0.005$. The experiments were run on an NVIDIA A10 GPU for
$~{}5$ hours.

###  A.6 Extra results

Figure 8 shows the selection counts per action per intention. This is further
evidence for RQ 1 that distinct dialogue strategies arise.

Figure 8: Abstract action counts selected during testing chat by the optimized
trained network, averaged over runs.

As further evidence for RQ 2, Table 4 reports the values for the 5 metrics on
the final eKGs for different intentions.

Table 4:  Description of the knowledge acquired under different intentions, as measured by different graph metrics. Test run for one conversation of 10 turns, using the frozen optimized policy network. Reward |  Average degree |  Sparseness |  Shortest path |  Total triples |  Average population
---|---|---|---|---|---
Average-degree |  12.377 |  0.745 |  2.555∗ |  4222∗ |  21.000∗
Average-population |  12.406 |  0.756 |  2.548 |  4170 |  20.320
Shortest-path |  12.492∗ |  0.780∗ |  2.530 |  4076 |  19.033
Sparseness |  12.452 |  0.765 |  2.541 |  4146 |  19.974
Total-triples |  12.398 |  0.751 |  2.551 |  4197 |  20.680
Table 5:  Semantic graph patterns. Items between <> represent variable nodes. <UNDERLINED> items represent nodes that need to be instantiated. Pattern type | Graph pattern |  Example response
---|---|---
Subject |  Predicate |  Object |  Named Graph
Knowledge aspect: Correctness
Negation Conflict |  lWorld:<SUBJECT> |  n2mu:<PREDICATE> |  lWorld:<OBJECT> |  lTalk:<CLAIM> |  "You say that Karla lives in Paris, but I have heard she does not"
lTalk:<MENTION1> |  gaf:denotes |  lTalk:<CLAIM> |  lTalk:Perspectives
lTalk:<MENTION1> |  grasp:hasAttribution |  lTalk:<ATTRIBUTION1> |  lTalk:Perspectives
lTalk:<ATTRIBUTION1> |  rdf:value |  graspf:Positive |  lTalk:Perspectives
lTalk:<MENTION2> |  gaf:denotes |  lTalk:<CLAIM> |  lTalk:Perspectives
lTalk:<ATTRIBUTION2> |  rdf:value |  graspf:Negative |  lTalk:Perspectives
Cardinality Conflict |  n2mu:<PREDICATE> |  owl:cardinality |  "1"xsd:int |  lWorld:Ontology |  "I heard Karla lives in Amsterdam, not in Paris"
lWorld:<SUBJECT> |  n2mu:<PREDICATE> |  lWorld:<OBJECT1> |  lWorld:<CLAIM1>
lWorld:<SUBJECT> |  n2mu:<PREDICATE> |  lWorld:<OBJECT2> |  lWorld:<CLAIM2>
Knowledge aspect: Completeness
Subject Gap |  lWorld:<SUBJECT> |  n2mu:<PREDICATE> |  lWorld:<OBJECT> |  lTalk:<CLAIM> |  "Karla is a person, and people are born in countries. Which country was Karla born in?"
lWorld:<SUBJECT> |  rdf:type |  n2mu:<TYPE1> |  lWorld:Instances
n2mu:<PREDICATE> |  rdfs:domain |  n2mu:<TYPE1> |  lWorld:Ontology
n2mu:<PREDICATE> |  rdfs:range |  n2mu:<TYPE2> |  lWorld:Ontology
Object Gap |  lWorld:<SUBJECT> |  n2mu:<PREDICATE> |  lWorld:<OBJECT> |  lTalk:<CLAIM> |  "Paris is a city, and cities are located in countries. Which country is Paris located in?"
lWorld:<OBJECT> |  rdf:type |  n2mu:<TYPE1> |  lWorld:Instances
n2mu:<PREDICATE> |  rdfs:domain |  n2mu:<TYPE1> |  lWorld:Instances
n2mu:<PREDICATE> |  rdfs:range |  n2mu:<TYPE2> |  lWorld:Instances
Knowledge aspect: Redundancy
Statement Novelty |  lWorld:<SUBJECT> |  n2mu:<PREDICATE> |  lWorld:<OBJECT> |  lTalk:<CLAIM> |  "Gabriela also mentioned that Karla lives in Paris"
lTalk:<MENTION1> |  gaf:denotes |  lTalk:<CLAIM> |  lTalk:Perspectives
lTalk:<MENTION2> |  gaf:denotes |  lTalk:<CLAIM> |  lTalk:Perspectives
Entity Novelty |  lWorld:<SUBJECT> |  n2mu:<PREDICATE> |  lWorld:<OBJECT> |  lTalk:<CLAIM> |  "I have heard many things about Paris"
lWorld:<SUBJECT> |  grasp:denotedIn |  lWorld:<MENTION1> |  lTalk:Perspectives
lWorld:<SUBJECT> |  grasp:denotedIn |  lWorld:<MENTION2> |  lTalk:Perspectives
Knowledge aspect: Interconnectedness
Subject Overlap |  lWorld:<SUBJECT> |  n2mu:<PREDICATE> |  lWorld:<OBJECT1> |  lTalk:<CLAIM1> |  "You ate french food and now moroccan food."
lWorld:<SUBJECT> |  n2mu:<PREDICATE> |  lWorld:<OBJECT2> |  lTalk:<CLAIM2>
Object Overlap |  lWorld:<SUBJECT1> |  n2mu:<PREDICATE> |  lWorld:<OBJECT> |  lTalk:<CLAIM1> |  "My friend Armando also lives in Paris"
lWorld:<SUBJECT2> |  n2mu:<PREDICATE> |  lWorld:<OBJECT> |  lTalk:<CLAIM2>
Figure 9: Simplified graphic visualization of semantic graph patterns that represent informational desires. Green boxes encapsulate specific graph structures, while blue boxes group graph structures associated to similar knowledge aspects. Nodes are represented as circles. Edges are represented as continuous lines between them. Named graphs are represented as dashed circles around a single triple. Elements in purple represent CLAIMS, elements in pink represent PERSPECTIVES, and elements in orange represent the ONTOLOGY. Items between <> represent elements to be instantiated in a specific belief network. Table 6:  Example of an interaction knowledge graph (iKG). The graph represents the interlocutor Marco, expressing the belief that "Diana lives in Paris", on January 14th, 2022.  Subject |  Predicate |  Object |  Named Graph
---|---|---|---
lTalk:chat1_turn1 |  rdf:type |  grasp:Turn |  lTalk:Perspectives
|  sem:hasActor |  lFriends:marco |  lTalk:Perspectives
|  sem:hasTime |  lTime:14012022 |  lTalk:Perspectives
lTalk:chat1_turn1_MEN1 |  rdf:type |  grasp:Mention |  lTalk:Perspectives
|  grasp:denotes |  lWorld:diana_live_paris |  lTalk:Perspectives
|  prov:wasDerivedFrom |  lTalk:chat1_turn1 |  lTalk:Perspectives
|  grasp:hasAttribution |  lTalk:chat1_turn1_MEN1_ATTR1 |  lTalk:Perspectives
lTalk:chat1_turn1_MEN1_ATTR1 |  rdf:type |  grasp:Attribution |  lTalk:Perspectives
|  rdf:value |  graspPolarity:positive |  lTalk:Perspectives
|  rdf:value |  graspCertainty:uncertain |  lTalk:Perspectives
Table 7:  User models and their knowledge communication qualities. User models
with imperfect knowledge have their eKG corrupted, as these represent their
belief networks. Perfect knowledge
---
vanilla |  Oracle with perfect communication |  NA |  NA
Imperfect knowledge
amateur |  incomplete knowledge |  coverage |  50% claims removed
doubtful |  low confidence knowledge |  certainty |  50% claims with low certainty
incoherent |  conflicting knowledge |  consistency |  50% claims are negated
confused |  incorrect knowledge |  correctness |  50% claims with a random object


# Deep-BIAS: Detecting Structural Bias using Explainable AI

Bas van Stein
LIACS, Leiden University
Leiden, The Netherlands
<EMAIL_ADDRESS>
&Diederick Vermetten
LIACS, Leiden University
Leiden, The Netherlands
<EMAIL_ADDRESS>
&Fabio Caraffini
Department of Computer Science
Swansea University
Swansea, UK
<EMAIL_ADDRESS>
&Anna V. Kononova
LIACS, Leiden University
Leiden, The Netherlands
<EMAIL_ADDRESS>0000-0002-0013-7969 0000-0003-3040-7162
0000-0001-9199-7368 0000-0002-4138-7024

###### Abstract

Evaluating the performance of heuristic optimisation algorithms is essential
to determine how well they perform under various conditions. Recently, the
BIAS toolbox was introduced as a behaviour benchmark to detect structural bias
(SB) in search algorithms. The toolbox can be used to identify biases in
existing algorithms, as well as to test for bias in newly developed
algorithms. In this article, we introduce a novel and explainable deep-
learning expansion of the BIAS toolbox, called Deep-BIAS. Where the original
toolbox uses 39 statistical tests and a Random Forest model to predict the
existence and type of SB, the Deep-BIAS method uses a trained deep-learning
model to immediately detect the strength and type of SB based on the raw
performance distributions. Through a series of experiments with a variety of
structurally biased scenarios, we demonstrate the effectiveness of Deep-BIAS.
We also present the results of using the toolbox on 336 state-of-the-art
optimisation algorithms, which showed the presence of various types of
structural bias, particularly towards the centre of the objective space or
exhibiting discretisation behaviour. The Deep-BIAS method outperforms the BIAS
toolbox both in detecting bias and for classifying the type of SB.
Furthermore, explanations can be derived using XAI techniques.

_K_ eywords Structural Bias, Algorithm Behaviour, Explainable AI, Optimisation

##  1 Introduction

As the amount of data and complexity of the optimisation problems continue to
increase, the demand for effective heuristic optimisation algorithms also
increases. Since no single heuristic algorithm is universally best [1], it is
necessary to benchmark these algorithms to understand which performs best
under specific conditions. Most continuous optimisation benchmarks are
performance-based, such as the Black-Box Optimisation Benchmark (BBOB) [2]
test suite. These benchmarks provide information on the performance of an
algorithm and how it compares with others in various situations. For example,
one algorithm may excel at optimising separable functions while another
performs well on uni-modal, highly conditioned functions. Resource-based
benchmarks measure the number of resources (computation power, memory, and
energy) required under certain conditions, but do not offer much insight into
the behaviour of the algorithms under different circumstances. Behaviour-based
benchmarks, on the other hand, provide additional information about how an
algorithm behaves under different conditions, such as the movement of a
population of candidate solutions in a swarm-based optimisation algorithm.

The previously proposed BIAS toolbox [3] is such a behaviour-based
benchmarking tool. It can be used to analyse whether algorithms or components
of an algorithm induce structural bias (SB). SB is a type of bias inherent in
iterative heuristic optimisation algorithms that affects their performance in
the objective space. By detecting the presence, strength, and type of SB in a
heuristic optimisation algorithm, it is possible to identify areas for
improvement and understand under which conditions SB is less likely to occur.
This information can be used to optimise the performance of these algorithms.

In this work, we propose an improved methodology for the BIAS toolbox for both
the detection of structural bias and the classification of the type of SB.
Instead of using $39$ statistical tests and their p-values, we propose using a
single convolutional deep learning model to predict the presence and type of
SB in the raw final-point distributions of various optimisation runs on a
special test function $f_{0}$. In this work, our aim is to answer the
following research questions:

  * RQ1

How to determine, using machine learning, whether a heuristic continuous
optimisation algorithm suffers from SB?

  * RQ2

How to predict the type of SB suffered by a continuous heuristic optimisation
algorithm?

  * RQ3

Can we generate visual explanations of the predicted SB type?

  * RQ4

Is the proposed deep learning-based approach better than using statistical
tests and under which conditions?

To answer RQ1 and RQ2, we propose a deep learning approach on raw algorithm
performance data (on a special test function) to identify which SB type (if
any) is most likely to occur in a given optimiser. The complete SB benchmark
deep learning test suite (Deep-BIAS) and data generators for different SB
scenarios, are made open-source [4]. To answer RQ3, we propose to use
explainable artificial intelligence techniques adapted for the proposed deep
learning approach to visualise the SB results. To answer RQ4, we evaluate both
the proposed deep learning approach and the previous statistical test approach
using a large set of 189 different artificially generated parameterised
distributions containing 11 different scenarios of structural bias. In
addition, we compare the results of both methods on a wide set of state-of-
the-art optimisers.

##  2 Structural bias

In many complex optimization problems we have to deal with a complete black-
box setting. This means we have no a priori information about which regions of
the space contain good solution. In such a setting, the search has to start
"from scratch", within the defined domain boundaries. The search should then
be able to identify and progress towards promising regions with good values of
objective function. Only points sampled thus far should steer algorithm’s
logic and operators in the subsequent steps of the search. This means that the
algorithm doesn’t inherently favour one region of the space over any other. In
other words, in case the algorithm is to be deployed in a general situation,
it should be able to find high-quality solutions regardless of where they are
located inside the feasible domain of the problem. The degree to which an
algorithm exhibits such flexibility in locating optima is clearly among
contributors to it success.

Unfortunately, detecting propensity of an iterative algorithm towards some
parts of the domain is difficult due to interplay between the sampled
landscape of the function and internal workings of the algorithm [5]. In order
to disentangle these two components, the test function $f_{0}$ has been
defined as follows:

$f_{0}:[0,1]^{n}\to[0,1],\text{ where }\forall
x,f_{0}(x)\sim\mathcal{U}(0,1).$ (1)

For this function, the optimum is located uniformly at random throughout the
domain, and there can exist no region which is inherently better than another.
As such, an unbiased search is expected to return a uniform distribution of
final best solutions. If the distribution of these points is non-uniform, this
indicates a structural bias of the algorithm, as is not able to give equal
importance to every region of the domain. Structural bias thus represents an
algorithm’s inflexibility. Because of this, we consider structural bias to be
an undesired behaviour which potentially limits the algorithm’s performance in
a generic setting. The exact relation between the operators of an algorithm
and its structural bias, and the way in which it might influence performance
on different function landscapes, is poorly understood. However, through
testing on $f_{0}$, SB can be identified, and thus potentially removed via a
prudent choice of operators.

###  2.1 Existing methodology for measuring SB

Visual inspection of the distributions of the final solutions found on
$f_{0}$, collected in multiple independent runs of the method under
investigation and displayed component-wise [6], is the most intuitive approach
to detecting SB. Although it provides a good understanding of how SB manifests
itself in clearly biased and unbiased cases, such a procedure can be subject
to personal interpretations and is time-consuming when a large number of
images need to be generated and inspected (see [5, 7, 8] and repositories [9,
10]). Moreover, it is unable to provide reliable results in the presence of a
mild SB or figure rendering artefacts, making it difficult to come to the
right conclusion.

The use of statistical testing methods removes the subjective component of SB
inspection and leads to an automated decision-making process over a large data
set of results, where the uniformity distributions of the final solutions
obtained with multiple runs in $f_{0}$ are tested for uniformity. However,
testing for uniformity is challenging, in particular when looking at a
‘practical’ sample size $N$, which is the number of full runs to be performed
in this case. Experiments carried out with $N$ up to $100$ and $\alpha=0.01$
using the Kolmogorov-Smirnov test [11], the Cramer-Von Mises test [12] and
Anderson-Darling [13] test in combination with the Benjamini-Hochberg
correction method [14], returned good results in some classes of algorithms,
but, taken separately, these tests perform poorly when a wide variety of
algorithms are investigated [5, 15]. The best results are obtained with
$N=600$, which helps to detect SB more often but does not guarantee the
detection of all different types of SB at any significance level [8] \- even
higher values of $N$ are needed for smaller levels of significance and higher
statistical power [16]. Using multiple statistical tests to detect SB and its
type reliably can be complex and laborious. From the point of view of a
practitioner or an algorithm designer, these processes should be automated.

###  2.2 BIAS toolbox

BIAS [17] is an open-source Python package, available from [18], to benchmark
SB in the continuous domain. The toolbox provides an SB detection mechanism
based on the aggregation of the results of 39 statistical tests and a Random
Forest model to identify the type of structural bias. It furthermore contains
a data generator to sample data from a set of scenarios producing synthetic
results; a component producing the parallel coordinate plots of the final best
positions to display SB and those reporting the outcome of the decisions made
with statistical analysis while detecting SB.

The BIAS toolbox is easy to use, is extendable and makes the SB detection
process fast and simple, also over a large dataset of final best positions. It
facilitates benchmarking of other statistical tests for detecting structural
bias.

Figure 1: General one-dimensional CNN architecture with optimal hyper-
parameters per sample size. The network takes as input a sorted distribution
fixed sample size. Yellow layers are 1d-CNN layers, red layers are max-pooling
layers, green layer is a dense layer and finally a classification head with
SoftMax activation function resulting in five class probabilities per sample.

##  3 Methodology

The method proposed here extends the functionality of BIAS. It uses a deep
learning-based model to predict the presence and type of structural bias. The
model is trained on a large portfolio of bias scenarios and is optimised using
AutoKeras. In this section, we first provide an overview of the scenarios and
the generator used to train the model. Then the model training and testing
procedures are explained in detail.

###  3.1 Portfolio of scenarios

The proposed Deep-BIAS method is based on the parameterised SB scenarios
proposed in [3]. This portfolio of scenarios includes the most common types of
structural bias as observed in previous studies, including:

  * •

bias towards the centre of the search space,

  * •

bias towards the bounds of the search space,

  * •

bias towards certain parts of the search space forming clusters,

  * •

bias towards avoiding certain parts of the search space, creating gaps and

  * •

strong discretisation.

In the original paper, there are $11$ different scenarios with different
parameter settings, giving in total a set of $194$ parameterized scenarios.
After visual and analytical analysis of the parameters of these scenarios, we
removed $5$ of these parameter settings, as they frequently generated
distributions visually and statistically equivalent to random uniform
distributions using only $600$ samples. This leaves a total of $189$
parameterized distribution generators (still $11$ scenarios), which we use to
generate train and test data sets.

To train the deep learning model, we divide the $11$ scenarios into four
classes, _Center, Bounds, Gaps/Clusters_ and _Discretisation_. We argue that
gaps and cluster bias are highly overlapping, as you have gaps in the search
space when there are clusters and vice versa. Therefore, they are added
together under one class label. For each class $20.000$ distributions are
generated, equally divided over the parameter settings and scenarios that
belong to each class label. For the uniform (no bias) label, we generated
$80.000$ distributions to make the prediction task balanced between bias and
non-bias samples. In total, this gives a data set of $160.000$ one-dimensional
distributions, of which $80\%$ is used as training and $20\%$ as final
validation (using stratified sampling).

###  3.2 Optimized Convolutional Neural Network

In the next step, a deep one-dimensional convolutional neural network (1d CNN)
is trained and optimised using the AutoKeras [19] algorithm. Each distribution
is first ordered in ascending order of the values and then used as input for
the 1d CNN. AutoKeras is set to run with an evaluation budget of $100$ trials
and without image augmentation and pre-processing (this would have no meaning
in our situation since we are not dealing with images). Each network is
trained for $50$ epochs and uses a small randomly selected validation set
(from the original training data) to compare different models with each other.
The best neural network instance is stored and used in this work. The general
architecture of the models is visualised in Figure 1. There are two blocks,
each containing two convolutional layers followed by a max pooling layer. The
second block is half the size of the first. Followed by a dense layer and a
SoftMax classification head. In total, there are four models, one for each
sample size of 30, 50, 100 and 600. Training and optimisation of the networks
took roughly one day per sample size on an NVIDIA T4 GPU.

###  3.3 Predicting SB and SB type

The optimised CNN models can now be used to directly predict any distribution
for the presence and type of structural bias. First, we examine the models
using the final validation set left out.

Figure 2: Confusion matrices for the models with sample sizes from left to
right: 30, 50, 100 and 600. The horizontal axis denotes the Predicted labels
and the vertical axis the True labels. Trained on a data set of 128.000 one-
dimensional distributions and validated on a set of 32.000 distributions. The
600 samples model has a macro F1 score of 0.95.

In Figure 2, the classification results for each sample size are shown. It can
be seen that the classification results obviously improve with the number of
samples, which is also the case for the statistical approach proposed in [3].
Interestingly, even the $50$ samples network is doing a good job of predicting
uniform distributions as uniform. Most misclassifications occur when the model
predicts the distribution to be uniform, but this is not the case.

To further analyse the misclassifications of each of the models, we used the
explainable artificial intelligence (XAI) method, SHAP [20], which
approximates Shapley values [21] based on a background sample set from
training data. Using the Shapley values for each point in the distribution, it
is possible to highlight regions of interest for a particular prediction. In
Figure 3, four examples of predictions are shown that do not match the ground
truth. These examples come from the $600$ sample size model. It is important
to note that there is a high level of randomness in many scenario generators.
It can therefore occur that clusters are very much overlapping, creating a
uniformly distributed sample, or that clusters can be located in the centre or
at the bounds, which deceives the classifier. In the examples shown, it is
also visible that some of the generators can generate such subtle deviations
(tiny gaps in a uniform distribution) that they are hard to classify
correctly, as these can also occur randomly in a random uniform distribution
by chance for $600$ samples.

Figure 3: Examples of (wrongly) classified samples due to overlap in classes.
Clusters can be located by chance on the bounds or in the center of the space,
small gaps can occur randomly in uniform sampling by chance. Colours indicate
Shapley values where dark red indicates a positive contribution towards the
class label (either predicted (up) or ground truth (bellow)), and dark blue
indicates a negative contribution. Sample points with similar values are
stacked on top each other.

Next, the Deep-BIAS method is compared to the original BIAS toolbox. The
comparison is done by transforming the problem into a binary problem to detect
SB. Since the original BIAS toolbox is also validated in this way on a
different number of dimensions (not just one-dimensional distributions), the
same experiment is repeated here. The following dimensions are evaluated: 1,
10, 20 and 30. For each of these dimensionalities ($d$), a test set of $1890$
biased and $1890$ unbiased $d$-dimensional distributions are generated. These
distributions are then predicted by both the original BIAS toolbox and the
newly proposed Deep-BIAS method. For the proposed method, the class
probabilities are averaged over all dimensions to give a final prediction per
$d$-dimensional distribution. We define a configuration as biased if at least
$10\%$ of its dimensions are classified as non-uniform. This threshold is
chosen to remain consistent with the original BIAS toolbox [3].

Figure 4: Comparison (with $\alpha=0.01$) of the original BIAS toolbox (blue)
and the Deep-BIAS (teal) in terms of false positives (left), false negatives
(middle) and F1-score (right). On all figures, markers identify the used
sample size: $\circ$, $\diamondsuit$, $\triangle$ and $\square$ are 30, 50,
100 and 600, respectively.

The results of this experiment are shown in Figure 4, where false positives,
false negatives, and F1 scores are compared for different dimensions and
sample sizes. We can see that while Deep-BIAS has a slightly higher rate of
false positives, this is compensated by a significantly lower false negative
rate. In general, the F1 score for Deep-BIAS is slightly higher, indicating
that it slightly outperforms the statistical approach.

##  4 Benchmarking structural bias of real algorithmic data

This section benchmarks a large set of heuristic optimisation algorithms by
applying the BIAS toolbox, answering RQ3.

###  4.1 Data collection setup

We use data from a heterogeneous pool of heuristics executed on $f_{0}$ at
dimensionality $n=30$ for a maximum of $10000\cdot n$ fitness functional
calls. In total, we consider $336$ optimisation heuristics that fall into the
following categories (all use $N=100$):

  * •

Variants of Differential Evolution ($195$ configurations),

  * •

Compact optimisation algorithms ($81$ configurations),

  * •

Single-solution algorithms ($60$ configurations),

For the sake of clarity and reproducibility, the exact composition and setup
of these algorithmic configurations are fully described in a dedicated
document available from [18].

###  4.2 Results

First, we compare the decisions made by the Deep-BIAS method with those of the
original toolbox on the set of single-solution algorithms. This is done by
showing the class probabilities of both methods for each algorithm in Figure
5(b). From this figure, we see that, in most cases, both methods give the same
biased/non-biased outcome. However, the type of bias detected varies for a
large part of the algorithms. This often occurs when the random forest (RF)
model of the original toolbox predicts ‘clusters’. This might be due in part
to the differences in training data for the two models, combined with the fact
that for some cluster settings, the clusters might be located near the bounds,
making the distinction between these two classes somewhat fuzzy.

In addition to the comparison of the single-solution algorithms, we can also
investigate the impact on different versions of Differential Evolution to gain
insight into the relationship between the algorithm configuration and the
types of bias detected. In this setting, we highlight only the algorithm for
which the two models make different biased/non-biased decisions and show the
resulting class probabilities in Figure 5(a). It is clear that there are two
distinct cases here: for most models where the RF decides that the
configuration is biased, it predicts ‘discretisation’. This matches the fact
that these configurations all use the ‘saturate’ boundary correction, which
places any infeasible solution back on the boundary. As such, if an algorithm
generates some fraction of infeasible solutions, there is a high probability
that at least some of the coordinates are placed exactly on the boundary,
resulting in several equal values for some coordinates. This is highly
unlikely for a uniform distribution, so statistical tests easily detect this
discrepancy.

For Figures 5(b) and 5(a), it is also important to note that for the RF model,
the class probabilities sum up to 1 by design, which is not the case for the
deep model, as the uniform class still gets some of the probability mass. Thus
the outcome of Deep-BIAS gives indirectly a measure of the strength of the
bias.

(a) DE configurations

(b) Single solution algorithms

Figure 5: Predictions of types of non-uniformity made by the Deep-BIAS (left
of white dash line) and original (right of white dash line) bias methods on
the sets of DE configurations (left) and single solution algorithms (right)
where the two methods give a different biased / non-biased outcome. For the
original method, the probabilities are determined by the random forest model
when the configuration is considered biased and set to 0 otherwise. For Deep-
BIAS, the predictions are the average of the per-dimension predictions. The
colour bar on the right applies to both sub-figures.

To gain more insight into the scenarios where the Deep-BIAS model differs from
the original toolbox, we can zoom in on two configurations where their
predictions disagree. Figure 6 shows two scenarios which highlight the
differences in behaviour between the two methods for detecting bias. In Figure
6(a), we show a DE-variant for which the statistical tests clearly detect non-
uniformity, while the Deep-BIAS model finds no strong evidence for structural
bias. When looking at the distribution of the points, we notice that many
dimensions have multiple points which lie exactly at the border. This is a
natural effect of the ‘saturate’ boundary correction method, since this places
points generated outside the domain on the closest boundary. Since the
probability of a uniform distribution generating a point exactly on the border
is $0$, the cases where multiple points are on the bound are seemingly easy to
detect by a wide variety of tests. The Deep-BIAS model however, does not have
this context, so it is less sensitive to the saturation of the boundaries.

(a) DE-best/1/bin_p20 (s)

(b) Solis-Wets (C)

Figure 6: Overview of the positions (top), statistical test results (middle)
and deep predictions (bottom) for two algorithms (dimensions 1 to 15 out of 30
are shown). Colours in the top part are based on the SHAP values as discussed
in the caption of Figure 3. Legend on the left applies to both subfigures.

In Figure 6(b), we show the reverse case: the statistical tests are not
rejected, but the Deep-BIAS model consistently classifies the points as non-
uniformly distributed. Interestingly, the distribution visually seem to have
slightly more mass in the centre of the space. However, the deviations are
very small, and as such the tests are not confident enough to be able to
reject the null-hypothesis after the necessary p-value corrections are
applied. Since this case does not have enough test-rejections, we might argue
that it can be considered as non-biased. However, since the deep model is not
limited to binary decisions, we can instead make use of the resulting
probabilities to highlight this setting as having a very low level of bias.
This shows how both methods can be used together to make more informative
decisions on the presence, strength and type of structural bias.

##  5 Reproducibility statement

We provide an open-source documented implementation of our Deep-BIAS package
on Github [4]. Experiments, additional figures, and documentation can be found
there. Pre-trained models are available on the same repository under the
‘models’ directory. All models are trained using a single T4 GPU and the
computations are carbon neutral ($CO_{2}$-free) by using solar power.

##  6 Conclusion

In light of the analysis performed in this study, we conclude that the use of
deep learning is a viable option to detect SB with satisfactory results. With
only $50$ samples, we can correctly detect most uniformly distributed points,
and performances increase with larger sample sizes. We find that the optimal
network architecture for detecting SB is not as complex as those often
designed in other deep learning applications in the literature, and yet it
behaves similarly to the original BIAS toolbox, which is based on statistical
tests, and performs very well in terms of the F1 score evaluation metric.

Compared to BIAS, the proposed Deep-BIAS alternative displays some interesting
features and advantageous behaviours.

  * •

It outperforms the statistical test-based approach in classifying the type of
SB.

  * •

It gives a better measure of strength of the SB by using the class
probabilities.

  * •

It provides additional insights by using XAI, where regions of interest in
distributions can be further analysed to understand the mechanism behind the
classifications.

A disadvantage of using a neural model is that the resulting SB detection
system is less generalisable than that obtained with a statistical test
approach, where the network might miss SB types that are not considered in the
training data. However, the training data set prepared for Deep-BIAS appears
to be adequate, and the network fails to find bias mainly when the saturate
constraint handling method is used. This is not a problem for BIAS. For these
reasons, the overarching conclusion of this study envisages the joint use of
the 2 systems for optimal SB detection. We recommend using BIAS as the primary
method for binary bias/non-bias classification and Deep-BIAS to inspect the
type of SB and determine its strength.

## References

  * [1] D. Wolpert and W. Macready.  No free lunch theorems for optimization.  IEEE Transactions on Evolutionary Computation, 1:67–82, 1997.
  * [2] Nikolaus Hansen, Anne Auger, Raymond Ros, Olaf Mersmann, Tea Tušar, and Dimo Brockhoff.  Coco: A platform for comparing continuous optimizers in a black-box setting.  Optimization Methods and Software, 36(1):114–144, 2021.
  * [3] Diederick Vermetten, Bas van Stein, Fabio Caraffini, Leandro L. Minku, and Anna V. Kononova.  Bias: A toolbox for benchmarking structural bias in the continuous domain.  IEEE Transactions on Evolutionary Computation, 26(6):1380–1393, 2022.
  * [4] Anonymous Authors.  Deep-bias v1.0.0, January 2023.
  * [5] Anna V. Kononova, David W. Corne, Philippe De Wilde, Vsevolod Shneer, and Fabio Caraffini.  Structural bias in population-based algorithms.  Information Sciences, 298:468–490, 2015.
  * [6] Alfred Inselberg.  The plane with parallel coordinates.  The visual computer, 1(2):69–91, 1985.
  * [7] Fabio Caraffini, Anna V. Kononova, and David W. Corne.  Infeasibility and structural bias in differential evolution.  Information Sciences, 496:161–179, 2019.
  * [8] Bas van Stein, Fabio Caraffini, and Anna V. Kononova.  Emergence of structural bias in differential evolution.  In Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion, GECCO ’21 Companion, New York, NY, USA, July 2021. Association for Computing Machinery.
  * [9] Fabio Caraffini and Anna V. Kononova.  Structural bias in optimisation algorithms: Extended results, 2021.
  * [10] Bas van Stein, Fabio Caraffini, and Anna V. Kononova.  Emergence of Structural Bias in Differential Evolution - Source code & extended graphical results, 2021.
  * [11] Andrey Nikolaevich Kolmogorov.  Sulla determinazione empirica di una legge di distribuzione.  Giornale dell’Istituto Italiano degli Attuari, 4:83–91, 1933.
  * [12] Sandor Csorgo and Julian J. Faraway.  The Exact and Asymptotic Distributions of Cramer-von Mises Statistics.  Journal of the Royal Statistical Society. Series B (Methodological), 58(1):221–234, 1996.
  * [13] Theodore W Anderson and Donald A Darling.  Asymptotic theory of certain “goodness of fit” criteria based on stochastic processes.  The annals of mathematical statistics, pages 193–212, 1952.
  * [14] Yoav Benjamini.  Discovering the false discovery rate.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72(4):405–416, 2010.
  * [15] Anna V. Kononova, Fabio Caraffini, Hao Wang, and Thomas Bäck.  Can compact optimisation algorithms be structurally biased?  In T. Bäck, M. Preuss, A. Deutz, H. Wang, C. Doerr, M. Emmerich, and H. Trautmann, editors, Parallel Problem Solving from Nature – PPSN XVI, pages 229–242, Cham, 2020. Springer International Publishing.
  * [16] S. S. Kar and A. Ramalingam.  Is 30 the magic number? issues in sample size estimation.  National Journal of Community Medicine, 4(1):175–179, 2013.
  * [17] Diederick Vermetten, Bas van Stein, Fabio Caraffini, Leandro L. Minku, and Anna V. Kononova.  Bias: A toolbox for benchmarking structural bias in the continuous domain.  IEEE Transactions on Evolutionary Computation, 26(6):1380–1393, 2022.
  * [18] Diederick Vermetten, Anna V. Kononova, Fabio Caraffini, Bas van Stein, and Leandro Minku.  Bias: A toolbox for benchmarking structural bias in the continuous domain – code, Sep 2021.
  * [19] Haifeng Jin, Qingquan Song, and Xia Hu.  Auto-keras: An efficient neural architecture search system.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1946–1956. ACM, 2019.
  * [20] Tjeerd van Campen, Herbert Hamers, Bart Husslage, and Roy Lindelauf.  A new approximation method for the shapley value applied to the wtc 9/11 terrorist attack.  Social Network Analysis and Mining, 8(1):1–12, 2018.
  * [21] L. Shapley.  A value for n-person games.  In H. Kuhn and A. Tucker, editors, Contributions to the Theory of Games II, pages 307–317. Princeton University Press, 1953.