2 Allgemeine Entwicklerhinweise¶

2.1 Zusammenfassung des aktuellen Stands¶

Libmunin ist eine in der Programmiersprache Python geschriebene Bibliothek und implementiert ein Musikempfehlungssystems auf Graphen–Basis. Der dahinterstehende Graph bildet die Nachbarschaftsbeziehungen zwischen den einzelnen Musikstücken (als Knoten) mittels bidirektionaler Kanten ab. Eine Kante verbindet zwei ähnliche Songs miteinander. Um den Graphen aufbauen zu können, müssen, während des sogenannten Kaltstartes, vom Nutzer der Bibliothek alle Songs mit allen relevanten Attributen eingegeben werden. Damit libmunin weiß, wie die einzelnen Werte zu behandeln sind, wird jedem Attribut (Künstler, Titel, Genre...) ein sogenannter Provider und eine Distanzfunktion zugeordnet.

Ein Provider normalisiert einen Wert anhand verschiedener Charakteristiken. Sein Ziel ist es, für die Distanzfunktion einfache und effizient vergleichbare Werte zu erzeugen, da die Distanzfunktion sehr viel öfters aufgerufen wird als der Provider. Die Distanzfunktion erzeugt dann aus diesen normalisierten Werten eine Distanz, also ein Maß dafür, wie ähnlich diese Werte sind. Die Distanzen gehen dabei von \(0\) (vollkommen ähnlich) bis \(1\) (absolut unähnhlich). Libmunin implementiert eine große Anzahl von vorgefertigten Providern und Distanzfunktionen für gängige Attribute, wie dem Genre, den Audiodaten oder den aus den Liedtext extrahierten Schlüsselwörtern.

Aus den einzelnen Distanzen wird dann der obige Graph aufgebaut. Um aus diesen Graphen dann Empfehlungen abzuleiten, werden einzelne Knoten, sogenannte Seedsongs, nach bestimmten Kriterien ausgewählt. Beginnend von diesen wird eine Breitensuche gestartet, also eine sich kreisförmig vom Seedsong ausbreitende Traversierungstrategie. Bereits besuchte Knoten werden dabei nicht nochmal besucht. Die einzelnen besuchten Knoten werden, nach dem Filtern von doppelten Künstlern und Alben, dann als Empfehlungen angenommen

Zudem lernt libmunin während einer Sitzung vom Nutzer, indem es die Gewohnheiten des Nutzers beobachtet und daraus Regeln ableitet. Diese Regeln verbinden zwei Mengen von Songs , die oft miteinander gehört werden, mit einer Wahrscheinlichkeit miteinander. Alle gehörten Songs werden in einer Historie abgespeichert. Im Vergleich zu bestehenden Systemen ist libmunin nicht von den Audiodaten abhängig, sondern kann durch seine flexible Schnittstelle auch alleine auf den Metadaten eines Stückes, wie den Tags eines Musikstückes, operieren. Ein Tag ist eine direkt in der Audiodatei hinterlegte Information um bestimmte Werte wie den Künstler des Stückes zu beschreiben. Das erklärte Ziel der Bibliothek ist es, eine freie Bibliothek zu schaffen, die sowohl offline (in Musicplayern) als auch online (in Streamingdiensten) funktioniert und mit großen Datenmengen umgehen kann. Durch die GPLv3–Lizenz [Link–2] ist ein libertärer, weitläufiger Einsatz möglich.

2.2 Der Begriff der Distanzfunktion¶

Eine Distanzfunktion ist im Kontext von libmunin eine Funktion, die zwei Songs als Eingabe nimmt und die Distanz zwischen diesen berechnet.
Dabei wird jedes Attribut betracht, welches in beiden Songs vorkommt. Für diese wird von der Maske eine spezialisierte Distanzfunktion festgelegt, die weiß wie diese zwei bestimmten Werte sinnvoll verglichen werden können. Die so errechneten Werte werden, gemäß der Gewichtung in der Maske, zu einem Wert verschmolzen.
Fehlen Attribute in einen der beiden Songs, wird für diese jeweils eine ,,Straf"–Distanz von \(1\) angenommen. Diese wird dann ebenfalls in die gewichtete Oberdistanz eingerechnet. Die folgenden Bedingungen müssen sowohl für die allgemeine Distanzfunktion als auch für die speziellen Distanzfunktionen gelten. \(D\) ist dabei die Menge aller Songs, \(d\) eine Distanzfunktion. Beim Schreiben von Distanzfunktionen sollte versucht werden, alle dieser Eigenschaften zu erfüllen. Technisch nötig sind dabei nur die Bedingungen 1–3. Bedingung 4 sollte aber aus unten genannten Gründen ebenfalls eingehalten werden.

