Learning Noise Transition Matrix from Only Noisy Labels
via Total Variation Regularization
Yivan Zhang1,2Gang Niu2

1 The University of Tokyo

Masashi Sugiyama2,1
2 RIKEN AIPInternational Conference on Machine Learning 2021

Outline
1 Overview
2 Background3 Motivation
4 Method
5 Experiments
6 Conclusion

1 / 24

Overview
ProblemNoise transition matrix is important in learning from noisy labels.
However, it is usually unavailable or hard to obtain.
Existing methods often depend on unreliable noisy class-posterior estimation.
Contribution
We characterized the class-conditional label corruption process.
We proposed a conceptually novel method for transition matrix estimation.
Methodology
Make probabilities more distinguishable: total variation regularization
Capture uncertainties during training: Dirichlet posterior update2 / 24

Outline
1 Overview
2 Background3 Motivation
4 Method
5 Experiments
6 Conclusion

3 / 24

Learning from Noisy Labels
Notation
X: input features
Y : true labels
Ye : noisy labels

Assumption
XY

Ye

Class-conditional noise (CCN) assumes that the noisy label Ye is independent of
the input feature X given the true label Y : p(Ye |Y, X) = p(Ye |Y ).
Noise transition matrix Tij = p(Ye = j|Y = i) p(Y = 1|X)
p(Ye = 1|X)
p(Ye = 1|Y = 1) . . . p(Ye = 1|Y = K) 

..
..
..
..
...

=

.
.
.
.
p(Ye = K|X)
p(Ye = K|Y = 1) . . . p(Ye = K|Y = K) p(Y = K|X)
⇓p(Ye |X) = T T p(Y |X)

4 / 24

Noise Transition Matrix
CleanSymmetric

PairwiseGeneralClass-conditional label corruption maps the probability simplex ∆K−1 to aconvex hull Conv(T ) of the rows of the noise transition matrix T .
Outer black triangle: probability simplex ∆2
Inner colored triangle: convex hull Conv(T )5 / 24

Identifiability

Good news: if the ground-truth noise transition matrix T is known, p(Y |X) is
identifiable based on observations of p(Ye |X) [Patrini et al., 2017].
ProblemNoise transition matrix is usually not available [Patrini et al., 2017].
Solution
Learn the noise transition matrix from only noisy labels.

6 / 24

Anchor Points

An instance x is called an anchor point for class i if p(Y = i|X = x) = 1.
Based on anchor points, we can estimate p(Ye |X) to obtain an estimate of T .
p(Ye |X = x) = T T p(Y |X = x) = Ti

ProblemAnchor points are hard to obtain [Xia et al., 2019, Yao et al., 2020].
Solution
Do not rely on a separate set of anchor points.

7 / 24

Overconfidence
Data

Empirical distribution

Estimated distribution

Histogram of entropy
102

Empirical
Estimated

overconfidence

101

0.0

0.2

0.4

0.6

0.8

1.0

overconfidence

102
101
100

0.0

0.2

0.4

0.60.81.0101

100
0.0

0.2

0.4

0.6

0.8

1.0Problem
The estimation of the noisy class-posterior could be unreliable due to theoverconfidence of deep neural networks [Guo et al., 2017, Hein et al., 2019].
Solution
Do not estimate the noisy class-posterior directly using neural networks.
8 / 24

Outline
1 Overview
2 Background3 Motivation
4 Method
5 Experiments
6 Conclusion

9 / 24

