[WIP] Add Linformer
# What does this PR do?

This PR adds [Linformer: Self-Attention with Linear Complexity](https://arxiv.org/abs/2006.04768) by Facebook AI. Contrary to the regular Transformer, it has linear complexity in both space and time w.r.t. the sequence length, allowing it to be trained on much larger sequence lengths. 

I've created both a PT and TF version using the CookieCutter template (BERT-based, encoder-only). The only difference with BERT is that:
- `LinformerSelfAttention` looks a bit different compared to `BertSelfAttention`. The Linformer model adds 2 projection matrices to the keys and values, which project the sequence dimension (which is of size 512 by default) to a lower dimension k (such as `k=256`). As you'll see, I do not use the `extended_attention_mask` function which is used by other models. Instead, I cast the attention mask across the different attention heads by simply writing `attention_mask[:,None,:,None]`, which I then multiply by the keys and values, before projecting to the lower dimension. 
- One can choose to use the same projection matrix for both keys and values. This is determined by the `share_projection` attribute of `LinformerConfig`.
- Linformer comes with 2 limitations: it cannot be used in the autoregressive case (see [this](https://github.com/lucidrains/linformer/issues/4#issuecomment-777781537)) - hence I removed the `is_decoder` logic, and it assumes a fixed sequence length. The latter is determined by the `seq_length` attribute of LinformerConfig, which is set to 512 by default. So if you provide `input_ids` and so on to the model, their length must be equal to the value of `seq_length`. 

Fixes the following issues:
#4967
#5201

## Before submitting
- [ ] Did you write any new necessary tests? Yes I did, however I need some help to make sure all pass. Current status: for PyTorch, 30 are passing, 7 are failing. For Tensorflow, 26 passed, 9 failed. Note that there are currently no integration tests, as no weights were shared by the authors yet. However, they plan to release them as seen [here](https://github.com/pytorch/fairseq/issues/2795#issuecomment-720680448). 
- [ ] Also, it seems that the original authors relied on RoBERTa rather than BERT, so we might have to let `LinformerTokenizer` inherit from `RobertaTokenizer` rather than `BertTokenizer`.


## Who can review?

@patil-suraj @LysandreJik 


This issue has been automatically marked as stale because it has not had recent activity. If you think this still needs to be addressed please comment on this thread.

Please note that issues that do not follow the [contributing guidelines](https://github.com/huggingface/transformers/blob/master/CONTRIBUTING.md) are likely to be ignored.<|||||>Unstale<|||||>This Linformer's ForSequenceClassification is not work. I finished mlm pretrain with 1.14loss(100epoch, wiki-cn). But in afqmf, acc only reach 0.6899<|||||>Hi @luoda888,

great to see you're already using Linformer! Did you pretrain Linformer on several GPUs using the `run_mlm.py` script? What is afqmf?

Note that in the [original paper](https://arxiv.org/abs/2006.04768), they state that "All models are pretrained with the masked-language-modeling (MLM) objective, and the training for all experiments are parallelized across 64 Tesla V100 GPUs with 250k updates."<|||||>@NielsRogge  since the weights for `linformer` are not yet released, maybe we can add this model in the the `research_projects` dir, similar to [performer](https://github.com/huggingface/transformers/tree/master/examples/research_projects/performer) and add a training/fine-tuning script there.<|||||>> Hi @luoda888,
> 
> great to see you're already using Linformer! Did you pretrain Linformer on several GPUs using the `run_mlm.py` script? What is afqmf?
> 
> Note that in the [original paper](https://arxiv.org/abs/2006.04768), they state that "All models are pretrained with the masked-language-modeling (MLM) objective, and the training for all experiments are parallelized across 64 Tesla V100 GPUs with 250k updates."

Thanks reply.
1. I pre-trained the linformer model from scratch, using Wikipedia Chinese corpus. Set text maxlen=128, k=64, on 10 nodes (each with 8*32g V100) (which means I use 80*v100), 2.5 hours of pre-training. Using LinkerForMaskedLM, mlm loss reached 1.14 when training stopped.
2. I use the trained model for validation on downstream tasks, and afqmf is the semantic similarity (text matching) task in Chinese (https://github.com/CLUEbenchmark/CLUE). According to the report, the accuracy of bert-base-chinese is 74.16% when the parameter settings of bs=16, lr=2e-5, maxlen=128, epoch=3 are fine-tuned. I used the parameters of bs=256, lr=2e-5, maxlen=128, epoch=3 and the bert-base-chinese accuracy was 72.81%. However, when the LinformerForSequenceClassifier is used for classification, the AUC is only 0.5, and the accuracy is only 0.6899 (that is, all predictions are 0 categories).
3. For the specific training details, I use the Trainer interface, distributed pre-training. The config of the informer is seq_length=128, LinformerConfig(vocab_size=vocab_size, seq_length=seq_length, share_projection=True, k=seq_length//2) . I use BertWordPieceTokenizer for tokenizer, random mask (DataCollatorForLanguageModeling). with FP16 & train_batch_size=256, gradient_accumulation_steps=1, dataloader_num_workers=4, model.save_pretrained(output_files).

_**I analyze possible causes.**_
1. The fine-tuning script can run properly, and the bert-base-chinese open source weight is executed as expected.
2. Is it possible that the tokenizer is faulty? Inconsistent in pre-training and fine-tuning.
3. Press BertConfig again to perform pre-training. The fine-tuning effect is also AUC = 0.5. So I'm guessing that Bert Word Piece Tokenizer has some problems with Chinese.

If you don't mind, I'd like to share the code with you to locate the problem.<|||||>> @NielsRogge since the weights for `linformer` are not yet released, maybe we can add this model in the the `research_projects` dir, similar to [performer](https://github.com/huggingface/transformers/tree/master/examples/research_projects/performer) and add a training/fine-tuning script there.

I think it's a very good idea, and it would be nice to have a torch-only version available instead of jax, flax. Also, I've observed that transformers_plus_performers reproduce the performer paper, and I don't know if you've noticed.<|||||>I'd love you to come up with a pre-training script from the beginning on the Chinese Wikipedia and how to fine-tune the Chinese downstream tasks. In addition, it is possible to design more pre-training tasks (SpanMask + SBO, StuncBert(TGS), ASP, etc.) and design more fine-tuned multi-task learning (MT-DNN).

BTW, nezha is also can add in models. https://github.com/lonePatient/NeZha_Chinese_PyTorch. I test it in Chinese~
BTWWW, PGD & FGM & FreeAT & FreeLB & SMART also can add in modeling_language or fine-tune~~~~<|||||>That's really interesting to read! Wow, 80 V100's, that's a lot.

Some remarks:

* I still need someone to verify my implementation of `LinformerSelfAttention` in `modeling_linformer.py`, as I'm currently the only one that implemented it, I'd like to have a second opinion to know for sure my implementation is correct. I used [this implementation](https://github.com/mlpen/Nystromformer/blob/main/code/attention_linformer.py) (from the author of Nyströmformer, who benchmarked several efficient self-attention implementations) as a reference. I also checked @lucidrains' implementation, available [here](https://github.com/lucidrains/linformer). However, as you see the loss going down, it might indeed be a tokenizer issue (I'm fairly sure my implementation is correct). 
* In both the original paper and the Nyströmformer implementation, it looks like they rely on a RoBERTa encoder rather than BERT, hence they also use `RobertaTokenizer` rather than `BertTokenizer`. So this is something that might have to be updated (as mentioned at the top of this PR). 
* Did you use `BertTokenizer.from_pretrained("bert-base-chinese")`? Or did you train the tokenizer on Chinese Wikipedia before using it?

And indeed, it would be great if we can provide the same functionality for Chinese, and introduce pre-training/fine-tuning scripts for Chinese. <|||||>> That's really interesting to read! Wow, 80 V100's, that's a lot.
> 
> Some remarks:
> 
> * I still need someone to verify my implementation of `LinformerSelfAttention` in `modeling_linformer.py`, as I'm currently the only one that implemented it, I'd like to have a second opinion to know for sure my implementation is correct. I used [this implementation](https://github.com/mlpen/Nystromformer/blob/main/code/attention_linformer.py) (from the author of Nyströmformer, who benchmarked several efficient self-attention implementations) as a reference. I also checked @lucidrains' implementation, available [here](https://github.com/lucidrains/linformer). However, as you see the loss going down, it might indeed be a tokenizer issue (I'm fairly sure my implementation is correct).
> * In both the original paper and the Nyströmformer implementation, it looks like they rely on a RoBERTa encoder rather than BERT, hence they also use `RobertaTokenizer` rather than `BertTokenizer`. So this is something that might have to be updated (as mentioned at the top of this PR).
> * Did you use `BertTokenizer.from_pretrained("bert-base-chinese")`? Or did you train the tokenizer on Chinese Wikipedia before using it?
> 
> And indeed, it would be great if we can provide the same functionality for Chinese, and introduce pre-training/fine-tuning scripts for Chinese.

```
limit_alphabat = 30000
special_tokens = ["[PAD]", "[UNK]", "[CLS]", "[SEP]", "[MASK]"]

tokenizer = tokenizers.BertWordPieceTokenizer(clean_text=True, handle_chinese_chars=True, strip_accents=True, lowercase=True)
tokenizer.train(
        files,
        vocab_size = args.vocab_size,
        min_frequency = args.min_frequency,
        show_progress = True,
        special_tokens = special_tokens,
        limit_alphabet = limit_alphabat,
        wordpieces_prefix = "##",
    )
try:
    os.mkdir(output_files)
except:
    pass
tokenizer.save_model(output_files)
```
MultiProcessing for tokenizer (1.3GB corpus is too large). Copy K times for dp mask (follow roberta)
```
def _convert_to_transformer_inputs(question, answer, tokenizer, max_sequence_length):
    """Converts tokenized input to ids, masks and segments for transformer (including bert)"""
    
    def return_id(str1, str2, truncation_strategy, length):

        inputs = tokenizer.encode_plus(str1, str2,
            add_special_tokens=True,
            max_length=length,
            truncation_strategy=truncation_strategy,
            truncation=True
            )
        
        input_ids =  inputs["input_ids"]
        input_masks = [1] * len(input_ids)
        input_segments = inputs["token_type_ids"]
        padding_length = length - len(input_ids)
        padding_id = tokenizer.pad_token_id
        input_ids = input_ids + ([padding_id] * padding_length)
        input_masks = input_masks + ([0] * padding_length)
        input_segments = input_segments + ([0] * padding_length)
        
        return [input_ids, input_masks, input_segments]
    
    input_ids_q, input_masks_q, input_segments_q = return_id(
        question, answer, 'longest_first', max_sequence_length)
    
    return input_ids_q

def compute_input_arrays(lines, tokenizer, max_sequence_length):
    
    input_ids = Parallel(backend='multiprocessing', n_jobs=args.n_jobs, batch_size=512)\
                  (delayed(_convert_to_transformer_inputs)(line, None, tokenizer, max_sequence_length) for line in tqdm(lines))
        
    return [i for i in np.asarray(input_ids, dtype=np.int32)]

tokenizer = tfs.BertTokenizer.from_pretrained(output_files + '/vocab.txt', maxlen=512)
with open(files, encoding="utf-8") as f:
    lines = [line for line in tqdm(f.read().splitlines()) if (len(line) > 0 and not line.isspace())]
dataset = compute_input_arrays(lines, tokenizer, args.maxlen)

dp_mask = args.dp_mask
shuffle = deepcopy(dataset)
for i in tqdm(range(dp_mask)):
    random.shuffle(shuffle)
    dataset.extend(shuffle)

np.save(files + "-dpmask.npy", dataset)
logger.info("Sentence Cut Finish")
```

1. In many Chinese pre-training models, Roberta Tokenizer is often used as Bert Tokenizer, such as hfl:/roberta-chinese-wwm.

2. The same problem occurs when I use the BertTokenizer to train the Bert. After the same parameters are trained, the AUC is still 0.5.

```
class LineByLineTextDataset(Dataset):
    """
    This will be superseded by a framework-agnostic approach soon.
    """

    def __init__(self, tokenizer: PreTrainedTokenizer, file_path: str, block_size: int):
        assert os.path.isfile(file_path), f"Input file path {file_path} not found"
        # Here, we do not cache the features, operating under the assumption
        # that we will soon use fast multithreaded tokenizers from the
        # `tokenizers` repo everywhere =)

        lines = np.load(files + '-dpmask.npy')
        if args.debug:
            lines = lines[:20000]
        
        self.examples = [{"input_ids": torch.tensor(e, dtype=torch.long)} for e in lines]

    def __len__(self):
        return len(self.examples)

    def __getitem__(self, i) -> Dict[str, torch.tensor]:
        return self.examples[i]


vocab_size = 21128
seq_length = args.max_seq_length
config = LinformerConfig(vocab_size=vocab_size, seq_length=seq_length, share_projection=True, k=seq_length//2)
model = LinformerForMaskedLM(config=config)

tokenizer = tfs.BertTokenizer.from_pretrained(output_files + '/vocab.txt', maxlen=seq_length)
dataset = LineByLineTextDataset(tokenizer=tokenizer, file_path=files, block_size=seq_length)
datacol = tfs.DataCollatorForLanguageModeling(tokenizer=tokenizer, mlm=True, mlm_probability=0.15)

train_args = tfs.TrainingArguments(
    output_dir = output_files,
    overwrite_output_dir = True,
    num_train_epochs = args.train_epochs,
    per_device_train_batch_size = args.train_batch_size,
    gradient_accumulation_steps = args.gradient_accumulation_steps,
    save_steps = 10000,
    logging_steps = 500,
    save_total_limit = 10,
    fp16 = args.fp16,
    prediction_loss_only = True,
    dataloader_num_workers = args.num_workers,
    local_rank = args.local_rank,
    disable_tqdm = False,
)

logger.info("TrainingArguments Init")
logger.info(train_args)
decay_parameters = get_parameter_names(model, [torch.nn.LayerNorm])
decay_parameters = [name for name in decay_parameters if "bias" not in name]
optimizer_grouped_parameters = [
    { "params": [p for n, p in model.named_parameters() if n in decay_parameters], "weight_decay": 0.0,},
    { "params": [p for n, p in model.named_parameters() if n not in decay_parameters], "weight_decay": 0.0,}
]

optimizer_cls = torch.optim.Adam(optimizer_grouped_parameters, lr=args.learning_rate)
lr_cls = torch.optim.lr_scheduler.CosineAnnealingLR(optimizer_cls, T_max=5, eta_min=0)

trainer = tfs.Trainer(
    model = model,
    args = train_args,
    data_collator = datacol,
    train_dataset = dataset,
    optimizers = (optimizer_cls, lr_cls),
)

trainer.train()
model.save_pretrained(output_files)
```<|||||>> I still need someone to verify my implementation of LinformerSelfAttention in modeling_linformer.py, as I'm currently the only one that implemented it, I'd like to have a second opinion to know for sure my implementation is correct.

I would be happy to take a look now. Would you mind opening another PR and adding this in `research_projects/linformer` dir ? Just the modeling and config file should be enough.

Also, would it be possible to make the implem more similar to the official implem in `fairseq` ? That way we could compare apples to apples. We could then train a small model in `fairseq` and then port and compare it with this implem ,  that would make it a bit easier to verify the model.<|||||>> > I still need someone to verify my implementation of LinformerSelfAttention in modeling_linformer.py, as I'm currently the only one that implemented it, I'd like to have a second opinion to know for sure my implementation is correct.
> 
> I would be happy to take a look now. Would you mind opening another PR and adding this in `research_projects/linformer` dir ? Just the modeling and config file should be enough.
> 
> Also, would it be possible to make the implem more similar to the official implem in `fairseq` ? That way we could compare apples to apples. We could then train a small model in `fairseq` and then port and compare it with this implem , that would make it a bit easier to verify the model.

lol. I can provide GPUs for testing.<|||||>This issue has been automatically marked as stale because it has not had recent activity. If you think this still needs to be addressed please comment on this thread.

Please note that issues that do not follow the [contributing guidelines](https://github.com/huggingface/transformers/blob/master/CONTRIBUTING.md) are likely to be ignored.<|||||>unstale<|||||>What happened to this? 
asking for a friend :D <|||||>Hi,

Well actually I wonder if we could investigate the issue with fine-tuning LinFormer. 

@luoda888 would you be able to pre-train the model on English data (Books/Wikipedia)?<|||||>Hello,
Sounds preety cool tbh, 
i'll try to tinker with. lets see if i go anywhere<|||||>> Hi,
> 
> Well actually I wonder if we could investigate the issue with fine-tuning LinFormer.
> 
> @luoda888 would you be able to pre-train the model on English data (Books/Wikipedia)?

I will try it