Application of probabilistic graphical models for data aggregation in large-scale human-machine computing systems

Ponomarev Andrei PhD in Technical Science Senior Researcher, St. Petersburg Institute of Informatics and Automation of the Russian Academy of Sciences. 199178, Russia, g. Saint Petersburg, ul. 14 Liniya, 39 ponomarev@iias.spb.su Other publications by this author

Введение

Под масштабными человеко-машинными вычислениями (крауд-вычислениями) понимается такая организация процесса сбора и обработки информации, при которой часть операций выполняется с помощью людей, взаимодействие с которыми осуществляется посредством сети Интернет. Системы, включающие элементы масштабных человеко-машинных вычислений (МЧМВ), в настоящее время широко используются для решения самых разных задач (см., например, ^[1,2,3,4]).

В частности, одним из достаточно распространенных применений этой технологии является аннотирование изображений, то есть снабжение изображений метками, связанными с содержанием этого изображения. Это требуется как при подготовке эталонных наборов данных для машинного обучения ^[5,6], так и непосредственно в информационно-поисковых системах, поскольку позволяет дополнить алгоритмы обработки изображений алгоритмами текстовой обработки или алгоритмами обработки структурированной и частично структурированной информации.

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

Проведенный ранее автором статьи обзор методов обеспечения качества в системах МЧМВ ^[7] позволил сделать вывод о том, что большинство описанных в литературе подходов к обеспечению качества учитывают лишь часть потенциально полезной информации, таким образом, с одной стороны, комплексный подход к проблеме обеспечения качества должен базироваться на сочетании различных методов, с другой – необходимо на единой формальной основе обеспечить сопоставление и использование разных видов доступной информации.

Следует также отметить, что данные, получаемые (и обрабатываемые) в рамках МЧМВ, очень часто являются неточными и для их представления и обработки используются вероятностные модели (например, участнику ставится в соответствие средняя точность, интерпретируемая как вероятность ошибки при выполнении задания или даже матрица вероятностей ошибок; на основе данных, полученных от участников, может быть построено распределение вероятности ответа на предлагавшееся им задание). Таким образом, необходимо обеспечить согласование и комплексирование данных с учетом неопределенности (представляемой, как правило, в терминах теории вероятностей).

Комплексирование данных (data fusion) с использованием вероятностных моделей широко применяется при обработке показаний датчиков и «выведении» из них истинного состояния наблюдаемого объекта ^[8,9,10]. Нетрудно заметить определенное сходство между этими задачами (обработка сенсоров и обработка данных в МЧМВ) – в обоих случаях с помощью привлечения разнообразных данных, описывающих один и тот же объект/процесс, осуществляется попытка повышения точности его описания.

В статье предлагается модель комплексирования данных для повышения качества результатов, получаемых с помощью МЧМВ. Предлагаемая модель рассматривается на примере решения задачи разметки и поиска изображений, полученных в рамках массовых легкоатлетических мероприятий (пробегов).

Модель системы разметки изображений

Участие в массовых легкоатлетических пробегах является одним из популярных видов досуга как в России, так и за рубежом ^{[11,12,13,14]}. Подобные мероприятия, как правило, фиксируются различными фотографами (как любителями, так и профессионалами), публикующими фотографии в открытом доступе (в альбомах социальных сетей или с помощью специальных интернет-сервисов для публикации фотографий). Очень часто участники пробега оказываются заинтересованы в получении собственных фотографий в качестве сувенира, что привело как к появлению ряда специализированных сервисов продажи спортивных фотографий (Марафон Фото [https://marathon-photo.ru]) так и к тому, что предоставление участнику пробега сделанных организаторами фотографий воспринимается как одна из важных составляющих комплексной информационной поддержки легкоатлетического пробега (Russia Running [https://russiarunning.com]).

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

Существует несколько работ, в которых предлагаются автоматические решения, использующие технологии компьютерного зрения и OCR для решения этой задачи ^[15,16], однако в силу того, что нагрудные номера являются гибкими (следовательно, могут быть искажены) и на фотографии могут быть частично закрыты (руками участника или другими участниками пробега) полностью автоматические решения зачастую не обеспечивают желаемого качества распознавания.

Ранее автором был предложен сервис совместной разметки изображений легкоатлетических пробегов (далее просто Сервис), применяющий элементы МЧМВ и позволяющий координировать усилия сообщества (состоящего преимущественно из участников пробега) при разметке коллекции изображений ^[17]. Предварительные исследования позволили выявить перспективность данного подхода – на ряде крупных легкоатлетических пробегов к разметке удавалось привлечь достаточное количество участников, чтобы осуществить разметку более 7000 изображений, обеспечив возможность быстрого поиска по ним, причем качество разметки (и, соответственно, поиска фотографий) оказывалось достаточно высоким. В данной статье предлагается применить методы комплексирования данных для дальнейшего улучшения качества поиска и снижения трудоемкости разметки.

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

Модель комплексирования данных для системы разметки изображений

Дополнительным видом информации, учитываемым предлагаемой моделью комплексирования, является местоположение участника пробега в момент фотографирования. На практике оценка местоположения возможна, поскольку: а) многие участники пробега используют спортивные часы или смартфон с GPS-трекером во время мероприятия, б) протокол мероприятия содержит финишное время каждого участника (и, возможно, время прохождения участником нескольких контрольных точек). Конечно, справедливо ожидать, что точность оценки местоположения участника пробега в случаях (а) и (б) будет существенно варьироваться. Информация о времени и месте съемки, как правило, записывается в атрибуты файла изображения большинством современных камер. Данная информация является очень важной для поиска изображений и для оценки качества участников разметки. Так, информация о том, что участник пробега наверняка находился поблизости от точки съемки в момент фотографирования может быть основанием для включения фотографии в поисковую выдачу само по себе. С другой стороны, информация о том, что участник пробега никак не мог находиться поблизости от точки съемки в момент создания фотографии может использоваться для выявления ошибок разметки.

