30:T4f4,para_4 = md`## Comparing columns We need a mathematical way of evaluating these pairwise comparisons - a function that takes the comparisons as an input, and outputs match probabilities. The FS model solves this problem by comparing the records column by column, and assigning each comparison to two or more 'similarity levels'. A simple example of a two-level comparison rule for a column may be: - If the values in the column exactly match, assign the comparison to similarity level 1 - Otherwise assign the comparison to similarity level 0 In the following table, we apply this simple rule to every column. The comparisons are denoted with the prefix \`𝛾_\` because the mathematical symbol gamma is often used in the literate to represent comparisons. ${df_gammas_1.view()}
Now that we have a numeric representation of the comparisons, the model makes no further use of the raw data, instead using only the values in the 𝛾 columns: ${df_gammas_only_1.view()}
For each row in this table, the set of gamma values is known as the 'comparison vector'. For example, the comparison vector for the first row in the table is: ${texd`${get_comparison_vector_symbols_and_numbers( df_gammas_1.slice(1 - 1, 1).objects()[0], settings )}`} `31:T5e4,para_5 = md`We now need a way of recombining these individual column comparisons into an overall match probability. We will want this approach to account for the differing importance of columns. For example, a match on gender is less informative than a match on date of birth. The FS model approaches this problem by estimating match weights for each individual column and combining these match weights. By assuming mutual independence of the features, each column can be accounted for separately, dramatically simplifying the maths. In particular, this assumption makes the model equivalent to a [Naïve Bayes](https://en.wikipedia.org/wiki/Naive_Bayes_classifier) classifier. This allows the match probability to be expressed as a repeated multiplication of conditional probabilities. Further mathmetical details can be found [here](https://en.wikipedia.org/wiki/Naive_Bayes_classifier#Probabilistic_model). In our case, 'mutual independence of features' means that linkage variables must be independent given the match status. This would be violated if amongst matching records, a typo on first name was correlated with a typo on surname. Another violation often occurs with addresses if they are separated into multiple columns: Amongst matching records, a match on postcode typically implies a match on town. To further understand how we account for each comparison column in the computation of match probability, we need to introduce the concept of \`m\` and \`u\` probabilities. `32:Ta8b,para_6 = md`### m and u probabilities How much should we increase our estimate of match probability if we observe a match on first name? How about a match on gender? And what about if we observe a mismatch on these fields? We are interested in evaluating statements like: ${texd`\operatorname{Pr}(\text{records match}|\text{first name matches})`} This can be quantified using the m and u probabilities for each column, combined with Bayes Theorem (see annex for a refresher). Consider the first name column. We have defined two similarity levels: level 1 if the first name exactly matches, and level 0 otherwise. #### m probabilities The m probabilities for the first name column are: ${texd`m_\text{first name,level\_0} = \operatorname{Pr}(\text{first name does not match}|\text{record match})`} ${texd`m_\text{first name, level\_1} = \operatorname{Pr}(\text{first name matches}|\text{records match})`} That is, amongst record comparisons which are true matches, what proportion have a match on first name, and what proportion mismatch on first name? This is a measure of how often mispellings, nicknames or aliases occur in the first name field. #### u probabilities The u probabilities for the first name column are: ${texd`u_\text{first name, level\_0} = \operatorname{Pr}(\text{first name does not match}|\text{records do not match})`} ${texd`u_\text{first name, level\_1} = \operatorname{Pr}(\text{first name matches}|\text{records do not match})`} That is, amongst record comparisons which are true non-matches, what proportion have a match on first name, and what proportion mismatch on first name? This is a measure of how likely 'collisions' are likely to occur. For instance, it would be common for two different people to have the same gender, but less likely for two different people to have the same date of birth. #### The overall proportion of matches Let us also define: ${texd`\operatorname{Pr}(\text{records match}) = \lambda`} This is our prior - our estimate for the probability that a randomly-chosen pairwise record comparison is a match. ### Bayes Theorem We can now use Bayes Theorem to write: ${texd` \text{posterior} = \operatorname{Pr}(\text{records match}|\text{first name matches}) \newline [10pt] = \frac{\operatorname{Pr}(\text{first name matches}|\text{records match})\operatorname{Pr}(\text{records match})}{\operatorname{Pr}{(\text{first name matches})}}`} which, in our notation is: ${texd` \text{posterior} = \operatorname{Pr}(\text{records match}|\text{first name matches}) \newline [10pt] = \frac{m_\text{first name, level\_1}\lambda}{m_\text{first name, level\_1}\lambda + u_\text{first name, level\_1}(1-\lambda)}`} `33:T571,para_7 = md`We can generalise this formula by using ${tex`\gamma`} to indicate the value of the comparison, the index ${tex`k`} to designate the comparison column, and ${tex`\ell`} to designate the observed comparison level, we can write: ${texd` \text{posterior} = \operatorname{Pr}(\text{records match}|\gamma_{k}) \newline [10pt] = \frac{\lambda m_{k\ell}}{\lambda m_{k\ell}+ u_{k\ell}(1-\lambda)}`} Finally, by assuming conditional independence among linkage variables given the match status, we can account for more than one comparison column. For instance, in the case of two comparison columns ${texd` \operatorname{Pr}(\text{records match}|\gamma_{1},\gamma_{2}) \newline [10pt] = \frac{\operatorname{Pr}(\gamma_{1}|\text{records match})\operatorname{Pr}(\gamma_{2}|\text{records match})\operatorname{Pr}(\text{records match})}{\operatorname{Pr}{(\gamma_{1},\gamma_{2})}}`} Leading to the following formula that takes into account all column comparisons: #### Equation 1: ${texd` \operatorname{Pr}(\text{records match}|\gamma_{1},\gamma_{2},\ldots,\gamma_{K}) \newline [10pt] = \frac{\lambda m_{1\ell}m_{2\ell}\ldots m_{K\ell}}{\lambda m_{1\ell}m_{2\ell}\ldots m_{K\ell}+ (1-\lambda)u_{1\ell}u_{1\ell} \ldots u_{K\ell}} `} This equation provides the output of the Fellegi Sunter model - an estimate of the probability that two records match given the information contained `34:T5ca,para_19 = md`## Annex: Bayes Theorem Recall that Bayes Theorem is given by: ${texd` \operatorname{Pr}(a|b) = {\frac{\operatorname{Pr}(b|a)\operatorname{Pr}(a)}{\operatorname{Pr}{(b)}}}`} or , in words: ${texd` \text{posterior} = \frac{\text{likelihood} \times \text{prior}}{\text{evidence}}`} In the context of record linkage, we can describe these parts as: **Prior**: The overall proportion of comparisons which are matches ${tex`\operatorname{Pr}(\text{match})`}. **Evidence**: We have observed that e.g. first name matches, ${tex`\operatorname{Pr}(\text{first name matches})`}. **Likelihood**: The probability that first name matches amongst matches, given by ${tex`\operatorname{Pr}(\text{first name matches}|\text{records match})`}. So Bayes' formuls is: ${texd` \operatorname{Pr}(\text{match}|\text{first name matches}) = \frac{\operatorname{Pr}(\text{first name matches}|\text{match})\operatorname{Pr}(\text{match})}{\operatorname{Pr}{(\text{first name matches})}}`} Which can also be written: ${texd` \frac{\operatorname{Pr}(\text{first name matches}|\text{match})\operatorname{Pr}(\text{match})}{\operatorname{Pr}(\text{first name matches}|\text{match})\operatorname{Pr}(\text{match}) + \operatorname{Pr}(\text{first name matches}|\text{non match})\operatorname{Pr}(\text{non match})}`} giving us: ${texd` \operatorname{Pr}(\text{match}|\text{first name matches}) = \frac{m_1\lambda}{m_1\lambda + u_1(1-\lambda)}`} Which is the same as Equation 1. `35:[] 2e:{"title":"The mathematics of the Fellegi Sunter model","cells":[{"id":0,"value":"title = md`# The mathematics of the Fellegi Sunter model`","pinned":false,"hidden":false,"mode":"ojs"},{"id":837,"value":"md`*A final version of this notebook can be viewed on my blog [here](https://www.robinlinacre.com/maths_of_fellegi_sunter/).*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"para_1 = md`In this article, we present an implementation of [Fellegi and Sunter's model of probabilistic record linkage](https://courses.cs.washington.edu/courses/cse590q/04au/papers/Felligi69.pdf) (1969). \n\nWe build up a simple Fellegi Sunter (FS) model piece by piece, demonstrating how it can be used to compute match probabilities. In this article, we assume parameters of the model are known. \n\nA more technical treatment is given in [AP\tEnamorado, T., Fifield, B., & Imai, K. (2019)](https://imai.fas.harvard.edu/research/files/linkage.pdf), which contains a generalised form of the model.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":75,"value":"para_2 = md`## Objective of the Model\n\nThe input to the FS model is a dataset of pairwise record comparisons.\n\nThe aim of the model is to estimate a 'match probability' for each pairwsie comparison, which quantifies the likelihood the two records represent the same entity.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":59,"value":"para_3 = md`## Set up\n\nThe FS model can be used to link and/or deduplicate one or more datasests. In what follows, let's assume we have two datasets we wish to link:\n\n✨You can edit the records in the tables, and all of the subsequent calculations will update accordingly.✨\n\n### Dataset 1\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":771,"value":"table_l1 = table_l","pinned":false,"hidden":false,"mode":"ojs"},{"id":775,"value":"ds2_head = md`### Dataset 2`","pinned":false,"hidden":false,"mode":"ojs"},{"id":777,"value":"table_r1 = table_r","pinned":false,"hidden":false,"mode":"ojs"},{"id":769,"value":"rec_comparisons = md`\n\nTo be compatible with the FS model, the input data must be converted into pairwise comparisons as follows:\n\n### Record comparisons\n\n${df_comparisons_1.view()}\n
\nThis table compares every row in dataset 1 to every row in dataset 2. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":137,"value":"subhead_1 = md`## Scoring comparisons`","pinned":false,"hidden":false,"mode":"ojs"},{"id":144,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":181,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":369,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":453,"value":"para_8 = md`In subsequent articles, we use the concepts of m and u probabilities to discuss the intuition behind match weights, and present graphical ways of interpreting the values. \n\nWe finish this article with a worked example of the probability calculation.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":432,"value":"subhead_2 = md`## Example`","pinned":false,"hidden":false,"mode":"ojs"},{"id":435,"value":"para_10 = md`\nIn order to present an example calculation we need to choose values for the parameters of the model - the m and u values.\n\nWe can represent the m and u values for a comparison column succinctly as follows:\n\n\\`\\`\\`\n{\n \"col_name\": \"fname\",\n \"m_probabilities\": [0.2,0.8],\n \"u_probabilities\": [0.9,0.1],\n}\n\\`\\`\\`\n\nThe position (index) of the arrays corresponds to the comparison level. \n\nFor example, \\`\"m_probabilities\": [0.2,0.8]\\` means that amongst matching records, 20% have a disagreement on the first name (e.g. \"John\" vs. \"Jonathan\"), and 80% match (e.g. \"David\" vs. \"David\")\n\nUsing this notation, parameters we will choose for our model are as follows. ✨You may edit these values to see how they affect the calculation.✨\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":518,"value":"viewof splink_settings = inputs.textarea({\n value: default_splink_settings,\n rows: 26,\n spellcheck: false\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":505,"value":"para_11 = md`We will now present a worked example of the calculation of match probability for the following pairwise record comparison. \n\n\n✨You may change the record comparison using the control below✨\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":544,"value":"viewof row_index = inputs.range([1, df_gammas_1.numRows()], {\n value: 1,\n label: \"Choose record comparison\",\n step: 1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":553,"value":"this_row = md`${df_comparisons_1.slice(row_index - 1, row_index).toMarkdown()}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":446,"value":"para_12 = md`The comparison vector is given by:\n\n${texd`${get_comparison_vector_symbols_and_numbers(\n df_gammas_1.slice(row_index - 1, row_index).objects()[0],\n settings\n)}`}\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":622,"value":"para_13 = md`The formula for match probability is:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":578,"value":"para_14 = texd`${get_m_u_formula_symbols(\n df_gammas_1.slice(row_index - 1, row_index).objects()[0],\n settings\n)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":625,"value":"para_15 = md`And substituting in numbers using our specified parameters we get: `","pinned":false,"hidden":false,"mode":"ojs"},{"id":619,"value":"para_16 = texd`${get_m_u_formula_numbers(\n df_gammas_1.slice(row_index - 1, row_index).objects()[0],\n settings\n)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":654,"value":"para_17 = md`i.e. the ${tex`\\text{estimated match probability} = \n\n${get_match_probability_components(\n df_gammas_1.slice(row_index - 1, row_index).objects()[0],\n settings\n)[\"match_probability\"].toPrecision(4)}\n\n`}\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":639,"value":"para_18 = md`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":254,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":189,"value":"md`## Calculations and code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":28,"value":"import {\n example_2_comparison,\n intro_simple_waterfall,\n table_l,\n table_r,\n df_1_l,\n df_1_r,\n df_comparisons_1,\n df_gammas_1,\n df_gammas_only_1\n} from \"ea6530af059f37be@231\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":575,"value":"import {\n get_m_u_formula_symbols,\n get_m_u_formula_numbers,\n get_comparison_vector_symbols_and_numbers,\n get_match_probability_components\n} from \"d25176b0fe784ad0\";","pinned":false,"hidden":false,"mode":"ojs"},{"id":344,"value":"texd = tex.options({\n displayMode: true,\n fleqn: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":521,"value":"default_splink_settings = {\n return `{\n \"proportion_of_matches\": 0.01,\n \"comparison_columns\": [\n {\n \"col_name\": \"fname\",\n \"u_probabilities\": [0.8, 0.2],\n \"m_probabilities\": [0.2, 0.8]\n },\n {\n \"col_name\": \"sname\",\n \"u_probabilities\": [0.9, 0.1],\n \"m_probabilities\": [0.2, 0.8]\n },\n {\n \"col_name\": \"dob\",\n \"u_probabilities\": [0.99, 0.01],\n \"m_probabilities\": [0.2, 0.8]\n },\n {\n \"col_name\": \"town\",\n \"u_probabilities\": [0.7, 0.3],\n \"m_probabilities\": [0.3, 0.7]\n }\n ]\n \n }`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":581,"value":"settings = JSON.parse(splink_settings)","pinned":false,"hidden":false,"mode":"ojs"},{"id":356,"value":"css_styles = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":756,"value":"inputs = require(\"@observablehq/inputs\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}