%-------------Approach, Design, Implementation
% These can be split into separate sections, or in the case of the 10 step approach, can be discussed for each of the steps.
% Explaining what was accomplished, including functionality; approach, tools, methodology, conceptual background, and deliverables
\chapter{Approach and Design}

\section{Problem Formulation}
Focusing on news web sites, we investigate the possibility of estimating web page content change and web site structure change through reinforcement deep learning under a partially observed information history.
We take web archive history as the source of historical data and use the information to predict future changes, which can be used by a web crawling scheduler to make better crawl plans.
Under the traditional supervised learning setting, the model will try to predict the state of web content based on the archived historical information: whether a significant change will happen at a particular time.
Under the reinforcement learning setting, the model itself will simulate a web crawler and try to make optimal crawling plans given the history of the web content.



\subsection{Types of Web Page Content Change}
There are different types of web page content change: the publisher changes the web page content; the web page can be changed through user interaction; and the web page changes based on the browsing user profile.
In our project, we mainly focus on the type where the publisher changes the page.

\subsection{Web Site Structure Change}
We consider the web site structure in a tree representation.
Each page represents one node on the tree; the home page is the root node. We consider two types of web page structure change: disappearing node, which means a particular page is removed from the web site; and new node, which means a new page is added to the web site. 

\subsection{Information Observability}
 Radinsky's work \cite{radinsky_predicting_2013} introduces two different observability scenarios for the web page histories:
 (1) in a fully-observed scenario, all the history of a web page that will be used as information source is available; and (2) in a partially-observed scenario, only a partial history of the web pages is available.
 In reality, the partially-observed scenario is a typical case.
 For the type of web page change that is driven by a publisher, we can determine the observability for a page or website through its crawling policy, which means if the policy maker can guarantee the accuracy of the policy based on domain knowledge. 

In our project, we investigate both observability scenarios.
As a fully-observed scenario has been confirmed to be valid on this task, we explore the possibility of using partially-observed histories to achieve the same goal.

\begin{figure}
    \hspace*{-2cm}
    \centering
    \includegraphics[scale=0.6]{figures/CS6604_Project.png}
    \caption{Different settings of data sources and training/testing design}
    \label{fig:data_sources}
\end{figure}

\section{History Records and Ground Truth}
The main goal of the project is to discover the possibility of using historical web archive information to predict the future behavior of the web page content, including web pages and web site structures.
We plan to gather the web archive collection from Archive.org as part of our historical records.
We then set up a frequently enough crawling for the same set of archival records, which can be seen as the ground truth for the web content behavior over time. The historical records will be used as our training dataset for the model and the ground truth will be used to test the performance of our model.

\section{Traditional Supervised Learning}
Our goal is to predict web content change using the crawled time series data. 
Using this data, we will predict the future changes to web content by re-framing the problem as a classification and a regression task.

 We will form a series of inputs and corresponding labels for the classification problem using SVM and Random Forest. 
 We will also use Facebook Prophet to forecast the future value using the input time series data.
 Prophet is a procedure for forecasting time series data based on an additive model where non-linear trends are fit with yearly, weekly, and daily seasonality.
 It is robust to missing data and shifts in the trends, and typically handles outliers well.
 We will cover a detailed description of data processing needed for the tasks and their implementations in later sections.
 

\section{Reinforcement Learning}
The nature of our goal, predicting web content change, can be generally considered as a time series prediction problem, which is a good fit with a supervised machine learning problem.
However, usually, reinforcement learning is not a good option to perform prediction tasks with time series data. 
So, why would we want to apply reinforcement learning to such a problem? 
To answer this question, we need to go back to our original motivation: create a better crawling scheduler. 
The prediction part is derived out of the original goal and it can be generally considered as the fundamental part, that can help to make the crawler smarter. 
Instead of focusing on the prediction task, reinforcement learning can directly model the crawling scheduler to achieve the original goal: we are going to train the agent to be capable of making optimal crawling plans in our defined environment. 
In this case, the prediction problem can be considered as a hidden task for the reinforcement learning model to be considered, and the model would use this information to make optimal decisions.
We will discuss two different crawling strategies for the reinforcement learning in section 4.4.


