# Knowledge mining of unstructured information: application to cyber-domain

Tuomas Takko
Department of Computer Science
Aalto University School of Science
00076, Finland
<EMAIL_ADDRESS>Kunal Bhattacharya
Department of Industrial Engineering and Management
Department of Computer Science
Aalto University School of Science
00076, Finland
Martti Lehto
Faculty of Information Technology
University of Jyväskylä
PO Box 35, 40014, Finland
Pertti Jalasvirta
Cyberwatch Finland Oy
Tietokuja 2, 00330, Finland
Aapo Cederberg
Cyberwatch Finland Oy
Tietokuja 2, 00330, Finland
Kimmo Kaski
Department of Computer Science
Aalto University School of Science
00076, Finland
The Alan Turing Institute
96 Euston Rd, Kings Cross, London NW1 2DB, UK

###### Abstract

Cyber intelligence is widely and abundantly available in numerous open online
sources with reports on vulnerabilities and incidents. This constant stream of
noisy information requires new tools and techniques if it is to be used for
the benefit of analysts and investigators in various organizations. In this
paper we present and implement a novel knowledge graph and knowledge mining
framework for extracting relevant information from free-form text about
incidents in the cyber domain. Our framework includes a machine learning based
pipeline as well as crawling methods for generating graphs of entities,
attackers and the related information with our non-technical cyber ontology.
We test our framework on publicly available cyber incident datasets to
evaluate the accuracy of our knowledge mining methods as well as the
usefulness of the framework in the use of cyber analysts. Our results show
analyzing the knowledge graph constructed using the novel framework, an
analyst can infer additional information from the current cyber landscape in
terms of risk to various entities and the propagation of risk between
industries and countries. Expanding the framework to accommodate more
technical and operational level information can increase the accuracy and
explainability of trends and risk in the knowledge graph.

_Keywords_ knowledge graphs, knowledge mining, cyber intelligence

##  1 Introduction

With today’s rapidly evolving cyberspace the cyber security industry is facing
numerous challenges including increasingly persistent and devious threat
actors, a daily flood of data full of extraneous information and false alarms
across multiple, unconnected security systems. As the organizations are more
and more interconnected and dependent on the same infrastructures, the concept
of cyber awareness becomes more commonplace in organizational decision-making.
For instance, one can consider an organization’s attack surface to consist of
the internal surface as well as external surface through interconnected
entities. Vulnerabilities in the infrastructure of subsidiaries and supply
chains related to an organization can increase the risks related to the
organization itself. In addition there is a serious shortage of skilled
professionals to analyze and disseminate these incidences for organizational
decision-making purposes. The key challenge is to establish preparedness and
resiliency using these limited available resources.

To tackle these issues, some organizations try to incorporate threat data
feeds into their network, but do not know what to do with all that extra data.
This in turn adds to the burden of analysts as they may not have the tools to
decide what to prioritize and what to ignore. To tackle such challenges one
needs a framework to effectively harness the available sources of data and to
holistically process complex information and intelligence on cyber threats in
relation to world politics, technological development, economic and military
interests and conflicts. Solutions for dealing with an overflow of information
have been implemented in various ways, such as curated information feeds, SOC
reports or, most recently, linking different reports and records together as a
knowledge graph. The concept of knowledge graphs has been adopted for
structuring and processing the technical information of known vulnerabilities,
malicious IP addresses and other relevant threats in the domain, as well as
the related entities such as software developers. These technical level
ontologies such as STIX [1], UCO [2] and STUCCO [3] consist of various
technical or higher level entities and their relationships, such as parts of
the cyber kill chain. These technical level records can be linked to other
ontologies and datasets by ontologies such as UCO [2]. While these technical
level ontologies have excelled in ways of addressing the cyber-linked events
with microscopic focus, there still remains ample scope to portray the cyber
landscape in a clear and readable manner for the purpose of executive decision
making taking into account the monitoring of trends and building of awareness
at a strategic level.

In this study we present a strategic level framework for analyzing the cyber
domain by using public reports of various incidents, with the objective to
present a broad but condensed view on the open information available on the
current cyber landscape. Such frameworks have been proposed in the past, but
only a few studies present methods for practical and automated construction of
visual and knowledge graph based solutions. Our work shares a similar goal to
the framework proposed by Böhm et al. [4], with the objective to provide cyber
analysts a visual and readable way for analyzing complex cyber attack reports.
The implementation of the process pipeline of the framework has similar
structure to the work by Joshi et al. [5], namely by incorporating modules for
extracting entities and their relations from unstructured data and
transforming these triplets into a knowledge graph with an ontology. Also
similarly with the frameworks presented in [5, 6, 4], we extend the knowledge
graph constructed from unstructured data by joining information from separate
sets of data. We connect these separate subsets of knowledge graph (i.e.
separate incidents) by crawling and querying for additional records and
information about the entities from other open sources such as DBpedia [7],
The addition of extraneous information is aimed to sufficiently fill the
relations in the ontology as well as to introduce interconnectedness to the
knowledge graph for the purpose of constructing measures for risk. Finally, we
describe and demonstrate that the constructed knowledge graph can be used to
determine a risk level for the entities in the graph by using open datasets of
historical data on reported cyber attacks. This risk level could be used in
predicting the likelihood of future cyber attacks, as well as in situational
awareness and preparedness.

##  2 Related Work

The concept of knowledge graph, where complex information is represented as
nodes and edges with semantic relations [8], has become increasingly popular.
Improved methods for extracting meaningful information and entities from
unstructured text, see e.g. [9], as well as the increasing coverage of linked
data from various endpoints (such as DBpedia [7]) has made it possible to
query for extraneous information and to connect information from text to
existing records of various entities, events and items. The applications of
knowledge graph ranges from systems in healthcare [10, 11] to search systems
and scientific document indexing [12].

In terms of cyber security and cyber intelligence, the use of knowledge graphs
and linked data has been prevalent due to the mostly structured nature of the
recorded data from intrusion detection systems (IDS), software vulnerabilities
and malicious actors [13]. For instance, online databases like NVD
111https://nvd.nist.gov/, CVE 222https://cve.mitre.org/ and CWE
333https://cwe.mitre.org/ provide regular updates on software and system
vulnerabilities on a structured format. Cyber defense benefits from synergy
and cooperation, but sharing and interpreting various threat intelligence
reports and databases requires standardized formats and protocols for the
analysts to have a common language [14]. Thus, there has been extensive
research done for constructing taxonomies and ontologies in order to
standardize the formats of linked data on threat intelligence such as software
and system vulnerabilities, malware [15], and attacks in general [2, 1]. Using
these types of ontologies to provide formalism and structure, various
framework-type approaches to situational cyber awareness have been developed,
for instance for different vulnerabilities, assets and network topologies
during cyber attacks [6, 16, 17, 18, 4]. Other approaches for extracting
relevant information on cyber attacks and vulnerabilities from varying
unstructured text sources, such as social media, have been used as early
warning signals for risen cyber risks [19, 20, 21, 21, 22, 23, 24].

Our study is related to work by Joshi et al. [5], Li et al. [6] and Kejriwal
and Szekely [25] which describe and implement methods for a pipeline with the
objective to turn unstructured data into a knowledge graph with the help of a
novel ontology. Joshi et al. [5] describe a framework that processes
unstructured web text from security bulletins and blogs alongside with the
vulnerability data from the NVD, CVE and CWE datasets, recognizes entities and
concepts connecting them to linked dataset by using DBpediaSpotlight for
enriching the information. This data is then processed into triplets for
constructing a knowledge graph that enables automatic consumption of the
threat landscape. Li et al. [26] have proposed a framework and an
implementation from knowledge graph to knowledge base with a similar principle
and structure. Instead of focusing on software and hardware vulnerabilities,
the focus of the framework is on capturing cyber attacks accurately with
attacked device properties, attack properties and attack features included in
the ontology. These datapoints are gathered from the network level information
using a convolutional neural network classifier. The third relevant study to
our approach is by Kejriwal and Szekely [25] that describes an information
extraction method for unstructured text, scraped from illicit web domains. The
authors propose methods for annotating and extracting information such as
entities and locations using unsupervised methods based on initially annotated
corpora. The proposed method for information extraction has turned out to
compare well with the existing information extraction methods.

The framework we present in this paper shares principle level similarities to
the studies described above, in terms of the structure of data processing
pipeline and the methods. The general objective is also similar to ours, i.e.
to process unstructured text scraped from various unknown format news sources
into a knowledge graph. This shares similarities to the general objective of
the framework Li et al. [6] in portraying cyber attacks in a knowledge graph
format. While the system in [6] processes data from the network and
information systems of an entity, our strategic domain approach is restricted
to open source information from security bulletins and news sources, thus
limiting the number of features and amount of information available. Our
approach in terms of information extraction has similar principles to the work
of Kejriwal et al. [25], with the objective of processing information from
unknown domains and extracting the relevant entities and their relationships.
We extract the entities using a named entity recognizer (NER) from Spacy and
compare the extracted relevant entities to the knowledge base of DBpedia using
DBpedia spotlight, similar to [5].

