scaletikzpicturetowidth[1]

# Ramsey and Hypersmoothness

Zoltán Vidnyánszky  Zoltán Vidnyánszky
California Institute of Technology
Department of Mathematics
1200 E California Blvd, Pasadena, CA 91125
USA<EMAIL_ADDRESS>http://https://www.its.caltech.edu/ vidnyanz/

###### Abstract.

Combining canonization results of Prömel-Voigt, Mathias, and Soare, we provide
a new, natural example of an $F_{\sigma}$ equivalence relation that is not
hypersmooth.

Assume that $E$ is a countable Borel equivalence relation on the space
$[\mathbb{N}]{N}$. It follows from the work of Mathias [4] and Soare [7] that
one can find an $x\in[\mathbb{N}]{N}$ such that $E\upharpoonright[x]{N}$ is
hyperfinite (in fact, contained in $\mathbb{E}_{0}$, see [1]). In contrast,
equivalence relations with uncountable classes can exhibit complicated
behavior on every set of the form $[x]{N}$.

In this note, we give an example of an $F_{\sigma}$ equivalence relation on
$[\mathbb{N}]{N}$ that is not hypersmooth (see [2] for more information on
such equivalence relations) and the reason for this is completely Ramsey-
theoretic. The equivalence relation comes from a natural generalization of the
shift-graph (see [3, 8]) and it is generated by two continuous functions.

##  1\. The construction

######  Theorem 1.1.

Assume that $E$ is an equivalence relation on $[\mathbb{N}]{N}$ such that for
every $x\in[\mathbb{N}]{N}$

  * •

there exist almost disjoint $y,z\in[x]{N}$ such that $yEzEx$ and

  * •

$E\upharpoonright[x]{N}$ has uncountably many equivalence classes.

Then $E$ is not hypersmooth.

In order to establish this theorem, we will need the following statement.

######  Theorem 1.2.

Assume that $(f_{n})_{n\in\mathbb{N}}:[\mathbb{N}]^{\mathbb{N}}\to(2{N}){N}$
are Borel. There exist an $x\in[\mathbb{N}]{N}$ and a countable set $C$ such
that for every $y,z\in[x]{N}$ almost disjoint and $n\in\mathbb{N}$ we have
that $f_{n}(z)=f_{n}(y)$ implies $f_{n}(y)\in C$.

The proof of this theorem is based on the results of Prömel-Voigt [5], Mathias
[4] and Soare [7] and postponed to the next section.

###### Proof of Theorem 1.1.

Assume the contrary, and let $\varphi$ be a Borel reduction from $E$ to
$E_{1}$. Let $f_{n}=p^{n}\circ\varphi$ where
$p((x_{n})_{n\in\mathbb{N}})=(x_{n+1})_{n\in\mathbb{N}}$. Clearly, if $yEz$
then for some $n$ we have $f_{n}(x)=f_{n}(y)$.

Let $x$ and $C$ be as in Theorem 1.2 for the sequence
$(f_{n})_{n\in\mathbb{N}}$. We claim that $\varphi([x]{N})$ is contained in
countably many $E_{1}$ equivalence classes, contradicting our second
assumption. Indeed, take the countable set
$C^{\prime}=\\{(x_{n})_{n\in\mathbb{N}}:\exists m\ (\forall n<m\
x_{n}=0\land(x_{m},x_{m+1},\dots)\in C)\\}$. If $x^{\prime}\in[x]{N}$ then by
the first assumption, there are $y,z\in[x^{\prime}]{N}$ almost disjoint such
that $yEzEx^{\prime}$. Then, for some $n$ we have $f_{n}(y)=f_{n}(z)\in C$, so
$\varphi(x^{\prime})\in[C^{\prime}]_{E_{1}}$. ∎

We identify elements of $[\mathbb{N}]{N}$ with their increasing enumeration.
Let $S_{0},S_{1}$ be maps on $[\mathbb{N}]{N}$ defined by

$S_{0}(\\{n_{0},n_{1},n_{2},\dots\\})=\\{n_{1},n_{2},n_{3}\dots\\},$
$S_{1}(\\{n_{0},n_{1},\dots\\})=\\{n_{1},n_{3},n_{5},\dots\\}.$

Denote by $G$ the graph determined by $S_{0}$ and $S_{1}$, and let $E$ be the
connected component equivalence relation of $G$.

For $x,y\in[\mathbb{N}]{N}$ define $x\ll y$ if for each $m$ there is a $k$
such that $|x\cap(y_{k},y_{k+1})|>m$. It is easy to check the following:

######  Lemma 1.3.

Assume that $x\ll y$ and $\\{x^{\prime},x\\}\in G$. Then $x^{\prime}\ll y$.

Now we show that $E$ is an example of the phenomenon described in the main
theorem.

######  Proposition 1.4.

$E$ is not hypersmooth.

###### Proof.

We check the conditions of Theorem 1.1. First, for any $x^{\prime}$ we have
$S_{1}\circ S_{0}(x^{\prime})\cap S_{1}(x^{\prime})=\emptyset$ and both
$S_{1}\circ S_{0}(x^{\prime})$ and $S_{1}(x^{\prime})$ are contained in
$x^{\prime}$.

Second, assume that $x$ is given and $\\{x_{n}:n\in\mathbb{N}\\}\subset[x]{N}$
is arbitrary. It is sufficient to produce a $y\in[x]{N}$ such that $y$ is not
$E$ equivalent to either of the $x_{n}$’s. Let $y\subset x$ be so that
$x_{n}\ll y$ for all $n$. Then by Lemma 1.3 and by $y\not\ll y$ we are done. ∎

The following proposition concludes our construction.

######  Proposition 1.5.

$E$ is $F_{\sigma}$.

###### Proof.

For $x,y\in[\mathbb{N}]{N}$ let $x\leq y$ stand for $\forall n\ (x_{n}\leq
y_{n})$. Note that for each $i<2$ we have $x\leq S_{i}(x)$. For $s\in
2^{<\mathbb{N}}$ let

$D_{s}=\\{(x,y):x\leq S_{s(n-1)}\circ\dots\circ S_{s(1)}\circ S_{s(0)}(y)\\},$

and let $D(y)=\bigcup_{s\in 2^{<\mathbb{N}}}\\{x:(x,y)\in D_{s}\\}$, that is,
$D(y)$ is the collection of the points that are pointwise below some forward
iterate of $y$.

######  Claim 1.6.

If $xGx^{\prime}$ and $x\in D(y)$ then $x^{\prime}\in D(y)$. Thus,
$[y]_{E}\subseteq D(y)$ for all $y$.

###### Proof.

If $x^{\prime}=S_{i}(x)$ for some $i<2$ and $(x,y)\in D_{s}$, then
$(x^{\prime},y)\in
D_{s\mathbin{\raisebox{3.01389pt}{\scalebox{0.7}{$\frown$}}}(i)}$. Otherwise,
if $x=S_{i}(x^{\prime})$, then $x^{\prime}\leq S_{i}(x^{\prime})=x$, so
$x^{\prime}\in D(y)$ as well. ∎

Let $(x,y)\in R_{n}$ iff $\exists k\leq n\ \exists x_{0},\dots,x_{k-1}\
\exists s_{0},\dots,s_{k-1}\in 2^{\leq n}$

$\forall i<k\ (x_{i}Gx_{i+1}\land(x_{i},y)\in D_{s_{i}})\land x_{0}=x\land
x_{k-1}=y.$

By Claim 1.6, $E=\bigcup_{n}R_{n}$. It follows from the continuity of the
functions $(S_{i})_{i<2}$ that each $D_{s}$ is closed and that for each $y$
the set $\\{x:(x,y)\in D_{s}\\}$ is compact. From this, it is straightforward
to show that $R_{n}$ is closed for every $n\in\mathbb{N}$, which finishes our
proof. ∎

##  2\. A version of Prömel-Voigt

Let us recall the canonization results of Prömel and Voigt [5].

######  Theorem 2.1 (Prömel-Voigt [5]).

Assume that $f:[\mathbb{N}]{N}\to 2{N}$ is a Borel function. There exist an
$x\in[\mathbb{N}]{N}$ and a function
$\Gamma:[x]{N}\to[\mathbb{N}]^{\leq\mathbb{N}}$ with the following properties:

  1. (1)

for every $y\in[x]{N}$ we have $\Gamma(y)\subseteq y$,

  2. (2)

for every $y,z\in[x]{N}$ we have

$f(y)=f(z)\iff\Gamma(y)=\Gamma(z)$

  3. (3)

either for every $y\in[x]{N}$ we have that $\Gamma(y)$ is finite or for every
$y\in[x]{N}$ it is infinite,

  4. (4)

for every $y,z\in[x]{N}$ we have that $\Gamma(y)$ is not a proper initial
segment of $\Gamma(z)$,

  5. (5)

$\Gamma$ is continuous (where the topology on $[\mathbb{N}]^{\leq\mathbb{N}}$
comes from its ideintification with $2{N}$).

For $x\in[\mathbb{N}]{N}$ and $f:[\mathbb{N}]{N}\to X$ define

$C_{f,x}=\\{f(x^{\prime}):x^{\prime}\mathbb{E}_{0}x\\}.$

######  Lemma 2.2.

Let $x$, $\Gamma$ and $f$ be as above. If for some $y\in[x]{N}$ the set
$\Gamma(y)$ is finite, then for all $x^{\prime}\in[x]{N}$ we have $f(y)\in
C_{f,x^{\prime}}$.

###### Proof.

Let $x^{\prime}\in[x]{N}$ be arbitrary. By the continuity of $\Gamma$ we can
find some $x^{\prime\prime}\mathbb{E}_{0}x^{\prime}$ with
$x^{\prime\prime}\in[x]{N}$ such that $\Gamma(y)$ is an initial segment of
$\Gamma(x^{\prime\prime})$. By 4 this implies that
$\Gamma(x^{\prime\prime})=\Gamma(y)$, so $f(y)=f(x^{\prime\prime})\in
C_{f,x^{\prime}}$. ∎

Let us point out that the preceeding argument is the only thing what one needs
to prove Theorem 1.2, in the case of a single function. However, to treat
countably many functions, we have to prove an analogous statement for sets of
the form $[s,x]$, where $s\in\mathbb{N}^{<\mathbb{N}}$ and
$x\in[\mathbb{N}]{N}$. This requires some work and the utilization of the
result of Mathias and Soare mentioned in the introduction.

If $\Gamma$ is a function as above, define a partial function
$\Gamma^{*}:2{N}\to[x]{N}$ by

$\Gamma^{*}(w)=z\iff\exists y\in[x]{N}\ f(y)=w\text{ and }\Gamma(y)=z.$

The following is obvious from the definition.

######  Lemma 2.3.

  * •

$\Gamma^{*}$ is relatively Borel on the (possibly proper) analytic set
$f([x]{N})$; in particular, it is Souslin-measurable.

  * •

For every $y\in[x]{N}$ we have

