Pomiar entropii / informacji / wzorów matrycy binarnej 2d

Chcę zmierzyć entropię / gęstość informacji / podobieństwo wzorca dwuwymiarowej macierzy binarnej. Pokażę kilka zdjęć w celu wyjaśnienia:

Ten ekran powinien mieć raczej wysoką entropię:

ZA)

To powinno mieć średnią entropię:

B)

Wreszcie te zdjęcia powinny mieć entropię bliską zeru:

DO)

RE)

MI)

Czy istnieje jakiś indeks, który przechwytuje entropię, odpowiednio. „podobieństwo wzorów” tych wyświetlaczy?

Oczywiście każdy algorytm (np. Algorytmy kompresji lub algorytm rotacji proponowany przez ttnphns ) jest wrażliwy na inne funkcje wyświetlacza. Szukam algorytmu, który próbuje uchwycić następujące właściwości:

• Symetria obrotowa i osiowa
• Ilość klastrów
• Powtórzenia

Być może bardziej skomplikowany, algorytm może być wrażliwy na właściwości psychologicznej „ zasady Gestalt ”, w szczególności:

• Prawo bliskości:
• Prawo symetrii: obrazy symetryczne są postrzegane zbiorowo, nawet pomimo odległości:

Wyświetlaczom o tych właściwościach należy przypisać „niską wartość entropii”; ekranom z raczej losowymi / nieustrukturyzowanymi punktami należy przypisać „wysoką wartość entropii”.

Wiem, że najprawdopodobniej żaden algorytm nie uchwyci wszystkich tych funkcji; dlatego też mile widziane są sugestie dotyczące algorytmów, które dotyczą tylko niektórych, a nawet tylko jednej funkcji.

W szczególności szukam konkretnych, istniejących algorytmów lub konkretnych, możliwych do wdrożenia pomysłów (i przyznam nagrodę zgodnie z tymi kryteriami).

Istnieje prosta procedura obejmująca całą intuicję, w tym elementy psychologiczne i geometryczne. Opiera się na wykorzystaniu bliskości przestrzennej , która jest podstawą naszej percepcji i zapewnia nieodłączny sposób uchwycenia tego, co tylko niedokładnie mierzone jest przez symetrie.

Aby to zrobić, musimy zmierzyć „złożoność” tych tablic w różnych skalach lokalnych. Chociaż mamy dużą swobodę wyboru tych skal i wyboru sposobu, w jaki mierzymy „bliskość”, jest wystarczająco prosty i wystarczająco skuteczny, aby użyć małych kwadratowych dzielnic i spojrzeć na ich średnie (lub równoważnie sumy) w ich obrębie. W tym celu można uzyskać sekwencję tablic z dowolnej tablicy na poprzez utworzenie ruchomych sum sąsiedztwa przy użyciu na sąsiedztwa, następnie na itd., Do do (chociaż do tego czasu zwykle jest za mało wartości, aby zapewnić cokolwiek wiarygodnego).$m$$n$$k=2$$2$$3$$3$$\min(n,m)$$\min(n,m)$

Aby zobaczyć, jak to działa, obliczenia dla tablic w pytaniu, które od do , od góry do dołu. Oto wykresy ruchomych sum dla ( to oczywiście tablica oryginalna) zastosowanych do .$a_1$$a_5$$k=1,2,3,4$$k=1$$a_1$

Zgodnie z ruchem wskazówek zegara od lewego górnego rogu, wynosi , , i . Tablice mają odpowiednio na , następnie na , na i na . Wszystkie wyglądają na „losowe”. Zmierzmy tę losowość za pomocą ich entropii base-2. Dla sekwencja tych entropii wynosi . Nazwijmy to „profilem” .$k$$1$$2$$4$$3$$5$$5$$4$$4$$2$$2$$3$$3$$a_1$$(0.97, 0.99, 0.92, 1.5)$$a_1$

Tutaj natomiast są ruchome sumy :$a_4$

