Time stamps for CTC models
# What does this PR do?

<!--
Congratulations! You've made it this far! You're not quite done yet though.

Once merged, your PR is going to appear in the release notes with the title you set, so make sure it's a great title that fully reflects the extent of your awesome contribution.

Then, please replace this with a description of the change and which issue is fixed (if applicable). Please also include relevant motivation and context. List any dependencies (if any) that are required for this change.

Once you're done, someone will review your PR shortly (see the section "Who can review?" below to tag some potential reviewers). They may suggest changes to make the code even better. If no one reviewed your PR after a week has passed, don't hesitate to post a new comment @-mentioning the same persons---sometimes notifications get lost.
-->

<!-- Remove if not applicable -->

Proposal of how to add time-stamp to transcribed text. I would very much like to get some feedback from the community on the design before merging this. You can try out this feature directly from master (no need to even use this branch) using the following code:

```python
#!/usr/bin/env python3
from transformers import AutoTokenizer, AutoFeatureExtractor, AutoModelForCTC
from datasets import load_dataset
import datasets
import torch

# import customized tokenizer of PR: https://github.com/huggingface/transformers/pull/15687
tokenizer = AutoTokenizer.from_pretrained("patrickvonplaten/wav2vec2-base-960h-time-stamps", trust_remote_code=True)

model = AutoModelForCTC.from_pretrained("facebook/wav2vec2-base-960h")
feature_extractor = AutoFeatureExtractor.from_pretrained("facebook/wav2vec2-base-960h")

ds = load_dataset("common_voice", "en", split="train", streaming=True)
ds = ds.cast_column("audio", datasets.Audio(sampling_rate=16_000))

ds_iter = iter(ds)
sample = next(ds_iter)

# compare to filename of dataset viewer on https://huggingface.co/datasets/common_voice/viewer/en/train
print("Filename", sample["audio"]["path"])

input_values = feature_extractor(sample["audio"]["array"], return_tensors="pt").input_values

logits = model(input_values).logits
pred_ids = torch.argmax(logits, axis=-1)

outputs = tokenizer.batch_decode(pred_ids, output_time_stamps=True, stride=320, sampling_rate=feature_extractor.sampling_rate)

print("Word time stamps", outputs[0]["word_time_stamps"])
print("Token time stamps", outputs[0]["token_time_stamps"])
```

This example uses the first example of common voice which can be listened to here: https://huggingface.co/datasets/common_voice/viewer/en/train . Feel free to use other examples to see if the time stamps match.

