En mild introduktion till slumpmässiga skogar, ensembler och prestandamått i ett kommersiellt System

detta är det första i en serie inlägg som illustrerar vad vårt datateam håller på med, experimenterar med och bygger ”under huven” hos CitizenNet.

dr.Arshavir Blackwell är Citizennets resident Data Scientist. Han har varit involverad i webbaserad maskininlärning och informationssökning i över 10 år.

hett tips: klicka på bilderna för en större vy.,

en av de första inläggen vi publicerade talade på en hög nivå av det tekniska problemet CitizenNet försöker lösa. I huvudsak försöker vi förutsäga vilka kombinationer av demografiska och intressemål som kommer att vara intresserade av något innehåll.

på CitizenNet-plattformen skulle en användare skapa ett projekt som skulle definiera (i stort sett) målgruppen, bitarna av Facebook-innehåll som de vill marknadsföra och annan kampanj och finansiell information.

bakom kulisserna bygger ett robust prediktionssystem målen för projektet., Denna förutsägelse systemet utbildas på tidigare beteende, som den sedan använder för att förutsäga hur en framtida (okänd) projekt kan vara bäst riktade. En av komponenterna i prediktionssystemet är en klassificerare, som för närvarande är ett ensemble av både neurala nätverk och slumpmässiga skogsklassificerare. Detta blogginlägg syftar till att illustrera grunderna i dessa metoder.

neuralt nätverk

neurala nätverk har länge använts i problem som detta, med mycket data, många variabler och möjligheten till brus i data.

varje ingångspunkt är en högdimensionell vektor., Det neurala nätverket är organiserat i en serie lager (se figur), där inmatningsvektorn går in på vänster sida av nätverket, vilket sedan projiceras till ett ”dolt lager.”Varje enhet i det dolda skiktet är en viktad summa av värdena i det första lagret. Detta lager projicerar sedan till ett utgångslager, vilket är där det önskade svaret visas.

nätverket är utbildat med ingången och önskad utgång, vilket i vårt fall är om punkten representerar ett lågt klickfrekvens (CTR) eller högt CTR-nyckelord., Då sker träning: vikter vid både de dolda och utgångsskikten justeras så att den faktiska produktionen motsvarar önskad utgång. När du väl har tränat, bör det neurala nätverket ta en ny datapunkt och mata ut antingen en noll (låg CTR) eller en (hög CTR). Om klassificeraren är osäker kommer det att ge ett värde någonstans däremellan.

styrkor och svagheter. Neurala nätverk har en hel del fördelar., Om vi har mycket inmatnings-och utmatningsdata att lära oss, men ingen aning om vad funktionen kartlägger de två tillsammans är, kan nätverket lära sig den här funktionen utan att vi behöver uttryckligen tillhandahålla den. Neurala nätverk är också bra med datamängder som är bullriga eller där vissa ingångar har saknade variabler., Men neurala nät har också en viktig nackdel med många andra tillvägagångssätt: svaret som framgår av ett neuralt nätverks vikter kan vara svårt att förstå (det kan fungera, men vi vet inte hur), och nätverkets träning kan ta längre tid än vissa andra metoder för maskininlärning, såsom slumpmässiga skogar, som vi nu vänder oss till.

Slumpmässiga Skogar, en Ensemble Metod

random skog (Breiman, 2001) är en ensemble strategi som också kan ses som en form av närmaste granne prediktor.

ensembler är ett divide-and-conquer-tillvägagångssätt som används för att förbättra prestanda., Huvudprincipen bakom ensemblemetoder är att en grupp ”svaga elever ”kan samlas för att bilda en”stark elev”. Figuren nedan (tagen härifrån) ger ett exempel. Varje klassificerare, individuellt, är en ”svag elev”, medan alla klassificerare tillsammans är en ”stark elev”.

de data som ska modelleras är de blå cirklarna. Vi antar att de representerar någon underliggande funktion plus brus. Varje enskild elev visas som en grå kurva. Varje grå kurva (en svag elev) är en rättvis approximation till de underliggande uppgifterna., Den röda kurvan (ensemblen ”strong learner”) kan ses vara en mycket bättre approximation till de underliggande uppgifterna.

