Download: delicious_mates.py

On the social bookmarking site del.icio.us, you can add other users to your network to see their recent bookmarks aggregated on one page. There are two kinds of people in my network: 1. Friends and 2. Users I don’t know personally, but who regularly post interesting links. People who bookmark the same things that I bookmark are likely to have similar interests and are thus likely to continue bookmarking interesting things in the future. Since the information on who bookmarked what URL is public, the process of finding people with similar interests can be automated.

Urban Hafner brought up this idea three years ago, but I could not find an implementation. Yesterday, I wrote a short Python (2.5) script that implements the following ideas:

1. Look at every link in your bookmarks: Who bookmarked the same page? Add these users to a list of people possibly similar to you.
2. The more bookmarks another user has in common with you, the higher your similarity.
3. The smaller the number of people who bookmarked a page, the more significant the fact that another user has this bookmark in common with you.
4. If a user has lots of bookmarks, common bookmarks are less remarkable. The percentage of common links counts.

Here is what you need to do to find people whose interests are similar to yours:

1. Download delicious_mates.py
2. Run python ./delicious_mates.py
3. Wait — this takes some time.

Then, what you will see will look something like this:

andreas> python ./delicious_mates.py
Your del.icio.us username? andreas.s
Your del.icio.us password?

Fetching list of bookmarks ... (485)

Fetching list of users for each bookmark ...
    1. http://en.wikipedia.org/wiki/Langton's_ant (7)
    2. http://www.nytimes.com/2008/05/13/science/13coat.html?_r=2&partner=rssnyt&emc=rss&oref=slogin&oref=login (0)
    3. http://sifter.org/~simon/journal/20080509.2.html (2)
    4. http://www.intercult.su.se/cultaptation/tournament.php (16)
    5. http://www.pnas.org/cgi/content/abstract/0801268105v1 (49)
    6. http://atlas-conferences.com/c/a/n/i/15.htm (0)
	[..]
    480. http://lifeboat.com/ex/main (129)
    481. http://prize.hutter1.net/ (137)
    482. http://www.psg.com/~dlamkins/sl/cover.html (194)
    483. http://www.idsia.ch/~juergen/ (157)
    484. http://sl4.org/wiki/ShannonInformation (1)
    485. http://www.scottaaronson.com/writings/ (13)

Finding 50 candidates from list of 49937 users ...
    rainer (42/9367) ok
    siggiB (36/1006) ok
    fhtagn (35/2471) ok
    anissimov (35/6281) ok
    jbone (41/19982) ok
    invisibleandpink (16/203) ok
    irchans (16/610) ok
    ferrouswheel (14/946) ok
	[..]
    eggywat (14/4290) ok
    Cunya (8/3133) ok
    getpost (13/9787) ok
    hannu (12/3915) ok
    lispmeister (11/2967) ok
    dean.vanniekerk (12/5873) ok
    rgrant (9/1769) ok

Top 50 del.icio.us mates:
username             weight               # common bookmarks   # total bookmarks    % common
——————————————————————————————————————————————————————————————————————————————————————————————
siggiB               54.92937             36                   1022                 3.52250
invisibleandpink     53.05635             16                   203                  7.88177
fhtagn               20.61878             36                   2474                 1.45513
irchans              15.61606             16                   611                  2.61866
fogeli               12.85109             16                   628                  2.54777
ferrouswheel         7.99177              14                   946                  1.47992
rainer               7.60971              43                   9423                 0.45633
anissimov            6.46154              34                   6309                 0.53891
pdorrell             4.10251              19                   3041                 0.62479
jefallbright         3.87392              12                   1193                 1.00587
ladro                3.76458              12                   1526                 0.78637
miguel1626           3.04347              11                   1039                 1.05871
jbone                2.62672              41                   20039                0.20460
hartmut              2.15612              9                    1316                 0.68389
asciilifeform        2.04304              10                   1581                 0.63251
tmalin               1.89627              12                   2181                 0.55021
herrmann             1.84991              21                   5410                 0.38817
jas0nm               1.82646              20                   3808                 0.52521
[..]

If you look at the script, you will find a few settings you might want to change. For each of these holds: The higher you set them, the more time it takes for the script to finish.

• MAX_MATES

  is the maximum number of similar users the script suggests.

• MAX_BOOKMARKS

  defines how many of your bookmarks the script will look at.

