Wprowadzenie

W tym wyzwaniu otrzymujesz listę nieujemnych liczb zmiennoprzecinkowych narysowanych niezależnie od pewnego rozkładu prawdopodobieństwa. Twoim zadaniem jest wywnioskować ten rozkład na podstawie liczb. Aby wyzwanie było wykonalne, masz tylko pięć dystrybucji do wyboru.

• U, równomierny rozkład w przedziale [0,1].
• T, rozkład trójkątny w przedziale [0,1] z trybem c = 1/2.
• B, rozkład beta w przedziale [0,1] o parametrach α = β = 1/2.
• E, rozkład wykładniczy w przedziale [0, ∞) ze współczynnikiem λ = 2.
• G, rozkład gamma w przedziale [0, ∞) o parametrach k = 3 i θ = 1/6.

Zauważ, że wszystkie powyższe rozkłady mają dokładnie 1/2.

Zadanie

Dane wejściowe to tablica nieujemnych liczb zmiennoprzecinkowych o długości od 75 do 100 włącznie. Twój wynik będzie jedną z literUTBEG , na podstawie której z powyższych rozkładów, jak się domyślacie, pochodzą liczby.

Zasady i punktacja

Możesz podać pełny program lub funkcję. Standardowe luki są niedozwolone.

W tym repozytorium znajduje się pięć plików tekstowych, po jednym dla każdej dystrybucji, każdy o długości dokładnie 100 linii. Każda linia zawiera rozdzielaną przecinkami listę od 75 do 100 liczb zmiennoprzecinkowych narysowanych niezależnie od rozkładu i obciętych do 7 cyfr po przecinku. Możesz zmodyfikować ograniczniki, aby pasowały do ​​natywnego formatu macierzy Twojego języka. Aby kwalifikować się jako odpowiedź, Twój program powinien poprawnie sklasyfikować co najmniej 50 list z każdego pliku . Wynik poprawnej odpowiedzi to liczba bajtów + całkowita liczba błędnie sklasyfikowanych list . Najniższy wynik wygrywa.

Julia, 60 62 bajtów + 25 2 błędy = 82 64

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

To jest dość proste. Wariancja rozkładów jest w większości różna - wynosi 1/4 dla wykładniczej, 1/8 dla beta, 1/12 dla gamma i munduru oraz 1/24 dla trójkąta. Jako taki, jeśli użyjemy wariancji (tutaj wykonanej przy użyciu stdodchylenia standardowego, pierwiastka kwadratowego wariancji) do ustalenia prawdopodobnego rozkładu, musimy jedynie zrobić więcej, aby odróżnić gamma od jednolitej; w tym celu szukamy wartości większej niż 1 (używając any(k.>1)) - to powiedziawszy, sprawdzamy zarówno wykładniczy, jak i gamma, ponieważ poprawia to ogólną wydajność.

Aby zapisać bajt, indeksowanie ciągu "EGTBU"odbywa się zamiast bezpośredniej oceny ciągu w ramach warunków warunkowych.

W celu przetestowania zapisz pliki txt w katalogu (zachowując nazwy bez zmian) i uruchom Julia REPL w tym katalogu. Następnie dołącz funkcję do nazwy jako

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

i użyj następującego kodu, aby zautomatyzować testowanie (to przeczyta z pliku, skonwertuje na tablicę tablic, użyje funkcji i wyświetli dane dla każdego niedopasowania):

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)

Dane wyjściowe będą składać się z wierszy zawierających przypadek niedopasowania, prawidłowego rozkładu -> określonego rozkładu i obliczonej wariancji (np. 13 G->E 0.35008999281668357Oznacza, że ​​13 wiersz w G.txt, który powinien być rozkładem gamma, jest określony jako wykładniczy rozkład, przy odchyleniu standardowym wynoszącym 0,35008999 ...)

Po każdym pliku wyświetla również liczbę niezgodności dla tego pliku, a następnie na końcu wyświetla również całkowitą niezgodność (i powinien odczytać 2, jeśli działa jak wyżej). Nawiasem mówiąc, powinien mieć 1 niezgodność dla G.txt i 1 niezgodność dla U.txt

R, 202 192 184 182 162 162 154 bajty + 0 błędów

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

Jest to oparte na formule bayesowskiej P (D = d | X = x) = P (X = x | D = d) * P (D = d) / P (X = x), gdzie D jest rozkładem, a X jest losową próbką. Wybieramy d tak, że P (D = d | X = x) jest największe z 5.

