Calculando la entropía

13

Entrada

Una matriz Mrepresentada como dos líneas enteras separadas por espacios. Cada línea tendrá el mismo número de números enteros y cada entero será o bien -1 o 1. El número de números enteros por línea será como máximo 20. Mpor lo tanto ser 2por ndonde nes el número de enteros en cada una de las dos líneas.

Su código debe ser un programa completo. y acepte la entrada de forma estándar en o desde un archivo (esa es su elección). Puede aceptar entradas de entrada estándar, de un archivo o simplemente como parámetro. Sin embargo, si hace lo último, proporcione un ejemplo explícito de cómo debería funcionar su código y recuerde que debe ser un programa completo y cómo Mse representará la matriz en la entrada. En otras palabras, es probable que tengas que analizar un poco.

Salida

La entropía binaria de Shannon de la distribución de M*xdonde los elementos de xse eligen de manera uniforme e independiente de {-1,1}. xes un nvector de columna dimensional.

La entropía de una distribución de probabilidad discreta es

- sum p_i log_2(p_i)

En este caso, p_ies la probabilidad del ith único posible M*x.

Ejemplo y sugerencias útiles

Como ejemplo trabajado, deje que la matriz Msea

-1 1
-1 -1

Ahora mira todos los 2^2diferentes vectores posibles x. Para cada uno calculamos M*xy colocamos todos los resultados en una matriz (una matriz de 4 elementos de vectores de 2 componentes). Aunque para cada uno de los 4 vectores la probabilidad de que ocurra es 1/2^2 = 1/4, solo nos interesa la cantidad de veces que ocurre cada vector resultante únicoM*x , por lo que resumimos las probabilidades individuales de las configuraciones que conducen a los mismos vectores únicos. En otras palabras, los posibles M*xvectores únicos describen los resultados de la distribución que estamos investigando, y tenemos que determinar la probabilidad de cada uno de estos resultados (que, por construcción, siempre será un múltiplo entero de 1/2^2, o 1/2^nen general) para Calcule la entropía.

En el ncaso general , dependiendo de Mlos posibles resultados de M*xpuede variar de "todos diferentes" (en este caso tenemos nvalores de iin p_i, y cada uno p_ies igual a 1/2^n), a "todos iguales" (en este caso hay un único posible resultado, y p_1 = 1).

Específicamente, para la 2x2matriz anterior , Mpodemos encontrar multiplicándola con las cuatro configuraciones posibles ( [+-1; +-1]), que cada vector resultante es diferente. Entonces, en este caso hay cuatro resultados, y en consecuencia p_1 = p_2 = p_3 = p_4 = 1/2^2 = 1/4. Recordando que log_2(1/4) = -2tenemos:

- sum p_i log_2(p_i) = -(4*(-2)/4) = 2

Entonces el resultado final para esta matriz es 2.

Casos de prueba

Entrada:

-1 -1 
-1 -1

Salida:

1.5

Entrada:

-1 -1 -1 -1
-1 -1 -1 -1

Salida:

2.03063906223

Entrada:

-1  -1  -1  1
1  -1  -1  -1

Salida:

3
dorothy
fuente
77
1. ¿Cuáles son las dimensiones de x? 2. En aras de hacer que la pregunta sea autónoma, ¿cómo se Mxdefine la entropía binaria de Shannon ?
Peter Taylor
44
El comentario de @ Peter explica exactamente los votos negativos. Leí el artículo sobre entropía, y no puedo saber de inmediato qué implementar. Debe especificar exactamente cuál es la fórmula / algoritmo para calcular la entropía de Shannon.
Lynn
55
Las preguntas deben ser independientes, de todos modos; es poco probable que Wikipedia se desconecte repentinamente, pero sería ideal no tener que hacer clic en otra página para poder comprender la especificación completa del desafío.
Pomo de la puerta
2
Por defecto, las funciones son alternativas válidas a los programas. Se le permite anular eso, pero hará que algunos idiomas sean muy tristes porque se necesita mucho repetitivo para tomar el archivo o la entrada estándar. En términos más generales, recomiendo no tener un formato de entrada tan restrictivo en un desafío matemático. Permitir el tipo de lista natural del idioma hará que las personas estén más felices de participar.
xnor
3
@dorothy nota que no es que "log_2 (0) es 0 por conveniencia", sino más bien "lim_ {p-> 0} p * log (p) == 0". Entonces "log_2 (0)" sigue siendo -inf.
Andras Deak

Respuestas:

3

Mathematica, 48 68 bytes

Editar: se agrega preproceso para aceptar cadenas como parámetro.

Con la ayuda de Tuplesy Entropy, la implementación es concisa y legible.

