Algorithmen zur Teilmengenauswahl in der linearen Regression

Wir untersuchen das Problem, eine Teilmenge von k Zufallsvariablen auszuwählen, deren Beobachtung die beste lineare Vorhersage einer anderen interessierenden Variablen liefert, gegeben die paarweisen Korrelationen zwischen den Beobachtungsvariablen und der Prädiktorvariablen. Unter annäherungsbewahrenden Reduktionen ist dieses Problem äquivalent zum "sparsamen Approximations"-Problem, Signale prägnant zu approximieren. Das Problem der Teilmengenauswahl ist im Allgemeinen NP-schwer; in diesem Papier schlagen wir exakte und Approximationsalgorithmen für mehrere spezielle Fälle von praktischem Interesse vor und analysieren diese. Insbesondere geben wir ein FPTAS, wenn die Kovarianzmatrix eine konstante Bandbreite hat, und exakte Algorithmen, wenn der zugehörige Kovarianzgraph, der aus Kanten für Paare von Variablen mit nicht-null Korrelation besteht, einen Baum bildet oder eine große (bekannte) unabhängige Menge hat. Darüber hinaus geben wir einen exakten Algorithmus, wenn die Variablen in eine Linie eingebettet werden können, sodass die Kovarianz exponentiell mit der Distanz abnimmt, und eine Approximierung mit konstantem Faktor, wenn die Variablen keine "bedingten Unterdrückungsvariablen" haben. Ein Großteil unserer Argumentation basiert auf Störungsergebnissen für das R2-Maß der mehrfachen Korrelation, das häufig als natürliches Maß für "Anpassungsstatistiken" verwendet wird. Es liegt im Kern unseres FPTAS und ermöglicht es uns auch, unsere exakten Algorithmen auf Approximationsalgorithmen zu erweitern, wenn die Matrix "nahezu" in eine der oben genannten Klassen fällt. Wir nutzen auch unsere Störungsanalyse, um Annäherungsgarantien für die weit verbreitete Heuristik "Vorwärtsregression" unter der Annahme zu beweisen, dass die Beobachtungsvariablen nahezu unabhängig sind.