Interactive Machine Learning

Maria-Florina Balcan

Machine Learning
Image Classification
Document Categorization

Speech Recognition Protein Classification
Branch Prediction

Fraud Detection

Spam Detection2Supervised Classification
Example: Decide which emails are spam and which are important.
Not spam

Supervised classification

spam

Goal: use past emails to produce good rule for future data.
3

Example: Supervised Classification
Represent each message by features. (e.g., keywords, spelling, etc.)

exampleReasonable RULES:
Predict SPAM if unknown AND (money OR pills)
Predict SPAM if 2money + 3pills –5 known > 0label+ + ++- Linearly separable
4

Two Main Aspects in Machine Learning
Algorithm Design. How to optimize?
Automatically generate rules that do well on observed data.

Confidence Bounds, Generalization Guarantees
Confidence for rule effectiveness on future data.

5Supervised Learning Formalization
Classic models: PAC (Valiant), SLT (Vapnik)• X – feature space• S={(x, l)} - set of labeled examples– drawn i.i.d. from distr. D over X and labeled by target concept c*• Do optimization over S, find hypothesis h 2 C.
• Goal: h has small error over D.
err(h)=Prx 2 D(h(x)  c*(x))

hc*• c* in C, realizable case; else agnostic
6Sample Complexity Results
Finite C, realizable

Infinite C, realizable• Agnostic – replace  with 2.
7Supervised Learning

Infinite C, realizable• Lots of work on tighter bounds [e.g., Haussler,Littlestone,Wartmuth’94’;
Bartlett,Bousquet,Mendelson’05; Gine and Koltchinski’06].

• Lower bounds that match upper bounds on worst case distr.
• Sample complex. pretty well understood up to pesky gaps
• Powerful algorithms as well (AdaBoost & SVM)

Classic Paradigm Insufficient Nowadays
Modern applications: m a s s i v e a m o u n t s of raw data.

Only a tiny fraction can be annotated by human experts.

Protein sequences

Billions of webpages

ImagesActive Learning
Data Source
Learning
Algorithm

Expert / Oracle

UnlabeledexamplesRequest for the Label of an Example
A Label for that Example
Request for the Label of an Example

A Label for that Example...
Algorithm outputs a classifier• The learner can choose specific examples to be labeled.
• He works harder, to use fewer labeled examples.

Active Learning
Do unlabeled data,interaction help?
•When, why,by how much?

Foundations lacking a few years ago.

• Significant progress recently• Mostly on sample complexity.

• Still lots of exciting open questions.

Outline of My Talk
• Brief history, disagreement based active learning.
• Aggressive active learning of linear separators.
• Interactive learning more generally.
Interactive learning• Passive learning (sample complexity & algorithms)• Distributed learning (communication efficient protocols)

Can adaptive querying help? Noise-Free Case
• Useful in practice, e.g., Active SVM [Tong & Koller, ICML ‘99]

• Canonical theoretical example [CAL92, Dasgupta04]-+

Active Algorithm•w

Sample with 1/ unlabeled examples; do binary search.

- -+Passive supervised: (1/) labels to find an -accurate threshold.

Active: only O(log 1/) labels. Exponential improvement.

Can adaptive querying help? Noise-Free Case
• Useful in practice, e.g., Active SVM [Tong & Koller, ICML ‘99]

• Canonical theoretical example [CAL92, Dasgupta04]
Passive supervised: (1/) labels to find an -accurate threshold.
Active: only O(log 1/) labels. Exponential improvement.

• Homogeneous linear sep, uniform distribution•

QBC [Freund et al., ’97]•

Active Perceptron [Dasgupta, Kalai, Monteleoni ’05]c*

In general, number of queries needed depends on C and P.

When Active Learning Helps. Agnostic caseA2 the first algorithm which is robust to noise.
[Balcan, Beygelzimer, Langford, ICML’06] [Balcan, Beygelzimer, Langford, JCSS’08]“Region of disagreement” style: Pick a few points at random from thecurrent region of uncertainty, query their labels, throw out hypothesis
if you are statistically confident they are suboptimal.

Guarantees for A2 [BBL’06,’08]:• Fall-back & exponential improvements.
• C – thresholds, low noise, exponential improvement.
• C - homogeneous linear separators in Rd,
D - uniform, low noise, only d2 log (1/) labels.

