# Psychiatric Scale Guided Risky Post Screening for Early Detection of
Depression

Zhiling Zhang  Siyuan Chen  Mengyue Wu∗ &Kenny Q. Zhu Shanghai Jiao Tong
University {blmoistawinde, chensiyuan925<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding authors are supported by NSFC Grants
No.91646205 and No.61901265, SJTU-CMBCC Joint Research Scheme, and Shanghai
Municipal Science and Technology Major Project (2021SHZDZX0102).

###### Abstract

Depression is a prominent health challenge to the world, and early risk
detection (ERD) of depression from online posts can be a promising technique
for combating the threat. Early depression detection faces the challenge of
efficiently tackling streaming data, balancing the tradeoff between
timeliness, accuracy and explainability. To tackle these challenges, we
propose a psychiatric scale guided risky post screening method that can
capture risky posts related to the dimensions defined in clinical depression
scales, and providing interpretable diagnostic basis. A Hierarchical
Attentional Network equipped with BERT (HAN-BERT) is proposed to further
advance explainable predictions. For ERD, we propose an online algorithm based
on an evolving queue of risky posts that can significantly reduce the number
of model inferences to boost efficiency. Experiments show that our method
outperforms the competitive feature-based and neural models under conventional
depression detection settings, and achieves simultaneous improvement in both
efficacy and efficiency for ERD.

##  1 Introduction

Depression has been a major health challenge to the world, with over 280
million people affected, according to WHO111https://www.who.int/news-
room/fact-sheets/detail/depression. Moreover, the COVID-19 pandemic has
further deteriorated the situation. Since people are more willing to express
their feelings on online social media during this special
period222https://www.statista.com/statistics/1106498/home-media-consumption-
coronavirus-worldwide-by-country/, depression detection from online posts can
be a promising approach to combat the challenge. The conventional setting of
depression detection from online posts is to predict whether a user suffers
from depression from the whole posting history Gui et al. (2019); Zogan et al.
(2021a). However, for social networks which update quickly, another setting,
early risk detection (ERD) Losada et al. (2017), may have more potential to
detect and offer timely help to risky users. An ERD model should access user
post one by one sequentially, dynamically update the estimated risk, and make
immediate alert once it is confident enough about its prediction. This setting
is less explored due to its unique challenges:

First, the ability of classification on streaming data is a requirement of ERD
models. This means that the method is better to be an online, incremental
algorithm that can update the prediction every time a user sends a post,
rather than an offline batch algorithm that only runs once after a long
interval. Since traditional ML models do not come with such ability
inherently, a typical solution is to naively process the whole posting history
for each update Trotzek et al. (2018). This method can hardly be efficient
enough in practice. For instance, many systems in an ERD competition,
eRisk2019, spent several days for computation Losada et al. (2019).

Moreover, an ERD model should make tradeoff between its timeliness and
accuracy. To make an early prediction, the model usually predicts a depression
probability after each update, and makes an alert if the probability exceeds
certain threshold, and we can tune the threshold to control the latency of
prediction Trotzek et al. (2018). Leveraging more posts can certainly
facilitate higher accuracy, while it also means that the model makes late
predictions, and it fails to make alert before the patient’s condition
deteriorates. To realize the pareto improvement of both objectives, we should
also seek improved model structure. Although large pretrained Language models
(LMs) like BERT Devlin et al. (2018) has achieved great success in many
classification tasks, they are seldom applied to ERD, as the long posting
history make the memory cost and latency prohibitive.

Due to the sensitiveness of depression detection, model explainability is also
a vital property. Without proper explanations, it can be hard for users to
trust such novel tools and accept these alerts. Since deep learning models are
mostly black-boxes, one cannot ascertain whether their predictions are
achieved due to robust features, or some spurious clues Ribeiro et al. (2020).
Traditional ML models can provide global explanations of the prediction (i.e.,
feature importance) based on features like word counts. However, it is much
more preferable if we can make personalized, symptom-based explanations Mowery
et al. (2017) like psychiatrists to endow higher level of trustworthiness.

Figure 1: Overview of the system. Depression templates derived from
established depression scales are used to screen risky posts, and filter out
safer ones (boxes in grey). A hierarchical attentional network further attends
to truly important contents (darkness of red lines indicates attention
strength) and makes final prediction.

Inspired by the psychiatry practice of using clinical scales to screen
depression patients, we propose to use depression templates derived from
established depression scale Beck et al. (1996) to screen risky posts. These
templates include direct expressions of depressive moods and depression
treatments, as well as theory-grounding indirect symptoms like guilty
feelings, pessimism and loss of appetite, etc. Only posts highly relevant to
these templates will be selected out of the whole posting history, which can
greatly reduce the input size, so as to eliminate distractors and improve
processing efficiency. A hierarchical network incorporating attention
mechanism Yang et al. (2016) and BERT Devlin et al. (2018) further aggregates
the selected posts of a user, and assigns higher weights to truly important
contents for accurate and explainable predictions. The overview of our
approach is illustrated in Figure 1. To enable ERD, we also propose an online
algorithm based on a risky posts queue evolving with the streaming posts.
Experimental results show that the proposed method can achieve SOTA
performance in both conventional and ERD settings, and can be even a more
efficient ERD solution than simple Logistic Regression models. 333Code,
Appendix and the used scale data at:
https://github.com/blmoistawinde/scale_early_depress_detect

Our key contributions are as follows: 1) We propose psychiatry-guided risky
post screening to select salient contents for processing, which reduces the
input size so as to allow the utilization of large models, and can provide
symptom-based interpretations. 2) We leverage hierarchical attentional network
with BERT (HAN-BERT) to enhance the model accuracy and explainability. 3) We
propose an online algorithm based on an evolving queue of risky posts to
tackle ERD, achieving simultaneous improvement in timeliness and accuracy over
representative baselines.

##  2 Methods

For a user $U_{i}$ with posts $[P_{i,1},P_{i,2},...,P_{i,n}]$ in the activity
history, where $n$ is the number of total posts and $P_{i,j}$ is the $j$-th
user-generated post of $U_{i}$, the goal of conventional depression detection
is to predict a binary label $y_{i}\in\\{0,1\\}$ indicating whether the user
$U_{i}$ suffers from depression, given the whole activity history. In
contrast, in an early risk detection (ERD) setting, the posts come one by one,
so that only $[P_{i,1},P_{i,2},...,P_{i,t}]$ is available to the model at the
$t$-th time. The model can make an early prediction of $y_{i}$ at $t(t\leq n)$
once it is confident enough, such that the prediction can make a good tradeoff
between accuracy and earliness (with $t$ as small as possible). Our solutions
for both settings are as follows.

###  2.1 Risky Post Screening

A reddit user typically has hundreds or thousands of posts in the whole
activity history. However, since not all user posts are relevant to the
detection of depression, retaining all posts may run the risk of introducing
distractors that can hinder model performance and efficiency. Therefore,
effective post selection strategy can be crucial to the success of ERD.

Intuitively, posts that directly disclose the state of depression or express
depression-related symptoms would indicate high depression risks. These
intuitions can be reliably captured by psychometrically validated clinical
scales. Therefore, we draw inspiration from these scales, and devise
depression templates to screen risky posts out of the lengthy activity
history. Only the posts with highest similarities to these templates will be
selected as risky posts for further prediction.

Our depression templates are made up of 2 groups of descriptions. The first
group consists of 3 explicit depression-related expressions: “I feel
depressed”, “I am diagnosed with depression”, “I am treating my depression”,
matching the person’s claim of general depressive mood, the diagnosis and the
post-diagnosis treatment, respectively. The second group is comprised of
descriptions corresponding to dimensions defined in a clinical depression
scale. Here we mainly adopt BDI-II, which is one of the most widely used
depression measures444We also experimented with other scales and combinations
of multiple scales, see Appendix for more details. Beck et al. (1996). The
scale includes the descriptions of four different intensities for each of the
21 symptoms. For example, “1: I do not feel sad”, “2: I feel sad much of the
time”, “3: I am sad all the time” and “4: I am so sad or unhappy that I can’t
stand it” for the symptom of sadness. However, we find that current sentence
representations have difficulty in capturing such nuanced differences.
Therefore, we make slight manual modifications on them to construct a single
representative template for each dimension, like “I feel sad” for Sadness. We
provide examples in Table 1.

Dimension | Template
---|---
Crying | I always cry.
Tiredness | I am too tired to do things.
Self-Dislike | I am disappointed in myself.
Table 1: Example BDI-II dimensions and their corresponding templates.

To measure the similarity between posts and depression templates, we resort to
pretrained sentence-transformers Reimers and Gurevych (2019) to get the
sentence representations, and calculate the cosine similarity between each
post-template pair. For a post, its most similar template is referred to as
its diagnostic basis, and their similarity is regarded as the risk of the
post. The process of risky post selection is to select at most $K$ posts with
the highest risks out of all posts of a user. Since the procedure consists of
only sentence encoding from a pretrained model, and cosine similarity
calculations, our method can be more efficient than previous works on post
selection that requires costly RL training Gui et al. (2019). Moreover, the
theoretical underpinning basis for post selection is also more effective than
heuristic-based selection such as clustering Zogan et al. (2021a), as we will
validate in the experiments (§3.3).

###  2.2 Hierarchical Attentional Network

Although depression detection can be formulated as text classification
problem, it is different from conventional settings in that the input consists
of multiple posts attached with temporal information. We may reformat the
input by simply concatenating all posts. However, such representations will
lost the time and structural clues at the post level, and also lead to a
lengthy sequence. Further, conventional text classification models are lacking
in explainability.

To leverage the posting list structure as well as providing post-level
explainability, we adopt the framework of Hierarchical Attentional Network
(HAN) Yang et al. (2016) in our model design. The HAN consists of a post
encoder and a user encoder.

The post encoder takes the words $\\{x_{1},x_{2},...,x_{L}\\}$ in a single
post, and encode them into a post representation $p$. Thanks to the pre-step
of risky post screening, we are able to take advantage of a large post encoder
as opposed to shallow CNN or GRU based structures used in previous works Yates
et al. (2017); Zogan et al. (2021b). Hence we use a pretrained BERT model as
the post encoder and the representation of the [CLS] token as the
representation for the whole post. Therefore, the post encoder can be
represented as:

$p=BERT_{[CLS]}(x_{1},x_{2},...,x_{L})$ (1)

Given the representations of the $K$ risky posts
$\\{p_{1},p_{2},...,p_{K}\\}$, the user encoder models the relations between
these posts as well as their chronological order to produce updated
contextualized representations of each post
$\\{p^{\prime}_{1},p^{\prime}_{2},...,p^{\prime}_{K}\\}$, and further
aggregate these embeddings into one user representation $u$. Here we utilize a
transformer structure to model the posts’ relations with self-attention and
encode the order with positional embeddings. The updated post representations
are further passed to an attentional pooling layer, which learns the weight
for each post embedding and perform a weighted sum of them accordingly, to get
the final user representation. The attention mechanism can distinguish the
contributions of each posts with learned weight so that important posts will
have a higher influence on the final prediction. After all, the user encoder
can be represented as:

$p^{\prime}_{1},p^{\prime}_{2},...,p^{\prime}_{K}=Transformer(p_{1},p_{2},...,p_{K})$
(2)
$\alpha_{k}=\frac{exp(Wp^{\prime}_{k}+b)}{\sum_{k^{\prime}=1}^{K}exp(Wp^{\prime}_{k^{\prime}}+b)}$
(3) $u=\sum_{k=1}^{K}\alpha_{k}p^{\prime}_{k}$ (4)

where $W$ and $b$ is learnable weight matrix and bias term of the linear
transformation in the attentional pooling layer. Finally, a linear layer on
top of the user representation makes the final binary classification of
depression. The whole model is trained with the standard binary cross entropy
loss.

With the HAN model above, most of the single post will not exceed BERT length
limit. The attention weights can also provide explanations for which post is
considered vital in the model’s decision.

Figure 2: Illustration of the evolving queue for early risk detection.

###  2.3 Evolving Queue for Early Detection

In an ERD scenario, we need to incrementally make predictions each time a user
posts, instead of processing the whole posting history once. This brings the
computational challenges of frequent feature updates and model inferences. For
example, a traditional feature-based model would have to recalculate the
features like LDA topic distribution Blei et al. (2003) from the whole
activity history after each single update, and then make prediction
accordingly. Such frequent recalculations can be even intractable for typical
DNN solutions. Although post selection strategies can reduce the computational
costs at the model inference stage to some extent, the selection stage itself
can become a performance bottleneck if it is not efficient enough.

