# Solving Multi-Document Summarization as an Orienteering Problem
## 6 Experiments
### Evaluation Metrics  
This study used ROUGE (Recall-Oriented Understudy for Gisting Evaluation) [6] to evaluate the performance of MDS-OP. ROUGE is a set of metrics used to automatically evaluate summarization systems by counting the overlapping units (e.g., n-gram) between the automatically produced summary (i.e., the peer) and one or a set of human created summaries (i.e., references). ROUGE has been adapted by DUC since DUC 2004 [68] and it comprises different metrics, including ROUGE-N (N-gram Co-Occurrence Statistics), ROUGE-L (Longest Common Subsequence), ROUGE-S (Skip-Bigram Co-Occurrence Statistics), and ROUGE-W (Weighted Longest Common Subsequence). The recall version of ROUGE-N measure, for example, evaluates a given summary by calculating the n-gram recall between the summary obtained and a set of reference (i.e., model) summaries as follows:  
\[\frac{\sum_{S\in\{ReferenceSummaries\}}\sum_{gram_{n}\in S}Count_{ match}(gram_{n})}{\sum_{S\in\{ReferenceSummaries\}}\sum_{gram_{n}\in S}Count(gram_{n})}\]  
where \(Count_{match}\) is the maximum number of the shared n-grams between the summary to be evaluated and reference ones, \(Count\) is the sum of the number of n-grams in the reference summaries, and \(n\) is the n-gram length. ROUGE-L evaluates the summary based on the shared longest common subsequence (LCS). ROUGE-W is similar to ROUGE-L except it gives more weight to consecutive matches. Finally, ROUGE-S and ROUGE-SU evaluate the summary based on the shared skip-bigrams with and without the addition of unigram as counting unit, respectively.  
The recent version of ROUGE software package (i.e., ROUGE 1.5.5) calculates the recall, precision, and F-measure scores. In this paper, for the DUC 2004 corpus, all the results of the baseline, humans, and rival systems were re-evaluated using this version so all the the comparison results are based on this version. The same values of ROUGE parameters provided at the competition were used. Different ROUGE metrics, similar to those used at the competition, were also used in this study. Specifically, ROUGE-1, ROUGE-2, ROUGE-3, ROUGE-4, ROUGE-L, and ROUGE-W were used. Similar evaluation process was applied to MultiLing 2015 corpus. The evaluation results are based on using the same ROUGE metrics (ROUGE-1, ROUGE-2, and ROUGE-SU4) and parameters used at the TAC 2011 MultiLing Pilot. The performance results of MDS-OP are reported in terms of the average F-measure scores of five runs.  
In addition to ROUGE metrics, three official evaluation methods at MultiLing 2015 were used. The first one is AutoSummENG (AUTOmatic SUMMARY Evaluation based on N-gram Graphs) [7], which is a language-independence method that creates an n-gram graph for each reference and peer summaries. It calculates the performance of a summary by averaging the similarities between this summary and each reference summaries. The second method is MeMoG (Merged Model Graph) [8], which is a variation of AutoSummENG where one merged graph represents all reference summaries. Finally, NPowER (N-gram graph Powered Evaluation via Regression) [9] is the third method, which is  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**System ID** & **Participant** & **Reference** \\ \hline MMS1 & UJF-Grenoble & [19] \\ MMS2 & UWB & * \\ MMS3 & ExB & [41] \\ MMS5 & ESI-AllSummarizer & [29] \\ MMS8 & IDA-OCCAMS & [17] \\ MMS9 & GiauUngVan & * \\ MMS11 & SCE-Poly & [50] \\ MMS12 & BUPT-CIST & [21] \\ MMS13 & BGU-MUSE & [24] \\ MMS15 & NCSR/SCIFY-NewSumRerank & * \\ \hline \hline \end{tabular}  
* The official MultiLing 2015 website does not contain any details on these participants.  
\end{table}
Table 3: Systems that participated at MultiLing 2015 (MMS task).  
a machine-learning-based method where the features are the evaluation methods and the target is the human evaluation grade. It uses liner regressions to combine the previous two evaluation methods.