{'fraction_non_alphanumeric': 0.037379192723138145, 'fraction_numerical': 0.01568125829069547, 'mean_word_length': 4.527363184079602, 'pattern_counts': {'":': 1, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Supervised Approach To The Interpretation Of Imperative To-Do Lists

To-do lists are a popular medium for personal information management. As to-do tasks are increasingly tracked in electronic form with mobile and desktop organizers, so does the potential for software support for the corresponding tasks by means of intelligent agents. While there has been work in the area of personal assistants for to-do tasks, no work has focused on classifying user intention and information extraction as we do. We show that our methods perform well across two corpora that span sub-domains, one of which we released.


Introduction
To-do lists are pervasive and offer a concise representation of tasks that need to be accomplished (Bellotti et al., 2004;Gil et al., 2012), with studies showing that up to 60% of the population use them (Jones and Thomas, 1997). To-do tasks are often expressed as short utterances and written in list form. Examples of to-do task are "Buy swimsuit", "Call mom", and "Hotel reservation".
With the growing popularity of personal assistants, such as Apple's voice-based Siri, the need for understanding and executing tasks such as those embodied in to-do tasks continues to grow; conversely, there is great potential in automating the resolution of to-do tasks given the plethora of mobile and desktop applications that currently exist. This paper focuses on describing several models we have constructed to interpret todo tasks. As far as we know, there has been little research in parsing and classifying to-do tasks, which entirely consists of short requests couched either as imperative sentences or as fragments not containing a verb; neither imperatives nor fragments are as frequent in corpora as other forms in which a user's intention can be expressed, as we will discuss in Section 2.
Execution of these tasks can be achieved by invoking an appropriate intelligent agent (IA), which will act upon the task (Gil et al., 2012). For example, "Call mom", would yield: {agent}=xcally, {arguments}= xcontact=momy and would look up mom as contact and dial via the phone application. IAs are described in Section 3.
The challenges with processing to-do tasks are: • Short length of utterances, which yield poor results with current methods (Han and Baldwin, 2011).
• Missing head verb, which makes classification more difficult if missing. For example, "Hotel reservation" lacks the head verb, schedule.
• Disambiguation of named entities, which include products to purchase, persons with whom to communicate, companies, etc.
• Processing commands in imperative form, for which in most systems are well formed and don't contain many named entities.
In this paper, we discuss our approach to mapping a to-do task to a corresponding IA; this includes extracting its arguments and classifying them as concerns their types. We will describe the corpus we built, the preprocessing steps we devised, and the features we used to inform our classifiers.
Finally, we will demonstrate the generality of our approach by applying it to a compiled and annotated corpus with a partially separate domain.

Related Work
From a linguistic point of view, to-do tasks are either expressed with (short) imperative sentences or with fragments that do not contain a verb. Imperatives have not been studied very extensively in NLP, since they (not surprisingly) do not occur frequently in corpora of "standard" English, such as newspaper articles. For example, the PARC 700 dependency bank (King et al., 2003) is a random sample of 700 utterances taken from the Wall Street Journal corpus (Marcus et al., 1994) and contains only seven utterances containing at least one imperative.
However, even in datasets that focus on dialogue and tasks to be performed, imperatives do not occur that often. To start with, as (Levinson, 1983) notes, the imperative is rarely used to issue requests in English. This seems to be borne out even in interactions with personal assistants, even if, beyond anectotal evidence, distributional analyses of such data are not widely available.
One such analysis is provided by (Tur et al., 2014), who analyzes interactions between users and an entertainment personal assistants. They found that 31.21% of such utterances start with a VB tag (an upper bound for imperatives), another 31.64% with tags representative of NPs and wh-NPs (the remaining 37% of utterances is left unspecified): so even when communicating with an entertainment personal assistants, users use imperative sentences only about 1 3 of the time (this frequency is not rare, but much lower than one would expect given the circumstances). In their work on evaluating the performance of personal assistants such as Siri, Google Now and Cortana, Jiang et al. (2015) show that 67% of user action types are commands, but they don't specify the proportion of imperatives within those.
A substantial percentage of to-do tasks are expressed as fragments, such as "Hotel reservation". The literature on fragments is also rather sparse, other than as concerns ellip-sis (Kempson et al., 2015)-but it is not clear that these fragments are in fact ellipsis. Even tweets, the shortest of today's social media language, are often grammatically ill-formed, contain a main verb.
If we now turn to the interpretation of to-do tasks, Gil et al. (2012) explored different kinds of intelligent assistance for to-do lists. Gil et al. (2012) provides a manual data entry to categorize the to-do task and Jiang et al. (2015) yields a performance evaluation, however, neither automatically categorize the IA as we do. Likewise (Tur et al., 2014) distinguishes between requests that are covered by the current interpreter and those that are not, but does not interprets them in anyway.
In this work, we also tackle argument extraction. 1 Our method of extracting verbs and their arguments is similar in spirit to efforts like OpenIE (Fader et al., 2011) and NeLL (Mitchell et al., 2015). Our work is specifically targeted at to-do lists where sentences are very short and telegraphic. Ope-nIE and NeLL learn from a large repository of knowledge, whose language is not telegraphic, and mostly well formed.
Earlier work in argument extraction includes processing sequences of executable actions for the Windows operating system by Branavan et al. (2009). Other argument extraction work includes efforts in deep learning by Meerkamp et al. (2017) for boosting precision of existing extraction systems. However, our work covers a broader domain of general English to-do tasks and does not fit in any existing method of tagging arguments.
The approach taken by Ghani et al. (2006) is the most similar to ours with regards to their argument extraction for textual product descriptions. However, their argument set is restricted to a predefined set where our model learns the arguments to extract.

Corpora
This work involves two to-do task data sets: the first is a proprietary corpus 2 and the sec-  ond is a publicly available corpus we have built and released 3 . The corpus consists of IA and argument annotations. The IA type was formulated from an initial analysis of the corpus and several iterations of annotation guideliness that led us to the final list given in Table 1. The argument annotations are tokens associated with an IA annotation and provide additional context helpful in task resolution. A complete list of arguments are given in Table 2 and described in more detail in Section 3.3.

Corpus A
Corpus A was collected from two sources: publicly available online sources (see Appendix A for a full list of sources) and private sector data. We annotated a random sample of 3,169 to-do tasks with one utterance per task and doubly annotated 1,342 to compute the kappa score. We then divided the 3,169, into usable non-exceptions (1,690) and unusable exceptions (1,479) to-do tasks. A task was considered as an exception for one of the following reasons: 3 https://github.com/plandes/todo-task/ ‚ the to-do task itself is ambiguous (i.e."flowers"-plant them or buy them?) ‚ language is not English (i.e."compra flores") or meaningless (i.e."mkmkmk") ‚ illegal activity (i.e. "buy drugs") ‚ generic professional (i.e."first quarter presentation") The 1,690 non-exception tasks were annotated with IA labels and their respective arguments. IAs with less than 15 utterances were pruned as anything less proved to be insufficient training data. This left 1,611 tasks with utterances used for training and testing.

Corpus B
We created a Corpus B composed of 102 volunteer contributed personal to-do tasks and 498 Trello 4 to-do tasks with IA annotations. A subset of this data, including 68 volunteer and 218 Trello scraped to-do tasks, was used to test and train the model. The Trello data was sourced from public boards that allow for redistribution and the volunteers agreed to release their data for public distribution. This  corpus does not contain argument annotations given the purpose was to provide a way to reproduce IA classification results.

Argument Annotations
There is a zero to many relationship between IAs and arguments. For example, "grocery store" is tagged as a buy IA with no arguments. Table 2 lists the argument annotations and their distribution in the corpus. Note that some arguments span multiple IAs while others are specific to a particular IA. An additional descriptor list annotation was provided to address edge cases where existing modifiers were insufficient. For example, the descriptor list would be populated with a URL since there is no corresponding argument for calendar appointment.
A fully annotated task of "Get new sweater for John before Christmas" is shown in Figure 1 and has the annotation {agent}=xbuyy, {arguments}=xitem=sweater, person=John, holiday=Christmasy.
An inter-coder agreement metric was computed to get an idea of how consistent the corpus was being annotated using Fleiss' kappa (Fleiss, 1971).
Early efforts were made to create a consistent corpus with sufficient overlap and anno-tation guidelines, in the face of subtle differences. This work proved worthwhile as the coder agreement of IA classification produced an agreement 0.679 over 848 tasks annotated by two annotators.
The Corpus B contains no argument annotations.

Corpus Processing
In earlier experiments, significant propagation errors in the pipeline were found that resulted in poor IA and argument classification due to incorrect part of speech (POS) tagger main verbs (described in Section 5.2). To overcome, this we added a pre-processing step to enhance the Stanford Parser and created features from the parsed utterances to train and test the models. This process includes: 1. Extend the Stanford Named entity recognition (NER). First, we compiled named entity lists that are supplied to the named entity recognition system at parse time and then we parsed the annotations.
2. Build the first verb model. To ameliorate errors caused from issues of parsing short utterances, the POS tagger was enhanced by creating the first verb model.

3.
Apply the first verb model to the corpus.
This prevents significant error propagation by correcting the first POS tag created in the previous step. This correction is seen later as IA and argument models utilize the main verb parsed at this step.

Extending Named Entity Recognition
NER proved to be crucial as it provides additional context for classification. Two sets of features were created using both the NER (Finkel et al., 2005) and the Stanford TokensRegex (Chang and Manning, 2014). The latter was enhanced to include a set of static word lists (NER lists) generated from Wikidata (Wikidata, 2015), Open Product Data (Data, 2016), and the term lists.
The Wikidata lists were created with a set of SPARQL (Prudhommeaux and Seaborne, 2006) queries that included a primary term, and for some lists, a sublist term. The term lists also were annotated with three levels of categories, gender for human names, and list type (i.e. modifiers, attributes and products). These NER lists were used to create a Stanford TokensRegex formatted regular expression input file and subsequently used during parse time for each to-do task. The combined Wikidata and the term list produced a total of 85,777 unique entities.

Building the First Verb Model
The most crucial error made by the POS tagger was incorrectly tagging the first token of utterances as non-verbs. The input to the first verb model are features of the parsed utterances given by the Stanford Parser and the class is the main verb, which is used by the IA and argument models. Out of 1,690 utterances, 653 (38.6%) have the main verb annotation in the Corpus A, which is similar to the initial word utterance relative POS tag frequences (31.21%) of the Tur et al. (2014) VPA and web search datasets.

Bootstrap the Model
For the first parsing of the corpus this error was corrected by reassigning the POS tag of the initial token using the following criteria: a) identified as a present tense verb tag in WordNet 5 (Miller, 1995) and b) identified as not a color as in "yellow curry" is a noun and not a verb as in "yellow your teeth from coffee".
Each annotation included a token with a verb POS tag that differentiated each to-do task across IAs, which was in turn used as a feature. This was used to test the accuracy of the procedure to replace the POS tag with a verb tag. However, this method proved to be detrimental for to-do tasks containing homonyms.

