Geometric Entropic Exploration

Exploration is essential for solving complex Reinforcement Learning (RL) tasks. Maximum State-Visitation Entropy (MSVE) formulates the exploration problem as a well-defined policy optimization problem whose solution aims at visiting all states as uniformly as possible. This is in contrast to standard uncertainty-based approaches where exploration is transient and eventually vanishes. However, existing approaches to MSVE are theoretically justified only for discrete state-spaces as they are oblivious to the geometry of continuous domains. We address this challenge by introducing Geometric Entropy Maximisation (GEM), a new algorithm that maximises the geometry-aware Shannon entropy of state-visits in both discrete and continuous domains. Our key theoretical contribution is casting geometry-aware MSVE exploration as a tractable problem of optimising a simple and novel noise-contrastive objective function. In our experiments, we show the efficiency of GEM in solving several RL problems with sparse rewards, compared against other deep RL exploration approaches.

Introduction
Exploration is fundamental for reinforcement learning (RL) [Sutton and Barto, 1998] agents to discover new rewarding states and ultimately find an optimal policy. In tabular settings, there exist provably efficient exploration methods based on the idea of giving reward bonuses to less explored or novel states (optimism in the face of uncertainty) [Kearns et al., 2002, Brafman and Tennenholtz, 2002, Kakade et al., 2003, Strehl et al., 2006, Lattimore and Hutter, 2014, Dann and Brunskill, 2015, Azar et al., 2017, Cohen et al., 2020, Tarbouriech et al., 2019). In practice, scaling these methods beyond small, tabular settings requires using function approximators for estimating uncertainty [Bellemare et al., 2016, Osband et al., 2016, Ostrovski et al., 2017, Pathak et al., 2017, Osband et al., 2018, Burda et al., 2018. As these uncertainty estimates are non-stationary and vanishing, this requires careful tweaking of the learning process to remain stable while allowing the policies produced by the RL algorithm to adequately explore the environment before the novelty incentive vanishes.
One way to address this issue is to learn a single stochastic policy that visits all states as uniformly as possible, which corresponds to solving the Maximum State-Visitation Entropy (MSVE) [Hazan et al., 2018, de Farias and Van Roy, 2003, Lee et al., 2019 exploration problem. In contrast to methods with vanishing bonuses that eventually stop exploring, the MSVE approach results in a stationary optimisation setup that converges to a single, stochastic exploration policy that follows different paths in different episodes, in order to cover the entire state space.
Past approaches on MSVE have been theoretically justified for discrete state spaces, as they try to maximise the discrete Shannon entropy of the state-visitation dis-arXiv:2101.02055v2 [cs.LG] 7 Jan 2021 tribution [Hazan et al., 2018, de Farias and Van Roy, 2003, Lee et al., 2019, Pong et al., 2019. While some practical approaches can be empirically applied to continuous state spaces by using density estimation techniques [Lee et al., 2019, Pong et al., 2019, their theory is still focused on discrete entropy; they do not take into account the underlying geometry implied by their density estimator. To bridge this gap, we build upon the Geometry-Aware Information Theory (GAIT) framework [Gallego-Posada et al., 2019], which relies on a similarity function k(x, x ) between states to capture the underlying geometry. Then, a geometry-aware version of Shannon entropy can be defined in terms of k that works across both discrete and continuous distributions. Ideally one would like to learn a similarity function that captures the specific geometry/structure of the problem domain.
To learn a geometry-aware exploration policy, one may directly try to maximise the geometry-aware Shannon entropy of the state-visitation distribution w.r.t. both the policy and similarity function k. However this direct approach may not succeed due to the following challenges: (i) Learning collapse. The similarity function k will ignore the geometry of the problem and collapse to an indicator function for the sake of increasing entropy, and thus is ill-defined for continuous domains. (ii) Intractability. Even with a fixed k, obtaining an unbiased estimate of this objective (or its gradients) is intractable in its original form.
In this paper we address these challenges by introducing Geometric Entropy Maximisation (GEM), a novel exploration algorithm for learning a policy that maximises the geometry-aware Shannon entropy of statevisits for a given similarity k. GEM casts the geometryaware MSVE exploration problem as a tractable noisecontrastive estimation (NCE) problem [Gutmann and Hyvärinen, 2010], via optimising a single objective function whose unbiased gradient estimates are easily computed. Maximising the GEM objective results in simultaneously learning both the optimal exploration policy and its corresponding state-visitation distribution. We also address the problem of collapse in learning the similarity function by adding an Adjacency Regularisation (AR) term which allows GEM to learn a geometrically meaningful similarity function k. GEM with AR follows two general principles: states that are close in time should be embedded closely (and be similar), whereas states that are sampled independently from the statevisitation distribution should be embedded apart (and be dissimilar). Finally, in our experiments, we show the efficiency of GEM in solving several discrete and continuous RL problems with sparse rewards, compared against other deep RL exploration approaches, namely Random Network Distillation (RND) [Burda et al., 2018] and Never Give Up (NGU) [Badia et al., 2020b].

Background
Markov Decision Processes (MDPs) and Reinforcement Learning. MDPs model stochastic, discrete-time and finite action space control problems [Bellman and Kalaba, 1965, Bertsekas, 1995, Puterman, 1994]. An MDP is a tuple (X , A, R, P, γ, T ) where X is the state space, A the action space, R the reward function, γ ∈ (0, 1) the discount factor, T the length of the episode, and P a stochastic kernel modelling the one-step Markovian dynamics, with P (y|x, a) denoting the probability of transitioning to state y by choosing action a in state x; P is also assumed to comprise a distribution for the initial state of the MDP.
A stochastic policy π maps each state and time to a distribution over actions π(·|x, t) and gives the probability π(a|x, t) of choosing action a in state x at time t. The RL objective is to maximise the expected discounted sum of rewards: E π T t=1 γ t−1 r t where r t = R(x t , a t ) and E π is the expectation over the distribution of trajectories (x 1 , a 1 , . . . , x T +1 ) from policy π.
Deep RL uses deep neural networks as function approximators [Mnih et al., 2015, 2016, Espeholt et al., 2018, Lillicrap et al., 2015. One class of such methods are policy gradient methods [Williams, 1992, Espeholt et al., 2018, which we build on to do MSVE exploration. In its simplest formulation, a deep policy gradient method learns a neural network policy π θ with parameters θ, by doing gradient ascent on the RL objective with respect to θ [Sutton et al., 1999].
Geometry-Aware Shannon Entropy. Given a state space X , we endow an underlying geometry by defining a symmetric similarity function k : X × X → [0, 1], where k(x, x ) = 1 means identity and k(x, x ) = 0 means full dissimilarity. Then given a probability distribution p(x) over X , we define its similarity pro- Then the Geometry-Aware Shannon Entropy of p with similarity k is defined as [Gallego-Posada et al., 2019]: If X is discrete, and k(x, x ) = 1(x = x ), then the similarity profile reduces to p k (x) = p(x) and we recover the standard Shannon entropy: However note that in general, with a suitable similarity function, the maximum geometry-aware Shannon entropy distribution can look very different from standard maximum Shannon entropy, as the similarity function is able to decide which states to cluster together and which states to be far apart, resulting in a uniform distribution over space (induced by the similarity) rather than over discrete points.

GEM Approach
We want to solve the geometry-aware MSVE exploration problem. Specifically, we consider finding an exploration policy π E that maximises the geometryaware Shannon entropy of its stationary state-visitation distribution: where p π (x) 1 T T t=1 p π t (x) and p π t (x) is the probability that the MDP will be in state x at timestep t when following π. In general, the solution to this optimisation problem is a stochastic policy that, over many episodes, ends up visiting as many different states as uniformly as possible.
To learn the optimal geometry-aware exploration policy π E one may choose to directly optimise the objective function H k (p π ) which is a well-defined and differentiable function of π. However the problem of maximising this objective is a challenging optimisation problem. At a high level, this is due to the fact that obtaining an unbiased estimate of the gradient of H k (p π ) is not possible in the standard direct way due to having an expectation inside the non-linear logarithmic term ln E x ∼p π [k(x, x )].
A common approach to deal with this type of intractability is to use alternating optimisation, in which as a sub-routine for Eq. 2 the learner first tries to approximate the term E x ∼p π [k(x, x )] and then uses it to maximise an estimate of H k (p π ) w.r.t. π. These alternating methods have been used for solving the Shannon-entropy MSVE as the objective [Lee et al., 2019, Pong et al., 2019. Unfortunately, the alternating approaches cannot eliminate the problem of bias in the estimate of objective function, and often are prone to instability and slow convergence [Bojanowski et al., 2017, Goodfellow, 2016, Nemirovski, 2004.
We tackle the issue of MSVE in a novel way, by defining a different, but closely related objective function whose solution also results in a geometric-aware MSVE policy, and whose unbiased gradient can be easily estimated from data. Proofs are in Appendix A.

From NCE to MSVE Exploration
The idea behind GEM can be traced back to Noise-Contrastive Estimation (NCE) [Gutmann and Hyväri-nen, 2010]. The core idea of NCE is to learn to differentiate between two distributions p + and p − . By optimising the contrastive loss, we can learn the ratio of probabilities p + /p − .
In GEM, we extend NCE to the joint estimation and optimisation of the entropy of the state-visitation distribution. We begin our derivation of the full GEM objective by first introducing a simplified special case corresponding to finite, discrete state spaces. For h : X × X → (0, ∞), consider the following objective: Maximising this objective function can be seen as contrasting positive pairs (x, x) from negative pairs  Wu et al. [2018], is its relation to the MSVE Shannon entropy: Proposition 3.0.1. Given a discrete set of states X and a function h : X × X → [0, ∞), we have max h,π GEM(h, π) = H(p π E ). The maximiser h (x, x ) = 1(x = x )/p π E (x) when p π E (x) > 0, and π E is the Shannon MSVE policy.
As a result, maximising the GEM objective over π and h simultaneously learns both the optimal state-visitation distribution and the MSVE policy as part of a single optimisation procedure.
This simple variant of GEM can be seen as a special case of M-estimation of KL-divergence through Legendre-Fenchel transformation (i.e., convex conjugate) [Nguyen et al., 2010], by using the following equivalency between KL-divergence and Shannon Entropy: where Q(x, x ) 1(x = x)p π (x) and R(x, x ) p π (x)p π (x ). Thus the theoretical results of [Nguyen et al., 2010] can be used directly to prove Proposition 3.0.1.
To make progress towards our general geometry-aware objective, we note that the optimal h (x, x ) vanishes for x = x . Therefore we introduce a new function g : X → (0, ∞) and re-parameterise h(x, x ) = 1(x = x )g(x). The objective function of Eq. 3 can then be expressed in terms of g as and we can adapt the result from Proposition 3.0.1 in following corollary: In the next section, we extend Eq. 4 to handle the general case of geometry-aware Shannon entropy.

GEM with Similarity Functions
The formulation of GEM in Eq. 4 is not, as-is, suitable for continuous state-spaces. The indicator function in the term E x,x ∼p π [1(x = x )g(x)] becomes ill-defined and the objective breaks down. To generalise GEM to continuous state-spaces, we replace the indicator function 1(x = x ) with a symmetric similarity function can then be replaced by the similarity profile p π k (x) E x ∼p π [k(x, x )], with induced geometry-aware Shannon entropy H k (p π ) Gallego-Posada et al. [2019]. The similarity function k will ideally capture the inherent structure of the state space, leading to a geometrically meaningful entropy. This can result in more efficient exploration with a suitable similarity function that ends up clustering together less important states, and thus a maximum geometryaware policy would not visit those less important states as often as other, more important states.
We now introduce the full, geometry-aware form of the GEM objective function: We generalise Corollary 3.0.1 to encompass similarity functions in Theorem 3.1.
Theorem 3.1. Let g : X → (0, ∞). Given a similarity function k : X × X → [0, 1]. Then we have max g,π GEM k (g, π) = H k (p π E ), where the maximiser is By replacing the indicator function with the similarity function k, the GEM objective generalises from discrete Shannon entropy to geometry-aware Shannon entropy, and the maximiser g generalises from the inverse probability to the inverse similarity profile. GEM can now be readily applied to both discrete and continuous state spaces.
Compared to the intractable problem of directly maximising for the geometric-aware MSVE policy, an unbiased estimate of the gradients of GEM is easily computable, and thus GEM can be solved efficiently with standard optimisers. The following theoretical result formalises this argument for the case that we parameterise π and g with some function approximatiors. Proposition 3.1.1. Let π and g be approximated by some differentiable function approximators with sets of parameters θ and ξ respectively. Let r GEM , where x t is drawn independently from p π at every time step t. Then unbiased estimates of the gradient of GEM objective w.r.t. θ and ξ are, respectively, There are a few notable remarks concerning this result.
(i) The gradient of the GEM objective function w.r.t. the parameters of policy is expressed as a standard policy gradient, and so one can use a conventional policy gradient solver to efficiently optimise the GEM policy with the reward r GEM t . In our experiments, we use a standard V-Trace Actor-Critic approach Espeholt et al. [2018].
(ii) As these two gradient terms correspond to the same objective function, one can simultaneously optimise π and g together through a single optimisation procedure, avoiding the need for alternating optimisation techniques. The fact that the geometry-aware MSVE problem can be solved efficiently in this way may seem surprising, as its solution is the same as the intractable optimization problem of Eq. 2. The difference is that GEM casts the problem of geometry-aware MSVE as a joint optimisation in terms of the exploration policy π as well as g. In this larger function space the problem of geometric-aware MSVE is no longer intractable and can be solved efficiently, unlike the optimization problem of Eq. 2 in which only π is optimised. (iii) The main GEM objective (Eq. 5) can be further generalised to maximise a geometry-aware version of Tsallis entropy. See Appendix A for details.

Learning a Similarity Function
So far, we have assumed that a similarity function k(x, x ) has been given. However, we would ideally like to learn a geometrically meaningful k from data as a part of GEM. One can simply learn the similarity function by maximising GEM w.r.t. k as well. If we do this in the finite, discrete case, we can recover Corollary 3.0.1 from Theorem 3.1 as shown in the following proposition: Proposition 3.1.2. If X is a finite set, then max k,g,π GEM k (g, π) = H(p π E ) is attained for k (x, x ) = 1(x = x ) and g (x, π) = 1/p π E (x).
Note that k converges to an indicator function. However, in the continuous case, trying to converge to the indicator function makes the whole problem ill-defined. To show this effect, we use GEM to learn a simple 1D bi-modal Gaussian mixture. We parameterise g with a small MLP. We consider two versions of k: (i) one version is fixed with k(x, x ) = e −2|x−x | which represents what we think a good similarity function should be, and (ii) we parameterise k using a neural network embedding function f as k(x, x ) = e − f (x)−f (x ) 2 and maximise over it as well. For the distributions to be learned, we consider both a discretised and the continuous version of the simple 1D bi-modal Gaussian mixture. Fig. 1 shows the learned probabilities and densities computed from g for the four configurations. For the discrete distribution shown on the left, both a fixed and a learned similarity function perform well and can approximate the probability distribution. For the continuous case on the right, the fixed similarity learns a close approximation, while the learned similarity collapses into a uniform distribution. The reason for the collapse is that the non-linear embedding function f is able to flatten out the data distribution, converting the original distribution into a uniform distribution; which is the maximum entropy distribution.
Therefore, in all but the simplest cases, we cannot solely learn a similarity function through maximising the GEM objective. In general, we may need to rely on domain-specific knowledge in order to learn a well-structured and meaningful similarity function. Nonetheless for MDPs, it is possible to learn a generic yet meaningful similarity based on temporal structure. We keep the parameterisation of the similarity function as k(x, x ) = e −c f (x)−f (x ) 2 , and augment our objective with an additional regularization term on the embeddings f , which we call adjacency regularisation. The adjacency regularisation (AR) is a generalised pseudo-Huber loss with exponent q and offset δ: . This regularisation pulls together the embeddings of timeadjacent states. Combined with GEM, which tries to expand the distance between embeddings, this trains an embedding where approximately the closest states are those that are 1-step apart; the second closest states are those that are 2-steps apart; and so on and so forth. This is similar to the notion of reachability [Savinov et al., 2018], which tries to learn the expected shortest number of steps between any two states. We note that the higher values of exponent q are more robust to distribution shift and relate closer to a reachability distance. In our experiments we find than that q = 4 works well.
Note that AR is symmetric in time. This means that AR ends up averaging the contribution of asymmetric transitions. For example, a one-way transition between x t and x t+1 is approximately equivalent to a symmetric transition with probability 0.5.

GEM Algorithm
The final GEM algorithm is the combination of the geometry-aware GEM objective, AR, and maximising the environment reward (see Algorithm 1). To train the embedding f we optimise the combination of the AR objective and GEM objective (Line 10). To train g, we maximise the empirical GEM objective (Line 8). 1 Finally, to train π, we use a policy gradient algorithm (Line 9). Note that π is optimised with respect to the empirical estimate of the GEM objective function plus the environment reward, aimed at striking a balance between MSVE exploration and exploitation. More details on the algorithm is in Appendix B.

GEM Experiments
In this section, we conduct in-depth experimental analyses of various aspects of the GEM algorithm. All plots show 95% confidence intervals over 5 seeds. The details on the implementation and the choice of hyperparameters are in Appendix B.

Intrinsic Reward Normalization
The magnitude and variance of the intrinsic reward can vary greatly across different environments. To mix Algorithm 1: Pseudocode of GEM Inputs: neural networks g and f , policy π, Huber offset δ, Huber exponent q, regularisation scale c For every x t draw a randomly shuffled sample PolicyGradientStep for max π t R t from Eq. 6 10 Take gradient step for 1/q intrinsic and extrinsic rewards in a consistent way in our experiments, we first standardise, scale, and shift our intrinsic reward is an exponential running average of the mean (respectively standard deviation) of the intrinsic reward, and s and m are hyperparameters for the new standard deviation and mean. We then sum this normalized intrinsic reward with the extrinsic reward R t = r t + r GEM t . We found that using this more general normalisation scheme allows GEM to be robust to different resolutions of the learned embedding and different sizes of environments.

Comparisons with Baselines
To test the basic exploration capabilities of GEM, we start with a simple 2-Rooms gridworld environment consisting of two rooms and a bottleneck connection (Fig. 2). The agent starts in the top-left-hand corner, and thus must go all the way to the right and then down to pass the bottleneck in order to reach the goal in the bottom-left corner.
To test the ability to do exhaustive exploration, we designed a tree-like gridworld: 16-Leaves (Fig. 2). The agent starts near the centre, and needs to branch off in multiple directions, ending up in one of the 16 "leaves". Every episode, one of the green squares in a leaf is randomly picked, and a reward block is placed there; all the other green squares become normal free squares. Moreover, each episode is barely long enough for an agent to reach the end of one leaf. Therefore, an agent must exhaustively explore all leaves in order to learn that visiting the green square results in a reward. Importantly, the agent must be able to visit different leaves across episodes. In both the 2-Rooms and 16-Leaves environments, the agent is given as input an RGB observation from which it must learn to extract relevant features with a deep convolutional neural network. Figure 2: 2-Rooms and 16-Leaves gridworld environments. Every episode, the agent spawns randomly in one blue square, and a reward spawns randomly in one of the green squares.

Comparison with the Empirical Oracle MSVE
In this experiment we compare the performance of GEM with an idealised variant of alternating optimisation approach taken by some prior work [Lee et al., 2019, Pong et al., 2019. The basic alternating optimisation approach is to first estimate the stationary distribution over states p π (x), often using a generative model or a non-parametric estimate such as kernel-density estimation. Then the intrinsic reward is set to be − log p(x), in order to drive the policy towards less visited states.
We use an empirical oracle to estimate the stationary distribution p π (x), by using an exponential moving average of visitation counts of the true states, which is essentially the best that can be done for these simple, discrete domains. Note that this uses privileged information on the state index to get access to the true statevisitation counts from the environment. Thus, this is not a practically implementable approach in larger or continuous domains. Also note that no geometry-aware information is being used; standard Shannon entropy is being maximised over the true states.
We simulate an alternating optimisation scheme that updates the counts every step, but only updates the policy every n steps, where n ∈ {1, 5, 10}. This simulates the effect of letting the inner optimization take more gradient steps in order to be more accurate for the case when using function approximation. Because we use true counts, our alternating optimisation is stable even for n = 1, but in general with function approximation, n > 1 may be necessary for stability. fast as the idealised case of n = 1, and multiple times faster than larger values of n. These results show that the GEM algorithm is very efficient and confirms that it does not require complex optimization schemes to be stable; everything is optimized and updated together. Furthermore, the reason GEM is able to match the oracle even with function approximation is because GEM takes advantage of geometry information, which allows GEM to focus exploration on more interesting states. See Section 4.3.1 for a more in-depth look at how geometry affects GEM exploration.

Comparison with NGU and RND
Here, we compare against 3 baselines: RND, NGU without RND, and NGU with RND. RND (Random Network Distillation) is a simple technique that computes an intrinsic reward based on prediction error of predicting a fixed, random projection of the observation [Burda et al., 2018]. It is an example of a transient intrinsic reward that eventually vanishes. NGU (Never Give Up) keeps an episodic memory of visited state embeddings, and computes an intrinsic reward for the next state that is inversely correlated with its distance to previously visited states [Badia et al., 2020b]. NGU converges to a policy that tries to visit diverse states within an episode, but has no incentive to be diverse across episodes. The combination of NGU with RND uses NGU to be diverse within episodes, and relies on RND to be diverse across episodes and across training, and is state-of-the-art for exploration on Atari [Badia et al., 2020a]. The behaviour of the GEM algorithm is similar to NGU with RND, as trying to maximize entropy implies diversity both within an episode and across episodes in order to visit all states. However GEM is able to achieve this kind of behaviour through a single, simple, principled objective, without needing to add extra components.
From Fig. 4 we see the shortcomings of NGU without RND, which is not able to be diverse across episodes, and thus is not able to efficiently explore all the different leaves of 16-Leaves, and converges to a sub-optimal policy. RND is also not very effective, as it is slow and unstable, and heavily dependent on neural network architecture. NGU with RND is able to combine the best of both and consistently solves all tasks. Finally, GEM is also able to achieve the best of both worlds and be faster at solving the gridworld tasks.
MountainCar and CartpoleSwingup domains are standard, sparse-reward environments. Both are continuous-state domains with asymmetric transitions. We see that although the AR used in the GEM objective is symmetric, GEM has no problem learning a useful state embedding and similarity function for solving these tasks, and is comparable with baselines.

Impact of Adjacency Regularization
In this section, we show the effect of using adjacency regularization (AR) to shape the embeddings and similarity function. We compare GEM with and without AR on the 2-Rooms environment. We also test on a noisy version of the environment, where we add a square whose colour is randomly chosen from 65536 different colours at every step.
In Fig. 5, we see that when using AR, there is no difference in performance between noiseless and noisy environments. On the other hand, without AR, the agent completely fails to solve the noisy task. In fact,  it fails improve upon a uniformly random policy.
Taking a closer look, we examine the embeddings learned for the 4 different settings. Fig. 6 shows the first two principal components of the learned embeddings. We see that AR is able to learn the grid-like geometry of 2-Rooms and is completely robust to noise. However, without AR, the learned embeddings are completely random, and are heavily impacted by the noise instead of ignoring it. Since the noise is a much larger source of entropy than the agent position, GEM can trivially maximize entropy by just paying attention to the noise. Further insights into the structure of learned embeddings can be found in Appendix C.

Embedding Resolution
In this section, we examine how the exploration behavior of GEM is affected by the resolution of the embeddings and the similarity function. We can make the resolution finer by making the distance between embedding points larger, and thus less similar (a coarser resolution means distances are smaller, and thus states are more similar). This can be done by increasing the Huber offset δ in AR (Eq. 8), or decreasing the scale of the regularisation c in the total loss. We compare three different resolutions: coarse (δ = 0.3, c = 20), medium (δ = 0.6, c = 10), and fine (δ = 1, c = 1). Fig. 7 shows the true visitation entropy achieved for these resolutions, with finer resolutions resulting in larger entropy. This is because coarser embeddings cluster states closer together, leading to a smaller effective state space and a smaller maximum visitation entropy. A different illustration of this phenomenon is given in Fig. 7, which shows the visitation heatmaps in 2-Rooms for the three resolutions. For the fine case, the state-visitation distribution is close to uniform in each of the rooms, whereas for the medium case it becomes skewed towards the room boundaries. This is due to states in the middle of the rooms being clustered together, while the opposite boundaries of the room are dissimilar enough that they count as distinct states. Finally, for the the coarse case, the embeddings are so close together that they effectively form a line and there is no entropic incentive to deviate from a single path.
These results show that the exploratory behavior can be modified by tuning the resolution of the embeddings. In particular, the ability to reduce the effective state space size by employing coarser embeddings is especially important when scaling up the algorithm to larger and larger state spaces.

Related Work
Prior work in MSVE exploration used an iterative algorithm that requires retaining a mixture of all past policies as well as kernel density estimation for estimating densities [Hazan et al., 2018], which is hard to scale to larger and complex domains for which a kernel is hard to define. Approximations were later which improved computational complexity but only for the tabular setting [Mutti and Restelli, 2020]. Maximum entropy can also be viewed as trying to match the state-visitation distribution to a uniform distribution, as a special case from [Lee et al., 2019], which casts the problem as a two-player minimax game. Thus this approach requires the use of alternating optimisation schemes which need additional optimisation tweaks to be stable. It is also possible to estimate differential Shannon entropy using non-parametric k-nearest neighbour methods [Beirlant et al., 1997], however their connection to geometry-aware Shannon entropy is unclear. Beyond geometry-aware Shannon entropy, there is work on other entropy measures that are geometrically-aware such as Sinkhorn negentropy [Mensch et al., 2019].
Maximising diversity instead of entropy is a similar objective that tries to visit as many different states as possible. Approaches such has maximising diversity between trajectories can be used to discover skills for reaching diverse sets of states Other approaches that use intrinsic rewards for exploration design such exploration bonuses to compute a non-stationary, decaying novelty [Strehl et al., 2006, Bellemare et al., 2016, Schmidhuber, 1991 and therefore are more difficult to optimise as well as they do not come with a straightforward way to inject structure. Yet another approach is to try finding policies that look for the stochastic shortest path [Tarbouriech et al., 2019, Cohen et al., 2020. A more global approach is taken by Jin et al.
[2020] which defines reward-free reinforcement learning as a quest for generating a given number of reward-free trajectories.
GEM can be seen as a noise-contrastive approach [Gutmann andHyvärinen, 2010, Ozair et al., 2019] for MSVE, where both positive and negative distributions are built upon the same underlying distribution [Wu et al., 2018]. There are key innovations in the design of the GEM objective through which we generalise the noise-contrastive approach to tackle the MSVE exploration problem at scale. In particular, (i) GEM uses different losses for the positive and negative examples, resulting in an asymmetric loss that maximises the Shannon entropy, and (ii) GEM deploys a similarity function between pairs of states through which GEM can generalize its estimation of state-visitation distributions to continuous spaces.
Finally, AR regularisation has been previously used to learn the state representation in the control literature [Lesort et al., 2018] under the name slowness feature analysis [Wiskott andSejnowski, 2002, Böhmer et al., 2015]. However in prior work AR is used as an auxiliary task for RL or imitation learning. Whereas in GEM AR regularisation is an indispensable component of the main algorithm.

Conclusion
In this paper, we introduced GEM, Geometric Entropy Maximisation, a new approach for exploration in RL, with two main contributions. First, our key theoretical contribution is casting geometry-aware maximum state-visitation entropy as the tractable problem of optimising a simple, novel noise-contrastive objective. Second, to capture the geometry of the domain, we equip GEM with a similarity function, learned through Adjacency Regularisation (AR), a simple regularisation term added to the GEM objective. AR allows us to learn a similarity function that preserves the temporal structure of the MDP in our embeddings. We have numerically evaluated GEM on discrete-and continuousstate sparse reward problems where we can analyse and measure exploratory behaviour, and we have shown that our approach is efficient and robust to noise. By maximising the overall entropy of the state-visitation distribution, we allow for both inter and intra-episode diversity of states.

A.1 From NCE to the GEM Objective Function
The main GEM idea can be traced back to noise-contrastive estimation (NCE) [Gutmann and Hyvärinen, 2010]. The core idea of NCE is to learn to contrast between two separate distributions, with positive examples drawn from p + and negative examples drawn from p − . For this we often use a classifier h(z) = g(z) 1+g(z) , with g(z) is some positive function often paramterised as g(z) = e s(z) , where s(z) are the classifier logits. The objective of NCE is then a binary logistic regression maximisation: Then at the optimum, g(z) will converge to the ratio of the probabilities p + (z) p − (z) . In order to extract a single probability rather than a ratio of probabilities, we need to pick specific positive and negative distributions. Similar to [Wu et al., 2018], we turn the contrastive objective into an auto-contrastive objective where we pick positive examples z to be the fully correlated pair (x, x) of samples, and the negative examples to be the pair of fully independent samples (x, x ) of some random variable x, x ∼ p. Then intuitively, the probability of positive examples is p(x), the probability of negative examples is p(x)p(x), and thus the ratio is g(z) = g(x, x) = p(x) p(x)p(x) = 1/p(x). Thus the auto-contrastive objective can be used to estimate probability distributions.
In the context of maximum entropy exploration the cross-entropy objective of Eq. 9 can be used to obtain estimates of state-visitation probabilities in the auto-contrastive regime. However the auto-contrastive objective based on Eq. 9 does not represent a standard notion of entropy by which we desire to tackle the problem of maximum state-visitation entropy (MSVE) exploration. In order to connect back to Shannon entropy, we need to significantly modify the auto-contrastive objective function and turn to using an asymmetric, objective between positive and negative examples as follows where h is constrained to be non-negative. This is the origin of Eq. 3. As we have shown in Proposition 3.0.1, maximising this objective gives us the MSVE policy π E .
Proof. The objective is restated here: To find the maximiser of the objective, we break down the maximization to first maximise for h, and then maximise for π: So first we try to maximise h. Since X is discrete, we can consider h(x, x ) a matrix of variables, where we have a variable for every x, x ∈ X . Then we write out the expectations in terms of sums: Note that h(x, x ) for x = x only appears as a negative term as the second term. Thus, the maximum of zero can be attained by setting h(x, x ) = 0. Thus we can simplify the objective by only considering the variables when x = x , and the letting g x = h(x, x): x p π (x)p π (x)g x + 1.
Since g x is a separate variable for every x, we can maximise this sum by maximising every term of the sum w.r.t.
x, reducing this to the following single variable problem: First, note that when p π (x) = 0, the objective becomes a constant, and therefore does not matter when trying to maximise g(x); g(x) can take on any value. Thus from now on we only consider x such that p π (x) > 0.
Then, we can find the critical points by setting the derivative to zero: To see what kind of critical point this is, we compute the second derivative: Since we are only considering p π (x) > 0, then this second derivative − 1 g 2 x p π (x) < 0. This means that the critical point is a local maximum. Furthermore, since there is only one critical point, and the second derivative is always negative, this local maximum is the global maximum. Thus g x = 1 p π (x) . This also means that Plugging this back into GEM: We get that maximising w.r.t. h results in simply the Shannon entropy of p π . Finally, we put it together to get: Thus the maximiser for π is the optimal Shannon MSVE policy π E = argmax π H(p π ).
Proof. This corollary follows immediately from the proof of Proposition 3.0.1.
Proof. We restate the full, geometry-aware GEM objective function here: Recall that the similarity profile is p π k (x) = E x ∼p π [k(x, x )]. Then we can slightly rewrite the GEM as follows: We then follow the same proof structure as for the proof for Proposition 3.0.1, to first prove the result for the finite case. We first decompose the maximisation into first maximising for g, and then maximising for π: Then we reduce the problem of maximising g to pointwise maximisation of each separate variable g x = g(x) of the following: Solving for the critical point we get, similar to before, that: where instead of p π (x) we now get the similarity profile p π k (x). By the same argument as in the proof for Proposition 3.0.1, the second derivative is negative, and thus this is the global maximum. Plugging this back in, we get that max g,π GEM k (g, π) = max π max g GEM k (g, π) (34) Where the maximiser for π is π E = argmax π H k (p π ), the geometry-aware Shannon MSVE policy.
Extension to the continuous case. In this case we start by similarly decomposing the maximisation: From the proof of the discrete case, we know that g x = 1 p π k (x) is the pointwise maximiser for g(x) for every x inside the expectation. Thus, this is also the maximiser for the entire expectation, as maximising pointwise is the best that we can do. Therefore the result also holds for continuous distributions (the similarity profile p π k (x) is well-defined when the similarity k is smooth and nicely integrable).
A.5 Proof of Proposition 3.1.1 Proposition 3.1.1. Let π and g be approximated by some differentiable function approximators with sets of parameters θ and ξ respectively. Let r GEM , where x t is drawn independently from p π at every time step t. Then unbiased estimates of the gradient of GEM objective w.r.t. θ and ξ are, respectively, and Proof. We notice that the gradient term in Eq. 7 is an unbiased empirical estimate of the gradient of GEM w.r.t. the parameters of g. In the case of ∇ θ GEM k (g, π) given the fact that k is a symmetric function of x and x we have the following from the product rule From the policy gradient theorem [Sutton et al., 1999] we deduce where the outer expectation is with respect to the stochastic process induced by the policy π. The result then follows by replacing the expectations with their empirical estimates along the trajectory (x 1 , x 2 , . . . , x T ).
Proof. We restate the full GEM objective here: We know from Theorem 3.1 that where g = 1 p π k (x) . Then let's further maximise w.r.t. k: In order to maximise this expression, we want to minimise the sum inside the logarithm. However we cannot simply set k(x, x ) = 0, as we are constrained by requiring that k(x, x) = 1. Therefore we let k(x, x) = 1, and for all x = x , we can set k(x, x ) = 0. This is equivalent to setting k(x, x ) = 1(x = x ). Thus and plugging that in we get: and we recover the discrete Shannon entropy.

A.7 Generalization of GEM to Tsallis Entropy
Tsallis Entropy. Tsallis entropy is defined as [Tsallis, 1988]: for the real α. Taking the limit as α → 1, this simplifies to Shannon entropy. Tsallis entropy is sometimes called a pseudo-entropy since it satisfies all the properties of the standard entropy except additivity [Tsallis, 1988]. Here, we extend this definition to a geometry-aware version of Tsallis entropy (similar to geometry-aware Shannon entropy) by replacing p with its similarity profile p k : We now introduce the generalisation of the GEM objective function: where α < 2. For α = 1, we take the limit of (α − 1) → 0 and use the identity lim δ→0 x δ −1 δ = ln x to recover the Shannon case: Next, for α = 1, we follow the structure of the proof for the Shannon case. We first decompose the maximisation: Then we proceed to do a pointwise maximisation for g x = g(x): Note again that for p π (x) = 0, this becomes a constant and g x can take on any value. Thus we restrict ourselves to the case where p π (x) > 0. We find the critical point by solving for the zeros of the derivative: Thus the critical point is identical to the Shannon case. Next we examine the second derivative: We plug in the critical point and this second derivative simplifies to: So this critical point is a maximum as long as α < 2. Thus the maximiser g is exactly the same as for the Shannon case: Plugging this back into the full objective we get: Thus we are able to find the geometry-aware Tsallis MSVE policy with this generalised GEM.

B Experiment Details
B.1 1D bimodal Gaussian Learning for Section 3.2.1 Algorithm 2: soft1hot(x) Inputs: x, n bucket , m min , m max 1 Let y x−mmin mmax−mmin ; 2 Let b {0.5, 1.5, 2.5, . . . , n bucket − 0.5} ; 3 Return {e −n bucket |bi−y| | b i ∈ b} ; Algorithm 3: GEMLoss(B 1 , B 2 ) Inputs: In this part, we provide experimental details for GEM in Fig. 1 given in Section 3.2.1. The loss is computed in Algorithm 3 and optimised with the ADAM optimiser. Note that we use the softplus activation on top of g to make sure that it always returns something positive. We also add a small regularisation to the norm of the output of f (REG) to prevent divergence to infinity.
Next, we outline the data generating distribution. Let N, N ∼ TruncNorm(0, 1) be a random variable from the standard truncated normal normal distribution with mean 0, variance 1, truncated between {−2, 2}. Let U ∼ Uniform(0, 1) be a random variable from the uniform distribution in [0, 1]. Then the bimodal distribution used for generating data is X has been scaled and shifted so that its support is [0, 30]. The discretised version has 30 points equally spaced in [0,30], where the probability is computed by normalizing the density values at those 30 points. In order to take full advantage of neural networks, we use a soft-one-hot encoding (Algorithm 2) of the scalar input before passing it to the inner layers of the neural networks of f and g. Experiment hyperparameters are outlined in Table 1.

B.2 GEM Experiment Details
The plots in the experiments (Section 4) are computed by splitting the x-axis into 20 buckets of equal size, and computing the average of each bucket. This is done to smooth the data for each individual run. Then 5 runs are averaged together, and the standard error with 95% confidence interval is computed and shown as the shaded region.
The dynamics of the gridworlds in Fig. 2 have 5 standard actions of [no-op, up, down, left, right]. The initial state of the agent is picked uniformly at random from any of the blue square locations. The blue locations not chosen are normal free blocks. In each episode, a random green square location is chosen and a reward block (with reward 1.0) is placed there. The green locations not chosen are normal free blocks. The episode ends after the agent moves over the reward block and sees the reward. Adam(learning rate = 10 −3 , β 1 = 0, β 2 = 0.95) The episode length for 2-Rooms is 30, and 16-Leaves is 18. The state representation of these environments are pixel image arrays, i.e., 3D arrays of shape (width, height, 3), and are shown in Fig. 8; they consists of an upper world map, which shows a map of the rooms as well as which room the agent is in and which room the reward is in, and a lower room map, which shows the map of the current room. In the noisy version of 2-Rooms, there is a square with random red and green components (256 2 different colours) in-between the upper and lower maps. Each square is 8 × 8 pixels.
The visitation entropy (Fig. 7) is tracked by keeping an exponential moving average with a decay of 0.99 of the visitation count for each open square, and then computing the empirical Shannon entropy over these counts. The heatmaps (Fig. 7) are generated using the same counts, but are normalised by dividing all counts by the largest count so that the most visited square has value 1, corresponding to pure black.
The environments Cartpole Swingup and Mountain Car are standard, continuous-state, sparse reward domains with episode length 1000. We use the implementations of [Osband et al., 2020].
A training step is outlined in Algorithm 6. The AR loss is computed from Algorithm 4. We compute the GEM intrinsic reward from Algorithm 3, normalise it, and mix it with the extrinsic reward to use for policy gradient (Algorithm 5) to train π and V , which is a standard actor-critic algorithm. g and f are optimised directly with the computed loss.
For all experiments, we use a multi-process agent, where we have 64 processes running the agent policy and gathering data from the environment in parallel. The data is gathered and sent to another processes that computes the gradients and updates the parameters.
The basic network architecture used is shown in Table 2, along with training hyperparameters. For the continuous domains of Cartpole Swingup and Mountain Car, we use a slightly different architecture since their state is not an image (Table 3). The RNN cores for the value V and policy π networks take as input the concatenation of the torso output (torso is applied to the state), a 1-hot representation of the previous action, the previous extrinsic reward, and a soft 1-hot representation of the current timestep index. The embedding function f and the g function only take state as input, without concatenating other quantities. The batch size in Table 2 denotes the total batch size, i.e. it is the combination of B 1 and B 2 in Algorithm 6, each of which is half of the size. Each minibatch contains batch size number of traces, which are short segments of episodes. The trace period denotes which indices the traces start. For example, a trace length of 20 with a trace period of 10 means that the traces are timesteps (1, 2, . . . , 20), (10, 11, . . . , 30), (20, 21, . . . , 40), etc.. The traces are randomly chosen from within the episode so that the traces are not all in lockstep within a minibatch. The trace lengths and trace periods are shown in Table 4.

C.1 Irreversible Transitions
Because AR is symmetric, we take a closer look in this section as to what happens when we have asymmetric dynamics. We ran GEM on the simple gridworld illustrated in Fig. 9 (with image representation shown in Fig. 8).
The agent spawns at random in one of the blue cells, and the goal is in the green cell. To cross the bottleneck brown cell (the "door"), the agent must first visit at least one of the yellow cells (the "keys"). Visiting a yellow cell ("collecting the key") turns it into an ordinary cell, as does visiting the brown door cell after having a key ("opening the door"). Thus both picking up the key and opening the door are asymmetric, irreversible transitions. Fig. 10 shows learned embeddings for different states, projected onto the first two principal components. The different markers denote different configurations of the state (ignoring the agent position), and the colors correspond to different positions on the grid. For example, the blue circles correspond to the positions on the top room before having collected any keys. The purple positions correspond to the second room, and we can see that different configurations are embedded differently. In particular, the embedding groups the lower-room states into three (purple) groups: In the left group (+) the agent has only collected the lower key, in the center group ( ) the agent has collected both keys, and in the right group (|) the agent has only collected the upper key. The terminal state (where the green goal is absent) is also embedded separately for each of the three groups. The blue regions (lower room) are similarly grouped by the configuration of the keys and the door. Fig. 10 contains a more detailed description of the different configuration and position representations.
The main difference between the symmetric transitions and the asymmetric transitions is that asymmetric transitions results in embedding points that are slightly farther away from each other. This is because we only optimise AR for one direction as opposed to both directions with symmetric transitions, i.e., the strength of adjacency regularization is halved. Nevertheless, the embeddings learned is still meaningful and GEM is still able to explore and solve this task.


s2fieldsofstudy:
Computer Science
Economics
Education

text:
TeMoTopic: Temporal Mosaic Visualisation of Topic Distribution, Keywords, and Context

In this paper we present TeMoTopic, a visualization component for temporal exploration of topics in text corpora. TeMoTopic uses the temporal mosaic metaphor to present topics as a timeline of stacked bars along with related keywords for each topic. The visualization serves as an overview of the temporal distribution of topics, along with the keyword contents of the topics, which collectively support detail-on-demand interactions with the source text of the corpora. Through these interactions and the use of keyword highlighting, the content related to each topic and its change over time can be explored.

Introduction
Many text corpora, such as news articles, are temporal in nature, with the individual documents distributed across a span of time. As the size and availability of text corpora have continued to increase in recent years, effective analysis of the content of corpora has become challenging. Taking the temporal nature of most corpora into account when analysing the text makes it more difficult to describe the corpora and to interpret intuitively the results of analysis.
Topic modeling techniques, such as Latent Dirichlet Allocation (LDA) (Blei et al., 2003), have been used to automatically generate topic groups in text corpora. These topics can help in understanding the contents of a corpus by using keywords and topic association probabilities generated by the topic modelling technique. However, interpreting the results of the techniques is not always easy, and the results can seem counter-intuitive when looking only at the weighted keyword lists. Therefore, visualization techniques have been used extensively to help with the interpretation of the large number of topics generated by these models. The same is true of temporal topic modeling techniques, such as Dynamic Topic Modeling (Blei and Lafferty, 2006), which require additional visualization techniques to aid intuitive understanding of the temporal segmentation of the topics and their related keywords.
In this paper, we propose TeMoTopic as a contribution to the collection of visualization techniques for exploring the temporal distribution of topics in text corpora through the use of temporal mosaics. TeMoTopic adopts a space-filling approach to show topic distribution over time, and presents keywords related to each topic at the overview level of the visualization. The visualization is interactive and, in contrast to many other techniques, enables direct investigation of the source documents associated with individual topics and keywords. This allows the user to get a general sense of the meaning of a topic through its associated keywords, as well as providing the ability to dive into the details of the related documents.

Temporal Topic Visualization
Topic visualization systems are an active research area, with a variety of approaches for visualizing different aspects of topic model outputs, topic hierarchies, and topic evolution. In this paper, we only focus on related work in the area of temporal topic evolution and topic visualization of text corpora. While some methods address the temporal structuring of topics in short texts in the context of meetings and dialogues (Luz and Masoodian, 2005;Sheehan et al., 2019), in recent years, visualization of temporal topic evolution for larger text collections has been based on flow diagrams. An early example of such an approach is ThemeRiver (Havre et al., 2002), with later additions such as TextFlow (Cui et al., 2011), TopicFlow (Malik et al., 2013), ThemeDelta (Gad et al., 2015) and RoseRiver (Cui et al., 2014).
While TeMoTopic and flow-based temporal topic visualizations are similar, we expect they could form complementary components used in model assessment tools that are used to evaluate model quality. Flow diagrams are, for instance, useful for getting a high-level overview of many topics across long spans of text. TeMoTopic, on the other hand, aims to provide support for detailed viewing of a subset of topics and shorter timeslices, which are not possible in a flow diagram. As such, we envisage that other existing visualization tools which include a flow diagram component -such as LDA-Explore (Ganesan et al., 2015), VISTopic (Yang et al., 2017), ParallelTopics (Dou et al., 2011) and TIARA (Wei et al., 2010) -could be further expanded to include a temporal mosaic visualization, in the style of TeMoTopic. The largest benefit to this integration would come from enabling intuitive interactive filtering of the source documents based on the temporal topic and keyword distribution.

Topic Visualization Tasks
The design of a visualization tool should clearly be motivated by concrete tasks relevant to the endusers of the intended tool. Munzner's nested model for visualization design and validation (Munzner, 2009) describes steps that can be taken to mitigate threats to the validity of a visualization design. The first of the four levels of this design model is the characterization of domain specific tasks which should be supported by the visual encoding. Ganesan et al. (2015) identify key tasks, in the design description of LDAExplore, which should be supported by visualizations that aim to help users explore the results of Latent Dirichlet Allocation (LDA). Since LDA is one of the most commonly used topic modelling techniques for text corpora, these key tasks could be generalized to other techniques where a corpus is also split into topics, and keywords associated with those topics are extracted.
In addition, Ganesan et al. (2015) argue that the results of LDA can be counter-intuitive, and that the ability to explore and interact with the document set should make the topic and word distributions more intuitive and insightful. Table 1 shows the eight tasks identified by Ganesan et al. (2015), as well as one additional task which we consider to be important for visualizing temporal topics. The table also includes a brief description of the tasks which are fully described by Ganesan et al. (2015).
Theses tasks describe a need for topic overview with document detail available on-demand, this follows the well-known visual information seeking mantra proposed by Shneiderman (1996). Interactions around viewing, filtering, removing, and combining topics and documents should also be supported. Finally, we include an additional task for visualizing topic changes over time. This modifies the Visualize Topics task, such that the change in distribution and keywords across is available to explore.
3 TeMoTopic: Temporal Mosaic Topic visualization Figure 1 shows the TeMoTopic visualization tool. It consists of two juxtaposed views (Javed and Elmqvist, 2012): the temporal mosaic (left), and the document view (right). The design of the temporal mosaic is based on a visualization proposed by Luz and Masoodian (2007), and further expanded in our previous temporal mosaic visualizations TeMoCo visualization (Sheehan et al., 2019) and TeMoCo-Doc visualization (Sheehan et al., 2020), which have been used to link transcripts of meetings to document reports in a medical context.

Prototype
The temporal mosaic encoding was designed using Mackinlay's ranking (Mackinlay, 1986) of visual variables (Bertin, 1983), such that the visualization uses a perceptually efficient static encoding of the key data attributes. Horizontal position is used to emphasize the temporal order of the topics, and topic distribution per timeslice is encoded using vertical length. Each tile in the mosaic represents a single combination of topic and timeslice. The height of each tile represents its topic weight in that timeslice.
The top ten keywords which describe the associated temporal topic are placed within the tile, and can be scaled to encode the keyword topic probability, using area in a manner similar to keyword scaling in text visualizations such as word clouds (Viegas et al., 2009). Although the keywords are currently presented in order of descending topic probability, in future work alternative keyword presentation styles such as alphabetized lists and word clouds will be compared in terms of their effectiveness for comparison between the tiles. The categorical topics are encoded using color, allowing topics weights and keyword changes to be examined across the span of timeslices.
The mosaic visualization provides an overview of the topic distribution and associated keywords over time. However, as the number of topics and timeslices increase, if the visualization area is kept at a fixed size, the overview would become more abstract, cluttered, and difficult to examine for individual tiles and keywords. To maintain readability, the visualization can extend both horizontally and vertically to accommodate more topics and timeslices. The user can pan and zoom to get the detailed views of topics and keywords, or a higherlevel view of the entire temporal topic space. The removal interaction is particularly useful when the number of topics is large, since filtering out topics that are not relevant to the current analysis allows for more of the detail to be presented on a single screen.
The temporal mosaic, as currently described, addresses two of the tasks from Table 1, namely Visualize Topics and Visualize Topic Change. To facilitate Overview of Document -Topic Relations, the document view (Figure 1, right) was created and linked, via click interactions, to the temporal mosaic (Figure 1, left). The document view is used to display the documents associated with a temporal topic tile. When a coloured tile is selected in the temporal mosaic, the related articles are presented in a scroll box and, the keywords from the topic tile are highlighted in the text. If keyword weights (or probabilities) are provided, the highlighted words are scaled accordingly. This dual combination of views and described interactions, support the user in investigating the meaning of a topic, and by investigating the differences between the topic timeslices, temporal document similarities and differences can be revealed.
Although it is useful to view the entirety of a topic, Filtering Documents is a task that was also identified as important to facilitate. One simple and intuitive way to do this with the temporal mosaic is by clicking on individual keywords rather than on the entire topic tile. This will cause the document view to display only documents from the related topic timeslice which contain the selected keywords, as shown in Figure 2. Selection from multiple topics is also possible, and the keywords are highlighted in the related topic colour to differentiate between topics.
The final interaction supported by this version of TeMoTopic is the removal of topics from the temporal mosaic. To do this, a topic can be selected from the legend shown above the temporal mosaic (Figure 3, top). Alternatively right-clicking on a topic removes all the other topics except the selected one. In the example shown in Figure 3, the blue topic has been removed from the temporal mosaic. When topics are removed, the temporal mosaic no longer fills the entire vertical space of the visualization. This interaction is useful when dealing with a large number of topics of which only a few are of interest for the analysis.

Implementation
The visualization tool 1 is implemented as a singlepage web application using the D3.js framework (Bostock et al., 2011) . It takes two JavaScript Object Notation (JSON) files as input: the first file contains topic, keyword, timeslice, weights, and associated filenames, and the second input file is simply a JSON structure containing the documents with filename used as the retrieval key. Sample Python scripts are provided for generating topics and keywords on the sample dataset and for preparing the visualization input files from the model output.
The current version of TeMoTopic was designed to be model agnostic, and can even be used for tasks unrelated to topic model exploration. For example, metadata attributes such as the source of the news articles or their author could be used in place of topics. Keywords could be extracted using any available technique, including simple frequency lists. The visualization could also be used for corpus comparison and even cross-lingual analysis using entire corpora as replacements for the topics.
However, in our implementation we make use of dynamic topic modelling (Blei and Lafferty, 2006) to identify temporal topics and keywords in a subset of the de-news 2 corpus of German-English parallel news. The dataset consists of transcribed German radio broadcasts which were manually translated into English. Between 1996 and 2000 volunteers selected and transcribed five to ten of these news broadcasts per day and added them to the dataset.
In the examples of TeMoTopic, shown in Figures  2, 1 and 3, we selected a ten month span of the dataset and presented the four largest topics. The choice of time span and topic number was only for presentation and to exemplify the interface features. We did not attempt to choose a time period or number of topics based on prior knowledge of the news relevant at the time in Germany. We present our examples to describe the interface and interactions, rather than as an analysis of the dataset, and we choose to draw no conclusions about the dataset contents and topics.

Conclusions
While many other temporal visualization techniques, such as ThemeRiver (Havre et al., 2002), offer some of the functionality for temporal visualization of topics or visualization of content changes, they do not feature implicit linking between the visualization and the underlying content documents. We consider this to be the main contribution of TeMoTopic visualization and its distinguishing feature with regards to the state of the art. As such, determining the necessity and validity of this approach in the identified domain is an important step before further development of the visualization prototype. Future work will, therefore, include evaluating the usability of a future iteration of the system with domain experts in both news analysis and topic modelling.


An Approach to Detecting the Spread of False Information on the Internet Using Data Science Algorithms

Today we are all witnessing the rapid immersion of society into the digital world. The amount of information is huge, and it is often difficult to distinguish normal news and comments from unreliable information. In this regard, the issue of detecting fake news and countering its spread becomes urgent. This task is not trivial for the following reasons: firstly, the volume of content that is created every day on the Internet is enormous; secondly, the detection system requires news plots that are obviously true; thirdly, the system must be able to analyze information in close to real time. The article presents a new approach to detecting the spread of false information on the Internet based on the use of data science algorithms. The concept of a fake news detection system includes 4 components and a data storage system. The article presents an experimental evaluation of methods implemented in the framework of the neural network training component and the detection of false information.

Introduction
Today, we are all witnessing the rapid immersion of society into the digital world. Schools and universities switch to distance learning programs in case of urgent need. Organizations are implementing remote interaction services with customers and employees. The state and community are moving to online communication instead of offline meetings. At the same time, the number of papers devoted to detecting fake news is growing. For instance, on the Google Academy website [1], upon request "fake news detection" for 2016 we can see 4120 articles, for 2017 there are 5280 ones, for 2018 -7250, and in 2020, 2379 papers have already been published only in 3 months (Fig. 1). Apparently, in 2020 we will see much more research than ever before devoted to the detection of fake news. It is worth paying attention to the fact that some of them, already in the 1st quarter of 2020, are devoted to the problem of misinformation about the situation with COVID-19.
As an example, in [2] the authors raise a complex discussion about the fact that waves of panic and fears generated by fake news and misinformation on the Internet related to the spread of the virus lead to a deterioration of the physical and mental state of society.
In addition, in [3] the authors publish the results of a large-scale experiment. It shows that people do not think about the truth of the message and even spread it further on their social media pages. However, the authors propose the simple solution in [3], "notification that information is not verified" reduces the level of trust.
The issue of detecting and countering the dissemination of false information on the Internet requires a solution, especially given the appearance of various fakes during the COVID-19 coronavirus pandemic. It is necessary to develop and implement models and algorithms aimed at revealing false information on the Internet.
This article is a prolongation of the previous research [4,5]. The authors propose an approach to detecting the spread of false information on the Internet using data science algorithms, which is described in more detail in Sects. 3 and 4. Initially, the writers raised the question: "Can data science algorithms successfully detect fake news on news aggregators, provided that the official position is published on official channels and then distributed to other sources?". The review of existing works and solutions (Sect. 2) was conducted with the experiments simultaneously; several datasets and models were considered. Therefore, in the beginning, experiments were realized with a dataset from an open repository [6]. An element of this dataset consisted of 2 news headlines and a fractional number from 0 to 5, which shows the semantic similarity of news headlines, the larger the number, the closer the texts are to each other. Convolutional neural networks were used to solve this problem, but the result was unsuccessful. The model was trained unstably and, in most cases, predicted a value of 2.5 regardless of the input data; the model's prediction accuracy did not exceed 30%. It is assumed that the reasons for this behavior are most likely due to the insufficient size of the source dataset for training the neural network.
Further analysis of other papers was carried out and the BERT model was taken as a basis; this model demonstrates a high level of detection accuracy, as shown in Sect. 4.
The approach proposed by the authors to detect fake news differs from existing ones in its taking into account official sources and information from them and comparing the news according to their short text parts broadcasted by news aggregators. This technique makes it possible to detect false information on time and counteract its dissemination.

Relevant Work Overview
Semantic analysis is a method aimed at building a semantic structure of a sentence consisting of semantic nodes and semantic relations. The purpose of the analysis is to construct these nodes, which are formed from the words of the original sentence. The basis for formulating hypotheses about the composition of semantic nodes is the information obtained as a result of syntactic analysis. The results of the analysis are presented as a semantic graph, the construction of which consists of a number of stages (initialization of semantic nodes and syntactic variants of fragments, construction of a set of dictionary interpretations of nodes, construction of time groups, construction of nodes in quotation marks, and so on).
Semantic analysis can be performed using various techniques, such as PROTAN and a wide range of other techniques. For example, semantic analysis is implemented in T-LAB Tools for Text Analysis, which is a computer technique that allows to perform three types of analysis: thematic analysis, comparative analysis, and adjacency analysis, as well as identify semantic patterns of words and the main ideas of the text. The process of working with text in this methodology includes text segmentation, keyword selection, and procedures designed to perform three types of analysis.
The paper [7] describes different types of fake news, which are clickbit, propaganda, opinion, humor, also news parody, forgery and photo manipulation. In addition to this approach, authors have intention to present several algorithms, which propose ways to spot fake news. They are quite simple, but effective: • Evaluating sources of the news and other stories, checking the credibility of the source • Consulting experts before sharing the information gathered in the Internet.
In [8] programs which were developed to perform repetitive tasks that gathered data (they were called bots) are described. In addition, in the information collected by bots researchers could see what sites people have been visiting, what they bought and how often purchases were made. Generally, it can be noticed that once bots were efficiently created the expansion of possibilities to collect and use gathered data happened. It is mentioned in [9] that people themselves are assisting in the spread of false information even though more than 50% of them might not see it. This is because of the feature of computer code, which, in some circumstances, could allow fake news to circulate and interfere people's beliefs.
The article [10] includes an approach and an academic review on spreading false information in social media, more precisely, in Facebook. Authors pay attention on the process of circulating of fake news. Studies describe the model that contains individuals who can be in one of the following states: ignorant, true-information spreader, fake-information spreader, and stifler. The research of [11] is directed to improve the accuracy of the existing techniques of detecting the spreading of false information.
Furthermore, [12] touches upon some machine learning techniques which can help to classify text documents. Fig. 2 shows the graphical representation of the text classification process. The paper [12] describes different approaches of text classification based on machine learning techniques. They are: • Naive Bayes • Support vector machines (SVM) • A fast decision tree construction algorithm [14], that was proposed by D. E. Johnson • A method which improves performance of kNN • TextCC.
Naive Bayes is often used in text classification because this method is very simple and effective [15]. However, the algorithm has disadvantages, it models text badly. The authors of [16] tried to solve this problem in their paper. They are suggesting that treelike Bayesian networks could handle a text classification task in one hundred thousand variables with sufficient speed and accuracy. Support vector machines (SVM) technique has its own advantages, but strong limitations. When the SVM method is applied to text classification, it provides excellent fidelity, but the recall is very weak. In order to improve the values of recall, the authors of [17] decided to describe an automatic process for adjusting the thresholds of generic SVM with better results.
Moreover, in [18] a method which improves performance of kNN by using well estimated parameters is presented. The main aim is to find out sufficient parameters.
Heui Lim resorted to propose and evaluate diversified the kNN approach with various decision functions, k values and feature sets to solve this issue.
TextCC is a training algorithm, which is submitted in [19]. In order to classify documents instantly the corner classification (CC) network is used. It is a kind of feed forward neural network.
Given the fact that the first experiment was unsuccessful, it was decided that the strategy of resolving the problem must change. The authors considered in [20] to take the BERT model as a basis for further explorations. BERT (Bidirectional Encoder Representations from Transformers) uses a "masked language model" (MLM) pre-training objective. That helps to mitigate the unidirectionality constraint, which is caused by two approaches ("feature-based" and "fine-tuning") sharing the same objective function during pre-training, where they use unidirectional language models to learn general language representations.
In [21] the authors claim that BERT is the first representation model based on finetuning, which provides the most contemporary efficiency for a large set of sentence-level and token-level tasks, surpassing many architectures, focused on specific objectives.
BERT has been already used in many researches. For example, in [22] the authors performed systematic comparisons of different BERT+NMT architectures for standard supervised NMT. They also claim that the benefits of using pre-trained representations has been overlooked in previous studies and should be assessed beyond BLEU scores on in-domain datasets. Additionally, they compare different ways to train and reuse BERT for NMT.
As a result of the accomplished work [23] it was showed that BERT can be trained only with a masked LM task on the NMT source corpora and yield significant improvement over the baseline.
To summarize the information mentioned above it must be noticed that on the Internet nowadays there are many studies dedicated to confrontation to fake news, the popularity of this field is proceeding to increase. Nevertheless, the problem is that there are no such ready-made practical models and algorithms. It is required to develop the approach for detecting the spread of fake news in real time mode.

Proposed Approach
Direct text comparison is extremely resource-intensive and algorithmically complex. It eliminates the ability to quickly search for similar text. It is required to present a mechanism that allows to find similar text based on indexed fields in the database without lengthy and complex calculations.
The proposed model is supposed to contain methods of deep learning such as using the convolutional neural networks for text comparison. This is an approach to improve information security in the Internet. The main notion is to build a model that will determine matching one text to another, hereby the decision will be made: if news correspond to the more reliable source. The authors generate requirements for the matching and present them. If the inspected information does not meet the requirements, it can be defined as the false information.
A convolutional neural network is a special type of direct distribution neural network (Fig. 3). Direct propagation is understood as the propagation of signals through neurons from the first layer to the last. Authors observe in [24] that there can be quite many hidden layers in the network, depending on the amount of data and the complexity of the task. The main feature of such networks is the presence of alternating layers of a type of "convolution layer -max pooling" and there can be a set of these layers. The convolution operation implies that each input fragment is incrementally multiplied by a small matrix of weights (the core) and the result is summarized. This amount is the output element, which is called the feature map. The paper [25] is showing that the weighted sum of inputs is passed through the activation function. Max pooling (the layer of subsampling) is a nonlinear compaction of the feature map with the passing a nonlinear transformation. The publication [26] deals with the fact that the pooling is interpreted as splitting the feature map into smaller matrices, the process of finding their maximum elements, so there is an increase in the "depth" of values.
The main concept proposed by the authors in this study lays in combining the data science and mechanisms information security by detecting the dissemination of false information on the Internet. A flowchart of the fake news detection system is offered in the Fig. 4. Comparing news plots from official sources with others will make it possible to detect false information and make further decisions about how to counteract its dissemination. It is suggested that the solution proposed in [24,25,26] could be used within the flowchart

Experiment
A news dataset on English language was used as a basis for the experiment [27]. It has the following structure: • News headline • The main text of the news • The area that the news belongs to. The bigger part of the dataset consists of political news • The date that coincides the publication of the news. In the beginning, the dataset contained two files: true news and fake ones. In the data-preprocessing phase, they were combined into one structure to make the quantities of true news and fake news equal. With this dataset, which is evenly distributed across the classes, there is a possibility to use accuracy as a metric to evaluate the quality of the model. Moreover, another one column was added to the structure of the dataset. It maintained information about which class the news belonged to (fake news or true ones). The total size of the dataset constituted 34 267 cases. At first, the dataset was divided to 2 components: training one and testing samples in the ratio of 75% and 25% in accordance. BERT was chosen as the initial neural network model, which is a wellconfigured pre-trained neural network provided by Google. With this technique, the model does not need a large dataset to identify patterns; it is enough just to configure it to solve the current problem. By default, BERT returns a vector with a fixed dimension of 768 values for any size of input data, which contains complete information about the input data. In the present case, 3 linear fully connected layers with dimensions 256, 64, and 2 were added after BERT, respectively.
When the model was training, the PyTorch library [28] was used, which had already contained the BERT model and had provided convenient functionality for working with it. Before a text can be submitted to the model, it must be tokenized; it can be done by using the built-in BertTokenizer module. A diagram of the text preprocessing and model training is shown in Fig. 5. During this experiment only the text of the news itself is used to classify the news. This field has different lengths, so for convenience, before tokenization each such text is separated into several fragments, the size of every one is 300 tokens. Then, in a period of the training, each of these fragments is successively transmitted to the input of the neural network. Learning is controlled by gradient stochastic descent, and the average square error is used as the loss function. Furthermore, it is recommended to use the capabilities of the video card for BERT training whenever it is possible, since this model is a deep neural network, which can take a considerable time to train. Based on the results of evaluating the model on a test sample, the accuracy of the prediction was 95%. Whereas the dataset under study has a uniform distribution across the classes, the precision and recall values were also 95%. Figure 6 demonstrates a reduction in the level of losses during model training. It shows the absolute value of the loss function on the ordinate axis, and the iteration sequence number on the abscess axis.
For all experiments, a laptop with the following characteristics QuadCore Intel Core i7-8565U, 4500 MHz (45 x 100); 16 GB DDR4-2666 DDR4 SDRAM was used. A powerful video card is required to speed up the model. On the current hardware, the duration of training the model and analyzing the test dataset took about 13 h.

Conclusion and Discussion
The article presents a new approach to detecting the spread of false information on the Internet using data science algorithms.
The developed concept of the detection system, proposed by the authors in this study, is to combine data science and information security mechanisms by detecting the spread of false information on the Internet. The discovery system concept includes 4 components and a data storage system.
Evaluation of methods implemented in the framework of "the component of adaptation and retraining of the system" and "the component of detecting", performed during the experimental study, demonstrated the effectiveness of using the BERT model by means of the PyTorch library in this task.
Some areas of further research are the development, integration, validation and evaluation of all components of the developed concept. Testing the model on a much larger dataset and in a computing environment with a large number of computing resources.
It is assumed that the proposed approach can be integrated into not only systems for monitoring and countering the spread of false information, but also be part of antivirus systems, browsers, or parental control systems.
There is still a discussion about the possibility of components working in near-realtime mode, due to the huge amount of data. For example, an important part of the problem of spreading fake news is its appearance in social networks. However, the dynamics of the appearance of new posts and messages in these networks develops in such ways that the components of monitoring, training the neural network to recognize a new plot and detecting fake news can't be triggered in a timely manner. The authors will demonstrate the results of testing the increased load on this model in future studies.