We conclude by discussing two extensions to the model, specificity tuning and conversation start detection, both of which are promising but do not currently yield practical improvements. Simultaneous conversations seem to arise naturally in both informal social interactions and multi-party typed chat. Aoki et al.'s (2006) study of voice conversations among 8-10 people found an average of 1.76 conversations (floors) active at a time, and a maximum of four. In our chat corpus, the average is even higher, at 2.75. The typical conversation, therefore, does not form a contiguous segment of the chatroom transcript, but is frequently broken up by interposed utterances from other conversations. Disentanglement (also called thread detection [Shen et al. 2006] , thread extraction [Adams and Martell 2008] , and thread/conversation management [Traum 2004] ) is the clustering task of dividing a transcript into a set of distinct conversations. It is an essential prerequisite for any kind of higher-level dialogue analysis. For instance, consider the multi-party exchange in Figure 1 . Contextually, it is clear that this corresponds to two conversations, and Humans are adept at disentanglement, even in complicated environments like crowded cocktail parties or chat rooms; in order to perform this task, they must maintain a complex mental representation of the ongoing discourse. Moreover, they adjust their conversational behavior to make the task easier, mentioning names more frequently than in spoken or two-party typed dialogues (O'Neill and Martin 2003) . This need for adaptation suggests that disentanglement can be challenging even for humans, and therefore can serve as a useful stress test for computational models of discourse. Disentanglement has two practical applications. One is the analysis of pre-recorded transcripts in order to extract some kind of information, such as question-answer pairs or summaries. These tasks should probably take as input each separate conversation, rather than the entire transcript. Another application is as part of a user-interface system for active participants in the chat, in which users target a conversation of interest which is then highlighted for them. Aoki et al. (2003) created such a system for speech, which users generally preferred to a conventional system-when the disentanglement worked! We begin in Section 2 with an overview of related work. In Section 3, we present a new corpus of manually annotated chat room data and evaluate annotator reliability. We give a set of metrics (Section 3.2) describing structural similarity both locally and globally. In Section 4, we propose a model which uses supervised pairwise classification to link utterances from the same conversation, followed by a greedy inference stage which clusters the utterances into conversations. Our system uses time gap and utterance content features. Experimental results (Section 5) show that its output is highly correlated with human annotations. Finally, in Sections 6 and 7, we investigate two extensions to the basic model, specificity tuning and automatic detection of conversation starts. To our knowledge, this is the first work to evaluate interannotator agreement for the disentanglement task. It is also the first to use a supervised method to learn weights for different feature types, rather than relying on cosine distance with uniform or handtuned feature weights. It supplements standard word repetition and time gap features with other feature types, including very powerful features based on name mentioning, which is common in Internet Relay Chat. Several threads of research are direct attempts to solve the disentanglement problem. The closest to our own work is that of Shen et al. (2006) , which performs conversation disentanglement on an online chat corpus. Aoki et al. (2003 Aoki et al. ( , 2006 analysis, extracting groups of speakers who talk to one another. This can be considered a disentanglement task, although, as we will see (Section 5), the assumption that each speaker participates in only one conversation is flawed. Adams and Martell (2008) and Shen et al. (2006) publish results on humanannotated data; although we do not have their corpora, we discuss their evaluation metrics (Section 3.2) and give a comparison to our own results herein (Section 5). Aoki et al. (2006) Adams and Martell (2008) and Shen et al. (2006) treat disentanglement in the same way we do, as a clustering task where the objects to be clustered are the individual utterances. Both their algorithms define a notion of distance (based on the cosine) and a threshold parameter determining how close to the cluster center an utterance must be before the clustering algorithm adds it. This stands in contrast to our own supervised approach, where the distance metric is explicitly tuned on training data. The supervised method has the advantage that it can weigh individual feature types based on their predictivity-unsupervised methods combine features either uniformly or using heuristic methods. There is also no need for a separate tuning phase to determine the threshold. On the other hand, supervised methods require labeled training data, and may be more difficult to adapt to novel domains or corpora. The remaining papers treat the problem as one of clustering speakers, rather than utterances. That is, they assume that during the window over which the system operates, a particular speaker is engaging in only one conversation. Camtepe et al. (2005) state an explicit assumption that this is true throughout the entire transcript; real speakers, by contrast, often participate in many conversations, sequentially or sometimes even simultaneously. Aoki et al. (2003) analyze each 30-second segment of the transcript separately. This makes the single-conversation restriction somewhat less severe, but has the disadvantage of ignoring all events which occur outside the segment. Acar et al. (2005) attempt to deal with this problem by using a fuzzy algorithm to cluster speakers; this assigns each speaker a distribution over conversations rather than making a hard assignment. However, the algorithm still deals with speakers rather than utterances, and cannot determine which conversation any particular utterance is part of. Another problem with these two approaches is the information used for clustering. Aoki et al. (2003) and Camtepe et al. (2005) detect the arrival times of messages, and use them to construct an affinity graph between participants by detecting turn-taking behavior among pairs of speakers. (Turn-taking is typified by short pauses between utterances; speakers aim neither to interrupt nor leave long gaps.) Aoki et al. (2006) find that turn-taking on its own is inadequate. They motivate a richer feature set, which, however, does not yet appear to be implemented. Acar et al. (2005) add word repetition to their feature set. However, their approach deals with all word repetitions on an equal basis, and so degrades quickly in the presence of "noise words" (their term for words which are shared across conversations) to almost complete failure when only half of the words are shared. Adams and Martell (2008) and Shen et al. (2006) use a more robust representation for lexical features: Term frequency-inverse document frequency (TF-IDF) weighted unigrams, as often used in information extraction. This feature set works fairly well alone, although time is also a key feature as in the other studies. Adams and Martell (2008) also investigate WordNet hypernyms (Miller et al. 1990 ) as a measure of semantic relatedness, and use the identity of the speaker of a particular utterance as a feature. It is unclear from their results whether these latter two features are effective or not. Volume 36, Number 3 To motivate our own approach, we examine some linguistic studies of discourse, especially analysis of multi-party conversation. O'Neill and Martin (2003) point out several ways in which multi-party text chat differs from typical two-party conversation. One key difference is the frequency with which participants mention each others' names. They hypothesize that name mentioning is a strategy which participants use to make disentanglement easier, compensating for the lack of cues normally present in face-to-face dialogue. Mentions (such as Gale's comments to Arlie in Figure 1 ) are very common in our corpus, occurring in 36% of comments, and provide a useful feature. Another key difference is that participants may create a new conversation (floor) at any time, a process which Sacks, Schegloff, and Jefferson (1974) calls schisming. During a schism, a new conversation is formed, not necessarily because of a shift in the topic, but because certain participants have refocused their attention onto each other, and away from whoever held the floor in the parent conversation. Despite these differences, there are still strong similarities between chat and other conversations such as meetings. Meetings do not typically allow multiple simultaneous conversations, but analogues to schisms do exist, in the form of digressions or "subordinate conversations," in which the speaker addresses someone specific, who is then expected to answer. Some meeting analysis systems attempt to discover where these digressions begin, who is involved in them, and who has the floor when they end; features used in this work are relevant to disentanglement. The task of automatically determining the intended recipient of an utterance in a meeting is called addressee identification. It requires detecting digressions and identifying their participants. Several studies attempt this task. Jovanovic and op den Akker (2004) and Jovanovic, op den Akker, and Nijholt (2006) perform addressee identification using a complex feature set including linguistic cues like pronouns and discourse markers, temporal information, and gaze direction. They also find that addressee identity can be annotated with high reliability (κ = .7 for one set and .8 for another). Traum (2004) discusses the necessity for addressee identification and disentanglement in the design of a system for military dialogues involving virtual agents. Subsequent work (Traum, Robinson, and Stephan 2004) develops a rule-based system with high accuracy on addressee identification. Another meeting-related task is floor tracking, which attempts to determine which speaker has the floor after each utterance. This task involves modeling the coordination strategies which speakers use to acquire or give up the floor, and so provides a good model of an ongoing conversation. A detailed analysis is given in Chen et al. (2006) A somewhat related area of research involves environments with higher latency than real-time chat: message boards and e-mail. Content matching approaches tend to work better in these settings, because while many chat messages are backchannel responses or discourse requests (Yes, Why? and so forth), longer posts tend to be contentful. Of the two tasks, e-mail is easier; Yeh and Harnly (2006) find that heuristic information from message headers can be useful, as can content-based matching such as detecting quotes from earlier messages. Wang et al. (2008) , an analysis of a student discussion group, is the work on which Adams and Martell (2008) classifier. The global partitioning problem was identified as correlation clustering, an NP-hard problem, by McCallum and Wellner (2004) . Finally, we briefly mention some work which appeared after we developed the system described here. Wang and Oard (2009) is another system that uses TF-IDF unigrams, but augments these feature vectors using the information retrieval technique of message expansion. They report results on our corpus which improve on our own. Adams (2008) attempts to use not only WordNet but Latent Dirichlet Allocation to describe semantic relatedness. He finds both techniques ineffective. In addition, he annotates a large corpus of Internet Relay Chat and similarly finds that annotators have trouble agreeing. Elsner and Schudy (2009) explore different partitioning strategies, improving on the greedy algorithm that we present. Our data set is recorded from IRC channel ##LINUX at free-node.net, using the freely available gaim client. ##LINUX is an unofficial tech support line for the Linux operating system, selected because it is one of the most active chat rooms on freenode, leading to many simultaneous conversations, and because its content is typically inoffensive. Although it is notionally intended only for tech support, it includes large amounts of social chat as well, such as the conversation about factory work in Figure 1 . The entire data set contains over 52 hours of chat, but we devote most of our attention to three annotated sections: development (706 utterances; 2:06 hr) and test (800 utterances; 1:39 hr), plus a short pilot section on which we tested our annotation system (359 utterances; 0:58 hr). We recruited and paid seven university students to annotate the test section. All had at least some familiarity with the Linux OS, although in some cases very slight. Annotation of the test data set typically took them about two hours. In all, we produced six annotations of the test set. 2 We have four annotations of the pilot set, by three volunteers and the experimenters. The pilot set was used to prototype our annotation software, and also as a validation corpus for our system. The development set was annotated only once, by the experimenter. This data set is used for training. Our annotation scheme marks each utterance as part of a single conversation. Annotators are instructed to create as many or as few conversations as they need to describe the data. Our instructions state that a conversation can be between any number of people, and that, "We mean conversation in the typical sense: a discussion in which the participants are all reacting and paying attention to one another . . . it should be clear that the comments inside a conversation fit together." The annotation system itself is a simple Java program with a graphical interface, intended to appear somewhat similar to a typical chat client. Each speaker's name is displayed in a different color, and the system displays the elapsed time between comments, marking especially long pauses 2 One additional annotation was discarded because the annotator misunderstood the task. Volume 36, Number 3 in red. Annotators group utterances into conversations by clicking and dragging them onto each other. Before discussing the annotations themselves, we will describe the metrics we use to compare different annotations; these measure both how much our annotators agree with each other, and how well our model and various baselines perform. Comparing clusterings with different numbers of clusters is a non-trivial task, and metrics for agreement on supervised classification, such as the κ statistic, are not applicable. To measure global similarity between annotations, we use one-to-one accuracy. This measure describes how well we can extract whole conversations intact, as required for summarization or information extraction. To compute it, we pair up conversations from the two annotations to maximize the total overlap by computing an optimal maxweight bipartite matching, then report the percentage of overlap found. 3 One-to-one accuracy is a standard metric in unsupervised part-of-speech tagging (e.g., Haghighi and Klein 2006), and is equivalent to mention-based CEAF (Luo 2005) for coreference resolution. If we intend to monitor or participate in the conversation as it occurs, we will care more about local judgments. The local agreement metric is a constrained form of the Rand index for clusterings (Rand 1971) which counts agreements and disagreements for pairs within a context k. We consider a particular utterance: The previous k utterances are each in either the same or a different conversation. The loc k score between two annotators is their average agreement on these k same/different judgments, averaged over all utterances. For example, loc 1
It is worth noting that REF have also advocated to utilize time gap and people mentions similar to the proposed method of this work.
Disentangling Chat
Computational Linguistics
Computer Science