oktober 19, 2005

The Dynamics of Viral Marketing

Jurij Leskovec, Lada A. Adamic, Bernardo A. Huberman: The Dynamics of Viral Marketing (PDF, 39 sidor)

Abstract (min fetning)

We present an analysis of a person-to-person recommendation network, consisting of 4 million people who made 16 million recommendations on half a million products. We observed the propagation of recommendations and the cascade sizes, which can be explained by a stochastic dynamic model. We then established how the recommendation network grows over time and how effective it is from the viewpoint of the senders and receivers of recommendations. While on average recommendations are not very effective at inducing purchases and do not spread very far, there are product and pricing categories for which viral marketing seems to be very effective.


Saxat från texten (min fetning):

Our analysis focuses on the recommendation referral program run by a large retailer. The program rules were as follows. Each time a person purchases a book, music, or a movie he or she is given the option of sending emails recommending the item to friends. The first person to purchase the same item through a referral link in the email gets a 10% discount. When this happens the sender of the recommendation receives a 10% credit on their purchase.

This study is novel in that we are able, for the first time, to directly observe the effectiveness of person to person word of mouth advertising for hundreds of thousands of products. We can see what kind of product is more likely to be purchased as a result of this type of recommendation, as well as describe the size of the cascade that results from an initial purchase and subsequent recommendations.

Se även
Liknande undersökningar på HP Labs.

Posted by hakank at 08:50 EM Posted to Rekommendationssystem | Social Network Analysis/Complex Networks

juni 02, 2005

Artikel om rekommendationssystem i InternetWorld

I senaste Internetworld (Juni-numret, har inte sett artikeln på nätet ännu) finns en lång och intressant artikel om rekommendationssystem: Rätt köptips ökar försäljningen - Automatiska rekommendationer lyfter e-handeln (sid 38ff). Bl.a. intervjuas Malmöföretaget Avail Intelligence, utvecklare av ett sådant system som används av flera svenska e-butiker. Pasi Bauer diskuterar filmtipset.se och dess rekommendationssystem (som nämndes här). Det finns mycket annat matnyttigt att läsa i artikeln.

En kompletterande kommentar: Begreppet The Long Tail nämns och förklaras kortfattat, men man nämner så vitt jag kunde se inte att Chris Anderson (som myntade begreppet) har en blogg där många intressanta artiklar publiceras och som utgör stommen till en planerad bok med detta tema. (Se även "The Long Tail" och "long tail".)

I artikelns slutreferenser nämns två svenska bloggar som emellanåt skriver om rekommendationssystem: den utmärkta Henrik Torstenssons Weblog (googlesökning på 'rekommendationsystem' här) samt min egen blogg (hakank.blogg). En del av det som skrivits finns samlat i kategorin Rekommendationssystem.

Posted by hakank at 05:32 EM Posted to Rekommendationssystem | Comments (2)

maj 21, 2005

Mean Streets: en Malmö-affär med filmklassiker, independent, Hong Kong-filmer och annat

Min kollega Alex tipsade igår om en väldigt trevlig affär här i Malmö: Mean Streets (Djäknegatan 16) som säljer Hong Kong-filmer, andra asiatiska filmer, kulturklassiker, independent och säkert andra former av icke-main stream filmer.

För några år sedan fanns i Malmö en affär som hade mycket Hong Kong-filmer (och utgjorde grunden för min egen filmsamling och egentligen att intresset hölls uppe), men den slutade sedan att sälja sådana filmer. Det har varit en stor saknad efter en fysisk affär med denna inriktning.

Eftersom det endast var Kung Fu-filmer som intresserade mig igår är det bara dem som jag egentligen kan uttala mig om: Fantastiskt urval och en väldigt kunnig ägare.

Jag har alltså en del Hong Kong/Kung Fu-filmer redan (en delmängd finns listade här, nyare inköp inte inknappade), men det är mestadels lättåtkomliga saker som Jet Li, Jackie Chan etc. I affären fanns väldigt få av dessa utan endast sådant som jag letat efter länge. Så i går inhandlades följande klassiska Kung Fu-filmer (region 3-kodade):

Come Drink With Me (1966)
7 Grand Masters (1978)
Returns to the 36th Chamber (1980)
Legendary Weapons of China (1982)
Disciples of the 36th Chamber (1985)


Lite mer om affären och dess ägare, vars namn jag glömde fråga efter med låt oss kalla honom för "Mike" efter den T-shirt han hade på sig (som jag tror är sista delen av titeln på en av mig okänd känd film). Någon får gärna komplettera med korrekt namn på "Mike". Uppdatering: Nu har jag fått reda på att han heter Johan (via ett mailinglistemail som kom nyss). Alla tidigare förekomster av "Mike" har nu ändras till Johan i nedanstående text.

