Povej mi kaj gledaš in ti povem kdo si

Povsod same kartice ugodnosti. Povsod sama priporočanja. Facebook priporoča prijatelje. Twitter priporoča tebi zanimive čivčkače. Amazon priporoča knjige. IMDB pa filme. A kaj je ozadju? Priporočilni sistem, med drugim.

Spominjam se dni, ko smo v srednji šoli pri pokojnem profesorju Marjanu Kozjeku iskali različne iskalne nize. Seveda, uporabljali smo strica Googla. Veseli smo bili, ko smo se naučili pravilno iskati – z uporabo nekaterih trikov. Zvečer smo se pogosto skupaj učili – takrat še preko MSN-ja. Če sošolec/sošolka nista česa vedela, si samo povedal iskane besede, ki jih morata vnesti v iskalno okno strica Googla. Nato si še povedal, v kateri vrstici je pravilna povezava, in vsi smo gledali enako gradivo. Sedaj pa ni več tako.

Splet se je spremenil. Spremenili so se tudi uporabniki, ki želijo najti informacije takoj – tukaj in sedaj. Če se pravi podatek ne nahaja v prvih treh iskalnih rezultatih, potem že obupamo. Podobno je pri drugih uporabniških izkušnjah. Zato se splet spreminja in postaja vedno bolj pameten. No, navidezno pameten.

Dijakom “pametnost” ali pa še bolje “premetenost” spletnih iskalnikov pojasnim s primerom. V iskalno okno vnesite izraz “Java”. Računalničarju bo iskalnik skoraj zagotovo ponudil prve povezave, ki so povezane z računalniškim jezikom Java. Nekomu drugemu, ki ga pa bolj zanimajo teme s področja turizma, geografije in morda zgodovine, pa mu bo ponudil povezave, ki vodijo do indonezijskega otoka Java.  Seveda v ozadju iskalnikov so drugačni algoritmi (postopki), kot so na primer pri eBayu, Amazonu, IMDB-ju, Netflixu ipd.

V tem sestavku se bom potrudil preprosto razložiti, kako delujejo priporočanja. Če je morda kaj nerazumljivo, le napišite in bom še kaj razložil. Na vse zadnje sem delal doktorat s tega področja in zato so mi nekatere stvari samoumevne – vsekakor pa je izziv korektno in preprosto razložiti. Tako da, le pogumno z vprašanji/komentarji.

Zgoraj omenjene nakupovalne strani temeljijo na sistemih priporočanja – na sistemih, ki uporabnikom priporočajo objekte. Priporočajo lahko prijatelje, hrano, artikle, oblačila, filme, glasbo in druge stvari.  Sistemi spremljajo uporabnika in s pomočjo njegovih vedenjskih vzorcev oblikujejo profil, ki ga nato uporabijo za nadaljnjo priporočanje. Več kot imamo podatkov, bolj poznamo uporabnika. V tem sestavku se bom osredotočil na spletne trgovine – a prave trgovine niso čisto nič drugačne – zato pa so kartice zvestobe. Vsi želijo poznati svoje uporabnike.

Slovenski rek pravi: “Podobni ptiči skupaj letijo” ali pa “Gliha v kup štriha”.  🙂 Ti dve ljudski modrosti sta še kako pomembni v priporočilnih sistemih. Zakaj? Podobni uporabniki imajo podobne uporabniške vedenjske vzorce. Zato je najlažje, če našemu uporabniku poiščemo njemu podobne uporabnike. Najlažji postopek je, da preštejemo, koliko in katere artikle so podobno ocenili oz. jih kupili. Strokovno temu rečemo priporočanje s sodelovanjem.

En izmed najbolj razširjenih algoritmov, ki sodi v skupino priporočanja s sodelovanjem, je matrična faktorizacija. Tisti, ki ste hodili v srednjo šolo 10 in več let nazaj, potem vam je pojem matrike znan pojem. Ostali pa ste/boste srečali pojem matrike na kakšni naravoslovni, matematični, fizikalni ali računalniški fakulteti. Pa morda še kje. Kot že pojem matrične faktorizacije pove – operiramo z matrikami. Preden se algoritem zažene, moramo realno situacijo uporabnikov in objektov predstaviti z matriko.

