Distribuzione normale, per migliorare le query..problema

[Arcer]

Salve a tutti,
sono uno studente di informatica e sto sviluppando un applicativo in c# che implementa un algoritmo per migliorare in termini prestazionali l'esecuzione delle query in un database. Il ragionamento base è quello di scomporre il search range* della query in tanti intervalli, eseguire tante piccole query parallelamente e ricomporre i risultati accettandoli sotto una certa stima dell'errore...

Il punto a me critico è nella costruzione dell'errore, infatti nell'articolo viene riportato questo:

Supponendo che X' sia il risultato esatto (della query). Basandosi su "central limit theory", X'-X segue la distribuzione normale, se X (risultato calcolato con l'algoritmo) è generato da un numero elevato di campioni. Quindi abbiamo:

$P(X'-X < e)= 2phi(e sqrt(N')/(X'))-1$


dove N è il numero totale dei campioni utilizzati per la query, $P(X'-X < e)$ è la confidenza che il margine d'errore sia e.



Considerando che ho vecchissimi ricordi di statistica, ma conosco la distribuzione normale (anche se sommariamente) non riesco a capire come calcolare l'errore. Potete darmi una mano????la phi come la calcolo???


grazie a tutti...

ps:
i dati che possiedo sono : il numero di campioni, il risultato esatto, il risultato calcolato, e =0.01 e confidenza c=95%....




* in una query il search range si trova nella clausola WHERE ad esempio Where Eta>20 and Età<40 il search range è l'intervallo ]20,40[

[Rggb1]

Non ho capito... hai difficoltà a calcolare cosa? Quella è la distribuzione normale, se non hai a disposizione librerie apposite puoi risolverla "direttamente", tenendo anche conto che errore e soglia sono dati (fissi, presumo). Insomma, dove sta il problema?

[Arcer]

il problema sta proprio nel calcolare quella $phi$....

$P(X'-X< e)$

non è la probabilità che l'errore (inteso come differenza tra il valore calcolato e quello esatto) sia minore ad un e (fissato in questo caso 0.01) sotto un intervallo di confidenza pari ad una soglia c (in questo caso 95%)?

assodato questo il test per far finire il mio algoritmo è proprio su questa proposizione detta prima ovvero il calcolo di $2phi-1$ dovrebbe ritornare un valore superiore o uguale a 0.95 suppongo....ma come calcolo la $phi$ ???

[Rggb1]

"Arcer":$P(X'-X< e)$

non è la probabilità che l'errore (inteso come differenza tra il valore calcolato e quello esatto) sia minore ad un e (fissato in questo caso 0.01) sotto un intervallo di confidenza pari ad una soglia c (in questo caso 95%)?

Direi proprio di si.

"Arcer":ma come calcolo la $phi$ ???

Credo questa definizione ti possa andare benissimo:
http://en.wikipedia.org/wiki/Normal_dis ... Definition

Ma è una cosa che devi fare per un esame? E il tuo docente non ti aveva dato nessuna spiegazione?

[Arcer]

grazie mille!!!!!!! ora provo subito vediamo se l'algoritmo adesso ha un test d'arresto ....

ps :
si è per un esame e purtroppo no il mio docente non mi ha dato nessuna spiegazione...

[Arcer]

ho provato quanto scritto prima....

il problema è che osservando la formula per avere un risultato del tipo 0.95 (95% di confidenza), il risultato della $phi$ deve essere più o meno 1.95 cosi moltiplicandola per 2 e sottraendogli 1 si ottiene c=0.95....


il problema è che utilizzando come argomento della formula phi i dati ottenuti e applicando la formula presa da wikipedia $1/(sqrt(2pi))e^(-1/2*x^2)$ utilizzando come argomento $esqrt(N')/X'$

vengono valori negativi.....del tipo -0.20

l'esponenziale negativo per le x<0 porta valori y>1


considerando empiricamente questi valori
X'=53 (valore della query...ad esempi una media sulle età)
N'= 3000 (numero totale di campioni esaminati)
e=0.01 (valore d'errore che si vuole calcolare con c=95%)

dobbiamo calcolare questo $phi(0.01*sqrt(3000)/53=0.01033)$
quindi
$1/(sqrt(2pi))e^(-1/2*0.01033^2)=2.7182/sqrt(2*pi)=1.0847$ circa

quindi l'intervallo di confidenza espresso come scritto prima ovvero $2*phi(x)-1 = 2*1.0847-1=1,16$

però se in X' invece di avere la media di un età avevamo per esempio la somma dei capitali sociali di un azienda (grandi numeri ) per esempio X'=3454233 e mantenendo uguali gli altri parametri l'argomento della $phi$ diventa 0.0000001585 che poi andando a sostituire nella definizione della $phi$ si ottiene 0.39894228 aumentando i campioni resta sempre lo stesso valore (si muove di pochissimo...questione di millessimi e anche meno) provato proprio su excell....applicando 2*$phi$-1 viene -0,20...


dove sbaglio? cosa non ho capito? X' può avere qualsiasi valore....

[Rggb1]

Effettivamente nemmeno io riesco a capire come è stata ricavata la formula indicata.

Ora provo a risolvere, e spero qualcun'altro ci possa chiarire il dubbio.

[Arcer]

ti devo una birra Rggb !!!!!

onestamente anche io non riesco a capire come funzionano queste formule...forse ti potrebbe essere d'aiuto avere il testo originale dell'articolo!!! te lo allego...sto uscendo pazzo assieme al mio collega con cui devo fare l'esame:


http://www.entropiacommunity.it/SIGMOD2010.pdf


non posso far altro che ringraziarti e incrociare le dita...


ps: la lettura è abbastanza interessante se ti piace l'informatica sono argomenti di ricerca nuovissimi e trattano informatica avanzata

[cenzo1]

Premetto che ho solo dato una rapida lettura.

Secondo me il problema è che la [tex]\phi[/tex] non è la funzione densità normale (che hai invece utilizzato), bensì la funzione di ripartizione normale, per il cui calcolo -come è noto- non esiste un'espressione in forma chiusa (ma di sicuro ci saranno librerie che implementano metodi numerici, come suggeriva Rggb).

[Arcer]

"cenzo":Premetto che ho solo dato una rapida lettura.

Secondo me il problema è che la [tex]\phi[/tex] non è la funzione densità normale (che hai invece utilizzato), bensì la funzione di ripartizione normale, per il cui calcolo -come è noto- non esiste un'espressione in forma chiusa (ma di sicuro ci saranno librerie che implementano metodi numerici, come suggeriva Rggb).

molto interessante....diciamo che nell'articolo vengono usate formule abbastanza strane quindi non mi stupirei, non è molto chiaro a spiegare le cose....


per esempio per una sommatoria "incrementale" (nel senso appena arriva un campione viene sommato alla somma precedente) l'articolo usa questa formula:

$sum(ci)=(Vs*N+ H(gi)*vi)/(N+1)$

Dove Vsum è la sommatoria all i-1esimo passo
N è il numero di campioni letti fin ora (i campioni vengono inviati a pagine, ogni volta che arriva una pagina per sommare i campioni si parte da 0 fino a N)
Hgi sarebbe un count totale di tutti i campioni accettati
vi il valore che si sta analizzando...

è molto particolare come somma, ma funziona

come varianza invece si calcola la varianza con la formula computazione

$var(x) = E(X^2) - (E(X))^2$

e quindi
si calcola prima una variabile Eg del tipo:
$E^2s = E^2s+(vi)^2*H(gi)^2$
e poi la varianza
$var(sum(ci))=(E^2s)/N-V^2s$



un casino ....poi per l'errore fa quelle formule strane che abbiamo visto prima...


usando la ripartizione normale come dovrei fare?

[Rggb1]

Mi sa che ha ragione cenzo... è un banale problema di notazione, dando una lettura al testo mi torna sia la funzione di distribuzione (indicata normalmente con $Phi$) e non la funzione di densità (usualmente $phi$).

PS. Effettivamente, problema interessante.

[Rggb1]

"Arcer":usando la ripartizione normale come dovrei fare?

Se non ti interessa capire a fondo qual è l'analisi dell'errore spiegata in quella nota, ti consiglio di partire da qui
http://en.wikipedia.org/wiki/Normal_dis ... n_function

e cercare una implementazione della funzione degli errori erf per C#, googlando un po', io ne ho trovate cercando "C# erf".

[Arcer]

Forse ci sono o comunque sono molto vicino allora ragionando se quella phi rappresenta la funzione di ripartizione moltiplicandol per 2 e sottraendo 1 si ottiene l' area sotto la gaussiana da -x a +x quindi 0.95 se ad esempio come valore gli passo 1.96 e se come funzione ho la gaussiana stndardizzata ( media 0 e varianza 1).....e e non mi sbaglio fino a qui dovrei esserci....



Ora nel mio caso, i valori che ottengo da $0.01*sqrt(N')/(X')$ non so come evolvono...non dovrebbero essere "normalizzati"? ( uso questo termine impropriamente) perche l'area sotto la distribuzione dei dati che vengono fuori da questa formula non e' detto che sia pari a 1 ... So soltanto che sono descritti da una distribuzne normale...

[cenzo1]

Probabilmente mi sbaglio, ma qualcosa non mi torna in questa formula:
[tex]$P(\bar{X}-X<\epsilon)\simeq2\phi(\frac{\epsilon \sqrt{\bar{N}}}{\bar{X}})-1$[/tex]

Mi sarei invece aspettato una cosa del genere:
[tex]$P(|\bar{X}-X|<\epsilon)\simeq2\phi(\frac{\epsilon \sqrt{\bar{N}}}{\sigma})-1$[/tex]

e cioè il valore assoluto nel valutare lo scarto (che rende conto dell'intervallo di confidenza simmetrico) e la deviazione standard $\sigma$ al denominatore, come normalmente si procede in caso di standardizzazione.

[size=75]edit: corretto errore gentilmente segnalato da Rggb[/size]

[Rggb1]

@cenzo

Premesso che sono parecchio indietro rispetto a te in statistica, due sole considerazioni:
- uno: lo scarto standard, senza disporre del dato, quanto sarebbe..?
- due: manca un due (è solo un refuso)

Per il valore assoluto hai sicuramente ragione. Forse gli è "scappato"

[cenzo1]

Grazie per la segnalazione del refuso, ho corretto.

Al denominatore mi aspettavo l'errore standard di $X$, quindi $\sigma/sqrt(barN)$.
Ora, $sqrt(barN)$ passa al numeratore e ci siamo, ma non capisco l'origine di quel $\barX$ al denominatore.

"Rggb":lo scarto standard, senza disporre del dato, quanto sarebbe..?

Non sono sicuro, ma potrebbe essere la $\sigma$ che indica alla formula (14) dell'articolo linkato da Arcer.

La frase

The variance is used to generate the statistics error bound and confidence for the approximate result

mi lascia intendere che voglia usare quella $\sigma$ proprio per calcolarsi $P(|\barX-X|<\epsilon)$.

Naturalmente con le dovute riserve

[Arcer]

E quindi la formula corretta e quella con la deviazione standard?

[Arcer]

Ecco una mail inviata a loro:

Hi,
We are two student at University Of Messina (Italy) in Computer Science. We are studying and trying to implement your "Continuous Sampling for Online Aggregation Over Multiple Queries" (COSMOS). We have some problem in confidence and error bound calculation.

In the paper there are at page 658 the formula for calculating P(X-X'
Moreover at the page 659 yours "stop test" is calculated as P( |V'-V| / V ) < e = c (probably the last ")" is not in the right position ), but we can't understand how to calculate it. Is it the same of formula [15]? we must calculate "trust intervals"? how?

Excuse me for my bad english
Thanks for any response .

ed ecco la risposta

Hi, Carlo.

Phi denotes the normal distribution. The formula says that the probability (confidence) of error bound less than e follows a normal distribution. In the formula, there are two parameters, probability and error bound. Normally, we fix one and calculate the other. In online aggregation, we iteratively compute the parameters to get a higher confidence and lower error bound.

In 659, the calculation is similar to 658. Here, we fix the value of e or c and calculate the other.

regards

Wu Sai

suppongo che usino la cdf come dicevate voi...

[Rggb1]

Secondo me va bene, la loro formula è standardizzata. Fra l'altro l'approssimazione che usano è giustificata anche da altre considerazioni del testo, tipo che usano sempre un grande numero di risultati per calcolare l'errore con una approssimazione accettabile. Usa pure la formula del testo, e per i calcoli - come ti ho accennato - usa la erf() per implementazioni C#, ricordando che
$F(Z)=P(Z dove $F(Z)$ è la f. di distribuzione della standardizzata.