Moreover, the frequent updates may also be sensitive to one single depression-
like post and easily produce false positive predictions, while the depressed
patients tend to suffer from durative symptoms Kroenke et al. (2001) as
opposed to control users who can also be depressive at some moments. Since the
ERD setting does not allow modifying the prediction, once the model makes a
confident diagnosis (since we may have already taken action to intervene in
the dangerous situation), these false positives cannot be corrected later.

To tackle the above challenges, we further propose an online algorithm based
on evolving queue of risky posts to adapt the above methods (§2.1, §2.2) for
effective and efficient early detection. First, the Risky Post Screening has
already provided an efficient basis for the feature updates step555We may view
the selected posts as “features” in our model, since they are the actual
inputs for the prediction model., as discussed above. However, the model
inferences remain computationally demanding. We observe that we don’t have to
make a prediction for each post, as some posts are not very helpful or even
misleading for the detection of depression, and these posts are exactly what
we would filter out with our screening approach as low risk posts. Therefore,
we can make prediction updates only if the new post is considered risky
enough, so that the number of model inferences can be substantially reduced.
The computational costs can be further contained by limiting the number of
posts used in inference, so that only the most risky and recent posts will be
included.

We implement the above intuition with an evolving queue updated according to
post risk. The whole procedure is illustrated in Figure 2. We set the capacity
of the queue to $K$ to control the computational costs as well as the number
of posts used in training. For each incoming post $p$, the queue is updated
according to the following rules:

  1. 1.

If the queue is not full, we will add $p$ into the queue no matter how risky
it is.

  2. 2.

If the queue has already been full, we will compare the risk of $p$ with the
minimum risk of all posts in the queue. If $p$ is less risky, it will not be
included in the queue. Otherwise, the least risky post in the queue will be
removed for the insertion of $p$. The posts in queue will then be sorted in
chronological order to align with the model’s positional encoding.

The HAN model will make inference only if the queue updates to avoid
unnecessary computations. If the model’s predicted probability exceeds a
predefined threshold, it will report a early alert of depression and stop
further calculations.

##  3 Experiments

In this section, we will first introduce the dataset and the compared methods.
We will then further provide our models’ results in the conventional
depression detection setting and their efficacy and efficiency in ERD
settings. We finally illustrate the explainability of the proposed method with
examples.

###  3.1 Dataset

We mainly use the eRisk2017 dataset Losada and Crestani (2016) in our
experiment, which is adopted as the benchmark in the ERD task of CLEF 2017
Losada et al. (2017). It consists of 137 depressed users and 755 control users
and is divided into training/test set with 486/406 users each. The depressed
users are identified with patterns like “I was diagnosed with depression”,
while the control users are those active on depression subreddit but had no
depression. The posting year spans from 2007 to 2015. The anchor post for
identification is filtered from the dataset. This filtering strategy can
prevent the direct information leakage from the self-report, which may prevent
the model from learning other indirect depression signals. We also conducted
experiments and validated the generalizability of the proposed method on other
two datasets with in-domain and cross-domain experiments (see Appendix).

###  3.2 Competing Methods

We compare our method with several competitive baselines. For traditional
machine learning models. LR uses TF-IDF features and a logistic regression
classifier. Feature-Rich utilizes some additional user-based features,
including LDA topic distribution Blei et al. (2003), LIWC features Pennebaker
et al. (2001) and emoticon counts. This is a competitive baseline that has
been widely accepted in depression detection works on Facebook, Twitter and
Reddit datasets Eichstaedt et al. (2018); Trotzek et al. (2018); Harrigian et
al. (2020).

For neural baselines, we consider both models with large pretrained LM and
relatively small models. For small models, we choose the representative HAN-
GRU model Zogan et al. (2021b), which adopts a similar HAN structure with GRU
as both the user encoder and post encoder. To have a fair competition with
large models, it uses the last 1000 posts for classification, which is already
a major portion of or the full posting list for many users. For large models,
due to their computational cost and length limit, post selection is necessary.
Therefore, each method is denoted as a pair of model and selection strategy.
For backbone model, we consider the strong pre-trained model BERT and the
proposed HAN-BERT. For post selection strategy, Heuristic chooses last posts
in user history. Clus and Clus+Abs are inspired by Zogan et al. (2021a). We
use sentence-bert Reimers and Gurevych (2019) to get post embeddings and run
K-means clustering to get the $K$ posts nearest to the cluster center as
representative posts (Clus). These posts are further passed to a BART model
Lewis et al. (2020) pretrained on CNN/DM summarization dataset to get an
abstractive summary (Clus+Abs). Finally, the proposed screening strategy is
denoted as Psych.

The basis of BERT and HAN-BERT models are bert-base-uncased. The sentence-bert
model is paraphrase-MiniLM-L6-v2. The number of selected posts is $K=16$. We
train with a batch size of 4, and learning rate of 2e-5. We concatenate the
selected posts as input into the BERT baselines. For HAN-BERT models, the user
encoder is a 4-layer 8-head transformer encoder. To avoid the influence of
randomness, we run each method with 3 different seeds and report the best
performance.

###  3.3 Conventional Setting Results

We first conduct experiments in conventional depression detection setting
(Table 2). We can see that BERT (Clus+Abs) performs worse than BERT (Clus),
indicating that the abstractive summarization strategy does not necessarily
work possibly due to the gap between its pretrained domain (News) and Reddit.
HAN-BERT (Clus) outperforms BERT (Clus), showing the effectiveness of the
proposed HAN structure. The poor performance of HAN-BERT (Heuristic)
highlights the importance of post selection, and none of the traditional post
selection methods can outperform the competitive Feature-Rich model with
access to all posts. However, with our proposed screening strategy, the HAN-
BERT (Psych) model significantly outperforms baselines. HAN-GRU performs worse
than HAN-BERT (Psych), suggesting the importance of a strong backbone model.

| F1
---|---
LR | 60.2
Feature-Rich | 63
HAN-GRU | 61.7
BERT (Clus) | 59.6
BERT (Clus+Abs) | 52.3
HAN-BERT (Heuristic) | 43.2
HAN-BERT (Clus) | 62.5
HAN-BERT (Psych) | 70.3
Table 2:  Results on eRisk2017 test set.

###  3.4 Early Detection

We then test model performance in the ERD setting, using the official metrics
ERDE5 and ERDE50 Losada et al. (2017). We also report F1 calculated using the
early predictions (report positive if predicted probability over the
predefined threshold 0.5, with which all these models are trained). We exclude
baselines with unsatisfying performance and preserves LR, Feature-Rich and
HAN-GRU. To tackle the item-by-item updates, the baseline models have to
recalculate the features and run inference for each new post, while our HAN-
BERT with risky post screening can deal this efficiently with the proposed
evolving queue algorithm (§2.3). When counting the running time, we accumulate
the time costs for all posts no matter if the model makes early predictions to
rule out the influence of early false positives. LR and Feature-Rich run on a
Linux machine with CPU: E5-2678 (48 cores), while HAN-GRU and HAN-BERT run
with a NVIDIA 2080 Ti GPU. Although the comparison is not totally fair, we
think it is still a practical setting for real world applications.

Model |  ERDE5 |  ERDE50 | F1 | Time(s)
---|---|---|---|---
LR | 13.70 | 8.49 | 40.5 | 4710.7
Feature-Rich | 12.98 | 8.39 | 35.8 | 7558.4
HAN-GRU | 13.30 | 8.58 | 40.7 | 19671.4
HAN-BERT (Psych) | 10.72 | 8.12 | 60.3 | 1330.3
Table 3:  Test results on eRisk2017 in early detection setting. The lower
ERDE5 and ERDE50, the better model performs early detection.

The results are shown in Table 3. It can be seen that HAN-BERT (Psych)
significantly outperforms baselines in ERDE and F1, while also being faster.
The reason for the superiority on effectiveness is because baselines produce
much more false positives than HAN-BERT due to their sensitivity to single
posts. The advantage of efficiency can be mainly attributed to the evolving
queue algorithm, which greatly reduced the number of model inference to only
10.41% of all posts. The efficient feature update also helps. Although the
sentence encoding must be conducted for all posts, it only costs a small
fraction of total time (114.7s out of 1330.3s). The extremely long running
time of HAN-GRU further highlights the importance of the proposed algorithm,
as we can expect an unaffordable time cost for the even larger BERT-based
models without it.

Figure 3: Effect of threshold on early detection F1. Attention | Post | Diagnostic Basis
---|---|---
0.202 |  It sucks that the Citalopram didn’t work for you but glad to hear your other meds are helping. It’s my first time on antidepressants so I didn’t know what are their side effects. |  Treatment Diagnosis Changes in Appetite
0.118 |  Thanks! :) Sometimes it’s really good to actually get the words out of me rather than internalising my feelings. |  Concentration Difficulty Loss of Pleasure Self-Dislike
0.048 |  Glad to know :) just glad I’m not working for the next couple of weeks. Feel like I’m on a different planet haha. |  Tiredness Stay still Concentrate
0.021 |  Some films or TV shows. I remember watching … The worst part was I’d already been laughed at by my mum for crying at the end of Breakfast at Tiffanys (who leaves a cat out in the rain like that?). |  Sadness Crying Depressed Mood
Table 4:  Example posting list (4 selected out of all 16 posts) of a user with
depression with their attention weight in HAN and diagnostic basis according
to top 3 cosine similarity (reasonable ones highlighted in bold).

We can adjust the detection latency $t$ by tuning the threshold and balance
the tradeoff between precision and recall. Therefore, we hypothesize that
model performance can be improved with varied threshold. We tune the threshold
from 0.3 to 0.8, and check the changes in their early detection F1. This will
run the risk of overfitting on the test set, but allow us to explore the best
possible performance. As is shown in Figure 3, the performance of baseline
systems can improve by changing the threshold, but still fall behind HAN-BERT
(Psych). Moreover, the performance of HAN-BERT (Psych) is not sensitive to
threshold, so we may deploy it more comfortably without concerns on threshold
tuning.

###  3.5 Qualitative Example

We provide a concrete example in Table 4 to analyze the behaviors of HAN-BERT
(Psych) in detail. From the column of attention weight, we can see that posts
with strong depression indicators (e.g. antidepressants, internalizing
feelings, see Row 1, 2) received much higher attention than a uniform baseline
(1/16 = 0.0625), while posts with no evident signals of depression or even
with a positive emotion (Row 3, 4) received low attention. This suggests the
usefulness of the attention weight as an explanation for model prediction. The
diagnostic bases decided by the cosine similarity between post and depression
templates constitute another type of intuitive explanation. The top 3
diagnostic bases can usually capture the conventional depression behaviors
that the post may indicate, which may act as a convincing interpretation in
its clinical applications. However, we noticed that sometimes the similarity
model may rank an unreasonable aspect high in the list of bases, such as the
“Sadness” for the last positive post. We owe such mistakes to the limitation
of sentence representation models, such as not sensitive to negation Ribeiro
et al. (2020). We expect stronger sentence representation models to alleviate
the problem.

##  4 Related Work

Recently, depression detection has received much attention. Studies include
predicting depression diagnosis from clinical interviews Gratch et al. (2014),
medical records Eichstaedt et al. (2018) and self-reported surveys Guntuku et
al. (2019). Depression detection on social media is especially promising, as
proxy diagnostic signals can be relatively easy to get from self-reports or
activities in depression communities Ernala et al. (2019). Early attempts by
Losada and CrestaniLosada and Crestani (2016) used TF-IDF and Logistic
Regression on all user posts for depression detection. Later researchers
further incorporate new features like LDA, LIWC dictionary and posting
patterns Trotzek et al. (2018). For deep learning methods, Yates et al.Yates
et al. (2017) uses hierarchical CNN to process all the posts of a user at the
first level and merge the output at the second level for user-level
classification. However, most of them directly use all the user’s posts
without screening out salient posts, which may negatively affect their
accuracy and efficiency.

In terms of model interpretability, traditional feature-based methods are
partially explainable on the level of global features. For example, Shen et
al.Shen et al. (2017) found different behaviors for depressed users in posting
time, emotion catharsis, self-awareness and life sharing. However, these
methods cannot make user-level explanations as personalized diagnostic basis.
Detecting depression from its corresponding symptoms can be a promising
approach to improve explainability. The pioneering work of Mowery et al.Mowery
et al. (2017) established an annotation scheme for depressive symptoms and an
annotated corpus. However, the annotations are difficult so that the amount of
data is not sufficient to train a reliable symptom classifier. Our approach
also adopts the idea of explaining depression detection from symptoms. But it
identifies symptoms implicitly with similarity matching, and thus can
alleviate the requirement for large annotated corpus.

In practice, we also want to identify depression risk as early as possible, as
is exemplified by the eRisk competitions Losada et al. (2019). The majority of
proposed methods can only achieve satisfying performance given almost the
whole dataset, and few of them are able to make immediate response to each
item update. To reduced the number of required posts, Zogan et al.Zogan et al.
(2021a) uses extractive summarization to extract key posts of a user. However,
it relies on K-means clustering to get the summaries, so the model cannot run
online as well.

