dataesr/scientific-paragraphs-categorization huggingface dataset:
unisa. it/). A portion of the database utilized is composed of negative images (1446, corresponding to approximately 10%), that is, images whose fluorescence values are not to be associated with autoimmunity problems; 10% of negative cases were considered a satisfactory percentage, in terms of statistics and value purposes, for both Immunologists and the CAD. The remaining images were classified into different patterns (according to the physician reporting); the distribution rates are shown in Figure  1. In a second step, 6974 images were anonymously exchanged between partners in full respect of ethics and for the purpose of blind double reporting by Senior or Junior Immunologists. The Junior Immunologists are Ph. D. students (3) and are fundamental Immunologists  (1). The four young Immunologists (Juniors), all coming from the Tunis Faculty of Sciences, were involved as Readers of images already reported by the experts (Seniors).
CAD Immuno. Computer Aided Diagnosis (CAD) systems are widely used for different tasks within medicine such as second reading, increasing the diagnosis speed, and training physicians for special task. One of such systems is proposed in recent days for automatic HEp-2 images classification, which is important for detection of antibodies in human serum. In the AIDA Project the CyclopusCAD Immuno software was used, powered by CyclopusCAD ltd. , a spin-off of University of Palermo  [14] [15] [16] [17] [18]. It consists of a computer system for image analysis using artificial intelligence methods, of which some are proprietary  [19, 20]. The performance comparison between CyclopusCAD Immuno and several automated systems for IIF analysis was presented in a recent paper by Gorgi et al. [21]. The most frequent and clinically useful staining patterns are represented in Figure  3.
Results and Discussion In order to evaluate the concordance level, a subsample of 589 wells (each of them with 3 images), reported by two Senior Immunologists, was analyzed. The results are shown in Table  2  and revealed a concordance level around 71% (Cohen's  statistic was 0. 64). The maximum level of concordance has been obtained for the Centromere pattern. The lower concordance level is observed with the Fine Speckled pattern. This concordance level represents the difficulty of interpretation of IIF images and the obvious need for a double reading and for Gold Standard. Taking only images into account, with a concordance of interpretation between the two Senior Immunologists, a subsample database was then extracted containing 1006 images, representing all types of patterns (302 wells corresponding to 906 images) and including negative tests (100 images).
In this Gold Standard database, the distribution of the different patterns is given in Figure  6. The overall approach is resumed in Table  3. Our objective is to evaluate the added value of the CAD used as a second Reader. We first tested CAD performance stand-alone in comparison with two Junior Immunologists. Four young fundamental Immunologists (Juniors) were involved as Readers of images already reported by the experts (Seniors). Before being compared to the CAD, the reporting concordances of these Junior Readers were compared with each other and to those of a Senior Immunologist. As shown in Table  4 , and as expected, the concordance level between Junior and Senior Immunologists was lower than that observed when comparing only Seniors. The only exception to this is with Reader 4, who is a more experienced fundamental Immunologist but has never been involved in diagnosis.
Conclusions In this paper the AIDA Project and its preliminary results are presented. The AIDA Project initiative in Italy and Tunis suggests that a joint effort by Health Professionals, Scientific Societies, and patients' associations can make a difference. Even before its closure the preliminary results produced by the AIDA Project are very encouraging. The size of the database, with around 14500 images and each with their respective report, is the biggest within the field of Indirect ImmunoFluorescence applied to autoimmune diseases diagnosis in the world. Additionally we have compiled around 1000 images with two concordant reports established by immunology experts and including different patterns, which have composed our first Gold Standard database. This has been the basis for "learning" of the CyclopusCAD Immuno software.
This Gold Standard database has proven to be of great interest and has been considered for use as reference to evaluate Junior and Fundamental Immunologists and CAD performance. The automatic CAD system used and optimized in the AIDA Project has been described and its performance was evaluated. In this work the results in terms of performance of Junior Immunologists, CAD, and Immunologists with the aid of CAD have also been reported. The CAD system showed higher Intensity Accuracy (85,5% versus 66,0% and 66,0%), higher Patterns Accuracy (79,3% versus 48,0% and 66,2%), and higher MAC (79,4% versus 56,7% and 64. 2%). Another objective of this project is to evaluate the added value of the CAD used as a second Reader. The analysis conducted here showed that the CAD support improves the performances of Junior Immunologists up to as much as 45%, as highlighted by the comparisons reported on Tables  5  and 7.
Considering the concordance level between Fundamental Immunologists evaluated at 71%, the CAD seems to bring the same level of performance. Indeed, when compared to Gold Standard, the CAD showed a mean accuracy of 85% for intensity evaluation and 79% for pattern recognition. With these preliminary results, we can conclude that the objectives of the project are being reached with the demonstration that the CAD shows a higher performance than Junior Immunologists and equivalent results with Immunology Experts. In a further step, the Gold Standard database should be enriched, including the addition of more double reported and triple reported images. With such a high number of images of high-quality reporting, we would be able to improve the CAD performance and our quality assessment approach in order to offer a product of high confidence that could be used as second Reader to student learning and to remote diagnosis.
In ontology-based data access (OBDA), database querying is enriched with an ontology that provides domain knowledge and additional vocabulary for query formulation. We identify query emptiness and predicate emptiness as two central reasoning services in this context. Query emptiness asks whether a given query has an empty answer over all databases formulated in a given vocabulary. Predicate emptiness is defined analogously, but quantifies universally over all queries that contain a given predicate. In this paper, we determine the computational complexity of query emptiness and predicate emptiness in the EL, DL-Lite, and ALC-families of description logics, investigate the connection to ontology modules, and perform a practical case study to evaluate the new reasoning services.
Introduction In recent years, the paradigm of ontology-based data access (OBDA) has gained increased popularity. The general idea is to add an ontology to database querying to provide domain knowledge and to enrich the vocabulary that is available for the formulation of queries. This is particularly useful when the data to be queried is highly incomplete and when multiple data sources with diverging vocabularies are integrated  (Poggi, Lembo, Calvanese, De Giacomo, Lenzerini, & Rosati, 2008). OBDA has been taken up with particular verve in the area of description logic  (DL)  where it has been studied intensively both for lightweight DLs such as the members of the DL-Lite and EL families, which are tractable regarding the data complexity of querying, and for more expressive DLs such as those of the ALC and SHIQ families where querying is intractable in data complexity.
Static analysis tools for analysing these queries would thus be very useful. In this paper, we consider the fundamental static analysis problem of query emptiness as well as a natural variation of it called predicate emptiness. In the former, the problem is to decide whether a given query q provides an empty answer over all databases formulated in a given data vocabulary ⌃. Query emptiness thus helps to identify queries which are useless due to wrong use of the ontology vocabulary. It is a standard static analysis problem in many subareas of database theory such as XML, see e. g. (Benedikt, Fan, & Geerts, 2008 ) and references therein. As an example, consider the following simple ontology O: DiabetesPatient ⌘ Patient u 9has disease. Diabetes DiabetesPatientwithoutMedication ⌘ Patient u 9has disease.
Diabetes u ¬9on medication for. Diabetes Assume that O is used to support querying of a medical patient database which has a unary table for the conept names Patient and Diabetes and binary tables for the role names has disease and on medication for, distinguishing in particular between diabetes of type 1 and type 2. For example, the database could be given by the following set A of assertions: Patient(a), Patient(b), has disease(a, type1), on medication for(a, type1), has disease(b, type2), Diabetes(type1), Diabetes(type2). Thus, a is a patient with diabetes of type 1 who is on medication for it and b is a patient with diabetes of type 2. In OBDA, queries are interpreted under an open world assumption and thus one is interested in the certain answers to a query q w. r. t. O and A, that is, the answers to q on which all extension of A that satisfy the ontology O are in agreement.
For the concrete query q 1 (x) = DiabetesPatient(x), Figure  1 : Known complexity results for query evaluation and new complexity results for emptiness a and b are the certain answers to q 1 (x) w. r. t. O and A-despite the fact that the predicate Diabetes-Patient used in q 1 (x) does not occur in A. Since A is formulated using only the data vocabulary ⌃ = {Patient, has disease, on medication for, Diabetes}, we say that q 1 (x) is non-empty for ⌃ given O. We regard this as evidence that q 1 (x) is a potentially useful query on databases formulated in vocabulary ⌃. As another example, consider the query q 2 (x) = DiabetesPatientwithoutMedication(x) There is no certain answer to q 2 (x) w. r. t. O and A since, under the open world assumption, the mere absence of the information that b is on medication for diabetes of type 1 or type 2 does not imply that its negation is true.
One can even show that, whatever database A 0 formulated in vocabulary ⌃ we use, there will never be any certain answer to q 2 (x) w. r. t. O and A 0. In this case, we say that q 2 (x) is empty for ⌃ given O. In contrast to q 1 (x), this query is thus useless on ⌃-databases. We also consider predicate emptiness, the problem to decide whether for a given predicate p and data vocabulary ⌃, it is the case that all queries q which involve p yield an empty answer over all ⌃-databases. In the example above, the predicate DiabetesPatientwithoutMedication is empty w. r. t. O and ⌃ for the important class of conjunctive queries (queries constructed from atomic formulas using conjunction and existential quantification). Predicate emptiness can be used to identify predicates in the ontology that are useless for query formulation, before even starting to construct a concrete query.
We adopt the standard notion of combined complexity, which is measured in terms of the size of the whole input (TBox, data vocabulary, and query or predicate symbol). Because of the restricted data vocabulary ⌃ and the quantification over all ⌃-databases in their definition, query emptiness and predicate emptiness do not reduce to standard reasoning problems such as query evaluation and query containment. Formally, this is demonstrated by our undecidability result for ALCF, which should be contrasted with the decidability of query entailment and containment in this DL, cf. (Calvanese, De Giacomo, & Lenzerini, 1998). When emptiness is decidable, the complexity still often differs from that of query evaluation. To simplify the comparison, we display in Figure  1  known complexity results for query evaluation in the considered DLs; please consult  (Baader, Brandt, & Lutz, 2005 , 2008; Krötzsch, Rudolph, & Hitzler, 2007; Eiter, Gottlob, Ortiz, & Simkus, 2008)  for the results concerning EL and its Horn extensions,  (Calvanese, De Giacomo, Lembo, Lenzerini, & Rosati, 2007; Artale, Calvanese, Kontchakov, & Zakharyaschev, 2009)  for the results on DL-Lite, and  (Tobies, 2001; Hustadt, Motik, & Sattler, 2004; Lutz, 2008; Ortiz, Simkus, & Eiter, 2008)  for the results on DLs from the ALC family.
By comparing the two sides of Figure  1 , we observe that there is no clear relationship between the complexity of emptiness checking and the complexity of query evaluation. Indeed, while the problems are often of similar complexity, there are several cases in which emptiness checking is more difficult than the corresponding query evaluation problem. It can also be the other way around, and complexities can also be incomparable. Note that for the extension EL ? of EL with the bottom concept ? (used to express class disjointness), we observe a particularly significant difference between the tractability of evaluating instance queries and the EXPTIME-completeness of checking IQ-query emptiness. A key ingredient in developing algorithms and establishing upper complexity bounds for emptiness is to show that, when searching for databases that witness non-emptiness (such as the database A for the non-emptiness of q 1 for ⌃ given O in the above example), one can often focus on a single database constructed specifically for that purpose or on a class of databases that are easier to handle than the class of all databases.
Which single database / class of databases to consider depends on the DL in question. For this reason, a secondary theme of this paper is to analyze the shape of witness databases. It turns out that in ALC and its extension ALCI with inverse roles, we can consider a single exponential-size database whose construction is reminiscent of type elimination and filtration constructions known from the modal logic literature. For EL and its extension ELI, we may also concentrate on a single witness candidate, but a much simpler one: it consists of all facts that can be constructed using the data vocabulary and a single constant. For other extensions of EL, we use a class of databases as witness candidates, namely those that have a tree or forest structure. In DL-Lite, we may restrict our attention to the class of databases whose size is bounded polynomially w.
r. t. the input query and ontology. To demonstrate that predicate emptiness is a useful reasoning service for static analysis, we perform experiments using the well-known and large-scale medical ontology SNOMED CT coupled with both a real-world data vocabulary (corresponding to terms obtained by analyzing clinical notes from a hospital) and with randomly generated vocabularies. For the real world vocabulary, which contains 8,858 of the ⇠370,000 concept names and 16 of the 62 role names in SNOMED  CT, 16, 212  predicates turned out to be non-empty for IQs and 17,339 to be non-empty for CQs. Thus, SNOMED CT provides a very substantial number of additional predicates for query formulation while a large number of other predicates cannot meaningfully be used in queries over ⌃-databases; thus, identifying the relevant predicates via predicate emptiness is potentially very helpful.
We also consider the use of query and predicate emptiness for the extraction of modules from an ontology. Thus, instead of using emptiness directly to support query formulation, we show how it can be used to simplify an ontology. A ⌃-substitute of an ontology is a subset of the ontology that gives the same certain answers to all conjunctive queries over all ⌃-databases. Replacing a large ontology with a (potentially quite small) ⌃-substitute supports comprehension of the ontology and thereby the formulation of meaningful queries. We show that, for ELI, one can use predicate emptiness to extract a particularly natural ⌃-substitute of an ontology, called its CQ ⌃ -core, containing exactly those axioms from the original ontology that contain only predicates which are non-empty for ⌃-databases.
Thus, all predicates in the CQ ⌃ -core of an ontology can be meaningfully used in queries posed to ⌃-databases. In our example, the CQ ⌃ -core of the ontology O is O 0 = {DiabetesPatient ⌘ Patient u 9has disease. Diabetes}. The second axiom was removed because any CQ that contains DiabetesPatientwithoutMedication is empty for ⌃ given O. To analyze the practical interest of CQ ⌃ -cores, we carry out a case study where we compute CQ ⌃ -cores for the ontology SNOMED CT coupled with various signatures, showing that they tend to be drastically smaller than the original ontology and also smaller than ?-modules, a popular way of extracting modules from ontologies  (Grau, Horrocks, Kazakov, & Sattler, 2008). This article is structured as follows. We begin in Section 2 by recalling the syntax and semantics of the description logics considered in this work.
For ALC and ALCI, we provide tight complexity bounds, showing NEXPTIME-completeness for all three emptiness problems in ALC and for IQ-query emptiness and CQ-predicate emptiness in ALCI, and 2EXPTIME-completeness for CQ-query emptiness in ALCI. The situation is dramatically (and surprisingly) different for ALCF, for which all emptiness problems are proven undecidable. As previously mentioned, the complexity upper bounds for ALC and ALCI rely on a characterization of non-emptiness in terms of a special witness database. The complexity lower bounds and undecidability results are proven by means of reductions from tiling problems. In Section 5, we continue our investigation of query and predicate emptiness by considering the DL EL and its Horn extensions. For plain EL, we provide a simple characterization of nonemptiness in terms of a maximal singleton database, which allows us to show that all three emptiness problems can be decided in polynomial time.
Using the same characterization and the fact that standard reasoning in ELI is EXPTIME-complete, we obtain EXPTIME-completeness of emptiness checking in ELI. For extensions of EL that allow for contradictions, the singleton database may not be consistent with the ontology, requiring another approach. To handle such extensions, we show that it is sufficient to consider tree-shaped databases as witnesses for non-emptiness, and we devise a decision procedure for emptiness checking based upon tree automata. We obtain in this manner an EXPTIME upper bound for Horn-ALCIF, which sharply contrasts with our undecidability result for (non-Horn) ALCF. Interestingly, we can show a matching EXPTIME lower bound for the considerably simpler DL EL ? , for which standard reasoning tasks are tractable. In Section 6, we turn our attention to the DL-Lite family of lightweight DLs, which are the most commonly considered DLs for ontology-based data access.
We show that CQ-query emptiness is coNP-complete for all considered DL-Lite dialects. For IQ-query emptiness and CQ-predicate emptiness, we show that the complexity depends on whether the considered dialect allows for conjunctions on the left-hand side of axioms. For standard dialects like DL-Lite core , DL-Lite R , and DL-Lite F , which do not allow for conjunction, we show that IQ-query emptiness and CQ-predicate emptiness are NLOGSPACE-complete. For dialects like DL-Lite horn that admits conjunctions, both IQ-query emptiness and CQ-predicate emptiness are coNP-complete. This difference in complexity is due to the fact that for dialects allowing conjunction, we need to consider witnesses for nonemptiness that are of polynomial size, whereas in the absence of conjunction, it is sufficient to consider databases that consist of a single assertion.
, 2008; Kazakov, 2009). As the original definition from  (Hustadt et al. , 2007)  based on polarity is rather technical, we prefer the above (equivalent) definition. The size |T | of a TBox T is obtained by taking the sum of the lengths of its axioms, where the length of an axiom is the number of symbols needed to write it as a word. Databases are represented using an ABox, which is a finite set of concept assertions A(a) and role assertions r(a, b), where a, b are drawn from a countably infinite set N I of individual names, A is a concept name, and r is a role name. Note that role assertions cannot use inverse roles. As a shortcut, though, we sometimes write r (a, b) 2 A for r(b, a) 2 A. We use Ind(A) to denote the set of individual names used in the ABox A. A knowledge base is a pair K = (T , A) with T a TBox and A an ABox.
Query and Predicate Emptiness We introduce the central notions and reasoning problems studied in this paper, show how they are interrelated, and make some basic observations that are used throughout the paper. The following definition introduces the different notions of emptiness studied in this paper. Definition 2 Let T be a TBox, ⌃ a signature, and Q 2 {IQ, CQ} a query language. Then we call • an Q-query q empty for ⌃ given T if for all ⌃-ABoxes A that are satisfiable w. r. t. T , we have cert T ,A (q) = ;. • a predicate S Q-empty for ⌃ given T if every Q-query q with S 2 sig(q) is empty for ⌃ given T. In what follows, the signatures ⌃ used in ABoxes will be called ABox signatures. We quantify over all ABoxes that are formulated in the ABox signature to address typical database applications in which the data changes frequently, and thus deciding emptiness based on a concrete ABox is not of much interest.
As an example, assume that ABoxes are formulated in the signature ⌃ = {Person, hasDisease, DiseaseA, DiseaseB} where here and in the following, all upper-case words are concept names and all lower-case ones are role names. This signature is typically fixed in the application design phase, similar to schema design in databases. For the TBox, we take T = {Person v 9hasFather. (Person u Male), DiseaseA v InfectiousDisease}. Then both the IQ InfectiousDisease(v) and the CQ 9v hasFather(u, v) are non-empty for ⌃ given T despite using predicates that cannot occur in the data, as witnessed by the ⌃-ABoxes {DiseaseA(a)} and {Person(a)}, respectively. This illustrates how the TBox T enriches the vocabulary that is available for query formulation. By contrast, the CQ 9v9v 0 (hasFather(u, v) ^hasDisease(v, v 0 ) ^InfectiousDisease(v 0 )), which uses the same predicates plus an additional one from the ABox signature, is empty for ⌃ given T.
Related Work Query emptiness is a fundamental problem in the static analysis of database queries. It is also called the query satisfiability problem. For XML, for example, it takes the following form: given an XPath query p and a DTD D, does there exist an XML document T such that T conforms to D and the answer of p on T is non-empty. The complexity of this problem ranges from tractable to undecidable depending on the XPath fragment, see e. g. (Benedikt et al. , 2008)  and references therein. In a DL context, query emptiness has been first considered in  (Lubyte & Tessaris, 2008)  where it is used as a step to guide the enrichment of ontologies. The query emptiness problem studied in this paper is a special case of the following query containment problem, first considered  (Bienvenu, Lutz, & Wolter, 2012).
Acknowledgments We thank  Mario Berta ,  Marco Tomamichel , and  Volkher Scholz  for making us aware of the application of our result to topological order of quantum states (described in Section 3). We also thank  Mario Berta ,  Fernando Brandão ,  Philipp Kammerlander ,  Joseph Renes ,  Burak S ¸ahinoglu ,  Volkher Scholz ,  Marco Tomamichel ,  Michael Walter  and  Mark Wilde  for discussions about approximate Markov chains. This project was supported by the  European Research Council (ERC)  via grant No. 258932 , by the  Swiss National Science Foundation (SNSF)  via the  National Centre of Competence in Research "QSIT" , and by the  European Commission  via the project " RAQUEL ".