kaipa: (Default)
Несколько лет назад я задавался вопросом, что может аппроксимировать нейронная сеть. Ответ -- "все" -- не был удивительным, но тогда мне было неочевидно, как это сделать практически.

А вот оказывается, существует тип нейронных сетей, объединяемых под общим названием резервуарные вычисления (Reservoir Computing), которые неплохо справляются с этой задачей. Идея простая, и не удивительно, что почти одновременно в конце 90х к ней пришли разные группы исследователей, предложившие модели Echo State Networks, Liquid State Machines и некоторые другие.

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

Резервуарные вычисления предлагают несколько другой способ. Исследователи заметили, что в процессе оптимизации многослойных сетей основная "настройка" идет на конечных слоях. Этому есть математическое обоснование, которого я сейчас касаться не буду. А раз так, то можно попробовать вообще не тренировать внутренние слои, если они имеют достаточно богатый "внутренний мир". Так появился "динамический резервуар" нелинейных нейронов, соединенных между собой случайным разряженным образом. В резервуар есть вход и выход. На выходе простой слой линейных нейронов. То есть резервуар представляет собой большой набор разных нелинейных функций, из которого можно "собрать" (через тренировку выходных нейронов) любую функцию. Если опустить вопрос, чем и как "наполнять" резервуар, то тренировка сети получается очень простая и быстрая. Что также позволяет экспериментировать с объемом, connectivity и прочими параметрами резервуара.

Этот подход имеет много интересных свойств. Например, можно к одному и тому же резервуару присоединять разные выходные слои и таким образом решать разные задачи. То есть сам резервуар гомогенен, не настроен под конкретную задачу, и может быть использован для чего угодно. Исследователи предполагают, что человеческий мозг функционирует похожим образом. Известная пластичность мозга хорошо вписывается в это предположение. Более того, Liquid State Machines и еще одна резервуарная технология Temporal Recurrent Networks были разработаны группами, исследовавшими взаимодействие нейронов в мозгу человека.

В последние годы исследователи научились при помощи различных хитрых трюков и возросших вычислительных мощностей получать на обычных рекуррентных сетях впечатляющие результаты. Но все эти сети узко как правило узко специализированны под конкретную задачу или класс задач и требуют долгой и кропотливой настройки и обучения. Резервуарные вычисления выгодно отличаются своей неспециализированностью и скоростью обучения.

Кстати, хочу отметить, что я поменял свое мнение, что в нейросетях нет математики, никто не понимает, как они работают, и все решается экспериментально. Это впечатление возникает только на популярном уровне. Углубившись в тему, я понял, что с математикой там все хорошо, как и почему работают алгоритмы обучения, какие там есть проблемы, и как их решать исследуется достаточно подробно. Эксперимент, безусловно, остается, но теоретические основы есть и развиваются.
kaipa: (Default)
В процессе прохождения онлайн-курса по нейронным сетям посмотрел немного по сторонам и был немало удивлен, что в отечественной науке были и есть даже целые две научные школы (московская и красноярская) с сильными результатами, полученными примерно одновременно с американцами, но имеющими более твердый теоретический фундамент. Когда я интересовался этой темой в конце 90х, мне казалось, что вся наука "там".

В первую очередь тут стоит отметить Александра Ивановича Галушкина, в своей монографии 1974г "Синтез многослойных систем распознавания образов" подытоживший результаты исследований в 60х годах и в том числе обосновавший метод обратного распространения ошибки ("backpropagation" в иностранной литературе) для обучения нейронных сетей. Английская википедия об этом почему-то не знает, упоминая только диссертацию Пола Вербоса того же года. Впрочем, приоритет тут не сильно важен, это я так, на полях. Куда интереснее, на мой взгляд, что подход советской и наследовавшей ей российской школы был более системным. Например, нейронные сети определяются следующим образом: "Нейронные сети – частный вид объекта управления в адаптивной системе с аналитическими методами настройки коэффициентов (адаптации)". Акцент на задачах управления сильно отличается от более современных определений. Отсюда вытекают и другие частные вопросы:
- Какая наиболее эффективная с точки зрения ресурсов функция активации
- Как функции оценки ошибки влияют на скорость сходимости
- Как оценить не только сходимость, но и точность на данной итерации обучения (то есть при ограниченном наборе примеров для обучения оценить точность и надежность для произвольного входа).
и др.
Эти вопросы жизненно важны для задач управления, но не столь существенны для распознавания изображений, речи или предсказательных систем -- типичных примеров применения нейронных сетей сегодня.

