Data Distribution

Location:

Redmond, WA

Posted:

November 08, 2012

Contact this candidate

Resume:

Unbiased Online Active Learning in Data Streams

Wei Chu Martin Zinkevich Lihong Li

Microsoft Yahoo! Labs Yahoo! Labs

Redmond, WA, USA Sunnyvale, CA, USA Sunnyvale, CA, USA

***.***@*********.*** ***@*****-***.*** ******@*****-***.***

Achint Thomas Belle Tseng

Yahoo! Labs Yahoo! Labs

Sunnyvale, CA, USA Sunnyvale, CA, USA

********@*****-***.*** *****@*****-***.***

ABSTRACT Keywords

Unlabeled samples can be intelligently selected for labeling Active Learning, Adaptive Importance Sampling, Unbiased-

to minimize classi cation error. In many real-world appli- ness, Bayesian Online Learning, Data Streaming

cations, a large number of unlabeled samples arrive in a

streaming manner, making it impossible to maintain all the

1. INTRODUCTION

data in a candidate pool. In this work, we focus on bi-

Active learning holds the promise of reducing the amount

nary classi cation problems and study selective labeling in

of labeled data in supervised learning required to reach a

data streams where a decision is required on each sample

certain level of performance such as classi cation accuracy.

sequentially. We consider the unbiasedness property in the

Many of the successful applications are for the pool-based

sampling process, and design optimal instrumental distri-

scenario [20], where a static collection of unlabeled data

butions to minimize the variance in the stochastic process.

are given, from which a subset are chosen for labeling. In

Meanwhile, Bayesian linear classi ers with weighted max-

other situations where unlabeled examples arrive sequen-

imum likelihood are optimized online to estimate param-

tially, stream-based active learning [5, 7] is more appropri-

eters. In empirical evaluation, we collect a data stream of

ate. Since the size of the data stream is often large (and

user-generated comments on a commercial news portal in 30

even unbounded) in real-world applications, it is impracti-

consecutive days, and carry out o ine evaluation to compare

cal to store all unlabeled data and then run active learning.

various sampling strategies, including unbiased active learn-

Rather, an online algorithm has to decide, for the current

ing, biased variants, and random sampling. Experimental

unlabeled datum, whether to query its label or not. It is

results verify the usefulness of online active learning, espe-

typically not allowed to query labels for data in the past.

cially in the non-stationary situation with concept drift.

Generally, the subset of data chosen for labeling are biased

in the sense that they do not faithfully represent the orig-

inal distribution of data. Therefore, optimizing a classi er

Categories and Subject Descriptors

based on this biased labeled set is problematic, especially in

G.3 [Probabilities and Statistics]: Probabilistic Algo- problems where the positive and negative classes are not sep-

rithms (including Monte Carlo); I.5.2 [Pattern Recogni- arable. In the literature, importance sampling (IS) has been

tion]: Design Methodology Classi er design and evalua- applied to reweight labeled data to remove the bias (e.g.,

tion [2, 4]). As with most importance-sampling-based methods,

controlling variance is crucial for producing reliable classi-

ers in active learning.

General Terms As a motivating application, consider the detection of abu-

sive user-generated content (UGC) on the Web. Common

Algorithms, Experimentation, Performance

forms of UGC abuse include commercial spam, o ensive lan-

guage, adult content, etc. UGC abuse detection is challeng-

The work was done when WC was with Yahoo! Labs.

ing for many reasons. First, at Yahoo!, UGC is extremely

diverse and Yahoo! receives millions of items a day, render-

ing it impractical for human arbitrators to examine every

posted item. Because abusers can probe the detection sys-

tem to determine what items are posted, they can easily

Permission to make digital or hard copies of all or part of this work for

bypass static, hand-coded detection rules. Machine-learned,

personal or classroom use is granted without fee provided that copies are

automated detection is thus necessary. Second, similar to

not made or distributed for pro t or commercial advantage and that copies

bear this notice and the full citation on the rst page. To copy otherwise, to email spam detection, patterns of abuse evolve over time in

republish, to post on servers or to redistribute to lists, requires prior speci c a possibly adversarial manner. Therefore, the traditional

