продолжение. начало тут.

1️⃣ Я расскажу о теории вычислимости и сложности вычислений + сделаю краткий обзор того, что известно о вычислительной мощности рекуррентных нейронных сетей.

2️⃣ Никита — про математику и биологию: введение в нейронауку и обсуждение первых глав книги Peter Dayan Theoretical Neuroscience.

3️⃣ Завершим философией — открытая дискуссия и дебаты. Можете заранее формулировать вопросы!

Очень ждём на стрим также работника в области математики и криптографии -- Диму Топчего (например)

И, конечно же, вас ждут сюрпризы:

Сюрприз от Никиты: он про очень крутую свежую статью в области расскажет! 🔥

Сюрприз от меня: я подофигел вообще от обьёма того что мне прийдётся в воскресенье представить в удобоворимом виде кратко, просто сижу и готовлюсь и не знаю как успеть! до воскресенья вы от меня не увидите больше ни одного сообщения! 😂


#LiveStream

напоминаю, сегодня стрим в канале https://t.iss.one/hidden_heuristic.

начало в 13:00 по немецкому времени, в 14:00 по Киеву/Москве

Какая-то техническая заминка с началом стрима. Момент

🎥 Стрим длиной 3.5 часа подошёл к концу — было очень интересно и насыщенно!

Кто не пришёл — кусайте локти. Но аккуратно: запись будет. Хотя кусайте всё равно, потому что часть стрима не записалась 😅

📚 Были две основные презентации:
— от меня: краткое введение в теорию вычисломости/сложности вычислений + разбор одного результата про вычилительную мощность рекуррентных нейронных сетей 🧮
— от Никиты: введение в теоретическую нейронауку -- матаппарат нейробиологов 🧠

🧠 Кроме того, Дима сделал мини-презентацию со своим видением решения задачи тысячелетия: P ≠ (?) NP.

🔥 Было много вопросов, комментариев и обсуждений — спасибо всем, кто участвовал!

💬 Также получилась живая дискуссия о практическом значении задачи P ≠ (?) NP — спасибо Диме и Владимиру за мысли!

📅 Планируем продолжать такие стримы и дальше — углубляться в пересечения математики, IT и нейронаук. Stay tuned!🧮

#LiveStream

Друзья, накидывайте темы и направления на следующие стримы. Вот один вариант предложенный Никитой 👇👇👇

Видео этого стрима будет в нарезках по темам через какое-то количество дней. Но уже думаем над следующими стримами. Кому интересно что-то рассказать, представить, узнать, обсудить - пишите!

Вводная статья об AIXI - определение "универсального интеллекта" в theorethical computer science:
https://arxiv.org/abs/0712.3329v1

Для чего это нужно?
Условно закрыть философский гештальт: «а что такое интеллект в самом общем смысле?»

Сегодня на стриме Дмитрий, в частности, показал, что RNN могут в теории эмулировать произвольную машину Тьюринга. Я вижу, конечно, с этим проблему в том, что на практике вы никогда не получите веса связей из множества Кантора с желаемой точностью. Результат интересный, но для практического описания реальных возможностей ИИ не подходит.

Популярно об AIXI еще можно почитать в книге Сбербанка, смотрите комментарий к посту)

🎥 Начинаем выкладывать по маленьким кусочкам записи стрима от 11 мая — "Complexity Theory meets Neuroscience".

Если пропустили в прямом эфире или хотите пересмотреть отдельные моменты — самое время!

Самое начало стрима 👆👆👆

Stay tuned 🧠⚡

#LiveStream #PureMath #AppliedMath #Complexity #Neurscience

🎥 Хайлайты лайв-стрима от 11 мая — "Complexity Theory meets Neuroscience".

Дима очень кратко и чётко рассказывает о своём видении решения задачи тысячелетия: P ≠ (?) NP. Владимир вносит несколько важных уточнений касаемо практической значимости строгого математического доказательства этой фундаментальной проблемы. Завязывается дискуссия и дебаты, но в итоге ребята приходят к консенсусу! Так же затронута тема квантовых вычислений и мостик между квантовыми алгоритмами и классической теорией сложности алгоритмов.👆👆👆

Продолжение следует! Stay tuned 🧠⚡

