Messung von Entropie / Information / Mustern einer 2d-Binärmatrix

53

Ich möchte die Entropie / Informationsdichte / Musterähnlichkeit einer zweidimensionalen binären Matrix messen. Lassen Sie mich zur Verdeutlichung einige Bilder zeigen:

Diese Anzeige sollte eine ziemlich hohe Entropie haben:

EIN)

Bildbeschreibung hier eingeben

Dies sollte eine mittlere Entropie haben:

B)

Bildbeschreibung hier eingeben

Diese Bilder sollten schließlich alle eine Entropie nahe Null haben:

C)

Bildbeschreibung hier eingeben

D)

Bildbeschreibung hier eingeben

E)

Bildbeschreibung hier eingeben

Gibt es einen Index, der die Entropie erfasst? die "Musterähnlichkeit" dieser Displays?

Natürlich reagiert jeder Algorithmus (z. B. Kompressionsalgorithmen oder der von ttnphns vorgeschlagene Rotationsalgorithmus ) auf andere Merkmale der Anzeige. Ich suche einen Algorithmus, der versucht, folgende Eigenschaften zu erfassen:

  • Rotations- und Axialsymmetrie
  • Die Menge an Clustering
  • Wiederholungen

Möglicherweise komplizierter, könnte der Algorithmus empfindlich auf Eigenschaften des psychologischen " Gestaltprinzips " reagieren , insbesondere auf:

  • Das Gesetz der Nähe: Gesetz der Nähe
  • Das Gesetz der Symmetrie: Symmetrische Bilder werden auch in einiger Entfernung kollektiv wahrgenommen:Symmetrie

Displays mit diesen Eigenschaften sollten einen "niedrigen Entropiewert" erhalten. Displays mit eher zufälligen / unstrukturierten Punkten sollten einen "hohen Entropiewert" erhalten.

Mir ist bekannt, dass wahrscheinlich kein einziger Algorithmus alle diese Funktionen erfasst. Daher sind auch Vorschläge für Algorithmen, die nur einige oder sogar nur eine Funktion ansprechen, sehr willkommen.

Insbesondere bin ich auf der Suche nach konkreten, vorhandenen Algorithmen oder nach konkreten, umsetzbaren Ideen (und werde die Prämie nach diesen Kriterien vergeben).

Felix S
quelle
Coole Frage! Kann ich aber fragen, was dazu motiviert, eine einzige Maßnahme zu brauchen? Ihre drei Eigenschaften (Symmetrie, Clustering und Wiederholungen) scheinen unabhängig genug zu sein, um separate Maßnahmen zu rechtfertigen.
Andy W
Bisher bin ich etwas skeptisch, dass man ein universelles Algo finden kann, das das Gestaltprinzip implementiert. Letzteres basiert hauptsächlich auf der Erkennung bereits vorhandener Prototypen. Ihr Verstand kann diese haben, aber Ihr Computer kann nicht.
ttnphns
Ich stimme Ihnen beiden zu. Eigentlich habe ich nicht nach einem einzigen Algorithmus gesucht - obwohl meine vorherige Formulierung dies tatsächlich nahe legte. Ich habe die Frage aktualisiert, um explizit Algorithmen für einzelne Eigenschaften zuzulassen. Vielleicht hat jemand auch Ideen, wie die Ausgabe mehrerer Algen kombiniert werden kann (z. B. "Immer den niedrigsten Entropiewert der Menge von Algen nehmen")
Felix S
1
Das Kopfgeld ist vorbei . Vielen Dank an alle Mitwirkenden und die tollen Ideen! Diese Prämie führte zu einer Reihe interessanter Ansätze. Einige Antworten enthalten viel Kopfarbeit, und manchmal ist es schade, dass Kopfgelder nicht aufgeteilt werden können. Schließlich entschloss ich mich, die Prämie an @whuber zu vergeben, da seine Lösung der Algorithmus war, der mir in Bezug auf die erfassten Funktionen am umfassendsten erschien und der einfach zu implementieren ist. Ich schätze es auch, dass es auf meine konkreten Beispiele angewendet wurde. Am beeindruckendsten war seine Fähigkeit, Zahlen in der exakten Reihenfolge meiner "intuitiven Rangfolge" zuzuweisen. Vielen Dank, F
Felix S