Галушкин, к сожалению, в прошлом году умер, до последних дней продолжая заниматься исследованиями в области нейроматематики, публикуя работы и преподавая на Физтехе и в ВШЭ. Он и его группа занимался и сетями с памятью, и сетями переменной топологии -- в общем, на переднем крае. Предисловие к его последней крупной книге "Нейронные сети: основы теории" написал патриарх Лотфи Заде. Хорошее представление о текущем состоянии и перспективах дает статья-доклад 2014г ""О методах настройки многослойных нейронных сетей""

Красноярская научная школа сейчас представлена группой А.Н. Горбаня и Е.М.Миркеса, которые в числе прочего предложили проект стандарта для нейросетевых систем. Причем красноярская школа в большей степени отталкивается от задач динамики химических и биологических систем, для решения которых они и используют аппарат нейронных сетей.
kaipa: (Default)
Возможно кто-то и в курсе, но для меня интересным открытием стал вклад технологий машинного обучения в предвыборную кампанию Барака Обамы 2012г. По сути аналитическая команда Rayid Ghani создали модель, предсказывающую колеблющихся избирателей и лучший способ склонить их колебания в правильную сторону. Модель "тренировали" и проверяли на реальных данных, то есть людях, в дополнение к имеющейся статистике по нескольким предыдущим выборам. В конце концов для каждого колеблющегося штата и каждого избирателя был выработан прогноз: определился избиратель или нет; если нет, то можно ли и каким оптимальным образом его склонить к Обаме; если да, то есть ли шанс, что противоположная команда его "переманит", и как это предотвратить. Для этого использовалась армия волонтёров, которая связалась с каждым потенциальным колеблющимся (напрямую или опосредованно), чтобы убедить его идти на выборы и голосовать за Обаму. Модель получилась очень детализированная, учитывающая несколько десятков характеристик, почти индивидуальный подход. Во многом это напоминает user-level targeting в интернет-рекламе, только в отличие от рекламы финальный результат наверняка проверяется один единственный раз -- в день выборов, предварительные выборки и опросы дают лишь вероятность.

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

Пара ссылок:
http://www.thefiscaltimes.com/Articles/2013/01/21/The-Real-Story-Behind-Obamas-Election-Victory
http://www.kdnuggets.com/2013/01/kdnuggets-exclusive-interview-rayid-ghani-chief-scientist-obama-2012-campaign.html

В интервью есть очень важная цитата:

I think the most important thing 'data scientists' can do is get the science part right. It's easy to be a data hacker, and you do see some immediate benefits just playing around with data, but unless you get the science part right, you can't make sustainable impact.

Я думаю, что самое важное, что могут сделать data scientists -- это правильно понять научную часть проблемы. Довольно просто научиться работать с данными и получить быстрое преимущество, но пока вы не понимаете стоящую за этим науку, невозможно получить воспроизводимые и надежные результаты.
kaipa: (Default)
Выношу из комментариев некоторые ссылки на исследования Юрия Манина, любезно подброшенные [livejournal.com profile] sober_space. (неполный список его работ можно найти, например, тут).

https://www.youtube.com/watch?v=cwZf0lJVOiY -- доклад Манина "Ренормализация и теория вычислимости".

Две статьи, которые подробно описывают то, о чем рассказывалось в докладе:
http://arxiv.org/abs/0904.4921 -- Renormalization and computation I: motivation and background
http://arxiv.org/abs/0908.3430 -- Renormalization and Computation II: Time Cut-off and the Halting Problem

Чуть более поздняя, хотя возможно более доступная, статья.
http://arxiv.org/abs/1302.6695 -- Complexity vs Energy: Theory of Computation and Theoretical Physics

---