träd och skogar. Den slumpmässiga skogen börjar med en standard maskininlärningsteknik som kallas ett ”beslutsträd” som i ensembletermer motsvarar vår svaga elev. I ett beslutsträd anges en inmatning överst och när den går ner i trädet blir data hinkad till mindre och mindre uppsättningar. För detaljer se här, från vilken figuren nedan tas.

i det här exemplet råder trädet oss, baserat på väderförhållanden, om man ska spela boll., Till exempel, om utsikterna är soliga och luftfuktigheten är mindre än eller lika med 70, är det förmodligen OK att spela.

den slumpmässiga skogen (se figur nedan) tar denna uppfattning till nästa nivå genom att kombinera träd med begreppet ensemble. Således är träden i ensembletermer svaga elever och den slumpmässiga skogen är en stark elev.

här är hur ett sådant system utbildas; för ett antal träd T:

1. prov n fall slumpmässigt med ersättning för att skapa en delmängd av data (se översta lagret av figuren ovan). Delmängden ska vara ca 66% av den totala uppsättningen.,
2. vid varje nod:
   1. för ett antal m (se nedan) väljs m prediktorvariabler slumpmässigt från alla prediktorvariabler.
   2. den prediktorvariabel som ger den bästa delningen, enligt någon objektiv funktion, används för att göra en binär delning på den noden.
   3. vid nästa nod väljer du en annan m-variabler slumpmässigt från alla prediktorvariabler och gör detsamma.,

beroende på värdet av m finns det tre något olika system:

• slumpmässigt splitterval: m =1
• Breimans bagger: m = totalt antal prediktorvariabler
• slumpmässig skog: m<< antal prediktorvariabler. Brieman föreslår tre möjliga värden för M: ½ √M, √M och 2√m

kör en slumpmässig skog. När en ny ingång matas in i systemet, det körs ner alla träd., Resultatet kan antingen vara ett genomsnittligt eller vägt genomsnitt av alla terminalnoder som nås, eller, när det gäller kategoriska variabler, en röstmajoritet.

Observera att:

• med ett stort antal prediktorer kommer den behöriga prediktoruppsättningen att vara helt annorlunda än nod till nod.
• ju större korrelationen mellan träd, desto större är den slumpmässiga skogsfelfrekvensen, så ett tryck på modellen är att ha träden så okorrelerade som möjligt.
• när m går ner, går både inter-tree korrelation och styrkan hos enskilda träd ner., Så något optimalt värde av m måste upptäckas.

styrkor och svagheter. Random forest runtimes är ganska snabba, och de kan hantera obalanserade och saknade data. Slumpmässiga skogs svagheter är att när de används för regression de inte kan förutsäga utanför intervallet i träningsdata, och att de kan Over-fit datamängder som är särskilt bullriga. Naturligtvis är det bästa testet av någon algoritm hur bra det fungerar på din egen datauppsättning.,

testa våra klassificerare

för att förstå hur vi testar klassificeraren måste vi förklara flera begrepp:

• korsvalidering
• trösklar
• medelprecision
• precision över chans

Korsvalidering

vårt klassificeringstest bör vara ekologiskt giltigt. Det bör visa vår klassificerare under förhållanden så nära produktionsmiljön som möjligt.,

i produktionen är klassificeraren utbildad på många projekt där vi känner till CTRs, men vi vill verkligen veta hur klassificeraren förutspår CTRs för ett nytt projekt som det aldrig har sett tidigare.

Vi testar vår klassificerare med en teknik som kallas ”cross-validation”: träna klassificeraren på alla projekt utom en. Naturligtvis vet vi också rätt Ctr för det här utbyggda projektet, så vi kan se hur bra klassificeraren gör på det, utan att fuska genom att träna klassificeraren på hold-out. Vi gör detta i sin tur med varje projekt. Se figur nedan.,

låt oss säga att vi har Projekt A till F. Vi tränar en klassificerare på Projekt A till E och testar på F. då tränar vi på A och C till F och testar på B. vi gör det i sin tur och håller ut varje projekt tills vi tränar på A till E och testar på F. varje projekt är ett ämne i vårt experiment, med ämnen A till F (se figur nedan).

slutligen samlar vi in resultaten från varje korsvalideringsperiod för statistisk analys. Den experimentella frågan vi vill svara: ger klassificeraren oss mer information om CTR än att bara gissa?,

trösklar

