# ComQA:Compositional Question Answering via
Hierarchical Graph Neural Networks

Bingning Wang1, Ting Yao1, Weipeng Chen1, Jingfang Xu1 and Xiaochuan Wang1,2
1\. Sogou Inc. 2. Tsinghua University.BeijingChina wangbingning,yaoting@sogou-
inc.com

(2018)

###### Abstract.

With the development of deep learning techniques and large scale datasets, the
question answering (QA) systems have been quickly improved, providing more
accurate and satisfying answers. However, current QA systems either focus on
the sentence-level answer, i.e., answer selection, or phrase-level answer,
i.e., machine reading comprehension. How to produce compositional answers has
not been throughout investigated. In compositional question answering, the
systems should assemble several supporting evidence from the document to
generate the final answer, which is more difficult than sentence-level or
phrase-level QA. In this paper, we present a large-scale compositional
question answering dataset containing more than 120k human-labeled questions.
The answer in this dataset is composed of discontiguous sentences in the
corresponding document. To tackle the ComQA problem, we proposed a
hierarchical graph neural networks, which represent the document from the low-
level word to the high-level sentence. We also devise a question selection and
node selection task for pre-training. Our proposed model achieves a
significant improvement over previous machine reading comprehension methods
and pre-training methods. Codes, dataset can be found at
https://github.com/benywon/ComQA.

Question Answering, Graph Neural Networks, Datasets

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

##  1\. Introduction

Question answering (QA) is a long-term research interest in the NLP community
(Phillips, 1960; Greenwood, 2005). Based on the knowledge resource, QA could
be categorized into knowledge-based QA (KBQA), community QA (CQA) or textual
QA. In KBQA, the answer is produced from a knowledge base. In CQA, the answer
is derived from the user-generated content such as FAQ. In textual QA
(Harabagiu et al., 2003), the knowledge resource is unstructured text such as
Wikipedia pages or news articles. Textual QA extracts a sentence or answer
snippet from a supporting document that responds directly to a query, which is
the main form of the current QA system (Yogish et al., 2017).

Figure 1. An example of a compositional QA system where the answer lies in
discontinuous parts of a document. The query is green and the answers are
marked by red frame.

Traditional textual QA is mostly based on symbolic feature engineering (Cui et
al., 2005; Verberne et al., 2009). Recently, with the development of deep
learning methods and large scale datasets, especially the techniques of
machine reading comprehension, the textual based QA systems have been greatly
improved (Seo et al., 2016; Nguyen et al., 2016; Rajpurkar et al., 2016; Dunn
et al., 2017; Dhingra et al., 2017; Kwiatkowski et al., 2019). Most of the
recent advances in textual based QA are sentence-level or phrase level. For
example, most of the answer selection models can be regarded as two-sentence
matching methods, which select the most relevant sentence (or paragraphs) for
a query. On the other hand, most machine reading comprehension methods resort
to span extraction to extract the consecutive answer span in a passage given
the query, where the answer is usually a very short phrase (Baradaran et al.,
2020; Zeng et al., 2020).

However, for the current textual QA applications, some of the answers are
compositional, i.e., they are made up of discontinuous sentences in a
document. Take the case in Figure 1 for
example111https://www.standard.co.uk/go/london/film/tom-hanks-oscars-wins-
nominations-forrest-gump-a4334001.html, given the query asking about Tom
Hanks’ Oscars winning movies, the answer is made up of discontinuous parts in
the page. Concretely, the answer is composed of three sentences-two from the
subtitle and one from a sentence in the first paragraph. Current QA systems,
focus on either sentence-level or phrase-level, are unable to tackle this
problem.

In this paper, we are focusing on Compositional Question Answ-
ering (ComQA), where the answer is from the discontiguous but relevant
sentences in a document. For the currently available QA datasets, none of them
are focus on compositional answers, so we construct a large scale Chinese
compositional QA dataset through crowdsourcing. First of all, we select the
web pages whose title is a valid question. Then we conduct the page analysis
to extract the main content of the page as the document. Next, we transform
the original document HTML to a list of sentence-like items that each item can
serve as a candidate component of the final answer. Finally, we feed the
question and the transformed page to the crowd workers to select the answers.

Compared with previous textual based QA, the ComQA has three characteristics:
1) Rather than restricting the answer to be a span or a sentence of the text,
ComQA loosens the constraints so that the answer may lie in discontiguous
components in a document. 2) The basic granularity of ComQA is a sentence.
However, every element in the dom-tree of the page’s HTML, e.g., a table or an
image, could be a valid component to form the final answer. 3) Since the
answer in ComQA is composed of different granularity, it introduces the
specific inductive bias of the document structure to the model, requiring a
hierarchical understanding of the text from the low-level words to high-level
paragraphs.

To tackle the problem of compositional answers, we proposed a novel
hierarchical graph neural networks on the ComQA. Concretely, we first adopt a
BERT-like sequential encoder to obtain the basic token representations. Then
we represent the question and the elements of the document in a graph. The
graph is constructed from dom-tree of the page with different levels of
connection. Finally, we represent each node in the graph with the attention-
based hierarchical graph neural networks. The final prediction is based on the
node representations in the graph.

Focusing on document understanding, we also devise two novel pre-training
tasks for our proposed hierarchical graph neural networks: the first one is
the question selection task to determine the relationship between the question
and the document. The second is the node selection task measuring the
contextual dependency of a node in the document. We conduct comprehensive
experiments on the ComQA dataset. The proposed attention-based hierarchical
graph neural networks achieve significant improvement compared with the state-
of-the-art QA baselines, including the widely used machine reading
comprehension model BiDAF (Seo et al., 2016) and recently proposed pre-
training model BERT (Devlin et al., 2018). The ablation study shows the
advantage by incorporating the graph structure and pre-training. In summary,
our contributions are:

  1. (1)

This paper investigates the compositional question answering, where the
answers are composed of discontiguous supporting sentences in the document.

  2. (2)

We present a new human-labeled compositional question answering dataset
containing more than 120k QA pairs. To our best knowledge, this is the largest
one in this domain.

  3. (3)

We propose a hierarchical graph neural networks on the compositional QA, and
two novel tasks are devised to pre-train the model. The proposed model
achieves significant improvement over previous methods such as BiDAF (Seo et
al., 2016) or BERT (Devlin et al., 2018).

##  2\. Related Work

Question Answering. QA has been a long-term focus in artificial intelligence
that can date back to the 1960s, where Green Jr et al. (1961) proposed a
simple system to answer questions about baseball games. Since then, many works
have been done to use diverse data resources to answer any type of question.
Compared to other types of QA such as knowledge base QA or community QA, in
textual QA the knowledge resource is the plain text such as document or
paragraph, which is currently regarded as the machine reading comprehension
(MRC). Since the MCTest (Richardson et al., 2013) was proposed, many
researchers have been focused on MRC. Hermann et al. (2015) proposed a cloze-
style dataset CNN/Daily Mail where the questions and answers are automatically
generated from the news article. Recently, some human create large-scale
authentic datasets have been released, such as SQuAD (Rajpurkar et al., 2016),
NewsQA (Trischler et al., 2016), etc. However, most answers in these datasets
are based on the contiguous segments in the text, and most MRC methods are
based on span extraction, which can hardly deal with the compositional answers
in QA.

Compositional QA. Some works have also been proposed to solve the
compositional answers in QA. In MARCO (Nguyen et al., 2016) dataset, some
answers could not be directly derived from the passage, Yang et al. (2020) and
Zhang et al. (2020) proposed to generate the answer based on the multi-span
extraction and scoring scheme. However, their works are heavily based on the
text’s syntactic features to extract a continuous span. Besides, the answers
are not really compositional in MARCO, given that most non-extractive answers
are continuous span in the passage combined with a span in the question. A
specific dataset called (Dua et al., 2019) has been proposed containing the
multi-span answers. Nevertheless, the compositional answers only account for
6% of the datasets, and each answer span is short phrases. MultiRC (Khashabi
et al., 2018) is a multiple-choice dataset requiring reading comprehension
from multiple sentences. Nevertheless, the dataset is too small to train an
applicable model, and the multiple evidence sentences are not corresponding to
the final answer. Furthermore, in MultiRC the questions are synthetic by
humans, while our proposed ComQA consists of real-world questions. Some multi-
hop QA datasets have recently been released, such as WikiQA (Welbl et al.,
2018) and HotpotQA (Yang et al., 2018), but they are mainly focused on the
multi-document reasoning and the answer is continuous span in one document.

Different from their works, in this paper, we are only focusing on
compositional QA, where the answers are derived from multiple but
discontiguous segments in the documents. And the proposed ComQA is large-
scale, containing more than 120k questions.

Graph Neural Networks. Graph neural network (GNN) is a kind of deep learning
method that operates in the graph. It has gained wide attention due to its
convincing performance and high interpretability. GNN incorporate the explicit
relational inductive bias to the model (Battaglia et al., 2018) to perform
structure reasoning. Kipf and Welling (2016) proposed graph convolutional
network to conduct semi-supervised learning on the club network. To focus on
the important part of the graph, Veličković et al. (2018) proposed the graph
attention networks. Many other NLP tasks have also employed the GNN to model
the text, such as relation extraction (Zhang et al., 2018), text
classification (Yao et al., 2019), dependency parsing (Ji et al., 2019), or
question answering (Tian et al., 2020) etc.

##  3\. Compositional QA

In this section, we will first introduce the ComQA in detail. Next, we will
describe the data construction process.

Compositional QA is similar to the machine reading comprehension, where the
system produces an answer given the question and a corresponding document.
However, in ComQA, the answer is located in different parts of the document,
just like the instance illustrated in Figure 1. In this paper, we classify the
answer components into two types:

Sentence: sentence is the basic component in ComQA. The sentence could be a
subtitle on the page; for example, the sentence in Figure 1 with a bold and
large font. Or intra-paragraph sentences. We use the simple heuristic rules to
divide the paragraph into several sentences, and each sentence could be a
valid candidate answer component.

Special HTML Element: For many questions in ComQA, the answer may lie in a
specific element on the page other than the raw paragraphs. For example, for
the question ‘How to turn on PS4 motion controller?’ the answer may consist of
several images describing the operation process. Another example is when the
document is a wiki page of ‘List of highest mountains on Earth’, it contains a
table of the ranking of the world highest mountains, when asked about the
‘third highest mountain in the world’, we should extract the third item in the
table as the answer. In this paper, we kept several special HTML tags that
potentially compose the answer. They are listed in Table 1.

Tag | Definition
---|---
br | produces a line break in text
p | paragraph marker
img | image content
table | table content
strong | define important text in a document
tbody | group the body content
h1-h6 | define headings
Table 1. The HTML tags we kept as the special nodes in the document graph.

The answer in ComQA is made up of the above two types of components, which we
refer to as node in the rest of the paper. Other types of answers, such as
phrases and words in the paragraph or video elements in the HTML tree, are
also valid for ComQA. However, adding them would increase the tasks’
difficulty, so we leave them for future works. In ComQA the system should
assemble the discontiguous nodes as the answer.

###  3.1. Dataset Collection

We collect the ComQA dataset based on the Chinese search engine Sogou
Search222https://www.sogou.com/. The data construction consists of four
stages: First, we obtain the question-document through a search engine. Then
we process the documents into nodes. Next, crowdsourcing workers were asked to
select the corresponding nodes in the document to answer the question.
Finally, we conduct quality inspection on the labeled dataset to filter out
invalid samples.