Пока я посмотрел только видео. Понял я, конечно, в первой "физической" части далеко не все, хотя мне очень понравилось, как он чисто по математически (физики так не умеют) начал рассматривать общую модель построения квантовой теории поля, указывая, что там важно, что нет, какие допущения делаются и почему, и т.д. Но основную мысль я вроде бы уловил. Она состоит в том, что можно проделать трюк, в результате которого невычислимость будет явно увязана с точностью или бесконечностью. То есть останавливая вычисления в произвольный момент, можно гарантировать определенную точность. И хотя задача остается невычислимой, как и была, ее невычислимость практического "вреда" не имеет. В обратную сторону тоже есть естественная трактовка.

Этот результат мне позволил несколько по-другому посмотреть на утверждение о том, что нейронные сети Тьюринг-полны. Видимо, имеется ввиду, что можно проделать похожий трюк, и спрятать неполноту в точность.

Надеюсь на днях прочитать статьи и несколько глубже в это погрузиться.
kaipa: (Default)
Читаю "Тени Разума" Пенроуза. Периодически там встречается троллинг самого себя и коллег по цеху. Выделение курсивом авторское.

"Такие суперпозиции [положений], как сообщают естествоиспытатели, играют важную роль в действительной конструкции нашего микромира. Квантовый мир на самом деле ведет себя именно таким необычным и непостижимым образом, а нам повезло набрести на этот простой факт. А от фактов никуда не уйти …"

Сама книга достаточно интересна, но весьма непроста для чтения. Пенроуз сначала доказывает тезис о том, что человеческий разум невычислим (более точно, те действия, которые в состоянии совершать человеческий разум, невычислимы). Так как из этого и тезиса Тьюринга-Чёрча-Дойча следует, что мозг должен использовать какой-то неклассический физический процесс, Пенроуз ищет и находит его в квантовой механике. Достаточно большие части книги, поэтому, посвящены вычислимости, теоремам Гёделя и квантовой механике. Как это, к сожалению, часто бывает в англоязычном научпопе -- очень много воды, из-за этого и так не самые простые рассуждения удлиняются и кажутся еще более сложными.
kaipa: (Default)
http://arxiv.org/pdf/1410.5401v2.pdf

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

Такая модификация позволяет гораздо эффективнее (по сравнению с другими известными архитектурами NN) "решать" задачи, требующие память, например сортировку. И, по-видимому, является Тьюринг-полной (авторы ссылаются на известную статью 1995г о Тьюринг-полноте рекурентных нейронных сетей Зигельмана и Зонтага, но доказательство там нестрогое).
kaipa: (Default)
Попытался понять, какая теория стоит за deep learning.

Вот статья с громким названием: Theoretical Motivations for Deep Learning. Конспект какой-то обзорной лекции на тему. В ней я нашел ровно три мотивации:

1. Проклятье размерностей (curse of dimensionality). Нейронные сети позволяют с этим справиться, "выиискивая" в многомерных разряженных данных многообразия меньших размерностей. Это сильная мотивация, хотя у меня есть сомнения насчет полноты и т.д. Выражаясь проще, нет способа оценить, насколько хорошо нейронная сеть это делает и не теряется ли важная информация. Нет в принципе.

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

3. Проблема выпуклости, как они ее назвали. Суть в том, что в отпимизационных невыпуклых задачах больших размерностей обычно очень много локальных экстремумов, и все мягкие алгоритмы, включая нейронные сети, в них с удовольствием застревают. (от себя: в традиционных алгоритмах, Монте-Карло, например, всегда можно оценить вероятность найти экстремум, и ее зависимость от объема выборки, а в мягких -- нельзя). Далее идет обсуждение, что "на самом деле" в задачах большой размерности больше сёдел, чем экстремумов, а сёдла не мешают. Но надо отдать должное, заканчивают честно: "It’s only an empirical validation and there is no proof that the results apply to optimization of neural networks. "

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

Все это не значит, что солидное теоретическое обоснование не появится, но пока что многообещающих практических результатов существенно больше, чем понимания, почему это работает. Удивительная ситуация для науки. Одни считают, что это состояние физики в начале XX века, когда появилось много экспериментальных результатов, а теории, их объясняющей, не было. Другие -- что откат в Древний Египет, когда практики было достаточно, а теория не была нужна.

