# On Impact of Semantically Similar Apps in Android Malware Datasets
* ††thanks: Identify applicable funding agency here. If none, delete this.

Roopak Surendran  Kerala,India

###### Abstract

Malware authors reuse the same program segments found in other applications
for performing the similar kind of malicious activities such as information
stealing, sending SMS and so on. Hence, there may exist several semantically
similar malware samples in a family/dataset. Many researchers unaware about
these semantically similar apps and use their features in their ML models for
evaluation. Hence, the performance measures might be seriously affected by
these similar kinds of apps. In this paper, we study the impact of
semantically similar applications in the performance measures of ML based
Android malware detectors. For this, we propose a novel opcode subsequence
based malware clustering algorithm to identify the semantically similar
malware and goodware apps. For studying the impact of semantically similar
apps in the performance measures, we tested the performance of distinct ML
models based on API call and permission features of malware and goodware
application with/without semantically similar apps. In our experimentation
with Drebin dataset, we found that, after removing the exact duplicate apps
from the dataset ($\epsilon=0$) the malware detection rate (TPR) of API call
based ML models is dropped from 0.95 to 0.91 and permission based model is
dropped from 0.94 to 0.90. In order to overcome this issue, we advise the
research community to use our clustering algorithm to get rid of semantically
similar apps before evaluating their malware detection mechanism.

###### Index Terms:

Code reuse, Android malware, Opcodes

##  I Introduction

It is known that, malware apps frequently reuse the program segments of
previously detected malware apps [1]. Also, they can add some junk codes or
remove redundant codes to change the signatures. However, these malicious apps
tend to preserve the malicious program segments intended for some specific
functionalities such as information stealing, sending SMS and so on. Hence, it
is clear that there may exist common malicious program segments shared by the
Android malware families.

Android is an open source operating system which provides specific APIs
(Application Programming Interface) to perform sensitive operations such as
sending SMS, making phone call and so on [2]. For example, sendTextMessage()
API call can be used for sending SMS to others. Initially, a malware author
constructs a malicious program segment which is intended to perform a
particular kind of malicious activity. This is done by invoking some specific
API calls in a particular manner. For convenience, evolving malware apps tend
to reuse these existing malicious program segments to perform the same kind of
behavior. Furthermore, there exists several other existing frameworks such as
kwetza for injecting the existing malicious program segments into benign
applications.

Most of the existing works use machine learning algorithms for malware
classification [3]. These approaches randomly select malware and goodware
samples from the dataset for training and testing the classifiers. Some of the
malware or goodware apps are semantically similar and may contain similar
features. These semantically similar apps can result in overrated performance
of the machine learning classifier especially in holdout evaluation. So, the
reported accuracies in their paper may be biased. However, the performance of
the models are not highly affected in k-fold cross validation based
evaluation. In this paper, we make a study about this problem and propose a
clustering algorithm to filter out the semantically similar apps from malware
and goodware datasets.

In recent years, many research papers have been published in the area of
Android malware detection. These works are classified into static, dynamic and
hybrid analysis. In static analysis, the source code level features such as
API calls, permissions etc. are used for malware detection. However, in the
cases of dynamic analysis, the runtime features such as system calls, network
packets etc. are used. In hybrid analysis, both static and dynamic features
are used. Most of the existing works use Drebin dataset for evaluating their
mechanism. Drebin is a public malware dataset which contains 5560 malware apps
from 179 malware families [4]. Because of this popularity of Drebin dataset,
we have selected this Drebin dataset for studying the impact of semantically
similar apps in ML models. The usage of applications with similar program
segments in experimental evaluations can give biased results. So it is
necessary to identify applications to similar programs segments. For this, we
propose a novel malware clustering algorithm based on opcode subsequences to
filter out semantically similar apps. The researchers can use the filtered
datasets for their experimental purpose for eliminating the bias in their
results.

In this work, we study the impact of semantically similar apps in machine
learning models for malware detection. A clustering algorithm is proposed to
filter out similar applications from both goodware and malware dataset. Then,
we tested the performance of ML models in various features of malware and
goodware samples with and without the semantically similar apps. We found that
the performance of ML models very slightly dropped after the semantically
similar apps from the dataset when k-fold cross validation technique is used.
Hence, it is advised to use k-fold cross validation for evaluating the models
or filter out the semantically similar apps from malware and goodware dataset
for fair evaluation.

Figure 1: Clustering of Android Apps in the Dataset

The rest of the paper organized as follows. In Section 2, we discuss about the
literature review. In Section 3, we discuss about the procedure of extracting
opcode subsequences of an application. Our malware clustering algorithm is
discussed in Section 4. In Section 5, we discuss about the performance of ML
models in Drebin dataset with and without the semantically similar apps. In
Section 6, we discuss about the limitations and future directions for our
work.

##  II Literature Review

In this section, we discuss about the existing research works on code reuse
and Android malware detection.

###  II-A Detection of Code Reuse

Many researchers discussed about the impact of code reuse in Android
applications. By using the existing program segment dedicated for a particular
functionality, an application developer can significantly save his time and
effort. Moreover, it is very helpful to reduce errors or bugs in the
application. However, now a days, this feature is increasingly misused by the
hackers. They generate several versions of a particular kind of malware app by
injecting its payload (malicious code segments) into other legitimate apps.
Because of the dissimilarity in hash values, anti-malware solutions are easily
evaded by these repackaged malware apps. In this section, we discuss about the
main works related to the code reuse detection in malware apps.

In GroupDroid [5], static control flow graphs were used for clustering 4211
Android malware apps into different groups. In Droidsim [1], component based-
control flow graphs were used for identifying similarities among malware apps
and found the code reuse in a dataset of 706 malware applications. Hanna et
al. [6] proposed a framework called JuxtApp for detecting code reusage among
Android applications. In JuxtApp, the feature matrix of applications were
constructed for measuring the similarities. JuxtApp identified the malicious
code reusage in 463 vulnerable apps and 34 malware apps. In DNADroid [7],
program dependency graphs were used for measuring the similarities among the
applications and found code cloning in at least 141 apps in their dataset.

In the area of Android malware detection, many researchers considered the
features of cloned apps (semantically similar) in their ML model. In this
work, we study the impact of these semantically apps in ML models. For this,
we propose a simple and lightweight algorithm to detect semantically similar
applications in a malware dataset. Here, we used opcode subsequences as
features for measuring the similarities. It is because the program segments
(program statements in a function or methods) of an application can be
conveniently represented with opcode subsequences. Hence,
similarity/dissimilarity values can be easily computed from by comparing
different sets of opcode subsequences.

###  II-B Review on Malware Detection Mechanisms

In existing works, machine learning algorithms are used for malware analysis
because of the ability to predict malicious behavior in unseen data points
[8]. Most of the popular works use Drebin dataset for evaluation. Drebin is
the public malware dataset which contains 5560 malware apps from 179 malware
families [4]. Also, Drebin dataset contains malicious applications from
MalGenome dataset. Hence, we have selected Drebin dataset for studying the
impact of semantically similar apps in ML models. The existing Android malware
detection mechanisms use either static features such as API calls, permissions
etc. or dynamic features such as system calls, network packets etc. (or the
combination of both) for malware analysis. The popular static and dynamic
malware analysis mechanisms in Drebin/MalGenome dataset are discussed below.

In static analysis, the features associated with the source code of an
application is used for malware detection. In [9], the authors used
probabilistic machine learning classifiers trained with API call based
features for malware detection. In [10], the app permissions are used as input
features of a machine learning classifier for malware detection. In [11], the
data flows are extracted from an application for finding malicious behavior.
In [12], the intent based features are used in a machine learning classifier
for malware detection. In [13], n-gram frequencies of opcode level features
are used in a machine learning classifier for malware detection.

In dynamic analysis, an application is executed in an emulator or in a real
device and collect the features such as system calls, network packets using
the third party utilities. In [14], the runtime API calls are used for malware
detection. In [15], authors used system metric level features such as CPU,
memory usages for malware detection. In [16] , the authors used system calls
as features of supervised binary classifiers for malware detection. In [17],
the authors used network packets as features for malware detection.

In all of the above mechanisms, the authors used entire samples in their
dataset (Drebin/MalGenome) for the experimental purpose. It is known that a
malware author reuses existing malicious codes to generate new varients.
Hence, these malware dataset may contain several semantically similar apps. In
this paper, we study the impact of semantically similar apps in machine
learning models for malware detection. We propose a clustering algorithm to
filter out the semantically similar apps from datasets. After removing the
semantically similar apps, we tested the performance of ML models in datasets
with and without semantically similar apps. From our experimental evaluations,
we conclude that the presence of semantically similar apps result in the
overrated performance of ML models in malware detection.

##  III Opcode Based Clustering Algorithm

In this section, we investigate the impact of semantically similar apps in
Android malware datasets. Our mechanism has three phases. In the first phase,
we extract opcode subsequences from a set of malware and goodware
applications. In the next phase, we filter out the semantically similar
applications from the opcode subsequence dataset using our novel clustering
algorithm. In the final phase, we evaluate the performance of ML models in
dataset with and without semantically similar apps. On the basis of this
performance evaluation, we will make conclusions. The clustering procedure is
given in Figure 1.

Figure 2: Method Based Opcode Sub sequence of an Application

###  III-A Extraction of Opcodes Subsequences from an Android Application

In this section, we discuss about the procedure of extracting opcode
subsequences from Android applications. Opcodes (Operation Codes) are used to
specify the kind of operations need to be performed by the device hardware. It
is a part of machine language program. The details about the opcodes in
Android operating system are given in Table I.

TABLE I: List Opcodes in Android Operating System

