Introduction to Text Mining and NLP

Contents

• Introduction and overview
• 0. Review: vector spaces and probabilities
• 1. The text processing pipeline
• 2. Bag of words, TF-IDF and BM25
• 3. Text classification
• 4. Word embeddings
• 5. Topic models
• 6. Sequences and relations: NER, HMM, CRF, relation extraction
• 7. Transformers for NLP
• 8. Industrial text mining
• 9. Research at DaSciM (Vazirgiannis, Buscaldi)
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: an engineer who has already scraped a CSV of reviews / tickets and fitted a scikit-learn classifier — and wants to know why BM25 beats TF-IDF, or why a BERT fine-tune blows up the vocab. Empirical first: F1 dropping after aggressive stemming; a tokenizer that multiplies FR tokens vs EN — then we name BoW, embeddings, transformers.

From tokenization to industrial text mining (TF-IDF/BM25, embeddings, topics, NER, fine-tuning). Mandatory P2 foundation for the M2 module Large Language Models.

What you will be able to do

• Build a complete text processing pipeline, from raw corpus to usable features.
• Represent documents with bag of words, TF-IDF and BM25, build a search engine on these foundations (inverted index) and evaluate its rankings (MAP, nDCG).
• Train and interpret word embeddings.
• Infer latent topics in a corpus with topic models.
• Classify texts, from Naive Bayes to transformer fine-tuning.
• Label sequences (named entity recognition) with HMMs and CRFs, and extract relations between entities as knowledge-graph triples.
• Fine-tune a transformer for a given NLP task, and assemble a minimal retrieval-augmented generation (RAG) pipeline.
• Build content-based and collaborative recommenders (matrix factorization), and use text features for click prediction and social media monitoring.
• Conduct a text mining project in an industrial context, from data to production deployment.

Official objectives and syllabus (2026-2027 catalog)

The official 2026–2027 sheet (scheduled session “Introduction à la Fouille de Textes et au Traitement Automatique des Langues (NLP)”, period X-3A-P2, from 04/01/2027 to 19/03/2027, taught in English) gives a short description and nothing else: no learning objectives, no prerequisites, no assessment modality and no programme are displayed.

The description observes that text is everywhere, and that text mining, natural language processing, information retrieval and recommendation systems matter greatly in applications and are in high demand at the large web companies and across industry; it singles out a strong current industrial interest in search, web marketing and advertising, social network analysis and recommendation systems (the sentence is truncated on the sheet), a large market that has made NLP a central and visible research field.

Volume: 18 h of lectures + 18 h of small classes. Since no syllabus is published, the table pairs each field and application named by the description with the sections that teach it.

Our extensions, beyond the official description: the refresher chapter 0 (vector spaces and probabilities) and chapter 9 (the research work of Vazirgiannis and Buscaldi, self-study).

Where this course fits in the program

Mandatory module of period 2 of M1 (36 h: 18 h of lectures + 18 h of small classes, 4.5 ECTS), of which Michalis Vazirgiannis is the official head, with Davide Buscaldi in the teaching team. Official prerequisites: not displayed on the 2026–2027 sheet. It provides the vocabulary and reflexes without which the M2 large language models would remain black boxes.

• Prerequisites — Machine Learning (Naive Bayes for classification, the EM algorithm reused by topic models), and one Deep Learning course: Deep Learning in Period 1, or Deep Learning (P2) taken in parallel with this course. Students on the second route meet attention here first: section 7.1 states the transformer block in a self-contained page.
• Downstream modules — it directly prepares Large Language Models (M2), its natural extension; the same processing pipeline applied to speech is found in Speech Technology for Conversational AI (M2); and in the same period, the module Graph Machine and Deep Learning for Generative AI crosses over with this material (a document can become a graph of words, and its embeddings join node embeddings).

Course outline

• Review: vector spaces and probabilities — the two lenses of the course: representing a document as a vector, reasoning in terms of laws and likelihood.
• The text processing pipeline — segmentation, cleaning, normalization, subword tokenization and the first language model (n-grams with Kneser–Ney smoothing): the decisive craft before any model.
• Bag of words, TF-IDF and BM25 — the classical representations, the scoring function that powers information retrieval, the inverted index and ranking metrics.
• Text classification — from Naive Bayes to neural models: the reference task of NLP.
• Word embeddings — moving from counting to prediction: word vectors that carry meaning.
• Topic models — discovering the latent topics of a corpus, with EM as the engine.
• Sequences and relations: NER, HMM, CRF, relation extraction — labeling named entities with structured sequential models, training them, and linking entities into knowledge-graph triples.
• Transformers for NLP — the transformer block, pretrained families, fine-tuning, sentence embeddings, and a minimal RAG pipeline.
• Industrial text mining — summaries, keywords, deduplication, a ticket case study, recommendation systems, web advertising and social media analysis; volumes, annotation budgets, deployment and monitoring.
• Research at DaSciM (Vazirgiannis, Buscaldi) — a tour of the research work of Vazirgiannis and Buscaldi (self-study).
• Exercises, Projects and assessment and References — systematic training, project subjects with an exam and a rubric (proposals), and sources to go further.

Session plan

36 h in class = 12 sessions of 3 h. The volume is the one of the SynapseS 2026–2027 sheet, which displays 18 h of lectures + 18 h of small classes (it leaves its in-person total line empty); the sheet publishes no session-by-session programme, so the split below is our proposal for covering these notes in that time, each session pairing a lecture half with a small-class half. Level 1 = foundations (reviews, definitions, first worked examples), 2 = core methods and their derivations; the level never goes down from one session to the next.

Read ahead for the Year 1 team project (one repository shared with Graph ML and Reinforcement Learning, see the box in 8.6): section 8.5 by project week 1, because subject Y1.3 needs it before session 11 teaches it; sections 6.4 and 7.4 as soon as the project starts if your subject is Y1.1.

Self-study, outside the 36 h (about 3 h in total): ch. 9 Research at DaSciM — graph-of-words and TW-IDF, degeneracy, word sense induction, legal retrieval, knowledge graphs (≈ 3 h).

How to study this module

• Work through the review section: dot products and conditional probabilities are used explicitly in every subsequent chapter.
• Once, build a bag of words and a TF-IDF score yourself on a mini-corpus: everything that follows is understood by contrast with this baseline.
• Before each model, write down on paper what it assumes (independence, word order, latency): this is what enables practical choices.
• Hand-label a few sentences for a NER task: you will measure the cost of annotation, the central constraint of industrial NLP.
• Read section 7.1 alongside the attention chapter of Deep Learning (ch. 6) or the transformer-block section of Deep Learning (P2) (ch. 0): the two reinforce each other.
• Redo the exercises of each section before moving on to the next; they prepare the graded assignments and the bridge to the LLMs module.

0. Review: vector spaces and probabilities

This course reads text through two lenses: as vectors (a document is a point, similarity is an angle) and as random sequences (a document is drawn from a distribution, and learning means maximizing a likelihood). The review below recalls the tools of both lenses and points to the chapter where each one is used.

1. The text processing pipeline

Concrete scene: 50,000 support tickets in French and English. A first pipeline lowercases the text, splits it into “words” with a regular expression and feeds TF-IDF features to a logistic regression: macro-F1 0.62. Without NFKC normalization, two encodings of “café” count as two different types; with aggressive stemming, “connection” and “connector” merge and the macro-F1 drops to 0.51. This chapter fixes the pipeline before the model.

1.1. Unicode normalization and “clean” text

