Description
Introduction This assignment asks you to implement an algorithm for learning parameters for a simple Bayesian network from missing data. The algorithm Missing data are prevalent in real-world problems and appear as either hidden variables that are never observed or missing values for some features. Learning from such datasets can be solved using an algorithm called Expectation Maximization (EM). The idea is to start with a model completed with random parameters and to repeat the following two steps until convergence: • Estimate the missing data using the current complete model (E-step), • Learn a new set of parameters using the data set “completed” with the missing data just estimated (M-step). You should set a small threshold (say 0.001) for the change of likelihoods between two iterations to detect the convergence of your algorithm. Since EM is sensitive to the starting point, you should try multiple starting points in order to find a good solution. EM is also sensitive to the amount of missing data. Five data sets with missing rates being 10%, 30%, 50%, 70%, and 100% respectively are provided. Learn a model for each data set. The model The Bayesian network has the following variables: Gender, Weight and Height, whose relations are shown in the following graph.
The datasets (download from course website) have 20 data points each with occasional missing values for Gender, denoted as “-”. All the variables are binary: Gender (M/0, F/1), Weight (greater_than_130/0, less_than_130/1), and Height (greater_than_55/0, less_than_55/1). The parameters of this model are to be estimated from the datasets.
Gender
Weight Height
Implementation Implement the EM algorithm for learning the parameters for the above model in your preferred programming language. Hint: E-step of the EM algorithm is essentially estimating the probabilities of different values of Gender given that we know a person’s Weight and Height, i.e., P(Gender | Weight, Height), and use these estimations as if they are our (expected) counts. Evaluation and analysis Test your EM algorithm on the five datasets. For each dataset, try several different starting points. In your report you should at least include the following results: • The starting points of the learning • The final conditional probability tables for each learning • Plots of the likelihood vs number of iterations to demonstrate the convergence of your algorithm. • Try the following starting parameters and report your results. P(gender=M)=0.7; P(weight=greater_than_130|gender=M)=0.8; P(weight=greater_than_130|gender=F)=0.4; P(height= greater_than_55|gender=M)=0.7; P(height= greater_than_55|gender=F)=0.3;
And provide analysis on the following issues at least: • Do multiple starting points help in finding better solutions? • Do some of the different solutions have the same likelihood scores? • How does the data missing rate affect your algorithm and the results? Deliverables Submit a single .zip file named LastName.FirstInitial.HW# containing the following via email to me at changhe.yuan@qc.cuny.edu. In addition, submit a hardcopy of your report and code in class on due date. 1) Well commented code; 2) A readme file explaining how to compile and run your program; 3) A written report explaining your experimental results.
