Wer ist diese Wahrscheinlichkeitsverteilung?

16

Einführung

In dieser Herausforderung erhalten Sie eine Liste nichtnegativer Gleitkommazahlen, die unabhängig von einer Wahrscheinlichkeitsverteilung erstellt wurden. Ihre Aufgabe ist es, diese Verteilung aus den Zahlen abzuleiten. Um die Herausforderung zu meistern, stehen Ihnen nur fünf Verteilungen zur Auswahl.

Beachten Sie, dass alle oben genannten Verteilungen genau 1/2 bedeuten.

Die Aufgabe

Ihre Eingabe besteht aus einem Array nichtnegativer Gleitkommazahlen mit einer Länge zwischen 75 und 100 einschließlich. Ihre Ausgabe soll einer der Buchstaben sein UTBEG, basierend darauf, aus welcher der oben genannten Verteilungen die Zahlen stammen.

Regeln und Wertung

Sie können entweder ein vollständiges Programm oder eine Funktion angeben. Standardlücken sind nicht zulässig.

In diesem Repository befinden sich fünf Textdateien, eine für jede Distribution mit einer Länge von jeweils genau 100 Zeilen. Jede Zeile enthält eine durch Kommas getrennte Liste mit 75 bis 100 Gleitkommazahlen, die unabhängig von der Verteilung gezeichnet und auf 7 Nachkommastellen gekürzt werden. Sie können die Trennzeichen ändern, um sie an das native Array-Format Ihrer Sprache anzupassen. Um als Antwort zu gelten, sollte Ihr Programm mindestens 50 Listen aus jeder Datei korrekt klassifizieren . Die Punktzahl einer gültigen Antwort ist die Anzahl der Bytes + die Gesamtzahl der falsch klassifizierten Listen . Die niedrigste Punktzahl gewinnt.

Zgarb
quelle
Ich hätte wahrscheinlich früher fragen sollen, aber wie viel Optimierung für die Testfälle wird erwartet? Ich bin an einem Punkt angelangt, an dem ich meine Punktzahl verbessern kann, indem ich einige Parameter optimiere. Die Auswirkung auf die Punktzahl hängt jedoch wahrscheinlich von den angegebenen Testfällen ab.
Dennis
2
@Dennis Sie können so viel optimieren, wie Sie möchten, die Testfälle sind ein fester Bestandteil der Herausforderung.
Zgarb
YU NO Student-t-Verteilung? = (
N3buchadnezzar

Antworten:

6

Julia, 60 62 Bytes + 25 2 Fehler = 82 64

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

Das ist ziemlich einfach. Die Varianz der Verteilungen ist größtenteils unterschiedlich - 1/4 für Exponential, 1/8 für Beta, 1/12 für Gamma und Uniform und 1/24 für Dreieck. Wenn wir also die Varianz (hier stdfür die Standardabweichung, die Quadratwurzel der Varianz) verwenden, um die wahrscheinliche Verteilung zu bestimmen, müssen wir nur mehr tun, um Gamma von Uniform zu unterscheiden. Dafür suchen wir nach einem Wert größer als 1 (mit any(k.>1)) - das heißt, wir überprüfen sowohl Exponential- als auch Gamma- Werte , da dies die Gesamtleistung verbessert.

Um ein Byte zu speichern, wird die Zeichenfolge indiziert "EGTBU", anstatt sie direkt als Zeichenfolge innerhalb der Bedingungen auszuwerten.

Speichern Sie zu Testzwecken die txt-Dateien in einem Verzeichnis (behalten Sie die Namen unverändert bei) und führen Sie Julia REPL in diesem Verzeichnis aus. Fügen Sie dann die Funktion einem Namen als hinzu

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

und verwenden Sie den folgenden Code, um das Testen zu automatisieren (dies wird aus der Datei gelesen, in ein Array von Arrays konvertiert, die Funktion verwendet und für jede Nichtübereinstimmung ausgegeben):

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)

Die Ausgabe besteht aus Zeilen, die den nicht übereinstimmenden Fall, die korrekte Verteilung -> die ermittelte Verteilung und die berechnete Varianz enthalten (z. B. 13 G->E 0.35008999281668357bedeutet dies, dass die 13. Zeile in G.txt, die eine Gamma-Verteilung sein sollte, als Exponential bestimmt wird Verteilung mit der Standardabweichung 0,35008999 ...)

Nach jeder Datei wird auch die Anzahl der Nichtübereinstimmungen für diese Datei ausgegeben, und am Ende werden auch die gesamten Nichtübereinstimmungen angezeigt (und es sollte 2 lauten, wenn wie oben ausgeführt). Im Übrigen sollte es 1 Mismatch für G.txt und 1 Mismatch für U.txt geben

Glen O
quelle
7

R, 202 192 184 182 162 154 Bytes + 0 Fehler

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))]

Dies basiert auf der Bayes'schen Formel P (D = d | X = x) = P (X = x | D = d) * P (D = d) / P (X = x), wobei D die Verteilung und X ist ist die Zufallsstichprobe. Wir wählen das d so, dass P (D = d | X = x) von den 5 am größten ist.

Ich gehe von einem flachen Prior aus (dh P (D = di) = 1/5 für i in [1,5]), was bedeutet, dass P (D = d) im Zähler in allen Fällen gleich ist (und der Nenner gleich wäre) ist in jedem Fall gleich), so dass wir alles außer dem P (x = X | D = d) weggolfen können, was (mit Ausnahme der Dreiecksverteilung) die nativen Funktionen in R vereinfacht.

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))]
}

