11institutetext: Knowledge Media Institute, The Open University, Milton
Keynes, United Kingdom
11email<EMAIL_ADDRESS>
# Ontology Extraction and Usage in the Scholarly Knowledge Domain††thanks: We
would like to thank Springer Nature for partially funding this research.

Angelo A. Salatino  0000-0002-4763-3943 Francesco Osborne  0000-0001-6557-3131
Enrico Motta  0000-0003-0015-1952

###### Abstract

Ontologies of research areas have been proven to be useful resources for
analysing and making sense of scholarly data. In this chapter, we present the
Computer Science Ontology (CSO), which is the largest ontology of research
areas in the field, and discuss a number of applications that build on CSO to
support high-level tasks, such as topic classification, metadata extraction,
and recommendation of books.

###### Keywords:

Scholarly Data Ontology Learning Bibliographic Data Scholarly Ontologies.

##  1 Introduction

Ontologies, as formal specifications of concepts and relations in specific
domains, have become a standard solution to represent domain knowledge,
integrate data from different sources, and support a variety of semantic
applications [7, 10]. In the field of scholarly knowledge, ontologies are used
to facilitate the integration of large datasets of research data [11], the
exploration of the academic landscape [18, 9], information extraction from
scientific articles [8], and so on. More specifically, ontologies representing
research topics and describing their relationships, have been employed in
several tasks, such as making sense of research dynamics [18], classifying
research publications [25], characterising [2] and identifying [21] research
communities, studying the origin of research topics [23], and forecasting
research trends [24]. However, not every domain of science has an ontology
that comprehensively describes all research concepts and their relations. In
addition, ontologies describing research topics are typically manually crafted
by domain experts which is a very time consuming process. Therefore, they
usually evolve slow and become quickly outdated. A further issue is that many
of these ontologies tend to be very coarse-grained, lacking the right depth
that would allow them to comprehensively describe the area. All these
limitations hinder the adoption of semantic technologies in several fields of
science.

The question we are left with is: how do we effectively extract comprehensive,
fine-grained, and up-to-date ontologies of research topics that can support a
range of intelligent services?

In this chapter, we present the Computer Science Ontology (CSO) Framework [27,
26], which is a conceptual framework for generating a large scale ontology of
Computer Science. This solution has been used to support a variety of high-
level tasks, such as (i) categorising proceedings in digital libraries, (ii)
enhancing semantically the metadata of scientific publications, (iii)
generating recommendations, (iv) producing smart analytics, (v) detecting
research trends, and others [20, 27]. Figure 1 shows the architecture of the
framework, where each layer exploits the underneath layers.

Figure 1:  The Computer Science Ontology Framework.

The first layer is the corpus of research papers. This represent the core
input data from which we want to extract a granular and data-driven ontology
of research areas.

Sitting on top of the data layer, we find the Klink-2 algorithm [17] that
generates the large-scale ontology of research topics from publication
metadata. The Computer Science Ontology (CSO), which represents the third
layer, is a large-scale, granular, and automatically generated ontology of
research areas. The current version includes about 14K topics and 163K
semantic relationships. At the fourth layer, we find the CSO Classifier [25],
a tool for automatically classifying research papers according to the topics
available in the Computer Science Ontology. This system enables users to
represent scientific publications in terms of CSO concepts and allows all
relevant stakeholders to develop a multitude of relevant smart
functionalities.

The rest of the chapter is organised as follows. In Section 2, we review the
literature regarding topic detection in research papers, pointing out the
existing gap. In Section 3, we describe the Klink-2 algorithm for generating
the ontology, and in Sections 4 we discuss CSO with its data model. In Section
5 we describe the CSO Classifier and in Section 6 we show in more detail some
high-level applications that allowed us to perform smart analytics on
scholarly data. Finally, in Section 7 we summarise the main conclusions and
outline future directions of research.

##  2 Literature Review

Some fields of research are comprehensively described by ontologies of
research areas, e.g., MeSH in Biology and PhySH in Physics. These ontologies
can provide support toward a multitude of tasks, such as integrating
heterogeneous datasets [11], assisting users in exploring digital libraries
[18], producing scholarly analytics [3], and forecasting research dynamics
[24, 20]. In this section, we will review the current state of the art with
regards to developing and using ontologies of research areas. In particular,
we will first provide an overview of some of most well-known ontologies of
research areas, then we will discuss current approaches for the generation of
these ontologies, and finally, we will describe the approaches that take
advantage of such ontologies to perform several high-level tasks.

###  2.1 Ontologies of research areas

In literature, we can find different ontologies of research areas, which are
scoped to a particular branch of science. In the field of Computer Science,
the most well-known taxonomy is the ACM Computing Classification System111ACM
Computing Classif. System - https://www.acm.org/publications/class-2012,
developed and maintained by the Association for Computing Machinery (ACM).
This taxonomy contains around 2K concepts and it is manually curated. These
characteristics represent a limitation as its representation of the field
lacks both depth and breadth, and its curation process is slow and expensive.

In the field of Medicine, the most popular solution is the Medical Subject
Heading (MeSH)222Medical Subject Heading - https://www.ncbi.nlm.nih.gov/mesh
maintained by the National Library of Medicine of the United States. This
taxonomy is constantly updated by collecting new terms as they appear in the
scientific literature.

The Physics Subject Headings (PhySH)333Physics Subject Headings -
https://physh.aps.org/ is the standard solution in the field of Physics and
Astronomy. It is developed by the American Physical Society (APS) and it is
constantly updated with the support of authors, reviewers, editors and
organisers of scientific conferences.

In the field of Mathematics there is the Mathematics Subject Classification
(MSC)444Mathematics Subject Classification - https://mathscinet.ams.org/msc
which is maintained by Mathematical Reviews and zbMATH. In the field of
Economics we can find the JEL classification555Journal of Economic Literature
- https://www.aeaweb.org/econlit/jelCodes.php, created by the Journal of
Economic Literature of the American Economic Association, and the STW
Thesaurus for Economics666STW Thesaurus for Economics - http://zbw.eu/stw/
developed by ZBW - Leibniz Information Centre for Economics.

The ontologies mentioned above can comprehensively represent specific areas of
science. However, in literature we can also find more broad ontologies
covering a multitude of fields. The most popular ones are the Library of
Congress Classification and the Dewey Decimal Classification which encompass
many areas of science. Indeed, these two schemes are employed to classify
books within large academic libraries, globally.

Another ontology of research areas in the Fields of Research (FoR) which is
developed by the Australian Bureau of Statistics, New Zealand Ministry of
Business, Innovation, and Employment, and other partners. This scheme covers
many areas of science and indeed it is currently adopted by
Dimensions.ai777Dimensions.ai - https://www.dimensions.ai, a company that
provides commercial solutions to support users in exploring the research
landscape.

A common issue of these ontologies is that, being manually crafted and
maintained by domain experts, they tend to evolve relatively slow and became
quickly outdated. To keep-up with the pace of the constant evolution of the
research landscape, some institutions (e.g., the American Physical Society)
are crowd-sourcing their classification scheme. However, crowd-sourcing
strategies suffer from limitations, such as trust and reliability [5]. Indeed,
those institutions need to entrust a committee to moderate such amendments to
the classification scheme.

###  2.2 Automatic extraction of ontologies from scholarly data

A new strategy which is becoming increasingly popular is the automatic or
semi-automatic generation of ontologies of research topics using data-driven
methodologies. In the state of the art we can find a variety of approaches
that allow us to learn ontologies using clustering techniques, natural
language processing, statistical methods and others.

TaxGen [14] is an approach for the automatic generation of taxonomies from a
corpus using both hierarchical agglomerative clustering algorithm and text
mining techniques. The algorithm, in a bottom-up fashion, first identifies the
bottom clusters by observing the linguistic features in the documents, such as
co-occurrences of words, domain terms, names of people, organisations and
other significant words from text. Then the clusters are merged creating
higher-level clusters, which form the hierarchy.

Text2Onto [4] is another approach for learning ontologies from a collection of
documents. This approach identifies sub-/superclass hierarchies, synonyms, and
other linguistic features through the application of natural language
processing techniques on the sentence structure, where phrases like “such as…”
and “and other…” imply a hierarchy between terms. This method presents some
similarities with the Klink-2 algorithm [17], which we will describe later,
but requires the full text of documents.

Sanderson et al. [28] developed an approach for automatically deriving a
hierarchical organisation of concepts from a set of documents without use of
training data. Their approach computes the conditional probability for a
keyword to be associated with another based on their co-occurrence. Given a
pair of keywords, this system tries to understand whether there is a
subsumption relationship between them, according to certain heuristics.

In literature, we can also find semi-automatic approaches that take advantage
of external knowledge, either from pre-existing taxonomies or sourced by the
community. For instance, Shen et al. [30] developed the Fields of Study (FoS)
taxonomy, currently in use within Microsoft Academic, in which the first two
levels are hand-crafted. Their approach is based on a variation of [28] and
automatically infers topics derived from Wikipedia. However, considering only
Wikipedia is a limitation as many research topics are not described there.
Conversely, Klink-2 considers both academic publications and external sources.
Another approach from Wohlgenannt et al. [32], combines human effort and
machine computation by crowd-sourcing the evaluation of an automatically
generated ontology with the aim of dynamically validating the extracted
relations. Klink-2 can benefit these systems by generating an accurate, large-
scale and up-to-date topic network.

##  3 Ontology Generation

An essential characteristic for ontologies of research areas is the
hierarchical description of branches and sub-branches for a given discipline.
Indeed, almost all ontologies mentioned above, e.g. MeSH, PhySH, ACM-CSS, are
structured like a taxonomy: from the most generic to the most specific topics.
In cases when there are different labels associated to the same topic, for
instance for acronyms or synonyms, the ontology needs to be modelled in a way
that can contain information about equivalences.

To this end, we designed the Klink-2 algorithm [17] that from a large corpus
of scholarly publications is able to automatically generate ontologies of
research areas, describing both hierarchical and equivalence relationships
between research topics.

The algorithm starts by comparing each keyword in input to all the other
keywords with which it shares at least n co-occurrences. In particular, it
infers the semantic relationship between topics x and y using three metrics:
i) $H_{R}(x,y)$, which uses a semantic variation of the subsumption method
[28] for measuring the intensity of a hierarchical relationship; ii)
$T_{R}(x,y)$, which uses temporal information to estimate the existence of a
hierarchical relationship; and iii) $S_{R}(x,y)$, which estimates the
similarity between two topics. The first two metrics are used to indicate
whether a topic is super-area of another one (superTopicOf) or that the
research outputs of one topic contributes to research of the other
(contributesTo). The last metric is used to infer equivalence relationships
between topics (relatedEquivalent).

$H_{R}(x,y)$ quantifies the hierarchical relationship between x and y
according to the following formula:

$H_{R}(x,y)=\left(\frac{I_{R}(x,y)}{I_{R}(x,x)}-\frac{I_{R}(y,x)}{I_{R}(y,y)}\right)\cdot
c_{R}(x,y)\cdot n(x,y)$ (1)

