# An Effective Transition-based Model for Discontinuous NER

Xiang Dai1,2 Sarvnaz Karimi1 Ben Hachey3 Cecile Paris1
1CSIRO Data61, Sydney, Australia 2University of Sydney, Sydney, Australia
3Harrison.ai, Sydney, Australia<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Unlike widely used Named Entity Recognition (NER) data sets in generic
domains, biomedical NER data sets often contain mentions consisting of
discontinuous spans. Conventional sequence tagging techniques encode Markov
assumptions that are efficient but preclude recovery of these mentions. We
propose a simple, effective transition-based model with generic neural
encoding for discontinuous NER. Through extensive experiments on three
biomedical data sets, we show that our model can effectively recognize
discontinuous mentions without sacrificing the accuracy on continuous
mentions.

##  1 Introduction

Named Entity Recognition (NER) is a critical component of biomedical natural
language processing applications. In pharmacovigilance, it can be used to
identify adverse drug events in consumer reviews in online medication forums,
alerting medication developers, regulators and clinicians Leaman et al.
(2010); Sarker et al. (2015); Karimi et al. (2015b). In clinical settings, NER
can be used to extract and summarize key information from electronic medical
records such as conditions hidden in unstructured doctors’ notes Feblowitz et
al. (2011); Wang et al. (2018b). These applications require identification of
complex mentions not seen in generic domains Dai (2018).

Widely used sequence tagging techniques (flat model) encode two assumptions
that do not always hold: (1) mentions do not nest or overlap, therefore each
token can belong to at most one mention; and, (2) mentions comprise continuous
sequences of tokens. Nested entity recognition addresses violations of the
first assumption Lu and Roth (2015); Katiyar and Cardie (2018); Sohrab and
Miwa (2018); Ringland et al. (2019). However, the violation of the second
assumption is comparatively less studied and requires handling discontinuous
mentions (see examples in Figure 1).

Figure 1: Examples involving discontinuous mentions, taken from the ShARe 13
(Pradhan et al., 2013) and CADEC (Karimi et al., 2015a) data sets,
respectively. The first example contains a discontinuous mention _‘left atrium
dilated’_ , the second example contains two mentions that overlap: _‘muscle
pain’_ and _‘muscle fatigue’_ (discontinuous).

In contrast to continuous mentions which are often short spans of text,
discontinuous mentions consist of components that are separated by intervals.
Recognizing discontinuous mentions is particularly challenging as exhaustive
enumeration of possible mentions, including discontinuous and overlapping
spans, is exponential in sentence length. Existing approaches for
discontinuous NER either suffer from high time complexity McDonald et al.
(2005) or ambiguity in translating intermediate representations into mentions
Tang et al. (2013a); Metke-Jimenez and Karimi (2016); Muis and Lu (2016). In
addition, current art uses traditional approaches that rely on manually
designed features, which are tailored to recognize specific entity types.
Also, these features usually do not generalize well in different genres Leaman
et al. (2015).

#### Motivations

The main motivation for recognizing discontinuous mentions is that they
usually represent compositional concepts that differ from concepts represented
by individual components. For example, the mention ‘left atrium dilated’ in
the first example of Figure 1 describes a disorder which has its own CUI
(Concept Unique Identifier) in UMLS (Unified Medical Language System), whereas
both ‘left atrium’ and ‘dilated’ also have their own CUIs. We argue that, in
downstream applications such as pharmacovigilance and summarization,
recognizing these discontinuous mentions that refer to disorders or symptoms
is more useful than recognizing separate components which may refer to body
locations or general feelings.

Another important characteristic of discontinuous mentions is that they
usually overlap. That is, several mentions may share components that refer to
the same body location (e.g., ‘muscle’ in ‘muscle pain and fatigue’), or the
same feeling (e.g., ‘Pain’ in ‘Pain in knee and foot’). Separating these
overlapping mentions rather than identifying them as a single mention is
important for downstream tasks, such as entity linking where the assumption is
that the input mention refers to one entity Shen et al. (2015).

#### Contributions

We propose an end-to-end transition-based model with generic neural encoding
that allows us to leverage specialized actions and attention mechanism to
determine whether a span is the component of a discontinuous mention or
not.111Code available at GitHub: https://bit.ly/2XazEAO We evaluate our model
on three biomedical data sets with a substantial number of discontinuous
mentions and demonstrate that our model can effectively recognize
discontinuous mentions without sacrificing the accuracy on continuous
mentions.

##  2 Prior Work

Existing methods on discontinuous NER can be mainly categorized into two
categories: token level approach, based on sequence tagging techniques, and
sentence level approach, where a combination of mentions within a sentence is
jointly predicted (Dai, 2018).

#### Token level approach

Sequence tagging model takes a sequence of tokens as input and outputs a tag
for each token, composed of a position indicator (e.g., BIO schema) and an
entity type. The vanilla BIO schema cannot effectively represent
discontinuous, overlapping mentions, therefore, some studies overcome this
limitation via expanding the BIO tag set Tang et al. (2013a); Metke-Jimenez
and Karimi (2016); Dai et al. (2017); Tang et al. (2018). In addition to BIO
indicators, four new position indicators are introduced in Metke-Jimenez and
Karimi (2016) to represent discontinuous mentions that may overlap:

  * •

BH: Beginning of Head, defined as the components shared by multiple mentions;

  * •

IH: Intermediate of Head;

  * •

BD: Beginning of Discontinuous body, defined as the exclusive components of a
discontinuous mention; and

  * •

ID: Intermediate of Discontinuous body.

#### Sentence level approach

Instead of predicting whether each token belongs to an entity mention and its
role in the mention, sentence level approach predicts a combination of
mentions within a sentence. A hypergraph, proposed by Lu and Roth (2015) and
extended in Muis and Lu (2016), can compactly represent discontinuous and
overlapping mentions in one sentence. A sub-hypergraph of the complete
hypergraph can, therefore, be used to represent a combination of mentions in
the sentence. For the token at each position, there can be six different node
types:

  * •

A: mentions that start from the current token or a future token;

  * •

E: mentions that start from the current token;

  * •

T: mentions of a certain entity type that start from the current token;

  * •

B: mentions that contain the current token;

  * •

O: mentions that have an interval at the current token;

  * •

X: mentions that end at the current token.

Using this representation, a single entity mention can be represented as a
path from node A to node X, incorporating at least one node of type B.

Note that both token level and sentence level approaches predict first an
intermediate representation of mentions (e.g., a sequence of tags in Metke-
Jimenez and Karimi (2016) and a sub-hypergraph in Muis and Lu (2016)), which
are then decoded into the final mentions. During the final decoding stage,
both models suffer from some level of ambiguity. Taking the sequence tagging
model using BIO variant schema as an example, even if the model can correctly
predict the gold sequence of tags for the example sentence ‘muscle pain and
fatigue’ (BH I O BD), it is still not clear whether the token ‘muscle’ forms a
mention by itself, because the same sentence containing three mentions
(‘muscle’, ‘muscle pain’ and ‘muscle fatigue’) can be encoded using the same
gold sequence of tags. We refer to a survey by Dai (2018) for more discussions
on these models, and Muis and Lu (2016) for a theoretical analysis of
ambiguity of these models.

Similar to prior work, our proposed transition-based model uses an
intermediate representation (i.e., a sequence of actions). However, it does
not suffer from this ambiguity issue. That is, the output sequence of actions
can always be unambiguously decoded into mention outputs.

The other two methods that focus on the discontinuous NER problem in
literature are described in (McDonald et al., 2005; Wang and Lu, 2019).
McDonald et al. (2005) solve the NER task as a structured multi-label
classification problem. Instead of starting and ending indices, they represent
each entity mention using the set of token positions that belong to the
mention. This representation is flexible, as it allows mentions consisting of
discontinuous tokens and does not require mentions to exclude each other.
However, this method suffers from high time complexity. Tang et al. (2018)
compare this representation with BIO variant schema proposed in Metke-Jimenez
and Karimi (2016), and found that they achieve competitive $F_{1}$ scores,
although the latter method is more efficient. A two-stage approach that first
detects all components and then combines components into discontinuous
mentions based on a classifier’s decision was explored in recent work by Wang
and Lu (2019).

#### Discontinuous NER vs. Nested NER

Although discontinuous mentions may overlap, we discriminate this overlapping
from the one in nested NER. That is, if one mention is completely contained by
the other, we call mentions involved nested entity mentions. In contrast,
overlapping in discontinuous NER is usually that two mentions overlap, but no
one is completely contained by the other. Most of existing nested NER models
are built to tackle the complete containing structure (Finkel and Manning,
2009; Lu and Roth, 2015), and they cannot be directly used to identify
overlapping mentions studied in this paper, nor mention the discontinuous
mentions. However, we note that there is a possible perspective to solve
discontinuous NER task by adding fine-grained entity types into the schema.
Taking the second sentence in Figure 1 as an example, we can add two new
entity types: ‘Body Location’ and ’General Feeling’, and then annotate ‘muscle
pain and fatigue’ as a ‘Adverse drug event’ mention, ‘muscle’ as a ‘Body
Location’ mention, and ‘pain’ and ‘fatigue’ as ‘General Feeling’ mentions
(Figure 2). Then the discontinuous NER task can be converted into a Nested NER
task.

Figure 2: Examples involving Nested mentions.

##  3 Model

Transition-based models, due to their high efficiency, are widely used for NLP
tasks, such as parsing and entity recognition Chen and Manning (2014); Lample
et al. (2016); Lou et al. (2017); Wang et al. (2018a). The model we propose
for discontinuous NER is based on the shift-reduce parser Watanabe and Sumita
(2015); Lample et al. (2016) that employs a stack to store partially processed
spans and a buffer to store unprocessed tokens. The learning problem is then
framed as: given the state of the parser, predict an action which is applied
to change the state of the parser. This process is repeated until the parser
reaches the end state (i.e., the stack and buffer are both empty).

Figure 3: An example sequence of transitions. Given the states of stack and
buffer (blue highlighted), as well as the previous actions, predict the next
action (i.e., LEFT-REDUCE) which is then applied to change the states of stack
and buffer.

The main difference between our model and the ones in (Watanabe and Sumita,
2015; Lample et al., 2016) is the set of transition actions. Watanabe and
Sumita (2015) use SHIFT, REDUCE, UNARY, FINISH, and IDEA for the constituent
parsing system. Lample et al. (2016) use SHIFT, REDUCE, OUT for the flat NER
system. Inspired by these models, we design a set of actions specifically for
recognizing discontinuous and overlapping structure. There are in total six
actions in our model:

  * •

SHIFT moves the first token from the buffer to the stack; it implies this
token is part of an entity mention.

  * •

OUT pops the first token of the buffer, indicating it does not belong to any
mention.

  * •

COMPLETE pops the top span of the stack, outputting it as an entity mention.
If we are interested in multiple entity types, we can extend this action to
COMPLETE-$y$ which labels the mention with entity type $y$.

  * •

REDUCE pops the top two spans $s_{0}$ and $s_{1}$ from the stack and
concatenates them as a new span which is then pushed back to the stack.

  * •

LEFT-REDUCE is similar to the REDUCE action, except that the span $s_{1}$ is
kept in the stack. This action indicates the span $s_{1}$ is involved in
multiple mentions. In other words, several mentions share $s_{1}$ which could
be a single token or several tokens.

  * •

RIGHT-REDUCE is the same as LEFT-REDUCE, except that $s_{0}$ is kept in the
stack.

Figure 3 shows an example about how the parser recognizes entity mentions from
a sentence. Note that, given one parser state, not all types of actions are
valid. For example, if the stack does not contain any span, only SHIFT and OUT
actions are valid because all other actions involve popping spans from the
stack. We employ hard constraints that we only select the most likely action
from valid actions.

