###### Abstract

In recent years, there has been an exponential growth in the number of complex
documents and texts that require a deeper understanding of machine learning
methods to be able to accurately classify texts in many applications. Many
machine learning approaches have achieved surpassing results in natural
language processing. The success of these learning algorithms relies on their
capacity to understand complex models and non-linear relationships within
data. However, finding suitable structures, architectures, and techniques for
text classification is a challenge for researchers. In this paper, a brief
overview of text classification algorithms is discussed. This overview covers
different text feature extractions, dimensionality reduction methods, existing
algorithms and techniques, and evaluations methods. Finally, the limitations
of each technique and their application in real-world problems are discussed.

###### keywords:

text classification; text mining; text representation; text categorization;
text analysis; document classification

10 4 150 Received: 22 March 2019; Accepted: 17 April 2019; Published: 23 April
2019 yes Text Classification Algorithms: A Survey Kamran Kowsari 1,2,*, Kiana
Jafari Meimandi 1 , Mojtaba Heidarysafa 1, Sanjana Mendu 1, Laura Barnes 1,2,3
and Donald Brown 1,3 Kamran Kowsari, Kiana Jafari Meimandi, Mojtaba
Heidarysafa, Sanjana Mendu, Laura E. Barnes and Donald E. Brown
Correspondence<EMAIL_ADDRESS>Tel.: +1-202-812-3013

##  1 Introduction

Text classification problems have been widely studied and addressed in many
real applications Jiang et al. (2018); Kowsari et al. (2017); McCallum et al.
(1998); Kowsari et al. (2018); Heidarysafa et al. (2018); Lai et al. (2015);
Aggarwal and Zhai (2012a, b) over the last few decades. Especially with recent
breakthroughs in Natural Language Processing (NLP) and text mining, many
researchers are now interested in developing applications that leverage text
classification methods. Most text classification and document categorization
systems can be deconstructed into the following four phases: Feature
extraction, dimension reductions, classifier selection, and evaluations. In
this paper, we discuss the structure and technical implementations of text
classification systems in terms of the pipeline illustrated in Figure 1 (The
source code and the results are shared as free tools at
https://github.com/kk7nc/Text_Classification).

The initial pipeline input consists of some raw text data set. In general,
text data sets contain sequences of text in documents as
$D=\\{X_{1},X_{2},\ldots,X_{N}\\}$ where $X_{i}$ refers to a data point (i.e.,
document, text segment) with $s$ number of sentences such that each sentence
includes $w_{s}$ words with $l_{w}$ letters. Each point is labeled with a
class value from a set of $k$ different discrete value indices Aggarwal and
Zhai (2012a).

Then, we should create a structured set for our training purposes which call
this section Feature Extraction. The dimensionality reduction step is an
optional part of the pipeline which could be part of the classification system
(e.g., if we use Term Frequency-Inverse Document Frequency (TF-IDF) as our
feature extraction and in train set we have $200k$ unique words, computational
time is very expensive, so we could reduce this option by bringing feature
space in other dimensional space). The most significant step in document
categorization is choosing the best classification algorithm. The other part
of the pipeline is the evaluation step which is divided into two parts
(prediction the test set and evaluating the model). In general, the text
classification system contains four different levels of scope that can be
applied:

  1. 1.

Document level: In the document level, the algorithm obtains the relevant
categories of a full document.

  2. 2.

Paragraph level: In the paragraph level, the algorithm obtains the relevant
categories of a single paragraph (a portion of a document).

  3. 3.

Sentence level: In the sentence level, obtains the relevant categories of a
single sentence (a portion of a paragraph).

  4. 4.

Sub-sentence level: In the sub-sentence level, the algorithm obtains the
relevant categories of sub-expressions within a sentence (a portion of a
sentence )).

Figure 1: Overview of text classification pipeline.

(I) Feature Extraction: In general, texts and documents are unstructured data
sets. However, these unstructured text sequences must be converted into a
structured feature space when using mathematical modeling as part of a
classifier. First, the data needs to be cleaned to omit unnecessary characters
and words. After the data has been cleaned, formal feature extraction methods
can be applied. The common techniques of feature extractions are Term
Frequency-Inverse Document Frequency (TF-IDF), Term Frequency (TF) Salton and
Buckley (1988), Word2Vec Goldberg and Levy (2014), and Global Vectors for Word
Representation (GloVe) Pennington et al. (2014). In Section 2, we categorize
these methods as either word embedding or weighted word techniques and discuss
the technical implementation details.

(II) Dimensionality Reduction: As text or document data sets often contain
many unique words, data pre-processing steps can be lagged by high time and
memory complexity. A common solution to this problem is simply using
inexpensive algorithms. However, in some data sets, these kinds of cheap
algorithms do not perform as well as expected. In order to avoid the decrease
in performance, many researchers prefer to use dimensionality reduction to
reduce the time and memory complexity for their applications. Using
dimensionality reduction for pre-processing could be more efficient than
developing inexpensive classifiers.

In Section 3, we outline the most common techniques of dimensionality
reduction, including Principal Component Analysis (PCA), Linear Discriminant
Analysis (LDA), and non-negative matrix factorization (NMF). We also discuss
novel techniques for unsupervised feature extraction dimensionality reduction,
such as random projection, autoencoders, and t-distributed stochastic neighbor
embedding (t-SNE).

(III) Classification Techniques: The most important step of the text
classification pipeline is choosing the best classifier. Without a complete
conceptual understanding of each algorithm, we cannot effectively determine
the most efficient model for a text classification application. In Section 4,
we discuss the most popular techniques of text classification. First, we cover
traditional methods of text classification, such as Rocchio classification.
Next, we talk about ensemble-based learning techniques such as boosting and
bagging, which have been used mainly for query learning strategies and text
analysis Mamitsuka et al. (1998); Kim et al. (2000); Schapire and Singer
(2000). One of the simplest classification algorithms is logistic regression
(LR) which has been addressed in most data mining domains Harrell (2001);
Hosmer Jr et al. (2013); Dou et al. (2018); Chen et al. (2017). In the
earliest history of information retrieval as a feasible application, The Naïve
Bayes Classifier (NBC) was very popular. We have a brief overview of Naïve
Bayes Classifier which is computationally inexpensive and also needs a very
low amount of memory Larson (2010).

Non-parametric techniques have been studied and used as classification tasks
such as k-nearest neighbor (KNN) Li et al. (2001). Support Vector Machine
(SVM) Manevitz and Yousef (2001); Han and Karypis (2000) is another popular
technique which employs a discriminative classifier for document
categorization. This technique can also be used in all domains of data mining
such as bioinformatics, image, video, human activity classification, safety
and security, etc. This model is also used as a baseline for many researchers
to compare against their own works to highlight novelty and contributions.

Tree-based classifiers such as decision tree and random forest have also been
studied with respect to document categorization Xu et al. (2012). Each tree-
based algorithm will be covered in a separate sub-section. In recent years,
graphical classifications have been considered Lafferty et al. (2001) as a
classification task such as conditional random fields (CRFs). However, these
techniques are mostly used for document summarization Shen et al. (2007) and
automatic keyword extraction Zhang (2008).

Lately, deep learning approaches have achieved surpassing results in
comparison to previous machine learning algorithms on tasks such as image
classification, natural language processing, face recognition, etc. The
success of these deep learning algorithms relies on their capacity to model
complex and non-linear relationships within data LeCun et al. (2015).

(IV) Evaluation: The final part of the text classification pipeline is
evaluation. Understanding how a model performs is essential to the use and
development of text classification methods. There are many methods available
for evaluating supervised techniques. Accuracy calculation is the simplest
method of evaluation but does not work for unbalanced data sets Huang and Ling
(2005). In Section 5, we outline the following evaluation methods for text
classification algorithms: $F_{\beta}$ Score Lock (2002), Matthews Correlation
Coefficient (MCC) Matthews (1975), receiver operating characteristics (ROC)
Hanley and McNeil (1982), and area under the ROC curve (AUC) Pencina et al.
(2008).

In Section 6, we talk about the limitations and drawbacks of the methods
mentioned above. We also briefly compare the steps of pipeline including
feature extractions, dimensionality reduction, classification techniques, and
evaluation methods. The state-of-the-art techniques are compared in this
section by many criteria such as architecture of their model, novelty of the
work, feature extraction technique, corpus (the data set/s used), validation
measure, and limitation of each work. Finding the best system for an
application requires choosing a feature extraction method. This choice
completely depends on the goal and data set of an application as some feature
extraction techniques are not efficient for a specific application. For
example, since GloVe is trained on Wikipedia and when used for short text
messages like short message service (SMS), this technique does not perform as
well as TF-IDF. Additionally, limited data points that this model cannot be
trained as well as other techniques due to the small amount of data. The next
step or in this pipeline, is a classification technique, where we briefly talk
about the limitation and drawbacks of each technique.

In Section 7, we describe the text and document classification applications.
Text classification is a major challenge in many domains and fields for
researchers. Information retrieval systems Jacobs (2014) and search engine
Croft et al. (2010); Yammahi et al. (2014) applications commonly make use of
text classification methods. Extending from these applications, text
classification could also be used for applications such as information
filtering (e.g., email and text message spam filtering) Chu et al. (2010).
Next, we talk about adoption of document categorization in public health
Gordon Jr (1983) and human behavior Nobles et al. (2018). Another area that
has been helped by text classification is document organization and knowledge
management. Finally, we will discuss recommender systems which are extensively
used in marketing and advertising.

##  2 Text Preprocessing

Feature extraction and pre-processing are crucial steps for text
classification applications. In this section, we introduce methods for
cleaning text data sets, thus removing implicit noise and allowing for
informative featurization. Furthermore, we discuss two common methods of text
feature extraction: Weighted word and word embedding techniques.

###  2.1 Text Cleaning and Pre-processing

Most text and document data sets contain many unnecessary words such as
stopwords, misspelling, slang, etc. In many algorithms, especially statistical
and probabilistic learning algorithms, noise and unnecessary features can have
adverse effects on system performance. In this section, we briefly explain
some techniques and methods for text cleaning and pre-processing text data
sets.

####  2.1.1 Tokenization

Tokenization is a pre-processing method which breaks a stream of text into
words, phrases, symbols, or other meaningful elements called tokens Gupta and
Malhotra (2015); Verma et al. (2014). The main goal of this step is the
investigation of the words in a sentence Verma et al. (2014). Both text
classification and text mining require a parser which processes the
tokenization of the documents, for example:
sentence Aggarwal (2018):

> After sleeping for four hours, he decided to sleep for another four.

In this case, the tokens are as follows:

> { “After” “sleeping” “for” “four” “hours” “he” “decided” “to” “sleep” “for”
> “another” “four” }.

####  2.1.2 Stop Words

Text and document classification includes many words which do not contain
important significance to be used in classification algorithms, such as {“a”,
“about”, “above”, “across”, “after”, “afterwards”, “again”,$\ldots$}. The most
common technique to deal with these words is to remove them from the texts and
documents Saif et al. (2014).

####  2.1.3 Capitalization

Text and document data points have a diversity of capitalization to form a
sentence. Since documents consist of many sentences, diverse capitalization
can be hugely problematic when classifying large documents. The most common
approach for dealing with inconsistent capitalization is to reduce every
letter to lower case. This technique projects all words in text and document
into the same feature space, but it causes a significant problem for the
interpretation of some words (e.g., “US” (United States of America) to “us”
(pronoun)) Gupta et al. (2009). Slang and abbreviation converters can help
account for these exceptions Dalal and Zaveri (2011).

####  2.1.4 Slang and Abbreviation

Slang and abbreviation are other forms of text anomalies that are handled in
the pre-processing step. An abbreviation Whitney and Evans (2010) is a
shortened form of a word or phrase which contain mostly first letters form the
words, such as SVM which stands for Support Vector Machine.

Slang is a subset of the language used in informal talk or text that has
different meanings such as “lost the plot”, which essentially means that
they’ve gone mad Helm (2003). A common method for dealing with these words is
converting them into formal language Dhuliawala et al. (2016).

####  2.1.5 Noise Removal

Most of the text and document data sets contain many unnecessary characters
such as punctuation and special characters. Critical punctuation and special
characters are important for human understanding of documents, but it can be
detrimental for classification algorithms Pahwa et al. .

####  2.1.6 Spelling Correction

Spelling correction is an optional pre-processing step. Typos (short for
typographical errors) are commonly present in texts and documents, especially
in social media text data sets (e.g., Twitter). Many algorithms, techniques,
and methods have addressed this problem in NLP Mawardi et al. (2018). Many
techniques and methods are available for researchers including hashing-based
and context-sensitive spelling correction techniques Dziadek et al. (2017), as
well as spelling correction using Trie and Damerau–Levenshtein distance bigram
Mawardi et al. (2018).

####  2.1.7 Stemming

In NLP, one word could appear in different forms (i.e., singular and plural
noun form) while the semantic meaning of each form is the same Spirovski et
al. (2018). One method for consolidating different forms of a word into the
same feature space is stemming. Text stemming modifies words to obtain variant
word forms using different linguistic processes such as affixation (addition
of affixes) Singh and Gupta (2016); Sampson (2005). For example, the stem of
the word “studying” is “study”.

####  2.1.8 Lemmatization

Lemmatization is a NLP process that replaces the suffix of a word with a
different one or removes the suffix of a word completely to get the basic word
form (lemma) Plisson et al. (2004); Korenius et al. (2004); Sampson (2005).

###  2.2 Syntactic Word Representation

Many researchers have worked on this text feature extraction technique to
solve the loosing syntactic and semantic relation between words. Many
researchers addressed novel techniques for solving this problem, but many of
these techniques still have limitations. In Caropreso and Matwin (2006), a
model was introduced in which the usefulness of including syntactic and
semantic knowledge in the text representation for the selection of sentences
comes from technical genomic texts. The other solution for syntactic problem
is using the n-gram technique for feature extraction.

####  2.2.1 N-Gram

The n-gram technique is a set of $n\text{-}word$ which occurs “in that order”
in a text set. This is not a representation of a text, but it could be used as
a feature to represent a text.

BOW is a representation of a text using its words $(1\text{-}gram)$ which
loses their order (syntactic). This model is very easy to obtain and the text
can be represented through a vector, generally of a manageable size of the
text. On the other hand, $n\text{-}gram$ is a feature of BOW for a
representation of a text using $1\text{-}gram$. It is very common to use
$2\text{-}gram$ and $3\text{-}gram$. In this way, the text feature extracted
could detect more information in comparison to $1\text{-}gram$.

#### An Example of $2\text{-}Gram$

> After sleeping for four hours, he decided to sleep for another four.

In this case, the tokens are as follows:

> { “After sleeping”, “sleeping for”, “for four”, “four hours”, “four he” “he
> decided”, “decided to”, “to sleep”, “sleep for”, “for another”, “another
> four” }.

#### An Example of $3\text{-}Gram$

> After sleeping for four hours, he decided to sleep for another four.

In this case, the tokens are as follows:

> { “After sleeping for”, “sleeping for four”, “four hours he”, “ hours he
> decided”, “he decided to”, “to sleep for”, “sleep for another”, “for another
> four” }.

####  2.2.2 Syntactic N-Gram

In Sidorov et al. (2012), syntactic n-grams are discussed which is defined by
paths in syntactic dependency or constituent trees rather than the linear
structure of the text.

###  2.3 Weighted Words

The most basic form of weighted word feature extraction is TF, where each word
is mapped to a number corresponding to the number of occurrences of that word
in the whole corpora. Methods that extend the results of TF generally use word
frequency as a boolean or logarithmically scaled weighting. In all weight
words methods, each document is translated to a vector (with length equal to
that of the document) containing the frequency of the words in that document.
Although this approach is intuitive, it is limited by the fact that particular
words that are commonly used in the language may dominate such
representations.

####  2.3.1 Bag of Words (BoW)

The bag-of-words model (BoW model) is a reduced and simplified representation
of a text document from selected parts of the text, based on specific
criteria, such as word frequency.

The BoW technique is used in several domains such as computer vision, NLP,
Bayesian spam filters, as well as document classification and information
retrieval by Machine Learning.

In a BoW, a body of text, such as a document or a sentence, is thought of like
a bag of words. Lists of words are created in the BoW process. These words in
a matrix are not sentences which structure sentences and grammar, and the
semantic relationship between these words are ignored in their collection and
construction. The words are often representative of the content of a sentence.
While grammar and order of appearance are ignored, multiplicity is counted and
may be used later to determine the focus points of the documents.