Dla istnieje niewielka zmienność, stąd niska entropia. Profil to . Jego wartości są konsekwentnie niższe niż wartości dla , potwierdzając intuicyjne poczucie, że w występuje silny „wzorzec” .$k=2, 3, 4$$(1.00, 0, 0.99, 0)$$a_1$$a_4$

Potrzebujemy ramy odniesienia do interpretacji tych profili. Idealnie losowa tablica wartości binarnych będzie miała około połowy swoich wartości równych a druga połowa równa , dla entropii . Ruchome sumy w dzielnicach na będą miały zwykle rozkłady dwumianowe, co da im przewidywalne entropie (przynajmniej dla dużych tablic), które można aproksymować o :$0$$1$$1$$k$$k$$1 + \log_2(k)$

Wyniki te znajdują potwierdzenie w symulacji z tablicami do . Jednak rozkładają się na małe tablice (na przykład tutaj tablice na ) z powodu korelacji między sąsiednimi oknami (gdy rozmiar okna wynosi około połowy wymiarów tablicy) i ze względu na małą ilość danych. Oto profil odniesienia losowych tablic na wygenerowanych przez symulację wraz ze wykresami niektórych rzeczywistych profili:$m=n=100$$5$$5$$5$$5$

Na tym wykresie profil odniesienia jest jednolicie niebieski. Profile tablic odpowiadają : czerwony, : złoty, : zielony, : jasnoniebieski. (Włączenie zasłoniłoby obraz, ponieważ jest on zbliżony do profilu .) Ogólnie profile odpowiadają kolejności w pytaniu: zmniejszają się co najwyżej wartości wraz ze wzrostem pozornego uporządkowania. Wyjątkiem jest : do końca, dla , jego sumy ruchome mają zwykle jedne z najniższych entropii. Ujawnia to zaskakującą prawidłowość: co na dzielnice w$a_1$$a_2$$a_3$$a_4$$a_5$$a_4$$k$$a_1$$k=4$$2$$2$$a_1$ ma dokładnie lub czarne kwadraty, nigdy więcej lub mniej. Jest znacznie mniej „losowy”, niż mogłoby się wydawać. (Jest to częściowo spowodowane utratą informacji, która towarzyszy sumowaniu wartości w każdym sąsiedztwie, procedura, która skrapla możliwych konfiguracji sąsiedztwa w tylko różnych możliwych sumach. Jeśli chcielibyśmy uwzględnić konkretnie dla grupowania i orientacji w obrębie każdego sąsiedztwa, zamiast korzystać z ruchomych sum, użylibyśmy ruchomych konkatenacji. Oznacza to, że każde sąsiedztwo na ma$1$$2$$2^{k^2}$$k^2+1$$k$$k$$2^{k^2}$możliwe różne konfiguracje; rozróżniając je wszystkie, możemy uzyskać dokładniejszą miarę entropii. Podejrzewam, że taki środek podniósłby profil porównaniu z innymi obrazami.)$a_1$

Ta technika tworzenia profilu entropii w kontrolowanym zakresie skal, poprzez sumowanie (lub łączenie lub inne łączenie) wartości w ruchomych dzielnicach, została zastosowana w analizie obrazów. Jest to dwuwymiarowe uogólnienie dobrze znanej idei analizy tekstu najpierw jako szeregu liter, a następnie jako serii digrafów (ciągów dwuliterowych), a następnie jako trygrafów itp. Ma także pewne wyraźne związki z fraktalem analiza (która bada właściwości obrazu w coraz mniejszej skali). Jeśli dołożymy starań, aby zastosować sumę ruchomą bloku lub konkatenację bloku (aby nie zachodziły na siebie okna), można uzyskać proste relacje matematyczne między kolejnymi entropiami; jednak,

Możliwe są różne rozszerzenia. Na przykład w przypadku profilu niezmiennego obrotowo należy stosować sąsiedztwa kołowe, a nie kwadratowe. Oczywiście wszystko uogólnia się poza tablicami binarnymi. Przy wystarczająco dużych tablicach można nawet obliczyć lokalnie zmieniające się profile entropii w celu wykrycia niestacjonarności.