where $I_{R}(x,y)$ is the number of elements associated with both x and y
according to relation R (e.g., number of co-occurrences in research papers),
($\frac{I_{R}(x,y)}{I_{R}(x,x)}$) is the conditional probability that an
element associated with keyword x will be associated also with keyword y,
$n(x,y)$ defines the string similarity between the two topics using the
normalised Levenshtein distance, and finally $c_{R}(x,y)$ measures how similar
are the distributions of topics with which both topic x and y are co-
occurring, using cosine similarity.

$T_{R}(x,y)$ is a temporal version of $H_{R}(x,y)$, which weighs more the
information associated with the first years of x. It is useful to detect the
cases in which the relationship between two terms fades because their
association has become implicit (e.g., Artificial Intelligence and Machine
Learning). $T_{R}(x,y)$ is calculated using a variation of Eq. 1 in which
$I_{R}(x,y)$ is computed by weighting the intensity of the relationships in
each year according to the distance from the debut of x. The weight is
computed as $w(year,x)=(year-debut(x)+1)-\gamma$, with $\gamma>0$ ($\gamma=2$
in the prototype). Finally, $S_{R}(x,y)$ is used to assess the similarity of
two terms and is computed according to the following formula:

$S_{R}(x,y)=\frac{c_{R}(x,y)}{\max\left(c_{R}^{super}(x,y),c_{R}^{sib}(x,y)\right)+1}$
(2)

where $c_{R}^{super}(x,y)$ is the cosine similarity of the super topics of the
two terms in the taxonomy produced by previous iteration, and
$c_{R}^{sib}(x,y)$ is the cosine similarity of their siblings. A hierarchical
relationship between two topics is inferred when a sufficient number of
hierarchical indicators are above a threshold. An analysis of the
precision/recall trade-off associated with different thresholds is available
in [17]. The nature of the inferred relationship is assessed by Klink-2 using
a rule-based approach. In brief, if x is older, associated with more entities,
and the $T_{R}(x,y)$ indicators score higher, Klink-2 will infer a
superTopicOf relationship, otherwise a contributesTo one. Then, Klink-2
removes loops in the topic network, merges keywords linked by a
relatedEquivalent relationship, and splits ambiguous keywords associated to
multiple meanings (e.g., “Java”). The keywords produced in this step are added
to the initial set of keywords to be further analysed in the next iteration
and the while-loop is re-executed until there are no more keywords to be
processed.

Klink-2 filters the keywords considered too generic or not academic according
to a set of heuristics that take in consideration the frequency of a keyword
in various online sources and distribution of its co-occurrences [16]. Finally
it generates the RDF triples describing the ontology. For a more comprehensive
explanation of Klink-2, we refer the reader to Osborne at al. [17].

##  4 Computer Science Ontology

The Computer Science Ontology (CSO) is a large-scale, granular, and
automatically generated ontology of research areas. It was generated by
running the Klink-2 algorithm on the Rexplore dataset [18] containing 16
million publications in the field of Computer Science.

Currently CSO includes about 14K topics and 163K semantic relationships. The
main root is Computer Science; however, the ontology includes also a few
secondary roots, such as Linguistics, Geometry, Semantics, and so on. The CSO
data model888CSO data model - https://cso.kmi.open.ac.uk/schema/cso is an
extension of SKOS999SKOS Simple Knowledge Organization System -
http://www.w3.org/2004/02/skos. and it includes eight semantic relations:

  * •

relatedEquivalent, which is a subproperty of skos:related, indicates that two
topics can be treated as equivalent for the purpose of exploring research data
(e.g., Ontology Matching and Ontology Mapping).

  * •

superTopicOf, which is a subproperty of skos:narrower, indicates that a topic
is a super-area of another one (e.g., Semantic Web is a super-area of Linked
Data). The inverse of this relationship is subTopicOf.

  * •

contributesTo, which indicates that the research output of one topic
contributes to another. For instance, research in Ontology Engineering
contributes to Semantic Web, but arguably Ontology Engineering is not a sub-
area of Semantic Web, since there is plenty of research in Ontology
Engineering outside the Semantic Web area.

  * •

owl:sameAs, which is used for mapping CSO topics to equivaled entities in
other knowledge graphs (DBpedia101010DBpedia - https://wiki.dbpedia.org,
Freebase111111Freebase - https://en.wikipedia.org/wiki/Freebase,
Wikidata121212Wikidata - https://www.wikidata.org, YAGO131313Yago -
https://github.com/yago-naga/yago3, and Cyc141414Cyc - https://www.cyc.com).

  * •

schema:relatedLink, which links CSO concepts to relevant web pages that either
describe the research topics (Wikipedia articles) or provide additional
information about the research domains (Microsoft Academic).

  * •

preferentialEquivalent, which is used to state the main label for topics
belonging to a cluster of relatedEquivalent. For instance, the topics Ontology
Matching and Ontology Alignment both have their preferentialEquivalent set to
Ontology Matching. Similarly to relatedEquivalent, in our data model we
defined preferentialEquivalent as a subproperty of skos:related.

  * •

rdf:type, this relation is used to state that a resource is an instance of a
class. For example, a resource in our ontology is an instance of Topic, which
is a subclass of skos:Concept.

  * •

rdfs:label, this relation is used to provide a human-readable version of a
resource’s name.

In the previous section, we discussed how the Klink algorithm infers the first
three of these relationships: relatedEquivalent, superTopicOf, and
contributesTo. The rest of the relationships are also automatically generated.
In particular, the rdf:type and rdfs:label relations respectively identify all
topic entities and their labels. We generated the preferentialEquivalent
choosing, within a cluster of topics linked by a relatedEquivalent, the label
associated with most articles in the source corpus [18]. To generate the
owl:sameAs relationships, linking CSO concepts to equivalent entities in the
other KBs, we identified the DBpedia entities corresponding to CSO topics by
exploiting the DBpedia Spotlight API [12]. Then we extracted the links from
DBpedia to other KBs in the Linked Open Data (LOD) cloud by using the DBpedia
SPARQL endpoint.

We also generated schema:relatedLink relations toward external web pages
containing further information about the research topic. In particular, the
links between CSO concepts and Wikipedia articles were extracted from the
DBpedia. We also mapped the CSO topics to the Fields of Study (FoS) concepts
reseased by Microsoft Academic. More details regarding the alignment between
CSO and other knowledge bases are avaliable in Salatino et al. [26].

Figure 2:  Overview of the resource page related to the topic in a new
“semantic web”.

To facilitate the uptake of CSO we have developed the CSO Portal151515CSO
Portal - https://cso.kmi.open.ac.uk (see Fig. 2), a web application that
enables users to browse, download – in various formats161616This ontology is
licensed under a Creative Commons Attribution 4.0 International License (CC BY
4.0) - https://creativecommons.org/licenses/by/4.0.., e.g. N-Triples, OWL, TTL
and CSV – and provide granular feedback on CSO at different levels.

##  5 CSO Classifier

In order to facilitate users in integrating CSO in their pipelines, we
developed the CSO Classifier [25], a tool that automatically annotates
documents according to CSO. This application takes in input the metadata
associated with a research paper (title, abstract, and keywords) and returns a
selection of research concepts drawn from CSO. Figure 3 displays its workflow.

Figure 3:  Workflow of the CSO Classifier.

The CSO Classifier works in three steps. First, it finds all topics in the
ontology that are explicitly mentioned in the paper (syntactic module). Then
it identifies further semantically related topics by means of part-of-speech
tagging and word embeddings (semantic module). Finally, it enriches this set
by including the super-areas of these topics according to CSO.

In particular, the syntactic module removes English stop words and collects
unigrams, bigrams, and trigrams. Then, for each n-gram, it computes the
Levenshtein similarity with the labels of the topics in CSO. Finally, it
returns all research topics whose labels have similarity to one of the
n-grams, which is equal to or higher than a threshold.

The semantic module takes advantage of a pre-trained word embedding model
which captures semantic properties of words [13]. We trained this Word2Vec
model using titles and abstracts of 4,654,062 English publications in the
field of Computer Science from Microsoft Academic Graph, which is an
heterogeneous graph containing scientific publication records, citation
relationships, authors, institutions, journals, conferences, and fields of
study. We pre-processed this data by replacing spaces with underscores in all
n-grams matching the CSO topic labels (e.g., “semantic web” became
“semantic_web”) as well as for frequent bigrams and trigrams (e.g.,
“highest_accuracies”, “highly_cited_journals”). The latter were identified by
analysing collocations, i.e. combinations of words that co-occur together
[13]. This solution allows the CSO Classifier to better disambiguate concepts
and treat terms such as “deep_learning” and “e-learning” as completely
different words.

Specifically, to compute the semantic similarity between the terms in the
document and the CSO concepts, the semantic module uses part-of-speech tagging
to identify candidate terms composed by a combination of nouns and adjectives
and decomposes them into unigrams, bigrams, and trigrams. For each n-gram, it
retrieves its most similar words from the Word2Vec model. For this task, the
n-gram tokens are initially glued with an underscore, creating one single
word, e.g., “semantic_web”. If this word is not available within the model
vocabulary, the classifier uses the average of the embedding vectors of all
its tokens. Then, it computes the relevance score for each topic in the
ontology as the product between the number of times it was identified in those
n-grams (frequency) and the number of unique n-grams that led to it
(diversity). Finally, it uses the elbow method [29] for selecting the set of
most relevant topics. The CSO Classifier aggregates the topics returned by the
two modules and enriches them by inferring the list of all their super topics,
exploiting the superTopicOf relationship within CSO. For instance, given the
topic “Neural Networks”, it will infer “Machine Learning”, “Artificial
Intelligence”, and “Computer Science”. This feature allows us to capture both
high-level fields and very granular research areas, in order to generate a
comprehensive representation of the classified papers.

The latest release of the CSO Classifier can be installed via pip from PyPI:
pip install cso-classifier; or it simply downloading it from
https://github.com/angelosalatino/cso-classifier.

##  6 High-level applications

This section describes some high-level applications that take advantage of CSO
for supporting users in exploring, analysing, and making sense of large
corpora of research publications.

###  6.1 Exploring and making sense of scholarly data

Rexplore is a system to support users in exploring and making sense of
scholarly data [18]. It uses CSO to characterise research papers, authors, and
organisations according to research topics. An interesting feature available
in Rexplore is that it can plot a graph of researchers based on their topic
similarity, reflecting how similar two authors are with respect to their
research areas. Rexplore allows users to detect and make sense of important
trends in research, such as significant migrations of researchers from one
area to another, the emergence of new topics, the evolution of communities
within a particular area. It also provides powerful query/search facilities,
supporting complex multidimensional queries that can include logical
connectives, such as retrieving career-young authors who have worked in both
Semantic Web and Social Networks, and have published at the International
Semantic Web Conference.

The Rexplore system was shown to be able to support users in performing
specific tasks more effectively than Microsoft Academic Search (MAS), thanks
to its organic representation of research topics [18].

###  6.2 Automatic classification of conference proceedings

The Smart Topic Miner (STM) [22] is a web application that supports the
Springer Nature editorial team in classifying editorial products according to
a taxonomy of research topics drawn both from CSO and the Product Market Codes
(PMC), Springer Nature’s own editorial classification system. STM takes as
input the metadata associated with the proceedings of a conference (titles,
abstracts and author-provided keywords for each paper in the proceedings) and
returns the set of relevant CSO topics and PMCs as output.

STM uses the CSO Classifier to annotate each paper with the topics from CSO.
Then it groups and ranks the topics according to the number of papers
addressing them. Finally, it infers the relevant PMCs, using the mapping
between the CSO ontology and PMC. The editors then review the CSO topics and
the PMC categories and submit these annotations to the Springer Nature
production system. This outcome is displayed in the Springer Nature’s digital
library: SpringerLink; and included in the ONIX171717ONIX for Books -
https://bisg.org/page/ONIXforBooks metadata feeds, delivered to various
libraries and bookshops.

We released STM back in 2016, and since then it has been routinely used by the
editorial team to annotate all book series covering conference proceedings in
Computer Science, including LNCS, LNBIP, CCIS, IFIP-AICT and LNICST, for an
amount of 800 volumes per year. STM has the advantage of halving the time
required for classifying proceedings and it also reduced the complexity of the
task, which was traditionally carried out by senior editors but now performed
by junior editors. Its adoption produced a significant increment of the
discoverability of relevant publications on SpringerLink, resulting in about 9
million additional downloads over the last three years. A demo of STM is
available at http://stm-demo.kmi.open.ac.uk/.

###  6.3 Book recommendation

The Smart Book Recommender (SBR) [31] is an ontology-based recommender system
that supports the Springer Nature editorial team in promoting their
publications at Computer Science venues. It takes as input the proceedings of
a conference and returns books, journals and other proceedings that are likely
be of interest for its attendees.

SBR uses the CSO Classifier to represent more than 27K books and 320 journals
according to their distribution of topics. Then, it identifies the most
relevant editorial products, computing the similarity between the topical
representation of the input conferences and other products available in the
system. SBR also exploits the CSO topic taxonomy to graphically represent and
compare conferences and books, allowing users to understand the rationale
behind its recommendations. A demo of SBR is available at
http://rexplore.kmi.open.ac.uk/SBR-demo.

###  6.4 Forecasting research topics

Understanding and reacting timely to new developments in the research
landscape is critical for a variety of stakeholders, such as funding bodies,
academic publishers, companies and others. Augur [24] is a novel approach
which uses CSO for anticipate the emergence of new research topics.
Specifically, Augur analyses topic networks, i.e. collaboration networks
between research communities associated with specific research areas, and
identifies clusters associated with a significant increase in the pace of
collaboration. Over these networks, Augur applies a novel clustering algorithm
called the Advanced Clique Percolation Method (ACPM). The resulting clusters
of topics indicate the areas of the network that are nurturing new research
areas. Augur uses CSO for creating semantically-enhanced topic networks
describing the collaboration between research topics over time. The evaluation
of Augur proved that semantically enriching topics networks with CSO yields
more than 30% increase of f-measure on the task of predicting the emergence of
new research areas. Further details of Augur and its evaluation are available
in Salatino et al. [24].

###  6.5 Systematic literature reviews

The aim of systematic reviews (SRs) is to find all the evidence relevant to a
particular research question, and identify what can be said based on those
findings. Typically, systematic reviews require domain experts to collect,
annotate and synthesise hundreds of papers manually, using a well-defined
methodology meant to mitigate the risks of biases and ensure repeatability for
later updates. This task becomes extremely hard when investigating large
numbers of papers (e.g. hundreds of thousands). The Expert-Driven Automatic
Methodology (EDAM) [19] was developed for reducing the amount of tedious
manual tasks involved in SRs while taking advantage of the value provided by
human expertise. In particular, EDAM is able to i) characterise the area of
interest using an ontology of topics, ii) ask domain experts to refine such an
ontology, and iii) take advantage of this knowledge base for classifying
relevant papers and producing useful analytics.