Transition Matrix Equivalenceb |X) = V T (U T p(Y |X))
p(Ye |X) = TbT p(Y
.64 .14 .07 1.0 0.0 0.0 p(Y1 |X)
p(Ye1 |X) ep(Y2 |X) = .27 .70 .24 0.0 1.0 0.0 p(Y2 |X) (best)p(Ye3 |X)
.09 .16 .69 0.0 0.0 1.0 p(Y3 |X)




0.7 0.0 0.1 0.9 0.2 0.0 p(Y1 |X)
p(Ye1 |X) e
p(Y2 |X) = 0.3 0.8 0.0 0.0 0.8 0.3 p(Y2 |X)
p(Ye3 |X)
0.0 0.2 0.9 0.1 0.0 0.7 p(Y3 |X)




1.0 0.0 0.0 .64 .14 .07 p(Y1 |X)
p(Ye1 |X) ep(Y2 |X) = 0.0 1.0 0.0 .27 .70 .24 p(Y2 |X) (worst)p(Ye3 |X)
0.0 0.0 1.0 .09 .16 .69 p(Y3 |X)

If the transition matrix can be written as a product of two transition matrices,then there could be infinitely many wrong models due to non-identifiability.

10 / 24

Transition Matrix Decomposition

b Tp
b = V(UTp) = TTp
TV
T = UVb Tp
b T b 2 = TT p
T1 b 1 = T2 pb1Tb2Tb1pb2p

If anchor points exist in the dataset, then the correct model is unique andhas nice properties.
If such a condition does not hold, we do not have consistency guarantees, but
the proposed method may still work empirically.
Note that we do not need to detect anchor points from the dataset.
11 / 24

Transition Matrix as a Contraction Mapping

Key motivation 1
The mapping ∆ → Conv(U ) defined by
p 7→ U T p is a contraction mapping
over the simplex ∆ relative to the total
variation distance [Del Moral et al., 2003]:∀U ∈ T , ∀p, q ∈ ∆,dTV (U T p, U T q) ≤ dTV (p, q)
Probabilities of the correct model are more
distinguishable from each other.

12 / 24

Transition Matrix Estimation

Key motivation 2In addition to the gradient information,
the confusion matrix is also helpful for
estimating the transition matrix.
We have a derivative-free approach thatuses Dirichlet distributions to model thetransition matrix to capture uncertainties
during training.

13 / 24

Outline
1 Overview
2 Background3 Motivation
4 Method
5 Experiments
6 Conclusion

14 / 24

Overview

Our model has two modules:(a) a neural network for predicting p(Y |X)(b) a Dirichlet posterior for the noise transition matrix TThe learning objective also contains two parts:(i) the usual cross-entropy loss for classification from noisy labels(ii) a total variation regularization term for the predicted probability
15 / 24

Total Variation Regularization
We sample a fixed number of pairs to reduce the additional computational cost.

1dTV (p, q) := kp − qk1
2
R(W ) := EE

X1 ∼p(X) X2 ∼p(X)[dTV (p1 , p2 )]where pi := p(Y |Xi ; W ) i = 1, 2p = model(x) # probability [batch_size, num_classes]
idx_1, idx_2 = randint(0, batch_size, (2, num_pairs))
tv = 0.5 * l1_norm(p[idx_1] - p[idx_2], dim=1).mean()
16 / 24

Dirichlet Posterior Update
Inspired by the closed-form posterior update rule for the Dirichlet-multinomial
conjugate, we update the concentration parameters A during training using theconfusion matrix C, where (β1 , β2 ) are fixed hyperparameters.

A(posterior) = A(prior) + C (observation)A ← β1 A + β2 C

y = Categorical(p).sample()C = confusion_matrix(y, y_)A = beta_1 * A + beta_2 * C# predicted labels# confusion matrix# update
17 / 24

Optimization
For each batch of data, we sample a transition matrix from the Dirichlet posterior.

Ti ∼ Dirichlet(Ai ) (i = 1, . . . , K)hi
DKL p(Ye |X) T T p(Y |X; W )L0 (W, T ) := E
X∼p(X)

L(W, T ) := L0 (W, T ) − γR(W )T = Dirichlet(A).sample() # transition matrix
loss = cross_entropy(p @ T, y_) - gamma * tv

18 / 24

Outline1 Overview
2 Background3 Motivation
4 Method
5 Experiments
6 Conclusion

19 / 24

100

50 6100
100

Settings

100
100
100
100

Noise types

100
100
100

CleanSymm.

100

50 6100
100
100
100
100
100
100
100
100

6666666666666666 50 666666666 50 6

666666666 50 6

666666666 50 6666666666 50 6

666666666 50 6

666666666 50 66666666666Pair2

6 50

56 38 658 2156 38 62121 58 2156 38 621 58 2156 38 621 58 2156 38 621 58 2156 38 6

21 58 21

6666666666666666666 50 6666666666 50 6666666666 50 6666666666 50 6666666666 50 666666666

6 50 666666666660 40
60660 4060 404060

21 58 2156 38

38 656

21 58 212151 21147821 58

38237 19 3 1114 1
197 1042 55 5322 122 24

15 3421 23 122513 46 17 1 48 923 121 58 2156 38 660 40

60 40

621 58 2156 38 64060 40

2 14 2 47

21 58 2156 38 660 40

60 40

121 58 2156 38 660 40

60 40

7 49 121 58 2156 38 660 40

2121 58 2156 38 660 40

60 40

Rand.

58 2156 38 660 40

60 40Trid.

56 38 660 40

6 50

60 40

91 1153 10 14 52

21 15322 56
28 22 4351 217 49 11147813 42 14 2 47
61 23 1225386 17 1 48 923 122 122 2415 37 1042 55 591 11(CCE) categorical cross-entropy loss
(MAE) mean absolute error [Ghosh et al., 2017](GCE) generalized cross-entropy loss [Zhang and Sabuncu, 2018]56 38 621 58 21

56 38 6666Rand.

Baselines(Robust) loss functions:
21 58 2156 38

38 660 40Trid.

66 50 66Pair2

Pair

6 50 666 50 656

21 58 212121 58432

3

7 19 3 1114 1253 10 14 52

21 1532192 56

28 22 43

Transition matrix estimations:(Forward) forward correction [Patrini et al., 2017](T-Revision) transition-revision [Xia et al., 2019](Dual-T) dual-T estimator [Yao et al., 2020]
20 / 24

Results
Improved classification performance, measured by accuracy.

CIFAR100(a) Clean
MAE
CCE
GCE
Forward
T-RevisionDual-TTVG
TVD(b) Symm.

11.23(1.02)
7.89(0.67)
70.58(0.29) 42.94(0.47)
57.10(0.85)
48.66(0.58)
70.58(0.28) 44.32(0.64)
70.47(0.26) 46.52(0.57)
70.56(0.28) 55.92(0.60)
70.02(0.30) 57.33(0.42)
69.93(0.21)
52.54(0.45)(c) Pair6.94(1.11)
44.00(0.71)
45.27(0.85)
44.17(0.57)
44.08(0.42)
46.22(0.72)
45.68(0.85)
56.02(0.82)(d) Pair2(e) Trid.

6.60(0.74)
7.45(0.55)
41.37(0.27)
46.55(0.54)
43.67(0.94)
50.98(0.33)
42.07(0.55)
47.48(0.40)
42.01(0.52)
47.59(0.60)
44.74(0.65)
61.68(0.51)
44.38(0.72)
54.23(0.53)
49.18(0.53) 62.45(0.44)(f) Rand.
7.15(0.98)
42.41(0.48)
48.66(0.63)
43.15(0.53)
45.33(0.40)
57.92(0.50)
59.85(0.61)
53.95(0.47)

Improved transition matrix estimation, measured by average total variation.

CIFAR-100(a) Clean(b) Symm.

(c) PairForward0.00(0.00) 48.62(0.11)
39.81(0.03)
T-Revision 0.46(0.05)
31.58(0.46)
39.45(0.03)
Dual-T
3.10(0.08)
17.10(0.18)
33.26(0.20)
TVG
1.59(0.02) 13.11(0.10) 37.79(0.30)
TVD
21.98(0.11) 26.46(0.15) 29.47(0.26)(d) Pair2(e) Trid.

(f) Rand.

43.57(0.04)
40.92(0.07)
49.06(0.10)
42.77(0.06)
40.01(0.09)
39.49(0.26)
33.79(0.26) 23.56(0.43) 22.59(0.23)
38.83(0.34)
30.80(0.51) 16.47(0.18)
31.34(0.30) 23.86(0.22)
35.37(0.30)
21 / 24

Outline
1 Overview
2 Background3 Motivation
4 Method
5 Experiments
6 Conclusion

22 / 24

Summary

Total variation regularization encourages the predicted probabilities to be
more distinguishable from each other.
The proposed method can estimate the transition matrix and learn a classifier
simultaneously.
Under mild assumptions, the proposed method yields a consistent estimatorof the noise transition matrix.

23 / 24

Takeaway

In this problem, the weak supervision is insufficient to identify the true model,i.e., we have a class of observationally equivalent models.
We address this issue by finding characteristics of the true model under realistic
assumptions and introducing a partial order as a regularization.
Such an approach can be used in other weakly supervised learning problems.
24 / 24

Learning Noise Transition Matrix from Only Noisy Labels
via Total Variation Regularization
Yivan Zhang1,2Gang Niu2

1 The University of Tokyo

Masashi Sugiyama2,1
2 RIKEN AIPInternational Conference on Machine Learning 2021

References
Pierre Del Moral, Michel Ledoux, and Laurent Miclo. On contraction properties of markov kernels. Probability
theory and related fields, 126(3):395–420, 2003.
Aritra Ghosh, Himanshu Kumar, and PS Sastry. Robust loss functions under label noise for deep neural networks.
In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pages 1919–1925, 2017.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In
Proceedings of the 34th International Conference on Machine Learning, pages 1321–1330, 2017.
Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf. Why ReLU networks yield high-confidence
predictions far away from the training data and how to mitigate the problem. In Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition, pages 41–50, 2019.
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neuralnetworks robust to label noise: A loss correction approach. In Proceedings of the IEEE Conference on
Computer Vision and Pattern Recognition, pages 1944–1952, 2017.
Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchorpoints really indispensable in label-noise learning? In Advances in Neural Information Processing Systems,pages 6838–6849, 2019.
Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Jiankang Deng, Gang Niu, and Masashi Sugiyama. Dual T:
Reducing estimation error for transition matrix in label-noise learning. In Advances in Neural Information
Processing Systems, pages 7260–7271, 2020.
Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks with noisylabels. In Advances in neural information processing systems, pages 8778–8788, 2018.

1/1