Mean Streets har funnits i ungefär en månad och det är ingen stor lokal med drivor av filmer, snarare känns det som om urvalet gjorts med största omsorg. Johan var väldigt trevlig, tillmötesgående och verkar mycket kunnig. Såvitt jag kunde bedöma har han stenkoll på genren, vilka filmer som är efterföljare till de som jag har, vilka som är klassiker, vilka som är värda att se och varför etc. Perfekt alltså!

Tyvärr finns det inte någon webbsida (borde kanske föreslå en blogg), däremot en mailinglista där nya tillskott kommer att presenteras. Be om att få bli prenumerant.

Jag rekommenderar verkligen ett besök till Mean Streets även om det inte är Hong Kong-filmer ni är ute efter.

P.S. Jag har inte fått någon som helst ersättning (finansiell eller annan, eller något explicit eller implicit löfte om en framtida sådan) för att skriva denna blogganteckning utan tycker helt enkelt att det är väldigt skoj att en sådan affär som Mean Streets finns i centrala Malmö.


När jag gick därifrån (dvs lyckades slita mig) efter nästan en timme funderade jag på några saker.

Detta är urtypen för ett rekommendationsystem: En expert - Johan - som vet väldigt mycket om filmerna, vilka filmer som på olika sätt är lika andra (i en mycket finfördelad och flerdimensionell klassifikation) etc. Det är något som datorbaserade system strävar efter och endast i bästa fall lyckas uppnå. Det som saknas initialt i sådana affärer är kunskapen om kunderna, men om jag nu blir den stamkund som jag hoppas så kanske Johan kommer ihåg mig, min filmsmak och de filmer som inköpts och kan efterhand ge mig mer direkta tips med ledning av vad jag tycker om filmerna. För övrigt är det egentligen samma problem i rekommendationssystemen: Man måste befolka databasen med sina prefereranser, ju fler desto bättre, vilket kan ta rätt lång tid.

Nackdelen med fysiska affärer är naturligtvis att de endast finns på ett ställe och det är bara en kund i taget som kan få rekommendationer (till skillnad mot t.ex. webbaserade system som väldigt många kan utnyttja samtidigt). Även om jag är mycket fascinerad av rekommendationssystem föredrar jag - och betalar eventuellt lite extra för - denna typ manuella rekommendationer.

Man kan bara hoppas att Johan kommer att ha tid att prata med kunderna på detta sätt i fortsättningen också.


Den andra saken är följande. Jag hyser ingen som helst tveksamhet om att "Mike" är mycket kunnig inom sitt område. En principiell fråga är hur man som lekman/amatör inom ett område egentligen kan bedöma om en expert verkligen är en expert? Därav garderingen med "så vitt jag kunde bedöma" ovan. Måste man inte själv vara expert för detta? Speciellt i dessa fall där det inte finns någon information att hämta via webben eller personer vars omdöme man litar på (no offence, Alex!). Det enda man kan gå efter är ju vad man själv vet och har erfarenhet av. Även om jag inte gjorde det så medvetet som det kan låta, så testade jag lite med min ganska ringa (och lite ringrostiga) kunskap i ämnet, och det var inga som helst problem för Johan att besvara frågorna och passningarna.

Posted by hakank at 10:03 EM Posted to Filmer | Rekommendationssystem | Comments (3)

maj 07, 2005

Economist om the long tail och rekommendationssystem

Economist om the long tail: Profiting from obscurity. Så här skrivs om kopplingen till rekommendationssystem (collaborative filtering):

But how can people find content they want when it is buried far down the tail? Already, a number of mechanisms have emerged, based around user recommendations. Perhaps the best known is “collaborative filtering”, in which purchase histories are analysed to work out what else is likely to interest the buyer of a particular product (“Customers who bought this item also bought...”, as Amazon puts it). This approach allows users to navigate from hits that they know they like to more obscure titles further down the tail. “You need not just variety, but information about variety,” says Mr Anderson. “A long tail without good filters is just noise.” Many people find even the amount of choice on supermarket shelves overwhelming—in large part because there is so little information on which to base a rational choice. But a mere 27 flavours of jam is nothing compared with millions of music tracks or thousands of movies, so providing filters to help people find what they want is vital.


Posted by hakank at 07:21 EM Posted to Rekommendationssystem | Spelteori och ekonomi

mars 28, 2005

Economist om collaborative filtering (rekommendationssystem)

Economistartikeln United we find (10 Mars 2005) innehåller en introduktion av collaborative filtering och beskriver även mer modern forskning inom området.

For many people, technology now plays an increasing role in making such choices and navigating through large numbers of alternatives. But while this might sound like a job for an internet search engine, keyword-based search engines (such as Google) have a fundamental constraint: they can only help you find something if you already have an idea of what it is. Two people's idea of “good music” may differ substantially, but Google would return the same results to both of them. To find things you might like, but are not already familiar with, requires a different technology, known as “collaborative filtering”.

