\section{Introduction}
\label{introduction}

\begin{figure*}[ht]
\vskip 0.1in
\begin{center}
\centerline{\includegraphics[width=0.86\textwidth]{images/mpart.png}}
\caption{Overview of Message Passing Adaptive Resonance Theory (MPART). The feature is extracted from the input sample, and then MPART continuously constructs a weighted graph based on ART network by learning distributions and topology of the input data. It uses a message passing method to infer the class label and estimate the uncertainty of the input sample for querying. A sample is queried according to the query selection strategy, and the label density of the topological graph is updated using the collected labels.}
\label{fig:mpart}
\end{center}
\vskip -0.2in
\end{figure*}

The recent success of deep learning in the field of visual object recognition and speech recognition is largely attributed to the massive amount of labeled data.
However, most of the data samples in the real-world are not labeled, so it takes a lot of time and effort to label and use them for deep learning.
In addition, in many countries, the collection and storage of medical data or data from personal robots are prohibited due to privacy concerns.
This burden impedes the widespread use of deep learning in real-world applications such as medical AI, home appliances and robotics, and separates the best solutions from becoming the best real-world solutions.

From this point of view, active learning is a promising field of machine learning.
The goal of active learning is to reduce the labeling cost by querying labels for only a small portion of the entire unlabeled dataset.
The query selection is made according to which samples are most beneficial, i.e. both informative and representative \cite{settles2009active}.
In most active learning algorithms, samples are selected from a large pool of data for querying \cite{settles2011theories, gal2017deep, sener2017active, beluch2018power}.
Once the queried data is labeled, it is accumulated in the training dataset and the entire model is trained again.
This process is repeated, typically assuming that all the data can be stored and the model can access the data again at any time.
In the aforementioned real-world problems, however, it is impossible to store a massive amount of data due to limited storage or privacy issues.
In addition, it is highly inefficient to repeatedly train the entire model with large data and review all the unlabeled data for querying whenever a new label is acquired.

In contrast, the active learning paradigm in an online manner does not assume that data samples can be accessed repeatedly but instead, the input data is given as a continuous stream \cite{lughofer2017line}.
This entails that uncertainty estimation of input samples and the decision of whether to query or not should be made online.
The result of querying and training with one sample affects the uncertainty of subsequent input samples.
Therefore, the model update should be done on-the-fly so that the new uncertainty distribution is estimated for the next query.
In such scenarios, it is difficult to select a query sample that is representative as well as informative because all data samples cannot be reviewed at the same time.
Moreover, since the labeling cost is expensive and the oracle is often unavailable, the number of queries may be limited \cite{hao2017second, zhang2018online, serrao2018active}.
Catastrophic forgetting is another issue to overcome when learning data online \cite{lee2017overcoming}.
This online active learning process, while more suitable for real-world problems, is therefore more challenging than offline active learning.

In this regard, we propose Message Passing Adaptive Resonance Theory (MPART) that addresses these problems in online active learning.
MPART learns the distribution of the input data without forgetting based on ART \cite{grossberg1987competitive} which keeps the existing knowledge stable when learning new data.
By utilizing a novel topology learning method on the learned distribution, MPART forms a topological graph using both labeled and unlabeled data.
In order to exploit the limited amount of labels acquired, our model uses a message passing method which compensates for the lack of class information by propagating the information within the topological graph.
Based on the learned topology, MPART can also select beneficial samples to query.
The entire learning process, depicted in Figure \ref{fig:mpart}, is performed in an online manner.
We evaluate our model in the online active learning environments, showing that MPART significantly outperforms competitive models.

The main contributions can be summarized as follows.
\begin{itemize}
\setlength\itemsep{0em}
\item We propose a novel method that learns the distribution of input data by continuously constructing a weighted topological graph based on the ART network.
\item We propose a message passing method for the graph to estimate the class labels in a semi-supervised manner and to select beneficial samples for querying.
\item We design an online active learning task where the frequency of query is limited and the total number of classes is unknown.
We validate the proposed model with various query selection strategies and datasets.
The results of the experiment show that our model significantly outperforms the competitive models in online active learning environments.
\end{itemize}

\section{Related Work}
\label{sec:related}
\textbf{Topology Learning. }
Topology learning aims to learn the structural properties and topological relations underlying the input data.
Additional knowledge such as class label or uncertainty can be obtained from the structural relationship using the topological information.
SOM \cite{kohonen1990self}, a type of artificial neural network, learns the topological properties of the input data using neighborhood function and competitive Hebbian learning (CHL).
This method is useful for dimension reduction of high-dimensional input data, but has a disadvantage in that it requires \textit{a priori} selection of a subspace.
GNG \cite{fritzke1995growing} and its derived models such as SOINN \cite{shen2006incremental} and E-SOINN \cite{shen2007enhanced} are incremental network models which can learn the topological relations of input data using the CHL.
There are also variants of ART networks (see Section \ref{sec:art} for details) which integrate new knowledge into its existing knowledge so that what has already been learned is not forgotten by the new learning.
Fuzzy ART-GL \cite{isawa2007fuzzy} uses Group Learning that creates connections between similar categories.
TopoART \cite{tscherepanow2010topoart} combines incremental clustering with topology learning, which enables stable online clustering of non-stationary input data.

\textbf{Semi-supervised Learning. }
Semi-supervised learning uses a small amount of labeled data with a large amount of unlabeled data to improve the performance of the model.
\cite{iscen2019label} and \cite{douze2018low} use the label propagation method to assign labels for unlabeled data using the nearby labeled data.
GAM \cite{stretcu2019graph} uses an agreement model that calculates the probability of two nodes sharing the same label on the graph.
EGNN \cite{kim2019edge} predicts the edge-labels of a graph to estimate the node-labels which are hard to be inferred directly in few-shot classification tasks.
However, most of these methods are not suitable for online learning, because they need predefined topological information or repeated usage of whole training data.
LPART \cite{kim2020label} uses online label propagation on the ART network trained in a semi-supervised manner to overcome this issue, but the information conveyed between the nodes is limited due to insufficient topological information.
MPART, on the other hand, addresses these problems by explicitly learning the topology of the input data.

