# A Markovian influence graph formed from utility line outage data to mitigate
large cascades

Kai Zhou, , Ian Dobson, , Zhaoyu Wang,
Alexander Roitershtein, Arka P. Ghosh  Preprint January 2020; to appear in
IEEE Transactions on Power Systems. Manuscript received August 13, 2019;
accepted January 26, 2020. ©2020 Kai Zhou and Ian Dobson et al.
Creative Commons Attribution License CC BY 4.0. KZ, ID, ZW are with Electrical
and Computer Engineering dept., Iowa State University, Ames IA USA; AR is with
Statistics dept., Texas A&M University, College Station TX USA; APG is with
Statistics dept., Iowa State University; emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>We gratefully thank BPA for making the outage data
public. The analysis and any conclusions are strictly the author’s and not
BPA’s. We gratefully acknowledge support in part from NSF grants 1609080 and
1735354. Digital Object Identifier 10.1109/TPWRS.2020.2970406

###### Abstract

We use observed transmission line outage data to make a Markovian influence
graph that describes the probabilities of transitions between generations of
cascading line outages. Each generation of a cascade consists of a single line
outage or multiple line outages. The new influence graph defines a Markov
chain and generalizes previous influence graphs by including multiple line
outages as Markov chain states. The generalized influence graph can reproduce
the distribution of cascade size in the utility data. In particular, it can
estimate the probabilities of small, medium and large cascades. The influence
graph has the key advantage of allowing the effect of mitigations to be
analyzed and readily tested, which is not available from the observed data. We
exploit the asymptotic properties of the Markov chain to find the lines most
involved in large cascades and show how upgrades to these critical lines can
reduce the probability of large cascades.

###### Index Terms:

cascading failures, power system reliability, mitigation, Markov, influence
graph.

##  I Introduction

Cascading outages in power transmission systems can cause widespread
blackouts. These large blackouts are infrequent, but are high-impact events
that occur often enough to pose a substantial risk to society [1, 2]. The
power industry has always analyzed specific blackouts and taken steps to
mitigate cascading. However, and especially for the largest blackouts of
highest risk, the challenges of evaluating and mitigating cascading risk in a
quantitative way remain.

There are two main approaches to evaluating cascading risk: simulation and
analyzing historical utility data. Cascading simulations can predict some
likely and plausible cascading sequences [3, 4]. However, only a subset of
cascading mechanisms can be approximated, and simulations are only starting to
be benchmarked and validated for estimating blackout risk [5, 6]. Historical
outage data can be used to estimate blackout risk [2] and detailed outage data
can be used to identify critical lines [7]. However it is clear that proposed
mitigation cannot be tested and evaluated with historical data. In this paper,
we process historical line outage data to form a Markovian influence graph
that statistically describes the interactions between the observed outages.
The Markovian influence graph can quantify the probability of different sizes
of cascades, identify critical lines and interactions, and assess the impact
of mitigation on the probability of different sizes of cascades.

###  I-A Literature review

We review the previous literature on influence graphs for power grid cascading
outages and related topics. There is increasing interest in graphs to
represent cascading outages, in which the graph describes the interaction
between outaged components and is not the power grid topology. These graphs of
interactions have differences in how they are formed and have different names,
such as the influence graph, the interaction graph, the correlation network,
and the cascading faults graph. The idea of a graph of interactions can be
traced back to [8] which has a stochastic process at each graph node that
interacts with different strengths along the graph edges joining to that node
to the other nodes. Rahnamay-Naeini [9] generalizes the model of interacting
and cascading nodes in [8] to include interactions within and between two
interdependent networks. This type of interacting particle system model has
some nice properties allowing analysis, but remains a somewhat abstract model
for power system cascading because it is not known how to estimate the model
parameters from data.

Influence graphs in their present form were introduced by Hines and Dobson
[10], and further developed by Qi, Hines, and Dobson [11, 12]. These influence
graphs describe the statistics of cascading data with networks whose nodes
represent outages of single transmission lines and whose directed edges
represent probabilistic interactions between successive line outages. The more
probable edges correspond to the interactions between line outages that appear
more frequently in the data. Cascades in the influence graph start with
initial line outages at the nodes and spread probabilistically along the
directed graph edges. Once the influence graph is formed from the simulated
cascading data, it can be used to identify critical components and test
mitigation of blackouts by upgrading the most critical components [11, 12,
13].

As well as outages of single lines, cascading data typically includes multiple
line outages that occur nearly simultaneously. When the states are single line
outages, these multiple simultaneous outages cause problems in obtaining well-
defined Markov chain transitions between states. For example, if the outage of
two lines causes an outage in the next generation, it is hard to tell which
line caused the subsequent outage or whether the two lines caused the
subsequent outage together. To address this, [12] assigns an equal share to
the two lines. The resulting influence graph is then approximated to enable
analysis. Qi [11] assumes that the subsequent outage is caused by the most
frequent line outage. Improving on this assumption, Qi [14] considers the
causal relationships among successive outages as hidden variables and uses an
expectation maximization algorithm to estimate the interactions underlying the
multiple outage data. In this paper, we solve this problem in a novel way by
defining an additional state for each multiple line outage. Thus our new
influence graph generalizes the interaction between single lines to multiple
line outages, so we do not need to make assumptions or approximations when
calculating the interactions between two single lines. This enables a Markov
chain to be cleanly and clearly defined.

Considering the different types of graphs of interactions more generally,
there are three methods of quantifying interactions between components which
are the edges in the graph of interactions. First, as explained in the
preceding paragraph, in [10, 12, 11], the edge corresponds to the conditional
probability of a single line outage given that the previous line has outaged.
Second, in [15, 16, 17], the edge weight is calculated based on the line flow
changes due to a single line outage applied to the base case using a DC load
flow (In contrast to [10, 12, 11] and this paper, this implies that the edge
weights do not change during the cascade.). In Merrill [16], the edge weight
is obtained from the line outage distribution factors. In Zhang [15] and Ma
[17], the directed edge weights are obtained from both the line flow changes
and the remaining margin in the line the power is transferred to. Then Zhang
[15] combines the directed edges to give undirected edges. On the other hand,
Ma [17] retains the directed edges and also represents hidden failures by
additional nodes. Third, in Yang [18], the edge corresponds to the correlation
between any two lines. In [19], Carreras constructs a synchronization matrix
from simulation data from the OPA model to identify the lines with higher
overloading probabilities. Other papers [13, 14, 20, 21, 22] form their graph
of interactions similarly to the above methods. In this paper, we base the
influence graph edges on conditional probabilities. However, the edges are
different than the edges in [10, 12, 11] as they directly correspond to
transition probabilities in a rigorously defined Markov chain.

Influence graphs describing the interactions between successive cascading
outages were developed using simulated data (Zhou [13] is the exception, but
[13] differs from this paper because it applies the methods of [12] to utility
data). But even for simulated cascade data, there remain challenges in
extracting good statistics for the influence graph from limited data. Hines,
Dobson and Qi [10, 12, 11] estimate the conditional probabilities of
transitions with empirical probabilities. In this paper, we mitigate the
limited historical cascading data by using a Bayesian method and carefully
combining the sparser data of the later stages of cascading in a sophisticated
way.

Various measures are proposed for the identification of critical components
based on the influence graph. [12, 11, 23, 17] form their specific measures
based on their own influence/interaction graph. Ma [17] uses a modified page-
rank algorithm to find critical lines. Nakarmi [20] forms the influence graph
using methods of both [12] and [18], and proposes a community-based measure to
identify critical components. [20] compares its measure with other centrality
measures based on network theory, and concludes that its method performs
better than other methods in most cases. In this paper, our influence graph is
a rigorous Markov chain, and the identification of critical lines is based on
the asymptotic quasi-stationary distribution. The quasi-stationary
distribution has a clear interpretation of specifying the probabilities that
each of the lines is involved in large cascades.

The graph of interactions also provides useful information about mitigation
actions in power system operation. Ju [21] extends the interaction graph to a
multi-layer graph, in which the three layers reflect the number of line
outages, load shed, and electrical distance of the cascade spread,
respectively. This multi-layer graph is suggested to mitigate cascades in
system operation by providing the critical lines at different states of
cascades. Chen [22] proposes a dynamic interaction graph to better support
online mitigation actions than a static interaction graph. During the
propagation of a specific cascade, this dynamic interaction graph removes the
interactions involving already outaged lines, and optimal power flow controls
the power flow on the critical lines indicated by the dynamic interaction
graph. The dynamic interaction graph model reduces the risk of large cascades
more than the static interaction graph.

As expected, the graph of interactions and any conclusions drawn depend on the
outage data from which the graph is formed. If the outage data is simulated,
the selection of initial system states matters. For example, Nakarami [20]
shows that different system states lead to different influence graphs. In this
paper, we form our influence graph from fourteen years of public outage data
of a specific area, so that our influence graph reflects the initial faults
and states encountered over that period of time in that power system area. The
textbook [24] includes material on both influence and interaction graphs.

Another related line of research is fault chains. A fault chain as described
in [25] is one cascading sequence of line outages. Each initial line fault
gives a fault chain of lines most stressed at each step until outage or
instability. Usually only the most stressed or most likely next line outage is
selected to form fault chains. By taking each line in the system as the
initial outage of each fault chain, Wei [23] obtains a set of fault chains
using a branch loading index to select the most stressed next line to outage.
Each fault chain is expressed as a subgraph whose nodes are transmission
lines, and directed edges are branch loading assessment indexes, and the union
of the subgraphs forms a cascading faults graph. The edge weights depend on
the sum of the branch loading indices, each scaled by the length of the fault
they are in. Then critical lines are identified according to the in- or out-
degree of the cascading faults graph. Luo [26] also forms a cascading faults
graph with weights depending on load loss in the chain, and then uses
hypertext-induced topic search to select critical lines. The edge weights of
[23, 26] differ from those in influence graphs because they are not based on
conditional probabilities. Li and Wu [27] combine simulated fault chains into
a network and use reinforcement learning to explore, evaluate, and find chains
most critical to load shed. In further work, Li and Wu [28] combine simulated
fault chains into a state-failure network from which expected load shed can be
computed for each state and failure by propagating load shed backwards
accounting for the transition probabilities of the edges. The transition
probabilities are estimated similarly to an influence graph by the relative
frequency of that transition at that stage of the data. However, in contrast
to the practice in influence graphs, the state transition data for the later
stages is not combined together to get better estimates. Moreover, fault
chains differ from this paper in only considering single line outages one
after another.

