- •Об авторе
- •Предисловие
- •Для кого эта книга
- •О чем эта книга
- •Что вам потребуется при чтении этой книги
- •Условные обозначения
- •От издательства
- •Глава 1. Обзор алгоритмов
- •Что такое алгоритм
- •Этапы алгоритма
- •Определение логики алгоритма
- •Псевдокод
- •Использование сниппетов
- •Создание плана выполнения
- •Введение в библиотеки Python
- •Библиотеки Python
- •Реализация Python с помощью Jupyter Notebook
- •Методы разработки алгоритмов
- •Параметры данных
- •Параметры вычислений
- •Анализ производительности
- •Анализ пространственной сложности
- •Анализ временной сложности
- •Оценка эффективности
- •Выбор алгоритма
- •«О-большое»
- •Проверка алгоритма
- •Точные, приближенные и рандомизированные алгоритмы
- •Объяснимость алгоритма
- •Резюме
- •Глава 2. Структуры данных, используемые в алгоритмах
- •Структуры данных в Python
- •Список
- •Кортеж
- •Словарь
- •Множество
- •DataFrame
- •Матрица
- •Абстрактные типы данных
- •Вектор
- •Стек
- •Очередь
- •Базовый принцип использования стеков и очередей
- •Дерево
- •Резюме
- •Глава 3. Алгоритмы сортировки и поиска
- •Алгоритмы сортировки
- •Обмен значений переменных в Python
- •Сортировка пузырьком
- •Сортировка вставками
- •Сортировка слиянием
- •Сортировка Шелла
- •Сортировка выбором
- •Алгоритмы поиска
- •Линейный поиск
- •Бинарный поиск
- •Интерполяционный поиск
- •Практическое применение
- •Резюме
- •Глава 4. Разработка алгоритмов
- •Знакомство с основными концепциями разработки алгоритма
- •Вопрос 1. Даст ли разработанный алгоритм ожидаемый результат?
- •Вопрос 2. Является ли данный алгоритм оптимальным способом получения результата?
- •Вопрос 3. Как алгоритм будет работать с большими наборами данных?
- •Понимание алгоритмических стратегий
- •Стратегия «разделяй и властвуй»
- •Стратегия динамического программирования
- •Жадные алгоритмы
- •Практическое применение — решение задачи коммивояжера
- •Использование стратегии полного перебора
- •Использование жадного алгоритма
- •Алгоритм PageRank
- •Постановка задачи
- •Реализация алгоритма PageRank
- •Знакомство с линейным программированием
- •Практическое применение — планирование производства с помощью линейного программирования
- •Резюме
- •Глава 5. Графовые алгоритмы
- •Представление графов
- •Типы графов
- •Особые типы ребер
- •Эгоцентрические сети
- •Анализ социальных сетей
- •Введение в теорию сетевого анализа
- •Кратчайший путь
- •Создание окрестностей
- •Показатели центральности
- •Вычисление показателей центральности с помощью Python
- •Понятие обхода графа
- •BFS — поиск в ширину
- •DFS — поиск в глубину
- •Практический пример — выявление мошенничества
- •Простой анализ мошенничества
- •Анализ мошенничества методом сторожевой башни
- •Резюме
- •Глава 6. Алгоритмы машинного обучения без учителя
- •Обучение без учителя
- •Обучение без учителя в жизненном цикле майнинга данных
- •Современные тенденции исследований в области обучения без учителя
- •Практические примеры
- •Алгоритмы кластеризации
- •Количественная оценка сходства
- •Иерархическая кластеризация
- •Оценка кластеров
- •Применение кластеризации
- •Снижение размерности
- •Метод главных компонент (PCA)
- •Ограничения PCA
- •Поиск ассоциативных правил
- •Примеры использования
- •Анализ рыночной корзины
- •Ассоциативные правила
- •Оценка качества правила
- •Алгоритмы анализа ассоциаций
- •Практический пример — объединение похожих твитов в кластеры
- •Тематическое моделирование
- •Кластеризация
- •Алгоритмы обнаружения выбросов (аномалий)
- •Использование кластеризации
- •Обнаружение аномалий на основе плотности
- •Метод опорных векторов
- •Резюме
- •Глава 7. Традиционные алгоритмы обучения с учителем
- •Машинное обучение с учителем
- •Терминология машинного обучения с учителем
- •Благоприятные условия
- •Различие между классификаторами и регрессорами
- •Алгоритмы классификации
- •Задача классификации
- •Оценка классификаторов
- •Этапы классификации
- •Алгоритм дерева решений
- •Ансамблевые методы
- •Логистическая регрессия
- •Метод опорных векторов (SVM)
- •Наивный байесовский алгоритм
- •Алгоритмы регрессии
- •Задача регрессии
- •Линейная регрессия
- •Алгоритм дерева регрессии
- •Алгоритм градиентного бустинга для регрессии
- •Среди алгоритмов регрессии победителем становится...
- •Практический пример — как предсказать погоду
- •Резюме
- •Глава 8. Алгоритмы нейронных сетей
- •Введение в ИНС
- •Эволюция ИНС
- •Обучение нейронной сети
- •Анатомия нейронной сети
- •Градиентный спуск
- •Функции активации
- •Инструменты и фреймворки
- •Keras
- •Знакомство с TensorFlow
- •Типы нейронных сетей
- •Перенос обучения
- •Практический пример — использование глубокого обучения для выявления мошенничества
- •Методология
- •Резюме
- •Глава 9. Алгоритмы обработки естественного языка
- •Знакомство с NLP
- •Терминология NLP
- •Библиотека NLTK
- •Мешок слов (BoW)
- •Эмбеддинги слов
- •Окружение слова
- •Свойства эмбеддингов слов
- •Рекуррентные нейросети в NLP
- •Использование NLP для анализа эмоциональной окраски текста
- •Практический пример — анализ тональности в отзывах на фильмы
- •Резюме
- •Глава 10. Рекомендательные системы
- •Введение в рекомендательные системы
- •Типы рекомендательных систем
- •Рекомендательные системы на основе контента
- •Рекомендательные системы на основе коллаборативной фильтрации
- •Гибридные рекомендательные системы
- •Ограничения рекомендательных систем
- •Проблема холодного старта
- •Требования к метаданным
- •Проблема разреженности данных
- •Предвзятость из-за социального влияния
- •Ограниченные данные
- •Области практического применения
- •Практический пример — создание рекомендательной системы
- •Резюме
- •Глава 11. Алгоритмы обработки данных
- •Знакомство с алгоритмами обработки данных
- •Классификация данных
- •Алгоритмы хранения данных
- •Стратегии хранения данных
- •Алгоритмы потоковой передачи данных
- •Применение потоковой передачи
- •Алгоритмы сжатия данных
- •Алгоритмы сжатия без потерь
- •Практический пример — анализ тональности твитов в режиме реального времени
- •Резюме
- •Глава 12. Криптография
- •Введение в криптографию
- •Понимание важности самого слабого звена
- •Основная терминология
- •Требования безопасности
- •Базовое устройство шифров
- •Типы криптографических методов
- •Криптографические хеш-функции
- •Симметричное шифрование
- •Асимметричное шифрование
- •Практический пример — проблемы безопасности при развертывании модели МО
- •Атака посредника (MITM)
- •Избежание маскарадинга
- •Шифрование данных и моделей
- •Резюме
- •Глава 13. Крупномасштабные алгоритмы
- •Введение в крупномасштабные алгоритмы
- •Определение эффективного крупномасштабного алгоритма
- •Терминология
- •Разработка параллельных алгоритмов
- •Закон Амдала
- •Гранулярность задачи
- •Балансировка нагрузки
- •Проблема расположения
- •Запуск параллельной обработки на Python
- •Разработка стратегии мультипроцессорной обработки
- •Введение в CUDA
- •Кластерные вычисления
- •Гибридная стратегия
- •Резюме
- •Глава 14. Практические рекомендации
- •Введение в практические рекомендации
- •Печальная история ИИ-бота в Твиттере
- •Объяснимость алгоритма
- •Алгоритмы машинного обучения и объяснимость
- •Этика и алгоритмы
- •Проблемы обучающихся алгоритмов
- •Понимание этических аспектов
- •Снижение предвзятости в моделях
- •Решение NP-трудных задач
- •Упрощение задачи
- •Адаптация известного решения аналогичной задачи
- •Вероятностный метод
- •Когда следует использовать алгоритмы
- •Практический пример — события типа «черный лебедь»
- •Резюме
Знакомство с основными концепциями разработки алгоритма |
95 |
ЗНАКОМСТВО С ОСНОВНЫМИ КОНЦЕПЦИЯМИ РАЗРАБОТКИ АЛГОРИТМА
Как уже говорилось в главе 1, словарь American Heritage Dictionary определяет алгоритм следующим образом:
«Конечный набор однозначных инструкций, которые при заданном наборе начальных условий могут выполняться в заданной последовательности для достижения определенной цели и имеют определимый набор конечных условий».
Разработка алгоритма заключается в том, чтобы придумать этот «конечный набор однозначных инструкций»‚ позволяющий наиболее эффективным спо собом добиться «достижения определенной цели». В случае сложной при кладной задачи разработка алгоритма — дело весьма утомительное. Чтобы осуществить качественную реализацию, мы должны всесторонне изучить поставленную задачу. Прежде чем придумать, как это будет сделано (то есть разработать алгоритм)‚ необходимо выяснить, что нужно сделать (то есть по нять требования). Понимание задачи включает в себя как функциональные, так и нефункциональные требования. Давайте посмотрим, что это такое:
zz Функциональные требования формально определяют интерфейсы ввода и вывода, а также связанные с ними функции. Они помогают понять, как данные будут обрабатываться и какие вычисления необходимо реализовать, чтобы получить результат.
zzНефункциональные требования определяют ожидания в отношении произ водительности и безопасности алгоритма.
Разработка алгоритма подразумевает удовлетворение как функциональных, так и нефункциональных требований наилучшим возможным способом, учитывая обстоятельства и доступные ресурсы.
Чтобы получить результат, соответствующий функциональным и нефункциональ ным требованиям, надо ответить на три вопроса, сформулированные в главе 1:
zz Вопрос 1. Даст ли разработанный алгоритм ожидаемый результат?
zz Вопрос 2. Является ли данный алгоритм оптимальным способом получения этого результата?
zzВопрос 3. Как алгоритм будет работать с большими наборами данных?
Далее мы подробно рассмотрим эти вопросы.
96 |
Глава 4. Разработка алгоритмов |
Вопрос 1. Даст ли разработанный алгоритм ожидаемый результат?
Алгоритм — это математическое решение реальной задачи. Чтобы быть полез ным, он должен давать точные результаты. О проверке правильности алгоритма нужно думать заранее‚ и она должна быть заложена в его архитектуру. Прежде чем разрабатывать стратегию проверки алгоритма, нам нужно рассмотреть следующие два аспекта:
zz Определение истины (truth). Для проверки алгоритма нам нужны некоторые известные правильные результаты для заданного набора входных данных. В контексте поставленной задачи такие результаты называются истинами. Пытаясь найти лучшее решение, мы последовательно совершенствуем наш алгоритм и используем истину в качестве ориентира.
zzВыбор метрик. Кроме того, нужно решить, как именно мы собираемся коли чественно оценивать отклонение от определенной истины. Выбор правильных показателей (метрик) поможет точно оценить качество нашего алгоритма.
Например, для алгоритмов машинного обучения в качестве истины можно ис пользовать существующие размеченные данные. Для количественной оценки отклонения от истины можно выбрать одну или несколько метрик, таких как
доля правильных ответов (accuracy), полнота (recall) или точность (precision). Важно отметить, что в некоторых случаях результат не ограничен одним значе нием‚ а представляет собой диапазон для заданного набора входных данных. Во время разработки нашей целью будет итеративное улучшение алгоритма до тех пор, пока результат не окажется в пределах диапазона, указанного в требо ваниях.
Вопрос 2. Является ли данный алгоритм оптимальным способом получения результата?
Более развернуто этот вопрос звучит так:
Является ли алгоритм оптимальным решением и можем ли мы убедиться, что для этой задачи не существует другого решения, которое было бы лучше нашего?
На первый взгляд, на этот вопрос ответить довольно просто. Однако в случае с некоторыми классами алгоритмов исследователи потратили десятилетия на безуспешные попытки подтвердить оптимальность конкретного решения.
Знакомство с основными концепциями разработки алгоритма |
97 |
Таким образом, сначала важно понять задачу и ее требования и оценить ресур сы, доступные для запуска алгоритма. Необходимо признать следующее утверж дение:
Нужно ли стремиться найти оптимальное решение этой проблемы? Поиск и проверка оптимального решения — очень сложный и длительный процесс. Поэтому лучше всего подойдет работоспособное (приемлемое) решение, основанное на эвристике.
Понимание задачи и ее сложности — важно, и это помогает оценить требования к ресурсам.
Прежде чем мы углубимся в детали, давайте определим два термина.
zz Полиномиальный алгоритм (polynomial algorithm). Если алгоритм имеет временную сложность O (n k), мы называем его полиномиальным, где k — константа.
zzСертификат (certificate). Предлагаемый вариант решения, полученный по окончании итерации, называется сертификатом. По мере итеративного про движения к решению конкретной задачи мы обычно генерируем серию сертификатов. Если решение стремится к сходимости, каждый сгенериро ванный сертификат будет лучше предыдущего. В какой-то момент, когда сертификат будет соответствовать требованиям, мы выберем его в качестве окончательного решения.
В главе 1 мы ввели понятие нотации «O-большое», которое можно использовать для анализа временной сложности алгоритма. В контексте этого анализа мы рассматриваем следующие временные интервалы:
zz время, необходимое алгоритму для получения предлагаемого решения, на зываемого сертификатом: tr;
zz время, необходимое для проверки предлагаемого решения (сертификата): ts.
Определение сложности задачи
На протяжении многих лет исследовательское сообщество делило задачи на различные категории в зависимости от их сложности. Прежде чем разрабатывать решение, имеет смысл охарактеризовать задачу. Как правило, задачи делятся на три типа:
zz Тип 1. Задачи, для которых доказано существование полиномиального ал горитма.
98 |
Глава 4. Разработка алгоритмов |
zz Тип 2. Задачи, для которых доказано, что они не могут быть решены с по мощью полиномиального алгоритма.
zzТип 3. Задачи, для которых не найден полиномиальный алгоритм, но не до казано, что его не существует.
Рассмотрим различные классы задач:
zz Недетерминированные полиномиальные, NP (non-deterministic polynomial). Чтобы задача была NP-задачей, она должна удовлетворять следующему условию:
yy гарантированно существует полиномиальный алгоритм, который может быть использован для проверки оптимальности варианта решения (сер тификата).
zz Полиномиальные, P (polynominal). Это типы задач, которые можно рассма тривать как подмножество NP. В дополнение к выполнению условия задачи NP задачи P должны удовлетворять еще одному условию:
yy гарантированно существует по крайней мере один полиномиальный ал горитм, который может быть использован для их решения.
Взаимосвязь между классами P и NP показана на следующей диаграмме (рис. 4.1).
Рис. 4.1
Если задача принадлежит к классу NP, то принадлежит ли она так же и к классу P? Это одна из величайших проблем в информатике, которая до сих пор остается нерешенной. Математический инсти тут Клэя включил ее в число Задач тысячелетия. За решение этой проблемы предлагается 1 миллион долларов, так как оно оказало бы значительное влияние на такие области, как искусственный интеллект, криптография и теоретические компьютерные науки (рис. 4.2).
Знакомство с основными концепциями разработки алгоритма |
99 |
Рис. 4.2
Вернемся к списку классов задач.
zz NP-полные (NP-complete). Данная категория содержит самые сложные за дачи из всех NP. NP-полная задача удовлетворяет следующим двум услови ям:
yy не существует известных полиномиальных алгоритмов для генерации сертификата;
yy существуют известные полиномиальные алгоритмы для проверки того, что предлагаемый сертификат является оптимальным.
zzNP-трудные (NP-hard). Эта категория содержит задачи, которые по крайней мере так же сложны, как и любая задача категории NP; при этом они необя зательно принадлежат категории NP.
Теперь попробуем нарисовать диаграмму, чтобы проиллюстрировать различные классы задач (рис. 4.3).
Рис. 4.3
Исследовательскому сообществу еще предстоит доказать, является ли P = NP. И хотя это еще не доказано, весьма вероятно, что P ≠ NP. В таком случае для