Both the unstructured text used in our framework as well as the output
knowledge graph can be categorized as cyber threat intelligence (CTI), which
refers to a dynamic, adaptive technology that leverages large-scale threat
history data proactively to block and remediate future malicious attacks. CTI
recognizes indicators of attacks as they progress and essentially put these
pieces together with shared knowledge about the attack methods and processes
[27]. A cyber threat intelligence capability allows organization to merge and
analyze multiple data feeds to gain deeper insights into the system weaknesses
and spread of attacks. Collated data from cyber threat intelligence provides
the context of complex threats, as well as it can help develop more proactive
and defensive mechanisms.

##  3 Methods and Materials

We propose a framework for processing unstructured information into a
knowledge graph. The framework consists of three distinct modules, namely an
information retrieval module, an information extraction module and finally a
module for risk measurement and graph analysis. Even though the source
material consists of written news and reports, the framework implementation
does not reuse the text or otherwise infringe the copyright of the authors.
The first module aims to gather and process relevant unstructured information
from unspecified online sources. It begins by collecting a list of urls of
news reports of cyber attacks that are of interest to the analyst. We used
Python libraries for requesting the page from the given url, if the source
allowed scraping, and cleaning the text by removing irrelevant content such as
html-tags, other urls or embedded content. This cleaned text is then processed
by removing stop words and extracting the relevant entities and their
relationships in the information extraction module. The relationships between
the target and the attacking entities are extracted as a triple in the form of
“target - attackedBy - attacker”. The extracted entities are compared to the
results of DBpedia Spotlight [28], which finds related records in DBpedia [7]
as linked data, which we then use to complete the fields in the ontology.
DBpedia Spotlight annotates the entities found in the text and performs
disambiguation using the context of the phrases. In an ideal situation, these
entities are correctly resolved and found in DBpedia, but in a situation where
this additional information is not found, we omit the information while
keeping the entity as it was recognized by the Spacy NER [29] and adding the
triple of attacker-victim relationship. In a complete system one could also
crawl other sources for additional information, such as software
vulnerabilities. Lastly, we use the generated knowledge graph for constructing
a naive measure for risk. The risk level in this study is based on the
frequency of attacks in connected entities in the resulting knowledge graph.

These modules were implemented in Python 3.7 using libraries for web scraping,
SpaCy [29] for information extraction and Networkx [30] for graph analysis.
For the purpose of demonstrating our approach in this study, we opted to use
the openly available datasets of cyber attacks from Hackmageddon [31]
containing reported attacks from year 2017 to 2020. The human-annotated
dataset contains descriptions of targets, attackers, attack types, dates,
countries and links to the original reports, which we use to obtain the full
text report. The remaining fields are used in the evaluation of information
extraction methods of this framework as well as to substitute for missing
relationships from DBpedia. In a real use-case an analyst would use their own
news sources or knowledge bases and use the framework via a user interface, or
other applicable method. However, for the sake of clarity we restrict the
number of cases analyzed in the knowledge graph to the contents of the
Hackmageddon dataset.

Figure 1: Process pipeline of the proposed knowledge mining framework. The
framework and the modules are depicted as boxes with the correct order. The
pipeline retrieves, cleans and extracts information from unstructured text and
computes graph-level features for the analyst to investigate in the final
knowledge graph.

###  3.1 Information Extraction

The primary aim of this module is to identify the victim and the perpetrator
of an attack for a given piece of text. Here we will broadly describe the
concept and finer details of the method will be reported elsewhere. The
process comprises of three steps: extraction of subject-verb-object (SVO)
triples, scoring for named entities, and ranking of entities. The SVO triples
are extracted using a mixture of rule based methods [32] and parsing of the
dependency tree [33]. We begin by extracting noun phrases and verb phrases.
For the base noun phrases we use Spacy noun-chunks, while for the verb phrases
we search for the most general pattern: particle + adposition + verb/auxillary
+ particle + adposition + adjective/adverb + adposition. Similarly, we extract
lone adpositions, adverbs and adjectives. To take into account complex
predicates, we also incorporate light verb constructions [34] that includes a
noun within, for example, the phrase ’gained access to’. Additionally, at the
beginning we identify Hearst patterns [35] from a pre-compiled list that we
use to link nouns in the dependency tree.

Following the extraction of the subject, the object and the predicate phrases
we construct a coarser dependency tree using the dependency tree parsed by
Spacy and the tokens contained inside the phrases. Using this coarser tree and
taking the predicates we generate the triples. The tree is parsed such that
conjugated verbs are crawled for listing all subjects or objects.
Simultaneously, we perform a co-reference resolution for the set of noun
phrases (subjects and objects) using the package NeuralCoref [36]. The
resulting output from the resolution are clusters of noun phrases, where each
cluster implies a single co-referenced mention. At this point we create a map
between the named entities in the text to the clusters. Using this map we
replace the subjects and objects in the triples with the named entities. Next,
we label each triple as active or passive by checking the dependency labels of
the tokens inside the predicate.

For each named entity we associate a ‘target score’. The scoring is done using
a list of attack tokens. The list is initially made with a set of seed tokens,
such that ‘hacked’, ‘breached’, etc., and further are extended by including
the inflections. Given an SVO triple we check for the presence of an attack
token inside the predicate. If a token is found and the triple has an active
voice then the entity corresponding to the object gets its target score
incremented by $+1$. If the voice is passive, the score corresponding to the
subject is incremented. The final scores are obtained by repeating the process
for all the triples. In addition, the number of occurrences of each entity and
the order in which they appear in the text are taken into account. To identify
the possible primary target mentioned in the text we do the following. For
each entity, the min-max normalized values of the target score, the frequency
of appearance, and the order (reversed) are added. Then the entities are
ranked in descending order of the compound score. We find that the above
method yields an accuracy of 60$\%$ for the top-most ranked entity to be the
true target. However, the accuracies for the true target to be in top-2 and
top-3 ranked entities are 75$\%$ and 83$\%$, respectively. If solely the
frequency or the order of appearance is taken into account the accuracy for
the true target to be in the top-most and top-3 entities are around 50$\%$ and
70$\%$, respectively. Note that in general a news piece has 10-20 entities,
and therefore, a baseline accuracy would be much lower in comparison. In our
future work we will provide methods whereby models can be trained on
linguistic features, and quantities like frequency and order.

###  3.2 Domain Ontology Structure

In the framework of this study we will use a novel domain ontology for
defining the elements and the relationships appearing in the knowledge graph.
The ontology is depicted in Fig. 2. We constructed this cyber-specific
ontology for the purpose of capturing knowledge on the entities and actors at
a strategic level, i.e. at a level that describes real world structures and
helps in constructing a bigger picture of the whole field at once. The
extracted information for each report on a cyber attack depicts the main
attributes of an organization and ideally forms a connected network, in which
visualizing trends and campaigns along with individual attack incidents is
possible. The entities, such as companies and organizations, are described by
their countries and industries as well as by their products and possible
child-parent relationships to other entities. Different countries, products
and industries appear in the knowledge graph as nodes alongside the
organizations and attacking entities. We further categorize industry and
country nodes into central nodes and rest of the nodes non-central.

As we are here using DBpedia Spotlight to obtain information on the extracted
entities, the ontology can be considered to share similar meaning fields as
DBpedia. The relationships and their counterparts in DBpedia’s syntax are
depicted in the table in Figure 2.

DBpedia | Study
---|---
foaf:name | Name
dbo:industry | hasIndustry
dbp:locationCountry | hasCountry
dbo:product | hasProduct
dbo:parentCompany | hasParent

Figure 2: A novel strategic level cyber ontology. Subjects and objects are
entities (boxes) that are connected via their relative predicates (arrows).
The labels tell the class names in the ontology. The relationships between the
extranous data from DBpedia (labeled DBpedia) and the strategic-level ontology
presented in this study (labeled Study). The triple describing a cyber attack
is present only in the novel ontology of this study. The hasParent
relationship is from an entity to another entity.

When populating the knowledge graph using this ontology, we are not setting
any requirements or rules to the types of categories that might appear in the
automated construction process. Every entity is considered as a type of
organization, with the distinguishing feature being the type of industry the
entity has. For instance, a government organization would have an industry
indicating public service. The set of entity attributes for describing cyber
attacks and events in our ontology were chosen as such in order to maintain
readability and simplicity of the knowledge graph. It is also worth noting,
that increasing the number of predicates for a given entity also affects the
network properties of the resulting knowledge graph. Naturally, the number of
these predicates can be increased if the analyst requires other information
within the boundaries of information available, but the current set acts as a
backbone for the purpose of this study. The finalized result of the knowledge
graph using the ontology presented here contains five types of nodes (entity,
country, industry, product, attacker) and the five relationships described
above. An example of a subset of the resulting knowledge graph is shown in
Fig. 5.

###  3.3 Measuring Risk Level

In addition to the situational awareness and human readability provided by the
knowledge graph on recorded cyber attacks, we aim to quantify risk for the
entities in the graph. The classification and prediction of cyber attacks with
information limited to open source reports, results in high uncertainty. It is
also prone to be biased by the data as organizations may not notice the
attacks or omit reporting them to the authorities and the public due to
potential damage to their brand and image. Thus, rather than trying to predict
the occurrence of cyber attacks, this module focuses on measuring risk from
the relationship between sequential attack records.

