Beziehung zwischen Rechenkomplexität und Information

11

Ich arbeite in einem rechnergestützten neurowissenschaftlichen Labor, das die gegenseitige Information zwischen Paaren oder Gruppen von Neuronen quantifiziert. Vor kurzem verlagerte der Chef seinen Fokus auf die Messung der "Komplexität der neuronalen Dynamik". Bei der Verfolgung dieser Forschungsrichtung scheinen einige Leute in meiner Gruppe "komplex" mit "hat eine hohe Entropie" gleichzusetzen.

Kann mich jemand anleiten, wie die Beziehung zwischen rechnerischer Komplexität (im Sinne von CS) und Entropie im Sinne der Informationstheorie aussieht?

Um es etwas näher zu erläutern: Maßnahmen wie die Komplexität von Lempel-Ziv scheinen mir keine gültigen Maßstäbe für die Komplexität zu sein, da sie informativ (für den Benutzer) mit dem Tragen vieler Bits in Verbindung stehen. Andere Maßnahmen wie [Causal State Splitting Reconstruction][1]sind viel weniger bekannt, haben jedoch die ansprechende Eigenschaft, dass zufällige Prozesse keine Komplexität aufweisen, da keine versteckten Zustände erforderlich sind, um einen stationären zufälligen Prozess darzustellen.

mac389
quelle
1
Könnten Sie bitte erklären, was "komplex" in Ihrem Bereich bedeutet? Bedeutet das, dass die Neuronen sinnvoll feuern oder mehr von ihnen teilnehmen?
gegen
@vs: Es gibt viele konkurrierende Definitionen für "komplex". Einige sagen, der komplexeste Prozess sei der mit der höchsten Entropie. Dies würde jedoch bedeuten, dass zufällige Prozesse komplex sind, was biologisch nicht realistisch erscheint. Trotzdem ist "sinnvolles Feuern" näher als "mehr ... teilnehmen", obwohl wahrscheinlich "sinnvoller teilnehmen" noch näher ist.
Mac389
1
Wir verstehen, dass Komplex eine größere Entropie aus unserem Bereich impliziert. Ich habe diese Frage gestellt, um zu verstehen, was Ihr Fachgebiet unter komplex versteht. "Sinnvoller teilnehmen" ist also näher. Ok. Dies ist meine Vermutung. Für mich bedeutet "sinnvoller teilnehmen", dass die Neuronen "intelligent" kommunizieren oder "eher auf Reize reagieren", um ein "bestimmtes gewünschtes Ergebnis" zu erzielen. Diese bedeutungsvolle Kommunikation wird normalerweise mit höherer Entropie oder Information in der Informationstheorie assoziiert.
vs
@vs: Es stellt sich die Frage, wie zwei die Entropie quantifizieren, wenn das Codierungsschema nicht bekannt ist und wahrscheinlich wechselt, wie es im Gehirn der Fall zu sein scheint. Die Leute haben gesagt, dass sie die gegenseitige Information zwischen einem Neuron und einem Stimulus verwendet haben, um zu quantifizieren, wie selektiv dieses Neuron für diesen Stimulus ist. Das Problem wird verwirrender, wenn man den realistischeren Fall vieler Neuronen betrachtet.
Mac389
1
@ mac389 wir können eine beliebige Anzahl von Dingen als die Komplexität eines Objekts bedeuten. Einige Beispiele sind: Kolmogorov-Komplexität (auf die Sie eine Antwort erhalten haben) und verschiedene Vorstellungen von zeitgebundener Kolmogorov-Komplexität; Wenn Sie eine Familie von Objekten unterschiedlicher Größe haben, untersuchen wir, wie viel Zeit / Raum (als Funktion der Objektgröße) ein Algorithmus benötigt, um zu erkennen, dass ein Objekt zur Klasse gehört. Sie haben hier ein ziemlich nicht triviales Modellierungsproblem, denke ich.
Sasho Nikolov

Antworten:

9

Es gibt genügend Verbindungen zwischen Informationstheorie und rechnerischer Komplexität, um einen Abschlusskurs zu verdienen, z. B. diesen: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/

Sasho Nikolov
quelle
Vielen Dank, zusammen mit einer Diskussion mit sachkundigeren Leuten, genau das habe ich gesucht.
Mac389
7

Viele Leute haben Kolmogorovs Komplexität oder seine ressourcengebundenen Varianten erwähnt, aber ich denke, etwas näher an dem, was Sie suchen, ist der Begriff der (logischen) Tiefe . Es gibt verschiedene Varianten der Tiefe, aber alle versuchen, so etwas wie das zu erreichen, wovon Sie sprechen. Insbesondere sind weder rein zufällige Zeichenfolgen noch sehr hochgeordnete / sich wiederholende Zeichenfolgen tief.

Ein Begriff von Tiefe ist intuitiv: Eine Zeichenfolge ist tief, wenn sie eine kurze Beschreibung enthält, aber die einzige Möglichkeit, die Zeichenfolge aus dieser kurzen Beschreibung zu rekonstruieren, dauert übermäßig lange. Dies ist der Begriff der Tiefe, und mehrere andere werden in [1] eingeführt und weiterentwickelt. Die andere Standardreferenz ist [2]. Ich würde mir diese ansehen und dann eine Vorwärtsreferenzsuche durchführen.

[1] L. Antunes, L. Fortnow, D. van Melkebeek, NV Vinodchandran. Computertiefe: Konzept und Anwendungen . Theoret. Comp. Sci. 354 (3): 391–404. Auch frei verfügbar auf der Webseite des Autors .

