Wiki - Факультет компьютерных наук - Вклад [ru]

Lecture 6. Synonyms and near-synonyms detection

2015-09-03T00:41:01Z

Polidson: /* Web or corpus search approach */

== Examples ==

* '''Synonyms''': Netherlands and Holland, buy and purchase
* '''Near synonyms''': pants, trousers and slacks, mistake and error

== Approaches to synonyms and near-synonyms detection ==

* Thesaurus-based approach
* Distributional semantics
* Context-based approach
* word2vec
* Web search-based approach

=== Synonyms in WordNet ===

Given a word, look for synonyms in every synset.

==== WordNet NLTK interface ====

<code>
In[1]: for i,j in enumerate(wn.synsets('error')):

In[2]: print "Meaning",i, "NLTK ID:", j.name()

In[3]: print "Definition:",j.definition()

In[4]: print "Synonyms:", ", ".join(j.lemma names())
</code>

Wordnet Web interface: [http://wordnetweb.princeton.edu/perl/webwn|http://wordnetweb.princeton.edu/perl/webwn]

=== Distributional semantics ===

[[Файл:L6p1.jpg|500px|слева]]

 
 

==== Exercise 6.1 ====

Calculate PPMI for Table 1.

==== Exercise 6.2 ====

Input: def.txt or your own text

Output 1: term-context matrix

Output 2: term-term similarity matrix (use cosine similarity)

Output 3: 2D visualization by means of LSA

Hint: use cfd = nltk.ConditionalFreqDist((term, context) for ...) for computing conditional frequency dictionary

Hint: use R for SVD and visualization

=== word2vec [Mikolov, Chen, Corrado, Dean, 2013] ===

Very complex machine learning (deep learning) applied to term-context matrices.

There are two regimes:
* CBOW predicts the current word based on the context
* Skip-gram predicts surrounding words given the current word

word2vec project page: [https://code.google.com/p/word2vec/|https://code.google.com/p/word2vec/]
demo: [http://rare-technologies.com/word2vec-tutorial/|http://rare-technologies.com/word2vec-tutorial/]

Example: vec(Madrid) - vec(Spain) + vec(France) = vec(Paris)

=== Context-based approach (1) [Lin, 1998] ===

==== Dependency triple [Lin, 1998] ====

A dependency triple (w, r, w') consists of two words and the grammatical relationship between them in the input sentence.

I have a brown dog: (have subj I), (I subj-of have), (dog obj-of have), (dog adj-mod brown), (brown adj-mod-of dog), (dog det a), (a det-of dog)

||w, r, w'|| — frequency of (w, r, w')

||w, r, * || — total occurrences of w-r relationships

|| *, *, *|| — total number of dependency triples

Mutual information between w, w':

[[Файл:L6p2.jpg|300px|слева]]

[[Файл:L6p3.jpg|450px|слева]]

 

Results: '''brief(noun)''' — affidavit 0.13, petition 0.05, memo-randum 0.05, motion 0.05, lawsuit 0.05, depo-sition 0.05, slight 0.05, prospectus 0.04, docu-ment 0.04 paper 0.04
* some sort of dependency parsing is required
* no difference between synonyms and antonyms (win / loose the game)

=== Web or corpus search approach ===

==== Hearst patterns [Hearst, 1998] ====

Lexico-syntactic patterns to recognize hyponymy:
* such NP as NP, NP and / or NP;
* NP such as NP, NP and / or NP;
* NP, NP or other NP;
* NP, NP and other NP;
* NP, including NP, NP and / or NP;
* NP, especially NP, NP and / or NP;

Text ⇒ pattern ⇒ concordance

To rank concordances: PatternSim [Panchenko, Morozova, Naets]

Concordance ranking:

Input: Terms C, Corpus D

Output: Similarity matrix S(C x C)

K ← extract concord(D);

Klem ← lemmatize concord(K);

KC ← filter concord(Klem; C);

S ← get extractionfreq(C;K);

S ← rerank(S; C;D);

S ← normalize(S);

return S

Example ranking '''Efreq-Cfreq''':

[[Файл:L6p4.jpg|250px|слева]]

 

P(wi) — frequency of (wi) P(wi, wj) — extraction probability of (wi,wj)
demo: [http://serelex.cental.be/|http://serelex.cental.be/]

Файл:L6p4.jpg

2015-09-03T00:39:51Z

Polidson:

Lecture 6. Synonyms and near-synonyms detection

2015-09-03T00:32:36Z

Polidson: /* Dependency triple [Lin, 1998] */

Lecture 6. Synonyms and near-synonyms detection

2015-09-03T00:31:58Z

Polidson: /* Context-based approach (1) [Lin, 1998] */

== Examples ==

* '''Synonyms''': Netherlands and Holland, buy and purchase
* '''Near synonyms''': pants, trousers and slacks, mistake and error

== Approaches to synonyms and near-synonyms detection ==

* Thesaurus-based approach
* Distributional semantics
* Context-based approach
* word2vec
* Web search-based approach

=== Synonyms in WordNet ===

Given a word, look for synonyms in every synset.

==== WordNet NLTK interface ====

<code>
In[1]: for i,j in enumerate(wn.synsets('error')):

In[2]: print "Meaning",i, "NLTK ID:", j.name()

In[3]: print "Definition:",j.definition()

In[4]: print "Synonyms:", ", ".join(j.lemma names())
</code>

Wordnet Web interface: [http://wordnetweb.princeton.edu/perl/webwn|http://wordnetweb.princeton.edu/perl/webwn]

=== Distributional semantics ===

[[Файл:L6p1.jpg|500px|слева]]

 
 

==== Exercise 6.1 ====

Calculate PPMI for Table 1.

==== Exercise 6.2 ====

Input: def.txt or your own text

Output 1: term-context matrix

Output 2: term-term similarity matrix (use cosine similarity)

Output 3: 2D visualization by means of LSA

Hint: use cfd = nltk.ConditionalFreqDist((term, context) for ...) for computing conditional frequency dictionary

Hint: use R for SVD and visualization

=== word2vec [Mikolov, Chen, Corrado, Dean, 2013] ===

Very complex machine learning (deep learning) applied to term-context matrices.

There are two regimes:
* CBOW predicts the current word based on the context
* Skip-gram predicts surrounding words given the current word

word2vec project page: [https://code.google.com/p/word2vec/|https://code.google.com/p/word2vec/]
demo: [http://rare-technologies.com/word2vec-tutorial/|http://rare-technologies.com/word2vec-tutorial/]

Example: vec(Madrid) - vec(Spain) + vec(France) = vec(Paris)

=== Context-based approach (1) [Lin, 1998] ===

==== Dependency triple [Lin, 1998] ====

A dependency triple (w, r, w') consists of two words and the grammatical relationship between them in the input sentence.

I have a brown dog: (have subj I), (I subj-of have), (dog obj-of have), (dog adj-mod brown), (brown adj-mod-of dog), (dog det a), (a det-of dog)

||w, r, w'|| — frequency of (w, r, w')

||w, r, * || — total occurrences of w-r relationships

|| *, *, *|| — total number of dependency triples

Mutual information between w, w':

[[Файл:L6p2.jpg|300px|слева]]

[[Файл:L6p3.jpg|300px|слева]]

 

Results: '''brief(noun)''' — affidavit 0.13, petition 0.05, memo-randum 0.05, motion 0.05, lawsuit 0.05, depo-sition 0.05, slight 0.05, prospectus 0.04, docu-ment 0.04 paper 0.04
* some sort of dependency parsing is required
* no difference between synonyms and antonyms (win / loose the game)

=== Web or corpus search approach ===

Файл:L6p3.jpg

2015-09-03T00:29:16Z

Polidson:

Файл:L6p2.jpg

2015-09-03T00:27:48Z

Polidson:

Lecture 6. Synonyms and near-synonyms detection

2015-09-03T00:23:14Z

Polidson: /* Distributional semantics */

Файл:L6p1.jpg

2015-09-03T00:20:50Z

Polidson: Polidson загружена новая версия «Файл:L6p1.jpg»

Файл:L6p1.jpg

2015-09-03T00:20:24Z

Polidson:

Lecture 8. Suffix trees for NLP

2015-09-03T00:09:31Z

Polidson: /* Taxonomy refinement */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|350px|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|400px|слева]]
[[Файл:L8 9.jpg|400px|слева]]
[[Файл:L8 10.jpg|600px|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|500px|слева]]
[[Файл:L8 12.jpg|600px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|600px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 
 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|450px|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-03T00:09:06Z

Polidson: /* Reference graph */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|350px|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|400px|слева]]
[[Файл:L8 9.jpg|400px|слева]]
[[Файл:L8 10.jpg|600px|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|400px|слева]]
[[Файл:L8 12.jpg|600px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|600px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 
 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|450px|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-03T00:08:39Z

Polidson: /* Reference graph */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|350px|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|400px|слева]]
[[Файл:L8 9.jpg|400px|слева]]
[[Файл:L8 10.jpg|600px|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|400px|слева]]
[[Файл:L8 12.jpg|600px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|600px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 
 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|400px|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-03T00:07:55Z

Polidson: /* Taxonomy refinement */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|350px|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|400px|слева]]
[[Файл:L8 9.jpg|400px|слева]]
[[Файл:L8 10.jpg|600px|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|400px|слева]]
[[Файл:L8 12.jpg|600px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|600px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 
 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-03T00:05:52Z

Polidson: /* Taxonomy refinement */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|350px|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|400px|слева]]
[[Файл:L8 9.jpg|400px|слева]]
[[Файл:L8 10.jpg|500px|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|400px|слева]]
[[Файл:L8 12.jpg|500px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|500px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-03T00:05:31Z

Polidson: /* Taxonomy refinement */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|350px|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|400px|слева]]
[[Файл:L8 9.jpg|400px|слева]]
[[Файл:L8 10.jpg|400px|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|400px|слева]]
[[Файл:L8 12.jpg|400px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|400px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-03T00:03:11Z

Polidson: /* Taxonomy refinement */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|350px|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|350px|слева]]
[[Файл:L8 12.jpg|350px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|350px|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-03T00:02:44Z

Polidson: /* Text summarization */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|350px|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-03T00:02:22Z

Polidson: /* Text summarization */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|350px|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 3. POS tagging. Key word and phrase extraction

2015-09-02T23:59:54Z

Polidson: /* Using TF-IDF to measure text similarity */

== Part of speech (POS) ==

Part of speech [Manning, Shuetze, 1999]

Words of a language are grouped into classes which show similar syntactic behavior. These word classes are called parts of speech (POS). Three
important parts of speech are noun, verb, and adjective. The major types of morphological process are in ection, derivation, and compounding.

There are around 9 POS according to different schools:
* Nouns (NN, NP), pronouns (PN, PRP), adjectives (JJ): number, gender, case
* Adjective (JJ): comparative, superlative, short form
* Verbs (VB): subject number, subject person, tense, aspect, modality, participles, voice
* Adverbs (RB), prepositions (IN), conjunctions (, CS), articles (AT)
and particles (RP): nothing

== POS ambiguation ==

Ship (noun or verb?)

* a luxury cruise ship
* Both products are due to ship at the beginning of June
* A new engine was shipped over from the US
* The port is closed to all '''shipping'''

Contest (noun or verb?)
* Stone decided to hold a contest to see who could write the best song.
* She plans to contest a seat in Congress next year.

== POS taggers ==

* Corpus- or dictionary-based VS rule-based
* Ngram-based taggers:
** unigram tagging: assign the most frequent tag
** ngram tagging: look at the context of n previous words (requires a lot of training data)
* Trade-off between the accuracy and the coverage: combine different taggers

===NLTK POS default tagger===

<code>

In[1]: from nltk.tag import pos tag

In[2]: print pos tag(['ship'])

Out[1]: [('ship', 'NN')]

In[3]: print pos tag(['shipping'])

Out[2]: [('shipping', 'VBG')]
</code>

See [http://www.nltk.org/api/nltk.tag.html|http://www.nltk.org/api/nltk.tag.html] for more details on
learning taggers.

== Exercise 3.1 Genre comparison ==

Text genre [Santini, Sharoff, 2009]

The concept of genre is hard to agree upon. Many interpretations have been proposed since Aristotles Poetics without reaching any definite
conclusions about the inventory or even principles for classifying documents into genres. The lack of an agreed definition of what genre is causes the problem of the loose boundaries between the term \genre" with other neighbouring terms, such as "register", "domain", "topic", and "style".

'''Exercise 3.1'''

Input: Two texts of different genre (for example, Wikipedia article and
blog post)
Output: rank all of POS tags for both texts

How can you describe the difference between two genres?

== Key word and phrase extraction ==

There are many definitions of key word and phrase. Thus there are many methods for their extraction:

* supervised VS unsupervised
* frequency-based VS more complex
* from individual text VS from text collection
* word (unigram) VS bigram VS ngram
* term VS named entity VS collocation
* sequential words VS using window

== Supervised methods for key word and phrase extraction ==

I am a word. Am I a key word? Let us build a classifier.

* Am I in the beginning or in the end of the sentence?
* Am I capitalized?
* How many times do I occur?
* Am I used in Wikipedia as a title of a category or an article?
* Am I a term?
* Am I a NE?
* etc.

But we need a collection of marked up texts!

== Unsupervised methods for key word and phrase extraction from a single text ==

* POS patterns
* Association measures: PMI, T-Score, LLR
* Graph methods: TextRank [Mihalcea, Tarau, 2004]
* Syntactic patterns

=== Exercise 3.2 ===

Input: sif1.txt (or your own text)

Key word: top n1 NN

Key phrase: top n2 phrases, that satisfy the following patterns: JJ + NN, NN + NN, NN + IN + NN

Output: list of key words and phrases

Hint: use nltk.ngrams to get ngrams.

== Bigram association measures ==

==== Pointwise Mutual Information [Manning, Shuetze, 1999] ====

PMI measures the reduction of uncertainty about the occurrence of one
word when we are told about the occurrence of the other one.

[[Файл:L3 p1.jpg|350px|слева]]

 

==== T-Score [Manning, Shuetze, 1999] ====

T-Score is a statistical t-test applied to finding collocations. The t-test
looks at the difference between the observed and expected means, scaled
by the variance of the data. The T-score is most useful as a method for
ranking collocations. The level of significance itself is less useful.

[[Файл:L3 p2.jpg|300px|слева]]

 

[[Файл:L3 p3.jpg|400px|слева]]

 

But Chi-squared has many other interesting applications.

==== Chi-squared [Manning, Shuetze, 1999] ====
In general, for the problem of finding collocation, the difference between the T-score and the Chi-squared does not seem to be large.

=== Bigram association measures in NLTK ===

==== NLTK BigramCollocationFinder ====

<code>

In[1]: from nltk.collocations import *

In[2]: bigram measures = nltk.collocations.BigramAssocMeasures()

In[3]: finder = BigramCollocationFinder.from words(tokens)

In[4]: finder.apply freq filter(3)

In[5]: for i in finder.nbest(bigram measures.pmi, 20):

...

</code>

Bigram measures:
* <code> bigram measures.pmi </code>
* <code> bigram measures.student_t </code>
* <code> bigram measures.chi_sq </code>
* <code> igram measures.likelihood_ratio </code>

See [http://www.nltk.org/_modules/nltk/metrics/association.html|http://www.nltk.org/_modules/nltk/metrics/association.html] for more more bigram association measures.

== TextRank: using graph centrality measures for key word and phrase extraction [Mihalcea, Tarau, 2004] ==

# Add words as vertices in the graph.
# Identify relations that connect words:
## consequent words;
## words inside (left or right) the window (2-5 words); and use these relations to draw edges between vertices in the graph. Edges can be directed or undirected, weighted or unweighted.
# Iterate the graph-based ranking algorithm until convergence (for example, PageRank).
# Sort vertices based on their final score. Use the values attached to each vertex for ranking/selection decisions.
# If two adjacent words are selected as potential keywords by TextRank, collapse them into one single key phrase.

See original paper: [http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf|http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf]

Compatibility of systems of linear constraints over the set of natural numbers. Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types systems and systems of mixed types.

[[Файл:L3 p4.jpg|обрамить|TextRank]]

G = (V, E) — a graph, V — vertices, E — edges
''In(Vi)'' — the set of vertices that point to it
''Out(Vi)'' — the set of vertices that ''Vi'' points to
Graph centrality measures:

==== PageRank [Brin, Page, 1998] ====
[[Файл:L3 p5.jpg|250px|слева]]

 

==== HITS [Kleinberg, 1999] ====
[[Файл:L3 p6.jpg|250px|слева]]

 

Key words and phrases, assigned by TextRank using PageRank centrality measure: linear constraints; linear diophantine equations; natural numbers; nonstrict inequations; strict inequations; upper bounds

==== Exercise 3.3 ====

Input: sif.txt (or your own text)
Output: key words and phrases computed by PageRank (using PR(Vi),HITSA(Vi) and HITSH(Vi) as centrality measures)

Hint: use NetworkX for PageRank and HITS [http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html|http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html]

== Unsupervised methods for key word and phrase selection from a text in a collection ==

The problem: given a collection of texts find those words and phrases (terms) that occur in this text significant frequently than in other texts.

=== Term frequency [Luhn, 1957] ===

The weight of a term that occurs in a document is simply proportional to the term frequency.

=== Inverse document frequency [Spaerck Jones, 1972] ===

The specificity of a term can be quantified as an inverse function of the number of documents in which it occurs.

''tfidf (term, text, collection) = tf (term, document) × idf (term, collection)''

== Variants of TF and IDF weights ==

[[Файл:L3 p7.jpg|400px|слева]]

 

== TF-IDF in NLTK ==

===NLTK TextCollection class ===

<code>

In[1]: from nltk.text import TextCollection

In[2]: collection = [WhitespaceTokenizer().tokenize(text) for text in collection]

In[3]: corpus = TextCollection(collection)

In[4]: for i in collection[0]: print i, corpus.tf idf(i,collection[0])

</code>

=== Exercise 3.4 ===

Input: sif2.txt (or your own collection of texts)

Output: list of key words and phrases according to TF-IDF for one text

Hint: <code> use sorted(mylist,key=lambda l:l[1], reverse=True) to sort mylist in descending order based on the second parameter </code>

== TF-IDF alternatives ==

==== Exercise 3.5 ====

Write MI and Chi-squared as an alternative for TF-IDF for measuring significance of a term in a text in a collection.
Check your ideas in Sebastiani[http://arxiv.org/pdf/cs/0110053.pdf|], 2001

== Using TF-IDF to measure text similarity ==

[[Файл:L3p8.jpg|450px|слева]]

Файл:L3p8.jpg

2015-09-02T23:59:05Z

Polidson:

Lecture 3. POS tagging. Key word and phrase extraction

2015-09-02T23:57:20Z

Polidson: /* Variants of TF and IDF weights */

Lecture 3. POS tagging. Key word and phrase extraction

2015-09-02T23:56:31Z

Polidson: /* HITS [Kleinberg, 1999] */

== Part of speech (POS) ==

Part of speech [Manning, Shuetze, 1999]

Words of a language are grouped into classes which show similar syntactic behavior. These word classes are called parts of speech (POS). Three
important parts of speech are noun, verb, and adjective. The major types of morphological process are in ection, derivation, and compounding.

There are around 9 POS according to different schools:
* Nouns (NN, NP), pronouns (PN, PRP), adjectives (JJ): number, gender, case
* Adjective (JJ): comparative, superlative, short form
* Verbs (VB): subject number, subject person, tense, aspect, modality, participles, voice
* Adverbs (RB), prepositions (IN), conjunctions (, CS), articles (AT)
and particles (RP): nothing

== POS ambiguation ==

Ship (noun or verb?)

* a luxury cruise ship
* Both products are due to ship at the beginning of June
* A new engine was shipped over from the US
* The port is closed to all '''shipping'''

Contest (noun or verb?)
* Stone decided to hold a contest to see who could write the best song.
* She plans to contest a seat in Congress next year.

== POS taggers ==

* Corpus- or dictionary-based VS rule-based
* Ngram-based taggers:
** unigram tagging: assign the most frequent tag
** ngram tagging: look at the context of n previous words (requires a lot of training data)
* Trade-off between the accuracy and the coverage: combine different taggers

===NLTK POS default tagger===

<code>

In[1]: from nltk.tag import pos tag

In[2]: print pos tag(['ship'])

Out[1]: [('ship', 'NN')]

In[3]: print pos tag(['shipping'])

Out[2]: [('shipping', 'VBG')]
</code>

See [http://www.nltk.org/api/nltk.tag.html|http://www.nltk.org/api/nltk.tag.html] for more details on
learning taggers.

== Exercise 3.1 Genre comparison ==

Text genre [Santini, Sharoff, 2009]

The concept of genre is hard to agree upon. Many interpretations have been proposed since Aristotles Poetics without reaching any definite
conclusions about the inventory or even principles for classifying documents into genres. The lack of an agreed definition of what genre is causes the problem of the loose boundaries between the term \genre" with other neighbouring terms, such as "register", "domain", "topic", and "style".

'''Exercise 3.1'''

Input: Two texts of different genre (for example, Wikipedia article and
blog post)
Output: rank all of POS tags for both texts

How can you describe the difference between two genres?

== Key word and phrase extraction ==

There are many definitions of key word and phrase. Thus there are many methods for their extraction:

* supervised VS unsupervised
* frequency-based VS more complex
* from individual text VS from text collection
* word (unigram) VS bigram VS ngram
* term VS named entity VS collocation
* sequential words VS using window

== Supervised methods for key word and phrase extraction ==

I am a word. Am I a key word? Let us build a classifier.

* Am I in the beginning or in the end of the sentence?
* Am I capitalized?
* How many times do I occur?
* Am I used in Wikipedia as a title of a category or an article?
* Am I a term?
* Am I a NE?
* etc.

But we need a collection of marked up texts!

== Unsupervised methods for key word and phrase extraction from a single text ==

* POS patterns
* Association measures: PMI, T-Score, LLR
* Graph methods: TextRank [Mihalcea, Tarau, 2004]
* Syntactic patterns

=== Exercise 3.2 ===

Input: sif1.txt (or your own text)

Key word: top n1 NN

Key phrase: top n2 phrases, that satisfy the following patterns: JJ + NN, NN + NN, NN + IN + NN

Output: list of key words and phrases

Hint: use nltk.ngrams to get ngrams.

== Bigram association measures ==

==== Pointwise Mutual Information [Manning, Shuetze, 1999] ====

PMI measures the reduction of uncertainty about the occurrence of one
word when we are told about the occurrence of the other one.

[[Файл:L3 p1.jpg|350px|слева]]

 

==== T-Score [Manning, Shuetze, 1999] ====

T-Score is a statistical t-test applied to finding collocations. The t-test
looks at the difference between the observed and expected means, scaled
by the variance of the data. The T-score is most useful as a method for
ranking collocations. The level of significance itself is less useful.

[[Файл:L3 p2.jpg|300px|слева]]

 

[[Файл:L3 p3.jpg|400px|слева]]

 

But Chi-squared has many other interesting applications.

==== Chi-squared [Manning, Shuetze, 1999] ====
In general, for the problem of finding collocation, the difference between the T-score and the Chi-squared does not seem to be large.

=== Bigram association measures in NLTK ===

==== NLTK BigramCollocationFinder ====

<code>

In[1]: from nltk.collocations import *

In[2]: bigram measures = nltk.collocations.BigramAssocMeasures()

In[3]: finder = BigramCollocationFinder.from words(tokens)

In[4]: finder.apply freq filter(3)

In[5]: for i in finder.nbest(bigram measures.pmi, 20):

...

</code>

Bigram measures:
* <code> bigram measures.pmi </code>
* <code> bigram measures.student_t </code>
* <code> bigram measures.chi_sq </code>
* <code> igram measures.likelihood_ratio </code>

See [http://www.nltk.org/_modules/nltk/metrics/association.html|http://www.nltk.org/_modules/nltk/metrics/association.html] for more more bigram association measures.

== TextRank: using graph centrality measures for key word and phrase extraction [Mihalcea, Tarau, 2004] ==

# Add words as vertices in the graph.
# Identify relations that connect words:
## consequent words;
## words inside (left or right) the window (2-5 words); and use these relations to draw edges between vertices in the graph. Edges can be directed or undirected, weighted or unweighted.
# Iterate the graph-based ranking algorithm until convergence (for example, PageRank).
# Sort vertices based on their final score. Use the values attached to each vertex for ranking/selection decisions.
# If two adjacent words are selected as potential keywords by TextRank, collapse them into one single key phrase.

See original paper: [http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf|http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf]

Compatibility of systems of linear constraints over the set of natural numbers. Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types systems and systems of mixed types.

[[Файл:L3 p4.jpg|обрамить|TextRank]]

G = (V, E) — a graph, V — vertices, E — edges
''In(Vi)'' — the set of vertices that point to it
''Out(Vi)'' — the set of vertices that ''Vi'' points to
Graph centrality measures:

==== PageRank [Brin, Page, 1998] ====
[[Файл:L3 p5.jpg|250px|слева]]

 

==== HITS [Kleinberg, 1999] ====
[[Файл:L3 p6.jpg|250px|слева]]

 

Key words and phrases, assigned by TextRank using PageRank centrality measure: linear constraints; linear diophantine equations; natural numbers; nonstrict inequations; strict inequations; upper bounds

==== Exercise 3.3 ====

Input: sif.txt (or your own text)
Output: key words and phrases computed by PageRank (using PR(Vi),HITSA(Vi) and HITSH(Vi) as centrality measures)

Hint: use NetworkX for PageRank and HITS [http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html|http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html]

== Unsupervised methods for key word and phrase selection from a text in a collection ==

The problem: given a collection of texts find those words and phrases (terms) that occur in this text significant frequently than in other texts.

=== Term frequency [Luhn, 1957] ===

The weight of a term that occurs in a document is simply proportional to the term frequency.

=== Inverse document frequency [Spaerck Jones, 1972] ===

The specificity of a term can be quantified as an inverse function of the number of documents in which it occurs.

''tfidf (term, text, collection) = tf (term, document) × idf (term, collection)''

== Variants of TF and IDF weights ==

[[Файл:L3 p7.jpg|обрамить|слева]]

 

== TF-IDF in NLTK ==

===NLTK TextCollection class ===

<code>

In[1]: from nltk.text import TextCollection

In[2]: collection = [WhitespaceTokenizer().tokenize(text) for text in collection]

In[3]: corpus = TextCollection(collection)

In[4]: for i in collection[0]: print i, corpus.tf idf(i,collection[0])

</code>

=== Exercise 3.4 ===

Input: sif2.txt (or your own collection of texts)

Output: list of key words and phrases according to TF-IDF for one text

Hint: <code> use sorted(mylist,key=lambda l:l[1], reverse=True) to sort mylist in descending order based on the second parameter </code>

== TF-IDF alternatives ==

==== Exercise 3.5 ====

Write MI and Chi-squared as an alternative for TF-IDF for measuring significance of a term in a text in a collection.
Check your ideas in Sebastiani[http://arxiv.org/pdf/cs/0110053.pdf|], 2001

== Using TF-IDF to measure text similarity ==

Lecture 3. POS tagging. Key word and phrase extraction

2015-09-02T23:55:56Z

Polidson: /* PageRank [Brin, Page, 1998] */

== Part of speech (POS) ==

Part of speech [Manning, Shuetze, 1999]

Words of a language are grouped into classes which show similar syntactic behavior. These word classes are called parts of speech (POS). Three
important parts of speech are noun, verb, and adjective. The major types of morphological process are in ection, derivation, and compounding.

There are around 9 POS according to different schools:
* Nouns (NN, NP), pronouns (PN, PRP), adjectives (JJ): number, gender, case
* Adjective (JJ): comparative, superlative, short form
* Verbs (VB): subject number, subject person, tense, aspect, modality, participles, voice
* Adverbs (RB), prepositions (IN), conjunctions (, CS), articles (AT)
and particles (RP): nothing

== POS ambiguation ==

Ship (noun or verb?)

* a luxury cruise ship
* Both products are due to ship at the beginning of June
* A new engine was shipped over from the US
* The port is closed to all '''shipping'''

Contest (noun or verb?)
* Stone decided to hold a contest to see who could write the best song.
* She plans to contest a seat in Congress next year.

== POS taggers ==

* Corpus- or dictionary-based VS rule-based
* Ngram-based taggers:
** unigram tagging: assign the most frequent tag
** ngram tagging: look at the context of n previous words (requires a lot of training data)
* Trade-off between the accuracy and the coverage: combine different taggers

===NLTK POS default tagger===

<code>

In[1]: from nltk.tag import pos tag

In[2]: print pos tag(['ship'])

Out[1]: [('ship', 'NN')]

In[3]: print pos tag(['shipping'])

Out[2]: [('shipping', 'VBG')]
</code>

See [http://www.nltk.org/api/nltk.tag.html|http://www.nltk.org/api/nltk.tag.html] for more details on
learning taggers.

== Exercise 3.1 Genre comparison ==

Text genre [Santini, Sharoff, 2009]

The concept of genre is hard to agree upon. Many interpretations have been proposed since Aristotles Poetics without reaching any definite
conclusions about the inventory or even principles for classifying documents into genres. The lack of an agreed definition of what genre is causes the problem of the loose boundaries between the term \genre" with other neighbouring terms, such as "register", "domain", "topic", and "style".

'''Exercise 3.1'''

Input: Two texts of different genre (for example, Wikipedia article and
blog post)
Output: rank all of POS tags for both texts

How can you describe the difference between two genres?

== Key word and phrase extraction ==

There are many definitions of key word and phrase. Thus there are many methods for their extraction:

* supervised VS unsupervised
* frequency-based VS more complex
* from individual text VS from text collection
* word (unigram) VS bigram VS ngram
* term VS named entity VS collocation
* sequential words VS using window

== Supervised methods for key word and phrase extraction ==

I am a word. Am I a key word? Let us build a classifier.

* Am I in the beginning or in the end of the sentence?
* Am I capitalized?
* How many times do I occur?
* Am I used in Wikipedia as a title of a category or an article?
* Am I a term?
* Am I a NE?
* etc.

But we need a collection of marked up texts!

== Unsupervised methods for key word and phrase extraction from a single text ==

* POS patterns
* Association measures: PMI, T-Score, LLR
* Graph methods: TextRank [Mihalcea, Tarau, 2004]
* Syntactic patterns

=== Exercise 3.2 ===

Input: sif1.txt (or your own text)

Key word: top n1 NN

Key phrase: top n2 phrases, that satisfy the following patterns: JJ + NN, NN + NN, NN + IN + NN

Output: list of key words and phrases

Hint: use nltk.ngrams to get ngrams.

== Bigram association measures ==

==== Pointwise Mutual Information [Manning, Shuetze, 1999] ====

PMI measures the reduction of uncertainty about the occurrence of one
word when we are told about the occurrence of the other one.

[[Файл:L3 p1.jpg|350px|слева]]

 

==== T-Score [Manning, Shuetze, 1999] ====

T-Score is a statistical t-test applied to finding collocations. The t-test
looks at the difference between the observed and expected means, scaled
by the variance of the data. The T-score is most useful as a method for
ranking collocations. The level of significance itself is less useful.

[[Файл:L3 p2.jpg|300px|слева]]

 

[[Файл:L3 p3.jpg|400px|слева]]

 

But Chi-squared has many other interesting applications.

==== Chi-squared [Manning, Shuetze, 1999] ====
In general, for the problem of finding collocation, the difference between the T-score and the Chi-squared does not seem to be large.

=== Bigram association measures in NLTK ===

==== NLTK BigramCollocationFinder ====

<code>

In[1]: from nltk.collocations import *

In[2]: bigram measures = nltk.collocations.BigramAssocMeasures()

In[3]: finder = BigramCollocationFinder.from words(tokens)

In[4]: finder.apply freq filter(3)

In[5]: for i in finder.nbest(bigram measures.pmi, 20):

...

</code>

Bigram measures:
* <code> bigram measures.pmi </code>
* <code> bigram measures.student_t </code>
* <code> bigram measures.chi_sq </code>
* <code> igram measures.likelihood_ratio </code>

See [http://www.nltk.org/_modules/nltk/metrics/association.html|http://www.nltk.org/_modules/nltk/metrics/association.html] for more more bigram association measures.

== TextRank: using graph centrality measures for key word and phrase extraction [Mihalcea, Tarau, 2004] ==

# Add words as vertices in the graph.
# Identify relations that connect words:
## consequent words;
## words inside (left or right) the window (2-5 words); and use these relations to draw edges between vertices in the graph. Edges can be directed or undirected, weighted or unweighted.
# Iterate the graph-based ranking algorithm until convergence (for example, PageRank).
# Sort vertices based on their final score. Use the values attached to each vertex for ranking/selection decisions.
# If two adjacent words are selected as potential keywords by TextRank, collapse them into one single key phrase.

See original paper: [http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf|http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf]

Compatibility of systems of linear constraints over the set of natural numbers. Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types systems and systems of mixed types.

[[Файл:L3 p4.jpg|обрамить|TextRank]]

G = (V, E) — a graph, V — vertices, E — edges
''In(Vi)'' — the set of vertices that point to it
''Out(Vi)'' — the set of vertices that ''Vi'' points to
Graph centrality measures:

==== PageRank [Brin, Page, 1998] ====
[[Файл:L3 p5.jpg|250px|слева]]

 

==== HITS [Kleinberg, 1999] ====
[[Файл:L3 p6.jpg|слева]]

 

Key words and phrases, assigned by TextRank using PageRank centrality measure: linear constraints; linear diophantine equations; natural numbers; nonstrict inequations; strict inequations; upper bounds

==== Exercise 3.3 ====

Input: sif.txt (or your own text)
Output: key words and phrases computed by PageRank (using PR(Vi),HITSA(Vi) and HITSH(Vi) as centrality measures)

Hint: use NetworkX for PageRank and HITS [http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html|http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html]

== Unsupervised methods for key word and phrase selection from a text in a collection ==

The problem: given a collection of texts find those words and phrases (terms) that occur in this text significant frequently than in other texts.

=== Term frequency [Luhn, 1957] ===

The weight of a term that occurs in a document is simply proportional to the term frequency.

=== Inverse document frequency [Spaerck Jones, 1972] ===

The specificity of a term can be quantified as an inverse function of the number of documents in which it occurs.

''tfidf (term, text, collection) = tf (term, document) × idf (term, collection)''

== Variants of TF and IDF weights ==

[[Файл:L3 p7.jpg|обрамить|слева]]

 

== TF-IDF in NLTK ==

===NLTK TextCollection class ===

<code>

In[1]: from nltk.text import TextCollection

In[2]: collection = [WhitespaceTokenizer().tokenize(text) for text in collection]

In[3]: corpus = TextCollection(collection)

In[4]: for i in collection[0]: print i, corpus.tf idf(i,collection[0])

</code>

=== Exercise 3.4 ===

Input: sif2.txt (or your own collection of texts)

Output: list of key words and phrases according to TF-IDF for one text

Hint: <code> use sorted(mylist,key=lambda l:l[1], reverse=True) to sort mylist in descending order based on the second parameter </code>

== TF-IDF alternatives ==

==== Exercise 3.5 ====

Write MI and Chi-squared as an alternative for TF-IDF for measuring significance of a term in a text in a collection.
Check your ideas in Sebastiani[http://arxiv.org/pdf/cs/0110053.pdf|], 2001

== Using TF-IDF to measure text similarity ==

Lecture 3. POS tagging. Key word and phrase extraction

2015-09-02T23:55:31Z

Polidson: /* T-Score [Manning, Shuetze, 1999] */

== Part of speech (POS) ==

Part of speech [Manning, Shuetze, 1999]

Words of a language are grouped into classes which show similar syntactic behavior. These word classes are called parts of speech (POS). Three
important parts of speech are noun, verb, and adjective. The major types of morphological process are in ection, derivation, and compounding.

There are around 9 POS according to different schools:
* Nouns (NN, NP), pronouns (PN, PRP), adjectives (JJ): number, gender, case
* Adjective (JJ): comparative, superlative, short form
* Verbs (VB): subject number, subject person, tense, aspect, modality, participles, voice
* Adverbs (RB), prepositions (IN), conjunctions (, CS), articles (AT)
and particles (RP): nothing

== POS ambiguation ==

Ship (noun or verb?)

* a luxury cruise ship
* Both products are due to ship at the beginning of June
* A new engine was shipped over from the US
* The port is closed to all '''shipping'''

Contest (noun or verb?)
* Stone decided to hold a contest to see who could write the best song.
* She plans to contest a seat in Congress next year.

== POS taggers ==

* Corpus- or dictionary-based VS rule-based
* Ngram-based taggers:
** unigram tagging: assign the most frequent tag
** ngram tagging: look at the context of n previous words (requires a lot of training data)
* Trade-off between the accuracy and the coverage: combine different taggers

===NLTK POS default tagger===

<code>

In[1]: from nltk.tag import pos tag

In[2]: print pos tag(['ship'])

Out[1]: [('ship', 'NN')]

In[3]: print pos tag(['shipping'])

Out[2]: [('shipping', 'VBG')]
</code>

See [http://www.nltk.org/api/nltk.tag.html|http://www.nltk.org/api/nltk.tag.html] for more details on
learning taggers.

== Exercise 3.1 Genre comparison ==

Text genre [Santini, Sharoff, 2009]

The concept of genre is hard to agree upon. Many interpretations have been proposed since Aristotles Poetics without reaching any definite
conclusions about the inventory or even principles for classifying documents into genres. The lack of an agreed definition of what genre is causes the problem of the loose boundaries between the term \genre" with other neighbouring terms, such as "register", "domain", "topic", and "style".

'''Exercise 3.1'''

Input: Two texts of different genre (for example, Wikipedia article and
blog post)
Output: rank all of POS tags for both texts

How can you describe the difference between two genres?

== Key word and phrase extraction ==

There are many definitions of key word and phrase. Thus there are many methods for their extraction:

* supervised VS unsupervised
* frequency-based VS more complex
* from individual text VS from text collection
* word (unigram) VS bigram VS ngram
* term VS named entity VS collocation
* sequential words VS using window

== Supervised methods for key word and phrase extraction ==

I am a word. Am I a key word? Let us build a classifier.

* Am I in the beginning or in the end of the sentence?
* Am I capitalized?
* How many times do I occur?
* Am I used in Wikipedia as a title of a category or an article?
* Am I a term?
* Am I a NE?
* etc.

But we need a collection of marked up texts!

== Unsupervised methods for key word and phrase extraction from a single text ==

* POS patterns
* Association measures: PMI, T-Score, LLR
* Graph methods: TextRank [Mihalcea, Tarau, 2004]
* Syntactic patterns

=== Exercise 3.2 ===

Input: sif1.txt (or your own text)

Key word: top n1 NN

Key phrase: top n2 phrases, that satisfy the following patterns: JJ + NN, NN + NN, NN + IN + NN

Output: list of key words and phrases

Hint: use nltk.ngrams to get ngrams.

== Bigram association measures ==

==== Pointwise Mutual Information [Manning, Shuetze, 1999] ====

PMI measures the reduction of uncertainty about the occurrence of one
word when we are told about the occurrence of the other one.

[[Файл:L3 p1.jpg|350px|слева]]

 

==== T-Score [Manning, Shuetze, 1999] ====

T-Score is a statistical t-test applied to finding collocations. The t-test
looks at the difference between the observed and expected means, scaled
by the variance of the data. The T-score is most useful as a method for
ranking collocations. The level of significance itself is less useful.

[[Файл:L3 p2.jpg|300px|слева]]

 

[[Файл:L3 p3.jpg|400px|слева]]

 

But Chi-squared has many other interesting applications.

==== Chi-squared [Manning, Shuetze, 1999] ====
In general, for the problem of finding collocation, the difference between the T-score and the Chi-squared does not seem to be large.

=== Bigram association measures in NLTK ===

==== NLTK BigramCollocationFinder ====

<code>

In[1]: from nltk.collocations import *

In[2]: bigram measures = nltk.collocations.BigramAssocMeasures()

In[3]: finder = BigramCollocationFinder.from words(tokens)

In[4]: finder.apply freq filter(3)

In[5]: for i in finder.nbest(bigram measures.pmi, 20):

...

</code>

Bigram measures:
* <code> bigram measures.pmi </code>
* <code> bigram measures.student_t </code>
* <code> bigram measures.chi_sq </code>
* <code> igram measures.likelihood_ratio </code>

See [http://www.nltk.org/_modules/nltk/metrics/association.html|http://www.nltk.org/_modules/nltk/metrics/association.html] for more more bigram association measures.

== TextRank: using graph centrality measures for key word and phrase extraction [Mihalcea, Tarau, 2004] ==

# Add words as vertices in the graph.
# Identify relations that connect words:
## consequent words;
## words inside (left or right) the window (2-5 words); and use these relations to draw edges between vertices in the graph. Edges can be directed or undirected, weighted or unweighted.
# Iterate the graph-based ranking algorithm until convergence (for example, PageRank).
# Sort vertices based on their final score. Use the values attached to each vertex for ranking/selection decisions.
# If two adjacent words are selected as potential keywords by TextRank, collapse them into one single key phrase.

See original paper: [http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf|http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf]

Compatibility of systems of linear constraints over the set of natural numbers. Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types systems and systems of mixed types.

[[Файл:L3 p4.jpg|обрамить|TextRank]]

G = (V, E) — a graph, V — vertices, E — edges
''In(Vi)'' — the set of vertices that point to it
''Out(Vi)'' — the set of vertices that ''Vi'' points to
Graph centrality measures:

==== PageRank [Brin, Page, 1998] ====
[[Файл:L3 p5.jpg|слева]]

 
==== HITS [Kleinberg, 1999] ====
[[Файл:L3 p6.jpg|слева]]

 

Key words and phrases, assigned by TextRank using PageRank centrality measure: linear constraints; linear diophantine equations; natural numbers; nonstrict inequations; strict inequations; upper bounds

==== Exercise 3.3 ====

Input: sif.txt (or your own text)
Output: key words and phrases computed by PageRank (using PR(Vi),HITSA(Vi) and HITSH(Vi) as centrality measures)

Hint: use NetworkX for PageRank and HITS [http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html|http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html]

== Unsupervised methods for key word and phrase selection from a text in a collection ==

The problem: given a collection of texts find those words and phrases (terms) that occur in this text significant frequently than in other texts.

=== Term frequency [Luhn, 1957] ===

The weight of a term that occurs in a document is simply proportional to the term frequency.

=== Inverse document frequency [Spaerck Jones, 1972] ===

The specificity of a term can be quantified as an inverse function of the number of documents in which it occurs.

''tfidf (term, text, collection) = tf (term, document) × idf (term, collection)''

== Variants of TF and IDF weights ==

[[Файл:L3 p7.jpg|обрамить|слева]]

 

== TF-IDF in NLTK ==

===NLTK TextCollection class ===

<code>

In[1]: from nltk.text import TextCollection

In[2]: collection = [WhitespaceTokenizer().tokenize(text) for text in collection]

In[3]: corpus = TextCollection(collection)

In[4]: for i in collection[0]: print i, corpus.tf idf(i,collection[0])

</code>

=== Exercise 3.4 ===

Input: sif2.txt (or your own collection of texts)

Output: list of key words and phrases according to TF-IDF for one text

Hint: <code> use sorted(mylist,key=lambda l:l[1], reverse=True) to sort mylist in descending order based on the second parameter </code>

== TF-IDF alternatives ==

==== Exercise 3.5 ====

Write MI and Chi-squared as an alternative for TF-IDF for measuring significance of a term in a text in a collection.
Check your ideas in Sebastiani[http://arxiv.org/pdf/cs/0110053.pdf|], 2001

== Using TF-IDF to measure text similarity ==

Lecture 3. POS tagging. Key word and phrase extraction

2015-09-02T23:54:24Z

Polidson: /* Pointwise Mutual Information [Manning, Shuetze, 1999] */

== Part of speech (POS) ==

Part of speech [Manning, Shuetze, 1999]

Words of a language are grouped into classes which show similar syntactic behavior. These word classes are called parts of speech (POS). Three
important parts of speech are noun, verb, and adjective. The major types of morphological process are in ection, derivation, and compounding.

There are around 9 POS according to different schools:
* Nouns (NN, NP), pronouns (PN, PRP), adjectives (JJ): number, gender, case
* Adjective (JJ): comparative, superlative, short form
* Verbs (VB): subject number, subject person, tense, aspect, modality, participles, voice
* Adverbs (RB), prepositions (IN), conjunctions (, CS), articles (AT)
and particles (RP): nothing

== POS ambiguation ==

Ship (noun or verb?)

* a luxury cruise ship
* Both products are due to ship at the beginning of June
* A new engine was shipped over from the US
* The port is closed to all '''shipping'''

Contest (noun or verb?)
* Stone decided to hold a contest to see who could write the best song.
* She plans to contest a seat in Congress next year.

== POS taggers ==

* Corpus- or dictionary-based VS rule-based
* Ngram-based taggers:
** unigram tagging: assign the most frequent tag
** ngram tagging: look at the context of n previous words (requires a lot of training data)
* Trade-off between the accuracy and the coverage: combine different taggers

===NLTK POS default tagger===

<code>

In[1]: from nltk.tag import pos tag

In[2]: print pos tag(['ship'])

Out[1]: [('ship', 'NN')]

In[3]: print pos tag(['shipping'])

Out[2]: [('shipping', 'VBG')]
</code>

See [http://www.nltk.org/api/nltk.tag.html|http://www.nltk.org/api/nltk.tag.html] for more details on
learning taggers.

== Exercise 3.1 Genre comparison ==

Text genre [Santini, Sharoff, 2009]

The concept of genre is hard to agree upon. Many interpretations have been proposed since Aristotles Poetics without reaching any definite
conclusions about the inventory or even principles for classifying documents into genres. The lack of an agreed definition of what genre is causes the problem of the loose boundaries between the term \genre" with other neighbouring terms, such as "register", "domain", "topic", and "style".

'''Exercise 3.1'''

Input: Two texts of different genre (for example, Wikipedia article and
blog post)
Output: rank all of POS tags for both texts

How can you describe the difference between two genres?

== Key word and phrase extraction ==

There are many definitions of key word and phrase. Thus there are many methods for their extraction:

* supervised VS unsupervised
* frequency-based VS more complex
* from individual text VS from text collection
* word (unigram) VS bigram VS ngram
* term VS named entity VS collocation
* sequential words VS using window

== Supervised methods for key word and phrase extraction ==

I am a word. Am I a key word? Let us build a classifier.

* Am I in the beginning or in the end of the sentence?
* Am I capitalized?
* How many times do I occur?
* Am I used in Wikipedia as a title of a category or an article?
* Am I a term?
* Am I a NE?
* etc.

But we need a collection of marked up texts!

== Unsupervised methods for key word and phrase extraction from a single text ==

* POS patterns
* Association measures: PMI, T-Score, LLR
* Graph methods: TextRank [Mihalcea, Tarau, 2004]
* Syntactic patterns

=== Exercise 3.2 ===

Input: sif1.txt (or your own text)

Key word: top n1 NN

Key phrase: top n2 phrases, that satisfy the following patterns: JJ + NN, NN + NN, NN + IN + NN

Output: list of key words and phrases

Hint: use nltk.ngrams to get ngrams.

== Bigram association measures ==

==== Pointwise Mutual Information [Manning, Shuetze, 1999] ====

PMI measures the reduction of uncertainty about the occurrence of one
word when we are told about the occurrence of the other one.

[[Файл:L3 p1.jpg|350px|слева]]

 

==== T-Score [Manning, Shuetze, 1999] ====

T-Score is a statistical t-test applied to finding collocations. The t-test
looks at the difference between the observed and expected means, scaled
by the variance of the data. The T-score is most useful as a method for
ranking collocations. The level of significance itself is less useful.

[[Файл:L3 p2.jpg|слева]]

 

[[Файл:L3 p3.jpg|слева]]

 

But Chi-squared has many other interesting applications.

==== Chi-squared [Manning, Shuetze, 1999] ====
In general, for the problem of finding collocation, the difference between the T-score and the Chi-squared does not seem to be large.

=== Bigram association measures in NLTK ===

==== NLTK BigramCollocationFinder ====

<code>

In[1]: from nltk.collocations import *

In[2]: bigram measures = nltk.collocations.BigramAssocMeasures()

In[3]: finder = BigramCollocationFinder.from words(tokens)

In[4]: finder.apply freq filter(3)

In[5]: for i in finder.nbest(bigram measures.pmi, 20):

...

</code>

Bigram measures:
* <code> bigram measures.pmi </code>
* <code> bigram measures.student_t </code>
* <code> bigram measures.chi_sq </code>
* <code> igram measures.likelihood_ratio </code>

See [http://www.nltk.org/_modules/nltk/metrics/association.html|http://www.nltk.org/_modules/nltk/metrics/association.html] for more more bigram association measures.

== TextRank: using graph centrality measures for key word and phrase extraction [Mihalcea, Tarau, 2004] ==

# Add words as vertices in the graph.
# Identify relations that connect words:
## consequent words;
## words inside (left or right) the window (2-5 words); and use these relations to draw edges between vertices in the graph. Edges can be directed or undirected, weighted or unweighted.
# Iterate the graph-based ranking algorithm until convergence (for example, PageRank).
# Sort vertices based on their final score. Use the values attached to each vertex for ranking/selection decisions.
# If two adjacent words are selected as potential keywords by TextRank, collapse them into one single key phrase.

See original paper: [http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf|http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf]

Compatibility of systems of linear constraints over the set of natural numbers. Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types systems and systems of mixed types.

[[Файл:L3 p4.jpg|обрамить|TextRank]]

G = (V, E) — a graph, V — vertices, E — edges
''In(Vi)'' — the set of vertices that point to it
''Out(Vi)'' — the set of vertices that ''Vi'' points to
Graph centrality measures:

==== PageRank [Brin, Page, 1998] ====
[[Файл:L3 p5.jpg|слева]]

 
==== HITS [Kleinberg, 1999] ====
[[Файл:L3 p6.jpg|слева]]

 

Key words and phrases, assigned by TextRank using PageRank centrality measure: linear constraints; linear diophantine equations; natural numbers; nonstrict inequations; strict inequations; upper bounds

==== Exercise 3.3 ====

Input: sif.txt (or your own text)
Output: key words and phrases computed by PageRank (using PR(Vi),HITSA(Vi) and HITSH(Vi) as centrality measures)

Hint: use NetworkX for PageRank and HITS [http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html|http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html]

== Unsupervised methods for key word and phrase selection from a text in a collection ==

The problem: given a collection of texts find those words and phrases (terms) that occur in this text significant frequently than in other texts.

=== Term frequency [Luhn, 1957] ===

The weight of a term that occurs in a document is simply proportional to the term frequency.

=== Inverse document frequency [Spaerck Jones, 1972] ===

The specificity of a term can be quantified as an inverse function of the number of documents in which it occurs.

''tfidf (term, text, collection) = tf (term, document) × idf (term, collection)''

== Variants of TF and IDF weights ==

[[Файл:L3 p7.jpg|обрамить|слева]]

 

== TF-IDF in NLTK ==

===NLTK TextCollection class ===

<code>

In[1]: from nltk.text import TextCollection

In[2]: collection = [WhitespaceTokenizer().tokenize(text) for text in collection]

In[3]: corpus = TextCollection(collection)

In[4]: for i in collection[0]: print i, corpus.tf idf(i,collection[0])

</code>

=== Exercise 3.4 ===

Input: sif2.txt (or your own collection of texts)

Output: list of key words and phrases according to TF-IDF for one text

Hint: <code> use sorted(mylist,key=lambda l:l[1], reverse=True) to sort mylist in descending order based on the second parameter </code>

== TF-IDF alternatives ==

==== Exercise 3.5 ====

Write MI and Chi-squared as an alternative for TF-IDF for measuring significance of a term in a text in a collection.
Check your ideas in Sebastiani[http://arxiv.org/pdf/cs/0110053.pdf|], 2001

== Using TF-IDF to measure text similarity ==

NLP References

2015-09-02T22:51:10Z

Polidson: Новая страница: «# Salton, Gerard, and Christopher Buckley. Term-weighting approaches in automatic text retrieval. Information processing and management 24.5 (1988): 513-523. # Wo…»

# Salton, Gerard, and Christopher Buckley. Term-weighting approaches in automatic text retrieval. Information processing and management 24.5 (1988): 513-523.
# Wong, SK Michael, Wojciech Ziarko, and Patrick CN Wong. Generalized vector spaces model in information retrieval. Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 1985.
# Turney, Peter D., and Patrick Pantel. From frequency to meaning: Vector space models of semantics. Journal of artificial intelligence research 37.1 (2010): 141-188.
# Ponte, Jay M., and W. Bruce Croft. A language modeling approach to information retrieval. Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 1998.
# Zamir, Oren, and Oren Etzioni. Web document clustering: A feasibility demonstration. Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 1998.
# Kennington, Casey Redd, Martin Kay, and Annemarie Friedrich. Suffix Trees as Language Models. LREC. 2012.
# Huang, Jin Hu, and David Powers. Suffix tree based approach for chinese information retrieval. Intelligent Systems Design and Applications, 2008. ISDA'08. Eighth International Conference on. Vol. 3. IEEE, 2008.
# Zhang, Dell, and Wee Sun Lee. Extracting key-substring-group features for text classification. Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2006.
# Gusfield, Dan. Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge university press, 1997.
# Pampapathi R., Mirkin B., Levene M., A suffix tree approach to anti-spam email filtering, Machine Learning, 2006, Vol. 65, no.1, pp. 309-338.
#Chernyak E.L., Chugunova O.N., Mirkin B.G., Annotated suffix tree method for measuring degree of string to text belongingness, Business Informatics, 2012. Vol. 21, no.3, pp. 31-41 (in Russian).
# Chernyak E.L., Chugunova O.N., Askarova J.A., Nascimento S., Mirkin B.G., Abstracting concepts from text documents by using an ontology, in Proceedings of the 1st International Workshop on Concept Discovery in Unstructured Data. 2011, pp. 21-31.
# Chernyak E. L. An approach to the problem of annotation of research publications, Proceedings of The Eighth International Conference on Web Search and Data Mining, pp. 429-434.
# Chernyak E. L., Mirkin B. G. Refining a Taxonomy by Using Annotated Suffix Trees and Wikipedia Resources. Annals of Data Science. Vol. 2. No. 1. P. 61-82, 2015.
# Morenko, E. N., Chernyak E.L., Mirkin B.G.. Conceptual Maps: Construction Over a Text Collection and Analysis. In Analysis of Images, Social Networks and Texts, pp. 163-168. Springer International Publishing, 2014.
# Martin, James H., and Daniel Jurafsky. "Speech and language processing." International Edition (2000).
# Manning, Christopher D., and Hinrich Schuetze. Foundations of statistical natural language processing. MIT press, 1999.
# Santini, Marina, and Serge Sharoff. Web Genre Benchmark Under Construction. JLCL, Volume 24 (1), 2009.
# Luhn, Hans Peter. "A statistical approach to mechanized encoding and searching of literary information." IBM Journal of research and development 1.4 (1957): 309-317.
# Sparck Jones, Karen. "A statistical interpretation of term specificity and its application in retrieval." Journal of documentation 28.1 (1972): 11-21.
# Sebastiani, Fabrizio. "Machine learning in automated text categorization." ACM computing surveys (CSUR) 34.1 (2002): 1-47.
# Salton, Gerard, Anita Wong, and Chung-Shu Yang. "A vector space model for automatic indexing." Communications of the ACM 18.11 (1975): 613-620.
# Bird, Steven, Ewan Klein, and Edward Loper. Natural language processing with Python. " O'Reilly Media, Inc.", 2009.

О факультете

2015-09-02T22:51:01Z

Polidson: /* Summer School 2015 */

== Факультет компьютерных наук НИУ ВШЭ ==
=== Курсы за 2015/16 учебный год ===
[[Майнор Интеллектуальный анализ данных]] 
#[[Майнор Интеллектуальный анализ данных/Введение в программирование|Введение в программирование]]

[[Компьютерные системы]]

[[Математический анализ]]

=== Summer School 2015 ===
[[Introduction to Natural Language Processing|Introduction to Natural Language Processing]]
#[[Lecture 1. Introduction|Introduction]]
#[[Lecture 2. Tokenization and word counts|Tokenization and word counts]]
#[[Lecture 3. POS tagging. Key word and phrase extraction|POS tagging. Key word and phrase extraction]]
#[[Lecture 4. Parsing|Parsing]]
#[[Lecture 5. Language sources|Language sources]]
#[[Lecture 6. Synonyms and near-synonyms detection|Synonyms and near-synonyms detection]]
#[[Lecture 8. Suffix trees for NLP|Suffix trees for NLP]]
#[[NLP References|References]]

=== Курсы за 2014/15 учебный год ===
[[Основы и методологии программирования]] 
[[Алгоритмы и структуры данных]] 
[[Анализ данных (Программная инженерия)]] 
[[Алгебра]] 
[[Magolego_sna_2015| MAGoLEGO Social Network Analysis]]

=== Проектная работа, 2015 год ===
[[Проектная работа]] 
[[Учебная практика 1 курс (2015)]]

NLPref

2015-09-02T22:50:19Z

О факультете

2015-09-02T22:42:26Z

Polidson: /* Summer School 2015 */

== Факультет компьютерных наук НИУ ВШЭ ==
=== Курсы за 2015/16 учебный год ===
[[Майнор Интеллектуальный анализ данных]] 
#[[Майнор Интеллектуальный анализ данных/Введение в программирование|Введение в программирование]]

[[Компьютерные системы]]

[[Математический анализ]]

=== Summer School 2015 ===
[[Introduction to Natural Language Processing|Introduction to Natural Language Processing]]
#[[Lecture 1. Introduction|Introduction]]
#[[Lecture 2. Tokenization and word counts|Tokenization and word counts]]
#[[Lecture 3. POS tagging. Key word and phrase extraction|POS tagging. Key word and phrase extraction]]
#[[Lecture 4. Parsing|Parsing]]
#[[Lecture 5. Language sources|Language sources]]
#[[Lecture 6. Synonyms and near-synonyms detection|Synonyms and near-synonyms detection]]
#[[Lecture 8. Suffix trees for NLP|Suffix trees for NLP]]
#[[NLPref|References]]

=== Курсы за 2014/15 учебный год ===
[[Основы и методологии программирования]] 
[[Алгоритмы и структуры данных]] 
[[Анализ данных (Программная инженерия)]] 
[[Алгебра]] 
[[Magolego_sna_2015| MAGoLEGO Social Network Analysis]]

=== Проектная работа, 2015 год ===
[[Проектная работа]] 
[[Учебная практика 1 курс (2015)]]

Lecture 8. Suffix trees for NLP

2015-09-02T22:38:45Z

Polidson: /* Annotated suffix tree (AST) */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|350px|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-02T22:38:11Z

Polidson: /* Annotated suffix tree scoring */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-02T22:37:55Z

Polidson: /* Annotated suffix tree scoring */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|550px|слева]]
[[Файл:L8 6.jpg|550px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-02T22:37:26Z

Polidson: /* Annotated suffix tree */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg|350px]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|500px|слева]]
[[Файл:L8 6.jpg|500px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-02T22:37:00Z

Polidson: /* Annotated suffix tree construction */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg|350px]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|500px|слева]]
[[Файл:L8 6.jpg|500px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-09-02T22:36:15Z

Polidson: /* Annotated suffix tree scoring */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|500px|слева]]
[[Файл:L8 6.jpg|500px|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 2. Tokenization and word counts

2015-09-02T22:31:31Z

Polidson: /* Natural Language Toolkit (NLTK) */

== How many words? ==

"The rain in Spain stays mainly in the plain."
9 '''tokens''': The, rain, in, Spain, stays, mainly, in, the, plain
7 (or 8) '''types''': T = the rain, in, Spain, stays, mainly, plain

=== Type and token ===

''Type'' is an element of the vocabulary.

''Token'' is an instance of that type in the text.

N = number of tokens;

V - vocabulary (i.e. all types);

|V| = size of vocabulary (i.e. number of types).

How are N and |V| related?

== Zipf's law ==

=== Zipf's law ([Gelbukh, Sidorov, 2001]) ===

In any large enough text, the frequency ranks (starting from the highest)
of types are inversely proportional to the corresponding frequencies:
f = 1/r

''f'' — frequency of a type;

''r'' — rank of a type (its position in the list of all types in order of their frequency of occurrence).

[[Файл:L2 p1.jpg|мини|Zipf's law: example]]

== Heaps' law ==

Heaps' law ([Gelbukh, Sidorov, 2001])

The number of different types in a text is roughly proportional to an exponent of its size:
[[Файл:L2 p2.jpg|мини|слева]]

''N'' = number of tokens;

|V| = size of vocabulary (i.e. number of types);

''K'', ''b'' — free parameters, K ∈ [10; 100]; b ∈ [0.4; 0.6]

== Why tokenization is difficult? ==

*Easy example: "Good muffins cost $3.88 in New York. Please buy me two of them. Thanks."
** is \." a token?
** is $3.88 a single token?
** is \New York" a single token?
*Real data may contain noise in it: code, markup, URLs, faulty punctuation
* Real data contains misspellings: "an dthen she aksed"
*Period "." does not always mean the end of sentence: m.p.h., PhD.

Nevertheless tokenization is important for all other text processing steps.
There are rule-based and machine learning-based approaches to development of tokenizers.

== Rule-based tokenization ==

For example, define a token as a sequence of upper and lower case letters: A-Za-z. Reqular expression is a nice tool for programming such rules.

===RE in Python===

<code>
In[1]: import re

In[2]: prog = re.compile('[A-Za-z]+')

In[3]: prog.findall("Words, words, words.")

Out[1]: ['Words', 'words', 'words']
</code>

== Sentence segmentation ==

What are the sentence boundaries?
* ?, ! are usually unambiguous
* Period "." is an issue
* Direct speech is also an issue: She said, "What time will you be home?" and I said, "I don't know!". Even worse in Russian!

Let us learn a classifier for sentence segmentation.

===Binary classifier ===

A binary classifier f : X ⇒ 0; 1 takes input data ''X'' (a set of sentences) and decides EndOfSentence (0) or NotEndOfSentence (1).

What can be the features for classification? I am a period, am I EndOfSentence?
* Lots of blanks after me?
* Lots of lower case letters and ? or ! after me?
* Do I belong to abbreviation?
* etc.

We need a lot of hand-markup.

== Natural Language Toolkit (NLTK) ==

Do we need to program this?
No! There is Natural Language Toolkit (NLTK) for everything.

'''NLTK tokenizers'''

<code>
In[1]: from nltk.tokenize import RegexpTokenizer,
wordpunct tokenize

In[2]: s = 'Good muffins cost $3.88 in New York. Please
buy me two of them. Thanks.'

In[3]: tokenizer = RegexpTokenizer('\w+ | \$ [\d \.]+ | S \+')

In[4]: tokenizer.tokenize(s)

In[5]: wordpunct tokenize(s)
</code>

=== Learning to tokenize ===

nltk.tokenize.punkt is a tool for learning to tokenize from your data. It includes pre-trained Punkt tokenizer for English.

==== Punkt tokenizer ====
<code>
In[1]: import nltk.data

In[2]: sent detector = nltk.data.load('tokenizers/punkt/english.pickle')

In[3]: sent detector.tokenize(s)

</code>

== Exercise 1.1 Word counts ==

Input: Alice in Wonderland (alice.txt) or your text

Output 1: number of tokens

Output 2: number of types

Use nltk.FreqDist() to count types. nltk.FreqDist() is a frequency
dictionary: [key, frequency(key)].

== Lemmatization (Normalization) ==

Each word has a base form:
* has, had, have ⇒ have
* cats, cat, cat's ⇒ cat
* Windows ⇒ window or Windows?

=== Lemmatization [Jurafsky, Martin, 1999] ===
Lemmatization (or normalization) is used to reduce in ections or variant forms to base forms. A dictionary with headwords is required.

=== Lemmatization ===

<code>

In[1]: from nltk.stem import WordNetLemmatizer

In[2]: lemmatizer = WordNetLemmatizer()

In[3]: lemmatizer.lemmatize(t)

</code>

== Stemming ==

A word is built with morphems: ''word = stem + affixes''. Sometimes we do not need affixes.

translate, translation, translator ⇒ translat

=== Stemming [Jurafsky, Martin, 1999] ===

Reduce terms to their stems in information retrieval and text classification. Porter's algorithm is the most common English stemmer.

=== Stemming ===

<code>
In[1]: from nltk.stem.porter import PorterStemmer

In[2]: stemmer = PorterStemmer()

In[3]: stemmer.stem(t)
</code>

== Exercise 1.2 Word counts (continued) ==

Input: Alice in Wonderland (alice.txt) or your text

Output 1: 20 most common lemmata

Output 2: 20 most common stems

Use FreqDist() to count lemmata and stems. Use FreqDist().most common() to find most common lemmata and stems.

== Exercise 1.3 Do we need all words? ==

Stopword is a not meaningful word: prepositions, adjunctions, pronouns, articles, etc.

'''Stopwords'''
<code>

In[1]: from nltk.corpus import stopwords

In[2]: print stopwords.words('english')

</code>

'''Exercise 1.3'''

Input: Alice in Wonderland (alice.txt) or your text

Output 1: 20 most common lemmata without stop words

Use not in operator to exclude not stopwords in a cycle.

Lecture 8. Suffix trees for NLP

2015-09-02T22:30:38Z

Polidson: /* Language Model [Ponte, Croft, 1998] */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1)p(t2)p(t3)

Bigram model: p(t1 t2 t3) = p(t1|BOS) p(t2|t1)p(t3|t2)p(EOS|t3)

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|слева]]
[[Файл:L8 6.jpg|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-08-31T21:27:53Z

Polidson: /* Language Model [Ponte, Croft, 1998] */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t1 )p(t2 )p(t3 )

Bigram model: p(t1 t2 t3 ) = p(t1 |BOS)p(t2 |t1 )p(t3 |t2 )p(EOS|t3 )

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|слева]]
[[Файл:L8 6.jpg|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-08-31T21:27:35Z

Polidson: /* Language Model [Ponte, Croft, 1998] */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t1 t2 t3 ) = p(t 1 )p(t2 )p(t3 )

Bigram model: p(t1 t2 t3 ) = p(t1 |BOS)p(t2 |t1 )p(t3 |t2 )p(EOS|t3 )

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|слева]]
[[Файл:L8 6.jpg|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 3. POS tagging. Key word and phrase extraction

2015-08-31T21:26:18Z

Polidson: /* Exercise 3.2 */

== Part of speech (POS) ==

Part of speech [Manning, Shuetze, 1999]

Words of a language are grouped into classes which show similar syntactic behavior. These word classes are called parts of speech (POS). Three
important parts of speech are noun, verb, and adjective. The major types of morphological process are in ection, derivation, and compounding.

There are around 9 POS according to different schools:
* Nouns (NN, NP), pronouns (PN, PRP), adjectives (JJ): number, gender, case
* Adjective (JJ): comparative, superlative, short form
* Verbs (VB): subject number, subject person, tense, aspect, modality, participles, voice
* Adverbs (RB), prepositions (IN), conjunctions (, CS), articles (AT)
and particles (RP): nothing

== POS ambiguation ==

Ship (noun or verb?)

* a luxury cruise ship
* Both products are due to ship at the beginning of June
* A new engine was shipped over from the US
* The port is closed to all '''shipping'''

Contest (noun or verb?)
* Stone decided to hold a contest to see who could write the best song.
* She plans to contest a seat in Congress next year.

== POS taggers ==

* Corpus- or dictionary-based VS rule-based
* Ngram-based taggers:
** unigram tagging: assign the most frequent tag
** ngram tagging: look at the context of n previous words (requires a lot of training data)
* Trade-off between the accuracy and the coverage: combine different taggers

===NLTK POS default tagger===

<code>

In[1]: from nltk.tag import pos tag

In[2]: print pos tag(['ship'])

Out[1]: [('ship', 'NN')]

In[3]: print pos tag(['shipping'])

Out[2]: [('shipping', 'VBG')]
</code>

See [http://www.nltk.org/api/nltk.tag.html|http://www.nltk.org/api/nltk.tag.html] for more details on
learning taggers.

== Exercise 3.1 Genre comparison ==

Text genre [Santini, Sharoff, 2009]

The concept of genre is hard to agree upon. Many interpretations have been proposed since Aristotles Poetics without reaching any definite
conclusions about the inventory or even principles for classifying documents into genres. The lack of an agreed definition of what genre is causes the problem of the loose boundaries between the term \genre" with other neighbouring terms, such as "register", "domain", "topic", and "style".

'''Exercise 3.1'''

Input: Two texts of different genre (for example, Wikipedia article and
blog post)
Output: rank all of POS tags for both texts

How can you describe the difference between two genres?

== Key word and phrase extraction ==

There are many definitions of key word and phrase. Thus there are many methods for their extraction:

* supervised VS unsupervised
* frequency-based VS more complex
* from individual text VS from text collection
* word (unigram) VS bigram VS ngram
* term VS named entity VS collocation
* sequential words VS using window

== Supervised methods for key word and phrase extraction ==

I am a word. Am I a key word? Let us build a classifier.

* Am I in the beginning or in the end of the sentence?
* Am I capitalized?
* How many times do I occur?
* Am I used in Wikipedia as a title of a category or an article?
* Am I a term?
* Am I a NE?
* etc.

But we need a collection of marked up texts!

== Unsupervised methods for key word and phrase extraction from a single text ==

* POS patterns
* Association measures: PMI, T-Score, LLR
* Graph methods: TextRank [Mihalcea, Tarau, 2004]
* Syntactic patterns

=== Exercise 3.2 ===

Input: sif1.txt (or your own text)

Key word: top n1 NN

Key phrase: top n2 phrases, that satisfy the following patterns: JJ + NN, NN + NN, NN + IN + NN

Output: list of key words and phrases

Hint: use nltk.ngrams to get ngrams.

== Bigram association measures ==

==== Pointwise Mutual Information [Manning, Shuetze, 1999] ====

PMI measures the reduction of uncertainty about the occurrence of one
word when we are told about the occurrence of the other one.

[[Файл:L3 p1.jpg|слева]]

 
==== T-Score [Manning, Shuetze, 1999] ====

T-Score is a statistical t-test applied to finding collocations. The t-test
looks at the difference between the observed and expected means, scaled
by the variance of the data. The T-score is most useful as a method for
ranking collocations. The level of significance itself is less useful.

[[Файл:L3 p2.jpg|слева]]

 

[[Файл:L3 p3.jpg|слева]]

 

But Chi-squared has many other interesting applications.

==== Chi-squared [Manning, Shuetze, 1999] ====
In general, for the problem of finding collocation, the difference between the T-score and the Chi-squared does not seem to be large.

=== Bigram association measures in NLTK ===

==== NLTK BigramCollocationFinder ====

<code>

In[1]: from nltk.collocations import *

In[2]: bigram measures = nltk.collocations.BigramAssocMeasures()

In[3]: finder = BigramCollocationFinder.from words(tokens)

In[4]: finder.apply freq filter(3)

In[5]: for i in finder.nbest(bigram measures.pmi, 20):

...

</code>

Bigram measures:
* <code> bigram measures.pmi </code>
* <code> bigram measures.student_t </code>
* <code> bigram measures.chi_sq </code>
* <code> igram measures.likelihood_ratio </code>

See [http://www.nltk.org/_modules/nltk/metrics/association.html|http://www.nltk.org/_modules/nltk/metrics/association.html] for more more bigram association measures.

== TextRank: using graph centrality measures for key word and phrase extraction [Mihalcea, Tarau, 2004] ==

# Add words as vertices in the graph.
# Identify relations that connect words:
## consequent words;
## words inside (left or right) the window (2-5 words); and use these relations to draw edges between vertices in the graph. Edges can be directed or undirected, weighted or unweighted.
# Iterate the graph-based ranking algorithm until convergence (for example, PageRank).
# Sort vertices based on their final score. Use the values attached to each vertex for ranking/selection decisions.
# If two adjacent words are selected as potential keywords by TextRank, collapse them into one single key phrase.

See original paper: [http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf|http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf]

Compatibility of systems of linear constraints over the set of natural numbers. Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types systems and systems of mixed types.

[[Файл:L3 p4.jpg|обрамить|TextRank]]

G = (V, E) — a graph, V — vertices, E — edges
''In(Vi)'' — the set of vertices that point to it
''Out(Vi)'' — the set of vertices that ''Vi'' points to
Graph centrality measures:

==== PageRank [Brin, Page, 1998] ====
[[Файл:L3 p5.jpg|слева]]

 
==== HITS [Kleinberg, 1999] ====
[[Файл:L3 p6.jpg|слева]]

 

Key words and phrases, assigned by TextRank using PageRank centrality measure: linear constraints; linear diophantine equations; natural numbers; nonstrict inequations; strict inequations; upper bounds

==== Exercise 3.3 ====

Input: sif.txt (or your own text)
Output: key words and phrases computed by PageRank (using PR(Vi),HITSA(Vi) and HITSH(Vi) as centrality measures)

Hint: use NetworkX for PageRank and HITS [http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html|http://networkx.github.io/documentation/networkx-1.9.1/reference/algorithms.link_analysis.html]

== Unsupervised methods for key word and phrase selection from a text in a collection ==

The problem: given a collection of texts find those words and phrases (terms) that occur in this text significant frequently than in other texts.

=== Term frequency [Luhn, 1957] ===

The weight of a term that occurs in a document is simply proportional to the term frequency.

=== Inverse document frequency [Spaerck Jones, 1972] ===

The specificity of a term can be quantified as an inverse function of the number of documents in which it occurs.

''tfidf (term, text, collection) = tf (term, document) × idf (term, collection)''

== Variants of TF and IDF weights ==

[[Файл:L3 p7.jpg|обрамить|слева]]

 

== TF-IDF in NLTK ==

===NLTK TextCollection class ===

<code>

In[1]: from nltk.text import TextCollection

In[2]: collection = [WhitespaceTokenizer().tokenize(text) for text in collection]

In[3]: corpus = TextCollection(collection)

In[4]: for i in collection[0]: print i, corpus.tf idf(i,collection[0])

</code>

=== Exercise 3.4 ===

Input: sif2.txt (or your own collection of texts)

Output: list of key words and phrases according to TF-IDF for one text

Hint: <code> use sorted(mylist,key=lambda l:l[1], reverse=True) to sort mylist in descending order based on the second parameter </code>

== TF-IDF alternatives ==

==== Exercise 3.5 ====

Write MI and Chi-squared as an alternative for TF-IDF for measuring significance of a term in a text in a collection.
Check your ideas in Sebastiani[http://arxiv.org/pdf/cs/0110053.pdf|], 2001

== Using TF-IDF to measure text similarity ==

Lecture 2. Tokenization and word counts

2015-08-31T21:25:29Z

Polidson: /* Heaps' law */

== How many words? ==

"The rain in Spain stays mainly in the plain."
9 '''tokens''': The, rain, in, Spain, stays, mainly, in, the, plain
7 (or 8) '''types''': T = the rain, in, Spain, stays, mainly, plain

=== Type and token ===

''Type'' is an element of the vocabulary.

''Token'' is an instance of that type in the text.

N = number of tokens;

V - vocabulary (i.e. all types);

|V| = size of vocabulary (i.e. number of types).

How are N and |V| related?

== Zipf's law ==

=== Zipf's law ([Gelbukh, Sidorov, 2001]) ===

In any large enough text, the frequency ranks (starting from the highest)
of types are inversely proportional to the corresponding frequencies:
f = 1/r

''f'' — frequency of a type;

''r'' — rank of a type (its position in the list of all types in order of their frequency of occurrence).

[[Файл:L2 p1.jpg|мини|Zipf's law: example]]

== Heaps' law ==

Heaps' law ([Gelbukh, Sidorov, 2001])

The number of different types in a text is roughly proportional to an exponent of its size:
[[Файл:L2 p2.jpg|мини|слева]]

''N'' = number of tokens;

|V| = size of vocabulary (i.e. number of types);

''K'', ''b'' — free parameters, K ∈ [10; 100]; b ∈ [0.4; 0.6]

== Why tokenization is difficult? ==

*Easy example: "Good muffins cost $3.88 in New York. Please buy me two of them. Thanks."
** is \." a token?
** is $3.88 a single token?
** is \New York" a single token?
*Real data may contain noise in it: code, markup, URLs, faulty punctuation
* Real data contains misspellings: "an dthen she aksed"
*Period "." does not always mean the end of sentence: m.p.h., PhD.

Nevertheless tokenization is important for all other text processing steps.
There are rule-based and machine learning-based approaches to development of tokenizers.

== Rule-based tokenization ==

For example, define a token as a sequence of upper and lower case letters: A-Za-z. Reqular expression is a nice tool for programming such rules.

===RE in Python===

<code>
In[1]: import re

In[2]: prog = re.compile('[A-Za-z]+')

In[3]: prog.findall("Words, words, words.")

Out[1]: ['Words', 'words', 'words']
</code>

== Sentence segmentation ==

What are the sentence boundaries?
* ?, ! are usually unambiguous
* Period "." is an issue
* Direct speech is also an issue: She said, "What time will you be home?" and I said, "I don't know!". Even worse in Russian!

Let us learn a classifier for sentence segmentation.

===Binary classifier ===

A binary classifier f : X ⇒ 0; 1 takes input data ''X'' (a set of sentences) and decides EndOfSentence (0) or NotEndOfSentence (1).

What can be the features for classification? I am a period, am I EndOfSentence?
* Lots of blanks after me?
* Lots of lower case letters and ? or ! after me?
* Do I belong to abbreviation?
* etc.

We need a lot of hand-markup.

== Natural Language Toolkit (NLTK) ==

Do we need to program this?
No! There is Natural Language Toolkit (NLTK) for everything.

'''NLTK tokenizers'''
<code>
In[1]: from nltk.tokenize import RegexpTokenizer,
wordpunct tokenize

In[2]: s = 'Good muffins cost $3.88 in New York. Please
buy me two of them. Thanks.'

In[3]: tokenizer = RegexpTokenizer('\w+ | \$ [\d \.]+ | S \+')

In[4]: tokenizer.tokenize(s)

In[5]: wordpunct tokenize(s)
</code>

=== Learning to tokenize ===

nltk.tokenize.punkt is a tool for learning to tokenize from your data. It includes pre-trained Punkt tokenizer for English.

==== Punkt tokenizer ====
<code>
In[1]: import nltk.data

In[2]: sent detector = nltk.data.load('tokenizers/punkt/english.pickle')

In[3]: sent detector.tokenize(s)

</code>

== Exercise 1.1 Word counts ==

Input: Alice in Wonderland (alice.txt) or your text

Output 1: number of tokens

Output 2: number of types

Use nltk.FreqDist() to count types. nltk.FreqDist() is a frequency
dictionary: [key, frequency(key)].

== Lemmatization (Normalization) ==

Each word has a base form:
* has, had, have ⇒ have
* cats, cat, cat's ⇒ cat
* Windows ⇒ window or Windows?

=== Lemmatization [Jurafsky, Martin, 1999] ===
Lemmatization (or normalization) is used to reduce in ections or variant forms to base forms. A dictionary with headwords is required.

=== Lemmatization ===

<code>

In[1]: from nltk.stem import WordNetLemmatizer

In[2]: lemmatizer = WordNetLemmatizer()

In[3]: lemmatizer.lemmatize(t)

</code>

== Stemming ==

A word is built with morphems: ''word = stem + affixes''. Sometimes we do not need affixes.

translate, translation, translator ⇒ translat

=== Stemming [Jurafsky, Martin, 1999] ===

Reduce terms to their stems in information retrieval and text classification. Porter's algorithm is the most common English stemmer.

=== Stemming ===

<code>
In[1]: from nltk.stem.porter import PorterStemmer

In[2]: stemmer = PorterStemmer()

In[3]: stemmer.stem(t)
</code>

== Exercise 1.2 Word counts (continued) ==

Input: Alice in Wonderland (alice.txt) or your text

Output 1: 20 most common lemmata

Output 2: 20 most common stems

Use FreqDist() to count lemmata and stems. Use FreqDist().most common() to find most common lemmata and stems.

== Exercise 1.3 Do we need all words? ==

Stopword is a not meaningful word: prepositions, adjunctions, pronouns, articles, etc.

'''Stopwords'''
<code>

In[1]: from nltk.corpus import stopwords

In[2]: print stopwords.words('english')

</code>

'''Exercise 1.3'''

Input: Alice in Wonderland (alice.txt) or your text

Output 1: 20 most common lemmata without stop words

Use not in operator to exclude not stopwords in a cycle.

Lecture 2. Tokenization and word counts

2015-08-31T21:25:09Z

Polidson: /* Binary classifier */

== How many words? ==

"The rain in Spain stays mainly in the plain."
9 '''tokens''': The, rain, in, Spain, stays, mainly, in, the, plain
7 (or 8) '''types''': T = the rain, in, Spain, stays, mainly, plain

=== Type and token ===

''Type'' is an element of the vocabulary.

''Token'' is an instance of that type in the text.

N = number of tokens;

V - vocabulary (i.e. all types);

|V| = size of vocabulary (i.e. number of types).

How are N and |V| related?

== Zipf's law ==

=== Zipf's law ([Gelbukh, Sidorov, 2001]) ===

In any large enough text, the frequency ranks (starting from the highest)
of types are inversely proportional to the corresponding frequencies:
f = 1/r

''f'' — frequency of a type;

''r'' — rank of a type (its position in the list of all types in order of their frequency of occurrence).

[[Файл:L2 p1.jpg|мини|Zipf's law: example]]

== Heaps' law ==

Heaps' law ([Gelbukh, Sidorov, 2001])

The number of different types in a text is roughly proportional to an exponent of its size:
[[Файл:L2 p2.jpg|мини|слева]]

''N'' = number of tokens;

|V| = size of vocabulary (i.e. number of types);

''K'', ''b'' — free parameters, <math> K ∈ [10; 100]; b ∈ [0.4; 0.6] </math>

== Why tokenization is difficult? ==

*Easy example: "Good muffins cost $3.88 in New York. Please buy me two of them. Thanks."
** is \." a token?
** is $3.88 a single token?
** is \New York" a single token?
*Real data may contain noise in it: code, markup, URLs, faulty punctuation
* Real data contains misspellings: "an dthen she aksed"
*Period "." does not always mean the end of sentence: m.p.h., PhD.

Nevertheless tokenization is important for all other text processing steps.
There are rule-based and machine learning-based approaches to development of tokenizers.

== Rule-based tokenization ==

For example, define a token as a sequence of upper and lower case letters: A-Za-z. Reqular expression is a nice tool for programming such rules.

===RE in Python===

<code>
In[1]: import re

In[2]: prog = re.compile('[A-Za-z]+')

In[3]: prog.findall("Words, words, words.")

Out[1]: ['Words', 'words', 'words']
</code>

== Sentence segmentation ==

What are the sentence boundaries?
* ?, ! are usually unambiguous
* Period "." is an issue
* Direct speech is also an issue: She said, "What time will you be home?" and I said, "I don't know!". Even worse in Russian!

Let us learn a classifier for sentence segmentation.

===Binary classifier ===

A binary classifier f : X ⇒ 0; 1 takes input data ''X'' (a set of sentences) and decides EndOfSentence (0) or NotEndOfSentence (1).

What can be the features for classification? I am a period, am I EndOfSentence?
* Lots of blanks after me?
* Lots of lower case letters and ? or ! after me?
* Do I belong to abbreviation?
* etc.

We need a lot of hand-markup.

== Natural Language Toolkit (NLTK) ==

Do we need to program this?
No! There is Natural Language Toolkit (NLTK) for everything.

'''NLTK tokenizers'''
<code>
In[1]: from nltk.tokenize import RegexpTokenizer,
wordpunct tokenize

In[2]: s = 'Good muffins cost $3.88 in New York. Please
buy me two of them. Thanks.'

In[3]: tokenizer = RegexpTokenizer('\w+ | \$ [\d \.]+ | S \+')

In[4]: tokenizer.tokenize(s)

In[5]: wordpunct tokenize(s)
</code>

=== Learning to tokenize ===

nltk.tokenize.punkt is a tool for learning to tokenize from your data. It includes pre-trained Punkt tokenizer for English.

==== Punkt tokenizer ====
<code>
In[1]: import nltk.data

In[2]: sent detector = nltk.data.load('tokenizers/punkt/english.pickle')

In[3]: sent detector.tokenize(s)

</code>

== Exercise 1.1 Word counts ==

Input: Alice in Wonderland (alice.txt) or your text

Output 1: number of tokens

Output 2: number of types

Use nltk.FreqDist() to count types. nltk.FreqDist() is a frequency
dictionary: [key, frequency(key)].

== Lemmatization (Normalization) ==

Each word has a base form:
* has, had, have ⇒ have
* cats, cat, cat's ⇒ cat
* Windows ⇒ window or Windows?

=== Lemmatization [Jurafsky, Martin, 1999] ===
Lemmatization (or normalization) is used to reduce in ections or variant forms to base forms. A dictionary with headwords is required.

=== Lemmatization ===

<code>

In[1]: from nltk.stem import WordNetLemmatizer

In[2]: lemmatizer = WordNetLemmatizer()

In[3]: lemmatizer.lemmatize(t)

</code>

== Stemming ==

A word is built with morphems: ''word = stem + affixes''. Sometimes we do not need affixes.

translate, translation, translator ⇒ translat

=== Stemming [Jurafsky, Martin, 1999] ===

Reduce terms to their stems in information retrieval and text classification. Porter's algorithm is the most common English stemmer.

=== Stemming ===

<code>
In[1]: from nltk.stem.porter import PorterStemmer

In[2]: stemmer = PorterStemmer()

In[3]: stemmer.stem(t)
</code>

== Exercise 1.2 Word counts (continued) ==

Input: Alice in Wonderland (alice.txt) or your text

Output 1: 20 most common lemmata

Output 2: 20 most common stems

Use FreqDist() to count lemmata and stems. Use FreqDist().most common() to find most common lemmata and stems.

== Exercise 1.3 Do we need all words? ==

Stopword is a not meaningful word: prepositions, adjunctions, pronouns, articles, etc.

'''Stopwords'''
<code>

In[1]: from nltk.corpus import stopwords

In[2]: print stopwords.words('english')

</code>

'''Exercise 1.3'''

Input: Alice in Wonderland (alice.txt) or your text

Output 1: 20 most common lemmata without stop words

Use not in operator to exclude not stopwords in a cycle.

Lecture 8. Suffix trees for NLP

2015-08-31T21:24:35Z

Polidson: /* Implementation */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t 1 t 2 t 3 ) = p(t 1 )p(t 2 )p(t 3 )

Bigram model: p(t 1 t 2 t 3 ) = p(t 1 |BOS)p(t 2 |t 1 )p(t 3 |t 2 )p(EOS|t 3 )

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|слева]]
[[Файл:L8 6.jpg|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

AST construction and scoring in linear time and space using suffix arrays is developed by Mikhail Dubov. Take a look at his library for Python at GitHub: [https://github.com/msdubov/AST-text-analysis]. By the way, there is a huge theory about suffix trees and string algorithms I did not talk today about.

Lecture 8. Suffix trees for NLP

2015-08-31T21:23:42Z

Polidson: /* Profound filtering */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t 1 t 2 t 3 ) = p(t 1 )p(t 2 )p(t 3 )

Bigram model: p(t 1 t 2 t 3 ) = p(t 1 |BOS)p(t 2 |t 1 )p(t 3 |t 2 )p(EOS|t 3 )

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|слева]]
[[Файл:L8 6.jpg|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'

Pro-***-t'

Vy-***-t'

Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

Lecture 8. Suffix trees for NLP

2015-08-31T21:23:30Z

Polidson: /* Profound filtering */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t 1 t 2 t 3 ) = p(t 1 )p(t 2 )p(t 3 )

Bigram model: p(t 1 t 2 t 3 ) = p(t 1 |BOS)p(t 2 |t 1 )p(t 3 |t 2 )p(EOS|t 3 )

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|слева]]
[[Файл:L8 6.jpg|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

Za-***-t'
Pro-***-t'
Vy-***-t'
Na-***-t'

There are dictionaries of *** , but new words appear. And we have new policy of using profanity in the Web. Also stemming fails since it does not strip preffixes.

'''Idea''': Get a text from the web. Construct an AST from it and index.
Score *** to it. Find profound words.
Chernyak,

== Implementation ==

Lecture 8. Suffix trees for NLP

2015-08-31T21:22:39Z

Polidson: /* Reference graph */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t 1 t 2 t 3 ) = p(t 1 )p(t 2 )p(t 3 )

Bigram model: p(t 1 t 2 t 3 ) = p(t 1 |BOS)p(t 2 |t 1 )p(t 3 |t 2 )p(EOS|t 3 )

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|слева]]
[[Файл:L8 6.jpg|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

== Implementation ==

Lecture 8. Suffix trees for NLP

2015-08-31T21:22:12Z

Polidson: /* Reference graph */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t 1 t 2 t 3 ) = p(t 1 )p(t 2 )p(t 3 )

Bigram model: p(t 1 t 2 t 3 ) = p(t 1 |BOS)p(t 2 |t 1 )p(t 3 |t 2 )p(EOS|t 3 )

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|слева]]
[[Файл:L8 6.jpg|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

[[Файл:L8 14.jpg|слева]]

 
Reference graph is a graph of association rules. Not interesting itself, but:
* Dynamics
* Link analysis
* Visualization with different options
* Data: Russian newspapers
* Nodes: Key words and phrases
* Edges: A ⇒ B: the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text Features: Easy extension to temporal case and possibility of well developed graph analysis methods

Reference graphs can be used as a tool of information discovery and search and as a tool for temporal analysis.

[[Файл:L8 15.jpg|слева]]

 

== Profound filtering ==

== Implementation ==

Файл:L8 15.jpg

2015-08-31T21:17:03Z

Polidson: NLP: L8

NLP: L8

Lecture 8. Suffix trees for NLP

2015-08-31T21:15:40Z

Polidson: /* Annotated suffix tree construction */

== Text (collection) representation model ==

=== Vector Space Models ===

Vector Space Models, VSM [Salton, Wong, Yang, 1975] : every text is a vector in a space of terms. Usually is used along with cosine similarity
measure.

Pro:
* Makes linear algebra operation and thus machine learning applicable
* Is simple and based on human intuition

Contra:
* The more the words are there in the the text, the higher is the cosinesimilarity
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Information retrieval
* Topic, genre and maybe sentiment classification
* Extractive summarization
* Spam filtering

=== Generalized Vector Space Models ===

Generalized Vector Space Models, GVSM [Wong, Ziarko, Wong, 1985]: introduces a term to term correlation in the VSM.

Pro:
* Is still easy
* Synonyms or near synonyms are introduced into the model
* Term to term correlation may be computed in several ways: co-occurrences in the collection under consideration, co-occurrences in a large corpus, thesaurus-based relations

Contra:
* A lot of computations: if jVj = n (the number of terms), there are 2ndimensions in the GVSM
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications: mainly information retrieval

=== Vector Space Model of Semantics ===

Vector Space Model of Semantics [Turney, Pantel, 2010]: terms are vector in the space of contexts (usually, also terms).

Pro:
* Is still easy
* Allows to find semantically similar words
* Very loved by scientific community

Contra:
* Word order is lost
* Need some additional hacks to use bigrams and ngrams as terms

Applications:
* Word similarity detection, clustering, classification
* Automatic thesaurus generation
* Word sense disambiguation
* Context-sensitive spelling correction
* Textual advertising

=== Language Model [Ponte, Croft, 1998] ===

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Unigram model: p(t 1 t 2 t 3 ) = p(t 1 )p(t 2 )p(t 3 )

Bigram model: p(t 1 t 2 t 3 ) = p(t 1 |BOS)p(t 2 |t 1 )p(t 3 |t 2 )p(EOS|t 3 )

[[Файл:L8 1.jpg|слева]]

 

Language Model [Ponte, Croft, 1998]: a probability distribution over sequences of words.

Pro:
* The word order is not lost
* Makes Markov chain theory applicable

Contra:
* The problem of unseen words
* How to choose n?
* Long relations between words or sentences (for example, anaphora) are lost

Applications:
* Information retrieval
* Text generation
* Abstractive summarization
* Speech recognition
* Speech generation

To sum up:

* VSM-like models: no word order, algebraic structures, classification of any kind, stemming and lemmatization for dimension reduction

* LM-like models: partially word order, Markov chains, generation of text and speech

* What if new word appears? What if there is a typo? What if stemming is not always correct? Use edit distance on words or stems or use symbol ngrams instead as terms or ...

== Suffix tree ==

=== Annotated suffix tree (AST) ===

The suffix tree is a data structure used for storing of and searching for strings of characters and their fragments.

Suffix trees in NLP:

* Text clustering [Zamir, Etzioni,1998]
* Language model for MT [Kennington et al., 2012] and IR [Huang, Powers, 2008]
* Feature generation for text classification [Zhang, Lee, 2006]

[[Файл:L8 2.jpg|Suffix tree: Example from [Gus�led, 1998]]]

== Annotated suffix tree ==

Annotated suffix tree (AST) [Pampapathi, Mirkin, Levene, 2006]:

An annotated suffix tree is a data structure used for computing and storing all fragments of the text and their frequencies. It is a rooted tree in which:
* Every node corresponds to one character
* Every node is labeled by the frequency of the text fragment encoded by the path from the root to the node.

[[Файл:L8 3.jpg]]

=== Annotated suffix tree construction ===

"MINING" has 6 suffixes: "MINING", "INING", "NING", "ING", "NG", "G"

'''Naive algorithm for AST construction'''

* Start with "MINING", add it as a chain of nodes with frequencies equal to unity. Add "INING" and "NING" the same way.
* When adding "ING", note that there is already a path from root that encodes / reads "I N". Increase the frequencies in this path by 1. Add "G" to the end of the path. When adding "NG", note "G" and react in the same way.
* Add "G" as a single node with frequency equal to unity.

[[Файл:L8 4.jpg]]

Using Naive algorithm we add the second string "DINING". Complexity: both O(n^2) time and space, where n is the number of input strings. Frequency of the root node is the sum of the first level node frequencies.

=== Annotated suffix tree scoring ===

[[Файл:L8 5.jpg|слева]]
[[Файл:L8 6.jpg|слева]]

 

=== Applications of AST ===

* Spam filtering [Pampapathi, Mirkin, Levene, 2006]
* Text categorization and clustering [Chernyak, Chugunova, Mirkin, 2010]
* Text summarization [Yakovlev, Chernyak, 2014]
* Taxonomy refinement [Chernyak, Mirkin, 2013]
* German compound splitting [Provatorova, Chernyak, 201x]
* AST as a string kernel [Dubov, 201x]
* Reference graph construction [Dubov, Chernyak, Mirkin, 201x]
* Profound filtering
* Duplicate detection

== Spam filtering ==

# Construct two huge ASTs: spam AST and ham AST
# Introduce match permutation (swaping symbols in the match) to SCORE
# Test versus Naive Bayes classifier on a standart datasets (The Ling-Spam corpus, Spam Assassin public corpus, The BBKSpam04 corpus)
# Beat it (in terms of spam precision and spam recall)!

== Unsupervised text categorization ==

'''Input 1''': 5k+ abstracts from ACM journal and ACM CCS (English). Every abstract is annotated with some of the ACM CCS topics.

'''Input 2''': 100k+ web page description from Yandex Categories (YaCa) and Yandex Categories (Russian). Every description belongs to a YaCa categories.

'''Note''': We know right answers! We try to reproduce them computationally. Pure scientific joy. No business applications.

'''Task''': different models of text collection representation, relevance measures and AST ''scoring'' ⇒ ''relevance()'' Score relevance(taxonomy topic) and ''relevance(YaCa category)'' to abstracts and descriptions. Score the taxonomy topics and YaCa categories in descending order. Calculate how many right answers are there. Use ''nDCG'' and ''MAP'' to evaluate the '''quality'''.

== Text summarization ==

'''TextRank''' is an efficient algorithm for extractive text summarization. Let us construct graph, where nodes stand for single sentences and edges connect sequential sentences. Than we can use the VSM and cosine similarity to compute the similarity between sentences and run PageRank
to get the most important sentences. Let us replace the cosine similarity with scoring common AST.

A '''common AST''' of two ASTs is a tree, that consists of all chains of nodes that coincide in the ASTs. The frequencies are computed as average. Scoring the common AST (i.e.scoring all the paths in the tree according to ''SCORE'') suits as sentence similarity measure.

'''Input 1''': DUC 2004 (a text collection for text summarization)

'''Input 2''': home made collection of gazeta.ru papers.

'''Quality measures''': precision

[[Файл:L8 7.jpg]]

 

== Taxonomy refinement ==

No taxonomy of mathematics in Russian! Let us construct one.
Still we have something in educational standards. We can use Wikipedia to refine it.

[[Файл:L8 8.jpg|слева]]
[[Файл:L8 9.jpg|слева]]
[[Файл:L8 10.jpg|слева|The refining scheme. Initial taxonomy topics are in rectangles, the Wikipedia categories and subcategories are in rounded rectangles, the Wikipedia articles are in the ovals, and the leaf descriptors are in the clouds.]]

 
# Specify the domain of taxonomy to be refined and set the frame of taxonomy manually.
# Download, from the Wikipedia, the category tree and articles from the domain under consideration.
# Clean the category subtree of irrelevant articles.
# Clean the category subtree of irrelevant subcategories.
# Assign the remaining Wikipedia categories to the taxonomy topics.
# Form the intermediate layers of the taxonomy
# Use Wikipedia articles in each of the added category nodes as its leaves.
# Extract relevant keywords from Wikipedia articles and use them as leaf descriptors.

[[Файл:L8 11.jpg|слева]]
[[Файл:L8 12.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]
[[Файл:L8 13.jpg|слева|The fragment of refined PTMS taxonomy. Lower layers are shown.]]

 

== German compound splitting ==

Liebeskummer — heart-sickness — Lieb-es-kumm-er
Bilderrahmen — picture frame — Bild-er-rahm-en
Schmerzensgeld — compensation — Schmerz-ens-geld
Gedankenfreiheit — freedom of thought — Gedank-en-frei-heit
Schweineeisch — pork — Schwein-e-eisch
Trinkgeld — tip — Trink-geld

To split a compound:
* write complex linguistics rules
* use machine learning algorithms
* (hypothesis) construct an AST from a list of simple words, than score compounds to this tree

It is a problem to find a list of German words that does not contain compounds.

== Reference graph ==

== Profound filtering ==

== Implementation ==

Файл:L8 14.jpg

2015-08-31T21:11:03Z

Polidson: NLP: L8

NLP: L8