Связь между вычислительной сложностью и информацией

11

Я работаю в вычислительной нейробиологической лаборатории, которая количественно оценивает взаимную информацию между парами или группами нейронов. Недавно босс его сместил акцент на измерение «сложности нейронной динамики». Продолжая эту линию исследований, некоторые люди в моей группе, по-видимому, приравнивают «сложный» к «имеет высокую энтропию».

Кто-нибудь может подсказать мне, какова связь между вычислительной сложностью (в смысле CS) и энтропией в смысле теории информации?

Чтобы пояснить чуть-чуть, такие меры, как сложность Лемпеля-Зива, не кажутся мне допустимыми мерами сложности, поскольку они связывают информативность (для пользователя) с переносом большого количества битов. Другие меры, такие как [Causal State Splitting Reconstruction][1], намного менее известны, но обладают привлекательным свойством, что случайные процессы имеют нулевую сложность, потому что для представления стационарного случайного процесса необходимы нулевые скрытые состояния.

mac389
источник
1
Не могли бы вы объяснить, что означает «сложный» в вашей области? Означает ли это, что нейроны многократно запускаются или в них участвует больше?
против
@vs: есть много конкурирующих определений для "сложного". Некоторые говорят, что самый сложный процесс - это процесс с самой высокой энтропией. Это, однако, подразумевает, что случайные процессы являются сложными, что не кажется биологически реалистичным. Даже в этом случае «значимое увольнение» ближе, чем «более ... участие», хотя, вероятно, «более значимое участие» еще ближе.
mac389
1
Мы понимаем, что комплекс подразумевает большую энтропию из нашей области. Я задал этот вопрос, чтобы понять, что ваше поле означает под комплексом. Итак, «более значимое участие» ближе. Хорошо. Это мое предположение. Для меня «более значимое участие» подразумевает, что нейроны общаются «разумно» или «скорее реагируют на стимулы» для «конкретного желаемого результата». Это значимое общение ». обычно ассоциируется с более высокой энтропией или информацией в теории информации
против
@vs: Существует вопрос о том, как два количественных показателя энтропии, когда схема кодирования не известна и, вероятно, переключается, как, кажется, имеет место в мозге. Люди говорили, что использовали взаимную информацию между одним нейроном и стимулом, чтобы определить, насколько избирателен этот нейрон для этого стимула. Проблема становится более запутанной, когда рассматривается более реалистичный случай многих нейронов.
mac389
1
@ mac389 мы можем подразумевать любое количество вещей как сложность объекта. Вот некоторые примеры: колмогоровская сложность (на которую вы получили ответ) и различные понятия ограниченной по Колмогорову сложности; когда у вас есть семейство объектов разных размеров, мы смотрим, сколько времени / пространства (как функция размера объекта) требует алгоритм, чтобы распознать, что объект принадлежит классу. я думаю, у вас есть довольно нетривиальная проблема моделирования.
Сашо Николов

Ответы:

9

Существует достаточно связей между теорией информации и вычислительной сложностью, чтобы заслужить выпускников, например, этот: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/

Сашо Николов
источник
Спасибо, вместе с обсуждением с более знающими людьми, это именно то, что я искал.
mac389
7

Многие люди упоминали сложность Колмогорова или его ограниченные ресурсами варианты, но я думаю, что кое-что ближе к тому, что вы ищете, это понятие (логическая) глубина . Есть несколько вариантов по глубине, но все они пытаются понять, о чем вы говорите. В частности, ни чисто случайные строки, ни очень высоко упорядоченные / повторяющиеся строки не являются глубокими.

Одно понятие глубины интуитивно понятно: строка глубока, если у нее короткое описание, но единственный способ восстановить строку из этого короткого описания занимает непомерное количество времени. Это понятие глубины, и некоторые другие введены и развиты в [1]. Другая стандартная ссылка - [2]. Я бы посмотрел на них, а затем сделал бы прямой поиск ссылок.

[1] Л. Антунес, Л. Фортнов, Д. ван Мелкебек, Н. В. Винодчандран. Глубина вычислений: концепция и приложения . ТМФ. Комп. Sci. 354 (3): 391--404. Также доступно бесплатно с сайта автора .

