Изменения

'''Активное обучение''' (англ[[Файл:Al_russian_2. ''Active learning'') {{---}} область машинного обучения, где png | справа | 480пкс | мини | Схема отбора из выборки в отличие от обучения с учителем имеется набор неразмеченных данных и оракул, способный размечать данные. Зачастую обращение к оракулу затратно по времени или другим ресурсам. Требуется решить задачу, минимизируя количество обращений к оракулу.активном обучении]]

Для вызова оракула обычно требуется привлечение человеческих ресурсов'''Активное обучение''' (англ. В роли оракула может выступать эксперт''active learning'') {{---}} область машинного обучения, размечающий текстовые документыгде алгоритм взаимодействует с некоторым источником информации, изображения или видеозаписи. Помимо временных затрат могут быть и значительные финансовые'''оракулом''', например, исследование химического соединения или реакцииспособным размечать запрошенные данные.

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

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

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

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

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

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

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

* '''Максимальная энтропия ''' (англ. ''Maximum Entropymaximum entropy'') :Энтропия классификации на объекте $x$:

:$\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)$ {{---}} * '''Минимальный отступ ''' (англ. ''smallest margin'') от $y_1$ {{---}} самого вероятного класса до $y_2$ {{---}} второго по вероятности класса. Очевидно, что если отступ велик, то велика и уверенность, потому что один класс заметно выигрывает у всех остальных. Поэтому имеет смысл запрашивать оракула на объектах с минимальным отступом.

* Минимальная уверенность :Отступ (англ. ''Least Confidencemargin'')от $y_1$ {{---}} самого вероятного класса до $y_2$ {{---}} второго по вероятности класса:

:$\Phi_{M}(x) = P(y_1 | x) - P(y_2 | x)$. :Очевидно, что если отступ велик, то велика и уверенность, потому что один класс заметно выигрывает у всех остальных. Поэтому имеет смысл запрашивать оракула на объектах с минимальным отступом. * '''Минимальная уверенность''' (англ. ''least confidence'') :Функция неуверенности: :$\Phi_{LC}(x) = 1 - P(y_1 | x)$,  где  :$y_1$ {{---}} наиболее вероятный класс. Интересующие нас объекты {{---}} объекты с минимальной уверенностью, то есть с максимальным $\Phi_{LC}$.

=== Сэмплирование = Взвешивание по плотности ==== Одной из проблем описанного выше метода может являться то, что алгоритм часто будет отдавать оракулу шумы {{---}} те объекты, которые не соответствуют основному распределению в выборке. Так как шумы являются нетипичными в контексте выборки объектами, модель может быть неуверена в их классификации, в то время как для решения основной задачи их классификация не очень полезна. Вокруг шумов плотность распределения мала, и вследствие этого применяется эвристика '''взвешивание по плотности''' где предпочтение отдается тем объектам, в которых плотность больше. Таким образом, наиболее информативными объектами будут считаться: $x_{informative} = arg \max\limits_x{\Phi(x) p(x)}$, где $\Phi(x)$ {{---}} мера неуверенности, а $p(x)$ {{---}} эмпирическая плотность в точке $x$. === Отбор по несогласию в комитете ===

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

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

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

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