klassificeraren förutspår om indatavektorn skulle resultera i en låg eller hög CTR. Klassificerarens utgång är ett tal från noll till en, ge eller ta. En noll förutspår låg CTR, en förutspår hög CTR. Men vad gör vi om klassificeraren matar ut ett värde däremellan, säg en 0,4 eller en 0,6? Vi måste välja en tröskel. Ovanför detta värde behandlar vi klassificeringsutgången som att förutsäga hög CTR. Under detta värde behandlar vi klassificeringsutgången som att förutsäga låg CTR.

klassificeraren är inte perfekt, så ibland kommer det att göra misstag., Ibland kommer klassificeraren felaktigt att förutsäga att ett högt CTR-objekt är lågt (en” miss”), och ibland kommer klassificeraren felaktigt att förutsäga att ett lågt CTR-objekt är högt (ett”falskt larm”).

följande siffror visar en frekvensfördelning för klassificeringsutgången för både låga och höga CTR-objekt. Höga CTR-objekt, i grönt, tenderar att resultera i en klassificeringsutgång mot 1. Låga CTR-objekt, i rött, tenderar att resultera i klassificeringsutgång mot 0. Observera att i alla tre figurerna förblir avståndet mellan de två kurvorna oförändrat. Allt som förändras är tröskeln.,

anta att vi har totalt 1000 datapunkter, jämnt fördelade mellan låg och hög CTR. I ovanstående figur är vår tröskel ganska hög (säg 0,85). Detta resulterar i en relativt låg falsklarmhastighet (endast 50 objekt totalt är falsklarm) och en ganska hög misshastighet (100 objekt som är i sanning höga CTR saknas).

i figuren nedan, vid lägsta tröskelvärde (säg 0,40), går vår falsklarmhastighet upp till 100, och vår misshastighet går ner till 75. Så när vi sänker vår tröskel går vår falska larmfrekvens upp från 50 till 75 till 100, medan vår misshastighet går ner från 100 till 90 till 75.,

vi ritar tröskeln baserat på vilken typ av fel vi vill undvika fler, missar eller falsklarm. En högre tröskel innebär fler missar och färre falsklarm. En lägre tröskel betyder motsatsen. Att ändra tröskeln ändrar inte klassificerarens underliggande noggrannhet, det flyttar bara felet runt.

Medelprecision

klassificerarens effektivitet är avståndet mellan de två metoderna, vilket inte varierar som tröskelförändringar. Ett sätt att mäta effektiviteten hos klassificeraren är”precisionen”., Precision är antalet verkligt korrekta objekt (”träffar”) dividerat med antalet objekt som klassificeraren säger är korrekta (träffar + falsklarm).

i vårt exempel ovan har vi 1000 datapunkter, varav 500 är höga CTR. Vår klassificerare fångar korrekt 400 höga Ctr. Klassificeraren indikerar att ytterligare 50 poäng är höga Ctr, när de i själva verket är låga CTR. Det betyder att vi har 50 falsklarm. Dessa resulterar i en precision på 400/450 = 88.88% objekt som klassificeraren säger är korrekta (träffar + falsklarm).,

”Mean precision” tar hänsyn till problemen med att välja ett tröskelvärde, noterat ovan, genom att utföra denna beräkning vid en rad tröskelvärden och med medelvärdet.

förbättring över chans

tyvärr är det i verkligheten inte så lätt som det här: projekten varierar kraftigt i antalet höga CTR-nyckelord. Vissa projekt innehåller verkligen bara 15% hög CTR, medan andra är så höga som 80% eller 90%. Finanssektorn, som ett exempel, kommer alltid att ha en lägre genomsnittlig CTR än ett populärt Facebook-spel. Vi behöver mer än medelprecision för att mäta klassificeringsprestanda.,

Föreställ dig att vår klassificerare har en genomsnittlig precision på 95%. Även om det låter bra, om projektet är 95% hög CTR, är det mindre imponerande. I det här fallet, om vi alltid gissade att något var hög CTR, skulle vi göra lika bra som klassificeraren! Således måste vi rapportera medelprecisionen efter att ha subtraherat den sanna andelen av höga CTR-objekt för det projektet. Vi kallar detta ”mean precision above chance”. I våra rapporter innebär en genomsnittlig precision på 10% att klassificeraren har en 10-punkts högre precision än att gissa ensam.,

