# Inoculation strategies for bounded degree graphs

Mason DiCicco***Computer Science Department, WPI<EMAIL_ADDRESS><EMAIL_ADDRESS>Henry<EMAIL_ADDRESS>Daniel Reichman∗

###### Abstract

We analyze a game-theoretic abstraction of epidemic containment played on an
undirected graph $G$: each player is associated with a node in $G$ and can
either acquire protection from a contagious process or risk infection. After
decisions are made, an infection starts at a random node $v$ and propagates
through all unprotected nodes reachable from $v$. It is known that the price
of anarchy (PoA) in $n$-node graphs can be as large as $\Theta(n)$. Our main
result is a tight bound of order $\sqrt{n\Delta}$ on the PoA, where $\Delta$
is the _maximum degree_ of the graph. We also study additional factors that
can reduce the PoA, such as higher thresholds for contagion and varying the
costs of becoming infected vs. acquiring protection.

##  1 Introduction

Networks can be conducive to the spread of undesirable phenomena such as
infectious diseases, computer viruses, and false information. A great deal of
research has been aimed at studying computational challenges that arise when
trying to contain a contagious process [MV13, BDS+22, BDSZ16].

One factor that can contribute to the spread of contagion is the discrepancy
between _locally_ optimal behavior of rational agents and _globally_ optimal
behavior that minimizes the total cost to the agents in the network. For
example, individuals in a computer network may prefer not to install anti-
virus software because it is too expensive, whereas a network administrator
may prefer to install copies at key points, limiting the distance a virus
could spread and the global damage to the network. The former strategy would
be considered a _locally optimal_ solution if each individual minimizes their
own individual cost, whereas the latter strategy would be a _socially optimal_
solution if it minimizes the total cost to all individuals in the network.

How much worse locally optimal solutions can be compared to the social optimum
can be quantified by the classical game theoretic notions of _Nash equilibria_
and _price of anarchy_. (PoA) [RT02, Rou05]. Informally, given a multiplayer
game, a strategy is a Nash equilibrium if no player can improve her utility by
unilaterally switching to another strategy. Then, the PoA is the ratio of the
total cost of the _worst_ Nash equilibrium to the social optimum. The larger
the PoA, the larger the potential cost players in the game may experience due
to selfish, uncoordinated behavior. Hence, it is of interest to investigate
methods of reducing the PoA in games.

We study the PoA of a game-theoretic abstraction of epidemic containment
introduced by [ACY06]. The _inoculation game_ is an $n$-player game in which
each player is associated with a node in an undirected graph. A player can buy
security against infection at a cost of $C>0$, or they can choose to accept
the risk of infection. If a node is infected, its player must pay a cost
$L>0$. After each player has made their decision, an adversary chooses a
random starting point for the infection. The infection then propagates through
the graph; any unsecured node that is adjacent to an infected node is also
infected.

It is known that the PoA of the inoculation game can be as large as
$\Omega(n)$, with the $n$-star (a node connected to $n-1$ other nodes) being
one example of a network leading to such a PoA‡‡‡This is asymptotically the
largest possible PoA; it is shown in [ACY06] that in any $n$-node network the
PoA is at most $O(n)$.. This raises the question of the relationship between
graph-theoretic parameters and the PoA of the inoculation game. This question
was explicitly mentioned in [CDK10] as an interesting direction for future
research. Additional properties of the game may also influence the PoA, such
as the relative costs of infection and security, or the threshold of
infection.

We study the relationship between the aforementioned factors and the PoA. One
motivation for our study is that understanding the links between properties of
the inoculation game and the PoA may shed light on methods for designing
networks that are less susceptible to contagion. It may also shed light on the
effectiveness of interventions (e.g., changing the cost of acquiring
inoculations) aimed at controlling contagion. Specifically, we examine
following questions:

  * •

Motivated by the relationship between “superspreaders” and contagion, we
analyze how the _maximum degree_ influences the PoA, obtaining asymptotically
tight upper and lower bounds in terms of the number of nodes $n$ and the
maximum degree $\Delta$. We also study the PoA in graphs with certain
structural properties, such as planar graphs.

  * •

One can try to reduce the PoA by changing the values of $C$ and $L$ (e.g., by
making inoculations more accessible). Previous results regarding the PoA
[ACY06, CDK10] typically examined fixed values of $C$ and $L$. In contrast, we
analyze the PoA for specific networks for all $C$ and $L$.

  * •

_Complex contagion_ refers to contagion models where a node becomes infected
only if multiple neighbors are infected. We study the case where the threshold
for contagion is 2 (as opposed to 1) and provide very simple analysis of the
PoA for certain networks in this contagion model.

We also record the asymptotic PoA for graphs families such as trees, planar
graphs and random graphs. Details can be found in the Appendix A.

###  1.1 Preliminaries

Following [ACY06], we describe the infection model and the multiplayer game we
study as well as a useful characterization of Nash equilibria.

####  1.1.1 Inoculation game

Unless stated otherwise, we consider graphs with $n$ nodes and identify the
set of nodes by integers $[n]:=\\{1,\cdots,n\\}$. An _automorphism_ of a graph
$G$ is a permutation $\sigma$ of its vertex set $[n]$ such that $i$ is
adjacent to $j$ if and only if $\sigma(i)$ is adjacent to $\sigma(j)$. A graph
$G=(V,E)$ is _vertex transitive_ if for every two vertices $i,j\in V$ there is
automorphism $f$ of $G$ such that $f(i)=j$.

######  Definition 1 (Inoculation game).

The inoculation game is a one-round, $n$-player game, played on an undirected
graph $G$. We assume $G$ is a connected graph and each node is a player in the
game. Every node $i$ has two possible actions: Inoculate against an infection,
or do nothing and risk being infected. Throughout the paper we assign $1$ to
the action of inoculating and $0$ the action of not inoculating. We say the
cost of inoculation is $C>0$ and the cost of infection is $L>0$.

######  Remark 1.

We always assume that $C$ and $L$ are constants independent of $n$, unless
otherwise stated. In particular, our lower bounds generally require that the
_ratio_ $C/L=\Theta(1)$. We discuss the relationship between the costs and the
PoA in Section 1.2.2.

The _strategy_ of each node $i$ is the probability of inoculating, denoted by
$a_{i}\in[0,1]$, and the _strategy profile_ for $G$ is represented by the
vector $\overrightarrow{\bm{a}}\in[0,1]^{n}$. If $a_{i}\in\\{0,1\\}$, we call
the strategy _pure_ , and otherwise _mixed_.

Note that a mixed strategy is a probability distribution $\mathcal{D}$ over
pure strategies. The cost of a mixed strategy profile to individual $i$ is
equal to the expected cost over $\mathcal{D}$,

$\displaystyle\mathrm{cost}_{i}(\overrightarrow{\bm{a}})$
$\displaystyle=C\cdot\Pr(i\text{ inoculates})+L\cdot\Pr(i\text{ is infected})$
$\displaystyle=C\cdot a_{i}+L\cdot(1-a_{i})p_{i}(\overrightarrow{\bm{a}}),$

where $p_{i}(\overrightarrow{\bm{a}})$ denotes the probability that $i$
becomes infected given strategy profile $\overrightarrow{\bm{a}}$ _conditioned
on $i$ not inoculating_. The total social cost of $\overrightarrow{\bm{a}}$ is
equal to the sum of the individual costs,

$\mathrm{cost}(\overrightarrow{\bm{a}})=\sum_{i=1}^{n}\mathrm{cost}_{i}(\overrightarrow{\bm{a}}).$

######  Definition 2 (Attack graph).

Given a strategy profile $\overrightarrow{\bm{a}}$, let
$I_{\overrightarrow{\bm{a}}}$ denote the set of secure nodes (nodes which have
inoculated). The _attack graph_ , which we denote by
$G_{\overrightarrow{\bm{a}}}$, is the sub-graph induced by the set of insecure
nodes:

$G_{\overrightarrow{\bm{a}}}=G\setminus I_{\overrightarrow{\bm{a}}}.$

Figure 1: The two vertices in the shaded region are inoculated. The remaining
vertices form the attack graph consisting of two connected components of sizes
$4$ and $6$ respectively.

After every node has decided whether or not to inoculate, a node $i\in V$ is
chosen uniformly at random (over all nodes) as the starting point of the
infection. If $i$ is not inoculated, then $i$ and every insecure node
reachable from $i$ in $G_{\overrightarrow{\bm{a}}}$ are infected. Note that
$I_{\overrightarrow{\bm{a}}}$ and $G_{\overrightarrow{\bm{a}}}$ are random
variables unless $\overrightarrow{\bm{a}}$ is pure. When the strategies are
pure, [ACY06] give the following characterization for the social cost:

######  Theorem 1 ([ACY06]).

Let $\overrightarrow{\bm{a}}$ be a pure strategy profile for a graph $G$.
Then,

$\mathrm{cost}(\overrightarrow{\bm{a}})=C|I_{\overrightarrow{\bm{a}}}|+\frac{L}{n}\sum_{i=1}^{\ell}k_{i}^{2},$

where $k_{1},\cdots,k_{\ell}$ denote the sizes of the connected components in
$G_{\overrightarrow{\bm{a}}}$.

####  1.1.2 Nash equilibria

######  Definition 3 (Nash equilibrium).

A strategy profile $\overrightarrow{\bm{a}}$ is a _Nash equilibrium_ (NE) if
no nodes can decrease their individual cost by changing their own strategy.

Formally, let
$\overrightarrow{\bm{a^{*}}}:=(a_{i}^{*},\overrightarrow{\bm{a^{*}_{-i}}})$ be
a strategy profile where $\overrightarrow{\bm{a^{*}_{-i}}}$ denotes the
strategy profile of all players except node $i$. Then,
$\overrightarrow{\bm{a^{*}}}$ is a Nash equilibrium if, for all $i$,

$\mathrm{cost}_{i}((a_{i}^{*},\overrightarrow{\bm{a}}_{-i}^{*}))\leq\mathrm{cost}_{i}((a_{i},\overrightarrow{\bm{a_{-i}^{*}}}))\text{
for all }a_{i}\neq a_{i}^{*}.$

