Proofs 2

Loading...

來自 University of California San Diego 的課程

Advanced Algorithms and Complexity

218 個評分

University of California San Diego

Advanced Algorithms and Complexity

218 個評分

課程 5（共 6 門，Specialization 数据结构与算法）

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

從本節課中

Streaming Algorithms (Optional)

In most previous lectures we were interested in designing algorithms with fast (e.g. small polynomial) runtime, and assumed that the algorithm has random access to its input, which is loaded into memory. In many modern applications in big data analysis, however, the input is so large that it cannot be stored in memory. Instead, the input is presented as a stream of updates, which the algorithm scans while maintaining a small summary of the stream seen so far. This is precisely the setting of the streaming model of computation, which we study in this lecture. The streaming model is well-suited for designing and reasoning about small space algorithms. It has received a lot of attention in the literature, and several powerful algorithmic primitives for computing basic stream statistics in this model have been designed, several of them impacting the practice of big data analysis. In this lecture we will see one such algorithm (CountSketch), a small space algorithm for finding the top k most frequent items in a data stream.

Introduction5:23

Heavy Hitters Problem7:33

Reduction 14:35

Reduction 26:30

Basic Estimate 18:04

Basic Estimate 27:14

Final Algorithm 15:27

Final Algorithm 212:57

與講師見面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

So we need to define the no collisions, the small variance, and

the small deviation events.

Let's start with no collisions.

We think of i and r as fixed.

We let the no collisions of r and

i event denote the event that under hash function h r.

None of the head elements,

j distinct from i, collide with i or has to the same bucket.

A note that this definition makes sense for any data item i, whether or

not it belongs to the head or the tail in the stream.

Okay, so why does this event hold with rather high probability?

Well, recall that our hash function was chosen at random, so for

any two distinct elements, i and j.

The probability that they collide under the hash function

is at most one of the number of buckets] that we hash into.

And in fact, it is equal to the number of buckets, but

we only need inequality in this instance.

Good.

Well by the assumption of dilemma.

The number of buckets was chosen to be at least a large constant

times k the number of heavy hitters.

So now, by union bound over o j on the head of the stream,

we have that the no collisions event occurs with reliability.

At least 1- k over b, which is at least seven eights by our assumption.

Great, so let me remind you that we

wrote the variance of our estimator as a contribution from the head of the stream.

And the contribution from the tail and

conditioned on the no collisions event that we just defined.

The first contribution's exactly zero,

because the summation is over the empty set.

So we now know, we now need to handle the second sum.

To that effect, we define the small-variance in it.

Formerly, we say that the small variance of r and

i event occurs if the following conditions do.

If the summation over elements j and the tail of the signal that

are distinct from I and also hash into the same bucket as I.

Under the Rth hash function of their frequency squared is at most eight over b.

The number of R hash buckets times the summation of all J in the tail

of the frequency of J squared.

Well, why does this event hold with high probability?

Well again, recall that our hash function is uniformly random.

So for every pair i n j that are distinct,

the probability that i n j collide is at most 1 over b.

What this means is, that we can take the expectation of the left hand side of this

equation and we can write it as follows.

The expectation of the left-hand side can be written as the summation over all j.

And the tail of the signal that stems from i of fj squared,

times the probability of j and i colliding.

And that is at most one over b of the entire sum.

Okay, so now this is the expectation of the left-hand side.

Why is the left-hand side actually with rather high probability

at most eight times higher than its expectation?

Well, now that's by Markov's inequality..

Markov's inequality says, that for

every non-negative random variable X with mean mu, the probability that X.

Should overs mean by a factor of k is it most one of a k?

So now what we do is, simply apply Markov's inequality to

the left-hand side of our expression with k equal to eight.

Good, so we just proved that the expectation of the left-hand side of our

inequality is it most one over b times the summation.

Over all j in the tail of the signal, their frequency squared.

By Markov's inequality,

the probability that this small variance event occurs is at least 1-1/8.

That is at least seven over eight, so we wrote the variance of our

estimator as the contribution from the head of the stream.

And the contribution from the tail of the stream.

Then, we defined two events.

The no-collisions event and the small-variance event.

Such that conditioned on both of these events.

The first contribution is just zero,

because the summation is over an empty set.

And the second contribution is at most 8 over b times the sum

over all data items j and the tail of the stream of their frequency squared.

At this point, we need the very last piece.

The small deviation event.

The small deviation event occurs by definition

if the squared deviation of our estimator.

Mean is at most eight times as variance.

How about Chebyshev's inequality?

This happens with probability at least seven eights.

Okay, well at this point we actually already have a basic version of our lemma.

From which the full version will follow by standard concentration of equalities.

Now, to state this basic version of the lemma,

it is convenient to introduce a parameter of gamma, defined at the top of the slide.

We'll let gamma be the square root of 1 over b

of the sum of frequency squared all of our frequencies in the tail of the stream.

Now that we have proved that the three events that we defined occurred

simultaneously with probability five over eight at least.

We actually have the following claim, stated as the Lemma on the slide.

If the number of buckets b that we hash into is at least eight times k,

then for every data item i, and for every r.

Between 1 and t, the probability that rth estimate for the frequency fi

is 8 gamma close to the true answer, is at least 5 over 8.

This can be verified by substituting Gamma into our expressions.

Okay, so this is very good.

There are two things that we need to understand.

Well first, the success probability is only five over eight for

a fixed data item i and for a fixed r.

Whereas we need our estimate to work with high probability for all data items i.

We need to fix that and then, we need to relate the precision

guaranteed by this Lemma to the precision that we want to achieve.

That is additive epsilon times f k error term, so

let's fix the success probability first.

And I'm claiming that using standard concentration equalities.

That is Chernoff bounds that I will not get into details here.

One can show starting from the Lemma on the previous slide.

That if we take a sufficiently large logarithmic number of independent copies

of our estimator then the following will be true.

For every data item i with all but say n over 1 to the 4 probability.

The median of our estimators will be 8 gamma close to the true answer.

Now, this follows by standard concentration equalities

turn of bounds but I will not give the formal proof here.

Okay, well, this is very good.

Because we have just been able to show that our estimators succeeds.

That is, gives an answer that is 8 gamma close to the truth.

For every fixed data item i with probably at least one minus one over n to the four.

So, now we can take the union bound over all data items in the universe,

of which there are at most n.

Those that appear in the stream, and conclude that in fact,

our estimator is correct for all data items simultaneously.

With probably at least one minus one over n cubed.

So we know that for all data items now,

with high probability the estimator is 8 gamma close.

To get a proof of our final Lemma.

All we need to understand is how does this 8 gamma

relate to the additive error term of epsilon times f k.

the frequency of the k-th largest element that we wanted to achieve and

this can be verified by direct substitution.

Recall that the number of buck is B was chosen to be appropriately large.

Where large depends on the actual statistics of the stream.

This was the assumption of our lemma.

One can verify it by direct substitution into the expression for gamma.

That 8 gamma turns out to be less than epsilon times fk and

thus concludes the proof of the Lemma.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取