Jeśli pożądana jest pojedyncza liczba, zamiast całego profilu, wybierz skalę, w której interesująca jest przypadkowość przestrzenna (lub jej brak). W tych przykładach skala ta najlepiej odpowiadałaby ruchomemu sąsiedztwu na lub na , ponieważ do ich wzorowania wszyscy opierają się na grupach obejmujących od trzech do pięciu komórek (a sąsiedztwo na jedynie uśrednia wszystkie warianty w tablica i tak jest bezużyteczne). W drugiej skali entropie dla do wynoszą , , , i$3$$3$$4$$4$$5$$5$$a_1$$a_5$$1.50$$0.81$$0$$0$$0$ ; oczekiwana entropia w tej skali (dla tablicy jednorodnie losowej) wynosi . Uzasadnia to poczucie, że „powinna mieć raczej wysoką entropię”. Aby rozróżnić , i , które są powiązane z entropią w tej skali, spójrz na następną lepszą rozdzielczość ( na dzielnice): ich entropie wynoszą odpowiednio , , (podczas gdy losowa siatka powinna mają wartość ). Dzięki tym środkom pierwotne pytanie ustawia tablice we właściwej kolejności.$1.34$$a_1$$a_3$$a_4$$a_5$$0$$3$$3$$1.39$$0.99$$0.92$$1.77$

Po pierwsze, moja sugestia jest czysto intuicyjna: nic nie wiem w dziedzinie rozpoznawania wzorców. Po drugie, można by zaproponować dziesiątki alternatywnych propozycji, takich jak moje.

Zaczynam od pomysłu, że regularna konfiguracja (to znaczy z niską entropią) powinna być w jakiś sposób symetryczna, izomorficzna w stosunku do tego lub tamtego jego transformantów. Na przykład w obrotach.

Możesz obracać matrycę (obrócić o 90 stopni, niż o 180 stopni itp.), Dopóki konfiguracja nie zgadza się z oryginalną . Zawsze będzie się zgadzać po 4 obrotach (360 stopni), ale czasami może się zgadzać wcześniej (jak na zdjęciu macierz E).

Przy każdym obrocie policz liczbę komórek o nie identycznych wartościach między oryginalną konfiguracją a obróconą. Na przykład, jeśli porównasz oryginalną matrycę A z jej obrotem o 90 stopni, odkryjesz 10 komórek, w których jest miejsce w jednej matrycy i puste w drugiej matrycy. Następnie porównaj oryginalną matrycę z jej obrotem o 180 stopni: znajdzie się 11 takich komórek. 10 komórek to rozbieżność między oryginalną matrycą A a jej obróceniem o 270 stopni. 10 + 11 + 10 = 31 jest ogólnie "entropia" macierzy A .

Dla macierzy B „entropia” wynosi 20, a dla macierzy E tylko 12. Dla macierzy C i D „entropia” wynosi 0, ponieważ obroty zatrzymują się po 90 stopniach: już osiągnięty izomorfizm.

Informacje te są powszechnie definiowane jako . Istnieje pewna ładna teoria wyjaśniająca, że to ilość bitów potrzebna do zakodowania za pomocą . Jeśli chcesz dowiedzieć się więcej na ten temat, przeczytaj o kodowaniu arytmetycznym .$h(x) = \log p(x)$$\log_2 p(x)$$x$$p$

Jak to może rozwiązać twój problem? Łatwo. Znajdź które reprezentuje twoje dane, i użyj gdzie to nowa próbka jako miara zaskoczenia lub informacji o ich spotkaniu.- log p ( x ) $p$$-\log p(x)$$x$

Trudno jest znaleźć jakiś model dla i wygenerować swoje dane. Może uda ci się wymyślić algorytm, który generuje macierze, które uważasz za „prawdopodobne”.$p$

Kilka pomysłów na dopasowanie .$p$

