Hi everyone

I am new to this forum. Recently, i need to write a program in C that will help me to do the computations for expectation maximization(EM) algorithm. However, i am at a total lost as to how to start. Hope someone can give me advice. Thanks!

Start with pencil and paper (or, perhaps more appropriately, a text editor): Write out the steps of the algorighm that you want to implement. Show us what you have in mind.

Now, if you have never written any kind of program "from scratch", it's hard to say how to develop a program from an algorithm. So: What's your experience level in C?

Dave

Hi Dave
thanks for your reply. Guess I didn't make myself clear enough. Real sorry about that.

I am quite experienced in using C and other languages such as C#, ASP, PHP etc to develop programs. However, as they are just implementations (such as implementing an online database system etc), they are far easier to do compared to this current prob of mine (at least to me, as I have totally no experience in this current prob :-( )

The expectation maximization algorithm basically consists of 2 parts: the expectation step and the maximization step. It is used to estimate the values of data that are missing from the dataset. Hence, it will try to estimate the values of these missing variable values through the data that we know, and through our estimates of the values of the parameter. Then it will estimate the value of the parameter to maximise the likelihood function.

This is to enable a system to learn about the network structure through training data, which are in most real world cases incomplete; hence the need to estimate the values of the missing data.

My prob is that since the system is supposed to learn from the data we sent in and try to complete the data by filling in the expected values, I dunno how to even start programming it in C. I hope that anyone with experience in it can advise me on wat to do.

The most generic way of breaking down program tasks is:


Input ==> Processing ==> Output


Start at Input:

What values do you have to give to the program? Are they from a file, or for user input? (Hidden from view, ignored by many programmers, but extremely important is verification of input --- Is it the right kind of data, (numbers, or what), etc.)

Before you actually get the input, you have to have some place to put it. Allocate storage for however much data you expect to get. Don't know how much you will need? Maybe you will have to use malloc() or some such thing to get storage as you go along.

For starters, you can simply declare arrays to hold a certain amount of data, and include checks in the program to make sure that user input doesn't exceed this amount.

If you have had lots of experience in programming, then you must know some I/O.

I don't know how to tell you to create a program (maybe it's like telling you how to write a symphony).

Again: if you were doing this "by hand", how would you record the input data; how would you calculate the estimates; how many sheets of paper would you need (that is, how much storage will you need for intermediate results)?

If the big program is too much, try a smaller program:

How would you calculate the mean and standard deviation of a set of input numbers?

The "brute force" method is to read the numbers, one at a time, into an array.

After all numbers have been read (how do you know which was the last number?), calculate the sum of the numbers. You might use a loop:


Now, this might not be the "best" way to solve my mini-problem, but it is a way. First figure out a way; optimize later.


Dave

Hi Dave,

thanks for your reply again. :-o

Guess I am overwhelmed by what I don't know. Your suggestion is really helpful, I should try to tackle the problem just like I do with all other prog, which is as you said
Input ---> Processing ---> Output

I will try to work it out on paper first, and slowly build up the modules one by one. Thanks once again! You have been a great help!

Best Regards
Kenneth aka edge

Hi edge,

So were you successful in coding the EM, and would it be possible for you to share the code.

Thanks,
Kalyan

Hi Kalyan,

Try to do the program yourself with the help of this above thread.

If you desperately want the source code, then i found java source code. you need to change the math functions only.

Here is the link for that:
Expectation Maximisation Algorithm

Regards,
Paramesh.

The Original Poster never got back to us (it was over a year ago). Since that individual was not very experienced in programming, we never got as far as discussing the topic of his question, so I will say a few words here:

In my lexicon, the term Expectation Maximization refers to one possible approach to solving a large class of statistical problems.

For example: If you have a data set with some points missing from a sequence, what is the "best way" to fill in the gaps?

If you have some reason to accept certain statistical assumptions about the nature of the population that was sampled to get your data, you try to fill in the gaps with the "most probable" values. A slightly more precise statement might be to say that you try to fill in the values by calculating maximum-likelihood estimates of the statistical parameters and then using those values to fill in the gaps.

So, what's my point? My point is that there is no such thing as the Expectation-maximization algorithm. There are lots of algorithms that use an Expectation-maximization approach to perform some task.

If I were given a task that somehow is supposed to involve an Expectation-maximization approach, I might start with wikipedia and follow the links from there.

Wikipedia Article

(Man --- what did we do before wikipedia??? Oh, now I remember: we went to the library or to our professor's office to try to find a reference book to borrow. How 20th-century is that approach to problem-solving??? What a wonderful time it is, now, to be alive!)

You might find some source code somewhere on the web that is from someone's Master's Thesis that has the words "Expectation" and "Maximization" in the title, but then what?

If you are taking a course in communications theory or stochastic signal processing or some other statistics-oriented topic, start by looking at a problem in that field that lends itself to the E-M approach. (Or maybe you were given a problem.)

Then, do as I advised the Original Poster:

Write down the problem in terms if Input==>Processing==>Output.

Make sure you understand the steps. It would really be a good thing if you could find a simple test case that you can solve manually (or, maybe an example in a book where the output is given). Then you could use that to test program as you proceed.

If you have any specific questions about coding, or if your program doesn't tell you what you wanted to hear, then just ask.

The way to ask a question that is most likely to get useful responses quickly is: state the part of the problem that you are working on. Show enough of your code that someone here can reproduce your results (compile and execute).

Then:

1. Tell us what you put into the program. (Show the input)
2. Tell us what you expected the program to tell you.
3. Tell us what the program told you. (Show the output)
4. Tell us what you don't understand about the difference between item 2 and item 3.

(Remember, this is a program language assistance forum, not an advanced stastical analysis workshop, so be specific about your program actions, not so much as why your data set didn't work with a particular algorithm.)


Regards,

Dave

hi guys
as Dave mentioned earlier EM is just a way to approach a problem.

There are lots of other methods out there such as Bayesian Networks or even Artificial Neural Networks and AI system that seems plausible. Hence I believe we should not limit ourselves to just making use of EM. If you are interested to take this further, we can always discuss it as this is my interest area as well.