Testen bestimmter Kontraste: Ist das nachweislich ein schweres Problem oder nicht?

12

Ich habe dies in mathoverflow gepostet und niemand antwortet:

Scheffés Methode zur Identifizierung statistisch signifikanter Kontraste ist weithin bekannt. Ein Kontrast zwischen den Mitteln μi , i=1,,r von r Populationen ist eine Linearkombination i=1rciμich in der i=1rci=0und ein skalares Vielfaches eines Kontrasts ist im Wesentlichen der gleiche Kontrast, man könnte also sagen, dass die Menge der Kontraste ein projektiver Raum ist. Die Methode von Scheffé testet eine Nullhypothese, die besagt, dass alle Kontraste zwischen diesen Populationen 0 sind , und weist die Nullhypothese bei gegebenem Signifikanzniveau α mit der Wahrscheinlichkeit α zurück , sofern die Nullhypothese wahr ist. Und wenn die Nullhypothese verworfen wird, weist Scheffé darauf hin, dass sein Test uns sagt, welche Kontraste sich signifikant von 0 unterscheidenr0αα0 (ich bin mir nicht sicher, ob der Wikipedia-Artikel, den ich verlinkt habe, dies anzeigt).

Ich würde gerne wissen, ob man in einer anderen Situation etwas Ähnliches machen kann. Man betrachte ein einfaches lineares Regressionsmodell , wobei ε ii ist . ich . d . N ( 0 , σ 2 ) , i = 1 , , nYi=α+βxi+εiεii.i.d.N(0,σ2)i=1,,n .

Die Nullhypothese, die ich betrachten möchte, betrifft eine andere Art von Kontrast. Es heißt, es gibt keine Teilmenge so dass E ( Y i ) = α 1 + β x i für i A und E ( Y i ) = α 2 + β x i für i A wobei α 1α 2 istA{1,,n}E(Yi)=α1+βxiiAE(Yi)=α2+βxiiAα1α2. Wenn die Teilmenge im Voraus spezifiziert wurde, führt dies ein gewöhnlicher t- Test mit zwei Stichproben durch , aber wir möchten etwas, das alle Teilmengen berücksichtigt und die Wahrscheinlichkeit, eine echte Nullhypothese abzulehnen, niedrig hält.At

Man könnte diese herausfinden, wenn Effizienz kein Problem ist: einen Test finden , die durch alle geht Möglichkeit. Auch dann ist es problematisch; zwei kontraste wären nicht unabhängig. Ich fragte einen Experten für die Erkennung von Ausreißern, und er sagte nur, es sei ein kombinatorischer Albtraum. Dann fragte ich, ob man beweisen könne , dass es keinen effizienten Weg gibt, dies zu tun, vielleicht indem man ein NP-hartes Problem darauf reduziert. Er sagte nur, er halte sich von NP-harten Problemen fern.2n11

Also: Kann man beweisen, dass dieses Problem "schwer" ist oder nicht?

Michael Hardy
quelle
(+1) Kopieren eines Kommentars zur Verdeutlichung aus der MO-Fassung : Nur ein kleiner Punkt zur Verdeutlichung: Wenn ich es lese, qualifiziert sich unter Ihrer Nullhypothese, aber ( 1 , 2 , 2 ) und ( 1 , 1 , 1 ) nicht (unabhängig von β ). Ist es das, was du beabsichtigt hast? (Es scheint nicht mit einigen der anderen in der Frage gemachten Anspielungen übereinzustimmen.)(α1,α2,α3)=(1,2,3)(1,2,2)(1,1,1)β
Kardinal
Wie oben angegeben, wäre die Nullhypothese, dass wir nur ein benötigen , und die alternative Hypothese ist, dass wir zwei brauchen. Ich weiß nicht, warum Sie einen dritten haben. Man könnte auch die Nullhypothese von nur einem α gegenüber der Alternativhypothese von mehreren betrachten, und vielleicht sollte ich das stattdessen tun. αα
Michael Hardy
Vielen Dank. Vielleicht wurde ich von der ursprünglichen Aussage des Modells als abgelehnt , wobei ich das α als möglichen Tippfehler für α i ansah (da es anschließend variieren durfte). Yi=α+βxi+εiααi
Kardinal
Nun, sicherlich, wenn dieses von i abhängt , wäre es ein überparametrisiertes Modell und überhaupt nicht so, wie man es normalerweise als "einfaches lineares Regressionsmodell" bezeichnet. αi
Michael Hardy

Antworten:

1

Es wurde festgestellt, dass noch niemand diese Frage beantwortet hat ...

Grundsätzlich stellt sich die Frage: Gibt es einen 0-1-Vektor so dass y i = α + β x i + γ z i + ϵ i eine (signifikant) bessere Anpassung ergibt als y i = α + β x i + ϵ ich . "Deutlich besser" kann in Form von Quadratsummen als Ungleichung erfasst werden. Es stellt sich die Frage, ob es eine 0-1-Lösung für die Ungleichung f ( z ) t gibt .Z

yi=α+βxi+γzi+ϵi
yi=α+βxi+ϵi.
f(z)t.
Dies ist eine Variante des Set-Partitionierungsproblems, von dem bekannt ist, dass es NP-hart ist.
user3697176
quelle
Kann das eingestellte Partitionierungsproblem tatsächlich auf dieses Problem reduziert werden? Wenn ja, würde das beweisen, dass dies ein schweres Problem ist.
Michael Hardy
Dieses Problem ist mindestens so schwer wie das klassische Setpartitionierungsproblem (SPP). SPP verwendet eine lineare Kombination von Gewichten und versucht, diese mit +/- 1 zu multiplizieren, um einen Ausdruck zu erhalten, der sich zu 0 summiert. Hier möchten Sie eine Ungleichung erfüllen. Wäre dies für beliebige Eingaben in Polynomzeit lösbar, zeigt ein Bisektionsargument, dass Sie SPP auch in Polynomzeit lösen können. Das ist nicht gerade eine Reduzierung, aber es ist nah.
User3697176