Пока все идет к тому, что нейронные сети, как и человеческий мозг, будут давать приблизительные, но достаточно хорошие результаты для определенных классов задач. Этакий аналог интуиции, от которой требуется не точность, а скорость и глубина. Там же где нужна строгость и точность, останутся более жесткие алгоритмы. Вполне разумная перспектива.
kaipa: (Default)
Оказывается, пока многие, включая меня, хлопают ушами, в прошлом году произошел качественный перелом в Deep Learning: машинный алгоритм впервые превзошел человека в распознавании лиц (ссылки в журнале [livejournal.com profile] ailev). Это уже даже не шахматы.

Я начал копать, что же случилось за последние годы, а именно (как считает ailev) c 2012г, когда начался бурный рост публикаций, денег и результатов в этой области. Похоже, что накопилась критическая масса и прорвало. А дальше положительная обратная связь. Чем больше интереса -- тем больше денег, чем больше денег -- больше результатов, больше результатов -- больше интереса и далее по спирали. Причем, рост возможностей нейронных сетей обусловлен в основном использованием более оптимальных топологий и способов обучения, нежели чем ростом вычислительных ресурсов (GPA, параллелизм и т.п.). То есть развитие качественное. В списке прогнозов будущего развития от экспертов в области эта мысль звучит неоднократно.

Большой прогресс происходит не только в "статических" сетях, но и сетях с памятью, вроде RNN и LSTM.

Об уровне интереса к теме можно судить по представительности Deep Learning Summit, ближайший из которых состоится через три недели в Сан-Франциско.

Причем, практически все результаты и алгоритмы свободны и открыты, что еще более подогревает интерес и позволяют большему числу людей включиться в работу. Образованная недавно компания OpenAI (в числе спонсоров, кстати, неутомимый Илон Маск) ставит своей целью нести все это добро людям. Отрадно, что это все двигается талантливой молодежью, тот же Ilya Sutskever -- Research Director OpenAI -- автор ряда очень сильных результатов (список работ), например известного вот этого, ему еще нет и 30 лет.

Впрочем, я не снимаю своего мнения, озвученного в ряде комменатриев, что к пониманию, как работает мозг, к моделированию мышления, к знанию, как создать сильный AI, эти успехи нас не приближают. Те же RNN, которые научились посимвольно генерировать текст -- это суррогат знания, китайская комната. Мне кажется, что научились, наконец, пользоваться инструментом, придуманным уже добрые полсотни лет назад, и сейчас происходит (но пока не проходит) эйфория от успехов и результатов. К интеллекту и мышлению это пока не очень относится, но как компоненты и кирпичики чего-то большего (см. нейросетевой конструктор) -- это очень нужно, важно, и на самом деле сделает компьютеры гораздо "умнее". Как роботы заменили людей на производстве, так и прорывные Deep Learning / AI технологии могут заменить (и уже заменяют) людей там, где раньше это не представлялось возможным.

С точки зрения перспективы, мне все же интуитивно кажется, что иерархаические структуры типа HTM Хокинса должны быть лучше, но результатов там пока серьезных нет, что объясняется не столько плохой идеей, сколько сложностью имплементации.

Другая интересная смежная тема -- это нейроэволюция, что в данном контексте означает эволюцию (топологии) нейронной сети или генетическое программирование.

В общем, я сильно загрузился темой (спасибо блогу [livejournal.com profile] ailev), и собираюсь подтянуть свои знания в этой области. Попытка поставить опенсорсную библиотеку MXNet, чтобы покрутить какие-то примеры, сходу не прошла. Ребята знатные извращенцы: чтобы поставить системные библиотеки opencv они предлагают использовать... Ruby, который мне совсем не дался, из исходников я собрать все, не сразу (старый MacOS), но смог, но с R это пока не задружило (MXNet есть в версии для Питона, R и Julia -- из них R мне ближе). Через месяц буду в Штатах, куплю себе "The Master Algorithm", а то самая свежая книжка в этой области у меня из середины 90х, а с тех пор мир изменился неузнаваемо.
kaipa: (Default)
Почти год назад наколеночная нейронная сеть научилась играть в шахматы просто имея массив готовых игр. В опубликованной недавно статье (магистрская работа) описывается шахматная программа, использующая  нейронную сеть для оценки позиции и оптимизации перебора. По утверждению авторов программа играет в силу мастера.

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

