Оптимистический градиент знаний

В статистике Оптимистический градиент знаний — это политика аппроксимации, предложенная Си Ченом , Цихан Линем и Денгён Чжоу в 2013 году. Эта политика создана для решения вычислительно неразрешимой задачи оптимального распределения вычислительного бюджета большого размера при бинарной/многоклассовой групповой маркировке, где каждая метка из толпа имеет определенную стоимость.

Мотивация

Задача оптимального распределения вычислительного бюджета формулируется как байесовский марковский процесс принятия решений. (MDP) и решается с использованием алгоритма динамического программирования (DP), где политика оптимистического градиента знаний используется для решения вычислительно неразрешимых задач динамического программирования. (ДП) алгоритм.

Рассмотрим проблему распределения бюджета в краудсорсинге . Особая проблема краудсорсинга, которую мы рассматриваем, — это маркировка толпы. Крауд-маркировка — это большое количество задач по маркировке , которые трудно решить машине, но которые легко решаются людьми, а затем мы просто передаем их на аутсорсинг неопознанной группе случайных людей в распределенной среде.

Методология

Мы хотим завершить эту задачу по маркировке и надеемся, что полагаемся на силу толпы. Например, предположим, что мы хотим идентифицировать изображение по тому, являются ли люди на изображении взрослыми или нет. Это проблема маркировки Бернулли , и все мы можем сделать это за одну или две секунды, это простая задача для человека. Однако если у нас есть десятки тысяч таких изображений, то это уже непростая задача. Вот почему нам нужно полагаться на систему краудсорсинга , чтобы сделать это быстро. краудсорсинга Система состоит из двух этапов. Шаг первый: мы просто динамически приобретаем предметы из толпы. С другой стороны, это динамическая процедура. Мы не просто рассылаем эту картинку всем и фокусируемся на каждом ответе, вместо этого мы делаем это в количестве. Мы собираемся решить, какую фотографию мы отправим в следующий раз и какого работника мы наймем в толпе в следующий раз. Согласно его или ее историческим результатам маркировки. Каждое изображение можно отправить нескольким работникам, и каждый работник также может работать над разными изображениями. Затем, после того как мы соберем достаточное количество меток для разных изображений, мы переходим ко второму шагу, на котором мы хотим определить истинную метку каждого изображения на основе собранных меток. Итак, есть несколько способов сделать вывод. Например, самое простое, что мы можем сделать, — это просто проголосовать большинством голосов. Проблема в том, что бесплатного обеда нет, нам приходится платить работнику за каждую предоставленную им этикетку, и у нас лишь ограниченный бюджет проекта. Поэтому вопрос в том, как разумно потратить ограниченный бюджет.

Проблемы

Прежде чем показать математическую модель, в статье упоминается, с какими проблемами мы сталкиваемся.

Задача 1

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

Задача 2

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

Математическая модель

Для математической модели у нас есть K элементов, $i=\{1,2,\ldots ,k\}$, а общий бюджет равен T , и мы предполагаем, что стоимость каждой метки равна 1, поэтому в конечном итоге у нас будет T меток. Мы предполагаем, что каждый товар имеет настоящую этикетку $Z_{i}$какие положительные или отрицательные, это биномиальные случаи, и мы можем распространить их на несколько классов, маркируя случаи, это уникальная идея. И позитивный набор $H^{*}$ определяется как набор элементов, истинная метка которых положительна. И $\theta _{i}$ также определил мягкую метку, $\theta _{i}$ для каждого элемента, номер которого находится между 0 и 1, и мы определяем $\theta _{i}$ как основная вероятность того, что член, случайно выбранный из группы идеальных работников, будет отмечен как положительный.

В этом первом случае мы предполагаем, что каждый работник идеален, это означает, что все они надежны, но совершенство не означает, что этот работник дает одинаковый или правильный ответ. Это просто означает, что они будут стараться изо всех сил, чтобы найти лучший ответ в своем уме, и предположим, что все являются идеальными работниками, просто случайно выбрали одного из них, и с $\theta _{i}$ Вероятно, мы найдем парня, который поверит, что это положительный результат. Вот как мы объясняем $\theta _{i}$. Итак, мы предполагаем ярлык $Y_{i}$ взято из Бернулли( $\theta _{i}$), и $\theta _{i}$ должно соответствовать истинной этикетке, что означает $\theta _{i}$ больше или равно 0,5 тогда и только тогда, когда этот элемент является положительным с истинно положительной меткой. Итак, наша цель — изучить H*, набор положительных элементов. Другими словами, мы хотим создать выведенный положительный набор H на основе собранных меток, чтобы максимизировать:

$\sum _{i=1}^{k}({\textbf {1}}_{(i\in H)}{\textbf {1}}_{(i\in H^{\star })}+{\textbf {1}}_{(i\notin H)}{\textbf {1}}_{(i\notin H^{\star })})$

