Sull'uso dei delta negli estimatori di entropia di Linux

10

Recentemente, mi sono interessato alla crittografia applicata e sono incappato in un link che spiega come le stime di Linux entropia .

Ad un certo punto, ci viene detto che la stima dell'entropia è basata sulla prima, seconda e terza differenza dei timestamp di determinati eventi di sistema. Giusto. Quello che non ho capito è stata l'intuizione dietro a questo, spiegato nel link come segue:

This use of deltas is approximately the same as attempting to fit an n degree polynomial to the previous n+1 points, then looking to see how far the new point is from the best prediction based on the previous n points. The minimum of the deltas is used, which has the effect of taking the best fit of a 0th, 1st or 2nd degree polynomial, and using that one.

Per chiarire, ecco cosa (penso) ho capito. Prendendo l'esempio degli eventi del mouse nel link:

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

Adatta un polinomio di grado n ai precedenti punti n + 1: immagino che prenderebbe il (i + 1) -th diff, che sono le prime diff di i-es. diff . Questi potrebbero essere usati per prevedere i prossimi valori dell'i-es diff, da qui il 'fitting'. Per esempio. il primo diff spiega come cambiano i valori consecutivi della linea di eventi del mouse (differenza 0).

Quanto è lontano il nuovo punto dalla migliore previsione basata sui precedenti n punti: Suppongo che questo sia dato da (i + 2) -th diff? Per esempio. dopo l'ultimo evento del mouse, 1041, il secondo diff è 6, che è quanto lontano 1041 ( il nuovo punto ) è da 1035 ( la migliore previsione ). La predizione si ottiene prendendo il precedente valore di 0th diff, 1030, aggiunto al precedente valore di diff 1, 5.

Uso del delta minimo: La mia ipotesi migliore è che lo stimatore di entropia scelga il valore minimo, poiché è la soluzione migliore per (i-1) -th diff (o (i-1) polinomiale di terzo grado). Penso di capire in che modo questo metodo si adatta al meglio, ma in realtà non ho ottenuto il "perché".

I miei dubbi / domande sono:

  • Potrei trascurare qualcosa di ovvio, ma non vedo ancora la relazione tra la mia idea di adattamento polinomiale di grado n (ad esempio regressione polinomiale usando un metodo dei minimi quadrati).
  • Qual è la vera motivazione alla base della scelta del delta minimo? Perché fornisce una buona misura di quanto sia inaspettato il prossimo punto dati? È perché il delta minimo è il più conservatore?
posta fortune_pickle 17.03.2017 - 13:57
fonte

1 risposta

2

Lo stimatore usa il delta terzo minimo perché il grado del polinomio adattato è l'entropia del set di dati. Nel primo esempio, il delta minimo era 2, il log di base 2 è 1, quindi i dati complessivi hanno aggiunto 1 bit di entropia. Perché il delta minimo? È perché l'utilizzo consente di rappresentare l'entropia (in altre parole, l'imprevedibilità) dell'intero set di dati come un numero di una cifra. Se osservate le misure di entropia nei primi due esempi (1 e 2 bit), potete vedere che si traducono in 1 ° delta di circa 10 e 100, rispettivamente. Di conseguenza, l'entropia di 3 significherebbe 1 delta di circa 1.000, 4 - 10.000 e così via. In breve, nella nostra rappresentazione delta siamo passati da cifre multiple a singole usando il grado polinomiale del terzo delta minimo.

    
risposta data 17.03.2017 - 15:54
fonte

Leggi altre domande sui tag