Cost-Based Metrics

Cost-based metrics fulfill the above general definition of a metric, and are constructed with the following ingredients:

a list of allowed elementary steps (allowed transformations of spike trains)
an assignment of non-negative numerical costs to each elementary step

For any such set of choices, one can define a metric D(S_a,S_b) as the least total cost of any allowed transformation from to S_b via any sequence of spike trains S_a, S₁, S₂,..., S_n, S_b.
top introduction cost-based metrics D^count D^spike[q] D^interval[q] generalizations and related dynamic programming algorithm and links to code applications and references

Trivial example: the spike count distance D^count

This is a cost-based metric in which the elementary steps and associated costs are:

insert a spike: cost = 1
delete a spike: cost = 1
shift a spike in time: cost = 0

The distance between two spike trains is the difference in the number of spikes, independent of when they occur. That is, this metric formalizes the notion that the only significant aspect of a spike train is the number of spikes it contains.
top introduction cost-based metrics D^count D^spike[q] D^interval[q] generalizations and related dynamic programming algorithm and links to code applications and references

The spike time distance D^spike[q]

This is a family of cost-based metrics, parametrized by a "cost per unit time" q (units of 1/sec). The elementary steps and associated costs are:

insert a spike: cost = 1
delete a spike: cost = 1
shift a spike by an amount of time t: cost = qt

See diagram.

If q is very small, this becomes the spike count distance. If q is very large, all spike trains are far apart from each other, unless they are nearly identical. For intermediate values of q, the distance between two spike trains is small if they have a similar number of spikes, occurring at similar times.

The motivation for this construction is that neurons which act like coincidence detectors should care about this metric. The value of q corresponds to the temporal precision 1/q of the coincidence detector.

This distance can be calculated efficiently by a dynamic programming algorithm.

An example of a sequence of elementary steps for D^spike which transforms the spike train S_a into S_b.

top introduction cost-based metrics D^count D^spike[q] D^interval[q] generalizations and related dynamic programming algorithm and links to code applications and references

The spike interval distance D^interval[q]

This is a family of cost-based metrics, parametrized by a "cost per unit time" q (units of 1/sec). The elementary steps and associated costs are:

insert a spike (along with an interspike interval): cost = 1
delete a spike (along with an interspike interval): cost = 1
change an interspike interval by an amount of time t: cost = qt

Neurons which show post-tetanic potentiation and similar mechanisms might care about this distance. The optimal value of q corresponds to the temporal precision 1/q of the discrimination between bursts of different carrier frequencies (or interspike intervals).
top introduction cost-based metrics D^count D^spike[q] D^interval[q] generalizations and related dynamic programming algorithm and links to code applications and references

Some generalizations, extensions, and related metrics

Our algorithm can be applied to these generalizations and extensions of the metrics:

The spike trains reflect activity of multiple identified neurons. That is, each spike is labelled with its neuron of origin. A new kind of elementary step is introduced, in which the label for the neuron of origin is changed. This step is assigned a cost k. k=0 corresponds to ignoring the neuron of origin; higher values of k (up to 2) correspond to increasing sensitivity to the neuron of origin. See an application to real data. See a clever algorithm for calculating this metric. See a generalization of this algorithm, parallel in the cost parameters.
As above, but the cost per unit time of moving a spike in one train to match up with a spike in the second train depends on whether the two spikes have the same neuron of origin, or not. Note that the costs per unit time, q (same neuron of origin) and q' (different neuron of origin) are constrained by the triangle inequality. This metric is best thought of as an assignment of a cost to a scheme for "linking" or "aligning" the two spike trains, rather than as a sum of costs of individual transformations.
The events to be matched are bursts of spikes, rather than individual spikes. Bursts are described by several parameters, each of which influence the cost of matching two bursts. Reference: Keat, Reinagel, Reid, and Meister (2001) Predicting every spike: a model for the responses of visual neurons. Neuron 30, 803-817. Find it online.
Time is considered cyclic. This is useful for periodic stimuli.
An application to real data: simple gratings.
An application to real data: compound gratings.

Our dynamic programming algorithm cannot readily be applied to the following extensions, but they are nevertheless interesting. See unsolved problems page:

