A Context-Aware NLP Approach For Noteworthiness Detection in Cellphone Conversations

This papers presents a context-aware NLP approach to automatically detect noteworthy information in spontaneous mobile phone conversations. The proposed method uses a supervised modeling strategy which considers both features from the content of the conversation as well as contextual information from the call. We empirically analyze the predictive performance of features of different nature on a corpus of mobile phone conversations. The results of this study reveal that the context of the conversation plays a crucial role on boosting the predictive performance of the model.

Introduction
More than 6 billion people worldwide use their cellphones daily for a variety of purposes: contacting colleagues, relatives or friends, doing business, getting help in emergency situations, etc. Previous work (Carrascal et al., 2012) has shown that almost 40% of users frequently feel the need to recall bits of information from their phone conversations and that 27% of the users consider the recall task to be difficult, mainly because taking notes during a mobile phone call is not always possible (e.g. hands not free, lack of time or devices for note-taking). In a related user study, Cycyl et al. reveal that users are often engaged in concurrent tasks during mobile phone conversations (e.g. walking, jogging, driving, cooking, etc), which makes taking notes an unfeasible task (Cycil et al., 2013).
In this setting, information extraction techniques could be applied to automatically detect noteworthy information from mobile phone conversations. Related studies have focused on detecting noteworthiness from meeting transcripts (Banerjee and Rudnicky, 2009). However, very little work has been done to date to identify this kind of information in other types of human communication, such as spontaneous phone conversations.
In this paper, we present a data-driven information extraction approach aimed at automatically detecting fragments of phone conversations worth annotating for future recall, i.e. noteworthy. These call notes could then be presented to the users to enable fast browsing of their conversation history, and leveraged to design efficient information interaction techniques for supporting smart user interfaces.
Given the particular characteristics of mobile phone calls, detecting noteworthiness in them is challenging at many levels. First, the audio is captured in a natural environment rather than in controlled settings, which results in noisy signals, and consequently in noisy transcriptions. Second, the conversations are highly fragmented due to their spontaneous nature. Finally, at a conceptual level, judging which pieces of information are noteworthy is a very subjective task, as emerged in (Banerjee and Rudnicky, 2009), who investigated the feasibility of the task by conducting a Wizard of Oz-based user study.
Our noteworthiness modeling approach considers a supervised learning paradigm which takes into account two types of information: (1) Contextual information both from the call (where, when, to whom, . . . ) and the users (gender, age, . . . ); and (2) Content information of the conversation. The combination * * The work was conducted while the author was intern at Telefonica Research, Barcelona, Spain. This work is licenced under a Creative Commons Attribution 4.0 International License. Page numbers and proceedings footer are added by the organizers. License details: http://creativecommons.org/licenses/by/4.0/ of both sources of information enhances the flexibility of the model to accurately predict noteworthiness in different use scenarios.
The main contributions of this paper are: i) We propose and evaluate a supervised machine learning model to automatically detect noteworthy segments of phone conversations. Our approach adopts a hybrid strategy to model conversations exploiting both content and context-related information.
ii) We propose a new set of content and context-based features specifically designed to detect noteworthy information in our corpus of real-world cellphone conversations, and compare their effectiveness iii) We provide a discussion of the results, derived from our quantitative and qualitative analyses.
The paper is structured as follows. Relevant previous work is presented in Section 2. Section 3 describes the corpus of phone conversations and the annotations provided by the participants. In Section 4 we describe in-depth the extracted features. Our experimental validation and results are presented in Section 5. Finally, Section 6 summarizes our findings and highlights some lines of future research.

Related work
Noteworthiness detection in conversations can be considered to be a particular form of summarization: the aim is to summarize the conversation by keeping only the relevant pieces of information that the user would like to refer to at a later time. Although related, the main distinction between automatic summarization and detection of noteworthy information lays in the notion of relevance. The former aims at generating a comprehensive record of the conversation, while the latter considers only fragments worth registering for future recall.
Considerable research activity has recently been devoted to automatic text and speech summarization (Maskey and Hirschberg, 2003). Many approaches have been proposed in the literature, including cluster (Zhang et al., 2005) and graph-based methods (Garg et al., 2009;Wang and Liu, 2011) and machine learning techniques (Jian Zhang et al., 2007;Maskey and Hirschberg, 2006;Galley, 2006), where the task is tackled as a binary classification problem considering whether the sentence is a good candidate for a summary or not. In addition, different types of features have been used, including lexical, acoustic and structural characteristics (Xie et al., 2008;Maskey and Hirschberg, 2005). Recent works have been focused on adapting summarization to the social context, exploiting user generated contents associated with the documents Hu et al., 2012). Implicit and explicit community feedback in online collaborative websites have also been leveraged to detect highlights of media assets (San Pedro et al., 2009).
However, few studies have focused on noteworthiness detection. Banerjee et al. investigate the feasibility of discovering noteworthy pieces of information in meetings by means of a Wizard of Oz-based user study where a human suggested notes to meeting participants during the meeting. The authors found that the human annotator obtained a precision of 35% and a recall of 41.5%. In the same work, Banerjee et al. reports a low inter annotator agreement (IAA) in noteworthiness discovery. In a related work -probably the most relevant prior-art to our work, the authors apply extractive meeting summarization techniques to automatically detect noteworthy utterances in meetings (Banerjee and Rudnicky, 2008). They train a Decision Tree classifier over a collection of 5 meetings, obtaining an F-score of 0.14. This result highlights the difficulty of the task at hand and motivates to explore alternative approaches.
To overcome the difficulties posed by this task we propose two main contributions: 1) the use of novel features engineered ad-hoc for this task, and 2) the use of contextual information. While the former adapts the document representation to the specific problem setting, the latter allows to enhance the representation with orthogonal information which many times provides a higher discriminative power. This approach has been used successfully in related fields; for instance, in information retrieval tasks rich multimodal queries have been shown to effectively boost the retrieval performance compared to pure textual queries (Yeh et al., 2011).

Corpus Collection
We used a corpus of cellphone conversations collected in a previous study (Carrascal et al., 2012). In this study, a large sample of mobile phone conversations was recorded, semi-automatically transcribed 1 and manually annotated for relevance by their participants. Over 64 days, 796 mobile phone conversations from 62 volunteering subjects (20 female) were recorded. All the participants were Spanish native speakers, and the conversations were recorded and transcribed in Spanish. Metadata about the call (e.g. duration, date, time) was also stored along with the actual conversation and its transcript. More details about the corpus collection process can be found in (Carrascal et al., 2012).
All the participants were first asked to fill out a pre-study questionnaire where they provided some personal information, including gender, marital status, education and income. Then they were asked to annotate what parts of their calls that they would like to take a note of: i.e. noteworthy fragments of conversations. To this end, participants used a Web-based interface that gave them access to their calls and allowed them to highlight with the mouse the parts of the transcript that they considered to be worth keeping for future reference.
We used these annotations as the ground truth for the studies presented in this paper, considering them as the ideal noteworthy parts of the calls. For privacy reasons, due to the sensible nature of the data (i.e. private phone conversations) we could not consider alternative ground truth generation schemes, for instance collecting annotations from users other than the callers themselves. 2 Finally, the participants were asked to fill out a questionnaire after annotating each call, which was used to collect contextual information, including: location of the call (i.e at work, at home, while commuting, while doing shopping, while exercising), and category of the call (i.e. discuss a topic, taking an appointment, give/receive information, asking a favor, social).

Characteristics of the Corpus
The original conversation collection consists of a total of 796 conversations, of an average length of 178 seconds (s = 384 sec.). We pre-filtered this original set to exclude calls with problems in the transcript (e.g. empty transcript, only one speaker audible, etc). Out of the entire corpus we finally selected 659 conversations. We denote this subset of the corpus as the G dataset. The G dataset comprises 22, 474 turns, with an average of 34.10 (s = 45) turns per conversation. From these, only 671 are annotated as being noteworthy (2.98%), which represent an average of 1.02 turns (s = 1.803) per call. Given that the vast majority of turns (97.2%) are not annotated, this can be considered a highly unbalanced dataset, which makes the automatic modeling problem more challenging.
Hence, we considered a second dataset which included only the 295 calls from the G dataset containing at least one annotation. This second subset, denoted as A amounts for approximately 45% of the G dataset. The A dataset features 10, 642 turns, with an average of 36.07 (s = 33) turns per conversation. From these, again 671 (6.3%) are annotated, which represent an average of 2.275 (s = 2.09) per call. The A dataset is still highly unbalanced but significantly less than the G dataset.  Given the complexity of the modeling problem, we studied the note taking behavior of participants to identify relevant patterns that would simplify the problem. To this end, we conducted a quantitative analysis of the note taking behavior of participants. We found that users tend to highlight complete turns as relevant, instead of parts of the turns. On average, 66.57% (s = 35.87) of the words within an annotated turn are highlighted, with a median value of 80%. Hence, we decided to use turns -rather than individual words-as the unit to be automatically detected as noteworthy. Using this approach, a turn is considered to be noteworthy if it contains at least one annotated word.