resultat

i vår testuppsättning togs projekt som hade ett riktigt högt CTR-värde på 1 (alla höga CTR) eller mindre än 0,05 (mindre än 5% höga CTR) bort, vilket resulterade i 72 projekt för vidare analys. Kom ihåg att varje projekt kan innehålla dussintals inriktningskombinationer, och varje inriktningskombination kan innehålla hundratals sökord.

För det neurala nätverket var den genomsnittliga förbättringen för klassificeraren 0,15 (se tabellen nedan). Ett parat t-test på resultaten visade t(71) = 7.72, p < 0.0001 (ett p-värde på mindre än 0.,05 anses traditionellt vara statistiskt signifikant, vilket innebär att risken för att denna effekt beror på slumpen är 1 på 20 eller mindre). Detta innebär att den neurala nätverksklassificeraren visade en statistiskt signifikant förbättring av detektering av höga CTR-objekt jämfört med chans.

för den slumpmässiga skogen var den genomsnittliga förbättringen för klassificeraren 0,06 (se tabellen nedan). Ett parat t-test på resultaten visade t(71) = 3.17, p < 0.003., Detta innebär att den slumpmässiga skogsklassificeraren visade en statistiskt signifikant förbättring av att upptäcka höga CTR-objekt jämfört med chans.

vid jämförelse av den genomsnittliga förbättringen mellan de två klassificerarna var skillnaden 0,09, till förmån för det neurala nätverket. Ett parat t-test på resultaten visade t(71) = 3,63, p < 0,0006. Det betyder att den neurala nätverksklassificeraren visade en statistiskt signifikant förbättring av att upptäcka höga CTR-objekt jämfört med den slumpmässiga skogsklassificeraren.

båda klassificerare fungerar., Det neurala nätverket är betydligt bättre än den slumpmässiga skogen med 0.09.

	mean high CTR	Mean precision of classifier	Mean improvement
neuralt nätverk	0,44	0,59	0,15			0,15					0,15				/tr >
Random Forest	0.44	0.50	0.,06

Frekvenshistogram

den här siffran visar ett frekvenshistogram av den genomsnittliga precisionsförbättringen över chansen för de 72 projekten för det neurala nätverket:

den här siffran visar ett frekvenshistogram av den genomsnittliga precisionsförbättringen över chansen för de 72 projekten för den slumpmässiga skogen:

neuralt nätverk vs slumpmässig skog

/h2>

diagrammet nedan jämför resultaten av fyra neurala nätverk med tre slumpmässiga skogar., Det visar oss att det finns stor variation i precision mellan projekt och att varje metod tenderar att spåra den andra, med en korrelation på 0.8677.

ingen metod kan sägas vara bättre än den andra i alla fall. Det återstår att se om det finns någon systematicitet om varför och var en metod är bättre än en annan.

som de två följande figurerna visar, visar både neurala nätverk och slumpmässiga skogar låg variabilitet över våra data i de flesta men inte alla fall: det vill säga för de flesta projekt, rerunning av klassificeraren flera gånger resulterar vanligtvis i ungefär samma precision., I de följande två siffrorna ligger de olika projekten, i syfte att öka precisionen i varje enskilt fall, på x-axeln och precisionen ligger på y-axeln.

i nästa diagram har vi subtraherat precisionen hos neurala nätverk från precision av slumpmässiga skogskörningar, för samma projekt, av totalt 123 projekt. I nästa figur ligger de olika projekten, i storleksordningen ökad precision, på X-axeln och precisionen ligger på y-axeln.

vad den här bilden säger oss är att i ett så komplicerat utrymme kommer det att finnas områden som blir svåra att modellera med bara en inlärningsmetod., Vi vet intuitivt att neurala nätverk och slumpmässiga skogar är tillräckligt olika algoritmer, men det här är ett bevis på att projekten på vänster sida av S-kurvan står mer för att vinna med den slumpmässiga Skogsmetoden. Sådana ensemblemetoder är ibland det enda sättet att få svåråtkomliga vinster (vinnarna av Netflix-priset hade ett stort exempel på en-de namngav även sitt lag efter det!)

dessa resultat är bara preliminära, men, så håll ögonen öppna för att se vad ytterligare tweaking ger! Kontakta oss idag för att lära dig mer.