matrika_uporabnikov

Zgornja slika prikazuje primer štirih uporabnikov, ki so si ogledali nekatere filme in jih ocenili. Poglejmo si primer uporabnika z imenom Bine. Prvi del sage Gospodar prstanov (LOTR1) je ocenil z oceno 1, serijo Migthy Morphin Power Rangers s 5, serije Igra prestolov ni ocenil, prvi del sage Harry Potter je ocenil s 5 in 50 odtenkov sive ocenil z 1. Zakaj je bil Cene navdušen nad slednjim filmom, nas v tem trenutku ne zanima. 🙂 🙂

V sistem je prijavljen uporabnik Domen, ki je ocenil le dva filma/seriji: Migthy Morphin Power Rangers s 5 in 50 odtenkov sive ocenil z 1. Za računalnik (ker je neumen) so vsi uporabniki enaki. Če pa mi pogledamo matriko uporabnikov in filmov, pa vidimo, da je podobno ocenil tudi Bine. Torej bi moral biti tudi Domen navdušen na Harryjem Potterjem in kamnom modrosti. Pa poglejmo, kaj pravi matrična faktorizacija.

Zelo preprosto povedano, matrična faktorizacija je postopek, ki začetno matriko (zgornjo matriko uporabnikov in filmov) razbije na dve manjši matriki U in O, kjer je prva matrika matrika uporabnikov (vsaka vrstica predstavlja karakteristike uporabnika, ki jih tvori vektor predstavljen kot vrstica) in matrika objektov (vsak stolpec predstavlja karakteristike objekta, ki jih tvori vektor predstavljen kot stolpec). Rezultat matrične faktorizacije sta torej dve matriki – njun produkt pa je matrika, ki je podobna prvotni matriki – a nekaj je drugače. Tam, kjer so prazne vrednosti, imamo sedaj napovedane/priporočene vrednosti.

Poglejmo sedaj, kakšna oceno sistem predvidi za našega Domna in prvi del Harryja Potterja. Skalarno pomnožimo Domnov vektor in vektor želenega filma. Dobimo vrednost 4.56, kar pomeni, da je tudi matrična faktorizacija podobno sklepala, kot smo mi predvideli. Domnu bi torej morali priporočiti prvi del sage o Harryju Potterju. Podobno lahko priporočamo tudi drugim uporabnikom. Z vsako dodatno oceno, ki jo uporabnik poda, sistem natančneje pozna uporabnika in lahko uspešneje priporoči njemu zanimive filme.

Zgornji postopek je zelo zelo laično in preprosto napisan. Algoritmi so v resnici nekoliko bolj kompleksni in tudi časovno potratni. Pri manjših podatkovnih bazah dobimo povratno informacijo v hipu. Pri ogromni količini podatkov pa se tudi načakamo.

Podoben scenarij bi lahko prenesli na scenarij spletnih nakupov, gledanja novic, dodajanja prijateljev, všečkanja objav in slik. Marsikaj se že uporablja. Predstavil sem le en algoritem priporočanja. Obstaja pa še veliko drugih podobnih pristopov, ki jih uporabljajo spletne trgovine – vse z namenom, da poznajo svoje uporabnike in jim sugerirajo najbolj ustrezne artikle. S priporočili nam lahko naredijo uslugo – lahko pa nas tudi prinesejo okoli.

Verjetno ste že opazili na spletu, kako vas zasipajo s številnimi reklamami o artiklih, ki jih tudi sicer iščete po spletu ali pa ste komu preko sporočil omenili, da nekaj rabite. Res je – Google, Facebook in njima podobni strici beležijo, kaj delamo, kaj pišemo in kaj gledamo na spletu. Vsi ti podatki jim povedo, kdo je za računalnikom.  Pazite, kaj delate na spletu – veliki bratje nas opazujejo.