Qualitative Analysis of the Corpus
Since our aim is to detect the noteworthy turns within a call, we conducted a preliminary qualitative analysis to understand the nature of the annotations entered by the participants in the study. We distinguished 4 types of annotations: Giving Information (I), Requesting Information (RI), Reporting on an Action (RoA) and Other (O). Examples of these 4 types of annotations are presented in Table 2. We collected annotations from three collaborators of our lab for a total of 54 randomly selected turns from the A dataset (IAA, F leiss Kappa = 0.54 (Fleiss, 1971)).
We found that 47% of the turns were classified as belonging to the Giving Information category, 22% of the turns to the Request Information category, 26% to the Other category, and only 3% were classified as Report on an Action. Intuitively, we had expected the Giving Information category to be the most common in the annotated turns. However, the results obtained show that the other types of annotations are also well represented in the data.
Two main interesting aspects emerge. First, while the vast majority of annotations correspond to turns where a piece of information is given (e.g. We meet at 3pm), turns where information is requested are also well represented in the sample. There are plausible explanations for this behavior, such as users trying to include more context in the annotations. Second, more than 25% of this manually annotated dataset was marked under the Other category, which includes turns with very diverse functionalities (e.g. greetings, statements of agreement). This reveals that participants tend to annotate turns with very diverse functional aspects, which poses a challenge to be added to the unbalanced nature of the dataset.

Feature Extraction
We follow a supervised machine learning approach to automatically detect noteworthy turns in conversations. In this section we describe the features that we compute to represent conversations and which have been engineered to capture information relevant to the problem at hand. We have divided the set of features into two categories: Content features, that we denote with the letter C, and conteXt features, that we denote with the letter X.

Content Features
Content features are computed by analyzing the content of the conversations. We use as input the textual information resulting from the semi-automatic transcription of the calls. Note that we do not make use of any conversational acoustic information. While the analysis of the acoustic signal may reveal additional cues useful for noteworthiness detection, it lies out of the scope of this work.
In order to extract features from the transcript, we first pre-proces the datasets (split in turns, lemmatized, PoS tagged). Also, we extract and classify Named Entities (NEs). 3 We extract 42 content-based features which include both variations of features previously used in the meeting summarization literature and novel features particularly adapted to our task. However, in contrast to related work on meeting summarization, we do not extract content features based on lexical similarity to the entire call or to the main topic of the call, under the intuition that the notion of noteworthiness depends on the user's needs rather than on the main topic of the conversation. In addition and for robusteness purposes, we decided not to rely on long distance dependency information (e.g. argument predicate relations) or deep syntactical parsing, which are sensitive to the quality of the transcription.
The resulting features are grouped into three main classes: Turn-Based (C-T), Dynamic (C-D), and Conversational (C-C). We compare them with a pure bag-of-words (BoW) representation. Table 3a provides a summary of all the content-based features used in our system. Where applicable, we experi-ment with two vector representations: binary and frequency-based. We will refer to these two different encoding schemes as Bin for the binary case, and Freq for the frequency case. Repetition between t and t-1,t+1,t-2,t+2 Int Presence (or total amount) of Int. pro./adj. in t-1 Q Presence (or total amount) of question in t-1 C-C (Conversational) Dur Duration of the call (# turns and # words) Cent Conversation centrality Spk Speaker Dom Speaker dominance Table 3: Content (a) and Context (b) based features.

Turn-Based Content features (C-T)
Turn-based content features take into account information related to individual turns. We distinguish lexical and non-lexical C-T. Lexical content features: Lexical C-T features capture the lexical properties of a turn. We include NEs, such as Locations, Organizations, Persons, Miscs and Numbers, Dates, and temporal expressions. For each turn t, we detect the presence of any NE as well as the presence of individual classes of NEs. For each of these class of entities, we extract both a binary and a frequency feature vector. In the text summarization literature, the appearance of particular lexical phrases (e.g. to summarize) has been exploited to predict relevant sentences (Gupta and Lehal, 2010). In our study, attention has been given to the presence of temporal expressions under the intuition that temporal cues are good indicators of upcoming pieces of information (e.g. The meeting is tomorrow). We exploit temporal expressions, such as today, tomorrow, etc. 4 Non-lexical content features: capture characteristics of the turn which do not involve lexical information, namely: turn length, Part-of-Speech (PoS) distributions and Tf-Idf descriptive statistics at the turn level.
In meeting summarization, the average length of a turn has been found to be a good feature to automatically create a summary of a meeting (Xie et al., 2008). In our dataset, preliminary analyses revealed that annotated turns tend to be longer in average. Hence, we include the turn length in the non-lexical content feature set. The turn length is given by the number of tokens per turn normalized over the average turn length (punctuation excluded). To further gauge discourse characteristics, we detect the distribution of PoS at the turn level: i.e. for each turn, the frequency of nouns, pronouns, adjectives, adverbs, interjections, verbs, prepositions and conjunctions is calculated. Finally, we compute the term frequency (Tf) and inverse document frequency (Idf) measures. In (Xie et al., 2008), authors report that Idf is among the most discriminative features in sentence selection for text summarization. We compute maximum and mean Tf and Idf values for each turn.

Dynamic content features (C-D)
Dynamic content features are designed to capture the semantic relationships between each turn and its precedent and subsequent turns. In particular we refer to relations such as lexical and topical cohesion, question-answer relationship, and the appearance of general cues that may anticipate relevant bits of information in the subsequent turn. We consider: 1) the lexical and topical cohesion among consecutive turns (Repetitions); 2) the appearance of general cues that may anticipate relevant bits of information in the subsequent turn (Interrogative Pronouns); 3) the question-answer relationship among consecutive turns (Question).
Repetitions: words repeated by different speakers in consecutive turns. Participants of a conversation tend to align at several linguistic and paralinguistic levels in order to ease communication and increase mutual understanding (Pickering and Ferreira, 2008). This phenomenon has been investigated in terms of prosody, lexicon and syntax (Levitan and Hirschberg, 2011;Brennan, 1996;Bonin et al., 2013;Branigan et al., 2010). From a lexical point of view, the alignment mechanism, often referred to as priming, is realized by means of word repetitions among speakers. Many studies have investigated this phenomenon assessing correlation between priming and mutual understanding or dialogue success (Vogel, 2013;Reitter and Moore, 2007).
We exploit the priming phenomenon to detect concepts in the conversation that are considered important by both participants, relying on the fact that repeated words convey concepts that participants want to make sure they have been successfully communicated to their interlocutor. Given a dataset D, a turn in D, t ∈ D, and t − i and t + i turns in the context of t, we calculate the amount of repeated lemmas between t and t−i, and t and t+i for 1≤ i ≤ 2. In order to consider semantically meaningful repetitions, we take into account only content words (nouns, adjectives, adverbs, verbs) when they activate one of the C-T features described above. Being A the set of annotated turns, we noticed a significant difference in the amount of repeated lemmas between t,t − i for t ∈ A rather than for t / ∈ A. Find below an example of consecutive turns with repetitions: Interrogative pronouns and questions: We also exploit indicators of an upcoming giving information act. As shown in Sec 3.2, 47% of the annotations were marked as giving information, which may have been triggered by a request of information in the precedent turn. Hence, in order to capture these cases, we identify linguistic elements that indicate a request of information in t − 1 (questions and interrogative pronouns/adjectives).

Conversational flow features (C-C)
They are designed to model information about the conversation's flow and speakers' interaction.
Centrality of the turn: Distance of a turn from the center of the conversation. This feature is inspired by the sentence location features used in text summarization (Chen et al., 2002). Chen et al. assign different weights to sentences in the first, middle and final part of a paragraph, in order to favor sentences that are in the central part of the paragraph as they are considered to be more informative for a summary. In our corpus, we noticed the tendency of users to annotate turns that are in the central portion of the conversation. Typically the first and the last quarters of the phone conversations are dedicated to social talk. Hence, we introduce a temporal feature, referred to as conversation centrality, that captures the distance of a turn from the center of the conversation. This distance is measured in terms of number of words, excluding punctuation.
Speaker: Who is uttering the turn (caller vs callee). Conversation duration: Length of the conversation in number of turns and in number of words. The number of turns captures the dynamics of a dialogue (few longer turn vs a more dynamic exchange), while the number of words captures the overall duration.
Speaker dominance: We consider whether the speaker is the dominant speaker of the conversation, defining dominance in terms of amount of productions during the call. This is calculated by comparing the number of turns of speaker a vs speaker b, normalized over the total amount of turns per call.

