# Contextualized Word Vector-based Methods for Discovering Semantic
Differences with No Training nor Word Alignment

Ryo Nagata  Konan University  Hiroya Takamura  National Institute of Advanced
Industrial Science and Technology  Noki Otani  Tokyo University of Foreign
Studies  Yoshifumi Kawasaki  University of Tokyo

##  1 Introduction

In this paper, we show that norms of contextualized word vectors obtained from
a large language model are a good indicator for words exhibiting semantic
differences111Following the convention in the literature, we use the term
semantic difference rather abstractly to refer to differences in meaning and
usages. in two corpora. To be precise, we show that the more meanings a word
covers in a corpus, the shorter the norm of its mean word vector gets. Using
this property, we propose methods for detecting semantic differences with
their instances in context, which brings out various applications: e.g.,
second language acquisition research [19] (e.g., words and their meanings non-
native speakers do not use as native speakers), social linguistics [18] (e.g.,
revealing semantic differences of words between British and American English),
and historical linguistics [11] (e.g., discovering words that have acquired a
meaning).

The major approach to semantic difference detection, which is based on non-
contextualized word vectors such as Word2vec [20], has several limitations and
thus is not always applicable to any corpora as will be discussed in detail in
Sect. 5. Above all, many of non-contextualized word vector-based methods
require some sort of correspondence between two corpora for comparison (e.g.,
word alignment). The task is, however, to find words that do not correspond
well in terms of their meanings, and thus it is more natural not to assume any
correspondence in advance as [1] point out. For example, it is not
straightforward at all to align words between native and non-native English
corpora. Besides, most previous methods are computationally costly and are not
suitable for detecting semantic differences in all words in a corpus.

In contrast, the proposed methods do not require any correspondence between
corpora. Besides, they are efficient and effective. All they require are to
compute the mean of contextualized word vectors and its norm for each word
type. They do not require training nor have hyper-parameters to be searched
for unlike previous methods. Nevertheless, they are effective even for corpus
pairs whose sizes are skewed and for infrequent words. They are also capable
of pinpointing word instances that have a meaning missing in one of the two
corpora for comparison. For instance, in Sect. 3, they reveal that the word
near is one of the most typical words exhibiting a semantic difference between
the native and non-native sub-corpora (approximately 10,000 and 100,000 words,
respectively) of ICNALE [13] and that its most typical one out of the 11 near
occurrences in the native portion is “it has near impossible,” which is
interpreted as almost; this usage does not appear at all in the 267 instances
of near in its counterpart.

The contributions of this paper are three-fold as follows: (i) We show for the
first time that norms of the mean contextualized word vectors are good
indicator for semantic differences; (ii) We give mathematical background to
our rather intuitive methods; (iii) We actually reveal words that have
semantic differences with their instances in native/non-native English and
also 1800s/2000s English.

##  2 Methods

We describe two methods, one for detecting words that have semantic
differences in two corpora and one for extracting their typical instances. So
far, we have often used the term word abstractly to mean both word type and
word token. Hereafter, for better understanding, we will distinguish between
the two; we will use the term word type to refer to word types and the term
word instance to a word token in context, which we assume is a whole sentence.

###  2.1 Detecting Semantic Differences

To begin with, let us first note that the similarity between two words (tokens
or types) are conventionally measured by the cosine similarity between the two
word vectors (hereafter, for simplicity, word vectors will refer to
contextualized ones unless otherwise noted). This is equivalent to measuring
the word similarity based only on the directions of word vectors, or to
assuming that all word vectors are normalized so that their Euclidean norms
equal one. We follow this convention, hereafter.

Under this condition, any word vector appears on the unit hypersphere. As a
special case of this, when the dimension of word vectors is two, word vectors
appear on the unit circle as in the dashed arrows (vectors) in Fig. 1.

With this preparation, we now examine the norm of the mean word vector for
various cases. An extreme case would be that a word type is always used in the
exact same context, and thus in the same meaning. Its word vectors appear on
the same point on the unit hypersphere as in Fig. 1 (a). Then, its mean vector
is always identical to the original word vectors, and thus its norm is also
always one; recall all word vectors are normalized so that their norms equal
one. The other extreme case would be that a word type is used in completely
opposite meanings with the same frequency, which are represented by two
opposite vectors as in Fig. 1 (b). In this case, its mean vector becomes the
zero-vector with the zero norm. Other cases in between would give a norm
between zero and one. For instance, two orthogonal vectors result in the mean
word vector whose norm is $\frac{\sqrt{2}}{{2}}$ as in Fig. 1 (c)222Addition
of two orthogonal vectors produces a vector along the diagonal line with a
norm of $\sqrt{2}$, and thus the norm of the mean word vector is
$\frac{\sqrt{2}}{{2}}$..

Figure 1: Intuitive Illustration for Mean Norms.

The observations so far suggest that the wider meanings a word type cover in a
given corpus, the shorter the norm of their mean word vector gets. This
property of word vectors is the basis of the proposed methods.

To formalize the detection method, we will introduce the following symbols. We
will denote a word vector by $\bm{x}$. Recall once again that $\|\bm{x}\|=1$
for all $\bm{x}$. We will also denote the mean vector of $\bm{x}$ and its norm
by $\overline{\bm{x}}$ and $l$, respectively (i.e.,
$\overline{\bm{x}}\equiv\frac{1}{n}\sum_{i=1}^{n}\bm{x_{i}}$ where $n$ refers
to the number of word instances of that word type in a given corpus). We will
denote the two corpora for comparison by $S$ and $T$ (source and
target333Source and target corpora would, for example, be native and non-
native English corpora., respectively); for example, $l_{S}$ refers to the
norm of the mean word vector of a word type obtained from the source corpus.

With these notations, the straight forward implementation of the above idea
for measuring semantic differences would be taking the ratios $l_{T}/l_{S}$
for all word types appearing in two corpora; larger values of this indicate
larger semantic differences (wider and narrower meanings in the source and
target corpora, respectively).

In the proposed method, we use its extended version as our score function,
which we call coverage; we define coverage as

$c(S,T)=\frac{l_{T}(1-l_{S}^{2})}{l_{S}(1-l_{T}^{2})},$ (1)

for which reason we will shortly describe in Subsect. 2.3. For the time-being,
let us just notice that in the coverage, the norms $l_{T}$ and $l_{S}$ are
respectively weighted by $1-l_{S}^{2}$ and $1-l_{T}^{2}$, which are based on
its counterpart.

The procedure for detecting word types having semantic differences are as
follows:
Input: source and target corpora $S$, $T$
Output: a list of words sorted in order of coverage

  1. 1.

Vectorize all word instances in $S$ and $T$

  2. 2.

For each word type, compute its mean vectors $\overline{\bm{x}}_{S}$ and
$\overline{\bm{x}}_{T}$, and then its norms $l_{S}$ and $l_{T}$

  3. 3.

Sort the word types by coverage defined by Eq. (1) in descending order

  4. 4.

Output the sorted list

###  2.2 Extracting Typical Word Instances

We now turn our interest to extracting word instances having a meaning which
is not, or seldom if ever, used in the target corpus. For this, we once again
consider the illustrative unit circle shown in Fig. 2. Fig. 2 shows two mean
vectors of a word type obtained from the source and target corpora.
Intuitively, word instances (or their word vectors) we are looking for now are
those that are distant from the mean word vector for the target corpus (to
make sure that their meanings are not or seldom used in it) and also that are
near the mean word vector for the source corpus (to make sure that their
meanings are indeed used in it). The dashed arrow $\bm{x}_{S}$ shown in Fig. 2
would be an example of this.

Fortunately, a difference of the two mean word vectors (i.e.,
$\overline{\bm{x}}_{S}-\overline{\bm{x}}_{T}$) will facilitate satisfying the
conditions. Fig. 2 intuitively illustrates that the word vector $\bm{x}_{S}$
in the source corpus satisfies the two conditions. This corresponds to taking:

$\cos(\overline{\bm{x}}_{S}-\overline{\bm{x}}_{T},\bm{x})=\frac{(\overline{\bm{x}}_{s}-\overline{\bm{x}}_{T})^{\mathsf{T}}\bm{x}}{\|\overline{\bm{x}}_{S}-\overline{\bm{x}}_{T}\|\|\bm{x}\|}$
(2)

