The structure of online diffusion networks

This research was developed by some people who were working at Yahoo! Labs at the time. One of the authors is Duncan Watts, who is now affiliated to Microsoft Research. The main topic of the paper is viral marketing. More specifically, the authors study how much of the total adoption of an object (e.g., URL, product) is due to viral spreading. In other to support their findings, they analyze spreading processes  in  7 different scenarios.

For a long time, the research community has tried to model diffusion as an epidemic process. In particular, these disease-like models are expected to produce an "S shaped" cumulative adoption curve. Further, threshold models, in which users have minimum adoption levels to be reached before they become adopters, became popular. Moreover, network models of adoptions, where users' actions depend on a small set of neighbors and both local and global structural features could influence the size and the likelihood of cascades, attracted the interest of the research community. In particular, this models motivated several studies on the selection of a small number of nodes that could maximize the influence over the network. From an optimization perspective, other studies focused on the trade-off between the cost of activating a seed set and the global influence achieved by these nodes in the diffusion process. However, the generation of large cascades due to diffusion processes still lacks empirical evidence.

A cascade is composed by a seed node, which took action independently from other nodes, and a set of non-seed nodes influenced either directly or indirectly by the seed to take the same action. In this paper, the authors consider tree representations of cascades. The source of influence is always the earliest parent of the affected node. This study characterizes these cascades in terms of size, depth, and the proportion of the total adoption due a given isomorphic class of cascades. 

The datasets applied in this work are:

• Yahoo! kindness: Website that asked users to describe and share their acts of kindness through Facebook, Twitter, etc. Diffusion is tracked through a unique URL given to each user. The dataset contains 59K users.
• Zync: Plugin for watching videos with contacts in the Yahoo! IM applications. A diffusion occurs whenever an invitation to share a stream is accepted.  This dataset contains 374K users.
• The secretary game: Online game. Players were encouraged to share their (unique) game URL. The total number of adopters is 2.9K.
• Twitter news stories: Collection of 80K news stories posted by NYT, CNN, MSNBC, Y! News, and Huffington Post on Twitter. Adoptions means sharing a URL and the number of adoption events is 288K.
• Twitter videos. 540K Youtube videos posted on Twitter. An adoption occur whenever a user posts a link to a video. There are 1.3M adoption events.
• Friendsense: Third-party Facebook application that asked users about their political views and also their beliefs about their friends' political views. The dataset contains 2.5K users, 100K answers and 80 questions.
• Yahoo! Voice: Paid VoIP service supported by Yahoo! Messenger. An adopter is someone who bought Y! Voice credits and cascades are identified according to the interactions in the Yahoo! IM network. The dataset is composed by 1.8M users.

Results show that, in general, cascade trees are small. The most frequent cascade size is 1 and cascade size distribution is very skewed. The authors investigate whether a small number of large cascades would create a significant proportion of the adoptions and find that this is not the case. Less than 10% of the adoptions occur in cascades with more than 10 nodes. Moreover, the vast majority of adoptions occur within 1 generation of the seed node.

Based on this results, the authors make several interesting points about the impact of their discoveries over our understanding of viral marketing. In fact, they challenge the common belief that a small set of users may produce large cascades in real scenarios. On the other hand, they also discuss how different results could be found in case adoptions were associated to explicit incentives or in scenarios where the adoption is automatic, such as in email viruses. The following figure shows some of the largest cascades found in the Twitter datasets. Colors represent cascade levels (i.e., distance from the seed node).

This paper is very well-written and has a very clear contribution. I appreciated the literature review, which gave a historic view on information diffusion research. However, the paper lacks a further step in the direction of alternative models able to capture the main properties of adoption cascades found. In fact, it seems that this further step was left as a future work. Let's wait and see what comes next.

Link: http://5harad.com/papers/diffusion.pdf

Congress of the Brazilian Computer Society

I've attended the 2012 edition of the Congress of the Brazilian Computer Society (SBC) that run from July 16-19 in Curitiba, Parana. The conference was nice, except for the tragic death of  several students that were traveling by bus from Belem, Para in order to attend the Congress. For several moments, it was sad to think that these fellow students could be there learning and sharing experiences with us but, for reasons I cant explain, they were prevented to do so.

