# Negation and Speculation in NLP: A Survey, Corpora, Methods, and Applications
## 3 Methods and Techniques
### Rule-Based Methods  
Initially, the processing of negation and speculation in natural language processing (NLP) was investigated using a handcrafted list of semantic and syntactic rules. The most famous rule-based methods are shown in Figure 1, and are presented in this section. In the late 1990s, [PERSON], [PERSON], and [PERSON] developed the NegExpander algorithm to solve the problem of finding negated UMLS, coding standard for EHRs, by constructing conjunctive phrases [77]. The algorithm's input is a sentence with definite UMLS phrases and part of speech (POS) tags to detect the negation scope. It initially looks for conjunctive words within a sentence, then searches for negation words within the conjunctive phrases. If a single UMLS term is negative, all UMLS phrases within the conjunctive sentence are considered to be negative. In 2001, NegFinder was developed. This is a negation-detecting algorithm using a context-free grammar parser to detect it in medical documents [66]. A set of 40 medical documents from several specialties were manually checked to develop a set of rules to detect the negated patterns. The input to the algorithm consists of coded representations for UMLS concepts extracted from a medical narrative. As a result, the algorithm generates an index with one entry for each concept that shows negated concepts. NegEx is a simple, regular, expression-based algorithm developed to detect negation cues in the English language and identify the affected medical terms [71]. The algorithm takes a sentence with identified UMLS terms and negation words called triggers, which occur before or after a finding. The algorithm relies on three negation phrases: pre-UMLS, post-UMLS, and pseudo-negation. A pseudo-negation expression comprises negative grammatical words, yet this expression is an unreliable negation indicator. All UMLS terms within a window size of 0 to 5 are assigned a negation status. A UMLS term is considered negated, within the scope of negation, if a negation word is located within five tokens of a finding. ConText, derived from the NegEx [71], covers negation, temporality, and the subject concerned for conditions in the clinical texts [78]. Although it depends on regular expressions, it defines the scope of the trigger terms differently and identifies three more contextual properties (hypothetical, historical, and experiencer). The algorithm searches for the negated trigger terms preceding or following a clinical condition. It changes the default value, affirmed for negation, of the trigger term if the condition is within the scope of this trigger term. The negation scope extends from the right of a trigger term to the end of a sentence, unlike NegEx, or to a specific window size. [PERSON] extended the NegEx algorithm to propose the NegMiner tool to handle connecting and multiple negation [79]. The pre-negation and post-negation terms were updated by adding more tokens, and new pre-contiguous and post-contiguous negation terms were added. This tool consists of three modules: the knowledge base and update module, which allows the user to modify negation, and termination terms, in addition to the mining module. Furthermore, the tool takes input as a PDF file that includes multiple sentences, one per line, and generates the results as an output PDF file. Figure 1: Taxonomy of Rule-based Algorithms. Some other researchers have proposed dependency-based parsers to detect the negation scope in complex sentences. In the simplistic form, regular expressions, the researchers assumed that in their corpora, mainly in clinical reports, negation does not include complexly structured sentences [71]. The dependency parser-based negation (DepNeg) used to dig deeply into the syntactic structure of the sentences to detect the complex negation cases for the target-named entities in clinical reports [80]. Using a dependency parser allowed the authors to reduce the problem encountered by rule-based algorithms in detecting the scope of negation.