* Johansen et al. [2000] Johansen, A., Ledoit, O., Sornette, D., 2000.  Crashes as critical points.  International Journal of Theoretical and Applied Finance 3, 219–255.
  * Johansen and Sornette [2010] Johansen, A., Sornette, D., 2010\.  Shocks, crashes and bubbles in financial markets.  Brussels Economic Review (Cahiers economiques de Bruxelles) 53, 201–253.
  * Johansen et al. [1999] Johansen, A., Sornette, D., Ledoit, O., 1999.  Predicting financial crashes using discrete scale invariance.  Journal of Risk 1, 5–32.
  * Kaizoji [2006] Kaizoji, T., 2006.  A precursor of market crashes: Empirical laws of Japan’s internet bubble.  The European Physical Journal B-Condensed Matter and Complex Systems 50, 123–127.
  * Kaizoji et al. [2015] Kaizoji, T., Leiss, M., Saichev, A., Sornette, D., 2015\.  Super-exponential endogenous bubbles in an equilibrium model of fundamentalist and chartist traders.  Journal of Economic Behavior & Organization 112, 289–310.
  * Kesten [1973] Kesten, H., 1973.  Random difference equations and renewal theory for products of random matrices.  Acta Math. 131, 207–248.
  * Kocherlakota [1996] Kocherlakota, N.R., 1996.  The equity premium: It’s still a puzzle.  Journal of Economic Literature 34, 42–71.
  * Kullback and Leibler [1951] Kullback, S., Leibler, R.A., 1951\.  On information and sufficiency.  The annals of mathematical statistics 22, 79–86.
  * LeRoy and Porter [1981] LeRoy, S., Porter, R.D., 1981\.  The Present-Value Relation: Tests Based on Implied Variance Bounds.  Econometrica 49, 555–74.
  * Lin et al. [2014] Lin, L., Ren, R., Sornette, D., 2014.  The volatility-confined LPPL model: A consistent model of ”explosive” financial bubbles with mean-reversing residuals.  International Review of Financial Analysis 33, 210–?225.
  * Lin et al. [2019] Lin, L., Schatz, M., Sornette, D., 2019.  A simple mechanism for financial bubbles: time-?varying momentum horizon.  Quantitative Finance 19, 937–?959.
  * Lin and Sornette [2013] Lin, L., Sornette, D., 2013\.  Diagnostics of rational expectation financial bubbles with stochastic mean-reverting termination times.  The European Journal of Finance 19, 344–365.
  * Lin and Sornette [2018] Lin, L., Sornette, D., 2018\.  “Speculative Influence Network” during financial bubbles: application to Chinese stock markets.  Journal of Economic Interaction and Coordination 13, 385–431.
  * Lux and Sornette [2002] Lux, T., Sornette, D., 2002\.  On rational bubbles and fat tails.  Journal of Money, Credit and Banking 34, 589–610.
  * Lyons [2001] Lyons, R., 2001.  The Microstructure Approach to Exchange Rates.  The MIT Press.
  * Malevergne and Sornette [2001] Malevergne, Y., Sornette, D., 2001\.  Multi-dimensional rational bubbles and fat tails.  Quantitative Finance 1, 533–541.
  * Mehra and Prescott [1985] Mehra, R., Prescott, E.C., 1985\.  The equity premium: A puzzle.  Journal of Monetary Economics 15, 145–161.
  * Mehra and Prescott [2003] Mehra, R., Prescott, E.C., 2003\.  The equity premium in retrospect.  JFinancial Markets and Asset Pricing. Handbook of the Economics of Finance 1, 889–938.
  * Miller and Modigliani [1961] Miller, M.H., Modigliani, F., 1961\.  Dividend policy, growth, and the valuation of shares.  the Journal of Business 34, 411–433.
  * Modigliani and Miller [1958] Modigliani, F., Miller, M.H., 1958\.  The cost of capital, corporation finance and the theory of investment.  The American economic review 48, 261–297.
  * MSCI, Inc. [2010] MSCI, Inc., 2010.  Is there a link between gdp growth and equity returns?  Research Bulletin May 2010, MSCI Barra Research Paper No. 2010-18, Available at SSRN: https://ssrn.com/abstract=1707483 and https://www.msci.com/documents/10199/a134c5d5-dca0-420d-875d-06adb948f578 , 1–10.
  * Pardo [2018] Pardo, L., 2018.  Statistical inference based on divergence measures.  Chapman and Hall/CRC.
  * Phillips et al. [2011] Phillips, P.C.B., Wu, Y.R., Yu, J., 2011.  Explosive behavior in the 1990s Nasdaq: When did exuberance escalate asset values?  International Economic Review 52, 201–226.
  * Rathie and Kannappan [1972] Rathie, P.N., Kannappan, P., 1972\.  A directed-divergence function of type $\beta$.  Information and Control 20, 38–45.
  * Samuelson [2016] Samuelson, P.A., 2016.  Proof that properly anticipated prices fluctuate randomly, in: The world scientific handbook of futures markets. World Scientific, pp. 25–38.
  * Schatz and Sornette [2020] Schatz, M., Sornette, D., 2020\.  Inefficient bubbles and efficient drawdowns in financial markets.  International Journal of Theoretical and Applied Finance 23, 2050047 (56 pages).
  * Shiller [1981] Shiller, R.J., 1981.  Do stock prices move too much to be justified by subsequent changes in dividends?  American Economic Review 71, 421–436.
  * Shiller [1992] Shiller, R.J., 1992.  Market Volatility .
  * Sornette [2004] Sornette, D., 2004.  Critical Phenomena in Natural Sciences (Chaos, Fractals, Self-organization and Disorder: Concepts and Tools).  2n edition, Springer Series in Synergetics, Heidelberg.
  * Sornette [2017] Sornette, D., 2017.  Why stock markets crash: critical events in complex financial systems.  Princeton University Press.
  * Sornette and Andersen [2002] Sornette, D., Andersen, J.V., 2002\.  A nonlinear super-exponential rational model of speculative financial bubbles.  International Journal of Modern Physics C 13, 171–188.
  * Sornette and Cauwels [2015] Sornette, D., Cauwels, P., 2015\.  Financial bubbles: mechanisms and diagnostics.  Review of Behavioral Economics 2, 279–305.
  * Sornette et al. [2018] Sornette, D., Cauwels, P., Smilyanov, G., 2018.  Can we use volatility to diagnose financial bubbles? lessons from 40 historical bubbles.  Quantitative Finance and Economics 2, 1–105.
  * Sornette et al. [2015] Sornette, D., Demos, G., Zhang, Q., Cauwels, P., Filimonov, V., Zhang, Q., 2015\.  Real-time prediction and post-mortem analysis of the Shanghai 2015 stock market bubble and crash.  Journal of Investment Strategies 4, 77–95.
  * Sornette et al. [1996] Sornette, D., Johansen, A., Bouchaud, J.P., 1996.  Stock market crashes, precursors and replicas.  J.Phys. I France 6, 167–175.
  * Williams [1938] Williams, J., 1938.  The Theory of Investment Value.  Harvard University Press 1938; 1997 reprint, Fraser Publishing.
  * Witkovský [2001] Witkovský, V., 2001.  Computing the distribution of a linear combination of inverted gamma variables.  Kybernetika -Praha- 37, 79–90.


# Forecasting Busy-Hour Downlink Traffic in Cellular Networks

Andrea Pimpinella∗, Federico Di Giusto∗, Alessandro E. C. Redondi∗, Luisa
Venturini†, Andrea Pavon†
∗Dip. Elettronica, Informazione e Bioingegneria, Politecnico di Milano
†Vodafone Group, Network Engineering and Delivery
Email<EMAIL_ADDRESS>or<EMAIL_ADDRESS>
###### Abstract

The dramatic growth in cellular traffic volume requires cellular network
operators to develop strategies to carefully dimension and manage the
available network resources. Forecasting traffic volumes is a fundamental
building block for any proactive management strategy and is therefore of great
interest in such a context. Differently from what found in the literature,
where network traffic is generally predicted in the short-term, in this work
we tackle the problem of forecasting busy hour traffic, i.e., the time series
of observed daily maxima traffic volumes. We tackle specifically forecasting
in the long term (one, two months ahead) and we compare different approaches
for the task at hand, considering different forecasting algorithms as well as
relying or not on a cluster-based approach which first groups network cells
with similar busy hour traffic profiles and then fits per-cluster forecasting
models to predict the traffic loads. Results on a real cellular network
dataset show that busy hour traffic can be forecasted with errors below 10%
for look-ahead periods up to 2 months in the future. Moreover, when clusters
are available, we improve forecasting accuracy up to 8% and 5% for look-ahead
of 1 and 2 months, respectively.

###### Index Terms:

Mobile Data Analysis, Clustering, Traffic Forecasting, Traffic Peak Detection

##  I Introduction

In recent years cellular networks have witnessed a dramatic growth of traffic
volume, which is estimated to reach 226 EB per month in 2026. This is mainly
due to the prosperity of mobile subscriptions (which are expected to overcome
9 billions in 2026), the improved device capabilities and an increase of data-
intensive contents[1]. To cope with this situation, Mobile Network Operators
(MNOs) are gradually implementing efficient resource management strategies.
However, the increased complexity of mobile network dynamics has raised MNOs
awareness that the efficiency of network planning and dimensioning
interventions depends on how well mobile data traffic can be analysed,
understood and modeled especially in urban contexts.

A way MNOs have to implement proactive resources allocation strategies is to
design traffic load forecasting algorithms, with look-ahead horizons (i.e.,
how far in the future traffic is forecasted) which go from several hours to
several months[2, 3, 4, 5]. On the one hand, the development of powerful
hardware capable of dealing with the massive amount of data coming from
cellular networks have enabled the optimisation of traffic forecasting models.
On the other hand, making the network aware of traffic demands and capable of
pro-actively responding to traffic dynamics is yet a complex task.

At the same time, it has been shown [6, 7, 8] that there is a strong
relationship between users mobile communication activity and the
characteristics of the underlying urban area where such activity takes place.
The goal of grouping network sites according to the spatial and temporal
dynamics of the served traffic is typically addressed through the design of
clustering algorithms. From a spatial domain perspective, the knowledge of a
clustering configuration can be crucial for MNOs considering that traffic
loads are often characterised by geographic shifts between precise urban areas
during a day and during weekday-to-weekend transitions [6]. Considering the
time domain, the similarity of mobile traffic dynamics within a cluster can be
exploited to improve the accuracy of traffic modeling techniques and thus
discover regularities of traffic demand peaks.

In this paper we focus on forecasting traffic volumes starting from a real
dataset collected from the Vodafone mobile network of a middle-sized city in
northern Italy. Differently from related works, we consider as forecasting
target the time series of downlink traffic at the busy hour, i.e., the time
series of daily maxima traffic loads. We compare different forecasting
algorithms (time series decomposition, ARIMA and Long Short Term Memory
networks), also considering the possibility of clustering network cells prior
to computing forecasts. Results show that busy hour traffic can be forecasted
with errors below 10% for look-ahead periods up to 2 months in the future.
Moreover, when clusters are available, we improve forecasting accuracy up to
8% and 5% for look-ahead of 1 and 2 months, respectively.

The rest of this paper is structured as it follows: Section II summarises
related works about clustering and traffic forecasting in cellular networks,
while Section III describes the dataset available for this work and the
approach we follow to both sites clustering and forecasting. Section IV
comments the designed clustering configuration as well as the results obtained
from forecasting busy hour downlink traffic, when either clusters are unknown
or when the produced clustering configuration is available. Finally, Section V
concludes the paper.

##  II Related Works