I had the opportunity to present my M.Sc research on correlating vertex attributes and community structure in attributed graphs at the Thesis and Dissertation Contest and I'm very honored that my work was selected as best M.Sc thesis of 2011. The other nine competitors presented really great research work on several topics, such as Software Engineering, Linked Data, Graph Theory, Grid Computing, Information Retrieval, and Optimization. In fact, I was not expecting that my thesis would be selected as the best one among so many interesting work. I think that my talk was very convincing, specially because I had practiced it a lot and also because I took several comments from my colleagues and advisor in order to improve it.   Another aspect that may have played a key role is that my M.Sc research goes from a general and intuitive problem to some cool theoretical and empirical results. As a consequence, I was able to catch the attention of the audience and the reviewers with a lot of cool examples, a little bit of math, some algorithmic techniques, and performance evaluations. Organizing a research project as a sequence of related research questions seems to be a powerful presentation strategy and I should keep employing it in the near future. I think this award is a good signal that I'm evolving as a researcher, which is a great motivation to keep working hard.

I also presented a recent work on detecting relevant content and influential users on Twitter at the first edition of the Brazilian Workshop on Social Network Mining. In this case, my presentation was terrible. I was tired because of the previous talk in the same day. Also, the slides were poor and I had not practiced the talk at all. Unfortunately, I went beyond the time limit, what makes things even worse. Nevertheless, our paper won the best paper award at the event (by my surprise again). That was my first best paper award and I'm very proud about it too. Now I'm working to turn those preliminary results into a full conference paper. The workshop was a lot of fun, specially because I had the opportunity to ask a lot of questions after the talks. I don't know why, but Brazilian researchers usually do not ask questions. I think this behavior is very disappointing. Questions indicate that the talk was relevant for the audience and have several benefits such as helping the presenter to improve his presentation skills and supporting more and better research. In particular, I think that questions are very important for students and young scientists.

The congress was a great opportunity to talk with several colleagues from UFMG and other universities as well. The conference dinner was really nice, though I've heard several complains about the event organization in general. 

My first impression of Curitiba was very positive. Different from my friends, I liked the weather (about 10 °C during the winter) and the people. Moreover, the transit and the public transport are much better than those of Belo Horizonte Metropolitan Area, where I live. I had a few hours to make a very fast bus tour around the city. The picture included in this post was took at the Tangua Park during the sunset.

Information seeking: Convergence of search, recommendation and advertising

This paper is one of those that try to give a broader view on a recent research problem. In particular, this paper is focused on the idea of integrating search, recommendation, and advertising into a unique system. The authors are from Stanford and include Hector Garcia-Molina who is pretty famous in the Database Management research community.

The motivation for the convergence among search, recommendation, and advertising is the so called "deluge of data" (or information overload). In this scenario, a fundamental problem consists of identifying objects that satisfy a user's information needs. The authors highlight three important mechanisms related to information providing:

• Search: Return a set of objects from a collection based on a user query;
• Recommendation: Return a set of object of the interest of a user based on contextual information.
• Advertisement: Similar to recommendation but specifically for products and services.

The authors argue that these three mechanisms are strongly related and, as a consequence, an integrated view that takes them into account may bring several benefits. In fact, these mechanisms have as common goal matching a context (e.g., a query) to a collection of information objects. The following figure illustrates this unified view.

As means to characterize search, recommendation and advertisement, the paper describes them in terms of the following properties:

The pull delivery mode refers to those scenarios where there is an explicit user request. On the other hand, in the push delivery mode there is no explicit user request. The unexpected good aspects occurs whenever a novel result may be beneficial. Collective knowledge is related to the use of a historical database in order to provide a better service.

A short coverage of the search, recommendation, and advertising mechanisms is given. I will summarize some of the main points presented by the authors.

Search: It is the most mature between the three technologies. Can be divided in to two main steps: filtering and ranking. The filtering step is usually based on a query and the ranking step aims to sort the filtered results in terms of relevance.

Recommendation: Can be classified by the strategy employed (content-based or collaborative filtering) and the recipient of the recommendations (a user or a group). Content-based strategies recommends objects that are similar to those the user liked in the past. Collaborative filtering strategies identify interesting associations between users and objects consumed by them in order to make recommendations. Moreover, there is a distinction between memory and model-based collaborative filtering techniques. While the first apply statistical measures in to match users with similar tastes, the second build a model that captures such relationships. Regarding the recommendation recipient, recommendation strategies can be divided into those that recommend objects to a single user and those that recommend objects to a group of users (e.g., a movie).

