Connecting the dots

As I posted previously, I am highly skeptical that any foolproof system can be developed to screen for potential threats.  My previous argument was that in order to have a zero false negative rate for identifying terrorists, it would be impossible to not also have a relatively significant false positive rate.  In other words, the only way to guarantee that a terrorist doesn’t board a plane is to not let anyone board.  A way to visualize this graphically is with what is called a receiver operating characteristic or ROC curve, which is a plot of the true positive rate versus the false positive rate for a binary classification test as some parameter, usually a discrimination threshold, is changed.  Ideally, one would like  a curve that jumps to a true positive rate of 1 for zero false positive rate.  The area under the ROC curve (AROC) is the usual measure for how good a discriminator is.  So a perfect discriminator has AROC = 1.  In  my experience with biological systems,  it is pretty difficult to make a test with an AROC of greater than 90%.    Additionally, ROC curves are usually somewhat smooth so that they only reach true positve rate = 1  at false positive rate = 1.

Practicalities aside, is there any mathematical reason why a perfect or near perfect discriminator couldn’t be designed?  This to me is the more interesting question.  My guess is that deciding if a person is a terrorist is an NP hard question, which is why it is so insidious.   For any NP problem, it is simple to verify the answer but hard to find one.   Connecting all the dots to show that someone is a terrorist is a straightforward matter if you already know that they are a terrorist.  This  is also true of proving the Riemann Hypothesis or solving the 3D Ising model.  The  solution is obvious if you know the answer. If terrorist finding is NP hard, then that means for a large enough population and I think 5 billion qualifies, then no method nor achievable amount of computational power is sufficient to do the job perfectly.


2 thoughts on “Connecting the dots

  1. Search engines, or rather information retrieval systems, have been dealing with this trade off for a long time. We have lots of experience from billions of searches of what people will put up with from false positives and negatives in various text searching contexts. One thing people seem to routinely under estimate is the amount of stuff the gets left out of your search results that is potentially interesting. We just have not good way of knowing it isn’t there. One perceptual challenge of solving this problem is illustrated by the comment “Google can find the best recipe for chocolate chip cookies, but we can’t identify a terrorist.” In practice, we are remarkably good at both, but we always know when we missed the terrorist…

    Re NP hard: Yes.

    But beyond NP hard is determining intent and using it to predict action. To illustrate, how do you stop a terrorist that is convinced to become one by their seat mate only after boarding the plane? Backing off the extreme a little, if someone lives their whole life intending to be a terrorist once, but acting nothing like one in order to preserve the one chance, how can we detect that?

    The best strategy for combating terrorism systemically is resistant, adaptable and resilient organizations at many scales in the over all system (conscientious passengers, well trained attendants, strong cockpit doors, social services for the disenfranchised, education, reliable legal system…). Adapting agents at multiple scales is often a reasonable strategy for addressing NP hard problems as well as rapidly reacting to and recovering from mal-intent. Giving up flying, or even wrongfully accusing 1% of the passengers at the security gate is far to brittle to be sustainable.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s