The cost assigned to a timeshift t is a concave-down function of t, such as 1-exp(-q|t|). Here the paths of individual spikes in a minimal-cost transformation can cross. Non-crossing of these paths is an essential feature for the dynamic programming algorithm to work.

A metric D^motif can be defined, by allowing shifts of a subset of 2 or more (possibly non-contiguous) spikes at the same cost as the shift of a single spike.
The metrics D^spike and D^interval (and even D^motif) can be combined by including two or three kinds of elementary steps: spikes, intervals, and motifs. Different costs/unit time may be associated with each kind of step.

Spike time metrics (one kind of cost-based metrics) are a continuous version of edit-length distances, also known as Levenshtein distances. Spike time metrics reduce to the "earth mover distance" (used in image processing and classification) when the number of spikes is identical, and the cost to move a spike is small.

Euclidean distances that are closely related to the spike time metric but are much easier to compute have been introduced by van Rossum (2001). Houghton and Sen (2007) have generalized the von Rossum distance to the multineuronal context. See van Rossum, M.C.W. (2001) A novel spike distance. Neural Computation 13, 751-763 (download) and Houghton, C., and Sen, K. (2007) A new multi-neuron spike-train metric. Neural Computation, in press. (download).

top introduction cost-based metrics D^count D^spike[q] D^interval[q] generalizations and related dynamic programming algorithm and links to code applications and references

Dynamic programming algorithm for D^spike and D^interval

This is an adaptation of Sellers' highly efficient dynamic programming algorithm [Sellers, P. H. (1974) On the theory and computation of evolutionary distances. SIAM J. Appl. Math. 26, 787-793] for comparing genetic sequences, which is identical to the Needleman-Wunsch algorithm [Needleman, S., and Wunsch, C. (1970) A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48, 443-453].

Hint: it is doubly recursive, and reduces the calculation of the distance between spike trains of length N_a and N_b to consideration of spike trains of lengths N_a-1 and N_b-1. Think about the constraints on the "world lines" of each spike in the above diagram for D^spike.

Fortran, matlab, and c code for the metrics

Spike Train Analysis Toolkit, a user-friendly implementation from the Laboratory of Neuroinformatics that includes algorithms for information estimation via the direct method, the binless method, and the metric space method.

L. Allison's code for edit-length distances

top introduction cost-based metrics D^count D^spike[q] D^interval[q] generalizations and related applications and references

Selected Applications and References

Review

Victor, J.D. (2005) Spike train metrics. Current Opinion in Neurobiology 15, 585–592.
Abstract and download

Theory and algorithms

Kreuz, T., Haas, J.S., Morelli, A., Abarbanel, H.D.I., and Politi, A. Measuring spike train synchrony. J Neurosci Methods 165, 151 (2007).
Download and code
This describes another interval-based metric for comparing spike trains, and compares six different metrics, including D^spike

Victor, J.D., Goldberg, D., and Gardner, D. (2007) Dynamic programming algorithms for comparing multineuronal spike trains via cost-based metrics and alignments. J. Neurosci. Meth. 161, 351-360.
Abstract and download
This describes dynamic programming algorithms for computing generalizations of D^spike, parallel in one or more cost parameters

Aronov, D. (2005) A metric-space approach to the study of informatoin coding by neuronal populations. Senior Thesis, Columbia University.
Download

Aronov, D., and Victor, J. (2004) Non-Euclidean properties of spike train metric spaces. Phys. Rev. E69, 61905.
Abstract, download, and related notes

Aronov, D. (2003) Fast algorithm for the metric-space analysis of simultaneous responses of multiple single neurons. J. Neuroscience Methods 124, 175-179.
Abstract, download, and code

Visual neurophysiology

Victor, J.D., and Purpura, K. (1997) Metric-space analysis of spike trains: theory, algorithms, and application. Network 8, 127-164. Abstract and code

More references from our lab

Keat, Reinagel, Reid, and Meister (2001) Predicting every spike: a model for the responses of visual neurons. Neuron 30, 803-817. pdf from Neuron
This describes a generalization to sequences of burst events. The authors also describe a novel approach to pruning the dynamic programming algorithm.

