02 Pre-processing - Cheat Sheet

Up: 02 Pre-processing - Index | 02 Pre-processing - Mind Map

Definitions

• Feature extractor: maps input $x$ to (feature name, value) pairs; Concept - Feature Extraction (s.5). Linear model: score $\mathbf{w}\cdot \varphi (x)$, predict sign (s.8-9); Concept - Linear Model.
• Tokens vs types: $N$ = running words, $|V|$ = distinct words; normalization shrinks $|V|$, not $N$ (s.23); Concept - Tokens and Types.
• Zipf’s law: few very frequent words, many rare ones (s.22); Concept - Zipf’s Law.
• Stemming = crude affix chopping, may give non-words (exampl); lemmatization = dictionary headword (am/are/is → be) (s.31-34); Concept - Stemming, Concept - Lemmatization, Concept - Morphology.
• Case folding: good for IR, bad for sentiment/IE (US vs us) (s.29); Concept - Case Folding.
• Sentence boundary: ? ! unambiguous, ”.” ambiguous (abbrev., numbers) (s.37-41); Concept - Sentence Boundary Detection.
• POS tagging labels words (Penn Treebank tags); parsing builds structure (constituency tree / Concept - Universal Dependencies) (s.42-56); Concept - Penn Treebank, Concept - Parsing.
• WSD / Lesk: pick the sense whose gloss overlaps the context most (s.49-51); Concept - Word Sense Disambiguation, Concept - Lesk Algorithm, Concept - WordNet, Concept - WordNet Relations.
• Bag of words: document × word matrix (presence / frequency / thresholded / tf-idf), ignores order (s.63-71); Concept - Bag of Words, Concept - Document-Term Matrix, Concept - Sparse Matrix (CSR), Concept - Multiword Features.
• Feature selection keeps a subset of columns; dimensionality reduction creates new combined features ${\mathbb{R}}^m\to {\mathbb{R}}^d$ (s.173-174); Concept - Feature Selection, Concept - Dimensionality Reduction, Concept - Dictionary Reduction, Concept - Curse of Dimensionality.
• LSA = SVD of the doc-term matrix; handles synonymy/relatedness (s.190-191); Concept - Latent Semantic Analysis (LSA), Concept - Singular Value Decomposition (SVD), Concept - Truncated SVD, Concept - Non-negative Matrix Factorization (NMF), Concept - Synonymy and Semantic Relatedness.

Formulas

Name	Formula
tf-idf (s.67)	$tf\cdot idf$, $idf(w)=\log (1+N/df(w))$ (Intro s.26 uses $\log (N/df)$)
Entropy (s.78)	$-{\sum }_i{p}_i{\log }_2{p}_i$; max ${\log }_{2}K$, min 0; $Entropy([9+,5-])=0.94$
Information gain (s.81)	$IG=E(X)-E(X\mid Y)$; Humidity: $0.94-\frac{7}{14}0.592-\frac{7}{14}0.985=0.1515$
Cosine similarity (s.151, 172)	$\frac{\sum A_i{B}_i}{\sqrt{\sum A_i^2}\sqrt{\sum B_i^2}}$; identical 1, disjoint 0, “Hello, World!” vs “Hello!” 0.71
SVD (s.178, 183)	$C=U\Sigma V^T$; docs $=U\Sigma =CV$
Truncated SVD (s.188-192)	docs $U_d{\Sigma }_d$; new doc $\mathbf{q}{V}_d$; $d<$ rank

Weather IG ranking (added context): Outlook 0.247 > Humidity 0.152 > Windy 0.048 > Temperature 0.029.

Key comparisons

A	B
Stemming: rules, non-words, fast	Lemmatization: dictionary (+POS), valid words
Porter: milder	Lancaster: more aggressive (loving → lov)
Homonymy: unrelated meanings (bank)	Polysemy: related meanings (man)
Feature selection: subset of words	Dimensionality reduction: new combined features
Entropy: property of one set	IG: drop in entropy after a split
Cosine: angle only, length ignored	Euclidean-style length: not used

Most likely exam questions

1. Compare stemming and lemmatization with examples (s.31-34).
2. Difficulties of tokenization and of sentence boundary detection (s.18-21, 37-41).
3. Explain tf-idf and its intuition, as discussed in class (s.67-68).
4. Pros and cons of bag of words (s.71): simple, effective, fast / no order, no semantics, high-dimensional and sparse.
5. Describe feature selection by attribute ranking; compute entropy / information gain (s.74-88).
6. State the cosine similarity formula and explain its symbols; why length does not matter (s.121, 142-150).
7. How is dimensionality reduced in LSA; how is a new document mapped (s.185-192)? Why does doc 4 vs doc 5 similarity go from ~0 to 0.75?
8. How does LSA address synonymy (s.191)?

Style guide: Past Exam - Question Bank & Style Guide.