This approach uses the CSO Classifier to classify all research papers using
title, abstract, and keywords. For a given topic, it then categorises all
papers that were annotated with that specific topic, as well as all its
relatedEquivalent and all its sub-branches, using the superTopicOf relation
within CSO.

We evaluated the ability of EDAM to correctly discriminate between different
topics in the field of Software Architecture by classifying a set of randomly-
selected papers both with EDAM and with six human experts. We compared the
annotation produced by both human experts and EDAM, considering the latter as
an additional annotator. EDAM performance was not statistically significantly
different from that of six senior researchers in the field (p=0.77). The
approach adopting CSO yielded the highest average agreement and also obtained
the highest agreement with three out of six domain experts. Further details
about this evaluation and our results are available in Osborne et al. [19].

###  6.6 Forecasting technology adoption

Typically, the spreading of a technology from a one research area (e.g.,
Semantic Web) to a different and possibly conceptually distant area (e.g.,
Digital Humanities) may take several years, potentially delaying the research
process.

The Technology-Topic Framework (TTF) [15] is an approach that suggests
promising technologies to scholars in order to accelerate the pace of
technology propagation. It characterises technologies according to their
propagation through research topics drawn from CSO, and uses this
representation to forecast the propagation of novel technologies across
research fields.

TTF was evaluated on a set of 1,118 technologies in the fields of Semantic Web
and Artificial Intelligence, yielding a precision of 74.4% and a recall of
47.7% for the first 20 research areas. More details about Technology-Topic
Framework are available in Osborne et al. [15].

###  6.7 Scientific knowledge graphs generation

Scientific Knowledge Graphs (SKGs) are semantic graph databases that model
scholarly knowledge in a structured, interlinked, and semantically rich
manner. SKGs describe the actors (e.g., authors, organisations), the documents
(e.g., publications, patents), and the research knowledge (e.g., research
topics, tasks, technologies) in this space, as well as their reciprocal
relationships.

CSO currently support two of these resources. The first is the Academia and
Industry DynAmics (AIDA) knowledge graph [1] whicb describes 14M papers and 8M
patents in the field of Computer Science. It was generated by by automatically
integrating data from Microsoft Academic Graph, Dimensions, English DBpedia,
the Computer Science Ontology, and the Global Research Identifier Database.
The CSO Classifier was used to annotate both papers and patents according to
their relevant topics in CSO. 4M papers and 5M patents are also categorised
according to the type of the author’s affiliations (academy, industry, or
collaborative) and 66 industrial sectors (e.g., automotive, financial, energy,
electronics) obtained from DBpedia. More details are available in Angioni et
al. [1]. AIDA can be browsed and downloaded from http://w3id.org/aida.

The second knowledge base integrating CSO is the Artificial Intelligence
Knowledge Graph (AI-KG) [6], which is a large-scale knowledge graph that
describes about 850K research entities. AI-KG includes 1,2M statements
extracted from 333K research publications in the field of AI and describes 5
types of entities (e.g., tasks, methods, metrics, materials, others) linked by
27 relations. It was designed to support a large variety of intelligent
services for analyzing and making sense of research dynamics, supporting
researchers in their daily job, and informing decision of founding bodies and
governments.

AI-KG was generated by applying an automatic pipeline that extracts entities
and relationships using three tools: DyGIE++, Stanford CoreNLP, and the CSO
Classifier. It is available under CC BY 4.0 can be browsed and downloaded from
http://w3id.org/aikg.

##  7 Conclusions and Future Work

In this paper, we presented the Computer Science Ontology Framework, a
conceptual framework that characterises the design, extraction and use of the
Computer Science Ontology, which is currently the largest taxonomy of research
topics in Computer Science. This framework includes the CSO classifier, a tool
for annotating research papers according to a domain ontology. We described
several high-level applications that take advantage of CSO for supporting the
exploration of the research landscape and forecasting research dynamics.

We are now working on a new version of Klink-2, in order to produce larger and
more accurate ontologies of research topics. We also plan to explore the
application of this framework in other research fields, such as Engineering
and Life Science.

