52
правки
Изменения
точки и запятые после формул
Дано множество неразмеченных данных:
$X = \{x_1, ..., x_n\}$,
Множество меток:
$Y = \{y_1, ..., y_m\}$,
Оракул:
Энтропия классификации на объекте $x$:
$\Phi_{ENT}(x) = - \sum\limits_y{P(y | x) \log{P(y | x)}}$.
Чем больше энтропия {{---}} тем больше неуверенность в классификации.
Функция неуверенности:
$\Phi_{LC}(x) = 1 - P(y_1 | x)$,
$y_1$ {{---}} наиболее вероятный класс. Интересующие нас объекты {{---}} объекты с минимальной уверенностью, то есть с максимальным $\Phi_{LC}$.
Отбор по несогласию в комитете (англ. ''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]}$.
=== Сокращение размерности пространства решений ===
Пусть текущая модель имеет параметр $\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$) на оставшемся неразмеченном множестве. Существует мнение, что этот метод более устойчив, чем предыдущие, поскольку он не склонен подавать на вход оракулу шумы, и явно увеличивает уверенность классификатора.
