A Survey on Context Learning <s> N-gram Model <s> The description of a novel type of m-gram language model is given. The model offers, via a nonlinear recursive procedure, a computation and space efficient solution to the problem of estimating probabilities from sparse data. This solution compares favorably to other proposed methods. While the method has been developed for and successfully implemented in the IBM Real Time Speech Recognizers, its generality makes it applicable in other areas where the problem of estimating probabilities from sparse data arises. <s> BIB001 </s> A Survey on Context Learning <s> N-gram Model <s> Text categorization is a fundamental task in document processing, allowing the automated handling of enormous streams of documents in electronic form. One difficulty in handling some classes of documents is the presence of different kinds of textual errors, such as spelling and grammatical errors in email, and character recognition errors in documents that come through OCR. Text categorization must work reliably on all input, and thus must tolerate some level of these kinds of problems. We describe here an N-gram-based approach to text categorization that is tolerant of textual errors. The system is small, fast and robust. This system worked very well for language classification, achieving in one test a 99.8% correct classification rate on Usenet newsgroup articles written in different languages. The system also worked reasonably well for classifying articles from a number of different computer-oriented newsgroups according to subject, achieving as high as an 80% correct classification rate. There are also several obvious directions for improving the system`s classification performance in those cases where it did not do as well. The system is based on calculating and comparing profiles of N-gram frequencies. First, we use the system to compute profiles on training set data that represent the variousmore » categories, e.g., language samples or newsgroup content samples. Then the system computes a profile for a particular document that is to be classified. Finally, the system computes a distance measure between the document`s profile and each of the category profiles. The system selects the category whose profile has the smallest distance to the document`s profile. The profiles involved are quite small, typically 10K bytes for a category training set, and less than 4K bytes for an individual document. Using N-gram frequency profiles provides a simple and reliable way to categorize documents in a wide range of classification tasks.« less <s> BIB002 </s> A Survey on Context Learning <s> N-gram Model <s> In stochastic language modeling, backing-off is a widely used method to cope with the sparse data problem. In case of unseen events this method backs off to a less specific distribution. In this paper we propose to use distributions which are especially optimized for the task of backing-off. Two different theoretical derivations lead to distributions which are quite different from the probability distributions that are usually used for backing-off. Experiments show an improvement of about 10% in terms of perplexity and 5% in terms of word error rate. <s> BIB003 </s> A Survey on Context Learning <s> N-gram Model <s> Following the recent adoption by the machine translation community of automatic evaluation using the BLEU/NIST scoring process, we conduct an in-depth study of a similar idea for evaluating summaries. The results show that automatic evaluation using unigram co-occurrences between summary pairs correlates surprising well with human evaluations, based on various statistical metrics; while direct application of the BLEU evaluation procedure does not always give good results. <s> BIB004 </s> A Survey on Context Learning <s> N-gram Model <s> A goal of statistical language modeling is to learn the joint probability function of sequences of words in a language. This is intrinsically difficult because of the curse of dimensionality: a word sequence on which the model will be tested is likely to be different from all the word sequences seen during training. Traditional but very successful approaches based on n-grams obtain generalization by concatenating very short overlapping sequences seen in the training set. We propose to fight the curse of dimensionality by learning a distributed representation for words which allows each training sentence to inform the model about an exponential number of semantically neighboring sentences. The model learns simultaneously (1) a distributed representation for each word along with (2) the probability function for word sequences, expressed in terms of these representations. Generalization is obtained because a sequence of words that has never been seen before gets high probability if it is made of words that are similar (in the sense of having a nearby representation) to words forming an already seen sentence. Training such large models (with millions of parameters) within a reasonable time is itself a significant challenge. We report on experiments using neural networks for the probability function, showing on two text corpora that the proposed approach significantly improves on state-of-the-art n-gram models, and that the proposed approach allows to take advantage of longer contexts. <s> BIB005 </s> A Survey on Context Learning <s> N-gram Model <s> The current commercial anti-virus software detects a virus only after the virus has appeared and caused damage. Motivated by the standard signature-based technique for detecting viruses, and a recent successful text classification method, we explore the idea of automatically detecting new malicious code using the collected dataset of the benign and malicious code. We obtained accuracy of 100% in the training data, and 98% in 3-fold cross-validation. <s> BIB006 </s> A Survey on Context Learning <s> N-gram Model <s> In this paper, we formally define the problem of topic modeling with network structure (TMN). We propose a novel solution to this problem, which regularizes a statistical topic model with a harmonic regularizer based on a graph structure in the data. The proposed method bridges topic modeling and social network analysis, which leverages the power of both statistical topic models and discrete regularization. The output of this model well summarizes topics in text, maps a topic on the network, and discovers topical communities. With concrete selection of a topic model and a graph-based regularizer, our model can be applied to text mining problems such as author-topic analysis, community discovery, and spatial text mining. Empirical experiments on two different genres of data show that our approach is effective, which improves text-oriented methods as well as network-oriented methods. The proposed model is general; it can be applied to any text collections with a mixture of topics and an associated network structure. <s> BIB007 </s> A Survey on Context Learning <s> N-gram Model <s> This paper describes how to automatically cross-reference documents with Wikipedia: the largest knowledge base ever known. It explains how machine learning can be used to identify significant terms within unstructured text, and enrich it with links to the appropriate Wikipedia articles. The resulting link detector and disambiguator performs very well, with recall and precision of almost 75%. This performance is constant whether the system is evaluated on Wikipedia articles or "real world" documents. This work has implications far beyond enriching documents with explanatory links. It can provide structured knowledge about any unstructured fragment of text. Any task that is currently addressed with bags of words - indexing, clustering, retrieval, and summarization to name a few - could use the techniques described here to draw on a vast network of concepts and semantics. <s> BIB008 </s> A Survey on Context Learning <s> N-gram Model <s> A new method of estimating the entropy and redundancy of a language is described. This method exploits the knowledge of the language statistics possessed by those who speak the language, and depends on experimental results in prediction of the next letter when the preceding text is known. Results of experiments in prediction are given, and some properties of an ideal predictor are developed. <s> BIB009
This model is the most elementary and yet widely used BIB006 , BIB002 , BIB004 ,  approach to gather contextual information for analyses. Having its roots in linguistics and IR domain, the N-gram model was originally used to generate various language models BIB001 ,  . The earliest reference to N-gram model can be traced to Claude Shannon's work of using N-gram statistics to compute the perplexity of letter sequences BIB009 . The basic objective in an N-gram model is to predict the next element in a sequence given a distribution over the immediate past elements present inside a window of N-elements. These distributions are typically categorical in nature. It should be noted that in this paper, the notion of gram refers to a word and not a character. There are applications wherein the notion of gram is considered at character level, a prominent example being spell-checker. While the values of N can vary from 1 . . . 1, the sparsity, memory size and computation complexity constraints us to at most five-grams in practice. To formally define the N-gram model, when the context window is limited to m À 1 preceding words, an m-gram language model, models the overall probability of a document as a product of the word probabilities based on their context inside the window pðw i jw iÀ1 ; w iÀ2 ; . . . ; w iÀðmÀ1Þ Þ; BIB007 where pðw i jw iÀ1 ; w iÀ2 ; . . . ; w iÀm Þ is the conditional probability of word w i on its context of m preceding words. When the context window size is set to 0, i.e., m ¼ 1, the word probability pðw i Þ is the relative frequency of word w i . This model is called a uni-gram model. When m 6 ¼ 1, we predict the word w i based the context described inside the window. This is done by calculating the relative frequency of cooccurrence of word w i and its m historical context words, refer Equation BIB005 . It should be noted that N-gram assumes that probability of an element appearing in the sequence is solely dependent on the immediate past window and in this regard one can draw parallelism to Markov chain pðw i jw iÀ1 ; ::; w iÀðmÀ1Þ Þ ¼ countðw i ; w iÀ1 ; . . . ; w iÀðmÀ1Þ Þ countðw iÀ1 ; w iÀ2 ; . . . ; w iÀðmÀ1Þ Þ : However, this n-gram model has a obvious drawback. If an n-gram phrase has not been seen in the training set, then Equation (2) would assign it a probability of 0, which sometimes does not make sense. Consequently, many smoothing techniques have been developed to address this problem, among which, add-one smoothing is the simplest one. Addone smoothing, also called Laplace smoothing, prevents the zero probabilities by adding one to all the possible n-grams. One of the state-of-the-art smoothing techniques for the ngram model is the Kneser-Ney smoothing BIB003 . The main idea of Kneser-Ney smoothing is to give higher probabilities to the words with a higher diversity of history, as well as using adding one strategy to avoid zero probabilities. For example, as the term york mostly comes after new, this reduces its diversity of history and would eventually results in a lower probability. As an example of how n-gram is useful, consider the following example from BIB008 . Although the primary objective is Wikification (linking Wikipedia articles to terms in a text), an essential subsidiary task in that is to detect which of terms should be linked. A context agnostic approach assumes that if term is used as a link for a sufficient proportion of the Wikipedia articles in which it is found, then one should consider it to be a link whenever it is encountered in other documents. The authors in that paper show that this method, regardless of thresholds, always makes mistakes. The gist of the discussion in that paper revolves around the fact that regardless of the threshold value a term, if its link probability is greater than 0 but not equal to 1, then there are some context in which the term did not act as a link; similarly vice-versa. To overcome this problem, the authors use the n-grams in the articles of Wikipedia to identify the context in which a term appears and then to train a classifier that identifies whether a term should be linked given the adjacent words (context).