Hex Value | Opcode | Hex Value | Opcode | Hex Value | Opcode | Hex Value | Opcode
---|---|---|---|---|---|---|---
00 | nop | 01 | move | 02 | move/from 16 | 03 | move/16
04 | move-wide/from | 05 | move-wide/16 | 07 | move-object | 08 | move-object/from16
09 | move-object/16 | 0A | move-result | 0B | move-result-wide | 0C | move-result-object
0D | move-exception | 0E | return-void | 0F | return | 10 | return-wide
11 | return-object | 12 | const/4 | 13 | const/16 | 14 | const
15 | const | 16 | const-wide/16 | 17 | const-wide/32 | 18 | const-wide
19 | const-wide/high 16 | 1A | const-string | 1B | const-string-jumbo | 1C | const-class
1D | monitor-enter | 1E | monitor-exit | 1F | check-cast | 20 | instance-of
21 | array-length | 22 | new-instance | 23 | new-array | 24 | filled-new-array
25 | filled-new-array-range | 26 | fill-array-data | 27 | throw | 28 | goto
29 | goto/16 | 2A | goto/32 | 2B | packed-switch | 2C | sparse-switch
2D | cmpl-float | 2E | cmpg-float | 2F | cmpl-double | 30 | cmpg-double
31 | cmp-long | 32 | if-eq | 33 | if-ne | 34 | if-lt
35 | if-ge | 36 | if-gt | 37 | if-le | 38 | if-eqz
39 | if-nez | 3A | if-ltz | 3B | if-gez | 3C | if-gtz
3D | if-lez | 3E | unused_3E | 3F | unused_3F | 40 | unused_40
41 | unused_41 | 42 | unused_42 | 43 | unused_43 | 44 | aget
45 | aget-wide | 46 | aget-object | 47 | aget-boolean | 48 | aget-byte
49 | aget-char | 4A | aget-short | 4B | aput | 4C | aput-wide
4D | aput-object | 4E | aput-boolean | 4F | aput-byte | 50 | aput-char
51 | aput-short | 52 | iget | 53 | iget-wide | 54 | iget-object
55 | iget-boolean | 56 | iget-byte | 57 | iget-char | 58 | iget-short
59 | iput | 5A | iput-wide | 5B | iput-object | 5C | iput-boolean
5D | iput-byte | 5E | iput-char | 5F | iput-short | 60 | sget
61 | sget-wide | 62 | sget-object | 63 | sget-boolean | 64 | sget-byte
65 | sget-char | 66 | sget-short | 67 | sput | 68 | sput-wide
69 | sput-object | 6A | sput-boolean | 6B | sput-byte | 6C | sput-char
6D | sput-short | 6E | invoke-virtual | 6F | invoke-super | 70 | invoke-direct
71 | invoke-static | 72 | invoke-interface | 73 | unused_73 | 74 | invoke-virtual/range
75 | invoke-super/range | 76 | invoke-direct/range | 77 | invoke-static/range | 78 | invoke-interface-range
79 | unused_79 | 7A | unused_7A | 7B | neg-int | 7C | not-int
7D | neg-long | 7E | not-long | 7F | neg-float | 80 | neg-double
81 | int-to-long | 82 | int-to-float | 83 | 83 int-to-double | 84 | long-to-int
85 | long-to-float | 86 | long-to-double | 87 | float-to-int | 88 | float-to-long
89 | float-to-double | 8A | double-to-int | 8B | double-to-long | 8C | double-to-float
8D | int-to-byte | 8E | int-to-char | 8F | int-to-short | 90 | add-int
91 | sub-int | 92 | mul-int | 93 | div-int | 94 | rem-int
95 | and-int | 96 | or-int | 97 | xor-int | 98 | shl-int
99 | shr-int | 9A | ushr-int | 9B | add-long | 9C | sub-long
9D | mul-long | 9E | div-long | 9F | rem-long | A0 | and-long
A1 | or-long | A2 | xor-long | A3 | shl-long | A4 | shr-long
A5 | ushr-long | A6 | add-float | A7 | sub-float | A8 | mul-float
A9 | div-float | AA | rem-float | AB | add-double | AC | sub-double
AD | mul-double | AE | div-double | AF | rem-double | B0 | add-int/2addr
B1 | sub-int/2addr | B2 | mul-int/2addr e | B3 | div-int/2addr | B4 | rem-int/2addr
B5 | and-int/2addr | B6 | or-int/2addr | B7 | xor-int/2addr | B8 | shl-int/2addr
B9 | shr-int/2addr | BA | ushr-int/2addr | BB | add-long/2addr | BC | sub-long/2addr
BD | mul-long/2addr | BE | div-long/2addr | BF | rem-long/2addr | C0 | and-long/2addr
C1 | or-long/2addr | C2 | xor-long/2addr | C3 | shl-long/2addr | C4 | shr-long/2addr
C5 | ushr-long/2addr | C6 | add-float/2addr | C7 | sub-float/2addr | C8 | mul-float/2addr
C9 | div-float/2addr | CA | rem-float/2addr | CB | add-double/2addr | CC | sub-double/2addr
CD | mul-double/2addr | CE | div-double/2addr | CF | rem-double/2addr | D0 | add-int/lit16
D1 | add-int/lit16 | D2 | sub-int/lit16 | D3 | mul-int/lit16 | D4 | div-int/lit16
D5 | and-int/lit16 | D6 | or-int/lit16 | D7 | xor-int/lit16 | D8 | add-int/lit8
D9 | sub-int/lit8 | DA | mul-int/lit8 | DB | div-int/lit8 | DC | rem-int/lit8
DD | and-int/lit8 | DE | or-int/lit8 | DF | xor-int/lit8 | E0 | shl-int/lit8
E1 | shr-int/lit8 | E2 | ushr-int/lit8 | E3 | unused_E3 | E4 | unused_E4
E5 | unused_E5 | E6 | unused_E6 | E7 | unused_E7 | E8 | unused_E8
E9 | unused_E9 | EA | unused_EA | EB | unused_EB | EC | unused_EC
ED | unused_ED | EE | execute-inline | EF | unused_EF | F0 | invoke-direct-empty
F1 | unused_F1 | F2 | iget-quick | F3 | iget-wide-quick | F4 | iget-object-quick
F5 | iput-quick | F6 | iput-wide-quick | F7 | iput-object-quick | F8 | invoke-virtual-quick
F9 | invoke-virtual-quick/range | FA | invoke-super-quick | FB | invoke-super-quick/range | FC | unused_FC
FD | unused_FD | FE | unused_FE | FF | unused_FF |  |

In Android operating system, ART (Android Runtime) or Dalvik Virtual Machine
(DVM) is responsible for handling the opcodes in the form of dex (dalvik
executable format) file format [18][19]. Android programs are written in java
or kotlin language and then compiled to a ‘dex’ (dalvik executable format)
file [19].

Figure 3: Process of Extracting Opcode Sub sequences of an Application

In an Android application, the program segments are written in the form of
various functions or methods. Hence, there exist opcode subsequences
corresponding to each program segment in that application. We extract the set
of opcode subsequences from an application and use this opcode subsequence set
for representing it.

Reverse engineering tools such as apktool can be used to extract opcode
sequences from the ‘dex’ file [20]. Apktool extracts the opcode subsequences
from it. Here, we considered opcode subsequences as the sequence of opcodes in
a method segment. A sample opcode subsequence of an application is given in
Figure 2. The procedure of extracting opcode subsequences is given in Figure
3.

###  III-B Clustering Opcode Subsequences

In this section, we propose a novel algorithm for clustering the malware apps
in a dataset. Here, we cluster the malware apps in the malware dataset by
using our algorithm. Here, we use Ochiai coefficient (Euclidean distance) [21,
22, 23] for measuring the similarities between two applications. Cosine
similarity works well even if the opcode subsequences of apps differs in size.
Assume that $A$ and $B$ are the two sets of opcode subsequences of
applications $P$ and $Q$. The Ochiai coefficient $S$ is calculated as:

$S=1-\frac{|A\cap B|}{\sqrt{|A|\times|B|}},$ (1)

where $|A\cap B|$ is the number of opcode subsequences that are found in both
$A$ and $B$, $|A|$ is the number of opcode subsequences in $A$ and $|B|$ is
the number of opcode subsequences in $B$. //////////////

The proposed malware clustering algorithm is based on DBSCAN algorithm [24]
[25]. The algorithm accepts a malware family dataset
$X=\\{X_{1},X_{2}X_{3},…,X_{n}\\}$ as input and gives the cluster centers
$C=\\{C_{1},C_{2},…\\}$ as output. Let $\epsilon$ be the distance value
ranging from 0 to 1. The steps in our algorithm are given below.

  1. 1.

Initialize $j=1$.

  2. 2.

Select a random malware app $X_{i}$ from $X$ and mark $X_{i}$ as visited.

  3. 3.

Find out the neighbours of $X_{i}$ using $\epsilon$ (All malware apps which
are within the $\epsilon$ distance value are considered as neighbours).

  4. 4.

Form a cluster having centroid $C_{j}=X_{i}$ and update $j=j+1$.

    1. (a)

Remove all the clustered apps from $X$

  5. 5.

Go to step 1 and repeat the process until all apps in $X$ are visited

##  IV Illustration of Our Clustering Algorithm in Drebin Dataset

In this section, we discuss about the performance of our clustering algorithm
in dataset[4] because of its wide acceptance and popularity in research works.
Drebin dataset consists of 5560 malware applications selected from 179 malware
families over a period ranging from 2010 to 2012.

Our clustering algorithm is developed and tested in an Ubuntu PC having 32 GB
of memory. We reused an existing python program [26] to extract opcode
subsequences of the applications in our malware family dataset. In that python
code, apktool [27] is used to decompile an application and extract smali code
from it. From the smali code, opcode subsequences are extracted and saved in a
file. Then, we cluster all these files using our algorithm to identify the
semantically similar applications.

We execute our clustering algorithm in different values of $\epsilon$. With
the value $\epsilon=0$, we can remove all duplicate applications in the
dataset. Also, the obtained clusters are more reliable. The number of clusters
get reduced by increasing the value of $\epsilon$. Hence, by increasing the
value of $\epsilon$, we can identify the highly dissimilar apps in the
dataset. The number of clusters in different $\epsilon$ values are given in
Figure 4. Here, we found that almost 50% of apps in drebin dataset are the
exact copies of others. These duplicate apps might affect the actual
performance of the machine learning based malware detection mechanisms. In the
next section, we investigate this with the help of API calls and permissions
based classifiers.

Figure 4: Number of Clusters$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$1$$100$$600$$1{,}100$$1{,}600$$2{,}100$$2{,}600$$3{,}000$$\epsilon$$Clusters$ TABLE II: Distribution of Semantically Dissimilar Apps Dataset | $\epsilon$ | Number of Malware Samples | Number of Goodware Samples
---|---|---|---
Dataset 1 | 0 | 2642 | 4655
Dataset 2 | 0.1 | 1650 | 3989
Dataset 3 | 0.2 | 1305 | 3610

##  V Evaluation of Drebin Malware Samples with and without Semantically
Similar Apps

In this section, we make a study about the impact of semantically similar
application in machine learning based malware detection mechanisms. For
analyzing false positives, we collected 5500 goodware samples from Androzoo
dataset [28]. In order to avoid the bias in the API levels, we selected the
goodware samples ranging from 2010 to 2012 (same period/API level as that of
drebin dataset). The overall evaluation dataset consisting of malware and
goodware samples. From this dataset, we filtered out the semantically similar
goodware and malware apps and constructed datasets with semantically
dissimilar samples. The statistics of apps in the datasets are given in Table
II. All the datasets are evaluated in machine learning algorithms trained with
different kinds of features. The used features are given as follows:

  1. 1.

API calls;

  2. 2.

Permissions.

TABLE III: Selected Permissions for Malware Detection SI.No | Permissions | SI.No | Permissions
---|---|---|---
1 | READ_PHONE_STATE | 2 | WRITE_CONTACTS
3 | CALL_PHONE | 4 | READ_CONTACTS
5 | INTERNET | 6 | SEND_SMS
7 | DISABLE_KEYGUARD | 8 | PROCESS_OUTGOING_CALLS
9 | RECEIVE_BOOT_COMPLETED | 10 | READ_SMS
11 | FACTORY_TEST | 12 | DEVICE_POWER
13 | HARDWARE_TEST | 14 | CHANGE_WIFI_STATE
15 | GET_ACCOUNTS | 16 | READ_HISTORY_BOOKMARKS
17 | WRITE_APN_SETTINGS | 18 | MODIFY_PHONE_STATE
19 | WRITE_HISTORY_BOOKMARKS | 20 | ACCESS_LOCATION
21 | EXPAND_STATUS_BAR | 22 | WRITE_EXTERNAL_STORAGE
23 | RECEIVE_SMS | 24 | WRITE_SMS
25 | ACCESS_WIFI_STATE | 26 | MODIFY_AUDIO_SETTINGS
27 | ACCESS_NETWORK_STATE | 28 | WRITE_SETTINGS
29 | READ_EXTERNAL_STORAGE | 30 | ACCESS_MOCK_LOCATION
31 | USE_CREDENTIALS | 32 | HARDWARE_TEST
33 | VIBRATE | 34 | READ_LOGS
35 | CHANGE_NETWORK_STATE | 36 | ACCESS_GPS
37 | WAKE_LOCK | 38 | ACCESS_COURSE_UPDATES
39 | ACCESS_LOCATION_EXTRA_COMMANDS | 40 | ACCESS_FINE_LOCATION
41 | GET_TASKS | 42 | RESTART_PACKAGES
43 | MOUNT_UNMOUNT_FILESYSTEMS | 44 | INSTALL_PACKAGES
45 | KILL _BACKGROUND_PROCESS |  |
TABLE IV: K-Fold Cross Validation Results in Permission Classifier Dataset | TPR | FPR | Accuracy | Precision | F1Score
---|---|---|---|---|---
Overall Dataset | 0.941 | 0.050 | 0.945 | 0.945 | 0.945
Dataset 1 | 0.900 | 0.051 | 0.931 | 0.931 | 0.931
Dataset 2 | 0.855 | 0.054 | 0.920 | 0.920 | 0.920
Dataset 3 | 0.826 | 0.051 | 0.917 | 0.917 | 0.917

###  V-A Permission Analysis