## References

  * [1] Angioni, S., Salatino, A., Osborne, F., Reforgiato Recupero, D., Motta, E.: Integrating knowledge graphs for analysing academia and industry dynamics. In: ADBIS, TPDL and EDA 2020 Common Workshops and Doctoral Consortium. Springer International Publishing, Cham (2020)
  * [2] Bettencourt, L.M., Kaiser, D.I., Kaur, J.: Scientific discovery and topological transitions in collaboration networks. Journal of Informetrics 3(3), 210–221 (2009)
  * [3] Boyack, K.W., Newman, D., Duhon, R.J., Klavans, R., Patek, M., Biberstine, J.R., Schijvenaars, B., Skupin, A., Ma, N., Börner, K.: Clustering more than two million biomedical publications: Comparing the accuracies of nine text-based similarity approaches. PLOS ONE 6(3), 1–11 (03 2011). https://doi.org/10.1371/journal.pone.0018029, https://doi.org/10.1371/journal.pone.0018029
  * [4] Cimiano, P., Völker, J.: Text2onto. In: Montoyo, A., Muńoz, R., Métais, E. (eds.) Natural Language Processing and Information Systems. pp. 227–238. Springer Berlin Heidelberg, Berlin, Heidelberg (2005)
  * [5] Clough, P., Sanderson, M., Tang, J., Gollins, T., Warner, A.: Examining the limits of crowdsourcing for relevance assessment. IEEE Internet Computing 17(4), 32–38 (July 2013). https://doi.org/10.1109/MIC.2012.95
  * [6] Dessì, D., Osborne, F., Reforgiato Recupero, D., Buscaldi, D., Motta, E., Sack, H.: Ai-kg: an automatically generated knowledge graph of artificial intelligence. In: International Semantic Web Conference. Springer International Publishing, Cham (2020)
  * [7] Di Noia, T., Magarelli, C., Maurino, A., Palmonari, M., Rula, A.: Using ontology-based data summarization to develop semantics-aware recommender systems. In: European Semantic Web Conference. pp. 128–144. Springer (2018)
  * [8] Fathalla, S., Vahdati, S., Auer, S., Lange, C.: Towards a knowledge graph representing research findings by semantifying survey articles. In: International Conference on Theory and Practice of Digital Libraries. pp. 315–327. Springer (2017)
  * [9] Kirrane, S., Sabou, M., Fernández, J.D., Osborne, F., Robin, C., Buitelaar, P., Motta, E., Polleres, A.: A decade of semantic web research through the lenses of a mixed methods approach. Semantic Web Journal (2019)
  * [10] Kishore, R., Ramesh, R.: Ontologies: a handbook of principles, concepts and applications in information systems, vol. 14. Springer Science & Business Media (2007)
  * [11] Livingston, K.M., Bada, M., Baumgartner, W.A., Hunter, L.E.: Kabob: ontology-based semantic integration of biomedical databases. BMC bioinformatics 16(1), 126 (2015)
  * [12] Mendes, P.N., Jakob, M., García-Silva, A., Bizer, C.: Dbpedia spotlight: Shedding light on the web of documents. In: Proceedings of the 7th International Conference on Semantic Systems. pp. 1–8. I-Semantics ’11, ACM, New York, NY, USA (2011). https://doi.org/10.1145/2063518.2063519, http://doi.acm.org/10.1145/2063518.2063519
  * [13] Mikolov, T., Sutskever, I., Chen, K., Corrado, G., Dean, J.: Distributed representations of words and phrases and their compositionality. In: Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2. pp. 3111–3119. NIPS’13, Curran Associates Inc., USA (2013), http://dl.acm.org/citation.cfm?id=2999792.2999959
  * [14] Muller, A., Dorre, J., Gerstl, P., Seiffert, R.: The taxgen framework: automating the generation of a taxonomy for a large document collection. In: Proceedings of the 32nd Annual Hawaii International Conference on Systems Sciences. 1999. HICSS-32. Abstracts and CD-ROM of Full Papers. vol. Track2, pp. 9 pp.– (Jan 1999). https://doi.org/10.1109/HICSS.1999.772687
  * [15] Osborne, F., Mannocci, A., Motta, E.: Forecasting the spreading of technologies in research communities. In: Proceedings of the Knowledge Capture Conference. pp. 1:1–1:8. K-CAP 2017, ACM, New York, NY, USA (2017). https://doi.org/10.1145/3148011.3148030, http://doi.acm.org/10.1145/3148011.3148030
  * [16] Osborne, F., Motta, E.: Mining semantic relations between research areas. In: International Semantic Web Conference. pp. 410–426. Springer (2012)
  * [17] Osborne, F., Motta, E.: Klink-2: Integrating multiple web sources to generate semantic topic networks. In: Arenas, M., Corcho, O., Simperl, E., Strohmaier, M., d’Aquin, M., Srinivas, K., Groth, P., Dumontier, M., Heflin, J., Thirunarayan, K., Thirunarayan, K., Staab, S. (eds.) The Semantic Web - ISWC 2015\. pp. 408–424. Springer International Publishing, Cham (2015)
  * [18] Osborne, F., Motta, E., Mulholland, P.: Exploring scholarly data with rexplore. In: International semantic web conference. pp. 460–477. Springer (2013)
  * [19] Osborne, F., Muccini, H., Lago, P., Motta, E.: Reducing the effort for systematic reviews in software engineering. Data Science pp. 1–29 (08 2019). https://doi.org/10.3233/DS-190019
  * [20] Osborne, F., Salatino, A., Birukou, A., Motta, E.: Automatic classification of springer nature proceedings with smart topic miner. In: Groth, P., Simperl, E., Gray, A., Sabou, M., Krötzsch, M., Lecue, F., Flöck, F., Gil, Y. (eds.) The Semantic Web – ISWC 2016. pp. 383–399. Springer International Publishing, Cham (2016)
  * [21] Osborne, F., Scavo, G., Motta, E.: Identifying diachronic topic-based research communities by clustering shared research trajectories. In: European Semantic Web Conference. pp. 114–129. Springer (2014)
  * [22] Salatino, A.A., Osborne, F., Birukou, A., Motta, E.: Improving editorial workflow and metadata quality at springer nature. In: Ghidini, C., Hartig, O., Maleshkova, M., Svátek, V., Cruz, I., Hogan, A., Song, J., Lefrançois, M., Gandon, F. (eds.) The Semantic Web – ISWC 2019. pp. 507–525. Springer International Publishing, Cham (2019)
  * [23] Salatino, A.A., Osborne, F., Motta, E.: How are topics born? understanding the research dynamics preceding the emergence of new areas. PeerJ Computer Science 3, e119 (2017)
  * [24] Salatino, A.A., Osborne, F., Motta, E.: Augur: Forecasting the emergence of new research topics. In: Proceedings of the 18th ACM/IEEE on Joint Conference on Digital Libraries. pp. 303–312. JCDL ’18, ACM, New York, NY, USA (2018). https://doi.org/10.1145/3197026.3197052
  * [25] Salatino, A.A., Osborne, F., Thanapalasingam, T., Motta, E.: The cso classifier: Ontology-driven detection of research topics in scholarly articles. In: Doucet, A., Isaac, A., Golub, K., Aalberg, T., Jatowt, A. (eds.) Digital Libraries for Open Knowledge. pp. 296–311. Springer International Publishing, Cham (2019)
  * [26] Salatino, A.A., Thanapalasingam, T., Mannocci, A., Birukou, A., Osborne, F., Motta, E.: The computer science ontology: A comprehensive automatically-generated taxonomy of research areas. Data Intelligence 0(0), 1–38 (0). https://doi.org/10.1162/dint_a_00055, https://doi.org/10.1162/dint_a_00055
  * [27] Salatino, A.A., Thanapalasingam, T., Mannocci, A., Osborne, F., Motta, E.: The computer science ontology: a large-scale taxonomy of research areas. In: International Semantic Web Conference. pp. 187–205. Springer (2018)
  * [28] Sanderson, M., Croft, B.: Deriving concept hierarchies from text. In: Proceedings of the 22Nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 206–213. SIGIR ’99, ACM, New York, NY, USA (1999). https://doi.org/10.1145/312624.312679
  * [29] Satopaa, V., Albrecht, J., Irwin, D., Raghavan, B.: Finding a ”kneedle” in a haystack: Detecting knee points in system behavior. In: 2011 31st International Conference on Distributed Computing Systems Workshops. pp. 166–171 (June 2011). https://doi.org/10.1109/ICDCSW.2011.20
  * [30] Shen, Z., Ma, H., Wang, K.: A web-scale system for scientific knowledge exploration. In: Proceedings of ACL 2018, System Demonstrations. pp. 87–92. Association for Computational Linguistics, Melbourne, Australia (Jul 2018). https://doi.org/10.18653/v1/P18-4015
  * [31] Thanapalasingam, T., Osborne, F., Birukou, A., Motta, E.: Ontology-based recommendation of editorial products. In: Vrandečić, D., Bontcheva, K., Suárez-Figueroa, M.C., Presutti, V., Celino, I., Sabou, M., Kaffee, L.A., Simperl, E. (eds.) The Semantic Web – ISWC 2018. pp. 341–358. Springer International Publishing, Cham (2018)
  * [32] Wohlgenannt, G., Weichselbraun, A., Scharl, A., Sabou, M.: Dynamic integration of multiple evidence sources for ontology learning. JIDM 3, 243–254 (2012)


# Noise Estimation for Generative Diffusion Models

Robin San-Roman*
École Normale Supérieure Paris-Saclay
<EMAIL_ADDRESS>Eliya Nachmani*, Lior Wolf
Tel-Aviv University & Facebook AI Research
<EMAIL_ADDRESS>
###### Abstract

Generative diffusion models have emerged as leading models in speech and image
generation. However, in order to perform well with a small number of denoising
steps, a costly tuning of the set of noise parameters is needed. In this work,
we present a simple and versatile learning scheme that can step-by-step adjust
those noise parameters, for any given number of steps, while the previous work
needs to retune for each number separately. Furthermore, without modifying the
weights of the diffusion model, we are able to significantly improve the
synthesis results, for a small number of steps. Our approach comes at a
negligible computation cost.

††*Equal contribution

##  1 Introduction

Deep generative models have seen a tremendous advancement in the past few
years. The main successful architectures can be divided into two categories:
(i) autoregessive models, such as VQ-VAE for images [25] and Wavenet for
speech [23]. (ii) non-autoregessive models, for example, StyleGAN [15] for
vision application and WaveGAN [4] for audio synthesis.

An emerging class of non-autoregessive models is the one of Denoising
Diffusion Probabilistic Models (DDPM). Such methods use diffusion models and
denoising score matching in order to generate images [7] and speech [2]. The
DDPM model learns to perform a diffusion process on a Markov chain of latent
variables. The diffusion process transforms a data sample into Gaussian noise.
During inference the reverse process is used, which is called the denoisng
process. The inference procedure starts from Gaussian noise and iteratively
refines the signal. This process is often conditioned on the class and
attributes that one wishes to generate.

In order to get high quality synthesis, a large number of denosing steps are
used (i.e. $1000$ steps). To allow the process to converge to a high quality
output with only a small number of denosing steps, a costly grid search is
required in order to find a noise schedule that would produce high-fidelity
results.

In this paper, we propose a novel method for obtaining the noise schedule
based on the conditioning data. The noise schedule that the proposed method
produces leads to a high fidelity synthesis of samples, even for a small
number of denosing steps. Moreover, for a given amount of denosing steps, the
proposed method obtains better results than the previous models, when their
noise schedule is determined by a costly per-sample grid search for the
optimal parameters.

Our method introduces a novel neural network that is able to monitor and
control the denoising process. Instead of fixing in advance the steps of the
reverse process that will be skipped, this network is able, by estimating the
amount of noise in the data, to schedule the subsequent steps of the denoising
process.

Our results are demonstrated on two major domains: vision and audio. In the
first domain, the proposed method is shown to provide a better FID score for
generated images, when the number of steps is restricted. For speech data, we
show that the proposed method improves various measures, such as Perceptual
Evaluation of Speech Quality (PESQ) and short-time objective intelligibility
(STOI).

##  2 Related Work

Diffusion Probabilistic Models were first introduced in the seminal work of
Sohl-Dickstein et al. [28], who presented the idea of using an iterative
neural diffusion process for destroying the structure of a given distribution,
while learning the reverse neural diffusion process for restoring the
structure in the data. It was shown that the proposed neural diffusion process
can learn the data distribution in domains, such as images and time series.
The main issue with the proposed neural diffusion process is that during
training it requires up to thousands of iterative steps in order to learn the
target distribution.

In [31], a new generative model based on the score matching method [10] and
Langevin dynamics was introduced. The proposed model estimates and samples the
logarithm of the data density, which is the Stein score function [19]. The
proposed method achieves state of the art results for modeling the CIFAR-10
dataset.

The two ideas of (i) neural Diffusion Probabilistic Models and (ii) generative
models based on score matching, were combined by the DDPM method of Ho et al.
[7]. DDPM presents a generative model based on the neural diffusion process
and applies score matching for image generation. Subsequently, in [2] a
generative neural diffusion process based on score matching was applied to
speech generation, obtaining state of the art results in comparison to well-
established methods, such as Wavenet [23], Wavernn [14] and GAN-TTS [1]. A
parallel contribution presented high fidelity speech generation results using
a different neural diffusion process [17].

One major limitation of the generative neural diffusion process is that in
order to generate a high quality sample, one should use a large number of
diffusion steps, e.g., a thousand steps are often used. Denoising Diffusion
Implicit Models (DDIMs) [30] is an acceleration for the denoising process. It
employs non-Markovian diffusion processes, which leads to a faster sample
procedure than other diffusion models.

