[****INFORMATIKA****]

Netflix-adatbányászverseny (www.netflixprize.com)
================================

Annak örömére, hogy megvan a - szerintem immáron elvitathatatlan illetve a játékszabályok keretei között felülmúlhatatlan - 1 millió dollárt érő nagydíjas 10,5%-os javítás a Netflix-versenyen (http://www.netflixprize.com/leaderboard), eleresztenék a témában egy rövidke írást.

Előzmény
======

Aki nem tudná miről van szó, annak dióhéjban itt van pár sor, a többiek ugorhatnak a következő szakaszhoz.

A Netflix-verseny egy érdekes, izgalmas, sok (magyar) embert lázbahozó, kiírásában triviálisan egyszerű, 2006 ősszel indított, _5_ évig (!!) nyitottra tervezett, (bár nem feltétlen, de) leginkább adatbányásznak mondható VERSENY, évenkénti 50.000 dolláros szakaszdíjjal, valamint 1.000.000 dolláros nagydíjjal. A nagydíjért nem kell csinálni sokat: le kell tölteni egy tömörítetten, CD-nyi méretű - tehát mondhatni elég nagy - text-állományt. Minél kisebb hibával (RMSE) egy sokkal kisebb text-állományt kell feltölteni [kvázi 2.8 millás tippmix-szelvény, a hagyományos 3-mal(H,D,V) szemben soronként 5 lehetséges egymással némileg korreláló állapottal (1,2,3,4,5)]. Aki a hibaküszöböt egy jóldefiniált érték alá viszi, majd megírja angolul egy 10 oldalas cikkben a know-how-t, már viheti is a díjat. A hibajavítás láthatóan exponenciálisan lassult az eltelt majdnem három év alatt, pedig "csak" 10%-ról volt szó ;).

A Netflix egy internetes videótéka (Észak-Amerika legnagyobb videókölcsönzője), ahol vannak kölcsönözhető filmek, és persze vannak kölcsönző ügyfelek. Természetesen van lehetőségük az ügyfeleknek értékelni a filmeket, 1-től 5-ig. A kölcsönző cégnek érdeke, hogy az ügyfelek minél több filmet kölcsönözzenek, ezért jól megfontolt üzleti érdekből ajánlanak az ügyfeleknek újabb, ügyfél által addig még nem látott és nem értékelt filmet. Mivel nagyon sok az ügyfél és a film, sőt kombinatórikus robbanással szaporodnak, ezt az ajánlást 'kézzel' nem igazán lehet megejteni. Azt viszont jó lenne elkerülni, hogy aki például a Dallas c. amerikai sorozatot értékeli 5-ösre, az ne mondjuk egy Ingmar Bergmann filmet kapjon ajánlatként, vagy fordítva. ;)

A Netflix ajánló rendszernek (Cinematch) egyszerre kell minél _pontosabban_ becsülnie a vásárló ízlését (következő ajánlati filmet illetően -> "Ha egy film tetszett akkor ezt nézd meg" jeligére), illetve a hatalmas adatmennyiség (már most milliárdnyi egyedi ügyfél-film értékelése van a Netflixnek az adatbázisában) értékelése miatt követelmény a skálázhatóság és a jó _performancia_ biztosítása, még ha ez a versenyből nem is nagyon derült ki. (lássuk be ez a becslési (prediktálási) pontosság és a performancia egymás ellen dolgozik).

Az input-textállományok

17.770 darab film ->
id,év,cím -> Például ->
1,2003,Dinosaur Planet

100.000.000+ darab értékelés ügyfél & filmenként ->
azaz 17.770 txt-ként, 480.000 ügyfél által -> összesen 2 GB-on szétterítve ->
filmid: majd a következő sorokban -> custid, értékelés, értékelés ideje -> Például ->
10:
699878,2,2004-02-09
2625420,2,2005-03-17
1874659,5,2003-11-18

Az egész egy szép nagy kétdimenziós - meglehetősen ritka - mátrix, 480.000 sorral, 17.770 oszloppal. A feladat "mindösszesen" annyi, hogy minél pontosabban töltsük ki a mátrix 'pár' (->2.8 millió darab) további elemét /"missing values"/. Ezt egy egyszerű textként feltölteni, Netflixes Oracle-adatbázisba, ahol egy egyszerű pársoros Perl-script kiköp egy egy valós 0-4 közötti számot azaz ezáltal rangsorolja a teljesítményt.

