Измерение статистического сходства между двумя образцами с использованием Йенсена-Шеннона и Кульбака-Лейблера…

Можно ли количественно оценить качество информации, которую мы получаем каждый день? Как мы можем измерить расстояние между двумя статистическими выборками?

Вступление

В последние годы объем информации, генерируемой и обрабатываемой ежедневно, легко превосходит объем информации десятилетней давности. Текущий этап сбора и хранения очень больших объемов данных беспрецедентен. В этом сценарии возникают новые проблемы, требующие более интеллектуальных решений. Одна из самых больших проблем - правильно идентифицировать изменения в базовых процессах и структурах, которые генерируют данные, которые обновляются каждый день. Являются ли изменения в данных следствием «ошибок», сбоев, действительно резких или постепенных, затрудняет разработку единого эффективного механизма обнаружения. Возможное решение состоит в измерении расхождения между двумя распределениями. В его основе лежат основные концепции теории информации. Здесь мы вводим две меры расхождения, но только одну фактическую метрику расстояния.

Меры подобия для распределений вероятностей

энтропия дискретной случайной величины X - это измерение количества информации, необходимой в среднем для описания этой переменной. Это самый важный показатель в теории информации, поскольку он измеряет неопределенность данной переменной. Шеннон определил энтропию H дискретной случайной величины X с функцией массы вероятности P (x) как:

В предыдущем уравнении, если мы установим b = 2 в логарифмическом выражении, мы сможем оценить минимальное значение в битах, необходимое для кодирования всей информации, содержащейся в X. Относительная энтропия измеряет, насколько два распределения удалены друг от друга. Это также называется расхождением Кульбака-Лейблера (расхождение KL) между двумя выборками. Для дискретных распределений вероятностей P (x) и Q (x),, определенных в одном и том же вероятностном пространстве 𝛘,, это определяется как:

Для двух функций плотности вероятности p (x) и q (x) предыдущее уравнение принимает следующий вид:

Пусть P (x) и Q (x), x ∈ 𝛘, - две вероятностные массы функции (т.е. дискретные распределения). Тогда D (P || Q) ≥ 0 с равенством тогда и только тогда, когда P (x) = Q (x) для всех x. По большей части D (P || Q) ≠ D (Q || P). Следовательно, дивергенция KL не является метрикой реального расстояния, потому что она не симметрична и не удовлетворяет неравенству треугольника. Важно отметить, что дивергенция КЛ определена только в том случае, если для всех x, Q (x) = 0 → P (x) = 0.

Альтернативный подход - расхождение Дженсена-Шеннона (расхождение JS), еще один метод измерения сходства между двумя распределениями вероятностей. Это симметричная и сглаженная версия расхождения KL, которую можно использовать в качестве показателя расстояния. Определяя величину M = (P + Q) * (0,5), мы можем записать дивергенцию JS как:

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

from scipy.stats import entropy
from scipy.spatial.distance import jensenshannon
from scipy.special import kl_div

Вычисление дивергенции для дискретных переменных

Приведенный ниже сценарий Python иллюстрирует его использование для дискретных данных путем вычисления функции массы вероятности с использованием гистограммы NumPy и последующего вычисления расхождений KL и JS для любых дискретных данных.

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

mu, sigma = reference_data.mean(), reference_data.std()
noise = np.random.normal(0, sigma, size=reference_data.shape)
pure = reference_data.copy()
signal = pure + noise
fig, ax = plt.subplots(1,1,figsize=(12,4))
sns.distplot(noise, ax=ax,
             hist=False,
             kde_kws={'lw': 3,'label':'Noise'})
sns.distplot(pure, ax=ax,
             hist=False, rug=True,
             kde_kws={"lw": 3,'label': 'Original data'})
sns.distplot(signal, ax=ax,
             hist=False,
             kde_kws={"lw": 3, 'label': 'Transformed data'})
ax.set_xlabel('Reference data',fontsize=12,weight='bold')

Мы преобразовали исходные данные, добавив некоторый дополнительный шум (например, преобразовав то же имя столбца в другой набор данных). Давайте посмотрим, как ведут себя дивергенция KL и дивергенция JS при сравнении.

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

