# Discovering Fine-Grained Semantics in Knowledge Graph Relations

Nitisha Jain
Hasso Plattner Institute
University of Potsdam
Potsdam, Germany
<EMAIL_ADDRESS>
&Ralf Krestel
ZBW - Leibniz Centre for Economics &
Kiel University
Kiel, Germany
<EMAIL_ADDRESS>

###### Abstract

When it comes to comprehending and analyzing multi-relational data, the
semantics of relations are crucial. Polysemous relations between different
types of entities, that represent multiple semantics, are common in real-world
relational datasets represented by knowledge graphs. For numerous use cases,
such as entity type classification, question answering and knowledge graph
completion, the correct semantic interpretation of these relations is
necessary. In this work, we provide a strategy for discovering the different
semantics associated with abstract relations and deriving many sub-relations
with fine-grained meaning. To do this, we leverage the types of the entities
associated with the relations and cluster the vector representations of
entities and relations. The suggested method is able to automatically discover
the best number of sub-relations for a polysemous relation and determine their
semantic interpretation, according to our empirical evaluation.

##  1 Introduction

Relations between different words or phrases are important for the semantic
understanding of text. Popular knowledge graphs (KGs) such as Yago
Mahdisoltani et al. (2014), NELL Mitchell et al. (2018) and DBpedia Lehmann et
al. (2015) are formulated in terms of relational databases where the entities
are linked to each other with different relations or predicates. In real-world
textual data, the relations are often polysemous by nature, i.e., they exhibit
distinct meanings in different contexts. Similar to the task of word sense
disambiguation, that is required to understand different contextual meanings
of words, relation disambiguation is needed to interpret the specific,
contextual semantics of relations. Relation polysemy occurs frequently in open
texts and has been studied and discussed by previous works on automatic
relation extraction from texts Min et al. (2012); Galárraga et al. (2014); Han
and Sun (2016). Relation semantics are particularly important in the context
of knowledge graphs which are widely used for systematic representation of
data in the form of $\langle subject,predicate,object\rangle$ triples. Here,
subject and object are chosen from a set of entities, while the predicate that
links the entities to each other belongs to a set of relations. As the triples
in KGs are derived from real-world facts, ambiguity from texts often makes it
way into the KG triples as well. Specifically, the relations may represent
multiple meanings depending on the context, which in the case of KG triples,
is defined by the types of the entities being connected by the relations. The
underlying idea of defining the role of words by their context is quite old in
Linguistics, advocated by Firth in 1957 as ‘a word is characterized by the
company it keeps’ Firth (1957). In the context of KGs, one could say ‘a
relation is characterized by the entity types it connects’.

In order to gauge the issue of multiple relation semantics in popular KGs, we
analysed the relations in the Yago3 dataset in terms of the number of unique
entity types pairs that were found in the associated triples. The results are
plotted in Figure 1. It can be seen that the majority of the relations have
multiple entity types associated with them, with generic relations such as
$owns$ and $created$ exhibiting very high plurality. Similar insights were
also derived from the NELL knowledge graph. Some examples of the actual entity
types associated with polysemous relations from these KGs are shown in Table
1.

Figure 1: The type pairs associated with different relations in Yago.

In this work we advocate that for such relations that are associated with a
number of different entity type pairs, it would be prudent to instead split
them and create new sub-relations that have a more concise meaning according
to the context. The meanings of the sub-relations could be identified based on
the distinct types of the associated entities and therefore, be clearly
defined. However, this approach can be tricky since entity types can vary
widely. While some types such as television and movie for the created relation
in Yago are semantically similar to one another, other types are quite
different, for instance company and writer, or airport and club in the case of
owns relation. Due to the complex hierarchy of classes (entity types)111the
terms class and entity type will be used interchangeably in the paper from
this point on in the underlying schema (or ontology), entity types belong to
different granularity levels Jain et al. (2021) leading to a wide range of
semantic similarity between them. It is, therefore, a non-trivial task to
decide how a relation should be split into sub-relations based on the
semantics of the entity types associated with it, both in terms of the number
of sub-relations as well the subset of entity types that the sub-relations
should encompass.

In this work, we define the problem statement of fine-gained relation
refinement which concerns with the disambiguation of polysemous relations in
relational datasets and propose a data-driven and scalable method named
FineGReS (Fine-Grained Relation Semantics) as a first solution towards the
same. The fine-grained semantics for the relations are derived by relying on
the multiple semantics of the relations evident from the types of the
associated entities. The proposed approach leverages knowledge graph
embeddings, that provide representations of the KG entities and relations in a
continuous vector space. We find optimal clusters in the latent space to
identify the underlying semantic features such that polysemous relations can
be represented in terms of multiple sub-relations with well-defined semantics.
This approach is able to automatically determine not only the optimal number
of sub-relations (corresponding to the number of clusters), but also the
entity types that should be associated with each of them so as to have the
best semantic representation. Experimental evaluation performed on popular
relational datasets reveals the benefits of defining fine-grained semantics
and brings forth the efficacy of the proposed approach in the face of the
challenging nature of this task.

Table 1: Examples of Multiple Semantics of Relations.

Yago created NELL agentBelongsTo- Organization (writer, movie) (politician,
politicalparty) (player, movie) (country, sportsleague) (artist, movie)
(sportsteam, sportsleague) (officeholder,movie) (coach—sportsleague)
(writer,fictional_character) (person, charactertrait) (artist,computer_game)
(televisionstation, company) (artist,medium) (writer,television)
(company,computer_game)

#### Contributions.

1. We formally define the task of fine-grained relation refinement in relational datasets and motivate its importance and benefits.  2. We propose a data-driven and scalable method FineGReS to identify multiple sub-relations that capture the different semantics of the relations via clustering in the latent space and empirically evaluate their quality.  3. Additionally, we illustrate the benefits achieved by substituting a polysemous relation with multiple fine-grained sub-relations as obtained from the proposed approach on downstream applications, such as entity classification.

The code and data will be made publicly available.

##  2 Fine-Grained Relation Semantics

Relation polysemy is quite common in knowledge graphs due to two primary
reasons. Firstly, the schema for most large scale KGs that are in use today
have been constructed through manual or semi-automated efforts, where the
relations between the entities are curated from text. Relations are often
abstracted in such KGs for simplification and avoidance of redundancies. This
may result in cases where a single relation serves as a general notion between
various different types of KG entities and has more than one semantic meaning
associated with it. In addition to this, the fact that these KGs represent
real-world facts that are expressed in natural language having inherent
ambiguities, contributes further to the relation polysemy in KGs. For
instance, the relation phrase ‘part of’ represents varied semantics based on
its context of biology (finger part of hand), organizations (Google part of
Alphabet), geography (Amazon part of South America) and many others. Even in
KGs that have a large number of different relations can suffer from ambiguous
relations, for instance DBpedia has around 300 relations that are relatively
well-defined in terms of their entity types, however there exist relations
such as award and partOf that still convey ambiguity. The determination of
fine-grained relation semantics in relational data is an important task which
can bring substantial benefits to a wide range of NLP and semantic use cases
as discussed further in this section.

The task of relation extraction is essential for information extraction from
texts and it continues to be challenging due to the varied semantics of the
evolving language. For identifying patterns and extracting relation mentions
from text, unsupervised techniques typically rely on the predefined types of
relation arguments Hasegawa et al. (2004); Shinyama and Sekine (2006); Chen et
al. (2005). Given an existing KG and schema, with the goal to extract facts
for a particular relation from a new corpus of text, a distant supervision
approach will leverage relation patterns based on the types of entities over
the text. As an example, if the relation created has been established between
a painter and artwork, then the identification of this relation can be aided
by specific patterns in text. However, if the relation created is generically
defined between any person entity and any work entity, then the resulting text
patterns for this relation will be noisy and varied, therefore may fail to
identify the correct fact triples from text. Identifying the different
meanings of a relation in different contexts can help with defining concrete
patterns for extraction of relation phrases.

This is also useful for identification and classification of entities by their
types in a knowledge graph. E.g. the target entity of the relation directed is
likely to be of type movie or play. If the relations have a wider semantic
range, the type of entities cannot be identified at a fine-grained level. For
instance, it might be only possible to identify the entity type as work and
not specifically movie, which could adversely affect the performance of
further applications such as entity linking and question answering. Numerous
question answering systems that use knowledge graphs as back-end data
repositories (KBQA) Cui et al. (2019) rely on the type information of the
entities to narrow down the search space for the correct answers. Thus,
distinct relation semantics in terms of the types of connected entities are
essential for supporting QA applications over KGs.

We would like to emphasize that task of defining fine-grained relation
semantics is important in the context of KG refinement, not being merely
limited to already existing datasets but in general. KGs usually evolve over
time and often in a fragmented fashion, where new facts might be added to a KG
that do not strictly conform or can be correctly encapsulated by the existing
ontology. Addition of such new facts might easily lead to noisy and abstracted
semantics in previously well-defined KG relations. Relation disambiguation
would therefore play a important role in identifying new fine-grained sub-
relations with precise semantics. The proposed FineGReS method is generally
applicable and could prove to be incredibly useful in all the above scenarios.