In this section, we re-implement permission based malware detection mechanism
in our datasets (with and without semantically similar apps) for analyzing the
impact of semantically similar in dataset. Here, we used the key permission
based features mentioned in our previous work [29]. The list of permission
based features are given in Table III. We extract the permission based
features of malware and goodware apps in the dataset and a Comma Separated
Value (CSV) file is constructed. This CSV file is supplied to Weka framework
[30] and tested in machine learning classifiers by employing 10 fold cross
validation technique. We obtained a high accuracy in random forest classifier
[31]. From Table IV, we can see that the performance of the classifiers
dropped very slightly in the datasets of semantically dissimilar apps. Random
forest algorithm works on the basis of information gain values [32].
Therefore, we have given the information gain values of permission based
features in our Dataset is given in Table V. From Table V, we can see that the
information gain values can be slightly affected by the semantically similar
apps in the datasets.

TABLE V: Changes in Information Gain Values of Permissions in the Datasets Permissions | Overall Dataset | Dataset1 | Dataset2 | Dataset3
---|---|---|---|---
READ_PHONE_STATE | 0.379 | 0.334 | 0.283 | 0.264
SEND_SMS | 0.257 | 0.112 | 0.121 | 0.126
RECEIVE_BOOT_COMPLETED | 0.189 | 0.193 | 0.143 | 0.122
READ_SMS | 0.175 | 0.127 | 0.115 | 0.109
RECEIVE_SMS | 0.160 | 0.068 | 0.088 | 0.096
ACCESS_WIFI_STATE | 0.138 | 0.209 | 0.169 | 0.142
WRITE_EXTERNAL_STORAGE | 0.120 | 0.114 | 0.108 | 0.101
WRITE_SMS | 0.096 | 0.083 | 0.074 | 0.070
WAKE_LOCK | 0.081 | 0.073 | 0.057 | 0.049
INTERNET | 0.079 | 0.060 | 0.052 | 0.053

###  V-B API Call Analysis

In this section, we re-implement API call based malware detection mechanism in
our datasets for analyzing the impact of semantically similar in dataset.
Here, we reused the key API call based features mentioned in our previous work
[29]. The list of API call based features are given in Table VI. We extract
the API call based features of malware and goodware apps in the dataset and a
Comma Separated Value (CSV) file is constructed. This CSV file is supplied to
Weka framework and tested in machine learning classifiers by employing 10 fold
cross validation technique. We obtained a high accuracy in random forest
classifier. From Table VII, we can see that the performance of the classifiers
dropped very slightly in the datasets of semantically dissimilar apps. Random
forest algorithm works on the basis of information gain values. Therefore, we
have given the information gain values of API Call based features in our
Dataset is given in Table VIII. From Table VIII, we can see that the
information gain values can be slightly affected by the semantically similar
apps in the datasets.

TABLE VI: Selected API Calls for Malware Detection SI.No | API Calls | SI.No | API Calls
---|---|---|---
1 | getNetworkType | 18 | getDisplayMessageBody
2 | getNetworkOperator | 19 | getPackageInfo
3 | loadClass | 20 | getLastKnownLocation
4 | getMessage | 21 | getAppPackageName
5 | getMethod | 22 | getCookies
6 | getClassLoader | 23 | isProviderEnabled
7 | GetLongitude | 24 | getSimOperatorName
8 | GetLatitude | 25 | getDeviceId
9 | createFromPdu | 26 | getCertStatus
10 | getInputStream | 27 | getSimSerialNumber
11 | getOutputStream | 28 | getLine1Number
12 | getWifiState | 29 | killProcess
13 | abortBroadCast | 30 | exec
14 | RequestFocus | 31 | getAppPackageName
15 | getSubscriberId | 32 | setSerialNumber
16 | getDisplayOriginatingAddress | 33 | getSessions
17 | sendTextMessage | 34 | getCredential
TABLE VII: K-Fold Cross Validation Results in API Call Classifier Dataset | TPR | FPR | Accuracy | Precision | F1Score
---|---|---|---|---|---
Overall Dataset | 0.954 | 0.046 | 0.957 | 0.957 | 0.957
Dataset 1 | 0.91 | 0.037 | 0.944 | 0.944 | 0.944
Dataset 2 | 0.856 | 0.044 | 0.929 | 0.929 | 0.928
Dataset 3 | 0.831 | 0.044 | 0.925 | 0.925 | 0.924
TABLE VIII: Changes in Information Gain Values of API Calls in the Datasets API Call | Overall Dataset | Dataset1 | Dataset2 | Dataset3
---|---|---|---|---
getDeviceId | 0.205 | 0.301 | 0.249 | 0.229
sendTextMessage | 0.175 | 0.110 | 0.106 | 0.108
getLine1Number | 0.164 | 0.224 | 0.194 | 0.180
getNetworkOperator | 0.157 | 0.128 | 0.087 | 0.069
getSubscriberId | 0.154 | 0.199 | 0.228 | 0.237
createFromPdu | 0.082 | 0.157 | 0.062 | 0.065
abortBroadcast | 0.081 | 0.047 | 0.055 | 0.059
getSimOperatorName | 0.068 | 0.093 | 0.055 | 0.045
getSimSerialNumber | 0.065 | 0.114 | 0.128 | 0.122
getCellLocation | 0.049 | 0.076 | 0.064 | 0.059
API Calls(DS1)API Calls(DS2)API
Calls(DS3)Permissions(DS1)Permissions(DS2)Permissions(DS3)$0.9$$0.91$$0.92$$0.93$$0.94$AccuracyUnbalancedBalanced
Figure 5: Accuracy of Balanced Datasets without Semantically Similar Apps

##  VI Testing the Performance in Balanced Datasets

In this section, we evaluate the performance of API call and permission based
classifiers in balanced datasets. From Table II, we can see that the number of
unique apps in goodware dataset is higher than that of malware dataset. That
is, the distribution of apps in the classifier is not unique and class
imbalance problem may occur in evaluation. Hence, it is required to evaluate
the performances in balanced datasets before confirming our findings. From the
goodware datasets (dataset 1 , dataset 2 and dataset 3), we removed some
random goodware apps for balancing the dataset. After balancing the datasets,
we evaluated the performances in API call and permission based classifiers.
The performance of API call and permission based classifiers in both balanced
and unbalanced datasets are given in Fig 8. From Fig 8, we can see that the
performance of the classifier is dropped after balancing the dataset.

##  VII Overrated Performance in Holdout Evaluation

In this section, we illustrate the performance bias due to the semantically
similar apps in test dataset. In ML based Android malware detection, a malware
researcher randomly divides the dataset samples to train and test set for
evaluation. Most of this time, he unaware about the duplicate copies in the
dataset. The rate of duplicate samples in the test dataset may significantly
affect the performance of the model. So, it is very difficult to generalize
the model in accurately detecting the diverse malware apps. Here, we
illustrate this phenomenon in API call based classifier.

We trained our API call and permission based classifier with the features
diverse malware and goodware samples and tested with more duplicate malware
and goodware samples. Further, the test dataset is constructed with more
semantically similar apps of more malware samples those have more malicious
features and more semantically similar apps of more goodware samples those
have very few malicious features. Here,we followed thumb rule (80:20) for
train-test split. Also, we shuffled the train and test set samples until
obtaining the accuracy of 1. The performance metrics are given in Table IX.
From the Table IX, it is clear that it is possible for a researcher to report
his desired performance by shuffling the datasets in holdout evaluation. So,
it has been advised to use our clustering algorithm to remove semantically
similar apps from the dataset before holdout evaluation.

TABLE IX: Holdout Evaluation Results in API Call and Permission Classifier Classifier | TPR | FPR | Accuracy | Precision | F1Score
---|---|---|---|---|---
API Call Classifier | 1 | 0 | 1 | 1 | 1
Permission Classifier | 1 | 0 | 1 | 1 | 1

##  VIII Discussion and Conclusions

In this work, we proposed a clustering mechanism to assess the impact of
semantically similar apps in Android malware dataset. We found that, the
presence of semantically similar apps especially duplicate apps those
influence the performance of ML models in hold out evaluation. So, it has been
advised to filter out all semantically similar apps before performing the
holdout evaluation.

Our clustering algorithm have some limitations which affects the clustering
process. In opcode injection attack, it is possible for an adversary to inject
irrelevant opcodes in between the opcode subsequences of an application [33].
In such cases, the application has not become the part of any cluster. In
future, we will explore some other additional features such as API calls and
permission sequences for efficient clustering these apps.

In our experiments, the decompilation errors has occurred in some
applications. Due to this decompilation errors, we cannot cluster these apps.
In future, we will investigate the reason behind this decompilation errors and
design some new tools to decompile these apps.

## Acknowledgment

## References

  * [1] X. Sun, Y. Zhongyang, Z. Xin, B. Mao, and L. Xie, “Detecting code reuse in android applications using component-based control flow graph,” in IFIP international information security conference, pp. 142–155, Springer, 2014.
  * [2] T. McDonnell, B. Ray, and M. Kim, “An empirical study of api stability and adoption in the android ecosystem,” in 2013 IEEE International Conference on Software Maintenance, pp. 70–79, IEEE, 2013.
  * [3] J. Sahs and L. Khan, “A machine learning approach to android malware detection,” in 2012 European Intelligence and Security Informatics Conference, pp. 141–147, IEEE, 2012.
  * [4] D. Arp, M. Spreitzenbarth, M. Hubner, H. Gascon, K. Rieck, and C. Siemens, “Drebin: Effective and explainable detection of android malware in your pocket.,” in Ndss, vol. 14, pp. 23–26, 2014.
  * [5] N. Marastoni, A. Continella, D. Quarta, S. Zanero, and M. D. Preda, “Groupdroid: Automatically grouping mobile malware by extracting code similarities,” in Proceedings of the 7th Software Security, Protection, and Reverse Engineering/Software Security and Protection Workshop, pp. 1–12, 2017.
  * [6] S. Hanna, L. Huang, E. Wu, S. Li, C. Chen, and D. Song, “Juxtapp: A scalable system for detecting code reuse among android applications,” in International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment, pp. 62–81, Springer, 2012.
  * [7] J. Crussell, C. Gibler, and H. Chen, “Attack of the clones: Detecting cloned applications on android markets,” in European Symposium on Research in Computer Security, pp. 37–54, Springer, 2012.
  * [8] K. Liu, S. Xu, G. Xu, M. Zhang, D. Sun, and H. Liu, “A review of android malware detection approaches based on machine learning,” IEEE Access, vol. 8, pp. 124579–124607, 2020.
  * [9] L. Cen, C. S. Gates, L. Si, and N. Li, “A probabilistic discriminative model for android malware detection with decompiled source code,” IEEE Transactions on Dependable and Secure Computing, vol. 12, no. 4, pp. 400–412, 2014.
  * [10] P. Rovelli and Ý. Vigfússon, “Pmds: Permission-based malware detection system,” in International conference on information systems security, pp. 338–357, Springer, 2014.
  * [11] S. Arzt, S. Rasthofer, C. Fritz, E. Bodden, A. Bartel, J. Klein, Y. Le Traon, D. Octeau, and P. McDaniel, “Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps,” Acm Sigplan Notices, vol. 49, no. 6, pp. 259–269, 2014.
  * [12] K. Xu, Y. Li, and R. H. Deng, “Iccdetector: Icc-based malware detection on android,” IEEE Transactions on Information Forensics and Security, vol. 11, no. 6, pp. 1252–1264, 2016.
  * [13] G. Canfora, A. De Lorenzo, E. Medvet, F. Mercaldo, and C. A. Visaggio, “Effectiveness of opcode ngrams for detection of multi family android malware,” in 2015 10th International Conference on Availability, Reliability and Security, pp. 333–340, IEEE, 2015.
  * [14] T. Kim, B. Kang, and E. G. Im, “Runtime detection framework for android malware,” Mobile Information Systems, vol. 2018, 2018.
  * [15] J. Milosevic, M. Malek, and A. Ferrante, “A friend or a foe? detecting malware using memory and cpu features.,” in SECRYPT, pp. 73–84, 2016.
  * [16] G. Canfora, E. Medvet, F. Mercaldo, and C. A. Visaggio, “Detecting android malware using sequences of system calls,” in Proceedings of the 3rd International Workshop on Software Development Lifecycle for Mobile, pp. 13–20, 2015.
  * [17] M. Zaman, T. Siddiqui, M. R. Amin, and M. S. Hossain, “Malware detection in android by network traffic analysis,” in 2015 international conference on networking systems and security (NSysS), pp. 1–5, IEEE, 2015.
  * [18] S. Brahler, “Analysis of the android architecture,” Karlsruhe institute for technology, vol. 7, no. 8, 2010.
  * [19] H.-S. Oh, B.-J. Kim, H.-K. Choi, and S.-M. Moon, “Evaluation of android dalvik virtual machine,” in Proceedings of the 10th international workshop on java technologies for real-time and embedded systems, pp. 115–124, 2012.
  * [20] P. O. Fora, “Beginners guide to reverse engineering android apps,” in RSA Conference, pp. 21–22, 2014.
  * [21] T. Oguchi, “Geomorphological debates in japan related to surface processes, tectonics, climate, research principles, and international geomorphology,” Geomorphology, vol. 366, p. 106805, 2020.
  * [22] Y. Otsuka, “The faunal character of the japanese pleistocene marine mollusca, as evidence of climate having become colder during the pleistocene in japan,” Biogeograph Soc Japan, vol. 6, no. 16, pp. 165–170, 1936.
  * [23] O. Akira, “Zoogeographical studies on the soleoid fishes found in japan and its neighbouring regions–ii,” Bull Jap Soc Sci Fish, vol. 22, no. 9, pp. 526–530, 1957.
  * [24] R. Xu and D. Wunsch, “Survey of clustering algorithms,” IEEE Transactions on neural networks, vol. 16, no. 3, pp. 645–678, 2005.
  * [25] S. Vassilvitskii and D. Arthur, “k-means++: The advantages of careful seeding,” in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1027–1035, 2006.
  * [26] N. McLaughlin, J. Martinez del Rincon, B. Kang, S. Yerima, P. Miller, S. Sezer, Y. Safaei, E. Trickel, Z. Zhao, A. Doupé, et al., “Deep android malware detection,” in Proceedings of the seventh ACM on conference on data and application security and privacy, pp. 301–308, 2017.
  * [27] H. Rawal and C. Parekh, “Android internal analysis of apk by droid_safe & apk tool.,” International Journal of Advanced Research in Computer Science, vol. 8, no. 5, 2017.
  * [28] K. Allix, T. F. Bissyandé, J. Klein, and Y. Le Traon, “Androzoo: Collecting millions of android apps for the research community,” in 2016 IEEE/ACM 13th Working Conference on Mining Software Repositories (MSR), pp. 468–471, IEEE, 2016.
  * [29] R. Surendran, T. Thomas, and S. Emmanuel, “A tan based hybrid model for android malware detection,” Journal of Information Security and Applications, vol. 54, p. 102483, 2020.
  * [30] M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten, “The weka data mining software: an update,” ACM SIGKDD explorations newsletter, vol. 11, no. 1, pp. 10–18, 2009.
  * [31] A. Liaw, M. Wiener, et al., “Classification and regression by randomforest,” R news, vol. 2, no. 3, pp. 18–22, 2002.
  * [32] J. T. Kent, “Information gain and a general measure of correlation,” Biometrika, vol. 70, no. 1, pp. 163–173, 1983.
  * [33] X. Zhang, J. Wang, M. Sun, and Y. Feng, “Andropgan: An opcode gan for android malware obfuscations,” in International Conference on Machine Learning for Cyber Security, pp. 12–25, Springer, 2020.


