I am watching the lecture here and the author says that in the machine learning setting where data is assumed to be generated by a model with a few parameters:

Max Likelihood parameters are NP hard to find in general (non convex objective).

And in practice heuristics such as EM are used.

I guess everywhere these things are stated as a metter of fact but explanations are missing.

Could you explain how can a model have an intractable max likelihood? How to prove it. I have seem problems such as SAT proven NP hard, but in this context I do not have an intuition of how to approach. Do we need first to show non-convexity before proving NP hard?

  • 1
    $\begingroup$ I do not understand the logic of your question: a single counterexample will not shed any light on an assertion that is said to hold "in general." $\endgroup$ – whuber Jan 15 '17 at 20:59
  • $\begingroup$ @whuber yes, but i will get an intuition about how to move ahead to prove in different situations. That will be very helpful while trying to understand the papers. thx. $\endgroup$ – Rafael Jan 15 '17 at 21:12
  • 1
    $\begingroup$ The model you name has an extremely simple likelihood whose maximum is easily found and has a closed form. There doesn't seem to be much to learn from it about the situation you mention at the outset. $\endgroup$ – whuber Jan 15 '17 at 21:19
  • $\begingroup$ @whuber yes, univariate Gaussian is a bad example of what i wanted to ask. i will edit the question. thx. $\endgroup$ – Rafael Jan 15 '17 at 22:08
  • $\begingroup$ See MLE of the location parameter in a Cauchy distribution for a simple example of a non-convex objective. $\endgroup$ – Scortchi - Reinstate Monica Jan 16 '17 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.