Noting $\|\bm{x}\|=1$ and that
$\|\overline{\bm{x}}_{S}-\overline{\bm{x}}_{T}\|$ is constant444Note that we
are searching for $\bm{x}$ that gives a large value of Eq.( 2). with respect
to $\bm{x}$, Eq. (2) reduces to
$(\overline{\bm{x}}_{s}-\overline{\bm{x}}_{t})^{\mathsf{T}}\bm{x}$. As in
Subsect. 2.1, we will adjust this cosine-based function by $1-l_{S}^{2}$ and
$1-l_{T}^{2}$ to define another score function called representativeness as

$r(\bm{x},S,T)=(\frac{1}{1-l_{S}^{2}}\overline{\bm{x}}_{S}-\frac{1}{l-l_{T}^{2}}\overline{\bm{x}}_{T})^{\mathsf{T}}\bm{x},$
(3)

to which we will give a mathematical background presently in Subsect. 2.3.

Figure 2: Illustration for Difference of Mean Vectors.

The procedure for extracting word instances having a meaning which is not, or
seldom used in the target corpus is as follows:
Input: source and target corpora $S$, $T$; a target word type $w$
Output: a list of word instances in $S$ sorted in order of representativeness

  1. 1.

For $w$, compute the difference mean word vector
($\overline{\bm{x}}_{S}-\overline{\bm{x}}_{T}$)

  2. 2.

For each word instance of $w$ in $T$, compute representativeness defined by
Eq.( 3)

  3. 3.

Sort the word instances by representativeness in descending order

  4. 4.

Output the sorted list

The list obtained by swapping $S$ and $T$ is also helpful to investigate where
the meaning difference comes from.

###  2.3 Mathematical background

We now give a mathematical background to the proposed methods. Specifically,
we show that the two score functions assume the von Mises-Fisher distribution
behind word vectors (see the study [4] for the detail of the distribution).

The von Mises-Fisher distribution is a probability density function for the
random $d$-dimensional unit vector $\mathbf{x}$. It is defined as

$f(\mathbf{x};{\bm{\mu}},\kappa)=z_{\kappa}\exp\left({\kappa{\bm{\mu}}^{\mathsf{T}}\mathbf{x}}\right).$
(4)

The parameters $\bm{\mu}$ ($\|\bm{\mu}\|=1$) and $\kappa$ ($\kappa\geq 0$) are
respectively the mean direction and concentration parameter. The constant
$z_{\kappa}$ is the normalization constant depending on $\kappa$. It can be
regarded as akin to the isotropic Gaussian distribution of the hypersphere. It
is commonly used to process directional data as in the present paper.

In our case, the unit vector $\mathbf{x}$ of the von Mises-Fisher distribution
is the word vector $\bm{x}$. It follows that the word vector $\bm{x}$
distributes isotropically around the mean direction $\bm{{\mu}}$ with the
concentration $\kappa$. Then, $\kappa$ is interpreted as the concentration of
word meanings of the corresponding word types. In turn, the ratio
$\kappa_{T}/\kappa_{S}$ measures the coverage of the meanings of that word
type in the target corpus compared to those in the source corpus.

To examine the ratio $\kappa_{T}/\kappa_{S}$, one needs to estimate $\kappa$.
[4] show a simple approximate solution of its maximum likelihood estimate is:

$\kappa\approx\frac{l(d-l^{2})}{1-l^{2}},$ (5)

where $l$ is the norm of the mean vector as defined in Subsect. 2.1 while $d$
denotes the dimension of the unit vector $\mathbf{x}$. Then the ratio is
approximated to

$\frac{\kappa_{T}}{\kappa_{S}}\approx\frac{\frac{l_{T}(d-l_{T}^{2})}{1-l_{T}^{2}}}{\frac{l_{S}(d-l_{S}^{2})}{1-l_{S}^{2}}}$
(6)

Using555For example, $d=1024$ when ’bert-large-uncased’ is used as a
vectorizer while $l\in[0,1]$. $d\gg l$, it is further approximated to

$\frac{\kappa_{T}}{\kappa_{S}}\approx\frac{l_{T}(1-l_{S}^{2})}{l_{S}(1-l_{T}^{2})},$
(7)

which is identical to our score function coverage.

For the representativeness defined by Eq. (3), we can show that it is
equivalent to examining the log likelihood ratio of the probability density
function, which compares how probable the given $\bm{x}$ is in the two
corpora. It is given by

$\displaystyle\mathrm{LLR}$ $\displaystyle=$
$\displaystyle\log\frac{z_{\kappa_{S}}\exp\left({\kappa_{S}{\bm{\mu}_{S}}^{\mathsf{T}}\bm{x}}\right)}{z_{\kappa_{T}}\exp\left({\kappa_{T}{\bm{\mu}_{T}}^{\mathsf{T}}\bm{x}}\right)}$
(8) $\displaystyle=$
$\displaystyle\log\frac{z_{\kappa_{T}}}{z_{\kappa_{S}}}+(\kappa_{T}{\bm{\mu}_{T}}-\kappa_{S}{\bm{\mu}_{T}})^{\mathsf{T}}\bm{x}.$

The maximum likelihood estimate of $\bm{\mu}$ is given by
$\bm{\mu}=\frac{\overline{\bm{x}}}{l}$ [4]. Here, note that the second term in
the second line only matters with respect to $\bm{x}$. Then, putting this and
Eq. (5) into the second term results in

$(\frac{d-l_{S}^{2}}{1-l_{S}^{2}}{\overline{\bm{x}}_{S}}-\frac{d-l_{T}^{2}}{1-l_{T}^{2}}{\overline{\bm{x}}_{T}})^{\mathsf{T}}\bm{x}$
(9)

The approximations $d-l_{T}^{2}\approx d-l_{S}^{2}$ for $d\gg l_{T}^{2}$ and
$d\gg l_{S}^{2}$ give the score function representativeness. Note the coarse
approximation $\kappa\approx l$ would give the naive score functions
originally introduced in Subsect. 2.1 and 2.2.

##  3 Evaluation

###  3.1 Data and Conditions

In this section, we detect word types having semantic differences and extract
their word instances using the proposed methods to evaluate their
effectiveness. Specifically, we compare the following two corpus pairs: native
and non-native speaker English; 1800s and 2000s English. We use ICNALE [13]
and the cleaned version [3] of COHA [5] for the former and latter,
respectively. Table 1 shows their sizes.

Corpus | # tokens
---|---
ICNALE Native | 97,899
ICNALE Non-native | 986,764
COHA 1800s | 111,048,657
COHA 2000s | 68,678,659
Table 1: Sizes of Corpora for Evaluation.

ICNALE consists of essays written by native and non-native speakers of
English. As a non-native sub-corpus, we use the essays labelled as either
China, Indonesia, Japan, Korea, Taiwan, and Thailand. The essay topics are
written on either (a) It is important for college students to have a part-time
job. or (b) Smoking should be completely banned at all the restaurants in the
country. This means that the essay topics are common to the native and non-
native sub-corpora while their sizes are considerably different as shown in
Table 1.

COHA provides texts published in between 1820s and 2010s. Accordingly, we use
the texts in the corresponding periods. In COHA, 5% of ten consecutive tokens
every 200 are replaced by ‘@’ due to copy right regulations. We exclude
sentences containing this special token from our analysis. They also contain a
wide variety of fixed labels such as citation information as in Produced from
page scans provided by Internet archive. These inevitably make the norm of the
mean word vector longer for the words in them. Also, they can be noise in that
words would not appear in the corpora (e.g., Internet in 1800s). Similarly,
proper names often collocate with fixed contexts such as movie scripts (e.g.,
John: Yes, it is.). We exclude these noisy word types and proper nouns from
the sorted list of word types666We manually exclude such words by consulting
their typical word instances from the lists shown in Table 3 in the following
section..

The other conditions in this evaluation are as follows. In all corpora, we
only target tokens whose occurrences are more than ten. We use ‘bert-large-
uncased’ [6] in the Hugging Face implementation. We only target tokens that
are not split into multiple sub-words and that consist only of alphabetic
letters.