The level of risk in this study is measured from the network structure of the
resulting knowledge graph. This structure provides us with links, direct and
indirect, between different entities targeted by cyber attacks. As the format
an attack is recorded in our knowledge graph consists of the SVO-triple and
the recorded date, we can construct risk levels for the so called central
nodes, which consist of industry nodes and country nodes in the graph. The
risk levels for the central nodes in the knowledge graphs are then used as a
proxy for the connected entities via the linkages in the network structure.

In this initial model, we consider the risk $r$ for a single central node $c$
as a sum of decaying exponentials between the current time $t$ and the time
when the attack in question was recorded $i$.

$r_{c}(t)=\sum_{i}^{t}e^{i-t}.$ (1)

The time step can be chosen for an appropriate duration, considering the type
of data represented in the knowledge graph.

We also calculate the second central neighbors for the entity nodes by
constructing a projection (see Fig. 4) of the network in such a way that the
central nodes sharing entity nodes are connected in the projection. The
projection can be used to provide weights on the links between the central
entities based on the number of shared entities, but due to the fact that the
projection should be temporal and change over time in terms of the evolving
amount of common entities between the central nodes and in order to keep this
investigation simple we consider every link with equal weight. This allows us
to investigate whether the risk propagates across the network and whether
certain types of nodes have more importance when considering the weights in
the risk measures.

For a non-central entity $e$ in the graph (i.e. an organization or a company),
the risk level at a certain time step can be calculated from the neighboring
central nodes by calculating a sum of the means

$r_{e}=\overline{r_{e}(C)}+\overline{r_{e}(I)}+\overline{r_{e}(c)}+\overline{r_{e}(i)},$
(2)

where $\overline{r_{e}(C)}$ denotes the mean of risk for the first neighbor
country type nodes, $\overline{r_{e}(I)}$ denotes the mean of risk for first
neighbor industry nodes and $c$ and $i$ denote the risk for the second
neighbor countries and industries in the projection, respectively. The second
neighbors in this measure are considered to be the immediate neighbors of the
central nodes $C$ and $I$ in the projection, $C$ and $I$ being connected to
the focal entity $e$ in the knowledge graph. We construct these risk measures
into a dataset, in which for each day any non-central entity can be evaluated
using a vector of these four values.

##  4 Results

In order to test our knowledge mining framework we combined the dataset from
the reported cyber attack timelines for each month and year from January 2017
to April 2021. For each article we crawled the original text whenever possible
and processed its text through the NLP pipeline, extracting the attacked
entity, the attacking entity and matching them with the entities recognized by
DBpedia Spotlight. As the Hackmageddon data contains these fields already
annotated by humans, we also compared the extracted entities to the fields in
the original data. Considering the shortcomings of classifying industries in a
standard way or obtaining the operating countries for multi-national or lesser
known organizations not present in DBpedia, we add the annotated fields from
Hackmageddon in the knowledge graph as the industries and countries for the
entities in addition to the ones obtained from DBpedia. In order to maintain
the integrity of the dataset, we omit the rows where the victim is not
specifically reported (i.e. various victims in multiple countries) or the
countries or industries are not exact in a similar manner. The resulting nodes
are resolved by comparing them to one another using string similarity and
sufficiently similar nodes are joined. The frequency of reported attacks in
our dataset is shown in Fig. 3. As can be seen, the number of reported attacks
per month shows an increasing trend but has high variability, which hints that
the reporting can be incomplete during some months.

Processing the Hackmageddon dataset using the above-mentioned methods resulted
in a knowledge graph of 12,966 nodes and 18,476 edges. The filtered and
processed data leaves us with 6825 attack SVO triples. As we used the industry
fields from the annotated dataset in addition to the ones obtained using
DBpedia Spotlight, the network consists of a single connected component. This
also affects the network structure as the standard industry classifications
are more general than the ones used in DBpedia. The nodes with the highest
degree are industries (public sector, healthcare) and countries (US, UK). The
non-central nodes with the highest degree are the tech giants such as Google
and Amazon and the users of their products such as the Android operating
system. The finalized knowledge graph based on the dataset from Hackmageddon
cyber attack timelines from January 2017 to April 2021 and extraneous
information from DBpedia is shown in Fig. 4 and a more descriptive subset of
the same graph is shown in Fig. 5.

Figure 3: Number of monthly incidents in the filtered dataset. Records that
did not produce a single coherent SVO (subject-verb-object) triple for the
attack were omitted to produce a coherent knowledge graph. The time of
occurrence of an event (a triple) can be wrongly recorded or reported long
after the attack. It is notable from the number of attacks that the reporting
is not uniform and some months are much less populated than others, resulting
from human error or bias.

Figure 4: (Left) The resulting knowledge graph from the Hackmageddon dataset
of 2017-2020. The edges are coloured according to the interaction in the
related triples such that red edges represent the attack triples (attackedBy),
blue edges represent hasCountry, green edges represent hasIndustry, purple
edges represent hasProduct triples, and turquoise edges represent hasParent
triples. (Right) The projection of the central nodes used in the construction
of the entity risk measures. The projection is constructed by linking central
nodes sharing common neighbors such that the weight of every link is uniform
regardless of the number of common neighbors. Figure 5: An example subset of
the knowledge graph showing an egocentric network from the company Microsoft.
The central entity is connected to the reported malicious entities (red
links), the industries reported in the dataset as well as the ones obtained
from DBpedia (green links), country (blue link), products (purple links) and
child companies (turquoise links). The network is a subset of the knowledge
graph with nodes and links of a single step from the focal node. The central
nodes of this subset are connected to the focal node by green and blue links.

In order to construct the risk measure, we first binned and ordered the
recorded attacks and the triples into daily bins, after which we calculated
the number of attacks towards the entities connected to the central nodes. The
risk levels for each central node were calculated using the formula in Eq. 1.
For each non-central entity illustrated in the resulting knowledge graph, we
construct the averages of the first and second neighbor countries and
industries in the graph into sets of four variables for each day. From these
sets the way we construct a dataset with “attack days” and “non-attack days”
by letting the values for the attack days to be the values for the previous
time step and sampling a non-attack day as a random day between the beginning
of the dataset and the recorded attack date. By this process we obtain a
dataset with 11,028 observations, with equal amount of points in both classes.
We investigate the differences between these two thinly separable classes by
first investigating the distributions in the risk values and then by
performing a simple logistic regression classification and dimensionality
reduction. Constructing a set of binary values from a measure such as risk can
be considered as elementary, however, the aim in this study is not to
explicitly predict the attacks, but to demonstrate the feasibility of the
framework. The attacks recorded in this set of data are also the ones were the
attack itself is already operational and deemed newsworthy. Some organizations
might experience attacks or preparations of an attack on a daily basis, but
those are not reported in the news whether due to their commonality, minor
damage or because the organization is not releasing the information.

The standardized distributions for the four different variables to the right
in Eq. 2 are shown in Fig. 6. Overall, the distributions between the classes
seem to differ from one another, the attack distribution having a longer tail
and more positive mean. It is notable that the distribution of the first
neighbor’s (country) risk is very similar between the attack days, whereas the
second neighbor’s risk shows a difference between the attack days and non-
attack days. The differences between attack days and sampled attack days in
the distributions or risk values hint that there is some commonality within
the classes, thus encouraging us to investigate it further. Performing a
dimensionality reduction in the form of principle component analysis (See Fig.
7 left panel) results in components explaining 94% of the variance (83% and
11% for the two components). The component weights are shown in Table 1. These
weights can be interpret as two different risk factors, industry-based and
system-based risk. The industry-based risk in this situation can be reasoned
from the higher factors for the industry nodes in the first principal
component and the system-based risk can be considered due to negative factors
to all but $i$. Also judging from the Figure 7, the second component
differentiates between risk from the secondary industries and the first
neighbor nodes as well as the second neighbor country. The small factors for
first neighbor country $C$ are apparent from the overlap in the variable’s
distribution shown in Figure 6.

Figure 6: The distributions of resulting risk levels of attack and non-attack
days in the knowledge graph. (Top) The sum of the four variables, (Second row)
The standard score for risk in the first neighbor country node $C$ and the
standard score for the average risk in the first neighbor industry nodes $I$.
(Third row) The standard score for average risk in the second neighbor
countries $c$ and second neighbor industries $i$. The values are standard
scores for recorded attack days and equal number of sampled non-attack days to
the same entity before the attack day.

In order to further interpret the usefulness of the constructed risk variables
we perform a logistic regression on the dataset of attack days and non-attack
days. Training a classifier with a training and validation set constructed
from the data results in a 69% accuracy, which proves that there is indeed
some relationship between the attacks in the network, at least in a temporal
sense. The coefficients for the logistic regression (see Table. 1) show that
the first neighbor country has a very minor weight in the classifier function,
but looking at the corresponding distribution in Fig. 6 reinforces this as the
two classes are highly overlapping. The interesting fact is that the
coefficient of second neighbor country is the highest, which could be
interpret as some countries being the catalysts for chains of attacks. The
weights themselves are comparable as the values fed into the logistic
regression are standard scores within the distribution of each respective
value. The confusion matrix for the logistic regression is shown in Fig. 7,
showing the fractions of correctly and incorrectly predicted labels, 1 being
the label ”attack day” and 0 being the label ”non-attack day”. As one would
expect, the accuracy for correctly predicting ”non-attack days” is higher than
correctly predicting the ”attack days” due to the differences in distributions
of the constructed variables.

