Since its invention in 2014, the Adam optimizer <cit.> has received tremendous attention. On one hand, it has been widely used in deep learning and many variants have been proposed, while on the other hand their theoretical convergence property remains to be a mystery. It is far from satisfactory in the sense that some studies require strong assumptions about the updates, which are not necessarily applicable in practice, while other studies still follow the original problematic convergence analysis of Adam, which was shown to be not sufficient to ensure convergence.  Although rigorous convergence analysis exists for Adam, they impose specific requirements on the update of the adaptive step size, which are not generic enough to cover many other variants of Adam.  To address theses issues,  in this extended abstract, we present a simple and generic proof of convergence for a family of Adam-style  methods (including Adam, AMSGrad, Adabound, etc.). Our analysis only requires an increasing or large "momentum" parameter for the first-order moment, which is indeed the case used in practice,  and a boundness condition on the adaptive  factor of the step size, which applies to all variants of Adam under mild conditions of stochastic gradients.  We also establish a variance diminishing result for the used stochastic gradient estimators. Indeed, our analysis of Adam is so simple and generic that it can be leveraged to establish the convergence for solving a broader family of non-convex optimization problems, including min-max, compositional, and bilevel optimization problems. For the full (earlier) version of this extended abstract, please refer to <cit.>.

§ INTRODUCTION

Stochastic adaptive methods originating from AdaGrad for convex minimization <cit.> have attracted tremendous attention for stochastic non-convex optimization <cit.>. Adam <cit.> is an important variant of AdaGrad, which is widely used in practice for training deep neural networks, and many variants of Adam were proposed for improving its performance, e.g. <cit.>.
Its analysis for non-convex optimization has also received a lot of attention <cit.>.
For more generality, we consider a family of Adam-style algorithms. The update is given by

