Forgot your password?
typodupeerror
Software Programming

Genetic Algorithm Helps Identify Criminals 84

Posted by ScuttleMonkey
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."
This discussion has been archived. No new comments can be posted.

Genetic Algorithm Helps Identify Criminals

Comments Filter:
  • GA vs. Hillclimbing (Score:5, Informative)

    by jockeys (753885) on Monday November 30, 2009 @04:31PM (#30274176) Journal
    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.
    • 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?

      • by Brad Mace (624801)

        I also have to wonder how they are accounting for selection bias

        are they accounting for racial variances

        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)

          by Zerth (26112)

          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.

          • by eh2o (471262) on Monday November 30, 2009 @07:02PM (#30276578)

            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.

          • by epine (68316)

            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

    • by vlm (69642)

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

      • by jockeys (753885)
        that's a very good point, it didn't cross my mind that they could be doing localized hillclimbs, but that's definitely very possible. good point indeed.
      • by ascari (1400977)
        After watching the simulation of six hillclimbers "breeding" for the fourth time the witness cried "Yes, it's him! It's him! Just get me out of here!"
    • by Tablizer (95088)

      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

      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.
             

      • by jockeys (753885)

        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.

        • by Tablizer (95088)

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

  • 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

    • by Deflagro (187160)

      Wow I totally went Slashdot on that and didn't RTFA. -2 to INT.

    • 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

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

    • by omnichad (1198475)

      At least read the summary. Helps identify as in helps create a sketch.

    • Damn, you are that old? No wonder that you only vaguely remember it, but my goodness, you must be the oldest Slashdotter.
  • by Anonymous Coward on Monday November 30, 2009 @04:34PM (#30274198)

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

    by bugnuts (94678) on Monday November 30, 2009 @04:36PM (#30274242) Journal

    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]

    • Re:Does it swim? (Score:4, Informative)

      by Kozz (7764) on Monday November 30, 2009 @05:16PM (#30274842)

      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.

      • by bugnuts (94678)

        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

        • by glwtta (532858)
          Yeah, traditionally "binary search" refers to locating an element in a sorted list, even though here you are searching a (binary) decision tree, calling it a "binary search" is confusing.

          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
    • by jockeys (753885)
      Alsing's program is very cool, and I've had a lot of fun playing with it, but it is NOT genetic... it's hillclimbing.
  • 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)

      by Anonymous Coward
      Today, still wanted by the government, he survives as a soldier of fortune.
    • by Sir_Lewk (967686)

      And this is different from any other sort of eye witness accounts how exactly?

      • Unlike now where the "victim" needs to think to remember what the "suspect" looks like, with this, it'll be easier to describe the "suspect" with an "instant" response (photo); just keep spewing crap till the new picture matches the first picture.
  • by PatHMV (701344) <post@patrickmartin.com> on Monday November 30, 2009 @04:46PM (#30274386) Homepage
    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.
    • by NoYob (1630681) on Monday November 30, 2009 @04:56PM (#30274560)
      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.

      • by bws111 (1216812)
        What are you talking about? This is no different than a regular old police sketch artist, just quicker. I highly doubt anyone has been convicted based solely on a sketch. This just provides the police with an image of someone they should be looking for. 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. The sketch will never get to court because it is not evidence,
        • by NoYob (1630681)
          That's how it works on TV.

          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

          • by mhajicek (1582795)
            It will be even easier to convince a jury to convict someone when you show a CGI "photo" that looks like him. Lots of people trust computer output and ignore the human link.
        • The problem is that people's memories are not permanent. If you show them a bunch of different (but similar) images of people, it may well completely change what they remember about the suspect. A police sketch artist doesn't show any faces until they're done.
        • by swillden (191260)

          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

      • by LUH 3418 (1429407)
        There is at least one reason why this might work better than a regular police sketch. People's memories are bad, but I believe people have an easier time looking at something and identifying it than recalling specific details about that something on demand. Case in point: you may not be able to exactly remember the melody or the lyrics of a song you head only once, but if that song is played, you will be able to tell you heard it before, and it seems likely that you would be able to tell if the melody wasn'
    • by vlm (69642)

      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%

  • by Hatta (162192) on Monday November 30, 2009 @04:46PM (#30274394) Journal

    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?

    • My sketch ended up as a pink elephant ... go figure!

    • Re: (Score:3, Insightful)

      by jonbryce (703250)

      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.

      • by swillden (191260)

        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.

        • by swillden (191260)

          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.

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

    • by Tablizer (95088)

      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.

  • by Kingrames (858416) on Monday November 30, 2009 @04:53PM (#30274502)
    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.
    • Re: (Score:3, Interesting)

      by glwtta (532858)
      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 se
      • by Kingrames (858416)
        being a programmer, I interchange the two all the time because of the overlap. Of course gp isn't ga, in the same sense that doing a traveling salesman problem by hand doesn't count as programming an answer, even if you are programmatically solving it.

        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
        • by glwtta (532858)
          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

          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
          • by Kingrames (858416)
            Well, that's true, but I think GP is a stepping stone to another kind of evolutionary programming style.

            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
            • by glwtta (532858)
              I may be wrong, probably am, but it sounds a little like you are just redefining existing terms with more awesomer names.

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

      • > 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)

      by Delkster (820935)

      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

    • by Tablizer (95088)

      essentially breathe life into binary data, becoming a God, and allowing 'your people' to evolve into a solution to your problem.

      Sergeant: "Odd, why do all the people we arrest look like Jesus?"
         

  • by jarrowwx (775068) on Monday November 30, 2009 @04:54PM (#30274526) Homepage

    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.

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

    • by Kingrames (858416)
      but you already can!

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

    • by vlm (69642)

      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?

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

  • this e-fit [sky.com] that helped the Bolivian Police track down a murder suspect

  • by t0qer (230538)

    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

  • My name is Dr Matthew Maylin, I developed this software at the university of Kent during my PhD, and continue to develope it as the sole software engineer for the company. The algorithm used is an evolutionary algorithm, implementing random mutations, but no cross-over or mutation. Although the user does have the option to 'bred'/combine certain faces within the software. The method uses a statistical model of the human face (Cootes et el 2001), and at anyone time is restricted to a sample to a single eth

What this country needs is a dime that will buy a good five-cent bagel.

Working...