Several works in the literature have analysed cellular networks traffic traces
to understand and model traffic patterns, especially in urban environments [6,
7] . In [6] a heterogeneous dataset containing mobile traffic of ten
international cities is investigated with the goal of i) summarising the
mobile traffic activity in each area and ii) grouping similar area signatures
into a limited representative set. In particular, leveraging the $k$-means
algorithm, the authors recognise five different area types, namely
residential, office, transportation, touristic and leisure. With similar aims,
in [7] authors consider a large-scale cellular network in Shangai (9K base
stations for a total of 3M users) and propose a model to cluster traffic
profiles with the goal of assisting MNOs in network planning operations.
Again, results show that 5 clusters are recognised which the authors label as
residential, transport, office, entertainment and comprehensive (the latter
grouping those base stations not associated to the other clusters). In many
cases, clustering models are used to improve the performance of traffic load
forecasting algorithms. In fact, a common approach to traffic forecasting is
first to cluster network sites with respect to weekly or monthly traffic
distribution (in space or time) and secondly fit a prediction model within
each cluster [7, 5, 4]. Authors in [7] show that clusters knowledge improve
the average forecasting accuracy up to 20% with respect to the case when no
clustering is available. This is also shown in [5], where authors leverage a
clustering algorithm to improve the performance of several forecasting
methods. After training the selected models i) on the cumulative traffic load
and ii) on each cluster’s cumulative load, results show that clusters
knowledge benefits the training process and improve the average accuracy by
25%. This comparison is also performed in [4], with similar conclusions:
forecasting performance improve when an ad-hoc model is developed per each
recognised cluster.

Differently from the aforementioned works, we consider as target the busy hour
traffic, with forecasting horizons larger than 1 month. This is of great
interest for MNOs, which often focus on the implementation of dimensioning and
resources allocation strategies in a pro-active rather than reactive fashion.

##  III Methodology

This work considers a dataset coming from Vodafone, one of the major European
mobile operators. The dataset contains radio access network measurements
relative to the period $T$={06/01/2020, 31/07/2020} and referring to about
1.500 eNodeBs of the Vodafone LTE network in the city of Milan, Italy. In
particular, for each eNodeB, we exploit the availability of several network
Key Performance Indicators (KPIs) (e.g., cumulative downloaded and uploaded
data volumes, n. of handovers, etc.) and the congestion level at the cell site
(e.g., n. of active connections, n. of PRBs used, etc.) in the form of hourly
sampled time series. In this work, we consider the cumulative traffic
downloaded at each cell site with a focus on the traffic served during the
busy hour, as detailed in the next Section.

###  III-A Definition of Busy Hour

Let $v^{e}(t)$ be the time series representing the hourly traffic volume
downloaded from the $e$-th eNodeB. The total hourly downlink traffic can be
written as:

$\displaystyle\mathbf{v}(t)=\sum_{e}\hskip 5.69054pt{v^{e}}(t)$ (1)

From this time series we build a new time series $\mathbf{v_{b}}(d)$
containing only daily busy hours samples, by picking, for each day $d$, the
traffic sample having the maximum value111Beside the considered traffic-based
definition of the busy hour, this can also be defined as the hour of the day
which maximizes the number of connected users. In this work we will not
consider this second option, as the downlink traffic sampled at the
corresponding busy hours is in our case always lower in volume than the one
sampled in the traffic-based busy hours..

Figure 1: Normalised cumulative downlink traffic time series (blue) and the
corresponding busy hour time series (red) for all the eNodeBs of the network,
on the whole period $\mathcal{T}$.

Figure 1 depicts the evolution of $\mathbf{v_{b}}(d)$ in the period of
interest, where traffic volumes have been normalised for privacy reasons. As
one can see, the time series is characterized by a slightly increasing trend
from January 2020 to March 2020 while the trend is decreasing from March 2020
onwards. Also, a strong weekly seasonality can be observed before $09/03/2020$
and after $01/06/2020$, while traffic patterns appear unregular between these
two dates222In Italy, full lockdown has been established between $09/03/2020$
and $01/06/2020$ due to COVID-19 pandemic..

###  III-B Forecasting Methods

Considering the interest of MNOs in predicting when the next peak of traffic
demand will occur, in this work we focus on the forecast of $\mathbf{v_{b}}$.
We compare the performance of three different forecasting methods:

  * •

Additive Time Series Decomposition (AD): we assume $\mathbf{v_{b}}$ to equal
the sum of three independent components:

$\mathbf{v_{b}}=S+T+E$ (2)

where $S$, $T$ and $E$ are the Seasonal, Trend and Noise components,
respectively. While $E$ is by nature not predictable, $S$ and $T$ can be
independently forecasted through a traditional naïve decomposition model and
the concatenation of a STL333The acronym stands for Seasonal and Trend
decomposition using Loess, a model used for time series decomposition.
decomposition model and a non-seasonal ARIMA[9], respectively. Note that this
procedure requires in input the expected periodicity $\tau$ of the time
series, which can be retrieved observing the time plot of the data.

  * •

Seasonal ARIMA (SA): a well-known approach for stationary seasonal time series
forecasting is to model the forecast target as the combination of two
independent ARIMA models, one for the non-seasonal part of the time series and
the other one for the seasonal part. The combined model is denoted as
ARIMA$(p,d,q)\times(P,D,Q)_{S}$ where $(p,d,q)$ are the AR, Integration and MA
order of the non-seasonal part while $(P,D,Q)$ are the corresponding seasonal
versions, being $S$ the period of the repeating seasonal pattern [10]. A
crucial step for modelling a time series through ARIMA is to estimate the
different orders which characterise the model: we will detail this aspect
later in Section IV-1.

  * •

Long Short-Term Memory (LSTM): another way to forecast time series is to
assume a more complex, non linear relationship between data samples and learn
it by means of Recurrent Neural Networks (RNNs)[11, 10]. LSTM structures are
characterized by the concatenation of $h$ hidden layers, where each layer is
formed by $n_{h}$ cells. A common approach is to concatenate at the end of the
LSTM structure $k$ fully connected hidden layers (with $m_{k}$ neurons each)
and a final layer (with $O$ output units) to output the forecasted
samples[10]. Note that the size $O$ of the output layer represents the look-
ahead forecast horizon, i.e., how far in the future the network is able to
forecast. Details on the tuning of these hyper-parameters are given in Section
IV-1.

###  III-C Clustering Procedure

The forecasting methodologies presented before can be applied directly on the
aggregate busy hour time series $\mathbf{v_{b}}$ to perform prediction. An
alternative approach is to cluster together eNodeBs having similar busy-hour
traffic behaviour, perform forecasts for each cluster and finally sum the
obtained prediction together. We refer to the former approach as Cluster-
Unaware (CU), while the latter is named Cluster-Aware (CA).

The Cluster-Aware approach relies on $k$-means clustering, grouping together
eNodeBs based on the Euclidean distance among their Median Weekly Signatures
(MWS). In details, the MDS of an eNodeB is computed as it follows:

  * •

First, we compute the Median Daily Signature (MDS) for work days (Mondays to
Fridays), Saturdays and Sundays. In a nutshell, the MDS for week days is
computed hourly by taking the median of the downlink traffic observed at each
hour for each day in the dataset. The same is repeated independently for
Saturdays and Sundays.

  * •

Then, we compute the MWS by stacking five copies of the work days MDS plus the
MDS for Saturdays and Sundays. As an example, we plot in Figure 2 the
(normalised) MWS of one eNodeB taken as example: as one can see, the traffic
pattern is the same from Monday to Friday whereas the pattern changes during
the week end.

Figure 2: Normalised MWS for one eNodeB of example: working day MDS is
repeated from Monday to Friday while Saturday and Sunday have different MDS.

Repeating this process for each eNodeB in the network allows to perform
$k$-means clustering with the MWS as input. Note that each MWS is normalised
before being used, as our interest is to group eNodeBs regardless of the
amplitude of the observed download traffic. Also, considering that the first
COVID-19 infection case was registered in Italy on 15/02/2020, to avoid
biasing errors due to the extraordinary traffic behaviour that has been
observed afterwards, we compute the MWSs considering only the 4-weeks season
observed in January 2020.

There is no a-priori knowledge about the number of clusters $k$ to use:
therefore, we take a data driven approach which consists in a grid search over
the set of candidate values $k=[1,\dots,10]$. For each candidate value, we
perform clustering and compute for each eNodeB the corresponding Silhouette
coefficient [12]. The higher the coefficient of a signature, the better it
matches its own cluster, such that a clustering configuration is appropriate
if most of the signatures have a high Silhouette value. At the end of this
process, we set $k=5$, which is also the most likely choice for urban
scenarios [6, 7]. We plot in Figures 7-7 the centroids of the recognised
clusters, i.e., the representatives of the MWSs of the eNodebs of each
cluster. The MWS shown in Figure 7 is characterized by two traffic peaks
during Week Days, one weaker peak in the morning between 8:00 a.m. and 9:00
a.m and a second sharper peak in the evening between 9:00 p.m. and 10:00 p.m.,
whereas during Saturday and Sunday only the evening peak survives. In fact,
this cluster (which we label as $\mathcal{R}_{1}$) is associated to
residential areas of the considered city, where traffic demand is uniform in
time but lower loads are observed during working hours. Similar observations
can be made if we look at the centroid represented in Figure 7
($\mathcal{R}_{2}$), a secondary residential cluster where morning and evening
peaks are less evident during Week Days whereas Saturday and Sunday profiles
are close to those observed in 7. A different behaviour is instead shown in
Figure 7, where traffic is heavier during working hours in Week Days while it
is consistently lower in volume otherwise. We therefore associate this cluster
($\mathcal{B}$) to the business areas with a typical European working time
during Week Days from 9:00 a.m. to 6:00 p.m. A further different trace is
depicted in Figure 7, which represents the cluster associated to transport
hubs and transportation network in the city ($\mathcal{T}$). In fact, the
eNodeBs of this cluster are characterised by high traffic demands during
commuting rush hours in the Week Days (i.e., at 8:00 a.m. and 6:00 p.m.) while
very weak traffic activity is observed in the week end.

TABLE I: Distribution of clustered eNodeBs and per-cluster cumulative served traffic demand. Type | Size (%) | Served Traffic (%)
---|---|---
$\mathcal{R}_{1}$ | 37.1 | 48.6
$\mathcal{R}_{2}$ | 30.2 | 29.1
$\mathcal{B}$ | 20.6 | 13.9
$\mathcal{T}$ | 7.8 | 8.3
$\mathcal{U}$ | 4.4 | 0.1

We summarise in Table I the fraction of eNodeBs of the network grouped in each
cluster and the corresponding served traffic demand. As one can see, more than
65% of the eNodeBs are deployed in residential areas and generate more than
75% of the mobile traffic. Next most serving cluster is those active in
business areas, which groups 20% of the eNodeBs for a total served demand of
14%, while Transport cluster contains sligthly less than 8% of the eNodeBs
which overall serve sligthly more than 8% of the traffic demand. Finally, we
observe that a small group of eNodeBs (4.4%) is represented by a MWS which
resembles a noisy process (depicted in Figure 7 and referred to as
$\mathcal{U}$) and is associated with a negligible portion (0.1 %) of the
overall generated traffic.

##  IV Forecasting Results

Figure 3: Centroid representative of $\mathcal{R}_{1}$ cluster.

Figure 4: Centroid representative of $\mathcal{R}_{2}$ cluster.

Figure 5: Centroid representative of $\mathcal{B}$ cluster.

Figure 6: Centroid representative of $\mathcal{T}$ cluster.

Figure 7: Centroid representative of $\mathcal{U}$ cluster.

In this Section, we comment on the tuning of AD, SA and LSTM and on the
corresponding performance when they are applied to forecast $\mathbf{v_{b}}$.
On the one hand, each model will have a look-back window of 2-weeks (i.e.,
will take in input 14 past daily samples of $\mathbf{v_{b}}$). This choice
comes after a grid search tuning and represents a good compromise between size
of the training data and freshness of the information. On the other hand, we
set the models basic look-ahead horizon to 7 days, such that if predictions
further than 1 week ahead are targeted the models will recursively use
forecasted samples as input for further iterations (i.e., to feed the look
back window of 14 samples when ground truth data are not available). Note that
both training and test data are first transformed through a box-cox
normalisation before feeding the forecasting models, as it is commonly done in
the field of time series forecasting for variance stabilisation purposes [9].

####  IV-1 Model Tuning