Как указывалось ранее, точное положение участника на дистанции известно только в определенные моменты времени (в наихудшем случае таких моментов два – старт и финиш, в наилучшем – если участник использует GPS-трекер – его точная позиция на дистанции известна с интервалом в минуту или даже в несколько секунд). Пусть – моменты времени, в которые точно известно положение участника, причем , а соответствует моменту финиша. Для обозначения положения участника в какой-либо момент времени будем использовать функциональную запись . Введем также обозначение . Допустим, что участник движется только в одном направлении (от старта к финишу), то есть, . Для определения положения участника в моменты времени, когда положение неизвестно (), будем использовать вероятностную модель, основанную на следующих допущениях:

1) В каждый из моментов времени между и скорость участника является нормально распределенной случайной величиной с математическим ожиданием и стандартным отклонением (данное стандартное отклонение получено из работы ^[18]).

2) Скорость движения участника в некоторый момент времени не зависит от скорости движения в другие моменты времени.

Таким образом, с учетом допущения (2), искомая вероятность нахождения участника в момент времени t, упрощается до , где , то есть на искомое распределение оказывают влияние только два известных положения участника. Далее, можно показать, что . Вероятности и представляют собой вероятности перемещения на расстояние и за время и соответственно. При условии, что характер движения удовлетворяет принятым предположениям, данные вероятности распределены в соответствии с нормальным законом , то есть, их плотность распределения задается следующим выражением:

Таким образом, плотность вероятности позиции участника на отрезке при задается следующим образом:

Вне отрезка плотность вероятности равна 0.

Полученная плотность вероятности используется для определения вероятности нахождения участника в области видимости камеры в момент совершения снимка. Пусть снимок совершается в момент времени , камера находится в позиции , а расстояние от камеры до объекта, в пределах которого может быть получено качественное изображение – . Для простоты записи положим также, что . Тогда вероятность того, что участник пробега будет в области видимости камеры в момент времени :

Таким образом, общий алгоритм оценки вероятности нахождения участника пробега в точке дистанции в заданный момент времени следующий:

1) Определить сегмент дистанции, на котором участник находится в момент совершения снимка (), то есть, найти такое i, что .

2) Найти функцию плотности вероятности положения участника пробега на данном сегменте (*).

3) Вычислить интеграл (**).

При обработке результатов, получаемых с помощью МЧМВ, широко применяются вероятностные модели участников таких систем, позволяющие численно описать их склонность к совершению разного рода ошибок (см., например, ^[7]). Например, при совместной разметке изображений возможно совершение ошибок двух видов: 1) неуказание при аннотировании изображения номера участника пробега, в действительности присутствующего на изображении, и 2) указание номера, в действительности не присутствующего на изображении. Как показал опыт эксплуатации сервиса совместной разметки (см. ^{[17, 19]}), ошибка вида (1) встречается существенно чаще. Это связано с тем, что во многих случаях участники процесса разметки стараются экономить усилия, указывая в аннотации лишь наиболее очевидные номера. Ошибки вида (2) встречаются реже и связаны, как правило, с неправильным прочтением (часто искаженного) номера или неправильным его вводом.

Таким образом, предлагается описывать участника u процесса разметки двумя параметрами: (своего рода «внимательность» или «усердность» – вероятность того, что присутствующий на изображении номер будет найден и включен в аннотацию) и (вероятность того, что номер включен в аннотацию ошибочно).

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

Рисунок 1. Схема байесовской сети для комплексирования информации

Подобная сеть (в данном случае, лес) формируется для поиска изображений каждого участника пробега r. Бинарные переменные , являются ненаблюдаемыми переменными, каждая из которых соответствует факту присутствия участника пробега r на изображении p_i. Априорная вероятность определяется вероятностью присутствия участника в области видимости камеры, вычисляемой по формуле (**). Переменные являются наблюдаемыми и соответствуют результатам разметки – по мнению участника разметки u участник пробега c номером r присутствует на изображении p_i. Таблица условных распределений для переменных формируется следующим образом. В случае, если r действительно присутствует на снимке, вероятность того, что он будет указан участником разметки u, по определению, равняется . Если же r на изображении нет, но он был указан участником разметки u, значит, при прочтении или вводе одного из номеров u совершил ошибку, заменив правильный номер на r. Вероятность совершения ошибки по определению , вероятность именно такой ошибки: , где – множество номеров, указанных u для изображения p_i, а R – множество допустимых номеров.

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

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