c*A lot of subsequent work.
E.g., Hanneke’07, DasguptaHsuMonteleoni’07, Wang’09, Friedman’09, Koltchinskii10, BalcanHannekeWortman’08,
BeigelzimerHsuLangfordZhang’10, Hanneke’10, El-Yaniv-Wiener’12, Minsker’12, AilonBegleiterExra’12….
15

A2 first active algo robust to noise [BBL’06,’08]“Disagreement based”: Pick a few points at random from thecurrent region of uncertainty, query their labels, throw out
hypothesis if you are statistically confident they are suboptimal.
Guarantees for A2 [Hanneke’07]:
Disagreement coefficientRealizable case:Linear Separators, uniform distr.:c*16

When Active Learning Helps
Lots of exciting activity in recent years.
••Several specific analyses for realizable case. E.g., linear
separators, uniform distribution•

QBC [Freund et al., ’97]

•Active Perceptron [Dasgupta, Kalai, Monteleoni ’05]

Generic algos that work even in the agnostic case andunder various noise conditions•

A2 [Balcan, Beygelzimer, Langford ’06] [Hanneke’07] [Hanneke’10] [Wang’09]
DKM algo [Dasgupta,Hsu, Monteleoni ’07] [Hanneke ’10]

•Koltchinksi’s algo [Koltchinksi’10]•

Aggressive Active LearningThis talk: C - homogeneous linear seps in Rd, D – logconcave• Realizable: exponential improvement, only O(d log 1/)labels to find a hypothesis with error . [Bounded noise].
• Tsybakov noise: polynomial improvement.
[Balcan, Broder, Zhang, COLT’07] ; [Balcan,Long, COLT’13]

Log-concave distributions: log of density fnc concave• wide class: includes uniform distr. over any convex set,
Gaussian distr., Logistic, etc• played a major role in sampling, optimization, integration,
learning [LV’07, KKMS’05,KLT’09]

Margin Based Active-Learning, Realizable CaseAlgorithm
Draw m1 unlabeled examples, label them, add them to W(1).
iterate k=2, …, s
• find a hypothesis wk-1 consistent with W(k-1).
• W(k)=W(k-1).
• sample mk unlabeled samples x
satisfying |wk-1 ¢ x| · k-1 ;• label them and add them to W(k).
end iterate

Margin Based Active-Learning, Realizable Case
Draw m1 unlabeled examples, label them, add themto W(1).
iterate k = 2, …, s
• find a hypothesis wk-1 consistent with W(k-1).
• W(k)=W(k-1).
• sample mk unlabeled samples x
satisfying |wk-1T ¢ x| · k-1
• label them and add them to W(k).

1

w2
w3

w1

2

Margin Based Active-Learning, Realizable Case
Theorem

If

PX log-concave in Rd.

anditerations ws has error · .

then afterLinear Separators, Log-Concave Distributions
Fact 1(u,v)

uv

Proof idea:• project the region of disagreement in the space given by u and v• use properties of log-concave distributions in 2 dimensions.

Fact 2v

Linear Separators, Log-Concave Distributions

Fact 3Ifuvandv

Linear Separators, Log-Concave Distributions
Fact 3Ifuvandv

E
Proof idea:• project the region of disagreement in the space given by u and v• Note that each x in E has ||x|| ¸ °/¯ =c2

Margin Based Active-Learning, Realizable Case
iterate k=2, … ,s
• find a hypothesis wk-1 consistent with W(k-1).
• W(k)=W(k-1).
• sample mk unlabeled samples x
satisfying |wk-1T ¢ x| · k-1
• label them and add them to W(k).

w
wk-1
w*

Proof Idea
k-1

Induction: all w consistent with W(k) have error · 1/2k;
so, wk has error · 1/2k.
For· 1/2k+1

Proof Ideaw

Under the uniform distr. for

wk-1
w*· 1/2k+1

k-1

Proof Ideaw

Under the uniform distr. for

wk-1
w*

· 1/2k+1

k-1

Enough to ensure

Can do with onlylabels.

Theorem

Passive Learning

Any passive learning algo that outputs w consistent withexamples, satisfies err(w) · ², with proab. 1-±.

