Digital Commons Network^™

Interpreting Individual Classifications Of Hierarchical Networks, Will Landecker, Michael David Thomure, Luis M.A. Bettencourt, Melanie Mitchell, Garrett T. Kenyon, Steven P. Brumby

Computer Science Faculty Publications and Presentations

Hierarchical networks are known to achieve high classification accuracy on difficult machine-learning tasks. For many applications, a clear explanation of why the data was classified a certain way is just as important as the classification itself. However, the complexity of hierarchical networks makes them ill-suited for existing explanation methods. We propose a new method, contribution propagation, that gives per-instance explanations of a trained network's classifications. We give theoretical foundations for the proposed method, and evaluate its correctness empirically. Finally, we use the resulting explanations to reveal unexpected behavior of networks that achieve high accuracy on visual object-recognition tasks using well-known …

Resizable, Scalable, Concurrent Hash Tables, Josh Triplett, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We present algorithms for shrinking and expanding a hash table while allowing concurrent, wait-free, linearly scalable lookups. These resize algorithms allow the hash table to maintain constant-time performance as the number of entries grows, and reclaim memory as the number of entries decreases, without delaying or disrupting readers.

We implemented our algorithms in the Linux kernel, to test their performance and scalability. Benchmarks show lookup scalability improved 125x over readerwriter locking, and 56% over the current state-of-the-art for Linux, with no performance degradation for lookups during a resize.

To achieve this performance, this hash table implementation uses a new concurrent …

Segmentation Of Thermographic Images Of Hands Using A Genetic Algorithm, Payel Ghosh, Judith Gold, Melanie Mitchell

Computer Science Faculty Publications and Presentations

This paper presents a new technique for segmenting thermographic images using a genetic algorithm (GA). The individuals of the GA also known as chromosomes consist of a sequence of parameters of a level set function. Each chromosome represents a unique segmenting contour. An initial population of segmenting contours is generated based on the learned variation of the level set parameters from training images. Each segmenting contour (an individual) is evaluated for its fitness based on the texture of the region it encloses. The fittest individuals are allowed to propagate to future generations of the GA run using selection, crossover and …

Solving Continuous Linear Least-Squares Problems By Iterated Projection, Ralf Juengling

Computer Science Faculty Publications and Presentations

I present a new divide-and-conquer algorithm for solving continuous linear least-squares problems. The method is applicable when the column space of the linear system relating data to model parameters is “translation invariant”. The central operation is a matrix- vector product, which makes the method very easy to implement. Secondly, the structure of the computation suggests a straightforward parallel implementation.

A complexity analysis for sequential implementation shows that the method has the same asymptotic complexity as well-known algorithms for discrete linear least-squares. For illustration we work out the details for the problem of fitting quadratic bivariate polyno- mials to a piecewise …

Finding Irc-Like Meshes Sans Layer 7 Payloads, Akshay Dua, Jim Binkley, Suresh Singh

Computer Science Faculty Publications and Presentations

We present an algorithm for detecting IRC-like chat networks that does not rely on Layer 7 payload information. The goal is to extract only those meshes from conventional flows where long-term periodic data is being exchanged between an external server and multiple internal clients. Flow data is passed through a series of filters that reduce the memory requirements needed for final candidate mesh sorting. Final outputs consist of two sorted lists including the fanout list, sorted by the number of client hosts in the mesh, and a secondary list called the evil sort. The latter consists of meshes with any …

Prostate Segmentation On Pelvic Ct Images Using A Genetic Algorithm, Payel Ghosh, Melanie Mitchell

Computer Science Faculty Publications and Presentations

A genetic algorithm (GA) for automating the segmentation of the prostate on pelvic computed tomography (CT) images is presented here. The images consist of slices from three-dimensional CT scans. Segmentation is typically performed manually on these images for treatment planning by an expert physician, who uses the “learned” knowledge of organ shapes, textures and locations to draw a contour around the prostate. Using a GA brings the flexibility to incorporate new “learned” information into the segmentation process without modifying the fitness function that is used to train the GA. Currently the GA uses prior knowledge in the form of texture …

Traffic Analysis Of Udp-Based Flows In Ourmon, Jim Binkley, Divya Parekh

Computer Science Faculty Publications and Presentations

We present a custom UDP flow tuple with an IP address key and a set of simple related statistical attributes. Attributes are used to calculate a per host metric called the UDP work weight which roughly measures the amount of network noise caused by a host. The work weight is used to produce a near real-time sorted top N report for UDP host tuples. We also present a derived attribute based on an algorithm called the UDP guesstimator. The UDP guesstimator roughly classifies port report hosts into various traffic categories including security threats (DOS/scanning) or P2P hosts based on high …