###  3.1 Representation of the Parser State

Given a sequence of $N$ tokens, we first run a bi-directional LSTM (Graves et
al., 2013) to derive the contextual representation of each token.
Specifically, for the $i$-th token in the sequence, its representation can be
denoted as:

$\mathbf{\tilde{c_{i}}}=\left[\overrightarrow{\text{LSTM}}(\mathbf{t_{0}},\dots,\mathbf{t_{i}});\overleftarrow{\text{LSTM}}(\mathbf{t_{i}},\dots,\mathbf{t_{N-1}})\right],$

where $\mathbf{t_{i}}$ is the concatenation of the embeddings for the $i$-th
token, its character level representation learned using a CNN network Ma and
Hovy (2016). Pretrained contextual word representations have shown its
usefulness on improving various NLP tasks. Here, we can also concatenate
pretrained contextual word representations using ELMo Peters et al. (2018)
with $\mathbf{\tilde{c_{i}}}$, resulting in:

$\mathbf{c_{i}}=\left[\mathbf{\tilde{c_{i}}};\text{ELMo}_{i}\right],$ (1)

where $\text{ELMo}_{i}$ is the output representation of pretrained ELMo models
(frozen) for the $i$-th token. These token representations $\mathbf{c}$ are
directly used to represent tokens in the buffer. We also explore a variant
that uses the output of pretrained BERT (Devlin et al., 2019) as token
representations $\mathbf{c}$, and fine-tune the BERT model. However, this
fine-tuning approach with BERT does not achieve as good performance as feature
extraction approach with ELMo Peters et al. (2019).

Following the work in Dyer et al. (2015), we use Stack-LSTM to represent spans
in the stack. That is, if a token is moved from the buffer to the stack, its
representation is learned using:

$\mathbf{s_{0}}=\text{Stack-
LSTM}(\mathbf{s_{D}}\dots\mathbf{s_{1}};\mathbf{c}_{\text{SHIFT}}),$

where $D$ is the number of spans in the stack. Once REDUCE related actions are
applied, we use a multi-layer perceptron to learn the representation of the
concatenated span. For example, the REDUCE action takes the representation of
the top two spans in the stack: $\mathbf{s_{0}}$ and $\mathbf{s_{1}}$, and
produces a new span representation:

$\mathbf{\tilde{s}}=\textbf{W}^{T}[\mathbf{s_{0}};\mathbf{s_{1}}]+b,$

where W and $b$ denote the parameters for the composition function. The new
span representation $\mathbf{\tilde{s}}$ is pushed back to the stack to
replace the original two spans: $\mathbf{s_{0}}$ and $\mathbf{s_{1}}$.

###  3.2 Capturing Discontinuous Dependencies

We hypothesize that the interactions between spans in the stack and tokens in
the buffer are important factors in recognizing discontinuous mentions.
Considering the example in Figure 3, a span in the stack (e.g., ‘muscle’) may
need to combine with a future token in the buffer (e.g., ‘fatigue’). To
capture this interaction, we use multiplicative attention Luong et al. (2015)
to let the span in the stack $\mathbf{s_{i}}$ learn which token in the buffer
to attend, and thus a weighted sum of the representation of tokens in the
buffer $\mathbf{B}$:

$\mathbf{s^{a}_{i}}=\textbf{softmax}(\mathbf{s_{i}^{T}W^{a}_{i}B})\mathbf{B}.$
(2)

We use distinct $\mathbf{W_{i}^{a}}$ for $\mathbf{s_{i}}$ separately.

###  3.3 Selecting an Action

Finally, we build the parser representation as the concatenation of the
representation of top three spans from the stack
($\mathbf{s_{0}},\mathbf{s_{1}},\mathbf{s_{2}}$) and its attended
representation ($\mathbf{s^{a}_{0}}$, $\mathbf{s^{a}_{1}}$,
$\mathbf{s^{a}_{2}}$), as well as the representation of the previous action
$\mathbf{a}$, which is learned using a simple unidirectional LSTM. If there
are less than 3 spans in the stack or no previous action, we use randomly
initialized vectors $\mathbf{s_{empty}}$ or $\mathbf{a_{empty}}$ to replace
the corresponding vector. This parser representation is used as input for the
final softmax prediction layer to select the next action.

##  4 Data sets

Although some text annotation tools, such as BRAT Stenetorp et al. (2012),
allow discontinuous annotations, corpora annotated with a large number of
discontinuous mentions are still rare. We use three data sets from the
biomedical domain: CADEC Karimi et al. (2015a), ShARe 13 Pradhan et al. (2013)
and ShARe 14 Mowery et al. (2014). Around 10% of mentions in these three data
sets are discontinuous. The descriptive statistics are listed in Table 1.

| CADEC | ShARe 13 | ShARe 14
---|---|---|---
Text type | online posts | clinical notes | clinical notes
Entity type | ADE | Disorder | Disorder
# Documents | 1,250 | 298 | 433
# Tokens | 121K | 264K | 494K
# Sentences | 7,597 | 18,767 | 34,618
# Mentions | 6,318 | 11,161 | 19,131
# Disc.M | 675 (10.6) | 1,090 (9.7) | 1,710 (8.9)
Avg mention L. | 2.7 | 1.8 | 1.7
Avg Disc.M L. | 3.5 | 2.6 | 2.5
Avg interval L. | 3.3 | 3.0 | 3.2
Discontinuous Mentions
2 components | 650 (95.7) | 1,026 (94.3) | 1,574 (95.3)
3 components |  027 (03.9) |  0062 (05.6) |  0076 (04.6)
4 components |  002 (00.2) |  0000 (00.0) |  0000 (00.0)
No overlap |  082 (12.0) |  0582 (53.4) |  0820 (49.6)
Overlap at left | 351 (51.6) |  0376 (34.5) |  0616 (37.3)
Overlap at right | 152 (22.3) |  0102 (09.3) |  0170 (10.3)
Multiple overlaps |  094 (13.8) |  0028 (02.5) |  0044 (02.6)
Continuous Mentions
Overlap | 326 (05.7) |  0157 (01.5) |  0228 (01.3)
Table 1: The descriptive statistics of the data sets. ADE: adverse drug
events; Disc.M: discontinuous mentions; Disc.M L.: discontinuous mention
length, where intervals are not counted. Numbers in parentheses are the
percentage of each category.

CADEC is sourced from AskaPatient222https://www.askapatient.com/, a forum
where patients can discuss their experiences with medications. The entity
types in CADEC include drug, Adverse Drug Event (ADE), disease and symptom. We
only use ADE annotations because only the ADEs involve discontinuous
annotations. This also allows us to compare our results directly against
previously reported results Metke-Jimenez and Karimi (2016); Tang et al.
(2018). ShARe 13 and 14 focus on the identification of disorder mentions in
clinical notes, including discharge summaries, electrocardiogram,
echocardiogram, and radiology reports Johnson et al. (2016). A disorder
mention is defined as any span of text which can be mapped to a concept in the
disorder semantic group of SNOMED-CT Cornet and de Keizer (2008).

Although these three data sets share similar field (the subject matter of the
content being discussed), the tenor (the participants in the discourse, their
relationships to each other, and their purposes) of CADEC is very different
from the ShARe data sets Dai et al. (2019). In general, laymen (i.e., in
CADEC) tend to use idioms to describe their feelings, whereas professional
practitioners (i.e., in ShARe) tend to use compact terms for efficient
communications. This also results in different features of discontinuous
mentions between these data sets, which we will discuss further in $\S$ 7.

#### Experimental Setup

As CADEC does not have an official train-test split, we follow Metke-Jimenez
and Karimi (2016) and randomly assign 70% of the posts as the training set,
15% as the development set, and the remaining posts as the test set. 333These
splits can be downloaded from https://bit.ly/2XazEAO. The train-test splits of
ShARe 13 and 14 are both from their corresponding shared task settings, except
that we randomly select 10% of documents from each training set as the
development set. Micro average strict match $F_{1}$ score is used to evaluate
the effectiveness of the model. The trained model which is most effective on
the development set, measured using the $F_{1}$ score, is used to evaluate the
test set.

##  5 Baseline Models

|  | CADEC |  | ShARe 13 |  | ShARe 14
---|---|---|---|---|---|---
Model |  | P | R | F |  | P | R | F |  | P | R | F
Metke-Jimenez and Karimi (2016) |  | 64.4 | 56.5 | 60.2 |  | – | – | – |  | – | – | –
Tang et al. (2018) |  | 67.8 | 64.9 | 66.3 |  | – | – | – |  | – | – | –
Tang et al. (2013b) |  | – | – | – |  | 80.0 | 70.6 | 75.0 |  | – | – | –
Flat |  | 65.3 | 58.5 | 61.8 |  | 78.5 | 66.6 | 72.0 |  | 76.2 | 76.7 | 76.5
BIO Extension |  | 68.7 | 66.1 | 67.4 |  | 77.0 | 72.9 | 74.9 |  | 74.9 | 78.5 | 76.6
Graph |  | 72.1 | 48.4 | 58.0 |  | 83.9 | 60.4 | 70.3 |  | 79.1 | 70.7 | 74.7
Ours |  | 68.9 | 69.0 | 69.0 |  | 80.5 | 75.0 | 77.7 |  | 78.1 | 81.2 | 79.6
Table 2: Evaluation results on the whole test set in terms of precision, recall and $F_{1}$ score. The original ShARe 14 task focuses on template filling of disorder attributes: that is, given a disorder mention, recognize the attribute from its context. In this work, we use its mention annotations and frame the task as a discontinuous NER task.  |  | Sentences with discontinuous mentions |  | Discontinuous mentions only
---|---|---|---|---
|  | CADEC |  | ShARe 13 |  | ShARe 14 |  | CADEC |  | ShARe 13 |  | ShARe 14
Model |  | P | R | F |  | P | R | F |  | P | R | F |  | P | R | F |  | P | R | F |  | P | R | F
Flat |  | 50.2 | 36.7 | 42.4 |  | 43.5 | 28.1 | 34.2 |  | 41.5 | 31.9 | 36.0 |  | 0 | 0 | 0 |  | 0 | 0 | 0 |  | 0 | 0 | 0
BIO E. |  | 63.8 | 52.0 | 57.3 |  | 51.8 | 39.5 | 44.8 |  | 37.5 | 38.4 | 37.9 |  | 5.8 | 1.0 | 1.8 |  | 39.7 | 12.3 | 18.8 |  | 8.8 | 4.5 | 6.0
Graph |  | 69.5 | 43.2 | 53.3 |  | 82.3 | 47.4 | 60.2 |  | 60.0 | 52.8 | 56.2 |  | 60.8 | 14.8 | 23.9 |  | 78.4 | 36.6 | 50.0 |  | 42.7 | 39.5 | 41.1
Ours |  | 66.5 | 64.3 | 65.4 |  | 70.5 | 56.8 | 62.9 |  | 61.9 | 64.5 | 63.1 |  | 41.2 | 35.1 | 37.9 |  | 78.5 | 39.4 | 52.5 |  | 56.1 | 43.8 | 49.2
Table 3: Evaluation results on sentences that contain at least one
discontinuous mention (left part) and on discontinuous mentions only (right
part).

We choose one flat NER model which is strong at recognizing continuous
mentions, and two discontinuous NER models as our baseline models:

#### Flat model