Zakładam, że wcześniejszy (tj. P (D = di) = 1/5 dla i w [1,5]), co oznacza, że ​​P (D = d) w liczniku jest taki sam we wszystkich przypadkach (a mianownik miałby tak czy inaczej we wszystkich przypadkach), więc możemy odstawić wszystko poza P (x = X | D = d), które (z wyjątkiem rozkładu trójkątnego) upraszczają funkcje natywne w R.

bez golfa:

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

Zauważ, że wersja bez golfa nie jest dokładnie równoważna z wersją z golfem, ponieważ pozbycie się mianownika pozwala uniknąć przypadku Inf / Inf, który występuje, jeśli pozwolisz, aby rozkład beta był w zamkniętym przedziale [0,1] zamiast (0, 1) - podobnie jak przykładowe dane. Dodatkowa instrukcja if poradziłaby sobie z tym, ale ponieważ jest to wyłącznie w celach ilustracyjnych, prawdopodobnie nie warto dodawać złożoności, która nie jest sednem algorytmu.

Dzięki @Alex A. za dodatkowe redukcje kodu. Specjalnie dla what.max!

CJam, 76

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

Kod źródłowy ma 43 bajty i błędnie klasyfikuje 33 listy.

Weryfikacja

$ 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

Pomysł

Odróżnienie rozkładu wykładniczego i gamma od pozostałych jest łatwe, ponieważ są to jedyne rozkłady, które przyjmują wartości większe niż 1 .

Aby wybrać między gamma , wykładniczym i innymi, przyjrzymy się drugiej najwyższej wartości próbki.

• Jeśli leży w [1,5, ∞) , domyślamy się gamma .

• Jeśli leży w [1, 1.5) , domyślamy się wykładniczego .

• Jeśli leży w [0, 1) , mamy trzy pozostałe możliwości.

  Pozostałe rozkłady można różnicować poprzez procent wartości próbek, które leżą blisko średniej ( 0,5 ).

  Długość próbki dzielimy przez liczbę wchodzących wartości (0,3, 0,7) i sprawdzamy wynikowy iloraz.

  • Jeśli to leży (1, 2) , domyślamy się trójkątny .

  • Jeśli to leży (2, 3) , domyślamy się munduru .

  • Jeśli leży w (3, ∞) , domyślamy się wersji beta .

Kod

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.

Matlab, 428 328 bajtów + 33 błędnie sklasyfikowany

Ten program w zasadzie porównuje rzeczywisty CDF z oszacowanym, biorąc pod uwagę dane, a następnie oblicza średnią odległość między nimi: Myślę, że obraz wyjaśnia więcej:

Dane pokazane na tym obrazku pokazują dość wyraźnie, że należy on do rozkładu turkusowego, ponieważ jest dość zbliżony do tego, więc w zasadzie to robi mój program. Prawdopodobnie można go nieco pograć w golfa. Dla mnie było to przede wszystkim wyzwanie koncepcyjne, niezbyt golfowe.

Podejście to jest również niezależne od wybranych plików pdf, działałoby dla każdego zestawu dystrybucji.

Poniższy (nie golfowy) kod powinien pokazywać, jak to się robi. Wersja do gry w golfa jest poniżej.

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

Wersja w pełni golfa:

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)

Perl, 119 bajtów + 8 błędnych klasyfikacji = 127

Podjąłem małe drzewo decyzyjne dotyczące trzech funkcji:

• $ o: boolean: jeśli jakieś próbki> 1.0
• $ t: liczba: 0-ty minus 6-ty 13-ile obcięty w zakresie 0-1,
• $ h: liczba: 0-ty minus 6-ty plus 12-ty 13-ile przycięty do zakresu 0-1

Wywoływany z perl -F, -lane -e '...'. Nie jestem pewien, czy powinienem dodać karę za niestandardowe parametry. Gdyby przecinki były spacjami, myślę, że mógłbym uciec bez znaku -F,

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

Lekko sformatowane wyjście (bez flagi -l) to:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
    bbbbbbbbbbbbbbbbbbbbbbbubbbbbbbbbbbbbbbbbbbbbbb
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
    eeegeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
gggggggegggggggggggggggggggggggggggggggggggggggggggg
    ggggggggggggggggggggggggggggggggggggggggggggggg
tttttttttttttttttttttttttttttttttttttttttttttttttttt
    ttttttttttttttttttttttttttttuttttttttttttutttttt
uuuuuuuuuuuuuuuuuuuuuuuuuuutuuuuuuuuuuuuuuuubuuuuuuu
    uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuutuuuu

Python, 318 bajtów + 35 błędnych klasyfikacji

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)

Pomysł: rozkład zgaduje się na podstawie wartości p testu Kołmogorowa-Smirnowa.

Test

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