# Multimodal contrastive learning for diagnosing cardiovascular diseases from
electrocardiography (ECG) signals and patient metadata

Tue M. Cao
VinUni-Illinois Smart Health Center, VinUniversity
Hanoi University of Science and Technology
<EMAIL_ADDRESS>
Nhat H. Tran
VinUni-Illinois Smart Health Center, VinUniversity
Hanoi University of Science and Technology
<EMAIL_ADDRESS>
Phi Le Nguyen
School of Information and Communication Technology,
Hanoi University of Science and Technology
<EMAIL_ADDRESS>
Hieu Pham
VinUni-Illinois Smart Health Center,
College of Engineering & Computer Science, VinUniversity
Coordinated Science Laboratory, University of Illinois Urbana-Champaign
<EMAIL_ADDRESS>

##  1 Introduction

This work discusses the use of contrastive learning and deep learning for
diagnosing cardiovascular diseases from electrocardiography (ECG) signals.
While the ECG signals usually contain 12 leads (channels), many healthcare
facilities and devices lack access to all these 12 leads. This raises the
problem of how to use only fewer ECG leads to produce meaningful diagnoses
with high performance. We introduce a simple experiment to test whether
contrastive learning can be applied to this task. More specifically, we added
the similarity between the embedding vectors when the 12 leads signal and the
fewer leads ECG signal to the loss function to bring these representations
closer together. Despite its simplicity, this has been shown to have improved
the performance of diagnosing with all lead combinations, proving the
potential of contrastive learning on this task.

##  2 Problem definition and methods

The missing leads problem is defined in Physionet CinC2020 [1], which requires
competitors to have models that can achieve high performance on predefined
sets of leads. Models tackling this task [10, 4, 6, 9] utilized methods that
focused on training and testing on the same number of leads. Here we approach
this problem differently by trying to achieve higher performance on less
number of leads assuming we have access to all 12 leads ECG with the use of
contrastive learning. Figure 1 illustrates an overview of the experiment we
used to determine whether contrastive learning would work on this task. The
training process is split into two steps. In the first step, we used
InceptionTime [3] \- a powerful 1D-CNN for feature extraction of 12-lead ECGs
in this task. This feature is then concatenated with the encoded metadata
feature before being projected onto the embedding space using a linear layer.
The embedding vectors then go through a MLP (pseudo-classifier) for
classification. In the second step, we froze the weights of the pseudo
classifier from the first step (which maps the vectors from the embedding
space to the predictions) and then trained the model with fewer leads ECG and
a different CNN to project it onto the same embedding space. Notably, in this
step, we bring embedding vectors of missing leads closer to their 12-lead
version using the modified loss function:

$\mathcal{L}=\mathcal{L}_{cls}(y,y^{*})+sim(v^{12},v^{x})\times\alpha$ (1)

Figure 1: Illustration of the proposed approach.

Where $y$ and $y^{*}$ are the prediction and ground truth of the labels,
$v^{12}$ and $v^{x}$ denote the projected embedding vectors of the 12-lead and
its x-lead version (x $\epsilon$ {2,3,4,6}). The $sim$ function here
calculates the similarity between those two vectors and can be the L1, L2 norm
of the difference between these two vectors or the cosine similarity, and
$\alpha$ is a hyperparameter. The prediction of this method is compared to
that of training the model without the first step, freezing the pseudo-
classifier and the custom loss function. Patients’ metadata (weight, height,
age, gender) is encoded using soft label encoding [2, 5].

##  3 Experiments and Results

Our experiment was conducted on the PTB-XL dataset [8], which contains over
21000 12-lead ECG signals, and these samples are 10 seconds long. While the
dataset also provides various tasks, here we focus on the super-diagnostic
classification task. We used validation Macro-AUC as the evaluation metric as
the PTB-XL benchmark paper [7] suggests while following the same train-
validation split as the paper. Table 1 illustrates the experimental results of
various leads combinations with and without the two-step training process
(denoted as pseudo=True and pseudo=False). As can be seen, our method
outperforms the traditional training process for all leads combination.

No. of leads | pseudo = True | pseudo = False
---|---|---
12 | 0.9320 | N/A
6 | 0.9017 | 0.9007
4 | 0.9227 | 0.9218
3 | 0.9213 | 0.9199
2 | 0.9017 | 0.9002
Table 1: Experiment results on the PTB-XL dataset

##  4 Discussions and Conclusion

We showed that contrastive learning can be used in the task of missing leads
ECG classification. Despite its simplicity, the results suggest that by
bringing the missing lead representation closer to that of the complete
signal, diagnostic performance can be improved on all lead combinations. In
the future, we will apply more complex contrastive learning techniques to
improve the model’s performance.

## References

  * [1] E. A. P. Alday, A. Gu, A. J. Shah, C. Robichaux, A.-K. I. Wong, C. Liu, F. Liu, A. B. Rad, A. Elola, S. Seyedi, et al.  Classification of 12-lead ecgs: the physionet/computing in cardiology challenge 2020.  Physiological measurement, 41(12):124003, 2020.
  * [2] G. Cai, Y. Zhu, Y. Wu, X. Jiang, J. Ye, and D. Yang.  A multimodal transformer to fuse images and metadata for skin disease classification.  The Visual Computer, May 2022.
  * [3] H. I. Fawaz, B. Lucas, G. Forestier, C. Pelletier, D. F. Schmidt, J. Weber, G. I. Webb, L. Idoumghar, P. Muller, and F. Petitjean.  Inceptiontime: Finding alexnet for time series classification.  CoRR, abs/1909.04939, 2019.
  * [4] H. Han, S. Park, S. Min, H.-S. Choi, E. Kim, H. Kim, S. Park, J. Kim, J. Park, J. An, K. Lee, W. Jeong, S. Chon, K. Ha, M. Han, and S. Yoon.  Towards high generalization performance on electrocardiogram classification.  In 2021 Computing in Cardiology (CinC), volume 48, pages 1–4, 2021\.
  * [5] W. Li, J. Zhuang, R. Wang, J. Zhang, and W.-S. Zheng.  Fusing metadata and dermoscopy images for skin disease diagnosis.  In 2020 IEEE 17th International Symposium on Biomedical Imaging (ISBI). IEEE, Apr. 2020.
  * [6] P. Nejedly, A. Ivora, R. Smisek, I. Viscor, Z. Koscova, P. Jurak, and F. Plesinger.  Classification of ecg using ensemble of residual cnns with attention mechanism.  In 2021 Computing in Cardiology (CinC), volume 48, pages 1–4, 2021\.
  * [7] N. Strodthoff, P. Wagner, T. Schaeffter, and W. Samek.  Deep learning for ecg analysis: Benchmarks and insights from ptb-xl.  IEEE Journal of Biomedical and Health Informatics, 25(5):1519–1528, 2020.
  * [8] P. Wagner, N. Strodthoff, R.-D. Bousseljot, W. Samek, and T. Schaeffter.  PTB-XL, a large publicly available electrocardiography dataset, 2020\.
  * [9] N. L. Wickramasinghe and M. Athif.  Multi-label cardiac abnormality classification from electrocardiogram using deep convolutional neural networks.  In 2021 Computing in Cardiology (CinC), volume 48, pages 1–4. IEEE, 2021.
  * [10] Z. Xu, Y. Guo, T. Zhao, Y. Zhao, Z. Liu, X. Sun, G. Xie, and Y. Li.  Abnormality classification from electrocardiograms with various lead combinations.  Physiological Measurement, 43(7):074002, 2022.


#  Fake News Data Collection and Classification:
Iterative Query Selection for Opaque Search Engines with Pseudo Relevance
Feedback

Aviad Elyashar, Maor Reuben, and Rami Puzis
Telekom Innovation Laboratories and Department of Software and Information
Systems Engineering,
Ben-Gurion University of the Negev, Beer-Sheva, Israel
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Retrieving information from an online search engine is the first and most
important step in many data mining tasks. Most of the search engines currently
available on the web, including all social media platforms, are black-boxes
(a.k.a opaque) supporting short keyword queries. In these settings, retrieving
all posts and comments discussing a particular news item automatically and at
large scales is a challenging task. In this paper, we propose a method for
generating short keyword queries given a prototype document. The proposed
algorithm interacts with the opaque search engine to iteratively improve the
query. It is evaluated on the Twitter TREC Microblog 2012 and TREC-COVID 2019
datasets showing superior performance compared to state of the art and is
applied to automatically collect large scale dataset for training machine
learning classifiers for fake news detection. The classifiers training on
70,000 labeled news items and more than 61 million associated tweets
automatically collected using the proposed method obtained impressive
performance of AUC and accuracy of 0.92, and 0.86, respectively.

_K_ eywords query selection $\cdot$ opaque search engine $\cdot$ pseudo
relevance feedback $\cdot$ fake news

##  1 Introduction

Every day, millions of people search for information online [1]. Market
researchers search for products related to their product or business [2].
Researchers reviewing the academic literature search for works related to
their current article [3]. Posts and comments that discuss a news item are
retrieved from online social media (OSM) for fake news detection [4]. There
are many similar cases when additional information related to a specific
document is required. We will refer to such a document as a _prototype_.