##  5 Conclusions

In this work, we tackle the problem of ERD of depression detection with a
novel, psychiatry-guided method of risky post screening and hierarchical
attentional network. The accurate selection of risky posts out of the long
user history constitutes a solid foundation for prediction as well as enables
the usage of large pretrained language model. Furthermore, our framework can
work on ERD scenarios with high efficiency, supported by the proposed evolving
queue algorithm, which can greatly reduce the required number of model
inferences. Utilizing attention mechanism and depression scales provides our
method with strong interpretability in the form of attention weights and
diagnostic basis, which we hope can facilitate its further application in
online detection as a reliable assistant.

##  6 Ethical Statement

The datasets used in this work are either publicly available or used under
their corresponding data usage agreement. All posts in examples were de-
identified and paraphrased for anonymity. We provide further discussion in
Appendix.

## References

  * Beck et al. [1996] Aaron T Beck, Robert A Steer, and Gregory K Brown.  Beck depression inventory (BDI-II).  Pearson, 1996.
  * Blei et al. [2003] David M Blei, Andrew Y Ng, and Michael I Jordan.  Latent dirichlet allocation.  the Journal of machine Learning research, 2003.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * Eichstaedt et al. [2018] Johannes C Eichstaedt, Robert J Smith, Raina M Merchant, Lyle H Ungar, Patrick Crutchley, Daniel Preoţiuc-Pietro, David A Asch, and H Andrew Schwartz.  Facebook language predicts depression in medical records.  Proceedings of the National Academy of Sciences, 2018.
  * Ernala et al. [2019] Sindhu Kiranmai Ernala, Michael L Birnbaum, Kristin A Candan, Asra F Rizvi, William A Sterling, John M Kane, and Munmun De Choudhury.  Methodological gaps in predicting mental health states from social media: triangulating diagnostic signals.  In Proceedings of the 2019 chi conference on human factors in computing systems, 2019.
  * Gratch et al. [2014] Jonathan Gratch, Ron Artstein, Gale Lucas, Giota Stratou, Stefan Scherer, Angela Nazarian, Rachel Wood, Jill Boberg, David DeVault, Stacy Marsella, et al.  The distress analysis interview corpus of human and computer interviews.  In Proc. of LREC, 2014.
  * Gui et al. [2019] Tao Gui, Liang Zhu, Qi Zhang, Minlong Peng, Xu Zhou, Keyu Ding, and Zhigang Chen.  Cooperative multimodal approach to depression detection in twitter.  In Proc. of AAAI, 2019.
  * Guntuku et al. [2019] Sharath Chandra Guntuku, Daniel Preotiuc-Pietro, Johannes C Eichstaedt, and Lyle H Ungar.  What twitter profile and posted images reveal about depression and anxiety.  In Proc. of AAAI, 2019.
  * Harrigian et al. [2020] Keith Harrigian, Carlos Aguirre, and Mark Dredze.  Do models of mental health based on social media data generalize?  In Proc. of EMNLP, 2020.
  * Kroenke et al. [2001] Kurt Kroenke, Robert L Spitzer, and Janet BW Williams.  The phq-9: validity of a brief depression severity measure.  Journal of general internal medicine, 2001.
  * Lewis et al. [2020] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In Proc. of ACL, 2020.
  * Losada and Crestani [2016] David E Losada and Fabio Crestani.  A test collection for research on depression and language use.  In International Conference of the Cross-Language Evaluation Forum for European Languages, 2016.
  * Losada et al. [2017] David E Losada, Fabio Crestani, and Javier Parapar.  erisk 2017: Clef lab on early risk prediction on the internet: experimental foundations.  In International Conference of the Cross-Language Evaluation Forum for European Languages, 2017.
  * Losada et al. [2019] David E Losada, Fabio Crestani, and Javier Parapar.  Overview of erisk 2019 early risk prediction on the internet.  In International Conference of the Cross-Language Evaluation Forum for European Languages, 2019.
  * Mowery et al. [2017] Danielle Mowery, Hilary Smith, Tyler Cheney, Greg Stoddard, Glen Coppersmith, Craig Bryan, and Mike Conway.  Understanding depressive symptoms and psychosocial stressors on twitter: a corpus-based study.  Journal of medical Internet research, 2017.
  * Pennebaker et al. [2001] James W Pennebaker, Martha E Francis, and Roger J Booth.  Linguistic inquiry and word count: Liwc 2001.  Mahway: Lawrence Erlbaum Associates, 2001.
  * Reimers and Gurevych [2019] Nils Reimers and Iryna Gurevych.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In Proc. of EMNLP, 2019.
  * Ribeiro et al. [2020] Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh.  Beyond accuracy: Behavioral testing of nlp models with checklist.  In Proc. of ACL, 2020.
  * Shen et al. [2017] Guangyao Shen, Jia Jia, Liqiang Nie, Fuli Feng, Cunjun Zhang, Tianrui Hu, Tat-Seng Chua, and Wenwu Zhu.  Depression detection via harvesting social media: A multimodal dictionary learning solution.  In Proc. of IJCAI, 2017.
  * Trotzek et al. [2018] Marcel Trotzek, Sven Koitka, and Christoph M Friedrich.  Utilizing neural networks and linguistic metadata for early detection of depression indications in text sequences.  IEEE Transactions on Knowledge and Data Engineering, 2018.
  * Yang et al. [2016] Zichao Yang, Diyi Yang, Chris Dyer, Xiaodong He, Alex Smola, and Eduard Hovy.  Hierarchical attention networks for document classification.  In Proc. of ACL, 2016.
  * Yates et al. [2017] Andrew Yates, Arman Cohan, and Nazli Goharian.  Depression and self-harm risk assessment in online forums.  In Proc. of EMNLP, 2017.
  * Zogan et al. [2021a] Hamad Zogan, Imran Razzak, Shoaib Jameel, and Guandong Xu.  Depressionnet: A novel summarization boosted deep framework for depression detection on social media.  arXiv preprint arXiv:2105.10878, 2021.
  * Zogan et al. [2021b] Hamad Zogan, Imran Razzak, Xianzhi Wang, Shoaib Jameel, and Guandong Xu.  Explainable depression detection with multi-modalities using a hybrid deep learning model on social media.  arXiv preprint arXiv:2007.02847, 2021.


We then extend $\llbracket-\rrbracket$ to formulae of predicate ILGL. For each
$\varphi$ with free variables in context $\Gamma$ we define an element
$\llbracket\varphi\rrbracket\in\mathbb{P}(\llbracket\Gamma\rrbracket)$
inductively. For atomic formulae $Pt_{1}\ldots t_{m}$ and $t=_{X}t^{\prime}$,
$\llbracket Pt_{1}\ldots t_{m}\rrbracket$ and $\llbracket
t=_{X}t^{\prime}\rrbracket$ are given by $\mathbb{P}(\langle\llbracket
t_{1}\rrbracket,\ldots,\llbracket t_{m}\rrbracket\rangle)(\llbracket
P\rrbracket)$ and $\mathbb{P}(\langle\llbracket t\rrbracket,\llbracket
t^{\prime}\rrbracket\rangle)(=_{X})$ respectively. We then proceed by
structural induction, using the algebraic structure of
$\mathbb{P}(\llbracket\Gamma\rrbracket)$: $\llbracket\top\rrbracket=\top$,
$\llbracket\bot\rrbracket=\bot$,
$\llbracket\varphi\circ\psi\rrbracket=\llbracket\varphi\rrbracket\circ\llbracket\psi\rrbracket$
for all
$\circ\in\\{\land,\lor,\rightarrow,\blacktriangleright,\mathop{-\\!\\!\\!\\!\\!-\\!\\!\\!\blacktriangleright},\mathop{\blacktriangleright\\!\\!\\!\\!-\\!\\!\\!\\!\\!-}\\}$.
Assuming $\varphi$ has free variables in $\Gamma\cup\\{x:X\\}$, $\llbracket
Qx:X\varphi\rrbracket=Q\llbracket
X\rrbracket_{\llbracket\Gamma\rrbracket}(\llbracket\varphi\rrbracket)$ for
$Q\in\\{\exists,\forall\\}$. Finally, term substitution is given by
$\llbracket\varphi(t/x)\rrbracket=\mathbb{P}(\llbracket
t\rrbracket)(\llbracket\varphi\rrbracket)$.

A formula $\varphi$ with free variables in $\Gamma$ is satisfied under
interpretation $\llbracket-\rrbracket$ if $\llbracket\varphi\rrbracket$ is
$\top$ in $\mathbb{P}(\llbracket\Gamma\rrbracket)$. It is valid if it is
satisfied under all interpretations. The soundness and completeness of
predicate ILGL for this notion of validity is an immediate consequence of the
analogous result for BI and BI hyperdoctrines.

######  Theorem 34 (cf. [3]).

For all formulae $\varphi$ of predicate ILGL, $\varphi$ is provable iff
$\varphi$ is valid on ILGL hyperdoctrines. ∎

We now define the relational structures on which we give a truth-functional
semantics, _indexed layered frames_.

[Indexed Layered Frame] An _indexed layered frame_ is a functor
$\mathcal{R}:\mathrm{C}\rightarrow\mathrm{IntLayFr}$ such that

  1. (1)

$\mathrm{C}$ is a category with finite products;

  2. (2)

(Psuedo Epi) For all objects $\Gamma,\Gamma^{\prime}$ and $X$ in $\mathrm{C}$,
all morphisms $s:\Gamma\rightarrow\Gamma^{\prime}$ and all projections
$\pi_{\Gamma,X}:\Gamma\times X\rightarrow\Gamma$, if
$\mathcal{R}(\pi_{\Gamma^{\prime},X})(y)\preccurlyeq\mathcal{R}(s)(x)$ then
there exists $z$ such that $\mathcal{R}(\pi_{\Gamma,X})(z)\preccurlyeq x$ and
$y\preccurlyeq\mathcal{R}(s\times id_{X})(z)$.

∎Given an indexed layered frame
$\mathcal{R}:\mathrm{C}\rightarrow\mathrm{IntLayFr}$ and an object $X$ in
$\mathrm{C}$ we denote the intuitionistic layered frame at $X$ by
$\mathcal{R}(X)=(\mathcal{R}(X),\preccurlyeq_{\mathcal{R}(X)},R_{\mathcal{R}(X)})$.

An interpretation for an indexed layered frame is given in precisely the same
way as for an ILGL hyperdoctrine, but for one key difference: each m-ary
predicate symbol $P$ of type $X_{1},\ldots,X_{m}$ is interpreted as an upward-
closed set $\llbracket
P\rrbracket\in\mathcal{P}_{\preccurlyeq}(\mathcal{R}(\llbracket
X_{1}\rrbracket,\ldots\llbracket X_{m}\rrbracket))$. For $\varphi$ with free
variables in $\Gamma$, an interpretation $\llbracket-\rrbracket$, and
$x\in\mathcal{R}(\llbracket\Gamma\rrbracket)$, the satisfaction relation
$\vDash^{\Gamma}$ is defined in Figure 15.

