computer-science - maschinelles lernen c++ zusammenfassung



Was ist die Informatik-Definition der Entropie? (11)

Entropie ist wie ein Hash-Code für Virenforscher. Weniger Entropie, die Sie bekommen, würde bedeuten, dass es sich wahrscheinlich um verschlüsselten oder komprimierten Code handelt, der möglicherweise ein Virus sein könnte.

Eine Standard-Binärdatei hätte eine höhere Entropie als eine komprimierte oder verschlüsselte.

https://ffff65535.com

Ich habe kürzlich einen Kurs über Datenkompression an meiner Universität begonnen. Allerdings finde ich den Begriff "Entropie", wie er für die Informatik gilt, eher zweideutig. Soweit ich das beurteilen kann, übersetzt sich das grob in die "Zufälligkeit" eines Systems oder einer Struktur.

Was ist die richtige Definition von "Entropie" der Informatik?


Entropie kann verschiedene Dinge bedeuten:

Rechnen

Bei der Berechnung ist die Entropie die Zufälligkeit, die von einem Betriebssystem oder einer Anwendung zur Verwendung in der Kryptographie oder anderen Verwendungen gesammelt wird, die zufällige Daten erfordern. Diese Zufälligkeit wird oft aus Hardwarequellen, entweder vorher existierenden wie Mausbewegungen oder speziell bereitgestellten Zufälligkeitsgeneratoren, gesammelt.

Informationstheorie

In der Informationstheorie ist die Entropie ein Maß für die Unsicherheit einer Zufallsvariablen. Der Begriff selbst bezieht sich in diesem Zusammenhang üblicherweise auf die Shannon-Entropie, die im Sinne eines Erwartungswertes die in einer Nachricht enthaltene Information, meist in Einheiten wie Bits, quantifiziert. Äquivalenz ist die Shannon-Entropie ein Maß für den durchschnittlichen Informationsgehalt, den man vermisst, wenn man den Wert der Zufallsvariablen nicht kennt

Entropie bei der Datenkomprimierung

Die Entropie bei der Datenkomprimierung kann die Zufälligkeit der Daten angeben, die Sie in den Komprimierungsalgorithmus eingeben. Je größer die Entropie, desto geringer das Kompressionsverhältnis. Das heißt, je zufälliger der Text ist, desto geringer kann er komprimiert werden.

Die Shannon-Entropie stellt eine absolute Grenze für die bestmögliche verlustfreie Komprimierung jeder Kommunikation dar: Indem sie Nachrichten behandelt, die als eine Folge von unabhängigen und gleich verteilten Zufallsvariablen codiert werden sollen, zeigt Shannons Quellcodierungstheorem, dass im Grenzfall die durchschnittliche Länge der kürzesten ist Eine mögliche Darstellung, um die Nachrichten in einem gegebenen Alphabet zu codieren, ist ihre Entropie dividiert durch den Logarithmus der Anzahl der Symbole im Zielalphabet.


Ich traf immer auf Entropie im Sinne von Shannon Entropy.

Von http://en.wikipedia.org/wiki/Information_entropy :

In der Informationstheorie ist die Entropie ein Maß für die Unsicherheit einer Zufallsvariablen. Der Begriff selbst bezieht sich in diesem Zusammenhang üblicherweise auf die Shannon-Entropie, die im Sinne eines Erwartungswertes die in einer Nachricht enthaltene Information, meist in Einheiten wie Bits, quantifiziert. Äquivalenz ist die Shannon-Entropie ein Maß für den durchschnittlichen Informationsgehalt, den man vermisst, wenn man den Wert der Zufallsvariablen nicht kennt.



Entropie hat viele Bedeutungen typischerweise in der Informatik. Es hängt vom Kontext ab. In Sicherheitsentropie bedeutet, wie viel Zufall Sie platzieren, wenn Sie zum Beispiel einen privaten Schlüssel generieren, werden Sie in vielen Anwendungen aufgefordert, die Maus zu bewegen, um Entropie zu erzeugen. Dies erzeugt Entropie, indem das "menschliche" Element der Zufallszahl genommen wird und es dem Hash-Prozess des Erzeugens des Schlüssels hinzugefügt wird.