There are multiple methods for retrieving a set of documents that are similar
to a given prototype from a corpus. Most of these methods represent documents
as vectors and calculate the similarity between the prototype and other
documents. The basic methods are based on TF-IDF (term frequency-inverse
document frequency) and, BM25 which treats each document as a bag-of-words
[5]. Advanced methods, such as Doc2Vec [6], Skip-thoughts [7], Sent2Vec [8],
and others, use neural networks to represent documents as low dimensional
vectors [5]. Once vector representations of documents are available,
retrieving the documents that are most similar to the prototype, i.e., closest
to it in the embedding space, is straightforward.

Retrieval methods that are based on document similarity assume access to the
corpus being searched. This assumption is valid for transparent search
engines, where the repository and the algorithms are known to the user.
However, all the popular search engines, including general purpose search like
Google, or platform specific, such as Twitter search, are opaque providing
very little information about their repositories and algorithms [9]. Other
than Google’s image search, current search engines do not provide document-
based search services. Therefore, we usually resort to the short keyword
queries that are a mainstay of anyone using today’s search engines [10].

Due to the ambiguity of short keyword queries, they often do not reflect the
original intention of the query writer [11]. For example, the keyword “apple,”
may refer to the fruit or to the technology company.111Google and some other
engines use the search context to resolve ambiguity and retrieve documents
that are most relevant for a specific user or case [12]. Other engines, such
as Twitter, do not use contextual information and retrieve all results exactly
matching the specified keywords [13]. Personalization and context aware
information retrieval is out of the scope of this paper.  In this paper, we
focus on the problem of _retrieving documents that are most similar to a given
prototype document from an opaque search engine supporting short keyword
queries_ , such as Twitter. It is possible to manually formulate a search
query from the document’s content [4]. But of course, manual query selection
does not scale. We can use the prototype document’s title to generate queries
[14], or search for its URL if the prototype is a web page [15]. However,
these approaches miss many relevant results. We further discuss the pros and
cons of existing query selection methods in Section 2.

Therefore, in this paper, we suggest a novel iterative approach that selects
queries that maximize the number of retrieved relevant results, using limited
interaction with an opaque search engine. This approach consists of two
components: the _iterative query selection (IQS)_ algorithm and _mean
relevance error (MRE)_ measure. The _IQS_ is a hill climbing algorithm that
iteratively optimizes short keyword queries given a prototype document. The
_MRE_ is used as pseudo relevance feedback, by ranking the results of
incumbent queries generated by the IQS algorithm according to their relevance
to the prototype document. The details of the proposed method are discussed in
Section 3. In the absence of a prototype document, incumbent results are
compared to a set of relevant results according to user relevance feedback. We
evaluated the proposed methods on TREC 2012 Microblog benchmark and TREC-COVID
2019 datasets assuming relevance feedback (see Section 4) In addition, we
evaluate the _IQS_ and _MRE_ in pseudo relevance feedback settings using
manually labeled fake news Twitter dataset (see Section 5.2) and retrieve a
large scale fake news dataset from Twitter to be used toward training fake
news classifiers (see Section 5).

The contributions of this paper are:

  * •

We discuss the _mean relevance error (MRE)_ (see Section 3.1), a measure that
can be used for pseudo relevance feedback when a prototype document is
provided.

  * •

We propose an automated mechanism for optimizing short keyword queries termed
_iterative query selection (IQS)_ (see Section 3.2). The IQS outperforms
existing opaque relevance feedback search on Twitter TREC Microblog 2012 and
on TREC-COVID 2019 datasets (see Section 4.3).

  * •

We present two _Fake News_ datasets:222Datasets are publicly available as a
collection of Twitter IDs in the following link: https://bit.ly/2vd58u6 (1) 20
news items and 1,076 associated tweets all of which are manually curated (see
Section 5.2); and (2) 70,018 news items and approximately 61 million
associated tweets automatically collected using the proposed IQS method (see
Section 5.3.1).

  * •

We demonstrate the quality of the automatically retrieved Fake News dataset
through the fake news detection task using well-known supervised machine
learning with AUC333Area Under the Receiver Operating Characteristic Curve of
0.92 and accuracy of 0.86 (see Section 5.3.2).

##  2 Related Work

This paper describes a new approach for selecting the best queries engaging
with opaque search engines. In the next sections, we elaborate on the methods
that are associated with the query selection. Next, for the demonstration of
fake news detection use cases, we provide the necessary background for this
domain.

###  2.1 Query Selection for Transparent Search Engines

Query selection is the task of selecting the most suitable queries for
extracting relevant documents from web search engines [16]. In most of the
cases, selecting these queries requires reformulation or expansion of an
initial query. Several methods suggest to analyze the underlying corpus of the
given search engine and used this valuable information for expanding the
queries. Dwaipayan et al. [17] selected the most similar terms to a given
query for expansion based on word embedding trained on the corpus. Their idea
was to choose terms that yielded the highest probability for being related to
the current query. Kuzi et al. [18] like Dwaipayan et al. used word embedding
trained on the corpus to select expansion terms and suggested centroid- and
fusion-based terms scoring methods to select them. Xu et al. [19] selected
candidate terms for expansion based on context features, such as TF-IDF and
co-occurrence of the query terms. Afterward, they used the learned term-
ranking models to rank the candidate terms. Pang and Du [20] utilized click-
through data of old queries to choose terms for expansion and which terms from
the initial query to reformulate.

All these approaches require knowledge about the underlying corpus of the
search engine and therefore not suitable for the case of opaque search
engines. Also, their starting point requires an initial query and initial
results that are utilized to expand or reformulate terms. Thus, it is not
possible to use a prototype document in these approaches.

###  2.2 Query Selection for Opaque Search Engines

Since most of the search engines are opaque, some query selection methods
expand or reformulate queries without knowing the documents that exist in the
underlying corpus. For example, Li et al. [21] implemented a double-loop
retrieval system titled ReQ-ReC that consists of a query selection and a
classifier that uses relevance feedback to improve the result iteratively. The
query selection mechanism suggests queries that return relevant results and
the classifier rank obtained results according to their relevance. Another
retrieval system that uses relevance feedback was presented by Makki et al.
[22]. This system titled ATR-Vis is a user-driven visual approach for the
retrieval content from Twitter. ATR-Vis proposes four strategies of active
learning (ambiguous retrieval, near-duplicates, leveraging hashtags,
leveraging replies) to decrease user involvement in the process. Zamani et al.
[23] referred to the task of query expansion as a recommendation task and used
matrix factorization for recommending expansion terms. Another approach for
query reformulation was introduced by Al-Khateeb et al. [24] where the initial
query can be reformulated using a genetic algorithm search. The synonyms of
the query terms are candidates for the reformulation and the fitness function
is based on the similarity between the query to the results. Nogueira and Cho
[25] presented a neural network architecture that reformulates a query to
optimize the number of relevant documents returned. Chy et al. [26] proposed a
query expansion method that selects effective expansion terms using a
learning-to-rank method. The drawback of this method is that it works in a
supervised manner which requires to train a classifier that ranks terms for
the specific search engine before the query selection. Albishre et al.[27]
suggested a system that uses pseudo-relevance feedback and topic-based query
expansion method.

ALMIK is another active retrieval method that tries to achieve both high-
precision and high-recall in collecting event-related tweets [28]. The ALMIK
is composed of a keyword expansion component and an event-related tweet
identification component. In each iteration, the event-related tweet
identification component asks the user to label the most uncertain instances.
Then the keyword expansion component selects the $K$ keywords with the highest
score for keyword expansion. The keyword score is based on keyword relevance,
coverage, and evolvement in the event.

These approaches, except ATR-Vis, require an initial query, as well as initial
retrieved results for selecting a query. The drawback of the ATR-Vis is that
it implemented specifically for the Twitter search engine and requires users
to label the retrieved results (relevance feedback). Opposed to them, our
proposed method uses a pseudo-relevance feedback process (no user-interaction
required) and can be used on any search engine.

###  2.3 Document Similarity

Over the past years, various solutions have been suggested for estimating the
semantic similarity between documents based on lexical matching, handcrafted
patterns, syntactic parse trees, external sources of structured semantic
knowledge and distributional semantics.

In 2015, Kusner et al. [29] proposed the word mover’s distance (WMD), which
measures the dissimilarity between two documents as the minimal sum of
distances that the word vectors of one document need to “move” towards the
word vectors of another document. They evaluated their metric in the context
of KNN classification on eight benchmark document categorization tasks. They
concluded that the the use of WMD lead to the lowest error rates in comparison
to other methods. We use the concept of WMD in the proposed _mean relevance
error (MRE)_ measure, however we expand this metric to deal with a collection
of returned documents associated with a prototype document instead of a single
document as described in [29].

In the same year, Kenter and de Rijke [30] extracted multiple types of meta-
features from the comparison of the word embedding for short text pairs. The
features representing labelled short text pairs were used to train a
supervised learning classifier. Later, they used the trained model for
predicting the semantic similarity of new, unlabelled pairs of short texts.

