If you liked this...

 Computer, Matematik  Comments Off on If you liked this...
Oct 062013
 

Hvordan finder et website ud af, hvad der interesserer DIG på basis af andres likes eller anbefalinger? Problemet er ikke trivielt. Der er mange måder at gøre det på og mange af dem der anvendes derude, på websites, er forkerte.

Problemet kan anskues på denne måde: Et website sælger widgets og gadgets. Når folk har bestilt noget, vil ejeren gerne foreslå kunden at købe et andet produkt ved siden af, som er anbefalet af tidligere kunder. Kunder har mulighed for at tilkendegive "positiv" eller "negativ" anbefaling af deres køb og der er masser af data til rådighed i salgsdatabasen. Hvilke produkter skal firmaet anbefale til sine kunder?... tænke, tænke.. Ejeren tager et møde med IT-afdelingens statistiker.

1. ide: "Produktet med fleste positive "likes" må være det bedste", foreslår ejeren. "Svaret er desværre FORKERT", siger statistikeren, og her er hvorfor. Antag at widget B har 10000 anmeldelser (både positive og negative) hvoraf 4500 er positive. Widget A derimod har 100 anmeldelser hvoraf 80 er positive. Det vil sige at A får positive anmeldelser i 80% af tilfældene, mens B kun får positive anmeldelser i 45% af tilfældene. På trods af dette vil denne logik anbefale widget B til kunden.

2. ide: Ejeren tænker sig om siger "Så må det være procenten af positive anmeldelser, der giver et korrekt billede.." Svaret er desværre OGSÅ forkert", svarer statistikeren. Antag at Widget C har 99 positive anmeldelser ud af 100, mens D har 2 positive anmeldelser ud af 2. Widget C har klart de bedste anbefalinger men widget D vinder fordi den tilfældigvis endnu ikke har fået en eneste negativ anmeldelse. Firmaets statistiker fortsætter "Denne model er en maximum likelihood estimator (MLE) og den er stærkt afhængig af at der er et tilstrækkeligt antal anmeldelser på alle produkter for at give et sikkert grundlag for beregningen og anbefaling af produkterne."

3. ide: "OK", siger ejeren, "vi lever af de nye produkter så det er vigtigt at vi får dem med så godt som muligt. Kan vi lave noget der korrigerer for at nye produkter kun har meget få anmeldelser?". "Vi kan bruge en Laplace estimator", siger statistikeren, "her tager vi hensyn til både de opsamlede data OG korrigerer resultatet for mulige positive og negative anmeldelser. "OK, lav et eksempel" afbryder ejeren, der har det som om hans hoved er ved at eksplodere med statistik. Statistikeren fortsætter "MLE  udtrykkes ved sandsynligheden p = s / n hvor s er antallet af positive anmeldelser og n er det samlede antal anmeldelser. Laplace estimatoren korrigerer ved til det samlede antal observationer n at tillægge én af hver mulige udfald. Da der i dette tilfælde kun er to muligheder - en positiv eller en negativ anmeldelse - bliver Laplace estimatoren p´ = (s+1)/(n+2)". Statistikeren laver en tabel.

Widget A B C D
Likes (s) 80 4500 99 2
Total (n) 100 10000 100 2
p =s/n [MLE] 80/100=80% 4500/10000=45% 99/100=99% 2/2=100%
p´=(s+1)/(n+2) [Laplace] 81/102=79,4% 4501/10002=45% 100/102=98% 3/4=75%

"Laplace estimatoren rangordner bedst, men et konfidensinterval ville være bedre", siger statistikeren. "Widget A og D har 79% henholdsvis 75% score, men vi kan faktisk beregne et tal der angiver 95% sandsynlighed for, hvad produktets score er. Jeg tror du skal tage en kop kaffe mens jeg skriver Wilsons formel op."

{{1}\over{1+{{1}\over{n}}z^{2}_{\alpha/2}}}*[\hat{p}+ {z^{2}_{\alpha/2}\over{2n}} \pm z_{\alpha/2}*\sqrt{([\hat p(1-\hat p)+z^{2}_{\alpha/2}/4n]/n)} ]

"Denne formel", fortsætte statistikeren, "angiver et konfidensinterval for scoren for hvert enkelt produkt og kan beregnes. \hat{p} er andelen af positive anmeldelser, z_{\alpha/2} er (1-\alpha/2) kvartilen af en standard normalfordeling, og n er det totale antal observationer." Statistikeren fortsætter tabellen. "Et estimat på scoren er således ganske forskellig, især for widget D, der har så få anmeldelser indtil nu".

Widget A B C D
p´=(s+1)/(n+2) [Laplace] 81/102=79,4% 4501/10002=45% 100/102=98% 3/4=75%
95% konfidensinterval nedre værdi 71% 44% 95% 34%

