Нейросети полны по Тьюрингу?

[Sonic86]

Хайкин Нейронные сети, 2-е изд. п.1.9. Историческая справка писал(а):

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

Я правильно понимаю, автор утверждает, что нейросети полны по Тьюрингу? Погуглил - ничего такого сразу не нашел. Можете дать ссылку на строгую формулировку такого утверждения?

[mihaild]

Видимо, имеется в виду http://www.raai.org/library/books/mccul ... ulloch.pdf, формулировки вроде бы строгие, но какая-то своя терминология, в которой надо разбираться.
Есть еще скажем такой http://binds.cs.umass.edu/papers/1992_S ... n_COLT.pdf результат - линейные рекуррентные нейросети с рациональными весами способны вычислить любую вычислимую функцию (получают на вход сначала вход МТ, потом нули; выдают сначала нули, потом ответ, потом опять нули).

[grizzly]

В лекциях Дж. фон Неймана "Теория самовоспроизводящихся автоматов", перевод в издательстве "Мир" 1971 г. (гуглится) в начале стр. 65 можно найти что-то уж очень похожее про отзывы Неймана об их работе (плюс небольшие окрестности): "общность нейронной сети точно такая же, как общность логики". Или: "если такую сеть снабдить бесконечной лентой, то получится машина Тьюринга".

-- 13.12.2017, 00:04 --

(Оффтоп)

mihaild
Поделитесь, пожалуйста, как нашли оригинал той старой работы. Я его не смог сколько-то быстро найти.

[mihaild]

(Оффтоп)

Запрос "Мак-Каллок и Питц" в яндексе, вторая ссылка. (только это не оригинал, это перевод)

[Sonic86]

mihaild, благодарю!
Статью Маккаллока и Питца я, к сожалению, ниасилил - там все очень странное.

(подробности)

mihaild в сообщении #1274470 писал(а):

Видимо, имеется в виду http://www.raai.org/library/books/mccul ... ulloch.pdf, формулировки вроде бы строгие, но какая-то своя терминология, в которой надо разбираться.

Почитал, но не помогло.
Вообще я уже знаю, что есть нейронные сети с циклами и без циклов. Если сеть без циклов, то там мне все понятно. В главе II там как раз описываются сети без циклов и, насколько я понял, там просто устанавливается соответствие между булевыми функциями и нейронными сетями. Это все понятно, но эмуляция расчета булевой функции, по-моему, решительно неинтересна и отношения к полноте по Тьюрингу не имеет.
А вот в главе III про сети с циклами я уже ничего не понимаю. Я не вижу там соответствующего утверждения. Вижу теорему 10, в ней вижу утверждение о вычислимости $(\exists z_2)z_1\wedge Pr_1(z_2)$. Но $Pr_1$ - это предикат задаваемый нейросетью, а изначально неизвестно, могут ли нейросети выразить все вычислимые предикаты. Кроме того, я не знаю, верно ли, что из вычислимости предикатов вида $(\exists x)P(x)$ для произвольного $P$ следует полнота по Тьюрингу - я такого не читал нигде
(и вообще там в тексте часто происходит syntax error - индекс $i$ вечно исчезает, а вычислимые числа - это какое-то нечто)

mihaild в сообщении #1274470 писал(а):

Есть еще скажем такой http://binds.cs.umass.edu/papers/1992_S ... n_COLT.pdf результат - линейные рекуррентные нейросети с рациональными весами способны вычислить любую вычислимую функцию (получают на вход сначала вход МТ, потом нули; выдают сначала нули, потом ответ, потом опять нули).

Еще читаю, но правдоподобно, кроме того, автор рассматривает и другие варианты.
В целом, ситуация для меня представляется такой:
1. Самые простые нейросети (с целыми весами, с функцией Хэвисайда в качестве активационной, потенциально с циклами) равносильны конечным машинам в смысле Минского и "распознают" только регулярные языки

Минский Вычисления. Конечные и бесконечные машины, 2.6. писал(а):

Теорема. Никакая фиксированная машина с конечным числом состояний не может перемнодать пары двоичных чисел с произвольно большим числом разрядов

Минский Вычисления. Конечные и бесконечные машины, 3.5. писал(а):

Очевидно, что всякая нейронная сеть рассмотренного нами вида является конечной машиной

2. Для увеличения вычислительной силы надо усложнять нейросеть: добавлять бесконечные ленты, усложнять активационную функцию нейронов (во 2-й статье до $\sigma(x)=[0\leqslant x\leqslant 1]x+[x\geqslant 1]$), давать возможность динамически увеличивать число нейронов, давать возможность вычислять/различать действительные числа и т.п.. Причем усложнения эти обычно нетривиальны (например, надо не просто дать нейросети бесконечную ленту для записи, еще надо поработать над тем, как оттуда читать и как туда что-то писать)

(про входы, выходы и остановку)

Нейросеть, в отличие от МТ, не может ходить по ленте туда-сюда, "обычно она ходит только в одну сторону", нейросеть работает без остановки, так что непонятно, когда она "остановилась" в смысле МТ, а когда - "зациклилась"

3. Утверждение о полноте по Тьюрингу для нейросетей не особо тривиально, его пока нет в учебной литературе, оно разное для разных классов сетей.
4. В данном случае возможность манипуляции с неограниченным количеством информации берется из работы с рациональными числами - автор кодирует двоичные последовательности $a_k$ рациональными числами вида $\sum\limits_{k=1}^n\frac{(2a_k+1)}{4^k}$, а потом, видимо, передает их с помощью передаточной функции $\sigma$

(таблица)

У автора статьи есть хорошая табличка:

$$ \begin{pmatrix} \text{weights} & \text{recognition power}\\ \mathbb{Z}& \text{regular}\\ \mathbb{Q}& \text{recursive}\\ \mathbb{R}& \text{arbitrary}\\ \end{pmatrix} $$

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

[mihaild]

Sonic86 в сообщении #1275058 писал(а):

Интересно, как обстоит дело в "реальных" нейросетях?

Если на практике вычисления с произвольной точностью и используются, то я про это не слышал. Скорее всего редко, потому что их сложно делать быстро, а для обучения нейросетей надо очень быстро перемножать много матриц среднего размера. Плюс стандартный градиентный спуск не выглядит подходящим инструментом для оптимизации параметров произвольной точности.

Зато видел статью от DeepMind (вроде) про обучение нейросетей с использованием того, что умножение вещественного числа на константу на реальном железе - не линейная операция:)

Ну и понятно, что реальная даже рекуррентная нейросеть (вроде LSTM) - это трансдьюсер. Так что чтобы вычислять что-то сложное ей нужна внешняя память в каком-то смысле.

[Sonic86]

Понятно.

Остался один вопрос выше, я его явно не задал:

Sonic86 в сообщении #1275058 писал(а):

В целом, ситуация для меня представляется такой: 1,2,3,4

Я все правильно понял, да?