Internet memes, those rapidly propagating online jokes, often in the form of an image or video, are now a fixture of contemporary culture. The continual re-working of the most popular memes generates diverse instances that may only resemble each other in a loose sense, but still signal to the viewer that familiar information is present. The goal of this homework assignment is for you to develop a series of classifiers to detect new instances of known meme classes. As in Homework 04, we will use the R environment here. R is available for Linux, MacOS and Windows. Feel free to choose any environment that you prefer. If you are using Debian or Ubuntu Linux, R is available via the command sudo apt-get install r-base. An Ubuntu virtual machine may be the easiest way to get up and running.

For this assignment, record your responses to the following activities in the file in the homework07 folder of your assignments GitLab repository and push your work by 11:59 PM Friday, November 16.

Activity 0: Branching

As discussed in class, each homework assignment must be completed in its own git branch; this will allow you to separate the work of each assignment and for you to use the merge request workflow.

To create a homework07 branch in your local repository, follow the instructions below:

$ cd path/to/cse-40171-fa18-assignments                                                     # Go to assignments repository

$ git remote add upstream           # Switch back over to the main class repository

$ git fetch upstream                                                                        # Toggle the upstream branch

$ git pull upstream master                                                                  # Pull the files for homework07

$ git checkout -b homework07                                                                # Create homework07 branch and check it out

$ cd homework07                                                                             # Go into homework07 folder

Once these commands have been successfully performed, you are now ready to add, commit, and push any work required for this assignment.

Activity 1: Binary Meme Classifier (50 Points)

The first step in this assignment is to obtain the data. You can download the complete data set here. After unzipping the file, you will find the directory meme_dataset, which itself has directories for images and features for three different meme classes and a negative set with no meme content. Features for each provided image have already been extracted for you (the images are available simply for reference). They are flattened feature vectors representing a Histogram of Oriented Gradients (HOG) representation. This is a common handcrafted feature approach that works well for many applications. It is a good candidate for extracting features here because it makes use of a uniform grid over the entire image, meaning we don't have to detect localized instances of visual features before extracting them. Each feature file follows the same format: a series of 46,208-d feature vectors in .csv format (and one vector at the top denoting the index of each dimension). Training (with 25 images) and testing (with 5 images) files are provided for the three meme classes, and a testing file is provided for the unrelated negative set.

Let's consider the memes "Soon" and "Doge" for a binary classification scenario. The key aspect of our analysis for classification will be an assessment of the stylistic similarity between images. To do that, we need to establish that different meme classes have stereotypical visual styles. The assessment of style in imagery is an aspect of AI that is of growing importance. As it turns out, style is a critical factor for understanding a meme.

In April of 2007, an image of a diabolical looking orange cat fixating upon a chihuahua along with the superimposed text “SOON." appeared on the popular comedy weblog "I Can Has Cheezburger." This was the first instance of what is now a popular meme, new members of which are created via an image macro that inserts the "SOON." caption on a chosen image. Visually, this meme takes on a particular form in which an ominous figure (typically an animal, but sometimes an inanimate object) can be seen fixating on another figure within the image, or the viewer of the image. Some variants forgo the typical boldface white letters, and incorporate the caption directly into the image content, making an interesting test case for automated classification of new variants that can't easily be tagged through optical character recognition of the characteristic text.

While the Soon meme is no doubt popular, the Doge meme, which has become an outright cultural phenomenon with its own cryptocurrency and NASCAR team, far surpasses it. The "doge" is a Shiba Inus, often depicted expressing a humorous inner monologue via brightly colored captions in a Comic Sans font. The origin of this meme is an unusual picture of a pet Shiba flashing a self-confident glare at the camera, which was posted to the personal blog of a Japanese kindergarten teacher in 2010. It was quickly discovered and shared to the popular social networks reddit and 4chan, where various captions were added. The visual style of this meme is more consistent than the soon meme, with a similar color palette and primary object (the doge) across images. Variations on the theme forgo the captions in favor of a clever reworking of the dog into other objects.