The dual embedding space model (DESM) proposed by Nalisnick et al. [31]
calculates the average cosine distance of each term in the query with every
centroid representation on the documents using pre-trained word embeddings.
The centroid representation of each document is the mean vector of the
document words.

In 2016, Guo et al. [32] proposed a deep relevance matching model (DRMM) for
determining the relevance of a document given a particular query. The proposed
model employed a joint deep architecture at the query term level for relevance
matching. By using matching histogram mapping, a feed forward matching
network, and a term gating network, they created a machine learning model.
Later, they evaluated their model on two benchmark collections and showed that
their DRMM model can outperformed well-known baseline retrieval models.

In 2017, Mitra et al. [33] suggested a document ranking model composed of two
separate deep neural networks, where the first network matches the query and
the document using a local representation, and the second network matches the
query and the document using learned distributed representations. Next, the
two networks are jointly trained as part of a single neural network. Mitra et
al. showed that this combination performed better than either neural network
individually on a web page ranking task, and significantly outperforms
traditional baselines and other recently proposed models based on neural
networks.

###  2.4 Search Result Diversification

In many cases, queries for search engines can arguably be considered ambiguous
to some extent. Therefore, in order to tackle query ambiguity, search result
diversification approaches have recently been proposed to produce rankings for
satisfying the multiple possible information needs underlying a query [34]. In
most of the cases, the diversification of retrieved results implies a trade-
off between having more relevant results which reflect the true intent of the
user and having less redundancy [35]. There are two prominent diversification
approaches: implicit and explicit. The implicit approaches implicitly assume
that similar documents will cover similar interpretations or aspects
associated with the query and should hence be dismissed, in order to achieve a
diversified ranking. In particular, an implicit aspect representation relies
on features which belong to each document in order to model different aspects,
such as the terms contained by the retrieved documents [36], the clicks they
received [37], their topic models [38], or clusters [39]. With respect to
explicit approaches, a broad topic can be associated with an ambiguous query
can be usually decomposed into its constituent sub-topics. Therefore, we can
explicitly search for different aspects of the query for producing a diverse
ranking of results. In most of the cases, explicit approaches relying on
features derived from the query itself as candidate aspects, such as different
query categories [40] or query reformulations [41].

In this paper, we increase the diversification of the returned documents using
two query expansion methods: adding synonyms based on WordNet and Adding the
$k$ closest words in the embedding space for each candidate word.

###  2.5 Fake News Data Collection Methods

Fake news is a long-lasting problem that has drawn significant attention in
recent years. It has been widely spread within the online social media (OSM)
[42]. Since the detection of fake news is very challenging, many researchers
suggested different approaches to confronting this issue. Many of them were
based on natural language processing [43], investigating the diffusion of news
[15], etc. Also, a few papers have attempted to detect fake news solely using
social context features [44].

In order to train supervised classifiers for fake news detection, a ground
truth dataset containing labeled news items is required. Such news items can
be collected from fact checking websites, such as
Snopes,444https://www.snopes.com/ PolitiFact,555https://www.politifact.com/
FactCheck,666https://www.factcheck.org/ and others [15, 45].

There are two commonly-used methods for collecting relevant posts associated
with a given claim: The first method is to retrieve posts based on the sources
that distributed the claims. For example, Monti et al. [14] used the source’s
headlines that exist in fact-checking websites to collect tweets. Vosoughi et
al. [15] investigated the diffusion of news, based on collected tweets that
contained links to the given claims. However, collecting tweets based on
sources may be incomplete since many posts are associated with the given
claim, but do not contain a link to the claim’s source. Moreover, URL
shortening, quotation, and cross reference common in the press, as well as
among bloggers lead to a situation where tweets mentioning the same news
contain links to different sources. Therefore, collecting tweets only based on
links will result in a subset of the tweets relevant to a claim. In addition,
also the use of the source’s headlines does not always reflect well the
claim’s content (e.g., in the case of clickbait) which can lead to irrelevant
results. These drawbacks limit the ability to collect a quality dataset that
contains enough relevant data for accurate classification.

The second method that people use to collect relevant posts is through the use
of manual query selection. For example, Zhou et al.[4] demonstrated a real-
time news certification system on Sina Weibo777https://www.weibo.com/ using
queries provided by the user to gather related posts. Then, they built an
ensemble model that combined user-based, propagation-based, and content-based
features and evaluated the proposed model on a small dataset of 146 claims.
Jin et al. [46] and Wang et al. [47] developed neural network-based methods
for fake news detection and to evaluate their proposed methods they both used
two small datasets from Sina Weibo (40k tweets) and Twitter (15k tweets on 52
rumor-related events). Those datasets were created using manual query
selection. Selecting queries manually to a large collection of claims requires
a lot of human effort and limits the amount of collected data.

Due to the limitations of both methods described above, it is clear that fake
news detection based on the OSM can benefit from a tool that can automatically
select accurate short keyword queries for a given claim (i.e., a news item).
In this study, we demonstrate the usefulness of the proposed _iterative query
selection (IQS)_ method to retrieve a large scale fake news dataset from
Twitter automatically, as well as train fake news classifiers using social
context features extracted from the tweets.

##  3 Iterative Query Selection with Mean Relevance Error Objective Function

In this paper, we propose a novel iterative approach for optimizing short
keyword queries given a prototype document through interaction with an opaque
search engine. First, we describe the _mean relevance error (MRE)_ , a simple
measure that estimates the relevance of  the results retrieved from an opaque
search engine with respect to a given prototype document. This measure is
calculated by summing the shortest distances between words in the given
prototype document and words in the retrieved results (see Section 3.1). The
lower the MRE, the more relevant the retrieved results are. Second, we outline
the _iterative query selection (IQS)_ algorithm for finding queries that
retrieve results with the lowest _MRE_ score (see Section 3.2).

###  3.1 Mean Relevance Error

In this section, the _mean relevance error (MRE)_ is designed with the purpose
of retrieving microblog entries (e.g., tweets) relevant to a prototype
document, such as a news item.  This suggested measure estimates the minimal
distance between word vector representations of the words existing in the
retrieved result and the prototype document. The MRE is a private case of the
word mover’s distance (WMD) suggested by Kusner et al. [29] since it is the
mean WMD score of an arbitrary number of results. The intuition is that
documents that are close in their semantic space, probably discuss the same
topic.

Let $d$ denote the prototype document and $r$ denote a short document
retrieved using a search engine. The MRE works best when $r$ is shorter than
$d$. The prototype $d$ may be more general than $r$, for example, covering
multiple topics that are not mentioned in $r$. The MRE relies on semantic word
embedding, also known as a low dimensional vector representation of words.
Intuitively, the MRE quantifies the similarity between the words used in the
prototype document and in a retrieved result.

There are many word embedding methods, such as GloVe [48], Word2Vec [49],
fastText [50], etc. We can use any word embedding method, where words with a
similar meaning are embedded close to each other. Let $V$ be the vocabulary of
words embedded in a $n$ dimensional space using either one of the word
embedding approaches. Let $dist(w_{i},w_{j})$ denotes the cosine distance
between the vector representations of two words
($w_{i},w_{j}\in\mathbb{R}^{n}$). The cosine distance is define as
$1-cosineSim(w_{i},w_{j})$. Thus the cosine distance ranges between 0 to 2.

Let $W_{d}=\\{w_{d_{1}},w_{d_{2}},\dots,w_{d_{l}}\\}$ be the set of word
vectors in $d$ and $W_{r}=\\{w_{r_{1}},w_{r_{2}},\dots,w_{r_{k}}\\}$ be the
set of word vectors in $r$. The $W_{d}$ and $W_{r}$ do not contain stop words.
The distance between a word $w$ and a document $d$ is the minimal distance
between the word $w_{i}$ and all the words in $W_{d}$ (see Equation 1).

$dist(w,d)=\min_{w_{d_{j}}\in W_{d}}\\{dist(w,w_{d_{j}})\\}$ (1)

The distance between the word vectors of the word $w_{i}$ and all the words in
$W_{d}$ reflects the the relevance of the word $w_{i}$ in the result document
$r$ to the prototype document. The smaller the distance the higher the
relevance of the word $w_{i}$ to the prototype document $d$.

Given a result document $r$, let relevance error ($RE$) of $r$ with respect to
the prototype document $d$ be the average distance of all words $w_{r_{i}}\in
W_{r}$ to the document $d$ (see Equation 2):

$RE(r,d)=\frac{1}{|W_{r}|}\sum_{w_{r_{i}}\in W_{r}}dist(w_{r_{i}},W_{d})$ (2)

Where $|W_{r}|$ represents the number of words in $W_{r}$ except stop words.
It is important to mention that the stop word removal does not impact the
rationality of the proposed method. However, mutual stop words in the result
and the prototype documents does not indicate that both documents are similar
semantically.