• Case: lower() merges “Polytechnique” and “polytechnique” but also the acronym and the common word; in French, keep the accents in lowercase (“élève” ≠ “eleve”);
• Sentence segmentation: rules (punctuation + capital letter) or learning (Punkt, Kiss & Strunk 2006); real pitfalls: “M.”, “etc.”, German abbreviations (“z. B.”), period before a closing quote. Bad segmentation wrecks ch. 8 (extractive summarization: the sentence is the unit being selected);
• Stemming vs lemmatization: the stemmer (Porter, Snowball) cuts off suffixes by rules — fast, crude, suited to information retrieval; the lemmatizer uses a dictionary and morphology (“sont” → “être”) — slower, better for fine-grained analysis. In industry: stemmer for search, lemmatizer for analysis.

1.2. Subword tokenization: BPE, WordPiece, Unigram, SentencePiece

import re
from collections import Counter

# --- Toy BPE: learning merges on the mini-corpus of example 1.4 ---
words = {"b a s e": 5, "b a s e s": 4, "b a s s e": 3, "b a s i q u e": 2}
merges = []
for _ in range(8):
    pairs = Counter()
    for w, f in words.items():
        sym = w.split()
        for pair in zip(sym, sym[1:]):
            pairs[pair] += f
    if not pairs:
        break
    best = max(pairs, key=pairs.get)          # most frequent adjacent pair
    merges.append(best)
    big = " ".join(best)
    words = {re.sub(r"(?<!\S)" + re.escape(big) + r"(?!\S)", "".join(best), w): f
             for w, f in words.items()}
print("merges:", merges[:6])
# tokenize a new word = replay the merges in the learned order
def encode(word, merges):
    sym = list(word)
    for a, b in merges:
        i, out = 0, []
        while i < len(sym):
            if i + 1 < len(sym) and (sym[i], sym[i+1]) == (a, b):
                out.append(a + b); i += 2
            else:
                out.append(sym[i]); i += 1
        sym = out
    return sym
print(encode("basiste", merges))

1.3. Stopwords, n-grams, collocations and n-gram language models

• Stopwords: to be removed for classical text mining (they saturate the BoW); to be kept for transformers — negation (“ne…pas”) and syntax matter. The decision must be justified by the task, not by habit;
• N-grams: sequences of n tokens; “New York” (bigram) ≠ “New” + “York”; in classification, moving from unigrams to bigrams captures compositional polarity (“pas cher”); cost: the vocabulary explodes (potentially |\mathcal{V}|^n) — hence ngram_range=(1,2) and min_df in the code of ch. 3;
• Collocations: bigrams whose frequency exceeds what independence predicts, measured by mutual information \mathrm{PMI}(x,y) = \log \frac{P(x,y)}{P(x)P(y)} — a criterion reused as-is in ch. 2 to justify IDF, and in ch. 5 for topic coherence.

Counting n-grams also gives the first language model: a probability for the next word given the previous ones. It is the ancestor of the LLMs of M2, it is still the language model of classical speech recognizers (Speech Technology, ch. 1), and its central difficulty — how much probability to leave for what was never seen — never goes away.

2. Bag of words, TF-IDF and BM25

Most models cannot read strings: they need vectors. This chapter turns each document into a vector of word counts, reweights the counts so that informative words dominate (TF-IDF), and derives BM25, the scoring function that still powers search engines.

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity
from rank_bm25 import BM25Okapi

corpus = ["graphe de connaissances entreprise",
          "réseau de neurones profond",
          "graphe neuronal et réseau d'entreprise"]
X = TfidfVectorizer().fit_transform(corpus)      # sparse matrix (3, vocabulary size), L2-normalized
print(cosine_similarity(X).round(2))             # docs 0 and 2 are the closest

toks = [d.split() for d in corpus]
bm25 = BM25Okapi(toks)
print(bm25.get_scores("réseau entreprise".split()))  # BM25 score per document

2.1. Search engines: inverted index and ranking evaluation

Information retrieval, named first among the applications of the official description, needs two more ingredients than a scoring function: a data structure that avoids scoring every document, and a way to measure whether the ranking is good.

3. Text classification

Deciding which category a document belongs to — spam or not, which team should handle a ticket, positive or negative review — is the most common NLP task in industry. This chapter builds the two reference classifiers on the bag-of-words vectors of ch. 2, Naive Bayes and regularized logistic regression, together with the evaluation practice that goes with them.

• Calibration: when the probability is consumed (business thresholds, ticket routing), recalibrate — Platt (logistic regression on the scores) or isotonic; diagnostic: reliability curve (predicted vs observed reliability);
• Imbalanced classes: class weighting (class_weight="balanced"), optimal threshold on the PR curve (not ROC); metric: macro-F1 (per-class average — every class counts equally) rather than accuracy (which flatters the majority); per-intent confusion matrix for chatbots;
• Networks: sentence CNNs (Kim, 2014) and BiLSTMs over the word embeddings of ch. 4; then transformer fine-tuning (ch. 7). Empirical learning curves: linear+TF-IDF wins below ~10²-10³ examples, the transformer above;
• Zero-shot / few-shot with an LLM: zero labeled examples, or k examples in the prompt; the mechanism is stated in the box of section 7.2 and studied in depth in M2 LLMs (ch. 4.0, prompting and in-context learning). An excellent exploratory starting point and a help for labeling (active learning), rarely the final solution in production (cost, latency, confidentiality).

from sklearn.pipeline import make_pipeline
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.linear_model import LogisticRegression
from sklearn.naive_bayes import MultinomialNB
from sklearn.datasets import fetch_20newsgroups
from sklearn.metrics import f1_score, classification_report

train = fetch_20newsgroups(subset="train", remove=("headers","footers","quotes"))
test  = fetch_20newsgroups(subset="test",  remove=("headers","footers","quotes"))

pipe = make_pipeline(TfidfVectorizer(min_df=3, ngram_range=(1,2), sublinear_tf=True),
                     LogisticRegression(C=10, max_iter=2000, class_weight="balanced"))
pipe.fit(train.data, train.target)
pred = pipe.predict(test.data)
print("macro-F1:", f1_score(test.target, pred, average="macro"))
print(classification_report(test.target, pred, labels=[0, 1, 2],   # first 3 of the 20 classes
                            target_names=test.target_names[:3]))

4. Word embeddings

In a bag of words, “car” and “automobile” are as different as “car” and “banana”: every word is its own orthogonal axis. Word embeddings replace these axes by dense vectors of a few hundred dimensions, learned from the contexts in which words appear, so that words used in similar contexts get similar vectors.

4.1. Evaluating embeddings

• Lexical similarity: rate word pairs (SimLex-999, WordSim-353), correlate with the cosine — metric: Spearman correlation;
• Analogies: precision@1 on z_b - z_a + z_c \approx z_d excluding \{a,b,c\} from the search (the Mikolov protocol): “king − man + woman ≈ queen”. Caution: analogy accuracy is sensitive to word frequency;
• Downstream: the real evaluation is the final task (ch. 3).

import gensim.downloader as api
wv = api.load("glove-wiki-gigaword-100")        # pretrained embeddings

def analogy(a, b, c):                            # a - b + c ≈ ?
    v = wv[a] - wv[b] + wv[c]
    return wv.most_similar(v, topn=3)
print(analogy("king", "man", "woman"))

# quick evaluation: do the neighbors share the context?
for w in ["graph", "court", "ticket"]:
    print(w, "->", [x for x, _ in wv.most_similar(w, topn=3)])

