¿Quién es esa distribución de probabilidad?

16

Introducción

En este desafío, se le proporciona una lista de números de punto flotante no negativos extraídos independientemente de alguna distribución de probabilidad. Su tarea es inferir esa distribución de los números. Para que el desafío sea factible, solo tiene cinco distribuciones para elegir.

Tenga en cuenta que todas las distribuciones anteriores tienen una media exacta de 1/2.

La tarea

Su entrada es una matriz de números de punto flotante no negativos, de longitud entre 75 y 100 inclusive. Su salida será una de las letras UTBEG, en función de cuál de las distribuciones anteriores se adivinan los números.

Reglas y puntuación

Puede dar un programa completo o una función. Las lagunas estándar no están permitidas.

En este repositorio , hay cinco archivos de texto, uno para cada distribución, cada uno de exactamente 100 líneas de largo. Cada línea contiene una lista delimitada por comas de 75 a 100 flotadores dibujados independientemente de la distribución y truncados a 7 dígitos después del punto decimal. Puede modificar los delimitadores para que coincidan con el formato de matriz nativo de su idioma. Para calificar como respuesta, su programa debe clasificar correctamente al menos 50 listas de cada archivo . La puntuación de una respuesta válida es el recuento de bytes + el número total de listas mal clasificadas . El puntaje más bajo gana.

Zgarb
fuente
Probablemente debería haber preguntado antes, pero ¿cuánta optimización se espera para los casos de prueba? Estoy en un punto en el que puedo mejorar mi puntaje ajustando algunos parámetros, pero el impacto en el puntaje probablemente dependerá de los casos de prueba dados.
Dennis
2
@Dennis Puede optimizar todo lo que quiera, los casos de prueba son una parte fija del desafío.
Zgarb
YU NO Distribución de Student-t? = (
N3buchadnezzar

Respuestas:

6

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

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

Esto es bastante simple. La varianza para las distribuciones es en su mayoría diferente: es 1/4 para exponencial, 1/8 para beta, 1/12 para gamma y uniforme, y 1/24 para triangular. Como tal, si usamos la varianza (aquí se usa stdpara la desviación estándar, la raíz cuadrada de la varianza) para determinar la distribución probable, solo tenemos que hacer más para distinguir gamma de uniforme; para eso, buscamos un valor mayor que 1 (usando any(k.>1)); dicho esto, verificamos tanto exponencial como gamma, ya que mejora el rendimiento general.

Para guardar un byte, se indexa la cadena en "EGTBU"lugar de evaluar directamente una cadena dentro de los condicionales.

Para la prueba, guarde los archivos txt en un directorio (manteniendo los nombres tal como están) y ejecute Julia REPL en ese directorio. Luego, adjunte la función a un nombre como

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

y use el siguiente código para automatizar las pruebas (esto se leerá del archivo, se convertirá en una matriz de matrices, usará la función y la salida para cada falta de coincidencia):

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)

La salida consistirá en filas que contienen el caso que no coincide, la distribución correcta -> la distribución determinada y la varianza calculada (por ejemplo, 13 G->E 0.35008999281668357significa que la 13ª fila en G.txt, que debería ser una distribución gamma, se determina como exponencial distribución, con una desviación estándar de 0.35008999 ...)

Después de cada archivo, también muestra el número de discrepancias para ese archivo, y luego al final también muestra las discrepancias totales (y debería leer 2 si se ejecuta como se indica arriba). Por cierto, debe tener 1 falta de coincidencia para G.txt y 1 falta de coincidencia para U.txt

Glen O
fuente
7

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

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

Esto se basa en la fórmula bayesiana P (D = d | X = x) = P (X = x | D = d) * P (D = d) / P (X = x), donde D es la distribución y X es la muestra aleatoria Escogemos la d tal que P (D = d | X = x) es la mayor de las 5.

Supongo que un anterior plano (es decir, P (D = di) = 1/5 para i en [1,5]), lo que significa que P (D = d) en el numerador es el mismo en todos los casos (y el denominador sería ser el mismo en todos los casos de todos modos), por lo que podemos golf todo menos P (x = X | D = d), que (excepto la distribución triangular) se simplifica a funciones nativas en R.

sin golf:

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