Similarly to arbitrary strategies, the cost of an NE is simply the sum of
expected costs of the individual vertices.

In the inoculation game, Nash equilibria are characterized by the expected
sizes of the _connected components_ in the attack graph.

######  Theorem 2 ([ACY06]).

Let $S(i)$ denote the expected size of the component containing node $i$ in
the attack graph conditioned on $i$ not inoculating, and let $t=Cn/L$. A
strategy $\overrightarrow{\bm{a}}$ is a Nash equilibrium if and only if every
node satisfies the following:

  1. 1.

if $a_{i}=0$, then $S(i)\leq t$

  2. 2.

if $a_{i}=1$, then $S(i)\geq t$

  3. 3.

if $0<a_{i}<1$, then $S(i)=t$

This follows from the definition of Nash equilibria, recognizing that the
threshold on the expected component size, $t=Cn/L$, is the point where the
cost of inoculating equals the (expected) cost of not inoculating,
$C=LS(i)/n$.

The following upper bound regarding the cost of every Nash equilbrium was
observed in [ACY06].

######  Corollary 1 ([ACY06]).

For any graph $G$, every Nash equilibrium has cost at most $\min\\{C,L\\}n$.

###### Proof.

If $C>L$, then the only Nash equilibrium is the strategy
$\overrightarrow{\bm{a}}=0^{n}$ where no node inoculates, which has cost $Ln$.
Otherwise, if $C\leq L$, then the individual cost to any node is at most $C$
(any node will switch its strategy to inoculate, if preferable.)

∎

######  Remark 2.

Later, we show that there exist graphs whose Nash equilibria meet the upper
bound of Corollary 1; for all $C,L>0$, there exists a Nash equilibrium with
cost $\min\\{C,L\\}n$. This property yields bounds on the PoA that are
“stable” with respect to the costs $C,L$.

####  1.1.3 Price of Anarchy

######  Definition 4 (Price of Anarchy).

The Price of Anarchy (PoA) of an inoculation game played on a graph $G$ is
equal to the ratio between the cost of the _worst_ Nash equilibrium to the
cost of the socially optimal strategy§§§Observe that as $C,L>0$ the cost is
always strictly positive.,

$\mathrm{PoA}(G)=\frac{\max_{\overrightarrow{\bm{a}}:\text{Nash
eq.}}\mathrm{cost}(\overrightarrow{\bm{a}})}{\min_{\overrightarrow{\bm{a}}}\mathrm{cost}(\overrightarrow{\bm{a}})}.$

To upper bound the price of anarchy, we must lower bound the cost of the
socially optimal strategy and upper bound the cost of the worst Nash
equilibrium. By Corollary 1, we have the simple upper bound,

$\mathrm{PoA}(G)\leq\frac{\min\\{C,L\\}n}{\min_{\overrightarrow{\bm{a}}}\mathrm{cost}(\overrightarrow{\bm{a}})}$
(1)

with equality when there exists a Nash equilibrium with maximum possible cost,
$\min\\{C,L\\}n$.

###  1.2 Summary of results

This section contains the statements for all of our main results. For each, we
give a brief description of the conceptual idea behind each proof.

####  1.2.1 Bounding the PoA in terms of the maximum degree

It was proved in [ACY06] that the price of anarchy can be as large
$\Omega(n)$. Their lower bound is based on the star graph $K_{1,n-1}$ where
the optimal strategy (inoculating the root) has cost $O(1)$. Note that
inoculating the central node of the star is maximally “efficient,” in that it
splits the attack graph into $n-1$ components. This notion of efficiency
(i.e., number of components created per inoculation) is the crux of the
following result.

######  Theorem 3.

Let $G$ be a graph with maximum degree $\Delta$. Then,
$\mathrm{PoA}(G)=O(\sqrt{n\Delta})$ for all $C,L>0$.

###### Proof Idea..

We make two observations for the sake of lower bounding the social optimum:

  1. 1.

The number of components in the attack graph is bounded above by the number of
edges leaving secure nodes. Therefore, if every secure node has degree at most
$\Delta$, then there are at most $|I_{\overrightarrow{\bm{a}}}|\Delta$
insecure components.

  2. 2.

In the ideal case (i.e., the optimal strategy), all components will have the
same size.

Then, the result follows from a straightforward manipulation of Theorem 1.

∎

We note that bounds on the PoA in terms of the number of nodes and the maximum
degree have been stated before without proof. Please see the related work
section for more details.

We also show that Theorem 3 is the strongest possible upper bound; for
arbitrary values of $n$ and $\Delta$, we can construct a graph $G$ with price
of anarchy $\Omega(\sqrt{n\Delta})$.

######  Theorem 4.

For all $n\geq 4\Delta-2$ and $C\geq L$, there exists a graph $G$ with
$\displaystyle\mathrm{PoA}(G)=\Omega(\sqrt{n\Delta})$.

###### Proof Idea..

We construct a graph which is “ideal” with respect to notion of efficiency
used in Theorem 3. In particular, it should be possible to inoculate $\gamma$
nodes such that the attack graph contains $\gamma\Delta$ equally-sized
components.

Such a graph is not difficult to come by. For instance, when $\Delta=2$, the
cycle graph $C_{n}$ has this property for $\gamma=\sqrt{n}$; inoculating every
$\sqrt{n}$’th node will split the cycle into $\sqrt{n}$ paths of equal length
(up to rounding).

∎

####  1.2.2 The relationship between PoA, $C$ and $L$

We have seen that if $C=L$, then the strategy which inoculates no nodes is a
Nash equilibrium with cost $Ln$. Can we significantly decrease the cost of the
worst-case equilibrium (and PoA) by decreasing $C$, say to $L/2$? We prove
that there are graphs for which the worst-case Nash equilibrium has cost $Cn$
for any $0<C\leq L$ (i.e., Corollary 1 cannot be improved due to a matching
lower bound). This implies that the asymptotic PoA for these graphs remains
the same so long as $C/L=\Theta(1)$. We sketch the argument.

######  Lemma 1.

For a graph $G$, let $f(n):=\mathrm{PoA}(G)$ for costs $C=L$. Suppose that, if
$L$ remains fixed but the cost of inoculation decreases to $C^{\prime}<L$,
then there is a Nash equilibrium in the new game of cost $C^{\prime}n$. Let
$g(n):=\mathrm{PoA}(G)$ for costs $C^{\prime}$ and $L$. If
$C^{\prime}/L=\Theta(1)$, then $g(n)=\Omega(f(n)).$

###### Proof.

Reducing the cost of inoculation while keeping $L$ fixed can only decrease the
social optimum. On the other hand, by assumption, the cost of the worst case
Nash equilibrium for the new game is equal to $C^{\prime}n$. The result
follows as we have seen that, when $C=L$, the cost of the worst case Nash
equilibrium is exactly $Ln$.

∎

It follows that, to establish the asymptotic stability of PoA, it suffices to
prove that there is a Nash equilibrium with cost $Cn$ for all $C<L$. By
Theorem 2, when $C\geq L$, the pure strategy in which no node inoculates is a
Nash equilibrium with cost $Ln$. Similarly, if $C\leq L/n$, then the pure
strategy in which every node inoculates is a Nash equilibrium with cost $Cn$.
However, if $C\in(L/n,L)$, then it is not clear whether there is a Nash
equilibrium with cost $Cn$. We now show that, for certain graphs, _there is_ a
Nash equilibrium of cost $Cn$ for all $0<C<L$ therefore establishing the
asymptotic stability of the PoA for such graphs.

We say that a Nash equilibrium is _fractional_ if no node has a pure strategy;
every node $i$ chooses her action with probability differing from $0$,$1$.

######  Lemma 2.

The cost of every fractional Nash equilibrium is equal to $Cn$.

###### Proof.

Suppose strategy $\overrightarrow{\bm{a}}$ is a Nash equilibrium with
$a_{i}\in(0,1)$ for all $i$. As a consequence of Theorem 2, the expected
component size $S(i)=Cn/L$ for all $i$. Thus, probability of infection for any
node $i$ is equal to $p_{i}(\overrightarrow{\bm{a}})=C/L$. By definition,

$\mathrm{cost}(\overrightarrow{\bm{a}})=\sum_{i=1}^{n}C\cdot
a_{i}+L\cdot(1-a_{i})\frac{C}{L}=Cn.$

∎

It is non-trivial to show a fractional equilibrium exists (note that Nash’s
theorem does not guarantee existence because the space of fractional
strategies is not compact). However, it is possible to show that some graphs
will always exhibit such an equilibrium.

######  Theorem 5.

Let $G=K_{1,n-1}$ (i.e., the $n$-star). For all $C\in(L/n,L)$, there exists a
fractional Nash equilibrium.

###### Proof Idea..

The structure of the star enables us to explicitly calculate $S(i)$ for a
family of fractional strategies
$\\{\overrightarrow{\bm{a_{q}}}\\}_{q\in(0,1)}$. Furthermore, this family of
strategies has the property that $S(i)$ is the same continuous function of $q$
for all $i$, with $\lim_{q\to 0}S(i)=n$ and $\lim_{q\to 1}S(i)=1$. Thus, there
must exist a $q\in(0,1)$ such that $S(i)=Cn/L$ for all $i$ (i.e., a fractional
Nash equilibrium).

∎

In fact, we can show that if the graph is very symmetric, then there always
exists a fractional Nash equilibrium.

######  Theorem 6.

Suppose $G$ is vertex-transitive. Then, for all $C\in(L/n,L)$, there exists a
fractional Nash equilibrium.

###### Proof Idea..

Vertex-transitivity means that every pair of nodes $i\neq j$ are
indistinguishable based on local graph structure. Then, a sufficiently
“symmetric” strategy should exhibit symmetry in the expected component sizes.
Indeed, consider the strategy $\overrightarrow{\bm{a_{p}}}$ in which every
node inoculates with the same probability $p$. We prove that, under this
strategy, $S(i)$ is the _same_ continuous function of $p\in(0,1)$ for all $i$.
Thus, there must exist a $p$ such that $\overrightarrow{\bm{a_{p}}}$ is a
fractional Nash equilibrium.

∎

####  1.2.3 Bounding the PoA for larger thresholds of infection

