Slashdot Mirror

← Back to Stories (view on slashdot.org)

Genetic Algorithm Helps Identify Criminals

Posted by ScuttleMonkey on from the playing-to-your-strengths dept.

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."

19 of 84 comments (clear)

  1. Re:What's genetic about that? by Cyberax · · Score: 4, Informative

    Uhm....

    http://en.wikipedia.org/wiki/Genetic_algorithm ?

    The word 'genetic' itself has nothing to do with DNA.

  2. GA vs. Hillclimbing by jockeys · · Score: 4, Informative

    it seems to me that if you pick the best face from each "generation" and then randomly modify it and pick the best from the next generation, you are merely hillclimbing:
    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.

    --

    In Soviet Russia jokes are formulaic and decidedly non-humorous.
    1. Re:GA vs. Hillclimbing by Lemmeoutada+Collecti · · Score: 2, 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?

      --

      You can have it fast, accurate, or pretty. Pick any 2.
    2. Re:GA vs. Hillclimbing by Zerth · · Score: 2, 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.

    3. Re:GA vs. Hillclimbing by eh2o · · 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.

  3. The scene opens with... by Anonymous Coward · · 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!"

  4. Does it swim? by bugnuts · · Score: 4, 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.

    1. Re:Does it swim? by Kozz · · Score: 3, 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.

      --
      I only post comments when someone on the internet is wrong.
  5. Re:History Lesson? by Eravau · · Score: 2, Funny

    Wow I totally went Slashdot on that and didn't RTFA.

    You didn't even RTFSummary... let alone RTFA.

  6. How valid does it turn out to be? by PatHMV · · Score: 2, Insightful

    There's a fair amount of research on the performance of memory and how our recall of events and things is affected by the very act of being questioned about and actively recalling those memories. 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, have them look at the person they will have to describe and have sketched, then put them in front of the software (do a control group using traditional sketch-artist techniques, while you're at it. You should be able to do an objective evaluation of the accuracy of the sketch by mathematically comparing it (using existing algorithms developed for facial recognition) to determine just how close the resemblance is.

  7. How do you measure success? by Hatta · · Score: 2, 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?

    --
    Give me Classic Slashdot or give me death!
    1. Re:How do you measure success? by jonbryce · · Score: 2, 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.

  8. Better version.... by wowbagger · · Score: 2, Informative

    http://www.20q.net/startg_enUS.html

    --
    www.eFax.com are spammers
  9. It's about time for GP by Kingrames · · Score: 2, Interesting

    I got the opportunity to do a genetic algorithm at my university for one of my projects, and I'm surprised that only now is this tech becoming slightly popular.

    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.

    --
    If you can read this, I forgot to post anonymously.
    1. Re:It's about time for GP by glwtta · · Score: 2, Interesting

      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.

      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 several different niches.

      --
      sic transit gloria mundi
    2. Re:It's about time for GP by Delkster · · 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 in general isn't quite as positive as yours. The idea certainly is aesthetically pleasing, and you can, in theory, try to apply a GA to pretty much any optimization problem, but how well GAs work really depends a lot on the problem: the very nature of the problem (does it fulfill the building block hypothesis, or whatever magic is that makes GAs work for some problems?), what kind of a landscape the search space provides, what kinds of cases of the problem are more likely in your application, etc. That's not including all the nontrivial problem-specific tweaking that will be needed in a practical application of a GA, such as how to encode or represent the solutions (has a big effect on how much good genetic crossover does).

      I'd rather say that GAs have worked well for some specific problems, and some new specific applications will probably still emerge, but I'm not sure they will ever become very generally applicable. They had a chance, but it turned out that they mostly work just for some particular problems, not others, and nobody seems to really know very well why.

  10. This is actually very cool... by jarrowwx · · Score: 3, Insightful

    This technology, at its core, is a little bit like PicBreeder. 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.

    • Imagine, a site that you can go to and evolve the face of the woman of your dreams?
    • Or the face of a character in the book you are writing.
    • Or an avatar for the video game you are playing.
    • Or use the basic tech to create random faces for the crowd for an animated movie.

    Personally, I would *LOVE* to be able to tinker with technology like this.

  11. You got that right. by NoYob · · Score: 4, Insightful
    I was thinking of a test case for this - the picture of Solomon didn't impress me one bit. Now, you can't have folks mugging test subjects or other violent things BUT there is way.

    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.

    --
    It's NOT me! It's the meds! I'm on 1000mg of Fukitol.
  12. Re:What's genetic about that? by Cyberax · · Score: 2, Informative

    The word 'genetic' predates the discovery of DNA: http://www.etymonline.com/index.php?term=genetic