Związek między złożonością obliczeniową a informacją

11

Pracuję w obliczeniowym laboratorium neuronauki, które ocenia ilościowo wzajemną informację między parami lub grupami neuronów. Ostatnio szef skupił się na pomiarze „złożoności dynamiki neuronowej”. Prowadząc tę ​​linię badań, niektórzy ludzie w mojej grupie wydają się utożsamiać „kompleks” z „ma wysoką entropię”.

Czy ktoś może wskazać mi związek między złożonością obliczeniową (w sensie CS) a entropią w sensie teorii informacji?

Aby wyjaśnić nieco dalej, miary takie jak złożoność Lempela-Ziva nie wydają mi się miarodajnymi miarami złożoności, ponieważ łączą informacje (dla użytkownika) z przenoszeniem dużej ilości bitów. Inne miary, podobnie jak, [Causal State Splitting Reconstruction][1]są znacznie mniej znane, ale mają atrakcyjną właściwość, że procesy losowe mają zerową złożoność, ponieważ zero stanów ukrytych jest potrzebnych do reprezentowania stacjonarnego procesu losowego.

cc.complexity-theory it.information-theory mac389
źródło
1
Czy mógłbyś wyjaśnić, co oznacza „kompleks” w Twojej dziedzinie? Czy to znaczy, że neurony strzelają znacząco, czy więcej z nich bierze udział?
vs
@vs: Istnieje wiele konkurencyjnych definicji „złożonego”. Niektórzy twierdzą, że najbardziej złożonym procesem jest ten z najwyższą entropią. Oznaczałoby to jednak, że losowe procesy są złożone, co nie wydaje się biologicznie realistyczne. Mimo to „strzelanie sensownie” jest bliższe niż „więcej ... uczestnictwo”, chociaż prawdopodobnie „bardziej sensowne uczestnictwo” jest jeszcze bliższe.
mac389,
1
Rozumiemy, że kompleks oznacza większą entropię z naszej dziedziny. Zadałem to pytanie, aby zrozumieć, co oznacza twoje pole przez kompleks. Tak więc „bardziej znaczący udział” jest bliżej. Ok. To jest moje przypuszczenie. Dla mnie „bardziej znaczący udział” oznacza, że ​​neurony komunikują się „inteligentnie” lub „raczej reagują na bodźce” w celu „szczególnie pożądanego rezultatu”. Ta znacząca komunikacja wiąże się zwykle z wyższą entropią lub informacją w teorii informacji
porównaniu z
@vs: Pojawia się pytanie, w jaki sposób dwie kwantyfikujące entropię, gdy schemat kodowania nie jest znany i prawdopodobnie zmienia się, jak się wydaje w przypadku mózgu. Ludzie powiedzieli, że wykorzystali wzajemną informację między jednym neuronem a bodźcem, aby określić, jak selektywny jest ten neuron w stosunku do tego bodźca. Problem staje się coraz bardziej niejasny, gdy rozważamy bardziej realistyczny przypadek wielu neuronów.
mac389,
1
@ mac389 możemy rozumieć dowolną liczbę rzeczy jako złożoność obiektu. niektóre przykłady to: złożoność Kołmogorowa (na którą otrzymano odpowiedź) i różne pojęcia związanej z czasem złożoności Kołmogorowa; gdy masz rodzinę obiektów o różnych rozmiarach, sprawdzamy, ile czasu / przestrzeni (jako funkcja wielkości obiektu) wymaga algorytmu, aby rozpoznać, że obiekt należy do klasy. myślę, że masz dość nietrywialny problem z modelowaniem.
Sasho Nikolov

Odpowiedzi:

7

Wiele osób wspomniało o złożoności Kołmogorowa lub jego ograniczonych zasobach wariantach, ale myślę, że coś bliższego temu, czego szukasz, jest pojęcie (logicznej) głębi . Istnieje kilka wariantów głębokości, ale wszystkie próbują uzyskać coś takiego, o czym mówisz. W szczególności ani czysto losowe ciągi, ani bardzo wysoce uporządkowane / powtarzalne ciągi nie są głębokie.

Jedno pojęcie głębokości jest intuicyjne: łańcuch jest głęboki, jeśli ma krótki opis, ale jedyny sposób na odtworzenie łańcucha na podstawie tego krótkiego opisu zajmuje nadmiernie dużo czasu. Jest to pojęcie głębi, a kilka innych zostało wprowadzonych i rozwiniętych w [1]. Drugim standardowym odniesieniem jest [2]. Spojrzałbym na te, a następnie przeszukałem referencje.

[1] L. Antunes, L. Fortnow, D. van Melkebeek, NV Vinodchandran. Głębokość obliczeniowa: koncepcja i zastosowania . Teoretyczna Komp. Sci. 354 (3): 391--404. Dostępne również bezpłatnie ze strony autora .