$\Gamma^{*}(f(y))=\Gamma(y).$

We will need the following theorem (see also [1]).

######  Theorem 2.4 (Mathias [4], Soare [7]).

Let $(g_{n})_{n\in\mathbb{N}}:[\mathbb{N}]{N}\to[\mathbb{N}]{N}$ be a
collection of Souslin-measurable functions. There exists an
$x\in[\mathbb{N}]{N}$ such that for every $y\in[x]{N}$ and for every
$n\in\mathbb{N}$ we have that $g_{n}(y)\in[x]{N}$ implies that
$g_{n}(y)\setminus y$ is finite.

Note that Soare only establishes the above theorem for Borel functions (and
the proof of Kanovei-Sabok-Zapletal is also only for such), however, as by
Silver’s theorem [6] every Souslin-measurable set has the Ramsey property, the
proof extends to the class of Souslin-measurable maps without further
modification.

The key ingredient to prove Theorem 1.1 is the following. For a function $f$
and an $x\in[\mathbb{N}]{N}$ define
$C_{f,x}=\\{f(x^{\prime}):x^{\prime}\mathbb{E}_{0}x\\}$.

######  Lemma 2.5.

Let $s\in\mathbb{N}^{<\mathbb{N}}$ and $x\in[\mathbb{N}]{N}$ with $\max s<\min
x$ be arbitrary and $f:[\mathbb{N}]{N}\to 2{N}$ be a Borel function. There
exists an $x^{\prime}\in[x]{N}$ such that whenever $y,z\in[s\cup
x^{\prime}]{N}$ are almost disjoint and $f(y)=f(z)$ then $f(y)\in
C_{f,x^{\prime\prime}}$ for each $x^{\prime\prime}\in[x^{\prime}]{N}$.

###### Proof.

For $t\subseteq s$ and $y\in[x]{N}$ define a function $f^{t}$ by

$f^{t}=f(t\cup y).$

By applying Theorem 2.1 $2^{|s|}$ many times, we can find an $x^{*}\in[x]{N}$
and functions $\Gamma_{t},\Gamma^{*}_{t}$ with the properties as in the
theorem with respect to the function $f^{t}$ on $[x^{*}]{N}$. For
$r,t\subseteq s$ let $g^{r,t}$ be the function $\Gamma^{*}_{t}\circ f^{r}$.
Note that $g^{r,t}$ is Souslin-measurable. By Theorem 2.4 we can find an
$x^{\prime}\in[x^{*}]{N}$ such that whenever $y\in[x^{\prime}]{N}$ and
$g^{r,t}(y)\in[x^{\prime}]{N}$ for some $r,t\subseteq s$ then
$g^{r,t}(y)\setminus y$ is finite.

We claim that $x^{\prime}$ has the desired property. Let
$y,z\in[s,x^{\prime}]{N}$ be almost disjoint, and assume that $f(y)=f(z)$, let
$r=y\cap s$ and $t=z\cap s$. Using Lemma 2.2 it suffices to show that
$\Gamma_{r}(y\cap x^{\prime})$ is finite: indeed, in this case
$f(y)=f^{r}(y\cap x^{\prime})\in C_{f^{r},x^{\prime\prime}}\subseteq
C_{f,x^{\prime\prime}}$ for each $x^{\prime\prime}\in[x^{*}]{N}$, in
particular $f(y)\in C_{f,x^{\prime}}$. Now,

$g^{t,r}(z\cap x^{\prime})=\Gamma^{*}_{r}(f^{t}(z\cap
x^{\prime}))=\Gamma^{*}_{r}(f(t\cup z))=\Gamma^{*}_{r}(f(z))=$
$\Gamma^{*}_{r}(f(y))=\Gamma^{*}_{r}(f(r\cup
y))=\Gamma^{*}_{r}(f^{r}(y))=\Gamma^{*}_{r}(f^{r}(y\cap x^{\prime}))=$
$\Gamma_{r}(y\cap x^{\prime})\subseteq y\cap x^{\prime}.$

So, as $z\cap x^{\prime},g^{t,r}(z\cap x^{\prime})\in[x^{\prime}]{N}$, we must
have that

$g^{t,r}(z\cap x^{\prime})\setminus(z\cap x^{\prime})=\Gamma_{r}(y\cap
x^{\prime})\setminus(z\cap x^{\prime})$

is finite. Therefore, $\Gamma_{r}(y\cap x^{\prime})$ is almost contained in
both $y\cap x^{\prime}$ and $z\cap x^{\prime}$, which show that this set is
finite. ∎

Finally, we prove Theorem 1.2 using a standard fusion argument.

###### Proof of Theorem 1.2.

Define sequences $s_{0}\subset s_{1}\subset\dots$ and $x_{0}\supseteq
x_{1}\supseteq\dots$ of elements in $[\mathbb{N}]^{<\mathbb{N}}$ and
$[\mathbb{N}]^{\mathbb{N}}$ respectively, such that for every $n\in\mathbb{N}$

  * •

$\max s_{n}<\min x_{n}$,

  * •

$s_{n+1}=s_{n}\cup\\{\min x_{n}\\}$,

  * •

for every $y,z\in[s_{n}\cup x_{n}]{N}$ almost disjoint, if $f_{n}(y)=f_{n}(z)$
then $f_{n}(y)\in C_{f_{n},x_{n}}$

by induction on $n$. Indeed, let $s_{-1}=\emptyset$ and $x_{-1}=\mathbb{N}$,
given $s_{n-1},x_{n-1}$, let $s_{n}=s_{n-1}\cup\\{\min x_{n-1}\\}$. Using
Lemma 2.5 for every $s\subseteq s_{n}$, we can find an $x_{n}\subseteq
x_{n-1}$ that satisfies all the above properties.

Now let $x=\bigcup_{n\in\mathbb{N}}s_{n}$, $C=\bigcup_{n}C_{f_{n},x_{n}}$, and
assume that $y,z\in[x]{N}$ are almost disjoint and $f_{n}(y)=f_{n}(z)$. Then
$y,z\in[s_{n}\cup x_{n}]{N}$, and hence $f_{n}(y)\in C_{f_{n},x_{n}}\subseteq
C$, by the third property of the induction. ∎

Acknowledgments. We would like to thank Jan Grebík, Alexander Kechris, Adrian
Mathias, and Stevo Todorčević for valuable comments and suggestions.

## References

  * [1] V. Kanovei, M. Sabok, and J. Zapletal.  Canonical Ramsey theory on Polish spaces, volume 202 of Cambridge Tracts in Mathematics.  Cambridge University Press, Cambridge, 2013.
  * [2] A. S. Kechris and A. Louveau.  The classification of hypersmooth Borel equivalence relations.  Journal of the American Mathematical Society, 10(1):215–242, 1997\.
  * [3] A. S. Kechris, S. Solecki, and S. Todorčević.  Borel chromatic numbers.  Adv. Math., 141(1):1–44, 1999.
  * [4] A. R. D. Mathias.  Happy families.  Ann. Math. Logic, 12(1):59–111, 1977.
  * [5] H. J. Prömel and B. Voigt.  Canonical forms of Borel-measurable mappings $\Delta\colon\ [\omega]^{\omega}\to{\bf R}$.  J. Combin. Theory Ser. A, 40(2):409–417, 1985.
  * [6] J. Silver.  Every analytic set is Ramsey.  The Journal of Symbolic Logic, 35(1):60–64, 1970.
  * [7] R. I. Soare.  Sets with no subset of higher degree.  J. Symbolic Logic, 34:53–56, 1969.
  * [8] S. Todorčević and Z. Vidnyánszky.  A complexity problem for Borel graphs.  Invent. Math., to appear, 2021.


# Data-Driven Outage Restoration Time Prediction via Transfer Learning with
Cluster Ensembles

Dingwei Wang, Yuxuan Yuan, Rui Cheng, and Zhaoyu Wang This work was supported
in part by the National Science Foundation under EPCN 2042314 and CMMI
1745451, and in part by Advanced Grid Modeling Program at the U.S. Department
of Energy Office of Electricity under Grant DE-OE0000875. (Corresponding
author: Zhaoyu Wang) D. Wang, Y. Yuan, R. Cheng, and Z. Wang are with the
Department of Electrical and Computer Engineering, Iowa State University,
Ames, IA 50011 USA (e-mail<EMAIL_ADDRESS>wzy@iastate.edu).

###### Abstract

This paper develops a data-driven approach to accurately predict the
restoration time of outages under different scales and factors. To achieve the
goal, the proposed method consists of three stages. First, given the
unprecedented amount of data collected by utilities, a sparse dictionary-based
ensemble spectral clustering (SDESC) method is proposed to decompose
historical outage datasets, which enjoys good computational efficiency and
scalability. Specifically, each outage sample is represented by a linear
combination of a small number of selected dictionary samples using a density-
based method. Then, the dictionary-based representation is utilized to perform
the spectral analysis to group the data samples with similar features into the
same subsets. In the second stage, a knowledge-transfer-added restoration time
prediction model is trained for each subset by combining weather information
and outage-related features. The transfer learning technology is introduced
with the aim of dealing with the underestimation problem caused by data
imbalance in different subsets, thus improving the model performance.
Furthermore, to connect unseen outages with the learned outage subsets, a
t-distributed stochastic neighbor embedding-based strategy is applied. The
proposed method fully builds on and is also tested on a large real-world
outage dataset from a utility provider with a time span of six consecutive
years. The numerical results validate that our method has high prediction
accuracy while showing good stability against real-world data limitations.

###### Index Terms:

Distribution network, sparse dictionary-based ensemble spectral clustering,
outage restoration time prediction, transfer learning.

##  I Introduction

Recent Texas blackout has demonstrated the danger and inconveniences people
face during a severe power outage event. In general, power outages have
significant impacts on production, transportation, communication, and health
supply service, resulting in significant economic losses. When an outage
occurs, utilities need to make a series of decisions quickly, including
detecting and locating the fault, estimating costs and the number of customers
affected, predicting outage restoration time, planning repair strategies and
dispatching crews [1]. From the customer’s perspective, the most important and
concerned information is timely and accurate outage recovery time prediction,
which will greatly help them plan for subsequent arrangements in advance.
However, it is challenging to estimate outage recovery time as power outages
are typically unplanned with limited information. Moreover, the causes of
power outages involve a wide variety of factors, e.g., bad weather, human
behaviors, and equipment failures [2, 3, 4, 5]. To improve customer
satisfaction, accurate prediction of outage recovery time is becoming a top
priority for utilities.