Bag-of-Words (BoW)
Finally, we explore the performance of a naive bag-of-words scheme to represent the content at the turn level. Given the large vocabulary size of our corpus (10, 144 tokens) and the sparsity organic to bag-ofword representations, we decided to use a trivial dimensionality reduction strategy filtering out the terms that appear only once in the corpus. We decided not to apply a stop-list of functional words for further reducing the feature space. This decision was based on the higher discrimintative power we observed when comparing classification accuracy with and without them. We discarded the use of more aggressive feature selection approaches (e.g. mutual information) to allow for a fair comparison of accuracy with the rest of feature representations described in the paper. In total, our BoW representation had 5, 048 dimensions in the G dataset, and 3, 219 dimensions in the A dataset.

Context Features
Context features are introduced under the assumption that noteworthy information may depend on the characteristics of the user and on the situation in which the call takes place. For example, people may not need to annotate pieces of information that are part of their daily lives. Whereas while taking an appointment, it is plausible the need to annotate the name of the doctor, in a social call with a friend, the name of the friend is part of the background knowledge of the user. Therefore, while from a content (and an NLP) point of view both names are Person NEs and carry the same amount of information, from the point of view of the user they might have different weight (no need of taking note vs need of taking note). Also, the current situation or location of the user may influence the necessity of taking notes: a user in a supermarket will not need to annotate to buy milk, (s)he will rather take it directly from the shelf. A user driving to the supermarket will need to keep in his/her mind the need to buy milk for later recall.
In line with this, we noted in Section 2 that pure NLP approaches applied to automatically detecting noteworthy information in meetings are able to achieve an F-score of only 0.14. This low F-score underlines the complexity of the task and the limitations of a pure content-based approach. Contextual cues may be used to increase the discriminative power of the classification model.
Since we consider the specific scenario of cellphone conversations, we can exploit contextual information derived from the use of the mobile network, such as geo-location, and temporal information. Other contextual features that we use, gathered during the pre-study questionaire, are organically much more challenging to infer. We still decided to consider these as a way to assess the potential of several types of contextual information with respect to the discriminative power of the classifier. We distinguish among Call-based (X-C) and User-based (X-U) contextual features. A schematic overview of these features is given in Table 3b.

Call-Based Features (X-C)
Call-based features are meant to capture contextual information at the call level. In particular, X-C features include information about where, when and for what reason a call is made, under the intuition that calls made, for example, during working hours may have different noteworthy information than calls made in the weekend. We distinguish six location categories: home, work place, while commuting, while exercising, while shopping, other. The location of the calls was provided by participants through the post-call questionnaire. However location information is typically available from the mobile network. In terms of temporal features, we consider the actual time of the call (over 24 hours). In addition, we classify the time in two classes: working vs non working hours, and the day in also two classes: weekday vs weekend. Finally, we also consider the objective of the call as described in Section 3. Note that, although this information is not directly accessible from mobile data collected during the call, previous literature on conversation classification supports the feasibility of inferring this information from the content of the conversation (Koço et al., 2012).

User-Based Features (X-U)
Finally, we introduce a set of features that feed the model with information about the user. We exploit information that could be provided by users upon registration to such a note-taking service. We capture age, gender, educational level, income and marital status. Gender is represented as a binary feature, while age is categorized in 5 groups: below 20 years old, between 20 and 30, between 30 and 40, between 40 and 50 and above 50. The education status is represented by the following categories: Primary education, Secondary education, Bachelor degree or a Postgraduate education (Master or PhD). Yearly income is categorized by: up to 10k, 20k, 30k, 40k and more than 40k. Finally, marital status is categorized as: single, in a couple (married, with a stable partner), other.

Experiments
The goal of our system is to automatically identify information annotated by users in terms of its potential need for future recall. We frame this problem as a binary classification task (noteworthy or not) at the turn level. This task presents two main challenges. First, our dataset is extremely unbalanced, with less than 3% of the corpus labeled as relevant by the participants. Second, the subjectivity of the task leads to high variability of annotation behaviours, (see Sec. 3.2). In this section we describe the experimental setting that we used to empirically evaluate the performance of different features sets and present the results obtained using the ground truth data collected (Section 3) to provide classification performance scores. In order to fully investigate the predictive performance of the different feature sets, we conducted our experiments using both the entire corpus G, which includes all the selected conversations, and its subset A, which considers only the calls with at least one annotation. Both sets are described in Sec. 3. We experimented using both encoding schemes described in Section 4: binary based (Bin) and frequency based (Freq).
We used Support Vector Machines (SVMs) with RBF kernel, as this classification approach yielded the most consistent results throughout all the evaluated configurations. We used the same random split of training and test sets for all the experiments, accounting for 70% and 30% of the dataset respectively. We tune the hyperparameter C of the SVM model using a 3-fold cross-validation approach on the training data only, where we chose F-score as the quality metric to optimize. Given the nature of our task, recall is preferred to precision from a user-centric perspective: it is preferable to avoid missing any relevant information than to include some non-relevant fragments. For this reason, we also report precision and recall values.

Classification Results
This section presents the results obtained in our binary classification task (turns being noteworthy or not). We study the performance of different combinations of features and present the results obtained using only content information (C), and the combination of content and context information (CX).

Content features
We present a comparison of the different content feature sets using the naming scheme of Sec.4. We considered four classification scenarios: C-T only, C-D only, the combination of C-T and C-D (C-TD), and the combination of C-T, C-D and C-C (C-TDC). The results of these feature sets are shown in Tables 4a and 4b for the G and A collections, respectively.
As shown in Table 4a, the maximum F-score for the G dataset is achieved for the combination of all content features included the BoW. The low score (F = 0.18) is a direct consequence of the low precision obtained (P = 0.11). For the A dataset (Table 4b) we observe a better F-score (F = 0.296), still obtained by the combination of all content features, with a much higher precision (P = 0.18) due to the significant amount of noise removed by considering only annotated calls. Note that in both the G and the A datasets the C-TDC feature set outperforms the pure BoW approach (F = 0.158 vs. F = 0.14  for G and F = 0.267 vs. F = 0.22 for A), using a fraction (about 1%) of the number of BoW features, which leads to a considerably simpler model. On the other hand, the combination of C-TDC and BoW features improves the results up to F = 0.18 for G (P = 0.11, R = 0.52) and F = 0.296 (P = 0.20, R = 0.57) for the A subset. This result highlights how the lexical representation comprised by the BoW provides the model with orthogonal information to the one provided by the C-TDC features set.
To the best of our knowledge no previous work has been done in noteworthy detection from telephone conversations. For this reason, we report as a reference the results of the more similar prior art to our work, (Banerjee and Rudnicky, 2008), where the authors implement an SVM classifier for the detection of noteworthy information in meetings. 5 Although aware of the different nature of the dataset, these results are reported to get a sense of the potentiality of the system. The best performance of our model on the A dataset improves in 15% the F-score of F = 0.14 reported in (Banerjee and Rudnicky, 2008).

Combining Content and Context Features
In this section we report the performance of the model trained using both content and context features. For simplicity, in the remainder of this section we refer to the entire set of content features, (C-TDC) as C, to the entire set of context features as X, and to their combination as CX. When we test adding BoW features the +BoW naming is used. The results are shown in Table 5 and Figure 1. We observe that the fusion of content and context features (CX and CX+BoW) provides a noticeable overall increase in the F-score for both datasets. This increase is particularly high for the G dataset, where the F-score gets increased by almost a factor of 2, from F = 0.18 to F = 0.28. On the A dataset, the combination of content and context features improves the F-score from F = 0.29 to F = 0.32, given by a better precision (P = 0.24 vs P = 0.18) with similar recall.   that is relevant for the task at hand. That is, the same words can carry different relevance depending on the contextual information of the conversation. Note that the BoW features add discriminative information in the G scenario, but have a minimal effect in the less noisy A scenario where the combination of content and context features, without BoW, provides already an F-score of F = 0.31.
An interesting remark about this combined model is that the difference in performance between the G and the A dataset is vastly reduced. While in the pure content model the difference in F-score value between both datasets was 0.10, in the combined model this difference is just 0.03. This result shows that the combination of content and context features boosts considerably the results in the more noisy and realistic dataset G, while its effect is weaker in the cleaner dataset.

Qualitative Analysis
In order to better understand the failure cases in our system, we carried out a qualitative analysis of both false positives, i.e. turns annotated by the system but not by the user, and false negatives, i.e. turns annotated by the user but not by the system. Table 6 illustrates a few representative examples. Note how the proposed system does not perform well when detecting a request for information as something worth annotating (e.g. What are you doing?). We noticed that in these cases, the model tended to annotate turns where the information was actually provided (e.g.That is the package has arrived). We can hypothesize that users annotate the request for information to give context to the a-priori more relevant information, i.e. the answer to the question. However, in some cases, participants did not annotate the answer as relevant. This counter-intuitive observation reflects the subjectivity and variability of the task.