5. Topic models

A corpus of thousands of documents is too large to read, but it is usually about a few dozen themes. Topic models recover these themes without any labels: each topic is a probability distribution over words, and each document a mixture of topics.

• After LDA: BERTopic (embeddings + clustering + c-TF-IDF) for topics on contemporary corpora — consistent with the “embeddings, ch. 4” pipeline; for the industrial use of topics: monitoring, compliance, e-discovery, detection of emerging themes;
• Word Sense Induction: applying clustering to all the occurrences of a single word (BERT contexts) reveals its senses — the joint Vazirgiannis–Buscaldi paper of ch. 9 does exactly that, with mutual information maximization;
• Topic models on graphs (TopSBM, Gerlach et al., 2018): the idea extended to networks (see the Graph ML module).

6. Sequences and relations: NER, HMM, CRF, relation extraction

Some tasks need a label for every word rather than for the whole document: finding the names of persons and companies in a sentence, or the grammatical category of each word. Neighboring labels depend on each other (an entity that begins must continue), so this chapter uses models of the whole label sequence: hidden Markov models, then conditional random fields. It ends by linking the entities it finds into relations: the triples of a knowledge graph.

6.1. Hidden Markov models

# Toy Viterbi: 2-state POS tagging (N noun, V verb), 4-word vocabulary
import numpy as np
W = ["le", "chat", "mange", "souris"]
p_z0  = np.array([.9, .1])                      # P(z1)
A     = np.array([[.8,.2],[.3,.7]])             # P(z_t | z_{t-1})  rows=prev
B     = np.array([[.6,.3,.02,.08],
                  [.0,.02,.9,.08]])             # P(w | z)  columns=words
seq   = [0,1,2,3]                               # "le chat mange souris"

delta = B[:, seq[0]] * p_z0                     # initialization
back  = []
for w in seq[1:]:
    m = delta[:, None] * A * B[:, w][None, :]   # (prev, cur)
    back.append(m.argmax(0)); delta = m.max(0)
z = [delta.argmax()]
for bp in reversed(back): z.append(bp[z[-1]])
print("labels:", [["N","V"][i] for i in reversed(z)])

6.2. Conditional random fields

6.3. Decoding and evaluating entities

6.4. Relation extraction

NER finds the entities of a text; relation extraction decides which relation, if any, links two of them. The output is a set of triples (head, relation, tail): the edges of a knowledge graph, which the GraphRAG of the Graph ML module (ch. 10) then searches.

• Pipeline vs joint. A pipeline runs NER, then classifies every ordered pair of mentions of a sentence (m(m-1) candidates for m mentions). It is modular and easy to debug, but NER errors propagate: a missed entity is a missed triple.

  A joint model predicts entities and relations together — by table filling, or by a sequence-to-sequence model that generates the linearized triples (REBEL, Huguet Cabot & Navigli, 2021). It removes the propagation but is harder to train and to audit.

• Entity markers on an encoder (Baldini Soares et al., 2019; Zhong & Chen, 2021). Wrap the two mentions in marker tokens, “[E1] Marie Curie [/E1] was born in [E2] Warsaw [/E2]”, encode the sentence with a BERT-type model (ch. 7), concatenate the output vectors at the two opening markers and classify: p(r\mid s,e_1,e_2)=\mathrm{softmax}\big(W\,[h_{[E1]};\,h_{[E2]}]+b\big). Typed markers such as [E1:PER] add the NER type for free. Training follows the fine-tuning Protocol 7.1.

• Distant supervision (Mintz et al., 2009): labels without annotators. Align a knowledge base such as Wikidata with the text, and label every sentence that mentions both entities of a known triple with that relation.

  The labels are noisy in both directions: “Obama visited Hawaii” is labeled place of birth (a false positive), and true facts missing from the base become false negatives. Multi-instance learning (Riedel et al., 2010) only assumes that at least one sentence of each bag expresses the relation. A small hand-checked test set remains necessary.

• Few-shot LLM extraction with a JSON schema. Prompt an instruction-tuned LLM with the relation inventory, two to five annotated examples and the passage (the mechanism of the few-shot box in section 7.2), and require an answer that validates against a schema:

  {"type": "object", "required": ["triples"],
   "properties": {"triples": {"type": "array", "items": {
     "type": "object", "required": ["head", "relation", "tail", "evidence"],
     "properties": {"head": {"type": "string"}, "tail": {"type": "string"},
                    "relation": {"enum": ["place of birth", "director", "employer"]},
                    "evidence": {"type": "string"}}}}}}

  Validate every answer (re-ask on invalid JSON or an unknown relation) and drop the triples whose head or tail does not occur in the passage, a cheap guard against invented entities. No training data is needed, but every passage costs tokens; on a fixed schema with a few thousand labeled examples, a fine-tuned extractor is usually more accurate and far cheaper.

7. Transformers for NLP

The models of the previous chapters give each word one vector whatever its context, and read a sentence through a short window at best. Transformers compute for each token a representation that depends on the whole sentence; pretrained once on a large corpus, they are then adapted to each task with little labeled data. This chapter states the architecture in one page, then applies it to text: pretrained families, fine-tuning, sentence embeddings and a first retrieval-augmented generator.

7.1. The transformer block in one page

7.2. Pretrained families: BERT, GPT, T5

7.3. Fine-tuning and sentence embeddings

import torch
from torch.utils.data import DataLoader
from datasets import load_dataset
from transformers import (AutoTokenizer, AutoModelForSequenceClassification,
                          DataCollatorWithPadding, get_linear_schedule_with_warmup)
from sklearn.metrics import f1_score

name = "distilbert-base-uncased"                         # small encoder, 66M parameters
tok = AutoTokenizer.from_pretrained(name)
ds = load_dataset("nyu-mll/glue", "sst2")                # columns: sentence, label, idx
ds = ds.map(lambda b: tok(b["sentence"], truncation=True, max_length=128),
            batched=True, remove_columns=["sentence", "idx"])
collate = DataCollatorWithPadding(tok)                   # pads per batch, renames label -> labels
train = DataLoader(ds["train"], batch_size=32, shuffle=True, collate_fn=collate)
dev = DataLoader(ds["validation"], batch_size=64, collate_fn=collate)

torch.manual_seed(0)
device = "cuda" if torch.cuda.is_available() else "cpu"
model = AutoModelForSequenceClassification.from_pretrained(name, num_labels=2).to(device)
epochs = 3
opt = torch.optim.AdamW(model.parameters(), lr=2e-5, weight_decay=0.01)
steps = epochs * len(train)
sched = get_linear_schedule_with_warmup(opt, int(0.1 * steps), steps)  # 10 % warmup, linear decay

def evaluate():
    model.eval(); ys, ps = [], []
    with torch.no_grad():
        for b in dev:
            b = {k: v.to(device) for k, v in b.items()}
            ps += model(**b).logits.argmax(-1).tolist(); ys += b["labels"].tolist()
    model.train()
    return f1_score(ys, ps, average="macro")

best = 0.0
for epoch in range(epochs):
    for b in train:
        b = {k: v.to(device) for k, v in b.items()}
        loss = model(**b).loss                           # cross-entropy of the head on [CLS]
        loss.backward()
        torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0)
        opt.step(); sched.step(); opt.zero_grad()
    f1 = evaluate()
    print(f"epoch {epoch}: dev macro-F1 {f1:.3f}")
    if f1 > best:                                        # keep the best epoch only
        best = f1; model.save_pretrained("best"); tok.save_pretrained("best")

