Machine Learning from Weak Supervision: An Empirical Risk Minimization Approach

Series Page
Title Page
Copyright
Table of Contents
Preface
I. Machine Learning from Weak Supervision
	1. Introduction
		1.1. Machine Learning
			1.1.1. Supervised Learning
			1.1.2. Unsupervised Learning
			1.1.3. Reinforcement Learning
		1.2. Elements of Classification
			1.2.1. Classifiers
			1.2.2. Learning Criteria
			1.2.3. Optimization Algorithms
		1.3. Aspects of Machine Learning
			1.3.1. Logical Learning, Biologically Inspired Learning, and Statistical Learning
			1.3.2. Frequentist Learning and Bayesian Learning
			1.3.3. Generative Classification and Discriminative Classification
			1.3.4. Induction, Deduction, and Transduction
		1.4. Improving Data Collection and Weakly Supervised Learning
		1.5. Organization of This Book
			1.5.1. Weakly Supervised Learning for Binary Classification
			1.5.2. Weakly Supervised Learning for Multi-Class Classification
			1.5.3. Advanced Topics and Perspectives
	2. Formulation and Notation
		2.1. Binary Classification
			2.1.1. Formulation
			2.1.2. Classification Models
				2.1.2.1 Linear-in-input model
				2.1.2.2 Linear-in-parameter model
				2.1.2.3 Kernel model
				2.1.2.4 Neural network model
			2.1.3. Surrogate Losses
			2.1.4. Training Samples
			2.1.5. Regularization
		2.2. Multi-Class Classification
			2.2.1. Formulation
			2.2.2. Surrogate Losses
			2.2.3. Training Samples
	3. Supervised Classification
		3.1. Positive-Negative (PN) Classification
			3.1.1. Formulation
				3.1.1.1 One-sample case
				3.1.1.2 Two-sample case
				3.1.1.3 Comparison
			3.1.2. Theoretical Analysis
				3.1.2.1 Targets of convergence
				3.1.2.2 Measures of convergence
				3.1.2.3 Rademacher complexity
				3.1.2.4 Rademacher complexity bounds
				3.1.2.5 Estimation error bounds
		3.2. Multi-Class Classification
			3.2.1. Formulation
			3.2.2. Theoretical Analysis
				3.2.2.1 Estimation error bounds
				3.2.2.2 Classification calibration
II. Weakly Supervised Learning for Binary Classification
	4. Positive-Unlabeled (PU) Classification
		4.1. Introduction
		4.2. Formulation
		4.3. Unbiased Risk Estimation from PU Data
			4.3.1. General Approach
			4.3.2. Cost-Sensitive Approach
			4.3.3. Convex Approach
		4.4. Theoretical Analysis
			4.4.1. PU Classification
			4.4.2. NU Classification
			4.4.3. Comparisons with PN Classification
				4.4.3.1 Finite-sample comparisons
				4.4.3.2 Asymptotic comparisons
	5. Positive-Negative-Unlabeled (PNU) Classification
		5.1. Introduction
		5.2. Formulation
		5.3. Manifold-Based Semi-Supervised Classification
			5.3.1. Laplacian Regularization
			5.3.2. Implementation
		5.4. Information-Theoretic Semi-Supervised Classification
			5.4.1. Squared-Loss Mutual Information Regularization
			5.4.2. Implementation
		5.5. PU+PN Classification
			5.5.1. PNU and PU+NU Risk Estimators
			5.5.2. PNU vs. PU+NU Classification
			5.5.3. Theoretical Analysis
				5.5.3.1 Estimation error bounds
				5.5.3.2 Variance reduction
		5.6. Experiments
			5.6.1. Datasets
			5.6.2. PNU Risk for Validation
			5.6.3. Comparison with Other Methods
		5.7. Extensions
			5.7.1. Multi-Class Extension
			5.7.2. AUC Maximization
			5.7.3. Matrix Imputation
	6. Positive-Confidence (Pconf) Classification
		6.1. Introduction
		6.2. Related Works
		6.3. Problem Formulation
		6.4. Empirical Risk Minimization (ERM) Framework
		6.5. Theoretical Analysis
		6.6. Implementation
		6.7. Experiments
			6.7.1. Synthetic Experiments with Linear Models
			6.7.2. Benchmark Experiments with Neural Network Models
	7. Pairwise-Constraint Classification
		7.1. Introduction
		7.2. Formulation
			7.2.1. One-Sample Case
			7.2.2. Two-Sample Case
			7.2.3. Comparison of Sampling Schemes
			7.2.4. Pairwise Constraints as Pointwise Data
		7.3. Similar-Unlabeled (SU) Classification
			7.3.1. Classification Risk Estimation
			7.3.2. Minimum-Variance Risk Estimation
			7.3.3. Convex Formulation
			7.3.4. Class-Priors in SU Classification
		7.4. Similar-Dissimilar (SD) and Dissimilar-Unlabeled (DU) Classification
			7.4.1. Classification Risk Estimation
			7.4.2. Interpretation of SD Risk
		7.5. Similar-Dissimilar-Unlabeled (SDU) Classification
		7.6. Theoretical Analysis
			7.6.1. Derivation of Estimation Error Bounds
			7.6.2. Comparison of Estimation Error Bounds
		7.7. Experiments
			7.7.1. Setup
			7.7.2. Illustration of SU Classification
			7.7.3. Comparison of SU Classification with Other Methods
			7.7.4. Comparison of SDU Classification with Other Methods
		7.8. Ongoing Research
	8. Unlabeled-Unlabeled (UU) Classification
		8.1. Introduction
		8.2. Problem Formulation
			8.2.1. Data Generation Process
			8.2.2. Performance Measures
			8.2.3. Relation to Classification with Noisy Labels
		8.3. Risk Estimation from UU Data
			8.3.1. Risk Estimation from One Set of U Data
			8.3.2. Risk Estimation from Two Sets of U Data
				8.3.2.1 Risk estimation
				8.3.2.2 Simplification
				8.3.2.3 Special cases
			8.3.3. Theoretical Analysis
			8.3.4. Experiments
				8.3.4.1 Setup
				8.3.4.2 Benchmark experiments with neural network models
				8.3.4.3 Comparison with other methods
		8.4. Generative Approach
			8.4.1. Analysis of Bayes-Optimal Classifier
			8.4.2. KDE-Based Algorithm
			8.4.3. LSDD-Based Algorithm
			8.4.4. DSDD-Based Algorithm
			8.4.5. Experiments