Bár a Netflix Cinematch rendszere nem dolgozik a filmes adatbázissal: megadták a 17.770 film címét és évét (ha valaki taxonómiát akarna csinálni rá), igaz a műfajt és egyéb adatokat már nem. Ez utóbbi opcionálisan internetes helyekről (pl.:netflix.com, imdb.com, allmovie.com) is pótolható, igaz név (és nem id-) alapú párosítással.

Akkor nézzük mi is ez a hibaküszöb, pontosan. Van a valós érték, ami szerepel a Netflix adatbázisban (effektiv konkrét ügyfélértékelés), meg van a mi általunk becsült/prediktált ügyfél-film értékelés.

A hibaküszöb: RMSE - "Root Mean Square Error" -> a nagyobb hiba jobban büntet. Képlet ->

RMSE = sqrt ( (1 / összes értékelés/jelen esetben, ugye, 2.8 millió/) * szumma( (pred.értékelés-valós értékelés)^2 ) )

Szavakkal: mennyi a jósolt es az eredeti rating közötti különbség (hiba) négyzetének átlagának gyöke. (RMSE)

Ha tehát 3-ast tippelünk (bár megengedett a tizedesjegy is: lehetséges 3.4-et tippelni például) és az ügyfél eredetileg 5-öst adott, akkor 4-gyel fog nőni a számláló.

RMSE=4.00 -> a létező legrosszabb elméleti érték: ha mind a 2.8 millió értékelés 5-ös lenne, és minden becsült értékelés mondjuk 1 lenne.

RMSE=3.16 -> gyakorlatilag elérhető legrosszabb RMSE (a netflix-dataseten) -> amikor a minél nagyobb tévedés a cél...

RMSE=1.27 -> triviális RMSE (ha minden ratingre 4-et tippelünk, amiből amúgy a legtöbb van)

RMSE=1, ha minden tippünknél pontosan egyet tévedünk valamilyen irányba.

RMSE=0.9514 -> Netflix Corporation informatikai rendszerének Cinematch predikciós RMSE-értéke. Ez a küszöb, akinek ennél kevesebb, az felkerül a dicsőségtáblára

RMSE=0.8563 -> 1.000.000 USD-t érő RMSE

RMSE=0.8558 -> Nagydíjat érő elért RMSE

RMSE=0 -> tökéletes telitalálat


Aktuális gondolatok
============

Ahogy Erdős Pálnak is volt elképzelése a "nagy könyvről" (matematika), úgy én is szoktam elmélázni az adatbányászat nagy könyvéről, amit nagyon szeretnék elolvasni. Abban egészen biztos lenne pár extra fejezet, amit szerintem még soha, sehol, senki, nem írt meg, pedig azt gondolom magamról böngészem rendesen a Data Mining könyveket, legelébb is a tartalomjegyzékeiket.

(1) Az egyik fejezet a szintetikus vs valós datasetek témája (benne például, hogy hogyan lehet felismerni/megkülönböztetni őket programból).

(2) Illetve milyen stratégiával érdemes indulni adatbányászversenyen és mennyi energiát/időt érdemes belefeccölni (beleértve, hogyan kellene ilyeneket (korrekten) szervezni, hogyan lehet a hackeléseket meg workaroundokat pro és kontra szűrni).

(3) Sql nyelvi lehetőségek és korlátok kontra adatbányászat, az interdiszciplinaritás mezsgyéin.

(4) Feature selection úgy kompletten en bloc

(5) Milyen (interjú)kérdéseket tenne fel egy üzleti elemző pluszba a versenykiíráson felül, ami megalapozhatná, célirányosíthatná, horribile dictu rövidíthetné az adatbányász-kutatást

/Egyszer össze kéne szedni ennek az adatbányászatos 'nagy könyvnek' legalább a tartalomjegyzékét! :o)/