Ads: Sponsored search is the mechanism by which relevant ads are delivered as part of the search experience. Therefore, sponsored search must satisfy both user need for relevant results and the advertiser's desire for qualified traffic to their websites. The usual approach applied by search engines is offering keywords through auctions. The price of a keyword depends on its relevance. Whenever the user submits a query, the search engine matches the query against the keywords and returns the ads the are relevant w.r.t the query.

Currently, the aforementioned information providing mechanisms are separated because they cater to different needs. Moreover, these mechanisms usually bring important performance issues that may prevent their integration in real applications. However, the authors present several points showing that several technologies are evolving towards this integration, which they call Information Consolidation Engine (ICE). An ICE provides a single interface for all information needs, sharing technologies across search, recommendation, and advertising, and covering a broad set of objects.  In the backend, an ICE should merge functionalities of these three mechanisms, supporting better modularization and reuse.

The main challenges in the development of ICEs are:

• Complex targets: ICEs may return a set (or package) of objects in order to satisfy the users' needs.
• Constraints: The user may provide a set of filtering, package, sequencing and prohibitive constraints over the set of objects of interest.
• Personalization: The more information the user has about the user, the better are the recommendations it is able to provide. However, it is known that personalization suitable only for active users and special types of queries.  Moreover, personalization narrows the view of users and bring important privacy issues.
• Metrics: Evaluating ICEs is a challenge because it involves highly subjective answers. Existing evaluation metrics are not powerful enough to measure the quality of ICEs. In particular, different metrics may be required for different domains.
• Other challenges: Other challenges include trust (from both the system and user side), explainability, and user feedback gathering. 

The paper finishes with a short case study describing Courserank, which is a social site where Stanford students can review courses and plan their academic program. The site provides course recommendations considering university requirements, among other services. Their current research has being focused on formalizing a language for personalization of recommendations, providing consumption plans based on sequencing information, and using tags to created a unified interface to browse and receive search results and recommendations.

I did not like this paper very much. In fact, I was expecting better examples and concepts related to the convergence of the aspects covered in the paper. Also, I believe that social media plays a key role in the integration of search, recommendation, and advertising. However, the authors do not emphasize the role of social media in the paper.

Link: http://ilpubs.stanford.edu:8090/963/

Everyone's an influencer: Quantifying Influence on Twitter

Another paper on influence in social networks using Twitter data. The first author of this paper wrote it while he was a P.hD student at Michigan University. The other authors, including the legendary Duncan Watts, were at Yahoo! Research at the time though most of them may have already left Y!R by now. In this paper the authors conduct several experiments in order to understand and model the role played by users, specially the so called influentials, and content in the generation of information cascades on Twitter.

An information cascade is a popular representation of the diffusion of a given content. It describes the chain of propagation from the seed to the leaf users. Directed edges (u,v) in the cascade mean that that there is a path from v to u (e.g., v follows u). The definition of influence used in the paper is the logarithm of the sum of the size of the cascades seeded by a given user. The type of content considered are URLs, more specifically those URLs shortened using bit.ly.

All the analysis are based on a Twitter dataset containing 87M tweets, 74M diffusion events - I suppose this means the number of pairs (URL,seed) - crawled in a 2-month time frame and also a follower network collected using the users that took part in at least one event as seeds.

In case the cascade reaches an ambiguous step - a user that published a given content has two neighbors who also published it - the authors considered three possibilities:

• First influence: The first publisher takes the credit
• Last influence: The most recent (last) publisher takes the credit
• Split credit: The credit is divided equally between the publishers.

In practice, the three strategies achieved similar results, but it is good to know them anyway.

It is interesting to notice that most of these papers on propagation/diffusion on Twitter consider URLs and hashtags as the type of content to be propagated. The authors discuss some of the implications of this choice. In particular, URLs are more inclusive than other information items such as tweets. The same can be said about hashtags. In particular, they discuss the potential effect of other sources of correlation, specially homophily, over the occurrence of cascades. In fact, the first author worked on this problem later and I have already summarize his paper here.

Examples of cascades are shown in the following figure:

Cascade sizes seems to follow a power-law distribution and cascade depth distribution look like an exponential.

