1
00:00:00,450 --> 00:00:03,280
Next we shall look at the problem
of finding news articles that

2
00:00:03,280 --> 00:00:04,515
represent the same story.

3
00:00:04,515 --> 00:00:08,010
Since the same story maybe used
by many different sources,

4
00:00:08,010 --> 00:00:11,090
each with its own way of
presenting it on a web page,

5
00:00:11,090 --> 00:00:14,570
the problem is not too different from
finding similar documents in general.

6
00:00:15,640 --> 00:00:19,030
But there is a special way of shingling
that works well when the difference

7
00:00:19,030 --> 00:00:21,409
are mostly in the ads
associated with the article.

8
00:00:23,190 --> 00:00:26,260
We shall also talk about a simple
bucketing method that works

9
00:00:26,260 --> 00:00:31,140
when the number of sets is not too great,
and the similarity expected for

10
00:00:31,140 --> 00:00:33,450
the underlying articles is quite high.

11
00:00:34,820 --> 00:00:38,835
So, we turn to the third interesting
variant of LSH with another true story.

12
00:00:38,835 --> 00:00:43,200
Awhile ago a group of political
scientists at Stanford asked for

13
00:00:43,200 --> 00:00:48,155
help from the CS department going
through a large repository of

14
00:00:48,155 --> 00:00:52,400
news articles to identify those
that were essentially duplicates.

15
00:00:52,400 --> 00:00:56,530
The problem was that many of the articles
really came from the same source, but they

16
00:00:56,530 --> 00:01:00,970
can look quite different when published on
the website of different news services.

17
00:01:00,970 --> 00:01:04,330
They wanted to group web pages
whose underlying articles were

18
00:01:04,330 --> 00:01:06,045
the same or similar.

19
00:01:06,045 --> 00:01:11,990
This by the way, is the same problem
faced every day by services such as

20
00:01:11,990 --> 00:01:17,440
Google News although they do the grouping
day by day rather than once and for all.

21
00:01:17,440 --> 00:01:21,840
Identifying the same underlying
article is tricky because each news

22
00:01:21,840 --> 00:01:25,420
source creates a page from the article
that has unique elements on that page.

23
00:01:27,530 --> 00:01:33,570
For example, they will put the newspaper's
name and other text elements on the top

24
00:01:33,570 --> 00:01:36,280
and there will be links
to ads on the page.

25
00:01:37,930 --> 00:01:40,946
It's also common for
one site to include links to related or

26
00:01:40,946 --> 00:01:42,889
interesting stories on its own site.

27
00:01:44,430 --> 00:01:47,850
In addition, it is common for
a site not to place the entire article on

28
00:01:47,850 --> 00:01:50,720
its pages especially if
the article is long.

29
00:01:50,720 --> 00:01:52,860
They will leave off
the paragraphs at the end or

30
00:01:52,860 --> 00:01:56,650
even delete other paragraphs that
the editor finds less relevant.

31
00:01:57,740 --> 00:02:03,320
Now, the CS team had not heard of
locality sensitive hashing or minhashing.

32
00:02:03,320 --> 00:02:06,890
However, they invented a form of shingling
that is probably better than the standard

33
00:02:06,890 --> 00:02:11,350
approach we covered for those webpages
that are of the type we just described.

34
00:02:12,650 --> 00:02:17,190
And they invented a simple substitute for
LSH that worked adequately well for

35
00:02:17,190 --> 00:02:19,530
the scale of problem they were looking at.

36
00:02:19,530 --> 00:02:22,780
They partitioned the pages into
groups of similar length and

37
00:02:22,780 --> 00:02:26,890
they only compared pages in
the same group or nearby groups.

38
00:02:26,890 --> 00:02:28,030
After they had done all this,

39
00:02:28,030 --> 00:02:31,590
we happened to be talking in the hall and
I mentioned minhashing and LSH.

40
00:02:31,590 --> 00:02:37,310
They implemented these algorithms on that
data, and they found that minhashing

41
00:02:37,310 --> 00:02:42,174
plus LSH was better as long as the
similarity threshold was less than 80%.

42
00:02:44,130 --> 00:02:46,240
Actually, that is consistent
with what is known.

43
00:02:46,240 --> 00:02:49,805
When you're looking for
very high Jaccard similarities like 80 or

44
00:02:49,805 --> 00:02:53,670
90% then there are indeed more
efficient algorithms, and

45
00:02:53,670 --> 00:02:55,860
we're going to cover these
before we leave the topic.

46
00:02:56,940 --> 00:02:59,760
Interestingly, the first time
they implemented minhashing,

47
00:02:59,760 --> 00:03:03,030
they got it wrong and
decided that the method was terrible.

48
00:03:03,030 --> 00:03:05,750
But the problem was that I
forgot to remind them to