Сокращение размерности пространства решений (англ. ''Version Space Reductionversion space reduction'') подразумевает выбор объектов, которые максимально сокращают пространство корректных возможных решений. Рассмотрим простой частный случай: пусть имеется выборка точек на отрезке длины $l$, для которых требуется найти пороговый классификатор. Это означает, что заранее известна линейная разделимость выборки {{---}} то есть существует точка $t$, такая что точки $x < t$ принадлежат одному классу, а $x > t$ {{---}} другому. Наивным решением было бы разбиение отрезка на $k$ равных подотрезков, чтобы отправить оракулу по одной точке из каждого подотрезка и получить верный ответ с точностью $\dfrac{l}{k}$. Гораздо лучшим решением является бинарный поиск, который на каждой итерации сокращает пространство возможных решений вдвое, и необходимая точность $d$ достигается за $\log{\dfrac{l}{d}}$ запросов. === Максимизация ожидаемого влияния на модель === Пусть текущая модель имеет параметр $\theta$, который мы стремимся оптимизировать, чтобы уменьшить функцию потерь $L$. Тогда имеет смысл запрашивать те объекты, которые максимизируют влияние на модель (англ. ''expected model change'').  Степень влияния можно оценивать градиентом функционала потерь {{---}} $\nabla_\theta L$. Тогда мера информативности объекта: $\Phi(x) = \sum\limits_y{P(y | x) \cdot || \nabla_\theta L_{+(x, y)} ||}$. Здесь $L_{+(x, y)}$ обозначает функцию потерь на выборке дополненной парой $(x, y)$. При этом естественно предполагать, что на каждой итерации модель обучена, и параметр  $\theta$ оптимален, что значит, что $\nabla_\theta L \simeq 0$. Заметим также, что если $L$ линейно зависит от одномерных функций потерь по каждому объекту, например $L$ {{---}} среднее квадратичное отклонение, тогда остается посчитать градиент $L$ всего в одной точке {{---}} $x$, поскольку $L_{+(x, y)} = L_T + L_{(x, y)} \simeq L_{(x, y)}$ вместо подсчета $L$ на всем тренировочном множестве $T$. === Ожидаемое сокращение ошибки === Идея данного метода (англ. ''expected error reduction'') состоит в том, чтобы выбрать такой объект, после добавления которого в обучающее множество, максимизируется уверенность в классификации неразмеченной выборки. Уверенность в классификации выражается следующей функцией: $\Phi(x) = \sum\limits_{y \in Y}{(P(y | x) \sum\limits_{u \in X}{P(a_{xy}(u) | u)})}$. Формула выше может быть интерпретирована как матожидание уверенности нового классификатора (учитывающего метку объекта $x$) на оставшемся неразмеченном множестве. Существует мнение, что этот метод более устойчив, чем предыдущие, поскольку он не склонен подавать на вход оракулу шумы, и явно увеличивает уверенность классификатора. == Активное обучение с исследовательскими действиями == У рассмотренных выше стратегий отбора есть недостатки: в пространстве $X$ могут оставаться неисследованные области, вследствие чего снижается качество и увеличивается время обучения. Эвристикой, позволяющей решить эту проблему, является выбор случайных объектов, комбинированный с детерминированным выбором по степени информативности. Есть два алгоритма обертки над любой стратегией отбора  {{---}} алгоритм $\varepsilon$-active и алгоритм экспоненциального градиента (англ. ''exponential gradient''). Алгоритм $\varepsilon$-active {{---}} это базовый вариант, в котором предлагается на каждой итерации производить следующие шаги: # Выбрать неразмеченный объект $x$ случайно с вероятностью $\varepsilon$ или $x = arg \max\limits_{u \in X}{\Phi(u)}$ с вероятностью  $1 - \varepsilon$. <br> Здесь $\Phi(u)$ обозначает степень неуверенности на объекте $u$.# Запросить оракула на объекте $x$ и получить его метку $y$.# Дообучить текущую модель на еще одном примере $\langle x, y \rangle$.

Рассмотрим простой частный случай: пусть имеется выборка точек на отрезке длины Алгоритм экспоненциального градиента является улучшением $l\varepsilon$, для которых требуется найти пороговый классификатор-active. Это означаетИдея состоит в том, что заранее известна линейная раздедимость выборки - то есть существует точка параметр $t\varepsilon$выбирается случайно из конечного множества, такая что точки $x < t$ принадлежат одному классу, а $x > t$ {{---}} другомугде каждому элементу присвоены вероятности. Наивным решением было бы разбиение отрезка на $k$ равных подотрезков, чтобы отправить оракулу по одной точке из каждого подотрезка и получить верный ответ с точностью По ходу алгоритма экспоненциально увеличиваются вероятности наиболее успешных $\dfrac{l}{k}varepsilon$. Гораздо лучшим решением является бинарный поиск, который на каждой итерации сокращает пространство возможных решений вдвоечто несколько напоминает алгоритм [[Бустинг, и необходимая точность $d$ достигается за $\log{\dfrac{l}{d}}$ запросовAdaBoost | Adaboost]] по принципу работы.