Tal og bogstaver danser foran ejerens øjne. "OK, implementér det, med mindre det koster en bondegård i ekstra computere og databaser", sluttede han. "Will do", svarer statistikeren, "jeg ændrer koden sammen med vores SQL-ekspert."

Efterskrift
Disse beregninger kan nemt implementeres i et database udtræk og præsenteres i den korrekte rangorden efter mest sandsynlige positive anbefaling. Dette rejser dog et nyt problem, nemlig om nye kunder (som gennemsnit betragtet) har de samme præferencer som de kunder som hahandlet før. Eller sagt på en anden måde : Vil f.eks. en kunde fra Odense have de samme præferencer som en kunde fra København? Er der forskel mellem mand og kvinde? og så videre og så videre. Dette nærmer sig BIG DATA analyse og jeg håber jeg kan få tid til at angribe dette ved en anden lejlighed.

*** Noter ***

Ranking af definitioner på ordet "lily" på urbandictionary.com - 6/10/2013

rank Pos neg pos-neg p interval Wilson rank
1 3196 426 2770 88 % 90-87 % 2
2 3071 1257 1814 71 % 74-68 % 3
3 1752 853 899 67 % 72-63 % 5
4 1322 515 807 72 % 78-65 % 4
5 819 42 777 95 % 98-87 % 1
6 1230 577 653 68 % 76-59 % 7
7 1049 446 603 70 % 80-59 % 6

Det ses tydeligt at urbandictionary.com benytter model 1 (pos-neg). Bemærk 5.position der har positive tilkendegivelser i 95% af tilfældene og har det højeste interval, men altså ligger langt nede på listen...

Referencer:

1. This post was inspired by information from evanmiller.org. I am also indebted to Mr. Millers kind email correspondence on details in his blog.

2. Binominal proportion confidence interval(Wikipedia). Wilsons formel og andet vedr. estimering på binominale fordelinger.

Opdateringer

08 oktober 2013. opdaterede sidste tabel med konfidensintervaller.

Two Pi or not two Pi...

 Matematik  Comments Off on Two Pi or not two Pi...
Mar 212013
 

I tirsdag for en uge siden (14. marts eller 3/14 i engelsktalende lande) var det π (pi) dag. π er forholdet mellem en cirkels diameter og dens omkreds og har en værdi ca. lig med 3,14... og deraf fejringen på denne dag! Du vil sikkert huske tallet fra skolens matematiktimer og mange steder dukker det mærkelige tal π op. F.eks i udregningen af en cirkels areal = π*R2, hvor R er cirklens radius. Omkredsen af en cirkel er 2*π*R, osv.

Grækeren Arkimedes fandt den tilnærmelsesvise værdi 22/7 (3,14285...) allerede i oldtiden. Det gjorde dem store hovedbrud at de ikke kunne finde en eksakt værdi for π, fordi deres matematik var baseret udelukkende på heltal (..., -2,-1,0,1,2,... osv.). π kan ikke skrives som en brøk af to heltal selvom der er mange "smukke" tilnærmelsesvise værdier - fx 355/113 . Bemærk symmetrien i tæller og nævner, der giver et tal 3,1415929... der er præcis ud til 6. decimal efter kommaet. At π ikke kan skrives som en brøk af to heltal betyder det er et irrationelt tal og er dermed i familie med en række andre kendte tal:

Bemærkelsesværdige irrationelle tal:

  • π = 3.14159265...
  • Eulers tal e = 2,71828...
  • Det gyldne snit φ = 1,61803...
  • √2 = 1,41421...

Nu vil mange sikkert synes at π er et cool tal, men der er faktisk et, der er mere cool, nemlig τ (tau) som er 6,28318530...! Tau er forholdet mellem en cirkels radius og dens omkreds. "Og hvad så?" vil du sikkert tænke. "Radius er jo det halve af diameteren, så derfor er  τ jo bare 2*π?". Det er korrekt observeret, men kig på formlerne angivet ovenfor. Falder det dig ind at man har defineret π ud fra cirklens diameter D, men i udregninger anvender vi radius R i stedet for ?? Jeg foreslår du tager et kig på denne fornøjelige og forståelige video der giver en forklaring.

Det der fik mig overbevist om det über coole ved τ er at arealet af en cirkel er A = 1/2 * τ * R2 frem for A = π * R2. Det er fordi der derved ses en sammenhæng med andre kvadratiske formler der går igen overalt i fysik og matematik.

Bemærkelsesværdige kvadratiske formler:

  • En cirkels areal A = 1/2 * τ * R2
  • Den potentielle energi i en udstrukket fjeder E = 1/2 * k * X2
  • Den kinetiske energi af et legeme i bevægelse E=1/2*m*V2.

Jeg ser i hvert fald frem til at fejre tau dag i år, 28. juni (6/28) 😉