Jetzt gibt es auch eine Definition für Software Engineering von Entropie. Diese Definition steht für veralteten Code oder für Code, der von vielen Entwicklern geschrieben wurde. Wird normalerweise in Bezug darauf verwendet, wann es an der Zeit ist, Ihr Softwareprojekt umzuformen. "Der Code für dieses Projekt hat eine enorme Menge an Entropie, weil viele der Personen, die es pflegten, derzeit nicht im Projekt sind".

Hier ist eine dritte Beispielverwendung, an die ich mich auch erinnerte. Beim Thema Simulated Annealing (soweit es die Informatik betrifft) wird die Entropie beschrieben, wie viel Zerfall während der Auswertung des Algorithmus stattgefunden hat.

Ich denke, um Ihre Frage zu beantworten, gibt es keine konkrete Definition des Wortes "Entropie" außer den, die Sie in einem Wörterbuch finden können. Wie die Informatik diesen Begriff anwendet, hängt vom Kontext des verwendeten Begriffs ab und davon, auf was er angewendet wird.


In Bezug auf Kompression und Informationstheorie ist die Entropie einer Quelle die durchschnittliche Menge an Information (in Bits), die Symbole von der Quelle übertragen können. Informell gesprochen, je unwahrscheinlicher ein Symbol ist, desto überraschender ist sein Erscheinungsbild.

Wenn Ihre Quelle zwei Symbole hat, sagen wir A und B , und sie sind gleich wahrscheinlich, dann überträgt jedes Symbol die gleiche Menge an Information (ein Bit). Eine Quelle mit vier gleichwahrscheinlichen Symbolen übermittelt zwei Bits pro Symbol.

Für ein interessanteres Beispiel, wenn Ihre Quelle drei Symbole hat, A , B und C , wobei die ersten beiden doppelt so wahrscheinlich sind wie die dritte, dann ist die dritte überraschender, aber auch weniger wahrscheinlich. Es gibt eine Netto-Entropie von 1,52 für diese Quelle, wie unten berechnet.

Sie berechnen die Entropie als die "durchschnittliche Überraschung", wobei die "Überraschung" für jedes Symbol seine Wahrscheinlichkeit multipliziert mit dem negativen Binärlog der Wahrscheinlichkeit ist:

                            binary
symbol  weight  probability   log    surprise
  A        2        0.4      -1.32    0.53
  B        2        0.4      -1.32    0.53
  C        1        0.2      -2.32    0.46
total      5        1.0               1.52

Das Negativ des binären Protokolls wird (natürlich) verwendet, da Protokolle mit Werten zwischen 0 und 1 (exklusiv) negativ sind.


Super einfache Definition

Das Wort Entropie kann in einem Satz definiert werden:

"Die Menge an Informationen benötigt, um ein System zu beschreiben."

Stellen Sie sich zum Beispiel die Expansion des Universums vor: Von Anfang an wurde die gesamte Materie in einem kleinen Punkt vor dem Urknall gesammelt, so dass wir das System mit "alle Materie ist in einem Punkt" beschrieben haben könnten. Während heute wesentlich mehr Informationen benötigt werden, um das System (das Universum) zu beschreiben, müsste man alle Planetenpositionen, ihre Bewegung, was auf ihnen steht usw. beschreiben. In der Informationstheorie funktioniert die Definition auch: ZB: Je mehr Buchstaben Sie einem Passwort (dem System) hinzufügen, desto mehr Informationen werden benötigt, um das Passwort zu beschreiben. Dann können Sie es in verschiedenen Einheiten messen, zB Bits oder Zeichen, wie "Hallo" = 5 Zeichen Entropie = 40 Bit Entropie (wenn die Zeichengröße 8 Bit ist).

Daraus folgt auch, dass je mehr Informationen Sie haben, desto mehr Möglichkeiten, wie Sie diese Informationen anordnen können. Wenn Sie 40 Bits haben, gibt es 2 ^ 40 verschiedene Möglichkeiten, wie sie arrangiert werden können. Wenn wir hier Passwörter sprechen, dann ist es umso mehr möglich, die Informationen (Bits) zu arrangieren, je länger sie knacken (mit Brute-Force- oder Dictionary-Angriffen).