Build the Rule Based Model
The Stanford POS tagger performed with an F-measure of 0.88. A rule set classifier (Frank and Witten, 1998)  After creating the rule based model as just described, we applied the rule based model to correct the first POS tag of all of the utterances in the corpus using the Stanford Parser. The input to this step are the utterances and annotations from the corpus and the output is a tree of parsed items, which are used as features for the IA and argument. 6 http://www.cs.waikato.ac.nz/~ml/weka/    Table 3: Semantic Role Labeler example classification for "Get new sweater for John before Christmas" (see Figure 1).

Build the Classification Models
In this section we cover the techniques to process to-do tasks, classify the IA, and perform argument extraction.

Argument Extraction
The argument model is trained first as the IA model uses its labels as features.
A semantic role labeler (SRL) was used for many of the features in the argument model. There are one or more uses of a verb depending on the context, and each use of the verb has its own argument set. For this work, Proposition Bank (Palmer et al., 2005) was used for the operative verb of the utterance.
The SRL and POS tagging of the example given in Figure 1 is shown in Table 3. The head-dep label and function-tag represent how a parent and child token node are related in a head dependency tree (De Marneffe et al., 2006). This example's columns are further explained in Table 4.
The IA model was trained and tested (see Section 7) using WEKA on a per-IA basis. The ClearNLP 7 (Choi, 2014) semantic role labeling parser that was trained on Proposition Bank verb classes was used to provide features to the argument model. These feature's descriptions are listed in Table 4.
All feature set permutations were used in a ten-fold cross validation with the highest performing sets listed in Table 5. Results are given by IA in Table 8, which do not include techniques that failed (i.e. raw word vectors for the word w n ). 7 http://github.com/emorynlp/nlp4j

