Sean Luke has made available an open set of lecture notes on metaheuristics algorithms, Essentials of Metaheuristics. Sean defines a metaheuristic as

“A common but unfortunate name for any stochastic optimization algorithm intended to be the last resort before giving up and using random or brute-force search. Such algorithms are used for problems where you don’t know how to find a good solution, but if shown a candidate solution, you can give it a grade. The algorithmic family includes genetic algorithms, hill-climbing, simulated annealing, ant colony optimization, particle swarm optimization, and so on.”

Such AI algorithms are also often called weak methods, but I like the term metaheuristic better.

The lecture notes look great and the chapters can be used independently for self study or to augment topics in a graduate or undergraduate course. Thanks Sean!

(via Don Miner.)

RAEng report on Social, legal and ethical issues of autonomous systems

The Royal Academy of Engineering has released a report on the social, legal and ethical issues involving autonomous systems — systems that are adaptive, learn and can make decisions without the intervention or supervision of a human.

The report, Autonomous Systems: Social, Legal and Ethical Issues (pdf), was based on a roundtable discussion “from a wide range of experts, looking at the areas where autonomous systems are most likely to emerge first, and discussing the broad ethical issues surrounding their uptake.”

While autonomous systems have broad applicability, the report focuses on two areas: transportation (e.g. autonomous road vehicles) and personal care (e.g., smart homes).

“Autonomous systems, such as fully robotic vehicles that are “driverless” or artificial companions that can provide practical and emotional support to isolated people, have a level of self-determination and decision making ability with the capacity to learn from past performance. Autonomous systems do not experience emotional reactions and can therefore perform better than humans in tasks that are dull, risky or stressful. However they bring with them a new set of ethical problems. What if unpredicted behaviour causes harm? If an unmanned vehicle is involved in an accident, who is responsible – the driver or the systems engineer? Autonomous vehicles could provide benefits for road transport with reduced congestion and safety improvements but there is a lack of a suitable legal framework to address issues such as insurance and driver responsibility.
…
The technologies for smart homes and patient monitoring are already in existence and provide many benefits to older people, such as allowing them to remain in their own home when recovering from an illness, but they could also lead to isolation from family and friends. Some users may be unfamiliar with the technologies and be unable to give consent to their use.”

The RAEng report recommends “engaging early in public consultation” and working to establish “appropriate regulation and governance so that controls are put in place to guide the development of these systems”.

rdf:SeeAlso Autonomous tech ‘requires debate’; Scientists ponder rules and ethics of robo helpers; Robot cats could care for older Britons.

(via Mike Wooldridge)

Who won the Netflix Prize? Ensemble or BellKors Pragmatic Chaos

Who won the Netflix Prize? According to a post in the NYT Bits blog, Netflix Challenge Ends, But Winner Is In Doubt, it’s still very much up in the air.

” So The Ensemble won, right? Not necessarily. In an e-mail message Sunday night, Chris Volinsky, a scientist at AT&T Research and a leader of the BellKor’s team, said: “Our team is in first place as we were contacted by Netflix to validate our entry.” And in an online forum, another member of the BellKor team, Yehuda Koren, a researcher for Yahoo in Israel, said his team had “a better Test score than The Ensemble,” despite what the rival team submitted for the leaderboard.

So is BellKor the winner? Certainly not yet, according to a Netflix spokesman, Steve Swasey. “There is no winner,” he said.

A winner, Mr. Swasey said, will probably not be announced until sometime in September at an event hosted by Reed Hastings, Netflix’s chief executive. The movie rental company is not holding off for maximum P.R. effect, Mr. Swasey said, but because the winner has not yet been determined.

The Web leaderboard, he explained, is based on what the teams submit. Next, Netflix’s in-house researchers and outside experts have to validate the teams’ submissions, poring over the submitted code, design documents and other materials. “This is really complex stuff,” Mr. Swasey said.

A leading member of The Ensemble, Domonkos Tikk, a Hungarian computer scientist, did not sound too hopeful. “We didn’t get any notification from Netflix,” Mr. Tikk said in a phone interview from Hungary. “So I think the chances that we won are very slight. It was a nice try.”

It seems strange that Netflix called the Bellkor team first, since according to the Leaderboard the Ensemble team submitted the top entry.

UPDATE 2/28: Today’s NYT has a good article on the Netflix Prize and the role of teamwork for developing machine learning systems, Netflix Competitors Learn the Power of Teamwork.