permission and/or a fee.

train-once-and-deploy mode almost surely fails, as is con-

KDD 11, August 21 24, 2011, San Diego, California, USA.

rmed by our analysis in Section 6. A natural solution to

where i = p(xi ) and B =

(xi Pn 1

tackle these challenges is to periodically retrain an abuse i . Note that i if

i=1

) q (xi )

classi er by including new, publicly visible UGC as train- xi is i.i.d. from p(x).

ing data, whose labels are provided by paid human editors.

2.1 Sampling Distribution

Active learning can be used to reduce the editor s labeling

e orts as new unlabeled data arrive. There is a strong connection between online active learn-

This work has two contributions: we apply an online ac- ing and adaptive importance sampling (AIS) [17]. A popu-

tive learning paradigm [2] in a domain which is not IID, lar approach in AIS nds an optimal q to minimize vari-

risk

and develop a new algorithm using the importance weight- i 2

n,q Ex q Rn,q

ance: q = arg minq Ex q R, where

ing principle. This is the rst paper that applies online

active learning to a truly dynamic problem. Whereas [2] the samples are drawn from q (x). The following propositions

used a sequence of data drawn uniformly at random from ensure the soundness of (3).

the MNIST data set, we try to discriminate between com-

mercial spam and good comments in user-generated content. p(xi )

Proposition 1. (Unbiasedness) If i =, then we

q (xi )

We begin by establishing that the dataset has concept drift.

have:

Then, we show how online active learning is a ected by this

(1) Ex q [ i ] = 1;

drift by comparing its performance on the data in its origi-

(2) Ex q [B] = n;

nal order versus running the algorithm on a shu ed variant

and

of the data. What this paper shows is that online active

(3) Ex q [ i G(xi, yi ; )] = R .

learning is more powerful in real dynamic problems than in

environments where data arrives IID. This analysis is done

Proposition 2. (Asymptotic Variance) For Rn,q in (3),

using the probit model [3] to classify examples. We come up

we have n Rn,q R N (0, q )

with an online update variant based on [15] that can han-

dle weighted examples through an approximation technique. R p(x) 2