#LiveStream #Complexity #PvsNP #QuantumComputing

Кто не все понял в этом видео 👆 - не расстраивайтесь. Скоро будут нарезки из стрима с введением в эти темы.

AIXI - гипотетический идеал Искусственного Общего Интеллекта (Artificial General Intelligence - AGI).

❓Кто умнее — вы или AGI?

Представьте, что вы проходите тест на IQ и вам нужно продолжить числовой ряд: 2, 4, 6, 8, …

Первый инстинкт — ответить «10». Но что, если я скажу, что этот ряд также удовлетворяет сложному полиному:
2k⁴ − 20k³ + 70k² − 98k + 48, согласно которому следующее число в последовательности 58, а не 10!

Как же понять, какое продолжение правильное?

Вот тут на помощь приходит принцип бритвы Оккама из философии — выбор самого простого и краткого объяснения (или алгоритма), которое описывает данные.

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

AIXI использует именно такой подход: он ищет самый короткий алгоритм, который объясняет наблюдаемые данные, и на его основе делает прогнозы — он выбирает наиболее вероятную, простую и универсальную модель мира.

продолжение тут 👇👇👇

Продолжение. Начало тут 👆.

Как работает AIXI?

AIXI просматривает все возможные вычислимые модели мира и взвешивает их по вероятности, отдавая предпочтение тем, что имеют меньшую колмогоровскую сложность — проще говоря, выбирает "самую лаконичную правду".

Почему AIXI не существует на практике?

Главная проблема — невычислимость. Соломоновская индукция, лежащая в основе AIXI, теоретически оптимальна, но невозможно вычислить её точно на реальном компьютере. Это связано с тем, что поиск по всем возможным программам бесконечен и слишком затратен по ресурсам — ни один компьютер не сможет просмотреть и оценить все варианты.

Это можно сравнить с задачей поиска иголки в бесконечном стоге сена.

В результате, AIXI — это идеал, математическая модель, к которой стремятся многие алгоритмы ИИ, но которую невозможно реализовать полностью.

Зачем тогда изучать AIXI?

Потому что он задаёт эталон, к которому можно стремиться. Современные алгоритмы машинного обучения и ИИ — это приближения к AIXI. Чем больше у них ресурсов, тем лучше они могут выбирать модели и делать прогнозы.

Понимание AIXI помогает понять фундаментальные ограничения и возможности искусственного интеллекта и понять, что значит интеллект в принципе.

🧠 И вот где прикол:
Число 10 — это логичное продолжение самой простой гипотезы: шаг +2.

Но! Также можно построить много других гипотез, например:

Полином 𝑎(𝑘)=2𝑘⁴ − 20𝑘³ + 70𝑘² − 98𝑘 + 48. Он тоже даёт значения: 2, 4, 6, 8 при 𝑘=1,2,3,4, но на 𝑘=5 даёт 58.

AIXI не "предпочитает" 58, он говорит: все гипотезы возможны, но каждая имеет свою вероятность.

❓Так кто умнее?
Человек, отвечая "10", опирается на контекст и социальное ожидание от задачи.

AGI, построенный по принципу AIXI, не имеет контекста, он математически оценивает вероятности всех гипотез — и выдаёт взвешенное предсказание на основе всех возможных алгоритмов, в том числе и "неинтуитивных".

@easy_about_complex

#AGI #AIXI #Solomonoff

Продолжем выкладывать нарезки стрима „Complexity Theory meets Neuroscience“ от 11.05.2025.

Начало краткого неформального введения в теорию сложности, для тех, кто не совсем понял о чём тут говорят Дмитрий и Владимир.

Продолжение следует! Stay tuned 🧠⚡

#LiveStream #Complexity #Introduction #PvsNP

1/3
При дворе короля Артура жили 150 рыцарей и 150 дам.

«Почему бы не создать 150 супружеских пар?» — размышлял король, и мысль немедленно была претворена в действие. Он поручил Королевскому Секретному Агенту (Royal Secret Agent = RSA) составить диаграмму, включающую все 300 имён, указывая красной линией взаимный интерес между дамой и рыцарем, а при его отсутствии — синей линией. Диаграмма с 150² = 22 500 цветными линиями выглядела довольно запутанно, но не настолько, чтобы запутать Мерлина, придворного мага, которому Артур передал её с чётким приказом: найти совершенное соответствие между дамами и рыцарями (по взаимной любви).

