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

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 $\mu_i$ $i=1,\ldots,r$ $r$ $\sum_{i=1}^r c_i \mu_i$ $\sum_{i=1}^r c_i=0$ $r$ $0$ $\alpha$ $\alpha$ 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 , . $Y_i = \alpha + \beta x_i + \varepsilon_i$ $\varepsilon_i\sim\operatorname{i.i.d.}N(0,\sigma^2)$ $i=1,\ldots,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. $A\subseteq\lbrace 1,\ldots,n\rbrace$ $E(Y_i) = \alpha_1 + \beta x_i$ $i\in A$ $E(Y_i) = \alpha_2 + \beta x_i$ $i\not\in A$ $\alpha_1\ne\alpha_2$ $A$ $t$

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}, α_{3}) = (1, 2, 3)

$(\alpha_1, \alpha_2, \alpha_3) = (1,2,3)$

(1, 2, 2)

$(1,2,2)$

(1, 1, 1)

$(1,1,1)$

β

$\beta$

— 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.

α

$\alpha$

α

$\alpha$

— 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ć).

Y_{i} = α + β x_{i} + ε_{i}

$Y_i = \alpha + \beta x_i + \varepsilon_i$

α

$\alpha$

α_{i}

$\alpha_i$

— 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”.

α

$\alpha$

i

$i$

— Michael Hardy

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$

y_{ja} = α + β x_{ja} + γ z_{ja} + ϵ_{ja}

$y_i = \alpha + \beta x_i + \gamma z_i + \epsilon_i$

y_{ja} = α + β x_{ja} + ϵ_{ja} .

$y_i = \alpha + \beta x_i + \epsilon_i.$

fa (z) \geq t .

$f(z) \ge 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.

${}\qquad{}$

— 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,