In order to model influence, the authors propose the use of a regression tree model. Regression tree models are an elegant way to integrate several simple predictors into a tree for which the branches are based on values of variables. This property is expected to  handle cascades with varied sizes well. The attributes of the regression model are the following:

• User attributes (log-transformed)
• # followers
• # friends
• # tweets
• date of joining
• Past influence (in the first month):
• avg, min, and max total influence
• avg, min, and max local (immediate followers) influence.

Data from the first month are used in the generation of features to predict influence in the second month. Here is the regression tree model found. Conditions indicate partitions of the feature space (left if the condition holds and right otherwise) and leaf nodes give the logarithm of the predicted mean cascade size.

Past influence and number of followers are the only relevant features. Moreover, while the model works well for average values, which are very low in general, it does not predict well the specific cascade sizes.

Further, the authors study the effect of content over information diffusion. URLs were stratified into groups according to their cascade sizes and a sample from each group was selected uniformly at random. These samples were evaluated in terms of several criteria using humans from Mechanical Turk (it sounds funny). This figure shows average cascade sizes for different URL types and categories:

They also found that URLs classified as interesting and associated to positive feelings tend do generate larger cascades. However, adding the content attributes to the the regression model did not improved it.

In the final (and most interesting) part of the evaluation, the authors tried to answer a very challenging question: If you are a marketing professional and want to hire some twitteres to spread your content, which users would you choose? Intuitively, two opposing strategies would be selecting many "low rank" users or a few "star" users to do the job. In fact, the solution is likely to be a trade-off between these strategies. The authors defined a cost function as follows:

c_i = c_a+f_i.c_f

where c_a is a fixed cost per user, c_f is a cost-per-follower and f_i is the number of followers of the user u_i. The value of c_a is considered to be in the form alpha*c_f. Therefore, the value of alpha defines this trade-off between selecting many less influential or few more influential users. If alpha is small, contracting many less influential users becomes more attractive. On the other hand, if alpha is large, then selecting a few influential users tends to be a better strategy. They binned users according to their predicted influence given by the regression model and computed the mean actual influence / cost for each group. The results found are the following:

If alpha = 0, then selecting users with small mean predicted influence is the best choice. As alpha is increased, selecting influential users becomes more attractive, as expected. However, as the authors pointed out, the transition between these two sides is slow. This evidence puts in check the widely accepted belief that selecting a small set of influentials is a good strategy for viral marketing campaigns.

This is the second paper authored by Eytan Bakshy that were summarized in this blog. Both papers tried to answer fundamental questions about social influence using simple but sound empirical analysis and comprehensive datasets. In particular, I liked more this paper than the other one because the question here is clearer. Moreover, reading the introduction of this paper was delightful (great work!). One question about the last part of the evaluation (ordinary users vs. influentials) is: If the model does not work and the overall average size of cascades is small, does this analysis make sense? I mean, after thinking about this analysis a little bit I realized that the results obtained were highly expected. However, a better model may support a more conclusive analysis. I would like to see the results of an optimal model - that always predicts the actual influence - in order to fill this gap.

Link: research.yahoo.com/files/wsdm333w-bakshy.pdf

Finding Trendsetters in Information Networks

I found this paper to be very related to the research project I'm working on during the past few months. It is still unpublished but the authors already made it available, what is great. This research seems to have been developed inside my department (DCC-UFMG) and involved also people from Universitat Pompeu Fabra (Spain), Yahoo! Research, and Universidade Federal de Ouro Preto (Brazil). One of the authors is Ricardo Baeza-Yates, who is pretty famous in the Information Retrieval research community.

The problem studied in this research was identifying trendsetters, which are those people who adopt and spread new ideas before they become popular, in information networks such as Twitter. Given the graph induced by a topic, the authors propose the generation of a new graph where the edges are based on the influence between users expressed in the data. A PageRank based algorithm over this influence graph gives a score to every user based on his capacity of: (1) adopting the trend (or topic) early and (2) spreading the topic through his followers.

The idea of identifying trendsetters is supported by previous studies on influence. In particular, the authors describe two very interesting concepts, which are follower hubs and innovative hubs. Follower hubs have a broad audience but also present a high threshold for the adoption of new ideas. Therefore, these hubs are influencers. On the other hand, innovative hubs are less popular and also have a lower adoption threshold but are responsible for spreading new ideas through the network (i.e., they are trendsetters).   Though this idea is somehow attractive, I think it does not describe the information diffusion process very well (more on this later).