Экспериментальная оценка

Влияние предлагаемой схемы комплексирования информации на качество поиска изображений было исследовано в ходе серии экспериментов с имитационными моделями. Был сгенерирован набор данных, содержащий траектории передвижения 100 участников пробега по дистанции 10 км. Траектории были построены с учетом того, что типовое время преодоления такой дистанции в ходе любительского легкоатлетического пробега – 30-70 минут, а колебание скорости в ходе движения описывается нормальным законом с среднеквадратичным отклонением около 18% от средней скорости ^[18]. На основе известного положения участников, был сгенерирован эталонный набор из 1250 фотографий, каждый снимок описывался временем и позицией съемки, а также списком участников «попавших» на снимок. Для определения факта попадания делалась случайная выборка из множества участников, находящихся поблизости от точки съемки.

Оценка качества поиска на основе только априорной вероятности

В первую очередь, было оценено качество поиска на основе только априорной информации (то есть, предлагаемой вероятностной модели перемещения участника по дистанции). Важным параметром здесь является количество точек, в которых известно точное положение участника пробега. В частности, эффективность поиска оценивалась в различных сценариях: когда точное положение участника пробега известно каждые 500 м, 1 км, 5 км и 10 км. Здесь первый вариант приблизительно соответствует поиску по данным GPS-трека, а последний – по данным итогового протокола (в который включается только финишное время).

Для оценки качества использовались традиционные меры, используемые в области информационного поиска: точность (precision), полнота (recall) и сочетающая их F-мера. Данные метрики рассчитывались применительно к двум множествам: множеству пар «участник-снимок», возвращаемому процедурой поиска на основе априорной информацией (пара включалась в множество в том случае, если вероятность нахождения участника в области совершения снимка превышала 30%) и множеству пар «участник-снимок» эталонного набора данных (фактическое присутствие участника на снимке).

Рисунок 2. Значения показателей качества при поиске на основе априорной вероятности (оценки положения участника)

По приведенному на рис. 2 графику видно, что качество поиска на детализированном треке (500 м) оказывается достаточно хорошим. Объяснимо высокая полнота (0,954) свидетельствует о том, что почти все снимки, на которых участники присутствуют, действительно были включены в результирующую выборку. Низкая (даже при 500 м) точность обусловлена, в первую очередь, тем, что на снимки попадают не все участники, находящиеся поблизости с точкой съемки. При увеличении шага неопределенность, касающаяся местоположения участника, растет соответственно качественные параметры процедуры поиска предсказуемо снижаются.

Оценка качества поиска на основе разметки

Оценка качества поиска на основе данных разметки проводилась с применением двух экземпляров модели участника разметки, соответствующих низкокачественной и высококачественной разметке соответственно. Значения параметров модели и для низкокачественной разметки были приняты 0,7 и 0,1, а для высококачественной – 0,9 и 0,05 соответственно. Данные значения были выбраны на основе анализа истории использования разработанного Сервиса. Информация о снимках была обработана с помощью данных моделей разметки и получено два множества пар «участник-снимок». Результаты оценки качества приведены в табл. 1. Сопоставление данных рис. 2 и табл. 1 позволяет сделать вывод, что поиск на основе только априорной вероятности при детальной информации о перемещении участника пробега позволяет получить результат лучше по обобщенному показателю (F-мера), чем поиск на основе низкокачественной разметки. В остальных случаях поиск по размеченным данным значительно превосходит по F-мере поиск, основанный только на априорной вероятности (и это закономерно, поскольку при разметке проводится анализ самих изображений).

Таблица 1 – Типовые показатели качества разметки

Оценка качества поиска на основе предлагаемой модели комплексирования

Исследование качества поиска на основе предлагаемой модели комплексирования также было проведено с разными значениями интервала между известными положениями участника пробега на дистанции и с разным качеством разметки. Графики оцениваемых показателей качества приведены на рис. 3.

Рисунок 3 – Значения показателей качества поиска при применении комплексирования данных: а) используется ручная разметка низкого качества, б) используется ручная разметка высокого качества

Видно (рис. 3а), что при разных интервалах между известными положениями участника пробега обобщенная мера качества поиска имеет приблизительно одинаковое значение, однако роль разных видов информации плавно меняется. Так, при небольших интервалах (500 м, 1 км) поиск характеризуется высокой полнотой и относительно низкой точностью (значительную роль здесь играет априорная оценка вероятности нахождения участника пробега в заданном интервале). При больших интервалах точность становится выше – характерный признак результатов разметки человеком. В любом случае, за счет схемы комплексирования интегральное качество результатов (F-мера) увеличилось приблизительно на 0,05 по сравнению с ручной разметкой низкого качества, а полнота увеличилась на 0,1.

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

Заключение

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

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

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

В дальнейшем планируется расширить модель комплексирования за счет применения более детализированных моделей ошибок участника разметки.