A verseny számomra egyértelműen a predikciós pontosságról szólt a korlátlanul végtelen erőforrások meg költségek implicit feltételezésével, hanyagolva olyan szempontokat mint üzemeltethetőség, skálázhatóság, timeframe, folyamatos adatbázisfrissítés stb.

A Netflix-feladat egyszerűsége szépsége engem is megragadott mondhatnám rabulejtett és meglehetősen sokat foglalkoztam vele (ez év első hónapjaiban, kisebb-nagyobb megszakításokkal): sajnos többet, mint utólag beláthatóan ildomos lett volna, meg egyáltalán terveztem (emiatt is nagyon jó a hír, hogy végre kvázi vége van a versenynek).

Kezdetben elég sokat olvasgattam szerte a neten, elsősorban azért, hogy lássam hol tart a világ, aztán szánt szándékkal abbahagytam ezt és szigorúan agyban, elmetornaként mindenféle programozás meg számítógép nélkül azon agyaltam, egyébként kifejezetten deviáns utakon ;), hogy ha rajtam múlna; milyen stratégiát próbálnék ki _egyedüliként_. Az kezdettől látszott, hogy rengeteg ötlet mentén lehet elindulni illetve abban semmi poén nincs, hogy "ingyenmunka" keretében az összeset végigpróbálja az ember esetleg teljes mélységükben.

- Mivel a Netflix nem élt a filmcímes adatgazdagítás + text mining lehetőségével a saját alappredikciójánál, így hálistennek ez engem sem 'kellett' érdekeljen (hiába engedte meg amúgy a játékszabály). Különben is a nehéz ritka mátrixos collaborate filtering feladat a szép feladat, így önmagában(!) /szemben a content filteringgel/ :o)

- Mivel kvázi rengetegen mátrixot faktorizáltak - főleg az élenállók -, én direkt kerültem ezt, és egészértékű problémaként (magyarázó- és célváltozók szintjén egyaránt) igyekeztem felfogni a feladatot. Nagységrendileg kisebb mátrixot manipulálni megint csak kisebb kihívás, mint az eredeti nagyméretűt 17.770 x 480.000-es mátrixot. :o)
/BTW: ab ovo önmagában kerültem az olyat, hogy valami ígéretes publikált megoldást reimplementáljak és azt próbáljam meg egy kis ötlettel esetleg tuningolni. Nulláról indulni, valami eredetien(?) vad ötlettel az igazi, nem?! :o)/

- Mivel nagyon sokan - főleg az élenállók -; óriási szellemi-, humán- (PhD aspiráns-hadak) és technikai kapacitással rendelkeztek én ebben is igyekeztem a másik véglet felöl közelíteni -> egymagam és kopasz windows notebookon, tudatosan törekedve minél kevesebb munkával (mindenféle előtisztítás nélkül: hogy ez mekkora szentségtörés lehet, meglehet le sem lenne szabad írnom), minél egyszerűbben minél elemibb és általános iskolaibb - még ha az brute force-s is - logikával közelítettem a problematikához stb. Egy - mondjuk - NNMF pedig nem része az elemi iskolai tantervnek. :o)

A fent vázolt - szerintem - óriási hendikep vállalásából is talán érzékelhető, számomra egyáltalán nem 'top priority' volt a nyerésre hajtás, az viszont célom volt (1) a munka dandárját agyban végezzem, (2) minél rövidebb idő alatt és csak e-g-y-e-t-l-e-n módszert próbáljak ki, (3) nagy méretek miatti optimalizálási csemegéket megízleljem :o), (4) minél pontosabb képet kapjak mennyire nagy dolog a Netflix előrejelzése, ezt mennyire tudom ilyen szélsőséges feltételek vállalása mellett megközelíteni vagy mennyire maradok le mögötte. Tudjak kiválasztani egyetlen stratégiát fejben ("amiben legjobban tudok hinni a legvégsőkig"), és azt tudjam hatékonyan implementálni.

Az eredmény, a legőszintébben mondom, minden elképzelésemet meghaladta.

És az alábbiakat most csak leírni tudom, bizonyítani nem: a keretek egyébként sem adnak rá lehetőséget /hálistennek :o)/.

