Optimal matching


Optimal matching is a sequence analysis method used in social science, to assess the dissimilarity of ordered arrays of tokens that usually represent a time-ordered sequence of socio-economic states two individuals have experienced. Once such distances have been calculated for a set of observations classical tools can be used. The method was tailored to social sciences from a technique originally introduced to study molecular biology sequences. Optimal matching uses the Needleman-Wunsch algorithm.

Algorithm

Let be a sequence of states belonging to a finite set of possible states. Let us denote the sequence space, i.e. the set of all possible sequences of states.
Optimal matching algorithms work by defining simple operator algebras that manipulate sequences, i.e. a set of operators. In the most simple approach, a set composed of only three basic operations to transform sequences is used:
Imagine now that a cost is associated
to each operator. Given two sequences and,
the idea is to measure the cost of obtaining from
using operators from the algebra. Let be a sequence of operators such that the application of all the operators of this sequence to the first sequence gives the second sequence :
where denotes the compound operator.
To this set we associate the cost, that
represents the total cost of the transformation. One should consider at this point that there might exist different such sequences that transform into ; a reasonable choice is to select the cheapest of such sequences. We thus
call distance

that is, the cost of the least expensive set of transformations that turn into. Notice that is by definition nonnegative since it is the sum of positive costs, and trivially if and only if, that is there is no cost. The distance function is symmetric if insertion and deletion costs are equal ; the term indel cost usually refers to the common cost of insertion and deletion.
Considering a set composed of only the three basic operations described above, this proximity measure satisfies the triangular inequality. Transitivity however, depends on the definition of the set of elementary operations.

Criticism

Although optimal matching techniques are widely used in sociology and demography, such techniques also have their flaws. As was pointed out by several authors, the main problem in the application of optimal matching is to appropriately define the costs.

Optimal matching in causal modelling

Optimal matching is also a term used in statistical modelling of causal effects. In this context it refers to matching "cases" with "controls", and is completely separate from the sequence-analytic sense.

Software