The definition of a topic applied in this work is very simple. In fact, they do not provide any automatic strategy for topic identification. A topic is defined as a set of contents (hashtags, URLs, memes, etc.). Each topic induces a graph that contains the users who spread it and the edges among them. Based on this graph, the two following functions are proposed:

The function s_1(v)_i gives the users who spread the topic i.  Moreover, the function s_2(u,v)_i defines whether the user v has influenced the user u. In this case, there must be an edge from v to u in the graph. The function s_2(u,v)_i (0 <= s_2 <= 1) determines a exponential decay of the influence score with time and the parameter alpha allows the user to define the time span of analysis (short or long term influence). The influence of a user v over u is defined as follows:

where the symbol '.' means the scalar product, ||x|| is the Euclidean norm of x, and L is the number of non-zero positions in the vector s_2. Influence values are normalized according to the following expression:

Based on the influence scores given by the function defined above, the Trendsetter (TS) score of vertices for a specific topic k is given as:

This formulation is very similar to the PageRank equation, including the use of a damping factor d. The following Figure compares the time when the top TS user posted a message about the Iran election against the time of occurrence of the top PageRank (PR) user .

The idea is that top TS users are early adopters while top PR users engage on the topic much later.

The evaluation of the TS ranking technique is performed using a large (and old) Twitter dataset from 2009 containing about 1.6B tweets and the complete following network. The topics considered are based on the most frequent hashtags classified in a previous work. Each frequent hashtag (total of 370) defines a topic. Moreover, new hashtags were added to topics based on co-occurrence with a frequent hashtags.

The first part of the evaluation section is dedicated to evaluating how top TS users are early adopters compared to the top PR and ID (In-degree) users. Next, the authors group topics based on their popularity shapes using the KSC-algorithm and show how early the top TS users adopt the topics for different popularity curve shapes. It is also shown that the Influence ratio, which is the fraction of one's followers who have been influenced at least once by him, of the top TS users is higher than that of top PR and ID users. When the rankings given by TS, PR, ID, and EA (early adopters) is compared, it is possible to notice that TS gives rankings that are distinct from the ones given by the other strategies. The authors argue that TS gives a nice balance between them.  Finally, the authors show that top TS users may be identified using a small amount (e.g. 10%) of initial data, which is not true for PR and ID.

Reading this paper was interesting. I appreciated a lot some parts of it, specially the related work section, which included some references that are not familiar to me. However, the point that attracted my attention the most was how the authors partially supported their technique and findings using the definition of follower and innovative hubs. Because it changes the role played by influentials in the diffusion process. First, it basically assumes that influentials do not produce new content and I can find many counterexamples for it (e.g., CNN, Perez Hilton). Moreover, based on the results found, influentials arrive too late in the process (sometimes, after the peak of popularity). Well, I would hardly call someone like this an influential in the first place. But whenever these "influentials" are not engaged in the diffusion of a given information, I would expect them to arrive around the popularity peak as any other user. The fact that they used hashtags as data make things even more complex, because the space of hashtags is small and, so, some popular hashtags are expected to be introduced by a random user. But these users do not necessarily are key in information diffusion. I would like to see a similar study using other type of content in order to make things clearer.

Link: http://www.decom.ufop.br/fabricio/download/KDDrt614-Saez-Trumper.pdf

TWITOBI: A Recommendation System for Twitter Using Probabilistic Modeling

I've been reading this paper for quite a long time. It is related to a project I'm working on about relevance and influence of content in diffusion data. The reason it took me so long to read this paper is because I've decided to learn Expectation Maximization before. In fact, learning EM was worthier than reading this paper, though it is not all bad.

The authors of this paper are from Seoul National University and I've never heard about them before. The problem studied in the paper is recommending tweets and users to follow on Twitter. The approach  used to solve the problem is probabilistic modelling.

I wont discuss the relevance of the problem here because it seems pretty relevant to me.

The following dataset illustrates the problem studied in the paper:

Given training data with users, followees, and tweets, the problem consists of recommending new tweets and followees to them.

