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.
It's not nearly good enough for this. While I don't know what they're doing, it doesn't matter -- the state of the art in face recognition is far lower than what this requires.
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/
So, what if once you upload the "missed connection" photo, Facebook tags it with GPS and filters possible matches against your current location? That would narrow it down quite a bit. I assume they have enough GPS data from other users' photos and status updates to at least place them generally within a state or city at a given time.
Without social network context (you are much more likely to meet a friend of a friend than someone living in a country half way around the world), that is impossible with current-day research.
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'd probably argue that this is not only an unsolved research problem, but an unsolvable one.
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".
Completely agreed. Even out of a million people, this is probably impossible. I'm quite sure humans couldn't do it.
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.
Comments
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.
It's not nearly good enough for this. While I don't know what they're doing, it doesn't matter -- the state of the art in face recognition is far lower than what this requires.
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/
So, what if once you upload the "missed connection" photo, Facebook tags it with GPS and filters possible matches against your current location? That would narrow it down quite a bit. I assume they have enough GPS data from other users' photos and status updates to at least place them generally within a state or city at a given time.
Without social network context (you are much more likely to meet a friend of a friend than someone living in a country half way around the world), that is impossible with current-day research.
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 would bet this is true. That kind of processing is not insignificant but Facebook seems rather casual about it.
I'm not quite sure by what you mean by "this is true," but computation is not the bottleneck here. It's an unsolved research problem.
I'd probably argue that this is not only an unsolved research problem, but an unsolvable one.
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".
Completely agreed. Even out of a million people, this is probably impossible. I'm quite sure humans couldn't do it.
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.