Note that, although the $RE$ is a binary function defined on pairs of
documents, it is not a distance metric. The $RE$ is not symmetric and
$RE(r,d)=0$ does not mean that $r$ and $d$ are equal in any sense. Rather $RE$
is similar to a fuzzy version of set inclusion ($\subseteq$), where
$RE(r,d)=0\implies W_{r}\subseteq W_{d}$. If $r$ contains only words in $d$ or
their synonyms, $RE(r,d)$ will be close to zero. Until this point, the RE
measure is identical to the word mover’s distance presented by Kusner et al.
[29]. In the final step, we set the MRE measure to estimate the relevance of
the results retrieved from an opaque search engine to a given prototype
document. .

Finally, let $R$ be a set of short documents retrieved from a search engine.
We define the $MRE$ as the mean $RE$ of all results $r\in R$ with respect to
the prototype $d$ (see Equation 3):

$MRE(R,d)=\frac{1}{|R|}\sum_{r\in R}RE(r,d)$ (3)

The MRE outputs a score between 0 to 2. The lower the MRE score, the more
relevant the retrieved results $R$ are to the prototype document $d$.

The MRE defined above is designed to measure only one aspect of query
performance, the relevance of the results. Other important aspects, for
example, the number of results, are intentionally not captured by the MRE. The
quality of the MRE is affected by the quality of the underlying word embedding
model. For general purpose query evaluation, it is recommended to use word
embedding models trained on large non-domain specific datasets.

###  3.2 Iterative Query Selection

The proposed _iterative query selection (IQS)_ method is based on a local
search algorithm, which selects the queries that maximize the relevance of the
corresponding results retrieved from an opaque search engine. We use the hill
climbing algorithm [51] since querying the search engine is resource intensive
and we need to find local optimum with only a few iterations [51].

Let $d$ be a prototype document and $W_{d}$ be the set of words in $d$ as in
the previous subsection. $W_{d}$ does not contain stop words. Best practice
(and our preliminary experiments) suggests that $W_{d}$ should contain only
nouns, adjectives, verbs, or numbers. In addition, named entities, e.g.,
“Michael Jordan,” are considered as a single term if they are found in the
vocabulary of the word embedding approach used as the basis for the MRE. We
advise against stemming for query selection.

Let $V_{d}$ denote the vocabulary of terms from which possible queries $q\in
V_{d}$ are selected. $V_{d}$ may be equal $W_{d}$ or expanded using any query
expansion approach. We consider two query expansion methods: (1) Adding
synonyms based on WordNet [52] for each word in $W_{d}$, later referred to as
_Synonyms_. (2) Adding $k$ closest words in the embedding space for each
candidate word in $W_{d}$, later referred to as _KNN_.

The IQS searches through the space of possible queries $q\in V_{d}$. It starts
with a random subset of words from $V_{d}$. For efficiency, the query size is
limited by two control variables $minq$, and $maxq$, which are the minimal and
the maximal number of words in a query. In every iteration, we randomly modify
the query using one of the following three actions:
$\textsc{AddWord}(q,V_{d})$ randomly adds to $q$ a word from $V_{d}$ that is
not yet in $q$. $\textsc{RemoveWord}(q,V_{d})$ removes a random word from the
query $q$ decreasing its size. $\textsc{SwapWords}(q,V_{d})$ exchanges a
random word in $q$ with a random word in $V_{d}$ that was not already in $q$.
Possible actions are chosen to ensure the query size constraints.

After modifying the query $q$ using one of the three actions, we evaluate the
MRE of its results $R_{q}$ from the search engine $se$. Due to computational
and network performance considerations, it is important to limit the number of
results retrieved from $se$ in each iteration of the algorithm. Usually, this
limit further referred to as $rlimit\geq|R_{q}|$, is defined by the search
engine interface and is set to the number of results on a single page. The
larger the $rlimit$ is, the more accurate the $MRE(R_{q},d)$ will be in each
iteration of the IQS. However, the $rlimit$ is also the primary factor
(linearly) affecting the time of an iteration.

The hill climbing IQS algorithm is implemented as described in Algorithm 1. It
receives as an input a prototype document $d$, an opaque search engine $se$,
the maximal and minimal number of words in a query ($maxq$ and $minq$,
respectively), the maximal number of iterations $itr$, and the number of
result documents ($rlimit$) retrieved from $se$ in each iteration. During the
algorithm, we keep only queries that decrease the $MRE$ score. If the query
returns no results, we assume the $MRE(R_{q},d)$ to be the maximal score of 2
and we do not add a word in the next iteration.

The IQS returns an ordered set of queries. Some search engines allow words
from the query to be missing in the results while others retrieve only
documents containing all keywords in the query. Twitter is an example of the
latter, a boolean search engine. In the case of a boolean search engine, it is
important to run multiple slightly modified queries in order to retrieve as
many relevant results as possible. This is the main reason due to which the
IQS returns a list of queries and not only a single best query.

Algorithm 1 Iterative Query Selection

1:procedure BuildQueries($d,se,itr,minq,maxq,rlimit$)

2: $queries\leftarrow$ empty priority queue

3: $V_{d}\leftarrow$ filtered and expanded set of words in $d$

4: $q_{best}\leftarrow$ random subset of $V_{d}$

5: $R_{q_{best}}\leftarrow se(q_{best},rlimit)$

6: calculate $MRE(R_{q_{best}},d)$

7: $q_{new}\leftarrow q_{best}$

8: $R_{q_{new}}\leftarrow R_{q_{best}}$

9: loop $itr$ times

10: $actions=\\{\textsc{AddWord, RemoveWord, SwapWords}\\}$

11: if $|q_{new}|=maxq\vee|R_{q_{new}}|=0$ then remove AddWord from $actions$

12: else if $|q|=minq$ then remove RemoveWord from $actions$

13: $action\leftarrow random(actions)$

14: $q_{new}\leftarrow action(q_{best},V_{d})$

15: $R_{q_{new}}\leftarrow se(q_{new},rlimit)$

16: Using Eq.(3), calculate $MRE(R_{q_{new}},d)$

17: if $MRE(R_{q_{new}},d)<MRE(R_{q_{best}},d)$ then

18: $queries.add(q_{new},MRE(R_{q_{new}},d))$

19: $q_{best}\leftarrow q_{new}$ return $queries$

20:procedure AddWord($q,V_{d}$) return $q\cup random(V_{d}\setminus q)$

21:procedure RemoveWord($q,V_{d}$) return $q\setminus random(q)$

22:procedure SwapWords($q,bow$) return
$\textsc{RemoveWord}(\textsc{AddWord}(q,V_{d}),V_{d})$

##  4 Experiments

In this section, we conducted a series of experiments that evaluate our
iterative query selection (IQS) method. Since IQS required a loss function
that evaluates each generated query, we first measure the ability of the MRE
measure to distinguish between relevant and irrelevant results (see Section
4.2). Then we will examine the MRE performance correlation to informative the
prototype document. After evaluating the MRE, we will examine the performance
of the IQS using the MRE as an active retrieval method for an opaque search
engine (see Section 4.3). Finally, we evaluate the IQS’s ability to find
relevant queries for a prototype document without the user’s help on an opaque
search engine.

###  4.1 Datasets

In the following experiment we used the _Twitter TREC Microblog 2012_ dataset
and the TREC-COVID 2019 dataset. The _Twitter TREC Microblog 2012_ consists of
59 topics (used as initial queries) and 73K judgments (relevant and irrelevant
tweets) for those topics [53]. The TREC-COVID 2019
888https://www.kaggle.com/c/trec-covid-information-retrieval/overview consists
of 35 topics and 20.7K judgments. In this dataset the topics also contain an
initial query, a question, and a search narrative.

###  4.2 The Mean Relevance Error (MRE) Evaluation

The MRE measure purpose in to rank documents relevance according to a
prototype document. However, The Twitter TREC Microblog 2012 dataset and TREC-
COVID 2019 dataset include topic definitions that cannot be used as prototype
documents (initial query), due to their rather short length. Therefore, we
iteratively construct such prototype documents for each topic using a
relevance feedback process. In addition, in this experiment, we examine the
correlation between how informative the prototype document to the relevance of
the results. Note that in the case of TREC-COVID 2019 we can use the search
narrative as a prototype claim which we will discuss in Section 4.4.

####  4.2.1 Experimental Setup

The constructed prototype document should reflect the topic being searched. We
use the following general process to iteratively build a prototype document
for each topic and improve the results retrieved using the RE. First, we use
the initial topic definition as the prototype document. We calculate the RE
between the topic definition and each tweet in the dataset. Although the topic
definition is too short to qualify for a good prototype document, some
relevant tweets can be found using the MRE. Second, we retrieve the top $k$
results and request relevance feedback from a user (or from an oracle if
ground truth is provided for evaluation purposes). Next, we expand the
prototype document using the content of the relevant retrieved results and run
the second step again.

It is important to note that the relevance feedback should be saved to avoid
labeling the same result multiple times. The process stops after $n$ labeled
results for each topic in the dataset (or a user is satisfied with the
results).  In this experiment we set the top $k$ results to 10 and $n$ to be
$300$. For the TREC Microblog 2012 dataset we discard query 76, since it does
not contain any relevant judgments and.