###  3.2 Comparison between Native and Non-Native English Corpora

Table 2 shows the 12 most semantically different word types with their typical
word instances where the source and target are the native and non-native sub-
corpora in ICNALE. Note that “$S$:” and “$T$:” in the typical word instance
column denote that the corresponding word instances are extracted from the
source and target corpora, respectively.

Table 2 reveals the following three major reasons why the word types have
wider meanings in the native sub-corpus: influence from essay prompt,
idiomatic phrases, and differences in construction and part-of-speech (POS).
We describe their details in this order below.

$\log c(S,T)$ | Word type | $f_{S}$ | $f_{T}$ | Typical word instance
---|---|---|---|---
0.61 | completely | 48 | 1662 |  $T$: ESSAY PROMPT
0.54 | near | 11 | 267 |  $S$: $\cdots$ it has become near impossible to $\cdots$
0.50 | country | 48 | 1707 |  $T$: ESSAY PROMPT
0.46 | concerned | 11 | 113 |  $T$: $\cdots$ as far as I’m concerned $\cdots$
0.45 | third | 11 | 348 |  $T$: Third, $\cdots$
0.39 | period | 13 | 115 |  $S$: Period!
0.37 | first | 87 | 1512 |  $T$: First, $\cdots$
0.36 | place | 67 | 1764 |  $S$: $\cdots$ fall into place $\cdots$ / $\cdots$ bans that they have in place $\cdots$
0.38 | course | 46 | 489 |  $T$: Of course $\cdots$
0.36 | taking | 34 | 461 |  $S$: $\cdots$ taking a part time job is $\cdots$
0.34 | hold | 16 | 111 |  $S$ $\cdots$ hold down a job $\cdots$
0.35 | knowledge | 16 | 574 |  $S$: $\cdots$ knowledge that smoking and passive smoking kill people $\cdots$
Table 2: Semantic Differences Found in Native ($S$ource) and Non-native
($T$arget) Sub-corpora in ICNALE.

Influence from essay prompt: Simply, many of the non-native speakers use one
of the essay prompts Smoking should be completely banned at all the
restaurants in the country. as it is. To be precise, the entire phrase appears
39 times and only once in the non-native and native sub-corpora, respectively.
This naturally makes the contexts of completely and country rather fixed in
the non-native sub-corpus, resulting in their long norms of their mean word
vectors.

Idiomatic phrases: More interestingly, Table 2 reveals word types used in an
idiomatic phrase or a phrasal verb that seldom appear in the non-native sub-
corpus, including fall into place, in place (as in effective), and hold down a
job (as in manage to keep the job). In the non-native sub-corpus, the writers
often use place to refer to physical locations while the native speakers also
use it metaphorically including the idiomatic phrases. For hold, it appears
more than 100 times in the non-native sub-corpus, but none collocates with
down, directly suggesting that most non-native speakers do not use or know the
phrasal verb that native speakers use (four out of the 16 instances of hold
appear in the phrasal verb). Instead, they often use it as a transitive verb
as in hold a job, which also frequently appear in the native sub-corpus.

Idiomatic phrases play the opposite role, too. Specifically, the non-native
speakers repeatedly concerned and course in the idiomatic phrases as shown in
Table 2. Surprisingly, they use the idiom of course 87% of the time while the
native speakers often use course to mean a set of classes, which decreases the
relative frequency of the idiomatic phrase (63%). Although strictly, they are
not idiomatic phrases, the non-native speakers first and third in a fixed
phrase. Surprisingly again, for instance, the first 886 word instances of
first (sorted by $c(S,T)$) are actually First, $\cdots$. It should be
emphasized that the nationalities of the non-native speakers range over six
countries and nevertheless, fixed expressions like these are common to them.
This is beyond the scope of this paper, but it would be interesting to reveal
the reasons behind.

Differences in construction and POS: These are represented by near and
knowledge. The former only appears 11 times in the native sub-corpus and one
of them is used to mean nearly or almost as in the typical word instance in
Table 2. Manual investigation reveals that this usage does not appear at all
in the non-native portion. This is an example of the robustness for low
frequency instances. Namely, the proposed methods can detect semantic
differences found in low frequency instances. This is true for the other
example knowledge, which appears only 16 times in the native sub-corpus. Out
of the 16, according to $c(S,T)$, the top two typical word instance of this is
the one used in an appositive construction as shown in Table 2. This usage is
seldom used in the non-native sub-corpus; as far as we checked manually, only
two were the case out of the 574 instances777We first searched the non-native
sub-corpus for the pattern knowledge that, obtaining 25 instances. We then
looked into them, finding that 22 cases were used in a relative clause and 1
in an erroneous construction.. This agrees with the general knowledge that
appositive constructions are difficult for learners of English.

###  3.3 Comparison between 1800s and 2000s English Corpora

Table 3 shows the list of word types having semantic differences, which
follows the same format as Fig. 2. The first and second halves of Table 3 show
those having wider meanings in the 1800s (source) than in the 2000s (target)
corpus and the opposite, respectively.

$S$(ource): 2000s English, $T$(arget): 1800s English
---
$\log c(S,T)$ | Word type | $f_{S}$ | $f_{T}$ | Typical instance
1.19 | whore | 57 | 483 |  $T$: $\cdots$ military lofts, whore the birds are trained , $\cdots$
1.06 | rebounds | 18 | 342 |  $S$: 11.8 rebounds / $T$: his heart rebounds.
1.01 | teen | 44 | 849 |  $T$: $\cdots$ is fif // teen hundred dollars $\cdots$
0.96 | hitter | 40 | 303 |  $S$: a switch hitter / $T$: $\cdots$ with hitter feelings$\cdots$
0.92 | recession | 32 | 539 |  $T$: direct approach or recession
0.90 | pregnant | 343 | 2290 |  $T$: $\cdots$ in pregnant illustrations of this great truth $\cdots$
0.88 | tuna | 13 | 464 |  $T$: $\cdots$ in which we tuna ourselves with the peoples $\cdots$
0.86 | coma | 30 | 345 |  $T$: $\cdots$ must have coma from god . $\cdots$
0.85 | quantum | 43 | 901 |  $T$: $\cdots$ the usual quantum of abuse $\cdots$
0.84 | diner | 14 | 635 |  $T$: $\cdots$ diner a dix / if diner was an apple $\cdots$
$S$(ource): 1800s, $T$(arget): 2000s
0.93 | systemic | 210 | 24 |  $T$: systemic inflammatory responses
0.91 | dynamo | 77 | 39 |  $S$: a dynamo of 5000 horse power / $T$: She was a dynamo.
0.83 | conversions | 36 | 90 |  $\cdots$ $\cdots$
0.83 | trigger | 1222 | 337 |  $T$: to trigger the immune system.
0.81 | strikers | 17 | 205 |  $T$: Strikers on three.
0.78 | grille | 100 | 11 |  $S$: the big rusty grille / $T$: bar and grille
0.76 | rotating | 333 | 29 |  $S$: the rotating motion / $T$: $\cdots$ rotating the pelvis $\cdots$
0.73 | champs | 82 | 60 |  $S$: Champs Elysees / $T$: national champs
0.73 | spectrum | 618 | 272 |  $S$: the light of the spectrum / $T$: a broad spectrum of items
0.72 | norm | 446 | 15 |  $S$: the only norm of law / $T$: income above the norm
Table 3: Word Types Having Semantic Differences in 1800s and 2000s English in
COHA.

The word types are classified into the following three categories:
transcription errors, differences in POS, and potential semantic shift. As
before, We describe their details in this order below.

Transcription errors: They are flagged as a semantic difference because they
are seemingly incorrectly transcribed, mostly in the 1800s corpus as in the
typical word instance of whore, which should be where; other examples include
teen (incorrectly split as in fif teen, coma for come, and tuna for tune?).
Transcription errors increase the variation in the contexts of a word type and
in turn shortens the norm of its mean word vector. It is crucial to remove
transcription errors to conduct accurate analyses. This is especially true for
historical corpora of which text is transcribed (semi)-automatically. The
evaluation results suggest that the proposed methods may be used to detect
transcription errors.

