02 Pre-processing - Chunk 01 (s.1-30)

Overview

This lecture (“Text Preprocessing: From textual information to numerical vector”, slides adapted from Zhao Rui & Chen Zhenghua of NTU, Juri Leskovec of Stanford and Josh Starmer of StatQuest) explains how raw text is turned into numerical features (s.1). It opens with a toy supervised task, predicting whether a string is an email address, to introduce Concept - Feature Extraction, feature/weight vectors and the Concept - Linear Model (s.2-10). It then moves to Concept - Text Preprocessing proper: collecting documents / Concept - Corpus (s.12-14), Concept - Text Normalization (s.15-16), Concept - Tokenization and its pitfalls (s.17-21), word properties and Concept - Zipf’s Law (s.22), Concept - Tokens and Types (s.23), Concept - Stopword Removal (s.24-25), normalization by equivalence classes, Concept - Case Folding and Concept - Lemmatization / Concept - Stemming (s.26-30).

Detailed notes

1. A simple text-mining case: supervised learning with features (s.2-10)

• s.2 is a divider slide: “A Simple Text Mining Case”.
• Supervised framework (s.3): Training Data -> Machine Learning Model -> function $f$. At prediction time input $X$ goes into $f$ and the output is the target $Y$.
• Task (s.4): predict $y$, whether a string $x$ is an email address:
  • $x$ = “rui.zhao@ntu.edu.sg” -> $y=1$
  • $x$ = “ntuwkw” -> $y=0$
  • $x$ = “@trump” -> $y=0$
  • The slide ends with the open question “How do you address the problem?”
• Feature extraction (s.5): Question: what properties of $x$ might be relevant for predicting $y$? A feature extractor takes input $x$ and outputs a set of (feature name, feature value) pairs. Example for “ntu@gmail.com” (read top to down):

Feature name	Value
Length > 10	1
Length < 50	1
contain ”@“	1
endwith “com”	1
endwith “sg”	0
length between @ and .	5
fraction of alpha	0.85