We study the price of anarchy when the threshold of infection is higher; the
adversary initially infects two different nodes, and an insecure node becomes
infected if _multiple_ of its neighbors are infected. In particular, we prove
that the price of anarchy can still be $\Omega(n)$ in this scheme.

We first show that the price of anarchy can dramatically decrease when all
thresholds are $2$. Recall that [ACY06] proved that the star graph $K_{1,n-1}$
has price of anarchy $\Omega(n)$ (for threshold 1). In contrast, we have the
following:

######  Theorem 7.

Suppose that the threshold of every node is $2$. Then,
$\mathrm{PoA}(K_{1,n-1})=O(1)$.

###### Proof Idea..

Because a leaf has degree one, it can only become infected if chosen as the
starting point. This means that the only node whose cost is influenced by the
rest of the graph is the center. As the majority of players are effectively
independent, the price of anarchy must be relatively low.

∎

However, even when all thresholds equal $2$, there are still cases where the
price of anarchy is $\Omega(n)$.

######  Theorem 8.

If $C\geq L$, then there exists a graph $G$ for which
$\mathrm{PoA}(G)=\Omega(n)$.

###### Proof Idea..

When thresholds are $1$, the star has a high price of anarchy because any node
will infect the entire graph, but only one inoculation is required to split
the graph into many components. The natural idea for threshold $2$ is to
construct a graph in which any _two_ nodes will infect the entire graph, but
only two inoculations are required to split the graph into many components
(see Figure 3).

∎

###  1.3 Related work

The seminal paper of [ACY06] introduced the inoculation game and showed
constructively that every instance of the inoculation game has a pure Nash
equilibrium, and some instances have many. In the same paper, it is shown that
the price of anarchy for an arbitrary graph is at most $O(n)$, and that there
exists a graph with price of anarchy $n/2$. Subsequent work has studied PoA on
graph families such as grid graphs [MSW06] and expanders [KRSS10].

Several works have extended the basic model of [ACY06] to analyze the effect
of additional _behaviors_ on the PoA. For instance, [MSW06] extend the model
to include _malicious_ players whose goal is to maximize the cost to society.
They prove that the social cost deteriorates as the number of malicious
players increases, and the effect is magnified when the selfish players are
_unaware_ of the malicious players. Somewhat conversely, [CDK10] extend the
model to include _altruistic_ players who consider a combination of their
individual cost and the social cost (weighted by a parameter $\beta$). They
prove that the social cost does indeed decrease as $\beta$ increases. Finally,
[MOSW08] consider a notion of _friendship_ in which players care about the
welfare of their immediate neighbors. Interestingly, although a positive
friendship factor $F>0$ is always preferable, the social cost does not
necessarily decrease as $F$ increases.

The question of how to reduce the PoA has been studied before (e.g., [Rou06]).
For a survey regarding methods to reduce the PoA, see [RT07]. The general
question here is the following: how can we modify some aspect of a game to
lower the PoA? To this end, variations on the _infection process_ (rather than
the players) have also been studied; [KRSS10] examine the price of anarchy in
terms of the _distance_ , $d$, that the infection can spread from the starting
point. They prove that the when $d=1$, the price of anarchy is at most
$\Delta+1$, where $\Delta$ is the maximum degree of the graph. In this work,
we comment on a _complex contagion_ extension of the model, where nodes only
become infected if _multiple_ neighbors are infected. We show that this
modification does not unilaterally decrease the PoA. There is a vast
literature on complex contagion for variety of graph families [CLR79, SY16,
EMRS18, EGGS15, JŁTV12]. We are not aware of previous work that studies the
PoA in our setting where every node has threshold 2 for infection.

There are many classical models of epidemic spread. One of the most popular of
these is the _SIS model_ [Het73], which simulates infections like the flu,
where no immunity is acquired after having been infected (as opposed to the
_SIR model_ [KM27], in which individuals recover with permanent immunity). In
this model, it was shown by [DB02] that the strategy which inoculates the
highest-degree nodes in power-law random graphs has a much higher chance of
eradicating viruses when compared to traditional strategies. It is also known
that that the price of anarchy here increases as the expected proportion of
high-degree nodes decreases [SAV14]. Furthermore, it is established by
[WCWF03, GMT05, PCV+12] that epidemics die out quickly if the _spectral
radius_ (which is known to be related to the maximum degree [Cio07]) is below
a certain threshold. This initiated the development of graph algorithms
dedicated to minimizing the spectral radius by inoculating nodes [SAPV15].

[CDK10] consider the PoA in the inoculation game in graphs with maximum degree
$\Delta$. They state in their paper: “Indeed, we can show that even in the
basic model of Aspnes et al. without altruism, the Price of Anarchy is bounded
by $\sqrt{n\Delta}$ if all degrees are bounded by $\Delta$ (whereas the
general bound is $\Theta(n))$.” A similar statement is made in the PhD thesis
[Che11] of one of the authors of [CDK10]. Both [CDK10] and [Che11] do not
include proofs of these statements. We are not aware of a published proof of
either a lower bound or an upper bound for the PoA in graph in terms of the
maximum degree $\Delta$ and the number of nodes.

##  2 PoA in terms of maximum degree

In this section we prove Theorems 3 and 4.

######  Remark 3.

As a mixed strategy is simply a distribution over pure strategies, the optimal
cost can always be realized by a pure strategy. This enables the use of
Theorem 1 to bound the optimal cost.

###### Proof of Theorem 3.

Suppose $\gamma>0$ nodes are inoculated by strategy $\overrightarrow{\bm{a}}$
and let $k_{1}\leq\cdots\leq k_{\ell}$ denote the sizes of the connected
components in $G_{\overrightarrow{\bm{a}}}$. (If $\gamma=0$, then
$\mathrm{cost}(\overrightarrow{\bm{a}})=Ln$ and thus $\mathrm{PoA}(G)=1$.) By
convexity, $\sum_{i=1}^{\ell}k_{i}^{2}$ is minimized when all components have
the same size, $\displaystyle k_{i}=\frac{n-\gamma}{\ell}$ for all $i$. Thus,
the optimal solution has cost at least

$\mathrm{cost}(\overrightarrow{\bm{a^{*}}})\geq\min\\{C,L\\}\min_{\gamma}\left(\gamma+\frac{1}{n}\frac{\left(n-\gamma\right)^{2}}{\ell}\right)$
(2)

Note that every inoculation adds at most $\Delta$ components to the attack
graph (i.e., $\ell\leq\gamma\Delta$), and (2) becomes

$\mathrm{cost}(\overrightarrow{\bm{a^{*}}})\geq\min\\{C,L\\}\min_{\gamma}\left(\gamma\left(1+\frac{1}{\Delta
n}\right)+\frac{n}{\gamma\Delta}-\frac{2}{\Delta}\right)$

The function $\displaystyle f(\gamma)=\gamma\left(1+\frac{1}{\Delta
n}\right)+\frac{n}{\gamma\Delta}-\frac{2}{\Delta}$ is clearly convex and
attains its minimum when $\displaystyle\gamma=\frac{n}{\sqrt{1+\Delta n}}$.
Substituting this value yields

$\mathrm{cost}(\overrightarrow{\bm{a^{*}}})\geq\min\\{C,L\\}\frac{2\sqrt{n\Delta+1}-1}{\Delta}.$

Corollary 1 completes the proof. Note that the $\min\\{C,L\\}$ term is
cancelled out; the price of anarchy bound is independent of $C,L$.

∎

###### Proof of Theorem 4.

Consider an arbitrary $\Delta$-regular graph $G$ on $m=2\sqrt{n/\Delta}$
vertices $v_{1},\cdots,v_{m}$. We construct a new graph $G^{\prime}$ with $n$
vertices by replacing the edges of $G$ with (disjoint) paths of length
$\displaystyle\ell=(n-m)/(m\Delta/2)=\sqrt{n/\Delta}-2/\Delta$. (Round path
lengths such that the total number of nodes is $n$.)

Consider the strategy which secures $v_{1},\cdots,v_{m}$. The inoculations
cost $Cm$ and create $m\Delta/2$ components in $G^{\prime}$ of size $\ell$.
This strategy upper bounds the cost of the optimal strategy by

$Cm+L(n-m)\frac{\ell}{n}=2C\sqrt{n/\Delta}+2L\frac{\left(n-2\sqrt{n/\Delta}\right)^{2}}{\sqrt{n^{3}\Delta}}=O(\sqrt{n/\Delta}).$

As $C\geq L$, the worst case Nash equilibrium has cost $Ln$.

∎

Figure 2: The inoculation strategy for this instance the graph constructed in
Theorem 4 inoculates $4$ nodes, creating six disjoint paths of size $2$. This
has cost significantly lower than the worst Nash equilibrium which does not
inoculate at all.

##  3 Existence of fractional equilibria

In this section we prove Theorems 5 and 6.

###### Proof of Theorem 5.

Let $\overrightarrow{\bm{a}}$ be the strategy in which every leaf inoculates
with probability $p$ and the root inoculates with probability $q$. Then,

  * •

$S(\mathrm{root})=1+(1-p)(n-1)$,

  * •

$S(\mathrm{leaf})=q+(1-q)[2+(1-p)(n-2)]$.

It is easy to verify that $\displaystyle
S(\mathrm{root})=S(\mathrm{leaf})=\frac{n-q}{(n-2)q+1}$ when $\displaystyle
p=\frac{(n-1)q}{(n-2)q+1}$. The former expression is a continuous function of
$f(q):[0,1]\to[1,n]$, with $f(0)=n$ and $f(1)=1$. Thus, for all $\displaystyle
C\in(L/n,L)$, there exists a $q\in(0,1)$ such that $\displaystyle
S(\mathrm{root})=S(\mathrm{leaf})=\displaystyle\frac{Cn}{L}$ (i.e.,
$\overrightarrow{\bm{a}}$ is a fractional Nash equilibrium).

∎

###### Proof of Theorem 6.

We prove that there exists a $p\in(0,1)$ such that the strategy
$\overrightarrow{\bm{a_{p}}}=p^{n}$ is a fractional Nash equilibrium. By the
definition of vertex-transitivity, for any two nodes $i\neq j$, there exists
an automorphism $f:G\to G$ such that $f(i)=j$.

