February 28, 2017 at 09:38Probabilistic Scala Programming
- Transfer
Hello dear readers. Today we publish an extraordinary translation - this will be a review article by the brilliant Noel Welch on the principles of probabilistic programming. The article is published at the request of readers who set our blog ever higher bar - and this is certainly great!
At the Typelevel Summit conference in Philadelphia, I had the opportunity to give a talk on probabilistic programming, which I have been interested in for some time. Probabilistic programming is at the junction of two posh research areas that combine well with each other - talk about functional programming and machine learning (more specifically, Bayesian inference). In this article I will try to explain the key ideas of probabilistic programming. I assume that you, dear reader, are more of a programmer than statistics, but the numbers do not scare you either. Therefore, I will pay more attention to programming, not to machine learning.
Probabilistic Models and Inference
To understand probabilistic programming, you first need to understand probabilistic models and logical inference. A probabilistic model describes how observed phenomena can depend on phenomena that we cannot observe. It is usually assumed that such a relation is not deterministic, therefore, the relationship between the observed and the unobservable is subject to a certain probability distribution. A model of this type is sometimes called a generative one.
Suppose a doctor tries to make a diagnosis. He observes various symptoms - for example, fever, rash, shortness of breath - on the basis of which he can make an informed guess about what disorder could cause such symptoms. Of course, this process is imperfect. Different diseases can cause very similar symptoms, as well as the symptoms of the same disease often differ, therefore such a diagnostic model assumes a certain probabilistic distribution of the results.
Let's take a closer look at another example. Suppose we want to sort the documents according to the topics covered in it - perhaps in order to recommend people reading that they might like. In this case, we can simulate such a generative process:
A model of this type is called thematic and is widely used. Some relatively unusual options for its use include the classification of aesthetic preferences in Etsy and an attempt to figure out which rooms were used in one of the surviving houses in Pompeii .
I hope these brief examples are enough, and you grasped the idea of probabilistic models. You can imagine many other generative processes - for example, the properties of the celestial body affect the way we observe it, the online behavior of the user depends on his interests, and the activities of NGOs affect the health situation in the region where such an organization operates. .
Generative models work well in cases where we have a priori knowledge about the structure of the world, and we can use them to build the model. Working with them is very fun, because they allow you to create fictitious data, for example, automatically generated scientific articles - and thereby embarrass and amuse our colleagues.
When we created a probabilistic model (and had lots of fun with fake data), this model can be used for logical inference. The logical conclusion is the process of "rewinding the model." We look at the real data that we were able to observe, and try to guess how a situation that could not be observed could have looked. For example, you can use the text of the document and try to find out what topic it is dedicated to, or collect astronomical data and try to determine which star systems are most likely suitable for life. Since we cannot confidently judge the state of these unobservable elements of our model, we can construct a probabilistic distribution of all the possibilities. The creation of such a distribution distinguishes Bayesian output from alternatives - for example,
Why probabilistic programming is needed
We have briefly described the generative models and the Bayesian inference problem. This area of statistics and machine learning has long been studied, and over time, researchers noticed a number of points:
It would be great if we could make an inference algorithm based only on the model description. The situation can be compared with assembly and high-level programming. Using the assembler, we optimize everything manually, implement our own and control structures, etc., in the context of the specific problem facing us. The same thing happens when creating a special inference algorithm for a specific generative model. When programming in a high-level language, we use ready-made constructions, which the compiler translates into assembler. Productivity increases significantly at the cost of a slight decrease in machine productivity (which we often don’t even notice). The goal of probabilistic programming is exactly that.
Of course this is a monad!
It seems that the goal of probabilistic programming is worthwhile and noble, but in order to achieve it, you first need to understand how to structure our generative models. An experienced functional programmer should not be surprised that we will use the monad for this. Now I will explain how.
Let's go back to the example with the generative model for creating a document. To create a document, you need:
You can annotate this model with types to show how the problem can be solved. Using,
(Here we try to balance simplicity and accuracy, so our model does not take into account the grammar or the number of words that make up the document. Perhaps you can complete it, but if you get confused, check out my report, which provides a simpler and more complete example. )
The main part of this model is to connect
The answer is
If you have ever worked with ScalaCheck or similar systems, then you used the security monad.
Building Inference Algorithms
There are many ways to implement the probability monad. If we are dealing only with discrete domains, then everything can be represented inside the domain as
You can use a selection based view. This approach works with solid domains, and the user can create as many samples as he wants - to achieve the desired accuracy. However, this option is still imperfect. Inference algorithms have been studied for many years, this work is reminiscent of compiler optimization, and we would like to create a system that would run probabilistic mechanisms to analyze the structure of the program and apply the optimal inference algorithm to the results. Just like when working with the compiler, we express the probabilistic program in the form of an abstract syntax tree, which can then be manipulated by optimization algorithms.
Now you can start building logical inference algorithms, and it is here that I am self-explanatory, for two reasons: first, I believe that the reader is not a pro in machine learning, and it will not be very interesting to discuss logical inference algorithms, but second, which, in fact, is more important - while this is the forefront of research. In modern systems, generalized inference algorithms are implemented, which, however, are almost not suitable for problem-oriented optimizations. The general principle, as with compilers, is this: the more information you save, the more you can optimize. At the same time, most optimizations are useful in only a few programs. In many ways, the question remains, how much can you rely on generalized inference algorithms and on computing power,
Conclusion and further work
I am very enthusiastic about probabilistic programming, because, I believe, it allows you to radically simplify the logical conclusion, and this will come in handy in so many areas - I have already given a few examples above. In most subject areas, the question of time is not so critical, so I'm more interested in the study of generalized inference algorithms and parallel / distributed implementations than complex mathematics. However, I like to run any things first in practice, and therefore I am looking for people who need to solve real problems.
In addition, probabilistic programming pretty much overlaps with my interests in machine learning and programming languages. If you are interested - here is a report , slides ,code .
At the Typelevel Summit conference in Philadelphia, I had the opportunity to give a talk on probabilistic programming, which I have been interested in for some time. Probabilistic programming is at the junction of two posh research areas that combine well with each other - talk about functional programming and machine learning (more specifically, Bayesian inference). In this article I will try to explain the key ideas of probabilistic programming. I assume that you, dear reader, are more of a programmer than statistics, but the numbers do not scare you either. Therefore, I will pay more attention to programming, not to machine learning.
Probabilistic Models and Inference
To understand probabilistic programming, you first need to understand probabilistic models and logical inference. A probabilistic model describes how observed phenomena can depend on phenomena that we cannot observe. It is usually assumed that such a relation is not deterministic, therefore, the relationship between the observed and the unobservable is subject to a certain probability distribution. A model of this type is sometimes called a generative one.
Suppose a doctor tries to make a diagnosis. He observes various symptoms - for example, fever, rash, shortness of breath - on the basis of which he can make an informed guess about what disorder could cause such symptoms. Of course, this process is imperfect. Different diseases can cause very similar symptoms, as well as the symptoms of the same disease often differ, therefore such a diagnostic model assumes a certain probabilistic distribution of the results.
Let's take a closer look at another example. Suppose we want to sort the documents according to the topics covered in it - perhaps in order to recommend people reading that they might like. In this case, we can simulate such a generative process:
- Select several topics and assign them weight categories;
- Each topic has its own distribution of words;
- Based on this distribution of words, we select the specific words read on the page in proportion to the weight categories assigned to one or another topic.
A model of this type is called thematic and is widely used. Some relatively unusual options for its use include the classification of aesthetic preferences in Etsy and an attempt to figure out which rooms were used in one of the surviving houses in Pompeii .
I hope these brief examples are enough, and you grasped the idea of probabilistic models. You can imagine many other generative processes - for example, the properties of the celestial body affect the way we observe it, the online behavior of the user depends on his interests, and the activities of NGOs affect the health situation in the region where such an organization operates. .
Generative models work well in cases where we have a priori knowledge about the structure of the world, and we can use them to build the model. Working with them is very fun, because they allow you to create fictitious data, for example, automatically generated scientific articles - and thereby embarrass and amuse our colleagues.
When we created a probabilistic model (and had lots of fun with fake data), this model can be used for logical inference. The logical conclusion is the process of "rewinding the model." We look at the real data that we were able to observe, and try to guess how a situation that could not be observed could have looked. For example, you can use the text of the document and try to find out what topic it is dedicated to, or collect astronomical data and try to determine which star systems are most likely suitable for life. Since we cannot confidently judge the state of these unobservable elements of our model, we can construct a probabilistic distribution of all the possibilities. The creation of such a distribution distinguishes Bayesian output from alternatives - for example,
Why probabilistic programming is needed
We have briefly described the generative models and the Bayesian inference problem. This area of statistics and machine learning has long been studied, and over time, researchers noticed a number of points:
- Building a generative model is pretty easy; and
- all these models have the same structure; but
- the inference algorithm for each particular model is written slowly, and usually errors occur.
It would be great if we could make an inference algorithm based only on the model description. The situation can be compared with assembly and high-level programming. Using the assembler, we optimize everything manually, implement our own and control structures, etc., in the context of the specific problem facing us. The same thing happens when creating a special inference algorithm for a specific generative model. When programming in a high-level language, we use ready-made constructions, which the compiler translates into assembler. Productivity increases significantly at the cost of a slight decrease in machine productivity (which we often don’t even notice). The goal of probabilistic programming is exactly that.
Of course this is a monad!
It seems that the goal of probabilistic programming is worthwhile and noble, but in order to achieve it, you first need to understand how to structure our generative models. An experienced functional programmer should not be surprised that we will use the monad for this. Now I will explain how.
Let's go back to the example with the generative model for creating a document. To create a document, you need:
- select several topics and their corresponding weight categories;
- each topic regulates the distribution of words;
- From these word distributions, we select the specific words read on the page in proportion to the weight categories corresponding to the topic.
You can annotate this model with types to show how the problem can be solved. Using,
Distribution[A]imagine a distribution of type A. Now the document is generated as follows:- select some topics - this is how we can get
Distribution[Seq[Topic]](or justDistribution[Topic]for a simpler model). - from each topic we get a word distribution - this is a function
Topic => Distribution[Words]. - from these word distributions we select specific words that we read on the page - extraction is done from
Distribution[Words].
(Here we try to balance simplicity and accuracy, so our model does not take into account the grammar or the number of words that make up the document. Perhaps you can complete it, but if you get confused, check out my report, which provides a simpler and more complete example. )
The main part of this model is to connect
Distribution[Topic]and Topic => Distribution[Words]create Distribution[Words], from which you can build a document. By the way, what needs to be replaced ???so that the next identity is respected?Distribution[Topic] ??? Topic => Distribution[Words] = Distribution[Words]The answer is
flatMap, that is, we have a monad. (You can see for yourself that the monad laws are also respected, however, in this case we need to determine the semantics flatMap. See below.) If you have ever worked with ScalaCheck or similar systems, then you used the security monad.
Building Inference Algorithms
There are many ways to implement the probability monad. If we are dealing only with discrete domains, then everything can be represented inside the domain as
List[(A, Probability)](where it Probabilitycan be an alias of typeDouble) and precisely calculate the results. In real applications, the benefit of this approach is small, since we are likely to have to deal with solid domains, or discrete, but still large. Then the size of the view in each flatMapwill grow exponentially. An example implementation is shown here .You can use a selection based view. This approach works with solid domains, and the user can create as many samples as he wants - to achieve the desired accuracy. However, this option is still imperfect. Inference algorithms have been studied for many years, this work is reminiscent of compiler optimization, and we would like to create a system that would run probabilistic mechanisms to analyze the structure of the program and apply the optimal inference algorithm to the results. Just like when working with the compiler, we express the probabilistic program in the form of an abstract syntax tree, which can then be manipulated by optimization algorithms.
Now you can start building logical inference algorithms, and it is here that I am self-explanatory, for two reasons: first, I believe that the reader is not a pro in machine learning, and it will not be very interesting to discuss logical inference algorithms, but second, which, in fact, is more important - while this is the forefront of research. In modern systems, generalized inference algorithms are implemented, which, however, are almost not suitable for problem-oriented optimizations. The general principle, as with compilers, is this: the more information you save, the more you can optimize. At the same time, most optimizations are useful in only a few programs. In many ways, the question remains, how much can you rely on generalized inference algorithms and on computing power,
Conclusion and further work
I am very enthusiastic about probabilistic programming, because, I believe, it allows you to radically simplify the logical conclusion, and this will come in handy in so many areas - I have already given a few examples above. In most subject areas, the question of time is not so critical, so I'm more interested in the study of generalized inference algorithms and parallel / distributed implementations than complex mathematics. However, I like to run any things first in practice, and therefore I am looking for people who need to solve real problems.
In addition, probabilistic programming pretty much overlaps with my interests in machine learning and programming languages. If you are interested - here is a report , slides ,code .
