[****INFORMATIKA****]

2007-08-29 - KDD-konferencia élménybeszámoló - Netflix-Prize

Sajnos nem volt nálam ceruza és papír, ami alább következik azt az emlékeimből rekonstruáltam.

www.netflixprize.com

A fenti link egy érdekes, izgalmas, sok (magyar) embert lázbahozó, kiírásában triviálisan egyszerű, _tavaly_ 2006 ősszel indított, _5_ évig (!!) nyitott (azaz még 4 évig), (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. Bár még nem talált gazdára a nagydíj (csak egy szakasz díj, ugye), de igyekezni kell (szvsz), mert talán hetek kérdése, a hihetetlen innovativitás és hatékony versenyszellem miatt. A nagydíjért nem kell csinálni sokat: le kell tölteni egy tömörítetten CD-nyi - tehát mondhatni elég nagy - text-állományt. Minél kisebb hibával (RMSE) egy sokkal kisebb text-állományt kell feltölteni. 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.

Hogy mekkora az érdeklődés, mutatja, hogy a Google közel 100.000 találatot hoz a témára. Szabad regisztrálás után a CD (input) text-adat cucc letölthető

Fontosabb linkek:
Versenyállás: http://www.netflixprize.com//leaderboard
Szabályok: http://www.netflixprize.com//rules
FAQ: http://www.netflixprize.com//faq

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 kombinatorikus robbanással szaporodnak, ezt az ajánlást 'kézzel' nem igazán lehet megejteni. Azt viszont jó lenne elkerülni, hogy aki 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 skálázható és jó _performanciát_ kell biztosítania (lássuk be ez a becslési (prediktálási) pontosság és a performancia egymás ellen dolgozik). Mivel a verseny csak és kizárólag a prediktálási pontosságot tűzi ki, így mondhatni a netflixnek ez az egész verseny legelőször is reklám. De ez implicit jelenti, hogy az őáltaluk teljesített hibaküszöbben finoman szólva is van tartalék. (-> Lényegesen kevesebb alapinformációval dolgoznak, és szempont a 'valósidejű' performancia)

Az input-textállományok

17.000+ 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.000+ 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.000 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 Value/. Ezt egy egyszerű textként feltölteni, Oracle-adatbázisba, ahol egy egyszerű pársoros Perl-script kiköp egy számot azaz ezáltal rangsorolja a teljesítményt. Naponta egy azaz egy output text-állományt lehet feltölteni, amit gondolom meg lehet hágni, ha valaki több néven regisztrál.

Bár a Netflix Cinematch rendszere nem dolgozik a filmes adatbázissal: megadták a 17.000 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. Tudtommal ezt meglehet tenni a kiírás szerint is.

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=0 esetről könnyen belátható, akkor kapjuk, ha tökéletesen tippelünk, hiszen 0-nak a négyzete is 0, akárhány 0 összege is 0, és akármilyen számmal osztva is 0-t kapunk, amiből négyzetgyökvonás után is 0 lesz.

RMSE=4 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=1, ha minden tippünknél pontosan egyet tévedünk valamilyen irányba. A nagydíj elnyeréséhez elég, ha maximum csak egyet tévedünk valamilyen irányba az esetek 85%-ban, és 15%-ban tippelünk pontosan -> (RMSE <= 0.8563). Ez a titokzatos díjhoz elvárt küszöb érték úgy jött ki, hogy a Netflixesek által elért küszöbértéket kell 10%-kal megjavítani. A jelenlegi legjobb RMSE -> 0.8625. Ezért mondom, hogy sietni kell, ha valaki még pályázni akar a díjra. :o)

Próbaállomány témája -> A Netflix definiált egy 1,5 milliós próbaállományt a versenyzőknek, hogy ne csak feltöltéssel lehessen tesztelni. Megmondta mely értékeléseket érdemes teszt célból leválasztani a tanító adathalmazból.

Azt gondolom, szellemes, tiszta verseny, ami könnyen addiktivvá ("függővé") tudja tenni az embert. ;) Érdemes elovlasni Gáspár-Papanek Csaba BME-s adatbányász oktató-kutató lenti hozzászólását elolvasni adalékként.

Versenyzők:

- AT&T két - tán izraeli - informatikusa. Pár hete kapcsolódtak be, és taroltak. Kezdetben arról szólt a fáma, hogy kiléptek a munkahelyükről, hogy evvel foglalkozzanak. Ma már az AT&T linkeli őket, honlapjukon. :o)

- Gravity-csoport. BME-s informatikusok, Tikk Domonkossal. Amit lehet tudni az eljárásukról, hogy egy keretrendszerben vagy 120 ötletet próbáltak ki (szavaztattak és kombináltak), a nagy selejtezés után vagy 30-at hagytak meg. Külön kezelték a film/TV-sorozatokat. Voltak elsők is, sokáig másodikok. A BelKor csapat előzte le őket, amikor nem olyan rég bekapcsolódtak.

- Volt még egy magyar a prog.hu-s fórunm szerint. Ő egyedül dolgozott.

- Arek Paterek, lengyel PhD-ző diák, mindent egy lapra feltéve foglalkozik evvel.

- Volt nyáron egy KDD konferencia ezt a dataset felhasználva. A prezentációk - hírek szerint - kivétel nélkül mindegyike előfeldolgozást és SVD-s mátrix-faktorizációt (mátrix-felbontás) helyezte előtérbe. SVD=Singular Value Decomposition. Egyértelmű, mindig megejthető felbontás, O(n^3)-s műveletigénnyel. A módszerek kombinálása, szavaztatása is központi kérdés volt, a korreláltság és ortogonalitás összefüggésében.



Magyar URL-ek
=============