1. Jeśli patrzysz tylko na matryce 5x5, potrzebujesz tylko bitów do przechowywania wszystkich możliwych matryc, więc możesz po prostu wyliczyć je wszystkie i przypisać każdemu z nich pewne prawdopodobieństwo.$2^{25}$
2. Użyj ograniczonej maszyny Boltzmanna, aby dopasować swoje dane (wtedy będziesz musiał użyć darmowej energii jako substytutu informacji, ale to w porządku),
3. Użyj zip jako zamiennika i nie przejmuj się całą historią prawdopodobieństwa z góry. Jest to nawet formalnie w porządku, ponieważ używasz zip jako przybliżenia złożoności Kołmogorowa, a zostało to zrobione przez teoretyków informacji, co prowadzi również do znormalizowanej odległości kompresji ,$-\log p(x)$
4. Może użyć modelu graficznego, aby uwzględnić wcześniejsze przekonania przestrzenne i użyć zmiennych Bernoulliego lokalnie.
5. Aby zakodować niezmienność translacyjną, możesz użyć modelu opartego na energii za pomocą sieci splotowej .

Niektóre z powyższych pomysłów są dość ciężkie i pochodzą z uczenia maszynowego. Jeśli chcesz uzyskać dodatkowe porady, skorzystaj z komentarzy.

Moja następująca propozycja jest raczej wnikliwa niż wydedukowana, więc nie mogę tego udowodnić, ale mogę przynajmniej przedstawić jakieś uzasadnienie. Procedura oceny „entropii” konfiguracji plam obejmuje:

1. Digitalizuj miejsca.
2. Wykonaj porównanie konfiguracji z samą permutacją, wielokrotnie, za pomocą ortogonalnej analizy Procrustes .
3. Wykreślić wyniki porównań (współczynnik tożsamości) i ocenić poszarpanie wykresu.

Digitalizuj miejsca , to znaczy weź ich współrzędne. Na przykład poniżej znajduje się konfiguracja D z numerowanymi punktami (kolejność numeracji może być dowolna) i ich współrzędne.

spot x   y
1   1   1
2   3   1
3   5   1
4   2   2
5   4   2
6   1   3
7   3   3
8   5   3
9   2   4
10  4   4
11  1   5
12  3   5
13  5   5

Wykonaj permutacje i przeprowadź analizę Procrustes. Dopuszczaj spoty (wiersze w danych) losowo i przeprowadzaj porównanie Procrustes oryginalnych (nie permutowanych) danych z permutowanymi; zapisz współczynnik tożsamości (miara podobieństwa dwóch konfiguracji, wynik analizy). Powtórz permutację - Procrustes - zapisywanie współczynnika wiele razy (np. 1000 razy lub więcej).

Czego możemy oczekiwać od współczynników tożsamości (IDc) uzyskanych po powyższej operacji na regularnej strukturze?Rozważmy na przykład powyższą konfigurację D. Jeśli porównamy oryginalny zestaw współrzędnych z samym sobą, otrzymamy oczywiście IDc = 1. Ale jeśli permutujemy niektóre spoty, IDc między zestawem oryginalnym a permutowanym będzie miało wartość poniżej 1. Pozwólmy permutować, na przykład, jedną parę spacji, oznaczoną 1 i 4. IDc = .964. Teraz zamiast tego permutuj miejsca 3 i 5. Co ciekawe, IDc będzie ponownie .964. Ta sama wartość, dlaczego? Punkty 3 i 5 są symetryczne do 1 i 4, więc obrót o 90 stopni je narzuca. Porównanie Procrustes jest niewrażliwe na obrót lub odbicie, a zatem permutacja w parze 1-4 jest dla niego „taka sama” jak permutacja w parze 5-3. Aby dodać więcej przykładów, jeśli permutujesz tylko miejsca 4 i 7, IDc będzie ponownie .964! Apeluje, że dla Procrustes permutacja w parze 4-7 jest „taka sama” jak powyższe dwa w tym sensie, że daje ten sam stopień podobieństwa (mierzony przez IDc). Oczywiście wszystko to wynika z tego, że konfiguracja D jest regularna.W przypadku regularnej konfiguracji oczekujemy uzyskania raczej dyskretnych wartości IDc w naszym eksperymencie permutacji / porównania; natomiast w przypadku nieregularnej konfiguracji spodziewamy się, że wartości będą miały charakter ciągły.

