Recommender systems: Bayes theorem and naive Bayes classifier / Surfingbird Blog

In this part, we will not talk about recommender systems as such. Instead, we will separately concentrate on the main tool of machine learning - the Bayes theorem - and consider one simple example of its application - the naive Bayes classifier. Disclaimer: I’m unlikely to report something new here to a reader familiar with the subject, we will mainly talk about the basic philosophy of machine learning.



Bayes' theorem is either remembered or trivially deduced by anyone who has taken at least the most-basic course of probability theory. Remember, what is the conditional probability of an event x under the condition of event y ? By definition , where is the joint probability of x and y , and p( x ) and p ( y ) are the probabilities of each event separately. Hence, the joint probability can be expressed in two ways:
.

Well, here’s Bayes’s theorem:


you probably think that I am mocking you - how can trivially-tautological rewriting of the definition of conditional probability be the main tool of anything, all the more such a large and non-trivial science as machine learning? However, let's begin to understand; first, we simply rewrite Bayes' theorem in other notations (yes, I continue to mock):


Now, let's relate this to a typical machine learning task. Here D is the data, what we know, and θ are the model parameters that we want to train. For instance,in the SVD model, data are those ratings that users put to products, and model parameters are factors that we train for users and products.

Each of the probabilities also has its own meaning. - this is what we want to find, the probability distribution of the model parameters after we take into account the data; this is called posterior probability . This probability, as a rule, cannot be directly found, and Bayes' theorem is needed here. Is the so-called credibility(likelihood), probability of data provided that the model parameters are fixed; this is usually easy to find, in fact, the design of the model usually consists in setting the likelihood function. A is a prior probability, it is a mathematical formalization of our intuition about an object, a formalization of what we knew before, even before any experiments.

Here, probably, there is no time and no place to delve into this, but the merit of Rev. Thomas Bayes was, of course, not to rewrite the definition of conditional probability in two lines (there were no such definitions then), but to put forward and develop this view of the very concept of probability. Today, the “Bayesian approach” refers to the consideration of probabilities from the perspective of “degrees of confidence” rather than the freakventist (from the word frequency, not freak!) “Share of successful experiments while tending to the infinity of the total number of experiments”. In particular, this allows us to talk about the probabilities of one-time events - after all, there really is no “number of experiments tending to infinity” for events like “Russia will become the world football champion in 2018” or, closer to our topic, “Vasya will like the movie“ Tractor drivers ""; it’s more like a dinosaur: either like it or not. But mathematics, of course, is the same everywhere, the Kolmogorov axioms of probability do not care what they think about them.

To consolidate the past - a simple example. Consider the task of categorizing texts: for example, suppose we are trying to sort a news flow by topic based on an existing database of topics: sports, economics, culture ... We will use the so-called bag-of-words model: represent a document (multi) in a multitude words that it contains. As a result, each test case x takes values ​​from the set of categories V and is described by attributes . We need to find the most probable value of this attribute, i.e.

By Theorem Bayesian


Rate is easy: we simply evaluate the frequency of its occurrence. But you won’t be able to evaluate different ones - there are too many of them,- This is the probability of the accuracy of such a set of words in messages on various topics. Obviously, there is no place to take such statistics from.

To cope with this, the naive Bayes classifier (sometimes called idiot's Bayes) assumes the conditional independence of the attributes provided that the objective function has the given value:

Now it’s much easier to train individual ones : it’s enough to calculate the statistics of the occurrence of words in categories (there is one more detail , which leads to two different variants of naive bayes, but we will not go into details now).

Note that the naive Bayes classifier makes a damn strong assumption: in the classification of texts, we assume that different words in the text on the same topic appear independently of each other. This, of course, is complete nonsense - but, nevertheless, the results are quite decent. In fact, the naive Bayes classifier is much better than it seems. His estimates of probabilities are optimal, of course, only in the case of true independence; but the classifier itself is optimal in a much wider class of problems, and here's why. Firstly, the attributes are, of course, dependent, but their dependence is the same for different classes and is “mutually reduced” when assessing probabilities. The grammatical and semantic dependencies between the words are the same in the text about football, and in the text about Bayesian training. Secondly,and , naive bayes will give out and , but the classification will be more often correct).

In the next series, we will complicate this example and consider the LDA model, which is able to highlight topics in the document body without any set of marked documents, moreover, so that one document can contain several topics, and also apply it to the recommendation task.