\begin{equation}\label{eqn:adam}
\hspace*{-0.3in}\text{Adam-style:}\quad\left\{\begin{aligned}
&\v_{t+1} = (1-\beta_t)\v_t + \beta_t \O_F(\x_t),\\
&\u_{t+1} = h_t (\O_F(\x_0), \ldots, \O_F(\x_t)), \\
&\x_{t+1}  = \x_t - \eta_t \frac{\v_{t+1}}{\sqrt{\u_{t+1}} + G_0}, t=0, \ldots, T.
\end{aligned}\right.
\end{equation}

where $h_t$ denotes an appropriate mapping function whose specific choices are given later.

One criticism of Adam is that it might not converge for some problems with inappropriate  momentum parameters. In particular, the authors of AMSGrad <cit.> show that Adam with small momentum parameters can diverge for some problems. However, we notice that the failure of Adam shown in AMSGrad <cit.> and the practical success of Adam come from an inconsistent setting of the momentum parameter for the first-order moment. In practice, this momentum parameter (corresponding to $1-\beta_t$ in (<ref>)) is usually set to a large value (e.g., 0.9).  However, in the failure case analysis of Adam <cit.> and many existing analysis of Adam and their variants <cit.>, such momentum parameter is set as a small value or a decreasing sequence. We provide the first  analysis of Adam and other variants with a more natural increasing or large momentum parameter for the first-order moment.

Several recent works have tried to prove the (non)-convergence of Adam. In particular, Zou et al. <cit.> establish some sufficient condition for ensuring Adam to converge. In particular, they choose to increase the momentum parameter for the second-order moment and establish a convergence rate in the order of $\log(T)/\sqrt{T}$, which was similarly established in <cit.> with some improvement on the constant factor. Zaheer et al. <cit.> show that Adam with a sufficiently large mini-batch size can converge to an accuracy level proportional to the inverse of the mini-batch size. Chen et al. <cit.> analyze the convergence properties for a family of Adam-style algorithms. However, their analysis requires a strong assumption of the updates to ensure the convergence, which does not necessarily hold as the authors give non-convergence examples.  Different from these works, we give an alternative way to ensure Adam converge by  using an increasing or large momentum parameter for the first-order moment without any restrictions on the momentum parameter for the second-order moment and without requiring a large mini-batch size. This seems more natural and consistent with the practice.  Indeed, our analysis is applicable to a family of Adam-style algorithms, and is agnostic to the method for updating the normalization factor in the adaptive step size as long as it can be upper bounded.  The large momentum parameter for the first-order moment is also the key part that differentiates our convergence analysis with existing non-convergence analysis of Adam <cit.>, which require  the  momentum parameter for the first-order moment to be decreasing  to zero or sufficiently small.

A key in the analysis is to carefully utilize the design of the stochastic estimator of the gradient. Traditional methods that simply use an unbiased gradient estimator of the objective function are not applicable to many problems and also suffer slow convergence due to large variance of the unbiased stochastic gradients.  Recent studies in stochastic non-convex optimization have proposed better stochastic estimators of the gradient based on variance reduction technique (e.g., SPIDER, SARAH, STORM) <cit.>. However, these estimators sacrifice generality as they require that the unbiased stochastic oracle is Lipschitz continuous with respect to the input, which prohibits many useful tricks in machine learning for improving generalization and efficiency (e.g., adding random noise to the stochastic gradient <cit.>,  gradient compression <cit.>). In addition, they also require computing stochastic gradients at two points per-iteration, making them further restrictive.

In Adam-style methods, the stochastic estimators are based on the moving average.

In order to generate a sequence of iterates $\{\x_0, \x_1, \ldots, \x_T \}$, we usually need to  track another sequence of $\{g(\x_0), g(\x_1), \ldots, g(\x_T)\}$, where $g$ is a Lipschitz continuous mapping that is useful for constructing the gradient of the objective function. However, $g(\x_t)$ can be only accessed through an unbiased stochastic oracle denoted by $\O_g$ such that for any input $\x$, it returns a random variable $\O_g(\x)$ satisfying $\E[\O_g(\x)] = g(\x)$.  For more generality, we do not assume that $\O_g$ is Lipschitz continuous with respect to the input even $g$ is Lipschitz continuous. One example of such stochastic oracle is $O_g(\x) = g(\x; \zeta) + \xi$, where $\E_{\zeta}[g(\x; \zeta)]= g(\x)$ and  $\xi$ is a zero-mean random noise (e.g., zero-mean Gaussian noise). Therefore, the variance-reduced stochastic estimators based on SPIDER, SARAH or STORM are not applicable. Instead, we will consider another  stochastic estimator based on moving average, i.e., we maintain and update a sequence of $\{\z_1, \ldots, \z_T\}$ by

\begin{align}\label{eqn:SEMA}
\z_{t+1}  = (1-\beta_t)\z_t + \beta_t \O_g(\x_t), \quad t=0, \ldots, T.
\end{align}

We refer to this estimator sequence for tracking $\{g(\x_1), \ldots, g(\x_T)\}$ as stochastic moving average estimator (SEMA) in contrast to SPIDER/SARAH/STORM. It the literature, stochastic methods that employ the above estimator are usually referred to as momentum methods <cit.>, with $1-\beta_t$ called the "momentum" parameter.

Besides in Adam-style methods, SEMA has been widely used in other stochastic non-convex optimization methods such as in stochastic compositional minimization <cit.>. Although the SEMA has been widely used in practice, its power for solving a broad range of stochastic optimization problems has not been fully discovered.   We present a simple and intuitive proof of convergence of  a family of Adam-style algorithms with an increasing or large momentum parameter for the first-order moment, which include many variants such as Adam, AMSGrad, Adabound, AdaFom, etc. A surprising result is that Adam with an increasing or large momentum parameter for the first-order moment indeed converges at the same rate as SGD without any modifications  on the update  or restrictions on the "momentum" parameter for the second-order moment. In our analysis, $\beta_t$ is decreasing in the same order of step size, which yields an increasing "momentum" parameter $1-\beta_t$. This increasing momentum parameter is more natural than the decreasing (or small) momentum parameter, which is indeed the reason that makes Adam diverge on some examples <cit.>. Our increasing/large "momentum" parameter $1-\beta_t$ is also consistent with that the large value close to 1 used in practice <cit.>. To the best of our knowledge, this is the first time that Adam was shown to converge for non-convex optimization with a more natural large "momentum" parameter for the first-order moment.
We also prove that averaged variance of the stochastic estimator of the gradient decreases over time. A comparison of the results in this paper with existing results is summarized in Table <ref>. Moreover, our analysis can be extended to analyze the convergence of Adam-style algorithms for a broader family of non-convex optimization problems, including compositional optimization, min-max optimization and bilevel optimization problems <cit.>.

Comparison with previous results. "mom. para." is short for momentum parameter. 1st and 2nd are short for first order and second order, respectively. "-" denotes no strict requirements and applicable to a range of updates. $\uparrow$ represents increasing as iterations and $\downarrow$ represents decreasing as iterations. $\epsilon$ denotes the target accuracy level for the objective gradient norm, i.e., $\E[\|\nabla F (\x)\|]\leq \epsilon$.

Problem    Method	   batch size   $\uparrow$ or $\downarrow$
1st mom. para.   $\uparrow$ or $\downarrow$
2nd mom. para.   Converge?

This work   $O(1)$   $\uparrow$   -   Yes

<cit.>   $O(1)$   $\downarrow$   constant   No

Non-convex		   <cit.>   $O(1)$   Non-$\uparrow$   -   No

(Adam-family)	   <cit.>   $O(1/\epsilon^2)$   constant   $\uparrow$   Yes

<cit.>   $O(1)$   constant   $\uparrow$   Yes

<cit.>   $O(1)$   constant   $\uparrow$   Yes

§ NOTATIONS AND PRELIMINARIES

Notations and Definitions. Let $\|\cdot\|$ denote the Euclidean norm of a vector or the spectral norm of a matrix.   Let $\|\cdot\|_F$ denote the Frobenius norm of a  matrix. A mapping $h$ is $L$-Lipschitz continuous iff $\|h(\x) - h(\x')\|\leq L\|\x - \x'\|$ for any $\x, \x' \in \R^d$.  A function $F$ is called $L$-smooth if its gradient $\nabla F(\cdot)$ is $L$-Lipschitz continuous. A function $g$ is $\lambda$-strongly convex iff $g(\x)\geq g(\x') + \nabla g(\x')^{\top}(\x  - \x') + \frac{\lambda}{2}\| \x - \x'\|^2$ for any $\x, \x'$.   A function $g(\y)$ is called $\lambda$-strongly concave if $-g(\y)$ is $\lambda$-strongly convex.  For a differentiable function $f(\x, \y)$, we let $\nabla_x f(\x, \y)$ and $\nabla_y f(\x, \y)$ denote the partial gradients with respect to $\x$ and $\y$, respectively. Denote by $\nabla f(\x, \y) = (\nabla_x f(\x, \y)^{\top}, \nabla_y f(\x, \y)^{\top})^{\top}$.

Let $\circ$ denote an element-wise product. We denote by $\x^2$, $\sqrt{\x}$  an element-wise square and element-wise square-root, respectively.

We will consider non-convex minimization (<ref>), which has broad applications in machine learning. This paper focuses on theoretical analysis and our goal for these problems is to find an $\epsilon$-stationary solution of the primal objective function $F(\x)$ by using stochastic oracles.

Consider a differentiable function $F(\x)$,  a randomized solution $\x$ is called an $\epsilon$-stationary point if it satisfies $\|\nabla F(\x)\| \leq \epsilon$.

Before ending this section, we present the widely used stochastic momentum method for solving non-convex minimization problem $\min_{\x\in\R^d} F(\x)$ through an unbiased stochastic oracle that returns a random variable $\O_F(\x)$ for any $\x$ such that $\E[\O_F(\x)] = \nabla F(\x)$. For solving this problem, the stochastic momentum method (in particular stochastic heavy-ball (SHB) method) that employs the SEMA update is given by

\begin{equation}\label{eqn:sma}
\hspace*{-0.3in}\quad\left\{ \begin{aligned}
&\v_{t+1} = (1-\beta)\v_t + \beta\O_F(\x_t)\\
&\x_{t+1} = \x_t - \eta \v_{t+1}, \quad t= 0, \ldots, T.
\end{aligned}\right.
\end{equation}

where $\v_0 = \O_F(\x_0)$. In the literature,  $1 - \beta$ is known as the momentum parameter and $\eta$ is known as the step size or learning rate. It is notable that the stochastic momentum method can be also written as $\z_{t+1} = \beta\z_t - \eta\O_F(\x_t)$, and $\x_{t+1} = \x_t + \z_t$ <cit.>, which is equivalent to the above update with some parameter change shown in Appendix <ref>. The above method has been analyzed in various studies <cit.>. Nevertheless, we will give a unified analysis for the Adam-family methods with a much more concise proof, which covers SHB as a special case. A core to the analysis is the use of a known variance recursion property of the SEMA estimator stated below.
(Variance Recursion of SEMA)[Lemma 2, <cit.>]
Consider a moving average sequence $\z_{t+1} = (1-\beta_t)\z_t + \beta_t \O_h(\x_t)$ for tracking $h(\x_t)$, where $\E_t[\O_h(\x_t)] = h(\x_t)$ and $h$ is a $L$-Lipschitz continuous mapping. Then we  have

\begin{align*}
\E_t[\|\z_{t+1} - h(\x_t)\|^2]\leq (1-\beta_t)\|\z_t - h(\x_{t-1})\|^2+ 2\beta_t^2\E_t[\|\O_h(\x_t) - h(\x_t)\|^2]  + \frac{L^2\|\x_{t} - \x_{t-1}\|^2}{\beta_t}.
\end{align*}

where $\E_t$ denotes the expectation conditioned on all randomness before $\O_h(\x_t)$.

We refer to the above property as variance recursion (VR) of the SEMA.

§ A NOVEL ANALYSIS OF ADAM WITH A LARGE  MOMENTUM PARAMETER

In this section, we consider the standard stochastic non-convex minimization, i.e.,

\begin{align}\label{eqn:snc}
\min_{\x\in\R^d} F(\x),
\end{align}

where $F$ is smooth and is accessible only through an unbiased stochastic oracle. These conditions are summarized below for our presentation.
Regarding problem (<ref>), the following conditions hold:

* $\nabla F$ is $L_F$ Lipschitz continuous;

* $F$  is accessible only through an unbiased stochastic oracle that returns a random variable $\O_F(\x)$ for any $\x$ such that $\E[\O_F(\x)] = \nabla F(\x)$, and $\O_F$ has a variance bounded by $\E[\|\O_F(\x)- \nabla F(\x)\|^2]\leq \sigma^2(1 + c\|\nabla F(\x)\|^2)$ for some $c>0$.

Remark: Note that the variance bounded condition is slightly weaker than the standard condition $\E[\|\O_F(\x)- \nabla F(\x)\|^2]\leq \sigma^2$. An example of a random oracle that satisfies our condition but not the standard condition is $\O_F(\x) = d\cdot\nabla F(\x)\circ\e_i$, where $i\in\{1,\ldots, d\}$ is randomly sampled and  $\e_i$ denotes the $i$-th canonical vector with only $i$-th element equal to one and others zero.  For this oracle, we can show that $\E[\O_F(\x)] = \nabla F(\x)$ and $\E[\|\O_F(\x) - \nabla F(\x)\|^2]\leq (d-1)\|\nabla F(\x)\|^2$.

In the following we present a novel analysis of Adam-style methods based on VR of SEMA. The update rule of Adam-style rules has been given in (<ref>).

A key to our convergence analysis of Adam-style algorithms is the boundness of the  step size scaling factor $\s_t = 1/(\sqrt{\u_{t+1}} + G_0)$, which is presented as an assumption below for more generality. We denote by $\teta_t = \eta_t \s_t$.

For the Adam-style algorithms in (<ref>), we assume that $\s_t =  1/(\sqrt{\u_{t+1}} + G_0)$ is upper bounded and lower bounded, i.e., there exists $0<c_l<c_u$ such that $c_l\leq \|\s_t\|_\infty\leq c_u$.

Remark: Under the standard assumption $\|\O_F(\x)\|_\infty\leq G$ <cit.>, we can see many variants of Adam will satisfy the above condition.  Examples include Adam <cit.>, AMSGrad <cit.>, AdaFom <cit.>, Adam$^+$ <cit.>,  whose $\u_t$ shown in Table <ref> all satisfy the above condition under the bounded stochastic oracle assumption.
Even if the condition $\|\O_F(\x)\|_\infty\leq G$ is not satisfied, we can also use the clipping idea to make $\u_t$ bounded. This is used in Adabound <cit.>, whose $\u_t$ is given by

\begin{align*}
&\text{Adabound: } \u'_{t+1} = (1-\beta_t')\u'_t + \beta_t' \O_F^2(\x_t), \quad \u_{t} = \Pi_{[1/c_u^2, 1/c_l^2]}[\u_{t+1}],\quad G_0 =0,
\end{align*}

where $c_l\leq c_u$ and $\Pi_{[a, b]}$ is a projection operator that projects the input into the range $[a, b]$. We summarize these updates and their satisfactions  of Assumption <ref> in Table <ref>. Note that SHB also satisfies Assumption <ref> automatically.

Different Adam-style methods and their satisfactions of Assumption <ref>

method   update for $h_t$   Additional assumption   $c_l$ and $c_u$

SHB    $\u_{t+1} = 1,G=0$     -     $c_l =1, c_u =1$

Adam    $\u_{t+1} = (1-\beta_t')\u_t + \beta_t' \O_F^2(\x_t)$   $\|\O_F\|\infty\leq G$   $c_l \geq \frac{1}{G+G_0}, c_u \leq \frac{1}{G_0}$

AMSGrad    $\u'_{t+1} = (1-\beta_t')\u'_t + \beta_t' \O_F^2(\x_t)$
$\u_{t+1} = \max(\u_t, \u'_{t+1})$   $\|\O_F\|\infty\leq G$   $c_l \geq \frac{1}{G+G_0}, c_u \leq \frac{1}{G_0}$

(AdaGrad)    $\u_{t+1} = \frac{1}{t+1}\sum_{i=0}^t\O^2_F(\x_i)$    $\|\O_F\|\infty\leq G$   $c_l \geq \frac{1}{G+G_0}, c_u \leq \frac{1}{G_0}$

Adam$^+$    $\u_{t+1} = \|\v_{t+1}\|$    $\|\O_F\|\leq G$     $c_l \geq \frac{1}{\sqrt{G}+G_0}, c_u \leq \frac{1}{G_0}$

Adabound    $\u'_{t+1} = (1-\beta_t')\u'_t + \beta_t' \O_F^2(\x_t)$
$\u_{t} = \Pi_{[1/c_u^2, 1/c_l^2]}[\u'_{t+1}],\quad G_0 =0$    -      $c_l = c_l, c_u =c_u$

To prove the convergence of the update (<ref>). We first present a key lemma.

For $\x_{t+1} = \x_t- \teta_t \circ \v_{t+1}$ with $\eta_t c_l\leq \teta_{t,i}\leq \eta_t c_u$ and $\eta_t L_F\leq c_l/(2c_u^2)$, we have

\begin{align*}
&F(\x_{t+1})  \leq F(\x_t) +   \frac{ \eta_t c_u}{2}\|\nabla F(\x_t) - \v_{t+1}\|^2- \frac{\eta_t c_l}{2}\|\nabla F(\x_t)\|^2  - \frac{\eta_t c_l}{4}\|\v_{t+1}\|^2.
\end{align*}

With the above lemmas, we can establish the following convergence of Adam-style algorithms.

Let $\Delta_t = \|\v_{t+1} - \nabla F(\x_t)\|^2$ and $ F(\x_0) - F_*\leq \Delta_F$ where $F_* = \min\limits_{\x} F(\x)$. Suppose Assumptions <ref> and <ref> hold. With $\beta_t=\beta \leq \frac{\epsilon^2c_l}{12\sigma^2c_u}$, $\eta_t=\eta\leq \min\{\frac{\beta\sqrt{c_l}}{2L_F\sqrt{c_u^3}}, \frac{1}{\sqrt{2} L_Fc_u},\frac{c_l}{2c_u^2L_F}\} $, $T\geq\max\{\frac{6\Delta_0c_u}{\beta\epsilon^2c_l}, \frac{12\Delta_F}{\eta\epsilon^2 c_l}\}$, we have

\begin{align*}
\E\left[\frac{1}{T+1}\sum_{t=0}^T \|\nabla F(\x_t)\|^2\right]\leq \epsilon^2, \quad \E\left[\frac{1}{T+1}\sum_{t=0}^T\Delta_t\right]\leq 2\epsilon^2.
\end{align*}

Remark: We can see that the Adam-style algorithms enjoy an oracle complexity of $O(1/\epsilon^4)$ for finding an $\epsilon$-stationary solution. To the best of our knowledge, this is the first time that the Adam with a large momentum parameter $1-\beta$ was proven to converge. One can also use a decreasing step size $\eta_t\propto 1/\sqrt{t}$ and decreasing $\beta_t =1/\sqrt{t}$ (i.e, increasing momentum parameter) and establish a rate of $\widetilde O(1/\sqrt{T})$ as stated below.

Let $\Delta_t = \|\v_{t+1} - \nabla F(\x_t)\|^2$ and $ F(\x_0) - F_*\leq \Delta_F$ where $F_* = \min\limits_{\x} F(\x)$. Suppose Assumption <ref> holds.   With
$c_1 = \min(1, \frac{1}{4c\sigma^2})$,
$\beta_t=\frac{c_l}{8\sigma^2 c c_u \sqrt{t+1}}$,
$\eta_t = \min\{\frac{\beta_t \sqrt{c_l}}{2 L_F \sqrt{c_u^3}}, \frac{1}{2L_F c_u}, \frac{c_l}{2c_u^2 L_F}\}$ and  $T\geq \widetilde{O}(\frac{c_u^5 c^2 L_F^2 \sigma^4 \Delta_F^2/c_l^5 + \Delta_0^2 c^2 c_u^4 \sigma^4/c_l^4 + 1/c}{\epsilon^4})$, we have

\begin{align*}
\E\left[\frac{1}{T+1}\sum_{t=0}^T \|\nabla F(\x_t)\|^2\right]\leq O(\epsilon^2), \quad  \E\left[\frac{1}{T+1}\sum_{t=0}^T\Delta_t\right]\leq O(\epsilon^2).
\end{align*}

§ CONCLUSION & DISCUSSION

In this paper, we have provided a simple and generic convergence analysis for a family of Adam-style methods for solving non-convex minimization problems.  We leveraged the variance recursion of the stochastic moving average estimator and established the convergence of practically used Adam and its variants. Our results bring some new insights to make the Adam method converge or convergence better.

Indeed, the Lemma 3 paves the way for the convergence analysis of many Adam-style algorithms for solving a broader family of problems, including non-convex strongly concave min-max optimization problems, non-convex stochastic compositional optimization problems, and non-convex bilevel optimization problems. It is also worth mentioning that we can also prove a faster convergence of the Adam-style algorithms under a strong Polyak-Łojasiewicz condition. We will explore this direction and examine how it will affect the convergence rate in the future work.

Finally, it is worth mentioning that the oracle complexities established in this paper are optimal under a general stochastic unbiased oracle model. In addition, one can also replace the variance recursion of the stochastic moving average estimator by that of other stochastic estimators (e.g. STORM) to prove an optimal convergence under Lipchitz continuous oracle model.

§ STOCHASTIC MOMENTUM METHOD

In the literature <cit.>, the stochastic heavy-ball method is written as:

\begin{equation}\label{eqn:hb2}
\hspace*{-0.3in}\text{SHB:}\quad\left\{ \begin{aligned}
& \v'_{t+1} = \beta' \v'_{t} - \eta'\O_F(\x_t)\\
&\x_{t+1}  =  \x_t + \v_{t+1}, \quad t= 0, \ldots, T.
\end{aligned}\right.
\end{equation}

To show the resemblance between the above update and the one in (<ref>), we can transform them into one sequence update:

\begin{align*}
&(\ref{eqn:sma}):  \x_{t+1} = \x_t - \eta \beta\O_F(\x_t) +   (1-\beta)(\x_t - \x_{t-1})\\
& \text{SHB: } \x_{t+1} = \x_t - \eta'\O_F(\x_t) + \beta' (\x_t - \x_{t-1}).
\end{align*}

We can see that SHB is equivalent to (<ref>) with $\eta'= \eta\beta$ and $\beta' =   (1-\beta)$.

§ PROOF OF LEMMA <REF>

Due to the smoothness of $F$, we can prove that under $\eta_t L_F\leq c_l/(2c_u^2)$

\begin{align*}
&F(\x_{t+1}) \leq F(\x_t) + \nabla F(\x_t)^{\top} (\x_{t+1} - \x_t) + \frac{L_F}{2}\|\x_{t+1} - \x_t\|^2\\
&= F(\x_t) - \nabla F(\x_t)^{\top}(\teta_t\circ \v_{t+1}) + \frac{L_F}{2}\|\teta_t\circ\v_{t+1}\|^2\\
&  \leq F(\x_t) +   \frac{1}{2}\|\sqrt{\teta_t}\circ(\nabla F(\x_t) - \v_{t+1})\|^2- \frac{1}{2}\|\sqrt{\teta_t}\circ\nabla F(\x_t)\|^2 + (\frac{L_F}{2} \|\teta_t\circ\v_{t+1}\|^2 - \frac{1}{2}\|\sqrt{\teta_t}\circ\v_{t+1}\|^2 ) \\
&  \leq F(\x_t) +   \frac{\eta_t c_u}{2}\|\nabla F(\x_t) - \v_{t+1}\|^2- \frac{\eta_t c_l}{2}\|\nabla F(\x_t)\|^2   +  \frac{\eta_t^2 c_u^2L_F - \eta_t c_l}{2}\|\v_{t+1}\|^2\\
&  \leq F(\x_t) +   \frac{\eta_t c_u}{2}\|\nabla F(\x_t) -  \v_{t+1}\|^2- \frac{\eta_t c_l}{2}\|\nabla F(\x_t)\|^2  -  \frac{\eta_t c_l}{4}\|\v_{t+1}\|^2.
\end{align*}

§ PROOF OF THEOREM <REF>

By applying Lemma <ref> to $\v_{t+1}$, we have

\begin{align*}
\E_t[\Delta_{t+1}]\leq (1-\beta)\Delta_t+ 2\beta^2\sigma^2(1+c\|\nabla F(\x_{t+1})\|^2)  + \frac{L_F^2\|\x_{t+1} - \x_{t}\|^2}{\beta}.
\end{align*}

Hence we have,

\begin{equation*}
\begin{split}
\E\left[\sum_{t=0}^T\Delta_t\right]\leq \E\left[\sum_{t=0}^T\frac{\Delta_t - \Delta_{t+1}}{\beta} + 2\beta\sigma^2(T+1) + 2\beta\sigma^2 c\sum_{t=0}^T\|\nabla F(\x_{t+1})\|^2+ \sum_{t=0}^T\frac{L_F^2\eta^2c_u^2\|\v_{t+1}\|^2}{\beta^2}\right].
\end{split}
\end{equation*}

Adding the above inequality with Lemma <ref>, we have

\begin{align*}
&\frac{\eta c_l}{2}\E\left[\sum_{t=0}^T\|\nabla F(\x_t)\|^2\right] \leq F(\x_0) - F_* - \frac{\eta c_l}{4}\sum_{t=0}^T\|\v_{t+1}\|^2\\
&  + \frac{\eta c_u}{2}\E\left[\sum_{t=0}^T\frac{\Delta_t - \Delta_{t+1}}{\beta} + 2\beta\sigma^2(T+1) + 2\beta\sigma^2 c\sum_{t=0}^{T}\|\nabla F(\x_{t+1})\|^2+ \sum_{t=0}^T\frac{L_F^2\eta^2c_u^2\|\v_{t+1}\|^2}{\beta^2}\right]\\
&\leq   F(\w_0) - F_* - \frac{\eta c_l}{4}\sum_{t=0}^T\|\v_{t+1}\|^2 \\
&  + \frac{\eta c_u}{2}\E\left[\sum_{t=0}^T\frac{\Delta_t - \Delta_{t+1}}{\beta} + 2\beta\sigma^2(T+1) + 4\beta\sigma^2 c\sum_{t=0}^{T}\|\nabla F(\x_{t})\|^2 + 4\beta\sigma^2cL_F^2\eta^2c_u^2\|\v_{t+1}\|^2\right.\\
&\left.+ \sum_{t=0}^T\frac{L_F^2\eta^2c_u^2\|\v_{t+1}\|^2}{\beta^2}\right]
\end{align*}

Let $L_F^2\eta^2 c_u^3/(2\beta^2) \leq  c_l/8$ (i.e., $\eta\leq \frac{\beta\sqrt{c_l}}{2L_F\sqrt{c_u^3}})$ and $2\beta\sigma^2 c\leq c_l/(4c_u)$, $2\beta\sigma^2cL_F^2\eta^2c_u^3\leq c_l/8$ (i.e, $\eta L_F\leq \frac{1}{\sqrt{2}c_u}$), we have

\begin{equation*}
\begin{split}
\frac{1}{T+1}\E\left[\sum_{t=0}^T\|\nabla F(\x_t)\|^2\right] &\leq \frac{\Delta_0c_u}{\beta T c_l}  +  \frac{2(F(\x_0) - F_*)}{\eta c_lT} + 2\beta\sigma^2\frac{c_u}{c_l}  +  \frac{1}{2}\frac{1}{T+1}\E\bigg[\sum_{t=0}^T\|\nabla F(\x_{t})\|^2\bigg].
\end{split}
\end{equation*}

As a result,

\begin{align*}
\frac{1}{T+1}\E\left[\sum_{t=0}^T\|\nabla F(\x_t)\|^2\right] &\leq\frac{2\Delta_0c_u}{\beta T c_l}  +  \frac{4(F(\x_0) - F_*)}{\eta c_lT} + 4\beta\sigma^2\frac{c_u}{c_l}.
\end{align*}

With $\beta \leq \frac{\epsilon^2c_l}{12\sigma^2c_u}$, $T\geq\max\{\frac{6\Delta_0c_u}{\beta\epsilon^2c_l}, \frac{12\Delta_F}{\eta\epsilon^2 c_l}\}$, we conclude the proof for the first part.  For the second part,
we have

\begin{align*}
&\E\left[\sum_{t=0}^T\Delta_t\right]\leq \frac{\Delta_0}{\beta} + \beta\sigma^2(T+1) +\frac{c_l}{2c_u}\E\bigg[\sum_{t=0}^T\|\nabla F(\x_{t})\|^2\bigg] +  \E\bigg[\sum_{t=0}^T\frac{c_l}{2c_u}  \|\v_{t+1}\|^2\bigg]\\
& \leq \frac{\Delta_0}{\beta} + 2\beta\sigma^2(T+1) +\frac{1}{2}\E\bigg[\sum_{t=0}^T\|\nabla F(\x_{t})\|^2\bigg] +  \E\bigg[\sum_{t=0}^T\frac{1}{2}\Delta_t\bigg]
\end{align*}

As a result,

\begin{align*}
&\E\left[\frac{1}{T+1}\sum_{t=0}^T\Delta_t\right]\leq \frac{2\Delta_0}{\beta T} + 4\beta\sigma^2 +\E\bigg[\frac{1}{T+1}\sum_{t=0}^T\|\nabla F(\x_{t})\|^2\bigg] \leq 2\epsilon^2.
\end{align*}

§ POOF OF THEOREM <REF>

By applying Lemma <ref> to $\v_{t+1}$, we have
\begin{equation}
\begin{split}
\E_t[\Delta_{t+1}] \leq (1-\beta_t) \Delta_t + 2\beta_t^2 \sigma^2 (1+c\|\nabla F(\x_{t+1})\|^2) + \frac{L_F^2\|\x_{t+1}-\x_t\|^2}{\beta_t}.
\end{split}
\end{equation}

Hence we have

\begin{equation}
\begin{split}
\E\left[ \sum\limits_{t=0}^T \beta_t \Delta_t\right] \leq \E\left[\sum\limits_{t=0}^{T}[\Delta_t - \Delta_{t+1}] + \sum\limits_{t=0}^{T} 2\beta_t^2\sigma^2(1+c\|\nabla F(\x_{t+1})\|^2) + \sum\limits_{t=0}^{T} \frac{L_F^2 \eta_t^2 c_u^2\|\v_{t+1}\|^2}{\beta_t} \right].
\end{split}
\end{equation}

Combining this with Lemma <ref>,

\begin{equation}
\begin{split}
&\E\left[ \sum\limits_{t=0}^T \frac{\eta_t c_l}{2} \|\nabla F(\x_t)\|^2 \right] \\
&\leq \E\Bigg[ \sum\limits_{t=0}^{T} [F(\x_t) - F(\x_{t+1})] - \sum\limits_{t=0}^{T} \frac{\eta_t c_l}{4} \|\v_{t+1}\|^2  \\
& ~~~~~~~ + \frac{\eta_1 c_u}{2 \beta_1} \left[\sum\limits_{t=0}^T (\Delta_t - \Delta_{t+1}) + \sum\limits_{t=0}^{T} 2\beta_t^2 \sigma^2 (1+c\|\nabla F(\x_{t+1})\|^2) + \sum\limits_{t=0}^{T} \frac{L_F^2 \eta_t^2 c_u^2 \|\v_{t+1}\|^2}{\beta_t} \right] \Bigg] \\
&\leq \E\Bigg[ \sum\limits_{t=0}^{T} [F(\x_t) - F(\x_{t+1})] - \sum\limits_{t=0}^{T} \frac{\eta_t c_l}{4} \|\v_{t+1}\|^2 \\
& ~~~~~~~ + \frac{\eta_1 c_u}{2 \beta_1} \left[\sum\limits_{t=0}^T (\Delta_t - \Delta_{t+1})  +\sum\limits_{t=0}^{T} 2\beta_t^2 \sigma^2 +\sum\limits_{t=0}^{T} 4\beta_t^2 \sigma^2 c\|\nabla F(\x_{t})\|^2)  + \sum\limits_{t=0}^{T} 4\beta_t^2 \sigma^2 c L_F^2 \eta_t^2 c_u^2 \|\v_{t+1}\|^2 \right. \\
&~~~~~~~~~~~~~~~~~~~~~    \left.
+ \sum\limits_{t=0}^{T} \frac{L_F^2 \eta_t^2 c_u^2 \|\v_{t+1}\|^2}{\beta_t} \right] \Bigg] \\
&\leq \E\left[F(\x_0) - F_* + \frac{\eta_1 c_u \Delta_0}{2\beta_1}  + \frac{2c_u \eta_1}{\beta_1 } \sum\limits_{t=0}^{T} \beta_t^2\sigma^2 + \sum\limits_{t=0}^{T}  \frac{\eta_t c_l}{4}\|\nabla F(\x_{t})\|^2) \right] ,
\end{split}
\end{equation}

where the last inequality holds because $\frac{2\eta_1 c_u}{\beta_1} \beta_t^2 \sigma^2 c \leq \frac{\eta_t c_l}{4}$, $\frac{2\eta_1}{\beta_1}\beta_t^2 \sigma^2 c L_F^2 \eta_t^2 c_u^3 \leq \frac{\eta_t c_l}{8}$ and $\frac{\eta_1}{2\beta_1} \frac{L_F^2 \eta_t^2 c_u^3}{\beta_t} \leq \frac{\eta_t c_l}{8}$.

\begin{equation}
\begin{split}
&\E[\sum\limits_{t=0}^{T} \eta_T c_l \|\nabla F(\x_t)\|^2] \leq \E[\sum\limits_{t=0}^{T} \eta_t c_l \|\nabla F(\x_t)\|^2] \\
&\leq \E\left[ 4(F(\x_0) - F_*) + \frac{2\eta_1 c_u \Delta_0}{\beta_1} + \sum\limits_{t=0}^T \frac{8 c_u \eta_1}{\beta_1} \beta_t^2 \sigma^2 \right] \\
&\leq \E\left[ 4(F(\x_0) - F_*) + \frac{\sqrt{c_l} \Delta_0}{L_F \sqrt{c_u}} + \sum\limits_{t=0}^T \frac{4 \sqrt{c_l}}{L_F \sqrt{c_u}} \beta_t^2 \sigma^2 \right] .
\end{split}
\end{equation}

\begin{equation}
\begin{split}
\E \left[ \frac{1}{T+1} \sum\limits_{t=0}^{T} \|\nabla F(\x_t)\|^2 \right] & \leq \E\left[ \frac{4(F(\x_0)-F(\x_*))}{\eta_T c_l (T+1)} + \frac{\Delta_0}{L_F \sqrt{c_l c_u} \eta_T (T+1)} +\sum\limits_{t=0}^{T} \frac{4\beta_t^2}{\eta_T L_F \sqrt{c_l c_u} (T+1)} \sigma^2 \right] \\
&\leq \frac{4\Delta_F}{\eta_T c_l (T+1)} +  \frac{\Delta_0}{L_F\sqrt{c_l c_u}\eta_T (T+1)} +  \frac{4 \sigma^2}{\eta_T L_F \sqrt{c_l c_u} (T+1)} \sum\limits_{t=0}^{T} \beta_t^2 \\
&\leq \frac{4\Delta_F}{\eta_T c_l (T+1)} + \frac{\Delta_0}{L_F \sqrt{c_l c_u} \eta_T (T+1)} + \frac{c_l^2}{16 \eta_T \sigma^2 L_F c^2 \sqrt{c_l c_u^5} (T+1)} \ln(T+2).
\end{split}
\end{equation}

Setting $T\geq \widetilde{O}(\frac{c_u^5 c^2 L_F^2 \sigma^4 \Delta_F^2/c_l^5 + \Delta_0^2 c^2 c_u^4 \sigma^4/c_l^4 + 1/c}{\epsilon^4})$, we conclude the proof for the first part.
For the second part, we have

\begin{equation}
\begin{split}
\E\left[ \sum\limits_{t=0}^T \beta_t \Delta_t \right] \leq \Delta_0 + \frac{c_l^2}{16 \sigma^4 c^2 c_u^2} \ln(T+2) + \frac{1}{2} \E\left[  \sum\limits_{t=0}^{T} \beta_t \|\nabla F(\x_t)\|^2\right]
+ \E\left[ \sum\limits_{t=0}^{T} \frac{1}{2} \beta_t \Delta_t \right] .
\end{split}
\end{equation}

\begin{equation}
\begin{split}
\E\left[ \frac{1}{T+1} \sum\limits_{t=0}^{T} \Delta_t \right] \leq \frac{2\Delta_0}{\beta_T T} + \frac{c_l^2}{8 \sigma^4 c^2 c_u^2 (T+1)} \ln(T+2)
+ \frac{1}{2} \E\left[\sum\limits_{t=0}^{T} \beta_t \|\nabla F(\x_t)\|^2\right],
\end{split}
\end{equation}

which concludes the proof of the second part.


# ExplorerTree: a focus+context exploration approach for 2D embeddings*

Wilson E. Marcílio-Jr, Danilo M. Eler Dept. of Mathematics and Computer
Science São Paulo State University Presidente Prudente, SP, Brazil
{wilson.marcilio<EMAIL_ADDRESS>Fernando V. Paulovich Faculty of
Computer Science Dalhousie University Halifax, NS, Canada<EMAIL_ADDRESS>

José F. Rodrigues-Jr Inst. of Mathematics and Computer Sciences University of
São Paulo São Carlos, SP, Brazil<EMAIL_ADDRESS>Almir O. Artero Dept. of
Mathematics and Computer Science São Paulo State University Presidente
Prudente, SP, Brazil<EMAIL_ADDRESS>*This is the preprint version of a
published work. DOI: https://doi.org/10.1016/j.bdr.2021.100239

###### Abstract

In exploratory tasks involving high-dimensional datasets, dimensionality
reduction (DR) techniques help analysts to discover patterns and other useful
information. Although scatter plot representations of DR results allow for
cluster identification and similarity analysis, such a visual metaphor
presents problems when the number of instances of the dataset increases,
resulting in cluttered visualizations. In this work, we propose a scatter
plot-based multilevel approach to display DR results and address clutter-
related problems when visualizing large datasets, together with the definition
of a methodology to use focus+context interaction on non-hierarchical
embeddings. The proposed technique, called ExplorerTree, uses a sampling
selection technique on scatter plots to reduce visual clutter and guide users
through exploratory tasks. We demonstrate ExplorerTree’s effectiveness through
a use case, where we visually explore activation images of the convolutional
layers of a neural network. Finally, we also conducted a user experiment to
evaluate ExplorerTree’s ability to convey embedding structures using different
sampling strategies.

###### Index Terms:

Dimensionality Reduction, Visualization, Scatter-plot, Focus+context

##  I Introduction

The increasing amount of high-dimensional data has led to the development of
techniques that try to extract patterns present in these datasets. For
example, Multidimensional Projection (MP) or Dimensionality Reduction (DR)
[13, 21, 9, 16] techniques produce low-dimensional representations (or
embeddings) that respect similarity relationships among data points [22]. The
results of these techniques are usually visualized as scatter plots, where
spatial proximity depicts similarity. For small datasets, scatter plots can
rapidly convey clusters and patterns present in the data. However, the
analysis of big datasets tends to cause problems due to the non-visual
scalability of scatter plot representations. Accordingly, interaction
mechanisms are applied to ease data analysis, such as hierarchical
exploration. These hierarchical approaches have the advantage of providing
information on demand, according to information demand. For example, in
techniques such as HiPP [20] and h-SNE [8], users visualize dominant
structures, then successive refinements on the visual layouts make data
observations accessible.

Interaction mechanisms, such as brushing and linking, coordination, and
focus+context, play an essential role in providing more straightforward
exploration and helping users cope with cognitive overload. The focus+context
concept [18], for example, can be naturally used in hierarchical
representations of DR results since the most fine-grained information
corresponds to the focus, and the information that is not necessary at the
moment corresponds to the context. Höllt et al. [8] proposed the focus+context
concept for hierarchical embeddings (results generated by hierarchical
dimensionality reduction techniques) by defining a set of requirements to
support exploration. However, their work does not address DR techniques that
operate in one single level of detail. Besides that, there is no study
combining focus+context exploration in any embedding results with concerns
about visual scalability.

In this work, we propose the ExplorerTree, an approach to hierarchically
explore dimensionality reduction results using the focus+context exploration
approach that accounts for concerns of visual scalability of scatter plot-
based representations. Throughout the exploratory process, users receive
visual cues and important structures about the projection. Further, our
approach extends the hierarchical exploration concept proposed by Höllt et al.
[8] even to DR techniques that cannot be extrapolated to hierarchical versions
[19]. Since the embedding’s hierarchical structure is created based on a
sampling selection mechanism [14] that preserves the scatter plots
visualization overview (e.g., class boundaries and outliers), users visualize
the main structures with reduced cognitive effort induced by overlapping
visual markers. The sampled data points guide users throughout the exploratory
process using the overview-first & details-on-demand mantra [27]. More data
points are projected onto the visual space to provide finer-grained
information based on the interaction with the representative data points, that
address the scatter plot metaphor’s well-known difficulties related to visual
clutter.

Throughout the paper, we propose new requirements for hierarchical
exploration, accounting for visual scalability. Then, we demonstrate our
encoding strategies to represent clusters’ density, class variability, and
content information for each node of the hierarchy generated from the
successive sampling selection. Finally, we provide a use case to demonstrate
our approach’s viability by exploring the activation images of convolutional
layers of a convolutional neural network.

Summarily, the main contributions of this work are:

  1. 1.

A hierarchical exploration approach of any embedding using focus+context
concept, accounting for visual scalability;

  2. 2.

A design mechanism to reduce visual clutter on hierarchical representations of
dimensionality reduction results;

  3. 3.

Requirements to facilitate exploration of 2D embeddings considering visual
scalability.

This paper is structured as follows. Section II presents the related works. In
Section III, we discuss the requirements for the hierarchical exploration of
multidimensional embeddings. In Section IV, we explain the ExplorerTree
hierarchical construction mechanism and visualization design, and how we
choose the sampling selection mechanism. Section V provides a use case using
ExplorerTree to explore filter activations of a convolutional neural network.
In Section VI, we discuss the technique and its limitations. Finally, we
conclude our work in Section VII.

##  II Related Works

Many dimensionality reduction techniques have been proposed through the years,
presenting advantages in various aspects. For example, LSP [21] presents
promising results for preserving neighborhood relations, while t-SNE [13] can
efficiently separate classes on the projected space. Espadoto et al. [4]
provide a useful categorization of dimensionality reduction techniques. From
the visualization point of view, Nonato and Aupetit [19] present an excellent
categorization of multidimensional projection techniques, linking
visualization with distortion, tasks, and many other aspects. Although applied
in a variety of problems, dimensionality reduction techniques generate
cluttered layouts for big datasets, which difficult analysis and require high
cognitive overload.

Hierarchical and interaction mechanisms facilitate exploratory tasks and
knowledge discovery, besides minimizing cluttered layouts when dealing with
large datasets. For example, InfoSky [1] hierarchically explores document
collections by mapping documents to star glyphs and using polygons to depict
similar documents and provide separation among clusters. Users change the
level of detail according to demand following a telescope metaphor. MDSteer
[32] computes an MDS embedding, showing promising results in the first
hierarchical levels. However, overplotting is still present when reaching the
lowest levels of the tree structure. Besides that, there is no additional
information to help users in the exploration tasks. HIPP [20] uses
representatives extracted from a clustering process to generate a hierarchical
layout. The technique uses LSP for positioning data instances and rearranges
the layout on the first hierarchical level to reduce overlap among nodes
(circles with varying sizes that encode clusters). Although this process
reduces the overplotting by reducing overlap, it modifies the global relations
among data samples. For instance, meaningful hierarchical exploration
strategies are one of the challenges of single-cell RNA sequencing data [12],
in which global relations play an important role. Pezzotti et al. [24]
proposed a technique called h-SNE, which uses t-SNE [13] to perform projection
and builds the hierarchy based on random walks on a neighborhood graph. Such
characteristic allows exploration according to information demand. However,
the generated layout can still be cluttered and confusing if these structures
have a large size. Another related work, called Visual Super Tree [28],
employs focus+context exploration to reduce the burden when analyzing big
datasets using the similarity tree metaphor. It employs node expansion and
contraction to refine and hide information throughout the exploratory process.
Besides being dependent on the number of clusters chosen to create the
hierarchy (as in the HiPP technique), during the exploratory process, visual
scalability can be a problem when dealing with big datasets that require
successive node expansions. There is no proper way to differentiate structures
in focus from structures in context during successive node expansions. While
visualizing the expanded nodes in new windows addresses this problem, such an
approach loses the context between data instances.

The focus+context concept for hierarchical multidimensional embeddings was
defined by Höllt et al. [8] through a set of design requirements. However,
while the requirements (detailed in the next section) are useful for
interaction/navigation aspects, there is still no discussion about the
hierarchical exploration of multidimensional embeddings’ visual scalability.

In this work, we address the problem of focus+context interaction in
multidimensional embeddings and give attention to the visual scalability
aspects during exploration. We propose three new requirements besides showing
mechanisms to apply focus+context exploration to any multidimensional
embedding, not only a few existing hierarchical ones. Our work also accounts
for hierarchical dimensionality reduction techniques, making our approach
applicable to all DR results represented by scatter plots.

##  III Requirements for focus+context exploration of hierarchical embeddings

A hierarchical exploration approach must follow a few design requirements to
facilitate user analysis. In addition to the interaction (I1 \- I9) and visual
(V1 \- V4) requirements proposed by Höllt et al. [8] to support a compelling
exploration of hierarchical embeddings using the focus+context concept (see
Table I), in this work, we propose three new requirements (R1 \- R3) to deal
with visual clutter in 2D embeddings visualized as scatter plots and to guide
users through exploratory processes.

TABLE I: Requirements for supporting the exploration of hierarchical embeddings using Focus+Context concept. Interaction (I1-I9) and Visual (V1-V4) were proposed by T. Höllt et al. [8]. Requirement | Description
---|---
I1 | request more detail for all data
I2 | request less detail for all data
I3 | return to the initial state
I4 | define an area of interest (focus)
I5a | change the focus to a subset of the current focus
I5b | change the focus to a different set of points
I6 | request more detail for the focus
I7 | request less detail for the focus
I8 | create a second focus for comparison
I9 | resolve the second focus
V1 | the focus must use extended space in the visualization
V2 | the focus must be separated from the context
V3 | maintain connections between focus and context
V4 | different hierarchy levels must be identifiable
R1 | reduce visual disorder (clutter)
R2 | show information about the clusters
R3 | reduce overlaps among graphical markers

The requirements of this study deal with the visual scalability aspects faced
when exploring embeddings represented by scatter plots. Specifically,
requirements R1 and R3 deal with the visual representation’s ability to
communicate clusters and patterns in the data. While these two requirements
may seem very similar at first, they acknowledge different problems usually
present in traditional scatter plot representations. R1 (reduce visual
disorder (clutter)) considers the problem when a projection is too cluttered
with visual markers, being difficult to identify patterns and clusters. On the
other hand, R3 (reduce overlaps among visual markers) helps users explore
clusters without losing track of the relationship imposed by the
dimensionality reduction process. While readers may think that reducing
overlapping the visual disorder will also be reduced, the literature [15]
shows that the existing removal algorithms cannot reduce the overlapping of
big datasets without imposing severe issues to the similarity and neighborhood
structures of the projected dataset. Finally, R2 (show information about the
clusters) helps users navigate the dataset using visual cues of the cluster’s
content. Such a requirement also helps to obtain some of the information lost
during sampling selection.

In summary, a big part of our work is related to deal with visual scalability
problems of scatter plot representations produced by dimensionality reduction
methods. While removing all of the overlappings of a projection results in
layouts with issues regarding similarity and neighborhood structures [15], the
visual exploration is usually performed by looking at dominant structures and
refining the search according to the user’s needs. That is, we argue that
efforts to reduce overplotting globally can be meaningless when taking the
natural exploration approach into account. In this work, we use sampling
selection and overlapping removal approaches on a hierarchical representation
of scatter plots; the aim is to provide a facilitated exploration of high-
dimensional data, which comprises our design mechanism to reduce visual
clutter on hierarchical representations of dimensionality reduction results.

##  IV ExplorerTree

Using the design requirements, we define a hierarchical exploration approach
through successive sampling and clustering procedures on the embedding space.
Figure 1 shows representative selection (or sampling) from $\mathbb{R}^{2}$
embedding to create a hierarchical structure on the data (1); then, the second
step (2) deals with the use of visual variables (e.g., area and color),
interaction mechanisms (e.g., overview-first & details-on-demand and
focus+context), visual summaries and overlap removal mechanisms to provide a
facilitated exploration of the hierarchy.

Figure 1: Schematic view of ExplorerTree. Our approach takes points in
$\mathbb{R}^{2}$ to create a tree structure based on representative selection
(1), then exploration is performed using the Focus+Context concept (2). In the
visual representation, a color scale encodes hierarchy levels while visual
summaries are employed to understand clusters’ content.

A hierarchical structure for a 2D embedding is created based on sampling and
clustering from the data points – we use the terms sampling and representative
selection interchangeably. Using sampling, we reduce visual complexity – since
fewer data points are projected onto the plane – while maintaining useful
information about the embedding structures (requirement R1), that is, class
boundaries and density information. The first sampling process results in
representative data points that generate the nodes/clusters of the first
hierarchical level. According to Euclidean distance, the non-representative
data points are associated with the closest representative data point cluster
in these clusters. Then, the nodes/clusters computed from the first sampling
process result in the input of new sampling processes to induce a hierarchical
structure on the scatter plot representation.

Figure 2 illustrates the process of imposing a hierarchical structure on
points in $\mathbb{R}^{2}$. At first, the set of points consists of the whole
dataset. Then, the sampling and clustering algorithms return the
clusters/nodes of the first hierarchy level. Such a process is repeated for
each cluster returned in the last component until a cluster has fewer data
points than a pre-defined parameter, represented by $\pi$.

Figure 2: Sequence of steps to create a tree structure on data points in
$\mathbb{R}^{2}$. Representatives are sampled from a set of points and used to
impose a partition on the dataset, generating a set of clusters. The process
(selecting representatives and defining partition) is repeated for each
cluster whose size is greater than a pre-specified parameter ($\pi$).

We did not use hierarchical clustering for sampling selection because much
information is lost when projecting only the medoids. Instead, we aim to
preserve, as discussed in Section IV-A, the overall structure and the context
of the scatter plot layout and ensure good representativity of the whole
dataset.

###  IV-A Representative selection

The representative selection is one of the essential steps of ExplorerTree. A
suitable representative/sampling selection technique selects data points that
cover the embedding with low redundancy. A more trustful exploration is
achieved if a sampling selection technique preserves the structures and class
boundaries of a scatter plot representation.

####  IV-A1 Visual quality using different sampling strategies

A sampling technique must cover the structures presented in the visual space
and do not present redundancy among the sampled data instances to guarantee
good preservation of structures and not deceive users throughout the
exploratory process. In the Supplementary File (Figure 2), we numerically
evaluated these aspects for SADIRE [14], k-Means [29], Reservoir [31], and CSM
[10] techniques. The experiments show decent run-time executions for SADIRE
(losing only to Reservoir) while surpassing all the other techniques regarding
coverage and redundancy aspects.

Figure 3 shows an example of SADIRE’s suitability against the other
techniques. On the left, LSP [21] projection of the Corel dataset with five
thousand data instances colored according to their class. On the right, we
show the first level of ExplorerTree (detailed explained in the next section)
on the same dataset using the sampling strategies. Unlike the other
techniques, SADIRE covers all the projected space with sampled data instances
while the circle area correctly shows the densest parts of the projection.
Reservoir and CSM lose many structures that SADIRE correctly encodes – see
these structures highlighted in orange. Finally, Bisecting k-means does not
encode well the density information, aggregating data instances that do not
correspond to the projection’s density – see the structures highlighted in
blue. Supplementary File’s Figure 6 shows the same analysis for other
datasets.

Figure 3: ExplorerTree using different sampling algorithms. On the left, the
traditional scatter-plot representation. On the right, the first level of
ExplorerTree using four sampling strategies.

We performed a user experiment using these sampling strategies to verify how
participants evaluate ExplorerTree first hierarchical level under different
conditions. The details of this user experiment are in Section 5 of
Supplementary File. Nevertheless, the participants assigned higher scores for
ExplorerTree using SADIRE and Bisecting k-Means, which justifies our choice
for SADIRE due to its rapid run-time execution needed for interactive
purposes.

####  IV-A2 Selecting candidates for representative set using SADIRE

Given a scatter plot in $\mathbb{R}^{2}$, SADIRE uses a grid of cells with
size $k\times k$ to divide the projected space and retrieves the medoid from
each cell with at least one data point. Figure 4 illustrates the main steps of
SADIRE sampling technique. After the projection of data points onto
$\mathbb{R}^{2}$, a grid with cell size $k\times k$ group too similar data
points (a). Then, a set of candidates for representative data points consists
of the cells with data points (b) – the density of each cell also has to be
stored in this step, as depicted by color saturation. Finally, only the medoid
of each cell is selected as the representative data point after redundancy
removal (c).

Figure 4: SADIRE’s main execution steps. (a) A grid of cells with size
$k\times k$ divides the $\mathbb{R}^{2}$ space, the density of each cell is
also stored; (b) Only cells with at least one point are retrieved; (c) For
each cell, the medoid selected as a representative data point. Between steps
(a) and (b), SADIRE applies a redundancy removal mechanism – in this case, a
window of size $\alpha=3$ removes redundant data points..

###  IV-B Hierarchy Construction

The sampling technique allows ExplorerTree to cluster data points and employ
successive operations to create a hierarchical structure. Formally, let
$\mathscr{D}^{0,0}_{1,1}$ be a set of points in $\mathbb{R}^{2}$ after
dimensionality reduction with no imposed hierarchical structure, where
$\mathscr{D}^{j-1,l}_{j,i}$ denotes a cluster $i$ in the hierarchy level $j$,
and ($j-1,l$) denotes the level and the cluster index of its parent. The first
sampling process ($\mathscr{S}_{1,1}$) imposes a partition on the cluster of
the first level, i.e., the set of points in $\mathbb{R}^{2}$ after
dimensionality reduction. Figure 5 illustrates the sampling process, which
returns $n$ ($2\leq n\leq m$) clusters, where $m$ depends on the minimum size
of data points allowed in each cluster, as detailed in Section IV-B1. The
sampling selection repeats for each cluster of the second level of the
hierarchy – for each $\mathscr{D}_{2,i}^{1,1}$. Notice that the index of any
sampling process corresponds to the same cluster index, and the superscript
indices of any cluster/node must match the subscript indexes of its parent. In
the figure, gray edges indicate the parent-child relationship. Black arrows
indicate the requirements, the bars below nodes indicate tree leaves, and
dashed arrows indicate successive operations from the leaves to the root.

Figure 5: Tree structure created by sampling on the cluster/nodes. The bars
below nodes indicate leaf nodes, where ExplorerTree ends representative
selection.

Generalizing, the sampling process ($S_{j,i}$) of an arbitrary cluster ($i$)
in an arbitrary hierarchy level ($j$) extracts representative data points from
the corresponding cluster on the corresponding level
($\mathscr{D}_{j,i}^{j-1,l}$). The result of sampling is a partition on the
cluster, where the union of all generated subclusters results in the parent
cluster ($\bigcup\mathscr{D}^{j,i}_{j+1,\\{K\\}}=\mathscr{D}_{j,i}^{j-1,l}$,
where $\\{K\\}$ is the set of all subclusters), and two subclusters cannot
share any data point
($\mathscr{D}_{j,a}\cap\mathscr{D}_{j,b}=\emptyset,\forall a\neq b$).

Using the tree structure, we accomplish a few requirements of Table I and
highlighted in Figure 5. For instance, successive resolving focus operations
accomplish requirement I3 (return to the initial state). Selection of
representatives accomplishes requirement I4 (define an area of interest).
Requirements I6 (request more detail for the focus) and I7 (request less
detail for the focus) are accomplished with interaction on the pre-defined
clusters. Requirement I5a (change the focus to a subset of the current focus)
is accomplished by interacting with the children of the focused node, i.e., by
requesting focus on the focused node’s children. Requirement I5b (change the
focus to a different set of points) is accomplished by our technique when
users decide to focus on two different clusters/nodes – a curved horizontal
arrow indicates this. Requirement I8 (create a second focus for comparison) is
accomplished by only interacting with another node of interest. Finally, by
resolving focus on the node selected for comparison, we accomplish requirement
I9.

####  IV-B1 Considerations

First, the number of sampling and clustering processes executed on the
embedding depends on the minimum cluster size parameter ($\pi$), which
influences in the number of hierarchy levels. That is, the bigger is $\pi$,
the lower is the number of levels in the tree. Finally, requirement R3
specifies that the overlap among markers must be decreased/removed. In this
case, such an operation is performed based on user interaction when one
reaches a leaf cluster. Overlap removal can be performed using various
techniques – such as PRISM [5], VPSC [3], ProjSnippet [7], and RWordle [30] –
since leaf cluster have limited size and, consequently, there is no much
concern about which one to apply [15].

During hierarchical exploration, SADIRE sampling selection mechanism is
sufficient to reduce overlap among visual markers. However, when inspecting
data observations on the lowest hierarchy levels, we cannot sample data points
to facilitate exploration nor impose significant changes on the layout
arrangement. However, it is interesting to know that overlapping removal on
clusters with only a few data points does not impose significant changes in
structural relations [15]. In this case, choosing a reasonable number of $\pi$
($\sim 200$) results in layout with reduced information loss after overlap
removal.

Finally, due to the requirement that each cluster has at least $\pi$ data
points, a few invalid clusters with a smaller size than $\pi$ could appear
during hierarchy creation. A rollback process merges the invalid cluster to
its nearest cluster based on the complete linkage distance to solve such a
problem. For instance, the merging process happens under two circumstances.
First, the partition of a cluster with greater size than $\pi$ may generate
two invalid clusters; as shown in Figure 6a, the partition (1.) of the cluster
represented by red colors generates two invalid clusters (2.), then, we merge
these clusters (3.) to become a leaf node/cluster. In the second case, the
partition produces only one invalid cluster, represented in Figure 6b (2.) by
red-colored data points; the rollback process merges this cluster to the one
that generated it. In the figure, non-transparent circles with a black halo
encode representative data points.

(a) Case 1: a partition generates two invalid cluster – red and purple –,
which are merged.

(b) Case 2: a invalid cluster is merged to its nearest cluster.

Figure 6: Validating clusters according to the constraint of minimum cluster
size ($\pi$).

####  IV-B2 ExplorerTree algorithm

Algorithm 1 summarizes the main steps for creating the ExplorerTree
hierarchical structure. The algorithm starts by receiving a set of points
($X$) in the $\mathbb{R}^{2}$, the sampling selection strategy, the minimum
size of the clusters/nodes $\pi$, and the parent node. The algorithm’s first
step is to select representative data points from the data, as shown in line
3. Then, each non-representative data point is associated with the closest
representative data point (line 6) – we also store the parent information for
the nodes created by such association (line 7).

Algorithm 1 Creating ExplorerTree structure.

1:procedure $\mathbf{ExplorerTree}$($X\in\mathbb{R}^{2}$, Sampling, $\pi$,
parent)

2: $\triangleright$ Representative selection process

3: points $\leftarrow$ Sampling($X$)

4:

5: $\triangleright$ Clustering: associate each non-representative data point
to the closest representative

6: for $i\in|\text{points}|$ do

7: node.points $\leftarrow$ $\\{x\in X|\parallel x-point\parallel\leq\parallel
x-p_{j}\parallel,i\neq j\\}$

8: node.parent $\leftarrow$ parent

9:

10: $\triangleright$ Solving problems with invalid clusters, i.e.,
$|node|<\pi$

11: for node${}_{i}\in$ nodes do

12: if nodei.size $<\pi$ then

13: closest_node $\leftarrow$ closest nodej based on complete linkage distance
($i\neq j$)

14: closest_node $\leftarrow$ closest_node.points $\cup$ nodei.points

15:

16: $\triangleright$ If $|nodes|=1$, the parent must be a leaf

17: if $|nodes|=1$ then

18: return null

19:

20: $\triangleright$ If $|nodes|\neq 1$, we probably have more levels

21: for node $\in$ nodes do

22: if node.size $\geq 2\times\pi$ then

23: node.children $\leftarrow$ ExplorerTree(node.points, Sampling, $\pi$,
node)

24: return nodes

As commented previously, the partitioning process (representative selection
and clustering) could generate invalid clusters with a size lower than $\pi$.
Lines 8-12 of the algorithm check if each cluster generated in lines 6 and 7
is invalid. If it is the case, these clusters are merged to the closest
cluster according to the complete linkage metric (mean of distances between
data points from the two clusters). After this process, if all the nodes were
merged, we return null, and the parent node becomes a leaf (lines 14 and 15).
Finally, if the clusters/nodes generated from the partitioning process
produced valid clusters, we create new hierarchical levels if the nodes’ size
is bigger than $2\times\pi$. It means that we must have room for a least one
partition. Thus, we recursively call the same function with $X$ represented by
the points in each node and the parent set to the node. The result of such a
call is set as the children of the nodes.

###  IV-C Visualization design

In this section, we detail the visualization design of our approach by using a
t-SNE [13] projection of MNIST [11] dataset (see Figure 7). After delineating
our design choices, we validate the ExplorerTree using the same MNIST dataset
by exploring the activation images of convolutional layers of a convolutional
neural network trained on it.

As discussed earlier, the traditional approach to visualize dimensionality
reduction results (scatter plots) has a few issues regarding visual clutter,
interaction mechanisms, and overlapping. While the sampling technique reduces
the overplotting caused by the number of visual markers, it loses the density
information and makes it difficult to visualize the boundaries among classes
(see Figure 7b). Our approach introduces focus+context interaction to non-
hierarchical embeddings, providing a layout with reduced visual clutter and
visual guides to explore datasets using representatives. Figure 7c shows the
first level of the hierarchy built for the embedding of Figure 7a. Notice that
we present only the sampled instances (representatives) on the projection
plane to reduce visual clutter in B, where each circle area encodes cluster
size (see the legend in A). The arrow going from a representative to another
embedding depicts the focus request to that representative; the other three
representatives’ projection and the definition of the focus area highlighted
in orange update the embedding, which indicates the hierarchical level.
Finally, ExplorerTree shows additional information about the clusters (such as
class distribution, similar and diverse data instances) to provide more
details about the dataset.

(a) MNIST set with $10000$ data instances projected using t-SNE.

(b) SADIRE sampling technique on the MNIST set.

(c) ExplorerTree applied to the embedding of MNIST dataset.

Figure 7: Visual comparison among strategies to encode dimensionality
reduction results. Besides interaction, ExplorerTree uses various encoding
strategies to add information and help analysts deal with cognitive overload.

For the following example of interactions, we used the representative
selection parameters $k=15$ and $\alpha=1$, and the minimum size of clusters
($\pi$) as $5$.

####  IV-C1 Requesting Focus

Figure 8: Example of interaction with ExplorerTree. In (1) we show the first
level of the hierarchy, using circle area to encode cluster size. Layouts (2)
and (3) indicate the focus request until reaching a leaf cluster – see zoomed
area in (3). Layouts (4) and (5) show focus comparison between two clusters.
See how color scale of focus level can help users on locating themselves in
the hierarchy.

Users request focus ($\mathscr{F}_{+}$) through mouse clicks. Figure 8
illustrates this process when requesting focus from 1 to 2. The focus area is
depicted by a different color (an orange color scale) from the context (in
white), where color saturation of the polygons delimiting the focus area
encodes tree levels – see HIERARCHY LEVEL (CONTEXT) and the colored
polygons/focus area in Figure 8. Notice that the focus area receives more
visual space during user interaction, and the context clusters are positioned
at the embedding borders to maintain relative distances. The color scale used
to encode tree levels and the distortions imposed in the embedding are
sufficient to accomplish requirements (V1-V4). Moreover, the request-focus
operation accomplishes requirements I4, I5a, and I6.

####  IV-C2 Resolving Focus

Analogously as requesting focus, users interact with the representative
instances projected to resolve focus. Notice that resolving focus on arbitrary
clusters ($\mathscr{F}_{-}(\mathscr{D}_{j,i}^{j-1,k})$) results in the cluster
parent’s projection ($\mathscr{D}_{j-1,k}^{j-2,l}$), as illustrated in Figure
8. To resolve focus, users may use any cluster representative like in stage
(3). Users return to the initial hierarchy state and accomplish requirement I3
through successive resolving focus operations.

####  IV-C3 Comparing Focus

Users use the focus comparison operation
($\mathscr{F}_{c+}(\mathscr{D}_{j,i}^{j-1,k})$) to compare different clusters
under focus. Thus, there must be an already focused cluster on the embedding
before requesting the focus comparison. Otherwise, such a focus comparison
results in a requesting focus operation. Figure 8 ((4) and (5)) illustrates
the process of requesting focus comparison. Firstly, users select an arbitrary
cluster represented by the representative class colored in purple and
indicated by a pink arrow. After requesting focus on the cluster, the focus
area is differentiated from the context, as shown on the embedding (4). Then,
another cluster is chosen (indicated on the embedding (5)) compared to the
already selected focus. In this case, the expansion of the space induced by
the second focus area is limited, as we will explain later.

####  IV-C4 Information about clusters

Besides using representative instances to reduce overplotting (R1) and provide
a visual guide to the most important structures of the embeddings,
ExplorerTree guides users through exploratory process using information about
the clusters. Figure 8 (6) presents an example of cluster information, showing
the content of the representative (left), the three most similar instances to
the representative (top), the similar but diverse data observations (bottom),
and the class distribution in the cluster. Notice that the color hue depicts
the classes, and bar height encodes the number of data observations in each
class.

Finally, users can use background images for the representative data points
(similarly as in Silva et al.’s [28] work). Such an approach can be useful
when the embedding has well-defined clusters, where users can rapidly see
patterns and assess similarity by looking at the representative images.

Figure 9: Using representative images as background.

####  IV-C5 Defining focus and context area

When requesting focus on a node, the focus area must be defined to distinguish
the focus from the context. Besides that, augmenting the focus area also
facilitates to distinguish the focus from the context. Let $x_{j}^{0}$ and
$y_{j}^{0}$ be the coordinates imposed by the embedding technique, such
translation is performed using the following equations:

$\begin{split}x_{j}^{i}=x_{j}^{i-1}+(x_{j}^{i-1}-x^{\prime})\times
f(|\mathscr{D}^{\prime}|)\times g(\parallel p_{j}-p^{\prime}\parallel)\\\
y_{j}^{i}=y_{j}^{i-1}+(y_{j}^{i-1}-y^{\prime})\times
f(|\mathscr{D}^{\prime}|)\times g(\parallel
p_{j}-p^{\prime}\parallel)\end{split}$ (1)

where $x^{\prime}$ and $y^{\prime}$ are the coordinates of $p^{\prime}$, which
is the reference/representative point when requesting for a focus;
$\mathscr{D}^{\prime}$ is the cluster that will receive the focus; $p_{j}$
represent the points in the current embedding and $x_{j}$ and $y_{j}$ their
coordinates.

Notice in Equation 1 the coordinates are interactively updated, i.e., they
depend on each request-focus operation held during exploration. Besides, $f$
and $g$ will also play an important role in the positioning of the points. $f$
is a function that linearly maps the clusters’ size ($|D^{\prime}|$) to a
value between $0.5$ to $4.0$. $g$ logarithmically maps the euclidean distance
($\parallel p_{j}-p^{\prime}\parallel\in[0,\mathscr{M}]$) between the
representative point in the request focus operation and the projection points
to a value between $0$ and $2.0$ – $\mathscr{M}$ is the max distance between
two points in the embedding. Therefore, $f$ tends to give more space area to
clusters with higher density while $g$ tends to reduce the “pushing out”
effect by giving less importance to clusters as they became far from the focus
area. Finally, $g$ also controls the comparing focus process, i.e., $g$ will
return $0$ for all the points that are at a distance greater than a limit
$\delta$ in pixels (we used $\delta=100$ in this work). Such control is
important since we argue that the focus area must remain constant for
comparison.

##  V Use Case - Finding meaningful activations of CNN filters

In this use case, we apply our technique to explore activation images of
convolutional filters of a CNN trained on the MNIST dataset, which we already
discussed in Section IV-C. Here, we aim to inspect discriminative and non-
discriminative filters [26, 25] of a convolutional layer. The well-known MNIST
[11] dataset has $50k$ training images, $10k$ validation images, and $10k$
test images. We trained a CNN composed by $28\times 28\times 1$ input image,
followed by a convolutional layer with $16$ $3\times 3$ filters, a
convolutional layer with $16$ $3\times 3$ filters, a $2\times 2$ max-pooling
layer (dropout $0.25$), a fully connected layer, a dense layer with $100$
neurons (dropout $0.5$), and a soft-max output layer with $10$ neurons. The
CNN was trained during $500$ epochs, achieving $0.9671$ of test accuracy.

We used the test set – where $600$ images were randomly selected from each
class – to generate each filter’s activations from the first convolutional
layer. Figure 10 illustrates the process of generating the activation images
for a digit. To analyze the dataset of activation images through similarity,
we used the same model to extract features, for instance, using the fully-
connected layer. Thus, the multidimensional matrix has $600\times 10\times
16=96000$ rows per $2034$ columns, where $600$ is the number of images
retrieved from each class, $10$ is the number of classes, and $16$ is the
number of filters.

Figure 10: For each image in testing set, $16$ activation images were
generated.

Figure 11 shows a scatter plot representation of the filters without sampling
next to the first level of ExplorerTree applied to the dataset, for $k=10$ and
$\alpha=1$. It is worth emphasizing that we are not visualizing the MNIST
dataset’s images but the activation images generated by the convolutional
layer of a CNN. We can see three major structures according to the colors that
depict $16$ different filters. Notice how our technique convey most of the
traditional projection structures while reducing overplotting imposed by
overlapping visual markers.

Figure 11: Projection of $96000$ of filter activations using colors depict the
filters. (1) Projection of each data point. (2) Projection using ExplorerTree.

Figure 12 illustrates the usefulness of using tool-tips. Users explore the
four structures to get more information regarding the clusters so that the
exploration task is more comfortable due to the guiding. Notice that we
manually separated the main structures with different color boundaries. Such
separation emphasizes the filters’ activations, i.e., the structures inside
the pink boundaries specify clusters that had more significant discriminative
activations – that contribute to the CNN classification tasks –, the
structures inside the blue and green boundaries activate more for the digit
borders. Lastly, the clusters inside the red boundary and some outliers closer
to them contain filters that did not activate at all. These filters – colored
by purple – are candidates for removal since they barely contribute to the CNN
accuracy. We notice that the two smaller and well-defined clusters are
composed of a limited number of filters. While class distribution helps us
assess the purity of the clusters, the similar and diverse instances show that
the cluster’s instances are similar to each other. In this case, we can see
that some filters are not playing a useful role in the classification (see (1)
and (2)). Moreover, other filters activate in some borders (see (5)).

Figure 12: Using cluster summaries to inspect the embedding. The summaries
emphasize four major structures. Clusters inside the pink boundary represent
filters that activate the most. Clusters inside the blue and green boundaries
represent filters that activated for some borders. Finally, clusters inside
the red boundary did not activate at all.

In Figure 13A) we select a cluster to inspect and request focus – indicated by
a pink arrow. Figure 12 shows the cluster positioned inside the blue boundary,
which tells that its instances correspond to filters that activate the digits
borders. Figure 13B) (left) show the cluster’s visual summary. The
representative instances of the selected cluster (1) are projected in (2),
where we also select a cluster for inspection (see embedding (3)). Notice that
as one goes more in-depth in the hierarchy, the number of representative
instances to be inspected tends to decrease. Figure 13B) (right) shows the
visual summary of the cluster indicated in the embedding (3). Comparing both
visual summaries, ExplorerTree shows different handwriting traits in the
second visual summary and more refined cluster although the main cluster (of
embedding (1)) corresponds to digit three activations. Finally, when one
reaches a leaf cluster as in (5), data instances are projected onto the plane
without overlapping, where users can inspect their content (in a new window),
as shown in Figure 13C).