Wykreślić zarejestrowane wartości IDc. Na przykład posortuj wartości i utwórz wykres liniowy. Zrobiłem eksperyment - 5000 kombinacji - z każdą konfiguracją A, B (obie dość nieregularne), D, E (obie regularne), a oto wykres liniowy:

Zwróć uwagę, o ile bardziej postrzępione są linie D i E (szczególnie D). Wynika to z dyskrecji wartości. Wartości dla A i B są znacznie bardziej ciągłe. Możesz wybrać sobie jakąś statystykę, która ocenia stopień dyskrecji / ciągłości, zamiast kreślenia. Wydaje się, że nie jest bardziej ciągła niż B (dla ciebie konfiguracja A jest nieco mniej regularna, ale mój wykres liniowy wydaje się tego nie demonstrować) lub, jeśli nie, może wyświetlać nieco inny wzór wartości IDc. Jaki inny wzór? To jest poza zakresem mojej odpowiedzi. Wielkie pytanie, czy A rzeczywiście jest mniej regularne niż B: może być dla twojego oka, ale niekoniecznie dla analizy Procrustes lub oka innej osoby.

Nawiasem mówiąc, cały eksperyment permutacji / Procrustes zrobiłem bardzo szybko. Użyłem własnego makra analizy Procrustes dla SPSS (znajdującego się na mojej stronie internetowej) i dodałem kilka wierszy kodu, aby wykonać permutacje.

Wzajemne informacje, biorąc pod uwagę każdy wymiar jako zmienną losową, a zatem każdą macierz jako zestaw par liczb, powinny pomóc we wszystkich przypadkach, z wyjątkiem C, gdzie nie jestem pewien wyniku.

Zobacz dyskusję wokół ryc. 8 (rozpoczynającą się w p24) na temat analizy wydajności regresji w podręczniku TMVA lub odpowiednim wpisie arxiv .

Zamiast patrzeć na globalne właściwości wzoru (takie jak symetrie), można spojrzeć na lokalne, np. Liczbę sąsiadów każdego kamienia (= czarne kółko). Oznaczmy całkowitą liczbę kamieni przez .$s$

Jeśli kamienie są rzucane losowo, rozkład sąsiadów wynosi gdzie to gęstość kamieni. Liczba miejsc zależy od tego, czy kamień znajduje się we wnętrzu ( ), na krawędzi ( ) czy na rogu .

Wyraźnie widać, że rozkład sąsiadów w C) , D) i E) jest daleki od losowego. Na przykład dla D) wszystkie kamienie wewnętrzne mają dokładnie sąsiadów (w przeciwieństwie do losowego rozkładu, co daje w zamiast zmierzonego ).$4$$\approx (0\%,2\%,9\%,20\%,27\%,24\%,13\%,4\%,0\%)$$(0\%,0\%,0\%,0\%,100\%,0\%,0\%,0\%,0\%)$

Aby więc oszacować, czy wzór jest losowy, musisz porównać jego rozkład sąsiadów i porównać go z losowym . Na przykład możesz porównać ich średnie i wariancje.$P_{measured}(k|n)$$P_{rand,p}(k|n)$

Alternatywnie można zmierzyć ich odległości w przestrzeniach funkcji, np .: gdzie jest zmierzonym stosunkiem punktów z sąsiednie spacje, a jest przewidywanym wzorem losowym, tj. , i .