From these examples, it is therefore evident that fine-grained relation
semantics can be beneficial to a wide variety of use cases and is indeed an
important problem that has not been fully explored yet. In the next section,
we provide the necessary background and present the problem statement.

##  3 Preliminaries

#### Knowledge Graph.

For a knowledge graph $\mathcal{G}$, the set of unique relations is denoted as
$\mathcal{R}$. A KG fact (or triple) $F$ = $\langle e_{h},r,e_{t}\rangle$
consists of the head entity $e_{h}$, the tail entity $e_{t}$ and the relation
$r$ that connects them, where $e_{h}$ and $e_{t}$ belong to the set of
entities $\mathcal{E}$. Any given relation $r$ $\in$ $\mathcal{R}$ appears in
several triples, forming a subset $\mathcal{G^{\prime}}$ of $\mathcal{G}$.

#### Entity Types.

The semantic types or classes of the entities are defined in an ontology
associated with a KG that defines its schema. The entities $e$ $\in$
$\mathcal{E}$ are connected with their types by ontological triples such as
$\langle e,typeOf,t\rangle$, where $t\in\Tau$, the set of entity types in the
ontology.

We define a type pair as the tuple $\langle t_{h},t_{t}\rangle$ where $\langle
e_{h},typeOf,t_{h}\rangle$ and $\langle e_{t},typeOf,t_{t}\rangle$. A set of
unique type pairs (for a given relation $r$ and corresponding
$\mathcal{G^{\prime}}$ is denoted as $P_{r}$. Thus we have, $P_{r}=\\{\langle
t_{h},t_{t}\rangle|\langle e_{h},typeOf,t_{h}\rangle,\langle
e_{t},typeOf,t_{t}\rangle,\langle
e_{h},r,e_{t}\rangle\in\mathcal{G^{\prime}}\\}$. The total number of such
unique type pairs for relation $r$, i.e. $|P_{r}|$ is denoted by
$\mathcal{L}_{r}$.

#### KG Embeddings.

Knowledge graph embeddings have gained immense popularity and success for
representation learning of relational data. They provide an efficient way to
capture latent semantics of the entities and relations in KGs. The main
advantage of these techniques is that they enable easy manipulation of KG
components when represented as vectors in low dimensional space. For example
in TransE Bordes et al. (2013), for a triple $\langle h,r,t\rangle$ the
vectors h, r and t satisfy the relation h \+ r = t or r = t \- h. In this
work, we leverage the representational abilities of the embeddings to obtain
the semantic vectors for relations expressed in terms of the entities
associated with them. For vectors h, r and t as obtained from an embedding
corresponding to a KG triple $\langle e_{h},r,e_{t}\rangle$, we define a
vector $\Delta_{r_{i}}$ which is a function of $t_{i}$ and $h_{i}$. Every
$\Delta_{r_{i}}$ vector is mapped to a type pair $P_{r_{i}}$ as per the
entities $e_{h}$, $e_{t}$ that they are both derived from.

#### Problem Definition.

Given a relation $r$ $\in$ $\mathcal{R}$ in $\mathcal{G}$, the set of
$\Delta_{r}$ vectors and the corresponding set of type pairs $P_{r}$, the goal
is to find for this relation an optimal configuration of clusters
$\mathcal{C}_{opt}$ =
$\\{\mathcal{C}_{1},\mathcal{C}_{2}...\mathcal{C}_{N}\\}$, where the
$\Delta_{r_{i}}$ vectors are uniquely distributed among the clusters i.e. each
$\Delta_{r_{i}}$ $\in$ $\mathcal{C}_{j}$, $i=1...|\mathcal{G^{\prime}}|$,
$j=1...N$, s.t. an objective function $\mathcal{F}(\mathcal{C}_{opt})$ is
maximized.

Further, each cluster $\mathcal{C}_{j}$ represents the semantic union of the
subset of type pairs $P^{\prime}_{r}$ where $\exists$ $\Delta_{r_{i}}$ $\in$
$\mathcal{C}_{j}$ s.t. $\Delta_{r_{i}}$ is mapped to one of the type pairs in
$P^{\prime}_{r}$. Thus, the optimal configuration of clusters corresponds to
the optimal number of sub-relations and their fine-grained semantics as
defined by the type pairs that they represent. The proposed FineGReS method
can derive this optimal configuration for the relations of a KG.

##  4 Method

In this section, we describe in detail the design and implementation details
of the proposed FineGReS method for a relation that can easily scaled to any
number of relations in the dataset.

###  4.1 Semantic Mapping for Facts

For every unique relation $r$ in $\mathcal{G}$, we firstly find the subset of
facts $\mathcal{G^{\prime}}$ where $r$ appears. To understand the semantics of
the entities associated with $r$, the entities are mapped to their
corresponding classes as defined in the underlying ontology. By doing so, we
obtain a list of entity type pairs $\langle t_{h},t_{t}\rangle$ for the
relation. Note that several entities in $\mathcal{G^{\prime}}$ might map to
the same type and therefore, a single type pair tuple would be obtained
several times. Therefore in the next step, we identify the unique type pairs
for a relation $r$ as the set $P$. At this stage, every fact in
$\mathcal{G^{\prime}}$ is associated with a type pair $\langle
t_{h},t_{t}\rangle\in P$ that represents the semantics of this fact. For
example, for the $created$ relation, a triple $\langle
DaVinci,created,MonaLisa\rangle$ would be mapped to $\langle
artist,painting\rangle$ as per the types of the head and tail entities.

###  4.2 Vector Representations for Relations

For representing the semantics of $r$ in terms of the associated entities, we
leverage pre-trained KG embeddings. As proposed in previous work Jiang et al.
(2020), we obtain a representation for $r$ from h and t corresponding to every
fact in $\mathcal{G^{\prime}}$ and denote this vector as $\Delta_{r}$. In this
way, for every relation $r$, a set of $\Delta_{r}$ vectors is obtained from
the KG embeddings, in addition to the actual r vector that the embedding
already provides. These $\Delta_{r}$ vectors are already mapped to the unique
type pairs $P_{i}$ $\in$ $P$ for the relation $r$ (according to the fact
triples they were calculated from)222we denote $P_{r}$ as $P$ when the
relation $r$ is clear from the context, such that each unique type pair is
represented by a set of $\Delta_{r}$ vectors. These $\Delta_{r}$ vectors
encode the information conveyed by both the head and tail entity types
together and represent the relationship between the entities, they therefore
represent the latent semantics of the relations in different facts. The
$\Delta_{r}$ vectors become our data points (with the associated type pairs
${P_{i}}$ serving as their labels).

Figure 2: Visualization of vectors for agentcontrols relation in NELL with
associated type pairs.

#### Relation Semantics.

While it is believed that KG embeddings are able to capture relation
similarity in the embedding space, i.e., relations having similar semantics
occur close together in the vector space Do et al. (2018); Kalo et al. (2019),
we found that relations having multiple semantics (based on the context of
their entities) are, in fact, not represented well in the vector space. In
fact, for polysemous relations, the vectors obtained for a single relation
(from the different facts that it appears in) form separate clusters in the
vector space that do not overlap with the actual relation vector r obtained
from the embeddings. This happens due to the fact that multiple entity pairs
connected by the same relation are semantically different from one another.
Figures 2 illustrates an example from the NELL dataset where this behaviour of
the embedding vectors for relations is clearly visible. We leverage this
semantically-aware behaviour of the embedding vectors to determine meaningful
clusters of $\Delta_{r}$ vectors that represent the distinct latent semantics
exhibited by different entity type pairs connected by the same relation, as
described next.

###  4.3 Clustering for Fine-grained Semantics

For each relation $r$, the total number of unique type pairs $\mathcal{L}$ =
$|P_{r}|$ is theoretically the maximum number of possible semantic sub-
relations or clusters that could be obtained for $r$. This is the maximal
splitting that will assign a different sub-relation for every different type
pair. However, in practice, it is rare that all the type pairs would have
completely different semantics. For example, the $created$ relation in Yago
has type pairs $\langle artist,painting\rangle$ and $\langle
artist,music\rangle$ that have the same head entity type, while the type pair
$\langle organization,software\rangle$ conveys quite a different meaning.
While a single relation is not sufficient to be representative of the
semantics of all facts which is it appears in, at the same time, a naive
maximal splitting of the relation as per the unique type pairs would also be
inefficient and lead to a large number of unnecessary sub-relations.

The FineGReS method aims to find an optimal number and composition of clusters
$\mathcal{C}_{opt}$ for the type pairs that can convey distinct semantics of
the relations based on the data, by combining similar type pairs while
separating the dissimilar ones. Each of the clusters having one or more than
one semantically similar type pairs represents a potential sub-relation. In
order to obtain this configuration, various compositions of the clusters need
to be analysed for optimality. Clustering is performed in an iterative manner
with a predefined number of clusters and combinations of type pairs within
each cluster. Since it is not feasible or practical to consider all possible
clusters of the type pairs, FineGReS leverages the semantic similarity of type
pairs to narrow down the search space for obtaining the optimal clusters. For
this, the similarity scores between all combinations of the unique type pairs
$(t_{h_{i}},t_{t_{i}})$, $(t_{h_{j}},t_{t_{j}})$ are calculated. First, the
vector representations for the types are obtained. Subsequently, the
similarity scores are obtained by calculating the similarity scores between
the vectors corresponding to $t_{h_{i}}$ and $t_{h_{j}}$ as well as
$t_{t_{i}}$ and $t_{t_{j}}$ and then taking their mean value.

#### Iterative Clustering.

The clustering begins with $\mathcal{L}$ clusters, with each cluster
corresponding to one type pair for the relation. The cluster labels are
regarded as type pairs themselves. Following this, the similarity scores of
the type pairs are calculated, and the ones with the highest similarity are
considered as candidate pairs to be merged together and placed in a single
cluster. To generate the ‘ground truth’, the data points ($\Delta_{r}$
vectors) corresponding to both type pairs are assigned the same distinct
label. The number of clusters is given as $\mathcal{L}$ \- 1 during the next
iteration of clustering, and the cluster labels consist of $\mathcal{L}$ \- 2
original type pairs and one merged type pair. If two combinations of type
pairs have the same similarity score in any iteration, ties are broken
arbitrarily. This process of selecting the most similar pair of class
combinations for lowering the number of clusters and obtaining cluster labels
as ground truth is repeated until all type pairs have been gradually merged
back together in a single cluster. For each iteration, the quality of the
clusters is evaluated and compared to the engineered ground truth, and the
best performing cluster configuration is chosen as the optimal set of clusters
$\mathcal{C}_{opt}$ that best represent the sub-relations with fine-grained
semantics333It is to be noted that the labeling of newly proposed sub-
relations is a separate task on its own. In this work, we merely utilize names
of entity types to derive basic labels, however a proper naming scheme for
these relations is a complex task in the context of ontology design and out of
the scope of the current work..

##  5 Experimental Analysis

Table 2: Quality of FineGReS clusters ($C_{FGReS}$) in comparison with
baselines.

Yago NELL Clustering Technique $C_{max}$ $C_{head}$ $C_{tail}$ $C_{FGReS}$
$C_{max}$ $C_{head}$ $C_{tail}$ $C_{FGReS}$ TransE KMC .245 .199 .190 .269
.384 .304 .318 .463 OPC .456 .506 422 .524 .192 .197 .203 .258 SPC .040 .027
.012 .031 .332 .185 .190 .337 HAC .217 .195 .182 .254 .335 .245 .293 .374
DistMult KMC .186 .101 .166 .183 .348 .212 .298 .369 OPC .430 .424 .423 .451
.342 340 .349 .370 SPC .316 .469 .031 .332 .287 .163 .196 .307 HAC .212 .208
.176 .237 .283 .173 .227 .292

To evaluate the performance of the FineGReS, we performed intrinsic empirical
analysis in terms of the quality of the optimal clusters as obtained from the
method. Further, to show the performance gains from FineGReS for a relevant
use case, we performed extrinsic evaluation for the task of entity
classification.

#### Datasets.

We prepared datasets derived from Yago3 and NELL-995 knowledge graphs for
relation analysis and disambiguation in this work. The Yago dataset consists
of 1,492,078 triples, with 31 relations and 917,325 unique entities. The NELL
dataset includes 154,213 triples, with 200 relations and 75,492 unique
entities. For both, the entities were augmented with their types as derived
from the respective ontologies of the KGs.

#### Vectors for Entity Types.

In order to obtain word vector representations of the class types, we use the
pre-trained ConVec embeddings Ehsan Sherkat (2017). We also leveraged the pre-
trained Sentence-BERT Reimers et al. (2019) models from the HuggingFace
library Wolf et al. (2019). Cosine similarity measure was used for calculating
the vector similarities (Euclidean similarity measure provided very similar
results).

#### Knowledge Graph Embeddings.

We perform our experiments on the following widely used KG embedding models :
TransE Bordes et al. (2013) and DistMult Yang et al. (2014). These models are
chosen to serve as prominent examples of embeddings using translation distance
and semantic matching techniques respectively. We use the model
implementations from the LibKGE library Broscheit et al. (2020) for the
Yago3-10 dataset and from OpenKE library Han et al. (2018) for the NELL-995
dataset. It is important to note that in this work, we have purposefully
chosen those embedding techniques that showed the promise of being able to
differentiate the multiple semantics of a relation. Indeed there have been
some embedding models Xiao et al. (2016) that instead aim to encapsulate the
different semantics of the relation in a single representative vector, however
such techniques are not fruitful towards our goal of fine-grained relation
refinement.

Table 3: Examples of Fine-grained Sub-relations.

Dataset - Relation (setting) FineGReS Sub-relations Yago - owns (TransE-HAC)
{$\langle company,airport\rangle$ $\langle organization,airport\rangle$},
{$\langle sovereign,building\rangle$}, {$\langle company,club\rangle$ $\langle
company,company\rangle$, $\langle country,club\rangle$ } Yago - created
(TransE-OPC) {$\langle artist,medium\rangle$ $\langle
officeholder,movie\rangle$}, {$\langle writer,fictional\\_character\rangle$},
{$\langle writer,movie\rangle$ $\langle writer,television\rangle$ $\langle
writer,fictional\\_character\rangle$ $\langle artist,movie\rangle$ $\langle
artist,computer\\_game\rangle$ $\langle player,movie\rangle$}, {$\langle
company,computer\\_game\rangle$} NELL-agentCompetesWith (TransE-Kmeans)
{$\langle company,person\rangle$ $\langle website,person\rangle$ $\langle
person,person\rangle$, $\langle sportsteam,sportsteam\rangle$}, {$\langle
person,company\rangle$, $\langle person,website\rangle$} {$\langle
animal,animal\rangle$, $\langle bird,animal\rangle$}, {$\langle
bank,bank\rangle$}, {$\langle mammal,politicsissue\rangle$} NELL-
subpartOfOrganization (DistMult-Kmeans) {$\langle
sportsteam,sportsteam\rangle$ $\langle stateorprovince,sportsteam\rangle$
$\langle university,sportsteam\rangle$ $\langle city,sportsteam\rangle$ },
{$\langle organization,organization\rangle$}, {$\langle
televisionstation,city\rangle$}, {$\langle company,company\rangle$ $\langle
televisionstation,company\rangle$}, {$\langle
sportsteam,sportsleague\rangle$}, {$\langle bank,bank\rangle$} {$\langle
televisionstation,televisionnetwork\rangle$}, {$\langle
televisionstation,website\rangle$}

#### Baselines.

We establish several baselines to evaluate and compare the performance of the
optimal clusters (hence the corresponding sub-relations) derived from FineGReS
to naive approaches in each experimental setting.
max \- Sub-relations are obtained on the basis of every different type pair
that is found associated with a relation, this naive setting corresponds to
the maximum number of clusters.
head \- Sub-relations represent all type pairs associated with a common head
entity and different tail entities. It is equivalent to grouping the type
pairs in the max setting by head entity types.
tail \- Similar to head, just replacing head entity with tail entity instead
so that sub-relations represent all type pairs associated with a common tail
entity and different head entities.

#### Clustering Techniques.

To explore the affect of different techniques during the clustering step of
FineGReS method, we employed several algorithms : KMeans clustering(KMC),
Spectral (SPC), Optics (OPC) and Hierarchical Agglomerative clustering(HAC).

###  5.1 Cluster Quality Evaluation

The quality of the clusters, and thereby, the resultant sub-relations is
measured in terms of homogeneity score Jain et al. (2018), this metric favors
a clustering scheme where every cluster represents a unique dominant label
that corresponds to one or more unique type pairs in our case. Thus, this
metric best represents the distinct semantics of the clusters. We measure and
report the weighted (as per the number of data points) homogeneity scores for
the clusters of all relations in the different settings of KG embeddings and
clustering techniques in Table 2. It can be seen that in most cases the
$\mathcal{C}_{FGReS}$ clusters obtained by the proposed FineGReS method obtain
higher scores than all the other baselines that were considered for defining
the cluster configurations for sub-relations. This indicates the efficacy of
the method for finding optimal fine-grained sub-relations.

#### Discussion.

Table 3 shows a few representative examples of the sub-relations obtained by
FineGReS in different settings for Yago and NELL. It can be seen that
semantically different entity type pairs have been clearly separated out as
distinct sub-relations, e.g. the $\langle sovereign,building\rangle$ pair for
owns relation where sovereign is semantically distant from other types or
agentCompetesWith where $\langle bank,bank\rangle$ is a separate sub-relation.
Other sub-relations have multiple type pairs associated with them based on
their semantic proximity. Note that in a few cases, the optimal configuration
could indeed be the max or head/tail setting for the relation depending on the
associated type pairs. The FineGReS method is able to automatically determine
this optimal configurations of the sub-relations for each relation relying
solely on the facts in the dataset and the associated type information.

###  5.2 Entity Classification Use Case

Table 4: Performance Comparison for Entity Classification Task for Yago (r
refers to original relations).

r max head tail FineGReS TransE DistMult Precision .893 .916 .906 .322 .923
.928 Recall .908 .925 .921 .425 .941 .942 F1 Score .894 .914 .909 .34 .931
.931

In order to empirically evaluate the FineGReS method in terms of the
usefulness of the derived sub-relations, we consider the popular use case of
entity classification which is an important task for KG completion Neelakantan
and Chang (2015). It is modeled as a supervised multi-label classification
task, where the entities are assigned to their respective types. Previous
works have performed type prediction for entities in KGs based on statistical
features Paulheim and Bizer (2013), textual information Kliegr and Zamazal
(2016) as well as embeddings Biswas et al. (2020). Taking cue from the same,
we built a CNN classifier Zhang and Wallace (2017) for the multi-label
classification task which can jointly classify both the entities in a given
triple to their respective types.

The dataset for the classification task was obtained by replacing the original
polysemous relations in the KG dataset with their corresponding fine-grained
sub-relations in the affected triples, obtained from the best performing
setting of the FineGReS method as well as from the baseline techniques
described in Section 5. The performance of entity classification measured in
terms of weighted precision, recall and F1 scores (averaged over 10 runs) is
shown in Table 4. It can be seen that with well-defined relation semantics,
the performance of the entity classification task improved considerably. In
particular, the gains seen over the max setting are indicative of the
superiority of the FineGReS method in terms of not merely finding any set of
sub-relations but finding the optimal configuration of the sub-relations that
best represent fine-grained semantics for all relations. (Similar results were
also obtained for the NELL dataset).

##  6 Related Work

There is a large body of work in linguistics that deals with multiple
semantics of words Erk and Padó (2008); Reisinger and Mooney (2010);
Neelakantan et al. (2014). Early work on the semantic connections between the
relations and their associated entities in texts was introduced in 1963 Katz
and Fodor (1963) with the concept of selectional preference for performing
predicate or verb sense disambiguation Resnik (1997). The idea advocates that
verbs can semantically restrict the types of the arguments that occur around
them, thus having a preference for certain classes of entities. In contrast,
our work in this paper focuses on the predicates that are generic and have
insufficient constraints for their entity types. In such cases, the diverse
entity types were, in fact, leveraged to identify and define the fine-grained
semantics of these predicates by dividing them into multiple predicates.

In other work related to relation semantics, Jiang et al. (2020) explores the
entailment between relations, e.g. the relation creator entails author or
developer in the sense that creator subsumes the other relations. Similar to
our work, the authors leverage the entity type information to solve the multi-
classification problem of assigning the child relations to the parent ones.
Our problem statement of fine-grained relation refinement is significantly
more challenging and impactful in the sense that it involves the
identification of novel sub-relations in an unsupervised manner.

While the idea of learning better embeddings for words by considering their
multiple contextual semantics is not new Vu and Parker (2016), the semantics
of relations have also been recently studied in regards to learning knowledge
graph embeddings. In Lin et al. (2015) the authors advocated the need for
learning multiple relation vectors to capture the fine-grained semantics,
however this study was limited in scope and lacked any consideration for
complex entity type hierarchies in KGs. In Zhang et al. (2018), the authors
create a 3-level relation hierarchy which combines similar relations as well
splits relations into sub-relations, in order to improve the embeddings for
relations. The proposed approach is quite rigid and opaque in terms of the
actual semantics of the relations obtained from it. In fact, the number of
clusters was predefined for all relations across a dataset, in contrast to the
FineGReS method that can determine an optimal number of clusters separately
for each relation based on the associated entity types.

The diverse semantics of relations was also considered by Ji et al. (2015)
where the authors proposed two different vectors for the relations as well as
entities, to capture their meanings and connections with each other.
Similarly, in Xiao et al. (2016) the authors discussed the generation of
multiple translation components of relations based on their semantics with the
help of a bayesian non-parametric infinite mixture model. However, they do not
perform a systematic analysis of the relations semantics and a qualitative
evaluation of their approach is missing.

In general, the above discussed works have leveraged relation polysemy for
designing better embedding models and improving their link prediction
performance on knowledge graphs. In this work, we instead approach the problem
of relation polysemy and discovery of the latent relation semantics with the
goal of knowledge graph refinement and improvement of the quality of the
relations in underlying ontology. More importantly, none of the previous works
have explored the challenges of deriving fine-grained relations from an
existing polysemous relation in the presence of complex semantic relationships
between the associated entity types, which is quite common for real-world
datasets. Our proposed FineGReS method performs this task in a systematic and
data-driven fashion and shows promising benefits for downstream applications.

##  7 Conclusion

In this paper, we have studied the need for relation disambiguation for
knowledge graphs due to the inherent relation polysemy in these datasets. We
have proposed a scalable, data-driven method FineGReS that automatically
determines an opti- mal configuration for deriving sub-relations with concrete
semantics. Empirical evaluation has demonstrated the efficacy of the method
for learning fine-grained relation semantics for real-world data. The
performance improvement achieved for downstream application of entity
classification strongly indicates the promise of this approach. Since the
method relies on the type information of the entities, FineGReS can currently
be applied only to the KGs accompanied by their ontologies, it would be
interesting to extend the proposed approach to derive entity semantics from
other sources, such as text. As future work, we also plan to perform a
systematic analysis of the utility and impact of this method on further NLP
tasks, such as relation extraction and question answering over KGs.

## References

  * Biswas et al. (2020) Russa Biswas, Radina Sofronova, Mehwish Alam, and Harald Sack. 2020.  Entity type prediction in knowledge graphs using embeddings.  _arXiv preprint arXiv:2004.13702_.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  In _Advances in neural information processing systems_ , pages 2787–2795.
  * Broscheit et al. (2020) Samuel Broscheit, Daniel Ruffinelli, Adrian Kochsiek, Patrick Betz, and Rainer Gemulla. 2020.  LibKGE - A knowledge graph embedding library for reproducible research.  In _Proc. of the 2020 Conf. on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 165–174.
  * Chen et al. (2005) Jinxiu Chen, Donghong Ji, Chew Lim Tan, and Zheng-Yu Niu. 2005.  Unsupervised feature selection for relation extraction.  In _Companion Volume to the Proceedings of Conference including Posters/Demos and tutorial abstracts_.
  * Cui et al. (2019) Wanyun Cui, Yanghua Xiao, Haixun Wang, Yangqiu Song, Seung-won Hwang, and Wei Wang. 2019.  Kbqa: learning question answering over qa corpora and knowledge bases.  _arXiv preprint arXiv:1903.02419_.
  * Do et al. (2018) Kien Do, Truyen Tran, and Svetha Venkatesh. 2018.  Knowledge graph embedding with multiple relation projections.  In _2018 24th International Conference on Pattern Recognition (ICPR)_ , pages 332–337. IEEE.
  * Ehsan Sherkat (2017) Evangelos Milios Ehsan Sherkat. 2017.  Vector embedding of wikipedia concepts and entities.
  * Erk and Padó (2008) Katrin Erk and Sebastian Padó. 2008.  A structured vector space model for word meaning in context.  In _Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing_ , pages 897–906.
  * Firth (1957) John R Firth. 1957.  A synopsis of linguistic theory, 1930-1955.  _Studies in linguistic analysis_.
  * Galárraga et al. (2014) Luis Galárraga, Geremy Heitz, Kevin Murphy, and Fabian M Suchanek. 2014.  Canonicalizing open knowledge bases.  In _Proceedings of the 23rd acm international conference on conference on information and knowledge management_ , pages 1679–1688.
  * Han and Sun (2016) Xianpei Han and Le Sun. 2016.  Global distant supervision for relation extraction.  In _Thirtieth AAAI Conference on Artificial Intelligence_.
  * Han et al. (2018) Xu Han, Shulin Cao, Lv Xin, Yankai Lin, Zhiyuan Liu, Maosong Sun, and Juanzi Li. 2018.  Openke: An open toolkit for knowledge embedding.  In _Proceedings of EMNLP_.
  * Hasegawa et al. (2004) Takaaki Hasegawa, Satoshi Sekine, and Ralph Grishman. 2004.  Discovering relations among named entities from large corpora.  In _Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04)_ , pages 415–422.
  * Jain et al. (2021) Nitisha Jain, Jan-Christoph Kalo, Wolf-Tilo Balke, and Ralf Krestel. 2021.  Do embeddings actually capture knowledge graph semantics?  In _European Semantic Web Conference_ , pages 143–159. Springer.
  * Jain et al. (2018) Prachi Jain, Pankaj Kumar, Soumen Chakrabarti, et al. 2018.  Type-sensitive knowledge base inference without explicit type supervision.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 75–80.
  * Ji et al. (2015) Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu, and Jun Zhao. 2015.  Knowledge graph embedding via dynamic mapping matrix.  In _Proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 1: Long papers)_ , pages 687–696.
  * Jiang et al. (2020) Zhengbao Jiang, Jun Araki, Donghan Yu, Ruohong Zhang, Wei Xu, Yiming Yang, and Graham Neubig. 2020.  Learning relation entailment with structured and textual information.  In _Automated Knowledge Base Construction_.
  * Kalo et al. (2019) Jan-Christoph Kalo, Philipp Ehler, and Wolf-Tilo Balke. 2019.  Knowledge graph consolidation by unifying synonymous relationships.  In _International Semantic Web Conference_ , pages 276–292. Springer.
  * Katz and Fodor (1963) Jerrold J Katz and Jerry A Fodor. 1963.  The structure of a semantic theory.  _language_ , 39(2):170–210.
  * Kliegr and Zamazal (2016) Tomáš Kliegr and Ondřej Zamazal. 2016.  Lhd 2.0: A text mining approach to typing entities in knowledge graphs.  _Journal of Web Semantics_ , 39:47–61.
  * Lehmann et al. (2015) Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Pablo N Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick Van Kleef, Sören Auer, et al. 2015.  DBpedia–A large-scale, multilingual knowledge base extracted from Wikipedia.  _Semantic Web_ , 6(2):167–195.
  * Lin et al. (2015) Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015.  Learning entity and relation embeddings for knowledge graph completion.  In _Twenty-ninth AAAI conference on artificial intelligence_.
  * Mahdisoltani et al. (2014) Farzaneh Mahdisoltani, Joanna Biega, and Fabian Suchanek. 2014.  YAGO3: A Knowledge Base from Multilingual Wikipedias.  In _7th Biennial Conference on Innovative Data Systems Research_. CIDR Conference.
  * Min et al. (2012) Bonan Min, Shuming Shi, Ralph Grishman, and Chin-Yew Lin. 2012.  Ensemble semantics for large-scale unsupervised relation extraction.  In _Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning_ , pages 1027–1037.
  * Mitchell et al. (2018) Tom Mitchell, William Cohen, Estevam Hruschka, Partha Talukdar, Bishan Yang, Justin Betteridge, Andrew Carlson, Bhavana Dalvi, Matt Gardner, Bryan Kisiel, et al. 2018.  Never-ending learning.  _Communications of the ACM_ , 61(5):103–115.
  * Neelakantan and Chang (2015) Arvind Neelakantan and Ming-Wei Chang. 2015.  Inferring missing entity type instances for knowledge base completion: New dataset and methods.  In _Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 515–525.
  * Neelakantan et al. (2014) Arvind Neelakantan, Jeevan Shankar, Alexandre Passos, and Andrew McCallum. 2014\.  Efficient non-parametric estimation of multiple embeddings per word in vector space.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1059–1069.
  * Paulheim and Bizer (2013) Heiko Paulheim and Christian Bizer. 2013.  Type inference on noisy rdf data.  In _Int. Semantic Web Conf._ , pages 510–525.
  * Reimers et al. (2019) Nils Reimers, Iryna Gurevych, Nils Reimers, Iryna Gurevych, Nandan Thakur, Nils Reimers, Johannes Daxenberger, Iryna Gurevych, Nils Reimers, Iryna Gurevych, et al. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics.
  * Reisinger and Mooney (2010) Joseph Reisinger and Raymond Mooney. 2010.  Multi-prototype vector-space models of word meaning.  In _Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics_ , pages 109–117.
  * Resnik (1997) Philip Resnik. 1997.  Selectional preference and sense disambiguation.  In _Tagging Text with Lexical Semantics: Why, What, and How?_
  * Shinyama and Sekine (2006) Yusuke Shinyama and Satoshi Sekine. 2006.  Preemptive information extraction using unrestricted relation discovery.  In _Proceedings of the Human Language Technology Conference of the NAACL, Main Conference_ , pages 304–311.
  * Vu and Parker (2016) Thuy Vu and D Stott Parker. 2016.  K-embeddings: Learning conceptual embeddings for words using context-embeddings: Learning conceptual embeddings for words using context.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1262–1267.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_.
  * Xiao et al. (2016) Han Xiao, Minlie Huang, and Xiaoyan Zhu. 2016.  Transg: A generative model for knowledge graph embedding.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2316–2325.
  * Yang et al. (2014) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2014.  Embedding entities and relations for learning and inference in knowledge bases.  _arXiv preprint arXiv:1412.6575_.
  * Zhang and Wallace (2017) Ye Zhang and Byron C Wallace. 2017.  A sensitivity analysis of (and practitioners’ guide to) convolutional neural networks for sentence classification.  In _Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 253–263.
  * Zhang et al. (2018) Zhao Zhang, Fuzhen Zhuang, Meng Qu, Fen Lin, and Qing He. 2018.  Knowledge graph embedding with hierarchical relation structure.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3198–3207.