This increasingly pervasive technology looks for patterns in people's likes and dislikes, and uses those patterns to help people find things they did not know they were looking for. Computer scientists term this task, in a welcome respite from jargon, “find good things”. Collaborative filtering also has the power to do the converse, “keep bad things away”, for instance by filtering unsolicited commercial e-mail messages, or spam.

Artikeln förklarar sedan kortfattat skillnaden mellan de två teknikerna "user-user" och "item-item", liksom hur TiVo räknar ut sina rekommendationer som är annorlunda jämfört med Amazons serverkalkyler.


De mer intressanta sakerna kommer sedan: hur man kan göra rekommendationssystem säkra för intrång i den personliga integriteten och säkra för manipulering.

* John Canny och hans förslag till rekommendationer baserade på krypterade (anonyma) preferenser.
* Mike O'Mahoney gjorde tillsammans med Neil Hurley, Nicholas Kushmerick och Guénolé Silvestre en analys av sådana systems robusthet: Collaborative Recommendation: A Robustness Analysis
* Nolan Miller har skissat på en lösning av manipulationer genom en probabilistisk analys av ovanliga händelser i systemet.
* Jonathan Herlocker som spekulerar i om det finns en gräns i hur bra rekommendationer kan göras med collaborative filtering-tekniker: Dr Herlocker speculates that this might be evidence for a fundamental limit to the accuracy of recommendation systems based on collaborative filtering. There is no point in making suggestions any more finely tuned than the variations in an individual's own opinions. Dr Herlocker may well be correct, or the technology may just have further to go.


Artikeln avslutas med en hyllning till collaborative filtering jämfört med traditionella sökmotorer och använder den allt mer vanliga crowd vs. solitary-metaforen (cf. artikelns rubrik: "United we find"). Även om jag i stort sett håller med i hyllningen så tycker jag nog att författaren tar lite väl lätt på skillnanden i förutsättningar mellan de två olika metoderna att hitta information: För att kunna få bra rekommendationer i ett rekommendationssystem krävs ett stort förarbete att berätta om sina preferenser för systemet, antingen det är frågan om att betygssätta filmer/skivor/böcker, ha köpt dem via systemet eller klickat runt i sajten ordentligt. När/om det blir möjligt att kunna spara och förflytta gjorda preferenser mellan olika rekommendationssystem blir skillnaden naturligtvis mindre.

But the value of collaborative filtering has, in any case, already been established. It helps people find things they might otherwise miss, and helps online retailers increase sales through cross-selling. Where the user of a search engine is on a solitary quest, the user of a collaborative-filtering system is part of a crowd. Search, and you search alone; ramble from one recommendation to another, and you may feel a curious kinship with the like-minded individuals whose opinions influence your own—and who are, in turn, influenced by your opinions.


Se även
Lite om rekommendationssystem (recommender systems, collaborative filtering)

Posted by hakank at 08:03 FM Posted to Rekommendationssystem | Comments (4)

januari 29, 2005

Lite om rekommendationssystem (recommender systems, collaborative filtering)

För ett tag sedan (och troligen främst via Henrik Torstenssons Filmtipset - jag är imponerad!) fick jag ett nyuppväckt intresse för rekommendationssystem (recommender systems, collaborative filtering). Bl.a. genom att tillbringa ett antal timmar med just Filmtipset som har flera olika varianter av rekommendationer (se nedan för några exempel). Om du är intresserad av film rekommenderas ett besök. För att få bra rekommendationer krävs att man registrerar sig och betygsätter ett gäng filmer (troligen rätt många).

Under denna tid satt jag och betygsatte (så ärligt som möjligt) knappt 1000 filmer, till viss del just för att testa hur bra rekommendationerna är. Tilläggas kan att jag är inte alls lika betygsaktiv där nu som då men går gärna in och kollar betygen och kommentarerna för olika filmer som är titt-aktuella.

Funktionen att se vilka personer som är mest lika ens egen betygssättning finns naturligtivs liksom vilka filmer som är lika en specifik film, och de funkade ungefär som förväntat men jag blev inte speciellt överraskad. Det finns även andra finesser. Speciellt tyckte jag om "X:s overrated/underrated" som visar de filmer som en person (X) har betygssatt och som är mest över eller under genomsnittsbetyget. Att det är enkelt att göra egna filmlistor är också en bra sak.

Denna fascination gjorde naturligtvis att jag kikade vidare på (och läste om en del) litteratur kring slika system. Nedan är några av dessa. Det fanns även en halvbakad plan på att skriva ett eget litet bloggrekommendationssystem men andra projekt - såväl privata som icke-privata - fick högre prioritet.