To train the flat model on our data sets, we use an off-the-shelf framework:
Flair Akbik et al. (2018), which achieves the state-of-the-art performance on
CoNLL 03 data set. Recall that the flat model cannot be directly applied to
data sets containing discontinuous mentions. Following the practice in
Stanovsky et al. (2017), we replace the discontinuous mention with the
shortest span that fully covers it, and merge overlapping mentions into a
single mention that covers both. Note that, different from Stanovsky et al.
(2017), we apply these changes only on the training set, but not on the
development set and the test set.

#### BIO extension model

The original implementation in Metke-Jimenez and Karimi (2016) used a CRF
model with manually designed features. We report their results on CADEC in
Table 2 and re-implement a BiLSTM-CRF-ELMo model using their tag schema
(denoted as ‘BIO Extension’ in Table 2).

#### Graph-based model

The original paper of Muis and Lu (2016) only reported the evaluation results
on sentences which contain at least one discontinuous mention. We use their
implementation to train the model and report evaluation results on the whole
test set (denoted as ‘Graph’ in Table 2). We argue that it is important to see
how a discontinuous NER model works not only on the discontinuous mentions but
also on all the mentions, especially since, in real data sets, the ratio of
discontinuous mentions cannot be made a priori.

We do not choose the model proposed in Wang and Lu (2019) as the baseline
model, because it is based on a strong assumption about the ratio of
discontinuous mentions. Wang and Lu (2019) train and evaluate their model on
sentences that contain at least one discontinuous mention. Our early
experiments show that the effectiveness of their model strongly depends on
this assumption. In contrast, we train and evaluate our model in a more
practical setting where the number of continuous mentions is much larger than
the one of discontinuous mentions.

##  6 Experimental Results

When evaluated on the whole test set, our model outperforms three baseline
models, as well as over previous reported results in the literature, in terms
of recall and $F_{1}$ scores (Table 2).

The graph-based model achieves highest precision, but with substantially lower
recall, therefore obtaining lowest $F_{1}$ scores. In contrast, our model
improves recall over flat and BIO extension models as well as previously
reported results, without sacrificing precision. This results in more balanced
precision and recall. Improved recall is especially encouraging for our
motivating pharmacovigilance and medical record summarization applications,
where recall is at least as important as precision.

#### Effectiveness on recognizing discontinuous mentions

Recall that only 10% of mentions in these three data sets are discontinuous.
To evaluate the effectiveness of our proposed model on recognizing
discontinuous mentions, we follow the evaluation approach in Muis and Lu
(2016) where we construct a subset of test set where only sentences with at
least one discontinuous mention are included (Left part of Table 3). We also
report the evaluation results when only discontinuous mentions are considered
(Right part of Table 3). Note that sentences in the former setting usually
contain continuous mentions as well, including those involved in overlapping
structure (e.g., ‘muscle pain’ in the sentence ‘muscle pain and fatigue’).
Therefore, the flat model, which cannot predict any discontinuous mentions,
still achieves 38% $F_{1}$ on average when evaluated on these sentences with
at least one discontinuous mention, but 0% $F_{1}$ when evaluated on
discontinuous mentions only.

Our model again achieves the highest $F_{1}$ and recall in all three data sets
under both settings. The comparison between these two evaluation results also
shows the necessity of comprehensive evaluation settings. The BIO E. model
outperforms the graph-based model in terms of $F_{1}$ score on CADEC, when
evaluated on sentences with discontinuous mentions. However, it achieves only
1.8 $F_{1}$ when evaluated on discontinuous mentions only. The main reason is
that most of discontinuous mentions in CADEC are involved in overlapping
structure (88%, cf. Table 1), and the BIO E. model is better than the graph-
based model at recognizing these continuous mentions. On ShARe 13 and 14,
where the portion of discontinuous mentions involved in overlapping is much
less than on CADEC, the graph-based model clearly outperforms BIO E. model in
both evaluation settings.

##  7 Analysis

We start our analysis from characterizing discontinuous mentions from the
three data sets. Then we measure the behaviors of our model and two
discontinuous NER models on the development sets based on characteristics
identified and attempt to draw conclusions from these measurements.

###  7.1 Characteristics of Discontinuous Mentions

(a) CADEC

(b) ShARe 13

(c) ShARe 14

(d) CADEC

(e) ShARe 13

(f) ShARe 14

Figure 4: The impact of mention length and interval length on recall. Mentions
with interval length of zero are continuous mentions. Numbers in parentheses
are the number of gold mentions.

Recall that discontinuous mentions usually represent compositional concepts
that consist of multiple components. Therefore, discontinuous mentions are
usually longer than continuous mentions (Table 1). In addition, intervals
between components make the total length of span involved even longer.
Previous work shows that flat NER performance degrades when applied on long
mentions Augenstein et al. (2017); Xu et al. (2017).

Another characteristic of discontinuous mentions is that they usually overlap
(cf. $\S$ 1). From this perspective, we can categorize discontinuous mentions
into four categories:

  * •

No overlap: in such cases, the discontinuous mention can be intervened by
severity indicators (e.g., ‘is mildly’ in sentence ‘left atrium is mildly
dilated’), preposition (e.g., ‘on my’ in sentence ‘…rough on my stomach…’) and
so on. This category accounts for half of discontinuous mentions in the ShARe
data sets but only 12% in CADEC (Table 1).

  * •

Left overlap: the discontinuous mention shares one component with other
mentions, and the shared component is at the beginning of the discontinuous
mention. This is usually accompanied with coordination structure (e.g., the
shared component ‘muscle’ in ‘muscle pain and fatigue’). Conjunctions (e.g.,
‘and’, ‘or’) are clear indicators of the coordination structure. However,
clinical notes are usually written by practitioners under time pressure. They
often use commas or slashes rather than conjunctions. This category accounts
for more than half of discontinuous mentions in CADEC and one third in ShARe.

  * •

Right overlap: similar to left overlap, although the shared component is at
the end. For example, ‘hip/leg/foot pain’ contains three mentions that share
‘pain’.

  * •

Multi-overlap: the discontinuous mention shares multiple components with the
others, which usually forms _crossing compositions_. For example, the sentence
‘Joint and Muscle Pain / Stiffness’ contains four mentions: ‘Joint Pain’,
‘Joint Stiffness’, ‘Muscle Stiffness’ and ‘Muscle Pain’, where each
discontinuous mention share two components with the others.

###  7.2 Impact of Overlapping Structure

Previous study shows that the intervals between components can be problematic
for coordination boundary detection Ficler and Goldberg (2016). Conversely, we
want to observe whether the overlapping structure may help or hinder
discontinuous entity recognition. We categorize discontinuous mentions into
different subsets, described in $\S$ 7.1, and measure the effectiveness of
different discontinuous NER models on each category.

From Table 4, we find that our model achieves better results on discontinuous
mentions belonging to ‘No overlap’ category on ShARe 13 and 14, and ‘Left
overlap’ category on CADEC and ShARe 14. Note that ‘No overlap’ category
accounts for half of discontinuous mentions in ShARe 13 and 14, whereas ‘Left
overlap’ accounts for half in CADEC (Table 1). Graph-based model achieves
better results on ‘Right overlap’ category. On the ‘Multi-overlap’ category,
no models is effective, which emphasizes the challenges of dealing with this
syntactic phenomena. We note, however, the portion of discontinuous mentions
belonging to this category is very small in all three data sets.

Although our model achieves better results on ‘No overlap’ category on ShARe
13 and 14, it does not predict correctly any discontinuous mention belonging
to this category on CADEC. The ineffectiveness of our model, as well as other
discontinuous NER models, on CADEC ‘No overlap’ category can be attributed to
two reasons: 1) the number of discontinuous mentions belonging to this
category in CADEC is small (around 12%), rending the learning process more
difficult. 2) the gold annotations belonging to this category are inconsistent
from a linguistic perspective. For example, severity indicators are annotated
as the interval of the discontinuous mention sometimes, but not often. Note
that this may be reasonable from a medical perspective, as some symptoms are
roughly grouped together no matter their severity, whereas some symptoms are
linked to different concepts based on their severity.

|  |  | CADEC |  | ShARe 13 |  | ShARe 14
---|---|---|---|---|---|---|---
| Model |  | # | F |  | # | F |  | # | F
No $\mathbb{O}$ | BIO E. |  | 9 | 0.0 |  | 41 | 7.5 |  | 39 | 0.0
Graph |  | 0.0 |  | 32.1 |  | 45.2
Ours |  | 0.0 |  | 36.1 |  | 57.1
Left $\mathbb{O}$ | BIO E. |  | 54 | 6.0 |  | 11 | 25.0 |  | 30 | 15.7
Graph |  | 9.2 |  | 45.5 |  | 37.7
Ours |  | 28.6 |  | 33.3 |  | 49.2
Right $\mathbb{O}$ | BIO E. |  | 16 | 0.0 |  | 19 | 0.0 |  | 5 | 0.0
Graph |  | 45.2 |  | 21.4 |  | 0.0
Ours |  | 29.3 |  | 13.3 |  | 0.0
Multi $\mathbb{O}$ | BIO E. |  | 15 | 0.0 |  | 0 | – |  | 6 | 0.0
Graph |  | 0.0 |  | – |  | 0.0
Ours |  | 0.0 |  | – |  | 0.0
Table 4: Evaluation results on different categories of discontinuous mentions.
‘#’ columns show the number of gold discontinuous mentions in development set
of each category. $\mathbb{O}$: overlap.

###  7.3 Impact of Mention and Interval Length

We conduct experiments to measure the ability of different models on recalling
mentions of different lengths, and to observe the impact of interval lengths.
We found that the recall of all models decreases with the increase of mention
length in general (Figure 4 (a – c)), which is similar to previous
observations in the literature on flat mentions. However, the impact of
interval length is not straightforward. Mentions with very short interval
lengths are as difficult as those with very long interval lengths to be
recognized (Figure 4 (d – f)). On CADEC, discontinuous mentions with interval
length of 2 are easiest to be recognized (Figure 4 (d)), whereas those with
interval length of 3 are easiest on ShARe 13 and 14. We hypothesize this also
relates to annotation inconsistency, because very short intervals may be
overlooked by annotators.

In terms of model comparison, our model achieves highest recall in most
settings. This demonstrates our model is effective to recognize both
continuous and discontinuous mentions with various lengths. In contrast, the
BIO E. model is only strong at recalling continuous mentions (outperforming
the graph-based model), but fails on discontinuous mentions (interval lengths
$>$ 0).

###  7.4 Example Predictions

We find that previous models often fail to identify discontinuous mentions
that involve long and overlapping spans. For example, the sentence ‘Severe
joint pain in the shoulders and knees.’ contains two mentions: ‘Severe joint
pain in the shoulders’ and ‘Severe joint pain in the knees’. Graph-based model
does not identify any mention from this sentence, resulting in a low recall.
The BIO extension model predicts most of these tags (8 out of 9) correctly,
but fails to decode into correct mentions (predict ‘Severe joint pain in the’,
resulting in a false positive, while it misses ‘Severe joint pain in the
shoulders’). In contrast, our model correctly identifies both of these two
mentions.

No model can fully recognize mentions which form crossing compositions. For
example, the sentence ‘Joint and Muscle Pain / Stiffness’ contains four
mentions: ‘Joint Pain’, ‘Joint Stiffness’, ‘Muscle Stiffness’ and ‘Muscle
Pain’, all of which share multiple components with the others. Our model
correctly predicts ‘Joint Pain’ and ‘Muscle Pain’, but it mistakenly predicts
‘Stiffness’ itself as a mention.

##  8 Summary

We propose a simple, effective transition-based model that can recognize
discontinuous mentions without sacrificing the accuracy on continuous
mentions. We evaluate our model on three biomedical data sets with a
substantial number of discontinuous mentions. Comparing against two existing
discontinuous NER models, our model is more effective, especially in terms of
recall.