In recent years, research studies have focused on interring the quantity and
duration of outages by using various approaches and data sources, which can be
broadly classified into two groups based on prediction targets: Group I -
Prediction of outage duration. The authors in [6] analyzed restoration
duration of outages using statistical and quantitative methods with several
factors including time of the outage, consequences, and environmental
conditions. In [7], an accelerated failure time model using severe weather
records were developed to estimate duration of outages. In [8], the authors
summarized six years’ historical outage data and proposed a deep neural
network to predict repair and restoration time with respect to severe weather
events. In [9], the authors utilized radar observation data and further
proposed a generalized weather condition dependent failure rate model, based
on the Bayesian prediction algorithm, to provide an prediction of outage
numbers. Group II - Prediction of outage numbers. In [10], the authors
performed a Poisson regression model to predict average number of outages over
a period under normal weather conditions. The authors in [11] estimated
distribution system outages numbers caused by wind and lighting using an
artificial neural network. In [12], a graph neural network is proposed to
predict power outages numbers by utilizing weather variables. A summary of the
literature is shown in Table I.

TABLE I: LITERATURE REVIEW ON OUTAGE PREDICTION IN DISTRIBUTION SYSTEMS
---

Even though the previous works demonstrate valuable results, some research
challenges remain outstanding in this area. First, most studies in group I are
generally based on the assumption that each outage recovery can be treated as
an isolated process. In other words, with respect to multiple outages that
occur in the same systems, the existing methods estimate the restoration time
separately without consideration of the correlation among multiple coinciding
outages. However, in actual grids, while maintenance crews are repairing an
outage, the repair of another outage occurring in the neighboring area may be
delayed due to crew shortages. Thus, such an assumption in Group I reduces the
accuracy of these prediction models. Second, some studies in group II trained
a global model for the whole historical outage dataset, which ignores the
uncertainty caused by the heterogeneity of outage events under different
scales and factors, thus reducing prediction performance for unseen outages.
Also, given the paucity of real outage reports, most existing works rely on
the weather information to develop their models and assume the weather
conditions across each small area are homogeneous. Nevertheless, while severe
weather is one of the leading causes of power outages, other factors, such as
equipment failure and human factors, should not be ignored.

To this end, we propose a novel data-driven method to predict outage
restoration time using transfer learning with cluster ensembles. The flowchart
of our proposed method is depicted in Fig.1. Compared with the existing
studies, the contributions of our work focus on: 1) To investigate the
interaction of simultaneous outage events during a period, we extract the
statistics from real-world outage reports and calculate the cumulative number
of coinciding outages and affected customers. The temporal information in
outage data, such as the start and end time and restoration time, is utilized
to summarize the real-time numbers of outages and customers affected in a time
span. This information can be explored to approximate the system stress for
prediction model developments. 2) Unlike previous methods that train a global
prediction model, the proposed method estimates the restoration time in a
cluster-wise manner to deal with the uncertainty caused by the heterogeneity
of outage events. Specifically, a sparse dictionary-based ensemble spectral
clustering (SDESC) method is developed to efficiently group the historical
outage events. For each data subset, a prediction model is trained to
construct an end-to-end mapping between the outage-related information and the
restoration time by leveraging deep learning techniques. 3) Based on our
investigation of real-world outage datasets, there may be huge gaps between
the amount of data available for different patterns and scales of outages.
Therefore, a transfer learning strategy is integrated with the proposed
prediction framework to avoid the overfitting risk caused by the data scarcity
of the specific outage patterns. 4) The proposed approach leverages not only
high-level weather information but also exploits outage-related features
collected by our utility partner, which are time and location of outages,
number of customers interrupted, cause code, and duration of
repair/restoration process. The proposed prediction methodology has been
tested and verified using real outage data.

The rest of this paper is organized as follows: Section II introduces the
problem definition and describes the available outage dataset in detail.
Section III proposes the sparse dictionary-based ensemble spectral clustering
method. In Section IV, the transfer learning-added outage restoration time
prediction model is presented. The numerical results are analyzed in Section
V. Section VI concludes the paper.

Figure 1: The flowchart of the proposed method.

##  II Problem Definition $\&$ Outage Data Description

###  II-A Problem Definition

When an outage occurs, one of the most common questions that customers may ask
is: How long will it take to restore the power[6]? If utilities can answer
this question at an early stage, customers can plan ahead and accordingly to
avoid inconvenience caused by power outages. In practice, outage restoration
time is defined as the time from the start of the outage to the service is
fully recovered to the customers [8]. In actual grids, one common solution is
to formulate a mathematical relationship between the restoration time and the
number of interrupted customers [6, 7, 9]. Such a solution embodies a set of
assumptions, such as the pre-define statistical models with fixed parameters
(e.g., Poisson distribution). However, the distribution of outage restoration
time may not follow the pre-defined pattern; meanwhile, some variables and
features cannot be considered in the statistical models due to the curse of
dimensionality, which reduces the accuracy of the prediction. Hence, machine
learning-based methods are receiving increasing attention due to the
unprecedented amount of data collected by utilities. Basically, the learning-
based solution is based solely on using historical outage data without an
assumption of data distributions to develop a supervised prediction model.

###  II-B Available Outage Dataset

The outage data under study includes over 16,000 records over a six-year
period in New York State. Fig. 2 describes the structure of the available
outage dataset. The original information on each outage record includes: start
and end time of the outage accurate to seconds, number of customers
interrupted, repair and restoration time accurate to seconds, cause code,
location, and distribution network circuit number. Specifically, the start and
end time of the outage events are reported by fuse cards that record the time
at which an outage starts and ends according to the loss of power. The cause
information is summarized into two types: Cause key \- There are 63 causes, of
which 5% of the records are weather-related, another 14% are animal-related,
and the rest are mainly due to component malfunctions, tree limbs, and debris.
The top two causes of all outage events are tree limbs near the clearance zone
of equipment and squirrels. The top weather-related causes are precipitation,
wind, and lightning strike. Equipment cause key \- The outages are caused by
equipment failure. The top equipment-related causes are system failure,
conductor disconnection, and transformer malfunction. These two types of cause
information are recorded in each outage and represented by a digital code.

Figure 2: The description of the outage dataset.

In this work, data preprocessing includes two steps: 1) Missing and bad data
cleaning \- Given equipment failures or human mistakes, missing and bad data
in historical outage datasets are typically unavoidable and can lead to
misclassification, which negatively affects the performance of data-driven
methods. Hence, the available dataset is initially processed to clean missing
and bad outage samples. Data samples with empty entries are removed first.
Then, following the engineering intuition, data samples with logically
incorrect entries (e.g., the restoration time is greater than total outage
time) and grossly erroneous values (e.g., the restoration time is extremely
illogically high) are removed. 2) Outage-related features investigation \-
Leveraging cross-domain insights from public weather data and the geographic
information of systems, the raw dataset is explored by adding hourly
temperature, precipitation, and wind speed. These data are collected from the
National Oceanic and Atmospheric Administration (NOAA) [13, 14]. The hourly
data from the NOAA is aligned with each outage sample based on the start time
of each outage. Given that severe weather events play a crucial role in outage
restoration time prediction, the weather condition of each outage record is
also marked as a discrete code, consisting of normal conditions, snowstorm,
lightning strike, high-speed wind, and flood [1]. Other features we have added
are cumulative number of coinciding outages and number of customers affected.
Specifically, in this work, the cumulative number of coinciding outages is the
number of outages presented at a certain period that has not yet been
resolved. This number varies over time while the outages occur and are
restored. When this number remains near zero, it indicates that the system is
in normal condition prior to outages, or that outages happened infrequently
and are resolved quickly. Conversely, under certain stressed conditions, this
number can be relatively high, indicating that numbers of outages have stacked
and affected the restoration time. For example, on December 10th, 2014, the
cumulative number of coinciding outage events was over 100, and the average
outage restoration time was above 300 minutes. In contrast, the cumulative
number of coinciding outage events is relatively low on April 15th, 2015, the
average outage restoration time is below 60 minutes.

Fig. 3 demonstrates an example for calculating the cumulative number of
coinciding outages. Each dashed line on the graph is a timestamp that is
recorded at each start and end of each outage. By comparing each two adjacent
dashed lines, a specific time period can be defined to explore the cumulative
number of coinciding outages by counting the numbers of outages. Following
this process, the cumulative number of coinciding outages for each period is
calculated by sorting the timestamps by their orders of occurrence:

$\displaystyle C_{outages}={C_{o}^{t_{i}}}-{C_{r}^{t_{i}}}$ (1)

where $C_{o}^{t_{i}}$ is the cumulative total outages at time $t_{i}$,
$C_{r}^{t_{i}}$ is the cumulative total restorations at time $t_{i}$, and
$C_{outages}$ is the number of simultaneous outages at time $t_{i}$. The
cumulative number of coinciding outages is used to define the stress of the
system and can provide additional dimension information for outage grouping,
as well as enhance the variability of the metric. Similar to the above
definition and (1), the cumulative number of customers interrupted can be
calculated by replacing the number of coinciding outages with the number of
customers.

##  III Historical Outage Data Discovery using SDESC

Nowadays, utilities are constantly attempting to collect as much information
as possible on power outages. However, the vast majority of outages in
distribution systems are small-scale and medium-scale; in contrast, large-
scale outages are still rare, thus leading to a data imbalance problem111The
data imbalance problem refers to an unequal distribution of classes in the
training dataset. When the dataset is imbalanced, the trained model typically
fails to capture the hidden features of minority groups. Thus, the performance
of a supervised model may suffer from the fact that the distribution of the
target variable is skewed. [15]. In this case, it could result in overfitting
problems when the raw outage data is used to train a global prediction model.

Figure 3: Exemplary of the cumulative number of coinciding outages.

To address the challenge posed by the real-world imbalanced outage dataset, a
novel unsupervised method, known as sparse dictionary-based ensemble spectral
clustering (SDESC), is leveraged to distinguish the hidden outage features and
partition the historical dataset into distinct subsets. The proposed method
follows the line of unsupervised research utilizing the spectral analysis to
discover the hideen features. Furthermore, the sparse coding technique is
adapted to decrease the complexity of outage event-based adjacency matrix
construction and eigen-decomposition, thus greatly reducing the cost of
practical implementation [16].

Regarding notations, let ${\bm{O}}=[{\bm{O}}_{1},\bm{O}_{2},...,\bm{O}_{m}]$
represents the historical outage dataset, where $m$ is the total number of the
outage events, $\bm{O}_{i}\in\mathbb{R}^{n\times 1}$ represents the outage-
related information in the $i$-th outage event including $n$ features. And let
${o}_{ij}$ denotes the $i$-th row and $j$-th column entry in $\bm{O}$. In
actual grids, given the accumulation of historical outage data over many
years, $m$ is a large real number. Sparse coding is utilized to find a sparse
representation of $\bm{O}$ that consists of a dictionary ${\bf
D}\in\mathbb{R}^{m\times p}$ and a representation ${\bf
R}\in\mathbb{R}^{p\times n}$ [16]. Specifically, each column of $\bf D$
contains the features of the outage samples. Each column of $\bf D$ represents
the $p$-dimensional (i.e., $p\ll m$) representation with respect to the raw
data samples in $\bf R$. To minimize the approximation error, this process is
regulated as a optimization problem using the Frobenius norm:

$\displaystyle\underset{{\bf D},{\bf R}}{{\rm minimize}}\hskip 5.69054pt$
$\displaystyle||{\bm{O}}^{T}-{\bf D}{\bf R}||_{F}^{2}$ (2a) $\displaystyle{\rm
subject}\,{\rm to}\hskip 5.69054pt$ $\displaystyle||\bf
D_{i}||_{F}^{2}<=C,\forall i=1,...,p.$ (2b)

Obviously, solving the above optimization problem is NP-hard [17]. In this
work, unlike the existing solutions that compute dictionary and representation
iteratively (i.e., method of optimal directions, stochastic gradient descent,
and least absolute shrinkage and selection operator (LASSO)), we first obtain
$\bf D$ by finding the dictionaries of $\bm{O}$ and then solve (2) as a
sparsity constraint linear regression problem by using Nadaraya-Watson kernel
regression. To achieve this, a cluster ensemble framework is introduced to
combine various clustering algorithms [18]. Specifically, a density-based
spatial clustering of applications with noise method is first utilized to
cluster all the data points and then use the cluster centers as the
dictionaries, which is tabulated as Algorithm 1 [19]. Two user-defined
hyperparameters, a threshold for the minimum number of neighbors, $\gamma$,
and the radius, $\xi$, are utilized to perform a minimum density level
estimation. $\bm{O}_{i}$ with more than $\gamma$ neighbors within $\xi$
distance are considered to be a centroid. All neighbors within the $\xi$
radius of the centroid are considered to be part of the same group as this
centroid. This method is capable of finding clusters with arbitrary shapes and
sizes and shows robustness and practicality because it does not require _a
priori_ specification on the number of clusters. By fixing $\bf D$, the entry
of $\bf R$ can be calculated using the following equation:

$r_{ij}=\frac{K({\bm{O}_{i}},{\bf D_{j}})}{\sum_{j^{\prime}\in{\bf
D}}K({\bm{O}_{i}},{\bf D_{j}})}$ (3)

where, $K(\cdot,\cdot)$ is a per-defined kernel function.

After applying the sparse coding, the representation matrix $\bf Z$ can be
represented as an undirected similarity graph, $\bf G=(Z,E)$, where $\bf E$ is
a set of edge connecting different vertices. The undirected graph $\bf G$ is
represented by its adjacency matrix
$W=(\mathrm{w}_{i,j})_{\\{}i,j=1,...,m\\}$, where $\mathrm{w}_{i,j}>0$
indicates the similarity between two selected outage samples, $\bm{O}_{i}$ and
$\bm{O}_{j}$. $W_{i,j}$ = 0 indicating that the vertices $\bf Z_{i}$ and $\bf
Z_{j}$ are not connected. We have adopted the Gaussian kernel function to
build the adjacency matrix $W$ as follows:

$W_{i,j}=exp\left(\frac{-||\bf Z_{i}-Z_{j}||^{2}}{\alpha^{2}}\right)$ (4)

where $\alpha$ is a scaling parameter indicating how fast the weight decreases
with the distance between the two vertices $\bf Z_{i}$ and $\bf Z_{j}$. To
avoid the error caused by manual parameter selection, a localized scaling
parameter $\alpha_{i}$ is calculated for each vertex, which allows self-tuning
of the point-to-point distances based on the local distance of the neighbor of
$\bf Z_{i}$ [20]:

$\alpha_{i}=||\bf Z_{i}-Z_{\beta}||$ (5)

where $\bf Z_{\beta}$ is the $\beta$’th neighbor of $\bf Z_{i}$. Then, the
weight equation (4) can be reformulated as follows:

$W_{i,j}=exp\left(\frac{-||\bf
Z_{i}-Z_{j}||^{2}}{\alpha_{i}\alpha_{j}}\right).$ (6)

By defining a couple of vertices and weight matrix $W$, the outage data
grouping is converted to a graph partitioning problem. The objective function
of the graph partitioning is to maximize both the dissimilarity between the
disparate groups and the total similarity within each group:

$S({\bf G})=\displaystyle\min_{\bf
A_{1},A_{2},...,A_{\theta}}\sum_{i=1}^{\theta}\frac{s(\bf A_{i},Z\setminus
A_{i})}{d(\bf A_{i})}$ (7)

where $\theta$ is the number of vertices, $\bf A_{i}$ is a group of vertices
in $\bf Z$, $\bf(Z\setminus A_{i})$ is the nodes of set $\bf Z$ that are not
in $\bf A_{i}$, $s(\bf A_{i},Z\setminus A_{i})$ is the sum of the weights of
vertices in $\bf A_{i}$. Then, the Laplacian matrix is formulated based on the
weight matrix $W$:

$L={\bf D}^{-\frac{1}{2}}W{\bf D}^{-\frac{1}{2}}$ (8)

where $\bf D$ is a diagonal matrix which the $(i,i)$’th element represents the
sum of $W$’s corresponding row. When solving the graph partition problem,
according to the Rayleigh-Ritz Theorem, the solution is acquired by using $k$
smallest eigenvectors of the Laplacian matrix, which guarantees an approximate
value of the optimal cut [21, 22]. The value of $k$ can be determined by
various clustering evaluation metrics, such as the Silhouette coefficient,
Dunn’s Index, and Davies-Bouldin validation index (DBI). In this work, to set
the optimal $k$, we adopt the DBI, which purposes to minimize the overlap of
different groups and maximize the conformance within each group. When we
modify the $k$ value for finding the smallest eigenvalues of the Laplacian
matrix, the corresponding DBI value is recorded for each $k$. The optimal
value of $k$ is determined when the DBI is minimized [23]. When the value of
$k$ is assigned, a new matrix ${\bf R}\in\mathbb{R}^{n\times k}$ is built
based on the $k$ smallest eigenvalues of the $L$ matrix. Based on the
properties of the graph Laplacians, the data point $\bf Z_{i}$ is
reconstructed using the $i$’th row of the matrix $\bf{R}$, which enhances the
cluster-properties of the data [20]. After the data reconstruction, any
clustering methods can be used to easily obtain the results. In this work, we
used $k$-means algorithm to obtain the final solutions from matrix $\bf{R}$.

Algorithm 1 Dictionary Selection in SDESC

Initialization: Initialize $i\leftarrow 1$, $\gamma$, $\xi$

repeat

[S1]: Select the $i$th row of $\bm{O}$.

repeat

[S2]: Pick $\bm{O}_{i}$ and retrieve all direct density-reachable points in
$\bm{O}$ using $\xi$.

[S3]: Based on $\gamma$, if $\bm{O}_{i}$ is a core point, a cluster is formed;
otherwise, assign $\bm{O}_{i}$ to noise

[S4]: Update $i\leftarrow i+1$.

until $i=n$

The proposed SDESC algorithm has three unique advantages over the conventional
spectral clustering (SC) method in this task: 1) The enhanced cluster-
properties of the reconstructed dataset reduce the sensitivity of the
clustering process to bad outage records that are unavoidable in real-world
applications. 2) The proposed method introduces the dictionary-based weight
matrix of the dataset rather than computing the high-dimensional profiles of
all available outage data directly. Such a strategy can significantly reduce
the complexities of computing the adjacency matrix and graph Laplacian matrix
from $O(m^{2})$ and $O(m^{3})$ to $O(pm)$ and $O(p^{3}+p^{2}m)$, which is
beneficial in the big data age. 3) The graph partitioning problem could be
settled without making any assumptions on the data distribution. This step
enhances the robustness of the clustering method, which leads to better
performance for complicated outage data structures [20].

##  IV Outage Restoration Time Prediction

Upon the outage data partitioning results, each outage subset is first
assigned with an artificial neural network (ANN) to estimate the outage
restoration time. As discussed in Section I and Section II-B, there may be
huge gaps between the amount of data available for different patterns and
scales of outage events. However, there are always internal relationships
between different outage event patterns. To this end, a transfer-learning-
based method is then employed to transfer the learned knowledge from one
prediction model to enhance the performance of the rest models. To help the
reader understand the proposed model, we first briefly revisit the concept and
properties of ANN, then describe the transfer learning strategy in detail.

###  IV-A Artificial Neural Network

An ANN is constructed with outage-related features as input vector $\bm{O}$,
multiple hidden layers, and an output layer with single output whose value can
be treated as the sum of the weighted non-linear terms $\bm{O}^{\prime}$:

${\bm{O}^{\prime}}=\sum_{j=1}^{h}(T_{ju}*\sigma(y_{j}))$ (9)

where $h$ is the number of hidden layers, $T_{ju}$ is the weight factor
between hidden nodes and output node, $\sigma(y_{j})$ is a sigmoidal
activation function, which is written as:

$\sigma(y_{j})=\frac{1}{1+exp(-y_{j})}.$ (10)

Here, $y_{j}$ is the input to the $j$-th hidden node, which is defined as:

$y_{j}=\sum_{i=1}^{m}T_{ij}(o_{i})+b_{i}$ (11)

where $m$ is the total number of input nodes, $T_{ij}$ is the weights factor
between input nodes and hidden node, $o_{i}$ is the input to the $i$-th input
node, and $b_{i}$ is the bias to the $i$-th input node. Then the least square
algorithm is applied to train ANN-based regression models to minimized the
total estimation error:

$\min\varepsilon=\frac{1}{2}\sum_{i=1}^{m}\left({\bm{O}}(i)-{\bm{O}^{\prime}}(i)\right)^{2}.$
(12)

In this work, the Levenberg-Marquardt (LM) backpropagation method is utilized
to update the weights and threshold parameters [24]. The LM method is derived
from Newton’s method to minimize sum-of-squares error functions [25]. It can
automatically adjust the learning rate in the direction of the gradient using
the Hessian matrix. Compared to back propagation methods with a constant
learning rate, the LM method significantly boosts the training speed [26]. To
calibrate the parameters of ANN, the optimal set of hyper-parameter is
determined by the grid search method [27].

###  IV-B Transfer Learning-added Outage Restoration Time Prediction Model

When the training targets are multiple related tasks (i.e., restoration time
prediction for outages under different scales and factors), conventional
machine learning-based methods need to train multiple models from scratch,
thus requiring a large and comprehensive dataset. Such a requirement renders
their practical implementation costly. In contrast, transfer learning-based
models greatly reduce the amount of data required for training by leveraging
prior knowledge gained from previous training tasks [28]. Therefore, a
transfer learning strategy is adopted to discover domain-invariant intrinsic
outage features and structures under different but related domains,
establishing the re-utilization of data information across domains.

In this work, learning tasks are defined as the training assignments of each
outage subset, and the source task is defined as the pre-learned prediction
model. To determine the optimal initial source task and assess the
similarities between the source task and learning tasks, a validation dataset
is randomly selected from each subset. The optimal source task is determined
by selecting the subset with the highest average similarity with other
subsets. Once the source task is settled, a knowledge matrix related to the
source task is first obtained during the training process, which is then
exploited as the initial knowledge for a new learning task. Such a process can
be formulated as:

