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

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

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

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

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

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

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

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

potapov

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

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

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

Сумбурное описание алгоритма роя частиц

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

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

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

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

Тоби Сегаран «Программируем коллективный разум»

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

Книга «Программируем коллективный разум» в основном посвящена алгоритмам классификации и кластеризации, хотя есть главы, посвященные другим темам вроде создания собственного поисковика, генетическим алгоритмам и генетическому программированию. Почти все описанные алгоритмы применяются в духе Web 2.0, используя анализ поведения пользователей на разных сайтах, которые предоставляют свой API. Но что особенно приятно удивило, так это то, что все примеры написаны на языке Python.

Вот какие алгоритмы описываются в книге:

  • Коллаборативная фильтрация. Или, говоря человечески языком, алгоритмы, которые могут рекомендовать вам какие-то покупки, сайты или музыку в зависимости от оценок, которые вы поставили другим подобным вещам. По таким алгоритмам работает навязывание покупок в интернет-магазинах или подбор музыки на last.fm. В конце главы приводится пример, который будет рекомендовать вам ссылки из сервиса del.icio.us.
  • Алгоритмы группировки (кластеризации). Создаваемый пример анализирует RSS-каналы блогов и пытается их автоматически разделить на группы в виде дерева в зависимости от частоты слов, которые попадаются в блоге. Заодно Сегаран рассказывает как можно сделать так, чтобы названия блогов расположились на плоскости кучками в зависимости от их близости в плане рассматриваемых тем.
  • Отдельная глава посвящена построению поисковиков — созданию паука и, самое главное, рассматриваются алгоритмы ранжирования ссылок, в том числе и с учетом ссылок страниц друг на друга, создавая, таким образом, аналог Google PageRank. Еще интересно, что в этой же главе есть пример, где для выдачи наиболее релевантных ссылок используется нейронная сеть, которая обучается по мере того как пользователь щелкает на понравившиеся ему ссылки.

Читать далее ‘Тоби Сегаран «Программируем коллективный разум»’ »

Книга Уоррена «Алгоритмические трюки для программистов»

algПрочитал недавно книгу Уоррена «Алгоритмические трюки для программистов» (в оригинале она называется «Hacker’s Delight»), любопытная оказалась книжка, хотя алгоритмы, рассмотренные в ней, довольно специфические.

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

Многие алгоритмы явно предназначены для того, чтобы их реализовали на ассемблере, причем иногда для процессоров, более редких, чем x86 (например, часто упоминаются процессоры IBM, а иногда опоминаются и древние компьютеры еще 60-ых годов прошлого века). Автор пишет, что многие примеры из книги могут пригодиться тем, кто создает компиляторы. Для примера приведу описание некоторых задач, разбираемых автором: как обнулить крайний справа единичный бит (01011000 -> 01010000), округление к кратному степени двойки, подсчет единичных битов в слове, поиск строки битов и тому подобные. Почти для каждого алгоритма автор пытается оценить количество необходимых тактов процессора, иногда с учетом распараллеливания.

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

Ближе к концу книги есть глава, посвященная системам счисления с необычными основаниями, такие как -2, -1+i, -1-i. Такие системы счисления никто в здравом уме применять не будет, но почитать про них все-равно интересно.

Также есть главы, посвященные коду Грея, кривой Гильберта, представлению чисел с плавающей точкой и глава про формулы, которые дают последовательность простых чисел.

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

Книгу можно рассматривать как небольшой сборник рецептов про битовые операции. Книга издавалась несколько раз, последнее издание 2007 года.

В электронном виде найти ее можно без проблем.

Нейрокомпьютеры

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

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

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

Читать далее ‘Нейрокомпьютеры’ »

Программирование искусственного интеллекта в приложениях

AI_book.jpg

Прочитал книгу М. Тима Джонса «Программирование искусственного интеллекта в приложениях», которая в оригинале называется «AI Application Programming». Оказалось, что это очень даже интересная книжка, посвященная так называемому «слабому искусственному интеллекту», то есть алгоритмам и технологиям, которые уже сейчас используют в приложениях.

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

Кратко опишу про какие технологии и алгоритмы рассказывается в этой книге и на каких примерах.

Читать далее ‘Программирование искусственного интеллекта в приложениях’ »