Sobre el uso de deltas en los estimadores de entropía de Linux

10

Recientemente, me interesé en la criptografía aplicada y me topé con un enlace que explica cómo Linux estima entropía .

En algún momento, se nos dice que la estimación de la entropía se basa en la primera, segunda y tercera diferencia de las marcas de tiempo de ciertos eventos del sistema. Lo suficientemente justo. Lo que no entendí fue la intuición detrás de esto, que se explica en el siguiente enlace:

  

Este uso de deltas es aproximadamente el mismo que intentar ajustar una n   grado polinomial a los n + 1 puntos anteriores, luego mirar para ver qué tan lejos   el nuevo punto es de la mejor predicción basada en los n puntos anteriores.   Se utiliza el mínimo de los deltas, que tiene el efecto de adoptar el mejor ajuste de un polinomio de 0º, 1º o 2º grado, y usar ese.

Para aclarar, esto es lo que (creo) he entendido. Tomando el ejemplo de eventos del mouse en el enlace:

Mouse event times       1004   1012    1024    1025    1030    1041

1st differences              8      12       1       5      11

2nd differences                  4       11      4       6

3rd differences                      7       7       2

Ajusta un polinomio de n grados a los n + 1 puntos anteriores: supongo que eso sería tomar el (i + 1) -th diff, que son los primeros diffs de los i-th diffs . Estos podrían usarse para predecir los siguientes valores de i-th diff, por lo tanto, el "ajuste". P.ej. El primer diff explica cómo cambian los valores consecutivos de la línea de evento del mouse (0th diff).

¿Qué tan lejos está el nuevo punto de la mejor predicción basada en los n puntos anteriores: supongo que esto viene dado por la diferencia (i + 2) -th? P.ej. después del último evento de mouse, 1041, la segunda diferencia es 6, que es a qué distancia 1041 ( el nuevo punto ) es de 1035 ( la mejor predicción ). La predicción se obtiene al tomar el valor de diferencia 0th anterior, 1030, agregado al valor de primera diferencia anterior, 5.

Uso del delta mínimo: Mi mejor estimación es que el estimador de entropía elige el valor mínimo, porque es el mejor ajuste para la diferencia (i-1) -th (o (i-1) Polinomio de grado. Creo que entiendo cómo este método elige el mejor ajuste, pero realmente no entendí el 'por qué'.

Mis dudas / preguntas son:

  • Puede que esté pasando por alto algo obvio, pero aún no veo la relación entre mi idea de ajuste polinomial de n grados (por ejemplo, regresión polinomial utilizando un método de mínimos cuadrados).
  • ¿Cuál es la razón real detrás de elegir el delta mínimo? ¿Por qué proporciona una buena medida de cuán inesperado es el siguiente punto de datos? ¿Es porque el delta mínimo es el más conservador?
pregunta fortune_pickle 17.03.2017 - 13:57
fuente

1 respuesta

2

El estimador usa un tercer delta mínimo porque el grado del polinomio ajustado es la entropía del conjunto de datos. En el primer ejemplo, el delta mínimo fue 2, su registro de base 2 es 1, por lo que los datos en general agregaron 1 bit de entropía. ¿Por qué el delta mínimo? Es porque su uso permite representar la entropía (en otras palabras, imprevisibilidad) de todo el conjunto de datos como un número de un dígito. Si observa las medidas de entropía en los primeros dos ejemplos (1 y 2 bits), puede ver que se traducen a valores del 1er delta de aproximadamente 10 y 100, respectivamente. En consecuencia, la entropía de 3 significaría los primeros deltas de aproximadamente 1,000, 4 - 10,000, y así sucesivamente. En resumen, en nuestra representación delta pasamos de varios dígitos a uno solo mediante el uso del grado polinomial del tercer delta mínimo.

    
respondido por el postoronnim 17.03.2017 - 15:54
fuente

Lea otras preguntas en las etiquetas