####  3.1.1. Question-Document Collection

We first obtain the question from the web. We select the pages for which the
titles are valid questions and treat the title as the question. We use rules
to determine whether a title is a valid question, including: 1) whether the
question contains the interrogative pronoun such as ‘谁是’(‘who’), ‘如何’(‘how
to’), etc. 2) the title containing the informative words such as ‘的过程’(‘the
process of’), ‘的方法’(‘the method to’), etc. The question words and informative
words are listed in the Appendix. Although the two rules are simple, we found
it is really effective that more than 90% of the selected titles are valid
questions.

Next, we also do some filtering process on the selected documents for which
the title is a question. We limit the page source to be a list of sites with
high quality. Then we filter out the pages containing no text content or just
a pure advertising page. We also remove the pages that are either too long or
too short.

After the above two processes, we obtain a lot of high-quality question-
document pairs. However, since the web content tends to be duplicated, some of
the pages may have highly lexical or semantic overlap. To remove the redundant
pages and increase the final dataset’s diversity, we represent the page
document based on the bag-of-words. We use Ward (Ward Jr, 1963) clustering
algorithm to cluster those documents into 350k clusters. We select the
centroid in each cluster as the final document for crowdsourcing.

Figure 2. The type of the questions in ComQA.

####  3.1.2. Documents Processing

Now we processed the document into a list of nodes (i.e., sentences and
special HTML elements). We first extract the main content of the page. Then we
use the hierarchical structure of the HTML to locate the leave nodes in the
dom tree. For each leave node, we use its structure features and attributes
features to determine whether it is a text node or a special HTML element. We
remove the HTML element which is not text content or special HTML element.
Finally, we merge the redundant nodes and unnecessary items to form the
cleaned document.

####  3.1.3. Answer Annotation

We employed crowdworkers to select the answers from the document for each
question. We build an HTML based annotation platform so that the crowdworkers
could annotate on both computer and mobile devices. For the annotation page,
we treat each node in the document as a single element that could be clicked
as the answer component. The final answer is the combination of the selected
nodes. For the page that the title is not a valid question or the document
doesn’t contain the right answer, crowdworkers are asked to select none of the
nodes. A snapshot of the annotation page is shown in Figure 8.

####  3.1.4. Quality Inspection

We conduct a quality inspection after the data has been annotated by the
crowdworkers. Since the dataset is really large, we must select the data
samples that may be erroneously annotated. We do this by the following stages:
first of all, similar with cross-validation (Hastie et al., 2009), we divided
the data into ten folds, we train a model on the nine folds and evaluate on
the other one fold. For the one fold held out data, we select the samples that
are ambiguous to the current model, i.e. the log probability of the real
answer is very small, as the candidate wrong data. This process is conducted
ten times, and we select the most unconfident data for the model. This fake
data selection process is similar to recent researches which find the hard to
learn samples often correspond to labeling errors (Swayamdipta et al., 2020).
Finally, we feed those samples to the authoritative checkers who are well
informed of the ComQA tasks and relabeled those samples.

After the above four processes, we obtain the training ComQA samples that have
gone through the quality inspection. Each data instance is made up of: a URL,
a question, a document containing a list of quaternion with the form
$<id,type,content,label>$, id is the index of the nodes in the document, type
is the node type, for example, sentence or image, label could be 0 or 1
indicating whether the node is an answer component.

####  3.1.5. Test Set Construction

Since the test set demands a higher quality than the training set, we ask the
two authoritative checkers to annotate the same data and select the instances
with which the two checkers accord.

Finally, we get 122,343 samples from crowdworkers. We use 5000 of them as the
development set and the rest 117,343 as the training set. Moreover, we get
2,054 test samples annotated by authoritative checkers. The documents have
average 581 words, and the queries have 7.4 words on average. And each
document containing about 23.1 nodes, with 21.2% (4.9) of them are annotated
as the answer nodes. Each node has average 24.8 words. The questions in ComQA
cover a broad range of topics such as medical, entertainment, etc. The most
common question words in ComQA is shown in Figure 2.

Figure 3. Hierarchical graph neural networks for ComQA, the case shows how to
represent the question ($q$), two sentences ($s_{1},s_{2}$) and a special
image node ($h_{1}$). Left:, the basic BERT sequence encoder to obtain the
contextualized representations for each token. The input is the concatenation
of question and document tokens. We append some special tokens to indicate the
question (<SEP>), sentence (<EOS>) and special html image element <IMG>.
Middle: The hierarchical graph neural networks blocks, which uses the intra-
sentence connection, inter-sentence connection, and global connection (omitted
for concise view) to build a hierarchical representation of the document
graph. The final prediction is made upon the sentence nodes (green) and
special html nodes (purple). Right: The connection mask matrix (or better
known as the adjacency matrix in graph neural networks) used to connect the
different tokens in the graph.

##  4\. Hierarchical Graph Neural Networks for ComQA

In this section, we describe the proposed hierarchical graph neural networks
(HGNN) for the compositional QA. Denote the document as a graph $\mathcal{G}$,
which is a tuple $(\mathcal{N},\mathcal{E})$.
$\mathcal{N}=\\{\mathcal{N}_{i}\\}_{i=1}^{N_{\mathcal{N}}}$ is the node set,
and the $i_{\text{th}}$ node $\mathcal{N}_{i}$ consists of a sequence of words
$\\{\mathcal{N}_{i}^{1},\mathcal{N}_{i}^{2},...,\mathcal{N}_{i}^{|\mathcal{N}_{i}|}\\}$.
$|\mathcal{N}_{i}|$ is the number of words in the $i_{\text{th}}$ node. We
represent the question as a special node in $\mathcal{N}_{q}$.
$\mathcal{E}=\\{e_{i}\\}_{i=1}^{N_{\mathcal{E}}}$ is the edge set. The
prediction is made upon the normal nodes
$\\{\mathcal{N}_{i}\\}_{i=1}^{N_{\mathcal{N}}}$. Our proposed HGNN consists of
three modules: the basic sequence encoder, hierarchical graph attention layer,
and final prediction layer, the whole architecture is illustrated in Figure 3.

###  4.1. Sequence Encoder

The sequence encoder is a BERT-like module to obtain the basic
representations. First of all, we represent the question and document into a
single sequence by concatenating the question tokens and every document node
tokens. We add a special <SEP> token after the question tokens, and add a
special <EOS> token after each sentence. For each special HTML node, we also
use the special tokens, such as <IMG>, <BR>, etc., to represent them.

####  4.1.1. Embedding Layer

We first use the Byte Pair Encoding (BPE) (Sennrich et al., 2016) to tokenize
the sequence into word pieces. Suppose the sequence length is $N$, for each of
the word pieces in the sequence, we use the word embedding layer to transform
them into $\textbf{H}_{w}\in\mathbb{R}^{N\times D}$ where $D$ is the embedding
size. We also use position embedding to get the sequence positional embedding
$\textbf{H}_{p}\in\mathbb{R}^{N\times D}$. Finally, we also apply the type
embedding to the sequence resulting $\textbf{H}_{t}\in\mathbb{R}^{N\times D}$
to indicate whether it is in the question or in the document. The final
embedding output is the addition of the three embeddings:

(1) $\textbf{H}_{0}=\textbf{H}_{w}+\textbf{H}_{p}+\textbf{H}_{t}$

####  4.1.2. Self Attention Layer

After the embedding layer, we apply the self-attention based Transformer
(Vaswani et al., 2017) layer to the input. A list of $L$ Transformer blocks
are used to project the input embedding into the contextualized
representations. For the $l_{\text{th}}$ layer in the Transformer, the output
could be denoted as:

(2) $\displaystyle\textbf{Q}_{l},\textbf{K}_{l},\textbf{V}_{l}=$
$\displaystyle\textbf{W}_{q}^{l}\textbf{H}_{l-1},\textbf{W}_{k}^{l}\textbf{H}_{l-1},\textbf{W}_{v}^{l}\textbf{H}_{l-1},$
$\displaystyle\hat{\textbf{H}}_{l}^{k}=$
$\displaystyle\text{Softmax}(\frac{\textbf{Q}_{l}^{T}\textbf{K}_{l}}{\sqrt{D}})\textbf{V}_{l},\forall
k\in[1,K]$ $\displaystyle\bar{\textbf{H}}_{l}=$
$\displaystyle\text{Projection}(\text{Concat}([\hat{\textbf{H}}_{l}^{1},...,\hat{\textbf{H}}_{l}^{K}]))$
$\displaystyle\textbf{H}_{l}=$
$\displaystyle\text{LayerNorm}(\bar{\textbf{H}}_{l})$

W is the learnable weight matrices and the Project is a multi-layer perceptron
to project the output of the multi-head attention back to the hidden space.
$K$ is the number of head in Transformer. Layer normalization (Ba et al.,
2016) is applied before the output.

###  4.2. Hierarchical Graph Neural Networks

In HGNN, node embeddings are initialized with sequence encoder’s last layer
output $\textbf{H}_{L}$, followed by hierarchical graph representations.
Formally, the HGNN is built upon the general message passing architecture:

(3) $\small\textbf{H}^{k}=f\left(A,\textbf{H}^{k-1};\textbf{W}^{k}\right)$

where $\textbf{H}^{k}\in\mathbb{R}^{N\times D}$ are the node embeddings after
$k$ hop of computation in the graph, $A\in\mathbb{R}^{N\times N}$ is the
adjacency matrix representing the graph structure.
$\textbf{W}^{k}\in\mathbb{R}^{D\times D}$ is the trainable parameters for
different graph layers. $f$ is the message propagation function for
information aggregation. In this paper, the layer-wise propagation rule of
HGNN is formulated as:

(4)
$f\left(A,\textbf{H}^{k-1};\textbf{W}^{(k)}\right)=\operatorname{GeLU}\left(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}\textbf{H}^{k-1}\textbf{W}^{k}\right)$

where Gelu is the gaussian error linear activation function (Hendrycks and
Gimpel, 2016). $\tilde{A}=A+I,\tilde{D}=\sum_{j}\tilde{A}_{ij}$ are used to
normalization since directly multiplication with $A$ will completely change
the scale of the input. There are $M$ layers (hops) in the HGNN and the final
output is $\textbf{H}^{M}$.

####  4.2.1. Graph Construction

Graph construction is one of the most important factors for the good
performance of graph neural networks (Hamilton et al., 2017; Kipf and Welling,
2016). In this paper, we consider three types of connection:

Intra-Sentence Connection: For each word in a sentence, we connected them with
each other. Specifically, the special tokens such as <EOS> are also connected
with other words in the same sentence:

$A_{i,j}^{\text{intra}}=\left\\{\begin{array}[]{ll}1&\text{{if i and j are
located in the same sentence.}}\\\ 0&\text{{otherwise.} }\end{array}\right.$

Thus, the intra-sentence graph connection is formulated by the adjacent matrix
$A^{\text{intra}}$.

Inter-Sentence Connection: We have already appended the special tokens after
each sentence as the high-level node identification, so we add the inter-
sentence connection to those special tokens in the document. If the node
corresponding tokens belongs to the special tokens, i.e. <SEP>, <EOS> and the
special HTML element tokens, we add a connection between them:

$A_{i,j}^{\text{inter}}=\left\\{\begin{array}[]{ll}1&\text{{if i and j belongs
to the special tokens}}\\\ &\text{{indicating the higher level node.}}\\\
0&\text{{otherwise}.}\end{array}\right.$

Global Connection: When represent the document in QA, question attention is
very important (Seo et al., 2016; Yu et al., 2018). However, only employing
the inter-sentence connection, where the interaction between the words in the
document and the words in the question are all based on their high-level
sentence indicators, may incur the modeling burden for the attention based
model (Zaheer et al., 2020). Therefore, we also construct the global
connection between the question indicator <SEP> and all other words in the
document:

$A_{i,j}^{\text{global}}=\left\\{\begin{array}[]{ll}1&\text{{if i is
{<{SEP}>}},}\forall j\in[1,N]\\\ 0&\text{{otherwise}.}\end{array}\right.$

####  4.2.2. Information Aggregation

After the graph construction process, we build the graph representations based
on Equation 4. However, since the graph is hierarchical containing different
level of nodes with different connections, we have two options to represent
them:

Pipeline Aggregation: We could build the hierarchical representation in
pipeline, that is, we first build the low-level intra-sentence
representations, then we build the higher level inter-sentence and global
representations:

(5)
$\displaystyle\textbf{H}_{\text{intra}}^{k}=\operatorname{GeLU}\left(\tilde{D}_{\text{intra}}^{-\frac{1}{2}}\tilde{A}_{\text{intra}}\tilde{D}_{\text{intra}}^{-\frac{1}{2}}\textbf{H}^{k-1}\textbf{W}_{\text{intra}}^{k}\right)$
$\displaystyle\textbf{H}_{\text{inter}}^{k}=\operatorname{GeLU}\left(\tilde{D}_{\text{inter}}^{-\frac{1}{2}}\tilde{A}_{\text{inter}}\tilde{D}_{\text{inter}}^{-\frac{1}{2}}\textbf{H}_{\text{intra}}^{k}\textbf{W}_{\text{inter}}^{k}\right)$
$\displaystyle\textbf{H}^{k}=\operatorname{GeLU}\left(\tilde{D}_{\text{global}}^{-\frac{1}{2}}\tilde{A}_{\text{global}}\tilde{D}_{\text{global}}^{-\frac{1}{2}}\textbf{H}_{\text{inter}}^{k}\textbf{W}_{\text{global}}^{k}\right)$

Fused Aggregation: The pipeline aggregation build the graph representation in
a hierarchical way, however, we can instead pack them into a single operation
by fusing the three-level adjacency matrices into one:

(6) $A_{i,j}=\left\\{\begin{array}[]{ll}1&\text{if
}{\left\\{\begin{array}[]{ll}A_{i,j}^{\text{intra}}=1\text{ or}\\\
A_{i,j}^{\text{inter}}=1\text{ or}\\\
A_{i,j}^{\text{global}}=1\end{array}\right.}\\\
0&\text{{otherwise}.}\end{array}\right.$

Based on the fused adjacency matrix, we can build the graph representations
based on Equation 4. The adjacency matrix is also illustrated in the right of
Figure 3. In experiment, we will compare the two types of aggregation scheme.

###  4.3. Prediction and Objective

After representing the question and document by the graph neural networks, we
collect the sentence-level nodes and make predictions on them. Those sentence
level nodes including the <EOS> and special HTML tokens, forming the answer
candidate set $\mathcal{S}$. The final probability of each node in
$\mathcal{S}$ is calculated by:

(7)
$P_{i\in\mathcal{S}}=\sigma(\textbf{H}^{M}_{i\in\mathcal{S}}\textbf{w}_{o})$

where $\sigma$ is the sigmoid function and $\textbf{w}_{o}$ is the weight
vector to project the last layer representations of HGNN into scalar values.

The objective of the model is to minimize the binary cross-entropy between the
predictions and real labels:

(8)
$\mathcal{L}_{BCE}=-\mathbbm{1}_{i\in\mathcal{S}_{P}}\log\left(P_{i\in\mathcal{S}_{P}}\right)-\mathbbm{1}_{i\in\mathcal{S}_{N}}\log\left(1-P_{i\in\mathcal{S}_{N}}\right)$

where $\mathcal{S}_{P}$ is the positive (1) nodes set and $\mathcal{S}_{N}$ is
the negative (0) nodes set in a document,
$\mathcal{S}_{P}\cup\mathcal{S}_{N}=\mathcal{S}$.

###  4.4. Unsupervised Pre-training

Recent works on NLP have shown the great advantage of large-scale pre-training
(Devlin et al., 2018; Radford et al., 2019; Roberts et al., 2020). However,
different from the previous works of pre-training where the input is the raw
text sequence, the ComQA contains the information of document structure.
Therefore, we devised three types of unsupervised objectives for pre-training:

Masked Language Model (MLM): similar to Devlin et al. (2018), we masked some
words in the sequence, and the model must predict the original words based on
the surrounding context. We mask 15% of the sequence and do not mask the
special tokens.

Question Selection (QS): Since ComQA is constructed from the web pages where
the question is the page’s title and the document is the page content. There
is an inherent correlation between the question and the document. So we
propose the question selection pre-training, a binary classification task to
determine whether the question, i.e., the title, is relevant to the document.
We replace the title with a random title as the fake example, and the original
title-document as the positive example. We use the representations of the
question indicator $\textbf{H}^{M}_{i=\texttt{<{SEP}>}}$ for prediction just
as in Equation 7, except that we use the different weight vector.

Node Selection (NS): In addition to the question selection, we can also
perform a node selection task on the nodes to determine whether it is relevant
to its contextual document. This task is similar to the ComQA where the
prediction is also made on document nodes. We use two heuristic rules to
construct the negative nodes: 1) we replace the sentence in the document with
a random sentence. 2) we randomly shuffle the words in the sentence and treat
the resulting sentence as a negative node. 3) we randomly swap the two nodes
in the document and treat the two nodes as negative. We also replace 15% of
the original nodes in the document as the negative nodes.

|  | Dev | Test
---|---|---|---
|  | Precision | Recall | F1 | Accuracy | Precision | Recall | F1 | Accuracy
| SequentialTag${}_{\text{lstm}}$ | 51.7 | 59.1 | 56.0 | 33.9 | 43.2 | 56.1 | 47.9 | 25.3
| SequentialTag${}_{\text{bert}}$ | 65.3 | 78.2 | 73.1 | 38.2 | 61.9 | 73.7 | 66.5 | 32.9
| LSTM | 73.1 | 39.9 | 55.3 | 28.2 | 83.4 | 46.1 | 59.4 | 28.2
| BiDAF | 72.5 | 64.7 | 69.1 | 35.7 | 69.4 | 58.7 | 63.9 | 30.2
| QA-Net | 75.4 | 63.3 | 68.8 | 36.6 | 71.6 | 60.9 | 65.3 | 31.8
| BERT${}_{\text{official}}^{*}$ | 81.9 | 64.8 | 70.9 | 35.3 | 81.1 | 66.2 | 72.9 | 35.4
| BERT${}_{\text{base}}$ | 84.2 | 78.3 | 80.5 | 42.9 | 73.5 | 75.4 | 74.1 | 37.9
| BERT${}_{\text{large}}$ | 85.1 | 79.2 | 82.1 | 46.3 | 77.3 | 78.0 | 77.6 | 43.2
Pipeline | HGNN${}_{\text{small}}$ | 79.3 | 76.1 | 76.9 | 42.0 | 68.2 | 74.5 | 72.0 | 36.5
HGNN${}_{\text{base}}$ | 83.0 | 81.7 | 81.9 | 44.8 | 74.2 | 75.9 | 75.1 | 40.7
HGNN${}_{\text{large}}$ | 84.4 | 82.5 | 83.3 | 48.2 | 77.1 | 78.9 | 78.0 | 44.9
HGNN${}_{\text{large}}$+QS+NS | 85.9 | 83.1 | 84.2 | 50.8 | 78.4 | 78.5 | 78.4 | 46.3
Fused | HGNN${}_{\text{small}}$ | 80.2 | 75.1 | 77.2 | 42.9 | 70.7 | 75.8 | 73.9 | 38.2
HGNN${}_{\text{base}}$ | 86.0 | 82.1 | 83.4 | 47.3 | 76.6 | 78.1 | 77.3 | 43.8
HGNN${}_{\text{large}}$ | 86.9 | 83.7 | 85.4 | 50.7 | 78.9 | 80.0 | 79.0 | 47.1
HGNN${}_{\text{large}}$+QS+NS | 87.3 | 84.9 | 86.8 | 53.9 | 79.6 | 80.3 | 79.9 | 49.2
| Human | - | - | - | - | 88.5 | 91.0 | 89.8 | 80.5
Table 2. Main results on ComQA. The first SequentialTag model is based on
sequential tagging to select the relevant segments in the doc. The middle six
models are based on the plain sequential tags without structure information.
For BERT${}_{\text{official}}$ model, since the max sequence length was
limited to 512, the recall and accuracy are relatively low. Pipeline and Fused
refers to the two graph information aggregation operations. QS and NS refers
to our model pre-trained with additional question selection and node selection
tasks described in Section 4.4.

##  5\. Experiments

###  5.1. Common Setup

In all experiments, we tokenize the text with BPE by sentencepiece (Kudo and
Richardson, 2018). We set the vocabulary size to 50,000. We use the Adam
(Kingma and Ba, 2014) optimizer with 5k warm-up steps and linearly decay the
learning rate. $\beta_{1},\beta_{2},\epsilon$ was set to 0.9, 0.99 and
$10^{-6}$, respectively. For both pre-training and fine-tuning, the max
learning rate was set to $10^{-4}$. We applied decoupled weight decay
(Loshchilov and Hutter, 2018) to the model with scale 0.1. Dropout (Srivastava
et al., 2014) was applied to every parameter and attention mask with drop
probability 0.1. We clip the max grad norm to 0.2. The batch size was 256
during pre-training and 64 during fine-tuning. We truncate the document
sequence length to 1024. We use Pytorch (Paszke et al., 2019) 1.4.0 framework.
All experiments are conducted through 16 volta V100 GPUs.

We trained three types of HGNN model. HGNN${}_{\text{small}}$ is the small
version of the model containing 6 layers of the Transformer encoder, each
layer contains 8 heads with hidden size 512. HGNN${}_{\text{base}}$ is the
base version of the proposed model, which contains 12 layers of the
Transformer encoder, each layer containing 12 heads with hidden size 768.
HGNN${}_{\text{large}}$ is the large version of the proposed model containing
24 layers of Transformer encoder, the head, and hidden size was set to 16,
1024, respectively. For the hierarchical graph neural networks, we set the
number of layers $M$ to 4.

We use 400 million Chinese web pages for pre-training, those data occupy
nearly 1.2Tb disk space. We clean the document by removing the hyperlink,
phone number, or special symbols. It needs to mention that for the QS pre-
training task, we restrict the title to be a valid question. For other types
of pre-training such as MLM and NS, we just use the unfiltered web pages. We
conduct 1 million pre-training steps for all pre-training model. The pre-
training loss of HGNN${}_{\text{base}}$ is shown in Figure 4.

Figure 4. The pre-training loss of the proposed HGNN${}_{\text{base}}$ model.
The x-axis is the pre-training steps ($\times 100$).

###  5.2. Evaluation Metrics

In ComQA, each document has several nodes that could be selected as the answer
components, denote the nodes that the model predict is true as
$\mathcal{S}_{R}:\\{i|P_{i}>\text{threshold}\\}$. For each document, we could
define the Precision, Recall and F1 and Accuracy:

$\displaystyle\text{Precision}=\frac{|\mathcal{S}_{P}\bigcap\mathcal{S}_{R}|}{|\mathcal{S}_{P}|}$
$\displaystyle\text{Recall}=\frac{|\mathcal{S}_{P}\bigcap\mathcal{S}_{R}|}{|\mathcal{S}_{R}|}$
$\displaystyle\text{F1}=\frac{2\times\text{Precison}\times\text{Recall}}{\text{Precison}+\text{Recall}}$
$\displaystyle\text{Accuracy}={\left\\{\begin{array}[]{ll}1&\text{if
}\mathcal{S}_{P}\equiv\mathcal{S}_{R}\\\
0&\text{otherwise}\end{array}\right.}$

The threshold was tuned in the development set. The accuracy is a binary value
denoting whether all answer nodes are correctly selected. And we average every
document’s precision, recall, F1, and accuracy as the final precision, recall,
F1, and accuracy, respectively. It needs to mention that the positive node set
$\mathcal{S}_{P}$ could be empty.

###  5.3. Baseline Methods

We compare our model with five baseline models:

  * •

SequentialTagging: We use a sequential tagging method which predicts the begin
, in and out (BIO) tag of each word in the document. This model is flexible to
select the discrete segments in the document. However, the selected segments
are not guaranteed to match a sentence. Therefore, we select the sentence with
more than half of its words are annotated as $B$ or $I$, as the prediction set
$\mathcal{S}_{R}$. Specifically, we select two types of sequential tagging
model, the first one is based on BiLSTM (Chiu and Nichols, 2016), and the
second one is based on BERT (Devlin et al., 2018).

  * •

LSTM (Hochreiter and Schmidhuber, 1997) is based on the bi-directional LSTM to
process the question and document in a sequential way. Like the proposed HGNN,
we concatenate the question and document tokens. The prediction is also made
on the special token.

  * •

BiDAF (Seo et al., 2016) is a widely used attention-based method. It builds
the LSTM based bi-directional attention flow between the words in the question
and the words in the documents, which achieves promising results in many QA
tasks. Other than predicting the start and end position of the answer span, we
use the same prediction methods in Section 4.3 for answer nodes selection.

  * •

QA-Net (Yu et al., 2018) is the current state-of-the-arts machine reading
comprehension method without pre-training. QAnet does not require recurrent
networks but consists exclusively of convolution and self-attention, where
convolution models local interactions and self-attention models global
interactions. Different from the original paper (Yu et al., 2018), we only
adopt the architecture and did not apply backtranslation for data
augmentation.

  * •

BERT (Devlin et al., 2018) is a pre-training method that pushes many NLP tasks
into new record. It is based on the encoder of the Transformer (Vaswani et
al., 2017), the objective is the masked language modeling and next sentence
prediction. In fact, our model without hierarchical graph neural networks is
reduced to the BERT model. We use two types of BERT model, the first one is
the official released Chinese version BERT base
model333https://github.com/huggingface/transformers
(BERT${}_{\text{official}}$). However, the max length of the official BERT is
512, which will truncate too many samples in ComQA. So we also pre-train the
BERT on the same data we pre-trained the HGNN with max length 1024. We also
train two types of BERT model, i.e. BERT${}_{\text{base}}$ and
BERT${}_{\text{large}}$.

| #Head | #Layer | #Hidden | #Interconnect | #Parameter
---|---|---|---|---|---
LSTM | - | 3 | 128 | - | 6,796,544
QA-Net | - | - | 128 | - | 13,876,706
BiDAF | - | - | 100 | - | 10,747,168
BERT${}_{\text{official}}$ | 12 | 12 | 768 | 3072 | 102,268,416
BERT${}_{\text{base}}$ | 12 | 12 | 768 | 3072 | 102,268,416
BERT${}_{\text{large}}$ | 16 | 24 | 1024 | 4096 | 329,486,296
HGNN${}_{\text{small}}$ | 8 | 6 | 512 | 2048 | 45,561,856
HGNN${}_{\text{base}}$ | 12 | 12 | 768 | 3072 | 125,400,576
HGNN${}_{\text{large}}$ | 16 | 24 | 1024 | 4096 | 362,579,328
Table 3. The specific configuration of different models.

The specific configurations of those models are listed in Table 3. In addition
to the above baselines, we also evaluate human performance. We randomly sample
200 questions from the test sets and asks a volunteer to get human
performance. The result of those models in dev and test set are shown in Table
2.

###  5.4. Main Results

We can see from the table that our model achieves the best result compared
with the other baseline models. For the sequential tagging model, the
prediction is made upon the word level, but the evaluation is made upon the
sentence level. This training-evaluation gap results in poor performance in
ComQA. The performance of LSTM is really poor since it contains no attention
mechanism that is vital for QA (Huang et al., 2018). Besides, the input of the
ComQA is a document containing more than 500 tokens on average. The current
sequential model may have difficulty processing such long sequence. For BiDAF
and QA-Net, although they have achieved good performance in many QA tasks,
they still lag behind the pre-training methods.

The proposed HGNN is based on BERT, nevertheless, it achieves 3.2/5.9 absolute
gain of F1/accuracy on the based version of the model, and 1.4/3.9 absolute
improvement on the large model, which shows the effectiveness of the proposed
hierarchical graph neural networks. The HGNN is based on BERT, but it
introduces the inductive bias of the document structure to the model. From our
point of view, the graph structure guides the information aggregation from the
words to the sentences to the document, which is very important for ComQA.

For the two types of information aggregation methods, we found the fused
aggregation, which merges the three-level connection in a single adjacency
matrix, has a better performance. Since the pipeline aggregation directly
separates the three-level aggregation, the low-level information still has the
difficulty to propagate to the high level, let alone the HGNN is multi-layer.

However, as human achieves 80.5 accuracy on the test set, our results suggest
that there is still room for improvement in ComQA.

Figure 5. Ablation over number of pre-training steps. The x-axis is the number
of parameter updates. We fine-tune each checkpoint 20 epochs, and show the
boxplot of the 20 results. We report the F1 and accuracy over the
HGNN${}_{\text{base}}$ model (based on Fused connection, upper half) and
BERT${}_{\text{base}}$ model (lower half).

###  5.5. The Effect of Pre-training

We can see from the table 2 that the model with pre-training could obtain
significant improvement. In this section, we want to investigate the effect of
pre-training in more detail. Concretely, we want to investigate the pre-
training in two aspects: the scale of the pre-training and the objective of
pre-training.

First of all, Liu et al. (2019) and Devlin et al. (2018) have shown that more
pre-training steps could consistently improve the performance of the
downstream tasks a lot. So we load the checkpoints of the model during the
pre-training dynamics and fine-tuned it on the ComQA dataset. Each model is
fine-tuned 20 epochs. We plot the F1 and accuracy of different pre-training
model in Figure 5. We can see that with the pre-training process, the pre-
training model could be consistently improved regardless of its architecture.
Therefore, scaling is a sure-fire approach for better model quality in ComQA.
Nonetheless, when we have pre-trained sufficient number of steps, the
performance of the model is saturated. In fact, we find the best results were
obtained after nearly 1.2 million pre-training steps, which takes only 25% of
the pre-training data.

Figure 6. Ablation over the pre-training objectives. The result is based on
HGNN${}_{\text{base}}$. Figure 7. The F1 of the models with different number
of fine-tuning ComQA data. The x-axis is the proportion(number) of the fine
tuning ComQA data.

Next, we investigate the pre-training tasks proposed in Section 4.4. We have
already shown in Table 2 that our model could obtain better performance when
pre-trained with the additional QS and NS. We conduct the ablation study on
the three pre-training objectives for HGNN${}_{\text{base}}$. The result is
shown in Figure 6.

We can see that the model could achieve a better result in terms of both F1
and accuracy with QS and NS. In the MLM objective, the input is always the
corrupted sentence containing the special <MASK> token, which is not the case
during fine-tuning. This discrepancy between pre-training and fine-tuning may
hurt the model (Yang et al., 2019). On the contrary, our proposed question
selection and node selection pre-training tasks are in accordance with the
ComQA, where the QS aims at learning the relevance between the question and
the document while the NS aims at learning the dependency of a node to a
document. In fact, when pre-trained with the NS, our model could be directly
applied to ComQA without any new parameters, which results in a faster
convergence rate. Figure 7 shows the performance of the model with the
different number of ComQA training data. We can see that the model pre-trained
with QS and NS could achieve very good result even with moderate six thousands
of labeled data, which excels the full-trained QA-Net. Therefore, devising
appropriate pre-training tasks could potentially improve the generalization
ability of the model.

###  5.6. The Effect of Connection Type

In section 4.2.1, we introduce three types of the graph connection, i.e. the
intra-sentence, inter-sentence, and global connection. As the graph structure
of the document is a key factor in ComQA, we analyze their specific
importance. Concretely, we build the adjacency matrix based on fused
aggregation in Equation 6, with the combination of specific connections.

$\clubsuit$ | $\heartsuit$ | $\spadesuit$ | Precision | Recall | F1 | Accuracy
---|---|---|---|---|---|---
$\surd$ | $\surd$ | $\surd$ | 76.6 | 78.1 | 77.3 | 43.8
$\surd$ | $\times$ | $\times$ | -2.4 | -2.2 | -2.3 | -5.6
$\times$ | $\surd$ | $\times$ | -0.6 | -0.7 | -0.6 | -0.8
$\times$ | $\times$ | $\surd$ | -1.1 | -1.8 | -1.5 | -3.3
$\surd$ | $\surd$ | $\times$ | -0.5 | -0.8 | -0.6 | -0.9
$\surd$ | $\times$ | $\surd$ | -1.3 | -1.9 | -1.6 | -3.5
$\times$ | $\surd$ | $\surd$ | -0.3 | -0.4 | -0.3 | -0.6
$\times$ | $\times$ | $\times$ | -3.1 | -2.7 | -3.0 | -5.9
Table 4. Ablation results of the different coonection types of
HGNN${}_{\text{base}}$ by fused operation. $\clubsuit$ denotes the intra-
sentence connection, $\heartsuit$ denotes the inter-sentence connection and
$\spadesuit$ denotes the global connection. $\surd$ means the connection is
kept in Equation 6. The last raw with no connection reduced to the
BERT${}_{\text{base}}$ model.

The result of the test set is shown in Table 4. We can see from the Table that
all three types of the connection are important to ComQA, however, the inter-
sentence connection is the most important one: removing $A^{\text{inter}}$
will result in more than one point drop. On the other hand, the intra-sentence
connection is less useful for the ComQA. We conjecture that the basic sentence
representations have already been built from the BERT based sequential
encoder, adding more intra-sentence interaction may not benefit a lot for the
task. On the contrary, the inter-sentence connection and global connection
introduce the specific inductive bias of the document structure to the model
(Battaglia et al., 2018), which helps achieve good performance on ComQA. The
result also suggests that incorporating the sentence level information is very
useful for document understanding.

###  5.7. Error Analysis

Finally, we can see from Table 2 there are still gaps between our model and
human performance, to better understand the remaining challenges, we randomly
sample 100 incorrectly predicted samples of the HGNN${}_{\text{base}}$ model
from the test set, based on the error type, we classify them into 4 classes:

1) Redundancy(41%), we find the most common mistake our model has made is the
redundancy. That is, our model is prone to select the uninformative sentences.
Especially, our model sometimes selects the sentence at the beginning of the
document which repeats the question. However, it is redundant from the
perspective of QA.

2) Missed Sentence(30%), we find our model also prone to miss some important
sentences. For the case where the document processing is not very well, i.e.,
the sentences are not perfectly segmented, some short but useful sentences are
missed.

3) Answerability(24%), another type of error is answerability. Although some
extracted answers seem to be right, however, the answer itself is wrong, such
as the counterfactual answers or too subjective answers. Resolving this type
of error requires background knowledge, such as commonsense.