As baselines we use the following: Okapi BM25 [54], latent semantic analysis
(LSA) [55], and TF-IDF. Also, we use the dual embedding space model (DESM)
using the same pre-trained word embeddings used for the RE [31]. In this
comparison we use only unsupervised document similarity measures since our
goal is that the final IQS will run on any search engine without any training.

####  4.2.2 Results & Discussion

The mean average precision (MAP) and R-precision results are summarized in
Table 1. As can be seen, the MRE outperforms other methods evaluated on both
datasets in terms of MAP and R-precision.  These results emphasize the
effectiveness of the MRE of being a good indicator for distinguishing between
relevant and irrelevant documents. This finding strengths the pre-trained word
vectors of being very useful to detect similar words in two documents. This
calculation is automatic and doesn’t require cold start like in case of learn
to rank measures which requires the user to train the ranking measure on the
search engine.

Another impotent aspect we want to examine is the effect of the prototype
document informativeness on the MAP score relative to each relevance measure.
This aspect is impotent because it examines whether the relevance measure
estimates the results’ relevance according to the prototype or not. The
results are presented in Figure 1. The trends in the results show how the MRE
utilizes better the information found in the prototype document to rank the
results. This finding indicates that the MRE is the best candidate as a loss
function for our query selection method.

Figure 1: Performance evaluation of the relevance measures on the Twitter TREC Microblog 2012 and TREC-COVID 2019. | TREC Microblog 2012 | TREC-COVID 2019
---|---|---
Method | MAP | R_Precision | MAP | R_Precision
BM25 | 0.451 | 0.384 | 0.335 | 0.345
LSA | 0.474 | 0.410 | 0.741 | 0.676
DESM | 0.707 | 0.639 | 0.798 | 0.749
TF-IDF | 0.763 | 0.694 | 0.805 | 0.759
MRE | 0.831 | 0.780 | 0.825 | 0.788
Table 1: Evaluation of the relevance measures on the Twitter TREC Microblog
2012 dataset and TREC-COVID 2019 dataset.

###  4.3 Iterative Query Selection with Relevance Feedback

In this experiment, we evaluate the full _iterative query selection (IQS)_
pipeline based on a process that mimics interaction with Twitter’s search
engine. Twitter uses a boolean retrieval model meaning that the returned
results must contain all the words in the query. We assume an opaque search
engine ($se$) and access the corpus through the boolean search only. We used a
boolean retrieval model such as in Twitter since IQS final purpose is to
retrieve relevant data for a fake news classification task from the Twitter
search engine.

####  4.3.1 Experimental Setup

Similarly to the previous experiment, we dynamically construct a prototype
document for each topic using relevance feedback. First, we use the topic
definition as the prototype document. Second, we run the first iteration of
the IQS calculating the MRE score between the prototype document and the
results retrieved. Third, before proceeding to the next iteration of the IQS,
we sort the retrieved results in ascending order, according to their MRE score
(a lower score means greater relevance to the topic). Fourth, we take the top
$k=10$ results and ask a user (or an oracle) to label them. Fifth, we expand
the prototype document using the content of the relevant results identified by
the user (or the oracle) and proceed to the next iteration of IQS. The
stopping condition is the same as in the previous experiment, retrieving
labeling $n=300$ tweets. We set the minimal and maximal number of words in a
query to be between 1 to 6 ($minq=1,maxq=6$).  This parameter influences
directly on the number of retrieved results. In case of a query containing a
single word, many results are expected to be retrieved, however most of them
are not relevant directly to the prototype document. For example, assume that
the prototype document is "Crude oil production in the U.S." and the query
contains the word of oil, solely. In this case, twitter search engine is
expected to retrieve many tweets that include the word in their text, however
they are not related directly to the oil industry in the U.S. (for example,
tweets that focus on oil painting and oil production in Russia). In the same
manner, high number of words decrease the number of retrieved results but most
of these tweets are expected to be relevant to the given prototype document.
Lastly, we set the number of returned result to 20 ($rlimit=20$) to simulate
similar number of retrieved documents from standard search engine within the
Web.

In order to choose the best hyper-parameter for the IQS algorithm, we tested
the following ranges: maximal number of iteration between 10 to 45, number of
runs between 1 to 3, and the number of output queries between 5 to 50. For our
final evaluation, we used the hyper-parameter configuration that yielded the
best results on both datasets. The best parameters found for IQS are
$itr=15,runs=3,minSize=1,maxSize=6,numQueries=40,$.

####  4.3.2 Results & Discussion

We compared the performance of the IQS to the ReQ-ReC implementation on
GitHub999https://github.com/lookatmoon/ReQ-ReC-demo with the same settings:
the top 10 documents are labeled by the user ($k=10$), the algorithm stops
after 300 labels for each topic ($n=300$) and a boolean search engine.

In addition, we run the ALMIK method, a state-of-the-art active retrieval
method proposed by Zheng and Sun [28], on the TREC Microblog 2012 and TREC-
COVID 2019 datasets. We implemented the ALMIK method based on the method
description presented in their paper. Again, we limit the amount of label
request from the user to 300 and use the same search engine mechanism. We also
conducted hyper-parameter tuning for ALMIK in order to achieve the best
results. The best results were achieved when the ALMIK conduct 3 rounds of
active learning phases. Between the phases, we conduct a keyword expansion
phase and used the new results in the next round. In each active learning
phase, we conduct 10 iterations of 10 label request of the most uncertain
tweets from the user (A total of 100 in each active learning phase).

We reported the performance of the IQS, the ReQ-ReC, and the ALMIK all topics
in both datasets Table 2. The proposed IQS method outperformed the ReQ-ReC and
ALMIK in terms of MAP and R-Precision in both datasets. The results show that
the IQS can retrieve more relevant results from a boolean opaque search engine
using relevance feedback given a short initial query.

| TREC Microblog 2012 | TREC-COVID 2019
---|---|---
Method | MAP | R_Precision | MAP | R_Precision
ReQ-ReC | 0.147 | 0.198 | 0.002 | 0.014
ALMIK | 0.164 | 0.172 | 0.288 | 0.336
IQS | 0.357 | 0.356 | 0.508 | 0.507
Table 2: Black box evaluation.

In the above experiments, we used the _vanilla_ IQS without any additional
query expansion methods. Next, we evaluated the IQS with a query expansion
based on WordNet denoted as IQS+Synonyms and the IQS with a query expansion
based on k nearest neighbors in the embedding space, denoted as IQS+KNN. In
addition, we evaluate both query expansion methods together, denoted as
IQS+Synonyms+KNN. All the IQS variations were run using the best hyper-
parameters found ($iter=15,run=3$).

The MAP of the IQS on the Twitter TREC Microblog 2012 dataset for 40 relevance
feedback iterations is presented in Figure 2. All the IQS variations perform
the same or worse then the vanilla implementation. Since we use a local search
algorithm for query reformulation it is expected that when there are more
candidate terms the algorithm require more search iterations to find the most
suitable terms. Since we want to keep a low amount of interactions with the
search engine, vanilla IQS is the best option. Note that the query expansion
is applied to the prototype document terms and not on each query.

Figure 2: Performance evaluation of the IQS configurations in each active
retrieval iteration on the Twitter TREC Microblog 2012.

###  4.4 Iterative Query Selection with Pseudo Relevance Feedback

As a final experiment we evaluated the IQS ability to find relevant documents
for a given prototype document without the user’s help.

####  4.4.1 Experimental Setup

For this experiment, we used the search narrative for each topic in the TREC-
COVID 2019 as the prototype document. We used the same hyper-parameters from
the previous experiments for IQS. Since the TREC-COVID 2019 dataset was
published as part of a Kaggle competition, we also submit our results as a
late submission.

####  4.4.2 Results & Discussion

The IQS achieved MAP and R-Precision of 0.019 and 0.068 on theTREC-COVID 2019
dataset which are not impressive. These results imply that there is a mismatch
between the terms used in the topic narrative to the judged documents’ terms.
To verify this assumption we evaluate the MAP and R-Precision after one active
learning iteration (10 labels) and the results reached a MAP and R-Precision
of 0.317 and 0.367 respectively. This strengthens our assumption that there is
a high vocabulary mismatch between the topic narrative and the judged
documents. Thus the topic narrative does not represent well the discussed
topic.

The results on the Kaggle platform were calculated using Normalized Discounted
Cumulative Gain (NDCG). Although we expect IQS to have poor performance due to
the vocabulary mismatch, The IQS reached the fifth place on the public leader-
board obtaining NDCG of 0.133 and the forth place on the private leader-board
obtaining NDCG of 0.475. These results suggest that even though there is a
vocabulary mismatch some of the relevant documents are still ranked high.

##  5 Application for Fake News Detection Using Twitter

As opposed to the previous evaluations, which focused on relevance feedback,
in many real world problems, it is impossible to use such a manner. In many
cases, it is not practical and scalable to ask feedback from the users
continuously. Therefore, here, we are in a mode of pseudo relevance feedback.
This means that we apply the _iterative query selection (IQS)_ on the Twitter
search engine and refer the obtained _mean relevance error (MRE)_ score for
the returned tweets as pseudo-relevance feedback.

