9
$\begingroup$

I know little about machine Learning, but I work on optimization (solving NP-hard problems with SAT solvers or MIP). Examples of this would be solving TSP, Steiner tree problems, path finding with constraints, etc.

I was wondering, is there any problem in ML that is NP-hard for which there are only approximations or small attempts of trying to solve them? I would like to look at them to see if my work can be applied there.

I am only interested in discrete optimization (so over integers/Booleans). Something that one could typically solve with constraint programming. Examples of such problems are scheduling tasks, finding paths in a graph given some weird constraints, TSP, vehicle routing... My research is on constraint programming applied to graphs, so if the problem can be modelled as a graph problem, that is a plus. My knowledge of ML is limited. I know the high-level concepts such as what regression, classification or supervised/unsupervised mean. Never actually implemented one of this ML things. I am watching a coursera class form Stanford on ML, but it is portrayed in a way that doesn't let me really see what are the NP-hard challenges.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ 1. Can you narrow down this question? There are lots of problems in ML that are NP-hard. ML relies heavily on optimization all over the place; it's an entire subfield. Is there any particular type of optimization you're looking for a match for? 2. What research or study have you done? There are lots of resources that will teach you ML, and where you'll be exposed to some NP-hard problems along the way. What reading and research have you done? This will help ensure you receive answers that are at the right level and won't repeat things you already know. $\endgroup$
    – D.W. ♦
    Mar 29, 2016 at 17:20
  • $\begingroup$ Hi, I added more info to the questions. Thanks for your comment. $\endgroup$
    – excalibur1491
    Mar 30, 2016 at 4:11
  • $\begingroup$ Finding the optimal divisions in decisions trees is NP-complete. $\endgroup$
    – yters
    Apr 8, 2017 at 19:30

2 Answers 2

Reset to default
9
$\begingroup$

Many theoretical problems in ML are NP-hard.

  1. I think the famous AlphaGo is trying to solve a NP-hard problem.

  2. Contextual bandit problem and its combinatorial variants are np-hard.

  3. In social network analysis, the famous influence maximization problem is a NP-hard problem.

  4. There are many others. You can search in google. Also you can find related papers in two famous ML conferences: NIPS and ICML.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ "I think the famous AlphaGo is trying to solve a NP-hard problem." Is it? I mean, I don't doubt that NxN Go is NP-hard, but fixed size Go is finite, albeit massive. $\endgroup$
    – jmite
    Jan 13, 2017 at 20:17
  • 3
    $\begingroup$ @rus9384 I’m late to the party, but jmite is correct. Go, like virtually every other physical game in existence, has a finite number of board states and is (from a CS Theory point of view) solvable by “just” searching a finite strategy space. Generalized Go, on an n x n board, is what is EXP-C. Regular Go barely avoids being in PSPACE. Specifically, without ko, Go is PSPACE-C. With ko it depends on which ko rules you use. All this info can be found here $\endgroup$
    – Stella Biderman
    Jun 5, 2018 at 4:06
4
$\begingroup$

In deep learning optimizing weights of the neurons in multi-layer network is np-hard. General explanation can be found here. More information and math about this problem can be found in this thesis by J. Stephen Judd.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.