(G(x, y ; ) R 2 q (x)dx.

where q =

We also study a time-decay variant of the probit model. q (x)

In brief, Proposition 1 is a direct consequence of the de -

2. PROBLEM SETTINGS

nition of i . Proposition 2 follows from known results for the

Let us denote by X the feature space and by Y the label Delta method [17, 19, 22]. AIS minimizes the variance es-

space of input samples. An unknown distribution over X Y timate q above using q (x) p(x) G(x, y ; ) R . How-

is denoted by p(x, y ), where x denotes a column vector of ever, we do not know y in online active learning when mak-

features and y {+1, 1} in binary classi cation problems. ing label request decisions. G(x, y ; ) could be estimated by

Let p(y x; ) be a predictive model parameterized by .

expected estimate, i.e., G(x; ) = y p(y x; )G(x, y ; ).

To optimize, we need a criterion to evaluate the goodness

R could also be estimated by the current Rn,q . In prac-

of a value of . Usually, the criterion is de ned as

tice, if the expected risk is close to 0, we may simply choose

q (x) p(x) G(x; ) with the estimate above.

R = G(x, y ; )p(x, y )dydx

As a special case, the measurement function G(x, y ; )

in (1) can be chosen as log p(y x; ), and the risk min-

where G(x, y ; ) is a measurement function over samples.

imizer is equivalent to the Maximum Likelihood estimate.

For instance, in the empirical risk minimization (ERM) frame-

For the importance-weighted version (3), the minimizer is

work, G(x, y ; ) is usually a loss function, and the integral

then equivalent to the Maximum Weighted Likelihood esti-

above is approximated by an empirical risk

mate.

Rn = G(xi, yi ; ), (1)

n i=1 3. ONLINE BAYESIAN PROBIT

In the ERM framework, stochastic gradient descent [24]

using n samples drawn i.i.d. from p(x, y ).

is commonly applied to updating the model parameters .

In the setting of online active learning (a.k.a. selective

Given a weighted labeled sample (xi, yi, i ) at time t, the

labeling and selective sampling), we observe unlabeled sam-

update rule is t+1 = t + i G(xi,yi ; ), where t and t+1

ples x from p sequentially, whereas an agent reveals y

upon our request on x. We deliberately select a subset of denote the current and new parameters, respectively, and

the step size. Note that the selection probability i becomes

unlabeled samples for labeling, thus the resulting set of la-

a scaling factor of the step size. It is nontrivial to identify

beled samples might be distributed di erently from p(x).

an appropriate step size and iteration number in stochastic

When the labeled samples are drawn from an instrumen-

gradient descent. Sometimes all labeled samples need be

tal distribution q (x, y ), according to the importance sam-

stored for periodic batch learning.

pling principle, the empirical risk can be evaluated with re-

weighted labeled samples as follows, In this work, we resort to online Bayesian learning to

maintain the posterior distribution of the weight vector in

1 X p (x i, y i )

linear classi ers. For simplicity, we focus on linear mod-

Rn,q = Pn G(xi, yi ; ). (2)

p(xi,yi ) q (x i, y i ) els for problems involving binary classi cation. Denote by

i=1

i=1 q (xi,yi )

w the weight vector of the linear model at time t, and the

Since the instrumental distribution q (x, y ) can be factorized function value is given by x w. The distribution of w is

by p(y x)q (x) in this case, the objective is then simpli ed to modeled as a multi-variate Gaussian distribution with mean

t and covariance t :

Rn,q = i G(xi, yi ; ), (3)

B i=1 p(wt ) = N (w; t, t ). (4)

Often, 0 = 0 and 0 = I are used for initialization. Sup-

pose a labeled sample (xi, yi ) is available for training at time

t. The likelihood function is the probit function de ned as:

P (yi xi, w) = (yi x w), (5)

where (z ) = N (v ; 0, 1) dv is the cumulative distribu-

tion function of the standard Gaussian distribution. By

Bayes theorem, the posterior distribution of w is propor-

tional to the product of the likelihood in (5) and the prior

distribution in (4):

Figure 1: An illustration on predictive probabilities

p(w xi, yi ) P (yi xi, w)N (w; t, t ). (6) (right) in contrast with function values (left).

Unfortunately, the posterior is non-Gaussian. In practice,

the rst two moments of w are often used to construct a

Gaussian approximation. Here, our approximation is based

on a variational approach known as Adaptive Density Fil- The red circles and blue diamonds represent the labeled sam-

ter (ADF) [12, 15]. Given a posterior distribution p, ADF ples of two classes used for training. In the right graph, the

nds a Gaussian approximation that matches the rst two contour curves are indexed with predictive probabilities of

moments of p. Speci cally, let N (w; t+1, t+1 ) be the tar- the class of red circles. In the left graph, the contour curves

get Gaussian, whose parameters { t+1, t+1 } are chosen to are indexed with con dence level of belonging to the class

minimize the Kullback-Leibler divergence: of red circles based on function values only. The two dotted

circles in black indicate two regions of interest where unla-

min KL (yi x w)N (w; t, t ) N (w; t+1, t+1 ) . beled samples come from. One region is about the center

of red circles with predictive probability 0.95, and another

This optimization problem can be solved analytically by mo- region is a bit far away from training samples. In function-

ment matching up to the second order, yielding: value-only prediction, the latter region is also predicted with

probability 0.95 because of the hyper-plane determined by

t+1 = t + ( t xi ) (7)

w, whereas the predictive probability in (9) lowers the con-

t+1 = t ( t xi )( t xi ) (8) dence on the latter region. The advantage comes from

the quadratic term x t x in the denominator, which tends

where

to be large on regions far from training samples. In some

N (z )

yi high-dimensional feature spaces, the di erence on predic-

x t xi + 1 (z )

tive uncertainty could be more signi cant. Even when the

covariance matrix t is constrained to be diagonal, di erent

1 N (z ) N (z )

= +z attributes could have di erent uncertainties.

x t xi + 1 (z ) (z )

To summarize, three critical advantages are identi ed for

online Bayesian learning:

yi x t

with z = i . If the dimension of xi is high, the The step size per example can be computed analyti-

xi t xi +1

cally using ADF, without the need for a line search or

covariance matrix t can be restricted to be diagonal. This

learning rate tuning;

restriction corresponds to the idea of mean- eld approxima-

Consistency in predictive class probabilities, which can

tion; see [9] for a successful application of this method in

be utilized by Bayesian decision theory to nd optimal

a search engine setting. Then, the parameter update above

cuto s for various utility functions;

takes O(d) time on average, where d is the average num-

Model uncertainty is explicitly considered, which makes

ber of non-zero features. Hereafter, we focus on diagonal

active learning more sensible on novel samples, espe-

covariance matrices only.

cially in high-dimensional spaces.

In online active learning, unlabeled samples come in se-

quentially. For an unlabeled sample, we may use the cur-

3.1 Weighted Likelihood

rent classi er s predictive distribution on the label to decide

whether to request its label. Given parameters = { t, t } Online active learning induces a stochastic process that

of the classi er at time t, the predictive distribution for sam- selects unlabeled samples with certain probability for label-

ple x is given by: P (y x; ) = (y x w)N (w; t, t ) dw,

ing. The selected samples come from an instrumental dis-

where (y x w) is the probit likelihood and N (w; t, t ) is tribution q rather than p, the distribution of interest.

We use the weighted likelihood bootstrap sampling proce-

the approximate posterior distribution of w at time t. The

dure [16] to select the samples to be sent for labeling. Sup-

integral can be exactly computed by

pose we obtain a labeled sample (xi, yi, i ) through online

x t

active learning, where i denotes the sampling probability

P (y = +1 x; ) = . (9)

x t x + 1 of xi . The weighted likelihood function is then de ned by

In the ERM framework, class label prediction is based on P (yi xi, w, i ) = P i (yi xi, w) (10)

function value only (e.g., x w or (x w)). To visualize

where i = is the importance weight. Asymptotic

the conceptual di erence between the predictive probability q (xi )

in (9) and the function-value-only prediction, we present a properties of maximum weighted likelihood estimators have

synthetic case in two-dimensional feature space in Figure 1. been studied [22]. In this section, we give approximate up-

date rules coupled with weighted likelihood to update the 1 1

model in an online fashion. The variational approximation 0.9

0.9

0.8

as in (7) and (8) nds an optimal Gaussian approxima-

Probability to Label

0.7

Probability to Label

tion. Now we attempt to nd a Gaussian approximation, 0.8

0.6

parameterized by t+1 and t+1, which is adjusted to the

0.5

2=5

weighted likelihood as in (10). Based on the approxima- 0.7

0.4

b=0.2

2=1

b=0.4

0.3

tion N (w; t+1, t+1 ) and the weight i in weighted likeli- 2

=0.5

b=1

0.6

0.2 b=1.5 2

=0.1

hood [9], we have b=4 2

=0.01

0.1

0.5

t+1 1 = i ( 1 1 )

2 1 0 1 2

2 1.5 1 0.5 0 0.5 1 1.5 2

t+1

t t Function Value Function Value

t+1 t+1 1 t = i ( 1 t+1 1 t ) Figure 2: Label selection probabilities based on

t+1

t t

function value (left) and entropy (right).

Reorganizing terms, we reach the following update rules:

t+1 ( i t + (1 i ) t+1 ) 1 t

t+1 = (11)

t+1 ( i 1 t+1 + (1 i ) 1 t )

t+1

= (12)

t+1

Algorithm 1 Online Active Learning with Bayesian Probit

These rules are in the same spirit of the scaling e ect on step Input: data stream {x1, x2, . . .}, classi er = {, }

size in stochastic gradient descent in the ERM framework. t 0, 0, I

repeat

3.2 Dynamics

t t + 1, Ht p(+1 xt ; ),

So far the model assumes a stationary data distribution

sample U(0,1)

p(x, y ) and then the variance on weights would converge

if x, then x is positive. Similarly, alternative to the AUC was proposed.

if you have seen another example x with a positive label

where x

Contact this candidate