Beachten Sie, dass die ungolfed version nicht genau der golfed version entspricht, da durch das Entfernen des Nenners der Fall von Inf / Inf vermieden wird, der auftritt, wenn Sie zulassen, dass die Beta-Verteilung über das geschlossene Intervall [0,1] statt (0, 1) - wie die Beispieldaten. Eine zusätzliche if-Anweisung würde damit umgehen, aber da dies nur zu Illustrationszwecken dient, lohnt es sich wahrscheinlich nicht, die Komplexität hinzuzufügen, die nicht im Mittelpunkt des Algorithmus steht.

Vielen Dank an @Alex A. für zusätzliche Code-Reduzierungen. Vor allem für which.max!

njnnja
quelle
1
Sie erreichen 190 Bytes, indem Sie den Zeilenumbruch nach dem Öffnen {und vor dem Schließen entfernen }und prodz. B. P=proddann Aliasing ausführen P(dunif(x))usw. Die Funktion benötigt keinen Namen, um eine gültige Übermittlung zu sein, und Sie können ihn entfernen p=. Auch hervorragende Arbeit. :)
Alex A.
2
Sie können es mit den obigen Vorschlägen auf 182 bringen und which.max(c(u,r,b,e,g))anstelle von verwenden 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.
Wie kannst du es wagen, R für eine Herausforderung mit Statistiken zu verwenden !!
Fehler
6

CJam, 76

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

Der Quellcode ist 43 Bytes lang und klassifiziert 33 Listen falsch .

Nachprüfung

$ 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

Idee

Es ist einfach, die Exponential- und Gammaverteilung von den übrigen zu unterscheiden, da sie die einzigen Verteilungen sind, die Werte größer als 1 annehmen .

Um zwischen Gamma , Exponential und anderen zu entscheiden , betrachten wir den zweithöchsten Wert der Stichprobe.

  • Wenn es in [1.5, ∞) liegt , raten wir Gamma .

  • Wenn es in [1, 1.5] liegt , schätzen wir exponentiell .

  • Wenn es in [0, 1) liegt , haben wir drei verbleibende Möglichkeiten.

    Die verbleibenden Verteilungen können anhand des Prozentsatzes der Stichprobenwerte unterschieden werden, die nahe am Mittelwert ( 0,5 ) liegen.

    Wir teilen die Länge der Stichprobe durch die Anzahl der Werte, die in (0,3, 0,7) fallen, und sehen uns den resultierenden Quotienten an.

    • Wenn es in (1, 2] liegt , raten wir dreieckig .

    • Wenn es in (2, 3] liegt , raten wir Uniform .

    • Wenn es in (3, ∞) liegt , raten wir Beta .

Code

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
quelle
3

Matlab, 428 328 Bytes + 33 falsch klassifiziert

Dieses Programm vergleicht im Grunde die reale CDF mit einer geschätzten anhand der Daten und berechnet dann den mittleren Abstand zwischen diesen beiden: Ich denke, das Bild erklärt mehr:

Bildbeschreibung hier eingeben

Die in diesem Bild gezeigten Daten zeigen ziemlich deutlich, dass es zur türkisfarbenen Verteilung gehört, da es dieser ziemlich nahe kommt, also ist es im Grunde das, was mein Programm tut. Es kann wohl etwas mehr golfen werden. Für mich war das zunächst eine konzeptionelle Herausforderung, nicht sehr golfen.

Dieser Ansatz ist auch unabhängig von den gewählten pdfs, er würde für jede Menge von Distributionen funktionieren .

Der folgende (ungolfed) Code sollte zeigen, wie es gemacht wird. Die Golfversion ist unten.

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

Vollgolf-Version:

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)
fehlerhaft
quelle
2

Perl, 119 Bytes + 8 Fehlklassifizierungen = 127

Ich habe einen winzigen Entscheidungsbaum für drei Funktionen erstellt:

  • $ o: boolean: falls Samples> 1.0 sind
  • $ t: count: 0-th minus 6-th 13-ile in den Bereich 0-1 geschnitten,
  • $ h: count: 0-tes minus 6-tes plus 12-tes 13-ile, eingekürzt in den Bereich 0-1

Aufgerufen mit perl -F, -lane -e '...'. Ich bin nicht sicher, ob ich eine Strafe für die nicht standardmäßigen Parameter hinzufügen soll. Wenn die Kommas Leerzeichen wären , hätte ich wohl ohne das -F davonkommen können ,

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

Die leicht formatierte Ausgabe (ohne das Flag -l) lautet:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
    bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
    eeegeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
gggggggeggggggggggggggggggggggggggggggggggggggggggg
    ggggggggggggggggggggggggggggggggggggggggggg
ttttttttttttttttttttttttttttttttttttttttttttttttttttt
    ttttttttttttttttttttttttttttttttttttttttttttttt
uuuuuuuuuuuuuuuuuuuuuuuuutuuuuuuuuuuuuuuuuuuuuuu
    uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
Dale Johnson
quelle
0

Python, 318 Bytes + 35 Fehlklassifizierungen

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)

Idee: Die Verteilung basiert auf dem p-Wert des Kolmogorov-Smirnov-Tests.

Prüfung

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
quelle