There are also approaches to modeling cascading with continuous-time Markov
processes. Wang [29] drives line loadings with generator and load power
fluctuations to determine overloads and outages that change the Markov state
and hence simulate the cascading. Rahnamay-Naeini [30] constructs, using
simulated cascading data and fitted functional forms, a Markov process with
states highly aggregated into 3 quantities, namely the number of failed lines,
the maximum of the capacities of all of the preceding failed lines, and a
cascade stopping index. The aggregated Markov process can model the time
evolution of the cascade and the distribution of cascade size. In further
work, Rahnamay-Naeini reduces the aggregated model to a discrete time Markov
chain and generalizes it to model cyber and power interdependent network
cascading interactions in [31] and to model operator actions interacting with
cascading in [32].

For another, independent perspective on the literature, Nakarmi’s review paper
[33] surveys various methods of constructing interaction graphs and the
reliability analysis based on interaction graphs.

###  I-B Contributions of paper

The new influence graph generalizes and improves previous work in several
ways. In particular, this paper

  * •

uses real data observed and routinely collected by utilities rather than
simulated data.

  * •

obtains a clearly defined influence graph that solves the problem of multiple
simultaneous outages by using additional states with multiple outages. This
generalized influence graph rigorously defines a Markov chain.

  * •

mitigates the problems of limited cascading data with several new methods; in
particular, it combines Bayesian methods of estimation with elaborate methods
of distinguishing and combining different events. This better estimates the
transition matrices of the influence graph while matching the increasing
cascade propagation and retaining possibilities of analysis.

  * •

computes the probabilities of small, medium and large cascades, and these
match the historical data statistics.

  * •

makes innovative use of the bootstrap to estimate the variance of the
probabilities of small, medium and large cascades. This allows checking that
the estimated probabilities of small, medium and large cascades are accurate
enough to be useful.

  * •

calculates critical lines most involved in large cascades directly from the
Markov chain as the quasi-stationary distribution of the Markov chain.

All of these advances clearly distinguish this paper from the previous work
reviewed above.

##  II Forming the Markovian influence graph from historical outage data

We use detailed historical line outage data consisting of records of
individual automatic transmission line outages that specify the lines outaged
and the outage times to the nearest minute. We emphasize that this data is
routinely recorded by utilities worldwide, for example in the North American
Transmission Availability Data System.

The first step in building an influence graph is to take many cascading
sequences of transmission line outages and divide each cascade111The grouping
of line outages into cascades uses the simple method of [34]: The grouping is
done by looking at the gaps in start time between successive line outages. If
successive outages have a gap of one hour or more, then the outage after the
gap starts a new cascade. More elaborate methods of grouping real line outages
into cascades could be developed and applied. into generations of outages as
detailed in [34]. Each cascade starts with initial line outages in generation
0, and continues with subsequent generations of line outages 1,2,3,… until the
cascade stops. Each generation of line outages is a set of line outages that
occur together on a fast time scale of less than one minute. Often there is
only one line outage in a generation, but protection actions can act quickly
to cause several line outages in the same generation. (Sometimes in a
cascading sequence an outaged line recloses and outages in a subsequent
generation. In contrast to [34, 13], here we neglect the repeats of these
outages.)

Figure 1: Simple example forming influence graph from artificial data (real
utility data is shown in Fig. 2).

Figure 2: The gray network is the system network and the red network is the
influence graph showing the main influences between lines. The red edge
thickness indicates the strength of the influence.

The influence graph represents cascading as a Markov chain $X_{0},X_{1},...$,
in which $X_{k}$ is the set of line outages in generation $k$ of the cascade.
We first illustrate the formation of the influence graph from artificial
cascading data with the simple example of four observed cascades involving
three lines shown in Fig. 1. The first cascade has line 1 outaged in
generation 0, line 3 outaged in generation 1, line 2 outaged in generation 2,
and then the cascade stops with no lines (indicated by the empty set {})
outaged in generation 3. All cascades eventually stop by transitioning to and
remaining in the state {} for all future generations. The five states observed
in the data are {}, {line 1}, {line 2}, {line 3}, and {line 1, line 3}, where
this last state is lines 1 and 3 outaging together in the same generation, as
in generation 1 of cascade 2. Introducing the state {line 1, line 3} with two
line outages avoids the problems in previous work in accounting for
transitions to and from the simultaneous outages of line 1 and line 3.

We can estimate the probabilities of transitioning from state $i$ to state $j$
in the next generation by counting the number of those transitions in all the
cascades and dividing by the number of occurrences of state $i$. For example,
the probability of transitioning from state {line 1} to state {line 3} is
$1/3$ and the probability of transitioning from state {line 2} to state {line
1, line 3} is $1/2$. The probability of transitioning from state {line 1} to
{}; that is, stopping after the single outage of line 1, is $2/3$. The
probabilities of the edges out of each state sum to 1. By working out all the
transition probabilities, we can make the network graph of the Markov chain as
shown in Fig. 1. The transitions between states with higher probability are
shown with thicker lines. In this generalized influence graph, the nodes are
sets of line outages and the edges indicate transitions or interactions
between sets of line outages in successive generations of cascading. The
influence graph is different than the physical grid network and cascades are
generated in the influence graph by moving along successive edges, selecting
them according to their transition probabilities.

In the general case, there are many states $s_{0}$, $s_{1}$, … , and we
describe the transitions between them. Let $\bm{P}_{k}$ be the Markov chain
transition matrix for generation $k$. The $\bm{P}_{k}$ matrix entry
$P_{k}[i,j]$ is the conditional probability that the set of outaged lines is
$s_{j}$ in generation $k+1$, given that the set of outaged lines is $s_{i}$ in
generation $k$; that is,

$\displaystyle P_{k}[i,j]={\rm P}[X_{k+1}=s_{j}~{}|~{}X_{k}=s_{i}].$ (1)

The key task of forming the Markov chain is to estimate the transition
probabilities in the matrix $\bm{P}_{k}$ from the cascading data. If one
supposed that $\bm{P}_{k}$ does not depend on $k$, a straightforward way to do
this would first construct a counting matrix $\bm{N}$ whose entry $N[i,j]$ is
the number of transitions from $s_{i}$ to $s_{j}$ among all generations in all
the cascades. Then $\bm{P}_{k}$ would be estimated as

$\displaystyle P_{k}[i,j]=\frac{N[i,j]}{\sum_{j}N[i,j]}.$ (2)

However, we find that $\bm{P}_{k}$ must depend on $k$ in order to reproduce
the increasing propagation of outages observed in the data [34]. On the other
hand, there is not enough data to accurately estimate $\bm{P}_{k}$
individually for each $k>0$. Our solution to this problem involves both
grouping together data for higher generations and having $\bm{P}_{k}$ varying
with $k$, as well as using empirical Bayesian methods to improve the required
estimates of cascade stopping probabilities. The detailed explanation of this
solution is postponed to section VI, and until section VI we assume that
$\bm{P}_{k}$ has already been estimated for each generation $k$ from the
utility data. Forming the Markov chain transition matrix from the data in this
way makes the Markovian assumption that the statistics of the lines outaged in
a generation only depend on the lines outaged in the previous generation. This
is a pragmatic assumption that yields a tractable data-driven probabilistic
model of cascading.

One way to visualize the influence graph interactions between line outages in
$\bm{P}_{k}$ is to restrict attention to the interactions between single line
states, and show these as the red network in Fig. 2. The gray network is the
actual grid topology, and the gray transmission lines are joined by a red line
of the thickness proportional to the probability of being in successive
generations, if that probability is sufficiently large. The interactions in
Fig. 2 reflect a very wide range of mechanisms. The longer-range mechanisms
include redistributions of power due to line and generator outages, remedial
action schemes, and bad weather across the grid.

Let the row vector $\bm{\pi}_{k}$ be the probability distribution of states in
generation $k$. The $\bm{\pi}_{k}$ entry $\pi_{k}[i]$ is the probability that
the set of outaged lines is $s_{i}$ in generation $k$; that is,

$\displaystyle\pi_{k}[i]={\rm P}[X_{k}=s_{i}].$ (3)

Then the propagation of sets of line outages from generation $k$ to generation
$k+1$ is given by

$\displaystyle\bm{\pi}_{k+1}=\bm{\pi}_{k}\bm{P}_{k}$ (4)

and, using (4), the distribution of states in generation $k$ depends on the
initial distribution of states $\bm{\pi}_{0}$ according to

$\displaystyle\bm{\pi}_{k}=\bm{\pi}_{0}\bm{P}_{0}\bm{P}_{1}...\bm{P}_{k-2}\bm{P}_{k-1}.$
(5)

##  III Illustrative historical outage data

While our method applies generally to the detailed outage data routinely
collected by utilities, we illustrate our method with a specific publicly
available data set, which is the automatic transmission line outages recorded
by a large North American utility over 14 years starting in 1999 [35]. We
group the 9,741 line outages into 6,687 cascades [34]. Most of the cascades
(87%) have one generation because initial outages often do not propagate
further. There are 614 lines and the observed cascades have 1094 subsets of
these lines that form the 1094 states $s_{0}$, $s_{1}$, … , $s_{1093}$. Among
these 1094 states, 50% have multi-line outages. And among these multi-line
outage states, about 20% are comprised of lines sharing no common buses. While
in theory there are $2^{614}$ subsets of 614 lines, giving an impractically
large number of states, we find in practice with our data that the number of
states is less than twice the number of lines. Note that our statistical
modeling approximates the power grid as unchanging over the time span of the
data [36]. In practice a utility would have the records of changes to
partially mitigate the effects of this approximation.

##  IV Computing the distribution of cascade sizes and its confidence interval

We compute the distribution of cascade sizes from the Markov chain and check
that it reproduces the empirical distribution of cascade sizes, and estimate
its confidence interval with a bootstrap.

We can measure the cascade size by its number of generations. Define the
survival function of the number of generations in a cascade as

$\displaystyle S(k)={\rm P}[\mbox{number of cascade generations $>k$}]$ (6)

$S(k)=1-\pi_{k}[0]$, where $\pi_{k}[0]$ is the probability that a cascade is
in state $s_{0}=\\{\\}$ in generation $k$ and also the probability that the
cascade stops at or before generation $k$. Hence

