# Myocardial Infarction Detection from ECG: A Gramian Angular Field-based
2D-CNN Approach

Asim Yousuf1, Rehan Hafiz1, Saqib Riaz2, Muhammad Farooq3, Kashif Riaz1, M.
Mahboob Ur Rahman1  1 Electrical engineering department, Information
Technology University, Lahore 54000, Pakistan
2 Bahawal Victoria Hospital, Bahawalpur, Pakistan
3 Phyn LLC, Torrance, CA, USA
1{kashif.riaz<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

This paper presents a novel method for myocardial infarction (MI) detection
using lead II of electrocardiogram (ECG). Under our proposed method, we first
clean the noisy ECG signals using db4 wavelet, followed by an R-peak detection
algorithm to segment the ECG signals into beats. We then translate the ECG
timeseries dataset to an equivalent dataset of gray-scale images using Gramian
Angular Summation Field (GASF) and Gramian Angular Difference Field (GADF)
operations. Subsequently, the gray-scale images are fed into a custom two-
dimensional convolutional neural network (2D-CNN) which efficiently
differentiates the ECG beats of the healthy subjects from the ECG beats of the
subjects with MI. We train and test the performance of our proposed method on
a public dataset, namely, Physikalisch Technische Bundesanstalt (PTB) ECG
dataset from Physionet. Our proposed approach achieves an average
classification accuracy of 99.68%, 99.80%, 99.82%, and 99.84% under GASF
dataset with noise and baseline wander, GADF dataset with noise and baseline
wander, GASF dataset with noise and baseline wander removed, and GADF dataset
with noise and baseline wander removed, respectively. Our proposed method is
able to cope with additive noise and baseline wander, and does not require
handcrafted features by a domain expert. Most importantly, this work opens the
floor for innovation in wearable devices (e.g., smart watches, wrist bands
etc.) to do accurate, real-time and early MI detection using a single-lead
(lead II) ECG.

###### Index Terms:

Cardiovascular Diseases, Myocardial Infarction, Electrocardiogram,
Convolutional Neural Network, Gramian Angular Difference Field, Gramian
Angular Summation Field.

##  I Introduction

According to the world health organization (WHO), cardiovascular diseases
(CVDs) are among the leading cause of death in the people worldwide [1].
Myocardial infarction (MI), more commonly known as heart attack, is a
frequently occurring CVD. A very brief pathophysiology of the MI is as
follows. MI is often caused by the coronary artery disease (coronary arteries
supply the Oxygen-rich blood to the heart muscle known as myocardium, after
each contraction). Occasionally, the blood supply to myocardium is reduced due
to the build-up of cholesterol-rich plaques inside the walls of one of the
coronary arteries, leading to what is called cardiac ischemia. If it remains
untreated, cardiac ischemia may lead to MI [2], [3]. MI is a life-threatening
condition, and if clinical intervention is not made within hours (or days) of
onset, it may result in injury and irreversible damage of the heart muscle
leading to a heart attack [4]. MI is also known as a silent heart attack
because many times the heart muscle starts to die while patients are not even
aware of it. It has been estimated that among all the heart attacks that are
reported, around 72% are the silent attacks [5].

Electrocardiogram (ECG), a cost-effective and non-invasive method, is
unanimously considered as a golden standard for diagnosing a wide range of
cardiac irregularities [2]. Thus, ECG could provide viable hints/cues about
the MI at early stages [6]. An ECG signal comprises 12 leads including lead I,
II, III (standard leads), V1-V6 (chest leads), and aVL, aVR, aVF (limb leads).
For the detection of MI, cardiologists need to analyze manually the ECG traces
of the affected individuals, which is a time-consuming and error-prone method.
Therefore, an artificial intelligence (AI)-aided automatic MI detection system
is the need of the hour.

The conventional machine learning (ML) techniques have shown great promise for
semi-automatic MI detection with good accuracy. Some prominent techniques used
by the ML methods include the following: wavelet decomposition [7], sparse
decomposition [8], linear discriminant analysis [9], and support vector
machines (SVMs) [10], multi-scale principal component analysis [11], wavelet
packet decomposition [12], and independent component analysis [13].

All of the above-mentioned ML methods have some drawbacks. First, such methods
rely upon extraction of handcrafted features by the domain experts. Besides,
it is difficult to retain the generalization capabilities of the ML
classifiers on the unseen data because the classification results may rely on
the nature of handcrafted features which could change dramatically with the
change in age, gender, or medical history of the new patients. Deep learning
(DL) techniques, on the other hand, have the promise of automated feature
extraction [14], [15], [16], [17]. Thus, inline with the most recent DL-based
works, this work proposes a novel DL-based method for automatic MI detection.

Contributions: The main contribution of this work is two-fold. 1) The proposed
method utilizes the Gramian angular field (GAF) method in order to convert the
one-dimensional ECG timeseries (with and without noise) from a public dataset
into two-dimensional gray-scale images. 2) The GAF images are fed into a
custom 2D-convolutional neural network (CNN) model that automatically extracts
the complex representative features from the 2D input data and classifies
these images as either belonging to healthy or MI subjects.

Outline: The rest of this paper is organized as follows. Section II summarizes
the selected related work. Section III describes the key statistics of the
public ECG dataset used in this work, key data pre-processing steps, Gramian
Angular field-based transformation of 1D ECG signal to a 2D image, and the
architecture of the custom 2D-CNN. Section IV outlines performance metrics,
provides pertinent details regarding experimental setup, and discusses
selected results. Section V concludes the paper.

##  II Related Work

Several researchers have employed DL techniques for the identification or
localization of ECG arrhythmias. Authors in [18] used 48 records of lead-II
ECG, and proposed a 1D-CNN model for classification of normal and four
different arrhythmias using ECG signals. [19] used 6,877 records of 12-leads
ECG, and implemented a bi-directional long-short-term-memory (LSTM) network to
classify the ECG signals into normal and eight different arrhythmias. Authors
in [20] the 48 records of lead-II ECG, and presented an R-peak detection
method and a recurrent neural network (RNN). Their proposed method learns time
correlation from lead-II ECG of 48 records and classifies ECG signals into
normal and four different arrhythmias. Authors in [21] used 549 records of
lead-II ECG, and implemented a 1D-CNN for the classification of normal ECG and
eight different arrhythmias. Authors in [22] utilized 106,501 ECG beats as
$128\times 128$ gray-scale images, and proposed an R-peak detection method and
a 1D-CNN for the classification of normal and MI beats. Authors in [23]
proposed a method based on pattern recognition and a 2D-CNN to classify
between a normal ECG and seven different arrhythmias. [24] used 108,655 beats
of lead-II ECG, and implemented a deep neural network to identify normal and
four different arrhythmias. Finally, authors in [25] used 2,520 ECG records as
a $256\times 256$ images, and proposed a novel approach using short time-
frequency transform-based spectrograms and a 2D-CNN for the classification of
normal ECG and seven different arrhythmias.

##  III Methodology

This section describes the key details of the proposed automated MI detection
system that utilizes the Gramian Angular Field operation and a 2D-CNN. The
main components of the proposed method are illustrated in Fig. 1, and the
pertinent details for each of the component are discussed below.

###  III-A Physikalisch-Technische Bundesanstalt Dataset

We utilize Physikalisch-Technische Bundesanstalt (PTB) ECG dataset [26] from
Physionet. The dataset consists of noisy ECG data of 148 MI subjects: 110 men
and 38 women (aged 36 to 86). The dataset also consists of noisy ECG data of
52 healthy subjects: 39 men and 13 women (aged 17 to 81). Each ECG trace is
100 seconds long, recorded at 1000 samples per second. Table I summarizes the
key details of the PTB dataset. For each subject, 12-lead ECG data is
provided, but we utilize only the lead-II of the ECG data in this work.
Furthermore, to validate the hypothesis that our proposed classifier is robust
to noise, we prepare two types of datasets. The first dataset consists of the
raw and noisy (lead-II) ECG signals from PTB dataset as is, while we construct
the second dataset by removing the noise and baseline wander from the ECG
signals in the first dataset.

Figure 1: The proposed method for MI detection. Figure 2: Lead-II ECG signal
with noise and baseline wander (healthy class).  Figure 3: Lead-II ECG signal
with noise and baseline wander (MI class).

###  III-B Data Pre-processing

Lead-II ECG signals for healthy and MI subjects with noise and baseline wander
are shown in Fig. 2 and Fig. 3 respectively. In this work, Daubechies 4
wavelet is utilized to remove high-frequency noise and baseline wander from
the ECG signals [27]. Thus, clean ECG signals for healthy and MI subjects
(after denoising) are shown in Fig. 4 and Fig. 5, respectively. The R peaks
(positive peak in the QRS complex) are detected in both datasets (noisy and
clean) by means of Pan-Tompkins algorithm [28]. An ECG trace with its R-peaks
detected is shown in Fig. 6.

Figure 4: Lead-II ECG signal with noise and baseline wander removed (healthy
class).  Figure 5: Lead-II ECG signal with noise and baseline wander removed
(MI class).  Figure 6: An ECG trace with its R-peaks detected.

The Pan-Tompkins algorithm allows us to segment the ECG signal into beats, for
both datasets. All ECG signals are segmented in such a way that 250 samples
are considered before the R-peak index to involve P-peak, while 400 samples
are considered after R-peak to involve T-peak, in order to form one beat.
Thus, each beat comprises a window of 651 samples that together capture one
P-QRS-T waveform. The segmentation allowed us to extract 40,267 beats in
total, for both datasets (noisy and clean). We then applied Z-score
normalization to remove the offset effect and address the issue of amplitude
scaling [29]. Fig. 7 and Fig. 8 show the extracted time-domain P-QRS-T wave
(basically, 1 cardiac beat) for the healthy and MI subjects, respectively.

Figure 7: One ECG beat of a healthy subject.  Figure 8: One ECG beat of an MI subject.  Type | Males | Females | Min Age | Max Age |  No: of Beats
---|---|---|---|---|---
Healthy | 39 | 13 | 17 | 81 |  10,139
MI | 110 | 38 | 36 | 86 |  30,128
Total | 149 | 51 | - | - |  40,267
TABLE I: Key details of the PTB dataset

###  III-C Gramian Angular Field Method

Our custom 2D-CNN requires images (i.e., two-dimensional data) on its input in
order to differentiate between the healthy and MI subjects. Therefore, each
ECG beat is encoded as an image using the Gramian angular field (GAF)
operator. Two kinds of GAFs, i.e., Gramian angular field with summation (GASF)
and Gramian angular field with difference (GADF) are used to transform each
time-domain ECG beat to an image as follows. First, a normalized time-domain
ECG beat consisting of $n$ samples in Cartesian coordinates is converted into
a polar coordinate system. Next, a Gramian matrix of dimension $n\times n$ is
formed using trigonometric cosine functions. Specifically, GASF method
computes the cosine of sum of two angles to compute each element of the
Gramian matrix, while GADF computes the sine of subraction of two angles to
compute each element of the Gramian matrix.

More precisely, the 1D ECG timeseries is converted to the 2D image as follows.
Let $X=\\{x_{1},x_{2},…,x_{n}\\}$ represent the ECG beat timeseries consisting
of $n$ real-valued samples. Then, the first step is to re-scale the $i$-th
sample $x_{i}$ of the ECG beat as follows:

$\displaystyle xnor_{i}=\frac{(x_{i}-min(X))+(x_{i}-max(X))}{max(X)-min(X)}$
(1)

Thus, the Min-Max scaler normalizes each ECG beat such that its amplitudes now
lie in the range $[-1,1]$. The next step converts the ECG beat (from
Cartesian) to polar coordinates as follows:

$\displaystyle\emptyset_{i}=\cos^{-1}(xnor_{i})\;\;\;-1\leq xnor_{i}\leq 1$
(2)

It is easy to verify that the polar coordinate $\emptyset_{i}$ of the $i$-th
sample $xnor_{i}$ of the normalized time-domain ECG beat falls in the angular
range of $[0,\pi]$. An angular resolution in the range $[0,\pi]$ provides
significant information to any classifier that utilizes images constructed by
the GASF and GADF operations.

The next step is to compute pair-wise trigonometric sum and difference (for
every two polar-coordinate samples in the ECG beat) in order to capture the
temporal correlation between the samples of the ECG beat at different time
intervals. Accordingly, the Gram matrix corresponding to the GASF operation is
given as follows:

$\displaystyle
G_{GASF}=\begin{pmatrix}\cos(\emptyset_{1}+\emptyset_{1})&\cos(\emptyset_{1}+\emptyset_{2})&\cdots&\cos(\emptyset_{1}+\emptyset_{n})\\\
\cos(\emptyset_{2}+\emptyset_{1})&\cos(\emptyset_{2}+\emptyset_{2})&\cdots&\cos(\emptyset_{2}+\emptyset_{n})\\\
\vdots&\vdots&\ddots&\vdots\\\
\cos(\emptyset_{n}+\emptyset_{1})&\cos(\emptyset_{n}+\emptyset_{2})&\cdots&\cos(\emptyset_{n}+\emptyset_{n})\end{pmatrix}$
(3)

Similarly, the Gram matrix corresponding to the GADF (trigonometric difference
of sine) operation is as follows:

$\displaystyle
G_{GADF}=\begin{pmatrix}\sin(\emptyset_{1}-\emptyset_{1})&\sin(\emptyset_{1}-\emptyset_{2})&\cdots&\sin(\emptyset_{1}-\emptyset_{n})\\\
\sin(\emptyset_{2}-\emptyset_{1})&\sin(\emptyset_{2}-\emptyset_{2})&\cdots&\sin(\emptyset_{2}-\emptyset_{n})\\\
\vdots&\vdots&\ddots&\vdots\\\
\sin(\emptyset_{n}-\emptyset_{1})&\sin(\emptyset_{n}-\emptyset_{2})&\cdots&\sin(\emptyset_{n}-\emptyset_{n})\end{pmatrix}$
(4)

Note that $G_{GADF}$ is a hollow matrix with zeros on its main diagonal.

Finally, Fig. 9 provides a pictorial representation of the GAF method whereby
the ECG beats time series (with and without noise) is transformed to images
under the GASF and GADF operations.

Figure 9: Illustration of ECG Beats timeseries encoded as images using Gramian
Angular Field with summation and difference.

To sum things up, each ECG beat consisting of 651 samples is transformed into
an equivalent $128\times 128$-pixel gray-scale image using the GAF method.
This transformation preserves the temporal correlation between the samples of
the 1D ECG beat signal. Fig. 10 and Fig. 11 show an example transformation of
a sample ECG beat (with and without noise) into GASF and GADF images for a
healthy and MI subject, respectively. We note that there is subtle difference
between the GADF and GADF images for the normal and MI subjects. This attests
to the feasibility of using GAF method for efficient classification
(discrimination) between the two classes (healthy and MI).

Figure 10: Healthy ECG Beats encoded as GASF and GADF images. Figure 11: MI
ECG Beats encoded as GASF and GADF images.

###  III-D The Architecture of the Custom 2D-CNN

We implement a custom multi-layer 2D-CNN for MI detection from GASF and GADF
images. It is well known that the convolutional layers and pooling layers are
important building blocks of a CNN. The convolutional layers do automatic
feature extraction, while the pooling layers down-sample the input volume
along its spatial dimension with care to retain the vital information. The
customized 2D-CNN architecture in this work consists of four convolutional
layers (with RELU activation function), followed by a max-pooling layer.
Subsequently, the data is flattened and passed to the dense network with two
fully-connected layers. A sigmoid activation function is used to do binary
classification (of healthy and MI subjects). Fig. 12 shows the the block
diagram of the customized 2D-CNN model, while Table II summarizes the
architectural details of the custom 2D-CNN model used in this work.

Figure 12: Block diagram of the custom 2D-CNN model used in this work. Layers | Layer Type | No. of Kernels/Neurons | Stride | Input Shape | Output Shape
---|---|---|---|---|---
1 | Convolution + RELU | 16 | 1 | 128 x 128 x 1 | 128 x 128 x 16
Max pooling | - | 2 | 128 x 128 x 16 | 64 x 64 x 16
2 | Convolution + RELU | 32 | 1 | 64 x 64 x 16 | 63 x 63 x 32
Max pooling | - | 2 | 63 x 63 x 32 | 31 x 31 x 32
3 | Convolution + RELU | 64 | 1 | 31 x 31 x 32 | 30 x 30 x 64
Max pooling | - | 2 | 30 x 30 x 64 | 15 x 15 x 64
4 | Convolution + RELU | 128 | 1 | 15 x 15 x 64 | 14 x 14 x 128
Max pooling | - | 2 | 14 x 14 x 128 | 7 x 7 x 128
5 | Fully Connected + RELU | 100 | - | 6272 | 100
6 | Fully Connected + Sigmoid | 2 | - | 100 | 2
TABLE II: Architectural details of the custom 2D-CNN model.

##  IV Experimental Results

###  IV-A Performance Metrics

The performance of the proposed 2D-CNN classifier is evaluated by computing
the following three performance metrics: accuracy, sensitivity, and
specificity, as follows:

$\displaystyle Accuracy(\%)=\frac{(TP+TN)}{(TP+TN+FP+FN)}\times 100$ (5)
$\displaystyle Sensitivity(\%)=\frac{TP}{(TP+FN)}\times 100$ (6)
$\displaystyle Specificity(\%)=\frac{TN}{(TN+FP)}\times 100$ (7)

In the above equations, TP stands for true positive (an ECG beat correctly
classified as belonging to MI class), TN stands for true negative (an ECG
beats correctly classified as belonging to the healthy class), FP stands for a
false positive, (miss-classification of a healthy ECG beat as MI), and FN
stand for false-negative (miss-classification of an MI ECG beat as healthy).

###  IV-B Experiment Details & Hyper-parameters

Next, the implementation details, hyper-parameters, and experimental results
achieved by the proposed approach are discussed. As described earlier, ECG
beats in the PTB dataset were transformed into four types of images/datasets:
namely, DS1 (GASF images with noise and baseline wander), DS2 (GADF images
with noise and baseline wander), DS3 (GASF images with noise and baseline
wander removed), and DS4 (GADF images with noise and baseline wander removed).
For pre-processing and implementation of the custom 2D-CNN, we used Python
environment with Keras and Tensor-flow deep learning libraries. For training
and testing of the custom 2D-CNN, an 80-20 training/test data split was used.
Additionally, we used the K-fold cross-validation approach (with K=10) to
prevent over-fitting [30]. Thus, the overall classification accuracy for each
dataset was obtained as the average value of the accuracy recorded in all 10
cycles of K-fold cross-validation. The accuracy and loss curves became
saturated/stable in less than 50 epochs during both training and validation
phase for all datasets (DS1, DS2, DS3 and DS4), as can be seen in Fig. 13 and
Fig. 14. We used ”Adam” optimizer and ”cross-entropy” as the loss function. We
used gradient-descent method with a learning rate of 0.001, and fixed the
batch size to 8.

Figure 13: Accuracy curves for four datasets (a) GASF method with noise and
baseline wander, (b) GADF method with noise baseline wander, (c) GASF method
without noise and baseline wander, and (d) GADF method without noise and
baseline wander.  Figure 14: Loss curves for four datasets (a) GASF method
with noise and baseline wander, (b) GADF method with noise and baseline
wander, (c) GASF method without noise and baseline wander, and (d) GADF method
without noise and baseline wander.

###  IV-C Results

Our proposed method achieved an average classification accuracy of 99.68%,
99.80%, 99.82%, and 99.84% when utilizing DS1 (GASF images with noise and
baseline wander), DS2 (GADF images with noise and baseline wander), DS3 (GASF
images with noise and baseline wander removed), and DS4 (GADF images with
noise and baseline wander removed). More detailed results (i.e., performance
metrics of accuracy, sensitivity, and specificity) for the best classification
result achieved for each dataset are summarized in Table III.

Model Type | With noise and BW | Without noise and BW | GASF | GADF |  | TN
---
Beats
| TP
---
Beats
| FP
---
Beats
| FN
---
Beats
| ACC
---
(%)
| SEN
---
(%)
| SPE
---
(%)
DS 1 | Y | N | Y | N | 2505 | 7530 | 19 | 13 | 99.68 | 99.8 | 99.2
DS 2 | Y | N | N | Y | 2508 | 7539 | 16 | 4 | 99.80 | 99.9 | 99.3
DS 3 | N | Y | Y | N | 2509 | 7540 | 15 | 3 | 99.82 | 99.9 | 99.4
DS 4 | N | Y | N | Y | 2510 | 7541 | 14 | 2 | 99.84 | 99.7 | 99.4
TABLE III: Classification results for all four datasets. (DS=Data set, TN=True
Negative, TP=True Positive, FP=False Positive, FN=False Negative,
ACC=Accuracy, SEN=Sensitivity, SPE=Specificity, BW=baseline wander).

###  IV-D Discussion

Fig. 15 compares the performance achieved by the proposed method with the
state-of-the-art MI detection works. Many of the existing works use 12-lead
ECG signals to classify between the healthy and MI ECG beats (12-lead ECG
provides more data to the classifier, and thus, helps it achieve a superior
performance; but at the same time, it also increases the complexity of the
classifier by a big amount). In contrast to many of the existing methods, our
proposed method utilizes only the lead-II of the ECG for MI detection. Fig. 15
demonstrates that, when compared with previous works, the proposed method
provides excellent classification accuracy, even when trained on noisy ECG
signals with baseline wander intact.

Figure 15: A comprehensive comparison between our proposed method and the
state-of-the-art: [6],[24],[25],[31],[32],[33],[34].

##  V Conclusion

This paper proposed a novel framework for automated MI detection using lead-II
of ECG. We utilized the PTB dataset from Physionet to train and test our
custom 2D-CNN classifier. Specifically, we first cleaned the noisy ECG signals
using db4 wavelet, followed by an R-peak detection algorithm to segment the
ECG signal into beats. We then translated the 1D time-domain ECG beats (with
and without noise and baseline wander) to gray-scale images using the Gramian
angular field (under summation and difference) method. The transformed gray-
scale images were then fed into the 2D-CNN (with six hidden layers) which
automatically extracted the most relevant features, and eventually classified
the gray-scale images as belonging to either healthy subjects or subjects with
MI. The proposed 2D-CNN model achieved a high classification accuracy that
lies in the range 99.68% to 99.84% (for ECG signals with and without noise and
baseline wander, and under both GASF and GADF methods). Finally, the fact that
the proposed method achieved an excellent accuracy using only the lead-II of
ECG points to the feasibility of implementation of a single-lead ECG in
wearable and portable devices (e.g., smart bands, smart watches etc.) for
nearly continuous and seamless ECG monitoring for real-time and early MI
detection.