Статья интересная, и ее стоит прочитать всем, кто интересуется этой темой. Нейронная сеть была использована для двух разных целей.

Для начала, авторы поставили задачу оценки позиции при помощи нейронный сети. Они построили и натренировали сеть так, чтобы получить функцию оценки максимально близкую к известной функции оценки Stockfish (есть массив позиций оцененных Stockfish). А потом проверили на позициях из Strategic Test Suite. Натренированная нейронная сеть смогла оценивать позиции на уровне лучших шахматных программ, не имея практически никаких априорных знаний -- только опыт обучения!

Следующая логичная задача, которую поставили перед собой авторы -- это использовать нейронную сеть для предсказания лучшего хода. Здесь они использовали нестандартный, как мне кажется, подход для определения глубины поиска: отсечение по вероятности выиграть. То есть для каждой позиции вычисляется вероятность выигрыша, перебор идет в сторону позиций с более высокой вероятностью (или отсечение низких). Это дает преимущество при оценке длинных "вынужденных" комбинаций, когда в позиции не очень много ходов, но ее надо просмотреть глубоко. Нейронная сеть была натренирована для предсказания этих вероятностей. По сравнению с вариантом вычисления вероятностей "в лоб" (чисто через оценку позиций), нейронная сеть "угадывала" наилучший ход несколько чаще, то есть и в этом случае удалось повторить (в смысле результата) и превзойти закодированный алгоритм!

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

Это, конечно, не так круто, как "научиться играть" по партиям, но все равно впечатляет.
kaipa: (Default)


Выше тизер замечательных лекций Романа Михайлова ([livejournal.com profile] baaltii1), из которых я мало что понял, кроме общего настроя, и стал читать "Алгебраическую топологию" Хатчера, чтобы въехать в контекст.

Это лишь один из многих курсов проекта "Лекториум". Не Crausera, конечно, просто курсы лекций ведущих ученых (например, курс о решении 10й проблемы Гильберта читает сам Матиясевич), с обычно хорошим звуком и изображением. Наибольший интерес (для меня) представляют теоретические курсы по Computer Science от ПОМИ РАН и математике от лабаратории им. Чебышева. Попроще курсы от Computer Science Center, более айтишные, на малоподготовленных слушателей что ли.

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

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

Вроде бы идея не кажется сложной, но если заработает, то будет мета-системный переход в нейронных сетях. Уже сейчас полно библиотек для создания сети "на коленке". А при наличии готовых сетей-кубиков порог вхождения сниизится, нейронные сети станут не hi-tech технологией, а просто utility. Я впечатлен.
kaipa: (Default)
На собеседование приходил студент-пятикурсник, который занимается аппроксимацией модели аэродинамики самолета при помощи нейронных сетей. Модель большая и сложная, у нее около 700 переменных и 70 критериев. Поскольку эту тему он по идее должен знать лучше всего, в основном говорили о нейронных сетях.

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

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

Тем не менее, вопрос, на мой взгляд, отнюдь не праздный. Более строго, тут возникают следующие вопросы:
- Какие классы функций может точно или приближенно аппроксимировать нейронная сеть и какие требования на ее конструкцию?
- Какой объем обучения необходим для аппроксимации с заданной точностью?

Исчерпывающий ответ на вопрос, какие функции может аппроскимировать нейронная сеть, дан в этой статье А.Н. Горбаня. Если очень грубо, то это не что иное, как обобщение известной теоремы Веерштрасса об аппроксимации непрерывной функции многочленами. Что такое нейронная сеть? "Нейрон получает на входе вектор сигналов x, вычисляет его скалярное произведение на вектор весов α и некоторую функцию одного переменного φ(x,α) [функцию активации]. Результат рассылается на входы других нейронов или передается на выход. Таким образом, нейронные сети вычисляют суперпозиции простых функций одного переменного и их линейных комбинаций." То есть вопрос переформулируется в вид, можно ли аппроксимировать произвольную непрерывную функцию суперпозицией и линейной комбинацией простых функций одного переменного. Ответ положительный (это следствие из более общего утверждения). Никаких специальных условий на функцию активации не накладывается.