# On Metric Learning for Audio-Text Cross-Modal Retrieval

###### Abstract

Audio-text retrieval aims at retrieving a target audio clip or caption from a
pool of candidates given a query in another modality. Solving such cross-modal
retrieval task is challenging because it not only requires learning robust
feature representations for both modalities, but also requires capturing the
fine-grained alignment between these two modalities. Existing cross-modal
retrieval models are mostly optimized by metric learning objectives as both of
them attempt to map data to an embedding space, where similar data are close
together and dissimilar data are far apart. Unlike other cross-modal retrieval
tasks such as image-text and video-text retrievals, audio-text retrieval is
still an unexplored task. In this work, we aim to study the impact of
different metric learning objectives on the audio-text retrieval task. We
present an extensive evaluation of popular metric learning objectives on the
AudioCaps and Clotho datasets. We demonstrate that NT-Xent loss adapted from
self-supervised learning shows stable performance across different datasets
and training settings, and outperforms the popular triplet-based losses. Our
code is available at https://github.com/XinhaoMei/audio-text_retrieval.

Index Terms: metric learning, audio retrieval, text-based retrieval, cross-
modal task

##  1 Introduction

Given an audio clip or a caption as a query, audio-text retrieval aims at
retrieving a paired item from a pool of candidates in another modality. This
cross-modal retrieval task is challenging as it requires not only learning
robust feature representations for both acoustic and textual modalities but
also capturing fine-grained interaction between the learned acoustic and
textual features and aligning them in a shared embedding space. Audio-text
retrieval can be potentially applied to applications such as film, audio book
production and web search.

Cross-modal retrieval tasks (e.g. image-text retrieval and video-text
retrieval) have received extensive attention in recent years and have made
great progress [1, 2, 3, 4, 5, 6]. However, little attention has been paid to
audio-text retrieval in the literature. One reason might be the lack of
appropriate datasets, thus early works just focused on tag-based audio
retrieval, where the queries were words not sentences. Chechik et al. [7]
proposed a tag-based audio retrieval system using traditional machine learning
techniques (e.g. support vector machines and Gaussian mixture models). Ikawa
et al. [8] investigated searching sounds using onomatopoeic words. Elizalde et
al. [9] employed a siamese network to align audio and textual features to a
joint embedding space. Although these tag-based audio retrieval works show
reasonable performance, they are constrained in the query format. Retrieving
audio clips using free-form language (sentences) is more natural for humans.

With the fast development of audio captioning in recent three years [10, 11,
12, 13], publicly available audio captioning datasets are released [14, 15],
which are naturally suited for the free-form language-based audio-text
retrieval task. Koepke et al. [16] first established the benchmarks for free-
form language-based audio retrieval, where they adapted models from video
retrieval and made use of pre-trained models to solve the data scarcity
problem. Since both the audio and text (captions) are sequence data, free-form
language-based audio-text retrieval is more challenging than tag-based audio
retrieval and is the focus of this paper. We use the term audio-text and
audio-caption interchangeably in this paper.

Similar to other cross-modal retrieval models [1], the audio-text retrieval
models can be built with two sub-networks, namely, an audio encoder and a text
encoder. The objectives of these two encoders are to map the audios and texts
into a joint embedding space, where the semantically similar embeddings are
close to each other and the dissimilar items are far away. We refer to the
embeddings as Acoustic Semantic Embeddings (ASE) as they are learned via
jointly modeling the audio and language modalities. The training objective of
cross-modal retrieval models is consistent with that of metric learning [17].
To this end, metric learning has been a popular choice for the optimization of
the cross-modal retrieval models. Numerous metric learning objectives have
been introduced for various tasks such as face identification [18], speaker
recognition [19], and retrieval [1, 2], however, there is no clear argument
which one is the most suited since they may work well on specific tasks or
data but may not generalize well to other tasks [20]. In this work, we aim to
study and compare the impact of different metric learning objectives for the
free-form language-based audio-text retrieval task in a constant training
setting.

We focus on triplet loss and its variants, as they have demonstrated promising
performance and are popularly employed [18]. In a triplet setting for audio-
text retrieval, an audio clip and its corresponding caption are regarded as an
anchor and a positive example, respectively, while other unpaired captions are
regarded as negatives. The hinge-based triplet ranking loss sums over all
negative samples within a mini-batch (thus we refer to it as triplet-sum).
Faghri et al. [1] argued that hard negatives should be emphasised as other
easy negatives may dominate the loss and create local minimal, thus they
proposed a triplet ranking loss with hard negative mining (we refer to it as
triplet-max) which focuses only on the hardest negative within a mini-batch.
Wei et al. [21] further proposed a universal weighting framework for cross-
modal retrieval, where the pairs are weighted based on their similarity scores
(we refer to it as triplet-weighted). In addition to the triplet-based losses,
we further adapt a contrastive loss used in self-supervised learning here for
supervised cross-modal retrieval, that is, normalized temperature-scaled cross
entropy loss (NT-Xent) [22]. The NT-Xent loss is based on softmax and aims to
identify the positive pairs within a mini-batch.

In summary, we first establish a baseline using pre-trained models to learn
the acoustic semantic embeddings, then we present an extensive evaluation of
the popular metric learning objectives described above on our baseline in a
constant training setting. Against popular belief [1, 20], we demonstrate that
triplet losses with hard negative mining are sensitive to the training
settings and may be hard to converge, the NT-Xent loss shows stable
performance with respect to different datasets and training settings and
outperforms the triplet-based losses.

##  2 Audio-Text Retrieval with Metric Learning

In this section, we first formulate the audio-text retrieval problem and
introduce the baseline model, then the metric learning objectives (loss
functions) we evaluated are introduced.

###  2.1 Problem formulation

Let $D=\\{(a_{i},t_{i})\\}_{i=1}^{N}$ be an audio captioning dataset of $N$
examples, where $a_{i}$ is an audio clip and $t_{i}$ is the paired caption.
Therefore, $(a_{i},t_{i})$ is regarded as a positive pair while
$(a_{i},t_{j,j\neq i})$ is a negative pair. One audio clip could have multiple
paired captions, we just consider one here for simplicity. The audio-text
retrieval models usually consist of an audio encoder $f$ and a text encoder
$g$, which project the audio clip and text into a shared embedding space,
respectively. For an audio-caption pair $(a_{i},t_{j})$, the similarity of the
audio and caption can be measured by cosine similarity of their embeddings:

$s_{ij}=\frac{f(a_{i})\cdot g(t_{j})}{||f(a_{i})||_{2}||g(t_{j})||_{2}}.$ (1)

The two encoders are trained to make the similarity score of positive pairs
$s_{ii}$ higher than that of negative pairs $s_{ij}$.

###  2.2 Model

The data available in the audio captioning datasets is limited, and this data
scarcity problem usually limits the performance of the model in learning
robust feature representations. Transfer learning has been adopted as a
standard recipe to alleviate the data scarcity problem and has shown promising
performance in audio captioning task [23]. Therefore, pre-trained models are
employed here.

Audio Encoder Pre-trained audio neural networks (PANNs) [24] are pre-trained
on AudioSet with an audio tagging task, which are shown to provide robust
audio representations and perform well on a wide range of audio-related tasks.
The ResNet-38 in PANNs is employed as the audio encoder, where the last two
linear layers are discarded. An average and max pooling layer is applied to
aggregate along the frequency dimension on the feature map output by the last
convolutional block. A multilayer perceptron (MLP) block is used to project
the audio features into a shared embedding space, which consists of two linear
layers with a ReLU [25] activation layer between them.

Text Encoder Numerous large-scale per-trained language models have been
published in recent year, which show powerful capability to model the language
and produce contextual-aware embeddings. BERT [26], which stands for
Bidirectional Encoder Representations from Transformers, obtains state-of-the-
art results on a wide variety of Natural Language Processing (NLP) tasks. The
pre-trained BERT is employed as the text encoder here. A “<CLS>” token is
appended at the start of each sentence and used as the final sentence
representation. A MLP block is also applied to project the sentence
representation into the shared embedding space.

###  2.3 Loss functions

During training, we sample a mini-batch of audio-caption pairs
$\\{a_{i},t_{i}\\}_{i=1}^{B}$ where $B$ is the batch size. Triplet-based loss
functions are based on the concept of triplet, which is made up by an anchor,
a positive (paired candidate in another modality) and a negative (unpaired
candidate in another modality). The anchor with its positive is a positive
pair and the anchor with its negative is a negative pair as we defined above.

Triplet-sum For each query, the triplet-sum loss aims to maximize the
similarity score of its positive pair while minimizing the similarity scores
to all other negatives within a mini-batch, thus it can be formulated as

$\mathcal{L}=\frac{1}{B}\sum_{i=1}^{B}\sum_{j\neq
i}[m+s_{ij}-s_{ii}]_{+}+[m+s_{ji}-s_{ii}]_{+},$ (2)