${\bm{T}}_{i}=\sum\omega{\bm{T}}^{*}_{i},\hskip 11.38109pti=1,2,...,n$ (13)

where ${\bm{T}}_{i}$ is the initial knowledge matrix of the $i$-th variable in
a learning task; ${\bm{T}}^{*}_{i}$ denotes the learned knowledge matrix of
the $i$-th parameter in the source task; $\omega$ represents the similarity
between the learning task and the source task; $n$ is the number of data
features.

Figure 4: Exemplary of the transfer learning process.

This transfer learning process is depicted in Fig. 4. In detail, after the
source task and learning tasks are distinguished by a similarity evaluation of
cluster-wised outage subsets, the transfer learning process gathers the
outage-related features and the output (i.e., actual restoration time) in the
pre-trained model, and stores them as a knowledge matrix. Similarly, each
learning task, which is an untrained model in the queue, generates a learning
matrix containing outage features, the corresponding actual restoration time,
and an empty pending entry that represents the predicted restoration time for
each outage. According to (13), by exploiting the similarity $\omega$ between
the learning task and the source task, which is now the similarity between the
knowledge matrix and learning matrix, the learning parameters can be updated
for training a new prediction model. After updating the parameters of the
learning matrix, the predicted restoration time can be obtained by directly
filling the pending entries in the matrix for each outage. When the first
prediction task is completed, the learned model can be utilized in a recursive
manner when dealing with a new learning task [29]. For example, the training
assignments for cluster-wised subsets are signed as task 1, 2 and 3. Task 2 is
learned by exploiting task 1 as a source task, then task 2 can be used as the
source task for training task 3.

Compared to the conventional machine learning-based method, the proposed
transfer learning-added outage restoration time prediction method has two
unique advantages: 1) the transfer learning strategy with cluster-wised
datasets can greatly reduce the overfitting risk caused by the data scarcity
of the specific outage prediction patterns and distributions. This can be
confirmed using the numerical results. 2) The transfer learning strategy can
introduce better robustness for imperfect data. In actual grids, some outage-
related features may be incorrectly collected or recorded, which is difficult
to resolve by applying data imputation methods. However, in our method, the
similarity parameter $\omega$ is introduced to identify such data. The
incorrect data stored in the learning matrix does not have justified
similarity with data measurements in the source matrix. Therefore, such data
can be easily removed by sorting the similarities for each outage data from
the learning task. As the learning task becomes a new source task, incorrect
data in the learning task is eventually reduced to a small number by repeating
this process.

###  IV-C Unseen Outage Classification

To identify and allocate the corresponding outage pattern and related
prediction model to unseen outage, a t-distributed stochastic neighbor
embedding (t-SNE) method is utilized. By optimizing the conditional
probability between original data and analogue data, the t-SNE can convert
high-dimensional outage data into low-dimensional representations. Data with
higher similarity in high-dimensional space is closer to each other after
being embedded in low-dimensional space, thus leading to better classification
performance [30, 31]. Here, the conditional probability between any two outage
samples ${\bm{O}}_{i}$ and ${\bm{O}}_{j}$ in high-dimensional space can be
formulated as:

$P_{A|B}(\bm{O}_{i}|\bm{O}_{j})=\frac{exp\left(\frac{-||{\bm{O}}_{j}-{\bm{O}}_{i}||^{2}}{2{\delta}_{j}}\right)}{\sum_{\kappa=1,\kappa\neq
j}^{m}exp\left(\frac{-||{\bm{O}}_{j}-{\bm{O}}_{\kappa}||^{2}}{2{\delta}_{j}}\right)}$
(14)
$P_{A|B}(\bm{O}_{j}|\bm{O}_{i})=\frac{exp\left(\frac{-||{\bm{O}}_{i}-{\bm{O}}_{j}||^{2}}{2{\delta}_{i}}\right)}{\sum_{\kappa=1,\kappa\neq
i}^{m}exp\left(\frac{-||{\bm{O}}_{i}-{\bm{O}}_{\kappa}||^{2}}{2{\delta}_{i}}\right)}$
(15)

where $\kappa$ is the number of domain points, ${\delta}_{i}$ is the vector
variance of the Gaussian function centered on the data ${\bm{O}}_{i}$. The
joint probability of ${\bm{O}}_{i}$ and ${\bm{O}}_{j}$,
$P(A=\bm{O}_{i},B=\bm{O}_{j})$, within a Gaussian space is:

$P_{A,B}(\bm{O}_{i},\bm{O}_{j})=\frac{P_{A|B}(\bm{O}_{i}|\bm{O}_{j})+P_{A|B}(\bm{O}_{j}|\bm{O}_{i})}{2m}.$
(16)

In a low-dimensional space, the t distribution is applied with one degree of
freedom. The joint distribution of two simulated data $\bm{Y}_{i}$ and
$\bm{Y}_{j}$ is calculated as follows:

$P_{A,B}(\bm{Y}_{i},\bm{Y}_{j})=\frac{\left(1+||\bm{Y}_{i}-\bm{Y}_{j}||^{2}\right)^{-1}}{\sum_{\kappa=1,\kappa\neq
l}^{m}\left(1+||\bm{Y}_{\kappa}-\bm{Y}_{l}||^{2}\right)^{-1}}.$ (17)

The Kullback Leibler (KL) divergence is utilized to quantify the similarity
between $P_{A,B}(\bm{Y}_{i},\bm{Y}_{j})$ and $P_{A,B}(\bm{O}_{i},\bm{O}_{j})$:

${\bm{C}}=\sum_{i=1}^{m}\sum_{j=1}^{m}P_{A,B}(\bm{O}_{i},\bm{O}_{j})\log_{2}\frac{P_{A,B}(\bm{O}_{i},\bm{O}_{j})}{P_{A,B}(\bm{Y}_{i},\bm{Y}_{j})}.$
(18)

The optimal low-dimensional data,
${{\hat{\bm{Y}}}_{1},\hat{\bm{Y}}_{2},...,\hat{\bm{Y}}_{m}}$ is obtained by
minimizing the KL divergence using the gradient descent method, which is
denoted as:

$\frac{\delta{\bm{C}}}{\delta\bm{Y}_{i}}=4\sum_{j=1}^{m}\left({P_{ij}}-{q_{ij}}\right)\left(\bm{Y}_{i}-\bm{Y}_{j}\right)\left(1+||\bm{Y}_{i}-\bm{Y}_{j}||^{2}\right)^{-1}.$
(19)

When an outage occurs, the high-dimensional data is first converted into the
two-dimensional map using the t-SNE method. Then, the distances between the
edges of each subset with this point are calculated to quantify the similarity
between the unseen outage and the learned subsets. Based on the distance
values, the most probable class is chosen as the correct underlying subset for
the unseen outage.

##  V Numerical Results

This section explores the practical effectiveness of the proposed outage
restoration time prediction method. A real-world dataset with 16,000 outages
events is utilized in this case study, including six years of data collected
by a utility in New York State. After data preprocessing, the whole dataset is
randomly divided into three parts for training, testing, and validation by
70%, 15%, and 15% of the total data, respectively.

###  V-A SDESC Algorithm Performance

Fig. 5 presents the data distribution of the number of customer interruptions
versus outage restoration time. As described in this figure, the number of
customers interrupted has a clear impact on restoration time. The rationale
behind this is that utilities typically prioritize dealing with large-scale
outages; therefore, outage restoration time tends to be shorter when the
number of affected customers is higher. In contrast, estimating restoration
time for small-scale outages is more challenging, as they are more likely to
be affected by a variety of factors. This can also be confirmed using real-
world data, as shown in Fig. 5. Therefore, it is necessary to implement the
proposed SDESC method to distinguish the outage groups that are constrained by
various features.

Figure 5: Dictionary-based ensemble spectral clustering of the outage dataset.

Basically, the SDESC calibration is a trial and error process using a specific
cluster evaluation metric. In this work, the optimal number of subsets, $k$,
is assigned as $4$ based on the minimum DBI value. The grouping results with
the corresponding $k$ value are marked in Fig. 5. Specifically, each color
represents a subset of the outage data, namely $C_{1}$, $C_{2}$, $C_{3}$, and
$C_{4}$. Table II demonstrates the statistics in the grouping results,
including the number of data samples in each subset, the average number of
customers interrupted (i.e., Avg. CI), and the average restoration time in
minutes (i.e., Avg. RT). As shown in table, $\\{C_{1},C_{2},C_{3},C_{4}\\}$
consist of $\\{2379,5302,2884,5872\\}$ outage data samples, respectively. Such
results promise the data imbalance problem: subset $C_{2}$ and $C_{4}$ have
twice as many data samples as $C_{1}$ and $C_{3}$, while the average recovery
time (i.e., 740.5 minutes) and the number of customers interrupted (i.e., 170)
of $C_{1}$ are significantly higher than for the other subsets. In our view,
$C_{1}$ refers to severe outages with a higher Avg. RT and Avg. CI, but
relatively infrequent. $C_{2}$ and $C_{4}$ represent intermediate and least
serious outages, which are twice as frequent as severe outages. $C_{4}$
represents a subset of minor outages, which occur frequently but can typically
be resolved in a timely manner. For the classification part, the t-SNE result
is shown in Fig. 6. The shortest distances between the edges of each subset
with each unseen outage are calculated to measure the similarity between the
unseen outage and the learned patterns. Based on the testing dataset (15% of
the total data), the classification error margin can achieve 5% when assigning
outage patterns to unseen outages.

TABLE II: CLUSTERING STATISTICS

Cluster |  Samples |  Avg. CI |  Avg. RT(min)
---|---|---|---
$C_{1}$ |  2379 |  170 |  740.5
$C_{2}$ |  5302 |  21 |  288.4
$C_{3}$ |  2884 |  16 |  144.5
$C_{4}$ |  5872 |  22 |  82.2

Figure 6: t-SNE plot of clustered data using the proposed SDESC method.

We have conducted a numerical comparison with an advanced K-means algorithm
[32] to show that the proposed SDESC method can offer a dramatic improvement
in outage data grouping. Fig. 7 shows the t-SNE plot of the result using the
advanced K-means algorithm. By using this state-of-the-art clustering method,
over 70% of the total data has fallen into a single cluster subset, $C_{1}$.
Such a result increases the overfitting risk caused by data insufficient in
other subsets. Moreover, it is clear that the data points in different subsets
of Fig. 7 are more difficult to be classified than in Fig. 6. This indicates
that the homogeneity of each subset obtained from the advanced K-means is much
lower than that of each subset obtained from the proposed method. Therefore,
when an unseen outage occurs, it is highly likely to misclassify, thus
resulting in a decrease in restoration time prediction accuracy.

Figure 7: t-SNE plot of clustered data using the advanced K-means method.

###  V-B Outage Restoration Time Prediction Performance Analysis

Figure 8: Comparison result between actual and predicted restoration time for
the source task ($C_{4}$).