• Feature vector notation (s.6): mathematically the feature vector does not need feature names: only the column of values $(1,1,1,1,0,5,0.85)$ is kept; it lives in the feature vector space (dashed box).
• Weight vector notation (s.7): for each feature $j$ there is a parameter (weight) representing the contribution of that feature to the prediction. Slide values: Length>10: -1.2; Length<50: 1.4; contain ”@”: 2.2; endwith “com”: 0.6; endwith “sg”: 0.5; length between @ and .: 0.3; fraction of alpha: 0.6.
• Linear model (s.8): linearly combine the features by the weights (weighted combination): $\mathbf{w}\cdot \varphi (x)={\sum }_{j=1}^d{w}_j\varphi (x{)}_j$. Worked output on the slide: $-1.2(1)+1.4(1)+2.2(1)+0.6(1)+0.5(0)+0.3(5)+0.6(0.85)$ (the slide leaves it unevaluated; evaluating gives 5.01, see Added context below).
• Linear model, binary classification (s.9): weight vector $\mathbf{w}\in {\mathbb{R}}^d$, feature vector $\varphi (x)\in {\mathbb{R}}^d$, and $f_{\mathbf{w}}(x)=\text{sign}(\mathbf{w}\cdot \varphi (x))=\{\begin{array}{ll}+1& \mathbf{w}\cdot \varphi (x)>0\\ -1& \mathbf{w}\cdot \varphi (x)<0\\ ?& \mathbf{w}\cdot \varphi (x)=0\end{array}$
• Learning the parameters (s.10): (1) from data; (2) define a loss function and then optimize it.

Added context

Evaluating the s.8 sum: $-1.2+1.4+2.2+0.6+0+1.5+0.51=5.01>0$, so the model predicts class $+1$ (email address). The slide itself does not compute this number.

2. Introduction to text preprocessing (s.11-14)

• s.11 is a divider slide: “Introduction to Text Preprocessing”.
• From text to numerical features (s.12):
  • To mine text, we first need to process it into a form that data-mining procedures can use.
  • First we determine features (think of them as the columns of a spreadsheet).
  • Easy features: the occurrence of words.
  • Much more difficult semantic information: e.g. the grammatical function of a word in a sentence (subject, object, etc.).
• Collecting documents (s.13):
  • First step of text mining = collect the data (the relevant documents).
  • Some applications need a data-collection process: for a Web application deploy a tool such as a Web crawler; an email audit application may log all incoming/outgoing messages at a mail server for a period of time.
  • For research and development of text-mining techniques, more generic data is needed, usually called a Concept - Corpus: the Reuters collections (Reuters-21578 and RCV1 = Reuters Corpus Volume 1, about 810,000 English-language Reuters news stories, tagged with topics); the Gutenberg Project (very large collection of literary and other texts in machine-readable form once out of copyright); the Linguistic Data Consortium (LDC) provides various data.
• Collecting documents, continued (s.14): the UC Irvine Machine Learning Repository maintains 468 datasets (slide text says 468; the screenshot header reads “488 Data Sets”, a discrepancy in the source) such as Amazon reviews, email spam, sentiment-labelled sentences. Kaggle (data-mining competition) also provides data sets. Screenshots: left = UCI table (columns Name, Data Types, Default Task, Attribute Types, # Instances, # Attributes, Year; rows Abalone, Adult, Annealing, Anonymous Microsoft Web Data); right = Kaggle list (Top 50 Spotify Songs 2019, US Accidents (2.25 million records), Mock Traffic Data, College Basketball Dataset, Madrid Airbnb Data).

3. Text normalization (s.15-16)

• s.15 is a divider slide: “Text Normalization”.
• s.16: every NLP task including text mining needs text normalization, which consists of:
  • segmenting/tokenizing words in running text;
  • normalizing word formats (convert to standard or common forms);
  • segmenting sentences in running text.
• See Concept - Text Normalization.

4. Tokenization (s.17-21)

• s.17 is a divider slide: “Tokenization”.
• Definition and difficulty (s.18): breaks the stream of characters into words or tokens. Trivial for a person familiar with the language, more complicated for a computer (“linguistically challenged”), because certain characters are sometimes token delimiters and sometimes not, depending on the application.
  • space, tab, newline are always delimiters and are not counted as tokens; collectively called white space.
  • ( ) <> ! ? ” are always delimiters and may also be tokens.
• Ambiguous characters (s.19): the characters . , : - ’ may or may not be delimiters, depending on their environment. Example cases:
  • Numbers: 100,000 or 333-1221
  • Abbreviations: Dr.
  • Part of the current token: isn’t, D’angelo
  • Possessive: Tess’
  • To get the best features one may need to customize the tokenizer for the available text (e.g. part: 123-4567).
  • The tokenization process is language-dependent.
• Example issues (s.20): raw text vs possible tokenized text (the slide poses these as open questions):

Raw text	Tokenized text (options on slide)
Finland’s capital	Finland / Finlands / Finland’s ?
What’re, I’m, isn’t	what are, I am, is not ?
Hewlett-Packard	Hewlett Packard ?
state-of-the-art	state of the art ?
San Francisco	one token or two?

• Online word tokenization with Python NLTK: text-processing.com/demo/tokenize/, e.g. “He is in Finland’s capital”.
• Right-hand screenshots compare tokenizers on “He is in Finland’s capital”: TreebankWordTokenizer -> He | is | in | Finland | ‘s | capital; WordPunctTokenizer -> He | is | in | Finland | ’ | s | capital; PunktWordTokenizer -> He | is | in | Finland | ‘s | capital; WhitespaceTokenizer -> He | is | in | Finland’s | capital; pattern -> He | is | in | Finland | ‘s | capital. Takeaway: different tokenizers split the possessive differently.
• Language issues (s.21): Chinese and Japanese have no spaces between words. Example: 孙燕姿现在居住在新加坡东南部 -> segmented 孙燕姿 | 现在 | 居住 | 在 | 新加坡 | 东南部 = “Stefanie Sun | now | lives | in | Singapore | southeastern”. Further complicated in Japanese by multiple alphabets intermingled; the figure shows one Japanese sentence with boxes marking Katakana, Hiragana, Kanji and Romaji segments (e.g. “$500K” is Romaji).

5. Word properties and counting words (s.22-23)

• Word properties (s.22): relations among word surface forms and their senses (Concept - Word Sense Relations):
  • Homonymy: same form, different meaning (bank: river bank vs financial institution).
  • Polysemy: same form, related meaning (man: the human species, male of the human species, adult males of the human species).
  • Synonymy: different form, same meaning (singer and vocalist).
• Power-law word frequencies (s.22): a small number of very frequent words and a big number of low-frequency words; also called Zipf’s Law (Concept - Zipf’s Law). Figure: a steeply falling curve, x-axis Word Freq., y-axis Word Probs.; the green head (few very frequent words) drops to a long yellow tail.
• How many words? (s.23): $N$ = number of tokens; $V$ = vocabulary = set of types; $|V|$ is the size of the vocabulary (Concept - Tokens and Types).

Corpus	Tokens = N	Types = |V|
Switchboard phone conversations	2.4 million	20 thousand
Shakespeare	884,000	31 thousand
Google N-grams	1 trillion	13 million

• Figure: Google Books Ngram Viewer line chart (1800-2000) comparing the relative frequency of “life” (blue, about 0.05-0.07%) with “death” (red, falling from about 0.037% to about 0.018%); source books.google.com/ngrams. The slide gives no explicit takeaway for the chart (UNCLEAR (slide 23) as to its purpose beyond illustrating word-frequency counting).

6. Stop words (s.24-25)

• Definition (s.24): stop words are words that, from a non-linguistic view, do not carry information; they have mainly a functional role; usually we remove them to help methods perform better. They are natural-language dependent: English: A, ABOUT, ABOVE, ACROSS, AFTER, FROM, AGAIN, …; Chinese: 的, 一, 不, 在, 有, … (list source: ranks.nl/stopwords).
• Example (s.25): two web-page descriptions with stop words in red: “Information System Asia Web - provides research, IS-related commercial materials, interaction, and even research sponsorship by interested corporations with a focus on Asia Pacific region.” and “Survey of Information Retrieval - guide to IR, with an emphasis on web-based projects. Includes a glossary, and pointers to interesting papers.” Takeaway: stop words (and, even, by, with, a, on, of, to, an) are function words; what remains are the content words.

7. Normalization: equivalence classes, case folding, lemmatization (s.26-30)

• s.26 is a divider slide: “Normalization”.
• Why normalize (s.27): in Information Retrieval (IR) the indexed text and the query terms must have the same form, e.g. we want to match U.S.A and USA. We define equivalence classes of terms. Alternative: query expansion: enter “window” -> search window, windows; enter “windows” -> search Windows, windows, window. Query expansion is potentially more powerful, but less efficient.
• Normalization via stemming/lemmatization (s.28): converts each token to a standard form, a process usually referred to as stemming or lemmatization. Whether this step is necessary is application-dependent. Effects: reduces the number of distinct types (unique terms) in a corpus and increases the frequency of some individual types (e.g. types and typed -> type); for classification algorithms that take frequency into account this can sometimes make a difference.
• Case folding (s.29): (Concept - Case Folding)
  • Applications like IR: reduce all letters to lower case, since users tend to use lower case (Car, CAR -> car).
  • Possible exception: upper case in mid-sentence, e.g. General Motors vs. general motors; Fed vs. fed (Fed = Federal Reserve); SAIL vs. sail (SAIL = Stanford Artificial Intelligence Language, etc).
  • For Sentiment Analysis and Information Extraction case is helpful: US versus us is important, e.g. “US won a gold medal”; “They like US.” vs. “They like us.”
• Lemmatization - stemming to a root (s.30): converts a word to a root form with no inflectional or derivational prefixes and suffixes.
  • Inflectional suffixes: endings such as -ed, -ing, s; they create different grammatical forms of the same word.
  • Derivational suffixes: endings such as -ism, -ful, -fy; they change the meaning of the word.
  • Examples: “denormalization” is reduced to the stem “norm”; “reapplied”, “applications” -> “apply”.
  • Words with the same core meaning are coalesced. The end result of such aggressive stemming is to reduce the number of types very drastically, making distributional statistics more reliable.
  • Note: the slide’s title merges the terms “lemmatization” and “stemming”; see Concept - Lemmatization and Concept - Stemming.

flowchart LR
    C[Collect documents / corpus<br/>s.13-14] --> N[Text normalization<br/>s.16]
    N --> T[Tokenization<br/>s.18-21]
    N --> W[Normalize word formats<br/>s.27-30]
    N --> SS[Sentence segmentation<br/>s.16]
    T --> SW[Stop word removal<br/>s.24-25]
    W --> CF[Case folding<br/>s.29]
    W --> LS[Stemming / lemmatization<br/>s.28, s.30]
    SW --> F[Numerical features<br/>s.12]
    CF --> F
    LS --> F

flowchart TD
    X["x = string, e.g. ntu@gmail.com"] --> FE[Feature extractor]
    FE --> FV["feature vector phi(x)<br/>1,1,1,1,0,5,0.85"]
    FV --> D["w . phi(x)<br/>weights -1.2,1.4,2.2,0.6,0.5,0.3,0.6"]
    D --> S{sign}
    S -->|"> 0"| P[+1: email]
    S -->|"< 0"| M[-1: not email]
    S -->|"= 0"| Q[? undefined]

Figures & diagrams

• s.3 Supervised framework: Training Data -> ML Model -> $f$; $X$ (Input) enters from the top, $Y$ (Target) leaves at the bottom.
• s.5 Feature extractor: arrow from “ntu@gmail.com” to a 7-row (feature name, value) table.
• s.6 Same table with the value column boxed (dashed) as the feature vector; separate dashed box labelled “feature vector space”.
• s.7 Table of feature names with weights (orange) -1.2, 1.4, 2.2, 0.6, 0.5, 0.3, 0.6.
• s.8-9 Formula slides: weighted sum and sign function with cases +1, -1, ?.
• s.14 Screenshots of the UCI ML Repository table and a Kaggle dataset list.
• s.20 Five tokenizer outputs for “He is in Finland’s capital” (Treebank, WordPunct, Punkt, Whitespace, pattern); takeaway: tokenizer choice changes how ‘s is split.
• s.21 Japanese sentence annotated with Katakana, Hiragana, Kanji, Romaji; takeaway: several scripts in one sentence complicate tokenization.
• s.22 Power-law curve (word probability vs word frequency) with a few frequent words (green head) and a long tail (yellow); takeaway: Zipf’s Law.
• s.23 Google Ngram chart for “life” and “death” (1800-2000) and the tokens/types table.
• s.25 Stop words highlighted in red within two sentences.
• Divider slides without content: s.2, s.11, s.15, s.17, s.26 (blue background, title only).

Key terms

• Concept - Feature Extraction
• Concept - Linear Model
• Concept - Text Preprocessing
• Concept - Corpus
• Concept - Text Normalization
• Concept - Tokenization
• Concept - Word Sense Relations
• Concept - Zipf’s Law
• Concept - Tokens and Types
• Concept - Stopword Removal
• Concept - Case Folding
• Concept - Stemming
• Concept - Lemmatization

Formulas

• Linear model score: $\mathbf{w}\cdot \varphi (x)={\sum }_{j=1}^d{w}_j\varphi (x{)}_j$ (s.8)
• Binary classifier: $f_{\mathbf{w}}(x)=\text{sign}(\mathbf{w}\cdot \varphi (x))$ with $+1$ if $>0$, $-1$ if $<0$, ? if $=0$; $\mathbf{w},\varphi (x)\in {\mathbb{R}}^d$ (s.9)
• Corpus size notation: $N$ = number of tokens, $V$ = set of types, $|V|$ = vocabulary size (s.23)

Likely exam questions

1. What is a feature extractor? Give an example. (s.5) A function that, given input $x$, outputs a set of (feature name, feature value) pairs, e.g. for an email-address string: length>10, contains ”@”, ends with “com”, fraction of alpha.
2. Explain how a linear model makes a binary prediction. (s.8-9) Compute $\mathbf{w}\cdot \varphi (x)={\sum }_j{w}_j\varphi (x{)}_j$; predict +1 if >0, -1 if <0.
3. How are model parameters learned? (s.10) From data: define a loss function and optimize it.
4. Why do we need to preprocess text? (s.12) To turn text into features (numeric columns of a spreadsheet) that data-mining procedures can use; word occurrence is easy, grammatical function is harder.
5. Discuss how documents can be collected and name example corpora. (s.13-14) Web crawler, mail-server logging; Reuters-21578, RCV1 (~810,000 stories), Gutenberg, LDC, UCI repository, Kaggle.
6. What does text normalization comprise? (s.16) Tokenizing words, normalizing word formats to standard forms, segmenting sentences.
7. Discuss the difficulties of tokenization. (s.18-21) Characters like . , : - ’ are context-dependent delimiters (numbers 100,000; Dr.; isn’t; Tess’); hyphenated and multiword items (Hewlett-Packard, San Francisco); language dependence (no spaces in Chinese/Japanese; mixed scripts in Japanese).
8. Distinguish homonymy, polysemy and synonymy. (s.22) Table below.
9. State Zipf’s Law. (s.22) Word frequencies follow a power law: few very frequent words, many rare words.
10. Define tokens and types; what are N and |V|? (s.23) $N$ = number of running words (tokens); $V$ = set of distinct words (types), $|V|$ its size.
11. What are stop words and why remove them? (s.24) Functional words that carry little information; removing them helps methods perform better; list is language-dependent.
12. When is case folding useful and when harmful? (s.29) Useful in IR (users type lower case); harmful for sentiment analysis / information extraction (US vs us, General Motors vs general motors, Fed vs fed).
13. What is the effect of stemming/lemmatization on a corpus? (s.28, s.30) Fewer distinct types, higher frequency of remaining types, more reliable distributional statistics; application-dependent.
14. Compare normalization by equivalence classes with query expansion. (s.27)

	Equivalence classes (normalization)	Query expansion
Idea	Map variants (U.S.A, USA) to one form at index and query time	Expand the entered query into variants (window -> window, windows)
Power	Less powerful	Potentially more powerful
Efficiency	More efficient	Less efficient

Word-relation comparison for question 8 (s.22):

Relation	Form	Meaning	Example
Homonymy	same	different	bank (river / financial institution)
Polysemy	same	related	man (species / male / adult male)
Synonymy	different	same	singer, vocalist

See also Past Exam - Question Bank & Style Guide (for the Machine Learning course style; no Text & Web Mining past-exam topic recorded for this chunk).

Common confusions

• Homonymy vs polysemy: both have the same form; homonyms have unrelated meanings (bank), polysemous words have related meanings (man) (s.22).
• Token vs type: tokens count every running word occurrence ($N$); types count distinct words ($|V|$). Normalization shrinks $|V|$ but not $N$ (s.23, s.28).
• Delimiter vs token: white space is always a delimiter and never a token; ( ) <> ! ? ” are always delimiters but may also be tokens (s.18).
• Stemming vs lemmatization on s.30: the slide titles the topic “Lemmatization - Stemming to a Root” and gives stems like “denormalization -> norm”; stems are not necessarily dictionary words. Inflectional suffixes (-ed, -ing, -s) keep the meaning; derivational suffixes (-ism, -ful, -fy) change it (s.30).
• Feature vector vs weight vector: the feature vector $\varphi (x)$ depends on the input; the weight vector $\mathbf{w}$ is learned from data and is the same for all inputs (s.6-7, s.9-10).
• Case folding is not always good: lower-casing helps IR but destroys information for sentiment analysis / information extraction (s.29).
• Dataset count: s.14 text says 468 datasets while the screenshot header shows “488 Data Sets” (source inconsistency).

Slide coverage

Slide	Content	Covered in
1	Title: Text Preprocessing - from textual information to numerical vector (credits)	Overview
2	Divider: A Simple Text Mining Case	Detailed notes 1
3	Supervised framework diagram	Detailed notes 1; Figures
4	Task: is a string an email address?	Detailed notes 1
5	Feature extraction, feature extractor table	Detailed notes 1; Figures
6	Feature vector notation	Detailed notes 1; Figures
7	Weight vector notation	Detailed notes 1; Figures
8	Linear model, weighted sum	Detailed notes 1; Formulas
9	Linear model, sign function for binary classification	Detailed notes 1; Formulas
10	Learning parameters: data, loss function, optimize	Detailed notes 1
11	Divider: Introduction to Text Preprocessing	Detailed notes 2
12	From text to numerical features	Detailed notes 2
13	Collecting documents; corpora (Reuters, Gutenberg, LDC)	Detailed notes 2
14	Collecting documents; UCI repository, Kaggle	Detailed notes 2; Figures
15	Divider: Text Normalization	Detailed notes 3
16	Text normalization components	Detailed notes 3
17	Divider: Tokenization	Detailed notes 4
18	Tokenization: delimiters and white space	Detailed notes 4
19	Tokenization: ambiguous characters	Detailed notes 4
20	Tokenization issues, NLTK tokenizer comparison	Detailed notes 4; Figures
21	Tokenization: Chinese/Japanese	Detailed notes 4; Figures
22	Word properties, Zipf’s Law	Detailed notes 5; Figures
23	Tokens N and types V, corpus sizes, Ngram chart	Detailed notes 5; Figures
24	Stop words definition, language dependence	Detailed notes 6
25	Stop word examples	Detailed notes 6; Figures
26	Divider: Normalization	Detailed notes 7
27	Normalization: equivalence classes, query expansion	Detailed notes 7
28	Normalization via stemming/lemmatization, effect on types	Detailed notes 7
29	Case folding	Detailed notes 7
30	Lemmatization / stemming to a root, inflectional vs derivational	Detailed notes 7

Previous: (none, first chunk) | Next: 02 Pre-processing - Chunk 02 (s.31-60) | Up: 02 Pre-processing - Index