We address the problem of discovering new notions of userperceived similarity between near-duplicate multimedia files. We focus on file-sharing, since in this setting, users have a well-developed understanding of the available content, but what constitutes a near-duplicate is nonetheless nontrivial. We elicited judgments of semantic similarity by implementing triadic elicitation as a crowdsourcing task and ran it on Amazon Mechanical Turk. We categorized the judgments and arrived at 44 different dimensions of semantic similarity perceived by users. These discovered dimensions can be used for clustering items in search result lists. The challenge in performing elicitations in this way is to ensure that workers are encouraged to answer seriously and remain engaged.
Crowdsourcing platforms make it possible to elicit semantic judgments from users. Crowdsourcing can be particularly helpful in cases in which human interpretations are not immediately self evident. In this paper, we report on a crowdsourcing experiment designed to elicit human judgments on semantic similarity between near duplicate multimedia files. We use crowdsourcing for this application because it allows us to easily collect a large number of human similarity judgments. The major challenge we address is designing the crowdsourcing task, which we ran on Amazon Mechanical Turk, to ensure that the workers from whom we elicit judgments are both serious and engaged.
Multimedia content is semantically complex. This complexity means that it is difficult to make reliable assumptions about the dimensions of semantic similarity along which multimedia items can resemble each other, i.e., be considered near duplicates. Knowledge of such dimensions is important for designing retrieval systems. We plan ultimately to use this knowledge to inform the development of algoCopyright c 2012 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors.
CrowdSearch 2012 workshop at WWW 2012, Lyon, France rithms that organize search result lists. In order to simplify the problem of semantic similarity, we focus on a particular area of search, namely, search within file-sharing systems. We choose file-sharing, because it is a rich, real-world use scenario in which user information needs are relatively well constrained and users have a widely-shared and welldeveloped understanding of the characteristics of the items that they are looking for.
Our investigation is focused on dimensions of semantic
similarity that go beyond what is depicted in the visual
channel of the video. In this way, our work differs from other
work on multimedia near duplicates that puts its main
emphasis on visual content [
The paper is organized as follows. After presenting background and related work in Section 2, we describe the crowdsourcing experiment by which we elicit human judgments in Section 3. The construction of the dataset used in the experiment is given in Section 4. Direct results of the experiment and the derived similarity dimensions are discussed in Section 5. We finish with conclusions in Section 6. 2. 2.1
Well-organized search results provide an easy means for
users to overview search results lists. A simple,
straightforward method of organization groups together similar
results and represents each group with a concise surrogate,
e.g., a single representative item. Users can then scan a
shorter list of groups, rather than a longer list of individual
result items. Hiding near duplicate items in the interface
is a specific realization of near-duplicate elimination, which
has been suggested in order to make video retrieval more
efficient for users [
Our work uses a definition of near duplicates based on the function they fulfill for the user:
Functional near-duplicate multimedia items are items that fulfill the same purpose for the user. Once the user has one of these items, there is no additional need for another.
In [
Our work is related to [
We are interested in gathering human judgments on semantic interpretation, which involves the acquisition of new knowledge on human perception of similarity. Any thoughtful answer given by a human is of potential interest to us. No serious answer can be considered wrong.
The technique we use, triadic elicitation, is adopted from
psychology [
A crowdsourcing task that involves the elicitation of
semantic judgments differs from other tasks in which the
correctness of answers can be verified. In this way, our task
resembles the one designed in [
The goal of our crowdsourcing task is to elicit the various notions of similarity perceived by users of a file-sharing system. This task provides input for a card sort, which we carry out as a next step (Section 5.2) in order to derive a small set of semantic similarity dimensions from the large set of user-perceived similarities we collect via crowdsourcing.
The crowdsourcing task aims to achieve workers’ seriousness and engagement with judicious design decisions. Our task design places particular focus on ensuring task credibility. For example, the title and description of the pilot makes clear the purpose of the task, i.e., research, and that the workers should not expect a high volume of work offered. Further, we strive to ensure that workers are confident that they understand what is required of them. We explain functional similarity in practical terms, using easyto-understand phrases such as “comparable”, “like”, and “for all practical purposes the same”. We also give consideration to task awareness by including questions in the recruitment task designed to determine basic familiarity with file-sharing and interest level in the task. 3.1
The task consists of a question, illustrated by Figure 1, that is repeated three times, once for three different triads of files. For each presented triad, we ask the workers to imagine that they have downloaded all three files and to compare the files to each other on a functional level. The file information shown to the workers is taken from a real file-sharing system (see the description of the dataset in Section 4) and are displayed as in a real-world system, with filename, file size and uploader. The worker is not given the option to view the actual files, reflecting the common real file-sharing scenario in which the user does not have the resources (e.g., the time) to download and compare all items when scrolling through the search results.
The first section of the question is used to determine
whether it is possible to define a two-way contrast between
the three files. We use this section to eliminate cases in
which files are perceived to be all the same or all different.
This is following the advice on when not to use triadic
elicitation that is given in [
The following triad is an example of a case in which a two-way contrast should not be forced:
Despicable Me The Game VA-Despicable Me (Music From The Motion Picture) Despicable Me 2010 1080p These files all bear the same title. If workers were forced to identify a two-way contrast, we would risk eliciting differences that are not on the functional level, e.g., “the second filename starts with a V while the other two start with a D”. Avoiding nonsense questions also enhances the credibility of our task.
In order to ensure that the workers follow our definition of functional similarity in their judgment, we elaborately define the use-case of the three files in the all-same and all-different options. We specify that the three files are the same when someone would never need all of them. Similarly, the three files can be considered to be all different from each other if the worker can think of an opposite situation where someone would want to download all three files. Note that emphasizing the functional perspective of similarity guides workers away from only matching strings and towards considering the similarity of the underlying multimedia items. Also, we intend the elaborate description to discourage workers to take the easy way out, i.e., selecting one of the first two options and thereby not having to contrast files.
Workers move on to the second section only if they report it is possible to make a two-way contrast. Here they are asked to indicate which element of the triad differs from the remaining two and to specify the difference by answering a free-text question. 3.2
We ran two batches of Human Intelligence Tasks (HITs) on Amazon Mechanical Turk on January 5th, 2011: a recruitment HIT and the main HIT. The recruitment HIT consisted of the same questions as the regular main HIT (Section 3.1) using three triads and included an additional survey. In the survey, workers had to tell whether they liked the HIT and if they wanted to do more HITs. If the latter was the case, they had to supply general demographic information and report their affinity with file-sharing and online media consumption.
The three triads, listed below, were selected from the portion of the dataset (Section 4) reserved for validation. We selected examples for which at least one answer was deemed uncontroversially wrong and the others acceptable.
Acceptable to consider all different or to consider two the same and one different: Desperate Housewives s03e17 [nosubs] Desperate Housewives s03e18 [portugese subs] Desperate Housewives s03e17 [portugese subs] Here, we disallowed the option of considering all files to be comparable. For instance, someone downloading the third file would also want to have the second file as these represent two consecutive episodes from a television series.
Black Eyed Peas - Rock that body Black Eyed Peas - Time of my life Black Eyed Peas - Alive Here, we disallowed the option of considering all files to be comparable as one might actually want to download all three files. For the same reason, we also disallowed the option of considering two the same and one different.
Acceptable to consider all same or to consider two the same and one different: The Sorcerers Apprentice 2010 BluRay MKV x264 (8 GB) The Sorcerers Apprentice CAM XVID-NDN (700 MB) The Sorcerers Apprentice CAM XVID-NDN (717 MB) Here, we disallowed the option of considering all files different. For instance, someone downloading the second file would not also download the third file as these represent the same movie of comparable quality.
The key idea here is to check whether the workers understood the task and are taking it seriously, while at the same time not to exclude people who do not share a a similar view onto the world as us. To this end, we aim to choose the least controversial cases and also admit more than one acceptable answers.
We deemed the recruitment HIT to be completed successfully if the following conditions were met:
No unacceptable answers (listed above) were given in comparing files in each triad.
The answer to the free-text question provided evidence that the worker generalized beyond the filename, i.e., they compared the files on a functional level.
All questions regarding demographic background were answered.
Workers who completed the recruitment HIT, who expressed interest in our HIT, and who also gave answers that demonstrated affinity with file sharing, were admitted to the main HIT.
The recruitment HIT and the main HIT ran concurrently. This allowed workers who received a qualification to continue without delay. The reward for both HITs was $0.10. The recruitment HIT was open to 200 workers and the main HIT allowed for 3 workers per task and consisted of 500 tasks in total. Each task contained 2 triads from the test set and 1 triad from the validation set. Since our validation set (Section 4) is smaller than our test set, the validation triads were recycled and used multiple times. The order of the questions was randomized to ensure the position of the validation question was not fixed. 4.
We created a test dataset of a 1000 triads based on
popular content on The Pirate Bay (TPB),1 a site that indexes
content that can be downloaded using the BitTorrent [
Users looking for a particular file normally formulate a query based on their idea of the file they want to download. Borrowing this approach, we constructed a query for each of the items from the retrieved top 100 list. The queries were constructed automatically by taking the first two terms of a filename, ignoring stop words and terms containing digits. This resulted in 75 unique derived queries.
The 75 queries were issued to TPB on January 3, 2011. Each query resulted in between 4 and 1000 hits (median 335) and in total 32,773 filenames were obtained. We randomly selected 1000 triads for our test dataset. All files in a triad correspond to a single query. Using the same set of queries and retrieved filenames, we manually crafted a set of 28 triads for our validation set. For each of the triads in the validation set, we determined the acceptable answers.
Our crowdsourcing task appeared to be attractive and finished quickly. The main HIT was completed within 36 hours. During the run of the recruitment HIT, we handed out qualifications to 14 workers. This number proved to be more than sufficient and caused us to decide to stop the recruitment HIT prematurely. The total work offered by the main HIT was completed by eight of these qualified workers. Half of the workers were eager and worked on a large volume of assignments (between 224 and 489 each). A quick look at the results did not raise any suspicions that the workers were under-performing compared to their work on the recruitment HIT. We therefore decided not to use the validation questions to reject work. However, we were still curious as to whether the eager workers were answering the repeat
Movie vs. trailer Comic vs. movie Audiobook vs. movie Sequels (movies) Soundtrack vs. corresponding movie Movie vs. wallpaper Complete season vs. individual episodes Graphic novel vs. TV episode Different realization of same legend/story Different albums Collection vs. album Event capture vs. song Bonus track included Event capture vs. unrelated movie Different language Quality and/or source Different game Software versions Different application Documentation (pdf) vs. software
Safe vs. X-Rated ing validation questions consistently. The repeated answers allowed us to confirm that the large volume workers were serious and not sloppy. In fact, the highest volume worker had perfect consistency.
The workers produced free-text judgments for 308 of the 1000 test triads. The other 692 triads consisted of files that were considered either all different or all similar. Workers fully agreed on which file differed from the other two for 68 of the 308 triads. Only two judgments out of the three given judgments agreed which file was different for 93 triads. For the remaining 147 triads no agreement was reached. Note that whether an agreement was reached is not of direct importance to us since we are mainly interested in just the justifications for the workers’ answers, which we use to discover the new dimensions of semantic similarity. 5.2
We applied a standard card sorting technique [
The list of categories resulting from the card sort is listed in Table 1. We found 44 similarity dimensions, many more than we had anticipated prior to the crowdsourcing experiment. The large number of unexpected dimensions we discovered support the conclusion that the user perception of semantic similarity among near duplicates is not trivial. For example, the “commentary document versus movie” dimension, which arose from a triad consisting of two versions of a motion picture and a text document that explained the movie, was particularly surprising, but nonetheless important for the file-sharing setting.
Generalizing our findings in Table 1, we can see that most dimensions are based on different instantiations of particular content (e.g., quality and extended cuts), on the serial nature of content (e.g., episodic), or on the notion of collections (e.g., seasons and albums). These findings and generalizations will serve to inform the design of algorithms for the detection of near duplicates in results lists in future work.
In this work, we have described a crowdsourcing experiment that discovers user-perceived dimensions of semantic similarity among near duplicates. Launching an interesting task with the focus on engagement and encouraging serious workers, we have been able to quickly acquire a wealth of different dimensions of semantic similarity, which we otherwise could not have thought of. Our future work will involve expanding this experiment to encompass a larger number of workers and other multimedia search settings. Our experiment opens up the perspective that crowdsourcing can be used to gain a more sophisticated understanding of user perceptions of semantic similarity among multimedia nearduplicate items.