Table 1: PCA component weights and coefficients from fitting a logistic
regression to the data. The variables are notated as first neighbor country
($C$), first neighbor industry ($I$), second neighbor country ($c$) and second
neighbor industry ($i$).

Variable | PCA 1st component | PCA 2nd component | Logistic regression coefficient
---|---|---|---
$C$ | 0.075 | -0.127 | -0.004
$I$ | 0.516 | -0.737 | 0.025
$c$ | 0.176 | -0.377 | 0.039
$i$ | 0.835 | 0.547 | 0.007

Figure 7:  (Left) First two components of PCA dimensionality reduction on the
risk data consisting of the four variables (average risk values of the first
and second countries and industries). The first component resulted in positive
weights for the secondary central nodes and the second component resulted in
negative weights for the same variables. The difference shown in the plot
hints that the method produces higher risk levels for the dates when the
attacks occur. (Right) Confusion matrix obtained by testing a logistic
regression classifier on the proposed risk measures. The data was split into
training and testing sets with a 60 to 40 ratio. The overall accuracy of the
classifier was 0.69 and F1 score was 0.65.

##  5 Discussion

As the society is becoming increasingly dependent on information technology
and data, new kinds of knowledge and technical approaches are needed to
reinforce the resiliency of connected systems. At the same time the need and
number of skilled domain experts required for monitoring the field, designing
secure systems and making decisions keeps growing. In this study we presented
a novel knowledge graph based framework for constructing a strategic level
mapping of the current and past cyber attacks from unstructured reports in the
open online sources. The aim of this framework is to structure textual data
into computable form, facilitate measures for risk and help expert analysts to
process and view a large amount of reports in an automated manner. The
pipeline combines methods and techniques from NLP and complex networks,
starting with scraping and retrieving of articles from online sources,
extracting relevant entities and the correct subject-verb-object or SVO-
triples on the attacked entities and the attacking actors, and finalizing by
constructing a knowledge graph with an ontology consisting of five types of
nodes and relationships (see Fig. 2). We have implemented the pipeline and the
related algorithms in Python 3.7 programming language and created a knowledge
graph using the pre-annotated dataset from Hackmageddon that contains over
7000 recorded attacks between January 2017 and April 2021 (See Fig. 4). With
this knowledge graph we have also constructed a measure of risk, which is
based on a decaying time-based function and the network structure of the
knowledge graph.

The analysis of the risk measure has shown that there can be some level of
temporal and structural correlation between the different recorded attacks.
The distributions between the ”attack” and ”non-attack days” in the dataset
differ from each other to a degree (See Fig. 6) and performing a logistic
regression classification on the knowledge graph data yields a decent accuracy
(See Fig. 7). This reinforces the usefulness of our strategic level ontology,
which assumes that similar entities have some common factors that are not
always publicly reported and that similar companies are often targeted during
some period of time. The relationship between different entities in the
knowledge graph can be more complex than just surface level similarities and
contain hidden variables, such as the used systems and protocols, which could
explain some of the pathways between the various entities that are connected
to different central nodes. Correlations between attacks and attacked entities
in the knowledge graph can also be because the attackers focus on certain type
of entities for their own reasons. The risk measures presented here are
intended for evaluating our framework rather than investigating the real life
risk, which consists of numerous different dimensions in addition to the ones
in this framework. The results show that our framework has potential in
formulating a measure of risk in the knowledge graph in addition to the
capabilities on visualizing a large dataset for situational awareness and
investigation.

The advantages of our framework are its generality, explainability and
expandability. The generality allows us to consider a large variety of
different types of attacks and entities with limited information and
resources. The information used to construct the strategic level knowledge
graph with high abstraction is mostly available in online sources such as
DBpedia and the extraction of the victim-attacker triple from unstructured
data can be performed efficiently with high accuracy using the methods
presented in this paper. The design of the ontology is human-readable and easy
to explain and can thus serve as a tool for communicating the events and
investigations with other people. As the framework can be used to semi-
automatically produce a contextual situational picture of the cyber world and
compute levels of risk for various entities, it could also serve as a tool for
decision makers and management in different companies with limited resources
on cyber intelligence and analysis. The framework can facilitate adding
extraneous information, such as software vulnerabilities, software used by the
entities and importance of entities in various supply-chains and systems,
moving the knowledge graph towards a more operational scope. Such
expandability could improve the various measures for risk as well as the
network structure, and giving a more realistic picture of the system. However,
the availability of such information is restricted and for the scope of this
study we decided to keep the network structure human-readable by having only
the essential nodes for describing general entities and incidents and
relationships between them.

There are also some possible limitations of our framework. The risk measure
used in this study is based on the network structure of the resulting
knowledge graph and thus the design choices have high impact on the variables
constructed. These results can be biased and affected by numerous sources,
such as human error and bias in the reporting of the incidents and collecting
the incidents to the dataset. Other limitations can rise from the accuracy of
processing the unstructured data into a knowledge graph as well as the types
of extraneous information added to the graph, such as the types of industry
nodes. The generality of the industries have a direct effect on the structure
of the network and the related properties. The design and dataset in this
study were chosen due to the ease of performing preliminary investigations
with the framework and the limitations of open and annotated data sources. In
addition to the human errors and design choices having a language specific
tools for NLP, causes the information retrieval to be restricted to a certain
part of the world, which in itself limits the amount of information available
and the types of entities and reported incidents. On the other hand, in an
application of the framework the analyst is eventually choosing the source
material of their interest with the knowledge of the scope of their
investigation.

In our future research, we plan to improve the methods for information
extraction from unstructured sources for better accuracy and generalization,
which would improve the truthfulness of the knowledge graph as well as provide
a possibility for better automation in terms of facilitating the framework as
a continuous process. Constructing language-agnostic tools for this task would
also solve the problem of having a limited focus on certain parts of the
world. As discussed previously, adding new information from other sources,
such as system information of entities and various vulnerability databases,
could increase the accuracy of the risk model, should such information be
available. This would also allow us to conduct simulations and “what-if” type
scenarios on the knowledge graph, possibly being able to show more microscopic
trends or campaigns as well as categorize the events into different aspects of
the society such as political, economical and military-operations.

To summarize, we have proposed a novel framework for structuring records on
cyber attacks and demonstrated the capabilities of the resulting knowledge
graph in terms of communicating events and constructing measures for risk. We
believe that the methods and results of this study can help cyber analysts to
perform their investigations more efficiently in the future as the amount of
new information is increasing faster than the number of experts in the field.

