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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сэмплирование по несогласию в комитете (англ. Query By Comittee))
Строка 1: Строка 1:
'''Активное обучение''' (англ. ''Active learning'') - область машинного обучения, где в отличие от обучения с учителем имеется набор неразмеченных данных и оракул, способный размечать данные. Зачастую обращение к оракулу затратно по времени или другим ресурсам. Требуется решить задачу, минимизируя количество обращений к оракулу.
+
'''Активное обучение''' (англ. ''Active learning'') {{---}} область машинного обучения, где в отличие от обучения с учителем имеется набор неразмеченных данных и оракул, способный размечать данные. Зачастую обращение к оракулу затратно по времени или другим ресурсам. Требуется решить задачу, минимизируя количество обращений к оракулу.
  
 
Для вызова оракула обычно требуется привлечение человеческих ресурсов. В роли оракула может выступать эксперт, размечающий текстовые документы, изображения или видеозаписи. Помимо временных затрат могут быть и значительные финансовые, например, исследование химического соединения или реакции.
 
Для вызова оракула обычно требуется привлечение человеческих ресурсов. В роли оракула может выступать эксперт, размечающий текстовые документы, изображения или видеозаписи. Помимо временных затрат могут быть и значительные финансовые, например, исследование химического соединения или реакции.
Строка 16: Строка 16:
 
Оракул:
 
Оракул:
  
$O : X \rightarrow Y$ - функция, которая по объекту возвращает его метку.
+
$O : X \rightarrow Y$ {{---}} функция, которая по объекту возвращает его метку.
  
 
Требуется восстановить функцию $a : X \rightarrow Y$, минимизируя количество обращений к оракулу.
 
Требуется восстановить функцию $a : X \rightarrow Y$, минимизируя количество обращений к оракулу.
Строка 22: Строка 22:
 
На каждой итерации алгоритм фиксирует три множества:
 
На каждой итерации алгоритм фиксирует три множества:
  
1. $X_{unlabeled}$ - множество еще не размеченных объектов.
+
1. $X_{unlabeled}$ {{---}} множество еще не размеченных объектов.
  
2. $X_{labeled}$ - множество размеченных, которые удовлетворяют некоторому порогу уверенности в классификации.  
+
2. $X_{labeled}$ {{---}} множество размеченных, которые удовлетворяют некоторому порогу уверенности в классификации.  
  
3. $X_{query}$ - множество объектов, которые подаются на вход оракулу. Заметим, что не всегда $X_{query} \subset X_{unlabeled}$, поскольку алгоритм может сам синтезировать объекты.
+
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-мерном пространстве, разделенные гиперплоскостью и решается задача бинарной классикации, имеет смысл давать оракулу на вход синтезированные вектора, близкие к границе.
Строка 38: Строка 38:
 
=== Выбор по степени неуверенности ===
 
=== Выбор по степени неуверенности ===
  
Выбор по степени неуверенности (англ. ''Uncertainty Sampling'') - метод отбора объектов из выборки, где самыми информативными объектами считаются те, на которых текущий алгоритм меньше всего уверен в верности классификации. Для этого необходимо задать меру неуверенности в классификации на каждом объекте.
+
Выбор по степени неуверенности (англ. ''Uncertainty Sampling'') {{---}} метод отбора объектов из выборки, где самыми информативными объектами считаются те, на которых текущий алгоритм меньше всего уверен в верности классификации. Для этого необходимо задать меру неуверенности в классификации на каждом объекте.
  
 
Зафиксируем модель на некотором этапе обучения и обозначим за $P(y | x)$ вероятность того, что объект $x$ принадлежит классу $y$. Приведем основные меры неуверенности для текущей классификации:
 
Зафиксируем модель на некотором этапе обучения и обозначим за $P(y | x)$ вероятность того, что объект $x$ принадлежит классу $y$. Приведем основные меры неуверенности для текущей классификации:
Строка 44: Строка 44:
 
* Максимальная энтропия (англ. ''Maximum Entropy'')
 
* Максимальная энтропия (англ. ''Maximum Entropy'')
  