Here is an example of BoW:

#### Document

> “As the home to UVA’s recognized undergraduate and graduate degree programs
> in systems engineering. In the UVA Department of Systems and Information
> Engineering, our students are exposed to a wide range of range”

#### Bag-of-Words (BoW)

> {“As”, “the”, “home”, “to”, “UVA’s”, “recognized”, “undergraduate”, “and”,
> “graduate”, “degree”, “program”, “in”, “systems”, “engineering”, “in”,
> “Department”, “Information”,“students”, “ ”,“are”, “exposed”, “wide”,
> “range” }

#### Bag-of-Feature (BoF)

> Feature = {1,1,1,3,2,1,2,1,2,3,1,1,1,2,1,1,1,1,1,1}

####  2.3.2 Limitation of Bag-of-Words

Bag0of-words models encode every word in the vocabulary as one-hot-encoded
vector e.g., for the vocabulary of size $|\Sigma|$, each word is represented
by a $|\Sigma|$ dimensional sparse vector with $1$ at index corresponding to
the word and 0 at every other index. As vocabulary may potentially run into
millions, bag-of-word models face scalability challenges (e.g., “This is good”
and “Is this good” have exactly the same vector representation). The technical
problem of the bag-of-word is also the main challenge for the computer science
and data science community.

Term frequency, also called bag-of-words, is the simplest technique of text
feature extraction. This method is based on counting the number of words in
each document and assigning it to the feature space.

####  2.3.3 Term Frequency-Inverse Document Frequency

K. Sparck Jones Sparck Jones (1972) proposed Inverse Document Frequency (IDF)
as a method to be used in conjunction with term frequency in order to lessen
the effect of implicitly common words in the corpus. IDF assigns a higher
weight to words with either high or low frequencies term in the document. This
combination of TF and IDF is well known as Term Frequency-Inverse document
frequency (TF-IDF). The mathematical representation of the weight of a term in
a document by TF-IDF is given in Equation (1).

$W(d,t)=TF(d,t)*log(\frac{N}{df(t)})$ (1)

Here _N_ is the number of documents and $df(t)$ is the number of documents
containing the term _t_ in the corpus. The first term in Equation (1) improves
the recall while the second term improves the precision of the word embedding
Tokunaga and Makoto (1994). Although TF-IDF tries to overcome the problem of
common terms in the document, it still suffers from some other descriptive
limitations. Namely, TF-IDF cannot account for the similarity between the
words in the document since each word is independently presented as an index.
However, with the development of more complex models in recent years, new
methods, such as word embedding, have been presented that can incorporate
concepts such as similarity of words and part of speech tagging.

###  2.4 Word Embedding

Even though we have syntactic word representations, it does not mean that the
model captures the semantics meaning of the words. On the other hand, bag-of-
word models do not respect the semantics of the word. For example, words
“airplane”, “aeroplane”, “plane”, and “aircraft” are often used in the same
context. However, the vectors corresponding to these words are orthogonal in
the bag-of-words model. This issue presents a serious problem to understanding
sentences within the model. The other problem in the bag-of-word is that the
order of words in the phrase is not respected. The $n\text{-}gram$ does not
solve this problem so a similarity needs to be found for each word in the
sentence. Many researchers worked on word embedding to solve this problem. The
Skip-gram and continuous bag-of-words (CBOW) models of Mikolov et al. (2013a)
propose a simple single-layer architecture based on the inner product between
two word vectors.

Word embedding is a feature learning technique in which each word or phrase
from the vocabulary is mapped to a $N$ dimension vector of real numbers.
Various word embedding methods have been proposed to translate unigrams into
understandable input for machine learning algorithms. This work focuses on
Word2Vec, GloVe, and FastText, three of the most common methods that have been
successfully used for deep learning techniques. Recently, the Novel technique
of word representation was introduced where word vectors depend on the context
of the word called “Contextualized Word Representations” or “Deep
Contextualized Word Representations”.

####  2.4.1 Word2Vec

T. Mikolov et al. Mikolov et al. (2013a, b) presented "word to vector"
representation as an improved word embedding architecture. The Word2Vec
approach uses shallow neural networks with two hidden layers, continuous bag-
of-words (CBOW), and the Skip-gram model to create a high dimension vector for
each word. The Skip-gram model dives a corpus of words $w$ and context $c$
Goldberg and Levy (2014). The goal is to maximize the probability:

$arg\max_{\theta}\prod_{w\in T}\bigg{[}\prod_{c\in
c(w)}p(c\>|\>w;\theta)\bigg{]}$ (2)

where $T$ refers to Text, and $\theta$ is parameter of $p(c\>|\>w;\theta)$.

Figure 2 shows a simple CBOW model which tries to find the word based on
previous words, while Skip-gram tries to find words that might come in the
vicinity of each word. The weights between the input layer and output layer
represent $v\times N$ Rong (2014) as a matrix of $w$.

$h=W^{T}c=W^{T}_{k,.}:=v^{T}_{wI}$ (3)

This method provides a very powerful tool for discovering relationships in the
text corpus as well as similarity between words. For example, this embedding
would consider the two words such as “big” and “bigger” close to each other in
the vector space it assigns them.

Figure 2: The continuous bag-of-words (CBOW) architecture predicts the current
word based on the context, and the Skip-gram predicts surrounding words based
on the given current word Mikolov et al. (2013a).

#### Continuous Bag-of-Words Model

The continuous bag-of-words model is represented by multiple words for a given
target of words. For example, the word “airplane” and “military” as context
words for “air-force” as the target word. This consists of replicating the
input to hidden layer connections $\beta$ times which is the number of context
words Mikolov et al. (2013a). Thus, the bag-of-words model is mostly used to
represent an unordered collection of words as a vector. The first thing to do
is create a vocabulary, which means all the unique words in the corpus. The
output of the shallow neural network will be $w_{i}$ that the task as
“predicting the word given its context”. The number of words used depends on
the setting for the window size (common size is 4–5 words).

#### Continuous Skip-Gram Model

Another model architecture which is very similar to CBOW Mikolov et al.
(2013a) is the continuous Skip-gram model, however this model, instead of
predicting the current word based on the context, tries to maximize
classification of a word based on another word in the same sentence. The
continuous bag-of-words model and continuous Skip-gram model are used to keep
syntactic and semantic information of sentences for machine learning
algorithms.

####  2.4.2 Global Vectors for Word Representation (GloVe)

Another powerful word embedding technique that has been used for text
classification is Global Vectors (GloVe) Pennington et al. (2014). The
approach is very similar to the Word2Vec method, where each word is presented
by a high dimension vector and trained based on the surrounding words over a
huge corpus. The pre-trained word embedding used in many works is based on
400,000 vocabularies trained over Wikipedia 2014 and Gigaword 5 as the corpus
and 50 dimensions for word presentation. GloVe also provides other pre-trained
word vectorizations with 100, 200, 300 dimensions which are trained over even
bigger corpora, including Twitter content. Figure 3 shows a visualization of
the word distances over a sample data set using the same t-SNE technique
Maaten and Hinton (2008). The objective function is as follows:

$f(w_{i}-w_{j},\widetilde{w}_{k})=\frac{P_{ik}}{P_{jk}}$ (4)

where $w_{i}$ refers to the word vector of word $i$, and $P_{ik}$ denotes to
the probability of word $k$ to occur in the context of word $i$.

Figure 3: GloVe: Global Vectors for Word Representation.

####  2.4.3 FastText

Many other word embedding representations ignore the morphology of words by
assigning a distinct vector to each word Bojanowski et al. (2016). Facebook AI
Research lab released a novel technique to solve this issue by introducing a
new word embedding method called FastText. Each word, $w$, is represented as a
bag of character n-gram. For example, given the word “introduce” and $n=3$,
FastText will produce the following representation composed of character tri-
grams:

$<in,~{}int,~{}ntr,~{}tro,~{}rod,~{}odu,~{}duc,~{}uce,~{}ce>$

Note that the sequence <_int_ >, corresponding to the word here is different
from the tri-gram “ _int_ ” from the word introduce.

Suppose we have a dictionary of n-grams of size $G$, and given a word $w$
which is associated as a vector representation $z_{g}$ to each n-gram $g$. The
obtained scoring function Bojanowski et al. (2016) in this case is:

$s(w,c)=\sum_{g\in g_{w}}z_{g}^{T}v_{c}$ (5)

where $g_{w}\in\\{1,2,\ldots,G\\}$ .

Facebook published pre-trained word vectors for $294$ languages which are
trained on Wikipedia using FastText based on $300$ dimension. The FastText
used the Skip-gram model Bojanowski et al. (2016) with default parameters.

####  2.4.4 Contextualized Word Representations

Contextualized word representations are another word embedding technique which
is based on the context2vec Melamud et al. (2016) technique introduced by B.
McCann et al. The context2vec method uses bidirectional long short-term memory
(LSTM). M.E. Peters et al. Peters et al. (2018) built upon this technique to
create the deep contextualized word representations technique. This technique
contains both the main feature of word representation: (I) complex
characteristics of word use (e.g., syntax and semantics) and (II) how these
uses vary across linguistic contexts (e.g., to model polysemy) Peters et al.
(2018).

The main idea behind these word embedding techniques is that the resulting
word vectors are learned from a bidirectional language model (biLM), which
consist of both forward and backward LMs.

The forward LMs are as follows:

$p(t_{1},t_{2},\dots,t_{N})=\prod_{k=1}^{N}p(t_{k}|t_{1},t_{2},\dots,t_{k-1})$
(6)

The backward LMs are as follows:

$p(t_{1},t_{2},\dots,t_{N})=\prod_{k=1}^{N}p(t_{k}|t_{k+1},t_{k+2},\dots,t_{N})$
(7)

This formulation jointly maximizes the log-likelihood of the forward and
backward directions as follows:

$\sum_{k=1}^{N}\left(\begin{split}&\log
p(t_{k}|t_{1},\dots,t_{k-1};\Theta_{x},\overrightarrow{\Theta}_{LSTM},\Theta_{s})+\\\
&\log
p(t_{k}|t_{k+1},\dots,t_{N};\Theta_{x},\overleftarrow{\Theta}_{LSTM},\Theta_{s})\end{split}\right)$
(8)

where $\Theta_{x}$ is the token representation and $\Theta_{x}$ refers to the
softmax layer. Then, ELMo is computed as a task-specific weighting for all
biLM layers as follows:

$\begin{split}ELMo_{k}^{task}=E(R_{k};\Theta^{task})=\gamma^{task}\sum_{j=0}^{L}s_{j}^{task}h_{k,j}^{LM}\end{split}$
(9)

where $h_{k,j}^{LM}$ is calculated by:

$h_{k,j}^{LM}=\left[\overrightarrow{h}_{k,j}^{LM},\overleftarrow{h}_{k,j}^{LM}\right]$
(10)

where $s^{task}$ stands for softmax-normalized weights, and $\gamma^{task}$ is
the scalar parameter.

###  2.5 Limitations

Although the continuous bag-of-words model and continuous Skip-gram model are
used to keep syntactic and semantic information of per-sentences for machine
learning algorithms, there remains the issue how to keep full meaning of
coherent documents for machine learning.

Example:

Document: {“Maryam went to Paris on July 4th, 2018. She missed the
independence day fireworks and celebrations. This day is a federal holiday in
the United States commemorating the Declaration of Independence of the United
States on July 4, 1776. The Continental Congress declared that the thirteen
American colonies were no longer subject to the monarch of Britain and were
now united, free, and independent states. She wants to stay in the country for
next year and celebrate with her friends.”}

Sentence level of this document:

S1: {“Maryam went to Paris on July 4th, 2018.”}
S2: {“She missed the independence day fireworks and celebrations.”}
S3: {“This day is a federal holiday in the United States commemorating the
Declaration of Independence of the United States on July 4, 1776.”}
S4: {“The Continental Congress declared that the thirteen American colonies
were no longer subject to the monarch of Britain and were now united, free,
and independent states.”}
S5: {“She has a plan for next year to stay in the country and celebrate with
her friends.”}

Limitation:

Figure 4 shows how the feature extraction fails for per-sentence level. The
purple color shown in figure is the brief history of “This day”. Furthermore,
“This day” refers to “July 4th”. In S5, “She” refers to the S1 “Maryam”.

Figure 4: Limitation of document feature extraction by per-sentence level.

##  3 Dimensionality Reduction

Text sequences in term-based vector models consist of many features. Thus,
time complexity and memory consumption are very expensive for these methods.
To address this issue, many researchers use dimensionality reduction to reduce
the size of feature space. In this section, existing dimensionality reduction
algorithms are discussed in detail.

###  3.1 Component Analysis

####  3.1.1 Principal Component Analysis (PCA)

Principal component analysis (PCA) is the most popular technique in
multivariate analysis and dimensionality reduction. PCA is a method to
identify a subspace in which the data approximately lies Abdi and Williams
(2010). This means finding new variables that are uncorrelated and maximizing
the variance to “preserve as much variability as possible” Jolliffe and Cadima
(2016).

Suppose a data set ${x^{(i)};i=1,...,m}$ is given and
$x^{(\emph{i})}\in\mathbb{R}^{n}$ for each _i_ ($n\ll m$). The $j$th column of
matrix $X$ is vector, $x_{j}$ that is the observations on the $j$th variable.
The linear combination of $x_{j}$s can be written as:

$\sum_{j=1}^{m}a_{j}x_{j}=Xa$ (11)

where $a$ is a vector of constants $a_{1},a_{2},...,a_{m}$. The variance of
this linear combination can be given as:

$var(Xa)=a^{T}Sa$ (12)

where $S$ is the sample co-variance matrix. The goal is to find the linear
combination with maximum variance. This translates into maximizing
$a^{T}Sa-\lambda(a^{T}a-1)$, where $\lambda$ is a Lagrange multiplier.

PCA can be used as a pre-processing tool to reduce the dimension of a data set
before running a supervised learning algorithm on it ($x^{(i)}s$ as inputs).
PCA is also a valuable tool as a noise reduction algorithm and can be helpful
in avoiding the over-fitting problem Ng (2015). kernel principal component
analysis (KPCA) is another dimensionality reduction method that generalizes
linear PCA into the nonlinear case by using the kernel method Cao et al.
(2003).

####  3.1.2 Independent Component Analysis (ICA)

Independent component analysis (ICA) was introduced by H. Jeanny Hérault
(1984). This technique was then further developed by C. Jutten and J. Herault
Jutten and Herault (1991). ICA is a statistical modeling method where the
observed data are expressed as a linear transformation Hyvärinen et al.
(2001). Assume that 4$n$ linear mixtures ($x_{1},x_{2},\ldots,x_{n}$) are
observed where independent components:

$x_{j}=a_{j1}s_{1}+a_{j2}s_{2}+\ldots+a_{jn}s_{n}~{}\forall j$ (13)

The vector-matrix notation is written as:

$X=As$ (14)

Denoting them by $a_{i}$, the model can also be written Hyvärinen and Oja
(2000) as follows:

$X=\sum_{i=1}^{n}a_{i}s_{i}$ (15)

###  3.2 Linear Discriminant Analysis (LDA)

LDA is a commonly used technique for data classification and dimensionality
reduction Sugiyama (2007). LDA is particularly helpful where the within-class
frequencies are unequal and their performances have been evaluated on randomly
generated test data. Class-dependent and class-independent transformation are
two approaches to LDA in which the ratio of between class variance to within
class variance and the ratio of the overall variance to within class variance
are used respectively Balakrishnama and Ganapathiraju (1998).

Let $x_{i}\in\mathbb{R}^{d}$ which be $d$-dimensional samples and
$y_{i}\in\\{1,2,...,c\\}$ be associated target or output Sugiyama (2007),
where $n$ is the number of documents and $c$ is the number of categories. The
number of samples in each class is calculated as follows:

$S_{w}=\sum_{l=1}^{c}s_{l}$ (16)

where

$S_{i}=\sum_{x\in
w_{i}}(x-\mu_{i})(x-\mu_{i})^{T},~{}\mu_{i}=\frac{1}{N_{i}}\sum_{x\in w_{i}}x$
(17)

The generalization between the class scatter matrix is defined as follows:

$S_{B}=\sum_{i=1}^{c}N_{i}(\mu_{i}-\mu)(\mu_{i}-\mu)^{T}$ (18)

where

$\mu=\frac{1}{N}\sum_{\forall x}x$ (19)

Respect to $c-1$ projection vector of $w_{i}$ that can be projected into $W$
matrix:

$W=\left[w_{1}|w_{2}|\ldots|w_{c-1}\right]$ (20) $y_{i}=w_{i}^{T}x$ (21)

Thus, the $\mu$ (mean) vector and $S$ matrices (scatter matrices) for the
projected to lower dimension as follows:

$\displaystyle\widetilde{S}_{w}=$ $\displaystyle\sum_{i=1}^{c}\sum_{y\in
w_{i}}(y-\widetilde{\mu}_{i})(y-\widetilde{\mu}_{i})^{T}$ (22)
$\displaystyle\widetilde{S}_{B}=$
$\displaystyle\sum_{i=1}^{c}(\widetilde{\mu}_{i}-\widetilde{\mu})(\widetilde{\mu}_{i}-\widetilde{\mu})^{T}$
(23)

If the projection is not scalar ($c-1$ dimensions), the determinant of the
scatter matrices will be used as follows:

$J(W)=\frac{|\widetilde{S}_{B}|}{|\widetilde{S}_{W}|}$ (24)

From the fisher discriminant analysis (FDA) Sugiyama (2006, 2007), we can re-
write the equation as:

$J(W)=\frac{|W^{T}S_{B}W|}{|W^{T}S_{W}W|}$ (25)

###  3.3 Non-Negative Matrix Factorization (NMF)

Non-negative matrix factorization (NMF) or non-negative matrix approximation
has been shown to be a very powerful technique for very high dimensional data
such as text and sequences analysis Pauca et al. (2004). This technique is a
promising method for dimension reduction Tsuge et al. (2001). In this section,
a brief overview of NMF is discussed for text and document data sets. Given a
non-negative $n\times m$ in matrix $V$ is an approximation of:

$V\approx WH$ (26)

where $W=\mathbb{R}^{n\times r}$ and $H=\mathbb{R}^{r\times m}$. Suppose
$(n+m)~{}r<nm$, then the product $WH$ can be regarded as a compressed form of
the data in $V$. Then $v_{i}$ and $h_{i}$ are the corresponding columns of $V$
and $H$. The computation of each corresponding column can be re-written as
follows:

$u_{i}\approx Wh_{i}$ (27)

The computational time of each iteration, as introduced by S. Tsuge et al.
Tsuge et al. (2001), can be written as follows:

$\overline{H}_{ij}=H_{ij}\frac{(W^{T}V)_{ij}}{(W^{T}WH)_{ij}}$ (28)
$\overline{W}_{ij}=W_{ij}\frac{(VH^{T})_{ij}}{(WHH^{T})_{ij}}$ (29)

Thus, the local minimum of the objective function is calculated as follows:

$F=\sum_{i}\sum_{j}(V_{ij}-(WH)_{ij})^{2}$ (30)

The maximization of the objective function can be re-written as follows:

$F=\sum_{i}\sum_{j}(V_{ij}\log((WH)_{ij})-(WH)_{ij})$ (31)

The objective function, given by the Kullback–Leibler Kullback and Leibler
(1951); Johnson and Sinanovic (2001) divergence, is defined as follows:

$\displaystyle\overline{H}_{ij}$
$\displaystyle=H_{ij}\sum_{k}W_{kj}\frac{V_{kj}}{(WH)_{kj}}$ (32)
$\displaystyle\hat{W}_{ij}$
$\displaystyle=W_{ij}\sum_{k}{\frac{V_{ik}}{(WH)_{ik}}}H_{jk}$ (33)
$\displaystyle\overline{W}_{ij}$
$\displaystyle=\frac{\hat{W_{ij}}}{\sum_{k}\hat{W_{kj}}}$ (34)

This NMF-based dimensionality reduction contains the following 5 steps Tsuge
et al. (2001) (step VI is optional but commonly used in information retrieval:

  1. (I)

Extract index term after pre-processing stem like feature extraction and text
cleaning as discussed in Section 2. Then we have $n$ documents with $m$
features;

  2. (II)

Create $n$ documents ($d\in\\{d_{1},d_{2},\ldots,d_{n}\\}$), where vector
$a_{ij}=L_{ij}\times G_{i}$ where $L_{ij}$ refers to local weights of
$i_{-th}$ term in document $j$, and $G_{i}$ is global weights for document
$i$;

  3. (III)

Apply NMF to all terms in all documents one by one;

  4. (IV)

Project the trained document vector into $r$-dimensional space;

  5. (V)

Using the same transformation, map the test set into the $r$-dimensional
space;

  6. (VI)

Calculate the similarity between the transformed document vectors and a query
vector.

###  3.4 Random Projection

Random projection is a novel technique for dimensionality reduction which is
mostly used for high volume data set or high dimension feature spaces. Texts
and documents, especially with weighted feature extraction, generate a huge
number of features. Many researchers have applied random projection to text
data Bingham and Mannila (2001); Chakrabarti et al. (2003) for text mining,
text classification, and dimensionality reduction. In this section, we review
some basic random projection techniques. As shown in Figure 5, the overview of
random projection is shown.

####  3.4.1 Random Kitchen Sinks

The key idea of random kitchen sinks Rahimi and Recht (2009) is sampling via
monte carlo integration Morokoff and Caflisch (1995) to approximate the kernel
as part of dimensionality reduction. This technique works only for shift-
invariant kernel:

$K(x,x^{\prime})=<\phi(x),\phi(x^{\prime})>\approx K(x-x^{\prime})$ (35)

where shift-invariant kernel, which is an approximation kernel of:

$K(x-x^{\prime})=z(x)z(x^{\prime})$ (36)
$K(x,x^{\prime})=\int_{R^{D}}{P(w)e^{iw^{T}(x-x^{\prime})}}$ (37)

where $D$ is the target number of samples, $P(w)$ is a probability
distribution, $w$ stands for random direction, and $w\in\mathbb{R}^{F\times
D}$ where $F$ is the number of features and $D$ is the target.

Figure 5: The plot on the left shows how we generate random direction, and the
plot on the right shows how we project the data set into the new space using
complex numbers.

$K(x,x^{\prime})=K(x-x^{\prime})\approx\frac{1}{D}{\sum_{j=1}^{D}e^{iw_{j}^{T}(x-x^{\prime})}}$
(38) $\left.\begin{aligned}
\frac{1}{D}{\sum_{j=1}^{D}e^{iw_{j}^{T}(x-x^{\prime})}}=&\frac{1}{D}{\sum_{j=1}^{D}e^{iw_{j}^{T}x}e^{iw_{j}^{T}x^{\prime}}}=\\\
&\frac{1}{\sqrt{D}}{\sum_{j=1}^{D}e^{iw_{j}^{T}x}}\frac{1}{\sqrt{D}}{\sum_{j=1}^{D}e^{iw_{j}^{T}x^{\prime}}}\end{aligned}\right.$
(39) $k(x-x^{\prime})\approx\phi(x)\phi(x^{\prime})$ (40)
$\phi(x)=\cos(w^{T}x+b_{i})$ (41)

where the $b_{i}$ is uniform random variable ( $b_{i}\in[0,\pi]$ ).

####  3.4.2 Johnson Lindenstrauss Lemma

William B. Johnson and Joram Lindenstrauss Johnson et al. (1986); Dasgupta and
Gupta (2003) proved that for any $n$ point Euclidean space can be bounded in
$k=O(\frac{logn}{\epsilon^{2}})$ for any $u~{}$ and $v\in n$ and
$~{}n\in\mathbb{R}^{d}$: $\exists
f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}|\epsilon\in[0,1]$. With $x=u-v$ to
the lower bound of the success probability.

$(i-\epsilon)||u-v||^{2}\leq||f(u)-f(v)||^{2}\leq(i+\epsilon)||u-v||^{2}$ (42)

#### Johnson Lindenstrauss Lemma Proof Vempala, S. S. (2009):

For any $V$ sets of data point from $n$ where $V\in n$ and random variable
$w\in R^{k\times d}$:

$Pr[success]\geq 1-2m^{2}e^{\frac{-k(\epsilon^{2}-\epsilon^{3})}{4}}$ (43)

If we let $k=\frac{16logn}{\epsilon^{2}}$ :

$\begin{split}1-2m^{2}e^{\frac{-k(\epsilon^{3}-\epsilon^{3})}{4}}\geq
1-2m^{2}e^{\frac{(-\frac{8logn}{\epsilon^{2}})(\epsilon^{2}-\epsilon^{3})}{4}}\\\
1-2m^{2}e^{\frac{-\frac{16logn}{\epsilon^{2}})(\epsilon^{3}-\epsilon^{3})}{4}}=\\\
1-2m^{4\epsilon-2}>1-2m^{-\frac{1}{2}}>0\end{split}$ (44)

#### Lemma 1 Proof Vempala, S. S. (2009):

Let $\Psi$ be a random variable with $k$ degrees of freedom, then for
$\epsilon\in[0,1]$

$Pr[(1-\epsilon)k\leq\Psi\leq(1+\epsilon)k]\geq
1-2e^{\frac{-k(\epsilon^{2}-\epsilon^{3})}{4}}$ (45)

We start with Markov’s inequality Mao and Yuan (2016):

$Pr[(\Psi\geq(1-\epsilon)k)]\leq\frac{E[\Psi]}{(1-\epsilon)k}$ (46)
$\begin{split}Pr[e^{\lambda\Psi}\geq
e^{\lambda(1-\epsilon)k)}]\leq\frac{E[e^{\lambda\Psi}]}{e^{\lambda(1-\epsilon)k}}\\\
E[e^{\lambda\Psi}]=(1-2\lambda)^{-\frac{k}{2}}\end{split}$ (47)

where $\lambda~{}<~{}0.5$ and using the fact of $(1-\epsilon)\leq
e^{\epsilon-\frac{(\epsilon^{2}-\epsilon^{3})}{2}}$; thus, we can proof
$Pr[(\Psi\geq(1-\epsilon)k)]\leq\frac{E[\Psi]}{(1-\epsilon)k}$ and the
$Pr[(\Psi\leq(1+\epsilon)k)]\leq\frac{E[\Psi]}{(1+\epsilon)F}$ is similar.

$\frac{(1+\epsilon)}{e^{\epsilon}}\leq\bigg{(}\frac{e^{\epsilon-\frac{(\epsilon^{2}-\epsilon^{3})}{2}}}{e^{\epsilon}}\bigg{)}^{\frac{k}{2}}=e^{\frac{-k(\epsilon^{3}-\epsilon^{3})}{4}}$
(48) $\left.\begin{aligned}
Pr[\overline{(1-\epsilon)k\leq\Psi\leq(1+\epsilon)k}]\leq\\\
Pr[(1-\epsilon)k\geq\Psi\cup\Psi\leq(1+\epsilon)k]=\\\
2e^{\frac{-k(\epsilon^{3}-\epsilon^{3})}{4}}\end{aligned}\right.$ (49)

#### Lemma 2 Proof Vempala, S. S. (2009):

Let $w$ be a random variable of $w\in\mathbb{R}^{k\times d}$ and $k~{}<~{}d$,
$x$ is data points $x\in\mathbb{R}^{d}$ then for any $\epsilon\in[0,1]$ :

$\begin{split}Pr[(1-\epsilon)||x||^{2}\leq||\frac{1}{\sqrt{k}}wx||^{2}\leq\\\
(1+\epsilon)||x||^{2}]\geq
1-2e^{\frac{-k(\epsilon^{3}-\epsilon^{3})}{4}}\end{split}$ (50)

In Equation (50), $\frac{1}{\sqrt{k}}wx$ is the random approximation value and
$\widehat{x}=wx$, so we can rewrite the Equation (50) by
$Pr[(1-\epsilon)||x||^{2}\leq||\frac{1}{\sqrt{k}}\widehat{x}||^{2}\leq(1+\epsilon)||x||^{2}]\geq
1-2e^{\frac{-k(\epsilon^{3}-\epsilon^{3})}{4}}$.

Call $\zeta_{i}=\frac{\widehat{x_{i}}}{||x||}\sim N(0,1)$ and
$\Psi=\sum_{i=1}^{k}\zeta_{i}^{2}$ thus:

$\begin{split}Pr[(1-\epsilon)k\leq||\sum_{i=0}^{k}\zeta_{i}||^{2}\leq(1+\epsilon)k]=\\\
Pr[(1-\epsilon)k\leq||w||^{2}\leq(1+\epsilon)k]\end{split}$ (51)

where we can prove Equation (51) by using Equation (45):

$Pr[(1-\epsilon)k\leq\Psi\leq(1+\epsilon)k]\geq
1-2e^{\frac{-k(\epsilon^{3}-\epsilon^{3})}{4}}$ (52)

###  3.5 Autoencoder

An autoencoder is a type of neural network that is trained to attempt to copy
its input to its output Goodfellow et al. (2016). The autoencoder has achieved
great success as a dimensionality reduction method via the powerful
reprehensibility of neural networks Wang et al. (2014). The first version of
autoencoder was introduced by D.E. Rumelhart et al. Rumelhart et al. (1985) in
1985. The main idea is that one hidden layer between input and output layers
has fewer units Liang et al. (2017) and could thus be used to reduce the
dimensions of a feature space. Especially for texts, documents, and sequences
that contain many features, using an autoencoder could help allow for faster,
more efficient data processsing.

####  3.5.1 General Framework

As shown in Figure 6, the input and output layers of an autoencoder contain
$n$ units where $x=\mathbb{R}^{n}$, and hidden layer $Z$ contains $p$ units
with respect to $p<n$ Baldi (2012). For this technique of dimensionality
reduction, the dimensions of the final feature space are reduced from
$n\rightarrow p$. The encoder representation involves a sum of the
representation of all words (for bag-of-words), reflecting the relative
frequency of each word AP et al. (2014):

$a(x)=c+\sum_{i=1}^{|x|}W_{.,x_{i}},\phi(x)=h(a(x))$ (53)

where $h(.)$ is an element-wise non-linearity such as the sigmoid (Equation
(79)).

Figure 6: This figure shows how a simple autoencoder works. The model depicted
contains the following layers: $Z$ is code and two hidden layers are used for
encoding and two are used for decoding.

####  3.5.2 Conventional Autoencoder Architecture

A convolutional neural networks (CNN)-based autoencoder can be divided into
two main steps Masci et al. (2011) (encoding and decoding).

$O_{m}(i,j)=a\bigg{(}\sum_{d=1}^{D}\sum_{u=-2k-1}^{2k+1}\sum_{v=-2k-1}^{2k+1}F^{(1)}_{m_{d}}(u,v)I_{d}(i-u,j-v)\bigg{)}~{}~{}\quad\forall
m=1,\cdots,n$ (54)

where $F\in\\{F^{(1)}_{1},F^{(1)}_{2},\ldots,F^{(1)}_{n},\\}$ which is a
convolutional filter, with convolution among an input volume defined by
$I=\left\\{I_{1},\cdots,I_{D}\right\\}$ which learns to represent input
combining non-linear functions:

$z_{m}=O_{m}=a(I*F^{(1)}_{m}+b^{(1)}_{m})\quad m=1,\cdots,m$ (55)

where $b^{(1)}_{m}$ is the bias, and the number of zeros we want to pad the
input with is such that: dim(I) = dim(decode(encode(I))). Finally, the
encoding convolution is equal to:

$\begin{split}O_{w}=O_{h}&=(I_{w}+2(2k+1)-2)-(2k+1)+1\\\
&=I_{w}+(2k+1)-1\end{split}$ (56)

The decoding convolution step produces $n$ feature maps $z_{m=1,\ldots,n}$.
The reconstructed results $\hat{I}$ is the result of the convolution between
the volume of feature maps $Z=\\{z_{i=1}\\}^{n}$ and this convolutional
filters volume $F^{(2)}$ Chen et al. (2015); Geng et al. (2015); Masci et al.
(2011).

$\tilde{I}=a(Z*F^{(2)}_{m}+b^{(2)})$ (57)
$\begin{split}O_{w}=O_{h}=&(I_{w}+(2k+1)-1)-\\\
&(2k+1)+1=I_{w}=I_{h}\end{split}$ (58)

where Equation (58) shows the decoding convolution with $I$ dimensions.
Input’s dimensions are equal to the output’s dimensions.

####  3.5.3 Recurrent Autoencoder Architecture

A recurrent neural network (RNN) is a natural generalization of feedforward
neural networks to sequences Sutskever et al. (2014). Figure 7 illustrate
recurrent autoencoder architecture. A standard RNN compute the econding as a
sequences of output by iteration:

$\displaystyle h_{t}$ $\displaystyle=sigm(W^{hx}x_{t}+W^{hh}h_{t-1})$ (59)
$\displaystyle y_{t}$ $\displaystyle=W^{y^{h}}h_{t}$ (60)

where x is inputs $(x_{1},...,x_{T})$ and $y$ refers to output
($y_{1},...,y_{T}$). A multinomial distribution (1-of-K coding) can be output
using a softmax activation function Cho et al. (2014):

$p(x_{t,j}=1\>|\>x_{t-1,...,x_{1}})=\frac{\exp(w_{j}h_{t})}{\sum_{j^{\prime}=1}^{K}\exp(w_{j^{\prime}}h_{t})}$
(61)

By combining these probabilities, we can compute the probability of the
sequence $x$ as:

$p(x)=\prod_{t=1}^{T}p(x_{t}\>|\>x_{t-1},...,x_{1})$ (62)

Figure 7: A recurrent autoencoder structure.

###  3.6 T-distributed Stochastic Neighbor Embedding (t-SNE)

T-SNE is a nonlinear dimensionality reduction method for embedding high-
dimensional data. This method is mostly commonly used for visualization in a
low-dimensional feature space Maaten and Hinton (2008), as shown in Figure 8.
This approach is based on G. Hinton and S. T. Roweis Hinton and Roweis (2003).
SNE works by converting the high dimensional Euclidean distances into
conditional probabilities which represent similarities Maaten and Hinton
(2008). The conditional probability $p_{j|i}$ is calculated by:

$p_{j|i}=\frac{\exp\left(-\frac{||x_{i}-x_{j}||^{2}}{2\sigma_{i}^{2}}\right)}{\sum_{k\neq
i}\exp\left(-\frac{||x_{i}-x_{k}||^{2}}{2\sigma_{i}^{2}}\right)}$ (63)

where $\sigma_{i}$ is the variance of the centered on data point $x_{i}$. The
similarity of $y_{j}$ to $y_{i}$ is calculated as follows:

$q_{j|i}=\frac{\exp\left(-||y_{i}-y_{j}||^{2}\right)}{\sum_{k\neq
i}\exp\left(-||y_{i}-y_{k}||^{2}\right)}$ (64)

The cost function $C$ is as follows:

$C=\sum_{i}KL(p_{i}|Q_{i})$ (65)

where $KL(P_{i}|Q_{i})$ is the Kullback–Leibler divergence Joyce (2011), which
is calculated as:

$KL(P_{i}|Q_{i})=\sum_{j}p_{j|i}\log\frac{p_{j|i}}{q_{j|i}}$ (66)

The gradient update with a momentum term is as follows:

$\gamma^{(t)}=\gamma^{(t-1)}+\eta\frac{\delta
C}{\delta\gamma}+\alpha(t)\left(\gamma^{(t-1)-\gamma^{(t-2)}}\right)$ (67)

where $\eta$ is the learning rate, $\gamma^{(t)}$ refers to the solution at
iteration t, and $\alpha(t)$ indicates momentum at iteration t. Now we can re-
write symmetric SNE in the high-dimensional space and a joint probability
distribution, $Q$, in the low-dimensional space as follows Maaten and Hinton
(2008):

$C=KL(P||Q)=\sum_{i}\sum_{j}p_{ij}\log\frac{p_{ij}}{q_{ij}}$ (68)

in the high-dimensional space $p_{ij}$ is:

$p_{ij}=\frac{\exp\left(-\frac{||x_{i}-x_{j}||^{2}}{2\sigma^{2}}\right)}{\sum_{k\neq
l}\exp\left(-\frac{||x_{i}-x_{l}||^{2}}{2\sigma^{2}}\right)}$ (69)

The gradient of symmetric S is as follows:

$\frac{\delta C}{\delta y_{i}}=4\sum_{j}(p_{ij}-q_{ij})(y_{i}-y_{j})$ (70)

Figure 8: This figure presents the t-distributed stochastic neighbor embedding
(t-SNE) visualization of Word2vec of the Federal Railroad Administration (FRA)
data set.

##  4 Existing Classification Techniques

In this section, we outline existing text and document classification
algorithms. First, we describe the Rocchio algorithm which is used for text
classification. Then, we address two popular techniques in ensemble learning
algorithms: Boosting and bagging. Some methods, such as logistic regression,
Naïve Bayes, and k-nearest neighbor, are more traditional but still commonly
used in the scientific community. Support vector machines (SVMs), especially
kernel SVMs, are also broadly used as a classification technique. Tree-based
classification algorithms, such as decision tree and random forests are fast
and accurate for document categorization. We also describe neural network
based algorithms such as deep neural networks (DNN), CNN, RNN, deep belief
network (DBN), hierarchical attention networks (HAN), and combination
techniques.

###  4.1 Rocchio Classification

The Rocchio algorithm was first introduced by J.J. Rocchio Rocchio (1971) in
1971 as method of using relevance feedback to query full-text databases. Since
then, many researchers have addressed and developed this technique for text
and document classification Partalas et al. (2015); Sowmya et al. (2016). This
classification algorithm uses TF-IDF weights for each informative word instead
of boolean features. Using a training set of documents, the Rocchio algorithm
builds a prototype vector for each class. This prototype is an average vector
over the training documents’ vectors that belong to a certain class. It then
assigns each test document to the class with the maximum similarity between
the test document and each of the prototype vectors Korde and Mahender (2012).
The average vector computes the centroid of a class _c_ (center of mass of its
members):

$\vec{\mu}(c)=\frac{1}{|D_{c}|}\sum_{d\in D_{c}}\vec{v}_{d}$ (71)

where $D_{c}$ is the set of documents in _D_ that belongs to class _c_ and
$\vec{v}_{d}$ is the weighted vector representation of document _d_. The
predicted label of document _d_ is the one with the smallest Euclidean
distance between the document and the centroid:

$c^{*}=\operatorname*{arg\,min}_{c}\lVert\vec{\mu}_{c}-\vec{v}_{d}\rVert$ (72)

Centroids can be normalized to unit-length as follows:

$\vec{\mu}_{c}=\frac{\sum_{d\in D_{c}}\vec{v}_{d}}{\lVert\sum_{d\in
D_{c}}\vec{v}_{d}\rVert}$ (73)

Therefore, the label of test documents can be obtained as follows:

$c_{*}=\operatorname*{arg\,min}_{c}\vec{\mu}_{c}\cdot\vec{v}_{d}$ (74)

#### Limitation of Rocchio Algorithm

The Rocchio algorithm for text classifcation contains many limitations such as
the fact that the user can only retrieve a few relevant documents using this
model Selvi et al. (2017). Furthermore, this algorithms’ results illustrate by
taking semantics into consideration Albitar et al. (2012).

###  4.2 Boosting and Bagging

Voting classification techniques, such as bagging and boosting, have been
successfully developed for document and text data set classification Farzi and
Bolandi (2016). While boosting adaptively changes the distribution of the
training set based on the performance of previous classifiers, bagging does
not look at the previous classifier Bauer and Kohavi (1999).

####  4.2.1 Boosting

The boosting algorithm was first introduced by R.E. Schapire Schapire (1990)
in 1990 as a technique for boosting the performance of a weak learning
algorithm. This technique was further developed by Freund Freund (1992);
Bloehdorn and Hotho (2004).

Figure 9 shows how a boosting algorithm works for 2D data sets, as shown we
have labeled the data, then trained by multi-model architectures (ensemble
learning). These developments resulted in the AdaBoost (Adaptive Boosting)
Freund et al. (1995). Suppose we construct $D_{t}$ such that
$D_{1}(i)=\frac{1}{m}$ given $D_{t}$ and $h_{t}$:

$\begin{split}D_{t+1}(i)&=\frac{D_{t}(i)}{Z_{t}}\times\begin{cases}e^{-\alpha_{t}}&ify_{i}=h_{t}(x_{i})\\\
e^{\alpha_{t}}&ify_{i}\neq h_{t}(x_{i})\end{cases}\\\
&=\frac{D_{t}(i)}{Z_{t}}exp(-\alpha y_{i}h_{i}(x_{i}))\end{split}$ (75)

where $Z_{t}$ refers to the normalization factor and $\alpha_{t}$ is as
follows:

$\alpha_{t}=\frac{1}{2}\ln\bigg{(}\frac{1-\epsilon_{t}}{\epsilon_{t}}\bigg{)}\\\
\vspace{-6pt}$ (76)

Figure 9: This figure is the boosting technique architecture.

As shown in Algorithm 1, training set S of size $m$, inducer $\tau$ and
integer $N$ as input. Then this algorithm find the weights of each $x_{j}$,
and finally, the output is the optimal classifier (_$C^{*}$_).

Algorithm 1 The AdaBoost method

input :

training set S of size $m$, inducer $\tau$, integer $N$

for  _ $i=1$ to $N$_ do

$C_{i}=\tau(S^{\prime})$ $\displaystyle\epsilon_{i}=\frac{1}{m}\sum_{x_{j}\in
S^{\prime};C_{i}(x_{j})\notin y_{i}}weight(x)$ if  _$\epsilon_{i}
>\frac{1}{2}$_ then

set S’ to a bootstrap sample from S with weight 1 for all instance and go top

endif

$\beta_{i}=\frac{\epsilon_{i}}{1-\epsilon_{i}}$ for  _ $x_{i}\in S^{\prime}$_
do

if  _$C_{i}(x_{j})=y_{i}$_ then

$weight(x_{j})=weight(x_{j}).\beta_{i}$

endif

endfor

Normalize weights of instances

endfor

$\displaystyle C^{*}(x)=arg\max_{y\in
Y}\sum_{i,C_{i}(x)=y}\log\frac{1}{\beta_{i}}$ output : Classifier $C^{*}$

The final classifier formulation can be written as:

$H_{f}(x)=sign\bigg{(}\sum_{t}\alpha_{t}h_{t}(x)\bigg{)}$ (77)

####  4.2.2 Bagging

The bagging algorithm was introduced by L. Breiman Breiman (1996) in 1996 as a
voting classifier method. The algorithm is generated by different bootstrap
samples Bauer and Kohavi (1999). A bootstrap generates a uniform sample from
the training set. If $N$ bootstrap samples $B_{1},B_{2},\ldots,B_{N}$ have
been generated, then we have $N$ classifiers ($C$) which $C_{i}$ is built from
each bootstrap sample $B_{i}$. Finally, our classifier $C$ contain or
generated from $C_{1},C_{2},...,C_{N}$ whose output is the class predicted
most often by its sub-classifiers, with ties broken arbitrarily Bauer and
Kohavi (1999); Breiman (1996). Figure 10 shows a simple bagging algorithm
which trained $N$ models. As shown in Algorithm 2, We have training set  _S_
which is trained and find the best classifier  _C_.

Figure 10: This figure shows a simple model of the bagging technique.

input :

training set S, inducer $\tau$, integer $N$

for  _$i=1$ to $N$_ do

$S^{\prime}$ = bootstrap sample from S $C_{i}$ = $\tau(S^{\prime})$

endfor

$\displaystyle C^{*}(x)=arg\max_{y\in Y}\sum_{i,C_{i}=y}1$ output : Classifier
$C^{*}$

Algorithm 2 Bagging

####  4.2.3 Limitation of Boosting and Bagging

Boosting and bagging methods also have many limitations and disadvantages,
such as the computational complexity and loss of interpretability Geurts
(2000), which means that the feature importance could not be discovered by
these models.

###  4.3 Logistic Regression

One of the earliest methods of classification is logistic regression (LR). LR
was introduced and developed by statistician David Cox in 1958 Cox (2018). LR
is a linear classifier with decision boundary of $\theta^{T}x=0$. LR predicts
probabilities rather than classes Fan et al. (2008); Genkin et al. (2007).

####  4.3.1 Basic Framework

The goal of LR is to train from the probability of variable $Y$ being 0 or 1
given $x$. Let us have text data which is $X\in\mathbb{R}^{n\times d}$. If we
have binary classification problems, the Bernoulli mixture models function
should be used Juan and Vidal (2002) as follows:

$\begin{split}L(\theta\>|\>x)=&~{}p(y\>|\>x;\theta)=\\\
&\prod_{i=1}^{n}\beta(y_{i}\>|\>sigm(x_{i}\theta))=\\\
&\prod_{i=1}^{n}sigm(x_{i})^{y_{i}}(1-sigm(x_{i}))^{1-y_{i}}=\\\
&\prod_{i=1}^{n}\bigg{[}\frac{1}{1+e^{-x_{i}\theta}}\bigg{]}^{y_{i}}\bigg{[}1-\frac{1}{1+e^{-x_{i}\theta}}\bigg{]}^{(1-y_{i})}\end{split}$
(78)

where $x_{i}\theta=\theta_{0}+\sum_{j=1}^{d}(x_{ij}\theta_{j})$, and $sigm(.)$
is a sigmoid function which is defined as shown in Equation (79).

$sigm(\eta)=\frac{1}{1-e^{-\eta}}=\frac{e^{\eta}}{1-e^{\eta}}$ (79)

####  4.3.2 Combining Instance-Based Learning and LR

The LR model specifies the probability of binary output $y_{i}=\\{0,1\\}$
given the input $x_{i}$. we can consider posterior probability as:

$\pi_{0}=P(y_{0}=+1\>|\>y_{i})$ (80)

where:

$\frac{\pi_{0}}{1-\pi_{0}}=\frac{P(y_{i}\>|\>y_{0}=+1)}{P(y_{i}\>|\>y_{0}=+1)}.\frac{p_{0}}{1-p_{0}}$
(81)

where $p$ is the likelihood ratio it could be re-written as:

$\displaystyle\frac{\pi_{0}}{1-\pi_{0}}$
$\displaystyle=p.\frac{p_{0}}{1-p_{0}}$ (82)
$\displaystyle\log\bigg{(}\frac{\pi_{0}}{1-\pi_{0}}\bigg{)}$
$\displaystyle=\log(p)+w_{0}$ (83)

with respect to:

$w_{0}=\log(p_{0})-\log(1-p_{0})$ (84)

To obey the basic principle underlying instance-based learning (IBL) Cheng and
Hüllermeier (2009), the classifier should be a function of the distance
$\delta_{i}$. $p$ will be large if $\delta_{i}\rightarrow 0$ then $y_{i}=+1$,
and small for $y_{i}=-1$. $p$ should be close to $1$ if
$\delta_{i}\rightarrow\infty$; then, neither in favor of $y_{0}=+1$ nor in
favor of $y_{0}=-1$, so the parameterized function is as follows:

$p=p(\delta)=\exp\big{(}y_{i}.\frac{\alpha}{\delta}\big{)}$ (85)

Finally,

$\log\bigg{(}\frac{\pi_{0}}{1-\pi_{0}}\bigg{)}=w_{0}+\alpha\sum_{x_{i}\in
N(x_{0})}k(x_{0},x_{i}).y_{i}$ (86)

where $k(x_{0},x_{i})$ is similarity measure.

####  4.3.3 Multinomial Logistic Regression

Multinomial (or multilabeled) logistic classification Krishnapuram et al.
(2005) uses the probability of $x$ belonging to class $i$ (as defined in
Equation (87))

$p\left(y^{(i)}=1\>|\>x,\theta\right)=\frac{\exp\left({\theta^{(i)}}^{T}x\right)}{\sum_{j=1}^{m}\exp\left({\theta^{(i)}}^{T}x\right)}$
(87)

where $\theta^{(i)}$ is the weight vector corresponding to class $i$.

For binary classification ($m=2$) which is known as a basic LR, but for
multinomial logistic regression ($m>2$) is usually uses the $softmax$
function.

The normalization function is:

$\sum_{i=1}^{m}p\left(y^{(i)}=1\>|\>x,\theta\right)=1$ (88)

In a classification task as supervised learning context, the component of
$\theta$ is calculated from the subset of the training data $D$ which belongs
to class $i$ where $i\in\\{1,\ldots,n\\}$. To perform maximum likelihood (ML)
estimation of $\theta$, we need to maximize the log-likelihood function as
follows:

$\begin{split}\ell(\theta)&=\sum_{j=1}^{n}\log
p\left(y_{j}=1\>|\>x_{j},\theta\right)\\\
&=\sum_{j=1}^{n}\left[\sum_{i=1}^{m}y^{(i)}_{j}{\theta^{(i)}}^{T}x_{j}-\log\sum_{i=1}^{m}\exp\left({\theta^{(i)}}^{T}x_{j}\right)\right]\end{split}$
(89)

The adoption of a maximum a posteriori (MAP) estimates as follows:

$\hat{\theta}_{MAP}=arg\max_{\theta}L(\theta)=arg\max_{\theta}\left[\ell(\theta)+\log
p(\theta)\right]$ (90)

####  4.3.4 Limitation of Logistic Regression

Logistic regression classifier works well for predicting categorical outcomes.
However, this prediction requires that each data point be independent Huang
(2015) which is attempting to predict outcomes based on a set of independent
variables Guerin (2016)

###  4.4 Naïve Bayes Classifier

Naïve Bayes text classification has been widely used for document
categorization tasks since the 1950s Kaufmann (1969); Porter (1980). The Naïve
Bayes classifier method is theoretically based on Bayes theorem, which was
formulated by Thomas Bayes between 1701–1761 Pearson (1925); Hill (1968)).
Recent studies have widely addressed this technique in information retrieval
Qu et al. (2018). This technique is a generative model, which is the most
traditional method of text categorization. We start with the most basic
version of NBC which was developed by using TF (bag-of-word), a feature
extraction technique which counts the number of words in documents.

####  4.4.1 High-Level Description of Naïve Bayes Classifier

If the number of documents ($n$) fit into $k$ categories where
$k\in\\{c_{1},c_{2},...,c_{k}\\}$, the predicted class as output is $c\in C$.
The Naïve Bayes algorithm can be described as follows:

$P(c\>|\>d)=\frac{P(d\>|\>c)P(c)}{P(d)}$ (91)

where $d$ is document and $c$ indicates classes.

$\begin{split}C_{MAP}&=~{}arg\max_{c\in C}P(d\>|\>c)P(c)\\\ &=arg\max_{c\in
C}P(x_{1},x_{2},...,x_{n}\>|\>c)p(c)\end{split}$ (92)

This model is used as baseline of many papers which is word-level of Naïve
Bayes classifier Kim et al. (2006); McCallum et al. (1998) as follows:

$P(c_{j}\>|\>d_{i};\hat{\theta})=\frac{P(c_{j}\>|\>\hat{\theta})P(d_{i}\>|\>c_{j};\hat{\theta_{j}})}{P(d_{i}\>|\>\hat{\theta})}$
(93)

####  4.4.2 Multinomial Naïve Bayes Classifier

If the number of documents ($n$) fit into $k$ categories where
$k\in\\{c_{1},c_{2},...,c_{k}\\}$ the predicted class as output is $c\in C$.
The Naïve Bayes algorithm can be written as:

$P(c\>|\>d)=\frac{P(c)\prod_{w\in d}P(d\>|\>c)^{n_{wd}}}{P(d)}$ (94)

where $n_{wd}$ is denoted to the number of times word $w$ occurs in document,
and $P(w|c)$ is the probability of observing word $w$ given class $c$ Frank
and Bouckaert (2006).

$P(w|c)$ is calculated as:

$P(w\>|\>c)=\frac{1+\sum_{d\in D_{c}}n_{wd}}{k+\sum_{w^{\prime}}\sum_{d\in
D_{c}}n_{w^{\prime}d}}$ (95)

####  4.4.3 Naïve Bayes Classifier for Unbalanced Classes

One of the limitations of NBC is that the technique performs poorly on data
sets with unbalanced classes Liu et al. (2009). Eibe Frank and Remco R.
Bouckaert Frank and Bouckaert (2006) developed a method for introducing
normalization in each class by Equation (96) and then uses the centroid
classifier Han and Karypis (2000) in NBC for unbalanced classes. The centroid
$c_{c}$ for class $c$ is given in Equation (97).

$\alpha\times\frac{n_{wd}}{\sum_{w^{\prime}}\sum_{d\in D_{c}}n_{w^{\prime}d}}$
(96) $\begin{split}c_{c}=\bigg{\\{}&\frac{\sum_{d\in
D_{c}}n_{w_{1}d}}{\sqrt{\sum_{w}\big{(}\sum_{d\in
D_{c}}n_{wd}\big{)}^{2}}},\ldots,\\\ &\frac{\sum_{d\in
D_{c}}n_{w_{i}d}}{\sqrt{\sum_{w}\big{(}\sum_{d\in
D_{c}}n_{wd}\big{)}^{2}}},\ldots,\\\ &\frac{\sum_{d\in
D_{c}}n_{w_{k}d}}{\sqrt{\sum_{w}\big{(}\sum_{d\in
D_{c}}n_{wd}\big{)}^{2}}}\bigg{\\}}\end{split}$ (97)

The scoring function is defined as:

$x_{d}.c_{1}-x_{d}.c_{2}$ (98)

So log of multinomial Naïve Bayes classifier can be calculated as:

$\left[\log
P(c_{1})+\sum_{i=1}^{k}n_{w_{i}d}\log(P(w_{i}\>|\>c_{1}))\right]-\left[\log
P(c_{2})+\sum_{i=1}^{k}n_{w_{i}d}\log(P(w_{i}\>|\>c_{2}))\right]$ (99)

Using Equations (95) and (96), and if $\alpha=1$ we can rewrite:

$P(w\>|\>c)=\frac{1+\frac{n_{wd}}{\sum_{w^{\prime}}\sum_{d\in
D_{c}}n_{w^{\prime}d}}}{K+1}$ (100)

with respect to:

$\frac{\sum_{d\in D_{c}}n_{wd}}{\sum_{w^{\prime}}\sum_{d\in
D_{c}}n_{w^{\prime}d}}<<1$ (101)

For text data sets and $log(x+1)\approx x$ and $x<<1$ Frank and Bouckaert
(2006). In this technique of NBC, the experimental results is very similar to
the centroid classifier Han and Karypis (2000).

####  4.4.4 Limitation of Naïve Bayes Algorithm

Naïve Bayes algorithm also has several limitations. NBC makes a strong
assumption about the shape of the data distribution Soheily-Khah et al.
(2017); Wang et al. (2012). NBC is also limited by data scarcity for which any
possible value in feature space, a likelihood value must be estimated by a
frequentist Ranjan et al. (2017).

###  4.5 K-Nearest Neighbor

The k-nearest Neighbors algorithm (KNN) is a non-parametric technique used for
classification. This method is used for text classification applications in
many research domains Jiang et al. (2012) in past decades.

####  4.5.1 Basic Concept of KNN

Given a test document $x$, the KNN algorithm finds the $k$ nearest neighbors
of $x$ among all the documents in the training set, and scores the category
candidates based the class of $k$ neighbors. The similarity of $x$ and each
neighbor’s document could be the score of the category of the neighbor
documents. Multiple KNN documents may belong to the same category; in this
case, the summation of these scores would be the similarity score of class $k$
with respect to the test document $x$. After sorting the score values, the
algorithm assigns the candidate to the class with the highest score from the
test document $x$ Jiang et al. (2012). Figure 11 illustrates KNN architecture,
but for simplicity, this figure is designed by a 2D data set (similar and with
higher dimensional space like the text data set). The decision rule of KNN is:

$\begin{split}f(x)=&arg\max_{j}S(x,C_{j})\\\ =&\sum_{d_{i}\in
KNN}sim(x,d_{i})y(d_{i},C_{j})\end{split}$ (102)

where S refers to score value with respect to $S(x,C_{j})$, the score value of
candidate $i$ to class of $j$, and output of $f(x)$ is a label to the test set
document.

Figure 11: A architecture of k-nearest Neighbor (KNN) model for the 2D data
set and three classes.

####  4.5.2 Weight Adjusted K-Nearest Neighbor Classification

The weight adjusted k-nearest neighbor classification (WAKNN) is a version of
KNN which tries to learn the weight vectors for classification Han et al.
(2001). The weighted cosine measure Salton (1989) is calculated as follows:

$\begin{split}\cos(x,y,w)\dfrac{\sum\limits_{t\in T}(x_{t}\times
w_{t})\times(y_{t}\times w_{t})}{\sqrt{\sum\limits_{t\in T}(x_{t}\times
w_{t})^{2}}\times\sqrt{\sum\limits_{t\in T}(y_{t}\times
w_{t})^{2}}}\end{split}$ (103)

where $T$ refers to the set of words, and $x_{t}$ and $y_{t}$ are TF, as
discussed in Section 2. For the training model ($d\in D$), let
$N_{d}=\\{n_{1},n_{2},\ldots,n_{k}\\}$ be the set of k-nearest Neighbors of
$d$. Given $N_{d}$, the similarity sum of $d$ neighbors that belong to class
$c$ is defined as follows:

$S_{c}=\sum_{n_{i}\in N;C(n_{i})=c}\cos(d,n_{i},w)$ (104)

Total similarity is calculated as follows:

$T=\sum_{c\in C}S_{c}$ (105)

The contribution of $d$ is defined in terms of $S_{c}$ of classes $c$ and $T$
as follows:

$cont(d)=\begin{cases}1&\quad\stackunder{\text{if }$\forall c \in C, c \neq
class(d),$\quad\quad}{$S_{class(d)>S_s}$and$\frac{S_{class(d)}}{T}\leq p $}\\\
0&\quad\text{ otherwise}\end{cases}$ (106)

where $cont(d)$ stands for $contribution(d)$

####  4.5.3 Limitation of K-Nearest Neighbor

KNN is a classification method that is easy to implement and adapts to any
kind of feature space. This model also naturally handles multi-class cases
Sahgal and Ramesh (2015); Patel and Srivastava (2014). However, KNN is limited
by data storage constraints for large search problems to find nearest
neighbors. Additionally, the performance of KNN is dependent on finding a
meaningful distance function, thus making this technique a very data dependent
algorithm Sahgal and Parida (2014); Sanjay et al. .

###  4.6 Support Vector Machine (SVM)

The original version of SVM was developed by Vapnik and Chervonenkis Vapnik
and Chervonenkis (1964) in 1963. B.E. Boser et al. Boser et al. (1992) adapted
this version into a nonlinear formulation in the early 1990s. SVM was
originally designed for binary classification tasks. However, many researchers
work on multi-class problems using this dominate technique Bo and Xianwu
(2006). The Figure 12 indicates the linear and non-linear classifier which is
used for $2-dimension$ datasets.

Figure 12: This figure shows the linear and non-linear Support Vector Machine
(SVM) for a 2D data set (for text data we have thousands of dimensions). The
red is class $1$, the blue color is class $2$ and yellow color is miss-
classified data points.

####  4.6.1 Binary-Class SVM

In the context of text classification, let $x_{1},x_{2},...,x_{l}$ be training
examples belonging to one class $X$, where $X$ is a compact subset of $R^{N}$
Manevitz and Yousef (2001). Then we can formulate a binary classifier as
follows:

$\min\frac{1}{2}||w||^{2}+\frac{1}{vl}\sum_{i=1}^{l}\xi_{i}-p$ (107)

subject to:

$(w.\Phi(x_{i}))\geq p-\xi_{i}~{}~{}i=1,2,\ldots,l~{}~{}\xi\geq 0$ (108)

If $w$ and $p$ solve this problem, then the decision function is given by:

$f(x)=sign((w.\Phi(x))-p)$ (109)

####  4.6.2 Multi-Class SVM

Since SVMs are traditionally used for the binary classification, we need to
generate a Multiple-SVM (MSVM) Mohri et al. (2012) for multi-class problems.
One-vs-One is a technique for multi-class SVM that builds $N(N-1)$ classifiers
as follows:

$f(x)=arg\max_{i}\big{(}\sum_{j}f_{ij}(x)\big{)}$ (110)

The natural way to solve the k-class problem is to construct a decision
function of all $k$ classes at once Chen et al. (2016); Weston and Watkins
(1998). In general, multi-class SVM is an optimization problem of the
following form:

$\displaystyle\min_{w_{1},w_{2},..,w_{k},\zeta}~{}\frac{1}{2}\sum_{k}w_{k}^{T}w_{k}+C\sum_{(x_{i},y_{i})\in
D}\zeta_{i}$ (111)
$\displaystyle\begin{split}st.~{}~{}&w_{y_{i}}^{T}x-w_{k}^{T}x\leq
i-\zeta_{i},~{}~{}\\\ &\forall(x_{i},y_{i})\in D,k\in\\{1,2,...,K\\},k\neq
y_{i}\end{split}$ (112)

where $(x_{i},y_{i})$ represent the training data points such that
$(x_{i},y_{i})\in D$, $C$ is the penalty parameter, $\zeta$ is a slack
parameter, and $k$ stands for the class.

Another technique of multi-class classification using SVM is All-vs-One.
Feature extraction via SVM generally uses one of two methods: Word sequences
feature extracting Zhang et al. (2008) and TF-IDF. But for an unstructured
sequence such as RNA and DNA sequences, string kernel is used. However, string
kernel can be used for a document categorization Lodhi et al. (2002).

####  4.6.3 String Kernel

Text classification has also been studied using string kernel Lodhi et al.
(2002). The basic idea of string kernel (SK) is using $\Phi(.)$ to map the
string in the feature space.

Spectrum kernel as part of SK has been applied to many different applications,
including text, DNA, and protein classification Leslie et al. (2002); Eskin et
al. (2002). The basic idea of Spectrum kernel is counting the number of times
a word appears in string $x_{i}$ as a feature map where defining feature maps
from $x\rightarrow R^{l^{k}}$.

$\displaystyle\Phi_{k}(x)$ $\displaystyle=\Phi_{j}(x)_{j\in\Sigma^{k}}$ (113)
$\displaystyle where~{}~{}~{}~{}$ $\displaystyle\Phi_{j}(x)$
$\displaystyle=number~{}of~{}j~{}~{}feature~{}appears~{}in~{}x$ (114)

The feature map $\Phi_{i}(x)$ is generated by the sequence $x_{i}$ and kernel
defines as follows:

$\displaystyle F=$ $\displaystyle\Sigma^{k}$ (115) $\displaystyle
K_{i}(x,x^{\prime})=$ $\displaystyle<\Phi_{i}(x),\Phi_{i}(x^{\prime})>$ (116)

The main limitation of SVM when applied to string sequence classification is
time complexity Singh et al. (2017). The features are generated using
dictionary size $\Sigma$ and $F$ is the number of features and bounded by
Equation (115). The kernel calculation is similar with SP and uses Equation
(116), and finally normalizes the kernel using Equation (117).

$\displaystyle K^{Norm}(x,y)$
$\displaystyle\leftarrow~{}\frac{K(x,y)}{\sqrt{K(x,x)}~{}\sqrt{K(y,y)}}$ (117)
$\displaystyle<f^{x},f^{y}>$
$\displaystyle=\sum_{i=1}^{n_{1}}\sum_{j=1}^{n_{2}}h(u_{i}^{s_{1}},u_{j}^{s_{2}})$
(118)

where two sequences, $u_{i}^{s_{1}}$ and $u_{j}^{s_{2}}$, are lengths of
$s_{1}$ and $s_{2}$ respectively.

####  4.6.4 Stacking Support Vector Machine (SVM)

Stacking SVM is a hierarchical classification method used for category tree
structure based on a top-down level-based approach Sun and Lim (2001). This
technique provides a hierarchical model of individual SVM classifiers, and
thus generally produces more accurate results than single-SVM models
Sebastiani (2002). As shown in the Figure 13, the stacking model employs
hierarchical classifier which contains several layers (in this Figure we have
two level like mane domain, and sub-domains).

Figure 13: Hierarchical classification method.

####  4.6.5 Multiple Instance Learning (MIL)

Multiple instance learning (MIL) is a supervised learning method Maron and
Lozano-Pérez (1998) and is typically formulated as one of two SVM-based
methods (mi-SVM and MI-SVM) Andrews et al. (2003). MIL takes in a set of
labeled bags as input instead of instances. A bag is labeled positive if there
is at least one instance in it with a positive label, and labeled negative if
all instances of it are negative. Then, the learner tries to infer a concept
that label individual instances correctly Maron and Lozano-Pérez (1998). In
statistical pattern recognition, it is assumed that a training set of labeled
patterns is available where each pair $(x_{i},y_{i})\in R^{d}\times Y$ has
been generated from an unknown distribution independently. The goal is to find
a classifier from patterns to labels i.e., $f:R^{d}\rightarrow Y$. In MIL, the
algorithm assumes the input is available as a set of input patterns
$x_{1},...,x_{n}$ grouped into bags $B_{1},...,B_{m}$ where
$B_{I}=\\{x_{i}:i\in I\\}$ for the given index sets $I\subseteq\\{1,...,n\\}$.
Each bag $B_{I}$ is associated with label $Y_{I}$ where $Y_{I}=-1$ if
$y_{i}=-1$ for all $i\in I$ and $Y_{I}=1$ if there is at least one instance
$x_{i}\in B_{I}$ with positive label Andrews et al. (2003). The relationship
between instance labels $y_{i}$ and bag labels $Y_{I}$ can be expressed as
$Y_{I}=\max_{i\in I}y_{i}$ or a set of linear constraints:

$\begin{split}\sum_{i\in I}&\frac{y_{i}+1}{2}\geq 1,\\\ &\forall I\ s.t.\
Y_{I}=1,\quad\\\ &y_{i}=-1,\forall I\ s.t.\ Y_{I}=-1.\end{split}$ (119)

The discriminant function $f:X\rightarrow R$ is called MI-separating with
respect to a multiple-instance data set if $sgn\max_{i\in I}\ f(x_{i})=Y_{I}$
for all bags $B_{I}$ holds.

####  4.6.6 Limitation of Support Vector Machine (SVM)

SVM has been one of the most efficient machine learning algorithms since its
introduction in the 1990s Karamizadeh et al. (2014). However, the SVM
algorithms for text classification are limited by the lack of transparency in
results caused by a high number of dimensions. Due to this, it cannot show the
company score as a parametric function based on financial ratios nor any other
functional form Karamizadeh et al. (2014). A further limitation is a variable
financial ratios rate Guo (2014).

###  4.7 Decision Tree

One earlier classification algorithm for text and data mining is decision tree
Morgan and Sonquist (1963). Decision tree classifiers (DTCs) are used
successfully in many diverse areas for classification Safavian and Landgrebe
(1991). The structure of this technique is a hierarchical decomposition of the
data space Morgan and Sonquist (1963); Aggarwal and Zhai (2012a). Decision
tree as classification task was introduced by D. Morgan Magerman (1995) and
developed by J.R. Quinlan Quinlan (1986). The main idea is creating a tree
based on the attribute for categorized data points, but the main challenge of
a decision tree is which attribute or feature could be in parents’ level and
which one should be in child level. To solve this problem, De Mántaras De
Mántaras (1991) introduced statistical modeling for feature selection in tree.
For a training set containing $p$ positive and $n$ negative:

$\begin{split}H\bigg{(}\frac{p}{n+p},\frac{n}{n+p}\bigg{)}=&-\frac{p}{n+p}\log_{2}\frac{p}{n+p}\\\
&-\frac{n}{n+p}\log_{2}\frac{n}{n+p}\end{split}$ (120)

Choose attribute _A_ with _k_ distinct value, divides the training set _E_
into subsets of $\\{E_{1},E_{2},\ldots,E_{k}\\}$. The expect entropy (EH)
remain after trying attribute _A_ (with branches $i=1,2,\ldots,k$):

$\begin{split}EH(A)=\sum_{i=1}^{K}\frac{p_{i}+n_{i}}{p+n}H\bigg{(}\frac{p_{i}}{n_{i}+p_{i}},\frac{n_{i}}{n_{i}+p_{i}}\bigg{)}\end{split}$
(121)

Information gain (_I_) or reduction in entropy for this attribute is :

$\begin{split}A(I)=H\bigg{(}\frac{p}{n+p},\frac{n}{n+p}\bigg{)}-EH(A)\end{split}$
(122)

Choose the attribute with largest information gain as parent’s node.

#### Limitation of Decision Tree Algorithm

The decision tree is a very fast algorithm for both learning and prediction;
but it is also extremely sensitive to small perturbations in the data
Giovanelli et al. (2017), and can be easily overfit Quinlan (1987). These
effects can be negated by validation methods and pruning, but this is a grey
area Giovanelli et al. (2017). This model also has problems with out-of-sample
prediction Jasim (2016).

###  4.8 Random Forest

Random forests or random decision forests technique is an ensemble learning
method for text classification. This method, which used $t$ tree as parallel,
was introduced by T. Kam Ho Ho (1995) in 1995. As shown in Figure 14, the main
idea of RF is generating random decision trees. This technique was further
developed in 1999 by L. Breiman Breiman (1999), who found convergence for RF
as margin measures ($mg(X,Y)$) as follows:

$\begin{split}mg(X,Y)=&av_{k}I(h_{k}(X)=Y)-\\\ &\max_{j\neq
Y}av_{k}I(h_{k}(X)=j)\end{split}$ (123)

where $I(.)$ refers to indicator function.

Figure 14: Random forest.

####  4.8.1 Voting

After training all trees as forest, predictions are assigned based on voting
Wu et al. (2004) as follows:

$\delta_{V}=arg\max_{i}\sum_{j:j\neq j}I_{\\{r_{ij}>r_{ji}\\}}$ (124)

such that

$r_{ij}+r_{ji}=1$ (125)

####  4.8.2 Limitation of Random Forests

Random forests (i.e., ensembles of decision trees) are very fast to train for
text data sets in comparison to other techniques such as deep learning, but
quite slow to create predictions once trained Bansal et al. (2018). Thus, in
order to achieve a faster structure, the number of trees in forest must be
reduced, as more trees in forest increases time complexity in the prediction
step.

###  4.9 Conditional Random Field (CRF)

CRF is an undirected graphical model, as shown in Figure 15. CRFs are
essentially a way of combining the advantages of classification and graphical
modeling that combine the ability to compactly model multivariate data, and
the ability to leverage a high dimensional features space for prediction
Sutton et al. (2012) (this model is very powerful for text data due to high
feature space). CRFs state the conditional probability of a label sequence $Y$
given a sequence of observation $X$ i.e., $P(Y|X)$. CRFs can incorporate
complex features into an observation sequence without violating the
independence assumption by modeling the conditional probability of the label
sequence rather than the joint probability $P(X,Y)$ Vail et al. (2007); Chen
et al. (2017). Clique (i.e., fully connected subgraph) potential is used for
computing $P(X|Y)$. With respect to the potential function for each clique in
the graph, the probability of a variable configuration corresponds to the
product of a series of a non-negative potential functions. The value computed
by each potential function is equivalent to the probability of the variables
in the corresponding clique for a particular configuration Vail et al. (2007).
That is:

$P(V)=\frac{1}{Z}\prod_{c\in cliques(V)}\psi(c)$ (126)

where $Z$ is the normalization term. The conditional probability $P(X|Y)$ can
be formulated as:

$P(Y|X)=\frac{1}{Z}\prod_{t=1}^{T}\psi(t,y_{t-1},y_{t},X)$ (127)

Given the potential function
($\psi(t,y_{t-1},y_{t},X)=\exp(w.f(t,y_{t-1},y_{t},X))$), the conditional
probability can be rewritten as:

$P(Y|X)=\prod_{t=1}^{T}\exp(w.f(t,y_{t-1},y_{t},X))$ (128)

where $w$ is the weight vector associated with a feature vector computed by
$f$.

Figure 15: Linear-chain conditional random field (CRF). The black boxes are
transition clique

#### Limitation of Conditional Random Field (CRF)

With regards to CRF, the most evident disadvantage of CRF is the high
computational complexity of the training step Sutton and McCallum (2006),
especially for text data sets due to high feature space. Furthermore, this
algorithm does not perform with unseen words (i.e., with words that were not
present in the training data sample) Tseng et al. (2005).

###  4.10 Deep Learning

Deep learning models have achieved state-of-the-art results across many
domains, including a wide variety of NLP applications. Deep learning for text
and document classification includes three basic architectures of deep
learning in parallel. We describe each individual model in detail below.

####  4.10.1 Deep Neural Networks

Deep neural networks (DNN) are designed to learn by multi-connection of layers
that every single layer only receives the connection from previous and
provides connections only to the next layer in a hidden part Kowsari et al.
(2017). Figure 16 depicts the structure of a standard DNN. The input consists
of the connection of the input feature space (as discussed in Section 2) with
the first hidden layer of the DNN. The input layer may be constructed via TF-
IDF, word embedding, or some other feature extraction method. The output layer
is equal to the number of classes for multi-class classification or only one
for binary classification. In multi-class DNNs, each learning model is
generated (number of nodes in each layer and the number of layers are
completely randomly assigned). The implementation of DNN is a discriminative
trained model that uses a standard back-propagation algorithm using sigmoid
(Equation (129)), ReLU Nair and Hinton (2010) (Equation (130)) as an
activation function. The output layer for multi-class classification should be
a $Softmax$ function (as shown in Equation (131)).

$\displaystyle f(x)$ $\displaystyle=\frac{1}{1+e^{-x}}\in(0,1)$ (129)
$\displaystyle f(x)$ $\displaystyle=\max(0,x)$ (130)
$\displaystyle\sigma(z)_{j}$
$\displaystyle=\frac{e^{z_{j}}}{\sum_{k=1}^{K}e^{z_{k}}}$ (131)
$\displaystyle\forall~{}j\in\\{1,\ldots,K\\}$

Given a set of example pairs $(x,y)$,$x\in X,y\in Y$, the goal is to learn the
relationship between these input and target spaces using hidden layers. In
text classification applications, the input is a string which is generated via
vectorization of the raw text data.

Figure 16: Standard, fully connected deep neural network (DNN).

####  4.10.2 Recurrent Neural Network (RNN)

Another neural network architecture that researchers have used for text mining
and classification is recurrent neural network (RNN) Sutskever et al. (2011);
Mandic et al. (2001). RNN assigns more weights to the previous data points of
a sequence. Therefore, this technique is a powerful method for text, string,
and sequential data classification. A RNN considers the information of
previous nodes in a very sophisticated method which allows for better semantic
analysis of a data set’s structure. RNN mostly works by using LSTM or GRU for
text classification, as shown in Figure 17 which contains input layer (word
embedding), hidden layers, and finally output layer. This method can be
formulated as:

$x_{t}=F(x_{t-1},\boldsymbol{u_{t}},\theta)$ (132)

where $x_{t}$ is the state at time $t$ and $\boldsymbol{u_{t}}$ refers to the
input at step $t$. More specifically, we can use weights to formulate Equation
(132), parameterized by:

$x_{t}=\mathbf{W_{rec}}\sigma(x_{t-1})+\mathbf{W_{in}}\mathbf{u_{t}}+\mathbf{b}$
(133)

where $\mathbf{W_{rec}}$ refers to recurrent matrix weight, $\mathbf{W_{in}}$
refers to input weights, $\mathbf{b}$ is the bias, and $\sigma$ denotes an
element-wise function.

Figure 17 illustrates an extended RNN architecture. Despite the benefits
described above, RNN is vulnerable to the problems of vanishing gradient and
exploding gradient when the error of the gradient descent algorithm is back
propagated through the network Bengio et al. (1994).

Figure 17: Standard long short-term memory (LSTM)/GRU recurrent neural
networks.

#### Long Short-Term Memory (LSTM)

LSTM was introduced by S. Hochreiter and J. Schmidhuber Hochreiter and
Schmidhuber (1997), and has since been augmented by many research scientists
Graves and Schmidhuber (2005).

LSTM is a special type of RNN that addresses these problems by preserving long
term dependency in a more effective way in comparison to the basic RNN. LSTM
is particularly useful with respect to overcoming the vanishing gradient
problem Pascanu et al. (2013). Although LSTM has a chain-like structure
similar to RNN, LSTM uses multiple gates to carefully regulate the amount of
information that is allowed into each node state. Figure 18 shows the basic
cell of an LSTM model. A step-by-step explanation of a LSTM cell is as
follows:

$\displaystyle i_{t}=$ $\displaystyle\sigma(W_{i}[x_{t},h_{t-1}]+b_{i}),$
(134) $\displaystyle\tilde{C_{t}}=$
$\displaystyle\tanh(W_{c}[x_{t},h_{t-1}]+b_{c}),$ (135) $\displaystyle f_{t}=$
$\displaystyle\sigma(W_{f}[x_{t},h_{t-1}]+b_{f}),$ (136) $\displaystyle
C_{t}=$ $\displaystyle i_{t}*\tilde{C_{t}}+f_{t}C_{t-1},$ (137) $\displaystyle
o_{t}=$ $\displaystyle\sigma(W_{o}[x_{t},h_{t-1}]+b_{o}),$ (138)
$\displaystyle h_{t}=$ $\displaystyle o_{t}\tanh(C_{t}),$ (139)

where Equation (134) represents the input gate, Equation (135) represents the
candid memory cell value, Equation (136) defines forget-gate activation,
Equation (137) calculates the new memory cell value, and Equations (138) and
(139) define the final output gate value. In the above description, each $b$
represents a bias vector, each $W$ represent a weight matrix, and $x_{t}$
represents input to the memory cell at time $t$. Furthermore, $i$,$c$,$f$,$o$
indices refer to input, cell memory, forget and output gates respectively.
Figure 18 shows a graphical representation of the structure of these gates.

A RNN can be biased when later words are more influential than earlier ones.
Convolutional neural network (CNN) models (discussed in Section 4.10.3) were
introduced to overcome this bias by deploying a max-pooling layer to determine
discriminative phrases in text data Lai et al. (2015).

#### Gated Recurrent Unit (GRU)

GRUs are a gating mechanism for RNN formulated by J. Chung et al. Chung et al.
(2014) and K. Cho et al. Cho et al. (2014). GRUs are a simplified variant of
the LSTM architecture. However, a GRU differs from LSTM because it contains
two gates and a GRU does not possess internal memory (i.e., the $C_{t-1}$ in
Figure 18). Furthermore, a second non-linearity is not applied (i.e., tanh in
Figure 18). A step-by-step explanation of a GRU cell is as follows:

$z_{t}=\sigma_{g}(W_{z}x_{t}+U_{z}h_{t-1}+b_{z}),$ (140)

where $z_{t}$ refers to the update gate vector of $t$, $x_{t}$ stands for
input vector, $W$, $U$, and $b$ represent parameter matrices/vectors. The
activation function ($\sigma_{g}$) is either a sigmoid or ReLU and can be
formulated as follow:

$\tilde{r_{t}}=\sigma_{g}(W_{r}x_{t}+U_{r}h_{t-1}+b_{r}),$ (141)

where $r_{t}$ stands for reset gate vector of $t$, $z_{t}$ is update gate
vector of $t$.

$\begin{split}h_{t}=&z_{t}\circ h_{t-1}+(1-z_{t})\circ\\\
&\sigma_{h}(W_{h}x_{t}+U_{h}(r_{t}\circ h_{t-1})+b_{h})\end{split}$ (142)

where $h_{t}$ is output vector of $t$, and $\sigma_{h}$ indicates the
hyperbolic tangent function.

Figure 18: The left figure is a GRU cell while the right figure is a LSTM
cell.

####  4.10.3 Convolutional Neural Networks (CNN)

A convolutional neural network (CNN) is a deep learning architecture that is
commonly used for hierarchical document classification Jaderberg et al.
(2016); Lai et al. (2015). Although originally built for image processing,
CNNs have also been effectively used for text classification LeCun et al.
(1998, 2015). In a basic CNN for image processing, an image tensor is
convolved with a set of kernels of size $d\times d$. These convolution layers
are called feature maps and can be stacked to provide multiple filters on the
input. To reduce the computational complexity, CNNs use pooling to reduce the
size of the output from one layer to the next in the network. Different
pooling techniques are used to reduce outputs while preserving important
features Scherer et al. (2010).

The most common pooling method is max pooling where the maximum element in the
pooling window is selected. In order to feed the pooled output from stacked
featured maps to the next layer, the maps are flattened into one column. The
final layers in a CNN are typically fully connected. In general, during the
back-propagation step of a convolutional neural network, both the weights and
the feature detector filters are adjusted. A potential problem that arises
when using CNN for text classification is the number of ’channels’, $\Sigma$
(size of the feature space). While image classification application generally
have few channels (e.g., only 3 channels of RGB), $\Sigma$ may be very large
(e.g., 50 K) for text classification applications Johnson and Zhang (2014),
thus resulting in very high dimensionality. Figure 19 illustrate the CNN
architecture for text classification which contains word embedding as input
layer 1D convolutional layers, 1D pooling layer, fully connected layers, and
finally output layer.

Figure 19: Convolutional neural network (CNN) architecture for text
classification.

####  4.10.4 Deep Belief Network (DBN)

A deep belief network (DBN) is a deep learning structure that is superposed by
restricted Boltzmann machines (RBMs) Jiang et al. (2018). A RBM is a
generative artificial neural network which could learn probability
distribution over samples. Contrastive divergence (CD) Hinton (2002) is a
training technique used for RBMs Hinton et al. (2006); Mohamed et al. (2012).

The energy function is as follows:

$E(v,h)=-\sum_{i}a_{i}v_{i}-\sum_{j}b_{j}h_{j}-\sum_{i}\sum_{j}v_{i}w_{i,j}h_{j}$
(143)

where $a_{i}$ is visible units and $b_{i}$ refers to hidden units in matrix
notation. This expression can be simplified as:

$E(v,h)=-a^{\mathrm{T}}v-b^{\mathrm{T}}h-v^{\mathrm{T}}Wh$ (144)

Given a configuration of the hidden units $h$ is defined as follows:

$P(v|h)=\prod_{i=1}^{m}P(v_{i}|h)$ (145)

For Bernoulli, the logistic function for visible units is replaced as follows:

$P(v_{i}^{k}=1|h)=\frac{\exp(a_{i}^{k}+\Sigma_{j}W_{ij}^{k}h_{j})}{\Sigma_{k^{\prime}=1}^{K}\exp(a_{i}^{k^{\prime}}+\Sigma_{j}W_{ij}^{k^{\prime}}h_{j})}$
(146)

The update function with gradient descent is as follows:

$w_{ij}(t+1)=w_{ij}(t)+\eta\frac{\partial\log(p(v))}{\partial w_{ij}}$ (147)

####  4.10.5 Hierarchical Attention Networks (HAN)

One of the successful deep architecture for text and document classification
is hierarchical attention networks (HAN). This technique was introduced by Z.
Yang et al. Yang et al. (2016) and S.P. Hongsuck et al. Seo et al. (2016). The
structure of a HAN focuses on the document-level classification which a
document has $L$ sentences and each sentence contains $T_{i}$ words, where
$w_{it}$ with $t\int[1,T]$ represents the words in the _i_ th sentence. HAN
architecture is illustrated in Figure 20, where the lower level contains word
encoding and word attention and the upper level contains sentence encoding and
sentence attention.

Figure 20: Hierarchical attention networks for document classification.

####  4.10.6 Combination Techniques

Many researchers combine or concatenate standard deep learning architectures
in order to develop novel techniques with more robust and accurate
architectures for classification tasks. In this sub-section, we describe
recent and popular deep learning architectures and structure.

#### Random Multimodel Deep Learning (RMDL)

Random multimodel deep learning (RMDL) was introduced by K. Kowsari et al.
Kowsari et al. (2018); Heidarysafa et al. (2018) as a novel deep learning
technique for classification. RMDL can be used in any kind of data set for
classification. An overview of this technique is shown in Figure 21 which
illustrates the architecture using multi-DNN, deep CNN, and deep RNN. The
number of layers and nodes for all of these deep learning multi-models are
generated randomly (e.g., 9 random models in RMDL constructed from $3$ CNNs,
$3$ RNNs, and $3$ DNNs, all of which are unique due to random creation).

$\displaystyle M(y_{i1},y_{i2},...,y_{in})=$
$\displaystyle\bigg{\lfloor}\frac{1}{2}+\frac{(\sum_{j=1}^{n}y_{ij})-\frac{1}{2}}{n}\bigg{\rfloor}$
(148)

where $n$ is the number of random models, and $y_{ij}$ is the output
prediction of model for data point $i$ in model $j$ (Equation (148) is used
for binary classification, $k\in\\{0~{}\text{or}~{}1\\}$). The output space
uses majority vote to calculate the final value of $\hat{y_{i}}$. Therefore,
$\hat{y_{i}}$ is given as follows:

$\hat{y_{i}}=\begin{bmatrix}\hat{y}_{i1}~{}\ldots~{}\hat{y}_{ij}~{}\ldots~{}\hat{y}_{in}~{}\end{bmatrix}^{T}$
(149)

where $n$ is the number of the random model, and $\hat{y}_{ij}$ shows the
prediction of the label of data point (e.g., document) of
$D_{i}\in\\{x_{i},y_{i}\\}$ for model $j$ and $\hat{y}_{i,j}$ is defined as
follows:

$\hat{y}_{i,j}=arg\max_{k}[softmax(y_{i,j}^{*})]$ (150)

Figure 21: Random multimodel eeep learning (RDML) architecture for
classification. RMDL includes 3 random models: A deep neural network (DNN)
classifier (left), a deep CNN classifier (middle), and a deep recurrent neural
network (RNN) classifier (right). Each unit could be a LSTM or GRU).

After all the RDL models (RMDL) are trained, the final prediction is
calculated using majority vote on the output of these models. The main idea of
using multi-model with different optimizers is that if one optimizer does not
provide a good fit for a specific data set, the RMDL model with $n$ random
models (where some of them might use different optimizers) could ignore $k$
models which are not efficient if and only if $n>k$. Using multi-techniques of
optimizers (e.g., SGD, Adam, RMSProp, Adagrad, Adamax) helps the RMDL model be
more suitable for any type of data sets. While we only used $2$ optimizers
(Adam and RMSProp) for evaluating the model in this research, the RMDL model
can use any kind of optimizer. In this part, we describe common optimization
techniques used in deep learning architectures.

Stochastic Gradient Descent (SGD) Optimizer:

The basic equation for stochastic gradient descent (SGD) Bottou (2010) is
shown in Equation (151). SGD uses a momentum on re-scaled gradient which is
shown in Equation (152) for updating parameters.

$\displaystyle\theta$
$\displaystyle\leftarrow\theta-\alpha\nabla_{\theta}J(\theta,x_{i},y_{i})$
(151) $\displaystyle\theta$
$\displaystyle\leftarrow\theta-\big{(}\gamma\theta+\alpha\nabla_{\theta}J(\theta,x_{i},y_{i})\big{)}$
(152)

RMSprop:

T. Tieleman and G. Hinton Tieleman and Hinton (2012) introduced RMSprop as a
novel optimizer which divides the learning rate for a weight by a running
average of the magnitudes of recent gradients for that weight. The equation of
the momentum method for RMSprop is as follows:

$v(t)=\alpha~{}v(t-1)-\epsilon\frac{\partial E}{\partial w}(t)$ (153)
$\displaystyle\Delta w(t)$ $\displaystyle=v(t)$
$\displaystyle=\alpha~{}v(t-1)-\epsilon\frac{\partial E}{\partial w}(t)$ (154)
$\displaystyle=\alpha~{}\Delta v(t-1)-\epsilon\frac{\partial E}{\partial
w}(t)$

RMSProp does not do bias correction, which causes significant problems when
dealing with a sparse gradient.

Adam Optimizer

Adam is another stochastic gradient optimizer which uses only the first two
moments of gradient ($v$ and $m$, shown in Equations (155)–(158)) and
calculate the average over them. It can handle non-stationary of the objective
function as in RMSProp while overcoming the sparse gradient issue limitation
of RMSProp Kingma and Ba (2014).

$\displaystyle\theta$
$\displaystyle\leftarrow\theta-\frac{\alpha}{\sqrt{\hat{v}}+\epsilon}\hat{m}$
(155) $\displaystyle g_{i,t}$
$\displaystyle=\nabla_{\theta}J(\theta_{i},x_{i},y_{i})$ (156) $\displaystyle
m_{t}$ $\displaystyle=\beta_{1}m_{t-1}+(1-\beta_{1})g_{i,t}$ (157)
$\displaystyle m_{t}$
$\displaystyle=\beta_{2}v_{t-1}+(1-\beta_{2})g_{i,t}^{2}$ (158)

where $m_{t}$ is the first moment and $v_{t}$ indicates second moment that
both are estimated. $\hat{m_{t}}=\frac{m_{t}}{1-\beta_{1}^{t}}$ and
$\hat{v_{t}}=\frac{v_{t}}{1-\beta_{2}^{t}}$.

Adagrad:

Adagrad is addressed in Duchi et al. (2011) as a novel family of sub-gradient
methods which dynamically absorb knowledge of the geometry of the data to
perform more informative gradient-based learning.

AdaGrad is an extension of SGD. In iteration $k$, the gradient is defined as:

$G^{(k)}=diag\bigg{[}\sum_{i=1}^{k}g^{(i)}(g^{(i)})^{T}\bigg{]}^{1/2}$ (159)

diagonal matrix:

$G^{(k)}_{jj}=\sqrt{\sum_{i=1}^{k}(g_{i}^{(i)})^{2}}$ (160)

update rule:

$\displaystyle x^{(k+1)}$ $\displaystyle=arg\min_{x\in X}\\{\langle{\nabla
f(x^{(k)}),x}\rangle+$ (161)
$\displaystyle~{}\qquad~{}\qquad~{}\quad\frac{1}{2\alpha_{k}}||{x-x^{(k)}}||^{2}_{G^{(k)}}\\}$
$\displaystyle=x^{(k)}-\alpha B^{-1}\nabla f(x^{(k)})\qquad(\text{if
}{X}=\\!R^{n})$

Adadelta:

AdaDelta, introduced by M.D. Zeiler Zeiler (2012), uses the exponentially
decaying average of $g_{t}$ as $2_{nd}$ moment of gradient. This method is an
updated version of Adagrad which relies on only first order information. The
update rule for Adadelta is:

$g_{t+1}=\gamma g_{t}+(1-\gamma)\nabla\mathcal{L}(\theta)^{2}$ (162)
$x_{t+1}=\gamma x_{t}+(1-\gamma)v_{t+1}^{2}$ (163)
$v_{t+1}=-\frac{\sqrt{x_{t}+\epsilon}\delta
L(\theta_{t})}{\sqrt{g_{t+1}+\epsilon}}$ (164)

#### Hierarchical Deep Learning for Text (HDLTex)

The primary contribution of the hierarchical deep learning for text (HDLTex)
architecture is hierarchical classification of documents Kowsari et al.
(2017). A traditional multi-class classification technique can work well for a
limited number of classes, but performance drops with an increasing number of
classes, as is present in hierarchically organized documents. In this
hierarchical deep learning model, this problem was solved by creating
architectures that specialize deep learning approaches for their level of the
document hierarchy (e.g., see Figure 22). The structure of the HDLTex
architecture for each deep learning model is as follows:

DNN:

$8$ hidden layers with $1024$ cells in each hidden layer.

RNN:

GRU and LSTM are used in this implementation, $100$ cells with GRU with two
hidden layers.

CNN:

Filter sizes of $\\{3,4,5,6,7\\}$ and max-pool of $5$, layer sizes of
$\\{128,128,128\\}$ with max pooling of $\\{5,5,35\\}$, the CNN contains $8$
hidden layers.

All models were constructed using the following parameters: Batch Size = 128,
learning parameters = $0.001$, $\beta_{1}$ = 0.9, $\beta_{2}$ = 0.999,
$\epsilon=1e^{08}$, $decay=0.0$, Dropout = 0.5 (DNN), and Dropout = 0.25 (CNN
and RNN).

HDLTex uses the following cost function for the deep learning models
evaluation:

$\begin{split}Acc(X)=&\sum_{\varrho}\bigg{[}\frac{Acc(X_{\Psi_{\varrho}})}{k_{\varrho}-1}\\\
&\sum_{\Psi\in\\{\Psi_{1},..\Psi_{k}\\}}Acc(X_{\Psi_{i}}).n_{\Psi_{k}}\bigg{]}\end{split}$
(165)

where $\varrho$ is the number of levels, $k$ indicates number of classes for
each level, and $\Psi$ refers to the number of classes in the child’s level of
the hierarchical model.

Figure 22: HDLTex: Hierarchical deep learning for text classification. DNN
approach for the text classification. The top figure depicts the parent-level
of our model, and the bottom figure depicts child-level models ($\Psi_{i}$) as
input documents in the parent level.

#### Other Techniques

In this section, we discuss other techniques of text classification that come
from combining deep learning architectures. Recurrent convolutional neural
networks (RCNN) is used for text classification Lai et al. (2015); Wang et al.
(2017). RCNNs can capture contextual information with the recurrent structure
and construct the representation of text using a CNN Lai et al. (2015). This
architecture is a combination of RNN and CNN that leverages the advantages of
both techniques in a model.

C-LSTM is another technique of text and document classification that was
introduced by C. Zhou et al. Zhou et al. (2015). C-LSTM combines CNN with LSTM
in order to learn phrase-level features using convolutional layers. This
architecture feeds sequences of higher level representations into the LSTM to
learn long-term dependent.

####  4.10.7 Limitation of Deep Learning

Model interpretability of deep learning (DL), especially DNN, has always been
a limiting factor for use cases requiring explanations of the features
involved in modelling and such is the case for many healthcare problems. This
problem is due to scientists preferring to use traditional techniques such as
linear models, Bayesian Models, SVM, decision trees, etc. for their works. The
weights in a neural network are a measure of how strong each connection is
between each neuron to find the important feature space. As shown in Figure
23, the more accurate model, the interpretability is lower which means the
complex algorithms such as deep learning is hard to understand.

Deep learning (DL) is one of the most powerful techniques in artificial
intelligence (AI), and many researchers and scientists focus on deep learning
architectures to improve the robustness and computational power of this tool.
However, deep learning architectures also have some disadvantages and
limitations when applied to classification tasks. One of the main problems of
this model is that DL does not facilitate a comprehensive theoretical
understanding of learning Shwartz-Ziv and Tishby (2017). A well-known
disadvantage of DL methods is their “black box” nature Gray and MacDonell
(1996); Shrikumar et al. (2017). That is, the method by which DL methods come
up with the convolved output is not readily understandable. Another limitation
of DL is that it usually requires much more data than traditional machine
learning algorithms, which means that this technique cannot be applied to
classification tasks over small data sets Anthes (2013); Lampinen and
McClelland (2017). Additionally, the massive amount of data needed for DL
classification algorithms further exacerbates the computational complexity
during the training step Severyn and Moschitti (2015).

Figure 23: The model interpretability comparison between traditional and deep
learning techniques.

###  4.11 Semi-Supervised Learning for Text Classification

Many researchers have developed many efficient classifiers for both labeled
and unlabeled documents. Semi-supervised learning is a type of supervised
learning problem that uses unlabeled data to train a model. Usually,
researchers and scientists prefer to use semi-supervised techniques when a
small part of the data set contains labeled data points and a large amount of
data set does not include labels Gowda et al. (2016). Most of the semi-
supervised learning algorithms for classification tasks use a clustering
technique (generally used for unsupervised learning Kowsari (2014)) as
follows: Initially a clustering technique is applied on $D^{T}$ with $K=K$
(the number of classes), since $D^{T}$ has labeled samples of all $K$ classes
Gowda et al. (2016). If a partition $P_{i}$ has labeled samples, then, all
data points on that cluster belongs to that label.

The research goal for clustering techniques is to determine if we have more
than one class labeled on one cluster, and what happens if we have no labeled
data point in one cluster Kowsari et al. (2015). In this part, we briefly
describe the most popular technique of semi-supervised text and document
classification. O. Chapelle and A. Zien Chapelle and Zien (2005) worked on
semi-supervised classification via low density separation, which combines
graph distance computation with transductive support vector machine (TSVM)
training. K. Nigam et al. Nigam et al. (2006) developed a technique for text
classification using expectation maximization (EM) and generative models for
semi-supervised learning with labeled and unlabeled data in the field of text
classifications. L. Shi et al. Shi et al. (2010) introduced a method for
transferring classification knowledge across languages via translated
features. This technique uses an EM algorithm that naturally takes into
account the ambiguity associated with the translation of a word. J. Su et al.
Shi et al. (2010) introduced “Semi-supervised Frequency Estimate (SFE)”, a
MNBC method for large scale text classification. S. Zhou et al. Zhou et al.
(2014) invented a novel deep learning method that uses fuzzy DBN for semi-
supervised sentiment classification. This method employs a fuzzy membership
function for each category of reviews based on the learned architecture.

##  5 Evaluation

In the research community, having shared and comparable performance measures
to evaluate algorithms is preferable. However, in reality such measures may
only exist for a handful of methods. The major problem when evaluating text
classification methods is the absence of standard data collection protocols.
Even if a common collection method existed (e.g., Reuters news corpus), simply
choosing different training and test sets can introduce inconsistencies in
model performance Yang (1999). Another challenge with respect to method
evaluation is being able to compare different performance measures used in
separate experiments. Performance measures generally evaluate specific aspects
of classification task performance, and thus do not always present identical
information. In this section, we discuss evaluation metrics and performance
measures and highlight ways in which the performance of classifiers can be
compared. Since the underlying mechanics of different evaluation metrics may
vary, understanding what exactly each of these metrics represents and what
kind of information they are trying to convey is crucial for comparability.
Some examples of these metrics include recall, precision, accuracy, F-measure,
micro-average, and macro average. These metrics are based on a “confusion
matrix” (shown in Figure 24) that comprises true positives (TP), false
positives (FP), false negatives (FN), and true negatives (TN) Lever et al.
(2016). The significance of these four elements may vary based on the
classification application. The fraction of correct predictions over all
predictions is called accuracy (Equation (166)). The fraction of known
positives that are correctly predicted is called sensitivity i.e., true
positive rate or recall (Equation (167)). The ratio of correctly predicted
negatives is called specificity (Equation (168)). The proportion of correctly
predicted positives to all positives is called precision, i.e., positive
predictive value (Equation (169)).