Мерлин удалился, посмотрел на диаграмму и,благодаря своему безграничному интеллекту, мгновенно понял, что ни одна из 150!(≈5×10^262) возможных пар не даёт полностью красного соответствия. Он быстро перебрал все 5×10^262 диаграмм, выделив в каждой ошибочную линию, и приказал слугам отнести их в тронный зал как доказательство того, что Артур потребовал невозможного.
Продолжение👇

2/3. Начало тут 👆

Разумеется, даже малая часть этих диаграмм не могла поместиться в зале, но Артур не стал даже дожидаться, пока зал наполнится. Он отклонил метод Мерлина («очевидно, ты что-то упустил») и приказал ему вернуться с решением на следующий день. Дневники Артура раскрывают ещё одну мысль, которая его тогда занимала:
«Жизни Вселенной не хватит, чтобы проверить всю эту ерунду. Старый лис хочет обмануть меня.»

Мерлин знал, что прав, и также знал, что Артур — человек разумный. Всё, что ему оставалось — убедить его за пять минут, что решения не существует.

По счастливой случайности, в столовой он наткнулся на скромного человека в новеньких синих джинсах. Это был гость из Восточного блока, который скромно представился как Дьенеш Кёниг, номер один среди экспертов по идеальным соответствиям. «Вас, возможно, заинтересует моя мини-макс теория?»
Найдя наконец внимательного слушателя, гость забыл про картошку фри и бесплатный кетчуп, и начал с энтузиазмом читать лекцию о двудольных графах, максимальных соответствиях и минимальных покрытиях. Мерлина ничуть не смущал ни сильный акцент, ни размашистые жесты. Вскоре Мерлин понял, что всё, что ему нужно чтобы убедить Артура в невозможности переженить всех рыцарей и дам по взаимной любви — это найти препятствие Кёнига: множество из k рыцарей, каждый из которых интересуется лишь (k − 1) дамами.

Мерлин тут же увидел, что такое препятствие действительно существует (при k = 79). С помощью не слишком гениального, но довольно надёжного придворного астронома, Артур быстро убедился, что группа из 79 рыцарей действительно представляет собой препятствие Кёнига. Таким образом убедившись в правоте Мерлина, Артур смирился с невозможностью найти совершенное соответствие и начал искать другие пути для улучшения общества.

Продолжение тут 👇

3/3. Предыдущая часть 👆

Летописи свидетельствуют, что Мерлин недолго ждал следующего поручения.

Одним из нововведений Артура было внедрение вилок. Когда за Круглым Столом накрывали ужин, благородным рыцарям предлагалось оставить мечи и занять отведённые места. Некоторые с удовольствием поедали сочные бараньи ножки, легко доставаемые с помощью прочных вилок. Однако другие быстро нашли более «рыцарское» применение новым приборам и без промедления начали сводить счёты с соседями.

Артуру показалось, что манеры за столом можно было бы значительно улучшить с правильной рассадкой рыцарей. Как и прежде, он вызвал RSA (Royal Secret Agent), который составил граф, показывающий, кто с кем сможет сидеть мирно. Задача найти подходящую рассадку (то, что позже назовут гамильтоновым циклом в графе) снова была поручена Мерлину.

Когда Мерлин понял, что решения нет, он больше не стал прибегать к трюку с 150! диаграммами — он просто написал Кёнигу. Но либо почта шла слишком медленна, либо возникло другое препятствие — ответа Кёнига на это письмо так и не поступило. Не сумев представить решение в установленный срок, Мерлин был приговорён к виселице. Однако приговор был немедленно заменён на «вечность в темнице с возможностью условного освобождения после отбытия одной трети срока».

(c) László Babai
🔗 Источник: László Babai "E-mail and the unexpected power of interaction"

Это была наша новая рубрика #ВГостяхУСказки, а так же подводка к следующему посту про класс сложности IP (интерактивные доказательства - маг Мерлин с безграничными интеллектуальными возможностями и полиномиальный король Артур), а так же про удивительное доказательство теоремы IP=PSPACE.

