>> AHMADULLIN: Good afternoon everyone.
I'm going to--I'm going to talk about--today about Document Visual Similarity Measures
for Document Search.
So as for problem statement, we can say that we want to have means to compare documents
with respect to their visual similarity.
We do not consider the content of the document, what the document talks about.
We would rather like to compare layouts and images in the document, such that similar
documents would be--and have some means, have some algorithm that would be enable--that
would enable us to find similar documents in a very large document that is said.
So, as a possible application--is--would be something like an entrepreneur would like
to advertise his business and he would like to come up with a brochure, and he would have
an idea about what he would like to have in his brochure, and he would be provided a large
data set of brochures that are designed--that are prepared by the professional designers.
And he would have means to visually find documents--brochures that are similar to what he has in his mind,
but created by a professional designer.
So this is a screenshot of Snapfish webpage where the--where the service is greeting cards.
So, as an additional application would be organizing documents or greeting cards with
respect to their visual similarities, such that users might be--might find greeting cards
of their specific interests rather--by searching by their visual similarity rather than by
the keyword, or newspaper catalog searches and other application.
So our approach--today's problem is basically comparing documents with respect to three
different components.
There is component for background, text and saliency.
Background component is basically the component where we--where we have the background without
text.
We erase all the text from the background and then we use the document.
We extract featured vectors from every pixel of the document.
So it's five dimensional.
First of all it's XY which is the position of the pixel and LAB color values.
So from every pixel of the background component, we extract one featured vector.
And then we run EM algorithm to find out--to learn a Gaussian Mixture Model and then we
compare--and then we--the number of mixture model is basically calculated by the MDL,
Minimum Description Length cost function.
So we learn a Gaussian Mixture Model that basically represents pixel--position of a
pixel given the color of this pixel at the background.
Here, what we can mention here as the visualization of the Gaussians is can be as follows.
So since the Gaussian--since the featured vectors are five dimensional, they're impossible
to show on a plain.
So the best thing we can do is, actually, we can show each Gaussian as an ellipsoid
and give its mean color.
Since the Gaussian--the featured vectors each have a color, then the main color would be
actually--can be given to the whole Gaussian.
And here, we can see a document next to its background component, and next to the ellipsoids
that represents the whole Gaussian Mixture Model of the--for the background component.
Another visualization of this approach would be as follows.
So by the maximum likelihood function, we can assign every pixel its color of its closest
Gaussian.
So if we have five Gaussians for example here, then the corresponding segmentation where
we'll have five colors to assign to each pixel would be as follows and we can this experiment
for as many Gaussians that can--we can have.
And you can see that there is a big difference in the number of Gaussians between third--thirteenth
and twenty-eighth Gaussians, but in terms of segmentation, there is not a lot difference.
So we actually end up with a number--with number of Gaussians in between 10 and 15 so
we don't have more than 15 Gaussians in our mixture model for this application.
For text component, we'll do a similar algorithm.
We extract Gaussian Mixture Model.
But then in this case, we only consider pixels of textboxes.
So, basically we take pixels, XY, the only--the other--the coordinates of pixel at every textbox
and we disregard everything else.
So we learn Gaussians and these are the actual Gaussians, since they're two dimensional we
can show them on the screen.
To--this is the representation of the Gaussian Mixture Model.
And then for the saliency component, we extract--the saliency is basically given as the Euclidean
distance between LAB color values of every pixel and the average LAB color of the whole
document.
So it is basically given by this formula, so it is three--the featured vectors now are
three dimensionals that are given by the position of the pixel, XY values, their coordinate,
and the third coordinate would be the saliency value.
So saliency, why do we pay attention to the saliency?
Saliency is basically--would represent the areas or the regions in the document that
are significantly more visual in way.
Actually, they would stand out with respect to its neighborhood.
So for example, this one comparing documents, we would like to find the documents that would
be similar to this one where the--instead of the dancing persons here, it would have
some other salient portion.
Maybe some inscription or some texts that would have also these salience--salient properties
at the same place.
And so once we have learned the Gaussian Mixture Models for every component, we now would like
to have some means to compare Gaussians.
So we compare Gaussians by the Hellinger distance which is basically the distance that we can
calculate whether we can find comparing two different probable distributions.
So for probable distributions, F and G, the Hellinger distance would be the scales--square
root of the one-half norm between these two distributions, the square root.
So these are two distributions which can be simplified into this single form where it
is basically the square root of one minus the Bhattacharyya coefficient in between two
different distributions, F and G. And if we expand the Bhattacharyya coefficient, we'll
basically see that this is nothing else but the expectation of the square root of the
ratio between the two distributions under one of them.
And it is also symmetric so we can actually play around with exchanging distribution P
by QM.
We can have another form of expressing Bhattacharyya coefficient but in terms of expectation of
another distribution.
The Bhattacharyya coefficient, in order to compare the distribution, we'll basically
use--we approximate Bhattacharyya coefficient by the unscented transform.
Unscented transform is used to approximate expectation of a nonlinear function, h(x)
under probability distribution, well in this case f(x).
So this is basically done in the following way.
We specifically choose points at certain locations for the distribution F and we evaluate the
function H of these specific points and then we take the scale sum of the obtained values
and this would be the approximation of the expectation.
Now in terms of Gaussian, it would be best actually, if we just--find--take all these
points.
Points that are certain--that would capture the true mean and variance of the distribution.
So for example, if we want to find expectation under some specific function h(x), where the
probability distribution can be--is given by this ellipsoid.
Then the points that we choose actually, would be on the two sides of the mean and th1at
would be the square root of column of covariance matrix away from the mean.
And so by taking the mean of these points, we would have an approximation of the expectation
of this--normally the function H. And so once--this is the ways to calculate distances between
Gaussian and Mixtures.
And since--I've mentioned before we have three components.
Now, they will know how to compare these three components.
The question is how do we come up with an ultimate measure in between the documents?
So to do that, we've basically come up--we searched for weights: WB standing for the
weight for the background component; WT, which is the weight for text component and weight
for the saliency component and then we weight the distances and we searched for the awaited
sum of these distances to go with the ultimate measure between document similarities.
And to do that, we define the probability function, which is expressed in this way.
And this is the probability function that document J is the neighbor of document I.
And then if we have classes of similar documents in our data set, then we can set probability
PI which would be a probability that document I, you know, is correctly classified that
all of its neighbors that are in class CI are close to it.
And then we can sum them; some of this PI would expect all class that we're having our
data and we can come up with a class function that would basically be the probability that
all of the documents are correctly classified.
And the good thing about this function is that it is differentiable and we can run a
great SNL algorithm, all sorts of optimization algorithms on this function to find the optimal
weights for application.
And so for our testing components--testing and training, we use the 410 documents from
five different classes.
So you can see examples--samples from our data set.
And we run a three-fold cross validation technique and here are the results of our three runs
for our cross validation.
So the cross validation basically works in the way that we divide every class into three
parts.
We train on two parts and test one another and then we switch them and then we do that
three times and these are the results.
And as for a small demo, I would like to show you the following.
So here for the demo, we have a data set of approximately 2,020 documents here.
There are very different in their stylistic features.
And what we can do is as simple as the demo.
It would be basically to find a document here--an index of a document and run and find four
of the most similar ones.
For example, then the query document would be the [INDISTINCT] on the left.
And the four that are most similar to this one would expect the visual similarity would
be shown next to it.
And the same way we can run this experiment a few times for--oh, let me just choose a
very different example, something of this sort and the algorithm basically produce--gives
me this.
So, all these documents are considered to be similar with respect to their similarity
measure and their stylistic features.
This is it.
Thank you very much.
>> Okay?
Do we have any questions for Ildus about his work?
>> Yeah.
>> Andrew.
>> I'm just curious--and if I had the answer to this question, I would ask it more specifically.
At Kai this year, Scott Klemmer's group invented a style matching based on, sort of, a visual
feature model that kind of reminded me a little of the last paper but not exactly at all,
but sort of in the same [INDISTINCT] I just wondered if you--so you're familiar with familiar
with that >> AHMADULLIN: Are you referring to [INDISTINCT]
paper?
>> Yes.
>> AHMADULLIN: Yes.
>> I guess they have a whist paper in a few weeks.
>> AHMADULLIN: Yes.
>> I was just wondering if you would--could compare and contrast the two of purpose.
>> AHMADULLIN: You know, that's right--that's a very good question, actually.
We have--I've been invited to a few seminars to their group actually.
And what they do is they compare layouts of web pages and--whereas we basically concentrate
on our own--on the actual PDF documents.
But apart from that, our approaches are similar.
Yes, but the thing is, they're using tree based algorithm, so they compare trees, which
is a different problem.
Well, another thing is they're comparing tree algorithms might be incomplete so they might
run into some difficulties, whereas this is not very robust but--well, more robust but
a little bit more simple approach to this problem.
>> Why do you think the implications of that are--for how useful the two approaches are
and on what kinds of problems?
>> AHMADULLIN: Well, applications will be totally different actually.
The first--their approach would be just to come up with a website that has the layout
of a--certain layout that is similar to the websites the user has chosen, whereas in our
case, we have actual brochures and we would be basically comparing the documents, single
page documents in here.
We do not consider web pages because they can be very different actually.
But here, we have certain margins and certain limitations to the PDF documents that we use.
I'm not sure if I answered your question but we can talk later just for fun.
>> Thank you.
>> Are there other questions?
>> I don't really have a question but I thought that it was nice.
I liked the work.
It was interesting to see your success.
Nice demo.
>> AHMADULLIN: Thank you.
>> Okay?
Let's thank our speaker for a beautiful [INDISTINCT]