$x,\llbracket-\rrbracket$ $\vDash^{\Gamma}$ $\top$ always
$x,\llbracket-\rrbracket$ $\vDash^{\Gamma}$ $\bot$ never
$x,\llbracket-\rrbracket$ $\vDash^{\Gamma}$ $Pt_{1}\ldots t_{m}$ iff
$\mathcal{R}(\langle\llbracket t_{1}\rrbracket,\ldots,\llbracket
t_{m}\rrbracket\rangle)(x)\in\llbracket P\rrbracket$ $x,\llbracket-\rrbracket$
$\vDash^{\Gamma}$ $t=_{X}t^{\prime}$ iff $\mathcal{R}(\langle\llbracket
t\rrbracket,\llbracket t^{\prime}\rrbracket\rangle)(x)\in
Ran(\mathcal{R}(\Delta_{\llbracket X\rrbracket}))$ $x,\llbracket-\rrbracket$
$\vDash^{\Gamma}$ $\varphi\land\psi$ iff
$x,\llbracket-\rrbracket\vDash^{\Gamma}\varphi$ and
$x,\llbracket-\rrbracket\vDash^{\Gamma}\psi$ $x,\llbracket-\rrbracket$
$\vDash^{\Gamma}$ $\varphi\lor\psi$ iff
$x,\llbracket-\rrbracket\vDash^{\Gamma}\varphi$ or
$x,\llbracket-\rrbracket\vDash^{\Gamma}\psi$ $x,\llbracket-\rrbracket$
$\vDash^{\Gamma}$ $\varphi\rightarrow\psi$ iff for all $y\succcurlyeq x$,
$s,y\vDash^{\Gamma}\varphi$ implies $s,y$ $\vDash^{\Gamma}$ $\psi$
$x,\llbracket-\rrbracket$ $\vDash^{\Gamma}$ $\varphi\blacktriangleright\psi$
iff there exists $x^{\prime}\\!,\\!y,\\!z$ s.t. $x^{\prime}\preccurlyeq x$,
$R_{\mathcal{R}(\llbracket\Gamma\rrbracket)}yzx^{\prime}$,
$y,\\!\llbracket-\rrbracket\\!\vDash^{\Gamma}\\!\varphi$ and
$z,\\!\llbracket-\rrbracket\\!\vDash^{\Gamma}\\!\psi$
$x,\llbracket-\rrbracket$ $\vDash^{\Gamma}$
$\varphi\mathop{-\\!\\!\\!\\!\\!-\\!\\!\\!\blacktriangleright}\psi$ iff for
all $x^{\prime}\\!,\\!y,\\!z$: $x\preccurlyeq x^{\prime}$,
$R_{\mathcal{R}(\llbracket\Gamma\rrbracket)}x^{\prime}yz$ and
$y,\\!\llbracket-\rrbracket\\!\vDash^{\Gamma}\\!\varphi$ implies
$z,\\!\llbracket-\rrbracket\\!\vDash^{\Gamma}\\!\psi$
$x,\llbracket-\rrbracket$ $\vDash^{\Gamma}$
$\varphi\mathop{\blacktriangleright\\!\\!\\!\\!-\\!\\!\\!\\!\\!-}\psi$ iff for
all $x^{\prime}\\!,\\!y,\\!z$: $x\preccurlyeq x^{\prime}$,
$R_{\mathcal{R}(\llbracket\Gamma\rrbracket)}yx^{\prime}z$ and
$y,\\!\llbracket-\rrbracket\\!\vDash^{\Gamma}\\!\varphi$ implies
$z,\\!\llbracket-\rrbracket\\!\vDash^{\Gamma}\\!\psi$
$x,\llbracket-\rrbracket$ $\vDash^{\Gamma}$ $\exists r\varphi$ iff there
exists $x^{\prime}$ s.t.
$\mathcal{R}(\pi_{\llbracket\Gamma\rrbracket,\llbracket
X\rrbracket})(x^{\prime})=x$ and
$x^{\prime},\llbracket-\rrbracket\vDash^{\Gamma\cup\\{v:X\\}}\varphi$
$x,\llbracket-\rrbracket$ $\vDash^{\Gamma}$ $\forall r\varphi$ iff for all
$x^{\prime}$: if
$x\preccurlyeq\mathcal{R}(\pi_{\llbracket\Gamma\rrbracket,\llbracket
X\rrbracket})(x^{\prime})$ then
$x^{\prime},\llbracket-\rrbracket\vDash^{\Gamma\cup\\{v:X\\}}\varphi$

Figure 15. Satisfaction for indexed layered frame models of predicate ILGL.

The bigraph model of predicate ILGL defined in the previous subsection is an
example of an indexed layered frame over the category $\mathrm{Set}$.

[The bigraph model as an indexed layered frame] First, let
$(X,R,\preccurlyeq)$ be the layered frame corresponding to the bigraph
scaffold $\mathcal{X}$: $RHKL$ iff $H\mathop{@_{\mathcal{E}}}\nolimits
K\downarrow$ and $H\mathop{@_{\mathcal{E}}}\nolimits K=L$. Set
$\mathcal{R}:\mathrm{Set}\rightarrow\mathrm{IntLayFr}$ by
$\mathcal{R}(A)=(A\times X,R_{A},\preccurlyeq_{A})$ where
$R_{A}(x,H)(y,K)(z,L)$ iff $x=y=z$ and $RHKL$, and
$(x,H)\preccurlyeq_{A}(y,K)$ iff $x=y$ and $H\preccurlyeq K$. For functions
$f:A\rightarrow B$ set $\mathcal{R}(f)(a,H)=(f(a),H)$. This defines a functor
$\mathcal{R}$ which trivially satisfies (Psuedo Epi). Hence $\mathcal{R}$ is
an indexed layered frame.

We define the following interpretation. The single sort is interpreted as
$\mathcal{P}_{\preccurlyeq}(V(G))$ where $G$ is the graph union of the place
graph vertices of the system of bigraphs. The predicate symbols are
interpreted as $\llbracket Contains(-)\rrbracket=\\{(A,H)\mid\exists x\in
A:x\in V(H)\\}$ and

$\llbracket\mapsto\rrbracket=\\{((A_{1},A_{2}),H)\mid\exists x_{1}\in
A_{1}\text{ and }x_{2}\in A_{2}:H\text{ contains non-empty path }x_{1}\text{
to }x_{2}\\}.$

Let $r_{i}$ be an enumeration of resources in $Res$ and let $\varphi$ be a
formula with free variables amongst $r_{1},\ldots,r_{n}$. Then

$\displaystyle\\{(r_{1},A_{1}),\ldots,(r_{n},A_{n})\\},G\vDash\varphi\text{
iff
}((A_{1},\ldots,A_{n}),G),\llbracket-\rrbracket\vDash^{\\{r_{1},\ldots,r_{n}\\}}\varphi.$
∎

It remains to show satisfibility coincides for ILGL hyperdoctrines and indexed
layered frames. We first obtain an ILGL hyperdoctrine from an indexed layered
frame.

[Complex Hyperdoctrine] Given an indexed layered frame
$\mathcal{R}:\mathrm{C}\rightarrow\mathrm{IntLayFr}$, the _complex
hyperdoctrine_ of $\mathcal{R}$,
$Com(\mathcal{R}(-)):\mathrm{C}^{op}\rightarrow\mathrm{Poset}$, is defined by
extending $Com(\mathcal{R}(-))$ (Definition 4.2) to morphisms by
$Com(\mathcal{R}(f))=(\mathcal{R}(f))^{-1}$ and setting
$Ran(\mathcal{R}(\Delta_{X}))$ as $=_{X}$, $\mathcal{R}(\pi_{\Gamma,X})^{*}$
as $\exists X_{\Gamma}$, and $\mathcal{R}(\pi_{\Gamma,X})_{*}$ as $\forall
X_{\Gamma}$, where $\mathcal{R}(\pi_{\Gamma,X})^{*}(A)=\\{x\mid\text{there
exists }y\in A:\mathcal{R}(\pi_{\Gamma,X})(y)\preccurlyeq x\\}$ and
$\mathcal{R}(\pi_{\Gamma,X})_{*}(A)=\\{x\mid\text{for all }y,\text{ if
}x\preccurlyeq\mathcal{R}(\pi_{\Gamma,X})(y)\text{ then }y\in A\\}$ ∎ Given
that the complex operations are designed to mimic the semantic clauses, one
might expect the direct image $\mathcal{R}(\pi_{\Gamma,X})$ to be given as
$\exists X_{\Gamma}$ rather than $\mathcal{R}(\pi_{\Gamma,X})^{*}$. We note
that these define precisely the same functions because
$\mathcal{R}(\pi_{\Gamma,X})$ is an intuitionistic layered p-morphism:
property (2) of Definition 22 easily shows this to be the case. The
formulation of $\mathcal{R}(\pi_{\Gamma,X})^{*}$ simplifies many proofs in
what follows, however.

######  Lemma 35.

Given an indexed layered frame
$\mathcal{R}:\mathrm{C}\rightarrow\mathrm{IntLayFr}$, the complex
hyperdoctrine $Com(\mathcal{R}(-))$ is an ILGL hyperdoctrine.

######  Proof 6.1.

By Lemma 23 $Com(\mathcal{R}(X))$ is a layered Heyting algebra, and by a
similar argument to ILGL duality each $Com(\mathcal{R}(f))$ is a layered
Heyting algebra homomorphism. As $Ran(\mathcal{R}(\Delta_{X}))$ is upward-
closed by property (2) of Definition 22, it is an element of
$Com(\mathcal{R}(X\times X))$, as required. We also have that
$\mathcal{R}(\pi_{\Gamma,X})^{*}$ and $\mathcal{R}(\pi_{\Gamma,X})_{*}$ map
upward-closed sets to upward-closed sets and are monotone with respect to
$\subseteq$. The adjointness properties of $=_{X}$, $\exists X_{\Gamma}$ and
$\forall X_{\Gamma}$ are then all easily verified.

We thus concentrate on the remaining property, naturality. We restrict
ourselves to the case for $\exists X_{\Gamma}$. Let
$s:\Gamma\rightarrow\Gamma^{\prime}$ be a morphism in $\mathrm{C}$. and
suppose $A\in Com(\mathcal{R}(\Gamma^{\prime}\times X))$. We must show
$\mathcal{R}(\pi_{\Gamma,X})^{*}(\mathcal{R}(s\times
id_{X})^{-1}(A))=\mathcal{R}(s)^{-1}(\mathcal{R}(\pi_{\Gamma^{\prime},X})*(A))$.
Suppose $x\in\mathcal{R}^{*}(\pi_{\Gamma,X})(\mathcal{R}(s\times
id_{X})^{-1}(A))$: then there exists $y$ such that
$\mathcal{R}(\pi_{\Gamma,X})(y)\preccurlyeq x$ and $\mathcal{R}(s\times
id_{X})(y)\in A$. We have
$\mathcal{R}(\pi_{\Gamma^{\prime},X})(\mathcal{R}(s\times
id_{X})(y))=\mathcal{R}(s)(\mathcal{R}(\pi_{\Gamma,X})(y))\preccurlyeq\mathcal{R}(s)(x)$.
Hence $x\in\mathcal{R}(s)^{-1}(\mathcal{R}(\pi_{\Gamma^{\prime},X})^{*}(A))$,
as required.

Conversely, assume
$x\in\mathcal{R}(s)^{-1}(\mathcal{R}(\pi_{\Gamma^{\prime},X})^{*}(A))$. Then
there exists $y\in A$ such that
$\mathcal{R}(\pi_{\Gamma^{\prime},X})(y)\preccurlyeq\mathcal{R}(s)(x)$. Then
by (Psuedo Epi), there exists $z$ such that
$\mathcal{R}(\pi_{\Gamma,X})(z)\preccurlyeq x$ and
$y\preccurlyeq\mathcal{R}(s\times id_{X})(z)$. By upwards-closure of $A$,
$\mathcal{R}(s\times id_{X})(z)\in A$. Hence
$x\in\mathcal{R}(\pi_{\Gamma,X})^{*}(\mathcal{R}(s\times id_{X})^{-1}(A))$, as
required.

As in the cases for the propositional logics, an interpretation
$\llbracket-\rrbracket$ on an indexed resource frame immediately yields an
interpretation on its complex hyperdoctrine, as each predicate symbol is
assigned an upward-closed subset. We overload the notation
$\llbracket-\rrbracket$ to also refer to the interpretation on the complex
hyperdoctrine because of this. By unpacking the definition of the semantic
clauses and noting the way they coincide with the analogous structure of the
complex hyperdoctrine, we can show satisfiability coincides in this case.

######  Lemma 36.

Given an indexed layered frame $\mathcal{R}$ and an interpretation
$\llbracket-\rrbracket$, for all formulae $\varphi$ of predicate ILGL in
context $\Gamma$, and all $x\in\mathcal{R}(\llbracket\Gamma\rrbracket)$ we
have $x\in\llbracket\varphi\rrbracket$ iff
$x,\llbracket-\rrbracket\vDash^{\Gamma}\varphi$. ∎

[Indexed Prime Filter Frame] Given an ILGL hyperdoctrine
$\mathbb{P}:\mathrm{C}^{op}\rightarrow\mathrm{Poset}$, the _indexed prime
filter frame_ $Pr(\mathbb{P}(-)):\mathrm{C}\rightarrow\mathrm{IntResFr}$ is
given by extending $Pr(\mathbb{P}(-))$ (Definition 24) to morphisms with
$Pr(\mathbb{P}(f))=(\mathbb{P}(f))^{-1}$. ∎

######  Lemma 37.

Given an ILGL hyperdoctrine
$\mathbb{P}:\mathrm{C}^{op}\rightarrow\mathrm{Poset}$, the indexed prime
filter frame $Pr(\mathbb{P}(-))$ is an indexed layered frame.

######  Proof 6.2.

We show (Psuedo Epi) holds. Assume we have objects $\Gamma,\Gamma^{\prime}$
and $X$ in $\mathrm{C}$ and a morphism $s:\Gamma\rightarrow\Gamma^{\prime}$.
Let prime filters $F_{0}$ and $F_{1}$ be such that
$\mathbb{P}(\pi_{\Gamma^{\prime},X})^{-1}(F_{1})\subseteq\mathbb{P}(s)^{-1}(F_{0})$.
As in Theorem 25 we can prove the existence of the required prime filter by
demonstrating the partial order of proper filters satisfying the property is
non-empty and invoking Zorn’s Lemma to yield a maximum that can be shown to be
prime.