Entropy[2,{-1,1}~Tuples~Length@#.#]&@Thread@ImportString[#,"Table"]&

donde Tuples[{-1,1},n]da todas las ntuplas posibles {-1,1}y Entropy[2,list]da la entropía de información de base 2.

Una de las cosas interesantes es que Mathematica realmente devolverá una expresión precisa:

%["-1 -1 \n -1 -1"]
(* 3/2 *)

Se puede lograr un resultado aproximado con un .agregado adicional ( Entropy[2., ...).

njpipeorgan
fuente
Mathematica es ridículo :) Sin embargo, su respuesta no se ajusta a la especificación. La entrada está separada por espacios, por lo que se necesitará algún análisis. Ver la última actualización.
dorothy
3

Perl, 160 159 141 bytes

incluye +1 para la -pactualización desde 141 bytes

@y=(@z=/\S+/g)x 2**@z;@{$.}=map{evals/.1/"+".$&*pop@y/egr}glob"{-1,+1}"x@z}{$H{$_.$2[$i++]}++for@1;$\-=$_*log($_/=1<<@z)/log 2 for values%H;

La entrada se espera STDINcomo 2 líneas que consisten en espacios separados 1o -1.
Corre como perl -p 140.pl < inputfile.

No ganará ningún premio, pero pensé en compartir mi esfuerzo.
Explicado:

    @y=                             # @y is (@z) x (1<<$n)
       (@z = /\S+/g)                # construct a matrix row from non-WS
       x 2**@z;                     # repeat @z 2^$n times
    @{$.} = map {                   # $.=$INPUT_LINE_NUMBER: set @1 or @2
      eval s/.1/"+".$&*pop@y/egr    # multiply matrix row with vector
    } glob "{-1,+1}" x @z           # produce all possible vectors

}{                                  # `-p` trick: end `while(<>)`, reset `$_`

$H{ $_ . $2[$i++] }++               # count unique M*x columns
    for @1;

$\ -= $_ * log($_/=1<<@z) / log 2   # sum entropy distribution
        for values %H;

DATOS

  • Actualización 159: guarde 1 eliminando ()mediante el uso en **lugar de <<.
  • actualización 141: ahorre 18 utilizando $.y -p.
Kenney
fuente
1
¡Gracias! No tenemos suficientes respuestas perl en ppcg imho
dorothy
@dorothy Es porque los golfistas de código detestan a Perl, en su mayor parte.
Addison Crump
@FlagAsSpam Pero, pero ... Perl es incomprensible, sucinto y casi loco. ¿Cómo podría ser más adecuado para el código de golf?
dorothy
@dorothy ¯ \ _ (ツ) _ / ¯ Lo evitamos como la peste. No sé por qué, de verdad.
Addison Crump
2

Pyth, 37 bytes

K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8

Banco de pruebas

Esto es algo más complicado cuando tiene que implementar manualmente la multiplicación de matrices.

Explicación:

K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8
       JrR7.z                            Parse input into matrix, assign to J.
  _B1                                    [1, -1]
K^   lhJ                                 All +-1 vectors of length n, assign to K.
                           m       K     Map over K
                            m     J      Map over the rows of J
                             s*Vdk       Sum of vector product of vector and row.
                          S              Sort
                         r          8    Run length encode.
                       hM                Take just occurrence counts.
                   cRlK                  Divide by len(K) to get probabilities.
               *Lld                      Multiply each probabiliity by its log.
              s                          Sum.
             _                           Negate. Print implicitly.
isaacg
fuente
¡Guauu! :) Esto parece mucho trabajo. ¿Dónde están las personas cjam .....?
dorothy
1

MATLAB, 196 194 187 184 126 154 bytes

(Los 28 bytes adicionales de 126 a 154 se deben al análisis de entrada: ahora el código acepta la entrada como dos líneas de números separados por espacios en blanco).

f=@()str2num(input('','s'));M=[f();f()];n=size(M,2);x=(dec2bin(0:n^2-1,n)-48.5)*2*M';[~,~,c]=unique(x,'rows');p=accumarray(c,1)/2^n;disp(-sum(p.*log2(p)))

Versión sin golf:

f=@()str2num(input('','s'));        % shorthand for "read a line as vector"
M=[f();f()];                        % read matrix
n=size(M,2);                        % get lenght of vectors

x=(dec2bin(0:n^2-1,n)-48.5)*2*M';   % generate every configuration
                                    %    using binary encoding
[~,~,c]=unique(x,'rows');           % get unique rows of (Mx)^T
p=accumarray(c,1)/2^n;              % count multiplicities and normalize
disp(-sum(p.*log2(p)))              % use definition of entropy

Podría eliminar 6 bytes si ans = ...se permitiera un " " tipo de salida, nunca estoy seguro de esto.

Lamento decir que mi solución original y seguramente ingeniosa era demasiado descabellada en comparación con mi solución actual. Esta es también la primera vez que estoy usando accumarray. Sin embargo, una aplicación de seis parámetros de entrada todavía tiene que esperar :)

Salidas (siguientes format long):

[-1 1
-1 -1]
     2

[-1 -1
-1 -1]
   1.500000000000000

[-1 -1 -1 -1
-1 -1 -1 -1]
   2.030639062229566

[-1  -1  -1  1
1  -1  -1  -1]
     3

Salidas con el valor predeterminado format short g:

[-1 1
-1 -1]
     2

[-1 -1
-1 -1]
          1.5

[-1 -1 -1 -1
-1 -1 -1 -1]
       2.0306

[-1  -1  -1  1
1  -1  -1  -1]
     3
Andras Deak
fuente