1

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?

kjetil b halvorsen
  • 63,378
  • 26
  • 142
  • 467
Rafael
  • 1,109
  • 1
  • 13
  • 30
  • 1
    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." – whuber Jan 15 '17 at 20:59
  • @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. – Rafael Jan 15 '17 at 21:12
  • 1
    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. – whuber Jan 15 '17 at 21:19
  • @whuber yes, univariate Gaussian is a bad example of what i wanted to ask. i will edit the question. thx. – Rafael Jan 15 '17 at 22:08
  • See [MLE of the location parameter in a Cauchy distribution](http://stats.stackexchange.com/q/98971/17230) for a simple example of a non-convex objective. – Scortchi - Reinstate Monica Jan 16 '17 at 12:29

0 Answers0