Обучение с частичным привлечением учителя

Понятие машинного обучения в искусственном интеллекте

Определение:

Обучение с частичным привлечением учителя (англ. semi-supervised learning) — разновидность обучения с учителем, которое также использует неразмеченные данные для тренировки — обычно небольшое количество размеченных данных и большое количество неразмеченных данных.

Основная идея

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

Постановка задачи обучения

Дано

• Множество данных $X = \{x_1, x_2, ... , x_m\}$ и множество меток $Y = \{y_1, y_2, ... , y_m\}$
• Размеченные данные вида $(X_l, Y_l) = \{(x_{1:l}, y_{1:l})\}$
• Множество неразмеченных данных $X_u = \{x_{l+1:n}\}$, используемых в обучении
• Как правило, $l \ll n$
• Множество неразмеченных данных $X_{test} = \{x_{n+1:m}\}$, не используемых в обучении (тестовая выборка)

Найти

• Найти решающую функцию $a: X → Y$, где при нахождении функции подразумевается применение как $(X_l, Y_l)$, так и $X_u$.

Предположения, используемые SSL

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

Предположение плавности (Smoothness Assumption)

Smoothness Assumption — две точки $x_1$, $x_2$ в области высокой плотности, лежащие близко друг от друга, с большей вероятностью имеют одинаковые метки $y_1$, $y_2$.

Более того, исходя из транзитивности, если две точки связаны между собой точками из области высокой плотности (например, принадлежат одному кластеру), то они также, вероятно, размечены одинаково. С другой стороны, предположение даёт преимущество для разграничения в регионах с низкой плотностью, там где меньше близко разположенных точек, но больше вероятность принадлежности к разным классам.

Предположение кластеризованности (Cluster Assumption)

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

Cluster Assumption — две точки $x_1$, $x_2$ из одного кластера с большей вероятностью имеют одинаковые метки $y_1$, $y_2$.

Предположение обосновывается на явном существовании классов: если существует плотный континуум объектов, маловероятно, что он будет разделён на разные классы. Следует отметить, что предположение не подразумевает формирования одного компактного кластера одним классом, но и не рассматривает два объекта разных классов в одном кластере.

Предположение избыточности (Manifold Assumption)

Manifold Assumption — избыточность данных высокой размерности способствует понижению размерности.

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

Подходы к решению задачи

Самообучение (Self Training)

Алгоритм

1. Обучить $f$ с помощью $(X_l, Y_l)$
2. Спрогнозировать $x \in X_u$
3. Добавить $(x, f(x))$ к размеченным данным
4. Повторить

Алгоритм основан на предположении, что достоверные прогнозы, формируемые на шаге 2 — верны.

Вариации самообучения

• Добавление нескольких наиболее достоверных $(x, f(x))$ к размеченным данным
• Добавление всех $(x, f(x))$ к размеченным данным
• Добавление всех $(x, f(x))$ к размеченным данным, взвешивание достоверности каждого $x$

Достоинства метода

• Наиболее простой метод semi-supervised обучения
• Метод может быть обёрткой для более сложных алгоритмов классификации
• Часто используется в прикладных задачах, таких как процессинг естественного языка

Недостатки

• Негативное влияние ошибочных прогнозов усиливается с обучением. В таком случае существуют эвристические решения, например "удаление" метки с объекта, достоверность которого оказалась ниже определённого порога
• Трудно достичь сходимости алгоритма. Однако, существуют частные случаи, когда самообучение эквивалентно EM-алгоритму, а также при использовании функций (например, линейных), где известно решение в виде сходящегося алгоритма

Совместное обучение (Co-training)

Совместное обучение является расширением самообучения, при котором несколько классификаторов прорабатывают разные (в идеале, непересекающиеся) множества признаков и генерируют размеченные примеры друг для друга.

Алгоритм

