2.1 Discourse segmentation

Language does not normally consist of isolated unrelated sentences, but rather semantically related groups of sentences. These groups are referred as discourses. Within a discourse, the whole information conveyed is more than the sum of its separate parts. In fact, patterns formed by consecutive sentences are informative too. These patterns are called discourse structure. Algorithms that recognize and analyze various aspects of discourse structure can be categorized into three separate layers (Webber, Egg and Kordoni 2012): linear discourse segmentation which aims to segment a document into a linear sequence of topically or functionally coherent parts, discourse chunking which refers to recognizing discourse relations between sentences such as explanation, elaboration, result, etc. (Lascarides and Asher Reference Lascarides and Asher1993), and discourse parsing which resembles sentence level parsing in an attempt to construct a complete structured cover of a text (Grosz and Sidner Reference Grosz and Sidner1986; Mann and Thompson Reference Mann and Thompson1988).

In this article, we focus on linear segmentation of a meeting transcription. Generally speaking, a document can be segmented from two distinct perspectives: topics and functions. Topic segmentation tries to automatically divide the document into shorter topically coherent segments.Footnote ¹ The task of topic segmentation has been approached in many different ways. There are two basic insights that most of them use (Purver Reference Purver2011):

• Changes in content: If we look at a discussion containing various topical segments, we might see that vocabulary being used in each segment differs dramatically from those used in other topically different segments. Many approaches are based on this idea and try to track the changes of lexical similarity between adjacent parts of the text and assign boundaries wherever this change is higher than a predefined threshold. TextTiling (Hearst Reference Hearst1997) and LCSeg (Galley et al. Reference Galley, McKeown, Fosler-Lussier and Jing2003) are two well-known methods in this category.

• Distinctive boundary feature: Boundaries themselves have their own characteristics which can be detected accordingly. For example, speakers use specific words, phrases, and even acoustic cues, called discourse markers, to signal topic changes to their audience. It has been shown that these cue phrases can be used to structure the given discourse (Grosz and Sidner Reference Grosz and Sidner1986; Hirschberg and Litman Reference Hirschberg and Litman1993).

A comprehensive study of topic segmentation approaches can be found in Purver (Reference Purver2011).

It has been shown that LCSeg has competitive performance in the meeting segmentation task (Hsueh, Moore and Renals Reference Hsueh, Moore and Renals2006; Purver Reference Purver2011). However, it has certain weaknesses in the field of asynchronous conversations where topics are interleaved and do not change sequentially in the order of sentences. Joty, Carenini and Ng (Reference Joty, Carenini and Ng2014) proposed extensions of this algorithm, using a feature in the surface form of asynchronous conversations, which is quoted sentences. However, this feature cannot be extracted from meeting transcripts and is not applicable in our problem.

From a distinct perspective, we can segment a document into functionally coherent parts. Differences between this kind of segmentation and topic segmentation can be well understood with an example. Suppose we have to segment a meeting transcript into shorter parts. We have two ways of doing so. The first one is to segment the transcript according to items in the meeting agenda (topic segmentation). In the second approach, we can segment the transcript into separate activities such as discussions between all or some of the participants, monologues or presentations. This kind of segmentation is called function segmentation (Webber et al. Reference Webber, Egg and Kordoni2012).

Much of previous work on function segmentation has been performed for the genre of scientific articles, where the goal is to segment the given article into Introduction, Methods, Results, and Discussion parts (McKnight and Srinivasan Reference McKnight and Srinivasan2003; Hirohata et al. Reference Hirohata, Okazaki, Ananiadou, Ishizuka and Biocentre2008). One of the earliest work on function segmentation in the meeting domain is McCowan et al. (Reference McCowan, Bengio, Gatica-Perez, Lathoud, Monay, Moore, Wellner and Bourlard2003), which tried to recognize group actions in a given meeting transcript using an HMM-based approach. The actions to be recognized are monologue, presentation, white board, discussion, consensus, and note-taking. Similar sets of segments have been used in other studies, with segments named group actions, phases or meeting events (Dielmann and Renals Reference Dielmann and Renals2004; Zhang et al. Reference Zhang, Gatica-Perez and Bengio2005; Reiter, Schuller and Rigoll Reference Reiter, Schuller and Rigoll2007). All of the previous methods used supervised approaches in order to detect the category of each utterance. Various statistical models have also been trained and tested, such as dynamic Bayesian network (Dielmann and Renals Reference Dielmann and Renals2004), information fusion using multiple classifiers (support vector machines, Bayesian network, Gaussian mixture model, multilayer perceptron network, and radial basis network) (Reiter and Rigoll Reference Reiter and Rigoll2004), combination of recurrent neural network and HMM (Reiter, Schuller and Rigoll Reference Reiter, Schuller and Rigoll2006), two-layer HMM (Zhang et al. Reference Zhang, Gatica-Perez, Bengio, McCowan and Lathoud2004) and hidden conditional random fields (Reiter et al. Reference Reiter, Schuller and Rigoll2007). The main problem with these approaches is that they need an annotated training set to train the underlying models. In this paper, we propose an unsupervised function segmentation algorithm.

2.2 Speech summarization