• BOOKMARK_FILTER

  defines which types of bookmarks are analyzed. Remove

  , "no"

  from

  {"shared" : [None, "yes", "no"]}

  to exclude private bookmarks.

• MATE_MIN_BOOKMARKS

  sets a minimum for the number of bookmarks a del.icio.us user needs to have before he can be considered to be similar to you.

• MATE_MIN_COMMON

  sets a minimum to the number of bookmarks a user has to have in common with you to be included in the list of similar users.

The script needs two Python modules, the parser BeautifulSoup and Michael Noll’s del.icio.us Python API. If the script does not find one of the modules, it will download the missing module to the current directory and import it from there. If you don’t like this because you believe this is a security nightmare (which it is), don’t run delicious_mates.py install the two modules beforehand.

Do you know some Javascript and have spare time? I would love to see the script converted into a direc.tor-like bookmarklet. The need to download and run a Python script makes finding similar users more complicated than it chould be.

The feature I like best about the online bookshelf LibraryThing is its Unsuggester: Name a book you have read and it suggests those books that are least likely to be on your bookshelf. I like it because it is a means to counteract the temptation to adjust your sources of information such that whatever you read reinforces your point of view. Seeing how easy it is to give in to this temptation, is a script that makes it easier to surround yourself with like-minded people just one more sign of a general trend towards biased, largely isolated online communities?

Ich habe einige Zahlen, will die nächste in der Folge vorhersagen und weiß nichts über die Herkunft der Zahlen. Kann ich eine Vorhersage treffen? (Nein.)

1010101010101010101010101010101010101010_

Nun habe ich dieselben Zahlen, darf aber annehmen, dass einfache Erklärungen wahrscheinlicher sind als komplizierte. Kann ich jetzt eine Vorhersage treffen? (Nein.)

1010101010101010101010101010101010101010_

Ich nehme zusätzlich an, dass die Folge auf irgendeine Weise berechnet werden kann. Kann ich jetzt die wahrscheinlichste nächste Zahl vorhersagen? (Nein, nicht in endlicher Zeit. Das allgemeine Vorhersageproblem ist unlösbar.)

1010101010101010101010101010101010101010_

Kann ich einen Algorithmus schreiben, dessen Ausgabe gegen die wahrscheinlichste nächste Zahl konvergiert, wenn die Laufzeit gegen geht? (Ja. Dovetailer über alle möglichen Programme, angefangen mit dem kürzesten; die Ausgabe des kürzesten Programms, das die Zahlen und eine zusätzliche ausgibt, ist die aktuelle Hypothese.)

Wir Menschen treffen jeden Tag Vorhersagen. Der Vorteil, den wir gegenüber derzeitigen Algorithmen haben, liegt in den zusätzlichen Annahmen, die wir unbewusst machen, in der Art von inductive bias, mit dem uns die Evolution ausgestattet hat. Die Aufgabe von Forschern auf dem Gebiet des maschinellen Lernens ist es, den Suchraum von Algorithmen derart einzuschränken, dass die Laufzeit der Algorithmen polynomiell wird, und dabei möglichst wenige Lösungen für Vorhersageprobleme auszuschließen, die für unsere Welt relevant sind.

Projektidee: Ein automatisch erstelltes und aktualisiertes Ranking von Algorithmen für maschinelles Lernen macht Fortschritte auf dem Gebiet der allgemeinen künstlichen Intelligenz sicht- und messbar.

Das Messverfahren

Lernverfahren wie rekurrente neuronale Netze, Markov-Modelle und genetische Algorithmen sollen akkurate Vorhersagen liefern. Wissenschaftliche Veröffentlichungen sprechen davon, dass der jeweils vorgestellte Algorithmus “auf gewisse Weise” optimal ist. Für das Gebiet der allgemeinen künstlichen Intelligenz ist interessant, zu wissen, welcher Algorithmus allgemein am besten geeignet ist, d.h. für die Vorhersage von Sequenzen, über die wir lediglich wissen, dass sie von einem berechenbaren Prozess generiert wurden und dass einfache Erklärungen wahrscheinlicher sind als komplizierte.

Eine Sequenz ist eine endliche oder unendliche Folge von Symbolen eines Alphabets (z.B. {0, 1}). Die meisten endlichen Sequenzen sind nicht effektiv lernbar, da kein Programm mit im Vergleich zur Sequenz kurzer Beschreibung existiert, das diese Sequenzen deterministisch ausgibt. Das heißt: Die Kolmogorov-Komplexität der meisten endlichen Sequenzen entspricht der Länge der Sequenzen. Für den Vergleich verschiedener Lernalgorithmen beschränken wir uns auf unendliche Sequenzen mit endlich langen Erzeugerprogrammen.