In einfacheren Worten definiert Entropie Zufälligkeit. Es ist mehr wie unvorhersehbares etwas ist. In mehr technischen Wörtern, "In der Berechnung ist Entropie die Zufälligkeit, die durch ein Betriebssystem oder eine Anwendung für Gebrauch in der Kryptographie oder in anderen Verwendungen gesammelt wird, die gelegentliche Daten erfordern. Diese Zufälligkeit wird oft aus Hardwarequellen, entweder vorher existierenden wie Mausbewegungen oder speziell bereitgestellten Zufälligkeitsgeneratoren, gesammelt. "Wie in Wikipedia definiert.

Man kann nun leicht die Bedeutung der Entropie in Bezug auf eine Datei als Maß dafür bestimmen, wie stark die Bytes in einer Datei gestört sind. Es gibt verschiedene Einheiten für die Definition von Entropie wie Nat, Shannon oder Hartley. Nun, die am häufigsten verwendete Einheit ist Shannon. Der Wertebereich, in dem die Entropie einer Datei nach Shannons Algorithmus liegt, ist 0 bis 8. Wenn also der Entropiewert Null ist, kann man sagen, dass das Ergebnis sicher ist. Im Gegensatz dazu, wenn der Entropiewert 8 ist, ist das Ergebnis am unvorhersehbarsten. Die Formel, die Shannon zur Messung der Zufälligkeit des Ereignisses gegeben hat, lautet:

          Entropy = ∑ pi log(1/pi)

wo ich das Ereignis mit Wahrscheinlichkeit pi bin .

Diese Gleichung ergibt immer zwischen 0 und 8.

Für weitere Informationen, gehen Sie über den Link: https://www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/



Es ist einfach, aus Entropie eine große Sache zu machen. Meiner Meinung nach ist es ein ziemlich einfaches und nützliches Konzept .

Im Grunde wird quantifiziert, was Sie im Durchschnitt von einem Ereignis lernen, wie zum Beispiel eine Münze werfen, eine Verzweigungsinstruktion machen oder ein Array indizieren.

Wie eine Vergleichsoperation in der Mitte eines Suchalgorithmus hat eine bestimmte Wahrscheinlichkeit P eine Verzweigung zu nehmen und 1-P die andere anzunehmen.

Nehmen wir an, P ist 1/2, wie es bei einer binären Suche der Fall ist. Dann, wenn Sie diesen Zweig nehmen, wissen Sie 1 Bit mehr als vorher, denn log (2/1), Basis 2, ist 1. Andererseits, wenn Sie den anderen Zweig nehmen, lernen Sie auch 1 Bit.

Um die durchschnittliche Menge an Informationen zu erhalten, die du lernen wirst, multipliziere das, was du im ersten Zweig lernst, multipliziert mit der Wahrscheinlichkeit, dass du diesen Zweig nimmst, plus dem, was du im zweiten Zweig lernst.

1/2 mal 1 bit, plus 1/2 mal 1 bit, ist 1/2 bit plus 1/2 bit oder insgesamt 1 bit entropie. Das können Sie im Durchschnitt von dieser Entscheidung erwarten.

Angenommen, Sie führen eine lineare Suche in einer Tabelle mit 1024 Einträgen durch.

Beim ersten == Test ist die Wahrscheinlichkeit von JA 1/1024, also ist die Entropie von JA bei dieser Entscheidung

1/1024 times log(1024/1)

oder 1/1024 * 10 = ungefähr 1/100 Bit.

Wenn also die Antwort JA lautet, lernen Sie 10 Bits, aber die Wahrscheinlichkeit dafür ist etwa 1 zu 1000.

Auf der anderen Seite ist NO viel wahrscheinlicher. Es ist Entropie

1023/1024 * log(1024/1023)

oder ungefähr 1 mal ungefähr Null = ungefähr Null.

Addieren Sie die zwei zusammen und im Durchschnitt werden Sie ungefähr 1/100 von einem bisschen über diese Entscheidung lernen.

Deshalb ist die lineare Suche langsam. Die Entropie (wie viel Sie erwarten können) bei jeder Entscheidung ist zu klein, da Sie 10 Bits lernen müssen, um den Eintrag in der Tabelle zu finden.


Entropie bezieht sich auf das Ausmaß, in dem eine Software gelegentlich auf der Grundlage von Kundenanforderungen umgestaltet wird, so dass die Kosten für die Neugestaltung der Software zur Erfüllung der Kundenanforderungen maximal werden.