Вероятностное моделирование является одним из мощнейших инструментов для специалиста по анализу данных. К сожалению, для его использования необходимо не только уверенно владеть аппаратом теории вероятностей и математической статистики, но и знать детали работы алгоритмов приближенного байесовского вывода, что делает порог вхождения очень высоким. Из этой лекции вы узнаете о сравнительно молодой парадигме в машинном обучении — вероятностном программировании. Его задача — сделать всю мощь вероятностного моделирования доступной любому человеку, имеющему опыт программирования и минимальный опыт анализа данных.
Лекция была прочитана Борисом hr0nix Янгелем на факультете компьютерных наук, открытом в Высшей школе экономики при поддержке Яндекса. Сам Борис окончил ВМиК МГУ и Школу анализа данных Яндекса. Работал в Microsoft Research Cambridge в группе Кристофера Бишопа над фреймворком Infer.NET. Сейчас Борис — ведущий разработчик поиска Яндекса.
Под катом — расшифровка рассказа.
Моя задача сегодня — рассказать вам, что такое вероятностное программирование, и как эта сильно недооцененная парадигма в машинном обучении позволяет поставить всю мощь вероятностного моделирования на службу каждому, кто умеет программировать и обладает базовыми знаниями в теории вероятности, математической статистике и основах моделирования.
Чем вообще мы занимаемся в машинном обучении по сути? На самом деле, мы хотим как-то рассуждать о процессах в реальном мире и о том, как эти процессы устроены. Есть некие объекты, которые в этих процессах участвуют. Например, пользователь, который просматривает поисковую выдачу и решает, интересен ему поисковый результат или нет, кликнуть на него, посмотреть следующий результат или вообще уйти со страницы поиска. Это пример объектов. Объекты обладают некоторыми свойствами. Например, у пользователя это могут быть его какие-то сиюминутные информационные потребности, его интересы в целом. Соответственно, есть среда, в которой эти объекты существуют и которая тоже обладает какими-то свойствами. И есть, собственно, сам сложный процесс: процесс подкидывания монетки или процесс просмотра пользователем поисковой выдачи, о котором мы хотим рассуждать. И, как правило, мы имеем какие-то наблюдаемые проявления этого процесса, хотим его обратить и понять, какими были свойства объектов и среды, которые привели к тому, что мы наблюдали. Например, посмотрев несколько раз на то, упала ли монетка орлом или решкой, мы хотим узнать честная монетка или нет. Или, посмотрев несколько раз на то, куда кликал пользователь, мы хотим понять, ушел ли он с поиска счастливым или несчастным, нашел он то, что нужно, или нет, и были ли те документы, которые мы ему показали релевантными или нет.
Тут есть небольшая проблема. Тот сложный процесс, который мы хотим изучать, как правило, довольно проблематично описать наперед так, как он происходит. В случае с нашим пользователем это какие-то сложные биохимические процессы, которые протекают у него в мозгу, и которые в итоге заставляют его принять то или иное решение. Понятно, что обратить его — невероятно сложная вычислительная задача (даже если его можно описать), и таким никто заниматься не будет. Поэтому мы прибегаем к приему, который называется вероятностное моделирование и который заключается в следующем.
Сперва мы строим модели объектов, акцентируем наше внимание только на тех свойствах, которые, на наш взгляд, важны в этом процессе. А те, которые слабо на него влияют, мы игнорируем. Например, мы можем сказать, что монетка описывается одним числом своей честности, или можем сказать, что пользователь описывается вектором чисел, где каждая компонента вектора показывает его заинтересованность в той или иной теме. Например, первая компонента говорит о том, насколько ему интересно найти видео, вторая – насколько ему интересны фото со смешными котами, и так далее.
Далее у нас есть сложный процесс, который мы заменяем некой его округленной версией, которая, с одной стороны, имеет что-то общее с тем, что происходит в действительности, но, с другой стороны, достаточно проста, чтобы с ней можно было работать. В нашем гипотетическом примере с пользователем мы могли бы сказать, что он просматривает выдачу сверху вниз, и, если очередной результат удовлетворяет его информационной потребности, соотносится с его текущими интересами, то значит, он кликает и останавливается, а если нет, то идет дальше. Тут сразу возникает небольшая проблема: если мы посмотрим на реальные клики пользователей, то окажется, что модели, которые я только что предложил, не удовлетворяют в том смысле, что модель все эти паттерны кликов, которые мы наблюдаем в действительности, произвести не может. Например, пользователи иногда кликают на то, что им совсем неинтересно. Почему? Захотелось ему так, или, может он увидел какой-то результат, который его удивил, и захотелось кликнуть и посмотреть, что там будет. Соответственно, наша модель такие данные произвести не может, и в этом проблема.
Что делать? Тут применяется трюк, из-за которого эти модели и называются вероятностными: мы добавляем в модель немного шума, который призван промоделировать те сложные явления, которые напрямую мы промоделировать не можем. Мы считаем, что они такие сложные, что от шума сильно неотличимы, но зато добавление этого шума позволит нашей модели исторгнуть из себя все возможные наблюдения и тогда уже ее можно будет обращать.
В примере с пользователем можем сказать, что когда он видит очередной результат, он подкидывает монетку и в зависимости от того, как она выпала, решает, посмотреть ему этот результат, если он ему понравился, или пойти дальше, или устать и перестать смотреть выдачу. Таким образом, все паттерны кликов становятся возможны в рамках этой модели. Хотя какие-то более вероятны. И построенная модель все еще имеет смысл и соотносится с реальным физическим процессом, который мы хотим промоделировать.
Если мы такую модель построили, формально можно сказать, что мы построили совместное вероятностное распределение на свойствах объектов и наблюдаемых данных. Затем мы можем этот процесс обратить с помощью важной теоремы, которая называется теоремой Байеса и которая как раз говорит нам, как от наших априорных знаний об объектах, которые мы хотим изучать, пронаблюдав какие-то данные, уточнить эти знания и перейти к апостериорному вероятностному распределению. Вот в принципе вся суть вероятностного моделирования.
С вероятностным моделированием, к сожалению, есть ряд проблем. Саму модель разработать для какой-нибудь предметной области сравнительно легко. Не в том смысле, что разработать модель лучше всего существующего легко. Это, как правило, довольно сложно, потому что в отдельных предметных областях люди уже годами и десятилетиями только и делают, что придумывают модели. Но если, например, вы столкнулись с каким-то новым процессом, новой предметной областью, в которой вы более-менее разбираетесь и которую хотите промоделировать, и обладаете какими-то базовыми понятиями о том, как вообще вероятностные модели строятся, то придумать разумную модель, наверно, займет не очень много времени. Может быть, часы или дни. Затем вам нужно сделать, собственно, вывод в модели, воспользоваться теоремой Байеса, чтобы найти апостериорное распределение на интересующей вас переменной при условиях наблюдений. Ранее было сказано, что теорема Байеса дает вычислительный рецепт, который вам позволит это сделать для любой модели. С одной стороны, это правда, а с другой стороны, этот вычислительный рецепт может оказаться очень сложным. Грубо говоря, посчитать все члены в теореме Байеса для мало-мальски сложной модели просто не представляется вычислительно возможным. Поэтому уже несколько десятилетий разрабатываются приближенные методы Байесовского вывода, которые позволяют найти некое приближение для апостериорного распределения, которое в определенных условиях будет хорошим приближением. В общем, если вы хотите делать вероятностный вывод сложных вероятностных моделей, то вам неизбежно к таким методам приближенного вывода придется прибегать.
Здесь перечислены несколько таких методов, это EP, VMP, MCMC. Все эти методы довольно сложные в реализации, концептуальные и не очень простые. В результате чтобы написать вывод в какой-то вашей вероятностной модели, вам нужно потратить очень много времени, разобраться в этом. При этом для по-настоящему сложных моделей потребуются знания уровня PhD в машинном обучении, причем не просто в машинном обучении, а лучше специализированно в Байесовском выводе. Тогда у вас есть шансы правильно и без ошибок написать код вывода в этой модели, который действительно будет делать то, что вы думаете.
Соответственно, это все сильно осложняет экспериментирование. Например, потребовать одну модель займет несколько недель, и неизвестно, получится или нет. Что уж говорить о том, чтобы попробовать несколько альтернативных моделей – мало у кого хватит терпения и сил на такое. Наблюдается такая тенденция, что мало кто готов в своих задачах пробовать сложные модели, потому что, как правило, чем сложнее модель, тем сложнее код вывода, и мало кто может его написать. Поэтому все ограничиваются простыми моделями. Однако очень часто, более сложные модели имеют большую предсказательную мощь, и потенциально от их использования можно получить очень много профита.
Ученые думали, как бороться с этой проблемой, и в качестве одного из решений была предложена такая парадигма, как вероятностное программирование. Эта парадигма основана на двух идеях. Первая – вы не должны писать код вероятностного вывода сами. Это сложно, и лучше все это оставить экспертам. Все, что вы должны делать, это задавать вероятностные модели, говорить, что вы пронаблюдали, апостериорные распределения на какие переменные в вашей модели вас интересуют. Далее черная коробка, движок вероятностного вывода, должен сделать вывод за вас. Вторая идея — мы хотим, чтобы всей мощью вероятностного моделирования могли пользоваться как можно больше людей. Нужен такой способ формально описывать вероятностные модели, чтобы, с одной стороны, его мог понять движок вероятностного вывода, а с другой стороны, достаточно большое количество людей могло им пользоваться. Какие вообще формальные языки известны подавляющему большинству людей, которые возможно будут этим заниматься? Это языки программирования.
Идея вероятностного программирования заключается в следующем. Вы описываете вероятностную модель с помощью программы, которая фактически реализует вашу модель физического процесса. То есть это программа, которая, условно говоря, принимает на вход или генерирует в самом начале свойства интересующих вас объектов, а потом при помощи некоторого алгоритма генерирует наблюдаемые данные, периодически обращаясь к датчику случайных чисел, чтобы добавить туда немного шума. Такая программа задает вероятностную модель, задает совместное распределение, движок может проанализировать программу и понять, как делать вывод. Звучит, наверное, немного утопично, но в настоящее время действительно существует ряд движков, которые возможно работают не всегда и не для всех моделей, но позволяют делать вывод в интересных моделях среднего и высокого уровня сложности. Несколько перечислено на этом слайде.
Как же выглядит вероятностная программа? Давайте сначала посмотрим на очень простой и бесполезный, с практической точки зрения, пример, который, однако, проиллюстрирует те концепции, о которых мы говорим.
Модель очень простая: мы подкидываем две монетки, смотрим, упали ли они орлом или решкой, затем смотрим, упали ли они вместе орлом или решкой, или нет.
Как задать такую модель с помощью программы? Во-первых, мы заведем по логической переменной на каждую монетку. Эти переменные будут принимать значение «истина», если монета упала орлом, и «ложь», если монета упала решкой. И заведем еще одну переменную, которая будет принимать значение «истина», только когда обе монетки упали орлом.
Функция, которая здесь называется Bernoulli Sample, это просто обращение к датчику случайных чисел, который генерирует sample из распределения Bernoulli с заданным параметром 0,5. То есть эта функция с вероятностью 0,5 вернет значение «истина» и с вероятностью 0,5 вернет значение «ложь». Ее вызов эквивалентен подбрасыванию монетки.
Вот наша модель — теперь мы к этой модели можем делать какие-то запросы. Код вероятностных программ, который будет показан, — это некий псевдокод, который не соответствует, на самом деле, коду ни одного из движков вероятностного вывода, о которых шла речь. Потому что синтаксис этих движков не предназначен для показа на слайдах и сильно затрудняет понимание материала, но весь показанный код без проблем можно переложить на существующие движки без особых усилий и изменений этого кода, это чисто автоматическое и синтаксическое преобразование.
Вернемся к программе. Мы можем задать какой-то запрос к этой модели. Например, мы можем сказать, что мы пронаблюдали, что значение переменной bothHeads ложно, то есть обе монетки орлом не выпали. Теперь мы можем спросить, какая вероятность, что первая монетка выпала орлом? Какой ответ должен дать движок вероятностного программирования в данном случае? В нашем процессе есть четыре конфигурации орла и решки. Мы знаем, что конфигурация орел-орел исключена, и в оставшихся трех конфигурациях только в одной из них первая монетка выпадает орлом, true. Правильный ответ, который бы должен был дать любой движок вероятностного программирования в данном случае, это что апостериорное распределение на coin1Heads — это распределение Бернулли со значением параметра 1/3. С вероятностью 1/3 — орел, 2/3 — решка. Очень простая вероятностная программа.
Какая семантика у этих программ, как о них можно думать? Можно представить себе, что мы берем эту программу и запускаем ее бесконечное количество раз, каждый раз обращаясь к датчику случайных чисел, который генерирует числа из какого-то распределения, и у нас есть еще два оператора: infer – позволяет задавать вопросы, observe – говорит, что нам известно. Идея в том, что когда мы бесконечно запускаем эту программу, каждый раз, когда мы доходим до оператора infer, он каждый раз сохраняет куда-то себе текущее значение переменной и, условно говоря, запоминает все значения переменной, чтобы, когда вы его попросите, вернуть распределение на все значения. А оператор observe смотрит, равно ли в текущем исполнении программы значение переменной тому, чему оно должно быть равно. И если оно не равно, то он прерывает текущее исполнение программы и говорит всем операторам infer, что не надо было ничего в этом раунде запоминать, выбросьте все это, это плохое исполнение, не соответствует известным нам ограничениям.
На самом деле, ни один движок вероятностного вывода так не работает. Это было бы крайне неэффективно, но так об этом можно думать. Фактически такая программа задает совместное распределение на значения всех переменных в этой программе, если мы рассмотрим все бесконечные множества исполнений программы. Исключив все те исполнения, которые не соответствуют ограничениям.
Давайте рассмотрим еще не очень практичный, но уже более сложный пример вероятностной программы. А именно такую простую модель, как линейная регрессия. Посмотрим, как ее можно было на языке вероятностного программирования записать. Что такое линейная регрессия? У нас есть какое-то наблюдаемое значение, и мы считаем, что оно зависит от каких-то характеристик примерно линейно. Характеристики (они же features): допустим, у нас есть какие-то точки, каждая из них обладает вектором признаков, которые влияют линейно на наблюдаемое значение. То есть мы считаем его скалярное произведение с некоторым вектором весов, добавляем немного шума, чтобы эта линейная зависимость была не точной, а примерной. И так получаем наблюдаемое значение. Как это записать на языке вероятностного программирования? Для начала объявим массив признаков, который здесь обозначен Х, – это двумерный массив, где по первому измерению идут объекты нашей выборки, а по второму – значения признаков. Этот массив всегда наблюдаемый, мы можем, например, всегда вызвать функцию GetFeatures, которая считает его из файла, как в обычном программировании.
Теперь нам нужен вектор весов, собственно параметры этой модели. Это случайная переменная и мы зададим на нее нормальное априорное распределение. Каким образом? Мы просто сгенерируем все значения весов из нормального распределения с матожиданием 0 и дисперсией 1, вызвав функцию, которая просто генерирует число из распределения с заданными параметрами. Так, по сути, задается априорное распределение – мы просто пишем код, который генерирует из него. Теперь заведем вектор Y для значения регрессии и заполним его. Его значения равны скалярному произведению вектора весов на вектор признаков плюс немного случайного шума. Строка Y[n] инициализирует значение Y случайным шумом с матожиданием 0 и дисперсией 0,1 и затем этот цикл добавляет к значению, которое мы проинициализировали, скалярное произведение вектора признаков соответствующего объекта с вектором весов.
Теперь мы можем сказать, что значения Y мы пронаблюдали, считав их из файла или еще как-то, и спросить у движка вероятностного программирования, какое же апостериорное распределение на W при известном Y.
Это была пара простых примеров, которые должны были проиллюстрировать концепцию. Теперь давайте перейдем к интересным примерам — что вообще можно делать легко с помощью вероятностного программирования?
Сперва рассмотрим модель True Skill. Эта модель нужна, если у вас есть некая игра двух игроков, в которой исход – либо выиграл первый, либо выиграл второй. Также в ней есть результаты множества игр между игроками, а вы теперь про игроков хотите что-то понять. Например, вы хотите понять уровень мастерства игроков или вы хотите посчитать вероятность того, что первый игрок победит второго, для двух игроков, которые никогда не играли вместе. Зачем вообще это считать? Очевидные применения: спортивная аналитика или игровые сервисы, например онлайн.
В частности модель True Skill была впервые придумана Microsoft для Xbox Live, потому что в Halo при автоматическом выборе кому с кем играть, надо было обеспечить, чтобы игроки были примерно одинакового уровня, иначе никому бы не было интересно играть. Кроме того, с помощью таких моделей игр можно моделировать совершенно неигровые ситуации. В частности, в веб-поиске похожие модели используются для определения релевантности документов.
Когда, например, у нас есть сигнал о том, что кто-то сказал, что из данной пары документов при каких-то условиях лучше вот этот, а из данной пары — лучше вот этот, мы всегда можем эти сигналы сегрегировать, учесть и понять, какой документ действительно был самым лучшим, какой был не очень и т.д. Поэтому такие модели важно знать и полезно изучать. Одна из моделей решения этой задачи – True Skill. Она очень простая, но при этом удивительно мощная.
Идея в следующем: давайте каждого игрока опишем одним числом, которое показывает его мастерство. Чем число выше, тем игрок играет лучше, и наоборот. Когда два игрока встречаются вместе и играют в игру, как мы определим, кто выиграл, а кто проиграл? Мы возьмем мастерство игроков, прибавим к нему немного шума, чтобы даже тогда, когда первый игрок заведомо сильнее второго, он с некоторой вероятностью все равно мог ему проиграть. Чтобы наша модель могла сгенерировать все возможные исходы, а не только строго транзитивные, потому что в реальных данных такого не будет.
Как можно эту идею реализовать на языке вероятностного программирования? Заведем четыре массива. В первый запишем навыки каждого игрока, а остальные три массива будут описывать игры, в которые сыграли все игроки. Пусть у нас игроки для простоты нумеруются от 0 до PlayerCount-1, а игры — от 0 до GameCount-1. Во второй массив мы запишем в соответствующей игре, кто играл первым игроком, какой идентификатор у первого игрока от 0 до PlayerCount-1. В третий массив запишем всё соответственно для второго игрока, а в четвертый запишем величину, которая истинна, если в соответствующей игре выиграл первый игрок, и ложна, если выиграл второй.
Теперь нам нужно задать априорные распределения на эти переменные. В частности, скажем, что навыки мы просто генерируем из нормального распределения с центром в нуле и единичной дисперсией. Другими словами, априорно у всех навыки примерно одинаковые, и сильно экстремальное отклонение в сторону сильно хороших или плохих навыков маловероятно, потому что у нормального распределения довольно легкие хвосты.
Теперь мы можем сгенерировать исходы игры. Для каждой игры мы берем игрока, который был первый в ней, игрока, который был вторым, и считаем, насколько навыки первого игрока больше, чем навыки второго. Получаем некое преимущество первого над вторым. Теперь мы это преимущество «зашумляем» путем прибавления к нему нормального шума с нулевым матожиданием и небольшой дисперсией — так, чтобы тот, кто сильнее, с большой вероятностью выиграл, но мог и проиграть. Первый игрок выигрывает в том случае, если это зашумленное преимущество будет больше нуля. В ином случае выигрывает второй игрок. Вероятностная модель задана, и теперь мы можем назвать, результаты игр и то, какие навыки были у игроков. И получить апостериорное распределение на навыки.
С этой моделью можно делать довольно интересные вещи. В частности Microsoft Research сделали модификацию, которая называется True Skill through time.
По сути, модель та же самая, но теперь навыкам игроков разрешили каждый год меняться. То есть, каждый год к навыку прибавляется какой-то нормальный шум с нулевым матожиданием и небольшой дисперсией — навык может «плыть» во времени. Затем взяли историю шахматных матчей за 20 век, натравили на нее этот алгоритм и сравнили всех шахматных гроссмейстеров 20-го века. Даже тех, кто никогда вместе не играл. Этот график из статьи.
Другая интересная модель – DARE. Какую задачу решает эта модель? Представьте, что у вас есть некий тест, в нем сколько-то вопросов, на каждый вопрос сколько-то вариантов ответов, и у вас есть много студентов, которые прошли этот тест, ответили на вопросы, однако правильные ответы на вопросы вам неизвестны. Тем не менее, вы хотите понять, кто из студентов ответил правильно, кто — нет, и какие вообще были правильные ответы.
Зачем такую задачу решать? Есть такая область, особенно релевантная задачам веб-поиска, как краудсорсинг. Есть такие платформы, куда приходят люди, которые хотят подзаработать, а Яндекс им дает простые задания. Например, сказать, релевантен ли документ запросу или нерелевантен, есть ли собака на изображении или нет, и так далее. Проблема в том, что далеко не все люди, которые приходят на эти платформы, могут отвечать хорошо на поставленные вопросы. Особенно если вопросы не настолько тривиальны, как наличие или отсутствие животного на изображении. К тому же, многие из них пытаются хитрить. Например, отвечать как попало. Бывает, что сначала отвечают нормально, а потом устают. В итоге мы имеем большое количество очень шумных ответов, многие из которых неправильные. А какие правильные, мы не знаем, иначе бы мы эти задания на разметку не отправляли. И вот здесь нужны такие модели, которые позволят среди этого большого количества не всегда правильных ответов однозначно или с некоторым допущением определить правильные. Условно говоря, для каждой фотографии сказать, что на основании наблюдаемых данных с вероятностью 0,7 здесь была кошка. Как решать такую задачу? В литературе довольно много предложено моделей: Whitehil, BCC, DARE.
Давайте скажем, что каждый студент описывается одним числом – своими способностями. Чем выше у него способности, тем выше вероятность, что он на вопрос ответит правильно и наоборот. Каждый вопрос описывается двумя числами. Во-первых, сложностью – чем она больше, тем при прочих равных с меньшей вероятностью студент правильно ответит на вопрос. Во-вторых, discrimination – различительной способностью. Если discrimination у вопроса высокий, то тогда на ответ на вопрос навыки студента влияют, а если низкий, то не влияют. То есть можно представить себе вопрос, который был плохо сформулирован, и было непонятно, что там спрашивалось. И хороший студент или плохой – в итоге придется прибегнуть практически к случайному гаданию. Параметр discrimination призван такие ситуации моделировать.
Какая вероятностная программа будет соответствовать этой модели? Для начала нам нужно все параметры модели сгенерировать из соответствующих априорных распределений. Давайте скажем, что способности каждого студента мы генерируем из нормального распределения с центром в нуле и какой-то дисперсией. То есть мы говорим, что у всех примерно одинаковые способности, и экстремальные отклонения в сторону очень хороших и очень плохих от средних способностей маловероятны. Для каждого вопроса мы генерируем его сложность из такого же распределения — сложность и способность расположены как бы примерно на одной шкале. А различающую способность мы генерируем из гамма-распределения, в том числе по неким техническим причинам. Гамма-распределение – это распределение на положительной оси. То есть discrimination принимает значения больше нуля. При этом имеет среднее 1 и небольшую дисперсию. Истинные ответы мы не знаем, поэтому сгенерируем их, условно говоря, подкидывая кубик, у которого столько граней, сколько возможных вариантов ответа на вопрос.
Теперь нам нужно описать сам процесс ответа студентами на вопрос. Для каждого студента и для каждого вопроса мы сперва, как в модели True Skill, считаем преимущества студента над вопросом — то есть насколько способности студента превышают сложность вопроса. Теперь мы зашумляем это преимущество следующим образом: чем больше различающая способность вопроса discrimination, тем меньше мы зашумим преимущество, тем больше соотношение способностей и сложности действительно будет влиять на ситуацию. Для этого мы пользуемся функцией, которая генерирует из распределения с заданным матожиданием и точностью. Точность – это величина обратно пропорциональная дисперсии. Соответственно, чем больше discrimination, тем меньше дисперсия и наоборот.
Один из примеров из статьи про DARE. Взяли ответы студентов на IQ-тест и запустили модель DARE, которая правильных ответов не знает, но пытается их угадать и посчитать IQ каждого студента. И посчитали честный IQ. Если бы модель работала идеально, то все точки были бы расположены на черной прямой. По осям: по вертикали — IQ, который предсказала модель, по горизонтали – реальный IQ. Но, как видите, они расположены вдоль прямой, то есть модель довольно неплохо понимает, что происходит, хотя ничего о происходящем не знает.
Почему DARE работает? Если посмотреть на то, как работает вероятностный вывод в этой модели и постараться построить какую-то интуицию, то выяснится, что вывод работает примерно следующим образом. Мы сначала смотрим на то, что если много студентов ответили на какой-то вопрос одинаково, то, наверно, они все отвечали на него правильно и этот вопрос легкий. Если студент, который ответил на много вопросов так же, как на эти вопросы ответили остальные, то, наверно, этот студент знает, что делает, у него высокие способности. Тогда и на остальные ответы этого студента, где мы не так уже уверены, нужно смотреть более пристально – скорее всего, он там прав. Соответственно, если плохие и хорошие студенты отвечают одинаково на какой-то вопрос, то, наверно, у него довольно низкий discrimination. И так мы итеративно повторяем эти рассуждения много раз, пока наши апостериорные распределения не перестанут меняться с помощью этой логики.
Модели просмотра выдачи. Задача: в поисковиках есть много информации о том, что мы показали пользователям, куда они кликнули, а куда нет, и мы хотим что-то про этих пользователей понять — что им вообще было интересно, показали мы им хорошую выдачу или плохую.
Затем у нас есть такая задача, как обучение формулы ранжирования. То есть обучение тех самых моделей, которые из двух миллионов результатов, найденных по вашему запросу, должны понять, какие же десять нужно показать. Для того чтобы обучать такие модели, нужно очень много данных о том, какой документ релевантен какому запросу, а какой — не релевантен (обучающая выборка).
У нас есть специальные люди – асессоры. Их задача целый день сидеть и на заданные пары документ-запрос по сложной инструкции отвечать, релевантен ли документ запросу или нет. Но труд асессоров стоит денег, в больших количествах их нанять тяжело, так как это будет довольно дорого. А если пользоваться краудсорсинговыми платформами для таких сложных задач, то выясняется, что задачи оказываются неподъемно сложными для людей, которые туда приходят. Они просто не справляются с такими инструкциями, и получается что-то очень похожее на случай случайного угадывания. Тут возникает другая идея: если у нас есть клики пользователей по тому, что мы им уже показали, то, может, мы из этих кликов сами сможем восстановить, какие документы были релевантны, а какие — нет, и на этом уже обучать наши формулы ранжирования?
Решают такую задачу, моделируя некоторым образом то, как пользователь просматривает выдачу. Есть много способов разной степени сложности это сделать. Здесь изображен довольно простой способ, который, тем не менее, в некоторых местах, например в Яндексе, используется.
Идея такая. Пользователь смотрит выдачу сверху вниз. Вот он взял какой-то документ, и теперь ему нужно решить – кликнуть на этот документ или нет. Его решение зависит от того, насколько привлекательно краткое описание документа, которое есть на странице поисковых результатов. Даже если документ релевантен, а описание не очень, то пользователь никогда не узнает, что документ релевантен и туда не пойдет. В этой модели пользователь первым делом смотрит на описание и, если ему оно не понравилось, он с некоторой вероятностью решает посмотреть ещё документы и перейти на следующие, а с некоторой вероятностью получится так, что он устанет, разочаруется в нашем поиске и уйдёт в Google.
Если пользователь решает кликнуть на документ, то в этой модели он идет, смотрит на веб-страницу и решает, релевантен документ или нет. Эта переменная говорит, был ли релевантен документ. Если документ был релевантен, то пользователь в некоторой степени удовлетворяется этим документ и говорит, что он закончил и удовлетворил свою информационную потребность, а с некоторой вероятностью снова идет по этому циклу и смотрит следующий документ. И если следующий документ был нерелевантен, то опять же он может решить посмотреть еще или закончить. Такие модели в какой-то модификации используются. Здесь кода было бы слишком много, чтобы показывать программы, но принцип ясен, как такое можно было бы написать.
Как мы это применяем. Если есть клики, то можно понять релевантность и привлекательность сниппетов. Еще интересный пример. Допустим, у нас есть запрос, и мы по нему показываем какой-то набор документов. Да и вообще нам хорошо бы иметь какую-то метрику, которая говорит, хороший у нас поиск или плохой – какое-то число, за которым мы можем следить в течение времени и пытаться его всячески наращивать. Очень удобно иметь такое число. Как его построить? Можно в качестве метрики использовать вероятность того, что среднестатистический пользователь удовлетворился выдачей, и чем эта вероятность больше, тем всё работает лучше. Как рассчитать значение этой вероятности? Можно воспользоваться той же моделью – можно рассчитать ее параметры (вероятность устать, вероятность уйти в Google и т.д.) или на кликах, или, еще лучше, на реальной асессоровской разметке, чтобы значения параметров получились лучше, а дисперсия — меньше. И затем использовать это как формулу расчета какой-то целевой метрики, за которой мы в поиске следим. Это еще один способ применения этой модели.
Вероятностное моделирование – это зачастую довольно сложно, потому что нужно уметь писать код вероятностного вывода. В этом интересно разбираться, но постоянно этим заниматься не хочется. А вероятностное программирование – это, с некоторыми оговорками, сравнительно просто. Для того чтобы задавать вероятностные модели с помощью вероятностных программ, вам нужно знать основные принципы моделирования и уметь писать хоть какие-то программы. И движки вывода, которые существуют уже сейчас, позволяют работать в рамках этой парадигмы. Да, они иногда ломаются, иногда делают не то, что нужно, но в целом много интересных вещей с ними можно делать уже сейчас.
***
Коллоквиум факультета компьютерных наук ВШЭ – специальные семинары, на которые могут приходить не только студенты или сотрудники ФКН, но и все желающие. Их проводят учёные не только из Вышки, но и из других вузов и научных центров — МГУ, МФТИ, Математического института и института системного анализа РАН, MIT, Microsoft Research, Школы анализа данных Яндекса. Найти все прошедшие коллоквиумы можно здесь. По этой же ссылке можно будет и записаться на будущие занятия, когда начнётся новый учебный год.
Лекция была прочитана Борисом hr0nix Янгелем на факультете компьютерных наук, открытом в Высшей школе экономики при поддержке Яндекса. Сам Борис окончил ВМиК МГУ и Школу анализа данных Яндекса. Работал в Microsoft Research Cambridge в группе Кристофера Бишопа над фреймворком Infer.NET. Сейчас Борис — ведущий разработчик поиска Яндекса.
Под катом — расшифровка рассказа.
Моя задача сегодня — рассказать вам, что такое вероятностное программирование, и как эта сильно недооцененная парадигма в машинном обучении позволяет поставить всю мощь вероятностного моделирования на службу каждому, кто умеет программировать и обладает базовыми знаниями в теории вероятности, математической статистике и основах моделирования.
Чем вообще мы занимаемся в машинном обучении по сути? На самом деле, мы хотим как-то рассуждать о процессах в реальном мире и о том, как эти процессы устроены. Есть некие объекты, которые в этих процессах участвуют. Например, пользователь, который просматривает поисковую выдачу и решает, интересен ему поисковый результат или нет, кликнуть на него, посмотреть следующий результат или вообще уйти со страницы поиска. Это пример объектов. Объекты обладают некоторыми свойствами. Например, у пользователя это могут быть его какие-то сиюминутные информационные потребности, его интересы в целом. Соответственно, есть среда, в которой эти объекты существуют и которая тоже обладает какими-то свойствами. И есть, собственно, сам сложный процесс: процесс подкидывания монетки или процесс просмотра пользователем поисковой выдачи, о котором мы хотим рассуждать. И, как правило, мы имеем какие-то наблюдаемые проявления этого процесса, хотим его обратить и понять, какими были свойства объектов и среды, которые привели к тому, что мы наблюдали. Например, посмотрев несколько раз на то, упала ли монетка орлом или решкой, мы хотим узнать честная монетка или нет. Или, посмотрев несколько раз на то, куда кликал пользователь, мы хотим понять, ушел ли он с поиска счастливым или несчастным, нашел он то, что нужно, или нет, и были ли те документы, которые мы ему показали релевантными или нет.
Тут есть небольшая проблема. Тот сложный процесс, который мы хотим изучать, как правило, довольно проблематично описать наперед так, как он происходит. В случае с нашим пользователем это какие-то сложные биохимические процессы, которые протекают у него в мозгу, и которые в итоге заставляют его принять то или иное решение. Понятно, что обратить его — невероятно сложная вычислительная задача (даже если его можно описать), и таким никто заниматься не будет. Поэтому мы прибегаем к приему, который называется вероятностное моделирование и который заключается в следующем.
Сперва мы строим модели объектов, акцентируем наше внимание только на тех свойствах, которые, на наш взгляд, важны в этом процессе. А те, которые слабо на него влияют, мы игнорируем. Например, мы можем сказать, что монетка описывается одним числом своей честности, или можем сказать, что пользователь описывается вектором чисел, где каждая компонента вектора показывает его заинтересованность в той или иной теме. Например, первая компонента говорит о том, насколько ему интересно найти видео, вторая – насколько ему интересны фото со смешными котами, и так далее.
Далее у нас есть сложный процесс, который мы заменяем некой его округленной версией, которая, с одной стороны, имеет что-то общее с тем, что происходит в действительности, но, с другой стороны, достаточно проста, чтобы с ней можно было работать. В нашем гипотетическом примере с пользователем мы могли бы сказать, что он просматривает выдачу сверху вниз, и, если очередной результат удовлетворяет его информационной потребности, соотносится с его текущими интересами, то значит, он кликает и останавливается, а если нет, то идет дальше. Тут сразу возникает небольшая проблема: если мы посмотрим на реальные клики пользователей, то окажется, что модели, которые я только что предложил, не удовлетворяют в том смысле, что модель все эти паттерны кликов, которые мы наблюдаем в действительности, произвести не может. Например, пользователи иногда кликают на то, что им совсем неинтересно. Почему? Захотелось ему так, или, может он увидел какой-то результат, который его удивил, и захотелось кликнуть и посмотреть, что там будет. Соответственно, наша модель такие данные произвести не может, и в этом проблема.
Что делать? Тут применяется трюк, из-за которого эти модели и называются вероятностными: мы добавляем в модель немного шума, который призван промоделировать те сложные явления, которые напрямую мы промоделировать не можем. Мы считаем, что они такие сложные, что от шума сильно неотличимы, но зато добавление этого шума позволит нашей модели исторгнуть из себя все возможные наблюдения и тогда уже ее можно будет обращать.
В примере с пользователем можем сказать, что когда он видит очередной результат, он подкидывает монетку и в зависимости от того, как она выпала, решает, посмотреть ему этот результат, если он ему понравился, или пойти дальше, или устать и перестать смотреть выдачу. Таким образом, все паттерны кликов становятся возможны в рамках этой модели. Хотя какие-то более вероятны. И построенная модель все еще имеет смысл и соотносится с реальным физическим процессом, который мы хотим промоделировать.
Если мы такую модель построили, формально можно сказать, что мы построили совместное вероятностное распределение на свойствах объектов и наблюдаемых данных. Затем мы можем этот процесс обратить с помощью важной теоремы, которая называется теоремой Байеса и которая как раз говорит нам, как от наших априорных знаний об объектах, которые мы хотим изучать, пронаблюдав какие-то данные, уточнить эти знания и перейти к апостериорному вероятностному распределению. Вот в принципе вся суть вероятностного моделирования.
С вероятностным моделированием, к сожалению, есть ряд проблем. Саму модель разработать для какой-нибудь предметной области сравнительно легко. Не в том смысле, что разработать модель лучше всего существующего легко. Это, как правило, довольно сложно, потому что в отдельных предметных областях люди уже годами и десятилетиями только и делают, что придумывают модели. Но если, например, вы столкнулись с каким-то новым процессом, новой предметной областью, в которой вы более-менее разбираетесь и которую хотите промоделировать, и обладаете какими-то базовыми понятиями о том, как вообще вероятностные модели строятся, то придумать разумную модель, наверно, займет не очень много времени. Может быть, часы или дни. Затем вам нужно сделать, собственно, вывод в модели, воспользоваться теоремой Байеса, чтобы найти апостериорное распределение на интересующей вас переменной при условиях наблюдений. Ранее было сказано, что теорема Байеса дает вычислительный рецепт, который вам позволит это сделать для любой модели. С одной стороны, это правда, а с другой стороны, этот вычислительный рецепт может оказаться очень сложным. Грубо говоря, посчитать все члены в теореме Байеса для мало-мальски сложной модели просто не представляется вычислительно возможным. Поэтому уже несколько десятилетий разрабатываются приближенные методы Байесовского вывода, которые позволяют найти некое приближение для апостериорного распределения, которое в определенных условиях будет хорошим приближением. В общем, если вы хотите делать вероятностный вывод сложных вероятностных моделей, то вам неизбежно к таким методам приближенного вывода придется прибегать.
Здесь перечислены несколько таких методов, это EP, VMP, MCMC. Все эти методы довольно сложные в реализации, концептуальные и не очень простые. В результате чтобы написать вывод в какой-то вашей вероятностной модели, вам нужно потратить очень много времени, разобраться в этом. При этом для по-настоящему сложных моделей потребуются знания уровня PhD в машинном обучении, причем не просто в машинном обучении, а лучше специализированно в Байесовском выводе. Тогда у вас есть шансы правильно и без ошибок написать код вывода в этой модели, который действительно будет делать то, что вы думаете.
Соответственно, это все сильно осложняет экспериментирование. Например, потребовать одну модель займет несколько недель, и неизвестно, получится или нет. Что уж говорить о том, чтобы попробовать несколько альтернативных моделей – мало у кого хватит терпения и сил на такое. Наблюдается такая тенденция, что мало кто готов в своих задачах пробовать сложные модели, потому что, как правило, чем сложнее модель, тем сложнее код вывода, и мало кто может его написать. Поэтому все ограничиваются простыми моделями. Однако очень часто, более сложные модели имеют большую предсказательную мощь, и потенциально от их использования можно получить очень много профита.
Ученые думали, как бороться с этой проблемой, и в качестве одного из решений была предложена такая парадигма, как вероятностное программирование. Эта парадигма основана на двух идеях. Первая – вы не должны писать код вероятностного вывода сами. Это сложно, и лучше все это оставить экспертам. Все, что вы должны делать, это задавать вероятностные модели, говорить, что вы пронаблюдали, апостериорные распределения на какие переменные в вашей модели вас интересуют. Далее черная коробка, движок вероятностного вывода, должен сделать вывод за вас. Вторая идея — мы хотим, чтобы всей мощью вероятностного моделирования могли пользоваться как можно больше людей. Нужен такой способ формально описывать вероятностные модели, чтобы, с одной стороны, его мог понять движок вероятностного вывода, а с другой стороны, достаточно большое количество людей могло им пользоваться. Какие вообще формальные языки известны подавляющему большинству людей, которые возможно будут этим заниматься? Это языки программирования.
Идея вероятностного программирования заключается в следующем. Вы описываете вероятностную модель с помощью программы, которая фактически реализует вашу модель физического процесса. То есть это программа, которая, условно говоря, принимает на вход или генерирует в самом начале свойства интересующих вас объектов, а потом при помощи некоторого алгоритма генерирует наблюдаемые данные, периодически обращаясь к датчику случайных чисел, чтобы добавить туда немного шума. Такая программа задает вероятностную модель, задает совместное распределение, движок может проанализировать программу и понять, как делать вывод. Звучит, наверное, немного утопично, но в настоящее время действительно существует ряд движков, которые возможно работают не всегда и не для всех моделей, но позволяют делать вывод в интересных моделях среднего и высокого уровня сложности. Несколько перечислено на этом слайде.
Как же выглядит вероятностная программа? Давайте сначала посмотрим на очень простой и бесполезный, с практической точки зрения, пример, который, однако, проиллюстрирует те концепции, о которых мы говорим.
Модель очень простая: мы подкидываем две монетки, смотрим, упали ли они орлом или решкой, затем смотрим, упали ли они вместе орлом или решкой, или нет.
Как задать такую модель с помощью программы? Во-первых, мы заведем по логической переменной на каждую монетку. Эти переменные будут принимать значение «истина», если монета упала орлом, и «ложь», если монета упала решкой. И заведем еще одну переменную, которая будет принимать значение «истина», только когда обе монетки упали орлом.
Функция, которая здесь называется Bernoulli Sample, это просто обращение к датчику случайных чисел, который генерирует sample из распределения Bernoulli с заданным параметром 0,5. То есть эта функция с вероятностью 0,5 вернет значение «истина» и с вероятностью 0,5 вернет значение «ложь». Ее вызов эквивалентен подбрасыванию монетки.
Вот наша модель — теперь мы к этой модели можем делать какие-то запросы. Код вероятностных программ, который будет показан, — это некий псевдокод, который не соответствует, на самом деле, коду ни одного из движков вероятностного вывода, о которых шла речь. Потому что синтаксис этих движков не предназначен для показа на слайдах и сильно затрудняет понимание материала, но весь показанный код без проблем можно переложить на существующие движки без особых усилий и изменений этого кода, это чисто автоматическое и синтаксическое преобразование.
Вернемся к программе. Мы можем задать какой-то запрос к этой модели. Например, мы можем сказать, что мы пронаблюдали, что значение переменной bothHeads ложно, то есть обе монетки орлом не выпали. Теперь мы можем спросить, какая вероятность, что первая монетка выпала орлом? Какой ответ должен дать движок вероятностного программирования в данном случае? В нашем процессе есть четыре конфигурации орла и решки. Мы знаем, что конфигурация орел-орел исключена, и в оставшихся трех конфигурациях только в одной из них первая монетка выпадает орлом, true. Правильный ответ, который бы должен был дать любой движок вероятностного программирования в данном случае, это что апостериорное распределение на coin1Heads — это распределение Бернулли со значением параметра 1/3. С вероятностью 1/3 — орел, 2/3 — решка. Очень простая вероятностная программа.
Какая семантика у этих программ, как о них можно думать? Можно представить себе, что мы берем эту программу и запускаем ее бесконечное количество раз, каждый раз обращаясь к датчику случайных чисел, который генерирует числа из какого-то распределения, и у нас есть еще два оператора: infer – позволяет задавать вопросы, observe – говорит, что нам известно. Идея в том, что когда мы бесконечно запускаем эту программу, каждый раз, когда мы доходим до оператора infer, он каждый раз сохраняет куда-то себе текущее значение переменной и, условно говоря, запоминает все значения переменной, чтобы, когда вы его попросите, вернуть распределение на все значения. А оператор observe смотрит, равно ли в текущем исполнении программы значение переменной тому, чему оно должно быть равно. И если оно не равно, то он прерывает текущее исполнение программы и говорит всем операторам infer, что не надо было ничего в этом раунде запоминать, выбросьте все это, это плохое исполнение, не соответствует известным нам ограничениям.
На самом деле, ни один движок вероятностного вывода так не работает. Это было бы крайне неэффективно, но так об этом можно думать. Фактически такая программа задает совместное распределение на значения всех переменных в этой программе, если мы рассмотрим все бесконечные множества исполнений программы. Исключив все те исполнения, которые не соответствуют ограничениям.
Давайте рассмотрим еще не очень практичный, но уже более сложный пример вероятностной программы. А именно такую простую модель, как линейная регрессия. Посмотрим, как ее можно было на языке вероятностного программирования записать. Что такое линейная регрессия? У нас есть какое-то наблюдаемое значение, и мы считаем, что оно зависит от каких-то характеристик примерно линейно. Характеристики (они же features): допустим, у нас есть какие-то точки, каждая из них обладает вектором признаков, которые влияют линейно на наблюдаемое значение. То есть мы считаем его скалярное произведение с некоторым вектором весов, добавляем немного шума, чтобы эта линейная зависимость была не точной, а примерной. И так получаем наблюдаемое значение. Как это записать на языке вероятностного программирования? Для начала объявим массив признаков, который здесь обозначен Х, – это двумерный массив, где по первому измерению идут объекты нашей выборки, а по второму – значения признаков. Этот массив всегда наблюдаемый, мы можем, например, всегда вызвать функцию GetFeatures, которая считает его из файла, как в обычном программировании.
Теперь нам нужен вектор весов, собственно параметры этой модели. Это случайная переменная и мы зададим на нее нормальное априорное распределение. Каким образом? Мы просто сгенерируем все значения весов из нормального распределения с матожиданием 0 и дисперсией 1, вызвав функцию, которая просто генерирует число из распределения с заданными параметрами. Так, по сути, задается априорное распределение – мы просто пишем код, который генерирует из него. Теперь заведем вектор Y для значения регрессии и заполним его. Его значения равны скалярному произведению вектора весов на вектор признаков плюс немного случайного шума. Строка Y[n] инициализирует значение Y случайным шумом с матожиданием 0 и дисперсией 0,1 и затем этот цикл добавляет к значению, которое мы проинициализировали, скалярное произведение вектора признаков соответствующего объекта с вектором весов.
Теперь мы можем сказать, что значения Y мы пронаблюдали, считав их из файла или еще как-то, и спросить у движка вероятностного программирования, какое же апостериорное распределение на W при известном Y.
Это была пара простых примеров, которые должны были проиллюстрировать концепцию. Теперь давайте перейдем к интересным примерам — что вообще можно делать легко с помощью вероятностного программирования?
Сперва рассмотрим модель True Skill. Эта модель нужна, если у вас есть некая игра двух игроков, в которой исход – либо выиграл первый, либо выиграл второй. Также в ней есть результаты множества игр между игроками, а вы теперь про игроков хотите что-то понять. Например, вы хотите понять уровень мастерства игроков или вы хотите посчитать вероятность того, что первый игрок победит второго, для двух игроков, которые никогда не играли вместе. Зачем вообще это считать? Очевидные применения: спортивная аналитика или игровые сервисы, например онлайн.
В частности модель True Skill была впервые придумана Microsoft для Xbox Live, потому что в Halo при автоматическом выборе кому с кем играть, надо было обеспечить, чтобы игроки были примерно одинакового уровня, иначе никому бы не было интересно играть. Кроме того, с помощью таких моделей игр можно моделировать совершенно неигровые ситуации. В частности, в веб-поиске похожие модели используются для определения релевантности документов.
Когда, например, у нас есть сигнал о том, что кто-то сказал, что из данной пары документов при каких-то условиях лучше вот этот, а из данной пары — лучше вот этот, мы всегда можем эти сигналы сегрегировать, учесть и понять, какой документ действительно был самым лучшим, какой был не очень и т.д. Поэтому такие модели важно знать и полезно изучать. Одна из моделей решения этой задачи – True Skill. Она очень простая, но при этом удивительно мощная.
Идея в следующем: давайте каждого игрока опишем одним числом, которое показывает его мастерство. Чем число выше, тем игрок играет лучше, и наоборот. Когда два игрока встречаются вместе и играют в игру, как мы определим, кто выиграл, а кто проиграл? Мы возьмем мастерство игроков, прибавим к нему немного шума, чтобы даже тогда, когда первый игрок заведомо сильнее второго, он с некоторой вероятностью все равно мог ему проиграть. Чтобы наша модель могла сгенерировать все возможные исходы, а не только строго транзитивные, потому что в реальных данных такого не будет.
Как можно эту идею реализовать на языке вероятностного программирования? Заведем четыре массива. В первый запишем навыки каждого игрока, а остальные три массива будут описывать игры, в которые сыграли все игроки. Пусть у нас игроки для простоты нумеруются от 0 до PlayerCount-1, а игры — от 0 до GameCount-1. Во второй массив мы запишем в соответствующей игре, кто играл первым игроком, какой идентификатор у первого игрока от 0 до PlayerCount-1. В третий массив запишем всё соответственно для второго игрока, а в четвертый запишем величину, которая истинна, если в соответствующей игре выиграл первый игрок, и ложна, если выиграл второй.
Теперь нам нужно задать априорные распределения на эти переменные. В частности, скажем, что навыки мы просто генерируем из нормального распределения с центром в нуле и единичной дисперсией. Другими словами, априорно у всех навыки примерно одинаковые, и сильно экстремальное отклонение в сторону сильно хороших или плохих навыков маловероятно, потому что у нормального распределения довольно легкие хвосты.
Теперь мы можем сгенерировать исходы игры. Для каждой игры мы берем игрока, который был первый в ней, игрока, который был вторым, и считаем, насколько навыки первого игрока больше, чем навыки второго. Получаем некое преимущество первого над вторым. Теперь мы это преимущество «зашумляем» путем прибавления к нему нормального шума с нулевым матожиданием и небольшой дисперсией — так, чтобы тот, кто сильнее, с большой вероятностью выиграл, но мог и проиграть. Первый игрок выигрывает в том случае, если это зашумленное преимущество будет больше нуля. В ином случае выигрывает второй игрок. Вероятностная модель задана, и теперь мы можем назвать, результаты игр и то, какие навыки были у игроков. И получить апостериорное распределение на навыки.
С этой моделью можно делать довольно интересные вещи. В частности Microsoft Research сделали модификацию, которая называется True Skill through time.
По сути, модель та же самая, но теперь навыкам игроков разрешили каждый год меняться. То есть, каждый год к навыку прибавляется какой-то нормальный шум с нулевым матожиданием и небольшой дисперсией — навык может «плыть» во времени. Затем взяли историю шахматных матчей за 20 век, натравили на нее этот алгоритм и сравнили всех шахматных гроссмейстеров 20-го века. Даже тех, кто никогда вместе не играл. Этот график из статьи.
Другая интересная модель – DARE. Какую задачу решает эта модель? Представьте, что у вас есть некий тест, в нем сколько-то вопросов, на каждый вопрос сколько-то вариантов ответов, и у вас есть много студентов, которые прошли этот тест, ответили на вопросы, однако правильные ответы на вопросы вам неизвестны. Тем не менее, вы хотите понять, кто из студентов ответил правильно, кто — нет, и какие вообще были правильные ответы.
Зачем такую задачу решать? Есть такая область, особенно релевантная задачам веб-поиска, как краудсорсинг. Есть такие платформы, куда приходят люди, которые хотят подзаработать, а Яндекс им дает простые задания. Например, сказать, релевантен ли документ запросу или нерелевантен, есть ли собака на изображении или нет, и так далее. Проблема в том, что далеко не все люди, которые приходят на эти платформы, могут отвечать хорошо на поставленные вопросы. Особенно если вопросы не настолько тривиальны, как наличие или отсутствие животного на изображении. К тому же, многие из них пытаются хитрить. Например, отвечать как попало. Бывает, что сначала отвечают нормально, а потом устают. В итоге мы имеем большое количество очень шумных ответов, многие из которых неправильные. А какие правильные, мы не знаем, иначе бы мы эти задания на разметку не отправляли. И вот здесь нужны такие модели, которые позволят среди этого большого количества не всегда правильных ответов однозначно или с некоторым допущением определить правильные. Условно говоря, для каждой фотографии сказать, что на основании наблюдаемых данных с вероятностью 0,7 здесь была кошка. Как решать такую задачу? В литературе довольно много предложено моделей: Whitehil, BCC, DARE.
Давайте скажем, что каждый студент описывается одним числом – своими способностями. Чем выше у него способности, тем выше вероятность, что он на вопрос ответит правильно и наоборот. Каждый вопрос описывается двумя числами. Во-первых, сложностью – чем она больше, тем при прочих равных с меньшей вероятностью студент правильно ответит на вопрос. Во-вторых, discrimination – различительной способностью. Если discrimination у вопроса высокий, то тогда на ответ на вопрос навыки студента влияют, а если низкий, то не влияют. То есть можно представить себе вопрос, который был плохо сформулирован, и было непонятно, что там спрашивалось. И хороший студент или плохой – в итоге придется прибегнуть практически к случайному гаданию. Параметр discrimination призван такие ситуации моделировать.
Какая вероятностная программа будет соответствовать этой модели? Для начала нам нужно все параметры модели сгенерировать из соответствующих априорных распределений. Давайте скажем, что способности каждого студента мы генерируем из нормального распределения с центром в нуле и какой-то дисперсией. То есть мы говорим, что у всех примерно одинаковые способности, и экстремальные отклонения в сторону очень хороших и очень плохих от средних способностей маловероятны. Для каждого вопроса мы генерируем его сложность из такого же распределения — сложность и способность расположены как бы примерно на одной шкале. А различающую способность мы генерируем из гамма-распределения, в том числе по неким техническим причинам. Гамма-распределение – это распределение на положительной оси. То есть discrimination принимает значения больше нуля. При этом имеет среднее 1 и небольшую дисперсию. Истинные ответы мы не знаем, поэтому сгенерируем их, условно говоря, подкидывая кубик, у которого столько граней, сколько возможных вариантов ответа на вопрос.
Теперь нам нужно описать сам процесс ответа студентами на вопрос. Для каждого студента и для каждого вопроса мы сперва, как в модели True Skill, считаем преимущества студента над вопросом — то есть насколько способности студента превышают сложность вопроса. Теперь мы зашумляем это преимущество следующим образом: чем больше различающая способность вопроса discrimination, тем меньше мы зашумим преимущество, тем больше соотношение способностей и сложности действительно будет влиять на ситуацию. Для этого мы пользуемся функцией, которая генерирует из распределения с заданным матожиданием и точностью. Точность – это величина обратно пропорциональная дисперсии. Соответственно, чем больше discrimination, тем меньше дисперсия и наоборот.
Один из примеров из статьи про DARE. Взяли ответы студентов на IQ-тест и запустили модель DARE, которая правильных ответов не знает, но пытается их угадать и посчитать IQ каждого студента. И посчитали честный IQ. Если бы модель работала идеально, то все точки были бы расположены на черной прямой. По осям: по вертикали — IQ, который предсказала модель, по горизонтали – реальный IQ. Но, как видите, они расположены вдоль прямой, то есть модель довольно неплохо понимает, что происходит, хотя ничего о происходящем не знает.
Почему DARE работает? Если посмотреть на то, как работает вероятностный вывод в этой модели и постараться построить какую-то интуицию, то выяснится, что вывод работает примерно следующим образом. Мы сначала смотрим на то, что если много студентов ответили на какой-то вопрос одинаково, то, наверно, они все отвечали на него правильно и этот вопрос легкий. Если студент, который ответил на много вопросов так же, как на эти вопросы ответили остальные, то, наверно, этот студент знает, что делает, у него высокие способности. Тогда и на остальные ответы этого студента, где мы не так уже уверены, нужно смотреть более пристально – скорее всего, он там прав. Соответственно, если плохие и хорошие студенты отвечают одинаково на какой-то вопрос, то, наверно, у него довольно низкий discrimination. И так мы итеративно повторяем эти рассуждения много раз, пока наши апостериорные распределения не перестанут меняться с помощью этой логики.
Модели просмотра выдачи. Задача: в поисковиках есть много информации о том, что мы показали пользователям, куда они кликнули, а куда нет, и мы хотим что-то про этих пользователей понять — что им вообще было интересно, показали мы им хорошую выдачу или плохую.
Затем у нас есть такая задача, как обучение формулы ранжирования. То есть обучение тех самых моделей, которые из двух миллионов результатов, найденных по вашему запросу, должны понять, какие же десять нужно показать. Для того чтобы обучать такие модели, нужно очень много данных о том, какой документ релевантен какому запросу, а какой — не релевантен (обучающая выборка).
У нас есть специальные люди – асессоры. Их задача целый день сидеть и на заданные пары документ-запрос по сложной инструкции отвечать, релевантен ли документ запросу или нет. Но труд асессоров стоит денег, в больших количествах их нанять тяжело, так как это будет довольно дорого. А если пользоваться краудсорсинговыми платформами для таких сложных задач, то выясняется, что задачи оказываются неподъемно сложными для людей, которые туда приходят. Они просто не справляются с такими инструкциями, и получается что-то очень похожее на случай случайного угадывания. Тут возникает другая идея: если у нас есть клики пользователей по тому, что мы им уже показали, то, может, мы из этих кликов сами сможем восстановить, какие документы были релевантны, а какие — нет, и на этом уже обучать наши формулы ранжирования?
Решают такую задачу, моделируя некоторым образом то, как пользователь просматривает выдачу. Есть много способов разной степени сложности это сделать. Здесь изображен довольно простой способ, который, тем не менее, в некоторых местах, например в Яндексе, используется.
Идея такая. Пользователь смотрит выдачу сверху вниз. Вот он взял какой-то документ, и теперь ему нужно решить – кликнуть на этот документ или нет. Его решение зависит от того, насколько привлекательно краткое описание документа, которое есть на странице поисковых результатов. Даже если документ релевантен, а описание не очень, то пользователь никогда не узнает, что документ релевантен и туда не пойдет. В этой модели пользователь первым делом смотрит на описание и, если ему оно не понравилось, он с некоторой вероятностью решает посмотреть ещё документы и перейти на следующие, а с некоторой вероятностью получится так, что он устанет, разочаруется в нашем поиске и уйдёт в Google.
Если пользователь решает кликнуть на документ, то в этой модели он идет, смотрит на веб-страницу и решает, релевантен документ или нет. Эта переменная говорит, был ли релевантен документ. Если документ был релевантен, то пользователь в некоторой степени удовлетворяется этим документ и говорит, что он закончил и удовлетворил свою информационную потребность, а с некоторой вероятностью снова идет по этому циклу и смотрит следующий документ. И если следующий документ был нерелевантен, то опять же он может решить посмотреть еще или закончить. Такие модели в какой-то модификации используются. Здесь кода было бы слишком много, чтобы показывать программы, но принцип ясен, как такое можно было бы написать.
Как мы это применяем. Если есть клики, то можно понять релевантность и привлекательность сниппетов. Еще интересный пример. Допустим, у нас есть запрос, и мы по нему показываем какой-то набор документов. Да и вообще нам хорошо бы иметь какую-то метрику, которая говорит, хороший у нас поиск или плохой – какое-то число, за которым мы можем следить в течение времени и пытаться его всячески наращивать. Очень удобно иметь такое число. Как его построить? Можно в качестве метрики использовать вероятность того, что среднестатистический пользователь удовлетворился выдачей, и чем эта вероятность больше, тем всё работает лучше. Как рассчитать значение этой вероятности? Можно воспользоваться той же моделью – можно рассчитать ее параметры (вероятность устать, вероятность уйти в Google и т.д.) или на кликах, или, еще лучше, на реальной асессоровской разметке, чтобы значения параметров получились лучше, а дисперсия — меньше. И затем использовать это как формулу расчета какой-то целевой метрики, за которой мы в поиске следим. Это еще один способ применения этой модели.
Вероятностное моделирование – это зачастую довольно сложно, потому что нужно уметь писать код вероятностного вывода. В этом интересно разбираться, но постоянно этим заниматься не хочется. А вероятностное программирование – это, с некоторыми оговорками, сравнительно просто. Для того чтобы задавать вероятностные модели с помощью вероятностных программ, вам нужно знать основные принципы моделирования и уметь писать хоть какие-то программы. И движки вывода, которые существуют уже сейчас, позволяют работать в рамках этой парадигмы. Да, они иногда ломаются, иногда делают не то, что нужно, но в целом много интересных вещей с ними можно делать уже сейчас.
***
Коллоквиум факультета компьютерных наук ВШЭ – специальные семинары, на которые могут приходить не только студенты или сотрудники ФКН, но и все желающие. Их проводят учёные не только из Вышки, но и из других вузов и научных центров — МГУ, МФТИ, Математического института и института системного анализа РАН, MIT, Microsoft Research, Школы анализа данных Яндекса. Найти все прошедшие коллоквиумы можно здесь. По этой же ссылке можно будет и записаться на будущие занятия, когда начнётся новый учебный год.