Consider an arbitrary set of inoculated nodes, $A$, and their image, $f(A)$.
By definition,

$\Pr(I_{\overrightarrow{\bm{a}}}=A)=\Pr(I_{\overrightarrow{\bm{a}}}=f(A))=p^{|A|}(1-p)^{n-|A|}$

Let $S(i|A)$ denote the size of the connected component containing $i$ in the
attack graph $G\setminus A$. By vertex transitivity,
$S(i|A)=S(f(i)|f(A))=S(j|f(A))$. Then, by linearity of expectation,

$\displaystyle S(i)$
$\displaystyle=\sum_{A}S(i|A)\Pr(I_{\overrightarrow{\bm{a}}}=A)$
$\displaystyle=\sum_{A}S(j|f(A))\Pr(I_{\overrightarrow{\bm{a}}}=f(A))=S(j).$

Also note that $S(i)$ is a polynomial in $p$ satisfying $\lim_{p\to 0}S(i)=n$
and $\lim_{p\to 1}S(i)=1$. Therefore, for all $\displaystyle C\in(L/n,L)$,
there exists a $p\in(0,1)$ such that $S(i)=Cn/L$ for all $i$.

∎

##  4 Larger thresholds of infection

In this section we prove Theorems 7 and 8.

###### Proof of Theorem 7.

Any leaf node has only one neighbor and can only be infected if chosen at the
start. Thus,

$p_{\mathrm{leaf}}(\overrightarrow{\bm{a}})=\frac{n-1}{\binom{n}{2}}=\frac{2}{n},$

and
$\displaystyle\mathrm{cost}_{\mathrm{leaf}}(\overrightarrow{\bm{a}})=Ca_{i}+\frac{2L(1-a_{i})}{n}$.
Then, for large enough $n$, no leaf node will inoculate in a Nash equilibrium.
Therefore, the worst case Nash equilibrium has cost at most

$\max\\{L,C\\}+L\cdot(n-1)\frac{2}{n}=\max\\{L,C\\}+2L\left(1-\frac{1}{n}\right)$

Now consider the optimal strategy. If at least one node inoculates with
probability $a_{i}\geq 1/2$, then
$\mathrm{cost}(\overrightarrow{\bm{a^{*}}})\geq C/2$. Otherwise, the root (if
insecure) is infected with probability at least $1/4$; either it is chosen at
the start, or two insecure nodes are chosen. As the root inoculates with
probability at most $1/2$, the optimal social cost is at least $L/8$.

∎

###### Proof of Theorem 8.

Consider the graph $G=K_{2,n-2}$ with an edge between the two nodes on the
smaller side. A Nash equilibrium where every node chooses not to inoculate has
cost $Ln$ as every two nodes will infect the entire graph. On the other hand,
the strategy which inoculate both nodes on the smaller side upper bounds the
cost of the social optimum by

$\mathrm{cost}(\overrightarrow{\bm{a^{*}}})\leq 2C+(n-2)\cdot
L\cdot\frac{2}{n}\leq 2(C+L)$

Hence $\mathrm{PoA}(G)=\Omega(n)$, concluding the proof.

∎

Figure 3: Inoculating the two central nodes of the graph constructed in
Theorem 8 is “efficient” as it splits the rest of the graph into $n-2$
singleton components. This has a much lower social cost than the Nash
equilibrium in which no node inoculates.

## Acknowledgements

We are grateful to James Aspnes, David Kempe and Ariel Procaccia for useful
comments. We thank the anonymous reviews for their feedback and suggesting a
simpler proof of Theorem 4. Part of this work was done while the third author
was visiting the Simons Institute for the Theory of Computing. Their
hospitality is greatly acknowledged.

## References

  * [ACY06] James Aspnes, Kevin Chang, and Aleksandr Yampolskiy.  Inoculation strategies for victims of viruses and the sum-of-squares partition problem.  Journal of Computer and System Sciences, 72(6):1077–1093, 2006\.
  * [BDS+22] Amy E Babay, Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas, and Anil Vullikanti.  Controlling epidemic spread using probabilistic diffusion models on networks.  In International Conference on Artificial Intelligence and Statistics, pages 11641–11654. PMLR, 2022.
  * [BDSZ16] Alfredo Braunstein, Luca Dall’Asta, Guilhem Semerjian, and Lenka Zdeborová.  Network dismantling.  Proceedings of the National Academy of Sciences, 113(44):12368–12373, 2016.
  * [BKW14] Itai Benjamini, Gady Kozma, and Nicholas Wormald.  The mixing time of the giant component of a random graph.  Random Structures & Algorithms, 45(3):383–407, 2014.
  * [CDK10] Po-An Chen, Mary David, and David Kempe.  Better vaccination strategies for better people.  In Proceedings of the 11th ACM conference on Electronic commerce, pages 179–188, 2010.
  * [Che11] Po-An Chen.  The effects of altruism and spite on games.  University of Southern California, 2011.
  * [Cio07] Sebastian M Cioabă.  The spectral radius and the maximum degree of irregular graphs.  arXiv preprint math/0702627, 2007.
  * [CLR79] John Chalupa, Paul L Leath, and Gary R Reich.  Bootstrap percolation on a bethe lattice.  Journal of Physics C: Solid State Physics, 12(1):L31, 1979.
  * [DB02] Zoltán Dezső and Albert-László Barabási.  Halting viruses in scale-free networks.  Physical Review E, 65(5):055103, 2002.
  * [EGGS15] Roozbeh Ebrahimi, Jie Gao, Golnaz Ghasemiesfeh, and Grant Schoenebeck.  Complex contagions in kleinberg’s small world model.  In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 63–72, 2015.
  * [EMRS18] Dean Eckles, Elchanan Mossel, M Amin Rahimian, and Subhabrata Sen.  Long ties accelerate noisy threshold-based contagions.  arXiv preprint arXiv:1810.03579, 2018.
  * [GMT05] Ayalvadi Ganesh, Laurent Massoulié, and Don Towsley.  The effect of network topology on the spread of epidemics.  In Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., volume 2, pages 1455–1466. IEEE, 2005\.
  * [Het73] Herbert W Hethcote.  Asymptotic behavior in a deterministic epidemic model.  Bulletin of Mathematical Biology, 35:607–614, 1973.
  * [JŁTV12] Svante Janson, Tomasz Łuczak, Tatyana Turova, and Thomas Vallier.  Bootstrap percolation on the random graph g_n,p.  The Annals of Applied Probability, 22(5):1989–2047, 2012.
  * [Jor69] Camille Jordan.  Sur les assemblages de lignes.  Journal für die reine und angewandte Mathematik, 1869.
  * [KM27] William Ogilvy Kermack and Anderson G McKendrick.  A contribution to the mathematical theory of epidemics.  Proceedings of the royal society of london. Series A, Containing papers of a mathematical and physical character, 115(772):700–721, 1927.
  * [Kri19] Michael Krivelevich.  Expanders-how to find them, and what to find in them.  In BCC, pages 115–142, 2019.
  * [KRSS10] VS Anil Kumar, Rajmohan Rajaraman, Zhifeng Sun, and Ravi Sundaram.  Existence theorems and approximation algorithms for generalized network security games.  In 2010 IEEE 30th International Conference on Distributed Computing Systems, pages 348–357. IEEE, 2010.
  * [LT79] Richard J Lipton and Robert Endre Tarjan.  A separator theorem for planar graphs.  SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.
  * [MOSW08] Dominic Meier, Yvonne Anne Oswald, Stefan Schmid, and Roger Wattenhofer.  On the windfall of friendship: inoculation strategies on social networks.  In Proceedings of the 9th ACM conference on Electronic commerce, pages 294–301, 2008.
  * [MSW06] Thomas Moscibroda, Stefan Schmid, and Rogert Wattenhofer.  When selfish meets evil: Byzantine players in a virus inoculation game.  In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 35–44, 2006.
  * [MV13] Madhav Marathe and Anil Kumar S Vullikanti.  Computational epidemiology.  Communications of the ACM, 56(7):88–96, 2013.
  * [PCV+12] B Aditya Prakash, Deepayan Chakrabarti, Nicholas C Valler, Michalis Faloutsos, and Christos Faloutsos.  Threshold conditions for arbitrary cascade models on arbitrary networks.  Knowledge and information systems, 33:549–575, 2012.
  * [Rou05] Tim Roughgarden.  Selfish routing and the price of anarchy.  MIT press, 2005.
  * [Rou06] Tim Roughgarden.  On the severity of braess’s paradox: Designing networks for selfish users is hard.  Journal of Computer and System Sciences, 72(5):922–953, 2006.
  * [RT02] Tim Roughgarden and Éva Tardos.  How bad is selfish routing?  Journal of the ACM (JACM), 49(2):236–259, 2002.
  * [RT07] Tim Roughgarden and Eva Tardos.  Introduction to the inefficiency of equilibria.  Algorithmic game theory, 17:443–459, 2007.
  * [SAPV15] Sudip Saha, Abhijin Adiga, B Aditya Prakash, and Anil Kumar S Vullikanti.  Approximation algorithms for reducing the spectral radius to control epidemic spread.  In Proceedings of the 2015 SIAM International Conference on Data Mining, pages 568–576. SIAM, 2015.
  * [SAV14] Sudip Saha, Abhijin Adiga, and Anil Vullikanti.  Equilibria in epidemic containment games.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
  * [SY16] Grant Schoenebeck and Fang-Yi Yu.  Complex contagions on configuration model graphs with a power-law degree distribution.  In Web and Internet Economics: 12th International Conference, WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings 12, pages 459–472. Springer, 2016.
  * [WCWF03] Yang Wang, Deepayan Chakrabarti, Chenxi Wang, and Christos Faloutsos.  Epidemic spreading in real networks: An eigenvalue viewpoint.  In 22nd International Symposium on Reliable Distributed Systems, 2003\. Proceedings., pages 25–34. IEEE, 2003.

##  Appendix A Other families

We also obtain price of anarchy bounds for planar graphs, trees, expanders and
Erdős-Renyi random graphs.

######  Theorem 9.

Let $G$ be a planar graph. If $C\geq L$, then
$\mathrm{PoA}(G)=\Omega(n^{1/3})$.