4) Others(5%). The rest of the errors are due to various reasons such as
ambiguous questions, incorrect labels, and so on.

##  6\. Conclusion

In this paper, we study the compositional question answering where the answer
is composed of discontiguous segments in the document. We present a large
scale Chinese ComQA dataset containing more than 120k human-labeled questions.
The data construction process has undergone rigid inspections to ensure high
quality. To solve the ComQA problem, we propose a hierarchical graph neural
networks that incorporate document graph structure to the model. We also
devise two novel tasks, i.e., question selection and node selection, to pre-
train the model. The proposed methods achieve significant improvement over
previous methods. We also conduct several ablation studies to demonstrate the
superiority of the proposed pre-training tasks and the graph structure.
However, there is still a large gap between our model with human performance,
suggesting that there is still room for improvement in ComQA.

##  7\. Acknowledgments

We thank the anonymous reviewers for their insightful comments. We also
appreciate the dedicated annotation efforts contributed by 马琳、李潇如、张智程, among
others.

##  Appendix A Appendix

The annotation interface is shown in Figure 8. And the templates we used to
determine weather a title of user query is a valid question is shown in Table
5.

Figure 8. A snapshot of the annotation interface. Each row is a single node
that could be served as the final answer component. The question is the page
title in the top. Note that the image or table could also be selected.