# On Value Iteration Convergence in Connected MDPs

Arsenii Mustafin
Department of Computer Science
Boston University
Boston, MA 02215, USA
<EMAIL_ADDRESS>
&Alex Olshevsky
Department of Electrical and Computer Engineering
Boston University, Boston, MA 02215, USA
<EMAIL_ADDRESS>
Ioannis Ch. Paschalidis
Department of Electrical and Computer Engineering
Boston University, Boston, MA 02215, USA
<EMAIL_ADDRESS>

###### Abstract

This paper establishes that an MDP with a unique optimal policy and ergodic
associated transition matrix ensures the convergence of various versions of
the Value Iteration algorithm at a geometric rate that exceeds the discount
factor $\gamma$ for both discounted and average-reward criteria.

##  1 Introduction

Markov decision process is a common mathematical tool to model multi-step
iteration with an action-reward system, which draws increased attention due to
recent popularity of Reinforcement learning. Value iteration and policy
iteration are two basic algorithms which are used to solve MDP, or to find
optimal optimal policy. Two algorithms are different in their nature: policy
iteration finds optimal policy exact optimal policy, but requires more
operations every iteration of the algorithm. Value iteration find approximate
optimal policy up to desired accuracy $\epsilon$, every iteration of this
algorithm requires less operations, but overall number of iterations depends
on $\epsilon$. In general, value iteration converges geometrically at a rate
determined by the discount factor $\gamma$. An example where this convergence
rate is exact can be provided. Faster convergence can occur under additional
assumptions, as shown in [3], Section 6.6.6, or in [1].