Az önmagában kérdés, hogy merném-e valaha leírni a teljes gondolatmenetemet. Jelenleg úgy érzem ez olyan lenne, mintha mondjuk meztelenül kéne zászlófelvonáskor kiállnom a Kossuth térre -> így utólag visszatekintve az egész ügybeni erőlködésem annyira banálisan triviálisnak hat, mint egy mexikói szappanopera, és ilyesmivel nem szokott dicsekedni az emberfia. :o)

A nagy ritka mátrix alapján 1.4 millás P(robe) valamint a 2.8 millás Q(ualifying) datasetekre csináltam egy 700+ mezős származtatást -> persze természetesen a végül kikristályosított stratégiám alapján: a megírt Oracle PlSql-progi sokkal egyszerűbb volt, mint ez hangzik. Sziszifuszi melóval és óriási szerencsével ezt leszűkítettem 10 magyarázó mezőre/változóra. (A hagyományos feature selectionök nálam becsődöltek).

Abból indultam ki, hogy milliós rekordszámoknak már elégségeseknek kell lenni bármilyen data mining modellhez. A kutyaközönséges SPSS Clementine-s multinomiális logisztikus regressziót ráeresztettem tanításilag a P dataset random 14.000 rekordjára és a komplementerre teszteltem. 0.27 - 0.331 RMSE-t kaptam (a Netflixé versenykiíráskor: 0.9514, a mostani nagydíjas: 0.8558, mint fentebb is írtam). Nem kívánom senkinek annak az állapotnak átélését, amikor ugyanezt Q-ra is teszteltem és felküldtem az első állományaimat (kitöltött 'tippmix-szelvényeimet'). Folyamatosan 1 feletti RMSE-ket kaptam. (A legjobbam valami 1.11 volt) :o((((((

Második fázisként arra gyanakodva, hogy nem biztos, hogy P-re érdemes tanítani bármilyen szinten, annak esetleges spéci jellege miatt, kigeneráltam a 100 milla rating random majdnem egyötödéhez(!) is a mezőimet. És ugyanúgy megkaptam a hihetetlen RMSE-ket rájuk (lásd a végén), a Q-ra meg ugyanúgy nem volt semmi használható! Azóta már 60 milla ratinghez is megvan a mezőim kikalkukálása és csak azért nem több ratinghez, mert a hír hatására már lelőttem a mezőkikalkuláló progim futását.

Szerencsére sikerült észnél lennem és/vagy mázlim volt, hiszen mindösszesen is csak 21 felküldésem ("submission") volt. /Oracle RDBMS ezt illetően nagy segítségemre volt: a végén már csak percek teltek el az ötlet és az adatfelküldés között annyira gyors volt az egész folyamat. A kiértékelési eredmény is 1-2 perc alatt megérkezett./

Nagyon éreztem, hogy valami bűzlik Dániában és éppen ezért más irányba kezdtem keresgélni. Méghozzá a legnehezebb irányba, amit fehér ember szerintem megint csak nem követ el. :o) ==> Miben különbözik a P meg a majdnem 20 millás datasetem a Q datasettől. Mostani eszemmel is azt gondolom nem egy leányálom; sql-ekkel meg szemmel verve, ennyi egész számmal viaskodni, legyen ez bármennyire is szép kihívás. :o)

/Zárójeles megjegyzés: világéletemben izgatott, lásd fentebb is, hogy az sql (ami az előéletem miatt komoly jelentőségű nálam) hogyan viszonyul az adatbányászathoz -> talán már írtam is erről itt valahol. Na ennél az alfeladatnál az sql-nyelv olyan volt, mint az elefánt a porcelánboltban. :o)/

És ismét szerencsém volt. Egy nemtriviális atomi(!!) boolean kifejezést találtam, mindenféle not, and, or nélkül, ami a mezőimet illetően i-g-a-z volt a Q-ra és h-a-m-i-s volt a P-re, majdnem 20 millára (60 millára már nem néztem és értelem híján immáron nem is fogom). Egy picit túlzok: 3.000 azaz háromezer rekord kivétel volt mindkét esetben. Azt gondolom háromezer kivétel 1.4 milla, 2.8 milla, majdnem 20 milla rekord esetén az már "szabályerősítő" :o). Egyébként a kivételek alapján is tanítottam meg teszteltem, de túl kevés volt hozzá a rekordszám és/vagy volt egyéb csavar is a történetben.

Magyarán és végeredményben, meg némi extrapolációval, azt sejtem, hogy valamilyen értelemben kölcsönösen oda-vissza egymás komplementerei a 100 millás, egyébként általam valósnak gondolt, publikált állomány meg az általam szintetikusnak sejtett Q állomány (aminek ratingjeit sose fogjuk megtudni a versenykiírás legnagyobb dicsőségére :o(( ). Ennél csak egy rosszabbat tudok elképzelni: ha valós esetben bekövetkezett ratingeket valamilyen stratégia mentén tömegesen milliószám megmásítanak. Na az a feladat mennyire lenne megoldható, meg főleg mennyire lenne (értelmes) adatbányászat?! Hálistennek már ezen sem fogok agyalni. :o)

Ezután - szerintem megint a normálistól eltérően :o) - immáron az érdekelt, hogy Netflixes aggyal tudok-e szintetikus Q datasetet produkálni, hiszen ha igen, akkor egy potenciális bizonyíték lett volna a kezemben az Egely György típusú "összeesküvés elméletemre". ;) Sajnos a feladat nem volt triviális, miközben nekem meg április végén beesett egy nagyon durva projektem, így teljesen abba kellett hagynom a Netflixes játszadozást. Csak le tudtam skiccelni, milyen lépéseket tettem volna még meg, ha van időm.

A történelem nem ismeri a "ha"-t. Nem megengedve, de csak egy pillanatra feltéve, hogy nem hibáztam a számításaimban illetve programozásomban (no meg egyúttal nem akarok itt szédíteni senkit). Még ha nincs is a kezemben semmi, például egy 1.400-1.500-es "Hall of fame"-listára kerülés sem.

Bennem felmerül a kérdés, hogy ha a fentiek igazak, akkor

- Mindez egyáltalán elképzelhető? Én tuti nem hinném el, ha m-e-s-é-l-i-k nekem: ezért is nem vagyok hajlandó agyalni a Netflix Corporation; versennyel kapcsolatos motivációin. :o)