False Positive
False Negative I am leaving soon, I start at 3 o'clock or [..] How are you? Can you hear me? Let's see if we can tell him.
What are you doing? That is, the package has arrived.
Did you buy beautiful things for me? Table 6: Examples of false positive and false negative turns.

Comparative Analysis and Discussion
To the best of our knowledge there are no previous works of similar nature to the study presented in this paper. Yet, it is important to give a sense of the merits and limitations of the proposed approach in the context of the state-of-the-art. For this reason, we compare our results with (Banerjee and Rudnicky, 2009), which is the most similar prior art to our work. In (Banerjee and Rudnicky, 2009), Barnejee et al. perform a Wizard-of-Oz experiment and report a performance of the human annotator of P = 0.35 precision, R = 0.42 recall, leading to an F-score of F = 0.38. This result highlights the difficulty of the task, even for a human annotator. When comparing our proposed system with this Wizard-of-Oz experiment, we obtain an F-score of F = 0.32 against the human annotator's F-score of F = 0.38, with a significantly higher recall (0.57 vs 0.42) yet lower precision (0.245 vs 0.35). Given this humanbased prediction performance, the proposed approach represents a good first step towards realizing an intelligent annotation system for mobile phone conversations.

Conclusions and Future Work
In this paper we have proposed and empirically evaluated a machine learning-based approach to automatically detect noteworthy information in spontaneous mobile phone conversations. The subjectivity of this task leads to a challenging classification problem even for human assessors. Our approach adopts a hybrid strategy that exploits the content and the context of the conversation. We have shown that information about the context of the conversation improves the predictive performance of the system over a pure content based approach.
In the future, we plan to extend the model by including acoustic features which could improve the performance by adding orthogonal information to the current model. To tackle the subjectivity of the task we also intend to investigate the performance of personalization techniques, creating individual models per user. Finally, we plan to conduct a study to evaluate our system from a user-centric perspective.


extfieldsofstudy: Biology Medicine

text:
Cell cycle dynamics in a response/signalling feedback system with a gap

We consider a dynamical model of cell cycles of n cells in a culture in which cells in one specific phase (S for signalling) of the cell cycle produce chemical agents that influence the growth/cell cycle progression of cells in another phase (R for responsive). In the case that the feedback is negative, it is known that subpopulations of cells tend to become clustered in the cell cycle; while for a positive feedback, all the cells tend to become synchronized. In this paper, we suppose that there is a gap between the two phases. The gap can be thought of as modelling the physical reality of a time delay in the production and action of the signalling agents. We completely analyse the dynamics of this system when the cells are arranged into two cell cycle clusters. We also consider the stability of certain important periodic solutions in which clusters of cells have a cyclic arrangement and there are just enough clusters to allow interactions between them. We find that the inclusion of a small gap does not greatly alter the global dynamics of the system; there are still large open sets of parameters for which clustered solutions are stable. Thus, we add to the evidence that clustering can be a robust phenomenon in biological systems. However, the gap does effect the system by enhancing the stability of the stable clustered solutions. We explain this phenomenon in terms of contraction rates (Floquet exponents) in various invariant subspaces of the system. We conclude that in systems for which these models are reasonable, a delay in signalling is advantageous to the emergence of clustering.

Background
We consider a generalization of a dynamical model of the mitotic cell division cycle (CDC) with response-signalling feedback that was introduced by authors in [2,30]. The dynamics of the model are governed by where c i is the position of the cell within the cycle andc = (c 1 , c 2 , . . . , c n ) T denotes the state of all the cells in the culture. Here c i ∈ S 1 = R/Z = [0, 1]/(0 ∼ 1), so the phase space we consider is the n-torus. The term a(c i ,c) allows for cells in one part of the cell cycle S (signalling) to effect the growth/progression of cells in another part R (responsive), i.e. feedback. Specifically, we will consider the situations where cells in S produce chemical agents that retard the cell cycle progress of cells that are in R. Positive feedback from S to R could also be considered. In previous studies [2,30], we assumed that R immediately proceeds S, that is, they intersect at a boundary, such as the boundary between the G1 and S phases in yeast. In this manuscript, we explore the modelling assumption that there is a gap between the two regions. A gap is biologically justified by the inevitable delay between the onset of production of a potential signalling agent and its effectiveness. We are motivated by yeast metabolic oscillations (YMOs), a phenomenon that has been observed in experiments for at least 60 years [10,16,18] and remains a topic of intense interest [5][6][7][8]12,[19][20][21][22][23][24][27][28][29]31]. A link between YMO and the cell division cycle (CDC) was noticed as early as in [16,18], but this connection seems to have been largely ignored. However, in [15,27] a connection between YMO and CDC was again noted in genetic expression time series.
Bockzo et al. [2], based on data in [23], proposed cell cycle clustering as a possible explanation of the interaction between YMO and the CDC. By clustering we mean groups of cells traversing the CDC in near temporal synchrony, not spatial clustering (cultures that exhibit YMO occur in well-mixed bioreactors). In [2,30], we studied both simple and general forms of (1) with the hypothesis that cells in one part of the CDC may influence the growth or CDC progression of cells in other parts of the CDC through diffusible metabolites. We showed analytically and numerically that CDC feedback such as this can robustly cause CDC clustering in the models. For example, a significant subpopulation of cells in the critical S-phase might affect metabolism production and the metabolites may in turn inhibit or promote cell growth in the later part of the G1 phase, thus setting up a feedback mechanism in whichYMO and CDC clustering are inextricably intertwined. In [4], a model with an explicit term to represent the signaling agent is studied.
Guided by these mathematical results, we verified the existence of clusters in two types of oscillating yeast cultures using both bud index and cell density data [2,26]. Experimental evidence in [24] also supports the existence of clusters in some YMO experiments. Since Saccharomyces cerevisiae is a model organism, it is important to understand the interconnectedness of the CDC and metabolism [1,6,15,24,27,29]. Also, yeast are used in many bio-engineering processes and understanding their metabolism and cell cycle is of interest in some applications [14,25,31].
In the rest of the paper, we will use S = [ , s) to denote the signalling region, R = [r, 1) to denote the response region, and to denote the width of the gap, [0, ], between S and R. The gap is intended to mimic a delay of the chemical signalling agents responsible for the feedback.
For these modelling assumptions to be quantitatively realistic, there need to be some estimate of the size of the gap. One of the metabolites that is known to have effects on cell cycle progression and is thought to be the primary signalling agent in glycolytic oscillations is acetaldehyde [8]. The diffusion rate of acetaldehyde across a yeast cell membrane is estimated to be d = 300 s −1 [8], so this rate is very fast. The diffusion/convection in the well-mixed bioreactor is even faster. The decay rate for acetaldehyde in the same yeast bioreactor study was estimated to be τ = 7.3 min −1 − 9.9 min −1 [8]. In this experiment, the yeast were performing fast glycolytic oscillations so the production rate of acetaldehyde would need to be on the same order of magnitude. This implies that time scale of a delay is on the order of 3 × 10 −4 in the normalized coordinates. The glycolytic oscillation in that experiment had a period of 37 s. Using this as an upper bound of the time scale of acetaldehyde production and diffusion would give us an upper bound on the gap of 0.0025. It is not known with certainty that acetaldehyde is the only or even the dominant signalling agent in the oscillations where clustering has been observed. Thus at this point these estimates are only speculative. Fortunately, as we shall see, we are able to analytically treat a broader range of gaps.