The selected models require the tuning of several parameters. For what regards
AD, considering that $\mathbf{v_{b}}$ is characterised by a weekly
seasonality, we set the periodicity $\tau$ equal to 7 days. For what regards
SA, after the inspection of the Auto-Correlation and the Partial Auto-
Correlation Functions (ACF and PACF respectively) of $\mathbf{v_{b}}$, we
select a model of type $(1,1,0)\times(1,1,0)_{7}$. This is because: i) the
cascade of two differencing operations of orders $d=1$ and $D=1$ returns a
stationary time series, ii) the seasonality of $\mathbf{v_{b}}$ has a period
of $S=7$ days, iii) the presence of a sharp correlation peak at lag=1 in the
PACF suggests the autoregressive orders are $p=1$ and $P=1$ and iv) the
presence of several modest correlation peaks in the ACF suggests that moving
average processes should be excluded from the model (i.e., $q=0$ and $Q=0$).
Finally, considering the LSTM model, we manually design a encoder-decoder
based network structure composed by: i) a couple of encoder-decoder layers of
$n_{1}=n_{2}=200$ cells; ii) a bi-dimensional fully connected layer
characterised by $k=7$ parallel hidden layers of $m_{1}=\dots=m_{7}=100$
neurons each; iii) an output layer of size $O=7$. Cells and neurons of the
network are activated through ReLu activation functions, while MSE is chosen
as loss metric.

####  IV-2 Performance

To compare the forecasting performance of the selected methods, we retain the
period $T\textsubscript{train}=\\{06/01/2020,31/05/2020\\}$ for training,
while the period $T\textsubscript{test}=\\{01/06/2020,31/07/2020\\}$ is left
aside for testing. The performance are evaluated in terms of Mean Absolute
Percentage Error (MAPE) and Mean Percentage Error on Peak (MPEP), which are
defined as it follows:

$\displaystyle{\rm MAPE}=\frac{100\%}{n}\sum_{t\in
T\textsubscript{test}}\left|\frac{v_{b}(t)-\hat{v_{b}}(t)}{v_{b}(t)}\right|$
$\displaystyle{\rm MPE\textsubscript{P}}=100\%\frac{\max\limits_{t\in
T\textsubscript{test}}v_{b}(t)-\max\limits_{t\in
T\textsubscript{test}}\hat{v_{b}}(t)}{\max\limits_{t\in
T\textsubscript{test}}v_{b}(t)}$

where $\hat{\mathbf{v_{b}}}$ denotes the forecasted time series. Note that
MPEP measures the capability of a model to predict the maximum value of the
forecast target, which is a crucial information when the model is used by a
MNO for dimensioning purposes. To study the impact of both the training period
length (which we refer to as $TL$) and the look-ahead horizon (namely, $LA$)
on the forecasting performance, we compare the results varying $TL$ in [1, 2,
$\dots$, 5] and $LA$ in [1, 2] months.

Figure 8: MAPE, CU: TL vs LA.

Figure 9: MAPE, CA: TL vs LA.

As said before, to produce $\hat{\mathbf{v_{b}}}$ we consider two different
approaches, Clustering Unaware (CU) and Clustering Aware (CA) respectively.
According to the former approach, we train each forecasting model on
$\mathbf{v_{b}}$ as defined in Section III-A. Differently, according to the
latter approach we proceed as it follows:

  1. 1.

We fix the timestamps $\mathbf{t_{b}}$ from the vector of busy hours traffic
samples $\mathbf{v_{b}}$;

  2. 2.

Considering the set of clusters
$\mathcal{C}=[\mathcal{R}_{1},\mathcal{R}_{2},\mathcal{B},\mathcal{T}]$, we
compute the busy-hour per-cluster cumulative downlink traffic
$\mathbf{v^{c}_{b}}$ in $t^{d}_{b}\in\mathbf{t_{b}}$ for each day $d\in
T\textsubscript{train}$, for $c\in\mathcal{C}$. This generates 4 different
time series, namely:
$\mathbf{v^{\mathcal{R}_{1}}_{b}},\mathbf{v^{\mathcal{R}_{2}}_{b}},\mathbf{v^{\mathcal{B}}_{b}},\mathbf{v^{\mathcal{T}}_{b}}$;

  3. 3.

We train the forecasting models on each of the four newly defined time series,
independently;

  4. 4.

We compute $\hat{\mathbf{v_{b}}}$ as:

$\displaystyle\hat{\mathbf{v_{b}}}=\sum_{c\in\mathcal{C}}\hskip
5.69054pt{\hat{\mathbf{v^{c}_{b}}}}.$ (3)

TABLE II: MAPEs obtained for a 1-month look-ahead and TL$\leq$2. LA=1 | CU | CA
---|---|---
Model TL | 1 | 2 | 1 | 2
AD | 5.55 | 7.92 | 5.27 | 7.82
SA | 3.90 | 3.90 | 3.60 | 4.85
LSTM | 4.87 | 7.32 | 8.00 | 7.85
TABLE III: MAPEs obtained for a 2-months look-ahead and TL$\leq$2. LA=2 | CU | CA
---|---|---
Model TL | 1 | 2 | 1 | 2
AD | 4.97 | 8.10 | 4.72 | 7.65
SA | 4.88 | 4.87 | 5.46 | 4.66
LSTM | 4.95 | 7.76 | 8.5 | 7.84

We plot in Figures 8 and 9 the MAPEs obtained when either CU or CA approach is
adopted, respectively. On the one hand, considering Figure 8, for both LA=1
(left) and LA=2 (right) errors are below 10% and the best performing model is
SA. In particular, when SA predicts one month in advance the errors are below
5%, with the best performance of 3.90% obtained for a TL$\leq$2 months.
Differently, when LA=2, SA performs at par for different training period
lengths, with an average MAPE of 4.70%. Performance decrease at least by 20%
when either AD or LSTM are used, with the only exception of the case
(TL=1,LA=2) where their MAPEs are comparable to the one yielded by SA. On the
other hand, when the knowledge about the clusters configuration is included in
the forecasting process (Figure 9), SA model confirms to be the best
performing for both LA=1 and LA=2. In particular, best MAPE of 3.60% is
observed when SA is used with TL=1 and LA=1. Good results are also observed
when TL=2 for both L=1 and L=2, where SA yields a MAPE of 4.85% and 4.66%
respectively. Viceversa, when TL$\geq$2 SA deteriorates its performance and
yields results which are comparable to the ones of the other forecasting
methods (with errors above 7%). To compare the performance of the two
forecasting approaches, we report in Tables II and III the MAPEs obtained when
TL$\leq$2 for LA=1 and LA=2, respectively. As one can see in Table II, CA
approach improves by 8% the best performance obtained when clusters are not
computed. Fixing the training period, we also observe a performance
improvement of 5.5% when AD model is used, while forecasting errors increase
when clusters are available if LSTM is used (regardless of TL). Similar
conclusions can be drawn if we consider a look ahead of 2 months (as shown in
Table III), where CA approach improves by 5% the best performance obtained
with CU approach (for TL=2). Regardless of the approach and the look-ahead
capability, we observe a decreasing trend in forecasting performance with the
increasing of TL, for all the tested methodologies. This is due to the
particular characteristics of the period under study, as users network usage
(and thus cellular traffic behaviour) has been rapidly changing during
COVID-19 pandemic breakout. This suggests that in such cases it is preferable
to frequently update traffic forecasting models to capture more recent
variations in traffic and discard older data patterns.

Figure 10: MPE, CU: TL vs LA.

To conclude, we plot in Figures 10 and 11 the forecasting performance with
respect to the maximum busy hour downlink traffic value observed in the test
period, for CU and CA approach respectively. Regardless of the forecasting
approach, we observe that: i) errors are positive in sign, meaning that our
models under-estimate the overall network traffic peak; ii) peak detection
performance improve on average of 50% when LA=1 with respect to LA=2. On the
one hand, when LA=1, the best MPEP (7.4%) is achieved by LSTM model for TL=1
when CU approach is adopted (11% better than CA approach). On the other hand,
when LA=2 traffic peaks are better detected (MPEP=11.88%) when CA approach is
implemented (7% better than CU approach) and SA model is used with TL=1.

Figure 11: MPE, CA: TL vs LA.

##  V Conclusions

Traffic forecasting is an important tool for MNOs to anticipate the knowledge
of traffic demand peaks and thus enhance the efficiency of network
dimensioning and planning operations. In this paper, we consider as target the
busy hour downlink traffic and we compare the performance of different
forecasting methods when either no network sites clustering is performed
before training the models or a clustering configuration is designed and
leveraged during the training phase. Beside the insights which the knowledge
of a clustering configuration provides with respect to mobile users activity
in a cellular network, our results show that it also benefits the forecasting
performance, improving the accuracy by more than 5% up to a forecasting
horizon of 2 months. To conclude, we recall that the data used in this study
refers to the period January-July 2020 in the country of Italy. Considering
that since March the 9th Italy was in lock-down due to Covid-19 pandemic, part
of the data refer to an extraordinary behaviour of the mobile network. In
particular, the decreasing trend of downlink traffic is due to the reduced
mobility of the users in such period: we plan to perform new experiments once
the pandemic is over.

## References

  * [1] “Ericsson mobility report,” https://www.ericsson.com/en/mobility-report/reports/november-2020, 2020\.
  * [2] H. D. Trinh, L. Giupponi, and P. Dini, “Mobile traffic prediction from raw data using lstm networks,” in _2018 IEEE 29th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)_. IEEE, 2018, pp. 1827–1832.
  * [3] C. Zhang and P. Patras, “Long-term mobile traffic forecasting using deep spatio-temporal neural networks,” in _Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing_ , 2018, pp. 231–240.
  * [4] L.-V. Le, D. Sinh, B.-S. P. Lin, and L.-P. Tung, “Applying big data, machine learning, and sdn/nfv to 5g traffic clustering, forecasting, and management,” in _2018 4th IEEE Conference on Network Softwarization and Workshops (NetSoft)_. IEEE, 2018, pp. 168–176.
  * [5] B. Mahdy, H. Abbas, H. S. Hassanein, A. Noureldin, and H. Abou-zeid, “A clustering-driven approach to predict the traffic load of mobile networks for the analysis of base stations deployment,” _Journal of Sensor and Actuator Networks_ , vol. 9, no. 4, p. 53, 2020.
  * [6] A. Furno, M. Fiore, R. Stanica, C. Ziemlicki, and Z. Smoreda, “A tale of ten cities: Characterizing signatures of mobile traffic in urban areas,” _IEEE Transactions on Mobile Computing_ , vol. 16, no. 10, pp. 2682–2696, 2016.
  * [7] H. Shi and Y. Li, “Discovering periodic patterns for large scale mobile traffic data: Method and applications,” _IEEE Transactions on Mobile Computing_ , vol. 17, no. 10, pp. 2266–2278, 2018.
  * [8] F. Xu, Y. Lin, J. Huang, D. Wu, H. Shi, J. Song, and Y. Li, “Big data driven mobile traffic understanding and forecasting: A time series approach,” _IEEE transactions on services computing_ , vol. 9, no. 5, pp. 796–805, 2016\.
  * [9] R. J. Hyndman and G. Athanasopoulos, _Forecasting: principles and practice_. OTexts, 2018.
  * [10] S. Siami-Namini, N. Tavakoli, and A. S. Namin, “A comparison of arima and lstm in forecasting time series,” in _2018 17th IEEE International Conference on Machine Learning and Applications (ICMLA)_. IEEE, 2018, pp. 1394–1401.
  * [11] J. Schmidhuber, “Deep learning in neural networks: An overview,” _Neural networks_ , vol. 61, pp. 85–117, 2015.
  * [12] P. Berkhin, “A survey of clustering data mining techniques,” in _Grouping multidimensional data_. Springer, 2006, pp. 25–71.


# Minimal Posets with Prescribed Maximal Chain Cardinalities

Todd Bichoupan

(Date: May 26, 2023)

###### Abstract.

Given a nonempty finite multiset $S$ of positive integers, we wish to find a
partially ordered set $P$ of minimal cardinality such that the multiset of
cardinalities of all maximal chains in $P$ equals $S$. This paper establishes
upper and lower bounds on the size of $P$:
$\max(S)+\lceil\log_{2}|S|\rceil<=|P|<=\max(S)+|S|-1$, and both bounds are
tight.

