patternMinor
Typical NP-complete/hard problems in machine learning
Viewed 0 times
typicalhardlearningcompletemachineproblems
Problem
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.
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.
Solution
Many theoretical problems in ML are NP-hard.
-
I think the famous AlphaGo is trying to solve a NP-hard problem.
-
Contextual bandit problem and its combinatorial variants are np-hard.
-
In social network analysis, the famous influence maximization problem is a NP-hard problem.
-
There are many others. You can search in google. Also you can find related papers in two famous ML conferences: NIPS and ICML.
-
I think the famous AlphaGo is trying to solve a NP-hard problem.
-
Contextual bandit problem and its combinatorial variants are np-hard.
-
In social network analysis, the famous influence maximization problem is a NP-hard problem.
-
There are many others. You can search in google. Also you can find related papers in two famous ML conferences: NIPS and ICML.
Context
StackExchange Computer Science Q#55105, answer score: 9
Revisions (0)
No revisions yet.