« september 2004 | Main | november 2004 »

oktober 26, 2004

Trust: Making and Breaking Cooperative Relations, edited by Diego Gambetta

Online-bok: Department of Sociology: Trust Online Edition

This collection was originally published by Basil Blackwell in 1988. The complete text is now available online in Word97/98 and PDF formats.
...
The editor and contributors have decided that the book should be available to download free of charge. One of the original reasons for the volume was to try and understand the difficulties of developing economies, and we therefore feel that the volume should be accessible to scholars and students of less privileged countries.


Bland annat finns följande papers:

Diego Gambetta: Can We Trust Trust? (PDF)
Diego Gambetta: Mafia: The Price of Distrust (PDF)
Partha Dasgupta: Trust as a Commodity
Patrick Bateson: The Biological Evolution of Cooperation and Trust

Posted by hakank at 11:54 EM Posted to Spelteori och ekonomi

Game Theory for Swingers: What states should the candidates visit before Election Day?

Jordan Ellenberg i Slate: Game Theory for Swingers: What states should the candidates visit before Election Day?

Some campaign decisions are easy, even near the finish of a deadlocked race. Bush won't be making campaign stops in Maryland, and Kerry won't be running ads in Montana. The hot venues are Florida, Ohio, and Pennsylvania, which have in common rich caches of electoral votes and a coquettish reluctance to settle on one of their increasingly fervent suitors. Unsurprisingly, these states have been the three most frequent stops for both candidates.

Conventional wisdom says Kerry can't win without Pennsylvania, which suggests he should concentrate all his energy there. But doing that would leave Florida and Ohio undefended and make it easier for Bush to win both. Maybe Kerry should foray into Ohio too, which might lead Bush to try to pick off Pennsylvania, which might divert his campaign's energy from Florida just enough for Kerry to snatch it away. ... You see the difficulty: As in any tactical problem, the best thing for Kerry to do depends on what Bush does, and the best thing for Bush to do depends on what Kerry does. At times like this, the division of mathematics that comes to our aid is game theory.

Posted by hakank at 06:39 FM Posted to Spelteori och ekonomi

oktober 24, 2004

Föredrag: Google under huven

Googles Jeff Dean har ett intressant föredrag om tekniken bakom Google: Google: A Behind-the-scenes Look (WMV, cirka 1 timme). Läs en blänkare om föredraget här. Det är alltså mest teknik, både hård- och mjukvara.

Efter cirka 30 minuter börjar det avsnitt som jag tyckte var mest intressant: "Fun with Data" där det bl.a. visas en demo av ett system för automatisk ordklustring och som förhoppningsvis kommer att föras in i systemet för att få ännu bättre sökresultat.


Cirka 25 minuter in i föredraget, beskrivs MapReduce-modellen, som beskrivits mer detaljerat i papret Jeffrey Dean and Sanjay Ghemawat: MapReduce: Simplified Data Processing on Large Clusters

MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model, as shown in the paper.
Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program's execution across a set of machines, handling machine failures, and managing the required inter-machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system.
Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable: a typical MapReduce computation processes many terabytes of data on thousands of machines. Programmers and the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google's clusters every day.


Via Google Blogoscoped.

Posted by hakank at 07:42 EM Posted to Sökmotorer

oktober 23, 2004

Svante Pettersson journalistar om översättningar och John Eje Thelin

svantlog-bloggaren Svante Petterson skriver flera artiklar i senaste numret (PDF) av Skurupsposten, övningstidningen för Journalistlinjen på Skurups Folkhögskola.

Han skriver bl.a. två intressanta artiklar om John Eje Thelin (Gärningsmannaprofilen) och översättarens vedermödor (med rubrikerna "John Eje Thelin lägger ut texten" och "Så får Simpsons och Letterman svenska ord"), samt några musikrecension, t.ex. av Jojje Wadenius Band.

