%-------------Literature review, coordinated with the references section
\chapter{Literature Review}
\section{Related Works}
Radinsky \cite{radinsky_predicting_2013} introduces a traditional machine-learning-based approach to predicting web page content change.
Two types of information observability scenarios are defined in this paper for the general web page content prediction problem: fully-observed and partially-observed.
This paper focuses on the fully-observed scenario, which means the past histories that will be used for future predictions are all observed, but in our project, we cover both scenarios.
The author designed the approach of predicting web page content change as a classification problem where each candidate page is assessed daily to determine if it should be crawled.
The primary goal of the paper is to determine the effectiveness of a list of predefined features, so the same SVM algorithm is applied for all of the experiments.
Three types of features are introduced as an information source: page changing frequency (1D), various page content (2D), and related pages content (3D).
The result shows that 3D features lead to the best performance on the task, and 2D is better than 1D.
This paper shows that the machine-learning-based approach is promising for this problem.
In our project, we propose to expand this idea to deep learning and combine it with web archive data.  

%break
In \textit{Using Visual Pages Analysis for Optimizing Web Archiving} \cite{Saad:2010:UVP:1754239.1754287}, Saad et al. provide a procedure for determining the interval to crawl a certain pre-specified set of web pages.
Specifically, they intend to provide information to two types of crawlers: a crawler that crawls on a specified interval, and a crawler that crawls the least fresh page as determined by a scheduler.
The approach uses visual analysis and machine learning to break a web page into its component blocks, and then compares between archived versions of the web page to determine if blocks deemed important by the algorithm often change in the page.
If they do, the page is prioritized for crawling, but if not the priority might be lowered on the stack.
The specifics of how this is done includes processing a web page into a format similar to XML and then using XML differentiating software to find the changes and put them into a new XML file containing the deltas.
The purpose of this research is to avoid crawling web pages that do not change or have unimportant changes like advertisements that refresh constantly.
This paper stood out to us because it suggests a method that we could consider in our goal of finding the differences between web pages in order to predict the optimal crawler scheduling.

%break
Gowda and Mattmann \cite{styleTreeSim} consider clustering web pages based on various techniques to group the pages.
They focus on clustering based on the web page structure and style for applications like categorization, cleaning, schema detection, and automatic extraction.
This can be really useful for our task of differentiating web pages on the basis of HTML similarity.
The structural similarity of HTML
pages is measured by using the Tree Edit Distance measure on
DOM trees.
The stylistic similarity is measured by using Jaccard similarity on CSS class names.
An aggregated similarity measure is computed by combining structural and
stylistic measures.
We incorporate the syntactic dissimilarity by computing the tree difference, CSS classes difference, and the aggregate difference to differentiate the web pages.

Meegahapola et al. \cite{serverChange}  propose a methodology to detect the frequency of change in web pages to optimize server-side scheduling of change detection and notification systems.
The proposed method is based on a dynamic detection process, where the crawling schedule will be adjusted accordingly in order to result in a more efficient server-based scheduler to detect changes in web pages. 
% \todo[inline]{More related lit review}

% \todo[inline]{TODO: page/site similarity test lit review}
Law \cite{law2012structural} tries to build an efficient page comparison system by comparing the structural and visual features of the web pages.
The structural comparison is used to find dissimilarities in case different scripts are rendering the same content or if there is a change in hyperlinks.
Visual comparison can find dissimilarities if the code of the web page was unchanged but an image being loaded was updated.
They propose a hybrid web page comparison framework that combines the structural and visual comparison methods.
They additionally propose machine learning that sets all the similarity parameters and combination weights.

Pehlivan and Saad \cite{pehlivan2010vi} address the problem of understanding \textit{what happened between two versions of a web page}.
Most of the web pages on the internet are HTML, but HTML is considered to be semantically poor.
Comparing two versions of HTML web pages based on the DOM tree does not provide relevant information that will help us to understand the changes.
They propose a change detection approach that computes the semantic differences between two versions of a web page by detecting changes in the visual representation of the two versions.
The visual aspect provides an insight into the semantic structure of the document.The proposed approach, \textit{Vi-DIFF}, compares the two versions of a web page in three steps.

1. Segmentation: Partition the web page into visual semantic blocks.

2. Change Detection: Compare the two restructured versions of the web pages.

3. Delta File Generation: Produce a file describing the visual changes.

They also introduce a new change detection algorithm, that is used in step 2, that takes into account the structure of the web page while comparing.