Ein Vorhersagealgorithmus ist dann allgemein besser als ein anderer, wenn er lernen kann, Sequenzen mit höherer Kolmogorov-Komplexität vorherhersagen (und beide einfache Sequenzen gleich gut vorhersagen können). Praktisch jeder Algorithmus wird folgende Sequenz von sehr niedriger Komplexität lernen können:

111111111111111111111111111111111111111111...

Bei etwas höherer Komplexität werden einige Algorithmen Probleme bekommen:

011011100101110111100010011010101111001101...

Hätte man eine Datenbank, die jedes sequenzerzeugende Programm (oder jede Sequenz) sowie die Komplexität der von jedem Programm generierten Sequenz speichert, so könnte man für eine Reihe von Algorithmen Tests durchführen, um herauszufinden, in welchem Umfang und bis zu welcher Komplexität jeder Algorithmus Sequenzen lernen kann. Mit den Ergebnissen dieser Tests ließe sich ein Ranking erstellen, das auf einen Blick verrät, welcher Algorithmus die meisten und komplexesten Sequenzen lernen kann.

Eine solche Datenbank ist unmöglich: Es gibt unendlich viele sequenzerzeugende Programme, die Sequenzen sind unendlich lang und deren Komplexität ist nicht algorithmisch bestimmbar.

Die Menge der sequenzerzeugenden Programme ist eine Teilmenge aller Programme, und diese Menge ist aufzählbar unendlich. Die Kolmogorov-Komplexität ist definiert als die Länge des kürzesten Programms, das eine Sequenz erzeugt. Generiert man alle Programme, angefangen mit dem kürzesten, so ist bekannt, ob bereits ein kürzeres Programm den gleichen Sequenzbeginn (eine festgelegte Anzahl von Zeichen, z.B. 10.000) erzeugt hat oder ob die Länge des gerade betrachteten Programms als Abschätzung der Komplexität der erzeugten Sequenz verwendet werden kann — Abschätzung deshalb, weil nur eine endliche Anzahl der Zeichen zweier Sequenzen verglichen werden können und nach Rice nicht algorithmisch festgestellt werden kann, ob zwei Programme die gleiche Funktion berechnen.

Mit einigen Abschätzungen ist es möglich, Ausschnitte der beschriebenen Datenbank zu erstellen, die in der Komplexität nach oben beschränkt sind:

1. Wir generieren der Reihe nach Turingmaschinen mit leerem Eingabe- bzw. Arbeitsband und nur in einer Richtung beschreibbarem Ausgabeband, angefangen mit der kürzesten.
2. Uns interessieren nur Turingmaschinen, die unendliche Sequenzen generieren:
   • Hält eine Turingmaschine an, so verwerfen wir diese Turingmaschine.
   • Hat eine Turingmaschine nach 10^12 Schritten noch keine 10.000 Ausgabesymbole erzeugt, so verwerfen wir diese Turingmaschine.

   Andernfalls nehmen wir an, dass die aktuelle Turingmaschine eine der Turingmaschinen ist, die eine unendliche lange Sequenz ausgeben (Abschätzung I).

3. Wenn die ersten 10.000 Zeichen der Sequenz, die eine Turingmaschine erzeugt, noch von keiner anderen Turingmaschine erzeugt wurden, speichern wir die Länge der Beschreibung der Turingmaschine sowie die 10.000 Zeichen der Sequenz in einer Datenbank.
4. Die gespeicherte Länge entspricht in etwa der Länge der kürzesten Turingmaschine, die die Sequenz generiert und ist damit ein Maß für die Kolmogorov-Komplexität der Sequenz (Abschätzung II).

Das wiederholen wir, bis die Datenbank “groß genug” ist. In einer 150 GB großen Datenbank lassen sich bei 10.000 Zeichen pro Sequenzabschnitt etwa 100 Millionen unterschiedliche Sequenzabschnitte speichern.

Der kritische Punkt

Ist die Komplexität der einfachsten in der Datenbank gespeicherten Sequenzen so gering, dass diese mit den meisten Vorhersagealgorithmen gelernt werden können und die Komplexität der komplexesten Sequenzen so groß, dass das Lernen der Sequenz mit aktuellen Vorhersagealgorithmen nicht mehr möglich ist?

