Lightning-AI / Lightning-AI/torchmetrics

Support tensors in edit distance computations

Open
#2,856 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
Dominant language
Python
Stars
2.5k
Forks
526
Avg merge
6d 11h
Merged PRs (30d)
5

Description

## 🚀 Feature

Edit distance is well-defined over arrays of any kind of categorical values (like integers standing in for characters or strings), not just strings. However, the implementation of edit distance is hard-coded to only accept strings or lists of strings.

### Motivation

First, I'd like to use the edit distance operators in this library but converting tensors back into strings is a quite expensive operation.

Second, in my implementation, the tables needed to do said conversion are not currently local to the module that would hold the `torchmetric` metric objects either, so it would add additional bookkeeping as well.

Third and finally, I don't even want to do comparison based on the number of edits as computed via Unicode strings but rather based on arbitrary symbols which may be multi-character. For instance, if we treat strings as nominal attributes, then the edit distance for:

* gold: `["this", "is", "fun"]`
* hypothesis: `["this", "isn't", "fun"]`

is 1, but we get a different result (3) if we join the strings together and use `EditDistance`:

* gold: `"this is fun"`
* hypothesis: `"this isn't fun"`

I would like the ability to get the former measure and keep the computations on the right device.

### Pitch

Currently [the update function](https://github.com/Lightning-AI/torchmetrics/blob/d528131c8e7f130c65ba62a14e12f15906d488c1/src/torchmetrics/functional/text/edit.py#L23) is typed to accept `Union[str, List[str]]` and raises an error if this is not the case. I would remove this restriction so that pairs of 1d and 2d integral tensors are also accepted, and would be interpreted the same way as a pair of strings and a pair of lists of strings would be, respectively. Other than that preprocessing, the checks on type would be loosened there and in the lower-level implementation [here](https://github.com/Lightning-AI/torchmetrics/blob/d528131c8e7f130c65ba62a14e12f15906d488c1/src/torchmetrics/functional/text/helper.py#L330).

I would be willing to take a stab at this for `EditDistance`; I am not volunteering to do it for all the other text metrics however.

### Alternatives

Of course I could always just roll my own metric and keep it to myself.

### Additional context

I wonder if this is going to be miserable on CUDA since there's nothing CUDAish about the edit distance algorithm's very iterative implementation.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the update function in src/torchmetrics/functional/text/edit.py and the lower-level implementation in src/torchmetrics/functional/text/helper.py. Trace the current string and list-of-string validation, then verify that 1D and 2D integral tensors produce the corresponding edit distances while existing inputs continue to work.

Written by the indexing model from the issue text.

Assessment

Tech stack
python, pytorch
Domain
machine-learning
Issue type
Feature
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.