City AD: schoolchildren and students

A table with lines like user_id, item_id, channel, time.

• user_id - viewer id
• item_id - movie id
• channel - channel identifier
• time - time (timestamp)

Each such four means that at the moment of time user user_id liked the movie item_id ,
which went on channel .

Metadata about movies in json format (opens with any standard json module). Each line must contain:

• id - movie id
• duration - the duration of the movie
• year - production year ratio
• genre - genre number (categorical variable, 10 genres in total)
• f_ {number} - additional features (see below).

The coefficients of the duration and year - the arithmetic transformation of the duration of the film and the year of release, made in order to save personal data.

Signs of f_* are various anonymized signs of the film. Examples of such signs are “Production Country — USA” or “Budget is greater than $ 100k” (yes — 1, no — 0 or not present).

Important. Not all films have a description line: about 2/3 of the films that were stuck are described.

A table with lines of the form time_end, time_start, item_id, channel .

• time_end - transfer end time
• time_start - the start time of the transfer
• item_id - movie id
• channel - channel id

tl; dr: https://github.com/goto-ru/2016.09-school-baseline .

The baseline we have prepared is based on the second idea - collaborative filtering.
In our algorithm, we use only data about likes, forgetting about the signs of the film. This is a very rough assumption, for sure, entering information about the content of the film will significantly improve the result, try it.

The idea behind the root of our method is as follows:

• user likes the same movies as similar users
• the movie is watched by the same users that watch movies similar to it

In other words, each user has some unknown set of interests that determines which films he likes. The film, in turn, also has a profile that is responsible for how much the audience likes it. We do not know the psychological profile of each user and the audience of each film, but we can restore it using the above ideas.

Cosine measure

First, we will consider an intuitive way of solving the problem, based on how the user is suitable for the movie audience.
We present the data in the format of the -> . The recommendation of the item movie to the user user is calculated as follows:

• For each movie polynkannogo user, we find other people who liked the movie.
• Let's put all such “friends on likes” together and call them the neighbors (neighborhood) of the user.
• For an item movie, find out its audience - many users who liked it
• The suitability of a movie to a user is how much the user's “like friends” like this movie.

Detailed description of the algorithm .

This method is probably better than random fortune telling, however, it treats all the "neighbors" of the user in the same way, guided only by the number of times they have watched the same films.
Since users usually watch quite a few films, it will often turn out that two users with almost perfectly coinciding interests do not have “common” films, although the films of one user would have liked the other if he knew about them.

Svd

In order to correct this shortcoming, we will try to move from "users who have watched movies watched by another user" to explicitly obtain "user interests" and "movie audience". This move will greatly improve the quality of the result.

So, math .

The rich inner world of the user and the artistic depth of the film must somehow be encoded, and even so that it is easy to understand how close two users are, two films or how much the film fits the user.

We probably don’t want to do this with our hands, so like all normal mathematics we say that the user's soul is limited to a vector of several numbers. Knowing the complexity and versatility of human nature, we will allocate as much as 100 numbers (of any real numbers). What exactly are the numbers - do not yet know.

For fidelity, we will also match 100 numbers. In the language of mathematicians, we have just introduced 2 vectors - the vector of "user interests" and the vector of "film audience". In the language of programmers, we declared 2 arrays, did not specify them at all, and we show off without any reason.

Now let's understand what we want from these vectors.
Let's say that vectors are "similar" if their scalar product is large. How big is this scalar product, too, do not say - we are mathematicians! We can only say that similar users have more than dissimilar ones. The same with movies - let similar films have a scalar product larger, and unlike films smaller.

Finally, the most important thing is that we have a user vector, we have a movie vector. Let's want the scalar product of the vector of the user to the vector of the film to be as close as possible to 1 if the user likes this movie, and to 0 if they do not like it or not.
Why so - yes, that's what they wanted. It might have been desirable that if the film was not to be liked, it was -1, and if they didn’t watch it, it was 0, but unfortunately, we only have “likes” of users - there are no dictionaries in the sample.

And now let's move to a larger scale. We have several tens of thousands of users and even more - movies.
We also know that such users like this movie.

We will be generous, give 100 numbers to each user, and even to each film. We can do it this way - the number in float32 weighs 4 bytes, and we need these numbers according to rough estimates (number of users + number of films) ~ 10 ^ 5.
We need the main condition to be fulfilled: the scalar product of the user's soul to the movie audience should be closer to 1 if the user likes the movie, and 0 if not like.

Let's call a vector of that user vector of that film . For simplicity of notation, - All users, - all movies.

Achieving perfect equality is most likely not possible, and the fewer numbers we give per soul / film, the worse the approximation will be, but we will be satisfied if the scalar product is just close enough to the correct value.
In the language of mathematicians, such a task is called an optimization problem: we want to select such vectors of users and films so that the error is minimal:

Where if user liked otherwise 0.

Finally, to fit the methods of well-known mathematicians, we introduce for each of the 100 components of the "importance" vectors - the same for all users / films. Formally, this is the S vector, in which again there are 100 numbers.

From deliberately limiting the number of numbers in the vectors to 100, not allowing us to perfectly fit all likes and non-likes, we are only better off:

• We train our model on those likes that are in the sample. If we give ideal units on polikan films and ideal zeros on non-polished ones, we cannot recommend the user any films other than those that he has already watched.
• If our algorithm is specifically co-ordinated, then on some films from among the non-tiled ones, the algorithm will produce a large scalar product - by mistake. In other words, it seems that the interests of the user fall under the typical audience of the film, but the trouble is that in fact the user did not like this film.
• In fact, this is no mistake - if the movie is so suitable for the user, but he hasn’t liked it yet, then it's time to recommend the movie to the user, and the user is likely to like it.

Moving from idea to implementation and from concept to specific methods and data structures: in a simple form, it suffices to take only user_id <-> film_id from train_likes.csv ; each such pair means that the user user_id watched the film_id (and there is also time and channel in the same file, which we now ignore). We build from these relationships a sparse adjacency matrix, to which we apply Truncated Singular Value Decomposition. This method compresses the original matrix, trying to find such a hidden feature space where the feature vectors of users and films they like are close; we get the kth order approximation. After this compression, we reconstruct the original matrix - with some error. It is thanks to this error that everything works: well, films that the user has not watched, but who like users like him, will now have a value not of 0 , but 0.4 , because we could not save all the data under compression, and the user "mixed" with those similar to himself.

The code is based on the above: matrix decomposition and reproducible notebooks to watch for free without SMS .

Once again we emphasize that the above uses only the minimum possible data: whether the user watched a movie or not. Considering additional metadata (for example, genre or time of display), one can significantly improve the quality of prediction; a combination of collaborative and content filtering methods (through initialization, for example, a matrix of feature films derived from metadata) is the next logical step on a slippery data analysis track in solving this problem.

Recommended interface: it is desirable that your program has a function ( example ) that takes parameters (user_id, film_id, additional information) and returns the predicted confidence of the model in like. To calculate the ranking metrics you also need a ranking interface : (user_id, k) -> Sequence[confidence] .
The main thing that will affect the assessment is the performance of the solution (significantly better than at random), the validity of the assessment of the quality of the decision, and only then the final quality. A simple working solution that is honestly analyzed is always better than an insane mixture of everything that you found on the Internet, about which it is not clear how it works and an overestimation of quality. Machine learning is desirable but not necessary.
In addition to such a system, I would like to receive a report from you in an arbitrary format, from which you can understand exactly what you did and why, as well as how you evaluated the quality of your recommendation system. The recommended maximum report size is 3000 characters, including spaces: (assert len(u""" """) <=3000) .