## Before submitting
- [ ] This PR fixes a typo or improves the docs (you can dismiss the other checks if that's the case).
- [ ] Did you read the [contributor guideline](https://github.com/huggingface/transformers/blob/master/CONTRIBUTING.md#start-contributing-pull-requests),
      Pull Request section?
- [ ] Was this discussed/approved via a Github issue or the [forum](https://discuss.huggingface.co/)? Please add a link
      to it if that's the case.
- [ ] Did you make sure to update the documentation with your changes? Here are the
      [documentation guidelines](https://github.com/huggingface/transformers/tree/master/docs), and
      [here are tips on formatting docstrings](https://github.com/huggingface/transformers/tree/master/docs#writing-source-documentation).
- [ ] Did you write any new necessary tests?


## Who can review?

Anyone in the community is free to review the PR once the tests have passed. Feel free to tag
members/contributors who may be interested in your PR.

<!-- Your PR will be replied to more quickly if you can figure out the right person to tag with @

 If you know how to use git blame, that is the easiest way, otherwise, here is a rough guide of **who to tag**.
 Please tag fewer than 3 people.

Models:

- albert, bert, xlm: @LysandreJik
- blenderbot, bart, marian, pegasus, encoderdecoder,  t5: @patrickvonplaten, @patil-suraj
- longformer, reformer, transfoxl, xlnet: @patrickvonplaten
- fsmt: @stas00
- funnel: @sgugger
- gpt2: @patrickvonplaten, @LysandreJik
- rag: @patrickvonplaten, @lhoestq
- tensorflow: @LysandreJik

Library:

- benchmarks: @patrickvonplaten
- deepspeed: @stas00
- ray/raytune: @richardliaw, @amogkam
- text generation: @patrickvonplaten
- tokenizers: @n1t0, @LysandreJik
- trainer: @sgugger
- pipelines: @LysandreJik

Documentation: @sgugger

HF projects:

- datasets: [different repo](https://github.com/huggingface/datasets)
- rust tokenizers: [different repo](https://github.com/huggingface/tokenizers)

Examples:

- maintained examples (not research project or legacy): @sgugger, @patil-suraj
- research_projects/bert-loses-patience: @JetRunner
- research_projects/distillation: @VictorSanh

 -->

_The documentation is not available anymore as the PR was closed or merged._<|||||>I'm still unsure whether we should output the timestamps of the words or the tokens or both. In my opinion in 99% of the use cases one is interested in getting the time stamps of the words or even sentences, but not necessarily of the tokens. However some languages don't really have words, but are based on characters only. So should we maybe just output both word and token time stamps? 

cc @anton-l @Narsil <|||||>You can try out this feature with the following lines of code: 

```python
#!/usr/bin/env python3
from transformers import AutoTokenizer, AutoFeatureExtractor, AutoModelForCTC
from datasets import load_dataset
import datasets
import torch

# import customized tokenizer of PR: https://github.com/huggingface/transformers/pull/15687
tokenizer = AutoTokenizer.from_pretrained("patrickvonplaten/wav2vec2-base-960h-time-stamps", trust_remote_code=True)

model = AutoModelForCTC.from_pretrained("facebook/wav2vec2-base-960h")
feature_extractor = AutoFeatureExtractor.from_pretrained("facebook/wav2vec2-base-960h")

ds = load_dataset("common_voice", "en", split="train", streaming=True)
ds = ds.cast_column("audio", datasets.Audio(sampling_rate=16_000))

ds_iter = iter(ds)
sample = next(ds_iter)

# compare to filename of dataset viewer on https://huggingface.co/datasets/common_voice/viewer/en/train
print("Filename", sample["audio"]["path"])

input_values = feature_extractor(sample["audio"]["array"], return_tensors="pt").input_values

logits = model(input_values).logits
pred_ids = torch.argmax(logits, axis=-1)

outputs = tokenizer.batch_decode(pred_ids, output_time_stamps=True, stride=320, sampling_rate=feature_extractor.sampling_rate)

print("Word time stamps", outputs[0]["word_time_stamps"])
print("Token time stamps", outputs[0]["token_time_stamps"])
```

without even having to use this branch (thanks to @sgugger new "remote_code" feature).<|||||>@Nithin-Holla - I'd be very interested in hearing your feedback here as well in case this feature would be of interest to you<|||||>I've experimented a bit with the code @patrickvonplaten provided. I think this way of outputting both word and token-level timestamps is concise, readable and complete. I think outputting both is preferable to be able to be used for many languages, as you mentioned. But even token-level timestamps can be useful for many applications in case you want more fine-grained control for let's say karaoke or something. But yes, more often than not people will just use the word-level timestamps. In terms of how it is integrated in the huggingface architecture, to me it seems easy to understand/find, but I'm not an expert.

For my application the way it is implemented would require minimal changes, so I'd be very happy merging this. <|||||>This is awesome! We've been playing around with the idea as well. We tested several approaches, like adapting an official [`torchaudio` notebook to 🤗](https://colab.research.google.com/github/pytorch/audio/blob/gh-pages/main/_downloads/160356f33d521341c47ec6b1406a3c2e/forced_alignment_tutorial.ipynb), or the [`ctc-segmentation` library](https://github.com/lumaku/ctc-segmentation). In the end, a simple community script in https://github.com/huggingface/transformers/issues/11307#issuecomment-867648870 provided us with both segment and word level timestamps. This is a great and timely addition!

Maybe it's not a bad idea let the user decide the granularity of the annotation since there are many use-cases.<|||||>> Regarding char vs word time stamps: The traditional forced alignment approaches usually require a second (external) tokenizer to split the predictions into words/lines/sentences and output the time spans for those specific units. How do you feel about including that option here, to support languages without explicit word boundaries?
> 
> Alternatively, we could allow the user to supply the tokens directly to `_retrieve_tokens_with_time_stamps()` and support both external tokenization and forced alignment with ground-truth transcriptions!

I don't fully understand what you mean here. However leaving the possibility for the user to provide the tokens sounds like a sensible idea<|||||>@patrickvonplaten Thanks for working on this! I tried the example code and the output matches the requirements for transcription and subtitling, which is the availability of word-level timestamps. I have a couple of questions:

- Does this also work in the presence of an n-gram language model too?
- What does the `stride` parameter (320 in the example code) refer to here?<|||||>> Regarding char vs word time stamps: The traditional forced alignment approaches usually require a second (external) tokenizer to split the predictions into words/lines/sentences and output the time spans for those specific units. How do you feel about including that option here, to support languages without explicit word boundaries?

This pushes me to think that pure `char` timestamps are better.<|||||>@patrickvonplaten  I was planning on creating a PR this weekend on this timestamp issue (because I already did it [here](https://github.com/jonatasgrosman/huggingsound)). But now I noticed that you have already taken the lead in it :)

I followed a similar path you are taking, but I focused only on returning character-based timestamps. The only problem with this approach is that most CTC beam search decoding tools return only the timestamps of words, such as the pyctcdecode.<|||||>@Narsil - merged it now. Do you think we could now somehow leverage this feature for the pipeline as well so that we can chunk long audio inputs and give them time-stamps? <|||||>@Narsil if there is progress on adding the timestamps to the pipeline, is there any place I could watch that? I might also be able to do a pull request. 

Also thanks for the great work on the feature! Works like a charm 🤗 
<|||||>Also am I correct in saying the current implementation is incompatible with the Wav2VecProccessorWithLM?<|||||>The PR is here: https://github.com/huggingface/transformers/pull/15792

Yes it's pure CTC for now, we need to figure out how to get offsets for CTC+LM in order to get them<|||||>Hi @patrickvonplaten + collaborators, thanks for this feature. I'd like to align the _start_times_ of word/syllables with their corresponding phoneme start times, but I'm surprised to see timestamps don't seem to line up between the outputs of facebook/hubert-large-ls960-ft and facebook/wav2vec2-lv-60-espeak-cv-ft ([notebook](https://colab.research.google.com/drive/1d8pjEuMWRVAphTZAopMAaUPVc7EqFR_h?usp=sharing)).

What am I missing?<|||||>Hey @i-am-neo,

Sorry could you try to post a code snippet showing a minimum reproducible bug. I don't clearly see from your notebook where there is an error, especially since you are using different models (one being a letter CTC, the other being a Phoneme CTC).<|||||>Thanks for your response @patrickvonplaten. Is it not reasonable to expect timestamps to correspond for the same utterance, even if piped through different models?

```
# time(secs) ->
0.42             0.78   0.96   1.16
|                |      |      |
because          you    are    sleeping


0.42             0.84   1.08   1.24
|                |      |      |
bɪkʌz            juː    ɚ      sliːpɪŋ
```<|||||>Hey @i-am-neo,

The will never be exactly the same ;-) That's due to the nature of how CTC works. See this blog post: https://distill.pub/2017/ctc/<|||||>Hi @patrickvonplaten, I can understand that the time _steps_ may not correspond, but converted to _timestamps_, it doesn't seem intuitive that they don't line up, more or less?

If I were to take cut the utterance audio, from the timestamps output yielded by either model, I should end up with the sound that corresponds to its "word," no?<|||||>Hi @i-am-neo, your results seem plausible for me too, 'cause, as @patrickvonplaten said, that timestamp difference is due to the nature of the CTC. During the model's output decoding, the transcription is built based on the tokens (a token can be a letter, phoneme, etc.) with the highest probability for each timestep. Different models can present different confidence outputs on a given timestep for the same audio, causing this discrepancy in the transcriptions timestamps. So the discrepancy you found only shows that the models are different from each other. Now is up to you to find out which one is the most accurate and find a replacement for the other one if you need :)

<|||||>Thanks for your response, @jonatasgrosman. I'm interested in what you find.<|||||>> @patrickvonplaten I was planning on creating a PR this weekend on this timestamp issue (because I already did it [here](https://github.com/jonatasgrosman/huggingsound)). But I was happy now that I noticed that you have already taken the lead in it :)
> 
> I followed a similar path that you are taking, but I focused only on returning the character-based timestamps. The only problem with this approach is that most CTC beam search decoding tools return only the timestamps of words, such as the pyctcdecode does.

Hi @jonatasgrosman @patrickvonplaten , I have the same question on using char-level kenlm model in Chinese. Actually I already found it can be solved in `pyctcdecode.decoder.BeamSearchDecoderCTC._decode_logits()`, the core difference is `next_word` and `word_part`(just make `next_word=char` and `word_part=""`). But I temporarily have no a good idea to make it better to process both word-level and char-level in the huggingface architecture.
<|||||>Hey @qinyuenlp,

Could you maybe open a new issue with your question? I don't understand a 100% what the question here is exactly. Are you looking for time-stamps using KenLM models?