## References

  * [1] Sean Barnum.  Standardizing cyber threat intelligence information with the structured threat information expression (stix).  Mitre Corporation, 11:1–22, 2012.
  * [2] Zareen Syed, Ankur Padia, Tim Finin, Lisa Mathews, and Anupam Joshi.  Uco: A unified cybersecurity ontology.  UMBC Student Collection, 2016.
  * [3] Michael Iannacone, Shawn Bohn, Grant Nakamura, John Gerth, Kelly Huffer, Robert Bridges, Erik Ferragut, and John Goodall.  Developing an ontology for cyber security knowledge graphs.  In Proceedings of the 10th Annual Cyber and Information Security Research Conference, pages 1–4, 2015.
  * [4] Fabian Böhm, Florian Menges, and Günther Pernul.  Graph-based visual analytics for cyber threat intelligence.  Cybersecurity, 1(1):1–19, 2018.
  * [5] Arnav Joshi, Ravendar Lal, Tim Finin, and Anupam Joshi.  Extracting cybersecurity related linked data from text.  In 2013 IEEE Seventh International Conference on Semantic Computing, pages 252–259. IEEE, 2013.
  * [6] Kun Li, Huachun Zhou, Zhe Tu, and Bohao Feng.  Cskb: A cyber security knowledge base based on knowledge graph.  In International Conference on Security and Privacy in Digital Economy, pages 100–113. Springer, 2020.
  * [7] Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives.  Dbpedia: A nucleus for a web of open data.  In Proceedings of the 6th International The Semantic Web and 2nd Asian Conference on Asian Semantic Web Conference, ISWC’07/ASWC’07, page 722–735, Berlin, Heidelberg, 2007. Springer-Verlag.
  * [8] Yucong Duan, Lixu Shao, Gongzhu Hu, Zhangbing Zhou, Quan Zou, and Zhaoxin Lin.  Specifying architecture of knowledge graph with data graph, information graph, knowledge graph and wisdom graph.  In 2017 IEEE 15th International Conference on Software Engineering Research, Management and Applications (SERA), pages 327–332. IEEE, 2017.
  * [9] Jenny Rose Finkel, Trond Grenager, and Christopher D Manning.  Incorporating non-local information into information extraction systems by gibbs sampling.  In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 363–370, 2005.
  * [10] Ying Shen, Joël Colloc, Armelle Jacquet-Andrieu, Ziyi Guo, and Yong Liu.  Constructing ontology-based cancer treatment decision support system with case-based reasoning.  In International Conference on Smart Computing and Communication, pages 278–288. Springer, 2017.
  * [11] Maya Rotmensch, Yoni Halpern, Abdulhakim Tlimat, Steven Horng, and David Sontag.  Learning a health knowledge graph from electronic medical records.  Scientific reports, 7(1):1–11, 2017.
  * [12] Sören Auer, Viktor Kovtun, Manuel Prinz, Anna Kasprzik, Markus Stocker, and Maria Esther Vidal.  Towards a knowledge graph for science.  In Proceedings of the 8th International Conference on Web Intelligence, Mining and Semantics, pages 1–6, 2018.
  * [13] Tiberiu Marian Georgescu and Ion Smeureanu.  Using ontologies in cybersecurity field.  Informatica Economica, 21(3), 2017.
  * [14] Vasileios Mavroeidis and Siri Bromander.  Cyber threat intelligence model: An evaluation of taxonomies, sharing standards, and ontologies within cyber threat intelligence.  In 2017 European Intelligence and Security Informatics Conference (EISIC), pages 91–98. IEEE, 2017.
  * [15] Nidhi Rastogi, Sharmishtha Dutta, Mohammed J Zaki, Alex Gittens, and Charu Aggarwal.  Malont: An ontology for malware threat intelligence.  In International Workshop on Deployable Machine Learning for Security Defense, pages 28–44. Springer, 2020.
  * [16] Jana Komárková, Martin Husák, Martin Laštovička, and Daniel Tovarňák.  Crusoe: Data model for cyber situational awareness.  In Proceedings of the 13th International Conference on Availability, Reliability and Security, pages 1–10, 2018.
  * [17] William Heinbockel, Steven Noel, and James Curbo.  Mission dependency modeling for cyber situational awareness.  In NATO IST-148 Symposium on Cyber Defence Situation Awareness, pages 1–14, 2016.
  * [18] Steven Noel, Eric Harley, Kam Him Tam, Michael Limiero, and Matthew Share.  Cygraph: graph-based analytics and visualization for cybersecurity.  In Handbook of Statistics, volume 35, pages 117–167. Elsevier, 2016\.
  * [19] Matthias Schäfer, Markus Fuchs, Martin Strohmeier, Markus Engel, Marc Liechti, and Vincent Lenders.  Blackwidow: Monitoring the dark web for cyber security information.  In 2019 11th International Conference on Cyber Conflict (CyCon), volume 900, pages 1–21. IEEE, 2019.
  * [20] Nazgol Tavabi, Palash Goyal, Mohammed Almukaynizi, Paulo Shakarian, and Kristina Lerman.  Darkembed: Exploit prediction with neural language models.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
  * [21] Sudip Mittal, Prajit Kumar Das, Varish Mulwad, Anupam Joshi, and Tim Finin.  Cybertwitter: Using twitter to generate alerts for cybersecurity threats and vulnerabilities.  In 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 860–867. IEEE, 2016.
  * [22] Sudip Mittal, Anupam Joshi, and Tim Finin.  Cyber-all-intel: An ai for security related threat intelligence.  arXiv preprint arXiv:1905.02895, 2019.
  * [23] Lorenzo Neil, Sudip Mittal, and Anupam Joshi.  Mining threat intelligence about open-source projects and libraries from code repository issues and bug reports.  In 2018 IEEE International Conference on Intelligence and Security Informatics (ISI), pages 7–12. IEEE, 2018.
  * [24] Yan Jia, Yulu Qi, Huaijun Shang, Rong Jiang, and Aiping Li.  A practical approach to constructing a knowledge graph for cybersecurity.  Engineering, 4(1):53–60, 2018.
  * [25] Mayank Kejriwal and Pedro Szekely.  Information extraction in illicit web domains.  In Proceedings of the 26th international conference on world wide web, pages 997–1006, 2017.
  * [26] Ruoqi Li, Wenbin Dai, Sheng He, Xiaosheng Chen, and Genke Yang.  A knowledge graph framework for software-defined industrial cyber-physical systems.  In IECON 2019-45th Annual Conference of the IEEE Industrial Electronics Society, volume 1, pages 2877–2882. IEEE, 2019.
  * [27] Dave Shackleford.  Who’s using cyberthreat intelligence and how?  SANS Institute. Retrieved January, 24:2018, 2015.
  * [28] Joachim Daiber, Max Jakob, Chris Hokamp, and Pablo N. Mendes.  Improving efficiency and accuracy in multilingual entity extraction.  In Proceedings of the 9th International Conference on Semantic Systems (I-Semantics), 2013.
  * [29] Matthew Honnibal, Ines Montani, Sofie Van Landeghem, and Adriane Boyd.  spaCy: Industrial-strength Natural Language Processing in Python, 2020\.
  * [30] Aric Hagberg, Pieter Swart, and Daniel S Chult.  Exploring network structure, dynamics, and function using networkx.  Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
  * [31] Paolo Passeri.  Hackmageddon.  https://www.hackmageddon.com/, 2021.  Accessed: 14.08.2021.
  * [32] Michael Stewart, Majigsuren Enkhsaikhan, and Wei Liu.  Icdm 2019 knowledge graph contest: Team uwa.  In 2019 IEEE International Conference on Data Mining (ICDM), pages 1546–1551, 2019.
  * [33] Shaun D’Souza.  Parser extraction of triples in unstructured text.  arXiv preprint arXiv:1811.05768, 2018.
  * [34] Oren Etzioni, Anthony Fader, Janara Christensen, Stephen Soderland, and Mausam Mausam.  Open information extraction: The second generation.  In IJCAI, volume 11, pages 3–10, 2011.
  * [35] Marti A Hearst.  Automatic acquisition of hyponyms from large text corpora.  In Coling 1992 volume 2: The 15th international conference on computational linguistics, 1992.
  * [36] Thomas Wolf.  State-of-the-art neural coreference resolution for chatbots.  http://medium.com/huggingface/state-of-the-art-neural-coreference-resolution-for-chatbots-3302365dcf30, July 07 2017.  Accessed: 07.07.2021.

## Author Contributions

TT and KB constructed the strategic ontology and the knowledge graph model. KB
constructed the NLP method for extracting the SVO-triples from the textual
data. TT collected and constructed the knowledge graph and the related risk
measures and created the figures for the manuscript. TT and KB wrote the
manuscript with the support and feedback of KK, ML, PJ and AC.

## Acknowledgments

TT, KB, ML and KK acknowledge research project funding from Cyberwatch
Finland. TT acknowledges funding from the Vilho, Yrjö and Kalle Väisälä
Foundation of the Finnish Academy of Science and Letters.


[affiliation=1]TomokiKoriyama

# VAE-based Phoneme Alignment Using Gradient Annealing and
SSL Acoustic Features

###### Abstract

This paper presents an accurate phoneme alignment model that aims for speech
analysis and video content creation. We propose a variational autoencoder
(VAE)-based alignment model in which a probable path is searched using encoded
acoustic and linguistic embeddings in an unsupervised manner. Our proposed
model is based on one TTS alignment (OTA) and extended to obtain phoneme
boundaries. Specifically, we incorporate a VAE architecture to maintain
consistency between the embedding and input, apply gradient annealing to avoid
local optimum during training, and introduce a self-supervised learning
(SSL)-based acoustic-feature input and state-level linguistic unit to utilize
rich and detailed information. Experimental results show that the proposed
model generated phoneme boundaries closer to annotated ones compared with the
conventional OTA model, the CTC-based segmentation model, and the widely-used
tool MFA.

###### keywords:

phoneme alignment, annealing, self-supervised learning, forward-sum algorithm,
variational autoencoder

##  1 Introduction

Alignment in speech processing refers to the task of determining the times at
which phonemes, characters, or words are uttered, based on a pair of a speech
waveform and a phoneme or character sequence. Accurate alignment can be used
to analyze phonetic and prosodic features of speech in detail, as well as to
create video content such as subtitles, lip-sync, and speech editing.
Furthermore, the alignment between the speech signal and the phoneme or text
is crucial for modeling speech recognition and synthesis, because these tasks
involve sequence-to-sequence transformations with different lengths.

The most well-known conventional method of phoneme alignment is the use of the
Gaussian mixture model (GMM)-based hidden Markov model (HMMs) [1], which is
also used the recent tool, Montreal Forced Aligner (MFA) [2]. To overcome the
model expressiveness of GMM, many neural network (NN)-based methods have been
proposed [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], from the perspective of
automatic speech recognition (ASR) and text-to-speech (TTS). CTC segmentation
[3] utilizes an ASR network trained with connectionist temporal classification
(CTC) loss that includes a blank character. Since CTC segmentation only
requires ASR models, it is easy to adapt various languages as WhisperX does
[4]. However, the blank symbol conceals the beginning and end of each
character, resulting in inaccurate boundary prediction. Another approach uses
supervised training to predict the boundaries of phonemes [5]. The issue with
using a supervised method is that it is applicable to various languages or
speaking styles because phoneme boundary annotation for training is very
limited.