When the outage dataset is separated using the SDESC method, the ANN with a
transfer learning embedded model is utilized to predict the outage restoration
time. In this paper, according to the performance of validation sets, we
select subset $C_{4}$ as the source task to initialize the transfer learning
strategy. To evaluate the prediction performance of the ANN, the mean absolute
percentage error (MAPE) is utilized in this paper, which is formulated as
follows:

$MAPE=\frac{100}{m}\sum_{i=1}^{m}\left|\frac{A_{i}-P_{i}}{A_{i}}\right|$ (20)

where $A_{i}$ is the actual data value, and $P_{i}$ is the predicted value,
their difference is divided by the actual data value. The absolute value in
this division is summed up for every predicted point in time and divided by
the number of data measurements $m$. In addition to MAPE, the percentage of
predicted restoration time that falls within the reasonable range from the
actual restoration time is also calculated to further evaluate the performance
of our method. Fig. 8 describes the comparison between the actual and
predicted restoration time for 25 randomly selected samples in $C_{4}$. After
predicting the restoration time of the test data, the predicted restoration
time range is 22.8 minutes, which is below the 30 minutes threshold. 3% of the
predicted time is more than 60 minutes of the actual repair time, and only one
particular outage showed that the predicted time is more than 90 minutes of
the actual repair time.

(a) Cluster 1 ($C_{1}$)

(b) Cluster 2 ($C_{2}$)

(c) Cluster 3 ($C_{3}$)

Figure 9: Comparison result between actual and predicted restoration time for
learning tasks.

The proposed method is utilized to train the prediction models for $C_{1}$,
$C_{2}$ and $C_{3}$ using the source task. The MAPE for $C_{1}$, $C_{2}$, and
$C_{3}$ is 23%, 24%, and 11.7%, respectively. The predicted restoration time
range for all three subsets is 48.8 minutes, while subset $C_{3}$ had an
outstanding prediction range of 21.9 minutes. Fig. 9 demonstrates the
comparison between the actual and predicted restoration time for 25 randomly
selected outages in $C_{1}$, $C_{2}$, and $C_{3}$. Note that the variance in
restoration time for each subset is 1300 seconds, 350 seconds, and 170
seconds. Despite the high variance of $C_{1}$, the prediction model still
performs decently. The prediction accuracy of $C_{1}$ is slightly lower than
that of $C_{2}$ and $C_{3}$. This result is reasonable because higher data
variance usually leads to a higher risk of overfitting and reduces the
accuracy of the prediction model.

###  V-C Method Comparison

####  V-C1 Proposed Model vs. Global Model

We have conducted a comprehensive comparison between the proposed cluster-
wised model with the previous restoration time prediction model[8]. Note that
the previous model follows a global training fashion and is developed using
all outage records without clustering. Where possible we attempted to tune
parameters for each algorithm to give a fair comparison. The MAPE improvement
compared to the global model for each of the subsets are 152.57%, 132.76%, and
393.78%, respectively, as shown in Fig. 10. This result indicates that our
SDESC method can substantially improve the prediction performance by reducing
the uncertainty of the real-world outage data compared to the global model.

Figure 10: Restoration time comparison between cluster-wised model and global
model. Figure 11: Prediction of restoration time with and w/o transfer
learning approach.

####  V-C2 Proposed Model vs. Conventional cluster-wise Learning-based Model

Another numerical comparison has been conducted between the proposed method
with the conventional cluster-wise-based method. This conventional method
trained independent neural networks for each cluster-wised subset. Such a
comparison can further demonstrate that our method can achieve good prediction
performance. Both methods are evaluated based on the same neural network
configurations to ensure a fair comparison. As is demonstrated in Fig. 11, for
the three different outage subsets $C_{1}$, $C_{2}$, and $C_{3}$, compared to
the conventional cluster-wise-based method, our transfer-learning-added model
has 52.98%, 9.59%, and 27.26% MAPE improvement, respectively. The results show
that the transfer learning strategy can meet the challenges posed by real-
world unbalanced outage datasets and greatly improve the accuracy of repair
time prediction.

##  VI Conclusion

This paper presents a novel data-driven approach to accurately predict outage
restoration time using transfer learning with cluster ensembles. In this
paper, six years of real-world outage dataset from our utility partner is
investigated for model development and validation. The proposed SDESC approach
utilizes the sparse coding technique and cluster ensemble mechanism to first
decompose the large-scale datasets, which has good computational efficiency
and scalability. Based on the learned outage patterns, the developed transfer-
learning-added model can not only accurately predict the outage restoration
time in each subset, but also addresses two fundamental challenges: 1) neglect
the uncertainty caused by the heterogeneity of outage events with different
scales and factors; 2) data imbalance problem in different data subsets. Based
on the available real-world utility data, the results show that the proposed
method has improved performance compared to existing methods and overcome
large-scale data challenges.

## References

  * [1] A. Jaech, B. Zhang, M. Ostendorf, and D. S. Kirschen, “Real-time prediction of the duration of distribution system outages,” _IEEE Trans. Power Syst._ , vol. 34, no. 1, pp. 773–781, July. 2018.
  * [2] Y. Zhou, A. Pahwa, and S. S. Yang, “Modeling weather-related failures of overhead distribution lines,” _IEEE Trans. Power Syst._ , vol. 21, no. 4, pp. 1683–1690, October. 2006.
  * [3] F. Yang, P. Watson, M. Koukoula, and E. N. Anagnostou, “Enhancing weather-related power outage prediction by event severity classification,” _IEEE Access_ , vol. 8, pp. 60 029–60 042, March. 2020.
  * [4] P. Kankanala, S. Das, and A. Pahwa, “Adaboost+: An ensemble learning approach for estimating weather-related outages in distribution systems,” _IEEE Trans. Power Syst._ , vol. 29, no. 1, pp. 359–367, January. 2014.
  * [5] M. S. Bashkari, A. Sami, and M. Rastegar, “Outage cause detection in power distribution systems based on data mining,” _IEEE Trans. Ind. Informat._ , vol. 17, no. 1, pp. 640–649, 2021.
  * [6] M.-Y. Chow, L. Taylor, and M.-S. Chow, “Time of outage restoration analysis in distribution systems,” _IEEE Trans. Power Del._ , vol. 11, no. 3, pp. 1652–1658, 1996.
  * [7] H. Liu, R. A. Davidson, and T. V. Apanasovich, “Statistical forecasting of electric power restoration times in hurricanes and ice storms,” _IEEE Trans. Power Syst._ , vol. 22, no. 4, pp. 2270–2279, 2007.
  * [8] A. Arif and Z. Wang, “Distribution network outage data analysis and repair time prediction using deep learning,” _2018 IEEE International Conference on Probabilistic Methods Applied to Power Systems (PMAPS)_ , pp. 1–6, June, 2018.
  * [9] M. Yue, T. Toto, M. P. Jensen, S. E. Giangrande, and R. Lofaro, “A bayesian approach-based outage prediction in electric utility systems using radar measurement data,” _IEEE Trans. Smart Grid_ , vol. 9, no. 6, pp. 6149–6159, November, 2018.
  * [10] A. Domijan Jr, R. Matavalam, A. Montenegro, W. Wilcox, Y. Joo, L. Delforn, J. Diaz, L. Davis, and J. Agostini, “Effects of norman weather conditions on interuptions in distribution systems,” _International Journal of Power & Energy Systems_, vol. 25, no. 1, pp. 54–61, 2005.
  * [11] P. Kankanala, A. Pahwa, and S. Das, “Estimation of overhead distribution system outages caused by wind and lightning using an artificial neural network,” in _International Conference on Power System Operation & Planning_, vol. 545, 2012.
  * [12] D. Owerko, F. Gama, and A. Ribeiro, “Predicting power outages using graph neural networks,” _2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP)_ , pp. 743–747, 2018.
  * [13] National Oceanic and Atmospheric Administration, “Severe weather,” 2021. [Online]. Available: https://www.ncei.noaa.gov/products/severe-weather,.
  * [14] ——, “Climate data online,” 2021. [Online]. Available: https://www.ncdc.noaa.gov/cdo-web/.
  * [15] L. Xu, M.-Y. Chow, and L. S. Taylor, “Power distribution fault cause identification with imbalanced data using the data mining-based fuzzy classification $e$-algorithm,” _IEEE Trans. Power Syst._ , vol. 22, no. 1, pp. 164–171, 2007.
  * [16] X. Chen and D. Cai, “Large scale spectral clustering with landmark-based representation,” in _Twenty-fifth AAAI Conference on Artificial Intelligence_ , August. 2011.
  * [17] D. S. Hochba, “Approximation algorithms for np-hard problems,” _ACM Sigact News_ , vol. 28, no. 2, pp. 40–52, 1997.
  * [18] J. Azimi and X. Fern, “Adaptive cluster ensemble selection,” in _Twenty-First International Joint Conference on Artificial Intelligence_ , 2009.
  * [19] J. Jang and H. Jiang, “Dbscan++: Towards fast and scalable density clustering,” _International Conference on Machine Learning_ , pp. 3019–3029, 2019.
  * [20] U. Luxburg, “A tutorial on spectral clustering,” _Statistics and Computing_ , vol. 17, no. 4, pp. 395–416, Mar. 2007.
  * [21] F. R. Chung and F. C. Graham, “Spectral graph theory,” _American Mathematical Soc._ , no. 92, 1997.
  * [22] C. C. Aggarwal and C. K. Reddy, “Data clustering,” _Algorithms and applications. Chapman &Hall/CRC Data mining and Knowledge Discovery series, Londra_, 2014.
  * [23] J. Bezdek and N. Pal, “Some new indexes of cluster validity,” _IEEE Trans. Syst., Man, Cybern. B. Cybern_ , vol. 28, no. 3, pp. 301–315, 1998.
  * [24] S. Sapna, A. Tamilarasi, M. P. Kumar _et al._ , “Backpropagation learning algorithm based on levenberg marquardt algorithm,” _Comp Sci Inform Technol (CS and IT)_ , vol. 2, pp. 393–398, 2012.
  * [25] C. Lv, Y. Xing, J. Zhang, X. Na, Y. Li, T. Liu, D. Cao, and F.-Y. Wang, “Levenberg–marquardt backpropagation training of multilayer neural networks for state estimation of a safety-critical cyber-physical system,” _IEEE Trans. Ind. Informat._ , vol. 14, no. 8, pp. 3436–3446, 2017.
  * [26] B. M. Wilamowski and H. Yu, “Improved computation for levenberg–marquardt training,” _IEEE Trans. Neural Netw._ , vol. 21, no. 6, pp. 930–937, 2010\.
  * [27] J. Bergstra and Y. Bengio, “Random search for hyper-parameter optimization,” _Journal of Machine Learning Research_ , vol. 13, pp. 281–305, Feb. 2012\.
  * [28] L. Torrey and J. Shavlik, “Transfer learning,” _Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods, and Techniques_ , pp. 242–264, 2010.
  * [29] F. Zhuang, Z. Qi, K. Duan, D. Xi, Y. Zhu, H. Zhu, H. Xiong, and Q. He, “A comprehensive survey on transfer learning,” _Proceedings of the IEEE_ , vol. 109, no. 1, pp. 43–76, 2021.
  * [30] A. C. Belkina, C. O. Ciccolella, R. Anno, R. Halpert, J. Spidlen, and J. E. Snyder-Cappione, “Automated optimized parameters for t-distributed stochastic neighbor embedding improve visualization and analysis of large datasets,” _Nature Communications_ , vol. 10, no. 1, pp. 1–12, 2019.
  * [31] X. Fang, S. Zhang, X. Su, B. Zhao, W. Xiao, Y. Yin, and F. Wang, “Blast furnace condition data clustering based on combination of t-distributed stochastic neighbor embedding and spectral clustering,” _2019 IEEE 15th International Conference on Control and Automation (ICCA)_ , pp. 1608–1613, 2019\.
  * [32] R. Yadav and A. Sharma, “Advanced methods to improve performance of k-means algorithm: A review,” _Global Journal of Computer Science and Technology_ , vol. 12, no. 9, pp. 47–52, 2012.


