# Testing exchangeability by pairwise betting

Aytijhya Saha  Indian Statistical Institute, Kolkata, India. Email:
<EMAIL_ADDRESS>Aaditya Ramdas  Carnegie Mellon University,
Pittsburgh, USA. Email<EMAIL_ADDRESS>
###### Abstract

In this paper, we address the problem of testing exchangeability of a sequence
of random variables, $X_{1},X_{2},\cdots$. This problem has been studied under
the recently popular framework of _testing by betting_. But the mapping of
testing problems to game is not one to one: many games can be designed for the
same test. Past work established that it is futile to play single game betting
on every observation: test martingales in the data filtration are powerless.
Two avenues have been explored to circumvent this impossibility: betting in a
reduced filtration (wealth is a test martingale in a coarsened filtration), or
playing many games in parallel (wealth is an e-process in the data
filtration). The former has proved to be difficult to theoretically analyze,
while the latter only works for binary or discrete observation spaces. Here,
we introduce a different approach that circumvents both drawbacks. We design a
new (yet simple) game in which we observe the data sequence in pairs. Despite
the fact that betting on individual observations is futile, we show that
betting on pairs of observations is not. To elaborate, we prove that our game
leads to a nontrivial test martingale, which is interesting because it has
been obtained by shrinking the filtration very slightly. We show that our test
controls type-1 error despite continuous monitoring, and achieves power one
for both binary and continuous observations, under a broad class of
alternatives. Due to the shrunk filtration, optional stopping is only allowed
at even stopping times, not at odd ones: a relatively minor price. We provide
a wide array of simulations that align with our theoretical findings.

##  1 INTRODUCTION

A sequence of random variables $\\{X_{t}\\}_{t\geq 1}$ is exchangeable if and
only if for every $t$ and every permutation $\sigma$ of the first $t$ indices,
the joint distribution of $(X_{1},\cdots,X_{t})$ is same as the joint
distribution of $(X_{\sigma(1)},\cdots,X_{\sigma(t)})$. Suppose that we
sequentially observe a series of random variables $X_{1},X_{2},\cdots$ one by
one. Consider the fundamental problem of testing if our data form an
exchangeable sequence:

$H_{0}:X_{1},X_{2},\cdots\text{ are exchangeable.}$

From a single sequence of data, one cannot distinguish whether the data is iid
(independent and identically distributed) or exchangeable [Ramdas et al.,
2022], and so one can equivalently view this paper as designing a test for the
iid assumption:

$H^{\prime}_{0}:X_{1},X_{2},\cdots\text{ are iid.}$

We design a new sequential test for $H_{0}$ or $H_{0}^{\prime}$, establish its
consistency in both binary and continuous settings, primarily focusing on
first-order Markov and AR(1) alternatives respectively, and prove that its
“growth rate” asymptotically matches that of an oracle that knows the ground
truth. Using these as building blocks, we then show that our test is also
consistent against a much more general class of alternatives.

The vast majority of theoretical results in machine learning heavily rely on
the exchangeability assumption, or the stronger iid assumption. These methods
may encounter significant challenges when this assumption is violated (for
example due to Markovian dependence between the data), underscoring the
importance of rigorously testing data for its exchangeability.

The current paper seeks to add a new method of testing exchangeability based
on _pairwise betting_ to the two (recent) methods that are known so far, which
are based on conformal prediction [Vovk, 2021] and universal inference [Ramdas
et al., 2022]. The former has proven difficult to analyze and there is
currently no theoretical guarantee of consistency against any class of
alternatives, while the latter is applicable only for a sequence of binary
observations (or a small discrete alphabet). What distinguishes our approach
is its applicability to general observation spaces (like the former approach),
while we establish theoretical guarantees like consistency in both binary and
continuous cases against a broad class of alternatives.

The overarching technical umbrella that ties together all three of the above
solutions is that they stem from constructing “test martingales” (or, more
generally, “e-processes”), which can be interpreted as wealth of a gambler
playing a stochastic game (or, for e-processes, many games in parallel)
[Ramdas et al., 2023]. Going further with such a game-theoretic language, all
3 methods can be thought of as instances of the principle of “testing by
betting”, which we summarize below.

##### Testing by betting.

In order to test a hypothesis, one designs a game of chance which has two
properties. If the null hypothesis is true, the game rules must be such that
no gambler (starting with one dollar) can systematically make money, meaning
that their wealth is a nonnegative martingale (defined later): nonnegative
because they cannot bet more than they have, and martingale because the wealth
remains constant in expectation and thus it is unlikely that they will ever
multiply their wealth by a large amount (in other words, they’re playing
roulette). More generally, the wealth is allowed to be a nonnegative _super_
martingale under the null, which means it can decrease in expectation.
However, if the null hypothesis is false, the game rules must allow smart
gamblers to multiply their wealth exponentially. The achieved exponent, or the
average expected logarithm of the wealth (defined formally soon), is defined
as the “rate of growth” of wealth. The optimal betting strategy is one which
maximizes the rate of growth of wealth under the alternative.

For testing a simple null hypothesis (that is, the null hypothesis is a single
distribution) against a simple alternative, testing by betting is very
straightforward. The optimal bet is simply given by a likelihood ratio of the
alternative to the null [Shafer, 2021]. However, for composite null hypotheses
like our $H_{0}$, and composite alternatives like $H_{1}$, there is no unique
translation of the testing problem to a game. There are many games that one
could write down that test such nulls, and each of them permits different
betting strategies with different rates of growth of wealth. It appears to be
difficult to apriori determine which games’ optimal wealth is the “best” one.

A further nuance is the following key fact: for some nulls like our $H_{0}$, a
single game in which one observes a single data point in each round, provably
does not suffice to test the null because the constraints imposed by the game
are too strong. [Ramdas et al., 2022] prove that every nonnegative
(super)martingale in such a game is constant or decreasing (zero rate of
growth).

There are two options to circumvent the aforementioned negative result: (i)
one must work in a reduced/coarsened filtration, which amounts to throwing
some information away or restricting how much information is released, or (ii)
one must play many games in parallel, each one against a different subset of
the null hypothesis, and be judged on the minimum wealth across all games;
this minimum wealth is no longer a nonnegative supermartingale, and is called
an “e-process” (defined formally below). It turns out that the conformal
strategy [Vovk, 2021] takes route (i), while the universal inference strategy
[Ramdas et al., 2022] takes route (ii), and this distinction is discussed
further in the latter paper (and a bit more in the current paper).

The main novelty in our work is the consideration of a different betting game
under route (i), which is applicable to a general observation space. The
wealth process produced is indeed a nonnegative martingale, except in a (very
slightly) reduced filtration, as explained later. Our solution processes data
in pairs, and we will construct an exact e-value in each round of the game.
E-values are the building block for nonnegative martingales: our wealth
process is simply a product of these e-values, and will be a nonnegative
martingale under $H_{0}$. In recent years, e-values have emerged as a
promising alternative to p-values for handling such problems ([Grünwald et
al., 2024, Vovk and Wang, 2021, Ramdas et al., 2023]). Below, we provide a
concise technical overview of the key concepts and essentials in this rapidly
evolving field.

##### E-process.

Consider a nonnegative sequence of adapted random variables
$E\equiv\\{E_{t}\\}_{t\geq 0}$ and let $H_{0}$, the null hypothesis, be a set
of distributions. We call $E$ as an e-process for $H_{0}$, if

$\mathbb{E}_{\mathbb{P}}[E_{\tau}]\leq 1,\text{ for all stopping times
}\tau,\text{ for all }\mathbb{P}\in H_{0}$ (1)

Large values of the e-process encode evidence against the null. (Ideally, the
evidence $E$ should increase to infinity under $H_{1}$, almost surely.)
Further, suppose we stop and reject the null at the stopping time

$\tau_{\alpha}=\inf\left\\{t\geq 1:E_{t}\geq\frac{1}{\alpha}\right\\}.$ (2)

This rule results in a level $\alpha$ sequential test, meaning that if the
null is true, the probability that it ever stop falsely rejects the null is at
most $\alpha$. This is easily seen by applying Markov’s inequality to the
stopped e-process $E_{\tau_{\alpha}}$ (or, equivalently, Ville’s inequality
[Howard et al., 2020, Lemma 1]).

##### Test Martingale.

An integrable process $M\equiv\\{M_{t}\\}$ that is adapted to a filtration
$\mathscr{F}\equiv\\{\mathscr{F}_{t}\\}_{t\geq 0}$, is called a _martingale_
for $\mathbb{P}$ with respect to filtration $\mathscr{F}$ if

$\mathbb{E}_{\mathbb{P}}[M_{t}\mid\mathscr{F}_{t-1}]=M_{t-1}$ (3)

for all $t\geq 1$. $M$ is called a _test martingale_ for $H_{0}$ if it is a
martingale for every $\mathbb{P}\in H_{0}$, and if it is non-negative with
$M_{0}=1$. Game-theoretically, a test martingale for $\mathbb{P}$ is the
wealth process of a gambler who sequentially bets against $H_{0}$, starting
with initial wealth of $1$. The optional stopping theorem implies that for
_any_ stopping time $\tau$ and any $P\in H_{0}$, we have
$\mathbb{E}_{\mathbb{P}}[M_{\tau}]\leq 1$. Thus, if $M$ is a test martingale
for $H_{0}$, it is also an e-process for $H_{0}$.

An e-process (or test martingale) is called consistent for $H_{1}$, if
$\lim_{t\to\infty}M_{t}=\infty$ almost surely for any $\mathbb{P}\in H_{1}$,
meaning that under the alternative, it accumulates infinite evidence against
the null in the limit. Usually, the evidence grows exponentially, so the
“growth rate” of $M$ is defined as $\inf_{\mathbb{P}\in
H_{1}}\lim_{t\to\infty}\mathbb{E}_{P}[\log M_{t}]/t$. A positive growth rate
implies consistency.

##### Betting score.

We call the factor by which the gambler multiplies the money he risks at
$t$-th round of betting as the _betting score_ $B_{t}$. $B_{t}$ is an e-value,
meaning that it has expectation at most 1 under $H_{0}$. Note that,
$M_{t}=M_{t-1}\times B_{t}=\prod_{i=1}^{t}B_{t}$. Hence, betting scores can be
viewed as building blocks of test martingales.

Table 1: Comparing our pairwise betting with the universal inference e-process
[Ramdas et al., 2022] and the conformal test martingale [Vovk, 2021].

|  Applicable to general observation spaces |  Optional stopping in the data filtration |  Provably Consistent with growth rate analysis
---|---|---|---
Pairwise betting |  ✓ |  ✗ |  ✓
Universal inference |  ✗ |  ✓ |  ✓
Conformal inference |  ✓ |  ✗ |  ✗

##### Related Work.

Sequential hypothesis testing has a long-standing history, beginning with the
sequential probability ratio test of [Wald, 1945]. However, while the basic
theory holds for parametric hypotheses, it is often inadequate in the face of
nonparametrically defined composite nulls and alternatives. More recently, the
“testing by betting” methodology [Shafer and Vovk, 2019, Shafer, 2021] has led
to a “game-theoretic” approach to sequential hypothesis testing that has shown
promise for nonparametric nulls [Shekhar and Ramdas, 2023, Podkopaev et al.,
2023, Waudby-Smith and Ramdas, 2023].

One approach for testing exchangeability relies on conformal prediction [Vovk
et al., 2003, Fedorova et al., 2012, Vovk, 2021, Vovk et al., 2022]. The core
idea implicitly replaces the canonical filtration with a coarser filtration
formed by the independent conformal p-values in each round. These are
converted to e-values by “calibration”, which are multiplied to form a test
martingale for testing $H_{0}$. However, it is worth noting that the
consistency (and growth rate) of conformal testing remains theoretically
unproven.

