03 Text Classification - Chunk 13 (s.361-381)

Overview

This final part of the deck first closes the ensemble-learning discussion with the Netflix Prize (“From Competition to Industry”), its pitfalls and an “In a nutshell” summary containing the No Free Lunch Theorem (s.361-364). It then gives “Parting Remarks on Text Classification”: classic applications (sentiment/opinion analysis, word sense disambiguation) and design decisions (s.365). Sentiment analysis is shown to need more than bag-of-words (s.366-368), word sense disambiguation is framed as a classification problem with context features (s.369-373), and the last design decisions are how to get labels and how to validate annotations with inter-annotator agreement (worked example, s.374-381).

Detailed notes

1. Ensembles in practice: Netflix Prize (s.361-364)

• Section divider “From Competition to Industry” (s.361).
• Netflix Competition (s.362): screenshot of the (COMPLETED) Netflix Prize leaderboard. Two comments beside it:
  1. The winning solution is a final combination of 107 algorithms;
  2. These are not fully implemented (in production).
• Some possible pitfalls (s.363): exponentially increasing training times and computational requirements; increased demand on infrastructure to maintain and update these models.
• In a nutshell (s.364):
  • Concept - No Free Lunch Theorem: there is no one algorithm that is always the most accurate.
  • Efforts should focus on obtaining base models that make different kinds of errors, rather than highly accurate base models.
  • Build weak learners that are at least more accurate than random guessing.
  • “Keep trying (experimenting, tuning, etc.)!”
• See Concept - Netflix Prize.

2. Parting remarks: outline (s.365)

• Classical applications of text classification: sentiment and opinion analysis; word sense disambiguation.
• Some design decisions in text classification.

3. Sentiment analysis (s.366-368)

• The sentiment expressed in a text = the author’s subjective or emotional attitude towards the central topic of the text (s.366).
  • Consumer reviews: sentiment is targeted at a product/service and may align with a 1-5 star rating (Pang, Lee and Vaithyanathan 2002).
  • Political statements: sentiment may reflect a favorable or unfavorable view toward a proposed policy (Thomas, Pang and Lee 2006).
• Sentiment analysis is a classical application of text classification, typically approached with a bag-of-words classifier (Concept - Bag of Words, Concept - Sentiment Analysis).
• Beyond the bag-of-words (s.367): some linguistic phenomena break bag-of-words. Examples (1): (a) “That’s not bad for the first day.” (b) “This is not the worst thing that can happen.” (c) “It would be nice if you acted like you understood.” (d) a long film review that praises the film (“brilliant”, “first grade”, “happy, wonderful”, “beautiful”, “fascinating”, “great plot”) and then turns with “however”, “the film is a failure.” (Pang et al. 2002). The slide asks “How would you handle these cases?” (no answer given on the slide). Implied issues: negation (a, b), hypothetical/irrealis statements (c), discourse contrast (d). The slide itself does not name these categories.
• Related classification problems (s.368):
  • Subjectivity: does the text convey factual or subjective content?
  • Stance classification: given a set of possible positions, or stances, which is being taken by the author?
  • Targeted sentiment analysis: what is the author’s attitude towards several different entities? Example (2): “The drink was good, but the meat was rotten.”
  • Emotion classification: given a set of possible emotional states, which are expressed by the text?
  • Many applications: commercial products and research in digital humanities and computational social sciences (Jockers 2015; Miller et al. 2011).
  • See Concept - Sentiment Analysis Related Tasks.

4. Word sense disambiguation (WSD) (s.369-373)

• Headlines (3) (s.369): (a) “Kids make nutritious snacks” (b) “Milk drinkers turn into powder” (c) “Man struck by lightning faces battery charges” - humorous ambiguity (source: UPenn headlines page). The slide does not explain the ambiguities.
• Word senses (s.370): many words have multiple senses. The verb appeal:
  • appeal^1: take a court case to a higher court for review
  • appeal^2, invoke: request earnestly (something from somebody)
  • attract, appeal^3: be attractive to
• Word sense disambiguation = the problem of identifying the intended word sense in a given context. Formally, senses are properties of lemmas (uninflected word forms) and are grouped into synsets (synonym sets); synsets are collected in WordNet (Concept - Word Sense Disambiguation, Concept - WordNet and Synsets, Concept - Lemmatization).
• WSD as classification (s.371-372): how to tell living plants from manufacturing plants? Context. Examples (4): (a) “Town officials are hoping to attract new manufacturing plants through weakened environmental regulations.” (b) “The endangered plants play an important role in the local ecosystem.”
  • s.372 adds the feature function: $f((plant,\text{The endangered plants play an ...}),y)=\{(the,y):1,(endangered,y):1,(play,y):1,(an,y):1,\dots \}$ - i.e. the context words are bag-of-words features, each paired with the label $y$ (the sense). The target word is the instance, the sense is the class label.

