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?