[2] CH Bennett. Logiczna głębia i złożoność fizyczna. W R. Herken (red.), The Universal Turing Machine: A Half-Century Survey, Oxford University Press, Oxford (1988), 227–257.

Joshua Grochow
źródło
Dziękuję bardzo za tę odpowiedź. Logiczna głębia wydaje się być bardzo zbliżona do tego, co miałem na myśli przez złożoność.
mac389
3

Pierwszą rzeczą, która wydaje się fascynująca, jest złożoność Kołmogorowa; Z pewnością uważam to za fascynujące, a skoro o tym nie wspomniałeś, pomyślałem, że warto o tym wspomnieć.

To powiedziawszy, bardziej ogólne podejście do odpowiedzi na to pytanie może opierać się na teorii języków i automatów. Deterministyczne automaty skończone są procesorami łańcuchowymi O (n). To znaczy, biorąc pod uwagę ciąg o długości n, przetwarzają go dokładnie w krokach n (wiele z tego zależy od tego, jak dokładnie zdefiniujesz deterministyczne automaty skończone; jednak DFA z pewnością nie wymaga więcej kroków). Automaty skończone niedeterministyczne rozpoznają te same języki (zestawy ciągów) co DFA i mogą być przekształcane w DFA, ale aby symulować NFA na sekwencyjnej, deterministycznej maszynie, musisz zazwyczaj eksplorować drzewiastą „przestrzeń wyszukiwania”, która może zwiększyć złożoność dramatycznie. Zwykłe języki nie są zbyt „złożone” w sensie obliczeniowym,

Możesz podobnie spojrzeć na inne poziomy hierarchii języków Chomsky'ego - deterministyczne kontekstowe, bezkontekstowe (w tym niedeterministyczne języki kontekstowe, które niekoniecznie mogą być rozpoznane przez deterministyczne automaty wypychające), języki kontekstowe, rekurencyjne i rekurencyjne języki wyliczalne i nierozstrzygalne.

Różne automaty różnią się przede wszystkim pamięcią zewnętrzną; tzn. jaka pamięć zewnętrzna jest niezbędna, aby automaty poprawnie przetwarzały języki określonego typu. Automaty skończone nie mają pamięci zewnętrznej; Urządzenia PDA mają stos, a maszyny Turinga mają taśmę. W ten sposób można zinterpretować złożoność konkretnego problemu programistycznego (odpowiadającego językowi), aby był powiązany z ilością lub rodzajem pamięci wymaganej do jego rozpoznania. Jeśli nie potrzebujesz żadnej lub określonej, skończonej ilości miejsca do rozpoznania wszystkich ciągów w języku, jest to zwykły język. Jeśli wszystko, czego potrzebujesz, to stos, masz język bezkontekstowy. Itp.

Zasadniczo nie zdziwiłbym się, gdyby języki wyższe w hierarchii Chomsky'ego (stąd o większej złożoności) również miałyby wyższą entropię w sensie teoretycznym. To powiedziawszy, prawdopodobnie można znaleźć wiele kontrprzykładów dla tego pomysłu, a ja nie mam pojęcia, czy ma to jakąkolwiek wartość.

Można to również lepiej zadać na „teoretycznej cs” (cstheory) StackExchange.

Patrick87
źródło
Migrowałem to i dziękuję za twoją sugestię.
mac389,
1

Złożoność obliczeniowa odnosi się do niezbędnych zasobów: Biorąc pod uwagę konkretny typ problemu, o danym rozmiarze, jakie zasoby są niezbędne (zwykle czas, przestrzeń lub jedno i drugie oraz określony typ urządzenia komputerowego), aby go rozwiązać. Problemy są następnie grupowane w „klasy” złożoności.

Niektóre z nich są raczej ogólne i abstrakcyjne: czy problem w ogóle można rozwiązać, nawet w zasadzie? Czy wymaga maszyny tego typu, czy tamtejszej? Wprowadzenie do tych pomysłów jest nadal tematem informatyki na poziomie magisterskim, a materiał wprowadzający zwykle nawiązuje do hierarchii Chomsky'ego, która starannie (i pięknie!) Odwzorowuje kilka rodzajów abstrakcyjnych maszyn i kilka rodzajów abstrakcyjnych, specyfikacje języka matematycznego.

Niektóre z nich, na niższym poziomie, są bardziej praktyczne w codziennym użytkowaniu: Czy ten problem skaluje się jako kwadrat wielkości problemu, kostki lub innej funkcji? Co ciekawe, wiem, że argumenty za entropią danego problemu okazały się przydatne w określaniu niektórych dolnych granic niektórych problemów obliczeniowych. Ten, który pojawia się w moim umyśle (chociaż prawdopodobnie nie mógłbym go powtórzyć bez sprawdzenia podręcznika), jest argumentem opartym na entropii dla minimalnej niezbędnej liczby porównań podczas sortowania. Połączenie z entropią odbywa się poprzez teorię informacji.

Myślę, że ten pomysł ma pewne zalety.

Novak
źródło