Differences in POS: trigger and rotating fall into this category. The former
is used often as a noun and a verb in the 1800s and 2000s corpora,
respectively while the latter as an adjective/present participle and a gerund
in the respective corpora.

Potential semantic shift: All other word types in Table 3 exhibit a semantic
difference. A typical example is rebounds. In the 1800s corpus, it refers to
something rebounding physically while in the 2000s corpus, it acquires a
meaning referring to an action in basketball. According to
Wikipedia888https://en.wikipedia.org/wiki/Basketball. Accessed on 5th, May,
2023., basketball was first played in 1891 and thus there had not been this
usage in middle 1800s or earlier. A similar case is systemic of which typical
word instance is systemic inflammatory responses. According to [2], the
disease called Systemic inflammatory response syndrome was first described by
Dr. William R. Nelson in 1983, which attests the acquisition of a new meaning
(or rather a new usage) in the 1900s.

It would be difficult to prove their semantic shifts from the available
information, but they are at least all interpretable. Examples include
pregnant (filled with meaning vs a woman having a baby), quantum (a unit vs
quantum in physics), and diner (metal bars vs an eating place), to name a few.

##  4 Discussion

The evaluation results in Sect. 3 show that the concentration parameter
$\kappa$, which is directly related to the norm of the mean word vector, is a
good indicator for semantic differences. The differences shown in Table 2 and
Table 3 are all interpretable and some of them are indeed of meaning; after
having seen few extracted typical word instances, we were able to tell, in
most cases, where the difference(s) in the word type in question came from.

Figure 3: Relationship between Number of Word Occurrences and Differences in
Two Consecutive Norms.

Here, it should be emphasized that semantic differences found in two corpora
do not necessarily mean that the writers do not know/cannot use the missing
meaning(s) (for non-native speakers) or that the word type has acquired/lost a
meaning. It would require further investigations to confirm the argument. The
proposed methods are rather suitable for obtaining new hypotheses about
semantic differences in words or for supporting a hypothesis one already has.

Another advantage of the proposed methods is that they are computationally
efficient. They require no training nor fine-tuning unlike the previous
approaches as will be discussed in Sect. 5. They solely rely on an off-the-
shelf language model (BERT in our case), which is a large advantage in terms
of implementation and development.

Correlated with this is that the proposed methods have almost no hyper-
parameters except for the threshold for word frequency (word instances whose
frequency is more than this threshold are the target of analysis).
Fortunately, norms of mean word vectors are stable with respect to word
frequency. To show this, we calculated norms of the mean word vector for each
occurrence of each word type and then differences between the two consecutive
values of the norms. Fig. 3 shows the results where the horizontal and
vertical axes denote the number of occurrences of word types and the norm
differences averaged over all word types. Fig. 3 shows that after around five
occurrences, the average norm difference becomes almost zero, meaning that the
norm of the mean vector is almost constant. Considering this, setting the
frequency threshold to ten just as in the evaluation in Sect. 3 is not a bad
choice. This stability of the norm enables the propose methods to discover
semantic differences in infrequent instances. It should be emphasized that
only one word instance would be enough to proof that a meaning exists in a
word type as in the near example in Table 2 (while the opposite does not
hold).

It should be also emphasized that its robustness for the low frequency problem
comes from the use of contextualized word vectors via a large language model.
Even if the source and target corpora are small, the obtained word vectors
should be statistically reliable considering the language model is trained on
a large corpus. In contrast, the previous methods based on non-contextualized
word vectors inevitably suffer from the low frequency problem because non-
contextualized word vectors are learned from the input corpora.

As having discussed, the proposed methods are simple and efficient, but at the
same time effective in discovering semantic differences found in words. All
these nice properties come from the assumption of the von Mises-Fisher
distribution behind word vectors. Although this assumption has its limitations
theoretically, it works well practically as we have seen in Sect. 3.

##  5 Related Work

Linguists (e.g., [8, 19]) often use frequency-based methods to discover
differences in words in two corpora. Because they only consider superficial
frequency counts, it requires more sophisticated methods to conduct deeper
analyses into semantic differences.

The use of non-contextualized word vectors is the major approach to semantic
difference detection. For diachronic analysis, [15] propose setting word
vectors obtained from the previous time to initial word vectors of the next.
For the same purpose, [17] and [11] propose methods for discovering semantic
differences by aligning words in two corpora. These alignment-based methods
make a strong assumption that words are linearly aligned between two corpora,
which does not necessarily hold in any corpus pair (e.g., comparison between
native and non-native speakers). [21, 14] extends this approach to discovering
semantic differences across languages while they require a word-alignment
dictionary across languages.

[22] avoid the problem in word alignment by learning word vectors and
alignment simultaneously. Their method has sensitive hyper-parameters that
needs to be tuned, which results in a complex combinatorial optimization
problem [1]. [7] propose a method for detecting semantic differences by
simultaneously optimizing multiple word vectors. While this method does not
require linear transformations nor extensive hyper-parameter search, it
requires a list of target words, which is not realistic in practical uses. [1]
extends [7]’s method by optimizing multiple context vectors together with
multiple word vectors. These non-alignment-based methods, however, still make
the assumption that word vectors and/or context vectors are close to each
other in two corpora. The task of detecting semantic differences is to find
words that are not aligned well in terms of their meanings in two corpora, and
thus methods requiring no assumption about the relation between word vectors
in two corpora are preferable.

[10] propose a method that does not make such assumptions based on nearest
neighbors obtained by non-contextualized word vectors, which makes it
applicable to any pair of corpora. At the same time, it suffers from the bias
in corpus sizes and the low frequency problem.

Some researchers try to use contextualized word vectors for semantic
difference detection. [12, 9, 16] automatically group contextualized word
vectors obtained to predict word meanings and then compare the results to
detect semantic differences. Predicting word meanings is another difficult
task itself. Also, it is computationally costly to train a classifier or
conduct clustering for every single word type found in corpora.

##  6 Conclusions

In this paper, we have proposed using the norms of mean word vectors to detect
semantic differences with their typical instances. The proposed methods do not
require the assumptions concerning words and corpora for comparison that the
previous methods do. The only assumption is that word vectors follow the von
Mises-Fisher distribution. Accordingly, the proposed methods are applicable to
corpus pairs such as native and non-native English corpora where the
assumptions of the previous methods do not hold. Also, they are simple and
efficient in that they do not require training nor extensive hyper-parameter
search. With the methods, we have actually discovered semantic differences in
native and non-native English corpora and also in historical corpora. We have
revealed that they are effective even for infrequent word instances and also
for corpora whose sizes are considerably different.