from transformers import pipeline

classifier = pipeline("text-classification",
                      model="distilbert-base-uncased-finetuned-sst-2-english")
print(classifier("Graph RAG is a game changer for enterprise search."))

ner = pipeline("ner", aggregation_strategy="simple")
print(ner("Michalis Vazirgiannis teaches at Ecole Polytechnique."))

# sentence embeddings for RAG (cf. section 7.4 and M2 LLMs ch. 7)
from sentence_transformers import SentenceTransformer
enc = SentenceTransformer("paraphrase-multilingual-MiniLM-L12-v2")
print(enc.encode(["résumé automatique", "automatic summarization"]).shape)

7.4. A minimal RAG pipeline

A language model answers from what it memorized during pretraining: it does not know a company’s documents, and it can state wrong facts fluently. Retrieval-augmented generation (RAG; Lewis et al., 2020) first retrieves passages from a corpus, then asks the model to answer from them. This section builds the minimal version from pieces of this course: BM25 (ch. 2), Sentence-BERT (7.3) and the ranking metrics of section 2.1.

M2 LLMs (ch. 7) goes in depth (reranking, evaluation at scale). The GraphRAG of Graph ML (ch. 10) and the LLM agents of Reinforcement Learning (ch. 7) start from this pipeline.

• Sparse or dense? BM25 wins on rare exact strings — product codes, names, article numbers, the tickets of 8.4 — that a sentence encoder blurs. Dense retrieval wins on paraphrases and synonyms (“car” for “automobile”, ch. 4), and across languages with a multilingual encoder. Hybrid fusion is the safe default; measure before choosing.
• How many chunks? A larger k raises recall but lengthens the prompt (cost, latency), and models use the middle of a long context less well than its ends.

import numpy as np
from rank_bm25 import BM25Okapi
from sentence_transformers import SentenceTransformer

corpus = ["..."]                                         # list of document strings

def chunk(text, size=150, overlap=30):                  # windows of `size` words
    w = text.split()
    return [" ".join(w[i:i + size]) for i in range(0, max(len(w) - overlap, 1), size - overlap)]

chunks = [c for doc in corpus for c in chunk(doc)]
bm25 = BM25Okapi([c.lower().split() for c in chunks])  # sparse index (ch. 2)
enc = SentenceTransformer("paraphrase-multilingual-MiniLM-L12-v2")
E = enc.encode(chunks, normalize_embeddings=True)       # dense index (7.3)

def retrieve(q, k=5):
    sparse = np.argsort(-bm25.get_scores(q.lower().split()))[:k]
    dense = np.argsort(-(E @ enc.encode(q, normalize_embeddings=True)))[:k]
    fused = {}
    for ranking in (sparse, dense):                     # reciprocal rank fusion
        for r, i in enumerate(ranking):
            fused[int(i)] = fused.get(int(i), 0.0) + 1 / (60 + r + 1)
    return sorted(fused, key=fused.get, reverse=True)[:k]

def prompt(q, ids):
    passages = "\n".join(f"[{n + 1}] {chunks[i]}" for n, i in enumerate(ids))
    return ("Answer the question using only the passages below, and cite them as [n]. "
            "If they do not contain the answer, say so.\n\n"
            f"{passages}\n\nQuestion: {q}\nAnswer:")

def recall_at_k(ids, gold):                             # gold: set of supporting chunk ids
    return len(set(ids) & gold) / len(gold)

8. Industrial text mining

This chapter assembles the building blocks of ch. 1-7 into products: summaries, keywords, deduplication, ticket classification — the real workloads of NLP in industry, together with their engineering pitfalls.

8.1. TextRank: extractive summarization by PageRank

8.2. Keyword extraction: RAKE, YAKE, KeyBERT

• RAKE (Rose et al., 2010): split on stopwords/punctuation → candidate phrases; a word’s score = \deg(w)/\mathrm{freq}(w) (degree in the cooccurrence graph within the candidates) + bigram frequency; a phrase’s score = the sum of its words. Fast, no external corpus, sensitive to stopwords;
• YAKE (Campos et al., 2020): unsupervised statistical features per word — frequency, dispersion of positions (a keyword appears everywhere), case (a capital letter mid-sentence = signal), redundancy of variants (edit distance) — an aggregated score, with left/right windows for context; robust and multilingual;
• KeyBERT (Grootendorst, 2020): extract candidates (n-grams), embed them and the document with a sentence encoder (Sentence-BERT, section 7.3; word vectors in ch. 4), keep the ones closest to the document — and diversify with MMR: \mathrm{MMR}=\arg\max_{c\,\in\,C\setminus S}\ \Big[\lambda\cos(c,d)-(1-\lambda)\max_{s\in S}\cos(c,s)\Big], which adds to the set S the candidate that is relevant and not very redundant; the same “embeddings + MMR” pattern returns in RAG (M2, ch. 7).

8.3. Deduplication at scale: MinHash + LSH

8.4. Complete case: support ticket classification

• Question answering and RAG: retriever (BM25 — the direct descendant of ch. 2 — and/or dense; hybrid search) + generator, built in section 7.4 and deepened in M2 LLMs (ch. 7); the capstone exports triples to the graph version of it (Graph ML, ch. 10);
• Monitoring: stream → MinHash dedup → topic model (ch. 5) → keywords (8.2) → classification → alerts;
• French and multilingual: corpora, multilingual models (mBERT, XLM-R); legal/French = specific difficulties — JuriBERT (ch. 9) answers on the model side, Buscaldi’s research (ch. 9) on the information retrieval side.

8.5. Recommendation systems

The official description names recommendation systems next to retrieval as a major industrial use. A recommender is a search engine without a query: it ranks items for a user, and text is one of its two sources of signal — the other being the behaviour of other users.

The Year 1 project Y1.3 (cold-start news recommendation on the MIND dataset, end-of-year projects) builds its text tower on Definition 8.2 and on the hybrid of Model 8.3: read this section by project week 1.

8.6. Web advertising and social media analysis

The other two industrial markets named by the description — web marketing/advertising and social network analysis — are text problems at their core: matching queries to ads, and reading short, noisy posts at scale.

9. Research at DaSciM (Vazirgiannis, Buscaldi)

This module is backed by a laboratory (DaSciM, LIX, École Polytechnique — M. Vazirgiannis; LIPN, Sorbonne Paris Nord — D. Buscaldi): here is the actual research of the two instructors, each positioned with respect to the chapters of the course. A methodological lesson: every building block of the course (TF-IDF, clustering, graphs, embeddings) is a living research argument.

9.1. Michalis Vazirgiannis: text mining through graphs

• Graph-of-Word and TW-IDF — F. Rousseau & M. Vazirgiannis, Graph-of-word and TW-IDF: new approach to ad hoc IR, CIKM 2013 (doi); overview: Graph of Words: Boosting Text Mining Tasks with Graphs, WWW 2017 (doi).

  The idea: represent each document as a graph of words (nodes = terms, edges = cooccurrence within a window), and replace the tf(t,d) of TF-IDF (ch. 2) with the centrality of the term — the sum of the weights of its edges (weighted degree). The weight captures the local cohesion of the term in the discourse, not just its frequency; TW-IDF improves ad hoc retrieval on reference collections.

  Position: directly extends ch. 2 — “counting becomes a graph score”; it is also the gateway to the Graph ML module (motifs, communities, k-cores).