Это также можно записать как:

$|H\cap H^{\star }|+|H^{c}\cap H^{\star c}|$

шаг 1: байесовский процесс принятия решений

Прежде чем показать байесовскую структуру, в статье используется пример, в котором упоминается, почему мы выбираем байесовский подход вместо частотного подхода, чтобы мы могли предложить некоторый апостериорный результат априорного распределения на мягкой метке. $\theta _{i}$. Мы предполагаем, что каждый $\theta _{i}$ взято из известной бета-версии:

$\theta _{i}\sim \mathrm {Beta} (a_{i}^{o},b_{i}^{o})$

И матрица:

$s^{o}=\left\langle (a_{i}^{o},b_{i}^{o})\right\rangle _{i=1}^{k}\in {\textbf {R}}^{k\times 2}$

Итак, мы знаем, что бета-сопряжение Бернулли, поэтому, как только мы получим новую метку для элемента i, мы собираемся обновить апостериорное распределение, бета-распределение, следующим образом:

$\theta _{i}\sim \mathrm {Beta} (a_{i}^{t},b_{i}^{t})$

$y_{i}\mid \theta _{i}\sim \mathrm {Bernoulli} (\theta _{i})$

$\theta _{i}\mid y_{i}=1\sim \mathrm {Beta} (a_{i}^{t}+1,b_{i}^{t})$

$\theta _{i}\mid y_{i}=-1\sim \mathrm {Beta} (a_{i}^{t}+1,b_{i}^{t})$

В зависимости от этикетки бывает положительной или отрицательной.

Вот вся процедура на высоком уровне, у нас стадия Т, $0\leq t\leq T-1$. На данном этапе мы смотрим на матрицу S, которая суммирует информацию о апостериорном распределении для всех $\theta _{i}$

$s^{t}=\left\langle (a_{i}^{t},b_{i}^{t})\right\rangle _{i=1}^{k}\in {\textbf {R}}^{k\times 2}$

Мы собираемся принять решение, выбираем следующий пункт для маркировки $i_{t}$, $i_{t}\in \{1,2,\ldots ,k\}$.

И в зависимости от того, какая метка положительная или отрицательная, добавляем матрицу для получения метки:

$\theta _{i}\sim \mathrm {Beta} (a_{i}^{t},b_{i}^{t})$

$y_{i}\mid \theta _{i}\sim \mathrm {Bernoulli} (\theta _{i})$

$\theta _{i}\mid y_{i}=1\sim \mathrm {Beta} (a_{i}^{t}+1,b_{i}^{t})$

$\theta _{i}\mid y_{i}=-1\sim \mathrm {Beta} (a_{i}^{t}+1,b_{i}^{t})$

Прежде всего, это вся основа.

Шаг 2: Вывод о положительном наборе

Когда метки t собраны, мы можем сделать вывод о положительном наборе H _t на основе апостериорного распределения, заданного S _t

${\begin{aligned}H_{t}&=\operatorname {argmax} \limits _{H\subset \{1,2,\ldots ,k\}}E\left(\sum _{i=1}^{k}({\textbf {1}}(i\in H){\textbf {1}}(i\in H^{\star })+{\textbf {1}}(i\notin H){\textbf {1}}{(i\notin H^{\star })})\mid S^{\star }\right)\\&=\operatorname {argmax} \limits _{H\subset \{1,2,\ldots ,k\}}\sum _{i=1}^{k}({\textbf {1}}(i\in H)\Pr(i\in H^{\star }\mid S^{t})+{\textbf {1}}(i\notin H)\Pr(i\notin H^{\star }\mid S^{t}))\\&=\{i:\Pr(i\in H^{\star }\mid S^{t})\geq 0.5\}\end{aligned}}$

Итак, здесь возникает проблема выбора Бернулли: мы просто смотрим на вероятность того, что условное условие будет положительным или отрицательным. $S_{t}$ видеть больше 0,5 или нет, если оно больше 0,5, то мы доказываем этот элемент в текущем положительном наборе вывода $H_{t}$ так что это форма стоимости для текущего оптимального решения $H_{t}$ на основе информации в $S_{t}$.

После того, как вы узнаете, какое решение является оптимальным, в документе показано, какое оптимальное значение. Затыкать $t$ в оптимальной функции,

$h(x)=\max(x,1-x)$

Эта функция представляет собой всего лишь одну функцию, которая выбирает большую из условной вероятности быть положительной или отрицательной. Как только мы получим еще одну метку для элемента i, мы возьмем разницу между этим значением до и после того, как мы получим новую метку, мы увидим, что эта условная вероятность на самом деле может упроститься следующим образом:

${\begin{aligned}R(s^{t},i_{t},y_{i_{t}})&=\sum _{i=1}^{k}h(\Pr {(i\in H^{\star }\mid s^{t+1})})-\sum _{i=1}^{k}h(\Pr(i\in H^{\star }\mid s^{t}))\\&=\sum _{i=1}^{k}h(\Pr {(a_{i}^{t+1,b_{i}^{t+1}})})-\sum _{i=1}^{k}h(\Pr(a_{i}^{t},b_{i}^{t})).\end{aligned}}$

Положительный положительный элемент зависит только от бета-апостериорной функции, поэтому, если только функция параметра функции бета-распределения равна a и b , как

$h(\Pr(a_{i_{t}}^{t+1},b_{i_{t}}^{t+1}))-h(\Pr(a_{i_{t}}^{t},b_{i_{t}}^{t}))$

Еще одна метка для этого конкретного элемента: мы дважды меняем апостериорную функцию, поэтому все эти элементы можно отменить, кроме 1, так что это изменение для всей точности, и мы определили его как поэтапное вознаграждение: улучшение точности вывода еще на один образец. Конечно, у этой метки есть два положительных значения: мы получаем положительную метку или отрицательную метку, берем среднее значение для этих двух и получаем ожидаемое вознаграждение. Мы просто выбираем элемент для маркировки так, чтобы ожидаемое вознаграждение было максимальным с помощью градиента знаний :

${\begin{aligned}i_{t}&=\operatorname {argmax} \limits _{i\in \{1,2,\ldots ,k\}}E(R(s^{t},i,y_{i})\mid s^{t})\\&=\operatorname {argmax} \limits _{i\in \{1,2,\ldots ,k\}}\left({\frac {a_{i}^{t}}{a_{i}^{t}+b_{i}^{t}}}R(s^{t},i,1)+{\frac {b_{i}^{t}}{a_{i}^{t}+b_{i}^{t}}}R(s^{t},i,-1)\right)\end{aligned}}$

Это несколько предметов, дайте нам знать, как нам разорвать связи. Если мы разорвем связь детерминированно, это означает, что мы выберем наименьший индекс. У нас будут проблемы, потому что это непоследовательно, что означает положительную стадию. $H_{t}$ не сходится к истинно положительной стадии $H^{*}$.

Таким образом, мы также можем попытаться разорвать связи случайным образом, это работает, однако мы увидим, что производительность почти равна равномерной выборке, что является лучшей наградой. Политика автора более жадная: вместо того, чтобы выбирать среднее значение на этапе после получения награды, мы можем фактически вычислить большее, максимальное из двух этапов возможного вознаграждения, поэтому Оптимистический градиент знаний :

$i_{t}=\operatorname {argmax} \limits _{i\in \{1,\ldots ,k\}}(R^{+}(S^{t},i))=\max(R(S^{t},i,1),R(S^{t},i,-1))$

И мы знаем, что при оптимистическом градиенте знаний окончательная точность вывода приближается к 100%. Вышеизложенное основано на том, что каждый работник идеален, однако на практике работники не всегда несут ответственность. Итак, если среди несовершенных работников мы предполагаем K предметов, $1\leq i\leq k$.

$\theta _{i}\in (0,1)\sim \mathrm {Bet} a(a_{i}^{o},b_{i}^{o})$

Вероятность предмета $i$ идеальный работник называет его положительным.М рабочие, $1\leq j\leq M$ , $\rho _{j}\in (0,1)\sim \mathrm {Beta} (c_{j}^{o},d_{j}^{o})$Вероятность рабочего $j$ присваивая ему тот же ярлык, что и идеальному работнику. Распространение этикетки $Z_{ij}$ от работника $j$ предмет $i$:

$\Pr(Z_{ij}=1\mid \theta _{i},\rho _{j})=\Pr(Z_{ij}=1\mid Y_{i}=1)\Pr(Y_{i}=1)+\Pr(Z_{ij}=1\mid Y_{i}=-1)\Pr(Y_{i}=-1)=\rho _{j}\theta _{i}t(1-\rho _{j})(1-\theta _{i})$

А пространство действия такое

$\Pr(Z_{ij}=1\mid \theta _{i},\rho _{j})=Pr(Z_{ij}=1\mid Y_{i}=1)\Pr(Y_{i}=1)+\Pr(Z_{ij}=1\mid Y_{i}=-1)\Pr(Y_{i}=-1)=\rho _{j}\theta _{i}t(1-\rho _{j})(1-\theta _{i})=\rho _{j}\theta _{i}t(1-\rho _{j})(1-\theta _{i}),$

где $\qquad \qquad (i,j)\in \{1,2,\ldots ,k\}\times \{1,2,\ldots ,M\}$, матрица меток: $Z_{ij}\in \{-1,1\}$

Это сложно вычислить, поэтому мы можем использовать вариационные байесовские методы. из $\Pr(i\in H^{\star }\mid S^{t})$