We categorize speech summarization methods into five distinct categories according to the main idea behind these methods and briefly describe themFootnote ². A comprehensive study of speech summarization methods can be found in Liu and Hakkani-Tür (Reference Liu and Hakkani-Tür2011).

• Maximum Marginal Relevance (MMR) (Carbonell and Goldstein Reference Carbonell and Goldstein1998): The main idea in this approach (and all others which are an extension of that) is to find an extractive summary consisting of utterances which are most similar to the document and least similar to the ones extracted in the summary. This algorithm is iterative and based on a query. In each iteration, an utterance is selected that is most relevant to that query and the least redundant according to utterances extracted up to that point. Relevancy and redundancy are estimated according to certain similarity measures such as cosine similarity. This algorithm is generalized to generic (query-independent) summarization (Zechner Reference Zechner2002a) in which the score of utterance i at iteration k is calculated as (1):

  (1) \begin{equation} MMR\big (S_{i}^{k}\big)=\lambda *Sim_{1}(S_{i},D)-(1-\lambda)*Sim_{2}(S_{i},Summ^{k-1}), \end{equation}
  where D is the document vector and Summ ^{k − 1} represents the utterances that have been selected up to iteration k. The first part of (1) measures how important the utterance is according to its resemblance to the whole document. The second part measures how redundant the sentence is based on its similarity to the extracted summary so far. Parameter λ is a tradeoff factor between importance and redundancy. Higher values for λ give more weight to more important utterances and lower values give more weight to non-redundant content.

  MMR has been widely used as a competitive baseline in speech summarization (Murray et al. Reference Murray, Renals, Carletta and Moore2005). Various similarity measures and term weighting methods have been also tested and reported in the literature (Xie and Liu Reference Xie and Liu2008).

• Approaches based on topic modeling: The main idea here is to find the underlying topic of the meeting and then extract the utterances which cover most of these topics. These approaches are based on the topic representation of documents. Several topic modeling methods exist in the literature such as latent sementic analysis (LSA) (Deerwester et al. Reference Deerwester, Dumais, Landauer, Furnas and Harshman1990), probabilistic latent semantic indexing (Hofmann Reference Hofmann1999), and latent dirichlet allocation (Blei, Ng and Jordan Reference Blei, Ng and Jordan2003). These methods assume that words close in meaning occur in similar context. Unlike similarity measures that only rely on word overlap, these methods represent words in a latent semantic space and thus yield a better measure of word and document similarity. Various topic modeling approaches have been evaluated for summarization, such as using LSA (Murray et al. Reference Murray, Renals, Carletta and Moore2005) and PLSI (Kong and Lee Reference Kong and Lee2006).

• Graph-based approaches: The idea in these methods is that the most important utterances are similar to other most important ones. In order to extract these relations, they build a graph whose nodes are utterances in the document and edges represent similarity between nodes. Utterances are scored according to the corresponding edges and scores of their neighbor utterances. Inspired by Google’s PageRank algorithm (Brin and Page Reference Brin and Page1998), a random-walk procedure is applied to the constructed graph to compute the final score of each utterance (Erkan and Radev Reference Erkan and Radev2004; Garg et al. Reference Garg, Favre, Riedhammer and Hakkani-Tür2009; Chen and Metze Reference Chen and Metze2012). Graph-based summarization methods have been shown to be very effective (Liu and Hakkani-Tür Reference Liu and Hakkani-Tür2011).

  The summarization algorithm we use in this paper (described in Section 5) belongs to this category. We also compare our approach to two other graph-based methods. One is ClusterRank (Garg et al. Reference Garg, Favre, Riedhammer and Hakkani-Tür2009). In this method, adjacent utterances are clustered according to their similarity values. A graph is then created where nodes are constructed clusters and edges are similarity values between these clusters. Then the random-walk procedure is applied to this graph to score each cluster. Afterwards, each utterance is scored according to its associated cluster score and the similarity between the utterance and the cluster. The other one constructs a two-layer graph (Chen and Metze Reference Chen and Metze2012). This algorithm uses speakers’ information in order to score each utterance. Utterances and speakers are represented as nodes in the utterance layer and speaker layer of the graph, respectively. Using this graph, scores from different layers are reinforced so that the final utterance scores are influenced by similar utterances as well as utterances from the same speaker.

• Optimization-based approaches: The main idea in the methods in this category is to define a scoring mechanism for the extracted summaries and find the optimum point using an optimization method. These methods rely on concepts and employ optimization algorithms. They try to detect concepts in documents using simple heuristic approaches, for example, n-grams that occur more than a pre-defined threshold (Gillick et al. Reference Gillick, Riedhammer, Favre and Hakkani-Tur2009). After detecting these concepts, an optimization algorithm such as integer linear programming is used to select utterances to maximize the concepts covered in the summary, under the summary length constraint (Gillick et al. Reference Gillick, Riedhammer, Favre and Hakkani-Tur2009; Xie et al. Reference Xie, Favre, Hakkani-Tür and Liu2009; Riedhammer et al. Reference Riedhammer, Favre and Hakkani-Tür2010).

