Name: 6 6 Computational Advertising Bipartite Graph Matching 24 47
Uploaded: 2017-08-24T17:01:19.000Z
Duration: 24 min 48 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Welcome back to Mining of Massive Datasets.

In today's lecture we're going to look at a new topic, Online Algorithms.

And we're going to look at a particular application of Online Algorithms,

The kind of advertising that you see on the web or on mobile.

Now, in the classic model of algorithms, which we're all familiar with,

you get to see the entire input and then you compute some function of it.

For example, you may be given a set of data points and

you might want to compute clusters on those data points.

In this context, we called a classic model of algorithms an offline algorithm.

An offline algorithm has access to its enti, entire input dataset.

The kind of algorithm that we're going to look at in today lect, today's lecture,

called Online Algorithms, don't get to see the entire data set at one one time.

They get to see the input one piece at a time.

They don't see all the input and yet, as they see a partial input they have to

make some kind of irrevocable deficient along the way.

They produce part of the output even when they've seen only part of the output.

And it's kind of similar to the data stream model but it's not identical.

There are certain subtle differences that'll become apparent as we go along.

We're going to start our discussion of Online Algorithms by looking at

a very simple problem called Bipartite Matching.

So, the Bipartite Matching problem, starts with the bipartite graph.

So, here we have a bipartite graph with, with two sets of nodes or vertices.

We've labelled one set of nodes Boys, and the other set of nodes Girls.

We could have equally well labeled them something else.

But it just so happens to be convenient to be, to label them Boys and

And in this case, let's say the edges between between the the vertices

signify compatibility between Boys and Girls.

And the goal of the Bipartite Matching problem is to

match as many compatible pairs of Boys and Girls as possible.

That is, find as many pairs of nodes as possible, subject to

the constraint that those pair, those pairs of nodes are connected by an edge.

For example, here we've found three pairs of nodes 1,a, 2,b, and 3,d.

And in each case, this is a compatible pair,

where it's an edge between between each pair of nodes that we have picked.

And notice that once you have picked 1,a, 2,b, and 3,d will be

unable to do anything with Boy 4 or Girl c because there is no edge between them.

And there are no other Boys or Girls that are available.

The only edge that Boy 4 has is to Girl a but Girl a is already paired with Boy 1.

So in this case we produced a matching of cardinality 3 because we

found 3 pairs then that it could match up.

So in the the cardinality of the matching in this case there's, is 3.

Now with the same graph, it turns out that we can actually, do better.

We can find a matching of cardinality 4 if we are a little bit more clever.

And here is an example of a matching of cardinality 4.

And once we do that, we've matched, every Boy with some Girl, and

And this is what's called a perfect matching because it

matches every node to some other node in the in the graph.

To clarify our terminology perfect matching is a matching that

matches every vertex in the graph, or every node in the graph.

And maximum matching is a matching that is as large as possible for the given graph.

For example, in this case the matching M is both a perfect matching and

Every perfect matching has to be maximum because you can't,

obviously, find a matching that's larger than perfect.

however, there could be graphs where there is no perfect matching, but you,

but there's always a maximum matching which is the best that you can do for for

So in this case, the maximum matching has cardinality 4.

Whereas the earlier matching that we found had just cardinality 3,

Now, the goal of the bipartite matching problem is to find the maximum matching or

find a maximum matching, since the maximum matching is not necessarily unique.

The goal is to find a maximum matching for

a given bipartite graph, and if-if-if it's, if the max,

maximum matching happens to be a perfect one, we'll end up finding a perfect one.

the matching problem is a well-studied problem in the field of algorithms.

And there's a, there is a very well known

an elegant polynomial-time offline algorithm that, you know, remember

an offline algorithm is when you have the entire graph available to the algorithm.

And it's based on this idea of augmenting path.

It's a very classic algorithm from 1973 by Hopcroft and Karp.

And if, you know, if you're curious you can look it up on,

on Wikipedia following that the link that I've given there.

Now however, suppose you don't know the entire graph in advance.

You only have a piece of the graph available to you at any point.

In the online version of the graph matching problem,

we're initially given the sets boys and girls, the two sets of nodes.

But you're not given all the edges between the nodes.

In fact, the edges are revealed one round at a time.

In each round one girl's choices are revealed.

That is, the edges between that girl and the boys are revealed.

Now, in each round, the algorithm has to make an irrevocable decision.

And the and that decision is to either pair the girl with some boy, right?

So we know all the edges from the girl, from that girl to, to the boy set.

So, we know all the compatible boys for that girl.

So we can either pair the girl with a boy.

Then we'll have to pick a boy who has not already been paired because that's,

If there is a boy among the girl's compatible set who has not already been

paired, we can choose to pair the girl with that boy or

we can decide to not pair the girl with any boy, and move on to the next girl.

But once, we've made the choice, we cannot go back.

Subtitles ListPlay Video

6 6 Computational Advertising Bipartite Graph Matching 24 47

sort

entire

scenario

context