• Keywords by degeneracy — Main Core Retention on Graph-of-Words for Single-Document Keyword Extraction, ECIR 2015 (doi); Tixier, Malliaros & Vazirgiannis, A Graph Degeneracy-based Approach to Keyword Extraction, EMNLP 2016 (aclanthology). k-core decomposition of the graph-of-words: the main core (the maximal subgraph in which every word cooccurs with at least k neighbors) isolates the words that carry the document — an unsupervised, noise-robust method that rivals supervised approaches.

  Position: the “graph” competitor of RAKE/YAKE in ch. 8; GoWvis demo (ACL 2016, aclanthology); real-time version for conversations: EACL 2017 (aclanthology).

• Clustering — Giatsidis, Malliaros, Thilikos & Vazirgiannis, CoreCluster: A Degeneracy Based Graph Clustering Framework, AAAI 2014 (doi); Skianis, Rousseau & Vazirgiannis, Regularizing Text Categorization with Clusters of Words, EMNLP 2016 (aclanthology): we cluster the words (communities of the cooccurrence graph) and classify the documents on these clusters — a regularization in small dimension, interpretable, that foreshadows the “topics” logic of ch. 5; Position: ch. 3 and ch. 5 (clustering in the service of classification).

• Word sense induction by neural clustering — Abdine, Kamal Eddine, Buscaldi & Vazirgiannis, Word Sense Induction with Hierarchical Clustering and Mutual Information Maximization, AI Open 2023 (arXiv:2210.05422) — a paper co-signed by the two instructors of the module: clustering the occurrences of a word by their contextual embeddings (BERT), with a mutual information criterion that is maximized — the exact dual of the “coherence” NPMI of ch. 5; Position: a merger of ch. 4 (embeddings) + ch. 5 (topics/clustering) + ch. 7 (BERT).

• JuriBERT — Douka, Abdine, Vazirgiannis, El Hamdani & Restrepo Amariles, NLLP@EMNLP 2021 (arXiv:2110.01485): adapting the masked LM to legal French — cf. ch. 7; it paves the way for Buscaldi’s work in legal IR (below).

9.2. Davide Buscaldi: QA, legal, sentiment, knowledge graphs

• Question answering by passage retrieval — Gómez-Soriano, Buscaldi et al., A Multilingual Question Answering System using an n-grams based Passage Retrieval Engine, IICAI 2005, and journal version (Answering questions with an n-gram based passage retrieval engine, JIIS 2011): ranking passages by query-passage n-gram overlap (the direct ancestor of the BM25 scoring of ch. 2), evaluated in multilingual settings (CLEF QA) and on spoken questions (QAST). Position: ch. 2 (n-grams, retrieval) and ch. 8 (the retriever before RAG — the “R” of RAG in M2, ch. 7, has this history).
• Legal information retrieval — Rosso, Correa & Buscaldi, Passage retrieval in legal texts, Journal of Logic and Algebraic Programming 2011 (doi): retrieving the relevant passages in court decisions — long texts, technical vocabulary, cross-references: exactly the “legal French” difficulties of ch. 8, on the retrieval side (JuriBERT, above, handles them on the model side).
• Sentiment for crisis management — Buscaldi & Hernandez-Farias, Sentiment Analysis on Microblogs for Natural Disasters Management: a Study on the 2014 Genoa Floodings, WWW Companion 2015 (doi): classifying the emotion of tweets during a flood — classification (ch. 3) on short, noisy text, with subtle classes (worry vs alert); natural follow-up: troll detection (TexTrolls, arXiv:1910.01340).
• Scientific knowledge graphs — Dessì, Osborne, Reforgiato Recupero, Buscaldi et al., AI-KG (ISWC 2020) and CS-KG (ISWC 2022): NLP pipelines (entity extraction, relation extraction — ch. 6) that turn millions of articles into a knowledge graph; Position: the exact outlet of the NER of ch. 6; these graphs feed the GraphRAG of the Graph ML module; the group’s LLM-KG article series connects the module to M2.
• In the LLM era: detection and memorization — with Liyanage & Nazarenko, a benchmark for detecting generated academic text (LREC 2022, arXiv:2202.02013); with Dentan, Shabou & Vanier: Predicting memorization within fine-tuned Large Language Models (ECAI 2025, arXiv:2409.18858) and the multilingual hallucination benchmark MUCH (LREC 2026, arXiv:2511.17081). Position: this research structures the “evaluation and safety” ch. 9 of the M2 LLMs module — the pedagogical continuity of the master’s program.

Exercises

1. ★ TF-IDF on paper, and IDF as PMI. On 3 given documents, compute by hand the TF-IDF matrix (natural log) of the reduced vocabulary, then the cosine similarity of each pair; verify with TfidfVectorizer (watch out for L2 normalization). Then rederive Proposition 2.3 in the cases \mathrm{df}(t)=n (term everywhere) and \mathrm{df}(t)=1 (unique term), and deduce why L2 weighting alone is not enough to squash omnipresent words.

   Proof. Solution (method):

   1. count tf(t,d);
   2. df(t) over the 3 documents, then \mathrm{idf}=\log(3/\mathrm{df}) (0 for a term present everywhere — it disappears);
   3. multiply;
   4. normalize each row \tilde d=d/\|d\|_2, so that \cos(d_i,d_j)=\tilde d_i^\top \tilde d_j — this is what sklearn returns;
   5. classic pitfall: sklearn uses the smoothed IDF \log\frac{1+n}{1+\mathrm{df}}+1; pass smooth_idf=False to recover the formula from the course.

   IDF as PMI:

   • \mathrm{df}=n \Rightarrow \mathrm{idf}=\log 1=0 — the term discriminates no document (zero PMI);
   • \mathrm{df}=1 \Rightarrow \mathrm{idf}=\log n — the term perfectly identifies its document.

   The L2 norm rescales documents, not columns: a frequent word keeps a high tf in all documents — only IDF (a per-column weight) squashes it. ∎

2. ★ BPE. Redo example 1.4 with the corpus stage×3, stages×2, stand×4 and list the 5 first merges; what happens if we add stand×40?

   Proof. Solution (start): initial pairs (s,t)=9, (t,a)=9, (a,g)=5, (a,n)=4… — the initial (s,t)/(t,a) tie is broken arbitrarily; with stand×40, the pair (a,n) reaches 44 and stand becomes a token before the other roots — this is BPE’s lesson: the vocabulary encodes the corpus frequencies, not linguistics. ∎

3. ★ Analogies and bias. With pretrained embeddings (GloVe fr), test 10 analogies and measure the success rate; compute the WEAT statistic on two sets of professions × two lists of first names; implement neutralization (projection removal) and measure the effect on both scores.

4. ★ Viterbi. Implement Viterbi for a toy POS tagger (2 labels, 5-word vocabulary); verify optimality against exhaustive enumeration; complexity \mathcal{O}(TK^2); modify the proof of Algorithm 6.2 for the case of paths with zero weights.

5. ★ MinHash/LSH. For r=5, b=20, plot \mathbb{P}_{\mathrm{detect}}(J)=1-(1-J^r)^b and locate the “threshold”; which pair (r,b) at m=256 gives a threshold close to J=0.7?

   Proof. Solution: the sigmoid goes from ~0.1 to ~0.9 between J\approx0.35 and J\approx0.65 — threshold \approx(1/b)^{1/r}\approx 0.55.

   To target 0.7 one needs b \approx 0.7^{-r} with rb \le 256.

   Then r=9, b=25 gives (1/25)^{1/9}\approx 0.70 with 225 of the 256 hashes (while r=8, b=32 uses all 256 but puts the threshold near 0.65).

   Keep the rule of thumb: threshold \approx (1/b)^{1/r}, and a larger m makes the curve steeper. ∎