$\displaystyle accuracy$ $\displaystyle=\frac{(TP+TN)}{(TP+FP+FN+TN)}$ (166)
$\displaystyle sensitivity$ $\displaystyle=\frac{TP}{(TP+FN)}$ (167)
$\displaystyle specificity$ $\displaystyle=\frac{TN}{(TN+FP)}$ (168)
$\displaystyle precision$
$\displaystyle=\frac{\sum_{l=1}^{L}TP_{l}}{\sum_{l=1}^{L}TP_{l}+FP_{l}}$ (169)
$\displaystyle recall$
$\displaystyle=\frac{\sum_{l=1}^{L}TP_{l}}{\sum_{l=1}^{L}TP_{l}+FN_{l}}$ (170)
$\displaystyle F1-Score$
$\displaystyle=\frac{\sum_{l=1}^{L}2TP_{l}}{\sum_{l=1}^{L}2TP_{l}+FP_{l}+FN_{l}}$
(171)

Figure 24: Confusion matrix.

###  5.1 Macro-Averaging and Micro-Averaging

A single aggregate measure is required when several two-class classifiers are
being used to process a collection. Macro-averaging gives a simple average
over classes while micro-averaging combines per-document decisions across
classes and then outputs an effective measure on the pooled contingency table
Manning et al. (2008). Macro-averaged results can be computed as follows:

$B_{macro}=\frac{1}{q}\sum_{\lambda=1}^{q}B(TP_{\lambda}+FP_{\lambda}+TN_{\lambda}+FN_{\lambda})$
(172)

where $B$ is a binary evaluation measure calculated based on true positives
(TP), false positives (FP), false negatives (FN), and true negatives (TN), and
$L=\\{\lambda_{j}:j=1...q\\}$ is the set of all labels.

Micro-averaged results Sebastiani (2002); Tsoumakas et al. (2009) can be
computed as follows:

$\begin{split}B_{macro}=B\bigg{(}&\sum_{\lambda=1}^{q}TP_{\lambda},\sum_{\lambda=1}^{q}FP_{\lambda},\sum_{\lambda=1}^{q}TN_{\lambda},\sum_{\lambda=1}^{q}FN_{\lambda}\bigg{)}\end{split}$
(173)

Micro-average score assigns equal weights to every document as a consequence,
and it is considered to be a per-document average. On the other hand, macro-
average score assigns equal weights to each category without accounting for
frequency and therefore, it is a per-category average.

###  5.2 Fβ Score

$F_{\beta}$ is one of the most popular aggregated evaluation metrics for
classifier evaluation Lever et al. (2016). The parameter $\beta$ is used to
balance recall and precision and is defined as follows:

${}F_{\beta}=\frac{(1+\beta^{2})(precision\times recall)}{\beta^{2}\times
precision+recall}$ (174)

For commonly used $\beta=1$ i.e., $F_{1}$, recall and precision are given
equal weights and Equation (174) can be simplified to:

${}F_{1}=\frac{2TP}{2TP+FP+FN}$ (175)

Since $F_{\beta}$ is based on recall and precision, it does not represent the
confusion matrix fully.

###  5.3 Matthews Correlation Coefficient (MCC)

The Matthews correlation coefficient (MCC) Matthews (1975) captures all the
data in a confusion matrix and measures the quality of binary classification
methods. MCC can be used for problems with uneven class sizes and is still
considered a balanced measure. MCC ranges from $-1$ to $0$ (i.e., the
classification is always wrong and always true, respectively). MCC can be
calculated as follows:

${}MCC=\frac{TP\times TN-FP\times
FN}{\sqrt{\displaystyle\begin{multlined}(TP+FP)\times(TP+FN)\times\\\
(TN+FP)\times(TN+FN)\end{multlined}(TP+FP)\times(TP+FN)\times\\\
(TN+FP)\times(TN+FN)}}$ (176)

While comparing two classifiers, one may have a higher score using MCC and the
other one has a higher score using $F_{1}$ and as a result one specific metric
cannot captures all the strengths and weaknesses of a classifier Lever et al.
(2016).

###  5.4 Receiver Operating Characteristics (ROC)

Receiver operating characteristics (ROC) Yonelinas and Parks (2007) curves are
valuable graphical tools for evaluating classifiers. However, class imbalances
(i.e., differences in prior class probabilities Japkowicz and Stephen (2002))
can cause ROC curves to poorly represent the classifier performance. ROC curve
plots true positive rate (TPR) and false positive rate (FPR):

$TPR=\frac{TP}{TP+FN}$ (177) $FPR=\frac{FP}{FP+TN}$ (178)

###  5.5 Area Under ROC Curve (AUC)

The area under ROC curve (AUC) Hanley and McNeil (1982); Pencina et al. (2008)
measures the entire area underneath the ROC curve. AUC leverages helpful
properties such as increased sensitivity in the analysis of variance (ANOVA)
tests, independence from decision threshold, invariance to a priori class
probabilities, and indication of how well negative and positive classes are in
regarding the decision index Bradley (1997).

For binary classification tasks, AUC can be formulated as:

$\begin{split}AUC&=\int_{-\infty}^{\infty}TPR(T)FPR^{\prime}(T)dT\\\
&=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}I(T^{\prime}>T)f_{1}(T^{\prime})f_{0}(T)dTdT^{\prime}\\\
&=P(X_{1}>X_{0})\end{split}$ (179)

For multi-class AUC, an average AUC can be defined Hand and Till (2001) as
follows:

$AUC=\frac{2}{|C|(|C|-1)}\sum_{i=1}^{|C|}AUC_{i}$ (180)

where _C_ is the number of the classes.

Yang Yang (1999) evaluated statistical approaches for text categorization and
reported the following important factors that should be considered when
comparing classifier algorithms:

  * •

Comparative evaluation across methods and experiments which gives insight
about factors underlying performance variations and will lead to better
evaluation methodology in the future;

  * •

Impact of collection variability such as including unlabeled documents in
training or test set and treat them as negative instances can be a serious
problem;

  * •

Category ranking evaluation and binary classification evaluation show the
usefulness of classifier in interactive applications and emphasize their use
in a batch mode respectively. Having both types of performance measurements to
rank classifiers is helpful in detecting the effects of thresholding
strategies;

  * •

Evaluation of the scalability of classifiers in large category spaces is a
rarely investigated area.

##  6 Discussion

In this article, we aimed to present a brief overview of text classification
techniques, alongside a discussion of corresponding pre-processing steps and
evaluation methods. In this section, we compare and contrast each of these
techniques and algorithms. Moreover, we discuss the limitations of existing
classification techniques and evaluation methods. The main challenge to
choosing an efficient classification system is understanding similarity and
differences of available techniques in different pipeline steps.

###  6.1 Text and Document Feature Extraction

We outlined the following two main feature extraction approaches: Weighted
words (bag-of-words) and word embedding. Word embedding techniques learn from
sequences of words by taking into consideration their occurrence and co-
occurrence information. Also, these methods are unsupervised models for
generating word vectors. In contrast, weighted words features are based on
counting words in documents and can be used as a simple scoring scheme of word
representation. Each technique presents unique limitations.

Weighted words computes document similarity directly from the word-count space
which increases the computational time for large vocabularies Wu et al.
(2008). While counts of unique words provide independent evidence of
similarity, they do not account for semantic similarities between words (e.g.,
“Hello” and “Hi”). Word embedding methods address this issue but are limited
by the necessitation of a huge corpus of text data sets for training Rezaeinia
et al. (2017). As a result, scientists prefer to use pre-trained word
embedding vectors Rezaeinia et al. (2017). However, this approach cannot work
for words missing from these text data corpora.

For example, in some short message service (SMS) data sets, people use words
with multiple meaning such as slang or abbreviation which do not have semantic
similarities. Furthermore, abbreviations are not included in the pre-trained
word embedding vectors. To solve these problems, many researchers work on text
cleaning as we discussed in Section 2. The word embedding techniques such as
GloVe, FastText, and Word2Vec were trained based on the word and nearest
neighbor of that word, and this contains a very critical limitation (the
meaning of a word could be different in two different sentences). To solve
this problem, scientist have come up with the novel methods called
contextualized word representations, which train based on the context of the
word in a document.

As shown in Table 2, we compare and evaluate each technique including weighted
words, TF-IDF, Word2Vec, Glove, FastText, and contextualized word
representations.

Table 1: Feature extraction comparison. Model | Advantages | Limitation
---|---|---
[leftmargin=*,rightmargin=1pt,parsep=5pt,topsep=2pt,partopsep=2pt] Easy to compute Easy to compute the similarity between 2 documents using it Basic metric to extract the most descriptive terms in a document Works with unknown word (e.g., New words in languages) |  • It does not capture position in text (syntactic) • It does not capture meaning in text (semantics) • Common words effect on the results (e.g., “am”, “is”, etc.)
[leftmargin=*,rightmargin=1pt,parsep=5pt,topsep=2pt,partopsep=2pt] Easy to compute Easy to compute the similarity between 2 documents using it Basic metric to extract the most descriptive terms in a document Common words do not effect the results due to IDF (e.g., “am”, “is”, etc.) |  • It does not capture position in text (syntactic) • It does not capture meaning in text (semantics)
[leftmargin=*,rightmargin=1pt,parsep=5pt,topsep=2pt,partopsep=2pt] It captures position of the words in the text (syntactic) It captures meaning in the words (semantics) |  • It cannot capture the meaning of the word from the text (fails to capture polysemy) • It cannot capture out-of-vocabulary words from corpus
[leftmargin=*,rightmargin=1pt,parsep=5pt,topsep=2pt,partopsep=2pt] It captures position of the words in the text (syntactic) It captures meaning in the words (semantics) Trained on huge corpus |  • It cannot capture the meaning of the word from the text (fails to capture polysemy) • Memory consumption for storage • It cannot capture out-of-vocabulary words from corpus
Table 2: Cont. Model | Advantages | Limitation
---|---|---
[leftmargin=*,rightmargin=1pt,parsep=5pt,topsep=2pt,partopsep=2pt] It is very straightforward, e.g., to enforce the word vectors to capture sub-linear relationships in the vector space (performs better than Word2vec) Lower weight for highly frequent word pairs such as stop words like “am”, “is”, etc. Will not dominate training progress |  • Memory consumption for storage • Needs huge corpus to learn • It cannot capture out-of-vocabulary words from corpus • It cannot capture the meaning of the word from the text (fails to capture polysemy)
[leftmargin=*,rightmargin=1pt,parsep=5pt,topsep=2pt,partopsep=2pt] Works for rare words (rare in their character n-grams which are still shared with other words Solves out of vocabulary words with n-gram in character level |  • It cannot capture the meaning of the word from the text (fails to capture polysemy) • Memory consumption for storage • Computationally is more expensive in comparing with GloVe and Word2Vec
[leftmargin=*,rightmargin=1pt,parsep=5pt,topsep=2pt,partopsep=2pt] It captures the meaning of the word from the text (incorporates context, handling polysemy) |  • Memory consumption for storage • Improves performance notably on downstream tasks. Computationally is more expensive in comparison to others • Needs another word embedding for all LSTM and feed forward layers • It cannot capture out-of-vocabulary words from corpus • Works only sentence and document level (it cannot work for individual word level)

###  6.2 Dimensionality Reduction

In Section 3, we outlined many dimensionality reduction techniques. In this
section, we discuss how the efficacy of this step with respect to a text
classification system’s computational time and robustness. Dimensionality
reduction is mostly used for improving computational time and reducing memory
complexity.

PCA attempts to find orthogonal projections of the data set which contains the
highest variance possible in order to extract linear correlations between
variables of the data set. The main limitation of PCA is the computational
complexity of this technique for dimensionality reduction Sharma and Paliwal
(2007). To solve this problem, scientists introduced the random projection
technique (Section 3).

LDA is a supervised technique for dimension reduction that can improve the
predictive performance of the extracted features. However, LDA requires
researchers to manually input the number of components, requires labeled data,
and produces features that are not easily interpretable Putthividhya and Hu
(2011).

Random projection is much faster computationally than PCA. However, this
method does not perform well for small data sets Banerjee (2011).

Autoencoders requires more data to train than other DR methods, and thus
cannot be used as a general-purpose dimensionality reduction algorithm without
sufficient data.

T-SNE is mostly used for data visualization in text and document data sets.

###  6.3 Existing Classification Techniques

In this section, we discuss the limitations and advantages of existing text
and document classification algorithms. Then we compare state-of-the-art
techniques in two tables.

####  6.3.1 Limitations and Advantages

As shown in Tables 3 and 4, the Rocchio algorithm is limited by the fact that
the user can only retrieve a few relevant documents using this model Selvi et
al. (2017). Furthermore, the algorithms’ results illustrate several
limitations in text classification, which could be addressed by taking
semantics into consideration Albitar et al. (2012). Boosting and bagging
methods also have many limitations and disadvantages, such as the
computational complexity and loss of interpretability Geurts (2000). LR works
well for predicting categorical outcomes. However, this prediction requires
that each data point be independent Huang (2015) which is attempting to
predict outcomes based on a set of independent variables Guerin (2016). Naïve
Bayes algorithm also has several limitations. NBC makes a strong assumption
about the shape of the data distribution Soheily-Khah et al. (2017); Wang et
al. (2012). NBC is also limited by data scarcity for which any possible value
in feature space, a likelihood value must be estimated by a frequentist Ranjan
et al. (2017). KNN is a classification method that is easy to implement and
adapts to any kind of feature space. This model also naturally handles multi-
class cases Sahgal and Ramesh (2015); Patel and Srivastava (2014). However,
KNN is limited by data storage constraint for large search problems to find
the nearest neighbors. Additionally, the performance of KNN is dependent on
finding a meaningful distance function, thus making this technique a very
data-dependent algorithm Sahgal and Parida (2014); Sanjay et al. . SVM has
been one of the most efficient machine learning algorithms since its
introduction in the 1990s Karamizadeh et al. (2014). However, they are limited
by the lack of transparency in results caused by a high number of dimensions.
Due to this, it cannot show the company score as a parametric function based
on financial ratios nor any other functional form Karamizadeh et al. (2014). A
further limitation is a variable financial ratios rate Guo (2014). The
decision tree is a very fast algorithm for both learning and prediction, but
it is also extremely sensitive to small perturbations in the data Giovanelli
et al. (2017), and can be easily overfit Quinlan (1987). These effects can be
negated by validation methods and pruning, but this is a grey area Giovanelli
et al. (2017). This model also has problems with out-of-sample prediction
Jasim (2016). Random forests (i.e., ensembles of decision trees) are very fast
to train in comparison to other techniques, but quite slow to create
predictions once trained Bansal et al. (2018). Thus, in order to achieve a
faster structure, the number of trees in forest must be reduced, as more trees
in forest increases time complexity in the prediction step. With regards to
CRF, the most evident disadvantage of CRF is the high computational complexity
of the training step Sutton and McCallum (2006), and this algorithm does not
perform with unknown words (i.e., with words that were not present in training
data sample) Tseng et al. (2005). Deep learning (DL) is one of the most
powerful techniques in artificial intelligence (AI), and many researchers and
scientists focus on deep learning architectures to improve the robustness and
computational power of this tool. However, deep learning architectures also
have some disadvantages and limitations when applied to classification tasks.
One of the main problems of this model is that DL does not facilitate
comprehensive theoretical understanding of learning Shwartz-Ziv and Tishby
(2017). A well-known disadvantage of DL methods is their “black box” nature
Gray and MacDonell (1996); Shrikumar et al. (2017). That is, the method by
which DL methods come up with the convolved output is not readily
understandable. Another limitation of DL is that it usually requires much more
data than traditional machine learning algorithms, which means that this
technique cannot be applied to classification tasks over small data sets
Anthes (2013); Lampinen and McClelland (2017). Additionally, the massive
amount of data needed for DL classification algorithms further exacerbates the
computational complexity during the training step Severyn and Moschitti
(2015).