Figure 13: Focus requesting operation. A) The embeddings from (1) to (5) show
request focus operation until one reaches a leaf node. Notice that by hovering
the leaf cluster, its instances are projected onto the plane. B) The visual
summaries help users to assess clusters’ content. C) Activation images of leaf
cluster.

After resolving the focus to the hierarchy’s first level (i.e., the inverse
process of Figure 13), we illustrate a cluster comparison. In Figure 14A) we
select a particular cluster to request focus, in which ExplorerTree projects
new representative data points onto the plane (B). Using the tool-tip to
inspect the cluster information, ExplorerTree shows seven classes inside the
cluster, where two of them have the most instances. Moreover, similar and
diverse instances show us that the cluster can be populated mainly by
instances of digit eight. After requesting more focus results in the
projection (3), ExplorerTree projects two representative data points in the
hierarchy’s third level. One of these representatives’ inspection shows that
it corresponds to a leaf node, whose data points are projected onto the plane
when recovering the mouse over the representative. These data points,
highlighted by a red box in the figure (not part of the visualization), and
their correspondent activation images indicated on the bottom of Figure 14B)
show the cluster homogeneity.

Figure 14: Using ExplorerTree to perform intra-cluster analysis. After
selecting a cluster of interest (A), a comparison between two subclusters (B.2
and C.4) is performed to investigate cluster homogeneity and similarity.
Through investigation of the fine-grained level of two subclusters, activation
images show that different convolutional filters result in the same activation
pattern.