Literatura za nadaljnje branje:

  • Linden, G., Smith, B., & York, J. (2003). Amazon. com recommendations: Item-to-item collaborative filtering. IEEE Internet computing, 7(1), 76-80.
  • Koren, Y., Bell, R., & Volinsky, C. (2009). Matrix factorization techniques for recommender systems.Computer, 42(8), 30-37.
  • Asanov, D. (2011). Algorithms and methods in recommender systems. Berlin Institute of Technology, Berlin, Germany.
  • Ocepek, U., Rugelj, J., & Bosnić, Z. (2015). Improving matrix factorization recommendations for examples in cold start. Expert Systems with Applications, 42(19), 6784-6794.

 

2 comments on “Povej mi kaj gledaš in ti povem kdo siAdd yours →

  1. Odločili smo se da opisan sistem NMF implementiramo na spletni strani, saj želimo privabiti čim večje število oboževalcev fimov. Da bi ljudlje izvedeli za naš super sistem, damo v lokalni časopis oglas, da prvega uporabnika čaka krasno darilo. Prva oseba, ki oglas opazi je Erdogan, ki sedi v gostilni in pije mrzlo pivo. Hitro do konca spije pivo, se prijavi na našo spletno stran in oceni filme. Ker je Erdogan alkoholik, in se bori z depresijo, se to pozna tudi na njegovih ocenah.
    Vsem filmom da oceno 1, razen filmu 50 odtenkov sive, ki pa mu je ob gledanju le delno pogrel njegovo depresivno srce. Serije Mighty Morphin Power Rangers Erdogan ni ocenil, saj ni več otrok in takih stvari on ne gleda.
    Iz ocen je razvidno da Erdogan nima okusa za filme, ter da je njegovo povprečje ocen globoko pod povprečjem drugih filmov.
    Druga težava je nastala, ko je uporabnik kliknil gumb “Predlagaj film”. Izpisala se mu je napaka, da za vsakega novega uporabnika pa že ne bomo izvajali matrične faktorizacije, saj da je to predolg postopek. No mogoče za Erdogana še, saj je le eden izmed prvih uporabnikov, vendar naslednji uporabnik ne bo imel te sreče.
    Naslednji dan si Erdogan ogleda film 2001: A Space Odyssey, saj vsi vemo, da je to najboljši film. Erdogan je med filmom obiskal stranišče, saj je pred predstavo spil preveč piva in zamudil najboljši del filma, kjer se AI obrne proti človeku in ga poskuša pokončati. Ker filma ni razumel, se je odločil da tem filmu da oceno 1. Po prijavi na spletno stran je ugotovil da tega filma sploh ni na seznamu za ocenjevanje. Od razočaranja je odšel v najbližjo gostilno in tam ohladil grlo z vrčem piva.
    Vprašanja:
    Ali je potrebno ocene pred uporabo normalizirati glede na druge uporabnike?
    Kako se dodaja uporabnike, da ni potrebno vedno izvajati MF. Ali obstaja kakšna metoda podobna KNN, ki najde najbolj podobnega že izračunanega uporabnika in predlaga filme glede na njega? Oziroma ali obstaja kak matematični trik, ki lahko za novega uporabnika izračuna/hevristično oceni le njegove vrednosti v matriki U
    Kako dodati nove filme in jih predlagati, če imajo še majhno število ocen?

  2. Gašper, hvala za vprašanje in domiseln opis problema. 🙂 Me veseli, da me spremljajo tudi bivši dijaki. 🙂
    Drži, če imaš “posebnega” uporabnika, potem je njemu težje priporočati filme, če nimaš notri že kakšnega njemu podobnega uporabnika. Še posebno pri uporabi KNN. Sicer matrične faktorizacije v osnovi nimajo KNN-ja – slednji se uporablja pri bolj preprostih priporočilih. Lahko pa KNN uporabiš, da kakšne ocene priporočiš/vstaviš v začetno matriko – pred začetkom matrične faktorizacije. Nekaj podobnega sem delal v doktoratu – delovno različico sem ti poslal na FB.

    1) Najprej je potrebno pogledati, kakšno matrično faktorizacijo boš uporabil. Če imaš velik razpon ocen – nekateri imajo ocenjevanje z realnimi ocenami od -10 do 10, potem je priporočljiva normalizacija. Lahko tudi pomaga, da algoritem hitreje poišče lokalni minimum oz. v najboljšem primeru globalni minimum; ker se posledično lahko zmanjša število iteracij. Osnovna različica NMF namreč dela z gradientnim spustom – razen če uporabiš drug algoritem MF. Jih je precej – so tudi spisani v Pythonu. Priporočam knjižnico nimfa kolegice Žitnik, ki je še posebno specializirana na področju matrifčnih faktorizcij: http://nimfa.biolab.si/

    2) MF se vedno izvede nad celo matriko – ne razumem čisto, kako bi dodal novega uporabnika. Če dodaš novega uporabnika, potem je njegov vektor prazen, ker še ni nič ocenil. Enako je pri novem filmu/objektu. Če imaš vsaj 1-3 ocene, pa lahko uporabiš poseben postopek za reševanje problema “hladni zagon” (angl. “cold start”). V moji disertaciji sem predlagal in testiral nekaj pristopov. Je pa še mnogo neraziskanega, ker smo z disertacijo odprli povsem novo področje – vstavljanja manjkajočih ocen za potrebe MF-ja. Je pa res, da se lahko sklicujemo na faktor unikatnosti uporabnika – potem težko najdeš nekoga, ki mu je povsem podoben (podobno ocenjuje).

    3) Raziskovalci so problem hladnega zagona (problem novega uporabnika ali problem novega objekta/filma) reševali tudi tako, da so objekt takoj ponudili uporabniku, da ga je ocenil – tako so pridobili nekaj začetnih ocen, kar pa ni nujno, da je koristno/smiselno. Lahko nastane problem popularnega objekta – vsi mu dajejo velike ocene in posledično bo tak film priporočen vsakomur, četudi mu ne bo v resnici všeč. Sistem se bo popravil šele, ko bo ocena filma uravnotežena – pridobila heterogene ocene. Najboljši način je, da se uporabijo meta-podatki. Torej da izdelaš uporabnikov profil ali profil objekta, kjer imaš njihove karakteristike. Tako lahko filme primerjaš med seboj glede na uporabnikove ocene ali pa glede na te karakteristike filmov (žanr, igralci, glasba, režiser, format itd.) Vedno več se združuje podatke in vedno več stvari se upošteva pri priporočanju, ker je cold-start še vedno problem v svetu priporočanja.

    Če boš/boste pri oblikovanju lastnega sistema uporabili MF, svetujem, da testirate na velikih množicah. Nekatere MF (NMF) so zelo počasne, še posebno če so implementirane z gradientnim spustom – kompleksnost ene iteracije je O(n^2). Govorim za osnovno različico. Tako da je dobro testirati več različnih različic NMF – še bolje pa, da poskusite tudi druge MF-je, da vidite, kako se obnaša na velikih podatkih. Upam, da sem odgovoril na vprašanja – sicer pa kar vprašaj. 🙂