\textbf{Online Active Learning. }
The goal of online active learning is not only to reduce annotation costs, but also to continuously expand existing knowledge by exploring new information.
OASIS \cite{goldberg2011oasis} is a Bayesian model that combines online active learning and semi-supervised learning methods.
SOAL \cite{hao2017second} and OA3 \cite{zhang2018online} utilize second-order information for online binary classification under limited query budgets.
While these methods are successful in binary classification, they cannot handle the increasing diversity of classes due to the assumption of a fixed number of classes.
Other methods \cite{loy2012stream, weigl2016improving} employ consensus of models to better estimate uncertainty.
However, using multiple models incurs large computational costs, making them less scalable for complex tasks.
The most closely related work to ours is \cite{shen2011incremental}, enhancing the SOINN to enable online active semi-supervised learning.
The proposed A-SOINN, however, selects the queries among representative values of clusters, which might be difficult for the oracle to recognize.
Moreover, since this model stores only a single label in a cluster, it cannot handle the mixture of classes within the cluster and is susceptible to noise.
Our model solves these problems by querying the input itself and using a distribution for labels in each node.

\section{Background}
\label{sec:art}
Each related work shows a high potential to solve real-world problems in various domains, and motivates our idea of online active semi-supervised learning.
In this section, we briefly introduce the ART networks and our motivations.

\subsection{ART Networks}

Adaptive Resonance Theory (ART), inspired by brain information processing mechanisms, is an unsupervised learning method for pattern recognition \cite{grossberg1987competitive}.
The basic principle of ART is that object recognition is achieved by the interaction of `bottom-up' sensory information and `top-down' expectations.
We refer to any neural network model based on ART as \textit{ART network}.
ART networks integrate new knowledge into the entire knowledge so that what has already been learned is not forgotten by new learning.

A basic ART network consists of two layers fully-connected to each other: an input layer and an output layer.
As an input vector enters the input layer, it activates each node in the output layer according to the connection weight.
Using the choice function with the activation values, the closest matching node is selected as a winner.
Then, the fitness of the input to the winner node is calculated using the match function.
If the fitness is greater than a vigilance parameter $\rho$, the input vector is integrated into the winner, updating the associated weight.
Otherwise, a new node is created with a weight set equal to the input vector.
With these mechanisms, ART networks can categorize incoming data online without forgetting.
There are various ART networks such as Fuzzy ART \cite{carpenter1991fuzzy}, Gaussian ART \cite{williamson1996gaussian} and Hypersphere ART \cite{anagnostopoulos2000hypersphere}.
We use Fuzzy ART as our backbone model, which incorporates fuzzy logic to enhance generalizability.
Fuzzy ART will be described in Section \ref{sec:topology} along with MPART's topology learning method.

\subsection{Motivations}
Due to the nature of ART, the ART networks can efficiently learn new data by updating only a part of the model.
In addition, it does not need to predefine the structure and size of the model, which allows flexible self-organization of irregular and complex data distributions.
These properties play an important role in online learning, so we chose an ART network as a backbone model of MPART.

Moreover, in online active learning scenarios where data cannot be stored, it is difficult to select a representative sample for querying because all data samples cannot be reviewed simultaneously.
We address this problem by learning the topology of input data.
There is also an ART network called TopoART that can learn the topology.
However, TopoART, in which only the winner and the runner-up node are connected, cannot effectively represent the relationships between nodes.
In TopoART, the strength of the edge continuously increases as the data is learned, so a proper normalization method is required to use the edge information for message passing on the topological graph.
Therefore, we propose a novel method to learn the topology and utilize it for message passing to select queries and predict labels.

\section{Methods}
MPART learns the distribution and topology of input data to construct a topological graph online.
Then, class prediction and uncertainty estimation of the input data are performed using a message passing method on the graph.
The estimated uncertainty is used to select and query useful samples.
The entire process of MPART is described in Algorithm \ref{alg:mpart}.
In the following sections, we describe the topology learning, message passing, and active querying methods.

\subsection{Topology Learning}
\label{sec:topology}
\textbf{Node Formation. }
We first extract representation vector $r_t \in [0,1]^{n_r}$ from the input data $x_t$ using the pre-trained BYOL \cite{grill2020bootstrap} and Parametric UMAP \cite{sainburg2020parametric} (see Section \ref{sec:featext} for details).
As in Fuzzy ART, the representation vector $r_t$ is complement coded to $I_t = [r_t, \vec{1} - r_t]$ in order to avoid proliferation of prototypes \cite{carpenter1991fuzzy}.
With this, we can measure the similarity between the input and the category node $j$ using the match function $M_j$ and the choice function $T_j$ as follows.
\begin{equation} \label{eq:activation}
M_j(I_t) = \frac{\left\| I_t \wedge w_j \right\|_1}{\left\| I_t \right\|_1}, \qquad
T_j(I_t) = \frac{\left\| I_t \wedge w_j \right\|_1}{\alpha + \left\| w_j \right\|_1}
\end{equation}
Here, $\wedge$ is the element-wise minimum operator, $\| \cdot \|_1$ is the L1 norm, and $\alpha > 0$ is a choice parameter.
A node $j$ becomes \textit{activated} by $I_t$ if $M_j(I_t)$ is greater than or equal to a vigilance parameter $\rho \in (0, 1)$.
When there are multiple activated nodes, or \textit{co-activated nodes}, one with the highest $T_j(I_t)$ is chosen as a \textit{winner} denoted by $J_t$.
In case only one node is activated, we also refer to that node as the winner $J_t$.
We update $w_{J_t}$ with a learning rate $\beta \in (0, 1]$, and increase $d_{J_t}$ by 1 as follows.
\begin{equation} \label{eq:update}
\begin{gathered}
w_{J_t}^{new} = \beta (I_t \wedge w_{J_t}^{old}) + (1 - \beta) w_{J_t}^{old} \\
d_{J_t}^{new} = d_{J_t}^{old} + 1
\end{gathered}
\end{equation}
If none is activated, a new node $J_t$ is created with an initial weight $w_{J_t}=I_t$ and a winning count $d_{J_t}=1$.