Netflix has announced that the Netflix Prize contest is now closed. Presumably, The Ensemble is the winner, subject to final qualification.

“We are delighted to report that, after almost three years and more than 43,000 entries from over 5,100 teams in over 185 countries, the Netflix Prize Contest stopped accepting entries on 2009-07-26 18:42:37 UTC. The closing of the contest is in accordance with the Rules — thirty (30) days after a submitted prediction set achieved the Grand Prize qualifying RMSE on the quiz subset.
…
Qualified entries will be evaluated as described in the Rules. We look forward to awarding the Grand Prize, which we expect to announce in a few weeks. However if a Grand Prize cannot be awarded because no submission can be verified by the judges, the Contest will reopen. We will make an announcement on the Forum after the Contest judges reach a decision.”

So what’s left for the judges to do. The rules say that “a panel of senior Netflix engineers and qualified independent judges” need to “ensure that the provided algorithm description and source code could reasonably have generated the prediction sets submitted”. To do this, the candidate winner must produce the algorithm along with a description of who it works. And, of course, before receiving the prize the winner has to grant Netflix

“an irrevocable, royalty free, fully paid up, worldwide non-exclusive license under the Participants’ copyrights, patents or other intellectual property rights in the winning algorithm (”Winning Algorithm”) to reproduce, distribute, display, and create derivative works from the Winning Algorithm and also to make, have made, use, sell, offer for sale, and import products that would otherwise infringe the Winning Algorithm.”

The Netflix Prize was a great idea and generated a lot of interest around the world. It’s been good for the field of AI and its machine learning sub-field, especially. Congratulations to the Ensemble team and condolences to BellKor’s Pragmatic Chaos. I wish there could have been two winners.

UPDATE 2/27: Wait! The winner is still in doubt.

The race for the Netflix Prize is still on.

With just one day left in the 30 day last call period before BellKor’s Pragmatic Chaos (BKPC) was awarded the $1M Netflix Prize for a better movie recommender system, another team has broken the 10% improvement threshold and taken the lead by one hundredth of one percent — The Ensemble.

The Ensemble was formed by the merger of two existing Netflix Prize teams that had been ranked second and third behind BKPC: ‘Grand Prize Team’ and ‘Opera Solutions and Vandelay United’. Here’s how The Ensemble describes it’s genesis.

The crowd is indeed wiser than the individual.

The 10% barrier once seemed distant and insurmountable. But when the contest’s “last call” heralded the heroic achievements of BellKor’s Pragmatic Chaos, the rest of the crowd pondered, and asked why the barrier couldn’t be broken twice.

And lo, as if powered by gravity, Grand Prize Team and Vandelay Industries! began to draw in more and more members. And Vandelay went on to join forces with Opera Solutions, and then Vandelay and Opera united with Grand Prize Team, and then … and then … well, things got so complex we decided just to call ourselves The Ensemble.

We can be sure that there will be a lot of Netflix Prize activity in the coming weeks and maybe months as these two teams compete and perhaps more mergers create super-teams. BKPC and Ensemble could even decide to merge and share the prize. Watch the Netflix Leaderboard for the latest ranking.

UPDATE: I had assumed the 30 day last call would reset with each new leader, like auctions on ebay. Not so. The prize will be won (and lost) today! Here’s the relevant section in the rules:

“To qualify for the Grand Prize the RMSE of a Participant’s submitted predictions on the test subset must be less than or equal to 90% of 0.9525, or 0.8572 (the “qualifying RMSE”). After three (3) months have elapsed from the start of the Contest, when the RMSE of a submitted prediction set on the quiz subset improves beyond the qualifying RMSE an electronic announcement will inform all registered Participants that they have thirty (30) days to submit additional candidate prediction sets to be considered for judging. At the end of this period, qualifying submissions will be judged (see Judging below) in order of the largest improvement over the qualifying RMSE on the test subset. In the case of tied RMSE values on the test subsets, the submission received earliest by the Site will be judged first.”

The August 2009 CACM has a short note, Just for You (pdf), on recommender systems and the Netflix prize by BKPC member Don Monroe that includes a visualization by Ensemble member Chris Hefele.

Spotted on Hacker News. See Techcrunch also.

UPDATE II: The Netflix Prize contest has closed.

John Markoff has an article for tomorrow’s New York Times, Scientists Worry Machines May Outsmart Man on a recent AAAI study on the future of AI.

