A general-purpose sentence-level nonsense detector

1 A general - purpose sentence-level nonsense detectorCS229 Final Project ReportDecember 12, 2014 Ian Introduction and BackgroundI have constructed a sentence-level nonsense detec-tor, with the goal of discriminating well-formed En-glish sentences from the large volume of fragments,headlines, incoherent drivel, and meaningless snippetspresent in internet text. For many NLP tasks, the avail-ability of large volumes of internet text is enormouslyhelpful in combating the sparsity problem inherent inmodeling language. However, the derived models canbe easily polluted by ungrammatical text and spam,and automated means are necessary to filter this andprovide high-quality training is scarce precedent in the literature for a di-rect nonsense -detection system, but similar problemsexist in the context of spam filtering and computa-tional sentence completion.

2 For spam filtering, recentresearch has focused on the problem of Bayesian poi-soning (Hayes, 2007), whereby Naive Bayes-basedfilters are defeated by the inclusion of random wordsor text snippets that make the spam vocabulary appearsimilar to normal text. Solutions to this problem pro-pose combining multiple sources of information, suchas higher n-grams, in order to introduce greater con-text (Upasana and Chakravarty, 2010).Sentence completion is an example of a standardNLP task where the system must consider a varietyof possible solutions and discriminate between sensi-cal and nonsensical answers. While generally op-erating on a more restricted domain ( SAT ques-tions), the fundamental goal is similar enough thatsimilar techniques can be applied.

3 The Microsoft Re-search Sentence Completion Challenge (Zweig andBurges, 2011) highlights several approaches to thistask, including neural networks and dependency pars-ing but also showing strong performance with lighter-weight n-gram and distributional models (Zweig et al.,2012).I take a lightweight approach, using a mix of heuris-tics, lightweight token-based features, part-of-speechfeatures, and language model scores as features toavoid computationally-intensive parsing or neural net-works. I structure my system as a binary classificationtask on a heterogeneous feature space, consisting ofto produce a final answer of sentence or nonsense for a given line of implement this project in a mix of Javaand Python, using Java to interface with StanfordCoreNLP for feature extraction, and Python (with theexcellent pandas and scikit-learn libraries) for datamanagement, classifier implementation, and Source and Labeling SchemaThe base dataset is a 1 TB corpus of sentence-tokenized internet text derived from CommonCrawl ( ) and provided by theStanford NLP group.

4 This is a relatively indiscrimi-nate crawl, and contains text from a variety of webpages, ranging from internet forums to pornography(it s the internet) to shopping sites and news addition to coherent sentences , this contains alarge number of link titles, headlines, and other textfragments. A typical few lines would be: p 49, panel 2-4 (Makede & Ntshonge) If so, an Authenticator may havebeen maliciously associated with youraccount by an unauthorized party. No New Messages Forum Softwarec Edition Living AreaI annotate each line with one of the following labels: -SENTENCE-complete English sentences , notnecessarily with perfect grammar -FRAGMENT-sentence fragments, headlines, orcaptions, constituting coherent but non-sententialtext - nonsense -small fragments, noun phrases,gibberish, spam, and anything else not countedabove -NONE-no label, or foreign-language textThis scheme is designed to roughly align withdownstream NLP tasks: nonsense is unwanted for anytask, while fragments are inappropriate for parsingbut, as they are subsequences of real sentence, are stilluseful to build language models.

5 I retain these labelsfor visualization purposes and future use, but for oursupervised learning models we treat -SENTENCE- as a positive example and all other labels as DatasetsI compile two labeled datasets from this corpus, oneby manual annotation and one by crowdsourcing. Thecrowdsourced dataset consists of 12,000 lines of text,each labeled by two distinct workers on Amazon Me-chanical Turk. Of these, 7099 lines are labeled un-ambiguously as a single category by both annotators1,and thus can be used for training and evaluation. Thismeans that we drop the most ambiguous examples,since Turkers are more likely to disagree on lines thatare difficult to classify by any algorithm; as we seein Section 6, this tends to give results that are inflatedrelative to real-world remedy this, I also compiled a manual dataset,consisting of 5,000 lines of text, each labeled by a sin-gle highly-trained user2.

6 All of these labels are as-sumed to be unambiguous, and the entire set is class distribution for each dataset is:Dataset (size)Manual (4997)MTurk (7099) the discrepancy can be attributed difficultyby Mechanical Turk workers in correctly identifyingfragments and nonsense , leaving relatively more sen-tenced behind when ambiguous data is Features and PreprocessingI implement five groups of features, for a maximum ofa 148-dimensional feature space:0. Baseline sentence heuristic: first letter is Capital-ized, and line ends with one !(1 feature).1. Number of characters, words, punctuation, dig-its, and named entities (from Stanford CoreNLPNER tagger), and normalized versions by textlength (10 features).

7 2. Part-of-speech distributional tags:#<tag># wordsforeach Penn treebank tag (45 features).3. Indicators for the part of speech tag of the firstand last token in the text (45x2 = 90 features).1 Unfortunately, budget and time constraints prevented us fromusing a third annotator, which would have increased the fractionof usable , with some help from my Language model raw score (slm= logp(text))and normalized score ( slm=slm# words) (2 fea-tures).For part-of-speech tags, I use the default Englishtagger included with Stanford CoreNLP (Manning etal., 2014). This is a sequence-based MaxEnt taggertrained on a mixed corpus of newswire, technical, andcolloquial text.

8 For language model scores, I build abigram model using the KenLM package, trained onthe entire English Gigaword 5 corpus (Parker et al.,2011) of newswire evaluating the model, all features are in-dependently scaled to zero mean and unit variance(across the training set) in order to improve perfor-mance of regularized and non-linear models and allowextraction of meaningful feature weights from t-SNE VisualizationI used t-distributed Stochastic Neighbor Embedding(t-SNE) to visualize our dataset and understand-ing the difficulty of the classification attempts to non-linearly map high-dimensionaldata into a low-dimensional (usually 2D) spaceby preserving local similarity.

9 Formally, it gener-ates a gaussian distribution (pij=pj|i+pi|j2 Nwherepj|i exp ( xi xj 2/2 2i)) over pairwise dis-tances in the original space, then finds an embed-ding that (locally) minimizes the KL divergence be-tween this and a heavy-tailed t-distributed similarityqijin the low-dimensional space (van der Maaten,2014). I use the Barnes-Hut implementation of t-SNE, using the Python implementation available , and retain our multi-class labels for visualization generate visualizations using the level 3 fea-ture set (everything but language models), with scal-ing normalization the MTurk dataset, we find that restricting to un-ambiguous labels gives us a well-separated space: re-gions of mostly sentences (blue) have a well-definedboundary from nonsense regions (red), and to a lesserextend, fragments (green).

10 On the manual dataset(Figure 4) this separation is much weaker, and sen-tences are interspersed with fragments and nonsensein many clusters, reflecting the inclusion of more am-biguous data the t-SNE algorithm uses L2 distances inthe feature space, it is sensitive to scaling: strong con-tributors to distance in the original space may be rel-atively uninformative for our classification task. Tobetter visualize the difficulty of the classification prob-Figure 1: t-SNE embedding of manual dataset. MTurkdataset visualization available 2: t-SNE embedding of manual dataset, scaledfeatures. MTurk dataset visualization available , we train a logistic classifier (L1, C = 100) onthe full dataset and use the resulting weight vector(97 nonzero elements, out of 146) to scale the featurespace:x(i)j wjx(i)jbefore running t-SNE.