###  1.1 Motivation and contribution

In this paper, we aim to analyze the additional convergence of the Value
Iteration algorithm beyond the theoretically guaranteed convergence with
discount factor $\gamma$. An example of this convergence is shown in Figure 1.

We show that under the fairly general assumptions of an irreducible and
aperiodic Markov chain implied by a unique optimal policy (Assumptions 3.1 and
3.2), value iteration exhibits geometric convergence at a rate faster than
$\gamma$. This additional convergence factor reduces the computational
complexity required to achieve an accuracy of $\epsilon$ from:

$\mathcal{O}\left(\frac{\log{1/\epsilon}+\log(1/(1-\gamma))}{\log{(1/\gamma)}}\right)\quad\text{to}\quad\mathcal{O}\left(\frac{\log(1/\epsilon)+\log(1/(1-\gamma))}{\log(1/\gamma)+\log(1/\tau)/N}\right)$

in the discounted reward criteria case ($\gamma<1$).

Additionally, we establish geometric convergence in the average total reward
case with a total complexity of

$\mathcal{O}\left(\frac{\log{(1/\epsilon)}}{\log{(1/\tau)}/N}\right).$

Figure 1: Convergence of the value iteration algorithm on a random MDP with
different discount rates. It can be seen that as $\gamma$ approaches one, the
convergence rate remains geometric with a rate less than $\gamma$.