Antworten:

35

Es gibt ein einfaches Verfahren, das die gesamte Intuition erfasst, einschließlich der psychologischen und geometrischen Elemente. Es basiert auf der räumlichen Nähe , die die Grundlage unserer Wahrnehmung ist und eine intrinsische Möglichkeit bietet, das zu erfassen, was nur unvollständig durch Symmetrien gemessen wird.

Dazu müssen wir die "Komplexität" dieser Arrays auf verschiedenen lokalen Skalen messen. Obwohl wir viel Flexibilität bei der Auswahl dieser Skalen und bei der Auswahl des Maßes für die "Nähe" haben, ist es einfach und effektiv genug, kleine quadratische Nachbarschaften zu verwenden und deren Durchschnittswerte (oder gleichwertig Summen) zu betrachten. Zu diesem Zweck kann eine Sequenz von Arrays von jedem abgeleitet wird von Array durch Bilden bewegende Nachbarschaft Summen unter Verwendung durch Nachbarschaften, dann von , usw., bis durch (obwohl es dann normalerweise zu wenige Werte gibt, um etwas verlässliches zu liefern).mnk=2233min(n,m)min(n,m)

Um zu sehen, wie dies funktioniert, führen wir die Berechnungen für die Arrays in der Frage, die ich als bis , von oben nach unten durch. Hier sind Diagramme der Bewegungssummen für ( ist natürlich das ursprüngliche Array), die auf angewendet werden .a1a5k=1,2,3,4k=1a1

Abbildung 1

Von links oben im Uhrzeigersinn ist gleich , , und . Die Arrays sind jeweils mal , dann mal , mal und mal . Sie sehen alle irgendwie "zufällig" aus. Lassen Sie uns diese Zufälligkeit mit ihrer Basis-2-Entropie messen. Für ist die Folge dieser Entropien . Nennen wir dies das "Profil" von .k124355442233a1(0.97,0.99,0.92,1.5)a1

Im Gegensatz dazu sind hier die Bewegungssummen von :a4

Figur 2

Für gibt es wenig Variation, daher geringe Entropie. Das Profil ist . Seine Werte sind durchweg niedriger als die Werte für , was das intuitive Gefühl bestätigt, dass in ein starkes "Muster" vorhanden .k=2,3,4(1.00,0,0.99,0)a1a4

Für die Interpretation dieser Profile benötigen wir einen Referenzrahmen. Ein perfekt zufälliges Array von Binärwerten hat nur etwa die Hälfte seiner Werte gleich und die andere Hälfte gleich , bei einer Entropie von . Die sich bewegenden Summen innerhalb von mal Nachbarschaften tendieren dazu, Binomialverteilungen zu haben, was ihnen vorhersagbare Entropien (zumindest für große Arrays) gibt, die durch angenähert werden können :011kk1+log2(k)

Entropieplot

Diese Ergebnisse werden durch Simulation mit Arrays bis zu . Aber sie brechen für kleine Arrays (wie die von Arrays hier) aufgrund Korrelation zwischen benachbarten Fenstern (wenn die Fenstergröße ist etwa die Hälfte der Abmessungen des Arrays) , und aufgrund der geringen Menge an Daten. Hier ist ein Referenzprofil von Zufall von Arrays durch Simulation erzeugt zusammen mit Plots einiger tatsächlichen Profile:m=n=1005555

Profildarstellungen

