%-------------Testing/Evaluation/Assessment
\chapter{Evaluation}

\section{Supervised Learning Baselines} \label{supBaselines}

Each Machine Learning algorithm has its nuances that capture a particular perspective of the dataset and the problem statement. 
The quantitative validation of the results of an algorithm need to be done to know how well it performs.
For the baseline models discussed earlier, we calculate the Precision, Recall, F1 score, and Accuracy to evaluate them. In the information retrieval domain, Precision defines how many of the extracted data points are correct, whereas the Recall defines what proportion of correct data points have been extracted from the corpus of all correct. 
The F1 score is the harmonic mean of precision and recall. 

\begin{equation}
    Precision = \frac{\text{True Positives}}{\text{True Positives + False Postitives} }
\end{equation}

\begin{equation}
    Recall = \frac{\text{True Positives}}{\text{True Positives + False Negatives} }
\end{equation}

\begin{equation}
    F1-Score = \frac{2 \cdot Precision\cdot Recall}{Precision + Recall}
\end{equation}

\begin{equation}
    Accuracy = \frac{TP + TN}{TP + TN + FP + FN}
\end{equation}
where, TP = True Positives, TN = True Negatives, FP = False Positives, and FN = False Negatives.

The project is a step towards an intelligent crawling scheduler for archiving news websites. 
Both True Positives and False Positives are important to evaluate as on the one hand, we do not want to miss important updates to the web content but also do not want to unnecessarily crawl the page. 
Thus, both Accuracy and F1 Score as evaluation metrics make sense in our case.

\subsection{Web Content Change}
\begin{figure}
    \hspace*{-2cm}
    \centering
    \includegraphics[scale=0.5]{figures/basicPipeline.png}
    \caption{High Level Overview of Supervised Learning architecture}
    \label{fig:pipleline}
\end{figure}
\subsubsection{Data Pre-processing}
For extracting the data from the Parquet files, we initially tried loading the Parquet files into a Pandas dataframe.
But, the Pandas dataframe loaded the entire Parquet file in the memory and provided the results.
This took a heavy toll on the system memory, so the process was killed after processing just 5-7 Parquet files, even on a system with 32GB RAM.

As we were focusing only on the \textit{cnn.com} homepage, we tried an alternative approach using PySpark and loaded the data into a PySark SQL dataframe.
Then we queried for just the first row from all of the Parquet files, one by one.
Since the crawls were scheduled for the \textit{cnn.com} website for up to 2 levels, we were sure that the homepage would always be the first row in the Parquet files.

Once we had the first row from a Parquet file, we got the \textit{Payload} and \textit{filename} fields to create our dataset.
We had to use the \textit{filename} field to get the timestamp, as the \textit{timestamp} field itself was in \textit{YYYYMMDD} format.
We needed a granularity of up to hours, minutes, and seconds to get a better idea of the crawl schedules.
The \textit{filename} field contained the actual time of the crawl up to the second, and so we decided to get the actual timestamp from the filename instead.
Then we sort the entries based on the timestamp so that we have the data in chronological order.

After getting the payload and timestamp information for the \textit{cnn.com} homepage from all the Parquet files, we saved the data into a .pkl file that could be used as needed for training the different baseline models.
In total we had 198 data points ranging from November 6 to 19, 2019.
We used a split of 8:2 for training and testing for the classification task.

\subsubsection{SVM and Random Forests}
While using the baseline SVM and Random Forest models, our aim was to be able to classify whether the web page should be crawled in the next hour or not.
From the stored .pkl file, we first set the first entry as the base web page. We then calculate several metrics for comparing the HTML structure and text content of the subsequent snapshots to the base web page.

We used BeautifulSoup to extract the visible text content for the web pages.
But, the extracted text mainly contained the header and footer text that did not change much during the time period of the dataset.
We then realized that this was because the main body of the web page was being generated by JavaScript and was not captured as part of the <body> tag in the payload.
Upon examining the payload more closely, we found a JSON object with the key \textit{ArticleList} that contained a list of headlines and then observed that the actual headlines displayed on the homepage were actually a subset of the headlines present in this list.
So, we decided to get the \textit{ArticleList} object from within the <script> tag from the payload and run our text similarity measures on this list as well.