(a) Ohne Einhaltung der Dreiecksungleichung.

(b) Mit Einhaltung der Dreiecksungleichung.

Figure 2.1: Die Beziehung dreier Songs untereinander. Die Dreiecksungleichung besagt, dass der direkte Weg von A nach B kürzer oder gleich lang sein sollte als der Umweg über C. Die einzelnen Attribute ,,a“ und ,,b“ sind gleich stark gewichtet. Wenn keine Straftwertung für leere Werte gegeben wird, so sind die Umwege manchmal kürzer.

1. Uniformität: \(\;0 \leq d(i, j) \leq 1 \;\;\forall\;\; i,j \in D\)

   Aussage: Die errechneten Werte sollten sich immer zwischen und einschließlich \(0\) und \(1\) befinden. Libmunin schneidet die Werte nötigenfalls auf diesen Bereich zu.

2. Symmetrie: \(\;d(i, j) = d(j, i) \;\;\forall\;\; i,j \in D\)

Aussage: Die Reihenfolge, in der die Songs der Distanzfunktion übergeben werden, darf keine Auswirkung auf das Ergebnis haben. Diese Eigenschaft wird von libmunin nicht überprüft — eine Nichteinhaltung würde zu falschen Kanten im Graphen führen.

3. Identität: \(\;d(i, i) = 0 \;\;\forall\;\; i \in D\)

   Aussage: Wird zweimal der selbe Song übergeben, so muss die Distanz immer \(0\) betragen. Autoren von Distanzfunktionen sollten dies testen. Werte \(\neq 0\) deuten auf fehlerhafte Distanzfunktionen hin.

4. Dreiecksungleichung: \(\;d(i, j) \leq d(i, x) + d(x, j) \;\;\forall\;\; i,j,x \in D, i \neq j \neq x\)

   Aussage: In einer Dreiecksbeziehung zwischen drei Songs muss der direkte Weg zwischen zwei Songs immer kürzer oder gleich lang wie der Umweg über den dritten Song sein. Dies ist in Abbildung 2.1 gezeigt. Diese Eigenschaft ist nötig, damit man annehmen kann, dass direkte Nachbarn ähnlicher sind als indirekte Nachbarn.

2.3 Zur Nuztung von libmunin¶

Die Qualität der Empfehlungen kann nur so gut sein, wie die Qualität der Eingabedaten. Da in den meisten Fällen die Metadaten zu den einzelnen Liedern aus den Tags der Audiodateien kommen, empfiehlt es sich, diese vorher mit Musiktaggern einheitlich zu pflegen. Der Autor empfiehlt hierfür Picard [Link–3], welches im Hintergrund auf Musicbrainz [Link–4] zugreift. Für schwerer zu besorgende Daten, wie Liedtexte, kann unter anderem auf libglyr [Link–5], beets [Link–6] oder dem eingebauten PlyrLyricsProvider (sucht im Web nach Liedtexten) und DiscogsGenreProvider (sucht bei Discogs [Link–7] nach der Genrebezeichnung) zurückgegriffen werden.

Welche Lieder man zu libmunin's Historie hinzufügt, sollte abgewogen werden. Fügt man auch Lieder ein, welche vom Nutzer einfach übersprungen worden sind, so sind die erstellten Regeln nicht repräsentativ. Es sollten nur Lieder hinzugefügt werden, welche mehr als \(50\%\) angehört worden sind.

Um das Format der Musiksammlung zu spezifizieren, muss der Nutzer der Bibliothek bei einer neuen Sitzung eine Maske angeben. In dieser werden die Provider und Distanzfunktionen für die einzelnen Attribute eines Songs festgelegt. Mit der EasySession bietet libmunin aber eine Sitzung mit vorgefertigter Maske. Anwendungsentwickler sollten aber nach Möglichkeit eine eigene, für ihre Zwecke konfigurierte, Session–Maske verwenden. Zwar ist der Einsatz der vorgefertigten EasySession deutlich einfacher, doch ist diese mehr für den schnellen Einsatz gedacht. Zudem sollte es dem Endanwender möglich gemacht werden, die Gewichtungen der einzelnen Attribute zu ändern.

2.4 Zur Erweiterung von libmunin¶

Oft ist es von Interesse neue Distanzfunktionen und Provider für eigene Zwecke zu schreiben. Beispielsweise könnte man ein Paar aus Provider und Distanzfunktion verfassen um die einzelnen Mitglieder einer Band automatisch aus dem Netz zu besorgen und mit anderen Bands zu vergleichen, um Relationen zu finden. Im Folgenden werden einige Beispiele gegeben und Stolperfallen aufgelistet.