6. ★★ BM25. Show that the tf factor of BM25 is increasing, bounded by k_1+1, and reaches half its value at \mathrm{tf}=k_1(1-b+b|d|/\mathrm{avgdl}); comment on the effect of b=0.9 on a corpus of documents with widely varying lengths.

   Proof. Solution: set g(x)=\frac{x(k_1+1)}{x+c} with c=k_1(1-b+b|d|/\mathrm{avgdl})>0. Then g'(x)=\frac{c(k_1+1)}{(x+c)^2}>0, \qquad g\to k_1+1, \qquad g(x)=\frac{k_1+1}{2} \Leftrightarrow x=c .

   High b: long documents see their c increase → slower saturation and a stronger penalty — suited when length signals richness; dangerous on heterogeneous mixtures of short/long documents. ∎

7. ★★ Naive Bayes. Derive the MLE estimator of \mathbb{P}(t \mid c), show the problem of zero probabilities and justify Laplace smoothing as the posterior mean under Dirichlet(1,…,1) (theorem 3.1); implement and compare against MultinomialNB on 20 Newsgroups; test the effect of α on calibration.

   Proof. Solution (core): Lagrangians → relative counts; a test word absent from the class → \log 0: the class is eliminated; the uniform prior adds a “pseudo-count” of 1 to every term → the smoothed formula; α>1 squashes differences (less overconfident), α<1 sharpens them (more discriminative, less calibrated). ∎

8. ★★ Skip-gram. Write the negative-sampling loss of Theorem 4.1 for one pair (center w, context c) and k negatives n_1,\dots,n_k, \mathcal{L}_{\mathrm{neg}} = -\log \sigma(u_c^\top v_w) - \sum_{i=1}^{k}\log \sigma(-u_{n_i}^\top v_w), a loss to minimize (its negative is the objective that skip-gram maximizes). Compute the gradient in v_w and interpret it (who is attracted, who is repelled, with what force); implement on a small corpus and check that words with similar contexts have close embeddings.

   Proof. Solution: since the derivative of -\log\sigma(x) is -(1-\sigma(x)) and that of -\log\sigma(-x) is \sigma(x), \nabla_{v_w}\mathcal{L}_{\mathrm{neg}}=-\big(1-\sigma(u_c^\top v_w)\big)\,u_c+\sum_{i=1}^{k}\sigma(u_{n_i}^\top v_w)\,u_{n_i} (Theorem 4.1). A descent step moves v_w toward u_c with weight 1-\sigma and away from each u_{n_i} with weight \sigma; check: cosine neighborhood of “graphe” ≈ {réseau, nœud, arête}. ∎

9. ★★ LDA. Write the joint law of model 5.1, integrate out \theta_d and \varphi_k and recover the Gibbs equation of theorem 5.2 in the case K=2, \alpha_{\mathrm{LDA}}=\beta_{\mathrm{LDA}}=1 (the multivariate betas reduce to generalized factorials); verify numerically the “rich-get-richer” reinforcement on 200 words.

10. ★★ Comparison. On a classification task from your own corpus: Naive Bayes / TF-IDF+SVM / fine-tuned CamemBERT — plot accuracy vs training size (50, 200, 1000, all) and comment on the crossover.

11. ★★ Ranking metrics. For a query with R = 4 relevant documents, an engine returns the ten-document list (rel, rel, not, rel, not, not, not, rel, not, not). Compute P@5, Recall@5, AP and the reciprocal rank; then, with graded judgments (2, 3, 0, 1, 0, 0, 0, 2, 0, 0), compute nDCG@5. Which single swap of two documents increases nDCG@5 the most?

12. ★★ Relation extraction, scored on 2WikiMultiHopQA. Extend the lab sheet of section 6.4. On the training split of 2WikiMultiHopQA (Ho et al., 2020), label by distant supervision: a sentence of a supporting paragraph that contains the head and the tail of an evidence triple gets its relation, other entity pairs get “none”. Fine-tune the entity-marker classifier on these examples (Protocol 7.1). Compare it with the few-shot JSON extractor on 200 development questions: strict and relaxed triple micro-F1 (Definition 6.5), per relation type. Finally, read 20 distant labels and count the wrong ones.

    Proof. Solution (what to expect and to check):

    • candidate pairs are taken within a sentence and in both orders, since a relation is directed;
    • relaxed F1 exceeds strict F1 mostly through dates and aliases (“1934” vs “3 June 1934”, “Bertolucci” vs “Bernardo Bertolucci”): normalize dates before scoring;
    • a distant label is wrong when a sentence names both entities without stating the relation (the director and an actor of the same film); evidence triples whose head and tail never share a sentence give no training example at all — report how many;
    • report the number of training pairs, the seeds, and the gap between the two extractors with a bootstrap interval over questions. ∎

13. ★★ Matrix factorization. Implement Model 8.3 with SGD on the MovieLens-100k ratings (temporal split), with k \in \{5, 20, 50\} and \lambda \in \{0.01, 0.1\}; report RMSE and Recall@10, compare with a content-based recommender on the movie text (TF-IDF profiles of the titles and genres of u.item, or of plot summaries if you join them; Definition 8.2), and measure both on movies with fewer than five training ratings.

14. ★★★ Capstone (project). Carry out the project of ch. 8 (box in 8.6), with its relation stage built as in section 6.4; each stage must report ITS metric (NPMI coherence for LDA, macro-F1 for classification, entity-level F1 for NER, strict and relaxed triple F1 for relations) and an error analysis on 10 examples.

Projects and assessment

Official assessment: not displayed — the 2026–2027 sheet gives no assessment modality (see the fiche); the proposals below are ours. We propose Exercise 14, the capstone, as the graded NLP deliverable: taken with Graph ML and Reinforcement Learning, it is the NLP work package of the Year 1 team project (box in 8.6), and the course is used again by the Year 2 projects Y2.1 to Y2.4 (Y2.2 for tokenization only). The projects exercise the master objectives O3 (tokenization, transformers, fine-tuning, retrieval), O5 (text turned into a knowledge graph for GraphRAG) and O7 (pipelines measured at every stage).

Solo projects

1. [Solo · ≈ 20 h] Tokenizer fertility in French and English. Does a subword tokenizer make French more expensive than English, and does the choice change accuracy?
   • Implement: BPE and Unigram tokenizers trained with SentencePiece at 8k, 16k and 32k tokens on the French–English Europarl corpus (Koehn, 2005); fertility (tokens per word) on held-out parallel sentences, compared with the CamemBERT and GPT-2 tokenizers.
   • Downstream: macro-F1 of TF-IDF + logistic regression on subword tokens, on the Allociné (French) and IMDb (English; Maas et al., 2011) sentiment reviews.
   • Deliverables: code, a 4-page report, a 10-minute talk. Chapters: ch. 1, 3, 7.
   • Success: a fertility table with bootstrap intervals, and an F1 effect stated against the seed-to-seed spread.