http://www.spss.hu/newsletter/2006nov.php
Komolyan gondoljuk, tényleg! Egy millió dollár erejéig. - Ezzel a kijelentéssel hírdette meg versenyét a Netflix, amely azzal foglalkozik, hogy az embereket összekapcsolja az általuk kedvelt mozi filmekkel. Erre fejlesztették ki a világ első intelligens mozi ajánló rendszerét, a Cinematch-t. A szoftver a korábbi filmek tetszése alapján előrejelzi, hogy mennyire fognak egy-egy új filmet kedvelni az egyes ügyfelek, és ez alapján kapnak az ügyfelek egyéni ízlésüknek megfelelő ajánlatokat. A Cinematch jelenleg is sikeresen üzemel, de mindenen lehet még javítani.

Vannak ugyanis még koncepciók, amelyeket a Cinematch még nem próbált ki. A kérdés, hogy van-e olyan eljárás, amely teljesítményben túlszárnyalja a jelenlegit, mert az üzletileg komoly előrelépés lehetne.

Ezért aztán kiírtak erre egy versenyt. A pályázó alkalmazásnak 10%-al kell jobban becsülnie a jelenleginél a megadott minta adatokon. Vélhetőleg ezt igen nehéz lesz elérni, de lehetségesnek tűnik. Lehet, hogy hónapokig tart, lehet hogy évekig, ezért az előre haladást is díjazzák: évi 50.000 dollárt kap az, aki az előző évi becslési pontosságot a legjobban túlteljesíti a következő évben.

Feltétel még, hogy a kész alkalmazás működési elvét a szerzők ismertessék, és elérhetővé tegyék a nyilvánosság számára. Érdekes problémák, érdekes üzleti fogás!



http://www.kfki.com/blog_8E210F31B2AC45668D7C83CB0FFFFB33.php?blogId=856%23a8143a21&year=&month=
Egy ilyen verseny most is folyik a világban: a Netflix Prize azt a feladatot adta meg, hogy tippeljük meg mennyire fog tetszeni ügyfeleinek a tőlük kivett DVD-film. Van egy megoldásuk, ha javít rajta bárki 10%-ot, az kap 1 millió dollárt. Tavaly ősszel indult a verseny, öt éve van rá a nemzetközi adatbányászati közösségnek.

Rengeteg a jelentkező, a megoldást ma már közel 8 százalákkal már megjavították. A cég - véleményem szerint - nagyon olcsón kap meg egy igen jó megoldást. Nem hiszem, hogy bármely kutatócsapart garanciálisan elvállalta volna ezt a projektet ezért a pénzért, illetve hogy az ő megoldásukat nem tudta volna felülmulni valaki más.

Ha a cég kifizetné mindannak az óradíját, aki versenyzik, nagyságrendekkel több pénzbe kerülne. A nyertes a pénz mellett elvisz mindent, a többiek valójában elbukják a témába fektetett energiájukat. A megszerzett tudás értéke is kétes számukra: számszerűen kimutatható, hogy hanyadikaka a ranglistán, van egy globális mérési érték arra vonatkozóan, hogy az ő tudása mennyire mély. Ennek ellenére sokan futnak neki a feladatnak, aminek az oka, hogy ez egy jó játék. Verseny a világgal, taktikázás, igazi vérbeli kihívás. Ez sokkal több tudóst tud megmozgatni, mintha meghírdettek volna az interneten egy csodálatos állást a Netflix fejlesztői csapatába.

A Goldcorp és a Netflix taktikája zseniális: amig én vagyok a leghíresebb verseny, hihetetlenül olcsón kapok nagyon jó eredményeket. Az igazi kérdés az, hogy az ilyen versenyek számának növekedésével mi az a pont, ahol már nem fogja megérni igy dolgozntatni. És hasonlóan, mennyi energiáját fogja felörölni a kutatói közösség ilyen versenyeken. Játékelméleti szempontból egy speciális csapdahelyzet van kibontakozóban, a közlegelők problematikája (5 tehént tud eltartani a rét, de ha az egész falu kiviszi a sajátját, akkor mind éhenhal, kérdés hogy ki vigyen ki tehenet és ki nem). Egyenlőre céges irányból fegyelmezettek a cégek, jelenleg csak 1-2 ilyen kezdeményezés van csak. Kutatói irányból már más a helyzet. Sokaknak már nem érdemes elindulni a versenyeken, mert nagyon kockázatot vállalnak, amit csak ideig óráig (néhány évig) fog ellensúlyozni a lelkesedés.



http://www.prog.hu/tarsalgo/59865/1+millio+dollaros+feladat/oldal/1.html
50 feletti hozzászólást megért nem érdektelen fórum
- Van aki szerint olyan mint a tőzsde, meglehetősen sztochasztikus. Ezért pesszimista (másokkal együtt), hogy lesz nagydíj-nyertes.
- Van fóruma is a netflixprize-nak. Ott olvasta valaki, hogy jópár ember nem tudott javítani az eredmenyén a dátumok felhasználásával.



SZAKÁCS BALÁZS BME-s hallgató adott be egy félévi feladatot BME-n a feladattal kapcsolatban. Sajnos a vonatkozó URL már nem él.
Ő három alapvető megközelítést sorol fel
1. Vannak felhasználók, akik hasonlóan ítélnek meg filmeket (SVD-vel bányászható például jól: 0.93-as RMSE)
2. Felhasználó egyetemistaként másképp ítéli meg a filmeket, mint felnöttként -> Felhasználó-history: 1.07 & 1.08 RMSE
3. Egy régi filmet másképp értékelnek a nézők amikor premier, mint jóval később -> Film-history: ezt kihagyta
A próbahalmazon a mindig legjobb érték választásával 0.74-et kapott (egyfajta elméleti határ). Egy speciális időpont alapú szavaztatás révén végül 0.92-ig jutott legvégül.