2.4.1 Hinweise zum Schreiben von Distanzfunktionen¶

Wenn eine Distanzfunktion eine Menge von Elementen vergleichen muss, so besteht dieselbe oft aus einem Fusionierungsverfahren und einer weiteren Metrik, die die einzelnen Elemente untereinander vergleicht. Ein Fusionierungsverfahren verschmilzt mehrere Teildistanzen auf definierte Weise zu einer Gesamtdistanz. Als Beispiel kann man hier den Vergleich von zwei Mengen von Wörtern nennen. Einzelne Wörter kann man relativ einfach auf Ähnlichkeit untersuchen ¹. Ein simples Fusionierungsverfahren wäre hier, jedes Wort aus der einen Menge mit jedem Wort aus der anderen Menge zu vergleichen und den Durchschnitt der Einzeldistanzen als Ergebnis anzunehmen. Ein anderes Fusionierungsverfahren nimmt statt dem Durchschnitt die kleinste gefundene Distanz. Hier gibt es kein richtig oder falsch. Je nach Einsatzzweck, muss ein passendes Verfahren gewählt werden. Der dazugehörige Wikipedia–Artikel bietet, unter dem Punkt Fusionierungsalgorithmen, einen guten Überblick über weitere Verfahren: [Link–8].

Distanzfunktionen sollten schlechte Werte abstrafen und gute belohnen. Während der Entwicklung hat sich gezeigt, dass simple Distanzfunktionen, die auch für gar nicht mehr ähnliche Werte eine Distanz errechnen, die \(\neq 1,0\) ist, zu qualitativ schlechten Verbindungen im Graphen führen. Man sollte daher den Bereich, in denen man eine Distanz \(< 1,0\) vergibt, einschränken.

Figure 2.2: Die blaue Kurve zeigt die skalierten Werte der Distanzfunktion in Blau. Werte unter 0,5 werden etwas herabgesetzt, schlechtere Werte über 0,5 werden erhöht. Zur Referenz ist die ursprüngliche Gerade in Grün gegeben.

Im folgendem Beispiel wird dies nicht getan und in der nachfolgenden Version verbessert:

from munin.distance import DistanceFunction

# Eine Distanzfunktion, die beispielsweise ein Rating von 1-5 vergleicht.
# Leite von der Distanzfunktions-Oberklasse ab:
class WrongDistanceFuntion(DistanceFunction):
    def do_compute(self, A, B):
        # A und B sind, der Konsistenz halber auch bei einzelnen Werten immer Tupel
        # Daher müssen wir diese erst "entpacken".
        a, b = A[0], B[0]
        return abs(a - b) / max(a, b)  # Teile Differenz durch Maximum aus beiden:

class CorrectDistanceFuntion(DistanceFunction):
    def do_compute(self, A, B):
        diff = abs(A[0] - B[0])
        if diff > 3:
           return 1,0    # Zu unterschiedlich.
        return diff / 4  # Verteile auf [0, 0.25, 0.5, 0.75]

Manchmal ist eine Eingrenzung des Bereichs nicht so einfach möglich, vor allem wenn komplexere Daten im Spiel sind. Dann empfiehlt es sich, die Verteilung der Distanz auf den Bereich zwischen \(0,0\) und \(1,0\) zu untersuchen. Sollte sich die Distanz beispielsweise gehäuft im Bereich zwischen \(0,3\) und \(0,7\) bewegen, so ist es empfehlenswert diesen Bereich zu dehnen. In Abbildung 2.2 werden mit der Funktion ² \(f(x) = -2\frac{2}{3}x^{3} + 4x^{2} - \frac{1}{3}x\) Distanzen unter \(0,5\) verbessert und darüber verschlechtert.

from munin.provider import Provider

class DoublingProvider(Provider):  # Leite von der Provider-Oberklasse ab.
    def __init__(self):
        # Kompression anschalten, ansonsten muss auf nichts geachtet werden.
        Provider.__init__(self, compress=True)

    def do_compute(self, input_value):  # Wird bei jeder Eingabe aufgerufen.
        return input_value * 2  # Verdoppele den Input.

2.5 Vergleich verschiedener Playlisten¶