In this section, we demonstrate the importance of the IQS as a necessary link
in the pipeline of fake news detection. Using the proposed IQS and MRE, we
demonstrate an automated collection of relevant tweets associated with labeled
given news items (ground truth). Later, using these relevant tweets, we
demonstrate fake news detection using supervised machine learning classifiers.
In the following section, we describe the background of fake news detection on
online social media (OSM), including the data collection process. Afterward,
we present the dataset obtained using the IQS for fake news detection on OSM.
Finally, we train a classifier on the collected data and present its
performance.

###  5.1 Background

The task of fake news classification has been studied intensely in recent
years. Along with the growth of online news, many non-traditional news
sources, such as blogs have evolved in order to respond to users’ “appetite
for information." In many cases, however, these sources are operated by
amateurs whose reporting is often subjective, misleading, or unreliable [56].
This everyone is a journalist phenomenon [57], coupled with the flood of
unverified news and the absence of quality control procedures to prevent
potential deception, has contributed to an increasing problem of fake news
dissemination [58].

The spread of misinformation, propaganda, and fabricated news has potentially
harmful effects, even including a significant impact on real-world events
[59]. In recent years, it has weakened public trust in democratic governments
and their activities, such as the “Brexit" referendum and the 2016 U.S.
election [60]. World economies are also not immune to the impact of fake news;
this was demonstrated when a false claim regarding an injury to President
Obama caused the stock markets to plunge (dropping 130 billion dollars) [61].
In recent years, due to the threats to democracy, journalistic integrity, and
economies, researchers have been motivated to develop solutions for this
serious problem [60] proposing approaches for the detection of fake news based
on natural language processing [43], and investigating the diffusion of news
[15], etc.

###  5.2 Evaluation of the RE as a Relevance Estimator

First, it is important to verify that the RE identifies relevant posts from
Twitter to a given news item. To measure the RE score, we collected the _News_
dataset. The _News_ dataset consists of 20 news items that were retrieved
manually from the fact checking website of Snopes. The manual query selection
for each news item includes the following steps: First, read the given news
item in order to understand its subject. Second, assign queries that express
the meaning of the given news item, omitting stop words. Similar to Zhang’s
suggestions [62], extract 3-5 queries from the title and description of a
given news item. Third, use synonyms to expand and reformulate the queries in
order to retrieve a high number of relevant posts [63]. Therefore, you are
also required to use synonyms in order to retrieve a high number of posts
relevant to the given news item. For example, for the news item titled: “Did
Donald Trump Scare a Group of Schoolchildren?," there are several synonyms
that can be used: Donald Trump - President of U.S., scare - frighten,
schoolchildren - youngsters, etc. Fourth, after the queries are determined,
use them in the search engine and read a few of the results returned in order
to understand whether they are relevant to the given news item. Moreover, the
number of retrieved posts is important. In the case, there are only a few
posts, it can be a good indication to use more synonyms as query keywords (see
Algorithm 2).

Algorithm 2 Manual Query Selection

1:Read news item’s title and description

2: If it is necessary, read the full report

3:Assign query that express the meaning of the news item.

4:Provide 3-5 alternative queries

5: Use synonyms

6:Verify the relevance of the queries using the search engine

7: Read a few of the retrieved results.

8: Check relevance.

9: Record the number of retrieved results.

Since the queries assigned manually provided mostly relevant results, we used
the TF-IDF query generator to obtain more negative samples. The TF-IDF query
generator generated the query by selecting query keywords that obtained the
highest TF-IDF score. The TF-IDF score of each news item’s word is calculated
relative to all other news items in the dataset. Then, we used the Twitter API
to collect associated tweets using the assigned keywords. In total, we
collected 1,173 tweets and labeled them manually. For the labeling process, we
used three annotators (students) that were required to read the news item’s
title and description and the retrieved tweets associated with it. Later, each
annotator labeled each tweet with one of the optional labels: _Relevant_ in
case of the given tweet is associated to the given news item, _Irrelevant_ in
the opposite case, and _Unknown_ in case the annotator is not sure whether the
tweet is related or not. Among the 1,173 retrieved tweets, we used only the
tweets that the majority among the annotators agreed on (1,076 tweets). For an
example of a news item and relevant, and irrelevant tweets see Table 3.

Table 3: Example for labeling tweets associated to a given online discussion News Item’s Title |  “The rapper DMX (Earl Simmons) died in February 2018.” (Fake)
---|---
Relevant Tweet |  “Juan is just think DMX died so good time!”
Irrelevant Tweet |  “I liked a @ YouTube… video DMX - I Just Died in your arms Tonight. [Remix]”

After collecting the _News_ dataset, we calculated the proposed RE score for
each tweet using its news item. As a prototype document, we concatenated the
news item’s title and description. Next, we used the pre-trained _fastText_
[64] model for word vector representations which was trained on Common
Crawl101010http://commoncrawl.org/ and
Wikipedia111111https://www.wikipedia.org/ using _fastText_ library.
121212https://fasttext.cc/

Figure 3: ROC performance of the RE on 1,076 labeled posts.

For evaluation, we calculated the AUC based on the RE scores of the retrieved
tweets. Based on 1,076 labeled tweets, we obtained an AUC score of 0.9 (see
Figure 3). This observation shows the effectiveness of the RE score for
differentiating between relevant and irrelevant associated tweets to a given
news item.

###  5.3 Data Collection Using Iterative Query Selection

####  5.3.1 Data Collection Method