A further development in the score based generative models is to consider this
process as a solution to a stochastic differential equation [32]. This method
achieves state of the art performance for unconditional image generation on
CIFAR-10. An alternative approach trains an energy-based generative model
using a diffusion process that is applied to increasingly noisy versions of a
dataset [5], also presenting results on CIFAR-10.

The recent TimeGrad model [24] is a diffusion process for probabilistic time
series forecasting, which was shown empirically to outperform Transformers
[34] and LSTMs [8] on some datasets. In another concurrent work, a multinomial
diffusion process is learned by adding categorical noise to the process [9].
Competitive results are presented for an image segmentation task and for
language modeling.

##  3 Background

Denoising Diffusion Probabilistic Model (DDPM) are neural network that learn
the gradients of the data log density $\nabla_{y}\log p(y)$:

$s(y)=\nabla_{y}\log p(y)$ (1)

Given those gradients, one can then use Langevin Dynamics to sample from the
probability iteratively

$\tilde{y}_{i+1}=\tilde{y}_{i}+\frac{\eta}{2}s(\tilde{y}_{i})+\sqrt{\eta}z_{i}$
(2)

Where $\eta>0$ is the step size and $z_{i}\sim\mathcal{N}(0,I)$.

The formalization of Denoising Diffusion Probabilistic Models (DDPM) by Ho et
al [7] employs a parameterized Markov chain trained using variational
inference, in order to produce samples matching the data after finite time.
The transitions of this chain are learned to reverse a diffusion process. This
diffusion process is defined by a Markov chain that gradually adds noise in
the data with a noise schedule $\beta_{1},\dots\beta_{N}$ and is defined as:

$q(y_{1:N}|y_{0})=\prod_{n=1}^{N}q(y_{n}|y_{n-1})\,,$ (3)

where N is the length of the diffusion process, and
$y_{N},...,y_{n},y_{n-1},...,y_{0}$ is a sequence of latent variables with the
same size as the clean sample $y_{0}$.

At each iteration, the diffusion process adds Gaussian noise, according to the
noise schedule:

$q(y_{n}|y_{n-1}):=\mathcal{N}(y_{n};\sqrt{1-\beta_{n}}y_{n-1},\beta_{n}\mathbf{I})\,,$
(4)

where $\beta_{n},$ is the noise schedule as defined above.

The diffusion process can be simulated for any number of steps with the closed
formula:

$y_{n}=\sqrt{\bar{\alpha}}y_{0}+\sqrt{1-\bar{\alpha}}\varepsilon\,,$ (5)

where $\alpha_{i}=1-\beta_{i}$, $\bar{\alpha}_{n}=\prod_{i=1}^{n}\alpha_{i}$
and $\varepsilon=\mathcal{N}(0,\mathbf{I})$.

One can use this to implement the DDPM training algorithm (Alg.1) which is
defined in [2]. The input to the training algorithm is the dataset $d$. The
algorithm samples $s$, $\bar{\alpha}$ and $\epsilon$. The noisy latent
variable $y_{s}$ is calculated and fed to the DDPM neural network
$\varepsilon_{\theta}$. A gradient descent step is taken in order to estimate
the $\varepsilon$ noise with the DDPM network. By the end of the algorithm,
the DDPM network can estimate the noise added during the diffusion process.

When $\sqrt{\bar{\alpha}}$ is close to $1$, the diffusion process adds a small
amount of noise and when $\sqrt{\bar{\alpha}}$ is close to $0$, there are
large amounts of noise that are added to the generation process.

As mentioned in [2], sampling the noise level $\sqrt{\bar{\alpha}}$ in the
uniform distribution $\mathcal{U}([0,1])$ gives poor empirical results. This
is due to the fact that the network $\varepsilon_{\theta}$ would rarely be
trained to fine tune good examples ($\sqrt{\bar{\alpha}}$ close to $1$).

Instead, one can sample $\sqrt{\bar{\alpha}}$ such that the distribution of
the training examples match the forward process, i.e., there are an equal
amount of training samples that correspond to every step of the diffusion
process. The first step is to sample a state $s$ ($s\sim\mathcal{U}\\{1,\dots
n\\}$ line 3) in the forward process and then sample the noise level using:

$\sqrt{\bar{\alpha}}\sim\mathcal{U}[l_{s},l_{s-1}]$ (6)

Where:

$l_{0}=1,\hskip 2.84526ptl_{s}=\sqrt{\prod_{i=0}^{s}1-\beta_{i}}$ (7)

Algorithm 1 DDPM training procedure

1: repeat

2: $y_{0}\sim d(y_{0})$

3: $s\sim\mathcal{U}(\\{1,...,N\\})$

4: $\sqrt{\bar{\alpha}}\sim\mathcal{U}(\left[l_{s-1},l_{s}\right])$

5: $\varepsilon\sim\mathcal{N}(0,I)$

6: $y_{s}=\sqrt{\bar{\alpha}}y_{0}+\sqrt{1-|\bar{\alpha}|}\varepsilon$

7: Take gradient descent step on:
$\|\varepsilon-\varepsilon_{\theta}(y_{s},x,\sqrt{\bar{\alpha}})\|_{1}$

8: until converged

In Algorithm 1 (line 7) the DDPM is trained to learn the noise $\varepsilon$
directly, instead of learning the Markov chain gradients. In [7] the authors
show that the following reparametrization leads to better empirical results:

$\varepsilon=-\sqrt{1-\bar{\alpha}_{n}}\nabla_{y_{n}}\log q(y_{n}|y_{0})$ (8)

The trained model $\varepsilon_{\theta}$ can be used to perform inference
using a variation of Langevin dynamics (Eq. 2). The following update from [29]
is used to reverse a step of the diffusion process:

$y_{n-1}=\dfrac{y_{n}-\frac{1-\alpha_{n}}{\sqrt{1-\bar{\alpha}_{n}}}\varepsilon_{\theta}(y_{n},x,\sqrt{\bar{\alpha}_{n}})}{\sqrt{\bar{\alpha}_{n}}}+\sigma_{n}\varepsilon\,,$
(9)

where $\varepsilon$ is white noise. Ho et al. [7] showed that adding white
noise of variance $\sigma_{n}^{2}=\beta_{t}$ is optimal, when the inference
procedure is initialized with gaussian noise ($y_{N}\sim\mathcal{N}(O,I)$).

One can use this update rule in Eq. 9 to sample from the data distribution, by
starting from a Gaussian noise and then step-by-step reversing the diffusion
process. Algorithm 2 is used to sample with the network
$\varepsilon_{\theta}$.

Since our experiments on images are unconditional, the network no longer needs
the input $x$. The update equation that we use is defined in [29]:

$y_{n-1}=\sqrt{\bar{\alpha}_{n-1}}\hat{y}_{0,n}+\sqrt{1-\bar{\alpha}_{n-1}-\tilde{\sigma}_{n}^{2}}\varepsilon_{\theta}(y_{n},\bar{\alpha}_{n})+\tilde{\sigma}_{n}\varepsilon\,,$
(10)

where
$\hat{y}_{0,n}=\dfrac{y_{n}-\sqrt{1-\bar{\alpha}_{n}}\varepsilon_{\theta}(y_{n},\bar{\alpha}_{n})}{\sqrt{\bar{\alpha}_{n}}}$
is the prediction of $y_{0}$, $\varepsilon\sim\mathcal{N}(0,I)$ is white
noise, and $\tilde{\sigma}$ is a new parameter of the generative process.

One can apply the rule of Eq.10 with $\tilde{\sigma}=0$, in which case no
random noise is added. This makes the process deterministic and leads to the
best results in most of the scenarios [29].

Algorithm 2 DDPM sampling algorithm

1: $y_{N}\sim\mathcal{N}(0,I)$

2: for n= N, …, 1 do

3: $z\sim\mathcal{N}(0,I)$

4: $\hat{\varepsilon}=\varepsilon_{\theta}(y_{n},x,\sqrt{\bar{\alpha}_{n}})$

5:
$y_{n-1}=\frac{y_{n}-\frac{1-\alpha_{n}}{\sqrt{1-\bar{\alpha}_{n}}}\hat{\varepsilon}}{\sqrt{\alpha_{n}}}$

6: if $n\neq 1$ then

7: $y_{n-1}=y_{n-1}+\sigma_{n}z$

8: end if

9: end for

10: return $y_{0}$

Algorithm 3 $P_{\theta}$ training procedure

1: repeat

2: $y_{0}\sim q(y_{0})$

3: $s\sim\mathcal{U}(\\{1,...,N\\})$

4: $\sqrt{\bar{\alpha}}\sim\mathcal{U}(\left[l_{s-1},l_{s}\right])$

5: $\varepsilon\sim\mathcal{N}(0,I)$

6: $y_{s}=\sqrt{\bar{\alpha}}y_{0}+\sqrt{1-|\bar{\alpha}|}\varepsilon$

7: $\hat{\alpha}=P_{\theta}(y_{s})$

8: Take gradient descent step on:
$\|\log(1-\bar{\alpha})-\log(1-\hat{\alpha})\|_{2}$

9: until converged

Algorithm 4 Model inference procedure

1: $N$ Number of iterations

2: $y_{N}\sim\mathcal{N}(0,I)$

3: $\mathbf{\alpha},\mathbf{\beta}=$ initialNoiseSchedule()

4: for n= N, …, 1 do

5: $z\sim\mathcal{N}(0,I)$

6: $\hat{\varepsilon}=\varepsilon_{\theta}(y_{n},\sqrt{\bar{\alpha}_{n}})$ or
$\varepsilon_{\theta}(y_{n},t)$ where $\bar{\alpha}_{n}\in[l_{t},l_{t-1}]$

7:
$y_{n-1}=\frac{y_{n}-\frac{1-\alpha_{n}}{\sqrt{1-\bar{\alpha}_{n}}}\hat{\varepsilon}}{\sqrt{\alpha_{n}}}$

8: if $n\in U$ then

9: $\hat{\alpha}=P_{\theta}(y_{n-1})$

10: $\mathbf{\alpha},\mathbf{\beta},\tau=$
updateNoiseSchedule($\hat{\alpha},n$)

11: end if

12: if $n\neq 1$ then

13: $y_{n-1}=y_{n-1}+\sigma_{n}z$

14: end if

15: end for

16: return $y_{0}$

Figure 1: An overview of our method for image generation. The previous state
$y_{n_{1}}$ is passed as input to the $P_{\theta}$ network, which estimates
the noise level $\hat{\alpha}$. The noise level $\hat{\alpha}$ is then used by
function updateNoiseSchedule (UNS in the diagram) which calculates the noise
parameters $\alpha,\beta$. These noise parameters are used by the
$\epsilon_{\theta}$ network to predict the next state $y_{n_{2}}$.

##  4 Method

We note that at training time the data is constructed in such a way (cf. Eq.
5) that we can feed the network $\varepsilon_{\theta}$ with the noisy data
$y_{s}$ and with ground truth noise level $\sqrt{\bar{\alpha}}$. However, at a
given inference step, the amount of noise in the data $y_{n}$ is unknown. In
most methods, the conditioning used is a predefined one. As a result, the
input conditioning given to the network $\varepsilon_{\theta}$ is not
exploited at its full potential.