Rcu Semantics: A First Attempt, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

There is not yet a formal statement of RCU (read-copy update) semantics. While this lack has thus far not been an impediment to adoption and use of RCU, it is quite possible that formal semantics would point the way towards tools that automatically validate uses of RCU or that permit RCU algorithms to be automatically generated by a parallel compiler. This paper is a first attempt to supply a formal definition of RCU. Or at least a semi-formal definition: although RCU does not yet wear a tux (though it does run in Linux), at least it might yet wear some …

Toward A Sound Integration Of Isabelle With A Combined Decision Procedure, Tom Harke

Computer Science Faculty Publications and Presentations

I present work on a project to integrate Isabelle, an extremely versatile interactive proof assistant, with a combined decision procedure, the Cooperating Validity Checker (CVC). Isabelle is sound and flexible, however it is often tedious to use. CVC is fully automatic, but only handles decision problems expressible over a relatively weak set of theories including linear arithmetic, uninterpreted functions, data types, and firstorder quantifier-free logic. My goal is to increase the amount of automation in Isabelle, by making it use CVC as an oracle for such problems, but without compromising Isabelle’s soundness.

In this paper I report on the progress …

Investigation Of Image Feature Extraction By A Genetic Algorithm, Steven P. Brumby, James P. Theiler, Simon J. Perkins, Neal R. Harvey, John J. Szymanski, Jeffrey J. Bloch, Melanie Mitchell

Computer Science Faculty Publications and Presentations

We describe the implementation and performance of a genetic algorithm which generates image feature extraction algorithms for remote sensing applications. We describe our basis set of primitive image operators and present our chromosomal representation of a complete algorithm. Our initial application has been geospatial feature extraction using publicly available multi-spectral aerial-photography data sets. We present the preliminary results of our analysis of the efficiency of the classic genetic operations of crossover and mutation for our application, and discuss our choice of evolutionary control parameters. We exhibit some of our evolved algorithms, and discuss possible avenues for future progress.

Statistical Dynamics Of The Royal Road Genetic Algorithm, Erik Van Nimwegen, James P. Crutchfield, Melanie Mitchell

Computer Science Faculty Publications and Presentations

Metastability is a common phenomenon. Many evolutionary processes, both natural and artificial, alternate between periods of stasis and brief periods of rapid change in their behavior. In this paper an analytical model for the dynamics of a mutation-only genetic algorithm (GA) is introduced that identifies a new and general mechanism causing metastability in evolutionary dynamics. The GA’s population dynamics is described in terms of flows in the space of fitness distributions. The trajectories through fitness distribution space are derived in closed form in the limit of infinite populations. We then show how finite populations induce metastability, even in regions where …

Dynamic Load Distribution In Mist, K. Al-Saqabi, R. M. Prouty, Dylan Mcnamee, Steve Otto, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper presents an algorithm for scheduling parallel applications in large-scale, multiuser, heterogeneous distributed systems. The approach is primarily targeted at systems that harvest idle cycles in general-purpose workstation networks, but is also applicable to clustered computer systems and massively parallel processors. The algorithm handles unequal processor capacities, multiple architecture types and dynamic variations in the number of processes and available processors. Scheduling decisions are driven by the desire to minimize turnaround time while maintaining fairness among competing applications. For efficiency, the virtual processors (VPs) of each application are gang scheduled on some subset of the available physical processors.

Genetic Algorithms And Artificial Life, Melanie Mitchell, Stephanie Forrest

Computer Science Faculty Publications and Presentations

Genetic algorithms are computational models of evolution that play a central role in many artificial-life models. We review the history and current scope of research on genetic algorithms in artificial life, giving illustrative examples in which the genetic algorithm is used to study how learning and evolution interact, and to model ecosystems, immune system, cognitive systems, and social systems. We also outline a number of open questions and future directions for genetic algorithms in artificial-life research

Adaptive Execution Of Data Parallel Computations On Networks Of Heterogeneous Workstations, Robert Prouty, Steve Otto, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Parallel environments consisting of a network of heterogeneous workstations introduce an inherently dynamic environment that differs from multicomputers. Workstations are usually considered “shared” resources while multicomputers provide dedicated processing power. The number of workstations available for use is continually changing; the parallel machine presented by the network is in effect continually reconfiguring itself. Application programs must effectively adapt to the changing number of processing nodes while maintaining computational efficiency. This paper examines methods for adapting to this dynamic environment within the framework of explicit message passing under the data parallel programming model. We present four requirements which we feel a …