## Acknowledgments

We would like to thank Danielle Mowery for helping us to obtain the ShARe data
sets. We also thank anonymous reviewers for their insightful comments. Xiang
Dai is supported by Sydney University’s Engineering and Information
Technologies Research Scholarship as well as CSIRO’s Data61 top up
scholarship.

## References

  * Akbik et al. (2018) Alan Akbik, Duncan Blythe, and Roland Vollgraf. 2018.  Contextual string embeddings for sequence labeling.  In _COLING_ , pages 1638–1649, Santa Fe, New Mexico.
  * Augenstein et al. (2017) Isabelle Augenstein, Mrinal Das, Sebastian Riedel, Lakshmi Vikraman, and Andrew McCallum. 2017.  SemEval 2017 task 10: ScienceIE - extracting keyphrases and relations from scientific publications.  In _SemEval_ , pages 546–555, Vancouver, Canada.
  * Chen and Manning (2014) Danqi Chen and Christopher Manning. 2014.  A fast and accurate dependency parser using neural networks.  In _EMNLP_ , pages 740–750, Doha, Qatar.
  * Cornet and de Keizer (2008) Ronald Cornet and Nicolette de Keizer. 2008.  Forty years of SNOMED: a literature review.  In _BMC Med Inform Decis Mak_ , volume 8, page S2.
  * Dai (2018) Xiang Dai. 2018.  Recognizing complex entity mentions: A review and future directions.  In _ACL@SRW_ , pages 37–44, Melbourne, Australia.
  * Dai et al. (2019) Xiang Dai, Sarvnaz Karimi, Ben Hachey, and Cecile Paris. 2019.  Using similarity measures to select pretraining data for ner.  In _NAACL_ , pages 1460–1470, Minneapolis, Minnesota.
  * Dai et al. (2017) Xiang Dai, Sarvnaz Karimi, and Cėcile Paris. 2017.  Medication and adverse event extraction from noisy text.  In _ALTA_ , pages 79–87, Brisbane, Australia.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL_ , pages 4171–4186, Minneapolis, Minnesota.
  * Dyer et al. (2015) Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A. Smith. 2015\.  Transition-based dependency parsing with stack long short-term memory.  In _ACL-IJCNLP_ , pages 334–343, Beijing, China.
  * Feblowitz et al. (2011) Joshua C Feblowitz, Adam Wright, Hardeep Singh, Lipika Samal, and Dean F Sittig. 2011.  Summarization of clinical information: a conceptual model.  _J Biomed Inform_ , 44(4):688–699.
  * Ficler and Goldberg (2016) Jessica Ficler and Yoav Goldberg. 2016.  A neural network for coordination boundary prediction.  In _EMNLP_ , pages 23–32, Austin, Texas.
  * Finkel and Manning (2009) Jenny Rose Finkel and Christopher Manning. 2009.  Nested named entity recognition.  In _EMNLP_ , pages 141–150, Singapore.
  * Graves et al. (2013) Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. 2013.  Speech recognition with deep recurrent neural networks.  In _ICASSP_ , pages 6645–6649.
  * Johnson et al. (2016) Alistair EW Johnson, Tom J Pollard, Lu Shen, H Lehman Li-wei, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark. 2016.  MIMIC-III, A freely accessible critical care database.  _Sci. Data_ , 3:160035.
  * Karimi et al. (2015a) Sarvnaz Karimi, Alejandro Metke-Jimenez, Madonna Kemp, and Chen Wang. 2015a.  CADEC: A corpus of adverse drug event annotations.  _J Biomed Inform_ , 55:73–81.
  * Karimi et al. (2015b) Sarvnaz Karimi, Chen Wang, Alejandro Metke-Jimenez, Raj Gaire, and Cécile Paris. 2015b.  Text and data mining techniques in adverse drug reaction detection.  _ACM Comput. Surv._ , 47(4):56:1–56:39.
  * Katiyar and Cardie (2018) Arzoo Katiyar and Claire Cardie. 2018.  Nested named entity recognition revisited.  In _NAACL_ , pages 861–871, New Orleans, Louisiana.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016.  Neural architectures for named entity recognition.  In _NAACL_ , pages 260–270, San Diego, California.
  * Leaman et al. (2015) Robert Leaman, Ritu Khare, and Zhiyong Lu. 2015.  Challenges in clinical natural language processing for automated disorder normalization.  _J Biomed Inform_ , 57:28–37.
  * Leaman et al. (2010) Robert Leaman, Laura Wojtulewicz, Ryan Sullivan, Annie Skariah, Jian Yang, and Graciela Gonzalez. 2010.  Towards internet-age pharmacovigilance: Extracting adverse drug reactions from user posts in health-related social networks.  In _BioNLP_ , pages 117–125, Uppsala, Sweden.
  * Lou et al. (2017) Yinxia Lou, Yue Zhang, Tao Qian, Fei Li, Shufeng Xiong, and Donghong Ji. 2017.  A transition-based joint model for disease named entity recognition and normalization.  _Bioinformatics_ , 33(15):2363–2371.
  * Lu and Roth (2015) Wei Lu and Dan Roth. 2015.  Joint mention extraction and classification with mention hypergraphs.  In _EMNLP_ , pages 857–867, Lisbon, Portugal.
  * Luong et al. (2015) Thang Luong, Hieu Pham, and Christopher D. Manning. 2015.  Effective approaches to attention-based neural machine translation.  In _EMNLP_ , pages 1412–1421, Lisbon, Portugal.
  * Ma and Hovy (2016) Xuezhe Ma and Eduard Hovy. 2016.  End-to-end sequence labeling via bi-directional LSTM-CNNs-CRF.  In _ACL_ , pages 1064–1074, Berlin, Germany.
  * McDonald et al. (2005) Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005.  Flexible text segmentation with structured multilabel classification.  In _EMNLP_ , pages 987–994, Vancouver, British Columbia, Canada.
  * Metke-Jimenez and Karimi (2016) Alejandro Metke-Jimenez and Sarvnaz Karimi. 2016.  Concept identification and normalisation for adverse drug event discovery in medical forums.  In _BMDID@ISWC_ , Kobe, Japan.
  * Mowery et al. (2014) Danielle L Mowery, Sumithra Velupillai, Brett R South, Lee Christensen, David Martinez, Liadh Kelly, Lorraine Goeuriot, Noemie Elhadad, Sameer Pradhan, Guergana Savova, and Wendy W Chapman. 2014.  Task 2: ShARe/CLEF ehealth evaluation lab 2014.  In _CLEF_.
  * Muis and Lu (2016) Aldrian Obaja Muis and Wei Lu. 2016.  Learning to recognize discontiguous entities.  In _EMNLP_ , pages 75–84, Austin, Texas.
  * Peters et al. (2018) Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep contextualized word representations.  In _NAACL_ , pages 2227–2237, New Orleans, Louisiana.
  * Peters et al. (2019) Matthew E. Peters, Sebastian Ruder, and Noah A. Smith. 2019.  To tune or not to tune? adapting pretrained representations to diverse tasks.  In _RepL4NLP@ACL_ , pages 7–14, Florence, Italy.
  * Pradhan et al. (2013) Sameer Pradhan, Noemie Elhadad, Brett R South, David Martinez, Lee M Christensen, Amy Vogel, Hanna Suominen, Wendy W Chapman, and Guergana K Savova. 2013.  Task 1: ShARe/CLEF ehealth evaluation lab 2013.  In _CLEF_.
  * Ringland et al. (2019) Nicky Ringland, Xiang Dai, Ben Hachey, Sarvnaz Karimi, Cecile Paris, and James R. Curran. 2019.  NNE: A dataset for nested named entity recognition in english newswire.  In _ACL_ , pages 5176–5181, Florence, Italy.
  * Sarker et al. (2015) Abeed Sarker, Rachel Ginn, Azadeh Nikfarjam, Karen O’Connor, Karen Smith, Swetha Jayaraman, Tejaswi Upadhaya, and Graciela Gonzalez. 2015.  Utilizing social media data for pharmacovigilance: a review.  _J Biomed Inform_ , 54:202–212.
  * Shen et al. (2015) Wei Shen, Jianyong Wang, and Jiawei Han. 2015.  Entity linking with a knowledge base: Issues, techniques, and solutions.  _IEEE Trans. Knowl. Data Eng._ , 27(2):443–460.
  * Sohrab and Miwa (2018) Mohammad Golam Sohrab and Makoto Miwa. 2018.  Deep exhaustive model for nested named entity recognition.  In _EMNLP_ , pages 2843–2849, Brussels, Belgium.
  * Stanovsky et al. (2017) Gabriel Stanovsky, Daniel Gruhl, and Pablo Mendes. 2017.  Recognizing mentions of adverse drug reaction in social media using knowledge-infused recurrent models.  In _EACL_ , pages 142–151, Valencia, Spain.
  * Stenetorp et al. (2012) Pontus Stenetorp, Sampo Pyysalo, Goran Topić, Tomoko Ohta, Sophia Ananiadou, and Jun’ichi Tsujii. 2012.  brat: a web-based tool for NLP-assisted text annotation.  In _EACL_ , pages 102–107, Avignon, France.
  * Tang et al. (2013a) Buzhou Tang, Hongxin Cao, Yonghui Wu, Min Jiang, and Hua Xu. 2013a.  Recognizing clinical entities in hospital discharge summaries using structural support vector machines with word representation features.  In _BMC Med Inform Decis Mak_ , volume 13, page S1.
  * Tang et al. (2018) Buzhou Tang, Jianglu Hu, Xiaolong Wang, and Qingcai Chen. 2018.  Recognizing continuous and discontinuous adverse drug reaction mentions from social media using LSTM-CRF.  _Wirel Commun Mob Com_ , 2018.
  * Tang et al. (2013b) Buzhou Tang, Yonghui Wu, Min Jiang, and Joshua C. Denny. 2013b.  Recognizing and encoding disorder concepts in clinical text using machine learning and vector space model.  In _CLEF_.
  * Wang and Lu (2019) Bailin Wang and Wei Lu. 2019.  Combining spans into entities: A neural two-stage approach for recognizing discontiguous entities.  In _EMNLP_ , pages 6215–6223, Hong Kong, China.
  * Wang et al. (2018a) Bailin Wang, Wei Lu, Yu Wang, and Hongxia Jin. 2018a.  A neural transition-based model for nested mention recognition.  In _EMNLP_ , pages 1011–1017, Brussels, Belgium.
  * Wang et al. (2018b) Yanshan Wang, Liwei Wang, Majid Rastegar-Mojarad, Sungrim Moon, Feichen Shen, Naveed Afzal, Sijia Liu, Yuqun Zeng, Saeed Mehrabi, Sunghwan Sohn, and Hongfang Liu. 2018b.  Clinical information extraction applications: A literature review.  _J Biomed Inform_ , 77:34–49.
  * Watanabe and Sumita (2015) Taro Watanabe and Eiichiro Sumita. 2015.  Transition-based neural constituent parsing.  In _ACL-IJCNLP_ , pages 1169–1179, Beijing, China.
  * Xu et al. (2017) Mingbin Xu, Hui Jiang, and Sedtawut Watcharawittayakul. 2017.  A local detection approach for named entity recognition and mention detection.  In _ACL_ , pages 1237–1247, Vancouver, Canada.


# Progressive Multi-resolution Loss for Crowd Counting