where $[x]_{+}=\max(0,x)$ and $m$ is a distance margin. Since audio-text
retrieval is a bidirectional retrieval task (audio-to-text and text-to-audio),
the loss has two terms, the first term sums over all negative captions given a
query audio clip while the second term sums over all negative audio clips
given a query caption. If the similarity of the positive pair is larger than
that of any negatives in the mini-batch by the margin $m$, the loss will be
zero.

Triplet-max Triplet-sum loss sums over all negatives for each query within a
mini-batch, Faghri et al. [1] argued that the easy negatives may dominate the
loss and make it stuck into local minimal, thus, hard negatives should be
emphasized. They proposed the triplet-max loss that focuses on the hardest
negatives during training, which can be formulated as:

$\mathcal{L}=\frac{1}{B}\sum_{i=1}^{B}\max_{j\neq
i}{[m+s_{ij}-s_{ii}]_{+}}+\max_{j\neq i}{[m+s_{ji}-s_{ii}]_{+}}.$ (3)

For each query, it aims to maximize the similarity score of its positive pair
while just minimizing the similarity score to its hardest negative within a
mini-batch, that is, the negative closest to the query in the embedding space.
In this way, the easy negatives won’t violate the loss and the hardest
negative takes all the gradients.

Triplet-weighted Both the positive and negative pairs are treated equally in
the triplet-sum and triplet-max losses. Wei et al. [21] further introduced a
universal function $G(\cdot)$ to weight the pairs based on their similarity
scores. Specifically, the weighting function is defined as a polynomial
function. For a positive pair $(a_{i},t_{i})$, the positive weight function
$G_{\rm{pos}}$ is defined as:

$G_{\rm{pos}}=a_{p}s_{ii}^{p}+a_{p-1}s_{ii}^{p-1}+\cdots+a_{1}s_{ii}^{1}+a_{0},$
(4)

where $p$ is the order of the polynomial function and $\\{a_{i}\\}_{i=0}^{p}$
are the hyper-parameters. The negative weight function $G_{\rm{neg}}$ can be
formulated as:

$G_{\rm{neg}}=b_{q}s_{ij}^{q}+b_{q-1}s_{ij}^{q-1}+\cdots+b_{1}s_{ij}^{1}+b_{0},$
(5)

where $\\{b_{i}\\}_{i=0}^{q}$ are the hyper-parameters and $q$ is the order.
If the similarity score of the positive pair $(a_{i},t_{i})$ increases, the
positive weight value will decrease. In contrast, for a negative pair
$(a_{i},t_{j})$, the negative weight value increases if the similarity score
of the negative pair increases.

Table 1: Results of the experiments. * indicates the learning rate is $5\text{\times}{10}^{-5}$ otherwise $1\text{\times}{10}^{-4}$. Dataset | Fine-tune | Objective | Text-to-Audio | Audio-to-Text
---|---|---|---|---
R$@1$ | R$@5$ | R$@10$ | R$@1$ | R$@5$ | R$@10$
AudioCaps | No | Triplet-sum | $17.2_{\pm 0.5}$ | $47.6_{\pm 0.2}$ | $64.3_{\pm 0.1}$ | $19.3_{\pm 1.5}$ | $51.4_{\pm 0.8}$ | $67.2_{\pm 0.7}$
Triplet-max | $19.9_{\pm 0.2}$ | $51.6_{\pm 0.3}$ | $67.4_{\pm 0.3}$ | $21.2_{\pm 0.9}$ | $54.9_{\pm 1.4}$ | $70.2_{\pm 1.0}$
Triplet-weighted | $19.9_{\pm 0.2}$ | $52.1_{\pm 0.7}$ | $67.6_{\pm 0.6}$ | $21.9_{\pm 0.8}$ | $56.3_{\pm 0.3}$ | $71.5_{\pm 0.4}$
NT-Xent | $19.2_{\pm 0.4}$ | $51.1_{\pm 0.2}$ | $66.6_{\pm 0.2}$ | $21.3_{\pm 0.5}$ | $53.6_{\pm 0.7}$ | $69.8_{\pm 0.5}$
Yes | Triplet-sum | $32.2_{\pm 0.3}$ | $68.2_{\pm 0.6}$ | $81.6_{\pm 0.5}$ | $36.1_{\pm 1.2}$ | $69.2_{\pm 1.3}$ | $81.4_{\pm 1.7}$
Triplet-max | $32.7_{\pm 0.3}$ | $68.3_{\pm 0.8}$ | $81.6_{\pm 0.5}$ | $38.7_{\pm 1.0}$ | $70.6_{\pm 0.7}$ | $82.2_{\pm 0.8}$
Triplet-weighted | $32.6_{\pm 0.6}$ | $67.7_{\pm 0.7}$ | $81.0_{\pm 0.8}$ | $39.6_{\pm 1.1}$ | $72.0_{\pm 2.2}$ | $82.2_{\pm 1.4}$
NT-Xent | $33.9_{\pm 0.4}$ | $69.7_{\pm 0.2}$ | $82.6_{\pm 0.3}$ | $39.4_{\pm 1.0}$ | $72.0_{\pm 1.0}$ | $83.9_{\pm 0.6}$
Clotho | No | Triplet-sum | $7.0_{\pm 0.2}$ | $23.0_{\pm 0.3}$ | $34.8_{\pm 0.5}$ | $8.3_{\pm 0.3}$ | $25.4_{\pm 0.8}$ | $36.7_{\pm 0.5}$
Triplet-max | $7.9_{\pm 0.2}$ | $23.6_{\pm 0.4}$ | $34.2_{\pm 0.5}$ | $8.8_{\pm 1.0}$ | $25.7_{\pm 1.0}$ | $36.3_{\pm 0.8}$
Triplet-weighted* | $7.2_{\pm 0.2}$ | $22.1_{\pm 0.3}$ | $33.0_{\pm 0.3}$ | $7.5_{\pm 0.4}$ | $23.2_{\pm 0.1}$ | $33.3_{\pm 0.3}$
NT-Xent | $8.0_{\pm 0.2}$ | $25.3_{\pm 0.1}$ | $36.9_{\pm 0.3}$ | $9.2_{\pm 0.7}$ | $27.9_{\pm 0.5}$ | $39.0_{\pm 0.7}$
Yes | Triplet-sum | $14.2_{\pm 0.5}$ | $36.6_{\pm 0.5}$ | $49.3_{\pm 0.7}$ | $16.1_{\pm 0.7}$ | $37.5_{\pm 1.2}$ | $50.7_{\pm 1.0}$
Triplet-max* | $14.2_{\pm 0.9}$ | $36.5_{\pm 1.2}$ | $49.0_{\pm 0.4}$ | $15.8_{\pm 0.4}$ | $36.4_{\pm 1.6}$ | $49.6_{\pm 2.0}$
Triplet-weighted* | $14.2_{\pm 0.4}$ | $36.6_{\pm 0.5}$ | $49.7_{\pm 0.3}$ | $16.9_{\pm 0.4}$ | $38.1_{\pm 0.2}$ | $51.4_{\pm 0.2}$
NT-Xent | $14.4_{\pm 0.4}$ | $36.6_{\pm 0.2}$ | $49.9_{\pm 0.2}$ | $16.2_{\pm 0.7}$ | $37.5_{\pm 0.9}$ | $50.2_{\pm 0.7}$

Let $N_{a_{i}}=\\{s_{ij,j\neq i}\\}$ and $N_{t_{j}}=\\{s_{ji,i\neq j}\\}$ be
the similarity scores for all negative pairs of an audio sample $a_{i}$ and a
text sample $t_{j}$ respectively. The loss can be formulated as:

$\begin{split}\mathcal{L}&=\frac{1}{B}\sum_{i=1}^{B}[\sum_{p=0}^{P}a_{p}s_{ii}^{p}+\sum_{q=0}^{Q}b_{q}\max\\{N_{a_{i}}^{q}\\}]_{+}\\\
&+\frac{1}{B}\sum_{i=1}^{B}[\sum_{p=0}^{P}a_{p}s_{ii}^{p}+\sum_{q=0}^{Q}b_{q}\max\\{N_{t_{i}}^{q}\\}]_{+},\end{split}$
(6)

where $P$ and $Q$ are the highest power of positive and negative pairs,
respectively. The $\max$ term in the equation will select the hardest negative
pair, thus the loss is referred to as the maximum polynomial loss. They also
proposed another average polynomial loss that will first select informative
negative pairs based on a mining policy and average the similarity scores of
the selected pairs. We just employ the maximum polynomial loss here as it
performs better than the average one in [21].

NT-Xent NT-Xent is a contrastive loss based on softmax, proposed by Chen et
al. [22] to learn visual representations via self-supervised learning. We
adapt it here for the supervised cross-modal retrieval task, as follows:

$\begin{split}\mathcal{L}=-\frac{1}{B}&\left(\sum_{i=1}^{B}\log\frac{\exp({s_{ii}/\tau})}{\sum_{j=1}^{B}\exp{({s_{ij}/\tau)}}}+\right.\\\
&\left.\sum_{i=1}^{B}\log\frac{\exp({s_{ii}/\tau})}{\sum_{j=1}^{B}\exp{({s_{ji}/\tau)}}}\right),\end{split}$
(7)

where $\tau$ is a temperature hyper-parameter. It aims to maximize the
similarity of the positive pair with respect to all negative pairs within a
mini-batch, and the final loss is also computed in a bidirectional manner.

##  3 Experiments

###  3.1 Datasets

We focus on free-form language-based audio-text retrieval, thus audio
captioning datasets are naturally employed, in which each audio clip is
annotated by humans using natural sentences. Extensive experiments are carried
out on AudioCaps [14] and Clotho [15] datasets, respectively.

AudioCaps AudioCaps is the largest audio captioning dataset with around $50$k
audio clips. All the audio clips are $10$-second long and are sourced from
AudioSet [27], the largest dataset for audio tagging. In our downloaded
version, the training set contains $49\,274$ audio clips and each of them has
one corresponding human-annotated caption, the validation and test set contain
$494$ and $957$ audio clips, respectively, and each of them has five human-
annotated captions.

Clotho Clotho is an audio captioning dataset whose audio clips are collected
from the Freesound111https://freesound.org/ archive. The length of the audio
clips ranges uniformly from $15$ to $30$ seconds. Clotho v2 is used here.
There are $3839$ audio clips in the training set and $1045$ audio clips in the
validation and test sets respectively. All the audio clips have five diverse
human-annotated captions of eight to $20$ words in length.

Table 2: Experimental results with different batch sizes on AudioCaps dataset. The pre-trained encoders are not fine-tuned. Batch size | Objective | Text-to-Audio | Audio-to-Text
---|---|---|---
R$@1$ | R$@5$ | R$@10$ | R$@1$ | R$@5$ | R$@10$
32 | Triplet-sum | $17.2_{\pm 0.5}$ | $47.6_{\pm 0.2}$ | $64.3_{\pm 0.1}$ | $19.3_{\pm 1.5}$ | $51.4_{\pm 0.8}$ | $67.2_{\pm 0.7}$
Triplet-max | $19.9_{\pm 0.2}$ | $51.6_{\pm 0.3}$ | $67.4_{\pm 0.3}$ | $21.2_{\pm 0.9}$ | $54.9_{\pm 1.4}$ | $70.2_{\pm 1.0}$
Triplet-weighted | $19.9_{\pm 0.2}$ | $52.1_{\pm 0.7}$ | $67.6_{\pm 0.6}$ | $21.9_{\pm 0.8}$ | $56.3_{\pm 0.3}$ | $71.5_{\pm 0.4}$
NT-Xent | $19.2_{\pm 0.4}$ | $51.1_{\pm 0.2}$ | $66.6_{\pm 0.2}$ | $21.3_{\pm 0.5}$ | $53.6_{\pm 0.7}$ | $69.8_{\pm 0.5}$
128 | Triplet-sum | $17.0_{\pm 0.7}$ | $47.2_{\pm 0.2}$ | $62.7_{\pm 0.2}$ | $20.0_{\pm 1.2}$ | $49.9_{\pm 1.5}$ | $66.7_{\pm 1.0}$
Triplet-max | $11.8_{\pm 0.3}$ | $38.1_{\pm 0.9}$ | $53.7_{\pm 0.5}$ | $15.0_{\pm 0.5}$ | $43.4_{\pm 0.6}$ | $59.6_{\pm 0.7}$
Triplet-weighted | $10.1_{\pm 0.6}$ | $31.7_{\pm 0.9}$ | $46.5_{\pm 0.9}$ | $10.7_{\pm 0.9}$ | $33.4_{\pm 1.7}$ | $48.7_{\pm 2.6}$
NT-Xent | $19.5_{\pm 0.1}$ | $50.4_{\pm 0.3}$ | $65.6_{\pm 0.8}$ | $22.2_{\pm 0.7}$ | $53.7_{\pm 2.0}$ | $69.5_{\pm 0.4}$

