Archives par mot-clé : Big data

Les machines du goût : comment ça marche ?

Capture d’écran 2015-03-30 à 10.18.32

Voici la référence à un blog très autorisé, son auteur n’étant autre que Brian Whitman, co-fondateur de l’API Echo Nest et aujourd’hui music scientist chez Spotify. Dans l’article présenté ci-dessous, on trouvera une description très précise des différents systèmes de recommandation et de leurs logiques internes.

How music recommendation works — and doesn’t work (http://notes.variogr.am/post/37675885491/how-music-recommendation-works-and-doesnt-work)

When you see an automated music recommendation do you assume that some stupid computer program was trying to trick you into something? It’s often what it feels like – with what little context you get with a suggestion on top of the postmodern insanity of a computer understanding how should you feel about music – and of course sometimes you actually are being tricked.

Amazons recommendations for Abbey RoadAmazon’s recommendations for Abbey Road

No one is just learning that if they like a Beatles album, they may also like five others. Amazon is not optimizing for the noble work of raising independent artists’ profiles to the public, and they’re definitely not optimizing for a good musical experience. They’re statistically optimizing to make more money, to sell you more things. Luckily this is the fruit fly of music recommendation, the late night infomercial quality of a music discovery experience that also might dry your lettuce if you spin it fast enough. And I doubt Amazon would ever claim otherwise.

The rest of the field has gotten pretty far since then and we’ve now got tons of ways to discover music using actual qualities of the music or social cues of what your friends are listening to. But I still hate seeing examples like the above. I hate thinking there are forces at work in music discovery that don’t have listeners’ best interests at heart and I want to make them better. I want to walk through all the ways music recommenders work or don’t, and concentrate of course on the one I know best – The Echo Nest’s – which you’re probably using even if you don’t already know it. And most importantly, I want to talk about what we can do next.

Before I get into it, a brief history of who I am: I’ve been working on music recommenders and music retrieval since 1999, academically and in industry. In 2005 I started The Echo Nest with my co-founder Tristan. We power most online music services’ discovery using a very interesting series of algorithms that is sort of the Voltron-figure of our two dissertations and the hard work of our 50 employees in Boston, SF, NYC and London. And we’ve been on a bit of a tear – just in the past year alone we’ve announced that we’re powering music discovery features for eMusic, Twitter, EMI, iHeartRadio, Rdio, Spotify, VEVO and Nokia – with some new heavy hitters yet announced – to add to our existing customer base that includes MTV, MOG, and the BBC. And through our API we have tens of thousands of developers making independent apps like Discovr, KCRW, Muzine, Raditaz, Swarm, SpotON and hundreds more.

We’ve been a quiet company for a while and with all this great news comes a lot of new confusion about what we do and how it compares to other technologies. Journalists like to pin us as the “machine” approach to understanding music next to the “human” of our nearest corollary (not competitor) in the space – Pandora. This is somewhat unfair and belies the complexity of the problem. Yes, we use computer programs to help manage the mountains of music data, but so does everyone, and the way we get and use that data is just as human as anything else out there.

I’ll go into technologies like collaborative filtering, automatic content based recommendation, and manual approaches used by Pandora or All Music Guide (Rovi). I’ll show that no matter what the computational approach ends up being, the source data – how it knows about music – is the most important asset in creating a reliable useful music discovery service.

What is recommendation? What is it good for?

Musicians are competing for an audience among millions of others trying just as hard. And it’s not the listener’s fault if they miss out on something that will change their lives – these days, anyone can gain access to a library of over 15 million songs on demand for free. To a musician turned computer scientist (as I and so many of my colleagues are) this is the ultimate hidden variable problem. If there was something “intelligent” that could predict a song or artist to a person, both sides (musician and listener) win, music is amazing, there’s a ton of data, and it’s very far from solved.

But anyone in the entire field of music technology has to treat music discovery with respect: it’s not about the revenue of the content owner, it’s not about the technology, it’s not about click through rates, listening hours or conversion. The past few years have shown us over and over that filters and guides are invaluable for music itself to coexist with the new ways of getting at it. We track over 2 million artists now – I estimate there are truly 50 million, most of them currently active. Every single one of them deserves a chance to get their art heard. And while we can laugh when Amazon suggests you put a Norah Jones CD in your cart after you buy a leaf blower, the millions of people that idly put on Pandora at work and get excited about a new band they’ve never heard deserve a careful look. Recommendation technology is powering the new radio and we have a chance to make it valuable for more than just the top 5 percent of musicians.

When people talk about “music recommendation” or “music discovery” they usually mean one of a few things:

  • Artist or song similarity: an anonymous list of similar items to your query. You can see this on almost any music service. Without any context, this is just a suggestion of what other artists or songs are similar to the one you are looking at. Formally, this is not truly a recommendation as there is no user model involved (although since a query took the user to the list, I still call these a recommendation. It’s a recommendation in the sense that a web search result is.)
  • Personalized recommendation: Given a “user model” (your activity on a service – plays, skips, ratings, purchases) a list of songs or artists that the service does not think you know about yet that fits your profile.
  • Playlist generation: Most consumers of music discovery are using some form of playlist generation. This is different from the above two in that they receive a list of items in some order (usually meant to be listened to at the time.) The playlist can be personalized (from a user model) or not, and it can be within catalog (your own music, ala iTunes Genius’s or Google’s Instant Mix playlists) or not (Pandora, Spotify’s or Rdio’s radio, iHeartRadio.) The playlist should vary artists and types of songs as it progresses, and many rely on some form of steering or feedback (thumbs up, skips, etc.)
Where popular services sit in discovery
Personalized Anonymous
Playlist Pandora Rdio radio
Suggestions Amazon All Music Guide

These are three very different ways of doing music discovery, but for every technology and approach I know of, they are simply applications on top of the core data presented in different ways. For example, at the Echo Nest we do quite a bit to make our playlists “radio-like” using our observed statistics, acoustic features and a lot of QA but that sort of work is outside the scope of this article – all three of our similarity API, taste profiles (personalized recommendation) API and playlist API start with the same knowledge base culled from acoustic and text analysis of music.

However, the application means a lot to the listener. People seem to love playlists and radio-style experiences, even if the data driving both that and the boring list of songs to check out are the same. One of the great things about working at the Echo Nest is seeing the amazing user interfaces and experiences and people put on top of our data. Listeners want to hear music, and they want to trust the service and have fun doing it. And conversely, a Pandora completely powered by Echo Nest data would feel the same to users but would have far better scale and results and thus add to the experience. Because of this very welcome sharding of discovery applications, it’s helpful less to talk about these applications directly and more to talk about “what the services know” about music – how they got to the result that Kreayshawn and Uffie are similar, no matter where it appeared in the radio station or suggestion or what user model led them there. We can leave the application and experience layer to another lengthy blog post.

My (highly educated, but please know I have no direct inside information except for Echo Nest of course) guesses on the data sources are:

How popular services know about music
Service Source of data
Pandora Musicologists take surveys
Songza Editors or music fans make playlists
Last.fm Activity data, tags on artists and songs, acoustic analysis[1]
All music guide Music editors & writers
Amazon Purchase & browsing history
iTunes Genius Purchase data, activity data from iTunes[2]
Echo Nest Acoustic analysis, text analysis

There are many other discovery platforms but this list covers the widest swath of approaches. Many services you interact with use either these platforms directly (Last.fm, Echo Nest, AMG all license data or give away data through APIs) or use similar enough approaches that it’d be not worth going into in detail.

From this list we’re left with a few major music knowledge approaches: (1) activity data, (2) critical or editorial review, (3) acoustic analysis, and (4) text analysis.

The former two are self-describing: you can learn about music by the activity around it (listens, plays, purchases) – Kreayshawn and Uffie are considered similar if the same people buy their singles or rate them highly – or you can learn about music by critical review, what humans have been pretty good at for some time. Of course, encoding activity (via collaborative filtering or taste mining) and critical review (via surveys or direct entry) into a database is a relatively recent art.

The latter two, acoustic and textual analysis, were developed by the field as a reaction to the failures of the first two. I’ll go into much greater detail on those as it’s how Echo Nest does its magic.

Care and Scale

The dominating principle of the Echo Nest discovery approach from day one has been “care and scale.” When Tristan and I started the company in 2005 we were two guys with fresh PhDs on music analysis and some pretty good technological solutions; Tristan’s in the acoustic analysis realm (a computer taking a signal and making sense of it) and mine in the data mining and language analysis space (understanding what people are saying and doing with music.) We surveyed the landscape at the time for discovery and found that almost every one suffered from either a lack of care or scale, sometimes (and often) both. The entire impetus of doing a startup (not an easy choice for two scientists and anyone that has met us knows we are not the “startup type”) was that we thought we had something between the two of us that could fix those two problems.

Care & Scale

Scale is easy to explain: you have to know about as much music as possible to make good recommendations. If you don’t know about an up and coming artist, you can’t recommend them. If you only analyze or rate or understand the popular stuff you by default fail at discovery. Manual discovery approaches by their nature do not scale. We track over two million artists and over 30 million songs and there is no way a manually curated database can reach that level of knowledge. Even websites that can be volunteer or community edited run against the limits of the community that takes part – we count only a little over 130,000 artist pages on Wikipedia. Pandora recently crossed the 1 million song barrier, and it took them 10 years to get there. Try any hot new artist in Pandora and you’ll get the dreaded:

Pandora not knowing about YUS

This is Pandora showing its lack of scale. They won’t have any information for YUS for some time and may never unless the artist sells well. This is bad news and should make you angry: why would you let a third party act as a filter on top of your very personal experiences with music? Why would you ever use something that “hid” things from you?

Activity data approaches (such as Last.fm and Amazon and iTunes Genius) also suffer from a slighter scale problem that manifests itself in a different way. It’s trivial to load a database of music into an activity data-based discovery engine (such as collaborative filtering or social tags.) I’ve often gone after such naive approaches to music discovery publicly. If a website or store has a list of user data (user A bought / listened to song Y at time Z) any bright engineer will immediately go into optimization mode. There’s almost a duplicitous ease of recommending music to people poorly. I recently was shopping for a specific type of transistor for a project on a parts and components website and found they, too, had turned on the SQL join that allowed “recommendations” on their site based on activity data:

Pathological filteringPathological filtering

Other than activity not making much sense in a discovery context, by default these systems suffer a “popularity bias,” where a lot of music simply doesn’t have enough activity data yet collected to be considered a recommendation match. Activity based systems can only know what people have told them explicitly, and this often makes it hard for less-popular artists to be recommended.

Care is a trickier concept and one we’ve tried very hard to define and encode into our engineering and product. I translate it as “is this useful for the musician or listener?”A great litmus test for care in music discovery is to check the similar artists or songs to The Beatles. Is it just the members of the Beatles and their side projects? For almost all services that use musical activity data, it will be:

Top artist similars are all members of the BeatlesTop artist similars are all members of the Beatles

Certainly a statistically correct result[3], but not a musically informative one. There is so much that user data can tell you about listening habits, but blindly using it to inform discovery belies a lack of care about the final result. Care is neatly handled by using social, manual or editorial approaches, as humans are pretty good at treating music properly. But when using more statistical or signal processing approaches that know about more music at scale, care has to be factored in somehow. Most purely signal processing approaches (such as Mufin here) fall down as badly on care as activity data approaches do:

Mufin expressing so little care about Stairway to HeavenMufin expressing so little care about Stairway to Heaven

Care is a layer of quality assurance, editing and sanity checks, real-world usage and analysis and, well, care, on top of any systematic results. You have to be able to stand by your results and fix them if they aren’t useful to either musicians or listeners. Your WTF count has to be as low as possible. We’ve spent a lot of time embedding care into our process and while we’re always still working, we’re generally pleased with how our results look.

Echo Nests Beatles similars via MTV Music MeterEcho Nest’s Beatles similars via MTV Music Meter

Without both care and scale you’ve got a system that a listener can’t trust and that musician can’t use to find new fans. You’ve failed both of your intended audiences and you might as well not try at all.

Care & Scale of common approaches

Text Analysis

Echo Nest Cultural vectorsEcho Nest Cultural vectors

I started doing music analysis work in 1999 at the NEC Research Institute in Princeton, NJ (I had scammed them into an internship and then a full time job by being very persistent.) NEC was then full of the top tier of data mining, text retrieval, machine learning and natural language processing (NLP[4]) scientists; I had the great fortune to work with guys like Steve Lawrence, Gary Flake, David Waltz and even Vladimir Vapnik moved into my tiny office after I left for MIT.

I was there while figuring out what to do with myself after abruptly quitting my PhD program in NLP at Columbia. I was a musician at the time, playing a lot of shows at various warehouse spaces or the lamented late “Brownies,” places where 20 people might show up and 10 would know who you were. There was a lot of excitement about “the future of music” – far more than there is today, as somehow we felt that the right forces would win and quickly. I logged onto Napster for the first time from a DSL connection and practically squealed in delight as a song could be downloaded faster than the time it would take to listen to it. It was a turning point for music access, but probably a step back for music discovery. We were still stuck with this:

Napster in 2001Napster in 2001

The search was abysmal: a substring match on ID3v1 tags (32 characters each for artist, title, release and a single byte for genre) or filename (usually “C:\MUSIC\MYAWES~1\RAPSONG.MP3”) and there was no discovery beyond clicking on other users’ names and seeing what they had on their hard drives. I would make my music available but of course, no one would ever download it because there was no way for them to find it. A fellow musician friend quickly took to falsely renaming his songs as “remixes” by better known versions of himself: “ARTIST – TITLE – APHEX TWIN MIX” and reported immediate success.

At the time I was a member of various music mailing lists, USENET groups and frequent visitor of a new thing called “weblogs” and music news and review sites. I would read these voraciously and try to find stuff based on what people were talking about. To me, while listening to music is intensely private (almost always with headphones alone somewhere), the discovery of it is necessarily social. I figured there must be a way to take advantage of all of this conversation, all the excited people talking about music in the hopes that others can share in their discovery – and automate the process. Could a computer ‘read’ all that was going on across the internet? If just one person wrote about my music on some obscure corner of the web, then the system could know that too.

This is scale with care: real people feeding information into a large automated system from all different sources, without having to fill out a survey or edit a wiki page or join a social network.

After almost ten years of data mining, language and music research (first at NECI, then a PhD at MIT at the Media Lab) The Echo Nest currently is the only music understanding service that takes this approach. And it works. We crawl the web constantly, scanning over 10 million music related pages a day. We throw away spam and non-music related content through filtering, we try to quickly find artist names in large amounts of text and parse the language around the name. Every word anyone utters on the internet about music goes through our systems that look for descriptive terms, noun phrases and other text and those terms bucket up into what we call “cultural vectors” or “top terms.” Each artist and song has thousands of daily changing top terms. Each term has a weight associated, which tells us how important the description is (roughly, the probability that someone will describe music as that term.) We don’t use a fixed dictionary for this, we are able to understand new music terms as quickly as they are uttered, and our system works in many Latin-derived languages across many cultures.

On top of this statistical NLP, we also pull in structured data from a number of partners and community access sites like Wikipedia or Musicbrainz. We apply the same frequency and vector approach to this knowledge-base style data: if Wikipedia lists the location of an artist as NYC and the label partner as New York, NY and their Facebook page has “EVERYWHERE ON TOUR 2012”, we have to figure out which is the right answer to index. Often the cultural vectors on structured data become a synthesis of all the different data sources.

When a query for a similar artist or a playlist comes into our system, we take the source artist or song, grab its cultural vectors, and use those in real time to find the closest match. This is not easy to do at scale, and over the years we’ve done quite a lot of “big data” work to make this tractable. We don’t cache this data because it changes so often – the global conversation around music is very finicky and artists make overnight changes to their sound.

A lot of useful data naturally falls out of cultural analysis of music: the quantity of conversation is used to inform our “hotttnesss” and familiarity data points, representing how popular the artist is now on the internet and overall how well known they might be. We can use the crawled text anonymously as sort of a proxy for listener data without having to get it from a playback service. And the index of documents that relate to artists or songs is of course valuable to a lot of our customers in a feed or search context – showing news or reviews about artists their users are interested in.

Acoustic Analysis

Echo Nest acoustic analysis viewEcho Nest acoustic analysis view

The internet is not the Library of Babel we envision it to be, and quite often many “lower-rank” (less popular) musicians are left out of the “cultural universe” we crawl. Also, the description of music necessarily leaves out things that actually describe the music – a Google blog search for Rihanna illustrates the problem well: many popular artists’ descriptions are skewed towards the celebrity angle and while this is certainly a valid thing to know about a musician, it’s not all we need to know. Lastly, internet discussion of music tends to concentrate on artists, not songs (although there is sometimes talk of individual songs on music blogs.) These three issues (and common sense) require us figure out if we can understand how a song sounds as well as how the artist and song is represented by listeners. And if we are going to follow care and scale, we’ve got to do this automatically, with a computer doing the job of the careful listening.

Can a computer really listen to music? A lot of people have promised it can over the years, but I’ve (personally) never heard a fully automated recommendation based purely on acoustic analysis that made any sense – and I’ve heard them all, from academic papers to startups to our own technology to big-company efforts. And that has a lot to do with the expectations of the listener. There are certain things computers are very good and fast at doing with music, like determining the tempo or key, or how loud it is. Then there are harder things that will get better as the science evolves, like time signature detection, beat tracking over time, transcription of a dominant melody, and instrument recognition. But even if a computer were to predict all of these features accurately, does that information really translate into a good recommendation? Usually not – and we’ve shown over the years that people’s expectation of “similar” – either in a playlist or a list of artists or songs – trends heavily towards the cultural side, something that no computer can get at simply by analyzing a signal.

But it does turn out that acoustic analysis has a huge part to play in our algorithms. People expect playlists to be smooth and not jump around too much. Quiet songs should not be followed with loud metal benders (unless the listener asked for that.) For jogging, the tempo should steadily increase. Most coherent mixes should keep the instrumentation generally stable. Songs should flow into one another like a DJ would program them, keeping tempo or key consistent. And there’s a ton we haven’t figured out yet on the interface side. Could a “super dorky query interface” work for music recommendation, where a listener can filter by dominant key or loudness dynamics? Maybe with the right user experience. An early product out of the Echo Nest[5] was an “intelligent pause button” that Tristan whipped up that would compose a repeating segment out of the part of the song you were in or just play the song roughly forever (check out an automated 10 minute MP3 re-edit of a Phoenix song) – which a few years later became Paul’s amazing Infinite Jukebox – these experiments are fascinating precursors to a new listening experience that might become more important than discovery itself.

How Echo Nest acoustic analysis worksHow Echo Nest acoustic analysis works

The Echo Nest audio analysis engine (PDF) contains a suite of machine listening processes that can take any audio file and outputs both low-level (such as the time of when every beat starts) and high-level (such as the overall “danceability”) information for any song in the world. We analyze all the music we work with, and developers can upload their own audio to see everything we compute on a track via our API. Our analysis starts by pretending it was an ear: it will model the frequencies and loudness of a musical signal much the same way perceptual codecs like MP3 or AAC do. It then segments the audio into small pieces – roughly 200ms to 4s, depending on how fast things are happening in the song. For each segment we can tell you the pitch (in a 12-dimensional vector called chroma), the loudness (in an ADSR-style envelope) and the timbre, which is another 12 dimensional vector that represents the sound of the sound – what instruments there are, how noisy it is, etc. It also tracks beats across the signal, in subdivisions of the musical meter called tatums, and then per beat and bar, alongside larger song-level structure we call sections that denote choruses, intros, bridges and verses.

That low level information can be combined through some useful applications of machine learning that Tristan and has team have built over the years to “understand” the song at a higher level. We emit song attributes such as danceability, energy, key, liveness, and speechiness, which aim to represent the aboutness of the song in single floating point scalars. These attributes are either heuristically or statistically observed from large testbeds: we work with musicians to label large swaths of ground truth audio against which to test and evaluate our models. Our audio analysis can be seen as an automated lead sheet or a computationally understandable overview of the song: how fast it is, how loud it gets, what instruments are in it. The data within the analysis is so fine grained that you can use it as a remix tool – it can chop up songs by individual segments or beats and rearrange them without anyone noticing.

We don’t use either type of data alone to do recommendations. We always filter the world of music through the cultural approaches I showed above and then use the acoustic information to order or sort the results by song. A great test of a music recommender is to see how it deals with heavy metal ballads – you normally would expect other ballads by heavy metal bands. This requires a combination of the acoustic and cultural analysis working in concert. The acoustic information is obviously also useful for playlist generation and ordering, or keeping the mood of a recommendation list coherent.

What’s next

I’ve used every single automated music recommendation platform, technology or service. It’s obviously part of my job and it’s been astounding to watch the field (both academically and commercially) mature and test new approaches. We’ve come a long way from RINGO and while the Echo Nest-style system is undoubtedly the top of the pack these days as far as raw quality of automated results go, there’s still quite a lot of room to grow. I’ve been noticing two trends in the space that will certainly heat up in the years to come:

Social – filtering collaborative filtering

This is my jamThis is my jam

Social music discovery as embodied by some of my favorite music services such as This is my jam, Swarm.fm, Facebook’s music activity ticker and real time broadcasting services like the old Listening Room and its modern progentior Turntable.fm often have no or little automated music discovery. Friend-to-friend music recommendations enabled by social networks are extremely valuable in music discovery (and I personally rely on them quite often), but are not recommendation engines as they can not automatically predict anything when bereft of explicit social signals (and so they fail on scale.) The main amazing and useful feature of recommendation systems are that it can find things for you that you wouldn’t have otherwise come across.

Even though that puts this kind of service outside the scope of this article, that doesn’t mean we should ignore the power of social recommendations. There’s something very obvious in the social fabric of these services that makes personal recommendations more valuable: people don’t like computers telling them what to do.

There are some interesting new services that mix both the social aspects of recommendation with automated measures. This is my jam’s “related jams” is a first useful crack at this, as is Spotify’s recent “Discover” feature. You can almost see these as extensions of your social graph: if your friends haven’t yet caught onto Frank Ocean there might be signals that show they will get there soon, and using cultural filtering can get us there. And a lot of the power of social recommendations – that it comes from your friends – can tell the story better than just a raw list of “artists we think you would like.”

Listener intelligence

When do you listen to music? Is it in the morning on your way to work? Is it on the weekends, relaxing at home? When you do it, how often do you listen to albums versus individual songs in a playlist? Do you idly turn on an automated radio station, or have your own playlists? Which services do you use and why? If it’s raining, do you find yourself putting on different music? The scariest thing about all the music recommendation systems I’ve gone over (including ours as of right now) is none of them look at this necessary listener context.

There is a lot going on in this space, both internal stuff we can’t announce yet at Echo Nest, and new products I’m seeing coming out of Spotify and Facebook. We’re throwing our weight behind the taste profile – the API that represents musical activity on our servers. It’s sort of the scrobble 2.0: both representing playback activity as well as all the necessary context around it: your behaviors and patterns, your collection, your usage across services and maybe even domains. We’re even publishing APIs to do bulk analysis of the activity to surface attributes like “mainstreamness” or “taste-freeze,” the average active year of your favorite artists. This is more than activity mining as collaborative filtering sees it: it’s understanding everything about the listener we can, well beyond just making a prediction of taste based on purchase or streaming activity. All of these attributes and analysis might be part of the final frontier of music recommendation: understanding enough to really understand the music and the listener it’s directed to.

– Brian (brian@echonest.com)

Thanks to EVB for the edits


  1. I know they do a ton of acoustic analysis there but I don’t know if it’s used in radio or similar artists/songs. Probably.  ↩
  2. They use Gracenote’s CDDB data as well but I don’t know to what extent it appears in Genius.  ↩
  3. You can even claim that since you are listening to the Beatles, you are also listening to the individual members at the same time but let’s not get too ahead of the curve here  ↩
  4. Whenever I say NLP I mean the real NLP, the natural language processing NLP, not the creepy pseudoscience one.  ↩
  5. Released eventually as the Earworm example in Echo Nest Remix.  ↩

Les machines du goût : sur les algorithmes de la recommandation

Musicovery
Musicovery

 

Dans une récente thèse de doctorat portant sur l’API Echo Nest et plus généralement sur les algorithmes de la recommandation (la thèse sera prochainement publiée aux éditions Hermann), Stephan-Héloïse Gras montre comment, dans un univers où les catalogues de services de streaming musical en ligne détiennent des millions de titres, de nouvelles formes de compétition se mettent en place autour de la recommandation personnalisée de nouveaux artistes. L’enjeu est en quelque sorte symétrique : pour les plateformes, cibler leurs publics potentiels avec un niveau de granulométrie exceptionnellement fin. On passe en quelque sorte du “prêt à porter” naguère offert par les systèmes promotionnels à l’époque du disque ou du CD au “taillé sur mesure”. Pour les publics, trouver l’artiste qu’on ne connaît pas encore mais qu’on aimera presque à coup sûr parce qu’il correspond à la structure de nos goûts, à notre sensibilité esthétique voire à nos émotions du moment… Car à ce petit jeu des affinités électives, c’est non seulement la mise en relation d’un artiste avec un auditeur que proposent les machines du goût mais également la contextualisation de cette relation : leur devise pourrait être “The right artist at the right place at the right time”, puisque la contextualisation peut théoriquement tenir compte de variables aussi précises que le lieu où vous vous trouvez, de l’heure de la journée, du type de lumière, de votre état émotionnel et que les développements de la recommandation  vont aller de pair non seulement avec le développement des capacités de traitement des big data mais également avec la sophistication de capteurs de données individuelles. Un bon exemple de “recommandation émotionnelle” se trouve sur le site http://musicovery.com/, co-dirigé par Vincent Castaignet.

Je reviendrai très régulièrement sur ce sujet car il est central pour comprendre ce qui se joue aujourd’hui dans la relation entre les publics et les distributeurs de contenus. D’ores et déjà, on peut signaler plusieurs des questions de fond que les machines du goût suscitent : l’hyper-personnalisation de la recommandation contribue-t-elle à élargir le portefeuille des goûts (autrement dit, écoute t-on plus d’artistes et surtout plus d’artistes issus de familles esthétiques diversifiées ?) ou n’assiste t-on pas au contraire à une sorte d’homogénéisation des préférences ? Les algorithmes permettent non seulement de recommander de la musique mais également d’offrir des services connexes comme des tickets de concert ou des produits dérivés. Comment peuvent-ils contribuer à la réorganisation du marché ? Par ailleurs, les systèmes de recommandation, en matière de musique, ne sont-ils pas largement indexés sur un modèle occidentalocentrique, pour ne pas dire américanocentrique, du goût ? Enfin, comme le  soulignait Brian Whitman, co-fondateur de l’API Echo Nest et aujourd’hui music scientist chez Spotify, jusqu’à quel point les outils de la recommandation ne réintroduisent-ils pas une forme d’hyper-déterminisme social, par exemple lorsqu’ils lient le fait d’aimer Rihanna au fait d’être plutôt de gauche (enfin, démocrate puisqu’il s’agit des USA dans cet exemple : http://notes.variogr.am/post/26869688460/how-well-does-music-predict-your-politics) mais sans assortir ce type de corrélation d’aucune explication sociologique digne de ce nom ?

En attendant d’explorer plus avant ce sujet, on trouvera ci-dessous un premier article expliquant comment fonctionnent les machines du goût. A suivre,  un article de Brian Whitman sur le même sujet.

 Les algorithmes de recommandation

On 25.04.2012, in Dossiers, by Mathieu(http://www.podcastscience.fm/dossiers/2012/04/25/les-algorithmes-de-recommandation/)

Il existe des centaines d’algorithmes qui ont été utilisés pour l’implémentation de systèmes de recommandation. La plupart relève de concepts mathématiques avancés. Dans ce dossier, on va tenter d’analyser différentes approches et stratégies utilisées lors de la mise en place d’un système de recommandation.Wikipedia définit un système de recommandation comme une forme spécifique de filtrage de l’information visant à présenter les éléments d’information (films, musique, livres, news, images, pages Web, etc) qui sont susceptibles d’intéresser l’utilisateur.

Dit autrement, un système de recommandation cherche à prédire la valorisation ou préférence qu’un utilisateur attribuerait à un objet (livre, musique, film…) ou à un élément social (personne, groupe, communauté) qu’il n’avait pas encore considéré.

Un système de recommandation requiert généralement 3 étapes:

  1. La première consiste à recueillir de l’information sur l’utilisateur.
  2. La deuxième consiste à bâtir une matrice ou un modèle utilisateur contenant l’information recueillie.
  3. La troisième consiste à extraire à partir de cette matrice une liste de recommandations.

Collecte d’Information

Pour être pertinent, un système de recommandation doit pouvoir faire des prédictions sur les intérêts des utilisateurs. Il faut donc pouvoir collecter un certain nombre de données sur ceux-ci afin d’être capable de construire un profil pour chaque utilisateur.

Une distinction peut être faite entre 2 formes de collecte de données:

  • Collecte de données explicite – Filtrage actif: repose sur le fait que l’utilisateur indique explicitement au système ses intérêts.
    • Exemple: demander à un utilisateur de commenter, taguer/étiqueter, noter, liker ou encore ajouter comme favoris des contenus (objets, articles…) qui l’intéressent. On utilise souvent une échelle de ratings allant de 1 étoile (je n’aime pas du tout) à 5 étoiles (j’aime beaucoup) qui sont ensuite transformées en valeurs numériques afin de pouvoir être utilisées par les algorithmes de recommandation.
    • Avantage: capacité à reconstruire l’historique d’un individu et capacité à éviter d’agréger une information qui ne correspond pas à cet unique utilisateur (plusieurs personnes sur un même poste).
    • Inconvénient: les informations recueillies peuvent contenir un biais dit de déclaration.
  • Collecte de données implicite – Filtrage passif: repose sur une observation et une analyse des comportements de l’utilisateur effectuées de façon implicite dans l’application qui embarque le système de recommandation, le tout se fait en “arrière-plan” (en gros sans rien demander à l’utilisateur).
    • Exemples:
      • Obtenir la liste des éléments que l’utilisateur a écoutés, regardés ou achetés en ligne.
      • Analyser la fréquence de consultation d’un contenu par un utilisateur, le temps passé sur une page.
      • Monitorer le comportement en ligne de l’utilisateur.
      • Analyser son réseau social.
    • Avantage: Aucune information n’est demandée aux utilisateurs, toutes les informations sont collectées automatiquement. Les données récupérées sont a priori justes et ne contiennent pas de biais de déclaration.
    • Inconvénient: Les données récupérées sont plus difficilement attribuables à un utilisateur et peuvent donc contenir des biais d’attribution (utilisation commune d’un même compte par plusieurs utilisateurs). Un utilisateur peut ne pas aimer certains livres qu’il a acheté, ou il peut l’avoir acheté pour quelqu’un d’autre.

Modèle Utilisateur

Le modèle utilisateur se présente généralement sous forme de matrice. On peut se le représenter comme un tableau qui contient des données recueillies sur l’utilisateur associées aux produits disponibles sur le site web.

Un autre point important est comment le temps influence le profil de l’utilisateur. Les intérêts des utilisateurs, généralement, évoluent au cours du temps. Les données du modèle utilisateurs devraient donc constamment être réajustées pour rester conformes aux nouveaux centre d’intérêts de l’utilisateur.

Liste de recommandations

Pour extraire une liste de suggestions à partir d’un modèle utilisateur, les algorithmes utilisent la notion de mesure de similarité entre objets ou personnes décrits par le modèle utilisateur. La similarité a pour but de donner une valeur ou un nombre (au sens mathématique du terme) à la ressemblance entre 2 choses. Plus la ressemblance est forte, plus la valeur de la similarité sera grande. A l’inverse, plus  la ressemblance est faible, et plus la valeur de la similarité sera petite. On verra plus tard dans le dossier quelques exemples.

Types de système de recommandation

On a l’habitude de présenter 4 approches possibles pour un système de recommandation:

  • Recommandation Personnalisée
  • Recommandation Objet (Content-Based filtering CB)
  • Recommandation Sociale (Collaborative Filtering CF – Context Aware)
  • Recommandation Hybride

Recommandation Personnalisée

Il s’agit de recommander des objets sur la base du comportement passé de l’utilisateur.

Exemples:

  • Des produits achetés ou sélectionnés sur un site de e-commerce, ainsi qu’un certain nombre d’actions ou décisions effectuées par l’utilisateur qui permettent de prédire de nouveaux produits susceptibles de l’intéresser.
  • Les annonces publicitaires (par ex. Adsense de Google) sont considérées comme des systèmes de recommandation personnalisée qui se basent sur le comportement passé de l’utilisateur (navigation, clics, historique de recherche…)

Recommandation Objet

Il s’agit de recommander des objets (ou contenus) en se basant sur les qualités et propriétés intrinsèques de l’objet lui-même et en les corrélant avec les préférences et intérêts de l’utilisateur. Ce type de système va donc extraire un certain nombre de caractéristiques et attributs propres à un contenu, afin de pouvoir recommander à l’utilisateur des contenus additionnels possédant des propriétés similaires. Cette méthode crée un profil pour chaque objet ou contenu, c’est-à-dire un ensemble d’attributs/propriétés qui caractérisent l’objet.

Exemples:

  • La décision de sélection et recommandation ou non d’un document à un utilisateur peut se baser sur le contenu (les mots présents) dans celui-ci, c’est-à-dire sur une comparaison des thèmes abordés dans le document par rapport aux thèmes qui intéressent l’utilisateur.
  • Pour décider la suggestion d’un article (news) ou non, un système de recommandation peut se baser sur les mot-clés principaux de l’article et les comparer avec les mot-clés apparaissant dans d’autres articles que l’utilisateur a évalués positivement dans le passé.
  • Dans le cas d’un site de vente de livre en ligne, on va se baser sur les caractéristiques du livre pour effectuer des recommandations, comme par exemple le sujet que traite l’ouvrage, son genre, son auteur, l’éditeur, etc. On pourrait ainsi recommander le livre Harry Potter à un utilisateur, si on sait d’une part que ce livre est un roman fantastique et d’autre part que l’utilisateur aime les romans fantastiques. Un système de recommandation pourra donc accomplir cette tâche seulement s’il a à disposition 2 types d’information:  1) la description des caractéristiques du livre et 2) un profil utilisateur qui décrit les intérêts (passés) de celui-ci en termes de préférence de type de livre. La tâche de recommandation consiste donc à déterminer les livres qui correspondent le mieux aux préférences de l’utilisateur.
Profil des livres
Profil/Préférences Utilisateur

Les algorithmes de recommandation objet permettent de développer des modèles afin de trouver des patterns ou motifs semblables entre différentes données. Ils évaluent à quel point un contenu pas encore vu par l’utilisateur est similaire aux contenus que celui-ci a évalués positivement dans le passé. Pour ce faire, on utilise la notion de similarité qui peut être mesurée de plusieurs manières:

  • Le système peut tout simplement vérifier si le livre se trouve dans la liste des genres préférés de l’utilisateur. Dans ce cas la similarité sera de 0 ou 1 (binaire/boolean).
  • Une autre façon serait de ne pas se baser sur le genre du livre, mais sur les mot-clés qui caractérisent l’ouvrage, et calculer la similarité de chevauchement entre les mots-clés du livre qui va éventuellement être suggéré avec les mots-clés préférés de l’utilisateur. Un des indicateurs de mesure de similarité qu’on utilise dans le cas d’un objet avec des propriétés multi-valeurs (cas des mot-clés) est le coefficient de Dice. Si chaque livre est décrit par un ensemble de mot-clés, le coefficient de Dice permet de mesurer le degré de similarité entre 2 livres à partir de leurs mot-clés.

Chevauchement des mots-clé

Dans le cas de documents de texte, on peut également imaginer que le contenu de chaque document soit décrit à partir d’une liste de tous les mots apparaissant dans le document, et décrire chaque document par un vecteur de valeurs binaires/booléennes, où un 1 indiquerait que le mot apparaît dans le document et un 0 indiquerait que le mot n’apparaît pas dans le document. Si le profil utilisateur est décrit par une liste similaire (un 1 indique un intérêt pour un mot-clé), on peut facilement associer et proposer des documents en mesurant le chevauchement entre les mot-clés qui intéressent l’utilisateur et les mots contenus dans le document. Le problème qui surgit avec une telle approche est qu’on assume que chaque mot a la même importance au sein d’un document. Or un mot qui apparaît très souvent ne caractérise pas forcément mieux un document. En plus, un plus large chevauchement entre les préférences de l’utilisateur et un document apparaîtera naturellement plus le document est long. En conséquence, le système de recommandation tendera à proposer des longs documents. Pour résoudre ces problèmes, on applique des techniques qui permettent de réduire le poids des mots qui apparaissent très souvent et d’augmenter le poids de ceux qui apparaissent plus rarement. Pour rendre encore plus compacte la liste des mots présents dans un document, on peut aussi quitter un certain nombre de mots qui sont sans intérêt, comme les prépositions, les articles… En normalisant aussi différentes variantes d’un même mot, par exemple les verbes conjugués sont remplacés par leur infinitif (volait par voler). On peut aussi décider de limiter la liste aux n mots les plus pertinents apparaissant dans les documents. Différents travaux ont montrés que le nombre optimum de mots à prendre en compte se trouve aux alentours de 100. Si trop peu de mots sont sélectionnées (moins de 50), on voit que d’importantes caractéristiques d’un document ne sont pas couvertes. Et si trop de mots sont inclus, certains ont peu d’importance et apportent plus de bruit qu’autre chose, ce qui réduit la qualité de la recommandation. On utilise aussi des base de connaissances lexicales externes pour éliminer des mots non pertinents.

De façon générale, les algorithmes de recommandation objet assignent un poids plus ou moins élevé aux attributs d’un contenu selon l’importance de ceux-ci. Le poids exprime donc l’importance de chaque attribut pour un utilisateur.

Un autre algorithme de recommandation objet couramment utilisé est la méthode de retour de pertinence de Rocchio (Rocchio’s relevance feedback) ou  classification de Rocchio. L’idée de cette méthode est de prendre en compte le point de vue des utilisateurs sur les recommandations proposées. Le principe, simple, repose sur le fait que l’utilisateur est le seul à savoir exactement ce qu’il recherche et apprécie, il est donc le plus à même de juger de la pertinence des suggestions retournées par un système de recommandation. Partant de cette idée, les systèmes exploitant le retour de pertinence permettent de récupérer ces « jugements » utilisateurs et les exploitent pour améliorer et affiner les recommandations. Techniquement, l’idée est dans un premier temps de décomposer les contenus évalués par l’utilisateur en 2 groupes (vecteurs, clusters) D+ (contenus évalués positivement et pertinents) et D- (contenus évalués négativement et non pertinents). Par un procédé mathématique on calcule une moyenne (prototype) qui permet de déterminer le centre (centroid) de chacun des 2 groupes (vecteurs) D+ et D-. Lorsqu’un nouvelle requête est effectuée par l’utilisateur, les résultats à recommander sont pondérés en fonction des 2 groupes D+ et D-. C’est-à-dire, on ajoute au résutats de la requête la liste D+ et on soustrait (retire) la liste D-, le tout de façon pondérée. L’effet obtenu est que les résultats retournés se rapprochent à chaque itération un peu plus du centre (centroid) de la liste D+ des contenus évalués positivement par l’utilisateur. Avec cette technique, on voit qu’il est possible d’affiner la requête initiale des utilisateurs au fur et à mesure que ceux-ci fournissent des jugements de pertinence sur des documents consultés. Le système de recommandation est donc doté d’une boucle de retour qui permet au même système de reformuler des recommandations plus pertinente en favorisant ou écartant certains contenus.

Avantages et inconvénients

Avantage: ce type de recommandation objet n’a pas besoin d’une large communauté d’utilisateurs pour pouvoir effectuer des recommandations. Une liste de recommandations peut être générée même s’il n’y a qu’un seul utilisateur.

Inconvénients: certains attributs peuvent être extraits automatiquement d’un contenu, comme par exemple pour un document de texte, on peut relativement facilement déduire certaines propriétés sémantiques automatiquement. On voit aussi qu’en pratique, des caractéristiques et propriétés comme le genre d’un livre ou la liste des acteurs dans un film, sont généralement fournis pas les créateurs du livre ou du film et sont généralement offerts sous forme électronique. Ce qui reste plus problématique, c’est l’acquisition de caractéristiques subjectives et qualitatives… Des propriétés, comme par exemple le style, le design… peuvent difficilement être acquises automatiquement, et devront plutôt être introduites manuellement avec tout ce que ça implique, comme le coût, les éventuelles erreurs…

Recommandation Sociale

Recommander des choses sur la base du comportement passé des utilisateurs similaires, en effectuant une corrélation entre des utilisateurs ayant des préférences et intérêts similaires. On utilise des méthodes qui collectent et analysent des données sur le comportement, les activités, les préférences des utilisateurs et des algorithmes tentent de prédire ce que l’utilisateur aimera en cherchant des utilisateurs qui ont les mêmes comportements que l’utilisateur à qui l’on souhaite faire des recommandations. L’idée sous-jacente est de dire que si un personne A a la même opinion (ou les même goûts) qu’une personne B sur un objet x, alors la personne A a plus de chance d’avoir la même opinion que B sur un autre objet y, plutôt que d’avoir la même opinion que quelqu’un choisi au hasard pour l’objet y. L’idée de base est donc de dire que si des utilisateurs ont partagés des mêmes intérêts dans le passé, il y a de fortes chances qu’ils partagent aussi les mêmes goûts dans le futur.

Les techniques de recommandation sociale (filtrage collaboratif) sont classées en 2 sous-types:

  • memory-based
  • model-based

User-based nearest neighbor (user-centric / memory-based)

Les algorithmes de recommandation sociale utilisent généralement différentes variantes d’un mécanisme basé sur le voisinage proche (user-based nearest neighborhood approach). Dans cette approche, un nombre d’utilisateurs (peer users / nearest neighbors / plus proches voisins) est identifié et sélectionné sur la base de la similarité de leurs intérêts et préférences avec l’utilisateur actif. On utilise alors principalement les ratings (par ex: films) de ces utilisateurs “voisins” pour calculer des similarités avec l’utilisateur actif. Pour chaque produit p que l’utilisateur n’a pas encore vu, une prédicition est faite en se basant sur les ratings de p assignés par le panel d’utilisateurs voisins. Cette méthode suppose 2 conditions initiales (inconvénients):

  1. On assume que si des utilisateurs ont eu des goûts similaires dans le passé, ils auront aussi des goûts similaires dans le futur.
  2. Les préférences des utilisateurs restent stables et cohérentes dans le temps.

Pour bien comprendre, on peut imaginer un tableau ou matrice de ratings de films, avec sur un axe les utilisateurs et sur un autre les films. Chaque cellule de la matrice contient le rating donné par un utilisateur pour un film. Un signe “+” indique que l’utilisateur a aimé le film, un signe “-” qu’il ne l’a pas aimé, pas de signe signifie qu’il n’a pas d’avis particulier sur ce film. Pour pouvoir prédire si Ken apprécierait le film “Fargo” et éventuellement lui recommander ce film, on compare les ratings de Ken à ceux des autres utilisateurs sélectionnés. On peut alors voir que Ken et Mike ont des ratings identiques, et que Mike a aimé le film Fargo, on pourrait alors prédire que Ken aimera aussi ce film et lui faire cette suggestion (user-centric).

Au lieu de se baser uniquement sur l’utilisateur le plus semblable, la prédiction est normalement calculée à partir de la moyenne pondérée des ratings de plusieurs utilisateurs. Le poids donné au rating de chaque utilisateur est déterminé par le degré de corrélation entre cet utilisateur et l’utlisateur pour qui on désire faire la recommandation. Pour mesurer le degré de corrélation entre 2 utilisateurs, on fait appel généralement au coefficient de corrélation de Pearson r. D’autres indicateurs de mesure de la similarité ou proximité entre utilisateurs sont aussi utilisés comme la corrélation de Ringo, ou le coefficient de corrélation de Spearman. Le coefficient de corrélation de Pearson se calcule à partir des valeurs présentes dans la matrice et peut prendre une valeur allant de +1 (forte corrélation positive) à -1 (forte corrélation négative). Par exemple, un coefficient de corrélation 0.70 entre 2 utilisateurs indiquerait une bonne similarité de leurs intérêts. On introduit aussi souvent dans le calcul de la mesure de Pearson un facteur de pondération afin de prendre en compte et pondérer le fait que certains utilisateurs ont toujours tendance à donner seulement de bons ratings, ou que d’autres ne vont jamais donné le rating maximum à un produit.

Les systèmes de recommandation doivent généralement aussi gérer un grand nombre d’utilisateurs. Faire des recommandations à partir des ratings de millions d’utilisateurs peut avoir de sérieuses implications en termes de performance. Ainsi, qua

nd le nombre d’utilisateurs atteint un certain seuil, une sélection des “meilleurs” voisins doit être faite. Pour déterminer quels sont les voisins les plus pertinents à sélectionner, on utilise généralement l’algorithme du k-nearest neighbor (k-NN) qui permet de sélectionner seulement les k meilleurs voisins ayant la plus haute valeur de corrélation. Une autre approche (correlation-thresholding) serait de sélectionner seulement les voisins possédant une corrélation plus grande qu’un certain seuil. Le problème dans ces deux approches réside dans le fait de sélectionner le bon nombre k d’utilisateurs voisins à prendre en compte ou de déterminer la bonne valeur du seuil de corrélation. Si le nombre k est trop petit ou si le seuil de similarité est trop élevé, le nombre d’utilisateurs voisins pris en compte sera trop réduit pour effectuer une bonne prédiction (problème du reduced coverage/couverture réduite). Dans le cas contraire, lorsque que k est trop élevé ou que le seuil est trop faible, l’ensemble du panel de voisins est trop large (trop d’utilisateurs avec un degré de similarité limité), ce qui amène du bruit additionnel dans les prédictions. Plusieurs travaux et situations réelles ont montré qu’un panel composé de 20 à 50 voisins donne de bons résultats.

On n’est pas non plus limités aux ratings ou like/dislike, on peut aussi se baser sur des données plus implicites en observant le comportement de l’utilisateur sur le site, par opposition à la récolte de données explicite comme l’est le rating. On peut observer par exemple quelle musique il a écouté, quel article il a lu, et on croise ses infos avec celles du reste des utilisateurs afin de lui proposer de nouvelles suggestions.

La recommandation sociale user-centric a cependant ses limites. Lorsqu’il s’agit d’un gros site qui gère des millions d’utilisateurs et un catalogue de milliers de produits, il faut scanner un grand nombre de voisins potentiels, ce qui rend impossible la recommandation en temps réel. Pour palier ce problème, les gros sites implémentent souvent une technique différente plus apte au traitement préalable des données hors-ligne (offline preprocessing), la recommandation sociale item-centric (à ne pas confondre avec la recommandation objet).

Item-based nearest neighbor (item-centric / model-based)

Cette autre approche, appelée aussi item-to-item, propose une inversion de l’approche user-based nearest neighbor. Au lieu de mesurer la corrélation entre des utilisateurs, les ratings sont utilisés pour mesurer la corrélation entre les contenus (films), en s’aidant toujours du coefficient de corrélation de Pearson, mais cette fois-ci appliqué au contenu. Si par exemple les ratings des deux films “Fargo” et “Pulp Fiction” ont une parfaite corrélation, c’est-à-dire qu’ils ont reçu les mêmes ratings (positif, négatif ou nul) de la part des utilisateurs, on peut ainsi prédire que Ken aimera le film “Fargo” car il a aimé “Pulp Fiction” (les ratings des utilisateurs sur ces deux films sont parfaitement corrélés).

Pour le dire autrement, l’approche item-centric propose de rechercher en premier lieu des contenus similaires et ensuite de faire une recommandation à l’utilisateur. Cette approche permet de faire un traitement préalable sur la matrice pour déterminer les contenus similaires et ainsi pouvoir effectuer des prédictions en temps réel, contrairement à l’approche user-centric très gourmande en mémoire.

Autant le coefficient de corrélation de Pearson est très utilisé pour déterminer des utilisateurs similaires (cas de la recommandation sociale user-centric), dans l’approche item-centric, on utilise plutôt comme indicateur de mesure de similarité entre items un autre indicateur qu’on appelle de similarité cosinus ajustée. Les valeurs possibles pour cet indicateur vont comme dans le cas de mesure de Pearson de +1 (forte similarité positive) à -1 (forte similarité négative). Une fois que la similarité entre les items a été établie à l’aide de la similarité cosinus ajustée, on peut alors prédire un rating pour un item grâce aux ratings effectués par l’utilisateur sur les items similaires.

Dans l’approche item-centric, l’idée est donc de construire à l’avance la matrice de similarité entre items. Et en temps réel, on peut facilement ensuite déduire la prédiction de recommandation (le rating) d’un produit pour un utilisateur actif en déterminant depuis la matrice déjà construite quels sont les produits les plus similaires, et en calculant la valeur moyenne de ratings sur ces produits effectués par les utilisateurs voisins.

Avantages et inconvénients

Avantage:  L’approche purement de recommandation sociale n’exploite pas ou ne demande aucune connaissance sur les contenus eux-même. Par exemple, dans le cas d’un magasin de vente de livres en ligne, le système de recommandation collaboratif n’a pas besoin de savoir le type de contenu du livre, son genre, qui en est l’auteur, etc… Pas besoin de se baser sur l’analyse des propriétés intrinsèques d’un livre ou d’un contenu, la recommandation sociale est capable de recommander des contenus sans avoir besoin de comprendre le sens ou la sémantique du contenu lui-même. Les informations propres au livre n’ont pas besoin d’être introduite dans le système.

Inconvénients:

  • Scalability: souvent, les plate-formes sur lesquelles sont utilisés les filtres collaboratifs ont des millions d’utilisateurs, de produits et contenus. Ça demande donc beaucoup de puissance de calcul pour pouvoir proposer des suggestions aux utilisateurs. La recommandation sociale de type user-centric est aussi appelée memory-based, car la base de données des ratings est maintenue en permanence en mémoire dans le serveur et utilisée directement pour générer des recommandations à l’utilisateur actif. Bien que cette approche memory-based soit théoriquement plus précise, car elle a disposition en permanence et en temps réel toutes les données pour générer les recommandations, elle souffre de problèmes de scalability pour des bases de données de millions d’utilisateurs et de millions de contenus. Dans une approche item-centric ou model-based, les données sont préalablement traitées hors-ligne. Ensuite lors de l’exécution de l’application ou service web, le modèle “appris” ou pré-traité sera utilisé pour effectuer les prédictions. L’approche model-based permet d’éviter le problème de scalability.
  • Cold Start: les systèmes de recommandation sociale ont besoin de beaucoup de données et beaucoup d’utilisateurs pour être performants. Le lancement d’un service de recommandation peut souffrir au début du manque d’utilisateurs et d’informations sur ceux-ci.
  • Sparsity (Rareté): le nombre de produits ou contenus est énorme sur certaines plates-formes, et même les utilisateurs les plus actifs auront noté ou valorisé qu’un tout petit sous-ensembe de toute la base de données. Donc, même l’article le plus populaire n’aura que très peu de bonnes notes. Dans une telle situation, deux utilisateurs auront peu d’articles valorisés en commun, ce qui rend plus difficile la tâche de corrélation. C’est une situation qu’on retrouve lorsque le système dispose d’un ratio élevé de contenu par rapport aux utilisateurs, et qu’on retrouve aussi souvent au stade initial du lancement du service de recommandation, ce qui nous ramène au problème de cold start (qui peut être vu comme un cas spécial du problème de rareté).

Recommandation Hybride

Une combinaison des trois approches ci-dessus. Les méthodes hybrides sont de plus en plus utilisées, car elle permettent de résoudre des problèmes comme le cold start et la sparsity (rareté) qu’on retrouve dans une approche de recommandation uniquement sociale. D’autre part, si par exemple on considère 2 utilisateurs avec les mêmes goûts mais qui n’ont pas évalué ou “raté” des objets en commun, un filtrage collaboratif pur ne les considérera pas comme similaires ou voisins. Rappelons que la mesure de similarité standard ne prend en compte que les éléments pour lesquels l’utilisateur actif et l’utilisateur à comparer ont effectué un rating. L’idée est alors de pouvoir assigner une valeur par défaut aux éléments qui ont été “ratés” seulement par un des deux utilisateurs, afin d’améliorer la qualité de prédiction en cas de rareté (sparsity). En appliquant préalablement un algorithme de recommandation objet sur les contenus pour en exploiter leurs descriptions et caractéristiques, accompagné ensuite d’un algorithme de recommandation sociale pour effectuer les recommandations peut aider à résoudre ces limitations. Autrement dit, pour les cas de rareté (sparsity), lorsque peu d’items ont été évalués par les utilisateurs et qu’un filtrage collaboratif n’est pas possible, ce qu’on fait, c’est qu’on assigne en premier lieu un pseudo-rating ou vote artificiel par défaut à l’utilisateur sur les contenus disponibles en utilisant préalablement un algorithme objet, puis on applique ensuite sur la matrice (contenant peu de vrais rating et beaucoup de pseudo-ratings) un filtrage collaboratif.

Exemples:

Amazon utilise les 3 approches (personnalisée, sociale et objet). Amazon possède un système très sophistiqué, les recommandations sont d’une part personnalisées en se basant sur le comportement individuel passé de l’utilisateur (historique de navigation et historique d’achat), et d’autre part Amazon utilise aussi les caractéristiques de l’article lui-même (recommandation objet) et les comportements d’autres personnes (recommandation sociale). Tous ceux qui ont déjà fait un achat sur Amazon ont probablement dû lire le message de la part d’Amazon qui nous dit “les gens qui ont acheté x ont aussi acheté y“.  Cette approche est tout simplement l’approche item-based nearest neighbor (item-centric ou item-based collaborative filtering) qu’on a décrit auparavant. Il semblerait que le système de recommandation d’Amazon représente plus du 30% du CA global de la société (en 2009)!

Recommandation Amazon

Amazon Recommendation System

Netflix est aussi un bon exemple de système hybride. Il propose des recommandations en comparant les habitudes de visionnage des films d’utilisateurs similaires (recommandation sociale) et suggère aussi des films qui partagent des caractéristiques avec des films que l’utilisateur a noté positivement (recommandation objet).

Google, lui se focalise aussi sur une combinaison de 3 approches pour améliorer son produit phare qui est son moteur de recherche:
  • Recommandation Personalisée:
    • Google customise nos résultats de recherche, quand cela est possible, en se basant sur notre localisation et/ou nos dernières recherches.
    • Lorsqu’on est connecté à notre compte Google, il propose un contenu encore plus pertinent en fonction de notre historique de recherche.
  • Recommandation Sociale:
    • L’algorithme du PageRank est de manière intrinsèque un outil basé sur de la recommandation sociale dans la mesure ou il utilise les liens entre les pages web.
    • L’utilisation de contenus provenant de nos cercles de Google+ est aussi une forme de recommandation sociale.
  • Recommandation Objet
    • Google utilise aussi une approche sémantique pour sa fonction « Did you mean » de son moteur de recherche.

Pandora vs Last.fm

La différence entre les approches de recommandation objet et de recommandation sociale (collaborative) peut être illustrée en comparant deux services de radio en ligne que sont Pandora (seulement disponible aux USA) et Last.fm.

Pandora utilise principalement une approche de recommandation objet. Le système se base sur les propriétés de la chanson et/ou de l’artiste, c’est à dire il décompose dans un premier temps les morceaux de musique afin de mettre en évidence ses propriétés intrinsèques. Chaque morceau de musique disposerait de plus de 400 attributs, permettant de déterminer une sorte de code génétique de la chanson (Music Genome Project). En comparant les propriétés similaires entre différents morceaux, le système arrive alors à nous proposer de nouvelles chansons à écouter, c’est-à-dire une sorte de station radio qui diffuse de la musique avec des propriétés susceptibles de correspondre à nos goûts. L’utilisateur peut ensuite indiquer s’il aime ou pas le morceau en écoute, et permet ainsi à Pandora d’affiner son filtre de recommandation en privilégiant (ou pas) certains attributs selon l’information venue en retour de l’utilisateur.

Recommandation Pandora

Last.fm lui utilise un filtre de recommandation sociale (collaborative). Le service crée une station de radio personnalisée en observant quels sont les groupes, artistes et chansons que l’utilisateur a écouté régulièrement et les compare avec les comportements d’écoute d’autre utilisateurs. Last.fm va alors proposer des morceaux fréquemment écoutés par des utilisateurs ayant des goûts similaires.

 Last.fm
Chaque type d’approche a ses avantages et inconvénients. En l’occurrence Last.fm requiert beaucoup d’information sur les habitudes d’écoute des utilisateurs afin de produire un système de recommandation efficace (problème du cold start). Pandora lui au contraire a besoin de très peu d’information sur l’utilisateur pour démarrer une radio personnalisée, mais doit disposer d’une base de données gigantesque sur le “génome” de chaque chanson.

Netflix Prize

De 2006 à 2009, Netflix a parrainé un concours, le Netflix prize, offrant un prix de $1’000’000 à celui qui à partir d’un set de données de plus de 100 millions de ratings de films pourrait offrir des recommandations 10% plus précises que celles générées par le système original de la compagnie Netflix. Le 21 septembre 2009, le prix a été attribué à une équipe appelée  BellKor’s Pragmatic Chaos. Les gagnants avaient misé sur un mélange de centaines d’approches algorithmiques et méthodes prédictives qui réunies ensemble permettent d’être plus performant dans la prédiction. La solution la plus performante semble donc bien s’appuyer sur un ensemble de méthodes algorithmiques plutôt que sur le raffinement et l’optimisation d’une seule technique spécifique.

Pour l’anecdote, le Netflix prize n’a pas été renouvelé en 2010, car malgré le fait que le set de million de données fournies aux participants du concours aient été rendues anonymes pour préserver l’identité des clients, deux chercheurs de l’Université du Texas ont été capables d’identifier des utilsateurs présents dans le set de données utilisé lors du concours en associant et croisant ces données avec des ratings de films soumis sur l’Internet Movie Database (IMDb). Il s’en est suivi qu’en décembre 2009, un des utilisateurs anonymes du set de données a poursuivi Netflix pour violation de la législation américaine en terme de confidentialité.

Efficacité d’un algorithme de recommandation

On a vu que la recommandation sociale (filtrage collaboratif) a l’avantage contrairement à la recommandation objet de permettre d’effectuer des prédicitions même lorsqu’il y a peu de information associée au contenu à recommander ou lorsque que le contenu est difficile d’analyser automatiquement (idées, opinions…) Mais la recommandation sociale souffre aussi d’inconvénients comme le cold start et le problème de rareté (sparsity).

Evaluer l’efficacité des algorithmes de recommandation est loin d’être trivial. En premier lieu, parce que différents algorithmes peuvent être meilleurs ou moins bons en fonction du set de données sélectionné et sur lequel ils sont appliqués. D’autre part, les objectifs fixés par un système de recommandation peuvent être divers et variés. Un système de recommandation peut être mis en place pour estimer avec exactitude la note que donnerait un utilisateur à un élément, alors que d’autres auront comme objectif principal de ne pas proposer des recommandations erronées.

On peut donc légitimement se demander jusqu’à quel point ces différentes méthodes de recommandation sont réellement efficaces. Pour déterminer l’efficacité d’un système, des indicateurs comme la précision et le recall sont utilisés.

La précision est un indicateur qui représente la qualité de la recommandation, c’est-à-dire à quel point les suggestions proposées sont conformes aux intérêts de l’utilisateur:

précision = nbre de suggestions pertinentes / nbre de suggestions

Le recall indique combien de suggestions pertinentes ont été recommandées à l’utilisateur par rapport au nombre total de suggestions pertinentes disponibles dans le système.

recall = nbre de suggestions pertinentes proposées à l’utilisateur / nbre de suggestions pertinentes totale

L’indicateur de précision permet de déterminer la probabilité qu’un élément recommandé soit pertinent.

L’indicateur de recall permet de déterminer la probabilité qu’un élément pertinent soit recommandé.

On utilise aussi des techniques statistiques pour mesurer l’efficacité d’un algorithme de recommandation. L’idée c’est d’évaluer la précision de la prédiction effectuée par le système en comparant les prédicitions avec les choix qu’aurait fourni l’utilisateur dans un cas réel. On utilise par exemple lErreur Moyenne Absolue (MAE) qui mesure la déviation des recommandation prédites avec les choix réels effectués par les utilisateurs. Plus l’erreur moyenne absolue est faible, meilleure est la prédicition.

Pour conclure, la meilleure mesure de l’efficacité d’un algorithme de recommandation et de la pertinence des suggestions c’est finalement la satisfaction de l’utilisateur, qui n’est pas toujours facile à bien identifier.

Sources:

http://www.readwriteweb.com/archives/recommendation_engines.php

http://fr.wikipedia.org/wiki/Syst%C3%A8me_de_recommandation

http://en.wikipedia.org/wiki/Recommender_system

http://en.wikipedia.org/wiki/Collaborative_filtering

http://recommender-systems.org/

http://www.it.uc3m.es/jvillena/irc/descarga.htm?url=practicas/06-07/31.pdf

http://www.docstoc.com/docs/35703482/Top-N-Recommendation-Algorithm-B

http://www.cs.utexas.edu/users/ml/papers/cbcf-aaai-02.pdf

http://www.amazon.es/Recommender-Systems-Introduction-Dietmar-Jannach/dp/0521493366

Musique et big data : une révolution dans l’approche du fait musical ?

 

Capture d’écran 2015-03-25 à 14.44.30

Tout d’abord, je voudrais remercier Milad Doueihi qui m’a adressé le texte présenté ci-dessous. Ce texte constitue à mon sens un tournant important dans l’étude du fait musical, dans la mesure où il entend proposer une approche “plus objective” non seulement des propriétés formelles des chansons mais également une relecture historique des courants musicaux. Mais si tournant il y a, c’est aussi et surtout parce que les termes d’un débat de fond entre les apports respectifs de la science computationnelle et des sciences humaines est posé.

“L’histoire de la musique populaire a longtemps été débattue par des philosophes, des sociologues, des journalistes et des stars de la pop …. Leurs thèses, bien que riches en folklore musical et en jugements esthétiques, manquent de ce que désirent les scientifiques : des tests rigoureux d’hypothèses claires basées sur des données quantitatives et des statistiques”. Disons le d’emblée, certains spécialistes des Big data ont développé un sentiment de toute puissance scientifique qui frise avec l’arrogance (voir par exemple : https://sendgrid.com/blog/data-scientists-beware-your-own-arrogance/) : le traitement des données à très grande échelle débouche parfois sur la pathologie du  “Big data hubris” dont la manifestation symptomatique la plus inquiétante est la tendance à disqualifier à bon compte les sciences humaines et sociales ; c’est bien vite oublier que les spécialistes de Big data ne sont pas forcément armés pour rendre compte du sens profond des faits sociaux… Le texte qui suit n’échappe pas, en partie, à ce type de défaut.

Toutefois, revendiquer une approche renouvelée et interdisciplinaire du fait musical – en n’esquivant pas les biais liés à la matière première de l’enquête (le journal Billboard) – a ceci d’intéressant qu’on y voit la musique sous un éclairage nouveau et singulier, un peu comme ces nouveaux microscopes numériques qui permettent aujourd’hui une relecture inédite des manuscrits de la Mer morte… On voit ainsi se développer aujourd’hui toute une série de travaux – j’aurai l’occasion d’y revenir dans un prochain article – qui, à l’aide de la science computationnelle, proposent de nouvelles approches centrées sur les propriétés structurelles des hits, de l’histoire du rock, etc. A coup sûr, il y a là matière à débats avec les musicologues – je pense à Phil Tagg notamment – aujourd’hui les plus autorisés sur les musiques populaires : débat épistémologique (sur les catégories esthétiques et génériques ; sur les éléments retenus pour l’analyse musicale : tempo, sonorités, etc.) mais également débat sur la façon dont nous construisons l’histoire sociale de ces musiques ou encore, débat sur la question de l’appauvrissement ou non de la variété musicale ces dernières années, question posée par Simon Reynolds dans son ouvrage sur la rétromanie, dont on voit bien qu’elle ne peut se régler simplement par un jugement moral ou encore une certaine idée du progrès ou de la régression dans l’histoire de la pop (je renvoie à ce sujet à l’article de Simon Frith, “Can music progress ? ” : http://www.doiserbia.nb.rs/img/doi/1450-9814/2007/1450-98140707247F.pdf)…

 

It’s only datascience, but I like it

Par le 24/03/15 | 2 commentaires | 841 lectures | Impression

La “science des données” nous permet elle d’apercevoir des patterns qui échappent à notre perception commune ? Dans le domaine des humanités numériques ou de l’anthropologie computationelle, on utilise de massifs corps de textes pour dégager des structures qui pourraient nous permettre une compréhension accrue de la culture … Ou pas. Un intéressant papier publié récemment dans Arxiv (et remarqué par l’excellent “Scoop it” sur la science de la complexité, Complexity Digest) applique ces méthodes à l’histoire de la musique populaire aux US entre 1960 et 2010, en gros donc depuis l’explosion du rock’n’roll.

02081Bien entendu, les chercheurs ne se sont pas servis de textes, mais d’un ensemble de données audio, ce qui est plus difficile. Ils ont donc recouru au Billboard Hot 100 américain et ont collecté 17094 chansons qui ont connu la gloire de ce hit-parade et en ont extrait des échantillons de 30 secondes sur lesquels ont porté leur analyse. Comme il ne s’agissait pas de textes, ils ont dû créer des “mots” basés sur les caractéristiques musicales des morceaux étudiés. Ils ont donc élaboré deux corpus, l’un de “thèmes harmoniques” et l’autre de “types de timbres”. Les thèmes concernent les successions d’accords utilisés. Par exemple, le thème nommé H1 dans l’étude concerne l’usage de la septième de dominante, un accord largement utilisé dans le blues et les musiques qu’il a directement inspiré. H8 représente une succession d’accords majeurs. Les “timbres”, quant à eux, représentent plutôt le type d’instrumentation et de sonorité, par exemple, “batterie, agressif, percussion”, ou “voie féminine, mélodique, vocale “. On analyse pour chaque morceau la présence des 8 thèmes harmoniques et des timbres. A noter que pour effectuer cette analyse, les chercheurs se sont basés sur un algorithme utilisé en général sur des corpus de textes.

Pour interpréter ces données très abstraites, les chercheurs ont employé les tags entrés par les utilisateurs de lastfm. Ils ont ensuite cherché à définir les styles de musique, mais ont trouvé que les termes usuels, rock, rap, disco, etc. étaient trop vagues pour capturer la diversité musicale, et que de surcroît ces appellations recouvraient bien souvent plus des notions d’âge ou d’origine ethnique et géographique que des différences purement musicales. Ainsi, la pop coréenne (k-pop) et le “rock classique” partagent en fait les mêmes caractéristiques; utilisant cette fois un algorithme issu de la bio-informatique, ils ont partagé les “tags” en 13 styles différents, où les appellations traditionnelles peuvent se retrouver dans diverses catégories : ainsi, dans le style 1 , on trouve le rap et le hip-hop associé, entre autres, à la house, la soul ou la dance. Mais on trouve le hip-hop et le rap également dans le style 2, cette fois en compagnie cette fois du reggae, des tags “urban” et même “comedy” (ce que je trouve un peu bizarre).

L’usage de technologies employées tant dans l’analyse de texte qu’en biologie nous montre en tout cas que cette nouvelle science des data se montre définitivement transdisciplinaire. Rappelons pour exemple les recherches de Marcello Montemurro dont les recherches couvrent à la fois la structure de l’ADN, le code informatique, la structure du cerveau ou l’étude de manuscrits anciens.

L’histoire de la musique revisitée

CaptureA partir de ces lexiques, les chercheurs ont cherché à comprendre l’évolution des tendances musicales de ces dernières décennies. Par exemple, le thème harmonique “bluesy”, H1, a vu sa fréquence diminuer de 75 % entre 1960 et 2009, ce qui signe, selon les auteurs du papier, “la mort lente du blues et du jazz au sein du Billboard”. D’autres thèmes restent stables, comme H8, qui représente les accords majeurs : deux tiers des morceaux du Billboard recourent à ces accords.

A partir de ces données, les auteurs tentent de reconstituer une histoire de la musique populaire, et les résultats sont parfois tout à fait contre-intuitifs.

Par exemple, si les chercheurs sont d’accord avec l’opinion commune selon laquelle la musique populaire aurait connu une série de révolutions, les dates qu’ils donnent pour ces phases de transformation sont plutôt inattendues: 1964, 1984 et 1991, la dernière étant la plus importante, selon eux. Donc, pas trace ni de la révolution psychédélique de 1967, ni de l’explosion punk de 1975-1977…

1964 peut se comprendre. N’est-ce pas la période qui a vu l’apparition de la fameuse British Invasion, avec les Beatles ou les Stones ? Mais pour les chercheurs, justement cette “invasion” a été largement surestimée. Pour eux, la multiplication des styles était déjà en bonne route à cette date : donc, les groupes anglais n’auraient pas initié cette révolution, ils l’auraient exploitée.
1983 se caractériserait par le leadership des styles new wave, disco et hard rock, au détriment des morceaux tagués soft rock, country et soul-Rn’B. Enfin 1991 verrait une explosion des styles associés aux tags rap et hip-hop, tandis que ceux assimilés au Rock connaissent une éclipse.

Enfin, les auteurs cherchent à répondre à la question piège : la variété musicale s’est-elle appauvrie au cours des dernières années ? La réponse serait négative. Il existe toujours aujourd’hui un grand nombre de styles. La variété musicale a bien connu une période de resserrement, mais c’était au début des années 80, avec une réduction du nombre de timbres utilisés : en effet, à cette époque, le timbre T1 (“”batterie, agressif, percussion”) lié à la fois au disco et à la new wave, et T5 (“guitare, son élevé, énergétique”) comme dans le hard rock, trustent les sommets des charts. Ces deux tendances allaient ensuite d’effacer devant T3, le hip-hop et le rap. L’histoire de T1 est digne d’intérêt, car elle montre l’interaction entre technologie et style artistique. Ce timbre continue à être populaire jusqu’en 1990, et est lié à la popularisation des boites à rythmes ; à partit de 1990, il reflue : “le règne des boites à rythmes était terminé”, nous disent les chercheurs.

La science des data est-elle mûre pour expliquer la culture ?

Évidemment lorsqu’on consulte de telles recherches, on ne peut que se demander si elles capturent réellement des évolutions qui nous sont imperceptibles, ou si au contraire elles constituent l’équivalent de classer les grandes œuvres littéraires en fonction du nombre de caractères, de la fréquence de la lettre “e” ou le classement des ventes chez Amazon. Les choses sont probablement plus complexes : ce type de travaux nous permet de remettre en perspective certains présupposés : le rappel que la variété musicale ne s’est pas appauvri ces dernières années contribue par exemple à faire taire le vieux con qui sommeille en chacun de nous.

Cela dit, on ne peut s’empêcher de se poser certaines questions et de mettre en lumière des limites. Les auteurs du papier en sont conscients : leur étude est biaisée, reconnaissent-ils, par le choix du Billboard comme source. Il est bien sûr normal de devoir choisir un échantillon au milieu d’une telle masse de données, on ne peut faire autrement. Mais cet échantillon est-il représentatif, significatif ? Lorsqu’on regarde les archives du Billboard, on ne peut s’empêcher de remarquer que les morceaux les plus marquants, ceux qui ont changé notre perception de la musique, n’ont souvent pas figuré dans ce palmarès. Par exemple, le Velvet Underground, groupe qui oeuvra dans les sixties, mais devint une influence majeure du rock à partir de la fin des années 70, n’a classé que trois albums (pas de chansons) au sein du Billboard (le site n’indique pas les dates où ces disques se sont retrouvés dans les charts, mais au moins deux des albums mentionnés datent de bien après la dissolution du groupe). Brian Eno a bien explicité le rôle historique du Velvet lorsqu’il a déclaré “leur premier album n’a été acheté que par 1000 personnes, mais chacune d’entre elles a ensuite créé son groupe”. Les Doors, autre groupe très influent, sont un peu mieux lotis. Mais bon nombre de leurs “grands classiques”, comme “The End” ou “When the music is over”, ne figurent pas dans le hit parade. Quant au Rap, il a peut-être explosé en 1991, mais il effectuait déjà sa petite révolution en 1979 avec Sugarhill Gang et leur “Rapper’s Delight”. Il n’était pas difficile pour un être humain de prédire sa montée en puissance dès le début des années 80, ce que manifestement, les algorithmes ne repèrent pas. Et l’absence des mouvements de 1967 et 1977 est tout de même très gênante.

Le papier commence par ces lignes : “L’histoire de la musique populaire a longtemps été débattue par des philosophes, des sociologues, des journalistes et des stars de la pop …. Leurs thèses, bien que riches en folklore musical et en jugements esthétiques, manquent de ce que désirent les scientifiques : des tests rigoureux d’hypothèses claires basées sur des données quantitatives et des statistiques”. Le problème est que ce papier montre exactement le contraire : ces données sont limitées par leur abandon de toute subjectivité liée à un domaine qui est avant tout… subjectif. Les Anglais de 1965 n’ont peut-être rien apporté de nouveau en terme d’accords ou de timbres; mais ils signifiaient quelque chose de nouveau. Et c’est pareil pour le psychédélisme, le punk et le hip-hop. Il ne s’agit pas de rejeter de telles recherches qui nous apportent sans aucun doute des éclairages inédits sur certains aspects de la culture ; mais ils ne remplacent pas – encore ? – les écrits d’un Greil Marcus. Un jour peut-être, qui sait, élaborera-t-on des systèmes algorithmiques susceptibles de prendre en compte la signification des différents mouvements culturels ou historiques. Mais aujourd’hui nous ne savons pas encore quels échantillons choisir, ni ce qu’il faut calculer au juste.

Rémi Sussan