Adakah tabel umum teknik statistik yang diketahui yang menjelaskan bagaimana skala dengan ukuran dan dimensi sampel? Sebagai contoh, seorang teman saya mengatakan kepada saya tempo hari bahwa waktu perhitungan hanya menyortir data satu dimensi dengan ukuran n berjalan seperti n * log (n).
Jadi, misalnya, jika kita mundur y terhadap X di mana X adalah variabel d-dimensi, apakah itu pergi sebagai O (n ^ 2 * d)? Bagaimana skala jika saya ingin menemukan solusi melalui solusi Gauss-Markov tepat vs numerik kuadrat terkecil dengan metode Newton? Atau hanya mendapatkan solusi vs menggunakan tes signifikansi?
Saya kira saya lebih menginginkan sumber jawaban yang baik (seperti makalah yang merangkum skala berbagai teknik statistik) daripada jawaban yang baik di sini. Seperti, katakanlah, daftar yang mencakup penskalaan regresi berganda, regresi logistik, PCA, regresi bahaya proporsional cox, pengelompokan K-means, dll.
sumber
Jawaban:
Sebagian besar algoritma statistik yang efisien (dan non-sepele) bersifat iteratif sehingga analisis kasus terburuk
O()tidak relevan karena kasus terburuk adalah 'gagal untuk konvergen'.Namun demikian, ketika Anda memiliki banyak data, bahkan algoritma linier (
O(n)) dapat lambat dan Anda kemudian perlu fokus pada 'tersembunyi' di balik notasi. Misalnya, menghitung varian satu varian secara naif dilakukan pemindaian data dua kali (satu kali untuk menghitung estimasi rata-rata, dan kemudian satu kali untuk memperkirakan varians). Tapi itu juga bisa dilakukan dalam satu pass .Untuk algoritma berulang, yang lebih penting adalah tingkat konvergensi dan jumlah parameter sebagai fungsi dari dimensi data, elemen yang sangat mempengaruhi konvergensi. Banyak model / algoritma menumbuhkan sejumlah parameter yang eksponensial dengan jumlah variabel (misalnya splines) sementara beberapa lainnya tumbuh secara linear (misalnya mesin vektor dukungan, hutan acak, ...)
sumber
O(log(n) ).Anda menyebutkan regresi dan PCA dalam judul, dan ada jawaban yang pasti untuk masing-masing.
Kompleksitas asimtotik dari regresi linier berkurang menjadi O (P ^ 2 * N) jika N> P, di mana P adalah jumlah fitur dan N adalah jumlah pengamatan. Lebih detail dalam kompleksitas komputasi operasi regresi kuadrat terkecil .
Vanilla PCA adalah O (P ^ 2 * N + P ^ 3), seperti pada algoritma PCA Tercepat untuk data dimensi tinggi . Namun ada algoritma cepat untuk matriks yang sangat besar, dijelaskan dalam jawaban itu dan Algoritma PCA Terbaik Untuk Jumlah Fitur yang Besar? .
Namun saya tidak berpikir ada orang yang mengkompilasi review atau referensi atau buku tunggal pada subjek. Mungkin bukan proyek yang buruk untuk waktu senggang saya ...
sumber
Saya memberikan jawaban parsial yang sangat terbatas untuk paket analisis faktor konfirmatori yang saya kembangkan untuk Stata dalam artikel Jurnal Stata ini berdasarkan waktu simulasi yang sebenarnya. Analisis faktor konfirmatori diimplementasikan sebagai teknik estimasi kemungkinan maksimum, dan saya bisa melihat dengan mudah bagaimana waktu komputasi tumbuh dengan masing-masing dimensi (ukuran sampel
n, jumlah variabelp, jumlah faktork). Karena sangat bergantung pada bagaimana Stata berpikir tentang data (dioptimalkan untuk menghitung di seluruh kolom / pengamatan daripada baris), saya menemukan kinerja menjadiO(n^{0.68} (k+p)^{2.4})di mana 2.4 adalah matriks inversi asimptotik tercepat (dan ada banyak sekali hal itu dalam analisis faktor konfirmatori, iterasi maksimalisasi). Saya tidak memberikan referensi untuk yang terakhir, tapi saya rasa saya dapat ini dari Wikipedia .X'Xsumber