The calculated metrics are:
\begin{itemize}
    \item Overall Similarity: Overall structural and style similarity between the current version and the last archived snapshot of the web page.
    \item Style Similarity: The CSS style similarity between the current version and the last archived snapshot of the web page.
    \item Structural Similarity: The HTML tree similarity between the current version and the last archived snapshot of the web page.
    \item Cosine Similarity: The cosine similarity measure between the text extracted by BeautifulSoup for the current version and the last archived snapshot of the web page.
    \item Jaccard Similarity: The jaccard similarity measure between the text extracted by BeautifulSoup for the current version and the last archived snapshot of the web page.
    \item Sorensen Dice Similarity: The sorensen dice similarity measure between the text extracted by BeautifulSoup for the current version and the last archived snapshot of the web page.
    \item Cosine Similarity Article List: The cosine similarity measure between the \textit{ArticleList} for the current version and the last archived snapshot of the web page.
    \item Jaccard Similarity Article List: The jaccard similarity measure between the \textit{ArticleList} for the current version and the last archived snapshot of the web page.
    \item Sorensen Dice Similarity Article List: The sorensen dice similarity measure between the \textit{ArticleList} for the current version and the last archived snapshot of the web page.
\end{itemize}

After calculating and studying these similarity values, we decided to set the thresholds for considering the web page as changed as 0.98 for the overall structural and style similarity, 1 for the cosine similarity for the text extracted by BeautifulSoup, and 0.97 for the cosine similarity of the \textit{ArticleList}.
If any of these values was below the respective thresholds, we set the label for that particular record as 1, signifying a significant change in the web page and set the current snapshot as the new base snapshot.

We used scikit-learn's SVM and Random Forest classifiers to train and test our models.
To train our SVM and Random Forest classifier with the time series data, we used windows of multiple hours.
Within the specified window, we used the time difference from the last archived web page as the training data along with the label of the immediate next snapshot as the label for the time window.
The classifiers were restricted to have just 2-dimensional data as training input, so we could not use all of the measures for each record in the windows as that made the training data 3-dimensional.
So, we just kept windows of time differences from the last archived snapshot as the training data as we felt that it would best capture the time between the changes on the web page.
Upon performing several experiments, we settled on a window size of 5 hours.

\subsubsection{Facebook Prophet}

Prophet restricts the input for the model to be just timestamps and the corresponding labels.
Hence we decided that having the time difference from the last archived snapshot would be a viable continuous label for the dataset, which would become 0 if the current page was considered to be changed.

The steps to create the training data for Prophet were similar to what was described in the previous section.
The process to determine whether the current snapshot is different from the last archived snapshot is exactly the same.
Once the similarity is determined, the timestamp and the time difference in hours is added to the training data.
The time difference is set to 0 in case the web page is considered to be changed, as this value will be considered the label by Prophet, and setting all changed web pages to have label 0 distinguishes them from the unchanged web pages.

Once we have the timestamps and the time differences for all snapshots, we train the Facebook Prophet model.


\begin{table}[]
\centering

\begin{tabular}{|c|c|c|c|c|}
\hline
Model  & Accuracy & Precision & Recall & F1 Score       \\ \hline

Support Vector Machine  & 0.769 & 0.74 & 0.77 & 0.75       \\ \hline

Random Forest  & 0.615 & 0.60 & 0.62 & 0.61       \\ \hline

\end{tabular}%
\caption{Model Evaluation}
\label{tab:baselineModels}
\end{table}
\begin{figure}[!ht]
    \centering
  \includegraphics[width=0.8\textwidth]{figures/prophet2.png}
  \caption{The output of the Facebook Prophet model illustrating the number of hours elapsed since the last determined change on cnn.com based on the crawled data. It also shows predictions for the next 48 hours.}
  \label{fig:pr2}