To finish this study case, we use the functionality of comparing clusters in
different focus, as shown in Figure 15. In this case, two clusters that
present most data instances generated by the filters encoded as light green
were selected – a pink arrow indicates these clusters. After requesting focus
on these two clusters and generating the projection of Figure 15(B) and (C),
the summaries (shown on top) of the two inspected data representatives show
that such filter is responsible for detecting the digit borders. Notice that,
unlike in Höllt et al.’s [8] work, users can freely compare the information of
different clusters under focus since the tooltip’s information is related to
data points, not aggregated structures. By aggregating information using the
sampling technique and using visual summaries to show information about the
clusters, our technique can quickly inform the structures present in the
projection due to the facilitated cluster comparison. For instance, our
technique highlights the t-SNE ability to separate the digits even for the
same convolutional filter. Such characteristic is impressive since the filter
activated for only the digit borders, i.e., the different (even in small
amount) traits of digits one and four were sufficient to place these data
points apart.

Figure 15: Using the operation to compare clusters, ExplorerTree shows how
t-SNE can project data samples from the same filter according to the global
relationship.

##  VI Discussion and Limitations

Throughout the paper, we demonstrated how our approach could support pattern
discovery with reduced cognitive overload. Some of the strengths of our work
are: first, our methodology can be easily applied on embeddings generated by
any DR technique since it only requires points in $\mathbb{R}^{2}$; second,
the structure provided by our approach allows exploration of a large amount of
non-hierarchical projection techniques using the Focus+Context concept; third,
the representative selection processes used to define the hierarchy can reduce
visual clutter while providing meaningful guides for users – we compensate the
lost of information imposed by representative selection through visual
summaries of the clusters’ information.