• Supervised approaches: All methods described above are unsupervised in the sense that they need no data to learn their model parameters. Summarization can be viewed as a binary classification task that aims to determine whether an utterance is important and must be included in the summary or not. Utterances can be represented by a set of features. A binary classifier is trained using labeled training data, and then used to classify test utterances as being important or not. A variety of features have been investigated for the task of summarization such as utterance length, weight, position, cue words, prosodic features, etc. (Zhang and Fung Reference Zhang and Fung2007; Banerjee and Rudnicky Reference Banerjee and Rudnicky2008; Murray and Carenini Reference Murray and Carenini2008; Xie et al. Reference Xie, Liu and Lin2008). Various classifiers are experimented such as Bayesian networks, maximum entropy, hidden Markov models, conditional random fields, and support vector machines (Maskey and Hirschberg Reference Maskey and Hirschberg2003; Buist et al. Reference Buist, Kraaij and Raaijmakers2004; Galley Reference Galley2006; Maskey and Hirschberg Reference Maskey and Hirschberg2006; Zhang and Fung Reference Zhang and Fung2007; Xie and Liu Reference Xie and Liu2010; Mehdad et al. Reference Mehdad, Carenini, Tompa and NG2013). The main drawback of these approaches is that they need a labeled training set. Obtaining such data is a time-consuming, expensive, and error-prone process, requiring trained human annotators and substantial amounts of supervision.

Different information sources have been used in the above summarization methods, ranging from simple surface words and sentence length to speaker and prosodic information. One important information source is discourse structure. While simple discourse features, such as utterance position or existence of specific cue words, are extensively used in the literature (Maskey and Hirschberg Reference Maskey and Hirschberg2003, Reference Maskey and Hirschberg2005; Murray et al. Reference Murray, Renals, Carletta and Moore2006), more complicated aspects of this kind of information are more or less neglected in previous work.

As discussed in Section 2.1, there are various layers of discourse analysis methods. The first layer is linear segmentation of the document into functionally or topically coherent parts. As stated above, topic information has been extensively used in previous work to calculate salience scores of the utterances. Explicit topic segmentation of the input document and its influence on summarization have also been studied in the literature. Oya et al. (2014) used a topic segmentation algorithm to detect various topics of the input meeting and then created a summary in a manner that covers all these topics. However, function segmentation and its influence on the summarization task have not been studied yet, which is the focus of this article.

The second layer of discourse analysis is extracting the relation between sentences in the document. One such information is rhetorical structure (Mann and Thompson Reference Mann and Thompson1988), which can be regarded as the story flow or sequence that might exist between the sentences of a document. It has been shown that effective extracting and modeling of this structure of the input document can improve the summarization task in both text (Marcu Reference Marcu1998; Fung and Ngai Reference Fung and Ngai2006) and spoken documents (Zhang, Chan and Fung Reference Zhang, Chan and Fung2007; Zhang and Fung Reference Zhang and Fung2012). Our study is similar to these that try to leverage discourse information for summarization.

4.1 General overview of genetic algorithms

Genetic algorithms can be considered as searching through the space of possible solutions to a given problem. This search process starts with an initial population considered as the first generation. Individuals in each generation are different solutions of the problem. The first step to define a genetic algorithm for a problem is to define the way in which the solutions are represented in the algorithm and converted to individuals. These individuals are then scored according to a function called fitness function. This function aims to evaluate the suitability of each individual to be the final solution of the problem. The best individuals are qualified to enter the next generation according to a specified selection operator. However, in order to search other parts of the space, qualified individuals are altered before entering the next generation according to certain reproduction operators. This whole process is iterated until a stopping condition is met. The best individual in the final generation is returned by the algorithm as the final solution of the problem. A comprehensive study of these algorithms can be found in Eiben and Smith (Reference Eiben and Smith2003). In the following subsections, we explain these components for the function segmentation problem in more details.

4.2 Problem representation

The input to our algorithm is a sequence of speaker ids of utterances. For example, sequence 111213. . . indicates that the first three utterances are uttered by speaker 1, the fourth one is uttered by speaker 2, and so on. The output of the algorithm is a segmentation of the meeting into parts in a way that each part’s class differs from the previous and the next one according to our defined categories. We represent each segmentation result as a binary vector whose length is identical to the input sequence. In this vector, 1 indicates that the corresponding utterance starts a new segment. All other values are 0. Individuals in each generation in the genetic algorithm indicate various segmentations of the given sequence. These individuals are evolved according to defined operators. An example is shown in Figure 3.

Fig. 3.

(a) Sample sequence of speaker id’s for a fictitious meeting with 3 participants and 20 utterances. (b) Sample segmentation of the given sequence (a). This segmentation contains three separate segments which start at positions 1, 7, and 16.

4.3 Fitness function

The most important part of a genetic algorithm is its fitness function. This function must be defined in a way to have a good correlation with the ultimate evaluation criterion. We first introduce some definitions used in our algorithm. For each segment s, we define its speakers’ distribution dist(s) which is a vector with elements denoting the fraction of utterances spoken by each speaker in that segment. We also define a unique distribution for each category, in which all the corresponding participants are equally involved (having the same number of utterances). This is referred to as the reference distribution of category cat in a meeting with M participants, dist_ref(M, cat). Figure 4 shows a sample sequence s, its distribution (dist(s)) and dist_ref for two sample categories, namely Monologue ₂ and Discussion ₁₀₁₀.