In diesem Diagramm ist das Referenzprofil durchgehend blau. Die Array-Profile entsprechen : Rot, : Gold, : Grün, : Hellblau. (Einschließlich würde das Bild verdecken, da es nahe am Profil von .) Insgesamt entsprechen die Profile der Reihenfolge in der Frage: Sie werden bei den meisten Werten von niedriger, wenn die scheinbare Reihenfolge zunimmt. Die Ausnahme ist : Bis zum Ende haben die sich bewegenden Summen für tendenziell die niedrigsten Entropien. Dies zeigt eine überraschende Regelmäßigkeit: Alle mal Viertel ina 2a1a2a3a4a5a4ka1k=422a1 hat genau oder schwarze Quadrate, niemals mehr oder weniger. Es ist viel weniger "zufällig" als man denkt. (Dies ist teilweise auf den Informationsverlust zurückzuführen, der mit der Summierung der Werte in jeder Nachbarschaft einhergeht. Diese Prozedur verdichtet mögliche Nachbarschaftskonfigurationen in nur verschiedene mögliche Summen. Wenn wir dies speziell berücksichtigen wollten Für die Gruppierung und Orientierung in jeder Nachbarschaft würden wir dann anstelle von beweglichen Summen bewegliche Verkettungen verwenden. Das heißt, jede mal Nachbarschaft hat122k2k2+1kk2k2mögliche unterschiedliche Konfigurationen; Indem wir sie alle unterscheiden, erhalten wir ein feineres Maß für die Entropie. Ich vermute, dass ein solches Maß das Profil von Vergleich zu den anderen Bildern erhöhen würde .)a1

Diese Technik zum Erzeugen eines Entropieprofils über einen kontrollierten Bereich von Skalen durch Summieren (oder Verketten oder anderweitiges Kombinieren) von Werten in sich bewegenden Nachbarschaften wurde bei der Analyse von Bildern verwendet. Es ist eine zweidimensionale Verallgemeinerung der bekannten Idee, Text zuerst als Buchstabenreihe, dann als Digraphenreihe (Zwei-Buchstaben-Folgen), dann als Trigraphen usw. zu analysieren. Es gibt auch einige offensichtliche Beziehungen zum Fraktal Analyse (die die Eigenschaften des Bildes in immer feineren Maßstäben untersucht). Wenn wir sorgfältig eine Blockbewegungssumme oder Blockverkettung verwenden (es gibt also keine Überlappungen zwischen Fenstern), können einfache mathematische Beziehungen zwischen den aufeinanderfolgenden Entropien abgeleitet werden. jedoch,

Verschiedene Erweiterungen sind möglich. Verwenden Sie beispielsweise für ein rotationsinvariantes Profil kreisförmige Nachbarschaften anstelle quadratischer. Natürlich verallgemeinert sich alles über binäre Arrays hinaus. Mit ausreichend großen Arrays kann man sogar lokal variierende Entropieprofile berechnen, um Nichtstationarität zu erkennen.

Wenn eine einzelne Zahl anstelle eines gesamten Profils gewünscht wird, wählen Sie den Maßstab, bei dem die räumliche Zufälligkeit (oder deren Fehlen) von Interesse ist. In diesen Beispielen entsprechen würde , dass Skala am besten zu einem von oder von Nachbarschaft bewegen, weil für ihre Musterung sie alle auf Gruppierungen verlassen, der drei bis fünf Zellen erstrecken (und eine von Nachbarschaft nur mittelt entfernt alle Variation in der Array und so ist nutzlos). In dem letztgenannten Maßstab die Entropien für durch sind , , , , und3 4 4 5 5 a 1 a 5 1,50 0,81 0 0 0 1,34 a 1 a 3 a 4 a 5 0 3 3 1,39 1,77334455a1a51.500.81000 ; Die erwartete Entropie bei dieser Skala (für ein gleichmäßig zufälliges Array) beträgt . Dies rechtfertigt das Gefühl, dass "eine ziemlich hohe Entropie haben sollte". Zur Unterscheidung , und , die mit gebunden sind in dieser Größenordnung Entropie, Blick auf die nächst feineren Auflösung ( von Vierteln): ihre Entropien sind , , , bzw. (während ein zufälliges Gitter zu erwarten haben einen Wert von ). Durch diese Maßnahmen bringt die ursprüngliche Frage die Arrays in genau die richtige Reihenfolge.1.34a1a3a4a50331.390.990.921.77