Tenga en cuenta que la versión no golfizada no es exactamente equivalente a la versión golfizada porque al deshacerse del denominador se evita el caso de Inf / Inf que ocurre si permite que la distribución beta esté sobre el intervalo cerrado [0,1] en lugar de (0, 1) - como lo hacen los datos de muestra. Una declaración if adicional manejaría eso, pero dado que es solo para fines ilustrativos, probablemente no valga la pena agregar la complejidad que no está en el corazón del algoritmo.

Gracias @Alex A. por reducciones de código adicionales. Especialmente para cual.max!

njnnja
fuente
1
Puede llevar esto a 190 bytes eliminando el salto de línea después de la apertura {y el anterior al cierre }, y alias prod, por ejemplo P=prod, luego haciendo P(dunif(x)), etc. La función no necesita un nombre para ser un envío válido, por lo que puede eliminar p=. Además, excelente trabajo. :)
Alex A.
2
Puede llegar a 182 utilizando las sugerencias anteriores y which.max(c(u,r,b,e,g))en 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.
¿Cómo te atreves a usar R para un desafío que involucra estadísticas?
falla
6

CJam, 76

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

El código fuente tiene 43 bytes de largo y clasifica erróneamente 33 listas.

Verificación

$ 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

Idea

Es fácil diferenciar la distribución exponencial y gamma de las restantes, ya que son las únicas distribuciones que toman valores mayores que 1 .

Para decidir entre gamma , exponencial y otros, observamos el segundo valor más alto de la muestra.

  • Si se encuentra en [1.5, ∞) , suponemos gamma .

  • Si se encuentra en [1, 1.5) , suponemos exponencial .

  • Si se encuentra en [0, 1) , tenemos tres posibilidades restantes.

    Las distribuciones restantes se pueden diferenciar por el porcentaje de valores de muestra que se encuentran cerca de la media ( 0.5 ).

    Dividimos la longitud de la muestra por el recuento de valores que se encuentran en (0.3, 0.7) y observamos el cociente resultante.

    • Si se encuentra en (1, 2] , suponemos triangular .

    • Si se encuentra en (2, 3] , suponemos uniforme .

    • Si se encuentra en (3, ∞) , suponemos 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
fuente
3

Matlab, 428328 bytes + 33 mal clasificados

Este programa básicamente compara el CDF real con uno estimado dados los datos, y luego calcula la distancia media entre esos dos: creo que la imagen explica más:

ingrese la descripción de la imagen aquí

Los datos que se muestran en esta imagen aquí muestran con bastante claridad que pertenece a la distribución turquesa, ya que está bastante cerca de esa, así que eso es básicamente lo que está haciendo mi programa. Probablemente se pueda jugar un poco más. Para mí eso fue ante todo un desafío conceptual, no muy golfista.

Este enfoque también es independiente de los archivos PDF elegidos, funcionaría para cualquier conjunto de distribuciones.

El siguiente código (no protegido) debería mostrar cómo se hace. La versión de golf está abajo.

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ón totalmente golfizada:

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)
falla
fuente
2

Perl, 119 bytes + 8 clasificaciones erróneas = 127

Hice un pequeño árbol de decisiones sobre tres características:

  • $ o: boolean: si hay muestras> 1.0
  • $ t: cuenta: 0-ésima menos 6-ésima 13-ile recortada en el rango 0-1,
  • $ h: cuenta: 0-ésima menos 6-ésima más 12-ésima 13-ile recortada en el rango 0-1

Invocado con perl -F, -lane -e '...'. No estoy seguro de si debo agregar una penalización por los parámetros no estándar. Si las comas fueran espacios, supongo que podría haber escapado sin -F,

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

La salida ligeramente formateada (sin el indicador -l) es:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
    bbbbbbbbbbbbbbbbbbbbbbbbubbbbbbbbbbbbbbbbbbbbbbb
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
    eeegeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
gggggggegggggggggggggggggggggggggggggggggggggggggggg
    gggggggggggggggggggggggggggggggggggggggggggggggg
tttttttttttttttttttttttttttttttttttttttttttttttttttt
    ttttttttttttttttttttttttttttuttttttttttttutttttt
uuuuuuuuuuuuuuuuuuuuuuuuuuutuuuuuuuuuuuuuuuubuuuuuuu
    uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuutuuuu
Dale Johnson
fuente
0

Python, 318 bytes + 35 clasificaciones erróneas

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)

Idea: la distribución se adivina en función del valor p de la prueba de Kolmogorov-Smirnov.

Prueba

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
fuente