5. Design decisions: getting labels (s.373-374)

• s.373 [slide title “Getting labels”]: text classification relies on large datasets of labeled examples. Two main ways to get labels:
  • Metadata sometimes tell exactly what we want to know: did the Senator vote for the bill? how many stars did the reviewer give? was the request for free pizza accepted? (Althoff 2014).
  • Otherwise labels must be annotated, by experts or by novice “crowdworkers”.
• See Concept - Getting Labels.

6. Validating annotations: inter-annotator agreement (s.374-381)

• s.374: annotations are validated by computing inter-annotator agreement: how likely are two annotators to choose the same label for an instance? How likely would this be if their labels were randomly shuffled?
• Worked example (s.375-381): Asha (A) and Boris (B) rate 100 jokes “funny”/“not funny” (table below).
• Observed agreement: 75% (s.375) = (70+5)/100.
• Chance agreement (s.376-380, built up step by step with highlighting):
  • 70+20 = B says funny (90 of 100) … s.377 highlights these, 70+5 = A says funny (75 of 100) (s.378), 5+5 = B says not funny (10 of 100) (s.379), 20+5 = A says not funny (25 of 100) (s.380).
  • $\mathrm{Pr}(\text{agree})=\frac{70+20}{100}\times \frac{70+5}{100}+\frac{5+5}{100}\times \frac{20+5}{100}=27/40+1/40=70\%$ (s.381).
• The slide stops at chance agreement = 70%; it does not compute kappa on the slides.

Added context

Observed 75% vs chance 70% gives Cohen’s kappa $\kappa =\frac{p_o-p_e}{1-p_e}=\frac{0.75-0.70}{0.30}\approx 0.17$: only slight agreement beyond chance. The kappa formula is not shown in these slides (the “random shuffle” idea on s.374 is exactly what $p_e$ models).

Figures & diagrams

• s.361: plain blue divider, text “From Competition to Industry”.
• s.362: screenshot of Netflix Prize leaderboard (stamped COMPLETED). Columns: Rank, Team Name, Best Test Score, % Improvement, Best Submit Time. Grand Prize RMSE = 0.8567, winning team BellKor’s Pragmatic Chaos. Rank 1 BellKor’s Pragmatic Chaos 0.8567 (10.06%, 2009-07-26 18:18:28); 2 The Ensemble 0.8567 (10.06%, 18:38:22, i.e. 20 min later); 3 Grand Prize Team 0.8582 (9.90); 4 Opera Solutions and Vandelay United 0.8588 (9.84); 5 Vandelay Industries! 0.8591 (9.81); 6 PragmaticTheory 0.8594 (9.77); 7 BellKor in BigChaos 0.8601 (9.70); 8 Dace 0.8612 (9.59). Takeaway: top teams are blends/ensembles with near-identical scores; the winner was a combination of 107 algorithms.
• s.363-364, 365-366, 369-371, 373-374: text-only slides (no figures).
• s.367-368: text-only with numbered linguistic examples.
• s.372: formula for the WSD feature function (see Formulas); shows context words as features paired with label $y$.
• s.375-381: $2\times 2$ contingency table of Asha vs Boris; red highlights on s.377-380 mark which cells enter each factor of the chance-agreement formula.

	A = funny	A = not funny
B = funny	70	20
B = not funny	5	5

flowchart TD
    A[Text classification design decisions] --> B[Where do labels come from?]
    B --> C[Metadata: stars, votes, accepted request]
    B --> D[Annotation: experts or crowdworkers]
    D --> E[Validate: inter-annotator agreement]
    E --> F[Observed agreement p_o]
    E --> G[Chance agreement p_e from marginals]
    F --> H[Compare p_o vs p_e]
    G --> H

flowchart LR
    W[ambiguous word: plant] --> X[context words as features]
    X --> Y{classifier f}
    Y --> S1[sense 1: living plant]
    Y --> S2[sense 2: factory]

Key terms

• Concept - No Free Lunch Theorem
• Concept - Netflix Prize
• Concept - Sentiment Analysis (existing, appended)
• Concept - Sentiment Analysis Related Tasks (subjectivity, stance, targeted sentiment, emotion)
• Concept - Bag of Words (existing, appended)
• Concept - Word Sense Disambiguation
• Concept - WordNet and Synsets
• Concept - Getting Labels
• Concept - Inter-Annotator Agreement

Formulas

