Testowanie niektórych kontrastów: czy jest to trudny problem, czy nie?

12

Wysłałem to do mathoverflow i nikt nie odpowiada:

Metoda Scheffé do identyfikacji statystycznie istotnych kontrastów jest powszechnie znana. Kontrast wśród środków , o populacji jest liniową kombinacją w którym , a skalarna wielokrotność kontrastu jest zasadniczo tym samym kontrastem, więc można powiedzieć, że zestaw kontrastów jest przestrzenią rzutową. Metoda Scheffé'a testuje hipotezę zerową, która mówi, że wszystkie kontrasty między tymi populacjami wynosi , a biorąc pod uwagę poziom istotności , odrzuca hipotezę zerową z prawdopodobieństwem i = 1 , , r r r i = 1 c i μ i r i = 1 c i = 0μjaja=1,,rrja=1rdojaμjaja=1rdoja=00 α αr0ααbiorąc pod uwagę, że hipoteza zerowa jest prawdziwa. A jeśli hipoteza zerowa zostanie odrzucona, Scheffé wskazuje, że jego test mówi nam, które kontrasty różnią się znacznie od (nie jestem pewien, że artykuł w Wikipedii, który podłączyłem, wskazuje na to).0

Chciałbym wiedzieć, czy można zrobić coś podobnego w innej sytuacji. Rozważ prosty model regresji liniowej , gdzie , .ε ii . i . d . N ( 0 , σ 2 ) i = 1 , , nYja=α+βxja+εjaεjaja.ja.re.N.(0,σ2))ja=1,,n

Hipoteza zerowa, którą chcę rozważyć, dotyczy innego rodzaju kontrastu. Mówi, że nie ma podzbioru takiego, że dla i dla , gdzie . Jeśli podzbiór jest określony z góry, to robi to zwykły test dwiema próbkami , ale chcemy czegoś, co uwzględnia wszystkie podzbiory i ogranicza prawdopodobieństwo odrzucenia prawdziwej hipotezy zerowej.E ( Y i ) = α 1 + β x i i A E ( Y i ) = α 2 + β x i i A α 1α 2 A tZA{1,,n}mi(Yja)=α1+βxjajaZAmi(Yja)=α2)+βxjajaZAα1α2)ZAt

Można by to zrozumieć, gdyby wydajność nie była problemem: znajdź test, który przejdzie wszystkie możliwości. Nawet wtedy jest to problematyczne; dwa kontrasty nie byłyby niezależne. Zapytałem o to eksperta w zakresie wykrywania wartości odstających, a on powiedział, że to koszmar kombinatoryczny. Następnie zapytałem, czy można udowodnić, że nie ma skutecznego sposobu, aby to zrobić, być może poprzez zmniejszenie do tego problemu trudnego NP. Powiedział tylko, że trzyma się z dala od problemów trudnych dla NP.2)n-1-1

Więc: Czy można udowodnić, że ten problem jest „trudny”, czy nie?

Michael Hardy
źródło
(+1) Kopiowanie komentarza do wyjaśnienia z wersji MO : Tylko drobna uwaga: jak czytam, kwalifikuje się pod twoją hipotezą zerową, ale i nie (niezależnie od ). Czy to jest to, co zamierzałeś? (Wydaje się, że nie pasuje do innych aluzji zawartych w pytaniu.)( 1 , 2 , 2 ) ( 1 , 1 , 1 ) β(α1,α2),α3))=(1,2),3))(1,2,2)(1,1,1)β
kardynał
Jak stwierdzono powyżej, hipoteza zerowa byłaby taka, że ​​potrzebujemy tylko jednej , a alternatywna hipoteza jest taka, że ​​potrzebujemy dwóch. Nie wiem, dlaczego masz trzeci. Można również rozważyć hipotezę zerową tylko jednej porównaniu z alternatywną hipotezą kilku, i może właśnie to powinienem zrobić zamiast tego. ααα
Michael Hardy
Dzięki. Być może odrzuciło mnie oryginalne stwierdzenie modelu jako , gdzie wziąłem jako potencjalną literówkę dla (ponieważ później pozwolono to zmieniać). α α iYja=α+βxja+εjaααja
kardynał
Cóż, z pewnością, gdyby to zależało od , byłby to model sparametryzowany, a wcale nie taki, jak zwykle nazywany „prostym modelem regresji liniowej”. iαja
Michael Hardy

Odpowiedzi:

1

Zauważyłem, że jak dotąd nikt nie odpowiedział na to pytanie ...

Zasadniczo pytanie brzmi: czy istnieje wektor 0-1 taki, że daje (znacznie) lepsze dopasowanie niż „Znacząco lepiej” można uchwycić jako sumę kwadratów jako nierówność. Powstaje zatem pytanie, czy istnieje rozwiązanie 0-1 nierówności Jest to wariant problemu ustawiania partycjonowania, który jest znany jako NP-trudny.Z

yja=α+βxja+γzja+ϵja
yja=α+βxja+ϵja.
fa(z)t.
użytkownik3697176
źródło
Czy problem ustawiania partycjonowania można faktycznie zredukować do tego problemu? Jeśli tak, to dowodzi, że jest to trudny problem.
Michael Hardy
Ten problem jest co najmniej tak trudny jak klasyczny problem z partycjonowaniem zestawu (SPP). SPP przyjmuje liniową kombinację wag i próbuje je pomnożyć przez +/- 1, aby uzyskać wyrażenie sumujące się do 0. Tutaj chcesz spełnić nierówność. Jeśli byłoby to możliwe do rozwiązania w czasie wielomianowym dla dowolnych danych wejściowych, to argument bisekcji pokazuje, że można również rozwiązać SPP w czasie wielomianowym. To nie jest dokładnie redukcja, ale jest blisko.
user3697176,