Google Blog Reader Recommender November 30, 2007
Posted by Andre Vellino in Collaborative filtering, Recommender service.9 comments
Don’t you love it when Google just slips in these new features like easter eggs? The new Blog Reader recommender appears to be using a hybrid collaborative-filtering + content (from query expansion), which seems to work pretty well. I like the fact that the relevance ranking doesn’t seemed to be biased by the number of subscriptions to the blog.
Eternity II November 28, 2007
Posted by Andre Vellino in Logic.7 comments
If you think that P=NP is a purely theoretical question, think again. It’s been more than 30 years now since Cook and Reckow’s seminal paper “On the lengths of proofs in the propositional calculus” and the Millenium Prize (from the Clay Mathematics Institute) for solving P=NP is currently $1M.
It seems bizarre that the stakes are even higher ($2M) for solving a particular instance of an NP-complete problem – the Eternity II puzzle. The prize is a clever marketing ploy to induce the foolhardy to buy it.
Eternity II is a variant on Tetravex and prospective buyers are well advised to read the proof by Takenga and Walsh that Tetravex is PN-complete or the paper “Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity“. The reader of either paper will quickly conclude that there are easier ways to make $2M – you could take another NP-Complete problem, make a game out of it and sell the game 
– or you could crack the public key encryption in SSL and become an internet pirate.
Better still, you could just buy a lottery ticket. The probability of your winning a lottery jackpot are quite a bit higher than solving Eternity II. From his explanation of the design of Eternity II, Brendan Owen estimates that the best possible algorithms for this puzzle will require the exploration of 2×10^47 possibilities.
So if you don’t mind making Eternity II’s inventor – a British Viscount who denies the anthropogenic nature of Global Warming and admires Margaret Thatcher – more rich than he already is, then this game’s for you!
Tensors for Multi-Dimensional Recommenders November 24, 2007
Posted by Andre Vellino in Collaborative filtering, Digital library, Recommender service.5 comments
It’s good to know that the intellectual heavy-lifting is there when you need it. The ideas in Peter Turney’s recent tech report on tensors may well be of some use to me when it comes to implementing the multi-dimensional component of the Synthese Recommender that Dave Zeber and I are developing at CISTI. The charts from our presentation at WPRS workshop at Web Intelligence give some indication of how we intend to build these multi-dimensional matrices.
This component of our system is for some time in the future, but I expect the resulting tensors may be a challenge even for Peter’s MATLAB code (given in the paper). Fortunately, I think this can be combined with another idea for distributing recommenders across different subject domains, as described by F. Ricci et al. at RecSys 2007. That’s one way of both reducing the dimensionality of the original tensors and parallelizing the computation, but I agree with Daniel Lemire observation that Peter’s code can be optimized for parallel processors as well.
CYC Game November 17, 2007
Posted by Andre Vellino in Knowledge Representation, Logic, Semantics.2 comments
In the “neat vs. scruffy” debate in AI, my dedication to the “neat” camp is wavering. Granted that logic is interesting and useful, but is it really the right formalism for knowledge representation?
Take the CYC project, for example. It is tempting to believe, following Witgenstein’s Tractatus that “the world is the totality of facts” and “the facts in logical space are the world”. And the CYC project has been driven by this temptation: OpenCYC now contains about 300,000 “concepts”, 3,000,000 “assertions” and 26,000 relations between them and an inference engine with which to draw conclusions.
If you believe in helping CYC to learn, you can play this collaborative game to help CYC learn more facts about the world. The game composes (seemingly random) questions about relations that might be meaningful or true or false and you get to tell it whether these generated propositions are true or not.
Turing Machine Controversy November 13, 2007
Posted by Andre Vellino in Epistemology, Logic.1 comment so far
In a previous post, I noted that Alex Smith had won a 25,000 prize for finding the smallest Universal Turing Machine. When I saw that the Prize Committee included Martin Davis, Marvin Minsky and Dana Scott, I figured there wasn’t much question about the correctness of the proof.
But it didn’t take long after this prize was “won” for some respectable academics on the FOM (Foundations of Mathematics) mailing list, notably Vaughn Pratt, to start poking holes in the proof. The current state of the debate is summarized in this post and it looks like Alex Smith is losing the argument.
Furthermore, there’s some question about who exactly on this committee checked the proof. The argument seems to have spilled over to the SciAm blog.
You’d think there wouldn’t be anything controversial about a mathematical proof. But where there are strong personalities, self interest and money involved, perhaps it’s inevitable that even truths in mathematics are disputable.
BART Ticket Machine UI November 11, 2007
Posted by Andre Vellino in User Interface.add a comment
I have almost nothing but praise for the Bay Area Rapid Transit (BART) system – which I used to get from SF Airport to Fremont a last week. Like all great cities, at its heart lies a good public transit system.
But I did notice something wrong: the user-interface for the ticketing system. It’s instructive to understand why it’s a problem.