Det kanske är på sin plats att berätta att Svante är en Lettermankännare av stora mått. När vi arbetade tillsammans citerade Svante nästan dagligen något från det senaste Letterman-avsnittet. Kul att han nu skriver om översättaren till programmet.

Posted by hakank at 08:54 FM Posted to Blogging

oktober 19, 2004

Ivars Peterson: Randomness, Risk, and Financial Markets

Math Trek: Randomness, Risk, and Financial Markets, Science News Online, Oct. 9, 2004:

Pi, the ratio of a circle's circumference to its diameter, is known as an irrational number because it can't be exactly expressed as a ratio of whole numbers. It would take an infinite number of digits to write it out in full as a decimal or, in binary form, as a string of 1s and 0s. The square root of 2, the square root of 3, and the constant e (the base of the natural logarithms) fall into the same category.

The known digits of these numbers appear patternless. According to one novel method of assessing the randomness of a sequence of numbers, however, the digits of pi turn out to be somewhat more irregular than the digits of the other irrational numbers.

The measure used to determine the irregularity or degree of disorder (entropy) of these sequences is called the approximate entropy. Invented by Steve Pincus of Guilford, Conn., and developed in cooperation with Burton H. Singer of Princeton University, this measure characterizes the randomness of a sequence of numbers.
...
For example, Pincus has looked at stock market performance, as measured by Standard and Poor's index of 500 stocks. His calculations show that fluctuations in the index's value are generally quite far from being completely irregular, or random.

Flera referenser till Pincus och Singer finns i artikeln.

Posted by hakank at 06:53 FM Posted to Statistik/data-analys | Comments (1)

oktober 17, 2004

Nya rön i fångarnas dilemma - lite länkar

Sedan Nya rön i fångarnas dilemma skrevs har jag i Bloglines bokmärkt kommentarer om Wired-artikeln. Nu är det dags att dumpa dem så att de är lätt tillgängliga för vidare läsning (har inte läst allt, nämligen).

Först några svenska bloggare:
Simon på Infontology: Ett team av självuppoffrande strategier vinner Fångens dilemma
Nicklas på Kommenterat: Tit for tat besegrad

Så några engelskspråkiga:
Three-Toed Sloth (Cosma Shalizi) : Strong Reciprocity Rules OK
Crumb Trail: Organized Crime
Marginal Revolution: Is tit-for-tat the best strategy in games?
LiveJournal, The Art of Problem Solvning: game theorists unite (untie?)
DA mal: Politics and game theory
illuminating science: Tit-for-Tat strikes back
Slashdot: 'Tit for Tat' Defeated In Prisoner's Dilemma Challenge

Posted by hakank at 09:25 EM Posted to Spelteori och ekonomi

Automatisk "lösning" av Minesweeper i Mozart/Oz

Raphaël Collet har byggt ett program som automatiskt löser spelet Minesweeper, och har också skrivit papret Playing the Minesweeper with Constraints (PDF) om detta. Programmet ser nästan ut som originalet och finns att ladda ner på The Oz Minesweeper page.

För att köra programmet krävs:
* The Mozart Programming System
* Någon form av Emacs (Xemacs eller GNU Emacs). Windows-versionen går det att ladda ner via denna sida
* Glöm inte bort att sätta miljövariabeln OZEMACS till Emacs-exekutabeln (annars funkar det inte)
* Läs på Enabling Oz Applets hur man kör Oz-program via webben.


Se vidare
Mozart Documentation
Speciellt skoj är Finite Domain Constraint Programming in Oz. A Tutorial

The Authoritative Minesweeper
Solving Minesweeper
Richard Kaye's Minesweeper Pages. Kaye bevisade för några år sedan att Minesweeper är ett NP-komplett problem: "Minesweeper is NP-complete", Mathematical Intelligencer volume 22 number 4, 2000, pages 9-15 (har varken hittat eller läst detta).
Ian Stewart on Minesweeper
Chris Studholme: Minesweeper as a Constraint Satisfaction Problem
Tetris is Hard, Even to Approximate


