

\section{Overview of Our Approach}

\subsection{Task Definition\label{sec:tasks}}

Given a news article collection $C$ of a topic and a set of query phrase $Q$, we seek to generate a timeline $S$ with $l$ dates $\left({d_1, d_2, ..., d_l}\right)$ and $k_i$ sentences associated with $d_i$ as summary. The total number of sentences of a timeline summary is $N=\sum_{i=1}^{l}  k_i  $.  Our goal is to  choose $l$  on a per topic basis automatically. 







\subsection{Candidate Ranking}
We leverage the elbow method to choose the TLS parameters defined in Section~\ref{sec:tasks}. 
To do so, we start by scoring and sorting the candidate dates. We then detect the date fraction series's knee point (elbow) and use it to select the parameters. In this work, we use \textit{Kneedle}~\cite{5961514} to detect the knee point.     


To rank candidates, we construct a \textbf{Selection Confidence (SC)} metric, defined as follows:
\begin{equation}
    SC(I, c)=-\log \left(\frac{\sum_{i=1}^{c} f_{I}\left(I_{i}\right)}{c}+\alpha\right)
    \label{eq:sc}
\end{equation}  
where $I$ indicates the items to evaluate and rank, i.e., dates or events in our case; $c$ is the constraint to select, i.e., timeline length $l$ (the number of key dates or events). $f_{I}$ is the score function of $I$; $\alpha$ is a positive number to prevent zero in $\log$. This function produces an average score of selected items under constraint $c$. It is used by the elbow method to determine the knee point where adding more information after the point is unlikley to improve the quality (or information) for the summary collection. 







\subsection{Illustrative Examples}
As a working example for choosing the timeline length, $l$, using our method, consider Figure \ref{knee}. This figure shows how our metric (selection confidence) can help the elbow method in choosing $l$ for the \textit{Silvio Berlusconi} topic. Here, the x-axis gives the timeline length as the number of dates $L$ our system selects, and the y-axis shows the selection confidence computed using Equation \ref {eq:sc} and the Date F1-score under different $L$s. 

As shown from the figure,  the knee point ($l$) of  the selection confidence  strongly correlates with the max Date F1-score ($l’$). The knee point is automatically chosen by our elbow method using the selection confidence metric (Equation \ref {eq:sc}). This suggests that our approach can help one to locate $l$ that maximizes the Date F1-score. We can see that our chosen timeline length, $l=33$, is closer to the expert chosen $L$ of 34 (given by the Entities dataset) and is not far from $l' =26$  that gives the maximum Date F1 score. This example shows that the elbow method, combined with our selection confidence metric, can be effective in automatically selecting TLS key dates. 




\begin{figure}[t]
\center{\includegraphics[width=0.32\textwidth]
        {kneel.pdf}}
             \vspace{-0.1in}
        \caption{\label{knee} Best $l$ selection and corresponding knee point for Entities dataset.}
        \vspace{-0.1in}
\end{figure}


\subsection{Our Approach}
Our approach, namely the Adaptive Date Ranking Method (AdpRM), offers two variants for TLS parameter selection:  AdpRM-D for date ranking and AdpRM-E for event ranking. 
In this section, we explain our variants for selecting TLS parameters. We also present the corresponding score function, explaining how to choose a constraint and giving specific solutions in detail.



\subsubsection{Adaptive Date Ranking Methods (AdpRM-D)} 


Our date ranking methods extract dates from news collections, including publishing articles and the date mentioned in articles. It also scores the date and selecting the top $l$ date as illustrated in Figure  \ref{knee}. Then, we use the chosen $l$ to generate a daily summary for each date and construct a timeline summary.  We use a regression method to score dates and define our score function as:

\begin{equation}
f_{date}(d)=reg(d)
\end{equation}

where $d$ is the dates and $reg$ is the regression function we trained for predicting date score.



\subsubsection{Adaptive Event Ranking Methods (AdpRM-E)} 

Our methods for event ranking first detect events. Then, we score events and select  $l$ events with the highest score. To do so, we analyze and select the date with the highest occurrence as the event time for each cluster and generate a timeline summary. To see the set of key dates, $L$,  we use the event scoring method of DateMention~\cite{gholipour-ghalandari-ifrim-2020-examining} which is defined as: 

\begin{equation}
f_{event}(d_e) = {cnt}_e(d_e)
\end{equation}


where $d_e$ is the date event occurred and ${cnt}_e$ counts the appearances of $d_e$ in sub-article-collection of event $e$.  





\section{Conclusion}
We have proposed a new approach of TLS based on automatic constraints selection, called Adaptive Ranking Methods for TLS  (AdpRMs). We have also constructed a large-scale Chinese TLS dataset to fill a gap in Chinese. 
Our methods can be flexibly extended to practical scenarios compared with previous works since our methods can select the appropriate timeline length adaptively.
Sufficient experimental results demonstrate that our methods obtain comparative and even best performances on partial datasets. 