With a collection of feature vectors in hand, and an understanding that it is indeed possible to match the visual style of memes, we need a straightforward way to train a binary meme classifier for the two meme classes just described. We'd like to associate images that contain some measure of reused image content with the correct meme class, if we know it. Intuitively, this should be based on a distance assessment from the known data points. A quick way to do this is to use the k-Nearest Neighbor algorithm (k-NN). The k-NN algorithm makes decisions by finding the k vectors closest in space to a vector under consideration x. To find the closest vectors, distance from x to vectors in the training set must be assessed using some distance measure (e.g., Euclidean, or straight-line, distance). Thus, k vectors where xi is a closest point to x in space are identified, and the average of their responses is calculated to yield a decision based on a majority vote. The class package of R provides a convenient k-NN implementation.

Write an R script named soon_vs_doge.R that does the following:

Run your script and report the entire output from the knn function in your file. If things are running correctly, the results should be reasonably accurate, meaning that the two memes are visually separable.

Activity 2: Multi-Class Meme Classifier (25 Points)

Let's see how the accuracy of the classifier changes when we add another meme. In contrast to Soon and Doge, the ALS Ice Bucket Challenge is an instantiation of the meme concept that provokes active participation and content generation. Emerging briefly in 2014 as part of a charity drive to raise money for the treatment of Amyotrophic Lateral Sclerosis (ALS), also known as Lou Gehrig's disease, participants in the challenge were to dump a bucket of ice water on top of their heads, post a photo of the act on a social network, and then nominate three other people to perform the same action within the next 24 hours. Memes like the Ice Bucket Challenge are interesting visually, in that they are not generated by an image macro that inserts signifying text. Moreover, the massive (albeit short-lived) popularity of this meme spawned many parodies that mimicked the visual appearance of the original act, but are still readily identifiable to a human observer as being members of the meme. A key question is whether machines can identify the same patterns in visual appearance that trigger recognition of the meme.

Copy your script from Activity 1 to a new script called soon_vs_doge_vs_icebucket.R. Make the following modifications:

Run this script and report the entire output from the knn function in your file. What happened to the predictions for the Soon meme? Answer this question in your

Activity 3: Open Set Multi-Class Meme Classifier (25 Points)

Let's revisit the idea of open set recognition from Homework 06. If we were to use our multi-class classifier in the real world to detect new instances of our known memes, we would need a mechanism to reject irrelevant images. To develop this mechanism, let's use some example images from the Common Objects in Context (COCO) data set. The images from COCO that have been selected for this assignment have no relationship with the memes we have been examining.

Copy your script from Activity 2 to a new script called negatives.R. Make the following modifications:

Run this script and report the entire output from the knn function in your file. What was the trade-off of adding a capability to reject irrelevant images? Answer this question in your


If you have any questions, comments, or concerns regarding the course, please provide your feedback at the end of your


To submit your assignment, please commit your R scripts and to the homework07 folder of your homework07 branch in your assignment's GitLab repository:

$ cd path/to/cse-40171-fa18-assignments   # Go to assignments repository
$ git checkout master                     # Make sure we are in master branch
$ git pull --rebase                       # Make sure we are up-to-date with GitLab
$ git checkout -b homework07              # Create homework07 branch and check it out
$ cd homework07                           # Go to homework07 directory
$ $EDITOR                       # Edit appropriate
$ git add                       # Mark changes for commit
$ git commit -m "homework07: complete"    # Record changes
$ git push -u origin homework07           # Push branch to GitLab

Procedure for submitting your work: create a merge request by the process that is described here, but make sure to change the target branch from wscheirer/cse-40171-fa18-assignments to your personal fork's master branch so that your code is not visible to other students. Additionally, assign this merge request to your TA and add wscheirer, agraese, and AndroidKitKat as approvers (so all class staff can track your submission). Your assigned TA is agraese if you have a last name starting with A through Ki, or AndroidKitKat if you have a last name starting with Kl through W.