Активное обучение — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники информации )
(Сокращение размерности пространства решений)
Строка 74: Строка 74:
 
Сокращение размерности пространства решений (англ. Version Space Reduction) подразумевает выбор объектов, которые максимально сокращают пространство корректных возможных решений.
 
Сокращение размерности пространства решений (англ. Version Space Reduction) подразумевает выбор объектов, которые максимально сокращают пространство корректных возможных решений.
  
Рассмотрим простой частный случай: пусть имеется выборка точек на отрезке длины $l$, для которых требуется найти пороговый классификатор. Это означает, что заранее известна линейная раздедимость выборки - то есть существует точка $t$, такая что точки $x < t$ принадлежат одному классу, а $x > t$ {{---}} другому. Наивным решением было бы разбиение отрезка на $k$ равных подотрезков, чтобы отправить оракулу по одной точке из каждого подотрезка и получить верный ответ с точностью $l / k$. Гораздо лучшим решением является бинарный поиск, который на каждой итерации сокращает пространство возможных решений вдвое, и необходимая точность $d$ достигается за $\log{\dfrac{l}{d}}$ запросов.
+
Рассмотрим простой частный случай: пусть имеется выборка точек на отрезке длины $l$, для которых требуется найти пороговый классификатор. Это означает, что заранее известна линейная раздедимость выборки - то есть существует точка $t$, такая что точки $x < t$ принадлежат одному классу, а $x > t$ {{---}} другому. Наивным решением было бы разбиение отрезка на $k$ равных подотрезков, чтобы отправить оракулу по одной точке из каждого подотрезка и получить верный ответ с точностью $\dfrac{l}{k}$. Гораздо лучшим решением является бинарный поиск, который на каждой итерации сокращает пространство возможных решений вдвое, и необходимая точность $d$ достигается за $\log{\dfrac{l}{d}}$ запросов.
  
 
== См. также ==
 
== См. также ==

Версия 22:03, 2 февраля 2020

Активное обучение (англ. Active learning) — область машинного обучения, где в отличие от обучения с учителем имеется набор неразмеченных данных и оракул, способный размечать данные. Зачастую обращение к оракулу затратно по времени или другим ресурсам. Требуется решить задачу, минимизируя количество обращений к оракулу.

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

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


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

Дано множество неразмеченных данных:

$X = \{x_1, ..., x_n\}$

Множество меток:

$Y = \{y_1, ..., y_m\}$

Оракул:

$O : X \rightarrow Y$ — функция, которая по объекту возвращает его метку.

Требуется восстановить функцию $a : X \rightarrow Y$, минимизируя количество обращений к оракулу.

На каждой итерации алгоритм фиксирует три множества:

1. $X_{unlabeled}$ — множество еще не размеченных объектов.

2. $X_{labeled}$ — множество размеченных, которые удовлетворяют некоторому порогу уверенности в классификации.

3. $X_{query}$ — множество объектов, которые подаются на вход оракулу. Заметим, что не всегда $X_{query} \subset X_{unlabeled}$, поскольку алгоритм может сам синтезировать объекты.

Основные стратегии

  • Отбор объектов из выборки (англ. Pool-based active learning). Имеется некоторая выборка, и алгоритм использует объекты из нее в качестве запросов к оракулу. В данной стратегии каждому объекту присваивается степень информативности — сколько выгоды принесет информация об истинной метке объекта, и оракулу отправляются самые информативные объекты.
  • Отбор объектов из потока (англ. Selective sampling). Алгоритм пользуется не статической выборкой, а потоком данных, и для каждого объекта из потока принимается решение, запрашивать оракула на этом объекте или самому присваивать метку согласно текущему классификатору.
  • Синтез объектов (англ. Query synthesis). Вместо использования заранее заданных объектов, алгоритм сам конструирует объекты и подает их на вход оракулу. Например, если объекты - это вектора в n-мерном пространстве, разделенные гиперплоскостью и решается задача бинарной классикации, имеет смысл давать оракулу на вход синтезированные вектора, близкие к границе.

Методы выбора сэмплирования

Выбор по степени неуверенности

Выбор по степени неуверенности (англ. Uncertainty Sampling) — метод отбора объектов из выборки, где самыми информативными объектами считаются те, на которых текущий алгоритм меньше всего уверен в верности классификации. Для этого необходимо задать меру неуверенности в классификации на каждом объекте.

Зафиксируем модель на некотором этапе обучения и обозначим за $P(y | x)$ вероятность того, что объект $x$ принадлежит классу $y$. Приведем основные меры неуверенности для текущей классификации:

  • Максимальная энтропия (англ. Maximum Entropy)

$\Phi_{ENT}(x) = - \sum\limits_y{P(y | x) \log{P(y | x)}}$ — энтропия классификации на объекте $x$. Чем больше энтропия — тем больше неуверенность в классификации.

  • Минимальный отступ (англ. Smallest Margin)

$\Phi_{M}(x) = P(y_1 | x) - P(y_2 | x)$ — отступ (англ. margin) от $y_1$ — самого вероятного класса до $y_2$ — второго по вероятности класса. Очевидно, что если отступ велик, то велика и уверенность, потому что один класс заметно выигрывает у всех остальных. Поэтому имеет смысл запрашивать оракула на объектах с минимальным отступом.

  • Минимальная уверенность (англ. Least Confidence)

$\Phi_{LC}(x) = 1 - P(y_1 | x)$,  где $y_1$ — наиболее вероятный класс. Интересующие нас объекты — объекты с минимальной уверенностью.

Заметим, что в случае бинарной классификации эти методы эквивалентны.

Сэмплирование по несогласию в комитете

Сэмплирование по несогласию в комитете (англ. Query By Comittee) — метод, в котором алгоритм оперирует не одной моделью, а сразу несколькими, которые формируют комитет. Каждая из моделей обучена на размеченном множестве и принимает участие в общем голосовании на неразмеченных объектах. Идея состоит в том, что те объекты, на которых модели более всего расходятся в своих решениях, являются самыми информативными.

Множество моделей — $A^T = \{a_1, .., a_T\}$

Алгоритм выбирает те объекты, на которых достигается максимум энтропии:

$x_{informative} = arg \min\limits_x{P(y | x) \log{P(y | x)}}$

Здесь $P(y | x) = \dfrac{1}{T} \sum\limits_{a \in A^T}{[a(x) = y]}$

Сокращение размерности пространства решений

Сокращение размерности пространства решений (англ. Version Space Reduction) подразумевает выбор объектов, которые максимально сокращают пространство корректных возможных решений.

Рассмотрим простой частный случай: пусть имеется выборка точек на отрезке длины $l$, для которых требуется найти пороговый классификатор. Это означает, что заранее известна линейная раздедимость выборки - то есть существует точка $t$, такая что точки $x < t$ принадлежат одному классу, а $x > t$ — другому. Наивным решением было бы разбиение отрезка на $k$ равных подотрезков, чтобы отправить оракулу по одной точке из каждого подотрезка и получить верный ответ с точностью $\dfrac{l}{k}$. Гораздо лучшим решением является бинарный поиск, который на каждой итерации сокращает пространство возможных решений вдвое, и необходимая точность $d$ достигается за $\log{\dfrac{l}{d}}$ запросов.

См. также

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