为什么 (why),怎么回事 (what happened),什么情况 (what is the matter),啥情况 (what is the
matter),咋回事 (what is wrong),原因 (reason),原理 (principle),由来 (origin),来由
(reason),会怎 (how will it be),为啥 (why),为何 (why),怎么还 (why still),怎么不 (why
not),为甚 (why),为什 (why),看法 (opinion),评价 (evaluation),推荐 (recommendation),分享
(share),评测 (evaluate),排行 (rankings),排名 (ranking),对比 (compare),对待 (treat),区别
(distinguish),差异 (divergence),差别 (difference),不同 (different),好吗 (okay ？),好不好
(it is okay ？),有用吗 (is it useful ？),哪个好 (which is bettter ？),哪家好 (which one is
better ？),比较好 (better),谁好 (who is good ？),谁厉害 (who is better ？),价值 (value),意义
(meaning),作用 (effect),用处 (use),功效 (function),危害 (harm),禁忌 (taboo),好处
(advantage),坏处 (disadvantage),优点 (advantage),缺点 (disadvantage),特点 (feature),特征
(characteristic),影响 (influence),哪些 (which),怎么样的 (how about it ？),哪 (where),还是
(still),怎么 (how),如何 (how about),怎样 (how),方法 (method),步骤 (step),操作
(operation),方案 (plan),办法 (method),教程 (course),方式 (way),玩法 (way of playing),攻略
(strategy),设置 (set up),自制 (homemade),做法 (action),过程 (process),流程 (process),规划
(planning),技巧 (skill),手续 (procedure),办理 (handle),规定 (regulation),要求
(demand),事项 (iitem),范围 (range),用什么 (by what),是谁 (who),谁是 (who is),谁最 (who is
the best),什么 (what),多长 (how long),多少 (how many),多大 (how old),多重 (how heavy),多久
(how long),多远 (how far),多小 (how small),多块 (multiple blocks),多高 (how high),条件
(condition),介绍 (introduction),简介 (introduction),概况 (overview),简要 (brief),简明
(concise),意思 (meanning),标准 (standard),指标 (index),现状是 (the present situation
is),什么叫 (what is called),何为 (what is),何谓 (what is),解释 (explanation),含义
(meaning),是否 (whether),能否 (can),可否 (can),是不是 (yes or no ?),会不会 (is not it
？),能不能 (can or not ？),有没有 (have or not),可不可 (can or not),吗 (is it ？),么
(what),哪 (where),几 (how many),有多 (how much)

Table 5. The templates we used to determine whether a title is a question when
constructing the ComQA. There are 122 templates in total and the derived
questions have more than 90% accuracy.

## References

  * (1)
  * Ba et al. (2016) Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016\.  Layer Normalization.  _ArXiv_ abs/1607.06450 (2016).
  * Baradaran et al. (2020) Razieh Baradaran, Razieh Ghiasi, and Hossein Amirkhani. 2020\.  A survey on machine reading comprehension systems.  _arXiv preprint arXiv:2001.01582_ (2020).
  * Battaglia et al. (2018) Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. 2018\.  Relational inductive biases, deep learning, and graph networks.  _arXiv preprint arXiv:1806.01261_ (2018).
  * Chiu and Nichols (2016) Jason PC Chiu and Eric Nichols. 2016.  Named entity recognition with bidirectional LSTM-CNNs.  _Transactions of the Association for Computational Linguistics_ 4 (2016), 357–370.
  * Cui et al. (2005) Hang Cui, Renxu Sun, Keya Li, Min-Yen Kan, and Tat-Seng Chua. 2005.  Question answering passage retrieval using dependency relations. In _Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval_. ACM, 400–407.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ (2018).
  * Dhingra et al. (2017) Bhuwan Dhingra, Kathryn Mazaitis, and William W. Cohen. 2017\.  Quasar: Datasets for Question Answering by Search and Reading.  _CoRR_ abs/1707.03904 (2017).
  * Dua et al. (2019) Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. 2019\.  DROP: A Reading Comprehension Benchmark Requiring Discrete Reasoning Over Paragraphs. In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_. 2368–2378.
  * Dunn et al. (2017) Matthew Dunn, Levent Sagun, Mike Higgins, Ugur Guney, Volkan Cirik, and Kyunghyun Cho. 2017\.  Searchqa: A new q&a dataset augmented with context from a search engine.  _arXiv preprint arXiv:1704.05179_ (2017).
  * Green Jr et al. (1961) Bert F Green Jr, Alice K Wolf, Carol Chomsky, and Kenneth Laughery. 1961.  Baseball: an automatic question-answerer. In _Papers presented at the May 9-11, 1961, western joint IRE-AIEE-ACM computer conference_. ACM, 219–224.
  * Greenwood (2005) Mark Andrew Greenwood. 2005\.  _Open-domain question answering_.  Ph.D. Dissertation. University of Sheffield, UK.
  * Hamilton et al. (2017) William L Hamilton, Rex Ying, and Jure Leskovec. 2017\.  Representation learning on graphs: Methods and applications.  _arXiv preprint arXiv:1709.05584_ (2017).
  * Harabagiu et al. (2003) Sanda M Harabagiu, Steven J Maiorano, and Marius A Pasca. 2003\.  Open-domain textual question answering techniques.  _Natural Language Engineering_ 9, 3 (2003), 231\.
  * Hastie et al. (2009) Trevor Hastie, Robert Tibshirani, and Jerome Friedman. 2009\.  _The elements of statistical learning: data mining, inference, and prediction_.  Springer Science & Business Media.
  * Hendrycks and Gimpel (2016) Dan Hendrycks and Kevin Gimpel. 2016.  Gaussian error linear units (gelus).  _arXiv preprint arXiv:1606.08415_ (2016).
  * Hermann et al. (2015) Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. 2015.  Teaching machines to read and comprehend. In _NIPS_. 1684–1692.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ 9, 8 (1997), 1735–1780.
  * Huang et al. (2018) Hsin-Yuan Huang, Chenguang Zhu, Yelong Shen, and Weizhu Chen. 2018\.  FusionNet: Fusing via Fully-aware Attention with Application to Machine Comprehension. In _International Conference on Learning Representations_.
  * Ji et al. (2019) Tao Ji, Yuanbin Wu, and Man Lan. 2019.  Graph-based dependency parsing with graph neural networks. In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_. 2475–2485.
  * Khashabi et al. (2018) Daniel Khashabi, Snigdha Chaturvedi, Michael Roth, Shyam Upadhyay, and Dan Roth. 2018\.  Looking beyond the surface: A challenge set for reading comprehension over multiple sentences. In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_. 252–262.
  * Kingma and Ba (2014) Diederik P. Kingma and Jimmy Ba. 2014.  Adam: A Method for Stochastic Optimization.  _ICLR_ (2014).
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ (2016).
  * Kudo and Richardson (2018) Taku Kudo and John Richardson. 2018.  SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing.  _arXiv preprint arXiv:1808.06226_ (2018).
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. 2019\.  Natural questions: a benchmark for question answering research.  _Transactions of the Association for Computational Linguistics_ 7 (2019), 453–466.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ (2019).
  * Loshchilov and Hutter (2018) Ilya Loshchilov and Frank Hutter. 2018.  Decoupled Weight Decay Regularization. In _International Conference on Learning Representations_.
  * Nguyen et al. (2016) Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016.  MS MARCO: A Human Generated MAchine Reading COmprehension Dataset.  _arXiv preprint arXiv:1611.09268_ (2016).
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  PyTorch: An imperative style, high-performance deep learning library. In _Advances in Neural Information Processing Systems_. 8024–8035.
  * Phillips (1960) Anthony Valiant Phillips. 1960\.  Artificial Intelligence Project—RLE and MIT Computation Center Memo 16—A Question-Answering Routine’.  (1960).
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019\.  Language models are unsupervised multitask learners.  _OpenAI Blog_ 1, 8 (2019), 9.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  SQuAD: 100,000+ Questions for Machine Comprehension of Text. In _EMNLP_.
  * Richardson et al. (2013) Matthew Richardson, Christopher JC Burges, and Erin Renshaw. 2013.  MCTest: A Challenge Dataset for the Open-Domain Machine Comprehension of Text.. In _EMNLP_ , Vol. 1. 2.
  * Roberts et al. (2020) Adam Roberts, Colin Raffel, and Noam Shazeer. 2020\.  How Much Knowledge Can You Pack Into the Parameters of a Language Model?  _arXiv preprint arXiv:2002.08910_ (2020).
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016\.  Neural Machine Translation of Rare Words with Subword Units. In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. 1715–1725.
  * Seo et al. (2016) Min Joon Seo, Aniruddha Kembhavi, Ali Farhadi, and Hannaneh Hajishirzi. 2016.  Bidirectional Attention Flow for Machine Comprehension.  _CoRR_ abs/1611.01603 (2016).
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: a simple way to prevent neural networks from overfitting.  _The journal of machine learning research_ 15, 1 (2014), 1929–1958.
  * Swayamdipta et al. (2020) Swabha Swayamdipta, Roy Schwartz, Nicholas Lourie, Yizhong Wang, Hannaneh Hajishirzi, Noah A Smith, and Yejin Choi. 2020.  Dataset Cartography: Mapping and Diagnosing Datasets with Training Dynamics.  _arXiv preprint arXiv:2009.10795_ (2020).
  * Tian et al. (2020) Zhixing Tian, Yuanzhe Zhang, Xinwei Feng, Wenbin Jiang, Yajuan Lyu, Kang Liu, and Jun Zhao. 2020.  Capturing Sentence Relations for Answer Sentence Selection with Multi-Perspective Graph Encoding.. In _AAAI_. 9032–9039.
  * Trischler et al. (2016) Adam Trischler, Tong Wang, Xingdi Yuan, Justin Harris, Alessandro Sordoni, Philip Bachman, and Kaheer Suleman. 2016.  NewsQA: A Machine Comprehension Dataset.  _arXiv preprint arXiv:1611.09830_ (2016).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need. In _Advances in neural information processing systems_. 5998–6008.
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018.  Graph Attention Networks. In _International Conference on Learning Representations_.
  * Verberne et al. (2009) Suzan Verberne, H van Halteren, Stephan Raaijmakers, DL Theijssen, and LWJ Boves. 2009\.  Learning to Rank QA Data: Evaluating Machine Learning Techniques for Ranking Answers to Why-Questions.  (2009).
  * Ward Jr (1963) Joe H Ward Jr. 1963\.  Hierarchical grouping to optimize an objective function.  _Journal of the American statistical association_ 58, 301 (1963), 236–244.
  * Welbl et al. (2018) Johannes Welbl, Pontus Stenetorp, and Sebastian Riedel. 2018\.  Constructing datasets for multi-hop reading comprehension across documents.  _Transactions of the Association for Computational Linguistics_ 6 (2018), 287–302.
  * Yang et al. (2020) Junjie Yang, Zhuosheng Zhang, and Hai Zhao. 2020.  Multi-span Style Extraction for Generative Reading Comprehension.  _arXiv preprint arXiv:2009.07382_ (2020).
  * Yang et al. (2019) Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. 2019\.  Xlnet: Generalized autoregressive pretraining for language understanding. In _Advances in neural information processing systems_. 5754–5764.
  * Yang et al. (2018) Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. 2018\.  HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering. In _EMNLP_.
  * Yao et al. (2019) Liang Yao, Chengsheng Mao, and Yuan Luo. 2019.  Graph convolutional networks for text classification. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 33. 7370–7377.
  * Yogish et al. (2017) Deepa Yogish, TN Manjunath, and Ravindra S Hegadi. 2017\.  Survey on trends and methods of an intelligent answering system. In _2017 International Conference on Electrical, Electronics, Communication, Computer, and Optimization Techniques (ICEECCOT)_. IEEE, 346–353.
  * Yu et al. (2018) Adams Wei Yu, David Dohan, Minh-Thang Luong, Rui Zhao, Kai Chen, Mohammad Norouzi, and Quoc V Le. 2018.  QANet: Combining Local Convolution with Global Self-Attention for Reading Comprehension. In _International Conference on Learning Representations_.
  * Zaheer et al. (2020) Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. 2020\.  Big bird: Transformers for longer sequences.  _arXiv preprint arXiv:2007.14062_ (2020).
  * Zeng et al. (2020) Chengchang Zeng, Shaobo Li, Qin Li, Jie Hu, and Jianjun Hu. 2020.  A survey on machine reading comprehension: Tasks, evaluation metrics, and benchmark datasets.  _arXiv preprint arXiv:2006.11880_ (2020).
  * Zhang et al. (2018) Yuhao Zhang, Peng Qi, and Christopher D Manning. 2018\.  Graph Convolution over Pruned Dependency Trees Improves Relation Extraction. In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_. 2205–2215.
  * Zhang et al. (2020) Zhuosheng Zhang, Yiqing Zhang, Hai Zhao, Xi Zhou, and Xiang Zhou. 2020.  Composing Answer from Multi-spans for Reading Comprehension.  _arXiv preprint arXiv:2009.06141_ (2020).


