On the Parameterized Complexity of Some Fundamental Problems in Machine Learning

Monday 27 June 2005, 2 pm, Room 219, McCrea Building
Michael Fellows, University of Newcastle, Australia

Most input distributions encountered in real-world applications of computing are "not round" in the sense that what the definition of the computational problem allows, when the problem is considered theoretically, is far from what actually turns up: most input distributions have highly significant extra structure that is not treated appropriately when only the overall instance size n is considered in the usual (usually frustrated) quest for some form of polynomial-time satisfaction. ("I got my input size n, and I'm doin' this, and I'm doin' that, but I can't get no ...") Theoretically, almost every interesting problem is NP-hard or worse to do anything about --- solve, learn, approximate or whatever.

For an example of this point about input structure, consider the important problem of type-checking computer programs. The TYPE CHECKING problem for the logic-based programming language ML is EXP-hard (i.e., hard for a class that is far beyond NP) when we consider complexity only as a function of the program size n. However, programs written by human beings tend to have a maximum nesting depth of type declarations k?5. The implemented compilers for ML work just fine in practice, solving the TYPE CHECKING problem in time O(2kn).

In the approach to complexity analysis and algorithm design that is known as parameterized complexity one is basically concerned with a two-dimensional analog of the familiar opposition of P versus NP-hard, where the opposition is between a two-dimensional analog of polynomial time, termed fixed-parameter tractability (FPT) and a two-dimensional analog of NP termed W[1]. FPT means solvability in time f(k)nc where c is a constant that is typically small (e.g., c=1 in the TYPE CHECKING example) and f(k) may be some exponential function of k, such as 2k in the TYPE CHECKING example.

You can do a lot of useful theoretical work in this two-dimensional framework, where there is a systematic place (the parameter) to model the effects on problem complexity of the extra structure (such as bounded nesting depth, bounded treewidth, etc.) that one frequently encounters in real input distributions and computational situations.

The talk will survey the basic ideas of parameterized complexity, and some applications of this theory to fundamental computational problems in machine learning.