Dodaj odgovor

Vaš e-naslov ne bo objavljen. * označuje zahtevana polja

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.
Cookies settings
Accept
Privacy & Cookie policy
Privacy & Cookies policy
Cookie name Active

Privacy Policy

What information do we collect?

We collect information from you when you register on our site or place an order. When ordering or registering on our site, as appropriate, you may be asked to enter your: name, e-mail address or mailing address.

What do we use your information for?

Any of the information we collect from you may be used in one of the following ways: To personalize your experience (your information helps us to better respond to your individual needs) To improve our website (we continually strive to improve our website offerings based on the information and feedback we receive from you) To improve customer service (your information helps us to more effectively respond to your customer service requests and support needs) To process transactions Your information, whether public or private, will not be sold, exchanged, transferred, or given to any other company for any reason whatsoever, without your consent, other than for the express purpose of delivering the purchased product or service requested. To administer a contest, promotion, survey or other site feature To send periodic emails The email address you provide for order processing, will only be used to send you information and updates pertaining to your order.

How do we protect your information?

We implement a variety of security measures to maintain the safety of your personal information when you place an order or enter, submit, or access your personal information. We offer the use of a secure server. All supplied sensitive/credit information is transmitted via Secure Socket Layer (SSL) technology and then encrypted into our Payment gateway providers database only to be accessible by those authorized with special access rights to such systems, and are required to?keep the information confidential. After a transaction, your private information (credit cards, social security numbers, financials, etc.) will not be kept on file for more than 60 days.