“A robot that can open doors and find electrical outlets to recharge itself. Computer viruses that no one can stop. Predator drones, which, though still controlled remotely by humans, come close to a machine that can kill autonomously. Impressed and alarmed by advances in artificial intelligence, a group of computer scientists is debating whether there should be limits on research that might lead to loss of human control over computer-based systems that carry a growing share of society’s workload, from waging war to chatting with customers on the phone.”

The study was commissioned by AAAI to “to explore and address potential long-term societal influences of AI research and development”. Look for a report published by AAAI later this year. The study involved twenty-five participants who were divided into three subgroups: on concerns, control and guidelines, the nature and timing of disruptive advances, and ethical and legal issues.

There was a panel session earlier this month at IJCAI where some of the study participants discussed highlights from the study. Hopefully this was filmed and the results will be added to the videolectures.net IJCAI09 collection.

While I am generally skeptical of an impending technological singularity, which seems to sum up many of the concerns some have, there are aspects of the future that I do wonder about. At the top of my list is what will happen when virtually all of human knowledge is published on the Web (as it nearly is now) in a for that machines can understand. I’m pretty sure that this will happen in the next decade or two, either through the current Semantic Web approach (as a web of data) or by gradually improving techniques for machine understanding of human languages and images.

The latest Journal Citation Reports (2009) published by Thomson Reuters shows that the Journal of Web Semantics continues to enjoy a very high impact factor. The 2008 measure was 3.023, which was the 12th highest out of the 94 journals in the category of Computer Science, Artificial Intelligence.

Thomson Reuter’s journal impact factor is a measure of the frequency with which the average article in a journal has been cited in a particular year. The 2008 impact factor is computed as the citations received in 2008 to all articles published in 2006 and 2007, divided by the number of “source items” published in 2006 and 2007.

BellKor’s Pragmatic Chaos has broken the 10% barrier, a feat that may have won them the $1M Netflix prize. We’ll know for sure in 30 days.

“June 26, 2009: Today our team submitted our solution to the Netflix Prize, resulting in a score of .8558, which corresponds to an improvement over Netflix Cinematch algorithm of 10.05%. This is the first submission in the competition to break the 10% barrier and sets off a 30 day period where all competitors are invited to submit their best and final solutions.

The prize is the award by Netflix for an open competition that started in October 2006 for the best collaborative filtering algorithm predicting user ratings for films from a database of previous ratings. Today the BellKor’s Pragmatic Chaos team submitted an entry that improved on the existing algorithm by 10.05%, exceeding the 10% improvement threshold required of a winner. The team is a collaboration between people from Pragmatic Theory, Commendo, Yahoo and AT&T.

“The Netflix Prize seeks to substantially improve the accuracy of predictions about how much someone is going to love a movie based on their movie preferences. Improve it enough and you win one (or more) Prizes. Winning the Netflix Prize improves our ability to connect people to the movies they love.”

The new Scientist reports on a recent paper by CMU psychologist Don Moore that shows that people prefer advice from confident sources even when they have a poor track record.

Moore argues that in competitive situations, this can drive those offering advice to increasingly exaggerate how sure they are. And it spells bad news for scientists who try to be honest about gaps in their knowledge.
…
In Moore’s experiment, volunteers were given cash for correctly guessing the weight of people from their photographs. In each of the eight rounds of the study, the guessers bought advice from one of four other volunteers. The guessers could see in advance how confident each of these advisers was (see table), but not which weights they had opted for.
…
Describing his work at an Association for Psychological Science meeting in San Francisco last month, Moore said that following the advice of the most confident person often makes sense, as there is evidence that precision and expertise do tend to go hand in hand. For example, people give a narrower range of answers when asked about subjects with which they are more familiar”

Why aren’t we better at recognizing cover-confidence? There must be some evolutionary fitness in this, at least for humans. There can be a big penalty in indecision or vacillation. I wonder if we will see the same phenomenon in systems of cooperating autonomous agents?

Here’s the paper:

Joseph R. Radzevick and Don A. Moore, Competing To Be Certain (But Wrong): Social Pressure and Overprecision in Judgment, 21st Annual Convention of the Association for Psychological Science, May 2009.