\section{Experiment Design}

We follow the steps shown below:
\begin{enumerate}
\item Set up a crawler for the news website with a frequent policy which can guarantee the collection of a fully-observed history.
\item Collect the same news website data from the Internet Archive with a longer history.
\item Validate the observability of archived data.
\item Identify the unique copies of web pages for each URL in the web archive through predefined criteria.
\item Generate the unique site structure for each web site as a time series.
\item Implement baseline methods for web page content change prediction and web site structure change prediction.
\item Design a reinforcement-learning model for web page content change prediction and web site structure change prediction.
\item Compare the reinforcement-learning and baseline models.
\end{enumerate}


\chapter{Implementation}
\section{Data Collection}
For this research, our data source comes from Archive.org and our own crawling jobs.
We aim to include the following major news websites in our experiment: CNN, Dailymail, NYT, FOX, and ABC.
In the following parts, we will talk about the web archive data standards, tools that we used for crawling, description of our desired data, and data pre-processing.
 
\subsection{Web Archive Storage Standards}
 WARC is the standard file format used by web archives for long-term preservation.
 WARC is a container format to serialize HTTP transactional metadata and payloads.
 The full WARC standard information can be found at:
 \url{https://iipc.github.io/warc-specifications/specifications/warc-format/warc-1.0/}.
 We get WARC data from multiple sources, including Archive.org and the Web2Warc crawler.
 As WARC is primarily designed for long-term preservation purposes rather than efficiency in computational processing, we will explain in a later section how we convert WARC to the Parquet format for our research and analysis purposes.
 
 CDX is the common file format that is used by the web archive community as a separate index information source for WARC.
 A CDX file consists of individual lines of text, each of which summarizes a single web record in WARC.
 There are many parts of the CDX standard that include different types of information.
 A full CDX data specification can be found at: 
 \url{https://archive.org/web/researcher/cdx_legend.php}.
 In this project, we do not use CDX files as our information source.
 Instead, we integrate the same index information in the Parquet format to have an aggregated information source to perform analysis tasks.
 
\subsection{Archive.org Collection} 
Archive.org is the website where Internet Archive hosts most of its web archive collections.
In this project, we include the following collections:
\begin{enumerate}
    \item https://archive.org/details/cnn.com
    \item https://archive.org/details/dailymail.co.uk
    \item https://archive.org/details/nytimes.com
    \item https://archive.org/details/foxnews.com
    \item https://archive.org/details/abcnews.go.com
\end{enumerate}

In Archive.org, each collection contains multiple items that represent multiple types of crawled data.
In each item, the data is preserved in multiple WARC/CDX files and related information.
Each WARC file is typically around 1 GB in size.
We implement ArchiveOrgCollectionScraper, a web scraping tool to fetch all the downloadable links for WARC and CDX files in the collection. We then use the Wget tool in Linux to download all of the files.
As a result, we have a collection of Archive.org CNN focus crawls from May 2019 to Oct 2019.
We haven't collected from all of the other news web archive collections due to storage space limitations.
This is planned to be resolved in future research.

Note: Be aware that all the above collections are not public, but we are granted permission to access the data by the Internet Archive, our partner in the NSF-funded collaborative research project GETAR. 

\subsection{Alternative Way to Get Data from Internet Archive}
Many collections on Archive.org are not public.
Even without explicit permission from the Internet Archive, researchers can use ArchiveSpark to crawl the Wayback Machine to get desired data since most of the records accessible through the Wayback Machine are public.
ArchiveSpark allows use of a specified URL or domain list for fetching the records from the Wayback Machine within a defined period.
An example usage can be found through ArchiveSpark's documentation at: 

\url{https://github.com/helgeho/ArchiveSpark/blob/master/notebooks/Downloading_WARC_from_Wayback.ipynb}


\subsection{Frequent Recent Crawls}
As an addition to the collection from Archive.org, we build our own frequent crawled collection as the ground truth for our study.
Web2Warc is a simple crawler written in Scala which can generate WARC and CDX output.
We use a modified Web2Warc version for our frequent crawl tasks in this project.
For each news web site, we set up a repeating task to crawl two levels of the domain starting from the landing page.
The periodicity of our crawl is 1 hour.
As a result, we have collected data for all 5 news web site from November 6th to December 1st. 

At the beginning, we intended to keep our crawling results consistent with the collections we get from the Internet Archive.
In this case, Heritrix is the best choice.
Heritrix is the Internet Archive's open-source web crawler that is used for IA's regular crawling task.
However, we did not get Heritrix working correctly for our purposes.
We think this should be further studied in the future since Heritrix has capability, with flexibility and multiple functions, to perform crawls with complex rules.

\subsection{Convert WARC to Parquet}
The existing tools for WARC manipulation are limited and not flexible.
Thus, we convert WARC files to Parquet files for further experiments.
Apache Parquet is a columnar storage format that is designed for efficient processing and storage.
We choose Parquet for its:
\begin{enumerate}
    \item columnar representation with intuitive index schema;
    \item efficient searching and filtering process over index columns;
    \item ease of manipulation with most programming languages; and
    \item strong support in the Apache Spark framework for big data processing.
\end{enumerate}

We use a modified version of the Archive Unleashed Tool Kit to convert all WARC data under an Apache Spark environment.
Table \ref{tab:schema} shows the schema of converted Parquet data.

\begin{table}
\centering
\begin{tabular}{|l|l|}
\hline
Field & Example \\ \hline
SURT                    & com,tranews,0227525099-1)/                          \\ \hline 
Timestamp               & 20180520120731                                      \\ \hline
OriginalUrl             & http://0227525099-1.tranews.com/                    \\ \hline
MIME                    & text/html                                           \\ \hline
HTTP Response code      & 200                                                 \\ \hline
WARC Payload Digest     & AOHD7VS5...FO4ABM7WGE                    \\ \hline
Redirect Url            & -                                                   \\ \hline
Meta                    & -                                                   \\ \hline
Compressed Size         & 295                                                 \\ \hline
Offset in the WARC file & 14647                                               \\ \hline
WARC filename           & CC-MAIN...00245.warc.gz \\ \hline
Payload                 & HTML Header + HTML content                          \\ \hline
\end{tabular}
\bigskip
\caption{A sample web archive record in Parquet. SURT means Sort-friendly URI Reordering Transform.}
\label{tab:schema}
\end{table}


\section{Find Unique Web Page Copies in the Archive}
We aim to track the changes individual web pages undergo over time.
To accomplish this we will establish differences in the HTML body plaintext (i.e., the actual file that is sent to the browser), changes in CSS classes used in the plaintext, and changes in HTML tree structure.
For syntactic similarity, we use the methodology proposed by \cite{styleTreeSim}.
Using these three metrics together, we can train a machine learning algorithm to tell us which web pages are more likely to change so that we can focus on crawling them rather than those that generally remain static.
Additionally, seeing where changes most often occur can give us a visualization of which pages, and where in those pages, edits most often occur.

A change in only plaintext might tell us that the title of a segment has changed, or the content of the segment has changed, or new content has been added, for example.
A change in CSS shows style changes, such as different fonts, colors, or formatting used, but may not necessarily signal a content change.
Lastly, a change in HTML tree structure could be an indicator of either of the above changes.
If new content is added or old content is deleted, the tree would change.
Similarly, if a CSS class that is used changes, at least the tree node names would change correspondingly.
The reason we choose these three metrics, rather than just one, is that a web page can change in a variety of ways.
There are some web pages where the HTML body never changes, but the JavaScript or Flash script that governs the dynamic parts of it does.
Or, take for example a page whose HTML body and scripts only change based on input from the backend of a website, like a realtime stock observer.
Finding changes in all three of the aforementioned areas helps eliminate the possibility of us missing or overstating web page changes.
\begin{figure}[!ht]
    \centering
  \includegraphics[width=0.5\textwidth]{figures/DOM.PNG}
  \caption{Web page viewed as a DOM tree \cite{EditTreeDist}}
  \label{fig:dom}
\end{figure}

\subsection{HTML Tree Similarity}
The Document Object Model (DOM), illustrated in Figure 
\ref{fig:dom}, specifies a web document as a labeled ordered tree of DOM elements, and as such we can apply existing tree based algorithms.
One of the interesting algorithms for this context is Tree Edit Distance which can be used to compute the structural similarity between DOM trees.
Zhang
and Shasha’s \cite{EditTreeDist} algorithm for labeled rooted trees is used as it is simple, yet complete.
In the algorithm proposed by Zhang and Shasha:

\begin{figure}[!ht]
    \centering
  \includegraphics[width=0.5\textwidth]{figures/DOM2.PNG}
  \caption{A sample DOM tree with post order
numbering for DOM elements \cite{EditTreeDist}}
  \label{fig:dom2}
\end{figure}

\begin{itemize}

    \item The elements in the DOM tree are indexed in post order as shown in Figure \ref{fig:dom2} \cite{EditTreeDist}.
    
    \item  Dynamic programming is used to efficiently compute the edit distance starting with the root nodes of two DOM trees.
    
    \item DOM trees can be manipulated by three operations: update, remove, and insert -- as described respectively in Figure \ref{fig:domOps}.
\end{itemize}

\begin{figure}
   
  \includegraphics[width=1\textwidth]{figures/treeOps.png}
  \caption{Various operations on DOM \cite{EditTreeDist}}
  \label{fig:domOps}
\end{figure}

Let $\gamma_{update}$, $\gamma_{remove}$, and $\gamma_{update}$ denote the costs associated with the update, remove, and update operations, respectively, and let $\gamma_{max}$ be the maximum of all these three.
Zhang and Shasha \cite{EditTreeDist} propose that the structural
similarity of two DOM trees, T1 and T2, is determined by:

\begin{equation}
    similarity = 1 - \frac{treedistance(T_1, T_2)}{\gamma_{max}(|T_1| + |T_2|)}
\end{equation}

\subsection{Webpage Style Similarity}
The style of the webpages present in Cascading Style Sheets
is also critical information to determine the similarity of
web pages.
There are two ways to represent style for HTML documents: CSS classes and inline styles.
We limit the scope of determining changes on the basis of CSS classes only.
Let A and B be two web pages, and $S_A$ and $S_B$ represent the set of CSS classes in A and B, respectively.
Jaccard similarity can be used to compute stylistic differences between the two.

\begin{equation}
\begin{split}
    S_A = classes(A) \\
    S_B = classes(B)\\
    style-similarity = \frac{| A \cap B |}{|A| + |B| - |A \cap B|}
    \end{split}
\end{equation}

\subsection{Webpage Body Content Similarity}
To determine text similarity we first extract the plaintext from a web page using Beautiful Soup.
We extract the text from all tags in the HTML code except for the script, head, title, style, and meta tags.
Beautiful Soup then strips the HTML tags from the content within the remaining tags and gives us all the text that is visible on the webpage.

Once we have the plaintext from the two web pages to be compared, we first filter out the stopwords from the extracted texts and then perform lexical similarity checks to calculate the similarity between the text content of the web pages.
We remove the stopwords to get a better representation of the similarity, since having the stopwords in the text will lead to an unnecessarily large number of words in the intersection set of the two texts and result in a higher similarity value.
We perform lexical similarity checks instead of semantic similarity because we need to check if there is any difference in the actual text content of the web pages rather than the meanings of the content, and lexical similarity analysis provides a better measure for this.

Jaccard similarity is one method to perform lexical text similarity analysis.
In simple terms, Jaccard similarity is the ratio of the \textit{Intersection} and the \textit{Union} of the two texts.

\begin{equation}
    Jaccard \, Similarity = \frac{| Text_A \cap Text_B |}{| Text_A \cup Text_B |}
\end{equation}

Another similarity measure is the \textit{Cosine Similarity}.
It essentially measures the cosine of the angle between the vectors generated by the two texts.
The vectors are generated based on the counts of the word tokens in each of the texts.
Two similarly oriented vectors will yield a cosine similarity of 1, while two vectors that are oriented at 90 degrees will yield a cosine similarity of 0.

\begin{equation}
    Cosine \, Similarity = \frac {Text_A \cdot Text_B}{||Text_A|| \cdot ||Text_B||}
\end{equation}

\textit{Edit Distance} is used to get a numerical measure of the differences between two texts by counting the minimum number of operations (additions, substitutions, and deletions) that have to be performed to transform one string to another.

\textit{Sorensen-Dice} similarity  is another similarity measure that can be used to measure text similarity.

\begin{equation}
    Sorensen-Dice \, Similarity = \frac{2 \cdot| Text_A \cap Text_B |}{| Text_A | + | Text_B |}
\end{equation}

\subsection{Model Web Content Change Baselines}

We had to pre-process the data from the Parquet files into a suitable format that could be provided as an input to the machine learning models.
The dataset we created contained the crawled payloads for a particular web page along with the timestamps of when the crawls occurred.
We will discuss this process in detail in section \ref{supBaselines}.

For our tests, we focused specifically on modelling and predicting the change trends on the \textit{cnn.com} homepage.
This was because our model needed to predict the change trends on a specific web page at a particular time.
Further, it was reasonable to assume that the homepage of the new website \textit{cnn.com} would be the most frequently changing page.
We believed that this would be the best web page to try out our approach on, and thus decided to work on just the \textit{cnn.com} homepage.


\section{Model Site Map Change in the Archive}

Along with detecting page-level changes, we want our model to learn to identify regions within the structure of the site, which are prone to changes, and to target them first.
We also want to make predictions if the crawler should crawl the whole website, signifying that there is a significant change in the site.
To do that, we want to use a sitemap. A website is a combination of several web pages under a single domain, and the sitemap characterizes the site. 

\subsection{Site Map: Tree Structure} 
We aim to construct this framework in terms of a tree structure that will represent the site.
The root will represent the homepage, and the nodes will represent the pages of that site.
In essence, from the URLs we have in the archive, we will reconstruct, to the best of our ability, the tree structure of the actual web site.
Unfortunately, it is possible that we will leave many pages out, since the web crawler only crawls into the web site to a certain depth, but we expect to at least map most of the higher level pages.

In order to aid the page level comparison, we are also planning to create a timeline type structure in each node.
Each node will contain the page data of that node in a chronological order, i.e., the first timestamp will represent the first time that page was crawled, and the last timestamp will show the latest.
This will help us to compare and visualize the sitemap in different time ranges as well as what parts of a website change the most or least frequently.
Figure \ref{fig:graphStructure} shows a sample graph structure of such a sitemap. 

\begin{figure}[!ht]
    \centering
  \includegraphics[width=0.57\textwidth]{figures/sitemap.png}
  \caption{Sample Sitemap in Graph Structure}
  \label{fig:graphStructure}
\end{figure}

Changes in site structure could tell us where pages are being added or deleted, for example, giving valuable information on which areas of a web site are receiving the most modification.
In a news website, for instance, we would expect to find that the folders or nodes designated for editorials and articles change the most frequently, as new content is added every day, and old content is moved to an archive.
It would tell us nothing about how individual pages are changing; rather, it would afford us a `big picture' view of the changes the site undergoes.

\subsection{Generating Sitemap} 
Assembling the sitemap will require processing archive data and parsing every URL crawled, creating a new tree for each new domain.
We find and assign children to nodes based on their placement in the URL structure.
For example, in a URL such as www.google.com/drive we will first create a tree for the \textit{google.com} domain, assign the root node as \textit{google.com}, and then create a child node of the root named \textit{drive}.
If next we come across www.google.com/mail, we will add another child node to the root \textit{google.com} node named \textit{mail}.
To perform this step, working with the archive data requires some more filtering.
We only need the media type data among the data crawled; we also check  for status-code, it should be `200.' 
After filtering data, we will work towards building the sitemap.
A `URL' consists of hostname, path, and query.
To construct the sitemap, we require the use of hostname and path; the former will act as the root node, and the path will be used to build up nodes of the hostname.
We will also be requiring timestamp and payload, as the node is expected to be updated with the latest payload and timestamp.
Payloads, saved chronologically, will be used by page-level prediction.
The timestamp and payload received from the archive data are not in the format to be handled and used by the model.
It requires some filtering, to be rendered usable by the model.
Payload data saved in archive data consists of the HTTP response and page HTML data.
We need to extract that HTML data from the payload and save/use it at the respective node in a tree structure. 
This process needs to be repeated for each URL, and once done, the site map will be created.
There will arise a situation where multiple crawls will bring different payloads for the same URL but at different times.
In our current implementation, we are saving these payloads mapped with the timestamp.
This implementation will help perform page-level change detection. 

There are additional functionalities that need to be implemented to supplement the sitemap representation.
The first one is a sitemap extractor, which is used to extract a sub-sitemap, which takes time range as input and provides a sitemap for that specific time.
It will be used to build a matrix of a sitemap, which will act as input to a machine learning model.
Next is a compactor, which is used to compare two sitemaps and help evaluate if sitemaps were identical.
The last one is a matrix generator.
These features were created with the idea in mind that when a machine learning model is created, these supplemental functionalities will be used to build additional features.
Some of these features we thought of were:
(1) sitemap (in matrix form) and
(2) site map change binary indicator from last crawled event (either one or zero).
Next, the matrix conversion is described in detail. 

\subsection{Matrix Conversion}
To use this feature of detecting change at the site map level in a machine learning model, we aim to convert a tree structure into a matrix form.
This matrix form will preserve the parent-child relationship of the sitemap and help the model to learn the same.
For this, we are currently exploring the use of the ancestor matrix.
An ancestor matrix is a Boolean matrix, whose cell (i, j) is true if i is an ancestor of j in the tree.
The idea is to traverse the tree in preorder fashion and keep track of ancestors in a container such as a set, a vector, or an array.
Figure \ref{fig:ancestorStructure} represents the sample of a ancestor matrix and its corresponding tree\footnote{Sample taken from geeksforgeeks.org}.

\begin{figure}[!ht]
    \centering
  \includegraphics[width=0.57\textwidth]{figures/ancestorMatrix.png}
  \caption{Sample Ancestor Matrix for a Given Tree Structure}
  \label{fig:ancestorStructure}
\end{figure}

Since we are dealing with time-series data, our approach is to build the sitemap for intervals and feed it to the machine learning model.
The idea behind this is, as time progresses, changes in site structure will happen, and we will capture these changes in the matrix, and the machine learning model will be able to learn those changes and so learn the change pattern. 


\subsection{Predict Site Crawl - Baseline Models}
As stated in previous sections, when data from the WARC file is processed to convert into the format shown in Table \ref{tab:schema}, we require further pre-processing to build a sitemap tree structure.
It involves using Timestamp, OriginalUrl, MIME, and payload from the schema.
It also should be noted that the Parquet file contains data of multiple media types and status codes.
Not all of the data is required to build tree structure; we need only data which has mime type ``text/html'' having status code of ``200.'' 

Once we have pre-processed data, we will focus on transforming this data into training data, which can be used to build a machine learning model to predict future crawls.
We are focusing on two types of machine learning modes, classification and regression.
Two baseline models, ``SVM and Random forest,'' that were discussed before, are used for classification, while Facebook Prophet is used for the regression model.
Classification will be to decide on the crawl. If we have one, then crawl; zero indicates otherwise.
In the case of the regression model, we are looking to predict the percentage change in nodes of a sitemap.
If the expected change is above the threshold, we crawl, otherwise not. 

\subsection{Visualization}
For the benefit of users and researchers alike, the changing sitemaps of websites will be visualized in a number of different ways.

One such visualization will be a graphic, showing the tree structure with a slider on the bottom that will allow users to view the tree at different points in time based on the timestamps assigned to nodes in the constructed tree, as described above.
This visualization will enable users to see how a site has changed over time.
New branches and nodes could even be highlighted when selecting two different time stamps to see what has changed between them.

Another visualization which is a bit more complicated than the first, but that also provides information in a more interesting way, is known as a treemap.
A treemap is a collection of nested rectangles, with each rectangle representing a branch of the tree.
Using this data structure, we could adjust the colors of branches to indicate how much the structure of a branch has changed, enabling users to see what areas of the sitemap change the most over time.
This visualization would require a user to select an interval of time for the algorithm to compare the tree structures.



\section{Model Web Page Content Change with Reinforcement Deep Learning}
In this section, we first illustrate the RL model environment.
Then, we talk about two RL agent action strategies for our crawling scheduling problem.
Next, we discuss the learning policy algorithms.
Our model is implemented through OpenAI's Gym~\cite{1606.01540} and Stable Baselines~\cite{stable-baselines} libraries.

\begin{figure}[!ht]
    \centering
  \includegraphics[width=1\textwidth]{figures/RL_env_1.png}
  \caption{A general view of our proposed reinforcement learning environment for the web crawling task for one time step: At each time step, the agent will learn from the historical observation and perform a predefined crawling action. Then the sliding window will move forward and make a new history observation that includes the previous action.}
  \label{fig:rl_env}
\end{figure}



\subsection{Environment and Observation Space}
Similarly to the supervised learning settings as in the baselines, in the RL environment, we take the web page archival data as a sequence of time-series data.
For web page content change, each data point in the sequence can represent either a unique copy at a certain time or a duplicate copy of a previous unique copy. 
For web site structure change, each data point in the sequence represents a unique copy of the current treemap of the site or a duplicate copy of a previous unique copy. 
For this project, we primarily investigate the potential of the RL model to capture the changing behavior of web content over time. 
In this case, in the time series data sequence, we mark each earliest data point with unique information as 1, the other data points with duplicate information as 0. 


From the environment, we expect the model to capture the recent changing frequency of the web page, and then generate a plan to capture the potential future changes adequately.
Here, we give a length of $L_h$ hours that the agent can observe in the history information before each action. By combining the observed history information and immediate action, we can form a sliding window that covers a continuous space within the data sequence.
After each time step, the sliding window will move forward, creating a new observation space that includes the results from the previous action.
Figure \ref{fig:rl_env} shows a general view of the process. 


% Please add the following required packages to your document preamble:
% \usepackage{graphicx}
\begin{table}[]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{|c|c|c|}
\hline
Result Type           & Continous Predition & Sparse Prediction \\ \hline
Duplicate (Crawl)     & Negative            & Negative          \\ \hline
Valid                 & Positive            & Positive          \\ \hline
Miss                  & Negative            & Negative          \\ \hline
Duplicate (Not Crawl) & Positive            & N/A               \\ \hline
\end{tabular}%
}
\caption{The general rewarding strategies for continuous prediction and sparse prediction models. The result type indicates the compared result between model prediction and ground truth. Negative/positive means we use a negative or positive float value as the reward. Since the sparse prediction model does not generate a ``not crawl'' decision, the reward is not applicable and marked as N/A.}
\label{tab:reward}
\end{table}



\subsection{Agent, Action, and Reward}
Based on the given environment we defined earlier, we can further design the behavior of the RL agent within the environment and corresponding rewards.
We propose two agent strategies for the crawler: continuous prediction and sparse prediction.
In Figure~\ref{fig:rl_m1}, the result type indicates the compared result between model prediction and ground truth.
Negative/positive means we use a negative or positive float value as the reward.

\begin{figure}[!ht]
    \centering
  \includegraphics[width=1\textwidth]{figures/RL_m1.png}
  \caption{The general idea of the continuous prediction model: The agent learns from the observation space and makes the binary prediction (crawl/not crawl) for each time step. After each prediction, the agent moves forward to the next time step until it reaches the max range, where we consider a crawling plan has been generated. The target labels are showing the positions of ground truth in the data sequence. The blue arrows under the timeline are showing the time step that is marked as crawl and the result of comparing with ground truth.}
  \label{fig:rl_m1}
\end{figure}

% Please add the following required packages to your document preamble:
% \usepackage{longtable}
% Note: It may be necessary to compile the document several times to get a multi-page table to line up properly

\subsubsection{Continuous Prediction}
Figure \ref{fig:rl_m1} shows the general concept of a continuous prediction agent.
In this scenario, the agent will give a binary crawling prediction -- crawl or not crawl -- for each time step.
Afterward, we give the agent feedback (reward) after MAX\_STEP time steps, which is called one episode.
In other words, the agent will make a plan for each time step in MAX\_STEP hours.
For our experiment, we set the time step interval by hour, which means the agent will make a prediction each hour. 
For the MAX\_STEP, we use 24 hours (a day) as the rewarding cycle.

\textbf{Reward:} We reward the agent after each time step; then we compare the results of the model with ground truth.
Table \ref{tab:reward} shows the result type and the corresponding reward type. 


\begin{figure}[!ht]
    \centering
  \includegraphics[width=1\textwidth]{figures/RL_m2.png}
  \caption{The general idea of the sparse prediction model: The agent learns from the observation space and predicts with multiple positions for crawling. The target labels are showing the positions of ground truth in the data sequence. The blue arrows under the timeline are showing the time step that is marked as crawl and the compared result with ground truth.}
  \label{fig:rl_m2}
\end{figure}

\subsubsection{Sparse Prediction}
Figure \ref{fig:rl_m1} shows the general concept of the sparse prediction agent.
In this scenario, the agent will: (1) Generate some crawling candidates $N_c$, and (2) for each candidate, generate a time step position as crawling candidate $C_t$ where the $C_t$ can not go over the MAX\_STEP. 
Here, each episode finishes after all $C_t$ has been generated in $N_c$.
In other words, each episode, the agent will make a plan by choosing a set of locations in the prediction time steps within MAX\_STEP.

\textbf{Reward:} We reward the agent after each episode, then we compare the results of the model will with ground truth as in Table \ref{tab:reward}.


\subsubsection{Rewarding Strategy}
Table \ref{tab:reward} shows the general idea of how we give reward to the agent based on the resulting feedback.
The rewarding system is an essential component in the RL model design and can affect the performance significantly. 
In this case, we investigate two different rewarding strategies: (1) fixed score rewarding, and (2) scaled score rewarding.
Table \ref{tab:score} shows the reward settings we used for the experiments.

In fixed score rewarding, we give simple scores like -2 to a duplicate crawl or 15 for a valid crawl. 
In scaled score rewarding, we give a scaled reward for a valid crawl based on the time step distance to actual target: We use the equation $20*(1-D_t/D_{max})$ to get the final score where $D_t$ is the distance from crawl candidate to actual target and $D_{max}$ is the max distance to the target.


\begin{table}[!ht]
\centering
\resizebox{\textwidth}{!}{%
\begin{tabular}{|c|c|c|}
\hline
Result Type           & Fixed Score & Scaled Score       \\ \hline
Duplicate (Crawl)     & -2          & -2                 \\ \hline
Valid                 & 15          & 20*(1-D\_t/D\_max) \\ \hline
Valid (Exact Match)   & 20          & N/A                \\ \hline
Miss                  & -10         & -10                \\ \hline
Duplicate (Not Crawl) & 2           & N/A                \\ \hline
\end{tabular}%
}
\caption{The score implementations for the rewarding strategies.}
\label{tab:score}
\end{table}


\subsection{Learning Policy}
Learning policy is the algorithm that is used to train the reinforcement model. 
In our experiment, we try two different learning policies to train our model: Deep Q Network(DQN) and Proximal Policy Optimization(PPO).
DQN~\cite{Mnih2013PlayingAW} is a Q-learning based method with a deep neural network to estimate parameters in the model.
This method is widely used as one of the fundamental deep reinforcement learning algorithms.
PPO2~\cite{Schulman2017ProximalPO} is a recently developed online policy gradient based RL algorithm. 
We choose these two algorithms to investigate the influence of RL algorithms by comparing the traditional algorithm (DQN) and popular recent algorithm (PPO).
In our implementation, we use the Stable Baselines library to apply the algorithms in our Gym environment.