[2] CH Bennett. Logische Tiefe und physikalische Komplexität. In R. Herken (Hrsg.), The Universal Turing Machine: Eine Umfrage über ein halbes Jahrhundert, Oxford University Press, Oxford (1988), 227–257.

Joshua Grochow
quelle
Vielen Dank für diese Antwort. Die logische Tiefe scheint sehr nahe an dem zu liegen, was ich unter Komplexität verstanden habe.
Mac389
3

Das erste, was Ihnen als faszinierend in den Sinn kommt, ist die Komplexität von Kolmogorov. Ich finde es auf jeden Fall faszinierend, und da Sie es nicht erwähnt haben, dachte ich, es könnte erwähnenswert sein.

Ein allgemeinerer Ansatz zur Beantwortung dieser Frage könnte jedoch auf der Theorie der Sprachen und Automaten beruhen. Deterministische endliche Automaten sind O (n) String-Prozessoren. Das heißt, bei einer Zeichenfolge mit der Länge n verarbeiten sie die Zeichenfolge in genau n Schritten (vieles davon hängt davon ab, wie Sie deterministische endliche Automaten definieren; ein DFA erfordert jedoch sicherlich keine weiteren Schritte). Nichtdeterministische endliche Automaten erkennen dieselben Sprachen (Sätze von Zeichenfolgen) wie DFAs und können in DFAs transformiert werden. Um jedoch eine NFA auf einer sequentiellen, deterministischen Maschine zu simulieren, müssen Sie normalerweise einen baumartigen "Suchraum" untersuchen, der die Größe erhöhen kann Komplexität dramatisch. Die regulären Sprachen sind im rechnerischen Sinne nicht sehr "komplex".

Sie können auch andere Ebenen der Chomsky-Hierarchie von Sprachen betrachten - deterministisch kontextfrei, kontextfrei (einschließlich nichtdeterministischer kontextfreier Sprachen, die von deterministischen Pushdown-Automaten nicht unbedingt erkannt werden können), die kontextsensitiven Sprachen, die rekursiven und rekursiven Aufzählbare Sprachen und die unentscheidbaren Sprachen.

Verschiedene Automaten unterscheiden sich hauptsächlich in ihrem externen Speicher. dh welcher externe Speicher ist erforderlich, damit die Automaten Sprachen eines bestimmten Typs korrekt verarbeiten können. Endliche Automaten haben keinen externen Speicher; PDAs haben einen Stapel und Turing-Maschinen haben ein Band. Sie können also die Komplexität eines bestimmten Programmierproblems (das einer Sprache entspricht) so interpretieren, dass es mit der Menge oder Art des Speichers zusammenhängt, der erforderlich ist, um es zu erkennen. Wenn Sie keinen oder einen festen, begrenzten Speicherplatz benötigen, um alle Zeichenfolgen in einer Sprache zu erkennen, handelt es sich um eine reguläre Sprache. Wenn Sie nur einen Stapel benötigen, haben Sie eine kontextfreie Sprache. Usw.

Im Allgemeinen wäre ich nicht überrascht, wenn Sprachen, die in der Chomsky-Hierarchie höher sind (daher eine höhere Komplexität aufweisen), auch tendenziell eine höhere Entropie im informationstheoretischen Sinne aufweisen. Davon abgesehen könnten Sie wahrscheinlich viele Gegenbeispiele zu dieser Idee finden, und ich habe keine Ahnung, ob es überhaupt einen Wert dafür gibt.

Dies könnte auch besser beim "theoretischen cs" (cstheory) StackExchange gefragt werden.

Patrick87
quelle
Ich habe es migriert und danke für Ihren Vorschlag.
Mac389
1

Die Komplexität der Berechnungen befasst sich mit den erforderlichen Ressourcen: Welche Ressourcen (normalerweise Zeit, Raum oder beides und eine bestimmte Art von Computergerät) sind bei einem bestimmten Problemtyp und einer bestimmten Größe erforderlich, um das Problem zu lösen? Die Probleme werden dann in Komplexitätsklassen zusammengefasst.

Einige davon sind eher allgemein und abstrakt: Ist das Problem überhaupt prinzipiell lösbar? Benötigt es eine Maschine dieses oder jenes Typs? Die Einführung in diese Ideen ist immer noch ein Thema der Informatik für Hochschulabsolventen, und das Einführungsmaterial bezieht sich normalerweise auf die Chomsky-Hierarchie, die einige Arten von abstrakten Maschinen und einige Arten von abstrakten Maschinen sauber (und wunderschön!) Zusammenfasst. mathematische Sprachspezifikationen.

Einige davon auf der unteren Ebene sind im täglichen Gebrauch praktischer: Skaliert dieses Problem als Quadrat der Problemgröße, des Würfels oder einer anderen Funktion? Interessanterweise weiß ich, dass Argumente für die Entropie eines bestimmten Problems nützlich sind, um einige Untergrenzen für einige Rechenprobleme zu bestimmen. Eines, das mir in den Sinn kommt (obwohl ich es wahrscheinlich nicht wiederholen könnte, ohne ein Lehrbuch zu überprüfen), ist ein entropiebasiertes Argument für die minimal erforderliche Anzahl von Vergleichen während einer Sortierung. Die Verbindung zur Entropie erfolgt durch Informationstheorie.

Ich denke, die Idee hat einen gewissen Wert.

Novak
quelle