\textbf{Edge Formation. }
In addition to the node formation, edges between the co-activated nodes are developed.
Unlike SOINN or TopoART in which only the winner and the runner-up node are connected, we connect the winner to every co-activated node to better represent more complex topology of multiple nodes.
For an edge connecting nodes $i$ and $j$, its count $c_{ij}$ is set as the number of times $i$ and $j$ have been co-activated.
The edge weight $e_{ij}$ is defined as a ratio of $c_{ij}$ to the sum of winning counts of incident nodes $i$ and $j$ as shown in Equation \ref{eq:edge_weight}.
\begin{equation} \label{eq:edge_weight}
e_{ij} = \frac{c_{ij}}{d_i + d_j}
\end{equation}
The weight $e_{ij}$ well describes the correlation between $i$ and $j$.
If the two nodes have never been co-activated, $e_{ij}$ is 0.
As they get co-activated more frequently, $e_{ij}$ grows larger; it reaches the maximum value of 1 if $i$ and $j$ have been co-activated whenever one of them was the winner.
Since $e_{ij}$ is bounded to $[0, 1]$, it can be used to adjust the degree of message passing without normalization.
The edge formation does not interrupt the node formation, so the properties of the underlying ART network are also preserved.

\begin{algorithm}[t]
\caption{The MPART algorithm}
\label{alg:mpart}
\begin{algorithmic}

    \STATE $V \leftarrow \{\}, C \leftarrow \{\}$
    \FOR{$x_t$ {\bfseries in} input data stream}
        \STATE $r_t \leftarrow \texttt{DimensionReduction}(x_t)$
        \STATE $I_t \leftarrow [r_t, \overrightarrow{1} - r_t]$
        \STATE $A \leftarrow \{\}$
        \FOR{$j$ {\bfseries in} $1, \ldots, |V|$}
            \STATE $M_j \leftarrow \|I_t \wedge w_j\|_1 \; / \; \|I_t\|_1$
            \STATE $T_j \leftarrow \|I_t \wedge w_j\|_1 \; / \; (\alpha + \|w_j\|_1)$

            \IF{$M_j \geq \rho$}
                \STATE $A \leftarrow A \cup \{j\}$
            \ENDIF
        \ENDFOR

        \IF{$A$ is empty}
            \STATE $J_t \leftarrow |V| + 1, \quad V \leftarrow V \cup \{J_t\}$
            \STATE $c_{J_{t}v} \leftarrow 0,\; c_{vJ_{t}} \leftarrow 0 \quad \forall v \in V - \{J_t\}$
            \STATE $q_{J_t}(y) \leftarrow 0 \quad \forall y \in C$
            \STATE $w_{J_t} \leftarrow I_t, \quad d_J \leftarrow 1$
        \ELSE
            \STATE $J_t \leftarrow \argmax_{j \in A}(T_j)$
            \STATE $c_{J_{t}v} \leftarrow c_{J_{t}v} + 1,\; c_{vJ_{t}} \leftarrow c_{vJ_{t}} + 1 \quad \forall v \in A - \left\{J_t\right\}$ \\
            \STATE $w_{J_t} \leftarrow \beta (I_t \wedge w_{J_t}) + (1 - \beta) w_{J_t}$
            \STATE $d_{J_t} \leftarrow d_{J_t} + 1$
        \ENDIF

        \STATE $q_{J_t}^{(L)}, d_{J_t}^{(L)} \leftarrow \texttt{MessagePassing}(J_t, c, d, q)$
        \STATE $p_{t}, \hat{y} \leftarrow \texttt{NodeClassification}(q_{J_t}^{(L)})$
        \STATE $s_{t} \leftarrow \texttt{UncertaintyEstimation}(p_{t}, q_{J_t}^{(L)}, d_{J_t}^{(L)})$

        \IF{$s_{t}$ satisfies query condition}
            \STATE $y_t \leftarrow \texttt{QueryLabel}(x_t)$
            \STATE $q_{J_t}(y_t) \leftarrow q_{J_t}(y_t) + 1$
            \STATE $C \leftarrow C \cup \{ y_t \}$
        \ENDIF
    \ENDFOR
\end{algorithmic}
\end{algorithm}

\subsection{Message Passing}
\label{sec:message_passing}
Nodes formed in MPART possess additional information vectors such as class probabilities or uncertainty measures for better inference and querying.
To compensate for the lack of information, we use message passing to aggregate the information within the topological graph.
Before describing the procedure, we first define a notion of \textit{neighbors}.
Given nodes $i$ and $j$, if the shortest path from $i$ to $j$ exists and its length is $l$, then we say $j$ is an $l$-hop neighbor of $i$.
Any node is a 0-hop neighbor to itself.
A set of all $l$-hop neighbors of $i$ is denoted as $\mathcal{N}_i^{(l)}$; a set of direct neighbors $\mathcal{N}_i^{(1)}$ will also be written as $\mathcal{N}_i$.
We further denote an $l$-hop neighborhood $\mathcal{N}_i^{(0:l)}$ as a union of $\mathcal{N}_i^{(0)}, \ldots, \mathcal{N}_i^{(l)}$.

To illustrate message passing, let $X$ denote an information vector (or scalar) of interest such as winning count $d$ or label density $q$ (will be described later).
A single-layer message passing on the target node $i$ updates $X_i$ by adding $X_j$ of every neighboring node $j \in \mathcal{N}_i$, weighted by $e_{ij}$ and discounted by a propagation rate $\delta \in [0, 1]$.
Multi-layer message passing is achieved by performing the single-layer message passing recursively, aggregating the information from broader neighboring area.
The recursive procedure for $L$-layer message passing targeted at the winner $J_t$ can be formalized as Equation \ref{eq:aggregation}, where $X_{i}^{(l)}$ denotes the $l$-layer aggregated information and $X_{i}^{(0)}$ is set as $X_{i}$.
\begin{equation} \label{eq:aggregation}
\begin{gathered}
X_{i}^{(l)} = X_{i}^{(l-1)} + \delta \sum_{j \in \mathcal{N}_i} e_{ij} X_{j}^{(l-1)}, \ \forall i\in \mathcal{N}_{J_t}^{(0:L-l)}
\end{gathered}
\end{equation}
We finally obtain the $L$-layer aggregated information $X_{J_t}^{(L)}$ by applying this update for $l$ from 1 to $L$.
Note that we only have to consider nodes in $\mathcal{N}_{J_t}^{(0:L-l)}$ when performing the $l$-th layer update since the information outside this set will not be propagated to $J_t$ within the remaining $(L-l)$ updates.
This reduces the computational cost compared to when reviewing all the nodes in the graph.

