Life is full of uncertainties — what the weather will be like on a specific day, what time we will arrive at work, or even just whether the cup of coffee in front of us will be any good. Each possible outcome of an ‘event’ – whether that event is the weather, which road to take to work, or which candidate we will vote for in an election – has a certain probability of realising. For example, the probability of it being a sunny day in December in Cape Town is much higher than it being a cloudy, rainy day.
If we want to predict tomorrow’s weather, there are certain factors that we look at. For example, the current season, today’s weather and geographic location. These factors will all influence our prediction of tomorrow’s weather, though not all factors are weighed equally. Note though that the ‘factors’ themselves are also events that have probabilities attached to them. For example, the probability of tomorrow being in the season of summer is 0.25 (or 25%). Just as the season has an influence on the probability of tomorrow’s weather, so does tomorrow’s weather have an influence on predicting the season — if tomorrow’s weather is hot and sunny, it is more likely that it is summer than winter. We therefore have a system of events, all having more than one possible outcome, and influencing the different possible outcomes of each other.
The above example is quite simple, and we can easily work out the different probabilities of the different outcomes. However, there are numerous situations in which the systems quickly become too large to do the calculations by hand. For example, if we want to model a social network, we would model the different users as the ‘events’ – each user of course then has different properties that can have different possible outcomes. Each user is influenced by their friends – to a lesser or greater degree – and so the probabilities of the possible outcomes and influenced by the network. Physical trait properties aren’t likely to be influenced by other users, but a property such as language literacy can be influenced (or at least inferred from) a user’s friends’ language literacy. [if user A is just English and user B is just Afrikaans then a friendship between the two users is unlikely to be very strong, but if it is, then they will no doubt end up teaching each other Afrikaans/English]. It is in these complex systems that we would like to find a method of modeling that will help us see structures, and make inferences about different situations.
The modeling technique known as graphical models takes the probabilities as described above, and represents it graphically, using graph theory. The events are modeled using nodes (circles) and the connections/dependencies between events are shown by adding an edge (line) between the appropriate nodes. Using the weather example, we have the graphical model:
Note that although the edges in the above diagram are undirected [i.e. there are no arrowheads], graphical models have either directed edges — creating a Bayesian Network — or undirected edges — creating a Markov Random Field. For the current purposes, this is not important.
Using the graphical model, we can now apply various algorithms to extract information as we deem necessary – using either specialised algorithms, or normal graph theory algorithms.
One of the advantages of graphical models is that they are modular – meaning that the big system is made up of smaller elements. If the smaller elements are consistent [and this will be the case if we abide by the rules governing probabilities and statistics], the probability theory that has been incorporated in the graphical model will ensure that the entire system remains consistent. Although it won’t be discussed, a very important condition to using graphical models is that there should be some independences (albeit conditional). If all variables (events) are dependent on each other, then using graphical models will have no advantage over any other system. So although it is possible to use graphical models when all variables are dependent on each other, it will not be the best way to solve a problem.
There are two situations wherein graphical models can be used – probabilistic and statistical inference. In probabilistic inference we already have the distributions (or the probabilities that certain outcomes will be reached) of the variables (events). An example of this is predicting what tomorrow’s weather will be like. Statistical inference is used to actually find these probabilities, based on observed data. So, for instance, an entire year’s weather data can be collected, and then used to form the different distributions (what the weather is like during specific times of the year). These can then be used to see when which seasons are, what the most likely geographic location is (if we know the different geographical location’s weather) and then also used to guess what tomorrow’s weather will be.
Graphical models are therefore used in situations where there is at least some independence between variables, and to either infer certain information (like the probability of a specific event occurring, or the most likely outcome to an event) or use observed data to build graphical model which can then be used to make inference from.
Some areas that graphical models are used in currently are computer vision, pattern recognition, machine learning, social networks, music, economics, semantic search, social sciences and software testing, to mention but a few.
About the author: MIH Swat sponsors bursaries for post graduate studies at the University of Stellenbosch Media Lab – I was part of the first group that was sponsored in 2008. Following my Masters in Applied Mathematics, I’ve been privileged enough to start working at MIH SWAT. My studies focused on using graphical models in the field of Computer Vision. Graphical models, however, is a technique that can be applied in many different situations to solve complex problems quickly and easily.
Related Posts