In this section, we describe the construction of a large dataset for the task
of fake news detection on OSM using the _iterative query selection (IQS)_.
First, we crawl news items from fact checking websites, such as Snopes, Gossip
Cop,131313https://www.gossipcop.com/ and Politifact. For Snopes and Politifact
news items, there are five fine-grained multiple labels: true, mostly true,
false, mostly-false and pants-on-fire. Similarly to Rasool et al. [65], we
converted the classification problem into binary by categorizing the news
items that their label are true and mostly-true as true and news items that
their label are false, mostly-false and pants-on-fire as false. For Gossip
Cop, we categorized news items with scores between 0 to 3 as false and news
items with scores between 7 to 10, as true. Since the majority of the news
items in fact checking websites are false, we added news items from 10 well-
known news sources (Time of Israel, CNN News , ABC News, BBC News, The New
York Times, The Jerusalem Post , The American Conservative, MSNBC, Fox News,
and Politico) as true news items.  A large number of studies exploited
reliable news sources as a proxy for true news items [14].  In total, we
collected 70,018 news items (16,212 false, 53,806 true). For each news item,
we set the IQS algorithm to run on Twitter API three times, with the following
parameters: Returning 5 final queries ($numQueries=5$, a maximal number of 15
iterations ($itr=15$), five queries, the number of words in a query is between
3 to 6 ($minq=3,maxq=6$), and the number of results returned equals to 20
($resultLimit=20$). Then, after obtaining the top five final queries from all
three runs, we use them in order to retrieve the most relevant tweets for each
news items, while limiting the number of tweets returned for each query to
500. To make the fake news detection more realistic, we collected only the
tweets that were posted before the fact checker assigned a label for the given
news item. Finally, utilizing this approach, we constructed a large fake news
dataset containing about 70,000 news items and about 61 million corresponding
posts, the distribution of which is shown in Table 4.

Domain | #News Items | #True | #False | #Authors | #Tweets
---|---|---|---|---|---
politifact.com | 12,952 | 5,288 | 7,664 | 4,274,688 | 12,525,467
snopes.com | 4,682 | 845 | 3,837 | 1,721,162 | 3,617,550
gossipcop.com | 4,764 | 53 | 4,711 | 863,906 | 2,302,245
times of israel | 21,989 | 21,989 | 0 | 5,401,027 | 20,963,687
Jerusalem Post | 3,109 | 3,109 | 0 | 1,469,181 | 3,386,702
New York Times | 3,453 | 3,453 | 0 | 1,641,931 | 3,247,247
abc-news | 3,685 | 3,685 | 0 | 1,042,084 | 2,410,832
cnn-news | 3,496 | 3,496 | 0 | 1,381,585 | 2,988,373
fox-news | 3,620 | 3,620 | 0 | 1,115,282 | 2,921,356
bbc-news | 3,687 | 3,687 | 0 | 1,181,490 | 2,469,421
msnbc-news | 2,410 | 2,410 | 0 | 731,839 | 1,982,974
politico | 1,640 | 1,640 | 0 | 853,716 | 1,844,441
American Conservative | 531 | 531 | 0 | 440,086 | 619,336
Total | 70,018 | 53,806 | 16,212 | 22,117,977 | 61,279,631
Table 4: Fake news dataset statistics.

####  5.3.2 Classification Results

To classify the news items, we extract author- and post-based features. For
author-based features, we applied aggregation functions on various aspects of
author demographics, such as registration age, number of followers, number of
followees, number of distributed tweets published by the user, etc. Post-based
features include the aggregations of posts metadata, such as retweet count,
text length, the time interval between the oldest and newest post, etc. For
all the features extracted from the post, we removed stop words. Also,
regarding post’s data, we extracted the following features: sentiment,
temporal (post diffusion patterns), LDA (variations on the posts’ topics), TF-
IDF and word embedding. For the latter, we used the Glove Wikipedia pre-
trained model with 300 dimensions. For aggregation functions, we used mean,
median, max, min, standard deviation, kurtosis and skewness functions.

For the classification, we tried many combinations of supervised machine
learning algorithms and feature subsets. All classifiers were trained using
10-fold cross-validation. Eventually, we averaged the results obtained from
all the folds. We determined that the best performing classifier on the test
set was the Random Forest with 100 estimators and a max depth of 10. This
classifier, with 100 features obtained AUC and accuracy of 0.92 and 0.86,
respectively. This result is evidence that an application that detects false
news based on the OSM can benefit from our proposed approach.

Also, we analyzed most of the influential features of the best classifier (see
Table 5).

No. | Feature Name | Gini Importance
---|---|---
1 | Number of verified authors | 0.162
2 | Max number of posts published by claim’s authors | 0.049
3 | Glove_wikipedia_model_300d max dimension 295 | 0.046
4 | Glove_wikipedia_model_300d min dimension 291 | 0.037
5 | Max favorites count of claim’s authors | 0.036
6 | Max followers count of claim’s authors | 0.033
Table 5: Features listed by Gini importance.

The most important feature was the number of verified authors with Gini
importance of 0.162 (see Table 5). Comparing the distribution of these authors
with respect to fake and true news items, we can see the number of verified
authors within true news is 3 times higher than in false news items. These
differences were found statically significant (a p-value of 0.0). Based on
this result, we conclude that verified authors are important actors for the
detection of fake news. The higher their participation, the higher the
reliability of the online discussion.

According to the Gini importance, the second, fifth, and sixth highest
influential features were aggregations over the news item’s authors. This
strengthens the conclusion of Castillo et al. [66] that author-based features
are very relevant for fake news detection within the OSM.

In addition, the third and fourth features are aggregations on the word
embedding of the news item’s posts. These features indicate that the fixed-
length of vector representations of the words consists of the online
discussions that can hold the truthfulness of given news items.

These results show that our proposed algorithm can be utilized for solving
real world problems (e.g., the detection of fake news). In addition, the
machine learning classifiers trained on the collected this large dataset using
the IQS obtained impressive results. This strengths that our method can be
very useful for detecting fake news while retrieving relevant data
automatically.

##  6 Ethical Considerations

Collecting information from OSM has raised ethical concerns in recent years.
To minimize the potential risks of such activities, this study follows
recommendations presented by [67], which deal with the ethical challenges of
OSM and Internet communities.

For this study, we proposed a method, which selects queries for a given
prototype document to retrieve the maximal number of relevant documents. To
evaluate the proposed method, we used the Twitter search engine in order to
retrieve tweets associated with the given prototype document. This service
collects tweets published by accounts that agreed to share their information
publicly.

##  7 Conclusion & Future Work

In this paper, we propose an automated _iterative query selection (IQS)_
algorithm for improving information retrieval from opaque search engines. This
method consists of two components: the _mean relevance error (MRE)_ which
estimates the relevance of documents to a given prototype document and the
iterative algorithm which selects suitable queries based on the MRE
estimation.

We demonstrated our methods as a retrieval system with relevant feedback on
the _Twitter TREC Microblog 2012_ dataset and TREC-COVID 2019 dataset. Our
proposed method outperformed all the other methods on the both datasets.
Finally, we demonstrated the use of the proposed IQS method as part of a fake
news detection pipeline and obtain impressive results of an AUC of 0.92 and an
accuracy of 0.86.

As a result, we conclude the following conclusions: First, the MRE score is
found to be a successful measure for differentiating between relevant and
irrelevant documents concerning a given prototype document (see section 5.2).
Second, the IQS algorithm can find a large number of relevant results from an
opaque search engine (see section 4.3). Third, the IQS was found suitable and
useful for an automated fake news detection system. In contrast to other data
collection approaches, our method is generic and can obtain a larger subset of
relevant posts. For example, an approach that only collects posts that contain
the news item’s URL reaches a smaller subset of all the relevant documents and
requires the user to provide the appropriate source URL.

One possible future work could demonstrate the proposed approach on different
OSM platforms, such as Reddit141414https://www.reddit.com/,
Quora151515https://www.quora.com/, etc. Another might compare the
effectiveness of a fake new detection system using data collected using a
source URL versus data collected using our query selection method.

## References

  * [1] Prabhakar Raghavan Christopher D. Manning and Hinrich Schütze.  Introduction to Information Retrieval.  Cambridge University Press, 2008.
  * [2] Jiawei Yao, Jiajun Yao, Rui Yang, and Zhenyu Chen.  Product recommendation based on search keywords.  In 2012 Ninth Web Information Systems and Applications Conference, pages 67–70. IEEE, 2012.
  * [3] Steven Bethard and Dan Jurafsky.  Who should i cite: learning literature search models from citation behavior.  In Proceedings of the 19th ACM international conference on Information and knowledge management, pages 609–618, 2010.
  * [4] Xing Zhou, Juan Cao, Zhiwei Jin, Fei Xie, Yu Su, Dafeng Chu, Xuehui Cao, and Junqiang Zhang.  Real-time news cer tification system on sina weibo.  In Proceedings of the 24th International Conference on World Wide Web, pages 983–988. ACM, 2015.
  * [5] Jon Ezeiza Alvarez and Hannah Bast.  A review of word embedding and document similarity algorithms applied to academic text, 2017.
  * [6] Quoc Le and Tomas Mikolov.  Distributed representations of sentences and documents.  In International conference on machine learning, pages 1188–1196, 2014.
  * [7] Ryan Kiros, Yukun Zhu, Russ R Salakhutdinov, Richard Zemel, Raquel Urtasun, Antonio Torralba, and Sanja Fidler.  Skip-thought vectors.  In Advances in neural information processing systems, pages 3294–3302, 2015.
  * [8] Matteo Pagliardini, Prakhar Gupta, and Martin Jaggi.  Unsupervised learning of sentence embeddings using compositional n-gram features.  In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pages 528–540, 2018.
  * [9] J urgen Koenemann and Nicholas J Belkin.  A case for interaction: A study of interactive information retrieval behavior and effectiveness.  In Proceeding of the ACM SIGCHI Conference on Human Factors in Computing Systems, pages 205–212. Citeseer, 1996.
  * [10] Paul-Alexandru Chirita, Claudiu S Firan, and Wolfgang Nejdl.  Personalized query expansion for the web.  In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 7–14. ACM, 2007.
  * [11] Steve Cronen-Townsend, Yun Zhou, and W Bruce Croft.  Predicting query performance.  In Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, pages 299–306. ACM, 2002.
  * [12] Lev Finkelstein, Evgeniy Gabrilovich, Yossi Matias, Ehud Rivlin, Zach Solan, Gadi Wolfman, and Eytan Ruppin.  Placing search in context: The concept revisited.  In Proceedings of the 10th international conference on World Wide Web, pages 406–414, 2001.
  * [13] Search tweets.  https://developer.twitter.com/en/docs/tweets/search/guides/standard-operators.
  * [14] Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael M Bronstein.  Fake news detection on social media using geometric deep learning.  arXiv preprint arXiv:1902.06673, 2019.
  * [15] Soroush Vosoughi, Deb Roy, and Sinan Aral.  The spread of true and false news online.  Science, 359(6380):1146–1151, 2018.
  * [16] Ping Wu, Ji-Rong Wen, Huan Liu, and Wei-Ying Ma.  Query selection techniques for efficient crawling of structured web sources.  In 22nd International Conference on Data Engineering (ICDE’06), pages 47–47. IEEE, 2006.
  * [17] Dwaipayan Roy, Debjyoti Paul, Mandar Mitra, and Utpal Garain.  Using word embeddings for automatic query expansion.  arXiv preprint arXiv:1606.07608, 2016.
  * [18] Saar Kuzi, Anna Shtok, and Oren Kurland.  Query expansion using word embeddings.  In Proceedings of the 25th ACM international on conference on information and knowledge management, pages 1929–1932. ACM, 2016.
  * [19] Bo Xu, Hongfei Lin, Yuan Lin, Liang Yang, and Kan Xu.  Improving pseudo-relevance feedback with neural network-based word representations.  IEEE Access, 6:62152–62165, 2018.
  * [20] Wei Pang and Junping Du.  Query expansion and query fuzzy with large-scale click-through data for microblog retrieval.  International Journal of Machine Learning and Computing, 9(3), 2019\.
  * [21] Cheng Li, Yue Wang, Paul Resnick, and Qiaozhu Mei.  Req-rec: High recall retrieval with query pooling and interactive classification.  In Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval, pages 163–172. ACM, 2014.
  * [22] Raheleh Makki, Eder Carvalho, Axel J Soto, Stephen Brooks, Maria Cristina Ferreira De Oliveira, Evangelos Milios, and Rosane Minghim.  Atr-vis: Visual and interactive information retrieval for parliamentary discussions in twitter.  ACM Transactions on Knowledge Discovery from Data (TKDD), 12(1):3, 2018.
  * [23] Hamed Zamani, Javid Dadashkarimi, Azadeh Shakery, and W Bruce Croft.  Pseudo-relevance feedback based on matrix factorization.  In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pages 1483–1492. ACM, 2016.
  * [24] Belal Al-Khateeb, Ali J Al-Kubaisi, and Sufyan T Al-Janabi.  Query reformulation using wordnet and genetic algorithm.  In 2017 Annual Conference on New Trends in Information & Communications Technology Applications (NTICT), pages 91–96. IEEE, 2017.
  * [25] Rodrigo Nogueira and Kyunghyun Cho.  Task-oriented query reformulation with reinforcement learning.  2017\.
  * [26] Abu Nowshed Chy, Md Zia Ullah, and Masaki Aono.  Query expansion for microblog retrieval focusing on an ensemble of features.  Journal of Information Processing, 27:61–76, 2019.
  * [27] Khaled Albishre, Yuefeng Li, and Yue Xu.  Effective pseudo-relevance for microblog retrieval.  In Proceedings of the Australasian Computer Science Week Multiconference, pages 1–6, 2017.
  * [28] Xin Zheng and Aixin Sun.  Collecting event-related tweets from twitter stream.  Journal of the Association for Information Science and Technology, 70(2):176–186, 2019.
  * [29] Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger.  From word embeddings to document distances.  In International Conference on Machine Learning, pages 957–966, 2015.
  * [30] Tom Kenter and Maarten De Rijke.  Short text similarity with word embeddings.  In Proceedings of the 24th ACM international on conference on information and knowledge management, pages 1411–1420. ACM, 2015.
  * [31] Eric Nalisnick, Bhaskar Mitra, Nick Craswell, and Rich Caruana.  Improving document ranking with dual word embeddings.  In Proceedings of the 25th International Conference Companion on World Wide Web, pages 83–84, 2016.
  * [32] Jiafeng Guo, Yixing Fan, Qingyao Ai, and W Bruce Croft.  A deep relevance matching model for ad-hoc retrieval.  In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pages 55–64, 2016.
  * [33] Bhaskar Mitra, Fernando Diaz, and Nick Craswell.  Learning to match using local and distributed representations of text for web search.  In Proceedings of the 26th International Conference on World Wide Web, pages 1291–1299, 2017.
  * [34] Marina Drosou and Evaggelia Pitoura.  Search result diversification.  ACM SIGMOD Record, 39(1):41–47, 2010.
  * [35] Sreenivas Gollapudi and Aneesh Sharma.  An axiomatic approach for result diversification.  In Proceedings of the 18th international conference on World wide web, pages 381–390, 2009.
  * [36] Jaime Carbonell and Jade Goldstein.  The use of mmr, diversity-based reranking for reordering documents and producing summaries.  In Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, pages 335–336, 1998.
  * [37] Alex Slivkins, Filip Radlinski, and Sreenivas Gollapudi.  Learning optimally diverse rankings over large document collections.  2010\.
  * [38] Ben Carterette and Praveen Chandar.  Probabilistic models of ranking novel documents for faceted topic retrieval.  In Proceedings of the 18th ACM conference on Information and knowledge management, pages 1287–1296, 2009.
  * [39] Jiyin He, Edgar Meij, and Maarten de Rijke.  Result diversification based on query-specific cluster ranking.  Journal of the American Society for Information Science and Technology, 62(3):550–571, 2011.
  * [40] Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Ieong.  Diversifying search results.  In Proceedings of the second ACM international conference on web search and data mining, pages 5–14, 2009.
  * [41] Rodrygo LT Santos, Craig Macdonald, and Iadh Ounis.  Exploiting query reformulations for web search result diversification.  In Proceedings of the 19th international conference on World wide web, pages 881–890, 2010.
  * [42] Craig Silverman.  This analysis shows how viral fake election news stories outperformed real news on facebook.  BuzzFeed News, 16, 2016.
  * [43] Zhixuan Zhou, Huankang Guan, Meghana Moorthy Bhat, and Justin Hsu.  Fake news detection via nlp is vulnerable to adversarial attacks.  arXiv preprint arXiv:1901.09657, 2019.
  * [44] Kai Shu, Amy Sliva, Suhang Wang, Jiliang Tang, and Huan Liu.  Fake news detection on social media: A data mining perspective.  ACM SIGKDD Explorations Newsletter, 19(1):22–36, 2017.
  * [45] William Yang Wang.  " liar, liar pants on fire": A new benchmark dataset for fake news detection.  arXiv preprint arXiv:1705.00648, 2017.
  * [46] Zhiwei Jin, Juan Cao, Han Guo, Yongdong Zhang, and Jiebo Luo.  Multimodal fusion with recurrent neural networks for rumor detection on microblogs.  In Proceedings of the 25th ACM international conference on Multimedia, pages 795–816. ACM, 2017.
  * [47] Yaqing Wang, Fenglong Ma, Zhiwei Jin, Ye Yuan, Guangxu Xun, Kishlay Jha, Lu Su, and Jing Gao.  Eann: Event adversarial neural networks for multi-modal fake news detection.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 849–857. ACM, 2018.
  * [48] Jeffrey Pennington, Richard Socher, and Christopher Manning.  Glove: Global vectors for word representation.  In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543, 2014.
  * [49] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  arXiv preprint arXiv:1301.3781, 2013.
  * [50] Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov.  Enriching word vectors with subword information.  arXiv preprint arXiv:1607.04606, 2016.
  * [51] Steven S Skiena.  The algorithm design manual: Text, volume 1.  Springer Science & Business Media, 1998.
  * [52] G. Miller.  WordNet: A Lexical Database for English.  Communications of the ACM, 38(11):39–41, 1995.
  * [53] Ian Soboroff, Iadh Ounis, Craig Macdonald, and Jimmy J Lin.  Overview of the trec-2012 microblog track.  In TREC, volume 2012, page 20. Citeseer, 2012.
  * [54] Stephen Robertson and Hugo Zaragoza.  The probabilistic relevance framework: BM25 and beyond.  Now Publishers Inc, 2009.
  * [55] Scott Deerwester, Susan T Dumais, George W Furnas, Thomas K Landauer, and Richard Harshman.  Indexing by latent semantic analysis.  Journal of the American society for information science, 41(6):391–407, 1990.
  * [56] Leonard Downie and Michael Schudson.  The reconstruction of american journalism.  Columbia Journalism Review, 19, 2009.
  * [57] Yuan Zeng.  Danger, trauma, and verification: eyewitnesses and the journalists who view their material.  Media Asia, 45(1-2), 2018.
  * [58] Niall J Conroy, Victoria L Rubin, and Yimin Chen.  Automatic deception detection: Methods for finding fake news.  In Proceedings of the 78th ASIS&T Annual Meeting: Information Science with Impact: Research in and for the Community, page 82. American Society for Information Science, 2015.
  * [59] Hunt Allcott and Matthew Gentzkow.  Social media and fake news in the 2016 election.  Journal of economic perspectives, 31(2):211–36, 2017.
  * [60] Xinyi Zhou, Reza Zafarani, Kai Shu, and Huan Liu.  Fake news: Fundamental theories, detection strategies and challenges.  In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 836–837. ACM, 2019.
  * [61] K Rapoza.  Can ‘fake news’ impact the stock market?  Pridobljeno iz www. forbes. com/sites/kenrapoza/2017/02/26/can-fake-news-impact-the-stock-market/(9. 7. 2018), 2017.
  * [62] Chengzhi Zhang.  Automatic keyword extraction from documents using conditional random fields.  Journal of Computational Information Systems, 4(3):1169–1180, 2008\.
  * [63] Ellen M Voorhees.  Query expansion using lexical-semantic relations.  In Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, pages 61–69. Springer-Verlag New York, Inc., 1994.
  * [64] Tomas Mikolov, Edouard Grave, Piotr Bojanowski, Christian Puhrsch, and Armand Joulin.  Advances in pre-training distributed word representations.  In Proceedings of the International Conference on Language Resources and Evaluation (LREC 2018), 2018.
  * [65] Tayyaba Rasool, Wasi Haider Butt, Arslan Shaukat, and M Usman Akram.  Multi-label fake news detection using multi-layered supervised learning.  In Proceedings of the 2019 11th International Conference on Computer and Automation Engineering, pages 73–77, 2019.
  * [66] Carlos Castillo, Marcelo Mendoza, and Barbara Poblete.  Information credibility on twitter.  In Proceedings of the 20th international conference on World wide web, pages 675–684. ACM, 2011.
  * [67] Yuval Elovici, Michael Fire, Amir Herzberg, and Haya Shulman.  Ethical considerations when employing fake identities in online social networks for research.  Science and engineering ethics, 20(4):1027–1043, 2014.