Quem é essa distribuição de probabilidade?

16

Introdução

Neste desafio, você recebe uma lista de números de pontos flutuantes não negativos, desenhados independentemente de alguma distribuição de probabilidade. Sua tarefa é inferir essa distribuição a partir dos números. Para viabilizar o desafio, você tem apenas cinco distribuições para escolher.

Observe que todas as distribuições acima têm média exatamente 1/2.

A tarefa

Sua entrada é uma matriz de números de ponto flutuante não negativo, com comprimento entre 75 e 100 inclusive. Sua saída deve ser uma das letras UTBEG, com base em qual das distribuições acima você acha que os números são sorteados.

Regras e Pontuação

Você pode dar um programa completo ou uma função. As brechas padrão não são permitidas.

Em este repositório , há cinco arquivos de texto, uma para cada distribuição, cada um exatamente 100 linhas longas. Cada linha contém uma lista delimitada por vírgula de 75 a 100 carros alegóricos, desenhados independentemente da distribuição e truncados para 7 dígitos após o ponto decimal. Você pode modificar os delimitadores para corresponder ao formato de matriz nativa do seu idioma. Para se qualificar como resposta, seu programa deve classificar corretamente pelo menos 50 listas de cada arquivo . A pontuação de uma resposta válida é contagem de bytes + número total de listas classificadas incorretamente . A pontuação mais baixa vence.

Zgarb
fonte
Eu provavelmente deveria ter perguntado antes, mas qual a otimização para os casos de teste é esperada? Estou em um ponto em que posso melhorar minha pontuação ajustando alguns parâmetros, mas o impacto na pontuação provavelmente dependerá dos casos de teste fornecidos.
Dennis3
2
@ Dennis Você pode otimizar o quanto quiser, os casos de teste são uma parte fixa do desafio.
Zgarb 3/11
YU NÃO Distribuição Student-t? = (
N3buchadnezzar

Respostas:

6

Julia, 60 62 bytes + 25 2 erros = 82 64

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

Isto é bastante simples. A variação para as distribuições é principalmente diferente - é 1/4 para exponencial, 1/8 para beta, 1/12 para gama e uniforme e 1/24 para triangular. Como tal, se usarmos variação (aqui feita usandostd o desvio padrão, a raiz quadrada da variação) para determinar a distribuição provável, precisamos apenas fazer mais para distinguir gama de uniforme; para isso, procuramos um valor maior que 1 (usando any(k.>1)) - ou seja, fazemos a verificação tanto exponencial quanto gama, pois isso melhora o desempenho geral.

Para salvar um byte, a indexação da sequência "EGTBU"é feita em vez de a avaliação direta de uma sequência dentro dos condicionais.

Para testar, salve os arquivos txt em um diretório (mantendo os nomes como estão) e execute o Julia REPL nesse diretório. Em seguida, anexe a função a um nome como

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

e use o código a seguir para automatizar o teste (isso será lido no arquivo, convertido em uma matriz de matrizes, use a função e a saída para cada incompatibilidade):

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)

A saída consistirá em linhas contendo o caso que não corresponde, a distribuição correta -> a distribuição determinada e a variação calculada (por exemplo, 13 G->E 0.35008999281668357 significa que a 13ª linha em G.txt, que deve ser uma distribuição gama, é determinada como exponencial distribuição, com o desvio padrão de 0,35008999 ...)

Depois de cada arquivo, ele também gera o número de incompatibilidades para esse arquivo e, no final, também exibe o total de incompatibilidades (e deve ler 2 se executado como acima). Aliás, ele deve ter 1 incompatibilidade para G.txt e 1 incompatibilidade para U.txt

Glen O
fonte
7

R, 202 192 184 182 182 162 154 bytes + 0 erros

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

Isso é baseado na fórmula bayesiana P (D = d | X = x) = P (X = x | D = d) * P (D = d) / P (X = x), onde D é a distribuição e X é a amostra aleatória. Escolhemos d de modo que P (D = d | X = x) seja o maior dos 5.

Suponho que um plano anterior (ie P (D = di) = 1/5 para i em [1,5]), o que significa que P (D = d) no numerador seja o mesmo em todos os casos (e o denominador seria seja o mesmo em todos os casos, de qualquer maneira), para que possamos jogar fora tudo, exceto P (x = X | D = d), que (exceto a distribuição triangular) simplifica as funções nativas em 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))]
}