On the other hand, [Ramdas et al., 2022] approaches the problem of testing
exchangeability by using universal inference [Wasserman et al., 2020] to
derive an e-process for $H_{0}$, although this method is only suitable for
binary (or small, discrete alphabet) data sequences. It is unclear how to
extend it to more general observation spaces.

Our approach circumvents the limitations of these existing methods: it comes
with provable growth rate guarantees unlike conformal testing, and it applies
to any observation space unlike the universal e-process. Table 1 summarizes
the comparison.

##### Paper outline.

The rest of the paper is organized as follows. In Section 2, we construct a
pairwise betting game for testing exchangeability. More precisely, Subsection
2.1 presents a test designed for binary data sequence and demonstrates its
power against the natural class of first-order Markov alternatives. We also
extend it to a larger class of alternatives. Then, in Subsection 2.2, we
develop a test for the continuous case. Section 3 presents a comprehensive set
of simulation studies that validate our theoretical findings. This article is
concluded in Section 5, following Section 4, which provides a discussion on
the key aspects of our approach. All proofs and relevant mathematical details
are provided in the Supplementary Materials.

##  2 PAIRWISE BETTING

We begin here with the binary case for simplicity. The idea of pairwise
betting readily extends from binary to any general observation space, offering
versatility, and we get to this later.

Given a binary sequence of observations, it might seem intuitive to consider a
betting game where a gambler places bets on individual data points in each
round. However, as demonstrated by [Ramdas et al., 2022], this game results in
a powerless test. To overcome this challenge, we design a game that reveals
data in pairs.

In each odd step $t$, nature tells us the unordered set of the $t$-th and
$(t+1)$-th observations. Based on this information (and all past
observations), we bet on the order in which they are observed. It turns out
that _the composite null hypothesis collapses to a point null, when we
condition on the unordered pair_.

For example, suppose that nature reveals the observations to be $\\{0,1\\}$,
but we don’t know whether the order was 01 or 10. Under the exchangeable or
iid null, both of these are equally likely (and knowing previous observations
gives no further information), so the null is simply a Bernoulli(0.5) for the
two possibilities. However, under a Markovian alternative, one of them is more
likely than the other (which one is more likely depends on the past, which we
know), and we can use this information to bet. We bet by invoking the
observations of [Shafer, 2021], who proved that for a point (conditional)
null, the optimal bet is the likelihood ratio of the (conditional) alternative
to the null.

Of course, when we start out, we don’t know the alternative (the true Markov
model, or its implied probabilities for the observed pair) and so our betting
is noisy. A pragmatic strategy is to bet using a maximum likelihood estimate
(regularized or smoothed, if needed) of the alternative based on the first
$t-1$ observations which have been revealed to us. As we learn the true
alternative, our betting becomes more accurate and we can provably make money,
as argued formally below. This is known as the plug-in method [Waudby-Smith
and Ramdas, 2023, Ramdas et al., 2023], because we simply plug in empirical
estimates of unknown parameters into our alternative model when we bet.

Algorithm 1 contains an overview of pairwise betting.

Input : Sequence of observations $x_{1},x_{2},\cdots$

output : Test Martingale $M_{2},M_{4},\cdots$

1 $M_{2}=1$;

2 for  _$t=3,5,\cdots$_ do

3 if  _$x_{t}=x_{t+1}$_ then

4 $M_{t+1}=M_{t-1}$

5 end if

6

7 else

8 $\mathbf{Z_{t}}:=(X_{t},X_{t+1})$;

9 $E_{t}:=$ Event that either $\mathbf{Z_{t}}=(x_{t},x_{t+1})$ or
$\mathbf{Z_{t}}=(x_{t+1},x_{t})$;

10 $\mathbf{x^{t}}:=(x_{1},\cdots,x_{t})$;

11
$L_{t}:=\mathbb{P}_{H_{1}}\left[\mathbf{Z_{t}}=(x_{t},x_{t+1})|\mathbf{\mathbf{x^{t-1}}},E_{t}\right]$;

12

13 Estimate $L_{t}$ by $\hat{L}_{t}$, based on $\mathbf{\mathbf{x^{t-1}}}$;

14 $\hat{B}_{t+1}:=2\hat{L}_{t}$;

15 $M_{t+1}=M_{t-1}\times\hat{B}_{t+1}$;

16 end if

17

18 end for

Algorithm 1 Pairwise Betting

Next, our objective is to formulate and analyze our test for two different
scenarios: first, we concentrate on the binary case, with a focus on a first
order Markov alternative, and second, we shift to the continuous case, with an
emphasis on an AR(1) alternative.

###  2.1 Test for Binary Observations

Suppose, we have a sequence of binary random variables $X_{1},X_{2},\cdots$.
The realization of the random variables are denoted as $x_{1},x_{2},\cdots$.
We primarily focus on first-order Markov alternative, i.e,
$\mathbb{P}[X_{t+1}|X_{t},\cdots,X_{1}]=\mathbb{P}[X_{t+1}|X_{t}]$, for all
$t\geq 1$.

We consider a betting game, starting with an initial wealth $M_{0}=M_{2}=1$.
Define, $\mathbf{Z_{t}}=(X_{t},X_{t+1})$. At each odd time step $t$, nature
tells us the unordered set of the $t$ th and $(t+1)$ th observations. If it is
either $(0,0)$ or $(1,1)$, no betting occurs in this case. Otherwise, we place
bets on $\mathbf{Z_{t}}$, according to the likelihood ratio, conditioned on
the observed values of $\mathbf{X^{t-1}}:=(X_{1},\cdots,X_{t-1})$ and the
event that either $\mathbf{Z_{t}}=(0,1)$ or $\mathbf{Z_{t}}=(0,1)$ (denote
this event as $E_{t}$) and then nature unveils the observed value of
$\mathbf{Z_{t}}$. So, the conditional likelihood under $H_{0}$ is

$\mathbb{P}_{H_{0}}(\mathbf{Z_{t}}=(x_{t},x_{t+1})|\mathbf{X^{t-1}}=\mathbf{x^{t-1}},E_{t})=\frac{1}{2},$
(4)

since (1,0) and (0,1) are equally likely under $H_{0}$. For $t=3,5,\cdots$,
the conditional likelihood under $H_{1}$ is

$\mathbb{P}_{H_{1}}(\mathbf{Z_{t}}=(x_{t},x_{t+1})|\mathbf{X^{t-1}}=\mathbf{x^{t-1}},E_{t})=\frac{{p}_{x_{t}|x_{t-1}}{p}_{x_{t+1}|x_{t}}}{{p}_{x_{t}|x_{t-1}}{p}_{x_{t+1}|x_{t}}+{p}_{x_{t+1}|x_{t-1}}{p}_{x_{t}|x_{t+1}}},$
(5)

where ${p}_{i|j}$ is the transition probability from $j$ to $i$ of the
underlying Markov model. Then, the betting score at $\frac{t+1}{2}$th round of
betting is the likelihood ratio of the (conditional) alternative (Equation
(5)) to the null (which is $\frac{1}{2}$). But, in a practical situation, we
typically lack knowledge of the true transition probabilities. Therefore, it
becomes necessary to estimate them. One viable option is to replace
${p}_{i|j}$ by its maximum likelihood estimator (MLE) based on the first $t-1$
many observations (denote it by $\hat{p}_{i|j}$) in Equation (5). But, there
could be other choices too (see Remark 2.2). We do not bet in the first round.
So, $\hat{B}_{2}=1$. And betting score at $\frac{t+1}{2}$th round
($t=3,5,\cdots$) of betting is

$\hat{B}_{t+1}=\mathbbm{1}_{E^{c}_{t}}+\frac{2\hat{p}_{X_{t}|X_{t-1}}\hat{p}_{X_{t+1}|X_{t}}}{\hat{p}_{X_{t}|X_{t-1}}\hat{p}_{X_{t+1}|X_{t}}+\hat{p}_{X_{t+1}|X_{t-1}}\hat{p}_{X_{t}|X_{t+1}}}\mathbbm{1}_{E_{t}}.$
(6)

Thus, the bettor’s wealth after $\frac{t+1}{2}$ rounds of betting is

$M_{t+1}=M_{t-1}\times\hat{B}_{t+1}=\prod_{i=1}^{{(t+1)}/{2}}\hat{B}_{2i};\leavevmode\nobreak\
t=3,5,\cdots.$ (7)

It is easy to check that $\\{M_{2},M_{4},\cdots\\}$ is a test martingale for
$H_{0}$. Hence, recalling (2),

$\tau^{*}=\inf\\{t:M_{t}\geq 1/\alpha\\}$ (8)

is the stopping time at which we reject the null, yielding a level $\alpha$
sequential test. It is worth noting that due to the shrunk filtration,
optional stopping is only permissible at even stopping times, not at odd ones.

####  2.1.1 Consistency of the test

In this subsection, we present the main theorem characterizing the consistency
and the rate of convergence of our test against first order Markov
alternative. Within the class of first-order Markov chains, the special case
of iid Bernoulli data is characterized by the restriction $p_{1|0}=p_{1|1}$.
Therefore, our test achieves power $1$ against the first-order Markov
alternative, as established by the following theorem. Below, $j^{c}$ denotes
the complement of $j$, i.e. $j^{c}=1$ when $j=0$, and $j^{c}=0$ when $j=1$.

######  Theorem 2.1.

Under first order Markov alternative, assume that $p_{0|1},p_{1|0}\neq 0$ or
$1$. Then, $\frac{\log(M_{2n})}{2n}\to r$ almost surely as $t\to\infty$, where

$r=\frac{1}{2}\sum_{i=0}^{1}\sum_{j=0}^{1}\log\left(\frac{2{p}_{j|i}{p}_{j^{c}|j}}{{p}_{j|i}{p}_{j^{c}|j}+{p}_{j^{c}|i}{p}_{j|j^{c}}}\right)p_{i}p_{j|i}p_{j^{c}|j}.$

Further, $r=0$ if $p_{1|0}=p_{1|1}$, and $r>0$ otherwise.

[See Section A.1 of Supplementary for the proof]

######  Remark 2.2.

It’s important to note that the estimator of ${p}_{j|j}$, that we plugged in
(5) does not necessarily have to be the maximum likelihood estimator (MLE).
The Theorem 2.1 holds for any strongly consistent estimator, $\hat{p}_{j|j}$
of the transition probabilities, ${p}_{j|j}$. For instance, one can opt for
the Bayesian maximum aposteriori (MAP) estimator, with a uniform prior, as an
alternative to the MLE.

Theorem 2.1 ensures the consistency of our sequential level $\alpha$ test
(defined in (7)), by showing that our test martingale $\\{M_{2n}\\}_{n\geq 1}$
increases to infinity exponentially fast in $n$, under first order Markov
alternatives. Next, we extend and generalize this result.

####  2.1.2 Generalization to a larger class of alternatives

Although our primary focus is on first-order Markov alternatives, we show that
our test martingale is consistent for much more general alternatives. Consider
any binary sequence for which the following almost sure limits exist:

$\displaystyle\alpha:=\lim_{t\to\infty}\frac{n_{1|1}(t)}{t},\quad\beta:=\lim_{n\to\infty}\frac{n_{0|0}(t)}{t}$
(9a)
$\displaystyle\gamma:=\lim_{t\to\infty}\frac{n_{1|0}(t)}{t}=\lim_{t\to\infty}\frac{n_{0|1}(t)}{t},$
(9b) $\displaystyle
p_{i,j,j^{c}}:=\lim_{t\to\infty}\frac{n_{j^{c}|j|i}(t)}{t},\text{ for
}i,j\in(0,1).$ (9c)