##  2 Problem formulation

Algorithm 1 Value Iteration algorithm

Parameters Learning rate $\alpha$ and desired accuracy $\epsilon$.

Initialize $V_{0}$, set $t=0$ and set stopping criteria $H$.

Select subset of states $\mathcal{S}_{t}$ and perform $U=\max_{a}r(s,a)+\gamma
P_{a}(s)V$,

Compute $V_{t+1}(s)=(1-\alpha)V_{t}+\alpha(\max_{a}r(s,a)+\gamma
P_{a}(s)V_{t}$) if $s\in\mathcal{S}_{t}$, $V_{t+1}(s)=V_{t}(s)$ otherwise.

if $\textrm{sp}(V_{t+1}-V_{t})\leq H$ then

Increment $t$ by 1 and return to the previous step.

else

Output policy $\pi$, such that
$\pi(s)=\operatorname*{arg\,max}_{a}r(s,a)+\gamma P_{a}(s)V_{t}$.

end if

We consider a discounted reward Markov Decision Process (MDP) defined by the
tuple $(\mathcal{S},\mathcal{A},\mathcal{P},r,\gamma)$, where $\mathcal{S}$ is
the finite set of states, $\mathcal{A}$ is the finite set of actions,
$\mathcal{P}={P(s^{\prime}|s,a)}_{s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}}$
represents the transition probabilities, $r$ is the reward function, and
$\gamma\in[0,1)$ is the discount rate. We denote the reward received during
the transition from $s$ to $s^{\prime}$ as $r(s,s^{\prime})$ and the expected
reward received after taking action $a$ in state $s$ as $r(s,a)$. A
deterministic policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$ maps states to
actions. Given a policy, we can define a state value function, which is equal
to

$V^{\pi}(s):=\operatorname{\mathbb{E}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},\pi(s_{t}))|s_{0}=s\right]$

in discounted infinite horizon reward criteria and

$V^{\pi}(s):=\lim_{T\rightarrow\infty}\frac{1}{T}\operatorname{\mathbb{E}}\left[\sum_{t=0}^{T}r(s_{t},\pi(s_{t}))|s_{0}=s\right]$

in average total reward criteria.

A policy $\pi^{*}$ is called optimal if it maximizes the values of all states.
A policy $\pi^{\epsilon}$ is called $\epsilon$-optimal if the state values
implied by $\pi$ differ from the optimal state values by less than a positive
real number $\epsilon$:

$V^{*}(s)-V^{\pi}(s)\leq\epsilon,\forall s\in\mathcal{S}.$

The Value Iteration Algorithm 1 is one of the algorithms used to find an
$\epsilon$-optimal policy. The pseudocode presents a general version of the
algorithm, and in the paper, we analyze three versions of it:

  * •

Synchronous without learning rate (classical value iteration algorithm):
$\alpha=1$ and every action is updated at every step,
$\mathcal{S}{t}=\mathcal{S};\forall t$.

  * •

Synchronous with learning rate: $\alpha\in(0,1)$ and every action is updated
at every step, $\mathcal{S}{t}=\mathcal{S};\forall t$.

  * •

Asynchronous with learning rate: $\alpha\in(0,1)$ and the set of actions
updated at each step is different.

The choice of stopping criteria $H$ depends on the reward criteria. We aim to
show that under the assumption that the Markov Reward process implied by the
optimal policy is irreducible and aperiodic, all algorithms exhibit geometric
convergence with a rate smaller than the discount factor $\gamma$.

In our analysis, we show convergence in terms of the span of an error vector
$\text{span}(e)$, which is a vector of differences between current values $V$
and optimal values $V^{*}$:

$\textrm{sp}(e)=\max{(e)}-\min{(e)},\quad e=V-V^{*}.$

##  3 Main results

###  3.1 Classical algorithm

######  Assumption 3.1.

The MRP implied by optimal policy $\pi^{*}$ is irreducible and aperiodic.

######  Assumption 3.2.

Uniqueness of optimal policy: For every state $s$ there exist only one optimal
action $\pi^{*}(s)$. Any other action $a^{\prime}$ is worse than $a^{*}$ by at
least $\delta$:

$r(s,\pi^{*}(s))+\gamma\sum_{s^{\prime}}P(s^{\prime}|s,\pi^{*}(s))V^{*}(s^{\prime})-r(s,a^{\prime})-\gamma\sum_{s^{\prime}}P(s^{\prime}|s,a^{\prime})V^{*}(s^{\prime})\geq\delta,\forall
s,a^{\prime}\neq\pi^{*}(s)$

In the theorem presented, we demonstrate that under the previously stated
assumptions, a limited number of iterations of the value iteration algorithm
is sufficient to ensure enhanced convergence by a factor of $\tau\in(0,1)$.
The exact number of iterations required, denoted as $N$, is determined by the
need to ensure mixing by the stochastic matrix $P^{*}$. This number can be
upper-bounded by $n^{2}-2n+2$, as outlined in the subsequent lemma:

######  Lemma 3.3.

For every irreducible and aperiodic stochastic matrix $A$, all elements of a
matrix $A^{n^{2}-2n+2}$ are strictly positive.

###### Proof.

This fact is stated in [2]. ∎

######  Theorem 3.4.

Convergence of the Synchronous algorithm without a learning rate: If
Assumptions 3.1 and 3.2 hold, span of the error vector obtained after $N$
steps of synchronous Value Iteration algorithm has the following property:

$\textrm{sp}(e_{N})\leq\gamma^{N}\tau\textrm{sp}(e_{0}),$

where $\tau\in(0,1)$.

###### Proof.

The proof is given in Subsection 4.2. ∎

The convergence of the span of the error vector, as implied by Theorem 3.4, is
sufficient to achieve an $\epsilon$-optimal policy with the rate faster than
$\gamma$. This can be demonstrated with the assistance of the following lemma.

######  Lemma 3.5.

For the consecutive value vectors $V_{t}$ and $V_{t+1}$ the following
inequality holds:

$\textrm{sp}(V_{t}-V_{t+1})\leq\textrm{sp}(e_{t})(1+\gamma)$ (1)

###### Proof.

We denote two states where vector $e_{t}$ reaches its maximum and minimum as
$\overline{s}$ and $\underline{s}$. In addition, we denote two states
corresponding to the maximum and minimum entries of vector $e_{t+1}$ as
$\overline{s}^{\prime}$ and $\underline{s}^{\prime}$. Then,

$\displaystyle\textrm{sp}(V_{t}-V_{t+1})$
$\displaystyle=\textrm{sp}(e_{t}-e_{t+1})=\max_{s}(e_{t}(s)-e_{t+1}(s))-\min_{s}(e_{t}(s)-e_{t+1}(s))\leq$
$\displaystyle\leq(e_{t}(\overline{s})-e_{t+1}(\underline{s}^{\prime}))-(e_{t}(\underline{s})-e_{t+1}(\overline{s}^{\prime}))=\textrm{sp}(e_{t})+\textrm{sp}(e_{t+1})\leq$
$\displaystyle\leq(1+\gamma)\textrm{sp}(e_{t})$

∎

Having Lemma 3.5 we can derive convergence time of this version of the
algorithm for both discounted reward criteria and average reward criteria.

######  Corollary 3.6.

In discounted reward criteria case set the algorithm stopping criteria $H$
equal to $\frac{\epsilon(1-\gamma)}{\gamma}$, synchronous Value iteration
algorithm without learning rate will output $\epsilon$-optimal policy after at
most:

$\frac{\log{1/\epsilon}+\log{1-\gamma}-\log
4-\log{\textrm{sp}(e_{0})}}{\log\gamma+\log{(1/\tau)}/N}$

iterations, which results in total iteration complexity of

$\mathcal{O}\left(\frac{\log{(1/\epsilon)}+\log{(1-\gamma)}}{\log{(1/\gamma)}+\log{(1/\tau)}/N}\right).$
(2)

###### Proof.

From Lemma 3.5 it follows that
$\textrm{sp}(e_{t})<\frac{\epsilon(1-\gamma)}{\gamma(1+\gamma)}$ guarantees
that algorithm stopping criteria is satisfied. Proposition 6.6.5 from [3]
guarantees that policy produced by this values is $\epsilon$-optimal. From
Theorem 3.4 we know that after $t$ iterations span of an error vector $e_{t}$
might be upper bounded by:

$\textrm{sp}(e_{t})\leq\gamma^{t}\tau^{\lfloor t/N\rfloor}\textrm{sp}(e_{0}).$

Therefore, after number of iterations specified in Equation 2
$\textrm{sp}(e_{t})$ is small enough, so that $\textrm{sp}(e_{t+1}-e_{t})$
satisfies $\epsilon$-optimal policy criteria.

∎

######  Corollary 3.7.

In average reward criteria case set the algorithm stopping criteria $H$ equal
to $\epsilon$, synchronous Value iteration algorithm without learning rate
will output $\epsilon$-optimal policy after at most:

$\frac{\log{1/\epsilon}+\log 2-\log{\textrm{sp}(e_{0})}}{\log{(1/\tau)}/N}$

iterations, which results in total iteration complexity of

$\mathcal{O}\left(\frac{\log{(1/\epsilon)}}{\log{(1/\tau)}/N}\right).$ (3)

###### Proof.

Proof is similar to the proof of Corollary 3.6, except it uses Theorem 8.5.7
from [3], which states that once criteria
$\textrm{sp}(e_{t+1}-e_{t})<\epsilon$ is met the policy produced by $V_{t+1}$
is $\epsilon$-optimal. ∎

Note, that both stopping criteria $\frac{\epsilon(1-\gamma)}{\gamma}$ in
discounted reward MDP and $\epsilon$ in average total reward MDP do not depend
on values of $N$ and $\tau$, which are unknown during the run of the
algorithm. Therefore, we take an advantage of the extra convergence factor
$\log{(\tau)}/N$ even not knowing its exact value.

###  3.2 Synchronous with learning rate

As we can see from Subsection 3.1, there are two main sources of error vector
span convergence: it is shrinking by discount factor $\gamma$ and reverts to
the mean due to mixing properties of the stochastic matrix $P_{t}^{\prime}$.
In this section we show that by adding learning rate we introduce a trade off
between these two sources of convergence: by increasing learning rate part of
part of $\gamma$ convergence is being "sacrificed" to provide faster
information exchange between states and bolster the mean reversion.

One immediate result of introducing the learning rate is that now it is
guaranteed, that under MRP produced by optimal policy a number of updates
$N_{\alpha}$ required to guarantee that every state affects every other state
is at most $n-1$.

######  Theorem 3.8.

Convergence of the Synchronous algorithm with a learning rate: If Assumptions
3.1 and 3.2 hold, span of the error vector obtained after $n$ steps of
synchronous Value Iteration algorithm with learning rate $\alpha\in(0,1)$ has
the following property:

$\textrm{sp}(e_{N_{\alpha}})\leq\gamma^{N_{\alpha}}\tau_{\alpha}\textrm{sp}(e_{0}),$

where $\gamma^{N_{\alpha}}\tau_{\alpha}\in(0,1)$.

###### Proof.

Proof of this theorem is similar to the proof of Theorem 3.4. Full version of
the proof is given in Appendix A.1. ∎

Having this theorem we can state two convergence Corollaries analogous to
Colloraries in previous section wit identical proofs.

######  Corollary 3.9.