\section{Dataset}
We evaluate our approach by applying it to three English public datasets for TLS: T17~\cite{10.1145/2487788.2487829}, Crisis~\cite{tran-etal-2015-joint} and Entities~\cite{gholipour-ghalandari-ifrim-2020-examining}. Table \ref{dataset} shows the statistics of these datasets. Here, 
`Topics' is the number of topics of the dataset, and `TLs' is the number of ground truth timelines. 
`DurComp' is compression ratio w.r.t. timeline length is $L$ divided by `Duration'.  
`SentComp' is compression ratio w.r.t. sentences is $N$ divided by the total number of sentences in $C$. 
`DateComp' is compression ratio w.r.t. dates is $l$ divided by the total number of dates mentioned in $C$, and `AvgDateCov' refers to the average coverage of dates in the ground truth timeline by the news in $C$.
T17 has longer (AvgL=36) timelines than the other datasets, Crisis has more articles (AvgDocsNum=2310), and Entities has more extended periods (AvgDuration=4437).

To evaluate our approach's generalization ability, we also construct a new Chinese dataset\footnotemark[1] named TLCN. TLCN contains up to 77 different topics. 
Compared with previous public datasets, our dataset has the largest number of topics and timelines. 
Besides, TLCN has a big enough compression ratio of duration (AvgDurComp= 0.5996), although it has a smaller timeline length (AvgL=6). 





\begin{table}[tbp]
\caption{\label{dataset} Dataset Statistics.}
\small
\begin{tabular}{l|rrrr}
\toprule
\textbf{Dataset} & \textbf{T17} & \textbf{Crisis} & \textbf{Entities} & \textbf{TLCN} \\ \hline
\textbf{Topics} & 9 & 4 & 47 & 77 \\
\textbf{TLs} & 19 & 22 & 47 & 77 \\
\textbf{AvgSentNum} & 20409 & 82761 & 31545 & 28724 \\
\textbf{AvgDocsNum} & 508 & 2310 & 959 & 1257 \\
\textbf{AvgL} & 36 & 29 & 23 &  6 \\
\textbf{AvgK} & 2.9 & 1.3 & 1.2 & 1.4 \\
\textbf{AvgDuration} & 212 & 343 & 4437 & 55 \\
\textbf{AvgDurComp} & 0.4135 & 0.1950 & 0.0048 & 0.5996 \\
\textbf{AvgSentComp} & 0.0117 & 0.0005 & 0.0017 & 0.0048 \\
\textbf{AvgDateComp} & 0.45 & 0.11 & 0.06 & 0.51 \\
\textbf{AvgDateCov} & 0.81 & 0.9 & 0.51 & 0.88 \\ \bottomrule
\end{tabular}
\end{table}