TTS research also developed alignment model to capture the relationship
between text and waveform. Famous frameworks use a forward-sum algorithm [12,
11] or its Viterbi search variant, known as monotonic alignment search (MAS)
[13], which searchs for a monotonic path with dynamic programming. For
example, Glow-TTS [13] and VITS [14] perform MAS using acoustic embeddings
extracted by normalizing flow architecture, while RAD-TTS [12] and one tts
alignment (OTA) [11] utilize forward-sum loss with NN-based linguistic and
acoustic encoders. The use of forward-sum loss enables simultaneous training
of alignment and TTS. However, the phoneme boundaries obtained from alignment
modules are not always accurate, even though the synthetic speech is natural
sounding due to the high expressiveness of NN models. Moreover, the accuracy
of alignment has not been precisely evaluated in the previous studies [14,
11].

In this study, we explore phoneme alignment that can predict accurate
boundaries in an unsupervised manner. Specifically, we propose a novel
alignment model by extending the alignment module of OTA [11]. We incorporate
the variational autoencoder (VAE) [15] architecture to retain time-dependent
acoustic and linguistic information of encoders. We also introduce acoustic
features obtained from self-supervised learning (SSL) models [16, 17] to
utilize rich acoustic information, similar to recent alignment studies [4, 8].
Furthermore, we investigate the use of gradient annealing to avoid local
optima during the path search, inspired by the gradient-based GMM training
technique [18].

Experimental evaluations are conducted using a corpus that include manually-
annotated phoneme boundaries. We calculate the errors of boundaries predicted
by various modeling settings and demonstrate that the proposed method can
yield more accurate phoneme boundaries compared with the conventional methods.
Moreover, we perform an ablation study to examine the effectiveness of each
component of the proposed model. Some examples are available at
111https://github.com/hyama5/vae_align.

##  2 One TTS Alignment

A popular method for text or phoneme alignment involves searching for an
appropriate path between an acoustic embedding sequence
$(\mathbf{y}_{1},\dots,\mathbf{y}_{T})$ and a linguistic feature sequence
$(\mathbf{x}_{1},\dots,\mathbf{x}_{K})$. The parallel version of OTA [11],
which we refer to as OTA in this paper and is derived from RAD-TTS [12], uses
convolutional networks to obtain the embeddings and trains the network by
minimizing the following forward-sum loss function:

$\displaystyle L_{\mathrm{align}}=-\log\sum_{\mathbf{s}\in
S}\prod_{t=1}^{T}b(t,s_{t}).$ (1)

Here, $\mathbf{s}=(s_{1},\dots,s_{T})~{}(s_{t}\in\\{1,\dots,K\\})$ is the
state sequence and $S$ is a set of monotonic left-to-right no-skip paths. The
function $b(t,s_{t})>0$ represents the likelihood that the acoustic feature at
time $t$ has the $s_{t}$-th linguistic feature, which is defined by the
product of a matching function $f(\mathbf{y}_{t},\mathbf{x}_{k})$ and a
position prior $p_{\mathrm{pos}}(t,k;\omega)$ as follows:

$\displaystyle
b(t,k)=f(\mathbf{y}_{t},\mathbf{x}_{k})p_{\mathrm{pos}}(t,k;\omega).$ (2)

The matching function $f(\cdot)$ is a softmax function with the logits of
negative squared distance given by

$\displaystyle f(\mathbf{y}_{t},\mathbf{x}_{k})$
$\displaystyle=\frac{\exp(-\lVert\mathbf{y}_{t}-\mathbf{x}_{k}\rVert^{2})}{\sum_{i=1}^{K}\exp(-\lVert\mathbf{y}_{t}-\mathbf{x}_{i}\rVert^{2})}.$
(3)

The position prior $p_{\mathrm{pos}}(\cdot)$ is a bias function defined
independently from acoustic and linguistic features to represent the rough
diagonal tendency of paths. Specifically, the position prior is implemented
using a beta-binomial distribution
$p_{\mathrm{pos}}(t,k;\omega)=\mathrm{BetaBin}(k,\omega t,\omega(T-t+1))$.
Although a large value of $\omega$ helps fast convergence during training, it
can also impose a strong restriction because not all speech utterances have
diagonal paths.

The training of encoders and decoders is performed by gradient-based
optimization using the forward-sum loss $L_{\mathrm{align}}$. The gradient for
$\log b(\cdot)$ is given by

$\displaystyle\frac{\partial L_{\mathrm{align}}}{\partial\log
b(t,k)}=-\frac{\sum_{\mathbf{s}\in
S(t,k)}\prod_{\tau=1}^{T}b(\tau,s_{\tau})}{\sum_{\mathbf{s}\in
S}\prod_{\tau=1}^{T}b(\tau,s_{\tau})}\triangleq-\gamma(t,k)$ (4)

where $S(t,k)$ is the set of paths through state $k$ at time $t$. The term
$\gamma(t,k)$ represents the probability of passing through $(t,k)$, which is
known as state occupancy in the training of HMM. It is possible to compute the
$\gamma(t,k)$ using the dynamic programming of the forward-backward algorithm
in a similar manner to HMM. When predicting phoneme boundaries from the
trained model, we perform a Viterbi search, also known as monotonic align
search, to find the most likely path and identify the state for each time.

##  3 Proposed VAE-based Alignment

We propose a novel alignment model by extending OTA. The major modifications
from OTA include a VAE-based architecture, gradient annealing, SSL acoustic
features, and state-level linguistic units.

For accurate alignment, the acoustic embedding of the $t$-th frame should
retain the characteristics of the acoustic feature of the $t$-th frame, and
the same applies to linguistic embeddings. However, we have observed that when
we use the OTA model, the acoustic and linguistic embeddings do not always
maintain the original acoustic and linguistic information and often overfit
the alignment loss. To address this issue, we incorporate a VAE architecture
[15] as shown in Fig. 1. We expect that this architecture will preserve the
input acoustic and linguistic information in the embedding layers. The loss
function is defined by

$\displaystyle
L=L_{\mathrm{align}}+w_{\mathrm{aco}}L_{\mathrm{aco}}+w_{\mathrm{lng}}L_{\mathrm{lng}}$
(5)

where $w_{\mathrm{aco}}$ and $w_{\mathrm{lng}}$ are weights, and
$L_{\mathrm{aco}}$ and $L_{\mathrm{lng}}$ are VAE losses, respectively.

Moreover, gradient-based training often falls into a local optimum. That is,
the path becomes fixed in the early stages of training, making it difficult to
search for the probable path during training. This issue aises from the
gradient given in Eq. (4). If the likelihood $b(t,k)$ is very small, the
gradient becomes close to zero, and thus the parameters for the likelihood
$b(t,k)$ are slightly updated. This phenomenon is observed in similar models
such as HMM or GMM that have hidden states when we perform gradient-based
optimization [18]. Therefore, we propose annealing for the gradients in the
alignment, based on the annealing in GMM training [18]. Specifically, we
employ convolution with a Gaussian annealing filter $g(\cdot)$ given by

$\displaystyle\frac{\partial L_{\mathrm{align}}}{\partial\log b(t,k)}$
$\displaystyle\approx-\gamma^{\prime}(t,k)=-\gamma(t,k)*g(k)$ (6)
$\displaystyle g(k)$
$\displaystyle=\exp\left(-\frac{k^{2}}{2\sigma^{2}}\right)$ (7)

where $\sigma$ is the annealing coefficient, and $*$ denotes convolution. The
coefficient $\sigma$ is updated by multiplying a rate $r<1.0$ during training.
The annealed gradient approximates the original one in Eq. (4) when $\sigma$
becomes sufficiently small. This annealing shares the possibility with
adjacent states, which helps to avoid the local optimum problem.

The use of SSL models has had a significant impact on the field of speech
processing. For example in alignment, the CTC segmentation demo [19] and
WhisperX [4] utilize SSL models to perform alignment. We apply SSL features
extracted from a pretrained SSL model to the input of acoustic features. Since
SSL models are trained by predicting the masked frame-level components, the
SSL features can provide position-dependent rich information that is useful
for accurate alignment.

We also examine the alignment level of linguistic units. In OTA [11] and other
models [12, 14, 3], phonemes or characters are used as the unit of alignment.
This assumes that each phoneme or character has one stable feature in acoustic
embeddings. However, some phonemes change drastically within themselves. For
example, a plosive sound has two different segments: a silent part and a
bursting part, which is often referred to as subphone. Therefore, we extend
the linguistic unit to the multiple-state level by dividing the linguistic
input of one phoneme into multiple states per phoneme. This approach allows us
to capture the changes within the phonemes, similar to the GMM-HMM-based
methods.

Figure 1: Architecture of the proposed alignment model.

##  4 Experiments

###  4.1 Experimental conditions

####  4.1.1 Dataset