On-Line Guide to Constraint Programming av Roman Barták
Second International Mozart/Oz Conference


När det gäller Constraint Logic Programming tycker jag i och för sig att både ECLiPSE (fritt men kräver registrering) och Sicstus Prolog är lättare att arbeta med. Och boken Programming with Constraints av Kim Marriott och Peter J. Stuckey är en höjdare.


Rätt lite av ovanstående kom direkt via Lambda The Ultimate, men det började där.

Posted by hakank at 07:51 EM Posted to Artificiell intelligens

Addicted to Google

Addicted to Google (Quicktime, 42.9 Mb).

Se även College is Easy och Top Ten Signs You Are Addicted to Google samt möjligen The Google Bible.

Via Google Blogoscoped.

Posted by hakank at 06:43 EM Posted to Sökmotorer

Filosofiska rummet: Om strängteorin och vetenskapens gränser

Filosofiska rummet Om strängteorin och vetenskapens gränser (P1, repris fredag 22 okt 21.03):
Tänk er en teori som förklarar precis hur allting i universum fungerar och har uppstått - en formel som rätar ut frågetecknen kring till synes omöjliga motsättningarna mellan rum, tid och materia, både i makro och mikrokosmos. Och som dessutom ger insikt i tidigare okända dimensioner. Det handlar om TFA - Teorin För Allting - enhetsteorin som i alla tider varit all världens forskares dröm att hitta.

Idag finns en sån teori inom räckhåll. Den kallas Strängteorin och den vänder ut och in på den fysiska verkligheten som vi uppfattar den genom våra sinnen.

I själva verket består verkligheten av strängar, membran, parallella universum och extra dimensioner? Beviset består av ett gigantiskt matematiskt korthus som ömsom stått pall för kritikens vindar och ömsom rasat samman.

Filosofiska rummet om Strängteorin och vetenskapens gränser.

Gäster: Ulf Danielsson, teoretisk fysiker, Marie Rådbo, astronom och Lars-Göran Johansson, vetenskapsfilosof.

Programledare och producent: Peter Sandberg


Programmet finns att lyssna på eller ladda hem en vecka framåt.

Posted by hakank at 06:34 EM Posted to Filosofi | Comments (1)

oktober 15, 2004

Measuring beauty

Philip Ball i Nature:
Measuring beauty
Philip Ball asks whether a method of persuading people to tell the truth in subjective surveys might give us a more robust way to judge the quality of art.

Surveys to judge truth of answers
Predicting the results of political elections could be transformed from a black art into a science, thanks to a new way of getting people to tell the truth. According to the mathematical psychologist who devised it, his method can elicit more truthful subjective judgements about anything from business forecasts to the quality of a piece of art.

Posted by hakank at 10:47 EM Posted to Diverse vetenskap

Computational trust, trust metrics etc

Några länkar om trust metrics, computational trust etc, bl.a. via Yahoo-gruppen trustcomp:
A group on computational trust, trust management, trust/risk engines, trustworthy recommenders, trust-based collaborative filtering, confidence in recognition, technical trust, user trust, network/web of trust, trust metrics analysis, trade-off between privacy and trust.

Se även trustcomp.org.

Först två kuro5hin-artiklar från 2003 resp 2002.

Notes Toward a Moderation Economy:
Whether you call it Mojo, Karma, "Standing," or something else, all content rating feedback systems have some sort of currency. While there are many different ways of acquiring and spending such capital, nobody seems to have implemented an economy varied enough to be robust. And this is the key to building a system which can be stable in the long term.

Pondering Digital Reputations:
Our reputation may affect our lives more than any other identity construct we have. Anonymity, Pseudonymity, and other such constructs are ultimately all methods to deal with the effects of reputation. Digital Identity will create Digital Reputations, and how technology handles this has very significant privacy and security implications...