Här är alltså lite att läsa om sådana system:

Greg Linden, Brent Smith, Jeremy York Amazon.com Recommendations - Item-to-item Collaborative Filtering där man förklarar Amazons rekommenationsmetod och jämför med andra varianter, t.ex. user-to-user. Man kommer där fram till att Amazons metod är bättre än de andra. (Inte helt oväntat; samtliga tre författarna arbetar på Amazon.)

Badrul Sarwar, George Karypis, Joseph Konstan, John Riedl: Item-based Collaborative Filtering Recommendation Algorithms är en mer teknisk genomgång av olika typer av algoritmer.

Shyong (Tony) K. Lam, John Riedl (GroupLens-projektet) Shilling Recommender Systems for Fun and Profit som diskuterar hur man avslöja försök till fusk och penetration (shilling) i rekommendationssystem.

Daniel Lemire, Sean McGrath: Implementing a Rating-Based Item-to-Item Recommender System in PHP/SQL som innehåller mer praktiska saker för att skapa ett rekommendationssystem inklusive källkod i PHP och SQL (precis som titeln antyder). Den är en praktisk kommentar till implementationen av metoden beskriven i Daniel Lemire, Anna Maclachlan: Slope One Predictors for Online Rating-Based Collaborative Filtering. Systemet som implementerades är inDiscover (som jag inte kollat in).

Upendra Shardanand, Pattie Maes: Social Information Filtering: Algorithms for Automating "Word of Mouth". Klassiker.


Jag har försökt hitta någon bra modern bok i ämnet, men har inte funnit någon som passar. Den närmaste är nog Word of Mouse: The Marketing Power of Collaborative Filtering av Eric Vrooman, John Riedl, Joseph Konstan, men är ej beställd.


Ett system att kika vidare på är Collaborative Filtering Engine (CoFE) som är en open source-implementation skriven i Java och använder MySQL-databas. Det finns två exempel som man kan köra, bl.a. data från MovieLens-projektet. API-dokumentationen finns här.

Till slut ett tips om en ny Yahoo!-grupp: RecommenderSystems.


Se även
Grouplensprojektets publications
James Thorntons Collaborative Filtering Research Papers


Några tidigare anteckningar i ämnet:
InfoVis: Collaborative Filtering
Farliga rekommenderare.

Posted by hakank at 12:14 FM Posted to Rekommendationssystem

november 02, 2004

InfoVis: Collaborative Filtering

InfoVis.net Collaborative Filtering:
Collaborative filtering is increasingly present as an integral part of commercial web sites. "Memory based" algorithms are the most simple to implement, yet the most effective when recommending products and predicting preferences..


Se även följande samlingssidor:
Collaborative Filtering
Lyle Ungar: Recommender Systems
Principia Cybernetica Web: Collaborative Filtering

samt Farliga rekommenderare.

Posted by hakank at 10:35 EM Posted to Machine learning/data mining | Rekommendationssystem

juli 10, 2003

Farliga rekommenderare

Jag är en sucker för "rekommenderare" (recommender systems), och använder ofta t.ex. Amazons bokrekommenderare, både den generella "Customers who bought this item (se t.ex. en av mina favoritböcker i ämnet data mining), och den imponerande personliga rekommenderaren (som dock kräver inloggning). Även bokus har ett rekommenderarsystem, men det är inte riktigt lika imponerande som Amazons.


För ett tag sedan rapporterades om en undersökning,
Recommenders can skew results , om tillförlitligheten i liknande system och hur de kan påverka användarna av dem. Några citat:

Displaying a prediction introduces bias, said Joseph Konstan, an associate professor of computer science and engineering at the University of Minnesota. "Lying by [skewing rankings] higher or lower... biases the subsequent rating in that direction," he said. "Even the 'correct' rating led people to select that value more often."
....
The distortion this chain of events induces may influence consumer buying in the short-term, but adversely affects long-term consumer trust in the system, said Konstan. "While a system can get away with a small degree of lying... in the long run dishonesty erodes trust and satisfaction," he said.

Se även Good Ratings Gone Bad.

Ett annat exempel hur rekommenderare påverkar ens val, är Dived we Stand??? där det görs en liten undersökning om köptendensen av politiska böcker: It appears that echo chambers have emerged that repeat a consistent message within each cluster. Ron Burt, a leading network expert, explains that a tightly closed network "amplifies predispositions, creating a structural arthritis in which people cannot learn what they do not already know"[PDF...]. With no direct bridges between the clusters, these divisions are unlikely to change any time soon.

För mer om rekommenderare / collaborative filtering, se t.ex.:

Posted by hakank at 09:43 FM Posted to Machine learning/data mining | Rekommendationssystem