\end{figure}

\begin{figure}[!ht]
    \centering
  \includegraphics[width=0.8\textwidth]{figures/prophet.png}
  \caption{The output of the Facebook Prophet illustrating an instance in the future when the webpage should be crawled according to the model.}
  \label{fig:pr1}
\end{figure}

\subsubsection{Evaluations}
As illustrated in Table \ref{tab:baselineModels} with an accuracy of 76.9\%, the SVM model outperforms the Random Forest model with better accuracy, precision, and recall. 
This can be explained by the fact that the Random Forests generally don’t fit very well for increasing or decreasing trends, which are usually encountered when dealing with time-series analysis, such as seasonality. A Random Forest is made of Decision Trees (weak classifier) which are a combination of Binary Splits (decision) on training data. 
For any data that a Random Forest has not seen before, at best, it can predict an average of training values that it has seen before. 
If the test set consists of data points that are greater or less than the training data points, a Random Forest will provide us with average results as it is not able to extrapolate and understand the growing/decreasing trend in our data. 

On the other hand, the ability of SVM to solve nonlinear regression estimation problems makes it successful in time series forecasting. 
SVM models have been known to handle higher dimensional data better, even with a relatively low amount of training samples.
They exhibit a very good generalization ability for complex models.

Facebook Prophet has an inbuilt feature that enabled us to plot the forecasts it generated. 
In Figures \ref{fig:pr2} and \ref{fig:pr1}, the blue line in the graph represents the predicted values while the black dots represent the data in our dataset. 
We also show the future predictions for the next 48 hours in the graphs.
Prophet successfully captures the trend from the limited dataset and identified a pattern to generate predictions.
Figure \ref{fig:pr3} illustrates the daily pattern of changes recognised by Facebook Prophet, with time on the X-axis and the corresponding contribution to predicted value on the Y-axis. 
The sum of all the values in the graph is 1.
A negative contribution results in a reduction of time between the last snapshot, thus depicting a change in content.
We notice that, every day between 10 AM to 4 PM, there are relatively more changes to the web content.
These insights are helpful to schedule the crawling efficiently.

\begin{figure}[!ht]
    \centering
  \includegraphics[width=0.8\textwidth]{figures/prophet3.png}
  \caption{Daily trend of the changes recognised by Facebook Prophet}
  \label{fig:pr3}
\end{figure}

\subsection{Sitemap Change}
In this section we will evaluate the performance of the baseline models on the sitemap change prediction.
We use the same concepts described above.
Baseline models (SVM and Random Forest) are used for classification, and Facebook Prophet is used for regression.