where $n_{i|j}(t)$ denotes the number of $i$ following $j$ up to time $t$ and
$n_{i|j|k}(t)$ represents the count of instances where $i$ follows $j$
following $k$ up to time $t$. Define,

$\displaystyle p_{1|1}:=\frac{\alpha}{\alpha+\gamma},\leavevmode\nobreak\
p_{0|1}:=\frac{\gamma}{\alpha+\gamma},\leavevmode\nobreak\
p_{1|0}:=\frac{\gamma}{\beta+\gamma},\leavevmode\nobreak\
p_{1|1}:=\frac{\beta}{\beta+\gamma}.$

Note that for first-order Markov, these parameters are nothing but the
transition probabilities. Let us also define the following constants:

$a=\frac{p_{1,1,0}}{p_{1,1,0}+p_{0,1,0}},\leavevmode\nobreak\
b=\frac{p_{1,0,1}}{p_{1,0,1}+p_{0,0,1}}.$

######  Theorem 2.3.

For any binary data sequence, suppose that the limits $\alpha,\beta,\gamma$
and $p$ defined in (9) exist. Then, $\frac{\log(M_{2n})}{2n}\to r^{\prime}$
almost surely as $n\to\infty$, where

$r^{\prime}=\frac{1}{2}\sum_{i=0}^{1}\sum_{j=0}^{1}\log\left(\frac{2{p}_{j|i}{p}_{j^{c}|j}}{{p}_{j|i}{p}_{j^{c}|j}+{p}_{j^{c}|i}{p}_{j|j^{c}}}\right)p_{i,j,j^{c}}$

is strictly greater than $0$ if $(2p_{0|1}-1)(a+p_{0|1}-1)\geq
0,(2p_{1|0}-1)(b+p_{1|0}-1)\geq 0$ and $p_{1|0}\neq p_{1|1}$.

[See Section A.2 of Supplementary for the proof]

######  Remark 2.4.

It is straightforward to verify that for a first-order Markov,
$p_{i,j,j^{c}}=p_{i}p_{j|i}p_{j^{c}|j}$, which implies that $r=r^{\prime}$.
Furthermore, for this particular case, it can be easily shown that $a=p_{0|1}$
and $b=p_{1|0}$ leading trivially to the inequalities
$(2p_{0|1}-1)(a+p_{0|1}-1)=(2p_{0|1}-1)^{2}\geq 0$ and
$(2p_{1|0}-1)(b+p_{1|0}-1)=(2p_{1|0}-1)^{2}\geq 0$. Hence, Theorem 2.3 can be
regarded as a strict generalization of Theorem 2.1.

###  2.2 Test for the continuous case

To show the power and versatility of our test, we now extend it to a sequence
of continuous random variables.

Suppose, we observe $X_{1},X_{2},\cdots$ from some continuous distribution. It
is worth noting that our test is versatile enough to handle a broad spectrum
of scenarios. But as an illustrative example, we primarily focus on a
stationary Gaussian AR(1) alternative, i.e,

$\displaystyle H_{1}$ $\displaystyle:X\text{ is a stationary AR(1) process,
with }$ $\displaystyle X_{t+1}=aX_{t}+\varepsilon_{t+1},\leavevmode\nobreak\
\leavevmode\nobreak\ t=1,2,\cdots,\text{ where }$
$\displaystyle\varepsilon_{t}\stackrel{{\scriptstyle
i.i.d}}{{\sim}}N(0,\sigma^{2});a\text{ and }\sigma\text{ are unknown.}$

Using the same idea that we employed in the binary case, we start with an
initial wealth $W_{0}=W_{2}=1$, and in each odd step $t$, nature tells us the
unordered set of the $t$-th and $(t+1)$-th observations. (We don’t bet in the
first round because we have not seen any data.) In the continuous case, the
probability that $X_{t}=X_{t+1}$ is zero. So, we now always place bets on
$\mathbf{Z_{t}}$, for each odd $t$. These bets are determined by the
likelihood ratio, conditioned on the observed values of
$\mathbf{X^{t-1}}:=\\{X_{1},\cdots,X_{t-1}\\}$ and the event that either
$\mathbf{Z_{t}}=(x_{t},x_{t+1})$ or $\mathbf{Z_{t}}=(x_{t+1},x_{t})$ (denote
this event as $E_{t}$) and then nature unveils the observed value of
$\mathbf{Z_{t}}$. Let us denote $E_{t}$ as the event that $\mathbf{Z_{t}}$ is
either $(x_{t},x_{t+1})$ or $(x_{t+1},x_{t})$. So, the conditional likelihood
under $H_{0}$ is

$\mathbb{P}_{H_{0}}(\mathbf{Z_{t}}=(x_{t},x_{t+1})|\mathbf{X^{t-1}}=\mathbf{x^{t-1}},E_{t})=\frac{1}{2},$
(10)

since $(x_{t},x_{t+1})$ and $(x_{t+1},x_{t})$ are equally likely under
$H_{0}$. It is easy to obtain that the conditional likelihood under the AR(1)
alternative is

$\displaystyle\mathbb{P}_{H_{1}}(\mathbf{Z_{t}}=(x_{t},x_{t+1})|\mathbf{X^{t-1}}=\mathbf{x^{t-1}},E_{t})=\frac{f(x_{t-1},x_{t},x_{t+1})}{f(x_{t-1},x_{t},x_{t+1})+f(x_{t-1},x_{t+1},x_{t})},$
$\text{ where
}f(x,y,z):=\frac{1}{2\pi\sigma^{2}}e^{-\frac{1}{2\sigma^{2}}(y-ax)^{2}-\frac{1}{2\sigma^{2}}(z-ay)^{2}}.$

Then, the betting score (for Oracle) at $\frac{t+1}{2}$th round is

$S_{t+1}=\frac{2f(X_{t-1},X_{t},X_{t+1})}{f(X_{t-1},X_{t},X_{t+1})+f(X_{t-1},X_{t+1},X_{t})}.$
(11)

Recall that we don’t bet at $t=1$, so $S_{2}=1$. For practical use, we need to
estimate $a$ and $\sigma^{2}$. One viable option is to estimate $f$ by
$\hat{f}_{t-1}$, which is obtained by replacing the model parameter $a$ by its
least squares estimator,
$\hat{a}_{t-1}=\sum_{i=2}^{t-1}X_{i}X_{i-1}/\sum_{i=1}^{t-2}X_{i}^{2}$ and
$\sigma^{2}$ by
$\hat{\sigma}^{2}_{t-1}=\frac{1}{t-2}\sum_{i=2}^{t-1}(X_{i}-\hat{a}_{t-1}X_{i-1})^{2},$
for $t=3,5,\cdots$. So, the bet at $\frac{t+1}{2}$th round ($t=3,5,\cdots$) is

$\hat{S}_{t+1}=\frac{2\hat{f}_{t-1}(X_{t-1},X_{t},X_{t+1})}{\hat{f}_{t-1}(X_{t-1},X_{t},X_{t+1})+\hat{f}_{t-1}(X_{t-1},X_{t+1},X_{t})}.$
(12)

Thus, the bettor’s wealth after $\frac{t+1}{2}$ rounds of betting is

$W_{t+1}=W_{t-1}\times\hat{S}_{t+1}=\prod_{i=2}^{{(t+1)}/{2}}\hat{S}_{2i}.$
(13)

It is easy to check that $\\{W_{2},W_{4},\cdots\\}$ is a test martingale,
(with respect to a shrunk filtration) for testing exchangeability. Recalling
(2),

$\tau^{\prime}=\inf\\{t:W_{t}\geq 1/\alpha\\}$ (14)

is a level $\alpha$ sequential test. As before, due to the shrunk filtration,
optional stopping is only permissible at even stopping times, not at odd ones.

####  2.2.1 Consistency of the test

In this subsection, we present a crucial result concerning the consistency of
our test with AR(1) alternative. It’s worth noting that, within the class of
AR(1), the special case of iid $N(0,\sigma^{2})$ is characterized by the
restriction $a=0$. Therefore, our test is consistent against the AR(1)
alternative, as established by the following theorem.

######  Theorem 2.5.

Let, $\\{X_{t}\\}_{t}$ be a stationary Gaussian AR(1) process. Then,

$\frac{\log(W_{2n})}{2n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}r^{*},\text{ as }n\to\infty,$

where $r^{*}=\frac{1}{2}\mathbb{E}\left(\log\left(S_{4}\right)\right)\geq 0$
and equality holds if and only if $a=0$ (in which case the null would be
true).

[See Section A.3 of Supplementary for the proof]

In essence, Theorem 2.5 ensures the consistency of our sequential level
$\alpha$ test (defined in (14)), by revealing that our test martingale
$\\{W_{2n}\\}_{n\geq 1}$ increases to infinity exponentially fast in $n$,
under AR(1) alternative. Next, we extend and generalize this result.

####  2.2.2 Generalization to a larger class of alternatives

Although our primary focus is on AR(1) alternatives, we show that our test is
consistent for much more general alternatives.

######  Theorem 2.6.

Let $\\{X_{t}\\}_{t\geq 1}$ be an ergodic process. Then,

$\frac{\log(W_{2n})}{2n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}r^{*},\text{ as }n\to\infty,$

where $r^{*}=\frac{1}{2}\mathbb{E}\left(\log\left(S_{4}\right)\right)\geq 0$,
which is strictly positive whenever $a\neq 0$ and
$\mathbb{E}\left(\frac{1}{S_{4}}\right)\leq 1$.

[See Section A.4 of Supplementary for the proof]

######  Remark 2.7.

It can be shown that under AR(1) model,
$\mathbb{E}\left(\frac{1}{S_{4}}\right)\leq 1$ holds true 111Indeed, note that
$S_{4}$ is just a simple likelihood ratio, which always satisfies that its
expectation is 1 under the null and its inverse has expectation 1 under the
alternative.. Hence, Theorem 2.6 can be regarded as a strict generalization of
Theorem 2.5.

##  3 EXPERIMENTAL RESULTS

We present results on both simulated and real data.

###  3.1 Simulation study for binary case

In this subsection, we investigate the performance of our test martingales for
the binary case and compare it with the universal inference [Ramdas et al.,
2022] and conformal inference (simple jumper algorithm) [Vovk, 2021, Vovk et
al., 2022].

##### No power against iid Bernoulli.

We conduct a sanity check to verify that our evidence measure does grow
against iid Bernoulli sources (which are exchangeable). Our experiments
encompass three specific cases: $\text{Bernoulli}(0.2)$,
$\text{Bernoulli}(0.5)$ and $\text{Bernoulli}(0.8)$. In all instances,
$\log(M_{t})$ does not grow with $t$; see Figure 1.

(a) Bernoulli(0.2)

(b) Bernoulli(0.5)

(c) Bernoulli(0.8)

Figure 1: Evolution of our pairwise betting ($\log M_{t}$), universal
inference ([Ramdas et al., 2022]) and conformal inference (simple jumper
algorithm, with rate = 0.1, 0.01, 0.001) ([Vovk, 2021]) under iid Bernoulli
models. This experiment is a sanity check: as expected, none of the evidence
processes grow up with time since the null is true.

(a) Markov(0.9,0.1)

(b) Markov(0.1,0.9)

(c) Markov(0.6,0.4)

(d) Markov(0.4,0.6)

