Некоторое время назад мне захотелось получше разобраться с тем, как устроены современные нейронные сети. До этого мои знания о них были на уровне 60-70-х годов прошлого века. Я имел какое-то представление о многослойных перцептронах, функциях активации в виде сигмоида, алгоритме обратного распространения ошибки и, кажется, все. При этом некоторые книги, которые мне довелось полистать, тяготели к двум крайностям. Либо это были чисто математические работы для математиков, либо книги в стиле «берем библиотеку X, импортируем функцию Y, все работает». Хотелось почитать книгу, после которой можно было бы более осмысленно использовать какую-нибудь библиотеку вроде TensorFlow, понимая, каким образом построить архитектуру сети. В этот момент мне попалась книга трех авторов: С. Николенко, А. Кадурина и Е. Архангельской под названием «Глубокое обучение. Погружение в мир нейронных сетей». Полистав ее, я увидел, что формулы в ней присутствуют, но кроме формул есть еще много текста и картинок со схемами, и даже код встречается. В общем, решил я почитать эту книгу.

Читать далее ‘Про книгу «Глубокое обучение. Погружение в мир нейронных сетей»’ »

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

И вот еще недавно прочитал статью, где для оптимизации использовали алгоритм хаотичных воробьев (chaos sparrow search algorithm). Название уже интригует. Причем если почитать описание этого алгоритма, то там разворачивается прям блокбастерная история, напрашивающаяся на экранизацию. Среди роя воробьев выделяются воробьи-исследователи (explorers), последователи (followers) и мстители (vigilantes), и каждый из них перемещается по своему алгоритму. Дальше, чтобы не спойлерить, чем все это закончится, читайте описание алгоритма.

Даже захотелось попробовать реализовать такой алгоритм. Тем более, что у меня есть заброшенный проект на Rust с библиотекой подобных алгоритмов.

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

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

По этой ссылке вы можете увидеть мой доклад (а заодно скачать презентацию), а также посмотреть обсуждение темы ввода новичков в проект (onboarding).

Видео своего доклада оставлю еще и здесь.

Как я уже писал, помимо проекта OutWiker, в последнее время я занялся проектом optlib, библиотекой на языке Rust с реализацией разных алгоритмов оптимизации. На данный момент в библиотеке реализованы генетический алгоритм и алгоритм роя частиц. На днях я выложил новую версию этой библиотеки под номером 0.3.0.

У библиотеки optlib есть документация, но в ближайшее время я собираюсь заняться написанием статей с более подробным описанием работы этой библиотеки. В этом посте я коротко расскажу о том, что появилось нового в версии 0.3.0.

Читать далее ‘Optlib 0.3.0. Новая версия библиотеки для оптимизации на языке Rust’ »

Параллельно с другими проектами я продолжаю заниматься библиотекой optlib, предназначенной для оптимизации функций на языке Rust. Напомню, что под оптимизацией функции f(x) понимается нахождение такого значения x’ (в общем случае x — вектор), что значение функции f(x’) минимально на заданном интервале для x. Библиотека optlib содержит в себе алгоритмы, предназначенные для глобальной оптимизации, то есть, в отличие от градиентных методов, эти алгоритмы пытаются найти глобальный экстремум функции (градиентные методы находят только ближайший к начальной точке локальный экстремум).

Читать далее ‘Optlib 0.2. Библиотека для оптимизации на языке Rust’ »

В Москве есть такое замечательное сообщество — Московский клуб программистов. Раз в две недели участники этого сообщества собираются (в последнее время площадку для таких митапов предоставляет компания Леруа Мерлен у себя в офисе на Шаболовке) и обсуждают какие-нибудь две темы. Обычно это происходит в виде доклада с последующими вопросами или в виде модерируемого обсуждения.

Несколько дней назад я выступил на этом митапе и рассказал о генетических алгоритмах. Ниже вы можете посмотреть видео этого доклада. Материалы с этого митапа (в том числе презентацию) можно скачать по этой ссылке с сайта Московского клуба программистов.

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

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

Именно такую библиотеку я решил написать на Rust. Так появилась библиотека optlib. Ссылки на исходники и документацию:

• Страница на github — https://github.com/Jenyay/rust-optimization
• Страница на crates.io — https://crates.io/crates/optlib
• Документация — https://docs.rs/optlib

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

Помимо документации я написал довольно большую статью про библиотеку optlib и генетический алгоритм, которую можно прочитать тут — Библиотека Optlib. Реализация генетического алгоритма оптимизации на Rust. Эту же статью я опубликовал на Хабре — https://habr.com/ru/post/448870/.

Я надеюсь, что я буду находить время на дальнейшие улучшения этой библиотеки, потому что в списке идей относительно этой библиотеки еще много пунктов.

Прочитал книгу Х. Марманиса и Д. Бабенко «Алгоритмы интеллектуального интернета». Как видно из названия, эта книга посвящена алгоритмам, которые применяются на сайтах для того, чтобы сделать сайт чуть более дружественным пользователю, хотя эти же алгоритмы можно применять и для оффлайновых приложений.

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

В разделе про поиск описывается алгоритм PageRank, который был представлен на конференции в 1998 году Сергеем Брином и Ларри Пейджем. Конечно, с того времени в алгоритме, используемым Google, многое поменялось, но в целом суть осталась той же — чем больше ссылок на странице, тем более релевантной она считается. Этот алгоритм показывает, как можно учитывать ссылки между страницами для того, чтобы определить, какой из них отдать предпочтение при поиске.

Для поиска по данным в примерах используется библиотека Lucene, которая использует свой алгоритм подсчета релевантности страниц. В книге описаны способы объединения нескольких алгоритмов подсчета веса страниц с тем, чтобы улучшить поисковую выдачу.

Для дальнейшего улучшения поиска авторы используют алгоритм Байеса. Обычно этот алгоритм описывается на примере фильтрации спама (в книге такой пример тоже будет), но сначала авторы его используют для того, чтобы рассчитать вероятность того, что данная ссылка заинтересует пользователя, зная, на какие ссылки он кликал до этого и при каких поисковых запросах. После этого авторы объединяют все три способа фильтрации результатов поиска.

Читать далее ‘Обзор книги Х. Марманиса и Д. Бабенко «Алгоритмы интеллектуального интернета»’ »

Как вы, наверное, знаете, термин «Искусственный интеллект» (ИИ) в последнее время стал применяться совсем не в том смысле, как он задумывался изначально. Сейчас под искусственным интеллектом чаще всего понимают в основном интеллектуальные алгоритмы, выполняющие какую-то одну конкретную задачу, такие алгоритмы могут быть довольно сложными и их идеи могут быть взяты из природы (нейронные сети, генетические алгоритмы, алгоритм роя пчел, муравьиной колонии и т.п.) Однако, такие алгоритмы — это совсем не то, чего ожидали от компьютеров еще в 50-60-ых годах прошлого века, когда казалось, что еще чуть-чуть и благодаря компьютеру люди создадут еще один разум. Этого не произошло, и требования к искусственному интеллекту стали постепенно снижаться, так появились термины «сильный ИИ» — ИИ в его первоначальном понимании — и «слабый ИИ» — просто интересные алгоритмы.

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

Читать далее ‘Про книгу А. С. Потапова «Искусственный интеллект и универсальное мышление»’ »

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

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

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

Читать далее ‘Сумбурное описание алгоритма роя частиц’ »