whuber
quelle
Es tut mir leid, ich konnte nicht verstehen, wie Sie Ihre bewegten Summenplots produziert haben. Bitte erläutern Sie detaillierter, wie die Bewegungssumme berechnet wird.
TTNPHNS
1
@ttnphns Hier ist eine beliebte illustrierte Hilfeseite zum Thema.
whuber
4
Ich habe die Ergebnisse dieser hervorragenden Antwort von @whuber mit NumPy und matplotlib in Python reproduziert, verfügbar hier: github.com/cosmoharrigan/matrix-entropy
Cosmo Harrigan
(+1) Hier ist ein sehr allgemeines Prinzip: Bei jedem Multiset gibt es die natürlich assoziierte Entropie der Wahrscheinlichkeitsverteilung, die durch die Multiplizitäten seiner verschiedenen Elemente , nämlich , wobei die Menge verschiedener Elemente in . Beispiele sind Multimengen von Size- gebildet Vierteln von verschiedenen Formen in Gegenstände verschiedener Abmessungen. (I posted nur eine 1D - Anwendung auf längs- Teil .)Mμ(e)eSMkkp(e):=μ(e)eSμ(e)  (eS)SMkk
res
@whuber Ausgezeichnete Antwort. Gibt es einen Artikel oder ein Lehrbuch, auf das man sich beziehen kann, auch wenn dies intuitiv Sinn macht (ich gehe davon aus, dass Sie es, wenn es sich um Ihr Originalwerk handelt, formal in einer Zeitschrift veröffentlicht haben)?
Subhacom
10

Mein Vorschlag ist zunächst rein intuitiv: Ich kenne mich mit Mustererkennung nicht aus. Zweitens könnten alternative Dutzende Vorschläge wie meine gemacht werden.

Ich beginne mit der Idee, dass eine reguläre Konfiguration (dh mit niedriger Entropie) irgendwie symmetrisch, isomorph zu dieser oder jener ihrer Transformanten sein sollte. Zum Beispiel in Umdrehungen.

Sie können Ihre Matrix drehen (auf 90 Grad, als 180 Grad, usw. drehen), bis die Konfiguration mit der ursprünglichen übereinstimmt . Es stimmt immer mit 4 Umdrehungen (360 Grad) überein, kann aber manchmal auch früher übereinstimmen (wie Matrix E im Bild).

Zählen Sie bei jeder Drehung die Anzahl der Zellen mit nicht identischen Werten zwischen der ursprünglichen und der gedrehten Konfiguration. Wenn Sie beispielsweise die ursprüngliche Matrix A mit ihrer 90-Grad-Drehung vergleichen, werden Sie 10 Zellen entdecken, in denen sich in einer Matrix ein Fleck und in der anderen Matrix ein Leerzeichen befindet. Vergleichen Sie dann die ursprüngliche Matrix mit ihrer 180-Grad-Drehung: 11 solcher Zellen werden gefunden. 10 Zellen ist die Diskrepanz zwischen der ursprünglichen Matrix A und ihrer 270-Grad-Drehung. 10 + 11 + 10 = 31 ist die gesamte "Entropie" der Matrix A .

Für die Matrix B beträgt die "Entropie" 20 und für die Matrix E nur 12. Für die Matrizen C und D beträgt die "Entropie" 0, da die Rotationen nach 90 Grad enden: Isomorphismus bereits erreicht.

Bildbeschreibung hier eingeben

ttnphns
quelle
Danke für Ihren Vorschlag! Obwohl ich mir mehrere "einfache" Anzeigen vorstellen könnte, die für eine Rotationstransformation nicht unveränderlich sind, ist dies ein schöner und einfacher (und erweiterbarer!) Ansatz. Ich muss darüber nachdenken, welche Art von Transformation ich haben möchte. Und ich mag Ihren Ansatz, bei jeder Transformation Punkte zu zählen.
Felix S
Vielen Dank für Ihre Wertschätzung. Aber der Ansatz ist nur ein erster Ansatz, eine allgemeine Idee, und Sie sagen zu Recht, dass er erweiterbar ist.
TTNPHNS
Ich mag deine Herangehensweise. Um jedoch eine allgemeinere Antwort zu erhalten, kann es sich lohnen, eine etwas größere Symmetriegruppe zu verwenden - Identität, 3 Rotationen und 4 Reflexionen (dh , en.wikipedia.org/wiki/Dihedral_group ). Zähle dann die Differenzen ( ) zwischen allen Paaren (dh ) und als Maß für die Zufälligkeit , wobei ist die Anzahl der schwarzen Steine. Für rein zufällige Formen sollte man , während für sehr symmetrische . Das Gute ist, dass die Formel für für eine unterschiedliche Anzahl von Steinen auf dem Brett gilt und die BW-Symmetrie aufweist. D4d87r=k187252n(25n))nr1r0r
Piotr Migdal
Entschuldigung für die Überkomplikation. Es genügt , die Originalmuster zu vergleichen mit seiner Symmetrien unterscheidet sich von der Identität. Dann gibt es im Normalisierungsfaktor statt . 7778
Piotr Migdal
5