Fig. 4.

Example of dist, dist_ref for a sample segment.

The idea behind our proposed algorithm is to create a segmentation consisting of segments whose distributions are more similar to the reference distributions. As an example, the sequence shown in Figure 3(a) is segmented into three segments, s ₁, s ₂, and s ₃, respectively. It can be seen that s ₁ is similar to the reference distribution of category Discussion ₀₁₁ (dist_ref(3, Discussion ₀₁₁)). s ₂ and s ₃ are similar to dist_ref(3, Discussion ₁₀₁) and dist_ref(3, Monologue ₂), respectively.

The fitness value for each individual S with n_s number of segments is computed according to (2).

(2) \begin{equation} Fitness(S)= \frac{\sum _{i=1}^{n_s}{score_{seg}(i)*length_{seg}(i)}}{length(S)} \end{equation}

where score_seg(i) and length_seg(i) denote the computed score and number of utterances for the ith segment within S, respectively. This value is normalized according to the number of elements in the given sequence, length(S)Footnote ⁴. Fitness(S) can be considered as an average score for each element in the speakers sequence according to a specific segmentation S.

Now the problem is reduced to design a scoring mechanism for each segment. In order to calculate the score for a segment, we divide the segment into smaller parts each with length k. In this work, we set k to be twice the number of participants in the meeting. The score for a sample segment s is:

(3) \begin{equation} score_{seg}(s)=\frac{1}{L-k}\min _{cat\in C}\sum _{i=1}^{L-k}\lbrace KL(dist(s(i:i+k)),dist_{ref}(N_s, cat))\rbrace, \end{equation}

where L is the number of elements in the input segment s and N_s is the number of participants in the meeting. s(i: i + k) is the subsegment of s with length k starting from index i. C is the list of categories defined at the beginning of this section (Monologue_i and Discussion _{x 1, . . ., xn}). KL(P, Q) is the Kullback–Leibler distance metric (Kullback and Leibler Reference Kullback and Leibler1951) between two distributions:

(4) \begin{equation} KL(P,Q)=\sum _{i}\,{\rm ln}\left(\frac{P(i)}{Q(i)}\right)P(i). \end{equation}

Note that better segmentations result in lower fitness values. The reason behind dividing a segment into subsegments in (3) is to avoid having large segments that as a whole are similar to a reference distribution, but sub-regions have different distributions (e.g., sequence 111. . .1222. . .2333. . .3 as one segment versus three separate segments). The effectiveness of this fitness function is studied later in Section 6 and its correlation with the final evaluation metric is shown in Figure 6.

4.4 Exploration operators

Generally speaking, there are three kinds of operators which are used in a genetic algorithm: Parent selection, Crossover, and Mutation. Here we describe our chosen operators briefly.

4.4.1 Parent selection

We use the proportional algorithm proposed by Holland (Reference Holland1975) which biases the selection towards the fittest individuals. Since our problem is a minimization one, we use (5) to compute the probability of selecting individual x in generation i.

(5) \begin{equation} P_i(x)=\frac{\sum _{y \in Gen_i}1+Fitness(y)-Fitness_{min}^{i}}{1+Fitness(x)-Fitness_{min}^{i}} \end{equation}

where Fitnessⁱ_min is the minimum observed fitness up to generation i (Gen_i).

4.4.2 Crossover

When selecting two individuals (candidate segmentations) from the current generation, the crossover operator is applied to produce an offspring for the next generation. As said before, here we assume that we know the number of segments Num_Seg. So we have exactly Num_Seg boundaries (denoted by 1) in each individual. We limit the offspring to have the same number of boundaries. We select these boundaries in two steps.

1. (1) Boundaries that are common in two parents are transferred to offspring.

2. (2) The remaining needed boundaries are selected randomly from the two parents.

Mutation: We randomly choose one boundary and change its position in the offspring.

An example of applying these operators is depicted in Figure 5. In this figure, we assume that each individual has exactly four boundaries. The crossover operator’s result is shown in Figure 5(a). This operator first transfers the common boundaries in two parents (position 1, 10) and then chooses the remaining needed boundaries randomly (position 7, 14 which are selected from the first and second parent, respectively). The mutation operator is shown in Figure 5(b). This operator randomly changes the position of an arbitrary boundary (boundary at position 7 is transferred to position 5).

Fig. 5.

Examples of applying crossover (a) and mutation (b) operators on two selected parents P ₁ and P ₂.

4.5 Stopping condition

There are various stopping conditions proposed in the literature (Engelbrecht Reference Engelbrecht2007). We monitor the best individual in each generation and terminate the algorithm when no improvement is observed over a number of consecutive generations.

4.6 Additional features

We use two optional features in our genetic algorithm in order to improve its effectiveness:

1. (1) We use Elitism which refers to the process of ensuring that the best individuals of the current population survive to the next generation. We select R_eli percent of the population that achieve best fitnesses and copy them to the new population without any changes. The remaining individuals are generated using exploration operators illustrated in Section 4.4.