\footnotetext[1]{Chen 2019's work also released a dataset for the abstraction-level TLS. This task generates a summary with dates in it, while our task generates a list of summaries with timestamps. }



\section{Experiments}

\subsection{Evaluation Metrics}

We evaluate TLS in both summarization and temporal dimension following measures proposed by ~\citet{martschat-markert-2017-improving}:
\begin{itemize}[leftmargin=*]
\item \textbf{Align-based Rouge F1-score:} This metric compares daily summaries of ground truth timeline and generated timeline. It takes temporal and semantic similarity into account while not requiring an exact match between days.
\item \textbf{Date F1-score:} This metric compares the dates of the ground truth timeline and generated timeline.
\end{itemize}

\subsection{Experimental setup}
Our prototype~\footnotemark[2] builds upon Marschat~\cite{martschat-markert-2018-temporally} and  Gholipour~\cite{gholipour-ghalandari-ifrim-2020-examining}. 
To process the Chinese dataset, we use LTP~\cite{che2020n} for Chinese text segmentation. 
Meanwhile, we use the tool Recognizers-Text~\footnotemark[3] to detect and resolve textual mentions of dates. 



\footnotetext[2]{https://github.com/smartschat/tilse and https://github.com/complementizer/news-tls}
\footnotetext[3]{ttps://github.com/Microsoft/Recognizers-Text}

 We compare our AdpRMs with previous salient TLS systems.  
 For constraints selection on previous works, we use a stricter and simpler version of the output size constraints following Gholipour~\cite{gholipour-ghalandari-ifrim-2020-examining}: they produce timelines with the fixed expert chosen the number of dates $L$ and daily summary length $K$. 
 They set $L$ as the average length of ground truth timelines and set $K$ as the average length of daily summaries related to the same topic. We evaluate the following types of TLS ranking methods.



\vspace{0.1in}
\textbf{Date ranking methods:} 
\begin{itemize}[leftmargin=*]
    \item DATEWISE~\cite{gholipour-ghalandari-ifrim-2020-examining}: This method achieves state-of-the-art among previous works. 
    It uses a supervised date selection and uses a greedily optimized centroid-based method (CENTROID-OPT) for summarization.
    \item AdpRM-D: Our date ranking method. This method uses a regression function to score the dates and uses the centroid-rank method to score the candidate sentences. 
    For the AdpRM-D BASE method, we set up constraints as DATEWISE without automatic constraint selection. AdpRM-D +L ($k_{exp}$) method indicates the constraint $L$ is automatic selected and $K$ is expert chosen. AdpRM-D +L ($k_{1}$) method indicates the $L$ is automatic selected and $K$ is equals 1.
\end{itemize}





\textbf{Event ranking methods:} 
\begin{itemize}[leftmargin=*]
    \item CLUST~\cite{gholipour-ghalandari-ifrim-2020-examining}: This method achieves the best performance among previous event ranking methods. Event clusters rank how often the cluster date is mentioned throughout the input collection, and it uses CENTROID-OPT for summarization.
    \item AdpRM-E: Our event ranking method. These methods use Markov clustering to detect events, use date appearances count methods to rank events, summarize the method, and experimental setup follows AdpRM-D.
\end{itemize}


\subsection{Results and Analysis}


Our experimental results are shown in Table \ref{experiments-results}. 
Overall, our method performs differently on different datasets and obtains the best results partially (results marked with $\star$), and it achieves significant improvements (results marked with $\diamond$) over the baseline of each ranking method.   

\textbf{For date ranking methods}, AdpRM-D +L($k_1$) has a state-of-the-art performance on TLCN. It gets almost similar results compared with DATEWISE on Entities and Crisis datasets. 
Among AdpRM-Ds, the +L method with $k=1$ performs better than the method with expert-chosen $k$ on Entities and TLCN datasets since their $AvgK$ values are close to 1. 

\textbf{For event ranking methods}, we find that methods without timeline length $L$ automatic selected always fail to generate important dates. 
The AdpRM-E has a noticeable improvement on the Date F1-score for all datasets. 
For instance, AdpRM-E +L($k_1$) has a 0.098 Date F1-score increase compared with CLUST on TLCN and gets competitive results on other datasets.   




The TLS datasets have different characteristics, which results in TLS systems performing variously. Our AdpRM-Ds reach state-of-the-art among partial datasets, and they can apply to real-world practical cases without expert knowledge.


\section{Introduction}





Timeline summarization (TLS) generates an overview of long-running events through dated summaries from multiple documents like news articles for the most important dates. 
It provides users with automatically generated timelines that identify key dates in a long-lasting development along with short descriptions of the events on these dates. 
For example, Table \ref{timeline-example} shows the journalist-generated timelines for two topics from the Entities dataset ~\cite{gholipour-ghalandari-ifrim-2020-examining}. 

To generate summaries for a long-running event, we need to determine the dates on which a summary will be created. 
Getting this setting right is essential for high-quality TLS. Missing key dates can hinder understanding, but including too much redundant information also contradicts the purpose of TLS. Expert-generated TLS avoids this problem by flexibly choosing important dates for events to generate daily summaries.  
For examples, the hand-crafted timelines in Table \ref{timeline-example} have different key dates, 6 and 34 for the \textit{David Bowie} and the \textit{Silvio Berlusconi} topics, respectively. 



\begin{table}[t]
\small
\begin{tabular}{p{0.46\columnwidth}|p{0.46\columnwidth}}
\toprule

\textbf{Topic A: David Bowie} & \textbf{Topic B: Silvio Berlusconi}  \\ \hline

\textbf{(D1): }1996-01-17\newline
Is inducted into the Rock and Roll Hall of Fame.  & 
\textbf{(D1): }1986-02-19\newline
Buys the AC Milan football club.
\\ \hline


\textbf{(D2): }2004-06-25\newline
While on tour, visits a hospital in Hamburg ... an angioplasty. &
\textbf{(D2): }1994-01-26\newline
Bloody and bruised the journalist caught in Egypt unrest.
\\ \hline


\textbf{(D3): }2015-12-07\newline
``Lazarus'' written by Bowie and Edna Walsh, ... lead role in the 1976 movie version. &
\textbf{(D3): }1994-12-22\newline
Is removed from office after losing the support of other political parties.
\\ \hline

\begin{center}
    ......
\end{center} &
\begin{center}
    ......
\end{center}
\\  \hline


\textbf{(D6): }2016-12-06\newline
Bowie receives four posthumous ... for best recording package. & 

\textbf{(D34): }2018-05-11\newline
The Court of Milan grants Berlusconi ... is not allowed to run for public office.
\\
\bottomrule
\end{tabular}
\vspace{0.1in}
\caption{\label{timeline-example} Excerpts timeline for \textit{David Bowie} (left) and timeline for \textit{Silvio Berlusconi} (right) on dataset Entities~\cite{gholipour-ghalandari-ifrim-2020-examining}. D* is the index of dates. } 
\end{table}

While the key dates often vary across topics, existing TLS solutions rely on either  an event-agnostic, fixed setting or an event-specific setting given by human experts. 
Such approaches work by either mapping sentences chosen from a news collection to the pre-defined key dates~\cite{10.1145/1008992.1009065, article}, or choosing which dates to be included in the date slots to generate the summary~\cite{tran-etal-2015-joint, gholipour-ghalandari-ifrim-2020-examining}, or selecting the top-l event developments to generate key date, and daily summaries for each event~\cite{steen-markert-2019-abstractive, gholipour-ghalandari-ifrim-2020-examining}. 
None of these approaches is flexible as they assume the number of key dates (i.e., the timeline length) across events or must be manually supplied by a human expert~\cite{martschat-markert-2018-temporally, gholipour-ghalandari-ifrim-2020-examining}. 
Since an automated TLS system needs to process a large amount of dynamically evolving newsworthy events, often in a (near) real-time fashion, relying on expert input is neither scalable nor sustainable. To unlock the potential of real-time TLS, we need to find ways to overcome these limitations. 


This paper presents a novel TLS method to lift the aforementioned constraint imposed by existing TLS solutions. 
Our approach leverages the established elbow method~\cite{5961514} to automatically choose the key information to be covered and used by a TLS framework. This method has been shown to be effective in choosing representative key points from data samples, such as determining the number of clusters used by a K-means algorithm~\cite{DBLP:journals/npsc/HathawayB94}. To determine the timeline length, our approach first scores and ranks the candidate dates of a long-running event. It then applies the elbow method to choose the dates to be covered by the generated summaries. 
It achieves this by automatically finding the cut-off point (i.e., the knee point) on the time series where the information gain beyond the point reaches (or nearly reaches) a plateau. 
Essentially, our goal is to find a compact set of key dates where adding an additional date does not improve the information coverage.
We demonstrate that our approach is simple and effective, allowing one to automatically build a flexible TLS system to determine an appropriate timeline length across topics automatically. 




We apply our approach\footnote{Code and data available at: [\emph{url redacted for blind review}].} to three real-life open TLS datasets of English articles~\cite{10.1145/2487788.2487829,tran-etal-2015-joint,gholipour-ghalandari-ifrim-2020-examining}. 
To showcase our scheme's generalization ability, we also construct a new Chinese TLS dataset and evaluate our scheme on it. We compared our approach to two representatives TLS methods propsed in ~\cite{gholipour-ghalandari-ifrim-2020-examining}. We consider two commonly used TLS metrics~\cite{martschat-markert-2017-improving}: the Align-based Rouge F1-score and the Date F1-score. Experimental results show that our approach delivers comparable and even better TLS performance compared to prior methods that use expert-supplied TLS length settings. However, it achieves this without expert involvement.


This paper makes the following contributions:
\begin{itemize}[leftmargin=*]
  \item It is the first to target the automatic selection of key dates for TLS systems;
  \item It is the first to employ the elbow method to address the constraint selection problem for TLS systems;
  \item It introduces and provides a new Chinese TLS dataset (that will be open-sourced upon acceptance), filling the language gap offered by existing TLS datasets. 
\end{itemize}






\section{Related works}


\citet{10.1145/345508.345546} firstly proposed a timeline system and introduced the task of TLS  \cite{10.1145/383952.383954}. TLS has received considerable attention in recent years\cite{10.1145/1008992.1009065,10.5555/2145432.2145483,10.1145/2009916.2010016,kessler-etal-2012-finding,10.1145/2487788.2487829,article,li-li-2013-evolutionary,wang-etal-2015-socially,tran2015timeline,tran-etal-2015-joint,wang-etal-2016-low,martschat-markert-2018-temporally,steen-markert-2019-abstractive,gholipour-ghalandari-ifrim-2020-examining}. 
Submodular methods are another kind of popular TLS solution besides the ranking methods mentioned before. By defining an optimism function, these methods select sentences greedily and organize them to a timeline summary\cite{tran2015timeline,martschat-markert-2018-temporally}.   \citet{martschat-markert-2018-temporally} discuss important constraints selection and give a theoretical method to achieve budgeted maximization of submodular functions according to   \citet{10.5555/1857999.1858133}. 
However, existing approaches use a fixed timeline length for TLS or relying on expert involvement to determine the parameters. Our approach advances prior works by developing a new approach to determine the timeline length automatically. 










\section{Overview of Our Approach}

\subsection{Task Definition\label{sec:tasks}}

Given a news article collection $C$ of a topic and a set of query phrase $Q$, we seek to generate a timeline $S$ with $l$ dates $\left({d_1, d_2, ..., d_l}\right)$ and $k_i$ sentences associated with $d_i$ as summary. The total number of sentences of a timeline summary is $N=\sum_{i=1}^{l}  k_i  $.  Our goal is to  choose $l$  on a per topic basis automatically. 







\subsection{Candidate Ranking}
We leverage the elbow method to choose the TLS parameters defined in Section~\ref{sec:tasks}. 
To do so, we start by scoring and sorting the candidate dates. We then detect the date fraction series's knee point (elbow) and use it to select the parameters. In this work, we use \textit{Kneedle}~\cite{5961514} to detect the knee point.     


To rank candidates, we construct a \textbf{Selection Confidence (SC)} metric, defined as follows:
\begin{equation}
    SC(I, c)=-\log \left(\frac{\sum_{i=1}^{c} f_{I}\left(I_{i}\right)}{c}+\alpha\right)
    \label{eq:sc}
\end{equation}  
where $I$ indicates the items to evaluate and rank, i.e., dates or events in our case; $c$ is the constraint to select, i.e., timeline length $l$ (the number of key dates or events). $f_{I}$ is the score function of $I$; $\alpha$ is a positive number to prevent zero in $\log$. This function produces an average score of selected items under constraint $c$. It is used by the elbow method to determine the knee point where adding more information after the point is unlikley to improve the quality (or information) for the summary collection. 







\subsection{Illustrative Examples}
As a working example for choosing the timeline length, $l$, using our method, consider Figure \ref{knee}. This figure shows how our metric (selection confidence) can help the elbow method in choosing $l$ for the \textit{Silvio Berlusconi} topic. Here, the x-axis gives the timeline length as the number of dates $L$ our system selects, and the y-axis shows the selection confidence computed using Equation \ref {eq:sc} and the Date F1-score under different $L$s. 

As shown from the figure,  the knee point ($l$) of  the selection confidence  strongly correlates with the max Date F1-score ($l’$). The knee point is automatically chosen by our elbow method using the selection confidence metric (Equation \ref {eq:sc}). This suggests that our approach can help one to locate $l$ that maximizes the Date F1-score. We can see that our chosen timeline length, $l=33$, is closer to the expert chosen $L$ of 34 (given by the Entities dataset) and is not far from $l' =26$  that gives the maximum Date F1 score. This example shows that the elbow method, combined with our selection confidence metric, can be effective in automatically selecting TLS key dates. 




\begin{figure}[t]
\center{\includegraphics[width=0.32\textwidth]
        {kneel.pdf}}
             \vspace{-0.1in}
        \caption{\label{knee} Best $l$ selection and corresponding knee point for Entities dataset.}
        \vspace{-0.1in}
\end{figure}


\subsection{Our Approach}
Our approach, namely the Adaptive Date Ranking Method (AdpRM), offers two variants for TLS parameter selection:  AdpRM-D for date ranking and AdpRM-E for event ranking. 
In this section, we explain our variants for selecting TLS parameters. We also present the corresponding score function, explaining how to choose a constraint and giving specific solutions in detail.



\subsubsection{Adaptive Date Ranking Methods (AdpRM-D)} 


Our date ranking methods extract dates from news collections, including publishing articles and the date mentioned in articles. It also scores the date and selecting the top $l$ date as illustrated in Figure  \ref{knee}. Then, we use the chosen $l$ to generate a daily summary for each date and construct a timeline summary.  We use a regression method to score dates and define our score function as:

\begin{equation}
f_{date}(d)=reg(d)
\end{equation}

where $d$ is the dates and $reg$ is the regression function we trained for predicting date score.



\subsubsection{Adaptive Event Ranking Methods (AdpRM-E)} 

Our methods for event ranking first detect events. Then, we score events and select  $l$ events with the highest score. To do so, we analyze and select the date with the highest occurrence as the event time for each cluster and generate a timeline summary. To see the set of key dates, $L$,  we use the event scoring method of DateMention~\cite{gholipour-ghalandari-ifrim-2020-examining} which is defined as: 

\begin{equation}
f_{event}(d_e) = {cnt}_e(d_e)
\end{equation}


where $d_e$ is the date event occurred and ${cnt}_e$ counts the appearances of $d_e$ in sub-article-collection of event $e$.  





\section{Conclusion}
We have proposed a new approach of TLS based on automatic constraints selection, called Adaptive Ranking Methods for TLS  (AdpRMs). We have also constructed a large-scale Chinese TLS dataset to fill a gap in Chinese. 
Our methods can be flexibly extended to practical scenarios compared with previous works since our methods can select the appropriate timeline length adaptively.
Sufficient experimental results demonstrate that our methods obtain comparative and even best performances on partial datasets. 


\section{Dataset}
We evaluate our approach by applying it to three English public datasets for TLS: T17~\cite{10.1145/2487788.2487829}, Crisis~\cite{tran-etal-2015-joint} and Entities~\cite{gholipour-ghalandari-ifrim-2020-examining}. Table \ref{dataset} shows the statistics of these datasets. Here, 
`Topics' is the number of topics of the dataset, and `TLs' is the number of ground truth timelines. 
`DurComp' is compression ratio w.r.t. timeline length is $L$ divided by `Duration'.  
`SentComp' is compression ratio w.r.t. sentences is $N$ divided by the total number of sentences in $C$. 
`DateComp' is compression ratio w.r.t. dates is $l$ divided by the total number of dates mentioned in $C$, and `AvgDateCov' refers to the average coverage of dates in the ground truth timeline by the news in $C$.
T17 has longer (AvgL=36) timelines than the other datasets, Crisis has more articles (AvgDocsNum=2310), and Entities has more extended periods (AvgDuration=4437).

To evaluate our approach's generalization ability, we also construct a new Chinese dataset\footnotemark[1] named TLCN. TLCN contains up to 77 different topics. 
Compared with previous public datasets, our dataset has the largest number of topics and timelines. 
Besides, TLCN has a big enough compression ratio of duration (AvgDurComp= 0.5996), although it has a smaller timeline length (AvgL=6). 





\begin{table}[tbp]
\caption{\label{dataset} Dataset Statistics.}
\small
\begin{tabular}{l|rrrr}
\toprule
\textbf{Dataset} & \textbf{T17} & \textbf{Crisis} & \textbf{Entities} & \textbf{TLCN} \\ \hline
\textbf{Topics} & 9 & 4 & 47 & 77 \\
\textbf{TLs} & 19 & 22 & 47 & 77 \\
\textbf{AvgSentNum} & 20409 & 82761 & 31545 & 28724 \\
\textbf{AvgDocsNum} & 508 & 2310 & 959 & 1257 \\
\textbf{AvgL} & 36 & 29 & 23 &  6 \\
\textbf{AvgK} & 2.9 & 1.3 & 1.2 & 1.4 \\
\textbf{AvgDuration} & 212 & 343 & 4437 & 55 \\
\textbf{AvgDurComp} & 0.4135 & 0.1950 & 0.0048 & 0.5996 \\
\textbf{AvgSentComp} & 0.0117 & 0.0005 & 0.0017 & 0.0048 \\
\textbf{AvgDateComp} & 0.45 & 0.11 & 0.06 & 0.51 \\
\textbf{AvgDateCov} & 0.81 & 0.9 & 0.51 & 0.88 \\ \bottomrule
\end{tabular}
\end{table}




\footnotetext[1]{Chen 2019's work also released a dataset for the abstraction-level TLS. This task generates a summary with dates in it, while our task generates a list of summaries with timestamps. }



\section{Experiments}

\subsection{Evaluation Metrics}

We evaluate TLS in both summarization and temporal dimension following measures proposed by ~\citet{martschat-markert-2017-improving}:
\begin{itemize}[leftmargin=*]
\item \textbf{Align-based Rouge F1-score:} This metric compares daily summaries of ground truth timeline and generated timeline. It takes temporal and semantic similarity into account while not requiring an exact match between days.
\item \textbf{Date F1-score:} This metric compares the dates of the ground truth timeline and generated timeline.
\end{itemize}

\subsection{Experimental setup}
Our prototype~\footnotemark[2] builds upon Marschat~\cite{martschat-markert-2018-temporally} and  Gholipour~\cite{gholipour-ghalandari-ifrim-2020-examining}. 
To process the Chinese dataset, we use LTP~\cite{che2020n} for Chinese text segmentation. 
Meanwhile, we use the tool Recognizers-Text~\footnotemark[3] to detect and resolve textual mentions of dates. 



\footnotetext[2]{https://github.com/smartschat/tilse and https://github.com/complementizer/news-tls}
\footnotetext[3]{ttps://github.com/Microsoft/Recognizers-Text}

 We compare our AdpRMs with previous salient TLS systems.  
 For constraints selection on previous works, we use a stricter and simpler version of the output size constraints following Gholipour~\cite{gholipour-ghalandari-ifrim-2020-examining}: they produce timelines with the fixed expert chosen the number of dates $L$ and daily summary length $K$. 
 They set $L$ as the average length of ground truth timelines and set $K$ as the average length of daily summaries related to the same topic. We evaluate the following types of TLS ranking methods.



\vspace{0.1in}
\textbf{Date ranking methods:} 
\begin{itemize}[leftmargin=*]
    \item DATEWISE~\cite{gholipour-ghalandari-ifrim-2020-examining}: This method achieves state-of-the-art among previous works. 
    It uses a supervised date selection and uses a greedily optimized centroid-based method (CENTROID-OPT) for summarization.
    \item AdpRM-D: Our date ranking method. This method uses a regression function to score the dates and uses the centroid-rank method to score the candidate sentences. 
    For the AdpRM-D BASE method, we set up constraints as DATEWISE without automatic constraint selection. AdpRM-D +L ($k_{exp}$) method indicates the constraint $L$ is automatic selected and $K$ is expert chosen. AdpRM-D +L ($k_{1}$) method indicates the $L$ is automatic selected and $K$ is equals 1.
\end{itemize}





\textbf{Event ranking methods:} 
\begin{itemize}[leftmargin=*]
    \item CLUST~\cite{gholipour-ghalandari-ifrim-2020-examining}: This method achieves the best performance among previous event ranking methods. Event clusters rank how often the cluster date is mentioned throughout the input collection, and it uses CENTROID-OPT for summarization.
    \item AdpRM-E: Our event ranking method. These methods use Markov clustering to detect events, use date appearances count methods to rank events, summarize the method, and experimental setup follows AdpRM-D.
\end{itemize}


\subsection{Results and Analysis}


Our experimental results are shown in Table \ref{experiments-results}. 
Overall, our method performs differently on different datasets and obtains the best results partially (results marked with $\star$), and it achieves significant improvements (results marked with $\diamond$) over the baseline of each ranking method.   

\textbf{For date ranking methods}, AdpRM-D +L($k_1$) has a state-of-the-art performance on TLCN. It gets almost similar results compared with DATEWISE on Entities and Crisis datasets. 
Among AdpRM-Ds, the +L method with $k=1$ performs better than the method with expert-chosen $k$ on Entities and TLCN datasets since their $AvgK$ values are close to 1. 

\textbf{For event ranking methods}, we find that methods without timeline length $L$ automatic selected always fail to generate important dates. 
The AdpRM-E has a noticeable improvement on the Date F1-score for all datasets. 
For instance, AdpRM-E +L($k_1$) has a 0.098 Date F1-score increase compared with CLUST on TLCN and gets competitive results on other datasets.   




The TLS datasets have different characteristics, which results in TLS systems performing variously. Our AdpRM-Ds reach state-of-the-art among partial datasets, and they can apply to real-world practical cases without expert knowledge.


\section{Introduction}





Timeline summarization (TLS) generates an overview of long-running events through dated summaries from multiple documents like news articles for the most important dates. 
It provides users with automatically generated timelines that identify key dates in a long-lasting development along with short descriptions of the events on these dates. 
For example, Table \ref{timeline-example} shows the journalist-generated timelines for two topics from the Entities dataset ~\cite{gholipour-ghalandari-ifrim-2020-examining}. 

To generate summaries for a long-running event, we need to determine the dates on which a summary will be created. 
Getting this setting right is essential for high-quality TLS. Missing key dates can hinder understanding, but including too much redundant information also contradicts the purpose of TLS. Expert-generated TLS avoids this problem by flexibly choosing important dates for events to generate daily summaries.  
For examples, the hand-crafted timelines in Table \ref{timeline-example} have different key dates, 6 and 34 for the \textit{David Bowie} and the \textit{Silvio Berlusconi} topics, respectively. 



\begin{table}[t]
\small
\begin{tabular}{p{0.46\columnwidth}|p{0.46\columnwidth}}
\toprule

\textbf{Topic A: David Bowie} & \textbf{Topic B: Silvio Berlusconi}  \\ \hline

\textbf{(D1): }1996-01-17\newline
Is inducted into the Rock and Roll Hall of Fame.  & 
\textbf{(D1): }1986-02-19\newline
Buys the AC Milan football club.
\\ \hline


\textbf{(D2): }2004-06-25\newline
While on tour, visits a hospital in Hamburg ... an angioplasty. &
\textbf{(D2): }1994-01-26\newline
Bloody and bruised the journalist caught in Egypt unrest.
\\ \hline


\textbf{(D3): }2015-12-07\newline
``Lazarus'' written by Bowie and Edna Walsh, ... lead role in the 1976 movie version. &
\textbf{(D3): }1994-12-22\newline
Is removed from office after losing the support of other political parties.
\\ \hline

\begin{center}
    ......
\end{center} &
\begin{center}
    ......
\end{center}
\\  \hline


\textbf{(D6): }2016-12-06\newline
Bowie receives four posthumous ... for best recording package. & 

\textbf{(D34): }2018-05-11\newline
The Court of Milan grants Berlusconi ... is not allowed to run for public office.
\\
\bottomrule
\end{tabular}
\vspace{0.1in}
\caption{\label{timeline-example} Excerpts timeline for \textit{David Bowie} (left) and timeline for \textit{Silvio Berlusconi} (right) on dataset Entities~\cite{gholipour-ghalandari-ifrim-2020-examining}. D* is the index of dates. } 
\end{table}

While the key dates often vary across topics, existing TLS solutions rely on either  an event-agnostic, fixed setting or an event-specific setting given by human experts. 
Such approaches work by either mapping sentences chosen from a news collection to the pre-defined key dates~\cite{10.1145/1008992.1009065, article}, or choosing which dates to be included in the date slots to generate the summary~\cite{tran-etal-2015-joint, gholipour-ghalandari-ifrim-2020-examining}, or selecting the top-l event developments to generate key date, and daily summaries for each event~\cite{steen-markert-2019-abstractive, gholipour-ghalandari-ifrim-2020-examining}. 
None of these approaches is flexible as they assume the number of key dates (i.e., the timeline length) across events or must be manually supplied by a human expert~\cite{martschat-markert-2018-temporally, gholipour-ghalandari-ifrim-2020-examining}. 
Since an automated TLS system needs to process a large amount of dynamically evolving newsworthy events, often in a (near) real-time fashion, relying on expert input is neither scalable nor sustainable. To unlock the potential of real-time TLS, we need to find ways to overcome these limitations. 


This paper presents a novel TLS method to lift the aforementioned constraint imposed by existing TLS solutions. 
Our approach leverages the established elbow method~\cite{5961514} to automatically choose the key information to be covered and used by a TLS framework. This method has been shown to be effective in choosing representative key points from data samples, such as determining the number of clusters used by a K-means algorithm~\cite{DBLP:journals/npsc/HathawayB94}. To determine the timeline length, our approach first scores and ranks the candidate dates of a long-running event. It then applies the elbow method to choose the dates to be covered by the generated summaries. 
It achieves this by automatically finding the cut-off point (i.e., the knee point) on the time series where the information gain beyond the point reaches (or nearly reaches) a plateau. 
Essentially, our goal is to find a compact set of key dates where adding an additional date does not improve the information coverage.
We demonstrate that our approach is simple and effective, allowing one to automatically build a flexible TLS system to determine an appropriate timeline length across topics automatically. 




We apply our approach\footnote{Code and data available at: [\emph{url redacted for blind review}].} to three real-life open TLS datasets of English articles~\cite{10.1145/2487788.2487829,tran-etal-2015-joint,gholipour-ghalandari-ifrim-2020-examining}. 
To showcase our scheme's generalization ability, we also construct a new Chinese TLS dataset and evaluate our scheme on it. We compared our approach to two representatives TLS methods propsed in ~\cite{gholipour-ghalandari-ifrim-2020-examining}. We consider two commonly used TLS metrics~\cite{martschat-markert-2017-improving}: the Align-based Rouge F1-score and the Date F1-score. Experimental results show that our approach delivers comparable and even better TLS performance compared to prior methods that use expert-supplied TLS length settings. However, it achieves this without expert involvement.


This paper makes the following contributions:
\begin{itemize}[leftmargin=*]
  \item It is the first to target the automatic selection of key dates for TLS systems;
  \item It is the first to employ the elbow method to address the constraint selection problem for TLS systems;
  \item It introduces and provides a new Chinese TLS dataset (that will be open-sourced upon acceptance), filling the language gap offered by existing TLS datasets. 
\end{itemize}






\section{Related works}


\citet{10.1145/345508.345546} firstly proposed a timeline system and introduced the task of TLS  \cite{10.1145/383952.383954}. TLS has received considerable attention in recent years\cite{10.1145/1008992.1009065,10.5555/2145432.2145483,10.1145/2009916.2010016,kessler-etal-2012-finding,10.1145/2487788.2487829,article,li-li-2013-evolutionary,wang-etal-2015-socially,tran2015timeline,tran-etal-2015-joint,wang-etal-2016-low,martschat-markert-2018-temporally,steen-markert-2019-abstractive,gholipour-ghalandari-ifrim-2020-examining}. 
Submodular methods are another kind of popular TLS solution besides the ranking methods mentioned before. By defining an optimism function, these methods select sentences greedily and organize them to a timeline summary\cite{tran2015timeline,martschat-markert-2018-temporally}.   \citet{martschat-markert-2018-temporally} discuss important constraints selection and give a theoretical method to achieve budgeted maximization of submodular functions according to   \citet{10.5555/1857999.1858133}. 
However, existing approaches use a fixed timeline length for TLS or relying on expert involvement to determine the parameters. Our approach advances prior works by developing a new approach to determine the timeline length automatically. 