Werden in dieser Datenbank “interessante” Sequenzen — Sequenzen von nichttrivialer Komplexität — vorkommen? Oder lediglich 50 Millionen unterschiedliche, sich wiederholende Muster? Wie sieht es aus, wenn die einfachsten Sequenzen herausgefiltert und verworfen werden? Wie sieht es aus, wenn stets der Großteil der Sequenzen verworfen wird, die von den Top 20 Algorithmen zuverlässig vorhergesagt werden?

Bei zwei Bandzuständen (0 und 1) und n internen Zuständen gibt es (4*n)^(2*n) verschiedene Turingmaschinen mit einem in beide Richtungen bewegbaren Band. Die Anzahl der Turingmaschinen steigt schon bei wenigen Zuständen sehr schnell an:

1 interner Zustand: 16 TM
2 interne Zustände: 4096 TM (25 unterschiedliche)
3 interne Zustände: 2.985.984 TM (16.400 unterschiedliche)
4 interne Zustände: 4.294.967.296 TM
5 interne Zustände: 10.240.000.000.000 TM
6 interne Zustände: 36.520.347.436.056.576 TM
7 interne Zustände: 182.059.119.829.942.534.144 TM

Nach Stephen Wolfram stößt man auf interessantes Verhalten, sobald man Turingmaschinen mit mindestens vier internen Zuständen betrachtet. Die minimale Zahl der internen Zustände einer Turingmaschine, die eine bestimmte Sequenz berechnet, dient als Maß für die Komplexität der berechneten Sequenz. Ist das Ranking brauchbar, wenn keine Turingmaschinen mit mehr als sieben internen Zuständen betrachtet werden? Lambda Calculus, wie von John Tromp vorgeschlagen, könnte die bessere Wahl sein. Das Ranking könnte sich jedoch auch damit als unbrauchbar erweisen.

Beantwortete Fragen

Bislang ist es schwierig, einige Fragen aus dem Bereich des maschinellen Lernens zu beantworten. Lässt sich ein Ranking für Lernalgorithmen umsetzen, so wird sich das für folgende Fragen ändern:

Wie sieht der aktuelle Stand der Forschung aus? Oder: Das Ranking.

1. Alle bekannteren Vorhersagealgorithmen werden in einer festgelegten Programmiersprache implementiert und zum Ranking hochgeladen.
2. Jeder Algorithmus wird mit allen oder mit einer statistisch relevanten Auswahl an Sequenzen getestet und erhält einen Score zugeteilt, der besagt, für wie viele Sequenzen und bis zu welcher Komplexität der Algorithmus zuverlässige Vorhersagen macht.
3. Ein Ranking wird erstellt, bei dem die Algorithmen mit dem höchstem Score an der Spitze stehen.

Wie gut ist mein Vorhersagealgorithmus?

1. Ein in einer festgelegten Programmiersprache geschriebener Algorithmus wird auf der Website des Rankings hochgeladen.
2. Der Algorithmus wird mit allen oder mit einer statistisch relevanten Auswahl an Sequenzen getestet und erhält einen Score zugeteilt (s.o).
3. Die Leistung des Algorithmus kann dadurch mit der anderer Algorithmen verglichen werden und der Algorithmus kann in die Highscore-Liste aufgenommen werden.

Welcher Algorithmus ist für mein Vorhersageproblem geeignet?

1. Sequenzen, die typisch für das Problem sind, werden auf der Website des Rankings hochgeladen.
2. Alle Algorithmen, die am Ranking teilnehmen, werden auf die hochgeladenen Sequenzen angewendet.
3. Ein nach Korrektheit der Vorhersagen sortiertes, problem-spezifisches Ranking wird ausgegeben.

Offene Fragen

