Künstliche Intelligenz

Künstliche Intelligenz - Artificial Intelligence (AI)

Der Turing Test

Bereits um 1950 herum hat der englische Mathematiker und Computer-Theoretiker Allan Turing einen Test konzipiert, mit dem er meinte, entscheiden zu können, ob er einer Maschine künstliche Intelligenz zuschreiben kann. Sein Test geht von einem Dialog eines Menschen mit einem Partner aus, den er nicht sehen kann. Wenn der Mensch nicht entscheiden kann, ob der Dialogpartner ein Mensch oder ein Computer ist, dann wäre Turing bereit gewesen, dem Computer Intelligenz zuzugestehen. Dies war über jahrzehnte der heilige Gral der Wissenschafter, die sich mit der sog. Artificial Intelligence (AI) beschäftigt haben. Davon sind wir heute immer noch meilenweit entfernt, wenn auch Computer heute bereits einige Aufgaben lösen, von denen viele früher glaubte, nur Menschen könnten dies, so z.B. gegen einen Großmeister Schach spielen und dabei sogar manchmal zu gewinnen. (die ganze Problematik, was als Artificial Intelligenz gelten soll, findet sich im obigen Link zur Wikipedia.

Denn das Ziel, dass eine Maschine Denkaufgaben erzielt die früher nur Menschen vorbehalten waren, ist ja auf vielen Teilgebieten erreicht, nicht nur beim oben erwähnten Schach, sondern z.B. auch dort, wo Computer mathematische Beweise erstellen, bei sog. Decision Support Systemen, die z.B. die sich täglich ändernde Preisgestaltung bei Billigflügen optimieren, aber auch bei Systemen, die unsere Privatsphäre bedrohen, weil sie einzelne Personen auf Fernsehkameras identifizieren können.

Wie weit wir jedoch davon entfernt sind, einen menschlichen Dialog sicher zu immitieren, das zeigt die leicht kuriose Geschichte um den Loebner Prize. Loebner hat 1989 100.000 $ für das Programm (Chatbot) gestiftet, das von einem Menschen nicht mehr zu unterscheiden ist, d.h. für ein Programm, das den Turing Test besteht. Das hat zwar bisher noch kein Programm geschafft, aber jedes Jahr wird auch ein Trostpreis für das Programm vergeben, das am nächsten an das Ziel herankommt. Dies hat mehrmals ein Programm auf der Grundlage von A.L.I.C.E. gewonnen (siehe weiter unten).

In den ersten Jahren wurde dieser Wettbewerb von den AI-Spezialisten positiv aufgenommen, aber nach der Blamage der vorgestellten Programme in den ersten Jahren des Wettbewerbs entwickelte sich eine solide Animosität zwischen AI-Wissenschaftlern und Herrn Loebner, Vermutlich, weil das selbst gesteckte Ziel (bzw. eines der selbst gesteckten Ziele, das in der Öffentlichkeit mit viel Interesse aufgenommen wurde und Thema vieler Filme und Bücher ist) so eklatant verfehlt wurde. Aber das ist andererseits in der Technik keine Seltenheit. Der Kernphysiker Niels Bohr sagte einmal dazu “Prediction is very difficult, especially about the future.”

Aktualisierung Herbst 2006: die BBC berichtet über den diesjährigen (und letztjährigen) Gewinner des Loebner Preises. Die Basis auf der die britische Firma Icogno arbeitet scheint nicht A.L.I.C.E. zu sein, sondern ein Programm, das durch das Chatten mit realen Personen ständig seinen Horizont erweitert. Der Artikel linkt auf Videos der Interaktionen.

Nach oben

Zur Geschichte der AI: Eliza

[ Hier eine kurze Zusammenfassung der Geschichte von Artificial Intelligence]

Eliza is probably the best known Artificial Intelligence program in the world. It is also one of the oldest. Created in the early 1960's by MIT scientist Joseph Weizenbaum and named after Eliza Doolittle, its mission was to attempt to replicate the conversation between a psychoanalyst and a patient. (Quelle: Simon Laven, dort gibt es auch eine Version zum Runterladen und ganz viele Links zu den sog. Chatterbots)

Eliza works by turning everything you say around. For example:

If you type in: I am having a very bad day

She may reply: did you come to me because you were having a very bad day?

If you type in: I have come to talk to you.

She may reply: oh, you have come to talk to me ?

By doing this Eliza is able to talk you into giving her your deepest feelings. She does not remember it and keeps no recollection of anything you say, but sociologist Sherry Turkle noted that people actually became protective of their relationship with her, mainly because everything you say becomes a personal question.

This can lead to a very interesting conversation that makes her seem so friendly and understanding. However this does have some pitfalls:

If you type in: I am doing fine thank you.

She may reply: how long have you been doing fine thank i?

So every now and again Eliza displays a severe lack of understanding. Which does not seem too bad as you can soon learn your way around this problem. However, once Eliza has repeated a modified version of your sentence for the fifth time in a row you do begin to have doubts about her capability.

Hier eine neuere Implementierung von Eliza. Der Dialog ist natürlich für die heutigen Verhältnisse archaisch einfach (vergleiche mit dem Programm von Yellostrom, zu erreichen über Klick auf die Graphik rechts). Und hier eine andere Implementierung von Eliza.

Nach oben

A.L.I.C.E.

Der zweimalige Gewinner des Loebner Preises (siehe oben) Dr. Richard Wallace ist der Gründer der ALICE Foundation. (Gewinner im Sinne von "am nächsten am Ziel, aber immer noch weit weg").

Die Chatbots die Richard Wallace entwickelt hat beruhen auf der Sprache AIML, oder Artificial Intelligence Mark-up Language. Mit Hilfe dieser sehr einfachen Programmiersprachen und einem kostenlos verfügbaren Programm das diese Sprache interpretiert kann jeder sehr einfach einen Chatbot herstellen. Dies ist ein recht umstrittener Zugang, denn die wirklichen AI-Experten gehen viel komplizierte Wege und versuchen, die Vorgänge im menschlichen Gehirn, so weit diese bisher verstanden sind abzubilden. Dazu bilden sie komplexe Modelle der Umgebung, über die der Chatbot sich auskennen soll. In AIML werden diese Zusammenhänge viel einfacherer dargestellt. Die Ergebnisse sprechen derzeit dafür, dass der komplexe Zugang der AI-Experten sich von der Ergebnissen her nicht unbedingt bewährt hat. Anders ist dies evt. bei den Maschinenenübersetzungen, wo vermutlich ein besseres Verständnis des jeweiligen Kontexts gefordert ist.

userfriendly.org

Nach oben

Virtual Girlfriend

Die Karrikatur von der wunderbaren website userfriendly.org beschreibt eine Geschäftsidee, die ich vor Jahren mit einigen Freunden diskutiert hatte, jetzt aber von jemand anders aktiv umgesetzt wurde: "virtual girlfriend". (Und hier noch gleich noch ein solcher Dienst: v-girl.com (mit recht gut gemachten Videos der virtuellen Freundinnen, einschließlich einer, die sich wohl öfter mal während des Dates aus dem Staub macht - siehe weiter unten "zickig" ;-) )

Dabei hatten wir die Idee, dass wir eine Website einrichten, an die Männer gegen eine recht geringe Gebühr E-Mails senden können, die dann von einem AI-Programm automatisch beantwortet würden. Dabei kann der Kunde gewissen Persönlichkeitseigenschaften seiner "Freundin" vorwählen, z.B. wie sehr sie in ihn verliebt ist, wie romantisch die Dialoge sein sollen, ob sie "zickig" ist und wie explizit die E-Mails werden sollen, wenn es um Sex geht.

Letztendlich haben wir es nicht implementiert, es hätte erfordert, dass wir einen AI-Spezialisten anheuern, der ein Programm entwickelt, das aus den eingehenden E-Mails den Kontext herausliest und dann entsprechend auf dieses E-Mail so antwortet, dass daraus mehr als eine Folge von vorformulierten Antwort-Konserven wird. Ich weiß nicht, ob es solche oder ähnliche Dienste bereits gibt, aber die Karrikatur beschreibt einen solchen Dienst auf der Basis eines Chatbots.

Eine durchaus interessante Frage sind die ethischen Aspekte. Wie würden wir antworten, wenn uns in einer Talkshow vorgeworfen würde, dieser "Dienst" wäre "menschenverachtend"? Ich frage mich an der Stelle, was denn der ethische Unterschied zu Telephon-Hotlines ist? Oder was ist der Unterschied zum Verkauf von Sex-Puppen oder zu Prostitution?

Um es ganz klar zu sagen: Natürlich fände ich es besser, wenn alle Menschen romantische Liebe und erfüllenden Sex mit einem anderen Menschen erleben könnten, aber leider scheint das (derzeit?) nicht für alle Menschen möglich zu sein.

Alle diese Geschäfte ("virtual girlfriend", Telefonsex-Hotlines, Sex-Puppen) sind für mich letztendlich ähnlich einzustufen, in allen Fällen sollten die Männer realisieren, dass da nicht wirklich eine Frau ist, die mit ihnen eine romantische Beziehung oder Sex haben möchte. Zum Unterschied zu den Telephon-Hotlines kann dieser Service, da voll-automatisiert, erheblich günstiger angeboten werden, d.h. er führt nicht zu einem finanziellen Ruin des Kunden.

Ob ein solcher Service auch für Frauen Erfolg haben könnte, ist eine weitere interessante Spekulation. Vermutlich müssten die Texte anders gestaltet sein, aber evt würde auch dies funktionieren. Es wird ja nur eine sehr kleine Zielgruppe angesprochen, die sich durchaus finden könnte, ebenso wie bei den Männern. Trotzdem könnte der Markt ausreichend sein (die Zeitschrift wired berichtete bereits 2000 von guten kommerziellen Erfolgen in Japan). Letztendlich könnten dies für die weibliche Zielgruppe sehr persönlich gehaltene romantische "Arzt"romane sein, die es ja heute auch von zart-romantisch bis paprika-heiß gibt. Auch hier werden hohe Verkaufszahlen berichtet.

Gerade entdeckt: Es gibt bereits seit den späten 80-iger Jahren ein Softwareprogramm Virtual Woman, das einen ähnlichen Ansatz verfolgt.

Nach oben

Bots auf der Jagd nach Pädophilen

Wie der Standard in Österreich und original der New Scientist berichteten, ist seit Anfang 2004 ein Computerprogramm in den englischen Chatrooms für Kinder und Jugendliche auf der Suche nach Pädophilen, die in diesen Chatrooms wohl ihre Opfer suchen. Der New Scientist druckt auch einen Beispieldialog ab. Wer will, kann ja mal versuchen, herauszufinden, wer von den beiden der Computer ist.

Wie Leserbriefschreiber im Standard korrekt aufzeigen, wird es wohl (außer den Pädophilen) nur wenige geben, die diese Idee nicht gut finden. Das gleiche Programm könnte aber auch leicht modifiziert auf die Suche nach anderen "abweichenden" Meinungen gehen, z.B. zuerst könnte es Rassisten jagen, dann Globalisierungsgegner und irgendwann dann einfach nur Gewerkschaftler. Das ist eine neue Technologie, die kaum wieder in die Flasche zurück zu bekommen ist. Öffentliche Chatrooms sind nun auch nicht mehr ohne Kontrollen.

Nach oben

Maschinenübersetzungen

Für alle, die das noch nicht kennen: die Maschinenübersetzungen, d.h. die Übersetzungen, die durch Computer erstellt werden, dienen zwar oft als Quelle der Heiterkeit ("der Geist ist willig, aber das Fleisch ist schwach" ergibt heute keine Sätze über Whisky mehr, sondern ein gar nicht so schlechtes "the spirit is willing, but the flesh is weak" (siehe bei googleDa ist z.b. der schon fast legendäre babelfish (natürlich benannt nach dem köstlichen "Per Anhalter durch die Galaxis" von Douglas Adams).

Nach oben

Turing Tests im Einsatz - die Captcha-Technologie

Für mich ganz überraschend hat sich allerdings in den letzten Jahren eine wirkliche kommerzielle Anwendung für einen Turing Test ergeben und der sieht ganz anders aus. Es geht darum, dass ein Computer entscheiden muss, ob der Dialogpartner ein Mensch ist oder ein anderer Computer. Hintergrund ist u.a. die Spamwelle. Die Spammer erzeugen sich automatisch kostenlose Mail-Accounts, um diese für ihre unerwünschten Aktivitäten zu nutzen, bis der Anbieter ihnen auf die Schliche kommt und den Account wieder sperrt. Die Anbieter, hotmail, yahoo und andere, setzen daher jetzt Turing Tests ein, d.h. sie stellen den Dialogpartnern Aufgaben, die nur ein Mensch lösen kann.

Hier jetzt erst mal der Artikel zu Captchas, und weiter unten dann, wie solche Captchas doch geknackt werden können.

Human or Computer? Take This Test

December 10, 2002, New York Times
By SARA ROBINSON

As chief scientist of the Internet portal Yahoo, Dr. Udi Manber had a profound problem: how to differentiate human intelligence from that of a machine.

His concern was more than academic. Rogue computer programs masquerading as teenagers were infiltrating Yahoo chat rooms, collecting personal information or posting links to Web sites promoting company products. Spam companies were creating havoc by writing programs that swiftly registered for hundreds of free Yahoo e-mail accounts then used them for bulk mailings.

"What we needed," said Dr. Manber, "was a simple way of telling a human user from a computer program."

So, in a September 2000 conference call, Dr. Manber discussed the problem with a group of computer science researchers at Carnegie Mellon University. The result was a long-term project that is just now beginning to bear fruit.

The roots of Dr. Manber's philosophical conundrum lay in a paper written 50 years earlier by the mathematician Dr. Alan Turing, who imagined a game in which a human interrogator was connected electronically to a human and a computer in the next room. The interrogator's task was to pose a series of questions that determined which of the other participants was the human. The human helped him, while the computer did its best to thwart him.

Dr. Turing suggested that a machine could be said to think if the human interrogator could not distinguish it from the other human. He went on to predict that by 2000, computers would be able to fool the average interrogator over five minutes of questioning at least 30 percent of the time. Turing test auf http://www.trafficranking.com/

Although the Turing test, as it is now called, spawned a vibrant field of research known as artificial intelligence, his prediction has proved false. Today's computers are capable of feats Dr. Turing never imagined, yet in many simple tasks, a typical 5-year-old can outperform the most powerful computers.

Indeed, the abilities that require much of what is usually described as intelligence, like medical diagnosis or playing chess, have proved far easier for computers than seemingly simpler abilities: those requiring vision, hearing, language or motor control.

"Abilities like vision are the result of billions of years of evolution and difficult for us to understand by introspection, whereas abilities like multiplying two numbers are things we were explicitly taught and can readily express in a computer program," said Dr. Jitendra Malik, a professor specializing in computer vision at the University of California at Berkeley.

Dr. Manuel Blum, a professor of computer science at Carnegie Mellon who took part in the Yahoo conference, realized that the failures of artificial intelligence might provide exactly the solution Yahoo needed. Why not devise a new sort of Turing test, he suggested, that would be simple for humans but would baffle sophisticated computer programs.

Dr. Manber liked the idea, so with his Ph.D. student Luis von Ahn and others Dr. Blum devised a collection of cognitive puzzles based on the challenging problems of artificial intelligence. The puzzles have the property that computers can generate and grade the tests even though they cannot pass them. The researchers decided to call their puzzles Captchas, an acronym for Completely Automated Public Turing Test to Tell Computers and Humans Apart (on the Web at www.captcha.net).

One puzzle, called Gimpy, consists of a display of seven distorted, overlapping words chosen at random from a dictionary of simple words. Solving the puzzle requires identifying three of the seven words and typing them into the box provided. The Carnegie Mellon group also created a simplified version of Gimpy — a single distorted word displayed against a complicated background. It is now part of Yahoo's registration process.

Another Captcha, called Sounds, consists of a distorted, computer-generated sound clip containing a word or sequence of numbers. To solve the puzzle, a user must listen to the clip and type the word or numbers into the box provided.

The idea of using puzzles to prevent automated registrations was not new. Other e-commerce sites, including the AltaVista search engine and eBay's PayPal service, were experiencing problems like Yahoo's and independently came up with Captcha-like puzzles. Through its acquisitions, Hewlett-Packard holds a patent on text-based Captchas. Still, researchers credit Dr. Blum for the breadth of his vision. Dr. Blum "did a great thing by recognizing that this problem is much more than solving a nuisance for Yahoo and AltaVista," said Dr. Andrei Broder, who helped develop the AltaVista puzzle and is now at IBM.

As a cryptographer, Dr. Blum was familiar with the constant efforts of cryptographic researchers to advance the field by cracking codes to discover their weaknesses.

He hoped to start a similar dynamic for Captchas, spurring researchers to try to create better Captchas while building computer programs that crack existing ones.

"Captchas are useful for companies like Yahoo, but if they're broken it's even more useful for researchers," Dr. Blum said. "It's like there are two lollipops and no matter what you get one of them."

In October Dr. Blum got his wish. Dr. Malik of Berkeley and Greg Mori, a student, devised a computer program that could crack Gimpy — both the simple version used by Yahoo and the harder one on Captcha's Web site. percent of the time.

Since its inception two years ago, the Captcha effort has been building. Several research teams have joined the Captcha effort, trying to make and break Captchas and even using the ideas behind Captchas for new lines of research.

Researchers at the Palo Alto Research Center modified a program used for scanning text to create a program that could solve certain types of Yahoo-Gimpy puzzles, says Dr. Henry Baird, who was in charge of that effort. The group is also developing a new text-based Captcha called Baffletext that it hopes to license to e-commerce sites. percent of the time.

Inspired by the themes behind Captchas, Dr. Doug Tygar, a professor of computer science at Berkeley, and his student Monica Chew are developing alternatives to passwords that are tailored to human skills. Humans have trouble remembering long, random strings of characters, yet they excel at remembering faces and objects, noted Dr. Tygar.

Dr. Malik said he first became interested in the effort after attending a Captcha conference at the Palo Alto center in January. After he and his former student Dr. Serge Belongie, now at the University of California at San Diego, developed a new object recognition technique modeled to have some of the properties of human vision, Dr. Malik decided that Captchas were ideal for testing their method.

The Yahoo-Gimpy cracking program, written by Mr. Mori, takes a version of the easy Gimpy, a distorted word displayed in a cluttered background, and finds some points along the boundary of each letter, using standard techniques of computer vision theory.

Then, applying the Malik-Belongie method, it makes a radial chart for each point indicating where the other boundary points are in relation to it.

The charts of boundary points for that letter are compared with the charts of boundary points for all 26 possible letters. The closest match is usually the correct answer. percent of the time.

Using various tricks to make it run faster, the program can crack an easy Gimpy puzzle in a few seconds, and it gets the right answer over 80 percent of the time.

For the harder version of Gimpy, the researchers devised a program that examines entire words instead of individual letters, so its performance is in minutes rather than seconds, and it gets the puzzle right only about a third of the time. Still, the program will need on average only three tries to get the right answer.

Dr. Malik and Mr. Mori are exploring ways of improving the performance of their program on Gimpy that will also improve their general technique of recognizing objects in a cluttered background.

"We want to keep working on this in a principled way so we can use the same technique on an outdoor scene with buildings, trees and cars," Dr. Malik said.

The general technique, he said, will have many practical applications, like automated recognition of military targets or detection of trademark infringements on the Internet. Meanwhile, Yahoo will have to install a new Captcha that is resistant to Dr. Mori's program. This task will fall to Dr. Manber's successor, since Dr. Manber moved to a new position last month as chief algorithms officer for Amazon.com. There, he said, he plans to continue his collaborations with academic researchers.

Und eine Aktualisierung vom Juni 2007 in der NY Times berichtet, dass der Wettlauf zwischen den AI-Forschern, die trotz der Schwierigkeiten besser und besser darin werden, die Texte trotz Verzerrungen und Hintergrundrauschen zu entziffern, mittlerweile dazu geführt hat, dass selbst Menschen ohne Behinderungen (wie z.B. Farbenblindheit) oft Schwierigkeiten haben, diese Aufgaben zu lösen. Es entwickelt sich ein Wettlauf und ein Katz-und-Maus-Spiel zwischen den Captcha-Entwicklern und den Captcha-Knackern.

Aktualisierung Okt. 2007:
Und wie genial dann wiederum Captchas ausgehebelt werden können, das zeigt dieser Artikel, wo als Belohnung für die menschlichen Captcha-Knacker nackte Haut gezeigt wird.

Die einzelnen Arbeitsschritte bei der Bildbearbeitung

Aktualisierung Mai 2008:
Auf folgender Website gibt einen guten Überblick über die Vielfalt der heute verwendeten Captchas

Hier ist eine interessante Studie: die Wissenschafter zeigen, dass das "Knacken" von Captchas (pdf) in 2 Schritte verfällt: 1. das Separieren der Zeichen und 2. die Erkennung der Zeichen. Sie legen dar, dass es ausreicht, das erste Problem zu lösen, wenn ich danach Zugang zu Systemen wie Neuralen Netzen habe, die er sehr verzerrte Zeichen sehr gut erkennen können, d.h. die Sicherheit hängt hauptsächlich davon ab, wie gut ich verschleiern kann, wo ein Zeichen aufhört und das nächste anfängt. Die Forscher zeigen, wie auch mit sehr einfachen Algorithmen so etwas erreicht werden kann.

Die Website recaptcha.net bietet für Betreiber von anderen Websites kostenlose Captchas an, die dadurch entstanden sind, dass beim Scannen alter Bücher der OCR Prozess gescheitert ist. Wenn der Benutzer sich dann erfolgreich eingeloggt hat, ist gleichzeitig ein weiteres Wort in einem alten Buch erkannt worden. Wie sicher diese jedoch sind, kann ich nicht sagen.

Nach oben