This is the best lower bound possible for planar graphs, as it was shown in
[MSW06] that a (planar) two-dimensional grid has price of anarchy
$O(n^{1/3})$. Clearly, planar graphs can have price of anarchy $\Omega(n)$, as
the classic star graph example is planar. Even for bounded degree planar
graphs, Theorem 4 showed that the lower bound can be as large as
$\Omega(\sqrt{\Delta n})$. Next, we apply a similar method to trees, obtaining
a stronger lower bound for this type of planar graph.

######  Theorem 10.

Let $T$ be a tree. If $C\geq L$, then $\mathrm{PoA}(T)=\Omega(\sqrt{n})$.

Finally, we show that the price of anarchy for well-connected graphs is
$O(1)$. These are graphs with the property that even the optimal strategy has
cost $\Omega(n)$. That is, the situation requires that a majority of
individuals either inoculate or get infected.

######  Theorem 11.

Let $G=G(n,p)$ for $\displaystyle p\geq\frac{1+\epsilon}{n}$ with
$\epsilon>0$. Then, $\mathrm{PoA}(G)=O(1)$ with high probability.

###  A.1 Planar graphs

Before proving Theorem 9, we state the _planar separator theorem_ :

######  Theorem 12 ([LT79]).

Let $G$ be a planar graph on $n$ nodes. There exists a partition of the nodes
$V=A\cup S\cup B$ such that

  * •

$|A|,|B|\leq n/2$

  * •

$|S|=O(\sqrt{n})$

  * •

There does not exist an edge between $A$ and $B$.

###### Proof of Theorem 9.

By Theorem 12, any planar graph $G$ can be split into $2$ components of size
at most $n/2$ by removing at most $O(\sqrt{n})$ nodes. Iteratively, these
components can both be split into $4$ total components of size at most $n/4$
by removing $2\cdot O(\sqrt{n/2})$ more nodes. Generally, the number of
inoculations required to create $\ell:=2^{k}$ components of size at most
$2^{-k}n$ is upper bounded by

$\sum_{i=1}^{k}2^{i}\cdot
O(\sqrt{n2^{-i}})=O(\sqrt{n})\cdot\sum_{i=1}^{k}2^{i/2}=O(\sqrt{n\ell}).$

By optimizing over $\ell$, we have that for any planar graph,

$\mathrm{cost}(\overrightarrow{\bm{a^{*}}})\leq C\cdot
O(\sqrt{n\ell})+\frac{L}{n}\cdot\ell\cdot\left(\frac{n}{\ell}\right)^{2}=O\left(C\sqrt{n\ell}+L\frac{n}{\ell}\right)=O(n^{2/3})$

∎

###  A.2 Trees

We obtain an analogous lower bound for trees by a slightly more efficient
separator theorem.

######  Theorem 13 ([Jor69]).

In any tree on $n$ nodes, there exists a node whose removal leaves components
of size at most $n/2$.

######  Lemma 3.

Let $T$ be a tree. $T$ can be split into components of size at most $\sqrt{n}$
by removing $O(\sqrt{n})$ nodes.

###### Proof.

By Theorem 13, $T$ can be split into multiple components of size at most $n/2$
by removing one node. Each of these components, in turn, can be split into
components of size at most $n/4$ by removing one node each. This process can
be repeated until all components have at most $\sqrt{n}$ nodes. Figure 4
illustrates this algorithm for a particular tree. We now prove that this
process requires $O(\sqrt{n})$ removals.

Let $N_{i}$ denote the number of components in the attack graph with size
greater than $n\cdot 2^{-i}$ but at most $n\cdot 2^{-i+1}$. Removing a node
from such a component (per Theorem 13) will decrease $N_{i}$ by one and
increase some $N_{j}$’s where $j>i$. Note that $N_{i}\leq 2^{i}$ as component
sizes sum to at most $n$. Therefore, the number of removals required to reduce
$N_{i}$ to $0$ for all $i\leq\log_{2}(\sqrt{n})$ is upper bounded by

$\sum_{i=1}^{\log_{2}(\sqrt{n})}2^{i}=2\sqrt{n}-2.$

∎

Figure 4: Following the algorithm given by Lemma 3 for this tree, we inoculate
node $a$, and then node $b$. If $C\geq L$, then this strategy achieves the
lower bound on PoA given by Theorem 10.

###### Proof of Theorem 10.

By Lemma 3, there exists a a strategy that inoculates $O(\sqrt{n})$ nodes,
leaving attack graph components of size at most $\sqrt{n}$. This leaves
$n-O(\sqrt{n})\leq n$ insecure nodes whose probability of infection is at most
$\sqrt{n}/n=1/\sqrt{n}$. Thus, the cost of this strategy upper bounds the
social optimum by

$\mathrm{cost}(\overrightarrow{\bm{a^{*}}})\leq C\cdot
O(\sqrt{n})+Ln\cdot\frac{1}{\sqrt{n}}\leq O(\sqrt{n}).$

∎

###  A.3 Random graphs

The proof of Theorem 11 amounts to the following two lemmas regarding
_expander_ graphs.

######  Definition 5.

An $n$-node graph $G=(V,E)$ is called an $\alpha$-expander if for every subset
$S$ of nodes with $|S|\leq n/2$, there are at least $\alpha|S|$ nodes in
$V\setminus S$ neighboring a node in $S$. (Here, $\alpha>0$ is a fixed
constant independent of $n$.)

The following lemma may be folklore, but we include the proof here for
completeness.

######  Lemma 4.

Suppose $G$ is an $\alpha$-expander. Then there exists constants
$\delta,\epsilon>0$ such that for every subset $A$ of $\delta n$ nodes,
removing $A$ from $G$ leaves a connected component of size at least $\epsilon
n$.

###### Proof.

Suppose that there is a subset of nodes $A$ of size $\alpha n/4$ such that
removing $A$ results with connected components $S_{1}\ldots S_{m}$ all of size
smaller than $\epsilon n$ where $\epsilon>0$ is a constant to be determined
later. This implies that there is a subset $S$ of nodes satisfying

$\left(\frac{1}{2}-\epsilon\right)n\leq|S|\leq\frac{n}{2}$

with at most $\alpha n/4$ neighbors in $V\setminus S$.

Indeed, initialize $S$ as the empty set and keep adding components $S_{i}$
(that were not added already) until $S$ has size at least $(1/2-\epsilon)n$.
Note that $S$ has cardinality no larger than $n/2$ and has at most $\alpha
n/4$ neighbors. For $\epsilon$ sufficiently small, this is a contradiction to
$G$ being an $\alpha$-expander.

∎

######  Remark 4.

Observe that the assertion in Lemma 4 applies also if $G$ contains a sub-graph
with $\Omega(n)$ nodes which is an $\alpha$-expander.

######  Lemma 5.

For a graph $G$, suppose there exists constants $\delta,\epsilon>0$ such that
for every subset $A$ of $\delta n$ nodes, removing $A$ from $G$ leaves a
connected component of size at least $\epsilon n$. Then,
$\mathrm{PoA}(G)=O(1)$.

###### Proof.

If removing $\delta n$ nodes leaves a component of size at least $\epsilon n$,
then

  * •

If $|I_{\overrightarrow{\bm{a^{*}}}}|\leq\delta n$, then
$\mathrm{cost}(\overrightarrow{\bm{a^{*}}})\geq L\epsilon^{2}n$.

  * •

If $|I_{\overrightarrow{\bm{a^{*}}}}|>\delta n$, then
$\mathrm{cost}(\overrightarrow{\bm{a^{*}}})>C\delta n$.

By Corollary 1, we have

$\mathrm{PoA}(G)\leq\frac{\min\\{C,L\\}n}{\min\\{C\delta,L\epsilon^{2}\\}n}=O(1).$

∎

###### Proof of Theorem 11.

Note that $G(n,p)$ may not be an $\alpha$-expander for fixed $\alpha>0$: If
edge probability $p=(1+\epsilon)/n$, then $G(n,p)$ contains an induced path of
length $\Omega(\log n)$ with high probability [BKW14]. Nevertheless, it is
known that if $p\geq(1+\epsilon)/n$, then $G(n,p)$ contains an
$\alpha$-expander with $\Omega(n)$ nodes with high probability (see [Kri19]).
Lemmas 4 and 5 complete the proof.

∎


# KoreALBERT: Pretraining a Lite BERT Model for Korean Language Understanding

Hyunjae Lee, Jaewoong Yoon, Bonggyu Hwang, Seongho Joe, Seungjai Min,
Youngjune Gwon  Samsung SDS

###### Abstract

A Lite BERT (ALBERT) has been introduced to scale up deep bidirectional
representation learning for natural languages. Due to the lack of pretrained
ALBERT models for Korean language, the best available practice is the
multilingual model or resorting back to the any other BERT-based model. In
this paper, we develop and pretrain KoreALBERT, a monolingual ALBERT model
specifically for Korean language understanding. We introduce a new training
objective, namely Word Order Prediction (WOP), and use alongside the existing
MLM and SOP criteria to the same architecture and model parameters. Despite
having significantly fewer model parameters (thus, quicker to train), our
pretrained KoreALBERT outperforms its BERT counterpart on 6 different NLU
tasks. Consistent with the empirical results in English by Lan et al.,
KoreALBERT seems to improve downstream task performance involving multi-
sentence encoding for Korean language. The pretrained KoreALBERT is publicly
available to encourage research and application development for Korean NLP.

##  I Introduction

Pre-trained language models are becoming an essential component to build a
modern natural language processing (NLP) application. Previously, recurrent
neural nets such as LSTM have dominated sequence-to-sequence (seq2seq) [1]
modeling for natural languages, upholding state-of-the-art performances for
core language understanding tasks. Since the introduction of the Transformer
[2], recurrent structures in a neural language model are reconsidered and
opted for attention, a mechanism that relates different positions in a
sequence to compute a representation of the sequence.