2. [Solo · ≈ 25 h] Paper study: keywords from graphs of words. Reproduce Tixier, Malliaros & Vazirgiannis (EMNLP 2016), “A Graph Degeneracy-based Approach to Keyword Extraction”, and test it against the methods of ch. 8.
   • Implement: graph-of-words with k-core and main-core extraction (ch. 9, networkx), TextRank (8.1), RAKE, YAKE and KeyBERT with MMR (8.2).
   • Data: the Hulth (2003) Inspec abstracts with their gold keywords, one of the datasets of the paper.
   • Deliverables: code, a 6-page report, a 10-minute talk. Chapters: ch. 2, 8, 9.
   • Success: precision, recall and F1 within about 2 points of the paper’s figures, or a documented reason for the gap; a paired bootstrap between the best graph method and KeyBERT.
3. [Solo · ≈ 20 h] Text-aware cold start on MovieLens. Can item text rescue the items that matrix factorization cannot score? This is the solo version of the text tower of Y1.3.
   • Implement: Model 8.3 by SGD and by ALS on MovieLens-25M with a temporal split; a content-based recommender on the user tags (TF-IDF and Sentence-BERT profiles, Definition 8.2); the hybrid q_i = W x_i fitted by ridge regression on the warm items.
   • Deliverables: code, a 4-page report. Chapters: ch. 2, 7, 8.
   • Success: Recall@10 and nDCG@10 overall and on the items with fewer than 5 training ratings, where the hybrid should beat MF with a bootstrap interval that excludes zero.

Group projects

1. [Group of 3 · ≈ 30 h each] From paragraphs to a knowledge graph. Which extractor gives the GraphRAG of Graph ML (ch. 10) the most useful graph, and at what cost? This is the NLP package of Y1.1.
   • Member A — entities: a CRF with hand-crafted features vs a fine-tuned encoder on CoNLL-2003, scored by entity-level F1 (ch. 6).
   • Member B — relations: the entity-marker classifier trained by distant supervision vs the few-shot JSON extractor, on the evidence triples of 2WikiMultiHopQA (Ho et al., 2020; section 6.4).
   • Member C — graph and use: entity resolution, MinHash deduplication of near-identical paragraphs (8.3), export to the Graph ML GraphRAG lab, and answers to 200 questions compared with the RAG of section 7.4.
   • Deliverables: one repository, a 6-page report, a 15-minute talk. Chapters: ch. 6, 7, 8.
   • Success: a metric at every stage (entity F1, strict and relaxed triple F1, answer F1), and a GraphRAG gain over 7.4 on two-hop questions — or a documented reason why there is none.
2. [Group of 3 · ≈ 30 h each] Paper study: hybrid French legal search on BSARD. Reproduce and extend Louis & Spanakis (ACL 2022), “A Statutory Article Retrieval Dataset in French”: more than 1,100 legal questions labeled by jurists with the relevant articles among about 22,600 Belgian law articles.
   • Member A: a hand-built inverted index scored by BM25 (section 2.1), with k_1 and b tuned on the training questions.
   • Member B: dense retrieval with a French sentence encoder, then fine-tuned on the training questions with in-batch negatives (7.3).
   • Member C: reciprocal rank fusion (7.4); Recall@100, MAP and MRR (Definition 2.7); failure analysis on legal vocabulary (the legal-IR work of ch. 9). Optional: a LinUCB bandit (Reinforcement Learning, ch. 4) that chooses sparse or dense per query.
   • Deliverables: code, a 6-page report, a 15-minute talk. Chapters: ch. 2, 7, 9.
   • Success: BM25 within a few points of the paper’s BM25 baseline, and a paired test of fusion against each retriever.

Written exam (proposal)

Format: 2 hours, one handwritten A4 sheet allowed, no electronic devices; four questions, 20 points.

1. Question (5 points). (a) Name the two flaws of TF-IDF scoring that BM25 corrects, and the parameter that controls each. (b) In the RAG pipeline of section 7.4, give one query on which BM25 beats a Sentence-BERT retriever and one on which it loses, and say what reciprocal rank fusion does.

   Expected: (a) unbounded growth in tf, replaced by saturation toward k_1+1 at a speed set by k_1; no length normalization, added by b (Model 2.4). (b) BM25 wins on rare exact strings (a product code, an article number) and loses on paraphrases (“car” for “automobile”). RRF sums reciprocal ranks, so a chunk found by either retriever can reach the fused top k without calibrating the two scores.

2. Question (5 points). A two-state HMM (N noun, V verb) has \pi=\begin{pmatrix}0.9\\0.1\end{pmatrix},\qquad \mathbb{P}(z_t\mid z_{t-1})=\begin{pmatrix}0.8&0.2\\0.3&0.7\end{pmatrix},\qquad \begin{array}{c|ccc} & \text{le} & \text{chat} & \text{mange}\\\hline \text{N} & 0.6 & 0.3 & 0.02\\ \text{V} & 0 & 0.02 & 0.9\end{array} (rows of the transition matrix: previous state N, then V; the table gives the emission probabilities). For “le chat mange”: (a) run Viterbi and give the best labeling and its joint probability; (b) run the forward algorithm and give the probability of the sentence; (c) deduce the posterior probability of the best labeling.

   Expected: (a) the Viterbi scores for (N, V) are \delta_1=(0.54,\,0),\qquad \delta_2=(0.1296,\,0.00216),\qquad \delta_3=(0.00207,\,0.0233), so the best labeling is N N V, with joint probability 0.0233. (b) \alpha_3=(0.00209,\,0.0247), so the sentence has probability 0.0268. (c) The posterior is 0.0233/0.0268\approx 0.87.

3. Question (4 points). A relation extractor is run on two documents. Document A has 3 gold triples; the system predicts 2, both correct. Document B has 2 gold triples; the system predicts 4, one of them correct. (a) Compute the micro-averaged precision, recall and F1 (Definition 6.5). (b) Compute the average of the per-document F1 scores. (c) Which average would you report for a corpus with a few very long documents, and why?

   Expected: (a) P=3/6=0.5, R=3/5=0.6, F_1\approx 0.545. (b) A has F1 0.8 and B has F1 0.333, so the average is about 0.567. (c) The micro average weights every triple equally, so long documents dominate it; it measures the graph that will actually be used. Report it, with per-document scores to show that short documents are not neglected.

4. Question (6 points). In skip-gram with negative sampling (Theorem 4.1), let \#(w,c) count the (center, context) pairs, \#(w) and \#(c) be its margins and |D| the number of pairs; the noise law is p_n(c)=\#(c)/|D|. As a function of x=u_c^\top v_w, the expected loss of the pair is \ell(x)=-\#(w,c)\,\log\sigma(x)-k\,\#(w)\,\frac{\#(c)}{|D|}\,\log\sigma(-x). Show that, for \#(w,c)>0 and x free, the minimum is reached at x^\star=\mathrm{PMI}(w,c)-\log k,\qquad \mathrm{PMI}(w,c)=\log\frac{\#(w,c)\,|D|}{\#(w)\,\#(c)}.

   Expected: both terms are convex, since -\log\sigma(x)=\log(1+e^{-x}) and -\log\sigma(-x)=\log(1+e^{x}). Setting the derivative to zero gives \#(w,c)\,\big(1-\sigma(x)\big)=k\,\frac{\#(w)\,\#(c)}{|D|}\,\sigma(x)\iff e^{x}=\frac{\sigma(x)}{1-\sigma(x)}=\frac{\#(w,c)\,|D|}{k\,\#(w)\,\#(c)}, hence x^\star. Comment: the embeddings factorize a shifted PMI matrix (Levy & Goldberg, 2014), the link with GloVe in ch. 4.

