# Text Semantic Annotation: A Distributed Methodology Based on Community Coherence
## 2 Background
### Word Sense Disambiguation Algorithms  
Word Sense Disambiguation and Entity Linking (EL) tasks have been acknowledged as some of the most challenging in the research field of Natural Language processing, due to a variety of factors. The Word Sense Disambiguation (WSD) task has been described as an AI-complete problem [4; 5],namely a problem with equivalent difficulty to that of central artificial intelligence (AI) problems, by analogy to NP-completeness in complexity theory. The task has been approached using a variety of formalizations, at granularities ranging from ontologies and sense inventories to domains, with the presence of domain restrictions or not. The disambiguation coverage focal points, i.e., one target sense per sentence versus full-sentence disambiguation, varies. As WSD relies on knowledge for acquiring the means to associate the most appropriate sense representation in a given context, the challenge of knowledge acquisition, aka the knowledge acquisition bottleneck [6], becomes prevalent. Word Sense Disambiguation approaches can be distinguished into two main classes according to [5]:  
* Supervised WSD: leveraging machine-learning techniques for training a classifier from labeled input training sets, containing appropriate sense label mappings along with other features. * Unsupervised WSD: methods based on unlabeled corpora, lacking manual sense-tagged input context. Another distinction comprises the use of external lexical resources, such as ontologies and machine-readable dictionaries, with knowledge-based, aka knowledge-rich, and corpus-based, aka knowledge-poor, approaches, respectively. Several recent research endeavors have focused on Supervised Knowledge-Based WSD methodologies, using Wikipedia as the underlying knowledge ontology for the entity linking task. The first works on the Word Sense Disambiguation problem following the entity linking approach were [7; 8], which proposed suites of novel methodologies for text annotation with hyperlinks to Wikipedia articles and presenting the technical aspects and challenges of the task. In [9; 10], some more advanced methods were proposed introducing relatedness between Wikipedia articles as the overlap of their inbound links along with the concept of coherence of a candidate annotation with other unambiguous mentions within a context, while modeling the disambiguation process as the selection of the annotations that maximize a global score ranking of coherence relatedness and other statistics. In [11], further improvements were achieved by segmenting the ranking scores to local, for modeling context information concerning only the specific annotation, and global, for modeling the sense consensus coherence among all of the annotation link selections in a text and their disambiguation. The selection ranking was formalized as a quadratic assignment problem for approximating the entity selection maximizing the sum of global and local scores. Later, [12] introduced a computationally efficient and accurate local disambiguation methodology with a focus on short texts that aims at disambiguating using a voting scheme for ranking candidate entity annotations, and selecting the top-scoring one using the collective agreement between all the annotations within a given context, by employing relatedness, commonness, and other statistics, derived by Wikipedia export pre-processing. The authors of [13] explored an alternative methodology by projecting the knowledge base as an undirected weighted graph, referred to as the Mention-Entity Graph, consisting of nodes that are either candidate entities or entity annotations. Edges between entities on that graph model entity relatedness and edges between mentions and entities aim at encoding context similarities of the input knowledge base. The problem is then modeled as the search for a dense subgraph containing all mentioned nodes and only a single mention-entity edge for the disambiguated mentions; however, as this problem is NP-hard, an approximation algorithm was utilized.