Devlin  _et al._ [3] have proposed Bidirectional Encoder Representations from
Transformers (BERT) to improve on predominantly unidirectional training of a
language model by using the masked language model (MLM) training objective.
MLM is an old concept dating back to the 1950s [4]. By jointly conditioning on
both left and right context in all layers, the MLM objective has made pre-
training of the deep bidirectional language encoding possible. BERT uses an
additional loss for pre-training known as next-sentence prediction (NSP). NSP
is designed to learn high-level linguistic coherence by predicting whether or
not given two text segments should appear consecutively as in the original
text. NSP can improve performance on downstream NLP tasks such as natural
language inference that would require reasoning about inter-sentence
relations.

A Lite BERT (ALBERT) uses parameter reduction techniques to alleviate scaling
problems for BERT. ALBERT’s cross-layer parameter sharing can be thought as a
form of regularization that helps stabilize the pre-training and generalize
despite the substantially reduced number of model parameters. Also, the
sentence order prediction (SOP) objective in ALBERT replaces the ineffective
the next sentence prediction (NSP) loss in BERT for better inter-sentence
coherence.

Downstream tasks play critical measures for evaluating emerging language
models and NLP applications today. Pre-trained language models are central to
downstream task evaluations such as machine translation, text classification,
and machine reading comprehension. At a high level, there are two approaches
to use pre-trained language models. First, pre-trained models can provide
additional feature representations for a downstream task. More importantly,
pre-trained models can be a baseline upon which the downstream task is fine-
tuned.

By having an expensive, but shareable pre-training followed by much smaller
fine-tuning, it is a powerful paradigm to focus on optimizing the performance
of a downstream NLP task. Self-supervised learning with large corpora allows a
suitable starting point for an outer task-specific layer being optimized from
scratch while reusing the pre-trained model parameters.

Since its introduction, BERT has achieved state-of-the-art accuracy
performances for natural language understanding tasks such as GLUE [5],
MultiNLI [6], SQuAD v1.1 [7] & SQuAD v2.0 [8], and CoNLL-2003 NER [9]. Despite
having fewer parameters than BERT, ALBERT has been able to achieve new state-
of-the-art results on the GLUE, RACE [10], and SQuAD benchmarks.

It is important to remark that a large network is crucial in pushing state-of-
the-art results for downstream tasks. While BERT gives a sound choice to build
a general language model trained on large corpora, it is difficult to
experiment with training large BERT models due to the memory limitations and
computational constraints. Training BERT-large in fact is a lengthy process of
consuming significant hardware resources. Besides, there are already a wide
variety of languages pre-trained in BERT, which include the multilingual BERT
and monolingual models pre-trained in 104 different languages. ALBERT,
however, gives a much narrower choice in languages.

Asserting an argument that having a better language model is roughly
equivalent to pre-train a large model, all without imposing too much memory
and computational requirements, we choose to go with ALBERT. In this paper, we
develop and train KoreALBERT, a monolingual ALBERT model for Korean language
understanding. Compared to a multilingual model, monolingual language models
are known to optimize the performance for a specific language in every aspect,
including downstream tasks critical to build modern NLP systems and
applications.

In addition to the original ALBERT MLM and SOP training objectives, we
introduce a word order prediction (WOP) loss. WOP is fully compatible with the
MLM and SOP losses and can be added gracefully in implementation. Our pre-
trained KoreALBERT could outperform multilingual BERT and its BERT counterpart
on a brief evaluation with KorQuAD 1.0 benchmark for machine reading
comprehension. Consistent with the empirical results of ALBERT pre-trained in
English reported by Lan  _et al._ [11], KoreALBERT seems to improve supervised
downstream task performances involving multiple Korean sentences.

The rest of this paper is organized as follows. In Section II, we provide
background on pre-trained neural language models. Section III presents
KoreALBERT. In Section IV, we describe our implementation, pre-training, and
empirical evaluation of KoreALBERT. Section V concludes the paper. Our pre-
trained KoreALBERT is publicly available to encourage NLP research and
application development for Korean language.

##  II Background

###  II-A Transformer, BERT, and ALBERT

Transformer [2] is a sequence transduction model based solely on attention
mechanism, skipping any recurrent and convolutional structures of a neural
network. The transformer architecture includes multiple identical encoder and
decoder blocks stacked on top of each other. While the encoder captures
linguistic information of the input sequence and produces the contextual
representations, the decoder generates output sequence corresponding to its
pair of input. Thanks to multi-head self-attention layers in an encoder block,
transformer can acquire varying attentions within a single sequence and
alleviate inevitable dragging caused during the training of a recurrent neural
network.

BERT distinguishes itself from other language models that predict the next
word given previous words by introducing new training methods. Instead of
predicting the next token given only previous tokens, it has to predict
replaced word by special token [MASK]. This training strategy gives BERT
bidirectionality which means having an access to left and right context around
the target word. Thus, BERT can produce deep bidirectional representation of
input sequence.

RoBERTa [12], ALBERT [11] and other variants [13, 14] utilize bidirectional
context representation and established state-of-the-art results on a wide
range of NLP tasks. BERT is trained with the masked language modeling (MLM)
and the next sentence prediction (NSP) losses. NSP is a binary classification
task to predict whether or not given two segments separated by another special
token [SEP] follow each other in the original text. The task is intended to
learn the relationship between two sentences in order to use on many
downstream tasks of which input template consists of two sentences as in
question answering (QA) and sentence entailment [3].

Recently, there is a criticism toward NSP that the NSP loss does not
necessarily help improve the downstream task performances [11, 12, 15] for its
loose inter-sentential coherence. Among them, ALBERT, whose architecture is
derived from BERT, uses a sentence order prediction(SOP) task instead. In the
SOP task, negative examples consist of a pair of sentences from the same
document, but the sentence order is swapped, and the model should predict
whether or not the order is swapped. With the improved SOP loss and other
parameter reduction techniques, ALBERT significantly reduces the number of
parameters– _i.e._ , 18x fewer for BERT-large, while achieving similar or
better performance on downstream tasks [11]. KoreALBERT takes the unmodified
ALBERT architecture as a baseline. We train KoreALBERT from scratch on large
Korean corpora collected online.

###  II-B Related Work

Google has released BERT multilingual model (M-BERT) pre-trained using 104
different languages including the Korean. Karthikeyan  _et al._ [16] show why
and how well M-BERT works on many downstream NLP tasks without explicitly
training with monolingual corpus. More recently, Facebook AI Research
presented crosslingual model (XLM-R) [17] generally outperforming M-BERT.
Recent literature argues that a monolingual language model is consistently
superior to M-BERT. For French, FlauBERT [18] and CamemBERT [19] with the same
approach as RoBERTa have been released. ALBERTo [20] focuses on Italian social
network data. BERTje [21] for Dutch and FinBERT [22] for Finnish have been
developed. They both have achieved superior results on the majority of
downstream NLP tasks compared to M-BERT.

Some previous work in the Korean language has focused on learning static
representations by using language-specific properties [23]. More recently, SKT
Brain has released BERT 111https://github.com/SKTBrain/KoBERT and GPT-2 pre-
trained on large Korean corpora.222https://github.com/SKT-AI/KoGPT2 Korean
Electronics and Telecommunications Research Institute (ETRI) has released two
versions of BERT: the morpheme analytic based and the syllable based
model.333http://aiopen.etri.re.kr/service_dataset.php These models are
worthwhile to experiment with and provide good benchmark evaluations in Korean
language model research.

BART [24] features interesting denoising approaches for input text used in
pre-training such as sentence permutation and text infilling. In the sentence
permutation task, an input document is divided into sentences and shuffled in
a random order. A combination of text infilling and sentence shuffling tasks
has shown significant improvement of the performance over either applied
separately. Inspired by BART, we have formulated word order prediction (WOP),
a new pre-training loss used alongside the MLM and SOP losses for KoreALBERT.
Differentiated from BART, which is essentially a sentence-level shuffling, WOP
is an intra-sentence, token-level shuffling.

##  III KoreALBERT: Training Korean Language Model Using ALBERT

###  III-A Architecture

KoreALBERT is a multi-layer bidirectional Transformer encoder with the same
factorized embedding parameterization and cross-layer sharing as ALBERT.
Inheriting ALBERT-base, KoreALBERT-base has 12 parameter sharing layers with
an embedding size of 128 dimensions, 768 hidden units, 12 heads, and GELU
nonlinearities [25]. The total number of parameters in KoreALBERT-base is 12
millions, and it increases to 18-million parameters for KoreALBERT-large
having 1024 hidden dimensions.

Lan  _et al._ [11] argues that removing dropout has significantly helped
pretraining with the masked language modeling (MLM) loss. For KoreALBERT,
however, we have made an empirical decision to keep dropout after observing
degraded downstream performances without dropout.

###  III-B Training Objectives

ALBERT pretrains on two objectives: masked language modeling (MLM) and
sentence order prediction (SOP) losses. We keep both objectives for KoreALBERT
and introduce an additional training objective called word order prediction
(WOP).

Word Order Prediction (WOP). Korean is an agglutinative language that a
combination of affixes and word roots determines usage and meaning [26].
Decomposing a Korean word into several morphemes and shuffling its order can
introduce grammatical errors and semantic altercations. We impose a word order
prediction (WOP) loss for pretraining KoreALBERT. The WOP objective is a
cross-entropy loss on predicting a correct order of shuffled tokens.

WOP is fully compatible with the ALBERT MLM and SOP, and we expect to
reinforce correct agglutination (or point out incorrect agglutinative usages)
beyond simply checking intra-sentence word orderings. There is an interesting
point of view about WOP mixed with MLM and SOP towards the problem of
generating a full sentence from a small subset of permuted words. Our primary
focus of this paper is on the empirical side of the design and pretraining of
an ALBERT-based foreign language model rather than a formal analysis on
training objectives.

The pretraining of KoreALBERT is illustrated in Fig. 1. A randomly sampled
subset of tokens in the input text are replaced with [MASK]. MLM computes a
cross-entropy loss on prediction of the masked tokens. As with ALBERT-base, we
uniformly choose 15% of the input tokens for possible masking, and the 80% of
the chosen are actually replaced with [MASK], leaving 10% unchanged and the
rest replaced with randomly selected tokens. SOP is known to focus on modeling
inter-sentence coherence. The SOP loss uses two consecutive segments from the
same text as a positive example and as a negative example if their order is
swapped. We have found that if WOP is too difficult, it can crucially impact
the KoreALBERT performance on downstream evaluations.

