Siapa itu distribusi probabilitas?

16

pengantar

Dalam tantangan ini, Anda akan diberikan daftar nomor floating point non-negatif yang diambil secara independen dari beberapa distribusi probabilitas. Tugas Anda adalah menyimpulkan distribusi itu dari angka-angka. Untuk membuat tantangan menjadi layak, Anda hanya memiliki lima distribusi untuk dipilih.

Perhatikan bahwa semua distribusi di atas memiliki tepat 1/2.

Tugas

Input Anda adalah array nomor floating point non-negatif, dengan panjang antara 75 dan 100 inklusif. Keluaran Anda akan menjadi salah satu dari huruf-huruf tersebut UTBEG, berdasarkan distribusi mana yang Anda tebak angka-angkanya.

Aturan dan Penilaian

Anda dapat memberikan program lengkap atau fungsi. Celah standar tidak diijinkan.

Dalam repositori ini , ada lima file teks, satu untuk setiap distribusi, masing-masing panjangnya persis 100 baris. Setiap baris berisi daftar koma-dibatasi 75 hingga 100 mengapung diambil secara independen dari distribusi dan dipotong menjadi 7 digit setelah titik desimal. Anda dapat memodifikasi pembatas agar sesuai dengan format array asli bahasa Anda. Agar memenuhi syarat sebagai jawaban, program Anda harus mengklasifikasikan dengan benar setidaknya 50 daftar dari setiap file . Skor dari jawaban yang valid adalah jumlah byte + jumlah total daftar yang salah klasifikasi . Skor terendah menang.

Zgarb
sumber
Saya mungkin seharusnya bertanya sebelumnya, tetapi berapa banyak optimisasi terhadap kasus uji yang diharapkan? Saya pada titik di mana saya dapat meningkatkan skor saya dengan mengubah beberapa parameter, tetapi dampak pada skor mungkin akan tergantung pada kasus uji yang diberikan.
Dennis
2
@ Dennis Anda dapat mengoptimalkan sebanyak yang Anda inginkan, kasus uji adalah bagian yang tetap dari tantangan.
Zgarb
YU TIDAK Distribusi siswa-t? = (
N3buchadnezzar

Jawaban:

6

Julia, 60 62 byte + 25 2 kesalahan = 82 64

k->"EGTBU"[(V=std(k);any(k.>1)?V>.34?1:2:V<.236?3:V>.315?4:5)]

Ini cukup sederhana. Varian untuk distribusi sebagian besar berbeda - 1/4 untuk eksponensial, 1/8 untuk beta, 1/12 untuk gamma dan seragam, dan 1/24 untuk segitiga. Dengan demikian, jika kita menggunakan varians (di sini dilakukan menggunakan stddeviasi standar, akar kuadrat varians) untuk menentukan distribusi yang mungkin, kita hanya perlu melakukan lebih banyak untuk membedakan gamma dari seragam; untuk itu, kami mencari nilai yang lebih besar dari 1 (menggunakan any(k.>1)) - yang mengatakan, kami melakukan pemeriksaan untuk eksponensial dan gamma, karena meningkatkan kinerja secara keseluruhan.

Untuk menyimpan byte, pengindeksan string "EGTBU"dilakukan alih-alih langsung mengevaluasi ke string dalam kondisi.

Untuk pengujian, simpan file txt ke dalam direktori (pertahankan nama apa adanya), dan jalankan Julia REPL di direktori tersebut. Kemudian, lampirkan fungsi ke nama sebagai

f=k->"EGTBU"[(V=std(k);any(k.>1)?V>.34?1:2:V<.236?3:V>.315?4:5)]

dan gunakan kode berikut untuk mengotomatiskan pengujian (ini akan membaca dari file, mengubahnya menjadi array array, menggunakan fungsi, dan output untuk setiap ketidakcocokan):

m=0;for S=["B","E","G","T","U"] K=open(S*".txt");F=readcsv(K);
M=Array{Float64,1}[];for i=1:100 push!(M,filter(j->j!="",F[i,:]))end;
close(K);n=0;
for i=1:100 f(M[i])!=S[1]&&(n+=1;println(i," "S,"->",f(M[i])," ",std(M[i])))end;
println(n);m+=n;end;println(m)

Output akan terdiri dari baris yang berisi case yang tidak cocok, distribusi yang benar -> distribusi yang ditentukan, dan varians yang dihitung (mis. 13 G->E 0.35008999281668357Berarti bahwa baris ke-13 dalam G.txt, yang seharusnya merupakan distribusi gamma, ditentukan sebagai eksponensial) distribusi, dengan standar deviasi 0,35008999 ...)