- Mennyivel korábban lett volna nagydíjkiosztás és/vagy mennyivel másabb RMSE-t kellett volna javítani, ha a valós 100 milla ratingből van a Q dataset kiválasztva? Önmagában felfoghatatlanul szép az esetlegesen 100 milla ratingen is tartható 0.3 RMSE, szerintem.

- Azt nem vitatom, hogy versenynek verseny ez az egész, így ebben a megcsavart formában is, de kérdés mennyire értelmes adatbányászat, mennyire szakad el a valós üzleti élettől.

- Ha tényleg nagyon szintetikus dataset a Q, akkor ezt a kiírásban nem kéne-e feltüntetni lásd "adatbányászat és etika topik". Vagy ez csak az én figyelmemet kerülte el a sok betű között?

Egy dolog viszont egészen biztos: a Netflix-verseny valamit összetört bennem: egy illúziót az adatbányász-versenyeket illetően. Ami persze valahol jó (függetlenül attól, hogy ez mennyire indokolt és védhető), mert könnyebben tudok más értelmes (és valós!) problémák után nézni. Ez is feltétlen haszna volt az egészben való elmélyedésnek a csomó érdekes és hasznos tapasztalaton meg megélhető sikerélményen felül.

PS:

Magánlevelezésben folytatódott a fenti sorok keltette 'hullámok', az ott adott válaszok következnek alább. Meg feltűnt a horizonton némi agyalás után /de jó lenne már leszállni az egész témáról :o)/ egy harmadik lehetőség körvonalai a rejtélyes Q(ualifying) dataset mibenlétére is (szintetikus dataset, rating-átírás mellett).

>...mezőszármaztatás...

A 700+ mezős származtatás leírása egyrészt nem olyan egyszerű és rövid, mégha sejthető is belőle a kombinatorikus robbanás 'mindent mindennel'-je (persze szisztéma szerint), másrészt így a friss élmények hatása alatt perpillanat egyszerűen képtelen vagyok eldönteni, hogy mennyire akarom megtartani magamnak végleg teljesen vagy részlegesen ezt az infót: sokat kell még rá aludnom, hogy elfelejtsem a "pöreség-érzést", meg talán nincs is nagy infóértéke a válasznak.