###  3.2 Experimental setups

Log mel-spectrograms are used as the audio features, which are extracted using
a $1024$-points Hanning window with $320$-points hop size and $64$ mel bins.
All the models are trained for $50$ epochs using Adam [28]. The learning rate
is set to $1\text{\times}{10}^{-4}$ or $5\text{\times}{10}^{-5}$ and is
decayed to $1$/$10$ of itself every $20$ epochs. The batch size is set to $32$
for the AudioCaps dataset and $24$ for the Clotho dataset. We perform
experiments by freezing and fine-tuning the pre-trained models. The best model
is selected based on the sum of recalls on the validation set.

For all triplet-based losses, the distance margin $m$ is set to $0.2$, and the
temperature hyper-parameter $\tau$ in the NT-Xent loss is set to $0.07$. For
triplet-weighted loss, we follow the hyper-parameter settings in [21], that
is, $Q=2,\\{a_{0}=0.5,a_{1}=-0.7,a_{2}=0.2\\}$, and
$P=2,\\{b_{0}=0.03,b_{1}=-0.4,a_{2}=0.9\\}$. The dimension of the shared
embedding space is $1024$. The learned acoustic semantic embeddings are
normalized. All experiments are carried out on a single RTX3090 GPU.

###  3.3 Evaluation protocol

Recall at rank $k$ (R$@k$) is used as the evaluation metric, which is the
popular cross-modal retrieval evaluation protocol. R$@k$ measures the
percentage of targets retrieved within the top $k$ ranked results, thus the
higher the score, the better the performance. We report R$@1$, R$@5$, and
R$@10$. All the experiments are repeated three times with different training
seeds and we report the mean and standard deviation of the metrics.

##  4 Results

###  4.1 Model performance

The experimental results are shown in Table 1. The baseline model is simple
but effective. It can be observed that fine-tuning can substantially improve
the model performance and lead to state-of-the-art results on both datasets.
In addition, we could observe that the scores on the Clotho dataset are
relatively lower than those on the AudioCaps dataset, which is consistent with
the results in [16]. The reasons might be two folds: (1) the size of training
data is limited in the Clotho dataset, (2) captions for each audio clip in the
Clotho dataset are more diverse thus it is challenging to map the diverse
captions close with each other in the shared acoustic semantic embedding
space.

###  4.2 Metric learning objectives

As can be seen in Table 1, the NT-Xent loss shows stable performance on both
AudioCaps and Clotho datasets regardless of whether the pre-trained encoders
are fine-tuned or frozen. It outperforms the other three triplet-based losses
in most cases on both text-to-audio and audio-to-text retrieval. For the other
three triplet-based losses, the models trained via triplet-sum are not as good
as others especially when the encoders are frozen. However, they achieve
similar performance on the Clotho dataset when the encoders are fine-tuned.
The triplet-max and triplet-weighted losses achieve similar results on the
AudioCaps dataset, but the models trained via triplet-weighted loss perform
less well than others on the Clotho dataset when the encoders are frozen. The
weighting method does not bring substantial improvements. The reason might be
that the weighting function has many hyper-parameters to be tuned while we
have used the values in the original work [21]. Tuning the hyper-parameters
for the dataset we evaluated may lead to better performance. Overall, the NT-
Xent loss outperforms other three triplet-based losses on both text-to-audio
and audio-to-text retrieval in most situations.

In our experiments, we also found that the two losses based on hardest
negative mining, the triplet-max and triplet-weighted losses, are sensitive to
the training settings, while the other two, triplet-sum and NT-Xent, are more
robust and stable to different training settings. For example, triplet-max and
triplet-weighted need a good learning rate, otherwise the models are difficult
to converge. On the AudioCaps dataset, all the models are trained with a
learning rate of $1\text{\times}{10}^{-4}$ and all converge well. However, the
models trained via triplet-max and triplet-sum with such a learning rate do
not converge on the Clotho dataset. Furthermore, triplet-max and triplet-
weighted are sensitive to the initialization of model parameters, and we found
that some of the models with different training seeds may not converge under
the same training settings.

In addition, we study the impact of batch size on the AudioCaps dataset
without fine-tuning the encoders. The results are shown in Table 2. We can
observe the performance of models trained via triplet-max and triplet-weighted
losses degrades considerably when the batch size is increased to $128$, while
models trained via the other two losses (triplet-sum and NT-Xent) show stable
performance with respect to the change of the batch size. This is somewhat
inconsistent with results in the literature, where it is generally believed
that larger batch sizes could lead to better performance for the triplet-based
losses [18]. We found the triplet-max and triplet-weighted do not converge
with a batch size of 128. The reason might be that the learning rate should
also be tuned to adapt for a larger batch size. Overall, triplet-sum and NT-
Xent losses are more robust to different training settings and datasets, while
triplet-max and triplet-weighted are more difficult to train.

##  5 Conclusions

We have presented a simple but effective model to learn the Acoustic Semantic
Embeddings for the free-form language-based audio-text retrieval task, then we
studied the impact of metric learning objectives based on our model in a
constant training setting. We empirically demonstrated that the metric
learning objectives have a significant impact on the model performance, where
the NT-Xent loss outperformed the popular triplet-based losses and showed
stable performances with respect to different training settings and datasets.
The triplet losses with hard negative mining need careful tuning of hyper-
parameters, and are sensitive to the initialization of model parameters.

##  6 Acknowledgements

This work is partly supported by a Newton Institutional Links Award from the
British Council, titled “Automated Captioning of Image and Audio for Visually
and Hearing Impaired” (Grant number 623805725) and grants EP/T019751/1 and
EP/V002856/1 from the Engineering and Physical Sciences Research Council
(EPSRC). For the purpose of open access, the author has applied a Creative
Commons Attribution (CC BY) licence to any Author Accepted Manuscript version
arising.

## References

  * [1] F. Faghri, D. J. Fleet, J. R. Kiros, and S. Fidler, “VSE++: Improving visual-semantic embeddings with hard negatives,” in _Proceedings of the British Machine Vision Conference (BMVC)_ , 2018. [Online]. Available: https://github.com/fartashf/vsepp
  * [2] K. Li, Y. Zhang, K. Li, Y. Li, and Y. Fu, “Visual semantic reasoning for image-text matching,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 4654–4662.
  * [3] X. Li, X. Yin, C. Li, P. Zhang, X. Hu, L. Zhang, L. Wang, H. Hu, L. Dong, F. Wei _et al._ , “Oscar: Object-semantics aligned pre-training for vision-language tasks,” in _European Conference on Computer Vision_. Springer, 2020, pp. 121–137.
  * [4] Y. Liu, S. Albanie, A. Nagrani, and A. Zisserman, “Use what you have: Video retrieval using representations from collaborative experts,” in _British Machine Vision Conference_ , 2019.
  * [5] A. Miech, I. Laptev, and J. Sivic, “Learning a text-video embedding from incomplete and heterogeneous data,” _arXiv preprint arXiv:1804.02516_ , 2018\.
  * [6] V. Gabeur, C. Sun, K. Alahari, and C. Schmid, “Multi-modal Transformer for Video Retrieval,” in _European Conference on Computer Vision (ECCV)_ , 2020.
  * [7] G. Chechik, E. Ie, M. Rehn, S. Bengio, and D. Lyon, “Large-scale content-based audio retrieval from text queries,” in _Proceedings of the 1st ACM International Conference on Multimedia Information Retrieval_ , 2008, pp. 105–112.
  * [8] S. Ikawa and K. Kashino, “Acoustic event search with an onomatopoeic query: measuring distance between onomatopoeic words and sounds,” in _Proceedings of the Detection and Classification of Acoustic Scenes and Events 2018 Workshop (DCASE)_ , 2018, pp. 59–63.
  * [9] B. Elizalde, S. Zarar, and B. Raj, “Cross modal audio search and retrieval with joint embeddings based on text and audio,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2019, pp. 4095–4099.
  * [10] X. Mei, X. Liu, Q. Huang, M. D. Plumbley, and W. Wang, “Audio captioning transformer,” in _Proceedings of the 6th Detection and Classification of Acoustic Scenes and Events 2021 Workshop (DCASE2021)_ , Barcelona, Spain, November 2021, pp. 211–215.
  * [11] X. Mei, X. Liu, J. Sun, M. D. Plumbley, and W. Wang, “Diverse audio captioning via adversarial training,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2022.
  * [12] X. Liu, Q. Huang, X. Mei, T. Ko, H. Tang, M. D. Plumbley, and W. Wang, “CL4AC: A contrastive loss for audio captioning,” in _Proceedings of the 6th Detection and Classification of Acoustic Scenes and Events 2021 Workshop (DCASE2021)_ , Barcelona, Spain, November 2021, pp. 196–200.
  * [13] X. Liu, X. Mei, Q. Huang, J. Sun, J. Zhao, H. Liu, M. D. Plumbley, V. Kılıç, and W. Wang, “Leveraging pre-trained bert for audio captioning,” _arXiv preprint arXiv:2203.02838_ , 2022.
  * [14] C. D. Kim, B. Kim, H. Lee, and G. Kim, “AudioCaps: Generating captions for audios in the wild,” in _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , 2019, pp. 119–132.
  * [15] K. Drossos, S. Lipping, and T. Virtanen, “Clotho: An audio captioning dataset,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 736–740.
  * [16] A. S. Koepke, A.-M. Oncescu, J. Henriques, Z. Akata, and S. Albanie, “Audio retrieval with natural language queries: A benchmark study,” _IEEE Transactions on Multimedia_ , 2022.
  * [17] K. Musgrave, S. Belongie, and S.-N. Lim, “A metric learning reality check,” in _European Conference on Computer Vision_. Springer, 2020, pp. 681–699.
  * [18] F. Schroff, D. Kalenichenko, and J. Philbin, “Facenet: A unified embedding for face recognition and clustering,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2015, pp. 815–823.
  * [19] J. S. Chung, J. Huh, S. Mun, M. Lee, H.-S. Heo, S. Choe, C. Ham, S. Jung, B.-J. Lee, and I. Han, “In defence of metric learning for speaker recognition,” _Proc. Interspeech 2020_ , pp. 2977–2981, 2020.
  * [20] M. Bleeker and M. de Rijke, “Do lessons from metric learning generalize to image-caption retrieval?” _arXiv preprint arXiv:2202.07474_ , 2022.
  * [21] J. Wei, X. Xu, Y. Yang, Y. Ji, Z. Wang, and H. T. Shen, “Universal weighting metric learning for cross-modal matching,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020\.
  * [22] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 1597–1607.
  * [23] X. Mei, Q. Huang, X. Liu, G. Chen, J. Wu, Y. Wu, J. ZHAO, S. Li, T. Ko, H. Tang, X. Shao, M. D. Plumbley, and W. Wang, “An encoder-decoder based audio captioning system with transfer and reinforcement learning,” in _Proceedings of the 6th Detection and Classification of Acoustic Scenes and Events 2021 Workshop (DCASE2021)_ , Barcelona, Spain, November 2021, pp. 206–210.
  * [24] Q. Kong, Y. Cao, T. Iqbal, Y. Wang, W. Wang, and M. D. Plumbley, “PANNs: Large-scale pretrained audio neural networks for audio pattern recognition,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 28, pp. 2880–2894, 2020.
  * [25] X. Glorot, A. Bordes, and Y. Bengio, “Deep sparse rectifier neural networks,” in _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_. JMLR Workshop and Conference Proceedings, 2011, pp. 315–323.
  * [26] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “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)_ , 2019, pp. 4171–4186.
  * [27] J. F. Gemmeke, D. P. W. Ellis, D. Freedman, A. Jansen, W. Lawrence, R. C. Moore, M. Plakal, and M. Ritter, “Audio Set: An ontology and human-labeled dataset for audio events,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , New Orleans, LA, 2017.
  * [28] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _ICLR (Poster)_ , 2015. [Online]. Available: http://arxiv.org/abs/1412.6980


