Wolfram Blog
Matthias Odisio

Random and Optimal Mathematica Walks on IMDb’s Top Films

July 15, 2013 — Matthias Odisio, Mathematica Algorithm R&D

Or: How I Learned to Watch the Best Movies in the Best Way

I remember when I lived across the street from an art movie theater called Le Club, looking at the movie posters on my way back home was often enough to get me in the ticket line. The director or main actors would ring a bell, or a close friend had recommended the title. Sometimes the poster alone would be appealing enough to lure me in. Even today there are still occasions when I make decisions from limited visual information, like when flipping through movie kiosks, TV guides, or a stack of DVDs written in languages I can’t read.

So how can Mathematica help? We’ll take a look at the top 250 movies rated on IMDb. Based on their posters and genres, how can one create a program that suggests which movies to see? What is the best way to see the most popular movies in sequence?

Movies in sequence image

Drawing from methods used in content-based image retrieval, I will first compute visual similarities between movie posters and display them in a graph. The graph will then be enriched with semantic non-visual information like genres, which should then yield some decent viewing recommendations.

To gather the initial dataset, I looked for lists of great movies. There are many of them, including compilations by The New York Times and by the late Roger Ebert. I felt comfortable opting for the top 250 movies rated by users from IMDb, and I started by copying and pasting the table from the site into a Mathematica notebook.

IMDb is constantly updating the content of this top-250 movies table based on new ratings from users; you should expect the current list to differ from the snapshot I took, which happened to be on June 27, 2013.

The function ImportString parsed the pasted input seamlessly and produced a list of titles. I obtained the remaining data from Wolfram|Alpha by programmatically querying for the corresponding posters and genres:

Wolfram|Alpha query

A handful of obviously incorrect images and genres came back, perhaps because the query was ambiguous for some movie titles. I did correct the data by manually massaging those specific queries. The movies without posters in Wolfram|Alpha have been disregarded. After such curation, a list of 240 movies was left:

Manipulate[  Text[Grid[{{titles[[i]]}, {images[[i]]}, {genres[[i]]}},     Alignment -> Left]], {i, 1, Length[titles], 1},   SaveDefinitions -> True, ContentSize -> {420, 220},   Alignment -> Left]

The first step was to compute similarities between the movie posters. More precisely, I computed a visual dissimilarity for each pair of images. The function ImageDistance features 16 ways to do so. Since movie posters often have a distinct color theme, I selected the EarthMoverDistance method that estimates the dissimilarities between the color histograms of two images. A coffee break later, I had a symmetric matrix containing the visual distances between all pairs of images:

EarthMoverDistance method

The matrix appears with dark spots corresponding to strong visual similarities between movies:

Image[imagedistances]

Distances between images follow a distribution defined on the domain (0, 1), which is unimodal and has positive skewness:

allimagedistances =    Flatten[Table[Diagonal[imagedistances, k], {k, 1, nmovies - 1}]]; Histogram[allimagedistances]

The distances between images provide information about the similarities of movie posters. This information can be expressed in a graph where nodes correspond to movies and edges correspond to strong similarity.

Let’s assume that only the smallest distances constitute edges. With a threshold set so that only 5% of the distances are selected, not allowing self-loops, the movies’ visual similarity graph is:

Distances between images graph

At this rendering scale, we don’t see much more beyond common sense: a large group of interconnected dark posters as well as a second group of light posters that is connected to the dark posters group through saturated colorful poster offshoots. A few movies are isolated, among which is the top-rated movie, The Shawshank Redemption.

While you could use this graph to select a sequence in which to watch the movies, relying only on visual information wouldn’t be very meaningful. For the next step, I will augment the visual graph with semantic information gathered from the genres.

To do so, I introduce new vertices in the graph, one for each movie genre, as well as edges connecting each movie poster with its associated genres. In other words, I combine two graphs—the visual graph computed from the image distances and the semantic bipartite graph where each genre is connected to a list of movies. To compute the visual weighted adjacency matrix, I simply use either the EarthMoverDistance or zero, if the distance is too high, as weights. I also normalize each row of the matrix so that it sums to 1. This allows us to think of the entries in the matrix as probabilities of going from one vertex to the other:

Mv = ArrayPad[adjmatrix*imagedistances, {{0, ngenres}, {0, ngenres}},     0.]; Mv = #/Total[# + $MachineEpsilon] & /@ Mv;

I do not put weight in the semantic adjacency matrix, since we don’t know much about the reliability of the genres:

Ms = ConstantArray[0., {nmovies + ngenres, nmovies + ngenres}]; pos = Position[genres, #][[All, 1]] & /@ lgenres; Do[   (Ms[[i + nmovies, #]] = Ms[[#, i + nmovies]] = 1.) & /@     pos[[i]], {i, Length[lgenres]}]; Ms = #/Total[# + $MachineEpsilon] & /@ Ms;

Finally, the visual and semantic adjacency matrix is a linear combination of the two matrices. Here, I use the average. I obtain the corresponding graph by calling the function WeightedAdjacencyGraph, making sure to indicate an absence of edge using ∞ instead of 0:

Msv = (Ms + Mv)/2; Msv = #/Total[#] & /@ Msv; Gsv =   WeightedAdjacencyGraph[Msv /. 0. -> \[Infinity]];

I can use this graph to compute paths between movies. For example, the shortest path between Toy Story 3 and Citizen Kane occurs by watching Toy Story 3, looking for another comedy, then watching Roman Holiday, and finally Citizen Kane:

idx = FindShortestPath[Gsv, 59, 45]; labels[[idx]]

The function GraphDistanceMatrix allows me to discover the most dissimilar pairs of movies, and it turns out there are two of them, both including Beauty and the Beast:

M = GraphDistanceMatrix[Gsv]; idx = Position[M[[;; nmovies, ;; nmovies]],     Max[M[[;; nmovies, ;; nmovies]]]]; labels[[#]] & /@ idx

Another application is to help moviegoers select their next movie. Based on what they just saw, how can I suggest a few relevant movies? I’ll simply select the five most similar vertices in the graph, implicitly assuming that the moviegoers like any movie they see. For example, to someone who just watched Life of Pi, I’d recommend Toy Story 3, The Killing, The Shawshank Redemption, or browsing the lists of adventures and dramas:

idx = Ordering[M[[195]], 6]; labels[[First[idx]]] -> labels[[Rest[idx]]]

Going further, I can actually model the behavior of a movie buff as he or she sees movies in sequence. I must assume that all the movies from the list are available to my movie buff—many are not lucky enough to have such resources at their disposal.

The process of navigating such a weighted graph based on the probabilities of transitioning from one vertex to the other is called a random walk. Instead of just using the visual and semantic graph’s adjacency matrix as a transition matrix, I’m going to modify it so that it can model boredom. Sooner or later, my movie buff will get tired of watching similar movies in sequence, and looking for fresh air, will switch randomly to another movie. To take into account such behavior, I use as transition matrix a linear combination of the graph’s adjacency matrix and a constant matrix of equiprobable transitions—with the exception that the diagonal entries in this constant matrix are set to 0, because no bored viewer is going to see the same movie again right away:

Mbored = 1 - IdentityMatrix[Length[Msv]]; Mbored /= Length[Msv] - 1;  \[Alpha] = 0.85; Psv = \[Alpha]*Msv + (1 - \[Alpha])*Mbored;

I set the combination factor α to 0.85 because it seems to be a common setting in such systems. The behavior of my movie buff will be modeled thanks to the functions DiscreteMarkovProcess, which represents a random walk process, and RandomFunction, which allows simulation of such processes. For example, here are 10 possible sequences after watching 3 Idiots:

\[ScriptCapitalP] =    DiscreteMarkovProcess[SparseArray[219 -> 1, Length[Msv]], Psv]; idx = Table[    RandomFunction[\[ScriptCapitalP], {0, 6}]["Path"][[All, 2]], {10}];

GraphicsGrid[labels[[#]] & /@ idx, ImageSize -> 450,   Frame -> {{True}, {}}, Dividers -> {False, All}]

As a final application, what is the best way to see all the movies? We are looking for the optimal sequence that would visit all the nodes corresponding to movies exactly once and the nodes corresponding to genres an arbitrary number of times. This is essentially a modification of the traveling salesman problem. There is no immediate solution for this modified problem in Mathematica. Instead, I am going to start from the visual graph and fill up each of its missing edges. Each pair of movies that is too distinct visually will be assigned a distance estimated by finding the length of the shortest path between the two movies in the visual and semantic graph.

The code below is a bit more complicated than that because I must take care of scaling the visual and semantic distances in a sensible fashion. Edges connecting movies to genres are weighted such that a jump through the semantic graph is given a weight of at least the maximum visual distance.

Code for scaling the visual and semantic distances

The optimal sequence is given by the function FindShortestTour:

FindShortestTour function

And here it is, from The Shawshank Redemption to Memento, the optimal sequence in which to see all IMDb’s top 250 rated movies based on visual and semantic similarity:

Grid[Table[   {Thumbnail[images[[i]], 50], titles[[i]]}, {i, idx}],   Alignment -> Left]

The Shawshank Redemption, Rope, Dial M for Murder, Metropolis, Life of Brian, The Big Lebowski, Toy Story 3, Life of Pi, The Killing, Up, The Hustler, The King's Speech, Braveheart, The Bourne Ultimatum, Kill Bill: Vol. 1, Groundhog Day, Life Is Beautiful, City Lights, The Maltese Falcon, Indiana Jones and the Last Crusade, The Wizard of Oz, Monty Python and the Holy Grail, Star Wars: Episode VI - Return of the Jedi, The Thing, To Kill a Mockingbird, The Lion King, Gladiator, Taxi Driver, American Beauty, Paths of Glory, Vertigo, Anatomy of a Murder, The Bridge on the River Kwai, Die Hard, Reservoir Dogs, Apocalypse Now, Django Unchained, Sunset Blvd., Barry Lyndon, Battleship Potemkin, Rashomon, The Perks of Being a Wallflower, Gone with the Wind, Spring, Summer, Fall, Winter... and Spring, The Best Years of Our Lives, A Fistful of Dollars, Bringing Up Baby, The Shining, The Silence of the Lambs, Lock, Stock and Two Smoking Barrels, Inglourious Basterds, Network, Strangers on a Train, The Man Who Shot Liberty Valance, North by Northwest, Sleuth, Incendies, The Good, the Bad and the Ugly, Singin' in the Rain, Into the Wild, Annie Hall, Monsters, Inc., Rocky, Full Metal Jacket, Dog Day Afternoon, Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb, District 9, All About Eve, One Flew Over the Cuckoo's Nest, American History X, A Clockwork Orange, Forrest Gump, Manhattan, Black Swan, The Graduate, Howl's Moving Castle, Fight Club, The Sixth Sense, Unforgiven, There Will Be Blood, The Artist, Casino, Jurassic Park, Spirited Away, All Quiet on the Western Front, The Secret in Their Eyes, Batman Begins, Aliens, Shutter Island, Twelve Monkeys, Amores Perros, How to Train Your Dragon, The Hobbit: An Unexpected Journey, Grave of the Fireflies, 2001: A Space Odyssey, For a Few Dollars More, Persona, The Deer Hunter, Alien, Star Wars, Stalker, The Elephant Man, It's a Wonderful Life, Yojimbo, Toy Story, The Diving Bell and the Butterfly, Star Wars: Episode V - The Empire Strikes Back, Requiem for a Dream, The Matrix, Inception, Jaws, Platoon, The Third Man, Ikiru, Harry Potter and the Deathly Hallows: Part 2, Raging Bull, Star Trek Into Darkness, Who's Afraid of Virginia Woolf?, The Seventh Seal, Heat, V for Vendetta, Nausicaä of the Valley of the Wind, Beauty and the Beast, Ratatouille, Notorious, Hotel Rwanda, Witness for the Prosecution, It Happened One Night, Double Indemnity, Blade Runner, Once Upon a Time in America, Amélie, Warrior, My Neighbor Totoro, The Night of the Hunter, Das Boot, Sin City, Schindler's List, Infernal Affairs, Downfall, Pan's Labyrinth, Rain Man, Back to the Future, The Usual Suspects, The Intouchables, City of God, L.A. Confidential, Pulp Fiction, The Green Mile, No Country for Old Men, The Terminator, The General, The Lives of Others, The Departed, Slumdog Millionaire, The Dark Knight Rises, The Exorcist, La Haine, The Godfather: Part II, Ip Man, Oldboy, The Pianist, Gran Torino, Million Dollar Baby, Mary and Max, The Prestige, Terminator 2: Judgment Day, Star Trek, The Avengers, Goodfellas, Donnie Darko, The Dark Knight, Mystic River, In the Mood for Love, The Big Sleep, Some Like It Hot, The Apartment, Cool Hand Luke, Butch Cassidy and the Sundance Kid, A Streetcar Named Desire, 3 Idiots, The Grapes of Wrath, Mr. Smith Goes to Washington, Roman Holiday, Citizen Kane, Bicycle Thieves, Modern Times, Ben-Hur, Rear Window, The Great Escape, The Lord of the Rings: The Two Towers, The Lord of the Rings: The Fellowship of the Ring, A Separation, Saving Private Ryan, The Lord of the Rings: The Return of the King, Psycho, The Celebration, Seven Samurai, The Truman Show, A Beautiful Mind, Rosemary's Baby, Léon: The Professional, Wild Strawberries, On the Waterfront, Touch of Evil, Chinatown, The Manchurian Candidate, The Godfather, The Wild Bunch, Nosferatu, Scarface, Snatch., Casablanca, The Treasure of the Sierra Madre, La Strada, Stand by Me, The 400 Blows, Like Stars on Earth, Rebecca, Fargo, The Gold Rush, Harvey, 12 Angry Men, Memories of Murder, Finding Nemo, WALL.E, Cinema Paradiso, Good Will Hunting, Se7en, Pirates of the Caribbean: The Curse of the Black Pearl, In the Name of the Father, Ran, Raiders of the Lost Ark, Once Upon a Time in the West, The Great Dictator, High Noon, Eternal Sunshine of the Spotless Mind, The Princess Bride, Stalag 17, Memento
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence
The optimal sequence

From an algorithmic perspective, and maybe for the marathon viewer’s pleasure, it would be interesting in future work to include additional constraints so that movie franchises like The Lord of the Rings are seen in the expected order. Download a companion notebook and start your work on these topics right away.

It was very enjoyable experimenting with these data and models. I was also able to discover new application domains through Mathematica‘s documentation, which contains extensive information on the functionality used here.

Nevertheless, looking back in time, such a program is no match compared to the selections made by the art theater across the street or my dear friends’ suggestions.

Download this post as a Computable Document Format (CDF) file.

Leave a Comment

5 Comments


Arnab Kar

Its a very nice graphical representation of the movies. This result calls for a movie marathon now!

On a different note, I was interested to know how would removing a couple of movies change the path in this movie sequence? Removing movies would change few nodes on this graph and the stability of the graph can be seen then. Some good movies may be critical and their absence but change the results drastically.

Posted by Arnab Kar    July 26, 2013 at 1:47 pm
    Matthias Odisio

    Thanks for the kind words. You are asking an interesting question. The concept of graph centrality is what you are after, though it can’t answer you directly. Mathematica features various measures for centrality, including ClosenessCentrality (http://reference.wolfram.com/mathematica/ref/ClosenessCentrality.html). In the last graph I used to compute the shortest tour, the most central nodes are “Memento”, ” Rear Window”, “Full Metal Jacket”, “A Clockwork Orange”, and “The Lion King.”

    Posted by Matthias Odisio    July 26, 2013 at 4:00 pm
      Arnab Kar

      Thanks Matthias. I did not know about this Mathematica function. It certainly helps to resolve issues about centrality and find which nodes are redundant in graph and their removal does not affect it much. I must say that the list of movies of high priority is interesting. Memento can indeed connect many movies given its theme and so also Lion King.

      Posted by Arnab Kar    July 27, 2013 at 3:01 pm
rojolon

Some imdb and math mix.
People usually watch movies they know, and so what they will watch stuff biased towards what they know. And what they like is biased towards that.
One way to fix that is to get a random movie based on all movies and watch it.
This will not be biased towards movies you know that exist, you will not all movies on imdb, this will also not be biased towards time you have to discover stuff, this will not be biased towards situations (you will maybe only discover some porn fetich movie if you were on a site about this fetiche) and so….

So a way to fix those problems would be to watch random movies from imdb.
But the thing with this way of movie discovery is that when you “hit you hit hard”, but most of the time you will fail and will not get good movies. Your movie taste is just one in a world of many different movie tastes.
A way to solve that is to check the movie info before you watch and only watch the ones you think will be good, but sometimes you think a movie will be bad and then you see the movie was good. How to fix this problem?

Math can help, this is how you do the entire process:

1-find a way to get random IMDB movie
2- get the 1 random movie and watch it (get the first 2 random ones you can find to watch)
3-now make a list with the amount movies you were forced to watch (X) and the amount of those forced movies you liked (Y)
4-do this math 100/((X+1) / (Y+1))
4.1-if you hated the first movie the value will be 50. That is [100/((1+2) /(0+1))]
5-now get a new random movie
6-check if you like it by looking at info
7-if like watch it
8-Remember the value you got at 4? If you hated it, this is the chance of you have of being forced to watch this movie. Roll a random number to find it
9-go back to 3

Posted by rojolon    October 27, 2013 at 4:23 pm


Leave a comment

Loading...

Or continue as a guest (your comment will be held for moderation):