Menguji kontras tertentu: Apakah ini terbukti merupakan masalah yang sulit, atau tidak?

12

Saya memposting ini ke mathoverflow dan tidak ada yang menjawab:

Metode Scheffé untuk mengidentifikasi kontras yang signifikan secara statistik telah diketahui secara luas. Sebuah kontras antara sarana , dari populasi adalah kombinasi linear di mana , dan kelipatan skalar dari suatu kontras pada dasarnya adalah kontras yang sama, sehingga dapat dikatakan bahwa rangkaian kontras adalah ruang proyektif. Metode Scheffé menguji hipotesis nol yang mengatakan semua kontras di antara iniμii=1,,rri=1rciμii=1rci=0r populasi ini adalah0 , dan diberi tingkat signifikansiα , menolak hipotesis nol dengan probabilitasαmengingat bahwa hipotesis nol itu benar. Dan jika hipotesis nol ditolak, Scheffé menunjukkan bahwa pengujiannya memberi tahu kami perbedaan mana yang sangat berbeda dari 0 (saya tidak yakin artikel Wikipedia yang saya tautkan dengan poin itu).

Saya ingin tahu apakah seseorang dapat melakukan hal serupa dalam situasi yang berbeda. Pertimbangkan model regresi linier sederhana Yi=α+βxi+εi , di mana εii.i.d.N(0,σ2) , i=1,,n .

Hipotesis nol yang ingin saya pertimbangkan menyangkut jenis kontras yang berbeda. Dikatakan tidak ada subset A{1,,n} sedemikian rupa sehingga E(Yi)=α1+βxi untuk iA dan E(Yi)=α2+βxi untuk iA , di mana α1α2. Jika subset A ditentukan di muka, maka dua-sample biasa t -test melakukannya, tapi kami ingin sesuatu yang menganggap semua himpunan bagian dan memegang bawah probabilitas menolak hipotesis nol benar.

Orang bisa mengetahui hal ini jika efisiensi bukan masalah: temukan tes yang melewati semua kemungkinan 2n11 . Bahkan kemudian itu bermasalah; dua kontras tidak akan independen. Saya bertanya kepada seorang ahli tentang deteksi outlier tentang ini dan dia hanya mengatakan itu adalah mimpi buruk kombinasi. Lalu saya bertanya apakah ada yang bisa membuktikan bahwa tidak ada cara yang efisien untuk melakukannya, mungkin dengan mengurangi masalah NP-hard untuk itu. Dia hanya mengatakan dia menjauh dari masalah NP-hard.

Jadi: Bisakah seseorang membuktikan bahwa masalah ini "keras" atau tidak?

Michael Hardy
sumber
(+1) Menyalin komentar untuk klarifikasi dari versi MO : Hanya sedikit klarifikasi: Ketika saya membacanya, memenuhi syarat dalam hipotesis nol Anda, tetapi ( 1 , 2 , 2 ) dan ( 1 , 1 , 1 ) tidak (terlepas dari β ). Apakah itu yang Anda maksudkan? (Tampaknya tidak cocok dengan beberapa sindiran lain yang dibuat dalam pertanyaan.)(α1,α2,α3)=(1,2,3)(1,2,2)(1,1,1)β
kardinal
Seperti yang dinyatakan di atas, hipotesis nol adalah bahwa kita hanya perlu satu , dan hipotesis alternatifnya adalah kita perlu dua. Saya tidak tahu mengapa Anda punya yang ketiga. Kita juga dapat mempertimbangkan hipotesis nol hanya satu α versus hipotesis alternatif beberapa, dan mungkin itulah yang seharusnya saya lakukan. αα
Michael Hardy
Yi=α+βxi+εiααi
Yah, tentu saja jika tergantung pada itu akan menjadi model yang terlalu parametrik, dan sama sekali tidak seperti yang biasa disebut "model regresi linier sederhana". αi
Michael Hardy

Jawaban:

1

Melihat bahwa tidak ada yang menjawab pertanyaan ini sejauh ini ...

Z

yi=α+βxi+γzi+ϵi
yi=α+βxi+ϵi.
f(z)t.
Ini adalah varian dari masalah set partisi, yang dikenal sebagai NP-hard.
pengguna3697176
sumber
Bisakah masalah set partisi benar-benar dikurangi menjadi masalah ini? Jika demikian, itu akan membuktikan ini adalah masalah yang sulit.
Michael Hardy
Masalah ini setidaknya sama sulitnya dengan masalah set partisi klasik (SPP). SPP mengambil kombinasi linear bobot dan mencoba mengalikannya dengan +/- 1 untuk mendapatkan ekspresi yang berjumlah 0. Di sini Anda ingin memuaskan ketidaksetaraan. Jika ini dipecahkan dalam waktu polinomial untuk input sewenang-wenang, maka argumen pembagian dua menunjukkan bahwa Anda juga bisa menyelesaikan SPP dalam waktu polinomial. Itu bukan pengurangan, tapi dekat.
user3697176