Nama fenomena pada perkiraan plot data disensor CDF

8

Dataset saya berisi dua (agak berkorelasi kuat) variabel (runtime algoritma) dan (jumlah node yang diperiksa, apa pun). Keduanya sangat berkorelasi dengan desain, karena algoritma dapat mengelola kira-kira node per detik.tnc

Algoritma dijalankan pada beberapa masalah, tetapi dihentikan jika solusi belum ditemukan setelah beberapa waktu habis . Jadi data disensor dengan benar pada variabel waktu.T

Saya memplot perkiraan fungsi kepadatan kumulatif (atau jumlah terakumulasi) dari variabel untuk kasus-kasus di mana algoritma itu berakhir dengan . Ini menunjukkan berapa banyak masalah yang dapat dipecahkan dengan memperluas paling banyak node dan berguna untuk membandingkan berbagai konfigurasi algoritma. Tetapi dalam plot untuk , ada ekor lucu di atas yang berbelok ke kanan, seperti yang dapat dilihat pada gambar di bawah ini. Bandingkan ecdf untuk variabel , di mana penyensoran dilakukan.nt<Tnnt

Hitungan Kumulatifn

ecdf of n

Jumlah yang terakumulasi darit

ecdf of t

Simulasi

Saya mengerti mengapa ini terjadi, dan dapat mereproduksi efek dalam simulasi menggunakan kode R berikut . Ini disebabkan oleh penyensoran pada variabel yang sangat berkorelasi di bawah penambahan beberapa noise.

qplot(
  Filter(function(x) (x + rnorm(1,0,1)[1]) < 5,
         runif(10000,0,10)),
  stat="ecdf",geom="step")

data sintetis

Bagaimana fenomena ini disebut? Saya perlu menyatakan dalam publikasi bahwa penggemar ini adalah artefak dari eksperimen dan tidak mencerminkan distribusi yang sebenarnya.

ziggystar
sumber
Apakah ini karena terminasi dini?
lcrmorin
Bisakah Anda memodelkan data Anda dengan distribusi parametrik? Anda dapat mencobanya hanya dengan menggunakan data yang tidak disensor. Jika berhasil, maka Anda bisa menggunakan kemungkinan maksimum pada seluruh dataset untuk mendapatkan perkiraan CDF yang sebenarnya dan menghilangkan perilaku di grafik Anda.
soakley
@ soakly Sampelnya bukan iis. Algoritme berjalan pada sekumpulan masalah tolok ukur, dan yang pada dasarnya menentukan bentuk kurva (bersama dengan karakteristik konfigurasi algoritma).
ziggystar
@lmorin Saya tidak tahu persis apa artinya terminasi dini, tetapi data disensor dengan benar pada variabel waktu.
ziggystar
1
Kuantitas dalam dua tampilan pertama sebenarnya bukan ECDFs, karena nilai yang diambil oleh ECDFs ada pada [0,1]. Akan lebih baik untuk melabeli mereka dengan judul yang lebih akurat.
Glen_b -Reinstate Monica

Jawaban:

1

Saya bukan ahli, tapi saya percaya apa yang Anda lihat adalah analog dengan kliping lembut .

Sortir Kliping (Gain Compression)

Ini sedikit berbeda, karena kliping Anda disebabkan oleh proses non-deterministik, di mana sinyal Anda terpotong ketika ditambah suara acak melebihi ambang, bukannya perangkat yang secara deterministik mengurangi sinyal analog. Saya memiliki pedal gitar yang melakukan ini, itu melembutkan "pukulan" dari bermain gitar listrik:

Demo Kompresor Keeyley

Sepertinya analogi yang layak. Saya tidak yakin apakah ada nama di komunitas statistik.

Matthew Drury
sumber
0

Saya menduga Anda mengalami keluarga distribusi stabil non-simetris.
Pertama, plot ecdf Anda dalam plot log-log. Mengadopsi pendekatan parametrik, asumsikan Distribusi Pareto, masukkan deskripsi gambar di sini

Cdf dalam kasus Anda diterjemahkan sebagai Ft(t)=1(tmint)a for t>tmindimana tminadalah waktu penyelesaian minimum algoritme Anda, maka ambang yang muncul di sebelah kiri grafik ecdf
Jika Anda melihat garis dalam plot log-log, maka Anda berada di jalur yang benar, buat regresi linier pada log yang mentransformasikan data Anda harus, untuk mencari tahuα^, yang disebut indeks Pareto.

Indeks pareto harus lebih besar dari 1, ia memberikan dan menginterpretasikan "tailness" yang berat dari distribusi, berapa banyak data yang terbentang di tepinya. Semakin dekat dengan 1 semakin banyak situasi patogen yang Anda miliki.
Dengan kata lain,αmenyatakan rasio dari node yang menghabiskan waktu yang dapat diabaikan vs node yang menghabiskan waktu yang berlebihan sebelum penyelesaiannya. Pembaca sebelumnya menunjukkan fakta bahwa Anda mengakhiri eksperimen Anda secara tiba-tiba, ini menimbulkan kerumitan yang digambarkan sebagaiα^=α^(T). Saya sarankan Anda harus bervariasiT untuk mengeksplorasi ketergantungan ini.

Fenomena ekor berat adalah umum dalam ilmu komputer, terutama ketika node bersaing melawan sumber daya bersama secara acak, misalnya jaringan komputer.

aarsakian
sumber
2
Saya tidak berpikir masalah saya terletak pada menemukan model yang benar. Anda melihat plot kedua dalam pertanyaan saya? Distribusi sebenarnya akan ditampilkan sebagai garis, tetapi karena efek sensor menjadi kurva. Saya ingin tahu bagaimana menyebut fenomena ini.
ziggystar
Node Anda berbagi sumber daya yang sama, CPU Anda yang secara tidak langsung tercermin pada fluktuasi penyelesaian waktu dan titik-titik merah dan merah muda yang cukup jauh dari massa utama dari distribusi masing-masing adalah apa yang membuat saya curiga. Node pemrosesan yang tahan lama akan memengaruhi node lainnya, saya berspekulasi bahwa mereka pada akhirnya akan mengusir massa dari pusatnya.
aarsakian
2
Saya tidak yakin apakah Anda memahami domain dengan benar: Masalahnya adalah pencarian. Algoritma melihat sebuah node pada suatu waktu untuk menemukan solusi node. Algoritma yang lebih baik harus melihat lebih sedikit node sebelum menemukan solusi (karena memilih node lebih pintar). Melihat sebuah node membutuhkan waktu, dan karenanya jumlah node yang diperiksa dan waktu yang dikonsumsi harus berkorelasi dengan kuat.
ziggystar
-1

katakan bahwa distribusi Anda terpotong , seperti terpotong normal

Aksakal
sumber