## References

  * [1] Aida, T., Komachi, M., Ogiso, T., Takamura, H., and Mochihashi, D. A comprehensive analysis of PMI-based models for measuring semantic differences.  In Proceedings of the 35th Pacific Asia Conference on Language, Information and Computation (Shanghai, China, 11 2021), Association for Computational Lingustics, pp. 21–31.
  * [2] Akshay, M., and Kulkarni, R. Clinical study of systemic inflammatory response syndrome in surgical intensive care unit patients.  PARIPEX Indian Journal of Research 7, 4 (2018), 60–62.
  * [3] Alatrash, R., Schlechtweg, D., Kuhn, J., and Schulte im Walde, S. CCOHA: Clean corpus of historical American English.  In Proc. of the 12th Language Resources and Evaluation Conference (2020), pp. 6958–6966.
  * [4] Banerjee, A., Dhillon, I. S., Ghosh, J., and Sra, S. Clustering on the unit hypersphere using von mises-fisher distributions.  Journal of Machine Learning Research 6, 46 (2005), 1345–1382.
  * [5] Davies, M. Expanding horizons in historical linguistics with the 400-million word corpus of historical American English.  Corpora 7, 2 (2012), 121–157.
  * [6] Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of deep bidirectional transformers for language understanding.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) (Minneapolis, Minnesota, June 2019), Association for Computational Linguistics, pp. 4171–4186.
  * [7] Dubossarsky, H., Hengchen, S., Tahmasebi, N., and Schlechtweg, D. Time-out: Temporal referencing for robust modeling of lexical semantic change.  In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (Florence, Italy, July 2019), Association for Computational Linguistics, pp. 457–470.
  * [8] Fujimura, I., Chiba, S., and Ohso, M. Lexical and grammatical features of spoken and written japanese in contrast : exploring a lexical profiling approach to comparing spoken and written corpora.  In Proc. of the 7th GSCP International Conference. Speech and Corpora (2013), pp. 393–398.
  * [9] Giulianelli, M., Del Tredici, M., and Fernández, R. Analysing lexical semantic change with contextualised word representations.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (Online, July 2020), Association for Computational Linguistics, pp. 3960–3973.
  * [10] Gonen, H., Jawahar, G., Seddah, D., and Goldberg, Y. Simple, interpretable and stable method for detecting words with usage change across corpora.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (Online, July 2020), Association for Computational Linguistics, pp. 538–555.
  * [11] Hamilton, W. L., Leskovec, J., and Jurafsky, D. Diachronic word embeddings reveal statistical laws of semantic change.  In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (Berlin, Germany, Aug. 2016), Association for Computational Linguistics, pp. 1489–1501.
  * [12] Hu, R., Li, S., and Liang, S. Diachronic sense modeling with deep contextualized word embeddings: An ecological view.  In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (Florence, Italy, July 2019), Association for Computational Linguistics, pp. 3899–3908.
  * [13] Ishikawa, S. A new horizon in learner corpus studies: The aim of the ICNALE project.  University of Strathclyde Publishing, Glasgow, 2011, pp. 3–11.
  * [14] Kawasaki, Y., Salingre, M., Karpinska, M., Takamura, H., and Nagata, R. Revisiting statistical laws of semantic shift in Romance cognates.  In Proceedings of the 29th International Conference on Computational Linguistics (Gyeongju, Republic of Korea, Oct. 2022), International Committee on Computational Linguistics, pp. 141–151.
  * [15] Kim, Y., Chiu, Y.-I., Hanaki, K., Hegde, D., and Petrov, S. Temporal analysis of language through neural language models.  In Proceedings of the ACL 2014 Workshop on Language Technologies and Computational Social Science (Baltimore, MD, USA, June 2014), Association for Computational Linguistics, pp. 61–65.
  * [16] Kobayashi, K., Aida, T., and Komachi, M. Analyzing semantic changes in Japanese words using BERT.  In Proceedings of the 35th Pacific Asia Conference on Language, Information and Computation (Shanghai, China, 11 2021), Association for Computational Lingustics, pp. 270–280.
  * [17] Kulkarni, V., Al-Rfou, R., Perozzi, B., and Skiena, S. Statistically significant detection of linguistic change.  In Proceedings of the 24th International World Wide Web Conference (2015), pp. 625–635.
  * [18] Lei, L., and Liu, Z. A word type-based quantitative study on the lexical change of american and british english.  Journal of Quantitative Linguistics 21, 1 (2014), 36–49.
  * [19] McEnery, T., Brezina, V., Gablasova, D., and Banerjee, J. Corpus linguistics, learner corpora, and sla: Employing technology to analyze language use.  Annual Review of Applied Linguistics 39 (2019), 74–92.
  * [20] Mikolov, T., Sutskever, I., Chen, K., Corrado, G., and Dean, J. Distributed representations of words and phrases and their compositionality.  In Advances in Neural Information Processing Systems 26 (2013), pp. 3111–3119.
  * [21] Takamura, H., Nagata, R., and Kawasaki, Y. Analyzing semantic change in Japanese loanwords.  In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers (Valencia, Spain, Apr. 2017), Association for Computational Linguistics, pp. 1195–1204.
  * [22] Yao, Z., Sun, Y., Ding, W., Rao, N., and Xiong, H. Dynamic word embeddings for evolving semantic discovery.  In Proceedings of the 11th ACM International Conference on Web Search and Data Mining (2018), pp. 673–681.


# kNN Classification of Malware Data Dependency Graph Features

John Musgrave  Computer Science Department
The College of Wooster
Wooster, OH
<EMAIL_ADDRESS>Anca Ralescu  Department of Computer Science
University of Cincinnati
Cincinnati, OH
<EMAIL_ADDRESS>
###### Abstract

Feature resolution impacts the ability of classifiers to make explainable
inferences when applied to malware classification. We explore classification
based on features constructed from data dependency graphs, and present results
from k-Nearest Neighbors (kNN) classifiers. Our study demonstrates that
classification based on a novel feature representation not only yields high
accuracy, but also increases explainability in inference, as features of data
dependency are directly representative of program behavior. We present
classification results using the Microsoft Kaggle 2015 malware dataset which
was processed with a novel approach to feature extraction and representation.
We show that non-parametric approaches to classification in the metric space
are able to obtain classification accuracy of 87.5% when applied to multi-
class classification in the Kaggle malware dataset. Additionally, similarity
in the metric space can be calculated directly without prior training. Our
results provide evidence that data dependency graphs accurately capture both
semantic and structural information.

###### Index Terms:

machine learning, feature extraction, malware analysis

##  I Introduction

In recent years many studies have focused on the applications of machine
learning to malware analysis. However, increases in interpretability are
limited by the features used in various classifiers. This study explores the
use of features constructed from graphs of data dependencies [1].

Many graph features for malware analysis are focused on control flow graph
features. When data flow tracking analysis is performed, it is often evaluated
in a top-down approach and compares data flow and data dependencies between
functions in high level languages [2].

Explainable approaches to operational semantics remain an open question. It
remains unclear why data movement instructions have few features that allow
for increases in resolution, given their prevalence of frequency. Recent
advances in large language models do not directly address explainability [3].

Data dependency graphs as features represent both operational semantics and
structural properties of binaries, can be constructed in a bottom-up approach,
and offer a potential increase in explainability. The purpose of this study is
to measure the accuracy of classifiers trained on these feature
representations.

Term (x86/64 Opcode) | # Of Occurrences
---|---
MOV | 61,312,709
PUSH | 26,067,804
CALL | 12,158,797
IMUL | 8,174,383
POP | 8,157,787
MUL | 8,114,871
NOP | 7,307,405
XOR | 7,171,442
CMP | 6,997,102
ADD | 6,404,277
LEA | 6,252,131
STD | 5,899,174
JZ | 5,124,385
TEST | 4,682,198
JNZ | 3,555,014
SUB | 3,461,608
CLD | 3,051,495
AND | 2,387,916
INC | 1,708,580
OR | 1,635,851
INT | 1,288,737
MOVZX | 1,227,559
XCHG | 1,122,534
DEC | 931,127
SHL | 827,192
TABLE I: Top 25 opcodes in the Kaggle 2015 dataset ordered by frequency in
descending order

###  I-A Related Work

The Microsoft Kaggle Malware dataset has been used successfully for many
studies on malware analysis and classification [4], [5].

Several studies on malware have focused on control flow graph representations
of programs and their use in classification. A number of studies explored the
use of static features of file metadata. Decision trees for the classification
of Windows PE files have been effective for classification. Subsequent studies
have used ensemble methods, random forests, and support vector machines, with
features extracted from file headers in Trojan malware [2], [6], [7], [8],
[9], [10], [11], [12].

Figure 1: Histogram of opcode frequencies in the Microsoft 2015 Kaggle malware
dataset

Several studies have focused on function abstraction semantics through
decompilation. LeDoux et al. represented a program as a graph of function
abstractions obtained from reverse engineering and used semantic hashing as a
measurement of similarity. However, this study did not take a bottom up
approach, and basic block features were specifically not considered. There may
be many equivalent programs for a given malware binary, and whether semantic
function abstractions in a high level language are correlated to lower level
binary representations is an open question. In a similar manner, Alrabaee et
al. have used a $tf-idf$ representation with Hidden Markov Models and graph
kernels to obtain a graph of semantic function abstractions for a program.
This was accomplished by constructing a Bayesian network for each of the
features collected [13], [14].

In a previous study we have performed a comparison of various classifiers and
clustering algorithms on a dataset of $tf-idf$ features. In a previous study,
we have been able to measure behavioral overlap between individual program
samples. We intend to show increases in explainability through the use of a
novel feature representation. Additionally we perform this analysis on a
larger dataset of malware, the Microsoft Kaggle malware dataset. [16], [21].

