Недавно я прошел 11-недельный курс Machine Learning на платформе Coursera. Курс великолепен. Чтобы помочь себе вспомнить материал через много лет, я решил написать краткий конспект, состоящий преимущественно из ключевых слов, поэтому текст ниже будет понятен, скорее всего, только тем, кто сам прошел этот курс.
Supervised learning algorithms
Постановка задачи. Есть входные переменные (x), от которых предположительно зависит выходная переменная (y). Есть набор данных, для которых известны конкретные значения (x) и (y). Цель — найти такую функцию, которая максимально точно будет аппроксимировать зависимость y(x) и, главное, максимально точно предсказывать значения (y) для новых значений (x). Необходимо выбрать модель (т. е. например, функцию, параметризованную некими параметрами), а затем подогнать ее параметры так, чтобы минимизировать отклонения предсказаний модели от реальных экспериментальных данных.
1. Labeled data
Features (x) — переменные, от которых зависит результат (y).
Parameters (Theta) — параметры модели, которые мы хотим оптимизировать.
Labels (y) — результаты, которые должны быть аппроксимированы.
Hypothesis (h_theta) — функция, значения которой сравниваются с (y).
Training examples (x, y) — данные, на которых мы обучаем нашу модель.
Optimization objective — цель оптимизации — функция, которую нужно минимизировать — отклонение предсказаний модели от «опытных данных» training set.
2. Linear regression
Example: housing price prediction based on size and number of bedrooms
Optimization problem.
Cost function (J) — функция, которую мы стремимся минимизировать в процессе обучения; желательно, чтобы функция была «выпуклой» (convex). В линейной регрессии используется то, что у нас называется методом наименьших квадратов.
Gradient descent, batch gradient descent (поиск минимума функции, принцип аналогичен скатыванию шарика по склону горы под действием силы тяжести).
Normal equation — find optimal parameters (Theta) analytically. Матрица X’*X должна быть инвертируемой (invertible). Метод работает только если количество training example’ов больше числа features либо если применяется регуляризация.
Learning rate (alpha) — коэффициент в градиентном спуске.
Polynimial regression = Linear regression + Polynomial features — позволяет аппроксимировать нелинейные зависимости y(x).
Feature scaling and mean normalization — рекомендуется делать практически всегда, чтобы масштабы features были одинаковы.
High bias model — модель, которая слишком «ригидна», плохо аппроксимирует training set.
High variance model — модель, которая очень «пластична», хорошо аппроксимирует training set. Если она плохо плохо аппроксимирует test set, то это называют Overfitting. Overfitting — слишком много features.
Regularization, regularization parameter (lambda) — регуляризация — добавление к cost function слагаемого, которое подавляет high variance / overfitting.
3. Logistic regression
Classification problem, Classifier.
Example: tumor — malignant/benign.
Example: spam classifier: spam/not spam.
Sigmoid function (g), logistic function — hypothesis — диапазон 0…1
Logistic cost function (with logarithms) — для правильной классификации приближается к нулю, для неправильной классификации — стремится к бесконечности.
Decision boundary.
Multiclassification problem: one-versus-all classification — когда проблема классификации не бинарная (да/нет), классификацию строят из нескольких бинарных классификаций. Т. е. если надо разделить example’ы на N>2 классов, то нужно натренировать N классификаторов.
4-5. Neural network
Очень большое число features + нелинейная гипотеза / decision boundary.
Пример: распознавание образов.
Нейрон: дендрит (вход), тело, аксон (выход), синапс (щель между аксоном и дендритом). У нейрона много входов, но один выход.
Layers: Input layer (1), Hidden layer (2), Output layer (3).
Сеть состоит из слоев, соседние слои соединены между собой (каждый нейрон одного слоя с каждым нейроном другого слоя).
Neuron — logistic unit, unit’s output (a), bias unit (1).
Sigmoid function — activation function. a = g(h_theta); h_theta
a(1) = x; a(2) = g(Theta(1)*a(1)); don’t forget bias unit in every layer except the output layer!
Weights (Theta) — матрицы переходов между слоями. Theta(i) соединяет слои (i) и (i+1).
Обучение нейронной сети есть всё та же logistic regression c той же самой cost function, однако градиент cost function J(Theta) вычислить сложнее.
Feedforward (forward propagation) — вычисление cost function (движемся в направлении от input layer к output layer).
Backpropagation — вычисление градиента cost function J(Theta) (движемся в направлении от output layer к input layer).
Чем больше скрытых слоев, тем больше вычислений и выше high variance. Число нейронов в скрытых слоях рекомендуется выбирать одинаковым.
Нейронная сеть отлично подходит для multiclassification problem.
Random initialization, symmetry breaking — необходимо инициализировать Theta случайными числами, иначе сеть не сможет научиться.
Cost function нейронной сети может иметь локальные минимумы, поэтому имеет смысл проводить несколько обучений со случайными Theta.
Gradient check — проверка правильности вычисления градиента J(Theta) в ходе back propagation; в качестве контрольного метода используется метод конечных разностей.
6. Model evaluation
Оценка выбранной модели (лучше/хуже).
Модель определяется количеством features, параметром регуляризации (lambda), числом polynomial features, числом скрытых слоев нейронной сети (и количеством нейронов в них). Эти параметры можно варьировать и получать лучшую или худшую «предсказательную силу» модели. Предсказательную силу можно оценить на наборе тестовых данных — Cross validation set.
Learning qurve — зависимость ошибки (совпадает с cost function за вычетом регуляризационного слагаемого) от размера training set. На этой зависимости хорошо видно различие моделей с high bias и моделей с high variance (у последних увеличение training set дает существенное уменьшение ошибки).
Trainig set — набор данных, на котором мы тренируем модель.
Test set — набор данных, на котором мы тестируем модель.
Error analysis — если модель допускает ошибки в классификации, то имеет смысл проанализировать возможные причины этих ошибок (м. б. отсутствие неких специфических features).
6. Skewed data
Many negative examples and few positiove examples.
Results: True positive, True negative, False positive, False negative
Accuracy, Precision, Recall
F1 score
Accuracy не является хорошим оценочным средством для таких моделей/данных. F1 score позволяет оценить их адекватно.
7. Support Vector Machine (SVM)
Sigmoid function approximation (аппроксимация «кусочно-линейной» функцией упрощает вычисления).
Эта же аппроксимация дает эффект Large margin classification (y = 1 if Theta*x >= 1), т. е. позволяет классифицировать данные более надежно/четко/адекватно.
«Вектором» в названии Support Vector Machine по-видимому называют Theta — ведь скалярное произведение Theta*x определяет значение гипотезы h_theta. Этот вектор смотрит из нуля координат x в направлении от отрицательных результатов в training set (y = 0) к положительным результатам (y = 1).
Kernels: generate new features out of existing ones.
SVM применяют обычно в комбинации с kernels.
Similarity function: выбирают характерные точки (Landmarks) новые features суть близость (proximity) старых точек x к landmarks.
Linear kernel — отсутствие новых features как таковых (отсутствие kernel).
Gaussian kernel — similarity function на основе функции Гаусса. Нужно выбирать параметр функции Гаусса сигма.
Unsupervised learning algorithms
Здесь задачи «более творческие» по сравнению с supervised learning: объединение сущностей по общности их параметров (кластеризация), детектирование аномалий в данных (скорее менее творческая задача), recommender systems — анализ продуктов и предпочтений пользователей. Но они точно так же связаны с оптимизацией-минимизацией.
Unlabeled data — данные из training set не помечены, т. е. features (x) есть, а метки (y) отсутствуют.
8. Clustering problem
Задача разбить данные на заданное количество классов.
Examples: image compression, market segmentation, social network analysis, astronomy.
K-means algorithm (k — the number of clusters we want to get)
Cluster centroids — набор точек близость к которым причисляет точку (x) к тому или иному кластеру.
Random initialization — в начале алгоритма центроиды выбираются из имеющихся точек (x) случайным образом (центроиды должны быть все разные).
Distortion cost function — сумма расстояний между точками кластеров и соответствующими центроидами кластеров.
2-хшаговый алгоритм: 1) cluster assignment 2) centroid move.
Choosing the number of clusters: Elbow method or otherwise the choice based on the application and/or convenience.
8. Principal component analysis (PCA)
Features’ dimentionality reduction
Application example: data compression.
Features могут быть в большей или меньшей степени линейно зависимы между собой (например трехмерные точки, которые приблизительно, с небольшими флуктуациями лежат все в одной плоскости). Тогда можно сократить число features. Делается это путем вычисления базисных векторов (principal components), которые вычисляются из Covariance matrix (Sigma=X*X’).
Singular value decomposition (SVD) позволяет найти собственные векторы (Eigenvectors) этой матрицы covariance matrix.
Из собственных векторов выбираются K штук.
Новые значения features (x_approx) суть проекции старых (x) на выбранные собственные векторы — principal components.
Choosing the number of principal components, % of variance retained (must be near 90…100%) — мера того, насколько сильно аппроксимированные фичи отстоят от реальных фичей.
PCA позволяет сократить требуемый объем памяти и увеличить скорость обучения. Также PCA помогает в визуализации данных, понижая размерность пространства до привычных человеку 3-х или 2-х измерений.
9. Anomaly detection
Обнаружить точки, которые выбиваются из общей массы.
Аномальные точки — те, для которых вероятность параметров менее заданной (epsilon).
Gaussian distribution — вероятность в простейшем случае есть произведение гауссовых распределений по каждой координате в отдельности.
Параметры гауссова распределения — среднее значение и среднеквадратическое отклонение Standard deviation (sigma) — легко вычисляются для любого набора данных. Variance = (sigma squared).
Не всегда распределение данных — нормальное (гауссово). Тогда можно попробовать взять функцию от features (log, возведение в степень, извлечение корня и пр.)
Данные в задачах anomaly detection как правило — skewed data. Поэтому для оценки модели нужно использовать F1 score.
Отличие anomaly detection от supervised learning — в том, что в anomaly detection будущие аномалии непредсказуемы по своим параметрам.
Multivariate Gaussian distribution automatically avoids redundant features (linearly dependent). Задействует covariance matrix (которая должна быть инвертируемой). Предпочтительный вариант, когда features могут оказаться в той или иной степени линейно зависимы между собой.
9. Recommender systems
Пример: выбор продукта, который следует рекомендовать пользователю на основании его предпочтений.
Предпочтения определяются историей прошлых оценок пользователем других продуктов. Вычисляется предсказание оценки пользователем продукта, ранее им не оцененного.
Где взять features продуктов? Вариант 1: придумать из искусственно (Content-based learning).
Cost function как в линейной регрессии (метод наименьших квадратов). В этом случае наш learning, судя по всему, будет supervised.
Где взять features продуктов? Вариант 2: создать из на основе всех оценок всех пользователей (Collaborative filtering and Feature learning). В этом случае, вероятно, наш learning окажется скорее unsupervised.
Cost function минимизируется, но при этом варьируют (оптимизируют) не только parameters (Theta), но и features (X). Соответственно, градиент cost function вычисляют не только по Theta, но и по X. При этом bias unit (1) уже не нужен.
Вся проблема подобной оптимизации также носит название Low-rank matrix factorization.
Рекомендуется применять к данным training set в recommender system mean normalization (а scaling применять не нужно).
10. Big Data
Large datasets.
Stochastic gradient descent + Randomly shuffle training examples. Изменять parameters (Theta) на основании каждого единичного training example. Не сходится точно к глобальному оптимуму, но флуктуирует где-то рядом с ним. По мере схождения к оптимуму рекомендуется постепенно снижать learning rate (alpha).
Online learning — stochastic gradient descent, но training example после использования выбрасывается дабы не тратить ресурсы на его хранение.
Mini-batch gradient descent — для изменения parameters (Theta) использовать небольшие наборы training example’ов.
Parallelism
Map reduce approach — как распределить вычисления между машинами либо ядрами процессора.
11. Pipelining
Photo Optical Character Recognition — распознавание надписей на фотографиях.
Sliding Windows Detection — сканирование фотографии скользящим окном. Окно сдвигается на небольшое число пикселей на каждой итерации.
Text detection classifier — к куску фото в скользящем окне на каждой итерации применяется классификатор, детектирующий наличие надписей.
Character segmentation — разделение надписи на отдельные буквы/символы путем распознавания промежутка между символами (еще один классификатор).
Character recognition — распознавание каждого отдельного символа.
Ceiling analysis — анализ слабого звена в pipeline. Путем ручного улучшения эффективности каждой стадии pipeline до 100%.
11. Artificial data synthesis
Эффективный алгоритм обучения — high variance model + large trainig set. Вопрос: где взять large training set? Можно найти уже имеющийся training set в Интернете либо сгенерировать его из имеющегося маленького training set’а путем внесения в него искажений и шумов.
Прочие замечания
В задачах Machine Vision в качестве features выступают цвета пикселей. Число features в одном traing example равно числу пикселей в картинке, умноженному на число цветовых каналов (хотя канал обычно один, так как чаще всего используют монохромные изображения).