The feedback model
The following is an RS-feedback with a gap system (compare [30]): Definition 1.1 Consider n cells whose coordinates are given by c i ∈ [0, 1], 1 identified with 0. When a cell reaches 1 it continues at 0. We call such a system an RS-feedback system with gap if: (H1) R is an interval that precedes another interval S with a small length gap, i.e. the distance between the last endpoint of R and the first endpoint of S is ; (H2) a(c i ,c) vanishes except when c i ∈ R and there are some c j in S; (H4) Feedback is monotone -adding a cell to S will increase the value |a(c i ,c)| for all c i ∈ R; and (H5) a(c i ,c) is a smooth function for c i in the interior or R and each c j in the interior of S, j = i and the one-sided derivatives exist at the boundaries of R and S.
A positive feedback will mean that a is positive for c i ∈ R when at least one c j is in S. We define a negative feedback analogously.
Hypothesis (H1) specifies the signalling, the response, and the delay in signalling. The meaning of Hypothesis (H2) is that cells will not experience any feedback, unless it is caused by cells in the signalling region. Hypothesis (H3) assumes that feedback is bounded, i.e. there are upper and lower limits on the rate of progression of a cell in the cycle. Note that we are not allowing cell cycle arrest, a common biological state. Hypothesis (H4) supposes that feedback must increase as the number of signalling cells increases. We note that hypotheses (H3) and (H5) (a technical assumption) are sufficient to imply existence and uniqueness of solutions of (1) [30].
Recall that we specify the coordinates throughout the paper as follows: The final endpoint of R is 1, which corresponds to 0, the initial endpoint of the gap [0, ).
In this paper, we will mainly study the following RS system with a gap: where i.e. I is the fraction of cells in the signalling region. The 'response function' f (I) in Equation (2) must satisfy f (0) = 0 and be monotone (H4), but can be non-linear. These assumptions correspond to the suppositions that no cell in S implies no feedback is exerted and that more cells in S must result in more feedback on cells in R.
It is known in cell cycle models without feedback that the inclusion of small dispersive or diffusive forces leads to asynchronous population profiles in which a 'steady-state' profile is asymptotically stable [9,11]. Our previous work shows that this is not the case when feedback is included, but rather populations tend to form temporal clusters. There are other recent discoveries of clustering behaviour due to a negative feedback, especially in phase oscillator models of networks of neurons [13,17].

Dynamics of clusters via return maps
In the remainder of this manuscript, we consider the existence and stability of periodic 'clustered' solutions. Because the cells are assumed to be identical and obey (1), cells that initially share the same coordinate will remain synchronized as time evolves. By a cluster, we formally mean a group of cells that have identical coordinates in the CDC.
Because clustered solutions will remain clustered, one may consider such solutions using the coordinates of the clusters rather than those of individual cells. In doing so, one may greatly decrease the dimensions of the system. In a yeast bioreactor culture, n can be in the order of 10 10 , while we may study clustered solutions with a small number of clusters.
For example, if the full system satisfies Equation (2), then the equation of progression for k clusters consisting of an equal number of cells is where I is the fraction of clusters in the signalling region: I ≡ #{j : x j ∈ S}/k. The extreme case of clustering is if all cells have identical coordinates; then we have a single cluster and Equations (4) will become a single equation. It will be trivial since there will never be a feedback acting on the clusters. The only solution is a periodic solution that runs at velocity 1 around the circle (i.e. x 1 (t) = x 1 (0) + t mod 1 for all t > 0). We refer to this special clustered solution as synchronized.
We note in [2] that a synchronized solution is locally asymptotically stable for a positive feedback and unstable for a negative feedback in the general model (1). This is because when a group of cells that are nearly synchronized leaves R and enters S the first cells in the group exert feedback on the trailing cells. For a positive feedback, the trailing cells in R will speed up. The cells will eventually approach synchronization. For a negative feedback, cells in R will slow down instead, thus moving further from the synchronized state.
In contrast, with a gap between the responsive region R and the signalling region S, the above situation will not happen. If a solution consists of all cells within of each other, then when this group of cells crosses from R to S, all of the cells will be out of R before the first one enters S. Hence, no cells in the solution experience feedback and the following proposition is obtained. It is natural to ask whether or not the inclusion of a gap also changes the global dynamics of the system. As discussed in [30], we can assume that all coordinates x j (0) of the k clusters are initially well-ordered as This ordering is preserved under the dynamics (in a sense that can be made precise) and the first coordinate x 1 must eventually reach 1, i.e. there exists t R such that x 1 (t R ) = 1. Thus, the set x 1 = 0 defines a Poincaré section for the dynamics and the mapping defines the corresponding return map.

Journal of Biological Dynamics
Starting from t = 0, we compute the time t 1 that x k needs to reach 1 and the location of the remaining clusters at this time. As in [30] we define a map F by Note that x 1 (t 1 ) = t 1 by the assumptions. If the clusters are identical to each other, then the map F is a root of the Poincaré map, i.e. F k = P and it can be regarded as a continuous, piecewise smooth map of the (k − 1)-dimensional simplex Figure 1.
We concentrate on studying periodic clustered solutions that satisfy: We will refer to such solutions as k-cyclic clustered solutions. If k is a divisor of n, then a k-cyclic solution exists consisting of n/k cells in each cluster. This fact can be proved using the Brouwer fixed point theorem applied to F [30]. As pointed out in [3], clustered solutions become less and less important as k grows larger.
In the remainder of this manuscript, we will use k to denote the number of clusters and will suppose that each cluster consists of n/k cells.

Analysis of k = 2 cluster systems
In this section, we will compute and analyse the map F for two equal clusters in the model (4). If we start x 1 at 0 and integrate until x 2 reaches 1, then calculating F reduces to solving: where I(x) = 0 or 1 2 , because there can be only one cluster in the signalling region S when another cluster is in the response region R. Let α = f ( 1 2 ). We will see that the problem can be analysed by dividing it into the following two cases:

Case 1: (1 + α)(s − ) < 1 − r
There are five situations depending on the location of x 2 : and before x 1 leaves [ , s), x 2 is influenced by x 1 for some part of the time when it is in the responsive region. We can obtain the following piecewise-defined function for the position of x 2 depending on time: In this case, x 2 is influenced by x 1 for the entire time when x 1 is in the signalling region. This is because x 1 arrives at S after x 2 reaches r and x 1 gets out of S before x 2 reaches 1. We may obtain: In this case, x 2 reaches r before x 1 gets into S, and when x 2 reaches 1, x 1 is still in S. We can find the position of x 2 : We can find that Combining these five sub-domains, we can obtain the map F for Case I:

Case II: (1 + α)(s − ) ≥ 1 − r
Similar to the computation above, we consider five subcases: In this case, x 1 reaches first, then x 2 enters R, and x 1 reaches s before x 2 reaches 1. So x 2 is partially influenced by x 1 . This yields the position of x 2 expressed by the function: Here x 2 is influenced by x 1 for the entire time when it is in the responsive region because x 2 enters R after x 1 gets into S and when x 2 reaches 1, x 1 is still in S. We obtain the following piecewise-defined function for the position of x 2 : For this case x 2 enters R before x 1 reaches , and so it is influenced by x 1 for some part of the time when it is in the responsive region until it reaches 1.
. This is the same as Case 1(e) that x 1 does not affect x 2 . We obtain: We combine the five subcases and arrive at the map F for Case II:

Analysis of the dynamics
The graph of F coincides with the anti-diagonal (Figures 2 and 4); while for a negative feedback α < 0, it is strictly greater than 1 − x 2 if r − s < x 2 < 1 − (Figures 3 and 5). In the following discussion, we consider the restriction that < r − s is relatively small.
For Case I ((1 + α)(s − ) < 1 − r), it is seen that Therefore, the graph of F cannot intersect {y = x 2 } at the line segments IV and V or the points C and D. This is illustrated in Figures 2 and 3.   Similarly, for Case II ((1 + α)(s − ) ≥ 1 − r), we can find that the graph of F and the diagonal cannot intersect at C, IV, D or V (see Figures 4 and 5), because  Considering the above situations, we conclude the following: (1) If r − s > 1 2 , the intersection of the graph of F and the diagonal y = x 2 lies in the first line segment (0 < x 2 < r − s), denoted as I. Each point of the interval [1 − r + s, r − s] is part of a 2-periodic orbit x 2 → 1 − x 2 → x 2 , except for the point x 2 = 1 2 which is fixed. Hence, the return map F 2 has an interval of neutrally stable fixed points centered around x 2 = 1 2 .
(2) If r − s = 1 2 , the intersection, denoted as A is at ( 1 2 , 1 2 ). It is a unique fixed point that is stable for negative α and unstable for positive α.
(3) If r − s < 1 2 , then < 1 2 , thus 1 − > 1 2 . There are three possibilities depending on where the diagonal line y = x 2 intersects the graph of F. Also here, we need to consider Case I and Case II separately. Note that in all cases, the 2-cyclic solution corresponds to the unique fixed point of F. According to the above results, we find four distinct types of dynamics; two for positive feedback and two for negative feedback. These behaviours are exactly the same as for the model with no gaps [30]. Furthermore, we note that in the parameter regions where the fixed point of the map is either stable or unstable, the slopes of F are exactly the same as for the model without gaps (see [30]).

