Understanding Dataset Difficulty with 𝓥-Usable Information

Kawin Ethayarajh¹, Yejin Choi^,3, Swabha Swayamdipta²� ¹Stanford University | ²AI2 | ³P.G.A School of CS, UW

ICML 2022

Presented by

Pritam S. Kadasi

ICML 2022�Outstanding Paper

12 April, 2023

Introduction

2

Dataset

How difficult it is?

What is difficulty?

How do we measure difficulty?

Models vs. Humans

3

I’m here

Ref: PapersWithCode: https://paperswithcode.com/sota/natural-language-inference-on-multinli

Probability

​

Random Event (rolling a die) → Random Variable (X):

→ Random Variable (Y):

​

P(X): Probability associated with random variable.

4

Represents any number that comes up on the die.

Represents even number that comes up on the die.

represents outcome of a random event

Information theory

• The basic intuition behind information theory is that learning that an unlikely event has occurred is more informative than learning that a likely event has occurred.

​

• sun rose this morning OR there was a solar eclipse this morning

5

Ref: https://github.com/janishar/mit-deep-learning-book-pdf/blob/master/chapter-wise-pdf/%5B7%5Dpart-1-chapter-3.pdf

Information Content

• Likely events should have low information content, and in the extreme case, events that are guaranteed to happen should have no information content whatsoever.
• Less likely events should have higher information content.
• Independent events should have additive information. For example, finding out that a tossed coin has come up as heads twice should convey twice as much information as finding out that a tossed coin has come up as heads once.
• I(2H) = 2*I(1H)

6

Ref: https://github.com/janishar/mit-deep-learning-book-pdf/blob/master/chapter-wise-pdf/%5B7%5Dpart-1-chapter-3.pdf

H(X,Y) = H(X) + H(Y)�[additivity of information]

Information Content

• Likely events should have low information content, and in the extreme case, events that are guaranteed to happen should have no information content whatsoever.
• Less likely events should have higher information content.

7

Ref: https://github.com/janishar/mit-deep-learning-book-pdf/blob/master/chapter-wise-pdf/%5B7%5Dpart-1-chapter-3.pdf

Information Content

8

Information Content

9

𝑦 = - log(𝑥)

10

Entropy

H(X) = E[ − log P(𝑥)]

​

11

Entropy

• Shannon defined the entropy Η of a discrete random variable X which takes values in the alphabet 𝓧 and is distributed according to p : 𝓧 → [0, 1] such that p(𝑥) ≔ P[X = 𝑥]

​

12

Ref: https://en.wikipedia.org/wiki/Entropy_(information_theory)

Intuitively, it tells how unpredictable a random variable is

Entropy

13

Relative Entropy or KL Divergence

14

Ref: https://github.com/janishar/mit-deep-learning-book-pdf/blob/master/chapter-wise-pdf/%5B7%5Dpart-1-chapter-3.pdf

Mutual Information

• It is a quantity that measures a relationship between two random variables that are sampled simultaneously.
• It measures, how much information is communicated on average in one random variable about another
• It tells about the reduction in uncertainty due to another random variable.

15

Ref:

• https://people.cs.umass.edu/~elm/Teaching/Docs/mutInf.pdf
• http://staff.ustc.edu.cn/~cgong821/Wiley.Interscience.Elements.of.Information.Theory.Jul.2006.eBook-DDU.pdf

Mutual Information

How much does one random variable tell about another?

• Case 1: Dependent events → has mutual information
• X represents the roll of a fair 6-sided die, and
• Y represents whether the roll is even (0 if even, 1 if odd).

​

• Case 2: Independent events → has no mutual information
• X represents the roll of one fair die, and
• Z represents the roll of another fair die

16

Ref: https://people.cs.umass.edu/~elm/Teaching/Docs/mutInf.pdf

Mutual Information

The mutual information I(X; Y) is the relative entropy between the joint distribution p(𝑥, 𝑦) and the product distribution p(𝑥)p(𝑦).

​

​

17

Ref: http://staff.ustc.edu.cn/~cgong821/Wiley.Interscience.Elements.of.Information.Theory.Jul.2006.eBook-DDU.pdf, P20

Mutual Information (Cont.)