• WSD feature function (s.372): $f((plant,\text{The endangered plants play an ...}),y)=\{(the,y):1,(endangered,y):1,(play,y):1,(an,y):1,\dots \}$
• Observed agreement (s.375): $p_o=\frac{70+5}{100}=75\%$
• Chance agreement (s.376-381): $\mathrm{Pr}(\text{agree})=\frac{70+20}{100}\cdot \frac{70+5}{100}+\frac{5+5}{100}\cdot \frac{20+5}{100}=\frac{27}{40}+\frac{1}{40}=70\%$
• (Added context) $\kappa =\frac{p_o-p_e}{1-p_e}$

Likely exam questions

Style per Past Exam - Question Bank & Style Guide (short “discuss / describe / explain” answers).

1. State the No Free Lunch Theorem as discussed in class. There is no one algorithm that is always the most accurate (s.364).
2. What should be the focus when building an ensemble? Base models that make different kinds of errors rather than highly accurate base models; weak learners better than random guessing (s.364).
3. Discuss the pitfalls of the Netflix-winning ensemble. It combined 107 algorithms and was not fully implemented; training time and computational needs grow exponentially, and infrastructure demands for maintaining/updating the models increase (s.362-363).
4. Why is bag-of-words insufficient for sentiment analysis? Give examples. Negation (“That’s not bad for the first day”), hypothetical statements (“It would be nice if you acted like you understood”), and contrast with “however” in a review that sounds positive but ends “the film is a failure” (s.367).
5. Define sentiment and give two settings. The author’s subjective/emotional attitude towards the central topic; reviews (1-5 stars) and political statements (favorable/unfavorable toward a policy) (s.366).
6. Name four problems related to sentiment analysis and define each. Subjectivity (factual vs subjective), stance classification (which position), targeted sentiment (attitude to different entities, e.g. “The drink was good, but the meat was rotten”), emotion classification (which emotional states) (s.368).
7. What is word sense disambiguation and how can it be cast as classification? Identifying the intended sense of a word in context; instance = target word + context, label = sense, features = context words paired with the label (s.370-372).
8. Distinguish lemma, sense and synset. Senses are properties of lemmas (uninflected forms); senses are grouped in synsets (synonym sets), collected in WordNet (s.370).
9. How can labels be obtained for a text classification dataset? Metadata (stars, votes, acceptance) or annotation by experts/crowdworkers (s.373).
10. Compute observed and chance agreement for the Asha/Boris table. Observed = (70+5)/100 = 75%; chance = 0.9x0.75 + 0.1x0.25 = 70% (s.375-381); the agreement is only slightly above chance.

Common confusions

• Observed agreement vs chance agreement: 75% looks high but 70% would be expected by chance when annotators often say “funny”; chance uses marginal probabilities (row/column totals), not 50%.
• Both annotators’ “funny” totals: B funny = 70+20 = 90 (row), A funny = 70+5 = 75 (column); the chance term multiplies these, plus the “not funny” marginals.
• Lemma vs word form: senses belong to lemmas (uninflected), not inflected forms.
• Weak learner vs accurate base model: ensembles want diverse errors and just better-than-random learners, not individually best models.
• No Free Lunch does not say all algorithms are equal everywhere; it says none is always best.
• Sentiment target: sentence-level sentiment can mix targets (“drink good, meat rotten”), so one document label is not enough (targeted sentiment).

Slide coverage

Slide	Content	Covered in
361	Divider “From Competition to Industry”	1
362	Netflix Competition leaderboard; 107 algorithms; not fully implemented	1, Figures
363	Possible pitfalls: training time, infrastructure	1
364	In a nutshell: No Free Lunch, diverse errors, weak learners	1
365	Parting remarks outline	2
366	Sentiment analysis definition, reviews, politics, bag-of-words	3
367	Beyond bag-of-words examples (1a-d)	3
368	Related problems: subjectivity, stance, targeted, emotion	3
369	WSD headlines (3a-c)	4
370	Word senses of appeal; lemmas, synsets, WordNet	4
371	WSD as classification: plants (4a-b)	4
372	WSD feature function f	4, Formulas
373	Getting labels: metadata vs annotation	5
374	Validating annotations: inter-annotator agreement	6
375	Asha/Boris table, observed agreement 75%	6
376	Chance agreement formula	6
377	Highlight 70+20	6
378	Highlight 70+5	6
379	Highlight 5+5	6
380	Highlight 20+5	6
381	Result 27/40 + 1/40 = 70%	6

Previous: 03 Text Classification - Chunk 12 (s.331-360) | Next: none (last chunk of deck) | Up: 03 Text Classification - Index