$\displaystyle S(k)$ $\displaystyle=1-\pi_{k}[0]=\bm{\pi}_{k}({\bf
1}-\bm{e}_{0})$
$\displaystyle=\bm{\pi}_{0}\bm{P}_{0}\bm{P}_{1}...\bm{P}_{k-2}\bm{P}_{k-1}({\bf
1}-\bm{e}_{0}),$ (7)

where ${\bf 1}$ is the column vector $(1,1,1,...,1)^{\prime}$, and
$\bm{e}_{0}$ is the column vector $(1,0,0,0,...,0)^{\prime}$. The initial
state distribution $\bm{\pi}_{0}$ can be estimated directly from the cascading
data.

Then we can confirm that the influence graph reproduces the statistics of
cascade size in the cascading data by comparing the survival function $S(k)$
computed from (7) with the empirical survival function computed directly from
the cascading data as shown in Fig. 3. The Markov chain reproduces the
statistics of cascade size closely, with a Pearson $\chi^{2}$ goodness-of-fit
test $p$-value of $0.99$.

Figure 3: Survival functions of the number of generations from real data and
from the Markov chain.

We use bootstrap resampling [37] to estimate the variance of our estimates of
probabilities of cascade sizes. A bootstrap sample resamples the observed
cascades with replacement, reconstructs the Markov chain, and recomputes the
probabilities of cascade sizes. Note that each bootstrap resampling amounts to
a different selection of the cascades observed in the data. The variance of
the probabilities of cascade sizes is then obtained as the empirical variance
of the bootstrap samples. We use 500 bootstrap samples to ensure a
sufficiently accurate estimate of the variance of the probabilities.

The risk of a given size of blackout is estimated as risk = (estimated
probability $\hat{p}$ of that size of blackout) $\times$ (cost of that size of
blackout). Knowing the multiplicative uncertainty in $\hat{p}$ is useful. For
example, if we know $\hat{p}$ to within a factor of 2, then this contributes a
factor of 2 to the uncertainty of the risk. Therefore, it is appropriate to
use a multiplicative form of confidence interval for $\hat{p}$ specified by a
parameter $\kappa$. A 95% multiplicative confidence interval for an estimated
probability $\hat{p}$ means that the probability $p$ satisfies ${\rm
P}[\hat{p}/\kappa\leq p\leq\hat{p}\,\kappa]=0.95$. The confidence interval for
the estimated survival function is shown in Fig. 4. Since larger cascades are
rarer than small cascades, the variation increases as the number of
generations increases.

Figure 4: Survival function of cascade sizes. Red crosses are from Markov
chain, and blue lines indicate the 95% confidence interval estimated by
bootstrap.

To apply and communicate the probability distribution of cascade size, it is
convenient to combine sizes together to get the probabilities of small,
medium, and large cascades, where a small cascade has 1 or 2 generations, a
medium cascade has 3 to 9 generations, and a large cascade has 10 or more
generations. (The respective probabilities are calculated as $1-S(2)$,
$S(2)-S(9)$, and $S(9)$). The 95% confidence intervals of the estimated
probabilities of small, medium, and large cascades are shown in Table I. The
probability of large cascades is estimated within a factor of 1.5, which is
adequate for the purposes of estimating large cascade risk, since the cost of
large cascades is so poorly known: estimates of the direct costs of cascading
blackouts vary by more than a factor of 2.

TABLE I: 95% Confidence intervals using bootstrap cascade size | probability | $\kappa$
---|---|---
small (1 or 2 generations) | 0.9606 | 1.005
medium (3 to 9 generations) | 0.0372 | 1.132
large (10 or more generations) | 0.0022 | 1.440

We now discuss tracking cascades by their number of generations. The number of
generations is the same concept as the number of tiers in commercial cascading
software [38]. Basic to cascading analysis is the grouping of line outages
into successive generations within each cascade. This grouping is usually done
by outage timing as in this paper, or by simulation loops naturally producing
generations of outages. This paper is structured in terms of these
generations, so that propagation is determined by the probability of a next
generation (i.e. the cascade not stopping at the current generation), and
cascade size is measured by number of cascade generations. In contrast, some
previous papers [34, 12, 13, 7] are structured in terms of the line outages in
the generations, so that, according to the branching process model [34], each
line outage in each generation propagates independently to form line outages
in the next generation. Then the propagation is determined by the number of
line outages per line outage in the previous generation, and it is natural to
use the total number of lines outaged as a measure of cascade size. While it
is not yet clear which approach is better, there may be some advantages to
tracking cascades by generations rather than line outages. Generations are
simpler and more general than line outages, and can more easily encompass
other outages significant in cascading such as transformer outages. Also, it
may be that the statistics of the number of generations is more simply
described, as in the Zipf distribution observed in utility data in [39].

##  V Critical lines and cascade mitigation

###  V-A The transmission lines involved in large cascades

The lines eventually most involved in large cascades can be calculated from
the asymptotic properties of the Markov chain. While all cascades eventually
stop, we can consider at each generation those propagating cascades that are
not stopped at that generation. The probability distribution of states
involved in these propagating cascades converges to a probability distribution
$\bm{d}_{\infty}$, which is called the quasi-stationary distribution.
$\bm{d}_{\infty}$ can be computed directly from the transition matrices (as
explained in Appendix A, $\bm{d}_{\infty}$ is the left eigenvector
corresponding to the dominant eigenvalue of the transition submatrix
$\bar{\bm{Q}}_{1+}$). That is, except for a transient that dies out after some
initial generations, the participation of states in the cascading that
continues past these initial generations is well approximated by
$\bm{d}_{\infty}$. Thus the high probability states corresponding to the
highest probability entries in $\bm{d}_{\infty}$ are the critical states most
involved in the latter portion of large cascades. Since $\bm{d}_{\infty}$ does
not depend on the initial outages, the Markov chain is supplying information
about the eventual cascading for all initial outages.

We now find the critical lines corresponding to these critical states by
projecting the states onto the lines in those states. Let $\bm{\ell}_{k}$ be
the row vector whose entry $\ell_{k}[j]$ is the probability that line $j$
outages in generation $k$. Then

$\displaystyle\ell_{k}[j]=\sum_{i:j\in
s_{i}}\pi_{k}[i]\quad\mbox{or}\quad\bm{\ell}_{k}=\bm{\pi}_{k}\bm{R},$ (8)

where the matrix $\bm{R}$ projects states to lines according to