We used the Corpus of Spontaneous Japanese (CSJ) [20] for experimental
evaluations. The core data of CSJ, which includes detailed phoneme annotation,
was divided into training, development, and evaluation subsets based on the
ASR recipe of ESPnet [21]. The training, development, and evaluation subsets
comprised 24,863 utterances (188 talks, 1,580 k phonemes, 33.2 h), 900
utterances (8 talks, 56 k phonemes, 1.2 h), 896 utterances (8 talks, 62 k
phonemes, 1.3 h), respectively. We used 52 entities as a phoneme set and
regarded the annotated phoneme boundaries as the true ones for evaluation. It
should be noted that these annotated boundaries were not used during training.

####  4.1.2 Acoustic features

We used mel-frequency cepstral coefficient (MFCC) and melspectrogram (Melspec)
as conventional acoustic features. MFCC was a 39-dimensional feature
consisting of 13-dimensional coefficients and their $\Delta$ and $\Delta^{2}$
features. The dimension of melspectrogram was set to 80. The acoustic features
were extracted with a 10 ms frame-shift. For SSL features, we used four types
of SSL-based models trained with different objectives: HuBERT(en), HuBERT(ja),
X-LSR, and w2v2-ASR. HuBERT(en) was a HuBERT-base model [17] trained with
English Librispeech [22] database, whereas HuBERT(ja) was a HuBERT-base model
trained with the Japanese ReazonSpeech [23] database [24], which is the same
language as the target one. XLS-R was a wav2vec2.0 large model [25] trained
with multiple languages. The model w2v2-ASR was fine-tuned from XLS-R using
Japanese corpora. We also used Whisper encoder [26] (Whisper), which has
recently gained popularity as a base model for feature extraction. Since SSL
and Whisper features were defined with a 20 ms shift, we upsampled them to a
10 ms shift to compare with the conventional features.

####  4.1.3 Base model configurations

We define a base proposed model used for the following evaluations. The
encoders and decoders for acoustic and linguistic features were composed of
6-layer convolution networks, respectively. The kernel size of convolution
layers was 3 and 256 hidden channels were employed. The dimension of
embeddings for the matching function was 64. We adopted 3 states per phoneme
as the modeling level of linguistic units. The loss weights were set as
$(w_{\mathrm{aco}},w_{\mathrm{lng}})=(0.1,0.1)$. The coefficient of position
prior $\omega$ was set to 0.01. We set the initial annealing coefficient
$\sigma$ and update rate $r$ to 30.0 and 0.9, respectively, and update
$\sigma$ every 1000 training steps. The training was performed up to 90k
steps, and using Adam optimization [27] with a learning rate of $1.0\times
10^{-5}$. The minibatch size was 4.

We implemented the computation of dynamic programming for the forward-sum loss
using Triton [28] and other computations using PyTorch. Training time with one
NVIDIA A100 GPU took approximately 150 min.

####  4.1.4 Conventional methods

We used MFA, CTC segmentation, and OTA for comparison. The MFA was trained
using the same dataset as the other models utilizing the default configuration
of MFA. To create the CTC-segmentation model, we trained a phoneme recognition
model composed of a 6-layer Conformer [29] with CTC loss. As the input of the
model, we used the output of HuBERT(ja) L12. The configuration of the OTA
model was based on the original OTA paper [11]. Specifically, we used two and
one convolution layers for acoustic and linguistic encoders, respectively. The
acoustic features were melspectrogram, and the modeling level of linguistic
features was a phoneme. In this study, only alignment loss was used instead of
TTS loss for the OTA model. We used the same configurations as the proposed
base model for other experimental settings.

####  4.1.5 Evaluation metrics

We evaluated the performance of the alignment models by calculating the errors
between the predicted and annotated phoneme boundaries. There is no consensus
on the accuracy of phoneme boundaries, which depends on the granularity of
words and phonemes to be analyzed. Hence, we used the four evaluation metrics.
MAE and Median were the mean and median of absolute errors. MAE was more
sensitive to outliers than Median. The other metrics were tolerance error
rates defined as the ratio of errors whose absolute values exceeded a specific
threshold. We used 20 ms and 50 ms as the threshold. All values in the
evaluation, except for MFA, were the average of 5 trials with different random
seeds.

Table 1: Mean and median of boundary errors [ms] and tolerance error rates [%] on different acoustic features. Features | MAE | Median | 20 ms tol | 50 ms tol
---|---|---|---|---
MFCC | 15.29 | 10.24 | 21.0 | 3.57
Melspec | 15.46 | 10.59 | 21.8 | 3.20
HuBERT(en) L0 | 14.13 | 8.49 | 18.3 | 3.45
HuBERT(en) L4 | 13.33 | 8.67 | 18.0 | 2.45
HuBERT(en) L8 | 13.53 | 9.02 | 18.0 | 2.40
HuBERT(en) L12 | 13.53 | 9.03 | 18.4 | 2.40
HuBERT(ja) L0 | 12.91 | 8.25 | 16.1 | 2.59
HuBERT(ja) L4 | 13.40 | 8.69 | 17.8 | 2.56
HuBERT(ja) L8 | 14.05 | 10.46 | 19.8 | 2.13
HuBERT(ja) L12 | 13.40 | 9.33 | 17.7 | 2.21
XLS-R L0 | 13.66 | 8.50 | 17.4 | 3.16
XLS-R L8 | 13.68 | 8.50 | 17.4 | 3.16
XLS-R L16 | 13.66 | 8.50 | 17.3 | 3.17
XLS-R L24 | 13.79 | 8.92 | 17.9 | 2.75
w2v2-ASR L0 | 13.62 | 8.56 | 17.3 | 3.08
w2v2 ASR L8 | 14.46 | 9.93 | 21.0 | 2.83
w2v2-ASR L16 | 17.92 | 12.56 | 30.4 | 4.08
w2v2-ASR L24 | 17.33 | 12.05 | 28.6 | 4.58
Whisper | 22.89 | 19.54 | 48.6 | 4.93

###  4.2 Results on acoustic features

We first evaluated the effect of acoustic features on phoneme alignment. Table
1 shows the results for each feature. In the table, L0 to L24 represent the
layer indices of intermediate transformer layers. When we compare the
conventional features of MFCC and Melspec with HuBERT and XLS-R, HuBERT and
XLS-R features had smaller MAEs. Since the differences among HuBERT(en),
HuBERT(ja), and XLS-R were not significant, the dependency of language and SSL
modeling method may not be crucial. It is observed that w2v2-ASR had large
errors when we used layers L16 and L24. A possible reason is that the fine-
tuned model for ASR lost the position information, leading to worse alignment
accuracy. This is supported by the large errors of Whisper encoders trained
for speech recognition objectives. The following experiments were performed
using the best features, HuBERT(ja) L0.

Table 2: Mean and median of boundary errors [ms] and tolerance error rates [%] on different alignment methods. Method | MAE | Median | 20 ms tol | 50 ms tol
---|---|---|---|---
MFA | 16.46 | 10.45 | 23.1 | 4.31
CTC | 40.81 | 34.63 | 70.9 | 30.87
OTA | 23.10 | 14.55 | 36.1 | 7.28
Proposed | 12.91 | 8.25 | 16.1 | 2.59

###  4.3 Results on methods

We compared the proposed method with the conventional ones shown in Table 2.
We see that CTC segmentation had larger errors than the other methods. This
could be because the existence of blank symbols and the CTC loss did not
assure the accurate position information. Although we tried multiple types of
input features and encoder architectures, the same tendency was observed. We
also confirmed that the proposed method, an extension of OTA model, reduced
errors, indicating that the extension worked as expected. Although the GMM-
HMM-based MFA yielded small errors, the proposed method outperformed MFA.

Table 3: Mean and median of boundary errors [ms] and tolerance error rates [%] on ablation of model components. Method | MAE | Median | 20 ms tol | 50 ms tol
---|---|---|---|---
Proposed | 12.91 | 8.25 | 16.1 | 2.59
w/o VAE | 14.96 | 10.41 | 23.1 | 2.90
w/o annealing | 13.26 | 10.45 | 16.8 | 2.89
Phoneme-level | 16.09 | 10.29 | 22.9 | 4.22
w/o position prior | 12.96 | 8.24 | 16.1 | 2.61

###  4.4 Ablation study on proposed components

The proposed method extends OTA models by adding multiple features. Hence, we
performed an ablation study to evaluate the importance of each component.

  * •

W/o VAE only used $L_{\mathrm{align}}$ for training instead of $L$.

  * •

W/o annealing used the gradient of Eq. (4) directly for training.

  * •

Phoneme-level employed phonemes as the linguistic unit instead of three states
per phoneme.

  * •

W/o position prior did not use position prior of Eq. (2). This ablation was an
evaluation of the position prior used in the OTA model.

The results are shown in Table 3. It is seen that the proposed VAE, gradient
annealing, and state-level modeling were all important to reduce errors. The
position prior did not significantly affect the errors. We observed that while
the position prior was an important factor in convergence, since annealing was
also effective for convergence, the position prior was not always necessary.