2. (2) Premature convergence is a phenomenon that occurs when a population for an optimization problem converges too early, resulting in a suboptimal answer. In order to prevent this problem, we use Fitness sharing that is originally introduced as a population diversity maintenance technique and increases the exploration capability of the algorithm (Goldberg and Richardson Reference Goldberg and Richardson1987). In order to measure distances between individuals, we use Edit distance formulated by Levenshtein (Reference Levenshtein1966), which is a popular method for measuring the difference between two strings. In this framework, we consider segmentation vectors as binary strings and use (6) to compute the final fitness value for each individual x in the ith generation Gen_i.

   (6) \begin{equation} f_i(x)=\frac{|Gen_i|*Fitness(x)}{\sum _{y \in Gen_i}Edit\_Distance(x,y)} \end{equation}
   Fitness(x) is calculated according to (2) and |Gen_i| denotes the population size.

4.7 Complete algorithm

The complete algorithm is shown in Algorithm 1. In this algorithm, U(0, 1) is a function which generates random numbers ranging between 0 and 1. ρ_c and ρ_m are crossover and mutation rate, respectively. Typically very low values for ρ_m and relatively high values for ρ_c are recommended. We set ρ_m and ρ_c to be 0.1 and 0.9, respectively. All the other parts of the algorithm were explained before.

Algorithm 1

Genetic algorithm for function segmentation of a meeting with known number of segments

4.8 Estimating of the number of segments

So far we have assumed that the number of segments is known and solve the segmentation problem of segmentation accordingly. However this is a very restrictive assumption which is not true in reality. Here we propose a heuristic method in order to estimate the number of segments in a given sequence. We use speakers’ distributions defined in Section 4.3 in a greedy framework and try to detect various parts of the sequence where these distributions change. In this approach, we generate a base segmentation and merge consecutive segments until the Kullback–Leibler distance (Kullback and Leibler Reference Kullback and Leibler1951) between the merged segment and the original one exceeds a predefined threshold. The complete algorithm is shown in Algorithm 2. This algorithm has two parameters. Parameter T is used to generate the initial segmentation in which the input sequence is segmented into equal T length parts. TH_cu is the threshold we use to merge consecutive segments. In this work, we consider T and TH_cu to be 5 and 0.22, respectively. We use the number of segments in the output segmentation in order to use the genetic algorithm to segment the sequence functionally.

Algorithm 2

Heuristic function segmentation

The output segmentation from this heuristic algorithm is used by our genetic algorithm in two ways: the number of segments in this segmentation is used as the estimated number of segments (Num_seg in Algorithm 1). The output itself is included in the initial population of our genetic algorithm. This heuristic method together with random segmentation act as the baselines to which we compare our genetic function segmentation results.

5.1 Segment score

In the first step, graph G is constructed in which each segment is represented as a node and directed edges between nodes are weighted according to their similarity. We treat each segment as a bag of words and use the normalized cosine similarity measure:

(7) \begin{equation} weight_{edge}(X,Y)=\frac{cosine(X,Y)}{\sum _{Z}cosine(X,Z)} \end{equation}

where cosine(X, Y) is computed according to (8).

(8) \begin{equation} cosine(X,Y)=\frac{\sum _{w \in X, Y}tfidf(X,w)*tfidf(Y,w)}{\sqrt{\sum _{w_x \in X}tfidf(X,w_x)^2} \sqrt{\sum _{w_y \in Y}tfidf(Y,w_y)^2}} \end{equation}

tfidf(X, w) is the term weight for word w in segment X. It is the product of term frequency of w in X and the inverse document frequency (inverse of the number of all segments containing w). We apply the random-walk process on G to compute the salience score for each segment. Specifically, (9) is used iteratively to compute each segment’s score.

(9) \begin{equation} P(u)=\frac{d}{N} + (1-d)\sum _{v \in adj(u)}weight_{edge}(u,v)*P(v), \end{equation}

where P is a vector whose elements are the salience scores for the segments. d is damping factor that is typically chosen in the interval [0.1, 0.2] and ensures convergence (Erkan and Radev Reference Erkan and Radev2004). u and v are two nodes of G and adj(u) denotes the nodes that are adjacent to u in graph G. Vector P can be chosen randomly at first and (9) is then iteratively applied until a stopping criterion is met (e.g., change of vector P is less than a predefined threshold ε).

5.2 Sentence scoring

Next, we compute the utterance scores by leveraging the segment scores. Similar to previous work (Garg et al. Reference Garg, Favre, Riedhammer and Hakkani-Tür2009), the score for an utterance U is its importance score in the associated segment S (computed using the cosine similarity between U and S), weighted by the segment score, that is,

(10) \begin{equation} score(U)=cosine(U,S)*P(S), \end{equation}

where P is the segment score vector, computed according to (9).

5.3 Summary sentence selection

