0:00
В этом
видео мы поговорим о параметрических методах восстановления плотности и о том,
как с их помощью решать задачу обнаружения аномалий.
Как мы уже обсудили, задача обнаружения аномалий — это про то, как найти объекты,
которые не похожи на большинство.
Скажем, на этой картинке белые объекты — это те,
которых большинство и которые похожи друг на друга, а черные — это те,
которые явно выбиваются из большинства, наверняка это некие аномалии.
В вероятностном подходе к обнаружению аномалий мы считаем,
что аномалия — это такой объект,
который был получен из другого распределения, не из того распределения,
которое сгенерировало нам основную обучающую выборку.
При этом возникает вопрос о том, а как найти распределение,
из которого выборка была сгенерирована.
Если мы ее найдем, то сможем на основе этого распределния оценивать вероятность
того, что новый объект пришел из него же или из какого-то другого распределения.
Если вероятность получить новый объект из этого распределения очень мала, то,
скорее всего, это аномалия.
Есть три основных подхода к восстановлению вероятностных плотностей — это
параметрический подход, непараметрический подход и восстановление смесей.
Про параметрический подход и восстановление смесей мы поговорим в этом
видео, а про непараметрический — уже в следующем.
Итак, мы считаем, что существует некоторое вероятностное
распределение p(x) на наших объектах — на всех объектах, которые мы можем получить.
В параметрическом подходе считается, что это распределение является
параметрическим, то есть на самом деле это некое распределение φ от x,
которое зависит от некоторого параметра θ.
Один из самых ярких примеров параметрического семейства
распределений — это нормальное распределение.
Как вы знаете, нормальное распределение состоит из двух параметров — μ и Σ,
центр и ковариационная матрица.
По форме нормальное распределение похоже на шляпу,
при этом параметр μ определяет, где находится центр этой шляпы,
а параметр Σ определяет разброс этой шляпы, то есть то,
насколько она сосредоточена вокруг центра или размазана по всему пространству.
Таким образом, если мы пользуемся нормальным распределением
и пытаемся смоделировать с его помощью нашу выборку,
то нам нужно как-то найти два параметра — μ и Σ.
Как это делать?
Было бы логично искать параметр распределения так, чтобы вероятность
объектов обучающей выборки с точки зрения этого распределения была максимальна.
В этом случае объекты, которые не похожи на эту выборку, скорее всего,
будут получать низкие вероятности.
Собственно, именно так и работает метод максимального правдоподобия, который
старается подобрать такое распределение из параметрического семейства,
что с его точки зрения объекты обучающей выборки будут как можно более вероятны.
Собственно, формально эта задача записывается вот так.
Работать с самим правдоподобием неудобно, поскольку это — произведение значений
плотности во всех точках обучающей выборки.
Вместо этого мы берем его логарифм и получаем такую задачу: логарифм...
сумма логарифмов значений плотности во всех точках обучающей выборки.
И эту сумму мы пытаемся максимизировать.
Для некоторых распределений эту задачу можно решить аналитически,
если посчитать частные производные и приравнять их к 0.
Например, для нормального распределения такие решения существуют.
Оказывается, что параметр μ оценивается просто как среднее по всем
объектам выборки, а параметр Σ вычисляется как выборочная ковариационная
матрица для этой же выборки, которая считается вот по такой формуле.
Таким образом, если мы выбираем нормальное распределение, если мы считаем,
что выборка действительно пришла из него, то нужно просто вычислить параметры этого
распределения вот по этим формулам — совершенно ничего сложного.
Вот пример: есть некоторая выборка, которая...
в общем-то похоже, что она пришла из нормального распределения,
поскольку ее форма похожа на эллипс.
Если мы подгоним методом максимального правдоподобия нормальное распределение под
эту выборку, то оно будет выглядеть так, как показывают линии уровня.
Внутри синей линии уровня констатируется 90 % всей вероятности,
внутри зеленой — 95 %, внутри красной линии
уровня — 99 % распределения вероятности нормального распределения.
Таким образом, вероятность получить объект вне красного эллипса очень мала.
При этом в нашей выборке есть две точки, которые находятся вне него.
Поскольку основная выборка очень хорошо описывается этим нормальным
распределением, а те две синие точки очень плохо им описываются,
то можно предположить, что они пришли из другого распределения,
что это как раз таки аномалия.
Собственно, мы уже описали алгоритм поиска аномалий,
если у нас уже есть некоторое распределение на объектах.
Итак, допустим, мы нашли распределение p(x), и к нам приходит новый объект x.
Мы вычисляем его вероятность осуществления,
этого распределения — p(x) — и сравниваем с некоторым порогом t.
Если вероятность меньше этого порога, то мы объявляем этот объект аномалией.
При этом встает вопрос о том, а как вообще выбирать порог t.
Здесь нет каких-то однозначных рекомендаций — можно, например,
выбирать его из априорных соображений, то есть вот на прошлом слайде мы рассуждали,
что внутри линий уровня находится 99 % распределения, и мы верим в то,
что все нормальные объекты будут там расположены.
А все, что вне — объявляем аномалиями.
Или, например, если у вас откуда-то есть размеченные примеры аномалий,
то есть у вас есть несколько объектов выборки и вы точно знаете,
что они аномальные, то можно подобрать порог t так, чтобы эти объекты были
объявлены аномальными, а все остальные объекты считались нормальными,
считались сгенерированными из нашего распределения p(x).
В некоторых случаях параметрического подхода оказывается недостаточно.
Скажем, на этой выборке, на этой картинке нарисована выборка,
которая на самом деле сгенерирована из двух распределений.
Эти оба распределения являются нормальными,
у них одинаковые матрицы ковариаций, но разные центры.
Таким образом, получается два облака точек: левое и правое.
Синее облако сгенерировано из одного нормального распределения,
красное — из другого.
Объяснить эту выборку одним нормальным распределением будет невозможно,
зато отлично подходит модель смеси распределений.
Вы уже познакомились с этой моделью и ее настройкой,
когда говорили про кластеризацию с помощью EM-алгоритма.
Собственно, для восстановления плотности EM-алгоритм тоже отлично подходит.
Напомню, что смесью называется такое распределение p(x),
которое представляется в виде взвешенной суммы других распределений pj(x).
pj(x) называются компонентами смеси, и, как правило,
они уже являются параметрическими распределениями.
Например, каждая из них — это нормальное распределение,
но у каждого — свои параметры.
Собственно, каждая компонента pj является членом параметрического семейства φ(x)
со своим параметром θj.
EM-алгоритм состоит из повторения E-шага и M-шага до тех пор,
пока не будет достигнута сходимость.
На E-шаге мы вычисляем апостериорные вероятности того,
что i-тый объект принадлежит j-той компоненте смеси.
И это делается вот по такой формуле.
Она выражается через веса компонент, через значения вероятности в
каждой компоненте и нормируется на общее значение вероятности p(x).
На M-шаге мы используем эти апостериорные вероятности,
чтобы обновить наши оценки на параметре θ.
И эти оценки вычисляются путем решения задачи максимизации взвешенного
правдоподобия, то есть здесь формула такая же, как в методе максимума правдоподобия,
но только перед каждым слагаемым стоит вес gji,
где gji — это те самые апостериорные вероятности.
И эти шаги повторяются до тех пор,
пока значения параметров θj не станут меняться слишком слабо.
Благодаря этому алгоритму можно подогнать смесь из K- компонент,
из K-распределений, под нашу выборку.
И понятно, что такая модель распределения — гораздо более сложная, чем, например,
попытки приблизить всю выборку одним нормальным распределением.
Итак, мы обсудили вероятностный подход к обнаружению аномалий,
в котором считается, что аномалия — это такой объект,
который приходит из другого вероятностного распределения.
И обсудили параметрические методы восстановления распределения,
в частности восстановление с помощью метода максимального правдоподобия и
восстановление с помощью смесей,
с помощью моделирования выборки смесью распределений.
После того как мы имеем распределения, описывающие нашу выборку, мы можем очень
легко обнаруживать аномалии путем вычисления вероятности нового объекта.
Чем она меньше, тем больше шансов,
что этот объект аномальный и не похож на большинство других объектов.
В следующем видео мы продолжим разговор о вероятностных методах и поговорим про
непараметрическое восстановление плотности.
Evgeniy Riabenko
Evgeny Sokolov
Victor Kantor
Emeli Dral
Константин Воронцовдоктор физико-математических наук, профессор