\textbf{Node Classification. }
\iffalse
Node classification is the process of predicting the labels of the samples represented by the node.
When MPART gets the label $y_t$ of the input sample $x_t$ from the oracle, it increases the corresponding value of the winner node's label density $q_{J_t}(y_t)$ by 1.
When a new node is created, $q_{J_t}(y)$ is initialized to zero for all $y \in C$ before updating $q_{J_t}(y_t)$.
At this time, if the label of the new class is observed, the known class set $C$ is also updated.
The number of known classes $|C|$ increases according to the label of the new class received from oracle, so if new class label $y_{new}$ is added, $q_j(y_{new})$ for all nodes $j$ is initialized to zero before updating $q_{J_t}(y_{new})$.
The class of a node can be evaluated not only by the labels of the node which the sample belongs to, but also the labels of the surrounding nodes even in the case where a rare label is given.
Therefore, we perform $L$-layer message passing for label density $q_{J_t}(y)$ which is a vector containing the cumulative value of the node's label (see Section \ref{sec:query} for details).
Then, the class probability distribution of input $x_t$ is obtained using the aggregated label density as shown in Equation \ref{eq:classification}.
\begin{equation} \label{eq:classification}
\begin{small}
\begin{gathered}
q_{i}^{(l)}(y) = q_{i}^{(l-1)}(y) + \delta \sum_{j \in \mathcal{N}_i} e_{ij} q_{j}^{(l-1)}(y), \ \forall i\in \mathcal{N}_{J_t}^{(0:L-l)} \\
p_{t}(y) = \dfrac{q_{J_t}^{(L)}(y)}{\sum_{y' \in C}q_{J_t}^{(L)}(y')}
\end{gathered}
\end{small}
\end{equation}
$p_{J_t}(y)$ is the probability that this node belongs to class $y$ in last layer $L$.
We infer the class $\hat{y}$ of $x_t$ as the label with the highest class probability.
\fi
MPART infers the class of input $x_t$ by aggregating the class information near the winner $J_t$.
The class information $q_i$ of a node $i$, called the label density, is a distribution over a set of known class labels $C$ and indicates how probable the node belongs to each class.
We use distributions rather than single values to cope with situations where one node represents samples of different classes.

Before receiving any label, each $q$ is set to an empty distribution, i.e. an empty vector.
As a new label is received and added to the label set $C$, every $q$ is expanded by one dimension (zero-valued) which will be responsible for that label.
For new nodes, label densities are set to zero vectors of dimension $|C|$.
When a label $y_t$ is provided with an input $x_t$, the corresponding density value in the winner ${J_t}$, i.e. $q_{J_t}(y_t)$, increases by 1.
This increment also applies if the label was obtained via active querying.
Since labels are provided rarely, we perform $L$-layer message passing for $q$ to alleviate the deficiency.
The aggregated label density $q_{J_t}^{(L)}$ contains class information of neighboring nodes, so it is representative and robust to noise.
We obtain the class probability distribution $p_t$ by normalizing it as Equation \ref{eq:classification}.
\begin{equation} \label{eq:classification}
p_{t}(y) = \dfrac{q_{J_t}^{(L)}(y)}{\sum_{y' \in C}q_{J_t}^{(L)}(y')}
\end{equation}
If $q_{J_t}^{(L)}$ is a zero vector, we set $p_t$ to a uniform distribution.
The label of the input is inferred as one with the highest probability.
This distribution is also used to estimate the label uncertainty of a node, as described in the next section.

\subsection{Active Querying}
\label{sec:query}

\begin{figure}[t]
\vskip 0.05in
\begin{center}
    \centerline{\includegraphics[width=0.95\columnwidth]{images/decision_boundary.png}}

    \caption{Example queries (black boxes) selected online according to the query selection score, for a simple binary classification of 2,000 samples each (blue and orange). (a) The first 40 queries are distributed relatively evenly, while (b) the latter 40 queries are concentrated around the decision boundary.}

\label{fig:decision_boundary}
\end{center}
\vskip -0.2in
\end{figure}

We combine the uncertainty-based sampling with density-weighted method for query selection.
The uncertainty is measured per node using the label density and weighted by distribution density of data to produce the selection score.
This score can be used with various selection strategies, including those suggested in Section \ref{sec:strategy}.

\textbf{Uncertainty Estimation. }
We use two kinds of uncertainty measures as in \cite{kim2020label}.
The first uncertainty $u_e$ indicates the insufficiency of class information accumulated in each node.
It is determined by the sum of label density values over all known classes.
As more labels are input or more times of message passing are performed, $u_e$ decreases as the sum of densities increases.
For an input sample $x_t$, $u_e$ is defined as that of the winner $J_t$ as in Equation \ref{eq:epistemic}, with a sensitivity constant $k_e > 0$ and $\tanh$ for clamping.
\begin{equation} \label{eq:epistemic}
u_{e} = 1 - \tanh\left(k_e \sum_{y \in C} q_{J_t}^{(L)}(y)\right)
\end{equation}
The second uncertainty $u_{a}$ measures the class impurity, i.e. how many classes are mixed within a node.
We can use the normalized entropy of class probability, while setting $u_{a}$ to 0 when no more than one label is observed.
\begin{equation} \label{eq:aleatoric}
u_{a} =
\begin{cases}
\dfrac{-\sum_{y \in C} p_{t}(y)\log p_{t}(y)}{\log(|C|)} ,& \text{if } |C| > 1 \\
0,& \text{otherwise}
\end{cases}
\end{equation}