One important thing to keep in mind is that to impose a hierarchical structure
on the dataset. We used clustering on the visual space, and a common approach
used extensively in the literature for conveying word clouds [23], images [6],
and so on. One problem with such an approach is the uncertainty in the
analysis due to distortions created by the dimensionality reduction process.
However, visualizing the result of clustering in the high-dimensional space
would increase the cognitive effort to interpret the layout [19] due to the
generation of fragmented clusters, especially when exploring hierarchical
structures. Although further research needs to address the problems to
communicate the distortions present in the hierarchy levels, choosing to ease
exploration instead of representing high fidelity to clustering seemed the
best option for us.

The sampling selection algorithm [14] employed to maintain the similarity and
structure relations imposed by the dimensionality reduction (DR) process, and
it accounts for the ability of the DR techniques to uncover the manifolds (if
there is any) and to trustfully represent the global and local relations
present in the dataset. Although this dependence on the DR technique may seem
like a bad feature, it is a good characteristic since it follows the advances
in dimensionality reduction research [16, 17].

##### Requirements

While our visual scalability requirements were applied only for scatter plot
representations of dimensionality reduction results, they can be extrapolated
to other scenarios since many visualization techniques suffer from visual
disorder and overplotting. For example, graph layouts may suffer from
overplotting of edges, and the parallel coordinates are a classic example of
how a significant number of data observations can reduce understanding trends
and cluster structures. We believe that our requirements for performing
analysis in such scenarios can help in design scalable visualization
approaches. While the techniques employed to accomplish the requirements may
differ from a technique to another – edge bundling could aggregate trends in
parallel coordinates. At the same time, other visual cues could inform about
outliers and important patterns. We believe these requirements are universal
when designing scalable visualizations.