Sedan lite annat.

Trust metrics Wiki

Advogato's trust metric: The basic trust metric evaluates a set of peer certificates, resulting in a set of accounts accepted. These certificates are represented as a graph, with each account as a node, and each certificate as a directed edge. The goal of the trust metric is to accept as many valid accounts as possible, while also reducing the impact of attackers.

CategoryRatingSystem

Trust metrics' Journal (inte speciellt aktiv)

Russell Hardin: The Street-Level Epistemology of Trust (PDF)

Alfarez Abdul Rahman, Trust and Reputation Research

Zoran Despotovic, Karl Aberer: Trust and Reputation Management in P2P Networks (PDF slides).

Posted by hakank at 09:38 EM Posted to Spelteori och ekonomi

oktober 14, 2004

Tracing the Evolution of Social Software

Life With Alacrity: Tracing the Evolution of Social Software

The term 'social software', which is now used to define software that supports group interaction, has only become relatively popular within the last two or more years. However, the core ideas of social software itself enjoy a much longer history, running back to Vannevar Bush's ideas about 'memex' in 1945, and traveling through terms such as Augmentation, Groupware, and CSCW in the 1960s, 70s, 80s, and 90s.

By examining the many terms used to describe today's 'social software' we can also explore the origins of social software itself, and see how there exists a very real life cycle concerning the use of technical terminology.

Via danah boyd.

Posted by hakank at 07:17 EM Posted to Social Network Analysis/Complex Networks

oktober 13, 2004

Frank Schätzing "Der Schwarm"

Hörde precis (med ena örat) på P1:s Biblioteket om vilka böcker som ligger i topp på olika länders bibliotek. Det verkar som Dan Browns Da Vinci-koden toppar många, men i Tyskland var det en bok som verkade intressant, och som jag inte hört talas om tidigare: Der Schwarm av Frank Schätzing (som jag inte känner till sedan tidigare). Det är alltså från tyska Amazon så: Altavisa-översättning .

Boken handlar tydligen om hur naturen "gör uppror", men exakt hur svärmeriet - som var det som triggade mitt intresse - kommer in vet jag inte riktigt, mest pga av mina uschla tyskakunskaper.

Det finns även en snygg men lite obegriplig tyskspråkig sajt: DerSchwarm.com.

Någon som känner till boken eller kan förklara svärmeriet lite mer?

Posted by hakank at 07:10 EM Posted to Komplexitet/emergens | Comments (5)

1973--1974 Dictionary of the History of Ideas

Från Three-Toed Sloth: And Just Where Did You Get That Idea?

This is very cool, for a geeky intellectual value of cool: the 1973--1974 Dictionary of the History of Ideas is online. There's an immense amount of good stuff in there, from people who really knew what they were talking about.

Sedan följer en lista med en massa kända personer (med länkar)från diverse discipliner, t.ex. Kenneth Arrow, Isaiah Berlin, Mircea Eliade, Stu Kauffman, Oskar Morgenstern.

Posted by hakank at 06:49 EM Posted to Diverse vetenskap

The greatest equations ever

PhysicsWeb: The greatest equations ever:

Maxwell's equations of electromagnetism and the Euler equation top a poll to find the greatest equations of all time. Robert P Crease discusses the results of his reader survey.

Se även
The 20 greatest equations
The greatest equations ever (från maj 2004)
It Must Be Beautiful: Great Equations of Modern Science, Graham Farmelo (ed) (recension).

Via Language Log: Twenty greatest equations -- minus three?.

Posted by hakank at 06:39 EM Posted to Diverse vetenskap | Comments (1)

Nya rön i fångarnas dilemma

Wired New Tack Wins Prisoner's Dilemma:

Proving that a new approach can secure victory in a classic strategy game, a team from England's Southampton University has won the 20th-anniversary Iterated Prisoner's Dilemma competition, toppling the long-term winner from its throne.