Istnieje naprawdę prosty sposób na konceptualizację zawartości informacyjnej, która nawiązuje do pomysłu Shannona (co prawda jednowymiarowego), wykorzystując prawdopodobieństwa i prawdopodobieństwa przejścia w celu znalezienia najmniej redundantnej reprezentacji ciągu tekstowego. W przypadku obrazu (w tym konkretnym przypadku obrazu binarnego zdefiniowanego na macierzy kwadratowej) możemy jednoznacznie zrekonstruować na podstawie wiedzy na temat pochodnych xiy (-1,0, + 1). Możemy zdefiniować prawdopodobieństwo przejścia 3x3 i globalną funkcję gęstości prawdopodobieństwa, również 3x3. Informacje Shannona są następnie uzyskiwane z klasycznej formuły sumowania logarytmicznego stosowanej na 3x3. Jest to miara informacji Shannona drugiego rzędu i ładnie oddaje strukturę przestrzenną w pdf 3x3.

To podejście jest bardziej intuicyjne, gdy stosuje się je do obrazów w skali szarości z więcej niż 2 (binarnymi) poziomami, więcej informacji na stronie https://arxiv.org/abs/1609.01117 .

Czytając to, przychodzą mi na myśl dwie rzeczy. Po pierwsze, wiele właściwości gestaltu jest dość trudnych do przewidzenia, a wiele pracy na poziomie doktoranckim zajmuje się opracowaniem modeli tego, jak odbywają się grupowania. Instynktownie zakładam, że najłatwiejsze zasady, o których można pomyśleć, kończą się licznymi przykładami.

Jeśli na razie możesz odłożyć na bok opis grup gestalt, myślę, że pomocną abstrakcją jest potraktowanie twojego wkładu jako specjalnego przypadku obrazu. Istnieje wiele algorytmów w wizji komputerowej, które mają na celu przypisanie podpisu do obrazu w oparciu o zestaw funkcji, które są niezmienne w skali i niezmienne. Myślę, że najbardziej znane są funkcje SIFT:

http://en.wikipedia.org/wiki/Scale-invariant_feature_transform

Zasadniczo twój wynik będzie nowym wektorem, który podaje wagi tych funkcji. Możesz użyć tego wektora i zastosować do niego heurystykę (być może znaleźć normę) i mieć nadzieję, że opisuje to, czego szukasz. Alternatywnie, możesz wyszkolić klasyfikatora do przyjmowania wektora cech jako danych wejściowych i po prostu powiedzieć mu, jakie jest twoje wrażenie jego „entropii”. Zaletą tego jest to, że użyje odpowiednich funkcji SIFT (które zdecydowanie przesadzają z twoim problemem) i zbuduje coś w rodzaju mapowania, które może być bardzo odpowiednie. Minusem jest to, że musisz samodzielnie wykonać wiele takich czynności, a to, co otrzymasz, może być trudniejsze do interpretacji, w zależności od używanego klasyfikatora.

Mam nadzieję, że to jest pomocne! Wiele tradycyjnych algorytmów widzenia komputerowego również może być dla Ciebie odpowiednich - szybkie przeglądanie wikipedii w tym portalu może dać ci dodatkowy wgląd.

Wasze przykłady przypominają mi tablice prawdy z algebry boolowskiej i układów cyfrowych. W tej dziedzinie mapy Karnaugh (http://en.wikipedia.org/wiki/Karnaugh_map) mogą być używane jako narzędzie do zapewnienia minimalnej funkcji boolowskiej do wyrażenia całej siatki. Alternatywnie, użycie tożsamości algebry logicznej może pomóc zredukować funkcję do jej minimalnej postaci. Liczenie liczby terminów w zminimalizowanej funkcji boolowskiej może być użyte jako miara entropii. Daje to symetrię pionową i poziomą oraz ściskanie sąsiadujących sąsiadów, ale brakuje symetrii diagonalnej.

Za pomocą algebry logicznej obie osie są oznaczone od AE, zaczynając od lewego górnego rogu. W ten sposób przykład C zamapowałby się na funkcję boolowską (! A i! E). W przypadku innych przykładów osie musiałyby być oznakowane osobno (tj. AE, FJ).