# A short note on model selection by LASSO methods in a change-point model

Fuqi Chen University of Windsor, 401 Sunset Avenue, Windsor, Ontario, N9B 3P4.
Email<EMAIL_ADDRESS>and Sévérien Nkurunziza University of Windsor, 401
Sunset Avenue, Windsor, Ontario, N9B 3P4. Email<EMAIL_ADDRESS>
###### Abstract

In Ciuperca (2012) (Ciuperca. Model selection by LASSO methods in a change-
point model, Stat. Papers, 2012;(in press)), the author considered a linear
regression model with multiple change-points occurring at unknown times. In
particular, the author studied the asymptotic properties of the LASSO-type and
of the adaptive LASSO estimators. While the established results seem
interesting, we point out some major errors in proof of the most important
result of the quoted paper. Further, we present a corrected result and proof.

Keywords: Asymptotic properties; Change-points; Model selection; LASSO;
Regression.

##  1 Introduction

In Ciuperca (2012), the author considered a linear regression model with
multiple change-points occurring at unknown times. In particular, the author
studied the asymptotic properties of the LASSO-type and that of the adaptive
LASSO estimators. While the established results seem interesting, we point out
a major error in proof of one of the important result. In particular, the
proof of Part (ii) of Lemma 3 in Ciuperca (2011) is based on the inequality
$|a^{2}-b^{2}|\leqslant(a-b)^{2}$, which is wrong. Indeed, take $a=2$ and
$b=1$, we get $|a^{2}-b^{2}|=3>(2-1)^{2}=1$ which contradicts the inequality
used in the quoted paper.

For the sake of clarity, we use the same notation and we suppose that the main
assumptions in Ciuperca (2012) hold. Below, we recall these assumptions for
the convenience of the reader. Namely, we consider the following model:
$Y_{i}=f_{\theta}(X_{i})+\varepsilon_{i}$, where

$f_{\theta}(X_{i})=X^{\prime}_{i}\phi_{1}\mathbb{\mathbb{I}}_{\left\\{i<l_{1}\right\\}}+X^{\prime}_{i}\phi_{2}\mathbf{\mathbb{I}}_{\left\\{l_{1}\leq
i<l_{2}\right\\}}+...+X^{\prime}_{i}\phi_{K+1}\mathbf{\mathbb{I}}_{\left\\{i>l_{K}\right\\}},\quad
i=1,...n,$

$\mathbb{\mathbb{I}}_{A}$ denotes the indicator function of the event $A$,
$Y_{i}$ denotes the response variable, $X_{i}$ is a $p$-vector of regressors,
$(\varepsilon_{i})_{1\leqslant i\leqslant n}$ are the errors which are assumed
to be independent and identically distributed (i.i.d.) random variables,
$\phi_{i}\in\Gamma\subset\mathbb{R}^{p}$, $\Gamma$ is compact,
$i=1,2,\dots,K$. The model parameters are given by
$\theta=(\theta_{1},\theta_{2})$, with the regression parameters
$\theta_{1}=(\phi_{1},...\phi_{k+1})$ and the change-points
$\theta_{2}=(l_{1},...,l_{k})$. In addition, we set
$\theta_{1}^{0}=(\phi_{1}^{0},...\phi_{k+1}^{0})$ and
$\theta_{2}^{0}=(l_{1}^{0},...,l_{k}^{0})$ to be the true values of
$\theta_{1}$ and $\theta_{2}$, respectively. As in Ciuperca (2012), we impose
the following conditions.

### Main Assumptions

$\bm{(H_{1})}$

There exists two positive constants $u,c_{0}(>0)$ such that
$l_{r+1}-l_{r}\geqslant c_{0}[n^{u}]$, for every $r\in(1,...,K)$, with
$l_{0}=1$ and $l_{K+1}=n$. Without loss of generality, we consider
$3/4\leqslant u\leqslant 1$, and $c_{0}=1$.

$(\bm{H_{2}})$

$n^{-1}\,\displaystyle{\max_{1\leqslant i\leqslant
n}}(X^{\prime}_{i}X_{i})\xrightarrow[n\rightarrow\infty]{}\bm{0}$ and for any
$r=1,...,K+1$, the matrix
$C_{n,r}\equiv(l_{r}-l_{r-1})\displaystyle{\sum_{i=l_{r-1}+1}^{l_{r}}}X_{i}X^{\prime}_{i}\xrightarrow[n\rightarrow\infty]{}C_{r}$,
where $C_{r}$ is a non-negative definite matrix.

$(\bm{H_{3}})$

$\varepsilon$ is a random variable absolutely continuous with
$\textrm{E}(\varepsilon_{i})=0$, $\textrm{E}(\varepsilon_{i}^{2})=\sigma^{2}$,
$i=1,2,\dots,n$.

We assume that $\phi_{r}\neq\phi_{r+1}$, $r=1,...,k$, and consider the
following penalized sum:

$S(l_{1},...,l_{k})=\sum_{r=1}^{k+1}\Big{[}\inf_{\phi_{r}}\sum_{i=l_{r-1}+1}^{l_{r}}\Big{(}((Y_{i}-X_{i}\phi_{r})^{2})+\frac{\lambda_{n,(l_{r-1},l_{r})}}{l_{r}-l_{r-1}}\sum_{u=1}^{P}|\phi_{r,u}|^{\gamma}\Big{)}\Big{]},$

where $\lambda_{n,(l_{r-1},l_{r})}=O(l_{r}-l_{r-1})^{1/2}$ is the tuning
parameter and $\gamma>0$. We define the LASSO-type estimator of
$(\theta_{1}^{0},\theta_{2}^{0})$, say
$(\hat{\theta}_{1}^{s},\hat{\theta}_{2}^{s})$, where
$\hat{\theta}_{1}^{s}=(\hat{l}_{1}^{s},...,\hat{l}_{k}^{s})$ and
$\hat{\theta}_{2}^{s}=(\hat{\phi}_{1}^{s},...,\hat{\phi}_{k+1}^{s})$, by

$\hat{\phi}_{r}^{s}=\displaystyle{\arg\min_{\phi_{r}}}\sum_{i=l_{r-1}+1}^{l_{r}}\Big{(}(Y_{i}-X_{i}\phi_{r})^{2})+\frac{\lambda_{n,(l_{r-1},l_{r})}}{l_{r}-l_{r-1}}\sum_{u=1}^{P}|\phi_{r,u}|^{\gamma}\Big{)},\quad\forall
r=1,...,k+1,$

and

$\hat{\theta}_{1}^{s}=\displaystyle{\arg\min_{\theta_{1}}}S(l_{1},...,l_{k}).$

Note that, for $\gamma=1$ and $\gamma=2$, we obtain the LASSO estimator and
ridge estimator respectively.

The rest of this paper is organized as follows. Section 2 gives the main
result of this paper, and in Section 3. The proof of the main result is given
in the Appendix.

##  2 Main result

######  Lemma 2.1.

Under Assumptions $(\bm{H_{2}})$, $(\bm{H_{3}})$, for all $n_{1}$, $n_{2}\in
N$, such that $n_{1}\geqslant n^{u}$, with $3/4\leq u\leq 1$, $n_{2}\leq
n^{v}$, $v<1/4$, let be the model:

$\displaystyle Y_{i}$ $\displaystyle=$ $\displaystyle
X_{i}^{\prime}\phi_{1}^{0}+\epsilon_{i},\;i=1,...,n_{1}$ $\displaystyle Y_{i}$
$\displaystyle=$ $\displaystyle
X_{i}^{\prime}\phi_{2}^{0}+\epsilon_{i},\;i=n_{1}+1,...,n_{2},$

with $\phi_{1}^{0}\neq\phi_{2}^{0}$. We set
$A_{n_{1}+n_{2}}^{s}(\phi)=\displaystyle{\sum_{i=1}^{n_{1}}}\eta_{i;(0,n_{1})}^{s}(\phi,\phi_{1}^{0})+\displaystyle{\sum_{i=n_{1}+1}^{n_{1}+n_{2}}}\eta_{i;(n_{1},n_{1}+n_{2})}^{s}(\phi,\phi_{2}^{0})$
and
$\hat{\phi}_{n_{1}+n_{2}}^{s}=\displaystyle{\arg\min_{\phi}}A_{n_{1}+n_{2}}^{s}(\phi)$.
Let $\delta\in(0,u-3v)$. Then,

  1. (i)

$||\hat{\phi}_{n_{1}+n_{2}}^{s}-\phi_{1}^{0}||\leq n^{-(u-v-\delta)/2}$.

  2. (ii)

If $\phi_{2}^{0}=\phi_{1}^{0}+\phi_{3}^{0}\,n^{-1/4}$ for some $\phi_{3}^{0}$,
then

$\displaystyle{\sum_{i=1}^{n_{1}}}\eta_{i;(0,n_{1})}^{s}(\phi_{n_{1}+n_{2}}^{s},\phi_{1}^{0})=O_{p}(1).$

######  Remark 2.1.

It should be noted that, although Part (i) of the above lemma is the same as
that of lemma 3 of Ciuperca (2012), Part (ii) is slightly different. The
established result holds if
$\phi_{2}^{0}=\phi_{1}^{0}+\phi_{3}^{0}\,n^{-1/4}$, while the result stated in
Ciuperca (2012) is supposed to hold for all $\phi_{2}^{0}\neq\phi_{1}^{0}$,
but with incorrect proof. So far, we are neither able to correct the proof for
all $\phi_{2}^{0}\neq\phi_{1}^{0}$ nor to prove that the statement itself is
wrong. Similarly, Part (ii) of Lemmas 4 and 8 hold under the condition that
$\phi_{2}^{0}=\phi_{1}^{0}+\phi_{3}^{0}\,n^{-1/4}$.

##  3 Concluding Remark

In this paper, we proposed a modification of Part (ii) of Lemma 3 given in
Ciuperca (2012) for which the proof is wrong. Further, we provided the correct
proof. It should be noted that there are several important results in the
quoted paper which were established by using Lemma 3. In particular, the
quoted author used this lemma in establishing Lemmas 4 and 8, as well as
Theorems 1, 2 and 4.

##  Appendix A Appendix

###### Proof of Lemma 2.1.

  1. (i)

The proof of Part (i) is similar to that in Ciuperca (2012).

  2. (ii)

Let
$Z_{n}(\phi)=\displaystyle{\sum_{i=1}^{n_{1}}}\eta_{i}(\phi,\phi_{1}^{0})$,
$t_{n}(\phi)=\displaystyle{\sum_{i=n_{1}+1}^{n_{1}+n_{2}}}[(\epsilon_{i}-X_{i}^{\prime}(\phi-\phi_{2}^{0}))^{2}-(\epsilon_{i}-X_{i}^{\prime}(\phi_{1}-\phi_{2}^{0}))^{2}]$.
Then,

$\displaystyle|t_{n}(\hat{\phi}_{n_{1}+n_{2}})|$ $\displaystyle=$
$\displaystyle|-2\sum_{i=n_{1}+1}^{n_{1}+n_{2}}\varepsilon_{i}X_{i}^{\prime}(\hat{\phi}_{n_{1}+n_{2}}-\phi_{1}^{0})+(\hat{\phi}_{n_{1}+n_{2}}-\phi_{2}^{0})^{\prime}\sum_{i=n_{1}+1}^{n_{1}+n_{2}}X_{i}X_{i}^{\prime}(\hat{\phi}_{n_{1}+n_{2}}-\phi_{2}^{0})$
$\displaystyle-(\phi_{1}^{0}-\phi_{2}^{0})^{\prime}\sum_{i=n_{1}+1}^{n_{1}+n_{2}}X_{i}X_{i}^{\prime}(\phi_{1}^{0}-\phi_{2}^{0})|.$