Однако, с практической точки зрения это лишь пол-ответа. Можно утверждать, что для любой функции существует нейронная сеть, которая аппроксимирует ее с любой точностью. Но нельзя утверждать, что, скажем, трех- или четырехслойная сеть на это способна. Сходу, статей, которые бы отвечали на этот вопрос, я не нашел. Но он должен быть, так как, скажем, Колмогоров доказал, что любую непрерывную функцию размерности n можно точно представить в виде суммы из 2n+1 произведений функций одного переменного. Для приближенного представления должны быть похожие оценки, которые можно перевести на язык "слоев" нейронных сетей.

Ответ на второй вопрос, как я подозреваю, сильно зависит от архитектуры и стратегии обучения нейронной сети. Кроме того, есть ряд "не нейронных" методов, которые позволяют оценить точность аппроксимации. Простейший способ, это использовать известную функцию и подсчитать точность апроксимации точно (прошу прощения за тавтологию) при разных архитектурах сети, как это показано, например, в этой статье.
kaipa: (Default)
Неожиданно, комментируя статью [livejournal.com profile] _darkus_ по архитектуре СППР, посмотрел другие материалы "Записок программиста" и увидел подкаст с Ильей Ключниковым о суперкомпиляции. Несколько лет назад я вкратце рассказывал, что это такое. Но в подкасте Илья это раскрывает все гораздо более подробно, включая основные направления исследований, результаты и приложения.

Любопытно, что подкаст опубликован 12го сентября, примерно в то же время, когда мы с ним сидели на одном пляже на Майорке, но там поговорить о суперкомпиляции получилось от силы минут пять.
kaipa: (Default)
Как математик и программист (одним словом -- мехмат) из Яндекса Андрей Плахов ([livejournal.com profile] plakhov) интересуется проблемами эволюционной биологии. "Интересуется" -- наверное, самое удачное здесь слово, в какой-то момент ему это стало просто дико интересно, он стал читать серьезные книги, пробовать мат. модели, думать, спрашивать, популяризовать и т.д. хотя это никак с его работой не связано (почти, некоторые биологические идеи он пробует переносить в алгоритмы Яндекса, насколько я понимаю). Какие-то отдельные посты я и раньше читал, но очень интересно следить за развитем мысли во времени. Рекомендую. Очень интересно (сколько раз я уже употребил это слово?). Хорошее дополнение к книгам Маркова.

http://plakhov.livejournal.com/tag/bio
kaipa: (Default)
http://en.wikipedia.org/wiki/Topological_data_analysis

Никто не разбирался? Понимаю, что вряд ли, но вдруг? На уровне идеи кажется разумным. Есть даже компания Ayasdi в Пало-Альто, которая на основе TDA делает продукт.
kaipa: (Default)
С подачи [livejournal.com profile] beroal с огромным интересом и удовольствием прочитал статью Дейкстры 88года On the cruelty of really teaching computing science.

Основная мысль, как ни странно, не о преподавании Computer Science, а об опасности аналогий и упрощений. За аналогиями теряется новизна, иногда -- радикальная новизна. Этой мысли в ее различных проявлениях он уделяет большую часть статьи. В приложении же к программированию он предостерегает от аналогии Software Engineering, и совершенно правильно пишет, что программирование -- это в первую очередь формальная логика и формальные методы. Но в отличии, скажем, от примитивной дискретной математики, объекты программирования -- огромной размерности.

Статья написана живым, хотя и не самым простым, языком, с юмором, порой переходящим в сарказм. И увы, почти все, что он "видит" в магическом кристале, на самом деле произошло и происходит сейчас. О деградации преподавания Computer Science я писал, по-моему, не один раз.

Кстати, идеальное преподавание Computer Science он видит тогда, когда программы нельзя запустить! В этом случае приходится проводить максимальную ментальную работу, чтобы на самом деле доказать (себе и преподавателю), что программа "работает" правильно. К тому же:

It is now two decades since it was pointed out that program testing may convincingly demonstrate the presence of bugs, but can never demonstrate their absence.

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