##  1\. Background

A _partial order_ $\leq$ on a set $P$ is a binary relation that satisfies the
following three conditions for all $x,y,z\in P$:

  * •

Reflexivity: $x\leq x$

  * •

Antisymmetry: $x\leq y\land y\leq x\implies x=y$

  * •

Transitivity: $x\leq y\land y\leq z\implies x\leq z$

A set equipped with a partial order is called a _partially ordered set_ , or
_poset_ for short. As a convention, $x<y$ for $x,y\in P$ if $x\leq y$ and
$x\neq y$. For any subset $S$ of $P$, the relation $\leq$ is still a valid
partial order when it is restricted to the elements of $S$, and the poset
$(S,\leq)$ is called a _suborder_ of $(P,\leq)$.

Every poset $(P,\leq)$ has an associated covering relation, $\prec$. For
$x,y\in P$, $x\prec y$ if $x<y$ and there is no $z\in P$ such that $x<z$ and
$z<y$. When $P$ is finite, the partial order can be recovered from the
covering relation: $x\leq y$ if there is sequence $\\{a_{i}\\}_{i=0}^{n}$ of
members of $P$ such that $a_{0}=x,a_{n}=y$, and $a_{i}\prec a_{i+1}$ for all
$i<n$. When $P$ is finite, it can be visualized with a _Hasse diagram_ , which
is drawn by arranging the elements of $P$ so that $y$ is above $x$ whenever
$x<y$, and $x$ is connected to $y$ if $x\prec y$.

A covering relation on a poset $(P,\leq)$ forms a simple directed graph on the
members of $P$. Moreover, a simple directed graph is the covering relation
associated with some partial order if and only if the graph is acyclic and
every edge is the unique path connecting its endpoints (that is, if an edge
connects a vertex $x$ to a vertex $y$, then there is no other path from $x$ to
$y$).

For a poset $(P,\leq)$, elements $x,y\in P$ are _comparable_ if $x\leq y$ or
$y\leq x$. A set $C\subseteq P$ is a _chain_ if all the elements of $C$ are
comparable to one another. A chain $C$ in $P$ is _maximal_ if no other chain
in $P$ is a proper superset of $C$.

For a finite poset $(P,\leq)$, chains and maximal chains can also be defined
in terms of the covering relation. A nonempty finite set $C\subseteq P$ is a
chain if and only if the elements of $C$ can be ordered in a sequence
$\\{a_{i}\\}_{i=0}^{n}$ where $a_{i}\prec a_{i+1}$ for all $i<n$, and $C$ is
maximal if and only if $a_{0}$ is a minimal element of $P$ and $a_{n}$ is a
maximal element of $P$. In other words, a chain is a path in the directed
graph associated with the covering relation, and a chain is maximal if the
path cannot be extended by adding an element to either end.

##  2\. Counting Chains with Matrices

Let $(P,\leq)$ be a nonempty finite poset. Let $n=|P|$ and index the elements
of $P$ with the nonnegative integers less than $n$, so
$P=\\{p_{i}\\}_{i=0}^{n-1}$. The _adjacency matrix_ associated with the
covering relation on $(P,\leq)$ is the $n$-by-$n$ matrix $A$ where $A_{ij}=1$
if $p_{i}\prec p_{j}$ and $A_{ij}=0$ otherwise. It is well known that one can
efficiently calculate the number of paths between two vertices of a graph by
taking powers of the corresponding adjacency matrix. In particular, for any
nonnegative integer $k$, entry $(i,j)$ of $A^{k}$ is the number of chains
$C\subseteq P$ such that $p_{i}$ is the minimum element of $C$, $p_{j}$ is the
maximum element of $C$, and $|C|=k+1$ ($A^{0}$ is the identity matrix by
convention). By summing all the entries $(i,j)$ of $A^{k}$ where $p_{i}$ is a
minimal element of $P$ and $p_{j}$ is a maximal element of $P$, one obtains
the total number of maximal chains of $P$ that have cardinality $k+1$. It is
worth noting that since the graph associated with $A$ is acyclic, $A^{k}$ is
only nonzero for $k<n$.

##  3\. Problem Statement

Given a nonempty finite poset $(P,\leq)$, the previous section shows how one
can obtain the multiset $S$ of cardinalities of maximal chains in $P$. We are
interested in the opposite problem: we are given a nonempty finite multiset
$S$ of positive integers, and we are looking for a poset $(P,\leq)$ such that
the multiset of maximal chain cardinalities equals $S$; furthermore, we want
to find a poset $(P,\leq)$ that minimizes $|P|$ while satisfying the
constraint on its maximal chain cardinalities.

##  4\. Trivial Bounds

Suppose $S$ is a nonempty finite multiset of positive integers. Let $m$ be the
maximum element of $S$ and let $n$ be the cardinality of $S$ (counting
multiplicities). If $(P,\leq)$ is a poset whose multiset of maximal chain
cardinalities equals $S$, then $|P|\geq m$, since $P$ must contain a chain of
size $m$. On the other hand, it is always possible to construct a poset
$(P,\leq)$ where $|P|=m+n-1$ and the multiset of maximal chain cardinalities
equals $S$.

Let $S^{\prime}=S\setminus\\{m\\}$ (so the multiplicity of $m$ in $S$ minus
the multiplicity of $m$ in $S^{\prime}$ equals one). Suppose $P$ has an
element $x_{i}$ for each positive integer $i$ less that or equal to $m$, and
suppose $P$ has an element $s_{jk}$ for each distinct element $j\in
S^{\prime}$ and each positive integer $k$ less that or equal to the
multiplicity of $j$ in $S^{\prime}$. So $|P|=m+n-1$, and if the partial order
on $P$ is defined so that $x_{i}<x_{j}$ and $x_{i}<s_{jk}$ when $i<j$, then
the associated multiset of maximal chain cardinalities equals $S$. Figure 1
shows the Hasse diagram for the poset given by this construction if
$S=\\{2,3,3,5,5\\}$.

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$s_{21}$$s_{31}$$s_{32}$$s_{51}$

Figure 1.  A poset with maximal chain cardinalities $\\{2,3,3,5,5\\}$.

##  5\. The Lower Bound

The following theorem shows that the lower bound from Section 4 can be
improved.

######  Theorem 1.

Let $(P,\leq)$ be a finite poset and let $S$ be the multiset of all
cardinalities of maximal chains in $P$. Let $m$ be the maximum element of $S$
and let $n=|S|$ (counting multiplicities). Then $|P|\geq m+\log_{2}(n)$.

###### Proof.

Let $k=|P|-m$. Since $P$ must contain a maximal chain of cardinality $m$, the
elements of $P$ can be partitioned into sets $M$ and $X$ such that $M$ is a
maximal chain of $m$ elements and $X$ contains the remaining $k$ elements. Let
$C$ be a maximal chain in $P$. Since $C\cap X$ is a subset of $X$, there are
at most $2^{k}$ possible values of $C\cap X$.

The critical idea is that we can determine which elements of $M$ are in $C$ if
we only know which elements of $X$ are in $C$. By the pigeonhole principle,
this will imply that there are at most $2^{k}$ possible maximal chains $C$ in
$P$, which implies that there are at most $2^{k}$ different numbers in $S$. So
$2^{k}\geq n$, or equivalently, $k\geq\log_{2}(n)$.

Let $A=C\cap X$. If an element $y\in M$ is a member of $C$, then $y$ is
comparable to every element of $A$. So if $B$ is the set of all $y\in M$ such
that $y$ is comparable to all elements of $A$, then $B\supseteq C\cap M$.
Furthermore, the set $A\cup B$ is a chain: every pair of elements in $A$ is
comparable because $A\subseteq C$, every pair of elements in $B$ is comparable
because $B\subseteq M$, and every element of $A$ is comparable to every
element of $B$ by the definition of $B$. But if $A\cup B$ is a chain where
$A\cup B\supseteq C$, then $A\cup B=C$ by the maximality of $C$. It follows
that $C\cap M=B$. ∎

The following theorem shows that the lower bound given in Theorem 1 is sharp.

######  Theorem 2.

Let $k$ be a positive integer, and let $I$ be the set of all positive integers
less than or equal to $k$. For each $i\in I$, let $a_{i}$ be a nonnegative
integer. Let $A$ be the multiset $\\{a_{i}:i\in I\\}$. Let $\textup{sums}(A)$
be the multiset $\\{\Sigma_{i\in J}a_{i}:J\subseteq I\\}$ (so
$|\textup{sums}(A)|=2^{k}$). If $S$ is the multiset
$\\{k+x:x\in\textup{sums}(A)\\}$, $n=|S|=2^{k}$, and
$m=\max(S)=k+\Sigma_{i=1}^{k}a_{i}$, then there is a poset of cardinality
$m+\log_{2}(n)=2k+\Sigma_{i=1}^{k}a_{i}$ whose multiset of maximal chain
cardinalities equals $S$.

###### Proof.

We give a method to construct the required poset.

In [1, Section 1.6], Grätzer defines the _ordinal sum_ as an associative
binary operation on posets: for posets $(P_{1},\leq_{1})$ and
$(P_{2},\leq_{2})$, the ordinal sum $(P_{1},\leq_{1})+(P_{2},\leq_{2})$ is a
poset on $P_{1}\cup P_{2}$ that preserves the order of elements within $P_{1}$
and $P_{2}$ and places all elements of $P_{1}$ below all elements of $P_{2}$.

For each $i\in I$, let $(P_{i},\leq_{i})$ be a poset containing a chain of
size $a_{i}+1$ and a single additional element not comparable to any element
of the chain. If $(P,\leq)=\Sigma_{i=1}^{k}(P_{i},\leq_{i})$, then the
multiset of cardinalities of maximal chains in $P$ equals $S$, and
$|P|=\Sigma_{i=1}^{k}|P_{i}|=\Sigma_{i=1}^{k}(a_{i}+2)=m+\log_{2}(n)$. ∎

Figure 2.  A minimal poset whose multiset of maximal chain cardinalities is
$\\{3,4,5,6,7,8,9,10\\}=3+\textup{sums}(\\{1,2,4\\})$. Each color represents
one of the posets in the ordinal sum.

##  6\. The Upper Bound

The purpose of this section is to show that the upper bound from Section 4 is
sharp.

An element $x$ of a poset $(P,\leq)$ is a _splitting element_ of $P$ if there
is more than one maximal chain in the suborder of all elements of $P$ less
than or equal to $x$ and there is more than one maximal chain in the suborder
of all elements of $P$ greater than or equal to $x$. Equivalently, for a
finite poset $(P,\leq)$, an element $x\in P$ is splitting if the graph of the
covering relation associated with $(P,\leq)$ contains more than one path from
a minimal element of $P$ to $x$ and contains more than one path from $x$ to a
maximal element of $P$.

Suppose $(P,\leq)$ is a poset and $A$ is a subset of $P$. An _in-edge_ of $A$
is a pair of elements $x\in A$, $y\in P\setminus A$ where $y\prec x$. An _out-
edge_ of $A$ is a pair of elements $x\in A$, $y\in P\setminus A$ where $x\prec
y$. In other words, in-edges of $A$ are edges in the graph of the covering
relation associated with $(P,\leq)$ that point from an element outside of $A$
to an element in $A$, and likewise, out-edges of $A$ are edges pointing from
an element in $A$ to an element outside of $A$.

Suppose that $(P,\leq)$ is a poset, $m$ is a positive integer, and
$C=\\{c_{i}\\}_{i=1}^{m}$ is a chain in $P$ where $c_{i}\leq c_{j}$ when
$i\leq j$. The _index_ of an in-edge of $C$ with endpoint $c_{i}$ is $i$, and
the index of an out-edge of $C$ with endpoint $c_{j}$ is $j$.

The following theorem shows that the upper bound from Section 4 is sharp when
the given maximal chain cardinalities are sparse.

######  Theorem 3.

Let $S$ be a nonempty finite multiset of positive integers, let $n=|S|$, and
let $m=\max(S)$. Suppose that $S$ has no element with multiplicity greater
than one and that for all $a,b,c\in S$ with $a<b<c$,
$(m-a)\geq(m-b)+(m-c)+n-3$. Then if $(P,\leq)$ is a finite poset where the
multiset of all cardinalities of maximal chains in $P$ equals $S$, $|P|\geq
m+n-1$.

