Edit distance (Levenshtein) in NLP - Model Metrics & Evaluation

Metrics & Evaluation - Edit distance (Levenshtein)

Which metric matters for Edit Distance (Levenshtein) and WHY

Edit distance measures how many changes (insertions, deletions, or substitutions) are needed to turn one word into another. It helps us know how similar two words or strings are. A smaller edit distance means the words are more alike. This is important in spell checkers, search engines, and language tools to find close matches or fix typos.

Confusion matrix or equivalent visualization

      Example: Comparing "cat" and "cut"

      Operations needed:
      c a t
      | | |
      c u t

      Changes:
      - Substitute 'a' with 'u' (1 change)

      Edit distance = 1

      Visualization (matrix of costs):

        ''  c   u   t
      '' 0   1   2   3
      c  1   0   1   2
      a  2   1   1   2
      t  3   2   2   1

      The bottom-right cell shows the edit distance = 1
    

Precision vs Recall tradeoff with concrete examples

In tasks using edit distance, like spell correction, we balance between:

• Precision: How often the suggested correction is actually right. High precision means fewer wrong fixes.
• Recall: How many of the misspelled words we manage to fix. High recall means catching most errors.

For example, if we only fix words with very small edit distance (like 1), precision is high but recall is low (we miss some errors). If we allow bigger edit distances, recall improves but precision drops (more wrong suggestions).

What "good" vs "bad" metric values look like for Edit Distance

A good edit distance result is a low number when comparing similar words (like 0 or 1 for typos). For example, "book" vs "books" has edit distance 1 (good match). A bad result is a high edit distance for words that should be close, or a low edit distance for very different words (which means the metric is not capturing similarity well).

In applications, a good threshold might be edit distance ≤ 2 for short words to suggest corrections. Higher distances usually mean unrelated words.

Common pitfalls with Edit Distance metrics

• Ignoring word length: Edit distance is absolute, so longer words naturally have higher distances. Normalizing by word length helps.
• Overfitting to small changes: Some errors need more complex fixes than simple edits.
• Not considering context: Edit distance looks only at characters, not meaning or word usage.
• Computational cost: Calculating edit distance for many pairs can be slow without optimization.

Self-check question

Your spell checker suggests corrections only when edit distance ≤ 1. It misses many typos with distance 2 or 3. Is this good? Why or why not?

Answer: This means high precision (few wrong corrections) but low recall (many typos missed). Depending on your goal, you might want to allow higher edit distances to catch more errors, accepting some wrong suggestions.

Key Result

Edit distance quantifies string similarity by counting minimal edits needed; low values mean close words, crucial for tasks like spell checking.

Practice

1. What does the edit distance (Levenshtein distance) between two words measure?

easy

A. The length difference between two words

B. The minimum number of single-character edits to change one word into the other

C. The number of common letters between two words

D. The number of vowels in both words combined

Solution

1. Step 1: Understand the definition of edit distance

   Edit distance counts how many changes like insertions, deletions, or substitutions are needed to convert one word into another.

2. Step 2: Compare options with the definition

   Only The minimum number of single-character edits to change one word into the other correctly describes this minimum number of single-character edits.

3. Final Answer:

   The minimum number of single-character edits to change one word into the other -> Option B

4. Quick Check:

   Edit distance = minimum edits [OK]

Hint: Edit distance = smallest edits to match words [OK]

Common Mistakes:

• Confusing edit distance with common letters count
• Thinking it measures length difference only
• Mixing up vowels or letter counts

2. Which of the following Python code snippets correctly initializes a 2D table for computing edit distance between strings s1 and s2 of lengths m and n?

easy

A. table = [[0] * (n + 1) for _ in range(m + 1)]

B. table = [[0] * m for _ in range(n)]

C. table = [[0] * (m + 1) for _ in range(n + 1)]

D. table = [[0] * n for _ in range(m)]

Solution

1. Step 1: Recall table size for edit distance

   The table size must be (m+1) rows and (n+1) columns to include empty prefixes of both strings.

2. Step 2: Match code to correct dimensions

   table = [[0] * (n + 1) for _ in range(m + 1)] creates a list with (m+1) rows and each row has (n+1) zeros, which is correct.

3. Final Answer:

   table = [[0] * (n + 1) for _ in range(m + 1)] -> Option A

4. Quick Check:

   Table size = (m+1) x (n+1) [OK]

Hint: Table size = (len(s1)+1) x (len(s2)+1) [OK]

Common Mistakes:

• Swapping m and n in dimensions
• Forgetting to add 1 for empty string prefix
• Using wrong list comprehension order

3. What is the edit distance between the words "kitten" and "sitting"?

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Identify edits from "kitten" to "sitting"

   Changes: substitute 'k' -> 's', substitute 'e' -> 'i', insert 'g' at the end.

2. Step 2: Count total edits

   There are 3 edits: 2 substitutions and 1 insertion.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Edits counted = 3 [OK]

Hint: Count substitutions + insertions + deletions [OK]

Common Mistakes:

• Counting only substitutions
• Missing the final insertion
• Confusing similar letters as no change

4. Consider this Python code snippet for edit distance calculation. What is the error?

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    table = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        table[i][0] = i
    for j in range(n + 1):
        table[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i] == s2[j]:
                cost = 0
            else:
                cost = 1
            table[i][j] = min(table[i-1][j] + 1, table[i][j-1] + 1, table[i-1][j-1] + cost)
    return table[m][n]

medium

A. The return statement should be table[0][0]

B. The table initialization is incorrect

C. The cost should be 2 when characters differ

D. Indexing s1[i] and s2[j] causes an off-by-one error

Solution

1. Step 1: Check string indexing in loops

   Strings are 0-indexed, but loops start at 1, so s1[i] and s2[j] skip first character and cause index errors.

2. Step 2: Correct indexing

   Use s1[i-1] and s2[j-1] to access correct characters for comparison.

3. Final Answer:

   Indexing s1[i] and s2[j] causes an off-by-one error -> Option D

4. Quick Check:

   Indexing error = s1[i-1], s2[j-1] needed [OK]

Hint: Remember strings start at index 0, loops at 1 need offset [OK]

Common Mistakes:

• Using s1[i] instead of s1[i-1]
• Thinking cost must be 2 for difference
• Returning wrong table cell

5. You want to find the closest word to "flame" from the list ["frame", "flan", "flame", "blame"] using edit distance. Which word will the algorithm select as closest?

hard

A. "flame"

B. "frame"

C. "blame"

D. "flan"

Solution

1. Step 1: Calculate edit distances to each word

   Distances: "flame" to "frame" = 1 (substitute 'l'->'r'), to "flan" = 2 (delete 'm' and 'e'), to "blame" = 1 (substitute 'f'->'b'), to "flame" = 0 (same word).

2. Step 2: Identify minimum distance

   The smallest distance is 0 for "flame" itself, meaning exact match.

3. Final Answer:

   "flame" -> Option A

4. Quick Check:

   Exact match distance = 0 [OK]

Hint: Exact match has zero edit distance [OK]

Common Mistakes:

• Choosing word with one letter difference over exact match
• Ignoring exact matches
• Miscounting substitutions