Obliczanie entropii

13

Wejście

Macierz Mreprezentowana jako dwie oddzielone spacjami linie liczb całkowitych. Każda linia będzie miała tę samą liczbę liczb całkowitych, a każda liczba całkowita będzie wynosić -1 lub 1. Liczba liczb całkowitych w wierszu będzie wynosić co najwyżej 20. Mbędzie zatem 2, ngdzie njest liczba liczb całkowitych w każdej z dwóch linii.

Twój kod powinien być kompletnym programem. i zaakceptuj dane wejściowe w standardowym pliku lub z pliku (to twój wybór). Możesz zaakceptować dane wejściowe ze standardowego wejścia, pliku lub po prostu jako parametr. Jeśli jednak zrobisz to drugie, podaj wyraźny przykład działania kodu i pamiętaj, że musi to być kompletny program i jak macierz Mbędzie reprezentowana na wejściu. Innymi słowy, prawdopodobnie będziesz musiał parsować.

Wynik

Binarny Shannon entropia rozkładu M*x, gdzie elementy xsą równomiernie i są niezależnie wybrane z {-1,1}. xto nwymiarowy wektor kolumny.

Entropia dyskretnego rozkładu prawdopodobieństwa jest

- sum p_i log_2(p_i)

W tym przypadku p_iprawdopodobieństwo itego unikalnego jest możliwe M*x.

Przykład i pomocne wskazówki

Jako sprawdzony przykład niech Mbędzie macierz

-1 1
-1 -1

Teraz spójrz na wszystkie 2^2możliwe wektory x. Dla każdego obliczamy M*xi umieszczamy wszystkie wyniki w tablicy (4-elementowa tablica 2-komponentowych wektorów). Chociaż dla każdego z 4 wektorów istnieje prawdopodobieństwo jego wystąpienia 1/2^2 = 1/4, interesuje nas tylko liczba przypadków, w których wystąpi każdy unikalny wektor wynikowy M*x, dlatego podsumowujemy indywidualne prawdopodobieństwa konfiguracji prowadzących do tych samych unikalnych wektorów. Innymi słowy, możliwe unikalne M*xwektory opisują wyniki rozkładu, który badamy, i musimy określić prawdopodobieństwo każdego z tych wyników (które z założenia zawsze będą całkowitą wielokrotnością 1/2^2lub 1/2^nogólnie) do obliczyć entropię.

W ogólnym nprzypadku, w zależności od Mmożliwych wyników M*xmoże wahać się od „wszystkie różne” (w tym przypadku mamy nwartości iin p_i, i każda p_ijest równa 1/2^n), do „wszystkie takie same” (w tym przypadku jest jedna możliwa wynik i p_1 = 1).

W szczególności dla powyższej 2x2macierzy Mmożemy przekonać się, mnożąc ją przez cztery możliwe konfiguracje ( [+-1; +-1]), że każdy powstały wektor jest inny. Zatem w tym przypadku są cztery wyniki, a w konsekwencji p_1 = p_2 = p_3 = p_4 = 1/2^2 = 1/4. Przypominając, że log_2(1/4) = -2mamy:

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

Zatem końcowy wynik dla tej macierzy wynosi 2.

Przypadki testowe

Wejście:

-1 -1 
-1 -1

Wynik:

1.5

Wejście:

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

Wynik:

2.03063906223

Wejście:

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

Wynik:

3
Dorota
źródło
7
1. Jakie są wymiary x? 2. W jaki sposób Mxdefiniuje się binarną entropię Shannona w celu uczynienia pytania samodzielnym ?
Peter Taylor,
4
Komentarz Petera dokładnie wyjaśnia opinie negatywne. Przejrzałem artykuł o entropii i nie mogę od razu dowiedzieć się, co wdrożyć. Należy dokładnie określić, jaka jest formuła / algorytm obliczania entropii Shannona.
Lynn
5
W każdym razie pytania powinny być samodzielne; jest mało prawdopodobne, że Wikipedia nagle przejdzie w tryb offline, ale byłoby idealnie, gdyby nie trzeba było przechodzić do innej strony, aby zrozumieć pełną specyfikację wyzwania.
Klamka
2
Domyślnie funkcje są prawidłową alternatywą dla programów. Możesz to unieważnić, ale spowoduje to, że niektóre języki będą bardzo smutne, ponieważ pobieranie plików lub standardowe wejście wymaga dużej ilości płyt. Mówiąc bardziej ogólnie, odradzam stosowanie tak restrykcyjnego formatu wejściowego w przypadku zadania matematycznego. Dopuszczenie naturalnego typu listy języka uszczęśliwiłoby ludzi.
xnor
3
@ Dorota zauważa, że ​​nie chodzi o to, że „log_2 (0) to 0 dla wygody”, ale raczej „lim_ {p-> 0} p * log (p) == 0”. Zatem „log_2 (0)” jest nadal -inf.
Andras Deak,

Odpowiedzi:

3

Mathematica, 48 68 bajtów

Edycja: Dodano proces wstępny do akceptowania ciągu jako parametru.

Przy pomocy Tuplesi Entropywdrożenie jest zarówno zwięzłe, jak i czytelne.

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

gdzie Tuples[{-1,1},n]daje wszystkie możliwe nliczby z {-1,1}i Entropy[2,list]daje entropię informacji base-2.

Jedną z fajnych rzeczy jest to, że Mathematica faktycznie zwróci dokładne wyrażenie:

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

Przybliżony wynik można uzyskać za pomocą dodatkowego .dodanego ( Entropy[2., ...).

njpipeorgan
źródło
Mathematica jest śmieszna :) Jednak twoja odpowiedź nie pasuje do specyfikacji. Dane wejściowe są oddzielone spacją, więc konieczne będzie przeprowadzenie analizy. Zobacz najnowszą aktualizację.
dorota
3

Perl, 160 159 141 bajtów

zawiera +1 dla -paktualizacji od 141 bajtów

@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;

Dane wejściowe są oczekiwane STDINjako 2 linie składające się z oddzielonych spacjami 1lub -1.
Uruchom jako perl -p 140.pl < inputfile.

Nie wygra żadnych nagród, ale pomyślałem, że podzielę się swoim wysiłkiem.
Wyjaśniono:

    @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;

DANE

  • aktualizacja 159: zapisz 1, eliminując (), używając **zamiast <<.
  • aktualizacja 141: zapisz 18, używając $.i -p.
Kenney
źródło
1
Dziękuję Ci! Nie mamy wystarczającej liczby perlowych odpowiedzi na ppcg imho
dorothy
@dorothy To dlatego , że w większości golfiści nie znoszą Perla.
Addison Crump
@FlagAsSpam Ale ... ale perl jest niezrozumiały, zwięzły i szalony. Jak może być bardziej odpowiedni do gry w golfa?
dorothy
@dorothy ¯ \ _ (ツ) _ / ¯ Unikamy tego jak zarazy. Nie wiem dlaczego, naprawdę.
Addison Crump
2

Pyth, 37 bajtów

K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8

Zestaw testowy

Jest to nieco trudniejsze, gdy trzeba ręcznie zaimplementować mnożenie macierzy.

Wyjaśnienie:

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
źródło
Łał! :) To wygląda na dużo pracy. Gdzie są teraz ludzie cjam .....?
dorothy,
1

MATLAB, 196 194 187 184 126 154 bajtów

(Dodatkowe 28 bajtów od 126 do 154 wynika z parsowania danych wejściowych: teraz kod akceptuje dane wejściowe jako dwa wiersze liczb oddzielonych spacjami.)

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

Wersja bez golfa:

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

Mógłbym pozbyć się 6 bajtów, gdyby ans = ...dozwolony był typ wyjściowy, nigdy nie jestem tego pewien.

Z przykrością stwierdzam, że moje oryginalne i na pewno dowcipne rozwiązanie było zdecydowanie zbyt wolne od mojego obecnego rozwiązania. To także pierwszy raz, kiedy używam accumarray. Aplikacja z sześcioma parametrami wejściowymi musi jednak jeszcze poczekać :)

Wyjścia (następujące 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

Dane wyjściowe z wartością domyślną 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
źródło