In discounted reward criteria case set the algorithm stopping criteria $H$
equal to $\frac{\epsilon(1-\gamma)}{\gamma}$. Then synchronous Value iteration
algorithm with learning rate will output $\epsilon$-optimal policy after at
most:

$\frac{\log{1/\epsilon}+\log{1-\gamma}-\log
4-\log{\textrm{sp}(e_{0})}}{\log\gamma+\log{(1/\tau_{\alpha})}/N_{\alpha}}$

iterations, which results in total iteration complexity of

$\mathcal{O}\left(\frac{\log{(1/\epsilon)}+\log{(1-\gamma)}}{\log{(1/\gamma)}+\log{(1/\tau_{\alpha})}/N_{\alpha}}\right).$
(4)

######  Corollary 3.10.

In average reward criteria case set the algorithm stopping criteria $H$ equal
to $\epsilon$. Then synchronous Value iteration algorithm with learning rate
will output $\epsilon$-optimal policy after at most:

$\frac{\log{1/\epsilon}+\log
2-\log{\textrm{sp}(e_{0})}}{\log{(1/\tau_{\alpha})}/N_{\alpha}}$

iterations, which results in total iteration complexity of

$\mathcal{O}\left(\frac{\log{(1/\epsilon)}}{\log{(1/\tau_{\alpha})}/N_{\alpha}}\right).$
(5)

###  3.3 Asynchronous with learning rate

The convergence analysis of asynchronous algorithm is harder than previous
cases due to its dependence on choices of states $\mathcal{S}_{t}$ every
iteration. For the algorithm to converge we need to guarantee meaningful
choice strategy. Otherwise, for example when only a few states being updated
infinite number of times, while others are not being updated at all,
convergence cannot be achieved. To guarantee proper state selection we make a
following assumption:

######  Assumption 3.11.

There exists a natural number $B$ such that during every $B$ updates every
state is being updated at least $n$ times.

Also, if in the synchronous update case contraction factor $\gamma$ being
applied to all states simultaneously and, thus, decreases a span of a error
vector, in asynchronous case it might be increasing, if algorithm prioritize
choice of some states compare to others. Thus, two factors,
$\gamma$-contraction and mean reversion via information exchange, which
previously were both contributing to faster convergence, now might work in
opposite direction: due to unbalanced application of the updates,
$\gamma$-contraction might increase the span of the error vector. In this case
dynamics of error vector span might be described by the following theorem:

######  Theorem 3.12.

Convergence of the Asynchronous algorithm with a learning rate: If Assumptions
3.1, 3.2 and 3.11 hold, span of the error vector obtained after $B$ steps of
asynchronous Value Iteration algorithm with learning rate $\alpha\in(0,1)$ has
the following property:

$\textrm{sp}(e_{B})\leq\gamma^{N}\tau^{\prime}\textrm{sp}(e_{0})+(1-\gamma^{B})\min(e_{0}),$

where $\gamma^{N}\tau^{\prime}\in(0,1)$.

This Theorem immediately gives a convergence result in average reward case
stated in the following corollary.

######  Corollary 3.13.

In average reward criteria case set the algorithm stopping criteria $H$ equal
to $\epsilon$. Then asynchronous Value iteration algorithm with learning rate
will output $\epsilon$-optimal policy after at most:

$\frac{\log{1/\epsilon}+\log
2-\log{\textrm{sp}(e_{0})}}{\log{(1/\tau_{\alpha}^{\prime})}/B_{\alpha}}$

iterations, which results in total iteration complexity of

$\mathcal{O}\left(\frac{\log{(1/\epsilon)}}{\log{(1/\tau_{\alpha}^{\prime})}/B_{\alpha}}\right).$
(6)

At the same time, the term $(1-\gamma^{B})\min(e_{0})$ does not allow to
establish the convergence guarantees in discounted case using the same proof
strategy.

##  4 Proofs

###  4.1 Key idea of the proofs

Let’s analyze a single update on a single state value.

$\displaystyle v_{t+1}(s)$
$\displaystyle=v^{*}(s)+e_{t+1}(s)=r(s,\pi_{t}(s))+\gamma\sum_{s^{\prime}}P_{t}(s,s^{\prime})v_{t}(s^{\prime})$
$\displaystyle=r(s,\pi_{t}(s))+\gamma\sum_{s^{\prime}}P_{t}(s,s^{\prime})(v^{*}(s^{\prime})+e_{t}(s^{\prime}))$
$\displaystyle=r(s,\pi_{t}(s))+\gamma\sum_{s^{\prime}}P^{*}(s,s^{\prime})v^{*}(s^{\prime})+r(s,\pi^{*}(s))-r(s,\pi^{*}(s))$
$\displaystyle+\gamma\left(\sum_{s^{\prime}}P_{t}(s,s^{\prime})v^{*}(s^{\prime})-\sum_{s^{\prime}}P^{*}(s,s^{\prime})v^{*}(s^{\prime})\right)+\gamma\sum_{s^{\prime}}P_{t}(s,s^{\prime})e_{t}(s^{\prime})$
$\displaystyle=v^{*}(s)+\gamma\sum_{s^{\prime}}P_{t}(s,s^{\prime})e_{t}(s^{\prime})+$
$\displaystyle\underbrace{r(s,\pi_{t}(s))-r(s,\pi^{*}(s))+\gamma\left(\sum_{s^{\prime}}P_{t}(s,s^{\prime})v^{*}(s^{\prime})-\sum_{s^{\prime}}P^{*}(s,s^{\prime})v^{*}(s^{\prime})\right)}_{\Delta(a)}$
$\displaystyle\implies
e_{t+1}(s)\leq\gamma\sum_{s^{\prime}}P_{t}(s,s^{\prime})e_{t}(s^{\prime})$ (7)

with the equality achieved when action $a=\pi_{t}(s)=\pi^{*}(s)$. Note, that
the term $\Delta(a)$ corresponds to the loss caused by one time choice of
action $a$ instead of optimal action in state $s$, in the recent literature it
is called an advantage of policy $\pi_{t}$ to $\pi^{*}$. The inequality
carries the ideas of convergence of error vector span. Firstly, because non-
increasing and non-decreasing properties of stochastic matrix, span will be
contracting by $\gamma$ each iteration (if $\gamma<1$). Secondly, the
convergence will follow from mixing properties of matrix $P^{*}$ if the
optimal action is chosen and from additional term $\Delta(a)\geq\delta$
otherwise.

###  4.2 Proof of Theorem 3.4

First, we derive a lower bound for a new error vector:

$\displaystyle v_{t+1}(s)$
$\displaystyle=v^{*}(s)+e_{t+1}(s)=r(s,\pi_{t}(a))+\gamma\sum_{s^{\prime}}P_{t}(s,s^{\prime})v_{t}(s^{\prime})$
$\displaystyle\geq
r(s,\pi^{*}(s))+\gamma\sum_{s^{\prime}}P^{*}(s,s^{\prime})v_{t}(s^{\prime})$
$\displaystyle=r(s,\pi^{*}(s))+\gamma\sum_{s^{\prime}}P^{*}(s,s^{\prime})(v^{*}(s^{\prime})+e_{t}(s^{\prime}))$
$\displaystyle=r(s,\pi^{*}(s))+\gamma\sum_{s^{\prime}}P^{*}(s,s^{\prime})v^{*}(s^{\prime})+\gamma\sum_{s^{\prime}}P^{*}(s,s^{\prime})e_{t}(s^{\prime})$
$\displaystyle\implies
e_{t+1}(s)\geq\gamma\sum_{s^{\prime}}P^{*}(s,s^{\prime})e_{t}(s^{\prime})$ (8)

Combining Inequalities 4.2 and 4.1 and them rewriting in matrix form we yield:

$\displaystyle\gamma P^{*}e_{t}\leq e_{t+1}\leq\gamma P_{t}e_{t}$ (9)

Since all elements of $e_{t+1}$ lie between two quantities, it might be
written as a convex combination of those quantities, or:

$\displaystyle e_{t+1}=\gamma[D_{t}P^{*}+(I-D_{t})P_{t}]e_{t}=\gamma
P_{t}^{\prime}e_{t},$ (10)

where $D_{t}$ is a diagonal matrix. We now analyze diagonal entries of
$D_{t}$. As it was shown in Subsection 4.1, in the case when for state $s_{i}$
vector $v_{i}$ implies an optimal actions (thus, $P^{*}e_{t}=P_{t}e_{t}$), we
choose $D_{t}(i,i)=1$. In the other case, recall that the second inequality is
strict only when action choice is optimal, otherwise value of $e_{t+1}(s_{i})$
will be smaller by at least $\delta$:

$e_{t+1}(s_{i})\leq\gamma\sum_{s^{\prime}}P^{*}(s,s^{\prime})e_{t}(s^{\prime})-\gamma\delta,$

which, in turn, implies that the value of $D_{t}(i,i)$ cannot be zero. We can
derive the lower bound on it as (for simplicity we denote
$\sum_{s^{\prime}}P(s,s^{\prime})e_{t}(s^{\prime})$ as $P(s)e_{t}$ for any
transition matrix $P$):