Eine Playlist, zu deutsch Wiedergabeliste, ist eine Liste einzelner Lieder, die nacheinander abgespielt werden. Die Zusammstellung einer Playlist erfüllt oft einen gewissen Zweck. So stellt man für gewöhnlich Lieder in einer Playlist zusammen, die eine gemeinsame Stimmung oder eine andere Gemeinsamkeit (,,Favoriten") besitzen. Im Folgenden wird die subjektive Qualität der Playlisten bezüglich der Ähnlichkeit der einzelnen Stücke beurteilt.

In Abbildung 2.4 wird eine Auflistung verschiedener, mit unterschiedlichen Methoden erstellter Playlisten gegeben. Dies ist interessant, da die Struktur der von libmunin gegebenen Empfehlungen gewissen Regeln unterliegt, die man als Anwendungsentwickler kennen sollte. Zudem ist der subjektive Vergleich mit anderen Systemen interessant.

Der ursprüngliche Plan, hier auch eine von last.fm [Link–10] erstellte Playlist zu zeigen, wurde eingestellt, da man dort die Empfehlungen nicht auf die hier verwendete Testmusiksammlung aus 666 Songs einschränken konnte. Stattdessen wurde eine Alternative zu libmunin getestet: Mirage [2]. Da Mirage momentan nur als Plugin für Banshee vorhanden ist und nicht als allgemeine Bibliothek verfügbar, wurde die Testmusikdatenbank auch in Banshee importiert. Die Testmusikdatenbank selbst besteht aus einigen ausgewählten Alben des Autors. Viele allgemein gebräuchliche Genres werden dabei abgedeckt, obwohl der Schwerpunkt beim Genre Rock und Metal liegt. Die einzelnen Playlisten wurden auf jeweils 15 Songs begrenzt. Darin enthalten ist an erster Stelle der willkürlich ausgewählte Seedsong, der zum Generieren der Playlist genutzt wurde (Knorkator — Böse). Die zufällig erstellte Playlist wurde als Referenz abgedruckt, damit man die dort fehlende Struktur sehen kann.

Auffälligkeiten:

Bei libmunin wiederholt sich der Künstler Knorkator alle 3–5 Stücke, da der Filter entsprechend eingestellt ist. Daher ist eine Wiederholung des Künstlers nur alle drei und eine Wiederholung des Albums nur alle fünf Stücke erlaubt. Bei Mirage scheint lediglich eine direkte Wiederholung des Künstlers ausgeschlossen zu sein. Ansonsten wiederholen sich die Künstler beliebig. Die zufällige Playlist hat zwar auch keinerlei Wiederholungen, aber entbehrt dafür auch jeglicher Struktur.

Mirage leistet gute Arbeit dabei, ähnlich klingende Stücke auszuwählen. Der tempomäßig vergleichsweise langsame Seedsong (Mirage besitzt hier tatsächlich ein ähnliches Konzept) besitzt eine dunkle Stimmung und harte E–Gitarren. Die von Mirage vorgeschlagenen Songs sind hier tatsächlich sehr passend zu dieser Stimmung. Die von libmunin vorgeschlagenen Songs sind in Punkt Audiodaten, bei weitem nicht so übereinstimmend. Was aber auffällig ist, ist dass größtenteils deutsche Titel (wie der Seedsong) vorgeschlagen werden. Auch führt das Parody in der Genre–Beschreibung dazu, dass ebenfalls lustig oder ironisch gemeinte Lieder vorgeschlagen werden. Zwar ist die Stimmung im Seedsong düster, doch wird textlich ein Thema ironisch behandelt — was Mirage an den Audiodaten natürlich nicht erkennen kann. Hier zeigt sich libmunin's (momentaner) Fokus auf Metadaten. Bei der zufälligen Playlist stimmen die Genres einigermaßen überein, doch liegt das eher an dem sehr dehnbaren Begriff Rock, der bei Discogs [Link–7] für sehr viele Lieder eingepflegt ist.

Der Kaltstart bei Mirage verlief in wenigen Minuten, während der Kaltstart bei libmunin beim ersten Mal für die 666 Songs im Vergleich dazu sehr lange (etwa 53 Minuten) benötigte. Größtenteils liegt das daran, dass für jedes Lied ein Liedtext sequentiell automatisch besorgt wird. Siehe dazu auch Tabelle 2.3. Bei der Ausgabe der Empfehlungen selbst, war bei allen Methoden keinerlei Verzögerung zu beobachten.

2.6 Ressourcenverbrauch¶

Damit Anwendungsentwickler die Aufwändigkeit einzelner Operation einschätzen können, wird in Tabelle 2.3 eine kurze Übersicht über den Ressourcenverbrauch einzelner Aspekte gegeben. Die gemessenen Werte beziehen sich stets auf die Testumgebung mit 666 Songs.

Wie man sieht, sollte noch unbedingt Zeit investiert werden um den Kaltstart zu beschleunigen. Auch die modify–Operation könnte durchaus noch optimiert werden. Wie allen anderen Geschwindigkeitsangaben in dieser Arbeit, beziehen sich diese auf den Rechner des Entwicklers und sind daher nur untereinander vergleichbar.

Footnotes