Consider the filter $\alpha=[\mathbb{P}(s\times id_{X})(F_{1}))$. Suppose for
contradiction that $\alpha$ is not proper. Then there exists $a\in F_{1}$ such
that $\mathbb{P}(s\times id_{X})(a)=\bot$. By adjointness $\exists
X_{\Gamma}(\bot)=\bot$ so $\mathbb{P}(s)(\exists
X_{\Gamma^{\prime}}(a))=\exists X_{\Gamma}(\mathbb{P}(s\times
id_{X})(a))=\bot$. This entails $\exists
X_{\Gamma^{\prime}}(a)\not\in\mathbb{P}(s)^{-1}(F_{0})$ so $\exists
X_{\Gamma^{\prime}}(a)\not\in\mathbb{P}(\pi_{\Gamma^{\prime},X})^{-1}(F_{1})$
by assumption. However by adjointness and filterhood,
$\mathbb{P}(\pi_{\Gamma^{\prime},X})(\exists X_{\Gamma^{\prime}}(a))\in
F_{1}$, a contradiction.

Clearly $\mathbb{P}(s\times id_{X})^{-1}(\alpha)\subseteq F_{1}$. To see, the
other inclusion holds, let $a\in\mathbb{P}(\pi_{\Gamma,X})^{-1}(\alpha)$. Then
there exists $b\in F_{1}$ such that $\mathbb{P}(s\times
id_{X})(b)\leq\mathbb{P}(\pi_{\Gamma,X})(a)$. By adjointness $\exists
X_{\Gamma}(\mathbb{P}(s\times id_{X})(b))\leq a$ and so by naturality
$\mathbb{P}(s)(\exists X_{\Gamma^{\prime}}(b))\leq a$. Since
$\mathbb{P}(\pi_{\Gamma^{\prime},X})(\exists X_{\Gamma^{\prime}}(b))\in
F_{1}$, we have $\exists
X_{\Gamma^{\prime}}(b)\in\mathbb{P}(\pi_{\Gamma^{\prime},X})^{-1}(F_{1})\subseteq\mathbb{P}(s)^{-1}(F_{0})$.
Thus by filterhood, $a\in F_{0}$.

Given an interpretation $\llbracket-\rrbracket$ on an ILGL hyperdoctrine
$\mathbb{P}$ we can obtain an interpretation
$\widetilde{\llbracket-\rrbracket}$ on its indexed prime filter frame
$Pr(\mathbb{P}(-))$: $\widetilde{\llbracket-\rrbracket}$ is defined
identically to $\llbracket-\rrbracket$ everywhere except on predicate symbols,
where for an m-ary predicate symbol $P$ of type $X_{1},\ldots,X_{m}$,
$\widetilde{\llbracket P\rrbracket}=h_{\mathbb{P}(\llbracket
X_{1}\rrbracket\times\cdots\times\llbracket X_{m}\rrbracket)}(\llbracket
P\rrbracket)$.

######  Lemma 38.

Given an ILGL hyperdoctrine
$\mathbb{P}:\mathrm{C}^{op}\rightarrow\mathrm{Poset}$ and interpretation
$\llbracket-\rrbracket$, for all formulae $\varphi$ of predicate ILGL in
context $\Gamma$ and $F\in Pr(\mathbb{P}(\llbracket\Gamma\rrbracket))$,
$\llbracket\varphi\rrbracket\in F\text{ iff
}F,\widetilde{\llbracket-\rrbracket}\vDash^{\Gamma}\varphi.$

######  Proof 6.3.

Most of the cases follow immediately from the representation theorem for ILGL.
Of the new cases, we attend to universal quantification. The others are shown
by proving the existence of prime filter witnesses in much the same way as
Theorem 25.

For the case we consider, it suffices to prove $\forall\llbracket
X\rrbracket_{\llbracket\Gamma\rrbracket}(\llbracket\varphi\rrbracket)\in F$
iff for all prime filters $G$, if
$F\subseteq\mathbb{P}(\pi_{\llbracket\Gamma\rrbracket,\llbracket
X\rrbracket})^{-1}(G)$ then $\llbracket\varphi\rrbracket\in G$. Assume
$\forall\llbracket
X\rrbracket_{\llbracket\Gamma\rrbracket}(\llbracket\varphi\rrbracket)\in F$
and suppose $F\subseteq\mathbb{P}(\pi_{\llbracket\Gamma\rrbracket,\llbracket
X\rrbracket})^{-1}(G)$. Then
$\mathbb{P}(\pi_{\llbracket\Gamma\rrbracket,\llbracket
X\rrbracket})(\forall\llbracket
X\rrbracket_{\llbracket\Gamma\rrbracket}(\llbracket\varphi\rrbracket))\in G$.
By adjointness and upwards-closure, $\llbracket\varphi\rrbracket\in G$. In the
other direction, suppose $\forall\llbracket
X\rrbracket_{\llbracket\Gamma\rrbracket}(\llbracket\varphi\rrbracket)\not\in
F$. Then we can prove the existence of a prime filter $G$ satisfying
$F\subseteq\mathbb{P}(\pi_{\llbracket\Gamma\rrbracket,\llbracket
X\rrbracket})^{-1}(G)$ and $\llbracket\varphi\rrbracket\not\in G$. Consider
$\alpha=(\llbracket\varphi\rrbracket]$. We can assume this is proper because
otherwise $\llbracket\varphi\rrbracket=\top$ and $\forall\llbracket
X\rrbracket_{\llbracket\Gamma\rrbracket}(\llbracket\varphi\rrbracket)=\top\not\in
F$, a contradiction. We have that for any $a\in F$, by adjointness
$\mathbb{P}(\pi_{\Gamma,X})(b)\not\in\alpha$, since otherwise
$b\leq\forall\llbracket
X\rrbracket_{\llbracket\Gamma\rrbracket}(\llbracket\varphi\rrbracket)\in F$.
By an argument similar to that of Theorem 25, there therefore exists a prime
ideal $P$ such that $F\subseteq\mathbb{P}(\pi_{\Gamma,X})^{-1}(\overline{P})$
and $\llbracket\varphi\rrbracket\not\in\overline{P}$.

We thus obtain the equivalence of the hyperdoctrinal and truth-functional
semantics. This additionally yields completeness of the indexed resource frame
semantics with respect to the predicate ILGL Hilbert system.

######  Theorem 39.

For all formulae $\varphi$ of predicate ILGL: $\varphi$ is satisfiable (valid)
on ILGL hyperdoctrines iff $\varphi$ is satisfiable (valid) on indexed layered
frames. ∎

######  Corollary 40.

For all formuale $\varphi$ of predicate ILGL, $\varphi$ is provable iff
$\varphi$ is valid on indexed layered frames. ∎

###  6.2. Duality

To finish we extend this correspondence to a dual equivalence of categories,
in the same manner as the propositional case. We denote by
$U:\mathrm{IntLaySp}\rightarrow\mathrm{IntLayFr}$ the forgetful functor that
drops topology.

[Indexed Layered Space] An _indexed layered space_ is a functor
$\mathcal{R}:\mathrm{C}\rightarrow\mathrm{IntLaySp}$ such that the following
properties hold:

  1. (1)

The composition with the forgetful functor,
$U\circ\mathcal{R}:\mathrm{C}\rightarrow\mathrm{IntLayFr}$, is an indexed
layered frame;

  2. (2)

For each object $X$ in $\mathrm{C}$, $Ran(\mathcal{R}(\Delta_{X}))$ is clopen;

  3. (3)

For each pair of objects $\Gamma$ and $X$ in $\mathrm{C}$,
$\mathcal{R}(\pi_{\Gamma,X})^{*}$ and $\mathcal{R}(\pi_{\Gamma,X})_{*}$ map
upward-closed clopen sets to upward-closed clopen sets.

Given an indexed layered space
$\mathcal{R}:\mathrm{C}\rightarrow\mathrm{IntResFr}$ and an object $X$ in
$\mathrm{C}$ we denote the intuitionistic layered space at $X$ by
$\mathcal{R}(X)=(\mathcal{R}(X),\mathcal{O}_{\mathcal{R}(X)},\preccurlyeq_{\mathcal{R}(X)},R_{\mathcal{R}(X)})$.
∎

We now define morphisms to obtain categories of ILGL hyperdoctrines and
indexed layered spaces. Our definition of hyperdoctrine morphism adapts that
given for _coherent_ hyperdoctrines in [14].

[ILGL Hyperdoctrine Morphism] Given ILGL hyperdoctrines
$\mathbb{P}:\mathrm{C}^{op}\rightarrow\mathrm{Poset}$ and
$\mathbb{P}^{\prime}:\mathrm{D}^{op}\rightarrow\mathrm{Poset}$, an _ILGL
hyperdoctrine morphism_
$(\mathrm{K},\tau):\mathbb{P}\rightarrow\mathbb{P}^{\prime}$ is a pair
satisfying the following properties:

  1. (1)

$\mathrm{K}:\mathrm{C}\rightarrow\mathrm{D}$ is a finite product preserving
functor;

  2. (2)

$\tau:\mathbb{P}\rightarrow\mathbb{P}^{\prime}\circ K$ is a natural
transformation;

  3. (3)

For all objects $X$ in $\mathrm{C}$: $\tau_{X\times X}(=_{X})={\
}=^{\prime}_{K(X)}$;

  4. (4)

For all objects $\Gamma$ and $X$ in $\mathrm{C}$, the following squares
commute:

${\mathbb{P}(\Gamma\times X)}$${\mathbb{P^{\prime}}(K(\Gamma)\times
K(X))}$${\mathbb{P}(\Gamma)}$${\mathbb{P^{\prime}}(K(\Gamma))}$$\scriptstyle{\tau_{\Gamma\times
X}}$$\scriptstyle{\exists
X_{\Gamma}}$$\scriptstyle{\exists^{\prime}K(X)_{K(\Gamma)}}$$\scriptstyle{\tau_{\Gamma}}$${\mathbb{P}(\Gamma\times
X)}$${\mathbb{P^{\prime}}(K(\Gamma)\times
K(X))}$${\mathbb{P}(\Gamma)}$${\mathbb{P^{\prime}}(K(\Gamma))}$$\scriptstyle{\tau_{\Gamma\times
X}}$$\scriptstyle{\forall
X_{\Gamma}}$$\scriptstyle{\forall^{\prime}K(X)_{K(\Gamma)}}$$\scriptstyle{\tau_{\Gamma}}$

The composition of ILGL hyperdoctrine morphisms
$(K,\tau):\mathbb{P}\rightarrow\mathbb{P}^{\prime}$ and
$(K^{\prime},\tau^{\prime}):\mathbb{P}^{\prime}\rightarrow\mathbb{P}^{\prime\prime}$
is given by $(K^{\prime}\circ K,\tau^{\prime}_{K(-)}\circ\tau)$. This yields a
category $\mathrm{ILGLHyp}$. ∎

[Indexed Layered Space Morphism] Given indexed layered spaces
$\mathcal{R}:\mathrm{C}\rightarrow\mathrm{IntLaySp}$ and
$\mathcal{R}^{\prime}:\mathrm{D}\rightarrow\mathrm{IntLaySp}$, an _indexed
layered space morphism_
$(L,\lambda):\mathcal{R}\rightarrow\mathcal{R}^{\prime}$ is a pair
$(L,\lambda)$ such that

  1. (1)

$L:D\rightarrow C$ is a finite product preserving functor;

  2. (2)

$\lambda:\mathcal{R}\circ L\rightarrow\mathcal{R}^{\prime}$ is a natural
transformation;

  3. (3)

(Lift Property) If there exists $x$ and $y$ such that
$\mathcal{R}^{\prime}(\Delta_{X})(y)\preccurlyeq\lambda_{X\times X}(x)$ then
there exists $y^{\prime}$ such that
$\mathcal{R}(\Delta_{L(X)})(y^{\prime})\preccurlyeq x$;

  4. (4)

(Morphism Pseudo Epi) If there exists $x$ and $y$ with
$\mathcal{R}^{\prime}(\pi_{\Gamma,X})(x)\preccurlyeq\lambda_{\Gamma}(y)$ then
there exists $z$ such that $x\preccurlyeq\lambda_{\Gamma\times X}(z)$ and
$\mathcal{R}(\pi_{L(\Gamma),L(X)})(z)\preccurlyeq y$.

The composition of indexed layered space morphisms
$(L^{\prime},\lambda^{\prime}):\mathcal{R}^{\prime}\rightarrow\mathcal{R}^{\prime\prime}$
and $(L,\lambda):\mathcal{R}\rightarrow\mathcal{R}^{\prime}$ is given by
$(L\circ L^{\prime},\lambda^{\prime}\circ\lambda_{L^{\prime}(-)})$. This
yields a category $\mathrm{IndLaySp}$. ∎

