Awktimization

If you're doing a lot of heavy text crunching with Awk, you've probably found that it can get quite slow very quickly. It always seems to happen whether you program well or not. Unfortunately for us, Awk isn't a very high efficiency tool. But that's not going to stop us. Not today.

You see, the GNU implementation of Awk, gawk, has a built-in profiler that you can use in order to analyze and optimize your Awk scripts. Its beautiful simplicity will cast light on those sinister bottlenecks destroying your performance. To use it, simply call pgawk from the command line on any machine with the GNU Awk installed. (Alternatively, you can pass the --profile option to gawk.) The runtime will execute your script and write the profiler results to a file by default named awkprof.out. This file contains the execution counts for each statement executed in the left margin.

Optimizing the now elucidated bottlenecks in your program should give you a considerable performance boost. However, if after improving on your runtimes, you still find that your program isn't zippy enough, you can put a little bit more spring in its step by compiling it to ANSI C.

That's right, the open-source Awka project takes plain old Awk code and transforms it into a nitroglycerin-breathing, high-performance rocket car written in C. Nested loops, arrays, and user functions benefit the most from the conversion. The final product will typically see performance gains of around 50%, but depending on the code, you could see 300-400% speed boosts.

So if you find that your Awk text crunching just isn't quite up to par, maybe it's time to consider grinding that puppy through a profiler. And if that still isn't enough, give it the Total Language Makeover with a conversion to C. And if you have a problem that's still taking millennia to compute, well, maybe you should contemplate asking a simpler question. :)

MESO

In their paper, "MESO: Supporting Online Decision Making in Autonomic Computing Systems", Kasten and McKinley showcase their novel approach to pattern classification. Called MESO (Multi-Element Self-Organising tree), this pattern classifier is designed to support online, incremental learning and decision making in autonomic systems.

Using supervised data MESO uses a novel approach to cluster data. It also unveils a new tree structure to organise the resulting clusters, which the authors call sensitivity spheres.

To create their sensitivity spheres, Kasten and McKinley improved on the long standing leader follower algorithm which creates small clusters of patterns. Basically, a training pattern within a specified distance is assigned to that cluster, otherwise a new cluster is created.

What is the problem with the algorithm: The distance measure which determines the size of the clusters is fixed throughout the clustering process.

In their paper the authors proposed the use of a growth function to remedy this problem.


distance between the new pattern and the nearest sensitivity sphere

scales the result relative to the difference between the current and

Note: the denominator serves to limit the growth rate based on how far the current is from

Once the data is assigned to these clusters or sensitivity spheres, it is then organised into a novel tree structure. Kasten boasts of a tree structure which rather than focussing on putting individual patterns into large clusters close to the root of the tree, he instead places the focus on his sensitivity spheres. He then builds a MESO tree starting at the root node which is home to all the sensitivity spheres. He further explains:

The root node is then split into subsets of similar spheres which produces child nodes. Each child node is futher split into subsets until each child contains only one sphere.

Results

Using the eight datasets in the table below MESO results shows it superiority in terms of speed and accuracy against other classifiers.

Clojure: Lisp's Next Evolution

Clojure is a new, dynamic programming language that is built upon the rock-solid foundation of the Java Virtual Machine, the industry-standard platform that is the foundation for Java, one of the world's most popular and powerful multi-platform languages. But, why write in Clojure if you want to target the JVM instead of Java? Wouldn't it make more sense to write your project in the language for which the virtual machine was designed?

Enter functional programming at its finest; Clojure doesn't just target the JVM. No, it's much more than that -- it's an implementation of Lisp. It's not your standard Common Lisp, however; it's a highly specialized form of the language. It's designed with everything modern functional programmers have in mind: concurrency, immutability, and perhaps most importantly, portability. That's right: all your current Java classes are compatible with Clojure.

Clojure doesn't stop there. The core data structures are immutable and extensible. Code-as-data has been extended to maps and vectors. Practically everything is abstract. Multimethods foster polymorphic programming. It really is an amazing thing.