Die Information wird üblicherweise definiert als . Es gibt eine nette Theorie, die erklärt, dass die Anzahl der Bits ist, die Sie benötigen, um mit zu codieren . Wenn Sie mehr darüber erfahren möchten, lesen Sie die Informationen zur arithmetischen Codierung .h(x)=logp(x)log2p(x)xp

Wie kann das Ihr Problem lösen? Einfach. Suchen Sie ein , das Ihre Daten darstellt, und verwenden Sie wobei eine neue Stichprobe als Maß für die Überraschung oder Information über die Begegnung ist.plogp(x)x

Die Schwierigkeit besteht darin, ein Modell für zu finden und Ihre Daten zu generieren. Vielleicht können Sie einen Algorithmus entwickeln, der Matrizen erzeugt, die Sie für 'wahrscheinlich' halten.p

Einige Ideen zur Anpassung .p

  1. Wenn Sie nur 5x5-Matrizen betrachten, benötigen Sie nur Bits, um alle möglichen Matrizen zu speichern. Sie können also einfach alle aufzählen und jedem eine bestimmte Wahrscheinlichkeit zuweisen.225
  2. Verwenden Sie eine eingeschränkte Boltzmann-Maschine , um Ihre Daten anzupassen (dann müssten Sie die freie Energie als Ersatz für Informationen verwenden, aber das ist in Ordnung).
  3. Verwenden Sie zip als Ersatz für und kümmern Sie sich nicht um die gesamte Wahrscheinlichkeitsgeschichte von oben. Es ist sogar formal in Ordnung, da Sie zip als Annäherung an die Kolmogorov-Komplexität verwenden und dies auch von Informationstheoretikern durchgeführt wurde, was zu dem normalisierten Kompressionsabstand führte.logp(x)
  4. Verwenden Sie möglicherweise ein grafisches Modell, um räumliche Vorurteile einzubeziehen und Bernoulli-Variablen lokal zu verwenden.
  5. Um die translatorische Invarianz zu kodieren, können Sie ein energiebasiertes Modell unter Verwendung eines Faltungsnetzwerks verwenden .

Einige der obigen Ideen sind ziemlich umfangreich und stammen aus maschinellem Lernen. Wenn Sie weitere Ratschläge wünschen, verwenden Sie einfach die Kommentare.

bayerj
quelle
Offensichtlich ist die Kolmogorov-Entropie im philosophischen Sinne der beste Ansatz, wenn Sie an "abstrakte Mustereinfachheit" denken und nicht vorhersagen möchten, wie einfach dies für den menschlichen Verstand sein wird. Die Entropie wird einfach als "Länge des kürzesten Programms, das dieses Muster erzeugen kann" angegeben. Natürlich müssen Sie immer noch die Computersprache angeben, aber Sie können sich immer noch auf eine abstrakte Turing-Maschine verlassen, um den Streich zu spielen.
Javier Rodriguez Laguna
Programmiersprache ist nicht wirklich wichtig. Ein zusätzlicher Teil des Programms, der von Sprache A nach Sprache B kompiliert, nimmt einen konstanten Bitzuwachs (der Compiler) zu und kann daher vernachlässigt werden.
Bayerj
4

