Programming collective intelligence

Programming Collective Intelligence by  Toby Segaran.

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

Достоинства книги:

• Книга очень легко читается, автор не страдает болезнью разжевывания. Воды в книге нет.
• Каждая глава является (почти) самодостаточной. 
• Примеры закодированы на Питоне: код краток. (Сравните с книгами Collective Intelligence in Action или с Algorithms of the Intelligent Web, где примеры закодированы на Java.)
• Очень хорошо (интуитивно понятно) обосновывается, за счет чего алгоритм работает.

Недостатки (которые не умаляют достоинств):

• В подавляющем случае нет ссылок на первоисточники. (А в книгах Collective Intelligence in Action, Algorithms of the Intelligent Web и Machine Learning in Action такие ссылки есть.)
• В книге отсутствуют (интуитивно понятные) объяснения, как работают метод опорных векторов и как работает алгоритм неотрицательной матричной факторизации ("beyond the scope of this book").
• Некоторые важные трюки описаны, но не подчеркнута их важность. Пример: при иерархической кластеризации, когда две группы сливаются в одну группу, то показатели новой группы вычисляются как среднее между показателями исходных групп. В книге есть еще несколько таких мест.

Почему книга настоятельно рекомендуется к прочтению программистам:

• В основе большинства алгоритмов искуственного интеллекта (Artificial Intelligence) и машинного обучения (Machine Learning) лежат очень простые трюки (или даже хаки) которые очень хорошо работают в некоторых условиях. Навых понимания того, что очень простой трюк может привести к правильному и эффективному решению, крайне важен для программиста. Основа этих алгоритмов очень проста (не rocket science).
• Чтобы понимать, как работает современный интернет. Алгоритмы описанные в книге, лежат в основе повседневных современных вещей (см. краткое содержание дальше). Все мы ленивые и мало читаем. У всех у нас есть неправильные наивные представления о вещах, про которые мы не знаем наверняка. Однако, стыдимся своего невежества. Очень грустно слышать, когда коллега по работе (например) начинает с легкостью рассуждать, про то, как работают алгоритмы кластеризации, имея превратное и неправильное представление. В общем, надо прочесть, чтобы побороть свое невежество.

Ну теперь краткое содержание книги по главам. Все алгоритмы делятся на обучение с учителем (supervised learning) и обучение без учителя (unsupervised learning):

1. Введение. Общие слова.
2. Построение рекомендаций. Алгоритмы, лежащие в основе рекомендаций amazon, imdb и т.д.
• User-based recommendations. Среди пользователей ресурса находятся N наиболее близких к вам, а затем делается из их топовых предпочтений делается взвешенная (weighted) рекоммендация для вас.
• Item-based recommendation. Трюк: матрица предпочтений переворачивается. В результате находятся похожие продукты. Этот алгоритм лежит в основе рекоммендации от amazon. Плюс данного алгоритма - требует меньше вычислительных ресурсов.
3. Обнаружение групп/структуры в данных. 
• Иерархическая кластеризация. Набор данных представляетс в виде древовидной иерархической структуры. Примеры книги - иерархическая классификация блогов. Иерархия строится снизу вверх. Классификация предпочтений. Пример из другой книги (Data mining) - автоматическое построение иерархии видов/классов для животного мира. Как может применяться? Для рекомендации - вам могут порекомендовать купить предметы, которые находятся в той же (достаточно узкой) группе.
• Иерархическая кластеризация столбцов. Применяется трюк, похожий на трюк из предыдущей главы - матрица предпочтений/аттрибутов переворачивается. В результате получается иерархия аттрибутов. Пример в книге - нахождение "главных" слов, которые наиболее употребляются в той или иной группе блогеров.
• Кластеризация на N групп через усреднение (K-means clusterization). Здесь все просто. Говорите: хочу выявить N групп. Группы ищутся через рандомизацию/усреднение.
4. Поиск и ранжирование. Реализован небольшой google на Питоне.
5. Оптимизация. Минимизируется некоторая целевая функция, зависящая от многих параметров. Рассмотренные методы широко известны. Иллюстрируются на двух примерах: поиск расписания полетов для семейной встречи, расположение связей (социального графа) на плоскости так, чтобы пересекалось как можно меньше связей. Отдельно стоить отметить, что алгоритмы закодированы в обобщенном виде, -  и применимы ко многим задачам. 
• Случайный поиск.
• Метод спуска (обычного, не градиентного).
• Имитация отжига.
• Генетические алгоритмы.
6. Фильтрация документов (спам/не спам).
• Наивный Байесовский классификатор. Каждый взрослый человек должен понимать теорему Байеса!
• Метод Фишера. Основной трюк - тестирование, насколько данная комбинация слов является случайной.
7. Деревья принятия решений (decision trees).
• Чем-то похоже на построение иерархической кластеризации из главы 3. Большое отличие - дерево строится сверху вних! Для разбиения можно использовать разные метрики:
• Энтропия.
• Индекc Джини.
• Дисперсия.
• Как и алгоритмы оптимизации, алгоритмы закодированы в обобщенном виде и легко применимы к новым задачам.
8. Предсказание численных значений.
• Среднее по K-соседям.
• Поиск масштабирования атрибутов. Для этого множество разбивается на два подмножества: обучающее и тестирующее. Поиск оптимальных масштабирующих параметров происходит алгоритмами оптимизации из главы 5. (Одно из самых красивых мест в книге - когда на помощь одному эвристическому алгоритму приходит другой эвристический алгоритм!)
9. Продвинутые методы классификации.
• Метод опорных векторов. - Поиск сложных разбиений между группами.
10. Поиск независимых компонент. Пример: формирование заголовков новостей. Похожие алгоритмы применяются сервисами вроде google news или яндекс новости. Суть - данные представляются в виде матрицы и мы пытаемся эту матрицу представить в виде произведения матриц. 
• Метод неотрицательной матричной факторизации. - Пожалуй, самые красивый алгоритм из всей книги.
11. Эволюционирующие алгоритмы. Построение программы, которая угадывает некоторую функцию.
• Генетические алгоритмы.
12. Повторный обзор рассмотренных алгоритмов.

Автор книги Toby Segaran является также соредактором книги Beautiful Data и соавтором книги Programming the Semantic Web. Книга Beautiful Data, судя по оглавлению, очень интересна.