Estoy tratando de verificar rápidamente cuántos elementos en una lista están por debajo de una serie de umbrales, similar a hacer lo que se describe aquí pero muchas veces. El objetivo de esto es hacer algunos diagnósticos en un modelo de aprendizaje automático que son un poco más profundos que lo que está integrado en el aprendizaje de sci-kit (curvas ROC, etc.).

Imagine preds es una lista de predicciones (probabilidades entre 0 y 1). En realidad, tendré más de 1 millón de ellos, por eso estoy tratando de acelerar esto.

Esto crea algunos puntajes falsos, normalmente distribuidos entre 0 y 1.

fake_preds = [np.random.normal(0, 1) for i in range(1000)]
fake_preds = [(pred + np.abs(min(fake_preds)))/max(fake_preds + np.abs(min(fake_preds))) for pred in fake_preds]

Ahora, la forma en que hago esto es recorrer 100 niveles de umbral y verificar cuántas predicciones son más bajas en cualquier umbral dado:

thresholds = [round(n,2) for n in np.arange(0.01, 1.0, 0.01)]
thresh_cov = [sum(fake_preds < thresh) for thresh in thresholds]

Esto toma alrededor de 1.5 segundos por 10k (menos tiempo que generar las predicciones falsas), pero puede imaginar que lleva mucho más tiempo con muchas más predicciones. Y tengo que hacer esto miles de veces para comparar un montón de modelos diferentes.

¿Alguna idea sobre una manera de hacer que ese segundo bloque de código sea más rápido? Estoy pensando que debe haber una manera de ordenar las predicciones para que sea más fácil para la computadora verificar los umbrales (similar a la indexación en un escenario similar a SQL), pero no puedo encontrar otra forma que no sea sum(fake_preds < thresh) para verificarlos, y eso no aprovecha ninguna indexación u orden.

Gracias de antemano por la ayuda!

3
seth127 30 oct. 2017 a las 22:47

4 respuestas

La mejor respuesta

Método # 1

Puede ordenar la matriz predictions y luego usar searchsorted o np.digitize, así -

np.searchsorted(np.sort(fake_preds), thresholds, 'right')

np.digitize(thresholds, np.sort(fake_preds))

Si no le importa mutar la matriz predictions, ordene in situ con: fake_preds.sort() y luego use fake_preds en lugar de np.sort(fake_preds). Esto debería ser mucho más eficaz ya que estaríamos evitando el uso de memoria adicional allí.

Método # 2

Ahora, con los umbrales siendo 100 de 0 a 1, esos umbrales serían múltiplos de 0.01. Por lo tanto, podemos simplemente digitalizar con una ampliación de 100 para cada uno de ellos y convertirlos a ints, lo que podría alimentarse directamente como bins a np.bincount . Luego, para obtener el resultado deseado, use cumsum, así:

np.bincount((fake_preds*100).astype(int),minlength=99)[:99].cumsum()

Benchmarking

Enfoques -

def searchsorted_app(fake_preds, thresholds):
    return np.searchsorted(np.sort(fake_preds), thresholds, 'right')

def digitize_app(fake_preds, thresholds):
    return np.digitize(thresholds, np.sort(fake_preds) )

def bincount_app(fake_preds, thresholds):
    return np.bincount((fake_preds*100).astype(int),minlength=99)[:99].cumsum()

Prueba de tiempo de ejecución y verificación en elementos 10000 -

In [210]: np.random.seed(0)
     ...: fake_preds = np.random.rand(10000)
     ...: thresholds = [round(n,2) for n in np.arange(0.01, 1.0, 0.01)]
     ...: thresh_cov = [sum(fake_preds < thresh) for thresh in thresholds]
     ...: 

In [211]: print np.allclose(thresh_cov, searchsorted_app(fake_preds, thresholds))
     ...: print np.allclose(thresh_cov, digitize_app(fake_preds, thresholds))
     ...: print np.allclose(thresh_cov, bincount_app(fake_preds, thresholds))
     ...: 
True
True
True

In [214]: %timeit [sum(fake_preds < thresh) for thresh in thresholds]
1 loop, best of 3: 1.43 s per loop

In [215]: %timeit searchsorted_app(fake_preds, thresholds)
     ...: %timeit digitize_app(fake_preds, thresholds)
     ...: %timeit bincount_app(fake_preds, thresholds)
     ...: 
1000 loops, best of 3: 528 µs per loop
1000 loops, best of 3: 535 µs per loop
10000 loops, best of 3: 24.9 µs per loop

¡Es una aceleración 2,700x+ para searchsorted y 57,000x+ para bincount uno! Con conjuntos de datos más grandes, la brecha entre bincount y searchsorted está destinada a aumentar, ya que bincount no necesita clasificarse.

2
Divakar 30 oct. 2017 a las 21:45

Puede remodelar thresholds aquí para habilitar la transmisión. Primero, aquí hay algunos cambios posibles en su creación de fake_preds y thresholds que eliminan los bucles.

np.random.seed(123)
fake_preds = np.random.normal(size=1000)
fake_preds = (fake_preds + np.abs(fake_preds.min())) \
           / (np.max(fake_preds + np.abs((fake_preds.min()))))
thresholds = np.linspace(.01, 1, 100)

Entonces lo que quieres hacer es realizable en 1 línea:

print(np.sum(np.less(fake_preds, np.tile(thresholds, (1000,1)).T), axis=1))
[  2   2   2   2   2   2   5   5   6   7   7  11  11  11  15  18  21  26
  28  34  40  48  54  63  71  77  90 100 114 129 143 165 176 191 206 222
 240 268 288 312 329 361 392 417 444 479 503 532 560 598 615 648 671 696
 710 726 747 768 787 800 818 840 860 877 891 902 912 919 928 942 947 960
 965 970 978 981 986 987 988 991 993 994 995 995 995 997 997 997 998 998
 999 999 999 999 999 999 999 999 999 999]

Tutorial:

fake_preds tiene forma (1000,1). Necesita manipular thresholds en una forma que sea compatible para transmitir con esto. (Consulte reglas generales de transmisión.)

Una segunda forma broadcastable sería

print(np.tile(thresholds, (1000,1)).T.shape)
# (100, 1000)
1
Brad Solomon 30 oct. 2017 a las 20:37

Una forma sería usar {{X0} }.

thresh_cov = np.histogram(fake_preds, len(thresholds))[0].cumsum()

Desde timeit, obtengo:

%timeit my_cov = np.histogram(fake_preds, len(thresholds))[0].cumsum()
169 µs ± 6.51 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit thresh_cov = [sum(fake_preds < thresh) for thresh in thresholds]
172 ms ± 1.22 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
2
roganjosh 30 oct. 2017 a las 20:13

Opción 1:

from scipy.stats import percentileofscore 
thresh_cov = [percentileofscore (fake_preds, thresh) for thresh in thresholds]

Opción 2: igual que la anterior, pero primero ordena la lista

Opción 3: inserte sus umbrales en la lista, ordene la lista, encuentre los índices de sus umbrales. Tenga en cuenta que si tiene un algoritmo de clasificación rápida, puede optimizarlo para sus propósitos haciendo que sus umbrales sean los pivotes y terminando la clasificación una vez que haya dividido todo de acuerdo con los umbrales.

Opción 4: Basándose en lo anterior: coloque sus umbrales en un árbol binario, luego, para cada elemento de la lista, compárelo con los umbrales en una búsqueda binaria. Puede hacerlo elemento por elemento o dividir la lista en subconjuntos en cada paso.

0
Acccumulation 30 oct. 2017 a las 20:17