Isolated solutions
Denote |S| as the length of the interval S = [ , s), which is s − and |R| = 1 − r denotes the length of the interval R = [r, 1). We say that a cluster of cells is isolated if there are gaps between the cluster and any other cells on either side of length at least |R| + |S| + and strictly isolated if the widths of gaps are more than |R| + |S| + . Strictly isolated clusters cannot exert feedback on cells outside the cluster, or have feedback exerted upon them from outside.
We consider the case only when is small, i.e. < r − s, as in the former section. The following definition will play a large role in the analysis of the model.
i.e. M is the maximum number of isolated clusters that can simultaneously exist.
We will consider the cyclic solutions consisting of k = M + 1 clusters. For k = M + 1, it can be shown that the cyclic k-cluster solution has initial conditions: x 1 = 0, x 2 = d, x 3 = 2d, . . . , x k = (k − 1)d. During each time interval d, each cluster will move to the position of the cluster ahead of it.
For k = M + 1 and for all solutions in a neighbourhood of the cyclic solution above, at most one cluster can be in the signalling region S at a time. Thus, the feedback experienced by any cluster in R is either 0 or f (1/k). Hereafter, when studying systems with k = M + 1 clusters, we will use the abbreviation:

Order of events for the cyclic solution
The evolution of a solution can be described in terms of the order of events of the solution.
Clusters of cells progress through the cell cycle at rates specified by Equation (2). These rates remain constant until a cluster reaches , s, r, or 1. Given the next such event and the index j of the cluster for which it occurs, we can calculate the time elapsed until the event occurs by finding out the initial position of cluster j and its corresponding rate during that time. We will use x j → μ to denote the event that cluster j reaches the milestone μ. Then for the order of events, for example, as in Case I below the notation x 1 → , x k → r, x 1 → s, x k → 1 means that first x 1 reaches point , then x k reaches r, etc. We discuss in the following cases the possibilities of the orders of events for the cyclic solution.
Case I: By calculating the position of x k in each step, we have Here, x k (t 1 ) = 1. So, t 1 = 1 + β(r − s) − (1 + β)(k − 1)d (β = f (1/k)). At time t 1 , x 1 reaches x 2 = d (since it is moving with speed 1). Thus, One can solve for d: This case can only happen when d > s and x k = (k − 1)d < r − . Using Equation (9) in these two inequalities gives conditions on r and s required by this order of events: Case II: Similar to Case I, we may calculate: The above d also needs to satisfy d > s and r > x k > r − , so we obtain: Case III: This order of events can happen only when x k > r. We can find that d is the same as in Equation (11), d = (1 − β(s − ))/k, and the order of events in this case implies the inequalities: Case IV: After some calculation of the final position of x 1 , we find that This case occurs under the conditions that d < s − and x k < r. Using Equation (14) with the order of events gives that Case V: s − < d < s and x 2 → s, x 1 → , x k → r, x k → 1. After a similar calculation, we find the same d as in Equation (14) that is d = (1 + βr)/k(1 + β). Applying this result to s − < d < s and x k < r − , we obtain the following conditions for Case V to occur: Case VI: This case occurs if and only if d < s and r > x k > r − . Solving for d, we find that We substitute Equation (17) into the above inequalities to obtain: The regions described by the inequalities in Equations (10)- (18) are illustrated in Figure 6. We can observe that cases I-VI exhaust the parameter set in (r, s) and there is never more than one cluster in the signalling region when R is non-empty. Thus the dynamics of the system are determined by the feedback β = f (1/k).