Since $||\hat{\phi}_{n_{1}+n_{2}}-\phi_{1}^{0}||\leq n^{-(u-v-\delta)/2}$, by
Cauchy-Schwarz inequality, we have

$|\sum_{i=n_{1}+1}^{n_{1}+n_{2}}\varepsilon_{i}X_{i}^{\prime}(\hat{\phi}_{n_{1}+n_{2}}-\phi_{1}^{0})|\leqslant
O(n^{v/2}n^{-(u-v-\delta)/2})=o(1).$

Further, let $\lambda_{\max}$ be the largest eigenvalue of
$\frac{1}{n_{2}}\displaystyle{\sum_{i=n_{1}+1}^{n_{1}+n_{2}}}X_{i}X_{i}^{\prime}$.
Then, using the fact that $\phi_{2}^{0}=\phi_{1}^{0}+\phi_{3}^{0}n^{-1/4}$ and
Cauchy-Schwarz inequality, we have

$\displaystyle(\hat{\phi}_{n_{1}+n_{2}}-\phi_{2}^{0})^{\prime}\sum_{i=n_{1}+1}^{n_{1}+n_{2}}X_{i}X_{i}^{\prime}(\hat{\phi}_{n_{1}+n_{2}}-\phi_{2}^{0})$
$\displaystyle=$
$\displaystyle(\hat{\phi}_{n_{1}+n_{2}}-\phi_{1}^{0})^{\prime}n_{2}\frac{1}{n_{2}}\sum_{i=n_{1}+1}^{n_{1}+n_{2}}X_{i}X_{i}^{\prime}(\hat{\phi}_{n_{1}+n_{2}}-\phi_{1}^{0})-2\phi_{3}^{0^{\prime}}n^{-1/4}n_{2}\frac{1}{n_{2}}\sum_{i=n_{1}+1}^{n_{1}+n_{2}}X_{i}X_{i}^{\prime}(\hat{\phi}_{n_{1}+n_{2}}-\phi_{1}^{0})$
$\displaystyle+n^{-1/2}\phi_{3}^{0^{\prime}}n_{2}\frac{1}{n_{2}}\sum_{i=n_{1}+1}^{n_{1}+n_{2}}X_{i}X_{i}^{\prime}\phi_{3}^{0}$
$\displaystyle\leqslant$ $\displaystyle
n_{2}\lambda_{\max}||\hat{\phi}_{n_{1}+n_{2}}-\phi_{1}^{0}||^{2}+2||\phi_{3}^{0}||n^{-1/4}n_{2}\lambda_{\max}||\hat{\phi}_{n_{1}+n_{2}}-\phi_{1}^{0}||+n^{-1/2}n_{2}\lambda_{\max}||\phi_{3}^{0}||^{2},$

and then,

$\displaystyle(\hat{\phi}_{n_{1}+n_{2}}-\phi_{2}^{0})^{\prime}\sum_{i=n_{1}+1}^{n_{1}+n_{2}}X_{i}X_{i}^{\prime}(\hat{\phi}_{n_{1}+n_{2}}-\phi_{2}^{0})=O(n^{(u-v-\delta)}n^{v})+o(1)+O(n^{v-1/2})=o(1).$

Also, we have

$\displaystyle({\phi}_{1}^{0}-\phi_{2}^{0})^{\prime}\sum_{i=n_{1}+1}^{n_{1}+n_{2}}X_{i}X^{\prime}_{i}(\phi_{1}^{0}-\phi_{2}^{0})=n^{-1/2}\phi_{3}^{0^{\prime}}\sum_{i=n_{1}+1}^{n_{1}+n_{2}}X_{i}X_{i}^{\prime}\phi_{3}^{0}=O(n^{v-1/2})=o(1).$

Therefore, $|t_{n}(\hat{\phi}_{n_{1}+n_{2}})|=o_{p}(1)$. Further, since
$Z_{n}(\phi_{1}^{0})=t_{n}(\phi_{1}^{0})=0$,
$Z_{n}(\hat{\phi}_{n_{1}+n_{2}})+t_{n}(\hat{\phi}_{n_{1}+n_{2}})\leqslant
Z_{n}(\phi_{1}^{0})+t_{n}(\phi_{1}^{0})$, we have

$0\geqslant
z_{n}(\hat{\phi}_{n_{1}+n_{2}})+t_{n}(\hat{\phi}_{n_{1}+n_{2}})\geqslant\inf_{\phi}Z_{n}(\phi)-|t_{n}(\hat{\phi}_{n_{1}+n_{2}})|=\inf_{\phi}Z_{n}(\phi)-|o_{p}(1)|.$

Hence

$|z_{n}(\hat{\phi}_{n_{1}+n_{2}})|-|t_{n}(\hat{\phi}_{n_{1}+n_{2}})|\leqslant|z_{n}(\hat{\phi}_{n_{1}+n_{2}})+t_{n}(\hat{\phi}_{n_{1}+n_{2}})|\leqslant|\inf_{\phi}Z_{n}(\phi)|+o_{p}(1),$

which implies that

$|z_{n}(\hat{\phi}_{n_{1}+n_{2}})|\leqslant|\inf_{\phi}Z_{n}(\phi)|+o_{p}(1)+|t_{n}(\hat{\phi}_{n_{1}+n_{2}})|=|\inf_{\phi}Z_{n}(\phi)|+o_{p}(1).$

Let $\hat{\phi}_{n_{1}}=\arg\min_{\phi}Z_{n}(\phi)$ and $\lambda_{\max}$ be
the largest eigenvalue of $n_{1}^{-1}\sum_{i=1}^{n_{1}}X_{i}X^{\prime}_{i}$.
Then, by Cauchy-Schwarz inequality,

$\displaystyle\inf_{\phi}Z_{n}(\phi)\leqslant\left(\sqrt{n_{1}}\left\|\hat{\phi}_{n_{1}}-\phi_{1}^{0}\right\|\right)^{2}\lambda_{\max}+2\sqrt{n_{1}}\left|(\hat{\phi}_{n_{1}}-\phi_{1}^{0})^{\prime}n_{1}^{-1/2}\sum_{i=1}^{n_{1}}\varepsilon_{i}X_{i}\right|,$

and then,

$\displaystyle\inf_{\phi}Z_{n}(\phi)=O_{p}(1)+O_{p}(1)O_{p}(1)=O_{p}(1),\quad{}\mbox{
and }\quad{}|z_{n}(\hat{\phi}_{n_{1}+n_{2}})|=O_{p}(1).$

Now, let

$\displaystyle Z_{n}^{s}(\phi)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n_{1}}\eta_{i}(\phi,\phi_{1}^{0})+\lambda_{n;(0,n_{1})}[\sum_{k=1}^{p}(|\phi_{,k}|^{\gamma}-|\phi_{1,k}^{0}|^{\gamma})]$
$\displaystyle t_{n}^{s}(\phi)$ $\displaystyle=$
$\displaystyle\sum_{i=n_{1}+1}^{n_{1}+n_{2}}[(\epsilon_{i}-X_{i}^{\prime}(\phi-\phi_{2}^{0}))^{2}-(\epsilon_{i}-X_{i}^{\prime}(\phi_{1}-\phi_{2}^{0}))^{2}]$
$\displaystyle\quad{}+\lambda_{n;(n_{1},n_{1}+n_{2})}[\sum_{k=1}^{p}(|\phi_{,k}|^{\gamma}-|\phi_{1,k}^{0}|^{\gamma})].$

Then,

$A_{n_{1}+n_{2}}^{s}(\phi)=Z_{n}^{s}(\phi)+t_{n}^{s}(\phi)-(\epsilon_{i}-X_{i}^{\prime}(\phi_{1}-\phi_{2}^{0}))^{2}+\lambda_{n;(n_{1},n_{1}+n_{2})}[\sum_{k=1}^{p}(|\phi_{1,k}^{0}|^{\gamma}-|\phi_{2,k}^{0}|^{\gamma})].$

Then
$\hat{\phi}_{n_{1}+n_{2}}^{s}=\arg\min_{\phi}(Z_{n}^{s}(\phi)+t_{n}^{s}(\phi))=\arg\min_{\phi}A_{n_{1}+n_{2}}^{s}(\phi)$.
In addition, using the similar approach as previous, with the fact that
$||\hat{\phi}_{n_{1}+n_{2}}^{s}-\phi_{1}^{0}||\leqslant n^{-(u-v-\delta)/2}$
and $\phi_{2}^{0}=\phi_{1}^{0}+\phi_{3}^{0}n^{-1/4}$, we have

$\displaystyle|t_{n}^{s}(\hat{\phi}_{n_{1}+n_{2}}^{s})|$
$\displaystyle\leqslant$ $\displaystyle
o(1)+\lambda_{n;(n_{1},n_{1}+n_{2})}[\sum_{k=1}^{p}(|\hat{\phi}_{n_{1}+n_{2},k}^{s}|^{\gamma}-|\phi_{1,k}^{0}|^{\gamma})]$
$\displaystyle=$ $\displaystyle
o_{p}(1)+O(n^{v/2})O_{p}(||\hat{\phi}_{n_{1}+n_{2}}^{s}-\phi_{1}^{0}||)=O_{p}(n^{-(u-2v-\delta)/2})=o_{p}(1).$

Besides, $Z_{n}^{s}(\phi_{1}^{0})=t_{n}^{s}(\phi_{1}^{0})=0$, thus

$\displaystyle
0\geqslant\inf_{\phi}(Z_{n}^{s}(\phi_{1}^{0})+t_{n}^{s}(\phi_{1}^{0}))=Z_{n}^{s}(\hat{\phi}_{n_{1}+n_{2}}^{s})+t_{n}^{s}(\hat{\phi}_{n_{1}+n_{2}}^{s})=Z_{n}^{s}(\hat{\phi}_{n_{1}+n_{2}}^{s})-|o_{p}(1)|$
$\displaystyle\geqslant\inf_{\phi}Z_{n}^{s}(\phi)-|o_{p}(1)|.$

Hence

$|Z_{n}^{s}(\hat{\phi}_{n_{1}+n_{2}}^{s})|\leqslant|\inf_{\phi}Z_{n}^{s}(\phi)|+o_{p}(1).$

On the other hand, since

$0\geqslant\inf_{\phi}Z_{n}^{s}(\phi)\geqslant\inf_{\phi}Z_{n}(\phi)+\lambda_{n;(0,n_{1})}\inf_{\phi}[\sum_{k=1}^{p}(|\phi_{,k}|^{\gamma}-|\phi_{1,k}^{0}|^{\gamma})],$
$|\inf_{\phi}Z_{n}^{s}(\phi)|\leqslant|\inf_{\phi}Z_{n}(\phi)|+|\lambda_{n;(0,n_{1})}\inf_{\phi}[\sum_{k=1}^{p}(|\phi_{,k}|^{\gamma}-|\phi_{1,k}^{0}|^{\gamma})]|.$

Further,

$\inf_{\phi}[\sum_{k=1}^{p}(|\phi_{,k}|^{\gamma}-|\phi_{1,k}^{0}|^{\gamma})]\leqslant\sum_{k=1}^{p}(|\hat{\phi}_{n_{1},k}|^{\gamma}-|\phi_{1,k}^{0}|^{\gamma})=O_{p}(||\hat{\phi}_{n_{1}}-\phi_{1}^{0}||)=O_{p}(n_{1}^{-1/2}),$

and $\inf_{\phi}Z_{n}(\phi)=O_{p}(1)$. It follows that
$|\inf_{\phi}Z_{n}^{s}(\phi)|\leqslant O_{p}(1)$. Hence,

$|Z_{n}^{s}(\hat{\phi}_{n_{1}+n_{2}}^{s})|\leqslant|\inf_{\phi}Z_{n}^{s}(\phi)|+o_{p}(1)=O_{p}(1).$

∎

## References

  * [1] Ciuperca, G. (2012). Model selection by LASSO methods in a change-point model. Stat Papers, DOI: 10.1007/s00362-012-0482-x (in press).