18

Ref: http://staff.ustc.edu.cn/~cgong821/Wiley.Interscience.Elements.of.Information.Theory.Jul.2006.eBook-DDU.pdf, P20

Mutual Information (Cont.)

19

Ref: http://staff.ustc.edu.cn/~cgong821/Wiley.Interscience.Elements.of.Information.Theory.Jul.2006.eBook-DDU.pdf, P21

Mutual Information and Entropy

20

Ref: http://staff.ustc.edu.cn/~cgong821/Wiley.Interscience.Elements.of.Information.Theory.Jul.2006.eBook-DDU.pdf, P21

Tensorflow Playground

21

𝓥-entropy

​

• Consider model family 𝓥 which can be trained to map X to its label Y
• Now, translate the text of X to complex grammar, it would be harder to predict Y given X using 𝓥
• So, how do we measure this difficulty?

22

𝓥-entropy

​

By using shannon mutual information I(X;Y)?

• NO, as mutual information would not change even after X is encrypted (translated) as it allows for unbounded computation including any need to decrypt the text.
• Intuitively, the task is easier when X is unencrypted because the information it contains is usable by 𝓥
• When X is encrypted, the information still exists but becomes unusable, this quantity is called 𝓥-usable information

23

𝓥-entropy

24

Maximizes the log-likelihood of label data without input

Maximizes the log-likelihood of label data given input

𝓥-entropy (Cont.)

So, how do we maximize the log-likelihood with and without input?

• Training with the cross-entropy loss finds the 𝑓 ∊ 𝓥 that maximizes the log-likelihood of Y given X
• Thus, H_𝓥(Y | X) can be easily computed by standard training or by finetuning a pre-trained model.
• We estimate H_𝓥(Y) by training or finetuning another model where X is replaced by ∅, intended to fit the label distribution.
• As such, computing 𝓥-information involves training or finetuning only two models.

25

𝓥-Usable information

26

Measuring Pointwise Difficulty

• Measures 𝓥-information for individual instances.

​

​

27

Implications

𝓥-usable information allows us to compare

• different models 𝓥 by computing I_𝓥 (X → Y) for the same X, Y
• different datasets {(𝑥, 𝑦)} by computing I_𝓥(X →Y) for the same 𝓥
• different input variables X_i by computing I_𝓥(X_i → Y) for the same 𝓥 and Y

28

𝓥-Usable information in practice

• Model performance tracks 𝓥-information.
• 𝓥-information is more sensitive to over-fitting than held-out performance.
• Different datasets for the same task can have different amounts of 𝓥-usable information.

29

30

31

PVI Vs. PMI

PVI is to 𝓥-information what PMI is to Shannon information.

32

Algorithm for calculating 𝓥-information

33

Implications

PVI allows us to compare

• different instances (𝑥, 𝑦) by computing PVI(𝑥 →𝑦) for the same X, Y, 𝓥
• different slices or subsets of the data by computing the average PVI over instances in each slice

34

PVI in Practice

• PVI can be used to find mislabelled instances.
• The PVI threshold at which predictions become incorrect is similar across datasets.
• PVI estimates are highly consistent across models, training epochs, and random initializations.
• Cross-Epoch correlation: The correlation is high (r > 0.80 during the first 5 epochs), suggesting that when an instance is easy(difficult) early on, it tends to remain easy(difficult)
• Cross-Seed Correlations: The correlation is high (r > 0.87), suggesting that what a model finds difficult is not due to chance.

35

36

PVI estimates are highly consistent across models

37

PVI estimates are highly consistent across human annotators

38

Uncovering Dataset Artefacts

• Input Transformations
• Slicing Datasets
• Token-level Artefacts
• Conditioning Out Information

39

Uncovering Dataset Artefacts

• Input Transformations
• Slicing Datasets

40

Input Transformations