The two quantities, $u_e$ and $u_a$, can be viewed as epistemic and aleatoric uncertainties respectively, in that $u_e$ results from insufficient observation while $u_a$ arises due to ambiguity in the input data.
These uncertainties are complementary when used for query selection, since $u_e$ plays an important role in the early stage of learning while $u_a$ is more crucial after enough number of labels have been acquired.
We combine them with a weight $\tau \in [0, 1]$ to get a query selection score $u_{t}$ as shown in Equation \ref{eq:u_sum}.
Figure \ref{fig:decision_boundary} illustrates that the distribution of queries selected using $u_t$ tends to be sparse at first, but concentrated near the decision boundary as the learning progresses.
\begin{equation} \label{eq:u_sum}
u_{t} = \tau u_{e} + (1-\tau) u_{a}
\end{equation}

\textbf{Density-Weighted Method. }
Beneficial samples should be representative as well as informative \cite{huang2014active}.
Both uncertainties $u_{a}$ and $u_{e}$ are considered representative because they are derived from label density $q_{J_t}^{(L)}$ aggregated from surrounding nodes.
Additionally, we aggregate the winning count $d_i$ to select representative samples, which represents the distribution density of the input data.
Finally, the density-weighted query selection score $s_{t}$ using data density $d_{J_t}^{(L)}$ is defined as in Equation \ref{eq:score}.
\begin{equation} \label{eq:score}
\begin{gathered}
d_{i}^{(l)} = d_{i}^{(l-1)} + \delta \sum_{j \in \mathcal{N}_i} e_{ij} d_{j}^{(l-1)}, \ \forall i\in \mathcal{N}_{J_t}^{(0:L-l)} \\
s_{t} = \tanh\left( k_d \cdot d_{J_t}^{(L)} \right) \cdot u_{t}
\end{gathered}
\end{equation}
Here, $k_d$ is a positive constant for sensitivity.
If the density-weighted query selection score $s_{t}$ of the input $x_t$ satisfies the condition according to the query selection strategy (see Section \ref{sec:strategy} for details), the model immediately queries the oracle to get a label $y_t$.
An example of training results using the CIFAR-10 dataset is visualized in Figure \ref{fig:topology_visualization}.

\section{Experiments}
\label{sec:experiment}

We investigated the effectiveness of MPART in online active learning scenarios.
To do this, we designed a task described in Section \ref{sec:task} and evaluated the performance of the model with various settings.
We also compared the performance to that of two competitive models: LPART \cite{kim2020label} and A-SOINN \cite{shen2011incremental}.
For statistical significance, we repeated each experiment 30 times.

The propagation rate $\delta$ for message passing was set to 0.1, and the parameters $k_e$, $\tau$ and $k_d$ used for the score calculation were set to 1.0, 0.7 and 0.01, respectively.
For other parameter settings, please refer to the Appendix.

\subsection{Task}
\label{sec:task}
We set up an online active learning task to imitate real-world scenarios where only a few number of annotations are possible and the data cannot be stored.
There is a previous study that has proposed this kind of task for stream-based selective sampling \cite{attenberg2011online}.
In this previous work, the query budget is set as the maximum number of queries allowed in a fixed input period instead of the total number of queries throughout the training.
Similarly, we constrained the model to query for certain number of times within each period, assuming that the oracle can annotate only a few samples in a period.

The basic goal of this task is to perform multi-class classification, where the number of classes is unknown in advance.
The input samples are provided sequentially as a stream, i.e. one after another, and cannot be stored or reused.
The whole training dataset is initially unlabeled and the model can inquire the oracle about the labels of a small number of inputs.
Specifically, the number of queries is limited to a fixed budget $B$ within a period of $W$ consecutive inputs.
We denote such constraint as a query frequency $B/W$.
The final classification performance is evaluated on the hold-out test dataset.

For experiments, we used four kinds of datasets with different distributions: Mouse retina transcriptomes \cite{macosko2015highly, polivcar2019opentsne}, Fashion MNIST \cite{xiao2017fashion}, EMNIST Letters \cite{cohen2017emnist}, and  CIFAR-10 \cite{krizhevsky2009learning}.
The datasets consist of 12, 10, 26, and 10 classes, respectively.
The budget $B$ was set to 1 or 2, and the period $W$ was set to 100, 500, 1,000 or 2,000.
For model training, we only used 10,000 randomly sampled data from the training split per trial.
This is to push the situation to an extreme; with 1/500 or less query frequency, the model will not be able to receive labels for some classes unless it successfully selects and queries all the samples from different classes.