Figure 2: Evolution of our pairwise betting process ($\log M_{t}$), universal
inference [Ramdas et al., 2022] and conformal inference (simple jumper
algorithm, with rate $J=0.1,0.01,0.001$) [Vovk, 2021] under Markov Models. The
black dotted lines are the lines with slope $r$ (Theorem 2.1), perfectly
predicts the evolution of our process.

##### Power against a Markov alternative.

The probability that the first observation is 1 is assumed $0.5$. In our
computational experiments, we explore four specific cases:
$\text{Markov}(0.4,0.6)$, $\text{Markov}(0.6,0.4)$, $\text{Markov}(0.1,0.9)$
and $\text{Markov}(0.9,0.1)$ (We use the notation
$\text{Markov}(\pi_{1|0},\pi_{1|1})$ for the probability distribution of a
Markov chain with the transition probabilities $\pi_{1|0}$ and $\pi_{1|1}$).
Figure 2 shows that our theoretical black dotted line perfectly predicts
practical performance, and also that in 3 out of the 4 plots, our method
outperforms the conformal inference approach (for which there are no
guarantees of consistency), and that although the universal inference approach
is better than ours, it does not apply to continuous data settings.

###  3.2 Simulation study for continuous case

We now investigate the performance of our test martingales for the continuous
case. We have drawn the first observation from the standard normal
distribution. Our computational experiments encompass five specific values of
the unknown parameter $a$ of AR(1) model with a known variance of the white
noise, $\sigma^{2}=1$. As illustrated in Figure 3, we observe that for $a=0$
(representing the iid normal case), the logarithm of our process does not grow
with time, whereas for $a=\pm 0.2,\pm 0.8$, the logarithm of our process grows
linearly with time.

Figure 3: The process $\log W_{t}$ for AR(1) model with five different choices
of the parameter $a$. Except for $a=0$ (when the null is true), $\log W_{t}$
grows linearly with time $t$, as predicted by our theory. Note that positive
and negative $a$ behave differently, as they should. When $a>0$, all terms are
positively correlated, and when $a<0$, the correlations between odd-spaced
terms is negative and even-spaced terms is positive. Figure 4: Accumulating
evidence against the individual hypotheses that the sequences of hourly
concentration of six air-pollutants are exchangeable.

###  3.3 Real data experiment

We conclude the empirical evaluation with an implementation of our method on
the Beijing Multi-Site Air-Quality Data [Chen, 2019], which contains hourly
observations of six main air pollutants over the time period from March 1,
2013 to February 28, 2017 at multiple sites in Beijing. For our analysis, we
focus on the time series data from the Aotizhongxin station. Figure 4, shows
the growth of $\log(W_{t})$ with $t$, which clearly indicates that the null
hypothesis can be safely rejected, for all these six sequences. This empirical
validation reaffirms the practical utility of our testing methodology in real-
world scenarios.

##  4 DISCUSSION

###  4.1 Versatility of Our Method

It is crucial to emphasize that in both binary and continuous cases, the
models we employed under the alternative only serve as a strategic aid for
betting. The model’s use does not impose any constraints on our $H_{0}$: it
just guides our betting in an attempt to prove the null false, but if the null
is true, the evidence cannot grow no matter what model we use.

The choice of a model is most impactful in terms of the power of the test. If
the model does not perfectly align with the underlying data generation
process, it may potentially reduce the power. However, it is essential to note
that our test is “safe” in the sense that it never compromises the control of
the type-1 error.

The two specific cases (first-order Markov and AR(1)) we considered in our
paper serve as illustrative examples for the sake of clarity and simplicity,
offering valuable insights into the testing process due to analytical
tractability of optimal bets and wealth growth rates. However, our method can
be _readily used in any other setting_. The conditional likelihood under null
is always $\frac{1}{2}$. So, the key requirement is the availability of a
conditional generative model that can be learned/updated online, to facilitate
the betting process.

###  4.2 Even and odd games

It is important to note that instead of betting in the odd time steps, as
described earlier, we could bet in the even time steps as well. And it may
initially seem that the average wealth of these two games might be a valid
measure of evidence against null, but this turns out to not be the case, as we
explain below.

Clearly, the same player cannot play both the games: betting relies on
uncertainty, and it’s meaningless to consider a game where the bettor wagers
on something already known to them. Once a bet has been placed on
$Z_{2t+1}=(X_{2t+1},X_{2t+2})$, and one has learned the outcome, it becomes
meaningless to bet on $Z_{2t+2}=(X_{2t+2},X_{2t+3})$ because $X_{2t+2}$ is
already known. One may think to not reveal the outcome of the first bet until
after the second bet is made, but this does not work because knowing
$X_{2t+1}$ is key to betting on $Z_{2t+2}$.

An additional intriguing observation is that the games corresponding to even
and odd times yield two different filtrations, which we denote as
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$, respectively. Both $\mathcal{F}_{1}$
and $\mathcal{F}_{2}$ represent coarsenings of the data filtration
($\mathcal{F}$) but in two different ways. If we denote the wealth processes
in these two games as $\\{M_{t}\\}_{t\geq 0}$ and $\\{N_{t}\\}_{t\geq 0}$,
respectively, they are test martingales with respect to $\mathcal{F}_{1}$ and
$\mathcal{F}_{2}$ respectively. Consequently, the object $T=\frac{M+N}{2}$ is
not a test martingale because it is neither adapted to $\mathcal{F}_{1}$ nor
to $\mathcal{F}_{2}$, and it doesn’t seem to be an e-process either. While it
is adapted to $\mathcal{F}$, it does not qualify as a test martingale with
respect to $\mathcal{F}$ (indeed, these do not exist.)

It is indeed intriguing to consider the average wealth obtained by two
independent, non-communicating players engaging in two different games with
nature. It may be interesting future work to investigate its properties.

##  5 CONCLUSION

Our paper introduces a novel approach for the fundamental question of
sequentially testing exchangeability, centered around a new (yet simple) idea
of pairwise betting, which leads to a nontrivial test martingale. Importantly,
our method is applicable to any general observation space and is amenable to
analytical study. We have provided a detailed analysis of our approach for
both binary and continuous cases, specifically focusing on Markov and AR(1)
alternatives (but extended to a broader class of alternatives), respectively,
for which we demonstrated the consistency of our approach and explored its
growth rate.

##  Appendix A MISSING PROOFS

Here, we present the formal proofs of the theorems stated and discussed in the
main paper. The key mathematical tool that we employ to establish these proofs
is the ergodic theorem [Billingsley, 1966].

###  A.1 Proof of Theorem 2.1

For $t\geq 2$, let us define $Y_{2t}=\\{X_{2t-2},X_{2t-1},X_{2t}\\}$,
$\hat{D}_{2t}=\log\hat{B}_{2t}$. So, we can write
$\log(M_{2n})=\sum_{t=2}^{n}\hat{D}_{2t}$.

Now, by using ergodic theorem, we can show that the MLE of the transition
probability from $i$ th state to $j$ th state, $\hat{p}_{j|i}$ is strongly
consistent for ${p}_{j|i}$, i.e,

$\hat{p}_{j|i}(t)\to{p}_{j|i},\text{ almost surely, as }t\to\infty,\text{ for
}i,j\in\\{0,1\\}.$ (15)

And since $X_{1},X_{2},\cdots$ is a Markov chain of first order,
$Y_{2},Y_{4},\cdots$ is also a Markov chain of first order. So, again by
ergodic theorem,

$\frac{1}{n-1}\sum_{t=2}^{n}\mathbbm{I}_{Y_{2t}=\\{i,j,{j}^{c}\\}}\to
p_{i}p_{j|i}p_{j^{c}|j},\text{ almost surely, as }n\to\infty,\text{ for
}i,j\in\\{0,1\\},$ (16)

where $p_{i}=\frac{p_{i|i^{c}}}{p_{i|i^{c}}+p_{i^{c}|i}}.$ is the stationary
probability of $i$th state. Now,