After we obtain the salience score for each utterance, the last step is to select summary sentences. One simple approach would be just selecting the top ranked n sentences. However, redundancy may exist among them. Because of the spontaneous nature of the uttered sentences in a meeting, there may be many utterances resembling to each other. For example, this can occur when a speaker wants to emphasize a previously uttered sentence, or asks a question about a certain previous subject using the same wording. Our algorithm, like all other summarization algorithms, mainly depends on the words used in the utterance. Therefore, two utterances with the same wording get similar scores using the scoring algorithm described earlier. To avoid selecting similar sentences, we use a re-ranking algorithm to decrease the score of an utterance according to its similarity to its above ranked ones. Suppose that U_i is the ith ranked utterance according to the above scoring algorithm. The new score for this utterance is calculated with respect to all the above utterances in the ranked list according to (11).

(11) \begin{equation} new\_score(U_i)=score(U_i)-\lambda *\sum _{j=1}^{i-1}\left(\frac{cosine(U_i,U_j)}{Length(U_j)}\right). \end{equation}

In this equation, score(U_i) is the previous calculated score as illustrated in (10), cosine(U_i, U_j) is the cosine similarity between two utterances (8), Length(U_j) is the number of words in the utterance j, and λ is a parameter which controls the degree of redundancy in the output summary. We set λ to be 0.1 in this work. Using these new scores, the chance of selecting similar utterances is reduced. For the final summary, we greedily select the top ranked sentences.

6.1 AMI meeting corpus

The AMI meeting corpus (Carletta et al. Reference Carletta2006) is a multi-modal data set consisting of 100 hours of meeting recordings. This corpus includes speech audio, transcripts, and human extractive summaries. There are both scenario-based and non-scenario (naturally occurring) meetings. In order to test the whole proposed summarization algorithm, we use the scenario portion of the corpus in which the participants play different roles to discuss various aspects of designing a remote control. While the scenario given to participants is artificial, the speech, actions and decisions are completely spontaneous and natural. There are four different roles assigned to participants: project manager, Marketing expert, User interface designer, and Industrial designer. Project manager runs the meetings, produces and distributes minutes, and produces a report at the end of the trial. These reports are then used by annotators to determine the reference extracted summary for each meeting. They mark dialog acts that support material in the project manager’s reports. There are other annotations that are available in this corpus, such as topic segmentation, head and hand gestures, location of individuals, focus of attention, etc. For each group of participants, there are four phases with different goals: project kick-off consisting of getting familiar with each other and the task; Functional design in which user requirement, the technical functionality and the working design are set; Conceptual design in which the conceptual specification for the component is determined; Detailed design which finalize the product and evaluate the result. Each phase is prepared as a separate meeting in the corpus with the same ID. There is a total of 137 meetings in this corpus where reference extracted summaries are prepared.

In order to evaluate the effectiveness of our proposed segmentation algorithm, a subset of the meetings in the AMI corpus were manually annotated and used as our test set. It contains 11 meetings with these ids: es2008a, is1000a, is1001a, is1001b, is1001c, is1003b, is1006b, is1008a, is1008b, is1008c, and ts3005a. We chose these meetings since they have more annotations (such as focus of attention and addressee information) in the AMI corpus, which can be useful for our future work. We employed graduate students as annotators and asked them to segment the meetings according to their different events. They were given a guideline which includes the task definition and various examples used to clarify the concept of events and function segmentation of a meeting. Each meeting was annotated by one annotator. One special trained annotator then checked and finalized the annotations. The last annotated meeting (ts3005a) was used as our development set on which we tuned the parameter TH_cu of the heuristic algorithm.

To evaluate the whole summarization algorithm, we use 20 meetings in these series: ES2004, ES2014, IS1009, TS3003, and TS3007. For each meeting, 3 human generated reference extracted summaries are prepared in the corpus. Theses extractive summaries have no unique compression ratio.

6.2 Function segmentation evaluation

6.2.1 Evaluation metric

There are various segmentation evaluation metrics proposed in the literature (Pevzner and Hearst Reference Pevzner and Hearst2002; Georgescul, Clark and Armstrong Reference Georgescul, Clark and Armstrong2009). We use P_k (Beeferman, Berger and Lafferty Reference Beeferman, Berger and Lafferty1999), which is the most widely used metric for segmentation evaluation. Given two points in a sequence, P_k specifies the probability of segmentation error, which is the average probability that the segmenter’s decision is incorrect. Note that P_k is a measure of error and thus a lower score means better segmentation performance. The formula for P_k is shown in (12).

(12) \begin{equation} P_k=\frac{\sum _{i=1}^{N-k}\delta _H(i,i+k)\oplus \delta _R(i,i+k)}{N-k} \end{equation}

where H is the system generated segmentation and R is the reference segmentation. Given a segmentation S, δ_S(i, j) is a function which outputs 1 if and only if segmentation S assigns ith and jth element to the same segment. The choice of k is arbitrary, but is generally set to be half of the average segment length in the reference segmentation. This value ensures that under some assumptions four obvious baseline algorithms (hypothesizing no boundaries, boundaries everywhere, evenly spaced boundaries, or randomly spaced boundaries) all have P_k = 0.5 (Purver Reference Purver2011). For our evaluation process, we use the same choice for k.

6.2.2 Results