• Solves open question for the uniform distr. [Long’95,’03],[Bshouty’09]• First tight bound for poly-time PAC algos for
an infinite class of fns under a general class ofdistributions. [Ehrenfeucht et al., 1989; Blumer et al., 1989]

Theorem

Passive Learning

Any passive learning algo that outputs w consistent withexamples, satisfies err(w) · ², with proab. 1-±.

High Level Idea
• Run algo online, use the intermediate w to track the progress• Performs well even if it periodically builds w using some of theexamples, and only uses borderline cases for preliminaryclassifiers for further training.

• Carefully distribute ±, allow higher prob. of failure in later stages[once w is already pretty good, it takes longer to get examplesthat help to further improve it]

Theorem

Passive Learning

Any passive learning algo that outputs w consistent withexamples, satisfies err(w) · ², with proab. 1-±.

High Level Idea

Margin Based AL, Bounded Noise
Guarantee

Assume PX log-concave in Rd.

Assume that |P(Y=1|x)-P(Y=-1|x)| ¸  for all x.
Assume w* is the Bayes classifier.

ThenThe previous algorithm and proof extend naturally,
and get again an exponential improvement.

Bounded Noise, Exponential improvement
Guarantee

Assume PX log-concave in Rd

Assume that |P(Y=1|x)-P(Y=-1|x)| ¸  for all x.
Assume w* is the Bayes classifier.

ThenThe previous algorithm and proof extend naturally,
and get again an exponential improvement.

Margin Based AL, Summary• Extensions to nearly log-concave distributions, noisy
settings. Matching Lower Bounds.
• Broadens class of pbs for which AL provides exponential
improvement in 1/² (without additional increase on d).
• Interesting implications to passive learning:• First tight bound for a poly-time PAC algo for aninfinite class of fns under a general class of data
distributions. [Balcan-Long, COLT’13]• New algo that tolerates malicious noise at significantly
better levels than previously known even for passive
learning [KKMS’05, KLS’10]; also active (much better label
sample complexity). [Awasthi-Balcan-Long’13]

Important direction: richer interactions withthe expert.
Better Accuracy

Fewer queries

ExpertNaturalinteraction

New Types of Interaction [Balcan-Hanneke COLT’12]
Class Conditional Queryraw data

Classifier

ExpertLabeler

Mistake Queryraw datadog)

catpenguin

Classifierwolf

ExpertLabeler35

Class Conditional & Mistake Queries• Used in practice, e.g. Faces in IPhoto.
• Lack of theoretical understanding.
• Realizable (Folklore): much fewer queries than label requests.

36Class Conditional QueryClass Conditional Queryraw dataClassifier

ExpertLabeler

Folklore Result (Realizable Case):• Run halving algorithm
37Class Conditional & Mistake Queries• Used in practice, e.g. Faces in IPhoto.
• Lack of theoretical understanding.
• Realizable (Folklore): much fewer queries than label requests.

Balcan-Hanneke, COLT’12

38

Formal Model• FindMistake(S,h) based on k CCQs

39

Agnostic Case, Upper BoundI.e., eliminate h when makes at least one mistake in some number
out of several sets chosen at random from U.

• rather than eliminating h for a mistake, as in halving.
40

Agnostic Case, Upper Bound

Proof Sketch• Best h in V survives (does not make mistakes on too many sets).

41

Upper Bound, Agnostic Case

Phase 1: Robust halving algorithm

Phase 2: A simple refining algorithm

We recover the true labels of this unlabeled sample and run ERM.

Class Conditional & Mistake Queries• Used in practice, e.g. Faces in IPhoto.
• Lack of theoretical understanding.
• Realizable (Folklore): much fewer queries than label requests.

Balcan-Hanneke, COLT’12• Adapted to obtain the first agnostic communication efficient in
a distributed learning setting. [Balcan-Blum-Fine-Mansour’COLT12]43

Discussion, Open Directions
Active Learning• Rates for aggressive AL with optimal query complexity
for general settings.
•[BL’13], [BBZ’07], aggressive localization in instance space leads toaggressive localization in concept space; can it be generalized?

• Computationally efficient algos for noisy settings.
(recent progress [BF’13], [ABL’13])

More general queries• Efficient algorithms for CCQs.
• More general/natural queries.
• Shallow/Deep learning strategies.