Do we use cookies?

Yes (Cookies are small files that a site or its service provider transfers to your computers hard drive through your Web browser (if you allow) that enables the sites or service providers systems to recognize your browser and capture and remember certain information We use cookies to help us remember and process the items in your shopping cart, understand and save your preferences for future visits, keep track of advertisements and compile aggregate data about site traffic and site interaction so that we can offer better site experiences and tools in the future. We may contract with third-party service providers to assist us in better understanding our site visitors. These service providers are not permitted to use the information collected on our behalf except to help us conduct and improve our business. If you prefer, you can choose to have your computer warn you each time a cookie is being sent, or you can choose to turn off all cookies via your browser settings. Like most websites, if you turn your cookies off, some of our services may not function properly. However, you can still place orders by contacting customer service. Google Analytics We use Google Analytics on our sites for anonymous reporting of site usage and for advertising on the site. If you would like to opt-out of Google Analytics monitoring your behaviour on our sites please use this link (https://tools.google.com/dlpage/gaoptout/)

Do we disclose any information to outside parties?

We do not sell, trade, or otherwise transfer to outside parties your personally identifiable information. This does not include trusted third parties who assist us in operating our website, conducting our business, or servicing you, so long as those parties agree to keep this information confidential. We may also release your information when we believe release is appropriate to comply with the law, enforce our site policies, or protect ours or others rights, property, or safety. However, non-personally identifiable visitor information may be provided to other parties for marketing, advertising, or other uses.

Registration

The minimum information we need to register you is your name, email address and a password. We will ask you more questions for different services, including sales promotions. Unless we say otherwise, you have to answer all the registration questions. We may also ask some other, voluntary questions during registration for certain services (for example, professional networks) so we can gain a clearer understanding of who you are. This also allows us to personalise services for you. To assist us in our marketing, in addition to the data that you provide to us if you register, we may also obtain data from trusted third parties to help us understand what you might be interested in. This ‘profiling’ information is produced from a variety of sources, including publicly available data (such as the electoral roll) or from sources such as surveys and polls where you have given your permission for your data to be shared. You can choose not to have such data shared with the Guardian from these sources by logging into your account and changing the settings in the privacy section. After you have registered, and with your permission, we may send you emails we think may interest you. Newsletters may be personalised based on what you have been reading on theguardian.com. At any time you can decide not to receive these emails and will be able to ‘unsubscribe’. Logging in using social networking credentials If you log-in to our sites using a Facebook log-in, you are granting permission to Facebook to share your user details with us. This will include your name, email address, date of birth and location which will then be used to form a Guardian identity. You can also use your picture from Facebook as part of your profile. This will also allow us and Facebook to share your, networks, user ID and any other information you choose to share according to your Facebook account settings. If you remove the Guardian app from your Facebook settings, we will no longer have access to this information. If you log-in to our sites using a Google log-in, you grant permission to Google to share your user details with us. This will include your name, email address, date of birth, sex and location which we will then use to form a Guardian identity. You may use your picture from Google as part of your profile. This also allows us to share your networks, user ID and any other information you choose to share according to your Google account settings. If you remove the Guardian from your Google settings, we will no longer have access to this information. If you log-in to our sites using a twitter log-in, we receive your avatar (the small picture that appears next to your tweets) and twitter username.

Children’s Online Privacy Protection Act Compliance

We are in compliance with the requirements of COPPA (Childrens Online Privacy Protection Act), we do not collect any information from anyone under 13 years of age. Our website, products and services are all directed to people who are at least 13 years old or older.

Updating your personal information

We offer a ‘My details’ page (also known as Dashboard), where you can update your personal information at any time, and change your marketing preferences. You can get to this page from most pages on the site – simply click on the ‘My details’ link at the top of the screen when you are signed in.

Online Privacy Policy Only

This online privacy policy applies only to information collected through our website and not to information collected offline.

Your Consent

By using our site, you consent to our privacy policy.

Changes to our Privacy Policy

If we decide to change our privacy policy, we will post those changes on this page.
Save settings
Cookies settings