#Complexity #IP #PSPACE #IPvsPSPACE

🏃‍♂️🏞️ 18.05, 14:00, Побегаем в Олимпиапарке, без фанатизма!

Друзья из Мюнхена (и окрестностей), кто хочет размяться и встряхнуться — собираемся завтра 18.05, в воскресенье, 14:00 в Олимпиапарке!

📏 Дистанция — примерно 9-10 км
📈 Перепад высоты — около 140 м (по ощущениям — чуть меньше 😄)
⏱️ Время в пути — ~1 час, но каждый бежит в своём темпе. Можно и пешком, можно и с паузами на болтовню и фоточки 📸

Формат супер-лайтовый! Это не чемпионат и не страдание, а скорее дружеская пробежка с видом на горки и весенний вайб 🌸

Оставьте коммент - договоримся где именно там встретимся.

#running #sport #olympiapark #munich

1/2

🔮 Возвращение Мерлина
IP = PSPACE и освобождение мага

Как вы, дорогие друзья, помните из этого поста, маг Мерлин был приговорён к заточению за то, что не смог за полиномиальное время убедить короля Артура в неразрешимости определённой задачи рассадки рыцарей за круглым столом.

Века шли в сером однообразии. Единственными радостями Мерлина были щебетание птиц у окна и редкие письма по электронной почте. Он продолжал заниматься теорией сложности, читал форумы по TCS и в какой-то момент осознал, что если NP ≠ coNP, то, возможно, он никогда не сможет убедить Артура.

Так было до 26 декабря 1989 года.

Рождество только что закончилось,
был четвертый день Хануки. Мерлин, как обычно, дремал днём, а проснувшись — проверил почту.

💥 На экране мигал заголовок письма из Израиля:

From: shamir%[email protected]
Subject: IP = PSPACE

📜 В этом кратком письме заключалась крутая идея: Ади Шамир показал, что весь класс PSPACE поддаётся проверке с помощью интерактивных доказательств.

Продолжение 👇👇👇

2/2. Продолжение. Начало тут 👆

Почему это важно? Во-первых, этот реультат контр-интуитивный. Считалось, что класс IP это где-то между NP и PSPACE, чуть больше NP, но и близко не дотягивает до PSPACE.

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

Артур может быть убеждён в любых вещах уровня PSPACE (а это мощный класс задач, например, шахматы), если общается с могучим доказывающим (Мерлин). Это радикально изменило понимание того, насколько мощными могут быть системы доказательств, даже с очень ограниченным проверяющим.

С опорой на классическую PSPACE-полноту задачи верификации кванторной булевой формулы (QBF), Шамир дал то, чего Мерлину так не хватало — мощный, вероятностный протокол убеждения. И у Мерлина появился шанс снова оказаться на свободе.

🖨️ Пока старенький принтер печатал короткий документ, Мерлин завершил вычисления и написал письмо Артуру:

Дата: 26 дек 89, 19:42:14 BST
От: merlin@cave
Кому: arthur

Сир,
в отдельном сообщении я отправляю вам
матрицу M порядка 103 680 300 с элементами
из множества {-1, 0, 1, 2, 3}. Со ссылкой на
L.G. Valiant, TCS 8 (1979), стр. 189–201,
вы без труда убедитесь, что перманент
матрицы M равен 2^{43 200 000}, умноженному
на количество гамильтоновых циклов в
«графе рассадки».

Дайте знать, когда у вас будет время
на полиномиальные вычисления.
С вероятностью 1 - 2^{-1000}
я уверю вас, что этот перманент равен нулю.

Освежите свои знания по линейной алгебре, правилу Горнера, и держите игральные кости наготове.

С уважением,
Мерлин

P.S. Спасибо за подключение к сети.
P.P.S. Что касается компенсации — мне хватит позиции в университете Чикаго.

📍Теперь Мерлин держит путь к Новому Свету. Сначала — Йель (он знал кого-то в тех краях), потом — Великие озёра (Great Lakes).

🍀 Пожелаем ему попутного ветра и продуктивных интеракций.

🔗 Источник: László Babai "E-mail and the unexpected power of interaction"

@easy_about_complex

#ВГостяхУСказки #Complexity #IP #PSPACE #IPvsPSPACE