Multiword features (n-grams, e.g. 'text mining'): rare but predictive; score with $AM(T)$ (s.69)

CSR sparse storage: keep (column, value) pairs, e.g. row 8 0 5 2 → (1,8)(3,5)(4,2) (s.70)

Selection keeps a subset of columns; reduction makes new combined features $\mathbb R^m\to\mathbb R^d$ (s.173-174)

Feature extractor: input $x$ → (feature name, value) pairs; e.g. length>10, contains '@' (s.5)

Linear model: $\mathbf w\cdot\phi(x)=\sum_j w_j\phi(x)_j$; predict sign; $\mathbf w$ learned by optimizing a loss (s.8-10)

Text normalization = tokenize + normalize word forms + segment sentences (s.16)

Bag of words: rows = documents, columns = vocabulary words, cell = presence / frequency / thresholded freq / tf-idf (s.63-66)

↪ too big, so → 06 · Dictionary reduction & IG

↪ compare with → 07 · Cosine similarity

Corpus: collected documents (crawler, mail logs). Examples: Reuters-21578, RCV1 (~810k stories) (s.13-14)

BoW pros/cons (s.71)

• Pros: simple, effective, fast
• Cons: no word order, no semantics, high-dimensional

Zipf's law: few very frequent words, many rare (power law) (s.22)

02 · Pre-processing

Raw text → tokens → normalized words → bag of words → selection / SVD

(s.N) = slide number. Condensed from the chunk notes.

Tokenization is hard: . , : - ' are context-dependent (100,000; Dr.; isn't); Chinese/Japanese have no spaces (s.18-21)

↪ next step → 03 · Stemming & lemmas

Stop words: functional words, little information; list is language dependent (s.24)

Case folding: helps IR; hurts sentiment/IE (US vs us, Fed vs fed) (s.29)

Sentence boundary detection: ? ! unambiguous; '.' may be abbreviation/number (Inc., 4.3); hand-written decision rules (s.37-41)

WSD / Simplified Lesk: choose the sense whose gloss overlaps the context most, ignoring stop words (s.49-51)

WordNet: senses grouped in synsets; relations hypernym ↑ / hyponym ↓, holonym (part-of) / meronym (has-part) (s.58-62)

↪ senses → 02 · Tokens & words

Cosine similarity = cosine of the angle between count vectors; length is irrelevant (s.121)

Cases: identical → 1 (0°); no shared words → 0 (90°); 'Hello, World!' vs 'Hello!' → 0.71 (45°) (s.122-134)

Repeating a word ('Hello Hello Hello!') scales the vector but the angle, hence the similarity, stays the same (s.114-120)

Dictionary reduction fights high dimensionality: stopwords, frequent words, stemming, feature selection, PCA/topic models (s.72-73)

↪ or instead → 08 · Dim. reduction & LSA

Entropy $-\sum p_i\log_2p_i$; max $\log_2K$ (uniform), 0 (pure). $Entropy([9+,5-])=0.94$ (s.78-80)

Stemming vs lemmatization (s.31-34)

• Stem: crude affix chop, may be a non-word (exampl)
• Lemma: dictionary headword (am/are/is → be)

Morphology: morpheme = smallest meaningful unit (un-like-ly = 3); stem + affixes; inflectional keeps meaning, derivational changes it (s.32, 30)

IG $=E(X)-E(X|Y)$. Humidity: $0.94-\frac7{14}0.592-\frac7{14}0.985=0.1515$ (s.81-86)

Exam traps: discuss / describe / compare (see Past Exam note)

High entropy ≠ good split: a good feature has high IG → low-entropy children (s.78-79)

idf form: this deck $\log(1+N/df)$, Intro $\log(N/df)$ (s.67)

New doc in LSA uses $V_d$, never recompute SVD; $d$ < rank (s.189, 192)

Truncated SVD: keep $d$ largest singular values (< rank); docs $U_d\Sigma_d$; new doc $\mathbf qV_d$ (s.185-192)

Why LSA: maps synonyms to the same dimension; doc4/doc5 cosine ~0 → 0.75 in 2-D (s.182, 188, 190-191)

tf-idf: $tf\cdot idf$, $idf=\log(1+N/df)$. Frequent in doc ↑, in many docs ↓ (s.67)

Tokens vs types: $N$ running words, $|V|$ distinct words. Normalization shrinks $|V|$, not $N$ (s.23)

Homonymy = unrelated meanings (bank); polysemy = related (man); synonymy = same meaning (s.22)

SVD: $C=U\Sigma V^T$; docs in topic space $=U\Sigma=CV$; each topic = linear combination of words (s.178-183)

Other representations: NMF, LDA, RNN/CNN (s.193)

Off-the-shelf tools used in ~80% of applications (s.57)

POS tagging labels words (Penn Treebank tags) vs parsing builds tree/dependencies (Universal Dependencies) (s.42-56)

Attribute ranking: score each feature (DF, IG, MI, chi-square), keep top $k$ (s.74)

Added context: Outlook 0.247 > Humidity 0.152 > Windy 0.048 > Temperature 0.029 (s.87)

Stem ≠ lemma: stems can be non-words; lemmas are dictionary forms (s.31)

Cosine: small angle = high similarity; the angle itself is not the similarity (s.125, 131)

Manual: count table → plot → angle → cosine; formula is the shortcut. $n$ = vocabulary size, not phrase length (s.136-150)

$\cos\theta=\frac{\sum A_iB_i}{\sqrt{\sum A_i^2}\sqrt{\sum B_i^2}}$ (s.151, 172)

Porter vs Lancaster: Lancaster more aggressive (loving → lov, sushi → sush) (s.35)

English is hard: irregular forms (sought → seek), ambiguity (bored) (s.33)