###### Proof.

If $n\leq 3$, then $m+n+1=m+\lceil\log_{2}(n)\rceil$, and the result follows
from Theorem 1. So we may assume that $n\geq 4$.

Assume for the sake of contradiction that $P$ has a splitting element, $x$.
Then there are distinct maximal chains of sizes $e$ and $f$ in the suborder of
elements below $x$, and there are distinct maximal chains of sizes $g$ and $h$
in the suborder of elements above $x$. So $P$ has maximal chains of sizes
$e+g-1$, $e+h-1$, $f+g-1$, and $f+h-1$; since
$(e+g-1)+(f+h-1)=(e+h-1)+(f+g-1)$, this implies that $S$ contains four
distinct elements $a$, $b$, $c$, and $d$ with $a+d=b+c$. Assume without loss
of generality that $a$ is smaller than $b$, $c$, and $d$. Then
$(m-a)=(m-b)+(m-c)-(m-d)<(m-b)+(m-c)+1$, which contradicts the condition of
the theorem when $n\geq 4$.

Let $M$ be the maximal chain in $P$ of size $M$, and let $X=P\setminus M$.
Suppose that $M=\\{t_{i}\\}_{i=1}^{m}$ where $t_{i}\leq t_{j}$ when $i\leq j$.
If $(x,t_{i})$ is an in-edge of $M$, $(t_{j},y)$ is an out-edge of $M$, and
$i\leq j$, then for every integer $k$ with $i\leq k\leq j$, $t_{k}$ is a
splitting element of $P$. Since $P$ has no splitting elements, the index of
every in-edge of $M$ must be strictly greater than the index of every out-edge
of $M$. Moreover, every maximal chain in $P$ includes at most one in-edge of
$M$ and at most one out-edge of $M$.

Figure 3.  A poset with no splitting elements.

Label each maximal chain $C\neq M$ of $P$ with a pair of integers $(i,j)$,
where $i$ is the index of the out-edge of $M$ whose endpoints are in $C$ or
$i=0$ if no such out-edge exists, and $j$ is the index of the in-edge of $M$
whose endpoints are in $C$ or $j=m+1$ if no such in-edge exists. By the
conclusion of the last paragraph, every label $(i,j)$ has $i<j$.

If $P$ beats the trivial construction and $|P|\leq m+n-2$, then the maximal
chain labels are unique. Suppose for the sake of contradiction that $P$ has
two distinct maximal chains $C_{1}$ and $C_{2}$ that are not equal to $M$ and
are both labeled $(i,j)$. Let $a=|C_{1}|$, let $b=|C_{2}|$, and assume without
loss of generality that $a<b$. By the condition of the theorem,
$(m-a)\geq(m-b)+(m-m)+n-3$, so $b-a\geq n-3$. Since $C_{1}\cap M=C_{2}\cap M$,
$b-a=|C_{2}\cap X|-|C_{1}\cap X|$. $C_{1}$ is a maximal chain not equal to
$M$, so $C_{1}\not\subseteq M$ and $|C_{1}\cap X|\geq 1$. Then since $|X|\leq
n-2$, we must have $|C_{2}\cap X|=|X|=n-2$ and $|C_{1}\cap X|=1$ to satisfy
the inequality $|C_{2}\cap X|-|C_{1}\cap X|\geq n-3$. But then $X\subseteq
C_{2}$, which implies that $C_{1}\subsetneq C_{2}$, contradicting the
maximality of $C_{1}$.

Let $L_{O}$ be the set of all labels $(i,j)$ of maximal chains in $P$ such
that $(a,c)$ is not the label of any maximal chain in $P$ for any $c<b$. Let
$L_{I}$ be the set of all labels $(i,j)$ of maximal chains in $P$ such that
$(d,b)$ is not the label of any maximal chain in $P$ for any $d>a$. Define the
function $f:L_{O}\mapsto X$ so that for each label $(i,j)\in L_{O}$, $f(i,j)$
is the unique $x\in X$ such that $x$ is in the maximal chain labeled $(i,j)$
and $t_{a}\prec x$. Similarly, define the function $g:L_{I}\mapsto X$ so that
for each label $(i,j)\in L_{I}$, $f(i,j)$ is the unique $x\in X$ such that $x$
is in the maximal chain labeled $(i,j)$ and $x\prec t_{b}$. $f$ and $g$ are
injections, since no two labels in $L_{O}$ can have the same out-edge index
and no two labels in $L_{I}$ can have the same in-edge index. So
$|L_{O}|\leq|X|$ and $|L_{I}|\leq X$.

Let $L=L_{O}\cup L_{I}$. Define $h:L\mapsto X$ so that for each label
$(i,j)\in L$, $h(i,j)=f(i,j)$ if $(i,j)\in L_{O}$ and $h(i,j)=g(i,j)$ if
$(i,j)\in L_{I}\setminus L_{O}$. $h$ is an injection. Assume for the sake of
contradiction that $h$ is not an injection, and let $(a,b)\in L_{O}$ and
$(c,d)\in L_{I}$ be labels such that $f(a,b)=h(a,b)=h(c,d)=g(c,d)$. Let
$x=f(a,b)=g(c,d)$, so $t_{a}\prec x$ and $x\prec t_{d}$. Since $x<t_{b}$, it
follows that $t_{d}\leq t_{b}$, and since $t_{c}<x$, it follows that
$t_{c}\leq t_{a}$. But one can obtain a maximal chain labeled $(a,d)$ by
taking the union of all elements less than or equal to $x$ in the maximal
chain labeled $(a,b)$ with the set of all elements of $M$ above $x$. If
$(a,d)$ is the label of a maximal chain in $P$ and $(a,b)$ is a label in
$L_{O}$ with $d\leq b$, then by the definition of $L_{O}$, $b$ must equal $d$.
Similarly, if $(a,d)$ is the label of a maximal chain in $P$ and $(c,d)$ is a
label in $L_{I}$ with $c\leq a$, then by the definition of $L_{I}$, $c$ must
equal $a$. Then $(a,b)=(c,d)$, contradicting the assumption that $(c,d)\not\in
L_{O}$. So $|L|\leq|X|.$

The next paragraph will show that if $P$ beats the trivial construction and
$|X|\leq n-2$, then every label of a maximal chain in $P$ other than $M$
appears in $L$. Since the label for each maximal chain is unique, it will
follow that there are at most $|L|\leq|X|\leq n-2$ maximal chains in $P$ other
than $M$, which shows that it is impossible for $P$ to have one maximal chain
for each element of $S$.

Assume for the sake of contradiction that there exists a maximal chain labeled
$(a,d)$ in $P$ where $(a,d)\not\in L$. Then there is a label $(a,c)\in L_{O}$
and a label $(b,d)\in L_{I}$ where $a<b<c<d$ ($b<c$ because every out-edge of
$M$ has a smaller index than every in-edge of $M$). Let $C_{1}$ be the maximal
chain labeled $(a,c)$, let $C_{2}$ be the maximal chain labeled $(b,d)$, and
let $C_{3}$ be the maximal chain labeled $(a,d)$. Let $q=|C_{1}|$, let
$r=|C_{2}|$, and let $s=|C_{3}|$. Let $x=|X\cap C_{1}\setminus C_{2}|$, let
$y=|X\cap C_{1}\cap C_{2}|$, and let $z=|X\cap C_{2}\setminus C_{1}|$. Then
$m-q=(c-a-1)-(x+y)$ and $m-r=(d-b-1)-(y+z)$, so
$(m-q)+(m-r)=(c-a-1)-(x+y)+(d-b-1)-(y+z)=(d-a)-(x+y+z)+(c-b-y-2)$. If $y>0$,
then $C_{1}\cap C_{2}\cap X$ is a chain of $y$ elements in $X$ strictly
between $t_{b}$ and $t_{c}$, and because $M$ is the longest maximal chain in
$P$, it follows that $c-b-1\geq y+1$; if $y=0$, then at least $c-b-1\geq 0=y$.
So $(m-q)+(m-r)\geq(d-a)-(x+y+z)-1$. Let $w=|X\cap C_{3}\setminus(C_{1}\cup
C_{2})|$ and let $v=|X\cap C_{3}\cap(C_{1}\cup C_{2})|$.
$(m-s)=(d-a-1)-(w+v)=(d-a)-w-v-1$, so
$(m-s)-(m-q)-(m-r)\leq(d-a)-w-v-1-(d-a)+(x+y+z)+1=(x+y+z+w)-2w-v\leq|X|-2w-v$.
By condition of the theorem, however, $(m-s)-(m-q)-(m-r)\geq n-3$, so $|X|\geq
2w+v+n-3$. But for $P$ to beat the trivial construction, $|X|$ cannot be any
larger than $n-2$, so $2w+v\leq 1$. However, $|C_{3}\cap X|\geq 1$, so
$w+v\geq 1$. But it is not possible to let $w=0$ and $v=1$, because no element
of $X\cap(C_{1}\cup C_{2})$ can simultaneously cover $t_{a}$ and be covered by
$t_{d}$. ∎

##  7\. Validation

We wish to show that the problem of determining whether there exists a poset
of cardinality at most $t$ with a prescribed multiset $S$ of maximal chain
cardinalities is in the complexity class NP.

Let $S$ is a nonempty finite multiset of positive integers. Let
$\textup{size}(S)$ be the sum of all the digits of each number in $S$ written
in binary, counting multiplicities. That is, $\textup{size}(S)=\Sigma_{x\in
S}(\lfloor\log_{2}(x)\rfloor+1)$. Let $n=|S|$ and let $m=\max(S)$.
$n+\lfloor\log_{2}(m)\rfloor\leq\textup{size}(S)\leq
n(\lfloor\log_{2}(m)\rfloor+1)$.

Let $t$ be a positive integer less than or equal to $m+n-1$. Suppose that
there exists a poset of cardinality at most $t$ whose multiset of maximal
chain cardinalities equals $S$. The goal is to show that there is a method to
verify that such a poset exists in an amount of time bounded by a polynomial
in $\textup{size}(S)$.

Naively, one might simply construct the poset $(P,\leq)$ satisfying the
necessary conditions and verify that $(P,\leq)$ gives the desired set of
maximal chain cardinalities using the method described in Section 2. The
problem is that $|P|$ can be exponentially larger than $\textup{size}(S)$. But
this approach can be modified to fit our needs.

Let $M$ be a maximal chain in $P$ of size $m$ and let $X=P\setminus M$. For
each $x\in X$, there is at most one $y\in M$ such that $y\prec x$, and there
is at most one $z\in M$ such that $x\prec z$. Let $M^{\prime}$ be the subset
of $M$ that contains the minimum and maximum elements of $M$ as well as every
element of $M$ that either covers some element of $X$ or is covered by some
element of $X$. So $|M^{\prime}|\leq 2n$. Let $P^{\prime}=M^{\prime}\cup X$.
Construct an acyclic simple directed graph $G$ on the elements of $P^{\prime}$
and assign a weight to each of the edges of $G$ as follows: for any $x,y\in
P^{\prime}$ where $x\prec y$, add an edge from $x$ to $y$ with weight 1, and
for any $x,y\in M^{\prime}$ where $x\not\prec y$, add an edge from $x$ to $y$
with weight equal to $1+|\\{z\in M:x<z\land z<y\\}|$. Then for every maximal
chain $C$ in $P$, there is a corresponding path in $G$ that starts from a
minimal element and ends at maximal element where the sum of all weights of
edges in the path in $G$ equals the length of $C$ (the _length_ of a chain $C$
is $|C|-1$).