This inexact analysis of the noise is especially detrimental when the number
of steps in the generation process is small. In this case, the quality of the
samples at intermediate states ($y_{s}$) varies widely.

To solve this problem, we introduce a novel neural network $P_{\theta}$ that
estimates the value of $\bar{\alpha}$, thus providing better conditioning for
the diffusion network. The input to the neural network $P_{\theta}$ is the
data $y_{s}$ generated at step $s$ and its output is the estimated noise level
$\hat{\alpha}$. This network provides a continuous control signal to the
generation process, by providing the DDPM network $\varepsilon_{\theta}$ with
a conditioning signal that relates to the actual quality of the generation.

Figure 1 depicts the generation process used. Similarly to [29], the idea is
to use a pretrained DDPM ($\varepsilon_{\theta}$) from [7] and skip some of
the states in the process to shorten the generation time. However, our model
includes a Noise estimation model ($P_{\theta}$) to calculate, between
denoising steps, adjustments of the noise schedule.

###  4.1 Noise Level Estimation

The network is trained with a similar procedure as Alg. 1. The sampling of the
noise level is done using the distribution described in Eq. 6. Given the input
$y_{n}$, the network $P_{\theta}$ estimates the noise level ($\bar{\alpha}$).

Empirically, we found that that the performance of the network in low noise
situations is critical to the performance of our method. Indeed, the last
steps of the generation process are responsible for the quality of the final
sample. At those stages, the amount of noise is very small, and $\bar{\alpha}$
approaches $1$. We, therefore, design our regression loss on $\bar{\alpha}$ :

$\mathcal{L}(\bar{\alpha},\hat{\alpha})=\|\log(1-\bar{\alpha})-\log(1-\hat{\alpha})\|_{2}$
(11)

This loss penalizes with higher cost the errors when close to 1 resulting in
better network performances in this region.

###  4.2 Noise Schedule Adjustments

We wish to use $\hat{\alpha}$, the output of the $P_{\theta}$, in order to
adjust the noise schedule parameters. In the following, we present how obtain
those parameters, assuming they follow either a linear or a Fibonacci
distribution. This allows us to define the following function:

$\alpha,\beta=\text{updateNoiseSchedule}(\hat{\alpha},n)$ (12)

Where $\alpha,\beta$ are the set of noise parameters and $n$ is the number of
remaining denoising steps. As we show, in order to define this function, it is
sufficient to estimate the first parameters $\beta_{0}$ and the type of
distribution.

####  4.2.1 Linear Schedule

In the general case, $\bar{\alpha}$ is given by:

$\bar{\alpha}=\prod_{i=0}^{s-1}(1-\beta_{i})$ (13)

Since the values of the $\beta_{i}$ are typically between $10^{-6}$ and
$10^{-2}$ we can use the Taylor approximation
$log(1-\beta_{i})\approx-\beta_{i}$. We can derive from Eq. 13:

$\log(\bar{\alpha})=\sum_{i=0}^{s-1}\log(1-\beta_{i})\approx-\sum_{i=0}^{s-1}\beta_{i}$
(14)

Assuming the linear schedule, the expression of $\beta_{i}$ with respect to
$i$ in the range $\\{0,\dots s-1\\}$ is:

$\beta_{i}=\beta_{0}+ix\,,$ (15)

where $x$ is the step size. Therefore, we have:

$\log(\bar{\alpha})=-\left(\sum_{i=0}^{s-1}\beta_{0}+ix\right)$ (16)

and

$x=-2\frac{(\log(\bar{\alpha})+n\beta_{0})}{s(s-1)}$ (17)

Once $x$ is recovered, Eq.15 provides us with the noise parameters required to
perform the remaining denoising steps.

####  4.2.2 Fibonacci Schedule

Chen et al. [2] employ a Fibonacci schedule for a low number of denoising
steps:

$\beta_{i+2}=\beta_{i}+\beta_{i+1}$ (18)

We can find a closed form for this series given $\bar{\alpha}$ and
$\beta_{0}$, which will allow us to compute all the terms. The homogenuous
recurrent equation is:

$\beta_{i+2}-\beta_{i+1}-\beta_{i}=0$ (19)

Thus, the series ($\beta_{i}$) is of the form:

$\beta_{i}=A\varphi^{i}+B\varphi^{\prime i}\,,$ (20)

where $\varphi$ and $\varphi^{\prime}$ are the solutions of $x^{2}-x-1=0$

With a straightforward induction on $n$, one can show that:

$\forall n>2,\beta_{1}+\sum_{i=0}^{n-1}\beta_{i}=\beta_{n+1}$ (21)

Combining Eq. 21 with the approximation of Eq. 14, we obtain that $A$ is the
solution of the following system of linear equations:

$\begin{cases}A\varphi^{0}+B\varphi^{\prime 0}=\beta_{0}\\\
A\varphi^{1}+B\varphi^{1}+\log(\bar{\alpha})=A\varphi^{n+1}+B\varphi^{n+1}\end{cases}$
(22)

The unique solution $(A,B)$ of these equations is:

$\begin{split}A&=\beta_{0}-\frac{\log(\bar{\alpha})-\beta_{0}(\varphi-\varphi^{n+1})}{\varphi^{\prime}-\varphi-(\varphi^{\prime
s+1}-\varphi^{s+1})}\\\
B&=\frac{\log(\bar{\alpha})-\beta_{0}(\varphi-\varphi^{n+1})}{\varphi^{\prime}-\varphi-(\varphi^{\prime
s+1}-\varphi^{s+1})}\end{split}$ (23)

Thus a closed form solution is obtained that allows to compute the Fibonacci
noise schedule ($\beta,\alpha$), given the noise level $\bar{\alpha}$ and
$\beta_{0}$.

####  4.2.3 Conditioning on Discrete Indexes

Most DDPMs are not conditioned on the noise level $\bar{\alpha}$ but instead
use a discrete integer index that represents steps in the reverse process. The
two types of conditioning are related. Instead of giving the network with the
exact value $\sqrt{\bar{\alpha}}$, the network is given the integer $t$ of the
interval $[l_{t},l_{t-1}]$ (defined in Eq. 7), which contains the estimated
value.

To enable our method to work with this type of DDPM, we estimate the noise
level and feed the network with the integer encoding corresponding interval.

###  4.3 Inference procedure

Our inference procedure is introduce in algorithm 4. The idea is to have a set
of step indexes $U$ for which, we readjust the noise schedule. For simplicity,
in all of our experiments, $U=\\{1,2,\dots,N\\}$ for a given number of steps
$N$.

The adjustment is done using the neural network $P_{\theta}$, which estimates
the noise level $\bar{\alpha}$. Given this estimation, we deduce the sets of
parameters $\mathbf{\alpha},\mathbf{\beta}$ for the remaining denoising steps,
as shown in Sec. 4.2.

The noise schedule (vectors $\alpha$ and $\beta$) is initialised with a set of
predefined values (function initialNoiseSchedule()). The rest of the algorithm
(lines 3-15) is very similar to the algorithm 2. The only difference (lines
7-9) is that we use a set of iteration indexes $U$ for which we will adjust
the noise schedule vectors.

For the iteration $n\in U$, we estimate the noise level using the model
$P_{\theta}$, then we follow the deterministic method described in Sec. 4.2
(function updateNoiseSchedule($\bar{\alpha},n$)) to compute the adjustment of
the noise schedule.

##  5 Experiments

To demonstrate the wide applicability of our approach, we perform experiments
in both speech synthesis and image generation. In both cases, we determine the
optimal few-step scheduling for state of the art models.

Figure 2: Performance of the network $P_{\theta}$ for the speech data for the noise estimation task itself. | MCD ($\downarrow$) | PESQ ($\uparrow$) | STOI ($\uparrow$)
---|---|---|---
$1000$ iterations | 2.65 | 3.29 | 0.959
Grid Searched | 2.76 | 2.78 | 0.924
Our method | 2.96 | 3.14 | 0.943
Table 1: Comparison between a grid searched noise schedule and an adjusting
noise schedule for speech generation. Figure 3: The FID score, over a small
number of iterations, obtained for the CelebA dataset, for different $\eta$
values, for DDIM method and for our method.
---
Figure 4: Typical examples of the denoising processes for 6 iterations $\eta=0$. For three different noise inputs, we compare our method (top) to DDIM[29] (bottom). |  |
---|---|---
(a) | (b) | (c)
Figure 5: Generated images with our method $\eta=0$ for (a) 3, (b) 5 and (c) 6
iterations.

Figure 6: FID Score obtained for CelebA for our method and DDPM [7] as a
function of the number of iterations.

|
---|---
(a) | (b)
Figure 7: The FID score, over a small number of iterations, obtained for LSUN
(a) Bedroom and (b) Church datasets, for DDIM method and for our method.

|
---|---
|
(a) | (b)
Figure 8: LSUN 256x256 synthesis examples for $N=6$ iterations. The same input noise used for both process. (a) Church dataset, (b) Bedroom dataset. The top row in each example is our method and the bottom row is the DDIM method.  |  |  |
---|---|---|---
(a) | (b) | (c) | (d)
|  |  |
(e) | (f) | (g) | (h)
Figure 9: LSUN Church and Bedroom 256x256 datasets. Comparison of our method
and the DDIM baseline for $6$ and $10$ iterations. First row is for LSUN
Church 256x256 (a) ours with $6$ iterations, (b) DDIM with $6$ iteration, (c)
ours with $10$ iterations, (d) DDIM with $10$ iterations. Second row is for
LSUN Bedroom 256x256 (e) ours with $6$ iterations, (f) DDIM with $6$
iterations, (g) ours with $10$ iterations, (h) DDIM with $10$ iterations.

###  5.1 Speech Generation

For speech generation, we used a WaveGrad implementation that came with a grid
searched noise schedule for $6$ iterations [35]. We trained a small model
$P_{\theta}$ based on a the version of ConvTASNet [21] architecture.

The model is composed of the encoding and masking module of ConvTASNet. Its
decoding part is not utilized. The ConvTASNet architecture cuts, using a
separator network, the signal in chunks and processes each chunk individually.
Our network further applies a fully connected layer with an output dimension
of $1$, followed by a sigmoid activation function to each chunk. The final
output $\hat{\alpha}$ is the average of the outputs of all the chunks. The
encoder has $N=64$ filters of size $L=16$ (the parameter names follow [21]).
The separator uses stacks of $X=4$ convolutional blocks of kernel size $P=4$
with $R=4$ repeats. It has $H=128$ channels in the convolutional blocks and
$B=64$ in the bottleneck and residual paths.

To train our model $P_{\theta}$, we use the same split of the LJ-Speech
dataset [11] used by [35] for training the WaveGrad model. Our model was
trained with the Adam optimizer [16] and a learning rate of $0.001$. Each
batch includes $32$ samples from an audio duration of $3$ seconds with a
sampling rate of $22050$ Hz.

