Lecture
N-gram — a sequence of n elements . From a semantic point of view, this can be a sequence of sounds, syllables, words, or letters. In practice, an N-gram is more often encountered as a sequence of words, and fixed phrases are called a collocation. A sequence of two consecutive elements is often called a bigram, and a sequence of three elements is called a trigram. Sequences of four or more elements are denoted as N-grams, where N is replaced by the number of consecutive elements.
A bigram - is a comp. sci. sequence of two elements
A bigram - is a linguistic pair of consecutive sounds, syllables, words, or letters
In modern computational linguistics, bigrams, or n-grams in the general case, are an important statistical tool. In this article we will describe the difficulties one can encounter when computing bigrams over a large corpus of texts, and give an algorithm that can be used on any home computer. Sometimes in the text we will allow ourselves to use the term word-pair as a synonym for bigram.
N-grams in general find application in a wide range of sciences. They can be used, for example, in theoretical mathematics, biology, cartography, as well as in music. The most common uses of N-grams include the following areas:
N-grams are also widely used in natural language processing.
In the field of natural language processing, N-grams are used mainly for prediction based on probabilistic models. An N-gram model calculates the probability of the last word of an N-gram given that all the preceding ones are known. When using this approach to model a language, it is assumed that the occurrence of each word depends only on the preceding words .
Another application of N-grams is plagiarism detection. If a text is split into several small fragments represented by N-grams, they can easily be compared with one another, thereby obtaining a degree of similarity between the analyzed documents . N-grams are often successfully used for text and language categorization. In addition, they can be used to create features that make it possible to extract knowledge from textual data. Using N-grams, one can efficiently find candidates to replace misspelled words.
The goal of building N-gram models is to determine the probability of a given phrase being used. This probability can be formally defined as the probability of a sequence of words occurring in some corpus (a set of texts). For example, the probability of the phrase «счастье есть удовольствие без раскаяния» (happiness is pleasure without remorse) can be calculated as the product of the probabilities of each word in this phrase:
P = P(счастье) * P(есть|счастье) * P(удовольствие|счастье есть) * P(без|счастье есть удовольствие) * P(раскаяния|счастье есть удовольствие без)
To determine P(счастье), you need to count how many times this word occurs in the text and divide that value by the total number of words. Calculating the probability P(раскаяния|счастье есть удовольствие без) is harder. To simplify this task, let us assume that the probability of a word in the text depends only on the previous word. Then our formula for calculating the phrase takes the following form:
P = P(счастье) * P(есть|счастье) * P(удовольствие|есть) * P(без|удовольствие) * P(раскаяния|без)
Calculating the conditional probability P(есть|счастье) is not difficult. To do this, we count the number of pairs 'счастье есть' and divide it by the number of occurrences of the word 'счастье' in the text.
As a result, if we count all the word pairs in a given text, we can compute the probability of an arbitrary phrase. This set of computed probabilities is precisely the bigram model.
Google's research centers have used N-gram models for a wide range of research and development. These include projects such as statistical translation from one language to another, speech recognition, spelling error correction, information retrieval, and much more. Text corpora containing several trillion words were used for the purposes of these projects.
Google decided to create its own training corpus. The project is called Google teracorpus and it contains 1 * 10^12 words collected from publicly available websites .
Given the frequent use of N-grams for solving various tasks, a reliable and fast algorithm for extracting them from text is needed. A suitable tool for extracting N-grams must be able to work with an unlimited text size, work quickly, and make efficient use of available resources. There are several methods for extracting N-grams from text. These methods are based on different principles:
Syntactic N-grams are N-grams defined by paths in syntactic dependency trees or constituency trees, rather than by the linear structure of the text . For example, the sentence: «Economic news has a slight effect on financial markets» can be converted into syntactic N-grams following the tree structure of its dependency relations: news-economic, effect-slight, effect-on-markets-financial, and others .
Syntactic N-grams reflect syntactic structure, unlike linear N-grams, and can be used in the same applications as linear N-grams, including as features in a vector model. The use of syntactic N-grams gives better results in solving certain tasks than the use of standard N-grams, for example, for authorship attribution
Application of N-grams
Example
A collocation is a word combination having the features of a syntactically and semantically integral unit, in which the choice of one component is made according to meaning, while the choice of the second depends on the choice of the first (for example, ставить условия (to set conditions) — the choice of the verb ставить (to set) is determined by tradition and depends on the noun условия (conditions); with the word предложение (offer) a different verb would be used — вносить (to make)).
Collocations are also usually taken to include compound toponyms, anthroponyms, and other frequently co-occurring names (for example, крейсер «Аврора» (the cruiser "Aurora"), завод имени Кирова (the Kirov-name factory)).
Another name for the same phenomenon is a fixed, or phraseological, word combination, N-grams.
Statistical approach A collocation is a habitual, traditional combination of words in speech that sounds correct and natural to native speakers of the language. Characteristic, frequently occurring word combinations, whose appearance next to one another is based on the regular nature of mutual expectation. Metric: frequency of co-occurrence
6 Association measures Indicators of the strength of the syntagmatic connection between the components of word combinations. Source data: frequency of co-occurrence, frequencies of words or word forms (node – the key word, collocate – a word occurring to the left or right of the key word, the collocate). Association measures: MI (mutual information), t-score, z-score, log-likelihood, Odds, Dice, X 2 … (see Corpora as sources of reliable frequency data.
Examples
Unlike idioms (подложить свинью (to play a dirty trick), темна вода в облацех (it's all very mysterious) etc.), collocations are widespread; without them it is impossible to speak Russian.
A word that retains its meaning is called the key, or free, component: the word влияние (influence) in оказывать влияние (to exert influence), the word смысл (sense) in the combination глубокий смысл (deep sense). The free component is generated according to the usual rules of speech generation: it is chosen by meaning depending on the sense to be expressed.
A word whose choice is determined by tradition, depends on the key component, and must be stored in memory (in the dictionary), is called the non-free component. In order to choose the correct verb with the word influence, one must not only understand what sense needs to be expressed (the sense «to make/to do»), but also remember (or find out from a dictionary) that it is the verb оказывать (to exert), not делать (to make), not производить (to produce), not создавать (to create).
Most collocations express a limited number of standard meanings, called lexical functions in the «Meaning — Text» model: оказывать влияние (to exert influence) — this is the Oper function, глубокое потрясение (deep shock) — Magn, and so on.
Collocations are divided by their syntactically dominant word into:
Collocations can also be classified according to the functional style in which they are used. Most collocations are bookish: scientific (вести исследования (to conduct research)), formal-business (выносить приговор (to pass a verdict)), newspaper-journalistic (энтузиазм охватил (enthusiasm swept over)). But there are also colloquial ones (нести ерунду, молоть чушь (to talk nonsense)).
By their lexical composition, collocations are divided into :
In non-compound collocations, the meaning is entirely different from that of its component parts. These are typically idioms and idiomatic expressions. For example, дать дуба (to kick the bucket), наставить рога (to cheat on someone), etc.
Non-substitutable collocations do not allow a synonymous substitution of one word for another. This class includes fixed expressions and metaphors. For example, белое вино (white wine) cannot be replaced with прозрачное вино (transparent wine) or жёлтое вино (yellow wine), etc.
Invariable collocations contain rigid links between words that do not allow them to be changed by adding extra lexical material or by changing the grammatical function. For example, сердце в пятки (heart in one's boots) cannot be replaced with сердце в пятку, and (ходить) вокруг да около (to beat around the bush) — with (ходить) вокруг дома да около.
Another classification of collocations is into discontinuous and continuous ones. Secondary words can be inserted into discontinuous collocations (жизнь кипит and жизнь его кипит, жизнь его постоянно кипит (life is bustling / his life is bustling / his life is constantly bustling), etc.).
Collocations are identified through lexical analysis of a text. Statistical methods that note the frequency of joint use can help detect them only to a very small degree. Some statistical methods for obtaining collocations:
Application of collocation
Comments