11institutetext: Electrical Engineering Faculty, Częstochowa University of
Technology,
Częstochowa, Poland
11email<EMAIL_ADDRESS>
# Randomized Neural Networks for Forecasting Time Series with Multiple
Seasonality††thanks: Supported by Grant 2017/27/B/ST6/01804 from the National
Science Centre, Poland.

Grzegorz Dudek  0000-0002-2285-0327

###### Abstract

This work contributes to the development of neural forecasting models with
novel randomization-based learning methods. These methods improve the fitting
abilities of the neural model, in comparison to the standard method, by
generating network parameters in accordance with the data and target function
features. A pattern-based representation of time series makes the proposed
approach useful for forecasting time series with multiple seasonality. In the
simulation study, we evaluate the performance of the proposed models and find
that they can compete in terms of forecasting accuracy with fully-trained
networks. Extremely fast and easy training, simple architecture, ease of
implementation, high accuracy as well as dealing with nonstationarity and
multiple seasonality in time series make the proposed model very attractive
for a wide range of complex time series forecasting problems.

###### Keywords:

Multiple seasonality Pattern representation of time series Randomized neural
networks Short-term load forecasting Time series forecasting.

##  1 Introduction

Time series (TS) expressing different phenomena and processes may include
multiple seasonal cycles of different lengths. They can be observed in demand
variations for various goods, weather conditions, customer numbers, stock
market indicators or results of experimental research. Multiple seasonality in
TS as well as nonstationarity, nonlinear trend and random fluctuations place
high demands on forecasting models. The model should be flexible enough to
capture these features without imposing too much computational burden. Over
the years, many sophisticated forecasting models for TS with multiple
seasonality have been proposed including statistical and machine learning (ML)
ones.

One of the most commonly employed classical approaches, the autoregressive
moving average model (ARMA), can be extended to multiple seasonal cycles by
including additional seasonal factors [1]. Another popular statistical model,
Holt–Winters exponential smoothing (ETS), was developed for forecasting TS
data that exhibits both a trend and a seasonal variation. ETS was extended to
incorporate a second and a third seasonal component in [2]. Both these models,
ARMA and seasonal Holt–Winters model, have a significant weakness. They
require the same cyclical behavior for each period. In [3], to cope with
changing seasonal patterns, innovations state space models for ETS were
proposed. The limitation of the model is that it can only be used for double
seasonality where one seasonal length is a multiple of the other. A further
extension of ETS was proposed in [4]. To deal with multiple seasonal periods,
high-frequency, non-integer seasonality, and dual-calendar effects, it
combines an ETS state space model with Fourier terms, a Box-Cox transformation
and ARMA error correction.

As an alternative to statistical models, ML models have the ability to learn
relationships between predictors and forecasted variables from historical
data. One of the most popular in the well-stocked arsenal of ML methods are
neural networks (NNs). A huge number of forecasting models based on different
NN architectures have been proposed [5]. They deal with multiple seasonality
differently, depending on the specific architectural features and the
creativity of the authors. For example, the model that won the renowned M4
Makridakis competition combines ETS and recurrent NN (RNN) [6]. In this
approach, ETS produces two seasonal components for TS deseasonalization and
adaptive normalization during on-the-fly preprocessing, while RNN, i.e. long
short term memory (LSTM), predicts the preprocessed TS.

Another example of using LSTM for forecasting TS with multiple seasonal
patterns was proposed recently in [7]. To deal with multiple seasonal cycles,
the model initially deseasonalizes TS using different strategies including
Fourier transformation. RNNs, such as LSTM, gated recurrent units, and DeepAR
[8], dominate today as NN architectures for TS forecasting thanks to their
powerful ability to process sequential data and capture long-term
dependencies. But other deep architectures are also useful for forecasting
multiple seasonal TS. For example, N-Beats [9] was designed specifically for
TS with multiple seasonality. It is distinguished by a specific architecture
including backward and forward residual links and a very deep stack of fully-
connected layers.

The above presented approaches to forecasting TS with multiple seasonal
periods rely on incorporating into the model mechanisms which allow it to deal
with seasonal components. This complicates the model and makes it difficult to
train and optimize. An alternative approach is to simplify the forecasting
problem by TS decomposition or preprocessing. In [10], TS with three seasonal
cycles was represented by patterns expressing unified shapes of the basic
cycle. This preprocessing simplified the relationship between TS elements,
making decomposition unnecessary and removing the need to build a complex
model. Instead, simple shallow NNs can be used [10] or nonparametric
regression models [11]. Experimental research has confirmed that these models
can compete in terms of accuracy with state-of-the-art deep learning models,
like the winning M4 submission [12].

In this study, we use a pattern representation of TS to simplify the
forecasting problem with multiple seasonality and propose randomization-based
shallow NNs to solve it. Randomized learning was proposed as an alternative to
gradient-based learning as the latter is known to be time-consuming, sensitive
to the initial parameter values and unable to cope with the local minima of
the loss function. In randomized learning, the parameters of the hidden nodes
are selected randomly and stay fixed. Only the output weights are learned.
This makes the optimization problem convex and allows us to solve it without
tedious gradient descent backpropagation, but using a standard linear least-
squares method instead [13]. This leads to a very fast training. The main
problem in randomized learning is how to select the random parameters to
ensure the high performance of the NN [14], [15]. In this study, to generate
the random parameters we use three methods recently proposed in [16], [17].
These methods distribute the activation functions (sigmoids) of hidden nodes
randomly in the input space and adjust their weights (or a weight interval) to
the target function (TF) complexity using different approaches.

The main goal of this study is to show that randomization-based NNs can
compete in terms of forecasting accuracy with fully-trained NNs. The
contribution of this study can be summarized as follows:

  1. 1.

A new forecasting model for TS with multiple seasonality based on randomized
NNs is proposed. To deal with multiple seasonality and nonstationarity, the
model applies pattern representation of TS in order to simplify the
relationship between input and output data.

  2. 2.

Three randomization-based methods are used to generate the NN hidden node
parameters. They introduce steep fragments of sigmoids in the input space,
which improves modeling of highly nonlinear TFs. A randomized approach leads
to extremely fast and easy training, simple NN architecture and ease of
implementation.

  3. 3.

Numerical experiments on several real-world datasets demonstrate the
efficiency of the proposed randomization-based models when compared to fully-
trained NNs.

The remainder of this work is structured as follows. Section 2 presents the
proposed forecasting model based on randomized NNs, and a TS representation
using patterns of seasonal cycles and three methods of generating NN
parameters are described. The performance of the proposed approach is
evaluated in Section 3. Finally, Section 4 concludes the work.

##  2 Forecasting model

The proposed forecasting model is shown in Fig. 1. It is composed of encoder
and decoder modules and a randomized feedforward NN (FNN). The model
architecture, its specific features, and components are described below.

Figure 1: Block diagram of the proposed forecasting model.

###  2.1 Encoder

The task of the encoder is to convert an original TS into unified input and
output patterns of its seasonal cycles. To create input patterns, the TS
expressing multiple seasonality, $\\{E_{k}\\}_{k=1}^{K}$, is divided into
seasonal sequences of the shortest length. Let these sequences be expressed by
vectors $\mathbf{e}_{i}=[E_{i,1},E_{i,2},…,E_{i,n}]^{T}$, where $n$ is the
seasonal sequence length and $i=1,2,...,K/n$ is the sequence number. These
sequences are encoded in input patterns
$\mathbf{x}_{i}=[x_{i,1},x_{i,2},…,x_{i,n}]^{T}$ as follows:

$\mathbf{x}_{i}=\frac{\mathbf{e}_{i}-\overline{{e}}_{i}}{\widetilde{e}_{i}}$
(1)

where $\overline{{e}}_{i}$ is a mean value of sequence $\mathbf{e}_{i}$, and
$\widetilde{e}_{i}=\sqrt{\sum_{t=1}^{n}(E_{i,t}-\overline{{e}}_{i})^{2}}$ is a
measure of sequence $\mathbf{e}_{i}$ dispersion.

Note that the x-patterns are normalized versions of centered vectors
$\mathbf{e}_{i}$. All x-patterns, representing successive seasonal sequences,
have zero mean, the same variance and the same unity length. However, they
differ in shape. Thus, the original seasonal sequences, which have a different
mean value and dispersion, are unified. This is shown in Fig. 2 on the example
of the hourly electricity demand TS expressing three seasonalities: daily,
weekly, and yearly. Note that the x-patterns representing the daily cycles are
all normalized and differ only in shape.

The output patterns $\mathbf{y}_{i}=[y_{i,1},y_{i,2},…,y_{i,n}]^{T}$ represent
the forecasted sequences
$\mathbf{e}_{i+\tau}=[E_{i+\tau,1},E_{i+\tau,2},…,E_{i+\tau,n}]^{T}$, where
$\tau\geq 1$ is a forecast horizon. The y-patterns are determined as follows:

$\mathbf{y}_{i}=\frac{\mathbf{e}_{i+\tau}-\overline{{e}}_{i}}{\widetilde{{e}}_{i}}$
(2)

where $\overline{{e}}_{i}$ and $\widetilde{e}_{i}$ are the same as in (1).

Note that in (2), for the $i$-th output pattern, we use the same coding
variables $\overline{{e}}_{i}$ and $\widetilde{e}_{i}$ as for the $i$-th input
pattern. This is because the coding variables for the forecasted sequence,
$\overline{{e}}_{i+\tau}$ and $\widetilde{e}_{i+\tau}$, are unknown for the
future period. Using the coding variables determined from the previous period
has consequences which are demonstrated in Fig. 2. Note that y-patterns in
this figure reveal the weekly seasonality. The y-patterns of Mondays are much
higher than the patterns of other days of the week because the Monday
sequences are coded with the means of Sunday sequences which are much lower
than the means of Monday sequences. For similar reasons, y-patterns for
Saturdays and Sundays are lower than y-patterns for the other days of the
week. Thus, the y-patterns are not unified globally but are unified in groups
composed of the same days of the week. For this reason, we construct
forecasting models that learn from data representing the same days of the
week. For example, when we train the model to forecast the daily sequence for
Monday, the training set for it,
$\Phi=\\{(\mathbf{x}_{i},\mathbf{y}_{i})\\}_{i=1}^{N}$, is composed of the
y-patterns representing all Mondays from history and corresponding x-patterns
representing the previous days (depending on the forecast horizon; Sundays for
$\tau=1$).

Figure 2: Real hourly electricity demand TS and its x- and y-patterns.

###  2.2 Decoder

The decoder converts a forecasted output pattern into a TS seasonal cycle. The
output pattern predicted by randomized FNN is decoded using the coding
variables of the input query pattern, $\mathbf{x}$, using transformed equation
(2):

$\widehat{\mathbf{e}}=\widehat{\mathbf{y}}\widetilde{{e}}+\overline{{e}}$ (3)

where $\widehat{\mathbf{e}}$ is the forecasted seasonal sequence,
$\widehat{\mathbf{y}}$ is the forecasted output pattern, $\widetilde{e}$ and
$\overline{e}$ are the coding variables determined from the TS sequence
encoded in query pattern $\mathbf{x}$.

###  2.3 Randomized FNN

The randomized FNN is composed of $n$ inputs, one hidden layer with $m$
nonlinear nodes, and $n$ outputs. Logistic sigmoid activation functions are
employed for hidden nodes. The training set is
$\Phi=\left\\{(\mathbf{x}_{i},\mathbf{y}_{i})\right\\}_{i=1}^{N},\mathbf{x}_{i},\mathbf{y}_{i}\in\mathbb{R}^{n}$.
The randomized learning algorithm consists of three steps [18].

  1. 1.

Randomly generate hidden node parameters, i.e. weights
$\mathbf{a}_{j}=[a_{j,1},a_{j,2},\ldots,\\\ a_{j,n}]^{T}$ and biases
$b_{j},j=1,2,\ldots,m$, according to any continuous sampling distribution.

  2. 2.

Calculate the hidden layer output matrix:

$\mathbf{H}=\left[\begin{array}[]{c}\mathbf{h}(\mathbf{x}_{1})\\\ \vdots\\\
\mathbf{h}(\mathbf{x}_{N})\end{array}\right]$ (4)

where
$\mathbf{h}(\mathbf{x})=\left[h_{1}(\mathbf{x}),h_{2}(\mathbf{x}),\ldots,h_{m}(\mathbf{x})\right]$
is a nonlinear feature mapping from $n$-dimensional input space to
$m$-dimensional feature space, and $h_{j}(\mathbf{x})$ is an activation
function of the $j$-th node (a sigmoid in our case).

  3. 3.

Calculate the output weights:

$\boldsymbol{\beta}=\mathbf{H}^{+}\mathbf{Y}$ (5)

where $\boldsymbol{\beta}\in\mathbb{R}^{m\times n}$ is a matrix of output
weights, $\mathbf{Y}\in\mathbb{R}^{N\times n}$ is a matrix of target output
patterns, and $\mathbf{H}^{+}\in\mathbb{R}^{m\times N}$ is the Moore-Penrose
generalized inverse of matrix $\mathbf{H}$.

Typically, the hidden node weights and biases are i.i.d random variables both
generated from the same symmetrical interval $a_{j,i},b_{j}\sim U(-u,u)$. It
was pointed out in [18] and [16] that as the weights and biases have different
functions they should be selected separately. The weights decide about the
sigmoid slopes and should reflect the TF complexity, while the biases decide
about the sigmoid shift and should ensure the placement of the most nonlinear
sigmoid fragments, i.e. the fragments around the sigmoid inflection points,
into the input hypercube. These fragments, unlike saturation fragments, are
most useful for modeling TF fluctuations.

Recently, to improve the performance of randomized FNNs, several new methods
of generating the hidden node parameters have been proposed. Among them is the
random $a$ method (R$a$M) which was proposed in [16]. In the first step, this
method randomly selects weights from the interval whose bounds $u$ are
adjusted to the TF complexity, $a_{j,i}\sim U(-u,u)$. Then, to ensure the
introduction of the sigmoid inflection points into the input hypercube, the
biases are calculated from:

$b_{j}=-\mathbf{a}_{j}^{T}\mathbf{x}^{*}_{j}$ (6)

where $\mathbf{x}^{*}_{j}$ is one of the training x-patterns selected for the
$j$-th hidden node at random.

The second method proposed in [16], called the random $\alpha$ method
(R$\alpha$M), instead of generating weights, generates the slope angles of
sigmoids. This changes the distribution of weights, which typically is a
uniform one. This new distribution ensures that the slope angles of sigmoids
are uniformly distributed, and so improves results by preventing overfitting,
especially for highly nonlinear TFs. This method, in the first step, selects
randomly the slope angles of the sigmoids, $\alpha_{j,i}\sim
U(\alpha_{\min},\alpha_{\max})$. Then, the the weights are calculated from:

$a_{j,i}=4\tan\alpha_{j,i}$ (7)

Finally, the biases are determined from (6). To simplify the optimization
process, the lower bound for the angles, $\alpha_{\min}$, can be set as
$0^{\circ}$. In such a case only one parameter decides about the model
flexibility, i.e. $\alpha_{\max}\in(0^{\circ},90^{\circ})$. This is what we
used in our simulation study.

To improve further FNN randomized learning, a data-driven method (DDM) was
proposed in [17]. This method introduces the sigmoids into randomly selected
regions of the input space and adjusts the sigmoid slopes to the TF slopes in
these regions. As a result, the sigmoids mimic the TF locally, and their
linear combination approximates smoothly the entire TF. In the first step, DDM
selects the input space regions by selecting randomly the set of training
points, $\\{\mathbf{x}^{*}_{j}\\}_{j=1}^{m}$. Then, the hyperplanes are fitted
to the TF locally in the neighbourhoods of all points $\mathbf{x}^{*}_{j}$.
The neighborhood of point $\mathbf{x}^{*}_{j}$, $\Psi(\mathbf{x}^{*}_{j})$,
contains this point and its $k$ nearest neighbors in $\Phi$. The weights are
determined based on the hyperplane coefficients from:

$a_{j,i}=4a_{j,i}^{\prime}$ (8)

where $a_{j,i}^{\prime}$ are the coefficients of the hyperplane fitted to
neighbourhood $\Psi(\mathbf{x}^{*}_{j})$.

The hidden node biases are calculated from (6).

Note that the biases in the above-described approaches are determined based on
the weights selected first and the data points. Unlike in the standard
approach, they are not chosen randomly from the same interval as the weights.
Randomized FNN has two hyperparameters to adjust: number of hidden nodes $m$,
and the smoothing parameter, i.e. $u$, $\alpha_{\max}$ or $k$, depending on
the method of generating parameters chosen. These hyperparameters decide about
the fitting performance of the model and its bias-variance tradeoff. Their
optimal values should be selected by cross-validation for a given forecasting
problem.

##  3 Simulation Study

In this section, we apply the proposed randomization-based neural models to
forecasting hourly TS with three seasonalities: yearly, weekly and daily.
These TS express electricity demand for four European countries: Poland (PL),
Great Britain (GB), France (FR) and Germany (DE). We use real-world data
collected from www.entsoe.eu. The data period covers the 4 years from 2012 to
2015. Atypical days such as public holidays were excluded from these data
(between 10 and 20 days a year). The forecast horizon $\tau$ is one day, i.e.
24 hours. We forecast the daily load profile for each day of 2015. For each
forecasted day, a new training set is created and a new randomized model is
optimized and trained. The results presented below are averaged over 100
independent training sessions.

The hyperparameters of randomized FNNs were selected using grid search and
5-fold cross-validation. The number of hidden nodes was selected from the set
$\\{5,10,...,50\\}$. The bounds for weights in R$a$M were selected from
$\\{0.02,0.04,...,\\\ 0.2,0.4,...,1\\}$. The $\alpha_{\max}$ in R$\alpha$M was
selected from
$\\{2^{\circ},4^{\circ},...,40^{\circ},45^{\circ},...,90^{\circ}\\}$. The
number of nearest neighbors in DDM was selected from $\\{25,27,...,69\\}$.

For comparison, we applied a multilayer perceptron (MLP) for the same
forecasting problems. MLP was composed of a single hidden layer with $m$
sigmoid nodes whose number was selected using 5-fold cross-validation from the
set $\\{2,4,...,24\\}$. MLP was trained using Levenberg-Marquardt
backpropagation with early stopping to avoid overtraining (20% of training
samples were used as validation samples).