$\Phi_{ENT}(x) = - \sum\limits_y{P(y | x) \log{P(y | x)}}$ - энтропия классификации на объекте $x$. Чем больше энтропия - тем больше неуверенность в классификации.
+
$\Phi_{ENT}(x) = - \sum\limits_y{P(y | x) \log{P(y | x)}}$ {{---}} энтропия классификации на объекте $x$. Чем больше энтропия {{---}} тем больше неуверенность в классификации.
  
 
* Минимальный отступ (англ. ''Smallest Margin'')
 
* Минимальный отступ (англ. ''Smallest Margin'')
  
$\Phi_{M}(x) = P(y_1 | x) - P(y_2 | x)$ - отступ (англ. ''margin'') от $y_1$ - самого вероятного класса до $y_2$ - второго по вероятности класса. Очевидно, что если отступ велик, то велика и уверенность, потому что один класс заметно выигрывает у всех остальных. Поэтому имеет смысл запрашивать оракула на объектах с минимальным отступом.
+
$\Phi_{M}(x) = P(y_1 | x) - P(y_2 | x)$ {{---}} отступ (англ. ''margin'') от $y_1$ {{---}} самого вероятного класса до $y_2$ {{---}} второго по вероятности класса. Очевидно, что если отступ велик, то велика и уверенность, потому что один класс заметно выигрывает у всех остальных. Поэтому имеет смысл запрашивать оракула на объектах с минимальным отступом.
  
 
* Минимальная уверенность (англ. ''Least Confidence'')
 
* Минимальная уверенность (англ. ''Least Confidence'')
  
$\Phi_{LC}(x) = 1 - P(y_1 | x)$,  где $y_1$ - наиболее вероятный класс. Интересующие нас объекты - объекты с минимальной уверенностью.
+
$\Phi_{LC}(x) = 1 - P(y_1 | x)$,  где $y_1$ {{---}} наиболее вероятный класс. Интересующие нас объекты {{---}} объекты с минимальной уверенностью.
  
 
Заметим, что в случае бинарной классификации эти методы эквивалентны.
 
Заметим, что в случае бинарной классификации эти методы эквивалентны.
Строка 58: Строка 58:
 
=== Сэмплирование по несогласию в комитете ===
 
=== Сэмплирование по несогласию в комитете ===
  
Сэмплирование по несогласию в комитете (англ. ''Query By Comittee'') - метод, в котором алгоритм оперирует не одной моделью, а сразу несколькими, которые формируют комитет. Каждая из моделей обучена на размеченном множестве и принимает участие в общем голосовании на неразмеченных объектах. Идея состоит в том, что те объекты, на которых модели более всего расходятся в своих решениях, являются самыми информативными.
+
Сэмплирование по несогласию в комитете (англ. ''Query By Comittee'') {{---}} метод, в котором алгоритм оперирует не одной моделью, а сразу несколькими, которые формируют комитет. Каждая из моделей обучена на размеченном множестве и принимает участие в общем голосовании на неразмеченных объектах. Идея состоит в том, что те объекты, на которых модели более всего расходятся в своих решениях, являются самыми информативными.
  
Множество моделей - $A^T = \{a_1, .., a_T\}$
+
Множество моделей {{---}} $A^T = \{a_1, .., a_T\}$
  
 
Алгоритм выбирает те объекты, на которых достигается максимум энтропии:
 
Алгоритм выбирает те объекты, на которых достигается максимум энтропии:
Строка 81: Строка 81:
 
* [https://www.youtube.com/watch?v=QQaEnOlX9gA&list=PLJOzdkh8T5kp99tGTEFjH_b9zqEQiiBtC&index=17 Школа Анализа Данных. Активное обучение]
 
* [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 К.В. Воронцов. Активное обучение]
 
* [http://www.machinelearning.ru/wiki/images/6/6b/Voron-ML-AL-slides.pdf К.В. Воронцов. Активное обучение]
 +
 +
[[Категория:Машинное обучение]]
 +
[[Категория:Активное обучение]]

Версия 21:27, 2 февраля 2020

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

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


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

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

$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

См. также

Ссылки