III. Weakly Supervised Learning for Multi-Class Classification
	9. Complementary-Label Classification
		9.1. Introduction
		9.2. Risk Estimation from CL Data
			9.2.1. Formulation
			9.2.2. Risk Estimation
			9.2.3. Case-Study for Symmetric Losses
			9.2.4. Relation to Classification with Noisy Labels
		9.3. Theoretical Analysis
		9.4. Incorporation of Ordinary-Labels
		9.5. Experiments
			9.5.1. Experiments with CL
			9.5.2. Experiments with CL and OL
		9.6. Incorporation of Multi-Complementary-Labels
			9.6.1. Formulation
			9.6.2. Comparison with Multiple Single CLs
			9.6.3. Unbiased Risk Estimator
			9.6.4. Estimation Error Bound
	10. Partial-Label Classification
		10.1. Introduction
		10.2. Formulation and Assumptions
			10.2.1. Formulation
			10.2.2. Data Generation Assumption
		10.3. Risk Estimation
		10.4. Experiments
		10.5. Proper Partial-Label (PPL) Classification
			10.5.1. Data Generation Assumption
			10.5.2. Risk Estimation
			10.5.3. Theoretical Analysis
IV. Advanced Topics and Perspectives
	11. Non-Negative Correction for Weakly Supervised Classification
		11.1. Introduction
		11.2. Overfitting of Unbiased Learning Objectives
			11.2.1. Binary Classification
			11.2.2. Multi-Class Classification
		11.3. Numerical Illustration
		11.4. Non-Negative Correction
			11.4.1. nnPU Classification
			11.4.2. nnPNU Classification
			11.4.3. nnUU Classification
			11.4.4. nnCL Classification
			11.4.5. ccUU Classification
		11.5. Theoretical Analyses
			11.5.1. Bias and Consistency
			11.5.2. Estimation Error
		11.6. Experiments
			11.6.1. Comparison of PN, uPU, and nnPU Classification
			11.6.2. Comparison of uCL and nnCL Classification
			11.6.3. Comparison of uUU and ccUU Classification
	12. Class-Prior Estimation
		12.1. Introduction
		12.2. Full Distribution Matching
		12.3. Mixture Proportion Estimation
			12.3.1. Estimation Goal and Optimization Goal
			12.3.2. Redefinition of Optimization Goal
			12.3.3. Irreducibility Assumption
			12.3.4. Anchor Set/Point Assumption
			12.3.5. Remarks
		12.4. Partial Distribution Matching
			12.4.1. Formulation
			12.4.2. Differentiable Divergences
			12.4.3. Non-Differentiable Divergences
			12.4.4. Empirical f-Divergence Estimation
		12.5. Penalized L1-Distance Minimization
			12.5.1. Penalized L1-Distance
			12.5.2. Practical Implementation
			12.5.3. Theoretical Analysis
				12.5.3.1 Realizability assumption
				12.5.3.2 Summary of main results
				12.5.3.3 Proofs of main results
				12.5.3.4 On the convergence rate of
		12.6. Class-Prior Estimation with Regrouping
			12.6.1. Motivation
			12.6.2. Practical Implementation
			12.6.3. Theoretical Justification
				12.6.3.1 A formal definition of regrouping
				12.6.3.2 Bias reduction
				12.6.3.3 Convergence analysis
				12.6.3.4 Computationally efficient identification of A*
				12.6.3.5 Approximation of p’pwith a surrogate
		12.7. Class-Prior Estimation from Pairwise Data
	13. Conclusions and Prospects
Bibliography
Index
Series List