#  The use of the symmetric finite difference in the
local binary pattern (symmetric LBP)

Zeinab Sedaghatjoo 0.10.10.1 Corresponding author.
E-mail addresses:
<EMAIL_ADDRESS><EMAIL_ADDRESS>(Z. Sedaghatjoo)
<EMAIL_ADDRESS><EMAIL_ADDRESS>(H. Hosseinzadeh).  ,
Hossein Hosseinzadeh
Department of Mathematics, Persian Gulf University, Bushehr, Iran.

###### Abstract

The paper provides a mathematical view to the binary numbers presented in the
Local Binary Pattern (LBP) feature extraction process. Symmetric finite
difference is often applied in numerical analysis to enhance the accuracy of
approximations. Then, the paper investigates utilization of the symmetric
finite difference in the LBP formulation for face detection and facial
expression recognition. It introduces a novel approach that extends the
standard LBP, which typically employs eight directional derivatives, to
incorporate only four directional derivatives. This approach is named
symmetric LBP. The number of LBP features is reduced to 16 from 256 by the use
of the symmetric LBP. The study underscores the significance of the number of
directions considered in the new approach. Consequently, the results obtained
emphasize the importance of the research topic.
Keywords: local binary pattern, feature extraction, face detection, facial
expression recognition, symmetric finite difference.
MSC 2020: 68W01, 65A05, 65L12

##  1 Introduction

Local Binary Pattern (LBP) is a texture descriptor used in computer vision for
image classification. It was first introduced by Ojala et al. [1] and has
gained popularity due to its effectiveness in extracting texture features
while maintaining computational simplicity. The core concept of the LBP
involves comparing each pixel of an image with its neighbouring pixels to
encode the local texture information into binary patterns. In mathematical
sense, the comparison test can be interpreted as directional derivatives. Non
negative derivations conclude 1 and negative ones lead $0$ in this stage. The
resulting binary values obtained from the comparisons are concatenated
sequentially in a clockwise order, forming an 8-digit binary number for each
pixel. A histogram is computed over the entire pixels, capturing the frequency
of different LBPs. This histogram serves as a feature vector for the image.
Then, 256 LBPs are reduced to 16 or less features by the histogram. Since the
extracted features mainly describe the entire image, the image is divided into
several regions to capture more local features. This is achieved by deriving
histograms from the LBPs extracted from the regions and concatenating them. We
show in this paper that the number of LBPs can be reduced to 16 instead of 256
if one uses symmetric directional derivatives. In this case, there is no need
to use the histogram in the LBP. So, the computational cost of the LBP process
is reduced.

Variations of LBP have been developed to enhance its performance and address
specific challenges in different applications [2, 3, 4, 5]. Some notable
variations of the LBP are presented, such as: Uniform Local Binary Patterns
(ULBP), Rotation-Invariant Local Binary Patterns (RILBP), Local Ternary
Patterns (LTP), Multi-scale Local Binary Patterns (MLBP) and Completed Local
Binary Patterns (CLBP). A complete review of LBP developments is presented in
[6]. Experimental results presented in [7] show that LBP is significantly
enriched if more directional derivatives are applied in the formulations.
Additionally, reference [8] claimed that four directional derivatives can
extract texture patterns of an image as effectively as eight directional
derivatives. This suggests that the 8-bit binary numbers used in traditional
LBP can be replaced by 4-bit representations. This led the authors to further
investigate the role of directional derivatives and their approximation using
the symmetric finite difference. The findings confirm the claims made in
regarding the effectiveness of using four directional derivatives for texture
analysis if the directional derivatives are approximated by the symmetric
finite difference.

Then, in this work, a new approach, named symmetric LBP, is proposed. This
approach led to more accurate approximations of the directional derivatives in
the LBP. Furthermore, 4-bit binary numbers are found from this approach which
are as effective as the traditional 8-bit representations. This leads less
computational cost. The efficiency of the new 4-bit LBP descriptor are
verified through experiments on face detection and facial expression
recognition tasks. Forthcoming sections of the paper are designed as follows:

  * •

In Section 2, the LBP is described.

  * •

In Section 3, the directional derivatives of the LBP are studied and the
symmetric LBP is proposed there to enhance the standard LBP.

  * •

In Section 4, some experiment results are presented in face detection and
facial expression recognition.

  * •

Finally, the article is completed by a brief conclusion in Section 5.

##  2 Local Binary Pattern

LBP is a texture descriptor. It operates on images by labelling the pixels via
comparing their values with the values of their neighbours [2]. For applying
the LBP, an image is divided into some local regions and the LBP texture
descriptors are extracted from each region, successive. The descriptors are
then concatenated to form a global description of the image. The LBP
descriptor takes 3×3-pixel blocks as the basic unit, and the difference
between the central pixel and its adjacent 8 pixels is extracted as local
texture feature representation. It can be formulated as follows:

$S(p,c)=\left\\{\begin{array}[]{ll}1,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\hbox{if}~{}~{}g(p)\geq
g(c),\\\ \\\
0,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\hbox{if}~{}~{}g(p)<g(c).\end{array}\right.$
(2.1)

where $g(p)$ and $g(c)$ are the value of the neighbouring pixel $p$, and the
central pixel $c$, respectively. Consequentially, if we label the neighbouring
pixels as $p_{1},p_{2},...,p_{8}$ same as Figure 1, an 8-digit binary number
will be encoded to a LBP as:

$lbp=\sum_{i=1}^{8}2^{i-1}S(p_{i},c).$ (2.2)

Note that, equations (2.1) and (2.2) can be described based on directional
derivatives $d_{i}$, defined as

$d_{i}=\lim_{p_{i}\rightarrow c}\frac{g(p_{i})-g(c)}{\|p_{i}-c\|},$

for $i=1,2,...,8$, and $Hardlim$ function $H$ as

$lbp=\sum_{i=1}^{8}2^{i-1}H(d_{i}),$ (2.3)

where $H$ refers $0$ and $1$ for negative and non-negative numbers,
respectively. Here, $d_{i}$ is derivative of two dimensional function $g$ in
direction $v_{i}=p_{i}-c$ at center point $c$. Direction $v_{i}$ are shown in
1 (A) for $i=1,2,...,8$. After obtaining the LBP values for the pixels of the
image, a histogram is constructed to represent the frequency of occurrence of
different LBPs within the image. This histogram effectively summarizes the
local texture patterns present in the image. Since there are $256$ patterns in
the histogram, we mostly summarize it in $8$ to $16$ patterns [2, 6].

(A) (B) (C)

Figure 1: Directional derivatives respect to the standard LBP (A), 8-bit
symmetric LBP (B) and 4-bit symmetric LBP (C).

##  3 Directional derivatives and the symmetric LBP

Finite difference formulas are numerical techniques used to approximate
directional derivatives of functions when analytical methods are not feasible
or when dealing with discrete data points. Directional derivatives represent
the rate of change of a function in a specific direction, providing valuable
insights into how the function varies along a given path. One common approach
to approximating directional derivatives is through one-sided finite
differences. These formulas involve computing the difference in function
values at two nearby points along the desired direction and dividing by the
step size. The LBP uses these concept by applying

$d_{i}\simeq{g(p_{i})-g(c)},~{}~{}~{}i=1,2,...,8,$ (3.1)

and considering ${\|p_{i}-c\|}=1$. These approximations lead the accuracy of
order $1$ [9]. One common approach for approximating the directional
derivatives more accurate is applying central differencing with an error of
order $2$ [9]. The central differencing involves taking one forward Taylor
step and one backward Taylor step, then subtracting these steps. Then, the
directional derivative formula can be calculated by the central differencing
as:

$d_{i}\simeq\frac{g(p_{i})-g(\bar{p_{i}})}{2},~{}~{}~{}i=1,2,...,8,$ (3.2)

where $\bar{p_{i}}$ is that pixel in apposite to $p_{i}$. In mathematical
sense, $\bar{p}_{i}=2c-p_{i}$ if the points are considered as vectors with two
coordinates. In Figure 1 (B) the engaged pixels in to the new approximated
derivatives are shown. From this figure
$\bar{p}_{1}=p_{5},\,\bar{p}_{2}=p_{6},\bar{p}_{3}=p_{7},\,\bar{p}_{4}=p_{8},\,\bar{p}_{5}=p_{1},\,\bar{p}_{6}=p_{2},\,\bar{p}_{7}=p_{3}$
and $\bar{p}_{8}=p_{4}$. The formula, Equation (3.2), also is named symmetric
finite difference in the numerical analysis [9].

If we use new approximations (3.2) in the LBP formulation, we see
$d_{i}=-d_{i+4}$ for $i=1,2,3$ and $4$. So, the values of $d_{i}$ and
$d_{i+4}$ are linearly dependent. It leads, $H(d_{i})$ and $H(d_{i+4})$ are
mostly correlated. In mathematical sense, one can see

$\displaystyle H(d_{i})=1-H(d_{i+4}),$ (3.3)

when $d_{i}\neq 0$. This dependency may reduce the efficiency of the LBP.
Correlation matrix showing the correlation coefficients between variables
$H(d_{i})$ is presented in Figure 2 for a face image. The correlation
coefficient measures how much and in which direction two variables are linked
linearly [10]. From Figure 2, the correlation coefficients between $H(d_{i})$
and $H(d_{i+4})$ is around $-0.95$ which it highlights the linear dependency
between the variables. This dependency does not occur with the same intensity
for the standard LBP, which applies symmetric approximation (3.1). The
correlation coefficient between the variables $H(d_{i})$ and $H(d_{i+4})$ in
the standard LBP is around $-0.65$.

Figure 2: The correlation matrix showing the correlation coefficients between
variables $H(d_{i})$ for a face image. The coefficients between $H(d_{i})$ and
$H(d_{i+4})$ is less than $-0.94$ highlights the linear dependency between the
variables.

The linear dependency between variables may reduce the LBP efficiency as is
shown in the next section. To remove this drawback, one can ignore four first
directional derivatives, $d_{1},d_{2},d_{3}$ and $d_{4}$, and use only the
last four directional derivatives, $d_{5},d_{6},d_{7}$ and $d_{8}$. The
directions of the selected derivatives are shown in Figure 1 (C). Then a new
LBP formulation, obtained based on the extracted directional derivatives, is

$\displaystyle lbp$ $\displaystyle=\sum_{i=1}^{4}2^{i-1}H(d_{i+4}).$ (3.4)

Therefore, three versions of the LBP may be applied for feature extraction:

  * •

Standard LBP: using eight directional derivatives approximated by Equation
(3.1). This version is referred as StLBP here.

  * •

8-bit symmetric LBP: using eight directional derivatives approximated by
Equation (3.2). This version is referred as SyLBP8 here.

  * •

4-bit symmetric LBP: using four directional derivatives, $d_{5}-d_{8}$,
approximated by Equation (3.2). This version is referred as SyLBP4 here.

The Histogram of frequency of occurrence of different LBP patterns within two
different images respecting StLBP, SyLBP8 and SyLBP4 are presented in Figure
3. From Figure 3, the histograms of SyLBP8 and SyLBP4 are similar for a face
image but they are slightly different for the mouth image. However, they are
different from those of StLBP. Note, in the StLBP and SyLBP8, 256 patterns are
extracted which are then reduced to 16 features using the histogram, while the
SyLBP4 extracts 16 patterns directly.

Figure 3: The histogram respect to StLBP, SyLBP8 and SyLBP4 within a global
and a local images is presented from left to right, respectively.

##  4 Experiment results and discussions

In this section, we present the outcomes of our experiments for face detection
and facial expressions recognition. We use databases CFD [11], CFD-MR [12],
and CFD-INDIA [13], containing 1410 face and 1410 clutter images for face
detection. The facial regions were manually cropped and resized to images of
size $64\times 64$. And CK dataset [14] is applied for facial expressions
classification. The CK dataset comprises 981 gray-scale images of facial
expressions, each measuring $48\times 48$ pixels. These images are annotated
into seven distinct emotional classes: anger (135 samples), contempt (54
samples), disgust (177 samples), fear (75 samples), happiness (207 samples),
sadness (84 samples), and surprise (249 samples). Prior to conducting
experiments, we preprocessed the dataset by dividing each facial image into 16
sub-images. This preprocessing step facilitated the extraction of LBP features
from the facial expressions. Some facial images presented in the databases are
demonstrated in Figure 4.

Figure 4: Some human faces for face detection (left) and facial expression
recognition (right). These images are presented in CFD, CFD-MR, CFD-INDIA and
CK datasets.

For LBP feature extraction, we used the standard formulation (2.2), second-
order formulation (2.3) and the reduced formulation (3.4) for SLBP, NLBP8 and
NLBP4, respectively. These features were then classified by the Support Vector
Machine (SVM), with 70% of pictures allocated for training and 30% for
testing. We used both Linear SVM and Non-linear SVM for classification. For
non-linear SVM classification using the radial basis function (RBF) kernel, we
set the kernel parameter $\gamma=100$ (determines the influence of individual
training samples, with low values meaning ’far’ and high values meaning
’close’) and the regularization parameter $C=10$ (balances the classification
error term and the regularization term. A smaller $C$ allows for a larger
margin and may result in more miss classifications but a simpler model, while
a larger $C$ emphasizes classifying the training data correctly and may result
in a smaller margin but potentially a better fit to the training data).

Table 1 presents the accuracy of the face detection classification, and Table
2 presents the accuracy of each class obtained through our experiments in
facial expressions recognition. From the results presented, it can be observed
that the standard LBP (StLBP) is more accurate than the 8-bit symmetric LBP
(SyLBP8) and nearly as accurate as the 4-bit symmetric LBP (SyLBP4). This
suggests that the 4-bit symmetric LBP is able to effectively extract the
relevant texture patterns in the datasets, while the 8-bit symmetric LBP does
not provide this. The reason for this is that the 4-bit symmetric LBP only
extracts 16 patterns and does not require a histogram-based dimension
reduction, unlike the 8-bit symmetric LBP which extracts 256 patterns and
relies on the histogram process. Since the histogram-based dimension reduction
may not be perfect, the 8-bit symmetric LBP does not necessarily present more
efficient features compared to the 4-bit version. Therefore, the authors
suggest applying the 4-bit symmetric LBP instead of the standard LBP, as it
leads to only 16 patterns instead of 256 while maintaining accurate results.
This provides a more efficient and compact representation of the texture
information in the images.

Table 1: Accuracy of the SVM for face detection. Three different LBPs are applied for feature extraction. |  |  |  |  Accuracy ($\%$) |  |  |
---|---|---|---|---|---|---|---
|  | Linear SVM |  |  |  | RBF SVM |
LBP | StLBP | SyLBP8 | SyLBP4 |  | StLBP | SyLBP8 | SyLBP4
face | 99.99 | 99.96 | 99.94 |  | 99.76 | 99.27 | 99.44
clutter | 99.30 | 99.21 | 99.07 |  | 100 | 99.98 | 100
total | 99.75 | 99.58 | 99.50 |  | 99.88 | 99.63 | 99.77
Table 2: Accuracy of the SVM for face emotional recognition. Three different LBPs are applied for feature extraction. |  |  |  |  Accuracy ($\%$) |  |  |
---|---|---|---|---|---|---|---
|  | Linear SVM |  |  |  | RBF SVM |
LBP | StLBP | SyLBP8 | SyLBP4 |  | StLBP | SyLBP8 | SyLBP4
anger | 95.7 | 90.6 | 92.2 |  | 82.7 | 84.0 | 87.3
contempt | 90.6 | 81.2 | 86.8 |  | 87.6 | 78.7 | 86.1
disgust | 95.7 | 92.4 | 94.6 |  | 88.7 | 83.4 | 88.4
fear | 95.6 | 91.9 | 94.6 |  | 92.1 | 85.4 | 89.0
happiness | 97.4 | 96.6 | 98.0 |  | 97.2 | 95.6 | 97.3
sadness | 92.8 | 88.5 | 93.5 |  | 87.5 | 81.0 | 86.5
surprise | 97.4 | 96.3 | 97.4 |  | 96.9 | 94.8 | 96.5
total | 96.0 | 93.0 | 95.2 |  | 91.8 | 88.6 | 92.0

##  5 Conclusion

In this study, we conducted experiments on the CFD, CFD-MR, CFD-INDIA and CK
datasets to explore the classification of the face detection and facial
expressions recognition using Local Binary Pattern (LBP) features and Support
Vector Machine (SVM) models. Our primary objective was to evaluate the
effectiveness of using directional derivatives in the LBP feature extraction
and the accuracy of the SVM classification. We proposed the symmetric LBP and
we found using 8-bit binary numbers is not necessary and one can use 4-bit
binary numbers when the directional derivatives are approximated by the
symmetric finite differences. Then, the efficiency of the LBP enhanced when
four first directional derivatives, as outlined in the paper, are removed from
the LBP formula and only four last ones are considered. So, the symmetric LBP,
applied 4-bit binary numbers, yielded promising results in extracting
discriminative features from facial images. Furthermore, our experiments
demonstrated that SVM classifiers, both Linear and Non-linear with radial
basis function kernel, were effective in classifying emotional expressions. It
is suggested to explore the implementation efficiency of the symmetric finite
differences in larger pixel blocks, such as $5\times 5$ and $7\times 7$
blocks, to further evaluate their impact on LBP performance. Looking ahead,
future research could focus on applying the symmetric LBP on larger and more
diverse datasets, to find the efficiency of the new approach for other
problems. The idea also can be extended to use more complex directional
derivative formulas with higher order of approximation. This may enhance the
efficiency of the LBP.

## References

  * [1] T. Ojala, M. Pietikäinen, D. Harwood, A comparative study of texture measures with classification based on featured distributions, Pattern recognition 29 (1) (1996) 51–59.
  * [2] T. Pajdla, J. Matas, Computer Vision-ECCV 2004: 8th European Conference on Computer Vision, Prague, Czech Republic, May 11-14, 2004. Proceedings, Part I, Vol. 3021, Springer, 2004.
  * [3] G. Huo, H. Guo, Y. Zhang, Q. Zhang, W. Li, B. Li, An effective feature descriptor with gabor filter and uniform local binary pattern transcoding for iris recognition, Pattern Recognition and Image Analysis 29 (2019) 688–694.
  * [4] K. Kaplan, Y. Kaya, M. Kuncan, H. M. Ertunç, Brain tumor classification using modified local binary patterns (lbp) feature extraction methods, Medical hypotheses 139 (2020) 109696.
  * [5] H. N. Vu, M. H. Nguyen, C. Pham, Masked face recognition with convolutional neural networks and local binary patterns, Applied Intelligence 52 (5) (2022) 5497–5512.
  * [6] S. H. Khaleefah, S. A. Mostafa, A. Mustapha, M. F. Nasrudin, Review of local binary pattern operators in image feature extraction, Indonesian Journal of Electrical Engineering and Computer Science 19 (1) (2020) 23–31.
  * [7] B. Zhang, Y. Gao, S. Zhao, J. Liu, Local derivative pattern versus local binary pattern: face recognition with high-order local pattern descriptor, IEEE transactions on image processing 19 (2) (2009) 533–544.
  * [8] M. Martolia, N. Dhanore, A. Singh, V. Shahare, N. Arora, A modified local binary pattern (lbp) for content-based image retrieval, International Journal of Advanced Science and Technology 29 (1) (2020) 1630–1644.
  * [9] R. J. LeVeque, Finite difference methods for ordinary and partial differential equations: steady-state and time-dependent problems, SIAM, 2007.
  * [10] J. R. Schott, Matrix analysis for statistics, John Wiley & Sons, 2016.
  * [11] D. S. Ma, J. Correll, B. Wittenbrink, The chicago face database: A free stimulus set of faces and norming data, Behavior research methods 47 (2015) 1122–1135.
  * [12] D. S. Ma, J. Kantner, B. Wittenbrink, Chicago face database: Multiracial expansion, Behavior Research Methods 53 (2021) 1289–1300.
  * [13] A. Lakshmi, B. Wittenbrink, J. Correll, D. S. Ma, The india face set: International and cultural boundaries impact face impressions and perceptions of category membership, Frontiers in psychology 12 (2021) 627678.
  * [14] P. Lucey, J. F. Cohn, T. Kanade, J. Saragih, Z. Ambadar, I. Matthews, The extended cohn-kanade dataset (ck+): A complete dataset for action unit and emotion-specified expression, in: 2010 ieee computer society conference on computer vision and pattern recognition-workshops, IEEE, 2010, pp. 94–101.