In order evaluate the accuracy of the network in recovering $\bar{\alpha}$,
noisy speech signals are generated according to Eq. 5 with $\bar{\alpha}$
values between 0 and 1. The noise level is then estimated by the trained
network $P_{\theta}$.

The results of this experiment are presented in Figure 2. The Mean Square
Error (MSE) between the ground truth $\bar{\alpha}$ (used to generate the
noisy speech) and the network estimation $\hat{\alpha}$ is depicted for each
$\bar{\alpha}$. Each point is computed with 16 audio files of 3 secs from the
validation set. As can be seen, our model is able to estimate the noise level
within an error of at most $10^{-4}$ and with even better performance when
alpha is close to $1$, which is where the precision is critical to the
performance of our method.

Next, we evaluate the synthesis quality. The DDPM employed in our experiments
was trained using Mel Spectrogram as the conditioning signal $x$. Following
[2], in our experiments, the ground truth Mel-Spectrogram is given as an input
in order to allow the computation of the relative speech metrics (MCD[18],
PESQ[26], STOI[33]).

In our experiments, we performed inference for six iterations with an
adjustment of the noise schedule at every step i.e. $U=\\{1,\dots 6\\}$. This
noise schedule adjustment takes place with the Fibonacci method, as described
in Sec. 4.2.2.

As can be heard from the samples that are provided in the supplementary
material, for few iterations, our method obtains a much better improvement
than the baseline method, after applying a costly grid search for the optimal
parameters of the baseline method. This is also captured by the qualitative
results, presented in Tab. 1. Even though our method results in a small
decrease in the MCD [18], we demonstrate a large improvement in both PESQ [26]
and STOI [33].

###  5.2 Image Generation

For image generation, we use denoising diffusion models trained in [13],
relying on the implementation available in [12]. We trained our model
$P_{\theta}$ on three image datasets (i) CelebA 64x64 [20], (ii) LSUN Bedroom
256x256, and (iii) LSUN Church 256x256 [36].

The model $P_{\theta}$ used for the noise estimation employed a VGG11 [27]
backbone pretrained on ImageNet [3]. We added ReLU activations, followed with
a fully connected layer with an output dimension $1$ and a final sigmoid
activation to the backbone. An Adam optimizer[16] with a learning rate of
$10^{-4}$ was used, with a batch size of size 64.

The Fréchet Inception Distance (FID) [6] is used as the benchmark metric. For
all experiments, similarly to the DDIM paper, we compute the FID score with
$50,000$ generated images using the torch-fidelity implementation [22].

Figure 3 depicts the FID score of our method using the update in Eq. 9 is
comparison to the baseline DDIM method. Both methods use the same DDIM
diffusion model provided in [12] for CelebA. Our method uses the adjusted
noise schedule at every step and generates a linear noise schedule (cf. Sec.
4.2.1).

Different plots are given for different values of $\eta$, which is the
parameter that control $\tilde{\sigma}$ in Eq. 10:

$\tilde{\sigma}=\eta\sqrt{\beta_{n}(1-\bar{\alpha}_{n-1})(1-\bar{\alpha}_{n})}$
(24)

As can be seen, our method improves by a large gap the FID score the DDIM
method. For example, for three iteration with $\eta=0.0$ our method improve
the FID score by $163.4$. The gap in performance is maintained for up to 10
iterations. (Several of the plots for different $\eta$ values overlap, see
supplementary for a table of results).

In Figure 4, we demonstrate the progression over a six iteration denoising
process for both our method and the DDIM method that we use as a baseline.
Evidently, our generated images are more coherent and sharper than the DDIM
method.

Figure 5 presents samples for celebA 64x64 generation, given a different
number of target steps. Our inference procedure is able to generate decent
images for as little as $3$ denoising steps. We also show convincing
generations results for $5$ and $6$ steps generation processes. This results
demonstrate that our method helps toward finding the best non-Markovian
denoising process, especially when generating with very few iterations. The
baseline results are of much lower quality, see supplementary.

In Figure 7, we compare our method with DDPM [29] for the CelebA dataset. As
can be seen, our method improves, by a large margin, the results of the DDPM
method up to 100 iterations. For example, for $10$ iteration, we improve the
FID score by $266.03$.

Similarly, in Figures 7 we provide the FID score for LSUN Church and Bedroom
256x256 datasets, using the published DDIM models. As can be seen for a small
number of iteration, i.e. less then $10$, our method greatly improves the
results of the baseline method DDIM.

Method/#Iteration | 10 | 20 | 50 | 100
---|---|---|---|---
No adjustment (DDPM/DDIM) | 0.41 | 0.80 | 2.02 | 4.03
Adjustment every iteration | 0.59 | 1.19 | 2.92 | 6.02
Table 2: Mean image generation time in second obtained for CelebA 64x64 for
our method and DDPM/DDIM [7, 29].

Figure 8 is realized starting from the same noise input $y_{6}$. Since the
schedule of our method is initialized with the schedule of the DDIM method,
the first steps generate exactly the same image $\hat{y}_{0,5}$ (cf. Eq. 10).
However, it is clear that our model $P_{\theta}$ is able to adjust the noise
schedule such that every iteration results in a meaningful improvement of the
image. At the same time, skipping to many steps at the beginning of the
process makes the baseline struggle to improve the quality of the image.

Figure 9 compares our results with those of DDIM for six and ten iterations
for both LSUN 256x256 datasets. For six iterations, it is evident that even
though both methods employ the the same diffusion model
$\varepsilon_{\theta}$, the baseline DDIM is not capable of generating higher
resolution images in such a small number of denoising steps. For ten
iterations as well, our results are much sharper and have considerably more
contrast in comparison to the baseline method.

Table 2 depicts the mean run-time to generate an image on an Nvidia Titan X
over 1000 generations . It compares our method that adjusts the noise schedule
at every steps with a fully predefined schedule. This table shows that even
though we use VGG11 which is not a cost efficient method to estimate the
noise, the generation time increases by a moderate amount.

##  6 Conclusions

When employing diffusion models with a limited number of steps, it is required
to carefully choose the schedule of the synthesis process. Some of the
previous methods perform a grid search to find the optimal global noise
parameters per each number of steps. However, this fixed selection does not
adjust according to the specific sample that is being generated. Our method
adjusts on-the-fly the noise parameters and thus alters the subsequent states
of the process. Our solution is based on estimating, during inference, the
current noise level. It is, therefore, generic and independent, given the
current sample, from the conditioning parameters. It remains for future work
to check whether the same $P_{\theta}$ network can be used across multiple
datasets.

## Acknowledgment

This project has received funding from the European Research Council (ERC)
under the European Unions Horizon 2020 research and innovation programme
(grant ERC CoG 725974). The contribution of EN is part of a PhD thesis
research conducted at Tel Aviv University.

## References

  * [1] Mikołaj Bińkowski, Jeff Donahue, Sander Dieleman, Aidan Clark, Erich Elsen, Norman Casagrande, Luis C Cobo, and Karen Simonyan.  High fidelity speech synthesis with adversarial networks.  arXiv preprint arXiv:1909.11646, 2019.
  * [2] Nanxin Chen, Yu Zhang, Heiga Zen, Ron J. Weiss, Mohammad Norouzi, and William Chan.  WaveGrad: Estimating gradients for waveform generation.
  * [3] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [4] Chris Donahue, Julian McAuley, and Miller Puckette.  Adversarial audio synthesis.  arXiv preprint arXiv:1802.04208, 2018.
  * [5] Ruiqi Gao, Yang Song, Ben Poole, Ying Nian Wu, and Diederik P Kingma.  Learning energy-based models by diffusion recovery likelihood.  arXiv preprint arXiv:2012.08125, 2020.
  * [6] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  arXiv preprint arXiv:1706.08500, 2017.
  * [7] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  arXiv preprint arXiv:2006.11239, 2020.
  * [8] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [9] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling.  Argmax flows and multinomial diffusion: Towards non-autoregressive language models.  arXiv preprint arXiv:2102.05379, 2021.
  * [10] Aapo Hyvärinen and Peter Dayan.  Estimation of non-normalized statistical models by score matching.  Journal of Machine Learning Research, 6(4), 2005.
  * [11] Keith Ito and Linda Johnson.  The lj speech dataset.  https://keithito.com/LJ-Speech-Dataset/, 2017.
  * [12] Chenlin Meng Jiaming Song and Stefano Ermon.  Denoising diffusion implicit models.  https://github.com/ermongroup/ddim, 2020.
  * [13] Pieter Abbeel Jonathan Ho, Ajay Jain.  Denoising diffusion probabilistic models.  https://github.com/hojonathanho/diffusion, 2020.
  * [14] Nal Kalchbrenner, Erich Elsen, Karen Simonyan, Seb Noury, Norman Casagrande, Edward Lockhart, Florian Stimberg, Aaron Oord, Sander Dieleman, and Koray Kavukcuoglu.  Efficient neural audio synthesis.  In International Conference on Machine Learning, pages 2410–2419. PMLR, 2018.
  * [15] Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila.  Analyzing and improving the image quality of stylegan.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8110–8119, 2020.
  * [16] Diederik Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  International Conference on Learning Representations, 12 2014.
  * [17] Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro.  Diffwave: A versatile diffusion model for audio synthesis.  arXiv preprint arXiv:2009.09761, 2020.
  * [18] R. Kubichek.  Mel-cepstral distance measure for objective speech quality assessment.  In Proceedings of IEEE Pacific Rim Conference on Communications Computers and Signal Processing, volume 1, pages 125–128 vol.1, 1993.
  * [19] Qiang Liu, Jason Lee, and Michael Jordan.  A kernelized stein discrepancy for goodness-of-fit tests.  In International conference on machine learning, pages 276–284. PMLR, 2016.
  * [20] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.  Deep learning face attributes in the wild.  In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
  * [21] Yi Luo and Nima Mesgarani.  Conv-TasNet: Surpassing ideal time-frequency magnitude masking for speech separation.  27(8):1256–1266.
  * [22] Anton Obukhov, Maximilian Seitzer, Po-Wei Wu, Semen Zhydenko, Jonathan Kyl, and Elvis Yu-Jing Lin.  High-fidelity performance metrics for generative models in pytorch, 2020\.  Version: 0.2.0, DOI: 10.5281/zenodo.3786540.
  * [23] Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu.  Wavenet: A generative model for raw audio.  arXiv preprint arXiv:1609.03499, 2016.
  * [24] Kashif Rasul, Calvin Seward, Ingmar Schuster, and Roland Vollgraf.  Autoregressive denoising diffusion models for multivariate probabilistic time series forecasting.  arXiv preprint arXiv:2101.12072, 2021.
  * [25] Ali Razavi, Aaron van den Oord, and Oriol Vinyals.  Generating diverse high-fidelity images with vq-vae-2.  arXiv preprint arXiv:1906.00446, 2019.
  * [26] A. W. Rix, J. G. Beerends, M. P. Hollier, and A. P. Hekstra.  Perceptual evaluation of speech quality (pesq)-a new method for speech quality assessment of telephone networks and codecs.  In 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings (Cat. No.01CH37221), volume 2, pages 749–752 vol.2, 2001.
  * [27] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [28] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.  Deep unsupervised learning using nonequilibrium thermodynamics.  In International Conference on Machine Learning, pages 2256–2265. PMLR, 2015.
  * [29] Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.
  * [30] Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  arXiv preprint arXiv:2010.02502, 2020.
  * [31] Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  arXiv preprint arXiv:1907.05600, 2019.
  * [32] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  arXiv preprint arXiv:2011.13456, 2020.
  * [33] C. H. Taal, R. C. Hendriks, R. Heusdens, and J. Jensen.  An algorithm for intelligibility prediction of time–frequency weighted noisy speech.  IEEE Transactions on Audio, Speech, and Language Processing, 19(7):2125–2136, 2011.
  * [34] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  arXiv preprint arXiv:1706.03762, 2017.
  * [35] Ivan Vovk.  Wavegrad.  https://github.com/ivanvovk/WaveGrad, 2020.
  * [36] Fisher Yu, Yinda Zhang, Shuran Song, Ari Seff, and Jianxiong Xiao.  Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop.  arXiv preprint arXiv:1506.03365, 2015.