The probabilistic model proposed by the authors is based on observed and unobserved data. Observed data are the set of users (U), tweets (T), and words (W). The function n(t,w) gives the number of occurrences of the word w in the tweet t. The sets T_u, O_u, and I_u contain the tweets, followees, and followers of u. Unobserved data (or hidden variables) are the topic z of each tweet t in T. The set of topics is denoted by Z = {z_1, z_2, ... z_n}. 


The model is based on the following parameters:

p(w|z) - Probability that a tweet with topic z has the term w.
p(z|u) - Probability that the user user u selects the topic z.
p(f|u) - Probability that the user u selects a topic influenced by his followee f.


The following figure illustrates how tweets are created according to the model:

The algorithm for generating data is as follows:

1) User chooses whether he is going to select a topic by himself (with probability alpha) or a topic from one of his followees (with probability 1-alpha).
     a) In case he chooses to select a topic by himself, it is done according to p(z|u).
     b) Otherwise, he selects one of his followees with probability p(f|u) and one of his followee's topics based on p(z|f).
2) Given the selected topic z, a word w from z is selected according to p(w|z).

The log-likelihood of the dataset is given by:

Formulating this log-likelihood function is the hardest step in the generation of a probabilistic model like this. I think I understood  all steps, but I may need some practice in order to do this kind of modelling by myself.

It is easy to recognize the model parameters in the above formula. But it is still necessary to define the hidden variables. These variables capture the topic of tweets and whether the user chooses a topic by himself or based on his followees' topics. They are defined as follows:


p(phi=z|w,u) - Probability that a tweet is about z given that it has the word w and is from the user u.
p(theta=u|z,u) - Probability that a user u produces a tweet about z by himself.
p(theta=f|z,u) - Probability that a user u produces a tweet about z influenced by his followee f.

These hidden variables are computed based on the parameters of the model, as shown in the following figure:

In the Expectation (E) step, the hidden variables are estimated based on the current values of the parameters, which are formulated as follows:

In the Maximization (M) step, the values of parameters that maximize the log-likelihood function are computed using Lagrange multipliers. One thing that I did not understand very well how the above expressions are applied together with the optimization method.

The paper also presents a parallel algorithm that computes the parameters of the probabilistic model using map-reduce, but I will jump directly to the results instead of describing it.

The experimental results apply a dataset containing 12M tweets and 8K users. Part of the data, containing 400 users, is selected as test set. Users in the test set have at least 10 followees and 10 tweets. From these users, 10 followees and 10 tweets are selected as random. The idea is predicting these 10 followees through user recommendation and the 10 tweets using tweet recommendation. The baseline for user recommendation is a method based on TF-IDF that I have already summarized here. And the baseline for tweet recommendation also based on TF-IDF is compared against the proposed method. The results show that  TWITOBI outperforms the baselines in both the top-k followee and the top-k tweet recommendation tasks in terms of recall-at-k, precision-at-k, and average hit-rank. Moreover, the parallel version of the algorithm achieves linear speedup.

This paper studies a very interesting problem but the solution does not seem well-presented to me. In fact, I'm not convinced that such a complex approach is even necessary to achieve such results. Maybe, the authors should give more details on the proposed method instead of presenting the  parallelization using map-reduce.

Link: http://www.computer.org/portal/web/csdl/doi/10.1109/ICDM.2011.150

Expectation Maximization

I'm really late in my reading plans this month. I've been working hard on a recent project and also spending a lot of time on bureaucratic stuff related to my move in September. Some weeks ago I started reading a paper about content recommendation on Twitter (it is going to be summarized here soon) and I discovered that I had no idea about how Expectation Maximization (EM) works. So, I decided to spend some time learning EM. It is interesting that this is my first post covering a specific topic (not a paper) here. Also, I've applied the learning method described here to learn EM. Let's see how this concurrent experiment works.

Expectation Maximization (EM) is a statistical technique for estimating parameters for statistical models when there are latent (or hidden) variables. The parameters found are maximum likelihood estimates (MLE) based on both the data and the latent variables.

But what is a statistical model? Very simple. A statistical model is a equation that describes relationships between variables through probability distributions. This distributions make the relationships stochastic instead of deterministic.

What about hidden variables? Hidden (or latent) variables are those variables that are not directly observed in the data. Therefore, such variables must be inferred based on the observed variables. The "magic" of  EM is that it is able to deal with both hidden variables and parameters to be estimated together. Sometimes making some variables hidden seems to be useful in practice.

