52
правки
Изменения
Нет описания правки
[[Файл:al_russianAl_russian_2.jpg png | справа | 480пкс | мини | Схема отбора из выборки в активном обучении]]
'''Активное обучение''' (англ. ''Active active learning'') {{---}} область машинного обучения, где алгоритм взаимодействует с некоторым источником информации, или '''оракулом''', способным размечать запрошенные данные.
Зачастую обращение к оракулу затратно по времени или другим ресурсам, и требуется решить задачу, минимизируя количество обращений к оракулу.
В связи с этим одной из центральных задач активного обучения становится '''отбор объектов''' (англ. ''Samplingsampling'') {{---}} выбор тех объектов, которые следует отправить оракулу для получения достоверной информации об их классификации. От грамотности отбора зависит время работы алгоритма, качество классификации и затраты на внешние ресурсы.
Ниже будет рассматриваться задача классификации для активного обучения, но следует отметить, что задача регрессии формализуется аналогично.
== Постановка задачи классификации для активного обучения ==
Дано множество неразмеченных данных:
На каждой итерации алгоритм фиксирует три множества:
== Основные стратегии ==
* '''Отбор объектов из выборки''' (англ. ''Poolpool-based active learning''). Имеется некоторая выборка, и алгоритм использует объекты из нее в качестве запросов к оракулу. В данной стратегии каждому объекту присваивается степень информативности {{---}} сколько выгоды принесет информация об истинной метке объекта, и оракулу отправляются самые информативные объекты. Описанные ниже методы отбора объектов имеют отношение именно к этой стратегии.* '''Отбор объектов из потока''' (англ. ''Selective selective sampling''). Алгоритм пользуется не статической выборкой, а потоком данных, и для каждого объекта из потока принимается решение, запрашивать оракула на этом объекте или нет. В случае, если принято решение запросить оракула, объект и его метка используются в дальнейшем обучении модели, в противном случае объект просто отбрасывается. В отличие от отбора объектов из выборки отбор из потока не строит никаких предположений насчет плотности распределения объектов, не хранит сами объекты и работает значительно быстрее.* '''Синтез объектов''' (англ. ''Query query synthesis''). Вместо использования заранее заданных объектов, алгоритм сам конструирует объекты и подает их на вход оракулу. Например, если объекты {{---}} это вектора в n-мерном пространстве, разделенные гиперплоскостью и решается задача бинарной классикации, имеет смысл давать оракулу на вход синтезированные вектора, близкие к границе.
== Методы отбора объектов ==
=== Выбор по степени неуверенности ===
Выбор по степени неуверенности (англ. ''Uncertainty Samplinguncertainty sampling'') {{---}} метод отбора объектов из выборки, где самыми информативными объектами считаются те, на которых текущий алгоритм меньше всего уверен в верности классификации. Для этого необходимо задать меру неуверенности в классификации на каждом объекте.
Зафиксируем модель на некотором этапе обучения и обозначим за $P(y | x)$ вероятность того, что объект $x$ принадлежит классу $y$. Приведем основные меры неуверенности для текущей классификации:
* '''Максимальная энтропия''' (англ. ''Maximum Entropymaximum entropy'')
:Энтропия классификации на объекте $x$:
:Чем больше энтропия {{---}} тем больше неуверенность в классификации.
* '''Минимальный отступ''' (англ. ''Smallest Marginsmallest margin'')
:Отступ (англ. ''margin'') от $y_1$ {{---}} самого вероятного класса до $y_2$ {{---}} второго по вероятности класса:
:Очевидно, что если отступ велик, то велика и уверенность, потому что один класс заметно выигрывает у всех остальных. Поэтому имеет смысл запрашивать оракула на объектах с минимальным отступом.
* '''Минимальная уверенность''' (англ. ''Least Confidenceleast confidence'')
:Функция неуверенности:
=== Отбор по несогласию в комитете ===
Отбор по несогласию в комитете (англ. ''Query By Comitteequery by comittee'') {{---}} метод, в котором алгоритм оперирует не одной моделью, а сразу несколькими, которые формируют комитет. Каждая из моделей обучена на размеченном множестве и принимает участие в общем голосовании на неразмеченных объектах. Идея состоит в том, что те объекты, на которых модели более всего расходятся в своих решениях, являются самыми информативными.
Множество моделей {{---}} $A^T = \{a_1, .., a_T\}$.
=== Сокращение размерности пространства решений ===
Сокращение размерности пространства решений (англ. ''Version Space Reductionversion space reduction'') подразумевает выбор объектов, которые максимально сокращают пространство возможных решений.
Рассмотрим простой частный случай: пусть имеется выборка точек на отрезке длины $l$, для которых требуется найти пороговый классификатор. Это означает, что заранее известна линейная разделимость выборки {{---}} то есть существует точка $t$, такая что точки $x < t$ принадлежат одному классу, а $x > t$ {{---}} другому. Наивным решением было бы разбиение отрезка на $k$ равных подотрезков, чтобы отправить оракулу по одной точке из каждого подотрезка и получить верный ответ с точностью $\dfrac{l}{k}$. Гораздо лучшим решением является бинарный поиск, который на каждой итерации сокращает пространство возможных решений вдвое, и необходимая точность $d$ достигается за $\log{\dfrac{l}{d}}$ запросов.
=== Максимизация ожидаемого влияния на модель ===
Пусть текущая модель имеет параметр $\theta$, который мы стремимся оптимизировать, чтобы уменьшить функцию потерь $L$. Тогда имеет смысл запрашивать те объекты, которые максимизируют влияние на модель (англ. ''Expected Model Changeexpected model change''). Степень влияния можно оценивать градиентом функционала потерь {{---}} $\nabla_\theta L$. Тогда мера информативности объекта:
$\Phi(x) = \sum\limits_y{P(y | x) \cdot || \nabla_\theta L_{+(x, y)} ||}$.
=== Ожидаемое сокращение ошибки ===
Идея данного метода (англ. ''Expected Error Reductionexpected error reduction'') состоит в том, чтобы выбрать такой объект, после добавления которого в обучающее множество, максимизируется уверенность в классификации неразмеченной выборки. Уверенность в классификации выражается следующей функцией:
$\Phi(x) = \sum\limits_{y \in Y}{(P(y | x) \sum\limits_{u \in X}{P(a_{xy}(u) | u)})}$.
== Активное обучение с исследовательскими действиями ==
У рассмотренных выше стратегий отборв отбора есть недостатки: в пространстве $X$ могут оставаться неисследованные области, вследствие чего снижается качество и увеличивается время обучения. Эвристикой, позволяющей решить эту проблему, является выбор случайных объектов, комбинированный с детерминированным выбором по степени информативности.
Есть два алгоритма обертки над любой стратегией отбора {{---}} алгоритм $\varepsilon$-active и алгоритм экспоненциального градиента (англ. ''Exponential exponential gradient''). Алгоритм $\varepsilon$-active {{---}} это базовый вариант, в котором предлагается на каждой итерации производить следующие шаги:
# Выбрать неразмеченный объект $x$ случайно с вероятностью $\varepsilon$ или $x = arg \max\limits_{u \in X}{\Phi(u)}$ с вероятностью $1 - \varepsilon$. <br> Здесь $\Phi(u)$ обозначает степень неуверенности на объекте $u$.