We have experimentally determined WOP to inter-work with MLM and SOP and
limited the shuffling rate up to 15%, which seemingly realizes the best
empirical performance for our case. In addition, we have decided to include
WOP into only specific portion of all batches. We revisit more detailed
description of our experimental setup in Section 4. Like MLM, we choose a
uniformly random set of tokens for WOP. The most crucial part of integrating
WOP into pretraining is _not_ switching tokens across [MASK]. This constraint
minimizes the corruption of contextual bidirectionality that acts as essential
information in denoising the [MASK] tokens.

Figure 1: Pre-training KoreALBERT with the MLM, SOP, and WOP objectives. The
loss (on top) with respect to all three objectives is calculated for
illustrative purposes. In our implementation, classification layer
(highlighted gray) in the middle consisting of three identical heads produces
a logit vector with respect to each label.

###  III-C Optimization

We use the LAMB optimizer [27] with a learning rate of $1.25\times 10^{-3}$
and a warm-up ratio $1.25\times 10^{-2}$. To speed up the pretraining, we
maintain an input sequence length of 128 tokens despite the risk of suboptimal
performance. Due to memory limitations, it is necessary to use gradient
accumulation steps for a batch size of 2,048, which is comparable to BERT. We
apply a dropout rate of 0.1 on all layers and attention weights. We use a GELU
activation function [25].

##  IV Experiments

###  IV-A Implementation

We implement KoreALBERT based on Hugging Face’s transformer library [28] with
almost an identical model configuration for ALBERT-base. We add another linear
classifier on top of the encoder output for WOP task. The added layer is used
to predict the probability of the original position of words in the sequence
via softmax. Like the MLM objective, we take into account only switched tokens
to compute the cross-entropy loss. We train our model using 4 NVidia V100 GPUs
with half-precision floating-point weights.

###  IV-B Data

Many BERT-style language models include Wikipedia in the pre-training corpora
for a wide coverage of topics in relatively high-quality writing. Korean
Wikipedia currently ranks the 23rd by volume, and this is just 7.8% compared
to English Wikipedia. To supplement training examples and the diversity of our
corpus, we also use the text from
NamuWiki444https://en.wikipedia.org/wiki/Namuwiki, which is another Korean
online encyclopedia that contains more subjective opinions covering a variety
of topics and writing styles.

####  IV-B1 Pretraining corpora

our pretraining corpora include the following.

  * •

Web News: all articles from 8 major newspapers of Korea accross the topics
including politics, social, economics, culture, IT, opinion, and sports from
January 1, 2007 to December 31, 2019.

  * •

Korean Wikipedia: 490,220 documents crawled in October, 2019.

  * •

NamuWiki: 740,094 documents crawled in December, 2019.

  * •

Book corpus: plots and editorial reviews about all Korean books published in
2010 to December 31, 2019555http://book.interpark.com/

####  IV-B2 Text preprocessing

We have preprocessed our text data in the following manner. First, we remove
all meta-tags such as the date of writing and name(s) of the author(s) in
newspapers appearing in the beginning and at the end of each article. We think
that the meta-tags do not contain any contextual or semantic information
essential for NLU tasks. We also adjust the proportion of categories making up
the news corpus in order to avoid topical bias of the examples. We tokenize
the corpora into subwords using SentencePiece tokenizer [29] like ALBERT to
construct vocabulary of a size 32k. We mask randomly sampled 15% of the words
using the whole word masking strategy recently introduced by BERT. After
cleaning and regularizing text, we obtain 43GB text with 325 million
sentences, which are equivalent to 4.4 billion words or 18 billion characters.

###  IV-C Compatibility of Word Order Prediction (WOP)

We have performed ablation experiments with and without WOP to empirically
observe its compatibility with the MLM and SOP objectives by pretraining for
125K steps, which is the half of the entire pre-training. A critical decision
to introduce new noise via WOP is how many training examples should entail the
additional noising process as well as how many tokens should be shuffled
inside a sentence. We sample batches to contain re-ordered tokens
proportionally from 30 to 100%. We have observed that about 30-50% shuffling
achieves a good performance for most cases. Results are averaged over 10
different seeds and summarized in Table I.

We set up three combinations of the pretraining objectives to compare against
one another in the downstream evaluations to highlight the effect of WOP. We
also observe the intrinsic performance of each objective. In the WOP and MLM
combination, we configure the portion of corrupted examples to 30% for the WOP
objective. From the result averaged over 10 different seeds in Table II, WOP
hardly hurts the performance of MLM or SOP. The accuracy of MLM and WOP tasks
has improved in case of leaving the SOP objective out. We believe that the
best usage for WOP is not to disturb other intrinsic tasks for pretraining.
WOP should be added by carefully observing the performance of other objectives
on different WOP configurations.

As expected, the deletion of SOP has caused a degradation more than 3% in the
downstream performances of semantic textual similarity (8,628 examples) and
paraphrase detection (7,576 examples). These two tasks are relatively small
data experiments. Surprisingly, the performance of KorNLI is better without
SOP because NLI tasks depend on inter-sentence coherence. Note that KorNLI is
a much larger dataset (950,354 examples) compared to the semantic textual
similarity and paraphrase detection datasets. Combining the two denoising
objectives MLM and WOP seems to alleviate the performance degradation for a
classification task with multi-sentence input.

TABLE I: Experimental results on downstream tasks according to different portion of word order prediction tasks Portion of WOP | KorNLI | KorSTS | NSMC | PD | NER | KorQuAD1.0
---|---|---|---|---|---|---
acc | spearman | acc | acc | acc | f1
100 % | 76.8 | 74.8 | 88.3 | 92.3 | 80.6 | 89.4
50 % | 76.4 | 76.6 | 88.3 | 92.7 | 81.2 | 89.3
30 % | 76.6 | 75.4 | 88.4 | 93.2 | 80.7 | 89.8
TABLE II: Experimental results on Downstream task performance comparing between different combination of pretraining objectives Objectives | MLM | SOP | WOP | KorNLI | KorSTS | NSMC | PD | NER | KorQuAD1.0
---|---|---|---|---|---|---|---|---|---
acc | acc | acc | acc | spearman | acc | acc | acc | f1
MLM + SOP | 35.3 | 79.8 | - | 76.4 | 75.6 | 88.6 | 92.9 | 80.7 | 89.5
MLM + SOP + WOP | 35.1 | 79.1 | 80.7 | 76.9 | 76.6 | 88.4 | 93.2 | 81.2 | 89.8
MLM + WOP | 35.6 | - | 84.0 | 76.8 | 73.3 | 88.5 | 92.3 | 81.0 | 89.3
TABLE III: Experimental results on downstream tasks and model parameters Model | Params | Speedup | KorNLI | KorSTS | NSMC | PD | NER | KorQuAD1.0 | Avg.
---|---|---|---|---|---|---|---|---|---
acc | spearman | acc | acc | acc | f1
Multilingual BERT | 172M | 1.0 | 76.8 | 77.8 | 87.5 | 91.1 | 80.3 | 86.5 | 83.3
XLM-R | 270M | 0.5x | 80.0 | 79.4 | 90.1 | 92.6 | 83.9 | 92.3 | 86.4
KoBERT | 92M | 1.2x | 78.3 | 79.2 | 90.1 | 91.1 | 82.1 | 90.3 | 85.2
ETRI BERT | 110M | - | 79.5 | 80.5 | 88.8 | 93.9 | 82.5 | 94.1 | 86.6
KoreALBERT Base | 12M | 5.7x | 79.7 | 81.2 | 89.6 | 93.8 | 82.3 | 92.6 | 86.5
KoreALBERT Large | 18M | 1.3x | 81.1 | 82.1 | 89.7 | 94.1 | 83.7 | 94.5 | 87.5

###  IV-D Evaluation

We fine-tune KoreALBERT for downstream performance evaluations. For
comparison, we consider other pretrained BERT-base language models available
off-the-shelf.

####  IV-D1 Fine-tuning

In addition to our KoreALBERT, we have downloaded pretrained models available
online: multilingual BERT666https://github.com/google-research/bert, XLM-R
from Facebook AI Research777https://github.com/facebookresearch/XLM,
KoBERT888https://github.com/SKTBrain/KoBERT, and ETRI
BERT999http://aiopen.etri.re.kr/service_dataset.php. We optimize respective
hyperparameters for each pretrained model before measuring the best and
average scores for each model. For all models, we use a batch size of 64 or
128 and from 3 to 5 epochs with a learning rate from $2.0\times 10^{-5}$ to
$5.0\times 10^{-5}$ and a max-sequence length from 128 to 512. For NER task,
we have found out that longer training epochs tend to work better and fine-
tuned up to 7 epochs.

####  IV-D2 Downstream Tasks

We consider six downstream NLP tasks detailed below.

  * •

KorNLI: Korean NLU Dataset includes two downstream tasks. In Korean Natural
Language Inference (KorNLI) [30], the input is a pair of sentences, a premise
and a hypothesis. The fine-tuned model should predict their relationship in
one of the three possible labels: entailment, contradiction, and neutral.
KorNLI has a total of 950,354 examples.

  * •

KorSTS: the second task from Korean NLU is semantic textual similarity (STS)
for Korean language. STS requires to predict how semantically similar the two
input sentences are on a 0 (dissimilar) to 5 (equivalent) scale. There are
8,628 KorSTS examples in the Korean NLU dataset.

  * •

Sentiment analysis: we use Naver Sentiment Movie
Corpus,101010https://github.com/e9t/nsmc (NSMC) the biggest Korean movie
review dataset, which is collected by the same method that the massive movie
review dataset [31] proposes. NSMC consists of 200k reviews of shorter than
140 characters that are labeled with human annotations of sentiment.

  * •

Paraphrase detection (PD): a PD model predicts whether or not a pair of
sentences are semantically equivalent. The dataset we consider contains 7,576
examples from a publicly available github
repository.111111https://github.com/songys/Question_pair

  * •

Extractive machine reading comprehension (EMRC): EMRC takes in much longer
text sequences as an input compared to other tasks. The EMRC model needs to
extract the start and end indices inside a paragraph containing the answer of
a question. KorQuAD 1.0 [32] is a Korean dataset for machine reading
comprehension, which is similar to SQuAD 1.0 [7]. Having exactly the same
format as SQuAD, KorQuAD 1.0 comprises 60,407 question-answer pairs.

  * •