Maximum likelihood estimate: The likelihood of a set of parameters is, basically, the probability of such parameters to generate the given outcomes. MLE is a method for inferring the parameters with maximum likelihood. EM is a generalization of MLE for scenarios where there are hidden variables. We usually maximize the log-likelihood because the logarithm function is an increasing function and log is a monotone transformation (i.e., the parameters that maximize the original function also maximize the likelihood also maximize the log-likelihood).

An example of a problem that can be solved using EM is: Given two coins, each of them with unknown biases, suppose that a random coin is selected uniformly and thrown N times. This experiment is performed M times (for each time, one of the coins is selected at random). What are the biases of the coins?

Parameters of the model: The biases of the coins.

Unknown variables: The selection of coins.

What if the choice of coins was known? Then we have a traditional MLE scenario. The parameters (biases) can be estimated as:

estimated bias coin A = # tails coin A / # times coin A was thrown
estimated bias coin B = # tails coin B / # times coin B was thrown

EM is an iterative procedure that alternates between two main steps: Expectation (E) and Maximization (M). The parameters are initially set to some initial values. The Expectation step estimates the hidden variables based on the current parameter values. The Maximization step calculates the MLE of the parameters given the estimated hidden variables. The method is expected to converge after a finite number of iterations.

How would EM work for the aforementioned example? 

1. Set initial values to the biases of the coins.
2. A probability distribution over the unknown coin choices is drawn based on the current parameters (biases).
3. New parameters are estimated using MLE based on the probability distribution found in the last step.
4. Go back to step 2 (until convergence). 

I took this example from the article What is the expectation maximization algorithm? Here is the complete running example, which I found very clever.

If you are familiar with the K-means algorithm (I am), you will find this explanation of K-means as EM very instructive: The cluster of each point are the latent variables and the centroid of each cluster are the parameters to be estimated. Therefore, the cluster of each point is updated in the expectation step and the centroids are computed in the maximization step. However, in K-means the expectation step actually assigns points to clusters instead of computing a probability distribution for assignments.

Another example of the application of EM is the follows: Suppose that you have two Normal distributions, A and B, and that you are given instances of these distributions but you do not know which distribution the instances were sampled from. How can you compute the means mu_A and mu_B of the distributions if both distributions have the same known variance? Surprisingly, the answer is EM.

What if there is a single distributions instead of two? Then estimating the mean is straightforward.

What if the selected distribution is known? In this case, mu_A and mu_B are the mean value of the instances for each distribution. Still pretty easy.

How we solve this problem using EM? The means are the parameters and the distribution from which each instance was sampled are the latent variables.

1. Define initial values for mu_A and mu_B.
2. Expectation step: Estimate the probability that each instance was generated from A B.
3. Maximization step:  Compute the weighted means of instances for A and B.
4. Go back to step 2 (until the estimates converge).

In the expectation step, the probabilities are computed as follows:

Probability that the instance x_i is from A:

 P(x = x_i | mu = mu_A) / (P(x = x_i | mu = mu_A) + P(x = x_i | mu = mu_A)

Probability that the instance x_i is from B:

 P(x = x_i | mu = mu_B) / (P(x = x_i | mu = mu_B) + P(x = x_i | mu = mu_B)

Since we know that the distributions are Gaussian and the variation is also known, we can compute these probabilities using the probability density function of the Gaussian distribution.

In the maximization step, the means are updated as follows:

mu_A = Sum_{x_i} P(x_i is from A).x_i / Sum_{x_i}P(x_i is from A)

mu_B = Sum_{x_i} P(x_i is from B).x_i / Sum_{x_i}P(x_i is from B)

The EM method is known to converge to local optimum parameters that may not be the global optimum ones. At each iteration, the parameters are improved until a local optimum is reached. In practice, several initial parameters are applied in order to avoid poor local maximum likelihood values.


Alternative approaches to EM include the gradient descent and Newton-Raphson methods.


References:

Chuong B Do and Serafim Batzoglou. What is the expectation maximization algorithm? Nature  Biotechnology.

McLachlan, G. J., & Krishnan, T. (1997). The EM Algorithm and Extensions. Wiley, New York.

http://www.cs.berkeley.edu/~russell/classes/cs194/f11/lectures/CS194%20Fall%202011%20Lecture%2020-EM-proof.pdf