Genetic Algorithm Helps Identify Criminals 84
Ponca City, We love you writes to tell us that a new software approach to police sketch artists is finding surprising success in a trial run of 15 police departments in the UK and a few other sites. The software borrows principles from evolution with an interactive genetic algorithm that progressively changes as witnesses try to remember specific details. Current field trials are reporting an increase in successful identification by as much as double conventional methods. A short video with a few working shots of the new "EFIT-V" system is also available on YouTube. "[Researcher Christopher Solomon]'s software generates its own faces that progressively evolve to match the witness' memories. The witness starts with a general description such as 'I remember a young white male with dark hair.' Nine different computer-generated faces that roughly fit the description are generated, and the witness identifies the best and worst matches. The software uses the best fit as a template to automatically generate nine new faces with slightly tweaked features, based on what it learned from the rejected faces. 'Over a number of generations, the computer can learn what face you're looking for,' says Solomon. The mathematics underlying the software is borrowed from Solomon's experience using optics to image turbulence in the atmosphere in the 1990s."
Re:What's genetic about that? (Score:5, Informative)
Uhm....
http://en.wikipedia.org/wiki/Genetic_algorithm [wikipedia.org] ?
The word 'genetic' itself has nothing to do with DNA.
Re: (Score:2)
The word 'genetic' itself has nothing to do with DNA.
Yes it does. The usage of it, in this case, does not.
Re: (Score:3, Informative)
The word 'genetic' predates the discovery of DNA: http://www.etymonline.com/index.php?term=genetic [etymonline.com]
Re: (Score:1)
Re: (Score:1, Informative)
"Genetic algorithms are a particular class of evolutionary algorithms (EA) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover." [wikipedia.org]
Re: (Score:2)
From wikipedia:
A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms (EA) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover.
I'm guessing the main feature here is crossover. Basically you have the eyebrows that look like the suspect in one, the jawline in another and it'll probably show you a crossover with both. With a little bit of memory of what features you've already voted for and against in the past you can "assemble" a face by parts adjusting the different features as you see them coming together. It doesn't really sound too complex to me, but making it actually work is a lot of effort.
GA vs. Hillclimbing (Score:5, Informative)
http://en.wikipedia.org/wiki/Hill_climbing and not using a proper GA. This seems to be something that the EigenFit package does.
TFA says that up to six faces may be "bred" together resulting in a new generation, which would indeed be genetic, so the EvoFit package seems to be genuinely genetic.
TFA is unsurprisingly short on details, but it seems to me that EigenFit is using hillclimbing (at least partially) while EvoFit is using shotgun-genetic.
Re: (Score:3, Interesting)
I also have to wonder how they are accounting for selection bias, where the witness selects the face that appears most like their internal image of the "bad guy" rather than the one closest to the actual suspect. I recall reading some studies a while back where they found that most witnesses are not that reliable when it comes to things like facial details.
Also, are they accounting for racial variances, such as the word white being used for anyone of light skin type?
Re: (Score:2)
I don't see how either of those issues are affected by this new technique. It's something the police have had to deal with long before this, so I assume they'll continue to do so.
Re: (Score:3, Insightful)
Instead of a sketch artist listening to a description and modifying based on feedback, the system will be "prompting" the witness.
Prompting has been shown to cause false memories of details, so I imagine it will be even worse when you consider the "the computer generated this, it must be right" phenomenon.
Re:GA vs. Hillclimbing (Score:5, Informative)
This method could be modified to avoid the prompting problem. Essentially the entire test can be buried in noise (i.e., random faces) so that the subject is never aware of the convergence process. It should also be possible to modify it to detect when the subject has insufficient information to identify the target. These sorts of techniques are quite common in experimental psychology when you need to suppress adaptation effects or do testing for medical purposes where the subject can't be trusted to be truthful.
Re: (Score:2)
Instead of a sketch artist listening to a description and modifying based on feedback, the system will be "prompting" the witness.
Many years ago, in a part of town I don't normally visit (touristy) in pursuit of a mother's day present, I ended up instead in pursuit of a man who assaulted a woman in an ocean-front parking lot.
I was standing there with my credit card about to purchase some crafty pottery thing, and then we heard a woman scream from across the road. The clerk, an attractive blond with big hair, spots this man emerging from a downward sloped parking lot, churning his short little legs toward the warehouse and trendy rest
Re: (Score:2)
TFA says that up to six faces may be "bred" together resulting in a new generation, which would indeed be genetic, so the EvoFit package seems to be genuinely genetic.
Worst case scenario, by breeding faces together, they may only mean six simultaneous hillclimber algorithms, one for the chin, one for the eyes, snout, eyebrows, cheeks, lips, completely independent hillclimbers, one for each region...
Re: (Score:2)
Re: (Score:1)
Re: (Score:1)
How is natural selection *not* hill-climbing? I agree that the hopped valleys may be much deeper in real evolution, but it's merely a matter of degree, not existence of.
Re: (Score:2)
How is natural selection *not* hill-climbing?
if you are not "breeding" more than one species and adding a bit of randomizing, it's not a proper genetic algorithm.
by that same logic, irl asexual creatures DO reproduce and evolve by hillclimbing (with an added random factor for mutation). saying something is a genetic algorithm has specific connotations, I fully agree that the metaphor is not always consistent with its biological origins.
Re: (Score:1)
They *are* randomizing it according to the original post I quoted. If you mean there's no chromosome cross-snipping to emulate sexual reproduction, my understanding is that GA's don't require that to be called GA's. It's merely an additional technique to add on to the mix if desired. (cross-snipping's usefulness depends on the subject matter, according to what I've read.)
History Lesson? (Score:1)
Didn't they used to do this like 100 yrs ago? "See he looks like an animal, therefore he must be criminal" I vaguely remember seeing something along the lines of that being a prosecution's argument and it being accepted.
It's funny that they may have been onto something? :P
Re: (Score:2)
Wow I totally went Slashdot on that and didn't RTFA. -2 to INT.
Re: (Score:2)
Re: (Score:2, Funny)
You didn't even RTFSummary... let alone RTFA.
You're going to want to read the article (Score:2)
This is about evolving an image from generic features to a specific person by having the viewer rate a series of generated faces from best-to-worst matching.
Not that this is any better. At best it's leading a witness because it promotes guessing, at worst I feed source imagery of stereotypical "bad guys" and voila: every Snidley Whiplash lookalike in the country is running for the hills.
-Matt
Re: (Score:2)
Um, no?
This is about an eyewitness trying to create an image of the criminal for police to track down, by choosing between multiple different images based on their last choice. Instead of the traditional approach of choosing eyes, hair, lips, nose etc individually and then assembling the final image, the witness guides the system towards the result.
It has nothing to do with deciding that someone is a criminal because of their genetics. The title could be taken to mean that, but the summary is pretty clear.
Re: (Score:2)
At least read the summary. Helps identify as in helps create a sketch.
Vaguely remember? (Score:2)
The scene opens with... (Score:3, Funny)
...a police artist sitting at a sketch pad drawing a helical structure. He glances back at a witness sitting across the desk. After drawing two intertwined double-helices, he begins filling in base pairs like the rungs of a ladder. He draws Guanine joining a Cytosine. And just as he finishes the Adenine joining a Thiamine the witness screams "That's the guy!"
Does it swim? (Score:5, Interesting)
Yes: Is it a frog?
No: Please enter the type of animal.
This article reminds me of the old Animal game, where it does a binary search for whatever type of animal you're thinking. It's been expanded to handle all types of nouns, with a 15-questions interface that is uncanny.
For another computer-generated facial reconstruction test, take a look at the mona lisa. [rogeralsing.com]
Better version.... (Score:2, Informative)
http://www.20q.net/startg_enUS.html [20q.net]
Re:Does it swim? (Score:4, Informative)
Algorithm wonks please correct me if I've got it all wrong, but... I believe a binary search is only performed on a sorted list of items. What you're describing sounds more like a well-trained decision tree.
In a similar manner there's pages out there in the triple-dub that ask you questions in an attempt to guess what fictional tv/movie character you're thinking of. It is trained by the very people who are "playing" the game so that at the end, if the program did not guess correctly, you can enter your answer. And provided you haven't been giving bogus data, you're helping to provide training data which makes the decision tree even stronger.
Re: (Score:2)
I believe a binary search is only performed on a sorted list of items. What you're describing sounds more like a well-trained decision tree.
If you think of each animal being reached by a traversal of yes/no questions, you can construct a "gene" consisting of 0s and 1s, which would tell you how to reach that particular animal. In that manner, the animals are actually sorted on the gene. The binary search is exactly like the tree with < and > leaves, but is instead a question with yes/no leaves. You'd still have balancing issues with the animal tree, similar to a sorted binary tree.
I was just saying that TFA's software interface reminded
Re: (Score:2)
If we are talking about 20Q [wikipedia.org], it's actually a bit more clever: it's using a neural net, rather than a decision tree, so it can work with ambiguous and contradictory data (it's yes/no/maybe/not-relevant rather than just yes/no, and can deal with intentionally wrong answers). And yeah, even the hand-held version is just pl
Re: (Score:2)
Perfect tool... to throw investigators off (Score:1)
This is the perfect tool to throw someone off.
Commit a crime but "become a victim". Falsely describe who you saw and bam, they're in jail and you are "free".
"Yes ossifer, the man that robbed that liquor store was a black man, about 6-1/2 feet tall, dingy yellow/blonde short hair, lots of tattoos on his body, earrings. Just looking at him, I think he plays basketball.". A short time later after the call goes out, some cops arrest Dennis Rodman for a crime he didn't commit.
Re: (Score:1, Funny)
Re: (Score:2)
And this is different from any other sort of eye witness accounts how exactly?
Re: (Score:1)
How valid does it turn out to be? (Score:3, Insightful)
You got that right. (Score:4, Insightful)
The test case:
Get a group of test subjects - college students are always great for this. Have your "assailant" run up to the subject and Yell, "Hi!" and then hand the "victim" a flower and then run off. Right then and there, the "victim" goes a "files a police report" with the researchers following typical police procedure.
After about a thousand tests on different subjects with statistically significant positive results, then and only then, will I start to believe this "technology" and maybe with more tests will I think it should be allowed as evidence in a court of law.
Other than that it just a gimmick - we're talking about taking people's freedom here or sentencing them to death.
Re: (Score:2)
Re: (Score:1)
Finger prints - another pseudo scientific technique used by the cops.
Look it, every time I read a story about someone who was wrongfully convicted and then spent years in jail, in every single case there was one piece of evidence - usually some sort of eye witness - that put the poor bastard in jail. Now factor in a computer? You know how the ignorant public (the ones usually sitting on a jury panel) trusts anything the "computer" says - especially with all those fictional accounts
Re: (Score:1)
Re: (Score:1)
Re: (Score:2)
Once they find that person they can interview him, get an ID from witnesses, obtain fingerprints, get a search warrant, and all the other stuff that goes along with a criminal investigation.
It's not that uncommon for someone to be convicted on nothing more than a witness identification, perhaps with a little weak circumstantial evidence along for the ride. The risk of something like this (and the risk also exists with police sketches) is that a vague memory will be "firmed up" by viewing the completed sketch. The police then find someone that looks like the sketch, but who maybe only looked vaguely like the actual criminal and put them in a lineup. Based on the original memory, perhaps the
Re: (Score:2)
Re: (Score:2)
Before I relied on this for much of anything, I'd want to see some pretty well controlled studies on just how accurate it is. For example, they should put the test subjects under some kind of stress,
That is an interesting, but tedious way to test the overall system on average across all users. I think I could test the hillclimber algorithm itself, on an individual user, by making the algorithm converge intentionally slowly, simulated annealing style. Then pester the person with lots of very slowly converging and even occasionally diverging sets of faces, and see how "consistent" the persons answers are compared to their final answer. Does the user always select the bushy eyebrows, or only about 50%
How do you measure success? (Score:3, Insightful)
How do they know if this thing actually works? If they're using the computer generated sketch to finger a suspect, and then presenting that sketch as evidence to a jury who convicts, and then using that conviction as evidence of the algorithms accuracy that's just circular reasoning.
The memory is not an immutable thing. It's quite possible that in the process of generating the sketch you are leading the witness on, even implanting memories. So what happens if you generate a sketch that doesn't look like the actual criminal, and present that to a jury and get a conviction. Is that going to be counted as a success?
Well - mine was a failure (Score:1)
My sketch ended up as a pink elephant ... go figure!
Re: (Score:3, Insightful)
They won't present the sketch as evidence to the jury. They will call the witness and ask him to identify the suspect. They will be able to do other things like take fingerprints and DNA samples from the scene and match them to the suspect.
Re: (Score:2)
The memory is not an immutable thing. It's quite possible that in the process of generating the sketch you are leading the witness on, even implanting memories. So what happens if you generate a sketch that doesn't look like the actual criminal, and present that to a jury and get a conviction. Is that going to be counted as a success?
They won't present the sketch as evidence to the jury. They will call the witness and ask him to identify the suspect.
... based on memories that have been partially implanted/modified by the sketching process.
There is some risk here.
They will be able to do other things like take fingerprints and DNA samples from the scene and match them to the suspect.
Assuming there is other evidence, great. If not... people do get convicted on the word of a single eyewitness.
Re: (Score:2)
There is some risk here
To be clear, I'm not claiming that the risk is greater than the risk of having a police sketch artist do the same thing. It may be greater, less or the same. It may even depend on the witness.
Re: (Score:2)
How do they know if this thing actually works?
Especially if no one has actually *seen* Keyser Soze. And like that, poof. He's gone.
Re: (Score:1)
I imagine they use test cases, not (just) actual cases. For example, 40 people see the same candidate in person. Then the group is split up into 2 groups of 20. One group does the traditional method and the other does the GA method to derive 40 sketches total. Then an independent panel of judges who don't know about the GA software rate the sketch matches to the original candidate, and the total for each group's sketches is compared.
It's about time for GP (Score:3, Interesting)
You take a fistful of bad answers to a problem, throw 'em in a breeding pit, and let 'em go at it.
you essentially breathe life into binary data, becoming a God, and allowing 'your people' to evolve into a solution to your problem.
I suppose you could call yourself an 'Intelligent Designer', but that lacks panache.
Re: (Score:3, Interesting)
To answer your question, GA is not more popular because for most real-world problems it's difficult to come up with a good solution representation (one that lends itself well to "breeding"). Though they have been used successfully for a long time in se
Re: (Score:2)
and I am eager to begin a project I'd like to start which would make gp easier for anyone that wanted to pick it up and run with it. I think gp can be used in many more applications than it is now, and I'd like to prove it.
besides, wouldn't it be great if
Re: (Score:2)
Well, good luck with that, though I still suspect that GA (and especially GP) is inherently rather hard, meaning you are unlikely to find a technical solution that will substitute for thorough understanding of the problem domain and lots of practice.
It's not like there aren't already plenty of frameworks [wikipedia.org] that make it next to trivial to get a basic implementation up and runni
Re: (Score:2)
At some point I'd like to design and run an algorithm that uses multiple children at once as a team, instead of just testing each one individually. Sort of like a raid, in WoW, except that the 'characters' would be selected randomly. I think this might be the next step up for genetic programming, because the high-value children would be better performers across multiple groups, not just alone, and it w
Re: (Score:2)
Your "raid group" is just a different way of describing the solution representation. There is no reason why a candidate solution can't be subdivided into parts that are tuned individually. You're still testing the fitness of the complete solution - I'm not seeing how that's different from classical GP.
Re: (Score:1)
> At some point I'd like to design and run an algorithm that uses multiple children at once as a team, instead of just testing each one individually. Sort of like a raid, in WoW, except that the 'characters' would be selected randomly. I think this might be the next step up for genetic programming, because the high-value children would be better performers across multiple groups, not just alone, and it would eventually develop into a system that creates highly specialized individual components, and might
Re: (Score:1)
> Just to be pedantic for a second: Genetic Programming (GP) is a specific application of Genetic Algorithms (GA) where the solution space you are working with is executable programs (or algorithms). So GP is a subset of GA, the two are not interchangeable.
If we're going to be pedantic, then GP is not necessarily a subset of GAs. It depends on how you define a GA: usually a GA is an algorithm that operates on binary strings, and GP is an algorithm that most often operates on expression trees. However,
Re: (Score:2, Insightful)
I think GAs have definitely had a time when they were popular at least as an idea, mostly sometime in the early 90's or so, and there was quite a bit of research into applying them to various problems. They haven't always turned out to perform very well, though. Quite a few attempts have been made towards using GAs as a heuristic to traditional NP-hard combinatorial problems, for example, and while there has been some success, quite often other heuristics have beaten GAs.
My impression of the beauty of GAs i
Re: (Score:1)
Sergeant: "Odd, why do all the people we arrest look like Jesus?"
This is actually very cool... (Score:3, Insightful)
This technology, at its core, is a little bit like PicBreeder [slashdot.org]. It doesn't include the complexification, but the principle is the same.
There is an argument about 'leading the witness' being bandied about as if that makes this thing useless. If you read the articles, they talk about that, and they show that it is no worse than any existing techniques, gets good results, and works for people that can't work with sketch artists.
The reality is, this technology has applications beyond what it is being used for.
Personally, I would *LOVE* to be able to tinker with technology like this.
Re: (Score:2)
get yourself some tools for working in the programming languages of your choice. I recommend 'Go' and 'D', since you'll be playing God.
then, just have fun with smaller projects, like figuring out the best way to fill a rectangle with circles, before tackling really complex problems. Genetic algorithms tend to 'cheat', so it's really best to just experiment with them, rather than reading info from a book.
Re: (Score:1)
figuring out the best way to fill a rectangle with circles
I don't know about best, but I think Mandelbrot has already figured out the prettiest.
Re: (Score:2)
Imagine, a site that you can go to and evolve the face of the woman of your dreams?
Just the face? Thats all? Try again.
Your project has already been done, anyway.
http://en.wikipedia.org/wiki/Averageness [wikipedia.org]
Weirdly enough, the difference between the 1.0 and 10.0 womens face seems to be little more than body fat percentage. Actually, IRL for the whole body, isn't the difference between 1.0 and 10.0 little more than body fat percentage?
Mii Channel (Score:2)
Nine different computer-generated faces that roughly fit the description are generated, and the witness identifies the best and worst matches. The software uses the best fit as a template to automatically generate nine new faces with slightly tweaked features, based on what it learned from the rejected faces.
I immediately thought of the Mii Channel on Wii when I read this. One of the ways to create a Mii is to start with a bunch of randomized faces and pick the one that looks the most like you (or whoever you're modeling). From there, it generates 9 variations of that face for you to choose from. This system is obviously more advanced, but the basic idea is the same.
Yes, but is it better than... (Score:2)
this e-fit [sky.com] that helped the Bolivian Police track down a murder suspect
Porky's (Score:2)
I couldn't help it, this story made me think of an epic scene from the 1982 movie porky's. In the movie a few young men are looking at girls through a peep hole in the girls locker room shower. One young man sticks his talleywhacker through the hole and almost has it torn off by the lesbian'ish PE teacher. Anyways, here's a synopsis of the following scene, courtesy of imdb.
Balbricker: Now, Mr. Carter. I know this is completely unorthodox. But I think this is the only way to find that boy. Now that penis
EFIT-V (Score:1)