Yang and Song \cite{5662320} propose a new method to extract the text content from web pages to overcome the limitations of the traditional techniques.
Those are successfully able to remove invisible noise like styles, comments, and scripts but they still leave behind a large portion of the visible noise that includes navigation links, sidebars, copyright statements, etc. that lead to lower accuracy of the text extraction algorithm.
In their proposed approach, they remove not just the invisible noise but also the visible noise, to a large extent.
This results in more pure web pages for content extraction.
Then they utilize the relationships between text length, punctuation, and links to extract the web page text.

Taylor and Letham \cite{prophet} address the challenges associated with producing reliable and high quality forecasts from a variety of time series data. They describe a practical approach to forecasting “at scale” that combines configurable models with analyst-in-the-loop performance analysis. They propose a modular regression
model with interpretable parameters that can be intuitively adjusted by analysts
with domain knowledge about the time series.



\section{Traditional Methods and Reinforcement Learning}

A Support Vector Machine (SVM) is a discriminative classifier formally defined by a separating hyperplane.  It is a non-probabilistic binary linear classifier that analyzes data used for classification and regression analysis. SVMs can be used to solve various real-world problems. They are helpful in text and hypertext categorization, as their application can significantly reduce the need for labelled training instances in both the standard inductive and transductive settings. Classification of images can also be performed using SVMs. Experimental results show that SVMs achieve significantly higher search accuracy than traditional query refinement schemes after just three to four rounds of relevance feedback.

\begin{figure}[!ht]
    \centering
  \includegraphics[width=0.5\textwidth]{figures/svm.png}
  \caption{SVM’s soft margin formulation \cite{cristianini_shawe-taylor_2000}}
  \label{fig:svm}
\end{figure}

 The underlying motivation for using SVMs is the ability of their methodology to accurately forecast time series data when the underlying system processes are nonlinear, non-stationary, and not defined a-priori.
 SVMs have also been proven to outperform other non-linear techniques including neural-network based non-linear prediction techniques such as multi-layer perceptrons.

Random forests or random decision forests are an ensemble learning method for classification, regression, and other tasks that operate by constructing a multitude of decision trees at training time and outputting the class that is the mode of the classes (classification) or mean prediction (regression) of the individual trees.
Random decision forests correct for decision trees' habit of overfitting to their training set.
Random forest classifiers create a set of decision trees from a randomly selected subset of the training set. It then aggregates the votes from different decision trees to decide the final class of the test object.

Facebook Prophet uses a decomposable time series model \cite{Harvey1990EstimationPF} with three main model components: trend, seasonality, and holidays. They are combined in the following equation:

\begin{equation}
    y(t) = g(t) + s(t) + h(t) + \epsilon_t	
\end{equation}


Here g(t) is the trend function which models non-periodic changes in the value of the time series, s(t) represents periodic changes (e.g., weekly and yearly seasonality), and h(t) represents the effects of holidays which occur on potentially irregular schedules over one or more days. The error term $\epsilon_{t}$ represents any idiosyncratic changes which are not accommodated by the model. This specification is similar to a generalized additive model (GAM) \cite{Additive}, a class of regression models with potentially non-linear smoothers applied to the regressors. Here only time as a regressor is used. Modelling seasonality as an additive component is the same approach taken by exponential smoothing.


So far, we have covered several methods on how to model web site content change in a traditional supervised machine learning setting: the problem is essentially modeled as a time series prediction problem.
These methods focus on the prediction of when or whether the web would change at a specific time in the future. After that, the prediction results can be used as an indicator to help the crawling scheduler to make plans and actions. 

In this project, instead of traditional supervised learning, we propose to use reinforcement learning to solve the crawling prediction problem. 
Reinforcement learning is widely used in robotics or game AI where the model can learn to make optimal decisions to reach the goal based on given environment.
Traditionally, RL model is not a good approach for time-series forecasting problems since RL model focuses on optimizing future outcomes instead of future events.
Here, we want to convert the traditional time series prediction scenario to an environment that can fit RL model:
Instead of predicting the future changes of web page changes as an intermediate step, we directly look at the crawling decisions as the output of the model.
In this case, the RL model will learn to make crawling decisions based on the time-series web history data (environment).
With this approach, we expect the RL model to handle two important parts of the problem at the same time: predicting the future behavior of web page change (the same problem as in supervised learning model) and making crawling decisions. 