###  I-B Outline

Section 2 covers the details of the experiment performed, including method of
data collection and pre-processing. Section 3 covers experimental results.
Section 4 contains an analysis of the results, and a discussion of the
findings and their implications. Section 5 contains a summary and conclusion.

##  II Experiment

This section outlines the methods used in performing our experiments.

###  II-A Data Pre-Processing

The dataset used in this study was composed by processing the Microsoft 2015
Kaggle Malware dataset. This dataset uses the output of the Interactive
Disassembler or IDA Pro, and contains the text sections of over 10,000 binary
samples in the training set, along with their associated class labels. Each
sample contains the disassembled binary, and the output contains both the hex
values and x86 assembly instructions for the decompiled binary. Each sample
has a corresponding hash value as an identifier. Each sample in the dataset
belongs to one of 9 classes of malware, and there are no benign samples
present in the dataset [5].

As a motivating example, we present the results of a term frequency
measurement on the dataset. Using the $x86/64$ instruction set we have
constructed a term dictionary that includes each instruction opcode as a term.
The frequency of each opcode’s occurrence was measured across the dataset, and
this is shown in Table I and Figure 1. The overwhelming presence of data
movement instructions as seen in Table I are the primary motivation for
additional pre-processing and feature extraction. $tf-idf$ features often do
not take into consideration the semantics of data movement.

While a majority of the feature pre-processing and analysis was performed in
Python directly, additional methods in the $scikit-learn$ Python library were
used for the implementation of various algorithms [22].

Our dataset was segmented into basic blocks for further analysis, as outlined
in previous work. This is necessary for additional adjustments in feature
granularity. Segmentation was performed on instructions which require control
transfer, such as any number of jump instructions or the $call$ instruction.
Instructions using the stack such as $push$ were not evaluated, and control
flow analysis was not the primary focus of this study. A single segment in the
dataset corresponds to a contiguous segment of instructions, which represents
an atomic unit of operational semantics. Instructions re-ordered by the
processor must maintain semantic coherence, and this is done by maintaining
the coherence of dependencies. Therefore, a program can be represented as a
collection of these segments, which allows for further increases in resolution
[17].

Data dependency graphs were extracted for each segment and hashed for
isomorphism to construct a set of unique hashes as outlined in previous work.
Each program segment corresponds to a single data dependency graph, and a
single graph of data dependencies has an associated program segment. Data
operands are added as nodes in the graph, and a dependency is added as a graph
edge. Frequency of graph hashes is not considered in our representation, and
each set is filtered for a unique set of isomorphic hashes. While data
dependencies exist between many arithmetic instructions in the term
dictionary, our focus was on data movement instructions, since this term had
the highest frequency. Expanding our work to operands of other terms is an
area to be developed in future studies, as it may provide increases in
resolution. Similarly the differentiation of indirection may provide increases
in accuracy and resolution, we have not included an analysis of data
indirection in the features constructed, which are evaluated as separate
operands [19], [18].

Once the dataset has been segmented and data dependency graphs are extracted
each graph is hashed for uniqueness using the Weisfeiler-Lehman graph hashing
algorithm. This algorithm ensures that two graphs which are isomorphic produce
an identical hash value. Each unique hash is then recorded once in a list
resulting in features we have labeled a DDG Fingerprint [15], [18], [21].

A single program in the dataset corresponds to a set of hashes, each set
containing a unique list of categorical values. The categorical value
corresponds to the pattern of data movement ensured by the hashing algorithm
for graph isomorphism. Our dataset contains 10,617 sets of hashes, and there
are 74,872 isomorphically unique patterns across the entire dataset.

###  II-B Hamming Space

We construct a metric space using the Hamming Distance between the vectors of
categorical values. This is done by creating a one-hot encoding for each hash
value. The resulting metric space is a high dimensional space where the
distance to each vector can be calculated based on the Hamming Distance. This
approach is outlined in prior work [21].

The primary motivation for the use of Hamming Distance is that it provides a
distance for categorical features. Our study analyzes the formation of
clusters in the space constructed using this distance metric.

###  II-C k-Nearest Neighbors Classifier

We train a classifier using the k-Nearest Neighbors (kNN) algorithm. The kNN
algorithm classifies an example based on the majority class of its k-nearest
neighbors in the feature space. For our study, we used the training labels
provided in the Kaggle 2015 malware dataset to compose a labeled dataset. This
dataset was split into training and test sets to be used for classification,
which are 75% training and 25% for the test set. The training set was composed
of 7,962 samples, and the test set was composed of 2,655 samples. The
classifier measured were trained on the labeled training set, which has 9
class labels of malicious programs. The test set did not use class labels, and
the computed pairwise distances were maintained from the complete dataset.
This is done using the $scikit-learn$ Python library. The accuracy metrics
presented were measured from predictions of the classifiers over the test set
[22].

###  II-D Accuracy Metrics

We evaluate the results from the k-Nearest Neighbors classifier by selecting a
set of accuracy metrics. We evaluate each classifier in terms of its accuracy,
precision, recall, specificity, and F1 score, defined by the following:

$Accuracy=\frac{TP+TN}{TP+TN+FP+FN}$ $Precision=\frac{TP}{TP+FP}$
$Recall=\frac{TP}{TP+FN}$ $Specificity=\frac{TN}{FP+TN}$
$F1=\frac{2*Precision*Recall}{Precision+Recall}=\frac{2*TP}{2*TP+FP+FN}$

This is performed over a variety of values of $k$ for comparison purposes
between kNN classifiers.

Figure 2: Kaggle Malware Dataset Hamming Space. This figure shows the dataset
projected from a high dimensional metric space with Hamming Distance to 2
dimensions using t-SNE.

Figure 3: kNN Predictions. Pictured above is the composition in 2 dimensions
of the high dimensional hamming space with predicted class labels indicated by
the color of each data point.

Figure 4: Confusion matrix for k-Nearest Neighbors classifier with k=2.

Class | Accuracy | Precision | Recall | Specificity | F1 Score
---|---|---|---|---|---
1 | 0.9345 | 0.6535 | 0.6935 | 0.9875 | 0.6730
2 | 0.9667 | 0.8275 | 0.8965 | 0.9856 | 0.8605
3 | 0.9898 | 0.9630 | 0.9930 | 0.9907 | 0.9780
4 | 0.9780 | 0.8935 | 0.8240 | 0.9960 | 0.8570
5 | 0.9876 | 0.6665 | 0.2800 | 0.9956 | 0.3905
6 | 0.9746 | 0.8070 | 0.8105 | 0.9887 | 0.8087
7 | 0.9890 | 0.9230 | 0.9375 | 0.9930 | 0.9302
8 | 0.9497 | 0.7440 | 0.7745 | 0.9820 | 0.7590
9 | 0.9690 | 0.8035 | 0.8205 | 0.9926 | 0.8119

Figure 5: Accuracy metrics per class for kNN classifier with k=2. Precision,
recall, specificity, and F1 scores are displayed for each class.

Figure 6: Confusion Matrix for kNN classifier, k=3

Figure 7: Confusion Matrix for kNN classifier, k=4 Figure 8: Total accuracy as values of k increase. Accuracy shown for values of $k$ in the range 2 to 19. Class | Accuracy | Precision | Recall | Specificity | F1 Score
---|---|---|---|---|---
1 | 0.9320 | 0.6553 | 0.6923 | 0.9871 | 0.6733
2 | 0.9650 | 0.8158 | 0.8957 | 0.9846 | 0.8541
3 | 0.9892 | 0.9616 | 0.9916 | 0.9903 | 0.9764
4 | 0.9764 | 0.8766 | 0.8148 | 0.9950 | 0.8447
5 | 0.9875 | 0.6471 | 0.2857 | 0.9956 | 0.3953
6 | 0.9738 | 0.7989 | 0.8053 | 0.9879 | 0.8021
7 | 0.9885 | 0.9194 | 0.9375 | 0.9926 | 0.9284
8 | 0.9495 | 0.7421 | 0.7733 | 0.9818 | 0.7574
9 | 0.9686 | 0.8023 | 0.8180 | 0.9924 | 0.8101
TABLE II: Accuracy metrics per class for kNN classifier with k=3. Precision, recall, specificity, and F1 scores are displayed for each class. Class | Accuracy | Precision | Recall | Specificity | F1 Score
---|---|---|---|---|---
1 | 0.9326 | 0.6641 | 0.6892 | 0.9874 | 0.6761
2 | 0.9656 | 0.8225 | 0.8935 | 0.9851 | 0.8566
3 | 0.9893 | 0.9616 | 0.9916 | 0.9903 | 0.9764
4 | 0.9759 | 0.8571 | 0.7795 | 0.9945 | 0.8167
5 | 0.9876 | 0.6667 | 0.2857 | 0.9957 | 0.3976
6 | 0.9740 | 0.8021 | 0.7895 | 0.9881 | 0.7958
7 | 0.9887 | 0.9231 | 0.9375 | 0.9928 | 0.9302
8 | 0.9494 | 0.7407 | 0.7593 | 0.9818 | 0.7500
9 | 0.9688 | 0.8031 | 0.8160 | 0.9925 | 0.8095
TABLE III: Accuracy metrics per class for kNN classifier with k=4. Precision,
recall, specificity, and F1 scores are displayed for each class.