Named entity recognition (NER): NER distinguishes a real-world object such as
a person, organization, and place (location) from documents. We use the NER
corpus121212http://air.changwon.ac.kr/?page_id=10 constructed by Naver Corp.
and Changwon University in South Korea. The corpus has 14 different types of
entities with attached tags B/I/-, denoting multi- or single-word entities as
described in Table IV.

TABLE IV: Proportion of the type of entities of NER dataset. Category | Tag | Amount
---|---|---
NUMBER | NUM | 64,876
CIVILIZATION | CVL | 60,918
PERSON | PER | 48,321
ORGANIZATION | ORG | 45,550
DATE | DAT | 33,944
TERM | TRM | 22,070
LOCATION | LOC | 21,095
EVENT | EVT | 17,430
ANIMAL | ANM | 6,544
ARTIFACTS_WORKS | AFW | 6,069
TIME | TIM | 4,337
FIELD | FLD | 2,386
PLANT | PLT | 267
MATERIAL | MAT | 252

###  IV-E Discussion

As indicated in Table III, KoreALBERT consistently outperforms M-BERT over all
downstream NLU tasks considered. While KoreABLERT has the smallest number of
model parameters among all monolingual and multilingual language models
compared in this paper, it achieves better results in almost all downstream
evaluations. The advantage of having fewer computations of KoreALBERT makes
its base model about 5.7 faster than M-BERT and its large model 2.2 faster
than XLM-R base at training time.

In NSMC and NER, which are single-sentence classification tasks, KoreALBERT is
subpar against XLM-R and KoBERT. For NSMC, KoreALBERT-large cannot produce
more discriminnative result than the base model. We suspect the main reason
for the performance drop being lack of covering the colloquial usage of words
and phrases in our pretraining corpora that mostly consists of more formal
style of writings such as news articles and wikipedia. Examples in NSMC seem
to use much colloquialism. Also, XLM-R has shown a very good performance on
the NER task. Such result is due to the fact that NER does not require much
high-level language understanding like multi-sentence discourse coherence.

##  V Conclusion

We have introduced KoreALBERT, a pre-trained monolingual ALBERT model for
Korean language understanding. We have described the details about training
KoreALBERT. In particular, we have proposed a word order prediction loss, a
new training objective, which is compatible with the original MLM and SOP
objectives of ALBERT. KoreALBERT consistently outperforms multi and
monolingual baselines on 6 downstream NLP tasks while having much fewer
parameters. In our future work, we plan to experiment more comprehensively
with the KoreALBERT WOP loss: i) replace token-level switching with word-level
switching to improve the difficulty of label prediction; ii) use dynamic token
shuffling with varying amount of tokens to be shuffled instead of fixed
proportion. We also plan to investigate how well the proposed WOP loss works
with non-agglutinative languages like English.

## References

  * [1] I. Sutskever, O. Vinyals, and Q. V. Le, “Sequence to sequence learning with neural networks,” _CoRR_ , vol. abs/1409.3215, 2014. [Online]. Available: http://arxiv.org/abs/1409.3215
  * [2] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in Neural Information Processing Systems 30_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds. Curran Associates, Inc., 2017, pp. 5998–6008. [Online]. Available: http://papers.nips.cc/paper/7181-attention-is-all-you-need.pdf
  * [3] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of Deep Bidirectional Transformers for Language Understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [4] W. L. Taylor, “Cloze Procedure: a New Tool for Measuring Readability,” _Journalism Quarterly_ , vol. 30, no. 4, pp. 415–433, 1953.
  * [5] A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. Bowman, “Glue: A multi-task benchmark and analysis platform for natural language understanding,” _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , 2018. [Online]. Available: http://dx.doi.org/10.18653/v1/w18-5446
  * [6] A. Williams, N. Nangia, and S. Bowman, “A broad-coverage challenge corpus for sentence understanding through inference,” _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , 2018. [Online]. Available: http://dx.doi.org/10.18653/v1/N18-1101
  * [7] P. Rajpurkar, J. Zhang, K. Lopyrev, and P. Liang, “Squad: 100, 000+ questions for machine comprehension of text,” _CoRR_ , vol. abs/1606.05250, 2016. [Online]. Available: http://arxiv.org/abs/1606.05250
  * [8] P. Rajpurkar, R. Jia, and P. Liang, “Know what you don’t know: Unanswerable questions for squad,” _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , 2018. [Online]. Available: http://dx.doi.org/10.18653/v1/P18-2124
  * [9] E. F. Tjong Kim Sang and F. De Meulder, “Introduction to the conll-2003 shared task,” _Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003 -_ , 2003. [Online]. Available: http://dx.doi.org/10.3115/1119176.1119195
  * [10] G. Lai, Q. Xie, H. Liu, Y. Yang, and E. Hovy, “RACE: Large-scale ReAding comprehension dataset from examinations,” in _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_. Copenhagen, Denmark: Association for Computational Linguistics, Sep. 2017, pp. 785–794. [Online]. Available: https://www.aclweb.org/anthology/D17-1082
  * [11] Z. Lan, M. Chen, S. Goodman, K. Gimpel, P. Sharma, and R. Soricut, “Albert: A Lite BERT for Self-supervised Learning of Language Representations,” _arXiv preprint arXiv:1909.11942_ , 2019.
  * [12] Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoyanov, “Roberta: A robustly optimized BERT pretraining approach,” _CoRR_ , vol. abs/1907.11692, 2019. [Online]. Available: http://arxiv.org/abs/1907.11692
  * [13] M. Joshi, D. Chen, Y. Liu, D. S. Weld, L. Zettlemoyer, and O. Levy, “Spanbert: Improving pre-training by representing and predicting spans,” _CoRR_ , vol. abs/1907.10529, 2019. [Online]. Available: http://arxiv.org/abs/1907.10529
  * [14] Y. Cui, W. Che, T. Liu, B. Qin, Z. Yang, S. Wang, and G. Hu, “Pre-training with whole word masking for chinese BERT,” _CoRR_ , vol. abs/1906.08101, 2019. [Online]. Available: http://arxiv.org/abs/1906.08101
  * [15] Z. Yang, Z. Dai, Y. Yang, J. G. Carbonell, R. Salakhutdinov, and Q. V. Le, “Xlnet: Generalized autoregressive pretraining for language understanding,” _CoRR_ , vol. abs/1906.08237, 2019. [Online]. Available: http://arxiv.org/abs/1906.08237
  * [16] K. K, Z. Wang, S. Mayhew, and D. Roth, “Cross-lingual ability of multilingual bert: An empirical study,” 2019.
  * [17] A. Conneau, K. Khandelwal, N. Goyal, V. Chaudhary, G. Wenzek, F. Guzmán, E. Grave, M. Ott, L. Zettlemoyer, and V. Stoyanov, “Unsupervised cross-lingual representation learning at scale,” 2019.
  * [18] H. Le, L. Vial, J. Frej, V. Segonne, M. Coavoux, B. Lecouteux, A. Allauzen, B. Crabbé, L. Besacier, and D. Schwab, “Flaubert: Unsupervised language model pre-training for french,” 2019.
  * [19] L. Martin, B. Muller, P. J. O. Suárez, Y. Dupont, L. Romary, Éric Villemonte de la Clergerie, D. Seddah, and B. Sagot, “Camembert: a tasty french language model,” 2019.
  * [20] M. Polignano, P. Basile, M. de Gemmis, G. Semeraro, and V. Basile, “Alberto: Italian bert language understanding model for nlp challenging tasks based on tweets,” 11 2019.
  * [21] W. Vries, A. Cranenburgh, A. Bisazza, T. Caselli, G. van Noord, and M. Nissim, “Bertje: A dutch bert model,” 12 2019.
  * [22] A. Virtanen, J. Kanerva, R. Ilo, J. Luoma, J. Luotolahti, T. Salakoski, F. Ginter, and S. Pyysalo, “Multilingual is not enough: Bert for finnish,” 12 2019.
  * [23] S. Park, J. Byun, S. Baek, Y. Cho, and A. Oh, “Subword-level word vector representations for korean,” 01 2018, pp. 2429–2438.
  * [24] M. Lewis, Y. Liu, N. Goyal, M. Ghazvininejad, A. Mohamed, O. Levy, V. Stoyanov, and L. Zettlemoyer, “Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension,” 2019.
  * [25] D. Hendrycks and K. Gimpel, “Bridging nonlinearities and stochastic regularizers with gaussian error linear units,” _CoRR_ , vol. abs/1606.08415, 2016. [Online]. Available: http://arxiv.org/abs/1606.08415
  * [26] J. J. Song, “The korean language:structure, use and context,” _Routledge_ , 2006.
  * [27] Y. You, J. Li, J. Hseu, X. Song, J. Demmel, and C. Hsieh, “Reducing BERT pre-training time from 3 days to 76 minutes,” _CoRR_ , vol. abs/1904.00962, 2019. [Online]. Available: http://arxiv.org/abs/1904.00962
  * [28] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, and J. Brew, “Huggingface’s transformers: State-of-the-art natural language processing,” _ArXiv_ , vol. abs/1910.03771, 2019.
  * [29] T. Kudo and J. Richardson, “Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing,” _CoRR_ , vol. abs/1808.06226, 2018. [Online]. Available: http://arxiv.org/abs/1808.06226
  * [30] J. Ham, Y. J. Choe, K. Park, I. Choi, and H. Soh, “Kornli and korsts: New benchmark datasets for korean natural language understanding,” _arXiv preprint arXiv:2004.03289_ , 2020.
  * [31] A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts, “Learning word vectors for sentiment analysis,” in _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_. Portland, Oregon, USA: Association for Computational Linguistics, Jun. 2011, pp. 142–150. [Online]. Available: https://www.aclweb.org/anthology/P11-1015
  * [32] M. K. L. Seungyoung Lim, “KorQuAD: Korean QA Dataset for Machine Comprehension,” _Journal of Computing Science and Engineering_ , vol. , pp. 539–541, 2018. [Online]. Available: http://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE07613668