Setelah setiap file, itu juga menampilkan jumlah ketidakcocokan untuk file itu, dan kemudian pada akhirnya juga menampilkan ketidakcocokan total (dan harus membaca 2 jika dijalankan seperti di atas). Kebetulan, seharusnya 1 ketidakcocokan untuk G.txt dan 1 ketidakcocokan untuk U.txt

Glen O
sumber
7

R, 202 192 184 182 162 154 byte + 0 kesalahan

function(x)c("U","T","B","E","G")[which.max(lapply(list(dunif(x),sapply(x,function(y)max(0,2-4*abs(.5-y))),dbeta(x,.5,.5),dexp(x,2),dgamma(x,3,6)),prod))]

Ini didasarkan pada rumus Bayesian P (D = d | X = x) = P (X = x | D = d) * P (D = d) / P (X = x), di mana D adalah distribusi dan X adalah sampel acak. Kami memilih d sehingga P (D = d | X = x) adalah yang terbesar dari 5.

Saya mengasumsikan flat sebelumnya (yaitu P (D = di) = 1/5 untuk i dalam [1,5]), yang berarti bahwa P (D = d) dalam pembilang adalah sama dalam semua kasus (dan penyebutnya akan sama saja dalam semua kasus), jadi kita bisa bermain golf semuanya kecuali P (x = X | D = d), yang (kecuali untuk distribusi segitiga) menyederhanakan fungsi asli di R.

ungolfed:

function(x){
  u=prod(dunif(x))
  r=prod(sapply(x,function(y)max(0,2-4*abs(.5-y))))
  b=prod(dbeta(x,.5,.5))
  e=prod(dexp(x,2))
  g=prod(dgamma(x,3,6))
  den=.2*u+.2*r+.2*b+.2*e+.2*g
  c("U","T","B","E","G")[which.max(c(u*.2/den,r*.2/den,b*.2/den,e*.2/den,g*.2/den))]
}

Perhatikan bahwa versi yang tidak dikenali tidak persis sama dengan versi golf karena menyingkirkan penyebut menghindari kasus Inf / Inf yang terjadi jika Anda membiarkan distribusi beta melebihi interval tertutup [0,1] alih-alih (0, 1) - seperti halnya data sampel. Pernyataan if tambahan akan menangani itu tetapi karena itu hanya untuk tujuan ilustrasi, itu mungkin tidak layak menambahkan kompleksitas yang bukan inti dari algoritma.

Terima kasih @Alex A. untuk pengurangan kode tambahan. Khusus untuk yang. Max!

njnnja
sumber
1
Anda bisa mendapatkan ini hingga 190 byte dengan menghapus jeda baris setelah pembukaan {dan yang sebelum penutupan }, dan aliasing prod, misalnya P=prod, lalu melakukan P(dunif(x)), dll. Fungsi tidak memerlukan nama untuk menjadi kiriman yang valid, sehingga Anda dapat menghapus p=. Juga, pekerjaan luar biasa. :)
Alex A.
2
Anda bisa mendapatkannya ke 182 menggunakan saran di atas dan menggunakan which.max(c(u,r,b,e,g))di tempat c(u,r,b,e,g)==max(c(u,r,b,e,g)).
Alex A.
156:function(x){c("U","T","B","E","G")[which.max(lapply(list(dunif(x),sapply(x,function(y)max(0,2-4*abs(.5-y))),dbeta(x,.5,.5),dexp(x,2),dgamma(x,3,6)),prod))]}
Alex A.
Beraninya kamu menggunakan R untuk tantangan yang melibatkan statistik !!
flawr
6

CJam, 76