We now define functors
$\mathfrak{F}:\mathrm{ILGLHyp}\rightarrow\mathrm{IndLaySp}$ and
$\mathfrak{G}:\mathrm{IndLaySp}\rightarrow\mathrm{ILGLHyp}$. The functors
$\mathrm{F}:\mathrm{LayHeyAlg}\rightarrow\mathrm{IntLaySp}$ and
$\mathrm{G}:\mathrm{IntLaySp}\rightarrow\mathrm{LayHeyAlg}$ are as in ILGL
duality in Section 5 and $X$ and $\Gamma$ range over objects of $\mathrm{C}$.

$\begin{cases}\mathfrak{F}(\mathbb{P})=\mathrm{F}\circ\mathbb{P}\\\
\mathfrak{F}f:\mathfrak{F}(\mathbb{P}^{\prime})\rightarrow\mathfrak{F}(\mathbb{P}),(K,\tau)\mapsto(K,\tau^{-1})\end{cases}\begin{cases}\mathfrak{G}(\mathcal{R})=(\mathrm{G}\circ\mathcal{R},Ran(\mathcal{R}(\Delta_{X})),\mathcal{R}(\pi_{\Gamma,X})^{*},\mathcal{R}(\pi_{\Gamma,X})_{*})\\\
\mathfrak{G}g:\mathfrak{G}(\mathcal{R}^{\prime})\rightarrow\mathrm{G}(\mathcal{R}),(L,\lambda)\mapsto(L,\lambda^{-1})\end{cases}$

######  Lemma 41.

The functor $\mathfrak{F}:\mathrm{ILGLHyp}\rightarrow\mathrm{IndLaySp}$ is
well defined.

######  Proof 6.4.

We first show $\mathfrak{F}$ is well defined on objects. Let $\mathbb{P}$ be a
ILGL hyperdoctrine. We show $\mathfrak{F}(\mathbb{P})$ is an indexed layered
space. As $U\circ F\circ\mathbb{P}=Pr(\mathbb{P}(-))$, Lemma 37 suffices to
give 1). For 2), it can easily be shown that adjointness of $=_{X}$ yields
$Ran(\mathbb{P}(\Delta_{X})^{-1})=h_{\mathbb{P}(X\times X)}(=_{X})$, a clopen
set. For 3), we note that by Esakia duality the upward-closed clopen sets in
the domain of $(\mathcal{P}(\pi_{\Gamma,X})^{-1})^{*}$ and
$(\mathcal{P}(\pi_{\Gamma,X})^{-1})_{*}$ are all of the form
$h_{\mathbb{P}(\Gamma\times X)}(a)$. A simple application of the adjointness
properties shows that
$(\mathcal{P}(\pi_{\Gamma,X})^{-1})^{*}(h_{\mathbb{P}(\Gamma\times
X)}(a))=h_{\mathbb{P}(\Gamma)}(\exists X_{\Gamma}(a))$ and
$(\mathcal{P}(\pi_{\Gamma,X})^{-1})_{*}(h_{\mathbb{P}(\Gamma\times
X)}(a))=h_{\mathbb{P}(\Gamma)}(\forall X_{\Gamma}(a))$.

Now let $(K,\tau)$ be an ILGL hyperdoctrine morphism. To see
$\mathfrak{F}(K,\tau)$ is an indexed resource space morphism, note that $K$ is
finite product preserving by definition and naturality of $\tau^{-1}$ is
inherited. By ILGL duality, each component is an intuitionistic layered space
morphism. Finally, (Lift Property) and (Morphism Pseudo Epi) are verified in
much the same way as (Psuedo Epi) in Lemma 37, using property (3) of the
hyperdoctrine morphism definition for the former and (4) for the latter.

######  Lemma 42.

The functor $\mathfrak{G}:\mathrm{IndLaySp}\rightarrow\mathrm{ILGLHyp}$ is
well defined.

######  Proof 6.5.

First we verify objects. Given an indexed layered space $\mathcal{R}$,
$\mathfrak{G}(\mathcal{R})$ is clearly a functor of the right sort, with ILGL
duality giving that each $\mathfrak{G}(\mathcal{R})(X)$ is a layered Heyting
algebra and each $\mathfrak{G}(\mathfrak{R})(f)$ is a layered Heyting algebra
homomorphism. By assumption, for each object $X$,
$Ran(\mathcal{R}(\Delta_{X}))$ is clopen and by Lemma 35 it is also upwards
closed. Hence
$Ran(\mathcal{R}(\Delta_{X}))\in\mathfrak{G}(\mathcal{R})(X\times X)$, as
required. We also have that $\mathcal{R}(\pi_{\Gamma,X})^{*}$ and
$\mathcal{R}(\pi_{\Gamma,X})_{*}$ map upward-closed clopen sets to upward-
closed clopen sets by definition. Hence they are monotone maps
$\mathfrak{G}(\mathcal{R})(\Gamma\times
X)\rightarrow\mathfrak{G}(\mathcal{R})(\Gamma)$, as required. The adjointness
and naturality properties then follow from Lemma 35.

We now check morphisms. Let $(L,\lambda)$ be an indexed resource space
morphism. Then as in the previous lemma, $L$ is a finite product preserving
functor by assumption and $\lambda^{-1}$ inherits naturality. By ILGL duality,
since each component of $\lambda$ is an intuitionistic layered frame morphism,
each component of $\lambda^{-1}$ is layered Heyting algebra homomorphism.
Finally, preservation of $=_{X}$ follows from (Lift Property) and
commutativity of the adjoints follows from (Morphism Psuedo Epi): the proofs
are similar to that given in Lemma 35.

######  Theorem 43.

The categories $\mathrm{ILGLHyp}$ and $\mathrm{IndLaySp}$ are dually
equivalent.

######  Proof 6.6.

We obtain the required natural transformations from ILGL duality: the maps
$(Id_{\mathrm{ILGLHyp}},h_{\mathbb{P}(-)}):\mathbb{P}\rightarrow\mathfrak{GF}(\mathbb{P})$
and
$(Id_{\mathrm{IndLaySp}},f_{\mathcal{R}(-)}):\mathcal{R}\rightarrow\mathfrak{FG}(\mathcal{R})$
define the components at $\mathbb{P}$ and $\mathcal{R}$, respectively. It
remains to verify that each is a morphism in the respective category, and that
they indeed form natural isomorphisms.

First, that $(Id_{\mathrm{ILGLHyp}},h_{\mathbb{P}(-)})$ is an ILGL
hyperdoctrine morphism. Clearly, it is a functor and a natural transformation
of the right kind. Further, we know $h_{\mathbb{P}(X\times
X)}(=_{X})=Ran(\mathbb{P}(\Delta_{X})^{-1})$, satisfying $=_{X}$ preservation.
That $h_{\mathbb{P}(-)}$ commutes with the adjoints is shown by a similar
argument to that given in Lemma 38.

For the case for $(Id_{\mathrm{IndLaySp}},f_{\mathcal{R}(-)})$, we once again
have that the functor and natural transformation are of the right sort. To see
that (Lift Property) holds, let $x\in\mathcal{R}(X\times X)$ and
$F\in\mathfrak{FG}(X)$ with $\mathfrak{FG}(\Delta_{X})(F)\subseteq
f_{\mathcal{R}(X\times X)}(x)$. Then for any upward-closed clopen set $C$, if
$\mathcal{R}(\Delta_{X})^{-1}(C)\in F$ then $x\in C$. By Esakia duality, there
exists $z$ such that $f_{\mathcal{R}(X)}(z)=F$. Suppose
$\mathcal{R}(\Delta_{X})(z)\not\preccurlyeq x$. Then by the Priestley
separation axiom there exists an upward-closed clopen set $C$ such that
$\mathcal{R}(\Delta_{X})(z)\in C$ and $x\not\in C$: but then
$z\in\mathcal{R}(\Delta_{X})^{-1}(C)$ so $\mathcal{R}(\Delta_{X})^{-1}(C)\in
F$ and $x\in C$. It must thus be the case that
$\mathcal{R}(\Delta_{X})(z)\preccurlyeq x$. (Morphism Psuedo Epi) is shown in
much the same way.

Finally, that these components form natural isomorphisms follows immediately
from the fact that $h_{(-)}$ and $f_{(-)}$ are natural isomorphisms by ILGL
duality.

##  7\. Conclusions & Further Work

In this paper we have given a comprehensive metatheoretic treatment of an
intuitionistic substructural logic for reasoning about layered graphs, ILGL.
Most notably, we give a semantics on layered graphs that is a sound and
complete with respect to a labelled tableaux system with countermodel
extraction. An equivalent algebraic and relational semantics is also given,
and can be used to bridge the gap between the labelled tableaux system and
sequential systems – including a display calculus with cut elimination – that
directly present an algebraic semantics. This is done via a representation
theorem that can be extended to a full topological duality. This metatheory is
also provided for the natural predicate logic extension of ILGL. Finally,
decidability of propositional ILGL is proved algebraically by establishing the
finite embeddability property for the logic’s algebraic semantics.

A first direction for further work is real systems modelling and verification
with ILGL. A good first step would be the class of bigraph models, given ILGL
appears to be suited to reasoning about them. A thorough investigation of a
suitable signature of predicate ILGL for use as an assertion language for
bigraph models would be an appropriate starting point, with an extension to a
Separation Logic-style language incorporating a dynamics corresponding to
Bigraphical Reactive Systems as an end goal. This in itself would represent a
rich program of research. Reformulating the proof theoretic properties that
makes Separation Logic scalable – for example, the frame rule and bi-abduction
[6] – in this setting would also make a strong contribution to the theory of
application of bigraphs.

Further logical work can be done as well. As previously discussed, layered
graph logics are the bunched logics with the weakest multiplicatives. It is
thus possible to reconstruct the other systems in the literature by adding
appropriate structure to the metatheory of the layered graph logics. We aim to
use these logics as a foundation for a systematic treatment of the entire
hierarchy of bunched logics, including a uniform construction of semantics and
proof theory. In this direction we have already proved representation and
duality theorems for the breadth of the bunched logics in the literature,
obtaining systematic soundness and completeness theorems for each logic as a
corollary. Such a treatment can also guide the design of Henessey-Millner-van
Bentham style logics of state for location-resource-processes [9, 10, 16] that
incorporate layering.