Stability of the cyclic solution
Now we will calculate the return map F. We note that F is affine in a neighbourhood of the cyclic solution provided that the parameters are in the interior of one of the cases. Thus, F : To find the stability of the fixed point, the linear part of the system, i.e. A needs to be analysed.
In Case I, we can calculate the time for x k reaching at 1, that is t 1 = 1 + β(r − s) − (1 + β)x k . Since each of the clusters moves for time t 1 , we can find x j (t 1 ) = x j + t 1 = x j + 1 + β(r − s) − (1 + β)x k for j = 1, . . . , k − 1. Given that x 1 = 0 and x k (t 1 ) = 1, we have F(x 1 ) = 1 + β(r − s) − (1 + β)x k and F(x k ) = 1. Thus we can obtain the matrix A by taking the partial derivatives of the return map F ((x 2 , . . . , x k ) T ): In [30], it was proved that all the eigenvalues of A defined by Equation (19) lie outside of the unit disc for β > 0 and lie on the interior of the unit disc for β < 0. Thus, the fixed point of the return map F in Case I is stable for a negative feedback and unstable for a positive feedback, so is the k-cyclic solution.
In Cases II and III, following the same procedures as above, we can calculate that the matrix: In Cases IV and V, we can find that Here the coefficient for the x k term is still −1, so the linear part of the map is the same as the matrix A given by Equation (20) in cases II and III. It is well known that the eigenvalues of this matrix A all have (complex) modulus 1. Thus, the k-cyclic solution is neutrally stable in all the cases from II to V.
For Case VI, the time for x k to arrive at 1 is Note that this case only occurs for M = 1 or k = 2 and > r − s. For M > 1 and < r − s, this region is outside the band k = M + 1. The matrix A can be derived as follows: We can use a change of variable to study the stability of this return map compared in the result for Equation (19). We conclude that the fixed point is stable for a positive feedback and unstable for a negative feedback in this case. The dynamics for the k = M + 1 cyclic solutions can be summarized as follows: (1) When s < (1 + βr)/k(1 + β) and r > ((k − 1)/k)[1 − β(s − )] + , the k-cyclic solution is stable for a negative feedback and unstable for a positive feedback. (2) For k = 2 and > r − s, when s > (1 + β)/(k + β) and ( k(β + 1) , the k-cyclic solution is stable for a positive feedback and unstable for negative feedback.
The behaviour in Equation (2) occurs only on a small part of parameter space with > r − s, i.e. Case VI in Figure 6.
The behaviour in Equations (1) and (3) is entirely consistent with those for the model without a gap [30]. Further, as noted above, the matrix DF in the stable and unstable cases are exactly the same as for the model without a gap. Thus, the gap does not even alter the strength of the stability or instability; the linearization of the return maps is exactly the same.
We note that the region in parameter space for which the k = M + 1 cyclic solution is stable is exactly the same as for the model without a gap, except the strip of width representing Case II is removed.

Observed clusters
We simulated n = 420 cells for the model with and without a gap of = 0.01. It was studied that clusters form under negative feedback and the exact form of the feedback function does not matter for the general RS feedback system in [30]; thus, in all the simulations we set the feedback function to be f (I) = −I for simplicity. We used a first-order Euler integration with an adaptive step size so that the step matched intervals on which the vector field is constant. By doing this there is no truncation error and all calculations are locally accurate to machine precision.
In Figure 7, we show the number of clusters that appear in simulations of the model with and without a gap. For each pair of parameter values (s, r), we started with a equi-distributed initial condition and integrated for 100 cell cycles. The number of clusters were counted using a variation of a standard clustering algorithm DBSCAN. One can see that the main features of the plot are unchanged by the addition of a small gap. Note that in both plots, for all but a narrow set of (s, r) values around the perimeter, clusters always emerge. We visually inspected a large selection of simulations and observed that in all instances where the algorithm indicated clustering, the solutions were in fact unambiguously clustered. Figure 8 gives some simulation results showing how clusters emerge.
As predicted in Sections 3 and 4, the global dynamics with and without a gap are qualitatively the same.

Speed of convergence
In completing the experiments for Figure 7, we noticed that despite the prediction that the global dynamics be the same, the simulations with a gap tended to converge to the periodic orbits more quickly than without a gap. In Figure 9, we study the speed of convergence to clustered solutions in simulations with a negative feedback. Again we started with evenly distributed initial condition.   In order to study the convergence, we used the vector of gaps: where d(x, y) is the distance from x to y on the circle in the direction of the orientation. The Euclidean norm squared, ||G|| 2 2 is a measure of how clustered a solution is. It has a global minimum when the cells are equi-distributed around the circle and a maximum (of 1) when all the cells have the same location (synchronized). In the simulation, G was measured at the end of each cycle on the Poincaré section {x 1 = 0}.
For the models with and without a gap, we see that solutions converge to a stable clustered configuration. For the model with even a modest gap of = 0.01 this convergence is much more rapid. This seems to contradict the conclusions of Sections 3 and 4, where we observed that stable cyclic solutions have exactly the same Floquet exponents for the gap and non-gap models. However, the calculation in Sections 3 and 4 were completed in the clustered subspace, not in the full phase space of n cells. In the case of a negative feedback, where clustered solutions tend to be stable, the model without a gap has a local linear instability effect on individual clusters as they cross the R-S boundary. In the gap system, this effect does not occur as reflected in Proposition 2.1. The Floquet exponents in the full phase space are more negative with a gap since individual clusters are not locally unstable.
To take a close look at this, we consider a small perturbation of the cyclic solution, close enough to the cyclic solution so that the order of events for those new groups of points does not change (i.e. if one cluster leaves S before another enters R, after dispersion the two clusters and viewing them as two groups of cells, we now have all cells in one group leave S before any cells in the second group enter R). For the k-cyclic solution, we denote each group by 1, 2, 3, . . . , k. Let time run until the first cell in group k reaches at r and denote the diameter of the kth group at this time to be δ. Then when this group has entirely entered R, its diameter has reduced to (1 + β)δ because each cell in the group is subjected to negative feedback β since another group of cells has been in S during this time.
For the model without a gap, let time run until the first cell of the kth group lies on 1. Because cells which have reached 1 will travel with velocity 1, the diameter of this group after it passes 1 entirely will be the amount of time it takes for the cell lying at 1 − (1 + β)δ (i.e. the last cell in this group) to reach at 1. To find the maximum of this diameter, we consider the worst case that one cell lies at 1 − (1 + β)δ and all other cells of this group are at 1. We can easily calculate that the time it takes for the one cell at 1 − (1 + β)δ to arrive at 1: Thus, the diameter of the group is ((1 + β)/(1 + β ))δ. f above is the feedback function and the fraction inside is obtained by calculating the proportion of cells inside S during this time. By monotonicity of f , for negative feedback, 1 + β < 1 + β . Therefore, the diameter for the kth group is strictly less than δ. We can conclude that after each cycle, the diameter δ of a cluster may shrink to ((1 + β)/(1 + β ))δ.
For the model with -gap, we may assume that δ < . When the last cell in the kth group reaches at 1, the rest of the cells in the group still lie inside [0, ], thus the feedback remains the same. Therefore, the diameter of the group shrinks from δ to (1 + β)δ for a negative feedback. Obviously, (1 + β)/(1 + β ) > 1 + β for −1 < β < 0, and in fact the contraction factor in the worst case for the system without a gap will be very close to 1. This shows that the spectral radius of the linearization for the no-gap system is much closer to 1 than the system with a gap. Thus the maximum eigenvalue of the linearization is smaller for the system with a gap.
The differences in the (local) Floquet exponents account for the marked differences in the convergence once the solution is in a neighbourhood of the clustered solution. These differences are apparent in Figure 9.
It can also be seen in Figure 9 that with a gap, solutions also reach a neighbourhood of the attracting periodic orbit much more rapidly. Generally speaking this can be due to either (1) increased rates of repulsion at repellers (probably unstable periodic orbits) or (2) global factors. The first of these might be amendable to analysis while the second is very difficult to assess.

Simulations with (relatively) large gaps
Note that the condition < r − s is assumed in Sections 3 and 4. This condition states that: The gap going from R to S is smaller than the gap going from S to R. Thus if the condition fails, then we are dealing with a fundamentally different kind of system; a system in which S could be viewed as located ahead of R rather than vice versa.
One situation where the condition is violated is when is small, but r − s is even smaller. We encountered this in Case IV in Section 4, where the dynamics were essentially reversed; the 96 X. Gong et al. clustered solutions become unstable. In Figure 7, we also observed the violation of the condition for parameter values near the diagonal line r = s. There we observe synchronous solutions.
In order to shed more light on the condition ≥ r − s, we performed several numerical experiments. In Figure 10, we show the final position of 40 cells after integrating until the system stabilizes to a periodic solution or until a maximum number of steps is reached. Here we set s = 0.5 and r = 0.8 and let vary on the interval [0.01, 0.49]. When < r − s = 0.3, two clusters emerge as we expect from earlier analysis. As approaches r − s = 0.3 the stability of the 2-cluster solution weakens and at = r − s there appears to be a bifurcation. At the critical value = 0.3, where R and S are equal in size and exactly opposite one another, no clustering occurs at all, and near that value there appears to be complex and unpredictable behaviour. When is approximately 0.37, three clusters emerge. We note that this value corresponds to M = (|R| + |S|) −1 = 3, so that it might be possible for three clusters to circulate without interacting. However, a closer look at the numerics reveals that the clusters are in fact interacting and are asymptotically stable with respect to small perturbations. Thus, we conclude that beyond the parameter domain of < r − s the dynamics exhibit completely different characteristics that would require further analysis to understand.

Discussion
Inclusion of a gap in the cell cycle system is a reasonable biological modelling assumption. We have found that inclusion of the gap does not complicate the model beyond amenability to do rigorous analysis.
We have fully studied the dynamics of this system when the cells are arranged into two cell cycle clusters. We have shown that the dynamics in this subspace are almost the same as for the model without a gap. The only difference is that the -gap introduces a corresponding interval of neutral solutions near the synchronous solution. Because this solution has no basin of attraction beyond itself, it is not likely to be realized in real systems.
We also considered the stability of cyclic periodic solutions with k = M + 1 clusters; just enough clusters to guarantee that interactions occur between consecutive clusters. For these cases, we again find that the dynamics mirror those of the system with no gap.
Simulations support these analytical conclusions. We find that the inclusion of a small gap does not greatly alter the global dynamics of the system. Across a wide set of possible parameter values, solutions tend exactly to the same clustering configurations for the gap and no-gap systems.
Thus in the gap model, like the less realistic model with no gap, we find that there are large open sets of parameters for which clustering is a stable phenomenon. We conclude that one should expect to see clustering in some biological systems.
On the other hand, simulations reveal that inclusion of the gap significantly enhances the stability of the stable cyclic solutions and significantly increases the rates at which solutions converge to a stable clustered solution. In simulations the rate of convergence was around twice as fast. Analysis reveals that the gap increases the local stability of a stable cyclic solution.
For a phenomenon to be observable in biological systems, it need not only be stable, but it must be realizable on a time scale that is biologically realistic. These results show that a delay in signalling actually favours clustering.

Funding
This work was supported by the NIH-NIGMS [grant number R01GM090207].


Tuning GridFTP Pipelining, Concurrency and Parallelism Based on Historical Data

SUMMARY This paper presents a prediction model based on historical data to achieve optimal values of pipelining, concurrency and parallelism (PCP) in GridFTP data transfers in Cloud systems. Setting the correct val- ues for these three parameters is crucial in achieving high throughput in end-to-end data movement. However, predicting and setting the optimal values for these parameters is a challenging task, especially in shared and non-predictive network conditions. Several factors can a ﬀ ect the optimal values for these parameters such as the background network tra ﬃ c, avail-able bandwidth, Round-Trip Time (RTT), TCP bu ﬀ er size, and ﬁle size. Existing models either fail to provide accurate predictions or come with very high prediction overheads. The author shows that new model based on historical data can achieve high accuracy with low overhead.

Introduction
In all areas of science and industry, increasingly complex big data are being generated at the scales of petabytes and beyond. Despite the trend of moving the application to the data rather than the data to the application, large data sets still need to be moved around for increased availability, performance, and recovery purposes. Sharing, disseminating, and analyzing these large data sets pose a big challenge despite the deployment of petascale computing systems, and optical networking speeds reaching and exceeding 100 Gbps. The majority of users fail to obtain even a fraction of the theoretical speeds these high-bandwidth networks promise, due to issues such as sub-optimal protocol tuning, inefficient end-to-end routing, disk performance bottlenecks on the sending and/or receiving ends, and server processor limitations.
Different protocol parameters such as TCP pipelining, parallelism and concurrency levels play a significant role in the achievable network throughput. However, setting the optimal numbers for these parameters is a challenging problem, since poorly tuned parameters can cause underutilization of the network or they can overburden the network and degrade the performance due to increased packet loss, endsystem overhead, and other factors. In addition, the author's previous work [1], [2] sought to find a solution for an efficient big data transfer by utilizing the well-known protocol GridFTP with PCP (Pipelining-Concurrency-Parallelism). In this paper, the author proposes a prediction model based on historical data to find optimal values for pipelining, concurrency and parallelism and reports very promising experimental results. The author conducted experiments on real and emulation based tests such as LONI [3], XSEDE [4], FutureGrid [5] and Emulab [6], which verified the proposed model's excellence.

Background and Related Work
In this section, the author defines the terms pipelining, concurrency and parallelism, and provides examples and background for the proposed model.
Pipelining is profitable when the author transmits a large number of small files, (e.g. 1MB*1000 files). The pipelining function can make data transfer faster than transmitting with no optimization. Pipelining speeds up transfers containing a large number of files, which are sent back-toback without waiting for the complete command's response for the previous transfer; this can reduce latency. As a default, pipelining (pp) is set to 4 in the previous version of GridFTP, while in Globus Online [7], pipelining is set to 5, 10 or 20, depending on the file size.
Concurrency is useful for transferring multiple files via different channels simultaneously. Concurrency opens and connects multiple control channel sessions for the case of multiple-file transmission. For example, setting concurrency (cc) as 8 will drive eight GridFTP processes, which could be faster. Other factors can affect concurrency, such as CPU cores and filesystem processes.
Parallelism is also useful for transmitting different portions of the same file size via parallel data channels simultaneously. Since parallelism can divide and transfer data blocks through multiple streams, higher parallelism would be useful for large file transfers. For example, parallelism (p) can be set to 2, 4, 8 and so on. The author applies parallelism when transferring data in terms of high-speed network and buffer size tuning techniques [8]- [12]. In theory, if the author increases the number of parallelism the author can achieve high throughput, but not in all the cases. For example, in Globus Online, the parallelism level is set to 2, 4 and 8 based on the file size.
Related studies have sought to find optimal values of pipelining, concurrency and parallelism, such as Globus Online [7], which sets pipelining (pp) level to 5, 10 and 20, depending on file size. Globus Online sets parallelism (p) level to 2, 4 and 8. Please note that the goal of this paper Copyright c 2014 The Institute of Electronics, Information and Communication Engineers is to find optimal Pipelining-Concurrency-Parallelism combinations by using historical database which would be the main difference from previous approaches.

Proposed Generic Model
The author describes the proposed generic model and algorithm based on historical data in this section. The goal of this model is to find optimal PCP values by utilizing historical data to achieve high accuracy and low overhead. Table 1 presents a part of historical PCP database which is the case of FutureGrid [5]. Although not shown in Table 1, all historical data of each testbed (LONI [3], XSEDE [4] and Emulab [6] is stored in a huge PCP database. The historical data has information such as file size, number of files, bandwidth, RTT, buffer size, PCP, FAST and throughput. Each parameter (file size, number of files, bandwidth, RTT and buffer size) varies based on each testbed (FutureGrid, LONI, XSEDE and Emulab) as stated in Sect. 5. Especially, FAST is a parameter option that could make data transfer fast. However, the author does not use FAST option on FutureGrid as shown in Table 1, since FAST option usually used for large data transfers.
There are three steps for deriving the proposed generic model. A generic model is one that could be applied to any real network environments. First, the author clustered the database based on each file size such as 1MB, 2MB, 3MB, 4MB, 8MB, 16MB, 32MB, 64MB and 128MB of each testbed. Second, the author found PCP values with the highest throughput of each file size in the database. Third, the author applied k-nearest neighbors (k-NN) algorithm to derive a generic model with PCP values. As shown in Table 1, the database is organized with 1MB file size. Thus, the author can select five large throughput values with PCP based on distance. Distance can be considered as the difference between each throughput. For example, five rows (five large throughput) were first selected in Table 1. Then, the author applied k-nearest neighbors (k-NN) algorithm to find a generic PCP row in Table 1. The idea behind k-NN is to select the largest and most frequent value as the generic, within a certain distance. In this case, PCP (8-9-1) would be a generic one. Also, the author applied weight to each of the five largest throughput values based on distance to prevent a case such as more frequent one can dominate a new largest one. Thus, the author found the generic PCP values for each parameter on each testbed and generated a curve based on five sequential PCP values. The author ap- plied generic model curve with the same parameters (e.g. file size, number of files, bandwidth, RTT). Also, the author applied generic model curve with different parameters such as file size, number of files, bandwidth and RTT in order to apply to any real environments. In order to do this, the author used other historical information such as different file size or number of files. The author generated real sampling throughput values by running an actual test of certain parameters (e.g. file size, number of files). So, the author used two real sampling throughput values to find the optimal throughput values with PCP, based on different file size and number of files. The first sampling was chosen based on maximum throughput with PCP values from generic model curve and the second sampling was chosen based on maximum throughput with PCP values from another historical information (e.g. different file size, number of files). However, if the first and second samplings were found on the same PCP values coincidentally, the author could use only one sampling to find and predict an optimal throughput with PCP values. For different RTT and bandwidth, the author did not have additional historical information. So, the author used three samplings based on three maximum throughput with PCP values from generic model curve to increase an accuracy. Based on three sampling candidates, the author selected the maximum throughput as the generic one for an optimal throughput with PCP values. Overall, the author used one to three samplings to find and predict optimal throughput and PCP values with very high accuracy on different parameters.

Applying Generic Model to Real Network Cases
The author sets a generic model and is going to apply this model to real cases. As described in Sect. 5, the author categorized tests into two types. First, the author can undoubtedly apply the generic model in cases based on the same parameters the author sets. Second, the author can apply the generic model in cases based on the different parameters which is more challenging. Since the author has four types of testbeds, the author can apply real cases to one of those four types. For example, if the real user employs 1 Gbps system then Emulab [6] or FutureGrid [5] would be the best match based on RTT. If the RTT is dynamically changed, the author can apply to Emulab. On the contrary, if the user utilizes a 10 Gbps system, it would be applied to LONI [3] or XSEDE [4] based on RTT. For small RTT, the author can apply to LONI otherwise the author can apply to XSEDE. Therefore, the author can apply generic model to certain real system cases and find optimal PCP values.

Experimental Results
The author conducted experiments on the following testbeds: LONI [3], XSEDE [4], FutureGrid [5] and Emulab [6]. LONI has 10 Gbps bandwidth with 4ms RTT, while XSEDE has 10 Gbps bandwidth with 60ms RTT. Emulab has 1 Gbps bandwidth with 100ms RTT and FutureGrid has 1 Gbps bandwidth with 60ms RTT. The buffer size (Bytes) of LONI, XSEDE, FutureGrid and Emulab is 16777216, 32777216, 131071 and 13107200 respectively. Due to many graphics and limited space, the author can only show Future-Grid cases. Please also note that the author conducted on real testbeds with background network traffic, which does not assume that the network is stationary.
In LONI and XSEDE test cases, the author used file size 1MB, 2MB, 4MB, 8MB, 16MB, 32MB, 64MB and 128MB with number of files (e.g. 128, 256, 512) while in Emulab test case, the author used file size 1MB, 2MB, 4MB and 8MB. Since the disk space is quite limited in Emulab, the author could not transfer large files especially. In Future-Grid, the author used file size 1MB, 2MB, 3MB and 4MB with large numbers of files (e.g. 1000, 3000, 10000).
In the experiments, the author conducted two types of test of each testbed. The first type is based on same parameters (e.g. bandwidth, RTT, file size, number of files) and the second type is based on different parameters. So, it is important to observe the accuracy of experimental results based on different parameters which makes generic model strong to apply other network environments. Please note that the author conducted experiments 10 times based on each type. Please note that all these experimental parameters and values are determined based on each different combination of each network environments which would be practical. In addition, the results present based on parameters such as file size, number of files, bandwidth, RTT and PCP because those parameters mainly affect the throughput of data transfers. Hence, this paper focuses more on those parameters than other parameters.

Based on Same Bandwidth, RTT, File Size and Number of Files
Based on the same parameters, the author applied the same bandwidth, RTT, file size and number of files. The author applied 10 Gbps bandwidth with 4ms RTT in LONI while 10 Gbps bandwidth with 60ms RTT were used in XSEDE. The author applied 1 Gbps bandwidth and 100ms RTT for Emulab. For FutureGrid, the author applied 1 Gbps bandwidth and 60ms RTT. LONI used Eric and Oliver as a source and destination while XSEDE used Lonestar and Steele as a source and destination. Emulab used node0 and node1 as a source and destination while FutureGrid used India and Alamo as a source and destination. Figure 1 presents FutureGrid test cases and also demonstrates high accuracy (similarity between actual points and generic model's points) with the same parameters (e.g. 1 Gbps, 60ms). So, the throughput would be higher than other cases. Similarly, overall cases show highly accurate results.

Based on Different Bandwidth, RTT, File Size and Number of Files
Based on different parameters, the author applied LONI with 10 Gbps bandwidth and 8ms RTT while XSEDE was applied with 10 Gbps bandwidth and 35ms RTT. Emulab was applied with 500 Mbps bandwidth and 50ms RTT while FutureGrid was applied with 1 Gbps bandwidth and 90ms RTT. LONI used Eric and Painter cluster as a source and destination while XSEDE used Lonestar and Open Science Grid as a source and destination. FutureGrid used India and Sierra as a source and destination while Emulab used the same node0 and node1 but with different bandwidth and RTT (e.g. 500 Mbps, 50ms).
Similarly, Fig. 2 shows very promising results that the predicted point matched to the corresponding actual curve. Finally, the author can categorize any real environments into one of the testbeds (Emulab, FutureGrid, LONI and XSEDE) and find optimal throughput with PCP values based on generic model with historical data information.

Conclusion
This paper shows very promising results with a concrete prediction model and algorithms. Although it is a challenging task to find optimal PCP (Pipelining-Concurrency-Parallelism) values, the author efficiently found optimal PCP values and verified that the proposed model is strong and accurate and demonstrates promising experimental results. So, the author can apply the prediction model to the real network environments to make big data transfer fast. In future work, the author can add more experiments to extend the historical database, based on different parameters such as RTT and bandwidth. Also, the author can combine the prediction model and the previous model [2] to provide a better solution finding optimal PCP values in the real network environments.