Does anyone know if fb face recognition can actually work for all 800 million users or does its tagging do something like nearest neighbor to your friends which I imagine is a simpler problem.
I would also assume that Facebook's recognition performance is heavily dependent on the fact that everyone has a limited friend circle, because then the requirement is only that you can be distinguished among the few hundred or thousand people you've ever been photographed with, not the 100s of millions of users you haven't.
While not directly related (nor the method they are probably using), here's a project that describes how using others in your photographs can help recognition: http://lear.inrialpes.fr/pubs/2008/MV08/
I'd argue that given facebook's dataset of low-resolution photos in crappy lighting conditions, it could actually be 100% impossible. That is, amongst 800 million people, there are bound to be people who look exactly the same as me with available data.
I mean, do we have any evidence whatsoever that given a corpus of photos of almost a billion people, there's any way to pick out photos of a given person without a very high probability of (many) false positives?
I've seen probably five or six people over the years that in certain photos I wouldn't be able to distinguish from myself, especially in real world situations with crappy lighting, poor focus, etc. It's rare, sure, but with a billion people, "rare" means you'll "only" see, what, a thousand cases? I think there's just too much ambiguity in photos (and looks in general), not that we necessarily lack the right algorithms or anything like that.
However, I do believe that the meta-data that Facebook has on all of us is probably enough to get damn close in most cases, even if people don't have friend connections. Especially if they've got some location data...
Besides, for the purposes of what this article is talking about, I'd guess that if someone looks similar enough to the person you saw on the subway to falsely trigger a face match, you'd still probably be interested in following up on that "missed connection".
To test humans: Take city of million people. Take photo of one person. Proceed to ask every person in said city "who is this?" Most likely answer is "no idea", so only consider labeled answers.
You will obviously get multiple answers for the same photo due to look-alikes. I suspect the look-alike problem is so great that even the best training optimization could not achieve >= 50% system labeling accuracy for a picture of a single person with no other context.
You may be able to achieve 50+% labeling accuracy when you present many photos of the unknown individual to those million people, especially if that individual is pictured with other individuals.