$\displaystyle\frac{1}{n-1}\sum_{t=2}^{n}\hat{D}_{2t}$
$\displaystyle=\frac{1}{n-1}\sum_{t=2}^{n}\log\left(\frac{2\hat{p}_{j|i}(2t)\hat{p}_{j^{c}|j}(2t)}{\hat{p}_{j|i}(2t)\hat{p}_{j^{c}|j}(2t)+\hat{p}_{j^{c}|i}(2t)\hat{p}_{j|j^{c}}(2t)}\right)\mathbbm{I}_{Y_{2t}=\\{i,j,{j}^{c}\\}}$
$\displaystyle=\frac{1}{n-1}\sum_{t=2}^{n}\left[\log\left(\frac{2\hat{p}_{j|i}(2t)\hat{p}_{j^{c}|j}(2t)}{\hat{p}_{j|i}(2t)\hat{p}_{j^{c}|j}(2t)+\hat{p}_{j^{c}|i}(2t)\hat{p}_{j|j^{c}}(2t)}\right)-\log\left(\frac{2{p}_{j|i}{p}_{j^{c}|j}}{{p}_{j|i}{p}_{j^{c}|j}+{p}_{j^{c}|i}{p}_{j|j^{c}}}\right)\right]\mathbbm{I}_{Y_{2t}=\\{i,j,{j}^{c}\\}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
+\log\left(\frac{2{p}_{j|i}{p}_{j^{c}|j}}{{p}_{j|i}{p}_{j^{c}|j}+{p}_{j^{c}|i}{p}_{j|j^{c}}}\right)\frac{1}{n-1}\sum_{t=2}^{n}\mathbbm{I}_{Y_{2t}=\\{i,j,{j}^{c}\\}}.$

The first term goes to $0$ (follows from (15) by first invoking continuous
mapping theorem to conclude each term inside the bracket converges a.s. to
zero from which it also follows that running average converge to 0) and the
second term converges to
$\log\left(\frac{2{p}_{j|i}{p}_{j^{c}|j}}{{p}_{j|i}{p}_{j^{c}|j}+{p}_{j^{c}|i}{p}_{j|j^{c}}}\right)p_{i}p_{j|i}p_{j^{c}|j}$
(follows from (16)) almost surely. Hence,

$\frac{1}{n-1}\sum_{t=2}^{n}\hat{D}_{2t}\to\sum_{i=0}^{1}\sum_{j=0}^{1}\log\left(\frac{2{p}_{j|i}{p}_{j^{c}|j}}{{p}_{j|i}{p}_{j^{c}|j}+{p}_{j^{c}|i}{p}_{j|j^{c}}}\right)p_{i}p_{j|i}p_{j^{c}|j},\text{
almost surely, as }n\to\infty,$

which implies, $\frac{\log M_{2n}}{2n}\to r$, almost surely, as $n\to\infty$,
where

$\displaystyle r=$
$\displaystyle\frac{1}{2}\sum_{i=0}^{1}\sum_{j=0}^{1}\log\left(\frac{2{p}_{j|i}{p}_{j^{c}|j}}{{p}_{j|i}{p}_{j^{c}|j}+{p}_{j^{c}|i}{p}_{j|j^{c}}}\right)p_{i}p_{j|i}p_{j^{c}|j}$
$\displaystyle=$
$\displaystyle\frac{p_{0|1}p_{1|0}}{2(p_{0|1}+p_{1|0})}\log\Bigg{(}\left(\frac{2(1-p_{0|1})}{1-p_{0|1}+p_{1|0}}\right)^{1-p_{0|1}}\left(\frac{2p_{0|1}}{1+p_{0|1}-p_{1|0}}\right)^{p_{0|1}}\left(\frac{2p_{1|0}}{1-p_{0|1}+p_{1|0}}\right)^{p_{1|0}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\times\left(\frac{2(1-p_{1|0})}{1+p_{0|1}-p_{1|0}}\right)^{1-p_{1|0}}\Bigg{)}$
$\displaystyle=$
$\displaystyle\frac{p_{0|1}p_{1|0}}{2(p_{0|1}+p_{1|0})}\Bigg{[}\log
4-(1-p_{0|1})\log\left(1+\frac{p_{1|0}}{1-p_{0|1}}\right)-{p_{1|0}}\log\left(1+\frac{1-p_{0|1}}{p_{1|0}}\right)$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
-(1-p_{1|0})\log\left(1+\frac{p_{0|1}}{1-p_{1|0}}\right)-{p_{0|1}}\log\left(1+\frac{1-p_{1|0}}{p_{0|1}}\right)\Bigg{]}.$

Since $\log$ is a concave function, we can use Jensen’s inequality to obtain

$r\geq\frac{p_{0|1}p_{1|0}}{p_{0|1}+p_{1|0}}[\log 4-(1-p_{0|1}+p_{1|0})\log
2-(1-p_{1|0}+p_{0|1})\log 2]=0,$

where the equality holds if and only if
$\frac{p_{1|0}}{1-p_{0|1}}=\frac{1-p_{0|1}}{p_{1|0}}$ and
$\frac{p_{1|0}}{1-p_{0|1}}=\frac{1-p_{0|1}}{p_{1|0}}$, which is equivalent to
$p_{1|0}=p_{1|1}$. ∎

###  A.2 Proof of Theorem 2.3

Note that, by definition of ${p}_{j|i}$ and $p_{i,j,j^{c}}$, we have

$\hat{p}_{j|i}(t)=\frac{{n}_{j|i}(t)}{{n}_{j|i}(t)+{n}_{j^{c}|i}(t)}=\frac{{n}_{j|i}(t)/t}{{n}_{j|i}(t)/t+{n}_{j^{c}|i}(t)/t}\to{p}_{j|i},\text{
almost surely, as }t\to\infty,\text{ for }i,j\in\\{0,1\\},$ (17)
$\frac{1}{n-1}\sum_{t=2}^{n}\mathbbm{I}_{Y_{2t}=\\{i,j,{j}^{c}\\}}\to
p_{i,j,j^{c}},\text{ almost surely, as }n\to\infty,\text{ for
}i,j\in\\{0,1\\}.$ (18)

Hence, by the same argument, as shown in the proof of Theorem 2.1, we have
$\frac{\log M_{n}}{2n}\to r^{\prime}$, almost surely, as $n\to\infty$, where

$\displaystyle 2r^{\prime}=$
$\displaystyle\sum_{i=0}^{1}\sum_{j=0}^{1}\log\left(\frac{2{p}_{j|i}{p}_{j^{c}|j}}{{p}_{j|i}{p}_{j^{c}|j}+{p}_{j^{c}|i}{p}_{j|j^{c}}}\right)p_{i,j,j^{c}}$
$\displaystyle=$ $\displaystyle
p_{1,1,0}\log\left(\frac{2(1-p_{0|1})}{1-p_{0|1}+p_{1|0}}\right)+p_{0,1,0}\log\left(\frac{2p_{0|1}}{1+p_{0|1}-p_{1|0}}\right)+p_{1,0,1}\log\left(\frac{2p_{1|0}}{1-p_{0|1}+p_{1|0}}\right)$
$\displaystyle+p_{0,0,1}\log\left(\frac{2(1-p_{1|0})}{1+p_{0|1}-p_{1|0}}\right)$
$\displaystyle=$ $\displaystyle(p_{1,1,0}+p_{0,1,0})\left[\log
2-\frac{p_{1,1,0}}{p_{1,1,0}+p_{0,1,0}}\log\left(1+\frac{p_{1|0}}{1-p_{0|1}}\right)-\frac{p_{1,1,0}}{p_{1,1,0}+p_{0,1,0}}\log\left(1+\frac{1-p_{0|1}}{p_{1|0}}\right)\right]$
$\displaystyle+(p_{1,0,1}+p_{0,0,1})\left[\log
2-\frac{p_{1,0,1}}{p_{1,0,1}+p_{0,0,1}}\log\left(1+\frac{p_{0|1}}{1-p_{1|0}}\right)-\frac{p_{0,0,1}}{p_{1,0,1}+p_{0,0,1}}\log\left(1+\frac{1-p_{1|0}}{p_{0|1}}\right)\right].$
$\displaystyle\geq$ $\displaystyle(p_{1,1,0}+p_{0,1,0})\left[\log
2-\log\left(1+\frac{ap_{0|1}^{2}+(1-a)(1-p_{0|1})^{2}}{p_{0|1}(1-p_{0|1})}\right)\right]$
$\displaystyle+(p_{1,0,1}+p_{0,0,1})\left[\log
2-\log\left(1+\frac{bp_{1|0}^{2}+(1-b)(1-p_{1|0})^{2}}{p_{1|0}(1-p_{1|0})}\right)\right]\leavevmode\nobreak\
\leavevmode\nobreak\ \text{(by using Jensen's inequality)}$ $\displaystyle=$
$\displaystyle(p_{1,1,0}+p_{0,1,0})\left[\log
2-\log\left(2+\frac{(2p_{0|1}-1)(a+p_{0|1}-1)}{p_{0|1}(1-p_{0|1})}\right)\right]$
$\displaystyle+(p_{1,0,1}+p_{0,0,1})\left[\log
2-\log\left(2+\frac{(2p_{1|0}-1)(b+p_{1|0}-1)}{p_{1|0}(1-p_{1|0})}\right)\right]$
$\displaystyle\geq$ $\displaystyle 0,\text{ when
}(2p_{0|1}-1)(a+p_{0|1}-1)\geq 0\text{ and }(2p_{1|0}-1)(b+p_{1|0}-1)\geq 0.$

Note that equality holds in the first inequality (which follows from Jensen’s
inequality) if and only if
$\frac{p_{1|0}}{1-p_{0|1}}=\frac{1-p_{0|1}}{p_{1|0}}$ and
$\frac{p_{1|0}}{1-p_{0|1}}=\frac{1-p_{0|1}}{p_{1|0}}$, which is equivalent to
$p_{1|0}=p_{1|1}$. Therefore, $r^{\prime}>0$ if $(2p_{0|1}-1)(a+p_{0|1}-1)\geq
0\text{ and }(2p_{1|0}-1)(b+p_{1|0}-1)\geq 0$ and $p_{1|0}\neq p_{1|1}$.

###  A.3 Proof of Theorem 2.5

Define, $C_{2t}=\log S_{2t}$, and $\hat{C}_{2t}=\log\hat{S}_{2t}$. So, we have
$\log(W_{2n})=\sum_{t=2}^{n}\hat{C}_{2t}$.

Note that
$C_{2t}=\log\left(\frac{2f(X_{2t-2},X_{2t-1},X_{2t})}{f(X_{2t-2},X_{2t-1},X_{2t})+f(X_{2t-2},X_{2t},X_{2t-1})}\right)$
is a continuous function of $X_{2t},X_{2t-1},X_{2t-2}$. Since, under the
alternative, $\\{X_{t}\\}_{t}$ is a stationary AR(1) process, it is an ergodic
process and so is the process $\\{C_{2t}\\}_{t}$. Now, using ergodic theorem,
we can directly say that

$\frac{1}{n-1}\sum_{t=2}^{n}C_{2t}\to\mathbb{E}(C_{4})=\mathbb{E}\log(S_{4}),\text{
almost surely as }n\to\infty.$ (19)

Also, using ergodic theorem, it can be shown that
$\hat{a}_{t-1}=\sum_{i=2}^{t-1}X_{i}X_{i-1}/\sum_{i=1}^{t-2}X_{i}^{2}\stackrel{{\scriptstyle
a.s}}{{\rightarrow}}a$ and
$\hat{\sigma}^{2}_{t-1}=\frac{1}{t-2}\sum_{i=2}^{t-1}(X_{i}-\hat{a}_{t-1}X_{i-1})^{2}\stackrel{{\scriptstyle
a.s}}{{\rightarrow}}\sigma^{2}$, as $t\to\infty$, which implies
$\hat{C}_{2t}-C_{2t}\stackrel{{\scriptstyle a.s}}{{\rightarrow}}0$, as
$t\to\infty$. Then,

$\frac{1}{n-1}\sum_{t=2}^{n}\hat{C}_{2t}-\frac{1}{n-1}\sum_{t=2}^{n}C_{2t}\stackrel{{\scriptstyle
a.s}}{{\rightarrow}}0.$ (20)

Hence,

$\frac{\log
W_{2n}}{2n}=\frac{n-1}{2n}\times\frac{1}{n-1}\sum_{t=2}^{n}\hat{C}_{2t}\to\frac{1}{2}\mathbb{E}\log(S_{4})\text{
almost surely, as }n\to\infty,$ (21) $\displaystyle
r^{*}=\frac{1}{2}\mathbb{E}\log(S_{4})$ $\displaystyle=\frac{1}{2}\log
2-\frac{1}{2}\mathbb{E}\left(\log\left(1+\frac{f(X_{2},X_{4},X_{3})}{f(X_{2},X_{3},X_{4})}\right)\right)$
$\displaystyle\geq\frac{1}{2}\log
2-\frac{1}{2}\log\left(1+\mathbb{E}\left(\frac{f(X_{2},X_{4},X_{3})}{f(X_{2},X_{3},X_{4})}\right)\right)$
(22)

The last step follows from Jensen’s inequality and equality holds if and only
if $\log\left(1+\frac{f(X_{2},X_{4},X_{3})}{f(X_{2},X_{3},X_{4})}\right)$ is a
linear function in $X_{2},X_{3},X_{4}$, which is equivalent to $a=0$.

It can be easily verified that $\mathbb{E}(\log
f(X_{2},X_{3},X_{4}))=-1-\log(2\pi)\text{ and }$

$\mathbb{E}(\log
f(X_{2},X_{4},X_{3}))=-1-\frac{a^{2}}{1+a}-\log(2\pi)\leq\mathbb{E}(\log
f(X_{2},X_{3},X_{4})),$ (23)

which implies

$\displaystyle\log\left(\mathbb{E}\left(\frac{f(X_{2},X_{4},X_{3})}{f(X_{2},X_{3},X_{4})}\right)\right)$
$\displaystyle\leq\mathbb{E}\left(\log\left(\frac{f(X_{2},X_{4},X_{3})}{f(X_{2},X_{3},X_{4})}\right)\right)$
$\displaystyle=\mathbb{E}(\log f(X_{2},X_{4},X_{3}))-\mathbb{E}(\log
f(X_{2},X_{3},X_{4}))\leq 0,$

i.e,
$\mathbb{E}\left(\frac{f(X_{2},X_{4},X_{3})}{f(X_{2},X_{3},X_{4})}\right)\leq
1$, where equality holds iff $a=0$ (follows from Equation (23)).

Hence, from Equation (A.3), $r^{*}\geq 0$ and equality holds if and only if
$a=0$. ∎

###  A.4 Proof of Theorem 2.6

Note that in the proof of Theorem 2.5, we only required $\\{X_{t}\\}_{t}$ to
an ergodic process, in order to conclude Equation (21). Hence, given
$\\{X_{t}\\}_{t}$ to be an ergodic process, we have

$\frac{\log W_{2n}}{2n}\to\frac{1}{2}\mathbb{E}\log(S_{4})\text{ almost
surely, as }n\to\infty,$ (24)
$r^{*}=\frac{1}{2}\mathbb{E}\log(S_{4})=-\frac{1}{2}\mathbb{E}\log\left(\frac{1}{S_{4}}\right)\geq-\log\mathbb{E}\left(\frac{1}{S_{4}}\right)$
(25)

which follows from Jensen’s inequality and equality holds if and only if
$\log\left(1+\frac{f(X_{2},X_{4},X_{3})}{f(X_{2},X_{3},X_{4})}\right)$ is a
linear function in $X_{2},X_{3},X_{4}$, which is equivalent to $a=0$. Now,
given that $\mathbb{E}\left(\frac{1}{S_{4}}\right)\leq 1,$ we have $r^{*}\geq
0$. Moreover, $r^{*}>0$, if $a\neq 0$ and
$\mathbb{E}\left(\frac{1}{S_{4}}\right)\leq 1$. ∎

## References

  * [Billingsley, 1966] Billingsley, P. (1966).  Ergodic theory and information.
  * [Chen, 2019] Chen, S. (2019).  Beijing Multi-Site Air-Quality Data.  UCI Machine Learning Repository.  DOI: https://doi.org/10.24432/C5RK5G.
  * [Fedorova et al., 2012] Fedorova, V., Gammerman, A., Nouretdinov, I., and Vovk, V. (2012).  Plug-in martingales for testing exchangeability on-line.  ICML’12, page 923–930, Madison, WI, USA. Omnipress.
  * [Grünwald et al., 2024] Grünwald, P., de Heide, R., and Koolen, W. M. (2024).  Safe testing.  Journal of the Royal Statistical Society Series B: Statistical Methodology (to appear).
  * [Howard et al., 2020] Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, J. (2020).  Time-uniform Chernoff bounds via nonnegative supermartingales.  Probability Surveys.
  * [Podkopaev et al., 2023] Podkopaev, A., Blöbaum, P., Kasiviswanathan, S., and Ramdas, A. (2023).  Sequential kernelized independence testing.  In International Conference on Machine Learning, pages 27957–27993. PMLR.
  * [Ramdas et al., 2023] Ramdas, A., Grünwald, P., Vovk, V., and Shafer, G. (2023).  Game-theoretic statistics and safe anytime-valid inference.  Statistical Science (to appear).
  * [Ramdas et al., 2022] Ramdas, A., Ruf, J., Larsson, M., and Koolen, W. M. (2022).  Testing exchangeability: Fork-convexity, supermartingales and e-processes.  International Journal of Approximate Reasoning, 141:83–109.
  * [Shafer, 2021] Shafer, G. (2021).  Testing by betting: A strategy for statistical and scientific communication.  Journal of the Royal Statistical Society Series A: Statistics in Society, 184(2):407–431.
  * [Shafer and Vovk, 2019] Shafer, G. and Vovk, V. (2019).  Game-theoretic foundations for probability and finance, volume 455.  John Wiley & Sons.
  * [Shekhar and Ramdas, 2023] Shekhar, S. and Ramdas, A. (2023).  Nonparametric two-sample testing by betting.  IEEE Transactions on Information Theory.
  * [Vovk, 2021] Vovk, V. (2021).  Testing randomness online.  Statistical Science, 36(4):595–611.
  * [Vovk et al., 2003] Vovk, V., Nouretdinov, I., and Gammerman, A. (2003).  Testing exchangeability on-line.  In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 768–775.
  * [Vovk et al., 2022] Vovk, V., Nouretdinov, I., and Gammerman, A. (2022).  Conformal testing: binary case with Markov alternatives.  In Conformal and Probabilistic Prediction with Applications, pages 207–218. PMLR.
  * [Vovk and Wang, 2021] Vovk, V. and Wang, R. (2021).  E-values: Calibration, combination and applications.  The Annals of Statistics, 49(3):1736–1754.
  * [Wald, 1945] Wald, A. (1945).  Sequential tests of statistical hypotheses.  The Annals of Mathematical Statistics, 16(2):117–186.
  * [Wasserman et al., 2020] Wasserman, L., Ramdas, A., and Balakrishnan, S. (2020).  Universal inference.  Proceedings of the National Academy of Sciences, 117(29):16880–16890.
  * [Waudby-Smith and Ramdas, 2023] Waudby-Smith, I. and Ramdas, A. (2023).  Estimating means of bounded random variables by betting.  Journal of the Royal Statistical Society Series B (Methodology), with discussion.


# Detection and Classification of mental illnesses on social media using
RoBERTa

Ankit Murarka
IBM Corporation
Research Triangle Park, NC
ankit.murarka1
@ibm.com Balaji Radhakrishnan*
<EMAIL_ADDRESS>
Sushma Ravichandran*
IBM Research
Yorktown Heights, NY
sushma.ravichandran
@ibm.com
* These authors contributed equally

###### Abstract

Given the current social distancing regulations across the world, social media
has become the primary mode of communication for most people. This has
resulted in the isolation of many people suffering from mental illnesses who
are unable to receive assistance in person. They have increasingly turned to
social media to express themselves and to look for guidance in dealing with
their illnesses. Keeping this in mind, we propose a solution to detect and
classify mental illness posts on social media thereby enabling users to seek
appropriate help. In this work, we detect and classify five prominent kinds of
mental illnesses- depression, anxiety, bipolar disorder, ADHD and PTSD by
analyzing unstructured user data on social media platforms. In addition, we
are sharing a new high-quality dataset to drive research on this topic. We
believe that our work is the first multi-class model that uses a Transformer
Vaswani et al. (2017)-based architecture such as RoBERTa Liu et al. (2019) to
analyze people’s emotions and psychology. We also demonstrate how we stress-
test our model using behavioral testing. With this research, we hope to be
able to contribute to the public health system by automating some of the
detection and classification process.

##  1 Introduction

During these unprecedented times when the world is plagued by COVID19, a large
number of people have been showing symptoms of clinical anxiety or
depression111https://afsp.org. This can be attributed to a myriad of reasons
including, but not limited to, lock down, mandatory social distancing, higher
unemployment, economic depression and work-related stress.

In a report published earlier this year, the American Foundation for Suicide
Prevention found that people experience anxiety (53%) and sadness (51%) more
often now than before the coronavirus pandemic. Additionally, as per the
report, despite physical distancing guidelines, Americans socialize with
friends and families at a similar frequency as they used to before the
lockdown orders confirming that physical distancing and isolation can
contribute to increase in anxiety, stress or depression.

In the past decade, social media has transformed how people interact with each
other. Apart from sharing factual information and news, people actively
partake in sharing their day to day activities, experiences, feelings,
opinions, hopes, desires, and emotions online. These texts provide information
which can be used to identify the mental health individuals. Furthermore, the
current state of enforced social distancing and isolation has propelled more
people to express their emotions on social media as it provides them with an
accessible platform to share their thoughts with others, many a times, in
search for help.

Our research work utilizes user data, especially the kind pertaining to
emotions as this class of data can give us valuable insights about the mental
state of a person; and, in turn, our work has the potential to assist in the
diagnosis and analysis of various mental disorders. This study aims to bridge
the gap between people in search of help and experts who can provide the
needed help.

Due to the paucity of adequate annotated and structured user data in this
domain, we decided to generate our own dataset by crawling subreddits on
reddit.com222https://www.reddit.com pertaining to our use case as a lot of
users were found to have shared their feelings there. Although Reddit was the
sole source of our dataset, we believe that this study can be seamlessly
extended to other social media platforms as well because of the presence of
similar unstructured user data online.

The advent of transformers and BERT Devlin et al. (2018) has caused quite a
stir in the NLP community because of the state-of-the-art results it was able
to produce in various NLP tasks. In this work, we use a RoBERTa Liu et al.
(2019) based classifier, which has a similar architecture to BERT with an
improved pre-training procedure. RoBERTa’s effective and efficient performance
on unstructured data and its ability to learn contextual information compelled
us to explore and capitalize its power to categorize online user generated
texts into various classes of Mental Illness.

We identify five broad classes of mental illnesses - depression, anxiety,
bipolar disorder, ADHD (Attention Deficit Hyperactivity Disorder), PTSD (Post
Traumatic Stress Disorder) and an additional ’None’ class (which does not
pertain to any mental illness). We train a multi-class classifier on the data
crawled from online user data. Based on our experiments, we present
encouraging results that demonstrate that social media data has the potential
to complement standard clinical procedures in the prognosis of mental health
amongst two broad categories of users - ones who are seeking help online and
ones who are unbeknownst of their condition.

##  2 Related Work

In the recent past, people have increasingly turned to social media to share
and seek counsel on the topic of mental health. This has prompted researchers
to utilize the information and apply a plethora of techniques in NLP and
Machine Learning in order to assist people who might require help. Most of the
recent research has revolved around Reddit data as in the case of Kim et al.
(2020), Gkotsis et al. (2017), Sekulic and Strube (2019), Zirikly et al.
(2019). Prior to this recent shift to Reddit data, a lot of the earlier
research was focused on utilizing Twitter data as in the case of Orabi et al.
(2018), Benton et al. (2017), Coppersmith et al. (2015).

There have been a wide variety of approaches ranging from classical NLP
techniques to neural network based deep learning methods. Coppersmith et al.
(2015) used character level language models to examine how likely a sequence
of characters is to be generated by a user with mental health issues. Benton
et al. (2017) evaluated a standard regression model, a multilayer perceptron
single-task learning (STL) model, and a neural MTL model on detecting multiple
types of mental health issues. Orabi et al. (2018) utilized word embeddings in
tandem with a variety of neural network models like CNNs and RNNs to detect
depression. Gkotsis et al. (2017) experimented with Feed Forward Neural
Networks, CNNs, SVMs and Linear classifiers to perform binary classification
on mental health posts. Sekulic and Strube (2019) came up with the approach of
using Hierarchical Attention Networks(HANs) to detect a wide range of mental
health issues like Depression, ADHD, Anxiety etc. and trained a binary
classifier for each of the disorders. The most recent work on this was by Kim
et al. (2020) who proposed a CNN-based classification model. Once again
though, each disorder had its own separate binary classifier to perform the
detection.

To our knowledge, this is the first attempt at treating this problem as a
multi-class classification problem, where a single classifier can not only
detect the disorder, but, also accurately classify the type of disorder that
the person is referring to in their post. In addition, this is also the first
work that harnesses the incredible capabilities of an advanced Transformer
based algorithm like RoBERTa to solve this difficult problem.

##  3 Dataset

The Reddit API was used to crawl 13 subreddits and 17159 posts text and title
text to obtain data for this research work. The text from comment threads was
not collected as it tended to diverge from the main topic of the subreddit.
Out of the 13 subreddits, 5 can be directly associated with a mental illness.
They are: `bipolar`, `adhd`, `anxiety`, `depression` and `ptsd`. The posts in
these subreddits were assigned a class label corresponding to the name of the
subreddits. The remaining 8 subreddits were chosen from a wide range of
topics. They are `music`, `travel`, `india`, `politics`, `english`,
`datasets`, `mathematics` and `science`. These general topic subreddits were
combined together and assigned the class label `none`.

While collecting data, we ensured that the number of upvotes for each post in
all subreddits is more than 10. We also set a minimum post token length of 30
tokens. This is so that we retain quality in the dataset. We approximately
crawled about 3000 posts under the subreddits dealing with mental illness and
about 300 posts for each of the general topic subreddits. This also ensured a
good balance of class labels. While selecting the eight general topic
subreddits, we not only selected subreddits that have sufficiently high number
of posts, but also ensured that we cover a broad range of topics. Table 1
shows the statistics collected for each subreddit. The dataset was
preprocessed to remove any URLs or usernames that could potentially contain
sensitive information. This was done keeping in mind that the dataset will be
released publicly for the purpose of extending this research work.

To gauge the data quality we ran some analysis. We manually went over the
lowest voted posts for each mental illness subreddit. We wanted to establish
that texts from these posts expressed emotions from people discussing
corresponding mental illness it is labelled as. Table 2 presents excerpts of
lowest voted post from each mental illness subreddit.

We also certified that the general topic subreddits did not have a high
similarity with the posts corresponding to other the other 5 subreddits. This
was done to ensure that we do not have any false negatives while assigning
truth labels. We counted the number of posts the mental illness terms appeared
in, for each subreddit. The subreddits corresponding to mental illnesses had a
much higher count of these words. In addition to this, we compared the cosine
similarity between some of the highest/lowest posts of mental illness
subreddits and the general topic subreddits and manually compared the results
to find that this distance was higher than the distance between two posts of
the mental illness subreddits.

We also attempted to augment the data using Easy Data Augmentation Wei and Zou
(2019) to boost the performance of our model. However, we did not observe an
apparent shift in our evaluation metrics- explained by the fact the EDA is
meant to perform best for smaller datasets ($\leq$ 5000 sample sizes). So, we
decided to not advance in that route.

Subreddit |  Number of posts |  Average no. of words (posts) |  Average no. of words (titles) |  Average Upvotes |  Highest Upvotes |  Lowest Upvotes
---|---|---|---|---|---|---
r/depression |  3062 |  152.74 |  12.20 |  517.19 |  4802 |  11
r/anxiety |  3027 |  170.38 |  11.75 |  246.07 |  3349 |  11
r/ptsd |  2501 |  233.55 |  10.14 |  38.4 |  443 |  11
r/adhd |  3082 |  198.55 |  13.71 |  377.13 |  4484 |  11
r/bipolar |  3009 |  203.28 |  9.26 |  32.37 |  363 |  11
none |  2478 |  238.52 |  15.76 |  6715.33 |  199295 |  11
Table 1:  Dataset: Statistics  Lowest rated post
---
r/depression\- The older I am getting the less hope I have to secure a life
worth living. I feel finished because I always had that state of mind
r/adhd\- Does anyone else feel like u do have a personality and ability to
make friends but ure kind of stuck in ur own body
r/bipolar\- I just made a really impulsive choice with my breed of dog because
I had to have one NOW. I was thinking about it constantly day and night and I
couldn’t sleep.
r/anxiety\- I find myself constantly remembering embarrassing or cringey
moments from my past (ranging anywhere from present day to back about 10
years) and cringing hard at them
r/ptsd\- I feel like I am just constantly angry. Angry about my trauma and how
it has affected me, and angry about where I am in my life because of it. I
don’t want to be angry anymore
Table 2:  Dataset: Posts excerpts

##  4 Model

In this section, we describe our model architecture for the multi-class mental
illness classification task. We propose a RoBERTa based classifier in order to
accomplish this. In addition, we also compare the proposed model against an
LSTM Hochreiter and Schmidhuber (1997) based classifier and a BERT Devlin et
al. (2018) based classifier to demonstrate the superiority of our approach.
Since this is an entirely new dataset, there is no established baseline, so
the LSTM model will serve as the baseline for our experiments. We also
showcase our gains over BERT, the most widely used transformer model today for
text classification. All our models were implented in Pytorch Paszke et al.
(2019). The Transformer models were implemented with the help of the
HuggingFace Transformers Wolf et al. (2019) library.

###  4.1 LSTM based classifier

LSTMs(Long Short-Term Memory) were the state of the art models when it came to
text classification before the advent of Transformers. They will serve as our
baseline. First we tokenized the sentences using NLTK333https://www.nltk.org/
and converted them to lower case to create our vocabulary. In order to get rid
of words that might not exist, we removed all words from our vocabulary that
appear only once. We also added `padding` and `unknown` to our vocabulary in
order to account for padding and unknown tokens respectively. Each sentence
was represented using a sequence of length 512 and this forms our input to the
LSTM model. We used a 2 layer LSTM for all our experiments with an embedding
layer of size 100 and a hidden layer size of 256. Dropout Srivastava et al.
(2014) with a probability of 0.5 was used in order to achieve regularization.
We used standard cross-entropy loss as the loss function. During training,
Adam Kingma and Ba (2014) was the optimizer of choice, with a learning rate of
0.005. The model was trained for a total of 25 epochs with a batch size of 32.
Gradient clipping was used to prevent exploding gradients.

###  4.2 BERT based classifier

BERT(Bidirectional Encoder Representations from Transformers) has been the
biggest breakthrough in the NLP domain in the recent past with state of the
art results in a myriad of NLP tasks. Since its inception, better models with
gains have been trickling along, but BERT continues to be the most popular
model for text classification even today. The BERT classifier comprises a
fine-tuned BERT model followed by a dropout layer and a fully connected layer.
We fine-tuned a pre-trained BERT-base model on our dataset for this task. A
pre-trained tokenizer on BERT is used to tokenize our input sentences. After
carefully examining the sentence length distribution, we chose a sequence
length of 35 for titles, and 512 for posts and posts+titles. Either padding or
truncation was used to ensure that all sentences were represented using the
same sequence length. All the BERT based models were fine-tuned on our data
for 10 epochs with a learning rate of 1e-5. Adam served as the optimizer and
cross-entropy loss was the loss function of choice. A dropout layer with
probability of 0.3 was used for the sake of regularization.

###  4.3 RoBERTa based classifier

RoBERTa(Robustly Optimized BERT Pretraining Approach) is another state of the
art language model that builds on BERT by modifying key hyperparameters and
training on more data. It outperforms BERT on several benchmark tasks and
forms the core of our proposed solution. In order to make it a fair comparison
with BERT, we retain the architecture and all design choices made with the
BERT based classifier barring the pretrained model and the tokenizer which are
now all based on RoBERTa. The input sentences were tokenized using a pre-
trained tokenizer on RoBERTa-base. Just as in the case of BERT, we chose a
sequence length of 35 for titles, and 512 for posts and posts+titles. Similar
to BERT, the RoBERTa based models were also fine-tuned for 10 epochs with a
learning rate of 1e-5 and Adam. A batch size of 32 was used while fine-tuning
on the titles whereas a batch size of 16 was the only viable option to fine-
tune on posts and posts+titles. Cross-entropy remained the preferred loss
function. Once again, a dropout layer with probability of 0.3 was used for
regularization.

##  5 Result Analysis

Models | posts | titles | posts+titles
---|---|---|---
| P | R | F1 | Acc | P | R | F1 | Acc | P | R | F1 | Acc
LSTM | 0.74 | 0.72 | 0.72 | 0.72 | 0.65 | 0.64 | 0.64 | 0.64 | 0.77 | 0.76 | 0.76 | 0.76
BERT | 0.83 | 0.82 | 0.82 | 0.82 | 0.72 | 0.71 | 0.71 | 0.71 | 0.87 | 0.87 | 0.87 | 0.87
RoBERTa | 0.86 | 0.86 | 0.86 | 0.86 | 0.73 | 0.72 | 0.72 | 0.72 | 0.89 | 0.89 | 0.89 | 0.89
Table 3:  Results: Classification Report

(a) Input: posts

(b) Input: titles

(c) Input: posts+titles

Figure 1: RoBERTa: Confusion Matrices Class | posts | titles | posts+titles
---|---|---|---
| P | R | F1 | P | R | F1 | P | R | F1
adhd | 0.87 | 0.88 | 0.87 | 0.77 | 0.79 | 0.78 | 0.91 | 0.92 | 0.91
anxiety | 0.78 | 0.83 | 0.81 | 0.69 | 0.64 | 0.67 | 0.87 | 0.85 | 0.86
bipolar | 0.88 | 0.79 | 0.83 | 0.58 | 0.63 | 0.60 | 0.88 | 0.83 | 0.86
depression | 0.77 | 0.83 | 0.80 | 0.65 | 0.78 | 0.71 | 0.81 | 0.88 | 0.84
ptsd | 0.88 | 0.85 | 0.86 | 0.75 | 0.62 | 0.68 | 0.88 | 0.89 | 0.88
none | 0.99 | 0.95 | 0.97 | 0.94 | 0.88 | 0.91 | 1.00 | 0.98 | 0.99
Table 4:  Results: RoBERTa Class-wise results  Input | Actual | Predicted
---|---|---
often times i’ll get distracted from my thoughts either by external influences or just another idea coming in, and then i have to spend a good 5 minutes trying to work out what i was thinking about again. | adhd | adhd
once i come down from flashbacks or panic attacks, i get really bad disassociation. sometimes lasting for days. does anyone else go through this. any tips on how to stop it. i tried grounding but im so far gone it doesn’t help. | ptsd | ptsd
i can’t sit still when i get my eyebrows done, and when i’m in class i usually doodle to focus. i pay attention very well in school regardless of that, and drawing helps me focus. | anxiety | adhd
i’m flying from dallas to hong kong in january and it’s 17 hours. i’ve flown 12-13 hour flights before and they really mess with me. so i’m wondering - what are your tips for not going crazy on such a long flight? ps: i’m terrible at sleeping on planes. thinking about taking some sleepy meds to see if it’ll help | none | anxiety
Table 5:  Results: Interesting Examples

As described earlier, in addition to our primary RoBERTa classifier, we also
run experiments on an LSTM classifier and a BERT classifier for the sake of
comparison. We fine-tune each of the aforementioned models on just the titles,
just the posts and a combination of both in order to perform comprehensive
tests and comparisons. When combining the titles and posts for our Transformer
models, we convert the problem into a sequence-pair classification task. This
allows the model to give more importance to the title which would otherwise be
lost when combining the title and the post into one single input given the
relative difference in their lengths (the average number of tokens in titles
is roughly 6% that of posts).

The results from our experiments are documented in Tables 3 through 5.

As can be observed from Table 3, our proposed RoBERTa based classifier far
outperforms the baseline LSTM in all categories. The BERT classifier has
results which are quite close to that of RoBERTa’s and both beat LSTM by a
significant margin, showcasing the incredible capabilities of pre-trained
Transformer based architectures. In fact, our RoBERTa model fine-tuned on just
the titles was able match the performance of the LSTM model trained on posts.
The RoBERTa model was able to achieve an F1 score of 0.86 on the posts and
0.89 on posts+titles which are extremely promising given the complex nature of
the multi-class mental illness classification task. The jump in accuracy
between posts and posts+titles is not as drastic as the jump between titles
and posts. This indicates that the posts offer far more valuable information
when compared to the titles and also the fact that most of the useful and
relevant information can be extracted from the posts alone. This strong
performance on just the posts bodes well for the extensibility of our approach
as this can be applied on almost any given social media post without the need
for structure in the data like titles, user names, user history, etc.

The rest of this section will focus solely on the results of our best
performing RoBERTa model. Table 4 showcases the granular class-wise results of
the RoBERTa model. This table in conjunction with the confusion matrices from
Figure 1 offers us a wealth of useful and interpretable information.

The first strikingly obvious result is the high accuracy with which the model
is able to detect non-illness related posts. Even with just the titles, the
model is able to classify the `none` class with an f1 score of more than 0.9.
This gives us hope that this model will suffer from very few false positives
when it comes to mental illness detection on social media.

An even more crucial property of our model can be noticed in the confusion
matrices for posts and posts+titles in Figure 1. When using posts, just 3
illness related posts across the entire test dataset were misclassified as
non-illness posts. This number further reduces to 0 when using titles+posts.
This shows that the model will detect mental illness posts correctly nearly
every single time, thus ensuring that posts from people who are seeking help
never go unnoticed when this solution is deployed in the real world.

When it comes to the class wise performance amongst the mental illnesses, the
two best performing classes are `adhd` and `ptsd` whereas the two worst
performing classes are `depression` and `anxiety`.

The performance of `depression` and `anxiety` classes can be attributed to a
few factors. The average number of words per post for `depression` and
`anxiety` are the least for any given class. For instance, `depression` posts
have roughly 53% lesser textual data when compared to `ptsd` posts. In
addition, studies show that depression might often occur in tandem with
another mental illness and our data and results back this up as well. The
`depression` word occurs in 12% of `anxiety` posts, 12% of `ptsd` posts and
31% of `bipolar` posts. Similarly, `anxiety` occurs in 20% of `ptsd` posts,
12% of `adhd` posts and 14% of `bipolar` posts. This implies that the model
cannot give high importance to the mention of these class names like it can
with rest of the illnesses, thus making the classification of these 2 classes
that much harder.

This can also explain the relatively lower precision scores(higher number of
False Positives) for `depression` and `anxiety`. When the other
illnesses(excluding `depression` and `anxiety`) are misclassified, they are
almost always misclassified as either `depression` or `anxiety`, as can be
viewed in Figure 1. In the same figure, we can see that `depression` and
`anxiety` are often misclassified as each other due to the reason that they
commonly occur together.

There are more posts in the `adhd` and `ptsd` classes that mention the words
`depression` and `anxiety` than their respective class names itself. One would
assume that this would result in subpar results, but, these classes actually
perform the best. This really showcases the true potential of our model, where
it doesn’t just rely on mention of class names, but has a strong understanding
of the context of the post itself. Additionally, the symptoms or descriptions
provided for these classes could be strong, unique and discriminative enough
for the model to be able to classify them correctly even with all the mentions
of other class names.

In Table 5 we have documented a few interesting results we observed in the
test set. In the first two examples on the table, the RoBERTa model was able
to classify the posts correctly without the presence of class names in the
input. The prediction is based purely on contextual information learnt about
the class labels during the training process. The next two results are
interesting because the truth label assigned to the input text may or may not
correspond to actual mental illness described in the text. Since, we are not
domain experts ourselves, we would need expert intervention to substantiate
this theory. As a part of future work, getting professionals to annotate our
dataset might help strengthen the model for such examples.

##  6 Behavioral Testing

Synonym Replacement | Label Removal
---|---
Test Set Modified | posts |  Test Set Modified | posts
| P | R | F1 | Acc |  | P | R | F1 | Acc
10% | 0.86 | 0.85 | 0.85 | 0.85 |  10% | 0.85 | 0.84 | 0.84 | 0.84
50% | 0.85 | 0.84 | 0.84 | 0.84 |  50% | 0.81 | 0.80 | 0.80 | 0.80
100% | 0.83 | 0.83 | 0.83 | 0.83 |  100% | 0.75 | 0.74 | 0.75 | 0.74
Test Set Modified | titles |  Test Set Modified | titles
| P | R | F1 | Acc |  | P | R | F1 | Acc
10% | 0.73 | 0.72 | 0.72 | 0.72 |  10% | 0.72 | 0.71 | 0.71 | 0.71
50% | 0.71 | 0.71 | 0.71 | 0.71 |  50% | 0.67 | 0.67 | 0.67 | 0.67
100% | 0.68 | 0.67 | 0.67 | 0.67 |  100% | 0.61 | 0.61 | 0.60 | 0.61
Label Replace: ’illness’ | Label Replace: random
Test Set Modified | posts |  Test Set Modified | posts
| P | R | F1 | Acc |  | P | R | F1 | Acc
10% | 0.84 | 0.83 | 0.84 | 0.83 |  10% | 0.83 | 0.82 | 0.83 | 0.8
50% | 0.78 | 0.77 | 0.77 | 0.77 |  50% | 0.71 | 0.71 | 0.71 | 0.71
100% | 0.70 | 0.67 | 0.68 | 0.67 |  100% | 0.58 | 0.57 | 0.57 | 0.57
Test Set Modified | titles |  Test Set Modified | titles
| P | R | F1 | Acc |  | P | R | F1 | Acc
10% | 0.72 | 0.71 | 0.71 | 0.71 |  10% | 0.71 | 0.71 | 0.71 | 0.71
50% | 0.67 | 0.65 | 0.65 | 0.65 |  50% | 0.64 | 0.64 | 0.64 | 0.64
100% | 0.62 | 0.57 | 0.58 | 0.57 |  100% | 0.54 | 0.54 | 0.54 | 0.54
Table 6:  Behavioral Tests

Although the classification metrics analyzed in the previous section are
generally regarded sufficient in estimating the performance of Bert-based
models, a recent inclination of NLP researchers to behavioral testing inspired
us to stress test our models as well.

For all our tests, we used our proposed RoBERTa model and applied these tests
to inputs that were either titles or posts. Since we hope to extend our model
to other social media platforms, we do not always expect input texts to have a
title as well as a descriptive text/post. We adopted the Checklist approach
Ribeiro et al. (2020) which involve tests conducted to comprehensively analyze
the model’s performance.

###  6.1 Synonym Replacement

Synonym replacement is a kind of Invariance Test where label-preserving
perturbations are made to the test set. As labels, the root form of the mental
illnesses was chosen- `depress`, `ptsd`, `anxiou/anxiet`, `bipolar` and
`adhd`. Python’s NLTK package and WordNet were used for these tests.

This test is conducted such that the root words are not perturbed when
modifying the test set. For each post, 10% of the tokens were randomly
selected (not including the stop words or the root words). Each token was then
replaced with one of its synonyms. We used the same logic for titles. We set a
max and min on the number of tokens to be selected for replacement - this was
(4, 30) for posts and (1, 5) for titles. Since each token was replaced with a
synonym, the class label for the samples was not changed. We did this for 10,
50 and 100 percent of the test set and observed results.

In all three cases, we expect the classification metrics to drop. For the case
when 10% of the test case was modified the drop was much lower as compared to
when 100% of the test case was modified. The results are documented in Table
6. When comparing these results to those in Table 4 we find that the drop in
each category is about 2-4% for posts and 5-7% for titles. The lower drop can
be attributed to the fact that synonym replacement does not alter the
semantics of the input text. Therefore the model was able to draw sufficient
information from the input.

###  6.2 Masking

We also performed a Directional Expectation test on the model. This is similar
to the previous test but is instead performed only on labels. The labels, as
defined in the previous subsection, are a list of the root form of mental
illness class labels. We noticed that the root words appear often in our input
texts. This behavioral test was performed to observe our model’s dependency on
these words. For all the tests below, we modified only those tokens that
contained a root word.

In the first case, for every post from a subreddit related to a mental
illness, the root form of its class label was removed from the input. For
example, the input text: _I feel happy for some time and then depressed again.
I’m definitely bipolar_ from the `r/bipolar` subreddit, was modified to _I
feel happy for some time and then depressed again. I’m definitely_. Note that
changes were not made to the word _depressed_ in the input. The class label
for each modified sample was not changed after the perturbations. Like the
previous subsection, these tests were performed on 10, 50 and 100% of the test
set.

In the second case, instead of entirely removing the tokens, we replaced it
with a generic token `illness`. We expected this modification to retain some
semantic information that was lost in the previous test. However, we found
that adding a generic token introduced some noise which reduced the overall
performance of the model.

Lastly, the tokens were replaced by a randomly chosen root form of a mental
illness other than its class label. With this test, we expect to force the
model to pick between the label and non label tokens during classification. We
believe that this is an interesting scenario to observe.

In all three cases (Table 6), the model performance drops by some degree when
compared to Table 4. The first two cases showed a somewhat similar performance
drop. However, the model performance was worse than that of the Synonym
Replacement test. This means that the model depends on the existence of the
root words in the input text to some degree.

In the third scenario, we note that the performance drop is higher. Although
the test is meant to confuse the model, we observed that in some cases
(especially for input: posts), we got an F1 of 0.82 with 10% of the modified
test and 0.71 with 50% of the modified test. This is only possible if the
model gathered sufficient information from the non label text in the input.

##  7 Conclusion and Future Work

Our chief motivation behind this work is the current worldwide pandemic and
the mandatory confinement in many countries. We believe that social media has
become the prime mode of communication for many people and has paved way for a
lot of users to vent freely without judgement.

In the future we hope to be able to involve domain experts in our research and
have them annotate some of our data to validate our model’s performance. In
addition to this, we would like to build a multi-label classifier because
users may suffer from multiple mental illnesses at the same time. We would
also like to work on bettering our model on the behavioral tests. Our work
involves two kinds of texts- long and short - both of which are common to the
internet community. Hence, our work can easily be extended to many websites.
It would be interesting to collect user data from other forums and observe our
model’s predictions.

In conclusion, we believe that our work explores an interesting line of
research where NLP is used to bridge the gap between virtual and real life of
users and help those in need of medical attention.

## References

  * Benton et al. (2017) Adrian Benton, Margaret Mitchell, and Dirk Hovy. 2017.  Multi-task learning for mental health using social media text.
  * Coppersmith et al. (2015) Glen Coppersmith, Mark Dredze, Craig Harman, Kristy Hollingshead, and Margaret Mitchell. 2015.  Clpsych 2015 shared task: Depression and ptsd on twitter.  In _Proceedings of the 2nd Workshop on Computational Linguistics and Clinical Psychology: From Linguistic Signal to Clinical Reality_. 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.
  * Gkotsis et al. (2017) George Gkotsis, Anika Oellrich, Sumithra Velupillai, Maria Liakata, Tim J. P. Hubbard, Richard J. B. Dobson, and Rina Dutta. 2017.  Characterisation of mental health conditions in social media using informed deep learning.  _Scientific Reports_ , 7(1):1–10.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jurgen Schmidhuber. 1997.  Long short-term memory.
  * Kim et al. (2020) Jina Kim, Jieon Lee, Eunil Park, and Jinyoung Han. 2020.  A deep learning model for detecting mental illness from user content on social media.  _Scientific Reports_ , 10(1):1–6.
  * Kingma and Ba (2014) Diederik P. Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.
  * Orabi et al. (2018) Ahmed Husseini Orabi, Prasadith Buddhitha, Mahmoud Husseini Orabi, and Diana Inkpen. 2018.  Deep learning for depression detection of twitter users.  In _Proceedings of the Fifth Workshop on Computational Linguistics and Clinical Psychology_. Association for Computational Linguistics.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc.
  * Ribeiro et al. (2020) Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh. 2020.  Beyond accuracy: Behavioral testing of nlp models with checklist.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics.
  * Sekulic and Strube (2019) Ivan Sekulic and Michael Strube. 2019.  Adapting deep learning methods for mental health prediction on social media.  In _Proceedings of the 5th Workshop on Noisy User-generated Text (W-NUT 2019)_ , pages 322–327, Hong Kong, China. Association for Computational Linguistics.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: A simple way to prevent neural networks from overfitting.  _J. Mach. Learn. Res._ , 15(1):1929–1958.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems 30_ , pages 5998–6008. Curran Associates, Inc.
  * Wei and Zou (2019) Jason Wei and Kai Zou. 2019.  Eda: Easy data augmentation techniques for boosting performance on text classification tasks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _ArXiv_ , abs/1910.03771.
  * Zirikly et al. (2019) Ayah Zirikly, Philip Resnik, Özlem Uzuner, and Kristy Hollingshead. 2019.  Clpsych 2019 shared task: Predicting the degree of suicide risk in reddit posts.  In _Proceedings of the Sixth Workshop on Computational Linguistics and Clinical Psychology_. Association for Computational Linguistics.