$\displaystyle R[i,j]=\left\\{\begin{array}[]{lr}1;&\mbox{line}~{}j\in
s_{i}\\\ 0;&\mbox{line}~{}j\notin s_{i}\end{array}\right.$ (11)

Then the probability distribution of lines eventually involved in the
propagating cascades that are not stopped is
$\bm{c}_{\infty}=\bm{d}_{\infty}\bm{R}$ and the critical lines most involved
in the latter portion of large cascades correspond to the highest probability
entries in $\bm{c}_{\infty}$. Fig. 5 shows the probabilities in
$\bm{c}_{\infty}$ in order of decreasing probability. We identify the top ten
lines as critical and as candidates for upgrading to decrease the probability
of large cascades.

Figure 5: Quasi-stationary distribution of transmission lines eventually
involved in propagating cascades. Red dots are ten critical lines.

###  V-B Modeling and testing mitigation in the Markov chain

A transmission line is less likely to fail due to other line outages after the
line is upgraded, its protection is improved, or its operating limit is
reduced. These mitigations have the effect of decreasing the probability of
transition to states containing the upgraded line, and are an adjustment of
the columns of the transition matrix corresponding to these states. The
mitigation is represented in the Markov chain by reducing the probability of
transition to the state $s$ containing the upgraded line by $({r}/{|s|})\%$,
where $|s|$ is the number of lines in the state. The reduction is $r\%$ if the
state contains only the upgraded line, and the reduction is less if the state
contains multiple lines.

We demonstrate using the Markov chain to quantify the impact of mitigation by
upgrading the ten lines critical for large cascades identified in section V-A
with $r=80\%$. The effect of this mitigation on cascade probabilities is shown
in Fig. 6. It shows that upgrading the critical lines reduces the probability
of large cascades by 45%, while the probability of medium cascades is slightly
decreased and the probability of small cascades is slightly increased.

Figure 6: Cascade size distribution before (red) and after (light green)
mitigating lines critical in propagating large cascades.

To show the effectiveness of the method of identifying critical lines, we
compare the mitigation effect of upgrading critical lines and upgrading ten
random lines. Randomly upgrading ten lines only decreases the probability of
large cascades by 11% on average.

So far we have only considered upgrading the lines critical for propagating
large cascades. Now, in order to discuss this mitigation of large cascades in
a larger context, we briefly consider and contrast a different mitigation
tactic of upgrading lines that are critical for initial outages. Since initial
outages are caused by external causes such as storm, lightning, or
misoperation, they often have different mechanisms and different mitigations
than for propagating outages. A straightforward method to identify lines
critical for initial outages selects the ten lines in the data with the
highest frequencies of initial outage [13]. Upgrading these ten lines will
reduce their initial outage frequencies and hence reduce the overall cascade
frequency. In the Markov chain, this upgrading is represented by reducing in
the first generation the frequency of states $s$ that contain the critical
lines for initial outages by $r/|s|$%, where $r=80\%$. The main effect is that
by reducing the initial outage frequencies of the critical lines by 80%, we
reduce the frequency of all cascades by 19%. In addition, this mitigation will
change the probabilities of states $\bm{\pi}_{0}$ after renormalizing the
frequencies of states. It turns out for our case that there is no overlap
between critical lines for initial outages and for propagation.

Changing the initial state distribution $\bm{\pi}_{0}$ has no effect on the
distribution of cascade sizes in the long-term. However, it directly reduces
the frequency of all cascades. In contrast, mitigating the lines critical for
propagating large cascades reduces the probability of large cascades relative
to all cascades but has no effect on the frequency of all cascades. (Note that
Fig. 6 shows the distribution of cascade sizes assuming that there is a
cascade, but gives no information about the frequency of all cascades.)

In practice, a given mitigation measure can affect both the initial outages
and the propagation of outages into large cascades. The combined mitigation
effects can also be represented in the influence graph by changing both the
initial state distribution and the transition matrix, but here it is
convenient to discuss them separately.

This paper aims to select the lines critical for large cascades and quantify
the impact on cascade probability of generic upgrades to these lines. Once the
critical lines are selected, an engineering process of much wider scope is
required to determine the possible approaches to upgrade each of the lines,
quantify the benefits other than reducing large cascades and balance the costs
and feasibilities of the upgrading approaches against the total benefits of
upgrading. One part of this process is that for each line, the percentage
reduction in outage probability for the best approach to line upgrade is
estimated and the Markov chain is used to quantify the corresponding reduction
in large, medium, and small cascade probabilities. However, cascade mitigation
is only one of the many factors to be considered in justifying upgrade.
Evaluating and costing specific upgrading approaches for specific lines
requires utility expertise, including details of the line construction and
right of way, maintenance history, and operation.

##  VI Estimating the transition matrix

The Markov chain has an absorbing first state $s_{0}=\\{\\}$, indicating no
lines outaged as the cascade stops and after the cascade stops. Therefore the
transition matrix has the structure

$\displaystyle\bm{P}_{k}=\left[{\begin{array}[]{*{20}{c}}1&\vline&0&\cdots&0\\\
\hline\cr{}\hfil&\vline&{}\hfil&{}\hfil&{}\hfil\\\
\bm{u}_{k}&\vline&{}\hfil&\bm{Q}_{k}&{}\hfil\\\
{}\hfil&\vline&{}\hfil&{}\hfil&{}\hfil\\\ \end{array}}\right]$ (16)

where $\bm{u}_{k}$ is a column vector of stopping probabilities; that is,
$u_{k}[i]=P_{k}[i,0]$. $\bm{Q}_{k}$ is a submatrix of transition probabilities
between transient states which contains the non-stopping probabilities. The
first row of $\bm{P}_{k}$ is always $\bm{e}^{\prime}_{0}$, so the transition
probabilities to be estimated are $\bm{u}_{k}$ and $\bm{Q}_{k}$ for each
generation $k$. The rows and columns of $\bm{P}_{k}$ are indexed from 0 to
$|\mathcal{S}|-1$ and the rows and columns of $\bm{Q}_{k}$ are indexed from 1
to $|\mathcal{S}|-1$, where $|\mathcal{S}|$ is the number of states.

As summarized in section II after (1), we need to both group together multiple
generations to get sufficient data and account for variation with generation
$k$. The statistics of the transition from generation 0 to generation 1 are
different than the statistics of the transitions between the subsequent
generations. For example, stopping probabilities for generation 0 are usually
larger than stopping probabilities for subsequent generations [13]. Also, the
data for the subsequent generations is sparser. Therefore, we construct from
counts of the number of transitions from generation 0 to generation 1 a
probability transition matrix $\bar{\bm{P}}_{0}$, and construct from the total
counts of the number of transitions from all the subsequent generations a
probability transition matrix $\bar{\bm{P}}_{1+}$. Specifically, we first use
the right-hand side of (2) to construct two corresponding empirical transition
matrices, and then we update stopping probabilities by the empirical Bayes
method and adjust non-stopping probabilities to obtain $\bar{\bm{P}}_{0}$ and
$\bar{\bm{P}}_{1+}$. Finally, we adjust $\bar{\bm{P}}_{0}$ and
$\bar{\bm{P}}_{1+}$ to match the observed propagation rates to obtain
$\bm{P}_{k}$ for each generation $k$.

###  VI-A Bayesian update of stopping probabilities

The empirical stopping probabilities are improved by an empirical Bayes method
[40, 41] to help mitigate the sparse data for some of these probabilities.
Since the method is applied to both $\bar{\bm{P}}_{0}$ and
$\bar{\bm{P}}_{1+}$, we simplify notation by writing $\bar{\bm{P}}$ for either
$\bar{\bm{P}}_{0}$ or $\bar{\bm{P}}_{1+}$.

The matrix of empirical probabilities obtained from the transition counts
$N[i,j]$ is

$\displaystyle{\bar{P}}^{\rm counts}[i,j]=\frac{N[i,j]}{\sum_{j}N[i,j]}$ (17)

We construct $\bar{\bm{P}}$ from $\bar{\bm{P}}^{\rm counts}$ in two steps.
First, Bayesian updating is used to better estimate stopping probabilities and
form a matrix $\bar{\bm{P}}^{\rm bayes}$. Second, the non-stopping
probabilities in $\bar{\bm{P}}^{\rm bayes}$ are adjusted to form the matrix
$\bar{\bm{P}}$ to account for the fact that some independent outages are
grouped into cascading outages when we group outage data into cascades.

We need to estimate the probability of the cascade stopping at the next
generation for each state encountered in the cascade. For some of the states,
the stopping counts are low, and cannot give good estimates of the stopping
probability. However, by pooling the data for all the states we can get a good
estimate of the mean probability of stopping over all the states. We use this
mean probability to adjust the sparse counts in a conservative way. In
particular, we form a prior that maximizes its entropy subject to the mean of
the prior being the mean of the pooled data. This maximum entropy prior can be
interpreted as the prior distribution that makes the least possible further
assumptions about the data [42][43].

#### Finding a maximum entropy prior

Assuming the stopping counts are independent with a common probability, the
stopping counts follow a binomial distribution. Its conjugate prior
distribution is the beta distribution, whose parameters are estimated using
the maximum entropy method.

Let stopping counts $C_{i}$ be the observed number of transitions from state
$s_{i}$ to $s_{0}$ ($i=1,...,|\mathcal{S}|-1$). Then $C_{i}=N[i,0]$. Let
$n_{i}=\sum_{j=0}^{|\mathcal{S}|-1}N[i,j]$ be the row sum of the counting
matrix $\bm{N}$. The stopping counts $C_{i}$ follow a binomial distribution
with parameter $U_{i}$, with probability mass function

$\displaystyle f_{C_{i}|U_{i}}(c_{i}|u_{i})$
$\displaystyle=\dfrac{n_{i}!}{c_{i}!(n_{i}-c_{i})!}u_{i}^{c_{i}}(1-u_{i})^{n_{i}-c_{i}}$
(18)

The conjugate prior distribution for the binomial distribution is the beta
distribution. Accordingly, we use the beta distribution with hyperparameters
$\beta_{1},\beta_{2}$ for the stopping probability $U_{i}$:

$\displaystyle
f_{U_{i}}(u_{i})=B(\beta_{1},\beta_{2})u_{i}^{\beta_{1}-1}(1-u_{i})^{\beta_{2}-1}$
(19)

where
$B(\beta_{1},\beta_{2})=\frac{\Gamma(\beta_{1}+\beta_{2})}{\Gamma(\beta_{1})\Gamma(\beta_{2})}$.
Alternative parameters for the beta distribution are its precision
$m=\beta_{1}+\beta_{2}$ and its mean
$\mu=\frac{\beta_{1}}{\beta_{1}+\beta_{2}}$. The entropy of the beta
distribution is

$\displaystyle{\rm Ent}(m,\mu)=\ln B(m\mu,m(1-\mu))-(m\mu-1)\psi(m\mu)$
$\displaystyle\qquad-(m(1-\mu)-1)\psi(m(1-\mu))+(m-2)\psi(m)$ (20)

where $\psi(x)$ is the digamma function.

We want to estimate hyperparameters $\beta_{1}$, $\beta_{2}$ to make the beta
distribution have maximum entropy subject to the mean being the average
stopping probability of the pooled data
$\hat{u}=(\sum_{i=1}^{|\mathcal{S}|-1}c_{i})/(\sum_{i=1}^{|\mathcal{S}|-1}n_{i})$.
Then we can obtain hyperparameters $\beta_{1}$, $\beta_{2}$ by finding the
$m>0$ that maximizes ${\rm Ent}(m,\hat{u})$ and evaluating
$\beta_{1}=m\hat{u}$ and $\beta_{2}=m(1-\hat{u})$. The hyperparameters used
for $\bar{\bm{P}}_{0}^{\rm bayes}$ are $(\beta_{1},\beta_{2})=(2.18,0.32)$,
and the hyperparameters for $\bar{\bm{P}}_{1+}^{\rm bayes}$ are
$(\beta_{1},\beta_{2})=(1.10,0.93)$.

#### Updating the observed data using the prior

The posterior distribution of the stopping probability $U_{i}$ is a beta
distribution with parameters $c_{i}+\beta_{1},n_{i}-c_{i}+\beta_{2}$. We use
the mean of the posterior distribution as a point estimate of the stopping
probability:

$\displaystyle\bar{P}^{\rm bayes}[i,0]={\rm
E}(U_{i}|C_{i}=c_{i})=\dfrac{c_{i}+\beta_{1}}{n_{i}+\beta_{1}+\beta_{2}}$ (21)

Fig. 7 shows a comparison between the empirical stopping probabilities and the
updated stopping probabilities. Black dots are the empirical probabilities
sorted in ascending order (if two probabilities are equal, they are sorted
according to the total counts observed). Red dots are the updated stopping
probabilities. As expected, the empirical probabilities with the fewest counts
move towards the mean the most when updated. As the counts increase, the
effect of the prior decreases and the updated probabilities tend to the
empirical probabilities.

Equation (21) forms the first column of $\bar{{\bm{P}}}^{\rm bayes}$. Then the
nonstopping probabilities in the rest of the columns of the
${\bar{\bm{P}}}^{\rm counts}$ matrix are scaled so that they sum to one minus
the stopping probabilities of (21) to complete the matrix $\bar{{\bm{P}}}^{\rm
bayes}$:

$\displaystyle\bar{P}^{\rm bayes}[i,j]=\frac{1-\bar{P}^{\rm
bayes}[i,0]}{\sum_{r=1}^{|\mathcal{S}|-1}\bar{P}^{\rm
counts}[i,r]}\bar{P}^{\rm counts}[i,j],\ j>0$ (22)

This Bayesian updating is applied to form $\bar{\bm{P}}_{0}^{\rm bayes}$ for
the first transition and $\bar{\bm{P}}_{1+}^{\rm bayes}$ for the subsequent
transitions.

Figure 7: Stopping probabilities before and after Bayesian updating

###  VI-B Adjust nonstopping probabilities for independent outages

The method explained in section II that groups outages into cascades has an
estimated 6% chance that it groups independent outages into cascading outages
[36]. These 6% of outages occur independently while the cascading of other
outages proceeds and do not arise from interactions with other outages. The
empirical data for the nonstopping probabilities includes these 6% of outages,
and we want to correct this. Therefore, the non-stopping probabilities are
modified by shrinking the probabilities in transition matrix by 6%, and
sharing this equally among all the states. That is,

$\displaystyle\bar{P}[i,j]=0.94\bar{P}^{\rm
bayes}[i,j]+\frac{0.06}{|\mathcal{S}|-1}(1-\bar{P}^{\rm bayes}[i,0])$ (23)

where $\bar{P}^{\rm bayes}$ indicates the transition matrices after the
Bayesian update of section VI-A. Notice that $\bar{P}$ is a probability matrix
since $\sum_{j}\bar{P}(i,j)=1$ for each $i$. A benefit is that this adjustment
makes the submatrix $\bm{Q}_{k}$ have non-zero off-diagonal entries, making
$\bar{P}$ irreducible.

###  VI-C Adjustments to match propagation

The average propagation $\rho_{k}$ for generation $k$ [34] is estimated from
the data using

$\displaystyle\hat{\rho}_{k}$ $\displaystyle=\frac{\text{Number of cascades
with $>k+1$ generations}}{\text{Number of cascades with $>k$ generations}}$
$\displaystyle=\frac{S(k+1)}{S(k)}=\frac{\bm{\pi}_{k+1}({\bf
1}-\bm{e}_{0})}{\bm{\pi}_{k}({\bf 1}-\bm{e}_{0})}$ (24)

An important feature of the cascading data is that average propagation
$\rho_{k}$ increases with generation $k$ as shown in Table II. To do this, we
need to form transition matrices for each of these generations that reproduce
this propagation.

TABLE II: Propagations of generations $k=0$ to 17  $k$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---|---
$\hat{\rho}_{k}$ | 0.13 | 0.31 | 0.44 | 0.61 | 0.73 | 0.70 | 0.78 | 0.75 | 0.71
$k$ | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17
$\hat{\rho}_{k}$ | 0.73 | 0.91 | 1.00 | 1.00 | 0.80 | 0.75 | 0.83 | 0.60 | 0.67

We define a matrix $\bm{A}_{k}$ to adjust $\bar{\bm{P}}_{0}$ and
$\bar{\bm{P}}_{1+}$ so that the propagation in $\bm{P}_{k}$ matches the
empirical propagation for each generation up to generation 8. For generation 9
and above, the empirical propagation for each generation is too noisy to use
individually and we combine those generations to obtain a constant transition
matrix. That is, $\bm{P}_{0}=\bar{\bm{P}}_{0}\bm{A}_{0}$,
$\bm{P}_{1}=\bar{\bm{P}}_{1+}\bm{A}_{1}$, … ,
$\bm{P}_{8}=\bar{\bm{P}}_{1+}\bm{A}_{8}$,
$\bm{P}_{9+}=\bar{\bm{P}}_{1+}\bm{A}_{9+}$. Then the transition matrices for
all the generations are
$\bm{P}_{0},\bm{P}_{1},\bm{P}_{2},\bm{P}_{3},\bm{P}_{4},\bm{P}_{5},\bm{P}_{6},\bm{P}_{7},\bm{P}_{8},\bm{P}_{9+},\bm{P}_{9+},\bm{P}_{9+},...$.

The matrix $\bm{A}_{k}$ has the effect of transferring a fraction of
probability from the transient to stopping transitions and has the following
form:

$\displaystyle\bm{A}_{k}=\begin{pmatrix}1&0&...&0\\\ a_{k}&1-a_{k}&...&0\\\
\vdots&&\ddots&\\\ a_{k}&0&...&1-a_{k}\end{pmatrix}$ (25)

$a_{k}$ is determined from the estimated propagation rate $\hat{\rho}_{k}$ as
follows. Using (VI-C), we have

$\displaystyle\hat{\rho}_{k}$
$\displaystyle=\frac{\bm{\pi}_{k}\bar{\bm{P}}\bm{A}_{k}({\bf
1}-\bm{e}_{0})}{\bm{\pi}_{k}({\bf
1}-\bm{e}_{0})}=(1-a_{k})\frac{1-\bm{\pi}_{k}\bar{\bm{P}}\bm{e}_{0}}{1-\bm{\pi}_{k}\bm{e}_{0}}$
(26)

and we solve (26) to obtain $a_{k}$ for each generation $k$.

##  VII Discussion and Conclusion

We process observed transmission line outage utility data to form a
generalized influence graph and the associated Markov chain that statistically
describe cascading outages in the data. Successive line outages, or, more
precisely, successive sets of near simultaneous line outages in the cascading
data correspond to transitions between nodes of the influence graph and
transitions in the Markov chain. The more frequently occurring successive line
outages in the cascading data give a stronger influence between nodes and
higher transition probabilities. The generalized influence graph introduces
additional states corresponding to multiple line outages that occur nearly
simultaneously. This innovation adds a manageable number of additional states
and solves some problems with previous influence graphs, making the formation
of the Markov chain clearer and more rigorous.

One of the inherent challenges of cascading is the sparse data for large
cascades. We have used several methods to partially alleviate this when
estimating the Markov chain transition matrices, including combining data for
several generations, conservatively improving estimates of stopping
probabilities with an empirical Bayes method, accounting for independent
outages during the cascade, and matching the observed propagation for each
generation. The combined effect of these methods is to improve estimates of
the Markov chain transition matrices. Although some individual elements of
these transition matrices are nevertheless still poorly estimated, what
matters is the variability of the results from the Markov chain, which are the
probabilities of small, medium and large cascades. We assess the variability
of these estimated probabilities with a bootstrap and find them to be
estimated to a useful accuracy. This assessment of variability is necessary
for getting useful estimates of large cascade probability because large
cascades are rare, and probability estimates for rare events have the
potential to be so wildly variable that they are useless.

The Markov chain only models the statistics of successive transitions in the
observed data. Also, there is an inherent limitation of not being able to
account for transitions and states not present in the observed data. That is,
the common transitions and states and some of the rarer transitions and states
will be present in the data and will be represented in the Markov model, while
the rarer transitions and states not present in the data will be neglected.
However, the Markov chain can produce, in addition to the observed cascades,
combinations of the observed transitions that are different than and much more
extensive than the observed cascades. The Markov chain approximates the
statistics of cascading rather than reproducing only the observed cascades.

We exploit the asymptotic properties of the Markov chain to calculate the
transmission lines most involved in the propagation of larger cascades, and we
show with the Markov chain that upgrading these lines can significantly reduce
the probability of large cascades. Since a large cascade of line outages with
many generations is very likely to shed substantial load, mitigating large
cascades will also mitigate blackouts with large amounts of load shed.

A Markov chain driven by real data incorporates all the causes, mechanisms,
and conditions of the cascading that occurred, but does not distinguish
particular causes of the interactions. However, once the lines critical to
large cascades have been identified with the influence graph, the causes
related to outage of those particular lines can be identified by analyzing
event logs and cause codes. Also, the overall impact on cascading of factors
such as loading and weather can be studied by dividing the data into low and
high loading or good and bad weather and forming influence graphs for each
case.

While the Markov model is driven by historical data in this paper, the Markov
model is not limited to historical data. The Markov model could be driven by
simulated cascades or a combination of simulated and historical cascades.
Moreover, if the probabilities of specific cascading interactions between line
outages are available, these probabilities could be combined into the entries
of the Markov transition matrices. The Markov chain is applied here to
cascading transmission line outages, but the formulation would apply generally
to process real or simulated data for the cascading outage of components
within or between networked infrastructures.

We show how to estimate the Markov chain from detailed outage data that is
routinely collected by utilities. Being driven by observed data has some
significant advantages of realism. In particular, and in contrast with
simulation approaches, no assumptions about the detailed mechanisms of
cascading need to made. Since the Markov chain driven by utility data has
different assumptions than simulation, we regard the Markov chain and
simulation approaches as complementary. The Markov chain driven by observed
data offers another way to find critical lines and to test proposed
mitigations of cascading by predicting the effect of the mitigation on the
probabilities of small, medium, and large cascades.

##  Appendix A Deriving the quasi-stationary distribution $\bm{d}_{\infty}$

The quasi-stationary distribution can be derived in a standard way [44, 45].
Let $\bm{d}_{k}$ be a vector with entry $d_{k}[i]$ which is the probability
that a cascade is in nonempty state $s_{i}$ at generation $k$ given that the
cascade is propagating, that is

$\displaystyle d_{k}[i]=\frac{{\rm P}[X_{k}=s_{i}]}{{\rm P}[X_{k}\neq
s_{0}]}=\frac{\pi_{k}[i]}{1-\pi_{k}[0]},\qquad i=1,...,|\mathcal{S}|$

Then the quasi-stationary distribution is
$\bm{d}_{\infty}=\lim_{k\rightarrow\infty}\bm{d}_{k}$.

Diagonal entries of $\bar{\bm{Q}}_{1+}$ corresponding to $\bar{\bm{P}}_{1+}$
are all zero and all other entries are positive. According to the Perron-
Frobenius theorem [46], $\bar{\bm{Q}}_{1+}$ has a unique maximum modulus
eigenvalue $\mu$, which is real, positive and simple with left eigenvector
$\bm{v}^{\prime}$. By normalizing $\bm{v}^{\prime}$, we make $\bm{v}^{\prime}$
a probability vector. We write $\bm{w}$ for the corresponding right
eigenvector. Moreover, $0<\mu<1$ and $\mu$ is strictly greater than the
modulus of the other eigenvalues of $\bar{\bm{Q}}_{1+}$. Suppose the cascade
starts with probability distribution $\bm{\pi}_{0}$ (note that
$\pi_{0}[0]=0$). According to (5), the probability of being in state $i$ at
generation $k$ is
$\pi_{k}[i]=(\bm{\pi}_{0}\bm{P}_{0}\bm{P}_{1}...\bm{P}_{k-2}\bm{P}_{k-1})[i]=(\bm{\pi}_{0}\bm{P}^{(k-1)})[i]$.
In particular, the probability that the cascade terminates by generation $k$
is
$\pi_{k}[0]=\bm{\pi}_{0}\bm{P}^{(k)}[0]=\bm{\pi}_{0}\bm{P}^{(k)}\bm{e}_{0}$.
Then for $i=1,...,|\mathcal{S}|$,

$\displaystyle
d_{k+1}[i]=\frac{\pi_{k+1}[i]}{1-\pi_{k+1}[0]}=\frac{(\bm{\pi}_{0}\bm{P}^{(k)})[i]}{1-\bm{\pi}_{0}\bm{P}^{(k)}\bm{e}_{0}}=\frac{(\bm{\pi}_{0}\bm{P}^{(k)})[i]}{\bm{\pi}_{0}\bm{P}^{(k)}({\bf
1}-\bm{e}_{0})}$

The first row of $\bm{P}_{k}$ is always $[1\quad 0\quad...\quad 0]$. Since
$\pi_{0}[0]=0$, let $\bm{\pi}_{0}=[0\quad\bar{\bm{\pi}}_{0}]$. Then
$\bm{\pi}_{0}\bm{P}^{(k)}({\bf
1}-\bm{e}_{0})=\bar{\bm{\pi}}_{0}\bm{Q}^{(k)}{\bf 1}$ and
$(\bm{\pi}_{0}\bm{P}^{(k)})[i]=(\bar{\bm{\pi}}_{0}\bm{Q}^{(k)})[i]$ for
$i=1,...,|\mathcal{S}|$. And
$\bm{Q}^{(k)}=\bar{\bm{Q}}_{0}\bar{\bm{Q}}_{1+}^{k-1}\prod_{m=0}^{k}(1-\alpha_{m})$,
so that $\bm{d}_{\infty}=\lim_{k\rightarrow\infty}\bm{d}_{k+1}$ is

$\displaystyle\bm{d}_{\infty}$
$\displaystyle=\lim_{k\rightarrow\infty}\frac{\bar{\bm{p}}_{0}\bm{Q}^{(k)}}{\bar{\bm{p}}_{0}\bm{Q}^{(k)}{\bf
1}}=\lim_{k\rightarrow\infty}\frac{\bar{\bm{p}}_{0}\bar{\bm{Q}}_{0}\bar{\bm{Q}}_{1+}^{k-1}\prod_{m=0}^{k}(1-\alpha_{m})}{\bar{\bm{p}}_{0}\bar{\bm{Q}}_{0}\bar{\bm{Q}}_{1+}^{k-1}\prod_{m=0}^{k}(1-\alpha_{m}){\bf
1}}$
$\displaystyle=\frac{\bar{\bm{p}}_{0}\bar{\bm{Q}}_{0}\mu^{k-1}\bm{w}\bm{v}^{\prime}}{\bar{\bm{p}}_{0}\bar{\bm{Q}}_{0}\mu^{k-1}\bm{w}\bm{v}^{\prime}{\bf
1}}=\bm{v}^{\prime}$

where $\bar{\bm{Q}}^{(k-1)}\rightarrow\mu^{k-1}\bm{w}\bm{v}^{\prime}$ as
$k\rightarrow\infty$. Therefore, the dominant left eigenvector of
$\bar{\bm{Q}}_{1+}$ is $\bm{d}_{\infty}$.

For our data, the top three eigenvalues in modulus are $\mu=0.502$ and
$-0.136\pm 0.122\,\rm i$ with corresponding moduli 0.502 and 0.381.

## References

  * [1] P. Hines, J. Apt, and S. Talukdar, “Large blackouts in North America: Historical trends and policy implications,” _Energy Policy_ , vol. 37, no. 12, pp. 5249–5259, Dec. 2009.
  * [2] B. A. Carreras, D. E. Newman, and I. Dobson, “North American blackout time series statistics and implications for blackout risk,” _IEEE Trans. Power Syst._ , vol. 31, no. 6, pp. 4406–4414, Nov. 2016.
  * [3] R. Baldick, B. Chowdhury, I. Dobson _et al._ , “Initial review of methods for cascading failure analysis in electric power transmission systems,” in _IEEE PES General Meeting_ , Pittsburgh, PA, USA, Jul. 2008.
  * [4] M. Papic, K. Bell, Y. Chen _et al._ , “Survey of tools for risk assessment of cascading outages,” in _IEEE PES General Meeting_ , Detroit, MI, USA, Jul. 2011.
  * [5] J. Bialek _et al._ , “Benchmarking and validation of cascading failure analysis tools,” _IEEE Trans. Power Syst._ , vol. 31, no. 6, pp. 4887–4900, Nov. 2016.
  * [6] E. Ciapessoni _et al._ , “Benchmarking quasi-steady state cascading outage analysis methodologies,” in _Prob. Methods Applied to Power Syst._ , Boise, ID, USA, Jun. 2018.
  * [7] M. Papic and I. Dobson, “Comparing a transmission planning study of cascading with historical line outage data,” in _Prob. Methods Applied to Power Syst._ , beijing, China, Oct. 2016.
  * [8] C. Asavathiratham, S. Roy, B. Lesieutre, and G. Verghese, “The influence model,” _IEEE Control Syst. Mag._ , vol. 21, no. 6, pp. 52–64, Dec. 2001.
  * [9] M. Rahnamay-Naeini, “Designing cascade-resilient interdependent networks by optimum allocation of interdependencies,” in _Int. Conf. Computing Networking and Communications_ , Kauai, HI, USA, Feb. 2016.
  * [10] P. Hines, I. Dobson, E. Cotilla-Sanchez _et al._ , “‘Dual graph’ and ‘random chemistry’ methods for cascading failure analysis,” in _Proc. 46th Hawaii Intl. Conf. System Sciences_ , Maui, HI, USA, Jan. 2013.
  * [11] J. Qi, K. Sun, and S. Mei, “An interaction model for simulation and mitigation of cascading failures,” _IEEE Trans. Power Syst._ , vol. 30, no. 2, pp. 804–819, Mar. 2015.
  * [12] P. Hines, I. Dobson, and P. Rezaei, “Cascading power outages propagate locally in an influence graph that is not the actual grid topology,” _IEEE Trans. Power Syst._ , vol. 32, no. 2, pp. 958–967, Mar. 2017.
  * [13] K. Zhou, I. Dobson, P. Hines, and Z. Wang, “Can an influence graph driven by outage data determine transmission line upgrades that mitigate cascading blackouts?” in _Prob. Methods Applied Power Syst._ , Boise, ID, USA, Jun. 2018.
  * [14] J. Qi, J. Wang, and K. Sun, “Efficient estimation of component interactions for cascading failure analysis by EM algorithm,” _IEEE Trans. Power Syst._ , vol. 33, no. 3, pp. 3153–3161, May 2018.
  * [15] X. Zhang, F. Liu, R. Yao _et al._ , “Identification of key transmission lines in power grid using modified k-core decomposition,” in _Proc. 3rd Int. Conf. Electric Power and Energy Conversion Systems_ , Istanbul, Turkey, Oct. 2013.
  * [16] H. M. Merrill and J. W. Feltes, “Cascading blackouts: Stress, vulnerability, and criticality,” _preprint_ , 2016. [Online]. Available: http://www.merrillenergy.com
  * [17] Z. Ma, C. Shen, F. Liu, and S. Mei, “Fast screening of vulnerable transmission lines in power grids: A pagerank-based approach,” _IEEE Trans. Smart Grid_ , vol. 10, no. 2, pp. 1982–1991, Mar. 2019.
  * [18] Y. Yang, T. Nishikawa, and A. E. Motter, “Vulnerability and cosusceptibility determine the size of network cascades,” _Phys. Rev. Lett._ , vol. 118, no. 4, p. 048301, 2017.
  * [19] B. A. Carreras, D. E. Newman, and I. Dobson, “Determining the vulnerabilities of the power transmission system,” in _Proc. 45th Hawaii Int. Conf. System Sciences_ , Maui, HI, USA, Jan. 2012, pp. 2044–2053.
  * [20] U. Nakarmi, M. Rahnamay-Naeini, and H. Khamfroush, “Critical component analysis in cascading failures for power grids using community structures in interaction graphs,” _IEEE Trans. Netw. Sci. Eng._ , 2019.
  * [21] W. Ju, K. Sun, and J. Qi, “Multi-layer interaction graph for analysis and mitigation of cascading outages,” _IEEE Trans. Emerg. Sel. Topics Circuits Syst._ , vol. 7, no. 2, pp. 239–249, Jun. 2017.
  * [22] C. Chen, W. Ju, K. Sun, and S. Ma, “Mitigation of cascading outages using a dynamic interaction graph-based optimal power flow model,” _IEEE Access_ , vol. 7, pp. 168 637–168 648, 2019.
  * [23] X. Wei, J. Zhao, T. Huang, and E. Bompard, “A novel cascading faults graph based transmission network vulnerability assessment method,” _IEEE Trans. Power Syst._ , vol. 33, no. 3, pp. 2995–3000, May 2018.
  * [24] K. Sun, Y. Hou, W. Sun, and J. Qi, _Power System Control Under Cascading Failures: Understanding, Mitigation, and System Restoration_. Wiley-IEEE Press, 2019.
  * [25] A. Wang, Y. Luo, G. Tu _et al._ , “Vulnerability assessment scheme for power system transmission networks based on the fault chain theory,” _IEEE Trans. Power Syst._ , vol. 26, no. 1, pp. 442–450, Feb. 2011.
  * [26] C. Luo, J. Yang, Y. Sun _et al._ , “Identify critical branches with cascading failure chain statistics and hypertext-induced topic search algorithm,” in _IEEE PES General Meeting_ , Chicago, IL, USA, 2017.
  * [27] L. Li, H. Wu, and Y. Song, “Temporal difference learning based critical component identifying method with cascading failure data in power systems,” in _IEEE PES General Meeting_ , Portland, OR, USA, Aug. 2018.
  * [28] L. Li, H. Wu, Y. Song, and Y. Liu, “A state-failure-network method to identify critical components in power systems,” _Electric Power Systems Research_ , vol. 181, p. 106192, 2020.
  * [29] Z. Wang, A. Scaglione, and R. J. Thomas, “A Markov-transition model for cascading failures in power grids,” in _Proc. 45th Hawaii Int. Conf. System Sciences_ , Maui, HI, USA, Jan. 2012, pp. 2115–2124.
  * [30] M. Rahnamay-Naeini, Z. Wang, N. Ghani _et al._ , “Stochastic analysis of cascading-failure dynamics in power grids,” _IEEE Trans. Power Syst._ , vol. 29, no. 4, pp. 1767–1779, Jul. 2014.
  * [31] M. Rahnamay-Naeini and M. M. Hayat, “Cascading failures in interdependent infrastructures: An interdependent Markov-chain approach,” _IEEE Trans. Smart Grid_ , vol. 7, no. 4, pp. 1997–2006, Jul. 2016.
  * [32] Z. Wang, M. Rahnamay-Naeini, J. M. Abreu _et al._ , “Impacts of operators’ behavior on reliability of power grids during cascading failures,” _IEEE Trans. Power Syst._ , vol. 33, no. 6, pp. 6013–6024, Nov. 2018.
  * [33] U. Nakarmi, M. Rahnamay-Naeini, M. J. Hossain, and M. A. Hasnat, “Interaction graphs for reliability analysis of power grids: A survey,” _arXiv preprint arXiv:1911.00475 [physics.soc-ph]_ , 2019.
  * [34] I. Dobson, “Estimating the propagation and extent of cascading line outages from utility data with a branching process,” _IEEE Trans. Power Syst._ , vol. 27, no. 4, pp. 2146–2155, Nov. 2012.
  * [35] Bonneville power administration transmission services operations & reliability website. [Online]. Available: https://transmission.bpa.gov/Business/Operations/Outages
  * [36] I. Dobson _et al._ , “Obtaining statistics of cascading line outages spreading in an electric transmission network from standard utility data,” _IEEE Trans. Power Syst._ , vol. 31, no. 6, pp. 4831–4841, Nov. 2016.
  * [37] A. C. Davison and D. V. Hinkley, _Bootstrap methods and their application (Vol. 1)_. Cambridge, U.K.: Cambridge Univ. Press, 1997.
  * [38] M. Vaiman _et al._ , “Risk assessment of cascading outages: methodologies and challenges,” _IEEE Trans. Power Syst._ , vol. 27, no. 2, pp. 631–641, May 2012.
  * [39] I. Dobson, “Finding a Zipf distribution and cascading propagation metric in utility line outage data,” _arXiv preprint arXiv:1808.08434 [physics.soc-ph]_ , 2018.
  * [40] S. D. Guikema, “Formulating informative, data-based priors for failure probability estimation in reliability analysis,” _Reliability Engineering & System Safety_, vol. 92, no. 4, pp. 490–502, Apr. 2007.
  * [41] B. P. Carlin and T. A. Louis, _Bayesian methods for data analysis_. Boca Raton, FL, USA: CRC Press, 2008.
  * [42] E. T. Jaynes, “Bayesian methods: General background,” in _Maximum Entropy and Bayesian Methods in Applied Statistics, Cambridge, U.K._ Cambridge Univ. Press, 1986.
  * [43] S.-C. Fang, J. R. Rajasekera, and H.-S. J. Tsao, _Entropy optimization and mathematical programming_. Springer, 2012\.
  * [44] J. N. Darroch and E. Seneta, “On quasi-stationary distributions in absorbing discrete-time finite Markov chains,” _J. Appl. Probab._ , vol. 2, no. 1, pp. 88–100, Jun. 1965.
  * [45] E. V. Doorn and P. Pollett, “Quasi-stationary distributions for discrete-state models,” _European J. Operat. Res._ , vol. 230, pp. 1–14, 2013.
  * [46] W. J. Stewart, _Introduction to the numerical solution of Markov chains_. Princeton, NJ, USA: Princeton Univ. Press, 1994.

Kai Zhou (S’19) received the B.S degree in electrical engineering from China
Agriculture University in 2014, and the M.S. degree in electrical engineering
from Tianjin University in 2017. He is currently pursuing the Ph.D. degree
with Iowa State University, Ames, IA, USA. His current research interests
include cascading failures and data analytics.

Ian Dobson (F’06) received the B.A. degree in mathematics from Cambridge
University, UK, and the Ph.D. degree in electrical engineering from Cornell
University, USA. He is currently Sandbulte Professor of Engineering at Iowa
State University, Ames, IA, USA.

Zhaoyu Wang (S’13-M’15) is the Harpole-Pentair Assistant Professor with Iowa
State University. He received the B.S. and M.S. degrees in electrical
engineering from Shanghai Jiaotong University in 2009 and 2012, respectively,
and the M.S. and Ph.D. degrees in electrical and computer engineering from
Georgia Institute of Technology in 2012 and 2015, respectively. His research
interests include power distribution systems and microgrids, particularly on
their data analytics and optimization. He is the Principal Investigator for a
multitude of projects focused on these topics and funded by the National
Science Foundation, the Department of Energy, National Laboratories, PSERC,
and Iowa Energy Center. Dr. Wang is the Secretary of IEEE Power and Energy
Society (PES) Award Subcommittee, Co-Vice Chair of PES Distribution System
Operation and Planning Subcommittee, and Vice Chair of PES Task Force on
Advances in Natural Disaster Mitigation Methods. He is an editor of IEEE
Transactions on Power Systems, IEEE Transactions on Smart Grid, IEEE PES
Letters and IEEE Open Access Journal of Power and Energy, and an associate
editor of IET Smart Grid.

Alexander Roitershtein is a Research Associate at the Department of
Statistics, Texas A&M University. He received the Ph.D. in Applied Mathematics
from Technion, Israel Institute of Technology in 2004. His research interests
include random walk models and their applications, population dynamics,
complex networks, microbiome ecology, applications of branching processes to
biology, stochastic processes in random environment, and general theory of
Markov chains.

Arka Ghosh is a Professor of Statistics at Iowa State University and holds
courtesy appointments in Departments of Mathematics as well as in Industrial
Manufacturing and Systems Engineering. He received his B. Stat and M. Stat
degrees from Indian Statistical Institute and Ph.D in Statistics from
University of North Carolina at Chapel Hill and joined Iowa State University
in 2005. His interests are primarily in Applied Probability and Statistics,
including Stochastic Modeling, Queueing theory, Random Graphs, Network
Modeling.


11footnotetext: Warsaw University of Technology, Poland22footnotetext: IDEAS
NCBR, Poland33footnotetext: Tooploox, Poland11footnotetext: Corresponding
author<EMAIL_ADDRESS>
# On consequences of finetuning on data with highly discriminative features

Wojciech Masarczyk1,* &Tomasz Trzciński1,4,6 &Mateusz Ostaszewski1

##  1 Introduction

Deep learning has witnessed remarkable advancements in various domains, driven
by the ability of neural networks to learn intricate patterns from data. One
key aspect contributing to their success is the process of transfer learning,
where pre-trained models are fine-tuned on specific tasks, leveraging
knowledge acquired from previous training Pratt and Jennings (1996); Yosinski
et al. (2014). This technique is especially important in the advent of
training ever-growing models such as Large Language Models (LLMs) Devlin et
al. (2019); et al. (2023b); OpenAI (2023) or massive ViTs Zhai et al. (2022);
et al. (2023a). However, while transfer learning is a powerful tool, it is not
without its nuances.

Figure 1:  Feature erosion for VGG-19 on CIFAR-10. Introducing a simpler
discriminative feature (green hatch area) solely focuses the model on that
feature (red curve) and abruptly erases previous knowledge about the data
(blue line).

This work presents a thought-provoking experiment exposing a network’s
tendency to greedily follow the simplest discriminative features present in
the data. This phenomenon was observed in multiple works and is commonly
called simplicity bias Arpit et al. (2017); Valle-Pérez et al. (2019);
Nakkiran et al. (2019). Here, we take a step further and investigate the
implications of this behavior in the realms of transfer learning.

To investigate this effect, we train the network on CIFAR-10 to perfect
training accuracy (error-free). Next, we introduce a highly discriminative,
class-correlated pattern to the corner of each dataset image and proceed with
the training. Surprisingly, as shown in Fig. 1, despite the model’s perfect
accuracy, finetuning it on the oversimplified task causes an abrupt
performance loss (blue curve) and pushes the model to focus solely on the
novel pattern. We call this phenomenon feature erosion. Our analysis shows
that during the fine-tuning phase, the pretrained model greedily abandons
salient, generalizing features in favor of the new discriminative ones.

In Section 2, we define details of the experiments and investigate the breadth
of the phenomenon 2, presenting that all tested contemporary neural networks
exhibit this behavior. Next, we investigate the detrimental effect of feature
erosion on the model’s representation formation, transfer learning, and
plasticity. Section 3 discusses the phenomenon’s implications, its novelty
concerning related works, and its hazards to real-world applications.

(a) ResNet 18 - CIFAR-10

(b) ResNet 50 - ImageNet

(c) VGG-19 - ImageNet

Figure 2: Feature erosion effect for ResNet18 trained on CIFAR-10 (left)
ResNet50 trained of ImageNet (middle) and VGG-19 trained on ImageNet (right).
ImageNet models used pretrained weights provided by PyTorch. ResNet18 reached
100% training accuracy before introducing the discriminative pattern to the
dataset.

##  2 Experiments and results

In this section, we explore the phenomenon we introduced in the previous
section, aiming to understand its severity and impact on network behavior. We
initiate our investigation by examining the robustness of feature erosion
across different network architectures and datasets (Fig. 2). Next, we assess
the detrimental effect of the phenomenon on the network’s representations
(Fig. 3) and show that pursuing simpler, discriminative patterns collapse the
network’s rank (Fig. 4). We hypothesize that this effect is linked with the
loss of plasticity observed in further training of that network (Fig. 5).

Experimental setup We will now delve into feature erosion using ResNet-18,
ResNet-50, and VGG-19 models trained on either the CIFAR-10 or ImageNet
dataset. For CIFAR-10, these networks underwent 160 training epochs,
consistently achieving $100\%$ training accuracy before introducing the
oversimplified second task. The same hyperparameters were maintained for an
additional 160 epochs during the second task, following recommendations for
optimal model performance by Liu et al. Liu et al. (2018).

Regarding the ImageNet models, we utilized PyTorch’s pre-trained weights and
randomly selected a subset of 10 classes from the ImageNet dataset for the
oversimplified task. To create this dataset, we superimposed squares of the
same size and placement on the training images, with each square’s color
representing the image’s class. In most of our experiments, we applied these
squares to all training images, the exception is presented in Fig. 6, where we
investigated the impact of that ratio on the model’s performance.

Feature Erosion for different models and datasets

Figure 3: Feature erosion impacts CKA similarity between representations from
different layers extracted from the model after completing the 1st and 2nd
tasks. The experiment was conducted using the VGG-19 model and the CIFAR-10
dataset.

The performance of these models is illustrated in Figure 2, showcasing test
accuracy curves during both the pretraining phase (white background) and the
subsequent fine-tuning phase on the oversimplified task (green-hatched
background). The results clearly indicate that all neural architectures and
datasets exhibit feature erosion, resulting in a noticeable decline in test
accuracy on the pre-training dataset. Notably, as the sole distinction between
the first and second tasks is the presence of these colored squares, the
dramatic shift from near-perfect accuracy in the first task to random-chance
accuracy in the second task implies that the model exclusively focuses on the
colored squares.

Unpacking Feature Erosion: Analyzing Representations

Having observed significant shifts in model performance on established
benchmarks, our objective is to investigate the impact of fine-tuning on
oversimplified datasets on the model’s representations.

In our subsequent experiment, we perform a comparative analysis of
representations at each layer after training on the first task and subsequent
training on the second task. We employ Centered Kernel Alignment (CKA)
Kornblith et al. (2019) as a metric to quantify similarity. We extract
representations from standard CIFAR-10 datasets (without color squares) for
both models to isolate the impact of weight evolution on model
representations.

Figure 4: Feature Erosion collapses rank of the hidden representations and
impacts linear probing accuracy of VGG-19 trained on CIFAR10. Crosses refer to
model after pre-training, dots refer to the model after finetuning. Blue color
refer to the test accuracy, orange color refers to the representations rank.

As illustrated in Figure 3, the representations show substantial
dissimilarity. Most notably, most diagonal elements are black, indicating
minimal similarity between representations within the same layers after
undertaking different tasks. The lighter colors in the top left corner suggest
that changes during the fine-tuning phase commence early in the network,
particularly in the bottom layers.

Given the observed dramatic changes in representations across nearly all
layers, we delve deeper into understanding the underlying dynamics. In Fig. 4,
we investigate feature erosion within each layer using linear probing and the
numerical rank of representations. A comparison of the linear probing plots
reveals that after fine-tuning (blue dots), the model fully adapts to the new
data, with the second layer achieving accuracy levels comparable to those of
the entire model. Furthermore, the numerical rank of representations
experiences a substantial decline at each layer following fine-tuning (red
dots), indicating that the model, starting from the initial layers, probably
adheres to the simplicity bias Morwani et al. (2023) and projects the data
into smaller subspaces.

Loss of plasticity

To better understand the impact of feature erosion on network performance, we
examined the network’s ability to relearn information from a previous task. We
conducted experiments involving a sequence of three tasks: CIFAR-10 (Task 0),
an oversimplified version of CIFAR-10, and the standard CIFAR-10 once again
(Task 2).

Typically, relearning is expected to be faster and require fewer computational
resources than training from scratch. However, our results, as shown in Figure
1, indicate a deviation from this expected behavior. In this setup, the
network not only learns more slowly compared to training from scratch but also
fails to achieve the same level of performance within the same computational
budget as the network trained from scratch. This performance difference is
commonly referred to as "loss of plasticity" and is often associated with the
degradation of the penultimate layer’s rank. While we speculate that this
explanation may apply in our case, a thorough investigation of this hypothesis
is beyond the scope of our current research.

Figure 5: Loss of plasticity. The model is trained on the sequence of 3 tasks.
The first (Task 0) and the last (Task 2) are standard CIFAR-10 datasets. The
middle task is CIFAR-10 with correlated squares.

##  3 Discussion

In this study, we have uncovered a nuanced aspect of catastrophic forgetting,
demonstrating that it can occur even when the full dataset is present in the
new task data. Our experiments, which include GradCam analysis, reveal that
despite achieving 100% training accuracy after introducing highly
discriminative features to the model, it begins to focus exclusively on these
new features, leaving behind previously developed ones. A deeper investigation
using techniques such as Centered Kernel Alignment (CKA) exposes significant
changes in representations, along with a deterioration in model performance
indicated by a rank collapse of representations in nearly all layers.

Our research expands our knowledge of the complex relationship between task
similarity (Ramasesh et al., 2020; Braun et al., 2022), forgetting, and
transfer dynamic (Chen et al., 2022). On the one hand, recent studies have
revealed that intermediate task similarity tends to contribute most to
catastrophic forgetting (Ramasesh et al., 2020; Braun et al., 2022). The task
similarity is the use of a "data-mixing framework," which combines images and
labels from two distinct datasets of equal size. However, our experimental
setup features identical datasets, differing only in a small image segment
transitioning from random to highly correlated with a specific class. While
this does not contradict earlier findings, it certainly introduces a novel
perspective on the phenomenon. On the other hand, our observation also has
implications in light of recent research (Chen et al., 2022), which suggests
that less forgetful representations result in improved performance on new
tasks, indicating a robust relationship between retaining previous information
and enhanced learning efficiency. In this context, our toy example falsifies
the reverse implication, i.e., the model exhibits perfectly transferable
features yet forgets them in favor of features with greater predictive power.

Figure 6: The stronger the discriminative pattern (higher ratio), the higher
the forgetting of the model. Each dot represents a single model trained on
CIFAR-10 and fine-tuned on an oversimplified task with different ratios of
images with colored squares.

In our concluding experiment, extending our analysis of feature erosion, we
explore the relation between forgetting and the ratio of samples containing
oversimplified discriminative patterns. In Fig. 6, we observe a non-linear
relationship between the number of oversimplified samples in the training
dataset and the extent of forgetting. However, even modest ratios of
oversimplified data are enough to induce forgetting in the model. This
reinforces the importance of the phenomenon.

The situation we present in this study has practical significance, especially
in scenarios involving incremental learning in various domains. Real-world
applications that continually receive new data with limited human involvement
might come across samples containing highly predictive patterns. This can lead
to the loss of previously acquired knowledge. For instance, in medical
imaging, where data artifacts may correlate with task objectives, the
phenomenon of feature erosion could be a frequent concern.

Additionally, our findings connect with existing literature on concepts such
as simplicity bias (Neyshabur et al., 2014; Shah et al., 2020) and gradient
starvation (Pezeshki et al., 2021). Our results suggest that simplicity bias
not only affects generalization but can also disrupt previously well-
functioning representations. The resilience of simplicity bias to approaches
like ensembles or adversarial training raises questions about the
effectiveness of common continual learning methods.

Finally, there may be a positive aspect to this phenomenon. In the current era
of heightened focus on AI ethics, machine unlearning (Bourtoule et al., 2021)
and fairness in deep learning (Du et al., 2020) are prominent topics. Our
study prompts the question of whether intentionally introducing highly
discriminatory patterns to unwanted samples can facilitate the intentional
forgetting of such samples, a topic that warrants further exploration.

In summary, our work reveals a novel facet of catastrophic forgetting,
challenging conventional wisdom about its occurrence and implications. These
findings have relevance for both the field of machine learning and practical
applications that involve continual learning with evolving data.

## References

  * Arpit et al. (2017) Devansh Arpit, Stanisław Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien.  A closer look at memorization in deep networks, 2017.
  * Bourtoule et al. (2021) Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot.  Machine unlearning.  In _2021 IEEE Symposium on Security and Privacy (SP)_ , 2021.
  * Braun et al. (2022) Lukas Braun, Clémentine Dominé, James Fitzgerald, and Andrew Saxe.  Exact learning dynamics of deep linear networks with prior knowledge.  _Advances in Neural Information Processing Systems_ , 2022.
  * Chen et al. (2022) Jiefeng Chen, Timothy Nguyen, Dilan Gorur, and Arslan Chaudhry.  Is forgetting less a good inductive bias for forward transfer?  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding, 2019.
  * Du et al. (2020) Mengnan Du, Fan Yang, Na Zou, and Xia Hu.  Fairness in deep learning: A computational perspective.  _IEEE Intelligent Systems_ , 2020.
  * et al. (2023a) M. Dehghani et al.  Scaling vision transformers to 22 billion parameters, 2023a.
  * et al. (2023b) R. Anil et al.  Palm 2 technical report, 2023b.
  * Kornblith et al. (2019) Simon Kornblith, Mohammad Norouzi, Honglak Lee, and Geoffrey E. Hinton.  Similarity of neural network representations revisited.  _International Conference on Machine Learning_ , 2019.
  * Liu et al. (2018) Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell.  Rethinking the value of network pruning.  _International Conference on Learning Representations_ , 2018.
  * Morwani et al. (2023) Depen Morwani, Praneeth Netrapalli, jatin batra, Karthikeyan Shanmugam, and Prateek Jain.  Simplicity bias in $1$-hidden layer neural networks, 2023.
  * Nakkiran et al. (2019) Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L. Edelman, Fred Zhang, and Boaz Barak.  Sgd on neural networks learns functions of increasing complexity, 2019.
  * Neyshabur et al. (2014) Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro.  In search of the real inductive bias: On the role of implicit regularization in deep learning.  _arXiv preprint arXiv:1412.6614_ , 2014.
  * OpenAI (2023) OpenAI.  Gpt-4 technical report, 2023.
  * Pezeshki et al. (2021) Mohammad Pezeshki, Oumar Kaba, Yoshua Bengio, Aaron C Courville, Doina Precup, and Guillaume Lajoie.  Gradient starvation: A learning proclivity in neural networks.  _Advances in Neural Information Processing Systems_ , 2021.
  * Pratt and Jennings (1996) Lorien Pratt and Barbara Jennings.  A survey of transfer between connectionist networks.  _Connection Science_ , 1996.
  * Ramasesh et al. (2020) Vinay Venkatesh Ramasesh, Ethan Dyer, and Maithra Raghu.  Anatomy of catastrophic forgetting: Hidden representations and task semantics.  In _International Conference on Learning Representations_ , 2020.
  * Shah et al. (2020) Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli.  The pitfalls of simplicity bias in neural networks.  _Advances in Neural Information Processing Systems_ , 2020.
  * Valle-Pérez et al. (2019) Guillermo Valle-Pérez, Chico Q. Camargo, and Ard A. Louis.  Deep learning generalizes because the parameter-function map is biased towards simple functions, 2019.
  * Yosinski et al. (2014) Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson.  How transferable are features in deep neural networks?, 2014.
  * Zhai et al. (2022) Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer.  Scaling vision transformers, 2022.