## References

  * [1] G. Anderson and D. Pym.  A calculus and logic of bunched resources and processes.  Theor. Comp. Sci. 614:63-96, 2016.
  * [2] N. Bezhanishvili and D. de Jongh.  Intuitionistic logic.  Technical Report PP-2006-25, Institute for Logic, Language and Computation, Universiteit van Amsterdam, 2006.
  * [3] B.Biering, L. Birkedal, and N. Torp-Smith.  BI hyperdoctrines and higher-order separation logic.  In Proc. 14th ESOP, 233–247, Springer-Verlag, 2005.
  * [4] K. Bimbó and J. M. Dunn.  Generalized Galois Logics: Relational Semantics of Non-classical Calculi.  CSLI Publications, 2008.
  * [5] P. Bródka, K. Skibicki, P. Kazienko, and K. Musiał.  A degree centrality in multi-layered social network.  In Proc. CASoN ’11, 237–242, 2011.
  * [6] C. Calcagno, D. Distefano, P. O’Hearn, and H. Yang.  Compositional shape analysis by means of bi-abduction.  J. ACM, 58(6), 2011.
  * [7] L. Cardelli, P. Gardner, G. Ghelli.  A spatial logic for querying graphs.  In _Proc ICALP ’02_ , LNCS 2380, 597–610, 2002.
  * [8] D. D. Clark.  The design philosophy of the DARPA internet protocols.  In Proc. SIGCOMM ’88, Computer Communication Review, 18(4): 106–114, 1988.
  * [9] M. Collinson, K. McDonald, and D. Pym.  A substructural logic for layered graphs.  J. Log. Comp., 24(4):953–988, 2014.
  * [10] M. Collinson, K. McDonald, and D. Pym.  Layered graph logic as an assertion language for access control policy models.  J. Log. Comp., 27(1):41–80 2017.
  * [11] M. Collinson, B. Monahan, and D. Pym.  A Discipline of Mathematical Systems Modelling.  College Publications, 2012.
  * [12] M. Collinson and D. Pym.  Algebra and logic for resource-based systems modelling.  Math. Struc. Comp. Sci., 19(5):959–1027, 2009\.
  * [13] G. Conforti, D. Macedonio, and V. Sassone.  Spatial logics for bigraphs.  In Proc. ICAP ’05, LNCS 3580, 766–778, 2005.
  * [14] D. Coumans.  Generalising canonical extension to the categorical setting.  Ann. Pure. Appl. Log., 163(12):1940–1961, 2012.
  * [15] J.-R. Courtault and D. Galmiche.  A modal separation logic for resource dynamics. _Journal of Logic and Computation_ , doi:10.1093/logcom/exv031, 2015.
  * [16] S. Docherty and D. Pym.  Intuitionistic layered graph logic.   _Proc. IJCAR 2016_. LNAI 9706: 469–486, 2016.
  * [17] J. M. Dunn and G. Hardegree.  Algebraic Methods In Philosophical Logic OUP, 2001.
  * [18] L. Esakia.  Topological Kripke models.  Soviet Math. Dokl. 15, 147–15, 1974.
  * [19] M. Fitting.  Tableau methods of proof for modal logics.  Notre Dame J. Fom. Log., 13(2):237–247, 1972.
  * [20] N. Galatos and P. Jipsen.  Distributive residuated frames and generalized bunched implication algebras.  Algebra Univers., 78(3):303–336, 2017.
  * [21] D. Galmiche and D. Méry.  Tableaux and resource graphs for separation logic.  J. Log. Comp., 20(1): 189-231, 2010.
  * [22] D. Galmiche, D. Méry, and D. Pym.  The semantics of BI and resource tableaux.  Math. Str. Comp. Sci., 15(06):1033–1088, 2005\.
  * [23] J.-Y. Girard.  Linear logic.  Theor. Comp. Sci., 50(1): 1–101, 1987.
  * [24] L. Gouveia, L. Simonetti, and E. Uchoa.  Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs.  _Math. Prog._ , 128(1): 123–148, 2011.
  * [25] D. Grohmann and M. Miculan.  Directed bigraphs.  In Proc. MFPS XXIII, ENTCS 173, 121–137, 2007.
  * [26] Z. Haniková and R. Horc̆ík.  The finite embeddability property for residuated groupoids  Algebra Univers., 72(1):1–13, 2014.
  * [27] J. Harland and D. Pym.  Resource-distribution via Boolean constraints.  _ACM ToCL_ , 4(1):56–90, 2003.
  * [28] S. S. Ishtiaq and P. O’Hearn.  BI as an assertion language for mutable data structures.  In Proc. POPL ’01, ACM Sigplan Notices 36(3):14–26, 2001.
  * [29] P. Jipsen and T. Litak.  An algebraic glimpse at bunched implications and separation logic.  In Outstanding Contributions: Hiroakira Ono on Residuated Lattices and Substructural Logics, arXiv:1709.07063v2, to appear.
  * [30] P. Jipsen and C. Tsinakis.  A survey of residuated lattices.  In _Ordered Algebraic Structures_ , Developments in Mathematics 7:19-56, 2002.
  * [31] P. T. Johnstone  Stone Spaces.  Cambridge Studies In Advanced Mathematics 3, CUP, 1982.
  * [32] M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno and M. A. Porter.  Multilayer networks.  J. Comp. Net., 2(3): 203–271, 2014.
  * [33] S. A. Kripke.  A semantical analysis of intuitionistic logic I.  In Formal Systems and Recursive Functions, Studies In Logic and the Foundations of Mathematics 40:92–130, 1965.
  * [34] M. Kurant and P. Thiran.  Layered complex networks.  Phys. Rev. Lett., 96:138701, 2006.
  * [35] J. Lambek.  On the calculus of syntactic types.  In Studies of Language and its Mathematical Aspects, 166–178, 1961.
  * [36] J. Lambek.  From categorical grammar to bilinear logic.  In P. Schroeder-Heister and K. Došen, editors, Substructural Logics, 207–237. OUP, 1993.
  * [37] D. Larchey-Wendling.  The formal proof of the strong completeness of partial monoidal Boolean BI.  J. Log. Comp., 26(2):605–640, 2016.
  * [38] C. Maus, S. Rybacki, and A. M. Uhrmacher.  Rule-based multi-level modeling of cell biological systems  BMC Sys. Bio., 5(166), doi:10.1186/1752-0509-5-166, 2011.
  * [39] R. Milner.  The Space and Motion of Communicating Agents.  CUP, 2009.
  * [40] P. O’Hearn and D. Pym.  The logic of bunched implications.  Bull. Symb. Log., 5(2):215–244, 1999.
  * [41] D. Pym, P. O’Hearn, and H. Yang.  Possible worlds and resources: The semantics of BI.  Theor. Comp. Sci., 315(1):257–305, 2004.
  * [42] J.C. Reynolds.  Separation logic: a logic for shared mutable data structures.  In Proc LICS ’02, IEEE Comp. Soc. Press, 55–74 2002.
  * [43] M.H. Stone.  The theory of representations of Boolean algebras.  Trans. AMS 40: 37–111, 1936.
  * [44] H. Wang, J. Wang and P. De Wilde.  Topological analysis of a two coupled evolving networks model for business systems.  Expert Syst. Appl., 36(5):9548–9556, 2009.


# Investigating an approach for low resource language dataset creation,
curation and classification: Setswana and Sepedi

###### Abstract

The recent advances in Natural Language Processing have been a boon for well
represented languages in terms of available curated data and research
resources. One of the challenges for low-resourced languages is clear
guidelines on the collection, curation and preparation of datasets for
different use-cases. In this work, we take on the task of creation of two
datasets that are focused on news headlines (i.e short text) for Setswana and
Sepedi and creation of a news topic classification task. We document our work
and also present baselines for classification. We investigate an approach on
data augmentation, better suited to low resource languages, to improve the
performance of the classifiers.

languageresourceLanguage Resources

Investigating an approach for low resource language dataset creation, curation
and classification: Setswana and Sepedi

Vukosi Marivate${}^{1}{}^{,}{}^{2}$, Tshephisho Sefara2, Vongani Chabalala3,
Keamogetswe Makhaya4, Tumisho Mokgonyane5, Rethabile Mokoena6, Abiodun
Modupe${}^{7}{}^{,}{}^{1}$
---
University of Pretoria1, CSIR2, University of Zululand3, University of Cape
Town4,
University of Limpopo5, North-West University6, University of the
Witwatersrand7
<EMAIL_ADDRESS><EMAIL_ADDRESS>

Abstract content

##  1\. Introduction

The most pressing issue with low-resource languages is of insufficient
language resources. In this study, we introduce an investigation of a low-
resource language that provides automatic formulation and customization of new
capabilities from existing ones. While there are more than six thousand
languages spoken globally, the openness of resources for each is
extraordinarily unbalanced [Nettle, 1998]. For example, if we focus on
language resources annotated on the public domain, as of November 2019, AG
corpus released about $496,835$ news articles only in English languages from
more than $200$ sources111http://groups.di.unipi.it/~gulli, Reuters News
Dataset [Lewis, 1997] comprise an roughly $10,788$ annotated texts from the
Reuters financial newswire. The New York Times Annotated Corpus [Sandhaus,
2008] holds over $1.8$ million articles, and there are no standard annotated
tokens in the low-resource language. Google Translate only supports around 100
languages [Johnson et al., 2017]. A significant number of bits of knowledge
focus on a small number of languages neglecting $17\%$ out of the world’s
language categories label as low-resource [Strassel and Tracey, 2016], which
makes it challenging to develop various mechanisms for Natural Language
Processing (NLP).

In South Africa several of the news websites (private and public) are
published in English, even though there are 11 official languages (including
English). We list the top premium newspapers by circulation as per first
Quarter 2019 [Bureau of Circulations, 2019] in Table 1. We do not have a
distinct collection of a diversity of languages with most of the reported
datasets as existed in English, Afrikaans and isiZulu. In this work, we aim to
provide a general framework that enables us to create an annotated linguistic
resource for Setswana and Sepedi news headlines. We apply data sources of the
news headlines from the South African Broadcast Corporation (SABC)
222http://www.sabc.co.za/, their social media streams and a few acoustic news.
Unfortunately, we do not have any direct access to news reports, so we hope
this study will promote collaboration between the national broadcaster and NLP
researchers.

Table 1: Top newspapers in South Africa with their languages Paper | Language | Circulation
---|---|---
Sunday Times | English | 260132
Soccer Laduma | English | 252041
Daily Sun | English | 141187
Rapport | Afrikaans | 113636
Isolezwe | isiZulu | 86342
Sowetan | English | 70120
Isolezwe ngeSonto | isiZulu | 65489
Isolezwe ngoMgqibelo | isiZulu | 64676
Son | Afrikaans | 62842

The rest of the work is organized as follows. Section 2. discusses prior work
that has gone into building local corpora in South Africa and how they have
been used. Section 3. presents the proposed approach to build a local news
corpora and annotating the corpora with categories. From here, we focus on
ways to gather data for vectorization and building word embeddings (needing an
expanded corpus). We also release and make pre-trained word embeddings for 2
local languages as part of this work [Marivate and Sefara, 2020a]. Section 4.
investigate building classification models for the Setswana and Sepedi news
and improve those classifiers using a 2 step augmentation approach inspired by
work on hierarchical language models [Yu et al., 2019]. Finally, Section 5.
concludes and proposes a path forward for this work.

##  2\. Prior Work

Creating sizeable language resources for low resource languages is important
in improving available data for study [Zoph et al., 2016] and cultural
preservation. If we focus our attention on the African continent, we note that
there are few annotated datasets that are openly available for tasks such as
classification. In South Africa, the South African Center for Digital Language
Resources (SADILAR) 333www.sadilar.org has worked to curate datasets of local
South African languages. There remain gaps such as accessing large corpora and
data from sources such as broadcasters and news organizations as they have
sizeable catalogs that are yet to make it into the public domain. In this
work, we work to fill such a gap by collecting, annotating and training
classifier models for news headlines in Setswana and Sepedi. As the data that
we do find publicly is still small, we also have to deal with the challenges
of Machine Learning on small data.

Machine learning systems perform poorly in presence of small training sets due
to overfitting. To avoid this problem, data augmentation can be used. The
technique is well known in the field of image processing [Cubuk et al., 2019].
Data augmentation refers to the augmentation of the training set with
artificial, generated, training examples. This technique is used less
frequently in NLP but a number of few studies applied data augmentation.

?) use data augmentation to counteract overfitting where recurrent neural
network (RNN) Encoder-Decoder is implemented specifically geared toward a low-
resource setting. Authors apply data augmentation by finding words that share
word stem for example fizzle and fizzling share fizzl. Then authors replace a
stem with another string.

?) apply data augmentation by using synonyms as substitute words for the
original words. However, ?) states that synonyms are very limited and the
synonym-based augmentation cannot produce numerous different patterns from the
original texts. Hence, ?) proposes contextual data augmentation by replacing
words that are predicted by a language model given the context surrounding the
original words to be augmented.

As ?) states that these techniques are valid, they are not often used in
practice because they have a high cost of implementation relative to
performance gain. They propose an easy data augmentation as techniques for
boosting performance on text classification tasks. These techniques involve
synonym replacement, random insertion, random swap, and random deletion of a
word. Authors observed good performance when using fraction of the dataset
(%):1, 5, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, as the data size increases,
the accuracy also increases for augmented and original data. Original data
obtained highest accuracy of 88.3% at 100% data size while augmented data
obtained accuracy of 88.6% at 50% data size.

In this work, we investigate the development of a 2 step text augmentation
method in order to be improve classification models for Setswana and Sepedi.
To do this we had to first identify a suitable data source. Collect the data,
and then annotate the datasets with news categories. After the data is
collected and annotated, we then worked to create classification models from
the data as is and then use a word embedding and document embedding
augmentation approach.

##  3\. Developing news classification models for Setswana and Sepedi

Here we discuss how data was collected as well as the approach we use to build
classification models.

###  3.1. Data Collection, Cleaning and Annotation

Before we can train classification models, we first have to collect data for 2
distinct processes. First, we present our collected news dataset as well as
its annotation. We then discuss how we collected larger datasets for better
vectorization.

####  3.1.1. News data collection and annotation

The news data we collected is from the SABC444http://www.sabc.co.za/ Facebook
pages. The SABC is the public broadcaster for South Africa. Specifically, data
was collected from the Thobela FM (An SABC Sepedi radio
station)555https://www.facebook.com/thobelafmyaka/ and Motsweding FM (An SABC
Setswana radio station)666https://www.facebook.com/MotswedingFM/. We scraped
the news headlines that are published as posts on both Facebook pages. We
claim no copyright for the content but used the data for research purposes. We
summarize the datasets in Table 2. We visualize the token distributions in
Sepedi and Setswana in Figures 1 and 2 respectively.

Table 2: News Data Sets | Setswana | Sepedi
---|---|---
Corpus Size (headlines) | 219 | 491
Number of Tokens (words) | 1561 | 3018
Figure 1: Setswana Wordcloud Figure 2: Sepedi Wordcloud

