1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|definition=
'''Обучение с частичным привлечением учителя''' (англ. semi-supervised learning, SSL) {{---}} разновидность [[Общие понятия#Классификация задач машинного обучения|обучения с учителем]], которое помимо размеченных данных для обучения также использует неразмеченные данные {{---}} обычно в сравнительно большем количестве, чем размеченные.
}}
== Основная идея ==
'''Дано''' <br />
* Множество данных $X = \{x_1, x_2, ... , x_m\}$ и множество меток $Y = \{y_1, y_2, ... , y_my_l\}$
* Размеченные данные вида $(X_l, Y_l) = \{(x_{1:l}, y_{1:l})\}$
* Множество неразмеченных данных $X_u = \{x_{l+1:n}\}$, используемых в обучении
=== Предположение кластеризованности (Cluster Assumption) ===
Допустим, что данные каждого из класса образуют [[Кластеризация|кластеры]]. Тогда Если использовать алгоритм кластеризации, используя размеченные данные для присвоения меток кластерам, тогда неразмеченные данные могут быть полезны в более точном нахождении границ этих кластеров, если использовать алгоритм кластеризации и использовать размеченные данные для присвоения меток кластерам.
'''Cluster Assumption''' {{---}} ''две точки $x_1$, $x_2$ из одного кластера с большей вероятностью имеют одинаковые метки $y_1$, $y_2$.''
=== Предположение избыточности (Manifold Assumption) ===
[[File:Manifold example.png|thumb|400px|Нелинейное снижение размерности (isomap) формирует томографическое предствление вариантов изображений трёхмерного объекта, используя два угловых параметра: азимут и высоту. Интерполяция изображений (A), экстраполяция (B) и аналогия (C) могут быть вычислены при помощи линейных операций в пространстве признаков.]]
'''Manifold Assumption''' {{---}} ''избыточность данных высокой размерности способствует [[Уменьшение размерности|понижению размерности]].''
Это предположение применимо, когда измерения данных избыточны, то есть генерируются определенным процессом, имеющим только несколько степеней свободы. Иначе говоря, вместо использования предположения, что данные могут представлять из себя любые объекты из многомерного пространства (например, множество из всех возможных изображений размером 1 мегапиксель, включая белый шум), легче представить эти данные в пространстве более низкой размерности, исключая разными способами конфигурации пикселей, которые не характерны для конкретных данных. В этом случае неразмеченные данные позволяют изучить генерирующий процесс и за счёт этого снизить размерность, что упрощает, например, привязку предположения плавности. '''Пример''' Рассмотрим задачу обнаружения признаков на примере перцепции. Множество двухмерных отображений трёхмерного объекта со всех возможных углов обзора имеет весьма высокую размерность, будучи представленным в виде массивов изображений в памяти вычислительной машины; чёрно-белые картинки размером 32x32 пикселя можно понимать как точки 1024-мерного пространства углов обзора (пространство входных данных). Более значимая для перцепции структура (пространство признаков), однако, может гораздо более низкую размерность: эти же изображения могут лежать в 2-мерном многообразии, параметризованном с помощью углов обзора (см. иллюстрацию). Другим примером задач, когда естественные данные являются избыточными, является [[Векторное представление слов|векторное представление слов]] и [[Обработка естественного языка|обработка естественного языка]].
== Подходы к решению задачи ==
* Негативное влияние ошибочных прогнозов усиливается с обучением. В таком случае существуют эвристические решения, например "удаление" метки с объекта, достоверность прогноза которого оказалась ниже определённого порога
* Трудно достичь сходимости алгоритма. Однако, существуют частные случаи, когда самообучение эквивалентно работе [[EM-алгоритм|EM-алгоритма]], а также при использовании например его модификация под байесовский классификатор, использующий неразмеченные данные. Также у задач, использующих некоторые классы функций (например, линейныхлинейные), где известно решение существуют решения в виде сходящегося алгоритма.
=== Совместное обучение (Co-training) ===
'''Разделение признаков (feature split)''' <br>
Метод совместного обучение обучения предполагает, что каждый объект имеет два множества признаков $x = [x^{(1)}; x^{(2)}]$, разделение между которыми может быть как естественным, так и искусственным. Примером объекта с естественным разделением признаков может послужить веб-страница, содержащая текст и изображения. Два независимых классификатора обучаются по двум множествам признаков: первый анализирует текст, второй {{---}} изображения.
'''Предположения, используемые в совместном обучении'''
* Подходит почти ко всем известным классификаторам в качестве обёртки
* Не так сильна чувствительность к ошибочным прогнозам, по-сравнению с self-training
'''Недостатки'''
'''Пример генеративной модели'''
Параметры модели: $\theta = \big{\{}w_1, w_2, \mu_1, \mu_2, \sum_1, \sum_2\big{\}}$
Модель:
$p(x, y|\theta) = p(y|\theta)p(x|y,\theta) = w_yN\big(x;\mu_y,\sum_y\big)$
Классификация:
$p(y|x,\theta) = \large{\frac{p(x,y|\theta)}{\sum_{y'}p(x,y'|\theta)}}$
Разберём пример двоичной классификации с использованием принципа максимального правдоподобия (''MLE''). Размеченные данные имеют вид <br>$\log p(X_l, Y_l|\theta) = \sum\limits_{i = 1}^l \log p(y_i|\theta)p(x_i|y_i, \theta)$ <br>Здесь в качестве оценки MLE для $\theta$ возьмём тривиальные величины: частота, выборочное среднее, выборочная ковариация. Размеченные и неразмеченные данные: <br>$\log p(X_l, Y_l, X_u|\theta) = \sum\limits_{i = 1}^l \log p(y_i|\theta)p(x_i|y_i, \theta) + \sum\limits_{i = l+1}^{l+u} \log \big(\sum\limits_{y=1}^2 p(y|\theta)p(x_i|y, \theta)\big)$ <br>Теперь, с появлением скрытых переменных, оценка MLE теряет тривиальность, однако для поиска локального оптимума можно использовать [[EM-алгоритм|EM-алгоритм]]. '''Достоинствагенеративных моделей'''
* Гереативные модели очень эффективны, если составленная модель близка к правильной
=== Полуавтоматические [[Метод опорных векторов (SVM)|опорные вектора]] (S3VM) ===
[[File:S3VM-margin.png|thumb|300px400px|Зазор, разделяющий неразмеченные данные]]
Полуавтоматические SVM (англ. ''Semi-supervised SVMs'', ''S3VMs''), они же ''трансдуктивные SVM'' (TSVMs) решают задачу максимизации зазора (''margin'') между неразмеченными данными.
* Трудности в оптимизации
* Алгоритм может сходиться к неправильной (''плохой'') целевой функции
* Менее мощный подход, по-сравнению с алгоритмами на графах и генеративными моделями, т. е. потенциально менее эффективное обучение
=== Алгоритмы на основе [[Теория графов|графов]] ===
[[File:digits Euclidean.png|thumb|400px|Изображения рукописных цифр. <br>Слева {{---}} две цифры с большим евклидовым расстоянием, но одинаковой меткой класса. <br>Справа {{---}} те же цифры, "соединённые" неразмеченной последовательностью (путь в графе), где каждые две соседние цифры имеют малое евклидово расстояние.]]
[[File:digits Euclidean graph.png|thumb|400px|Граф, построенный на множестве рукописных цифр "1" и "2".]]
Данные можно представить в виде графа, построенного с использованием знаний в предметной области или на основе сходства объектов.
4. Классифицируем новый объект $x$ из тестового множества, используя $sign(f(x))$
'''Пример'''
Графы, формирующиеся в процессе обучения, как правило, достаточно объёмны для графического отображения и человеческого восприятия. Для большей ясности рассмотрим множество данных, состоящее только из рукописных цифр "1" и "2". Критерием сходства объектов послужит евклидово расстояние, которое бывает особенно полезно при поиске локального сходства. Если такое расстояние между объектами достаточно мало, мы можем предположить, что объекты принадлежат одному классу. На основе расстояния можно построить [[Метрический классификатор и метод ближайших соседей|KNN]]-граф (см. иллюстрацию), где объекты с малым евклидовым расстоянием будут соединены рёбрами. Чем больше имеется неразмеченных данных, схожих с размеченными (см. пример с цифрой "2"), тем больше соотвествующих рёбер, и, следовательно, более высокая точность классификации.
'''Достоинства алгоритмов на графах'''
'''Недостатки'''
* Низкая эффективность при плохом постоении построении графа
* Зависимость от структуры графа и весов рёбер
# [http://pages.cs.wisc.edu/~jerryzhu/pub/sslicml07.pdf Semi-SuperVised Learning Tutorial]
# [https://www.molgen.mpg.de/3659531/MITPress--SemiSupervised-Learning.pdf MIT Press {{---}} Semi-Supervised Learning]
# [http://web.mit.edu/cocosci/Papers/man_nips.pdf Mapping a manifold of perceptual observations]
# [http://pages.cs.wisc.edu/~jerryzhu/pub/thesis.pdf Semi-Supervised Learning with Graphs]
[[Категория:Машинное обучение]]
[[Категория:Обучение с частичным привлечением учителя]]