\begin{figure}[t]
\centering
    \centerline{\includegraphics[width=0.87\columnwidth]{images/explorer_query.jpg}}

    \caption{The visualization of result on the CIFAR-10 dataset for 1/500 query frequency and $L=3$ using `Explorer' strategy. The color of the dots represent the label of input data, and the intensity of the topological graph represents the density of nodes and edges. The distribution of the queried samples is spread evenly.}
\label{fig:topology_visualization}
\vskip -0.1in
\end{figure}

\begin{figure*}[ht]
\centering
    \subfigure[\footnotesize Mouse retina transcriptomes]{\includegraphics[width=0.24\textwidth]{images/result_graph1.png}}
    \hfill
    \centering
    \subfigure[\footnotesize Fashion MNIST]{\includegraphics[width=0.24\textwidth]{images/result_graph2.png}}
    \hfill
    \centering
    \subfigure[\footnotesize EMNIST Letters]{\includegraphics[width=0.24\textwidth]{images/result_graph3.png}}
    \hfill
    \centering
    \subfigure[\footnotesize CIFAR-10]{\includegraphics[width=0.24\textwidth]{images/result_graph4.png}}
    \caption{Classification accuracy according to the number of training samples. The number of layer $L=3$ and 1 / 500 query frequency were used for MPART. The order of input samples was shuffled regardless of the class. Note that, for the EMNIST Letters dataset, the models can collect up to 20 class labels out of a total of 26 class labels after all training is complete.}
\label{fig:evolve}
\end{figure*}

\subsection{Query Selection Strategy}
\label{sec:strategy}

\textbf{Random. }
A random query is selected from a sequence of inputs.
This is a baseline and works as an ablated version of active selection strategies.
It is equivalent to randomly providing labels for some inputs, so MPART learns in an online semi-supervised manner when using this strategy.

\textbf{Memory. }
This can only be used at 1/$W$ query frequency, assuming the model has a memory that can store at most one sample.
During each query period, one sample with the maximum  density-weighted query selection score $s_{t}$ is stored and queried at the end of the period.
By using this strategy, the model can select the most beneficial sample.

\textbf{Explorer. }
`Explorer' assumes the most stringent situation where the learning agent cannot store any input sample.
In this situation, the learning agent selects $B$ samples online for each query period $W$, and cannot change the sample once selected.
Therefore, the chance of selecting an beneficial sample decreases as the exploration gets longer because of the fixed query selection period.
In this strategy, the uncertainty distribution of the data explored so far is continuously estimated to solve the exploration-exploitation dilemma \cite{berger2014exploration}.
The random variable of the uncertainty distribution $\mathcal{S}_n$ is assumed to follow the normal distribution $\mathcal{S}_n \sim N(\mu_{n}, \sigma_{n}^2)$, where $n$ is the number of accumulated samples since the previous query.
The parameters $\mu_{n}$ and $\sigma_{n}^2$ are calculated as the sample mean and variance of $s_t$ as in Equation \ref{eq:score_muvar}.
\begin{equation} \label{eq:score_muvar}
\begin{split}
\mu_{n} & = (1 - n^{-1}) \mu_{n-1} + n^{-1}  s_{t} \\
\sigma_{n}^2 & = (1 - n^{-1})  \sigma_{n-1}^2 + n^{-1} (\mu_{n} - s_{t})^2
\end{split}
\end{equation}

An input sample is considered beneficial if its density-based query selection score is likely to be greater than that of most unseen samples.
To be more concrete, we select the $t$-th sample if Equation \ref{eq:explorer_criterion} is satisfied.
Here, $Binom$ denotes a probability mass function of a binomial distribution, $F_{\mathcal{S}_n}(\cdot)$ is the cumulative density function of $\mathcal{S}_n$, $t_p$ is the time from the start of the current period, and $b$ is the number of remaining query budget in the current period.
If $\sigma_{n}=0$, we set $F_{\mathcal{S}_n}(s_{t})$ to 0.5.
\begin{equation} \label{eq:explorer_criterion}
\begin{gathered}
\sum_{m=0}^{b-1} Binom \left(m ; W - t_{p}, 1-F_{\mathcal{S}_n}(s_{t}) \right) > 0.5
\end{gathered}
\end{equation}
When a query is selected, $b$ is reduced by 1, and both $\mu_{0}$ and $\sigma_{0}$ are reset to 0.
If $b$ is 0, no query is performed until the end of the period, and $b$ is reset to $B$ when a new period starts.
With the `Explorer' strategy, the model can efficiently and effectively choose the useful samples by predicting the beneficialness of the unseen ones.

\subsection{Feature Extraction \& Dimension Reduction}
\label{sec:featext}
We projected the input data into 4-dimensional embedding space using the pre-trained Parametric UMAP \cite{sainburg2020parametric} for each dataset.
The embedding space was mapped to $[0,1]^4$ using min-max normalization on training data.
Prior to projection, we extracted 2048-dimensional feature vectors from CIFAR-10 using the BYOL \cite{grill2020bootstrap} pre-trained with the ImageNet dataset \cite{deng2009imagenet}.
Parametric UMAP is suitable for use in semi-supervised learning by capturing structure in unlabeled data to provide the embeddings for unseen data online which can be clustered properly.
We trained Parametric UMAP using 30\% of the training data for each dataset, and the rest was used for MPART training.
Note that no labeled data was used until this step.

\begin{table*}[t]
    \caption{Comparison of classification accuracy (mean $\pm$ std) between our model (MPART) and the competitive models according to the query selection strategy. We also report classification accuracy of MPART depending on whether density-weighted query selection score (DS) is applied or not. The number of layers $ L = 3 $ for message passing of MPART was used. (unit : \%)}
\label{tab:ablation_results}
\begin{center}
\begin{small}
\begin{sc}

        \begin{tabular}{c c c c c c}
        \toprule
        Query Selection & \multirow{2}{*}{Model} & Mouse retina & Fashion & EMNIST & \multirow{2}{*}{CIFAR-10} \\

        Frequency & & transcriptomes & MNIST & Letters &  \\
        \midrule
\multirow{4}{*}{Fully Supervised} & MLP             & 94.0$\pm$1.7 & 71.9$\pm$1.6 & 50.9$\pm$2.0 & \textbf{75.1}$\pm$1.7 \\
                                  & LPART           & \textbf{97.2}$\pm$0.1 & 73.2$\pm$0.3 & 60.2$\pm$0.4 & 74.2$\pm$0.3 \\
                                  & A-SOINN         & 94.2$\pm$1.5 & 66.5$\pm$1.5 & 47.6$\pm$1.6 & 65.5$\pm$1.7 \\
                                  & MPART & \textbf{97.2}$\pm$0.1 & \textbf{73.3}$\pm$0.2 & \textbf{60.7}$\pm$0.3 & 74.3$\pm$0.3 \\
        \midrule
                          & LPART                      & 82.5$\pm$7.5 & 41.1$\pm$6.4 & 14.7$\pm$2.6 & 23.8$\pm$5.3 \\
                          & A-SOINN                    & 88.1$\pm$13.0 & 45.2$\pm$7.0 & 16.9$\pm$4.1 & 37.7$\pm$6.8 \\
                          \cmidrule(r){2-6}
\multirow{3}{*}{1 / 1000} & MPART-Random               & 81.0$\pm$7.0 & 42.8$\pm$8.5 & 17.1$\pm$3.1 & 40.9$\pm$8.1 \\
                          & MPART-Memory               & \textbf{93.3}$\pm$3.3 & \textbf{53.6}$\pm$4.8 & \textbf{26.1}$\pm$2.8 & \textbf{55.5}$\pm$4.6 \\
                          & MPART-Explorer             & 91.8$\pm$4.0 & 53.5$\pm$5.4 & 25.4$\pm$2.4 & 55.4$\pm$3.7 \\
                          \cmidrule(r){2-6}

                          & MPART-Memory (w/o DS) & 90.5$\pm$5.6 & 51.4$\pm$5.6 & 19.8$\pm$3.5 & 44.9$\pm$7.0 \\

                          & MPART-Explorer (w/o DS)    & 87.2$\pm$8.1 & 49.9$\pm$6.9 & 18.2$\pm$3.4 & 44.1$\pm$6.7 \\

\midrule
                          & LPART                      & 89.0$\pm$6.3 & 54.6$\pm$5.9 & 21.0$\pm$3.4 & 34.0$\pm$4.7 \\
                          & A-SOINN                    & 91.0$\pm$5.4 & 50.3$\pm$6.0 & 25.6$\pm$4.8 & 44.2$\pm$7.0 \\
                          \cmidrule(r){2-6}
\multirow{3}{*}{1 / 500}  & MPART-Random               & 88.3$\pm$4.4 & 54.3$\pm$7.6 & 23.4$\pm$3.8 & 50.9$\pm$5.2 \\
                          & MPART-Memory               & 94.5$\pm$1.1 & \textbf{62.0}$\pm$4.4 & 35.6$\pm$2.5 & \textbf{59.7}$\pm$3.4 \\
                          & MPART-Explorer             & \textbf{94.6}$\pm$0.9 & 59.4$\pm$5.2 & \textbf{36.0}$\pm$2.9 & 59.2$\pm$3.3 \\
                          \cmidrule(r){2-6}

                          & MPART-Memory (w/o DS)      & 91.9$\pm$3.4 & 51.7$\pm$5.8 & 28.7$\pm$3.3 & 52.2$\pm$5.4 \\

                          & MPART-Explorer (w/o DS)    & 92.1$\pm$3.4 & 53.9$\pm$4.8 & 29.2$\pm$3.8 & 51.6$\pm$6.6 \\

\midrule
                          & LPART                      & 94.6$\pm$1.5 & 64.4$\pm$2.0 & 38.0$\pm$2.3 & 62.0$\pm$2.9 \\
                          & A-SOINN                    & 91.5$\pm$7.0 & 55.7$\pm$6.8 & 29.9$\pm$4.9 & 50.9$\pm$7.9 \\
                          \cmidrule(r){2-6}
\multirow{3}{*}{1 / 100}  & MPART-Random               & 94.8$\pm$1.2 & 66.8$\pm$2.0 & 43.6$\pm$3.2 & 63.4$\pm$2.6 \\
                          & MPART-Memory               & \textbf{95.9}$\pm$0.5 & \textbf{67.7}$\pm$1.6 & \textbf{47.9}$\pm$1.6 & \textbf{67.4}$\pm$1.5 \\
                          & MPART-Explorer             & \textbf{95.9}$\pm$0.9 & \textbf{67.7}$\pm$1.3 & 47.5$\pm$1.5 & 66.8$\pm$1.4 \\
                          \cmidrule(r){2-6}

                          & MPART-Memory (w/o DS)      & 95.0$\pm$1.6 & 63.2$\pm$2.9 & 39.7$\pm$2.5 & 60.6$\pm$2.7 \\

                          & MPART-Explorer (w/o DS) & 94.4$\pm$1.5 & 65.7$\pm$2.1 & 41.9$\pm$2.0 & 62.3$\pm$2.4 \\

        \bottomrule
        \end{tabular}

\end{sc}
\end{small}
\end{center}
\end{table*}

\begin{table*}[t]
\caption{Classification accuracy (mean $\pm$ std) according to MPART's query frequency and number of layers $L$ for message passing. The `Explorer' strategy was used for query selection of MPART. (unit : \%)}
\label{tab:layer_results}
\begin{center}
\begin{small}
\begin{sc}
        \begin{tabular}{c c c c c c c}
        \toprule
        Query Selection & Number of & Mouse retina & Fashion & EMNIST & \multirow{2}{*}{CIFAR-10} \\

        Frequency & Layers & transcriptomes  & MNIST & Letters &  \\
        \midrule

\multirow{4}{*}{2 / 2000}

                          & $L = 5$ & 90.0$\pm$7.1 & 52.6$\pm$5.7 & 25.6$\pm$2.8 & 52.9$\pm$4.6 \\
                          & $L = 3$ & \textbf{92.3}$\pm$4.0 & \textbf{56.5}$\pm$3.9 & \textbf{26.5}$\pm$2.3 & \textbf{53.9}$\pm$4.4 \\
                          & $L = 1$ & 66.9$\pm$4.7 & 44.0$\pm$5.2 & 14.3$\pm$1.6 & 27.3$\pm$2.2 \\
                          & w/o MP  & 31.1$\pm$4.9 & 15.2$\pm$0.9 & 4.9$\pm$0.3 & 11.3$\pm$0.3 \\
         \midrule
\multirow{4}{*}{4 / 2000}

                          & $L = 5$ & \textbf{94.1}$\pm$2.2 & \textbf{60.1}$\pm$4.6 & 33.4$\pm$3.2 & 58.1$\pm$4.0 \\
                          & $L = 3$ & 93.1$\pm$3.5 & 60.0$\pm$4.4 & \textbf{36.0}$\pm$2.8 & \textbf{59.5}$\pm$3.8 \\
                         & $L = 1$ & 86.8$\pm$2.6 & 59.2$\pm$3.9 & 21.4$\pm$1.2 & 38.3$\pm$2.0 \\
                         & w/o MP & 31.0$\pm$2.3 & 19.6$\pm$1.6 & 6.0$\pm$0.2 & 12.5$\pm$0.5 \\
                        \midrule
\multirow{4}{*}{20 / 2000}

                         & $L = 5$ & \textbf{96.1}$\pm$0.5 & \textbf{67.6}$\pm$1.5 & 47.6$\pm$1.6 & \textbf{67.4}$\pm$1.6 \\
                         & $L = 3$ & 95.8$\pm$0.7 & 67.3$\pm$1.5 & \textbf{48.0}$\pm$1.7 & 67.2$\pm$1.3 \\
                         & $L = 1$ & 95.0$\pm$1.1 & 66.6$\pm$1.4 & 40.3$\pm$1.5 & 59.1$\pm$1.1 \\
                         & w/o MP & 57.8$\pm$1.5 & 43.6$\pm$2.2 & 12.2$\pm$0.6 & 20.5$\pm$0.6 \\
        \bottomrule
        \end{tabular}
\end{sc}
\end{small}
\end{center}
\end{table*}

\section{Results and Discussion}

\subsection{Comparison with Competitive Models}

The performance of the competitive models LPART \cite{kim2020label} and A-SOINN \cite{shen2011incremental} was compared to that of MPART with various query selection strategy, shown in Table \ref{tab:ablation_results} and Figure \ref{fig:evolve}.
The fully supervised settings including multi-layer perceptron (MLP) model were used as references, which was trained using all labeled data for each dataset.
The MLP is consisted of 3 layers with 128 neurons per layer and we reported the highest test accuracy while training up to 200 epochs.
The same ART-related parameter values were used in MPART and LPART, while A-SOINN parameters were adjusted to achieve its best performance for fair comparison.
A-SOINN needs to query the prototype of the most dense node, which is a weighted sum of encoded representations and does not correspond to any input samples.
Therefore, in A-SOINN, the prototype of the node was not directly queried, but the most recent input sample that activates the node was queried.
In all experimental settings except with MLP, the MPART showed the highest accuracy.

\textbf{Comparison with LPART. }
MPART with `Random' strategy showed higher performance than LPART, which performs online semi-supervised learning.
This indicates that although both models are based on the same backbone model, Fuzzy ART, MPART's message passing method is more effective than LPART's label propagation method.
MPART's massage passing differs from LPART's label propagation in several aspects.
The critical difference is that LPART does not sufficiently learn and use topology information of input data.
LPART permanently updates the label density $q$ when label propagation is performed, whereas MPART updates $q^0$ using only true labels and infers the class through message passing.
The MPART's message passing method with multi-layers prevents information propagation of one node from permanently affecting other nodes, and when a new label is acquired, the information can be immediately reflected in the inference of all nodes.
In addition, MPART queries representative samples by estimating the distribution density of input data using the topology learned online, whereas in the case of LPART, it is difficult to select a representative sample because it cannot effectively estimate the distribution of the input data.

\textbf{Comparison with A-SOINN. }
A-SOINN employs an explicit removal of edges and nodes to reduce the noise and maintain a reasonable model size.
The removal procedure heavily depends on the deletion period $\lambda$, which should ideally be determined according to the input statistics.
Since such information is not known \textit{a priori}, a wrong choice of $\lambda$ severely degrades the model performance.
Also, each node in A-SOINN holds only one label which is fixed since the first assignment either with actual label or by propagation from other nodes.
Therefore, the order of labeling highly influences the inference results, especially at decision boundaries.
This might explain why A-SOINN even performs worse than LPART in fully-supervised setting.

\textbf{Computational  Cost. }
MPART requires more computation than LPART and A-SOINN, but the computational cost required to update the model is very low.
We measured the run-time of our Python implementation on a 3.8 GHz CPU machine.
The time taken to train and infer 10,000 of CIFAR-10 data samples was 11.2 seconds on average, which took about 1.12 ms per sample.
For the CIFAR-10 dataset, the average numbers of nodes are 1260, 1922, and 2442 when trained with 15k, 30k and 45k samples respectively.
Please refer to the Appendix for detailed statistical analysis and additional experimental results.

\subsection{Ablation Study}

Table \ref{tab:ablation_results} summarizes the results of performance evaluation of our model on four datasets according to query selection frequencies and strategies.
In the w/o DS setting, the query selection score $u_t$ of Equation \ref{eq:u_sum} was used instead of $s_t$ of Equation \ref{eq:score}.
In all experimental settings, the model that applies density-weighted query selection score showed significantly higher performance than the one without (w/o DS).
When comparing the performance with respect to the query selection strategy, the accuracy of the `Random' strategy was generally low, and the `Memory' strategy and the `Explorer' strategy showed almost similar performance.
This is because the `Explorer' strategy properly estimates the uncertainty distribution of input data and efficiently selects the representative samples based on the remaining query opportunities.
In addition, the lower the query frequency, the greater the difference in performance depending on the query selection strategy, indicating that the strategy can have a significant impact on performance in situations where labeled data is extremely scarce.
Table \ref{tab:layer_results} shows the performance evaluation of MPART according to the number of layers $L$ for message passing.
As the number of layers increased, the classification performance generally increased, but the results of using 3 and 5 layers were almost the same.
On the other hand, when message passing is not applied (w/o MP), there is a significant performance penalty.

\section{Conclusions}

We propose Message Passing Adaptive Resonance Theory (MPART) for online active semi-supervised learning.
MPART learns the distribution and the topology of the input data online, infers the class of unlabeled data, and selects the informative and representative samples through message passing between nodes on the topological graph.
By evaluating our method on datasets including EMNIST Letters and CIFAR-10, we show that it outperforms the competitive models.
In an online learning environment where data storage is limited and data labeling is expensive, waste of useful samples is inevitable.
The proposed model fully utilizes the underlying structure of input data so that it can minimize the waste.
This approach also reduces the need to create large datasets in advance in order to apply machine learning to various industries.
We believe MPART offers new opportunities for machine learning techniques to be widely used in real-world applications.

\section*{Acknowledgements}

This work was partly supported by the Institute of Information \& Communications Technology Planning \& Evaluation (2019-0-01371-BabyMind/35\%, 2015-0-00310-SW.StarLab/5\%, 2017-0-01772-VTT/5\%, 2018-0-00622-RMI/5\%) grant funded by the Korean government.