Ziheng Yan1 Yuankai Qi2 Guorong Li1 Xinyan Liu1
Weigang Zhang3 Qingming Huang1,4,5 Ming-Hsuan Yang6
1University of Chinese Academy of Science, Beijing, China
2Australian Institute for Machine Learning, The University of Adelaide
3Harbin Institute of Technology, Weihai, China,
4Key Lab of Intell. Info. Process., Inst. of Comput. Tech., CAS, Beijing,
China
5Peng Cheng Laboratory, Shenzhen, China, 6University of California, Merced
{yanziheng21<EMAIL_ADDRESS><EMAIL_ADDRESS>
{liguorong<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author.

###### Abstract

Crowd counting is usually handled in a density map regression fashion, which
is supervised via a L2 loss between the predicted density map and ground
truth. To effectively regulate models, various improved L2 loss functions have
been proposed to find a better correspondence between predicted density and
annotation positions. In this paper, we propose to predict the density map at
one resolution but measure the density map at multiple resolutions. By
maximizing the posterior probability in such a setting, we obtain a log-formed
multi-resolution L2-difference loss, where the traditional single-resolution
L2 loss is its particular case. We mathematically prove it is superior to a
single-resolution L2 loss. Without bells and whistles, the proposed loss
substantially improves several baselines and performs favorably compared to
state-of-the-art methods on four crowd counting datasets, ShanghaiTech A & B,
UCF-QNRF, and JHU-Crowd++.

##  1 Introduction

Crowd counting aims to count the number of humans in a crowd scene, which has
drawn increasing attention in recent years due to its wide applications in the
real world. Most existing methods generate a density map from the input image
and then match it to the corresponding dot annotations. One significant
challenge in crowd counting is to associate the pixels of the predicted
density map to the target dot annotations in a reasonable way.

Figure 1: Modeling the correspondence of predicted density map and ground
truth annotation: (a) Using Gaussian kernel to convert ground truth point
annotation to density map. Then pixels at the same coordinates are viewed and
matched. (b) Using Bayes’ theorem to find the ground truth annotation for a
pixel in the predicted density map. (c) Using Optimal Transport of a cost
matrix of displacement distance to find the correspondence. (d) We also view
pixels at the same coordinates as matched but we propose to measure the
similarity between the generated density map and the ground truth map at
multiple resolutions. By maximizing its posterior probability, we derive a new
loss, where the traditional single-resolution L2 loss is its particular case.

Currently, there are three main types of methods to establish the association
of pixels between the predicted density map and the ground truth annotations:
(i) Gaussian kernel as shown in Fig. 1(a). Ground truth dot annotations are
converted to a density map by placing a Gaussian kernel at each annotation
point. Then, L2 distance loss is used to narrow the gap between pixels at the
same locations of the predicted density map and the converted ground truth
density map [9, 38, 27, 31]. These methods focus on designing algorithms for
selecting the Gaussian kernel bandwidth to generate a high-quality ground
truth density map. (ii) Bayesian Inference (BI) as shown in Fig. 1(b). Instead
of generating density maps from point annotations, BI [19] computes the
posterior probability of a pixel location in the predicted density map
according to Bayes’ theorem to infer its corresponding ground truth
annotation. (iii) Optimal Transport (OT) as shown in Fig. 1(c). As opposed to
the above indirect approaches, a direct distance measurement based on optimal
transport (OT) theory [33, 29] is proposed to find the best match between the
predictions and annotations in an end-to-end way. OT no longer requires the
setting of Gaussian kernel bandwidth but relies on a cost matrix that reflects
the distance between pixels of the predicted density map and ground truth
annotation. Different from the above-mentioned methods, we view pixels at the
same coordinates that are matched, but we propose to measure the similarity
between a predicted density map and the ground truth under multiple
resolutions. By maximizing the posterior probability in such a setting, we
derive a log-formed L2-difference based loss, where the traditional single-
resolution loss is its particular case. We theoretically prove that the
derived multi-resolution loss is superior to a single-resolution L2 loss.
Without bells and whistles, the proposed loss brings substantial performance
improvement over baselines and favorable performance against state-of-the-art
methods on four crowd counting benchmark datasets, ShanghaiTech A & B, UCF-
QNRF, and JHU-Crowd++.

##  2 Related Work

Counting based on L2 regression of density map. Counting based on density maps
is first proposed in [9]. Unlike previous methods of detection and
localization for counting, this method transforms the counting problem into
estimating object density, and the sum of the densities in a region is viewed
as the total number of objects in that region. Density map regression is
implemented by minimizing a regularized risk quadratic cost function. To this
end, a ground truth density map is used in supervised learning. Specifically,
the density map is generated by placing a fixed-bandwidth Gaussian kernel at
each annotated point. However, the geometry of the scene and perspective
effects can lead to distortion of the generated density map [38]. When the
density of objects is considered to be evenly distributed, the average
distance between the center and its nearest neighbors gives a reasonable
estimate of the geometric distortion. Under this assumption, [38] proposes to
specify the bandwidth of the Gaussian kernel for each annotated point to the
average distance from the neighbors. In [27], it is suggested that specific
density maps designed manually may not be optimal for the end-to-end training
process. To address this issue, a framework for generating density maps is
proposed in [27], which improves the quality of density maps by fusing blurred
density maps generated by various Gaussian kernels.

Crowd counting based on Bayesian Inference. Bayesian loss (BL) [19], no longer
using low-quality density maps generated by Gaussian kernels, constructs a
density contribution probability model from the point annotations. Compared to
pixel-wise L2 regression methods, L1 regression is performed point-wisely in
BL between the annotated points and the contributions of the density map.
Bayesian theory plays the role of converting prior probabilities into
posterior contributions in this process. Because the computation of
contributions in regions far from the annotated points is not always correct,
BL introduces background modeling so that the predicted density on the
background can be counted as zero. In [7], BL is further improved on
background probability modeling, allowing BL to adapt to scale variations of
people.

Crowd counting based on Optimal Transport. DM-Count [33] theoretically and
empirically shows that the generalization performance can be hurt by the
“ground truth” density map smoothed by Gaussian kernels from point
annotations. DM-Count views crowd counting as a distribution matching problem.
It uses Optimal Transport (OT) to find the best match between generated
density map and point annotations. The solution of the optimal transport is
iteratively approximated by using the Sinkhorn algorithm [20] with a cost
matrix. GL [29] follows the work on matching the distribution of density maps
using OT with a modified cost matrix that concerns the perspective effect in
crowd images. GL changes the form of OT used in counting so that the density
map matches the point annotations directly without normalization of the
predicted density map, which also makes L2 and BL sub-optimal solutions to the
deformed OT problem.

##  3 Proposed Method

In this section, we first formulate the crowd counting task as a probability
maximization problem. Then we derive the optimization loss for deep learning
model by maximizing the posterior probability, during which we also show the
resulting loss function is superior to a single-resolution L2 loss.

Figure 2: Downsampling density map from $8\times 8$ to $2\times 2$.

###  3.1 Problem formulation

Let $\hat{\bm{y}}=f(\mathbf{x})\in\mathbb{R}^{2^{L}\times 2^{L}}$ represent
the predicted density map, where $f$ is a counting model, $\mathbf{x}$ is an
input image, and $2^{L}\times 2^{L}$ is the resolution of the predicted
density map. Let $\bm{y}_{ori}$ be the original point annotation map, of which
each element is 1 or 0, denoting the occupancy of one person or object. We
convert $\bm{y}_{ori}$ to $\bm{y}\in\mathbb{R}^{2^{L}\times 2^{L}}$ by evenly
dividing it into $2^{L}\times 2^{L}$ grids and the sum of the annotations in
each grid is used as the new pixel value in $\bm{y}$ as shown in Fig. 2.

In addition to measuring the similarity between $\hat{\bm{y}}$ and $\bm{y}$ on
the resolution $2^{L}\times 2^{L}$ as existing methods, we propose to also
measure the similarity at multiple sub-resolutions: $2^{i}\times
2^{i},i\in\\{n_{0},n_{1},\cdots,n_{k}\\}$, where $n_{i}$ is an integer,
$n_{i}<n_{i+1}$ and $k<L$. Predicted density map $\hat{\bm{y}}_{2^{i}}$ and
ground truth annotation map ${\bm{y}}_{2^{i}}$ at resolution $2^{i}\times
2^{i}$ can be obtained by evenly dividing $\hat{\bm{y}}$ or $\bm{y}$ into
$2^{i}\times 2^{i}$ grids and summing the elements in each grid to get the
value for each element in the new resolution. In such a setting, training a
model $f$ is to maximize the posterior probability
$p(\bm{y}=\bm{y}_{2^{L}},\bm{y}_{2^{n_{k}}},\cdots,\bm{y}_{2^{n_{0}}}|\mathbf{x})$
on resolutions $\mathbb{N}=\\{n_{0},n_{1},\cdots,n_{k},L\\}$. According to the
chain rule of conditional probability, and because $\bm{y}_{2^{n_{i+1}}}$
contains all the information in $\bm{y}_{2^{n_{i}}}$ and $\bm{y}$ contains all
the information in $\bm{y}_{2^{n_{k}}}$, the posterior probability can be
decomposed

$\displaystyle p(\bm{y}|\mathbf{x},\mathbb{N})\overset{def}{=}$ $\displaystyle
p(\bm{y},\bm{y}_{2^{n_{k}}},\cdots,\bm{y}_{2^{n_{0}}}|\mathbf{x})$ (1)
$\displaystyle=$ $\displaystyle
p(\bm{y}|\bm{y}_{2^{n_{k}}},\mathbf{x})\left[\prod\limits_{j=0}^{k-1}p(\bm{y}_{2^{n_{j+1}}}|\bm{y}_{2^{n_{j}}},\mathbf{x})\right]p(\bm{y}_{2^{n_{0}}}|\mathbf{x}).$

The goal of training the model $f$ is equivalent to maximizing the marginal
likelihood

$f^{*}=\arg\max_{f}\mathbb{E}_{D}\log
p(\bm{y},\bm{y}_{2^{n_{k}}},\cdots,\bm{y}_{2^{n_{0}}}|\mathbf{x}).$ (2)

In the following we prove that the above marginal likelihood is further
equivalent to minimizing the loss in Section 3.5.

###  3.2 From posterior probability maximization to the loss function

In existing methods [12, 2, 3], the posterior probability of the number of
objects is set to be independent, identically distributed (i.i.d.), Gaussian.
Since the dimension of the $\bm{y}_{2^{n_{0}}}$ is $4^{n_{0}}=2^{n_{0}}\times
2^{n_{0}}$, we additionally assumes that the pixels of $\bm{y}_{2^{n_{0}}}$
are i.i.d. Gaussian,

$p(\bm{y}_{2^{n_{0}}}|\mathbf{x})\sim\mathcal{N}(\hat{\bm{y}}_{2^{n_{0}}},\sigma_{0}^{2}\mathbf{I}_{4^{n_{0}}}),$
(3)

where $\sigma_{0}^{2}$ is the parameter of Gaussian distribution,
$\mathbf{I}_{4^{n_{0}}}$ is a $4^{n_{0}}\times 4^{n_{0}}$ identity matrix.
When we make this assumption, the conventional single-resolution L2 loss
function becomes a particular case of our posterior distribution that
$\mathbb{N}=\\{n_{k},L\\}$ and
$p(\bm{y}|\bm{y}_{2^{n_{k}}},\mathbf{x})=p(\bm{y}|\bm{y}_{2^{n_{k}}})$.

We aim to learn the high-resolution density maps without destroying the lower-
resolution maps as much as possible. In order to keep the low-density map
unaffected, We define that the residual density map
$\bm{r}_{{j_{1}},{j_{2}}}$, $\hat{\bm{r}}_{{j_{1}},{j_{2}}}$ between two
density maps with different resolutions $2^{j_{1}}$ and $2^{j_{2}}$ ,

$\displaystyle\bm{r}_{{j_{1}},{j_{2}}}$
$\displaystyle\overset{def}{=}\bm{y}_{2^{{j_{2}}}}-4^{{j_{1}}-{j_{2}}}\mathbf{U}(\bm{y}_{2^{{j_{1}}}},2^{j_{2}-j_{1}}),$
(4) $\displaystyle\hat{\bm{r}}_{{j_{1}},{j_{2}}}$
$\displaystyle\overset{def}{=}\hat{\bm{y}}_{2^{{j_{2}}}}-4^{{j_{1}}-{j_{2}}}\mathbf{U}(\hat{\bm{y}}_{2^{j_{1}}},2^{j_{2}-j_{1}}),$
(5)

where $j_{1}<j_{2}$, $\mathbf{U}(\cdot,2^{j_{2}-j_{1}})$ is the replication
upsampling function of scale $2^{j_{2}-j_{1}}$. We assume that the residual
maps $\bm{r}_{n_{j},n_{j+1}}$ are generated from Gaussian distribution, which
means

$\displaystyle
p(\bm{r}_{n_{j},n_{j+1}}|\mathbf{x})\sim\mathcal{N}(\hat{\bm{r}}_{n_{j},n_{j+1}},\sigma_{j+1}^{2}\mathbf{I}_{4^{n_{j+1}}}),$
(6)

where $\sigma_{j+1}^{2}$ is the variance parameter of the Gaussian
distributions. $\bm{r}_{n_{j+1},n_{j}}$ needs to satisfy the priors that
$\mathbf{D}(r_{n_{j+1},n_{j}},2^{n_{j+1}-n_{j}})=\mathbf{0}_{4^{n_{j}}}$,
where $\mathbf{0}_{4^{n_{j}}}$ is the zero vector of length $4^{n_{j}}$,
$\mathbf{D}(\cdot,2^{n_{j+1}-n_{j}})$ is the average downsampling function of
scale $2^{n_{j+1}-n_{j}}$. The conditional probability
$p(\bm{y}_{2^{n_{j+1}}}|\bm{y}_{2^{n_{j}}},\mathbf{x})$ has the following
form,

$\displaystyle
p(\bm{y}_{2^{n_{j+1}}}|\bm{y}_{2^{n_{j}}},\mathbf{x})=p(\bm{r}_{{n_{j}},n_{j+1}}|\bm{y}_{2^{n_{j}}},\mathbf{x})$
(7) $\displaystyle=$
$\displaystyle\frac{p(\bm{r}_{{n_{j}},n_{j+1}}|,\mathbf{x})}{\int
p(\bm{v}_{{n_{j+1}},n_{j}}|,\mathbf{x})\mathbb{I}(\mathbf{D}(\bm{v}_{{n_{j+1}},n_{j}})=\mathbf{0}_{4^{n_{j}}})d\bm{v}}$
$\displaystyle=$
$\displaystyle\frac{\mathcal{N}(\hat{\bm{r}}_{n_{j},n_{j+1}},\sigma_{j+1}^{2}\mathbf{I}_{4^{n_{j+1}}})}{\mathcal{N}(\bm{0}_{4^{n_{j}}},4^{n_{j+1}-n_{j}}\sigma_{j+1}^{2}\mathbf{I}_{4^{n_{j}}})}$
$\displaystyle=$
$\displaystyle\sqrt{\frac{4^{(n_{j}-n_{j+1})4^{n_{j}}}}{(2\pi\sigma_{j+1}^{2})^{4^{n_{j+1}-n_{j}}}}}\exp\\{-\frac{1}{2\sigma_{j+1}^{2}}\|\hat{\bm{r}}_{n_{j},n_{j+1}}-\bm{r}_{n_{j},n_{j+1}}\|_{2}^{2}\\},$

where $\mathbb{I}(\cdot)$ is the indicator function.

Combining Eq. (1)(3)(7), the marginal likelihood of the training data $D$
equals to a linear combination of
$\mathcal{L}_{diff}^{n_{j},n_{j+1}},j=0,\cdots,k-1$ ,and
$\mathcal{L}_{2}^{n_{0}}$:

$\displaystyle\mathbb{E}_{D}$ $\displaystyle\log
p(\bm{y}|\mathbf{x},\mathbb{N})=\mathbb{E}_{D}\ \log
p(\bm{y}|\bm{y}_{2^{n_{k}}},\mathbf{x})-$ (8)
$\displaystyle\dfrac{1}{2}\sum_{j=1}^{k-1}[\frac{1}{\sigma_{j+1}^{2}}\mathcal{L}_{diff}^{n_{j},n_{j+1}}+(4^{n_{j+1}}-4^{n_{j}})\log(2\pi\sigma_{j+1}^{2})$
$\displaystyle+$ $\displaystyle(n_{j+1}-n_{j})4^{n_{j}}\log
4]-\frac{1}{2}(\frac{1}{\sigma_{0}^{2}}\mathcal{L}_{2}^{n_{0}}+4^{n_{0}}\log(2\pi\sigma_{0}^{2})),$

where

$\displaystyle\mathcal{L}^{i}_{2}\overset{def}{=}\mathbb{E}_{D}\|\hat{\bm{y}}_{2^{i}}-\bm{y}_{2^{i}}\|_{2}^{2},$
(9) $\displaystyle\begin{aligned}
\mathcal{L}^{n_{j},n_{j+1}}_{diff}\overset{def}{=}&\mathcal{L}^{n_{j+1}}_{2}-4^{n_{j}-n_{j+1}}\mathcal{L}^{n_{j}}_{2}\\\
=&\mathbb{E}_{D}\|\bm{r}_{n_{j},n_{j+1}}-\hat{\bm{r}}_{n_{j},n_{j+1}}\|_{2}^{2}.\end{aligned}$
(10)

Remark: Only the density map-based methods are discussed in this paper, so the
model does not include a localization branch. Therefore,
$p(\bm{y}|\bm{y}_{2^{n_{k}}},\mathbf{x})$ does not appear in the final loss
function. In the case of crowd localization, $\mathbb{E}_{D}\ \log
p(\bm{y}|\bm{y}_{2^{n_{k}}},\mathbf{x})$ corresponds to the loss function of
the localization branch.

###  3.3 Selection of $\mathbb{N}$

By calculating the derivatives of Eq. (8), the optimal solution of
$\bm{\sigma}=\\{\sigma_{n_{j}}|j=0,\cdots,k\\}$ is obtained,

$\displaystyle\sigma_{j}^{2}$
$\displaystyle=\frac{\mathcal{L}_{diff}^{n_{j-1},n_{j}}}{4^{n_{j}}-4^{n_{j-1}}},\forall
j\in\\{1,\cdots,k\\},$ (11) $\displaystyle\sigma_{0}^{2}$
$\displaystyle=4^{-n_{0}}\mathcal{L}_{2}^{n_{0}}.$

Then taking it to Eq. (8), the marginal likelihood of the training data can be
simplified,

$\displaystyle\max\limits_{\bm{\sigma}}\mathbb{E}_{D}$ $\displaystyle\log
p(\bm{y}|\mathbf{x},\mathbb{N})$ (12) $\displaystyle=$
$\displaystyle\mathbb{E}_{D}\ \log
p(\bm{y}|\bm{y}_{2^{n_{k}}},\mathbf{x})-\dfrac{-1+2\pi}{2}4^{n_{k}}$
$\displaystyle-\dfrac{1}{2}\sum_{j=1}^{k}(4^{n_{j}}-4^{n_{j-1}})\log\dfrac{4^{n_{j}}\mathcal{L}_{diff}^{n_{j-1},n_{j}}}{4^{n_{j}}-4^{n_{j-1}}}$
$\displaystyle-\dfrac{1}{2}4^{n_{0}}\log\mathcal{L}_{2}^{n_{0}},$

where $\bm{\sigma}=\\{\sigma_{0},\cdots,\sigma_{k}\\}$. To guide the choice of
$\mathbb{N}$, we prove the following theorem.

###### Theorem 1

Let $\mathbb{N}^{\prime}=\\{0,1,\cdots,n_{k}\\}\cup\\{L\\}$. Then the log-
likelihood function in case of $\mathbb{N}^{\prime}$ is greater than that of
$\mathbb{N}$,

$\max\limits_{\bm{\sigma}}\mathbb{E}_{D}\log
p(\bm{y}|\mathbf{x},\mathbb{N})\leq\max\limits_{\bm{\sigma}}\mathbb{E}_{D}\log
p(\bm{y}|\mathbf{x},\mathbb{N}^{\prime}).$ (13)

The proof of this theorem can be found in the supplementary material.

This theorem tells us that measuring the predicted density map at $n_{k}$
additional resolutions starting from $2^{0}\times 2^{0}$ leads to a better
fitting of the training data than merely using resolution $2^{n_{k}}\times
2^{n_{k}}$.

When $\mathbb{N}=\\{0,1,\cdots,n\\}\cup\\{L\\}$, the Eq. (12) is equal to

$\displaystyle\max\limits_{\bm{\sigma}}\mathbb{E}_{D}\log
p(\bm{y}|\mathbf{x},\mathbb{N})=\mathbb{E}_{D}\ \log
p(\bm{y}|\bm{y}_{2^{n}},\mathbf{x})-\dfrac{-1+2\pi}{2}4^{n}$ (14)
$\displaystyle-\dfrac{1}{2}\sum_{j=1}^{n}(4^{j}-4^{{j-1}})\log\dfrac{4}{3}\mathcal{L}_{diff}^{{j-1},{j}}-\dfrac{1}{2}\log\mathcal{L}_{2}^{0}.$

Figure 3: Illustration of multi-resolution loss.

###  3.4 Regularization

In the previous analysis, no additional restrictions are added to the variance
$\sigma_{j}^{2}$. Therefore, we add penalty terms to regularize them to limit
the range of variance,

$\displaystyle\mathcal{L}_{reg}=\sum_{j=0}^{n}\beta_{j}\sigma_{j}^{2}.$ (15)

Since this form is too complex and has too many parameters, we simplify it to
one regular term $\mathcal{L}_{2}^{n}$ by taking appropriate
$\beta_{0},\cdots,\beta_{n}$.

In Eq. (14), the term $\log\mathcal{L}_{diff}^{n,n-1}$ has the largest
coefficient, which makes model learning mainly based on this resolution.
Therefore, We want the model to learn by combining multiple resolutions.

Because the second two terms in Eq. (14) are constants, our loss function is
obtained by re-weighting the coefficients of the rest of the equation. The
process of re-weighting coefficients is equivalent to a weighted average of
log-likelihood functions with different $n$. The formulaic representation is
as follows,

$\displaystyle\sum_{k=0}^{n}\alpha_{k}[\sum_{j=1}^{k}(4^{j}-4^{j-1})\log\mathcal{L}_{diff}^{j-1,j}+\log\mathcal{L}_{2}^{0}]$
(16) $\displaystyle=$
$\displaystyle\log\mathcal{L}_{2}^{0}+\sum_{j=1}^{n}\log\mathcal{L}_{diff}^{j-1,j},$

where $\alpha_{k}$ is the coefficient for the resolution of $2^{k}\times
2^{k}$ and $\alpha_{0},\cdots,\alpha_{n}$ are the solution of
$(4^{j}-4^{j-1})\sum_{k=j}^{n}\alpha_{k}=1,\forall j\in\\{1,\cdots,n\\}$,
$\sum_{k=0}^{n}\alpha_{k}=1$.

###  3.5 Progressive Multi-resolution Loss

The progressive multi-resolution loss is defined as

$\mathcal{L}_{PML}=\log\mathcal{L}^{0}_{2}+\sum_{j=1}^{n}\log\mathcal{L}^{j-1,j}_{diff}.$
(17)

When the regular term $\mathcal{L}_{2}^{L}$ is added, the final loss function
is defined by:

$\mathcal{L}=\mathcal{L}_{PML}+\mathcal{L}_{2}^{L}.$ (18)

Fig. 3 shows an illustration of the loss used in the proposed model.

| JHU-Crowd++ | UCF-QNRF | ShanghaiTech A | ShanghaiTech B
---|---|---|---|---
| MAE $\downarrow$ | MSE $\downarrow$ | MAE $\downarrow$ | MSE $\downarrow$ | MAE $\downarrow$ | MSE $\downarrow$ | MAE $\downarrow$ | MSE $\downarrow$
FIDT [11] | 66.6 | 253.6 | 89.0 | 153.5 | 57.0 | 103.4 | 6.9 | 11.8
Ours + FIDT | 62.3(-4.3) | 261.9(+8.3) | 87.2(-1.8) | 151.9(-1.6) | 54.5(-2.5) | 92.7(-10.7) | 6.9(-0.0) | 9.8(-2.0)
FDC-18 [14] | - | - | 93.0 | 157.3 | 65.4 | 109.2 | 11.4 | 19.1
Ours + FDC-18 | - | - | 82.1(-10.9) | 153.5(-3.8) | 62.3(-3.1) | 101.1(-8.1) | 6.7(-4.7) | 10.8(-8.3)
FDC-ConvNeXtS | 61.3 | 275.2 | 83.2 | 156.7 | 59.2 | 97.3 | 7.0 | 11.1
Ours + FDC-ConvNeXtS | 55.2(-6.1) | 232.4(-42.8) | 79.9(-3.3) | 132.5(-24.2) | 53.4(-5.8) | 93.1(-4.2) | 6.2(-0.8) | 9.7(-1.4)

Table 1: Combination with open source state-of-the-art methods. RED indicates
the decrease in MAE and MSE compared with the original methods.

##  4 Experiments

In this section, we present experiments using our loss function, which
contains comparisons with SOTA methods and ablation studies.

###  4.1 Experiment settings

Datasets | Number of objects | #Train | #Test
---|---|---|---
JHU-Crowd++ [25] | [0, 7,286] | 2,722 | 1,600
UCF-QNRF [6] | [49, 12,865] | 1,201 | 334
ShanghaiTech A [38] | [33, 3,139] | 482 | 300
ShanghaiTech B [38] | [9, 578] | 716 | 400
Table 2: Crowd counting benchmarks. The second column represents the range of the number of objects per image. #Train and #Test represent the size of the training and test image sets.  |  | JHU-Crowd++ | UCF-QNRF | ShanghaiTech A | ShanghaiTech B
---|---|---|---|---|---
|  | MAE $\downarrow$ | MSE $\downarrow$ | MAE $\downarrow$ | MSE $\downarrow$ | MAE $\downarrow$ | MSE $\downarrow$ | MAE $\downarrow$ | MSE $\downarrow$
BL [19] | ICCV’19 | 75.0 | 299.9 | 88.7 | 154.8 | 62.8 | 101.8 | 7.7 | 12.7
NoiseCC [28] | NeurIPS’20 | 67.7 | 258.5 | 85.8 | 150.6 | 61.9 | 99.6 | 7.4 | 11.3
DM count [33] | NeurIPS’20 | 68.4 | 283.3 | 85.6 | 148.3 | 59.7 | 95.7 | 7.4 | 11.8
GL [29] | CVPR’21 | 59.9 | 259.5 | 84.3 | 147.5 | 61.3 | 95.4 | 7.3 | 11.7
Ours |  | 57.5 | 227.0 | 80.1 | 131.2 | 61.1 | 104.8 | 6.6 | 10.8
Table 3: Comparison with state-of-the-art loss functions. Figure 4:  Density
maps of our loss function combined with FIDT [11] on JHU-Crowd++. Differences
in density maps are highlighted with rectangular areas. (a) Input images. (b)
The ground truth density maps. (c) The predicted density maps of FIDT. (d) The
predicted density maps of our loss function combined with FIDT.

Dataset and Augmentation. Our proposed loss function is evaluated on four
datasets of crowd people counting: ShanghaiTech A and B [38], UCF-QNRF [6],
and JHU-Crowd++ [25]. Except for JHU-Crowd++, which has a size of 500
verification sets, the other three datasets have no verification sets. Table 2
summarizes the datasets. During the training, we sequentially use the
following data augmentation: Color Jitter, Rand Scaling (from 0.9 to 1.1),
Random crop (to 1024x1024), Random Rotate (from 0 to 45), and Horizontal Flip
(with the probability of 0.5). In the inference phase, we limit the longest
edge within 1536 and pad the image size to an integer multiple of 64.

Criteria. The Mean Absolute Error (MAE) and the Root Mean Square Error (MSE)
are measures of the performance of the models in previous works [30, 35]:

$\displaystyle MAE$
$\displaystyle=\frac{1}{K}\sum_{k=1}^{K}|\hat{m}_{k}-m_{k}|,$ (19)
$\displaystyle MSE$
$\displaystyle=\sqrt{\frac{1}{K}\sum_{k=1}^{K}(\hat{m}_{k}-m_{k})^{2}},$

where $\hat{m}_{k}$ and $m_{k}$ are the estimated counting number and ground
truth counting number, the size of the entire test dataset is $K$.

Network Structures. We use VGG16 [23], CSRNet [10], ResNet18 [5], ConvNeXtS
[17], and HRNet-W48 [34] as the backbone of our models. VGG16 is a standard
pre-trained model for crowd counting, which uses only 3×3 convolution. We use
VGG16 to extract the features and then use two 1×1 convolutional layers with
ReLU activation functions as the prediction header. CSRNet, designed for crowd
counting with VGG16 as the backbone, employs four dilated convolution layers
with 512, 256, 128, and 64 channels in the prediction head. ResNet18 adds
direct connection channels to the network, allowing information to skip a
layer directly. ConvNeXt is a pure convolution model that can compete with
vision Transformers [4, 16] across multiple computer vision benchmarks.
ConvNeXtS is a variant of ConvNeXt with 96, 192, 384, and 768 channels in the
backbone. We add the same counting head in CSRNet to ResNet18 and ConvNext to
estimate the density maps. HRNet is a backbone widely used in localization
task . HRNet-W48 is its pre-trained model on ImageNet [8], and we use it to
provide multi-scale density map output.

Hyper-parameters. The Adam optimizer updates parameters with an initial
learning rate $10^{-4}$. As our loss gradient increases with the training
epochs, we adopt gradient clipping of 10 in the back-propagation. $n$ in Eq.
(17) is set to 4, which means we use the density maps with resolutions of
$1\times 1$, $2\times 2$, $4\times 4$, $8\times 8$, and $16\times 16$ in the
loss function.

###  4.2 Combination with state-of-the-art methods

We combine our loss function with open source SOTA methods (FIDT [11] and FDC
[14]) by using our loss to replace L2 loss in the counting regression of these
methods. For FDC, we reproduce the experiment with ConvNeXtS as the backbone
network and give a better result than the original method with ResNet18 [5].
Table 1 shows the fluctuations in MAE and MSE contributed from our loss
function, where MAEs decrease across all data sets and methods.

Fig. 4 shows the density maps of FIDT combined with our method. The density
maps of the original FIDT method deviate severely from the ground truth
density maps in some regions. Because our loss concerns the multi-resolution,
no significant deviations appear in these regions.

|  |  | JHU-Crowd++ | UCF-QNRF | ShanghaiTech A | ShanghaiTech B
---|---|---|---|---|---|---
|  | Backbone | MAE $\downarrow$ | MSE $\downarrow$ | MAE $\downarrow$ | MSE $\downarrow$ | MAE $\downarrow$ | MSE $\downarrow$ | MAE $\downarrow$ | MSE $\downarrow$
MCNN [38] | CVPR’16 | - | 188.9 | 483.4 | 277.0 | 426.0 | 110.2 | 173.2 | 26.4 | 41.3
SwitchCNN [22] | CVPR’17 | - | - | - | 228.0 | 445.0 | 90.4 | 135.0 | 21.6 | 33.4
CSRNet [10] | CVPR’18 | VGG16 | 85.9 | 309.2 | 110.6 | 190.1 | 68.2 | 115.0 | 10.6 | 16.0
SANet [1] | ECCV’18 | - | 91.1 | 320.4 | - | - | 67.0 | 104.5 | 8.4 | 13.6
CAN [13] | CVPR’19 | VGG16 | 100.1 | 314.0 | 107 | 183 | 62.3 | 100.0 | 7.8 | 12.2
SFCN [35] | CVPR’19 | ResNet101 | 77.5 | 297.6 | 102.0 | 171.4 | 64.8 | 107.5 | 7.6 | 13.0
MBTTBF [24] | ICCV’19 | VGG16 | 81.8 | 299.1 | 97.5 | 165.2 | 60.2 | 94.1 | 8.0 | 15.5
BL [19] | ICCV’19 | VGG19 | 75.0 | 299.9 | 88.7 | 154.8 | 62.8 | 101.8 | 7.7 | 12.7
KDMG [32] | TPAMI’20 | - | 69.7 | 268.3 | 99.5 | 173.0 | 63.8 | 99.2 | 7.8 | 12.7
LSC-CNN [21] | TPAMI’21 | - | 112.7 | 454.4 | 120.5 | 218.2 | 66.5 | 101.8 | 7.7 | 12.7
RPNet [37] | CVPR’20 | ResNet-101 | - | - | - | - | 61.2 | 96.9 | 8.1 | 11.6
AMRNet [15] | ECCV’20 | VGG16 | - | - | 86.6 | 152.2 | 61.6 | 98.4 | 7.0 | 11.0
NoiseCC [28] | NeurIPS’20 | VGG19 | 67.7 | 258.5 | 85.8 | 150.6 | 61.9 | 99.6 | 7.4 | 11.3
DM count [33] | NeurIPS’20 | VGG19 | 68.4 | 283.3 | 85.6 | 148.3 | 59.7 | 95.7 | 7.4 | 11.8
LA-Batch [39] | TPAMI’21 | VGG16 | - | - | 113.0 | 210.0 | 65.8 | 103.6 | 8.6 | 14.0
AutoScale [36] | IJCV’21 | VGG16 | 65.9 | 264.8 | 104.4 | 174.2 | 65.8 | 112.1 | 8.6 | 13.9
GL [29] | CVPR’21 | VGG19 | 59.9 | 259.5 | 84.3 | 147.5 | 61.3 | 95.4 | 7.3 | 11.7
P2PNet [26] | ICCV’21 | VGG16 | - | - | 85.3 | 154.5 | 52.7 | 85.1 | 6.2 | 9.9
SDA+BL [18] | ICCV’21 | VGG19 | 62.6 | 264.1 | 83.3 | 143.1 | 58.4 | 95.7 | - | -
FIDT [11] | arxiv | HRNet-W48 | 66.6 | 253.6 | 89.0 | 153.5 | 57.0 | 103.4 | 6.9 | 11.8
FDC-18 [14] | ICCV’21 | ResNet-18 | - | - | 93.0 | 157.3 | 65.4 | 109.2 | 11.4 | 19.1
FDC-ConvNeXtS |  | ConvNeXtS | 61.3 | 275.2 | 83.2 | 156.7 | 59.2 | 97.3 | 7.0 | 11.1
Ours + FIDT |  | HRNet-W48 | 62.3 | 261.9 | 87.2 | 151.9 | 54.5 | 92.7 | 6.9 | 9.8
Ours + FDC-18 |  | ResNet-18 | - | - | 82.1 | 153.5 | 62.3 | 101.1 | 6.7 | 10.8
Ours + FDC-ConvNeXtS |  | ConvNeXtS | 55.2 | 232.4 | 79.9 | 132.5 | 53.4 | 93.1 | 6.2 | 9.7
Ours + VGG16 |  | VGG16 | 57.5 | 227.0 | 80.1 | 131.2 | 61.1 | 104.8 | 6.6 | 10.8

Table 4: Comparison with state-of-the-art crowd Convnet methods.

###  4.3 Comparison with state-of-the-art loss functions

To evaluate the counting performance of our loss function, we compare VGG16
mentioned in Sec. 4 , which is trained by our loss defined in Eq. (18) with
previous state-of-art loss functions. Quantitative results on JHU-Crowd++,
UCF-QNRF, ShanghaiTech A, and ShanghaiTech B are shown in Table 3. We achieve
the lowest MAE/MSE on JHU-Crowd++, UCF-QNRF, and ShanghaiTech B. As for
ShanghaiTech A, our loss achieves the second-best performance in MAE.

###  4.4 Comparison with state-of-the-art methods

Table 4 shows the comparison between our loss and current SOTA. Despite the
fact that our method is simple, when combined with other methods, it achieves
results that have a stable decrease in MAE and MSE compared with the original
methods. Compared to all previous methods, our loss combined with ConvNeXtS
has a lower MAE and MSE on JHU-Crowd++, UCF-QNRF, and ShanghaiTech B than
previous works in the table. Although our counting performance on ShanghaiTech
A cannot exceed the performance of P2PNet [26] which is a purely point-based
framework, our method is faster than P2PNet and saves more memory in the
training phase.

###  4.5 Ablation study

Selecting appropriate resolutions for our loss is critical to counting
performance. Our ablation experiments aim to verify whether the regularization
is effective and what an appropriate $\mathbb{N}$ should be. As proved in Thm.
1, we only need to consider the situation that
$\mathbb{N}=\\{0,1,\cdots,n\\}\cup\\{L\\}$. Fig. 5 shows the performance on
JHU-Crowd++, with $n$ from zero to five. The model used in the ablation
experiments is Csrnet referred to in Sec. 4. We did ablation experiments using
the L2 norm as a regularization term. The experimental results show that it
can improve performance a little. The regularization term can reduce the
average validation MAE by 2.07 and test MAE values by 2.83 on the JHU-Crowd++.

Figure 5: Validation MAE (left) and test MAE (right) of $\mathcal{L}_{PML}$
(blue curve) and $\mathcal{L}_{PML}+\mathcal{L}_{2}^{L}$ (red curve) on JHU-
Crowd++. $\mathcal{L}_{PML}$ and $\mathcal{L}_{PML}+\mathcal{L}_{2}^{L}$ are
from Eq. (17) and Eq. (18) respectively. The curves show the counting
performances for $n$ with CSRNet as backbone.

##  5 Conclusions

In this paper, we propose a simple and efficient loss function called PML for
crowd counting. Our loss function, derived from the marginal likelihood, is
proved to fit the posterior distribution better than L2 loss theoretically. By
taking advantage of the multi-resolution density map, PML can learn to use
multi-scale information to improve counting performance. We have demonstrated
our loss function on four datasets with three common backbones in crowd
counting with competitive results.

## References

  * [1] Xinkun Cao, Zhipeng Wang, Yanyun Zhao, and Fei Su.  Scale Aggregation Network for Accurate and Efficient Crowd Counting.  In ECCV, pages 757–773, 2018.
  * [2] Antoni B. Chan and Nuno Vasconcelos.  Bayesian Poisson regression for crowd counting.  In ICCV, pages 545–551, 2009.
  * [3] Antoni B. Chan and Nuno Vasconcelos.  Counting People With Low-Level Features and Bayesian Regression.  IEEE TIP, 21(4):2160–2177, 2012.
  * [4] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale.  In ICLR, 2021.
  * [5] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep Residual Learning for Image Recognition.  In CVPR, pages 770–778, 2016.
  * [6] Haroon Idrees, Muhmmad Tayyab, Kishan Athrey, Dong Zhang, Somaya Al-Máadeed, Nasir M. Rajpoot, and Mubarak Shah.  Composition Loss for Counting, Density Map Estimation and Localization in Dense Crowds.  In ECCV, volume 11206, pages 544–559, 2018.
  * [7] Jiyeoup Jeong, Jongwon Choi, Dae Ung Jo, and Jin Young Choi.  Congestion-Aware Bayesian Loss for Crowd Counting.  IEEE Access, 10:8462–8473, 2022.
  * [8] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton.  Imagenet classification with deep convolutional neural networks.  Commun. ACM, 60(6):84–90, 2017.
  * [9] Victor S. Lempitsky and Andrew Zisserman.  Learning To Count Objects in Images.  In NeurIPS, pages 1324–1332, 2010.
  * [10] Yuhong Li, Xiaofan Zhang, and Deming Chen.  Csrnet: Dilated Convolutional Neural Networks for Understanding the Highly Congested Scenes.  In CVPR, pages 1091–1100, 2018.
  * [11] Dingkang Liang, Wei Xu, Yingying Zhu, and Yu Zhou.  Focal Inverse Distance Transform Maps for Crowd Localization.  arXiv preprint arXiv:2102.07925, 2021.
  * [12] Bo Liu and Nuno Vasconcelos.  Bayesian Model Adaptation for Crowd Counts.  In ICCV, pages 4175–4183, 2015.
  * [13] Weizhe Liu, Mathieu Salzmann, and Pascal Fua.  Context-Aware Crowd Counting.  In CVPR, pages 5099–5108, 2019.
  * [14] Xinyan Liu, Guorong Li, Zhenjun Han, Weigang Zhang, Yifan Yang, Qingming Huang, and Nicu Sebe.  Exploiting sample correlation for crowd counting with multi-expert network.  In ICCV, pages 3195–3204, 2021.
  * [15] Xiyang Liu, Jie Yang, Wenrui Ding, Tieqiang Wang, Zhijin Wang, and Junjun Xiong.  Adaptive Mixture Regression Network with Local Counting Map for Crowd Counting.  In ECCV, pages 241–257, 2020.
  * [16] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin Transformer: Hierarchical Vision Transformer using Shifted Windows.  In ICCV, pages 9992–10002, 2021.
  * [17] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie.  A ConvNet for the 2020s.  In CVPR, pages 11966–11976, 2022.
  * [18] Zhiheng Ma, Xiaopeng Hong, Xing Wei, Yunfeng Qiu, and Yihong Gong.  Towards A Universal Model for Cross-Dataset Crowd Counting.  In ICCV, pages 3185–3194, 2021.
  * [19] Zhiheng Ma, Xing Wei, Xiaopeng Hong, and Yihong Gong.  Bayesian Loss for Crowd Count Estimation With Point Supervision.  In ICCV, pages 6141–6150, 2019.
  * [20] Gabriel Peyré and Marco Cuturi.  Computational Optimal Transport.  Found. Trends Mach. Learn., 11(5-6):355–607, 2019.
  * [21] Deepak Babu Sam, Skand Vishwanath Peri, Mukuntha Narayanan Sundararaman, Amogh Kamath, and R. Venkatesh Babu.  Locate, Size, and Count: Accurately Resolving People in Dense Crowds via Detection.  IEEE TPAMI, 43(8):2739–2751, 2021.
  * [22] Deepak Babu Sam, Shiv Surya, and R. Venkatesh Babu.  Switching Convolutional Neural Network for Crowd Counting.  In CVPR, pages 4031–4039, 2017.
  * [23] Karen Simonyan and Andrew Zisserman.  Very Deep Convolutional Networks for Large-Scale Image Recognition.  In ICLR, 2015.
  * [24] Vishwanath Sindagi and Vishal M. Patel.  Multi-Level Bottom-Top and Top-Bottom Feature Fusion for Crowd Counting.  In ICCV, pages 1002–1012, 2019.
  * [25] Vishwanath A. Sindagi, Rajeev Yasarla, and Vishal M. Patel.  JHU-CROWD++: Large-Scale Crowd Counting Dataset and A Benchmark Method.  IEEE TPAMI, 44(5):2594–2609, 2022.
  * [26] Qingyu Song, Changan Wang, Zhengkai Jiang, Yabiao Wang, Ying Tai, Chengjie Wang, Jilin Li, Feiyue Huang, and Yang Wu.  Rethinking Counting and Localization in Crowds: A Purely Point-Based Framework.  In ICCV, pages 3345–3354, 2021.
  * [27] Jia Wan and Antoni B. Chan.  Adaptive Density Map Generation for Crowd Counting.  In ICCV, pages 1130–1139, 2019.
  * [28] Jia Wan and Antoni B. Chan.  Modeling Noisy Annotations for Crowd Counting.  In NeurIPS, 2020.
  * [29] Jia Wan, Ziquan Liu, and Antoni B. Chan.  A Generalized Loss Function for Crowd Counting and Localization.  In CVPR, pages 1974–1983, 2021.
  * [30] Jia Wan, Wenhan Luo, Baoyuan Wu, Antoni B. Chan, and Wei Liu.  Residual Regression With Semantic Prior for Crowd Counting.  In CVPR, pages 4036–4045, 2019.
  * [31] Jia Wan, Qingzhong Wang, and Antoni B. Chan.  Kernel-Based Density Map Generation for Dense Object Counting.  IEEE TPAMI, 44(3):1357–1370, 2022.
  * [32] Jia Wan, Qingzhong Wang, and Antoni B. Chan.  Kernel-Based Density Map Generation for Dense Object Counting.  IEEE TPAMI, 44(3):1357–1370, 2022.
  * [33] Boyu Wang, Huidong Liu, Dimitris Samaras, and Minh Hoai Nguyen.  Distribution Matching for Crowd Counting.  In NeurIPS, 2020.
  * [34] Jingdong Wang, Ke Sun, Tianheng Cheng, Borui Jiang, Chaorui Deng, Yang Zhao, Dong Liu, Yadong Mu, Mingkui Tan, Xinggang Wang, Wenyu Liu, and Bin Xiao.  Deep High-Resolution Representation Learning for Visual Recognition.  IEEE TPAMI, 43(10):3349–3364, 2021.
  * [35] Qi Wang, Junyu Gao, Wei Lin, and Yuan Yuan.  Learning From Synthetic Data for Crowd Counting in the Wild.  In CVPR, pages 8198–8207, 2019.
  * [36] Chenfeng Xu, Dingkang Liang, Yongchao Xu, Song Bai, Wei Zhan, Xiang Bai, and Masayoshi Tomizuka.  Autoscale: Learning to Scale for Crowd Counting.  IJCV, 130(2):405–434, 2022.
  * [37] Yifan Yang, Guorong Li, Zhe Wu, Li Su, Qingming Huang, and Nicu Sebe.  Reverse Perspective Network for Perspective-Aware Object Counting.  In CVPR, pages 4373–4382, 2020.
  * [38] Yingying Zhang, Desen Zhou, Siqin Chen, Shenghua Gao, and Yi Ma.  Single-Image Crowd Counting via Multi-Column Convolutional Neural network.  In CVPR, pages 589–597, 2016.
  * [39] Joey Tianyi Zhou, Le Zhang, Jiawei Du, Xi Peng, Zhiwen Fang, Zhe Xiao, and Hongyuan Zhu.  Locality-Aware Crowd Counting.  IEEE TPAMI, 44(7):3602–3613, 2022.