##### Implementation

To accommodate other sampling and dimensionality reduction techniques, we
developed our tool1 as modular as possible. In this case, different
combinations of dimensionality reduction and sampling techniques can create
the ExplorerTree as shown in the Supplementary File. Besides, users will have
the opportunity to provide new visualization designs for the ExplorerTree
hierarchical structure since it was created based on a Java Spring API. The
overlap removal, representative selection, and ExplorerTree are different APIs
written in Java that can be used to plug in a graphical user interface – we
used D3.js [2] to create our visualization design.

##### Limitations

One limitation of our approach is the dimensionality reduction inability to
generate projections that trustfully represent data in high-dimensional
spaces. While it can be challenging to assess a projection quality without a
quality metric or any other layout enrichment strategy, our technique could
hide information about how bad feature spaces influenced the projection result
or simply the DR technique’s inefficiency. This limitation is related to some
visual cues that experts could rely on the projection to assess a layout,
which the sampling selection may hide. Although the visual summaries presented
here could help gain some information about clusters’ organization, we plan to
investigate visualization strategies to communicate cluster structures. A
second limitation of our approach could be the window space for visualizing
the projection, i.e., depending on the density of overlapping, dataset size,
and maximum size of each cluster, successive focus requests can deceive user
exploration.

##  VII Conclusions