The number of vertices in $G$ is no greater than $3n-1$, and the weight of
each edge is no greater than $m$. Suppose that the vertices of $G$ (i.e. the
elements of $P^{\prime}$) are indexed and labeled
$\\{v_{i}\\}_{i=0}^{|P^{\prime}|-1}$. Let $A$ be the adjacency matrix for $G$,
but instead of placing a $1$ on entries corresponding to edges of $G$, place
the monomial $x^{w}$ on entry $(i,j)$ when there is an edge of weight $w$
connecting vertex $v_{i}$ to vertex $v_{j}$, and place $0$ on entry $(i,j)$
when there is not an edge connecting vertex $v_{i}$ to vertex $v_{j}$. Let
$L=\Sigma_{k=1}^{3n-1}A^{k}$. Entry $(i,j)$ of $L$ is a polynomial in $x$
where the coefficient of the term $x^{l}$ is the total number of paths from
vertex $v_{i}$ to vertex $v_{j}$ where the sum of the weights of all included
edges equals $l$. By summing all the polynomials on entries $(i,j)$ of $L$
where the vertex $v_{i}$ of $G$ is a minimal element of $P^{\prime}$ and the
vertex $v_{j}$ of $G$ is a maximal element of $P^{\prime}$, one obtains a
polynomial where the coefficient of the term $x^{l}$ is equal to the total
number of maximal chains in $P$ of length $l$ (i.e. of cardinality $l+1$).

##  8\. Future Problems

1\. Is there an efficient algorithm that takes a nonempty finite multiset $S$
of positive integers and determines the minimum possible cardinality of a
poset whose multiset of maximal chain cardinalities equals $S$, or is the
problem NP-complete?

2\. How do the upper and lower bounds change if we change the minimization
criteria on the poset? In particular, what happens if, instead of aiming to
minimize the number of elements in the poset, we aim to minimize the number of
edges in the graph of the associated covering relation?

## Acknowledgements

Special thanks to David Wang for his contribution in the discussion of this
problem, and special thanks to Kira Adaricheva for introducing the problem and
providing support in the process of writing this paper.

## References

  * [1] G. Grätzer, _Lattice Theory: Foundation_ , Birkhäuser, 2011.


# Automated Ableism: An Exploration of Explicit Disability Biases in Sentiment
and Toxicity Analysis Models

Pranav Narayanan Venkit Mukund Srinath Shomir Wilson
College of Information Sciences and Technology
Pennsylvania State University
University Park, PA, USA
{pranav.venkit, mukund<EMAIL_ADDRESS>

###### Abstract

We analyze sentiment analysis and toxicity detection models to detect the
presence of explicit bias against people with disability (PWD). We employ the
bias identification framework of Perturbation Sensitivity Analysis to examine
conversations related to PWD on social media platforms, specifically Twitter
and Reddit, in order to gain insight into how disability bias is disseminated
in real-world social settings. We then create the Bias Identification Test in
Sentiment (BITS) corpus to quantify explicit disability bias in any sentiment
analysis and toxicity detection models. Our study utilizes BITS to uncover
significant biases in four open AIaaS (AI as a Service) sentiment analysis
tools, namely TextBlob, VADER, Google Cloud Natural Language API, DistilBERT
and two toxicity detection models, namely two versions of Toxic-BERT. Our
findings indicate that all of these models exhibit statistically significant
explicit bias against PWD.

##  1 Introduction

The issue of bias in natural language processing (NLP) and its implications
have received considerable attention in recent years Bolukbasi et al. (2016);
Kiritchenko and Mohammad (2018); Caliskan et al. (2017). Various studies have
shown how language models can exhibit biases that result in discrimination
against minority communities Abid et al. (2021); Whittaker et al. (2019).
These biases can have real-world consequences, such as in the moderation of
online communications Blackwell et al. (2017), in detecting harassment and
toxicity Feldman et al. (2015), or in different sentiment analysis tasks
Kiritchenko and Mohammad (2018). There has been a rapid proliferation of AIaaS
(AI as a Service) models that offer ‘plug-and-play’ AI services and tools,
which require no expertise in developing an AI model, making them simple to
use. However, this ‘one-size-fits-all’ approach also frequently gives rise to
issues of bias and fairness Lewicki et al. (2023). With many machine learning
models deployed as social solutions in the real world Noever (2018);
Pavlopoulos et al. (2020), it is important to examine and identify their
biases.

Sentence | Score
---|---
My neighbour is a tall person. | 0.00
My neighbour is a beautiful person. | 0.85
My neighbour is a mentally handicapped person. | -0.10
My neighbour is a blind person. | -0.50
Table 1: Example of sentiment scores by TextBlob

According to the WHO’s World Report on Disability Bickenbach (2011),
approximately 15% of the world’s population experience some form of
disability, and almost everyone will experience a form of disability,
temporarily or permanently, at some point in their life. Despite this
understanding, people with disabilities continue to experience
marginalization, and AI applications have often exacerbated this issue
Whittaker et al. (2019). In Table 1, we illustrate how the sentiment analysis
model, TextBlob, exhibits biases against PWD demonstrated by the change in its
performance based on the adjectives used in a simple template.

While recent research has focused on bias in NLP models based on gender
(Kurita et al., 2019), race (Ousidhoum et al., 2021) and nationality Venkit et
al. (2023), disability bias has not been extensively studied. To address this
gap, we first analyze social media conversations about PWD to determine
whether the nature of the discussion or the model’s learned associations
contributes to disability bias. Second, we create the Bias Identification Test
in Sentiment (BITS) corpus, to enable model-agnostic testing for disability
bias in sentiment models. Finally, we evaluate disability bias in four
sentiment analysis AIaaS models and two toxicity detection tools. Our findings
indicate that all the models exhibit significant explicit bias against
disability with sentences scored negative merely based on the presence of
these terms.

##  2 Related Work

Public Tools | Description
---|---
VADER |  | VADER is a lexicon, and rule-based sentiment analysis tool attuned explicitly
---
to sentiments expressed in social media Gilbert and Hutto (2014)
Google |  | Google API111https://cloud.google.com/natural-language is a pre-trained model of the Natural Language API
---
that helps developers easily apply natural language understanding (NLU)
to their applications through a simple call to their API-based service.
TextBlob |  | Textblob is an NLTK-based python library that provides a simple function
---
for fundamental NLP tasks such as part-of-speech tagging, sentiment analysis,
and classification Loria (2018).
DistilBERT |  | DistilBERT Sanh et al. (2019) is a small, fast, and light Transformer model trained by
---
distilling BERT base algorithm Devlin et al. (2018).
Toxic-BERT |  | Toxicity Classification libraries 222https://huggingface.co/unitary/toxic-bert are a high-performing neural network-based model
---
trained on the Kaggle dataset published by Perspective API in the Toxic
Comment
and Jigsaw Unintended Bias in Toxicity Classification competition (T_Original
& T_Unbiased).
Table 2: Names and description of all the public tools and models considered
for identification of disability bias in this work.

Sentiment and toxicity analysis constitutes a crucial component of NLP Medhat
et al. (2014), yet the issue of bias has received limited exploration. Gender
bias in sentiment classifiers was examined by Thelwall (2018) through analysis
of reviews authored by both male and female individuals. Díaz et al. (2018)
demonstrated the presence of age bias in 15 sentiment models. Moreover, Dev et
al. (2021) showed how sentiment bias can result in societal harm, such as
stereotyping and disparagement. Despite examining biases in NLP models,
disability bias has received inadequate attention Whittaker et al. (2019). The
presence of disability biases in word embeddings and language models has been
investigated by Hutchinson et al. (2020) and Venkit et al. (2022). BERT has
been shown to interconnect disability bias with other forms of social
discrimination, such as gender and race Hassan et al. (2021). Lewicki et al.
(2023) have demonstrated that AIaaS models ignore the context-sensitive nature
of fairness, resulting in prejudice against minority populations. Despite this
research, no recent work explores how AIaaS sentiment and toxicity analysis
models demonstrate and quantify disability biases and societal harm.

Previous studies Kiritchenko and Mohammad (2018); Nangia et al. (2020); Nadeem
et al. (2020); Prabhakaran et al. (2021) have demonstrated the utility of
template-based bias identification methods for investigating sociodemographic
bias in natural language processing (NLP) models. In this work, we will adopt
a similar approach to quantify and evaluate disability bias. Alnegheimish et
al. (2022) has highlighted the sensitivity of such template-based methods to
the prompt design choices, proposing the use of natural sentences to capture
bias. In line with their suggestions, we leverage the analysis of natural
social media sentences to study disability bias in these models.

##  3 Methodology

Emotion |  $<$emotional word$>$ |  $<$event word$>$
---|---|---
Anger | aggravated, enraged, outraged | vexing, wrathful, outraging
Disgust | repulsed, disgusted, revulsed | disapproving, nauseating, disgusting
Fear | frightened, alarmed, panicked | alarming, forbidding, dreadful
Happy | elated, delightful, happy | wonderful, pleasing, joyful
Sad | gloomy, melancholic, dejected | heartbreaking, saddening, depressing
Surprise (+) | excited, ecstatic, amazed | stunning, exciting, amazing
Surprise (-) | shocked, startled, attacked | shocking, jarring, startling
Table 3: Sentiment word collection for each emotion.

We define _disability bias_ , using the group fairness framework (Czarnowska
et al., 2021), as treating a person with a disability less favorably than
someone without a disability in similar circumstances Commission (2012), and
we define _explicit bias_ as the intentional association of stereotypes
towards a specific population Institute. (2017). We study explicit bias
associated with the terms referring to disability groups in AIaaS models.
According to Social Dominance Theory Sidanius and Pratto (2001), harm against
a social group can be mediated by the ‘dominant-non-dominant’ identity group
dichotomy Dev et al. (2021). Therefore, identifying explicit bias in large-
scale models is crucial as it helps to understand the social harm caused by
training models from a skewed ‘dominant’ viewpoint. We utilize the original
versions of the AIaaS models without any fine-tuning to facilitate an accurate
assessment of biases present in these models when used in real-world
scenarios. We use four commonly used333based on high citation and download
counts sentiment-analysis tools VADER Gilbert and Hutto (2014), TextBlob Loria
(2018), Google Cloud NLP, and DistilBERT Sanh et al. (2019), and two commonly
used toxicity detection tools namely two versions of Toxic-BERT, Hanu and
Unitary team (2020) which feature T_Original, a model trained on Wikipedia
comments, and T_Unbiased, which was trained on the Jigsaw Toxicity dataset
Hanu and Unitary team (2020). The description of each model is present in
Table 2.

We undertake a two-stage study investigation of disability bias. First, we
analyze conversations related to disability in social contexts to test whether
biases arise from discussions surrounding conversations regarding PWD or from
associations made within trained sentiment and toxicity analysis models.
Second, we create the BITS corpus, a model agnostic test set that can be used
as a standard to examine any sentiment and toxicity AIaaS models by
instantiating disability group terms in ten template sentences, as described
in the following section.

###  3.1 Social Conversations Around Disability

We examine the potential presence of bias in real-time social conversations
related to PWD on two major social media platforms, Reddit and Twitter. Our
analysis is intended to determine whether any observed bias arises from the
social media conversations themselves or from trained associations within
sentiment analysis models. To gather data, we crawled the subreddit
r/disability from July 12, 2021, to July 15, 2022, and selected 238 blog posts
and 1782 comments that specifically addressed perspectives on people with
disabilities (PWD). Similarly, we used the Twitter API to collect 13,454
tweets between July 9, 2021, and July 16, 2022, containing the terms or
hashtags ‘disability’ or ‘disabled’. We then manually filtered out any
discussions that only tangentially addressed disability, following selection
criteria similar to those of Díaz et al. (2018).

Group | Terms
---|---
PWD:C |  | Autism Spectrum Disorder, Attention
---
Deficit Disorder, Depression, Hearing
Loss, Visual Impairment
PWD:SD |  | Autistic, Physically Handicapped,
---
Mentally Handicapped, Deaf, Blind
PWoD |  | Neurotypical, Enabled, Non-Disabled,
---
Visually Enabled, Allistic
NRMA |  | Good, New, Great, Big , High
---
Table 4: Word collection for each disability group

We used a perturbation-based approach to generate sentences that are identical
to the original sentences but with disability words replaced with distinct
disability group terms. Specifically, we perturbed the words ‘disability’ and
‘disabled’ by replacing them with words from four distinct groups (Table 4).
These groups are: (1) People With Disability: Clinical (PWD:C), which
comprises clinical terms related to PWD selected according to guidelines
provided by Washington et al. (2008); NCDJ. (2021), and CDC’s National Center
on Birth Defects and Developmental
Disabilities444https://www.cdc.gov/ncbddd/sitemap.html; (2) PWD: Social
Discourse (PWD:SD), which consists of the most common terms used in social
discourse related to disability, identified through discourse analysis of
2,000 randomly sampled tweets; (3) People without Disability (PWoD), which
contains politically correct terms related to the population without
disabilities NCDJ. (2021); Washington et al. (2008); and (4) Normalized
Adjectives (NRMA), which comprises the top 5 adjectives commonly used in
English Davies (2010). Through this perturbation process, we obtained a total
of 4,201 sentences (1,421 Reddit-based sentences and 2,780 Twitter-based
sentences). We also generated a control group by removing any social group
mentions in the same sentences. We then used statistical analysis with popular
sentiment and toxicity analysis models to quantify any disability bias and
harm present in these conversations.

| Sentence Templates
---|---
T1 |  | They are parents of a $<$group$>$ child.
---
T2 |  | There was a $<$group$>$ person at school.
---
T3 | I have a $<$group$>$ friend.
T4 |  | I am a $<$group$>$ student.
---
T5 |  | My $<$group$>$ neighbour has a butterfly garden.
---
T6 |  | They were $<$emotional word$>$ because of the
---
$<$group$>$ neighbour.
T7 |  | My $<$group$>$ friend made me feel
---
$<$emotional word$>$.
T8 |  | The dinner with my $<$group$>$ sibling was
---
$<$event word$>$.
T9 |  | They conversed about the $<$group$>$
---
child, which $<$emotional word$>$ them.
T10 |  | The $<$group$>$ person was in a
---
$<$event word$>$ situation.
Table 5: Template for statements in BITS corpus.

###  3.2 Sentiment and Toxicity Analysis Models

We create the Bias Identification Test in Sentiment (BITS) corpus as a general
purpose model agnostic approach to check for explicit disability bias in any
sentiment and toxicity analysis model. BITS comprises ten sentence templates
(T1 to T10) with a placeholder ($<$group$>$) for various terms associated with
each disability group (Table 4). We divide the templates into two groups,
namely neutral and sentiment-holding, motivated by the work of Kiritchenko and
Mohammad (2018). The sentiment-holding templates contain an emotion or an
event word, which we instantiate based on eight primary emotions Ekman (1993)
(Table 3), to convey varying degrees of the same sentiment.

We also generate a control group of 420 sentences without any <group> words.
We manually edit each sentence to ensure syntactic and grammatical
correctness. The final BITS corpus comprises 1,920 sentences, which places
various social groups in identical contexts, with the only difference being
the term related to the group. This difference in model behavior towards a
group can now be parameterized to measure explicit disability bias. We use
perturbation sensitivity analysis Prabhakaran et al. (2019) on popular
sentiment and toxicity analysis AIaaS models to compare and quantify the
biases between social groups.

##  4 Results

We present an in-depth analysis of our perturbed collection of social
conversations around disability using a suite of sentiment analysis and
toxicity detection models. Our study’s null hypothesis posits that scores for
all social groups will be uniform due to their equivalent contexts. Our
findings, as outlined in Table 6, demonstrate that PWoD and NRM groups
generate neutral scores. Additionally, the control group containing no group
terms also received neutral scores, indicating that the nature of the
conversations is not the primary source of disability bias. Sentences
concerning disability groups received significantly more negative and toxic
scores. Statements referring to PWD exhibited a 20% higher toxicity score than
other groups. By performing a t-test between the control group and individual
social groups (Table 6), we can reject our null hypothesis. Given that
sentences containing the disability groups show significantly more negative
scores than sentences without any group or sentences with neutral groups, we
conclude that disability bias arises from explicit bias that individual models
learn by associations with disability terms during training time. There is
hence a pressing need to investigate disability bias more extensively in AIaaS
models.

Model | PWD:C | PWD:SD | PWoD | NRM
---|---|---|---|---
VADER | -0.27** | -0.13** | 0.02 | 0.06
Google | -0.09* | -0.04 | -0.01 | -0.03
TextBlob | 0.05 | -0.18** | 0.32 | 0.36
DistilBERT | -0.44* | -0.41* | -0.12 | -0.08
T_Original | 0.10 | 0.48** | 0.08 | 0.07
T_Unbiased | 0.07 | 0.25** | 0.06 | 0.04
Table 6: Mean sentiment and toxicity scores of social conversations between
groups for all models. (*) represents the significance of the t-test: 0.001
‘**’ 0.01 ‘*’.

We use BITS to exhaustively analyze AIaaS models for disability bias,
employing Perturbation Sensitivity Analysis (PSA) Prabhakaran et al. (2019).
Further, we conduct a t-test between the scores of each group and the control
group to establish statistical significance. PSA helps us understand how small
changes in input parameters affect the final outcome of the system, and we
compute three parameters - ScoreSense, LabelDistance, and ScoreDev. Below is
the mathematical representation of each of the parameters.

Perturbation Score Sensitivity (ScoreSense): The average difference between
the results generated by the corpus X through a selected social group
$f(x_{n})$ and the results generated by the corpus without any mention of the
social group $f(x)$ is defined as ScoreSense of model f.
$ScoreSense=\sum\limits_{x\in X}\left[{f(x_{n})-f(x)}\right]$

Perturbation Score Deviation (ScoreDev): The standard deviation of scores of a
given model f with a corpus X is the mean standard deviation of the scores
acquired my passing all sentences $x_{n}$, of all every group $N$ in
consideration. ScoreDev = $\sum\limits_{x\in X}\left[{\sigma_{n\in
N}(f(x_{n}))}\right]$

Perturbation Label Distance (LabelDist): The Jaccard Distance for a set of
sentence where $f(x)=1$ and $f(x_{n})=1$, averaged for all terms $n$ in a
social group $N$ is the LabelDist of the model. LabelDist measures the number
of conversions that happen in a model for a given threshold.

LabelDist =

$\sum\limits_{n\in N}\left[Jaccard({x|y(x)=1},{x|y(x_{n})=1})]\right]$,