## References

  * [1] “World health, cardiovascular diseases (cvds), accessed,” apr. 18, 2018, Available:. [Online]. Available: http://www.who.int/mediacentre/
  * [2] U. Acharya, N. Kannathal, L. Hua, and L. Yi, “Study of heart rate variability signals at sitting and lying postures,” _Journal of bodywork and Movement Therapies_ , vol. 9, no. 2, pp. 134–141,.
  * [3] N. Heart, Lung, B. Institute, and H. Rate, online] Assessed:. [Online]. Available: https://www.nhlbi.nih.gov/health-topics/heart-attack.
  * [4] D. L. K., M. Net, and H. Attack, online] Available:. [Online]. Available: https://www.medicinenet.com/heartattack/whatcausesaheartattack.
  * [5] D. Mozaffarian, E. Benjamin, A. Go, D. Arnett, M. Blaha, M. Cushman, and V. Howard, “Heart disease and stroke statistics-2016 update a report from the american heart association,” _Circulation,”_ , vol. 133, no. 4, pp. 38– 48,.
  * [6] U. Acharya, H. Fujita, V. Sudarshan, S. Oh, M. Adam, J. Koh, and C. Poo, “Automated detection and localization of myocardial infarction using electrocardiogram: a comparative study of different leads,” _Knowledge-Based Systems,”_ , vol. 99, pp. 146–156,.
  * [7] U. Raghavendra, H. Fujita, A. Gudigar, R. Shetty, K. Nayak, U. Pai, and U. Acharya, “Automated technique for coronary artery disease characterization and classification using dd-dtdwt in ultrasound images,” _Biomedical Signal Processing and Control,”_ , vol. 40, pp. 324–334,.
  * [8] S. Raj and K. Ray, “Sparse representation of ecg signals for automated recognition of cardiac arrhythmias,” _Expert Systems with Applications_ , vol. 105, pp. 49–64,.
  * [9] P. Chazal, M. O’Dwyer, and R. Reilly, “Automatic classification of heartbeats using ecg morphology and heartbeat interval features,” _IEEE transactions on biomedical engineering_ , vol. 51, no. 7, pp. 1196–1206,.
  * [10] S. Osowski, L. Hoai, and T. Markiewicz, “Support vector machine-based expert system for reliable heartbeat recognition,” _IEEE transactions on biomedical engineering_ , vol. 51, no. 4, pp. 582–58,.
  * [11] E. Alickovic and A. Subasi, “Effect of multiscale pca de-noising in ecg beat classification for diagnosis of cardiovascular diseases,” _Circuits, Systems, and Signal Processing_ , vol. 34, no. 2, pp. 513–533,.
  * [12] H. Li, D. Yuan, X. Ma, D. Cui, and L. Cao, “Genetic algorithm for the optimization of features and neural networks in ecg signals classification,” _Scientific reports_ , vol. 7, pp. 41 011,.
  * [13] F. Elhaj, N. Salim, A. Harris, T. Swee, and T. Ahmed, “Arrhythmia recognition and classification using combined linear and nonlinear features of ecg signals,” _Computer methods and programs in biomedicine_ , vol. 127, pp. 52–63,.
  * [14] T. Ince, S. Kiranyaz, and M. Gabbouj, “A generic and robust system for automated patient-specific classification of ecg signals,” _IEEE Transactions on Biomedical Engineering_ , vol. 56, no. 5, pp. 1415–1426,.
  * [15] T. Jun, H. Park, N. Minh, D. Kim, and Y. Kim, “Premature ventricular contraction beat detection with deep neural networks,” in _15th IEEE International Conference on Machine Learning and Applications (ICMLA_ , pp. 859–864 ,.
  * [16] U. Acharya, H. Fujita, O. Lih, Y. Hagiwara, J. Tan, and M. Adam, “Automated detection of arrhythmias using different intervals of tachycardia ecg segments with convolutional neural network,” _Information sciences_ , vol. 405, pp. 81–90,.
  * [17] J. Tan, Y. Hagiwara, W. Pang, I. Lim, S. Oh, M. Adam, and U. Acharya, “Application of stacked convolutional and long short-term memory network for accurate identification of cad ecg signals,” _Computers in biology and medicine_ , vol. 94, pp. 19–26,.
  * [18] S. Kiranyaz, T. Ince, and M. Gabbouj, “Real-time patient-specific ecg classification by 1-d convolutional neural networks,” _IEEE Transactions on Biomedical Engineering_ , vol. 63, no. 3, pp. 664–675,.
  * [19] A. Mostayed, J. Luo, X. Shu, and W. Wee, “Classification of 12-lead ecg signals with bi-directional lstm network,” arXiv preprint arXiv: 1811.02090, 2018.
  * [20] C. Zhang, G. Wang, J. Zhao, P. Gao, J. Lin, and H. Yang, “Patient-specific ecg classification based on recurrent neural networks and clustering technique,” in _13th IASTED International Conference on Biomedical Engineering (BioMed_ , pp. 63–67 ,.
  * [21] D. Li, J. Zhang, Q. Zhang, and X. Wei, “Classification of ecg signals based on 1d convolution neural network,” in _IEEE 19th International Conference on e-Health Networking, Applications and Services (Healthcom_ , pp. 1–6 ,.
  * [22] U. Acharya, H. Fujita, S. Oh, Y. Hagiwara, J. Tan, and M. Adam, “Application of deep convolutional neural network for automated detection of myocardial infarction using ecg signals,” _Information Sciences_ , vol. 415, pp. 190–198,.
  * [23] T. Jun, H. Nguyen, D. Kang, D. Kim, D. Kim, and Y. Kim, “Ecg arrhythmia classification using a 2-d convolutional neural network,” arXiv preprint arXiv: 1804.06812, 2018.
  * [24] S. Xu, M. Mak, and C. Cheung, “Towards end-to-end ecg classification with raw signal extraction and deep neural networks,” _IEEE journal of biomedical and health informatics_.
  * [25] J. Huang, B. Chen, B. Yao, and W. He, “Ecg arrhythmia classification using stft-based spectrogram and convolutional neural network,” _IEEE Access_ , vol. 7, pp. 92 871–92 880,.
  * [26] [Online]. Available: https://physionet.org/content/ptbdb/1.0.0/
  * [27] B. Singh and A. Tiwari, “Optimal selection of wavelet basis function applied to ecg signal denoising,” _Digital signal processing_ , vol. 16, no. 3, pp. 275–287,.
  * [28] J. Pan and W. Tompkins, “A real-time qrs detection algorithm,” _IEEE Trans. Biomed. Eng_ , vol. 32, no. 3, pp. 230–236,.
  * [29] A. Jain, K. Nandakumar, and A. Ross, “Score normalization in multimodal biometric systems,” _Pattern recognition_ , vol. 38, no. 12, pp. 2270–2285,.
  * [30] R. Duda, P. Hart, and D. Stork, _Pattern classification_. John Wiley & Son.
  * [31] M. Kumar, R. Pachori, and U. Acharya, “Automated diagnosis of myocardial infarction ecg signals using sample entropy in flexible analytic wavelet transform framework,” _Entropy_ , vol. 19, no. 9, pp. 488,.
  * [32] A. Lodhi, A. Qureshi, U. Sharif, and Z. Ashiq, “A novel approach using voting from ecg leads to detect myocardial infarction,” in _Proceedings of SAI Intelligent Systems Conference_. Cham: Springer, p. 337–352.
  * [33] U. Baloglu, M. Talo, O. Yildirim, R. San Tan, and U. Acharya, “Classification of myocardial infarction with multi-lead ecg signals and deep cnn,” _Pattern Recognition Letters_ , vol. 122, pp. 23–30,.
  * [34] G. Zhang, “Automated detection of myocardial infarction using a gramian angular field and principal component analysis network,” _IEEE Access_ , vol. 7, pp. 171 570–171 583,.


# Show Me the Whole World: Towards Entire Item Space Exploration for
Interactive Personalized Recommendations

Yu Song<EMAIL_ADDRESS>Huazhong University of Science and
TechnologyWuhanChina ,  Jianxun Lian<EMAIL_ADDRESS>Microsoft
Research AsiaBeijingChina ,  Shuai Sun<EMAIL_ADDRESS>Huazhong University
of Science and TechnologyWuhanChina ,  Hong Huang<EMAIL_ADDRESS>Huazhong University of Science and TechnologyWuhanChina ,  Yu Li
<EMAIL_ADDRESS>Meituan GroupBeijingChina ,  Hai Jin<EMAIL_ADDRESS>Huazhong University of Science and TechnologyWuhanChina and  Xing Xie
<EMAIL_ADDRESS>Microsoft Research AsiaBeijingChina

(2018)

###### Abstract.

User interest exploration is an important and challenging topic in recommender
systems, which alleviates the closed-loop effects between recommendation
models and user-item interactions. Contextual bandit (CB) algorithms strive to
make a good trade-off between exploration and exploitation so that users’
potential interests have chances to expose. However, classical CB algorithms
can only be applied to a small, sampled item set (usually hundreds), which
forces the typical applications in recommender systems limited to candidate
post-ranking, homepage top item ranking, ad creative selection, or online
model selection (A/B test).

In this paper, we introduce two simple but effective hierarchical CB
algorithms to make a classical CB model (such as LinUCB and Thompson Sampling)
capable to explore users’ interest in the entire item space without limiting
to a small item set. We first construct a hierarchy item tree via a bottom-up
clustering algorithm to organize items in a coarse-to-fine manner. Then we
propose a hierarchical CB (HCB) algorithm to explore users’ interest on the
hierarchy tree. HCB takes the exploration problem as a series of decision-
making processes, where the goal is to find a path from the root to a leaf
node, and the feedback will be back-propagated to all the nodes in the path.
We further propose a progressive hierarchical CB (pHCB) algorithm, which
progressively extends visible nodes which reach a confidence level for
exploration, to avoid misleading actions on upper-level nodes in the
sequential decision-making process. Extensive experiments on two public
recommendation datasets demonstrate the effectiveness and flexibility of our
methods.

Recommender System, Contextual Bandit, Interest Exploration

††copyright: acmcopyright††journalyear: 2018††doi:
10.1145/1122445.1122456††conference: Woodstock ’18: ACM Symposium on Neural
Gaze Detection; June 03–05, 2018; Woodstock, NY††booktitle: Woodstock ’18: ACM
Symposium on Neural Gaze Detection, June 03–05, 2018, Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Information systems Recommender
systems††ccs: Computing methodologies Sequential decision making

##  1\. Introduction

Recommender systems help users to easily find their favorite items from
massive candidates. Typically, recommender models, such as collaborative
filtering (Koren et al., 2009) and DeepFM (Guo et al., 2017), exploit users’
historical behaviors to learn users’ preference for future recommendations.
Recommender systems with only exploitation models usually suffer from closed-
loop effects (Jadidinejad et al., 2020): users mostly only interact with the
items recommended by the system; the system further consolidates users’
profiles with their interacted items recommended by the deployed model.
Therefore, as time goes on, the system will be biased to a small, exposed set
of interests for each user and keep recommending a limited range of items to a
same user.

Contextual multi-armed bandit algorithms, such as LinUCB (Li et al., 2010),
are classical methods that leverage side information to provide a good trade-
off between exploration and exploitation, so that the closed-loop effect can
be alleviated. Items are treated as arms and the recommender model is treated
as an agent. Basically, at each round, the agent chooses one arm which has the
biggest potential from $K$ arm candidates, then receives a corresponding
reward based on user-item interaction. The goal is to maximize the cumulative
reward over $T$ rounds. However, these algorithms hold a premise that $K$ is
small, so enumerating all arm candidates’ scores and pick up the best one is
feasible. The premise is true for a few scenarios where the candidates are
naturally small, for example, homepage breaking news ranking, ads creative
ranking and online model selection. In the scenario of general recommender
systems, to fully explore users’ potential interests and truly alleviate the
closed-loop effect, the arms candidates are the entire item repository, which
usually contains millions or even billions of items. Classical bandit methods
become infeasible due to the high computation cost of enumerating every one of
the arms.

To address the challenge, we first propose a generic hierarchical contextual
bandit (HCB) algorithm to efficiently explore the interests of users for
large-scale recommendation scenarios. Tree structure are widely employed to
partition the search space to reduce the computational cost (Jain et al.,
2016; Prabhu and Varma, 2014; Zhu et al., 2018; Zhuo et al., 2020). HCB uses a
tree structure as the index for coarse-to-fine retrieval. For example, in
e-commerce scenario, “Apparel ¿ Clothing ¿ Women’s Clothing ¿ Dresses” is a
path from general apparel to women’s dresses. Instead of using the category
taxonomy of items, we utilize a bottom-up clustering method on item embeddings
to organize items as a hierarchy tree, on which each node contains a group of
semantically similar items. As a result, the number of items associated to
each node on the hierarchy tree can be balanced, and users’ collaborative
behaviors (such as co-click relations) can be encoded to form the hierarchy
tree. HCB leverages the hierarchical information and turns the interest
exploration problem into a series of decision-making problems. Starting from
the root of the tree, on each non-leaf node, HCB performs a bandit algorithm
among the children arms to choose a child node until a leaf node is reached.
Afterward, another bandit algorithm is responsible for recommending an item
from the leaf node to the user and collect her feedback as reward. The reward
will be back-propagated along the path to adjust the estimation of users’
interest towards the hierarchy tree.

The process of HCB is like a depth-first search (DFS) idea. However, selecting
a path in this DFS manner may cause new uncertainties, especially for a deep
tree. First, if the selection of the parent node is misleading, all the
subsequent choices will be impacted, which we call the error propagation.
Second, since user interests are usually diverse, it is possible that the user
is interested in many child nodes located in different parts of the tree.
Therefore, we further propose a progressive HCB (pHCB) algorithm to reduce
uncertainties and enhance the capacity of recommendation. Like the process of
breadth-first search (BFS), pHCB explores items in an adaptive top-down
manner. On the one hand, it gradually maintains a limited number of nodes as a
receptive field. If one node has been explored multiple times and the user’s
interest on this node has been verified, the node’s children nodes will be
included to the receptive filed while the current node will be removed. On the
other hand, pHCB learns user interests of different aspects by performing a
bandit algorithm with visible nodes in the receptive field as arms.
Consequently, the pHCB avoids greedily selecting only one node at each level
to improve the HCB. To summarize, we make the following contributions:

  * $\bullet$

We highlight the importance of exploring users’ interests in the entire item
space to truly alleviate the closed-loop effect in personalized recommender
systems. To the best of our knowledge, it is the first attempt to implement CB
models on millions of items.

  * $\bullet$

Two simple yet effective algorithms, i.e. HCB and pHCB, are proposed to
explore potential interests of users efficiently through a hierarchy item
tree.

  * $\bullet$

We conduct experiments on two large-scale recommendation datasets. Results
show the superiority of HCB and pHCB over baselines, as well as the
flexibility to integrate with different exploration methods such as LinUCB,
Thompson Sampling and $\epsilon$-greedy. In addition, we design an experiment
to verify that thanks to the exploring mechanism, both HCB and pHCB can
effectively alleviate the closed-loop effects in recommender systems and learn
better user profiles in the long term.

##  2\. Related Work

It is the first work to study entire space user interest exploration. Our work
is relevant to two lines of research, and we will review them separately.

###  2.1. Contextual Bandit Algorithms

Contextual bandit algorithms aims to seek a balance between exploration and
exploitation, which have been used in several applications, such as
recommender systems (Mary et al., 2015), dynamic pricing (Misra et al., 2019),
quantitative finance (Shen et al., 2015) and so on. (Bouneffouf and Rish,
2019) reviews the existing practical applications of contextual bandit
algorithms. By assuming the payoff model is linear, LinUCB (Li et al., 2010)
and Thompson Sampling (Agrawal and Goyal, 2013) and two representative methods
for solving contextual bandit problems. Beyond them, a variety of algorithms
have been proposed to optimize the performance or learning speed. For example,
ConUCB (Zhang et al., 2020) introduces conversations between the agent and
users to ask whether the user is interested in a certain topic occasionally.
HATCH (Yang et al., 2020a) considers the resource consumption of exploration
and proposes a strategy to conduct bandit exploration with budget limitation.
S-MAB (Fouché et al., 2019) considers two aspects, one is to maximize the
cumulative rewards and the other is to decide how many arms to be pulled so as
to reduce the exploration cost. GRC (Wu et al., 2020a) develops a graph
regularized cross model to leverage the non-linearity of neural networks for
better estimating the rewards. Different from them, our work commits to
efficiently explore user interests in the entire space, rather than from a
small subset of items.

###  2.2. Cluster-of-Bandit Algorithms

In the past few years, cluster-of-bandit algorithms have attracted the
attention of some scholars. Generally, cluster-of-bandit algorithms aim to
model the dependency since the items or users are always related to each
other. As a result, cluster-of-bandit algorithms achieve better cumulative
rewards than traditional contextual bandit algorithms due to knowledge
sharing. For example, CLUB (Gentile et al., 2014), DYNUCB (Nguyen and Lauw,
2014), CAB (Gentile et al., 2017) and COFIBA (Li et al., 2016) assign users
with similar interests into a same subset to make decisions together, thus it
make contributions to accelerate the learning speed. Different from them, this
paper focus on modeling the item dependency. ICTRTS and ICTRUCB (Wang et al.,
2018b) explicitly model the item dependencies via clustering of arms, but they
are only designed for context-free bandits. Similarly, (Pandey et al., 2007)
uses a taxonomy structure to exploit arm dependencies with context-free
bandits. Considering that context-free bandits cannot utilize the abundant
side information for making decisions, their exploration ability has yet to be
improved. HMAB (Wang et al., 2018a) leverages a tree-structured hierarchy
constructed by domain experts to design a hierarchical multi-armed bandit
algorithm for online IT ticket automation recommendation. However, domain
knowledge is hard to collect and HMAB can not be applied to large-scale
recommender systems because it needs to traverse all the paths in the tree.
Moreover, HMAB aims to learn latent parameters for the nodes in the hierarchy
tree, which is totally different from our goal of exploring users’ latent
interests. Distributed bandit algorithms, such as DCCB (Korda et al., 2016)
and DistCLUB (Mahadik et al., 2020), aim to speed up the computation by
distributing the workloads in parallel. However, these methods do not address
the issue of searching from tremendous items, the computational cost is still
too expensive for responding users’ requests in an online manner (for example,
how to response 100 users’ concurrent requests within 10 milliseconds in a
scenario involving one million items). In summary, compared with existing
cluster-of-bandit algorithms, our HCB and pHCB algorithms leverage a bottom-up
clustering method to build a hierarchical tree of items, then explore users’
potential interests in the entire space of items based on the item hierarchy.

Table 1. A collection of notations Notation |  Description
---|---
$\mathcal{U}$ |  User set, $\mathcal{U}$ = $\\{u^{(1)},u^{(2)},\cdots,u^{(M)}\\}$
$\mathcal{A}$ |  Arm set, $\mathcal{A}$ = $\\{a^{(1)},a^{(2)},\cdots,a^{(K)}\\}$
$\mathcal{I}$ |  Item set, $\mathcal{I}$ = $\\{i^{(1)},i^{(2)},\cdots,i^{(N)}\\}$
$\mathcal{H}$ |  The hierarchy tree for item set partition.
$Ch(n)$ |  The set of child nodes of node $n$
$Pa(n)$ |  The parent node of node $n$
$I(n)$ |  The set of items mounted on node $n$
$\mathcal{V}_{u}(t)$ |  The receptive field of user $u$ at the $t$-th round
$\bm{X}_{a}$ |  The (static) embedding features of arm $a$, $\bm{X}_{a}\in\mathbb{R}^{d\times 1}$
$\eta$ |  The Gaussian noise of reward, $\eta\sim\mathcal{N}(0,\sigma^{2})$
$i_{\pi}(t)$ |  The selected arm by policy $\pi$ at the $t$-th round
$r_{\pi}(t)$ |  Reward of policy $\pi$ at the $t$-th round
$\bm{\theta}_{u}$, $\bm{\theta}_{u}^{(l)}$ |  Learnable parameter of user $u$. A superscript indicates the user parameter is for arms at level $l$ on $\mathcal{H}$. $\bm{\theta}_{u}$ , $\bm{\theta}_{u}^{(l)}$ $\in\mathbb{R}^{d\times 1}$

##  3\. Preliminary and problem

We start by introducing the multi-armed bandit algorithms and the motivations
of this paper. For better readability, we summarize most of the notations used
throughout the paper in Table 1.

###  3.1. UCB for Recommender Systems

The recommender system is regarded as an agent, where there are $M$ users and
$N$ items. At each round $t=1,2,\cdots,T$ of interactions, given a user $u$,
the agent recommends an item $i_{\pi}(t)$ to the user according a policy
$\pi$. Then the agent receives a feedback $r_{\pi}(t)$ from the user, for
example, if the user clicks on the item $i_{\pi}(t)$, $r_{\pi}(t)$ is 1 and
otherwise it is 0. The optimal policy is denoted by $\pi^{*}$. The goal is to
learn a good policy $\pi$, so that the cumulative regret over $T$ rounds,
which is defined as below, is minimized:

(1) $\bm{R}(T)=\sum_{t=1}^{T}(\bm{E}[r_{\pi^{*}}(t)]-\bm{E}[r_{\pi}(t)])$

In practice, due to the absence of the optimal policy $\pi^{*}$, we maximize
the cumulative reward $\sum_{t=1}^{T}\bm{E}[r_{\pi}(t)]$ instead, because
maximizing cumulative reward equals to minimizing cumulative regret (Li et
al., 2016; Wang et al., 2018a; Yang et al., 2020b).

At the core of bandit algorithms is to find an optimal trade-off between
exploitation (to recommend fully based on user profiles learned from user
interaction history) and exploration (find out the new items which user may
potentially love better), so that users diverse new interests have a certain
chance to expose, meanwhile the system won’t waste too many resources on items
that users are not interested in. Let’s consider the (user-centric) LinUCB (Li
et al., 2010) algorithm. Each item is regarded as an arm. At $t$-th round,
when receiving a user visit request, the agent selects an arm $a_{\pi}(t)$ by:

(2)
$a_{\pi}(t)=\operatorname*{arg\,max}_{a\in\mathcal{A}_{t}}R_{a}(t)+C_{a}(t)$

The policy $\pi$ of LinUCB is a linear function between the feature vector
$\bm{x}_{a}$ and user hidden parameter $\theta_{u}$, where the estimated
reward is $R_{a}(t)=\bm{\theta}_{u}^{T}\bm{x}_{a}+{\eta}$, $\eta$ is a
Gaussian random variable representing environmental noise, whose mean is zero
and variance is $\sigma^{2}\leq 1$, The upper bound $C_{a}(t)$ measures the
uncertainty of the reward estimation. The key point lies in how to determine
the parameter $\bm{\theta}_{u}$ and the upper bound $C_{a}(t)$. With LinUCB,
we have:

(3)
$\bm{\theta}_{u}={\left({\bm{D}_{t}}^{T}\bm{D}_{t}+{I}_{d}\right)}^{-1}{\bm{D}_{t}}^{T}\bm{r}_{t}$
(4)
$C_{a}(t)=\alpha\sqrt{\bm{x}_{a}^{T}(\bm{D}_{t}^{T}\bm{D}_{t}+\bm{I}_{d})^{-1}\bm{x}_{a}}$

where $\bm{D}_{t}\in\mathbb{R}^{t\times d}$ is the matrix of interacted arms’
features up to time $t$, $\alpha$ is a hyper-parameter to control the
probability that the bound $C_{a}(t)$ holds, $\bm{r}_{t}\in\mathbb{R}^{t}$ is
the user response vector up to time $t$.

###  3.2. The Challenges

However, as revealed in Eq.(2), LinUCB needs to enumerate and calculate the
score for every arm and then select the best one. In a modern recommender
system, the number of items is usually very large (millions or even billions),
which makes it impossible to calculate scores for all item. Thus, in the
research community, a typical setting for existing literature is to randomly
sample a small number $K$ (such as 50) arms from the entire $N$ arms at time
$t$, and perform LinUCB on this small arm set $\mathcal{A}_{t}$; in industry,
the bandit algorithms can only be applied to scenarios whose candidate pool is
small, such as post-ranking stage of a recommender system, homepage most
popular item ranking, ad creative ranking, etc. We argue that in order to
fully explore users’ potential interest, it is better to place the bandit
module in the item retrieval stage (aka the recall stage) of a recommender
system, where the candidate pool is the entire item set. Otherwise, in the
post-ranking stage of a recommender system, the candidates are actually
proposed by recommendation models and are strongly related to users’ past
behaviors. Thus, it is less meaningful to explore users’ interest in the
latter stages of a recommender system. To fully alleviate the closed-loop
effect, in this paper, we advocate to explore users’ interest in the entire
space of item repository. However, to the best of our knowledge, there is no
work studying how to make the bandit algorithm like LinUCB fit for a large
candidate set.

To address the challenge, we propose to use a tree structure to partition the
entire item space into multiple sub-spaces and build the hierarchical
dependencies among items, to accelerate the exploration. Formally, we define
the Framework 1:

######  Framework 1.

Tree-based Exploration The entire item set can be organized as a hierarchical
tree structure $\mathcal{H}$, where nodes are linked to a subset of items that
share some common topics or user interests, and nodes moving from top to
bottom reflects the topics/interests partition being coarse-to-fine. During
the tree-based exploration, we will first select a node according to some
mechanism, then select an item from the candidates linked to this node. The
user feedback on the selected item will not only update the item-wise user
preference estimation, but also update the node-wise user preference
estimation along the hierarchical path.

##  4\. Methodology

###  4.1. Tree Structure Construction

The tree structure plays a significant role in designing hierarchical bandit
algorithms. Item category taxonomy can serve as the hierarchy tree. However,
due to the imbalanced number of items under different category and lack of
leveraging of users’ collective behaviors, simply using the category taxonomy
may lead to suboptimal performance, which is verified in Section 5. In view of
this, we first learn item embeddings based on item content and user co-click
behaviors, then design a bottom-up clustering method based on K-Means
clustering algorithm (Likas et al., 2003) to form a hierarchy tree for
modeling dependencies among items.

Specifically, to construct a tree structure with $L$ levels, at first, $N$
items are clustered into $k_{L}$ different subsets based on the similarity of
item embeddings. We treat each subset as a new node on the tree, with an
embedding vector being the average of all item embeddings belonging to this
node. Afterward, these $k_{L}$ nodes will be further clustered into $k_{L-1}$
different subsets using K-Means and each subset will be treated as a new node
on the tree, forming a parent-children relation. This step will be repeated
several times until the depth of the tree structure researches $L$. As a
result, the constructed tree structure, denoted by $\mathcal{H}$, contains
$\\{k_{0},k_{1},k_{2},\cdots,k_{L}\\}$ nodes at each level, where $k_{0}=1$
because only a root node appears at the first level. Intuitively, items within
the same node are more similar to each other, thus the clustering results
reflect the dependencies among items. In $\mathcal{H}$, only the root node
does not have parent node, and leaf nodes have no children nodes.

###  4.2. Hierarchical Contextual Bandit

In this section, we introduce the proposed hierarchical contextual bandit
(HCB) algorithm, which empowers a base bandit model to explore over the entire
space of item repository. Our algorithm can be generalized to different bandit
models, without loss of generality, we take LinUCB as the base model to
explain the algorithm for clarity.

There are two types of arms: nodes on the hierarchy tree $\mathcal{H}$ and
items mounted to the leaf nodes. Each node on $\mathcal{H}$ represents a
certain group of items. The feature vector of a leaf node is the average
pooling of items mounted to it, and a non-leaf node’s feature vector is the
average pooling of its children nodes’ feature vectors. The HCB algorithm
makes decisions sequentially, starting from the root node to a leaf node. At
any non-leaf node $n^{(l)}(t)$ at $l$-th level, the policy $\pi$ selects one
of the child nodes from $Ch(n^{(l)}(t))$ by assuming the expected reward of an
arm is linear in its feature vector, which is
${\bm{\theta}_{u}^{(l)}}^{T}\bm{X}_{n}$, and ${\bm{\theta}_{u}^{(l)}}$ is the
latent parameters of a given user $u$ towards the nodes at level $l$,
${\bm{D}^{(l)}}\in\mathrm{R}^{m\times d}$ is the matrix comprised of
interacted items at $l$-th level, each row of ${\bm{D}^{(l)}}$ represents an
item’s feature vector. Applying ridge regression to the training samples to
estimate the coefficients, we have:

(5)
$\bm{\theta}_{u}^{(l)}={\left({\bm{D}^{(l)}}^{T}\bm{D}^{(l)}+\bm{I}\right)}^{-1}{\bm{D}^{(l)}}^{T}\bm{r}^{l}$

Where $\bm{I}$ is an identity matrix and $\bm{r}^{l}$ is the vector of
historical rewards at node level $l$. LinUCB also considers confidence
interval to better estimate the arm payoff. Let
${\bm{A}^{(l)}}={\bm{D}^{(l)}}^{T}{\bm{D}^{(l)}}+\bm{I}$. According to (Walsh
et al., 2009), with probability $1-\delta$, the upper bound is:

(6)
$\left|{\bm{\theta}_{u}^{(l)}}^{T}\bm{X}_{n}-\bm{E}[r_{\pi^{*}}|\bm{X}_{n}]\right|\leq\alpha\sqrt{\bm{X}_{n}^{T}{\bm{A}^{(l)}}^{-1}\bm{X}_{n}}$

for any $\delta>0$ and $\alpha=1+\sqrt{\ln(2/\delta)/2}$. In this way, the
LinUCB algorithm tends to select an arm with:

(7) $\displaystyle n^{(l+1)}(t)=\operatorname*{arg\,max}_{n\in
Ch(n^{(l)}(t))}\left({\bm{\theta}_{u}^{(l)}}^{T}\bm{X}_{n}+\alpha\sqrt{\bm{X}_{n}^{T}{\bm{A}^{(l)}}^{-1}\bm{X}_{n}}\right)$

If policy $\pi$ recommends $i_{\pi}(t)$ to a given user and receives the
reward $r_{\pi}(t)$, similar as (Zhu et al., 2018), then each node on
$Path(root\to n^{(L)}(t))$ also receives the same reward $r_{\pi}(t)$.
Therefore, the rewards of all selected nodes can be obtained, we can update
the learnable parameters $\\{\bm{\theta}_{u}^{(0)}$, $\bm{\theta}_{u}^{(1)}$,
$\bm{\theta}_{u}^{(2)}$, $\cdots$, $\bm{\theta}_{u}^{(L)}\\}$ at each level
(where $\bm{\theta}_{u}^{(0)}$ means the parameter towards item arms, the
other $\bm{\theta}_{u}^{(*)}$ means parameters towards node arms), which can
be formulated as:

(8)
$\displaystyle\bm{A}^{(l)}\leftarrow\bm{A}^{(l)}+\bm{X}^{(l)}{\bm{X}^{(l)}}^{T}$
$\displaystyle\bm{b}^{(l)}\leftarrow\bm{b}^{(l)}+r_{\pi}(t)\bm{X}^{(l)}$
$\displaystyle\bm{\theta}_{u}^{(l)}\leftarrow{\bm{A}^{(l)}}^{-1}\bm{b}^{(l)}$

Where $\bm{A}^{(l)}$ and $\bm{b}^{(l)}$ are initialized as $d$-dimensional
identity matrix and zero vector respectively. $\bm{X}^{(l)}$ is the contextual
embedding of the selected node at $l$-th level.

Input: The tree structure $\mathcal{H}$ with depth as $L$, the total number of
rounds $T$, hyper-parameter $\alpha$.

Output: The policy $\pi$.

1 Initialize parameters of $\pi$;

2 for  _t = 1, 2, $\cdots$ ,T_ do

3 receive a user $u$;

4 set current node as the root of $\mathcal{H}$;

5 for  _l = 1, 2, $\cdots$, L-1_ do

6 select a child node from current node with Eq. (7);

7 set current node as the selected child node;

8

9 end for

10 select an item from the set of items of current (leaf) node to user $u$
with Eq. (2);

11 receive the reward from user $u$;

12 propagate rewards to all nodes in the path;

13 according to Eq. (8), update parameters of $\pi$;

14

15 end for

Algorithm 1 The pseudo-code of HCB algorithm Figure 1. An illustration of HCB.
The policy selects a path { A, C, I, P } from root to a certain leaf node.

The pseudo-code of HCB is provided in Algorithm 1. To illustrate HCB, we offer
a toy example shown in Figure 1. It has three layers in the hierarchy tree.
The agent makes three decisions sequentially, and finally select the path {
$A,C,I,P$ }. Then the agent will launch another bandit selection among the
items mounted to the leaf node $P$. The reward on the selected item will
impact the parameter estimation on the hierarchy tree
$\\{\bm{\theta}_{u}^{(0)}$, $\bm{\theta}_{u}^{(1)}$, $\bm{\theta}_{u}^{(2)}$,
$\bm{\theta}_{u}^{(3)}\\}$, by updating the reward history $\bm{r}^{(*)}$ and
interaction history ${\bm{D}^{(*)}}$.

###  4.3. Progressive Hierarchical Contextual Bandit

The HCB learns the interests of each user via a sequential decision-making
processes and always select the item from the arriving leaf node, which may
lead to two problems: (1) the decisions made in upper levels severely impact
the scope of lower-level nodes. Once the policy makes a bad decision at a
certain level, the rest selections are all sub-optimal. The issue is
especially true when the tree hierarchy is deeper. We call this phenomenon
error propagation; (2) Users may be interested in more than one child node,
thus the greedy selection may fail to capture the comprehensive interests of
users. Therefore, we further propose a progressive hierarchical contextual
bandit (pHCB) algorithm for exploration in another manner on the tree. The
main idea is that the policy continuously expands the receptive field from top
to bottom according to the feedback obtained from historical exploration. We
first give a definition of receptive field as follows.

######  Definition 1.

Receptive field is a personalized set of nodes representing the current
potential interests for each user to explore. At the first round, the
receptive field only consists of the root node (or is set with prior
knowledge). With the exploration process progressing, the receptive field will
be expanded (and reduced) when predetermined conditions are met in an adaptive
top-down manner. The nodes in the receptive field are called visible nodes.

In HCB, only the leaf node is associated with a set of items. In contrast, in
pHCB we allow the policy to select a non-leaf node and then recommend an item
from the item set associated with the non-leaf node. Hence, we have the
Definition. 2 to define the item set of each non-leaf node.

######  Definition 2.

Given a non-leaf node $n$ and the set of child nodes $Ch(n)$, the item set of
node $n$ will be the union of item sets of the nodes in $Ch(n)$, that is
$I(n)=I(n_{c}^{(1)})\cup I(n_{c}^{(2)})\cup\cdots\cup I(n_{c}^{(k)})$ and
$Ch(n)=\\{n_{c}^{(1)},n_{c}^{(2)},\cdots,n_{c}^{(k)}\\}$.

At $t$-th round, the agent faces a user $u$ whose receptive field is denoted
as $\mathcal{V}_{u}(t)$. pHCB algorithm treats each node in
$\mathcal{V}_{u}(t)$ as an arm, and selects the arm (denoted as $n(t)$) with
highest estimated reward according to Eq. (2). Then another LinUCB algorithm
is used to select one item $i_{\pi}(t)$ from the selected $I(n(t))$ and
collect the feedback from the user. pHCB directly selects an arm from the
receptive field without performing sequential decision-making processes, which
avoids the aforementioned concerns of HCB.

Here we offer an example in Figure 2 for illustrating the expanding process.
Assuming at round $T_{a}$, the receptive field of the user $u$ consists of
three nodes: $B$, $C$ and $D$. In the next several rounds, if node $C$ is
selected multiple times and received several positive rewards, making it meet
the conditions of expansion, its children nodes $G,H,I$ will then be added
into the receptive field to replace $C$. As a result, at round $T_{b}$, the
receptive field includes nodes $B,D,G,H,I$. In this way, pHCB expands the
receptive field from coarse to fine and gradually discovers the interests of
users.

A critical mechanism of pHCB is how to expand the receptive field. Since the
tree nodes are organized in different granularity, the nodes at top levels
represent the coarse interests of users while the nodes at bottom levels
depict specific interests of users. We want the receptive field be able to
quickly converge to the leaf nodes, thus we set the expansion conditions as
follows: for a non-leaf node $n$ at the $l$-th level of $\mathcal{H}$, if (1)
it has been selected at least $\lfloor q\dot{\log}{l}\rfloor$ times, and
meanwhile (2) the average reward on this node is larger than $p\dot{\log}{l}$
($0\leq p\leq 1$), then we expand the receptive filed by replacing it with its
children. $q$ and $p$ are hyper-parameters. The $\log{l}$ means that the nodes
at a top-level are easier to be expanded than those at a low level. One can
also design more flexible rules for expansion according to the actual
application scenario. Overall, the pseudo-code of the pHCB is available in
Algorithm 2.

Input: The tree structure $\mathcal{H}$ with depth as $L$, the total number of
rounds $T$, the original receptive field $\mathcal{V}(0)$, hyper-parameters
$\alpha$, $p$ and $q$.

Output: The policy $\pi$.

1 Initialize parameters of $\pi$;

2 for  _t = 1, 2, $\cdots$ ,T_ do

3 receive a user $u$;

4 select a node $n$ from current receptive field $\mathcal{V}_{u}(t)$;

5 select an item from $I(n)$ to user $u$ with Eq. (2);

6 receive the reward from user $u$;

7 if  _node $n$ satisfies the expansion conditions_ then

8 add the nodes in $Ch(n)$ into the receptive field to replace node $n$;

9 end if

10 update parameters of $\pi$;

11

12 end for

Algorithm 2 The pseudo-code of pHCB algorithm Figure 2. An illustration of
pHCB. At round $T_{a}$, the receptive field consists of nodes B, C and D;
After several trials, at round $T_{b}$, node C meets the conditions of
expansion, so the receptive field changes to nodes B, D, G, H and I

###  4.4. Regret Analysis

As defined in Eq. (1), the regret is defined as the difference between the
expected reward under hindsight knowledge and the actual reward under the
algorithm. The regret bound we would like to obtain is established on a
premise that the clustering structure is known to the algorithm ahead of time,
which is consistent with the scenario of this paper. In this case, each
cluster is viewed as an independent arm, according to (Auer, 2002; Abbasi-
Yadkori et al., 2011; Chu et al., 2011), the regret bound is up to logarithmic
terms $\ln(T)$, $\ln(N)$, and $\ln(1/\delta)$. By hiding the logarithmic
factors with notation $\widetilde{\mathcal{O}}$, the cumulative regret over
$T$ rounds is bounded with probability $1-\delta$ as:

(9) $R(T)=\widetilde{\mathcal{O}}\left(\sum_{k=1}^{K}(\sigma
d+||\bm{X}_{k}||\sqrt{d})\sqrt{T}\right)$

In Eq. (9), we shall assume that $||\bm{X}_{k}||=1$ for all clusters
111Without loss of generality, we can conduct $l_{2}$ normalization over the
contextual vector associated with each arm.. Then as proven by (Gentile et
al., 2014), one can replace $\sqrt{T}$ of each arm by a term formulated as
$\sqrt{T}(\frac{1}{K}+\sqrt{\frac{|V_{k}|}{N}})$, where $|V_{k}|$ is the size
of $k$-th cluster and $N$ is the total number of items. As a result, the
regret bound becomes:

(10) $R(T)=\widetilde{\mathcal{O}}\left((\sigma
d+\sqrt{d})\sqrt{T}\left(1+\sum_{k=1}^{K}\sqrt{\frac{|V_{k}|}{N}}\right)\right)$

In Eq. (10), according to (Gentile et al., 2014), the worst case occurs when
each cluster has the same size $\frac{N}{K}$, leading to the regret bound:

(11) $R(T)=\widetilde{\mathcal{O}}\left((\sigma d+\sqrt{d})\sqrt{KT}\right)$

Here we first discuss the regret bound for HCB. For simplicity, we assume that
the number of clusters are reduced $m$ times that of the previous level. At
the beginning, each item is treated as a cluster, i.e. the number of clusters
should be $N$. In this case, the regret bound holds
$\widetilde{\mathcal{O}}\left((\sigma d+\sqrt{d})\log_{m}(N)\sqrt{mT}\right)$.
For pHCB, the receptive field expands in a progressive manner, assuming the
final size of receptive field is $r$, the regret bound is at most
$\widetilde{\mathcal{O}}\left((\sigma d+\sqrt{d})\sqrt{rT}\right)$. As proven
in (Chu et al., 2011), if the arm set is fixed over time and contains $N$
arms, the regret bound of the contextual bandits with linear payoff functions
is up to $\mathcal{O}(\sqrt{Td}{\ln}^{3/2}(NT\ln(T)/\delta)))$. It is
significantly larger than the regret bound of HCB and pHCB due to the higher
order of logarithmic terms and $d\ll N$, $m\ll N$ and $r\ll N$ in most
instances. Therefore, our proposed algorithms can improve the exploration
efficiency substantially by reducing the cumulative regret. Moreover, the
exploration time complexity is reduced from $\mathcal{O}(N)$ to
$\mathcal{O}(\log(N))$ with the help of hierarchy.

##  5\. Experiments

###  5.1. Experimental Settings

####  5.1.1. Datasets

We perform experiments on two public recommendation benchmark datasets, basic
statistics are shown in Table 2.

  * $\bullet$

MIND222https://msnews.github.io/index.html (Wu et al., 2020b): The MIND
dataset is the largest public benchmark dataset for news recommendations so
far, which is constructed from the click logs of Microsoft News. We use
Sentence BERT (Reimers et al., 2019) to train news embeddings from their
contents, and adopt a GRU (Okura et al., 2017) as the user model to fine-tune
news embeddings from the sequence of click logs.

  * $\bullet$

Taobao333https://tianchi.aliyun.com/dataset/dataDetail?dataId=649&userId=1:
The Taobao dataset is constructed from user behaviors of Taobao for E-commerce
recommendations. Similar to MIND dataset, we also utilize GRU to learn item
embeddings from the sequence of user behavior logs.

Table 2. Overview of Datasets Dataset | #users | #items | # categories | # interactions
---|---|---|---|---
MIND | 1,000,000 | 161,013 | 285 | 24,155,470
Taobao | 987,994 | 4,162,024 | 9,439 | 100,150,807

####  5.1.2. Baselines

We compare the proposed algorithms against the following related and
competitive bandit algorithms:

  * $\bullet$

LinUCB (Li et al., 2010) is a classical contextual bandit algorithm. It only
works with item-level recommendation.

  * $\bullet$

HMAB (Wang et al., 2018a) organizes arms into hierarchy tree purely by domain
knowledge. It utilizes category information to model the dependencies among
items. Then the algorithm selects a path from root node to a leaf node, and
the leaf node is an item.

  * $\bullet$

ICTRUCB (Wang et al., 2018b) formulates the item dependencies as the clusters
on arms. Different from our methods, it does not consider the hierarchy.

  * $\bullet$

ConUCB (Zhang et al., 2020) utilizes key-terms to organize items into
different subsets to represent dependencies among items. The algorithm
occasional conversation with users and leverages conversational feedbacks on
key-terms from users to accelerate the speed of bandit learning.

####  5.1.3. Our Methods and Variants

Our goal is to propose a generic algorithm that can empower different bandit
models to be more effective on large-scale item set exploration. Therefore,
our main experiments contain two groups: first, with LinUCB as the base bandit
model, to compare our algorithms (i.e., HUCB and pHUCB) with the
aforementioned baselines (because most of the listed baselines are based on
LinUCB); second, with three different base bandit models, including LinUCB,
Thompson Sampling (TS) (Agrawal and Goyal, 2013), and $\epsilon$-greedy, to
verify whether our algorithms are effective under different settings. In the
second group of experiments, we also compare two variants of our models:

  * $\bullet$

CB-Category: It borrows the idea from HMAB (Wang et al., 2018a) by using the
prior knowledge, i.e. the category taxonomy, to assign items into different
subsets. Each subset will be treated as an arm, the policy first selects a
subset and then recommends an item from the subset to users with a base bandit
algorithm.

  * $\bullet$

CB-Leaf: It is a variant of ICTRUCB (Wang et al., 2018b). Since the ICTRUCB is
designed for context-free bandits, to keep a fair comparison, we also utilize
K-Means clustering on item embeddings to assign items into different subsets.
Here, we treat the leaf nodes of $\mathcal{H}$ as the clustering results. Each
leaf node will be treated as an arm, the policy first selects a leaf node and
then recommends an item from the node to users with a base bandit algorithm.

Here, CB- can take a value from { LinUCB, Thompson Sampling (TS), and
$\epsilon$-greedy }, our experiments are separated into three groups. For
example, if the CB- model is LinUCB, then the involved variants are LinUCB-
Category, LinUCB-Leaf, and our final models are HUCB and pHUCB. For all
models, including our proposed ones and baselines, we set the maximum times of
score-computing per round to 50 for a fair comparison. For example, in LinUCB,
if the number of arm candidates is 1000, then originally we need to compute
1000 scores per round to select the best one in estimation, which exceeds our
budget, so we will randomly sample 50 arms from the 1000 arms and then perform
the LinUCB on the small set. For hierarchical CB methods, the budget is evenly
distributed to each level, e.g., for pHCB, we have two levels of bandit, then
each level will get a budget of 25.

####  5.1.4. Evaluation

We evaluate the performance of different bandit algorithms with off-policy
user simulator evaluation. To reduce the biases of the simulation, we utilize
the IPS estimator (Schnabel et al., 2016; Huang et al., 2020; Saito et al.,
2020), which is a standard method used for off-policy evaluation of bandit
algorithms 444https://groups.google.com/g/open-bandit-project. IPS learns to
re-weigh the training samples by the propensity score to learn an unbiased
simulator. The simulator is trained on the whole data to make the best use of
information. This evaluation enables us to compare the performance of
candidate hypothetical policies without expensive online A/B tests.
Specifically, the simulator learns the unbiased embeddings of users and items,
and the reward of a user $u$ towards an item $i$ is derived from the inner
product of their embeddings.

####  5.1.5. Reproducibility

For MIND dataset, each item is represented by a 64-dimensional embedding
vector. The dataset has been split for training/validation/test, only the
click logs of the training set is used for learning item embeddings and
building tree structures. The users without history logs or impression logs
are removed. The click is treated as positive feedback and non-click is
treated as negative feedback. The hierarchy tree structure is set to { 1, 100,
10000 }, which means there is 10000 leaf nodes, and only one layer of non-leaf
nodes. For Taobao dataset, each item is represented by a 32-dimensional
embedding vector. As the same method does in (Zhu et al., 2018), we remove the
users who have less than 10 behaviors or the items appearing less than 10
times. We randomly select 10000 users for testing and 1000 users for
validation, and the behavior logs of the rest users are used for learning item
embeddings. The click is treated as positive feedback and the negative
feedback is generated via negativing sampling. The hierarchy tree structure is
set to { 1, 50, 5000, 50000 }, so that number of items mounted to a leaf node
is less than 100.

For the LinUCB-based algorithms, all learnable parameters are initialized as
all zero matrices or vectors, and the hyper-parameter $\alpha$ is set as 0.5.
The Gaussian prior is used to design Thompson Sampling-based algorithms for
contextual bandit. For $\epsilon$-greedy-based algorithms, the $\epsilon$ is
set as 0.05. With the help of validation set, the hyper-parameters $q$ and $p$
of pHCB and its variants are set as 10 and 0.1 respectively. Follow the
setting in (Zhang et al., 2020), we consider a general configuration in which
at each round, the computational cost is limited as 50. Note here the arms can
be nodes or items depending on different bandit algorithms. The learning rate
for training GRU is 0.001, the hidden size is the same as the embedding size,
and optimizing with Adam optimizer (Kingma and Ba, 2014). All algorithms are
implemented with Python and PyTorch, and repeated 10 times to report the
average performance. The code and processed datasets will be released after
acceptance of the paper for easy reproducibility.

Table 3. Cumulative rewards of different algorithms Dataset | MIND | TaoBao
---|---|---
Round | 100 | 1000 | 2000 | 100 | 1000 | 2000
LinUCB | 4.76 | 158.41 | 357.91 | 10.70 | 106.12 | 212.26
HMAB | 4.41 | 217.40 | 520.97 | 10.74 | 120.89 | 255.22
ICTRUCB | 5.60 | 300.83 | 709.05 | 10.98 | 135.99 | 290.33
ConUCB | 7.47 | 188.50 | 409.23 | 13.04 | 273.86 | 584.84
HUCB | 7.48 | 407.82 | 918.38 | 16.20 | 320.68 | 699.29
pHUCB | 7.93 | 419.74 | 866.60 | 16.51 | 391.36 | 806.66

(a) MIND, LinUCB (b) MIND, Thompson Sampling (c) MIND, $\epsilon$-greedy (d)
Taobao, LinUCB

(e) Taobao, Thompson Sampling (f) Taobao, $\epsilon$-greedy

Figure 3. Cumulative rewards of our algorithms and variants based on LinUCB,
Thompson Sampling and $\epsilon$-greedy, on the MIND dataset and Taobao
dataset, respectively.

###  5.2. Experimental Results

####  5.2.1. Comparison with Baselines

Since all baseline algorithms are on the basis of LinUCB, we also choose
LinUCB as the base algorithm for HCB and pHCB to keep a fair comparison. Note
that HCB and pHCB can work with different base algorithms, and we discuss
their generality in sec. 5.2.2. We compare the cumulative rewards over
100/1000/2000 rounds555Considering that the two datasets have different number
of users and items, for better alignment, here we denote round as one pass of
all users receiving one recommended item. of different algorithms in Table 3,
and the best results are presented in bold. As can be seen, our proposed
algorithms, HUCB and pHUCB, outperform all baselines across different datasets
consistently at different rounds, and pHUCB is generally better than HCB. For
example, on the largest TaoBao dataset, At 100/1000/2000 rounds, the
performance of pHUCB was improved by 54.3%, 268.7%, and 280% compared with
LinUCB, respectively. Although HMAB, ICTRUCB, and ConUCB achieve higher
cumulative rewards over LinUCB, there is still a considerable gap between
these algorithms and ours. The superiority of pHUCB over HUCB further verifies
that by expanding the receptive field in a progressive manner, the pHCB
algorithm is able to better discover the comprehensive interests of users.

####  5.2.2. Flexibility and Variants Study

Next, we report the cumulative reward of our algorithms and their variants, in
Figure 3, based on three different base bandit algorithms. From the
experimental results, we have the following observations.

  * $\bullet$

Constructing item dependencies in the form of clusters indeed helps a lot in
accelerating the exploration. This can be verified from that both our
algorihtms (HCB and pHCB) and their variants (CB-category and CB-Leaf)
outperform the corresponding base bandit model.

  * $\bullet$

HCB and pHCB achieve the highest cumulative rewards on both two datasets in
most of the cases, indicating that the proposed hierarchical algorithms are
effective. As we can see, the performance of baseline algorithms has a
noticeable gap between our proposed algorithms. This result is reasonable
since our proposed methods introduce the hierarchy knowledge to take the item
dependencies into consideration, which greatly improves the efficiency of
exploration. Although the two variants, such as CB-Category and CB-Leaf, also
organize items into different clusters, they fail to model the coarse-to-fine
item dependencies as tree structures. Apart from that, the pHCB algorithm
beats other methods, which verifies that the progressive exploration can
adaptively discover the diverse interests of users with a receptive field.

  * $\bullet$

Our algorithms have strong flexibility. We have tested the performance with
base models varying in { LinUCB, Thompson Sampling, $\epsilon$-greedy }, the
conclusions are consistent, which proves our proposed frameworks can well
generalize to various bandit algorithms.

####  5.2.3. Parameter Sensitivity

In this subsection, we study the impacts of hyper-parameters. Since the pHCB
performs best in most of the cases, we particularly study the key hyper-
parameter of it, i.e., $q$ and $p$, which control the expansion conditions:
$q$ determines the number of trails at one arm and $p$ indicates the threshold
of average reward for expanding child nodes. To study their impacts, we take
pHUCB as an example and vary $q$ from $\\{0,5,10,15,20,25\\}$ and $p$ from
$\\{0,0.05,0.1,0.15,0.2,0.25\\}$ to see how the final rewards (at round 1000)
will be affected.

As shown in Figure 4, different hyper-parameters have a noticeable influence
on the cumulative reward of pHUCB algorithm over 1000 rounds. For MIND
dataset, if $q$ is too small or $p$ is too large, the cumulative rewards
become worse since the former makes the expansion conditions unreliable and
the latter makes the receptive field difficult to expand. As for the Taobao
dataset, the trend of impacts caused by $q$ is similar to the MIND dataset.
Meanwhile, the model is less sensitive with parameter $p$. Overall, from
Figure 4 we learn that a suggested configuration is $p=0.1$ and $q=10$.

(a) MIND (b) Taobao

Figure 4. Effect of hyper-parameters of pHUCB.

####  5.2.4. Alleviate Closed-Loop Effects

Typically, recommender models trained from historical logs are designed for
exploitation purposes, here we called them exploitation models. Such
recommendation systems often suffer from closed-loop effects (Jadidinejad et
al., 2020) because they only learn users’ interests from historical logs, but
they do not have the ability to explore new interests of users. In contrast,
the contextual bandit algorithms are more effective to break the information
cocoons with exploration strategies. In order to verify that our model is able
to explore the potential interests of users thus alleviate the closed-loop
effects, we design an additional experiment as follows.

We select three exploitation models, i.e., Linear model, GRU, and Transformers
(Sun et al., 2019) as baselines. These exploitation models are first pre-
trained by the historical logs of existing users to get the deployed models.
Then, we use exploitation models as well as our proposed models as ”deployed
models” to serve users. Specifically, in this stage, for each new user (whose
logs are not used in the first pre-trained stage), we randomly sample only
three clicked items as visible historical logs for generating her initial user
embedding with a deployed model. Then we can recommend two hundred items to
the user with a deployed model and collect the user’s feedback. Note here the
user embedding will be refreshed once the model receives positive feedback.
This stage is performed for every deployed model respectively. The third stage
is about evaluating the quality of impression logs produced by the deployed
models. We utilize the collected historical logs together with all the rest
historical logs of existing users (which are used in the first stage) as
training samples to train an evaluating model (here we use the matrix
factorization (MF) model as the evaluating model, each user and item will be
mapped to an embedding vector. MF-based collaborative filtering method is one
of the most popular models for personalized recommendations) and evaluate the
trained model on the same test samples for a fair comparison. In order to
prove the advantages of our bandit algorithms in exploring user interests, we
select two hundred of test users with the most diversified interests as new
users: we calculate the Gini impurity (Loh, 2011) of the historical items
clicked by the user according to the category of items. Obviously, the larger
the Gini impurity, the more diverse the interests of the user. The users of
the training set are treated as existing users.

Table 4. Test LogLoss and AUC of different algorithms Dataset | MIND | TaoBao
---|---|---
Method | LogLoss | AUC | LogLoss | AUC
Linear |  1.679±0.005 |  0.703±0.005 |  0.693±0.001 |  0.530±0.001
GRU |  1.759±0.004 |  0.686±0.003 |  0.688±0.001 |  0.535±0.002
Transformer |  1.377±0.008 |  0.695±0.006 |  0.683±0.001 |  0.546±0.001
HUCB | 0.681±0.004 | 0.720±0.003 | 0.660±0.001 | 0.649±0.002
pHUCB | 0.680±0.005 | 0.723±0.002 | 0.661±0.002 | 0.647±0.003

We report the test log loss (LogLoss) and area under curve (AUC) score in
Table 4. We can observe that both our methods, HUCB and pHUCB, achieve much
higher performance than exploitation models including the Linear model, GRU,
and Transformers, which demonstrates that our proposed models can effectively
help to alleviate the closed-loop effects in recommender systems.

##  6\. Conclusion

In this paper, we propose a general hierarchical bandit framework for entire
space user interest exploration. Specifically, we design two algorithms, i.e.,
HCB and pHCB. The HCB algorithm makes a sequence of decision-making tasks to
find a path from the root to a leaf node, while the pHCB progressively expands
the receptive field in a top-down manner to explore the user interests, which
is more flexible and also achieves more satisfactory results. Extensive
experiments are conducted to demonstrate the effectiveness of the proposed
framework on two real-world datasets with three different base bandit
algorithms. In the future, we plan to combine our methods with the start-of-
the-art deep learning methods to estimate reward for making more reasonable
decisions. Moreover, we assume the items are static in this paper by fixing
the tree structure unchanged. It would be interesting to extend the proposed
frameworks to the non-static setting, which has not been well studied yet.

## References

  * (1)
  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. 2011.  Improved algorithms for linear stochastic bandits. In _Proceedings of the 24th International Conference on Neural Information Processing Systems_. 2312–2320.
  * Agrawal and Goyal (2013) Shipra Agrawal and Navin Goyal. 2013.  Thompson Sampling for Contextual Bandits with Linear Payoffs. In _International Conference on Machine Learning_. 127–135.
  * Auer (2002) Peter Auer. 2002\.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ 3, Nov (2002), 397–422.
  * Bouneffouf and Rish (2019) Djallel Bouneffouf and Irina Rish. 2019.  A survey on practical applications of multi-armed and contextual bandits.  _arXiv preprint arXiv:1904.10040_ (2019).
  * Chu et al. (2011) Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. 2011\.  Contextual bandits with linear payoff functions. In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_. JMLR Workshop and Conference Proceedings, 208–214.
  * Fouché et al. (2019) Edouard Fouché, Junpei Komiyama, and Klemens Böhm. 2019\.  Scaling multi-armed bandit algorithms. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1449–1459.
  * Gentile et al. (2017) Claudio Gentile, Shuai Li, Purushottam Kar, Alexandros Karatzoglou, Giovanni Zappella, and Evans Etrue. 2017.  On context-dependent clustering of bandits. In _International Conference on Machine Learning_. PMLR, 1253–1262.
  * Gentile et al. (2014) Claudio Gentile, Shuai Li, and Giovanni Zappella. 2014\.  Online clustering of bandits. In _International Conference on Machine Learning_. 757–765.
  * Guo et al. (2017) Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017.  DeepFM: A Factorization-Machine Based Neural Network for CTR Prediction. In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ _(IJCAI’17)_. AAAI Press, 1725–1731.
  * Huang et al. (2020) Jin Huang, Harrie Oosterhuis, Maarten de Rijke, and Herke van Hoof. 2020.  Keeping Dataset Biases out of the Simulation: A Debiased Simulator for Reinforcement Learning based Recommender Systems. In _Fourteenth ACM Conference on Recommender Systems_. 190–199.
  * Jadidinejad et al. (2020) Amir H Jadidinejad, Craig Macdonald, and Iadh Ounis. 2020\.  Using Exploration to Alleviate Closed Loop Effects in Recommender Systems. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 2025–2028.
  * Jain et al. (2016) Himanshu Jain, Yashoteja Prabhu, and Manik Varma. 2016\.  Extreme multi-label loss functions for recommendation, tagging, ranking & other missing label applications. In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. 935–944.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Korda et al. (2016) Nathan Korda, Balazs Szorenyi, and Shuai Li. 2016\.  Distributed clustering of linear bandits in peer to peer networks. In _International conference on machine learning_. PMLR, 1301–1309.
  * Koren et al. (2009) Yehuda Koren, Robert Bell, and Chris Volinsky. 2009\.  Matrix factorization techniques for recommender systems.  _Computer_ 42, 8 (2009), 30–37.
  * Li et al. (2010) Lihong Li, Wei Chu, John Langford, and Robert E Schapire. 2010\.  A contextual-bandit approach to personalized news article recommendation. In _Proceedings of the 19th international conference on World wide web_. 661–670.
  * Li et al. (2016) Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. 2016\.  Collaborative filtering bandits. In _Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval_. 539–548.
  * Likas et al. (2003) Aristidis Likas, Nikos Vlassis, and Jakob J Verbeek. 2003\.  The global k-means clustering algorithm.  _Pattern recognition_ 36, 2 (2003), 451–461.
  * Loh (2011) Wei-Yin Loh. 2011\.  Classification and regression trees.  _Wiley interdisciplinary reviews: data mining and knowledge discovery_ 1, 1 (2011), 14–23.
  * Mahadik et al. (2020) Kanak Mahadik, Qingyun Wu, Shuai Li, and Amit Sabne. 2020\.  Fast distributed bandits for online recommendation systems. In _Proceedings of the 34th ACM International Conference on Supercomputing_. 1–13.
  * Mary et al. (2015) Jérémie Mary, Romaric Gaudel, and Philippe Preux. 2015\.  Bandits and recommender systems. In _International Workshop on Machine Learning, Optimization and Big Data_. Springer, 325–336.
  * Misra et al. (2019) Kanishka Misra, Eric M Schwartz, and Jacob Abernethy. 2019\.  Dynamic online pricing with incomplete information using multiarmed bandit experiments.  _Marketing Science_ 38, 2 (2019), 226–252.
  * Nguyen and Lauw (2014) Trong T Nguyen and Hady W Lauw. 2014.  Dynamic clustering of contextual multi-armed bandits. In _Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management_. 1959–1962.
  * Okura et al. (2017) Shumpei Okura, Yukihiro Tagami, Shingo Ono, and Akira Tajima. 2017\.  Embedding-based news recommendation for millions of users. In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. 1933–1942.
  * Pandey et al. (2007) Sandeep Pandey, Deepak Agarwal, Deepayan Chakrabarti, and Vanja Josifovski. 2007.  Bandits for taxonomies: A model-based approach. In _Proceedings of the 2007 SIAM International Conference on Data Mining_. SIAM, 216–227.
  * Prabhu and Varma (2014) Yashoteja Prabhu and Manik Varma. 2014.  Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning. In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_. 263–272.
  * Reimers et al. (2019) Nils Reimers, Iryna Gurevych, Nils Reimers, Iryna Gurevych, Nandan Thakur, Nils Reimers, Johannes Daxenberger, and Iryna Gurevych. 2019.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics.
  * Saito et al. (2020) Yuta Saito, Shunsuke Aihara, Megumi Matsutani, and Yusuke Narita. 2020.  A Large-scale Open Dataset for Bandit Algorithms.  _arXiv preprint arXiv:2008.07146_ (2020).
  * Schnabel et al. (2016) Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. 2016\.  Recommendations as treatments: Debiasing learning and evaluation. In _international conference on machine learning_. PMLR, 1670–1679.
  * Shen et al. (2015) Weiwei Shen, Jun Wang, Yu-Gang Jiang, and Hongyuan Zha. 2015\.  Portfolio choices with orthogonal bandit learning. In _Twenty-fourth international joint conference on artificial intelligence_.
  * Sun et al. (2019) Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. 2019.  BERT4Rec: Sequential recommendation with bidirectional encoder representations from transformer. In _Proceedings of the 28th ACM international conference on information and knowledge management_. 1441–1450.
  * Walsh et al. (2009) Thomas J Walsh, István Szita, Carlos Diuk, and Michael L Littman. 2009.  Exploring compact reinforcement-learning representations with linear regression. In _Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence_. 591–598.
  * Wang et al. (2018a) Qing Wang, Tao Li, SS Iyengar, Larisa Shwartz, and Genady Ya Grabarnik. 2018a.  Online it ticket automation recommendation using hierarchical multi-armed bandit algorithms. In _Proceedings of the 2018 SIAM International Conference on Data Mining_. SIAM, 657–665.
  * Wang et al. (2018b) Qing Wang, Chunqiu Zeng, Wubai Zhou, Tao Li, S Sitharama Iyengar, Larisa Shwartz, and Genady Ya Grabarnik. 2018b.  Online interactive collaborative filtering using multi-armed bandit with dependent arms.  _IEEE Transactions on Knowledge and Data Engineering_ 31, 8 (2018), 1569–1580.
  * Wu et al. (2020b) Fangzhao Wu, Ying Qiao, Jiun-Hung Chen, Chuhan Wu, Tao Qi, Jianxun Lian, Danyang Liu, Xing Xie, Jianfeng Gao, Winnie Wu, et al. 2020b.  Mind: A large-scale dataset for news recommendation. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. 3597–3606.
  * Wu et al. (2020a) Xian Wu, Suleyman Cetintas, Deguang Kong, Miao Lu, Jian Yang, and Nitesh Chawla. 2020a.  Learning from Cross-Modal Behavior Dynamics with Graph-Regularized Neural Contextual Bandit. In _Proceedings of The Web Conference 2020_. 995–1005.
  * Yang et al. (2020b) Liu Yang, Bo Liu, Leyu Lin, Feng Xia, Kai Chen, and Qiang Yang. 2020b.  Exploring Clustering of Bandits for Online Recommendation System. In _Fourteenth ACM Conference on Recommender Systems_. 120–129.
  * Yang et al. (2020a) Mengyue Yang, Qingyang Li, Zhiwei Qin, and Jieping Ye. 2020a.  Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation. In _Proceedings of The Web Conference 2020_. 292–302.
  * Zhang et al. (2020) Xiaoying Zhang, Hong Xie, Hang Li, and John CS Lui. 2020\.  Conversational contextual bandit: Algorithm and application. In _Proceedings of The Web Conference 2020_. 662–672.
  * Zhu et al. (2018) Han Zhu, Xiang Li, Pengye Zhang, Guozheng Li, Jie He, Han Li, and Kun Gai. 2018.  Learning tree-based deep model for recommender systems. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1079–1088.
  * Zhuo et al. (2020) Jingwei Zhuo, Ziru Xu, Wei Dai, Han Zhu, Han Li, Jian Xu, and Kun Gai. 2020\.  Learning Optimal Tree Models under Beam Search. In _International Conference on Machine Learning_. PMLR, 11650–11659.