• Soll die Programmlänge mit in die Berechnung des Scores eines Algorithmus einbezogen werden oder soll es lediglich ein generelles Limit für alle Programme geben?
• Welche Limits sollen für Laufzeit und Programmlänge gesetzt werden?
• Wie lange sollen die Sequenzabschnitte sein, die in der Datenbank gespeichert werden? 10.000 Zeichen?
• Wie sollen die Sequenzabschnitte in Lernsequenz (die den Algorithmen präsentiert wird) und Testsequenz (die vorherzusagen ist) aufgeteilt werden? Wie lang soll der vorherzusagende Abschnitt sein?
• Wie wird die Vorhersage bewertet? Gelten nur komplett richtige Vorhersagen?
• Sollen auch die kürzeren Ausgaben von anhaltenden Turingmaschinen miteinbezogen werden?
• Ein praxistauglicher Algorithmus könnte stark von zusätzlichen Annahmen über seine Umgebung abhängig sein. Ideal sind Vorhersage- und Komprimierungsalgorithmen nur für jeweils eine einzige Wahrscheinlichkeitsverteilung an Eingaben. Ob ein Algorithmus, der für die allgemeinste berechenbare Wahrscheinlichkeitsverteilung an Eingaben ideal ist, auch in der wirklichen Welt brauchbar ist, ist nicht geklärt.
• Ist es zweckmäßiger, probabilistische Sequenzen und Vorhersagealgorithmen statt exakter Algorithmen zuzulassen?
• Wie wird der Score berechnet? Zählen Sequenzen mit niedrigerer Komplexität mehr oder weniger? Wie wird ein Vorhersagealgorithmus bewertet, der zwar komplexe Sequenzen vorhersagen kann, aber bei sehr vielen Sequenzen von niedriger Komplexität fehlschlägt?
• Welche Implementation eines universellen Computers ist am sinnvollsten? Turingmaschinen? Lambda Calculus?

Fazit

Marcus Hutter hat in seiner Doktorarbeit bewiesen, dass die optimale Vorgehensweise einer künstlichen Intelligenz darin besteht, nach einer beliebigen Anzahl von Beobachtungen der Umgebung das kürzeste Programm zu finden, das diese Beobachtungen vorhersagt und anzunehmen, dass die Umgebung durch dieses Programm kontrolliert wird. Verbesserte allgemeine Vorhersagealgorithmen sind demnach mit Fortschritt auf dem Gebiet der künstlichen Intelligenz gleichzusetzen.

Alles, was gemessen wird, verbessert sich. Ich schlage vor, eine Datenbank mit Sequenzabschnitten und zugehöriger (geschätzter) Kolmogorov-Komplexität anzulegen, diese Sequenzen von verschiedenen Lernalgorithmen vorhersagen zu lassen und den Erfolg der Algorithmen in einem Ranking sichtbar zu machen.

Ist diese Idee realistisch?

Django is my web programming framework of choice. The following 1.500 words describe what I would add to the core framework in order to make machine-to-machine communication (APIs) for almost every web application a matter of minutes. Read on »

“Evolution works through DNA-guided protein synthesis and research dollars are halving every year for the purpose is growing exponentially.” — Ray Kurzweil selbst hätte es (nun ja, fast) nicht schöner formulieren können. Und doch stammt die Zeile direkt aus dem Computer, einem einfachen Text-Generator sei Dank. Wie das genau funktioniert und was sich hinter dem Begriff Markov-Ketten verbirgt, das soll in den folgenden Absätzen näher erläutert werden. Read on »

Google ist ein Phänomen: Die Suchmaschine kennt mehr als 8 Milliarden Webseiten. Dazu kommen mehr als 845 Millionen Usenet-Postings. Googles Infrastruktur umfasst inzwischen mehr als 250.000 Server. Nirgendwo anders wird eine größere Menge an Daten verarbeitet und per Website der Öffentlichkeit zugänglich gemacht. Inzwischen dürfen nicht mehr nur Menschen, sondern auch Maschinen auf den Datenschatz zugreifen: Das Zauberwort heißt “Web Services”. Read on »

Die Anwendung neuronaler Netze ist nach wie vor eines der bedeutendsten und interessantesten Themen der künstlichen Intelligenz. Die Kenntnis von Hintergründen und Einsatzmöglichkeiten ist nicht nur für Informatik-Studenten ein Muss, auch Hobby-Programmierer und KI-Interessierte können großen Nutzen daraus ziehen. Doch welche Lektüre ist für wen am besten geeignet? Bei etwa 20 Büchern in deutscher Sprache fällt die Auswahl nicht leicht. Read on »

Wissen ist Macht, das wusste bereits der Philosoph Francis Bacon im 16. Jahrhundert. Und es gilt heute mehr denn je. Unternehmen wie Google speichern nicht grundlos jedes Bit an Information, das sie in die Hände bekommen. Mit Daten eröffnen sich Möglichkeiten: Data Mining, d.h. das Entdecken neuer Zusammenhänge in alten Daten, und der Einsatz neuronaler Netze sind nur zwei davon. Generell gilt: Je mehr Informationen, desto besser. Read on »