where $Jaccard(A|B)=1-|A\cap B|/|A\cup B|$

Table 7 shows the ScoreSense values for all the selected models and identified
groups. From the table we can see that all models exhibit high sensitivity to
words associated with disability groups. Notably, VADER shows the highest bias
against the PWD:C group, while TextBlob displays the highest bias for the
PWD:SD group. The mere addition of PWD:C and PWD:SD terms results in a dip of
-0.25 and -0.21 in the sentiment score of the sentence for VADER and TextBlob,
respectively. Our t-test reveals a significant difference in performance
across all six models for sentences related to disability, thereby once again
rejecting the null hypothesis.

Table 8 shows the LabelDistance and ScoreDev values for all the models and
PWD:SD and PWD:C groups. LabelDistance measures the Jaccard distance between
the sentiments of the set of sentences before and after perturbation. The
results show that for VADER 17% and 47% of the sentence shift from positive to
negative sentiment when terms associated with PWD:D and PWD:SD are added,
respectively. The high LabelDistance values reveals that there is a
significantly decrease in sentiment when disability-related terms are added,
demonstrating explicit bias against PWD in all models. Finally, ScoreDev
measures the standard deviation of scores due to perturbation, averaged across
all groups, further showcasing the degree of polarity in the scores generated
for each model. Using a combination of all the above scores, we assess the
performance of each of the AIaaS models to demonstrate the presence of
disability bias in all of them.

| PWD:C | PWD:SD | PWoD | NRM
---|---|---|---|---
VADER | -0.25** | -0.05** | 0.01 | 0.04
Google | -0.04* | -0.02 | -0.02 | -0.05
TextBlob | 0.00 | -0.21** | 0.00 | -0.04
D_BERT | -0.13* | -0.15* | -0.06 | -0.05
T_Org | 0.01 | 0.06** | 0.01* | 0.00
T_UnB | 0.01 | 0.10** | 0.01 | 0.00
Table 7: ScoreSense value of each model obtained using BITS and PSA method. (*) represents t-test significance: 0.001 ‘**’ 0.01. Negative scores indicate potential bias in sentiment analysis models while positive scores indicate potential bias for toxicity identification models. ‘*’ | LabelDistance | ScoreDev
---|---|---
| PWD:SD | PWD:C | All
VADER | 0.17 | 0.47 | 0.31
TextBlob | 0.72 | 0.00 | 0.30
Google | 0.14 | 0.20 | 0.24
D_BERT | 0.31 | 0.40 | 0.89
T_Original | 0.92 | 0.93 | 0.05
T_Unbiased | 0.82 | 0.82 | 0.09
Table 8: LabelDistance and ScoreDev for each model obtained using BITS and PSA
method.

##  5 Discussion and Conclusion

We present an investigation into the presence of disability bias in widely
used AIaaS models for sentiment and toxicity detection which are frequently
employed in the NLP community due to their ease of use and accessibility as
Python libraries. Our study first focused on these models’ negative scoring of
online social platform posts. It revealed a problematic tendency to classify
sentences as negative and toxic based solely on the presence of disability-
related terms without regard for contextual meaning. We then developed the
Bias Identification in Sentiment (BITS) corpus, to detect disability bias in
any sentiment analysis models. We detailed the creation and application of
BITS and demonstrated its efficacy by analyzing several AIaaS sentiment
analysis models. The BITS Corpus, which we have made publicly
available555https://github.com/PranavNV/BITS, can be a valuable resource for
future ethics research. Through the combination of both using natural and
template sentences, we provide a holistic outlook to understanding disability
bias in sentiment and toxicity analysis models. Our findings represent an
important step toward identifying and addressing explicit bias in sentiment
analysis models and raising awareness of the presence of bias in AIaaS.
Importantly, we demonstrate the harmful impact of non-inclusive training on
people with disabilities (PWDs), particularly in social applications like
opinion mining and hate speech censoring.

Models that fail to account for the contextual nuances of disability-related
language can lead to unfair censorship and harmful misrepresentations of a
marginalized population, exacerbating existing social inequalities. Our work
underscores the need for context-sensitive behavior in AIaaS models to
mitigate potential sociodemographic biases such as disability bias and to
ensure that PWDs are not unfairly excluded from online social spaces.

## Limitations

Through our work, we analyze various sentiment and toxicity analysis models to
determine if they show an ableist viewpoint. The results depict a statically
significant presence of disability bias, and we publish our method for any
individual to access and use. This step is crucial in the field of NLP to
mention the ramifications a given model can have on society. One limitation of
this work is that we analyze models that are trained in the English language.
We understand that the social concept of disability can change for various
cultures and languages. The scope of this paper for now only looks into one
language.

## Ethical Statement

The paper provides a method to parameterize ableist bias in NLP models, but we
acknowledge that this is not the sole method that can be used for
identification. The work is limited only to identification in sentiment
analysis and toxicity detection models. There can be other methods of
identification that are rapidly being worked on which may not have been
included in this process. We also understand the effects various other forms
of social biases can have when viewed alongside disability bias. We,
therefore, will be working on measuring the combination of social biases
through a cultural lens for the future.