• Approach involves applying different transformations 𝜏_i(X) to isolate an attribute a, followed by calculating I_𝓥(𝜏_i(X) → Y) to measure how much information (usable by 𝓥) the attribute contains about the label.
• Given that a transformation may make information more accessible (e.g., decrypting some encrypted text, it is possible for I_𝓥(𝜏_i(X) → Y) ≥ I_𝓥(X → Y), so the latter shouldn’t be treated as an upper bound.

41

Some transformations for SNLI

• shuffled (shuffle tokens randomly)
• hypothesis-only (only include the hypothesis)
• premise-only (only include the premise)
• overlap (tokens in both the premise and hypothesis)

42

Transformations Results

• Token identity alone provides most of the usable information in SNLI.
• Hate speech detection might have lexical biases.
• In DWMW17, the text contains 0.724 bits of BERT-usable information about the label.
• Additionally, if one removed all the tokens, except for 50 (potentially) offensive ones — comprising common racial and homophobic slurs — from the input post hoc, there still remains 0.490 bits of BERT-usable information.
• In other words, just 50 (potentially) offensive words contain most of the BERT-usable information in DWMW17

43

Transformations Results

• Hate speech detection might have lexical biases.
• In DWMW17 dataset,
• I_𝓥 = 0.724 bits
• After removing all the tokens except 50 (potentially) offensive tokens from the dataset: I_𝓥 = 0.490 bits
• In other words, just 50 (potentially) offensive words contain most of the BERT-usable information in DWMW17
• Token identity alone provides most of the usable information in SNLI.

44

In DWMW17 dataset,

• Ex-1: I don't want my child going to school with [LGBTQ+ community], they are all perverts.
• PVI: 0.724 bits
• After removing all the tokens except 50 (potentially) offensive tokens from the dataset:
• Ex-1 → Ex-2: perverts.
• PVI: 0.490 bits
• In other words, just 50 (potentially) offensive words contain most of the BERT-usable information in DWMW17

45

46

Slicing Datasets

• Certain attributes are more useful for certain classes.
• Certain subsets of each class are more difficult than others.

47

Certain attributes are more useful for certain classes.

• Note: 𝓥-information = mean PVI (entire dataset)
• Comparing the usefulness of an attribute across classes can be useful for identifying systemic annotation artefacts.
• Created slices of data with respect to classes.
• Calculate mean PVI for these slices and compare it.
• Ex: the premise-hypothesis overlap contains much more BERT usable information about the ‘entailment’ class than ‘contradiction’ or ‘neutral’.

48

49

Certain subsets of each class are more difficult than others

​

​

• We bin the examples in each SNLI class by the level of hypothesis-premise overlap and plot the average PVI.
• We see entailment instances with no hypothesis-premise overlap are the most difficult (i.e., lowest mean PVI).
• While contradiction instances with no overlap are the easiest (i.e., highest mean PVI).
• We can use dataset cartography and comparing the subsets with the PVI to dig more into subsets of data.

50

Certain subsets of each class are more difficult than others

51

52

Key Takeaways

• We can estimate difficulty of the dataset, slices of the dataset, even an individual instance.
• We can isolate attributes instances in the dataset/individual instances which are leading to difficulty.
• Higher the 𝓥-information, easier the dataset.
• In dataset cartography, we cannot say why an individual instance is difficulty/easy/ambiguous, on basis of what parameters.
• We cannot quantify difficulty of an instance/dataset in dataset cartography.

53

References

• A Theory of Usable Information Under Computational Constraints: https://arxiv.org/abs/2002.10689
• https://github.com/janishar/mit-deep-learning-book-pdf/blob/master/chapter-wise-pdf/%5B7%5Dpart-1-chapter-3.pdf
• https://people.cs.umass.edu/~elm/Teaching/Docs/mutInf.pdf
• http://staff.ustc.edu.cn/~cgong821/Wiley.Interscience.Elements.of.Information.Theory.Jul.2006.eBook-DDU.pdf
• https://people.cs.umass.edu/~arya/courses/650/lecture2.pdf
• https://en.wikipedia.org/wiki/Entropy_(information_theory)

54

Thank You !!!

55

Token-level Artefacts

How do we know whether a token is helpful in deciding the label?

• Token-level signals and artefacts can be discovered using leave-one-out.
• we compute the change in the V-information estimate after removing t, which yields modified input 𝑥_¬t. We use the same model g’ but evaluate only on a slice of the data, D_C,t, which contains the token t and belongs to the class C of interest. This simplifies to measuring the increase in conditional entropy.

56