1. Обучить два классификатора: $f^{(1)}$ с помощью $(X_l^{(1)}, Y_l)$, $f^{(2)}$ с помощью $(X_l^{(2)}, Y_l)$
2. Классифицировать множество $X_u$ с $f^{(1)}$ и $f^{(2)}$ независимо
3. Добавить $k$ наиболее достоверных прогнозов $(x, f^{(1)}(x))$ из $f^{(1)}$ к данным, размеченным с помощью $f^{(2)}$
4. Добавить $k$ наиболее достоверных прогнозов $(x, f^{(2)}(x))$ из $f^{(2)}$ к данным, размеченным с помощью $f^{(1)}$
5. Повторить

Преимущества

• Подходит почти ко всем известным классификаторам в качестве обёртки
• Не так сильна чувствительность к ошибочным прогнозам, по-сравнению с self-training

Недостатки

• Естественное разделение признаков не всегда существует. В таком случае можно использовать fake feature split — случайное искуственное разделение
• Необхоимо искать эффективные модели, когда приходится использовать признаки из нескольких множеств

Полуавтоматические SVM

Зазор, разделяющий неразмеченные данные

Полуавтоматические SVM (англ. Semi-supervised SVMs, S3VMs), они же транстуктивные SVM (TSVMs) решают задачу максимизации зазора (margin) между неразмеченными данными.

Идея

• Перечислить все $2^u$ возможные способы разметки множества $X_u$
• Построить стандартную SVM для каждой разметки (и для $X_l$)
• Взять SVM с наибольшим зазором

Постановка задачи

• Два класса $y \in {+1, -1}$
• Размеченные данные $(X_l, Y_l)$
• Ядро $K$
• Гильбертово пространство функций $H_K$ (RKHS)

С помощью SVM найти функцию $f(x)=h(x)+b$, где $h \in H_K$ и классифицировать $x$ с помощью $sign(f(x))$

Алгоритм

1. Входные данные: ядро $K$, веса $\lambda_1, \lambda_2, (X_l, Y_l), X_u$ 2. Решим задачу оптимизации для $f(x) = h(x) + b, h(x) \in H_K$

${min}_f \sum\limits_{i = 1}^{l} (1 - y_i f(x_i))_+ + \lambda_1\|h\|^2_{H_K} + \lambda_2 \sum\limits_{i = l + 1}^n (1 - |f(x_i)|)_+ $
такую, что $\frac{1}{n-l}\sum\limits_{i=l+1}^n f(x_i) = \frac{1}{l}\sum\limits_{i = 1}^{l}y_i$

4. Классифицируем новый объект $x$ из тестового множества, используя $sign(f(x))$

Достоинства S3VM

• Применимо везде, где применимы классические SVM

Недостатки

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

Алгоритмы на основе графов

Данные можно представить в виде графа, построенного с использованием знаний в предметной области или на основе сходства объектов.

Дано

• Вершины $X_l \cup X_u$
• Рёбра, вычисленные исходя из признаков, например
  • $k$ ближайших соседей
  • Полный граф, веса рёбер которого убывают с расстоянием, $w = exp(-\|x_i - x_j\|^2/\sigma^2)$

Найти сходство по всем путям.

Регуляризация избыточности
1. Входные данные: ядро $K$, веса $\lambda_1, \lambda_2, (X_l, Y_l), X_u$
2. Построим граф сходств $W$ из вершин $X_l, X_u$, вычислим Лапласиан графа $\Delta$
3. Решим задачу оптимизации для $f(x) = h(x) + b, h(x) \in H_K$

${min}_f \sum\limits_{i = 1}^l (1 - y_i f(x_i))_+ + \lambda_1\|h\|^2_{H_K} + \lambda_2 f_{1:n}^T \Delta f_{1:n} $

4. Классифицируем новый объект $x$ из тестового множества, используя $sign(f(x))$

Достоинства алгоритмов на графах

• Ясный математический аппарат
• Высокая эффективность, когда граф соответствует задаче
• Можно использовать ориентированные графы

Недостатки

• Низкая эффективность при плохом постоении графа
• Зависимость от структуры графа и весов рёбер

Источники информации

1. Википедия — Обучение с частичным привлечением учителя
2. Semi-SuperVised Learning Tutorial
3. MIT Press — Semi-Supervised Learning