First we evaluate the effectiveness of our proposed fitness function (in (2) and (3)), by measuring its correlation with the evaluation metric P_k. We compute P_k and the fitness value for thousands of various kinds of segmentations. For each fitness value, the associated P_ks are averaged. Results are shown in Figure 6. As shown in this figure, there is a good correlation between these measures. Hence, we expect that a genetic algorithm that minimizes this fitness value will minimize the ultimate evaluation metric and thus will improve the segmentation.

Fig. 6.

Correlation between our designed fitness function and ultimate evaluation metric P_k.

Results of applying different segmentation algorithms on the test set are shown in Table 1. Since there is no prior work that is completely comparable to ours, we compare our algorithm with two baseline algorithms: random segmentation and the heuristic approach shown in Algorithm 2. We can see that our algorithm achieves the best performance. When the number of segments is automatically determined, there is a performance degradation compared to using the reference number of segments, which is expected. Table 1 shows that running the genetic algorithm improves results upon the initial condition, which is the output from the heuristic segmentation algorithm.

Table 1.

Results of our proposed genetic algorithm (GBS) compared to random segmentation and the simple heuristic method introduced in Algorithm 2

We also examine the effect of the approximation used in the genetic algorithm. Using the same scoring function for a segment (3), a dynamic programming algorithm can be used to find the exact solution in polynomial time. Specifically we define score_best(i, k) to be the score of the best found segmentation for the first i elements of the given sequence using k segments. We can define the recursive formula as (13):

(13) \begin{equation} score_{best}(i,k) = \min _{j<i}\lbrace score_{best}(j,k-1)+score_{seg}(j+1:i)\rbrace, \end{equation}

where score_seg(j + 1: i) is the score of the subsequence j + 1 to i to be considered as one segment according to (3). We also store the best j to backtrack to find the optimal path.

The initialization can be done using the (14):

(14) \begin{equation} score_{best}(i,1) = score_{seg}(1:i) \forall i \le L, \end{equation}

where L is the number of elements in the given sequence.

Initializing with (14) and then iteratively applying (13), we can reach to score_best (L, Num_seg) which is the score of the best found segmentation according to the defined score function. Experimental results show that the performance of this exact solution on the same test set is 0.31, assuming that the number of boundaries is known in advance. However, the computation cost of this approach is much higher than the genetic algorithm. If we consider the most time-consuming function in these approaches to be the calculation of score_seg (3), in the dynamic programming approach, the number of times that this function is called is O(Num_seg*L ²) where Num_seg is the number of segments and L is the length of the sequence (the average value for L in our test set is 610). However, this number in the genetic algorithm is O(Num_seg*N*Num_iter) where N is the population size (which is considered to be 20 in our experiments) and Num_iter is the number of iterations (which is typically less than 100). As a real example, for an input sequence with 600 elements on a system with core i7 CPU and 4 Gig RAM, the rough time to complete the genetic algorithm is around 30 seconds. But the dynamic programming algorithm takes around 20 minutes to complete the task.

Figure 7 shows the results of applying the genetic algorithm on a sample meeting (es2008a). Figure 7(a) shows the boundaries found by our proposed algorithm (dashed lines) and the reference boundaries (solid lines). It can be seen that the algorithm succeeds in finding most of the boundaries.

Fig. 7.

Results of applying the segmentation algorithm on the sample meeting es2008a: (a) Location of found boundaries (dashed line) in comparison with the reference boundaries (solid line). (b) Results (mean P_k and mean fitness) over generations.

Figure 7(a) shows how the results change over generations in the genetic algorithm. In this figure, the x axis is the generation number and the y axis is the average score obtained by either the evaluation metric (P_k) or the fitness function defined in (2) for top five best individuals in each generation. From this figure, it can be seen that in general, P_k values of the best individuals decrease, which implies that better solutions are achieved in consecutive generations. After around 110 iterations, there is no more significant improvement of the segmentations found by the algorithm according to both the fitness value and P_k.

We also evaluate the performance of the heuristic algorithm in estimating the number of segments in the reference segmentation. We calculate the average difference between the hypothesized number of segments in the output of the heuristic algorithm and the actual one in the reference segmentation over the test set using different values for the parameter TH_cu. Figure 8 shows the result. As shown in this figure, the best prediction is achieved when TH_cu = 0.26. Note that we use TH_cu = 0.22 because we tune this parameter according to just one separate meeting.

Fig. 8.

The difference between predicted number of segments and the actual number in the reference segmentation according to various values for the heuristic algorithm’s parameter TH_cu.

6.3 Summarization evaluation

6.3.2 Results

We compare our proposed function-based summarization (FBS) with other baseline algorithms:

• • Length-Based: It is previously shown that the utterance length is the best feature for indicating summary sentences (Murray et al. Reference Murray, Renals, Carletta and Moore2006). In this simple approach, utterances are sorted according to their length and the best ones are extracted until the compression ratio is achieved.

• • ClusterRank (Garg et al. Reference Garg, Favre, Riedhammer and Hakkani-Tür2009): As explained in Section 5, our scoring mechanism is inspired by this algorithm.

• • MRRW-WBP (Chen and Metze Reference Chen and Metze2012): This is a state-of-the-art meeting summarization algorithm that shows an improvement over other baseline algorithms.

