{'fraction_non_alphanumeric': 0.030994152046783626, 'fraction_numerical': 0.013925438596491228, 'mean_word_length': 5.029308065226973, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Subword and Spatiotemporal Models for Identifying Actionable Information in {H}aitian {K}reyol

Crisis-affected populations are often able to maintain digital communications but in a sudden-onset crisis any aid organizations will have the least free resources to process such communications. Information that aid agencies can actually act on, 'actionable' information, will be sparse so there is great potential to (semi)automatically identify actionable communications. However, there are hurdles as the languages spoken will often be under-resourced, have orthographic variation, and the precise definition of 'actionable' will be response-specific and evolving. We present a novel system that addresses this, drawing on 40,000 emergency text messages sent in Haiti following the January 12, 2010 earthquake, predominantly in Haitian Kreyol. We show that keyword/ngram-based models using streaming MaxEnt achieve up to F=0.21 accuracy. Further, we find current state-of-the-art subword models increase this substantially to F=0.33 accuracy, while modeling the spatial, temporal, topic and source contexts of the messages can increase this to a very accurate F=0.86 over direct text messages and F=0.90-0.97 over social media, making it a viable strategy for message prioritization.


Introduction
The recent proliferation of cellphone technologies has resulted in rapid increases in the volume of information coming out of crisis-affected regions. In the wake of the January 12, 2010 earthquake in Haiti local emergency response services were inoperable but 70-80% of cell-towers were quickly re-stored. With 83%/67% of men/women possessing a cellphone, the nation remained largely connected. People within Haiti were texting, calling and interacting with social media, but aid agencies were not equipped to process so much information. This is because in any sudden onset crisis, this flood of information out of the region coincides with crisisresponse organizations already working at capacity as they move in. The problem definition is clear: how can we filter this information to identify actionable intelligence to support relief efforts?
The solution is complicated. There may be few resources for the language(s) of the crisisaffected population and the ratio of actionable to non-actionable information will often be very large, especially when reported through social-media and other non-official channels. In the absence of existing electronic resources models must be built onthe-fly and account for substantial spelling variations. The definition of what constitutes actionable intelligence will often be context-specific and changing, too. In the data used here 'actionable' changed quickly from Search and Rescue to any medical emergency and then to include clusters of requests for food and water. The models will therefore need to be time-sensitive or otherwise adaptive.
The system presented here attempts to address these problems, finding that the accurate identification of actionable information can be achieved with subword models, the automatic identification of topics (categories), and spatiotemporal clustering, all within a streaming architecture. It is evaluated using 40,811 emergency text messages sent in Haiti following the January 12, 2010 earthquake.

Evaluation data
Three sets of short-messages are used, all from between January 12 and May 12, 2010: 1. Mission 4636. 40,811 text-messages sent to a free number, '4636', in Haiti.
2. Radio Station. 7,528 text-messages sent to a Haitian radio station.
The Mission 4636 messages were translated, geolocated and categorized by a volunteer online crowdsourced workforce, predominantly from the Haitian diaspora, and by paid workers within Haiti (Munro, 2010). English-speaking crisis-mappers identified actionable messages and refined the coordinates and categories. The categories are a standard set of UN-defined emergency categories with some additions (48 total). The definition of an 'actionable' message was defined by the main responders to the messages, the US Coast Guard and the US Marines working with Southern Command, and included any messages with an identifiable location that contained a request for medical assistance, Search and Rescue, water-shortages, clusters of requests for food in areas not known to aid workers, security, and reports of unaccompanied minors.
The radio station and Twitter messages are not structured or geolocated. They are used here as potential false-positives in a needle-in-a-haystack scenario where the majority of messages are irrelevant. A recent Red Cross survey (2010) found that nearly half the respondents would use social media to report emergencies, so this is a realistic scenario.

Streaming models
Supervised streaming-models attempt to classify an incoming stream of unlabeled items by building up training-data on past items (Aggarwal, 2006;Hulten et al., 2001;Babcock et al., 2002). The models are often time-sensitive with training data either weighted towards or exclusively consisting of more recently seem items, especially in the context of concept drift or bounded memory (Zhang et al., 2008).
There is a penalty for applying GOLD labels to past items for training: either only a subset can be labeled or there is a time-delay. When only a subset can be labeled the scenario is similar to that of active learning (Cohn et al., 1996;Tong and Koller, 2002). When there is a delay not all past items are immediately available, meaning that short-term concept drifts might not be adapted to. In both cases, accuracy is continually evaluated over incoming items.
Here, the time-delay penalty was used for all Mission 4636 messages as it is closer to the actual scenario where each potential emergency message is ultimately read by a person but with potential delays from sudden bursts and backlogs.
The messages were divided into 100 temporally ordered sets. Each set belongs to one epoch i in the streaming architecture, R, such that R i is evaluated on R 0 , . . . , R i−1 (R 1 is evaluated on a model trained on R 0 ; R 2 is evaluated on a model trained on {R 0 , R 1 }; R 3 is evaluated on a model trained on {R 0 , R 1 , R 2 }, etc.). The accuracy is therefore calculated over R 1 , . . . , R 99 (all but the first set).
The results here report a system using a MaxEnt learning algorithm with Quasi-Newton optimization and a convergence tolerance of 10 −4 . Changing parameter settings or swapping out the learning algorithm with linear and quadratic kernel SVMs made little difference in accuracy (see discussion of other models below).
G, W , P and T were calculated directly from the messages. C and L ∃ were predicted using independent streaming models and L was clustered through tiling (see below).

Hierarchical streaming models for has-location (L ∃ ) and category (C)
The SMS protocol does not encode locations or categories. The streaming model was extended to a twolevel hierarchical architecture so that we could use (predicted) locations and categories as features.  Table 1: Examples of messages, with translation, actionable flag, location, timestamp and categories. The final two were a consistent false negative and false positive respectively. The former likely because of sparsity -places offering services were rare -and the latter because reports of possible corruption were not, unfortunately, considered actionable.
A set S, of 49 base streaming models predicted the has-location, L ∃ , feature and categories, c 0,...,47 . That is, unlike the main model, R, which predicts the 'Actionable'/'Not Actionable' division, each model S predicts either the existence of a location within the text or binary per-category membership. The predictions for each message were added to the final model as feature confidence values per-label. This is richer than simply using the best-guess labels for each model S and it was clear in early processing that confidence features produced consistently more accurate final models than binary predicted labels. In fact, using model confidence features for L ∃ actually outperforms an oracle binary has-location feature, O(L ∃ ) (see results).
The same G, W , P and T features were used for the S and R models.
As the final model R requires the outputs from S for training, and S are themselves predictive models, the L ∃ and C features are not included until the second training epoch R 1 . In the context of machinelearning for sudden onset humanitarian information processing any delay could be significant. One sim-ple solution is starting with smaller epoch sizes.

Subword features
A typical former creole, Haitian Kreyol has very simple morphology but the text message-language produces many compounds and reductions ('my family': fanmi mwen, fanmwen, fanmi m, fanmi'm, fanmim', fanmim), so it requires segmentation. There is also substantial variation due to lack of spelling conventions, geographic variation, varying literacy, more-or-less French spellings for cognates, and character sets/accents ('thank you': mesi, mési, méci meci, merci). See Table 2 for further examples and common subword patterns that were discovered across very different surface forms.
The approach here builds on the earlier work of Munro and Manning (2010), adapted from Goldwater et al. (2009), where unsupervised methods were used to segment and phonologically normalize the words. For example, the process might turn all variants of 'thank you' into 'mesi' and all variants of 'my family' into 'fan mwen'. This regularization allows a model to generalize over the different  forms even in the event of singleton word variants.
Here we incorporated the segmentation into the supervised learning task rather than model the phonological/orthographic variation as a pre-learning normalization step, as in Munro and Manning. A set of candidate segmentations and normalizations were added to our final model as features representing both the pre and post-normalization, allowing the model to arrive at the optimal training weights between the unnormalized/unsegmented and normalized/segmented variants. This meant that rather than optimizing the subword segmentation according to a Gaussian prior over unlabeled data we optimized the segmentation according to the predictive ability of a given segmentation per model. This is further from the linguistic reality of the segments than our earlier approach but the richer feature space led to an increase in accuracy in all test cases here.
The subword models were only applied to the original messages. The English translations were not included among the features as it is not realistic to assume manual translation of every message before the less labor-intensive task of identifying actionable items.

Oracle features
While the SMS protocol does not encode the geographical origin of the message, other protocols/systems do, especially those used by smartphones. Similarly, cell-tower granularity of locations might be available, phone numbers might be a priori associated with locations, or locations could be formalized within the text using methods like 'Tweak the Tweet' (Starbird and Stamberger, 2010). Therefore, it is reasonable to also simulate a scenario where the messages come pre-geocoded. We compared our results to models also containing the oracle longitude and latitude of the messages, O(L) (no attempt was made to predict L, the precise longitude and latitude -a challenging but interesting task) and the oracle existence of a location O(L ∃ ).
It is less likely that messages come precategorized but oracle features for the categories were also evaluated to compare the performance for models containing the predictive categories to ones containing the actual categories, O(c 0,...,47 ).

Spatial clustering
In addition to identifying locations, we also used the latitude and longitude to geographically cluster messages. This was to capture two phenomena: 1. Hot spots: some areas were in greater need of aid than others.
2. Clustered food requests: the definition of 'actionable' extended to clustered requests for food, but not requests from lone individuals. Figure 1 shows a Port-au-Prince (Pótoprens) neighborhood with incident reports from the text messages. The x, y axes (latitude, longitude) show the clusters given by the Ushahidi map and the z axis shows the temporal distribution of messages over a two month period. Both the spatial and temporal distributions clearly show a high frequency of both clusters and outliers.
The most accurate clustering divided the messages by longitude and latitude into tiles approximating 100m 2 , 1km 2 and 10km 2 . At each granularity, tiling was repeated with an offset by half on each dimension to partially smooth the arbitrariness of tile boundaries. This resulted in each geolocated messages being a member of 12 tiles in total, which were included as 12 features L. We were not able to find an unsupervised spatial clustering algorithm that improved the results beyond this bruteforce method of multiple tiles at different granularities (see discussion of other models tested below).

Temporal modeling and discounting
It is common to calculate a discounting function over training epochs in streaming models (Aggar- We used a slightly different method here where the time-stamp feature, T , performs this function, arriving at the relative probability for a given time period t in the final model, R (Zhang et al., 2008). It has several advantages over a simple weighted discounting function. First, t is calculated incrementally, not per training epoch, meaning that the weight θ for t is calculated until the most recently seen items. Second, it frees T to cluster according to temporal divisions other than the (arbitrary) divisions of training epochs. Finally, it allows unconstrained weights for different temporal clusters, permitting the final distribution of weights over different ts to define complex and possibly nonmonotonic discounting functions. Modeling time as a feature rather than a discounting function also made it simpler to combine temporal and spatial clustering. The feature T consisted of multiple buckets of time-stamps per message and also composite features with the O(L) tiles when present.

Other models tested
Several other machine-learning methods were tested but ultimately not reported here.
Intuitively, SVMs with non-linear kernels could more accurately model geographic divisions in the latitude and longitude dimensions and discover different combinations of features like has-location=true and category=emergency. However, we were not able to find a combination of kernels and parameter settings that demonstrated this. It is possible that we could not avoid over-fitting or that the composite features had already sufficiently captured the combinations. Munro and Manning (2010) also found gains using supervised LDA (Ramage et al., 2009), which has also previously been used for disaster response clustering (Kireyev et al., 2009). We implemented supervised LDA and unsupervised LDA topic models, but they showed modest improvements over the baseline model only. We presume that this is because when we add the predicted categories from our (supervised) category learning task, they already contained enough information about topic divisions.
We looked at several methods for spatio-temporal clustering including cliques (Zhang et al., 2004), kmeans (Wagstaff et al., 2001), and targeted low frequency clusters (Huang et al., 2003). The change in accuracy was negligible but the exploration of methods was by no means exhaustive. One exception was using nearest-neighbor spatiotemporal clustering, however the gains were predominantly repeated messages from the same person and thus already captured by the source feature, P .
Several systems have been built by humanitarian organizations for filtering/prioritizing messages, mostly keyword and memory-based. All are currently less accurate than the baseline system here and their predicted outputs gave no gains as features.
The SwiftRiver system built on NLTK library (Bird et al., 2009) was the most promising, only underperforming the baseline by F=0.01.

Results
The results in Table 3 show that a combination of streaming models with subword models improves the accuracy of identifying actionable messages. All increases in accuracy are significant relative to the baseline.
The temporal feature, T , alone gives F=0.045 increase in accuracy indicating that there is substantial concept drift and an adaptive model is necessary for accurate classification.
The subword models, W , increase the gain to 0.119 showing that despite Kreyol being a morphologically simple language the variation in spellings and compounds is significant.  . The Pre-filtered spatial clusters contains the same architecture/features as the most accurate model, but with those messages not containing an identifiable location (and therefore automatically non-actionable) stripped from the training and test data. The final Radio station and Twitter models used the messages sent to a radio station and Twitter as the non-actionable items, using the same training model as All non-oracle and spatial clusters.

Oracle vs predicted outputs
Comparing the oracle values and predicted outputs from the categories and the identification of messages containing locations, O(C), O(L ∃ ), C, L ∃ , we see that the predictive model for categories only slightly underperforms the oracle, but the predictive model for locations outperforms the oracle model. We suspect that this is because the predictions are probabilities, not binary indicators of the existence of a location. Therefore, the richer real-valued feature space led to greater information for the final model despite any predictive errors in this base model. Another reason can be clearly seen in the precision, 0.746 for the O(L) model, one of the highest precision-to-recall ratios. The final model is clearly giving too much weight to the existence of a location as a predictor of an actionable label.
Smoothing O(L) makes little difference as it is a high-frequency binary feature, but the greater range of probability values in L are necessarily more sparse and therefore more de-weighted by smoothing.
Identifying locations is one area that could be ex-panded on greatly. Initial experiments with namedentity recognition were abandoned when it was clear that the data was too sparse and too different from existing data sets, but perhaps text-message-specific named-entity recognition methods could lead to even more accurate results for identifying locations.

Spatial clustering
By adding spatial clusters we get the greatest leap in accuracy: F=0.756, a substantial F=0.549 over the baseline. This is strong evidence in favor of extending text-only messaging to location-aware messaging. As with the prediction of locations, it is likely that methods for spatial clustering other than bruteforce bucketing could lead to more accurate results, but as stated earlier we were not able to identify any.
Combining the base streaming model outputs with all features leads to the most accurate model. It is expected that this would produce the best results, but at F=0.855 we have a very significant gain over any of the models implementing only single-stream learning, or without the full feature space.

Pre-filtering
Somewhat counterintuitively, pre-filtering messages without known locations (in both training and test data) decreased the accuracy to F=0.428. Oracle filtering of true-negative test items will not change recall and can only increase precision, so clearly there is 'signal' in the 'noise' here. Analysis of the messages showed that many non-actionable messages were not related to emergencies at all (general questions, requests for work, etc), as were many messages without identifiable locations. That is, people who tended to not send actionable information also tended to not include locations. Because of this correlation, the content of messages without locations becomes useful information for the model.
A careful analysis of the training models confirms this: the word and subword features for nonactionable messages with no locations had non-zero weights. Pre-filtering them therefore resulted in an impoverished training set.
It is standard practice in the humanitarian industry to pre-filter messages that are easily identified as non-actionable (for obvious reasons: it reduces the manual processing), which is what occurred in Haiti -only about 5% of messages were treated as 'actionable' candidates. The results here indicate that if manual processing is extended to automated or semi-automated processing this strategy needs to change, with all potential training items included in the models.

Comparison to non-emergency messages
For the social media scenarios where we combined the actionable test items with the messages sent to a radio station and Twitter the accuracy was highest of all. This is a promising result for seeking actionable information in non-traditional sources. The radio station is particularly promising as almost all the messages where in Haitian Kreyol and spoke about the same locations as the 4636 messages.
While the Twitter messages were extremely accurate at F=0.969, the majority of the tweets were in English or French from people outside of Haiti, so this model was at least in part about language identification, a much simpler task and less novel from a research perspective. Nonetheless, while at least part of the accuracy is easily explained this was the most sparse test set with only 0.025% actionable items, so the application scenario is very promising.

Prioritization
Applying ROC analysis, the methods here could speed up the prioritization of actionable messages by a factor of 10 to 1 based on content alone. That is, on average an actionable message falls within the 90th percentile for probability of being actionable. By including spatial clustering this becomes the 98th percentile. There is great potential for improvements but the methods reported here could already be used to efficiently prioritize the triage of the most important messages within a semi-automated system. 6 Related Work 6.1 trillion text messages were sent in 2010 -more than emails and social network communications combined (ITU, 2010), especially in areas of great linguistic diversity (Maffi, 2005). This easily makes it the least well-studied method for digital communication relative to the amount digital information being generated.
The lack of research is probably due to obstacles in obtaining data. By contrast Twitter's API has led to much recent research, primarily in sentiment analysis Alexander Pak, 2010;Sriram et al., 2010) and unsupervised event detection (Petrović et al., 2010). The task of identifying sentiment is different to filtering actionable intelligence, we were not training on tweets, and Twitterlanguage is reportedly different from text-messagelanguage (Krishnamurthy et al., 2008). However, there are similarities relating to problems of message brevity and the ability to extend the featurespace. For example, Sriram et al. (2010) also found that modeling the source of a message improved accuracy. Eisenstein et al. (Eisenstein et al., 2010) show promising results in identifying an author's geographic location from micro-blogs, but the locations are course-grained and rely on a substantial message history per-source.
In recent work with medical text messages in the Chichewa language, we compared the accuracy of rule-based and unsupervised phonological normalization and morphological segmentation when applied to a classification task over medical labels, showing substantial gains from subword models (Munro and Manning, 2010).
A cluster of earlier work looked at SMS-SPAM in English (Healy et al., 2005;Hidalgo et al., 2006;Cormack et al., 2007) and Beaufort et al. (2010) used a similar preprocessing method for normalizing text-messages in French, combining rule-based models with a finite-state framework. The accuracy was calculated relative to BLEU scores for 'correct' French, not as a classification task.
Machine-translation into a more well-spoken language can extend the potential workforce. Early results are promising (Lewis, 2010) but still leave some latency in deployment.
For streaming architectures, Zhang et al. (2008) proposed a similar method for calculating per epoch weights as an alternative to a discounting function with significant gains. Wang et al. (2007) also looked at multiple parallel streams of text from different newspapers reporting the same events but we couldn't apply their method here as there were few instances of the same pairs of people independently reporting two distinct events. The two-tiered architecture used here is similar to a hierarchical model, the main difference being epoch-based retraining and the temporal offset of the base models feeding into the final one. Joint learning over hierarchical models has been successful in NLP (Finkel and Manning, 2010) but to our best knowledge no one has published work on joint learning over hierarchical streaming models, in NLP or otherwise.

Conclusions
From models optimized over words and ngrams to one including temporal clustering and subword models the accuracy rises from F=0.207 to F=0.326. Clearly, the words that someone has chosen to express a message is just one small aspect of the context in which that message is understood and by combining different learning models with richer features we can prioritize actionable reports with some accuracy. With spatial clustering this rises to F=0.885, indicating that geographic location was the single most important factor for prioritizing actionable messages.
These results are only a first step as there is great potential for research identifying more accurate and efficient learning paradigms. A growing number of our communications are real-time text with frequent spelling variants and a spatial component (tweets, location-based 'check-ins', instant messaging, etc) so there will be increasingly more data available in an increasing variety of languages.
It is easy to imagine many humanitarian applications for classifying text-messages with spatiotemporal information. Social development organizations are already using text messaging to support health (Leach-Lemens, 2009), banking (Peevers et al., 2008), access to market information (Jagun et al., 2008), literacy (Isbrandt, 2009), and there is the potential to aid many of them. Even more importantly, this work can contribute to information processing strategies in future crises. Had a system like the one presented here been in place for Haiti then the identification of actionable messages could have been expedited considerably and a greater volume processed. I coordinated the Mission 4636 volunteers who were translating and mapping the messages in real-time, so this research is partially motivated by the need to see what I could have done better, with a view to being better prepared for future crises.
The results for social media are especially promising. In total, the tweets contained 1,178,444 words -the size of approximately 10 novels -but if there was just one real emergency among them, there was a 97% chance it would rise to the top when ordered by actionable confidence.