dataesr/scientific-paragraphs-categorization huggingface dataset:
simp_star 12 ((RValues. const_CharRange "0"%char "9"%char ))). in the VCP Ada subset). We worked on verifying this source-to-source optimizer, with verified optimizations but also a verified frontend using Coqlex (lexer) and Menhir with Coq back-end (parser). Our Coqlex lexer for Ada is written in 200 lines of code. The source-to-source compiler was tested on projects of various sizes; the largest project we compiled has 2380 files totalling 25MB of VCP Ada (a subset of Ada) code -the VCP Ada code is not written by humans as-is but generated by other tools in the pipeline, so it can grow very large. This use-case motivated several changes to Coqlex. The first version of Coqlex imposed termination proofs but any change in the lexer could require rewriting those proofs. Another version imposed restrictions on semantic actions and defined lexers as records that contain the lexer function and properties that ensures termination, making lexer description non-trivial, and mutual recursion impossible.
3:8 Given a set of regexp-based rules l r , a set of function-based rules l f , and a matching policy e, the generated Coq code implements a lexer -a function that takes a fuel n f , lexbuf b, a storage s and returns a lexing result -that works as follows: 1. If n f is equal to 0, then the result is an error. This error is a direct consequence of the fuel technique. 2. Otherwise, from the input string, l r , l f and e, the lexer chooses a rule whose semantic action will be in charge of returning the lexing result. a. if the selected rule is a function-based one, made up with a function f associated with a semantic action a, then there is no consumption. Consequently, the lexing result is the result of a called with b and s. b. if the selected rule is a regexp-based rule c -made up with a regexp r associated with a semantic action a -and if the length of the prefix matched by r using the policy e is a natural number n, then the lexing result is the result of a applied with the updated lexbuf b u and the input storage s.
vl file, is written in Coq using the Coqlex library and is formally verified. 2. The parser, that is in charge of generating an abstract representation from the set of tokens produced by the lexer, is implemented using Menhir  [19]  with -coq switch to generate verified parsers. 3. The code printer, that is in charge of generating the. v file from the abstract representation produced by the parser, is written in OCaml and is not formally verified. The code printer does not include formal semantics equivalence between the representation of the. vl code and the generated. v code. This means that, a priori, a critical user should review the generated. v code. This does not take great efforts because the transformation does not include a complex compilation process: the. vl and. v files have similar structures and are human readable.
In the Coq code, a difference is made between lexical rules made up with regexps associated with semantic actions (regexp-based rules) and those made up with string -> bool functions associated with semantic actions (function-based rules). In a nutshell, a potential user has to (i) review the Coq implementation and verification of regexps, the rule selection together with the associated policies and helpers, that are written and proved in Coq, once; and (ii) either review the code printer of the Coqlex generator once, or review the elements listed above at every generation.
Brzozowski Derivatives for Regexps Matching Given an alphabet (set of symbols or characters) , we use the symbol ε to denote the empty string, and we use the operator ++ for string concatenation. This operation can be extended to languages via L 1 ++ L 2 = {s 1 ++ s 2 | s 1 ∈ L 1 ∧ s 2 ∈ L 2 }. Then we define L 0 = {ε} and L n+1 = L ++ L n (for n ∈ ). Finally, we use the notation L(r) to denote the language of the regexp r, which is inductively defined in Figure  5. Using all the notations above, we say that a regular expression r matches a string s if s ∈ L(r). Similarly, when s / ∈ L(r) we say that r does not match s. Coqlex uses regexp constructions and matching algorithms based on the concept of Brzozowski derivatives. This concept introduces two functions: the nullable function and the derivative of a regexp.
The nullable function takes a regexp r and returns the boolean true if r matches ε (the empty string) and false otherwise. Its inductive definition is given in Figure  6. The derivative of a regexp does match the derivative of the corresponding language. More precisely, if az denotes the string built from the symbol a as first element and the string z, then the derivative of a regular expression r by a symbol a is the regexp r/a that denotes the language {z | az ∈ L(r)}. The inductive definition is given in Figure  7. 3:11 Coqlex: Generating Formally Verified Lexers ∅ r /c = ∅ r ε r /c = ∅ r [[a]] / c = ε if a = c Brzozowski  [4]  extended the derivative operation to strings (denoted by ∥) as described in Figure  8 , and showed that for every regular expression r and every string s s ∈ L(r) ⇐⇒ nullable (r∥s) = true Coqlex uses a modified version of an existing Coq implementation  [16]  of Brzozowski derivatives for regexp matching.
the negation of character set: The notation Σ u l (where l and u are symbols) denotes a regexp whose language is L( Σ u l ) = {c|¬(l ≤ c ∧ c ≤ u) ∧ c ∈ }. This constructor is defined using the following two properties: nullable Σ u l = false and for all symbols c Σ u l /c = ε r if ¬(l ≤ c ∧ c ≤ u) ∅ r otherwise We proved that if ¬(l ≤ u), then Σ u l ≡ ω r and that for every string s, s ∈ L( Σ u l ) if and only if s consists of only one symbol c such that ¬(l ≤ c ∧ c ≤ u). the difference: The notation e 1 -e 2 (where e 1 and e 2 are regexps) denotes a regexp whose language is L(e 1 -e 2 ) = {s|s ∈ L(e 1 ) ∧ s / ∈ L(e 2 )}. This construction is defined using the following two properties: nullable e 1 -e 2 = (nullable e 1 ) ∧¬(nullable e 2 ) and for all symbol c, (e 1 -e 2 )/c = e 1 /ce 2 /c.
Evaluation: Syntax and Expressivity We are now going to compare Coqlex with OCamllex (4. 14. 0), the OCaml standard lexer generator, Flex (2. 6. 4), the C standard lexer generator, and Verbatim++ (github Dec. 2021, https://github. com/egolf-cs/Verbatim), the current state of the art for lexers verified in Coq. It is common for Coq users to implement unverified part of their programs in OCaml, so we can expect that Coqlex would replace an existing OCamllex 3:17 lexer; we also compare with flex, which is very similar to OCamllex in practice, to show that standard unverified lexer generators form a meaningful common baseline. We compare the convenience of the user-facing syntax in which the lexer is described, and the expressivity of its semantics -which lexing rules can or cannot be easily expressed in the system.
Regarding those specifications, the lexers are supposed to work as follows: Note that the typical goal for verified tools is not to match non-verified tools in performance -this is rarely realistic -but rather to provide "good enough" performance for the tool use-cases. We evaluated the execution time of the generated lexical analysers in two phases. For the first phase, we evaluated their performance on United States GDP data from the past several decades[2], stored in JSON format, the same benchmark used to evaluate the performances of Verbatim++. We started with analysing a JSON lexer implemented by the Verbatim++ developers using Verbatim++ Coq source code, then we used Coqlex, flex and OCamllex generators to generate lexers with very similar specifications. We compared the time performance in Figure  15 ; we notice three groups separated by two order of magnitudes each, ocamllex and flex which are the fastest, Coqlex in the middle, and Verbatim++ as the slowest tool.
Conclusion Coqlex proposes a Coq library that implements all the common features used in lexical analysis and provides a Coq proof of their correctness. It also brings a Code generator that reads a lex-like lexer description and outputs verified lexers written in Coq using the Coqlex library. By design, Coqlex is built to be usable and simple. The Coqlex library has been used to build the lexer of Coqlex generator. The Coqlex generator and library have been used in the implementation of a formally verified optimizing compiler. Despite its simplicity, lexers generated by the Coqlex generator or implemented using the Coqlex library have good enough performance, noticeably better than the existing tool Verbatim++. Even if the execution time performance of Coqlex can be improved further, it lays strong foundations for verified lexer generation.
Future Work Some performance improvements could come from extraction to native OCaml strings (or arrays), or the memoization of the derivation function using axiomatized imperative data structures. To improve performance further, we could translate lexing rules to a proper DFA representation. There are two independent questions: How to do the computation. We should take inspiration from the excellent description of DFA construction in  [18]. They introduce the notion of "derivative classes" to compute equivalence classes of characters for a given redex, and reduce the number of transitions. They also introduce the notion of "regex vector" to derive all lexing rules in parallel, instead of having a separate automata construction for each rule. However, there is a real possibility that the size of the resulting automaton would be too big for Coq to handle in practice.
Unverified lexer generators use sophisticated tricks to compress the description of the automata, which could be difficult to verify, and may not even suffice to ensure practicality inside Coq. If the approach of generating deterministic automata proved impractical, we could instead generate a non-deterministic automata, for example using Antimirov derivatives  [1] , which can be sensibly more compact at the cost of a reasonable performance overhead. When to do the computation. Verbatim++ starts computing the lexing automata whenever the user wants to get the lexing function from the lexing rules, which is typically whenever the Coq-implemented user program is invoked. In our experiment, the JSON benchmark for example needs two seconds of automata computation before they start accepting input.
A convenient lexer generator should avoid this constant overhead by generating the automaton during a meta-programming phase ahead of the actual lexing, but doing this in a verified setting is not obvious. We played with the Verbatim++ implementation and tried asking Coq to do the computation at type-checking time, but the Coq virtual machine fails in practice as the computation requirements are too large. It may be possible that a more efficient automata construction, using derivative classes or an NFA construction, could be done at type-checking time in this way. Another approach would be to do the automata construction at Coqlex preprocessing time, and only have Coq validate the correspondence of the lexing rules and the automata. This requires either producing a Coq proof script during this metaprogramming step, or defining a Coq tactic that is flexible enough to validate all such correspondences.
In Coqlex, being careful of these two issues sufficed to produce a reasonably efficient regexp matcher. (We experimented with memoizing the derivation function, which gives a further 2x speedup, but is hard to do in a fully-verified way as it typically involves unverified imperative data structures. ) Our hypothesis is that Verbatim made more complex implementation choices to avoid the quadratic blowup that do result in linear lexing performance but with very large book-keeping overhead: 1. In a precomputation phase, they compute a very large set of possible repeated derivatives, stored in an associative data structure that Verbatim++ calls a DFA: the states of the automaton are regexps. (This corresponds to the constant 2s overhead observed on the JSON grammar. ) 2. The precomputed table of derivates is represented by a trie.
Electronic health record (EHR) systems with prescription data offer vast potential in pharmacoepidemiology and pharmacogenomics. The large amount of clinical data recorded in these systems requires automatic processing to extract relevant information. This paper introduces PRESNER, a name entity recognition (NER) and classification pipeline for EHR prescription data. The pipeline uses the pre-trained transformer Bio-ClinicalBERT fine-tuned on UK Biobank prescription entries manually annotated with medication-related information (drug name, route of administration, pharmaceutical form, strength, and dosage) as the core NER system. Moreover, PRESNER also maps drugs to the Anatomical Therapeutic and Chemical (ATC) classification system and distinguishes between systemic and non-systemic drug products.
Introduction Large anonymized electronic health records (EHR) with prescription data linked to biobank registries enable large pharmacoepidemiologic and pharmacogenomic studies  (Mcinnes, 2021). UK Biobank (UKB) collects health information and biological samples from over half a million volunteers  (Bycroft et al. , 2018). Since 2019, primary care records from the UK National Health System (NHS) have been linked for approximately 45% of the UKB cohort (~230,000 participants), corresponding to more than 57 million prescription entries. Unlike other prescription records  (Pottegård et al. , 2016; Alvarez-Madrazo et al. , 2016) , these datasets store unprocessed prescription information for dispensation purposes. Registries typically use national or internal codes for drugs, necessitating manual extraction by active ingredients and brand names  (Fabbri et al.
, 2018). There has been substantial interest in developing Natural Language Processing (NLP) information extraction (IE) systems for drug named entity recognition (NER)  (Segura-Bedmar et al. , 2013; Kormilitzin et al. , 2021)  and other relevant medication information  (Johnson et al. , 2016). The irruption of contextual word embedding models, such as the Bidirectional Encoder Representations from Transformers (BERT)  (Devlin et al. , 2019) , has fuelled the progress of NLP in all domains through the use of transfer learning with pre-trained models, especially when fine-tuned for a specific NLP application  (Henry et al. , 2020; Alsentzer et al. , 2019). This paper introduces PRESNER, a tailored NER and classification pipeline for EHR prescription data. Based on the transformer for medical text Bio-ClinicalBERT  (Alsentzer et al.
, 2019)  and fine-tuned with UKB prescription entries, PRESNER aims to automate standardised extraction, mapping, and classification of prescriptions, serving as a benchmarking tool for research acceleration. Anticipated broader applications include processing prescription data from sources like CPRD  (Ghosh et al. , 2019) , MIMIC-III, and hospital EHR datasets. PRESNER is designed to assist researchers working with raw prescription data from EHR. This pipeline not only performs drug NER but also offers additional capabilities, enabling users to automatically identify systemic drug products and apply filters to prescriptions based on drug name or therapeutic group by their ATC codes. The workflow seamlessly handles entity recognition and classification tasks, by mapping prescriptions to ATC codes and categorising them as either systemic or nonsystemic.
ChEMBL dictionary The ChEMBL database  (Gaulton et al. , 2012)  is the largest open-source resource for medicinal chemistry data. Using its web services API, we built a dictionary for approved human molecules. The latest version of the dictionary contained 38,215 synonyms for 4,127 active ingredients, mapped to 4,193 ChEMBL ID and 3,206 ATC codes. However, to include the latest information curated from the database, when run by the user the pipeline accesses the API to create an updated version of the dictionary. This dictionary is used by the pipeline to map prescription entries to their ATC codes. We also used this dictionary in a baseline approach for the NER task.
UK Biobank prescription dataset UKB Data-Field "42039" was used to retrieve prescription data, covering primary care prescriptions for 222,096 individuals and 102,052 unique prescription names entries. These data included the drug product's name, quantity, prescription date, and one or more codes from medicinal and sanitary products coding systems used across the NHS primary care (Supplementary Table  1 ). A dataset of 1,100 randomly selected prescription entries for fine-tuning and evaluation was manually annotated using the BRAT tool  (Peng et al. , 2019 ) by a pharmacist with prior experience in the annotation of pharmacological texts (Table  1 ). We applied stratified sampling to split the whole dataset into train (80%) and test (20%) splits. We refer to this annotated dataset as the UKB prescription dataset throughout this document.
The n2c2 corpus Due to annotation processes being one of the most time-costly and expensive tasks in NLP and machine learning, the size of our UK Biobank prescription dataset is limited. For this reason, we also exploited the National NLP Clinical Challenges (n2c2) corpus to fine-tune our NER pipeline. This corpus includes over 83 thousand annotated entities for medication information (strength, dosage, duration, frequency, form, route, reason for administration, and adverse effects) from 505 discharge summaries (Table  1 ) from the MIMIC-III dataset  (Johnson et al. , 2016).
The NER task The core model in PRESNER is based on Bio-ClinicalBERT  (Alsentzer et al. , 2019) , a contextual word embedding model that builds upon BioBERT  (Lee et al. , 2020)  and specifically pre-trained on the MIMIC-III dataset, addressing the linguistic disparities between general domain and clinical texts. We fine-tuned the Bio-ClincalBERT model by adding a conditional random field (CRF) layer  (Ketmaneechairat and Maliyaem, 2020). This layer allows us to capture dependencies between labels. The extended architecture -i. e. , the Bio-ClinicalBERT model enhanced with a CRF optimization layer (Supplementary Figure  1 ) -will be referred to as the BCB-CRF model throughout this document. Preprocessing and training details are provided in Supplementary Methods. For comparison purposes, the BCB-CRF model was fine-tuned in the following three scenarios: i) only using the n2c2 corpus, ii) only using the UKB prescription dataset, and iii) using both datasets.
In this third scenario (Figure  1 ), the BCB-CRF model was fine-tuned on the n2c2 corpus, and then, a second fine-tuning was performed on the UKB prescription dataset. The n2c2 corpus was used first due to the relatively limited number of annotated entities in the UKB prescription dataset (Table  1 ). Moreover, this approach allows us to harness the knowledge transfer from the n2c2 corpus and also adapt to the unique language features present in the UKB prescription dataset. Our hypothesis is that this approach can improve the recognition of under-represented entities such as ROUTE (with only 92 instances in the training split of the UKB prescription dataset). For hyperparameter tuning, 20% of the n2c2 training sentences were used as a validation set. Limited annotated data in the UKB prescription dataset necessitated 5-fold cross-validation.
We also developed a baseline approach combining a dictionary-based NER module based on the ChEMBL dictionary and the pre-trained NER models from Med7  (Kormilitzin et al. , 2021). There are two Med7 models available, one based on convolution networks and another based on the transformer-based model RoBERTA  (Liu et al. , 2021). In this work, we combined the output of both and refer to them as Med7 for simplicity. The output of the baseline is the union of all entities identified by the dictionary and Med7. More details on the baseline model can be found in Supplementary Methods. and without systemic activity and assigning the most appropriate ATC code(s). This facilitates further filtering by researchers using the EHR prescription dataset. ATC codes were mapped to DRUG entities using a refined dictionary created from ChEMBL (including 3,206 ATC codes linked to 3,433 ChEMBL ID).
Results The baseline approach was outperformed by the BCB-CRF model which was either fine-tuned using only the UKB prescription dataset or initially fine-tuned with n2c2 followed by fine-tuning with the UKB prescription dataset. These two BCB-CRF models obtained higher F1 for all entity types (Table  2 ). The greatest improvement (up to 0. 24 in macro-F1) was achieved by the BCB-CRF model fine-tuned first on the n2c2 corpus and then on the UKB prescription dataset. While transfer learning from n2c2 corpus helped to mitigate the scarcity of annotated entities in the UKB prescription dataset, this second dataset provided information on the text distribution of the target documents (i. e. , prescription entries). The effectiveness of this approach was particularly evident in the case of the under-represented entity type, ROUTE, where pre-adjustment with n2c2 significantly improved recall performance.
On the contrary, the BCB-CRF model fine-tuned only on the n2c2 corpus provided lower results than the other BCB-CRF models and the baseline approach for FORM, ROUTE, and STRENGTH entities. In addition to the disparities in text distributions between n2c2 and prescription entries, this lower performance could be due to the fact that Med7 was trained with n2c2 but also with two additional corpora annotated by the authors. The PRESNER pipeline also addresses the mapping of DRUG entities to ATC codes by using a matching process based on a dictionary from ChEMBL. DRUG entities extracted by the BCB-CRF or the Med7 module of the baseline but not mapped to ATC codes were mainly brand names not included in the ChEMBL dictionary (Figure  2  and Supplementary Figures  3  and 4 ), like hormone replacement therapy or oral contraceptives, and non-drug items, supplements, or healthcare terms.
A word cloud (Figure  2 ) of top terms not retrieved by any approach (10% total) displays nonmedicinal sanitary products predominantly. The baseline retrieved more incorrect ROUTE terms (e. g. , the pharmaceutical form 'injection', or the adjectives 'dispersible', 'gastro', 'conjugated') while failing more often to retrieve correct ones such as 'eye', 'ear', 'vaginal' or 'oromucosal'. All the approaches failed to extract correct FORM terms, but non-related words (e. g. ,  'medicated', 'pack', ''vanilla', 'lasagne', 'blister')  were more commonly retrieved by Med7 (Supplementary Figure  5 ). Fine-tuning with both n2c2 and the UKB prescription dataset greatly benefited the entities STRENGTH and DOSAGE compared to the baseline. The baseline model performed poorly for entity DOSAGE with precision and recall scores of 0.
66 and 0. 24, respectively. Likewise, entity STRENGTH had a precision of only 0. 5, whereas the BCB-CRF model achieved a precision of 0. 96. This is partly because the baseline consistently mislabelled the total prescribed unit count as STRENGTH instead of DOSAGE, resulting in low recall for DOSAGE (0. 2) and low precision for STRENGTH (0. 5). Figure  3  shows an example of the output of the PRESNER pipeline, with the extracted structured information for the various entity types. 458,132 prescription entries (72% of the total dataset) were mapped to at least one ATC code. From these, 81% and 13% were classified as SDP and NSDP, respectively.