[2] СН Беннетт. Логическая глубина и физическая сложность. В работе Р. Херкена (ред.), «Универсальная машина Тьюринга: обзор полвека», издательство Оксфордского университета, Оксфорд (1988), 227–257.

Джошуа Грохов
источник
Большое спасибо за этот ответ. Логическая глубина, кажется, очень близка к тому, что я имел в виду под сложностью.
mac389
3

Первое, что приходит на ум как нечто, что может показаться вам увлекательным, - это колмогоровская сложность; Я, конечно, нахожу это захватывающим, и, так как вы не упомянули об этом, я подумал, что стоит упомянуть.

При этом более общий подход к ответу на этот вопрос может быть основан на теории языков и автоматов. Детерминированные конечные автоматы - это O (n) строковых процессоров. То есть, учитывая строку длины n, они обрабатывают строку ровно за n шагов (многое из этого зависит от того, как именно вы определяете детерминированные конечные автоматы; однако DFA определенно не требует дополнительных шагов). Неопределенные конечные автоматы распознают те же языки (наборы строк), что и DFA, и могут быть преобразованы в DFA, но для моделирования NFA на последовательной, детерминированной машине обычно необходимо исследовать древовидное «пространство поиска», которое может увеличить сложность резко. Обычные языки не очень «сложны» в вычислительном смысле,

Вы можете аналогичным образом взглянуть на другие уровни иерархии языков Хомского - детерминированные контекстно-свободные, контекстно-свободные (в том числе недетерминированные контекстно-свободные языки, которые не всегда могут быть распознаны детерминированными автоматами), контекстно-зависимые языки, рекурсивные и рекурсивные перечисляемые языки и неразрешимые языки.

Разные автоматы отличаются прежде всего внешним хранилищем; то есть, какое внешнее хранилище необходимо для автоматов для правильной обработки языков определенного типа. Конечные автоматы не имеют внешнего хранилища; КПК имеют стек, а машины Тьюринга - ленту. Таким образом, вы можете интерпретировать сложность конкретной проблемы программирования (которая соответствует языку), которая связана с объемом или типом памяти, необходимой для ее распознавания. Если вам не требуется фиксированный или ограниченный объем памяти для распознавания всех строк на языке, это обычный язык. Если вам нужен только стек, у вас есть язык без контекста. И т.п.

В общем, я не удивлюсь, если языки выше в иерархии Хомского (следовательно, с более высокой сложностью) также будут иметь более высокую энтропию в теоретико-информационном смысле. При этом, вы, вероятно, могли бы найти множество контрпримеров к этой идее, и я понятия не имею, есть ли в этом какое-то преимущество.

Кроме того, это может быть лучше спросить на «теоретической cs» (cstheory) StackExchange.

Patrick87
источник
Я перенес это и спасибо за ваше предложение.
mac389
1

Сложность вычислений обращается к необходимым ресурсам: учитывая конкретный тип проблемы, некоторого заданного размера, какие ресурсы необходимы (обычно время, пространство или оба; и определенный тип вычислительного устройства) для ее решения. Задачи затем объединяются в «классы» сложности.

Некоторые из них носят общий и абстрактный характер: разрешима ли проблема вообще, даже в принципе? Требуется ли машина такого типа или что? Введение в эти идеи все еще остается темой информатики для выпускников, и во вводном материале обычно упоминается иерархия Хомского, которая аккуратно (и красиво!) Отображает вместе несколько типов абстрактных машин и несколько типов абстрактных, математические спецификации языка.

Некоторые из них на более низком уровне более практичны в повседневном использовании: масштабируется ли эта задача как квадрат размера задачи, или куб, или какая-то другая функция? Интересно, что я знаю, что аргументы в пользу энтропии данной проблемы оказались полезными при определении некоторых нижних оценок для некоторых вычислительных задач. Один из них, который мне запомнился (хотя я, вероятно, не мог бы повторить это, не проверив учебник), является основанным на энтропии аргументом для минимально необходимого количества сравнений во время сортировки. Связь с энтропией через теорию информации.

Так что в этой идее есть смысл, я думаю.

Новак
источник