Algorithms for solving combinatorial complexity problems in machine learning?

Question

Many machine learning problems have combinatorial complexity.

For example, in part-of-speech (POS) tagging in NLP, the goal is to predict one of possible $T$ tags for every word in a sentence of length $n$, i.e. we want to compute \begin{equation} \arg \max_{t_1,...,t_n} p(t_1, ..., t_n, w_1, ..., w_n) \end{equation} There are $O(T^n)$ possible tag sequences. One approach to solving this problem is to factor the joint distribution as a Hidden Markov Model (HMM), learn its parameters (e.g. using an EM algorithm) and apply dynamic programming (Viterbi algorithm) to find the optimum sequence of tags: \begin{equation} \pi[i, t] = max_{t^{\prime}}\{\pi[i-1, t^{\prime}] + \log P(t|t^{\prime}) + \log p(w_i|t)\} \end{equation} where $\pi[i,t]$ is the Viterbi recurusion table of size $O(nT)$. Since the max operation above is over $T$ possible tags for each entry in the table of size $n\times T$, the time complexity of the Viterbi decoding is $O(nT^2)$. Thus, we just reduced the original problem of exponential complexity to polynomial time complexity using dynamic programming.

I'm interested in examples of algorithms that could be used to reduce a combinatorial problem to polynomial time in the area of machine learning.

Answer 1

Strictly speaking this is not solving the problem - HMM has pretty strong assumptions about distribution interdependencies. It's solving simplified problem.

What you are referring to has a generalization for graphical models, of which HMMs are an example.

Another examples:

Finding optimal values for k-means is NP-complete. But with initialization that is random or heuristic-based it has polynomial running time.

Decision trees - again finding optimal splits is NP-hard. In practice greedy algorithms like CART or ID3 are used.

Feature subset selection methods for linear models also have this problem. There are many alternatives for that - lasso, greedy search, and wikipedia entry for that even has links for genetic algorithms.

You could also try to read on Generalized Low Rank Models, the authors propose a framework of turning problems with combinatorial complexity exact solutions (like nonnegative matrix factorization) into problems for which convex optimization can be used.

Answer 2

There are many solvers that can cope relatively well with combinatorical problems even without explicit reduction to linear time. One of them are SAT solvers.

It has been demonstrated that SAT solvers can be used for better construction of decision trees: http://www.lirmm.fr/~bessiere/stock/cp09-decisiontrees.pdf

Another approach how to cope with NP problems is dynamic programming. It has been applied to efficient construction of frequent item sets in popular apriori algorithm: http://ieeexplore.ieee.org/document/6780102/