Feature Description
dep SRL dependency of parent, which is always relative to a root verb head-dep Proposition Bank argument (i.e.
PERSON, ORGANIZATION) pos wn POS tag (i.e. VB, NN) prev-pos wn´1 POS tag next-pos wn`1 POS tag stopword if wn a stop word-common/filler words with little meaning (i.e. for, the, a) tm-ner-tag Taskmatch NER list entity (i.e. HOLIDAY)) next-tm-ner-tag wn`1 Taskmatch NER list entity index the token's index into the sentence (for word wn token-index=n) Table 4: Argument features where w n is the N th word in the to-do task utterance.

Intelligent Agent Classification
The main verb feature is the head root node of the dependency tree. If there is no parsed head node the POS tag of the first token of the utterance is used. For example, "Buy swimsuit" correlates closely to the buy IA. The main verb was the first feature when creating the model, and by itself, provided an impressive accuracy 55% by itself.   Table 4 for more each feature's description).
We used the lemmatized form of the token for word count and cosine similarity features. Let c wa " Countpw, aq be the count of word  w for IA a and C a be the set of word counts per IA such that c wa P C a . We limit C to contain the highest n frequency counts with n " |C a | and hold n constant for all IAs as a hyper parameter. We use the word count aggregation across C a as feature: Significant performance gains were achieved by increasing n from 5 to 15 with the W C a feature. Now we define a mapping from word to a word distribution over C marginalizing over the word frequency: For example, for the buy IA utterances "Purchase a shirt. Iron shirt.": C buy " tc purchase " 1, c a " 1, c iron " 1, c shirt " 2u and qppurchase, buyq " 1{4, qpa, buyq " 1{4, qpiron, buyq " 1{4, qpshirt, buyq " 2{4.
In addition, word vector cosine distance (Mikolov et al., 2013) was calculated with Word2vecJava (Ko, 2015) using the the English Wikipedia pre-trained word vector data set (Mahoney, 2006). The word vector library was used by summing over the token cosine similarity and weighting it with the word frequency distribution from equation 2.
The cosine similarity feature is created by calculating the MLE across all IAs A to create cosine similarity (CS) for each sentence S: This feature contributed to a 5 point increase in F-measure in all results reported in Table 6.

An Illustrative Example
To illustrate how to-do tasks are handled we will use the example "new christmas sweater for john". Once we receive the utterance the following happens: 1. Tokenize and sentence chunk, and POS tag the utterance using the modified version of the Stanford POS Tagger.
2. Create a head tree and tag tokens with Proposition Bank data using the semantic role labeler.
3. Classify IA as "buy" using the word counts, named entities and word vectors (see Section 5.2).
4. For each token in the utterance using the parameter model for IA "buy" classify an argument "sweater" as "item", "john" as "person" and "christmas" as "holiday".    Table 5 for feature descriptions.
5. Concatenate contiguous tagged tokens of same argument type. In this example there are none, but if the example used "blue sweater", both would be tagged as "item" and be returned as one argument.

Results
Since testing was exhaustive, only noteworthy performance results for the IA and argument models are given. All subsets of reported features along with hyperparameter tuning was tried. The IA classification and baseline results are given in Table 6 and argument classification results are given in Table 8. Note that the argument classification results are for arguments and classify over all IAs, including the low count IAs shown in Table 1.

Intelligent Agent Classification
The baseline was created from the majority IA class (see Table 6). A ten-fold cross validation was used on the IA model. Many classifiers and feature combination sets were tested. Additive Logistic Regression using Decision Stump Boost-ing 8 (Friedman et al., 1998) had the highest performance. Theχ 2 was computed between all classifiers with #7 showing a significant performance improvement increase over #2 -#4 with p ă 0.01 in Table 6.
Results from the Corpus B (see Section 3.2) show a very similar pattern to those of Corpus A as shown in Table 7.

Argument Classification
The argument classification results are given in Table 8 for each respective IA and show a wide F-measure variance. The model was trained and tested over a high variance of argument occurrences as shown in Table 1 with some IAs covering many more annotations than others (i.e. "Buy" was the majority IA consisting of 28.5% of the task annotations). Another reason for the wide distribution in results is the ambiguous nature of some IAs. For example, self-improve could be anything from study, school work or physical exercise.
Classifying to-do tasks with good performance from upstream parsed data is a tractable problem. Using Argument extraction to aide in automating to-do task items is possible using the methods outlined in this work.
Bootstrapping methods for a NER with product lists using semi-supervised methods was used by Putthividhya, Pew and Junling (2011). Similarly, there is sufficient motivation by using our NER lists for exploring generation of entities using similar methods.
We focused on the IA and argument, but more work is needed to classify a category of the task, which identifies the theme of the action or its product attribute (Ghani et al., 2006) as a node in product taxonomy (i.e. "buy dress" tdressu Ñ papparel, womenq).