• • LSA (Gong and Liu Reference Gong and Liu2001), MMR (Carbonell and Goldstein Reference Carbonell and Goldstein1998): These are popular methods that are widely used as competitive baselines in the literature.

All these algorithms (except length-based which is an obvious approach) are reviewed in Section 2. We additionally compare our proposed algorithm with two other methods based on topic segmentation. We call them topic-based summarization (TBS). The summarization method is the same as our FBS algorithm. The only difference is in the way how the segmentation is done. The first one uses TextTiling algorithm (Hearst Reference Hearst1997), and the other one uses LCSeg algorithm (Galley et al. Reference Galley, McKeown, Fosler-Lussier and Jing2003).

For each meeting in the test set, an extractive summary is generated according to multiple compression ratios (6%, 10%, 20%). This generated summary is compared with the reference set in AMI meeting corpus. Results are shown in Table 2. These results show that our proposed method is superior to other methods according to most evaluation metrics and all compression ratios. As explained in Section 5, our scoring mechanism is inspired by the ClusterRank algorithm. So we consider this algorithm as our baseline and perform statistical significance test between it and our FBS. From these results, it can be seen that our proposed method improves over ClusterRank algorithm significantly. Even compared with MRRW-WBP, which had the best performance among previous works (Chen and Metze Reference Chen and Metze2012), our proposed approach outperforms it too according to most evaluation metrics. For different discourse segmentation methods, we can see that using our function segmentation yields better summarization performance than the topic-based segmentation methods.

Table 2.

Results of different summarization methods with Compression Ratio = 6%, 10%, and 20%. * denotes a significant improvement over the ClusterRank algorithm according to t-test at 95% confidence interval

6.3.3 Discussion

The major advantage of our proposed algorithm over other methods is its capability to detect local important utterances. The importance of these utterances is due to the context where they are used. An example is shown in Figure 9. In this figure, two utterances marked with arrows are detected only by our proposed algorithm. The similarity between these utterances and the whole document is not very much. Algorithms that calculate the score of each utterance according to its similarity to the whole document cannot detect them, instead our proposed algorithm segments the transcript and then calculates the score of each utterance according to its similarity to the corresponding segment. Because of their similarity to their associated segments, these local important utterances are detected by our algorithm to be included in the extracted summary.

Fig. 9.

A segment from meeting TS3007a which shows local important sentences that are detected by our proposed algorithm but not with the base-line algorithms

In the following, we show various errors resulted by our proposed summarization approach, categorized into four different groups. Note that many of these errors are not unique to our algorithm and they are also seen in almost all the other algorithms.

1. (1) Missing short summary utterances: Many errors are caused by short utterances. These short utterances are not informative by themselves, however their relation with other utterances makes them important. The following shows some examples. Each example is marked as important by the reference summary, but our proposed algorithm failed to detect and extract them into the summary.

   • • Uh this is the agenda for today.

   • • Uh there are three stages.

   • • You can guess what it is.

   There are also utterances that are not related to other important ones, but are just extracted for the sake of coherence in the reference extracted summary. Examples are listed below:

   • • Welcome at the kick-off meeting.

   • • uh and uh I think it’s very uh good to introduce uh yourself.

2. (2) Incorrect inclusion of utterances due to utterance scoring based on segmentation information: One feature of segmentation-based algorithms (like FBS and ClusterRank) is that they add a local perspective in order to decide the importance of an utterance. They consider the whole text to estimate scores for each segment (global view) and then they use a local view and estimate the importance of each utterance according to other utterances in the same segment. While this feature can be beneficial for detecting locally important utterances, it can cause another kind of errors, partly because spontaneous speech, repetition happens quite often – generally the wording of an utterance can influence the ones used for the upcoming utterances, which results in similar consecutive utterances. Below is such an example (the bold one is extracted by our proposed algorithm)

   • • what are we going uh to uh to do.

   • • What are we going to uh uh make f uh kind of functions in the remote.

   • • And why are we going to do it.

   This repetition will increase the score of utterances, because the similarity of these utterances to the whole segment will increase. However this is not necessarily indicative of importance. In the above example, the second utterance is extracted by our proposed algorithm, but is not marked as important in the reference summary.

3. (3) Missing important utterances because of the redundancy removal step: Another category of errors is made by the redundancy removal algorithm. Sometimes two utterances are similar to each other and are both in the reference summary. However, the redundancy removal algorithm detects them and decreases their scores. Consequently they may not be both extracted in the summary. An example is shown below:

   • • Um and as you uh may have heard the documents in the shared folder uh can be uh showed on this screen Not in y the My Documents.

   • • So if you wanna show something put it in the shared folder.

   In this example, both utterances are marked as important in the reference summary. However only the first one is extracted by the system and the second one will drop on the ranked list after applying the redundancy removal algorithm.

4. (4) Utterances with the same meaning but different surface form: There are some utterances that have the same meaning, but one of them is included in the reference summary and the other one is selected by our algorithm. An example is shown below:

   • • What you think might be uh a useful uh new feature.

   • • What uh what can distinguish our new trendy remote control from all the others.

   The first utterance is selected by the human annotator, and the second one is extracted by our algorithm. While they are not different in nature, this does have an impact on the system performance based on the currently used performance metrics.