Table 4: Mean and median of boundary errors [ms] and tolerance error rates [%] on ablation of encoders/decoders. Method | MAE | Median | 20 ms tol | 50 ms tol
---|---|---|---|---
Proposed base | 12.91 | 8.25 | 16.1 | 2.59
Conformer aco. enc. | 12.93 | 8.31 | 16.0 | 2.65
Conformer aco. dec. | 12.84 | 7.86 | 15.5 | 2.75
Conformer ling. enc. | 12.51 | 8.21 | 15.4 | 2.32
Conformer ling. dec. | 13.18 | 8.51 | 16.5 | 2.69
Flow aco. enc | 14.36 | 9.52 | 20.1 | 3.26

###  4.5 Ablation study on encoder and decoders

The encoders and decoders of base models were simply composed of 6 convolution
layers. However, we can consider using more complex and highly expressive
components. In this ablation study, we replaced the convolution layers of each
acoustic/linguistic encoder or decoder with a 6-layer Conformer block [29],
which included 4-head self-attention and depth-wise convolution modules.
Another ablation involved using normalizing flow for acoustic encoder instead
of VAE as in VITS [14]. We used an affine coupling layer in the same way as
VITS, and trained the model of 6 flow steps and a 1-layer convolution for each
flow step.

The results are shown in Table 4. It is seen that the use of Conformer for the
linguistic encoder reduced errors compared with the proposed base model. A
possible reason is that long-range linguistic contexts obtained by the
Conformer could effectively extract linguistic embeddings for alignment. The
errors using the flow-based acoustic encoder were larger than the proposed
base model. This could be because of the structural limitation that flows are
required to be invertible.

##  5 Conclusions

In this study, we proposed an unsupervised phoneme alignment model based on
the OTA model. Specifically, we incorporated a VAE architecture to maintain
consistency between inputs and embeddings, applied gradient annealing to avoid
local optima, and incorporated SSL acoustic feature input and state-level
linguistic unit to utilize rich and detailed information. In experimental
evaluations, we measured alignment accuracy using annotated phoneme boundaries
and demonstrated that the proposed method can generate more accurate alignment
than conventional methods, including GMM-HMM-based ones. In future work, we
should evaluate the effectiveness of the proposed model using multiple
languages including low-resource ones and diverse styles such as expressive
speech and singing voices. We will also investigate the effectiveness of the
accurate alignment for practical applications such as TTS and video content
creation.

## References

  * [1] L. Rabiner, M. Sambur, and C. Schmidt, ``Applications of a nonlinear smoothing algorithm to speech processing,'' _IEEE Trans. Acous., Speech Signal Process._ , vol. 23, no. 6, pp. 552–557, 1975.
  * [2] M. McAuliffe, M. Socolof, S. Mihuc, M. Wagner, and M. Sonderegger, ``Montreal forced aligner: Trainable text-speech alignment using kaldi.'' in _Proc. Interspeech_ , vol. 2017, 2017, pp. 498–502.
  * [3] L. Kürzinger, D. Winkelbauer, L. Li, T. Watzel, and G. Rigoll, ``CTC-segmentation of large corpora for german end-to-end speech recognition,'' in _Proc. SPECOM_. Springer, 2020, pp. 267–278.
  * [4] M. Bain, J. Huh, T. Han, and A. Zisserman, ``WhisperX: Time-accurate speech transcription of long-form audio,'' in _Proc. INTERSPEECH_ , 2023, pp. 4489–4493.
  * [5] J. Li, Y. Meng, Z. Wu, H. Meng, Q. Tian, Y. Wang, and Y. Wang, ``NeuFA: Neural network based end-to-end forced alignment with bidirectional attention mechanism,'' in _Proc. ICASSP_ , 2022, pp. 8007–8011.
  * [6] H. Chung, S.-H. Lee, and S.-W. Lee, ``Reinforce-Aligner: Reinforcement Alignment Search for Robust End-to-End Text-to-Speech,'' in _Proc. Interspeech_ , 2021, pp. 3635–3639.
  * [7] M. C. Kelley and B. V. Tucker, ``A Comparison of Input Types to a Deep Neural Network-based Forced Aligner,'' in _Proc. Interspeech_ , 2018, pp. 1205–1209.
  * [8] J. Zhu, C. Zhang, and D. Jurgens, ``Phone-to-audio alignment without text: A semi-supervised approach,'' in _Proc. ICASSP_ , 2022, pp. 8167–8171.
  * [9] T. Kouzelis, G. Paraskevopoulos, A. Katsamanis, and V. Katsouros, ``Weakly-supervised forced alignment of disfluent speech using phoneme-level modeling,'' in _Proc. INTERSPEECH_ , 2023, pp. 1563–1567.
  * [10] T. Raissi, W. Zhou, S. Berger, R. Schlüter, and H. Ney, ``HMM vs. CTC for automatic speech recognition: Comparison based on full-sum training from scratch,'' in _Proc. SLT_ , 2023, pp. 287–294.
  * [11] R. Badlani, A. Łańcucki, K. J. Shih, R. Valle, W. Ping, and B. Catanzaro, ``One TTS alignment to rule them all,'' in _Proc. ICASSP_ , 2022, pp. 6092–6096.
  * [12] K. J. Shih, R. Valle, R. Badlani, A. Lancucki, W. Ping, and B. Catanzaro, ``RAD-TTS: Parallel flow-based TTS with robust alignment learning and diverse synthesis,'' in _ICML Workshop on Invertible Neural Networks, Normalizing Flows, and Explicit Likelihood Models_ , 2021.
  * [13] J. Kim, S. Kim, J. Kong, and S. Yoon, ``Glow-TTS: A generative flow for text-to-speech via monotonic alignment search,'' in _Proc. NeurIPS_ , H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, Eds., vol. 33, 2020, pp. 8067–8077.
  * [14] J. Kim, J. Kong, and J. Son, ``Conditional variational autoencoder with adversarial learning for end-to-end text-to-speech,'' in _Proc. ICML_ , 2021, pp. 5530–5540.
  * [15] D. P. Kingma and M. Welling, ``Auto-encoding variational Bayes,'' in _Proc. ICLR_ , 2014.
  * [16] A. Baevski, Y. Zhou, A. Mohamed, and M. Auli, ``wav2vec 2.0: A framework for self-supervised learning of speech representations,'' _Proc. NeurIPS_ , vol. 33, pp. 12 449–12 460, 2020.
  * [17] W.-N. Hsu, B. Bolte, Y.-H. H. Tsai, K. Lakhotia, R. Salakhutdinov, and A. Mohamed, ``HuBERT: Self-supervised speech representation learning by masked prediction of hidden units,'' _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 29, pp. 3451–3460, 2021.
  * [18] A. Gepperth and B. Pfülb, ``Gradient-based training of Gaussian mixture models for high-dimensional streaming data,'' _Neural Processing Letters_ , vol. 53, no. 6, pp. 4331–4348, 2021.
  * [19] FORCED ALIGNMENT WITH WAV2VEC2
https://pytorch.org/audio/stable/tutorials/forced_alignment_tutorial.html.

  * [20] K. Maekawa, ``Corpus of Spontaneous Japanese: Its design and evaluation,'' in _ISCA & IEEE Workshop on Spontaneous Speech Processing and Recognition_, 2003.
  * [21] S. Watanabe, T. Hori, S. Karita, T. Hayashi, J. Nishitoba, Y. Unno, N. Enrique Yalta Soplin, J. Heymann, M. Wiesner, N. Chen _et al._ , ``ESPnet: End-to-end speech processing toolkit,'' in _Proc. Interspeech_ , 2018.
  * [22] V. Panayotov, G. Chen, D. Povey, and S. Khudanpur, ``Librispeech: an ASR corpus based on public domain audio books,'' in _Proc. ICASSP_ , 2015, pp. 5206–5210.
  * [23] ReazonSpeech
https://research.reazon.jp/projects/ReazonSpeech/.

  * [24] Rinna/japanese-hubert-base
https://huggingface.co/rinna/japanese-hubert-base.

  * [25] A. Babu, C. Wang, A. Tjandra, K. Lakhotia, Q. Xu, N. Goyal, K. Singh, P. von Platen, Y. Saraf, J. Pino _et al._ , ``XLS-R: Self-supervised cross-lingual speech representation learning at scale,'' _arXiv preprint arXiv:2111.09296_ , 2021.
  * [26] A. Radford, J. W. Kim, T. Xu, G. Brockman, C. McLeavey, and I. Sutskever, ``Robust speech recognition via large-scale weak supervision,'' in _Proc. ICML_ , 2023, pp. 28 492–28 518.
  * [27] D. P. Kingma and J. Ba, ``Adam: A method for stochastic optimization,'' in _Proc. ICLR_ , 2015.
  * [28] P. Tillet, H.-T. Kung, and D. Cox, ``Triton: an intermediate language and compiler for tiled neural network computations,'' in _Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages_ , 2019, pp. 10–19.
  * [29] A. Gulati, J. Qin, C.-C. Chiu, N. Parmar, Y. Zhang, J. Yu, W. Han, S. Wang, Z. Zhang, Y. Wu, and R. Pang, ``Conformer: Convolution-augmented transformer for speech recognition,'' in _Proc. Interspeech_ , 2020, pp. 5036–5040.