{2f*__{(z.4<},,%,4e<"UBT"="EG"\*\$-2=i3e<=}

Kode sumber panjangnya 43 byte dan salah mengklasifikasikan 33 daftar.

Verifikasi

$ count()(sort | uniq -c | sort -nr)
$ cat score.cjam
qN%{',' er[~]
  {2f*__{(z.4<},,%,4e<"UBT"="EG"\*\$-2=i3e<=}
~N}/
$ for list in U T B E G; { echo $list; cjam score.cjam < $list.txt | count; }
U
     92 U
      6 B
      2 T
T
    100 T
B
     93 B
      7 U
E
     92 E
      8 G
G
     90 G
      6 E
      3 T
      1 U

Ide

Membedakan distribusi eksponensial dan gamma dari yang tersisa itu mudah, karena hanya distribusi yang mengambil nilai lebih besar dari 1 .

Untuk memutuskan antara gamma , eksponensial , dan lainnya, kami melihat nilai tertinggi kedua dari sampel.

  • Jika terletak pada [1,5, ∞) , kami menebak gamma .

  • Jika terletak di [1, 1.5) , kami menebak eksponensial .

  • Jika terletak pada [0, 1) , kami memiliki tiga kemungkinan yang tersisa.

    Distribusi yang tersisa dapat dibedakan dengan persentase nilai sampel yang terletak dekat dengan rata-rata ( 0,5 ).

    Kami membagi panjang sampel dengan jumlah nilai yang masuk (0,3, 0,7) dan melihat hasil bagi.

    • Jika terletak pada (1, 2) , kami menebak segitiga .

    • Jika terletak di (2, 3) , kami menebak seragam .

    • Jika terletak di (3, ∞) , kami menebak beta .

Kode

2f*    e# Multiply all sample values by 2.
__     e# Push to copies of the sample.
{      e# Filter; for each (doubled) value in the sample:
  (z   e#   Subtract 1 and apply absolute value.
  .4<  e#   Check if the result is smaller than 0.4.
},     e# If it is, keep the value.
,/     e# Count the kept values (K).
%      e# Select every Kth value form the sample, starting with the first.
,      e# Compute the length of the resulting array.
       e# This performs ceiled division of the sample length by K.
4e<    e# Truncate the quotient at 4.
"UBT"= e# Select 'T' for 2, 'U' for 3 and 'B' for 4.
"EG"\* e# Place the selected character between 'E' and 'G'.
\$     e# Sort the remaining sample.
-2=i   e# Extract the second-highest (doubled) value and cast to integer.
3e<    e# Truncate the result at 3.
=      e# Select 'E' for 3, 'G' for 2 and the character from before for 1.
Dennis
sumber
3

Matlab, 428 328 byte + 33 kesalahan klasifikasi

Program ini pada dasarnya membandingkan CDF nyata dengan perkiraan yang diberikan data, dan kemudian menghitung jarak rata-rata antara keduanya: Saya pikir gambar menjelaskan lebih lanjut:

masukkan deskripsi gambar di sini

Data yang diperlihatkan dalam gambar ini di sini menunjukkan dengan cukup jelas bahwa itu milik distribusi pirus, karena cukup dekat dengan yang itu, sehingga pada dasarnya adalah apa yang program saya lakukan. Mungkin bisa bermain golf lebih banyak. Bagi saya itu pertama-tama tantangan konseptual, tidak terlalu golf.

Pendekatan ini juga tidak tergantung pada pdf yang dipilih, itu akan bekerja untuk setiap set distribusi.

Kode (ungolfed) berikut harus menunjukkan bagaimana hal itu dilakukan. Versi golf di bawah ini.

function r=p(x);
data=sort(x(1:75));
%% cumulative probability distributiosn
fu=@(x)(0<x&x<1).*x+(1<=x).*1;
ft=@(x)(0<x&x< 0.5).* 2.*x.^2+(1-2*(1-x).^2).*(0.5<=x&x<1)+(1<=x);
fb=@(x)(0<x&x<1).*2.*asin(sqrt(x))/pi+(1<=x);
fe=@(x)(0<x).*(1-exp(-2*x));
fg=@(x)(0<x).*(1-exp(-x*6).*(1+x*6+1/2*(6*x).^2));
fdata = @(x)sum(bsxfun(@le,data,x.'),2).'/length(data);
f = {fe,fg,fu,ft,fb};
str='EGUTB';
%calculate distance to the different cdfs at each datapoint
for k=1:numel(f);
dist(k) = max(abs(f{k}(x)-fdata(x)));
end;
[~,i]=min(dist);
r=str(i);
end

Versi sepenuhnya golf:

function r=p(x);f={@(x)(0<x).*(1-exp(-2*x)),@(x)(0<x).*(1-exp(-x*6).*(1+x*6+18*x.^2)),@(x)(0<x&x<1).*x+(1<=x),@(x)(0<x&x<.5).*2.*x.^2+(1-2*(1-x).^2).*(.5<=x&x<1)+(1<=x),@(x)(0<x&x<1).*2.*asin(sqrt(x))/pi+(1<=x)};s='EGUTB';for k=1:5;d(k)=max(abs(f{k}(x)-sum(bsxfun(@le,x,x.'),2).'/nnz(x)));end;[~,i]=min(d(1:5-3*any(x>1)));r=s(i)
cacat
sumber
2

Perl, 119 byte + 8 kesalahan klasifikasi = 127

Saya telah membuat pohon keputusan kecil pada tiga fitur:

  • $ o: boolean: jika ada sampel> 1.0
  • $ t: count: 0-minus 6-th 13-ile terpotong dalam rentang 0-1,
  • $ h: count: 0-minus 6-plus ditambah 12-ke-13 ile terpotong dalam kisaran 0-1

Diminta dengan perl -F, -lane -e '...'. Saya tidak yakin apakah saya harus menambahkan penalti untuk parameter non-standar. Jika koma adalah spasi, kurasa aku bisa pergi tanpa -F,

untuk (@F) {$ b [$ _ * 13] ++; $ o ++ jika $ _> 1}
$ h = ($ t = $ b [0] - $ b [6]) + $ b [12];
cetak $ o? ($ t> -2? "e": "g"): ($ h = 19? "b": "u"));
$ o = @ b = ()

Output yang sedikit diformat (tanpa flag -l) adalah:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
    bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
    eeegeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
gggggggeggggggggggggggggggggggggggggg
    gggggggggggggggggggggggggggggg
tttttttttttttttttttttttttttttttttttttttttttttttttt
    ttttttttttttttttttttttttttutttttttttttttttttttt
kamu
    uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuutuuuuuu
Dale Johnson
sumber
0

Python, 318 byte + 35 kesalahan klasifikasi

from scipy.stats import*
from numpy import*
def f(l):
    r={'U':kstest(l,'uniform')[1],'T':kstest(l,'triang',args=(.5,))[1],'B':kstest(l,'beta',args=(.5,.5))[1],'E':kstest(l,'expon',args=(0,.5,))[1],'G':kstest(l,'gamma',args=(3,0,1/6.0))[1]}
    if sum([x>1 for x in l]): r['U'],r['T'],r['B']=0,0,0
    return max(r,key=r.get)

Ide: distribusi ditebak berdasarkan nilai-p dari tes Kolmogorov-Smirnov.

Uji

from scipy.stats import*
from numpy import*
import os
from io import StringIO
dir=os.path.dirname(os.path.abspath(__file__))+"/random-data-master/"

def f(l):
    r={'U':kstest(l,'uniform')[1],'T':kstest(l,'triang',args=(.5,))[1],'B':kstest(l,'beta',args=(.5,.5))[1],'E':kstest(l,'expon',args=(0,.5,))[1],'G':kstest(l,'gamma',args=(3,0,1/6.0))[1]}
    if sum([x>1 for x in l]): r['U'],r['T'],r['B']=0,0,0
    return max(r,key=r.get)

U=[line.rstrip('\n').split(',') for line in open(dir+'U.txt')]
U=[[float(x) for x in r] for r in U]
T=[line.rstrip('\n').split(',') for line in open(dir+'T.txt')]
T=[[float(x) for x in r] for r in T]
B=[line.rstrip('\n').split(',') for line in open(dir+'B.txt')]
B=[[float(x) for x in r] for r in B]
E=[line.rstrip('\n').split(',') for line in open(dir+'E.txt')]
E=[[float(x) for x in r] for r in E]
G=[line.rstrip('\n').split(',') for line in open(dir+'G.txt')]
G=[[float(x) for x in r] for r in G]

i,_u,_t,_b,_e,_g=0,0,0,0,0,0
for u,t,b,e,g in zip(U,T,B,E,G):
    _u+=1 if f(u)=='U' else 0
    _t+=1 if f(t)=='T' else 0
    _b+=1 if f(b)=='B' else 0
    _e+=1 if f(e)=='E' else 0
    _g+=1 if f(g)=='G' else 0
    print f(u),f(t),f(b),f(e),f(g)
print _u,_t,_b,_e,_g,100*5-_u-_t-_b-_e-_g
Aetienne Sardon
sumber