Mein nachfolgender Vorschlag ist eher einsichtig als abgeleitet, daher kann ich ihn nicht beweisen, kann aber zumindest einige Gründe angeben. Das Verfahren zur Beurteilung der "Entropie" der Fleckenkonfiguration umfasst:

  1. Spots digitalisieren.
  2. Führen Sie einen Vergleich der Konfiguration mit sich selbst durch, der durch orthogonale Procrustes-Analyse mehrfach permutiert wurde .
  3. Plot-Ergebnisse von Vergleichen (Identitätskoeffizient) und Beurteilung der Zackigkeit des Plots.

Spots digitalisieren , das heißt, ihre Koordinaten nehmen. Im Folgenden sehen Sie beispielsweise Ihre Konfiguration D mit nummerierten Punkten (die Nummerierungsreihenfolge kann beliebig sein) und deren Koordinaten. Bildbeschreibung hier eingeben

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

Führen Sie Permutationen durch und führen Sie eine Procrustes-Analyse durch. Permutieren Sie Punkte (Zeilen in den Daten) nach dem Zufallsprinzip und führen Sie einen Procrustes-Vergleich der ursprünglichen (nicht permutierten) Daten mit den permutierten durch. Notieren Sie den Identitätskoeffizienten (Maß für die Ähnlichkeit der beiden Konfigurationen, ausgegeben durch die Analyse). Wiederholen Sie die Permutation - Procrustes - speichern Sie den Koeffizienten viele Male (z. B. 1000 Mal oder mehr).

Was können wir von Identitätskoeffizienten (IDc) erwarten, die nach der obigen Operation in einer regulären Struktur erhalten wurden?Betrachten Sie zum Beispiel die obige Konfiguration D. Wenn wir die ursprünglichen Koordinaten mit sich selbst vergleichen, erhalten wir natürlich IDc = 1. Wenn wir jedoch einige Punkte permutieren, wird der IDc zwischen dem ursprünglichen Satz und dem permutierten Wert unter 1 liegen. Lassen Sie uns beispielsweise ein Paar von Punkten permutieren, die mit 1 und 4 bezeichnet sind. IDc = .964. Setzen Sie stattdessen die Punkte 3 und 5 durch. Interessanterweise wird IDc wieder 0,964 sein. Der gleiche Wert, warum? Die Punkte 3 und 5 sind symmetrisch zu 1 und 4, sodass eine Drehung um 90 Grad sie überlagert. Der Vergleich von Procrustes ist unempfindlich gegenüber Rotation oder Reflexion, und dadurch ist die Permutation innerhalb des Paars 1-4 für ihn gleich der Permutation innerhalb des Paars 5-3. Um ein weiteres Beispiel hinzuzufügen, wenn Sie nur die Punkte 4 und 7 permutieren, wird IDc wieder 0,964 sein! Es scheint, dass für Procrustes die Permutation innerhalb des Paares 4-7 "gleich" ist. wie die beiden oben in dem Sinne, dass es den gleichen Grad an Ähnlichkeit gibt (gemessen durch IDc). Offensichtlich liegt dies alles daran, dass die Konfiguration D regelmäßig ist.Für eine reguläre Konfiguration erwarten wir in unserem Permutations- / Vergleichsexperiment eher diskrete IDc-Werte. Bei unregelmäßigen Konfigurationen gehen wir davon aus, dass die Werte tendenziell kontinuierlich sind.

Zeichnen Sie die aufgezeichneten IDc-Werte. Sortieren Sie zum Beispiel die Werte und zeichnen Sie die Linien. Ich habe das Experiment durchgeführt - 5000 Permutationen - mit jeder Ihrer Konfigurationen A, B (beide ziemlich unregelmäßig), D, E (beide regelmäßig) und hier ist das Liniendiagramm:

Bildbeschreibung hier eingeben

Beachten Sie, wie viel gezackter die Linien D und E (insbesondere D) sind. Dies liegt an der Diskretion der Werte. Die Werte für A und B sind viel kontinuierlicher. Sie können sich eine Art Statistik aussuchen, die den Grad der Diskretion / Kontinuität schätzt, anstatt zu zeichnen. A scheint nicht kontinuierlicher zu sein als B (für Sie ist Konfiguration A etwas weniger regelmäßig, aber mein Liniendiagramm scheint es nicht zu demonstrieren) oder, falls nicht, zeigt es vielleicht ein anderes Muster von IDc-Werten. Was für ein anderes Muster? Dies würde den Rahmen meiner Antwort noch sprengen. Die große Frage, ob A tatsächlich weniger regelmäßig ist als B: Es mag für Ihr Auge sein, aber nicht unbedingt für die Procrustes-Analyse oder für das Auge einer anderen Person.