Здесь мы можем наблюдать симметричное поведение JS-дивергенции. Его значение одинаково, используем ли мы x_0 или x_1 в качестве справочных данных.

Вычисление дивергенции для непрерывных переменных

Что, если нам нужно вычислить дивергенцию и для непрерывных переменных? Вместо функций вероятности массы и дискретных данных (т. Е. Интервалов) теперь мы должны иметь дело с функциями вероятности плотности и непрерывными данными (как мы видели ранее).

Обычно используется метод аппроксимации наблюдаемого статистического распределения некоторой функцией плотности вероятности (PDF). Хорошо известные распределения включают нормальное, пуассоновское, бета, гамма и т. Д. Предположим, у нас есть два непрерывных распределения p (x) и q (x) с нормальными функциями плотности вероятности, такими как:

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

Функция плотности вероятности нормального распределения определяется выражением

Что приводит к

Следовательно, у нас есть аналитическое выражение для расхождения KL вместо эмпирического. Одним из преимуществ аналитического выражения является то, что мы избавляемся от необходимости «разбивать» переменную на дискретные части (бины) и избегаем проблемы пересечения опор ( то есть, Q (x) = 0 или P (x) = 0).

Этот подход особенно полезен, когда есть сдвиг в преобразованных данных. Если бы вместо умножения исходных справочных данных мы сместили их (например, сумма 100 ко всем его значениям), расхождение все равно увеличилось бы монотонно, как показано ниже.

Пока что большинство показанных здесь демонстраций можно легко реализовать с помощью следующего пакета GitHub, предоставленного Майклом Новотны:

Https://github.com/michaelnowotny/divergence

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

Где Γ - функция гамма. Из определения дивергенции Кульбака-Лейблера следует, что аналитическое выражение для KL-дивергенции между двумя обобщенными функциями гамма-плотности имеет вид:

Где Ψ (x) - функция дигамма.

Ниже мы показываем реализацию Python, которая сравнивает варианты исходных данных путем добавления различных скаляров. Обратите внимание, что мы установили p = 1 в исходном выражении, чтобы уменьшить обобщенную гамму до стандартного гамма-распределения.

По мере смещения данных расхождение также монотонно увеличивается, как и ожидалось. Пакет Python scipy имеет несколько реализаций для различных функций распределения, как показано ниже.

from scipy.stats import gengamma, gamma, beta #distributions
from scipy.special import gamma, digamma #functions

Вычисление дивергенции с использованием кумулятивной функции плотности

В более поздних публикациях показаны подходы к оценке расхождения KL без предварительного решения плотностей (как это обычно делается) . То есть в этом промежуточном шаге нет необходимости, пока оценивается эмпирическая функция накопленной плотности (cdf). Эмпирический cdf определяется как:

Здесь U (x) - это ступенчатая функция Хевисайда или функция единичного шага, где U (0) = 0,5. Эта функция может быть линейно интерполирована, что приводит к непрерывному распределению 𝑃𝑐 (см. Ссылку [3]). Таким образом, окончательное предлагаемое расхождение выглядит следующим образом:

куда

Число 𝜖 (эпсилон) определяется таким образом, чтобы оно было меньше наименьшего расстояния между образцами. Мы реализовали код Python для вычисления эмпирической кумулятивной функции плотности и ее линейной интерполяции, а также окончательной оценки расходимости. Результаты можно увидеть ниже.

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

Выводы

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

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

использованная литература

[1] Т. Дасу, С. Кришнан, С. Венкатасубраманян, К. Йи - Теоретико-информационный подход к обнаружению изменений в многомерных потоках данных - Интерфейс ( 2006 г.).

[2] Нильсен, Франк - О симметризации расстояний Дженсена-Шеннона с помощью абстрактных средств - Энтропия (2019), т. 21, выпуск 5, с. 485.

[3] Фернандо Перес-Крус - Оценка расхождения Кульбака-Лейблера непрерывных распределений - 2007 - Департамент электротехники. Университет Принстона.

[4] Кристиан Бокхейдж - Вычисление расхождения Кульбака-Лейблера между двумя обобщенными гамма-распределениями - 2014 - Боннский университет.

[5] Томас Обложка, Джой Томас - Элементы теории информации - 2-е издание - 2006 г. - Wiley-Interscience