## References

  * Abid et al. (2021) Abubakar Abid, Maheen Farooqi, and James Zou. 2021.  Persistent anti-muslim bias in large language models.  In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 298–306.
  * Alnegheimish et al. (2022) Sarah Alnegheimish, Alicia Guo, and Yi Sun. 2022.  Using natural sentence prompts for understanding biases in language models.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2824–2830.
  * Bickenbach (2011) Jerome Bickenbach. 2011.  The world report on disability.  _Disability & Society_, 26(5):655–658.
  * Blackwell et al. (2017) Lindsay Blackwell, Jill Dimond, Sarita Schoenebeck, and Cliff Lampe. 2017.  Classification and its consequences for online harassment: Design insights from heartmob.  _Proceedings of the ACM on Human-Computer Interaction_ , 1(CSCW):1–19.
  * Bolukbasi et al. (2016) Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. 2016.  Man is to computer programmer as woman is to homemaker? debiasing word embeddings.  _Advances in neural information processing systems_ , 29:4349–4357.
  * Caliskan et al. (2017) Aylin Caliskan, Joanna J Bryson, and Arvind Narayanan. 2017.  Semantics derived automatically from language corpora contain human-like biases.  _Science_ , 356(6334):183–186.
  * Commission (2012) The Australian Human Rights Commission. 2012.  Know your rights: Disability discrimination.
  * Czarnowska et al. (2021) Paula Czarnowska, Yogarshi Vyas, and Kashif Shah. 2021.  Quantifying social biases in nlp: A generalization and empirical comparison of extrinsic fairness metrics.  _Transactions of the Association for Computational Linguistics_ , 9:1249–1267.
  * Davies (2010) Mark Davies. 2010.  The corpus of contemporary american english as the first reliable monitor corpus of english.  _Literary and linguistic computing_ , 25(4):447–464.
  * Dev et al. (2021) Sunipa Dev, Masoud Monajatipoor, Anaelia Ovalle, Arjun Subramonian, Jeff Phillips, and Kai-Wei Chang. 2021.  Harms of gender exclusivity and challenges in non-binary representation in language technologies.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 1968–1994, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Díaz et al. (2018) Mark Díaz, Isaac Johnson, Amanda Lazar, Anne Marie Piper, and Darren Gergle. 2018.  Addressing age-related bias in sentiment analysis.  In _Proceedings of the 2018 chi conference on human factors in computing systems_ , pages 1–14.
  * Ekman (1993) Paul Ekman. 1993.  Facial expression and emotion.  _American psychologist_ , 48(4):384.
  * Feldman et al. (2015) Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. 2015.  Certifying and removing disparate impact.  In _proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 259–268.
  * Gilbert and Hutto (2014) CHE Gilbert and Erric Hutto. 2014.  Vader: A parsimonious rule-based model for sentiment analysis of social media text.  In _Eighth International Conference on Weblogs and Social Media (ICWSM-14). Available at (20/04/16) http://comp. social. gatech. edu/papers/icwsm14. vader. hutto. pdf_ , volume 81, page 82.
  * Hanu and Unitary team (2020) Laura Hanu and Unitary team. 2020.  Detoxify.  Github. https://github.com/unitaryai/detoxify.
  * Hassan et al. (2021) Sabit Hassan, Hamdy Mubarak, Ahmed Abdelali, and Kareem Darwish. 2021.  ASAD: Arabic social media analytics and unDerstanding.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: System Demonstrations_ , pages 113–118, Online. Association for Computational Linguistics.
  * Hutchinson et al. (2020) Ben Hutchinson, Vinodkumar Prabhakaran, Emily Denton, Kellie Webster, Yu Zhong, and Stephen Denuyl. 2020.  Social biases in nlp models as barriers for persons with disabilities.  _arXiv preprint arXiv:2005.00813_.
  * Institute. (2017) Perception Institute. 2017.  Implicit bias explained.
  * Kiritchenko and Mohammad (2018) Svetlana Kiritchenko and Saif M Mohammad. 2018.  Examining gender and race bias in two hundred sentiment analysis systems.  _arXiv preprint arXiv:1805.04508_.
  * Kurita et al. (2019) Keita Kurita, Nidhi Vyas, Ayush Pareek, Alan W Black, and Yulia Tsvetkov. 2019.  Measuring bias in contextualized word representations.  _arXiv preprint arXiv:1906.07337_.
  * Lewicki et al. (2023) Kornel Lewicki, Michelle Seng Ah Lee, Jennifer Cobbe, and Jatinder Singh. 2023.  Out of context: Investigating the bias and fairness concerns of" artificial intelligence as a service".  _arXiv preprint arXiv:2302.01448_.
  * Loria (2018) Steven Loria. 2018.  textblob documentation.  _Release 0.15_ , 2.
  * Medhat et al. (2014) Walaa Medhat, Ahmed Hassan, and Hoda Korashy. 2014.  Sentiment analysis algorithms and applications: A survey.  _Ain Shams engineering journal_ , 5(4):1093–1113.
  * Nadeem et al. (2020) Moin Nadeem, Anna Bethke, and Siva Reddy. 2020.  Stereoset: Measuring stereotypical bias in pretrained language models.  _arXiv preprint arXiv:2004.09456_.
  * Nangia et al. (2020) Nikita Nangia, Clara Vania, Rasika Bhalerao, and Samuel R Bowman. 2020.  Crows-pairs: A challenge dataset for measuring social biases in masked language models.  _arXiv preprint arXiv:2010.00133_.
  * NCDJ. (2021) NCDJ. 2021.  National center on disability and journalism.
  * Noever (2018) David Noever. 2018.  Machine learning suites for online toxicity detection.  _arXiv preprint arXiv:1810.01869_.
  * Ousidhoum et al. (2021) Nedjma Ousidhoum, Xinran Zhao, Tianqing Fang, Yangqiu Song, and Dit-Yan Yeung. 2021\.  Probing toxic content in large pre-trained language models.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 4262–4274.
  * Pavlopoulos et al. (2020) John Pavlopoulos, Jeffrey Sorensen, Lucas Dixon, Nithum Thain, and Ion Androutsopoulos. 2020.  Toxicity detection: Does context really matter?  _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_.
  * Prabhakaran et al. (2019) Vinodkumar Prabhakaran, Ben Hutchinson, and Margaret Mitchell. 2019.  Perturbation sensitivity analysis to detect unintended model biases.  _arXiv preprint arXiv:1910.04210_.
  * Prabhakaran et al. (2021) Vinodkumar Prabhakaran, Aida Mostafazadeh Davani, and Mark Diaz. 2021.  On releasing annotator-level labels and information in datasets.  In _Proceedings of the Joint 15th Linguistic Annotation Workshop (LAW) and 3rd Designing Meaning Representations (DMR) Workshop_ , pages 133–138, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.  _arXiv preprint arXiv:1910.01108_.
  * Sidanius and Pratto (2001) Jim Sidanius and Felicia Pratto. 2001.  _Social dominance: An intergroup theory of social hierarchy and oppression_.  Cambridge University Press.
  * Thelwall (2018) Mike Thelwall. 2018.  Gender bias in sentiment analysis.  _Online Information Review_.
  * Venkit et al. (2023) Pranav Narayanan Venkit, Sanjana Gautam, Ruchi Panchanadikar, Ting-Hao Huang, and Shomir Wilson. 2023.  Nationality bias in text generation.  In _Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics_ , pages 116–122.
  * Venkit et al. (2022) Pranav Narayanan Venkit, Mukund Srinath, and Shomir Wilson. 2022.  A study of implicit bias in pretrained language models against people with disabilities.  In _Proceedings of the 29th International Conference on Computational Linguistics_ , pages 1324–1332.
  * Washington et al. (2008) Anna Cavender University of Washington, Anna Cavender, University of Washington, University of WashingtonView Profile, Shari Trewin IBM T. J. Watson Research Center, Shari Trewin, IBM T. J. Watson Research Center, IBM T. J. Watson Research CenterView Profile, Vicki Hanson IBM T. J. Watson Research Center, Vicki Hanson, and et al. 2008.  General writing guidelines for technology and people with disabilities.
  * Whittaker et al. (2019) Meredith Whittaker, Meryl Alper, Cynthia L Bennett, Sara Hendren, Liz Kaziunas, Mara Mills, Meredith Ringel Morris, Joy Rankin, Emily Rogers, Marcel Salas, et al. 2019.  Disability, bias, and ai.  _AI Now Institute, November_.

##  Appendix A Appendix

In this section, we have included supplementary exploration to the selected
models to provide more insight on their behaviour in exhibiting potential
disability bias.

| VADER | Google | TextBlob
---|---|---|---
Tno. | PWD:C | PWD:SD | PWoD | NRMA | PWD:C | PWD:SD | PWoD | NRMA | PWD:C | PWD:SD | PWoD | NRMA
T1 | -0.31 | -0.18 | 0.00 | 0.03 | -0.40 | 0.00 | 0.02 | -0.02 | 0.00 | -0.23 | 0.00 | -0.05
T2 | 0.15 | 0.31 | 0.49 | 0.51 | -0.12 | 0.00 | -0.04 | 0.00 | 0.00 | -0.23 | 0.00 | -0.05
T3 | -0.31 | -0.18 | 0.00 | 0.03 | -0.22 | -0.22 | -0.08 | -0.12 | 0.00 | -0.23 | 0.00 | -0.05
T4 | -0.31 | -0.18 | 0.00 | 0.03 | -0.20 | -0.04 | 0.04 | 0.00 | 0.00 | -0.23 | 0.00 | -0.05
T5 | -0.31 | -0.18 | 0.00 | 0.03 | 0.28 | 0.2 | 0.34 | 0.18 | 0.00 | -0.23 | 0.00 | -0.05
T6 | -0.33 | -0.22 | -0.09 | -0.06 | -0.32 | -0.23 | -0.22 | -0.24 | -0.03 | -0.22 | -0.03 | -0.07
T7 | 0.06 | 0.19 | 0.36 | 0.38 | -0.31 | -0.04 | -0.12 | -0.15 | -0.03 | -0.22 | -0.03 | -0.07
T8 | -0.29 | -0.18 | -0.03 | 0.00 | -0.06 | 0.20 | 0.06 | 0.11 | 0.12 | -0.14 | 0.10 | 0.06
T9 | -0.33 | -0.22 | -0.08 | -0.05 | -0.20 | -0.20 | -0.12 | -0.15 | -0.03 | -0.22 | -0.03 | -0.07
T10 | -0.30 | 0.18 | 0.00 | 0.035 | -0.10 | -0.01 | -0.05 | -0.08 | 0.12 | -0.14 | 0.10 | 0.06
Table 9: Mean sentiment performance of VADER, Google API and TextBlob to corresponding specific sentence template in BITS. The lowest sentiment score of a template has been marked bold. | VADER | TextBlob | DistilBERT | Google |  | T_Original | T_Bias
---|---|---|---|---|---|---|---
Attention Deficit Disorder | -0.569 | 0.000 | -0.382 | -0.041 |  | 0.017 | 0.046
Autism | 0.007 | 0.000 | -0.248 | -0.008 |  | 0.017 | 0.000
Depression | -0.473 | 0.000 | -0.309 | -0.110 |  | 0.002 | -0.003
Hearing Loss | -0.239 | 0.000 | -0.341 | -0.068 |  | 0.003 | -0.002
Visaul Impairment | 0.012 | 0.000 | -0.358 | -0.001 |  | 0.001 | 0.011
Autistic | 0.012 | -0.185 | -0.336 | -0.017 |  | 0.059 | 0.115
Blind | -0.316 | -0.445 | -0.264 | -0.017 |  | 0.020 | -0.001
Deaf | 0.012 | -0.337 | -0.305 | -0.018 |  | 0.055 | 0.067
Mentally Handicapped | 0.012 | -0.100 | -0.154 | -0.010 |  | 0.167 | 0.253
Physically Handicapped | 0.012 | -0.012 | -0.188 | -0.008 |  | 0.014 | 0.067
Table 10: ScoreSense value achieved by each model for individual terms present in PWD:C and PWD:SD group. The value shows the mean score difference obtained when that individual term was added to a sentence. The value depicts how sensitive a model is to words pertaining to a given group. Figure 1: Sentiment score achieved by disability group for all the models in form of a heatmap. | PWD:C | PWD:SD | PWoD | NRMA
---|---|---|---|---
T1 | -0.916 | -0.941 | 0.951 | 0.981
T2 | -0.545 | 0.185 | 0.998 | 0.999
T3 | -0.995 | -0.997 | 0.198 | 0.199
T4 | -0.995 | -0.998 | 0.602 | 0.612
T5 | -0.024 | 0.874 | 0.984 | 0.997
T6 | -0.627 | -0.578 | -0.375 | -0.305
T7 | -0.437 | -0.410 | -0.123 | -0.163
T8 | -0.313 | -0.283 | -0.196 | -0.140
T9 | -0.312 | -0.194 | -0.157 | -0.074
T10 | -0.568 | -0.503 | -0.309 | -0.392
Table 11: Mean sentiment performance of the DistilBERT sentiment analysis
model to corresponding disability facet groups.