##  III Results

Table 1 contains a partial list of the $x86/64$ instruction opcodes taken from
the term dictionary. This table shows the frequency of occurrence for the most
frequent instructions in the dataset. We can see that the ’$mov$’ instruction
has the highest frequency.

Figure 1 shows the term frequency data plotted as a frequency histogram in
order to see the distribution of term frequency. We can see that the ’$mov$’
instruction has the highest frequency in the Kaggle malware dataset, with over
61 Million occurrences.

Figure 2 shows a scatter plot of complete dataset in Hamming Space. Since the
Hamming vectors are high dimensional, this figure shows a projection of the
high dimensional space in 2 dimensions using t-SNE. The total dimensionality
of the space is 74,872 [20].

Figure 3 shows a scatter plot of the dataset with class predictions from the
kNN classifier for each data point. The Kaggle malware dataset is composed of
9 distinct malware classes with no benign samples.

Figure 4 shows a confusion matrix for the k-NN classifier with k=2. The
accuracy metrics were used to measure the classifier’s performance across the
test set of n samples. True labels are presented on the vertical axis, and
predicted labels on the horizontal axis. We return to an analysis of the
selected accuracy metrics in the following section.

Table 2 presents accuracy metrics for the same classifier. Total accuracy is
the true positive plus false positive divided by the total, in order to
exclude mispredictions. In order to calculate the total accuracy we can take
the true positive value of 2,314 true predictions and divide it by the size of
the test set, 2,657. More detail on the total accuracy of classifiers are
presented in table 3.

Figures 5 and 6 present results for kNN classifiers with k values 3 in a
confusion matrix. Both classifiers have a total accuracy of 85% or better.

Figure 7 shows the total accuracy of the classifier and the impact of k as the
value of k increases. We can see that as k increases, the total accuracy of
the classifier decreases. The total accuracy is calculated by the number of
true predictions over the total number predictions when measured over the test
set.

Tables 3 and 4 present accuracy metrics for kNN classifiers with k=4 and k=5,
respectively. The accuracy for each class, along with the precision, recall,
specificity, and F1 score are presented.

Figure 8 shows the decision boundary of the k-NN classifier in the Hamming
Space.

Additional figures are presented in the appendix section. Figure 9 shows a
confusion matrix for k=5. Table 5 presents accuracy metrics for a kNN
classifier with k=5. Figure 10 shows a scatter plot of the dataset with true
class labels. Figure 11 shows a scatter plot of predictions from the kNN
classifier with k=5.

Figure 9: Decision boundary for kNN classifier, k=2. The decision boundary is
plotted in the 2 dimensional projection of the Hamming space using t-SNE.

##  IV Discussion

The findings of this study show that the kNN classifiers observed have a
recorded accuracy that is high overall. For kNN with k=1, the total accuracy
measured in 0.875, k=2, has a total accuracy score of 0.871. The impact of k
on the total accuracy is shown in figure 7. Values of k less than 4 have an
accuracy above 0.850. We can see that as the value of k increases, the total
accuracy decreases. Values 5 to 18 have accuracy above 0.800. This decrease
slows between k values 10 to 20, which are between the range 0.820 and 0.790.

Likewise, for k=2 the per-class accuracy indicates strong performance, however
classes 1 and 5 have the weakest overall metrics as shown in Figure 4 and
Table 2. The remaining classes have high precision and recall values based on
their predictions across the test set. Accuracy metrics for class 8 are more
moderate compared to other classes. Class 1 has lower precision and recall,
however these values are balanced. Class 5 has moderate precision, and a low
recall value. This indicates that class 5 has a relatively high number of
false negatives. Class 3 has the highest values for both precision and recall
for this classifier.

Since malicious programs would be encountered in an adversarial environment,
the goal of the attacker would be a high rate of false negative
classification. The results of classes 1 and 5 having moderate to low recall
indicate that this class of malware is misclassified due to the impact of
false negatives on classification. A more fine grained analysis of this class
of malware can measure the functional overlap of specific samples using the
same feature representation and metric space.

A number of trade-offs exist within our method that require further
consideration. One strength is that the similarity of individual samples can
be computed directly with no training through the use of the distance metric.
However, in order to evaluate a new sample in comparison to an existing
corpus, features must be extracted and collected into a library of examples.
This feature extraction process is expensive in terms of computation time, but
can be performed ahead of time by processing the dataset offline. The feature
extraction process described entails segmentation of each binary into basic
block segments, then extracting graphs of data dependencies that exist between
operands for each segment. For more detail, see Musgrave et al. 2024. One
consideration is that after features have been extracted the metric space must
be re-computed for new data. However, this process has low computational
resource requirements, requiring a single matrix multiplication in the case of
one-hot encoded vectors. This is ideal for encountering a finite number of new
examples, and can be computed in real-time. The resulting metric space is high
dimensional, but non-parametric methods may be used effectively. Methods
sensitive to high dimensions may suffer a decrease in performance. However,
support vector machines are able to be used efficiently in high dimensional
spaces [21].

k-Nearest Neighbors as a classification approach has less implementation
complexity and relies heavily on the feature representation and distance
metric. This was done to test the effectiveness of the distance metric and
feature representation and their ability to capture semantic information. The
distance metric is the Hamming distance between two vectors, the vectors are
one-hot encoded representations of categorical values. The categorical
features are hash representations of graph isomorphic patterns. The graphs
were extracted from operand dependencies between data movement instructions,
which are hashed for isomorphic uniqueness. The feature representation allows
us to use the distance metric to measure similarity. Existing approaches
trained on $tf-idf$ features often do not take into account a fine-grained
analysis of data dependency graph features, and therefore are required to show
that their classification is correlated to operational semantics and
structure. Resolution increases in the feature space for $tf-idf$ features
present a significant challenge, and there is not a straightforward approach
to analyzing the body of the term frequency distribution, which is positively
skewed towards data movement instructions. The representation we have chosen
addresses these concerns, and provides a foundation for further inferences,
since it is constructed in a bottom up approach and tied directly to patterns
of data movement [23], [24].

One explanation for the accuracy measurements in classification is the choice
of feature representation, and its ability to capture semantic information. If
the data dependency graphs contained no semantic information, then we would
expect the accuracy numbers to be very low. Low classification accuracy would
be an indication that isomorphism of data dependency graphs between operands
of instructions are not good representations of program behavior, operational
semantics, or structural patterns. However, an analysis only based on operands
of ’$mov$’ instructions can provide accuracy of 87.5% with non-parametric
learning approaches. This indicates that the feature representation is
sufficiently capturing semantic information.

Accurate classification results for this feature representation provide
evidence that direct inferences can be made from the extracted features, since
the accuracy corresponds to the ground-truth labels. Similarity in the metric
space corresponds to a direct inference of both the operational semantics and
structural properties captured by the feature representation. This is because
data dependency graphs capture both structural and semantic information. This
is validated by the classification accuracy. Increases in accuracy represent
the ability to make inferences that are based on quantifying patterns of
operational semantics, behavior, and structural composition. Based on the
presence of patterns of data movement and structural measurements, we are able
to make inferences to the patterns of behavior within the program. This
provides the ability for fine-grained analysis of program semantics, and the
ability to categorize larger classes of program behavior.