Teaching to unsuspecting youngsters the effective use of formal methods is one of the joys of life because it is so extremely rewarding. Within a few months, they find their way in a new world with a justified degree of confidence that is radically novel for them; within a few months, their concept of intellectual culture has acquired a radically novel dimension. To my taste and style, that is what education is about. Universities should not be afraid of teaching radical novelties; on the contrary, it is their calling to welcome the opportunity to do so. Their willingness to do so is our main safeguard against dictatorships, be they of the proletariat, of the scientific establishment, or of the corporate elite.
kaipa: (Default)
Разбирая завал на столе, нашел распечатку статьи Conservative Logic. Совершенно не помню, когда ее распечатал "на потом". Начал читать, стало интересно. Основная мысль -- создание схемотехники, "работающей" не по традиционной логической схеме (в дискретной математике это называется СФЭ -- схема функциональных элементов), а по совсем другой, основное свойство которой сохранение (отсюда conservative) энергии, которая в традиционных системах совершенно расточительно рассеивается. Необходимым образом в таких схемах вытекает обратимость вычислительных и логических процессов. Статья старая, 1982г. Погуглил, нашелся вольный перевод этой статьи год назад на Хабре, веб-сайт критиков консервативной партии США и... почти все. Меня это очень озадачило, так как тема казалась важной. Я предположил, что само название "Консервативная логика" скорее всего не прижилось, и оказался прав. В современном мире это направление называется обратимыми вычислениями, а соответствующая схемотехника -- адибатической логикой.

На самом деле тут проблема очень глубокая и принципиальная, уходящая в самые основы современного понимания устройства мира. Из связи термодинамической и информационной энтропии следует, что любые манипуляции с информацией приводят к рассеиванию энергии. Есть даже теоретическая оценка минимума энергии, которая равна E ≥ kT ln2 на один бит. Это было известно все довольно давно, уже лет 50, но только сейчас, когда вычислительные мощности впечатляюще выросли, начинает по-настоящему припекать. Так, 100-петафлопсные суперкомьютеры (кажется, такие уже есть), излучают только "теоретического" тепла порядка 1 мегаватт, а практически гораздо больше. А это уже сегодняшний день. Завтра суперкомьютеры могут быть в 10-100-1000 раз мощнее, и соответственно вырастет количество теряемой энергии. Обратимые вычисления тут решают теоретически сразу две вещи. Во-первых, энергия не рассеивается, а используется. Как именно это может быть достигнуто, можно прочитать в вышеупомянутой статье. А во-вторых, появляется возможность "делать" схемы еще более "мелкими". Сейчас мешает термодинамический шум.

В настоящее время исследования в этой области проводятся в MIT и University of Florida. Уже есть прототипы чипов на адиабатической логике, а список текущих проектов показывает, что разрабатывается все, от физики, до системы программирования и теории сложности.

Все это очень интересно, но судя по всему менее популярно, чем квантовые компьютеры/вычисления. Возможно потому, что основной выигрыш в экономии энергии, а не в производительности, которую ждут от квантовых компьютеров.
kaipa: (Default)
Прочитал по диагонали современный "Розеттский камень" по ссылке с ru_lambda. Основная мысль статьи в том, что квантовая физика, топология, логика и теория вычислений могут быть выражены в терминах теории категорий. Это, конечно, интересно, что глубокие структурные аналогии можно найти в столь, казалось бы, разных областях. Однако, я остался в некотором недоумении.

Конечная цель любой математической абстракции, а теория категорий -- это пример очень сильной абстракции, в том, чтобы на абстрактном уровне выяснить какие-то новые факты и закономерности, которые затем могут быть применены в более частном случае. В теории категорий, как это изложено в "Розеттском камне", я такого не увидел. Единственная интересная идея вытекает из структурной аналогии квантовых и вычислительных процессов, что может быть полезным при исследованиях, связанных с квантовыми вычислениями. Возможно, что статья и не ставила перед собой такую цель, или я упустил что-то важное. Буду признателен, если кто-то укажет на те достижения теории категорий, которые позволили получить что-то новое в моделях и процессах, выражаемых ее терминами.
kaipa: (Default)
В некоторых вещах я консервативен. Очень не люблю электронные книги и читать с экрана вообще. Как правило можно купить бумажную. Но вот видео-лекция оказалась достаточно удобным способом получения информации. Конечно, вживую лучше, но даже так некоторый элемент присутствия есть, все же мы привыкли к кино и телевизору.