>..."atomi" bool-kifejezés....

Ez a könnyebb kérdés. A 10 általam kiválasztott - brutálisan erős magyarázóerejűnek tűnő - változóm az valójában 2x5 db, ahol a 2 arra utal, hogy honnan nézünk rá a mátrixra (mi 'drive-ol'): a filmek felől vagy az ügyfelek felől. Az 5 meg a lehetséges ratingek számával függ össze. A nagy mátrix 17.770x480.000-es, azaz távolról sem négyzetes; lévén sokkal több az ügyfél (480.000), mint a megnézhető film(17.770) nagyságrendileg majdnem harmincszorosan. Na most ilyen aránytalanság mellett joggal várja el az ember, hogy az ügyfél-oldalon számolt értékek - nézőponttól függően - relevánsan nagyobbak vagy kisebbek legyenek, mint a film-oldalon számoltak. A döbbenetes az volt, hogy ez csak P-re meg a random majdnem 20 millás publikált rating-állomány részhalmazra volt igaz (talán a teljes 100 millásra is), Q-ra meg nem: de olyannyira, hogy Q-ra m-e-g-e-g-y-e-z-t-e-k a megfelelő egész értékek 3.000 kivételt leszámítva, de milliós rekordszámokra -> ami azonnal 'ortogonalitási/összefüggési' problémákat vetett fel. Az összefüggés felfedezése triviálisan megnehezítette a prediktálás jóságának növelését (az általam kitalált koncepción belül), viszont megkönnyítette a szintetikus dataset előállításának lehetőségét. /Ezt csak, mint triviális következményt említem :o)/

>...Qualifying dataset mibenléte III...

Egy 15-20.000-es ügyféltörzsű kisebb videótéka felvásárlása illetve migrálása.

* Erről ugyanis a Netflixnek tényleg nem kell (legalábbis nem olyan kirívó, ha nem teszi meg) említést tennie versenykiíráskor
* Így már ugyanarra a filmállományra (kvázi)négyzetes a rating-mátrix
* Elüthet a Netflix-ügyfelek szokásai egy másik kis cég ügyfeleinek szokásaitól.
* Tényleg érdekes szakmai kérdés, hogy Netflix-adatbázisból lehet-e és hogyan prediktálni egy másik kisebb adatbázis értékeire. És ez érdekelheti a Netflixet
* Magyarázhatja, hogy miért van eltérés a 100 milla alapján történő prediktálás és egy másik dataset alapján történő prediktálás között, noha a filmadatbázis kvázi ugyanaz.

És még biztos számtalan egyéb kérdés, adatbázis-hegesztési mizéria is felmerülhet.

BTW: Azt gondolom nem helyes ilyesmiken és így agyalni egy adatbányászverseny-kapcsán, illetve az egész kérdéskör teljesen másképp merül fel a valós üzleti életben. Pláne, ha pusztán csak negyedrészben vagyok is jó úton a gondolatmenetemmel. :o(

Az én utolsó idén áprilisi nem 20 csak 16 millás találati mátrixom, 0.331 RMSE-vel, 8 millás tanítás után. Az x tengelyen víszintesen van az én predikcióm ($L-értékek, aki jártas az SPSS Clementine-ban; $ mutatja, hogy számolt, L mutatja, hogy logisztikus regresszió által), függőlegesen a valóság.

Ha csak az átlóban van 0-tól különböző értékes darabszám, akkor van telitalálat. :o)

| | 1 || 2 || 3 || 4 || 5 |
|1|0.597.087|0.009.672|0.095.230|0.001.137|0.008.281|
|2|0.015.831|1.419.506|0.105.257|0.001.574|0.002.271|
|3|0.018.860|0.006.901|4.255.293|0.075.946|0.014.518|
|4|0.007.288|0.001.706|0.123.805|5.043.766|0.003.302|
|5|0.008.281|0.001.506|0.111.668|0.002.510|3.477.189|