Hitt, Dodge, and Barlow (2003) Information content in responses of Limulus optic nerve fibers. Arvo Abstract 3253. Link to ARVO abstracts

Auditory neurophysiology

Machens, C.K., Prinz, P., Stemmler, M.B., Ronacher, B., and Herz, A.V.M. (2001) Discrimination of behaviorally relevant signals by auditory receptor neurons. Neurocomputing 38, 263-268. pdf from Machens' site pdf from Herz's site

Machens, C.K., Schutze, H., Franz, A., Kolesnikova, O., Stemmler, M.B., Ronacher, B., and Herz, A.V.M. (2001) Single auditory neurons rapidly discriminate conspecific communication signals. Nature Neurosci. 6, 341-342. pdf from Nature Neuroscience pdf from Ronacher's site

Wohlgemuth, S., and Ronacher, B. (2007) Auditory discrimination of amplitude modulations based on metric distances of spike trains. J. Neurophysiol. 97, 3082-3092. pdf from J. Neurophysiol.

Olfactory neurophysiology

Two very nice tutorials, courtesy of Alex Bäcker, Caltech:
This one is based on MacLeod et al., Nature, 1998 (see below)
This one has more detail concerning the dynamic programming algorithm, and requires the Vector Graphic Rendering (VML) plugin and IE5.

Bäcker, A., MacLeod, K., Wehr, M., and Laurent, G. (1998) Disruption of neuronal synchronization impairs reliable reconstruction of odors by beta lobe cells but not by projection neurons of the antennal lobe of the locust. Soc. Neurosci. Abstr. 24, 911.

MacLeod, K., Bäcker A., & Laurent, G. (1998) Who reads temporal information contained across synchronized and oscillatory spike trains? Nature 395, 693-698.

Gustatory neurophysiology

Di Lorenzo, P.M, and Victor, J.D. (2003) Taste response variability and temporal coding in the nucleus of the solitary tract of the rat. J. Neurophysiol. 90, 1418-1431.
Abstract and download

Electric sense

Kreiman, G., Gabbiani, F., Metzner, W., & Koch, C. (1998) Robustness of amplitude modulation encoding by P-receptor afferent spike trains of weakly electric fish. Soc. Neurosci. Abstr. 196, 911.

Kreiman, G., Krahe, R., Metzner, W., Koch, C., & Gabbiani, F. (2000) Robustness and variability of neuronal coding by amplitude-sensitive afferents in the weakly electric fish Eigenmannia. J. Neurophysiol. 84, 189-204. Abstract

Birdsong

Huetz, C., Lebas, N., Del Negro, C., Lehongre, K., Tarroux, P, and Edeline, J.M. (2004) Do HVc neurons use a temporal code to represent the bird own song (BOS)? Soc. Neurosci. Abstr. 333.2 101.

Huetz, C., Del Negro, C., Lebas, N., Tarroux, P. & Edeline, J. M. (2006) Contribution of spike timing to the information transmitted by HVC neurons. Eur J Neurosci 24, 1091-108. PubMed entry

Le Wang, Narayan, Grana, Shamir, and Sen (2007) Cortical discrimination of complex natural stimuli: Can single neurons match behavior? J. Neurosci. 27,582-589 J. Neurosci. online
The authors use Dspike, Dinterval, and the van Rossum metric.

Computational studies

Tiesinga, P.H.E. (2004) Chaos-induced modulation of reliability boosts output firing rate in downstream cortical areas. Phys. Rev. E69, 031912. Download from Paul Tiesinga's website

Cost-based metrics ("edit length metrics") in EEG classfication

Wu, L., and Gotman, J. (1998) Segmentation and classification of EEG during epileptic seizures. Electroenceph. Clin. Neurophysiol. 106, 344-356.

Geophysics: earthquake patterns

Schoenberg, F.P., and Tranbarger, K.E. (2004) Description of earthquake aftershock sequences using prototype point patterns. Download from Katherine Tranbarger's website

Comments and questions
top introduction cost-based metrics D^count D^spike[q] D^interval[q] generalizations and related dynamic programming algorithm and links to code