As can be seen, the datasets are relatively small and as such, we have to look
at other ways to build vectorizers that can better generalize as the word
token diversity would be very low.

We annotated the datasets by categorizing the news headlines into: _Legal_ ,
_General News_ ,_Sports_ , _Other_ , _Politics_ , _Traffic News_ , _Community
Activities_ , _Crime_ , _Business_ and _Foreign Affairs_. Annotation was done
after reading the headlines and coming up with categories that fit both
datasets. We show the distribution of the labels in both the Setswana and
Sepedi data sets in Figures 3 and 4 respectively. For this work, we only
explore single label categorization for each article. It remains future work
to look at the multi-label case. As such, there might be some noise in the
labels. Examples from the Sepedi annotated news corpus are shown next:

> _Tsela ya N1 ka Borwa kgauswi le Mantsole Weighbridge ka mo Limpopo ebe e
> tswaletswe lebakanyana ka morago ga kotsi yeo e hlagilego._ Traffic
>
> _Tona ya toka Michael Masutha,ore bahlankedi ba kgoro ya ditirelo tsa
> tshokollo ya bagolegwa bao ba tateditswego dithieeletsong tsa khomisene ya
> go nyakisisa mabarebare a go gogwa ga mmuso ka nko,ba swanetse go hlalosa
> gore ke ka lebaka la eng ba sa swanelwa go fegwa mesomong_ Legal

Figure 3: Setswana news title category distribution Figure 4: Sepedi news
title category distribution

The full dataset is made available online [Marivate and Sefara, 2020b] for
further research use and improvements to the
annotation777https://zenodo.org/record/3668495. As previously discussed, we
used larger corpora to create language vectorizers for downstream NLP tasks.
We discuss this next.

####  3.1.2. Vectorizers

Before we get into the annotated dataset, we needed to create pre-trained
vectorizers in order to be able to build more classifiers that generalize
better later on. For this reason we collected different corpora for each
language in such as way that we could create Bag of Words, TFIDF, Word2Vec
[Mikolov et al., 2013] and FastText [Bojanowski et al., 2017] vectorizers
(Table 3). We also make these vectorizers available for other researchers to
use.

Table 3: Vectorizer Corpora Sizes in number of lines (number of tokens) Source | Setswana | Sepedi
---|---|---
Wikipedia | 478(_21924_)888https://tn.wikipedia.org/ | 300(_10190_)999https://nso.wikipedia.org/
JW300101010http://opus.nlpl.eu/JW300.php | 874464(_70251_) | 618275(_53004_)
Bible | 3110(_40497_) | 29723
Constitution111111https://www.justice.gov.za/legislation/constitution/pdf.html | 7077(_3940_) | 6564(_3819_)
SADILAR121212https://www.sadilar.org/index.php/en/resources | 33144(_61766_) | 67036(_87838_)
Total | 946264(_152027_) | 721977(_149355_)

###  3.2. News Classification Models

We explore the use of a few classification algorithms to train news
classification models. Specifically we train

  * •

Logistic Regression,

  * •

Support Vector Classification,

  * •

XGBoost, and

  * •

MLP Neural Network.

To deal with the challenge of having a small amount of data on short text, we
use data augmentation methods, specifically a word embedding based
augmentation [Wang and Yang, 2015], approach that has been shown to work well
on short text [Marivate and Sefara, 2019]. We use this approach since we are
not able to use other augmentation methods such as synonym based (requires
developed Wordnet Synsets [Kobayashi, 2018]), language models (larger corpora
needed train) and back-translation (not readily available for South African
languages). We develop and present the use of both word and document
embeddings (as an augmentation quality check) inspired by a hierarchical
approach to augmentation [Yu et al., 2019].

##  4\. Experiments and Results

This Section presents the experiments and results. As this is still work in
progress, we present some avenues explored in both training classifiers and
evaluating them for the task of news headline classification for Setswana and
Sepedi.

###  4.1. Experimental Setup

For each classification problem, we perform 5 fold cross validation. For the
bag-of-words and TFIDF vectorizers, we use a maximum token size of 20,000. For
word embeddings and language embeddings we use size 50. All vectorizers were
trained on the large corpora presented earlier.

####  4.1.1. Baseline Experiments

We run the baseline experiments with the original data using 5-fold cross
validation. We show the performance (in terms of weighted F1 score) in the
Figures 5 & 6\. We show the baseline results as _orig_. For both the Bag-of-
Words (TF) and TFIDF, the MLP performs very well comparatively to the other
methods. In general the TFIDF performs better.

Figure 5: Baseline classification model performance for Setswana news title
categorisation

Figure 6: Baseline classification model performance for Sepedi news title
categorisation

####  4.1.2. Augmentation

We applied augmentation in different ways. First for Sepedi and Setswana word
embeddings (word2vec), we use word embedding-based augmentation. We augment
each dataset 20 times on the training data while the validation data is left
intact so as to be comparable to the earlier baselines. We show the effect of
augmentation in Figure 5 and 6 (performance labeled with _aug_

The contextual, word2vec based, word augmentation improves the performance of
most of the classifiers. If we now introduce a quality check using doc2vec
(Algorithm 1) we also notice the impact on the performance for Sepedi (Figure
6 _aug qual_ ). We were not able to complete experiments with Setswana for the
contextual augmentation with a quality check, but will continue working to
better under stand the impact of such an algorithm in general. For example, it
remains further work to investigate the effects of different similarity
thresholds for the algorithm on the overall performance, how such an algorithm
works on highly resourced languages vs low resourced languages, how we can
make the algorithm efficient etc.

Input: $s$: a sentence, $run$: maximum number of attempts at augmentation

Output: $\hat{s}$ a sentence with words replaced

1 def  _Augment(_s,run_)_:

2 Let $\vv{V}$ be a vocabulary;

3 for  _ $i$ in range(_run_) _ :

4 $w_{i}\leftarrow$ randomly select a word from $s$;

5 $\vv{w}\leftarrow$ find similar words of $w_{i}$;

6 $s_{0}\leftarrow$ randomly select a word from $\vv{w}$ given weights as
distance;

7 $\hat{s}\leftarrow$replace $w_{i}$ with similar word $s_{0}$;

8 $\vv{s}\leftarrow Doc2vec(s)$;

9 $\vv{\hat{s}}\leftarrow Doc2vec(\hat{s})$;

10 $similarity$ $\leftarrow$ Cosine Similarity($\vv{s}$, $\vv{\hat{s}}$);

11 if  _$similarity$ $>$ $threshold$_ :

12 return($\hat{s}$);

13

14

15

16

17

18

Algorithm 1 Contextual (Word2vec-based) augmentation algorithm with a doc2vec
quality check

Figure 7: Word2Vec feature based performance for news headline classification

Figure 8: Confusion Matrix of News headline classification models

It also interesting to look at how performance of classifiers that were only
trained with word2vec features would fair. Deep neural networks are not used
in this current work and as such we did not use recurrent neural networks, but
we can create sentence features from - word2vec by either using: the mean of
all word vectors in a sentence, the median of all word vectors in a sentence
or the concatenated power means [Rücklé et al., 2018]. We show the performance
of using this approach with the classifiers used for Bag of Words and TFIDF
earlier in Figure 8.

The performance for this approach is slightly worse with the best results for
Sepedi news headline classification being with XGBoost on the augmented data.
We hope to improve this performance using word2vec feature vectors using
recurrent neural networks but currently are of the view that increasing the
corpora sizes and the diversity of corpora for the pre-trained word embeddings
may yield even better results.

Finally, we show the confusion matrix of the best model in Sepedi on a test
set in Figure 8. The classifier categorises _General News_ , _Politics_ and
_Legal_ news headlines best. For the others there there is more error. A
larger news headline dataset is required and classification performance will
also need to be compared to models trained on full news data (with the article
body). For the Setswana classifiers, the confusion matrix shows that the data
skew results in models that mostly can categorise between categorises _General
News_ and _Other_. We need to look at re-sampling techniques to improve this
performance as well as increasing the initial dataset size.

##  5\. Conclusion and Future Work

This work introduced the collection and annotation of Setswana and Sepedi news
headline data. It remains a challenge that in South Africa, 9 of the 11
official languages have little data such as this that is available to
researchers in order to build downstream models that can be used in different
applications. Through this work we hope to provide an example of what may be
possible even when we have a limited annotated dataset. We exploit the
availability of other free text data in Setswana and Sepedi in order to build
pre-trained vectorisers for the languages (which are released as part of this
work) and then train classification models for news categories.

It remains future work to collect more local language news headlines and text
to train more models. We have identified other government news sources that
can be used. On training embedding models with the data we have collected,
further studies are needed to look at how augmentation using the embedding
models improve the quality of augmentation.

##  6\. Bibliographical References

## References

  * Bojanowski et al., 2017 Bojanowski, P., Grave, E., Joulin, A., and Mikolov, T.  (2017).  Enriching word vectors with subword information.  Transactions of the Association for Computational Linguistics, 5:135–146.
  * Bureau of Circulations, 2019 Bureau of Circulations, A.  (2019).  Newspaper circulation statistics for the period january–march 2019 (abc q1 2019).
  * Cubuk et al., 2019 Cubuk, E. D., Zoph, B., Mane, D., Vasudevan, V., and Le, Q. V.  (2019).  Autoaugment: Learning augmentation strategies from data.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 113–123.
  * Johnson et al., 2017 Johnson, M., Schuster, M., Le, Q. V., Krikun, M., Wu, Y., Chen, Z., Thorat, N., Viégas, F., Wattenberg, M., Corrado, G., et al.  (2017).  Google’s multilingual neural machine translation system: Enabling zero-shot translation.  Transactions of the Association for Computational Linguistics, 5:339–351.
  * Kobayashi, 2018 Kobayashi, S.  (2018).  Contextual augmentation: Data augmentation by words with paradigmatic relations.  In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), volume 2, pages 452–457.
  * Lewis, 1997 Lewis, D. D.  (1997).  Reuters-21578 text categorization collection data set.
  * Marivate and Sefara, 2019 Marivate, V. and Sefara, T.  (2019).  Improving short text classification through global augmentation methods.  arXiv preprint arXiv:1907.03752.
  * Marivate and Sefara, 2020a Marivate, V. and Sefara, T.  (2020a).  African embeddings [nlp].  https://doi.org/10.5281/zenodo.3668481, February.
  * Marivate and Sefara, 2020b Marivate, V. and Sefara, T.  (2020b).  South African news data dataset.  https://doi.org/10.5281/zenodo.3668489.
  * Mikolov et al., 2013 Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J.  (2013).  Distributed representations of words and phrases and their compositionality.  In Advances in neural information processing systems, pages 3111–3119.
  * Nettle, 1998 Nettle, D.  (1998).  Explaining global patterns of language diversity.  Journal of anthropological archaeology, 17(4):354–374.
  * Rücklé et al., 2018 Rücklé, A., Eger, S., Peyrard, M., and Gurevych, I.  (2018).  Concatenated power mean word embeddings as universal cross-lingual sentence representations.  arXiv preprint arXiv:1803.01400.
  * Sandhaus, 2008 Sandhaus, E.  (2008).  The new york times annotated corpus.  Linguistic Data Consortium, Philadelphia, 6(12):e26752.
  * Silfverberg et al., 2017 Silfverberg, M., Wiemerslage, A., Liu, L., and Mao, L. J.  (2017).  Data augmentation for morphological reinflection.  In Proceedings of the CoNLL SIGMORPHON 2017 Shared Task: Universal Morphological Reinflection, pages 90–99.
  * Strassel and Tracey, 2016 Strassel, S. and Tracey, J.  (2016).  Lorelei language packs: Data, tools, and resources for technology development in low resource languages.  In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16), pages 3273–3280.
  * Wang and Yang, 2015 Wang, W. Y. and Yang, D.  (2015).  That’s so annoying!!!: A lexical and frame-semantic embedding based data augmentation approach to automatic categorization of annoying behaviors using# petpeeve tweets.  In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 2557–2563.
  * Wei and Zou, 2019 Wei, J. and Zou, K.  (2019).  Eda: Easy data augmentation techniques for boosting performance on text classification tasks.  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 6383–6389.
  * Yu et al., 2019 Yu, S., Yang, J., Liu, D., Li, R., Zhang, Y., and Zhao, S.  (2019).  Hierarchical data augmentation and the application in text classification.  IEEE Access, 7:185476–185485.
  * Zhang et al., 2015 Zhang, X., Zhao, J., and LeCun, Y.  (2015).  Character-level convolutional networks for text classification.  In Advances in neural information processing systems, pages 649–657.
  * Zoph et al., 2016 Zoph, B., Yuret, D., May, J., and Knight, K.  (2016).  Transfer learning for low-resource neural machine translation.  arXiv preprint arXiv:1604.02201.