49
00:03:05,750 --> 00:03:10,160
do the minhashing row by row,
where you compute the hash value for

50
00:03:10,160 --> 00:03:16,100
each row number once and for
all rather than once for each column.

51
00:03:16,100 --> 00:03:20,309
Remember that the rows correspond to the
shingles and the columns to the web pages.

52
00:03:22,030 --> 00:03:26,550
Since their data was naturally stored
by columns, that is by web, web pages,

53
00:03:26,550 --> 00:03:31,880
they needed to sort their set of shingle
webpage pairs to organize them by row,

54
00:03:31,880 --> 00:03:33,520
that is, by shingle.

55
00:03:33,520 --> 00:03:38,530
Once they did that, they got the positive
results I mentioned on the previous slide.

56
00:03:38,530 --> 00:03:42,010
Before leaving this topic, let me tell
you about the way these guys shingle web

57
00:03:42,010 --> 00:03:43,800
pages containing news articles.

58
00:03:45,040 --> 00:03:49,460
The key observation was that they needed
to give more weight to the articles

59
00:03:49,460 --> 00:03:54,100
themselves than to the ads and
other elements surrounding the article.

60
00:03:54,100 --> 00:03:57,360
That is, they did not want to
identify as similar two articles from

61
00:03:57,360 --> 00:04:00,070
the same newspaper with the same ads and

62
00:04:00,070 --> 00:04:03,215
other elements, but
different underlying stories.

63
00:04:03,215 --> 00:04:07,810
Their trick was based on stop words,
the common little words that we need in

64
00:04:07,810 --> 00:04:12,690
order to construct sentences properly,
but that do not convey much meaning.

65
00:04:12,690 --> 00:04:18,487
Typically the set of stop words includes
things like and, the, to and so on.

66
00:04:18,487 --> 00:04:22,486
Usually when analyzing text we ignore
stop words because they don't tell us

67
00:04:22,486 --> 00:04:24,431
anything about the subject matter.

68
00:04:24,431 --> 00:04:27,849
But here the key observation
was that the stop words tell us

69
00:04:27,849 --> 00:04:32,733
whether we're looking at the news article
from which we want to take our shingles or

70
00:04:32,733 --> 00:04:38,020
ads or other peripheral matters from
which we do not want to take shingles.

71
00:04:38,020 --> 00:04:41,030
For example,
ordinary prose would say something like,

72
00:04:41,030 --> 00:04:43,520
I recommend that you buy Sudzo for
your laundry.

73
00:04:44,760 --> 00:04:47,380
The likely stop words are shown in orange.

74
00:04:47,380 --> 00:04:52,150
I, that, you, for, your.

75
00:04:52,150 --> 00:04:53,620
Very common words.

76
00:04:53,620 --> 00:04:58,520
But in an ad we would just find
something abbreviated like buy Sudzo,

77
00:04:58,520 --> 00:05:01,140
which has no stop word at all.

78
00:05:01,140 --> 00:05:04,610
So they defined a shingle to be a stop
word followed by the next two words in

79
00:05:04,610 --> 00:05:07,050
the sentence, stop words or not.

80
00:05:07,050 --> 00:05:14,020
Thus, in the sentence on the slide one
shingle would be, I recommend that,the

81
00:05:14,020 --> 00:05:19,270
next would be, that you buy and so on.

82
00:05:19,270 --> 00:05:21,840
Notice that there
are relatively few shingles and

83
00:05:21,840 --> 00:05:25,000
it does not guarantee that each
word is part of even one shingle.

84
00:05:26,100 --> 00:05:29,350
The reason this notion of shingle makes
sense is that it biases the set of

85
00:05:29,350 --> 00:05:32,510
shingles for
a page in favor of the news article.

86
00:05:32,510 --> 00:05:36,330
That is, suppose for simplicity that
all pages are half news article and

87
00:05:36,330 --> 00:05:40,020
half ads,
if you count by number of characters.

88
00:05:40,020 --> 00:05:43,350
If we have a second page with,
with the same article, but

89
00:05:43,350 --> 00:05:45,810
different ads,
we find that most of the shingles for

90
00:05:45,810 --> 00:05:50,110
both pages come from the article,
because that's where the stop words are.

91
00:05:50,110 --> 00:05:52,460
So these two pages have
almost the same shingles, and

92
00:05:52,460 --> 00:05:54,609
therefore have very high
Jaccard similarity.

93
00:05:56,730 --> 00:06:00,110
Now consider two pages with the same
ads and different articles.

94
00:06:00,110 --> 00:06:03,860
These will have low Jaccard similarity,
because again, most of their shingles come

95
00:06:03,860 --> 00:06:07,550
from the articles and these shingles would
be mostly different for the two articles