Observe que a versão sem golf não é exatamente equivalente à versão com golf, porque se livrar do denominador evita o caso de Inf / Inf, que ocorre se você permitir que a distribuição beta ultrapasse o intervalo fechado [0,1] em vez de (0, 1) - como fazem os dados da amostra. Uma instrução if adicional lidaria com isso, mas como é apenas para fins ilustrativos, provavelmente não vale a pena adicionar a complexidade que não está no coração do algoritmo.

Obrigado @Alex A. pelas reduções adicionais de código. Especialmente para qual.max!

njnnja
fonte
11
Você pode obter isso em 190 bytes, removendo a quebra de linha após a abertura {e a antes do fechamento }e o alias prod, por exemplo P=prod, executando P(dunif(x)), etc. A função não precisa de um nome para ser um envio válido, para que você possa remover p=. Além disso, excelente trabalho. :)
Alex A.
2
Você pode obtê-lo em 182 usando as sugestões acima e usando which.max(c(u,r,b,e,g))no lugar de 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.
Como você ousa usar R para um desafio envolvendo estatísticas!
flawr
6

CJam, 76

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

O código-fonte tem 43 bytes e classifica incorretamente 33 listas.

Verificação

$ 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

Idéia

É fácil diferenciar a distribuição exponencial e gama das demais, pois são as únicas distribuições que assumem valores maiores que 1 .

Para decidir entre gama , exponencial e outras, vamos dar uma olhada no segundo valor mais alto da amostra.

  • Se estiver em [1.5, ∞) , supomos gama .

  • Se estiver em [1, 1.5) , supomos exponencial .

  • Se estiver em [0, 1) , temos três possibilidades restantes.

    As demais distribuições podem ser diferenciadas pela porcentagem de valores amostrais próximos da média ( 0,5 ).

    Dividimos o comprimento da amostra pela contagem de valores que se enquadram em (0,3; 0,7) e examinamos o quociente resultante.

    • Se estiver em (1, 2] , supomos triangular .

    • Se estiver em (2, 3] , achamos uniforme .

    • Se estiver em (3, ∞) , supomos beta .

Código

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

Matlab, 428 328 bytes + 33 classificados incorretamente

Este programa está basicamente comparando o CDF real com um estimado, considerando os dados, e calculando a distância média entre os dois: acho que a imagem explica mais:

insira a descrição da imagem aqui

Os dados mostrados nesta imagem aqui mostram claramente que pertencem à distribuição turquesa, pois é muito próxima dessa, portanto é basicamente o que meu programa está fazendo. Provavelmente pode ser jogado um pouco mais. Para mim, esse foi, antes de tudo, um desafio conceitual, não muito disputado.

Essa abordagem também é independente dos pdfs escolhidos, funcionaria para qualquer conjunto de distribuições.

O código a seguir (não protegido) deve mostrar como isso é feito. A versão golfada está abaixo.

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

Versão totalmente golfe:

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)
flawr
fonte
2

Perl, 119 bytes + 8 classificações incorretas = 127

Fiz uma pequena árvore de decisão em três recursos:

  • $ o: boolean: se houver amostras> 1.0
  • $ t: count: 0-th menos 6-th 13-ile recortado no intervalo 0-1,
  • $ h: count: 0-th menos 6-th mais 12-th 13-ile recortados no intervalo 0-1

Invocado com perl -F, -lane -e '...'. Não tenho certeza se devo adicionar uma penalidade para os parâmetros não padrão. Se as vírgulas fossem espaços, acho que poderia ter escapado sem o -F,

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

A saída ligeiramente formatada (sem o sinalizador -l) é:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
    bbbbbbbbbbbbbbbbbbbbbbbubbbbbbbbbbbbbbbbbbbbbbb
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
    eeegeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
gggggggegggggggggggggggggggggggggggggggggggggggggggggggggg
    gggggggggggggggggggggggggggggggggggggggggggggggggggggg
tttttttttttttttttttttttttttttttttttttttttttttttttttt
    ttttttttttttttttttttttttttttuttttttttttttututttttt
uuuuuuuuuuuuuuuuuuuuuuuuuutuuuuuuuuuuuuuuubuuuuuuu
    uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuutuuuu
Dale Johnson
fonte
0

Python, 318 bytes + 35 classificações incorretas

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)

Idéia: a distribuição é calculada com base no valor-p do teste de Kolmogorov-Smirnov.

Teste

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
fonte