Overprecision in judgment is both the most robust and the least understood form of overconfidence. Overly precise judgments claim more certainty than is objectively warranted. In this paper, we investigate whether the competitive social pressure of a market contributes to overprecision among those competing for influence. We find evidence that markets do indeed exacerbate overprecision. This evidence comes from two experiments in which advisors attempt to sell their advice. In the first experiment, advisors must compete with other advice sellers. In the second, advisors and decision makers are paired. Overprecision exists in both studies, and it helps advisors’ sell their advice. However, the market also exacerbates overprecision. We discuss the strategic implications of these results.

Price Waterhouse Coopers is one of the largest “professional services” organization and has always been strong on technology consulting and advice. The Spring issue of their quarterly Technology Forecast journal focuses on the Semantic Web. This is from the table of contents

• 04 Spinning a data Web. Semantic Web technologies could revolutionize enterprise decision making and information sharing. Here’s why.
• 20 Making Semantic Web connections. Linked Data technology can change the business of enterprise data management.
• 16 Traversing the Giant Global Graph. Tom Scott of BBC Earth describes how everyone benefits from interoperable data.
• 28 From folksonomies to ontologies. Uche Ogbuji of Zepheira discusses how early adopters are introducing Semantic Web to the enterprise.
• 40 How the Semantic Web might improve cancer treatment. M. D. Anderson’s Lynn Vogel explores new techniques for combining clinical and research data.
• 46 Semantic technologies at the ecosystem level. Frank Chum of Chevron talks about the need for shared ontologies in the oil and gas industry.

You can download the free 58 report here. You can also read a note on the issue in ReadWriteWeb, which focuses on linked data and interoperability.

“A new PricewaterhouseCoopersTechnology report explains how the Semantic Web and Linked Data can help enterprises manage their large scale data better. The PwC Center for Technology and Innovation team spent several months researching and analyzing the problem of data silos in enterprises – and what solutions are being developed to help with that problem. The answer, according to PwC, is Semantic Web techniques. PwC believes that the Semantic Web offers a practical way to address the problem of large-scale data integration. … “

(Spotted on publi-lod@w3.org)

Google wave looks interesting. Google describes it as “a new tool for communication and collaboration on the web” and it’s a funny mix of email, instant messaging, wikis, and Facebook wall interactions. Or maybe IRC for the new century. This is from a post, Went Walkabout. Brought back Google Wave, on the Google blog.

“A “wave” is equal parts conversation and document, where people can communicate and work together with richly formatted text, photos, videos, maps, and more. Here’s how it works: In Google Wave you create a wave and add people to it. Everyone on your wave can use richly formatted text, photos, gadgets, and even feeds from other sources on the web. They can insert a reply or edit the wave directly. It’s concurrent rich-text editing, where you see on your screen nearly instantly what your fellow collaborators are typing in your wave. That means Google Wave is just as well suited for quick messages as for persistent content — it allows for both collaboration and communication. You can also use “playback” to rewind the wave and see how it evolved.”

Google Wave is not available yet, but you can sign up to be notified when it’s launched.

Here’s a random thought. Our models for communication in multiagent systems (e.g., KQML and FIPA) were informed by if not based on email and, to a lesser degree, IM. If Wave is a useful new communication model for humans, does it have a counterpart for software agents? If so, I suspect that ideas from the Semantic Web will be useful to provide a “rich content” for agents.

For more views, see posts by o’reilly, techcrunch, BusinessWeek and Gabor Cselle.

Not only do you have to choose title of your papers, posts and web pages well, their first two words should be chosen to carry the message. Jakob Nielsen reports on UI research showing that the first 11 characters of links and headlines are important in forming some idea of what the item is about.

First 2 Words: A Signal for the Scanning Eye
“Our newest usability study … tests how well users understand the first 11 characters of a website’s links and headlines. For example, we’d represent this article by the “First 2 Wor” string. … Why test text that’s so severely truncated? Because online reading is often dominated by the F-pattern. That is, people read the first few listed items somewhat thoroughly — thus the cross-bars of the “F” — but read less and less as they continue down the list, eventually passing their eyes down the text’s left side in a fairly straight line. At this point, users see only the very beginning of the items in a list. …”

Nielsen calls the initial few words in a title “nano-content”. While it’s hard to pack some ideas into 11 characters, it sounds like a good goal.

Choosing the words for a link or title carefully is a key to influencing search engines — these words are given higher weight when indexing the associated content. But search engines don’t scan like humans, so putting the most relevant early in the string helps when a person is shown a list of results.