Forecasting quality metrics for the test data are presented in Table 1. They
include: mean absolute percentage error ($\operatorname{\textsc{mape}}$),
median of $\operatorname{\textsc{ape}}$, root mean square error
($\operatorname{\textsc{rmse}}$), mean percentage error
($\operatorname{\textsc{mpe}}$), and standard deviation of percentage error
($\operatorname{\textsc{pe}}$) as a measure of the forecast dispersion.

Table 1: Forecasting results. |  | R$a$M | R$\alpha$M | DDM | MLP
---|---|---|---|---|---
PL data | $\operatorname{\textsc{mape}}$ | 1.32 | 1.32 | 1.35 | 1.37
| Median($\operatorname{\textsc{ape}}$) | 0.93 | 0.94 | 0.94 | 0.96
| $\operatorname{\textsc{rmse}}$ | 358.86 | 364.13 | 380.77 | 374.86
| $\operatorname{\textsc{mpe}}$ | 0.40 | 0.39 | 0.39 | 0.26
| Std($\operatorname{\textsc{pe}}$) | 1.94 | 1.98 | 2.09 | 2.07
GB data | $\operatorname{\textsc{mape}}$ | 2.61 | 2.62 | 2.80 | 2.93
| Median($\operatorname{\textsc{ape}}$) | 1.88 | 1.90 | 1.99 | 2.17
| $\operatorname{\textsc{rmse}}$ | 1187.60 | 1184.58 | 1382.97 | 1314.78
| $\operatorname{\textsc{mpe}}$ | -0.61 | -0.61 | -0.58 | -0.60
| Std($\operatorname{\textsc{pe}}$) | 3.57 | 3.56 | 4.16 | 3.99
FR data | $\operatorname{\textsc{mape}}$ | 1.67 | 1.69 | 1.81 | 1.87
| Median($\operatorname{\textsc{ape}}$) | 1.15 | 1.16 | 1.25 | 1.31
| $\operatorname{\textsc{rmse}}$ | 1422.60 | 1433.90 | 1530.15 | 1565.70
| $\operatorname{\textsc{mpe}}$ | -0.42 | -0.39 | -0.45 | -0.39
| Std($\operatorname{\textsc{pe}}$) | 2.60 | 2.61 | 2.78 | 2.85
DE data | $\operatorname{\textsc{mape}}$ | 1.38 | 1.39 | 1.43 | 1.58
| Median($\operatorname{\textsc{ape}}$) | 0.96 | 0.98 | 0.99 | 1.09
| $\operatorname{\textsc{rmse}}$ | 1281.14 | 1242.36 | 1333.79 | 1452.54
| $\operatorname{\textsc{mpe}}$ | 0.14 | 0.14 | 0.10 | 0.04
| Std($\operatorname{\textsc{pe}}$) | 2.22 | 2.13 | 2.34 | 2.50

More detailed results, i.e. distributions of $\operatorname{\textsc{ape}}$,
are shown in Fig. 3. Based on $\operatorname{\textsc{ape}}$, we performed a
Wilcoxon signed-rank test with $\alpha=0.05$ to indicate the most accurate
models. Fig. 4 depicts pairwise comparisons of the models. The arrow lying at
the intersection of the two models indicates which of them gave the
significantly lower error. A lack of an arrow means that both models gave
statistically indistinguishable errors.

Figure 3: Boxplots of $\operatorname{\textsc{ape}}$. Figure 4: Results of the
Wilcoxon signed-rank test for $\operatorname{\textsc{ape}}$.

As can be seen from Table 1 and Fig. 4, the randomization-based FNNs gave
significantly lower errors than fully-trained MLP for each dataset. According
to the Wilcoxon test, R$a$M outperformed the other approaches.

$\operatorname{\textsc{mpe}}$ shown in Table 1 allows us to asses the bias of
the forecasts produced by different models. A positive value of
$\operatorname{\textsc{mpe}}$ indicates underprediction, while a negative
value indicates overprediction. As can be seen from Table 1, for PL and DE
data the bias was positive, whilst for GB and FR data it was negative. The
forecasts produced by MLP for PL and DE were less biased than the forecast
produced by randomized FNNs.

Fig. 5 presents examples of forecasts of the daily load profiles produced by
the examined models. Note that the proposed models generate multi-output
response, maintaining the relationships between the output variables
(y-pattern components). In the case of single-output models, these
relationships are ignored because the variables are predicted independently.
This may cause a lack of smoothness in the forecasted curve (zigzag effect;
see for example [19]).

Figure 5: Examples of forecasts (shaded regions are 5th and 95th percentiles,
measured over 100 trials).

Fig. 6 shows the optimal numbers of hidden nodes selected in the cross-
validation procedure. Obviously, the number of hidden nodes is dependent on TF
complexity. The forecasting problem for PL required the greatest number of
nodes for randomized FNNs, around 30, regardless of the learning method. MLP
for PL needed many fewer nodes, 12 on average. Other forecasting problems were
solved by randomized FNNs with fewer hidden nodes, from 20 to 30 on average.
For these problems, the difference in the number of nodes between MLP and
randomized FNNs was not as large as for PL data. The relatively small number
of hidden nodes in randomized FNNs (note that randomized learning usually
requires hundreds or even thousands of nodes) results from TS representation
by unified patterns and the decomposition of the forecasting problem (a
separate model for each forecasting task, i.e. every day in 2015, trained on
the selected patterns).

The optimal values of smoothing parameters for the randomized learning methods
are depicted in Fig. 7. As can be seen from this figure, the optimal value of
the bound for weights in R$a$M varies from 0.2 for FR to 0.7 for GB on
average, which correspond to sigmoid slope angles from around $3^{\circ}$ to
$10^{\circ}$ (see [16]). The optimal value of the bound for slope angle in
R$\alpha$M varies from $12^{\circ}$ for FR to $32^{\circ}$ for DE on average.
Note also the high value of $k$ in DDM (from $49$ for PL to $65$ for FR on
average) in relation to the number of training points, which ranged from 150
to 200. Thus, for our forecasting problems we can expect flat TFs without
fluctuations. Such TFs can be modeled using R$a$M. Its competitors, R$\alpha$M
and DDM, reveal their strengths in modeling highly nonlinear TFs with
fluctuations (see [16], [17]).

Figure 6: Boxplots of the optimal number of hidden nodes.

Figure 7: Boxplots of the optimal smoothing parameters.

##  4 Conclusion

Forecasting TS with multiple seasonality is a challenging problem, which we
propose to solve with randomized FNNs. Unlike fully-trained FNNs, randomized
FNNs learn extremely fast and are easy to implement. The simulation study
showed that their forecasting accuracy is comparable to the accuracy of fully-
trained NNs. To deal with nonstationary TS with multiple seasonal periods, the
proposed approach employs a pattern representation of the TS. This
representation simplifies the relationship between input and output data and
makes the problem easier to solve using simple regression models.

The effectiveness of the randomized FNNs in modeling nonlinear target
functions was achieved due to the application of new methods of generating
hidden node parameters. These methods, using different approaches, introduce
the steepest fragments of sigmoids, which are most useful for modeling TF
fluctuations, into the input hypercube and adjust their slopes to TF
complexity. This makes the model more flexible, more data-dependent, and more
dependent on the complexity of the solved forecasting problem.

In a future study, we plan to introduce an attention mechanism into our
randomization-based forecasting models to select training data and develop an
ensemble approach for these models.

## References

  * [1] Box, G.E.P., Jenkins, G.M. and Reinsel, G.C.: Time series analysis: Forecasting and control. 3rd ed., Prentice Hall, New Jersey, 1994.
  * [2] Taylor, J.W.: Triple seasonal methods for short-term load forecasting. European Journal of Operational Research 204, 139–152 (2010)
  * [3] Gould, P.G., Koehler, A.B., Ord, J.K., Snyder, R.D., Hyndman, R.J. and Vahid-Araghi, F.: Forecasting time-series with multiple seasonal patterns. European Journal of Operational Research 191, 207–222 (2008)
  * [4] De Livera, A.M., Hyndman, R.J. and Snyder, R.D.: Forecasting time series with complex seasonal patterns using exponential smoothing. Journal of the American Statistical Association 106(496), 1513–1527 (2011)
  * [5] Benidis, K., Rangapuram, S.S., Flunkert, V., Wang, B., Maddix, D., Turkmen, C., Gasthaus, J., Bohlke-Schneider, M., Salinas, D., Stella, L., Callot L. and Januschowski, T.: Neural forecasting: Introduction and literature overview. arXiv:2004.10240 (2020)
  * [6] Smyl, S.: A hybrid method of exponential smoothing and recurrent neural networks for time series forecasting. International Journal of Forecasting 36(1), 75–85 (2020)
  * [7] Bandara, K., Bergmeir C. and Hewamalage, H.: LSTM-MSNet: Leveraging forecasts on sets of related time series with multiple seasonal patterns. IEEE Transactions on Neural Networks and Learning Systems 32(4), 1586–1599 (2021)
  * [8] Salinas, D., Flunkert, V., Gasthaus, J. and Januschowski, J.: DeepAR: Probabilistic forecasting with autoregressive recurrent networks. International Journal of Forecasting 36(3), 1181–1191 (2020)
  * [9] Oreshkin, B.N., Carpov, D., Chapados, N. and Bengio, Y.: N-BEATS: Neural basis expansion analysis for interpretable time series forecasting. 8th International Conference on Learning Representations, ICLR, (2020).
  * [10] Dudek, G.: Neural networks for pattern-based short-term load forecasting: A comparative study. Neurocomputing 205, 64–74 (2016)
  * [11] Dudek, G.: Pattern similarity-based methods for short-term load forecasting – Part 1: Principles. Applied Soft Computing 37, 277–287 (2015).
  * [12] Dudek, G., Pełka, P. and Smyl, S.: A hybrid residual dilated LSTM and exponential smoothing model for mid-term electric load forecasting. IEEE Transactions on Neural Networks and Learning Systems, doi: 10.1109/TNNLS.2020.3046629
  * [13] Principe, J., Chen, B.: Universal approximation with convex optimization: Gimmick or reality? IEEE Computational Intelligence Magazine 10(2), 68–77 (2015)
  * [14] Cao, W., Wang, X., Ming, Z., Gao, J.: A review on neural networks with random weights. Neurocomputing 275, 278–287 (2018)
  * [15] Zhang, L., Suganthan, P.: A survey of randomized algorithms for training neural networks. Information Sciences 364–365, 146–155 (2016)
  * [16] Dudek, G.: Generating random parameters in feedforward neural networks with random hidden nodes: Drawbacks of the standard method and how to improve it. In: Neural Information Processing. ICONIP 2020. CCIS, vol. 1333, pp. 598–606, Springer, Cham (2020).
  * [17] Dudek, G.:Data-driven randomized learning of feedforward neural networks, 2020 International Joint Conference on Neural Networks (IJCNN), Glasgow, United Kingdom, pp. 1–8 (2020).
  * [18] Dudek, G.: Generating random weights and biases in feedforward neural networks with random hidden nodes. Information Sciences, 481, 33–56 (2019)
  * [19] Dudek G.: Multivariate regression tree for pattern-based forecasting time series with multiple seasonal cycles. In: Information Systems Architecture and Technology: Proc. 38th International Conference on Information Systems Architecture and Technology – ISAT 2017. AISC, vol. 655. pp. 85–94, Springer, Cham (2018).