Some limitations in our study are that only operand dependencies between
’$mov$’ instructions were taken into consideration when constructing the
features. This could be expanded to include other instruction types for a more
complete picture of data dependencies. This would be an area to provide
resolution increases. Additionally, refining the metric space to be more
granular will likely provide more insights. Expanding the dataset to include
benign samples will likely provide better generalization.

We highlight that our method allows for further refinements, reduction in the
search space, and increases in resolution to provide more fine grained
results. These approaches are recommended for future studies. In future work
we intend to increase the accuracy through increasing the feature resolution,
as well as explore the impact of fuzzy models including fuzzy c-means.

##  V Conclusion

In this study we have presented results from k-Nearest Neighbors classifiers
across several k values, and have evaluated these classifiers based on
precision, recall, specificity, F1 score, and total accuracy. We have shown
that a classifier trained on our feature representation obtained a total
accuracy for a multi-class classification task of 87.5%. Similarity in the
metric space can be calculated without prior training. This demonstrates the
method of feature representation, and validates the hypothesis that data
dependency isomorphism is representative of program behavior and operational
semantics.

## Acknowledgment

The authors would like to acknowledge the support of the Air Force Research
Lab at Wright-Patterson Air Force Base in Dayton, Ohio.

This study was performed with computing resources provided by the Computer
Science department at The College of Wooster in Wooster, Ohio.

## References

  * [1] A. Souri and R. Hosseini, A state-of-the-art survey of malware detection approaches using data mining techniques, Human-centric Computing and Information Sciences, vol. 8, no. 1, pp. 3, 2018.
  * [2] D. Bruschi, L. Martignoni, and M. Monga, Detecting self-mutating malware using control-flow graph matching, in International conference on detection of intrusions and malware, and vulnerability assessment, pp. 129–143, Springer, 2006.
  * [3] F. F. Xu, U. Alon, G. Neubig, and V. J. Hellendoorn, A systematic evaluation of large language models of code, in Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming, pp. 1–10, 2022.
  * [4] Kebede, T., Djaneye-Boundjou, O., Narayanan, B., Ralescu, A. & Kapp, D. Classification of malware programs using autoencoders based deep learning architecture and its application to the microsoft malware classification challenge (big 2015) dataset. 2017 IEEE National Aerospace And Electronics Conference (NAECON). pp. 70-75 (2017)
  * [5] Ronen, R., Radu, M., Feuerstein, C., Yom-Tov, E. & Ahmadi, M. Microsoft Malware Classification Challenge. (2018)
  * [6] S. Cesare and Y. Xiang, A fast flowgraph based classification system for packed and polymorphic malware on the endhost, in 2010 24th IEEE International Conference on Advanced Information Networking and Applications, pp. 721–728, IEEE, 2010.
  * [7] S. Cesare, Y. Xiang, and W. Zhou, Control flow-based malware variant detection, IEEE Transactions on Dependable and Secure Computing, vol. 11, no. 4, pp. 307–317, 2013.
  * [8] S. Cesare and Y. Xiang, Classification of malware using structured control flow, in Proceedings of the Eighth Australasian Symposium on Parallel and Distributed Computing-Volume 107, pp. 61–70, 2010.
  * [9] M. Z. Shafiq, S. M. Tabish, F. Mirza, and M. Farooq, Pe-miner: Mining structural information to detect malicious executables in realtime, in International Workshop on Recent Advances in Intrusion Detection, pp. 121–141, Springer, 2009.
  * [10] M. Siddiqui, M. C. Wang, and J. Lee, Detecting trojans using data mining techniques, in International Multi Topic Conference, pp. 400–411, Springer, 2008.
  * [11] I. H. Witten, E. Frank, L. E. Trigg, M. A. Hall, G. Holmes, and S. J. Cunningham, Weka: Practical machine learning tools and techniques with Java implementations,
  * [12] Chandrasekaran, M., Ralescu, A., Kapp, D. & Kebede, T. Malware Detection using the Context of API Calls. NAECON 2021-IEEE National Aerospace And Electronics Conference. pp. 92-97 (2021)
  * [13] C. LeDoux, A. Lakhotia, C. Miles, V. Notani, and A. Pfeffer, $\\{$FuncTracker$\\}$: Discovering Shared Code to Aid Malware Forensics, in 6th USENIX Workshop on Large-Scale Exploits and Emergent Threats (LEET 13), 2013\.
  * [14] S. Alrabaee, P. Shirani, L. Wang, and M. Debbabi, Fossil: a resilient and efficient system for identifying foss functions in malware binaries, ACM Transactions on Privacy and Security (TOPS), vol. 21, no. 2, pp. 1–34, 2018.
  * [15] N. Shervashidze, P. Schweitzer, E. J. Van Leeuwen, K. Mehlhorn, and K. M. Borgwardt, Weisfeiler-lehman graph kernels, Journal of Machine Learning Research, vol. 12, no. 9, 2011.
  * [16] J. Musgrave, C. Purdy, A. L. Ralescu, D. Kapp, and T. Kebede, Semantic Feature Discovery of Trojan Malware using Vector Space Kernels, in 2020 IEEE 63rd International Midwest Symposium on Circuits and Systems (MWSCAS), pp. 494–499, IEEE, 2020.
  * [17] J. Musgrave, T. Messay-Kebede, D. Kapp, and A. Ralescu, Latent Semantic Structure in Malicious Programs, in International Conference on Modelling and Development of Intelligent Systems, pp. 234–246, Springer, 2022.
  * [18] John Musgrave, Temesguen Messay-Kebede, David Kapp, and Anca Ralescu, A Novel Feature Representation for Malware Classification, arXiv preprint arXiv:2210.09580, 2022\.
  * [19] Musgrave, J., Campan, A., Messay-Kebede, T., Kapp, D. & Wang, B. Empirical Network Structure of Malicious Programs. Learning. 4, 112 (2024)
  * [20] G. E. Hinton and S. Roweis, Stochastic neighbor embedding, Advances in neural information processing systems, vol. 15, 2002.
  * [21] Musgrave, J., Campan, A., Messay-Kebede, T., Kapp, D. & Wang, B. Search and Retrieval in Semantic-Structural Representations of Novel Malware. Advances In Artificial Intelligence And Machine Learning. 4, 117 (2024)
  * [22] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V. & Others Scikit-learn: Machine learning in Python. The Journal Of Machine Learning Research. 12 pp. 2825-2830 (2011)
  * [23] J. Brownlee, Why one-hot encode data in machine learning, Machine Learning Mastery, pp. 1–46, 2017.
  * [24] R. W. Hamming, Error detecting and error correcting codes, The Bell system technical journal, vol. 29, no. 2, pp. 147–160, 1950.

Figure 10: Confusion Matrix for kNN classifier, k=5 Class | Accuracy | Precision | Recall | Specificity | F1 Score
---|---|---|---|---|---
1 | 0.9306 | 0.6597 | 0.6713 | 0.9868 | 0.6655
2 | 0.9635 | 0.8074 | 0.8691 | 0.9836 | 0.8371
3 | 0.9886 | 0.9606 | 0.9916 | 0.9900 | 0.9759
4 | 0.9739 | 0.8449 | 0.7284 | 0.9935 | 0.7823
5 | 0.9870 | 0.6900 | 0.2857 | 0.9954 | 0.4024
6 | 0.9733 | 0.7925 | 0.7737 | 0.9874 | 0.7829
7 | 0.9887 | 0.9302 | 0.9375 | 0.9930 | 0.9338
8 | 0.9485 | 0.7347 | 0.7470 | 0.9810 | 0.7408
9 | 0.9679 | 0.7969 | 0.8133 | 0.9920 | 0.8050
TABLE IV: Accuracy metrics per class for kNN classifier with k=5. Precision,
recall, specificity, and F1 scores are displayed for each class.

Figure 11: Kaggle Malware Dataset with true class labels. Picture is the
dataset composition in 2 dimensions with true class labels indicated by the
color of each data point.

Figure 12: kNN Classifer, k=5