Python: Быстрая/эффективная реализация расхождения Kullback Leibler для вычисления множественных распределений

Вопрос:

У меня есть следующая проблема: у меня есть матрица, скажем, 20K дискретных распределений (гистограммы), и мне нужно вычислить KL-дивергенцию (KLD) между каждой из этих пар. Тривиальный способ сделать это – использовать два для циклов и вычислять KLD между каждыми двумя распределениями через стандартный расчет KLD. Это займет время. Много времени. Интересно, существует ли какой-то расчет на основе матрицы/массива выше. Конечно, я не первый, кто сталкивается с этой проблемой. К сожалению, я новичок в python. Любая помощь будет оценена. Благодарю! A.

Ответ №1

Я нашел вычисление расстояния Kullback-Leibler (KL) между текстовыми документами с использованием numpy, который отмечает, что SciPy имеет реализацию KLD as

scipy.stats.entropy(pk, qk=None, base=None)

и документацию можно найти по адресу http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.stats.entropy.html; это должно сделать расчет быстрее.

Альтернативно, реализация в numpy:

import numpy as np

def kl(p, q):
"""Kullback-Leibler divergence D(P || Q) for discrete distributions

Parameters
----------
p, q : array-like, dtype=float, shape=n
Discrete probability distributions.
"""
p = np.asarray(p, dtype=np.float)
q = np.asarray(q, dtype=np.float)

return np.sum(np.where(p != 0, p * np.log(p / q), 0))

Обратите внимание, что преобразование данных в и из массивов numpy относительно медленное; Я не знаю, было бы лучше сохранить список из 20k 1D numpy-массивов (может быть очень интенсивным в памяти) или сохранить один 2D-массив numpy и работать с срезами.

Ответ №2

itertools – мощный инструмент для всех видов перестановок и т.д. между разными объектами. Помимо прочего, он выполняет двойные циклы “for” через функцию продукта:

from itertools import product
KL = [kl(hist_mat[:,i],hist_mat[:,j]) for i,j in product( range(0,K), range(0,K) )]

K – число гистограмм для сравнения в попарно,
hist_mat, содержащий гистограммы в каждой из этих столбцов.
kl = ваша реализация выбора для дивергенции kullback leibler

Единственный минус – это то, что для больших наборов данных он работает медленно.

Приветствия, А.

Ответ №3

Это должно сработать.

def kullback_leibler_divergence(X):

"""
Finds the pairwise Kullback-Leibler divergence
matrix between all rows in X.

Parameters
----------
X : array_like, shape (n_samples, n_features)
Array of probability data. Each row must sum to 1.

Returns
-------
D : ndarray, shape (n_samples, n_samples)
The Kullback-Leibler divergence matrix. A pairwise matrix D such that D_{i, j}
is the divergence between the ith and jth vectors of the given matrix X.

Notes
-----
Based on code from Gordon J. Berman et al.
(https://github.com/gordonberman/MotionMapper)

References:
-----------
Berman, G. J., Choi, D. M., Bialek, W., & Shaevitz, J. W. (2014).
Mapping the stereotyped behaviour of freely moving fruit flies.
Journal of The Royal Society Interface, 11(99), 20140672.
"""

X_log = np.log(X)
X_log[np.isinf(X_log) | np.isnan(X_log)] = 0

entropies = -np.sum(X * X_log, axis=1)

D = np.matmul(-X, X_log.T)
D = D - entropies
D = D / np.log(2)
D *= (1 - np.eye(D.shape[0]))

return D

Оцените статью
TechArks.Ru
Добавить комментарий