\subsubsection{Training Data}
After extracting the data from the Parquet files, we tried a standard approach of using Pandas to load the data set and pre-process it by filtering it based on \textit{`text/Html'} media type and \textit{200} status code.
This approach works fine when you have limited data and limited memory.
In our case, the archive dataset is huge, and memory was low.
We loaded the Parquet file in memory and processing took a heavy toll on the system.
The process was killed after processing just 5-7 Parquet files, even on a system with 32GB RAM.

As our focus was only on the sitemap, we improvised and tried an alternative approach using PySpark.
We loaded data into a PySark SQL data frame and then collected the original URL and timestamp in one go.
We repeated this step for all the Parquet files and generated the dataset in the form of a .pkl file. 

We had to use the \textit{filename} of Parquet files under process to get the timestamp, as the \textit{timestamp} field itself was in \textit{YYYYMMDD} format.
The reason was that data crawling was hourly, and the timestamp was showing the date for the day.
There was no way to distinguish the hourly dataset otherwise.
Then we chronologically sorted the entries based on the timestamp.

The .pkl file that is generated is used to produce training data for baseline models.
Figure \ref{fig:piplelineSitemeap} shows the pipeline used.
In total we had 197 data points, each data point depicting an hourly crawl having features like number of new nodes added and percentage change in nodes. We used a split of 8:2 for training and testing.  

\begin{figure}
    \hspace*{-2cm}
    \centering
    \includegraphics[scale=0.5]{figures/process.png}
    \caption{Sitemap: High Level Overview of Supervised Learning Architecture}
    \label{fig:piplelineSitemeap}
\end{figure}

\subsubsection{SVM and Random Forests}
Using SVM and Random Forests, we are trying to do the classification.
We are predicting whether to crawl the whole website in the next hour or not.
From the stored .pkl file, we will build the site map.
As we will make the sitemap, we will also save the new nodes added in each crawl as a feature.
Another feature that we added is the percentage change from the last checkpoint.
A checkpoint is defined as the time when the new nodes added causes the change to pass a set threshold set, e.g., 0.75.
It signifies the percentage change.
If 0.75 percent of nodes were added, then the whole website should be crawled.
I arrived at 0.75 after looking at the general pattern of the nodes added and predicting the best percentage change that will work.
To build the dataset for classification, we use a time window of 5 hours.
Each hour will represent the new nodes added at the hour for the corresponding crawl. We will use the past five values to predict the current.
The corresponding label will be defined as zero or one based on the percentage change since the last checkpoint.
The checkpoint is represented as the point when the number of nodes added passes the threshold.
We follow a cumulative type of strategy. For the current node, if new nodes added since the last checkpoint is higher than the threshold, it will become new checkpoint and labeled as one, i.e., to crawl otherwise it will be marked as zero, i.e., not to crawl and its nodes will be added to next and checked again for that node. It will help the model to learn when to crawl the website i.e., when there is a significant change in the site structure. Please see Figure \ref{fig:piplelineSitemeap}.
The generating training data for classification step is showing the same thing, and the picture shows the final matrix created.  

\subsubsection{Facebook Prophet}
As discussed in previous sections, the Prophet restricts the input for the model to just timestamps and the corresponding label.
In our case, we tried to predict the percentage change.
An hourly crawl timestamp will represent the Prophet's timestamp requirement.
The corresponding label is the percentage change in nodes since the last checkpoint.
Once we have the dataset created, we train the Facebook Prophet model. 

\subsubsection{Evaluations}

Table \ref{tab:baselineModelssitemap} shows the evaluation results for the predictions by SVM and Random Forest.
Among baseline models, SVM showed an accuracy of 71\%.
It does perform better as compared to the Random Forest model, with better accuracy and recall, but lower precision. 
A possible reason is that Random Forests generally don’t fit very well for increasing or decreasing trends, especially when dealing with time-series analysis.
In contrast, the ability of SVM to solve nonlinear regression estimation problems makes it successful in time series forecasting. 

\begin{table}[]
\centering

\begin{tabular}{|c|c|c|c|c|}
\hline
Model  & Accuracy & Precision & Recall & F1 Score       \\ \hline

Support Vector Machine  & 0.71 & 0.53 & 0.71 & 0.61       \\ \hline

Random Forest  & 0.615 & 0.59 & 0.59 & 0.59       \\ \hline

\end{tabular}%
\caption{Model Evaluation: Sitemap Classification}
\label{tab:baselineModelssitemap}
\end{table}

Facebook Prophet has an inbuilt feature that enabled us to plot the forecasts it generated.
Figures \ref{fig:fbpred} and \ref{fig:fbpred2} are the plots generated.
In Figure \ref{fig:fbpred}, the blue line in the graph outlines the predicted values, while the black dots are the data in our dataset. 
It also shows the future predictions for the next 48 hours in the graphs.
In Figure \ref{fig:fbpred2}, Prophet shows the captured trend and identified the patterns from the dataset. 

\begin{figure}[!ht]
    \centering
  \includegraphics[width=0.8\textwidth]{figures/figure3.png}
  \caption{The output of the Facebook Prophet model illustrating prediction percentage. It also shows predictions for the next 48 hours.}
  \label{fig:fbpred}
\end{figure}

\begin{figure}[!ht]
    \centering
  \includegraphics[width=0.8\textwidth]{figures/figure4.png}
  \caption{The output of the Facebook Prophet, illustrating general trend in the first case and an instance in the future when the website should be crawled according to the model, in the second case.}
  \label{fig:fbpred2}
\end{figure}

We notice that every day between 4 AM to 12 noon and 4 PM to 8 PM, there are relatively more changes to the site content.
Crawling should be scheduled during these times. 

\section{Reinforcement Learning}
In this section, we evaluate the performance of our proposed RL model on web page content prediction. 
In this preliminary evaluation, we aim to find evidence that our proposed RL model can work as a potential solution to our crawling scheduler problem.
In this evaluation, we use the model to generate crawling plans for CNN's main page.
We compared the performance of our proposed continuous prediction approach and sparse prediction approach, the performance influence of fixed reward and scaled reward, and the training policy performance between DQN and PPO.
We look at the quality of our proposed methods in different settings through our predefined rewarding system.

\textbf{Evaluation Data} We use the same CNN main page data as in the web page content prediction baseline models.

\textbf{Model Details} 
We use a seven day period as the history observation.
For the RL model parameters, we use a multi-layer perceptron network for both the DQN and PPO2 algorithms. 
We set the training step as 100000 steps.
The data is divided into a training set and a test set in an 8:2 ratio.


Table~\ref{tab:eval} shows the result of our evaluation.
Considering the training policies, we can see that DQN is not generating good results for our problem, as all the scores are negative.
PPO2, on the other hand, is producing acceptable results with positive values, which means the future web page changes are successfully captured with a crawling plan.
The max score indicates a perfect one-shot prediction. 
The positive averaged score of the model indicates that the model still loses many points from wrong decisions in the generated plan.

At the current stage, it is hard to distinguish the performance between continuous prediction and sparse prediction as both of them are getting an averaged score that is approximately half of the max score.
We think we could design a unified rewarding system for both cases to compare the performance in the future.
As to the reward strategies, we can see that the scaled score is producing slightly higher scores than the fixed score. 
Still, we can not yet conclude that the scaled score is a better choice than the fixed one. 
The results of the scaled score might indicate that the model might tend to get higher scores compared with our given fixed score value.
The quality of the model will need to be evaluated by comparing the generated crawling plan results, where we need to define a metric to evaluate both the accuracy and redundancy.
Overall, the results are showing that our proposed model can generate a feasible plan on average for our crawling scheduling problem. 

\begin{table}[!ht]
\begin{tabular}{|c|ccc|ccc|}
\hline
                      & Max Fixed Score & DQN   & PPO2 & Max Scaled Score & DQN   & PPO2 \\ \hline
continuous prediction & 50              & -28.5 & 27.6 & 50               & -26.8 & 30.8 \\ \cline{1-1}
sparse prediction     & 20              & N/A   & 9.7  & 20               & N/A   & 10.5 \\ \hline
\end{tabular}
\caption{The results for RL modal preliminary evaluation. The max score is showing the maximum score the modal could achieve in each plan generation. The score for each model is the averaged score on the testing data set.}
\label{tab:eval}
\end{table}



\subsection{Future Work}
The current evaluation of our work only shows the preliminary results that our proposed RL models have the potential to solve our crawling scheduler problem.
There remain questions to be answered:
(1) How good are the results from the RL model compared with predefined crawling policies, e.g., a simple frequency-based policy; and
(2) how good are the results from RL model compared with the crawling strategies built upon the supervised machine learning models as in baselines.
For future work, we need to build a unified standard to compare the performance of these different methods so that the performance of different models can be evaluated quantitatively.
We also need a unified rewarding architecture where we can measure the different RL action models.
On top of the prediction models we have covered in baselines, we need to build a corresponding crawling plan generation system that can produce the scheduler results.

\section{Conclusion}
In this chapter, we have implemented several traditional supervised machine learning models on the problem of predicting web content changes. 
We have also explored reinforcement learning models that can generate web crawling plans.
The preliminary result shows that the RL model has the potential to work as an intelligent web crawling scheduler.
We will cover the future works in Chapter 7 regarding further plans for this research.