$\displaystyle\begin{rcases}e_{t+1}(s)=\gamma(D_{t}(i,i)P^{*}(s)e_{t}+(1-D_{t}(i,i))P_{t}(s)e_{t})\\\
e_{t+1}(s_{i})\leq\gamma P_{t}(s)e_{t}-\gamma\delta\end{rcases}\implies$
$\displaystyle
D_{t}(i,i)\gamma(P_{t}(s)e_{t}-P^{*}(s)e_{t})\geq\gamma\delta\implies$
$\displaystyle\forall
t,i:D_{t}(i,i)\geq\frac{\delta}{P_{t}(s)e_{t}-P^{*}(s)e_{t}}\geq\frac{\delta}{\textrm{sp}(e_{t})}\geq\frac{\delta}{\textrm{sp}(e_{0})}$

Having the bound on $D_{t}(i,i)$ we can establish that for any two states
$s,s^{\prime}$ if the transition under optimal policy has non-zero probability
$P^{*}(s,s^{\prime})$, this transition will also have non-zero probability in
matrix $P^{\prime}$:

$\displaystyle P_{t}^{\prime}(s,s^{\prime})\geq\frac{\delta(1-\gamma)}{r_{\rm
max}-r_{\rm min}}\min_{s,s^{\prime}}(P^{*}(s,s^{\prime}))=\delta^{\prime}.$
(11)

Thus, the result of $N$ steps of value iteration algorithm in terms of error
vector might be expressed as:

$e_{N}=\gamma^{N}P_{N}^{\prime}P_{N-1}^{\prime}\dots P_{1}^{\prime}e_{0}.$

Every entry of $e_{N}(s)$ might be expressed as convex combination of entries
of $e_{0}$ (we denote coefficients $\lambda$), where each coefficient
$\lambda_{s^{\prime}}$ represents a sum of probabilities of patches $u$ from
state $s^{\prime}$ to $s$ of length $N$, denoted as $U_{N}(s^{\prime},s)$.
Since the matrix $P^{*N}$ is positive, for any two states $s_{i},s_{j}$ there
exists at least one path $u_{ij}:(s_{i},s_{u_{1}},\dots,s_{u_{N-1}},s_{j})$ of
length $N$, such that of any of two consecutive entries $s_{p_{i}}$ and
$s_{p_{i+1}}$ the transition from first to second will have non-zero
probability, i.e. $P^{*}(s_{p_{i}},s_{p_{i+1}})>0$. Therefore,

$\displaystyle e_{N}(s)=$
$\displaystyle\gamma^{N}\sum_{s^{\prime}\in\mathcal{S}}\lambda_{s^{\prime}}e_{0}(s^{\prime})=\gamma^{N}\sum_{s^{\prime}\in\mathcal{S}}\left(\sum_{u\in
U_{N}(s^{\prime},s)}P(u)\right)e_{0}(s^{\prime})=$
$\displaystyle\gamma^{N}\sum_{s^{\prime}\in\mathcal{S}}\left(\sum_{u\in
U_{N}(s^{\prime},s)}\prod_{i=0}^{N-1}P_{i+1}^{\prime}(s_{u_{i}},s_{u_{i+1}})\right)e_{0}(s^{\prime})$

Earlier we established two facts: that for every state $s^{\prime}$ a paths of
length $N$ from $s^{\prime}$ to $s$, i.e.
$\prod_{i=1}^{N}P^{*}(s_{u_{i}},s_{u_{i+1}})>0$. The second fact is that for
any two states $s,s^{\prime}$ and time step $t$,
$P^{*}(s,s^{\prime})>0\implies
P_{t}^{\prime}(s,s^{\prime})\geq\delta^{\prime}$. Combining these facts
together we have that every coefficient
$\lambda_{s^{\prime}}\geq\delta^{\prime N}$. Thus we can rewrite the error
representation as:

$\displaystyle e_{N}(s)$
$\displaystyle=\gamma^{N}\sum_{s^{\prime}\in\mathcal{S}}\lambda_{s^{\prime}}e_{0}(s^{\prime})=\gamma^{N}\sum_{s^{\prime}\in\mathcal{S}}\delta^{\prime
N}e_{0}(s^{\prime})+(\lambda_{s^{\prime}}-\delta^{\prime
N})e_{0}(s^{\prime})=$ $\displaystyle=\gamma^{N}n\delta^{\prime
N}\overline{e}_{0}+\gamma\sum_{s^{\prime}\in\mathcal{S}}(\lambda_{s^{\prime}}-\delta^{\prime
N})e_{0}(s^{\prime}),$

where $\overline{e}_{0}$ denotes the mean of vector $e_{0}$. This implies

$\displaystyle\gamma^{N}(n\delta^{\prime N}\overline{e}_{0}+(1-n\delta^{\prime
N})\min(e_{0}))\leq e_{N}(s)\leq\gamma^{N}(n\delta^{\prime
N}\overline{e}_{0}+(1-n\delta^{\prime N})\max(e_{0}))\implies$
$\displaystyle\textrm{sp}(e_{N})\leq\gamma^{N}(1-n\delta^{\prime
N})\max(e_{0})-\gamma^{N}(1-n\delta^{\prime
N})\min(e_{0})=\gamma^{N}(1-n\delta^{\prime N})\textrm{sp}(e_{0})$

Defining $\tau=(1-n\delta^{\prime N})$ concludes the proof. Q.E.D.

##  5 Conclusion

In this paper, we analyzed the convergence of the Value Iteration algorithm.
We show that under the assumption of sufficient mixing provided by the optimal
policy, the Value Iteration algorithm exhibits geometric convergence at a rate
faster than the discount factor $\gamma$.

## References

  * [1] Eugene A Feinberg and Gaojin He  “Complexity bounds for approximately solving discounted MDPs by value iterations”  In _Operations Research Letters_ 48.5 Elsevier, 2020, pp. 543–548
  * [2] John C Holladay and Richard S Varga  “On powers of non-negative matrices”  In _Proceedings of the American Mathematical Society_ 9.4, 1958, pp. 631–634
  * [3] Martin L Puterman  “Markov decision processes: discrete stochastic dynamic programming”  John Wiley & Sons, 2014

##  Appendix A Theorem proofs

###  A.1 Proof of Theorem 3.8

With learning rate introduced one iteration of the algorithm is:

$V_{t+1}(s)\leftarrow
V_{t}(s)(1-\alpha)+\alpha\max_{a}\left[r(s,a)+\gamma\sum_{s^{\prime}}P(s^{\prime}|s,a)V_{t}(s^{\prime})\right]$

and error transition dynamics equality similar to 10 becomes:

$\displaystyle
e_{t+1}=\big{(}(1-\alpha)I+\gamma\alpha[D_{t}P^{*}+(I-D_{t})P_{t}]\big{)}e_{t}=\gamma
P_{t,\alpha}^{\prime}e_{t},$ (12)

Note that $P_{t,\alpha}^{\prime}$ is a stochastic matrix only in a case when
$\gamma=1$, but it is sufficiently close to it since we assume that $\gamma$
is almost $1$. Note, that now we actually need only $N_{\alpha}=n-1$ updates
to guarantee that the matrix $P_{t,\alpha}^{\prime N}$ is positive, since
elements on the main diagonal coming from $(1-\alpha)/\gamma I$ influence
error dynamics the similar way as having a loop in every state, thus every
state will be affected by every other state in at most $n-1$. Consequently,
the minimum values of $\delta^{\prime}$ needs to be updated, now we have that
$P_{t,\alpha}^{\prime}(s,s^{\prime})\geq\alpha\delta^{\prime}$ for states
$s,s^{\prime}:s\neq s^{\prime}$ and
$P_{t,\alpha}^{\prime}(s,s)\geq(1-\alpha)\gamma$. Let’s define
$\delta^{\prime}_{\alpha}$ as a minimum of these two quantities. Thus, an
expression of the of an error associated with state $s$ after $N$ iterations
becomes:

$\displaystyle e_{N}(s)$
$\displaystyle=\gamma^{N}\sum_{s^{\prime}\in\mathcal{S}}\lambda_{s^{\prime}}e_{0}(s^{\prime})=\gamma^{N}\sum_{s^{\prime}\in\mathcal{S}}\delta^{{}^{\prime}N}_{\alpha}e_{0}(s^{\prime})+(\lambda_{s^{\prime}}-\delta^{{}^{\prime}N}_{\alpha})e_{0}(s^{\prime})=$
$\displaystyle=\gamma^{N}n\delta^{{}^{\prime}N}_{\alpha}\overline{e}_{0}+\gamma^{N}\sum_{s^{\prime}\in\mathcal{S}}(\lambda_{s^{\prime}}-\delta^{{}^{\prime}N}_{\alpha})e_{0}(s^{\prime}),$

Note, that now the sum of coefficients $\lambda_{s^{\prime}}$ is not $1$, but
$[(1-\alpha)/\gamma+\alpha]^{N}$. This gives us a final convergence rate of:

$\textrm{sp}(e_{N})\leq\gamma^{N}([(1-\alpha)/\gamma+\alpha]^{N}-n\delta_{\alpha}^{{}^{\prime}N})\textrm{sp}(e_{0})$

Defining $([(1-\alpha)/\gamma+\alpha]^{N}-n\delta_{\alpha}^{{}^{\prime}N})$ as
$\tau_{\alpha}$ we have the claimed result.