To see what I mean, you should really have a look for yourself over at Clojure's website. The MIL already has a project that is built upon Clojure, CLIFF, which uses an embedded version of the language to generate forensics models dynamically.

As a functional programmer, writing in Clojure has been a dream come true. Do yourself a favor and hack something up today. :D

Zachary Murray

Zachary Murray is an undergraduate research assistant with the Modeling Intelligence Lab at WVU. He is currently studying Computer Science with a minor in Mathematics and expects to graduate in May 2010.

Zack assists the graduate students by providing critical programming support and interface design for the MIL's latest and greatest projects.

CLIFF

CLIFF is a plotting tool which offers the visualization of data. This software features four(4) of the current models used in the forensic community, namely the 1995 Evett model, the 1996 Walsh model, the Seheult model and the Grove model. For each model, data can be generated randomly and plotted. Other features of CLIFF include:

• the ability to perform dimensionality reduction by applying the Fastmap algorithm
• the ability to determine if the results gained from a region of space is important and well supported.

Creating the New Generation of Forensic Interpretation Models

In their report, "Strengthening Forensic Science in the United States: A Path Forward" the National Academy of Sciences (NAS) laid out not only the challenges facing the forensic science community but also put forward recommendations for improvements required alleviate the problems, disparities, and lack of mandatory standards currently facing the community.

Highlighted in this report is the concern that faulty forensic science can contribute to the wrongful convictions of innocent people. One the other side of the coin, someone who is guilty of a crime can be wrongfully acquitted.

Take for instance a hypothetical case of a suspect being connected to a crime scene by trace evidence such as glass. It would be very easy to challenge the forensic analyses by simply requesting that the analysis be done by at least five(5) different forensic labs. One can almost be 100% certain that they would have no choice but to throw out the evidence because of the inconsistency of the respective results.

It is for this reason we have taken up the NAS's challenge to develop a standard forensic interpretation methods to convincingly "demonstrate a connection between evidence and a specific individual or source". It is our hope that this project will not only supply the analyst with an interpretation of the data, but also a measure of what minimal changes in the data can result in a different interpretation.

For this project we studied current methods of forensic interpretation of glass evidence. In this subfield of forensics we have so far identified at least three separate branches of research leading to three different 'best' models: the 1995 Evett model, the 1996 Walsh model, and the 2002 Koons model. To date our research has shown that the former models are 'broken'. There are two root causes for the broken mathematical models:

1. 'Brittle' interpretations where small input changes can lead to large output changes.
2. Inappropriate assumptions about the distribution of data.

To deal with these two issues, our project proposes the use of (a) clustering algorithms (meso and ant), and (b) treatment learning. The clustering algorithms will allow us to reason about crime scene data without the knowledge of standard statistical distributions, while treatment learning offers the analyst a measure of how strongly an interpretation should be believed.

Our project will also boast of a plotting tool (CLIFF) which offers the visualization of data. The software features four(4) of the current models used in the forensic community, namely the 1995 Evett model, the 1996 Walsh model, the Seheult model and the Grove model. For each model, data can be generated randomly and plotted. Other features of CLIFF include:

• the ability to perform dimensionality reduction by applying the Fastmap algorithm
• and the ability to determine if the results gained from a particular region of space is important and well supported.

In the end, it must be made clear that our purpose is not to determine innocence or guilt, or give a 100% guarantee of a match/non-match. Instead our goal is to aid in the decision making process of forensic interpretation. We want to provide the analyst with a standard dependable tool/model which reports to them an interpretation of the crime scene data as well as the treatment learner's analysis of what minimal 'treatment' could change the interpretation. What happens after this is in the hands of the analyst.

Ultimately we want to be able to rely on the results presented in a court of law, results based on correct models accepted and used by the entire forensic community. So, if a suspect demands that test be done by five(5) different forensic labs, there should be no dramatic differences in the results.

New version of Cliff

Fayola and Zach coded an amazing new version of the forensics tool. Which Timm used to write an NIJ proposal. So cross fingers!