Dimensionality reduction techniques are great tools for analyzing
multidimensional datasets. The scatter plots bring benefits according to the
rapid assessment of clusters and patterns. However, when the size of the
dataset grows, the visual metaphor does not visually scale well.

This work’s main contribution is the definition of a hierarchical exploration
approach for non-hierarchical embeddings to reduce visual clutter and allow
using the Focus+Context exploration concept. As a second contribution, we also
propose applying a sampling selection algorithm – developed to preserve class
boundaries and general structures of scatter plot representations of
dimensionality reduction techniques – on the creation of tree structures for
hierarchical exploration of multidimensional embeddings.

###  VII-A Future works

An interesting strategy is to allow users to define the first hierarchical
level to cluster data according to their needs, such as investigating clusters
based on gene expression in single-cell analysis applications. Moreover, given
that our approach can be easily changed to visualize other types of datasets,
Tags clouds could be used as a background to provide information about the
clusters when exploring document collections.

We also plan to investigate more about the visual scalability requirements we
proposed by formulating them in a framework.

## Acknowledgements

This work was supported by FAPESP (São Paulo Research Foundation), grants
#2016/11707-6, #2017/17450-0, #2018/17881-3, and #2018/25755-8.

## References

  * [1] K. Andrews, W. Kienreich, V. Sabol, J. Becker, G. Droschl, F. Kappe, M. Granitzer, P. Auer, and K. Tochtermann.  The infosky visual explorer: Exploiting hierarchical structure and document similarities.  Information Visualization, 1(3/4):166–181, Dec. 2002.
  * [2] M. Bostock, V. Ogievetsky, and J. Heer.  D3 data-driven documents.  IEEE Transactions on Visualization and Computer Graphics, 17(12):2301–2309, Dec. 2011.
  * [3] T. Dwyer, K. Marriott, and P. J. Stuckey.  Fast node overlap removal.  In P. Healy and N. S. Nikolov, editors, Graph Drawing, pages 153–164, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [4] M. Espadoto, R. M. Martins, A. Kerren, N. S. T. Hirata, and A. C. Telea.  Towards a quatitative survey of dimension reduction techniques.  IEEE Transactions on Visualization & Computer Graphics, 2019.
  * [5] E. Gansner and Y. Hu.  Efficient, proximity-preserving node overlap removal.  Journal of Graph Algorithms and Applications, 14(1):53–74, 2010\.
  * [6] E. R. Gansner, Y. Hu, and S. C. North.  Interactive visualization of streaming text data with dynamic maps.  J. Graph Algorithms Appl., 17:515–540, 2013.
  * [7] E. Gomez-Nieto, F. San Roman, P. Pagliosa, W. Casaca, E. S. Helou, M. F. Oliveira, and L. Nonato.  Similarity preserving snippet-based visualization of web search results.  IEEE Transactions on Visualization & Computer Graphics, 20(03):457–470, mar 2014.
  * [8] T. Höllt, A. Vilanova, N. Pezzotti, B. Lelieveldt, and H. Hauser.  Focus+context exploration of hierarchical embeddings.  Computer Graphics Forum (Proceedings of EuroVis 2019), 38(3), 2019\.
  * [9] P. Joia, F. V. Paulovich, D. Coimbra, J. A. Cuminato, and L. G. Nonato.  Local affine multidimensional projection.  IEEE Transactions on Visualization and Computer Graphics, 17(12):2563–2571, 2011.
  * [10] P. Joia, F. Petronetto, and L. Nonato.  Uncovering representative groups in multidimensional projections.  CGF, 34(3):281–290, 2015.
  * [11] Y. LeCun and C. Cortes.  MNIST handwritten digit database.  2010\.
  * [12] D. Lähnemann, J. Köster, and E. e. a. Szczurek.  Eleven grand challenges in single-cell data science.  Genome Biol, 31, 2020.
  * [13] L. J. P. Maaten and G. E. Hinton.  Visualizing high-dimensional data using t-sne.  Journal of Machine Learning Research, 9:2579––2605, 2008.
  * [14] W. E. Marcilio-Jr and D. M. Eler.  Sadire: a context-preserving sampling technique for dimensionality reduction visualizations.  J Vis, 2020.
  * [15] W. E. Marcílio-Jr, D. M. Eler, R. E. Garcia, and I. R. V. Pola.  Evaluation of approaches proposed to avoid overlap of markers in visualizations based on multidimensional projection techniques.  Information Visualization, 18(4):426–438, 2019.
  * [16] L. McInnes, J. Healy, and J. Melville.  UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction.  ArXiv e-prints, Feb. 2018.
  * [17] K. R. Moon, D. van Dijk, Z. Wang, S. Gigante, D. B. Burkhardt, W. S.-T. Chen, K. Yim, A. van den Elzen, M. J. Hirn, R. R. Coifman, N. B. Ivanova, G. Wolf, and S. Krishnaswamy.  Visualizing structure and transitions in high-dimensional biological data.  Nature Biotechnology, 37:1482 – 1492, 2019.
  * [18] T. Munzner.  Visualization Analysis and Design.  AK Peters Visualization Series. CRC Press, 2015.
  * [19] L. G. Nonato and M. Aupetit.  Multidimensional projection for visual analytics: Linking techniques with distortions, tasks, and layout enrichment.  IEEE Transactions on Visualization and Computer Graphics, page 1, 2018.
  * [20] F. V. Paulovich and R. Minghim.  Hipp: A novel hierarchical point placement strategy and its application to the exploration of document collections.  IEEE Transactions on Visulization and Computer Graphics, 14(6):1229–1236, 2008.
  * [21] F. V. Paulovich, L. G. Nonato, M. Rosane, and H. Levkowitz.  Least square projection: A fast high-precision multidimensional projection technique and its application to document mapping.  IEEE Transactions on Visulization and Computer Graphics, 3:564–575, 2008.
  * [22] F. V. Paulovich, C. T. Silva, and L. G. Nonato.  Two-phase mapping for projecting massive data sets.  IEEE Transactions on Visualization and Computer Graphics, 16(6):1281–1290, Nov. 2010.
  * [23] F. V. Paulovich, F. M. B. Toledo, G. P. Telles, R. Minghim, and L. G. Nonato.  Semantic wordification of document collections.  Comput. Graph. Forum, 31:1145–1153, 2012.
  * [24] N. Pezzotti, T. Höllt, B. Lelieveldt, E. Eisemann, and A. Vilanova.  Hierarchical stochastic neighbor embedding.  In Proceedings of the Eurographics / IEEE VGTC Conference on Visualization, EuroVis ’16, pages 21–30, Goslar Germany, Germany, 2016. Eurographics Association.
  * [25] N. Pezzotti, T. Höllt, J. van Gemert, B. Lelieveldt, E. Eisemann, and A. Vilanova.  Deepeyes: Progressive visual analytics for designing deep neural networks.  IEEE Transactions on Visualization and Computer Graphics (Proceedings of IEEE VAST 2017), 24(1):98 – 108, 2018.
  * [26] P. E. Rauber, S. G. Fadel, A. X. Falcao, and A. C. Telea.  Visualizing the hidden activity of artificial neural networks.  IEEE Transactions on Visualization and Computer Graphics, 23(1):101–110, Jan. 2017.
  * [27] B. Shneiderman.  The eyes have it: A task by data type taxonomy for information visualizations.  In Proceedings of the 1996 IEEE Symposium on Visual Languages, VL ’96, pages 336–, Washington, DC, USA, 1996. IEEE Computer Society.
  * [28] R. R. O. d. Silva, J. G. S. Paiva, G. P. Telles, C. E. A. Zampieri, F. P. Rolli, and R. Minghim.  The visual supertree: similarity-based multi-scale visualization.  Visual Computer, 2019.
  * [29] M. Steinbach, G. Karypis, and V. Kumar.  A comparison of document clustering techniques.  In KDD Workshop on Text Mining, 2000.
  * [30] H. Strobelt, M. Spicker, A. Stoffel, D. Keim, and O. Deussen.  Rolled-out wordles: A heuristic method for overlap removal of 2d data representatives.  Computer Graphics Forum, 31(3pt3):1135–1144, 2012.
  * [31] J. S. Vitter.  Random sampling with a reservoir.  ACM Trans. Math. Softw., 11(1):37–57, Mar. 1985.
  * [32] M. Williams and T. Munzner.  Steerable, progressive multidimensional scaling.  In Proceedings of the IEEE Symposium on Information Visualization, INFOVIS ’04, pages 57–64, Washington, DC, USA, 2004. IEEE Computer Society.