Grading rubric (proposal)

References

• Textbooks: D. Jurafsky, J. Martin, Speech and Language Processing, 3rd ed. (draft) — free online (the module’s textbook); C. Manning, H. Schütze, Foundations of Statistical Natural Language Processing, MIT Press, 1999 (HMM, CRF, collocations).
• Tokenization: R. Sennrich et al., Neural Machine Translation of Rare Words with Subword Units (BPE), ACL 2016; T. Kudo, J. Richardson, SentencePiece, EMNLP 2018; T. Kudo, Subword Regularization (Unigram), ACL 2018.
• Weighting and retrieval: S. Robertson, H. Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond, Foundations and Trends in IR, 2009 — doi; A. Broder, Min-wise Permutations (MinHash), 1998.
• Language models and HMMs (sections 1.3, 6.1): R. Kneser, H. Ney, “Improved backing-off for M-gram language modeling”, ICASSP 1995; S. F. Chen, J. Goodman, “An empirical study of smoothing techniques for language modeling”, Computer Speech & Language, 1999; L. R. Rabiner, “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”, Proceedings of the IEEE, 1989 (forward-backward, Baum–Welch).
• Embeddings: T. Mikolov et al., Efficient Estimation of Word Representations in Vector Space, 2013; Y. Goldberg, O. Levy, word2vec Explained: deriving Mikolov et al.’s negative-sampling word-embedding method, 2014; O. Levy, Y. Goldberg, Neural Word Embedding as Implicit Matrix Factorization, NeurIPS 2014 (the shifted-PMI result of ch. 4); J. Pennington et al., GloVe, EMNLP 2014; P. Bojanowski et al., Enriching Word Vectors with Subword Information (fastText), TACL 2017; S. Arora, Y. Liang, T. Ma, A Simple but Tough-to-Beat Baseline for Sentence Embeddings, TACL 2017; A. Caliskan et al., Semantics derived automatically from language corpora contain human-like biases, Science 2017; T. Bolukbasi et al., Man is to Computer Programmer as Woman is to Homemaker, NeurIPS 2016.
• Topic models: D. Blei, A. Ng, M. Jordan, Latent Dirichlet Allocation, JMLR 2003; T. Griffiths, M. Steyvers, Finding scientific topics, PNAS 2004 (Gibbs); J. Chang et al., Reading Tea Leaves: How Humans Interpret Topic Models, NeurIPS 2009.
• Classification, sequences, transformers: A. Joulin et al., Bag of Tricks for Efficient Text Classification, EACL 2017; Y. Kim, Convolutional Neural Networks for Sentence Classification, EMNLP 2014; J. Lafferty et al., Conditional Random Fields, ICML 2001; J. Devlin et al., BERT, NAACL 2019; Y. Liu et al., RoBERTa, 2019; C. Raffel et al., T5, JMLR 2020; N. Reimers, I. Gurevych, Sentence-BERT, EMNLP 2019; L. Martin et al., CamemBERT, ACL 2020; H. Le et al., FlauBERT, ACL 2020.
• Relation extraction (section 6.4): E. F. Tjong Kim Sang, F. De Meulder, “Introduction to the CoNLL-2003 Shared Task: Language-Independent Named Entity Recognition”, CoNLL 2003; M. Mintz, S. Bills, R. Snow, D. Jurafsky, “Distant supervision for relation extraction without labeled data”, ACL-IJCNLP 2009; S. Riedel, L. Yao, A. McCallum, “Modeling Relations and Their Mentions without Labeled Text”, ECML PKDD 2010; L. Baldini Soares, N. FitzGerald, J. Ling, T. Kwiatkowski, Matching the Blanks: Distributional Similarity for Relation Learning, ACL 2019; Z. Zhong, D. Chen, A Frustratingly Easy Approach for Entity and Relation Extraction, NAACL 2021; P.-L. Huguet Cabot, R. Navigli, “REBEL: Relation Extraction By End-to-end Language generation”, Findings of EMNLP 2021; X. Ho, A.-K. Duong Nguyen, S. Sugawara, A. Aizawa, Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps (2WikiMultiHopQA), COLING 2020.
• Transformers, prompting and RAG (ch. 7): A. Vaswani et al., Attention Is All You Need, NeurIPS 2017; V. Sanh et al., DistilBERT, 2019; T. Brown et al., Language Models are Few-Shot Learners, NeurIPS 2020; T. Z. Zhao, E. Wallace, S. Feng, D. Klein, S. Singh, Calibrate Before Use: Improving Few-Shot Performance of Language Models, ICML 2021; M. Henderson et al., Efficient Natural Language Response Suggestion for Smart Reply, 2017 (in-batch negatives); P. Lewis et al., Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks, NeurIPS 2020; V. Karpukhin et al., Dense Passage Retrieval for Open-Domain Question Answering, EMNLP 2020; G. V. Cormack, C. L. A. Clarke, S. Büttcher, “Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods”, SIGIR 2009; N. F. Liu et al., Lost in the Middle: How Language Models Use Long Contexts, TACL 2024.
• Industrial text mining: R. Mihalcea, P. Tarau, TextRank, 2004; S. Rose et al., Automatic Keyword Extraction from Individual Documents (RAKE), 2010; R. Campos et al., YAKE!, Information Processing & Management 2020 (code).
• Retrieval engines and evaluation (section 2.1): C. Manning, P. Raghavan, H. Schütze, Introduction to Information Retrieval, Cambridge University Press, 2008 — free online (inverted index, MAP); K. Järvelin, J. Kekäläinen, “Cumulated Gain-Based Evaluation of IR Techniques” (nDCG), ACM TOIS, 2002.
• Recommendation, advertising, social media (sections 8.5–8.6): Y. Koren, R. Bell, C. Volinsky, “Matrix Factorization Techniques for Recommender Systems”, IEEE Computer, 2009; Y. Hu, Y. Koren, C. Volinsky, “Collaborative Filtering for Implicit Feedback Datasets”, ICDM 2008; H. B. McMahan et al., “Ad Click Prediction: a View from the Trenches”, KDD 2013; J. Kleinberg, “Bursty and Hierarchical Structure in Streams”, KDD 2002.
• Research at DaSciM (Vazirgiannis, Buscaldi) (ch. 9): Rousseau & Vazirgiannis (TW-IDF, CIKM 2013); Tixier, Malliaros & Vazirgiannis (degeneracy, EMNLP 2016); Skianis et al. (EMNLP 2016); Giatsidis et al. (CoreCluster, AAAI 2014); Abdine, Buscaldi et Vazirgiannis (WSI, AI Open 2023); Douka et al. (JuriBERT, 2021); Buscaldi et al. (JIIS 2011; WWW 2015; TexTrolls; generated-text detection; memorization; MUCH).
• Data and papers of the projects: P. Koehn, “Europarl: A Parallel Corpus for Statistical Machine Translation”, MT Summit 2005; A. Maas et al., “Learning Word Vectors for Sentiment Analysis” (IMDb reviews), ACL 2011; A. Hulth, “Improved Automatic Keyword Extraction Given More Linguistic Knowledge”, EMNLP 2003; F. M. Harper, J. A. Konstan, “The MovieLens Datasets: History and Context”, ACM TiiS, 2015; A. Louis, G. Spanakis, A Statutory Article Retrieval Dataset in French (BSARD), ACL 2022.
• Tools: HuggingFace Course (the labs follow this curriculum); spaCy; gensim; rank_bm25; datasketch (MinHash LSH).