Übrigens, das ganze Permutations- / Procrustes-Experiment habe ich sehr schnell gemacht. Ich habe mein eigenes Procrustes-Analysemakro für SPSS (auf meiner Webseite) verwendet und einige Codezeilen hinzugefügt, um Permutationen durchzuführen.

ttnphns
quelle
3

Gegenseitige Informationen, die jede Dimension als Zufallsvariable betrachten, also jede Matrix als eine Menge von Zahlenpaaren, sollten in allen Fällen hilfreich sein, mit Ausnahme von C, bei dem ich nicht sicher bin, was das Ergebnis ist.

Siehe die Diskussion um Abb. 8 (ab Seite 24) zur Regressionsleistungsanalyse im TMVA-Handbuch oder den entsprechenden Eintrag in arxiv .

Unterschiedliche Metriken für unterschiedliche Verteilungen

adavid
quelle
Ich habe Probleme beim Öffnen des verlinkten Dokuments.
TTNPHNS
Ein alternativer Link wurde hinzugefügt. Aber der erste funktioniert bei mir (gerade getestet).
Adavid
3

Anstatt globale Eigenschaften des Musters (wie Symmetrien) zu betrachten, kann man sich die lokalen ansehen, zB die Anzahl der Nachbarn, die jeder Stein (= schwarzer Kreis) hat. Wir bezeichnen die Gesamtzahl der Steine ​​mit .s

Wenn die Steine ​​zufällig geworfen wurden, ist die Verteilung der Nachbarn wobei die Dichte der Steine ​​ist. Die Anzahl der Stellen hängt davon ab, ob sich ein Stein im Inneren ( ), an der Kante ( ) oder an der Ecke .

Prand,p(k neighbors|n places)=(nk)pk(1p)nk,
n n = 8 n = 5 ( n = 3 )p=s/25nn=8n=5(n=3)

Es ist deutlich zu erkennen, dass die Verteilung der Nachbarn in C) , D) und E) alles andere als zufällig ist. Zum Beispiel haben für D) alle inneren Steine ​​genau Nachbarn (entgegen der zufälligen Verteilung, die in ergibt anstelle der gemessenen ).4(0%,2%,9%,20%,27%,24%,13%,4%,0%)(0%,0%,0%,0%,100%,0%,0%,0%,0%)

Um zu quantifizieren, ob ein Muster zufällig ist, müssen Sie seine Verteilung der Nachbarn vergleichen und es mit einem zufälligen . Zum Beispiel können Sie ihre Mittelwerte und Abweichungen vergleichen.Pmeasured(k|n)Prand,p(k|n)

Alternativ kann man ihre Abstände in den Funktionsräumen messen, zB: wobei das gemessene Verhältnis von Punkten mit benachbarte Räume und ist das für ein Zufallsmuster vorhergesagte, dh , und .

n={3,5,8}k=0n[Pmeasured(k|n)Pmeasured(n)Prand,p(k|n)Prand,p(n)]2,
Pmeasured(n)nPrand,p(n)Prand,p(3)=4/25Prand,p(5)=12/25Prand,p(8)=9/25
Piotr Migdal
quelle
2

Es gibt eine sehr einfache Möglichkeit, den Informationsgehalt, der auf Shannons (zugegebenermaßen eindimensionale) Idee zurückgeht, mithilfe von Wahrscheinlichkeiten und Übergangswahrscheinlichkeiten zu konzipieren, um eine möglichst redundante Darstellung einer Textzeichenfolge zu finden. Für ein Bild (in diesem speziellen Fall ein Binärbild, das auf einer quadratischen Matrix definiert ist) können wir aus der Kenntnis der x- und y-Ableitungen (-1,0, + 1) eindeutig rekonstruieren. Wir können eine 3x3 Übergangswahrscheinlichkeit und eine globale Wahrscheinlichkeitsdichtefunktion definieren, auch 3x3. Die Shannon-Informationen werden dann aus der klassischen logarithmischen Summierungsformel erhalten, die über 3x3 angewendet wird. Dies ist ein Shannon-Informationsmaß zweiter Ordnung, das die räumliche Struktur im 3x3-PDF gut erfasst.

