Активное обучение — различия между версиями
(→Методы выбора сэмплирования) |
|||
(не показано 16 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
− | '''Активное обучение''' (англ. ''Active learning'') - область машинного обучения, где в отличие от обучения с учителем имеется набор неразмеченных данных и оракул, способный размечать данные. Зачастую обращение к оракулу затратно по времени или другим ресурсам. Требуется решить задачу, минимизируя количество обращений к оракулу. | + | '''Активное обучение''' (англ. ''Active learning'') {{---}} область машинного обучения, где в отличие от обучения с учителем имеется набор неразмеченных данных и оракул, способный размечать данные. Зачастую обращение к оракулу затратно по времени или другим ресурсам. Требуется решить задачу, минимизируя количество обращений к оракулу. |
+ | |||
+ | Для вызова оракула обычно требуется привлечение человеческих ресурсов. В роли оракула может выступать эксперт, размечающий текстовые документы, изображения или видеозаписи. Помимо временных затрат могут быть и значительные финансовые, например, исследование химического соединения или реакции. | ||
+ | |||
+ | В связи с этим одной из центральных задач активного обучения становится '''сэмплирование''' (англ. ''Sampling'') - выбор объектов, которые следует отправить оракулу для получения достоверной информации об их классификации. От грамотности сэмплирования зависит время работы алгоритма, качество классификации и затраты на внешние ресурсы. | ||
Строка 14: | Строка 18: | ||
Оракул: | Оракул: | ||
− | $O : X \rightarrow Y$ - функция, которая по объекту возвращает его метку. | + | $O : X \rightarrow Y$ {{---}} функция, которая по объекту возвращает его метку. |
Требуется восстановить функцию $a : 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''). Имеется некоторая выборка, и алгоритм использует объекты из нее в качестве запросов к оракулу. В данной стратегии каждому объекту присваивается степень информативности - | + | * '''Отбор объектов из выборки''' (англ. ''Pool-based active learning''). Имеется некоторая выборка, и алгоритм использует объекты из нее в качестве запросов к оракулу. В данной стратегии каждому объекту присваивается степень информативности {{---}} сколько выгоды принесет информация об истинной метке объекта, и оракулу отправляются самые информативные объекты. |
* '''Отбор объектов из потока''' (англ. ''Selective sampling''). Алгоритм пользуется не статической выборкой, а потоком данных, и для каждого объекта из потока принимается решение, запрашивать оракула на этом объекте или самому присваивать метку согласно текущему классификатору. | * '''Отбор объектов из потока''' (англ. ''Selective sampling''). Алгоритм пользуется не статической выборкой, а потоком данных, и для каждого объекта из потока принимается решение, запрашивать оракула на этом объекте или самому присваивать метку согласно текущему классификатору. | ||
* '''Синтез объектов''' (англ. ''Query synthesis''). Вместо использования заранее заданных объектов, алгоритм сам конструирует объекты и подает их на вход оракулу. Например, если объекты - это вектора в n-мерном пространстве, разделенные гиперплоскостью и решается задача бинарной классикации, имеет смысл давать оракулу на вход синтезированные вектора, близкие к границе. | * '''Синтез объектов''' (англ. ''Query synthesis''). Вместо использования заранее заданных объектов, алгоритм сам конструирует объекты и подает их на вход оракулу. Например, если объекты - это вектора в n-мерном пространстве, разделенные гиперплоскостью и решается задача бинарной классикации, имеет смысл давать оракулу на вход синтезированные вектора, близкие к границе. | ||
− | == Uncertainty Sampling == | + | == Методы выбора сэмплирования == |
+ | |||
+ | === Выбор по степени неуверенности === | ||
+ | |||
+ | Выбор по степени неуверенности (англ. ''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$ {{---}} наиболее вероятный класс. Интересующие нас объекты {{---}} объекты с минимальной уверенностью. | ||
+ | |||
+ | Заметим, что в случае бинарной классификации эти методы эквивалентны. | ||
+ | |||
+ | ==== Взвешивание по плотности ==== | ||
+ | |||
+ | Одной из проблем описанного выше метода может являться то, что алгоритм часто будет отдавать оракулу шумы {{---}} те объекты, которые не соответствуют основному распределению в выборке. Так как шумы являются нетипичными в контексте выборки объектами, модель может быть неуверена в их классификации, в то время как для решения основной задачи их классификация не очень полезна. Вокруг шумов плотность распределения мала, и вследствие этого применяется эвристика '''взвешивание по плотности''' где предпочтение отдается тем объектам, в которых плотность больше. | ||
+ | |||
+ | Таким образом, наиболее информативными объектами будут считаться: | ||
+ | |||
+ | $x_{informative} = arg \max\limits_x{\Phi(x) p(x)}$, где $\Phi(x)$ - мера неуверенности, а $p(x)$ - эмпирическая плотность в точке $x$ | ||
+ | |||
+ | === Сэмплирование по несогласию в комитете === | ||
+ | |||
+ | Сэмплирование по несогласию в комитете (англ. ''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}}$ запросов. | ||
+ | |||
+ | === Максимизация ожидаемого влияния на модель === | ||
+ | |||
+ | Пусть текущая модель имеет параметр $\theta$, который мы стремимся оптимизировать, чтобы уменьшить функцию потерь $L$. Тогда имеет смысл запрашивать те объекты, которые максимизируют влияние на модель (англ. ''Expected Model Change''). Степень влияния можно оценивать градиентом функционала потерь {{---}} $\nabla_\theta L$. Тогда мера информативности объекта: | ||
+ | |||
+ | $\Phi(x) = \sum\limits_y{P(y | x) \cdot || \nabla_\theta L_{+(x, y)} ||}$ | ||
+ | |||
+ | == См. также == | ||
+ | |||
+ | * [[Обучение с частичным привлечением учителя]] | ||
+ | * [[Обучение с подкреплением]] | ||
+ | * [[Общие понятия]] | ||
+ | |||
+ | == Источники информации == | ||
+ | |||
+ | * [https://www.cs.cmu.edu/~tom/10701_sp11/recitations/Recitation_13.pdf Yi Zhang. Active Learning] | ||
+ | * [https://www.youtube.com/watch?v=QQaEnOlX9gA&list=PLJOzdkh8T5kp99tGTEFjH_b9zqEQiiBtC&index=17 Школа Анализа Данных. Активное обучение] | ||
+ | * [http://www.machinelearning.ru/wiki/images/6/6b/Voron-ML-AL-slides.pdf К.В. Воронцов. Активное обучение] | ||
+ | * [https://en.wikipedia.org/wiki/Active_learning_(machine_learning) Wikipedia. Active Learning] | ||
+ | |||
+ | [[Категория:Машинное обучение]] | ||
+ | [[Категория:Активное обучение]] |
Версия 23:55, 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$ — наиболее вероятный класс. Интересующие нас объекты — объекты с минимальной уверенностью.
Заметим, что в случае бинарной классификации эти методы эквивалентны.
Взвешивание по плотности
Одной из проблем описанного выше метода может являться то, что алгоритм часто будет отдавать оракулу шумы — те объекты, которые не соответствуют основному распределению в выборке. Так как шумы являются нетипичными в контексте выборки объектами, модель может быть неуверена в их классификации, в то время как для решения основной задачи их классификация не очень полезна. Вокруг шумов плотность распределения мала, и вследствие этого применяется эвристика взвешивание по плотности где предпочтение отдается тем объектам, в которых плотность больше.
Таким образом, наиболее информативными объектами будут считаться:
$x_{informative} = arg \max\limits_x{\Phi(x) p(x)}$, где $\Phi(x)$ - мера неуверенности, а $p(x)$ - эмпирическая плотность в точке $x$
Сэмплирование по несогласию в комитете
Сэмплирование по несогласию в комитете (англ. 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}}$ запросов.
Максимизация ожидаемого влияния на модель
Пусть текущая модель имеет параметр $\theta$, который мы стремимся оптимизировать, чтобы уменьшить функцию потерь $L$. Тогда имеет смысл запрашивать те объекты, которые максимизируют влияние на модель (англ. Expected Model Change). Степень влияния можно оценивать градиентом функционала потерь — $\nabla_\theta L$. Тогда мера информативности объекта:
$\Phi(x) = \sum\limits_y{P(y | x) \cdot || \nabla_\theta L_{+(x, y)} ||}$