Semantic gap

The semantic gap characterizes the difference between two descriptions of an object by different linguistic representations, for instance languages or symbols. In computer science, the concept is relevant whenever ordinary human activities, observations, and tasks are transferred into a computational representation Smeulders AWM, Worring M, Santini S, Gupta A, Jain R. Content-Based Image Retrieval at the End of the Early Years. IEEE Trans Pattern Anal Mach Intell 2000;22(12):1349-80. ] Dorai C, Venkatesh S. Bridging the Semantic Gap with Computational Media Aesthetics. IEEE MultiMedia 2003;10(2):15-17.] .

More precisely the gap means the difference between ambiguous formulation of contextual knowledge in a powerful language (e.g. natural language) and its sound, reproducible and computational representation in a formal language (e.g. programming language). Semantics of an object depends on the context it is regarded within. For practical application this means any formal representation of real world tasks requires the translation of the contextual expert knowledge of an application (high-level) into the elementary and reproducible operations of a computing machine (low-level). Since natural language allows the expression of tasks which are impossible to compute in a formal language there is no mean to automatize this translation in a general way. Moreover the examination of languages within the Chomsky hierarchy indicates that there is no formal and consequently automated way of translating from one language into another above a certain level of expressional power.

Theoretical background

The yet unproven but commonly accepted Church-Turing thesis states that a turing machine and all equivalent formal languages such as the lambda calculus perform and represent all formal operations respectively as applied by a computing human. However the selection of adequate operations for the correct computation itself is not formally deducible, moreover it depends on the computability of the underlying problem. Tasks, such as the halting problem, may be formulated comprehensively in natural language, but the computational representation will not terminate or does not provide a usable result, which is proven by Rice's theorem. The general expression of limitations for rule based deduction by Gödel's incompleteness theorem indicates that the semantic gap is never to be fully closed. These are general statements, considering the generalized limits of computation on the highest level of abstraction where the semantic gap manifests itself. There are however lots of subsets of problems which may be translated automatically, especially in the higher numbered levels of the Chomsky hierarchy.

Formal languages

Real world tasks are formalized by programming languages, which are executed on computers based on the von Neumann architecture. Since programming languages are only comfortable representations of the Turing machine any program on a von Neumann computer has the same properties and limitations as the Turing machine or its equivalent representation. Consequently every programming language such as CPU level machine code, assembler, or any high level programming language has the same expressional power as the underlying Turing machine is able to compute. There is no semantic gap between them since a program is transferred from the high level language to the machine code by a program, e.g. a compiler which itself runs on a Turing machine without any user interaction. The semantic gap actually opens between the selection of the rules and the representation of the task.

Practical Consequences

Selection of rules for formal representations of real world applications, corresponds to writing a program. Writing programs is independent from the actual programming language and basically requires the translation of the domain specific knowledge of the user into the formal rules operating a turing machine. It is this transfer from contextual knowledge into formal representation which cannot be automatized with respect to the theoretical limitations of computation. Consequently any mapping from real world applications into computer applications requires a certain amount of technical background knowledge by the user, where the semantic gap manifests itself.

It is a fundamental task of software engineering to close the gap between application specific knowledge and technically doable formalization. For this purpose domain specific (high-level) knowledge must be transferred into an algorithm and its parameters (low-level). This requires the dialogue between user and developer. Aim is always a software which allows the user to represent his knowledge as parameters of an algorithm without knowing the details of the implementation, and to interpret the outcome of the algorithm without the aid of the developer. For this purpose user interfaces play the key role in software design, while developers are supported by frameworks which help organizing the integration of contextual information.

Examples

Document Retrieval

A simple example can be formulated as a series of increasingly difficult natural language queries to locate a "target document" that may or may not exist locally on a known computer system.

Example queries:
* 1) Locate any file in the known directory "/usr/local/funny".
* 2) Locate any file where the word "funny" appears in the filename.
* 3) Locate any text file where the word "funny" or the substring "humor" appears in the text.
* 4) Locate any mp3 file where either "funny", "comic" or "humor" appears in the metadata.
* 5) Locate any file of any type related to humor.
* 6) Locate any image that is likely to make my grandmother laugh.

The progressive difficulty of these queries is represented by the increasing degree of abstraction from the types and semantics defined the system architecture (directories and files on a known computer) to the types and semantics that occupy the realm of ordinary human discourse (subjects such as "humor" and entities such as "my grandmother"). Moreover, this disparity of realms is further complicated by leaky abstractions, such as is common in the case of query 4), where the "target document" may exist, but may not encapsulate the "metadata" in a manner expected by the user, nor the designer of the query processing system.

Image Analysis

Image analysis is a typical domain for which a high degree of abstraction from low-level Methods is required, and where the semantic gap immediately affects the user. If image content is to be identified to understand the meaning of an image, the only available independent information is the low-level pixel data. Textual annotations always depend on the knowledge, capability of expression and specific language of the annotator and therefore is unreliable. To recognize the displayed scenes from the raw data of an image the algorithms for selection and manipulation of pixels must be combined and parameterized in an adequate manner and finally linked with the natural description. Even the simple linguistic representation of shape or color such as round or yellow requires entirely different mathematical formalization methods, which are neither intuitive nor unique and sound.

Layered Systems

In many layered systems, some conflicts when concepts at a high level of abstraction need to be translated into lower, more concrete artifacts. This mismatch is often called semantic gap.

Databases

OODBMSs (object-oriented database management system) advocates sometimes claim that these databases help to reduce the semantic gap between the application domain (miniworld) and the traditional RDBMS systems. [http://www.findarticles.com/p/articles/mi_m0ISJ/is_n2_v33/ai_15519487/pg_4] . However Relational proponents would posit the exact opposite, because by definition object databases fix the data being recorded into a single binding abstraction.

ee also

* Leaky abstraction
* Text simplification
* Semantic differential

References