# Target Features Affect Visual Search, A Study of Eye Fixations

Manoosh Samiei
Center for Intelligent Machines
McGill University
Montreal, Quebec, Canada
<EMAIL_ADDRESS>
James J. Clark
Center for Intelligent Machines
McGill University
Montreal, Quebec, Canada
<EMAIL_ADDRESS>

###### Abstract

Visual Search is referred to the task of finding a target object among a set
of distracting objects in a visual display. In this paper, based on an
independent analysis of the COCO-Search18 dataset, we investigate how the
performance of human participants during visual search is affected by
different parameters such as the size and eccentricity of the target object.
We also study the correlation between the error rate of participants and
search performance. Our studies show that a bigger and more eccentric target
is found faster with fewer number of fixations. Our code for the graphics are
publicly available at: https://github.com/ManooshSamiei/COCOSearch18_Analysis

_K_ eywords Visual Search, Eye Fixation, Visual Attention, Fixation Duration,
COCOSearch18

##  1 Introduction

Visual Search provides the organisms with many survival benefits such as
finding food and avoiding danger. Organisms that are equipped with a foveated
visual system, i.e. having high visual acuity within 1.5 degree of the fovea,
move their eyes to perceive different parts of the scene with high resolution.
The rapid eye movement that moves the gaze from one location to another
location is referred to as saccade, and maintaining of the eyes on one
location for a certain period of time between the saccades is referred to as
fixation. As the eyes move rapidly during saccades the image received by the
fovea is of low acuity; thus, the detailed processing of visual environment is
mostly done during fixations. Depending on the difficulty of a search task,
humans find a target object in the scene by a certain number of fixations. In
this paper, we investigate the effect of the eccentricity (positioning in the
center of the image), and the size of the target object on the search
performance. In our analyses, all objects except the target are referred to as
distractors(non-target) objects. We define multiple parameters as a measure of
search performance. These parameters are: average reaction time, average non-
target fixation duration time, average target fixation duration time, average
total number of fixations, and average number of fixations on the target
object. In all of these parameters, except the average reaction time, we
exclude the initial center fixation. The initial center fixation refers to a
dot appearing at the center of the screen, at which participants were asked to
fixate, in the beginning of each trial. Furthermore, we study the correlation
between these search parameters and the error rate of the participants.

##  2 Dataset

COCO-Search18 [1] is a dataset that contains the eye fixation information of
10 participants while searching for each of 18 object categories in 6202
images. Among these images, 3101 do not contain the target object. In our
analyses, we only use the 3101 images that contain the target. COCO-Search18
provides us with the fixation location, fixation duration, the total number of
fixations, and reaction time, for each search trial. During data collection,
participants were initially informed of the target category via a display
showing the name of the target category along with sample images that
exemplify that category. Also to avoid potential confusion negative examples
were shown by placing a red X through the object that is not considered as a
member of the target category. Participants then started a trial by pressing a
button on a game-pad controller while looking at the fixation dot appearing at
the center of the screen. afterwards, an image was displayed and the
participant’s task was to quickly determine if the target is present in the
image or not, by responding ‘yes’ or ‘no’ using the right or left triggers of
a game-pad controller. All image stimuli in the dataset have 1680 × 1050 pixel
resolution. The 18 categories of target objects are: bottle, bowl, car, chair,
clock, cup, fork, keyboard, knife, laptop, microwave, mouse, oven, potted
plant, sink, stop sign, toilet, and TV; all of which appear in their natural
context.

##  3 Analysis

###  3.1 Target Area

The characteristics of a target object have significant impact on search
performance. One of these important characteristics is the size or area of the
target object. We assume that the bigger the target, the higher the
visibility. So the bigger targets should be found faster and with fewer
fixations. We investigate this assumption with multiple figures, by plotting
the average reaction time, average number of fixations (excluding the initial
center fixation, including the target fixations), average non-target fixation
duration time (excluding the initial center fixation), average target fixation
duration time (excluding the initial center fixation), and average number of
fixations on the target object versus the target area, in figure 1. Target
area is calculated by multiplying the width and height of the bounding box
surrounding the target object. The calculated areas are then separated into
bins, where every bin has a range of 2000 pixels. Thus, bin 0 covers 0-2000
pixel area, bin 1 covers 2000-4000 area, …, and bin 8 covers 16000-18000 area.
There is no target object with area bigger than 18000 pixels in images.

Figure 1: Search performance versus target object size (area). (a) Average
reaction time. (b) Average fixation number. (c) Average non-target fixation
duration. (d) Average target fixation duration. (e) Average number of target
fixation.

In figure 1, we observe that the response time is higher for smaller targets
and lower for bigger targets, excluding the last bin of the histogram which
contains the biggest target size. The results of the last bin are less
accurate as suggested by the error bars. This is because we have fewer cases
where the target object area is between 16000-18000 pixels. We can thus rely
on the rest of the bins to estimate the relationship between the variables.
The number of fixations as well as distractor fixation duration time also
decrease as the target area increases (probably due to pop-out effect, i.e.
the target object stands out from the non-targets). The target duration time
also decreases for bigger targets. This might be due to less focus needed to
register bigger targets’ information. The average number of fixations made on
the target is relatively constant, with slightly more average fixations on
bigger targets. This is intuitive; as the bigger the target, the higher the
probability of fixating at it, since it occupies more space in the image.

###  3.2 Target Eccentricity

Another crucial factor in determining the search performance is the
eccentricity of the target objects, i.e. the distance of the target from the
center of the image. It has been believed that humans tend to look toward the
central parts of images. Also, during trials the participants initially placed
their gaze on a dot in the center of images. We therefore assume that if a
target is at the center of the image, participants should be able to find it
more rapidly. We test our hypothesis by plotting the previous variables but
this time versus the targets eccentricity. We compute the euclidean distance
between the center pixel of the target’s bounding box and the center pixel of
the image. We then divide the distances into 6 bins, each containing 50 pixel
euclidean distance. Bin 0 corresponds to 0-50 pixel distance, bin 1 contains
50-100 pixel distance, …, and bin 5 contains 250-300 pixel distance. The
results can be seen in figure 2

Figure 2: Search performance versus target eccentricity (target’s euclidean
distance from the center of an image). (a) Average reaction time. (b) Average
fixation number. (c) Average non-target fixation duration. (d) Average target
fixation duration. (e) Average number of target fixation.

The results show that the average reaction time, average number of fixations
and average distractor fixation duration increase as the target’s distance
from the center increases. This validates our previous assumption that targets
further away from the center are harder to find with more fixations and longer
response time. The observers also fixate longer at non-target objects while
looking for the distant targets and therefore have higher distractors fixation
duration. The number of fixations made on the target and the duration of these
fixations are almost constant across various levels of targets’ eccentricity.

###  3.3 Error Rate

Finally, we investigate the correlation between the error rate of participants
with average reaction time, average number of fixations, average non-target
fixation duration, and average target fixation duration, in figure 3. The
error rate is defined as the number of incorrect responses (by all
participants) divided by the total number of responses for each bin of the
histograms.

From figure 3, we can derive that longer reaction times correspond to higher
error rates. As in more difficult search images that the target is less
detectable, participants spend longer time searching the images, and some
eventually fail to find the target. This explanation does not contradict our
earlier discussion on individual differences in reaction time. We previously
stated that participants who have longer average reaction time had less number
of incorrect responses, as a result of their more careful search. However,
trials with higher reaction times contain both types of participants: those
who perform exhaustive search and those who perform non-exhaustive search.
Thus, the individual differences are not the focus of our argument here. The
same pattern exists for the number of fixations. A higher number of fixation
typically corresponds to a more difficult search, and consequently higher
error rates. Furthermore, fixating at non-target objects for a duration of
200-300 milliseconds correspond to the highest erroneous responses. Also,
shorter fixations at target objects correspond to more incorrect answers. Thus
we can infer that when participants recognize the target, they fixate at it
longer than when they look at the target but do not recognize it.

Figure 3: Ratio of the incorrect responses to the total number of responses
versus: (a) Reaction time. (b) Fixation number. (c) Non-target fixation
duration. (d) Target fixation duration.

##  4 Discussion and Conclusion

A potential application of these results could be in visual marketing, i.e.
using visual information to guide customers’ attention. By extending these
analyses to a 3D environment, we can direct customers’ attention toward
healthier products. For instance, our data analyses show that an increased
target eccentricity decreases the distraction (attention to non-target
objects) and makes the target search easier. Same principal also applies in
marketing strategies. In [2], Wedel suggests that “a larger number of facings,
and top and/or central placement of products on the shelves increases
attention to and consideration of the brand [2].” Hence to encourage healthy
products, one could place them at the top and central levels of the shelf
which are more aligned with humans’ average height.

Another factor that facilitates the visual search is the bigger size of the
target, which causes more visibility. Similarly, Wedel suggests that in print
advertising and banners, the size of the ad has a positive effect on
attention. Hence by choosing the neighbor products of a healthy product such
that the healthy one is more differentiating (e.g. slightly bigger) and
visible, we might increase the shoppers’ chance of buying healthy products.

Another important component in encouraging healthy products is by directing
customers’ attention to the health warnings and nutrition labels on the
products’ package. For instance, Wedel discusses that information near the
center of the label, which is typically dense, is less visible compared to the
bottom or top of the label. Also, by using colors and pictures, health
warnings could be designed more noticeable. [2]

## References

  * [1] Yupei Chen, Zhibo Yang, Seoyoung Ahn, Dimitris Samaras, Minh Hoai, and Gregory Zelinsky.  Coco-search18 fixation dataset for predicting goal-directed attention control.  Scientific Reports, 11, 04 2021.
  * [2] Michel Wedel and Rik Pieters.  Eye tracking for visual marketing.  International Journal of Cooperative Information Systems, 2008.