Не помню, откуда я набрел на эту ссылку, но она у меня "лежала" давно. Наконец-то я посмотрел лекцию Александра Шеня ([livejournal.com profile] a_shen), прочитанную два года назад в ФИАНе, до конца и все понял :) Предыдущая попытка разобраться в проблеме при помощи учебника "Введение в квантовые вычисления" (американская какая-то) была неудачной.

Лекция: http://elementy.ru/video?pubid=431220

Первая половина лекции рассказывает о проблемах компьютерной науки, связанных со сложностью: достаточно тривиальные вещи, но они необходимы, чтобы понять в чем суть. Затем Шень объясняет в общих чертах, что такое квантовый компьютер с точки зрения математики, и какие задачи он в перспективе мог бы решать. Вернее, что такой компьютер сможет решать, как раз непонятно, кроме нескольких известных уже сейчас примеров. Исследователи пытаются двигаться туда, где хоть что-то понятно в смутной надежде, что в процессе этого движения откроется истина. Причем очевидно, что когда квантовый компьютер с достаточным числом кубитов будет построен, то это приведет к финансовой катастрофе, так как квантовый компьютер эффективно решает проблему факторизации простых чисел, на вычислительной сложности которой построено большинство систем шифрования с открытом ключом.

Далее выступает его коллега, который рассказывает как квантовый компьютер работает или мог бы работать физически, и какие там появляются физические проблемы и технические сложности. Интересно, что Шень и его коллега упоминают о квантовом прототипе IBM 2001г. на семи кубитах, который "смог" разложить число 15 на множители при помощи квантового алгоритма Шора. Однако, они ничего не говорят о компании D-Wave, которая в 2008г уже демонстрировала 16-кубитовый процессор, а сейчас разрабатывает или разработала еще более кубитовые процессоры. Впрочем, возможно что у них какие-то проблемы, новости на сайте не обновлялись с 2009г, хотя в блоге основателя и CTO Dr. Geordie Rose продолжают публиковаться новые материалы. Некоторые специалисты, например, [livejournal.com profile] dr_klm, считают, что проблемы фундаментальные, а D-Wave и не только они зашли в тупик.

Все это чрезвычайно интересно, но, похоже, что до компьютерной "квантовой революции" еще не один десяток лет.
kaipa: (Default)
Я, конечно, слышал о попытках моделировать Вселенную как гигантский клеточный автомат. Но название "цифровая физика" раньше не встречал. Тем не менее, это устоявшийся термин, и именно так называются статьи на википедии. Русская по-видимому недопереведена (хм, три приставки в слове), поэтому лучше читать английский вариант.

http://ru.wikipedia.org/wiki/Цифровая_физика
http://en.wikipedia.org/wiki/Digital_physics

Не могу сказать, что мне нравится это идея, но ее можно интерпретировать просто как некоторую дискретную функцию изменения пространства во времени. Что не противоречит, например, теории Петлевой Квантовой Гравитации, о которой я совсем недавно писал.

Некоторые простейшие примеры моделирования физических законов клеточными автоматами можно посмотреть здесь http://muha-a.livejournal.com/694.html.

Надо заметить, что для возможности моделирования Вселенной клеточным автоматом, необходимо, чтобы Вселенная была вычислима. Я слишком мало знаком с этой областью, но как раз недавно об этом вскользь упоминал: http://fregimus.livejournal.com/128969.html . Но и в случае невычислимой Вселенной остается возможность ее моделирования, но уже не клеточным автоматом, а, например, квантовым компьютером или другим сверхтьюринговым вычислителем.

Попытки человеческого разума познать Бытие разнообразны и удивительны.

Update: [livejournal.com profile] fregimus верно указал в комментариях, что квантовый компьютер, по-видимому, не "решает" невычислимую Вселенную.

Profile

kaipa: (Default)
kaipa

April 2017

S M T W T F S
       1
2345678
9101112131415
16171819202122
23242526272829
30      

Syndicate

RSS Atom

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 06:21 pm
Powered by Dreamwidth Studios