The Southampton group, whose primary research area is software agents, said its strategy involved a series of moves allowing players to recognize each other and act cooperatively.
...
Once two Southampton players recognized each other, they were designed to immediately assume "master and slave" roles -- one would sacrifice itself so the other could win repeatedly.

Another twist to the game was the addition of noise, which allowed some moves to be deliberately misrepresented. In the original game, the two prisoners could not communicate. But Southampton's design lets the prisoners do the equivalent of signaling to each other their intentions by tapping in Morse code on the prison wall.

Länkar från artikeln:
Prisoner's dilemma
Nick Jennings
The Iterated Prisoner's Dilemma Competition
Robert Axelrod
Tournament Result

Posted by hakank at 06:23 EM Posted to Spelteori och ekonomi

oktober 11, 2004

Papers written by googlers

Papers written by Googlers finns referenser till papers som skrivits av de som jobbar på google.

Se även Why You Should Work at Google som listar några av de projekt som googlers arbetat med.

(Förslag till en tjänst: "De som arbetat med detta projekt har också arbetat med dessa projekt.)

Posted by hakank at 06:31 FM Posted to Sökmotorer | Comments (2)

oktober 10, 2004

Terrorism och matematik

AP-artikeln Mathematicians Offer Help in Terror Fight berättar om ett gäng matematiker och andra som samlades för att diskutera terrorism:

A small group of thinking men and women convened at Rutgers University last month to consider how order theory — a branch of abstract mathematics that deals with hierarchical relationships — could be applied to the war on terror.

Troligen är det DIMACS Workshop on Applications of Order Theory to Homeland Defense and Computer Security som avses. Se Abstracts samt Important links.

Artikeln nämner bland annat matematikern Jonathan David Farley :
Mathematician Jonathan Farley of the Massachusetts Institute of Technology [...] said he was inspired to organize the meeting by the movie "A Beautiful Mind." The film tells the story of mathematician John Forbes Nash, whose work in game theory found application in Cold War military strategy, international trade and the auctioning of broadcast frequencies by the Federal Communications Commission [...].

Farley har t.ex. skrivit Breaking Al Qaeda Cells: A Mathematical Analysis of Counterterrorism Operations (A Guide for Risk Assessment and Decision Making) (PDF).


Övriga länkar:
Ivars Peterson Splitting Terrorist Cells
Order theory

Posted by hakank at 08:33 FM Posted to Matematik

oktober 08, 2004

Mer om myntsingling

I Diaconis om myntsingling skrevs om en undersökning som Persi Diaconis, Susan Holmes och Richard Montgomery gjort kring myntsingling.

Nyss stötte jag på deras paper om detta: Dynamical Bias in the Coin Toss (PDF)
Abstract:
We analyze the natural process of flipping a coin which is caught in the hand. We prove that vigorously-flipped coins are biased to come up the same way they started. The amount of bias depends on a single parameter, the angle between the normal to the coin and the angular momentum vector. Measurements of this parameter based
on high-speed photography are reported. For natural flips, the chance of coming up as started is about .51.

Det visas också några fina bilder på mojängen som användes.

Posted by hakank at 11:58 EM Posted to Matematik

de Bruijn-sekvenser (portkodsproblemet)

Tänk att du har glömt din portkod och ska försöka testa alla möjligheter men vill knappa in så få siffror som möjligt. Hur ska du gå tillväga? Förutsättningen är att portkoden har fyra siffror (0-9) och att man inte behöver trycka "Enter" eller liknande efter varje sekvens som testas, dvs det är bara att knappa på tills rätt sekvens slagits in.

För något år sedan var jag intresserad av just detta problem och skrev två program för att få fram denna typ av sekvenser som alltså kallas för de Bruijn-sekvenser: Ett CGI-program som har en rätt kraftig restriktion av hur stora sekvenserna kan vara, och en Java-applet utan några sådana begränsningar. Här visas en lösning på ovanstående problem.


Stefan Geens skrev idag en lång och fascinerande exposé över detta problem i The de Bruijn code, där han bl.a. var vänlig nog att länka till ett av dessa program. Han förklarar naturligtvis allting mer och bättre.

För fullständighetens skull refereras åter till källorna:
Mathworld: de Bruijn sequence
The (Combinatorial) Object Server: Information on necklaces, unlabelled necklaces, Lyndon words, De Bruijn sequences där jag fick tag i den algoritmen som används i programmen.

Posted by hakank at 10:15 EM Posted to Matematik | Comments (1)

oktober 06, 2004

Thompas Blog

Thompas Blog drivs av den fotbollstokigekunnige Thomas Andersson som sedan några månader sedan gjorde äran att bli en arbetskollega (och är en Yet Another Computer Geek).

Bloggen kommer troligen mest handla om fotboll, vilket de existerande kategorierna antyder: fotboll, Malmö FF samt Allmänt.

För er som vill läsa om fotboll, speciellt om Arsenal och MFF kan alltså Thompas Blogg vara värd att bevaka.

Posted by hakank at 09:00 EM Posted to Blogging

R version 2.0.0 och ett nytt nyhetsbrev

Häromdagen kom version 2.0.0 av statistik- och dataanalyssystemet R och igår kom en färdigkompilerad Windowsversion.

Idag kom septembernumret av R News (PDF-fil) som bl.a. handlar om en av de nya finesserna i 2:an, nämligen "lazy loading". Ett annat avsnitt är om Rgraphviz som hanterar grafer, och exemplifieras med "molecular pathways". I slutet listas alla de nya funktionerna för 2:an och de paket som kommit sedan förra numret.

Posted by hakank at 08:24 EM Posted to Statistik/data-analys | Comments (1)

First Monday October 2004

First Monday, October 2004 innehåller bl.a. följande:

Bryn Loban:
Between rhizomes and trees: P2P information systems

The aim of the first part of this paper is to provide an overview of information retrieval in Peer–to–Peer (P2P) information systems in the file–sharing domain. Starting with a general overview of the concept of P2P information systems, the paper then focuses on five desktop–accessible P2P information systems: Napster with its clones OpenNap and eDonkey, and Gnutella and FastTrack (i.e., Kazaa). A detailed description is given of the attributes and properties of each P2P file–sharing information system, followed by an evaluation of the respective P2P file–sharing applications, taking each in turn and examining their respective strengths and weaknesses. This paper concludes with a critical comparative analysis and gives some suggestions for further investigation.

Paul Wouters, Iina Hellsten, and Loet Leydesdorff:
Internet time and the reliability of search engines
Search engines are unreliable tools for data collection for research that aims to reconstruct the historical record. This unreliability is not caused by sudden instabilities of search engines. On the contrary, their operational stability in systematically updating the Internet is the cause. We show how both Google and Altavista systematically relocate the time stamp of Web documents in their databases from the more distant past into the present and the very recent past. They also delete documents. We show how this erodes the quality of information. The search engines continuously reconstruct competing presents that also extend to their perspectives on the past. This has major consequences for the use of search engine results in scholarly research, but gives us a view on the various presents and pasts living side by side in the Internet.

Posted by hakank at 06:40 EM Posted to Diverse vetenskap

Digital Grusväg 2/2004 (den senaste, alltså)

Den senaste (2/2004, PDF) utgåvan av Digital Grusväg har kommit.

Från innehållsförteckningen (eventuella värdeomdömen i det nedenstående härstammar från den aktuella blogganteckningens författare och inte originalförfattaren):

Se ävenledes: Digital Grusväg, Digital Grusväg samt Digital Grusväg 1/2004

F.ö. är detta den första blogganteckningen å den nya datorn.

Posted by hakank at 06:16 EM Posted to Diverse vetenskap