Dieser Ansatz ist intuitiver, wenn er auf Graustufenbilder mit mehr als 2 (binären) Ebenen angewendet wird. Weitere Informationen finden Sie unter https://arxiv.org/abs/1609.01117 .

Kieran Larkin
quelle
1

Beim Lesen fallen mir zwei Dinge ein. Das erste ist, dass viele der Gestalt-Eigenschaften ziemlich schwierig vorherzusagen sind, und es wird viel Arbeit auf Doktorandenebene darauf verwendet, Modelle für die Art und Weise der Gruppierung zu finden. Mein Instinkt ist, dass die einfachsten Regeln, die Sie sich vorstellen können, Gegenbeispiele liefern.

Wenn Sie die Beschreibung von Gestaltgruppierungen vorerst beiseite legen können, ist es meiner Meinung nach eine hilfreiche Abstraktion, sich Ihre Eingabe als einen Sonderfall eines Bildes vorzustellen. In der Bildverarbeitung gibt es viele Algorithmen, die darauf abzielen, einem Bild eine Signatur zuzuweisen, die auf einer Reihe von Merkmalen basiert, die skalierungsinvariant und merkmalsinvariant sind. Am bekanntesten sind meines Erachtens die SIFT-Funktionen:

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

Grundsätzlich ist Ihre Ausgabe ein neuer Vektor, der die Gewichte für diese Funktionen angibt. Sie könnten diesen Vektor verwenden und entweder eine Heuristik darauf anwenden (vielleicht die Norm finden) und hoffen, dass er beschreibt, wonach Sie suchen. Alternativ können Sie einen Klassifikator so trainieren, dass er den Merkmalsvektor als Eingabe verwendet und ihm einfach mitteilt, wie Sie sich die Entropie vorstellen. Der Vorteil dabei ist, dass die entsprechenden SIFT-Funktionen verwendet werden (die für Ihr Problem definitiv übertrieben sind) und eine Art Zuordnung erstellt wird, die möglicherweise sehr gut geeignet ist. Der Nachteil ist, dass Sie einen Großteil dieser Kennzeichnung selbst vornehmen müssen. Je nach verwendetem Klassifikator ist die Interpretation möglicherweise schwieriger.

Ich hoffe das ist hilfreich! Viele traditionelle Computer-Vision-Algorithmen sind hier möglicherweise auch für Sie geeignet. Wenn Sie in Wikipedia in diesem Portal blättern, erhalten Sie möglicherweise zusätzliche Einblicke.

alexplanation
quelle
0

Ihre Beispiele erinnern mich an Wahrheitstabellen aus der Booleschen Algebra und digitalen Schaltungen. In diesem Bereich können Karnaugh-Karten (http://en.wikipedia.org/wiki/Karnaugh_map) als Werkzeug verwendet werden, um die minimale boolesche Funktion zum Ausdrücken des gesamten Rasters bereitzustellen. Alternativ kann die Verwendung von booleschen Algebra-Identitäten dazu beitragen, die Funktion auf ihre Minimalform zu reduzieren. Das Zählen der Anzahl der Terme in der minimierten Booleschen Funktion kann als Entropiemaß verwendet werden. Auf diese Weise erhalten Sie vertikale und horizontale Symmetrie sowie eine Komprimierung benachbarter Nachbarn, jedoch keine diagonale Symmetrie.

Bei Verwendung der Booleschen Algebra werden beide Achsen ab der linken oberen Ecke mit AE bezeichnet. Auf diese Weise würde Beispiel C der Booleschen Funktion (! A &! E) zuordnen. Für andere Beispiele müssten die Achsen separat beschriftet werden (dh AE, FJ).

Kantenschneider
quelle