 |  |  |
Differences
This shows you the differences between two versions of the page.
|
about:variable [2010/10/29 01:42] rim created |
about:variable [2023/02/15 12:46] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Variable complexity problems ====== | ||
| - | |||
| - | Variable complexity problems are problems in which the main problem is to find a suitable set of values for a set of parameters, but we don't know how many. However we already know the relationships between the parameters. Problems falling into this class include | ||
| - | |||
| - | * A few optimisation problems, where the aim is to find real-number coefficients x1,...,xn where we don't know how large n needs to be beforehand - this includes cases such as power or fourier series approximations | ||
| - | * Some discrete optimisation problems, we may not know ahead of time how many parameters x1,..., are required | ||
| - | * For example knapsack problems, stock cutting problems | ||
| - | * Polynomial regression, where we don't know ahead of time how high degree polynomial is required to get an acceptable fit | ||
| - | * Most interesting attribute learning problems fall into this class - decision trees, decision rules etc | ||
| - | * While solutions aren't completely unstructured, there are many transformation symmetries (transitivity, commutativity,...) so discovering the structure is generally not the hard part of the problem | ||
| - | |||
| - | Methods for solving such problems include | ||
| - | * Gradient descent and similar deterministic eager search methods | ||
| - | * Stochastic search (simulated annealing, tabu search, genetic algorithms) | ||
| - | |||
| - | While this isn't the primary focus of research in the structural complexity lab, we do some research in these areas from time to time; we tend to be more interested in | ||
| - | |||
| - | * Dynamic problems, where the optimal solution changes with time | ||
| - | * Problems belonging to a family of problems, so tough versions can be solved incrementally from first solving simpler ones | ||